Lemme de commutation PRP/PRF
Le résultat qui permet à une preuve de traiter un chiffrement par blocs comme une fonction aléatoire, à un coût qui croît comme le carré du nombre de requêtes.
Un chiffrement par blocs est une permutation : deux entrées distinctes ne donnent jamais la même sortie. Bien des preuves de sécurité pour des modes comme CTR sont plus simples si on le traite plutôt comme une fonction aléatoire, où les collisions sont permises. Le lemme dit qu'aucun adversaire faisant q requêtes ne peut distinguer les deux avec un avantage supérieur à environ q²/2n+1, pour une taille de bloc n.
C'est de là que vient la borne des anniversaires de presque toutes les preuves de modes de chiffrement par blocs. Le lemme paraît si évident que sa preuve de manuel a été citée des années sans examen, jusqu'à ce que Bellare et Rogaway signalent en 2004 qu'elle était fausse et en fassent la vitrine de leur technique de preuve par jeux. La conclusion tenait. La preuve, non.