Lunchtime and Chosen Ciphertext Security

6.876/18.426: Advanced Cryptography April 2, 2003 Lecture 14: Lunchtime and Chosen Ciphertext Security 1 Recap: Naor/Young's Lunchtime Security 1.1 Definition At the beginning of class we reviewed the concept of security against a "lunchtime" attack (abbreviated CCA-1). Recall the protocol-based definition of CCA-1 security: 1. Initiation: An adversary ADVPPT is given the public key PK. 2. Learning: ADV can send polynomially many ciphertexts to an oracle, who will send the corresponding plaintexts (or will notify ADV if the ciphertext is invalid). In this way, ADV attempts to learn about the secret key or weaknesses in the cryptosystem. 3. Testing: ADV then sends two messages mo, m₁ which he thinks he can distinguish. The decryptor chooses a random be (0,1) and sends the encryption of ma. ADV then responds with a guess g∈ {0,1}. Def. A cryptosystem is CCA-1 secure (or "lunchtime-secure") iff Pr(bg) 1 + 1 +Poly(k) where & is the security parameter. 1.2 Naor-Yung Cryptosystem The Naor-Yung scheme[NY90] is a cryptosystem (G, E, D) defined as follows: G: The public key is the triplet (PK1, PK2, R), where PK, and PK2 are two independent public keys generated from an underlying GM-secure cryptosystem (G, E, D), and R is a random string long enough to use for a non-interactive zero-knowledge proof. The secret key is (SK1, SK₂), the two secret keys associated with PK, and PK2. E: To encrypt a message, first encrypt it using each of the keys PK1, PK using the underlying GM-secure cryptosystem. Also, supply a non-interactive zero-knowledge proof (using Ras the random string) that the two encryptions are of the same message. Thus, E(m) = (E(T, PK₁), E(, PK2), ПR("same message")). D: The decryption algorithm has two steps: 1. First, check the validity of II. If II is invalid, terminate with failure (1). 14-1 2. Assuming II is valid, calculate D₁(E(1m)) = m. It is important to first check that II is a valid proof. If II is invalid, then it is entirely possible that the two encryptions are not of the same message. The importance of this point will become clear in the proof. 2 Proof of Lunchtime Security Here we proved that the Naor-Yung system described above is CCA-1 secure. Proof, as always, is by contradiction. 2.1 Proof Assume that there exists some ADVppy that can guess & with probability non-negligibly better than. We show how to construct, given ADV, an algorithm ade that breaks the GM-security of the underlying cryptosystem (G, E, D). Construct algorithm ade as follows: 1. adu randomly selects a (1,2), ade then generates (PK, SK,) using G, and lets PK3-a be the input key PK (that adv will break). adv must also generate a "random" string for the NIZK proofs. In the case of some NIZK proof systems, for example, that of Feige, Lapidot, and Shamir [FLS90], the simulator can actually pick the ran- dom string in advance, without knowing the theorem it will be asked to prove. We thus use the simulator to generate the string R, and send the Naor-Yung public key (PK1, PK2, R) to ADV. We will need to record the state a of the simulator so we can use it later. Note that R may not be random if generated in this way. However, we know that R generated this way must be indistinguishable from random, or the zero-knowledgeness of the NIZK proof system would not hold. 2. ADV sends a ciphertext (01, 02, II) to adv. Just as the usual case, adu first checks that II is valid with respect to R; if invalid, 1 is returned to ADV. If it is valid, then presumably, my mom, so adv can return m (obtained by decrypting ca using SK). Since the messages are the same, ADV obtains no knowledge of the procedure used to decrypt the ciphertext, merely the decryption itself. (This step can be repeated a polynomial number of times.) Note here that if the adversary manages to slip a false proof in, we might have a problem. If c and ca encrypt different messages, then the adversary can distinguish the case a 1 (in which case we are behaving exactly as we're supposed to) from the case a 2. We will need to argue later that the adversary cannot distinguish these two cases. However, this cannot happen with more than negligible probability by the soundness of the NIZK proof system. 3. ADV sends two messages (mom) to adv. ade returns (mo, m₁) and gets back c Em, PK). The goal of adv is to guess b. We next pick a random bit r and let CE(, PK) and ca. Then, we run the simulator from state a to fake a