Juhlittu salausalgoritmi saa päivityksen | Quanta-lehti

Yhä digitaalisemmassa elämässämme turvallisuus riippuu salauksesta. Lähetä yksityisviesti tai maksa lasku verkossa, ja luotat algoritmeihin, jotka on suunniteltu pitämään tietosi salassa. Tietysti jotkut ihmiset haluavat paljastaa nämä salaisuudet – joten tutkijat testaavat näiden järjestelmien vahvuutta varmistaakseen, etteivät ne murene fiksun hyökkääjän käsissä.

Yksi tärkeä työkalu tässä työssä on LLL-algoritmi, joka on nimetty tutkijoiden mukaan julkaissut sen vuonna 1982 – Arjen Lenstra, Hendrik Lenstra Jr. ja László Lovász. LLL ja sen monet jälkeläiset voivat rikkoa salausjärjestelmiä joissakin tapauksissa; niiden käyttäytymisen tutkiminen auttaa tutkijoita suunnittelemaan järjestelmiä, jotka ovat vähemmän alttiita hyökkäyksille. Ja algoritmin kyvyt ulottuvat salakirjoituksen ulkopuolelle: se on myös hyödyllinen työkalu edistyneillä matemaattisilla areenoilla, kuten laskennallinen lukuteoria.

Vuosien mittaan tutkijat ovat hioneet LLL-muunnelmia tehdäkseen lähestymistavasta käytännöllisemmän - mutta vain tiettyyn pisteeseen asti. Nyt salakirjoittajapari on rakentanut uuden LLL-tyylisen algoritmin, joka parantaa merkittävästi tehokkuutta. Uusi tekniikka, joka voitti Paras paperi -palkinto klo 2023 kansainvälinen kryptologiakonferenssi, laajentaa skenaarioiden kirjoa, joissa tietojenkäsittelytieteilijät ja matemaatikot voivat käyttää LLL:n kaltaisia ​​lähestymistapoja.

"Se oli todella jännittävää", sanoi Chris Peikert, kryptografi Michiganin yliopistosta, joka ei ollut mukana artikkelissa. Työkalu on ollut tutkimuksen kohteena vuosikymmeniä, hän sanoi. "On aina mukavaa, kun kohde, jonka eteen on työstetty niin pitkään... osoittaa, että yllätyksiä löytyy vielä."

LLL-tyyppiset algoritmit toimivat hilamaailmassa: äärettömät kokoelmat säännöllisin väliajoin olevia pisteitä. Yksi tapa visualisoida tämä kuvittele, että laatoit lattiaa. Voit peittää sen neliömäisillä laatoilla, ja näiden laattojen kulmat muodostaisivat yhden ristikon. Vaihtoehtoisesti voit valita erilaisen laatan muodon – esimerkiksi pitkän suunnikkaan – luodaksesi erilaisen hilan.

Hila voidaan kuvata käyttämällä sen "perustaa". Tämä on joukko vektoreita (lähinnä lukuluetteloita), joita voit yhdistää eri tavoilla saadaksesi jokaisen pisteen hilassa. Kuvitellaan hila, jonka kanta koostuu kahdesta vektorista: [3, 2] ja [1, 4]. Hila on vain kaikki pisteet, jotka voit saavuttaa lisäämällä ja vähentämällä näiden vektoreiden kopioita.

Tämä vektoripari ei ole hilan ainoa perusta. Jokaisella vähintään kaksiulotteisella hilalla on äärettömän monta mahdollista kantaa. Mutta kaikkia perusteita ei luoda tasa-arvoisiksi. Perusta, jonka vektorit ovat lyhyempiä ja lähempänä suoria kulmia keskenään, on yleensä helpompi työstää ja se on hyödyllisempi joidenkin laskennallisten ongelmien ratkaisemisessa, joten tutkijat kutsuvat niitä "hyviksi". Esimerkki tästä on sinisen vektorin pari alla olevassa kuvassa. Pidemmistä ja vähemmän ortogonaalisista vektoreista koostuvia emäksiä - kuten punaisia ​​vektoreita - voidaan pitää "pahoina".

Tämä on työtä LLL:lle: Anna sille (tai sen veljille) moniulotteisen hilan perusta, niin se sylkee paremman. Tämä prosessi tunnetaan hilapohjan vähentämisenä.

Mitä tekemistä tällä kaikella on kryptografian kanssa? Osoittautuu, että salausjärjestelmän rikkominen voidaan joissain tapauksissa muotoilla uudelleen toisena ongelmana: suhteellisen lyhyen vektorin löytäminen hilassa. Ja joskus tämä vektori voidaan poimia LLL-tyylisen algoritmin luomasta pelkistetystä perustasta. Tämä strategia on auttanut tutkijoita kaatamaan järjestelmiä, joilla pinnalla ei näytä olevan juurikaan tekemistä hilan kanssa.

Teoreettisessa mielessä alkuperäinen LLL-algoritmi toimii nopeasti: suorittamiseen kuluva aika ei skaalaudu eksponentiaalisesti syötteen koon mukaan – eli hilan mittasuhteen ja lukujen koon (bitteinä) mukaan. kantavektorit. Mutta se kasvaa polynomifunktiona, ja "jos todella haluat tehdä sen, polynomiaika ei aina ole niin mahdollista", sanoi Léo Ducas, kryptografi kansallisessa tutkimuslaitoksessa CWI Alankomaissa.

Käytännössä tämä tarkoittaa, että alkuperäinen LLL-algoritmi ei pysty käsittelemään liian suuria syötteitä. "Matemaatikot ja kryptografit halusivat kykyä tehdä enemmän", sanoi Keegan Ryan, tohtoriopiskelija Kalifornian yliopistossa San Diegossa. Tutkijat työskentelivät optimoidakseen LLL-tyylisiä algoritmeja isompien syötteiden mukauttamiseksi, mikä usein saavutti hyvän suorituskyvyn. Jotkut tehtävät ovat kuitenkin jääneet sinnikkäästi ulottumattomiin.

Uusi paperi, jonka kirjoittavat Ryan ja hänen neuvonantajansa, Nadia Heninger, yhdistää useita strategioita parantaakseen LLL-tyylisen algoritminsa tehokkuutta. Ensinnäkin tekniikka käyttää rekursiivista rakennetta, joka jakaa tehtävän pienempiin osiin. Toisaalta algoritmi hallitsee huolellisesti mukana olevien numeroiden tarkkuutta ja löytää tasapainon nopeuden ja oikean tuloksen välillä. Uuden työn ansiosta tutkijoiden on mahdollista pienentää tuhansien mittojen hilapohjat.

Aikaisempi työ on noudattanut samanlaista lähestymistapaa: A 2021 paperi yhdistää myös rekursion ja tarkkuuden hallinnan suuren hilan nopeaan työskentelyyn, mutta se toimi vain tietyntyyppisille hiloille, ei kaikille, jotka ovat tärkeitä kryptografiassa. Uusi algoritmi toimii hyvin paljon laajemmalla alueella. "Olen todella iloinen, että joku teki sen", sanoi Thomas Espitau, kryptografiatutkija PQShield-yrityksessä ja vuoden 2021 version kirjoittaja. Hänen tiiminsä työ tarjosi "konseptin todisteen", hän sanoi; uusi tulos osoittaa, että "voit tehdä erittäin nopean hilavähennyksen järkevällä tavalla."

Uusi tekniikka on jo alkanut osoittautua hyödylliseksi. Aurel Page, ranskalaisen kansallisen tutkimuslaitoksen Inria matemaatikko, sanoi, että hän ja hänen tiiminsä ovat saaneet algoritmin mukautuksen toimimaan joissakin laskennallisissa lukuteoriatehtävissä.

LLL-tyylisillä algoritmeilla voi olla rooli myös tutkimuksessa, joka liittyy hilapohjaisiin salausjärjestelmiin, jotka on suunniteltu pysyä turvassa jopa tulevaisuudessa tehokkaiden kvanttitietokoneiden kanssa. Ne eivät ole uhka tällaisille järjestelmille, koska niiden poistaminen vaatii lyhyempien vektorien löytämistä kuin näillä algoritmeilla voidaan saavuttaa. Mutta parhaat hyökkäykset, jotka tutkijat tietävät, käyttävät LLL-tyylistä algoritmia "perusrakennuspalikkana", sanoi. Wessel van Woerden, kryptografi Bordeaux'n yliopistosta. Käytännön kokeissa näiden hyökkäysten tutkimiseksi tämä rakennuspalikka voi hidastaa kaikkea. Uuden työkalun avulla tutkijat voivat laajentaa kokeilujen valikoimaa, joita he voivat suorittaa hyökkäysalgoritmeilla, mikä tarjoaa selkeämmän kuvan niiden suorituskyvystä.

Quanta tekee sarjan kyselyjä palvellakseen paremmin yleisöämme. Ota meidän tietojenkäsittelytieteen lukijakysely ja pääset mukaan voittamaan ilmaiseksi Quanta kauppatavaraa.