Quantum computing and quantum computers have been discussed for almost three decades. However, they remain mainly in theory. Almost all big companies like Google, IBM, and Microsoft have put their effort to build the most scalable quantum computers in recent years. These computers can change the game in cryptography since the known hard problems such as integer factorization and discrete logarithms can be broken with a large-scale quantum computer. These computers would seriously jeopardize the confidentiality and integrity of all digital communications. The question of when large-scale quantum computers will be built is still an open question. There are some educated predictions that sufficiently large quantum computers will be built to break all public-key schemes currently in use within the next ten or so years. That is why the National Institute of Standards and Technology (NIST) has announced a standardization process in 2016 to prepare our information security systems to be able to resist in quantum computing. The first two rounds of this process have been completed, and there are seven on-going candidates and eight alternate candidates. Among these 15 schemes, seven of them are based on lattices. In this thesis, we study the efficient implementation of lattice-based schemes. We first propose an efficient and compact variant of NEWHOPE, one of the most efficient second-round candidates of the NIST post-quantum standardization project. The proposed algorithm NEWHOPE-COMPACT heavily uses recent advances on Number vii Theoretic Transform (NTT), so that transformation from one polynomial to another is easy. To make it possible, we changed the definition of a component in componentwise multiplication during polynomial multiplication and show that changing the security level only requires to change the size of the polynomial and the definition of a component. Then, we present various optimizations for lattice-based KEMs using the NTT on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polynomial multiplications, and more aggressive layer merging in the NTT, but also in the form of reduced stack usage. We test our optimizations in software implementations of KYBER, one of the round three candidates in the NIST post-quantum project, NEWHOPE, and NEWHOPE-COMPACT.
Quantum computing and quantum computers have been discussed for almost three decades. However, they remain mainly in theory. Almost all big companies like Google, IBM, and Microsoft have put their effort to build the most scalable quantum computers in recent years. These computers can change the game in cryptography since the known hard problems such as integer factorization and discrete logarithms can be broken with a large-scale quantum computer. These computers would seriously jeopardize the confidentiality and integrity of all digital communications. The question of when large-scale quantum computers will be built is still an open question. There are some educated predictions that sufficiently large quantum computers will be built to break all public-key schemes currently in use within the next ten or so years. That is why the National Institute of Standards and Technology (NIST) has announced a standardization process in 2016 to prepare our information security systems to be able to resist in quantum computing. The first two rounds of this process have been completed, and there are seven on-going candidates and eight alternate candidates. Among these 15 schemes, seven of them are based on lattices. In this thesis, we study the efficient implementation of lattice-based schemes. We first propose an efficient and compact variant of NEWHOPE, one of the most efficient second-round candidates of the NIST post-quantum standardization project. The proposed algorithm NEWHOPE-COMPACT heavily uses recent advances on Number vii Theoretic Transform (NTT), so that transformation from one polynomial to another is easy. To make it possible, we changed the definition of a component in componentwise multiplication during polynomial multiplication and show that changing the security level only requires to change the size of the polynomial and the definition of a component. Then, we present various optimizations for lattice-based KEMs using the NTT on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polynomial multiplications, and more aggressive layer merging in the NTT, but also in the form of reduced stack usage. We test our optimizations in software implementations of KYBER, one of the round three candidates in the NIST post-quantum project, NEWHOPE, and NEWHOPE-COMPACT.
The security of most widely used public-key cryptography is fundamentally based on two computationally intractable problems: the integer factorization problem and the elliptic-curve discrete logarithm problem. However, these problems can be solved easily in polynomial time with the help of large-scale quantum computers using Shor's, Proos and Zalka's algorithm. Post-quantum cryptography provides schemes based on hard problems that are hard-to-solve not only by adversaries with classical computers but also by adversaries with large-scale quantum computers. Lattice-based cryptography is a branch of post-quantum cryptography consisting of schemes based on hard lattice problems. The National Institute of Standards and Technology (NIST) recently published the first set of standard post-quantum schemes. Kyber and HQC are the standard key-encapsulation mechanism/public-key encryption schemes, whereas Dilithium, Sphincs+, and Falcon are the standard digital signature algorithms. Although NIST's selection of the first set of post-quantum cryptographic standards is one of the most significant steps toward the transition from classical public-key cryptography to post-quantum cryptography, the field of post-quantum cryptography is still in a nascent stage compared to the decade-old classical public-key cryptography, such as RSA or ECDSA. Therefore, a major focus of this thesis is to bridge the gap between the theory and practice of post-quantum cryptography by exploring various problems that arise during the real-world deployment of post-quantum cryptography. Specifically, I focus on improving the practicality of lattice-based cryptography by proposing new efficient schemes, designing lightweight post-quantum schemes suitable for resource-constrained devices, efficient implementations, analyzing practical physical attacks on implementations of the post-quantum schemes, and designing their countermeasures to thwart the attacks. The first area of research of this dissertation is the exploration of various design choices for lattice-based key-encapsulation mechanisms to make them suitable in different environments under various operational constraints such as memory, silicon area, execution time, power requirement, etc. In our first contribution, we have explored various design choices for lattice-based key-encapsulation mechanisms, focusing on improving execution time on various hardware and software platforms. Our first design, Scabbard, is a suite of three key-encapsulation mechanisms that improved the state-of-the-art post-quantum key-encapsulation mechanism designs by reducing execution time, stack memory requirements, and/or area footprint. In our second contribution, we performed another design space exploration based on hardware resources (such as block RAM, distributed RAM, look-up tables, etc.) estimation and proposed the lattice-based key-encapsulation mechanism, Rudraksh, for resource-constrained devices. We also substantiate our claim of its usefulness with real-world implementations on an FPGA. The second area of research of this dissertation is the analysis of physical attacks. This attack analysis is essential when the attacker can access a device that executes cryptographic implementations, and such scenarios occur frequently in real-world deployments. Therefore, this is a crucial problem to address before deploying post-quantum cryptographic schemes in real-world applications, and countermeasures against physical attacks need to be developed as a prevention measure. In our third contribution, we proposed side-channel attack-resistant masked implementations of lattice-based KEM, Saber KEM, one of the NIST finalist KEMs. We showed that masked Saber outperforms the state-of-the-art masked implementations of Kyber, one of the NIST standards. Our investigations show that this is largely due to power-of-two moduli. Our final contribution to this thesis is physical attack analyses on implementations of the standard key-encapsulation mechanism Kyber. We proposed a cross-attack, fault-injection attack on the masked implementation of Kyber. We showed that the exploited vulnerability was introduced due to the algorithmic change caused by masking.
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.
Digital signatures ensure authenticity and data integrity and are widely utilized in various fields such as information technologies, finance, education, and law. They are crucial in securing servers against cyber attacks by authenticating connections between clients and servers. Additionally, encryption is used in many areas, such as secure communication, cloud, server and database security to ensure data confidentiality. Public-key cryptosystems are widely used as digital signature and encryption mechanisms. The security of public-key cryptosystems is based on difficult mathematical problems such as the integer factorization problem and the discrete logarithm problem. Security of the public-key cryptosystems is based on solving challenging mathematical problems like the discrete logarithm and integer factorization problems. P. Shor (1999) has shown that high-capacity quantum computers can be used to break cryptosystems whose security depends on solving the discrete logarithm problem and the integer factorization problem. The post-quantum standardization procedure has been organized by NIST (National Institute of Standards and Technology, USA) to replace cryptographic algorithms that will lose their security with the next-generation quantum-secure algorithms. Following this procedure, Crystals Dilithium, Falcon, and SPHINCS+ are chosen as the digital signature standards, and Crystals Kyber is chosen as the encryption/KEM standard. This work focuses on efficient batch signature generation with Dilithium, batch verification of signatures from the same user using Crystals Dilithium (NIST's post-quantum digital signature standard), and batch encryption to a single user with Crystals Kyber (NIST's post-quantum encryption/KEM standard). One of the main operations of Dilithium and Kyber is the matrix-vector product with polynomial entries. So, the naive approach to generate/verify m signatures with Dilithium (or encrypt m messages with Kyber) where m>1 is to perform m such multiplications. In this thesis, we propose to use efficient matrix multiplications of sizes greater than three to generate/verify m signatures with Dilithium and greater than two to encrypt m messages with Kyber. To this end, Dilithium signature generation, verification, and Kyber encryption algorithms are analyzed. In this study, individual operations for multiple messages or signatures are redesigned to allow for batch processing. For this purpose, the matrix-vector multiplications contained in these algorithms are converted into matrix-matrix multiplications, and the new batch Dilithium signature generation/verification and batch Kyber encryption algorithms are designed. Furthermore, it is shown that the efficient batch Dilithium signature generation algorithm can be used for the generation of a single signature. This is confirmed through probability and efficiency analyses. New batch algorithms have components that ensure the security of the original Dilithium and Kyber and allow batch signing/verification and encryption without causing security vulnerabilities. By transforming matrix-vector multiplications into matrix-matrix multiplications, efficient non-commutative or commutative matrix-matrix multiplication algorithms are allowed to be used in these systems. The efficiency achieved is independent of any specific architecture, device, or platform and is based on mathematical improvements. The designed batch algorithms provide the opportunity to select any batch size and apply the suitable matrix-matrix multiplication technique. In this context, probability computations are made for the usability of the Dilithium signature algorithm in both multiple and single signatures according to various batch sizes, and efficiency percentages are obtained based on the selected matrix-matrix multiplication techniques. Furthermore, improvement percentages provided by batch Kyber encryption and Dilithium verification are computed via matrix-matrix multiplication methods appropriate for changing batch sizes. To exemplify the theoretical calculations made, sample batch values are selected, and suitable matrix-matrix multiplication methods are determined. According to the dimensions of the matrices, multiplication formulas are derived for three security levels of Dilithium and Kyber. To test the calculations, the batch Dilithium signing, verification, and Kyber encryption algorithms designed within this study are implemented in the C programming language. The derived matrix-matrix multiplication formulas are also implemented in C to fit the infrastructure of Kyber and Dilithium and integrated into the batch algorithms. Efficiency comparisons are made between the new algorithms and reference algorithms. As a result, improvements up to 28.1%, 33.3%, and 31.5% in the arithmetic complexities are observed at three different security levels of Dilithium's signature, respectively. The batch Dilithium signature algorithm with an efficient matrix-multiplication method provides 34.22%, 17.40%, and 10.15% improvements on CPU cycle counts for three security levels. The multiplication formulas used for batch Dilithium signature generation are also applied for batch Dilithium verification. At three different levels of security, improvements in the arithmetic complexity are observed of up to 28.13%, 33.33%, and 31.25%. Furthermore, 49.88%, 56.60%, and 61.08% improvements on CPU cycle counts for three security levels are achieved, respectively. As a result of implementing Kyber Batch Encryption with efficient multiplication algorithms, 12.50%, 22.22%, and 28.13% improvements on arithmetic complexity, as well as 22.34%, 24.07%, and 30.83% improvements on CPU cycle counts, are observed for three security levels.
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.
Current cryptographic solutions used in information technologies today like Transport Layer Security utilize algorithms with underlying computationally difficult problems to solve. With the ongoing research and development of quantum computers, these same computationally difficult problems become solvable within reasonable (polynomial) time. The emergence of large-scale quantum computers would put the integrity and confidentiality of today’s data in jeopardy. It then becomes urgent to develop, implement, and test a new suite of cyber security measures against attacks from a quantum computer. This thesis explores, understands, and evaluates this new category of cryptosystems as well as the many tradeoffs among them. All the algorithms submitted to the National Institute of Standards and Technology (NIST) for standardization can be categorized into three major categories, each relating to the new underlying hard problem: namely error code correcting, algebraic lattices (including ring learning with errors), and super singular isogenies. These new mathematical hard problems have shown to be resistant to the same type of quantum attack. Utilizing hardware clock cycle registers such as RDTSC on x86 architecture and CCNT on ARM architectures, the work sets up the benchmarks of the four Round 3 NIST algorithms in two environments: cloud computing and embedded system. In addition, security levels of each algorithm is analyzed with varying key sizes to highlight tradeoffs. Results show a significant decrease in performance on embedded systems, revealing the aspects of each algorithm such as key pair generation that should be reduced due to performance. As expected, there are many tradeoffs and advantages for certain applications in each algorithm. Saber and Kyber are exceedingly fast but have larger ciphertext size for transmission over a wire. McEliece key size and key generation are the largest drawbacks but having the smallest ciphertext size and only slightly decreased performance allow a use case where key reuse is prioritized. NTRU finds a middle ground in these tradeoffs, being better than McEliece performance wise and better than Kyber and Saber in ciphertext size allows for a use case of highly varied environments, which need to value speed and ciphertext size equally. Going forward, the benchmarking system developed could be applied to digital signature, another vital aspect to a cryptosystem.
Not only is quantum computing a game changer but it is also an unprecedented threat to world security in cyberspace. Although quantum systems are expected to transform scientific computing, they are also endangering the very notion of classical cryptography, specifically, the public key system of RSA and elliptic curve cryptography (ECC). The problems in computation that such schemes are built on, including integer factorization and discrete logarithms, can be efficiently solved using quantum algorithms, including Shor. This makes the secured communication network by classical encryption susceptible to quantum attacks in the future. In turn, current quantum-resistant or post-quantum cryptographic algorithms (PQC) are resistant to classical and quantum adversaries. The article provides a general overview of significant families of PQC, such as lattice-based, code-based, multivariate polynomial, hash-based and isogeny-based, and discusses their relevance to the provisioning of communication networks. The work illuminates to some degree the advances toward standardization already being undertaken by the National Institute of Standards and Technology (NIST) by analysing its security underpinnings, trade-offs in its operation and its readiness to deploy. Experiments show that lattice based (CRYSTALS-Kyber, Dilithium) and code based (McEliece) are both well-theoretically secure as well as high performance, and that systems based on code (McEliece) have a long track record of reliability at the cost of large key-sizes. Other issues which have been talked about in the paper are interoperability issues, migration policies and side-channel attack defence. It finds conclusively that quantum-resistant cryptography is the next step that must be regarded as the most important to secure the secrecy and integrity of communication networks in the future.