# PRNG next bit test

I would like to know whether a specific PRNG satisfy the next-bit test or not.
will satisfying all of NIST statistical tests on PRNG guarantees passing the next-bit test? Or is there a specific algorithm to test for this?

I would like to know whether a specific PRNG satisfy the next-bit test or not.

That requires analyzing the design of the PRNG.

Will satisfying all of NIST statistical tests on PRNG guarantees passing the next-bit test?

No. The NIST statistical tests are intended to test an implementation of a RNG. They are next to useless to tell if a PRNG is good or bad from a design standpoint. The critical issue is that the test is working on the output of the (P)RNG, not on its design, which in cryptography is assumed to be available to attackers. It it entirely possible (and can be obtained on purpose, or even by accident) that a RNG with a disastrously weak design or implementation pass the test. A firm conclusion can however be drawn is if a RNG repeatedly fails test: either its design or implementation is faulty.

Is there a specific algorithm to test for this?

I do not know any attempt at that. It would likely require describing the PRNG per some grammar, which then would be processed by some sophisticated algorithm. That could draw some useful conclusions, at least sometime negative, and perhaps positive with heavy restrictions of the grammar and some hypothesis.

• I'm pretty sure the next bit test is equivalent to the halting problem. – SAI Peregrinus Jan 10 at 18:33
• NIST statistical tests can be used to eliminate some PRNG from the beginning. It can indicate weaknesses – kelalaka Jan 10 at 19:08

The source of confusion may be the following. Theoretically, since the work of Andrew Yao, it has been known that the next bit test is equivalent to pseudorandomness. Informally, a sequence generator is pseudorandom if and only if no polynomial time probabilistic algorithm can predict its next bit with probability strictly greater than $$1/2.$$

See the notes here for example.

However, there is a flip side to this. In CRYPTO'99 Schrift and Shamir proved

... the surprising result that the natural extension of the next bit test, even in the simplest case of biased independent bits, is no longer universal: We construct a source of biased bits, whose bits are obviously dependent and yet none of these bits can be predicted with probability of success greater than the bias. To overcome this difficulty, we develop new universal tests for arbitrary models of (potentially imperfect) sources of randomness.