Cryptology ePrint Archive: Report 2020/157

Multi-Source Non-Malleable Extractors and Applications

Vipul Goyal and Akshayaram Srinivasan and Chenzhi Zhu

Abstract: We introduce a natural generalization of two-source non-malleable extractors (Cheragachi and Guruswami, TCC 2014) called as \textit{multi-source non-malleable extractors}. Multi-source non-malleable extractors are special independent source extractors which satisfy an additional non-malleability 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 several applications. More specifically, we obtain the following results: \begin​{itemize} \item For any $s \geq 2$, we give a construction of a $s$-source non-malleable extractor for min-entropy $\Omega(n)$ and error $2^{-n^{\Omega(1)}}$ against {\it cover-free tampering family}. Roughly, cover-free tampering requires that for every source, there exists another source that is not tampered together with this source. Cover-free tampering is a strict superset of many natural tampering function families such as individual tampering and disjoint tampering functions (where $[s]$ is partitioned into several sets and each set is tampered independently). \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 non-malleable code secure against cover-free tampering family (via a generalization of the result by Cheragachi and Guruswami). \item We show that a modification of our construction of multi-source non-malleable extractors gives a $t$-out-of-$n$ non-malleable secret sharing scheme (Goyal and Kumar, STOC 2018) against $t$-cover-free tampering. Informally, $t$-cover-free tampering requires that every share is tampered together with at most $t-2$ other shares and includes disjoint tampering as a special case. This is the first construction of $t$-out-of-$n$ non-malleable secret sharing for every $t,n$ with security against a strict super class of disjoint tampering. \item We show that a stronger notion of $s$-source non-malleable extractor that is multi-tamperable 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 multi-tamperable, 2-source non-malleable extractors provided in our work, we get a network extractor protocol for min-entropy $\Omega(n)$ that tolerates an {\it optimum} number ($t = p-2$) 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}

Category / Keywords: foundations /

Date: received 11 Feb 2020, last revised 13 Feb 2020

Contact author: akshayaram at berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20200213:135003 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]