Paper 2016/340

Non-Malleable 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 non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami \cite{CG14b}; and \emph{non-malleable 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 non-malleable codes etc, and often have unexpected connections to their non-tampered analogues \cite{Li12b} \cite{CZ15}. %For example, seeded non-malleable extractors are closely related to privacy amplification with an active adversary, non-malleable codes are related to non-malleable secret sharing, and seedless non-malleable extractors provide a universal way to construct explicit non-malleable codes. However, the known constructions are far behind their non-tampered counterparts. Indeed, the best known seeded non-malleable extractor requires min-entropy rate at least $0.49$ \cite{Li12b}; while explicit constructions of non-malleable two-source extractors were not known even if both sources have full min-entropy, 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 non-malleable extractor for min-entropy $k \geq \log^2 n$. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result in \cite{Li15b}. In fact, we construct more general seeded non-malleable extractors (that can handle multiple adversaries) which were used in the recent construction of explicit two-source extractors for polylogarithmic min-entropy \cite{CZ15}. \item We construct the first explicit non-malleable two-source extractor for min-entropy $k \geq n-n^{\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 non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. For this, we construct the first explicit non-malleable two-source extractor with tampering degree $t$ up to $n^{\Omega(1)}$. %which works for min-entropy $k \geq n-n^{\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 non-malleable 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{one-many} and \emph{many-many} non-malleable codes. This provides a stronger information theoretic analogue of a primitive known as continuous non-malleable 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 non-malleable commitments}.

Note: Full version