On the complexity of solving generic overdetermined bilinear systems

John B. Baena; Daniel Cabarcas; Javier Verbel

doi:10.3934/amc.2021047

Article Contents

2023, Volume 17, Issue 5: 1210-1234. Doi: 10.3934/amc.2021047

This issue Previous Article On one-lee weight and two-lee weight $ \mathbb{Z}_2\mathbb{Z}_4[u] $ additive codes and their constructions Next Article Vandermonde sets, hyperovals and Niho bent functions

On the complexity of solving generic overdetermined bilinear systems

1.
Universidad Nacional de Colombia Sede Medellín, Carrera 65 Nro. 59A - 110, Medellín, Colombia
2.
Cryptography Research Centre, Technology Innovation Institute, P.O. Box 9639, Masdar City, Abu Dhabi, United Arab Emirates

^* Corresponding author: Javier Verbel (javier.verbel@tii.ae)
^* Corresponding author: Javier Verbel (javier.verbel@tii.ae)

Received: May 2021

Revised: July 2021

Early access: October 2021

Published: October 2023

Abstract Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by

Abstract

In this paper, we study the complexity of solving overdetermined generic systems of bilinear polynomials over a finite field $ \mathbb{F} $. Given a generic bilinear sequence $ B\in \mathbb{F}[ \textbf{x}, \textbf{y}] $, with respect to a partition of variables $ \textbf{x} $, $ \textbf{y} $, we show that, the solutions of the system $ B = \textbf{0} $ can be efficiently found on the $ \mathbb{F}[ \textbf{y}] $-module generated by $ B $. Following this observation, we define notions of regularity for overdetermined bilinear systems, and we conjecture that they are generic properties. Also, we propose three variations of Gröbner basis algorithms, that only involve multiplication by monomials in the $ \textbf{y} $-variables, namely, $ \textbf{y} $-XL, based on the XL algorithm, $ \textbf{y} $-MXL, based on the mutant XL algorithm, and $ \textbf{y} $-HXL, based on a hybrid approach. We develop the necessary theoretical tools to estimate the complexity of the algorithms for such sequences. We present experimental evidence for testing our conjecture, verifying our results, and comparing the complexity of the various methods. Based on the experimental data, we can conclude that $ \textbf{y} $-MXL outperforms F4 on bilinear systems.

Keywords:

Mathematics Subject Classification: Primary: 13P15, 94A60, 15A03, 68W30, 14G50; Secondary: 13P10, 14Q20.

Citation:

Full Text(HTML)

Table 1. Experimental results to verify Conjecture 1. Here we use $ n_x = 4 $, the column $ \% $ shows the percentage of times the chosen sequence $ B \in \mathcal{B}^{(h)}(n_x,n_y,m) \subset \mathbb{F}_{13}[x_1,\ldots,x_{n_x},y_1,\ldots,y_{n_y}] $ was $ \textbf{y} $-semiregular, and $ \tilde{d} $, which is equal to $ \lceil n_x(n_y-1)/(m-n_x)\rceil +1 $, indicates the $ \textbf{y} $-degree of regularity according to Proposition 3

$ n_y $	$ m $	$ \tilde{d} $	$ \% $	$ n_y $	$ m $	$ \tilde{d} $	$ \% $	$ n_y $	$ m $	$ \tilde{d} $	$ \% $
4	8	4	88	5	18	3	100	7	17	3	100
	9	4	100	6	10	5	99		18	3	100
	10	3	93		11	4	100		19	3	100
	11	3	100		12	4	100		20	3	100
	12	3	100		13	4	100		21	3	100
	13	3	100		14	3	92		22	3	100
	14	3	100		15	3	100	8	12	5	98
	15	3	99		16	3	100		13	5	100
	16	2	93		17	3	100		14	4	100
5	9	5	99		18	3	100		15	4	100
	10	4	100		19	3	100		16	4	100
	11	4	100		20	3	100		17	4	100
	12	3	90	7	11	5	100		18	3	92
	13	3	100		12	4	86		19	3	100
	14	3	100		13	4	100		20	3	100
	15	3	100		14	4	100		21	3	100
	16	3	100		15	4	100		22	3	100
	17	3	100		16	3	88		23	3	100

| Show Table

DownLoad: CSV

Table 2. Comparison between the solving degrees for $ \textbf{y} $-XL, $ \textbf{y} $-MXL and F4, the $ \textbf{y} $-first fall degree and the first fall degree of a sequence $ B \in \mathcal{B}(4,n_y,m) $ chosen uniformly at random over $ \mathbb{F}_{13} $

$ n_y $	$ m $	$ T_{ff} $	$ T_{wit} $	$ d_{ \textbf{y}-ff} $	$ \textbf{y} $-XL$ _{sol} $	$ \textbf{y} $-MXL$ _{sol} $	F4$ _{ff} $	F4$ _{sol} $
4	10	4	5	4 (0.93)	5 (0.89)	4 (1.0)	4 (0.87)	4 (0.99)
	11	3	5	3 (1.0)	5 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)
	12	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	13	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	14	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	15	3	3	3 (1.0)	3 (0.89)	3 (1.0)	3 (1.0)	3 (1.0)
	16	3	3	3 (1.0)	3 (1.0)	3 (1.0)	3 (0.89)	3 (1.0)
5	11	4	6	4 (1.0)	6 (0.98)	4 (0.98)	4 (1.0)	4 (1.0)
	12	4	5	4 (0.95)	5 (1.0)	4 (1.0)	4 (0.96)	4 (1.0)
	13	3	5	3 (1.0)	5 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)
	14	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	15	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	16	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	17	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	18	3	3	3 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
6	12	4	6	4 (1.0)	6 (0.99)	4 (0.99)	4 (1.0)	4 (1.0)
	13	4	5	4 (1.0)	5 (1.0)	4 (1.0)	4 (1.0)	4 (1.0)
	14	4	5	4 (0.94)	5 (1.0)	4 (1.0)	4 (0.95)	4 (1.0)
	15	3	4	3 (1.0)	4 (0.95)	4 (1.0)	3 (1.0)	3 (1.0)
	16	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	17	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	18	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	19	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	20	3	3	3 (1.0)	3 (0.95)	3 (1.0)	3 (1.0)	3 (1.0)

| Show Table

DownLoad: CSV

Table 3. Complement of Table 2

$ n_y $	$ m $	$ T_{ff} $	$ T_{wit} $	$ d_{ \textbf{y}-ff}(B) $	$ \textbf{y} $-XL$ _{sol} $	$ \textbf{y} $-MXL$ _{sol} $	F4$ _{ff} $	F4$ _{sol} $
7	13	4	6	4 (1.0)	6 (1.0)	5 (1.0)	4 (1.0)	4 (1.0)
	14	4	5	4 (1.0)	5 (1.0)	4 (1.0)	4 (1.0)	4 (1.0)
	15	4	5	4 (1.0)	5 (1.0)	4 (1.0)	4 (1.0)	4 (1.0)
	16	4	5	4 (0.94)	5 (1.0)	4 (1.0)	4 (0.95)	4 (1.0)
	17	3	4	3 (1.0)	4 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)
	18	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	19	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	20	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	21	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	22	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
8	14	4	6	4 (1.0)	6 (1.0)	5 (1.0)	4 (1.0)	4 (1.0)
	15	4	5	4 (1.0)	5 (0.9)	4 (1.0)	4 (1.0)	4 (1.0)
	16	4	5	4 (1.0)	5 (1.0)	4 (1.0)	4 (1.0)	4 (1.0)
	17	4	5	4 (1.0)	5 (1.0)	4 (1.0)	4 (1.0)	4 (1.0)
	18	4	5	4 (0.91)	5 (1.0)	4 (1.0)	4 (0.92)	4 (1.0)
	19	3	4	3 (1.0)	4 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)
	20	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	21	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	22	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	23	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)
	24	3	4	3 (1.0)	4 (1.0)	3 (1.0)	3 (1.0)	3 (1.0)

| Show Table

DownLoad: CSV

Algorithm 2 $ \textbf{y} $-HXL$ _{a_x,a_y} $

1: function $ \textbf{y} $-HXL$ _{a_x,a_y} $ $ B $       ▷ Where $ B \in \mathcal{B}(n_x,n_y,m) $}
2:      $ d = \left\lceil \frac{(n_y-a_y)(n_x - a_x+1)}{m-n_x +a_x-1} \right\rceil +1 $
3:      $ \textbf{e} = \begin{pmatrix} 0 & \cdots & 0 & 1 \end{pmatrix} \in \mathbb{F}_{q}^{n_x \binom{n_y + d -1}{d -1}} $
4:      for $ (\textbf{u}, \textbf{v}) \in \mathbb{F}_{q} ^{a_x}\times \mathbb{F} _{q}^{a_y} $ do
5:：     if $ \textbf{z} \cdot \textbf{M}_{ \textbf{y},\leq d}\left(B_ {(\textbf{u},\textbf{v})}\right) = \textbf{e} $ is inconsistent then
6:           return $ (\textbf{u},\textbf{v}) $
7:       end if
8:    end for
9: end function

| Show Table

DownLoad: CSV

Table 5. Complexity estimates for $ \textbf{y} $-MXL and $ \textbf{y} $-HXL$ _{a_x,a_y} $ for $ n_x = 20 $, $ n_y = 20,30 $ and different values of $ q $ and $ m $

$ n_y $	20						30
$ q $	$ m $	$ MXL $	$ a_x $	$ a_y $	$ HXL $	$ Alg $	$ m $	$ MXL $	$ a_x $	$ a_y $	$ HXL $	$ Alg $
5	42	110	19	0	59	S	52	136	20	0	61	S
	46	101	19	0	59	S	56	128	20	0	61	S
	50	94	19	0	60	S	60	119	20	0	61	S
	54	90	20	0	60	W	64	115	19	0	61	S
	58	86	20	0	60	W	68	110	19	0	61	S
	62	82	20	0	60	W	72	106	19	0	61	S
13	42	110	19	0	85	S	52	136	20	0	89	S
	46	101	19	0	86	S	56	128	20	0	89	S
	50	94	2	1	86	W	60	119	20	0	89	S
	54	90	3	0	80	W	64	115	19	0	87	S
	58	86	3	0	77	W	68	110	19	0	87	S
	62	82	2	0	74	W	72	106	19	0	87	S
31	42	110	3	0	98	W	52	136	20	0	114	S
	46	101	1	0	92	W	56	128	1	0	110	W
	50	94	1	0	87	W	60	119	1	0	104	W
	54	90	1	0	82	W	64	115	1	0	101	W
	58	86	1	0	79	W	68	110	0	1	97	W
	62	82	1	0	76	W	72	106	0	1	94	W

| Show Table

DownLoad: CSV

Table 4. Comparison between the largest Macaulay matrix used in F4 (Fmc) and the largest $ \textbf{y} $-Macaulay matrix used in $ \textbf{y} $-MXL (Mmc), on a random bilinear system, with $ B \in \mathcal{B}(n_x = 4,n_y,m) $ over $ \mathbb{F}_{13} $. Here, $ d_{reg} $ is the largest step degree in F4

$ n_y $	$ m $	$ d_{reg} $	$ \textbf{y} $-MXL$ _{sol} $	Fmc	Mmc	$ n_y $	$ m $	$ d_{reg} $	$ \textbf{y} $-MXL$ _{sol} $	Fmc	Mmc
4	10	4	4	276	140	6	20	3	3	205	112
	11	3	4	161	140	7	13	4	5	1020	1320
	12	3	3	159	60		14	4	4	1047	480
	13	3	3	157	60		15	4	4	770	480
	14	3	3	117	60		16	4	4	730	480
	15	3	3	119	60		17	3	4	321	480
	16	3	3	120	60		18	3	3	359	144
5	11	4	4	422	224		19	3	3	356	144
	12	4	4	395	224		20	3	3	354	144
	13	3	4	217	224		21	3	3	255	144
	14	3	3	215	84		22	3	3	255	144
	15	3	3	212	84	8	14	4	5	1368	1980
	16	3	3	160	84		15	4	4	1449	660
	17	3	3	160	84		16	4	4	1429	660
	18	3	3	158	84		17	4	4	1015	660
6	12	4	4	739	336		18	4	4	955	660
	13	4	4	579	336		19	3	4	412	660
	14	4	4	550	336		20	3	3	380	180
	15	3	4	248	336		21	3	3	447	180
	16	3	3	280	112		22	3	3	446	180
	17	3	3	278	112		23	3	3	444	180
	18	3	3	277	112		24	3	3	310	180

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. Bardet, Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie, Université Pierre et Marie Curie - Paris VI, 2004, https://tel.archives-ouvertes.fr/tel-00449609.
[2]	M. Bardet, M. Bros, D. Cabarcas, P. Gaborit, R. Perlner, D. Smith-Tone, J.-P. Tillich and J. Verbel, Improvements of algebraic attacks for solving the rank decoding and MinRank problems, Advances in Cryptology – ASIACRYPT 2020, (eds. S. Moriai and H. Wang), Springer International Publishing, Cham, (2020), 507–536.
[3]	M. Bardet, J.-C. Faugère, B. Salvy and P.-J. Spaenlehauer, On the complexity of solving quadratic Boolean systems, Journal of Complexity, 29 (2013), 53-75. doi: 10.1016/j.jco.2012.07.001.
[4]	M. Bardet, J.-C. Faugère, B. Salvy and B. Yang, Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems, IN MEGA '05, Eighth International Symposium on Effective Methods in Algebraic Geometry, 2005.
[5]	D. J. Bernstein and B.-Y. Yang, Asymptotically faster quantum algorithms to solve multivariate quadratic equations, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 10786 (2018), 487-506. doi: 10.1007/978-3-319-79063-3_23.
[6]	L. Bettale, J.-C. Faugère and L. Perret, Hybrid approach for solving multivariate systems over finite fields, J. Math. Cryptol., 3 (2009), 177-197. doi: 10.1515/JMC.2009.009.
[7]	L. Bettale, J.-C. Faugère and L. Perret, Solving polynomial systems over finite fields: Improved analysis of the hybrid approach, ISSAC 2012 Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ACM, New York, (2012), 67–74. doi: 10.1145/2442829.2442843.
[8]	B. Buchberger, Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, J. Symbolic Computation, 41 (2006), 475-511. doi: 10.1016/j.jsc.2005.09.007.
[9]	J. Buchmann, D. Cabarcas, J. Ding and M. S. E. Mohamed, Flexible partial enlargement to accelerate Gröbner basis computation over $\mathbb{F}_{2}$, Progress in Cryptology – AFRICACRYPT, Springer Berlin Heidelberg, Berlin, Heidelberg, (eds. D. J. Bernstein and T. Lange), (2010), 69–81.
[10]	D. Cabarcas, Gröbner Bases Computation and Mutant Polynomials, PhD thesis, University of Cincinnati, 2011.
[11]	D. Cabarcas, D. Smith-Tone and J. A. Verbel, Key recovery attack for ZHFE, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 10346 (2017), 289-308. doi: 10.1007/978-3-319-59879-6.
[12]	S. Cohen and C. Tomasi, Systems of Bilinear Equations, Technical report, Stanford University, Stanford, CA, USA, 1997.
[13]	N. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in Cryptology: EUROCRYPT 2000 (Bruges), Lecture Notes in Comput. Sci., Springer, Berlin, 1807 (2000), 392-407. doi: 10.1007/3-540-45539-6_27.
[14]	D. A. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, (Undergraduate Texts in Mathematics), 3$^{nd}$ edition, Undergraduate Texts in Mathematics, Springer, New York, 2007. doi: 10.1007/978-0-387-35651-8.
[15]	J. Ding and D. Schmidt, Solving degree and degree of regularity for polynomial systems over a finite fields, Number Theory and Cryptography, Lecture Notes in Comput. Sci., 8260, Springer, Heidelberg, (2013), 34–49. doi: 10.1007/978-3-642-42001-6_4.
[16]	J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139 (1999), 61-88. doi: 10.1016/S0022-4049(99)00005-5.
[17]	J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, (2002), 75–83. doi: 10.1145/780506.780516.
[18]	J.-C. Faugère, K. Horan, M. Kahrobaei Delaram, M. Kaplan, E. Kashefi and L. Perret, Quantum algorithm for solving multivariate quadratic equations, IACR Cryptology ePrint Archive, 2017 (2017), 1236.
[19]	J.-C. Faugère, M. Safey El Din and P.-J. Spaenlehauer, Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity, J. Symbolic Comput., 46 (2011), 406-437. doi: 10.1016/j.jsc.2010.10.014.
[20]	J.-C. Faugère, P.-J. Spaenlehauer and J. Svartz, Sparse Gröbner bases: The unmixed case, ISSAC 2014: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, (2014), 178–185. doi: 10.1145/2608628.2608663.
[21]	C. R. Johnson and J. A. Link, Solution theory for complete bilinear systems of equations, Numer. Linear Algebra Appl., 16 (2009), 929-934. doi: 10.1002/nla.676.
[22]	A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Advances in Cryptology – CRYPTO 99, 1666, Springer, Berlin, 1999, 19–30. doi: 10.1007/3-540-48405-1_2.
[23]	D. Lazard, Gröbner-bases, Gaussian elimination and resolution of systems of algebraic equations, Computer Algebra, EUROCAL, European Computer Algebra, 162 (1983), 146-156. doi: 10.1007/3-540-12868-9_99.
[24]	M. S. E. Mohamed, W. S. A. E. Mohamed, J. Ding and J. Buchmann, MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 5299, 2008,203–215. doi: 10.1007/978-3-540-88403-3_14.
[25]	J. Vates and D. Smith-Tone, Key recovery attack for all parameters of HFE-, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 10346 (2017), 272-288. doi: 10.1007/978-3-319-59879-6_16.
[26]	J. Verbel, J. Baena, D. Cabarcas, R. Perlner and D. Smith-Tone, On the complexity of "superdetermined'' minRank instances, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, (eds. J. Ding and R. Steinwandt), 11505 (2019), 167–186. doi: 10.1007/978-3-030-25510-7_10.
[27]	L. A. Vinh, On the solvability of systems of bilinear equations in finite fields, Proc. Amer. Math. Soc., 137 (2009), 2889–2898. https://arXiv.org/abs/0903.1156. doi: 10.1090/S0002-9939-09-09947-X.
[28]	D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory, 32 (1986), 54-62. doi: 10.1109/TIT.1986.1057137.
[29]	D. Yang, Solution Theory for Systems of Bilinear Equations, Ph.D thesis, College of William and Mary, 2011.