A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

Dit artikel presenteert een nieuw, praktisch en simulatie-veilig kwantumbewusteloos-overdrachtprotocol dat is gebaseerd op eenrichtingsfuncties in het platte model, de efficiëntie voor experimentele realisatie verbetert en tegelijkertijd foutcorrectie aanpakt door middel van equivocaal en verontschuldigbaar kwantumbit-commitment.

De kern

Stel je voor dat je op een magisch spektakel bent waar twee personen, Alice en Bob, een spel van "Geheime Keuze" willen spelen.

Het Spel: Oblivious Transfer

In dit spel heeft Alice twee geheime berichten (laten we ze Bericht A en Bericht B noemen). Bob wil er één kiezen om te zien.

• De Vangst: Bob mag het andere bericht niet kunnen bespieden.
• De Vangst 2: Alice mag niet weten welke één Bob heeft gekozen.

Dit heet Oblivious Transfer (OT). Het is een fundamenteel bouwsteen voor beveiligde computatie, zoals een digitale "blinddoos" waarbij de verkoper niet weet welke doos je hebt geopend en jij de andere niet kunt openen.

Het Probleem: De Oude Protocollen waren Te Fragiel

Lange tijd wisten wetenschappers hoe ze dit konden doen met quantummechanica (met behulp van tinyeltjes licht genaamd fotonen). De oude methoden hadden echter drie grote gebreken die het onmogelijk maakten om ze in een echt lab te bouwen:

1. Te Gevoelig: Als een foton verloren ging of van toestand veranderde door een klein beetje ruis (zoals een stootje op de tafel), moest het hele spel opnieuw beginnen. Het was als proberen een huis van kaarten te bouwen in een orkaan.
2. Te Zwaar: De oude methoden vereisten een astronomisch aantal fotonen – ongeveer 10 biljoen (10¹³) voor één ronde. Zelfs met de snelste lasers zou dit maanden duren om te verzenden.
3. Te Complex: Ze leunden op complexe wiskundige bewijzen die moeilijk te implementeren waren met standaard, kant-en-klare technologie.

De Oplossing: Een Praktisch, "Ruis-Tolerant" Protocol

De auteurs van dit artikel hebben een nieuwe versie van dit spel gebouwd die praktisch, snel en robuust is. Hier is hoe ze het deden, met behulp van enkele eenvoudige analogieën:

1. Het "Foutcorrigerende Net" (Ruis Hanteren)

In het oude spel, als je één kaart liet vallen, was het hele deck verpest. In dit nieuwe spel gebruiken Alice en Bob een veiligheidsnet.

• De Metafoor: Stel je voor dat Alice een bericht op een stuk papier schrijft, maar ze stuurt ook een "checksum" (een geheim code dat je vertelt of het papier gescheurd is).
• Hoe het werkt: Zelfs als sommige fotonen verloren gaan van toestand veranderen (ruis), gebruikt het protocol foutcorrigerende codes (zoals een net dat de gevallen kaarten opvangt) om de fouten te herstellen. Dit betekent dat het spel niet crasht alleen omdat het lab niet perfect is.

2. De "Eenmalige Pas" (Efficiëntie)

De oude protocollen waren als een spel waarbij je een biljoen keer een munt moest opgooien om één keer "Kop" te krijgen.

• De Metafoor: Het nieuwe protocol is als een hogesnelheidstrein in plaats van een langzaam, kronkelend pad.
• Het Resultaat: In plaats van 10 biljoen fotonen te nodig hebben, hebben ze slechts ongeveer 10 tot 30 miljoen nodig. Dit verlaagt de benodigde tijd van maanden naar slechts seconden. Het is het verschil tussen wachten op een brief die per schip arriveert versus het verzenden van een e-mail.

3. De "Magische Lockbox" (De Technische Truc)

Om het spel veilig te maken, gebruiken ze een speciaal type Quantum Lockbox (een "Bit Commitment" genoemd).

• De Oude Manier: De lockbox was zo streng dat als je probeerde te valsspelen, het hele systeem kapot ging.
• De Nieuwe Manier: De auteurs hebben een "Gedempte" Lockbox uitgevonden.
  • Stel je een lockbox voor die normaal gesproken één onveranderlijk geheim vasthoudt.
  • De nieuwe versie zegt: "We hoeven niet elke enkele lockbox perfect te hebben. We hoeven alleen maar dat de meeste van hen strak vergrendeld zijn."
  • Deze "gedempte" regel stelt hen in staat de zware, herhalende stappen van de oude protocollen over te slaan, wat enorme hoeveelheden tijd en middelen bespaart terwijl het spel toch veilig blijft.

Het Grote Plaatje

De auteurs hebben niet alleen bewezen dat dit op papier werkt; ze hebben een blauwdruk geleverd om het te bouwen.

• Ze hebben aangetoond dat met de huidige technologie (hetzelfde soort dat wordt gebruikt in Quantum Key Distribution, wat al in steden wordt getest), dit spel vandaag gespeeld kan worden.
• Ze hebben precies berekend hoeveel fotonen nodig zijn en hoe lang het duurt, bewijzend dat een veilig, multi-partij quantumnetwerk geen ver weg droom meer is, maar een haalbaar engineeringproject.

Kortom: Ze hebben een fragiel, traag en theoretisch quantumspel omgezet in een stevig, snel en praktisch hulpmiddel dat daadwerkelijk in een lab gebouwd kan worden.

Technische samenvatting

Technische Samenvatting: Een Praktisch Protocol voor Quantum Oblivious Transfer vanuit Eénrichtingsfuncties

1. Probleemstelling

Quantum Oblivious Transfer (QOT) is een fundamenteel primitief voor het construeren van Multi-Party Computation (MPC) in de quantumcontext. Hoewel eerdere werken [6, 7] aantoonden dat QOT kon worden gebouwd vanuit Eénrichtingsfuncties (OWF's) en quantumbronnen, stonden deze protocollen voor aanzienlijke barrières voor experimentele realisatie. De belangrijkste geïdentificeerde problemen waren:

• Fragiliteit: Bestaande protocollen waren niet tolerant voor experimentele fouten (bijvoorbeeld bit-flips tijdens de distributie van toestanden).
• Implementatiecomplexiteit: De afhankelijkheid van Zero-Knowledge Proofs die geen black-box gebruik maakten van OWF's, maakte integratie met praktische post-quantum hash-functies (zoals SHA) niet triviaal.
• Inefficiëntie: De iteratieve structuur van eerdere protocollen vereiste een onpraktisch groot aantal quantumtoestanden (bijvoorbeeld $\sim 10^{13}$ BB84-toestanden per uitvoering), wat resulteerde in transmissietijden in de orde van maanden.

De auteurs beogen een ruis-tolerant, efficiënt QOT-protocol te bieden dat gebaseerd is op OWF's in het plain model en haalbaar is voor huidige experimentele opstellingen.

2. Methodologie en Technische Aanpak

De voorgestelde oplossing construeert een simulatie-veilig QOT-protocol door een nieuw cryptografisch primitief in te voeren: een Equivocaal en Gereduceerd-Extracteerbaar (ERE) Bit Commitment-schema.

Kerninnovaties:

• Gereduceerde Extracteerbaarheid: De auteurs stellen vast dat volledige extracteerbaarheid niet strikt noodzakelijk is om de veiligheid van QOT te bewijzen. Zij introduceren "gereduceerde extracteerbaarheid", waarbij een simulator het gecommitteerde bericht kan extraheren voor een groot deel van de commitments, terwijl een verwaarloosbaar deel onextracteerbaar kan blijven. Deze versoepeling maakt een efficiënter protocol mogelijk.
• Ruis-tolerantie via Foutcorrectie: In tegenstelling tot eerdere werken die uitgaan van ruisvrije apparaten, incorporateert dit protocol lineaire foutcorrigerende codes (specifiek syndroomgebaseerde codes zoals LDPC). De zender zendt syndromen van gecodeerde waarden uit, waardoor de ontvanger (of een simulator) fouten kan corrigeren en correcte zaden kan extraheren, zelfs in aanwezigheid van ruis.
• Efficiënte Zaaddistillatie: Het protocol maakt gebruik van privacy-amplificatietechnieken (Leftover Hash Lemma) op BB84-toestanden om willekeurige zaden te distilleren. Deze zaden dienen als sleutels voor equivocaal commitments. De structuur groepeert deze zaden in families om parallelle commitments mogelijk te maken, waardoor de kwadratische overhead die in eerdere compilers voorkwam, wordt vermeden.
• Commitment-structuur: Het ERE-Commitment-schema combineert:
  1. EqCommitment: Een compiler die een standaard statistisch bindend commitment transformeert in een equivocaal commitment. De auteurs modificeren de originele compiler [7] door het aantal sequentiële herhalingen te reduceren van $\lambda$ naar één enkele instantie, waarbij volledige binding wordt ingeruild voor "gereduceerde binding".
  2. ERE-Commitment: Een hoger niveau protocol dat het EqCommitment-schema gebruikt. Het omvat het zenden van BB84-toestanden door de zender, het commiten van de ontvanger aan meetuitkomsten, en een challenge-fase waarin een subset wordt geopend voor verificatie. De resterende toestanden worden gebruikt om zaden te genereren voor de uiteindelijke berichtencryptie.

Protocolverloop (Protocol 1):

1. Quantumtransmissie: Alice zendt $2\lambda_{OT}$ BB84-toestanden naar Bob.
2. Commitment: Bob meet en committ aan zijn basiskeuzes en uitkomsten met behulp van het ERE-Commitment-schema.
3. Challenge: Alice daagt een willekeurige subset $T$ van de commitments uit. Bob opent deze om consistentie te verifiëren met de door Alice verzonden toestanden (rekening houdend met experimentele fout $\alpha$).
4. Sleutelgeneratie: Alice zendt de basisinformatie voor de niet-uitgedaagde set $\bar{T}$. Bob partitioneert $\bar{T}$ in sets $I_0$ en $I_1$ op basis van overeenkomstige basissen.
5. Encryptie: Alice zendt foutcorrectiesyndromen en versleutelt haar berichten $m_0, m_1$ met behulp van zaden die zijn afgeleid van de niet-uitgedaagde toestanden en een Pseudorandom Generator (PRG).
6. Decryptie: Bob corrigeert zijn fouten met behulp van de syndromen en ontcijfert het bericht dat overeenkomt met zijn keuzebit $b$.

3. Belangrijkste Bijdragen

• Nieuw Primitief: De definitie en constructie van een Equivocaal en Gereduceerd-Extracteerbaar (ERE) Bit Commitment-schema gebaseerd op OWF's.
• Ruis-tolerant QOT: Een QOT-protocol dat experimentele fouten (bit-flips en multi-foton-evenementen) expliciet afhandelt via syndroomgebaseerde foutcorrectie, een kenmerk dat ontbreekt in eerdere theoretische constructies.
• Efficiëntieverbetering: Door het optimaliseren van de commitment-structuur en het gebruik van foutcorrectie, reduceert het protocol het vereiste aantal BB84-toestanden van $\sim 10^{13}$ (in [7]) naar $\sim 10^7$.
• Multi-OT Distillatie: Het protocol maakt het distilleren van meerdere OT-sleutels ($n_{OT}$) mogelijk vanuit één enkele uitvoering van het protocol, wat cruciaal is voor een efficiënte MPC-implementatie.
• Analytisch Kader: Het artikel biedt analytische uitdrukkingen om de vereiste quantumbronnen te benchmarken tegenover doelwit-veiligheidsparameters (trace-afstand $\Delta$), rekening houdend met fysieke foutpercentages ($\alpha$) en lekage ($\vartheta$).

4. Resultaten en Prestaties

De auteurs bieden een prestatiebenchmark (Tabel 1) die hun protocol vergelijkt met [7] en [21] voor een doelwit trace-afstand $\Delta \le 10^{-15}$:

• Bronreductie: Het vereiste aantal BB84-toestanden ($N_{BB84}$) wordt gereduceerd tot ongeveer $1,43 \times 10^6$ (ideaal) tot $3,33 \times 10^7$ (realistische ruisomgeving), vergeleken met $2,27 \times 10^{13}$ voor het protocol in [7].
• Tijds-efficiëntie: Deze reductie vertaalt zich naar een acquisitietijd ($T_{acq}$) van seconden (bijvoorbeeld 1,43s tot 43,6s aannemende een snelheid van 1 MHz), terwijl het eerdere werk [7] ongeveer 8,6 maanden zou vereisen.
• Veiligheid: Het protocol is bewezen simulatie-veilig tegen kwaadaardige partijen in het plain model, waarbij uitsluitend wordt vertrouwd op het bestaan van post-quantum éénrichtingsfuncties.

5. Betekenis en Claims

Het artikel claimt dat dit werk de kloof overbrugt tussen theoretische quantumcryptografie en praktische implementatie. Door de vereiste voor ruisvrije apparaten te verwijderen en de quantumbronnen-overhead drastisch te reduceren, stellen de auteurs dat hun protocol de experimentele realisatie van QOT (en bij uitbreiding, quantum MPC) haalbaar maakt met huidige technologie.

De auteurs benadrukken dat hun constructie vergelijkbare BB84-kosten bereikt als protocollen gebaseerd op het Random Oracle Model (ROM) [21], maar werkt onder strikt zwakkere computationele aannames (plain model met OWF's in plaats van ROM). Zij stellen expliciet dat hun doel een "praktische implementatie" is, en zij claimen niet de klassieke efficiëntie van ROM-gebaseerde commitments te evenaren, maar eerder een levensvatbaar pad te bieden voor quantum-veilige OT in de echte wereld. Het werk benadrukt ook dat de eigenschap van gereduceerde extracteerbaarheid voldoende is voor veiligheid, een technische inzicht dat de efficiëntiewinsten mogelijk maakt zonder de op simulatie gebaseerde veiligheidsgaranties die voor MPC vereist zijn, te compromitteren.