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

110

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.

Ken Li
la source

Réponses:

76

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

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

Mohammad Al-Turkistany
la source
1
N'avons-nous pas besoin de dureté dans le meilleur des cas? Après tout, toutes nos clés devraient être en sécurité. Ou pouvons-nous efficacement (et efficacement) empêcher le meilleur des cas de se produire?
Raphaël
7
De plus, nous devrions pouvoir générer des instances difficiles dans un délai raisonnable. En bref, nous avons besoin de beaucoup plus que de simples ness. NP-hard
Kaveh
@ Raphaël, cela devrait être suffisant si la probabilité d'obtenir un "bon" cas indésirable est suffisamment petite. S'il est inférieur à la probabilité de deviner la clé correcte d'un "mauvais" cas souhaitable, ce risque doit être considéré comme acceptable.
Quazgar
49

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.

Aryabhata
la source
6
Aux fins de l'analyse cryptographique, McEliece ne devrait probablement pas être considéré comme un seul système; pour chaque classe de codes linéaires décodables efficacement que vous branchez, vous devez nécessairement proposer une stratégie différente pour la casser. Il a été cassé pour certaines classes de codes, mais (comme le dit l'article de Wikipedia) pas pour les codes de Goppa, qui avaient été suggérés à l'origine par McEliece.
Peter Shor
De cette liste, je dirais que NTRU semble la plus prometteuse, elle n’a pas encore été testée de la manière dont RSA a été testée sur la base des informations que j’ai lues jusqu’à présent.
Ken Li
Le cryptosystème Merkle-Hellman n’est pas un exemple approprié. Les verctors de sac à dos Merkle-Hellman ne sont qu'un sous-ensemble de tous les vecteurs de sac à dos; le problème de sac à dos Merkle-Hellman n'est donc peut-être pas si difficile à résoudre. Je ne pense pas que ce soit NP-difficile, du moins je ne suis au courant d'aucun document qui montre cela.
miracle173
25

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 n2n(n1)nn
  • 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.

Raphaël
la source
Excellent résumé. Mais notez que la dureté BQP présente les mêmes réserves que vos deux premiers points.
Mitch
14

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

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 PPNPNPINPNPNPINP

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 PNPNPNP

Heinz Fiedler
la source
RSA, oui c'est une fonction trappe. Je ne suis pas sûr que dlog soit TDF (à sens unique)
111
Si un problème NP-intermédiaire était NP-difficile, il serait NP-complet, une contradiction.
Myria
0

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!

Chris Jefferson
la source
-1

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

utilisateur13675
la source
Pouvez-vous donner une référence?
Raphaël
" en.wikipedia.org/wiki/Merkle- Hellman_knapsack_cryptosystem" ainsi que la monographie: Cryptographie Postquantum (Springer).
user13675