In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor dramatically strengthens the notion of a strong extractor. A strong extractor takes two inputs, a weakly-random x and a uniformly random seed y, and outputs a string which appears uniform, even given y. For a non-malleable extractor nmExt, the output nmExt(x,y) should appear uniform given y as well as nmExt(x,A(y)), where A is an arbitrary function with A(y) not equal to y. We show that an extractor introduced by Chor and Goldreich is non-malleable when the entropy rate is above half. It outputs a linear number of bits when the entropy rate is 1/2 + alpha, for any alpha>0. Previously, no nontrivial parameters were known for any non-malleable extractor. To achieve a polynomial running time when outputting many bits, we rely on a widely-believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves a character sum estimate, which may be of independent interest. Using our non-malleable extractor, we obtain protocols for "privacy amplification": key agreement between two parties who share a weakly-random secret. Our protocols work in the presence of an active adversary with unlimited computational power, and have asymptotically optimal entropy loss. When the secret has entropy rate greater than 1/2, the protocol follows from a result of Dodis and Wichs, and takes two rounds. When the secret has entropy rate delta for any constant delta>0, our new protocol takes a constant (polynomial in 1/delta) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor dramatically strengthens the notion of a strong extractor. A strong extractor takes two inputs, a weakly-random x and a uniformly random seed y, and outputs a string which appears uniform, even given y. For a non-malleable extractor nmExt, the output nmExt(x,y) should appear uniform given y as well as nmExt(x,A(y)), where A is an arbitrary function with A(y) not equal to y. We show that an extractor introduced by Chor and Goldreich is non-malleable when the entropy rate is above half. It outputs a linear number of bits when the entropy rate is 1/2 + alpha, for any alpha>0. Previously, no nontrivial parameters were known for any non-malleable extractor. To achieve a polynomial running time when outputting many bits, we rely on a widely-believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves a character sum estimate, which may be of independent interest. Using our non-malleable extractor, we obtain protocols for "privacy amplification": key agreement between two parties who share a weakly-random secret. Our protocols work in the presence of an active adversary with unlimited computational power, and have asymptotically optimal entropy loss. When the secret has entropy rate greater than 1/2, the protocol follows from a result of Dodis and Wichs, and takes two rounds. When the secret has entropy rate delta for any constant delta>0, our new protocol takes a constant (polynomial in 1/delta) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.

arXiv:1102.5415Feb 26, 20110 citations

Privacy Amplification and Nonmalleable Extractors Via Character Sums

Yevgeniy Dodis, Xin Li, Trevor D. Wooley +1 more

In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a nonmalleable extractor. A nonmalleable extractor dramatically strengthens the notion of a strong extractor. A strong extractor takes two inputs, a weakly random $x$ and a uniformly random seed $y$ , and outputs a string which appears uniform, even given $y$ . For a nonmalleable extractor ${\mathsf{nmExt}}$ , the output ${\mathsf{nmExt}}(x,y)$ should appear uniform given $y$ as well as ${\mathsf{nmExt}}(x,{\mathcal A}(y))$ , where ${\mathcal A}$ is an arbitrary function with ${\mathcal A}(y) \neq y$ . We show that an extractor introduced by Chor and Goldreich is nonmalleable when the entropy rate (the ratio between the entropy and the length of the weakly random string) is above half. It outputs a linear number of bits when the entropy rate is $1/2 + \alpha$ for any $\alpha>0$ . Previously, no explicit construction was known for any entropy rate less than 1. To achieve a polynomial running time when outputting more than one bit, we rely on a widely believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves character sum estimates, which may be of independent interest. Using our nonmalleable extractor, we obtain protocols for “privacy amplification": key agreement between two parties who share a weakly random secret. Our protocols work in the presence of an active adversary with unlimited computational power and have asymptotically optimal entropy loss. When the secret has entropy rate greater than $1/2$ , the protocol follows from a result of Dodis and Wichs and takes two (or three, for strongest security guarantees) rounds. When the secret has entropy rate $\delta$ for any constant $\delta>0$ , our new protocol takes a constant (polynomial in $1/\delta$ ) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a nonmalleable extractor. A nonmalleable extractor dramatically strengthens the notion of a strong extractor. A strong extractor takes two inputs, a weakly random $x$ and a uniformly random seed $y$, and outputs a string which appears uniform, even given $y$. For a nonmalleable extractor ${\mathsf{nmExt}}$, the output ${\mathsf{nmExt}}(x,y)$ should appear uniform given $y$ as well as ${\mathsf{nmExt}}(x,{\mathcal A}(y))$, where ${\mathcal A}$ is an arbitrary function with ${\mathcal A}(y) \neq y$. We show that an extractor introduced by Chor and Goldreich is nonmalleable when the entropy rate (the ratio between the entropy and the length of the weakly random string) is above half. It outputs a linear number of bits when the entropy rate is $1/2 + \alpha$ for any $\alpha>0$. Previously, no explicit construction was known for any entropy rate less than 1. To achieve a polynomial running time when outputting more than one bit, we rely on a widely believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves character sum estimates, which may be of independent interest. Using our nonmalleable extractor, we obtain protocols for “privacy amplification": key agreement between two parties who share a weakly random secret. Our protocols work in the presence of an active adversary with unlimited computational power and have asymptotically optimal entropy loss. When the secret has entropy rate greater than $1/2$, the protocol follows from a result of Dodis and Wichs and takes two (or three, for strongest security guarantees) rounds. When the secret has entropy rate $\delta$ for any constant $\delta>0$, our new protocol takes a constant (polynomial in $1/\delta$) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.

SIAM Journal on ComputingJan 1, 201426 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)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 complexityJan 1, 20110 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.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 ComputingJan 1, 201415 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].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.1045Annual Symposium on Foundations of Computer ScienceOct 1, 201246 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.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.00557Oct 2, 20172 citations

x

and a uniformly random seed

y

, and outputs a string which appears uniform, even given

y

. For a nonmalleable extractor

{\mathsf{nmExt}}

, the output

{\mathsf{nmExt}}(x,y)

should appear uniform given

y

as well as

{\mathsf{nmExt}}(x,{\mathcal A}(y))

, where

{\mathcal A}

is an arbitrary function with

{\mathcal A}(y) \neq y

. We show that an extractor introduced by Chor and Goldreich is nonmalleable when the entropy rate (the ratio between the entropy and the length of the weakly random string) is above half. It outputs a linear number of bits when the entropy rate is

1/2 + \alpha

for any

\alpha>0

. Previously, no explicit construction was known for any entropy rate less than 1. To achieve a polynomial running time when outputting more than one bit, we rely on a widely believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves character sum estimates, which may be of independent interest. Using our nonmalleable extractor, we obtain protocols for “privacy amplification": key agreement between two parties who share a weakly random secret. Our protocols work in the presence of an active adversary with unlimited computational power and have asymptotically optimal entropy loss. When the secret has entropy rate greater than

1/2

, the protocol follows from a result of Dodis and Wichs and takes two (or three, for strongest security guarantees) rounds. When the secret has entropy rate

\delta

for any constant

\delta>0

, our new protocol takes a constant (polynomial in

1/\delta

) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.

\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.

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.