Making the Most of Advice: New Correlation Breakers and Their Applications

Abstract

A typical obstacle one faces when constructing pseudorandom objects is undesired correlations between random variables. Identifying this obstacle and constructing certain types of "correlation breakers" was central for recent exciting advances in the construction of multi-source and nonmalleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These are algorithms that break the correlation a "bad" random variable Y ' has with a "good" random variable Y using an "advice" - a fixed string α that is associated with Y which is guaranteed to be distinct from the corresponding string α' associated with Y '. Prior to this work, explicit constructions of correlation breakers with advice require the entropy of the involved random variables to depend linearly on the advice length. In this work, building on independence-preserving mergers, a pseudorandom primitive that was recently introduced by Cohen and Schulman, we devise a new construction of correlation breakers with advice that has optimal, logarithmic, dependence on the advice length. This enables us to obtain the following results. . We construct an extractor for 5 independent n-bit sources with min-entropy (log n)^(1+o(1)). This result puts us tantalizingly close to the goal of constructing extractors for 2 sources with min-entropy O(log n), which would have exciting implications to Ramsey theory. . We construct non-malleable extractors with error guarantee ε for n-bit sources, with seed length d = O(log n)+ (log(1/ε))^(1+o(1)) for any min-entropy k = Ω(d). Prior to this work, all constructions require either very high minentropy or otherwise have seed length ω(log n) for any ε. Further, our extractor has near-optimal output length. Prior constructions that achieve comparable output length work only for very high min-entropy k ≈ n/2. . By instantiating the Dodis-Wichs framework with our non-malleable extractor, we obtain near-optimal privacy amplification protocols against active adversaries, improving upon all (incomparable) known protocols.

Additional details