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)
