This question is from Introduction to Modern Cryptography 2nd Edition by Katz and Lindell found in chapter 3 exercise 8.

(a) Define a notion of indistinguishability for the encryption of multiple distinct messages, in which a scheme need not hide whether the same message is encrypted twice.

(b) Show that Construction 3.17 does not satisfy your definition.

(c) Give a construction of a deterministic (stateless) encryption scheme that satisfies your definition.

Construction 3.17:

Let G be a pseudorandom generate with expansion factor . Define a private-key encryption scheme for messages of length as follows:

-Gen: on input 1ⁿ, choose uniform k {0,1}ⁿ and output it as the key.

-Enc: on input a key k {0,1}ⁿ and a message m {0,1}⁽ⁿ⁾, output the ciphertext c := G(k) m.

-Dec: on input a key k {0,1}ⁿ and a ciphertext c {0,1}⁽ⁿ⁾, output the message m := G(k) c.