3
$\begingroup$

I am wondering if there are any results in literature which construct a PRNG that is proved to pass the next bit test? If so, can you state what the PRNG is and where I can find more details on it? And if not, then why not; are there any important theoretical implications what would follow from existence of such a PRNG? Thanks in advance!

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Yes, such PRNGs exist. One example is Blum Blum Shub:

There is a proof reducing its security to the computational difficulty of factoring. When the primes are chosen appropriately, and O(log log M) lower-order bits of each xn are output, then in the limit as M grows large, distinguishing the output bits from random should be at least as difficult as solving the quadratic residuosity problem modulo M.

Technically, that means that Blum Blum Shub passes the next bit test assuming solving the quadratic residuosity problem is difficult. We cannot prove specifically that that's the case, but we do believe it is.

I suspect you might also be able to do a security reduction with a PRNG based on HMAC in counter mode, but I'm not personally aware of one in the literature. That doesn't mean that one doesn't exist, though.

$\endgroup$
1

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.