TL;DR
This paper introduces a novel, real-time, seedless method for extracting high-quality randomness from quantum random number generators (QRNGs), even in the presence of a quantum adversary. By modeling QRNG output as "forward block sources" and employing a two-source extraction strategy, they achieve significantly faster processing speeds, making it practical for demanding applications.
What Problem Does This Paper Address?
Quantum random number generators (QRNGs) are crucial for secure communication and cryptography, promising truly unpredictable randomness. However, the raw output from these devices often needs "post-processing" to remove biases and ensure high quality. A significant challenge arises from the potential presence of a "quantum adversary" who might possess quantum side information about the randomness source. Traditional randomness extractors, designed for classical adversaries, can fail in this quantum setting. Furthermore, existing quantum-proof extractors often require a "seed" (a pre-shared random string) which needs frequent updating, posing logistical challenges, or they are not designed for real-time processing, limiting their applicability in high-speed scenarios. This paper tackles the problem of developing a real-time, seedless, quantum-proof randomness extractor that can efficiently process QRNG output.
Methods
The core innovation lies in the introduction of the "forward block source" model. Instead of treating QRNG output as a general min-entropy source, this model characterizes sources where each subsequent block of data contributes a guaranteed amount of new randomness, conditioned on previous blocks. This is a more specific but still general model that captures the behavior of many practical QRNGs.
Leveraging this model, the authors propose two online, two-source randomness extractors. These extractors process data as it arrives, without needing the entire dataset upfront. The key technique is the use of an inner-product extractor over finite fields. This extractor is applied to blocks of data derived from two independent QRNGs. The "seedless" aspect is achieved by the two-source extraction approach, which eliminates the need for an external seed. The "real-time" aspect is enabled by the online processing and the parallelizability of the inner-product operation on blocks.
Datasets
Not discussed in the paper. The paper focuses on theoretical construction and simulation using parameters from a known QRNG.
Key Insights and Ideas
- Forward Block Sources: This new model is a crucial step in bridging the gap between theoretical randomness extraction and practical QRNGs. It allows for more efficient extraction algorithms by exploiting the structure of the data.
- Real-time, Seedless Extraction: The combination of these features is highly desirable for applications like quantum key distribution, where speed and simplicity are paramount. Eliminating the seed simplifies implementation and enhances security.
- Inner-Product Extractor as a Gadget: The use of a simple inner-product function over finite fields as a building block for a more complex extractor is an elegant design choice that facilitates parallelization and efficiency.
- Quantum Adversary Resilience: The work explicitly addresses the threat of quantum adversaries, ensuring information-theoretic security in a quantum-enabled world.
Key Results
The paper presents two main extractors, Ext_neq and Ext_eq.
- Theoretical Guarantees: Both extractors are proven to extract a constant fraction of min-entropy from two independent forward block sources, even in the presence of a quantum adversary with product side information. The error bounds are quantified in terms of the min-entropy rate and parameters of the extractor.
- Simulation Results: A simulation using parameters from a real-world QRNG (based on homodyne detection) implemented on an FPGA demonstrates a remarkable extraction speed of 64 Gbps. This is a significant improvement over previous state-of-the-art results (e.g., 18.8 Gbps).
- Asymptotic Analysis: The proposed
Ext_eqextractor is shown to be asymptotically faster than a previously proposed seeded extractor.
Limitations and Future Work
- Min-Entropy Rate Requirement: The current extractor requires a min-entropy rate $\delta > 1/2$. The authors identify it as an "intriguing challenge" to explore if this restriction can be relaxed or achieved without compromising security or efficiency.
- General Sources: Extending the online extractor to handle more general sources, or even the most general min-entropy source, is an open avenue for future research.
- Trade-offs: The paper notes a trade-off between error and computational complexity in the
Ext_neqextractor, where larger constants lead to smaller errors but increased computation.
Summary updated