Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2109.03097

Quantum secure non-malleable-extractors

Naresh Goud Boddu, Rahul Jain, Upendra Kapshikar

Published Sep 7, 2021• 5 citations
arXivHTMLPDF

Abstract

We construct several explicit quantum secure non-malleable-extractors. All the quantum secure non-malleable-extractors we construct are based on the constructions by Chattopadhyay, Goyal and Li [2015] and Cohen [2015]. 1) We construct the first explicit quantum secure non-malleable-extractor for (source) min-entropy $k \geq \textsf{poly}\left(\log \left( \frac{n}ε \right)\right)$ ($n$ is the length of the source and $ε$ is the error parameter). Previously Aggarwal, Chung, Lin, and Vidick [2019] have shown that the inner-product based non-malleable-extractor proposed by Li [2012] is quantum secure, however it required linear (in $n$) min-entropy and seed length. Using the connection between non-malleable-extractors and privacy amplification (established first in the quantum setting by Cohen and Vidick [2017]), we get a $2$-round privacy amplification protocol that is secure against active quantum adversaries with communication $\textsf{poly}\left(\log \left( \frac{n}ε \right)\right)$, exponentially improving upon the linear communication required by the protocol due to [2019]. 2) We construct an explicit quantum secure $2$-source non-malleable-extractor for min-entropy $k \geq n- n^{Ω(1)}$, with an output of size $n^{Ω(1)}$ and error $2^{- n^{Ω(1)}}$. 3) We also study their natural extensions when the tampering of the inputs is performed $t$-times. We construct explicit quantum secure $t$-non-malleable-extractors for both seeded ($t=d^{Ω(1)}$) as well as $2$-source case ($t=n^{Ω(1)}$).

DOI
10.48550/arxiv.2109.03097

Related papers

Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols

Eshan Chattopadhyay, Xin Li

We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors, 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter, 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic). For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li, and by Cohen all require seed length and min-entropy with quadratic loss in parameters. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve two rounds of communication and optimal entropy loss was sub-optimal in the min-entropy of the source. In this paper we give an explicit non-malleable extractor that works for nearly optimal seed length and min-entropy, and yields a two-round privacy amplification protocol with optimal entropy loss for almost all ranges of the security parameter. For the third problem, we improve upon a very recent result by Cohen and Schulman and give an explicit extractor that uses an absolute constant number of sources, each with almost logarithmic min-entropy. The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced by Cohen, which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of Cohen and Schulman, and may be of independent interest.

arXiv:1603.05226•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•19 citations

Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Eshan Chattopadhyay, Vipul Goyal, Xin Li

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 seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. In this paper we make progress towards solving the above problems. Our contributions are as follows. (1) 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 [Li15b]. (2) We construct the first explicit non-malleable two-source extractor for min-entropy $k \geq n-n^{Ω(1)}$, with output size $n^{Ω(1)}$ and error $2^{-n^{Ω(1)}}$. (3) We 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. We construct the first explicit non-malleable two-source extractor with tampering degree $t$ up to $n^{Ω(1)}$, which works for min-entropy $k \geq n-n^{Ω(1)}$, with output size $n^{Ω(1)}$ and error $2^{-n^{Ω(1)}}$. We show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree $t$ up to $n^{Ω(1)}$, relative rate $n^{Ω(1)}/n$, and error $2^{-n^{Ω(1)}}$.

arXiv:1505.00107•May 1, 2015•3 citations

A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries

Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin +1 more

In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret $X$ in order to establish a shared private key $K$ by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries. In the case that the channel is not authenticated, Dodis and Wichs (STOC'09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor. We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS'12), and is able to extract from source of min-entropy rates larger than $1/2$. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, shown by Cohen and Vidick (unpublished), we obtain the first privacy amplification protocol secure against active quantum adversaries.

arXiv:1710.00557•Oct 2, 2017•2 citations

Non-malleable Extractors, Two-Source Extractors and Privacy Amplification

Xin Li

In [1], Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor is a much stronger version of a seeded extractor. Dodis and Wichs showed that such an object can be used to give optimal privacy amplification protocols with an active adversary. Previously, there are only two known constructions of nonmalleable extractors [2], [3]. Both constructions only work for (n, k)-sources with k >; n/2. Interestingly, both constructions are also two-source extractors. In this paper, we present a strong connection between nonmalleable extractors and two-source extractors. The first part of the connection shows that non-malleable extractors can be used to construct two-source extractors. This partially explains why previous constructions of non-malleable extractors only work for entropy rate >; 1/2, and why explicit non-malleable extractors for small min-entropy may be hard to get. The second part of the connection shows that certain two-source extractors can be used to construct non-malleable extractors. Using this connection, we obtain the first construction of non-malleable extractors for k; 0. This dramatically improves previous results and answers an open problem in [2].

arXiv:1112.1045•Annual Symposium on Foundations of Computer Science•Oct 1, 2012•46 citations

Non-Malleable Extractors for Entropy Rate <1/2

Xin Li

Dodis and Wichs [DW09] introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string x and a uniformly random seed y as the inputs, the non-malleable extractor nmExt has the property that nmExt(x, y) appears uniform even given y as well as nmExt(x,A(y)), for an arbitrary function A with A(y) 6= y. Dodis and Wichs showed that such an object can be used to give optimal privacy amplification protocols with an active adversary. Previously, there are only two known explicit constructions of non-malleable extractors [DLWZ11, CRS11]. Both constructions only work for (n, k)-sources with k > n/2 and thus they also only achieve optimal privacy amplification protocols for k > n/2. In this paper, we give the first construction of non-malleable extractors for k 0, and a conditional construction that can potentially achieve k = αn for any constant α > 0. Using our non-malleable extractor, we also obtain the first optimal privacy amplification protocol for min-entropy k = (1/2 − δ)n, with an active adversary. Our constructions mainly use the bilinear property of the inner product function, and involve appropriate encodings of the seed y as well as ideas from additive combinatorics. ∗Partially supported by NSF Grants CCF-0634811, CCF-0916160, THECB ARP Grant 003658-0113-2007, and a Simons postdoctoral fellowship. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 166 (2011)

Electronic colloquium on computational complexity•Jan 1, 2011•0 citations

Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification

Gil Cohen, Ran Raz, Gil Segev

Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function $\mathsf{nmExt}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$ that takes two inputs---a weak source $W$ and a uniform (independent) seed $S$---and outputs a string $\mathsf{nmExt}(W,S)$ that is nearly uniform given the seed $S$ as well as the value $\mathsf{nmExt}(W,S')$ for any seed $S'\neq S$ that may be determined as an arbitrary function of $S$. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant and outputs up to a linear number of bits but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols), its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a nonmalleable extractor with short seeds. For any integers $n$ and $d$ such that $2.01\cdot\log n\leq d\leq n$, we present an explicit construction of a nonmalleable extractor $\mathsf{nmExt}\colon\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$, with $m=\Omega(d)$ and error exponentially small in $m$. The extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output $\mathsf{nmExt}(W,S)$ is nearly uniform given the seed $S$ as well as the values $\mathsf{nmExt}(W,S_1),\dots,\mathsf{nmExt}(W,S_t)$ for several seeds $S_1,\dots,S_t$ that may be determined as an arbitrary function of $S$, as long as $S\notin\{S_1,\dots,S_t\}$. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate $1/2+\delta$ with asymptotically optimal entropy loss and polylogarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs, whose entropy loss is not asymptotically optimal, and the protocol of Dodis et al., whose communication complexity is linear.

SIAM Journal on Computing•Jan 1, 2014•15 citations
We construct several explicit quantum secure non-malleable-extractors. All the quantum secure non-malleable-extractors we construct are based on the constructions by Chattopadhyay, Goyal and Li [2015] and Cohen [2015]. 1) We construct the first explicit quantum secure non-malleable-extractor for (source) min-entropy k≥poly(log⁡(nε))k \geq \textsf{poly}\left(\log \left( \frac{n}ε \right)\right)k≥poly(log(εn​)) (nnn is the length of the source and εεε is the error parameter). Previously Aggarwal, Chung, Lin, and Vidick [2019] have shown that the inner-product based non-malleable-extractor proposed by Li [2012] is quantum secure, however it required linear (in nnn) min-entropy and seed length. Using the connection between non-malleable-extractors and privacy amplification (established first in the quantum setting by Cohen and Vidick [2017]), we get a 222-round privacy amplification protocol that is secure against active quantum adversaries with communication poly(log⁡(nε))\textsf{poly}\left(\log \left( \frac{n}ε \right)\right)poly(log(εn​)), exponentially improving upon the linear communication required by the protocol due to [2019]. 2) We construct an explicit quantum secure 222-source non-malleable-extractor for min-entropy k≥n−nΩ(1)k \geq n- n^{Ω(1)}k≥n−nΩ(1), with an output of size nΩ(1)n^{Ω(1)}nΩ(1) and error 2−nΩ(1)2^{- n^{Ω(1)}}2−nΩ(1). 3) We also study their natural extensions when the tampering of the inputs is performed ttt-times. We construct explicit quantum secure ttt-non-malleable-extractors for both seeded (t=dΩ(1)t=d^{Ω(1)}t=dΩ(1)) as well as 222-source case (t=nΩ(1)t=n^{Ω(1)}t=nΩ(1)).
We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors, 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter, 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic). For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li, and by Cohen all require seed length and min-entropy with quadratic loss in parameters. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve two rounds of communication and optimal entropy loss was sub-optimal in the min-entropy of the source. In this paper we give an explicit non-malleable extractor that works for nearly optimal seed length and min-entropy, and yields a two-round privacy amplification protocol with optimal entropy loss for almost all ranges of the security parameter. For the third problem, we improve upon a very recent result by Cohen and Schulman and give an explicit extractor that uses an absolute constant number of sources, each with almost logarithmic min-entropy. The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced by Cohen, which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of Cohen and Schulman, and may be of independent interest.
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 seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. In this paper we make progress towards solving the above problems. Our contributions are as follows. (1) We construct an explicit seeded non-malleable extractor for min-entropy k≥log⁡2nk \geq \log^2 nk≥log2n. 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 [Li15b]. (2) We construct the first explicit non-malleable two-source extractor for min-entropy k≥n−nΩ(1)k \geq n-n^{Ω(1)}k≥n−nΩ(1), with output size nΩ(1)n^{Ω(1)}nΩ(1) and error 2−nΩ(1)2^{-n^{Ω(1)}}2−nΩ(1). (3) We 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. We construct the first explicit non-malleable two-source extractor with tampering degree ttt up to nΩ(1)n^{Ω(1)}nΩ(1), which works for min-entropy k≥n−nΩ(1)k \geq n-n^{Ω(1)}k≥n−nΩ(1), with output size nΩ(1)n^{Ω(1)}nΩ(1) and error 2−nΩ(1)2^{-n^{Ω(1)}}2−nΩ(1). We show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree ttt up to nΩ(1)n^{Ω(1)}nΩ(1), relative rate nΩ(1)/nn^{Ω(1)}/nnΩ(1)/n, and error 2−nΩ(1)2^{-n^{Ω(1)}}2−nΩ(1).
In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret XXX in order to establish a shared private key KKK by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries. In the case that the channel is not authenticated, Dodis and Wichs (STOC'09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor. We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS'12), and is able to extract from source of min-entropy rates larger than 1/21/21/2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, shown by Cohen and Vidick (unpublished), we obtain the first privacy amplification protocol secure against active quantum adversaries.
In [1], Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor is a much stronger version of a seeded extractor. Dodis and Wichs showed that such an object can be used to give optimal privacy amplification protocols with an active adversary. Previously, there are only two known constructions of nonmalleable extractors [2], [3]. Both constructions only work for (n, k)-sources with k >; n/2. Interestingly, both constructions are also two-source extractors. In this paper, we present a strong connection between nonmalleable extractors and two-source extractors. The first part of the connection shows that non-malleable extractors can be used to construct two-source extractors. This partially explains why previous constructions of non-malleable extractors only work for entropy rate >; 1/2, and why explicit non-malleable extractors for small min-entropy may be hard to get. The second part of the connection shows that certain two-source extractors can be used to construct non-malleable extractors. Using this connection, we obtain the first construction of non-malleable extractors for k; 0. This dramatically improves previous results and answers an open problem in [2].
Dodis and Wichs [DW09] introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string x and a uniformly random seed y as the inputs, the non-malleable extractor nmExt has the property that nmExt(x, y) appears uniform even given y as well as nmExt(x,A(y)), for an arbitrary function A with A(y) 6= y. Dodis and Wichs showed that such an object can be used to give optimal privacy amplification protocols with an active adversary. Previously, there are only two known explicit constructions of non-malleable extractors [DLWZ11, CRS11]. Both constructions only work for (n, k)-sources with k > n/2 and thus they also only achieve optimal privacy amplification protocols for k > n/2. In this paper, we give the first construction of non-malleable extractors for k 0, and a conditional construction that can potentially achieve k = αn for any constant α > 0. Using our non-malleable extractor, we also obtain the first optimal privacy amplification protocol for min-entropy k = (1/2 − δ)n, with an active adversary. Our constructions mainly use the bilinear property of the inner product function, and involve appropriate encodings of the seed y as well as ideas from additive combinatorics. ∗Partially supported by NSF Grants CCF-0634811, CCF-0916160, THECB ARP Grant 003658-0113-2007, and a Simons postdoctoral fellowship. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 166 (2011)
Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function nmExt:{0,1}n×{0,1}d→{0,1}m\mathsf{nmExt}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^mnmExt:{0,1}n×{0,1}d→{0,1}m that takes two inputs---a weak source WWW and a uniform (independent) seed SSS---and outputs a string nmExt(W,S)\mathsf{nmExt}(W,S)nmExt(W,S) that is nearly uniform given the seed SSS as well as the value nmExt(W,S′)\mathsf{nmExt}(W,S')nmExt(W,S′) for any seed S′≠SS'\neq SS′=S that may be determined as an arbitrary function of SSS. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate 1/2+δ1/2+\delta1/2+δ, where δ>0\delta>0δ>0 is an arbitrary constant and outputs up to a linear number of bits but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols), its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a nonmalleable extractor with short seeds. For any integers nnn and ddd such that 2.01⋅log⁡n≤d≤n2.01\cdot\log n\leq d\leq n2.01⋅logn≤d≤n, we present an explicit construction of a nonmalleable extractor nmExt ⁣:{0,1}n×{0,1}d→{0,1}m\mathsf{nmExt}\colon\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^mnmExt:{0,1}n×{0,1}d→{0,1}m, with m=Ω(d)m=\Omega(d)m=Ω(d) and error exponentially small in mmm. The extractor works for any weak source with min-entropy rate 1/2+δ1/2+\delta1/2+δ, where δ>0\delta>0δ>0 is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output nmExt(W,S)\mathsf{nmExt}(W,S)nmExt(W,S) is nearly uniform given the seed SSS as well as the values nmExt(W,S1),…,nmExt(W,St)\mathsf{nmExt}(W,S_1),\dots,\mathsf{nmExt}(W,S_t)nmExt(W,S1​),…,nmExt(W,St​) for several seeds S1,…,StS_1,\dots,S_tS1​,…,St​ that may be determined as an arbitrary function of SSS, as long as S∉{S1,…,St}S\notin\{S_1,\dots,S_t\}S∈/{S1​,…,St​}. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate 1/2+δ1/2+\delta1/2+δ with asymptotically optimal entropy loss and polylogarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs, whose entropy loss is not asymptotically optimal, and the protocol of Dodis et al., whose communication complexity is linear.