Paper 2013/723
Amplifying Privacy in Privacy Amplification
Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi, Eric Miles, and Leonid Reyzin
Abstract
We study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret $X$ of minentropy $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 {\em entropy loss} $L=km$ (it is known that the optimal value for $L=O(\lambda)$, where $\eps=2^{\lambda}$ is the desired security of the protocol). Other important considerations include (2) minimizing the number of communication rounds, (3) maintaining security even after the secret key is used (this is called {\em postapplication robustness}), and (4) ensuring that the protocol $P$ does not leak some ``useful information'' about the source $X$ (this is called {\em source privacy}). Additionally, when dealing with a very long source $X$, as happens in the socalled 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, and, indeed, all known protocols fail to achieve at least two of them. In this work we improve upon the current stateoftheart, by designing a variety of new privacy amplification protocols, in several cases achieving {\em optimal parameters for the first time}. Moreover, in most cases we do it by giving relatively {\em general transformations} which convert a given protocol $P$ into a ``better'' protocol $P'$. In particular, as special cases of these transformations (applied to best known prior protocols), we achieve the following privacy amplification protocols for the first time: \begin{itemize} \item $4$round (resp. $2$round) {\em sourceprivate} protocol with {\em optimal entropy loss} $L=O(\lambda)$, whenever $k = \Omega(\lambda^2)$ (resp. $k > \frac{n}{2}(1\alpha)$ for some universal constant $\alpha>0$). Best previous constant round sourceprivate protocols achieved $L=\Omega(\lambda^2)$. \item $3$round {\em postapplicationrobust} protocols with {\em optimal entropy loss} $L=O(\lambda)$, whenever $k = \Omega(\lambda^2)$ or $k > \frac{n}{2}(1\alpha)$ (the latter is also {\em sourceprivate}). Best previous postapplication robust protocols achieved $L=\Omega(\lambda^2)$. \item The first BRM protocol capable of extracting the optimal number $\Theta(k/\lambda)$ of session keys, improving upon the previously best bound $\Theta(k/\lambda^2)$. (Additionally, our BRM protocol is postapplicationrobust, takes $2$ rounds, and can be made sourceprivate by increasing the number of rounds to $4$.) \end{itemize}
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 Privacy AmplificationSource PrivacyBRMOptimal Entropy Loss
 Contact author(s)
 divesh aggarwal @ gmail com
 History
 20131124: last of 2 revisions
 20131107: received
 See all versions
 Short URL
 https://ia.cr/2013/723
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/723, author = {Divesh Aggarwal and Yevgeniy Dodis and Zahra Jafargholi and Eric Miles and Leonid Reyzin}, title = {Amplifying Privacy in Privacy Amplification}, howpublished = {Cryptology ePrint Archive, Paper 2013/723}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/723}}, url = {https://eprint.iacr.org/2013/723} }