Round 2 (Additional Signatures) OFFICIAL COMMENT: QR-UOV

255 views

Skip to first unread message

Shingo Orihara

unread,

Jan 20, 2026, 2:16:44 AMJan 20

to pqc-forum

Dear all,

While the proposed algorithm in "Just Guess: Improved (Quantum) Algorithm for the Underdetermined MQ Problem" [1] improves attacks on certain MQ schemes, our analysis shows that it does not outperform the best known attacks for the main QR-UOV parameter sets with q = 127 across all security levels. Consequently, the proposed algorithm has no impact on the security of these QR-UOV parameters.

In [1], the authors estimate the complexity of their proposed algorithm for QR-UOV. We noticed, however, that the analysis does not include our main parameter set with q=127.

To complement their results, we estimate the complexity of the proposed attack for the main parameters of QR-UOV and summarize our findings in the table below. The table adopts the same format as in the original paper, presenting the estimated complexities of classical and quantum modeling attacks alongside Hashimoto's algorithm [2] for comparison.

Full-Just-Guess-Solver [1]
security   (n,m,q)        k   p   Classical Quantum
Level I    (210,54,127)   34 11 256(243)   136(123)
Level III (306,78,127)   54 13 398(383)   207(193)
Level V    (411,105,127) 77 15 560(544)   289(274)

Hashimoto's algorithm [2]
security   (n,m,q)        Classical Quantum
Level I    (210,54,127) 158        129
Level III (306,78,127) 217        179
Level V    (411,105,127) 285        234

For Full-Just-Guess-Solver, (k, p) are the optimal parameters that minimize classic and quantum runtime complexity. The complexities without polynomial overhead are provided in parentheses.

Based on these estimates, we observe that the proposed attack does not appear to be efficient for the main parameters of QR-UOV.

[1] Alexander May, Massimo Ostuzzi, and Henrik Ressler. "Just Guess: Improved (Quantum) Algorithm for the Underdetermined MQ Problem." https://eprint.iacr.org/2025/1788.pdf (2025)

[2] Yasufumi Hashimoto. "An improvement of algorithms to solve under-defined systems of multivariate quadratic equations." JSIAM Lett. 15: 53-56 (2023)