Kryptografitriks gjør et vanskelig problem litt enklere | Quanta Magazine

Hva er den beste måten å løse vanskelige problemer på? Det er spørsmålet i hjertet av et underfelt av informatikk kalt beregningskompleksitetsteori. Det er et vanskelig spørsmål å svare på, men snu det rundt og det blir lettere. Den verste tilnærmingen er nesten alltid prøving og feiling, som innebærer å plugge inn mulige løsninger til en fungerer. Men for noen problemer ser det ut til at det rett og slett ikke er noen alternativer - den verste tilnærmingen er også den beste.

Forskere har lenge lurt på om det noen gang virkelig er tilfelle, sa Rahul Ilango, en doktorgradsstudent som studerer kompleksitetsteori ved Massachusetts Institute of Technology. "Du kan spørre: 'Er det problemer som gjetting-og-sjekk er optimalt for?'"

Kompleksitetsteoretikere har studert mange beregningsproblemer, og selv de vanskelige innrømmer ofte en slags smart prosedyre, eller algoritme, som gjør det litt lettere å finne en løsning enn ren prøving og feiling. Blant de få unntakene er såkalte kompresjonsproblemer, hvor målet er å finne den korteste beskrivelsen av et datasett.

Men i november i fjor, to grupper av forskere uavhengig av hverandre oppdaget en annen algoritme for kompresjonsproblemer - en som er litt raskere enn å sjekke alle mulige svar. Den nye tilnærmingen fungerer ved å tilpasse en algoritme oppfunnet av kryptografer for 25 år siden for å angripe et annet problem. Det er bare én begrensning: Du må skreddersy algoritmen til størrelsen på datasettet ditt.

"De er virkelig vakre og viktige resultater," sa Eric Allender, en teoretisk informatiker ved Rutgers University.

Definere hardhet

De nye resultatene er de siste som har undersøkt et spørsmål som først ble studert i Sovjetunionen, i god tid før kompleksitetsteorien kom. "Før jeg gikk på barneskolen, formulerte folk i Russland dette," sa Allender.

Det spesifikke beregningsproblemet som de sovjetiske forskerne studerte, kalt minimumskretsstørrelsesproblemet, er beslektet med et som designere av maskinvare står overfor hele tiden. Hvis du får fullstendige spesifikasjoner for hvordan en elektronisk krets skal oppføre seg, kan du finne den enkleste kretsen som vil gjøre jobben? Ingen visste hvordan de skulle løse dette problemet uten "perebor" - et russisk ord som omtrent tilsvarer "uttømmende søk."

Minimumskretsstørrelsesproblemet er et eksempel på et kompresjonsproblem. Du kan beskrive en krets oppførsel med en lang rekke biter - 0-er og 1-er - og deretter spørre om det er en måte å reprodusere den samme oppførselen ved å bruke færre biter. Å sjekke alle mulige kretsoppsett vil ta tid som vokser eksponentielt med antall biter i strengen.

Denne typen eksponentiell vekst er den definerende egenskapen til et vanskelig beregningsproblem. Men ikke alle vanskelige problemer er like vanskelige - noen har algoritmer som er raskere enn uttømmende søk, selv om kjøretidene deres fortsatt vokser eksponentielt. I moderne termer er perebor-spørsmålet om det finnes slike algoritmer for kompresjonsproblemer.

I 1959 hevdet en fremtredende forsker ved navn Sergey Yablonsky å ha bevist at uttømmende søk virkelig var den eneste måten å løse problemet med minste kretsstørrelse. Men beviset hans etterlot noen smutthull. Noen forskere la merke til manglene på den tiden, men Yablonsky var innflytelsesrik nok til å fraråde de fleste andre fra å jobbe med perebor-spørsmålet.

I tiårene som fulgte var det få forskere som studerte kompresjonsproblemer, og perebor-spørsmålet var mest kjent som en fotnote i kompleksitetsteoriens forhistorie. Utbredt oppmerksomhet til spørsmålet kom først nylig, etter at forskere oppdaget en merkelig sammenheng mellom kompresjonsproblemer og grunnlaget for kryptografi.

Enveis trafikk

Moderne kryptografi bruker harde beregningsproblemer for å beskytte hemmelige meldinger. Men beregningshardhet er bare nyttig hvis den er asymmetrisk - hvis det er vanskelig å tyde kodede meldinger, men ikke vanskelig å kode meldinger i utgangspunktet.

I hvert kryptografiskjema er opprinnelsen til denne asymmetrien et matematisk objekt kalt en enveisfunksjon, som forvandler inngangsbitstrenger til utgangsstrenger med samme lengde. Gitt en inngang til en enveisfunksjon, er det enkelt å beregne utgangen, men gitt en utgang er det vanskelig å invertere funksjonen - det vil si å reversere den og gjenopprette inngangen.

"Kryptografer vil virkelig gjerne ha veldig, veldig effektivt beregnbare enveisfunksjoner som er veldig, veldig vanskelige å invertere," sa Allender. Mange matematiske funksjoner ser ut til å ha denne egenskapen, og vanskeligheten med å invertere disse funksjonene stammer fra den tilsynelatende vanskeligheten med å løse forskjellige beregningsproblemer.

Dessverre vet ikke kryptografer med sikkerhet om noen av disse funksjonene virkelig er vanskelige å invertere - det er faktisk mulig at ekte enveisfunksjoner ikke eksisterer. Denne usikkerheten vedvarer fordi kompleksitetsteoretikere har kjempet i 50 år å bevise at tilsynelatende vanskelige problemer virkelig er vanskelige. Hvis de ikke er det, og hvis forskere oppdager superraske algoritmer for disse problemene, ville det være katastrofalt for kryptografi - på lik linje med å plutselig dirigere raske biler i begge retninger på en enveiskjørt gate.

Selv om en omfattende forståelse av beregningshardhet fortsatt er unnvikende, har kryptografer nylig gjort spennende fremskritt mot en enhetlig teori om enveisfunksjoner. Ett stort skritt ble tatt i 2020, da Tel Aviv Universitys kryptograf Rafael Pass og hans hovedfagsstudent Yanyi Liu bevist at enveisfunksjoner er nært knyttet til et spesifikt kompresjonsproblem kalt det tidsbegrensede Kolmogorov-kompleksitetsproblemet.

Hvis det ene problemet virkelig er vanskelig å løse for de fleste innganger, gir Pass og Lius resultat en oppskrift på hvordan man kan konstruere en beviselig vanskelig enveisfunksjon – en som garantert er sikker selv om andre beregningsproblemer skulle vise seg å være langt enklere enn forskerne forventet. Men hvis det er en rask algoritme for å løse det tidsbegrensede Kolmogorov-kompleksitetsproblemet, er kryptografi dømt, og enhver funksjon kan enkelt inverteres. En enveisfunksjon basert på hardheten til dette problemet er den sikreste funksjonen som er mulig - en enveisfunksjon for å styre dem alle.

Bygger på datastrukturer

Pass og Lius oppdagelse var det siste kapittelet i en lang rekke forskning som bruker kompleksitetsteori for å bedre forstå grunnlaget for kryptografi. Men det antydet også en måte å snu dette forholdet på: Ekvivalensen mellom det tidsavgrensede Kolmogorov-kompleksitetsproblemet og funksjonsinversjonen innebærer at innsikt om begge problemer kan avsløre mer om den andre. Kryptografer har studert funksjonsinversjonsalgoritmer i flere tiår for å bedre forstå de svake punktene ved krypteringsmetodene deres. Forskere begynte å lure på om disse algoritmene kunne hjelpe til med å svare på eldgamle spørsmål innen kompleksitetsteori.

Som mange beregningsproblemer kan funksjonsinversjon løses ved uttømmende søk. Gitt en utgangsstreng, plugg ganske enkelt alle mulige innganger inn i funksjonen til du finner den som gir det riktige svaret.

I 1980 begynte kryptografen Martin Hellman å studere om det var mulig å gjøre noe bedre - det samme spørsmålet som de sovjetiske matematikerne hadde stilt om kompresjonsproblemer tiår tidligere. Helvete mann oppdaget at ja, det er mulig - så lenge du er villig til å legge ned litt ekstra arbeid på forhånd, ved å bruke matematiske objekter kalt datastrukturer.

En datastruktur er i hovedsak en tabell som lagrer informasjon om funksjonen som skal inverteres, og å konstruere en krever å beregne utdataene til funksjonen for visse strategisk valgte innganger. Alle disse beregningene "kan ta veldig lang tid," sa Ryan Williams, en kompleksitetsteoretiker ved MIT. "Men tanken er at dette gjøres en gang, en gang for alle." Hvis du prøver å invertere den samme funksjonen gitt mange forskjellige utganger - for eksempel å dekode mange forskjellige meldinger kryptert på samme måte - kan det være verdt å gjøre dette arbeidet på forhånd.

Selvfølgelig krever lagring av den ekstra informasjonen plass, så ta denne strategien til det ekstreme, og du kan ende opp med et raskt program som ikke får plass på noen datamaskin. Hellman designet en smart datastruktur som gjorde at algoritmen hans kunne invertere de fleste funksjoner litt raskere enn uttømmende søk uten å ta for mye mer plass. Så i 2000, kryptografene Amos Fiat og Moni Naor utvidet Hellmans argumenter til alle funksjoner.

Etter Pass og Lius gjennombrudd i 2020, var disse gamle resultatene plutselig nylig relevante. Fiat-Naor-algoritmen kan invertere vilkårlige funksjoner raskere enn uttømmende søk. Kan det også fungere for kompresjonsproblemer?

Ute av uniform

De første forskerne som stilte spørsmålet var kompleksitetsteoretikeren Rahul Santhanam ved University of Oxford og hans doktorgradsstudent Hanlin Ren. Det gjorde de i en 2021 papir beviser at kompresjonsproblemer og funksjonsinversjon var enda mer sammenvevd enn forskerne hadde skjønt.

Pass og Liu hadde bevist at hvis det tidsbegrensede Kolmogorov-kompleksitetsproblemet er vanskelig, så må funksjonsinversjon også være vanskelig, og omvendt. Men problemer kan være vanskelige og likevel innrømme løsninger som er litt bedre enn uttømmende søk. Santhanam og Ren viste at det er en nær sammenheng mellom om uttømmende søk er nødvendig for det ene problemet og om det er nødvendig for det andre.

Resultatet deres hadde forskjellige implikasjoner for to brede klasser av algoritmer som forskere ofte studerer, kalt "uniforme" og "ikke-uniforme" algoritmer. Ensartede algoritmer følger samme prosedyre for hver inndata - et enhetlig program for å sortere lister med tall, for eksempel, vil fungere på samme måte enten det er 20 oppføringer på listen eller 20,000 XNUMX. Uensartede algoritmer bruker i stedet forskjellige prosedyrer for innganger av forskjellig lengde.

Datastrukturene som brukes av Fiat-Naor-algoritmen er alltid skreddersydd til en spesifikk funksjon. For å invertere en funksjon som krypterer en 10-bits streng, trenger du en datastruktur som er forskjellig fra den du trenger for å invertere en funksjon som krypterer en 20-bits streng, selv om krypteringen gjøres på lignende måte. Det gjør Fiat-Naor til en uensartet algoritme.

Santhanam og Rens resultat antydet at det kunne være mulig å transformere Fiat-Naor-algoritmen til en algoritme for å løse kompresjonsproblemer. Men å tilpasse algoritmen fra det ene problemet til det andre var ikke enkelt, og de forfulgte ikke spørsmålet videre.

Pass snublet over den samme ideen et år senere, etter å ha hørt Fiat holde en tale om den klassiske algoritmen på en workshop som feiret Naors bidrag til kryptografi. "Denne ideen om å bruke funksjonsinversjon hadde vært i bakhodet siden den gang," sa han. Senere begynte han å jobbe med problemet for alvor med en forsker ved Tel Aviv University Noam Mazor.

I mellomtiden ble Ilango inspirert til å angripe problemet etter diskusjoner med andre forskere, inkludert Santhanam, på et besøk til Simons Institute for Theory of Computing i Berkeley, California. "Det kom ut av en av disse veldig serendipitøse samtalene der du bare kaster ting rundt deg," sa Santhanam. Ilango slo seg senere sammen med Williams og Shuichi Hirahara, en kompleksitetsteoretiker ved National Institute of Informatics i Tokyo.

Den vanskelige delen var å finne ut hvordan man kunne bygge inn datastrukturen i hjertet av Fiat-Naor-algoritmen i en uensartet algoritme for å løse kompresjonsproblemer. Det er en standard prosedyre for å gjøre den typen innebygging, men det ville bremse algoritmen ned og utslette fordelen i forhold til uttømmende søk. De to teamene fant smartere måter å innlemme Fiat-Naor-datastrukturen, og oppnådde algoritmer for komprimeringsproblemer som fungerte på alle innganger og forble raskere enn uttømmende søk.

Detaljene til de to algoritmene er litt forskjellige. Den av Ilango og hans medforfattere er raskere enn uttømmende søk selv om du begrenser søket til de enkleste mulighetene, og det gjelder alle komprimeringsproblemer - tidsavgrenset Kolmogorov-kompleksitet, problemet med minimumskretsstørrelse og mange andre. Men kjerneideen var den samme for begge algoritmene. Teknikkene fra kryptografi hadde bevist sin verdi i dette nye domenet.

Inversjonskonvergens

Det nye beviset for uensartede algoritmer reiser et naturlig spørsmål: Hva med enhetlige algoritmer? Er det en måte å løse komprimeringsproblemer raskere enn uttømmende søk ved å bruke dem?

Den nylige rekken av resultater antyder at enhver slik algoritme vil tilsvare en enhetlig algoritme for å invertere vilkårlige funksjoner - noe som kryptografer uten hell har søkt i flere tiår. På grunn av det finner mange forskere muligheten usannsynlig.

"Jeg ville bli veldig overrasket," sa Santhanam. "Det ville kreve en helt ny idé."

Men Allender sa at forskere ikke burde utelukke muligheten. "En god arbeidshypotese for meg har vært at hvis det er en uensartet måte å gjøre noe på, er det veldig sannsynlig at det er en enhetlig måte," sa han.

Uansett har arbeidet gjort kompleksitetsteoretikere nyinteresserte i gamle spørsmål innen kryptografi. Yuval Ishai, en kryptograf ved Technion i Haifa, Israel, sa at det er det som gjør det mest spennende.

"Jeg er veldig glad for å se denne konvergensen av interesse mellom forskjellige samfunn," sa han. "Jeg tror det er flott for vitenskapen."