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

arXiv:0911.4680

Near-optimal extractors against quantum storage

Anindya De, Thomas Vidick

Published Nov 24, 2009• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0911.4680

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

Short Seed Extractors against Quantum Storage

Amnon Ta‐Shma

In this paper we show that a construction of Trevisan, solving the privacy amplification problem in the classical setting, also solves the problem when the adversary may keep quantum storage, thereby giving the first such construction with logarithmic seed length. The technique we use is a combination of Trevisan's approach of constructing an extractor from a black-box pseudorandom generator, together with locally list-decodable codes and previous work done on quantum random access codes.

arXiv:0808.1994•SIAM Journal on Computing•Jan 1, 2011•9 citations

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.

•Apr 21, 2010•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

Short seed extractors against quantum storage

Amnon Ta‐Shma

In the classical privacy amplification problem Alice and Bob share information that is only partially secret towards an eavesdropper Charlie. Their goal is to distill this information to a shorter string that is completely secret. The classical privacy amplification problem can be solved almost optimally using extractors. An interesting variant of the problem, where the eavesdropper Charlie is allowed to keep quantum information rather than just classical information, was introduced by Konig, Maurer and Renner. In this setting, the eavesdropper Charlie may entangle himself with the input (without changing it) and the only limitation Charlie has is that it may keep at most b qubits of storage. A natural question is whether there are classical extractors that are good even against quantum storage.Recent work has shown that some classical extractors miserably fail against quantum storage. At the same time, it was shown that some other classical extractors work well even against quantum storage, but all these extractors had a large seed length that was either as large as the extractor output, or as large as the quantum storage available to the eavesdropper.In this paper we show that a modified version of Trevisan's extractor is good even against quantum storage, thereby giving the first such construction with logarithmic seed length. The technique we use is a combination of Trevisan's approach of constructing an extractor from a black-box pseudorandom generator, together with locally list-decodable codes and previous work done on quantum random access codes.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•25 citations

The Bounded-Storage Model in the Presence of a Quantum Adversary

Robert König, Barbara M. Terhal

An extractor is a function that is used to extract randomness. Given an imperfect random source X and a uniform seed Y, the output E(X,Y) is close to uniform. We study properties of such functions in the presence of prior quantum information about X, with a particular focus on cryptographic applications. We prove that certain extractors are suitable for key expansion in the bounded-storage model where the adversary has a limited amount of quantum memory. For extractors with one-bit output we show that the extracted bit is essentially equally secure as in the case where the adversary has classical resources. We prove the security of certain constructions that output multiple bits in the bounded-storage model.

arXiv:quant-ph/0608101•IEEE Transactions on Information Theory•Jan 29, 2008•75 citations
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 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 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 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.
In the classical privacy amplification problem Alice and Bob share information that is only partially secret towards an eavesdropper Charlie. Their goal is to distill this information to a shorter string that is completely secret. The classical privacy amplification problem can be solved almost optimally using extractors. An interesting variant of the problem, where the eavesdropper Charlie is allowed to keep quantum information rather than just classical information, was introduced by Konig, Maurer and Renner. In this setting, the eavesdropper Charlie may entangle himself with the input (without changing it) and the only limitation Charlie has is that it may keep at most b qubits of storage. A natural question is whether there are classical extractors that are good even against quantum storage.Recent work has shown that some classical extractors miserably fail against quantum storage. At the same time, it was shown that some other classical extractors work well even against quantum storage, but all these extractors had a large seed length that was either as large as the extractor output, or as large as the quantum storage available to the eavesdropper.In this paper we show that a modified version of Trevisan's extractor is good even against quantum storage, thereby giving the first such construction with logarithmic seed length. The technique we use is a combination of Trevisan's approach of constructing an extractor from a black-box pseudorandom generator, together with locally list-decodable codes and previous work done on quantum random access codes.
An extractor is a function that is used to extract randomness. Given an imperfect random source X and a uniform seed Y, the output E(X,Y) is close to uniform. We study properties of such functions in the presence of prior quantum information about X, with a particular focus on cryptographic applications. We prove that certain extractors are suitable for key expansion in the bounded-storage model where the adversary has a limited amount of quantum memory. For extractors with one-bit output we show that the extracted bit is essentially equally secure as in the case where the adversary has classical resources. We prove the security of certain constructions that output multiple bits in the bounded-storage model.