Towards Simple and Useful One-Time Programs in the Quantum Random Oracle Model

1. Het Probleem

Eenmalige programma's (One-Time Programs, OTPs) en eenmalige geheugens (One-Time Memories, OTMs) zijn cryptografische primitieven die toestaan dat een programma slechts één keer wordt uitgevoerd. In zowel klassieke als kwantumsettings is het bewezen dat deze niet veilig kunnen worden geconstrueerd op basis van standaard cryptografische aannames alleen.

Bestaande oplossingen vereisen vaak onpraktische aannames, zoals:

• Hardware-tokens: Moeilijk te implementeren en vatbaar voor kwetsbaarheden.
• Beperkte opslag: Aannames over "geïsoleerde qubits" of beperkte kwantumopslagcapaciteit.
• Strikte tijdsbeperkingen: Aannames dat een tegenstander binnen een zeer kort tijdsbestek moet meten.

De kernuitdaging is het ontwikkelen van een OTP-constructie die:

1. Praktisch toepasbaar is met nabije-toekomstige kwantumhardware (geen complexe verstrengeling nodig).
2. Veilig is tegen realistische kwantumaanvallers die beperkte, maar adaptieve, kwantumverwerkingskracht hebben (die klassieke berekeningen kunnen afwisselen met kwantumcirkels).
3. Toelaat dat de ontvanger het kwantumprogramma bewaart voor later gebruik, zonder dat de beveiliging afneemt door de beperkte coherentie van niet-fouttolerante toestanden.

2. Methodologie

De auteur presenteert een constructie die rust op drie pijlers:

A. Kwantumtoestanden: Wiesner-toestanden

In plaats van complexe verstrengelde toestanden (zoals hidden subspace states) gebruikt het schema onafhankelijke single-qubit Wiesner-toestanden (conjugate coding).

• De zender bereidt $n$ onafhankelijke blokken voor, elk bestaande uit $m$ qubits.
• Elke qubit wordt willekeurig gecodeerd in de rekenbasis ($Z$) of de Hadamard-basis ($X$).
• Dit vereist geen multi-qubit verstrengeling, wat de implementatie aanzienlijk vereenvoudigt.

B. Cryptografische Primitieven: Conjunctie-Obfuscatie

Het schema gebruikt conjunctie-obfuscatie (conjunction obfuscation), die kan worden geïmplementeerd onder de aanname van Learning Parity with Noise (LPN).

• LPN wordt beschouwd als post-kwantum veilig.
• De obfuscatie verbergt welke posities tot welke basis behoren en genereert een sleutel alleen als de gemeten uitkomsten overeenkomen met de verwachte waarden.

C. Veiligheidsmodel: Bounded Adaptive Depth

De auteurs definiëren de tegenstander binnen de complexiteitsklasse $\mathsf{BPPQNCBPP}^d$.

• Dit model staat toe dat een tegenstander polynomiale klassieke berekeningen afwisselt met kwantumcirkels van beperkte diepte $d$.
• De tegenstander kan kwantumgeheugen behouden tussen klassieke berekeningen, maar de totale coherentie diepte is beperkt. Dit is fysiek realistisch voor niet-fouttolerante toestanden waar ruis zich ophoopt met de diepte van de schakeling.

3. Belangrijkste Bijdragen en Techniek

1. Een Nieuwe POVM-Bound (Hoofdstuk 3)

De kern van de technische bijdrage is een nieuwe informatie-theoretische grens voor sequentiële conjugate coding.

• Stelling: Als een tegenstander een POVM-meting uitvoert die met kans $(1-\epsilon)$ de juiste toestand identificeert in de rekenbasis, dan is de kans om de toestand in de geconjugeerde basis (Hadamard) te raden beperkt tot $\frac{1}{2^m} + O(\epsilon^{1/4})$.
• Sequentialiteit: Deze bound geldt zelfs als de tegenstander de keuze van de basis pas na de meting te weten komt.
• Dit generaliseert eerdere resultaten voor single-qubit naar multi-qubit toestanden en maakt het raden van de conjugate-basis exponentieel moeilijk voor grote $m$.

2. Constructie van de One-Time Memory (Hoofdstuk 4)

Het OTP-schema werkt als volgt:

1. Voorbereiding: De zender bereidt een tensorproduct van Wiesner-toestanden voor. Een willekeurige subset $\Theta_X$ gebruikt de $X$-basis en de complementaire subset $\Theta_Z$ gebruikt de $Z$-basis.
2. Verborgen Basis: Twee conjunctie-obfuscaties ($\mathcal{O}_X$ en $\mathcal{O}_Z$) worden gegenereerd. Deze controleren of de gehashte meetuitkomsten overeenkomen met de verwachte waarden voor hun respectievelijke subsets.
3. Versleuteling: De berichten $m_X$ en $m_Z$ worden versleuteld met sleutels $k_X$ en $k_Z$ die alleen vrijgegeven worden als de juiste obfuscatie succesvol wordt geëvalueerd.
4. Random Oracle: Een willekeurige orakel ($\mathcal{H}$) dwingt de tegenstander om klassieke queries te doen, waardoor ze zich moeten committeren aan specifieke meetuitkomsten.

3. Veiligheidsbewijs voor Klassieke Queries

Het bewijs toont aan dat een tegenstander die alleen klassieke queries doet aan het random orakel, niet beide berichten kan herstellen.

• Als de tegenstander in de $Z$-basis meet, zorgt de POVM-bound ervoor dat de informatie over de $X$-basis (en dus de hash-waarden voor $\Theta_X$) verdampt (min-entropy is hoog).
• Zonder de juiste hash-waarden kan de tegenstander de conjunctie-obfuscatie $\mathcal{O}_X$ niet evalueren en de sleutel $k_X$ niet achterhalen.
• Hierdoor is het onmogelijk om beide conjuncties succesvol te evalueren, wat de "one-time" eigenschap garandeert.

4. Lifting naar Kwantum Diepte (Hoofdstuk 5)

De auteurs gebruiken een informele toepassing van het lifting framework van Arora et al. [1] om de veiligheid uit te breiden naar kwantumaanvallers met beperkte diepte.

• Het argument is dat diepte-beperkte tegenstanders geen coherente superposities kunnen behouden over vele orakelqueries zonder tussenliggende metingen die de toestand laten instorten.
• Hierdoor "kollaberen" hun queries effectief tot klassieke transities, waardoor het bewijs voor klassieke queries ook geldt voor deze kwantumaanvallers.

4. Resultaten

• Constructie: Een eenvoudig OTP-schema dat alleen single-qubit operaties en klassiek installeerbare obfuscatie vereist.
• Veiligheid: Het schema is bewezen veilig tegen tegenstanders met beperkte kwantumdiepte in het Random Oracle Model (ROM).
• Efficiëntie: Geen complexe kwantumcirkels of verstrengeling nodig, wat de weg vrijmaakt voor implementatie met huidige of nabije-toekomstige hardware.
• Praktische Toepasbaarheid: Het schema staat toe dat een ontvanger het programma in kwantumgeheugen bewaart voor later gebruik, zolang de aanvalskracht van de tegenstander beperkt blijft door fysieke ruis en dieptelimieten.

5. Betekenis en Toekomstperspectief

Dit werk is significant omdat het een brug slaat tussen theoretische kwantumcryptografie en praktische implementatie:

1. Vereenvoudiging: Het elimineert de noodzaak voor zware cryptografische aannames (zoals Indistinguishability Obfuscation) of complexe kwantumtoestanden.
2. Realistische Aannames: Door te focussen op "bounded depth" in plaats van strikte tijdsbeperkingen of geheugenbeperkingen, creëert het een model dat beter past bij de fysieke realiteit van kwantumcomputers (waar ruis een natuurlijke beperking is).
3. Toekomstige Richtingen: De auteurs identificeren openstaande vragen, zoals het verbeteren van de POVM-bound (van $O(\epsilon^{1/4})$ naar $O(\epsilon^{1/2})$), het analyseren van ruis-tolerantie, en het formeel bewijzen van het "lifting"-argument voor hun specifieke setting.

Kortom, Stambler biedt een plausibel pad naar praktische, veilig bewezen eenmalige programma's die kunnen worden uitgevoerd op kwantumhardware die nog niet volledig fouttolerant is.