statistical inferences and PRNG characterization

[David Malone]

On Fri, May 19, 2006 at 06:51:55AM -0500, Travis H. wrote:
> As I understand it, when looking at output, one can take a
> hypothetical source model (e.g. "P(0) = 0.3, P(1) = 0.7, all bits
> independent") and come up with a probability that the source may have
> generated that output.  One cannot, however, say what probability such
> a source had generated the output, because there is an infinite number
> of sources (e.g. "P(0) = 0.29999.., P(1) = 7.000...").  Can one say
> that, if the source must be A or B, what probability it actually was A
> (and if so, how)?

You could do this with relatively simple Bayesian classification.
Start with a prior assumption like "As far as I know it is 50/50
that it is source A or B" and then for the output you see you
calculate P(A|output) and P(B|outout) using Bayes rule, your
probabilistic model for the source and P(A) = P(B) = 0.5.

	P(X|O) = P(O|X) P(X)/P(O)

A finite number of sources is not required here, as long as you're
willing to provide a prior distribution over all possible sources
that you can do calculations with.

> Also, it strikes me that it may not be possible to prove something
> cannot be distinguished from random, but that proofs must be of the
> opposite form, i.e. that some source is distinguishable from random.

I think you're still going to run into the problem of deciding what
is random, and that problem will be tied up in your choice of prior
distribution on the sources.

> Am I correct?  Are there any other subtleties in the application of
> statistics to crypto that anyone wishes to describe?  I have yet to
> find a good book on statistics in these kinds of situations, or for
> that matter in any.

I guess the usual proviso: these sort of calculations require
assumptions to make them possible, and the results should not be
confidently applied outside situations where those assumptions are
valid.

	David.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com