Threshold and proactive pseudo-random permutations

Yevgeniy Dodis, Aleksandr Yampolskiy, Moti Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 [41] and Dodis-Yampolskiy [25] with shared input and keys.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography
Subtitle of host publicationThird Theory of Cryptography Conference, TCC 2006, Proceedings
Pages542-560
Number of pages19
DOIs
StatePublished - 2006
Event3rd Theory of Cryptography Conference, TCC 2006 - New York, NY, United States
Duration: Mar 4 2006Mar 7 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3876 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Theory of Cryptography Conference, TCC 2006
CountryUnited States
CityNew York, NY
Period3/4/063/7/06

Keywords

  • Distributed Block Ciphers
  • Distributed Luby-Rackoff Construction
  • Oblivious Pseudo-Random Functions
  • Threshold Cryptography

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Threshold and proactive pseudo-random permutations'. Together they form a unique fingerprint.

Cite this