Kryptografitrick gör ett svårt problem lite lättare | Quanta Magazine

Vad är det bästa sättet att lösa svåra problem? Det är frågan i hjärtat av ett delområde av datavetenskap som kallas beräkningskomplexitetsteori. Det är en svår fråga att svara på, men vänd på den så blir det lättare. Det värsta tillvägagångssättet är nästan alltid trial and error, vilket innebär att man pluggar in möjliga lösningar tills man jobbar. Men för vissa problem verkar det helt enkelt inte finnas några alternativ – det sämsta tillvägagångssättet är också det bästa.

Forskare har länge undrat om det någonsin verkligen är fallet, sa Rahul Ilango, en doktorand som studerar komplexitetsteori vid Massachusetts Institute of Technology. "Du kan fråga, 'Finns det problem för vilka gissa-och-kolla bara är optimalt?"

Komplexitetsteoretiker har studerat många beräkningsproblem, och även de svåra erkänner ofta någon form av smart procedur, eller algoritm, som gör det lite lättare att hitta en lösning än ren trial and error. Bland de få undantagen finns så kallade kompressionsproblem, där målet är att hitta den kortaste beskrivningen av en datamängd.

Men i november förra året, två grupper av forskare oberoende av upptäckt en annan algoritm för kompressionsproblem — en som är lite snabbare än att kontrollera alla möjliga svar. Den nya metoden fungerar genom att anpassa en algoritm som uppfanns av kryptografer för 25 år sedan för att attackera ett annat problem. Det finns bara en begränsning: Du måste skräddarsy algoritmen till storleken på din datamängd.

"De är verkligen vackra och viktiga resultat," sa Eric Allender, en teoretisk datavetare vid Rutgers University.

Definiera hårdhet

De nya resultaten är de senaste för att undersöka en fråga som först studerades i Sovjetunionen, långt innan komplexitetsteorin kom. "Innan jag gick i grundskolan formulerade folk i Ryssland detta", sa Allender.

Det specifika beräkningsproblem som dessa sovjetiska forskare studerade, kallat problemet med minsta kretsstorlek, är besläktat med ett som designers av datorhårdvara möter hela tiden. Om du får fullständiga specifikationer för hur en elektronisk krets ska bete sig, kan du hitta den enklaste kretsen som kommer att göra jobbet? Ingen visste hur man skulle lösa detta problem utan "perebor" - ett ryskt ord som ungefär motsvarar "uttömmande sökning".

Problemet med minsta kretsstorlek är ett exempel på ett kompressionsproblem. Du kan beskriva en krets beteende med en lång sträng av bitar — 0:or och 1:or — och sedan fråga om det finns ett sätt att återskapa samma beteende med färre bitar. Att kontrollera alla möjliga kretslayouter skulle ta tid som växer exponentiellt med antalet bitar i strängen.

Denna typ av exponentiell tillväxt är det avgörande kännetecknet för ett hårt beräkningsproblem. Men alla svåra problem är inte lika svåra – vissa har algoritmer som är snabbare än uttömmande sökning, även om deras körtider fortfarande växer exponentiellt. I moderna termer är perebor-frågan om det finns några sådana algoritmer för kompressionsproblem.

1959 hävdade en framstående forskare vid namn Sergey Yablonsky att han har bevisat att uttömmande sökning verkligen var det enda sättet att lösa problemet med minsta kretsstorlek. Men hans bevis lämnade några kryphål. Vissa forskare märkte bristerna vid den tiden, men Yablonsky var inflytelserik nog att avskräcka de flesta andra från att arbeta med Perebor-frågan.

Under decennierna som följde var det få forskare som studerade kompressionsproblem, och perebor-frågan var mest känd som en fotnot i komplexitetsteorins förhistoria. Utbredd uppmärksamhet på frågan kom först nyligen, efter att forskare upptäckt en nyfiken koppling mellan kompressionsproblem och grunderna för kryptografi.

Enkelriktad trafik

Modern kryptografi använder hårda beräkningsproblem för att skydda hemliga meddelanden. Men beräkningshårdhet är bara användbart om det är asymmetriskt - om det är svårt att dechiffrera kodade meddelanden men inte svårt att koda meddelanden i första hand.

I varje kryptografischema är ursprunget till denna asymmetri ett matematiskt objekt som kallas en envägsfunktion, som omvandlar ingångsbitsträngar till utmatningssträngar med samma längd. Med en ingång till en envägsfunktion är det lätt att beräkna utdata, men givet en utdata är det svårt att invertera funktionen – det vill säga att omvända den och återställa ingången.

"Kryptografer skulle verkligen vilja ha mycket, mycket effektivt beräkningsbara envägsfunktioner som är riktigt, riktigt svåra att invertera," sa Allender. Många matematiska funktioner verkar ha denna egenskap, och svårigheten att invertera dessa funktioner härrör från den uppenbara svårigheten att lösa olika beräkningsproblem.

Tyvärr vet kryptografer inte säkert om någon av dessa funktioner verkligen är svåra att invertera - det är faktiskt möjligt att verkliga envägsfunktioner inte existerar. Denna osäkerhet kvarstår eftersom komplexitetsteoretiker har kämpat i 50 år att bevisa att till synes svåra problem verkligen är svåra. Om de inte är det, och om forskare upptäcker supersnabba algoritmer för dessa problem, skulle det vara katastrofalt för kryptografi - som att plötsligt dirigera fortkörande bilar i båda riktningarna på en enkelriktad gata.

Även om en omfattande förståelse av beräkningshårdhet fortfarande är svårfångad, har kryptografer nyligen gjort spännande framsteg mot en enhetlig teori om envägsfunktioner. Ett stort steg togs 2020, när Tel Aviv Universitys kryptograf Rafael Pass och hans doktorand Yanyi Liu bevisat att envägsfunktioner är intimt förbunden till ett specifikt kompressionsproblem som kallas det tidsbundna Kolmogorovs komplexitetsproblem.

Om det ena problemet verkligen är svårt att lösa för de flesta indata, så ger Pass och Lius resultat ett recept för hur man konstruerar en bevisligen svår enkelriktad funktion - en som garanterat är säker även om andra beräkningsproblem visar sig vara mycket lättare än forskarna förväntade sig. Men om det finns en snabb algoritm för att lösa det tidsbegränsade Kolmogorov-komplexitetsproblemet, då är kryptografi dömd, och vilken funktion som helst kan lätt inverteras. En envägsfunktion baserad på det här problemets hårdhet är den säkraste funktionen som möjligt - en envägsfunktion för att styra dem alla.

Bygger på datastrukturer

Pass och Lius upptäckt var det senaste kapitlet i en lång rad forskning som använder komplexitetsteori för att bättre förstå grunderna för kryptografi. Men det föreslog också ett sätt att invertera det förhållandet: motsvarigheten mellan det tidsbundna Kolmogorovs komplexitetsproblem och funktionsinversion innebär att insikter om det ena problemet kan avslöja mer om det andra. Kryptografer har studerat funktionsinversionsalgoritmer i decennier för att bättre förstå de svaga punkterna i deras krypteringsmetoder. Forskare började undra om dessa algoritmer kunde hjälpa till att svara på urgamla frågor inom komplexitetsteorin.

Liksom många beräkningsproblem kan funktionsinvertering lösas genom uttömmande sökning. Med en utdatasträng kopplar du helt enkelt in alla möjliga ingångar till funktionen tills du hittar den som ger rätt svar.

1980 började kryptografen Martin Hellman studera om det var möjligt att göra bättre - samma fråga som de sovjetiska matematikerna hade ställt om kompressionsproblem årtionden tidigare. Hellman upptäckt att ja, det är möjligt - så länge du är villig att lägga ner lite extra arbete i förväg, med hjälp av matematiska objekt som kallas datastrukturer.

En datastruktur är i huvudsak en tabell som lagrar information om funktionen som ska inverteras, och att konstruera en sådan kräver beräkning av utdata från funktionen för vissa strategiskt valda indata. Alla dessa beräkningar "kan ta väldigt lång tid", sa Ryan Williams, en komplexitetsteoretiker vid MIT. "Men tanken är att detta görs en gång, en gång för alla." Om du försöker invertera samma funktion med många olika utgångar - säg att avkoda många olika meddelanden krypterade på samma sätt - kan det vara värt besväret att göra detta i förväg.

Naturligtvis kräver lagring av den extra informationen utrymme, så ta denna strategi till det extrema, och du kan sluta med ett snabbt program som inte får plats på vilken dator som helst. Hellman designade en smart datastruktur som gjorde det möjligt för hans algoritm att invertera de flesta funktioner något snabbare än en uttömmande sökning utan att ta för mycket mer utrymme. Sedan år 2000, kryptograferna Amos Fiat och Moni Naor förlängas Hellmans argument till alla funktioner.

Efter Pass och Lius genombrott 2020 var dessa gamla resultat plötsligt nyrelevanta. Fiat-Naor-algoritmen kunde invertera godtyckliga funktioner snabbare än en uttömmande sökning. Kan det också fungera för kompressionsproblem?

Av Uniform

De första forskarna som tog upp frågan var komplexitetsteoretikern Rahul Santhanam vid University of Oxford och hans doktorand Hanlin Ren. Det gjorde de i en 2021 papper bevisar att kompressionsproblem och funktionsinversion var ännu mer sammanflätade än forskare hade insett.

Pass och Liu hade bevisat att om det tidsbegränsade Kolmogorovs komplexitetsproblem är svårt, måste funktionsinversion också vara svårt, och vice versa. Men problem kan vara svåra och ändå erkänna lösningar som är lite bättre än uttömmande sökning. Santhanam och Ren visade att det finns ett nära samband mellan om uttömmande sökning krävs för ett problem och om det krävs för det andra.

Deras resultat hade olika implikationer för två breda klasser av algoritmer som forskare ofta studerar, kallade "enhetliga" och "olikformiga" algoritmer. Enhetliga algoritmer följer samma procedur för varje inmatning - ett enhetligt program för att sortera listor med nummer, till exempel, kommer att fungera på samma sätt oavsett om det finns 20 poster på listan eller 20,000 XNUMX. Olikformiga algoritmer använder istället olika procedurer för ingångar av olika längd.

Datastrukturerna som används av Fiat-Naor-algoritmen är alltid skräddarsydda för en specifik funktion. För att invertera en funktion som förvränger en 10-bitars sträng behöver du en datastruktur som skiljer sig från den du skulle behöva för att invertera en funktion som förvränger en 20-bitars sträng, även om krypteringen görs på liknande sätt. Det gör Fiat-Naor till en olikformig algoritm.

Santhanam och Rens resultat antydde att det skulle vara möjligt att omvandla Fiat-Naor-algoritmen till en algoritm för att lösa kompressionsproblem. Men att anpassa algoritmen från ett problem till ett annat var inte okomplicerat, och de fortsatte inte med frågan vidare.

Pass snubblade på samma idé ett år senare, efter att ha hört Fiat hålla ett föredrag om den klassiska algoritmen på en workshop för att fira Naors bidrag till kryptografi. "Den här idén om att använda funktionsinversion hade legat i bakhuvudet sedan dess," sa han. Han började senare arbeta med problemet på allvar med forskaren vid Tel Aviv University Noam Mazor.

Samtidigt blev Ilango inspirerad att attackera problemet efter diskussioner med andra forskare, inklusive Santhanam, på ett besök på Simons Institute for the Theory of Computing i Berkeley, Kalifornien. "Det kom ur en av dessa mycket slumpmässiga konversationer där du bara slänger runt saker," sa Santhanam. Ilango slog sig senare samman med Williams och Shuichi Hirahara, en komplexitetsteoretiker vid National Institute of Informatics i Tokyo.

Det svåra var att ta reda på hur man bäddar in datastrukturen i hjärtat av Fiat-Naor-algoritmen i en olikformig algoritm för att lösa kompressionsproblem. Det finns en standardprocedur för att göra den typen av inbäddning, men det skulle sakta ner algoritmen och utplåna dess fördel jämfört med uttömmande sökning. De två teamen hittade smartare sätt att införliva Fiat-Naors datastruktur och fick algoritmer för kompressionsproblem som fungerade på alla ingångar och förblev snabbare än uttömmande sökningar.

Detaljerna för de två algoritmerna skiljer sig något åt. Den av Ilango och hans medförfattare är snabbare än uttömmande sökning även om du begränsar sökningen till de enklaste möjligheterna, och den gäller för alla kompressionsproblem - tidsbunden Kolmogorov-komplexitet, problemet med minsta kretsstorlek och många andra. Men kärnidén var densamma för båda algoritmerna. Teknikerna från kryptografi hade bevisat sitt värde i denna nya domän.

Inversionskonvergens

Det nya beviset för olikformiga algoritmer väcker en naturlig fråga: Hur är det med enhetliga algoritmer? Finns det något sätt att lösa kompressionsproblem snabbare än att göra en uttömmande sökning med dem?

Den senaste strängen av resultat antyder att varje sådan algoritm skulle vara likvärdig med en enhetlig algoritm för att invertera godtyckliga funktioner - något som kryptografer utan framgång har sökt i årtionden. På grund av det finner många forskare möjligheten osannolik.

"Jag skulle bli mycket förvånad," sa Santhanam. "Det skulle kräva en helt ny idé."

Men Allender sa att forskare inte borde bortse från möjligheten. "En bra arbetshypotes för mig har varit att om det finns ett oenhetligt sätt att göra något så finns det mycket troligt ett enhetligt sätt," sa han.

Hur som helst har arbetet gjort komplexitetsteoretiker nyintresserade av gamla frågor inom kryptografi. Yuval Ishai, en kryptograf vid Technion i Haifa, Israel, sa att det är det som gör det mest spännande.

"Jag är verkligen glad att se denna konvergens av intresse mellan olika samhällen," sade han. "Jag tror att det är bra för vetenskapen."