Over the last twenty years, lattice-based cryptography has quickly become a central component of modern cryptography. Its most prominent characteristics are (1) its capacity to build cryptographic primitives with powerful functionalities, famously including fully-homomorphic encryption, and (2) its widely-believed resilience against quantum attacks, leading to the currently most prevalent family of candidates for post-quantum cryptography. In this thesis, we further study these two fundamental features of lattice-based cryptography. First, we introduce a new advanced cryptographic primitive, that we call laconic function evaluation, which captures general sender-optimized two-party computation. We build laconic function evaluation from lattice-based assumptions, and show applications to efficient secure multi-party computation. Second, we take a systematic approach to studying post-quantum security of cryptographic protocols. We show that, perhaps surprisingly, post-quantum resilience of a computational assumption does not automatically imply post-quantum security of cryptographic primitives built upon it, including encryption and signature schemes. We do so by exhibiting counter-examples based on lattices. Last, we show that natural interactive protocols from lattices shed light on cryptographic arguments systems, and more specifically the so-called Fiat-Shamir transform. As a byproduct, we uncover a conceptual connection between two families of practical lattice-based signatures.--Author's abstract
Over the last twenty years, lattice-based cryptography has quickly become a central component of modern cryptography. Its most prominent characteristics are (1) its capacity to build cryptographic primitives with powerful functionalities, famously including fully-homomorphic encryption, and (2) its widely-believed resilience against quantum attacks, leading to the currently most prevalent family of candidates for post-quantum cryptography. In this thesis, we further study these two fundamental features of lattice-based cryptography. First, we introduce a new advanced cryptographic primitive, that we call laconic function evaluation, which captures general sender-optimized two-party computation. We build laconic function evaluation from lattice-based assumptions, and show applications to efficient secure multi-party computation. Second, we take a systematic approach to studying post-quantum security of cryptographic protocols. We show that, perhaps surprisingly, post-quantum resilience of a computational assumption does not automatically imply post-quantum security of cryptographic primitives built upon it, including encryption and signature schemes. We do so by exhibiting counter-examples based on lattices. Last, we show that natural interactive protocols from lattices shed light on cryptographic arguments systems, and more specifically the so-called Fiat-Shamir transform. As a byproduct, we uncover a conceptual connection between two families of practical lattice-based signatures.--Author's abstract
Today, lattice-based cryptography is a thriving scientific field. Its swift expansion is due, among others, to the attractiveness of fully homomorphic encryption and cryptographic multilinear maps. Lattice-based cryptography has also been recognized for its thrilling properties: a security that can be reduced to worst-case instances of problems over lattices, a quasi-optimal asymptotic efficiency and an alleged resistance to quantum computers. However, its practical use in real-world products leaves a lot to be desired. This thesis accomplishes a step towards this goal by narrowing the gap between theoretical research and practical implementation of recent public key cryptosystems. In this thesis, we design and implement a lattice-based digital signature, two fully homomorphic encryption schemes and cryptographic multilinear maps. Our highly efficient signature scheme, BLISS, opened the way to implementing lattice-based cryptography on constrained devices and remains as of today a promising primitive for post-quantum cryptography. Our fully homomorphic encryption schemes enjoy competitive homomorphic evaluations of nontrivial circuits. Finally, we describe the first implementation of cryptographic multilinear maps. Based on our implementation, a non interactive key exchange between more than three parties has been realized for the first time, and amounts to a few seconds per party.
The advent of quantum computing poses a significant threat to the security of current asymmetric cryptographic systems, which underpin much of modern digital communication and security. These systems, predominantly RSA and Elliptic Curve Cryptography (ECC), rely on the computational hardness of mathematical problems such as integer factorization and the discrete logarithm problem. Shor's algorithm, a quantum algorithm, demonstrates the ability to efficiently solve these problems, rendering classical public-key cryptography vulnerable to attacks by sufficiently powerful quantum computers. This paper argues for and thoroughly examines the strategic imperative of transitioning from these classical cryptographic foundations to a new paradigm based on lattices, which are believed to be resistant to quantum attacks. We delve into the fundamental mathematical problems underlying lattice-based cryptography, such as the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem, whose worst-case hardness is leveraged to achieve cryptographic security. A comprehensive literature review is provided, tracing the evolution of quantum threats and the emergence of lattice-based schemes. The methodology details the construction principles of prominent lattice-based cryptosystems. Results demonstrate their theoretical security against quantum adversaries and highlight their practical attributes, including compact key sizes and competitive performance. The discussion section contextualizes lattice-based cryptography within the broader landscape of post-quantum candidates, examining their strengths, weaknesses, and the ongoing standardization efforts by organizations like NIST. We conclude that lattice-based cryptography offers a robust and promising foundation for building resilient asymmetric cryptographic systems in the post-quantum era, ensuring the long-term security of digital information through a necessary re-architecture of cryptographic primitives.
The advent of quantum computing poses a significant existential threat to current public-key cryptographic standards, particularly RSA and Elliptic Curve Cryptography (ECC), which underpin global digital security. Shor's algorithm, if implemented on a sufficiently powerful quantum computer, can efficiently break these foundational schemes, rendering vast amounts of encrypted data vulnerable. This paper investigates lattice-based cryptography as a robust and promising candidate for post-quantum security. We provide a comprehensive analysis of its theoretical underpinnings, focusing on hard problems like the Shortest Vector Problem (SVP) and Learning With Errors (LWE), which are believed to be intractable even for quantum adversaries. Through a detailed literature review and methodological exposition, we examine the construction principles of prominent lattice-based Key Encapsulation Mechanisms (KEMs) and digital signature schemes, such as Kyber and Dilithium, highlighting their inherent security properties and performance characteristics. Our results demonstrate that lattice-based schemes offer competitive efficiency, compact key sizes, and strong security guarantees against both classical and quantum attacks, positioning them as essential building blocks for the post-RSA cryptographic landscape. The discussion elaborates on the practical implications, standardization efforts by NIST, and the challenges associated with the transition to quantum-resilient cryptographic infrastructure. We conclude that lattice-based cryptography is a cornerstone of quantum resilience, critical for securing future digital communications and data integrity.
The need and emergence of quantum computing under National Quantum Mission threatens the cyber-security of existing cryptographic protocols, especially public-key schemes built on integer factorization and discrete logarithms. Lattice-based cryptography has gained prominence as a robust candidate for post-quantum cryptography—offering security against quantum attacks while enabling efficient operations, parallelization, and novel functionalities. This paper analyzes the mathematical foundations of lattices, explores hardness assumptions underlying widely studied lattice problems, highlights prominent cryptographic constructions, analyzes performance trade-offs, and reviews standardization efforts. This paper concludes by identifying ongoing issues and future directions for lattice-based cryptographic systems in a quantum-secure digital world. The algorithm has been implemented in Python.
Alongside the growth of technology is the increasing demand for security of data and communication channels. As attacking power grows, devices become smaller and data expands, the security needs to be stronger yet less resource-consuming than ever before. Public key cryptography (PKC) is used in the majority of today's communications systems. The security of public-key cryptographic schemes, such as RSA and elliptic curve cryptography (ECC), is based on underlying mathematical problems such as factoring large integers or solving the discrete log problem. However, the discovery of Shor's Algorithm in 1994 insinuates that these schemes will be insecure when a full-scale quantum computer is developed, as these problems will be solvable in polynomial time. Therefore attention has moved towards post-quantum, or quantum-safe, cryptography (QSC). In 2016, the National Institute of Standards and Technology (NIST) announced the beginning of their efforts to migrate to QSC, a standardisation process which has involved the cryptographic community worldwide. There are five main types of QSC being considered for standardisation; lattice-based, code-based, multivariate-based, hash-based and isogeny-based. Lattice-based cryptography (LBC) offers a promising alternative to today's classical approaches. Hard problems based on lattices are believed to be unsolvable, even by a quantum-computer, in a feasible amount of time. In 1995, Ajtai showed that the average case complexity of these problems is at least as hard as solving the problems in the worst case. Furthermore, lattice-based schemes are the only remaining contender in the NIST process to provide the important primitives of encryption, key encapsulation and digital signature schemes (DSSs). A well-recognised open problem surrounding quantum-safe cryptography is its increase in bandwidth and computational complexity in comparison to existing cryptography. However, in comparison to other quantum-safe schemes, LBC has been shown to be relatively efficient. In this thesis, novel software designs of lattice-based schemes are presented and shown to be competitive with existing PKC. Additionally, physical attacks are considered and countermeasures are incorporated into the designs. DSSs are required for authentication, integrity and non-repudiation of data. This thesis provides an evaluation of three leading signature schemes, BLISS-B, Dilithium and \textsc{Falcon}, which vary in terms of their key features, such as the sampling processes used, and the structure of the lattices. Physical attacks on the three schemes are considered and the effect on performance of appropriate attack countermeasures is evaluated. A novel fault attack on the NIST candidate \textsc{Falcon} is also proposed. A further advantage of LBC is the ability to support cryptographic primitives with extended capabilities to facilitate certificate management and compute on encrypted data. The complexity of today's technology advances mean applications require more sophisticated primitives, which contrastingly are required to run on even smaller platforms. This thesis presents novel quantum-safe advanced cryptographic schemes, specifically lattice-based identity-based encryption (IBE) and hierarchical identity-based encryption (HIBE). IBE removes the need for certificate management, as a user's public key depends on their public identity. IBE is currently used in vital applications such as emergency services communication and so the development of a high-performance quantum-safe alternative is imperative. This thesis also introduces the first scalable HIBE scheme based on lattices. The first HIBE scheme based on structured lattices, Latte, was proposed by the National Centre for Cyber Security (NCSC) in 2017. However, the public key and ciphertext sizes increased with each delegation and hence it was not feasible to scale the algorithm. Skinny Latte, proposed in this thesis, remedies this issue by fixing the dimension of the lattice, thereby making public key and ciphertext sizes constant. This research also shows that it is practical for real-world deployment. Overall, this thesis demonstrates that lattice-based cryptography is practical for real-world applications. It considers both theoretical and physical attacks, and presents novel designs of advanced quantum-safe cryptographic primitives, which have only yet been realised by lattices.
The security of classical public-key cryptosystems, which operate based on the computational intractability of integer factorization and discrete logarithm problems, is profoundly threatened by the rapid development of quantum computing. Post-Quantum Cryptography (PQC) has been proposed to improve security against quantum attacks. Lattice-based cryptography is widely regarded as one of the most promising PQC method because of its proven security, efficient implementation, and functional versatility, and it has achieved significant progress in both algorithmic design and engineering implementation in recent years. This paper presents a systematic survey of the status of research on lattice-based cryptographic algorithms. First, the fundamental theory of lattices and their core hard problems are discussed. Next, the technical characteristics and performance of encryption and key encapsulation mechanisms, digital signature schemes, and key exchange protocols constructed based on lattice hard problems are reviewed and compared. Subsequently, the principles and optimization paths of two key technologies for lattice cryptography implementation, namely polynomial multiplication using the fast Number Theoretic Transform (NTT) and pre-image sampling algorithms, are discussed. Finally, considering the PQC standardization process of the National Institute of Standards and Technology (NIST), an outlook on future research directions for lattice-based cryptography is presented. The research directions include the development of more "succinct" fundamental hard problems, strengthening security proofs, improving algorithm efficiency, and countering novel attacks. This review serves as a reference for promoting the practical deployment and further research of lattice-based cryptography.