⚛️ quantum physics

Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

Dit artikel introduceert het Cyclotomische Coset Probleem (CCP) als een verborgen-subgroep-behoudende generalisatie van het Dihedrale Coset Probleem en presenteert een kwantum-sieving-algoritme dat CCP, uniforme EDCP en Gaussische S|LWE oplost in quasi-polynomiale tijd voor priemmachtmoduli, hoewel het nog geen quasi-polynomiale-tijd oplossing oplevert voor standaard LWE vanwege beperkingen in de staatgeneratie van de reductie.

Oorspronkelijke auteurs: Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

Gepubliceerd 2026-09-29

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

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

In de stille, risicovolle wereld van digitale beveiliging is een fundamentele uitdaging al lang hoe informatie te beschermen tegen de toekomstige dreiging van quantumcomputers. Decennialang hebben cryptografen vertrouwd op een wiskundige puzzel die bekend staat als Learning With Errors. Stel je voor dat je probeert een verborgen pad door een dicht bos te vinden, maar elke keer dat je een stap zet, verschuift de grond onder je lichtjes, waardoor je metingen worden verstoord. Deze "ruis" maakt de puzzel ongelooflijk moeilijk op te lossen voor standaardcomputers, maar het blijft het fundament van veel voorgestelde encryptiesystemen die ontworpen zijn om quantum-aanvallen te weerstaan. De veiligheid van deze systemen hangt af van de aanname dat zelfs een krachtige quantumcomputer de verborgen route niet efficiënt kan terugbrengen naar de oorspronkelijke gegevens vanuit de ruis.

Om de kracht van deze aanname te begrijpen, vertalen onderzoekers het probleem vaak naar een andere taal, een taal die betrekking heeft op quantumtoestanden en verborgen groepen. Denk aan een quantumtoestand als een delicate, onzichtbare munt die tegelijkertijd in een superpositie van kop en munt kan bestaan. In sommige versies van het probleem zijn deze munten zo gerangschikt dat ze een verborgen patroon onthullen, vergelijkbaar met het vinden van een specifiek ritme in een complex lied. Jarenlang wisten wetenschappers hoe ze een specifieke, vereenvoudigde versie van deze patroonzoektaak konden oplossen, maar de complexere, realistische versies bleven hardnekkig resistent tegen quantumoplossingen. De vraag was of een quantumcomputer uiteindelijk de volledige, ruizige versie van de puzzel zou kunnen kraken, of dat de ruis sterk genoeg is om het voor altijd veilig te houden.

Een team onderzoekers uit Rennes, Frankrijk, heeft nu een belangrijke stap gezet naar het beantwoorden van deze vraag door een nieuw wiskundig kader te introduceren dat de kloof tussen het eenvoudige en het complexe overbrugt. Ze ontwikkelden een methode om een gegeneraliseerde versie van het patroonzoekprobleem op te lossen, die ze het Cyclotomic Coset Problem noemen. Deze nieuwe aanpak werkt over een specifiek type getallensysteem dat anders werkt dan de standaard gehele getallen, waardoor de onderzoekers een krachtige techniek genaamd quantum sieving kunnen toepassen. Door quantumtoestanden zorgvuldig te filteren en te combineren, kan hun algoritme lagen van complexiteit afpellen, waardoor het verborgen geheim geleidelijk wordt onthuld. Het resultaat is een quantumalgoritme dat dit specifieke, gegeneraliseerde probleem kan oplossen in een tijd die aanzienlijk sneller is dan exponentieel, maar nog steeds langzamer dan de razendsnelle snelheid van een polynomiale oplossing.

De onderzoekers zijn echter voorzichtig in het verduidelijken van wat hun ontdekking wel en niet betekent voor de toekomst van encryptie. Hoewel hun methode het gegeneraliseerde probleem succesvol oplost voor een breed scala aan parameters, breekt het nog niet het standaard Learning With Errors-probleem dat wordt gebruikt in de echte wereld van de cryptografie. De reden hiervoor ligt in het aantal monsters dat nodig is. Het algoritme heeft een enorme hoeveelheid quantumdata nodig om effectief te functioneren, veel meer dan wat momenteel beschikbaar is via de standaard reductie die het encryptieprobleem omzet in het patroonzoekprobleem. In essentie hebben de onderzoekers een zeer krachtige sleutel gebouwd, maar het slot dat ze proberen te openen, vereist een sleutelring die te groot is om met de huidige methoden te produceren.

De kern van hun werk omvat een slimme manipulatie van quantumtoestanden over een structuur genaamd een cyclotomische ring. In simpelere termen hebben ze een nieuwe manier gecreëerd om de quantuminformatie te organiseren zodat deze een verborgen structuur behoudt, zelfs wanneer het oorspronkelijke probleem die structuur leek te hebben verloren. Ze bereikten dit door een nieuw type groep te definiëren, een wiskundige structuur die hen in staat stelt een "zeef" te gebruiken om ongewenste informatie eruit te filteren. Deze zeef werkt door quantumtoestanden herhaaldelijk te combineren op een manier die ruis wegcijfert en het signaal van het verborgen geheim versterkt. Het proces is iteratief en beweegt stap voor stap door verschillende niveaus van wiskundige precisie, vergelijkbaar met het verfijnen van een ruwe steen tot een edelsteen door laag voor laag kleine stukjes materiaal te verwijderen.

Hun bevindingen tonen aan dat voor een specifieke klasse problemen met priemmacht-moduli, het verborgen geheim kan worden teruggevonden in wat bekend staat als quasi-polynomiale tijd. Dit is een middenweg tussen de trage, exponentiële tijd die klassieke computers nodig hebben om moeilijke problemen op te lossen, en de directe snelheid van polynomiale tijd. Het algoritme gebruikt een aantal quantummonsters dat traag genoeg groeit om als efficiënt te worden beschouwd voor bepaalde parameters, maar de onderzoekers benadrukken dat deze efficiëntie niet automatisch vertaalt naar een breuk in de standaard encryptie. De reductie van het standaard encryptieprobleem naar hun nieuwe probleem produceert slechts een beperkt aantal van de noodzakelijke quantumtoestanden, wat een flessenhals creëert die voorkomt dat het algoritme direct kan worden toegepast om huidige cryptografische systemen te breken.

Het artikel verkent ook de relatie tussen hun nieuwe probleem en andere bekende quantumuitdagingen, zoals het Dihedral Coset Problem en het Extrapolated Dihedral Coset Problem. Ze laten zien dat hun methode deze gerelateerde problemen kan oplossen wanneer de modulus een macht is van een priemgetal, waarmee eerdere resultaten die beperkt waren tot machten van twee worden uitgebreid. Deze generalisering is significant omdat het aantoont dat de onderliggende wiskundige structuur robuuster en veelzijdiger is dan voorheen gedacht. Door te bewijzen dat deze problemen onder bepaalde omstandigheden equivalent zijn, bieden de onderzoekers een duidelijkere kaart van het landschap van de quantum-resistente cryptografie, waarbij ze laten zien waar de zwakke punten kunnen liggen en waar de verdedigingen solide blijven.

Uiteindelijk dient dit werk als een rigoureuze stresstest voor de aannames die ten grondslag liggen aan de post-quantum cryptografie. Het bevestigt dat hoewel quantumcomputers de theoretische kracht bezitten om bepaalde complexe patroonzoekproblemen veel sneller op te lossen dan klassieke machines, de specifieke ruis en beperkingen van het Learning With Errors-probleem een formidabele barrière vormen. De onderzoekers hebben aangetoond dat zelfs met geavanceerde quantumtechnieken, de weg naar het breken van de encryptie niet zo direct is als men zou hopen. De "ruis" in het systeem is niet slechts een klein ongemak; het is een fundamenteel kenmerk dat, in combinatie met de beperkingen van de huidige generatie van quantummonsters, het verborgen pad veilig houdt. De studie concludeert dat hoewel het veld aanzienlijk is gevorderd in het begrijpen van de mechanica van deze quantumpuzzels, de standaard encryptiemethoden veilig blijven voor deze specifieke aanvalslijn, althans voor de nabije toekomst.

Technische Samenvatting: Cyclotomische Cosets, Hidden Subgroup, en Quantum Sieving voor Prime-Power Moduli

1. Probleemcontext en Motivatie

Het Learning With Errors (LWE) probleem is een fundamentele aanname in post-kwantum cryptografie. Terwijl Regev een kwantumreductie heeft vastgesteld van LWE naar het Dihedrale Coset Problem (DCP), en Brakerski et al. later het Extrapolated Dihedral Coset Problem (EDCP) introduceerden om equivalentie met LWE te bewijzen, bestaat er een significante structurele beperking. In tegenstelling tot DCP bezit algemene EDCP geen exacte hidden-subgroup structuur, omdat de verzameling translaties geen subgroep vormt. Deze beperking verhindert de directe toepassing van efficiënte hidden-subgroup technieken, met name voor moduli die geen machten van twee zijn.

Recent werk door Bai et al. (CRYPTO 2025) bereikte een quasi-polynomiaal-tijd kwantumalgoritme voor EDCP en Gaussian $S|LWE\rangle$ over machten-van-twee moduli ( $q=2^t$ ) door gebruik te maken van een specifieke 2-adische ideale keten. Het generaliseren hiervan naar willekeurige prime-power moduli ( $q=p^t$ ) is echter moeilijk gebleken, omdat de dihedrale groep van orde $2q$ alleen nilpotent is als $q$ een macht van twee is. Bijgevolg konden standaard nilpotent group sieving technieken (zoals die van Imran en Ivanyos) niet direct worden toegepast op EDCP of DCP met niet-macht-van-twee moduli.

2. Methodologie en Kernconstructie

2.1 De Cyclotomische Coset Problem (CCP)

Om het gebrek aan een hidden-subgroup structuur in EDCP voor algemene priemachten te overwinnen, introduceren de auteurs de Cyclotomic Coset Problem (CCP). Dit probleem is gedefinieerd over de cyclotomische ring $R_q = \mathbb{Z}_q[\zeta_p]$ , waarbij $p$ een priemgetal is, $q=p^t$ , en $\zeta_p$ een primitieve $p$ -de eenheidswortel is.

De auteurs definiëren een semidirect product groep $G_{n,q,p} = R_q^n \rtimes \mathbb{F}_p$ . Zij bewijzen dat deze groep nilpotent is met een nilpotentie klasse van $t(p-1)$ . Binnen deze groep identificeren zij een hidden subgroup $H_s$ gegenereerd door $(s, 1)$ , waarbij $s$ de geheime vector is. De coset states geassocieerd met deze subgroep nemen de vorm aan:
$|\phi_{x,s}\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} |j\rangle |x + \lambda_j s \rangle$
waarbij $\lambda_j = \sum_{i=0}^{j-1} \zeta_p^i$ . Wanneer $p=2$ , reduceert deze constructie exact naar de standaard DCP.

2.2 Quantum Fourier Transform (QFT) over Cyclotomische Ringen

Een cruciaal technisch onderdeel is de definitie en efficiënte implementatie van de Quantum Fourier Transform over de ring $R_L = R/\pi^L R$ , waarbij $\pi = \zeta_p - 1$ . Gebruikmakend van de field trace en de $\pi$ -adische decompositie van het ideaal $(p) = (\pi)^{p-1}$ , construeren de auteurs een QFT die CCP samples naar phase states transformeert.

Deze transformatie zet het probleem van het herstellen van $s$ uit coset states om in het Phase-State Problem (PSP), waarbij het geheim gecodeerd is in de fase van de kwantumtoestand:
$|\psi_y\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} \chi_y(\lambda_j s) |j\rangle$
Hierbij is $\chi_y$ een karakter van de additieve groep van de ring.

2.3 Het Quantum Sieving Algoritme

De auteurs passen het "Simon-meets-Kuperberg" framework aan voor de cyclotomische setting. Het algoritme opereert door het modulusniveau iteratief te reduceren met behulp van de $\pi$ -adische ideale keten:
$R_q \cong R_{\pi^L} \to R_{\pi^{L-1}} \to \dots \to R_{\pi} \cong \mathbb{F}_p$

Het sieving proces omvat:

Zero-Sum Search: Gegeven een verzameling phase-state samples met labels $y_i$ , vindt het algoritme een deelreeks zodanig dat $\sum y_i \equiv 0 \pmod \pi$ . Dit wordt bereikt met een deterministisch zero-sum search algoritme (gebaseerd op Imran en Ivanyos) toegepast op de residuen modulo $\pi$ .
State Combination: Door de overeenkomstige kwantumtoestanden te tensoriseren en specifieke basisveranderingen en metingen uit te voeren, produceert het algoritme een nieuwe phase-state sample met een label in de lagere ring $R_{\pi^{L-1}}$ .
Iteratie: Dit proces wordt $L-1$ keer herhaald om het probleem te reduceren tot de basisgeval over $\mathbb{F}_p$ , waar het geheim kan worden hersteld via lineaire algebra.
Lifting: Zodra $s \pmod p$ gevonden is, lost het algoritme recursief de hogere machten van $p$ op om het volledige geheim $s \in \mathbb{Z}_q^n$ te herstellen.

3. Belangrijkste Bijdragen

Introductie van CCP en CyLWE: Het artikel definieert de Cyclotomic Coset Problem (CCP) en Cyclotomic LWE (CyLWE). Het stelt vast dat deze problemen voor constante $p$ equivalent zijn aan hun klassieke tegenhangers (DCP en LWE) en een hidden-subgroup structuur bezitten over een nilpotent groep, in tegen tegenstelling tot algemene EDCP.
Cyclotomische QFT en Phase States: De auteurs definiëren rigoureus de QFT over cyclotomische ringen $R_q$ en demonstreren hoe CCP samples getransformeerd kunnen worden naar phase states, wat de toepassing van sieving technieken mogelijk maakt.
Quasi-Polynomial Sieving Algoritme: Zij presenteren een kwantumalgoritme (Algoritme 1) dat CCP oplost in quasi-polynomiale tijd ( $2^{O(\log n \log q)}$ ) metens polynomiale kwantumruimte, mits het aantal samples ook quasi-polynomial is.
Generalisatie van Eerdere Resultaten: Het werk breidt de quasi-polynomiale tijd resultaten van Bai et al. (die beperkt waren tot $q=2^t$ ) uit naar elke prime-power modulus $q=p^t$ .
Equivalentiebewijzen: Het artikel levert kwantumreducties die aantonen dat:
- Uniforme EDCP en Gaussian $S|LWE\rangle$ over prime-power moduli gereduceerd kunnen worden naar CCP.
- Bijgevolg quasi-polynomiale-tijd kwantumalgoritmen bestaan voor uniforme EDCP en Gaussian $S|LWE\rangle$ wanneer $q=p^t$ .

4. Resultaten en Complexiteit

Complexiteit: Het voorgestelde algoritme lost CCP op met een tijd- en samplecomplexiteit van $2^{O(\log n \log q)}$ met gebruik van polynomiale kwantumruimte.
Scope: De resultaten zijn van toepassing op elke modulus $q = p^t$ waarbij $p$ een vast priemgetal is.
Reducties: Het artikel stelt vast dat het oplossen van CCP het oplossen van uniforme EDCP en Gaussian $S|LWE\rangle$ in quasi-polynomiale tijd mogelijk maakt onder dezelfde parametervoorwaarden.

5. Betekenis en Beperkingen

De auteurs benadrukken dat hoewel dit werk het begrip van kwantumalgoritmen voor lattice-gebaseerde problemen over prime-power moduli aanzienlijk heeft vergroot, het niet leidt tot een quasi-polynomial algoritme voor standaard LWE.

De beperking komt voort uit de reductieketen:

Standaard LWE reduceert naar DCP (of EDCP).
DCP/EDCP reduceert naar CCP.
De CCP solver vereist een quasi-polynomial aantal samples.

De bekende reducties van LWE naar DCP/EDCP produceren slechts een beperkt (polynomial) aantal benaderde toestanden. Omdat het aantal samples dat vereist is door de CCP solver groter is dan het aantal samples dat beschikbaar is vanuit de LWE reductie, blijft de totale complexiteit voor het oplossen van standaard LWE exponentieel.

Hiermee is de primaire bijdrage van het artikel dus theoretisch: het breidt de kracht van nilpotent group sieving uit naar een bredere klasse van moduli en biedt een verenigd framework voor coset problemen over cyclotomische ringen, terwijl het een bescheiden standpunt inneemt over de directe dreiging voor de veiligheid van standaard LWE.