Matrix samplers match quantum-proof extractors with improved efficiency
Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
Computational Complexity
Summary
Drawing a connection between two complex tools—matrix samplers and quantum-proof randomness extractors—the authors show these tools can be viewed as equivalent. This lets them create better ways to sample and extract randomness, which is important for ensuring data is trustworthy even against quantum hackers. Their new methods use fewer random bits and sample points, improving on previous designs. This advance helps make systems that rely on secure randomness more efficient and robust.
What this means in practice
- •For cryptography engineers: Improve secure key generation techniques resistant to quantum attacks with more efficient randomness extraction methods.
- •For data security teams: Enhance randomness quality in privacy-preserving systems under adversarial conditions using optimized matrix samplers with reduced resource use.
Authors
Kuan Cheng, Ruiyang Wu
Abstract
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.