-
Previous Article
Revisiting some results on APN and algebraic immune functions
- AMC Home
- This Issue
-
Next Article
Repeated-root constacyclic codes of length 6lmpn
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
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 |
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.
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. |
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 |
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 |
F4 |
F4 |
|||||||
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) |
F4 |
F4 |
|||||||
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) |
F4 |
F4 |
|||||||
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) |
F4 |
F4 |
|||||||
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 |
1: function 2: 3: 4: for 5:: if 6: return 7: end if 8: end for 9: end function |
Algorithm 2 |
1: function 2: 3: 4: for 5:: if 6: return 7: end if 8: end for 9: end function |
20 | 30 | |||||||||||
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 |
20 | 30 | |||||||||||
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 |
Fmc | Mmc | 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 |
Fmc | Mmc | 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
Other articles
by authors
[Back to Top]