A Note on Boosting Uncloneable Encryption in Microcrypt

Dit artikel toont aan dat veelvoudig beveiligde onklooneerbare encryptie voor berichten van willekeurige lengte kan worden geconstrueerd uit minimale aannames in de "microcrypt"-omgeving, specifiek door een informatie-theoretisch onklooneerbaar bit te combineren met óf veelvoudig beveiligde symmetrische sleutelencryptie óf pseudorandom unitaire transformaties.

De kern

Stel je voor dat je probeert een geheim bericht te sturen naar een vriend met behulp van een speciale quantum-locker. In de wereld van de quantumfysica geldt een vreemde regel: je kunt een quantumtoestand (zoals een specifieke rangschikking van atomen) niet perfect kopiëren zonder het origineel te vernietigen. Dit heet het No-Cloning Theorem.

Dit artikel gaat over een nieuw type "quantum-locker" genaamd Uncloneable Encryption (nabootsingsveilige encryptie). Het doel is een systeem te maken waarbij, zelfs als een hacker de vergrendelde locker steelt, hij geen perfecte kopie kan maken om deze later te openen. Als ze proberen het te kopiëren, breekt de kopie en verliezen ze het bericht.

De auteurs stellen een zeer specifieke vraag: Hoe weinig hoeven we aan te nemen over de toekomst van wiskunde en natuurkunde om deze superveilige dozen te laten werken voor vele berichten, niet slechts één?

Hier is de uiteenzetting van hun bevindingen met eenvoudige analogieën:

1. Het Startpunt: De "Uncloneable Bit"

Stel je hebt een magische munt. Als je hem opgooit, krijg je een resultaat (Kop of Munt). Het artikel gaat ervan uit dat we al een manier hebben om deze enkele munt in een doos te vergrendelen zodat niemand de doos kan kopiëren. Als ze proberen het te kopiëren, is de kopie nutteloos.

• Het Probleem: Deze magie werkt alleen voor één munt (één bericht). We willen vele berichten (zoals een hele roman) sturen met dezelfde geheime sleutel, zonder dat de beveiliging bezwijkt.
• Het Doel: De auteurs willen een "veelvoudig" veilig systeem bouwen dat uitsluitend gebruikmaakt van deze ene magische munt en enkele andere standaardtools.

2. De Eerste Grote Ontdekking: De "Universele Adapter"

De auteurs vonden een manier om die enkele magische munt om te zetten in een systeem dat lange berichten (zoals een heel boek) vele malen kan versleutelen.

• De Analogie: Denk aan de magische munt als een klein, fragiel zaadje. De auteurs bouwden een "kas" (een compiler) die dat zaadje neemt en er een enorme, herbruikbare boom van doet groeien.
• De Haken: In hun eerste versie van deze boom heeft de persoon die de doos vergrendelt een iets andere sleutel nodig dan de persoon die hem ontgrendelt. Het is alsof je een mastersleutel hebt om de deur te vergrendelen, maar een andere, eenvoudigere sleutel om hem te openen. Dit is wat ongemakkelijk.
• Het Resultaat: Ze bewezen dat als je de magische munt en een standaard, herbruikbare slot hebt (waarvan we aannemen dat deze bestaat), je een systeem kunt bouwen dat even veilig is als de beste standaardsloten die we vandaag hebben. Je kunt niet beter dan dat, dus dit resultaat is "strak" (perfect efficiënt).

3. De Tweede Grote Ontdekking: Het "Normaal" en "Identiek" Maken

De auteurs beseften dat ze het systeem nog beter konden maken, maar ze hadden één extra ingrediënt nodig: Pseudorandom Unitaries.

• Wat is dat? Stel je een machine voor die getallen genereert die voor een mens volledig willekeurig lijken, maar die eigenlijk gegenereerd worden door een specifieke, geheime formule. In de quantumwereld is dit een machine die data op een manier verward dat het eruit ziet als pure chaos, maar die eigenlijk gecontroleerd is.
• De Upgrade: Met deze extra machine losten ze het probleem van de "verschillende sleutels" op. Nu gebruiken de persoon die de doos vergrendelt en de persoon die hem ontgrendelt precies dezelfde sleutel. Dit heet "Normal Form".
• De "Identieke Kopie" Bonus: Normaal gesproken kan de quantumdoos er elke keer dat je een bericht verstuurt, iets anders uitzien (zoals een wazige foto versus een scherpe foto). De auteurs toonden aan dat met hun nieuwe methode, elke keer dat je hetzelfde bericht verstuurt, de doos er identiek uitziet als de vorige.
  • Waarom is dit belangrijk? In het "Uncloneable"-spel krijgt een hacker $t$ kopieën van een doos en probeert hij $t'$ kopieën te maken.
  • Standaardversie: De hacker krijgt $t$ licht verschillende wazige foto's.
  • Identieke versie: De hacker krijgt $t$ perfecte, identieke foto's.
  • De auteurs bewezen dat als je de wazige foto's niet kunt kopiëren, je de perfecte identieke foto's zeker niet kunt kopiëren. Dit maakt de beveiliging veel sterker en realistischer.

4. De "Microcrypt"-Wereld

Het artikel noemt een concept genaamd "Microcrypt".

• De Analogie: Stel je een wereld voor waar computers ongelooflijk krachtig zijn (zo krachtig dat ze elk wiskundig raadsel direct kunnen oplossen, wat betekent dat $P=NP$). In onze huidige wereld vertrouwen we erop dat wiskundige raadsels moeilijk op te lossen zijn om geheimen veilig te houden. Als $P=NP$, zouden de meeste van onze huidige sloten breken.
• De Claim: De auteurs tonen aan dat hun nieuwe Uncloneable Encryption-systeem misschien nog steeds werkt, zelfs in deze "gebroken" wereld waar wiskundige raadsels makkelijk zijn. Het vertrouwt op de vreemde wetten van de quantumfysica (de uncloneable bit) en de "willekeurig ogende" machines (pseudorandom unitaries) in plaats van op moeilijke wiskundige raadsels.
• De Conclusie: Zelfs als de wereld van de wiskunde instort, kan deze quantumbeveiliging misschien toch overeind blijven.

Samenvatting van het "Recept"

Het artikel biedt een recept om de ultieme quantum-locker te bouwen:

1. Ingrediënt A: Een "Uncloneable Bit" (een eenmalig veilig quantumslot voor één bit data).
2. Ingrediënt B: Een standaard, herbruikbaar slot (voor normale encryptie).
   • Resultaat: Je krijgt een herbruikbare locker voor lange berichten, maar de vergrendel- en ontgrendelsleutels zijn verschillend.
3. Voeg Ingrediënt C toe: Pseudorandom Unitaries (een machine die "nep-willekeurige" quantumchaos creëert).
   • Resultaat: Je krijgt een herbruikbare locker waarbij de vergrendel- en ontgrendelsleutels hetzelfde zijn, en elke keer dat je een bericht verstuurt, de doos er identiek uitziet als de vorige, waardoor het ongelooflijk moeilijk te hacken is.

Kortom: De auteurs bewezen dat we niet hoeven aan te nemen dat het onmogelijke waar is om deze superveilige quantumsystemen te bouwen. We hebben slechts een klein beetje quantummagie nodig (de uncloneable bit) en enkele standaardtools, en we kunnen een systeem bouwen dat veilig is, zelfs als de rest van de wereld van de wiskundige beveiliging faalt.

Technische samenvatting

Technische Samenvatting: Een Opmerking over het Versterken van Onklooneerbare Encryptie in Microcrypt

Probleemstelling

Onklooneerbare Encryptie (UE) is een kwantumcryptografisch primitief dat de onklooneerbaarheid van kwantuminformatie combineert met de semantische beveiliging van encryptie. Hoewel een eenmalig beveiligde UE (een "onklooneerbaar bit") informatie-theoretisch gezien geacht wordt te bestaan, vereist het bereiken van herbruikbare (meerdere keren) beveiliging cryptografische aannames.

Vorig werk stelde vast dat herbruikbare UE bestaat in "microcrypt"—een wereld van ongestructureerde kwantumcryptografie die veilig blijft zelfs als $P=NP$—maar deze resultaten leunden op geïdealiseerde modellen (specifiek de Haar-random oracle) in plaats van concrete aannames. Bovendien ontbraken bestaande constructies vaak de "normale vorm" (waarbij encryptie- en decryptiesleutels identiek zijn) of "veiligheid bij identieke kopieën" (waarbij de adversary meerdere kopieën van dezelfde pure toestand ontvangt in plaats van onafhankelijke gemengde toestanden).

Deze notie heeft tot doel de concrete aannames die nodig zijn voor herbruikbare UE te minimaliseren. Specifiek onderzoekt het of het bestaan van een informatie-theoretisch $t \to t'$ onklooneerbaar bit (een eenmalig beveiligd schema voor één-bit berichten waarbij een adversary $t$ kopieën niet kan klonen om $t'$ geldige decrypties te produceren) voldoende is om herbruikbare UE voor berichten van willekeurige lengte te construeren, en onder welke aanvullende aannames sterkere beveiligingsnoties bereikt kunnen worden.

Methodologie

De auteurs maken gebruik van twee primaire compiler-technieken om zwakke primitieven om te vormen tot sterkere herbruikbare UE-schema's:

1. Tekstuitbreiding via Decomposeerbare Kwantum Geraandomiseerde Encodering (DQRE)

Het artikel past een compiler aan die oorspronkelijk werd geïntroduceerd door [HKNY24] voor eenmalige UE.

• Mechanisme: De constructie gebruikt een DQRE om een circuit $C[m]$ te coderen dat het bericht $m$ output. De encryptiesleutel bestaat uit een eenmalige onklooneerbare sleutel ($udk$) en een set herbruikbare symmetrische sleutels.
• Kerninnovatie: In tegenstelling tot eerdere iteraties die leunden op eenmalige pads (wat herbruikbaarheid verhinderde), vervangt deze constructie eenmalige pads door een herbruikbaar IND-CPA symmetrisch sleutelencryptieschema (SKE).
• Beveiligingsargument: De beveiliging berust op de onderscheidbaarheid van de DQRE. De uitdaging-cifertexten worden zo geconstrueerd dat het onderscheiden tussen encrypties van $m_0$ en $m_1$ reduceert tot het onderscheiden van de onderliggende DQRE-labels, wat op zijn beurt reduceert tot de beveiliging van het onklooneerbaar-bit-spel.
• Normale Vorm: Om de "normale vorm" te bereiken (identieke encryptie-/decryptiesleutels), merken de auteurs op dat als de onderliggende herbruikbare SKE pseudorandom is (cifertexten zijn ononderscheidbaar van de maximaal gemengde toestand), het encryptieprotocol willekeurige strings kan bemonsteren in plaats van specifieke waarden te versleutelen voor "ongebruikte" sleutelbits. Dit elimineert de noodzaak om decryptiesleutels voor ongebruikte bits aan de adversary te onthullen.

2. Veiligheid bij Identieke Kopieën via Zuiveringskanalen

Het artikel adresseert de kloof tussen standaard UE-beveiliging (de adversary ontvangt onafhankelijke gemengde toestanden) en veiligheid bij identieke kopieën (de adversary ontvangt meerdere kopieën van dezelfde pure toestand).

• Mechanisme: Op basis van recente resultaten in kwantumleertheorie ([TWZ26, PSTW25, GML26]) en vorig werk over kopiebescherming ([AG25, C¸GK+25]), maken de auteurs gebruik van een zuiveringskanaal.
• Aanname-reductie: Vorige werken vereisten Eén-Weg Functies (OWF's) om een simulator te construeren die $t$ kopieën van een gemengde toestand vervangt door $t$ kopieën van een zuiveringsensemble. De auteurs tonen aan dat Pseudorandom Unitaries (PRU's) voldoende zijn om deze simulator te instantiëren.
• Constructie: Het encryptie-algoritme neemt een PRU-sleutel $k$ als willekeur. Het zuivert de cifertext en past de unitaire transformatie $U_k$ toe op het zuiveringsregister. De resulterende toestand is ononderscheidbaar van de output van het ideale zuiveringskanaal toegepast op de oorspronkelijke cifertext.

Belangrijkste Bijdragen en Resultaten

1. Equivalentie van Herbruikbare UE en Herbruikbare SKE

Het artikel stelt vast dat het bestaan van een $t \to t'$ onklooneerbaar bit, gecombineerd met herbruikbare SKE, voldoende is om herbruikbare $t \to t'$ UE voor berichten van willekeurige lengte te construeren.

• Stelling 1.1 (Informeel): Als een $t \to t'$ onklooneerbaar bit en herbruikbare SKE bestaan, dan bestaat er herbruikbare $t \to t'$ UE.
• Strakheid: Aangezien herbruikbare UE herbruikbare SKE impliceert, is dit resultaat strak; herbruikbare UE is equivalent aan herbruikbare SKE gegeven een onklooneerbaar bit.

2. Normale Vorm en Veiligheid bij Identieke Kopieën

De auteurs tonen aan dat sterkere beveiligingsnoties bereikbaar zijn onder iets sterkere, maar standaard, microcrypt-aannames.

• Stelling 1.2 (Informeel): Als een $t \to t'$ onklooneerbaar bit en Pseudorandom Unitaries (PRU's) bestaan, dan bestaat er een herbruikbaar $t \to t'$ UE-schema dat zowel normale vorm bezit als veiligheid bij identieke kopieën.
• Corollarium 1.8: Dit resultaat is afgeleid door de tekstuitbreidingscompiler (met PRU-gebaseerde SKE voor normale vorm) te combineren met de zuiveringskanaal-transformatie (met PRU's voor veiligheid bij identieke kopieën).

3. Generalisatie van Beveiligingsspellen

Het werk generaliseert het standaard $1 \to 2$ kloonspel naar willekeurige $t \to t'$ parameters, en biedt een unifyend kader voor het analyseren van onklooneerbaarheid waarbij een adversary probeert $t$ uitdaging-cifertexten te klonen tot $t'$ geldige decrypties.

Betekenis en Claims

Het artikel claimt een duidelijker, meer systematisch beeld te geven van de aannames die ten grondslag liggen aan herbruikbare onklooneerbare encryptie. De primaire betekenis ligt in:

1. Minimaliseren van Aannames: Het toont aan dat herbruikbare UE geen complexe, gestructureerde primitieven vereist (zoals publieke-sleutelencryptie of specifieke algebraïsche structuren), maar gebouwd kan worden vanuit de zeer zwakke aanname van een onklooneerbaar bit en standaard microcrypt-primitieven (SKE en PRU's).
2. Concrete Realisatie in Microcrypt: Het verplaatst het bestaan van herbruikbare UE van het domein van geïdealiseerde modellen (Haar-random oracles) naar concrete aannames die plausibel gelden zelfs als $P=NP$.
3. Unificatie: Het verenigt de constructie van UE met normale vorm en veiligheid bij identieke kopieën onder de enkele aanname van PRU's, en toont aan dat deze wenselijke eigenschappen niet wederzijds uitsluitend zijn, maar eerder natuurlijk voortvloeien uit standaard kwantumcryptografische bouwstenen.

De auteurs stellen expliciet dat hun resultaten aantonen dat meermalig beveiligde onklooneerbare encryptie "mogelijk voortvloeit uit concrete aannames in 'microcrypt'". Zij claimen niet deze primitieven uit eerste principes te construeren (bijvoorbeeld vanuit roosterproblemen), maar eerder het probleem te reduceren tot het bestaan van deze specifieke, goed bestudeerde kwantumprimitieven.