How to best obtain bit sequences from throwing normal dice?

Question

Throwing normal dice, one can get sequences of digits in [0,5]. In practice, which is the best procedure to transform such sequences into a desired number of bit sequences?

Answer 1

Thomas' first procedure produces 2 bits per roll with a probability of $\frac23$, i.e. it produces $\frac43 \doteq 1.333$ bits on the average. This can be improved as he describes, but it gets quite complicated soon.

Producing a single bit per roll by taking the result mod two leads to $1$ bit per roll, which is not much worse. Combining the two simple methods like

1 -> 00
2 -> 01
3 -> 10
4 -> 11
5 -> 0
6 -> 1

is quite simple and produces $1+\frac23 = \frac53 \doteq 1.667$ bits per roll. AFAIK, this is the maximum you can get without aggregating the rolls.

You can apply this idea to two rolls and obtain $5$ bits with probability of $\frac{32}{36}$ and $2$ bits otherwise thus getting

$$2 + (5-2) \cdot \frac{32}{36} = 2 + \frac{3 \cdot 8}9 = 2 + \frac83 = \frac{14}3 = 4\frac23$$

bits for two rolls, i.e., $2\frac13 \doteq 2.333$ bits per roll, which is quite close to the theoretical maximum of $\log_2 6 \doteq 2.585$.

For a simple "implementation without computer", note that you can extract 1 bit directly from each roll and need to process the "rest" only (e.g. you can get the bit via $n \bmod 2$ and the rest via $\lfloor \frac{n-1}3 \rfloor$). This makes even combining 3 or 4 rolls using a small table easy.

The exact procedure for two rolls

For simplicity, let's assume, each roll produces a number $n_i$ from the set $\{0, 1, \ldots, 5\}$.

• Extract one bit from each roll as $n_i \bmod 2$.
• Compute $3 \cdot \lfloor \frac {n_1}2 \rfloor + \lfloor \frac {n_2}2 \rfloor$, which is number $x \in \{0, \ldots, 8\}$
• In case of $x = 8$, you're out of luck and get nothing but the two bits from the first step.
• Otherwise, use $x \in \{0, \ldots, 7\}$ as the next three bits.

So, most of the time you get five bits. On the average, you get

$$\frac19 \cdot 2 + \frac89 \cdot 5 = \frac{42}9 = 4\frac23$$

bits as stated above.

There are nearly 5.170 bits in two rolls, but you can't extract 5 bits from them on the average without further aggregation.

Answer 2

The obvious approach is to consider the following bit extraction algorithm:

1. Roll the die, producing an integer $n$ uniform in $\mathbb{Z}_6$.

2. If $n < 4$, return $n$ as two bits. Otherwise, go to 1.

This will return two uniform bits. The algorithm will always terminate, since the probability of recursion is equal to $\frac{2}{6}$ which is subcritical. A proof of correctness can be found in Dennis' post on this question.

How many dice rolls will the algorithm require? At least one, and arbitrarily many, but on average:

$$1 + \frac{2}{6} + \left ( \frac{2}{6} \right )^2 + \cdots = \sum_{t = 0}^\infty \left ( \frac{2}{6} \right )^t = \frac{3}{2}$$

That is, on average, the algorithm will require one and a half dice rolls. This is, of course, in accordance with information theory, which states that the Shannon entropy of an unbiased dice roll is equal to:

$$\log_2{ \left ( 6 \right )} = \log_2{\left ( 4 \right )} + \log_2{ \left ( \frac{3}{2} \right )}$$

---

However, this is not optimal. A lot of effort is wasted into compressing this into two uniform bits. Can we do better? Yes. For instance, consider rolling two dice together, drawing a uniform $n$ out of $\mathbb{Z}_{36}$. Then we can apply the same algorithm, but returning five bits instead of four, since $32 < 36$. Similarly, the probability of recursion is also lower at $\frac{4}{36}$ which means we are wasting less time and entropy.

We could also roll three dice, drawing $n$ out of $\mathbb{Z}_{216}$, but this is not optimal, even though we can extract seven bits, the probability of recursion is $\frac{88}{216}$ which is much higher than with even just a single die.

So, clearly, the "trick" is to select an integral number of dice such that $6^k$ is very close to (but greater than) a power of two, to minimize the probability of recursion and maximize our use of entropy. A computer program could be written to find the optimal number of dice to roll according to some efficiency metric, depending on your application's needs (or perhaps a general one exists).

---

The "intuition" behind this is that you can't use arbitrary amounts of entropy, since the bit is the absolute smallest amount of information possible. Any non-integral amount of entropy remaining must be "left behind" (here we use a recursive procedure to eliminate it, but there are other alternatives*).

However, if you can combine multiple such non-integral amounts of entropy through a non-destructive process (here, throwing multiple dice at the same time) you will naturally get more integral amounts of entropy ($0.5 + 0.5 = 1$) which allows you to make better use, of what you would otherwise have had to throw away.

---

*The answers to this question also suggest recursion is not an optimal approach in terms of efficiency.

Answer 3

1 way to get 3 bits of entropy from a single die roll is as follows :

1. Roll the fair die
2. For 2,3,4,5 yield two bits {01,10,11,00} and go to 4, for 1 or 6 yield {1,0}.
3. For the number on the die appearing right-way-up to the thrower (0-179 degrees) yield {0} for the number on the die appearing upside-down to the thrower (180-359 degrees) yield {1} and go to 5.
4. For the number on the die being oriented within the first quadrant yield {00} for the other quadrants proceeding clockwise yield {01,10,11}.
5. Go to 1.

So for example I throw the following sequence 2(12 degrees), 3(111 degrees), 6 (98 degrees)

 2 -> 01, 12 degrees -> 0 , so 2(12) -> 010
 3 -> 10, 111 degrees -> 1, so 3(111) -> 101
 6 -> 0, 98 degrees -> 01, so 6(98) -> 001

Giving 010101001 169 for 3 throws.

Since number and rotations should both be random variables, the distribution is uniform, unbiased and random. The good thing is rotational distinctions between upper lower half, and all four quadrants are almost as easy to distinguish with the naked eye as the numbers themselves. Though on the boundaries there will be some error and bias, introducing a small additional noise into the signal.

Effectively this procedure amounts to the following : roll the die measuring its number and quadrant of rotation, and discard 1 bit of the quadrant information for the numbers {2,3,4 and 5}.

Answer 4

Here is a specialization of this answer that is efficient in term of average entropy loss, and easily implemented.

Let $n$ be the number of faces on the dice ($n=6$ for a common dice). Let $b$ be the minimum value on the dice ($b=1$ on a common dice). Let $m$ be some large integer with $m≥n^2$. No value used will exceed $m$.

1. Set $r←0$, $s←1$.
   
2. If $s$ is even then proceed to 8.
3. If $s>m/n$ then proceed to 7.
4. Throw dice, getting $x$
5. Set $r←(x-b)+(n⋅r)$ and $s←n⋅s$
6. Proceed to 2 (optionally: or directly to 8 for even $n$).
7. If $r=s-1$ then proceed to 1.
8. Output $r\bmod 2$
9. Set $r←⌊r/2⌋$ and $s←⌊s/2⌋$
10. Proceed to 2.

The algorithm maintains $r$ uniformly random with $0≤r<s$, and its correctness follows from that.

As $m$ grows, the average proportion of lost entropy vanishes. However, the algorithm will from time to time (including initially) experience a longer period where it accumulates entropy and temporarily outputs at a low rate (or not at all for several consecutive dice throws, for odd $n$).

Answer 5

I would point out three things relating to this question.

• Normal dice
• In practice
• This is a cryptography forum

The first two points mean that you might be using biased dice. Normal dice are non homogeneous, perhaps chipped and might even be missing some spots. So their rolls would favour one outcome over another in the long run. They go to great lengths with expensive casino dice to eliminate as much bias as possible. They can't entirely, and hence the dice have sharp edges for grabbing the soft cushioning /pins of the craps table. Chaos plays it's part here in further reducing bias. And since this is cryptography, bias isn't a good thing if you're going to roll dice to generate encryption keys.

So the obvious solution is a von Neumann extractor. Roll twice. If roll 1 > roll 2, you get a "1". If roll 2 > roll 1 you get a "0". If roll 1 = roll 2, then output nothing and roll again. It's inefficient as you generate less than 1 bit per 2 rolls (it would be exactly 1 bit /2 rolls but you'll need a re roll every 6th pair). I think that it's actually 0.429 bits /roll in the long run. Not too bad considering they will be independent and identically distributed, or IID in NIST parlance.

The basic von Neumann algorithm can be much improved (x2) by considering multi pass tuples and erasures, but that level of maths is beyond me.

So in summary, you can generate a 256 bit AES key with less than 600 dice rolls and no Uranium or dodgy Intel RDRAND. Perhaps there's another way though?