The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about

1/2

, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to

1

and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have

0.8

entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate

\frac 1 2

, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.

DOI: 10.48550/arxiv.2111.04157

Related papers

Extractors: Low Entropy Requirements Colliding With Non-Malleability

Eldon Chung, Maciej Obremski, Divesh Aggarwal

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about $1/2$ , the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to $1$ and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have $0.8$ entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate $\frac 1 2$ , which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to $1$ and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have $0.8$ entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate $\frac 1 2$, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.

Electronic colloquium on computational complexityJan 1, 20212 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)}}$ .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.00107May 1, 20153 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

Quantum secure non-malleable-extractors

Naresh Goud Boddu, Rahul Jain, Upendra Kapshikar

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)}$ ).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)}$).

arXiv:2109.03097Sep 7, 20215 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

Design Extractors, Non-Malleable Condensers and Privacy Amplification.

Xin Li

We introduce a new combinatorial object, called a design extractor, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications. Improving the output length of known non-malleable extractors. Non-malleable extractors were introduced in [DW09] to study the problem of privacy amplification with an active adversary. Currently, only two explicit constructions are known [DLWZ11, CRS11]. Both constructions work for n bit sources with min-entropy k > n/2. However, in both constructions the output length is smaller than the seed length, while the probabilistic method shows that to achieve error e, one can use O(log n+log (1/e)) bits to extract up to k/2 output bits. In this paper, we use our design extractor to give an explicit non-malleable extractor for min-entropy k > n/2, that has seed length O(log n+log (1/e)) and output length Ω(k). Non-malleable condensers. We introduce and define the notion of a non-malleable condenser. A non-malleable condenser is a generalization and relaxation of a non-malleable extractor. We show that similar as extractors and condensers, non-malleable condensers can be used to construct non-malleable extractors. We then show that our design extractor already gives a non-malleable condenser for min-entropy k > n/2, with error e and seed length O(log (1/e)). A new optimal protocol for privacy amplification. More surprisingly, we show that non-malleable condensers themselves give optimal privacy amplification protocols with an active adversary. In fact, the non-malleable condensers used in these protocols are much weaker compared to non-malleable extractors, in the sense that the entropy rate of the condenser's output does not need to increase at all. This suggests that one promising next step to achieve better privacy amplification protocols may be to construct non-malleable condensers for smaller min-entropy. As a by-product, we also obtain a new explicit 2-round privacy amplification protocol with optimal entropy loss and optimal communication complexity for min-entropy k>n/2, without using non-malleable extractors.We introduce a new combinatorial object, called a design extractor, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications. Improving the output length of known non-malleable extractors. Non-malleable extractors were introduced in [DW09] to study the problem of privacy amplification with an active adversary. Currently, only two explicit constructions are known [DLWZ11, CRS11]. Both constructions work for n bit sources with min-entropy k > n/2. However, in both constructions the output length is smaller than the seed length, while the probabilistic method shows that to achieve error e, one can use O(log n+log (1/e)) bits to extract up to k/2 output bits. In this paper, we use our design extractor to give an explicit non-malleable extractor for min-entropy k > n/2, that has seed length O(log n+log (1/e)) and output length Ω(k). Non-malleable condensers. We introduce and define the notion of a non-malleable condenser. A non-malleable condenser is a generalization and relaxation of a non-malleable extractor. We show that similar as extractors and condensers, non-malleable condensers can be used to construct non-malleable extractors. We then show that our design extractor already gives a non-malleable condenser for min-entropy k > n/2, with error e and seed length O(log (1/e)). A new optimal protocol for privacy amplification. More surprisingly, we show that non-malleable condensers themselves give optimal privacy amplification protocols with an active adversary. In fact, the non-malleable condensers used in these protocols are much weaker compared to non-malleable extractors, in the sense that the entropy rate of the condenser's output does not need to increase at all. This suggests that one promising next step to achieve better privacy amplification protocols may be to construct non-malleable condensers for smaller min-entropy. As a by-product, we also obtain a new explicit 2-round privacy amplification protocol with optimal entropy loss and optimal communication complexity for min-entropy k>n/2, without using non-malleable extractors.

Electronic colloquium on computational complexityJan 1, 20110 citations

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about

1/2

1

0.8

entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate

\frac 1 2

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about

1/2

1

0.8

entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate

\frac 1 2

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)}}

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)}

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