Security

Encryption breakthrough: Scientists derive truly random numbers using two-source extractors

Computer scientists enhance data security by simplifying the creation of truly random numbers used to build encryption keys.

Image: iStock

Random numbers are a lot more important than most of us realize. Besides creating keys used to encrypt anything from databases to email, random numbers help predict weather patterns, sort out gaming theory, and are utilized in the creation of music.

So what exactly is a random number? Random.org defines a random number as:

"One that is drawn from a set of possible values, each of which is equally probable, i.e., a uniform distribution. When discussing a sequence of random numbers, each number drawn must be statistically independent of the others."

Two ways to create random numbers

One might think it would be easy for computers to generate random numbers, but people at Random.org disagree, "Surprising as it may seem, it is difficult to get a computer to do something by chance. A computer follows its instructions blindly and is therefore completely predictable."

Still computers are involved in the creation of random numbers: either mathematically creating Pseudo-Random Numbers (PRNs) or using random occurrences like the movement of a digital mouse to create True Random Numbers (TRNs). Mario Stipcevic and Cetin Kaya Koc in their University of California Santa Barbara research paper True Random Number Generators go into more detail about each method of random-number generation:

  • Pseudo-Random Number Generator (PRNG) is nothing more than a mathematical formula that produces a deterministic, periodic sequence of numbers, which is completely dependent on the initial state called the seed. By definition, such generators are not provably random.
  • True Random Number Generators (TRNGs) extract randomness from physical processes that behave in a fundamentally non-deterministic way, which makes them better candidates for true random number generation.

Why a better way to create random numbers is needed

Today's computing systems (hardware and software) are powerful enough that bad guys are able to predict random numbers created using PRNGs in a reasonable amount of time—that has placed increased emphasis on finding a truly non-deterministic process. Current best practices employ natural phenomena to inject randomness.

For example, the HotBits service at Fourmilab in Switzerland uses the points in time at which a radioactive source decays to create TRNs. Random.org prefers to generate randomness using electromagnetic atmospheric noise samples.

Both systems work but are cumbersome. Also, there is some evidence that natural phenomena may be less random than we think.

Mathematical TRNs

Here is where computer science professor David Zuckerman and graduate student Eshan Chattopadhyay, at the University of Texas-Austin, come into the picture. "UT Austin computer scientists have developed a new method for producing truly random numbers," mentions the university's press release, "a breakthrough that could be used to encrypt data, make electronic voting more secure, conduct statistically significant polls, and more accurately simulate complex systems."

Being a member of the tech media for a long time has afforded me a certain perspective on the people who eat, sleep, and breathe theoretical computer science; they are the definition of conservative, and for our sake, they should be. So we need to pay attention when Yael Kalai, a senior researcher working in cryptography at Microsoft Research New England, says, "When I heard about it [the research of Zuckerman and Chattopadhyay], I couldn't sleep. I was so excited. I couldn't believe it. I ran to the (online) archive to look at the paper. It's really a masterpiece."

And, Oded Goldreich, a professor of computer science at the Weizmann Institute of Science in Israel, writes, "This is a fantastic result! Handling any constant min-entropy rate would have been a feast, and going beyond that would justify a night-long party."

Next, let's look at what has computer scientists all excited.

A different approach

Rather than roll the dice or use complicated methods to incorporate natural-occurring randomness, Zuckerman and Chattopadhyay developed the mathematics for something called a two-source extractor. The best explanation for us ordinary citizens is by Henry Yuen and his blog Purifying spoiled randomness with spoiled randomness. For those more adventurous, this link leads to Zuckerman and Chattopadhyay's research paper on the two-source extractor's development.

Yuen starts out by writing:

"Pure randomness, as it turns out, is a valuable resource that is as rare as—perhaps even rarer than—gold or diamonds."

Put simply, using a two-source extractor, Zuckerman and Chattopadhyay are able to mathematically meld two weakly-random sequences of numbers into a single sequence of truly random numbers that is completely unpredictable.

According to Zuckerman, the method they discovered will improve encryption immeasurably. "One common way that encryption is misused is by not using high-quality randomness," says Zuckerman. "So in that sense, by making it easier to get high-quality randomness, our methods could improve security."

SEE: Encryption Policy (Tech Pro Research)

Peer review and accolades

Though excited, computer scientists are not easily swayed, demanding formal proof of any new work. By getting invited to present at this year's ACM Symposium on Theory of Computing (STOC), Zuckerman and Chattopadhyay's research had to pass extensive peer review. Passing muster and having their paper chosen as one of three to receive the STOC Best Paper Award speaks to the researchers' credibility.

Also see

About Michael Kassner

Information is my field...Writing is my passion...Coupling the two is my mission.

Editor's Picks

Free Newsletters, In your Inbox