Score:3

Do there exists PRNGs that provably pass the next bit test?

lu flag

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!

kelalaka avatar
in flag
[Read this chat](https://chat.stackexchange.com/transcript/message/59992224#59992224)
Score:2
fr flag

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.

kelalaka avatar
in flag
[Read this chat](https://chat.stackexchange.com/transcript/message/59992224#59992224)
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.