Generating Cryptographically Secure Random Numbers With Coins and A Cup

This article was first published on Sia Blog - Medium
-----

Generally it’s a bad idea to generate your own randomness. Whether you are pulling things randomly out of your brain or using a physical device like a coin, you are likely introducing some form of bias and predictability which can greatly reduce the security of whatever you need randomness for (such as a passphrase or a bitcoin seed).

It turns out however that there are some neat mathematical tricks that allow us to generate cryptographic grade random numbers using just some coins, a cup, and pencil and paper. And the full procedure is simple enough that an eight year old could complete the task successfully.

The Von Neumann Trick

Before I get into my technique, I want to cover something called the ‘Von Neumann Trick’, which is a strategy used to turn a biased coin into a fair coin. The technique is simple: flip a coin twice. If it comes up as heads-heads or tails-tails, throw away the result and start over. If it comes up as heads-tails, accept the result as ‘heads’. If it comes up as tails-heads, accept the result as ‘tails’.

Quick proof: the probability of getting heads-heads is p². The probability of getting tails-tails is (1-p)². The probability of getting heads-tails is p*(1-p), and the probability of getting tails-heads is (1-p)*p. For all values of ‘p’, the probability of ‘heads-tails’ is equally likely to the probability of ‘tails-heads’, even though the probability of ‘heads-heads’ may be significantly different than the probability of ‘tails-tails’.

Though mathematically pure, this trick is deficient in the real world. The trick depends on the coin flips having the exact same bias for each flip, and also depends on the coin flips being completely independent. In the real world however, the probability that a coin comes up as heads is not just a function of ...

-----
To keep reading, please go to the original article at:
Sia Blog - Medium

Comments (No)

Leave a Reply