Paper 2018/353
NonMalleable Extractors and NonMalleable Codes: Partially Optimal Constructions
Xin Li
Abstract
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 several seemingly different topics. These include seeded nonmalleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey graphs), and nonmalleable codes in the split state model. Previously, the best constructions are given in [Li17]: seeded nonmalleable extractors with seed length and entropy requirement $O(\log n+\log(1/\epsilon)\log \log (1/\epsilon))$ for error $\epsilon$; tworound 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; twosource extractors for entropy $O(\log n \log \log n)$; and nonmalleable codes in the $2$split state model with rate $\Omega(1/\log n)$. However, in all cases there is still a gap to optimum and the motivation to close this gap remains strong. In this paper, we introduce a set of new techniques to further push the frontier in the above questions. Our techniques lead to improvements in all of the above questions, and in several cases partially optimal constructions. This is in contrast to all previous work, which only obtain close to optimal constructions. Specifically, we obtain: 1. A seeded nonmalleable 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 [GurS17]; 2. A tworound privacy amplification protocol with optimal entropy loss for security parameter up to $\Omega(k)$, which solves the privacy amplification problem completely; 3. A twosource 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})}$; and 4. The first explicit nonmalleable code in the $2$split state model with constant rate, which has been a major goal in the study of nonmalleable codes for quite some time. One small caveat is that the error of this code is only (an arbitrarily small) constant, but we can also achieve negligible error with rate $\Omega(\log \log \log n/\log \log n)$, which already improves the rate in [Li17] exponentially. We believe our new techniques can help to eventually obtain completely optimal constructions in the above questions, and may have applications in other settings.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 nonmalleable codeprivacy amplificationnonmalleable extractor
 Contact author(s)
 lixints @ cs jhu edu
 History
 20180418: received
 Short URL
 https://ia.cr/2018/353
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/353, author = {Xin Li}, title = {NonMalleable Extractors and NonMalleable Codes: Partially Optimal Constructions}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/353}, year = {2018}, url = {https://eprint.iacr.org/2018/353} }