Efficient Batch Algorithms for the Post-Quantum Crystals Dilithium Signature Scheme and Crystals Kyber Encryption Scheme

Date

2024-9-6

Author

Türe, Nazlı Deniz

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

65
views

0
downloads

Cite This

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.

Subject Keywords

Batch Digital Signature Generation, Post-Quantum Cryptography, Commutative Matrix Multiplication, Crystals Dilithium, Digital Signature, Batch Digital Signature Verification, Crystals Kyber, Batch Encryption

URI

https://hdl.handle.net/11511/112269

Collections

Graduate School of Applied Mathematics, Thesis