CPA-security of a pseudorandom permutation encryption scheme

Let $F$ be a pseudorandom permutation, and define a fixed-length encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$ $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm $Enc$ chooses a random string $r \leftarrow \{0,1\}^{n/2}$ of length $n/2$ and computes $c = F_k(r||m)$. Show how to decrypt, and prove that this scheme is CPA-secure for messages of length $n/2$.

I see the decryption could be $d = F_k^{-1}(c) = r||m \Rightarrow r_0r_1 ... r_{n/2-1} m_0m_1 ... m_{n/2-1}$, assuming $n$ is even the receiver knows that he must extract $m$ from the first exact half (from right to left) in the ciphertext sequence. As for the CPA-security, I notice that $F_k$ is non deterministic because of $r$, so for a message $m$ the 2 ciphertexts $c = F_k(r||m)$ and $c' = F_k(r'||m)$ are different if $r \neq r'$. Let $q(n)$ be a polynomial number of oracle queries, then $r = r'$ with probability $$\frac{q(n)}{2^{n/2}}$$ which should be negligible.
Is that correct? And should I say something about the security parameter $n$? I feel I'm missing something here.

• You appear to be missing the "prove that this scheme is CPA-secure for ..." part. $\;$
– user991
Jul 27, 2015 at 12:10
• You implicitly consider an adversary which follows some specific strategy. You must show that the probability is negligible for all polynomial-time adversaries. Namely, you must show that the existence of a polynomial-time adversary which succeeds in breaking CPA-security would contradict the assumed pseudorandomness of $F$. Jul 27, 2015 at 12:12
• @fkraiem so I should first define the CPA indistinguishability game (IND-CPA) considering 2 cases: this encryption scheme (A); and the encryption scheme (B) exactly the same as A, except that it uses $f \leftarrow Func_n$ instead of $F_k$. Then reducing it (the IND_CPA game) to the distinguishing between $F_k$ and f level ? Jul 27, 2015 at 12:41
• No, you first assume that there is some adversary $A$ which succeeds in breaking the CPA-security, and then you construct an algorithm $D$ which can distinguish $F_k$ from a uniformly chosen pemutation. Your algorithm $D$ will use $A$ as a subroutine (i.e., it will call $A$ on some appropriate inputs, and will use $A$'s answer as a hint to help it distinguish $F_k$ from a uniform permutation). Jul 27, 2015 at 12:43
• No, the proof is by contradiction: you show that $D$ does succeed in distinguishing $F_k$ from a random permutation. This is a contradiction because $F_k$ is pseudorandom, and hence $A$ cannot exist. Jul 27, 2015 at 12:56

You're close. As Mikero noted in the comments, this scheme is CCA-secure as proven in his book.

The proof strategy that seems easiest here is to do game-hops and with the IND\$-CPA definition:

• Start with the real case where $$c=F_K(r\mathbin\|m)$$ is returned
• Swap out $$F_K(\cdot)$$ for a random permutation $$\pi$$, so $$c=\pi(r\mathbin\|m)$$ is returned, you "lose" the PRP advantage on your bound here
• Swap out $$\pi$$ for a random function $$f$$ using the PRP-PRF-switching lemma, so $$c=f(r\mathbin\|m)$$ is returned, you lose the PRP-PRF bound here (additively)
• Swap out $$f$$ for the function that instead drops its input and instead returns a fresh random value, you additively lose the probability you named because only if $$r$$'s (and $$m$$'s) repeat there's a chance that you can distinguish this from the previous game, $$c\gets \{0,1\}^n$$
• Now you always return a random value as the ciphertext, independent of the input message, therefore it cannot convey any information about it, you're done

Is that correct?

The basic idea is there, it just needs to be spelled out a bit more explicitly.