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