PRP/PRF切替補題

ブロック暗号は置換であり、異なる2つの入力が同じ出力に写ることはない。CTRなどの暗号利用モードの安全性証明は、暗号を衝突が許されるランダム関数として扱うほうが楽になることが多い。この補題は、q回のクエリを行う攻撃者が両者を区別できる優位性は、ブロック長をnビットとしておよそq²/2ⁿ⁺¹以下だと述べる。

ほぼすべてのブロック暗号モードの証明に現れる誕生日バウンドは、ここに由来する。補題はあまりに自明に見えたため、教科書の証明は長年精査されずに引用された。2004年にベラーレとロガウェイがその証明が誤りであると指摘し、ゲームベースの証明技法の見本として使った。結論は正しく、間違っていたのは証明のほうだった。