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
5. The Discrete Outcome Sensing Procedure
5.1 The First Scanning Sequence
5.2 The Second Scanning Sequence
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. |
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.
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.
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.
Figure 1) The PUDEC dice, loose
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.
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.
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.
Figure 4) The dice handling, step 1
Figure 5) The dice handling, step 2
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).
Figure 7) The PUDEC dice ready for discrete outcome sensing
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.
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.
Figure 8) The first scan sequence, perpendicular sampling of top face label
Figure 9) The first scan sequence, perpendicular sampling of front face label
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.
Figure 10) The second scan 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).
Figure 11) The third scan 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.
Figure 12) The fourth scan sequence
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.
Figure 13) The final outcome obliteration