# Problem with a reduction using Hybrid Argument

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.
• 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?? – Jessica Bonanni Jan 1 '18 at 21:19