1
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ Read it as number of messages $e$ times number of message blocks $e\cdot s$. Note that the initial counter is chosen randomly. $\endgroup$ – Squeamish Ossifrage Feb 21 at 18:57
  • $\begingroup$ @SqueamishOssifrage is a good way to see it, but how do I deduce the inequality from the given fact? $\endgroup$ – Javier Feb 22 at 23:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – Samuel Neves Feb 23 at 13:24
  • $\begingroup$ @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! $\endgroup$ – Javier Feb 23 at 23:43
1
$\begingroup$

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)}}\,.$$

$\endgroup$

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.