Newer variants of the Fujisaki–Okamoto transformation are used in most candidates of the third round of the NIST Post-Quantum Cryptography standardization call in the category of public key encryption schemes. These transformations are applied to obtain a highly secure key encapsulation mechanism from a less secure public key encryption scheme. Furthermore, there are five candidates (three finalists and two alternatives) that passed to the third round of the process and whose security is based in lattice problems. This work analyzes the different ways in which the lattice-based candidates of the NIST call apply the Fujisaki–Okamoto transformation and the particularities of each application. The study of such differences and their repercussion in the design of the proposals will allow a better understanding of the algorithms. Moreover, we propose a modification of the Kyber algorithm—the only public key encryption candidate established as a PQC standard by NIST in its more recent publication—in order to avoid the re-encryption in the decapsulation algorithm and, in this way, to reduce the side channel attacks vulnerability.
Newer variants of the Fujisaki–Okamoto transformation are used in most candidates of the third round of the NIST Post-Quantum Cryptography standardization call in the category of public key encryption schemes. These transformations are applied to obtain a highly secure key encapsulation mechanism from a less secure public key encryption scheme. Furthermore, there are five candidates (three finalists and two alternatives) that passed to the third round of the process and whose security is based in lattice problems. This work analyzes the different ways in which the lattice-based candidates of the NIST call apply the Fujisaki–Okamoto transformation and the particularities of each application. The study of such differences and their repercussion in the design of the proposals will allow a better understanding of the algorithms. Moreover, we propose a modification of the Kyber algorithm—the only public key encryption candidate established as a PQC standard by NIST in its more recent publication—in order to avoid the re-encryption in the decapsulation algorithm and, in this way, to reduce the side channel attacks vulnerability.
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.
In this paper, we rethink the ciphertext equality check step of the decapsulation procedure of Saber, which is one out of four KEM finalists in the third round NIST PQC standardization process. Through this investigation, we pursue cryptographic answers to some important questions. Those are why the re-encryption process of Fujisaki-Okamoto transformation, which is commonly used method to satisfy IND-CCA security in most existing lattice-based KEM algorithms including Saber, is especially necessary in the case of Saber, whether the re-encryption process can be further simplified, and whether the ciphertext equality check must be performed over the entire (re-encrypted/originally received) ciphertexts?
Public-key cryptography is an indispensable component used in almost all of our present-day digital infrastructure. However, most if not all of it is predominantly built upon hardness guarantees of number theoretic problems that can be broken by large-scale quantum computers in the future. Sensing the imminent threat from continued advances in quantum computing, NIST has recently initiated a global-level standardization process for quantum resistant public-key cryptographic primitives such as public-key encryption, digital signatures, and key encapsulation mechanisms. While the process received proposals from various categories of post-quantum cryptography, lattice-based cryptography features most prominently among all the submissions. Lattice-based cryptography offers a very attractive alternative to traditional public-key cryptography mainly due to the variety of lattice-based schemes offering varying flavors of security and efficiency guarantees. In this article, we survey the evolution of lattice-based key-sharing schemes (public-key encryption and key encapsulation schemes) and cover various aspects ranging from theoretical security guarantees, general algorithmic frameworks, practical implementation aspects, and physical attack security, with special focus on lattice-based key-sharing schemes competing in the NIST’s standardization process.
Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS - Cryptographic Suite for Algebraic Lattices - a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NEWHOPE KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki-Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of postquantum security.
Recent developments in quantum computing have shed light on the shortcomings of the conventional public cryptosystem. Even while Shor's algorithm cannot yet be implemented on quantum computers, it indicates that asymmetric key encryption will not be practicable or secure in the near future. The National Institute of Standards and Technology (NIST) has started looking for a post-quantum encryption algorithm that is resistant to the development of future quantum computers as a response to this security concern. The current focus is on standardizing asymmetric cryptography that should be impenetrable by a quantum computer. This has become increasingly important in recent years. Currently, the process of standardizing asymmetric cryptography is coming very close to being finished. This study evaluated the performance of two post-quantum cryptography (PQC) algorithms, both of which were selected as NIST fourth-round finalists. The research assessed the key generation, encapsulation, and decapsulation operations, providing insights into their efficiency and suitability for real-world applications. Further research and standardization efforts are required to enable secure and efficient post-quantum encryption. When selecting appropriate post-quantum encryption algorithms for specific applications, factors such as security levels, performance requirements, key sizes, and platform compatibility should be taken into account. This paper provides helpful insight for post-quantum cryptography researchers and practitioners, assisting in the decision-making process for selecting appropriate algorithms to protect confidential data in the age of quantum computing.
Measuring the security of cryptographic systems is not a simple task. Nevertheless, there is an increasing need for a cryptographic metric which could assist in decision making when choosing between various candidates. The National Institute of Standards and Technology (NIST) has launched a process to standardize quantum-resistance public key encryption, key encapsulation and digital signature algorithms. This is NIST’s response to the threat posed by quantum computers against classical public key cryptography. In this paper, we apply a metric taxonomy, produced by earlier studies, to two NIST third round finalist digital signature algorithms Dilithium and Falcon in order to asses the effectiveness and extensiveness of the metric. Although, our results show that clear differences can be found with used metrics, we propose some improvements to them to allow more comprehensive analysis.