Loading AI tools
Modèle de sécurité cryptographique dans lequel les participants ont accès à une machine renvoyant des réponses uniformément aléatoires De Wikipédia, l'encyclopédie libre
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].
Dans le modèle de l'oracle aléatoire, les participants ont accès à un oracle qui répond à un nombre polynomial de requêtes de la manière suivante :
Comme souvent en informatique théorique, la notion de choix aléatoire peut se formaliser au moyen d'une « bande aléatoire[Note 3] » . 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ù 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.