Paper 2026/527

QR-UOV without Rejection Sampling: Security Analysis and High-Speed Implementation

Abstract

QR-UOV is a multivariate signature scheme derived from UOV that achieves compact public keys by exploiting quotient-ring structure, making it a promising candidate for post-quantum digital signatures. In QR-UOV, most parts of the public map are derived from the public key seed using a PRG. This public key expansion for QR-UOV includes rejection sampling to generate coefficients uniformly over $\mathbb{F}_q$, since QR-UOV uses a small odd-prime base field. However, this rejection sampling introduces extra data movement and irregular control flow. For the recommended parameter set, public-key expansion accounts for nearly 90% of the QR-UOV verification time. In this paper, we propose No Rejection Sampling (NoRS) QR-UOV, a variant of QR-UOV with rejection-sampling-free public-key expansion, which leaves the generation of secret-dependent coefficients unchanged. Concretely, the rejected value $q$ is deterministically mapped to $0$, which simplifies coefficient generation but introduces a slight bias in the resulting coefficient distribution. We evaluate the security impact of this modification through both theoretical and concrete analyses. Our results suggest that, for the proposed parameter sets, NoRS QR-UOV maintains the claimed security levels against the considered attacks. On the implementation side, we develop a high-speed implementation of NoRS QR-UOV for x86 processors with AES-NI and AVX2. Benchmark results on a Skylake platform show that NoRS consistently accelerates QR-UOV at all security levels, with the largest gain in signature verification. Under standard Round-2 parameter settings, benchmark results show that NoRS QR-UOV reduces the verification cost from $0.43$ to $0.30$ Mcycles at security level I, with comparable improvements at security levels III and V, corresponding to about $1.4\times$ speedup over standard QR-UOV. Overall, the results suggest that relaxing coefficient uniformity in public-key expansion is a practical and effective design choice for QR-UOV.