Usability of structured lattices for a post-quantum cryptography: practical computations, and a study of some real Kummer extensions

Andrea Lesavourey

Published Jan 1, 2021• 0 citations

Abstract

Lattice-based cryptography is an excellent candidate for post-quantum cryptography, i.e. cryptosystems which are resistant to attacks run on quantum computers. For efficiency reason, most of the constructions explored nowadays are based on structured lattices, such as module lattices or ideal lattices. The security of most constructions can be related to the hardness of retrieving a short element in such lattices, and one does not know yet to what extent these additional structures weaken the cryptosystems. A related problem – which is an extension of a classical problem in computational number theory – called the Short Principal Ideal Problem (or SPIP), consists of finding a short generator of a principal ideal. Its assumed hardness has been used to build some cryptographic schemes. However it has been shown to be solvable in quantum polynomial time over cyclotomic fields, through an attack which uses the Log-unit lattice of the field considered. Later, practical results showed that multiquadratic fields were also weak to this strategy.\nThe main general question that we study in this thesis is To what extent can structured lattices be used to build a post-quantum cryptography?

Related papers

Hardness of Lattice Based Cryptography

Thor Tunge

In this thesis we will discuss hard computational problems in lattice theory and relate them to cryptographic constructions. Many of these problems enjoy average-case hardness which makes them attractive for cryptography. In addition, lattice based cryptography is a candidate for post-quantum cryptography, as there is no known quantum algorithm which breaks various hardness theorems.\n\nWe build a foundation in algebraic number theory to have the required background to discuss schemes based on discrete algebraic structures. These structures are free Z-modules which permits unique factorization in prime ideals. We relate this algebraic number theory to lattices in R^n so we can use the theory from algebra to our advantage.\n\nWe then define some standard hard computational lattice problems and show how many of these are related to each other. We prove that these problems are at least as hard as finding the shortest vector of a lattice, which we conjecture is computationally infeasible. We then prove a quantum reduction the learning with errors problem, a problem in machine learning . We also show that there is a similar reduction for a variant of this problem over more general rings.

Jan 1, 20180 citations

From Number Theory to Lattices: The Post-Quantum Cryptographic Paradigm

Zen Revista, Zen Revista

The landscape of modern cryptography, traditionally anchored in the computational hardness of number-theoretic problems such as integer factorization and the discrete logarithm problem, faces an existential threat from the advent of quantum computing. Shor's algorithm, discovered in 1994, demonstrates the theoretical capability of a sufficiently powerful quantum computer to efficiently solve these problems, rendering widely used cryptographic schemes like RSA and Elliptic Curve Cryptography (ECC) insecure. This imminent threat necessitates a paradigm shift towards post-quantum cryptography (PQC), which aims to develop cryptographic algorithms resistant to both classical and quantum attacks. Among the various candidates for PQC, lattice-based cryptography has emerged as a particularly promising area. This paper provides a comprehensive overview of the transition from classical number theory-based cryptography to lattice-based schemes. We explore the fundamental mathematical principles underlying lattices, introduce key lattice problems such as the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Small Integer Solution (SIS), and Learning With Errors (LWE), and discuss their application in constructing quantum-resistant cryptographic primitives. Furthermore, we analyze the security, efficiency, and practical considerations of prominent lattice-based cryptosystems, highlighting their role in the ongoing NIST post-quantum cryptography standardization process. The paper concludes by discussing the challenges and future directions in the deployment and research of lattice-based cryptographic solutions.

Feb 9, 20260 citations

Lattice - Based Cryptography - Security Foundations and Constructions

Adeline Roux-Langlois

Lattice-based cryptography is a branch of cryptography exploiting the presumed hardness of some well-known problems on lattices. Its main advantages are its simplicity, efficiency, and apparent security against quantum computers. The principle of the security proofs in lattice-based cryptography is to show that attacking a given scheme is at least as hard as solving a particular problem, as the Learning with Errors problem (LWE) or the Small Integer Solution problem (SIS). Then, by showing that those two problems are at least as hard to solve than a hard problem on lattices, presumed polynomial time intractable, we conclude that the constructed scheme is secure.In this thesis, we improve the foundation of the security proofs and build new cryptographic schemes. We study the hardness of the SIS and LWE problems, and of some of their variants on integer rings of cyclotomic fields and on modules on those rings. We show that there is a classical hardness proof for the LWE problem (Regev's prior reduction was quantum), and that the module variants of SIS and LWE are also hard to solve. We also give two new lattice-based group signature schemes, with security based on SIS and LWE. One is the first lattice-based group signature with logarithmic signature size in the number of users. And the other construction allows another functionality, verifier-local revocation. Finally, we improve the size of some parameters in the work on cryptographic multilinear maps of Garg, Gentry and Halevi in 2013.

Jan 1, 20141 citation

Creating a Challenge for Ideal Lattices.

Thomas Plantard, Michael Schneider

Abstract. Lattice-based cryptography is one of the candidates in the area of post-quantum cryptography. Cryptographic schemes with security reductions to hard lattice problems (like the Shortest Vector Problem SVP) offer an alternative to recent number theory-based schemes. In order to guarantee asymptotic efficiency, most lattice-based schemes are instantiated using polynomial rings over integers. These lattices are called ideal lattices. It is assumed that the hardness of lattice problems in lattices over integer rings remains the same as in regular lattices. In order to prove or disprove this assumption, we instantiate random ideal lattices that allow to test algorithms that solve SVP and its approximate version. The Ideal Lattice Challenge allows online submission of short vectors to enter a hall of fame for full comparison. We adjoin a set of first experiments and a first comparison of ideal and regular lattices.

Jan 1, 201314 citations

Hardness of Structured Lattices Problems for Post-Quantum Cryptography

Felderhoff, Joël

The security of cryptographic protocols is based on the presumed difficulty of algorithmic problems. Among those identified so far, some of the best problems to serve as a foundation for quantum-proof cryptography come from lattices. Lattices are a mathematical structure defined as a set of space vectors generated by integer combinations of a finite number of linearly independent real vectors (its basis). A typical example of a related security problem is the Shortest Vector Problem (SVP). Given a base of an n-dimensional lattice, find a non-zero short vector. For efficiency reasons, these problems are restricted to lattices arising from number theory, known as structured lattices. As the security assumptions for these particular lattices are different from those for unstructured lattices, it is necessary to study them specifically, which is the aim of this thesis.We have studied the case of NTRU and uSVP modules in rank 2, proving that the SVP problem is equivalent on these two families of lattices. We also show a worst-case to average-case reduction for rank-2 uSVP lattices. Then we show that solving SVP on a prime ideal of small norm is no easier than solving SVP on any ideal.

Nov 26, 20240 citations

Learning with Errors and Lattice-Based Post-Quantum Public-Key Cryptography

Jaskari, Mikko

The security of conventional public-key cryptography schemes is based on mathematical problems which are considered to be infeasible to solve by classical computers in a reasonable amount of time. However, the rise of quantum computers might break this security in the future. Post-quantum cryptography (PQC) aims to achieve secure schemes which are resistant against attacks assisted by quantum computers. Public-key cryptography refers to asymmetric cryptography in which encryption is done with a public key and decryption is done with a private key. Characteristic properties of public-key cryptography include the possibility to derive the private key from public information by solving some presumably hard problem. The hardness of the problem constitutes the basis for the system's security. In the post-quantum era, the security must be based on problems that are too hard to solve even for quantum computers. In this thesis, we will study lattice-based cryptography which is believed to serve as a good candidate for secure post-quantum public-key cryptography. Our main attention is in the problem of learning with errors, which is in the base of some lattice-based schemes and is linked to the hard problem of finding short vectors in a lattice.

Dec 5, 20250 citations