Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification

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 [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 : Fn x Fd -> 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 epsilon-close to (U, A U + B) where U is uniformly distributed in F and A, B is an element of F are random variables independent of U. We show that the inner-product function (,) : FnxFn -> F is an affine-malleable extractor for min-entropy k = n/2 + Omega(log(1/epsilon)). Moreover, under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture), we show that this holds for k = Omega(log n log(1/epsilon)). 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 their 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. This gives a much simpler protocol for min-entropy k = n/2 + Omega(log(1/epsilon)), and additionally, 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.

Applications of Derandomization Theory in Coding

Mahdi Cheraghchi Bashi Astaneh

Randomized techniques play a fundamental role in theoretical computer science and discrete mathematics, in particular for the design of efficient algorithms and construction of combinatorial objects. The basic goal in derandomization theory is to eliminate or reduce the need for randomness in such randomized constructions. Towards this goal, numerous fundamental notions have been developed to provide a unified framework for approaching various derandomization problems and to improve our general understanding of the power of randomness in computation. Two important classes of such tools are pseudorandom generators and randomness extractors. Pseudorandom generators transform a short, purely random, sequence into a much longer sequence that looks random, while extractors transform a weak source of randomness into a perfectly random one (or one with much better qualities, in which case the transformation is called a randomness condenser). In this thesis, we explore some applications of the fundamental notions in derandomization theory to problems outside the core of theoretical computer science, and in particular, certain problems related to coding theory. First, we consider the wiretap channel problem which involves a communication system in which an intruder can eavesdrop a limited portion of the transmissions. We utilize randomness extractors to construct efficient and information-theoretically optimal communication protocols for this model. Then we consider the combinatorial group testing problem. In this classical problem, one aims to determine a set of defective items within a large population by asking a number of queries, where each query reveals whether a defective item is present within a specified group of items. We use randomness condensers to explicitly construct optimal, or nearly optimal, group testing schemes for a setting where the query outcomes can be highly unreliable, as well as the threshold model where a query returns positive if the number of defectives pass a certain threshold. Next, we use randomness condensers and extractors to design ensembles of error-correcting codes that achieve the information-theoretic capacity of a large class of communication channels, and then use the obtained ensembles for construction of explicit capacity achieving codes. Finally, we consider the problem of explicit construction of error-correcting codes on the Gilbert-Varshamov bound and extend the original idea of Nisan and Wigderson to obtain a small ensemble of codes, mostly achieving the bound, under suitable computational hardness assumptions.

EPFL2010

Applications of Derandomization Theory in Coding

Mahdi Cheraghchi Bashi Astaneh

EPFL2010