Round 2 (Additional Signatures) OFFICIAL COMMENT: UOV, MAYO, SNOVA

[Lars Ran]

Dear all,

As announced at the Rump Session of Eurocrypt this evening I found a new algorithm for solving UOV (and UOV-like systems) in characteristic 2.
The algorithm is based on wedge products and the fact that in characteristic 2 the polar forms are alternating.
For a high level overview of the algorithm you can see the rump-session slides at my homepage.

The algorithm works for (v, o, m)-UOV instances for which the following sum is non-positive

In that case the complexity is equivalent to finding the unique kernel vector of a sparse matrix of size Binomial(v + o, v) with density Binomial(v + 2, 2).

Assuming a cost model in which random memory access is free, the costs for the parameter sets of second round signature schemes in NISTs additional call for signatures can be summarized as follows

Parameter sets not in this list are not affected.

Keep an eye out on eprint the coming month for the full analysis.

Kind regards,

Lars

[Lars Ran]

• 
  
• 
  
• 
  

Dear all,

As a follow-up on my previous post about UOV, MAYO, and SNOVA, the paper with the full analysis is now available on ePrint, and I am happy to share it with you: https://eprint.iacr.org/2025/1143

As pointed out to me by Ray Perlner and Maxime Bros, the UOV-systems in SNOVA are not generic and this might cause problems for the algorithm. I agree with them and think more research is necessary to correctly predict the rank of the matrix M in the case of SNOVA. This means that the algorithm might still work, but it is unclear for what minimal o' <= o, if any. Therefore, I will retract my complexity claim on SNOVA for now.

The updated table of complexities can be found below:

I am happy to answer any questions or comments that you may have, so feel free to contact me.

Kind regards, Lars

Op dinsdag 6 mei 2025 om 23:28:38 UTC+2 schreef Lars Ran: