Lemma di commutazione PRP/PRF
Il risultato che permette a una dimostrazione di trattare un cifrario a blocchi come una funzione casuale, a un costo che cresce con il quadrato del numero di query.
Un cifrario a blocchi è una permutazione: due ingressi distinti non producono mai la stessa uscita. Molte dimostrazioni di sicurezza per modalità come CTR sono più semplici se il cifrario è trattato invece come una funzione casuale, dove le collisioni sono ammesse. Il lemma afferma che nessun avversario che effettui q query può distinguere i due casi con un vantaggio maggiore di circa q²/2n+1, con n dimensione del blocco.
Da qui nasce il limite del compleanno presente in quasi ogni dimostrazione sulle modalità dei cifrari a blocchi. Il lemma sembrava così ovvio che la sua dimostrazione da manuale fu citata per anni senza verifiche, finché nel 2004 Bellare e Rogaway non osservarono che era errata e la usarono come esempio della loro tecnica di dimostrazione basata sui giochi. La conclusione reggeva. La dimostrazione no.