Quantum Computers bi lahko z novim algoritmom razbili šifriranje prej, kot je bilo pričakovano

Ponovno objavil Platon

Spremljevalci: 0

Ena najbolj uveljavljenih in najbolj motečih uporab kvantnega računalnika prihodnosti je zmožnost vdiranja šifriranja. Nov algoritem bi lahko bistveno zmanjšal oviro za dosego tega.

Kljub vsemu hrupu okoli kvantnega računalništva so še vedno pomembna vprašanja za kaj bodo kvantni računalniki dejansko uporabni. Obstajajo upanja, da bi lahko pospešili vse, od procesov optimizacije do strojnega učenja, vendar v mnogih primerih ostaja nejasno, koliko lažji in hitrejši bodo.

Nekaj pa je precej gotovo: dovolj zmogljiv kvantni računalnik bi lahko naredil naše vodilne kriptografske sheme brez vrednosti. Medtem ko so matematične uganke, ki jih podpirajo, s klasičnimi računalniki praktično nerešljive, bi bile povsem sledljive za dovolj velik kvantni računalnik. To je težava, ker te sheme varujejo večino naših informacij na spletu.

Rešitev je bila v tem, da so današnji kvantni procesorji daleč od zahtevanega obsega. Toda po mnenju a poročati v ZnanostRačunalniški znanstvenik Oded Regev z Univerze v New Yorku je odkril nov algoritem, ki bi lahko znatno zmanjšal število potrebnih kubitov.

Pristop v bistvu predeluje enega najuspešnejših kvantnih algoritmov doslej. Leta 1994 je Peter Shor z MIT izumil način, kako ugotoviti, katera praštevila je treba pomnožiti, da dobimo določeno število – problem, znan kot faktoring praštevil.

Za velika števila je to neverjetno težaven problem, ki hitro postane nerešljiv na običajnih računalnikih, zato je bil uporabljen kot osnova za priljubljeno shemo šifriranja RSA. Toda z izkoriščanjem kvantnih pojavov, kot sta superpozicija in prepletenost, lahko Shorov algoritem reši te probleme tudi za neverjetno velika števila.

To dejstvo je povzročilo veliko panike med varnostnimi strokovnjaki, nenazadnje tudi zato, ker lahko hekerji in vohuni že danes prevzamejo šifrirane podatke in nato preprosto počakajo na razvoj dovolj zmogljivih kvantnih računalnikov, da jih razbijejo. In čeprav so bili razviti standardi postkvantnega šifriranja, bi lahko njihova implementacija po spletu trajala več let.

Verjetno pa bo čakanje precej dolgo. Večina izvedb RSA se zanaša na vsaj 2048-bitne ključe, kar je enako 617-mestnemu številu. Raziskovalci Fujitsu nedavno izračunano da bi kvantni računalnik, ki je popolnoma odporen na napake, z 10,000 kubiti potreboval 104 dni, da bi razbil tako veliko številko.

Vendar pa Regevov novi algoritem, opisan v a predtisk objavljen dne arXiv, bi lahko te zahteve znatno zmanjšal. Regev je v bistvu predelal Shorov algoritem tako, da je mogoče najti prafaktorje števila z veliko manj logičnimi koraki. Izvajanje operacij v kvantnem računalniku vključuje ustvarjanje majhnih vezij iz nekaj kubitov, znanih kot vrata, ki izvajajo preproste logične operacije.

V Shorovem izvirnem algoritmu je število vrat, potrebnih za faktorizacijo števila, kvadrat števila bitov, uporabljenih za njegovo predstavitev, kar je označeno kot n². Regevov pristop bi zahteval le n^1.5 vrata, ker išče prafaktorje z izvajanjem manjših množenj številnih števil namesto zelo velikih množenj posameznega števila. Prav tako zmanjša število potrebnih vrat z uporabo klasičnega algoritma za nadaljnjo obdelavo izhodov.

V prispevku Regev ocenjuje, da bi to za 2048-bitno število lahko zmanjšalo število potrebnih vrat za dva do tri velikosti. Če je res, bi to lahko omogočilo veliko manjšim kvantnim računalnikom, da razbijejo šifriranje RSA.

Vendar pa obstajajo praktične omejitve. Za začetek Regev ugotavlja, da Shorov algoritem koristi množico optimizacij, razvitih v preteklih letih, ki zmanjšujejo število kubitov, potrebnih za njegovo izvajanje. Ni še jasno, ali bi te optimizacije delovale pri novem pristopu.

Martin Ekerå, raziskovalec kvantnega računalništva pri švedski vladi, je prav tako povedal Znanost da se zdi, da Regevov algoritem potrebuje kvantni pomnilnik za shranjevanje vmesnih vrednosti. Zagotavljanje tega pomnilnika bo zahtevalo dodatne kubite in požrlo vse računske prednosti, ki jih ima.

Kljub temu je nova raziskava pravočasen opomin, da ko gre za grožnjo kvantnega računalništva šifriranju, vratnice se nenehno premikajo, in prehod na postkvantne sheme se ne more zgoditi dovolj hitro.

Kreditno slike: google