2016/07/30 by Li, Xin
#Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1608.00127
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 ε and seed length d=O(log n)+O(log(1/ε)log log (1/ε)), that supports min-entropy k=Ω(d) and outputs Ω(k) bits. Combined with the protocol in \citeDW09, 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 Ω(k/log k). (2) An explicit non-malleable two-source extractor for min-entropy k ≥ (1-γ)n, some constant γ>0, that outputs Ω(k) bits with error 2-Ω(n/log n). Combined with the connection in \citeCG14b this gives a non-malleable code in the two-split-state model with relative rate Ω(1/log n). This exponentially improves previous constructions, all of which only achieve rate n-Ω(1).\footnoteThe work of Aggarwal et. al \citeADKO15 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 \citeCohL16. Independent of our work, Cohen \citeCohen16 obtained similar results to (1) and the two-source extractor, except the dependence on ε is log(1/ε)(log log (1/ε))O(1) and the two-source extractor requires min-entropy log n (log log n)O(1).