You are looking at a specific version 20200213:135003 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.