Last time we introduced the setting of one-time symmetric key encryption, defined the notion of semantic security, and proved its equivalence to message indistinguishability.
Today we complete the proof of equivalence (found in the notes for last class), discuss the notion of pseudorandom generator, and see that it is precisely the primitive that is needed in order to have message-indistinguishable (and hence semantically secure) one-time encryption.
1. Pseudorandom Generators And One-Time Encryption
Definition 1 [Pseudorandom Generator] A function is a -secure pseudorandom generator if for every boolean function of complexity at most we have
(We use the notation for the uniform distribution over .)
The definition is interesting when (otherwise the generator can simply output the first m bits of the input, and satisfy the definition with and arbitrarily large ). Typical parameters we may be interested in are , , and , that is we want to be very small, to be large, to be huge, and to be tiny. There are some unavoidable trade-offs between these parameters.
Lemma 2 If is pseudorandom with , then .
Exercise 1 Prove that if is pseudorandom, and , then
Suppose we have a pseudorandom generator as above. Consider the following encryption scheme:
- Given a key and a message ,
- Given a ciphertext and a key ,
(The XOR operation is applied bit-wise.)
It’s clear by construction that the encryption scheme is correct. Regarding the security, we have
Lemma 3 If is -pseudorandom, then as defined above is -message indistinguishable for one-time encryption.
2. Security for Multiple Encryptions: Vanilla Version
Definition 4 [Message indistinguishability for multiple encryptions] is -message indistinguishable for encryptions if for every messages , and every of complexity we have
Similarly, we define semantic security, and the asymptotic versions.
Exercise 2 Prove that no encryption scheme in which is deterministic (such as the scheme for one-time encryption described above) can be secure even for 2 encryptions.
Encryption in some versions of Microsoft Office is deterministic and thus fails to satisfy this definition. (This is just a symptom of bigger problems; the schemes in those versions of Office are considered completely broken.)
If we allow the encryption algorithm to keep state information, then a pseudorandom generator is sufficient to meet this definition. Indeed, usually pseudorandom generators designed for such applications, including RC4, are optimized for this kind of “stateful multiple encryption.”