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 par Bennet et Gill en 1981 dans le cadre de l'étude du problème P ≟ NP^[1]. Ces derniers ont montré que les deux classes sont distinctes presque sûrement relatif à un oracle aléatoire.

En 1993, les cryptologues Mihir Bellare et Phillip Rogaway^[2] proposent d'utiliser le modèle de l'oracle aléatoire afin de construire des preuves de sécurité pour les algorithmes utilisant des fonctions de hachage, en remplaçant ces dernières par l'oracle. L'avantage est qu'il n'est pas nécessaire de considérer l'implementation de la fonction de hashage pour avoir une preuve de sécurité. 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^[3], ce qui a initialement causé des doutes quant à la pertinence des preuves dans ce modèle^{[4],[5],[6],[7],[8],[9]}. 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^[10].

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^[4],[11]. 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^[12]. Pour ces raisons une preuve dans le modèle de l'oracle aléatoire a surtout une valeur heuristique^{[4],[Note 2]}.