PRP/PRF切換引理的不同界限
PRP/PRF 切換引理通常表示如下：
我理解這個版本的證明 $ \frac{q(q-1)}{2^{n+1}} $ 以及它背後的遊戲技巧。
然而，我最近遇到了這個引理的不同版本，它在論文中更常用。表示如下：
這個版本的界限原來是 $ \frac{q^{2}}{2^{n+1}} $ （或類似的東西）。相應的證明（第150頁）沒有解釋為什麼碰撞對的數量是 $ \frac{q^{2}}{2} $ 代替 $ \frac{q(q-1)}{2} $ 當有 $ q $ 查詢。
所以我的問題是：
為什麼界限是 $ \frac{q^{2}}{2^{n+1}} $ 代替 $ \frac{q(q-1)}{2^{n+1}} $ 在這個切換引理的後一個版本中？如何證明？謝謝！
簡單的答案是，兩個引理都是正確的，第一個引理微不足道地暗示了第二個引理。這僅僅是因為對於任何 $ q\in\mathbb{N} $ , $ q(q-1) = q^2-q \leq q^2 $ .
那為什麼兩個版本都存在呢？第一個給出了更嚴格的上限，如果您在使用它的任何證明中都非常關心具體邊界的緊密性，那麼請使用那個。如果具體的鬆緊度不那麼重要，你也可以使用鬆散的，因為它寫起來更快，更容易閱讀。
相應的證明（第150頁）沒有解釋為什麼碰撞對的數量是 $ \frac{q^2}{2} $ 代替 $ \frac{q(q-1)}{2} $ 當有 $ q $ 查詢。
它沒有說有 $ q^2/2 $ 這樣的對。它說的是
少於_ $ Q^2/2 $ 這樣的對
這是真的，因為有 $ Q(Q-1)/2 \leq Q^2/2 $ 很多對。
如何證明？
好吧，證明在書中，但是如果您發現 Bellare 和 Rogaway 的證明更容易理解，那麼您可以簡單地使用該證明，因為它證明了嚴格更強的上限。