Coset ciclotomici: sottogruppo nascosto e algoritmo di setaccio quantistico per moduli pari a potenze di primi

Abstract degli autori

Il problema Learning With Errors (LWE) è un’assunzione fondamentale nella crittografia post-quantistica. Regev ha stabilito una riduzione quantistica da LWE al Dihedral Coset Problem (DCP). In seguito, Brakerski et al. hanno introdotto l’Extrapolated Dihedral Coset Problem (EDCP), dimostrandone l’equivalenza con LWE. Tuttavia, a differenza del DCP, l’EDCP non ammette più una struttura di coset. Ciò limita l’applicazione diretta delle tecniche per i problemi del sottogruppo nascosto. In questo lavoro introduciamo il Cyclotomic Coset Problem (CCP), una generalizzazione ciclotomica del DCP che conserva un’esatta struttura di sottogruppo nascosto. Sia $ζ_p$ una radice primitiva $p$-esima dell’unità, sia $π=ζ_p-1$, e poniamo $q=p^t$ e $L=t(p-1)$. Lavoriamo su $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$, dove l’isomorfismo deriva dall’identità di ramificazione totale $(p)=(π)^{p-1}$. Sfruttiamo la conseguente catena di ideali $π$-adica per costruire un setaccio quantistico che riduce successivamente gli stati di fase modulo $π^{L},π^{L-1},\ldots,π$. Per ogni primo fissato $p$ e modulo $q=p^t$, il nostro algoritmo risolve il CCP in tempo e con complessità campionaria pari a $2^{O_p(\log n\log q)}$, utilizzando spazio quantistico polinomiale. Il setaccio si applica anche all’EDCP uniforme e al Gaussian S|LWE>, producendo algoritmi in tempo quasi polinomiale per tutti i problemi menzionati quando $q=\text{poly}(n)$. Questo estende a un contesto ciclotomico il setaccio per l’EDCP con potenze di due di Bai et al. (CRYPTO 2025). Tuttavia, sottolineiamo che il nostro risultato, da solo, non fornisce un algoritmo in tempo quasi polinomiale per l’LWE standard, perché la riduzione attualmente nota produce solo un numero limitato di stati CCP approssimati.