Lattice-Based Post-Quantum Cryptography and Quantum Algorithms

Tid: Må 2025-06-09 kl 14.00

Plats: F3 (Flodis), Lindstedtsvägen 26 & 28, Campus

Videolänk: https://kth-se.zoom.us/j/62914864473

Språk: Engelska

Ämnesområde: Datalogi

Respondent: Joel Gärtner , Algebra, kombinatorik och topologi

Opponent: Professor Vinod Vaikuntanathan, Massachusetts Institute of Technology, MA, USA

Handledare: Professor Johan Håstad, Algebra, kombinatorik och topologi

Exportera till kalender

Abstract

Den här avhandlingen fokuserar på hotet som kvantdatorer innebär för asymmetrisk kryptografi. Mer specifikt analyseras och utvecklas både kvantdatorsäkra kryptosystem och kvantdatoralgoritmer som knäcker klassisk kryptografi. Inom båda dessa områden av avhandlingen så är gitter relevanta. Detta då relevanta kvantdatoralgoritmer analyseras med hjälp av gitter och fokus ligger på gitterbaserad kvantdatorsäker kryptografi.

En av hörnstenarna inom gitterbaserad kryptografi är “Learning With Errors” (LWE) problemet som introducerades 2005 av Regev. I samma arbete så utvecklade Regev även en kvantreduktion till LWE problemet från ett traditionellt gitterproblem. Ett av arbetena i denna avhandling analyserar denna reduktion i detalj, vilket möjliggör den första parametriseringen av ett kryptosystem vars konkreta säkerhet faktiskt baseras på denna reduktion.

Ett annat viktigt problem som används för gitterbaserad kryptografi är NTRU problemet, vilket introducerades flera år innan LWE problemet. I den här avhandlingen så introduceras NTWE problemet som en naturlig kombination av NTRU och LWE problemen. Dessutom utvecklas ett NTWE baserat kryptosystem som har vissa fördelar gentemot jämförbara NTRU och LWE baserade system.

Nyligen introducerade Regev en kvantfaktoriseringsalgoritm som, i vissa avseenden, är asymptotiskt bättre än tidigare kvantdatoralgoritmer på att attackera kryptografi som är baserad på svårigheten att faktorisera heltal. Som en del av denna avhandling så utvecklas nya varianter av Regevs algoritm som kan användas för att effektivt lösa andra kryptografiskt relevanta problem. Genom att analysera den gitterbaserade efterbehandlingen av algoritmen så argumenteras det också för att den kan göras robust mot fel i kvantdatorberäkningarna.

I denna avhandling så jämförs också den faktiska prestandan hos varianter av Regevs algoritm mot den hos tidigare kvantdatoralgoritmer. Trots att de nya algoritmerna har ett asymptotiskt övertag så visar jämförelsen att de tidigare algoritmerna fortfarande är att föredra för de konkreta probleminstanser som är kryptografiskt relevanta.

Det sista bidraget i denna avhandling är en ny gitterbaserad algoritm för digitala signaturer. Signaturscheman som bygger på liknande idéer finns sedan tidigare, exempelvis det nyligen standardiserade ML-DSA. Jämfört med dessa liknande scheman så är det nya signaturschemat som utvecklas i denna avhandling betydligt mer kompakt. Detta är till stor grad tack vare utvecklandet av en ny metod för att konstruera signaturer, men också till viss mån tack vare att schemat är baserat på NTWE problemet istället för någon variant av LWE problemet.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-363229

Till kalendern