Amplifying privacy in privacy amplification

Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi, Eric Miles, Leonid Reyzin

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


We study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. Despite being extensively studied in the literature, the problem of designing "optimal" efficient privacy amplification protocols is still open, because there are several optimization goals. The first of them is (1) minimizing the entropy loss L = k - m. Other important considerations include (2) minimizing the number of communication rounds, (3) maintaining security even after the secret key is used (this is called post-application robustness), and (4) ensuring that the protocol P does not leak some "useful information" about the source X (this is called source privacy). Additionally, when dealing with a very long source X, as happens in the so-called Bounded Retrieval Model (BRM), extracting as long a key as possible is no longer the goal. Instead, the goals are (5) to touch as little of X as possible (for efficiency), and (6) to be able to run the protocol many times on the same X, extracting multiple secure keys. Achieving goals (1)-(4) (or (2)-(6) in BRM) simultaneously has remained open. In this work we improve upon the current state-of-the-art, by designing a variety of new privacy amplification protocols, thereby achieving the following goals for the first time: - 4-round (resp. 2-round) source-private protocol with optimal entropy loss L = O(λ), whenever k = Ω(λ2) (resp. k > n/2(1-α) for some universal constant α > 0) . - 3-round post-application-robust protocols with optimal entropy loss L = O(λ), whenever k = Ω(λ2) or k > n/2(1-α) (the latter is also source-private). - The first BRM protocol capable of extracting the optimal number Θ(k/λ) of session keys, improving upon the previously best bound Θ(k/λ2). (Additionally, our BRM protocol is post-application-robust, takes 2 rounds, and can be made source-private by increasing the number of rounds to 4.).

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings
PublisherSpringer Verlag
Number of pages16
EditionPART 2
ISBN (Print)9783662443804
StatePublished - 2014
Event34rd Annual International Cryptology Conference, CRYPTO 2014 - Santa Barbara, CA, United States
Duration: Aug 17 2014Aug 21 2014

Publication series

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


Other34rd Annual International Cryptology Conference, CRYPTO 2014
Country/TerritoryUnited States
CitySanta Barbara, CA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Amplifying privacy in privacy amplification'. Together they form a unique fingerprint.

Cite this