| HN Mirror

Sadly, this is outside my area of expertise. I will nonetheless attempt to answer your question, but please take my words with a grain of salt.

Before we even begin delving into true RNGs, it is worthwhile to consider if we're over-engineering the problem. Is a PRNG "good enough" for the task at hand? In most cases, it is. A well-seeded PRNG, such as the ones present in modern-day Operating Systems, are suitable for most tasks not involving National Security.

However, if you have a genuine need for a true RNG, a computer algorithm certainly won't be generating it. Computers are by nature deterministic, and thus are very poor at behaving unpredictably. Thus, like with all good problems, we are forced to enter the realm of physics.

The fundamental problem is, who will be observing the source of randomness? To my knowledge, there isn't a physical source of randomness that is observable to everybody. (I did some quick googling to confirm my suspicions, but if you're planning on using my words to do anything useful, please confirm my statement!). Thus, as I see it, you have several options:

1) Your idea, where all parties derive a true random number from physics and publically sum everyone's numbers together. Your qualifiers (2) through (4) hold, but (1) is difficult. In this case, a certain number of rogue nodes will be able to manipulate the computation. I remember a Professor of mine, who does research in this field, stating the minimum number of truthful nodes needed in a distributed computation is (2/3)n + 1, but again confirm this number for yourself.

My point here is, using the public-summing method, you are faced with the difficult problem of determining if a node is attempting to manipulate the system. While a provable solution has been found, after decades of research across the globe, my Professor still is working on the problem, thus demonstrating it is not an easy task.

2) Have a single computer (say, random.org) that is observing a true RNG, and publicizes the result for all to see. Of course you'd use asymmetric crypto so that all parties can prove that they've received the correct number.

Again, your qualifiers (2) through (4) pass, but (1) presents a different problem. We're back to where we started: do you trust random.org?

However, it's an easier task to make an authority trustable than a peer in a distributed computation. We trust Verisign to be a certificate authority, because we believe their security practices are half-decent, and they can be audited. (Every year all CA's are independently audited by WebTrust.org using pretty strict criteria.)

The same could be done for random.org: why not require certification and frequent auditing of their RNG equipment?

The other nice thing about RNGs is that you can audit them yourself, given enough time and expertise. When viewed correctly, poor RNGs will have distinct patterns visible to the eye (example: http://www.cs.hku.hk/cisc/projects/va/index.htm ).

The crux of my argument is: I don't know of a true RNG, that upon observation by multiple parties, all will receive the same random number. My instinct and my research says that none exist, but I would love to be proven wrong. Crypto experts, correct me!

If you'd like more information, Wikipedia is always invaluable: http://en.wikipedia.org/wiki/Hardware_random_number_generato...