From: David Honig <honig@m7.sprynet.com>
Date: Fri, 31 Jul 1998 13:54:05 -0700 (PDT)
To: cypherpunks@toad.com
Subject: Refining entropy
In-Reply-To: <199807302045.WAA19934@replay.com>
Message-ID: <3.0.5.32.19980731134616.007c42d0@m7.sprynet.com>
MIME-Version: 1.0
Content-Type: text/plain




This essay addresses the question, How can we improve the output of a bad
true RNG?  By "true RNG" I mean a source of unpredictability, which
necessarily derives from an analog measurement.  By "bad" RNG
I mean that its output does not carry one bit of information per binary
symbol.  This means that not all output symbols are equiprobable.  Methods
to improve various properties of RNGs are called conditioning algorithms.

I had begun by thinking that, since the output of a block cipher in
feedback mode (ie, a stream cipher) is uniformly distributed ("white") that
it would be sufficient conditioning to feed a bad RNG into a block cipher
with feedback.  Here, the bad RNG would kick the cipher out of the fixed,
but key-dependant, sequence it would otherwise generate.

But it bothered me that I was producing more apparently-random bits than I
actually had negentropy.

On cypherpunks, Bill Stewart mentioned using hashes instead of ciphers.  A
hash is like a cipher in that
changing any input or key bit changes the  output unpredictably, but a hash
is irreversible because there are fewer output bits than input bits.    The
simplest hash is a one-bit parity; MD5
is a more expensive keyed hashing function used for message authentication.

Thinking about a hash instead of a cipher was interesting because now we
reduce the number of output bits, which if done right, could improve the
information carried by each binary digit.  We take the MAC of an imperfect
random number and toss the original random, retaining the MAC as our better
random value.

Can we get an analytic handle on this?

Let's take Mr. Shannon's measure of information over a discrete alphabet.
The average amount of information per symbol is the (negation of the) sum
of the probabilities of each symbol times the log base 2 of that probability.

If we have two symbols, A and B, and each occurs half the time, we have 
	1/2 * log (1/2) + 1/2 * log(1/2) = -1 = 1 bit, which is what we expect.

If symbol A occurs, say, 3 times more often than B, we get:
	3/4* log(3/4) + 1/4*log(1/4) = 3/4(log 3 - 2) + -2/4 = 3/4 log 3 - 6/4 -
2/4 = 3/4 log 3 - 2 = 
	2- 3/4*log 3 bits/symbol after handling the minus sign.  This is less than
the optimum 1 bit/symbol, achieved when the symbols are equiprobable as above.

So now we have demonstrated how to use Shannon to measure the actual
entropy carried by each imperfectly random symbol. We now use this to
measure the result of XORing two such imperfect values.

We continue to use the imperfect RNG source where A occurs 3/4 time, B
occurs 1/4 time.  We take 
two of these badbits and XOR them: 
A.A=A, 
A.B=B, 
B.A=B, 
B.B=A.

We now compute the liklihood of each output symbol: 

A.A	3/4 * 3/4 = 9/16	(A)
A.B	3/4 * 1/4 = 3/16	(B)
B.A	1/4 * 3/4 = 3/16	(B)
B.B	1/4 * 1/4 =1/16	(A)

So the output has symbol A 10/16 of the time, and B 6/16 of the time.  The
difference in frequency has decreased; the distribution becomes more
uniform, which means that the information content of the output has
increased.  The information content of the whole system can only decrease;
but if you destroy the inputs
the output carries their entropy.
	
The exact amount of information per symbol in the 10:6 distribution is 
	10/16 * log(10/16) + 6/16 * log(6/16) = 10/16 * (log10 - 4) + 6/16*(log6
-4) = 
	10/16 log 10 - 40/16 + 6/16 log 6 - 24/16 = 
	10/16 log 10 + 6/16 log 6 - 4 the negative of which is
	4 - (10log 10 + 6 log 6) / 16
	Which is less than 1 but more than the content of each of the 2 bits we
started with.

Intuitively, we have gone from this distribution:
 
----
------------

crossed with itself, yields this distribution of states: 

-
---
---
---------

which when collapsed yields this: 

------
----------


So: we can use Shannon's analytic measure to look at entropy collection
through
a combination of imperfect input bits.  It shows us that we'll never get
perfectly uniformly 
distributed symbols by combining arbitrary quantities of nonuniformly
distributed symbols, but we can get arbitrarily close.  All we need is more
input.
Quantity vs. quality.

A video ADC acquires say 8 bits resolution at 4 msamples/sec.  This might
condense down to 
4 Mbits/sec true negentropy, which is about half the rate of regular Ethernet.



honig@alum.mit.edu

   "Speech is not protected simply because it is written in a language"	
	Federal Misjudge Gwin on the Bernstein Case