Affine-malleable 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 with min-entropy and a uniformly random seed of length , and outputs a string of length close to that is close to uniform and independent of . Dodis and Wichs~\cite{DW09} introduced a generalization of randomness extractors called non-malleable extractors () where is close to uniform and independent of and for any function with no fixed points.
We relax the notion of a non-malleable extractor and introduce what we call an affine-malleable extractor () where is close to uniform and independent of and has some limited dependence of - that conditioned on , is close to where is uniformly distributed in and are random variables independent of .
We show under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture) that the inner-product function is an affine-malleable extractor. As a modest justification of the conjecture, we show that a weaker version of the conjecture is implied by the widely believed Polynomial Freiman-Ruzsa conjecture.
We also study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret of min-entropy , and wish to agree on secret key of length over a public communication channel completely controlled by a computationally unbounded attacker Eve. The main application of non-malleable extractors and its many variants has been in constructing secure privacy amplification protocols.
We show that affine-malleable extractors along with affine-evasive 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.