⚛️ quantum physics

MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)

Diese Arbeit generalisiert das MPC-in-the-head-Paradigma auf den Quantenkontext, was die Konstruktion von Drei-Runden-Zero-Knowledge-Arguments sowohl für NP als auch für QMA im Common-Reference-String-Modell ermöglicht, die unter der Standardannahme des Learning With Errors (LWE) gegen Superpositionsangriffe sicher bleiben.

Ursprüngliche Autoren: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Veröffentlicht 2026-07-08

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Beweisen, dass man ein Geheimnis kennt, ohne es zu verraten

Stellen Sie sich vor, Sie haben ein geheimes Passwort (einen „Zeugen“), das beweist, dass Sie berechtigt sind, ein sicheres Gebäude zu betreten. Sie möchten einem Wächter (dem „Verifier“) beweisen, dass Sie das Passwort kennen, ohne ihm tatsächlich zu sagen, wie es lautet. Dies nennt man einen Zero-Knowledge-Beweis (ein Beweis mit Kenntnis ohne Wissenspreisgabe).

In der klassischen Welt (der Welt der normalen Computer) gibt es einen berühmten Trick namens „MPC-in-the-Head“, um dies zu tun.

Die Analogie: Stellen Sie sich vor, Sie sind eine einzelne Person, aber Sie geben vor, ein Team aus fünf Freunden zu sein, die in einem Raum sitzen. Sie teilen Ihr geheimes Passwort in fünf Teile (Shares) auf und geben jedem „Freund“ in Ihrem Kopf ein Stück des Passworts.
Das Spiel: Sie führen ein Gespräch zwischen diesen fünf Freunden, um zu beweisen, dass das Passwort funktioniert. Dann bittet der Wächter darum, die Notizen von nur zwei der Freunde zu sehen.
Das Ergebnis: Wenn die Notizen übereinstimmen und Sinn ergeben, ist der Wächter davon überzeugt, dass das gesamte Team (und damit Sie) das Passwort kennt. Da der Wächter aber nur zwei Freunde gesehen hat, kann er das vollständige Passwort nicht herausfinden.

Das neue Problem: Der „Superposition“-Dieb

Diese Arbeit befasst sich mit einem beängstigenden neuen Problem: Was ist, wenn der Wächter ein Quantencomputer ist?

In der Quantenwelt ist eine „Superposition“ (Überlagerung) so etwas wie das Sein an zwei Orten gleichzeitig. Ein Quanten-Adversary (ein Angreifer) fragt nicht einfach nur nach den Notizen von Freund A oder Freund B. Er kann verlangen, eine Superposition von beiden gleichzeitig zu sehen.

Die Metapher: Stellen Sie sich vor, der Wächter schaut nicht nur auf das Papier; er legt das Papier in eine magische Box, die es ihm ermöglicht, gleichzeitig in jede mögliche Kombination der Notizen der Freunde hineinzuspähen.
Das Risiko: Bei den alten Tricks war das Geheimnis sicher, wenn man nur zwei Freunde zeigte. Aber wenn der Wächter in eine „Superposition“ der Notizen hineinspähen kann, könnte er mathematisch in der Lage sein, das gesamte Passwort zu rekonstruieren, was die Sicherheit aushebeln würde.

Die Autoren fragen sich: Können wir einen Zero-Knowledge-Beweis bauen, der auch dann sicher bleibt, wenn der Wächter diese „Superposition“-Superkraft nutzt?

Die Lösung: „MPC in the Quantum Head“

Die Autoren sagen Ja, und sie erreichen dies, indem sie den „MPC-in-the-Head“-Trick für die Quantenwelt aufrüsten. Sie nennen ihre neue Methode „MPC in the Quantum Head“.

So lösen sie die zwei Hauptherausforderungen:

1. Für reguläre Geheimnisse (NP-Probleme)

Das alte Problem: Frühere Versuche, dies quantensicher zu machen, beruhten auf einer speziellen Art von „magischem Schloss“ (einem Commitment-Schema), das perfekt verborgen war. Aber niemand weiß, wie man solche Schlösser mit Standard-Mathematik baut.
Der neue Trick: Die Autoren verwenden eine andere Art von Schloss, ein „Dual-Mode Commitment“.
- Die Analogie: Stellen Sie sich einen Tresor vor, der zwei Schlüssel hat.
  - Schlüssel A (Binding/Bindend): Der Tresor ist fest verschlossen. Sobald Sie eine Notiz hineingelegt haben, können Sie sie nicht mehr ändern. Aber wenn Sie einen superstarken Computer haben, könnten Sie die Notiz eventuell erraten.
  - Schlüssel B (Hiding/Verbergend): Der Tresor ist so undurchsichtig, dass selbst ein superstarker Computer nicht sehen kann, was sich darin befindet. Aber wenn Sie über eine spezielle „Hintertür“ verfügen (die der Prover besitzt), können Sie ihn öffnen, um alles zu enthüllen, was Sie wollen.
- Wie es funktioniert: Der Prover verwendet den „Hiding“-Modus, um die Notizen zu senden. Da die Notizen verborgen sind, kann der Quanten-Wächter das Geheimnis nicht lernen, selbst wenn er sie in Superposition betrachtet. Die Autoren beweisen, dass selbst mit diesem etwas schwächeren Schloss die Mathematik Bestand hat.

2. Für Quanten-Geheimnisse (QMA-Probleme)

Dies ist der schwierigere Teil. Was ist, wenn das Geheimnis selbst ein Quantenzustand ist (wie eine zarte, unsichtbare Wolke aus Wahrscheinlichkeit) und kein einfaches Passwort?

Die Herausforderung: In der klassischen Version reichen die „Freunde“ sich Notizen zu. In der Quantenversion reichen die „Freunde“ Quantenteilchen (Qubits) zu. Man kann die Notizen eines Quantenteilchens nicht einfach „aufschreiben“, ohne das Geheimnis zu zerstören. Es gibt kein „Transkript“, das man prüfen könnte.
Der neue Trick: Die Autoren verwenden eine Technik namens „Circuit-to-Hamiltonian Reduction“.
- Die Analogie: Stellen Sie sich das Quantengespräch zwischen den Freunden wie einen Film vor. Normalerweise kann man den Film nicht prüfen, ohne ihn ganz anzusehen.
- Stattdessen verwandeln sie den Film in eine gefrorene Skulptur (einen Hamiltonian). Diese Skulptur hat eine bestimmte Form. Wenn die Freunde das Spiel korrekt gespielt haben, hat die Skulptur eine sehr niedrige „Energie“ (sie ist glatt und perfekt). Wenn sie geschummelt haben, ist die Skulptur uneben und hat eine hohe Energie.
- Die Prüfung: Der Wächter fragt nicht nach dem ganzen Film. Er sticht einfach an ein paar zufälligen Stellen auf die Skulptur, um die Energie zu messen.
  - Wenn die Energie niedrig ist, wurde das Spiel korrekt gespielt.
  - Da die Skulptur aus vielen winzigen Teilen besteht, verrät das Anstechen an ein paar Stellen nicht den gesamten Film (das Geheimnis).
Der „Quantum Head“: Der Prover teilt das Quantengeheimnis unter den Freunden auf, verschlüsselt es und erstellt diese „gefrorene Skulptur“ des Gesprächs. Der Wächter prüft die Energie der Skulptur.

Warum das wichtig ist (laut dem Paper)

Das Paper behauptet, zwei spezifische Werkzeuge gebaut zu haben:

Einen Beweis für reguläre Geheimnisse (NP): Er basiert auf einem Standard-Mathematikproblem namens LWE (Learning With Errors), von dem angenommen wird, dass es selbst für Quantencomputer schwer zu knacken ist.
Einen Beweis für Quanten-Geheimnisse (QMA): Dies ist ein bedeutender Durchbruch. Es ist das erste Mal, dass ein Zero-Knowledge-Beweis für Quantenprobleme gebaut wurde, der gegen diese „Superposition“-Angriffe sicher ist, ebenfalls basierend auf der LWE-Annahme.

Zusammenfassung

Das Paper nimmt einen klassischen Trick zum Beweisen von Geheimnissen („MPC-in-the-Head“), rüstet ihn für die Quantenmechanik auf und löst das Problem der „Superposition-Angriffe“. Dies geschieht durch:

Die Verwendung spezieller „Dual-Mode“-Schlösser, die selbst für Quantencomputer schwer zu knacken sind.
Die Verwandlung von Quantengesprächen in „gefrorene Skulpturen“ (Hamiltonians), die überprüft werden können, ohne das Geheimnis preiszugeben.

Dies stellt sicher, dass selbst wenn ein zukünftiger Quantencomputer versucht, in eine Superposition aller Möglichkeiten in ein Beweisverfahren hineinzuspähen, das Geheimnis sicher bleibt.

Technische Zusammenfassung: MPC im Quantenkopf (Superpositions-sichere Zero-Knowledge-Protokolle)

Problemstellung

Die Arbeit befasst sich mit der Konstruktion von Zero-Knowledge (ZK)-Protokollen, die auch dann sicher bleiben, wenn ein böswilliger Verifizierer Herausforderungen (Challenges) stellt und Antworten in Quantensuperposition erhält. Diese „Superpositions-Sicherheit“ ist eine kritische Stärkung der klassischen Sicherheit, motiviert durch Szenarien, in denen Quanten-Adversaries mit klassischen kryptographischen Geräten interagieren oder in denen klassische Primitiven in größere Quantenprotokolle eingebettet sind.

Obwohl Damgård et al. [19] dieses Konzept für NP begründeten, basierte ihre Konstruktion auf perfekt versteckten und unbedinglich bindenden Dual-Mode-Commitments – einem Primitiv, das unter Standard-Kryptographieannahmen nicht bekannt ist. Zudem ließen sich ihre Techniken nicht natürlich auf QMA (Quantum Merlin-Arthur), das Quanten-Analogon zu NP, erweitern, da die Verifizierung von Quantenberechnungen ohne Preisgabe des Quanten-Zeugen (Witness) eine fundamentale Schwierigkeit darstellt.

Bestehende Alternativen, wie etwa Non-Interactive Zero-Knowledge (NIZK)-Beweise, sind für QMA unter Standardannahmen entweder unbekannt oder beruhen auf heuristischen Modellen (z. B. Quanten-Random-Oracles oder Obfuskation). Zudem sind NIZKs im Allgemeinen schwerfälliger als die dreiründigen $\Sigma$ -Protokolle, die aus Effizienzgründen bevorzugt werden.

Methodik

Die Autoren schlagen eine Verallgemeinerung des MPC-in-the-Head-Paradigmas [30] für den Quantenkontext vor, bezeichnet als „MPC im Quantenkopf“. Die Kernmethodik umfasst zwei distinkte, aber verwandte Konstruktionen:

1. Superpositions-sicheres ZK für NP

Die Autoren überarbeiten das Protokoll von Damgård et al. [19] und ersetzen die Anforderung an perfekt versteckte Commitments durch Dual-Mode-Commitments (statistisch versteckt und computergestützt bindend in einem Modus; perfekt bindend und computergestützt versteckt im anderen Modus).

Technik: Die Beweisstrategie nutzt ein Hybrid-Argument. In der realen Welt sind die Commitments auf die MPC-Ansichten (Views) bezogen. In einem Hybrid werden die Commitments in den statistisch versteckten Modus umgeschaltet. Entscheidend ist, dass die Autoren ein Hybrid einführen, in dem die Prover auf 0 committet (anstatt auf ehrliche Ansichten), diese aber unter Ausnutzung der computergestützten Bindungseigenschaft (die durch einen unbeschränkten Simulator gebrochen werden kann) auf die ehrlichen Ansichten öffnen kann.
Sicherheitsargument: Sob展開 die Commitments auf 0 liegen, bilden die geöffneten Ansichten (eine Teilmenge der Shares) und die nicht geöffneten Commitments ein perfekt sicheres Secret-Sharing-Schema. Die Autoren nutzen ein Lemma aus [19], das besagt, dass perfektes Secret Sharing gegenüber Superpositions-Angriffen sicher bleibt, sofern weniger als $2t$ Shares abgefragt werden (wobei $t$ der Privacy-Schwellenwert ist). Dies ermöglicht es, dass der Sicherheitsbeweis fortgesetzt werden kann, ohne perfekt versteckte Commitments zu benötigen.

2. MPC im Quantenkopf für QMA

Die Erweiterung auf QMA erfordert den Umgang mit Quanten-Zeugen und Quanten-Verifikationsschaltkreisen.

Das Hindernis: Im klassischen MPC-in-the-Head werden „Ansichten“ (Transkripte) von Parteien enthüllt. In der Multiparty Quantum Computation (MPQC) tauschen Parteien Quanten-Nachrichten aus, was bedeutet, dass es keinen klassischen Transkript gibt, den man enthüllen könnte; eine Partei hält lediglich einen finalen Quantenzustand.
Die Lösung: Die Autoren modellieren das globale MPQC-Protokoll als Quantenschaltkreis (ersetzen Nachrichtenübertragung durch SWAP-Gates). Sie wenden darauf Kitaevs Circuit-to-Hamiltonian-Reduktion [34] an.
- Der „Zeuge“ wird zum History-State des Hamiltonians, der eine niedrige Energie aufweist, wenn und nur wenn der MPQC akzeptiert.
- Der Prover committet diesen History-State (Qubit für Qubit) mittels eines Quantum One-Time Pads (QOTP) und committet die QOTP-Keys mittels Dual-Mode-Commitments.
- Der Verifizierer fordert den Prover auf, spezifische Qubits zu öffnen, die den lokalen Hamiltonian-Termen entsprechen.
Verifikation: Der Verifizierer misst die geöffneten Qubits, um die lokalen Hamiltonian-Terme zu prüfen. Wenn die Energie niedrig ist, entspricht der History-State einer gültigen Ausführung.
Zero-Knowledge: Die ZK-Eigenschaft beruht darauf, dass das Öffnen einer Teilmenge von Qubits, die zu einem lokalen Hamiltonian-Term gehören, nicht mehr Informationen preisgibt, als die Kontrolle über eine Teilmenge der Parteien im zugrunde liegenden MPQC. Die Autoren nutzen ein perfekt $2t$ -privates MPQC-Protokoll [17, 39], um sicherzustellen, dass der History-State der Berechnung auf einem Secret-Shared-Witness unter Superpositions-Abfragen ununterscheidbar von einem History-State auf einem Dummy-Input bleibt.

Zentrale Beiträge

Verallgemeinerung von MPC-in-the-Head: Die Arbeit präsentiert die erste Instanziierung des MPC-in-the-Head-Paradigmas für Quantenfunktionalitäten (MPQC) und schafft effektiv ein „Quantum MPC-in-the-Head“.
Superpositions-sicheres ZK für NP: Die Autoren konstruieren ein dreiründiges $\Sigma$ -Protokoll für NP, das gegen Superpositions-Angriffe sicher ist, basierend auf beliebigen Post-Quantum Dual-Mode-Commitments (z. B. aus LWE). Dies verbessert [19], indem die Notwendigkeit nicht-standardmäßiger perfekt versteckter Commitments entfällt.
Superpositions-sicheres ZK für QMA: Die Arbeit konstruiert das erste dreiründige $\Sigma$ -Protokoll für QMA, das gegenüber Superpositions-Angriffen sicher ist, basierend auf der Learning With Errors (LWE) Annahme. Dies füllt eine Lücke, in der keine Standard-Annahme-basierten NIZKs für QMA existierten.
Neue Beweistechniken:
- Ein neuartiges Hybrid-Argument für NP, das Commitments auf 0 umschaltet, um die Eigenschaften von perfektem Secret Sharing gegenüber Superpositions-Angriffen zu nutzen.
- Eine Technik für QMA, die die Circuit-to-Hamiltonian-Reduktion mit MPQC und QOTP kombiniert und die Ununterscheidbarkeit von EPR-Paaren und One-Time-Pads nutzt, um das Protokoll in Gegenwart von Superpositions-Abfragen zu simulieren.

Ergebnisse

Die Arbeit etabliert folgende Theoreme (informell):

Theorem 1.1: Unter der Annahme der Post-Quantum-Sicherheit von LWE existieren dreiründige $\Sigma$ -Protokolle für QMA im Common Reference String (CRS) Modell, die Zero-Knowledge gegenüber böswilligen Verifizierern erfüllen, die Superpositions-Abfragen stellen.
Theorem 1.2: Unter der Annahme der Existenz jeglicher Post-Quantum Dual-Mode-Commitments existieren dreiründige $\Sigma$ -Protokolle für NP im CRS-Modell, die Zero-Knowledge gegenüber böswilligen Verifizierern erfüllen, die Superpositions-Abfragen stellen.

Die Protokolle erreichen statistische Soundness und computergestütztes Zero-Knowledge (selbst gegenüber Quanten-Polynomialzeit-Adversaries mit Superpositions-Zugriff).

Bedeutung und Ansprüche

Die Autoren positionieren diese Arbeit als natürliche und notwendige Erweiterung der Zero-Knowledge-Kryptographie in das Quantenregime.

Theoretische Bedeutung: Sie löst das offene Problem der Konstruktion von Superpositions-sicherem ZK für QMA unter Standardannahmen – eine Aufgabe, die aufgrund des Mangels an geeigneten NIZKs oder Commitment-Schemata als schwierig galt.
Praktische Relevanz: Die dreiründige Struktur macht diese Protokolle signifikant leichter als NIZKs, was einen praktischen Weg für Post-Quantum-Signaturen und sichere Multiparty-Computation-Compiler (z. B. GMW-Stil-Compiler) bietet, die gegenüber Quanten-Adversaries mit Superpositions-Fähigkeiten sicher bleiben müssen.
Konzeptioneller Fortschritt: Das „MPC im Quantenkopf“-Framework wird als generalisierbare Technik präsentiert, die auf andere Commit-and-Open oder Cut-and-Choose Protokolle angewendet werden kann, die eine partielle Verifikation von Quantenberechnungen erfordern.

Die Arbeit stellt explizit fest, dass während NIZKs für QMA in Oracle-Modellen oder mit Designated-Verifier existieren, ihr Fokus auf dreiründigen Protokollen mit Standardannahmen und öffentlichem Setup (CRS) eine direktere und effizientere Lösung für das spezifische Bedrohungsszenario von Superpositions-Angriffen bietet.