PHYSICAL REVIEW A 87, 062327 (2013)
Postprocessing for quantum random-number generators: Entropy evaluation
and randomness extraction
Xiongfeng Ma,
1,2,*
Feihu Xu,
2,†
He Xu,
2
Xiaoqing Tan,
2,3,‡
Bing Qi,
2,§
and Hoi-Kwong Lo
2,
1
Center for Quantum Information, Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
2
Center for Quantum Information and Quantum Control, Department of Physics and Department of Electrical and Computer Engineering,
University of Toronto, Toronto, Ontario, Canada
3
Department of Mathematics, College of Information Science and Technology, Jinan University, Guangzhou, Guangdong, China
(Received 24 April 2013; published 21 June 2013)
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.
DOI: 10.1103/PhysRevA.87.062327 PACS number(s): 03.67.Dd, 42.50.Ex
I. INTRODUCTION
Random numbers play a crucial role in many fields
of science, technology, and industry—for instance,
cryptography, statistics, scientific simulations [1], and lottery.
Pseudorandom-number generators (pseudo-RNGs) based on
computational complexities have been well developed in the
past few decades [2] and can generate high-speed random num-
bers with little cost. However, the main drawback of pseudo-
RNGs is that the generated randomness is not information-
theoretically provable. In fact, all of the (software-based)
pseudo-RNGs can be realized by a deterministic algorithm
given sufficient computational power. This pseudorandomness
would cause problems in many applications, such as those
in cryptography [3,4]. Recently, Microsoft confirms that XP
contains RNG bugs;
1
security flaws have been found in online
encryption methods due to imperfections of random-number
generation.
2
To address the security issues introduced by pseudo-RNGs,
physical RNGs have been developed [5–7]. In particular,
the probabilistic nature of quantum mechanics offers a
natural way to build an information-theoretically provable
RNG [5]—quantum random-number generators (QRNGs).
Note that some physical RNGs have been included in
*
xma@tsinghua.edu.cn
†
feihu.xu@utoronto.ca
‡
ttanxq@jnu.edu.cn
§
bqi@physics.utoronto.ca
hklo@comm.utoronto.ca
1
See the news from the Computerworld, “Microsoft confirms that
XP contains random number generator bug,” Gregg Keizer, November
21, 2007.
2
See the news from the New York Times, “Flaw Found in an Online
Encryption Method,” John Markoff, February 14, 2012.
microprocessors,
3
although the generated randomness is not
quantum mechanical in nature.
4
In theory, a QRNG can produce random numbers with
provable randomness. In practice, quantum signals (the source
of true randomness
5
) are inevitably mixed with classical
noises. An adversary (Eve) can, in principle, control the
classical noise and gain partial information about the raw
random numbers. In this work, we assume a trusted device
scenario, but the classical noise might be deterministic if we
calibrate the system more carefully. For instance, imagine that
an input to our device is an external power supply. Imagine
further that through carefully monitoring the input value of the
power to our device, we have determined that the power may
still fluctuate by, say, up to 1%. In principle, the source of such
fluctuations of an external power supply might be the action of
an adversary—Eve—who, therefore, has complete knowledge
about the actual value of the power supply at all times.
Therefore, it is necessary to apply a postprocessing proce-
dure to distill out the true randomness that Eve has almost
3
See, for example, “Intel Corporation Intel 810 Chipset
Design Guide,” June 1999, Ch. 1.3.5, pages 1–10, down-
load.intel.com/design/chipsets/designex/29065701.pdf.
4
“Evaluation of VIA C3 ‘Nehemiah’ Random Number
Generator,” Cryptography Research, Inc., February 2003,
www.cryptography.com/public/pdf/VIA_rng.pdf.
5
We define “true randomness” when the randomness is information-
theoretically provable. One of the main objectives of our work is to
give a randomness extraction procedure such that the extracted output
numbers are proven random. On one hand, quantum mechanics comes
with randomness in nature. For example, no one can predict the results
of the vacuum fluctuation. On the other hand, it is not clear whether or
not one can extract “true” randomness from the classical noises. That
is, we have not proved the randomness extracted from the classical
noises. Thus, from a conservative point of view (especially for the
usage in cryptography), we only extract random numbers that are
information-theoretically provable.
062327-1
1050-2947/2013/87(6)/062327(10) ©2013 American Physical Society