Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors
Xin Li · arXiv (Cornell University) · 2016
In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are: (1) An explicit seeded non-malleable extractor with error $\\epsilon$ and seed length $d=O(\\log n)+O(\\log(1/\\epsilon)\\log \\log (1/\\epsilon))$, that supports min-entropy $k=\\Omega(d)$ and outputs $\\Omega(k)$ bits. Combined with the protocol in \\cite{DW09}, this gives a two round privacy amplification protocol with optimal entropy loss in the presence of an active adversary, for all security parameters up to $\\Omega(k/\\log k)$. (2) An explicit non-malleable two-source extractor for min-entropy $k \\geq (1-\\gamma)n$, some constant $\\gamma>0$, that outputs $\\Omega(k)$ bits with error $2^{-\\Omega(n/\\log n)}$. Combined with the connection in \\cite{CG14b} this gives a non-malleable code in the two-split-state model with relative rate $\\Omega(1/\\log n)$. This exponentially improves previous constructions, all of which only achieve rate $n^{-\\Omega(1)}$.\\footnote{The work of Aggarwal et. al \\cite{ADKO15} had a construction which "achieves" constant rate, but recently the author found an error in their proof.} (3)A two-source extractor for min-entropy $O(\\log n \\log \\log n)$, which also implies a $K$-Ramsey graph on $N$ vertices with $K=(\\log N)^{O(\\log \\log \\log N)}$. We also obtain a seeded non-malleable $9$-source extractor with optimal seed length, which in turn gives a $10$-source extractor for min-entropy $O(\\log n)$. Previously the best known extractor for such min-entropy requires $O(\\log \\log n)$ sources \\cite{CohL16}. Independent of our work, Cohen \\cite{Cohen16} obtained similar results to (1) and the two-source extractor, except the dependence on $\\epsilon$ is $\\log(1/\\epsilon)(\\log \\log (1/\\epsilon))^{O(1)}$ and the two-source extractor requires min-entropy $\\log n (\\log \\log n)^{O(1)}$.