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

Gil Cohen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

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 non-malleable 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 min-entropy 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.

Original languageEnglish (US)
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages188-196
Number of pages9
ISBN (Electronic)9781509039333
DOIs
StatePublished - Dec 14 2016
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: Oct 9 2016Oct 11 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Other

Other57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
CountryUnited States
CityNew Brunswick
Period10/9/1610/11/16

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Correlation breakers
  • Extractors
  • Independence-preserving mergers
  • Non-malleable
  • Privacy amplification

Fingerprint Dive into the research topics of 'Making the Most of Advice: New Correlation Breakers and Their Applications'. Together they form a unique fingerprint.

Cite this