Hypothèse calculatoire
En cryptographie, une hypothèse de difficulté calculatoire est une hypothèse qui sert à évaluer et à démontrer la robustesse des primitives cryptographiques.
Dans certains cas, la sécurité est dite inconditionnelle si elle ne repose sur aucune hypothèse de difficulté calculatoire ; un exemple courant est la technique dite du masque jetable, où le masque est aussi grand que le message. Cependant, il est souvent impossible d'atteindre une forme de sécurité aussi forte[1] ; dans de tels cas, les cryptographes doivent s'en remettre à une forme de sécurité dite « calculatoire ». En première approximation, cela signifie que ces systèmes sont sûrs en supposant que tous les adversaires disposent d'une capacité de calcul limitée, comme tous les protagonistes en disposent en pratique.
Déterminer la difficulté de résolution d'un problème n’est pas une question facile, et le cryptosystème de Merkle-Hellman a supposé par exemple la difficulté du problème du sac à dos à poids super-croissant, qui s'est révélée vulnérable face à un algorithme glouton. L'évaluation de la difficulté des hypothèses calculatoires est étudiée par la cryptanalyse.
Quelques hypothèses classiques de difficulté cryptographique modifier
Il existe de nombreuses conjecture de difficulté cryptographiques. Si la difficulté de résolution du problème sous-jacent n'est pas connue pour de bon, on connaît certaines propriétés de difficultés de ces problèmes relativement à la difficulté de résolution d'autres de ces problèmes.
Lorsque l’on dit que la conjecture A est plus forte que la conjecture B, cela signifie que la résolution de B se réduit polynomialement à la résolution de A – ce qui signifie que si A est résoluble en temps polynomial, B l'est forcément aussi, mais que la réciproque n'est pas forcément vraie. Ainsi le problème A est plus difficile que le problème B, et donc si on suppose la difficulté de B, cela implique la difficulté de A.
Pour démontrer la robustesse des protocoles cryptographiques, on espère démontrer la difficulté de la plus faible de ces conjectures (car la difficulté des hypothèses plus fortes en suivrait).
Il est de plus important d’avoir plusieurs hypothèses de difficulté de base, puisque si un des problèmes de base venait à être résoluble facilement, cela n'affecte pas nécessairement la difficulté des autres hypothèses. On sait par exemple que le problème du logarithme discret et la factorisation sont résoluble en temps polynomial par un calculateur quantique via l'algorithme de Shor. Si de telles machines existaient, alors il faudrait utiliser de cryptosystèmes qui reposent sur d'autres hypothèses ; c'est ce qu'on appelle la cryptographie post-quantique.
Suit quelques hypothèses calculatoires récurrentes en cryptographie, et quelques exemples d'utilisation.
Factorisation d'entiers modifier
De nombreux cryptosystèmes reposent sur la difficulté de factoriser un nombre semi-premier . La raison est que cette hypothèse a permis, par l'introduction de l'hypothèse RSA qui est une hypothèse plus forte que la factorisation. En effet si on sait résoudre la factorisation, alors le problème RSA est facile à résoudre.
L'exemple le plus célèbre de l'utilisation de la factorisation est le cryptosystème RSA puisque c'est le premier cryptosystème à clef publique à avoir été introduit. Mais d'autres schémas cryptographiques se reposent sur la difficulté de la factorisation ou ses variantes, comme le cryptosystème de Rabin ou le générateur pseudo-aléatoire de Blum-Blum-Shub.
Mais l’hypothèse RSA et ses variantes n’est pas la seule hypothèse de difficulté ayant été proposée plus forte que la factorisation, on peut citer le problème de la résiduosité quadratique, sur lequel repose la sécurité du cryptosystème de Paillier, qui est un chiffrement homomorphe additif, ou encore sa généralisation le problème de la résiduosité supérieure dont la difficulté implique la sécurité du cryptosystème de Benaloh (en).
En 2017, le meilleur algorithme connu pour résoudre la factorisation est le crible algébrique, qui fonctionne en temps sous-exponentiel ( ).
Logarithme discret modifier
Une autre grande classe d'hypothèses sont celles reposant sur la difficulté du problème du logarithme discret, qui a été introduit avec le protocole d'échange de clef de Diffie-Hellman.
Celle-ci est aussi à l'origine d’hypothèses plus fortes qu'elles utilisées pour prouver la sécurité de schémas cryptographiques, comme l’hypothèse décisionnelle de Diffie-Hellman qui permet de prouver la sécurité du cryptosystème ElGamal, ou du cryptosystème de Cramer-Shoup.
Ces hypothèses sont aussi utilisée dans la cryptographie à base de couplages où ses version généralisées sur les appariements ont permis la construction de schémas comme le chiffrement fondé sur l'identité de Boneh-Franklin (en).
Les meilleurs algorithmes existants en 2017 pour le problème du logarithme discret dépendent du groupe cyclique de base. S'il s'agit d’un groupe de la forme ou une extension, alors le crible algébrique reste le meilleur algorithme connu (avec des complexités différentes de celles de la factorisation). Si l'extension se fait sur un corps de petite caractéristique, alors Barbulescu et al. ont montré que ce problème était quasi-polynomial[2], ce qui rend ce type de corps inutilisable pour la cryptographie. En revanche sur des corps de grande caractéristique, la complexité rejoint celle de la factorisation. Actuellement sur les courbes elliptiques, il n'y a pas d'attaques générales connues meilleures que les méthodes génériques comme l'algorithme pas de bébé, pas de géant de complexité exponentielle ( , où n représente l'ordre du groupe de base).
Réseaux euclidiens modifier
En cryptographie post-quantique, les hypothèses reposant sur la difficulté de trouver un vecteur court dans un réseau euclidien étant donné une base assez longue est de plus en plus utilisée depuis les travaux fondateur de Regev en 2005. Les versions de ces hypothèses sur les réseaux sont la recherche du plus court vecteur entier (SVP pour shortest vector problem en anglais) et du vecteur le plus proche (CVP pour closest vector problem en anglais) qui ont la propriété d'impliquer les hypothèses de l’apprentissage avec erreurs, et de la recherche du plus court vecteur entier court (non nul).
Ces hypothèses sont à l'origine de cryptosystème NTRU et de son schéma de signature associé (en). Mais aussi des primitives plus avancées comme chiffrement totalement homomorphe de Gentry (en)[3].
Les meilleurs algorithmes de résolution en 2017 pour ce genre de problèmes reposent sur la réduction de réseaux (en).
Hypothèse de difficultés non-cryptographiques modifier
De la même manière qu'en cryptographie, les hypothèses de difficultés sont utilisées en théorie de la complexité algorithmique pour fournir des preuves que certaines propositions mathématiques sont difficiles à démontrer formellement sans faire ce type d'hypothèses. Dans ces applications, on peut démontrer qu'une hypothèse de complexité implique certaines propriétés de complexité d'un autre problème, à défaut de démontrer que la proprosition mathématique elle-même est vraie. L'hypothèse de ce type la plus célèbre est l'hypothèse P ≠ NP[4], mais on pourrait aussi citer l'hypothèse du temps exponentiel[5] et la conjecture des jeux uniques[6].
Notes et références modifier
Annexes modifier
Bibliographie modifier
- [Fortnow 2009] (en) Lance Fortnow, « The Status of the P versus NP Problem », Communications of the ACM, vol. 52, no 9, , p. 78–86 (DOI 10.1145/1562164.1562186, lire en ligne [PDF]).
- [Khot 2010] (en) Subhash Khot, « On the Unique Games Conjecture », Proc. 25th IEEE Conference on Computational Complexity, , p. 99–121 (DOI 10.1109/CCC.2010.19, lire en ligne [PDF]).
- [Woeginger 2003] (en) Gerhard Woeginger, « Exact Algorithms for NP-Hard Problems: : A Survey », Lecture Notes in Computer Science, Springer-Verlag, vol. 2570 « Combinatorial Optimization — Eureka, You Shrink! », , p. 185–207 (ISBN 978-3-540-00580-3, ISSN 0302-9743, DOI 10.1007/3-540-36478-1_17).
- [Katz et Lindell 2014] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Boca Raton, Chapman and Hall, , 583 p. (ISBN 978-1-4665-7026-9, lire en ligne), « Chapitre 2.3 Limitations of Perfect Secrecy »
- [Regev 2005] (en) Oded Regev, « On lattices, learning with errors, random linear codes, and cryptography », STOC, (lire en ligne [PDF])
- [Laguillaumie, Langlois et Stehlé 2014] Fabien Laguillaumie, Adeline Langlois et Damien Stehlé, Informatique Mathématique, une photographie en 2014, Perpignan, Sylvain Peyronnet, , 223 p. (ISBN 978-2-35412-228-7, lire en ligne [PDF]), « Chiffrement avancé à partir du problème Learning with Errors »
- [Barbulescu et al. 2014] (en) Razvan Barbulescu, Pierrick Gaudry, Antoine Joux et Emmanuel Thomé, « A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic », Eurocrypt, (DOI 10.1007/978-3-642-55220-5_1, lire en ligne)
Articles connexes modifier
