Re: [Eligibility-discuss] On 3797 alternatives

[Michael StJohns <[e-mail]>]

On 6/1/2023 3:47 PM, Eric Rescorla wrote:
>
>
> On Thu, Jun 1, 2023 at 8:43 AM Michael StJohns 
> <[e-mail]> wrote:
>
>     Hi -
>
>     Verifiably random is somewhat of an oxymoron.   We can do
>     statistical measurements of data streams, and come to conclusions
>     about how close they meet a given criteria, but that’s a far cry
>     from verifiable.  We can, using similar models usually prove a
>     source to be non random even if we can’t label it as predictable,
>     but the opposite is harder.
>
>     What I think we want is/are sources that meet some set of
>     statistical tests for randomness and that are shown to be
>     resistant to externally applied bias/interference.   The former is
>     pretty simple - take the output and run it through the tests.
>
>     The latter is more about "trustworthiness" than "verifiable
>     randomness".   WRT to the sources used to seed the last dozen or
>     so selections, we assume the trustworthiness because of the nature
>     of the sources and the fact that we combine a number of those
>     sources, but I'd be hard pressed to say that any single given
>     source is "verifiably random" in either meeting statistical tests
>     or resistance to externally applied bias.
>
>
> It's important to distinguish here between random and uniformly 
> distributed.

All large collections of true random bits are uniformly distributed, but 
not all uniform distribution of bits are random.

>
> As an example, imagine we have a randomness source X that produces 1-bit
> values X_1, X_2, .... By hypothesis, this passes the relevant 
> statistical tests.
>
> Now consider a source Y that is constructed as follows:
>
> Y_i =  {  0 if i is odd
>               X_i if i is even }
>
> Y will not pass many statistical tests because it is non-uniformly 
> distributed, but
> it of course contains entropy at 1/2 the rate of X.

But every i where i is odd is predictable and doesn't meet the general 
contract of "if the next bit generated can be predicted with better than 
50% confidence, then the bit is not random".  So it may be a good source 
of entropy (with enough bits produced), but is not directly usable as a 
random stream of bits.  (Hence your comment on hashing below - or the 
use of HKDF extract).

Y_i = X_(i*2)  also has 1/2 the entropy, but any given Y_i is only as 
predictable as a given X_(i*2)

> Fortunately procedures like
> those we use (hashing the inputs) are designed to use the available 
> entropy
> while accepting the non-random bits. This is good because some of these
> sources are not uniform (e.g., the US national debt). [0]
>
> As a result of this, statistical tests are generally not a good guide 
> to whether
> a given entropy source is appropriate.

Fair - but those self same statistical tests usually give some 
indication of the actual entropy production of the input stream. If I 
feed in 10000 bits (in the form of form of the asciification of a dozen 
or so values ) from a single source and get an answer of maybe 4 bits of 
entropy, it suggests that source may not be as useful as we would think.

>
> -Ekr
>
> [0] As an aside, even lottery numbers are not entirely uniform as a 
> bitstream
> unless you encode them properly.
>
>
I'd see something like: 
https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf 
or other papers.

It might be interesting to throw the inputs and outputs of our entropy 
source mixer at the various tests and see how it and they do.

Later, Mike