Paper 2026/2272

Attacking UOV-based Signatures over divided power algebras

Peigen Li, Beijing Institute of Mathematical Sciences and Applications
Siyong Tao, Department of Mathematical Sciences, Tsinghua University
Abstract

We introduce a family of divided power wedge attacks on UOV-type systems over finite fields of arbitrary characteristic. The construction extends the characteristic-two exterior-algebra construction of Merz and Ran to the $p$-truncated polynomial ring, where $p$ is the field characteristic. An attack level controls which divided-power relations are adjoined, balancing a lower solving degree against increased average Macaulay row weight. These relations remain in the ideal defining the hidden oil space and can remove extraneous kernel elements, including those obstructing the classical attack when $v\geq 2m$, where $v$ and $m$ denote the numbers of vinegar variables and public equations. We establish an oil-space recovery criterion and use conjectural Hilbert-series predictions to estimate solving degrees and attack costs. A multigraded extension accommodates lifted SNOVA systems. We evaluate the framework on UOV, MAYO, QR-UOV, and SNOVA. Relative to the comparison baselines reported in this paper, our conditional estimates yield reductions of $2$ bits for three UOV parameter sets, $3$--$14$ bits for selected additional MAYO parameter sets, and $2$--$24$ bits for three selected additional SNOVA parameter sets. No improvement is obtained for the QR-UOV parameter sets studied.

Note: We improve our previous attack. The resulting level-r divided power wedge attack reduces the estimated attack complexity for selected parameter sets of UOV, MAYO, and SNOVA submitted to the third round of NIST’s standardization process for additional digital signatures.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
UOV; divided power algebra; wegde attack
Contact author(s)
lpg22 @ bimsa cn
taosy22 @ mails tsinghua edu cn
History
2026-11-14: revised
2026-09-30: received
See all versions
Short URL
https://ia.cr/2026/2272
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2272,
      author = {Peigen Li and Siyong Tao},
      title = {Attacking {UOV}-based Signatures over divided power algebras},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2272},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2272}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.