Sécurité prouvable et réductions

La sécurité prouvable démontre que casser un schéma cryptographique est au moins aussi difficile que de résoudre un problème réputé intraitable, en fournissant une réduction explicite du problème supposé difficile à toute attaque sur le schéma.

Definition

Une réduction de sécurité est une preuve qui transforme tout adversaire efficace brisant un schéma cryptographique en un algorithme efficace résolvant un problème supposé difficile, démontrant ainsi que le schéma est sécurisé à moins que ce problème ne soit facile.

Scope

Ce sujet couvre la méthodologie des preuves cryptographiques basée sur la réduction : la structure d'une réduction de sécurité, la justesse (tightness) et la sécurité concrète, les styles de preuve basés sur le jeu (game-based) et sur la simulation (simulation-based), les modèles de l'oracle aléatoire (random-oracle) et standard, ainsi que les limites et critiques de cette approche. Il aborde la manière dont les garanties de sécurité sont formulées et argumentées. Il exclut les hypothèses de difficulté spécifiques, ainsi que les définitions et les modèles d'adversaire, qui sont traités dans des sujets connexes.

Core questions

• Comment une réduction traduit-elle une attaque sur un schéma en une solution à un problème difficile ?
• Quelle est la différence entre les preuves basées sur le jeu et celles basées sur la simulation ?
• Que signifie la « justesse » d'une réduction pour les paramètres de sécurité du monde réel ?
• Que sont les modèles de l'oracle aléatoire et standard, et pourquoi le premier est-il controversé ?
• Quelles sont les limites et les pièges courants des arguments de sécurité prouvable ?

Key concepts

• réduction de sécurité
• preuves basées sur le jeu
• preuves basées sur la simulation
• réductions justes (tight) vs lâches (loose)
• sécurité concrète
• modèle de l'oracle aléatoire
• modèle standard
• avantage négligeable
• hypothèse de difficulté

Key theories

Méthodologie de preuve réductionniste

Pour prouver la sécurité d'un schéma, on suppose un adversaire qui le brise et on construit, en utilisant cet adversaire comme sous-routine, un algorithme qui résout le problème difficile sous-jacent — ainsi, une attaque réussie contredirait l'hypothèse de difficulté.

Le modèle de l'oracle aléatoire

De nombreux schémas efficaces sont prouvés sécurisés en idéalisant une fonction de hachage comme un oracle véritablement aléatoire ; le modèle permet des preuves pour des constructions pratiques mais est heuristique, car aucune fonction réelle n'est un oracle aléatoire.

Mechanisms

Dans une réduction, le prouveur (prover) suppose un adversaire hypothétique qui brise le schéma avec un avantage non négligeable et construit un enrobage (wrapper) qui intègre une instance du problème difficile dans la vue de l'adversaire, exécute l'adversaire et utilise sa sortie pour résoudre le problème. Les preuves basées sur le jeu (game-based proofs) procèdent à travers une séquence de jeux indiscernables, du schéma réel à un schéma où l'adversaire ne peut manifestement pas gagner. La justesse (tightness) de la réduction — c'est-à-dire la quantité d'avantage et de temps d'exécution perdus — détermine les tailles de clé nécessaires pour un niveau de sécurité cible.

Clinical relevance

La sécurité prouvable est la norme selon laquelle les schémas cryptographiques gagnent la confiance et la standardisation : les processus AES, SHA-3 et post-quantiques du NIST ont accordé une grande importance aux preuves de sécurité, et des protocoles comme TLS 1.3 ont été accompagnés d'analyses réductionnistes et vérifiées par machine. Comprendre les réductions permet aux praticiens de juger ce qu'une affirmation de sécurité garantit et ne garantit pas, et de choisir des paramètres qui tiennent compte de la justesse de la réduction.

Evidence & guidelines

La pratique moderne privilégie les preuves dans le modèle standard lorsque cela est faisable et considère les preuves dans le modèle de l'oracle aléatoire comme des preuves heuristiques solides plutôt que des garanties absolues. Les cadres assistés par outils (EasyCrypt, CryptoVerif) fournissent des preuves vérifiées par machine. L'analyse de sécurité concrète (exacte), qui quantifie l'avantage de l'adversaire en fonction des ressources, est préférée aux déclarations purement asymptotiques pour la définition des paramètres réels.

History

La méthodologie réductionniste a émergé avec la révolution définitionnelle du début des années 1980 et a été systématisée tout au long des années 1990. Bellare et Rogaway ont introduit le modèle de l'oracle aléatoire (1993) pour prouver la sécurité de schémas pratiques, puis l'analyse de « sécurité concrète » pour quantifier les garanties. Le résultat de Canetti, Goldreich et Halevi de 1998, montrant des schémas sécurisés dans le modèle de l'oracle aléatoire mais non sécurisés une fois instanciés, a aiguisé le débat sur les modèles idéalisés.

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

Une preuve de sécurité signifie-t-elle qu'un schéma ne peut jamais être brisé ?

Non. Une preuve montre que briser le schéma implique de résoudre un problème supposé difficile dans un modèle spécifié. Si l'hypothèse échoue, si le modèle est irréaliste ou si l'implémentation s'écarte du schéma analysé, des attaques restent possibles. Les preuves réduisent, mais n'éliminent pas, le risque.

Pourquoi le modèle de l'oracle aléatoire est-il considéré comme controversé ?

Il modélise une fonction de hachage comme une fonction parfaitement aléatoire, ce qu'aucune fonction concrète n'est réellement. Les preuves dans ce modèle constituent des preuves solides et permettent des schémas efficaces, mais il existe des schémas (artificiels) sécurisés dans le modèle mais non sécurisés une fois que l'oracle est remplacé par une fonction de hachage réelle, de sorte que de telles preuves sont heuristiques.