Cryptology ePrint Archive: Report 2017/593

Solving Multivariate Polynomial Systems and an Invariant from Commutative Algebra

Alessio Caminata and Elisa Gorla

Abstract: The security of several post-quantum cryptosystems is based on the assumption that solving a system of multivariate (quadratic) polynomial equations $p_1=\dots=p_r=0$ over a finite field is hard. Such a system can be solved by computing a lexicographic Gr\"obner basis of the ideal $(p_1,\dots,p_r)$. The most efficient algorithms for computing Gr\"obner bases transform the problem into several instances of Gaussian elimination. The computational complexity of these algorithms is not completely understood, especially when the polynomials $p_1,\dots,p_r$ are not homogeneous. In this paper, we prove that this complexity is controlled by the Castelnuovo-Mumford regularity of the ideal $(p_1^h,\dots,p_r^h)$ obtained by homogenizing the input polynomials. This allows us to bound the complexity of solving a system of polynomial equations when the associated ideal is zero-dimensional, a common situation in cryptography. In combination with some theorems in commutative algebra, our results also allow us to bound the complexity of the ABC and cubic simple matrix schemes, as well as some instances of the MinRank Problem.

Category / Keywords: solving degree; degree of regularity; Castelnuovo-Mumford regularity; Gr\"obner basis; multivariate cryptography; post-quantum cryptography

Date: received 20 Jun 2017, last revised 30 Mar 2018

Contact author: alessiocaminata87 at gmail com

Available format(s): PDF | BibTeX Citation

Note: Improved introduction and exposition, added Theorem 2.10, reorganized Section 3, shortened Section 5. Main results unaffected.

Version: 20180330:171642 (All versions of this report)

Short URL: ia.cr/2017/593

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]