⚛️ quantum physics

On the Spectral theory of Isogeny Graphs and Quantum Sampling of Secure Supersingular Elliptic curves

Dit artikel presenteert de eerste bewezen kwantumalgoritmen voor het genereren van veilige supersinguliere elliptische krommen met onbekende endomorfismeringen, waarbij de analyse steunt op nieuwe spectrale resultaten voor isogeniegrafieken die de Quantum Unique Ergodicity-vermoeden bewijzen en heuristische aannames in gerelateerde cryptosystemen elimineren.

Oorspronkelijke auteurs: Maher Mamah, Jake Doliskani, David Jao

Gepubliceerd 2026-03-24

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Maher Mamah, Jake Doliskani, David Jao

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 Gouden Loterijticket: Hoe je veilig willekeurige getallen vindt zonder te vals te spelen

Stel je voor dat je een enorme, ondoordringbare muur moet bouwen. Om deze muur veilig te maken, heb je een heel specifiek, uniek steenblok nodig. Dit blok moet zo gekozen zijn dat niemand (zelfs niet met een supercomputer) kan raden hoe het precies in elkaar zit. In de cryptografie noemen we dit een "veilige kromme".

Het probleem is: hoe kies je zo'n steenblok willekeurig, zonder dat je per ongeluk een "geheime sleutel" (een wiskundige structuur) achterlaat die hackers kunnen gebruiken om de muur te doorbreken?

Tot nu toe was dit een groot mysterie. Mensen dachten: "Als je het niet kunt berekenen, kun je het ook niet veilig maken." Of ze moesten vertrouwen op een "vertrouwde meester" (een trusted setup) die het voor je deed, wat riskant is als die meester vals speelt.

De auteurs van dit paper, Maher Mamah, Jake Doliskani en David Jao, hebben een kwantum-methode bedacht om dit probleem op te lossen. Ze gebruiken een slimme truc met "kwantum-golven" om een veilig steenblok te vinden, zonder dat ze ooit hoeven te weten hoe het eruitziet voordat ze het kiezen.

Hier is hoe het werkt, stap voor stap:

1. De Labyrinten van de Krommen (Isogeny Graphs)

Stel je een gigantisch labyrint voor, bestaande uit miljoenen kamers. Elke kamer is een wiskundig object (een elliptische kromme). De deuren tussen de kamers zijn "isogenieën" (speciale verbindingen).

Het doel: Je wilt in een willekeurige kamer eindigen.
Het gevaar: Als je zelf een pad loopt (een wandeling door het labyrint), weet je precies waar je vandaan komt. Een hacker kan dan terugrekenen: "Ah, hij kwam van kamer A, dus hij weet de route!"
De oplossing: Je wilt niet lopen. Je wilt dat de kamer vanzelf "opduikt" zonder dat je de route hebt gelopen.

2. De Kwantum-Truc: Het Muziekorkest

In plaats van te lopen, gebruiken de auteurs kwantumcomputers. Ze behandelen het hele labyrint als een groot muziekindstrument.

Elke kamer in het labyrint heeft een eigen "klank" of frequentie (een eigenwaarde).
De auteurs gebruiken een techniek genaamd Quantum Phase Estimation. Dit is alsof je naar het labyrint luistert en precies de toonhoogte van de kamers kunt meten.
Ze spelen een "kwantum-golf" door het labyrint. Deze golf trilt op alle mogelijke paden tegelijk. Door heel precies te meten welke tonen (frequenties) er spelen, kunnen ze de golf "filteren" tot hij alleen nog maar op één specifieke kamer resoneren.

De Analogie:
Stel je voor dat je in een groot concertzaal staat met duizenden zangers. Iedereen zingt een ander geluid. Je wilt één specifieke zanger vinden, maar je mag niet naar hem wijzen.
In plaats daarvan zing je een toon die precies past bij die ene zanger. Door de toon heel langzaam te veranderen (de "filter"), hoor je plotseling alleen nog die ene zanger. De rest van de zaal wordt stil. Je hebt de zanger gevonden zonder te weten wie hij was voordat je begon!

3. Waarom is dit veilig? (De "Verstrooiing")

De grootste angst was: "Misschien zit de kwantum-golf toch vast in een paar specifieke kamers, en niet willekeurig?" Als dat zo is, is de uitkomst niet veilig.

De auteurs bewijzen iets heel moois: De golven zijn "verstrooid" (delocalized).

Vergelijking: Stel je voor dat je inkt in een glas water doet. Als de inkt in één klont blijft zitten, is dat slecht. Maar als de inkt zich perfect door het hele glas verspreidt, is elke druppel water even "zwart".
Ze bewijzen wiskundig dat de kwantum-golven zich perfect verspreiden over het hele labyrint. Geen enkele kamer heeft een "voordeel". Het is dus echt een eerlijke loterij.
Ze gebruiken een hypothese genaamd de Generalized Riemann Hypothesis (een beroemde wiskundige gok) om te bewijzen dat de tonen van de kamers zo verschillend zijn dat je ze nooit kunt verwarren.

4. Twee Manieren om het te doen

Het paper beschrijft twee methoden:

De "Grote Labyrint" Methode (Algorithm 1):
- Dit is de meest krachtige versie. Het gebruikt de "muziek" van het hele labyrint.
- Het is heel snel op een kwantumcomputer (snelheid hangt af van het getal $p$ , maar is polynomiaal).
- Voordeel: Het is bewezen veilig, zolang het "EndRing-probleem" (het vinden van de sleutel) moeilijk blijft.
De "Georiënteerde" Methode (Algorithm 3):
- Soms wil je niet zomaar een kamer, maar een kamer met een specifieke "stempel" (een orientatie). Denk aan een kamer die een rode vlag heeft.
- Deze methode gebruikt een andere kwantum-truc (Fourier-transformatie) om willekeurig een kamer met zo'n stempel te kiezen.
- Dit is handig voor specifieke cryptografische toepassingen die al bestaan (zoals CSIDH).

5. Wat betekent dit voor de wereld?

Voorheen moesten we vertrouwen op een "vertrouwde instantie" (zoals een overheid of een bedrijf) om deze veilige getallen te genereren. Als die instantie vals speelde, was de hele beveiliging weg.

Met deze nieuwe kwantum-algoritmen:

Geen vertrouwde instantie nodig: Iedereen kan zelf een veilige kromme genereren.
Verifieerbaar: Je kunt controleren of de computer eerlijk heeft gewerkt (door interactieve protocollen).
Toekomstbestendig: Het is veilig tegen hackers met toekomstige kwantumcomputers.

Samenvatting in één zin

De auteurs hebben bewezen dat je met een kwantumcomputer een willekeurig, veilig wiskundig object kunt "luisteren" naar zijn unieke geluid en zo kunt isoleren, zonder ooit te hoeven weten hoe je er bent gekomen, waardoor je een onkraakbare basis legt voor de cryptografie van de toekomst.

Het is alsof je een slot opent door te luisteren naar de trillingen van het metaal, in plaats van te proberen de sleutel te smeden. En het beste deel? Je weet niet eens hoe het slot eruitzag voordat je het opende.

Titel: Spectrale Theorie van Isogenie-Graphen en Quantum Sampling van Veilige Supersinguliere Elliptische Curven

Auteurs: Maher Mamah, Jake Doliskani, David Jao
Institutionen: Universiteit van Waterloo, McMaster University

1. Het Probleem

Isogenie-based cryptografie is een veelbelovende richting voor post-quantum cryptografie. Veel protocollen (zoals de CGL-hashfunctie, commitment-schema's en VDF's) vereisen een "veilige" startkromme: een supersinguliere elliptische kromme waarvan de ring van endomorfismen ( $\text{End}(E)$ ) onbekend is voor de gebruiker.

Huidige situatie: Er zijn geen efficiënte klassieke of quantum-algoritmen bekend die dergelijke krommen met garantie kunnen genereren zonder een "trusted setup" (vertrouwde opstelling).
Bestaande methoden:
- Genereren via $j$ -invarianten vereist exponentiële resources.
- Heuristische quantum-algoritmen (zoals [BBD+24]) bieden geen bewezen veiligheid.
- Trusted setup-protocollen (zoals [BCC+23]) vereisen dat meerdere partijen samenwerken, wat niet ideaal is voor gedecentraliseerde toepassingen.
De uitdaging: Hoe genereer je efficiënt een supersinguliere kromme waarvan de endomorfismenring onbekend is, zonder vertrouwen in een derde partij, en met een bewezen veiligheidsbewijs?

2. Methodologie

De auteurs presenteren twee quantum-algoritmen die gebruikmaken van de spectrale eigenschappen van supersinguliere isogenie-graphen en groepswerkingen.

A. Spectrale Delokalisatie en Eigenwaarde-scheiding

De kern van de analyse ligt in de eigenschappen van de $\ell$ -isogenie-graf $G(p, \ell)$ .

Spectrale Delokalisatie: De auteurs bewijzen een nieuwe schatting voor de sup-norm van eigenvectoren van de Brandt-operatoren (die corresponderen met de adjacency matrix van de graf). Ze bewijzen dat eigenvectoren niet geconcentreerd zijn op een kleine set krommen, maar "delokalisiert" zijn over de hele graf.
- Resultaat: $\|\phi\|_\infty \ll (pN)^{-1/4+\varepsilon}$ .
- Dit ondersteunt de Quantum Unique Ergodicity (QUE) conjectuur in deze context.
$\varepsilon$ -Scheiding: Een cruciale vereiste voor quantum phase estimation is dat verschillende eigenvectoren unieke "spectrale tags" (eigenwaarde-vectoren) hebben.
- De auteurs bewijzen onder de Generalized Riemann Hypothesis (GRH) een striktere scheiding voor eigenwaarden dan eerder werd voorspeld in heuristische werken.
- Ze tonen aan dat de eigenwaarden voldoende gescheiden zijn ( $\varepsilon \gg 1$ ) om eigenvectoren betrouwbaar te identificeren via quantum metingen.

B. Algoritme 1: Sampling van de Volledige Isogenie-graf

Dit algoritme genereert een willekeurige supersinguliere kromme zonder niveau-structuur.

Methode: Het gebruikt Hamiltonian simulation en Quantum Phase Estimation (QPE).
1. Start met een superpositie over eigenvectoren van de graf.
2. Pas QPE toe op een reeks commuterende adjacency-operatoren ( $A_{\ell_1}, \dots, A_{\ell_r}$ ) om de "spectrale tag" van de toestand te meten.
3. Door de $\varepsilon$ -scheiding te garanderen, wordt de toestand gefilterd naar een enkele eigenvector.
4. Meet de krommeregister. Door de delokalisatie-eigenschap is de kansverdeling over de krommen bijna uniform.
Complexiteit:
- Heuristisch: $\tilde{O}(\log^4 p)$ quantum gate complexiteit.
- Onder GRH: $\tilde{O}(\log^{13} p)$ met bewezen garanties.

C. Algoritme 2: Sampling van O-georiënteerde Krommen

Dit algoritme genereert krommen met een specifieke oriëntatie (relevant voor CSIDH en CSI-FiSh).

Methode: Het maakt gebruik van de regelmatige werking van de class group $\text{Cl}(\mathcal{O})$ $Cl (O)$ op de set van georiënteerde krommen.
1. Gebruik de Fourier-basis van de groepswerking.
2. Pas een "phase-kickback" procedure toe om de index van de groepselementen in superpositie te berekenen.
3. Meet het resultaat om een uniforme georiënteerde kromme te krijgen.
Complexiteit: Polynomiële quantum-tijd.

3. Belangrijkste Bijdragen

Eerste bewezen quantum-polynoomtijd algoritmen: De auteurs leveren de eerste algoritmen die met hoge waarschijnlijkheid veilige supersinguliere krommen genereren, met een volledig bewezen complexiteitsanalyse en veiligheidsbewijs.
Oplossing van het "Trusted Setup" probleem: De algoritmen genereren veilige krommen zonder dat een startkromme met bekende endomorfismenring nodig is, en zonder een trusted setup.
Theoretische doorbraken in Spectrale Theorie:
- Bewijs van een sterke delokalisatie voor eigenvectoren van isogenie-graphen (ondersteuning van QUE).
- Een striktere $\varepsilon$ -scheiding voor eigenwaarden onder GRH, wat een heuristische aanname uit eerdere werken (zoals [KSS22], [Dol23]) vervangt door een rigoureuze voorwaarde.
Veiligheidsbewijzen:
- Voor Algoritme 1: Veiligheid onder de aanname van de gemiddelde-case hardheid van het EndRing-probleem (het berekenen van de endomorfismenring).
- Voor Algoritme 2: Veiligheid onder de hardheid van het Vectorization-probleem voor de class group actie.

4. Resultaten

Output: Een supersinguliere elliptische kromme $E$ (en eventueel een oriëntatie) waarvan de endomorfismenring onbekend is.
Veiligheid: Het is bewezen dat een quantum-adversariaal met polynoomtijd slechts een verwaarloosbare kans heeft om de endomorfismenring van de gegenereerde kromme te berekenen, mits de onderliggende hardheidsaannames gelden.
Efficiëntie: De algoritmen zijn efficiënt in termen van het aantal qubits en gates (polynoom in $\log p$ ), hoewel de constante factoren en de noodzaak van Hamiltonian simulation (voor Algoritme 1) in de praktijk uitdagend kunnen zijn.
Verificatie: Door interactieve quantum-verificatieprotocollen te combineren, kan de correctheid van de gegenereerde kromme verifieerbaar worden gemaakt, zelfs in een omgeving met een "honest-but-curious" tegenstander.

5. Betekenis en Impact

Dit werk is van fundamenteel belang voor de toepassing van isogenie-based cryptografie:

Praktische Implementatie: Het lost een van de grootste praktische belemmeringen op: het genereren van veilige startparameters voor protocollen zoals CGL-hash, VDF's en commitment-schema's zonder vertrouwen in een centrale autoriteit.
Theoretische Stijging: Het vervangt heuristische aannames (die vaak in de literatuur worden gebruikt voor quantum-moneys en hash-functies) door rigoureuze wiskundige bewijzen onder standaard hypothese (GRH).
Toekomstperspectief: Het biedt een basis voor het opzetten van een publiek vertrouwd "hard" startpunt (bijv. door NIST) waarvandaan andere protocollen veilig kunnen worden gebootst, wat de weg vrijmaakt voor bredere adoptie van post-quantum isogenie-systemen.

Kortom, de paper levert een kwantitatief en kwalitatief verbeterde methode om de basis van isogenie-cryptografie te versterken door gebruik te maken van geavanceerde spectrale theorie en quantum-algoritmen.