PPAD und Quantum

Heute wird in New York und auf der ganzen Welt der Geburtstag von Christos Papadimitriou gefeiert. Dies ist eine gute Gelegenheit, nach den Beziehungen zwischen Christos 'Komplexitätsklasse PPAD (und seinen anderen verwandten Klassen) und Quantencomputern zu fragen. In seiner berühmten Arbeit von 1994 stellte Papadimitriou mehrere wichtige Komplexitätsklassen wie PLS, PPAD und andere vor und untersuchte sie systematisch. (Papadimitrious Artikel stützte sich auf einige frühere Artikel, und insbesondere, wie Aviad feststellte, wurde PLS 1988 von Johnson-Papadimitriou-Yannakakis eingeführt.)

Meine Hauptfrage ist:

Quantencomputer einen Vorteil bei Problemen mit ? oder in ? oder in ? usw...$PPAD$$PLS$$PLS \cap PPAD$

Eine andere Frage ist, ob es einige Quantenanaloga von PLS und PPAD sowie von Christos 'anderen Klassen gibt.

Ich stelle fest, dass in diesen Veröffentlichungen kürzlich bemerkenswerte Verbindungen von PPAD zur Kryptographie gefunden wurden: Zur kryptografischen Härte des Findens eines Nash-Gleichgewichts durch N Bitansky, O Paneth, A Rosen und Kann die PPAD-Härte auf kryptografischen Standardannahmen beruhen? von A Rosen, G Segev, I Shahaf und das Finden eines Nash-Gleichgewichts ist nicht einfacher als das Brechen von Fiat-Shamir von Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen und Guy Rothblum. Ich stelle auch fest, dass Christos 'Unterricht meiner Meinung nach besonders nahe an Mathematik und mathematischen Beweisen liegt.

Update: Ron Rothblum kommentierte (über FB), dass die Ergebnisse von Choudhuri, Hubacek, Kamath, Pietrzak, Rosen und G. Rothblum implizieren, dass PPAD plausibel außerhalb der Macht von Quantencomputern liegt. (Ich freue mich über eine ausführliche Antwort, die dies erklärt.)

Noch ein Kommentar: Eine verwandte nette Frage ist, ob das Finden der Senke in einer eindeutigen Einzelorientierung des Würfels einen effizienten Quantenalgorithmus hat. (Ich denke, diese Aufgabe ist einfacher als aber ich bin nicht sicher, wie sie mit .) Dies hängt mit der Suche nach einem Quantenvorteil für siehe /cstheory//a/767/712 . $n$$PLS$$PPAD$$LP$

Alles Gute zum Geburtstag Christos!

Zwei Antworten, die ich beim Schreiben eines Blogposts zu dieser Frage gelernt habe

1. Nein : In Black-Box-Varianten bietet die Komplexität von Quantenabfragen und Kommunikation die quadratische Beschleunigung von Grover, jedoch nicht mehr. Wie Ron betont, erstreckt sich dies unter plausiblen Annahmen auf die Komplexität der Berechnungen.

2. Vielleicht : Das Nash-Gleichgewicht ist wohl das Flaggschiff der "Christos-Klassen". Um den Spielern Zugang zur Quantenverschränkung zu verschaffen, wird ein neues Lösungskonzept des "quantenkorrelierten Gleichgewichts" vorgeschlagen, das das Nash-Gleichgewicht verallgemeinert. Ihre Komplexität ist noch offen. Sehen Sie dieses coole Papier von Alan Deckelbaum.

Und eine historische Anmerkung: PLS wurde 1988 von Johnson-Papadimitriou-Yannakakis eingeführt .

Ich werde versuchen, ein wenig zu erläutern , warum CHKPRR zeigt, dass für Quantencomputer plausibel schwierig ist.$\mathsf{PPAD}$

Auf hoher Ebene erstellt CHKPRR eine Verteilung über End-of-Line-Instanzen, bei denen das Finden einer Lösung Folgendes erfordert:

• die Solidität des Beweissystems zu brechen, das durch Anwenden der Fiat-Shamir-Heuristik auf das berühmte Sumcheck-Protokoll erhalten wird, oder
• Lösen eines -vollständigen Problems$\sharp \mathsf{P}$

Intuitiv beginnt die Reduktion mit einer . Das Zählen erfordert eine exponentielle Anzahl von Polynomschritten; Die Autoren machen diese Zählung inkrementell überprüfbar, indem sie das Zählverfahren einen Zustand beibehalten lassen, der nach jedem Schritt aktualisiert wird, was die Richtigkeit der bisherigen Berechnung beweist. Diese inkrementell überprüfbare Zählprozedur wird dann verwendet, um eine Instanz des Problems der entspannten Senke der überprüfbaren Linie zu erstellen, ein Versprechungsproblem, das in auf Gesamtsuchprobleme reduziert werden kann .$\sharp \mathsf{SAT}$$\mathsf{PPAD}$

Um diese Idee zu instanziieren, besteht die größte technische Herausforderung darin, einen Weg zu finden, um die Zählung schrittweise überprüfbar zu machen: Wir benötigen bei jedem Schritt der Berechnung einen kurzen, nicht interaktiven Beweis, der die Richtigkeit der bisherigen Berechnung demonstriert. Hier ist Nicht-Interaktivität das Kernproblem; in der Tat kennen wir bereits einen kurzen interaktiven Beweis für die Demonstration von Aussagen der Form , wobei ein niedriges -Variat Polynom über ein Feld , was in dieser Einstellung einwandfrei funktionieren würde: das Sumcheck-Protokoll$\sum_{\vec z \in \{0,1\}^n} f(\vec z) = x$$f$$n$$\mathbb{F}$. Die Umwandlung eines interaktiven Beweises in einen nicht interaktiven Beweis (Wahrung der öffentlichen Überprüfbarkeit und Kompaktheit) ist genau das, was die Fiat-Shamir-Heuristik tut.

Fiat-Shamir instanziieren

Die Fiat-Shamir-Heuristik ist sehr einfach: Korrigieren Sie eine Hash-Funktion, beginnen Sie mit einem interaktiven Proof für öffentliche Münzen und ersetzen Sie jede zufällige Nachricht des Verifizierers durch einen Hash des gesamten Transkripts. Die Frage ist dann, unter welcher Eigenschaft der Hash-Funktion wir beweisen können, dass das resultierende Protokoll noch einwandfrei ist (beachten Sie, dass es statistisch nicht mehr einwandfrei sein kann; die Hoffnung ist, dass es rechnerisch einwandfrei bleibt).

Bevor ich darauf eingehe, möchte ich auf Ihren Kommentar eingehen:

Ich verstehe immer noch nicht 1. Sicher gibt es kryptografische Härteannahmen, die im Quantenfall nicht zutreffen. Was macht es für QC schwierig, "Fiat-Shamir zu brechen", im Gegensatz zu "RSA brechen".

Die Beschreibung auf hoher Ebene, die ich gegeben habe, sollte deutlich machen, ich hoffe, dass "Fiat-Shamir brechen" und "RSA brechen" keine wirklich vergleichbaren Probleme sind. RSA ist eine konkrete, spezifische Härteannahme, und wenn Sie große ganze Zahlen berücksichtigen können, können Sie sie brechen.

Andererseits ist die vermutete Härte, Fiat-Shamir zu brechen, eine viel allgemeinere Annahme. Wenn Sie die Fiat-Shamir-Heuristik instanziieren , wählen Sie eine konkrete Auswahl der Hash-Funktion. aber es reicht für das -Härte Ergebnis CHKPRR dass es existiert eine Hash - Funktion , für die Fiat-Shamir - Ton ist. Um Fiat-Shamir mit einem Quantencomputer zu brechen, müsste für jede mögliche Wahl ein Angriff gegen seine Solidität gezeigt werden$\mathsf{PPAD}$der zugrunde liegenden Hash-Funktion. Auf einer intuitiven Ebene ist dies nicht das, was Quantencomputer können, da dies ein Problem ist, das nicht unbedingt eine starke Struktur zu haben scheint, die es ausnutzen könnte (im Gegensatz zu z. B. diskretem Logarithmus und RSA): Hash-Funktionen können typisch sein sehr "unstrukturiert".

Konkreter ausgedrückt gibt es zwei natürliche Alternativen bei der Auswahl einer Hash-Funktion, um Fiat-Shamir zu instanziieren:

Der heuristische, konkret effiziente Ansatz:

Wählen Sie Ihre Lieblings-Hash-Funktion, z. B. SHA-3. Wir haben natürlich keinen Beweis dafür, dass die Instanziierung von Fiat-Shamir mit SHA-3 ein schwieriges Problem darstellt. Wir kennen jedoch auch keinen nicht trivialen Angriff auf die Solidität von Beweissystemen, der durch Anwendung von Fiat-Shamir mit SHA-3 auf ein nicht entartetes interaktives Beweissystem erzielt wird. Dies gilt auch für die Quanteneinstellung: Wir kennen keinen Quantenangriff, der besser ist als die übliche quadratische Beschleunigung, die der Grover-Algorithmus liefert. Nach Jahrzehnten der Kryptoanalyse versucht, ist der Konsens in der Verschlüsselungs Gemeinschaft , dass der Quantenalgorithmus nicht scheinen , so weit wir sehen können superpolynomielle speedups für „Minicrypt-style“ Primitiven (Hash - Funktionen, PRGs, Blockchiffren, etc.) zur Verfügung zu stellen , ohne einige starke zugrunde liegende algebraische Strukturen - wie SHA-2, SHA-3, AES usw.

Der nachweisbare Sicherheitsansatz:

Hier besteht das Ziel darin, eine saubere Eigenschaft der Hash-Funktion zu isolieren, die den heuristischen Klang von Fiat-Shamir erzeugt, und eine Hash-Funktion zu erstellen, die diese Eigenschaften unter plausiblen kryptografischen Annahmen erfüllt.

Dieser nachweisbare Sicherheitsansatz hat eine lange und dichte Geschichte in der Kryptografie. Zu den vielversprechendsten Kandidaten gehört der Begriff der korrelationsunlösbaren Hash-Funktionen : Eine (verschlüsselte) Hash-Funktion wird in Bezug auf eine Beziehung als korrelationsunlösbar bezeichnet, wenn es bei einem zufälligen Hash-Schlüssel rechnerisch nicht durchführbar ist, eine zu finden Eingabe , so daß$R$$K$$x$$(x, H_K(x)) \in R$. Intuitiv erfasst dies auf natürliche Weise, was wir von Fiat-Shamir wollen: In einem interaktiven Beweissystem gibt es, wenn die Solidität statistisch ist, einige "schlechte Überprüfungsnachrichten", die sehr unwahrscheinlich sind, aber dem Prüfer das Betrügen ermöglichen würden. Was wir wollen, ist, dass der Prüfer ein Transkript nicht so berechnen kann, dass er es schafft, eine dieser "schlechten Nachrichten" zu finden, wenn er die nächste Nachricht des Überprüfers durch Hashing berechnet. Jedes interaktive Beweissystem ist daher einer spärlichen Beziehung , die die Paare enthält (Transkript, schlechte Nachricht für dieses Transkript), und Fiat-Shamir ist gesund, wenn es mit einer Hash-Funktion instanziiert wird, die für diese spärliche Beziehung korrelationsunlösbar ist .$R$$R$

Die Frage ist nun, wie korrelationsunlösbare Hash-Funktionen für Beziehungen erstellt werden können, die uns wichtig sind - und in diesem speziellen Kontext für die Beziehung, die dem Sumcheck-Protokoll zugeordnet ist. Hier hat eine neuere Arbeit (im Wesentlichen 1 , 2 , 3 , 4 , 5 , 6 ) gezeigt, dass man für viele interessierende Beziehungen tatsächlich korrelationsunlösbare Hash-Funktionen unter gitterbasierten Annahmen erstellen kann.

Die gitterbasierte Kryptographie ist derzeit die beste Wahl für die Erstellung quantensicherer kryptografischer Grundelemente. Für die meisten Probleme über Gitter, die von der Kryptogemeinschaft berücksichtigt werden, ist kein besserer Quantenalgorithmus bekannt als der übliche "klassische Algorithmus + quadratische Grover-Beschleunigung". Wenn wir also eine korrelationsunlösbare Hash-Funktion für die Sumcheck-Beziehung auf eine gut etablierte Gitterannahme stützen könnten, würde dies in der Krypto-Community als ein sehr starker Hinweis darauf angesehen, dass Quantencomputer Fiat-Shamir nicht immer brechen können (daher nicht können) lösen ).$\mathsf{PPAD}$

Wir sind tatsächlich nicht genau da. Das jüngste Durchbruchsergebnis von Peikert und Shiehian (das letzte Papier in der Liste, das ich zuvor gegeben habe) hat gezeigt, dass wir für wichtige Beziehungen eine korrelationsunlösbare Hash-Funktion unter gut etablierten Gitterproblemen wie Lernen mit Fehlern oder dem SIS-Problem aufbauen können ;; Die Sumcheck-Beziehung wird von dieser Arbeit jedoch nicht erfasst.

CHKPRR, das auf dieser Arbeit aufbaut, hat jedoch gezeigt, dass man eine korrelationsunlösbare Hash-Funktion unter der Annahme aufbauen kann, dass jede der vielen konkreten Konstruktionen vollständig homomorpher Verschlüsselungsschemata eine quasi optimale zirkuläre Sicherheit gegen superpolynomielle Zeitangriffe aufweist.

Lassen Sie uns diese Annahme auflösen:

• Die vollständig homomorphe Verschlüsselung (FHE) ist ein Grundelement, das wir unter einer Vielzahl von Gitterannahmen aufbauen können. Wenn das Schema nur Schaltungen mit begrenzter Größe auswerten muss, wissen wir tatsächlich, wie es unter dem Standardlernen mit Fehlerannahme aufgebaut werden kann.
• Zirkuläre Sicherheit besagt, dass das FHE schwer zu brechen sein sollte, selbst wenn es zum Verschlüsseln seines eigenen geheimen Schlüssels verwendet wird. Dies ist stärker als der übliche Sicherheitsbegriff, der keine schlüsselabhängigen Nachrichten zulässt. Es ist ein großes und seit langem offenes Problem, eine kreisförmig sichere FHE unter einer Standardgitterannahme wie LWE zu erstellen. Noch ein Jahrzehnt nach Gentrys erstem FHE-Bau und vielen Kryptoanalyseversuchen ist die zirkuläre Sicherheit etablierter FHE-Kandidaten selbst zu einer relativ sicher aussehenden Annahme geworden (selbst gegenüber Quantencomputern), und wir kennen keinen Angriff, der den Schlüssel ausnutzt -abhängige Verschlüsselungen auf nicht triviale Weise.
• Quasi-optimale Härte bedeutet, dass alle Polynomalgorithmen eine exponentiell geringe Wahrscheinlichkeit haben, das Schema zu brechen (dh Wahrscheinlichkeit , wobei der Sicherheitsparameter ist). Beachten Sie, dass wir zwar nicht triviale exponentielle Zeitalgorithmen kennen, das Schema jedoch mit nicht vernachlässigbarer Wahrscheinlichkeit in der Zeit für einige brechen würden , wir jedoch keinen polynomiellen Zeitalgorithmus kennen, der die Algorithmen bricht Schema mit einer Wahrscheinlichkeit von für einige .$2^{\omega(\log \lambda) - \lambda}$$\lambda$$2^{c\lambda}$$c < 1$2 - c λ c < 1$2^{-c \lambda}$$c < 1$
• Schließlich möchten wir, dass alle oben genannten Punkte weiterhin gelten, wenn wir dem Angreifer eine superpolynomielle Laufzeit gewähren. Dies steht immer noch im Einklang mit dem, was bekannte Algorithmen erreichen können.

Alles in allem ist dies eindeutig keine großartige, sehr plausible und gut etablierte Annahme. Es stellt jedoch eine sehr interessante Verbindung her: Es verbindet die Härte des Lösens von mit einem Quantencomputer mit der Frage, starke nichttriviale Verbesserungen gegenüber den bekanntesten Quantenalgorithmen zu erzielen, um wichtige anzugreifen (vollständig homomorphe Verschlüsselung) ), was eine gut untersuchte Frage ist.$\mathsf{PPAD}$

Natürlich besteht eine der wichtigsten offenen Fragen von CHKPRR darin, eine korrelationsunlösbare Hash-Funktion für die Sumcheck-Beziehung unter einer besseren gitterbasierten Annahme zu erstellen - idealerweise der LWE-Annahme. Dies erscheint nicht trivial, aber nicht unplausibel, da dies eine sehr junge Arbeit ist, in der bereits viele überraschende Ergebnisse für andere interessante Beziehungen erzielt wurden.