Security Reduction

This post explores the stream cipher, a practical solution to the long-key problem of the One-Time Pad. We delve into how a “pseudo-random generator” (PRG) can “stretch” a short key (seed) into a long keystream for encryption. The blog’s core focuses on the formal security definition of a PRG—the concept of “computational indistinguishability”—and presents a detailed proof demonstrating that a secure PRG leads to a semantically secure stream cipher. [Read More]

This blog delves deeper into the meaning and consequences of semantic security, one of the foundational concepts of modern cryptography. We will begin by proving that a semantically secure encryption scheme does not allow an adversary to deduce even the smallest piece of partial information about the original message, such as its parity. Next, through the example of an Internet roulette game, the blog will illustrate how the definition of semantic security is applied to analyze the security of real-world applications. Finally, we will become acquainted with another, equivalent interpretation of semantic security—the bit-guessing game—a powerful and convenient tool commonly used in cryptographic proofs. [Read More]

This blog introduces the notion of message recovery attacks, defines the corresponding security game, and proves that semantic security implies message recovery security via a black-box reduction. A semantic adversary is constructed by wrapping around a message recovery adversary, showing that any success in message recovery would contradict semantic security. This sets the stage for future reductions that interrelate various cryptographic security notions. [Read More]