Paper 2025/1156
An efficient construction of Raz's two-source randomness extractor with improved parameters
, Quantinuum, University College London, University of York, University of Bristol, École Normale Supérieure de Lyon, QuantinuumAbstract
Randomness extractors are algorithms that distill weak random sources into near-perfect random numbers. Two-source extractors enable this distillation process by combining two independent weak random sources. Raz’s extractor (STOC '05) was the first to achieve this in a setting where one source has linear min-entropy (i.e., proportional to its length), while the other has only logarithmic min-entropy in its length. However, Raz's original construction is impractical due to a polynomial computation time of at least degree 4. Our work solves this problem by presenting an improved version of Raz's extractor with quasi-linear computation time, as well as a new analytic theorem with reduced entropy requirements. We provide comprehensive analytical and numerical comparisons of our construction with others in the literature, and we derive strong and quantum-proof versions of our efficient Raz extractor. Additionally, we offer an easy-to-use, open-source code implementation of the extractor and a numerical parameter calculation module.
Note: 12 + 11 pages. Comments welcome!
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- extractorsrandomness extractorstwo-source extractorsRaz's extractorefficient randomness extractors
- Contact author(s)
-
cameron foreman @ quantinuum com
lewis wooltorton @ ens-lyon fr
kevin milner @ quantinuum com
florian curchod @ quantinuum com - History
- 2025-06-20: revised
- 2025-06-18: received
- See all versions
- Short URL
- https://ia.cr/2025/1156
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2025/1156,
author = {Cameron Foreman and Lewis Wooltorton and Kevin Milner and Florian J. Curchod},
title = {An efficient construction of Raz's two-source randomness extractor with improved parameters},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1156},
year = {2025},
url = {https://eprint.iacr.org/2025/1156}
}
