Paper 2025/1599

AVX2 Implementation of QR-UOV for Modern x86 Processors

Rei Ueno, Kyoto University, Tohoku University

Naofumi Homma, Tohoku University

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 $\mathrm{GF}(31^3)$ and $\mathrm{GF}(127^3)$ unlike other multivariate cryptosystem 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 this property remains unclear so far. Our implementation benefits from two proposed optimizations: (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, AVX512) to accelerate main operations such as matrix multiplication. Our implementation achieves substantial speedups over the Round 2 reference: for the parameter set $(q,\ell)=(127,3)$ at NIST security level I, it delivers a $5.1\times$ improvement in key generation, $3.6\times$ in signature generation, and $5.7\times$ in signature verification. These results demonstrate that QR-UOV achieves performance comparable or higher than that of UOV implementations, particularly at higher security levels.

@misc{cryptoeprint:2025/1599,
      author = {Hiroshi Amagasa and Rei Ueno and Naofumi Homma},
      title = {{AVX2} Implementation of {QR}-{UOV} for Modern x86 Processors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1599},
      year = {2025},
      doi = {10.46586/tches.v2026.i2.325-346},
      url = {https://eprint.iacr.org/2025/1599}
}