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

Better short-seed extractors against quantum knowledge

Avraham Ben-Aroya, Amnon Ta‐Shma

Published Apr 21, 2010• 3 citations
OpenAlex

Abstract

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.

Related papers

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

arXiv:1004.3737•Apr 21, 2010•1 citation

Near-optimal extractors against quantum storage

Anindya De, Thomas Vidick

We show that Trevisan's extractor and its variants [22,19] are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length Θ(K-b), where K is the source's entropy and b the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length Θ((K-b)/Kγ) for any γ>0. In contrast, the previous best construction [21] could only extract (K/b)1/15 bits.

ACM Symposium on Theory of Computing (STOC)•Jun 5, 2010•26 citations

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.

cs.CCCross-listedarXiv:2610.37122•Oct 28, 2026•0 citations

Near-optimal extractors against quantum storage

Anindya De, Thomas Vidick

We show that Trevisan's extractor and its variants \cite{T99,RRV99} are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length $Θ(K-b)$, where $K$ is the source's entropy and $b$ the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length $Θ((K-b)/K^γ)$ for any $γ>0$. In contrast, the previous best construction \cite{TS09} could only extract $(K/b)^{1/15}$ bits. Some of our constructions have the additional advantage that every bit of the output is a function of only a polylogarithmic number of bits from the source, which is crucial for some cryptographic applications. Our argument is based on bounds for a generalization of quantum random access codes, which we call \emph{quantum functional access codes}. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in \cite{TS09}, which was the source of the multiplicative overhead.

arXiv:0911.4680•Nov 24, 2009•1 citation

Quantum-Proof Extractors: Optimal up to Constant Factors

Kai-Min Chung, Cohen, Gil, Thomas Vidick +1 more

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.

arXiv:1605.04194•May 13, 2016•1 citation

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

arXiv:2109.03097•Sep 7, 2021•5 citations
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 kkk, has logarithmic seed length, and outputs Ω(k)Ω(k)Ω(k) bits, provided that the quantum adversary has at most βkβkβ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)Ω(n)Ω(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(1-β) n(1−β)n, for any $β< \half$.
We show that Trevisan's extractor and its variants [22,19] are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length Θ(K-b), where K is the source's entropy and b the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length Θ((K-b)/Kγ) for any γ>0. In contrast, the previous best construction [21] could only extract (K/b)1/15 bits.
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 DDD, accuracy ε\varepsilonε and failure probability δ≤εδ\leq\varepsilonδ≤ε, our matrix sampler uses m+Oα(log⁡(D/δ))m+O_α(\log(D/δ))m+Oα​(log(D/δ)) random bits and Oα(ε−2−αlog⁡1+α(D/δ))O_α(\varepsilon^{-2-α}\log^{1+α}(D/δ))Oα​(ε−2−αlog1+α(D/δ)) samples, for any constant α>0α>0α>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 poly⁡D\operatorname{poly} DpolyD dependence in the number of samples by O(log⁡1−γD)O(\log^{1-γ} D)O(log1−γD). Under the same scale of sample size, we can remove their log⁡log⁡D\log\log DloglogD factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length n−Oα(a+log⁡(1/η))n-O_α(a+\log(1/η))n−Oα​(a+log(1/η)) and seed length at most (1+α)log⁡a+(2+α)log⁡(1/η)+Oα(1)(1+α)\log a+(2+α)\log(1/η)+O_α(1)(1+α)loga+(2+α)log(1/η)+Oα​(1) for nnn-bit sources with conditional min-entropy n−an-an−a and error ηηη. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as 2−Ω(n)2^{-Ω(n)}2−Ω(n), having optimal seed length O(log⁡(n/η))O(\log(n/η))O(log(n/η)) and output length Ω(n)Ω(n)Ω(n), improving previous constructions.
We show that Trevisan's extractor and its variants \cite{T99,RRV99} are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length Θ(K−b)Θ(K-b)Θ(K−b), where KKK is the source's entropy and bbb the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length Θ((K−b)/Kγ)Θ((K-b)/K^γ)Θ((K−b)/Kγ) for any γ>0γ>0γ>0. In contrast, the previous best construction \cite{TS09} could only extract (K/b)1/15(K/b)^{1/15}(K/b)1/15 bits. Some of our constructions have the additional advantage that every bit of the output is a function of only a polylogarithmic number of bits from the source, which is crucial for some cryptographic applications. Our argument is based on bounds for a generalization of quantum random access codes, which we call \emph{quantum functional access codes}. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in \cite{TS09}, which was the source of the multiplicative overhead.
We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence O(log⁡(n/ε))O(\log(n/\varepsilon))O(log(n/ε)) on the input length nnn and error ε\varepsilonε. Our extractors support any min-entropy k=Ω(log⁡n+log⁡1+α(1/ε))k=Ω(\log{n} + \log^{1+α}(1/\varepsilon))k=Ω(logn+log1+α(1/ε)) and extract m=(1−α)km=(1-α)km=(1−α)k bits that are ε\varepsilonε-close to uniform, for any desired constant α>0α> 0α>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.
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)).