Evaluation and comparison of lattice-based digital signature of the "Digital Signature Schemes" PQC NIST competition

Abstract

Over the past decade, post-quantum cryptography has reached a tipping point; institutional bodies and stakeholders have initiated standardization and deployment, and various projects have achieved a reasonably high level of progress and even deployment and implementation. In July 2022, at the end of Round 3 of the NIST's PQC competition, 3 candidates were proposed for the NIST standardization for post-quantum digital signatures scheme: one signature scheme based on MLWE (Crystals-Dilithium), one signature based on NTRU (Falcon), and one signature based on hash (Sphincs+). Although the performance profiles and “black-box” security of these schemes are well understood, resistance to side-channel attacks remains a weak point for all of them. After that, the NIST announced that the PQC standardization process is continuing with a fourth round, with the following KEMs still under consideration: BIKE, Classic McEliece, HQC, and SIKE. However, there are no candidates of digital signature schemes left for consideration. As such, the NIST has issued a call for additional digital signature proposals to be considered in the PQC standardization process. Acceptance of documents ended on June 1, 2023. As a result, 40 candidates were selected for the role of DS standard, namely: 6 DS algorithms based on codes, one DS algorithm based on isogenies, 7 DS algorithms based on lattice operations, 7 candidates for the role of DS algorithm based on the MPC method -in-the-Head and 10 algorithms based on multivariate transformations, 4 DS schemes were selected based on symmetric cryptographic transformations, and 5 more candidates based on other types of cryptographic transformations. The NIST is primarily interested in additional general purpose signature schemes that are not based on structured lattices. For certain applications, such as certificate transparency, the NIST may also be interested in signature schemes that have short signatures and fast verification. The NIST is open to receiving additional materials based on structured lattices, but intends to diversify post-quantum signature standards. Therefore, any structured array-based signature proposal would need to significantly outperform CRYSTALS-Dilithium and FALCON in relevant applications and/or provide significant additional security properties to be considered for standardization. Thus, the purpose of this paper is to analyze, evaluate, and compare digital signature algorithms based on lattice cryptography, an additional PQC NIST competition, and compare them with already standardized lattice-based DS mechanisms, such as CRYSTALS-Dilithium and FALCON.