Lema de conmutación PRP/PRF
El resultado que permite a una demostración fingir que un cifrado por bloques es una función aleatoria, a un coste que crece con el cuadrado del número de consultas.
Un cifrado por bloques es una permutación: dos entradas distintas nunca dan la misma salida. Muchas pruebas de seguridad de modos como CTR son más sencillas si el cifrado se trata como una función aleatoria, donde las colisiones sí están permitidas. El lema dice que ningún adversario con q consultas puede distinguir ambos casos con una ventaja mayor que aproximadamente q²/2n+1 para un tamaño de bloque n.
De ahí sale la cota del cumpleaños que aparece en casi toda prueba de un modo de cifrado por bloques. El lema parece tan evidente que su demostración de manual se citó durante años sin revisarla, hasta que Bellare y Rogaway señalaron en 2004 que era incorrecta y la usaron como ejemplo estrella de su técnica de pruebas basadas en juegos. La conclusión se sostuvo. La demostración, no.