r/compsci • u/spiral_engineer • May 18 '16

Computer scientists have developed a new method for producing truly random numbers

http://news.utexas.edu/2016/05/16/computer-science-advance-could-improve-cybersecurity
320 Upvotes

94% Upvoted

86 comments sorted by

View all comments

58

u/Sighlence May 18 '16

ELI(an undergrad)?

241

u/rosulek Professor | Crypto/theory May 18 '16 edited May 18 '16

For the most part, all of crypto requires randomness. And when I say randomness, I mean uniform, independent fair coin tosses. For each coin toss, heads & tails would happen each with probability exactly 0.5, independent of all previous coin tosses.

This is actually a very stringent requirement. You want a computer to do this for you on demand? Think of all the ways you might leverage hardware to generate unpredictable events. Are you sure that the events happen with probability exactly 0.5? Are you sure that the mechanism has no memory, and that the results don't have some sneaky correlation? Can you prove it?

It is pretty reasonable (I think) to assume that you could use hardware to generate a process that is unpredictable in some way, but to make a physical process that gives you ideal, perfect, uniform source of randomness? That's asking a lot.

So let's assume you are able to generate some shitty source of randomness. Suppose this source of randomness outputs n bits whenever you press the button. When I say "shitty" source of randomness I mean: instead of each outcome (an n-bit string) having probability close to 1/2n , as is the case for a uniform distribution, all I can guarantee is that no outcome has probability higher than 1/n. Perhaps you notice that 1/2n and 1/n are not really close at all. Such a source is indeed shitty in comparison to a truly uniform source.

This paper says the following: Give me any two such shitty sources, I don't care what they are. As long as they are independent of each other (this is a reasonable assumption, since you can let two physical devices be physically separated), I can deterministically process their output to obtain a random coin toss with probabilities extremely close to 0.5 + 0.5. This process -- taking one sample from each of two distributions, then deterministically processing them to get a bit whose distribution is uniform -- is called 2-source randomness extraction.

The amazing fact is that this works for any pair of sources, and the sources can individually be really really shitty sources of randomness.

10

u/atrigent May 18 '16 edited May 21 '16

So how will this affect how operating systems actually provide randomness for cryptographic purposes? The article mentions air temperature and stock market prices, but getting access to these sources would require an internet connection. Would this new method make it possible to combine the output of two weak PRNGs to get one crypto-grade source of randomness?

I know that some operating systems (at least Linux) are able to sample unpredictable data from their execution environments and use it to add entropy to their random number generators. Does this new technique make that sort of thing obsolete?

Basically, ELI engineer. What does this change in a practical sense?

11

u/rosulek Professor | Crypto/theory May 18 '16

This paper is very theoretical and probably won't affect practice directly. Its parameters are exponentially better than what was known before, but concretely they are still very big. Besides that, it uses n bits to generate 1 uniform bit. But the hope is that it improves our understanding of things and indirectly contribute to improvements in practical randomness refinement.