The following encryption scheme: choose a random string $r \leftarrow \{0,1\}^n$ and compute the ciphertext $c= \thinspace <c_0, c_1>= \thinspace <r, F_k(r) \oplus m>$, assuming $F$ a PRF; is CPA-secure, as we have a randomized/non-deterministic encryption process. Why, if applying a modified encryption process, i.e. computing the ciphertext $c'= \thinspace <c_0, c_1'>= \thinspace <r, F_r(k) \oplus m>$, this is no more CPA-secure? I mean, this modified encryption process is also non-deterministic. Could it be because on each encryption invocation the input to the PRF $F$ is the fixed value $k$? I'm not sure if this makes sense.


1 Answer 1


Ask a CPA-query with a known $m$ and get back $c_0,c_1'$. Compute $c_1'' = c_1' \oplus m$. Then, compute $F^{-1}_r(c_1'')$ and this will be $k$. Now you know the key.

Of course, this attack assumes that you can invert $F$, but nothing in the definition says you cannot (and in practice you often can).

  • $\begingroup$ Hmm ok, but what if $F$ is a PRF and not a PRP? $\endgroup$
    – pa5h1nh0
    Commented Sep 17, 2015 at 18:20
  • 1
    $\begingroup$ You need to prove some pseudorandom properties but you won't be able to... $\endgroup$ Commented Sep 17, 2015 at 18:36
  • $\begingroup$ @pa5h1nh0, are you looking for the pseudo random generator? $\endgroup$
    – SEJPM
    Commented Sep 17, 2015 at 19:39
  • $\begingroup$ @SEJPM ahm nope, PRF, as I explicitly stated it in the question. $\endgroup$
    – pa5h1nh0
    Commented Sep 17, 2015 at 19:42

Your Answer

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

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