Paper 2026/1451

Lightweight Hardware Accelerator for the UOV Signature Scheme with Oil Space Blinding

Abstract

In reaction to the emerging quantum threat, the National Institute of Standards and Technology (NIST) seeks post-quantum secure digital signature schemes. NIST's ongoing competition recently advanced to the third round, in which the Unbalanced Oil and Vinegar scheme (UOV) is a promising candidate due to UOV's conservative design, small signatures, and performant signing and verification. While these benefits make UOV attractive, the implementation aspects for compact hardware acceleration of UOV remain underexplored. Existing hardware accelerators optimize for performance and have large memory footprints. Yet, constrained devices require compact and low-memory hardware support. At the same time, lowering the memory consumption of UOV without sacrificing performance is challenging due to UOV's large public keys and intermediate results. In addition, low-end devices are prone to power side-channel attacks and benefit from lightweight countermeasures. In this work, we focus on the open challenges of compact UOV hardware acceleration. We design a low-memory UOV architecture with runtime-flexible support of NIST security levels 1 to 5. Our architecture uses a load-balanced 16-lane datapath supporting the critical matrix operations of UOV. In addition, we lower UOV's peak memory consumption using a slicing technique and enable on-the-fly data generation via streamlined data realignment. We also include a pipelined Gaussian Elimination unit and a streaming approach for the large public keys needed for signature verification. In addition to compact hardware acceleration, we defend against differential power analysis attacks through a lightweight blinding countermeasure relying on UOV's equivalent keys. Our blinding requires random non-singular matrices, which are not trivial to sample efficiently in hardware. We therefore assess existing sampling approaches and propose a novel technique based on the lower-upper decomposition of matrices. The resulting blinding solely re-uses existing datapath components and limits the runtime overhead to less than 30%. Compared to existing UOV accelerators, our efficient FPGA design reaches up to 5.1x lower signing and 3.2x lower verification latency, while reducing the memory consumption between 2.2x and 16x.