4
$\begingroup$

The PRP/PRF switching lemma is usually denoted as follows: enter image description here

I understand the proof of this version of the bound $\frac{q(q-1)}{2^{n+1}}$ and the game-playing technique behind it.

However, I came across a different version of this lemma recently, which is used more often in papers. It is denoted as follows: enter image description here

This version of the bound turns out to be $\frac{q^{2}}{2^{n+1}}$ (or something like this). The corresponding proof (Page 150) does not explain why the number of collision pairs is $\frac{q^{2}}{2}$ instead of $\frac{q(q-1)}{2}$ when there are $q$ queries.

So my question is:

Why the bound is $\frac{q^{2}}{2^{n+1}}$ instead of $\frac{q(q-1)}{2^{n+1}}$ in the latter version of this switching lemma ? How to prove it ? Thanks!

$\endgroup$
4
  • 3
    $\begingroup$ Since $q^2 \geq q(q-1)$ for $q\in\mathbb{N}$ the first version implies the latter. $\endgroup$
    – Maeher
    Feb 7, 2022 at 13:43
  • $\begingroup$ Thanks, kelalaka and Maehar. I once had the same thought with you. That is "Is the latter bound derived from the former just for the convenience of calculation?". However, I can't find any support for this idea. No papers or books ever discuss the relationship between these two bounds, they just pick one of them but never mention another. So I want to know if there is a deeper relationship between the two other than inequality scaling. $\endgroup$
    – Max1z
    Feb 7, 2022 at 14:30
  • 2
    $\begingroup$ There is no deeper relationship. $q(q-1)$ is a tighter bound that trivially implies the looser bound $q^2$. If you care about the tightness of your bounds use the tighter one. If you don't it's more convenient to just use $q^2$. $\endgroup$
    – Maeher
    Feb 7, 2022 at 15:25
  • $\begingroup$ Thank you @Maeher ! If there is no deeper relationship, then my question is resolved. It would be better if there are any reference that mention this. $\endgroup$
    – Max1z
    Feb 8, 2022 at 3:05

1 Answer 1

4
$\begingroup$

The simple answer is, both lemmas are correct and the first one trivially implies the second one. This follows simply because for any $q\in\mathbb{N}$, $q(q-1) = q^2-q \leq q^2$.

Why then do both versions exist? The first one gives a tighter upper bound, if you care a lot about the tightness of the concrete bounds in whatever proof you are using it, then use that one. If the concrete tightness doesn't matter as much you can just as well use the looser because it is quicker to write and easier to read.

The corresponding proof (Page 150) does not explain why the number of collision pairs is $\frac{q^2}{2}$ instead of $\frac{q(q-1)}{2}$ when there are $q$ queries.

It doesn't state that there are $q^2/2$ such pairs at all. What it says is that

there are less than $Q^2/2$ such pairs

which is true, given that there are $Q(Q-1)/2 \leq Q^2/2$ many pairs.

How to prove it?

Well, the proof is in the book, but if you find the proof of Bellare and Rogaway easier to follow, then you can simply use that proof given that it proves a strictly stronger upper bound.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.