Hybrid Parallel SHA-3 and its Applications to Fiat-Shamir with Aborts Signatures

Abstract

The SHA-3 functions are widely adopted in post-quantum cryptographic algorithms, yet their computation often constitutes a major performance bottleneck in these schemes. Although a variety of post-quantum cryptographic algorithms are designed to exploit the parallel processing capabilities of SIMD-accelerated SHA-3 on modern processors, the computation of SHA-3 can still account for up to 80% of the total execution time in certain schemes, such as ML-DSA, a Fiat-Shamir with Aborts signature standardized by NIST. In this work, we present a novel perspective on the optimization of SHA-3 implementations by introducing two computation modes, namely, the Hybrid SHA-3 mode and the Synchronous Squeezing and Absorbing mode. The proposed modes substantially enhance both the utilization and flexibility of parallel SHA-3 operations. Furthermore, we present a method to effectively integrate these modes into Fiat-Shamir with Aborts signatures, allowing the computation of challenges to be leveraged for the generation of the polynomial vector y in subsequent rounds. We apply these techniques to ML-DSA and HAETAE. Compared to existing implementations, our optimizations achieve speedups of 10.83%–19.92% for Sign and 14.72%–18.05% for Verify in ML-DSA with AVX2.