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

Câu trả lời đơn giản là, cả hai bổ đề đều đúng và bổ đề thứ nhất bao hàm bổ đề thứ hai một cách tầm thường. Điều này xảy ra đơn giản vì đối với bất kỳ $q\in\mathbb{N}$, $q(q-1) = q^2-q \leq q^2$.

Tại sao sau đó làm cả hai phiên bản tồn tại? Cái đầu tiên cho giới hạn trên chặt chẽ hơn, nếu bạn quan tâm nhiều đến độ kín của giới hạn cụ thể trong bất kỳ bằng chứng nào bạn đang sử dụng, thì hãy sử dụng cái đó. Nếu độ chặt của bê tông không quan trọng bằng thì bạn cũng có thể sử dụng cái nới lỏng hơn vì nó viết nhanh hơn và dễ đọc hơn.

Chứng minh tương ứng (Trang 150) không giải thích tại sao số lượng các cặp va chạm là $\frac{q^2}{2}$ thay vì $\frac{q(q-1)}{2}$ khi có $q$ truy vấn.

Nó không nói rằng có $q^2/2$ cặp như vậy ở tất cả. Những gì nó nói là

có ít hơn $Q^2/2$ cặp như vậy

đó là sự thật, cho rằng có $Q(Q-1)/2 \leq Q^2/2$ nhiều cặp.

Làm thế nào để chứng minh điều đó?

Chà, bằng chứng có trong sách, nhưng nếu bạn thấy bằng chứng của Bellare và Rogaway dễ theo dõi hơn, thì bạn có thể chỉ cần sử dụng bằng chứng đó vì nó chứng tỏ một cận trên mạnh hơn nghiêm ngặt.