<blockquote>
<p>But is there any theoretical motivation, why this should work?</p>
</blockquote>
<p>They absolutely have theoretical grounding, they are all statistical tests that any true random oracle should satisfy.</p>
<p>It 'works', however, only in one specific way: they can prove something is <em>not</em> a good source of randomness. But an absence of evidence is not evidence of absence, they can <em>not</em> prove something <em>is</em> a good source of randomness.</p>
<p>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.</p>

CC BY-SA 4.0
2024-03-03T11:43:20.147Z
Okay, that is certainly true, lol.
uhbif19
CC BY-SA 4.0
2024-03-02T10:41:59.937Z
2024-03-02T10:41:59.937Z
orlp
<p>Found one well-known connection.</p>
<p>Seems like notion of &quot;normality&quot;, which is generalization of law of large numbers from single sampling values to <code>n-blocks</code> of them, does coincide to notion for random sequences resource-bounded to FSM.</p>
<p><a href="https://en.wikipedia.org/wiki/Normal_number#Connection_to_finite-state_machines" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Normal_number#Connection_to_finite-state_machines</a></p>

CC BY-SA 4.0
2023-10-02T19:21:18.920Z
2023-10-03T13:48:40.360Z
2023-10-03T13:48:40.360Z
uhbif19
<p>There are a lot of PRNG test batteries, like <a href="https://en.wikipedia.org/wiki/Diehard_tests" rel="nofollow noreferrer">DieHarder</a>. They do check that some statistical tests expected for random sequence are indeed present.</p>
<p>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?</p>
<p>By <a href="https://cstheory.stackexchange.com/questions/11461/are-theoretically-sound-pseudorandom-generators-used-in-practice">this answer</a> 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 &quot;better&quot; (i.e. generating all others)?</p>
<p>This seems similar to definition of randomness in algorithmic randomness theory, but I am not sure if there is a direct link.</p>

CC BY-SA 4.0
2023-09-29T10:14:02.483Z
https://crypto.stackexchange.com/q/394/351, https://crypto.stackexchange.com/q/10918/351, https://crypto.stackexchange.com/q/19676/351, https://crypto.stackexchange.com/q/2153/351, https://crypto.stackexchange.com/q/67437/351, https://crypto.stackexchange.com/q/10404/351, https://crypto.stackexchange.com/q/68804/351
D.W.
<cr.crypto-security><randomness><pseudorandom-generators>
Do pseudo-random number generator test batteries have any theoretical grounding?
uhbif19
# Do pseudo-random number generator test batteries have any theoretical grounding?

(Asked by: username_0 on 2023-09-28)

There are a lot of PRNG test batteries, like [DieHarder](https://en.wikipedia.org/wiki/Diehard_tests). 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](https://cstheory.stackexchange.com/questions/11461/are-theoretically-sound-pseudorandom-generators-used-in-practice) 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.

**Tags:** cr.crypto-security, randomness, pseudorandom-generators

> **Comments:**
> **username_1**: https://crypto.stackexchange.com/q/394/351, https://crypto.stackexchange.com/q/10918/351, https://crypto.stackexchange.com/q/19676/351, https://crypto.stackexchange.com/q/2153/351, https://crypto.stackexchange.com/q/67437/351, https://crypto.stackexchange.com/q/10404/351, https://crypto.stackexchange.com/q/68804/351  

---

## 2 answers

### Answer by username_2 on 2024-03-02. Score: 2

> 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.

> **Comments:**
> **username_0**: Okay, that is certainly true, lol.  

---

### Answer by username_0 on 2023-10-02. Score: 0

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>


---

