**Summary**

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 2If is pseudorandom with , then .

Exercise 1Prove 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 3If 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 2Prove 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.”