4.25) Let F be a strong pseudorandom permutation, and define the following fixed-length encryption scheme: On input a message $m ∈ \{0,1\}^{n/2}$ and key $k ∈ \{0,1\}^n$, algorithm $Enc$ chooses a uniform $r ∈ \{0,1\}^{n/2}$ and computes $c:= F_k(m∥r)$. (See Exercise 3.18.) Prove that this scheme is CCA-secure, but is not an authenticated encryption scheme.

Solution: The scheme trivially does not satisfy unforgeability, since any $n-bit$ string is a valid ciphertext. But the scheme is CCA-secure — once again, we provide the intuition but would expect formal proofs for a full solution. To see this, imagine replacing $F$ with a random permutation $π$. Let $E$ denote the set of random strings used to answer the attacker’s encryption-oracle queries, and let $D$ denote the set of $n/2-bit$ suffixes in the answers to the attacker’s decryption-oracle queries. The elements of $E$ are uniform and independent; the elements in $D$ are “close” to uniform and independent. As long as the random string used when generating the challenge ciphertext is not equal to any of the elements in $E∪D$, the attacker learns nothing about which of its two messages was encrypted.

PS: This question is from the book Introduction To Modern Cryptography, Katz and Lindell, 2nd Edition. I'm having a hard time understanding that solution. So, if anyone could explain that intuition in another words, or in more details, I'd be glad. Just to be clear I'm not looking for a complete/formal solution, just understanding the intuition. (Posting again as text, as suggested)

  • $\begingroup$ Welcome to crypto.SE! It would be helpful to specify which aspect of the solution is challenging. On the question of AE security, do you see why the fact that every $n$-long bit string is a valid ciphertext breaks AE-security? $\endgroup$ Commented Oct 5, 2022 at 22:00
  • $\begingroup$ Yes, I understand why any n-bit string is a valid ciphertext, consequentially, making the scheme forgeable. The part where the author is proving CCA security is what gets me, trying to understand why those sets were created to be what they are, why set D is "close" to uniform and independent, and why as long as the random string used when generating the challenge ciphertext is not equal to any of the elements in E∪D, the scheme is CCA-secure. $\endgroup$
    – Carlos73
    Commented Oct 5, 2022 at 22:10
  • $\begingroup$ One way to see this is to work backwards from the conclusion. So in the ideal case, the attacker learns nothing from the challenge bit if the answer encrypt $m_0$ or $m_1$ simply returned a random ciphertext without even looking at the messages. But this is not exactly true since the PRP has some "structure". But if we had a random permutation, we could justify this if the effective input to the PRP was not used earlier, i.e., $r \notin E \cup U$. Honestly I don't understand the "close" to uniform part... $\endgroup$ Commented Oct 6, 2022 at 21:50
  • $\begingroup$ You can find some more justification in joyofcryptography.com/pdf/book.pdf, chapter 9.4. But it uses as somewhat different formalism $\endgroup$ Commented Oct 6, 2022 at 21:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.