analiza aiqbench
This is theoretical computer science: it links matrix samplers to randomness extractors that remain secure against quantum adversaries, and improves their parameters. The quantum angle is central, since the extractors must withstand quantum-side information, but the results are asymptotic constructions with no near-term hardware or deployment implications. Readers in quantum cryptography and randomness-generation research will find the extractor constructions most relevant.
Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
arXiv:2610.37122v1 Announce Type: cross 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 $\delta\leq\varepsilon$, our matrix sampler uses $m+O_\alpha(\log(D/\delta))$ random bits and $O_\alpha(\varepsilon^{-2-\alpha}\log^{1+\alpha}(D/\delta))$ samples, for any constant $\alpha>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-\gamma} 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_\alpha(a+\log(1/\eta))$ and seed length at most $(1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $\eta$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-\Omega(n)}$, having optimal seed length $O(\log(n/\eta))$ and output length $\Omega(n)$, improving previous constructions.
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 $\delta\leq\varepsilon$, our matrix sampler uses $m+O_\alpha(\log(D/\delta))$ random bits and $O_\alpha(\varepsilon^{-2-\alpha}\log^{1+\alpha}(D/\delta))$ samples, for any constant $\alpha>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-\gamma} 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_\alpha(a+\log(1/\eta))$ and seed length at most $(1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $\eta$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-\Omega(n)}$, having optimal seed length $O(\log(n/\eta))$ and output length $\Omega(n)$, improving previous constructions.
Computational Complexity (cs.CC); Quantum Physics (quant-ph)
arXiv:2610.37122 [cs.CC]
(or arXiv:2610.37122v1 [cs.CC] for this version)
https://doi.org/10.48550/arXiv.2610.37122 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 288 cuvinte