Krüptograafianipid muudavad raske probleemi pisut lihtsamaks | Quanta ajakiri

Milline on parim viis raskete probleemide lahendamiseks? See on arvutiteaduse alamvaldkonna, mida nimetatakse arvutusliku keerukuse teooriaks, keskmes. Sellele küsimusele on raske vastata, kuid pöörake see ümber ja see muutub lihtsamaks. Halvim lähenemisviis on peaaegu alati katse-eksitus, mis hõlmab võimalike lahenduste ühendamist, kuni need töötavad. Kuid mõne probleemi puhul tundub, et alternatiive lihtsalt pole – halvim lähenemine on ka parim.

Teadlased on pikka aega mõelnud, kas see on tõesti nii, ütles Rahul Ilango, Massachusettsi Tehnoloogiainstituudis keerukuse teooriat õppiv magistrant. "Võite küsida: "Kas on probleeme, mille puhul arvamine ja kontrollimine on lihtsalt optimaalne?""

Keerukuse teoreetikud on uurinud paljusid arvutusprobleeme ja isegi raskemad tunnistavad sageli mingit nutikat protseduuri või algoritmi, mis muudab lahenduse leidmise pisut lihtsamaks kui puhas katse-eksitus. Väheste erandite hulka kuuluvad nn tihendusprobleemid, mille puhul on eesmärgiks leida andmestiku lühim kirjeldus.

Kuid mullu novembris kaks teadlaste rühma iseseisvalt avastasin teine ​​pakkimisprobleemide algoritm – selline, mis on kunagi nii veidi kiirem kui kõigi võimalike vastuste kontrollimine. Uus lähenemisviis toimib, kohandades krüptograafide poolt 25 aastat tagasi leiutatud algoritmi teistsuguse probleemi ründamiseks. On ainult üks piirang: peate algoritmi kohandama vastavalt oma andmekogumi suurusele.

"Need on tõesti ilusad ja olulised tulemused," ütles Eric Allender, Rutgersi ülikooli teoreetiline arvutiteadlane.

Kõvaduse määratlemine

Uued tulemused on viimased, mis uurivad küsimust, mida esmakordselt uuriti Nõukogude Liidus, palju enne keerukuse teooria tulekut. "Enne kui ma põhikoolis käisin, sõnastasid inimesed Venemaal seda," ütles Allender.

Konkreetne arvutusprobleem, mida need Nõukogude teadlased uurisid, mida nimetatakse minimaalse vooluringi suuruse probleemiks, on sarnane probleemiga, millega arvutiriistvara disainerid kogu aeg silmitsi seisavad. Kui teile antakse täielikud spetsifikatsioonid selle kohta, kuidas elektrooniline lülitus peaks käituma, kas leiate kõige lihtsama vooluahela, mis selle töö ära teeb? Keegi ei teadnud, kuidas seda probleemi lahendada ilma "pereborita" - venekeelse sõnaga, mis on ligikaudu samaväärne sõnaga "ammendav otsing".

Minimaalse vooluringi suuruse probleem on näide tihendusprobleemist. Saate kirjeldada vooluringi käitumist pika bittide jadaga - 0-d ja 1-d - ning seejärel küsida, kas on võimalik sama käitumist vähemate bittide abil reprodutseerida. Kõigi võimalike vooluahela paigutuste kontrollimine võtaks aega, mis kasvab eksponentsiaalselt koos bittide arvuga stringis.

Seda tüüpi eksponentsiaalne kasv on raske arvutusprobleemi määrav tunnusjoon. Kuid mitte kõik rasked probleemid pole võrdselt rasked – mõnel on algoritmid, mis on kiiremad kui ammendav otsing, ehkki nende käitusaeg kasvab plahvatuslikult. Tänapäeva mõistes on perebori küsimus selles, kas pakkimisprobleemide jaoks on selliseid algoritme olemas.

Aastal 1959 väitis silmapaistev teadlane Sergei Yablonsky, et on tõestanud, et põhjalik otsing on tõesti ainus viis vooluringi minimaalse suuruse probleemi lahendamiseks. Kuid tema tõend jättis mõned lüngad. Mõned teadlased märkasid toona vigu, kuid Yablonsky oli piisavalt mõjukas, et heidutada enamikku teisi perebori küsimusega tegelemast.

Järgnevatel aastakümnetel uurisid tihendusprobleeme vähesed teadlased ja perebori küsimust tunti peamiselt keerukuse teooria eelajaloo joonealuse märkena. Laialdane tähelepanu sellele küsimusele tõusis alles hiljuti, pärast seda, kui teadlased avastasid uudishimuliku seose tihendusprobleemide ja krüptograafia aluste vahel.

Ühesuunaline liiklus

Kaasaegne krüptograafia kasutab salajaste sõnumite kaitsmiseks raskeid arvutusprobleeme. Kuid arvutuslik kõvadus on kasulik ainult siis, kui see on asümmeetriline - kui kodeeritud sõnumeid on raske dešifreerida, kuid sõnumeid pole raske kodeerida.

Igas krüptograafiaskeemis on selle asümmeetria alguseks matemaatiline objekt, mida nimetatakse ühesuunaliseks funktsiooniks, mis teisendab sisendbittide stringid sama pikkusega väljundstringideks. Ühesuunalise funktsiooni sisendi korral on väljundit lihtne arvutada, kuid väljundit arvestades on funktsiooni raske ümber pöörata – see tähendab seda pöördprojekteerida ja sisendit taastada.

"Krüptograafid tahaksid väga, väga tõhusalt arvutatavaid ühesuunalisi funktsioone, mida on tõesti väga raske ümber pöörata," ütles Allender. See omadus näib olevat paljudel matemaatilistel funktsioonidel ja nende funktsioonide ümberpööramise raskus tuleneb erinevate arvutusprobleemide lahendamise näilisest raskusest.

Kahjuks ei tea krüptograafid kindlalt, kas mõnda neist funktsioonidest on tõesti raske ümber pöörata – tõepoolest on võimalik, et tõelisi ühesuunalisi funktsioone polegi olemas. See ebakindlus püsib, sest keerukuse teoreetikud on seda teinud võitles 50 aastat tõestamaks, et näiliselt rasked probleemid on tõesti rasked. Kui nad seda ei tee ja kui teadlased avastavad nende probleemide lahendamiseks ülikiired algoritmid, oleks see krüptograafia jaoks hukatuslik – sarnane kiirusületavate autode ootamatule suunamisele mõlemas suunas ühesuunalisel tänaval.

Ehkki arvutusliku kõvaduse põhjalik mõistmine on endiselt raskesti mõistetav, on krüptograafid hiljuti teinud põnevaid edusamme ühesuunaliste funktsioonide ühtse teooria suunas. Üks suur samm astuti aastal 2020, kui Tel Avivi ülikooli krüptograaf Rafaeli pass ja tema magistrant Yanyi Liu tõestas, et ühesuunalised funktsioonid on tihedalt seotud konkreetsele tihendusprobleemile, mida nimetatakse ajaliselt piiratud Kolmogorovi keerukuse probleemiks.

Kui seda ühte probleemi on enamiku sisendite puhul tõesti raske lahendada, annab Passi ja Liu tulemus retsepti, kuidas konstrueerida tõestatavalt raske ühesuunaline funktsioon – selline, mis on garanteeritud, et see on turvaline isegi siis, kui muud arvutusprobleemid osutuvad palju lihtsamaks. kui teadlased eeldasid. Aga kui on olemas kiire algoritm ajaga piiratud Kolmogorovi keerukuse probleemi lahendamiseks, siis on krüptograafia hukule määratud ja mis tahes funktsiooni saab kergesti ümber pöörata. Selle probleemi keerukusel põhinev ühesuunaline funktsioon on kõige turvalisem võimalik funktsioon – ühesuunaline funktsioon nende kõigi valitsemiseks.

Andmestruktuuridele tuginedes

Passi ja Liu avastus oli viimane peatükk pikast uurimistööst, mis kasutab keerukuse teooriat krüptograafia aluste paremaks mõistmiseks. Kuid see soovitas ka viisi selle seose ümberpööramiseks: ajaliselt piiratud Kolmogorovi keerukuse probleemi ja funktsiooni inversiooni vaheline samaväärsus tähendab, et arusaam kummastki probleemist võib teise kohta rohkem paljastada. Krüptograafid on funktsioonide inversiooni algoritme uurinud aastakümneid, et paremini mõista nende krüpteerimismeetodite nõrku kohti. Teadlased hakkasid mõtlema, kas need algoritmid võivad aidata vastata keerukuseteooria igivanadele küsimustele.

Nagu paljud arvutusprobleemid, saab funktsioonide inversiooni lahendada põhjaliku otsinguga. Väljundstringi korral ühendage lihtsalt funktsiooni kõik võimalikud sisendid, kuni leiate selle, mis annab õige vastuse.

1980. aastal hakkas krüptograaf Martin Hellman uurima, kas on võimalik midagi paremini teha – sama küsimust, mida nõukogude matemaatikud esitasid tihendusprobleemide kohta aastakümneid varem. Hellman avastasin et jah, see on võimalik – seni, kuni olete nõus eelnevalt lisatööd tegema, kasutades matemaatilisi objekte, mida nimetatakse andmestruktuurideks.

Andmestruktuur on sisuliselt tabel, mis salvestab informatsiooni ümberpööratava funktsiooni kohta ja selle konstrueerimine eeldab funktsiooni väljundite arvutamist teatud strateegiliselt valitud sisendite jaoks. Kõik need arvutused "võivad võtta väga kaua aega," ütles Ryan Williams, MIT-i keerukuse teoreetik. "Kuid idee on selles, et seda tehakse üks kord, üks kord ja kõik." Kui proovite sama funktsiooni inverteerida paljude erinevate väljunditega – näiteks paljude erinevate samamoodi krüpteeritud sõnumite dekodeerimiseks –, võib selle töö ette tegemine olla kasulik.

Muidugi nõuab selle lisateabe salvestamine ruumi, nii et viige see strateegia äärmuseni ja võite saada kiire programmi, mis ei mahu ühelegi arvutile. Hellman kujundas nutika andmestruktuuri, mis võimaldas tema algoritmil inverteerida enamikku funktsioone veidi kiiremini kui ammendav otsing, ilma et see võtaks liiga palju rohkem ruumi. Seejärel 2000. aastal krüptograafid Amos Fiat ja Moni Naor pikendatud Hellmani argumendid kõikidele funktsioonidele.

Pärast Passi ja Liu läbimurret 2020. aastal olid need vanad tulemused ühtäkki äsja aktuaalsed. Fiat-Naori algoritm suudab suvalised funktsioonid ümber pöörata kiiremini kui põhjalik otsing. Kas see võib töötada ka tihendusprobleemide korral?

Ühtlane

Esimesed teadlased, kes selle küsimuse tõstatasid, olid keerukuse teoreetikud Rahul Santanam Oxfordi ülikoolist ja tema magistrant Hanlin Ren. Nad tegid seda a 2021 paber tõestades, et tihendusprobleemid ja funktsioonide ümberpööramine olid veelgi rohkem läbi põimunud, kui teadlased arvasid.

Pass ja Liu tõestasid, et kui ajaliselt piiratud Kolmogorovi keerukuse probleem on raske, siis peab ka funktsiooni inversioon olema raske ja vastupidi. Kuid probleemid võivad olla rasked ja lubavad siiski lahendusi, mis on pisut paremad kui ammendav otsing. Santhanam ja Ren näitasid, et selle vahel, kas ühe probleemi puhul on vaja põhjalikku otsingut, on tihe seos, kas see on vajalik teise probleemi jaoks.

Nende tulemus avaldas erinevat mõju kahele laiale algoritmiklassile, mida teadlased sageli uurivad, mida nimetatakse "ühtlasteks" ja "mitteühtlasteks" algoritmideks. Ühtsed algoritmid järgivad iga sisendi puhul sama protseduuri – näiteks ühtne programm numbriloendite sortimiseks töötab samamoodi, olenemata sellest, kas loendis on 20 kirjet või 20,000 XNUMX kirjet. Ebaühtlased algoritmid kasutavad erineva pikkusega sisendite jaoks erinevaid protseduure.

Fiat-Naori algoritmi kasutatavad andmestruktuurid on alati kohandatud konkreetse funktsiooniga. 10-bitist stringi skrambleeriva funktsiooni inverteerimiseks vajate andmestruktuuri, mis erineb sellest, mida vajate 20-bitist stringi skrambleeriva funktsiooni inverteerimiseks, isegi kui skrambleerimine toimub sarnasel viisil. See muudab Fiat-Naori ebaühtlaseks algoritmiks.

Santhanami ja Reni tulemus näitas, et Fiat-Naori algoritmi võib olla võimalik muuta tihendusprobleemide lahendamise algoritmiks. Kuid algoritmi kohandamine ühest probleemist teise ei olnud lihtne ja nad ei uurinud seda küsimust edasi.

Pass komistas sama idee peale aasta hiljem, kui kuulis Fiati klassikalisest algoritmist kõnet pidamas Naori panust krüptograafiasse. "See idee funktsioonide inversiooni kasutamisest oli mu peas sellest ajast peale olnud," ütles ta. Hiljem hakkas ta selle probleemiga tõsiselt tegelema Tel Avivi ülikooli teadlasega Noam Mazor.

Vahepeal sai Ilango inspiratsiooni probleemi ründamiseks pärast arutelusid teiste teadlastega, sealhulgas Santhanamiga, külastades Californias Berkeleys asuvat Simonsi andmetöötlusteooria instituuti. "See tuli välja ühest neist väga vapustavatest vestlustest, kus te lihtsalt loobite asju," ütles Santhanam. Hiljem ühendas Ilango jõud Williamsiga ja Shuichi Hirahara, keerukuse teoreetik Tokyo riiklikus informaatikainstituudis.

Raske osa oli välja mõelda, kuidas kinnistada Fiat-Naori algoritmi keskmes olev andmestruktuur ebaühtlasesse tihendusprobleemide lahendamise algoritmi. Sellise manustamise jaoks on olemas standardprotseduur, kuid see aeglustab algoritmi, kaotades selle eelise põhjaliku otsingu ees. Kaks meeskonda leidsid nutikamaid viise Fiat-Naori andmestruktuuri kaasamiseks ja said tihendusprobleemide jaoks algoritmid, mis töötasid kõigis sisendites ja jäid kiiremaks kui ammendav otsing.

Kahe algoritmi üksikasjad erinevad veidi. Ilango ja tema kaasautorite oma on kiirem kui ammendav otsing isegi siis, kui piirata otsingut kõige lihtsamate võimalustega, ja see kehtib kõigi tihendusprobleemide puhul - ajaliselt piiratud Kolmogorovi keerukus, minimaalse vooluringi suuruse probleem ja paljud teised. Kuid mõlema algoritmi põhiidee oli sama. Krüptograafia tehnikad olid selles uues valdkonnas oma väärtust tõestanud.

Inversioon konvergents

Uus tõestus ebaühtlaste algoritmide kohta tõstatab loomuliku küsimuse: kuidas on lood ühtsete algoritmidega? Kas on võimalik pakkimisprobleeme kiiremini lahendada kui nende abil ammendav otsing?

Hiljutine tulemuste jada viitab sellele, et iga selline algoritm oleks samaväärne suvaliste funktsioonide ümberpööramise ühtse algoritmiga – mida krüptograafid on aastakümneid edutult otsinud. Seetõttu peavad paljud teadlased seda võimalust ebatõenäoliseks.

"Ma oleksin väga üllatunud," ütles Santhanam. "See nõuaks täiesti uut ideed."

Kuid Allender ütles, et teadlased ei tohiks seda võimalust välistada. "Minu jaoks on hea tööhüpotees olnud see, et kui millegi tegemiseks on ebaühtlane viis, siis tõenäoliselt on see ühtne," ütles ta.

Mõlemal juhul on töö pannud keerukuse teoreetikud uuesti huvi tundma krüptograafia vanade küsimuste vastu. Yuval Ishai, Iisraelis Haifas asuva Technioni krüptograaf, ütles, et see teebki selle kõige põnevamaks.

"Mul on väga hea meel näha seda huvide lähenemist erinevate kogukondade vahel," ütles ta. "Ma arvan, et see on teaduse jaoks suurepärane."