The focus of this thesis is the threat that quantum computers pose to asymmetric cryptography. This threat is considered through analysis and development of both quantum algorithms and post-quantum cryptosystems. Lattices are used in both of these areas of this thesis; lattice-based analysis is used for the quantum algorithms and the cryptosystems are lattice-based.

Arguably the most important building block for lattice-based cryptography is the Learning With Errors (LWE) problem. This problem was introduced by Regev in 2005 together with a quantum reduction from standard lattice problems. In this thesis Regev’s reduction is analyzed in detail, allowing for the first parametrization of a cryptosystem whose concrete security actually is based upon this reduction.

Another important problem used for lattice-based cryptography is the NTRU problem, which was introduced several years before the LWE problem. In this thesis, the NTWE problem is introduced as a natural combination of the NTRU and LWE problems with NTWE-based cryptosystems having certain benefits over comparable NTRU and LWE-based systems.

The quantum algorithms considered in this thesis are variants of Regev’s recently introduced quantum factoring algorithm. When attacking factoring-based cryptography, Regev’s algorithm has certain asymptotic advantages over previous quantum algorithms. As a part of this thesis, variants of Regev’s algorithm for solving other cryptographically relevant problems are introduced. Additionally, by analyzing the lattice-based classical post-processing of the algorithm, it is argued that the algorithm can be made robust to quantum errors.

Although Regev’s new algorithm, and the variations thereof, have an asymptotic advantage over previous quantum algorithms, an advantage for the concrete instances that are used for cryptography would arguably be more interesting. This motivates comparing the concrete efficiency of variants of Regev’s algorithm to that of previous quantum algorithms. Such a comparison is part of this thesis and — based on this comparison — it seems like previously available algorithms still are the best choice for quantum attacks against traditional cryptography.

The final contribution of this thesis is a new lattice-based digital signature scheme. Similar signature schemes have been considered before, such as with the recently standardized ML-DSA. However, compared to similar signature schemes, the new scheme is significantly more compact. This is in large part thanks to developing a new technique for constructing signatures, but also to some extent from being based on the NTWE problem instead of a variant of the LWE problem.

Den här avhandlingen fokuserar på hotet som kvantdatorer innebär för asymmetrisk kryptografi. Mer specifikt analyseras och utvecklas både kvantdatorsäkra kryptosystem och kvantdatoralgoritmer som knäcker klassisk kryptografi. Inom båda dessa områden av avhandlingen så är gitter relevanta. Detta då relevanta kvantdatoralgoritmer analyseras med hjälp av gitter och fokus ligger på gitterbaserad kvantdatorsäker kryptografi.

En av hörnstenarna inom gitterbaserad kryptografi är “Learning With Errors” (LWE) problemet som introducerades 2005 av Regev. I samma arbete så utvecklade Regev även en kvantreduktion till LWE problemet från ett traditionellt gitterproblem. Ett av arbetena i denna avhandling analyserar denna reduktion i detalj, vilket möjliggör den första parametriseringen av ett kryptosystem vars konkreta säkerhet faktiskt baseras på denna reduktion.

Ett annat viktigt problem som används för gitterbaserad kryptografi är NTRU problemet, vilket introducerades flera år innan LWE problemet. I den här avhandlingen så introduceras NTWE problemet som en naturlig kombination av NTRU och LWE problemen. Dessutom utvecklas ett NTWE baserat kryptosystem som har vissa fördelar gentemot jämförbara NTRU och LWE baserade system.

Nyligen introducerade Regev en kvantfaktoriseringsalgoritm som, i vissa avseenden, är asymptotiskt bättre än tidigare kvantdatoralgoritmer på att attackera kryptografi som är baserad på svårigheten att faktorisera heltal. Som en del av denna avhandling så utvecklas nya varianter av Regevs algoritm som kan användas för att effektivt lösa andra kryptografiskt relevanta problem. Genom att analysera den gitterbaserade efterbehandlingen av algoritmen så argumenteras det också för att den kan göras robust mot fel i kvantdatorberäkningarna.

I denna avhandling så jämförs också den faktiska prestandan hos varianter av Regevs algoritm mot den hos tidigare kvantdatoralgoritmer. Trots att de nya algoritmerna har ett asymptotiskt övertag så visar jämförelsen att de tidigare algoritmerna fortfarande är att föredra för de konkreta probleminstanser som är kryptografiskt relevanta.

Det sista bidraget i denna avhandling är en ny gitterbaserad algoritm för digitala signaturer. Signaturscheman som bygger på liknande idéer finns sedan tidigare, exempelvis det nyligen standardiserade ML-DSA. Jämfört med dessa liknande scheman så är det nya signaturschemat som utvecklas i denna avhandling betydligt mer kompakt. Detta är till stor grad tack vare utvecklandet av en ny metod för att konstruera signaturer, men också till viss mån tack vare att schemat är baserat på NTWE problemet istället för någon variant av LWE problemet.