Paper 2016/340
NonMalleable Extractors and Codes, with their Many Tampered Extensions
Eshan Chattopadhyay, Vipul Goyal, and Xin Li
Abstract
Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are \emph{seeded nonmalleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless nonmalleable extractors}, introduced by Cheraghchi and Guruswami \cite{CG14b}; and \emph{nonmalleable codes}, introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10}. Besides being interesting on their own, they also have important applications in cryptography, e.g, privacy amplification with an active adversary, explicit nonmalleable codes etc, and often have unexpected connections to their nontampered analogues \cite{Li12b} \cite{CZ15}. %For example, seeded nonmalleable extractors are closely related to privacy amplification with an active adversary, nonmalleable codes are related to nonmalleable secret sharing, and seedless nonmalleable extractors provide a universal way to construct explicit nonmalleable codes. However, the known constructions are far behind their nontampered counterparts. Indeed, the best known seeded nonmalleable extractor requires minentropy rate at least $0.49$ \cite{Li12b}; while explicit constructions of nonmalleable twosource extractors were not known even if both sources have full minentropy, and was left as an open problem in \cite{CG14b}. In this paper we make progress towards solving the above problems and other related generalizations. Our contributions are as follows. \begin{itemize} \item We construct an explicit seeded nonmalleable extractor for minentropy $k \geq \log^2 n$. This dramatically improves all previous results and gives a simpler 2round privacy amplification protocol with optimal entropy loss, matching the best known result in \cite{Li15b}. In fact, we construct more general seeded nonmalleable extractors (that can handle multiple adversaries) which were used in the recent construction of explicit twosource extractors for polylogarithmic minentropy \cite{CZ15}. \item We construct the first explicit nonmalleable twosource extractor for minentropy $k \geq nn^{\Omega(1)}$, with output size $n^{\Omega(1)}$ and error $2^{n^{\Omega(1)}}$, thus resolving the open question in \cite{CG14b}. \item We motivate and initiate the study of two natural generalizations of seedless nonmalleable extractors and nonmalleable codes, where the sources or the codeword may be tampered many times. For this, we construct the first explicit nonmalleable twosource extractor with tampering degree $t$ up to $n^{\Omega(1)}$. %which works for minentropy $k \geq nn^{\Omega(1)}$, with output size $n^{\Omega(1)}$ and error $2^{n^{\Omega(1)}}$. By using the connection in \cite{CG14b} and providing efficient sampling algorithms, we obtain the first explicit nonmalleable codes with tampering degree $t$ up to $n^{\Omega(1)}$, relative rate $n^{\Omega(1)}/n$, and error $2^{n^{\Omega(1)}}$. We call these stronger notions \emph{onemany} and \emph{manymany} nonmalleable codes. This provides a stronger information theoretic analogue of a primitive known as continuous nonmalleable codes. \end{itemize} Our basic technique used in all of our constructions can be seen as inspired, in part, by the techniques previously used to construct \emph{cryptographic nonmalleable commitments}.
Note: Full version
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. MAJOR revision.STOC 2016
 Contact author(s)
 vipul goyal @ gmail com
 History
 20160330: received
 Short URL
 https://ia.cr/2016/340
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/340, author = {Eshan Chattopadhyay and Vipul Goyal and Xin Li}, title = {NonMalleable Extractors and Codes, with their Many Tampered Extensions}, howpublished = {Cryptology ePrint Archive, Paper 2016/340}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/340}}, url = {https://eprint.iacr.org/2016/340} }