Modèle de l'oracle aléatoire

En cryptologie, le modèle de l'oracle aléatoire^{[Note 1]} est un cadre théorique idéalisé dans lequel on peut prouver la sécurité de certains algorithmes cryptographiques, en particulier les signatures numériques. Il postule l'existence d'un oracle, c'est-à-dire d'une boîte noire, qu'un adversaire peut interroger et qui fournit une réponse « aléatoire », dans un sens précisé plus bas. Ce modèle essaie de capturer le comportement idéal d'une fonction de hachage cryptographique.

Le modèle de l'oracle aléatoire a été introduit en 1993 par les cryptologues Mihir Bellare et Phillip Rogaway^[1].

Un des intérêts du modèle de l'oracle aléatoire est qu'il permet de construire des preuves de sécurité pour les algorithmes utilisant des fonctions de hachage, sans avoir besoin de rentrer dans les détails d'implémentation de ces dernières. Toutefois, on sait qu'il existe des algorithmes prouvés sûrs dans le modèle de l'oracle aléatoire, qui sont complètement cassés si on remplace l'oracle par n'importe quelle fonction de hachage réelle^[2], ce qui a initialement causé des doutes quant à la pertinence des preuves dans ce modèle^{[3],[4],[5],[6],[7],[8]}. Pire, il n'est possible de prouver la sécurité de certains algorithmes, tel que FDH, que dans le modèle de l'oracle aléatoire^[9].

Si les preuves dans le modèle standard restent préférables, les réticences face au modèle de l'oracle aléatoire sont aujourd'hui modérées^[3],[10]. Qui plus est, des modèles a priori différents tels que le modèle du chiffre idéal se sont en fait avérés équivalents au modèle de l'oracle aléatoire^[11]. Pour ces raisons une preuve dans le modèle de l'oracle aléatoire a surtout une valeur heuristique^{[3],[Note 2]}.

Exemples importants

• La sécurité du schéma de signature de Schnorr et de celui d'ElGamal ont été réduites à la difficulté du logarithme discret dans le modèle de l'oracle aléatoire^[12]. Il est cependant vraisemblable qu'une preuve sans l'oracle aléatoire est hors d'atteinte^[13],[14].
• La sécurité du chiffrement RSA avec OAEP^[15] comme avec PSS (en)^[16] est réduite à la difficulté du problème RSA dans le modèle de l'oracle aléatoire.
• La sécurité de la signature Full Domain Hash est réduite à la difficulté du problème RSA dans le modèle de l'oracle aléatoire^[1]. Cependant on sait qu'il n'existe de preuve que dans ce modèle^[9].
• La sécurité du chiffrement basé sur l'identité de Boneh-Franklin est réduite à une variante du problème de Diffie-Hellman calculatoire dans le modèle de l'oracle aléatoire^[17].

Définition

Dans le modèle de l'oracle aléatoire, les participants ont accès à un oracle ${\displaystyle {\mathcal {O}}}$ qui répond à un nombre polynomial de requêtes de la manière suivante :

• Pour une requête ${\displaystyle q}$ jamais formulée auparavant, l'oracle répond une chaîne de bits ${\displaystyle s_{q}\in \{0,1\}^{n}}$ choisie uniformément au hasard.
• Pour une requête ${\displaystyle q}$ déjà reçue, l'oracle renvoie ${\displaystyle s_{q}}$.

Comme souvent en informatique théorique, la notion de choix aléatoire peut se formaliser au moyen d'une « bande aléatoire^{[Note 3]} » ${\displaystyle \omega }$. La capacité pour le cryptologue de rembobiner cette bande est au cœur de nombreuses preuves de sécurité dans ce modèle, au moyen du forking lemma^[12].

Dans la mesure où ${\displaystyle s_{q}}$ est choisi de manière qui ne peut être distinguée d'un véritable choix uniforme, il est possible de le générer d'une manière inconnue de l'adversaire. Ce modèle, dit « de l'oracle aléatoire programmable » permet de contraindre l'adversaire dans une preuve par réduction à casser une hypothèse calculatoire.

Voir aussi

• Modèle du chiffre idéal
• Modèle du groupe générique