PRP/PRF-switchinglemma
Het resultaat waarmee een bewijs kan doen alsof een blokcijfer een willekeurige functie is, tegen kosten die met het kwadraat van het aantal queries groeien.
Een blokcijfer is een permutatie: twee verschillende ingangen geven nooit dezelfde uitvoer. Veel beveiligingsbewijzen voor modi als CTR zijn eenvoudiger als het cijfer wordt behandeld als een willekeurige functie, waar botsingen wél mogen. Het lemma zegt dat geen enkele aanvaller met q queries beide met een voordeel groter dan ruwweg q²/2n+1 kan onderscheiden, bij blokgrootte n.
Daar komt de verjaardagsgrens uit bijna elk bewijs voor blokcijfermodi vandaan. Het lemma is zo vanzelfsprekend dat het gangbare bewijs jarenlang zonder toetsing werd aangehaald, tot Bellare en Rogaway in 2004 aanwezen dat het fout was en het gebruikten als paradepaardje voor hun spelgebaseerde bewijstechniek. De conclusie klopte. Het bewijs niet.