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.

  • 1
    $\begingroup$ I've quickly edited your question to make consistent use of SE's MathJax formatting and I've put the exercise in question into quotes so everyone directly sees that this is the exercise and below are your attempts. If you don't like my edits you can either edit again or roll them back by clicking on the "edited ... ago". $\endgroup$ – SEJPM Jul 27 '15 at 12:09
  • $\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
  • 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

Your Answer

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

Browse other questions tagged or ask your own question.