Hiroshi Amagasa, Rei Ueno, Naofumi Homma

AVX2 Implementation of QR-UOV for Modern x86 Processors

Introduction

Avx2 implementation of qr-uov for modern x86 processors. Accelerate QR-UOV multivariate digital signatures on modern x86 processors using AVX2/AVX-512. Discover software optimization for NIST PQC candidates, achieving significant speedups.

Abstract

QR-UOV is a multivariate signature scheme selected as one of the candidates in the second round of the NIST PQC Additional Digital Signatures process. This paper presents software acceleration methods for QR-UOV optimized for modern x86 architectures. QR-UOV operates over small odd prime-power extension fields such as GF(313) and GF(1273) unlike other multivariate signature candidates. This property allows direct utilization of hardware multipliers for field arithmetic, offering a distinctive advantage for high-performance implementations. Yet, how to implement QR-UOV efficiently on modern CPUs based on the property remains unclear so far. Our implementation benefits from two proposed ideas: (1) reducing the computational overhead of the QR-UOV algorithm through algorithm-level optimization, and (2) leveraging advanced SIMD instruction set extensions (e.g., AVX2, AVX-512) to accelerate main operations such as matrix multiplication. Our implementation achieves substantial speedups over the Round 2 reference: for the parameter set (q, ℓ) = (127, 3) at NIST security level I, it delivers a 5.1x improvement in key generation, 3.6x in signature generation, and 5.7x in signature verification. These results demonstrate that QR-UOV achieves performance comparable or higher than that of UOV implementations, particularly at higher security levels.

Review

The paper "AVX2 Implementation of QR-UOV for Modern x86 Processors" presents a timely and highly relevant contribution to the field of post-quantum cryptography, focusing on the practical viability of the QR-UOV multivariate signature scheme. As a candidate in the NIST PQC Additional Digital Signatures process, the scheme's performance on modern hardware is a critical factor for its potential adoption. The authors correctly identify the unique characteristic of QR-UOV operating over small odd prime-power extension fields, which theoretically offers an advantage for direct hardware multiplier utilization, but note the lack of clarity on how to translate this into efficient CPU implementations. This sets a clear and important objective for the research. To achieve significant performance enhancements, the paper adopts a two-fold optimization strategy. Firstly, it proposes algorithm-level optimizations designed to inherently reduce the computational overhead of the QR-UOV algorithm itself. This demonstrates a deep understanding of the scheme's mathematical underpinnings, seeking efficiency gains beyond mere hardware acceleration. Secondly, and as highlighted by the title, the work effectively exploits advanced SIMD instruction set extensions, particularly AVX2 and AVX-512, to accelerate core arithmetic operations such as matrix multiplication. This thoughtful combination of algorithmic refinement with processor-specific, low-level optimization is crucial for maximizing performance on modern x86 architectures. The practical impact of these optimizations is substantial, as evidenced by the reported speedups over the Round 2 reference implementation. For the (q, ℓ) = (127, 3) parameter set at NIST security level I, the presented implementation achieves a 5.1x improvement in key generation, 3.6x in signature generation, and an impressive 5.7x in signature verification. These are significant gains that directly address the performance concerns surrounding post-quantum schemes. Crucially, the paper concludes that these results place QR-UOV's performance on par with, or even superior to, UOV implementations, especially at higher security levels. This strong performance data significantly bolsters the case for QR-UOV as a competitive and practical candidate within the ongoing NIST standardization efforts.

Full Text

Comments

You need to be logged in to post a comment.