Fonction pseudo-aléatoire

Une fonction pseudo-aléatoire (ou PRF pour pseudorandom function) est une fonction dont l'ensemble des sorties possibles n'est pas efficacement distinguable des sorties d'une fonction aléatoire. Il ne faut pas confondre cette notion avec celle de générateur de nombres pseudo-aléatoires (PRNG). Une fonction qui est un PRNG garantit seulement qu'une de ses sorties prise seule semble aléatoire si son entrée a été choisie aléatoirement. En revanche, une fonction pseudo-aléatoire garantit cela pour toutes ses sorties, indépendamment de la méthode de choix de l'entrée. En cryptographie, ce genre de fonction est extrêmement important : il sert de brique de base à la conception de primitives cryptographiques, en particulier pour les algorithmes de chiffrement. Formellement, une fonction pseudo-aléatoire est une fonction , où représente l'espace des clefs, représente le domaine de la fonction et son image. La définition de sécurité associée, est donnée par le fait que n'importe quel adversaire polynomial est incapable de distinguer entre la sortie de de la sortie d'une fonction aléatoire sur le même domaine, conditionnée sur le choix de la clef . L'existence de fonctions à sens unique est suffisante pour construire des fonctions pseudo-aléatoire. En effet il est possible de construire un générateur pseudo-aléatoire (PRG) à partir de fonctions à sens unique, et il est possible de construire une fonction pseudo-aléatoire à partir d'un générateur pseudo-aléatoire. L'existence d'une fonction pseudo-aléatoire rend possible la conception d'un schéma de chiffrement symétrique sémantiquement sûr par la construction qui suit. Intuitivement, elle consiste à utiliser la sortie de la fonction pseudo-aléatoire comme une sortie uniforme pour l'utiliser comme masque jetable. L'avantage réside en le fait que la clef n'est ici plus aussi longue que le message, mais va dépendre de la clef utilisée et de la taille de l'aléa (qui est dépendante de l'entrée de la fonction pseudo-aléatoire ). Génération de la clef: Une clef est générée aléatoirement dans l'espace des clefs de la PRF.