2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

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

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.