Existe-t-il des algorithmes de cryptographie à clé publique qui sont NP-difficiles à vaincre? [fermé]

Question

Si l'informatique quantique devenait une réalité, je me demandais s'il existait des algorithmes cryptographiques à clé publique basés sur des problèmes NP-complets plutôt que sur une factorisation entière ou des logarithmes discrets.

Modifier:

Consultez la section "Calcul quantique dans la théorie de la complexité de calcul" " section de l'article du wiki sur les ordinateurs quantiques. Il souligne que la classe de problèmes auxquels les ordinateurs quantiques peuvent répondre (BQP) ) est censé être strictement plus facile que NP-complete.

Modifier 2:

"Basé sur NP-complete" est une mauvaise façon d'exprimer ce qui m'intéresse.

Ce que je voulais demander, c'est un algorithme de chiffrement à clé publique avec la propriété que toute méthode permettant de rompre le chiffrement peut également être utilisée pour résoudre le problème NP-complet sous-jacent. Cela signifie que casser le chiffrement prouve que P = NP.

Answer 1

Je réponds à cet ancien fil de discussion car il s'agit d'une question très courante et importante, et toutes les réponses fournies ici sont inexactes.

La réponse courte à la question initiale est un "NON" sans équivoque. Il n'y a pas de schémas de chiffrement connus (sans parler de ceux à clé publique) qui soient basés sur un problème NP-complet (et donc tous, avec des réductions de temps polynomial). Certains sont " plus proches " que d'autres, cependant, alors laissez-moi élaborer.

Il y a beaucoup de choses à clarifier ici, commençons par la signification de "basé sur un problème NP-complet". L’interprétation généralement admise de ce principe est la suivante: "il peut être prouvé qu’il est sûr dans un modèle formel particulier, en supposant qu’aucun algorithme polynomial n’existe pour les problèmes NP-complets". Pour être encore plus précis, nous supposons qu’il n’existe aucun algorithme qui always résolve un problème NP-complet. C’est une hypothèse très sûre, car c’est une chose très difficile à faire pour un algorithme - il est apparemment beaucoup plus facile de trouver un algorithme qui résout des instances aléatoires du problème avec une bonne probabilité.

Cependant, aucun schéma de chiffrement n’a une telle preuve. Si vous consultez la littérature, à quelques rares exceptions près (voir ci-dessous), les théorèmes de sécurité se présentent comme suit:

  

Théorème: Ce schéma de chiffrement est sûrement sécurisé, en supposant qu'aucun   algorithme de temps polynomial existe pour    résolution d'instances aléatoires d'un problème X .

Notez les " instances aléatoires " partie. Pour un exemple concret, nous pourrions supposer qu'il n'existe aucun algorithme polynomial pour factoriser le produit de deux nombres premiers aléatoires à n bits avec une bonne probabilité. Cela est très différent (moins sûr) de supposer qu’il n’existe aucun algorithme polynomial pour toujours factoriser tous les produits de deux nombres premiers aléatoires à n bits.

Les "instances aléatoires" par rapport à "pires cas" & La question est ce qui a déclenché plusieurs intervenants ci-dessus. Les schémas de chiffrement de type McEliece sont basés sur une version très spéciale de codes linéaires de décodage, et non sur la version la plus défavorable, NP-complete.

En poussant au-delà de ces "instances aléatoires" Cette question a nécessité des recherches approfondies et esthétiques en informatique théorique. En commençant par les travaux de Mikl Ajtai, nous avons trouvé des algorithmes de chiffrement dans lesquels l'hypothèse de sécurité est un "cas extrême". (plus sûr) hypothèse au lieu d'une hypothèse aléatoire. Malheureusement, les hypothèses les plus défavorables concernent des problèmes dont on ne sait pas qu'ils sont NP complets, et certaines preuves théoriques suggèrent que nous ne pouvons pas les adapter pour utiliser des problèmes NP-complets. Pour les intéressés, consultez la rubrique "Cryptographie sur réseau".

Answer 2

Certains systèmes cryptographiques basés sur des problèmes NP-difficiles ont été proposés (tels que le Merkle-Hellman cryptosystème basé sur le problème de la somme des sous-ensembles et sur le cryptosystème de sac à dos Naccache-Stern basé sur sur le problème de sac à dos), mais ils ont tous été cassés. Pourquoi est-ce? Conférence 16 sur Les grandes idées de l'informatique théorique de Scott Aaronson dit quelque chose à ce sujet, que je pense que vous devriez prendre comme définitif. Ce qu'il dit est le suivant:

Idéalement, nous aimerions construire un [Générateur pseudo-aléatoire cryptographique] ou un cryptosystème dont la sécurité est basée sur un problème NP-complet. Malheureusement, les problèmes NP-complets concernent toujours le pire des cas. En cryptographie, cela se traduirait par une déclaration du type "il existe " un message "difficile à décoder", ce qui n'est pas une bonne garantie pour un système cryptographique! Un message devrait être difficile à décrypter avec une probabilité écrasante. Malgré des décennies d’efforts, il n’a encore été découvert aucun moyen de relier les cas les plus graves aux cas moyens de problèmes NP-complets. Et c’est pourquoi, si nous voulons des systèmes cryptographiques sécurisés sur le plan informatique, nous devons faire des hypothèses plus solides que P & # 8800; NP.

Answer 3

C’était une question ouverte en 1998:

Sur la possibilité de baser la cryptographie sur l'hypothèse que P! = NP par Oded Goldreich, Rehovot Israël et Shafi Goldwasser

Extrait de l'abstrait: "Notre conclusion est que la question reste ouverte".

- Je me demande si cela a changé au cours de la dernière décennie?

Modifier:

Autant que je sache, la question est toujours en suspens. Des progrès récents en vue de trouver une réponse sans algorithme existent.

Adi Akavia, Oded Goldreich, Shafi Goldwasser et Dana Moshkovitz ont publié ce document dans l'ACM en 2006: Sur la base des fonctions unidirectionnelles sur la dureté NP " Nos principales conclusions sont les deux résultats négatifs suivants "

Le site de Stanford Complexity Zoo permet de mieux comprendre la signification de ces deux résultats négatifs.

Answer 4

Bien que de nombreux formulaires aient été cassés, consultez Merkle-Hellman , basé sur une forme du «problème de sac à dos» NP-complet.

Answer 5

La cryptographie sur réseau offre le message (sur) généralisé à prendre qui permet de concevoir des cryptosystèmes où casser le cas moyen est aussi difficile que de résoudre un problème particulier de type NP-difficile (généralement le problème de vecteur le plus court ou le plus proche).

Je peux vous recommander de lire la section d'introduction de http://eprint.iacr.org/2008/521. , puis les références aux systèmes cryptographiques.

Voir également les notes de cours à l'adresse http: //www.cs.ucsd. edu / ~ daniele / CSE207C / et recherchez des liens pour un livre si vous le souhaitez.

Answer 6

Googling for NP-complete et le cryptage à clé publique trouve des faux positifs ... qui ne sont pas sécurisés. Ce le dessin animé pdf apparaît pour afficher un algorithme d'encyption de clé publique basé sur le problème de jeu dominant dominant minimium . En poursuivant la lecture, il admet ensuite que l’algorithme est sécurisé. Le problème sous-jacent est NP-Complete, mais son utilisation dans l’algorithme PK ne préserve pas la difficulté.

Une autre fausse découverte positive de Google: Cryptanalyse de Crypto de Goldreich-Goldwasser-Halevi 97 . Extrait du résumé:

Lors de Crypto '97, Goldreich, Goldwasser et Halevi ont proposé un cryptosystème à clé publique basé sur le problème de vecteur le plus proche dans un réseau, connu pour être NP-difficile. Nous montrons qu'il existe un défaut majeur dans la conception du schéma, qui a deux implications: tout texte chiffré fuyant des informations sur le texte en clair, et le problème du déchiffrement des textes cryptés peut être réduit à un problème de vecteur plus particulier, beaucoup plus facile que le problème général. .

Answer 7

Un site Web peut vous intéresser: Cryptographie post-quantique .

Answer 8

Voici mon raisonnement. Corrigez-moi si je me trompe.

(i) "Briser" un cryptosystème pose nécessairement problème dans NP et co-NP. (Briser un système cryptographique implique d'inverser la fonction de chiffrement, qui est un à un et calculable en temps polynomial. Ainsi, étant donné le texte crypté, le texte en clair est un certificat qui peut être vérifié en temps polynomial. L'interrogation du texte en clair sur la base du le texte chiffré est en NP et en co-NP.)

(ii) S'il existe un problème NP-difficile en NP et co-NP, alors NP = co-NP. (Ce problème serait NP-complet et en co-NP. Comme toute langue de NP est réductible à cette langue de co-NP, NP est un sous-ensemble de la co-NP. Maintenant, utilisez la symétrie: toute langue L en co-NP a -L (son complément) en NP, d'où -L est en co-NP - c'est-à-dire que L = --L est en NP.)

(iii) Je pense qu'il est généralement admis que NP! = co-NP, sinon il existe des preuves au format polynomial indiquant que les formules booléennes ne sont pas satisfaisables.

Conclusion: les conjectures théoriques sur la complexité impliquent que les cryptosystèmes NP-hard n’existent pas.

(Sinon, vous avez un problème NP-difficile en NP et co-NP, d'où NP = co-NP - qui est supposé être faux.)

Answer 9

Bien que RSA et d’autres algorithmes cryptographiques largement utilisés reposent sur la difficulté de la factorisation d’entiers (qui n’est pas connue pour être NP-complet), certains algorithmes de cryptographie à clé publique sont également basés sur des problèmes NP-complets. Une recherche google pour " clé publique " et " np-complete " va en révéler quelques-unes.

(J'ai dit à tort avant que les ordinateurs quantiques accélèrent les problèmes NP-complets, mais ce n'est pas vrai. Je suis corrigé.)

Answer 10

Comme l'ont souligné de nombreuses autres affiches, il est possible de baser la cryptographie sur des problèmes NP-hard ou NP-complete.

Cependant, les méthodes courantes de cryptographie seront basées sur des mathématiques difficiles (difficiles à résoudre, c’est-à-dire). La vérité est qu'il est plus facile de sérialiser des nombres en tant que clé traditionnelle que de créer une chaîne normalisée qui résout un problème NP-difficile. Par conséquent, la cryptographie pratique est basée sur des problèmes mathématiques dont il n’a pas encore été prouvé qu'ils étaient NP-difficiles ou NP-complets (il est donc concevable que certains de ces problèmes soient en P).

Dans le chiffrement ElGamal ou RSA, le déchiffrer nécessite le déchiffrement du logarithme discret, consultez donc ce wikipedia article.

  

Aucun algorithme efficace pour calculer les logarithmes discrets généraux logbg n’est connu. L'algorithme naïf consiste à élever b à des puissances de plus en plus élevées k jusqu'à ce que le g souhaité soit trouvé; c'est ce qu'on appelle parfois la multiplication d'essai. Cet algorithme nécessite un temps d'exécution linéaire dans la taille du groupe G et donc exponentiel dans le nombre de chiffres dans la taille du groupe. Il existe cependant un algorithme quantique efficace dû à Peter Shor ( http://arxiv.org/abs/ quant-ph / 9508027 ).

     

Le calcul des logarithmes discrets est apparemment difficile. Non seulement aucun algorithme efficace n'est connu dans le cas le plus défavorable, mais il est également possible de démontrer que la complexité du cas moyen est au moins aussi difficile que celle du cas le plus défavorable en utilisant la réductibilité automatique aléatoire.

     

En même temps, le problème inverse de l’exponentiation discrète n’est pas (il peut être calculé efficacement en utilisant l’exponentiation par quadrature, par exemple). Cette asymétrie est analogue à celle qui existe entre la factorisation de nombre entier et la multiplication de nombre entier. Les deux asymétries ont été exploitées dans la construction de systèmes cryptographiques.

La croyance répandue est que ceux-ci sont NP-complets, mais peut-être ne peut-on pas le prouver. Notez que les ordinateurs quantiques peuvent casser efficacement la cryptographie!

Answer 11

Comme personne n’a vraiment répondu à la question, je dois vous donner un indice: "McEliece". Faites des recherches dessus. C'est un algorithme de cryptage NP-Hard éprouvé. Il faut O (n ^ 2) temps de chiffrement et de déchiffrement. Il a aussi une clé publique de taille O (n ^ 2), ce qui est mauvais. Mais il y a des améliorations qui abaissent toutes ces limites.