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^[1].

Formellement, une fonction pseudo-aléatoire est une fonction ${\mathcal {F}}:{\mathcal {K}}\times {\mathcal {X}}\to {\mathcal {Y}}$ , où ${\mathcal {K}}$ représente l'espace des clefs, ${\mathcal {X}}$ représente le domaine de la fonction et ${\mathcal {Y}}$ 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 ${\mathcal {F}}(k,\cdot )$ de la sortie d'une fonction aléatoire sur le même domaine, conditionnée sur le choix de la clef $k\in {\mathcal {K}}$ ^[1].

Construction

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^[2], et il est possible de construire une fonction pseudo-aléatoire à partir d'un générateur pseudo-aléatoire^[1].

Applications

Chiffrement sémantiquement sûr

L'existence d'une fonction pseudo-aléatoire ${\mathcal {F}}$ rend possible la conception d'un schéma de chiffrement symétrique sémantiquement sûr par la construction qui suit^[1]. 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 ${\mathcal {F}}$ ).

Génération de la clef: Une clef $k\gets _{\$}{\mathcal {K}}$ est générée aléatoirement dans l'espace des clefs de la PRF.
Chiffrer: Pour chiffrer un message $m$ $m$ sous la clef $k$ $k$ , on calcule le message chiffré de la manière suivante:
- Tirer un aléa $r\gets _{\$}{\mathcal {X}}$ .
- Renvoyer le message chiffré: $C=(r,F(k,r)\oplus m)$ , où $\oplus$ représente le ou exclusif bit à bit.
Déchiffrer: Pour déchiffrer un message $C=(c_{1},c_{2})$ avec la clef $k$ , on calcule: $m'=F(k,c_{1})\oplus c_{2}$ .

La correction se vérifie par le fait que $\oplus$ est involutif.

La sécurité s'obtient par réduction polynomiale depuis la sécurité du chiffrement pseudo-aléatoire. En d'autres termes, si un adversaire était capable de distinguer entre le schéma présenté ci-dessus et une chaîne aléatoire, alors on pourrait directement l'utiliser pour distinguer entre un message construit à l'aide d'une fonction pseudo-aléatoire d'une vraie fonction aléatoire, auquel cas le chiffré $(c_{1},c_{2})$ serait distribué uniformément sur l'espace des chiffrés (le ou exclusif d'une constante (ici un message)par une fonction uniforme est distribué comme une fonction uniforme).

v · m Sécurité prouvable en cryptologie
Modèles de sécurité	Modèle standard Modèle de l'oracle aléatoire (ROM) Modèle du groupe générique (GGM) Modèle du groupe algébrique (AGM) Modèle du chiffre idéal (ICM) Modèle de l'action de groupe à sens unique (OWGA) Transfert inconscient (OT) Fonction à perte extrême (ELF) Fonction pseudo-aléatoire (PRF) Permutation pseudo-aléatoire (PRP) Générateur pseudo-aléatoire (PRG) Groupe bilinéaire Application multilinéaire Modèle de la chaîne de référence commune (CRS) Fonction à sens unique (OWF) Fonction à trappe (TDF) Obfuscation indistinguable (iO) Composabilité universelle (UC)
Outils et techniques de preuve	Réduction Séparation Avantage Argument hybride Distance statistique Coefficient H Simulation Forking lemma Leftover hash lemma Lemme de Schwartz-Zippel Théorème de Luby-Rackoff Théorème des anniversaires Heuristique de Fiat-Shamir
Hypothèses calculatoires	Factorisation Problème RSA Problème RSA fort Problème du logarithme discret Problème de Diffie-Hellman (CDH et DDH) Problème de la résiduosité quadratique Problème de la résiduosité supérieure Navigation dans un graphe expanseur Problème LWE Problème NTRU Problèmes de réseau (SVP, CVP, SIS, SIVP)
Propriétés de sécurité	IND (indistingabilité) EF (forge existentielle) NM (non malléabilité) Résistance aux collisions (CR) CPR (résistance aux collisions à préfixe choisi) PIR (résistance aux préimages) SPIR (résistance aux secondes préimages) Divulgation nulle de connaissance (ZK)
Modèles d'attaques	Attaque sans message (NMA) Clairs/messages choisis (CPA/CMA) Chiffrés choisis (CCA) Chiffrés choisis de façon adaptative (CCA2) Attaque par sondes (ISW)

Fonction pseudo-aléatoire

Construction

Applications

Chiffrement sémantiquement sûr

Notes et références

Bibliographie

Related Articles