⚛️ quantum physics

On the Impossibility of Simulation Security for Quantum Functional Encryption

Dit artikel stelt de onmogelijkheid vast van het bereiken van simulatie-veilige quantum functionele encryptie door aan te tonen dat klassieke onmogelijkheidsresultaten zich uitstrekken tot het quantumregime, waarbij onvoorwaardelijke barrières worden bewezen voor onbegrensde uitdagingsberichten en onmogelijkheid onder zwakkere aannames zoals pseudorandom quantumtoestanden of publieke-sleutelencryptie voor begrensde sleutelscenario's.

Oorspronkelijke auteurs: Mohammed Barhoush, Arthur Mehta, Anne Müller, Louis Salvail

Gepubliceerd 2026-01-27

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mohammed Barhoush, Arthur Mehta, Anne Müller, Louis Salvail

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: Wat is Functionele Encryptie?

Stel je voor dat je een kluis hebt (encryptie) met daarin een enorme bibliotheek aan boeken.

Traditionele Encryptie: Je hebt óf de hoofdsleutel om de hele kluis te openen en elk boek te lezen, óf je hebt geen sleutel en kunt niets lezen. Het is een "alles-of-niets"-deal.
Functionele Encryptie (FE): Dit is een slimmer systeem. Je geeft een specif으로 persoon een speciale "magische lens" (een functionele sleutel). Als die persoon door deze lens naar de afgesloten kluis kijkt, kan hij alleen het resultaat van een specifieke wiskundige berekening op de boeken zien (bijv. "Wat is het gemiddelde aantal woorden?"). Hij kan de werkelijke woorden, de titels of andere gegevens niet zien. Hij krijgt alleen het antwoord op de specifieke vraag die hij stelde.

Het Doel: "Simulatie-beveiliging"

In de cryptografie willen we bewijzen dat dit systeem perfect veilig is. De gouden standaard hiervoor wordt Simulatie-beveiliging genoemd.

Denk hierbij aan een goocheltruc.

De Werkelijke Wereld: Een goochelaar (de encryptor) vergrendelt de boeken, en een helper (de sleutelhouder) gebruikt de lens om het antwoord te krijgen.
De Simulatie Wereld: Een tweede goochelaar (de simulator) probeert een neppersie van de truc te maken zonder ooit de boeken te hebben gezien. Hij kent alleen de gestelde vraag en het gegeven antwoord.

Als het publiek (de aanvaller) het verschil niet kan zien tussen de Werkelijke Wereld en de Simulatie Wereld, dan is het systeem veilig. Het bewijst dat de lens niets over de boeken heeft onthuld, behalve het specifieke antwoord.

Het Probleem: De "Onmogelijke" Barrière

In de klassieke wereld (met normale computers en bits) hebben onderzoekers al bewezen dat je geen Functionele Encryptie-systeem kunt bouwen dat in alle situaties perfect "Simulatie-veilig" is. Als je de aanvaller te veel vragen laat stellen of te veel vergrendelde kluizen laat zien, valt de goocheltruc uit elkaar.

De Grote Vraag: Blijft deze "onmogelijkheid" ook gelden in de Quantumwereld?

Quantumcomputers gebruiken "qubits", die veel meer informatie kunnen bevatten en vreemd gedrag vertonen (zoals op twee plaatsen tegelijk zijn). Misschien biedt quantummechanica een achterdeurtje waardoor we een perfect, Simulatie-veilig systeem kunnen bouwen waar klassieke computers faalden?

Het Antwoord van het Papier: Nee, de Barrière Bestaat Nog Steeds

De auteurs van dit artikel zeggen: Nee. De klassieke onmogelijkheidsresultaten strekken zich grotendeels uit tot de quantumwereld. Zelfs met de superkrachten van de quantummechanica kun je geen perfect Simulatie-veilig Functioneel Encryptie-systeem bouwen in deze specifieke scenario's.

Ze bewijzen dit aan de hand van drie verschillende "vallen" of argumenten:

1. De "Te Veel Berichten" Val (Onvoorwaardelijke Onmogelijkheid)

Het Scenario: Stel je een aanvaller voor die vraagt om de resultaten voor veel verschillende vergrendelde kluien (ciphertexts) tegelijkertijd te zien, maar vervolgens slechts om één speciale lens (functionele sleutel) vraagt om ze allemaal te decoderen.
De Analogie: Stel je hebt 1.000 vergrendelde dozen. Je vraagt om één masterkey die alle dozen kan openen.
De Quantum Twist: In de quantumwereld is de sleutel misschien een piepkleine, gecomprimeerde quantumtoestand die de instructies voor alle 1.000 dozen bevat?
Het Resultaat: De auteurs bewijzen dat dit onmogelijk is. Het is also eigenlijk proberen de instructies voor 1.000 verschillende boeken in één enkele, kleine notitie te proppen. Zelfs met quantumcompressie kun je simpelweg niet zoveel informatie in een kleine quantumtoestand persen zonder het vermogen te verliezen om de specifieke boeken later te decoderen. Als de simulator probeert om de 1.000 dozen na te bootsen zonder de inhoud te kennen, faalt hij omdat de "sleutel" die hij later genereert, onmogelijk groot zou moeten zijn om al die antwoorden te beschrijven.

2. De "Kleine Sleutel" Val (Succinct Schemes)

Het Scenario: Dit kijkt naar een systeem waarbij de "vergrendelde doos" (ciphertext) heel klein moet zijn, ongeacht hoe complex de wiskundige berekening is.
De Analogie: Stel je een systeem voor waarbij je een roman van 100 pagina's in een piepkleine envelop ter grootte van een postzegel kunt vergrendelen.
De Quantum Twist: De auteurs gebruiken een concept genaamd Pseudorandom Quantum States (PRS). Dit zijn quantumtoestanden die er voor iedereen zonder de geheime sleutel volkomen willekeurig uitzien, maar die eigenlijk door een specifieke formule worden gegenereerd.
Het Resultaat: Ze bewijzen dat je deze willekeurig ogende quantumtoestanden niet kunt "comprimeren". Als je probeert een willekeurige quantumtoestand te verkleinen (om een piepkleine ciphertext te maken), vernietig je de informatie. Het is als het proberen op te vouwen van een wereldkaart tot een vierkante inch; de details gaan verloren. Daarom kan een systeem dat kleine ciphertexts belooft voor complexe wiskundige problemen, niet Simulatie-veilig zijn.

3. De "Veel Sleutels" Val (Public Key Encryption)

Het Scenario: Stel je een aanvaller voor die één vergrendelde doos ziet, maar de toestemming heeft om voor veel verschillende lenzen (functionele sleutels) te vragen om te proberen te achterhalen wat erin zit.
De Analogie: Je hebt één vergrendelde doos. Je vraagt om 1.000 verschillende lenzen. Elke lens is bedoeld om een ander stukje informatie te onthullen.
De Quantum Twist: De auteurs koppelen dit aan Public-Key Encryption (PKE), een standaardmanier waarop we vandaag de dag onze e-mails en websites beveiligen. Ze laten zien dat als er een perfect Quantum Functionele Encryptie-systeem bestond, dit zou leiden tot het breken van de beveiliging van standaard Public-Key Encryptie.
Het Resultaat: Omdat we geloven dat Public-Key Encryptie veilig is, impliceert dit dat een perfect Quantum Functionele Encryptie-systeem niet kan bestaan. Het is een "bewijs door tegenspraak": "Als dit magische systeem bestond, zou het de beveiliging van het internet breken. Aangezien de beveiliging van het internet echt is, is dit magische systeem onmogelijk."

Samenvatting van de Bevindingen

Het artikel sluit in feite de deur op de hoop dat quantummechanica ons kan redden van de beperkingen van Functionele Encryptie.

Klassieke Onmogelijkheid: We wisten al dat je geen perfect "Simulatie-veilig" systeem kon hebben in de klassieke wereld als de aanvaller te veel vragen stelde of te veel berichten zag.
Quantum Realiteit: De auteurs bewijzen dat quantummechanica dit niet oplost. Zelfs met qubits, verstrengeling en quantum-sleutels, voorkomen de fundamentele wetten van de informatietheorie een perfect Simulatie-veilig systeem in deze scenario's.

Ze laten zien dat de "barrière" niet alleen een zwakte is van klassieke computers, maar een fundamentele limiet van hoe informatie (zelfs quantuminformatie) kan worden gecomprimeerd en verborgen.

Wat dit Betekent (en Niet Betekent)

Het betekent NIET dat Functionele Encryptie nutteloos is. We kunnen nog steeds systemen bouren die "goed genoeg zijn" (Indistinguishability-Secure) voor veel praktische toepassingen.
Het betekent NIET dat quantumencryptie gebroken is. Het betekent alleen dat één specifieke, zeer hoog niveau van "perfecte beveiliging" (Simulatie-beveiliging) onbereikbaar is, net zoals dat in de klassieke wereld ook zo was.
Het BETEKENT WEL dat onderzoekers die op zoek zijn naar een "heilige graal" van quantum Functionele Encryptie moeten stoppen met het proberen te bereiken van dit specifieke type perfecte beveiliging, aangezien de wiskunde zegt dat het onmogelijk is.

Technische Samenvatting: Over de onmogelijkheid van simulatie-beveiliging voor Quantum Functionele Encryptie

Probleemstelling
Functionele Encryptie (FE) is een cryptografische primitief die fijnmazige toegang tot versleutelde gegevens mogelijk maakt, waarbij een gebruiker met een functionele sleutel $fk_F$ een functie $F(m)$ kan berekenen uit een encryptie van $m$ , zonder iets anders te leren. De sterkste beveiligingsnotie voor FE is simulatie-gebaseerde beveiliging (SIM-beveiliging), wat vereist dat alles wat een tegenstander kan berekenen uit het cijfertekst en de functionele sleutels, gesimuleerd kan worden met enkel de output van de functie.

Hoewel klassieke onmogelijkheidsresultaten hebben vastgesteld dat SIM-beveiligde FE onbereikbaar is voor algemene polynomiale circuits onder specifieke query-modellen (bijv. veel cijferteksten met één adaptieve sleutel, of een enkele cijfertekst met veel niet-adaptieve sleutels), rusten deze bewijzen op inherent klassieke argumenten. Een cruciale openstaande vraag bleef: breiden deze klassieke onmogelijkheden zich uit naar het quantumregime? Specifiek, kunnen quantumbronnen (quantum cijferteksten, quantum functionele sleutels, of quantum publieke sleutels) deze barrières overwinnen om SIM-beveiligde Quantum Functionele Encryptie (QFE) te realiseren?

Methodologie
De auteurs pakken deze vraag aan door klassieke onmogelijkheidsbewijzen uit te breiden naar de quantumsetting, aangepast om met quantumtoestanden en -operaties om te gaan. De methodologie bestaat uit drie afzonderlijke onmogelijkheidsbewijzen, die elk een verschillende beveiligingsvariant van QFE targeten:

Informatie-theoretische compressie-argumenten: De auteurs herinterpreteren de taak van de simulator in een SIM-beveiligingsspel als een informatiecompressieprobleem. Ze demonstreren dat als een SIM-beveiligd schema zou bestaan, dit zou impliceren dat er een compressiealgoritme bestaat dat grote hoeveelheden informatie (berichten of toestanden) kan comprimeren tot een kleine quantumtoestand (de functionele sleutel of de cijfertekst) terwijl perfect herstel mogelijk is.
Quantum oncomprimeerbaarheid-lemma's:
- Voor het geval van vele cijferteksten maken ze gebruik van een resultaat uit [20] over entanglement-assisted communicatie om aan te tonen dat $n$ bits niet betrouwbaar kunnen worden hersteld uit minder dan $n/2$ qubits.
- Voor het geval van het succincte schema bewijzen ze een nieuw lemma met betrekking tot de oncomprimeerbaarheid van Pseudorandom Toestanden (PRS). Ze tonen aan dat het comprimeren van een $n$ -qubit PRS naar $n-k$ qubits bijna alle structuur onherroepelijk verliest, waarbij de verwachte fidelity van herstel exponentieel daalt met de hoeveelheid compressie. Dit wordt bewezen met behulp van de relatie tussen gemiddelde fidelity en entanglement fidelity, gecombineerd met Levy's Lemma over de concentratie van maat voor Haar-random toestanden.
Reducties naar standaard cryptografische aannames:
- Voor het geval van vele-sleutel queries construeren ze een reductie van het bestaan van een SIM-beveiligde QFE naar het breken van Public-Key Encryptie (PKE). Ze tonen aan dat een simulator voor een 1-M-NA (één bericht, veel queries, niet-adaptief) QFE-schema zou fungeren als een informatiecompressor voor meerdere onafhankelijke PKE-cijferteksten, wat de beveiliging van het onderliggende PKE-schema zou schenden.

Belangrijkste bijdragen en resultaten

Het artikel stelt drie belangrijke onmogelijkheidsresultaten vast voor Secret-Key QFE (wat onmiddellijk de onmogelijkheid voor Public-Key QFE impliceert):

Onvoorwaardelijke onmogelijkheid van M-1-AD SIM-beveiligde QFE:
- Setting: De tegenstander vraagt om encryptie van veel berichten ( $M$ ) en verkrijgt vervolgens een enkele adaptieve functionele sleutel voor de identiteitsfunctie ($1$-AD).
- Resultaat: Een dergelijk schema bestaat niet.
- Mechanisme: De simulator moet $n$ cijferteksten genereren zonder de berichten te kennen. Bij ontvangst van de identiteitssleutel moet de simulator alle $n$ berichten herstellen. Dit vereist het comprimeren van $n$ willekeurige berichten in een functionele sleutel waarvan de grootte begrensd is door een polynoom $p \ll n$ . De auteurs bewijzen dat dit zelfs met quantumtoestanden onmogelijk is, omdat het de informatie-theoretische limieten van het comprimeren van klassieke informatie in een kleinere quantumtoestand schendt.
Conditionele onmogelijkheid van Succinct 1-1-NA SIM-beveiligde QFE:
- Setting: De tegenstander vraagt om een enkel bericht en een enkele niet-adaptieve functionele sleutel. Het schema is succinct (de omvang van de cijfertekst is onafhankelijk van de omvang van de functie).
- Aanname: Bestaan van Pseudorandom Toestanden (PRS).
- Resultaat: Geen enkel dergelijk schema bestaat.
- Mechanisme: De auteurs tonen aan dat een succincte QFE voor de circuitklasse van PRS-generatoren compressie en decompressie van PRS zou mogelijk maken. Ze bewijzen dat PRS oncomprimeerbaar zijn (een eigenschap die sterker is dan klassieke PRF's in sommige contexten, aangezien PRF $\implies$ PRS, maar het omgekeerde niet bekend is). Als een succincte QFE zou bestaan, zou men PRS van Haar-random toestanden kunnen onderscheiden door te controleren of de gecomprimeerde toestand hersteld kan worden, wat de PRS-aanname zou breken.
Conditionele onmogelijkheid van 1-M-NA SIM-beveiligde QFE:
- Setting: De tegenstander vraagt om een enkele cijfertekst en veel niet-adaptieve functionele sleutels.
- Aanname: Bestaan van Public-Key Encryptie (PKE) met klassieke sleutels.
- Resultaat: Geen enkel dergelijk schema bestaat.
- Mechanisme: De auteurs construeren een aanval waarbij de tegenstander de QFE-simulator gebruikt om $n$ onafhankelijke PKE-cijferteksten (die verschillende berichten versleutelen) te comprimeren tot een enkele QFE-cijfertekst. Als de simulator succesvol is, maakt dit het herstel van alle $n$ berichten mogelijk vanuit de enkele gecomprimeerde cijfertekst en de functionele sleutels. Dit schendt de beveiliging van het onderliggende PKE-schema. Opmerkelijk is dat dit resultaat geldt voor niet-succincte schema's, in tegen tegenstelling tot het PRS-gebaseerde resultaat.

Betekenis en Claims

Het artikel claimt de centrale vraag te hebben opgelost of quantumbronnen de klassieke barrières naar SIM-beveiligde FE kunnen omzeilen. De auteurs concluderen dat de klassieke onmogelijkheden grotendeels zich uitstrekken tot de quantumwereld, hoewel de bewijzen nieuwe technische instrumenten vereisen om met quantumtoestanden om te gaan.

Genuanceerde Barrières: De resultaten zijn genuanceerder dan de klassieke. Bijvoorbeeld, de onmogelijkheid van 1-M-NA SIM-beveiliging in de quantumsetting berust op de aanname van PKE (of PRS voor succincte schema's), terwijl het klassieke resultaat onvoorwaardelijk is (omdat klassieke FE een PRF impliceert). Dit benadrukt dat hoewel de barrière bestaat, de specifieke cryptografische aannames die nodig zijn om dit te bewijzen verschillen in de quantumregime.
Onafhankelijkheid van Aannames: Het artikel benadrukt dat de gebruikte aannames (PRS en PKE) niet vergelijkbaar zijn. PKE staat bekend als gescheiden van One-Way Functions (en dus PRS), en er bestaat geen implicatie in de omgekeerde richting. Daarom bieden de twee conditionele onmogelijkheidsresultaten onafhankelijk bewijs tegen het bestaan van SIM-beveiligde QFE.
Nieuwigheid van Bewijzen: De auteurs introduceren een nieuw oncomprimeerbaarheidseigenschap voor Pseudorandom Toestanden, die zij als potentieel van onafhankelijke interesse beschouwen. Ze leveren ook het eerste onmogelijkheidsbewijs voor 1-M-NA SIM-beveiligde QFE dat niet afhankelijk is van de succinctheid van het schema.
Reikwijdte: De resultaten zijn van toepassing op algemene circuitklassen. De auteurs erkennen dat beperkte klassen (bijv. "preimage sampleable" circuits) of specifieke modellen (zoals het bounded-quantum-storage model) nog steeds SIM-beveiliging zouden kunnen toestaan, maar voor algemene QFE lijkt het doel van de simulatie-gebaseerde beveiliging onbereikbaar.

Samenvattend demonstreert het artikel dat de fundamentele spanning tussen de informatie in een cijfertekst en de beperkte omvang van een functionele sleutel (of vice versa) voortduurt in de quantumsetting, wat de realisatie van de sterkste beveiligingsnotie voor functionele encryptie verhindert.