Dice

From Randomness for cryptography
Jump to navigation Jump to search

Dice are mechanical devices that are highly symmetric polyhedra with their faces numbered. The most common type is a cube, with 6 sides, numbers 1 to 6 with dots. See http://en.wikipedia.com/Dice for details on the history and culture. Dice have also been used to create random quantities for computer security, such as passphrases. See http://diceware.com.

Randomness of dice

There have been papers published that suggest dice aren't quite random in practice, e.g:

The last paper estimates the bias due to drilled pips on dice. Other reported limitations of dice randomness, 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 later 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

Note that 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).