Efficient Batch Post-quantum Signatures with Crystals Dilithium

Date

2025-01-01

Author

Türe, Nazlı Deniz
Cenk, Murat

Metadata

Show full item record

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

Item Usage Stats

26
views

0
downloads

Cite This

Digital signatures ensure authenticity and secure communication. They are used to verify the integrity and authenticity of signed documents and are widely utilized in various fields such as information technologies, finance, education, and law. They are crucial in securing servers against cyberattacks and authenticating connections between clients and servers. Performing multiple signature generation simultaneously and efficiently is highlighted as a beneficial approach for many systems. This work focuses on efficient batch signature generation using Crystal Dilithium, NIST’s post-quantum digital signature standard. One of the main operations of signature generation using Dilithium is the matrix-vector product with polynomial entries. So, the naive approach to generate m signatures where m>1 is to perform m such multiplications. In this paper, we propose to use efficient matrix multiplications of sizes greater than four to generate m signatures. To this end, a batch algorithm that transforms the polynomial matrix-vector multiplication in Dilithium’s structure into polynomial matrix-matrix multiplication is designed. The batch numbers and the sizes of the matrices to be multiplied based on the number of repetitions of Dilithium’s signature algorithm are determined. Moreover, many efficient matrix-matrix multiplication algorithms, such as Strassen-like multiplications and commutative matrix multiplications, are analyzed to design the best algorithms that are compatible with the specified dimensions and yield improvements. Various multiplication formulas are derived for different security levels of Dilithium, and improvements up to 27.28%, 32.0%, and 30.31% in the arithmetic complexities are observed at three different security levels, respectively. The proposed batch Dilithium signature algorithm and the efficient multiplication algorithms are also implemented, and 34.22%, 17.40%, and 10.15% improvements on CPU cycle counts for three security levels are obtained.

Subject Keywords

Batch Digital Signature Generation, Commutative Matrix Multiplication, Crystals Dilithium, Digital Signature, Multiple Signing, Post-Quantum Cryptography

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=105000419558&origin=inward
https://hdl.handle.net/11511/114240

Collections

Graduate School of Applied Mathematics, Conference / Seminar