news
Science | DOI: 10.1145/1924421.1924427
Gary Anthes
the Quest for
Randomness
It’s not easy to generate a string of numbers that lack any pattern
or rule, or even to define exactly what randomness means.
GEnERATInG RAndom num- BERS might seem pretty simple. After all, so many things in our everyday lives occur without pattern or repetition—coin tosses, for
example, or the distribution of raindrops on your car windshield. In any
case, the whole notion of striving for
randomness might seem a bit alien to
a computer scientist, who is trained
to make processes predictable and
repeatable.
IllustratIon by weknow/shutterstock
Cryptographers use random number generators (RNGs) to produce unpredictable keys for coded messages,
digital signatures, challenge-response
systems, and other technologies at the
heart of information security. And researchers in fields such as biology, economics, and physics use them to simulate the real world via Monte Carlo
models. Human life and great sums of
money may depend on the robustness
of these systems, yet it is often difficult
to prove that they work correctly—and
will continue to do so.
Part of the problem is one of definition. One might say, for example, that
a random bit generator (as RNGs are
often called) must over time produce
half 0s and half 1s, or that it must gen-
erate the sequence “00” one-quarter of
the time. But, points out Silvio Micali,
a computer scientist and cryptography
expert at Massachusetts Institute of
Technology (MIT), the sequence 0, 1,
2, ... 9 (written in binary) would pass
those tests but would hardly be consid-
ered “random.”
Definitions matter, Micali says. “If
you define [randomness] correctly,
then you can get it. But if you are vague
or unclear, you can’t possibly get it.”
In 1984, Micali and Manuel Blum, a
professor of computer science at Carn-
egie Mellon University, published an
influential paper, “How to Generate