Optimization of digital signature calculation and verification operations for the FIPS 205 standard

Abstract

Currently, significant efforts at the international and national levels are focused on the creation of practical quantum-resistant digital signature (DS) mechanisms. The first round of the international PQC competition has been conducted [1], which resulted in the creation and standardization of the finalists of the 3rd round of the competition, recommended as international standards, as US federal standards, in particular FIPS 205, a stateless digital signature standard based on a hash function (SPHINCS+ algorithm).

A hash-based signature is one of the most promising candidates (and perhaps the most conservative approach) for a post-quantum digital signature. The advantage of hash-based signatures is that their (classical and quantum) security strength is better understood (and easier to evaluate) than other candidates relying solely on the idealized strength of cryptographic hash functions.

The signature scheme standardized in FIPS 205 is constructed using other hash-based signature schemes as components: a few-time signature scheme, forest of random subsets (FORS), and a multi-time signature scheme, the eXtended Merkle Signature Scheme (XMSS).

The standard defines a DS scheme designed to withstand future quantum and classical quantum computer attacks that threaten the security of existing standards. Since the algorithm has already been standardized, an important task is to study its structure and practical implementation of the requirements for its components: parameter construction, key pair generation, DS production and verification, etc. Its solution depends to a large extent on improving the algorithm in terms of execution complexity (speed), which can be reduced to optimizing basic operations.

In this article, we consider and propose practical improvements to optimize the DS for the FIPS 205 algorithm based on the use of parallel computing. This is achieved mainly by optimizing the SHAKE256, SHA256, and SHA512 algorithms. The importance of optimizing the calculation of hash values is related to the fact that hashing is the main operation in FIPS 205.

The results obtained indicate the feasibility and relevance of the improvements made. Optimization provides a minimum speedup of 10% for all operations and all parameters.