Cryptology ePrint Archive: Report 2019/464

The complexity of MinRank

Alessio Caminata and Elisa Gorla

Abstract: In this note, we leverage some of our previous results to produce a concise and rigorous proof for the complexity of the generalized MinRank Problem in the under-defined and well-defined case. Our main theorem recovers and extends previous results by Faugère, Safey El Din, Spaenlehauer.

Category / Keywords: public-key cryptography / MinRank Problem; minors; solving degree; Castelnuovo-Mumford regularity; Groebner bases; multivariate cryptography; post-quantum cryptography.

Date: received 6 May 2019, last revised 10 Mar 2022

Contact author: caminata at dima unige it

Available format(s): PDF | BibTeX Citation

Note: Final version. Theorem numbering adjusted to match the published version

Version: 20220310:162746 (All versions of this report)

Short URL: ia.cr/2019/464


[ Cryptology ePrint archive ]