Tähistatud krüptograafiaalgoritmi uuendatakse | Ajakiri Quanta

Meie üha digitaalsemaks muutuvas elus sõltub turvalisus krüptograafiast. Saatke privaatsõnum või tasuge arve veebis ja te toetute algoritmidele, mis on loodud teie andmete salajas hoidmiseks. Loomulikult soovivad mõned inimesed neid saladusi paljastada – nii et teadlased püüavad testida nende süsteemide tugevust, veendumaks, et need ei laguneks nutika ründaja käe läbi.

Üks oluline tööriist selles töös on LLL-algoritm, mis sai nime teadlaste järgi, kes avaldas selle 1982. aastal — Arjen Lenstra, Hendrik Lenstra juunior ja László Lovász. LLL koos oma paljude järeltulijatega võib mõnel juhul krüptograafilisi skeeme rikkuda; nende käitumise uurimine aitab teadlastel kavandada süsteeme, mis on rünnakute suhtes vähem haavatavad. Algoritmi anded ulatuvad krüptograafiast kaugemale: see on kasulik tööriist ka arenenud matemaatika areenidel, nagu arvutusteooria.

Aastate jooksul on teadlased lihvinud LLL variante, et muuta lähenemine praktilisemaks – kuid ainult teatud piirini. Nüüd on paar krüptograafi loonud uue LLL-stiilis algoritmi, mis suurendab oluliselt tõhusust. Uus tehnika, mis võitis Parima paberi auhind kell 2023. aasta rahvusvaheline krüptoloogiakonverents, laiendab stsenaariumide valikut, mille puhul arvutiteadlased ja matemaatikud saavad kasutada elukestva õppega sarnaseid lähenemisviise.

"See oli tõesti põnev," ütles Chris Peikert, Michigani ülikooli krüptograaf, kes ei olnud selle artikliga seotud. Ta ütles, et tööriist on aastakümneid olnud uurimistöö keskmes. "Alati on tore, kui sihtmärk, mille kallal on nii kaua tööd tehtud... näitab, et üllatusi on veel oodata."

LLL-tüüpi algoritmid töötavad võremaailmas: korrapäraste vahedega punktide lõpmatud kogumid. Ühe võimalusena selle visualiseerimiseks kujutage ette, et plaatite põrandat. Võite selle katta ruudukujuliste plaatidega ja nende plaatide nurgad moodustaksid ühe võre. Teise võimalusena võite valida erineva plaadi kuju – näiteks pika rööpküliku –, et luua erinev võre.

Võret saab kirjeldada selle "aluse" abil. See on vektorite komplekt (põhimõtteliselt arvude loendid), mida saate võre iga punkti saamiseks erinevatel viisidel kombineerida. Kujutame ette võre, mille alus koosneb kahest vektorist: [3, 2] ja [1, 4]. Võre on vaid kõik punktid, milleni saate nende vektorite koopiaid liites ja lahutades.

See vektoripaar ei ole võre ainus alus. Igal vähemalt kahemõõtmelisel võrel on lõpmatult palju võimalikke aluseid. Kuid mitte kõik alused pole võrdsed. Alust, mille vektorid on lühemad ja üksteisega täisnurgale lähemal, on tavaliselt lihtsam töötada ja see on mõne arvutusprobleemi lahendamiseks kasulikum, mistõttu teadlased nimetavad neid aluseid "headeks". Selle näiteks on sinise vektori paar alloleval joonisel. Pikematest ja vähem ortogonaalsetest vektoritest koosnevaid aluseid, nagu punaseid vektoreid, võib pidada "halbadeks".

See on LLL-i töö: andke sellele (või tema vendadele) mitmemõõtmelise võre alus ja see sülitab välja parema. Seda protsessi nimetatakse võre baasi vähendamiseks.

Mis on sellel kõigel krüptograafiaga pistmist? Selgub, et krüptosüsteemi purustamise ülesande saab mõnel juhul ümber sõnastada teise probleemina: suhteliselt lühikese vektori leidmine võrest. Ja mõnikord saab selle vektori välja võtta LLL-stiilis algoritmi genereeritud vähendatud baasist. See strateegia on aidanud teadlastel ümber lükata süsteeme, mis pealtnäha näivad võredega vähe pistmist.

Teoreetilises mõttes töötab algne LLL-algoritm kiiresti: käitamiseks kuluv aeg ei skaleeru eksponentsiaalselt sisendi suurusega, st võre mõõtmega ja numbrite suurusega (bittides) baasvektorid. Kuid see suureneb polünoomfunktsioonina ja "kui soovite seda tegelikult teha, pole polünoomaeg alati nii teostatav," ütles ta. Léo Ducas, krüptograaf Hollandi riiklikus uurimisinstituudis CWI.

Praktikas tähendab see, et algne LLL-algoritm ei saa hakkama liiga suurte sisenditega. "Matemaatikud ja krüptograafid soovisid, et nad saaksid teha rohkem, " ütles Keegan Ryan, San Diego California ülikooli doktorant. Teadlased töötasid LLL-stiilis algoritmide optimeerimise nimel, et mahutada suuremaid sisendeid, saavutades sageli hea jõudluse. Siiski on mõned ülesanded jäänud visalt kättesaamatuks.

Uus artikkel, mille autoriks on Ryan ja tema nõunik, Nadia Heninger, ühendab mitu strateegiat, et parandada oma LLL-stiilis algoritmi tõhusust. Esiteks kasutab tehnika rekursiivset struktuuri, mis jagab ülesande väiksemateks tükkideks. Teiseks haldab algoritm hoolikalt kaasatud numbrite täpsust, leides tasakaalu kiiruse ja õige tulemuse vahel. Uus töö võimaldab teadlastel vähendada tuhandete mõõtmetega võre aluseid.

Varasemad tööd on järginud sarnast lähenemisviisi: A 2021 paber ühendab ka rekursiooni ja täppishalduse, et teha kiiret tööd suurte võredega, kuid see töötas ainult teatud tüüpi võre puhul, mitte kõigi krüptograafias oluliste võretega. Uus algoritm käitub hästi palju laiemas vahemikus. "Mul on tõesti hea meel, et keegi seda tegi," ütles Thomas Espitau, krüptograafiauurija ettevõttes PQShield ja 2021. aasta versiooni autor. Tema meeskonna töö pakkus "kontseptsiooni tõestust," ütles ta; uus tulemus näitab, et "saate teha väga kiiret võre vähendamise heli."

Uus tehnika on juba hakanud kasulikuks osutuma. Aurel Page, Prantsuse riikliku uurimisinstituudi Inria matemaatik, ütles, et tema ja ta meeskond on rakendanud algoritmi kohandamist, et töötada mõne arvutusteooria ülesandega.

LLL-stiilis algoritmid võivad mängida rolli ka võrepõhiste krüptograafiasüsteemidega seotud uuringutes, mis on loodud turvaliselt püsima isegi tulevikus võimsate kvantarvutitega. Need ei kujuta sellistele süsteemidele ohtu, kuna nende mahavõtmine nõuab lühemate vektorite leidmist, kui need algoritmid suudavad saavutada. Kuid parimad rünnakud, mida teadlased teavad, kasutavad LLL-stiilis algoritmi "põhilise ehitusplokina". Wessel van Woerden, krüptograaf Bordeaux' ülikoolis. Praktilistes katsetes nende rünnakute uurimiseks võib see ehitusplokk kõike aeglustada. Uut tööriista kasutades võivad teadlased laiendada katsete valikut, mida nad saavad ründealgoritmidega teha, pakkudes selgemat pilti nende toimimisest.

Quanta viib läbi mitmeid küsitlusi, et meie vaatajaskonda paremini teenindada. Võtke meie informaatika lugejaküsitlus ja teid osaletakse tasuta võitmiseks Quanta kaubad.