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), 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.
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 $β< \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 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
ε and failure probability
δ≤ε, our matrix sampler uses
m+Oα(log(D/δ)) random bits and
Oα(ε−2−αlog1+α(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
polyD dependence in the number of samples by
O(log1−γD). Under the same scale of sample size, we can remove their
loglogD 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+α)loga+(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.