I have an issue with this proof. We define two games:

$$H'(\lambda):$$ 1) Pick $R \in \mathcal{R}(n,l)$ (the space of truly random functions from $\{0,1\}^n$ to $\{0,1\}^l$

2) we define $\mathit{Enc}'_k(m)=(r,R(r) \oplus m)$, where $r$ is random from $\{0,1\}^n$.

3)$\mathcal{A}$ is an adversary who chooses two messages from $\{0,1\}^l$

4) A single bit is choosen randomly by a challenger $\mathcal{C}$, and the message $m_b$ is encrypted

5)Receiving the message $m_b$ adversary must guess what message was encrypted. It is the CPA-game and so we assume that $\mathcal{A}$ have access to the encryption oracle.

The other game is $H''(\lambda)$ defined as before but

$\mathit{Enc}_k''(m)=(r_1,r_2)$ where $r_1,r_2$ taken randomly from $\{0,1\}^{n}$ and $\{0,1\}^l$

I know that the difference between them is the second part of the Encryption algorithm, but I don't understand why in $H'$ game there are collision problem. The proof tells that calling $E(\mathit{bad})$ the problem of collisions in encryption queries, it sufficies to prove that $E[\mathrm{BAD}]$ have negligable probability and so

$$\Pr[E(\mathrm{BAD})]= \sum_{i,j} \Pr[r_i=r_j] \leq (q^2) 2^{-n}$$

Why in the first scheme there are collision problems and why if there are collision problems the two schemes can be distinguishable?


If there is a collision in the $r$ in the first game, then the attacker can learn the XOR of two plaintext messages by XORing the second elements. In the second game, the XOR of the two second elements if there is a collision will just be random. Thus, the attacker can distinguish these two games if there is a collision.

  • $\begingroup$ Yeah, but so the bad event should not be that $r_i=r_j$, but $R(r_i) = R(r_j) $ or do I go wrong?? $\endgroup$ – Jessica Bonanni Jan 1 '18 at 21:19
  • $\begingroup$ Since R is a FUNCTION, it follows that ri = rj implies R(ri) = R(rj). In addition, although R can also invoke collisions, the adversary has no way of knowing if this happened. In contrast, the adversary can see if ri=rj. $\endgroup$ – Yehuda Lindell Jan 2 '18 at 6:24

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.