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

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•29 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•3 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

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•7 citations

Trevisan's extractor in the presence of quantum side information (Mathematical Foundations and Applications of Computer Science and Algorithms)

Anindya De, Christopher Portmann, Thomas Vidick +1 more

Randomness extraction involves the processing of purely classical information and is therefore usually studied in the framework of classical probability theory.However, such a classical treatment is generally too restrictive for applications, where side information about the values taken by classical random variables may be represented by the state of a quantum system.This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices.Here, we show that the well known construction paradigm for extractors proposed by hevisan is sound in the presence of quantum side information.We exploit the modularity of this paradigm to give several concrete extractor construc- tions, which.e.g, extract all the conditional (smooth) min-entropy of the source using a seed of length poly-logarithmic in the input, or only require the seed to be weakly random.

数理解析研究所講究録•Jun 1, 2011•0 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 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 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 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 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)).
Randomness extraction involves the processing of purely classical information and is therefore usually studied in the framework of classical probability theory.However, such a classical treatment is generally too restrictive for applications, where side information about the values taken by classical random variables may be represented by the state of a quantum system.This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices.Here, we show that the well known construction paradigm for extractors proposed by hevisan is sound in the presence of quantum side information.We exploit the modularity of this paradigm to give several concrete extractor construc- tions, which.e.g, extract all the conditional (smooth) min-entropy of the source using a seed of length poly-logarithmic in the input, or only require the seed to be weakly random.