Beispiele für NP Complete-Schlüsselaustauschalgorithmen

7

Im Internet gibt es eine Reihe von Fragen (diese und andere Websites ; z. B. Warum gab es keinen Verschlüsselungsalgorithmus, der auf den bekannten NP-Hard-Problemen basiert? ), Die die NP-Härte verschiedener asymmetrischer Kryptosysteme diskutieren. Wie gut sind NP-Hard-Key-Sharing-Systeme etabliert? Das heißt, Systeme zum Einrichten eines gemeinsam genutzten Schlüssels (der dann bei der symmetrischen Verschlüsselung verwendet werden kann), die auf Problemen basieren, von denen bekannt ist, dass sie NP-schwer sind.

Ich wurde zu dieser Frage aufgefordert, als ich über https://en.wikipedia.org/wiki/Anshel-Anshel-Goldfeld_key_exchange las und mich fragte, ob bei der Implementierung in oder gezeigt werden konnte, dass sie NP-vollständig ist , weil diese auf den ersten Blick wie furchtbar harte Constraint-Zufriedenheits- oder quadratische Optimierungsprobleme aussehen. Das entsprechende Problem, auf dem dies basiert, ist das Simultane Konjugationsproblem.GLn(F2)GLn(R)

Ich bin mir bewusst, dass es einen wichtigen Unterschied zwischen Problemen gibt, die im schlimmsten Fall nur NP-schwer sind - aber bei den meisten zufälligen Instanzen einfach sind, im Gegensatz zu Problemen, bei denen es sich um "durchschnittliche NP-Fälle" handelt - bei einer Reihe von zufälligen Instanzen Die Hälfte von ihnen zu lösen ist immer noch schwierig. Ich würde gerne etwas über Systeme zur gemeinsamen Nutzung von Schlüsseln erfahren, die auf beiden Vorstellungen von Härte beruhen.

complexity-theory np-complete cryptography Alex Meiburg
quelle
1
Algorithmen können nicht NP-hart sein; Es ist eine Eigenschaft von Problemen .
Raphael
1
Richtig, ich meine die NP-Härte, die entsprechenden Protokolle zu brechen. Im Fall von AAG entspricht dies dann dem Problem der gleichzeitigen Konjugation (das für einige Gruppen wie die symmetrische Gruppe leicht bekannt ist und für andere wie die Geflechtgruppen als hart angesehen wird)
Alex Meiburg,
Bitte definieren Sie, was Sie unter einem "Key-Sharing-System" verstehen. Sprechen Sie über den Austausch von Schlüsseln mit öffentlichem Schlüssel , z. B. Diffie-Hellman und dergleichen?
DW
1
Ja, ein Protokoll (nicht unbedingt authentifizierend), das es den Parteien ermöglicht, einen Schlüssel zu erhalten, der (idealerweise) nur dem Paar von ihnen bekannt ist und der dann für die weitere verschlüsselte Kommunikation verwendet werden kann, z. B. AES
Alex Meiburg,

Antworten:

5

Es sind keine kryptografischen Algorithmen mit öffentlichem Schlüssel bekannt, die sich als NP-schwer zu brechen erwiesen haben. Keiner. Daher können wir Ihnen keine Beispiele nennen, da keine bekannt sind.

Antwort auf Ihre ursprüngliche Frage:

Die Analyse unter Warum gab es keinen Verschlüsselungsalgorithmus, der auf den bekannten NP-Hard-Problemen basiert? gilt auch für den Austausch öffentlicher Schlüssel.

Die Kryptographie erfordert eine durchschnittliche Härte. Die NP-Härte bezieht sich auf die Härte im ungünstigsten Fall; Es gibt keine Vorstellung von einer Verteilung auf Eingaben, Wahrscheinlichkeiten oder irgendeine Art von "Durchschnitt". Die Härte im ungünstigsten Fall scheint keine Härte im durchschnittlichen Fall zu bedeuten: Es gibt viele Probleme, von denen angenommen wird, dass sie im schlimmsten Fall hart, im durchschnittlichen Fall jedoch einfach sind. Status der Welten von Impagliazzo? hat einige Hinweise zu diesem Thema.

DW
quelle