The PUDEC logo should appear here.

How to Seed Random Number Generation from Dice Shuffling

Thierry Moreau

Document Number C005033

2010/09/16

Copyright (C) 2010 CONNOTECH Experts-conseils inc.

This document is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

The invention described in this document is covered by a pending patent application.

PUDEC and the PUDEC logo are trademarks of CONNOTECH Experts-conseils inc.

Specifications subject to change without notice.

Table of contents

1. Introduction

2. What Is the RNG Seeding Operation?

3. The PUDEC Dice Set

4. The Dice Shuffling and Discrete Outcome Preparation

5. The Discrete Outcome Sensing Procedure

5.1 The First Scanning Sequence

5.2 The Second Scanning Sequence

5.3 The Third Scanning Sequence

5.4 The Fourth Scanning Sequence

6. The Final Discrete Outcome Obliteration

7. Why Shuffling Dice for RNG Seeding?

Document Revision History

C-Number

Date

Explanation

C005033

Current version

C005007

2010/06/23

Initial release

C005018

2010/06/30

The description of the discrete outcome sensing procedure refers to relaxed bar code scan order for the fourth scanning sequence.

The patent pending status is mentioned along the Copyright notice.

C005033

2010/09/16

Document updated following the availability of production PUDEC dice: prototype photos replaced by production unit photos, the PUDEC logo appears at the beginning of the document, and minor related adjustments to the text.

The PUDEC acronym is explained and its trademark status is noted.

1. Introduction

This document explains how to handle PUDEC dice for the RNG seeding operation in systems that require it. It is a step by step instruction manual, but it also explains why the operator does what he is instructed to do. The name PUDEC is an acronym for Practical Use of Dice for Entropy Collection.

The PUDEC dice shown in this document are available for sale. The interested readers are invited to contact the author's organization for further information.

This original RNG seeding approach raises questions in the area of system and software design, and security theory of operations as well. While the author's organization is used to address these issues, they are left out of scope for the present document (which is more like a lay person tutorial introduction). We welcome inquiries about system, software, and security aspects.

Readers for whom English is a second language should be aware that die is the singular form for dice which is a plural noun.

2. What Is the RNG Seeding Operation?

Many computer applications use random number generation (RNG) but not all of them require good RNG and some rational basis for trust in RNG process quality. For instance, computer games make extensive use of RNG but the player experience is not dependent on RNG process quality.

The scope of this document is where trust in RNG quality is important, which includes:

In all these contexts where a trusted RNG process is desirable, the digital systems make use of the pseudo-random number generation (PRNG) technique, which require a random seed for initialization. The random seed selection must be truly random in the sense that no two occurrences can give the same outcome and there are no means of predicting any outcome. After truly random initialization, the PRNG technique is fully deterministic.

An image may assist the understanding. The system PRNG is an enormous wheel with engraved numbers that look random. The PRNG is said to be deterministic because the engraved numbers are fixed, and eventually repeating (a good RNG process makes use of a PRNG with a cycle length many orders of magnitude larger than the total consumption of pseudo-random numbers in the whole system life span). The truly random seeding operation is the random selection of an initial wheel position. The term RNG process refers to the combination of a truly random PRNG seeding operation (initial positionning of the wheel) followed by normal or routine system operations that consume PRNG output data (the wheel slowly rotating as pseudo-random data is consumed). In practice, the PRNG is implemented by software but the trust in its statistical properties is based on mathematical reasoning and software quality control and/or certification. The random RNG seeding operation is achieved with the PUDEC dice handling procedure explained below.

The RNG seeding with the PUDEC dice is expected to occur only once when a system is first installed.

3. The PUDEC Dice Set

The PUDEC dice set is shown in figures 1 and 2. The dice faces are labeled with bar codes instead of legible dots or digits. This is important for the secrecy of the random RNG seeding, and for its true randomness as well: the operator can neither see nor influence the dice outcome that is input to the system.

Image not found.

Figure 1) The PUDEC dice, loose

Image not found.

Figure 2) The PUDEC dice, packed

Also, each die face bar code label indicates the face value (from 1 to 6) and the die number within the set (from 1 to 36). Thus, when a die face label is scanned, the system gets more information about the discrete outcome than what would be possible from 36 identical dice.

Another feature of the PUDEC dice set is that adjacent faces have perpendicular bar codes. This feature is combined with a bi-directional bar code scanner device that can decode a label only in the orientation parallel to its beam (either left-to-right or right-to-left when the scanner beam is horizontal, but not vertical labels). This restriction is used for data validation by the system, so overall process is more robust.

4. The Dice Shuffling and Discrete Outcome Preparation

The PUDEC dice come in a set, and their shuffling procedure lumps the whole set in the same shuffling and outcome preparation sequence. The figure 3 show how the set of dice may be shuffled manually in a plastic container.

Image not found.

Figure 3) The dice shuffling

The discrete outcome for the set is made of a random alignment, manually prepared as shown in figures 4 and 5 and 6. The plastic film with two guides shown in these figures is a convenient accessory, included in the PUDEC offering as the PUDEC dice alignment mat. The placement of shuffled dice in a random alignment is like rules of a game where shuffled dice are brought to a stable conventional position for discrete outcome observation, except that players excitement is inhibited by the nonlegible die face values.

Image not found.

Figure 4) The dice handling, step 1

Image not found.

Figure 5) The dice handling, step 2

Image not found.

Figure 6) The dice handling, step 3

The final discrete outcome should look tidy as in the figure 7. The discrete outcome sensing logic is based on a single continuous alignment; it is broken in two sections when using the PUDEC dice alignment mat but this is just a matter of ergonomy and convenience.

This end result provides more discrete random information to the system than 36 draws of an identical dice (approximately a three-fold increase). The alignent is indeed a permutation of 36 uniquely identified objects. Furthermore, the final alignment shown in figure 7 has a top face and a front face for each independent die. Given a top face value (out of 6 possible outcomes), the front face value is yet another discrete random element (out of 4 possibe outcome).

Image not found.

Figure 7) The PUDEC dice ready for discrete outcome sensing

5. The Discrete Outcome Sensing Procedure

The discrete outcome sensing procedure uses a hand held bar code scanner device. The model we currently use is the Opticon LGP-6125 (or OPT-6125), which is a simple bi-directional scanner using the CCD linear array technology without any moving parts.

Four sequences of scans are required to provide the system with complete discrete outcome data with opportunities for data validation and even error correction. Each scan sequence follows the dice alignment from one end to the other, always in the same direction for the first three sequences (it doesn't matter which direction is taken, as long as the same one is taken in the first three sequences of an outcome sensing occurrence).

The bar code scanner gives audio and visual feedback when a bar code label is decoded. If the operatof follows the specified four sequences of scans with reasonable care, he seldom needs further feedback from the system logic. After a little practice, the outcome sensing procedure is a matter of handling the scanner at a regular pace to scan the labels that are in the correct orientation in each of the four sequence.

The scanner beam is not rotated during a scan sequence, so that only those die faces in the proper label orientation will result in a scan. This is on purpose for the system logic that does data validation and error correction. The operator quickly learns which label orientation is intended in each scan sequence from the scanner device feedback.

5.1 The First Scanning Sequence

In the first scan sequence, the scanner beam is kept perpendicular to the dice alignment, and exactly one face is scanned from each die: either the top face as shown in figure 8 or the front face as shown in figure 9.

Image not found.

Figure 8) The first scan sequence, perpendicular sampling of top face label

Image not found.

Figure 9) The first scan sequence, perpendicular sampling of front face label

5.2 The Second Scanning Sequence

In the second scanning sequence, the scanner beam is also kept perpendicular to the dice alignment, but only the top face of the dice alignment is scanned. See figure 10. Statistically, half of the dice will have a top face label in the proper orientation for this second scanning sequence.

Image not found.

Figure 10) The second scan sequence

5.3 The Third Scanning Sequence

For the third scannig sequence, the scanner beam orientation is parallel to the dice alignment and only the top face of the dice alignment is scanned. Because the beam covers more than one dice in the parallel orientation, it is useful to blind a portion of the beam with a finger (otherwise, the scanner would decode the nearby labels repeatedly and out of order as long as more than one label is detected in the beam). See figure 11. Statistically, half of the dice will have a top face label in the proper orientation for this third scanning sequence (those having been omitted from the second scan).

Image not found.

Figure 11) The third scan sequence

5.4 The Fourth Scanning Sequence

For the fourth scannig sequence, the scanner beam orientation is also parallel to the dice alignment but only the front face of the dice alignment is scanned. See figure 12. For this last scanning sequence, the scan order does not matter as long as every dice (having the proper orientation) is scanned at least once. Statistically, half of the dice will have a front face label in the proper orientation for this fourth scanning sequence.

Image not found.

Figure 12) The fourth scan sequence

6. The Final Discrete Outcome Obliteration

As seen in figure 13, the dice alignment should be destroyed or obliterated as soon as the discrete outcome sensing is complete. Otherwise, the secret random data input to the system could leak through surreptitious scan or photo by an ill-intentioned individual. Or another system might be inadvertently seeded with the same discrete outcome.

Image not found.

Figure 13) The final outcome obliteration

7. Why Shuffling Dice for RNG Seeding?

A long-awaited improvement
While nothing special occurred in 2010 that suddenly made the PUDEC dice an urgent necessity, none of the existing approaches has ever been considered satisfactory. The sampling of a physical phenomenon known to be unpredictable requires sensors whith no other use in a digital system, and thus can fail quietly or introduce sampling errors impossible to isolate from the physical phenomenon itself. Dedicated electronic circuits arrangements exhibiting unpredictable behavior has been designed, but none really got widespread acceptance. Any RNG seeding approach using custom electronics may become obsolete given the fast evolving integrated circuit technologies. The unpredictable sequence of events in a computer system, like the timing of keystrokes on a keyboard, could in theory supply truly random data as a by-product, but this approach is too dependent on the level of system activity and goes against the general desirability of tidiness in the internal state of a computer system.
An effective solution for self-evident trust
The truly random process of shuffling PUDEC dice is self-evident and easily verified while being performed. The PUDEC dice discrete outcome collection process includes self-validation features that further enhances the confidence.
A label of quality for the system on which it applies
The RNG seeding is always a distraction from the normal operations of the system in which it occurs and no random seeding approach can match the speed potential of a PRNG. In the case of the PUDEC dice shuffling operation, a no-compromise solution is put forward: the RNG seeding is a serious distraction requiring operator intervention. Accordingly, the system design where it is used would pay close attention to PRNG implementation aspects which might otherwise be overlooked because automated periodic seeding gives a false sense of assurance.
Addressing a critical system operational requirement
As hinted above, the fields of application for the PUDEC dice RNG seeding are those in which an RNG process failure should trigger a production system to be removed from service. The PUDEC dice handling procedure is thus operationally critical.