\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

On the complexity of solving generic overdetermined bilinear systems

Abstract / Introduction Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by
  • 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:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
  • [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. BardetJ.-C. FaugèreB. 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. BettaleJ.-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. CabarcasD. 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. CourtoisA. KlimovJ. 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èreM. 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)

SHARE

Article Metrics

HTML views(2797) PDF downloads(574) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return