Another good source of random bits

In a recent post, Steve Burnett talked a bit about NIST's DRBG and using it to generate random numbers. Here's an alternate approach to generating random bits. It has the advantage that its security is based on understanding how large organizations operate. Even fewer people understand that than understand the math behind pairing-based cryptography, so the number of people who could potentially attack a system that implements this approach is fairly small. Even better, absolutely none of these people are hackers.

In any event, here's how the sytem works.

Pick a suitably-big organization. The US government is a good example of this, and if this approach ever becomes approved for government use, the standard that defines its use will probably specify that the US government MUST be used for this.

To generate a random bit at a particular time, look at the parity of the number of divisions in the large organization at that instant in time. To make this more precise, to generate a random bit b(t) at a particular time t, find the number of divisions d(t) in the organization at that the time t and reduce it modulo 2:

b(t) = d(t) (mod 2)

The beauty of this PRNG is that, as anyone who has worked for one can tell you, the structure of large organizations is very random. Or if it's not truly random, it's indistinguishable from random. In any case, it's definitely a good source of random numbers, and this approach is probably just one the many ways that we can take advantage of this property.

Leave a Reply

Your email address will not be published. Required fields are marked *