Paper 2015/1094
Affinemalleable Extractors, Spectrum Doubling, and Application to Privacy Amplification
Divesh Aggarwal, Kaave Hosseini, and Shachar Lovett
Abstract
The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a ``weak" random source $X$ with minentropy $k$ and a uniformly random seed $Y$ of length $d$, and outputs a string of length close to $k$ that is close to uniform and independent of $Y$. Dodis and Wichs~\cite{DW09} introduced a generalization of randomness extractors called nonmalleable extractors ($\nmExt$) where $\nmExt(X,Y)$ is close to uniform and independent of $Y$ and $\nmExt(X,f(Y))$ for any function $f$ with no fixed points. We relax the notion of a nonmalleable extractor and introduce what we call an affinemalleable extractor ($\AmExt: \F^n \times \F^d \mapsto \F$) where $\AmExt(X,Y)$ is close to uniform and independent of $Y$ and has some limited dependence of $\AmExt(X,f(Y))$  that conditioned on $Y$, $(\AmExt(X,Y), \AmExt(X,f(Y)))$ is close to $(U, A \cdot U + B)$ where $U$ is uniformly distributed in $\F$ and $A, B \in \F$ are random variables independent of $\F$. We show under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture) that the innerproduct function $\IP{\cdot,\cdot}:\F^n \times \F^n \mapsto \F$ is an affinemalleable extractor. As a modest justification of the conjecture, we show that a weaker version of the conjecture is implied by the widely believed Polynomial FreimanRuzsa conjecture. We also 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. The main application of nonmalleable extractors and its many variants has been in constructing secure privacy amplification protocols. We show that affinemalleable extractors along with affineevasive sets can also be used to construct efficient privacy amplification protocols. We show that our protocol, under the Spectrum Doubling Conjecture, achieves near optimal parameters and achieves additional security properties like source privacy that have been the focus of some recent results in privacy amplification.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Preprint. MINOR revision.
 Contact author(s)
 divesh aggarwal @ gmail com
 History
 20151110: received
 Short URL
 https://ia.cr/2015/1094
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/1094, author = {Divesh Aggarwal and Kaave Hosseini and Shachar Lovett}, title = {Affinemalleable Extractors, Spectrum Doubling, and Application to Privacy Amplification}, howpublished = {Cryptology {ePrint} Archive, Paper 2015/1094}, year = {2015}, url = {https://eprint.iacr.org/2015/1094} }