Score:4

The different bounds of PRP/PRF switching lemma

kr flag

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!

cn flag
Since $q^2 \geq q(q-1)$ for $q\in\mathbb{N}$ the first version implies the latter.
Max1z avatar
kr flag
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.
cn flag
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$.
Max1z avatar
kr flag
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.
Score:4
cn flag

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.

kelalaka avatar
in flag
Thanks for the converting,
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.