⚛️ quantum physics

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

Dit artikel generaliseert het MPC-in-the-head-paradigma naar de kwantumsetting, wat de constructie van drie-ronde zero-knowledge arguments mogelijk maakt voor zowel NP als QMA in het common reference string-model die veilig blijven tegen superpositie-aanvallen op basis van de standaard Learning With Errors (LWE)-aanname.

Oorspronkelijke auteurs: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Gepubliceerd 2026-07-08

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Bewijzen dat je een Geheim Kent Zonder het te Laten Zien

Stel je voor dat je een geheim wachtwoord hebt (een "getuige") dat bewijst dat je een beveiligd gebouw mag betreden. Je wilt een bewaker (de "verifieerder") ervan overtuigen dat je het wachtwoord weet, zonder hen daadwerkelijk te vertellen wat het is. Dit wordt een Zero-Knowledge Proof genoemd.

In de klassieke wereld (de wereld van gewone computers) is er een beroemde truc genaamd "MPC-in-the-Head" om dit te doen.

De Analogie: Stel je voor dat je één persoon bent, maar je doet alsof je een team van vijf vrienden bent die in een kamer zitten. Je splitst je geheime wachtwoord in vijf stukjes (shares) en geeft elk stukje aan een andere "vriend" in je hoofd.
Het Spel: Je voert een gesprek tussen deze vijf vrienden om te bewijzen dat het wachtwoord werkt. Vervolgens vraat de bewaker om de aantekeningen van slechts twee van de vrienden te zien.
Het Resultaat: Als de aantekeningen overeenkomen en logisch zijn, is de bewaker ervan overtuigd dat het hele team (en dus jij) het wachtwoord kent. Maar omdat de bewaker slechts twee vrienden heeft gezien, kan hij het volledige wachtwoord niet achterhalen.

Het Nieuwe Probleem: De "Superpositie" Dief

Dit artikel pakt een eng nieuw probleem aan: Wat als de bewaker een kwantumcomputer is?

In de kwantumwereld is een "superpositie" als het ware op twee plaatsen tegelijk zijn. Een kwantum-adversary (de slechterik) vraagt niet alleen om de aantekeningen van Vriend A of Vriend B te zien. Ze kunnen vragen om een superpositie van beide tegelijkertijd te zien.

De Metafoor: Stel je voor dat de bewaker niet alleen naar het papier kijkt, maar het papier in een magische doos plaatst waarmee ze tegelijkertijd in elke mogelijke combinatie van de aantekeningen van de vrienden kunnen gluren.
Het Risico: In de oude trucs was het geheim veilig als je slechts twee vrienden liet zien. Maar als de bewaker in een "superpositie" van de aantekeningen kan gluren, kunnen ze het volledere wachtwoord wiskundig reconstrueren, wat de beveiliging breekt.

De auteurs vragen zich af: Kunnen we een Zero-Knowledge bewijs bouwen dat veilig blijft, zelfs als de bewaker deze "superpositie"-superkracht gebruikt?

De Oplossing: "MPC in the Quantum Head"

De auteurs zeggen ja, en ze doen dit door de "MPC-in-the-Head"-truc te upgraden voor de kwantumwereld. Ze noemen hun nieuwe methode "MPC in the Quantum Head."

Zo lossen ze de twee belangrijkste uitdagingen op:

1. Voor Gewone Geheimen (NP-problemen)

Het Oude Probleem: Eerdere pogingen om dit kwantumveilig te maken, vertrouwden op een speciaal type "magisch slot" (een commitment scheme) dat perfect verborgen was. Maar niemand weet hoe je deze sloten kunt bouwen met standaard wiskundige aannames.
De Nieuwe Truk: De auteurs gebruiken een ander soort slot, een "Dual-Mode Commitment."
- De Analogie: Stel je een kluis voor die twee sleutels heeft.
  - Sleutel A (Binding): De kluis zit stevig dicht. Zodra je een brief erin hebt gelegd, kun je deze niet meer veranderen. Maar als je een superkrachtige computer hebt, kun je misschien de inhoud raden.
  - Sleutel B (Hiding): De kluis is zo ondoorzichtig dat zelfs een superkrachtige computer niet kan zien wat erin zit. Maar, als je een speciale "achterdeur" hebt (die de prover heeft), kun je hem openen om alles te onthullen wat je wilt.
- Hoe het werkt: De prover gebruikt de "Hiding"-modus om de aantekeningen te versturen. Omdat de aantekeningen verborgen zijn, kan de kwantum-bewaker het geheim niet leren, zelfs niet als ze in superpositie naar de aantekeningen kijken. De auteurs bewijzen dat zelfs met dit iets zwakkere slot, de wiskunde standhoudt.

2. Voor Kwantum-geheimen (QMA-problemen)

Dit is het moeilijkere deel. Wat als het geheim zelf een kwantumtoestand is (zoals een delicate, onzichtbare wolk van waarschijnlijkheid) in plaats van een simpel wachtwoord?

De Uitdaging: In de klassieke versie wisselen de "vrienden" aantekeningen met elkaar uit. In de kwantumversie wisselen de "vrienden" kwantumdeeltjes (qubits) uit. Je kunt de aantekeningen van een kwantumdeeltje niet zomaar "opschrijven" zonder het geheim te vernietigen. Er is geen "transcript" om te controleren.
De Nieuwe Truk: De auteurs gebruiken een techniek genaamd "Circuit-to-Hamiltonian Reduction."
- De Analogie: Stel je voor dat het kwantumgesprek tussen de vrienden een film is. Normaal gesproken kun je de film niet controleren zonder de hele film te bekijken.
- In plaats daarvan veranderen ze de film in een bevroren sculptuur (een Hamiltonian). Deze sculptuur heeft een specifieke vorm. Als de vrienden het spel correct hebben gespeeld, heeft de sculptuur een zeer lage "energie" (het is glad en perfect). Als ze hebben gesjoemeld, is de sculptuur hobbelig en heeft het een hoge energie.
- De Controle: De bewaker vraat niet om de hele film te zien. Ze prikken gewoon op een paar willekeurige plekken op de sculptuur om de energie te meten.
  - Als de energie laag is, is het spel correct gespeeld.
  - Omdat de sculptuur uit veel kleine onderdelen bestaat, onthult het prikken op een paar plekken niet de hele film (het geheim).
De "Quantum Head": De prover splitst het kwantumgeheim onder de vrienden, versleutelt het, en creëert deze "bevroren sculptuur" van het gesprek. De bewaker controleert de energie van de sculptuur.

Waarom dit ertoe doet (volgens het artikel)

Het artikel beweert dat het twee specifieke instrumenten heeft gebouwd:

Een bewijs voor gewone geheimen (NP): Dit werkt op basis van een standaard wiskundig probleem genaamd LWE (Learning With Errors), waarvan wordt aangenomen dat het zelfs voor kwantumcomputers moeilijk is.
Een bewijs voor kwantumgeheimen (QMA): Dit is een grote doorbraak. Dit is de eerste keer dat een Zero-Knowledge bewijs voor kwantumproblemen is gebouwd dat beveiligd is tegen deze "superpositie"-aanvallen, eveneens gebaseerd op de LWE-aanname.

Samenvatting

Het artikel neemt een klassieke truc om geheimen te bewijzen ("MPC-in-the-Head"), upgrade deze voor de kwantummechanica, en lost het probleem van "superpositie-aanvallen" op. Dit doen ze door:

Speciale "dual-mode" sloten te gebruiken die moeilijk te kraken zijn, zelfs door kwantumcomputers.
Kwantumgesprekken te veranderen in "bevroren sculpturen" (Hamiltonians) die gecontroleerd kunnen worden zonder het geheim te onthullen.

Dit zorgt ervoor dat zelfs als een toekomstige kwantumcomputer probeert te gluren in een "superpositie" van alle mogelijkheden, het geheim veilig blijft.

Technische Samenvatting: MPC in de Quantum Head (Superpositie-veilige Zero-Knowledge)

Probleemstelling

Het artikel behandelt de constructie van Zero-Knowledge (ZK) protocollen die veilig blijven, zelfs wanneer een kwaadwillige verifieerder uitdagingen (challenges) uitgeeft en responsen ontvangt in kwantumsuperpositie. Deze "superpositie-beveiliging" is een cruciale versterking van klassieke beveiliging, gemotiveerd door scenario's waarin kwantum-adversaries interageren met klassieke cryptografische apparaten of waar klassieke primitieven zijn ingebed in grotere kwantumprotocollen.

Hoewel Damgård et al. [19] dit concept voor NP pionierden, vertrouwde hun constructie op perfect verborgen en onvoorwaardelijk bindende dual-mode commitments, een primitief dat niet bekend is om te bestaan onder standaard cryptografische aannames. Bovendien lieten hun technieken zich niet natuurlijk uitbreiden naar QMA (Quantum Merlin-Arthur), de kwantumanaloog van NP, vanwege de fundamentele moeilijkheid om kwantumcomputaties te verifiëren zonder de kwantumgetuige (witness) te onthullen.

Bestaande alternatieven, zoals Non-Interactive Zero-Knowledge (NIZK) bewijzen, zijn ofwel onbekend voor QMA onder standaard aannames, of vertrouwen op heuristische modellen (bijv. kwantum random oracles of obfuscation). Daarnaast zijn NIZK's over het algemeen zwaarder dan de drie-rondes $\Sigma$ -protocollen die de voorkeur genieten vanwege efficiëntie.

Methodologie

De auteurs stellen een generalisatie voor van het MPC-in-the-Head paradigma [30] naar de kwantumsetting, getiteld "MPC in de Quantum Head." De kernmethodologie omvat twee verschillende maar gerelateerde constructies:

1. Superpositie-veilige ZK voor NP

De auteurs herzien het protocol van Damgård et al. [19], maar vervangen de vereiste voor perfect verborgen commitments door dual-mode commitments (statistisch verborgen, computationeel bindend in de ene modus; perfect bindend, computationeel verborgen in de andere modus).

Techniek: De bewijsstrategie maakt gebruik van een hybride argument. In de echte wereld zijn de commitments aan de MPC-views. In een hybride worden de commitments gewisseld naar de statistisch verborgen modus. Cruciaal is dat de auteurs een hybride introduceren waarbij de prover commit aan 0 (in plaats van eerlijke views), maar deze nog steeds kan openen naar de eerlijke views met behulp van de computationele bindende eigenschap (die wordt doorbroken door een onbegrensde simulator).
Beveiligingsargument: Zodra de commitments aan 0 zijn, vormen de geopende views (een subset van shares) en de niet-geopende commitments een perfect veilig secret sharing schema. De auteurs maken gebruik van een lemma uit [19] dat stelt dat perfecte secret sharing veilig blijft tegen superpositie-aanvallen als minder dan $2t$ shares worden opgevraagd (waarbij $t$ de privacy-drempel is). Dit maakt het mogelijk om de beveiliging te bewijzen zonder dat perfect verborgen commitments vereist zijn.

2. MPC in de Quantum Head voor QMA

Het uitbreiden hiervan naar QMA vereist het afhandelen van kwantumgetuigen en kwantumverificatiecircuits.

Het obstakel: In klassieke MPC-in-the-Head geeft de prover "views" (transcripts) van partijen vrij. In Multiparty Quantum Computation (MPQC) wisselen partijen kwantumberichten uit, wat betekent dat er geen klassieke transcript beschikbaar is om vrij te geven; een partij houdt slechts een finale kwantumtoestand vast.
De oplossing: De auteurs modelleren het globale MPQC-protocol als een kwantumcircuit (waarbij berichtuitwisseling wordt vervangen door SWAP-gates). Ze passen Kitaev's Circuit-to-Hamiltonian reductie [34] toe op dit circuit.
- De "getuige" wordt de history state van de Hamiltonian, die een lage energie heeft indien en slechts indien de MPQC accepteert.
- De prover commit aan deze history state (qubit-voor-qubit) met behulp van een Quantum One-Time Pad (QOTP) en commit aan de QOTP-sleutels met dual-mode commitments.
- De verifieerder daagt de prover uit om specifieke qubits te openen die overeenkomen met lokale Hamiltonian-termen.
Verificatie: De verifieerder meet de geopende qubits om de lokale Hamiltonian-termen te controleren. Als de energie laag is, komt de history state overeen met een geldige uitvoering.
Zero-Knowledge: De ZK-eigenschap berust op het feit dat het openen van een subset qubits die overeenkomen met een lokale Hamiltonian-term niet meer informatie onthult dan het controleren van een subset partijen in het onderliggende MPQC-protocol. De auteurs maken gebruik van een perfect $2t$ -private MPQC protocol [17, 39] om te garanderen dat de history state van de computation op een geheim-gedeelde getuige ononderscheidbaar blijft van een history state op een dummy-input, zelfs onder superpositie-queries.

Belangrijkste Bijdragen

Generalisatie van MPC-in-the-Head: Het artikel presenteert de eerste instantiatie van het MPC-in-the-Head paradigma voor kwantumfunctionaliteiten (MPQC), wat effectief een "Quantum MPC-in-the-Head" creëert.
Superpositie-veilige ZK voor NP: De auteurs construeren een drie-rondes $\Sigma$ -protocol voor NP dat veilig is tegen superpositie-aanvallen op basis van elke post-kwantum dual-mode commitment (bijv. uit LWE). Dit is een verbetering ten opzie van [19] door de noodzaak voor niet-standaard perfect verborgen commitments weg te nemen.
Superpositie-veilige ZK voor QMA: Het artikel construeert het eerste drie-rondes $\Sigma$ -protocol voor QMA dat veilig is tegen superpositie-aanvallen, gebaseerd op de Learning With Errors (LWE) aanname. Dit vult een gat waar geen standaard-aanname NIZK's voor QMA bestaan.
Nieuwe Bewijstechnieken:
- Een nieuw hybride argument voor NP dat commitments naar 0 wisselt om de eigenschappen van perfect secret sharing tegen superpositie-aanvallen te benutten.
- Een techniek voor QMA die Circuit-to-Hamiltonian reductie combineert met MPQC en QOTP, waarbij de ononderscheidbaarheid van EPR-paren en one-time pads wordt gebruikt om het protocol te simuleren in de aanwezigheid van superpositie-queries.

Resultaten

Het artikel stelt de volgende stellingen vast (informeel):

Stelling 1.1: Onder de post-kwantum veiligheid van LWE bestaan er drie-rondes $\Sigma$ -protocollen voor QMA in het Common Reference String (CRS) model die voldoen aan zero-knowledge tegen kwaadwillende verifieerders die superpositie-queries uitvoeren.
Stelling 1.2: Onder de aanname van de existentie van enige post-kwantum dual-mode commitments, bestaan er drie-rondes $\Sigma$ -protocollen voor NP in het CRS-model die voldoen aan zero-knowledge tegen kwaadwillende verifieerders die superpositie-queries uitvoeren.

De protocollen bereiken statistische soundness en computationele zero-knowledge (zelfs tegen kwantum-polynomial-time adversaries met superpositie-toegang).

Betekenis en Claims

De auteurs positioneren dit werk als een natuurlijke en noodzakelijke uitbreiding van zero-knowledge cryptografie naar het kwantumdomein.

Theoretisch belang: Het lost het openstaande probleem op van het construeren van superpositie-veilige ZK voor QMA onder standaard aannames, een taak die voorheen als moeilijk werd beschouwd vanwege het gebrek aan geschikte NIZK's of commitment-schema's.
Praktische relevantie: De drie-rondes structuur maakt deze protocollen aanzienlijk lichter dan NIZK's, wat een praktische weg biedt voor post-kwantum signaturen en veilige multiparty computation compilers (bijv. GMW-stijl compilers) die veilig moeten blijven tegen kwantum-adversaries die in staat zijn tot superpositie-aanvallen.
Conceptuele vooruitgang: Het "MPC in de Quantum Head" framework wordt gepresenteerd als een generaliseerbare techniek die kan worden toegepast op andere commit-and-open of cut-and-choose protocollen die een gedeeltelijke verificatie van kwantumcomputaties vereisen.

Het artikel merkt expliciet op dat hoewel NIZK's voor QMA bestaan in oracle-modellen of met designated verifiers, hun focus op drie-rondes protocollen met standaard aannames en publieke setup (CRS) een directere en efficiëntere oplossing biedt voor het specifieke dreigingsmodel van superpositie-aanvallen.