PaperlayerView exact revision on arXiv

Source-linked AI summary

Postprocessing for quantum random number generators: entropy evaluation and randomness extraction

Xiongfeng Ma, Feihu Xu, He Xu, Xiaoqing Tan, Bing Qi, Hoi-Kwong Lo

arXiv:1207.1473v2quant-phcs.CR

TL;DR

Practical QRNGs mix quantum randomness with classical noise, so their raw outputs require quantified entropy and extraction. The paper develops a generic min-entropy framework, applies it to two QRNG systems, and implements Toeplitz-hashing and Trevisan extractors. The implementations achieve 441 kbits/s and 0.7 kb/s, respectively, while the processed outputs pass diehard, NIST, and testu01 tests.

  • Problem

    Practical QRNG outputs mix quantum randomness with classical noise, creating a need to quantify source randomness before extracting information-theoretically provable random numbers.

  • Method

    The paper evaluates QRNG quantum randomness by min-entropy, provides postprocessing guidance, and implements Toeplitz-hashing and Trevisan randomness extractors.

  • Results

    441 kbits/s for the Toeplitz-hashing extractor and 0.7 kb/s for Trevisan’s extractor; processed outputs pass diehard, NIST, and testu01 tests.

  • Takeaways & Limitations

    The framework and implementations provide a postprocessing approach for extracting quantum randomness from practical QRNG data.

Abstract

from arXiv · show

Quantum random-number generators (QRNGs) can offer a means to generate information-theoretically provable random numbers, in principle. In practice, unfortunately, the quantum randomness is inevitably mixed with classical randomness due to classical noises. To distill this quantum randomness, one needs to quantify the randomness of the source and apply a randomness extractor. Here, we propose a generic framework for evaluating quantum randomness of real-life QRNGs by min-entropy, and apply it to two different existing quantum random-number systems in the literature. Moreover, we provide a guideline of QRNG data postprocessing for which we implement two information-theoretically provable randomness extractors: Toeplitz-hashing extractor and Trevisan's extractor.

I. INTRODUCTION

QRNGs aim to provide information-theoretically provable randomness, but practical devices mix quantum signals with classical noise. The paper motivates min-entropy evaluation and extractors that distill nearly perfect randomness from raw data.

  • Motivation: Pseudo-RNGs can generate high-speed randomness cheaply, but their security is not information-theoretically provable.Their outputs can be reproduced by deterministic algorithms given sufficient computational power.
  • Motivation: Quantum mechanics provides a basis for physical RNGs whose randomness can be information-theoretically provable.QRNGs use the probabilistic nature of quantum mechanics to generate randomness.
  • Problem: Practical QRNG signals inevitably mix quantum randomness with classical noise that an adversary may partially know or control.The paper assumes a trusted-device scenario while noting that classical fluctuations could be deterministic and known to Eve.
  • Problem: Randomness extraction uses a short random seed to distill nearly perfect randomness from raw QRNG data and remove classical-noise effects.The extractor’s key input parameter is the raw data’s min-entropy.
  • Related work: Previously used xor, least-significant-bit, and nonuniversal-hashing operations can pass statistical tests without providing information-theoretically provable randomness.Trevisan’s extractor is highlighted for quantum-adversary security, polylogarithmic seed length, and strong-extractor properties.
  • Definitions: An extractor maps an n-bit partially random source and a d-bit seed to an almost perfect m-bit random string.Strong extractors additionally allow the seed to be reused, with a security parameter increased by ε.

II. QUANTUM RANDOMNESS EVALUATION

The paper presents a generic framework for evaluating quantum randomness in practical QRNGs and illustrates it with existing systems. Its workflow prepares and measures a quantum state, then postprocesses raw outcomes with an extractor.

  • Framework: The framework evaluates quantum randomness in practical QRNGs and is illustrated using systems from two prior implementations.The authors state that the procedure can be adapted to other QRNGs with modifications.
  • Physical model: QRNG postprocessing separates quantum signals from classical noise, treating the latter as potentially known to or manipulated by Eve.Its objective is to extract quantum randomness while eliminating classical-noise contributions.
  • Physical model: The generic workflow prepares a quantum state, measures it, and applies a randomness extractor to the resulting raw data.Examples use delayed self-heterodyning for photon phase fluctuations and homodyne detection for vacuum-state quadratures.

B. Quantum randomness evaluation

The evaluation derives quantum-signal min-entropy by separating quantum and classical variance under stated modeling assumptions. For one QRNG, the procedure obtains 6.7 bits per 8-bit raw sample; other cases remain quantitatively incomplete when parameters are unavailable.

  • Evaluation method: The key evaluation quantity is the quantum signal’s min-entropy, obtained by deriving its probability distribution.The method focuses on the quantum signal contained in the raw data rather than the total signal alone.
  • Evaluation method: The first example models the total signal as quantum signal plus independent classical noise and assumes a Gaussian quantum signal.The analog signal is digitized by an ADC, and the quantum-to-classical variance ratio is denoted γ.
  • Evaluation method: The total signal variance is characterized by sampling, with the final assumption supported when raw data are independent and identically distributed.The classical noise need not itself be Gaussian.
  • Evaluation method: The quantum variance is derived from total raw-data variance and the quantum-to-classical variance ratio, then used to obtain the quantum-signal distribution.The distribution is digitized on {0, 1}8 before min-entropy is calculated.
  • Result: 6.7 bits per 8-bit raw sample is the obtained min-entropy for the evaluated vacuum-fluctuation QRNG.The result follows from the Gaussian quantum-signal model and 8-bit ADC digitization.
  • Scope and limitation: The framework can extend to discrete-variable QRNGs, but without detailed data for Ref. the final min-entropy was not calculated.The missing parameters include total quantum-and-classical variance and their variance ratio.

C. Upper bound of randomness

The randomness available from a practical QRNG is bounded, and the paper estimates this upper bound from the measurement setup while presenting reusable extraction implementations.

  • A QRNG’s randomness is a limited resource, so an entropy upper bound indicates the remaining margin for postprocessing improvement.
  • 20.5 bits is the estimated upper bound of min-entropy per photodetector sample for the example QRNG.The estimate uses 1.5 × 10^6 photons within a 200 ps detection window at 0.95 mW and 1550 nm.
  • The paper presents prototypical Trevisan’s and Toeplitz-hashing extractors intended for use with the example QRNGs and more general QRNGs.

1. Results summary

The paper implements an improved Trevisan’s extractor using error-correcting codes and a refined combinatorial design. Its implementation achieves 0.7 kb/s, while Toeplitz hashing is faster but uses a longer seed.

  • Trevisan’s extractor is theoretically secure against quantum adversaries, uses a polylogarithmic seed, and can be a strong extractor.
  • The implementation combines a Reed-Solomon–Hadamard error-correcting code with a refined Nisan-Wigderson design.
  • 0.7 kb/s is the output speed of the implemented Trevisan’s extractor.The error-correction-based one-bit extractor is identified as the major computational bottleneck.
  • 441 kb/s is the Toeplitz-hashing speed, compared with 0.7 kb/s for Trevisan’s extraction, while Trevisan’s uses a shorter seed.

2. Implementation procedure

The Trevisan implementation maps min-entropy-bounded QRNG data and a random seed through error correction and combinatorial design to produce an ε-close-to-uniform output. The procedure selects seed and output lengths from source and security parameters.

  • The extractor takes an n_i-bit QRNG string with min-entropy at least k and a d-bit random seed, then outputs n_f bits ε-close to uniform.
  • The implementation first maps the input to an n̄-bit codeword using an error-correcting code formed from Reed-Solomon and Hadamard codes.
  • n̄ = 2^2m_e, with m_e = ⌈log n_i + 2 log n_f − 2 log ε + 4⌉ determining the codeword length.
  • The output length n_f is upper-bounded by k in the error-correcting-code construction.
  • The design uses ρ = 1 to optimize output length, and its seed is partitioned into blocks associated with the combinatorial design.The design parameter ρ represents the ratio of min-entropy extracted; d should be minimized while n_f is maximized.
  • Each output bit selects a substring of the encoded codeword using positions specified by the corresponding design set S_i.

B. Universal hashing

Universal hashing provides an information-theoretic extraction route, but its seed must be counted because extraction randomness is not free. The paper implements Toeplitz hashing and evaluates it alongside statistical tests and finite-size considerations.

  • Unlike privacy amplification, randomness extraction must account for the random seed because the seed consumes random bits.
  • The Leftover Hash Lemma states that a two-universal hash family maps a source with min-entropy at least k to an ε-close strong extractor output.
  • An (m, ρ)-design is a collection of m subsets whose average pairwise overlap is no more than ρ.
  • The Toeplitz matrix can be reused for QKD privacy amplification, but small blocks can significantly reduce privacy-amplification efficiency through finite-size effects.
  • A Toeplitz n × m matrix requires n + m − 1 random seed bits because its first row and column determine all entries.
  • The Toeplitz procedure determines m from n, k, and ε, constructs the seeded matrix, and multiplies it by the raw data to obtain extracted bits.
  • 441 kbits/s is achieved with a 4096 × 3230 Toeplitz matrix, using a source bound of 6.7 bits per sample and ε < 2^-100.
  • The raw QRNG data fails the statistical tests because classical noise is mixed in and the quantum signals follow a Gaussian rather than uniform distribution.

B. Autocorrelation

Raw-data autocorrelation is concentrated within the 8-bit ADC sample, while postprocessing reduces residual autocorrelation to approximately 10^-5.

  • Raw-data autocorrelation is significant only within an 8-bit sample, consistent with the 8-bit ADC.Beyond 8 bits, the correlation falls below approximately 1 × 10^-3.
  • Postprocessing with either extractor eliminates within-sample correlation and reduces autocorrelation beyond 8 bits to 1 × 10^-5.The low residual values are reported for both Toeplitz-hashing and Trevisan’s extractor outputs.
  • The average raw-data autocorrelation is 9.5 × 10^-4 between bits and 4.9 × 10^-4 between samples.
  • The extracted-output averages are −1.0 × 10^-5 for Toeplitz hashing and 1.6 × 10^-5 for Trevisan’s extractor.For comparison, a truly random 10 × 10^6-bit string has expected average normalized correlation 0 with standard deviation 4 × 10^-4.

V. CONCLUDING REMARKS

The paper develops min-entropy evaluation and implements Toeplitz-hashing and Trevisan’s extractors for practical QRNG postprocessing. The extracted outputs pass diehard, NIST, and testu01, while Trevisan’s speed is limited by its one-bit extractor.

  • The study models QRNGs to evaluate quantum-source min-entropy and implements both Trevisan’s and Toeplitz-hashing extractors.The postprocessing scheme is applied to existing QRNG implementations.
  • The postprocessed random numbers pass all tests of diehard, NIST, and testu01.
  • Trevisan’s extraction-speed bottleneck lies in the error-correction-based one-bit extractor.The authors identify this component as the target for improving implementation speed.

Appendix A: Trevisan’s extractor implementation details

The appendix selects Trevisan-extractor parameters by balancing seed cost, security, output length, and computational complexity. The implementation reaches 706.8 bits/s, with finite-field operations dominating performance.

  • Parameter selection: Trevisan-extractor block size affects seed cost, security parameters, and computational complexity.The listed parameter set is chosen to run sufficiently fast on a personal computer.
  • Parameter selection: The output length nf = 1 Mb balances speed, seed cost, and security, because complexity grows as O(n^2) with input length.Too small an nf increases seed cost and security parameter ε, while too large an nf slows extraction.
  • Combinatorial design: nf = 2^14 is identified as the most economical combinatorial-design parameter in terms of rate.Smaller values incur high key cost, whereas larger values produce unwieldy complexity growth.
  • Performance: 706.8 bits/s is the top generation rate, with finite-field operations in GF2^m limiting the error-control-code speed.The parameters are selected to maximize generation rate, and number-theoretical operations dominate performance.
  • Performance: The implementation runs on a personal computer, while faster mainframe or GPU execution is identified as a future route to exploit parallelism.

Appendix B: Statistical test results

Statistical testing shows that postprocessing is necessary: raw QRNG data fails the tests, whereas both extractors produce outputs that pass the reported standard tests, with Trevisan coverage reduced by computational constraints.

  • Extractor results: Both Toeplitz-hashing and Trevisan’s extractor outputs successfully pass all reported standard statistical tests.The tests are diehard, NIST, and testu01, although some Trevisan tests are omitted.
  • Raw-data results: Raw data cannot pass any statistical tests because classical noise is mixed into it and quantum fluctuations are Gaussian rather than uniform.This failure motivates effective QRNG postprocessing.
  • Control results: The matlab2007 pseudo-RNG control does not pass all tests despite generating uniformly random 8-bit values from 0 to 255.The control emulates an 8-bit ADC output.
  • Diehard: Diehard testing uses 240 Mbits of data and accepts results only when every final P-value lies between 0.01 and 0.99.For multiple P-values, a Kolmogorov–Smirnov test produces the final P-value.
  • NIST: NIST testing uses 3.25 Gbits across 500 sequences, requiring P > 0.01 for more than 0.976 of sequences.When multiple P-values occur, the worst case is selected.
  • testu01: The testu01 evaluation uses the small crush test on 8 Gbits because crush and big crush exceed the available data size and computational power.For multiple P-values, the worst case is selected; failing-test P-values converge to 0 or 1.
Loading 1207.1473v2…