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

Contact author: alessiocaminata87 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190510:122626 (All versions of this report)

Short URL: ia.cr/2019/464


[ Cryptology ePrint archive ]