freenode
Security & Cryptography

New estimates cut MAYO attack costs by as much as 61 bits

For some NIST additional-signature parameter sets, the revised figures sit below the security levels those designs claim.

Peigen Li and Siyong Tao have posted improved cost estimates for attacks on MAYO, a multivariate signature scheme still under consideration in NIST's additional post-quantum signature process, cutting prior figures by 2 to 61 bits. For some of the scheme's extra parameter sets from the third round, the new estimates fall below the benchmarks tied to the security levels those parameters claim.

MAYO is a compact variant of the older Unbalanced Oil and Vinegar construction. Designers and NIST reviewers judge such schemes in part by how expensive the best known algebraic attacks are, measured in bits of work. A drop of tens of bits does not by itself break a deployed system, but it can erase the margin a parameter set was supposed to hold over a target security level.

Writing on NIST's pqc-forum, Li and Tao said their work improves attacks published by Simon-Philipp Merz and Lars Ran. Their construction, using truncated polynomial algebras, extends that approach to fields of odd characteristic more efficiently. A level parameter controls which extra equations enter two algebraic attacks, so an attacker can use fewer equations and sparser matrices and still lower the estimated cost.

Against selected MAYO parameter sets, they put the new costs 2 to 61 bits under the baseline estimates and 2 to 29 bits under the Merz-Ran figures. They said they notified the Mayo team, which acknowledged receipt. On one part of the improvement, the choice of how many extra equations to include, Merz told them he and Ran had already made the same observation around the time their own paper appeared.