The Generating Series of Support Minors MinRank Ideals

Daniel Smith-Tone

Paper 2023/1456

The Generating Series of Support Minors MinRank Ideals

Daniel Smith-Tone

, National Institute of Standards and Technology, University of Louisville

Abstract

The support minors method has become indispensable to cryptanalysts in attacking various post-quantum cryptosystems in the areas of multivariate cryptography and rank-based cryptography. The complexity analysis for support minors minrank calculations is a bit messy, with no closed form for the Hilbert series of the ideal generated by the support minors equations (or, more correctly, for the quotient of the polynomial ring by this ideal). In this article, we provide a generating series whose coefficients are the Hilbert Series of related MinRank ideals. This simple series therefore reflects and relates the structure of all support minors ideals. Its simplicity also makes it practically useful in computing the complexity of support minors instances.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Multivariate Cryptography Rank-Based Cryptography Hilbert Series MinRank
Contact author(s): daniel smith @ nist gov
History: 2023-09-24: approved; 2023-09-22: received; See all versions
Short URL: https://ia.cr/2023/1456
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1456,
      author = {Daniel Smith-Tone},
      title = {The Generating Series of Support Minors {MinRank} Ideals},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1456},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1456}
}