⚛️ quantum physics

Verifiable and Collusion-Resistant Multi-Party Quantum Private Set Operations

Dit artikel stelt een verifieerbaar en collusiebestendig multi-party quantum private set intersection-protocol voor dat expliciete cardinaliteitstesten mogelijk maakt zonder een vertrouwde derde partij die de resultaten interpreteert, gebruikmakend van een op rotatie gebaseerde quantumconstructie gecombineerd met oblivious linear evaluation en garbled circuits om enkel te onthullen of de intersectie een drempelwaarde bereikt.

Oorspronkelijke auteurs: Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

Gepubliceerd 2026-06-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

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

Stel je een groep vrienden voor, die elk een geheime lijst met hun favoriete films vasthouden. Ze willen ontdekken welke films ze allemaal leuk vinden zonder dat iemand zijn volledige lijst aan de anderen onthult. In de digitale wereld wordt dit Private Set Intersection (PSI) genoemd.

Stel je nu voor dat deze groep vrienden enorm groot is en ze een super slimme, krachtige computer gebruiken (laten we die de "Server" noemen) om het rekenwerk voor hen te doen. Het probleem? Wat als de Server een beetje sluw is? Wat als de Server probeert in de lijsten te gluren, of wat als de Server samenwerkt met een van de vrienden om te bedriegen?

Dit artikel presenteert een nieuwe, hoogtechnologische oplossing genaamd MP-QPSI (Multi-Party Quantum Private Set Intersection). Het maakt gebruik van de vreemde wetten van de kwantumfysica om deze problemen op te lossen. Hier is hoe het werkt, eenvoudig uitgelegd:

De personages

De Vrienden (Deelnemers): Zij hebben de geheime lijsten. Ze zijn "lichtgewicht", wat betekent dat ze geen krachtige computers hebben; ze hoeven alleen maar een beetje kwantummagie te gebruiken om hun gegevens te vergrendelen.
De Server (Derde Partij/TP): Een krachtige kwantumcomputer die al het zware werk doet. Het wordt ervan uit gegaan dat deze de wiskunde uitvoert, maar het protocol gaat ervan uit dat de Server kan proberen te bedriegen of te gluren.
De Scheidsrechter (Vertrouwde Autoriteit/TA): Een neutrale partij die het spel opzet, sleutels uitdeelt en de eindresultaten controleert om er zeker van te zijn dat niemand heeft valsgespeeld.

Het kernprobleem: De "Sluwe Server"

In oudere versies van deze technologie werd aangenomen dat de Server eerlijk zou zijn, of in ieder geval niet zou samenwerken met de vrienden. Als de Server en een vriend zouden samenwerken (collusie), zouden ze de geheimen van iedereen kunnen stelen. Dit artikel lost dit op door het onmogelijk te maken voor de Server en een aantal vrienden om samen de code te breken.

Hoe het werkt: De "Kwantumenvelop" en de "Valstrik"

Denk aan het proces als het versturen van een pakketje door een beveiligde tunnel:

1. De gegevens vergrendelen (Encryptie)
Elke vriend stopt zijn filmlijst in een speciale Kwantumenvelop.

Het Magische Slot: Ze gebruiken een "Quantum One-Time Pad". Stel je een slot voor dat elke keer dat je ernaar kijkt, willekeurig van vorm verandert. Voor de Server ziet de envelop eruit als pure statische ruis (willekeurige ruis). Het is onmogelijk om te zien wat erin zit zonder de specifieke sleutel.
De Valstrikken: In de envelop verstoppen de vrienden "valstrikken" — zoals kleine alarmbelletjes. Als de Server de envelop probeert te openen of ermee rommelt, gaat het alarm af.
De Geheime Splitsing: De sleutels om deze enveloppen te ontgrendelen worden niet door één persoon vastgehouden. In plaats daarvan snijdt de Scheidsrechter de hoofdsleutel in stukken en geeft een stukje aan elke vriend. Je hebt een bepaald aantal vrienden (een "drempelwaarde") nodig om de stukjes bij elkaar te leggen en de uiteindelijke resultaten te openen. Dit voorkomt dat een enkele vriend samen met de Server de sleutels kan stelen.

2. Het rekenwerk uitvoeren (Homomorfe Evaluatie)
De Server ontvangt al deze vergrendelde, wazige enveloppen.

De Magische Truk: Ondanks dat de enveloppen vergrendeld zijn, kan de Server de "EN"-operatie uitvoeren (het vinden van de gemeenschappelijke films) zonder ze ooit te openen. Het is alsof een chef de ingrediënten kan mengen in een verzegelde, ondoorzichtige zak en het resultaat kan vertellen zonder de ingrediënten ooit te hebben gezien.
Het Logboek: Terwijl de Server de berekeningen uitvoert, houdt hij een gedetailleerd "bewijs" (logboek) bij van elke stap die hij heeft genomen.

3. Het werk controleren (Verificatie)
Zodra de Server klaar is, stuurt hij het resultaat en het bewijs terug.

De Vrienden controleren het Bewijs: De vrienden bekijken het bewijs om er zeker van te zijn dat de Server de regels heeft gevolgd en niet de wiskunde heeft vervangen door iets anders.
De Scheidsrechter controleert de Valstrikken: De Scheidsrechter opent de laatste envelop. Eerst controleert de Scheidsrechter de "alarmbelletjes" (valstrikken). Als de Server geprobeerd heeft te gluren of te bedriegen, zijn de valstrikken geactiveerd en weet de Scheidsrechter dit onmiddellijk.
De Laatste Ontgrendeling: Als alles klopt, combineren de vrienden hun stukjes sleutel om de uiteindelijke antwoord te ontgrendelen: de lijst met films die ze allemaal delen.

Waarom is dit bijzonder?

Geen Sluwe Samenwerkingen: Zelfs als de Server probeert samen te werken met een paar vrienden, kunnen ze de geheimen niet stelen omdat de sleutel is verdeeld. Ze hebben te veel vrienden nodig om het te ontgrendelen.
De Bedrieger Betrappen: Als de Server de verkeerde wiskunde uitvoert of in de gegevens probeert te gluren, zal het "valstrik"-systeem en de controle van het bewijs hen betrappen. De vrienden zullen weten dat het resultaat nep is en het verwerpen.
Flexibel: Het artikel laat zien dat dit systeem niet alleen bedoeld is voor het vinden van gemeenschappelijke films. Door een paar schakelaars in het "circuit" te veranderen, kan het ook de unie (alle unieke films gecombineerd) vinden of simpelweg tellen hoeveel films ze met elkaar delen.

De Kernboodschap

Dit artikel stelt een manier voor waarop veel mensen samen privé berekeningen kunnen uitvoeren met behulp van een krachtige, potentieel onbetrouwbare computer. Het gebruikt kwantumsloten om de gegevens te verbergen, gesplitste sleutels om samenwerking (collusie) te voorkomen en kwantumvalstrikken om bedriegers te betrappen. Het is als een hoogwaardig pokerspel waarbij de dealer (Server) de kaarten kan schudden maar ze nooit kan zien, en als hij probeert te vals te spelen, hebben de spelers een waterdichte manier om dat te bewijzen.

Technische Samenvatting: Verifieerbare en Collusie-resistente Multi-Party Quantum Private Set Operations

1. Probleemstelling

Private Set Operations (PSO), inclusief Private Set Intersection (PSI) en Union (PSU), zijn fundamenteel voor Secure Multiparty Computation (SMC). Hoewel er klassieke cryptografische oplossingen bestaan, vormen quantumalgoritmen (bijv. Shor's algoritme) een bedreiging voor huidige getaltheoretische schema's. Daarom is de focus verschoven naar Quantum PSI (QPSI).

Echter, bestaande Quantum PSO (QPSO) protocollen kampen met aanzienlijke beperkingen:

Bedreigingsmodellen: De meeste bestaande QPSI-schema's gaan uit van een semi-eerlijke vertrouwde derde partij (TP) of vertrouwen op aannames dat de TP niet kan colluderen met een deelnemer.
Collusie-resistentie: Eerdere multi-party QPSI (MP-QPSI) protocollen falen vaak in het weerstaan van collusie tussen de TP en een subset van deelnemers, of ze tolereren slechts de corruptie van een enkele deelnemer.
Verifieerbaarheid: Veel schema's missen mechanismen om te verifiëren of de TP het voorgeschreven quantumcircuit correct heeft uitgevoerd, wat het systeem kwetsbaar maakt voor kwaadwillige afwijkingen.

2. Methodologie

De auteurs stellen een Multi-Party Quantum Private Set Intersection (MP-QPSI) protocol voor dat Verifiable Quantum Fully Homomorphic Encryption (vQFHE) integreert met Threshold Fully Homomorphic Encryption (TFHE). Het protocol opereert in een model bestaande uit $n$ data-houdende deelnemers, een krachtige quantum TP, en een Trusted Authority (TA).

Kerncomponenten

Threshold Key Management (TFHE):
- De geheime sleutel voor decryptie wordt gedeeld onder $n$ deelnemers met behulp van een $(t, n)$ -threshold secret sharing schema.
- Decryptie vereist dat ten minste $t$ deelnemers samenwerken. Dit zorgt ervoor dat noch een subset van gecorrumpeerde deelnemers, noch een collusie tussen de TP en minder dan $t$ deelnemers de geheime sleutel kan achterhalen of private inputs kan leren.
Verifiable Quantum Evaluation (vQFHE):
- Het protocol maakt gebruik van de TrapTP constructie (uit [ADS+17]) als de vQFHE-laag.
- Encryptie: Deelnemers coderen hun private sets in quantumtoestanden met behulp van CSS-codes, voegen trap qubits toe ( $|0\rangle$ en $|+\rangle$ ), passen een willekeurige permutatie toe en maskeren het resultaat met een Quantum One-Time Pad (QOTP). De QOTP-sleutels worden geëncrypt de onder TFHE en geauthenticeerd met Message Authentication Codes (MAC).
- Evaluatie: De TP voert een homomorfe evaluatie uit van een multi-party AND-circuit ( $C_{\text{AND}}$ ) op de geëncrypteerde quantumtoestanden. De TP actualiseert de geëncrypteerde QOTP-sleutels homomorf en verbruikt "gadgets" (magic states) om non-Clifford (T) gates af te handelen, volgens het garden-hose model.
- Verificatie: De TP genereert een klassiek transcript (log) van de evaluatie. Deelnemers en de TA verifiëren dit log tegen de MAC's, de gate array en de trap code metingen om te garanderen dat de TP niet is afgeweken van het doelcircuit.
Protocolflow:
- Fase 1 (Voorbereiding): De TA genereert sleutels, sampleert permutaties, bereidt T-gate gadgets voor en distribueert geheime shares.
- Fase 2 (Encryptie): Deelnemers coderen hun sets in quantumtoestanden, passen traps en QOTP toe, en sturen de geëncrypteerde toestanden en sleutels naar de TP.
- Fase 3 (Evaluatie): De TP voert het $C_{\text{AND}}$ circuit homomorf uit, waarbij de sleutels worden bijgewerkt en een transcript wordt bijgehouden.
- Fase 4 (Verificatie & Decryptie): Deelnemers voeren klassieke verificatie uit (MAC, gate, en transcript checks) en threshold decryptie om de QOTP-sleutels te herstellen. De TA voert quantumverificatie uit (trap checks) en decrypt de uiteindelijke toestand om het intersectie-resultaat te broadcasten.

3. Belangrijkste Bijdragen

Multi-Party Extensie: De auteurs breiden vQFHE uit naar een multi-party setting door het te combineren met TFHE, waardoor $n$ partijen set-intersecties kunnen berekenen zonder private data prijs te geven.
Collusie-resistentie: In tegenstelling tot eerdere QPSI-schema's, is dit protocol bestand tegen collusie tussen de TP en tot $t-1$ deelnemers. Het threshold mechanisme zorgt ervoor dat zolang minder dan $t$ partijen gecorrumpeerd zijn, de geheime sleutel en private inputs veilig blijven.
Verifieerbaarheid tegen een Kwaadwillende TP: Het protocol biedt semantische veiligheid en verifieerbaarheid. Het kan detecteren of een kwaadwillende TP afwijkt van het voorgeschreven circuit (bijv. door de gate array of output te wijzigen) via een combinatie van klassieke transcript verificatie en quantum trap code checks.
Modulair Framework: De constructie wordt gepresenteerd als een modulair framework. De auteurs demonstreren hoe men:
- De circuitcomplexiteit kan verminderen (bijv. door CCCZ gates te gebruiken in plaats van $C_nX$ om het aantal T-gates te verlagen).
- De functionaliteit kan uitbreiden naar Quantum Private Set Union (QPSU) door het AND-circuit te vervangen door een OR-circuit via open-controlled operaties.
- De onderliggende vQFHE instanties kan verwisselen voor verschillende efficiëntie/veiligheid trade-offs.

4. Resultaten en Analyse

Correctheid: De auteurs hebben de logische multi-party AND gate gevalideerd met het IBM Quantum Platform en Qiskit. Simulaties bevestigden dat de output distributie overeenkomt met de ideale waarheidstabel voor de logische AND operatie.
Veiligheidsbewijzen:
- Privacy: Het protocol is bewezen informatie-theoretisch veilig tegen de TP met betrekking tot de quantumtoestanden (vanwege de QOTP en maximaal gemengde toestanden) en computationeel veilig met betrekking tot klassieke data (vanwege TFHE en MAC).
- Collusie: Stelling 3 bewijst dat elke coalitie van gecorrumpeerde deelnemers (omvang $<t$ ) die colludeert met de TP, geen informatie verkrijgt buiten het intersectie-resultaat.
- Verifieerbaarheid: Onder het semantische veiligheidsmodel ( $\kappa$ -SEM-VER) is aangetoond dat het protocol verifieerbaar is. Een hybride argument demonstreert dat elke afwijking door de TP met een overweldigende waarschijnlijkheid wordt gedetecteerd.
Prestaties:
- Communicatiecomplexiteit: De quantum communicatiekosten zijn $O(n\kappa L)$ , waarbij $n$ het aantal partijen is, $\kappa$ de veiligheidsparameter en $L$ de set grootte.
- Vergelijking: Vergeleken met bestaande schema's (bijv. [SMZ+15], [ZLS+20], [HZZ24]), is het voorgestelde protocol het enige dat multi-party scenario's ondersteunt met zowel PSI als PSU capaciteiten, terwijl het resistentie biedt tegen TP-participant collusie en kwaadwillend TP-gedrag.

5. Betekenis en Claims

Het artikel claimt een significante vooruitgang te bieden in het veld van quantum veilige computatie door de "TP-participant collusie" kloof aan te pakken die bestaande QPSI-oplossingen teistert.

Robuustheid: Door TFHE te integreren, bereikt het protocol een niveau van collusie-resistentie die eerder afwezig was in quantum PSI, waardoor veiligheid gegarandeerd is zelfs als de TP en een subset van deelnemers samenzweren.
Vertrouwensminimalisatie: De verifieerbaarheidlaag zorgt ervoor dat het systeem veilig kan functioneren zelfs als de TP kwaadwillend is, waardoor de noodzaak om de eerlijkheid van de TP te vertrouwen wordt weggenomen, en enkel zijn computationele capaciteit relevant is.
Flexibiliteit: Het modulaire ontwerp maakt het mogelijk om het framework aan te passen voor verschillende set-operaties (Union, Cardinality) en te optimaliseren voor verschillende hardware-beperkingen (bijv. het reduceren van T-gate complexiteit).

De auteurs erkennen dat hoewel het protocol sterke beveiliging biedt, het de klassieke overhead erft die geassocieerd wordt met TrapTP-gebaseerde vQFHE. Toekomstig werk wordt gesuggereerd om gadget-vrije T-handling te verkennen en verdere optimalisaties uit te voeren om de klassieke communicatiekosten te verlagen.