Threshold and Proactive Pseudo-Random Permutations

Yevgeniy Dodis; Aleksandr Yampolskiy; Moti Yung

Paper 2006/017 Original: eprint.iacr.org/2006/017 ↗

Threshold and Proactive Pseudo-Random Permutations

Yevgeniy Dodis

Aleksandr Yampolskiy

Moti Yung

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.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2006-01-17: last updated; 2006-01-17: published
Short URL: https://ia.cr/2006/017
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2006/017,
      author = {Yevgeniy Dodis and Aleksandr Yampolskiy and Moti Yung},
      title = {Threshold and Proactive Pseudo-Random Permutations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/017},
      year = {2006},
      url = {https://eprint.iacr.org/2006/017}
}