Threshold and proactive pseudo-random permutations

Yevgeniy Dodis; Aleksandr Yampolskiy; Moti Yung

doi:10.1007/11681878_28

Threshold and proactive pseudo-random permutations

Yevgeniy Dodis, Aleksandr Yampolskiy, Moti Yung

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Theory of Cryptography
Subtitle of host publication	Third Theory of Cryptography Conference, TCC 2006, Proceedings
Pages	542-560
Number of pages	19
DOIs	https://doi.org/10.1007/11681878_28
State	Published - 2006
Event	3rd Theory of Cryptography Conference, TCC 2006 - New York, NY, United States Duration: Mar 4 2006 → Mar 7 2006

Publication series

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

Other

Other	3rd Theory of Cryptography Conference, TCC 2006
Country/Territory	United States
City	New York, NY
Period	3/4/06 → 3/7/06

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11681878_28

Cite this

Dodis, Y., Yampolskiy, A., & Yung, M. (2006). Threshold and proactive pseudo-random permutations. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, Proceedings (pp. 542-560). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3876 LNCS). https://doi.org/10.1007/11681878_28

Threshold and proactive pseudo-random permutations. / Dodis, Yevgeniy; Yampolskiy, Aleksandr; Yung, Moti.
Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, Proceedings. 2006. p. 542-560 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3876 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Dodis, Y, Yampolskiy, A & Yung, M 2006, Threshold and proactive pseudo-random permutations. in Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3876 LNCS, pp. 542-560, 3rd Theory of Cryptography Conference, TCC 2006, New York, NY, United States, 3/4/06. https://doi.org/10.1007/11681878_28

@inproceedings{097a0aaf75d64e6291184c34e625d92c,

title = "Threshold and proactive pseudo-random permutations",

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.",

keywords = "Distributed Block Ciphers, Distributed Luby-Rackoff Construction, Oblivious Pseudo-Random Functions, Threshold Cryptography",

author = "Yevgeniy Dodis and Aleksandr Yampolskiy and Moti Yung",

year = "2006",

doi = "10.1007/11681878_28",

language = "English (US)",

isbn = "3540327312",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "542--560",

booktitle = "Theory of Cryptography",

}

TY - GEN

T1 - Threshold and proactive pseudo-random permutations

AU - Dodis, Yevgeniy

AU - Yampolskiy, Aleksandr

AU - Yung, Moti

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - Distributed Block Ciphers

KW - Distributed Luby-Rackoff Construction

KW - Oblivious Pseudo-Random Functions

KW - Threshold Cryptography

UR - http://www.scopus.com/inward/record.url?scp=33745526470&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745526470&partnerID=8YFLogxK

U2 - 10.1007/11681878_28

DO - 10.1007/11681878_28

M3 - Conference contribution

AN - SCOPUS:33745526470

SN - 3540327312

SN - 9783540327318

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 542

EP - 560

BT - Theory of Cryptography

T2 - 3rd Theory of Cryptography Conference, TCC 2006

Y2 - 4 March 2006 through 7 March 2006

ER -

Threshold and proactive pseudo-random permutations

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this