Pourquoi n'y a-t-il pas eu d'algorithme de chiffrement basé sur les problèmes connus de NP-Hard?

La plupart des méthodes de cryptage actuelles, telles que RSA, reposent sur la factorisation entière, qui n'est pas considérée comme un problème complexe, mais appartient au BQP, ce qui la rend vulnérable aux ordinateurs quantiques. Je me demande pourquoi il n’existe pas d’algorithme de chiffrement basé sur un problème NP-hard connu. Il semble (du moins en théorie) que cela constituerait un meilleur algorithme de cryptage que celui dont il n’est pas prouvé qu’il est NP-difficile.

La dureté la plus défavorable des problèmes NP-complets n'est pas suffisante pour la cryptographie. Même si les problèmes NP-complets sont difficiles dans le cas le plus défavorable ( ), ils peuvent néanmoins être résolus efficacement dans le cas moyen. La cryptographie suppose l’existence de problèmes insolubles dans la moyenne des cas dans NP. De plus, prouver l'existence de problèmes difficiles à moyen dans NP en utilisant l' hypothèse est un problème ouvert majeur.$P \ne NP$$P \ne NP$

Russell Impagliazzo, Une vision personnelle de la complexité moyenne des affaires , 1995, est une excellente lecture .

Une excellente étude est la complexité moyenne-cas par Bogdanov et Trevisan, fondations et tendances dans Theoretical Computer Science Vol. 2, no 1 (2006) 1–106

Il y a eu.

Un tel exemple est le cryptosystème McEliece, basé sur la dureté du décodage d'un code linéaire.

Un autre exemple est NTRUEncrypt, qui est basé sur le problème de vecteur le plus court, connu pour être NP-Hard.

Un autre système, le cryptosystème de sac à dos Merkle-Hellman, a été brisé.

Note: Je n'ai aucune idée si les deux premiers sont cassés / à quel point ils sont bons. Tout ce que je sais, c'est qu'elles existent et je les ai obtenues en effectuant une recherche sur le Web.

Je peux penser à quatre obstacles majeurs qui ne sont pas entièrement indépendants:

• La dureté NP ne vous donne que des informations sur la complexité dans la limite . Pour de nombreux problèmes NP-complets, il existe des algorithmes qui résolvent toutes les instances d'intérêt (dans un certain scénario) de manière raisonnablement rapide. En d'autres termes, pour toute taille de problème fixe (par exemple une "clé" donnée), le problème n'est pas nécessairement difficile simplement parce qu'il est NP-difficile.
• La dureté NP ne prend en compte que le pire des cas. Beaucoup, voire la plupart des cas, peuvent être faciles à résoudre avec des algorithmes existants. Même si nous savions comment caractériser les instances dures (autant que nous sachions), il nous faudrait quand même les trouver.
• Vous devez avoir d' énormes instances difficiles à résoudre. La recherche de (produits de) grands nombres premiers est facile dans la mesure où l'espace de recherche est plat: un nombre est adapté ou non. Imaginez utiliser des graphes: sur les graphes de la taille pour le grand , vous devez trouver ceux qui ont de belles propriétés. n $2^{n(n-1)}$$n$$n$
• Vous avez besoin d'une sorte de réversibilité. Par exemple, tout entier est décrit de manière unique par sa factorisation première. Image nous voudrions utiliser TSP comme méthode de cryptage; pouvez-vous (re) construire le graphe dont ils proviennent uniquement avec les visites les plus courtes?

Notez que je n'ai aucune expertise en cryptographie; ce ne sont que des algorithmes resp. objections de la complexité théorique.

La cryptographie à clé publique telle que nous la connaissons aujourd’hui repose sur des permutations à une trappe à sens unique , et la trappe est essentielle.

Pour qu'un protocole soit publiquement sécurisé, vous avez besoin d'une clé disponible pour tout le monde et d'un moyen de chiffrer un message à l'aide de cette clé. Évidemment, une fois chiffré, il devrait être difficile de récupérer le message d'origine en ne connaissant que son chiffrement et la clé publique: le chiffrement ne doit être déchiffrable qu'avec certaines informations supplémentaires, à savoir votre clé privée.

Dans cet esprit, il est facile de construire un système cryptographique primitif basé sur toute permutation à une trappe à sens unique.

1. Alice donne la permutation à sens unique au public et garde la trappe pour elle-même.
2. Bob a mis son entrée dans la permutation et a transmis le résultat à Alice.
3. Alice utilise la trappe pour inverser la permutation avec la sortie de Bob.

La difficulté est maintenant de trouver de véritables permutations unidirectionnelles dans les trappes, et il existe de nombreuses fonctions que nous pensons être de bons candidats (RSA, logarithme discret, quelques variations du problème du réseau). Cependant, si nous pouvons trouver avec certitude une fonction à sens unique, nous prouvons également que , prouvant ainsi qu'une fonction à sens unique est intraitable.$\mathsf{P} \ne \mathsf{NP}$

Inversement, si nous prouvons que , nous prouvons également qu’il existe une classe entre (intermédiaire), des problèmes rencontrés dans mais pas -hard. Quelques bons candidats pour des problèmes dans sont également candidats à des permutations à sens unique, car nous n’avons pas encore été en mesure de prouver qu’ils sont -hard.N P I N P N P N P I N $\mathsf{P} \ne \mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$

Donc, pour répondre à votre question, nous n’utilisons pas les problèmes - car nous avons besoin d’une permutation à sens unique avec les trappes, et ces fonctions spéciales résident probablement dans une classe entre et -dur.N P N $\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Juste pour donner un argument heuristique, basé sur l'expérience pratique.

Presque tous les cas, presque tous les problèmes NP-complets, sont faciles à résoudre. Il existe des problèmes pour lesquels ce n'est pas vrai, mais ils sont difficiles à trouver et il est difficile d'être certain que vous ayez une classe de ce genre.

Cela est apparu à plusieurs reprises dans la pratique lorsque des personnes ont essayé d'écrire des générateurs de problèmes aléatoires pour certaines classes célèbres de NP-complete, telles que Constraint Programming, SAT ou Travelling Salesman. À une date ultérieure, une personne trouve une méthode pour résoudre presque toutes les instances générées de manière triviale par un générateur aléatoire. Bien sûr, si c'était le cas pour un système de cryptage, nous aurions de sérieux problèmes!

Les cryptosystèmes Merkle-Hellman sont basés sur des problèmes de sac à dos binaire (somme de sous-ensemble).