Hypothèse calculatoire

De nombreux cryptosystèmes reposent sur la difficulté de factoriser un nombre semi-premier ${\displaystyle N=p\cdot q}$. 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 (${\displaystyle {\mathcal {O}}\left(\exp \left((c+o(1))(\log N)^{1/3}(\log \log N)^{2/3}\right)\right)}$).

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 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ 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 (${\displaystyle {\mathcal {O}}\left(\exp \left({\tfrac {|n|}{2}}\right)\right)}$, où n représente l'ordre du groupe de base).

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).

• [Fortnow 2009] (en) Lance Fortnow, « The Status of the P versus NP Problem », Communications of the ACM, vol. 52, n^o 9,‎ 2009, 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,‎ 2010, 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! »,‎ 2003, 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, 2014, 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,‎ 2005 (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, 2014, 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,‎ 2014 (DOI 10.1007/978-3-642-55220-5_1, lire en ligne)

• Sécurité inconditionnelle