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.

  • $\begingroup$ You appear to be missing the "prove that this scheme is CPA-secure for ..." part. $\;$ $\endgroup$
    – user991
    Jul 27 '15 at 12:10
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fkraiem
    Jul 27 '15 at 12:12
  • $\begingroup$ @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 ? $\endgroup$
    – pa5h1nh0
    Jul 27 '15 at 12:41
  • 1
    $\begingroup$ 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). $\endgroup$
    – fkraiem
    Jul 27 '15 at 12:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – fkraiem
    Jul 27 '15 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.