Warum gibt es keinen Verschlüsselungsalgorithmus, der auf den bekannten NP-Hard-Problemen basiert?

109

Der Großteil der heutigen Verschlüsselung, wie der RSA, basiert auf der ganzzahligen Faktorisierung, von der nicht angenommen wird, dass sie ein NP-hartes Problem darstellt. Sie gehört jedoch zu BQP, wodurch sie für Quantencomputer anfällig wird. Ich frage mich, warum es keinen Verschlüsselungsalgorithmus gab, der auf einem bekannten NP-harten Problem basiert. Es klingt (zumindest theoretisch) so, als würde es einen besseren Verschlüsselungsalgorithmus ergeben als einen, der sich nicht als NP-hart herausstellt.

Ken Li
quelle

Antworten:

76

PNPPNP

Eine ausgezeichnete Lektüre ist der Klassiker von Russell Impagliazzo, A Personal View of Average-Case Complexity , 1995.

Eine hervorragende Umfrage ist Average-Case Complexity von Bogdanov und Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106

Mohammad Al-Turkistany
quelle
1
Brauchen wir nicht auch im besten Fall Härte? Schließlich sollten alle unsere Schlüssel sicher sein. Oder können wir effektiv (und effizient) verhindern, dass der beste Fall eintritt?
Raphael
7
NP-hard
@Raphael, es sollte ausreichen, wenn die Wahrscheinlichkeit, einen unerwünschten "guten" Fall zu bekommen, klein genug ist. Wenn es kleiner ist als die Wahrscheinlichkeit, den richtigen Schlüssel für einen wünschenswerten "schlechten" Fall zu erraten, sollte dieses Risiko meiner Meinung nach als akzeptabel angesehen werden.
Quazgar
49

Da waren.

Ein solches Beispiel ist das McEliece-Kryptosystem, das auf der Härte der Dekodierung eines linearen Codes basiert.

Ein zweites Beispiel ist NTRUEncrypt, das auf dem kürzesten Vektorproblem basiert, von dem ich glaube, dass es NP-Hard ist.

Ein weiteres ist das kaputte Merkle-Hellman-Kryptosystem .

Hinweis: Ich habe keine Ahnung, ob die ersten beiden kaputt sind / wie gut sie sind. Ich weiß nur, dass sie existieren, und ich habe sie durch eine Websuche erhalten.

Aryabhata
quelle
6
Für die Kryptoanalyse sollte McEliece wahrscheinlich nicht nur als ein einziges Krytosystem betrachtet werden. Für jede Klasse von effizient decodierbaren linearen Codes, die Sie einstecken, müssen Sie sich eine andere Strategie ausdenken, um sie zu brechen. Es ist für einige Klassen von Codes defekt, aber (wie der Wikipedia-Artikel sagt) nicht für Goppa-Codes, die McElieces ursprünglicher Vorschlag waren.
Peter Shor
Von dieser Liste aus würde ich sagen, dass NTRU am vielversprechendsten aussieht. Es muss noch ausgiebig getestet werden, wie RSA basierend auf dem, was ich bisher gelesen habe, getestet wurde.
Ken Li
Das Merkle-Hellman-Kryptosystem ist kein geeignetes Beispiel. Die Merkle-Hellman-Rucksackprüfer sind nur eine Teilmenge aller Rucksackvektoren, so dass das Merkle-Hellman-Rucksackproblem möglicherweise nicht NP-schwer ist. Ich denke nicht, dass es NP-schwer ist, zumindest ist mir kein Papier bekannt, das dies zeigt.
Miracle173
25

Ich kann mir vier große Hürden vorstellen, die nicht völlig unabhängig sind:

  • Die NP-Härte gibt nur Auskunft über die Komplexität im Grenzbereich . Für viele NP-vollständige Probleme gibt es Algorithmen, die alle relevanten Fälle (in einem bestimmten Szenario) relativ schnell lösen. Mit anderen Worten, für jede feste Problemgröße (z. B. einen gegebenen "Schlüssel") ist das Problem nicht unbedingt schwierig, nur weil es NP-schwer ist.
  • Die NP-Härte berücksichtigt nur die Worst-Case-Zeit. Viele, sogar die meisten Instanzen können mit vorhandenen Algorithmen leicht gelöst werden. Selbst wenn wir wüssten, wie man die harten Instanzen charakterisiert (afaik, tun wir nicht), müssten wir sie immer noch finden.
  • 2n(n1)nn
  • Sie brauchen eine Art Umkehrbarkeit. Zum Beispiel wird jede ganze Zahl eindeutig durch ihre Primfaktorisierung beschrieben. Image Wir möchten TSP als Verschlüsselungsmethode verwenden. Können Sie bei allen kürzesten Touren den Graphen, von dem sie stammen, (neu) konstruieren?

Beachten Sie, dass ich keine Erfahrung mit Kryptografie habe. es handelt sich lediglich um algorithmische bzw. Komplexitätstheoretische Einwände.

Raphael
quelle
Hervorragende Zusammenfassung. Beachten Sie jedoch, dass die BQP-Härte dieselben Einschränkungen aufweist wie Ihre ersten beiden Punkte.
Mitch
14

Die Kryptografie mit öffentlichen Schlüsseln, wie wir sie heute kennen, basiert auf Einweg- Trapdoor- Permutationen, und die Trapdoor ist von wesentlicher Bedeutung.

Damit ein Protokoll öffentlich sicher ist, benötigen Sie einen Schlüssel, der jedem zur Verfügung steht, und eine Möglichkeit, eine Nachricht mit diesem Schlüssel zu verschlüsseln. Einmal verschlüsselt, dürfte es natürlich schwierig sein, die ursprüngliche Nachricht wiederherzustellen, wenn man nur die Verschlüsselung und den öffentlichen Schlüssel kennt: Die Verschlüsselung darf nur mit einigen zusätzlichen Informationen, nämlich Ihrem privaten Schlüssel, entschlüsselbar sein.

Vor diesem Hintergrund ist es einfach, ein primitives Kryptosystem zu erstellen , das auf einer Einweg-Falltürpermutation basiert.

  1. Alice gibt der Öffentlichkeit die Einwegpermutation und behält die Falltür für sich.
  2. Bob legte seine Eingabe in die Permutation und übertrug die Ausgabe an Alice.
  3. Alice verwendet die Falltür, um die Permutation mit Bobs Ausgabe zu invertieren.

PNP

PNPNPINPNPNPINP

NPNPNP

Heinz Fiedler
quelle
RSA, ja, es ist eine Falltürfunktion. Ich bin nicht sicher, ob dlog TDF ist (ist in eine Richtung)
111
Wenn ein NP-intermediäres Problem NP-schwer wäre, wäre es NP-vollständig, ein Widerspruch.
Myria
0

Nur um ein heuristisches Argument zu liefern, das auf praktischen Erfahrungen basiert.

Fast alle Fälle, von fast allen NP-vollständigen Problemen, sind leicht zu lösen. Es gibt Probleme, bei denen dies nicht zutrifft, die jedoch schwer zu finden sind, und es ist schwierig, sich zu vergewissern, dass Sie einen solchen Klang haben.

Dies ist in der Praxis mehrmals vorgekommen, wenn Leute versuchen, zufällige Problemgeneratoren für eine berühmte NP-Complete-Klasse wie Constraint Programming, SAT oder Travelling Salesman zu schreiben. Zu einem späteren Zeitpunkt findet jemand eine Methode, um fast alle Instanzen zu lösen, die der Zufallsgenerator trivial erzeugt. Wäre dies bei einem Verschlüsselungssystem der Fall, wären wir natürlich in ernsthaften Schwierigkeiten!

Chris Jefferson
quelle
-1

Merkle-Hellman-Kryptosysteme basieren auf binären Rucksackproblemen (Teilmengen).

user13675
quelle
Können Sie eine Referenz geben?
Raphael
" en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem " und auch die Monographie: Postquantum Cryptography (Springer).
user13675