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.
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.
The rapid advancement of quantum computing poses a fundamental threat to classical cryptographic mechanisms that underpin modern digital security. Shor’s algorithm can efficiently solve integer factorization and discrete logarithm problems, thereby breaking widely used public-key cryptosystems such as RSA, ECC, and Diffie–Hellman. Grover’s algorithm also reduces the effective security of symmetric encryption and hash functions by half. This paper provides a systematic analysis of the impact of quantum attacks on current cryptographic infrastructures, including TLS, digital signatures, and blockchain. We then review the state of post-quantum cryptography (PQC) as standardized by NIST, focusing on three leading candidates: CRYSTALS-Kyber for key encapsulation, and CRYSTALS-Dilithium and FALCON for digital signatures. Through simulation using the Open Quantum Safe (liboqs) library on a standard x86_64 platform, we measure key generation time, encryption/signing speed, decryption/verification latency, and key/signature sizes. Our results show that Kyber-768 achieves key generation in <0.1 ms and produces public keys of about 1.2 KB, while Dilithium-3 generates signatures of ~2.7 KB with verification times under 0.3 ms. Compared to RSA-2048 and ECDSA-P256, PQC algorithms offer competitive performance at the cost of larger key and signature sizes. Based on these findings, we propose a hybrid transition roadmap that combines classical and PQC algorithms in parallel, minimizing risk while maintaining backward compatibility. The paper concludes that organizations should begin immediate preparations for the post-quantum era, especially for data requiring long-term confidentiality.
The National Institute of Standards and Technology (NIST) has recently concluded the third round of its Post Quantum Cryptography Standardization Process, selecting four finalist algorithms for standardization: CRYSTALS Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+. These algorithms are designed to withstand attacks from both classical and quantum computers, ensuring the long-term security of digital communications. This paper presents a comprehensive comparative analysis of the security margins and practical deployment readiness of these finalist algorithms. CRYSTALS-Kyber, a key encapsulation mechanism based on the hardness of the Module Learning With Errors problem, offers strong security and efficient performance. CRYSTALS-Dilithium, a digital signature algorithm based on module lattices, provides robust security guarantees and relatively straightforward implementation. FALCON, a lattice-based digital signature algorithm utilizing the Fast Fourier Transform, offers compact signatures and fast verification but faces implementation challenges due to its reliance on floating-point arithmetic. SPHINCS+, a hash-based signature scheme, stands out as a conservative choice with security based solely on the well-established security of hash functions. The analysis reveals that while each algorithm has its strengths, they also face unique challenges in terms of side-channel vulnerabilities, formal security proofs, and performance trade-offs. The practical deployment of these algorithms requires careful consideration of specific security requirements, performance needs, and resource constraints. Ongoing research efforts aim to enhance the algorithms' resistance against advanced attacks, optimize their performance across diverse platforms, and develop standardized and secure hybrid cryptographic systems. The transition to post-quantum cryptography will involve challenges such as interoperability with legacy systems, the need for clear standards and regulatory guidance, and the costs associated with software and hardware updates. Continued engagement with the cryptographic community and monitoring of the evolving security landscape will be crucial for ensuring a secure and effective migration to post-quantum cryptography.
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.
As the advent of quantum computing threatens traditional cryptographic protocols, hybrid classical-quantum secure communication infrastructures have emerged as a critical frontier in cybersecurity. This paper explores the integration of post-quantum cryptographic algorithms—specifically CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium for digital signatures—into hybrid communication architectures designed to resist quantum-level attacks. Leveraging lattice-based cryptographic primitives, both algorithms have been selected for standardization by NIST due to their robust security and performance characteristics. This study evaluates their implementation in real-world communication stacks, assesses latency and throughput under hybrid channel configurations, and proposes a layered security architecture combining classical and quantum-resilient mechanisms. Furthermore, it examines key management, digital trust, and infrastructure scalability in a post-quantum context. Simulation results and hardware-based validations are used to determine practical deployment feasibility in critical sectors such as finance, defense, and healthcare. The findings offer a comprehensive framework for securing data in transitional computing eras, ensuring forward secrecy, and maintaining operational integrity against future adversarial quantum threats.
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 development of quantum computing technology is progressing very quickly, which poses a great threat to classical cryptographic algorithms like RSA and ECC, as they are based on mathematical problems that can be easily solved using quantum computing technology. To overcome the threat of quantum computing technology, the need for PQC algorithms like CRYSTALS Kyber, CRYSTALS Dilithium, Falcon, and SPHINCS+, which are standardized or recommended by NIST, has become essential in the era of cybersecurity. The feasibility of these algorithms in real time applications is the main focus of this thesis. A mixed approach is adopted for this purpose. Benchmark experiments were performed using the Open Quantum Safe library and PQC enabled OpenSSL for key generation, encryption, decryption, signature generation, signature verification, and TLS handshakes. Simulated environment and cloud environment were used for this purpose. Moreover, case studies were also conducted for cloud computing, financial sector, and IoT applications. Additionally, threat modeling is also performed for assessing the migration risks, i.e., “harvest now decrypt later.” The results indicate that the lattice-based methods, like Kyber and Dilithium, offer a robust trade off in terms of performance and security, albeit with increased key and signature sizes compared to classical methods. Hash based methods, like SPHINCS+, offer robust security, albeit with significant performance and size overheads, indicating that they are best used in specific circumstances. Hybrid approaches, using classical as well as quantum methods, were indicated as viable in the transition from classical to quantum methods, especially in circumstances that require backward compatibility. The paper concludes that NIST standardized PQC algorithms are technically viable for contemporary applications, especially in cloud computing and high-performance computing. However, for large-scale implementation, proper engineering and monitoring of developments in crypt analysis need to be performed. Future research should be directed towards implementation optimization, migration frameworks, and further studies in real-world implementations, especially for resource-constrained IoT and legacy system applications.