Article Contents
Article Contents
Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

# On the complexity of solving generic overdetermined bilinear systems

• 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.

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

 Citation:

• 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

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)

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)
 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

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

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
•  [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.

Tables(6)