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 3 Jun 2019

Contact author: alessio caminata at unine ch

Available format(s): PDF | BibTeX Citation

Note: Corrected a typo in the formula of the main theorem.

Version: 20190603:133348 (All versions of this report)

Short URL: ia.cr/2019/464


[ Cryptology ePrint archive ]