Status der Welten von Impagliazzo?

32

Im Jahr 1995 schlug Russell Impagliazzo fünf komplexe Welten vor:

1- Algorithmus: mit all den erstaunlichen Konsequenzen.P=NP

2- Heuristica: vollständige Probleme sind im schlimmsten Fall ( ) schwierig, aber im Durchschnitt effizient lösbar.P ≠ N PNPP≠NP

3- Pessiland: Es gibt vollständige Probleme im Durchschnitt , aber keine Einwegfunktionen. Dies impliziert, dass wir mit bekannter Lösung keine harten Instanzen eines vollständigen Problems erzeugen können . N PNPNP

4- Minicrypt: Einwegfunktionen sind vorhanden, aber kryptografische Systeme mit öffentlichem Schlüssel sind nicht möglich

5- Kryptomanie: Kryptografische Systeme mit öffentlichem Schlüssel sind vorhanden und eine sichere Kommunikation ist möglich.

Welche Welt wird von den jüngsten Fortschritten bei der Komplexität der Berechnungen bevorzugt? Was ist der beste Beweis für die Wahl?

Russell Impagliazzo, Ein persönlicher Blick auf die Komplexität von Durchschnittsfällen , 1995

Die fünf Welten von Impagliazzo, der Computational Complexity-Blog

cc.complexity-theory conditional-results average-case-complexity Mohammad Al-Turkistany
quelle
2
Ich bin kein ausgewiesener Experte, aber ich dachte, Sie möchten vielleicht wissen, dass Impagliazzo beim ersten Workshop zu Barriers in Complexity ein Forschungsprogramm gefordert hat, das Ihrer Frage sehr gut entspricht. Nennen Sie "erdähnliche Orakel" -Orakel, in denen die gleichen Komplexitätssätze gelten wie in der "realen" nicht-relativen Welt, in der wir leben. Untersuchen Sie dann die Eigenschaften dieser Orakel, die der realen Erde ähnlich sind. In diesem Rahmen lautet Ihre Frage also: "Was muss ein Orakel erfüllen, um erdähnlich zu sein?"
Aaron Sterling

Antworten:

25

Vor ungefähr einem Jahr organisierte ich einen Workshop zu Komplexität und Kryptographie: Status von Impagliazzos Welten , und die Folien und Videos auf der Website könnten von Interesse sein.

Die kurze Antwort lautet, dass sich nicht viel in dem Sinne geändert hat, dass die meisten Forscher immer noch glauben, dass wir in "Cryptomania" leben, und dass wir immer noch mehr oder weniger die gleichen Beweise dafür haben und nicht viel Fortschritte gemacht haben, um eine der Welten für die andere zu kollabieren.

Die vielleicht bedeutendste neue Information ist Shors Algorithmus, der zeigt, dass zumindest wenn Sie P durch BQP ersetzen, die am häufigsten verwendeten Kryptosysteme mit öffentlichem Schlüssel unsicher sind. Aufgrund von Gitter-basierten Kryptosystemen wird jedoch standardmäßig davon ausgegangen, dass wir auch in diesem Fall in Kryptomanie leben, obwohl der Konsens hier möglicherweise etwas schwächer ist als im klassischen Fall. Selbst im klassischen Fall scheint es viel mehr Hinweise auf die Existenz von Einwegfunktionen ("Minicrypt") zu geben als auf die Existenz einer Verschlüsselung mit öffentlichen Schlüsseln ("Cryptomania"). Angesichts der Anstrengungen, die die Menschen unternommen haben, um verschiedene Kryptosysteme mit öffentlichen Schlüsseln aufzubrechen, gibt es auch für letztere signifikante Beweise.

Boaz Barak
quelle
Dieser Link funktioniert möglicherweise besser: archive.dimacs.rutgers.edu/Workshops/Cryptography/program.html
Timothy Chow
18

Gute Frage, aber Wissenschaftler konnten "Algorithmica" nicht einmal von den übrigen Fällen trennen, geschweige denn die genaue Welt bestimmen, in der wir leben.

Das heißt, es gibt mehrere Forschungsarbeiten zu diesem Thema. Siehe zum Beispiel: Auf der Möglichkeit, die Kryptographie auf der Annahme zu gründen, dass P! = NP von Goldreich und Goldwasser, und Referenzen davon.

Siehe auch Einwegfunktionen auf der Basis der NP-Härte von Adi Akavia et al.

Darüber hinaus ist bekannt, dass das Decodieren einiger Kryptosysteme NP-hart ist (siehe beispielsweise das McEliece-Kryptosystem oder die Gitter-basierte Kryptographie ). Ich weiß nicht, warum dies das Problem NICHT löst, da ich mit solchen Kryptosystemen nicht vertraut bin. Siehe Peter Shors Kommentare unten.

Ich schlage auch vor, dass Sie einen kurzen Blick auf die Diskussion bei Stackoverflow werfen . Das Lesen der Literatur, in der Impagliazzo zitiert wird, kann ebenfalls aufschlussreich sein.

EDIT: Die folgenden Ergebnisse könnten von Interesse sein:

Feigenbaum und Fortnow. Random-Self-Reducibility von kompletten Sets. SIAM Journal on Computing, 22: 994–1005, 1993.

Bogdanov und Trevisan. Im Worst-Case- bis Average-Case-Bereich für NP-Probleme. In Proceedings of the 44. Annual IEEE Symposium on Foundations of Computer Science, S. 308–317, 2003.

Akavia, Goldreich, Goldwasser und Moshkovitz. Auf der Grundlage von Einwegfunktionen auf der NP-Härte

Gutfreund und Ta-Shma. Neue Zusammenhänge zwischen Derandomisierung, Worst-Case-Komplexität und Average-Case-Komplexität. Technik. Rep. TR06-108, Elektronisches Kolloquium über Computerkomplexität, 2006.

Bogdanov und Trevisan. Durchschnittliche Komplexität. Gefunden Trends Theor. Comput. Sci. 2, 1 (Okt. 2006), 1-106. DOI = http://dx.doi.org/10.1561/0400000004

MS Dousti
quelle
5
Das McEliece-Kryptosystem ist kein Kryptosystem. Es handelt sich um eine ganze Familie von Kryptosystemen, je nachdem, welche Klasse von Fehlerkorrekturcodes Sie verwenden. Wenn Sie willkürliche Fehlerkorrekturcodes verwenden, kann eine Nachricht nur schwer entschlüsselt werden. Wenn Sie eine Klasse von fehlerkorrigierenden Codes mit einem Polynomial-Time-Decoding-Algorithmus verwenden, ist es in der Tat Polynomial-Time, um die Nachricht zu decodieren, aber wir haben keinen Beweis mehr dafür, dass das Brechen des Kryptosystems NP-schwer ist. Die Situation mit gitterbasierter Kryptographie ist besser, aber es ist immer noch nicht schwer, NP zu knacken.
Peter Shor
@ Peter: Vielen Dank! Du hast ein Rätsel gelöst, das mich schon lange fasziniert!
MS Dousti
Tatsächlich scheint es, dass für einige Familien von fehlerkorrigierenden Codes das McEliece-Kryptosystem defekt ist, jedoch nicht für Goppa-Codes, die in McElieces ursprünglichem Vorschlag enthalten waren.
Peter Shor