Paper 2026/1409

Accelerating FAEST Signing on GPU via Fused AES Constraint Generation and Batched Leaf Hashing

Abstract

FAEST is a symmetric-key post-quantum digital signature scheme and a third-round candidate in the NIST Additional Digital Signatures standardization process. Its signing path concentrates cost in two operations: round-wise constraint generation, which proves in zero knowledge that the AES circuit is computed correctly, and finite-field multiplication, which computes the leaf nodes of a vector commitment. This paper accelerates both operations on a CUDA-enabled GPU, with AES round constraint generation as the main contribution. Specifically, we fuse the three consecutive stages that make up constraint generation into a fused GPU path and keep the intermediate results between stages resident in device memory, thereby reducing host–device data transfer. As a supporting measure, we batch independent finite-field multiplications for leaf nodes, jointly improving end-to-end signing performance. We verify the correctness of the implementation through byte-level output agreement with the CPU reference implementation. Combining fused constraint generation with batched leaf hashing, the full GPU path achieves up to roughly a 3× end-to-end signing speedup over the CPU reference. Furthermore, when AES constraint generation fusion is added on top of leaf hashing that is already performed on the GPU, an additional reduction in signing latency is observed in five of the six evaluated AES s/f variants. The magnitude of this effect does not scale monotonically with the security parameter; rather, it is determined by the per-variant bottleneck structure.