Paper 2026/527

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

Hiroki Furue, NTT (Japan)

Rei Ueno, Kyoto University, Tohoku University

Naofumi Homma, Tohoku University

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 constructed by extending the public key seed using 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, which removes rejection sampling from public-key expansion and 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 indicate that, for the proposed parameter sets, NoRS QR-UOV preserves the claimed security levels. 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. For the AES-128-based implementation, the verification cost is reduced from $0.43$ to $0.30$ Mcycles at security level I, with similar improvements at levels III and V, corresponding to about $1.4\times$ speedup. Overall, the results suggest that relaxing coefficient uniformity in public-key expansion is a practical and effective design choice for QR-UOV.

@misc{cryptoeprint:2026/527,
      author = {Hiroshi Amagasa and Hiroki Furue and Rei Ueno and Naofumi Homma},
      title = {{QR}-{UOV} without Rejection Sampling: Security Analysis and High-Speed Implementation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/527},
      year = {2026},
      url = {https://eprint.iacr.org/2026/527}
}