Cryptology ePrint Archive: Report 2006/017

Threshold and Proactive Pseudo-Random Permutations

Yevgeniy Dodis and Aleksandr Yampolskiy and 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.

Category / Keywords: Distributed Block Ciphers, Distributed Luby-Rackoff Construction, Oblivious Pseudo-Random Functions, Threshold Cryptography.

Publication Info: Extended abstract is to appear in TCC 2006.

Date: received 14 Jan 2006

Contact author: aleksandr yampolskiy at yale edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20060117:204725 (All versions of this report)

Short URL: ia.cr/2006/017

Discussion forum: Show discussion | Start new discussion