Secure Systems

Contributed by Bear Giles

Secure systems are systems that could survive intense radiation levels, broken hardware, etc.

Here's a simple example: assume you need a "fair coin toss" for a nondeterministic algorithm, but your hardware random generator is on the fritz and is no longer statistically random. You considered testing the RNG hardware and correcting for the bias, but the bias "drifts" too much for that approach (but too slowly for you to treat the results as random.)

Can you get a good "fair coin toss" from this hardware RNG? The answer is yes. Instead of reading each bit as it comes from the RNG, you look at pairs of bits:

   00 --> discard and retry
   01 --> 1
   10 --> 0
   11 --> discard and retry

If the odds of getting a "0" are p and the events are independent, you can quickly see that the relative odds of each possibility are p^2, p(1-p), (1-p)p and (1-p)^2. No matter what "p" is, the odds of getting a "0" or "1" out of the system is the same!

Likewise it's possible to create a fair three-sided coin given an unfair two-sided coin:

   000 --> discard and retry
   111 --> discard and retry
   100 --> 0     (1-p)p^2
   011           p(1-p)^2
   010 --> 1
   001 --> 2

The idea is you collect triplets of bits until you get a set where there is an "oddball". The position of the oddball gives you the result. The figures to the right show that the odds of the three choices are identical, if the coin tosses are independent.

Return to the Library