International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Threshold and Proactive Pseudo-Random Permutations

Authors:
Yevgeniy Dodis
Aleksandr Yampolskiy
Moti Yung
Download:
URL: http://eprint.iacr.org/2006/017
Search ePrint
Search Google
Abstract: We construct a reasonably efficient threshold and proactive pseudo-random permutation (PRP). Our protocol needs only O(1) communication rounds. It tolerates up to (n-1)/2 of n dishonest servers in the semi-honest environment. Many protocols that use PRPs (e.g., a CBC block cipher mode) can now be translated into the distributed setting. Our main technique for constructing invertible threshold PRPs is a distributed Luby-Rackoff construction where both the secret keys *and* the input are shared among the servers. We also present protocols for obliviously computing pseudo-random functions by Naor-Reingold and Dodis-Yampolskiy with shared input and keys.
BibTeX
@misc{eprint-2006-21511,
  title={Threshold and Proactive Pseudo-Random Permutations},
  booktitle={IACR Eprint archive},
  keywords={Distributed Block Ciphers, Distributed Luby-Rackoff Construction, Oblivious Pseudo-Random Functions, Threshold Cryptography.},
  url={http://eprint.iacr.org/2006/017},
  note={Extended abstract is to appear in TCC 2006. aleksandr.yampolskiy@yale.edu 13163 received 14 Jan 2006},
  author={Yevgeniy Dodis and Aleksandr Yampolskiy and Moti Yung},
  year=2006
}