Modèle de l'oracle aléatoire

• 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].

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.

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