Re: FFT test with few kbits
From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 02/29/04
- Next message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- Previous message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- Next in thread: Paul Pires: "Re: FFT test with few kbits"
- Maybe reply: Paul Pires: "Re: FFT test with few kbits"
- Reply: Paul Pires: "Re: FFT test with few kbits"
- Reply: Cristiano: "Re: FFT test with few kbits"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sun, 29 Feb 2004 21:02:47 +0100
On Fri, 27 Feb 2004 21:00:14 +0000, Paul Pires wrote:
> Take a moment to look at the common sense. Say this test
> is deployed, say it routinely passes good random streams.
But what evidence do you require before you would say that good random
streams routinely pass this test?
This would be easy, if we had a proof that Christiano's statistic
(asymptotically) follows the KS-distribution, but I hope that you can
agree, that we currently don't have such a proof.
Basically, that leaves just one other option: Monte Carlo
simulations. Essentially, what you are doing then is approximating the
empirical distribution of a statistic. Of course this is a valid
approach for any statistic. The only slightly tricky point is to
determine the number of simulations that you need. When someone has
done these simulations for a given value of N, you can of course use
these results in other cases where the sample size is also equal to
N. But what should you do when want to use this test with a different
value for N? The most prudent approach (which AFAIK is also followed
by statistical packages such as Diehard and NIST's) is to assume that
the test should only be used for the values of N for which simulations
have been performed. When you believe that we can be more lenient,
i.e. that we can also use the test even for values of N for which
there are no simulation results, could you explain why and under which
conditions? (One of the reasons why I would be cautious about
extrapolations is that the Fourier components show some curious
patterns that depend on the prime factors in N, and I would not be
surprised if the prime factorization also influenced the distribution)
>From a cryptographic point of view, of course, we are only interested
to see if the test can be used as a discriminator. But one of the
problems at the current stage is that it cannot be used in
isolation. For any other statistical test it would be reasonable to
reject a RNG based on the sole fact that it consistently fails that
test. At the current stage, we can't do that with Christiano's test,
because we must also show that a good RNG would not have failed as
well, something that is not necessary for statistical tests with a
known distribution (it does not matter if that distribution was
computed from its analytical solution or by simulations).
> I think it would be more usefull at this point to characterize the test rather
> than "prove" it. Make a matrix of tested outputs of many generators tested
> with many popular tests and also your proposed test. Post the results.
That's a good idea of course.
Ernst Lippe
- Next message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- Previous message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- Next in thread: Paul Pires: "Re: FFT test with few kbits"
- Maybe reply: Paul Pires: "Re: FFT test with few kbits"
- Reply: Paul Pires: "Re: FFT test with few kbits"
- Reply: Cristiano: "Re: FFT test with few kbits"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
