A Caltech Library Service

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

Cohen, Gil (2016) Making the Most of Advice: New Correlation Breakers and Their Applications. In: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 188-196. ISBN 978-1-5090-3933-3.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle
Additional Information:© 2016 IEEE. I wish to thank Leonard Schulman for insightful and highly enjoyable discussions regarding this work and, generally, on the fascinating problem of randomness extraction. I wish to thank Ben Lund and Adam Sheffer for referring me to [Jon12], [RNRS14].
Subject Keywords:extractors; non-malleable; privacy amplification; correlation breakers; independence-preserving mergers
Record Number:CaltechAUTHORS:20170127-141811095
Persistent URL:
Official Citation:G. Cohen, "Making the Most of Advice: New Correlation Breakers and Their Applications," 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, 2016, pp. 188-196. doi: 10.1109/FOCS.2016.28 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73785
Deposited By: Tony Diaz
Deposited On:27 Jan 2017 22:24
Last Modified:27 Jan 2017 22:24

Repository Staff Only: item control page