Next-Bit Test

This sixth blog in the Cryptography Series explores two fundamental ideas regarding Pseudorandom Generators (PRGs). First, we will learn about the Blum-Micali method, an intelligent sequential construction that allows us to build a PRG capable of extending its output to an arbitrary length from a base PRG that only stretches its input slightly. Next, the post introduces a core security standard: next-bit unpredictability. The highlight of this post is the proof of a classic and surprising result: a PRG is considered secure (indistinguishable from a truly random sequence) if and only if no adversary can efficiently predict its next bit. This provides a solid bridge between statistical theory and practical predictability. [Read More]