[Cryptography] Throwing dice for "random" numbers

[Arnold Reinhold]

On Mon, 13 Aug 2018 09:48 John Denker answered Dave Horsfall:

> On 08/12/2018 04:01 AM, Dave Horsfall wrote:
> 
>> I picked up a a pack of 12 dice from one of those discount stores for the 
>> princely sum of AU$2 (so we can safely assume that they are not exactly 
>> casino-quality[*], but at least the pattern of dots is correct).
>> 
>> So, the obvious question is: how unpredictable (not "random") would their 
>> sum be, modulo N, given that each individual source is numbered 1-6? 
> 
> *) Is this meant to be a conceptual question?  And
> are we supposed to take the word "sum" literally?
> 
> If so, then we proceed as follows:
> 
> Twelve is big enough that we can treat the distribution
> of sums as nearly Gaussian.  For a single die, the distro
> is nowhere near Gaussian, but we know the mean is 3.5 and
> the variance is 2.92, as you can easily verify directly
> from the definition.  When you sum multiple dice, the mean
> and variance grow linearly, so for 12 dice we get a mean 
> of 42 and a variance of 35.  So the stdev is σ=5.92.
> 
> It is well known that a Gaussian can be approximated well
> by a triangle with a HWHM equal to the stdev.  So the full
> width at baseline (FWBL) is 4σ.  It can be approximated
> less well but still decently by a rectangle with the same
> FWBL.  That is to say, all values within ±2σ of the middle
> are equally likely and all others are irrelevant.  So we
> estimate the entropy as log(4σ).
> 
> If you want to do a bunch of calculus, the fancy "official"
> result is log(√(4πe) σ) ... where the prefactor is √(4πe)
> = 4.13 ... so our intuitive value of 4 was not off by much.
> 
> All together you get log(4.13) + log(5.92) = 4.61 bits
> per roll.
> 
> 
> 
> *) Or is this supposed to be crypto engineering, as suggested
> by the Subject: line?
> 
> In that case, you shouldn't be computing the sum at all.
> You can get log(6) = 2.58 bits of entropy per die per roll,
> and if you consider them all separately you get 12*log(6)
> = 31 bits per roll.  That's a huge improvement in
> throughput.  There's no need to distinctively mark the
> dice.  We assume each die is statistically independent
> of the others.
> 
> 
> *) Or was the question meant to ask how to handle the
> systematic imperfections in the dice?
> 
> In that case, I recommend using the appropriate Rényi
> functional.
> 	H_0 is sometimes called the Hartley functional.
> 	H_1 is the plain old entropy
> 	H_∞ is what I call the adamance;
> 	    it is sometimes called the min-entropy, but
> 	    IMHO that is a misleading misnomer
> 
> H_∞ tells us the worst-case resistance to attack, which
> is appropriate for engineering a defensive cryptosystem.
> So we look at the probabilities.  The ideal case is
> 	1/6  1/6  1/6  1/6  1/6  1/6
> which gives you -log(1/6) = 2.58 bits of adamance per
> die per roll.
> 
> Now suppose that on the basis of careful measurements
> you know that the following is a *bound* on how badly
> non-ideal things can be:
> 	0.8/6  1/6  1/6  1/6  1/6  1.2/6
> which gives you -log(1.2/6) = 2.32 bits of adamance per
> die per roll.
> 
> This is what I would recommend (unless I have guessed
> wrong about the intended application).  This is what
> Turbid does.
> 
> ….

*) Another possibility: Dave mentioned reducing the sum modulo N, suggesting he is trying to get uniformly distributed numbers in the range 0 to N-1. If N is small compared to the expected mean of the sum, the result is likely to be close to uniform, but not exactly so. 

Here are some simple tricks for generating uniform integers using dice for common ranges, such as random decimal digits or random characters. Each of these methods produce perfectly random symbols, assuming the dice are perfect. 

To generate a string of random decimal digits, for example, one can roll many dice and record their values, discarding any that come up 6, until you have enough digits. Then roll that number of dice again, noting whether each outcome is odd or even. If odd, add 5 to the previous value, with 5+5 recorded as zero. 

For random characters from the set {a-z, 0-9}, one can make a six by six table with the 36 possible characters and use pairs fo dice rolls to select each character. For just letters, one can just discard pairs of rolls that produce digits from that table. To include upper and lower case letters and some special characters (the ten above the digits on standard keyboards), one can use a third die and press the shift key if the roll is odd. In the last example there are 72 possible characters, giving 6.17 bits of entropy per character, compared to 6.57 bits per character selected randomly from the 95 printing ASCII characters.

There are more examples in the diceware.com FAQ.

Arnold Reinhold