Kvanttitietokoneet voivat murtaa salauksen odotettua nopeammin uudella algoritmilla

Julkaissut Platon

seuraajia: 0

Yksi vakiintuneimmista ja häiritsevimmistä tulevaisuuden kvanttitietokoneiden käyttötavoista on kyky murtaa salaus. Uusi algoritmi voisi merkittävästi alentaa estettä tämän saavuttamiselle.

Huolimatta kaikesta kvanttilaskentaan liittyvästä hypetystä, ympärillä on edelleen merkittäviä kysymysmerkkejä mihin kvanttitietokoneista on oikeasti hyötyä. Toivotaan, että ne voisivat nopeuttaa kaikkea optimointiprosesseista koneoppimiseen, mutta kuinka paljon helpompaa ja nopeampaa ne ovat, on monissa tapauksissa epäselvää.

Yksi asia on kuitenkin melko varma: riittävän tehokas kvanttitietokone voi tehdä johtavista salausjärjestelmistämme arvottomia. Vaikka niiden taustalla olevat matemaattiset pulmat ovat käytännöllisesti katsoen ratkaisemattomia klassisilla tietokoneilla, ne olisivat täysin jäljitettävissä riittävän suurelle kvanttitietokoneelle. Se on ongelma, koska nämä järjestelmät suojaavat suurimman osan tiedoistamme verkossa.

Pelastus on ollut, että nykyiset kvanttiprosessorit ovat kaukana vaaditusta mittakaavasta. Mutta a:n mukaan raportoi tiede, New Yorkin yliopiston tietojenkäsittelytieteilijä Oded Regev on löytänyt uuden algoritmin, joka voi vähentää tarvittavien kubittien määrää huomattavasti.

Lähestymistapa uudistaa olennaisesti yhden tähän mennessä menestyneimmistä kvanttialgoritmeista. Vuonna 1994 MIT:n Peter Shor kehitti tavan selvittää, mitkä alkuluvut on kerrottava yhteen tietyn luvun saamiseksi – tämä ongelma tunnetaan alkulukulaskentana.

Suurille määrille tämä on uskomattoman vaikea ongelma, josta tulee nopeasti käsittämätöntä perinteisillä tietokoneilla, minkä vuoksi sitä käytettiin suositun RSA-salausjärjestelmän perustana. Mutta hyödyntämällä kvanttiilmiöitä, kuten superpositiota ja sotkeutumista, Shorin algoritmi voi ratkaista nämä ongelmat jopa uskomattoman suurille määrille.

Tämä tosiasia on johtanut pieneen paniikkiin tietoturva-asiantuntijoiden keskuudessa, varsinkin siksi, että hakkerit ja vakoilijat voivat nykyään kerätä salattuja tietoja ja sitten vain odottaa riittävän tehokkaiden kvanttitietokoneiden kehitystä murtaakseen sen. Ja vaikka kvanttisalauksen jälkeisiä standardeja on kehitetty, niiden käyttöönotto verkossa voi viedä useita vuosia.

Todennäköisesti odotusaika on kuitenkin melko pitkä. Useimmat RSA:n toteutukset perustuvat vähintään 2048-bittisiin avaimiin, mikä vastaa 617 numeron pituista lukua. Fujitsun tutkijat äskettäin laskettu että kestäisi täysin vikasietoinen kvanttitietokone, jossa on 10,000 104 kubittia, XNUMX päivää niin suuren luvun murtamiseen.

Kuitenkin Regevin uusi algoritmi, joka on kuvattu kohdassa a preprint julkaistu arXiv, voisi mahdollisesti vähentää näitä vaatimuksia huomattavasti. Regev on olennaisesti muokannut Shorin algoritmia siten, että on mahdollista löytää luvun alkutekijät käyttämällä paljon vähemmän loogisia vaiheita. Toimintojen suorittaminen kvanttitietokoneessa edellyttää pienten piirien luomista muutamista kubiteista, joita kutsutaan porteiksi ja jotka suorittavat yksinkertaisia loogisia operaatioita.

Shorin alkuperäisessä algoritmissa luvun laskemiseen tarvittava porttien määrä on sen esittämiseen käytettyjen bittien lukumäärän neliö, jota merkitään n². Regevin lähestymistapa vaatisi vain n^1.5 portit, koska se etsii alkutekijöitä suorittamalla useiden lukujen pienempiä kertolaskuja yhden luvun erittäin suurien kertolaskujen sijaan. Se myös vähentää tarvittavien porttien määrää käyttämällä klassista algoritmia lähtöjen jatkokäsittelyyn.

Paperissa Regev arvioi, että 2048-bittisellä numerolla tämä voisi vähentää tarvittavien porttien määrää kahdesta kolmeen suuruusluokkaa. Jos se on totta, paljon pienemmät kvanttitietokoneet voivat murtaa RSA-salauksen.

Käytännön rajoituksia on kuitenkin. Aluksi Regev huomauttaa, että Shorin algoritmi hyötyy lukuisista vuosien aikana kehitetyistä optimoinneista, jotka vähentävät sen suorittamiseen tarvittavien kubittien määrää. Vielä on epäselvää, toimisivatko nämä optimoinnit uudessa lähestymistavassa.

Myös Ruotsin hallituksen kvanttilaskentatutkija Martin Ekerå kertoi tiede että Regevin algoritmi näyttää tarvitsevan kvanttimuistia väliarvojen tallentamiseen. Muistin edellyttäminen vaatii ylimääräisiä kubitteja ja syö kaikki sen laskennalliset edut.

Siitä huolimatta uusi tutkimus on ajankohtainen muistutus siitä, että kun on kyse kvanttilaskennan uhkasta salaukselle, maalitolpat liikkuvat jatkuvasti, ja siirtyminen post-kvanttijärjestelmiin ei voi tapahtua tarpeeksi nopeasti.

Kuva pistetilanne: Google