PRP/PRF-växlingslemmat
Satsen som låter en bevisförare låtsas att ett blockchiffer är en slumpfunktion, mot ett pris som växer med antalet frågor i kvadrat.
Ett blockchiffer är en permutation: två olika indata ger aldrig samma utdata. Många säkerhetsbevis för driftlägen som CTR blir enklare om chiffret i stället behandlas som en slumpfunktion, där kollisioner är tillåtna. Lemmat säger att ingen angripare med q frågor kan skilja de två åt med större fördel än ungefär q²/2n+1 för blockstorlek n.
Därifrån kommer födelsedagsgränsen i nästan varje bevis för ett blockchifferläge. Lemmat är så självklart att standardbeviset länge citerades utan granskning, tills Bellare och Rogaway 2004 påpekade att det var felaktigt och använde det som skolexempel för sin spelbaserade bevisteknik. Slutsatsen höll. Beviset gjorde det inte.