Randomness extractors are an important building block for classical and quantum cryptography. However, for many applications it is crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood and we would like to argue that in the same way as Bell inequalities (multiprover games) and communication complexity, the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraints. We then construct a semidefinite programming (SDP) relaxation for this program that is tight for some extractor constructions. Moreover, we show that this SDP relaxation is even sufficient to certify quantum-proof extractors. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. Finally, we analyze the limitations of this SDP relaxation.Randomness extractors are an important building block for classical and quantum cryptography. However, for many applications it is crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood and we would like to argue that in the same way as Bell inequalities (multiprover games) and communication complexity, the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraints. We then construct a semidefinite programming (SDP) relaxation for this program that is tight for some extractor constructions. Moreover, we show that this SDP relaxation is even sufficient to certify quantum-proof extractors. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. Finally, we analyze the limitations of this SDP relaxation.

Leibniz international proceedings in informaticsJan 1, 20152 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.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

A modular framework for randomness extraction based on Trevisan's construction

Wolfgang Mauerer, Christopher Portmann, Volkher B. Scholz

Informally, an extractor delivers perfect randomness from a source that may be far away from the uniform distribution, yet contains some randomness. This task is a crucial ingredient of any attempt to produce perfectly random numbers---required, for instance, by cryptographic protocols, numerical simulations, or randomised computations. Trevisan's extractor raised considerable theoretical interest not only because of its data parsimony compared to other constructions, but particularly because it is secure against quantum adversaries, making it applicable to quantum key distribution. We discuss a modular, extensible and high-performance implementation of the construction based on various building blocks that can be flexibly combined to satisfy the requirements of a wide range of scenarios. Besides quantitatively analysing the properties of many combinations in practical settings, we improve previous theoretical proofs, and give explicit results for non-asymptotic cases. The self-contained description does not assume familiarity with extractors.Informally, an extractor delivers perfect randomness from a source that may be far away from the uniform distribution, yet contains some randomness. This task is a crucial ingredient of any attempt to produce perfectly random numbers---required, for instance, by cryptographic protocols, numerical simulations, or randomised computations. Trevisan's extractor raised considerable theoretical interest not only because of its data parsimony compared to other constructions, but particularly because it is secure against quantum adversaries, making it applicable to quantum key distribution. We discuss a modular, extensible and high-performance implementation of the construction based on various building blocks that can be flexibly combined to satisfy the requirements of a wide range of scenarios. Besides quantitatively analysing the properties of many combinations in practical settings, we improve previous theoretical proofs, and give explicit results for non-asymptotic cases. The self-contained description does not assume familiarity with extractors.

arXiv:1212.0520Dec 3, 201220 citations

Extraction of quantum randomness

Igor M. Arbekov, S. N. Molotkov

Uspekhi Fizicheskih NaukNov 1, 202016 citations

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.