Paper 2020/157
MultiSource NonMalleable Extractors and Applications
Vipul Goyal, Akshayaram Srinivasan, and Chenzhi Zhu
Abstract
We introduce a natural generalization of twosource nonmalleable extractors (Cheragachi and Guruswami, TCC 2014) called as \textit{multisource nonmalleable extractors}. Multisource nonmalleable extractors are special independent source extractors which satisfy an additional nonmalleability property. This property requires that the output of the extractor remains close to uniform even conditioned on its output generated by tampering {\it several sources together}. We formally define this primitive, give a construction that is secure against a wide class of tampering functions, and provide applications. More specifically, we obtain the following results: \begin{itemize} \item For any $s \geq 2$, we give an explicit construction of a $s$source nonmalleable extractor for minentropy $\Omega(n)$ and error $2^{n^{\Omega(1)}}$ in the {\it overlapping joint tampering model}. This means that each tampered source could depend on any strict subset of all the sources and the sets corresponding to each tampered source could be overlapping in a way that we define. Prior to our work, there were no known explicit constructions that were secure even against disjoint tampering (where the sets are required to be disjoint without any overlap). %Our extractor is preimage sampleable and hence, gives rise to nonmalleable codes against the same tampering family. % \item We show how to efficiently preimage sample given the output of (a variant of) our extractor and this immediately gives rise to a $s$state nonmalleable code secure in the overlapping joint tampering model (via a generalization of the result by Cheragachi and Guruswami). \item We adapt the techniques used in the above construction to give a $t$outof$n$ nonmalleable secret sharing scheme (Goyal and Kumar, STOC 2018) for any $t \leq n$ in the \emph{disjoint tampering model}. This is the first general construction of a threshold nonmalleable secret sharing (NMSS) scheme in the disjoint tampering model. All prior constructions had a restriction that the size of the tampered subsets could not be equal. \item We further adapt the techniques used in the above construction to give a $t$outof$n$ nonmalleable secret sharing scheme (Goyal and Kumar, STOC 2018) for any $t \leq n$ in the \emph{overlapping joint tampering model}. This is the first construction of a threshold NMSS in the overlapping joint tampering model. \item We show that a stronger notion of $s$source nonmalleable extractor that is multitamperable against disjoint tampering functions gives a single round network extractor protocol (Kalai et al., FOCS 2008) with attractive features. Plugging in with a new construction of multitamperable, 2source nonmalleable extractors provided in our work, we get a network extractor protocol for minentropy $\Omega(n)$ that tolerates an {\it optimum} number ($t = p2$) of faulty processors and extracts random bits for {\it every} honest processor. The prior network extractor protocols could only tolerate $t = \Omega(p)$ faulty processors and failed to extract uniform random bits for a fraction of the honest processors. \end{itemize}
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2021
 Contact author(s)
 akshayram1993 @ gmail com
 History
 20210305: last of 3 revisions
 20200213: received
 See all versions
 Short URL
 https://ia.cr/2020/157
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/157, author = {Vipul Goyal and Akshayaram Srinivasan and Chenzhi Zhu}, title = {MultiSource NonMalleable Extractors and Applications}, howpublished = {Cryptology ePrint Archive, Paper 2020/157}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/157}}, url = {https://eprint.iacr.org/2020/157} }