Paper 2026/2272
Attacking UOV-based Signatures over divided power algebras
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
-
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}
}