Intel’s circuit is implemented in
a 45nm complementary metal oxide semiconductor and can generate
2. 4 billion truly random bits per second—200 times faster than the best
available analog equivalent—while
drawing just 7 milliwatts of power,
according to Krishnamurthy. And the
technology is highly scalable, he says,
so that multiple copies of the digital
circuit could be coupled in parallel arrays. The technology could be scaled
up in this way to directly provide the
random numbers needed by large
systems, or it could be scaled down to
low voltages so as to just provide high-entropy seeds for a software-based
RNG, Krishnamurthy says. In the latter
mode, it would operate at 10 megabits
per second and draw just 10 microwatts of power.
Krishnamurthy acknowledges that
the circuit’s output is subject to process fluctuations—caused by transistor, power supply, and temperature
variations—that could introduce bias
in its output. But Intel has developed
a self-calibrating feedback loop that
compensates for those variations. The
resulting design operates at a level of
entropy of 99.9965% and has passed
the NIST tests for randomness, Krishnamurthy says.
But more work on these tests is
needed, says Elaine Barker, a mathematician in NIST’s Computer Security Division. “The thing we have
been really struggling with is how to
test the entropy sources, the noise
some random
number generators
initially work
correctly but silently
fail over time,
introducing biases
that corrupt
randomness.
sources,” she says. “We are kind of
feeling our way along. How do you
do general testing for technology
when you don’t know what will come
along? We are not really sure how
good these tests are.”
Entropy sources may not produce
output that is 100% random, and dif-
ferent test samples from a single
source may have different degrees of
randomness. “We want to know how
much entropy is in 100 bits— 100, 50,
or two?” Barker says. “And does it con-
tinue that way?”
Indeed, generating random num-
bers today clearly lags what is theoreti-
cally possible, Micali says. “We are still
in the mode of using library functions
and strange things that nobody can
prove anything about,” he says.
Further Reading
Barker, E. and Kelsey, J.
Recommendation for random number
generation using deterministic random
bit generators (revised), NIST Special
Publication 800-90, U.S. national
Institute of Standards and Technology,
March 2007.
Blum, M. and Micali, S.
how to generate cryptographically
strong sequences of pseudorandom
bits, SIAM Journal on Computing 13, 4,
november 1984.
Menezes, A., van Oorschot, P., and
Vanstone, S.
Pseudorandom bits and sequences,
Handbook of Applied Cryptography, CRC
Press, Boca Raton, FL, 1996.
Rukhin, A, Soto, J., Nechvatal, J., Smid, M.,
Barker, E., Leigh, S., Levenson, M., Vangel, M.,
Banks, D., Heckert, A., Dray, J., and Vo, S.
A statistical test suite for random and
pseudorandom number generators
for cryptographic applications, NIST
Special Publication 800-22, U.S. national
Institute of Standards and Technology,
April 2010.
Srinivasan, S., Mathew, S., Ramanarayanan, R.,
Sheikh, F., Anders, M., Kaul, H., Erraguntla, V.,
Krishnamurthy, R., and Taylor, G.
2.4Ghz 7m W all-digital PVT-variation
tolerant true random number generator
in 45nm CMOS, 2010 IEEE Symposium
on VLSI Circuits, honolulu, hI,
June 16–18, 2010.
Gary Anthes is a technology writer and editor based in
arlington, Va.
© 2011 acM 0001-0782/11/04 $10.00
Society
Predictive Modeling as Preventive Medicine
If an ounce of prevention is
worth a pound of cure, then
how much prevention would it
take to put a dent in the u.S.’s
projected $2.8 trillion annual
health-care tab?
how about $3 million
worth? That’s the amount the
heritage Provider network is
offering as prize money in a new
contest for developers to create
algorithms aimed at identifying
those patients most likely to
require hospitalization in the
coming year. (contest details
are available at http://www.
heritagehealthprize.com/.)
Previous studies have
suggested that early treatment
of at-risk patients can
dramatically reduce health care
expenditures. for example, a
well-regarded study in camden,
nJ, demonstrated that hospitals
could slash costs by more than
50% for their most frequently
hospitalized patients by
targeting them with proactive
health care before they incurred
expensive trips to the emergency
room.
In hopes of replicating
those savings on a larger scale,
the contest organizers will
furnish developers with a set of
anonymized medical records
for 100,000 patients from 2008.
using this data set, developers
will try to develop a predictive
algorithm to pinpoint those
patients most likely to have been
hospitalized the following year.
within the year.
“The heritage health Prize is
a high profile way to harness the
power of predictive modeling
and using it solves one of
America’s biggest challenges,”
says Jeremy howard, chief
data scientist for Kaggle, the
company managing the contest.
If successful, this effort
could yield a powerful
computational tool to help rein
in spiraling health-care costs,
potentially saving billions
of dollars—or at least a few
pounds’ worth of cure.
—Alex Wright