Paper 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}
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- akshayaram @ berkeley edu
- History
- 2021-03-05: last of 3 revisions
- 2020-02-13: received
- See all versions
- Short URL
- https://ia.cr/2020/157
- License
-
CC BY