Hypothèses de difficulté calculatoire

Les hypothèses de difficulté calculatoire sont des conjectures non prouvées mais bien étudiées — telles que la difficulté de la factorisation, des logarithmes discrets et des problèmes de réseaux (lattices) — sur lesquelles repose en fin de compte la sécurité des schémas cryptographiques.

Definition

Une hypothèse de difficulté calculatoire est une conjecture selon laquelle un problème calculatoire particulier ne peut pas être résolu efficacement (en temps polynomial) par un adversaire réaliste, servant de fondement sur lequel la sécurité prouvable est construite.

Scope

Ce sujet aborde les hypothèses sur lesquelles repose la cryptographie : l'existence de fonctions à sens unique, les problèmes de théorie des nombres (factorisation, RSA, logarithme discret), et les problèmes de réseaux (lattices) et de codes utilisés en cryptographie post-quantique. Il traite de la hiérarchie entre les hypothèses, de la distinction entre la difficulté dans le pire des cas et la difficulté en moyenne, et de la manière dont les hypothèses sont examinées. Il exclut les mécanismes de réduction qui relient les hypothèses aux schémas et les définitions de sécurité elles-mêmes, traités dans des sujets connexes.

Core questions

• Pourquoi la sécurité cryptographique doit-elle reposer sur des hypothèses de difficulté non prouvées ?
• Quelles sont les principales hypothèses (fonctions à sens unique, factorisation, logarithme discret, réseaux (lattices)) ?
• Comment les hypothèses se rapportent-elles les unes aux autres en termes de force ?
• Quelle est la différence entre la difficulté dans le pire des cas et la difficulté en moyenne ?
• Comment les problèmes difficiles candidats sont-ils examinés, et que se passe-t-il lorsqu'un d'entre eux est compromis ?

Key concepts

• fonction à sens unique
• fonction à trappe
• hypothèse de factorisation des entiers
• hypothèse du logarithme discret
• hypothèses RSA et Diffie-Hellman
• apprentissage avec erreurs (LWE)
• difficulté dans le pire des cas vs difficulté en moyenne
• P versus NP
• hiérarchie des hypothèses

Key theories

Les fonctions à sens unique comme hypothèse minimale

L'existence de fonctions à sens unique — faciles à calculer, difficiles à inverser — est nécessaire et suffisante pour une grande partie de la cryptographie symétrique et constitue l'hypothèse la plus fondamentale ; presque toute la cryptographie présuppose au moins cela.

Hypothèses de théorie des nombres et de réseaux (lattices)

La cryptographie à clé publique repose sur des problèmes structurés — la factorisation des entiers, le problème RSA et les logarithmes discrets (classiquement), ainsi que les problèmes d'apprentissage avec erreurs (learning-with-errors) et de vecteurs les plus courts dans les réseaux (lattices) (post-quantique) — chacun étant étayé par des décennies d'examen cryptanalytique.

Mechanisms

La cryptographie nécessite des problèmes difficiles en moyenne (sur des instances aléatoires), et pas seulement dans le pire des cas, étant donné que les clés sont choisies aléatoirement. Les hypothèses sont organisées selon une hiérarchie approximative : une rupture d'une hypothèse plus faible (par exemple, la factorisation) compromet souvent les schémas qui en dépendent, tandis que les réductions relient les hypothèses entre elles. Les hypothèses de réseaux (lattices) sont remarquables pour leurs réductions du pire des cas à la moyenne, ce qui confère une confiance accrue. La confiance en une hypothèse quelconque provient d'efforts cryptanalytiques soutenus et infructueux plutôt que d'une preuve formelle.

Clinical relevance

Les hypothèses de difficulté déterminent ce qui est sûr ou non à déployer. La découverte que les ordinateurs quantiques pourraient casser la factorisation et les logarithmes discrets (via l'algorithme de Shor) a invalidé les hypothèses sous-jacentes à RSA et à la cryptographie à courbe elliptique face aux adversaires quantiques, conduisant directement à l'adoption de standards post-quantiques basés sur les réseaux (lattices). Choisir des schémas basés sur des hypothèses bien étudiées et suivre leur statut est essentiel pour la sécurité à long terme.

Evidence & guidelines

Les organismes de normalisation privilégient les hypothèses ayant de longs antécédents cryptanalytiques ; le processus post-quantique du NIST a explicitement évalué la maturité et la confiance des hypothèses sous-jacentes concernant les réseaux (lattices), les codes et les fonctions de hachage. Les bonnes pratiques évitent les hypothèses exotiques ou nouvellement proposées pour les systèmes à haute assurance et préfèrent les problèmes conservateurs, bien examinés, avec des tailles de clé définies en fonction des meilleures attaques connues.

History

La dépendance à la difficulté est apparue avec la cryptographie à clé publique en 1976, lorsque Diffie et Hellman ont lié la sécurité au logarithme discret, et RSA à la factorisation. Les années 1980 ont formalisé les fonctions à sens unique et la distinction entre le pire des cas et le cas moyen. Les réductions du pire des cas à la moyenne d'Ajtai (1996) et le problème d'apprentissage avec erreurs (learning-with-errors) de Regev (2005) ont établi les hypothèses de réseaux (lattices), qui ont gagné en importance en tant que fondements résistants aux attaques quantiques et sous-tendent les nouveaux standards post-quantiques.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

Pourquoi ne pouvons-nous pas simplement prouver que ces problèmes sont difficiles ?

Prouver qu'un problème nécessite un temps super-polynomial résoudrait de profondes questions ouvertes en théorie de la complexité (notamment P versus NP), qui restent sans solution. La cryptographie repose donc sur des hypothèses dont la plausibilité découle de décennies de tentatives infructueuses pour les résoudre efficacement.

Que se passe-t-il si une hypothèse de difficulté est compromise ?

Chaque schéma dont la sécurité se réduit à cette hypothèse devient potentiellement non sécurisé et doit être remplacé. C'est pourquoi la menace quantique pour la factorisation et les logarithmes discrets a provoqué une migration mondiale vers des schémas basés sur des hypothèses différentes, résistantes aux attaques quantiques.