Score:4

Crypto

The different bounds of PRP/PRF switching lemma

Max1z

6/7/23, 11:08 AM

The PRP/PRF switching lemma is usually denoted as follows:

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:

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!

161

0 + 0

block-cipher

pseudo-random-function

pseudo-random-permutation

probability

Maeher

6/7/23, 1:43 PM

Since $q^2 \geq q(q-1)$ for $q\in\mathbb{N}$ the first version implies the latter.

Max1z

6/7/23, 2:30 PM

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.

Maeher

6/7/23, 3:25 PM

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

6/8/23, 3:05 AM

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

Crypto

Maeher

6/8/23, 12:17 PM

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.

0 + 0

kelalaka

6/8/23, 1:16 PM

Thanks for the converting,

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: The different bounds of PRP/PRF switching lemma

TH: ขอบเขตที่แตกต่างกันของบทแทรกการสลับ PRP/PRF

RO: Diferite limite ale lemei de comutare PRP/PRF

RU: Различные оценки леммы о переключении PRP/PRF

VI: Các giới hạn khác nhau của bổ đề chuyển mạch PRP/PRF

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.