Cryptology ePrint Archive: Report 2021/1611

Solving degree, last fall degree, and related invariants

Alessio Caminata and Elisa Gorla

Abstract: In this paper we study and relate several invariants connected to the solving degree of a polynomial system. This provides a rigorous framework for estimating the complexity of solving a system of polynomial equations via Groebner bases methods. Our main results include a connection between the solving degree and the last fall degree and one between the degree of regularity and the Castelnuovo--Mumford regularity.

Category / Keywords: public-key cryptography / degree of regularity, Castelnuovo--Mumford regularity, Groebner bases, last fall degree, solving degree

Date: received 10 Dec 2021

Contact author: caminata at dima unige it

Available format(s): PDF | BibTeX Citation

Version: 20211210:165538 (All versions of this report)

Short URL: ia.cr/2021/1611


[ Cryptology ePrint archive ]