[Cryptography] Throwing dice for "random" numbers

[Judson Lester]

On Wed, Aug 22, 2018 at 10:47 AM Howard Chu <hyc at symas.com> wrote:

> John Denker via cryptography wrote:
> > On 08/15/2018 07:20 AM, Dave Horsfall wrote:
> >
> >> it occurred to me that it's not as simple as it seems, with the
> >> generated output (e.g. modulo 10) not being as uniform as one would
> >> hope.
> >


A little Googling about von Neumann and dice led me to this
http://markus-jakobsson.com/papers/jakobsson-ieeeit00.pdf which describes a
very cute algorithm for getting fair resutls from biased dice. Since a lot
of the discussion here has been "assuming perfect dice" and you describe a
cheap pack of 12, which are likely far from perfect.

Essentially, partition the dice as suggested by John Denker - an egg carton
seems ideal. Roll a few times, recording the results for each die. Result
the lists of results to a list of *result ranks* - e.g. 3 2 6 -> 2 1 3 and
4 4 5 -> 1 1 2. Each such list is indexed into a canonical order of rank
lists (e.g. 123, 132, [213], 231, 312, 321 -> 3) and the index is the
result for that die for that set of rolls. Consume dice based on the "size"
of the fair die (i.e. 326 is a result of a 6 sided fair die, but 445 is on
a 3 sided die) until the sum of the sides is at least your required range.

The paper also describes how to convert the results into fair bitstrings,
which might let you truncate at the point where you have enough bits, where
the above summing solution would demand that you discard the whole result
if it were greater than your intended range.

Alternatively (and on increasingly shaky ground), you might discard final
"fair dice" until you found one of the right size to get you to your needed
range. I think if the algorithm for choosing which dice to include were
deterministic for a particular result, you might still get good random
values, but I'd be shocked if no one here differed on that point.

Judson
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180822/5c4838b5/attachment.html>