Hypothèse calculatoire
# 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 ; 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

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

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

### Logarithme discret

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

### Réseaux euclidiens

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

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

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, mais on pourrait aussi citer l'hypothèse du temps exponentiel et la conjecture des jeux uniques.

