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

Abstract

The FIPS205 standard is fully hash-based signature algorithm: its security does not rely on numerical problems (factorization, discrete logarithms) or algebraic structures (lattices, codes), but only on the standard properties of cryptographic hash functions, in particular keyed hashes and PRF constructions based on these hash functions. The main mathematical constructions of the standard are Merkle trees (hash trees), hypertrees (tree-of-trees constructions), and combinatorial multi-signatures that sign a set of small indices.

The advantages of building a digital signature scheme based on such components are post-quantum resistance based on conservative assumptions, statelessness, and small key sizes. However, computational complexity remains a weakness of the FIPS205 algorithm and the respective reference algorithm SPHINCS+. This is due to the mathematics used. Signature generation involves a large number of hash computations (FORS, dozens of WOTS chains, many hashes for trees). This process is slower than the mathematics of most signature schemes. However, as shown in previous work, this can be improved using optimization.

Previous articles have considered and proposed practical improvements in order to optimize the digital signature formation process for the FIPS 205 algorithm. Previous works have discussed the possibilities of increasing the performance of the FIPS 205 algorithm by eliminating common calculations, using a special input format for hash calculations, and parallel calculations by using threads. This work is a extension of previous works. It additionally increases the performance of algorithms for key generation, signature generation, and signature verification based on the FIPS 205 standard. The results obtained can be applied to any signature scheme similar to FIPS 205.

This paper considers the use of AVX commands for hash calculation using the example of SHA256 and SHA512 functions, as well as their use in the implementation of various algorithm schemes, namely one-time signature schemes, extended Merkle trees, hypertrees, and forests. The article compares the optimization results obtained by the authors of SPHINCS+ and this work in the context of using AVX commands. This work is of great importance, since virtually all modern processors are capable of executing AVX commands and are multi-core and multi-threaded.

The results show that by optimizing algorithms and using AVX, we got a significant speed boost for all operations. For key pair generation, we got a speed boost of 7.76–8.35 times for STORE mode and 2.5–3.93 times for FAST mode. Signature generation was accelerated by almost 10 times for STORE mode and 1.87–3.99 times for FAST mode, while signature verification was accelerated by at least 1.4 times for STORE mode and 27% for FAST mode.

The results obtained are quite promising and show that the use of parallel computing on multi-core processors significantly increases the performance of functions for WOTS, XMSS, and FORS schemes, as well as the functions that use them.