In proof of CPA-security of encryption scheme $(r, F_k(r)\oplus m )$ where:

The value $r^*$ is used when answering at least one of A’s encryption oracle queries: In this case, A may easily determine whether $m_0$ or $m_1$ was encrypted. This is so because if the encryption oracle ever returns a ciphertext $\langle r^*,s \rangle$, si in response to a request to encrypt the message $m$, the adversary learns that $f(r^*) = s\oplus m.$

  • My question is how can the adversary use $f(r^*)$?
  • Haven't we assume that the adversary doesn't know about $f$?

What I understand is that if we have used the keyed function $F_k$, then since the adversary doesn't know $k$, the knowledge of $F_k(r^*)$ can't be used because s/he still needs lots of time, that is $2^{|k|}$, to check which function $F_k$ where used. So it seems to me using the encryption scheme is secure even we repeat the random number $r$.

It seems that I am missing something but I can't find it.

  • 1
    $\begingroup$ Hint: imagine you are the adversary playing the IND-CPA game. Assume that in step 4 the challenger reuses one of the $r_i$ used in step 2. How do you play to detect that, detect which $r_i$ was reused, and win the game with certainty? $\endgroup$
    – fgrieu
    Sep 30 '20 at 8:19
  • 1
    $\begingroup$ @fgrieu Thanks. Although I didn't like to think like an adversary when I think like her/him I understand that the whole point isn't to find the $F_k$ function. It seems if $r$ repeats, then he can *distinguishes$ between two messages. $\endgroup$
    – Doralisa
    Sep 30 '20 at 10:41

Thanks to @fgrieu I've got the point I've missed. The point is the adversary doesn't want to find the keyed function, of course, s/he would be happy if knew it, but s/he wants information and wins some game.

So Let's think like an adversary and we have asked $z$ queries $m_1, \cdots, m_z$ and got $\langle r_1, F_k(r_1)\oplus m_1\rangle, \cdots , \langle r_z, F_k(r_z)\oplus m_z\rangle$. We can have the following information from the queries' answers.

$F_k(r_1) = F_k(r_1) \oplus m_1 \oplus m_1$


$F_k(r_z) = F_k(r_z) \oplus m_z \oplus m_z$

Then we choose $m'$ and $m''$ and get one more ciphertext $F_k(r')\oplus m_b$. If random number r repeats, for example r'= r_i, then we can do the following computation

$F_k(r_i)\oplus m_i \oplus m_i \oplus F_k(r') \oplus m_b = m_b$

And we exactly know which message was encrypted just by checking whether $m_b = m'$ or $m_b=m''$.

Even the adversary still doesn't know the $F_k$ we used he win CPA-game.


Look at page 47 at "A Graduate Course in Applied Cryptography" (there they also show a Attack Game)


$PRG_{adv}[A,G]:= |Pr[W_0] - Pr[W_1] |$

(Illustrated in Fig. 3.1 as in the book)

"Attack Game 3.1 can be recast as a “bit guessing” game"

  • $\begingroup$ Or I maybe misunderstood the question, sorry -if I did , please say that. "What is advantage of adversary if the random number repeats?" - You can change the game (in the book I provided) slightly so that they use repeating numbers (As fgrieu wrote in a comment) $\endgroup$ Sep 30 '20 at 8:35
  • $\begingroup$ & I'm sorry again; I'm a bit new, (to this site, overall) So I haven't got used to the symbol-formattings. $\endgroup$ Sep 30 '20 at 8:42
  • 2
    $\begingroup$ There is no need to be sorry at all. Your answer provides some new information to me about the definition of advantage of adversary and new games though doesn't exactly answered it. Thanks. $\endgroup$
    – Doralisa
    Sep 30 '20 at 11:01
  • $\begingroup$ @Doralisa Oh, Okay thanks so much; Have a great day, & good luck :) (Just wanted to say this) $\endgroup$ Sep 30 '20 at 12:52

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.