Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-028 | 7th February 2018 20:36

Pseudorandom Correlation Breakers, Independence Preserving Mergers and their Applications


Authors: Xin Li
Publication: 8th February 2018 14:52
Downloads: 120


The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in the following five seemingly different topics: seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey graphs), non-malleable independent source extractors, and non-malleable codes in the split state model. Two key ingredients used in these works are correlation breakers and independence preserving mergers. By giving very efficient constructions of these two objects, we now have close to optimal solutions to the above five problems \cite{Li17}: seeded non-malleable extractors with seed length and entropy requirement $O(\log n+\log(1/\epsilon)\log \log (1/\epsilon))$ for error $\epsilon$; two-round privacy amplification protocols with optimal entropy loss for security parameter up to $\Omega(k/\log k)$, where $k$ is the entropy of the shared weak source; two-source extractors for entropy $O(\log n \log \log n)$; non-malleable two-source extractors for entropy $(1-\gamma)n$ with error $2^{-\Omega(n/\log n)}$; and non-malleable codes in the $2$-split state model with rate $\Omega(1/\log n)$. However, in all cases there is still a small gap to optimum and the motivation to close this gap remains strong. On the other hand, previous techniques seem to have reached their limit and insufficient for this purpose.

In this paper we introduce new techniques to recycle the entropy used in correlation breakers and independence preserving mergers. This allows us to break the barriers of previous techniques and give further improvements to the above problems. Specifically, we obtain the following results: (1) a seeded non-malleable extractor with seed length $O(\log n)+\log^{1+o(1)}(1/\epsilon)$ and entropy requirement $O(\log \log n+\log(1/\epsilon))$, where the entropy requirement is asymptotically optimal by a recent result of Gur and Shinkar \cite{GurS18}; (2) a two-round privacy amplification protocol with optimal entropy loss for security parameter up to $\Omega(k)$, which solves the privacy amplification problem completely;\footnote{Except for the communication complexity, which is of secondary concern to this problem.} (3) a two-source extractor for entropy $O(\frac{\log n \log \log n}{\log \log \log n})$, which also gives an explicit Ramsey graph on $N$ vertices with no clique or independent set of size $(\log N)^{O(\frac{\log \log \log N}{\log \log \log \log N})}$;
(4) a non-malleable two-source extractor for entropy $(1-\gamma)n$ with error $2^{-\Omega(n \log \log n/\log n)}$; and (5) non-malleable codes in the $2$-split state model with rate $\Omega(\log \log n/\log n)$. Some of our techniques are similar in spirit to what has been done in previous constructions of pseudorandom generators for small space computation \cite{Nisan92, NisanZ96}, and we believe they can be a promising way to eventually obtain optimal constructions to the five problems mentioned above.

ISSN 1433-8092 | Imprint