arXiv:1605.04194

Quantum-Proof Extractors: Optimal up to Constant Factors

Kai-Min Chung, Cohen, Gil, Thomas Vidick, Xiaodi Wu

Published May 13, 2016• 1 citation

Abstract

We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence $O(\log(n/\varepsilon))$ on the input length $n$ and error $\varepsilon$. Our extractors support any min-entropy $k=Ω(\log{n} + \log^{1+α}(1/\varepsilon))$ and extract $m=(1-α)k$ bits that are $\varepsilon$-close to uniform, for any desired constant $α> 0$. Previous constructions had a quadratically worse seed length or were restricted to very large input min-entropy or very few output bits. Our result is based on a generic reduction showing that any strong classical condenser is automatically quantum-proof, with comparable parameters. The existence of such a reduction for extractors is a long-standing open question, here we give an affirmative answer for condensers. Once this reduction is established, to obtain our quantum-proof extractors one only needs to consider high entropy sources. We construct quantum-proof extractors with the desired parameters for such sources by extending a classical approach to extractor construction, based on the use of block-sources and sampling, to the quantum setting. Our extractors can be used to obtain improved protocols for device-independent randomness expansion and for privacy amplification.

DOI: 10.48550/arxiv.1605.04194

Related papers

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

Kuan Cheng, Ruiyang Wu

cs.CCCross-listedarXiv:2610.37122Oct 28, 20260 citations

Better short-seed quantum-proof extractors

Avraham Ben-Aroya, Amnon Ta‐Shma

arXiv:1004.3737Apr 21, 20101 citation

Better short-seed extractors against quantum knowledge

Avraham Ben-Aroya, Amnon Ta‐Shma

Apr 21, 20103 citations

Quantum secure non-malleable-extractors

Naresh Goud Boddu, Rahul Jain, Upendra Kapshikar

arXiv:2109.03097Sep 7, 20215 citations

High-rate and computationally-efficient seedless extractors for device-independent quantum cryptography

Simone Lin, Cameron Foreman, Lluis Masanes

quant-pharXiv:2605.31525Jun 1, 20260 citations

Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification

Gil Cohen, Ran Raz, Gil Segev

SIAM Journal on ComputingJan 1, 201415 citations

arXiv:1605.04194

Quantum-Proof Extractors: Optimal up to Constant Factors

Kai-Min Chung, Cohen, Gil, Thomas Vidick, Xiaodi Wu

Published May 13, 2016• 1 citation

arXiv HTML PDF

Abstract

We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence

O(\log(n/\varepsilon))

on the input length

n

and error

\varepsilon

. Our extractors support any min-entropy

k=Ω(\log{n} + \log^{1+α}(1/\varepsilon))

and extract

m=(1-α)k

bits that are

\varepsilon

-close to uniform, for any desired constant

α> 0

. Previous constructions had a quadratically worse seed length or were restricted to very large input min-entropy or very few output bits. Our result is based on a generic reduction showing that any strong classical condenser is automatically quantum-proof, with comparable parameters. The existence of such a reduction for extractors is a long-standing open question, here we give an affirmative answer for condensers. Once this reduction is established, to obtain our quantum-proof extractors one only needs to consider high entropy sources. We construct quantum-proof extractors with the desired parameters for such sources by extending a classical approach to extractor construction, based on the use of block-sources and sampling, to the quantum setting. Our extractors can be used to obtain improved protocols for device-independent randomness expansion and for privacy amplification.

DOI: 10.48550/arxiv.1605.04194

Related papers

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

Kuan Cheng, Ruiyang Wu

We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler--extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$ , accuracy $\varepsilon$ and failure probability $δ\leq\varepsilon$ , our matrix sampler uses $m+O_α(\log(D/δ))$ random bits and $O_α(\varepsilon^{-2-α}\log^{1+α}(D/δ))$ samples, for any constant $α>0$ . Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under the same optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1-γ} D)$ . Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$ -bit sources with conditional min-entropy $n-a$ and error $η$ . We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$ , having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$ , improving previous constructions.We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler--extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $δ\leq\varepsilon$, our matrix sampler uses $m+O_α(\log(D/δ))$ random bits and $O_α(\varepsilon^{-2-α}\log^{1+α}(D/δ))$ samples, for any constant $α>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under the same optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1-γ} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$, having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$, improving previous constructions.

cs.CCCross-listedarXiv:2610.37122Oct 28, 20260 citations

Better short-seed quantum-proof extractors

Avraham Ben-Aroya, Amnon Ta‐Shma

We construct a strong extractor against quantum storage that works for every min-entropy $k$ , has logarithmic seed length, and outputs $Ω(k)$ bits, provided that the quantum adversary has at most $βk$ qubits of memory, for any $β< \half$. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries when the source is close to uniform. We also obtain an improved construction of a strong quantum-proof extractor in the high min-entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts $Ω(n)$ bits from any source over $\B^n$, provided that the min-entropy of the source conditioned on the quantum adversary's state is at least $(1-β) n$ , for any $β< \half$.We construct a strong extractor against quantum storage that works for every min-entropy $k$, has logarithmic seed length, and outputs $Ω(k)$ bits, provided that the quantum adversary has at most $βk$ qubits of memory, for any $β< \half$. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries when the source is close to uniform. We also obtain an improved construction of a strong quantum-proof extractor in the high min-entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts $Ω(n)$ bits from any source over $\B^n$, provided that the min-entropy of the source conditioned on the quantum adversary's state is at least $(1-β) n$, for any $β< \half$.

arXiv:1004.3737Apr 21, 20101 citation

Better short-seed extractors against quantum knowledge

Avraham Ben-Aroya, Amnon Ta‐Shma

We construct a strong extractor against quantum storage that works for every min-entropy k, has logarithmic seed length, and outputs Ω(k) bits, provided that the quantum adversary has at most βk qubits of memory, for any β < 12 . Previous constructions required poly-logarithmic seed length to output such a fraction of the entropy and, in addition, required super-logarithmic seed length for small values of k. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries, when the source is close to uniform. We also obtain an improved construction of a strong extractor against quantum knowledge, in the high guessing entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts Ω(n) bits from any source over {0, 1}, provided that the guessing entropy of the source conditioned on the quantum adversary’s state is at least (1−β)n, for any β < 12 . Previous constructions required poly-logarithmic seed length to output Ω(n) bits from such sources.We construct a strong extractor against quantum storage that works for every min-entropy k, has logarithmic seed length, and outputs Ω(k) bits, provided that the quantum adversary has at most βk qubits of memory, for any β < 12 . Previous constructions required poly-logarithmic seed length to output such a fraction of the entropy and, in addition, required super-logarithmic seed length for small values of k. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries, when the source is close to uniform. We also obtain an improved construction of a strong extractor against quantum knowledge, in the high guessing entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts Ω(n) bits from any source over {0, 1}, provided that the guessing entropy of the source conditioned on the quantum adversary’s state is at least (1−β)n, for any β < 12 . Previous constructions required poly-logarithmic seed length to output Ω(n) bits from such sources.

Apr 21, 20103 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

High-rate and computationally-efficient seedless extractors for device-independent quantum cryptography

Simone Lin, Cameron Foreman, Lluis Masanes

Device-independent (DI) quantum cryptography provides secure cryptography with minimal trust in, or characterisation of, the used quantum devices. An essential component of DI protocols is the use of randomness extractors for privacy amplification, but these typically require an initial seed of randomness that introduces a potential vulnerability. To solve this problem, the security of seedless extractors was proven in Quantum 9, 1654 (2025). The core idea was to use the Bell violation of the raw data, rather than its min-entropy, as the extractor promise. However, the large fluctuations in the Bell inequality used required many rounds to precisely estimate the Bell violation, consuming substantial randomness and making the protocol very inefficient. In this work, we present a new proof technique based on a truncation method that allows the user to estimate the protocol parameters with an asymptotically vanishing fraction of rounds and, as a consequence, achieves the optimal rate of one key bit per singlet. Notably, we prove this result using seedless extractors that can be implemented efficiently.Device-independent (DI) quantum cryptography provides secure cryptography with minimal trust in, or characterisation of, the used quantum devices. An essential component of DI protocols is the use of randomness extractors for privacy amplification, but these typically require an initial seed of randomness that introduces a potential vulnerability. To solve this problem, the security of seedless extractors was proven in Quantum 9, 1654 (2025). The core idea was to use the Bell violation of the raw data, rather than its min-entropy, as the extractor promise. However, the large fluctuations in the Bell inequality used required many rounds to precisely estimate the Bell violation, consuming substantial randomness and making the protocol very inefficient. In this work, we present a new proof technique based on a truncation method that allows the user to estimate the protocol parameters with an asymptotically vanishing fraction of rounds and, as a consequence, achieves the optimal rate of one key bit per singlet. Notably, we prove this result using seedless extractors that can be implemented efficiently.

quant-pharXiv:2605.31525Jun 1, 20260 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

We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence

O(\log(n/\varepsilon))

on the input length

n

and error

\varepsilon

. Our extractors support any min-entropy

k=Ω(\log{n} + \log^{1+α}(1/\varepsilon))

and extract

m=(1-α)k

bits that are

\varepsilon

-close to uniform, for any desired constant

α> 0

D

, accuracy

\varepsilon

and failure probability

δ\leq\varepsilon

, our matrix sampler uses

m+O_α(\log(D/δ))

random bits and

O_α(\varepsilon^{-2-α}\log^{1+α}(D/δ))

samples, for any constant

α>0

. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under the same optimal random seed length, we can replace the

\operatorname{poly} D

dependence in the number of samples by

O(\log^{1-γ} D)

. Under the same scale of sample size, we can remove their

\log\log D

factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length

n-O_α(a+\log(1/η))

and seed length at most

(1+α)\log a+(2+α)\log(1/η)+O_α(1)

for

n

-bit sources with conditional min-entropy

n-a

and error

η

. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as

2^{-Ω(n)}

, having optimal seed length

O(\log(n/η))

and output length

Ω(n)

, improving previous constructions.

We construct a strong extractor against quantum storage that works for every min-entropy

k

, has logarithmic seed length, and outputs

Ω(k)

bits, provided that the quantum adversary has at most

βk

qubits of memory, for any $β< \half$. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries when the source is close to uniform. We also obtain an improved construction of a strong quantum-proof extractor in the high min-entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts

Ω(n)

bits from any source over $\B^n$, provided that the min-entropy of the source conditioned on the quantum adversary's state is at least

(1-β) n

, for any $β< \half$.

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.