Daniel Simonin kvanttialgoritmiväite herättää kysymyksiä – ML-KEM ja ML-DSA eivät ole murtuneet

Simonin keskeiset väitteet ovat seuraavat:

• DCP voidaan ratkaista polynomiajassa. Algoritmin väitetään toimivan kvanttitietokoneella ajassa, joka kasvaa polynomisesti ongelman koon mukana .
• Aiempi teoreettinen aukko saisi ratkaisun. Oded Regevin vuonna 2002 esittämä pelkistys yhdisti dihedraalisen aliryhmäongelman DCP:hen ja hilaprobleemeihin. Sen jälkeen keskeinen algoritminen askel on ollut avoinna noin kaksi vuosikymmentä .
• Menetelmä käyttää uutta teknistä ideaa. Simon korvaa aiemmissa lähestymistavoissa keskeisen oraakkelin niin sanotulla ”block-and-query”-tekniikalla, jonka tarkoitus on erottaa piilotettua aliryhmää koskeva tieto .
• Seuraukset voisivat ulottua hilaproblemeihin. Esijulkaisun mukaan algoritmi voitaisiin yhdistää Regevin pelkistykseen sekä Brakerskin, Kirshanovan, Stehlén ja Wenin parannuksiin. Tällöin voitaisiin saada polynomiajassa toimivia kvanttialgoritmeja muun muassa lyhimmän vektorin ongelman (SVP) likimääräiseen ratkaisemiseen ja Learning With Errors -ongelmaan (LWE) .

Työssä väitetään lisäksi, että algoritmi sietää virheellisiä näytteitä jopa suhteella 1/O(log n). Tämän pitäisi mahdollistaa algoritmin yhdistäminen aiempiin pelkistyksiin tehokkaasti .

Todentaminen on vasta alussa

Väite on merkittävä, mutta sen asema on toistaiseksi vain alustava. Luonnos on merkitty esijulkaisuksi, eikä sitä ole vertaisarvioitu tieteellisessä lehdessä tai konferenssissa .

Ensireaktiot kryptografian ja postkvanttitutkimuksen piirissä ovat olleet varovaisia ja paikoin erittäin epäileviä. Asiantuntija-arvioissa on nostettu esiin, että useat todistuksen kannalta ratkaisevat kohdat esitetään luonnoksina. Myös SVP:tä ja LWE:tä koskeva lopputulos nojautuu osittain julkaisemattomiin henkilökohtaisiin tiedonantoihin eikä kokonaisuudessaan julkisesti johdettuihin tuloksiin .

Elokuun 7.–8. päivän tilanteessa väitteelle ei ollut julkaistu riippumatonta vahvistusta eikä kumoavaa analyysiä . Vallitseva lähestymistapa on siksi yksinkertainen: ensin matematiikka tarkistetaan, vasta sitten arvioidaan seurauksia.

Tämä ero on tärkeä. Kyseessä ei ole valmis ohjelmisto, jolla olisi hyökätty käytössä olevaan salausjärjestelmään. Kyse on teoreettisesta väitteestä DCP:n ratkaisemisesta, ja juuri väitteen todistus on ensimmäinen asia, joka on saatava riippumattomaan tarkasteluun .

Mitä tämä merkitsee ML-KEMille ja ML-DSA:lle?

Lyhyt vastaus organisaatioille, jotka ottavat käyttöön tai arvioivat NISTin postkvanttisalausstandardeja, on: Simonin esijulkaisu ei tällä hetkellä anna aihetta muuttaa suunnitelmia .

• ML-KEMiin ei ole esitetty käytännön hyökkäystä. ML-KEM on FIPS 203 -standardin mukainen avainten kapselointimekanismi, joka perustuu Module-LWE-oletukseen. Esijulkaisu ei murra sitä eikä esitä hyökkäystä sen parametrisarjoihin .
• ML-DSA:ta ei ole murrettu. FIPS 204:n ML-DSA on hilapohjainen digitaalinen allekirjoitusmenetelmä, jonka taustalla ovat muun muassa Module-LWE- ja Module-SIS-oletukset. Simonin työ ei sisällä hyökkäystä ML-DSA:ta tai sen NIST-parametreja vastaan .
• Yhteys on toistaiseksi epäsuora. Vaikka DCP voidaan yhdistää yleisiin hilaprobleemeihin tunnetuilla pelkistyksillä, tästä ei vielä seuraa konkreettista hyökkäystä juuri niihin rakenteellisiin oletuksiin, joihin ML-KEM ja ML-DSA perustuvat .
• Huoli olisi ensisijaisesti rakenteellinen. Jos tulos vahvistetaan, se vahvistaisi käsitystä siitä, että kvanttitietokoneet voivat ratkaista joitakin hilaprobleemeja tehokkaasti. ”Hilaproblemit” on kuitenkin laaja luokka, kun taas NIST-standardit perustuvat tarkasti määriteltyihin ja rakenteellisiin ongelmaversioihin .

Aiempi tutkimus antaa väitteelle myös vertailukohdan. Vuonna 2025 Bai, Jangir, Kirshanova, Ngo ja Youmans esittivät kvasipolynomisen kvanttialgoritmin rajoitettuun DCP:n muunnelmaan, jossa modulus on kahden potenssi . Simonin väittämä täysi polynominen ratkaisu olisi tästä huomattava edistysaskel, mutta sitä ei ole vielä vahvistettu.

Miksi asiantuntijat suhtautuvat varauksella?

Ensireaktiot voidaan tiivistää kolmeen havaintoon:

1. Todistus on tarkastettava yksityiskohtaisesti. Keskeisten välivaiheiden luonnosmaisuus tekee mahdottomaksi arvioida väitteen kestävyyttä pelkän tiivistelmän perusteella .
2. Kryptografiset seuraukset ovat ehdollisia. DCP:n ratkaiseminen polynomiajassa ei yksin riitä osoittamaan, että ML-KEM tai ML-DSA voidaan murtaa. Johtopäätös riippuu siitä, miten tarkasti DCP:n ja kyseisten standardien käyttämien ongelmien välinen pelkistys toimii .
3. Virallisia kannanottoja ei vielä ole. NIST, tutkimuslaitokset ja standardointielimet eivät olleet julkaisseet asiasta merkittäviä virallisia lausuntoja, mikä on tuoreesta esijulkaisusta johtuen odotettavaa .

Kryptografian piirissä väitettä pidetään siis mahdollisesti tärkeänä, mutta ei vielä todistettuna käännekohtana. Raportoidut ensireaktiot ovat olleet ”raskaan skeptisiä”, koska todistuksessa on useita tarkastelua vaativia kohtia ja osa viittauksista on julkaisemattomia .

Johtopäätös: seuraa tutkimusta, mutta älä panikoi

Simonin esijulkaisu voi onnistuessaan muuttaa merkittävästi käsitystä joidenkin hilapohjaisten kryptografisten ongelmien kvanttikestävyydestä. Se täyttäisi teoreettisen aukon DCP:n ympärillä ja voisi avata uusia kysymyksiä postkvanttisalausmenetelmien perustasta.

Tällä hetkellä kyse on kuitenkin vahvistamattomasta esijulkaisusta, ei toimivasta hyökkäyksestä. ML-KEMin tai ML-DSA:n käyttöönottoa ei lähteiden perusteella ole syytä keskeyttää, parametrisarjoja vaihtaa tai postkvanttimigraation aikatauluja muuttaa tämän yksittäisen väitteen vuoksi . Seuraava ratkaiseva vaihe on riippumaton matemaattinen tarkastus.