We now turn to the problem of constructing encryption schemes that are provably secure in the presence of an eavesdropper. Our goal is to build schemes whose ciphertexts reveal no information about the plaintext beyond its length, under standard computational assumptions.
We begin by constructing a fixed-length private-key encryption scheme that achieves indistinguishable encryptions in the presence of an eavesdropper.
The construction closely mirrors the one-time pad. The essential difference is that instead of using a truly random pad, we generate a pseudorandom pad from a short secret key.
key k
|
v
pseudorandom generator
|
v
pseudorandom pad
|
v
plaintext ⊕ pad = ciphertext
This idea allows us to encrypt long messages using short keys, while maintaining computational security.
Let G be a pseudorandom generator with expansion factor ℓ, meaning that |G(s)| = ℓ(|s|).
The encryption scheme consists of three algorithms:
Encryption proceeds by applying the pseudorandom generator to the secret key (which serves as the seed) in order to obtain a long pseudorandom pad. This pad is then XOR-ed with the plaintext.
Let G be a pseudorandom generator with expansion factor ℓ. Define a private-key encryption scheme Π = (Gen, Enc, Dec) for messages of length ℓ(n) as follows:
Correctness follows immediately from the fact that XOR is its own inverse.
Theorem. If G is a pseudorandom generator, then this scheme has indistinguishable encryptions in the presence of an eavesdropper.
The proof proceeds by reduction: any adversary that distinguishes ciphertexts can be used to distinguish the output of G from true randomness.
The construction above assumes that all messages have fixed length. This limitation can be overcome by using a variable-output-length pseudorandom generator.
Informally, we want a generator that can output a pseudorandom string of any desired length.
More precisely, the generator G receives two inputs:
The unary encoding prevents an adversary from requesting exponentially long outputs in polynomial time.
A stream cipher is an algorithm that generates a pseudorandom stream. A secure stream cipher must therefore satisfy the definition of a variable-output-length pseudorandom generator.
A stream cipher is not an encryption scheme per se, but rather a tool for constructing encryption schemes.
Historically, RC4 was widely deployed and believed to be secure. It is now considered weak due to statistical biases in its output, which enabled attacks such as the break of WEP encryption.
Linear Feedback Shift Registers (LFSRs) have also been popular, though they are insufficient on their own for cryptographic security. Modern practice strongly favors constructions based on block ciphers.
So far, we have considered the case where an adversary observes a single ciphertext. In practice, an eavesdropper can observe many encryptions under the same key.
This motivates the notion of indistinguishability under multiple encryptions.
Definition. A private-key encryption scheme has indistinguishable multiple encryptions if no probabilistic polynomial-time adversary can distinguish between encryptions of multiple message vectors, except with negligible advantage.
It is important to note that some schemes secure for single encryptions fail in this stronger setting.
Theorem. Any private-key encryption scheme whose encryption algorithm is deterministic does not have indistinguishable multiple encryptions.
A tragic and common mistake is encrypting multiple plaintexts using a stream cipher in its naive form, thereby reusing the same keystream.
Secure constructions for multiple encryptions require careful randomization and will be discussed separately.