[Cryptography] The ultimate random source

[Arnold Reinhold]

On Feb 16, 2014, at 8:00 AM, Jerry Leichter <leichter at lrw.com> wrote:

> On Feb 16, 2014, at 7:55 AM, Jerry Leichter wrote:
>> On Feb 15, 2014, at 11:46 PM, Phillip Hallam-Baker wrote:
>>> I actually started with rather more elaborate steampunk devices that had dice with different colored faces. These would be machine read somehow.
>> See http://hackaday.com/2009/05/26/dice-o-matic/
> ...however, as with the paper on the not-quite-randomness of coin tosses that John Denker forwarded yesterday, dice aren't quite random either:  
> http://www.insidescience.org/blog/2012/09/12/dice-rolls-are-not-completely-random
> 
> Interestingly, the same factors come into play:  Initial position is important; air resistance is not; bouncing helps but not as much as you'd expect.
>                                                        -- Jerry
> 

There have been other such papers on the limitations of dice randomness, but all deal with the case where dice are given an initial throw and then bounce along until they come to rest, with no additional energy input. Adding in enough mechanical energy as the dice tumbles eliminates the bias. This is a problem that has been recognized since at least the 4th century CE, see https://en.wikipedia.org/wiki/Dice_tower. My approach is to put the dice in a shoe box and shake them up vigorously, at least ten hard shakes. There is also a small bias in inexpensive dice where the pips are dimpled causing a slight mass imbalance. Casino dice don't have this problem and also have sharp corners, which improve tumbling, but are subject to wear.

However none of this matters for cryptographic purposes. Small biases in dice have very little impact on the entropy generated. For an ideal cubic die, each face has probability 1/6=1.66666... and a random throw has entropy -log2(6)=2.5849625.  Consider a crooked die with one face having a higher probability and the other five equal. We can compute its entropy by summing -p*log2(p) for each face. Below are the results of the favored face having p=1/5, 1/4, and 1/3, all biases that would make a gambler who could command them drool:

Face p	-p*log2(p)	        p	-p*log2(p)	p	-p*log2(p)
1	0.2	0.464385619	0.25	0.5			0.3333	0.528320834
2	0.16	0.42301699	0.15	0.410544839	0.1333	0.387585413
3	0.16	0.42301699	0.15	0.410544839	0.1333	0.387585413
4	0.16	0.42301699	0.15	0.410544839	0.1333	0.387585413
5	0.16	0.42301699	0.15	0.410544839	0.1333	0.387585413
6	0.16	0.42301699	0.15	0.410544839	0.1333	0.387585413
Entropy	2.5794706		2.552724		2.466248
Delta entropy	 
from ideal 0.00549		        0.03224		0.11871

As you can see, the difference from the entropy of an ideal die throw grows from negligible (0.00549 bits per throw) to insignificant (0.11871 bits per throw).

Arnold Reinhold