American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2021047
Online First

Online First 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). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

On the complexity of solving generic overdetermined bilinear systems

John B. Baena 1, , Daniel Cabarcas 1, and  Javier Verbel 2,,

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)

Received  May 2021 Revised  July 2021 Early access October 2021

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: Post-quatum cryptography, multivariate public key cryptography, minimum rank, bilinear systems, complexity, polynomial solving.
Mathematics Subject Classification: Primary: 13P15, 94A60, 15A03, 68W30, 14G50; Secondary: 13P10, 14Q20.
Citation: John B. Baena, Daniel Cabarcas, Javier Verbel. On the complexity of solving generic overdetermined bilinear systems. Advances in Mathematics of Communications, doi: 10.3934/amc.2021047
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.

show all references

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.

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 Options

Download as excel

$ 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 Options

Download as excel

$ 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)
Table Options

Download as excel

$ 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)
Table202 
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 Options

Download as excel

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 Options

Download as excel

$ 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
Table Options

Download as excel

$ 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]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[2]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[3]

Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022031
[4]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012
[5]

Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023
[6]

Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022026
[7]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[8]

Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169
[9]

Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249
[10]

Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089
[11]

Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013
[12]

Lih-Chung Wang, Tzer-jen Wei, Jian-Ming Shih, Yuh-Hua Hu, Chih-Cheng Hsieh. An algorithm for solving over-determined multivariate quadratic systems over finite fields. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022001
[13]

Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046
[14]

Yu-Chi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021053
[15]

Mariantonia Cotronei, Tomas Sauer. Full rank filters and polynomial reproduction. Communications on Pure and Applied Analysis, 2007, 6 (3) : 667-687. doi: 10.3934/cpaa.2007.6.667
[16]

E. Fossas, J. M. Olm. Galerkin method and approximate tracking in a non-minimum phase bilinear system. Discrete and Continuous Dynamical Systems - B, 2007, 7 (1) : 53-76. doi: 10.3934/dcdsb.2007.7.53
[17]

Chuang Peng. Minimum degrees of polynomial models on time series. Conference Publications, 2005, 2005 (Special) : 720-729. doi: 10.3934/proc.2005.2005.720
[18]

Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[19]

Zhong Wan, Chunhua Yang. New approach to global minimization of normal multivariate polynomial based on tensor. Journal of Industrial and Management Optimization, 2008, 4 (2) : 271-285. doi: 10.3934/jimo.2008.4.271
[20]

Tobias Breiten, Karl Kunisch, Laurent Pfeiffer. Numerical study of polynomial feedback laws for a bilinear control problem. Mathematical Control and Related Fields, 2018, 8 (3&4) : 557-582. doi: 10.3934/mcrf.2018023

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (274)
  • HTML views (201)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy