Den berömda kryptografialgoritmen får en uppgradering | Quanta Magazine

I våra alltmer digitala liv är säkerheten beroende av kryptografi. Skicka ett privat meddelande eller betala en räkning online så förlitar du dig på algoritmer som är utformade för att hålla din data hemlig. Naturligtvis vill vissa människor avslöja dessa hemligheter - så forskare arbetar med att testa styrkan hos dessa system för att säkerställa att de inte faller sönder i händerna på en smart angripare.

Ett viktigt verktyg i detta arbete är LLL-algoritmen, uppkallad efter forskarna som publicerade den 1982 — Arjen Lenstra, Hendrik Lenstra Jr. och László Lovász. LLL, tillsammans med dess många ättlingar, kan bryta kryptografiska system i vissa fall; Att studera hur de beter sig hjälper forskare att designa system som är mindre sårbara för attacker. Och algoritmens talanger sträcker sig bortom kryptografi: Det är också ett användbart verktyg inom avancerade matematiska arenor som beräkningsnummerteori.

Under åren har forskare finslipat varianter av LLL för att göra tillvägagångssättet mer praktiskt - men bara upp till en viss punkt. Nu har ett par kryptografer byggt en ny LLL-liknande algoritm med en betydande ökning av effektiviteten. Den nya tekniken, som vann Pris för bästa papper vid Internationell kryptologikonferens 2023, breddar utbudet av scenarier där datavetare och matematiker kan använda LLL-liknande metoder.

"Det var riktigt spännande," sa Chris Peikert, en kryptograf vid University of Michigan som inte var involverad i tidningen. Verktyget har varit i fokus för studier i decennier, sa han. "Det är alltid trevligt när ett mål som har arbetats på så länge ... visar att det fortfarande finns överraskningar att hitta."

Algoritmer av LLL-typ fungerar i gittervärlden: oändliga samlingar av regelbundet åtskilda punkter. Som ett sätt att visualisera detta, föreställ dig att du kakel ett golv. Du kan täcka den med fyrkantiga brickor, och hörnen på dessa brickor skulle utgöra ett galler. Alternativt kan du välja en annan kakelform - säg ett långt parallellogram - för att skapa ett annat gitter.

Ett gitter kan beskrivas med dess "bas". Detta är en uppsättning vektorer (i huvudsak listor med tal) som du kan kombinera på olika sätt för att få varje punkt i gittret. Låt oss föreställa oss ett gitter med en bas som består av två vektorer: [3, 2] och [1, 4]. Gittret är bara alla punkter du kan nå genom att lägga till och subtrahera kopior av dessa vektorer.

Det vektorparet är inte gittrets enda grund. Varje gitter med minst två dimensioner har oändligt många möjliga baser. Men alla baser är inte skapade lika. En bas vars vektorer är kortare och närmare räta vinklar med varandra är vanligtvis lättare att arbeta med och mer användbar för att lösa vissa beräkningsproblem, så forskare kallar dessa baser "bra". Ett exempel på detta är paret blå vektorer i figuren nedan. Baser som består av längre och mindre ortogonala vektorer - som de röda vektorerna - kan betraktas som "dåliga".

Det här är ett jobb för LLL: Ge det (eller dess bröder) en bas av ett flerdimensionellt gitter, och det kommer att spotta ut ett bättre. Denna process är känd som gitterbasreduktion.

Vad har allt detta med kryptografi att göra? Det visar sig att uppgiften att bryta ett kryptografiskt system i vissa fall kan omformas som ett annat problem: att hitta en relativt kort vektor i ett gitter. Och ibland kan den vektorn plockas från den reducerade basen som genereras av en LLL-stilsalgoritm. Denna strategi har hjälpt forskare att störta system som på ytan verkar ha lite att göra med galler.

I teoretisk mening går den ursprungliga LLL-algoritmen snabbt: tiden det tar att köra skalas inte exponentiellt med storleken på indata - det vill säga dimensionen på gittret och storleken (i bitar) på talen i basvektorer. Men det ökar som en polynomfunktion, och "om du faktiskt vill göra det är polynomtid inte alltid så genomförbart," sa Léo Ducas, en kryptograf vid det nationella forskningsinstitutet CWI i Nederländerna.

I praktiken betyder det att den ursprungliga LLL-algoritmen inte kan hantera indata som är för stora. "Matematiker och kryptografer ville ha förmågan att göra mer," sa Keegan Ryan, doktorand vid University of California, San Diego. Forskare arbetade för att optimera LLL-stilsalgoritmer för att rymma större indata, vilket ofta uppnådde bra prestanda. Ändå har vissa uppgifter legat envist utom räckhåll.

Den nya tidningen, författad av Ryan och hans rådgivare, Nadia Heninger, kombinerar flera strategier för att förbättra effektiviteten hos sin LLL-stilsalgoritm. För det första använder tekniken en rekursiv struktur som bryter ner uppgiften i mindre bitar. För en annan hanterar algoritmen noggrant precisionen av de inblandade siffrorna, och hittar en balans mellan hastighet och ett korrekt resultat. Det nya arbetet gör det möjligt för forskare att reducera baserna på gitter med tusentals dimensioner.

Tidigare arbete har följt ett liknande tillvägagångssätt: A 2021 papper kombinerar också rekursion och precisionshantering för att göra snabba arbeten av stora gitter, men det fungerade bara för specifika typer av gitter, och inte alla de som är viktiga i kryptografi. Den nya algoritmen fungerar bra på ett mycket bredare område. "Jag är verkligen glad att någon gjorde det," sa Thomas Espitau, en kryptografiforskare på företaget PQShield och en författare till 2021-versionen. Hans teams arbete erbjöd ett "proof of concept", sa han; det nya resultatet visar att "du kan göra mycket snabb gitterreduktion på ett bra sätt."

Den nya tekniken har redan börjat visa sig användbar. Aurel Page, en matematiker vid det franska nationella forskningsinstitutet Inria, sa att han och hans team har gjort en anpassning av algoritmen för att arbeta med vissa beräkningsuppgifter för talteori.

Algoritmer av LLL-stil kan också spela en roll i forskning relaterad till gitterbaserade kryptografisystem utformade för att förbli säker även i en framtid med kraftfulla kvantdatorer. De utgör inget hot mot sådana system, eftersom att ta ner dem kräver att man hittar kortare vektorer än vad dessa algoritmer kan uppnå. Men de bästa attacker forskarna känner till använder en LLL-stilsalgoritm som en "grundläggande byggsten", sa Wessel van Woerden, en kryptograf vid universitetet i Bordeaux. I praktiska experiment för att studera dessa attacker kan den byggstenen sakta ner allt. Med det nya verktyget kan forskare kanske utöka utbudet av experiment de kan köra på attackalgoritmerna, vilket ger en tydligare bild av hur de presterar.

Quanta genomför en serie undersökningar för att bättre betjäna vår publik. Ta vår datavetenskaplig läsarundersökning och du kommer att delta för att vinna gratis Quanta handelsvaror.