# On the probability of a collision in RFO-rCTR

My slides show that assuming a polynomial number $$q(n)$$ of blocks have been encrypted by a random function oracle in the context of a CPA-game, the probability of having a collision in the input to the oracle is bounded by $$\frac{q(n)^2}{2^{l(n)}}$$ (cfr. Katz and Lidell, 2nd edition pages 93-94).

Then I am proposed the following: assuming that in total $$e(n)$$ messages are encrypted each consisting of at most $$s(n)$$ blocks then the probability of a collission in the input is bounded by $$\frac{e(n)^2s(n)}{2^{l(n)}}$$.

Is this a typo? Why are we dropping the square from $$s(n)$$?

Here you may see the slides I refer to (see slide 18 and 19)

• Read it as number of messages $e$ times number of message blocks $e\cdot s$. Note that the initial counter is chosen randomly. – Squeamish Ossifrage Feb 21 '19 at 18:57
• @SqueamishOssifrage is a good way to see it, but how do I deduce the inequality from the given fact? – Rodrigo Feb 22 '19 at 23:28
• Blocks within the same message never collide. So to determine the number of possible collisions you have a sum of the form $\sum_{i=1}^{e(n)} (i - 1) s(n) = s(n) {e(n) \choose 2} \le s(n) e(n)^2$. – Samuel Neves Feb 23 '19 at 13:24
• @SamuelNeves perfect! that is the answer. i see that it is reasonable to assume that blocks within the same message never collide, they could in principle, for instance in the rCTR mode if $s(n) > 2^{l(n)}$ but of course this is not the case in practice. You may want to post your comment as an answer! – Rodrigo Feb 23 '19 at 23:43

The key idea here is the blocks within the same message do not collide—message $$1$$ will have no possible block collisions, message $$2$$ can collide with the message $$1$$'s $$s(n)$$ blocks, message $$i$$ can collide with message $$i-1$$'s $$s(n)$$ blocks or message $$i-2$$'s $$s(n)$$ blocks, etc.
In other words, the number of possibly colliding block combinations is given by $$\sum_{i=1}^{e(n)} (i - 1)s(n)\,,$$ which simplifies to $$s(n) {e(n) \choose 2}$$. We turn this into a probability $$\frac{s(n){e(n) \choose 2}}{2^{l(n)}} \le \frac{s(n)e(n)^2}{2^{l(n)}}\,.$$