L’algoritmo quantistico di Simon per il DCP: cosa sostiene e perché non ha ancora compromesso la crittografia post-quantistica

La posta in gioco è soprattutto teorica. Se la dimostrazione fosse corretta, il risultato potrebbe colmare una lacuna rimasta aperta per circa vent’anni e avere conseguenze sui collegamenti tra il DCP, i problemi reticolari e alcuni fondamenti della crittografia post-quantistica . Ma il preprint non rappresenta, oggi, un attacco pratico contro gli standard crittografici in uso.

Che cosa sostiene il preprint

Il DCP è un problema matematico legato alla ricerca di informazione nascosta in stati quantistici associati a gruppi diedrali. Da anni è considerato un possibile ponte verso problemi reticolari, la famiglia di problemi matematici su cui si basano diversi algoritmi post-quantistici .

Le tesi principali di Simon sono quattro:

• Un risolutore polinomiale per il DCP. L’algoritmo dovrebbe risolvere il problema in tempo polinomiale su un computer quantistico, sviluppando il percorso teorico aperto dalla riduzione di Regev del 2002, che collega il Dihedral Subgroup Problem al DCP .
• La chiusura di una lacuna ventennale. Se confermato, il risultato completerebbe il passaggio che mancava dopo il collegamento stabilito da Regev tra DCP e problemi reticolari, una questione rimasta irrisolta all’incirca dal 2004 .
• Un approccio tecnico differente. Il lavoro sostituisce un oracle fondamentale degli approcci precedenti con una tecnica definita “block-and-query”, pensata per estrarre informazioni sul sottogruppo nascosto .
• Possibili conseguenze per i reticoli. Secondo il preprint, l’algoritmo potrebbe essere combinato con le riduzioni di Regev e con i miglioramenti di Brakerski, Kirshanova, Stehlé e Wen . Da questa combinazione deriverebbero algoritmi quantistici polinomiali per vari problemi reticolari, tra cui l’approssimazione entro un fattore polinomiale del vettore più corto — lo Shortest Vector Problem, o SVP — e il Learning With Errors, noto come LWE .

Il documento afferma inoltre che il metodo può tollerare un tasso di campioni difettosi fino a 1/O(log n). Questa proprietà sarebbe importante per combinare in modo efficiente l’algoritmo con le riduzioni verso i problemi reticolari .

Perché la comunità resta prudente

A pochi giorni dalla pubblicazione, la reazione degli esperti è stata descritta come cauta, se non apertamente scettica . Il motivo non è il tema trattato, che è certamente rilevante, ma il livello di verifica raggiunto dal lavoro.

• Non c’è ancora una revisione paritaria. Il documento è esplicitamente indicato come “Preliminary Draft”: non è stato sottoposto a peer review né pubblicato in una rivista o in una conferenza .
• Alcuni passaggi decisivi sono solo abbozzati. Diverse analisi iniziali osservano che alcune dimostrazioni essenziali sono presentate in forma schematica. Anche il corollario finale relativo ai parametri di SVP e LWE si basa in parte su comunicazioni personali non ancora accompagnate da derivazioni pubblicate .
• Manca una conferma indipendente. Nei giorni successivi alla comparsa del preprint non risultavano ancora verifiche o confutazioni indipendenti pubblicate . La linea prevalente è quindi: prima i fatti, poi le conclusioni .
• Non è stato realizzato un attacco operativo. Il lavoro sostiene un risultato sul DCP; non presenta un attacco implementato contro un sistema crittografico standardizzato .

In altre parole, il punto da verificare per primo è la correttezza delle dimostrazioni. Anche una tesi teorica potenzialmente rivoluzionaria non diventa automaticamente una minaccia concreta solo perché è stata caricata su un archivio di preprint.

Che cosa significa per ML-KEM e ML-DSA

Per le organizzazioni che stanno adottando o valutando gli standard post-quantistici del NIST, la risposta immediata è semplice: non c’è, sulla base di questo preprint, un motivo per cambiare rotta .

• Nessuna minaccia pratica immediata. Il preprint non implementa un attacco contro ML-KEM, standardizzato nel FIPS 203, né contro ML-DSA, standardizzato nel FIPS 204 . Nessun set di parametri NIST è stato attaccato .
• Il collegamento è indiretto. Il DCP è connesso ai problemi reticolari attraverso riduzioni note. Tuttavia, dimostrare che tali riduzioni producano un attacco concreto a Module-LWE o Module-SIS — le ipotesi di difficoltà specifiche alla base, rispettivamente, di ML-KEM e ML-DSA — richiede un ulteriore passaggio teorico che non è stato stabilito .
• Il rischio, se confermato, sarebbe innanzitutto strutturale. Il risultato rafforzerebbe l’idea che un computer quantistico possa risolvere efficientemente alcuni problemi reticolari. Ma “problemi reticolari” è una categoria più ampia delle specifiche strutture reticolari impiegate dagli standard NIST .
• Esiste un precedente recente, ma diverso. Nel 2025 Bai e colleghi hanno presentato un algoritmo quantistico in tempo quasi polinomiale per una variante ristretta del DCP, l’Extrapolated Dihedral Coset Problem su moduli potenze di due . La pretesa di Simon di ottenere tempo pienamente polinomiale sarebbe quindi un salto considerevole, ma al momento non verificato.

È importante distinguere tra tre livelli diversi: un algoritmo per un problema astratto, una riduzione teorica verso una famiglia di problemi reticolari e un attacco effettivo contro un’istanza concreta di ML-KEM o ML-DSA. Il preprint si colloca al primo livello e sostiene conseguenze sul secondo; non dimostra il terzo.

La risposta degli esperti: attendere e verificare

La comunità della crittografia e della sicurezza post-quantistica sta adottando una posizione sostanzialmente condivisa: esaminare il lavoro con attenzione, senza però reagire come se gli standard fossero già stati spezzati .

Le prime analisi parlano di “forte scetticismo” soprattutto per la forma schematica delle dimostrazioni e per il ricorso a riferimenti non pubblicati . Inoltre, anche nell’ipotesi che il DCP fosse davvero risolvibile in tempo polinomiale, le conseguenze per la crittografia basata su reticoli resterebbero condizionate: dipenderebbero dalla validità e dall’applicabilità dell’intera catena di riduzioni, non dalla sola risoluzione del DCP .

NIST, laboratori accademici e organismi di standardizzazione non hanno ancora diffuso dichiarazioni formali, un’assenza comprensibile dato che il preprint è stato pubblicato da pochi giorni . Per ora non risultano indicazioni per modificare le tempistiche di migrazione post-quantistica, i set di parametri o le raccomandazioni operative .

La conclusione, oggi

Il lavoro di Daniel Simon è una tesi teorica importante, perché potrebbe colmare una lacuna di lunga data nel rapporto tra il Dihedral Coset Problem e i problemi reticolari. Se le prove venissero confermate, l’impatto sulla ricerca in crittografia quantistica e post-quantistica sarebbe significativo.

Ma la verifica è ancora tutta da fare. Il documento non è sottoposto a peer review, alcune dimostrazioni chiave sono presentate come abbozzi e non esiste un attacco contro ML-KEM, ML-DSA o altri parametri NIST. Per questo, allo stato attuale, la risposta più corretta non è “la crittografia post-quantistica è stata infranta”, bensì: è comparsa una pretesa teorica rilevante, che richiede un controllo indipendente e rigoroso prima di produrre qualsiasi conseguenza pratica.