We provide a high-level cost comparison between Regev's quantum algorithm with Ekerå–Gärtner's extensions on the one hand, and existing state-of-the-art quantum algorithms for factoring and computing discrete logarithms on the other. This when targeting cryptographically relevant problem instances, and when accounting for the space-saving optimizations of Ragavan and Vaikuntanathan that apply to Regev's algorithm, and optimizations such as windowing that apply to the existing algorithms.

Our conclusion is that Regev's algorithm without the space-saving optimizations may achieve a per-run advantage, but not an overall advantage, if non-computational quantum memory is cheap. Regev's algorithm with the space-saving optimizations does not achieve an advantage, since it uses more computational memory, whilst also performing more work, per run and overall, compared to the existing state-of-the-art algorithms. As such, further optimizations are required for it to achieve an advantage for cryptographically relevant problem instances.

One of the primary approaches for constructing lattice-based signature schemes is through the “Fiat-Shamir with aborts” methodology. Schemes constructed using this approach may abort and restart during signing, corresponding to rejection sampling produced signatures in order to ensure that they follow a distribution that is independent of the secret key. This rejection sampling is only feasible when the output distribution is sufficiently wide, limiting how compact this type of signature schemes can be. In this work, we develop a new method to construct lattice signatures with the “Fiat-Shamir with aborts” approach. By constructing signatures in a way that is influenced by the rejection condition, we can significantly lower the rejection probability. This allows our scheme to use an iterative rejection sampling to target narrower output distributions than previous methods, resulting in much more compact signatures. In the most compact variant of our new signature scheme, the combined size of a signature and a verification key is less than half of that for ML-DSA and comparable to that of compact hash-and-sign lattice signature schemes, such as Falcon. Alternatively, by targeting a somewhat wider distribution, the rejection condition of the scheme can be securely ignored. This non-aborting variant of our scheme still retains a notable size advantage over previous lattice-based Fiat-Shamir schemes.

The CRYSTALS-Dilithium digital signature scheme, selected by NIST as a post-quantum cryptography (PQC) standard under the name ML-DSA, employs a public key compression technique intended for performance optimization. Specifically, the module learning with error instance (A, t) is compressed by omitting the low-order bits t0 of the vector t. It was recently shown that knowledge of t0 enables more effective side-channel attacks on Dilithium implementations. Another recent work demonstrated a method for reconstructing t0 from multiple signatures. In this paper, we build upon this method by applying profiled deep learning-assisted side-channel analysis to partially recover the least significant bit of t0 from power traces. As a result, the number of signatures required for the reconstruction of t0 can be reduced by roughly half. We demonstrate how the new t0 reconstruction method enhances the efficiency of recovering the secret key component s1, thereby facilitating digital signature forgery, on an ARM Cortex-M4 implementation of Dilithium.

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.

One of the primary approaches for constructing lattice-based signature schemes is through the “Fiat-Shamir with aborts” methodology. Schemes constructed using this approach may abort and restart during signing, corresponding to rejection sampling produced signatures in order to ensure that they follow a distribution that is independent of the secret key. This rejection sampling is only feasible when the output distribution is sufficiently wide, limiting how compact this type of signature schemes can be. In this work, we develop a new method to construct lattice signatures with the “Fiat-Shamir with aborts” approach. By constructing signatures in a way that is influenced by the rejection condition, we can significantly lower the rejection probability. This allows our scheme to use an iterative rejection sampling to target narrower output distributions than previous methods, resulting in much more compact signatures. In the most compact variant of our new signature scheme, the combined size of a signature and a verification key is less than half of that for ML-DSA and comparable to that of compact hash-and-sign lattice signature schemes, such as Falcon. Alternatively, by targeting a somewhat wider distribution, the rejection condition of the scheme can be securely ignored. This non-aborting variant of our scheme still retains a notable size advantage over previous lattice-based Fiat-Shamir schemes.

Regev recently introduced a quantum factoring algorithm that may be perceived as a d-dimensional variation of Shor’s factoring algorithm. In this work, we extend Regev’s factoring algorithm to an algorithm for computing discrete logarithms in a natural way. Furthermore, we discuss natural extensions of Regev’s factoring algorithm to order finding, and to factoring completely via order finding. For all of these algorithms, we discuss various practical implementation considerations, including in particular the robustness of the post-processing.

Most of the previous attacks on Dilithium exploit side-channel information which is leaked during the computation of the polynomial multiplication cs1, where s1 is a small-norm secret and c is a verifier's challenge. In this paper, we present a new attack utilizing leakage during secret key unpacking in the signing algorithm. The unpacking is also used in other post-quantum cryptographic algorithms, including Kyber, because inputs and outputs of their API functions are byte arrays. Exploiting leakage during unpacking is more challenging than exploiting leakage during the computation of cs1 since c varies for each signing, while the unpacked secret key remains constant. Therefore, post-processing is required in the latter case to recover a full secret key. We present two variants of post-processing. In the first one, a half of the coefficients of the secret s1 and the error s2 is recovered by profiled deep learning-assisted power analysis and the rest is derived by solving linear equations based on t = As1 + s2, where A and t are parts of the public key. This case assumes knowledge of the least significant bits of t, t0. The second variant uses lattice reduction to derive s1 without the knowledge of t0. However, it needs a larger portion of s1 to be recovered by power analysis. We evaluate both variants on an ARM Cortex-M4 implementation of Dilithium-2. The experiments show that the attack assuming the knowledge of t0 can recover s1 from a single trace captured from a different from profiling device with a non-negligible probability.

CRYSTALS-Kyber has been selected by the NIST as a public-key encryption and key encapsulation mechanism to be standardized. It is also included in the NSA's suite of cryptographic algorithms recommended for national security systems. This makes it important to evaluate the resistance of CRYSTALS-Kyber's implementations to side-channel attacks. The unprotected and first-order masked software implementations have been already analysed. In this paper, we present deep learning-based message recovery attacks on the omega-order masked implementations of CRYSTALS-Kyber in ARM Cortex-M4 CPU for omega <= 5. The main contribution is a new neural network training method called recursive learning. In the attack on an omega-order masked implementation, we start training from an artificially constructed neural network M-omega whose weights are partly copied from a model M omega-1 trained on the (omega - 1)-order masked implementation, and then extended to one more share. Such a method allows us to train neural networks that can recover a message bit with the probability above 99% from high-order masked implementations.

A famous reduction by Regev shows that random instances of the Learning With Errors (LWE) problem are asymptotically at least as hard as a worst-case lattice problem. As such, by assuming that standard lattice problems are hard to solve, the asymptotic security of cryptosystems based on the LWE problem is guaranteed. However, it has not been clear to which extent, if any, this reduction provides support for the security of present concrete parametrizations. In this work we therefore use Regev’s reduction to parametrize a cryptosystem, providing a reference as to what parameters are required to actually claim security from this reduction. This requires us to account for the concrete performance of this reduction, allowing the first parametrization of a cryptosystem that is provably secure based only on a conservative hardness estimate for a standard lattice problem. Even though we attempt to optimize the reduction, our system still requires significantly larger parameters than typical LWE-based cryptosystems, highlighting the significant gap between parameters that are used in practice and those for which worst-case reductions actually are applicable.

Lattice-based cryptosystems are some of the primary post-quantum secure alternatives to the asymmetric cryptography that is used today. These lattice-based cryptosystems typically rely on the hardness of some version of either the NTRU or the LWE problem. In this paper, we present the NTWE problem, a natural combination of the NTRU and LWE problems, and construct a new lattice-based cryptosystem based on the hardness of the NTWE problem. As with the NTRU and LWE problems, the NTWE problem naturally corresponds to a problem in a q-ary lattice. This allows the hardness of the NTWE problem to be estimated in the same way as it is estimated for the LWE and NTRU problems. We parametrize our cryptosystem from such a hardness estimate and the resulting scheme has performance that is competitive with that of typical lattice-based schemes. In some sense, our NTWE-based cryptosystem can be seen as a less structured and more compact version of a cryptosystem based on the module-NTRU problem. Thus, parameters for our cryptosystem can be selected with the flexibility of a module-LWE-based scheme, while other properties of our system are more similar to those in an NTRU-based system.