[26217] in cryptography@c2.net mail archive
Re: statistical inferences and PRNG characterization
daemon@ATHENA.MIT.EDU (David Malone)
Mon May 22 10:23:11 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sat, 20 May 2006 11:58:10 +0100
From: David Malone <dwmalone@maths.tcd.ie>
To: "Travis H." <solinym@gmail.com>
Cc: Cryptography <cryptography@metzdowd.com>
In-Reply-To: <d4f1333a0605190451v6f3e4cd3t298f0ffc6e503e52@mail.gmail.com>
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@metzdowd.com
