3
$\begingroup$

There are a lot of PRNG test batteries, like DieHarder. They do check that some statistical tests expected for random sequence are indeed present.

But is there any theoretical motivation, why this should work? Why all other statistical tests would probably work too? And why PRNG would be good in crypto way, meaning that it could not be predicted?

By this answer it appears like currently non-relative proofs of PRNG security are not available at all, but maybe there are at least justifications why some statistical tests are "better" (i.e. generating all others)?

This seems similar to definition of randomness in algorithmic randomness theory, but I am not sure if there is a direct link.

$\endgroup$
1

2 Answers 2

2
$\begingroup$

But is there any theoretical motivation, why this should work?

They absolutely have theoretical grounding, they are all statistical tests that any true random oracle should satisfy.

It 'works', however, only in one specific way: they can prove something is not a good source of randomness. But an absence of evidence is not evidence of absence, they can not prove something is a good source of randomness.

Tests like DieHarder are just a tool for automatically filtering methods that have easily shown issues. It is not a tool for showing a method is good.

$\endgroup$
1
  • $\begingroup$ Okay, that is certainly true, lol. $\endgroup$
    – uhbif19
    Commented Mar 3 at 11:43
0
$\begingroup$

Found one well-known connection.

Seems like notion of "normality", which is generalization of law of large numbers from single sampling values to n-blocks of them, does coincide to notion for random sequences resource-bounded to FSM.

https://en.wikipedia.org/wiki/Normal_number#Connection_to_finite-state_machines

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.