Mikä on paras tapa ratkaista vaikeita ongelmia? Tämä on kysymys tietojenkäsittelytieteen ala-alan ytimessä, jota kutsutaan laskennallisen monimutkaisuuden teoriaksi. Siihen on vaikea vastata, mutta käännä se ympäri, niin se helpottuu. Huonoin lähestymistapa on lähes aina yritys ja erehdys, jolloin mahdollisten ratkaisujen kytkeminen onnistuu. Mutta joillekin ongelmille näyttää siltä, ​​että vaihtoehtoja ei yksinkertaisesti ole – huonoin lähestymistapa on myös paras.

Tutkijat ovat pitkään pohtineet, onko näin koskaan todella tapahtunut, sanoi Rahul Ilango, jatko-opiskelija, joka opiskelee monimutkaisuusteoriaa Massachusetts Institute of Technologyssa. "Voit kysyä: "Onko ongelmia, joihin arvaaminen ja tarkistaminen on optimaalista?""

Monimutkaisuusteoreetikot ovat tutkineet monia laskennallisia ongelmia, ja kovatkin myöntävät usein jonkinlaisen näppärän menettelyn tai algoritmin, joka tekee ratkaisun löytämisestä hieman helpompaa kuin pelkkä yritys ja erehdys. Harvoja poikkeuksia ovat ns. pakkausongelmat, joissa tavoitteena on löytää lyhin kuvaus tietojoukosta.

Mutta viime marraskuussa kaksi tutkijaryhmää itsenäisesti löysi toinen pakkausongelmien algoritmi – joka on aina niin vähän nopeampi kuin kaikkien mahdollisten vastausten tarkistaminen. Uusi lähestymistapa toimii mukauttamalla kryptografien 25 vuotta sitten keksimää algoritmia eri ongelman kimppuun. On vain yksi rajoitus: Sinun on räätälöitävä algoritmi tietojoukkosi koon mukaan.

"Ne ovat todella kauniita ja tärkeitä tuloksia", sanoi Eric Allender, teoreettinen tietojenkäsittelytieteilijä Rutgersin yliopistossa.

Kovuuden määrittely

Uudet tulokset ovat viimeisimmät, jotka tutkivat kysymystä, jota tutkittiin ensimmäisen kerran Neuvostoliitossa, paljon ennen monimutkaisuusteorian tuloa. "Ennen kuin olin peruskoulussa, ihmiset Venäjällä muotoilivat tätä", Allender sanoi.

Erityinen laskennallinen ongelma, jota nuo Neuvostoliiton tutkijat tutkivat, jota kutsutaan minimipiirin koon ongelmaksi, on samanlainen kuin tietokonelaitteiston suunnittelijat kohtaavat jatkuvasti. Jos saat täydelliset tiedot siitä, kuinka elektronisen piirin pitäisi käyttäytyä, voitko löytää yksinkertaisimman piirin, joka tekee työn? Kukaan ei osannut ratkaista tätä ongelmaa ilman "pereboria" - venäjän sanaa, joka vastaa karkeasti sanaa "tyhjentävä haku".

Pienin piirikoon ongelma on esimerkki pakkausongelmasta. Voit kuvata piirin käyttäytymistä pitkällä bittijonolla - 0s ja 1s - ja sitten kysyä, onko olemassa tapa toistaa sama käyttäytyminen käyttämällä vähemmän bittejä. Kaikkien mahdollisten piiriasettelujen tarkistaminen vie aikaa, joka kasvaa eksponentiaalisesti merkkijonon bittien määrän mukana.

Tällainen eksponentiaalinen kasvu on kovan laskentaongelman määrittelevä piirre. Mutta kaikki vaikeat ongelmat eivät ole yhtä vaikeita – joillakin on algoritmeja, jotka ovat nopeampia kuin tyhjentävä haku, vaikka niiden suoritusajat kasvavat silti eksponentiaalisesti. Nykyaikaisin termein perebor-kysymys on, onko olemassa sellaisia ​​​​algoritmeja pakkausongelmiin.

Vuonna 1959 tunnettu tutkija nimeltä Sergey Yablonsky väitti todistaneensa, että kattava haku todella oli ainoa tapa ratkaista piirin vähimmäiskokoongelma. Mutta hänen todisteensa jätti joitakin porsaanreikiä. Jotkut tutkijat huomasivat puutteet tuolloin, mutta Yablonsky oli tarpeeksi vaikutusvaltainen lannistamaan useimpia muita perebor-kysymyksen parissa.

Seuraavina vuosikymmeninä harvat tutkijat tutkivat pakkausongelmia, ja perebor-kysymys tunnettiin enimmäkseen alaviitteenä kompleksisuusteorian esihistoriassa. Kysymykseen kiinnitettiin laajaa huomiota vasta äskettäin, kun tutkijat löysivät uteliaan yhteyden pakkausongelmien ja kryptografian perusteiden välillä.

Yksisuuntainen liikenne

Nykyaikainen salaustekniikka käyttää kovia laskentaongelmia salaisten viestien suojaamiseen. Mutta laskennallinen kovuus on hyödyllinen vain, jos se on epäsymmetrinen - jos koodattujen viestien tulkitseminen on vaikeaa, mutta viestien koodaaminen ei ole vaikeaa.

Jokaisessa salausmenetelmässä tämän epäsymmetrian alkuperä on matemaattinen objekti, jota kutsutaan yksisuuntaiseksi funktioksi, joka muuntaa tulobittijonot samanpituisiksi lähtöjonoiksi. Kun yksisuuntaisen funktion syöte on annettu, on helppo laskea ulostulo, mutta lähdön perusteella funktiota on vaikea kääntää - toisin sanoen käännellä sitä ja palauttaa tulo.

"Kryptograafit haluaisivat todella, erittäin tehokkaasti laskettavia yksisuuntaisia ​​toimintoja, joita on todella, todella vaikea kääntää", Allender sanoi. Tämä ominaisuus näyttää olevan monilla matemaattisilla funktioilla, ja näiden funktioiden kääntämisen vaikeus johtuu ilmeisestä vaikeudesta ratkaista erilaisia ​​laskennallisia ongelmia.

Valitettavasti kryptografit eivät tiedä varmasti, onko jokin näistä funktioista todella vaikea kääntää – todellakin on mahdollista, että todellisia yksisuuntaisia ​​toimintoja ei ole olemassa. Tämä epävarmuus jatkuu, koska monimutkaisuusteoreetikot ovat kamppailivat 50 vuotta todistaa, että vaikeilta näyttävät ongelmat ovat todella vaikeita. Jos ne eivät ole, ja jos tutkijat löytävät supernopeita algoritmeja näihin ongelmiin, se olisi tuhoisaa salauksen kannalta – samanlaista kuin ylinopeusautojen äkillinen reititys molempiin suuntiin yksisuuntaisella kadulla.

Vaikka kattava ymmärrys laskennallisesta kovuudesta on edelleen vaikeaselkoinen, kryptografit ovat viime aikoina edistyneet jännittävästi kohti yhtenäistä teoriaa yksisuuntaisista funktioista. Yksi iso askel otettiin vuonna 2020, kun Tel Avivin yliopiston kryptografi Rafael Pass ja hänen jatko-opiskelijansa Yanyi Liu osoittanut, että yksisuuntaiset funktiot ovat läheisesti yhteydessä tiettyyn pakkaustehtävään, jota kutsutaan aikarajaiseksi Kolmogorovin kompleksisuusongelmaksi.

Jos tämä yksi ongelma on todella vaikea ratkaista useimmille syötteille, niin Passin ja Liun tulos antaa reseptin todistettavasti vaikean yksisuuntaisen funktion rakentamiseen – funktion, joka on taatusti turvallinen, vaikka muut laskentaongelmat osoittautuvatkin paljon helpoiksi. kuin tutkijat odottivat. Mutta jos on olemassa nopea algoritmi aikarajallisen Kolmogorovin kompleksisuusongelman ratkaisemiseksi, niin kryptografia on tuhoon tuomittu ja mikä tahansa funktio voidaan helposti kääntää. Yksisuuntainen funktio, joka perustuu tämän ongelman kovuuteen, on turvallisin mahdollinen toiminto – yksisuuntainen funktio hallitsemaan niitä kaikkia.

Tietorakenteiden pohjalta

Passin ja Liun löytö oli viimeisin luku pitkässä tutkimuksessa, joka käyttää kompleksisuusteoriaa ymmärtääkseen paremmin kryptografian perusteita. Mutta se ehdotti myös tapaa kääntää tämä suhde: Aikarajaisen Kolmogorovin kompleksisuusongelman ja funktion inversion välinen ekvivalenssi tarkoittaa, että oivallukset jommastakummasta ongelmasta voivat paljastaa enemmän toisesta. Kryptografit ovat tutkineet funktion inversioalgoritmeja vuosikymmeniä ymmärtääkseen paremmin salausmenetelmiensä heikkoja kohtia. Tutkijat alkoivat miettiä, voisivatko nämä algoritmit auttaa vastaamaan ikivanhoihin kysymyksiin monimutkaisuusteoriassa.

Kuten monet laskennalliset ongelmat, funktion inversio voidaan ratkaista kattavalla haulla. Kun annat lähtöjonon, kytke kaikki mahdolliset syötteet funktioon, kunnes löydät oikean vastauksen.

Vuonna 1980 kryptografi Martin Hellman alkoi tutkia, olisiko mahdollista tehdä parempaa – sama kysymys, jonka Neuvostoliiton matemaatikot olivat kysyneet pakkausongelmista vuosikymmeniä aiemmin. Hellman löysi että kyllä, se on mahdollista – kunhan olet valmis tekemään ylimääräistä työtä etukäteen käyttämällä matemaattisia objekteja, joita kutsutaan tietorakenteiksi.

Tietorakenne on pohjimmiltaan taulukko, joka tallentaa tietoja käännettävästä funktiosta, ja sellaisen rakentaminen edellyttää funktion tulosten laskemista tietyille strategisesti valituille tuloille. Kaikki nämä laskelmat "voivat kestää hyvin kauan", sanoi Ryan Williams, monimutkaisuusteoreetikko MIT:ssä. "Mutta ajatuksena on, että tämä tehdään kerran ja lopullisesti." Jos yrität kääntää saman funktion useilla eri lähtöillä - esimerkiksi purkaa useita samalla tavalla salattuja viestejä - tämän työn tekeminen etukäteen saattaa olla kannattavaa.

Tietenkin lisätietojen tallentaminen vaatii tilaa, joten ota tämä strategia äärimmäisyyksiin, ja saatat päätyä nopeaan ohjelmaan, joka ei mahdu mihinkään tietokoneeseen. Hellman suunnitteli älykkään tietorakenteen, jonka avulla hänen algoritminsa pystyi kääntämään useimmat toiminnot hieman nopeammin kuin kattava haku viemättä liikaa tilaa. Sitten vuonna 2000 kryptografit Amos Fiat ja Moni Naor laajennettu Hellmanin argumentit kaikille funktioille.

Passin ja Liun läpimurron jälkeen vuonna 2020 nämä vanhat tulokset olivat yhtäkkiä uusia merkityksellisiä. Fiat-Naor-algoritmi voisi kääntää mielivaltaiset funktiot nopeammin kuin kattava haku. Voisiko se toimia myös pakkausongelmiin?

Ei yhtenäistä

Ensimmäiset tutkijat, jotka esittivät kysymyksen, olivat kompleksisuusteoreetikko Rahul Santanam Oxfordin yliopistosta ja hänen jatko-opiskelijansa Hanlin Ren. He tekivät niin a 2021 paperi osoittaa, että pakkausongelmat ja funktion inversio kietoutuivat vielä enemmän kuin tutkijat olivat ymmärtäneet.

Pass ja Liu olivat osoittaneet, että jos aikarajallinen Kolmogorovin kompleksisuusongelma on kova, niin myös funktion inversion täytyy olla kovaa ja päinvastoin. Mutta ongelmat voivat olla vaikeita ja silti hyväksyä ratkaisuja, jotka ovat hieman parempia kuin tyhjentävä haku. Santhanam ja Ren osoittivat, että on olemassa läheinen yhteys sen välillä, tarvitaanko perusteellista etsintää yhteen ongelmaan ja tarvitaanko sitä toiseen.

Heidän tuloksilla oli erilainen vaikutus kahteen laajaan algoritmiluokkaan, joita tutkijat usein tutkivat ja joita kutsutaan "yhtenäisiksi" ja "epäyhtenäisiksi" algoritmeiksi. Yhtenäiset algoritmit noudattavat samaa menettelyä jokaiselle syötteelle – yhtenäinen ohjelma esimerkiksi numeroluetteloiden lajitteluun toimii samalla tavalla riippumatta siitä, onko luettelossa 20 merkintää vai 20,000 XNUMX. Epäyhtenäiset algoritmit käyttävät sen sijaan erilaisia ​​proseduureja eripituisille syötteille.

Fiat-Naor-algoritmin käyttämät tietorakenteet on aina räätälöity tietyn toiminnon mukaan. 10-bittistä merkkijonoa sekoittavan funktion invertoimiseksi tarvitset tietorakenteen, joka eroaa 20-bittistä merkkijonoa sekoittavan funktion invertoimiseksi, vaikka sekoitus tapahtuisi samalla tavalla. Tämä tekee Fiat-Naorista epäyhtenäisen algoritmin.

Santhanamin ja Renin tulos ehdotti, että Fiat-Naor-algoritmi voisi olla mahdollista muuntaa algoritmiksi pakkausongelmien ratkaisemiseksi. Mutta algoritmin mukauttaminen ongelmasta toiseen ei ollut yksinkertaista, eivätkä he jatkaneet kysymystä.

Pass törmäsi samaan ideaan vuotta myöhemmin kuultuaan Fiatin puhuvan klassisesta algoritmista työpajassa, jossa juhlittiin Naorin panosta kryptografiaan. "Tämä ajatus funktion inversion käytöstä on ollut mielessäni siitä lähtien", hän sanoi. Myöhemmin hän alkoi työskennellä ongelman parissa tosissaan Tel Avivin yliopiston tutkijan kanssa Noam Mazor.

Sillä välin Ilango innostui hyökkäämään ongelmaan keskusteltuaan muiden tutkijoiden, mukaan lukien Santhanamin, kanssa vieraillessaan Simons Institute for the Theory of Computingissa Berkeleyssä, Kaliforniassa. "Se tuli yhdestä näistä erittäin seesteisistä keskusteluista, joissa vain heittelet asioita", Santhanam sanoi. Myöhemmin Ilango yhdisti voimansa Williamsin ja Shuichi Hirahara, monimutkaisuusteoreetikko Tokion National Institute of Informaticsissa.

Vaikeinta oli selvittää, kuinka Fiat-Naor-algoritmin ytimessä oleva tietorakenne upotetaan epäyhtenäiseen algoritmiin pakkausongelmien ratkaisemiseksi. Tällaiseen upotukseen on olemassa vakiomenettely, mutta se hidastaisi algoritmia ja pyyhkiisi pois sen edun kattavaan hakuun verrattuna. Molemmat tiimit löysivät älykkäämpiä tapoja sisällyttää Fiat-Naor-tietorakenne ja saivat pakkausongelmiin algoritmeja, jotka toimivat kaikissa tuloissa ja pysyivät nopeampia kuin tyhjentävä haku.

Näiden kahden algoritmin yksityiskohdat eroavat hieman. Ilangon ja hänen yhteistyökumppaniensa tekemä on tyhjentävää hakua nopeampi, vaikka haku rajattaisiinkin yksinkertaisimpiin mahdollisuuksiin, ja se pätee kaikkiin pakkausongelmiin - aikarajaiseen Kolmogorov-kompleksisuuteen, minimipiirikoon ongelmaan ja moniin muihin. Mutta ydinajatus oli sama molemmissa algoritmeissa. Salaustekniikat olivat osoittaneet arvonsa tällä uudella alalla.

Käänteinen konvergenssi

Uusi todiste epäyhtenäisille algoritmeille herättää luonnollisen kysymyksen: entä yhtenäiset algoritmit? Onko olemassa tapaa ratkaista pakkausongelmat nopeammin kuin tyhjentävä haku niiden avulla?

Viimeaikaiset tulossarjat viittaavat siihen, että mikä tahansa tällainen algoritmi vastaisi yhtenäistä algoritmia mielivaltaisten funktioiden invertoimiseksi - mitä kryptografit ovat etsineet tuloksetta vuosikymmeniä. Tästä syystä monet tutkijat pitävät mahdollisuutta epätodennäköisenä.

"Olisin hyvin yllättynyt", Santhanam sanoi. "Se vaatisi täysin uuden idean."

Mutta Allender sanoi, että tutkijoiden ei pitäisi jättää huomiotta tätä mahdollisuutta. "Hyvä työhypoteesi minulle on ollut, että jos on olemassa epäyhtenäinen tapa tehdä jotain, hyvin todennäköisesti on olemassa yhtenäinen tapa", hän sanoi.

Joka tapauksessa työ on saanut kompleksisuusteoreetikot äskettäin kiinnostumaan salauksen vanhoista kysymyksistä. Yuval Ishai, kryptografi Technionissa Haifassa, Israelissa, sanoi, että se tekee siitä jännittävimmän.

"Olen todella iloinen nähdessäni tämän kiinnostuksen lähentymisen eri yhteisöjen välillä", hän sanoi. "Mielestäni se on hienoa tieteelle."