Paper 2015/1094

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 $X$ with min-entropy $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 non-malleable 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 non-malleable extractor and introduce what we call an affine-malleable 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 inner-product function $\IP{\cdot,\cdot}:\F^n \times \F^n \mapsto \F$ 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 $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. 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.