Welche Sprachen wurden erfolgreich kryptografisch erfasst?

Eine Beobachtung, die mit asymmetrischer Kryptographie verbunden ist, ist, dass einige Funktionen (von denen angenommen wird) leicht in eine Richtung auszuführen, aber schwierig zu invertieren sind. Darüber hinaus wird das Problem zu einem Kandidaten für ein Kryptografieschema mit öffentlichem Schlüssel, wenn eine "Falltür" -Information vorhanden ist, mit der die inverse Operation schnell berechnet werden kann.

Klassische Falltürprobleme, die durch RSA bekannt wurden, umfassen das Factoring-Problem und das Problem des diskreten Protokolls. Ungefähr zur gleichen Zeit, zu der RSA veröffentlicht wurde, erfand Rabin ein Kryptosystem mit öffentlichem Schlüssel, das auf dem Auffinden diskreter Quadratwurzeln beruhte (dies erwies sich später als mindestens so schwierig wie das Faktorisieren).

Andere Kandidaten sind im Laufe der Jahre aufgetaucht. KNAPSACK (kurz nach RSA), Elliptic Curve "Logarithms" mit spezifischen Parametern und Lattice Shortest Basis Problems sind Beispiele für Probleme, deren Falltürprobleme in anderen veröffentlichten Schemata verwendet wurden. Es ist auch leicht einzusehen, dass solche Probleme irgendwo in NP liegen müssen.

Dies erschöpft mein Wissen über Falltürfunktionen. Es scheint auch die Liste auf Wikipedia zu erschöpfen .

Ich hoffe, dass wir eine Community-Wiki-Liste von Sprachen bekommen, die Falltüren und relevante Literatur zulassen. Die Liste wird nützlich sein. Die sich entwickelnden Anforderungen der Kryptographie ändern auch, welche Falltürfunktionen die Basis von Kryptosystemen sein können. Die Speicherexplosion auf Computern ermöglicht Schemata mit großen Schlüsselgrößen. Das sich ständig abzeichnende Gespenst von Quantum Computing macht Schemata ungültig, die mit einem Orakel zum Auffinden versteckter abelscher Untergruppen gebrochen werden können. Das vollständig homomorphe Kryptosystem von Gentry funktioniert nur, weil wir Falltürfunktionen entdeckt haben, die Homomorphismen berücksichtigen.

Ich interessiere mich besonders für Probleme, die nicht NP-Complete sind.

Es ist wichtig, zwischen Trapdoor-Funktionen und Public-Key-Verschlüsselung zu unterscheiden. Während Trapdoor-Funktionen Schemata für die Verschlüsselung mit öffentlichen Schlüsseln liefern, implizieren einige der von Ihnen genannten Kandidaten bekanntermaßen nur die Verschlüsselung mit öffentlichen Schlüsseln und bieten Ihnen nicht unbedingt Trapdoor-Funktionen. Tatsächlich zeigen Gertner, Malkin und Reingold , dass es keine Black-Box-Konstruktion einer Trapdoor-Funktion aus einem "Trapdoor-Prädikat" gibt (das als ein Ein-Bit-Public-Key-Verschlüsselungsschema betrachtet werden kann).

Klassische Beispiele für Falltürfunktionen sind die RSA- und Rabin-Funktionen. Ein klassisches Beispiel für ein Falltür-Prädikat ist die Entscheidung Quadratic Residuosity modulo eines Komposits aufgrund von Goldwasser und Micali. Die diskreten log- und gitterbasierten Konstruktionen, die Sie erwähnen, führen direkt zu einer Verschlüsselung mit öffentlichen Schlüsseln, ohne dass die Falltürfunktionen ausgeführt werden müssen.

Nachfolgend finden Sie eine (nicht umfassende) Liste der Konstruktionen von Public-Key-Verschlüsselungsschemata, von denen die meisten keine Trapdoor-Funktionen ausführen.

• Kryptosystem mit öffentlichem Schlüssel von El Gamal (einschließlich elliptischer Kurvenvarianten). Sicherheit basiert auf der Annahme von Decisional Diffie Hellman. Durchläuft keine Trapdoor-Funktionen (eine Trapdoor-Funktion, deren Sicherheit auf der semantischen Sicherheit von El Gamal basiert, finden Sie im folgenden Artikel von Peikert-Waters).

  [Taher El Gamal: Ein Kryptosystem mit öffentlichem Schlüssel und ein auf diskreten Logarithmen basierendes Signaturschema. CRYPTO 1984: 10-18]

• Ajtai-Dwork, Regev. Die Sicherheit basiert auf einer eindeutigen SVP in Gittern. Es ist nicht bekannt, dass dies Falltürfunktionen impliziert.

  [Miklós Ajtai, Cynthia Dwork: Ein Public-Key-Kryptosystem mit Worst-Case / Average-Case-Äquivalenz. STOC 1997: 284-293]

  [Oded Regev: Neue gitterbasierte kryptografische Konstruktionen. STOC 2003: 407-416]

• Regev, Peikert. Sicherheit basiert auf der Härte des Lernens mit Fehlern (dies schließt eine Reduzierung von SVP ein). Es ist nicht bekannt, dass dies Falltürfunktionen impliziert.

  [Oded Regev: Über Gitter, Lernen mit Fehlern, zufälligen linearen Codes und Kryptographie. STOC 2005: 84-93]

  [Chris Peikert: Public-Key-Kryptosysteme aus dem Worst-Case-Shortest-Vector-Problem: Extended Abstract. STOC 2009: 333-342]

• Peikert, Wasser. Die Sicherheit basiert auf Diffie Hellman und auf Gitterproblemen. Es ist bekannt, dass Trapdoor-Funktionen (durch verlustbehaftete Trapdoor-Funktionen) impliziert werden.

  [Chris Peikert, Brent Waters: Verlustbehaftete Falltürfunktionen und ihre Anwendungen. STOC 2008: 187-196]

• Lyubashevsky, Palacio, Segev. Die Sicherheit basiert auf der Teilmengen-Summe. Es ist nicht bekannt, dass dies Falltürfunktionen impliziert.

  [Vadim Lyubashevsky, Adriana Palacio, Gil Segev: Kryptografische Primitive mit öffentlichem Schlüssel sind nachweislich so sicher wie Teilmengen. TCC 2010: 382-400]

• Stehlé, Steinfeld, Tanaka, Xagawa und Lyubashevsky, Peikert, Regev. Sicherheit basiert auf der Ringhärte von LWE. Der Vorteil dieser gegenüber früheren Vorschlägen ist ihre kleinere Schlüsselgröße. Es ist nicht bekannt, dass dies Falltürfunktionen impliziert.

  [Damien Stehlé, Ron Steinfeld, Keisuke Tanaka und Keita Xagawa: Effiziente Verschlüsselung öffentlicher Schlüssel auf der Basis idealer Gitter. ASIACRYPT 2009: 617-635]

  [Vadim Lyubashevsky, Chris Peikert, Oded Regev: Über ideale Gitter und Lernen mit Fehlern über Ringe. EUROCRYPT 2010: 1-23]