# American Institute of Mathematical Sciences

doi: 10.3934/amc.2022001
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.

## An algorithm for solving over-determined multivariate quadratic systems over finite fields

 1 Department of Applied Mathematics, National Donghwa University, No. 1, Sec. 2, Da Hsueh Rd., Shoufeng, Hualien 974301, Taiwan, R.O.C 2 College of Artificial Intelligence and Green Energy, National Yang Ming Chiao Tung University, Gueiren, Tainan 711010, Taiwan, R.O.C 3 at Private-Enterprises

*Corresponding author: Lih-Chung Wang

Received  September 2019 Revised  November 2021 Early access February 2022

Fund Project: The first author is partially supported by MOST109-2122-M-259-001 and 110-2122-M-259-001

An algorithm for solving over-determined multivariate quadratic systems over finite fields is given. It is more efficient than other known algorithms over finite fields of relatively large size in terms of both performance and memory comsumption. It is also simpler for computer programming. The complexity estimate of our algorithm can be used to estimate the security level of multivariate cryptosystems by solving the multivariate quadratic systems induced by the cryptosystems.

Citation: 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, doi: 10.3934/amc.2022001
##### References:
 [1] G. Ars, J.-C. Faugère, H. Imai, M. Kawazoe and M. Sugita, Comparison between XL and Gröbner basis algorithms, Advances in Cryptology - ASIACRYPT 2004, 3329 (2004), 338-353.  doi: 10.1007/978-3-540-30539-2_24. [2] 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. [3] A. Braeken, C. Wolf and B. Preneel, A study of the security of unbalanced oil and vinegar signature schemes, Topics in cryptology–CT-RSA 2005, Lecture Notes in Computer Science, Springer-Verlag, 3376 (2005), 29–43. doi: 10.1007/978-3-540-30574-3_4. [4] N. Courtois, The security of hidden field equations(HFE), Topics in Cryptology–CT-RSA 2001, Lecture Notes in Computer Sci., Springer, Berlin, 2020 (2001), 266–281. doi: 10.1007/3-540-45353-9_20. [5] N. Courtois, Higher order correlation attacks, XL algorithm and cryptanalysis of toyocrypt, Information Security and Cryptology–ICISC 2002, Lecture Notes in Computer Science, Springer-Verlag, 2587 (2003), 182–199. doi: 10.1007/3-540-36552-4_13. [6] N. Courtois, Algebraic attacks over $GF(2^{k})$, application to HFE challenge 2 and sflash-v2, Public Key Cryptography–PKC 2004, Lecture Notes in Computer Sci., Springer-Verlag, 2947 (2004), 201–217. doi: 10.1007/978-3-540-24632-9_15. [7] N. Courtois, M. Daum and P. Felke, On the security of HFE, HFEv and Quartz, Public Key Cryptography - PKC 2003, Lecture Notes in Computer Science, Springer-Verlag, 2567 (2002), 337–350. doi: 10.1007/3-540-36288-6_25. [8] N. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in Cryptology - EUROCRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, 1087 (2000), 392–407. doi: 10.1007/3-540-45539-6_27. [9] N. Courtois and J. Patarin, About the XL Algorithm over $GF(2)$, Topics in Cryptology–CT-RSA 2003, Lecture Notes in Computer Sci., Springer-Verlag, 2612 (2003), 141–157. doi: 10.1007/3-540-36563-X_10. [10] D. Cox, J. Little and D. O'Shea, Ideal, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 4$^{th}$ edition, Undergraduate Texts in Mathematics. Springer, Cham, 2015. doi: 10.1007/978-3-319-16721-3. [11] C. Diem, The XL- algorithm and a conjecture from commutative algebra, Advances in Cryptology–ASIACRYPT 2004, Lecture Notes in Computer Sci., Springer-Verlag 3329 (2004), 323–337. doi: 10.1007/978-3-540-30539-2_23. [12] V. Dubois, P.-A. Fouque1, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH, Advances in Cryptology CRYPTO 2007, Lecture Notes in Computer Science, Springer-Verlag, 4622 (2007), 1–12. doi: 10.1007/978-3-540-74143-5_1. [13] J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, Applied Cryptography and Network Security|ACNS 2005, Lecture Notes in Computer Science, Springer-Verlag 3531 (2005), 164–175. [14] J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F$_{4}$), J. Pure Appl. Algebra, 139 (1999), 61-88.  doi: 10.1016/S0022-4049(99)00005-5. [15] J.-C. Faugère, A new efficient algorithm for computing Gröbner Bases without reduction to zero (F$_{5}$), Symbolic and Algebraic Computation, International Symposium ISSAC, Proceedings. ACM, 2002 (2002), 75–83. [16] J.-C. Faugère and A. Joux, Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using gröbner bases, Advances in Cryptology CRYPTO 2003, Lecture Notes in Computer Science, Springer-Verlag, 2729 (2003), 44–60. doi: 10.1007/978-3-540-45146-4_3. [17] M. R. Garay and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, Calif., 1979. [18] L. Goubin and N. Courtois, Cryptanalysis of the TTM cryptosystem, Advances in Cryptology–ASIACRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, 1976 (2000), 44–57. doi: 10.1007/3-540-44448-3_4. [19] Y.-H. Hu, C.-Y. Chou, L.-C. Wang and F. Lai, Cryptanalysis of variants of UOV, Information Security Conference ISC 2006, Lecture Notes in Computer Science, Springer-Verlag, 4176 (2006), 161–170. [20] A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, Advances in Cryptology EUROCRYPT'99, Lecture Notes in Computer Science, Springer-Verlag, 1592 (1999), 206–222. doi: 10.1007/3-540-48910-X_15. [21] A. Kipnis and A. Shamir, Cryptanalysis of the oil and vinegar signature scheme, Advances in Cryptology CRYPTO'98, Lecture Notes in Computer Science, Springer-Verlag, 1462 (1998), 257–267. doi: 10.1007/BFb0055733. [22] A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Advances in Cryptology CRYPTO'99, Lecture Notes in Computer Sci., Springer-Verlag, 1666 (1999), 19–30. doi: 10.1007/3-540-48405-1_2. [23] W. Keith Nicholson, Introduction to Abstract Algebra, 2$^nd$ edition, John Wiley & Sons, Inc., New York, 1999. [24] Performance of Optimized Implementations of the NESSIE primitives, version 2.0, http://www.cryptonessie.org. [25] J. Patarin, Cryptanalysis of the matsumoto and imai public key scheme of Eurocrypt'88, Advances in Cryptology CRYPTO'95, Lecture Notes in Computer Science, Springer-Verlag, 963 (1995), 248–261. doi: 10.1007/3-540-44750-4_20. [26] J. Patarin, The Oil and Vinegar Algorithm for Signatures, presented at the Dagstuhl Workshop on Cryptography, 1997. [27] J. Patarin and L. Goubin, Improved algorithms for isomorphisms of polynomials, Advances in Cryptology - EUROCRYPT 1998, Lecture Notes in Computer Science, Springer-Verlag, 1403 (1998), 184–200. [28] J.-M. Shy, Theory of XLT Algorithm and Its Analysis, Master thesis. [29] L.-C. Wang, Y.-H. Hu, F. Lai, C.-Y. Chou and B.-Y. Yang, Tractable rational map signature, Public Key Cryptography PKC 2005, Lecture Notes in Computer Science, Springer-Verlag, 3386 (2005), 244–257. doi: 10.1007/978-3-540-30580-4_17. [30] L.-C. Wang, B.-Y. Yang, Y.-H. Hu and F. Lai, A "mdeium- field" multivariate public-key encryption scheme, Topics in cryptology–CT-RSA 2006, Lecture Notes in Computer Science, Springer-Verlag, 3860 (2006), 132–149. doi: 10.1007/11605805_9. [31] C. Wolf, A. Braeken and B. Preneel, Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC, Security in Communication Networks, 4th International Conference, SCN 2004, Lecture Notes in Computer Science, Springer-Verlag, 3352 (2005), 294–309. [32] B.-Y. Yang and J.-M. Chen, All in the XL family: Theory and practice, Information Security and Cryptology ICISC 2004, Lecture Notes in Computer Science, Springer-Verlag, 3506 (2005), 67–86. doi: 10.1007/11496618_7. [33] B.-Y. Yang and J.-M. Chen, Theoretical analysis of XL over small fields,, ACISP 2004: Information Security and Privacy, 3108 (2004), 277-288.  doi: 10.1007/978-3-540-27800-9_24. [34] B.-Y. Yang and J.-M. Chen, Building secure tame-like multivariate public-key cryptosystems the new TTS, Information Security and Privacy, 35th Australasian Conference, ACISP 2005, Lecture Notes in Computer Science, Springer-Verlag, 3574 (2005), 518–531. [35] B.-Y. Yang, J.-M. Chen and N. Courtois, On Asymptotic security estimates in XL and gröbner bases-Related algebraic cryptanalysis, Information and Communications Security, 6th International Conference ICICS 2004, Lecture Notes in Computer Science Springer-Verlag, 3269 (2004), 401–413. [36] Version V 2: 13 - 14 released on 2007/07/06, in http://magma.maths.usyd. edu.au/magma/, Online, Demo http://magma.maths.usyd.edu.au/calc, CPU: Opteron 2.6G.

show all references

##### References:
 [1] G. Ars, J.-C. Faugère, H. Imai, M. Kawazoe and M. Sugita, Comparison between XL and Gröbner basis algorithms, Advances in Cryptology - ASIACRYPT 2004, 3329 (2004), 338-353.  doi: 10.1007/978-3-540-30539-2_24. [2] 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. [3] A. Braeken, C. Wolf and B. Preneel, A study of the security of unbalanced oil and vinegar signature schemes, Topics in cryptology–CT-RSA 2005, Lecture Notes in Computer Science, Springer-Verlag, 3376 (2005), 29–43. doi: 10.1007/978-3-540-30574-3_4. [4] N. Courtois, The security of hidden field equations(HFE), Topics in Cryptology–CT-RSA 2001, Lecture Notes in Computer Sci., Springer, Berlin, 2020 (2001), 266–281. doi: 10.1007/3-540-45353-9_20. [5] N. Courtois, Higher order correlation attacks, XL algorithm and cryptanalysis of toyocrypt, Information Security and Cryptology–ICISC 2002, Lecture Notes in Computer Science, Springer-Verlag, 2587 (2003), 182–199. doi: 10.1007/3-540-36552-4_13. [6] N. Courtois, Algebraic attacks over $GF(2^{k})$, application to HFE challenge 2 and sflash-v2, Public Key Cryptography–PKC 2004, Lecture Notes in Computer Sci., Springer-Verlag, 2947 (2004), 201–217. doi: 10.1007/978-3-540-24632-9_15. [7] N. Courtois, M. Daum and P. Felke, On the security of HFE, HFEv and Quartz, Public Key Cryptography - PKC 2003, Lecture Notes in Computer Science, Springer-Verlag, 2567 (2002), 337–350. doi: 10.1007/3-540-36288-6_25. [8] N. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in Cryptology - EUROCRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, 1087 (2000), 392–407. doi: 10.1007/3-540-45539-6_27. [9] N. Courtois and J. Patarin, About the XL Algorithm over $GF(2)$, Topics in Cryptology–CT-RSA 2003, Lecture Notes in Computer Sci., Springer-Verlag, 2612 (2003), 141–157. doi: 10.1007/3-540-36563-X_10. [10] D. Cox, J. Little and D. O'Shea, Ideal, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 4$^{th}$ edition, Undergraduate Texts in Mathematics. Springer, Cham, 2015. doi: 10.1007/978-3-319-16721-3. [11] C. Diem, The XL- algorithm and a conjecture from commutative algebra, Advances in Cryptology–ASIACRYPT 2004, Lecture Notes in Computer Sci., Springer-Verlag 3329 (2004), 323–337. doi: 10.1007/978-3-540-30539-2_23. [12] V. Dubois, P.-A. Fouque1, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH, Advances in Cryptology CRYPTO 2007, Lecture Notes in Computer Science, Springer-Verlag, 4622 (2007), 1–12. doi: 10.1007/978-3-540-74143-5_1. [13] J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, Applied Cryptography and Network Security|ACNS 2005, Lecture Notes in Computer Science, Springer-Verlag 3531 (2005), 164–175. [14] J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F$_{4}$), J. Pure Appl. Algebra, 139 (1999), 61-88.  doi: 10.1016/S0022-4049(99)00005-5. [15] J.-C. Faugère, A new efficient algorithm for computing Gröbner Bases without reduction to zero (F$_{5}$), Symbolic and Algebraic Computation, International Symposium ISSAC, Proceedings. ACM, 2002 (2002), 75–83. [16] J.-C. Faugère and A. Joux, Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using gröbner bases, Advances in Cryptology CRYPTO 2003, Lecture Notes in Computer Science, Springer-Verlag, 2729 (2003), 44–60. doi: 10.1007/978-3-540-45146-4_3. [17] M. R. Garay and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, Calif., 1979. [18] L. Goubin and N. Courtois, Cryptanalysis of the TTM cryptosystem, Advances in Cryptology–ASIACRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, 1976 (2000), 44–57. doi: 10.1007/3-540-44448-3_4. [19] Y.-H. Hu, C.-Y. Chou, L.-C. Wang and F. Lai, Cryptanalysis of variants of UOV, Information Security Conference ISC 2006, Lecture Notes in Computer Science, Springer-Verlag, 4176 (2006), 161–170. [20] A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, Advances in Cryptology EUROCRYPT'99, Lecture Notes in Computer Science, Springer-Verlag, 1592 (1999), 206–222. doi: 10.1007/3-540-48910-X_15. [21] A. Kipnis and A. Shamir, Cryptanalysis of the oil and vinegar signature scheme, Advances in Cryptology CRYPTO'98, Lecture Notes in Computer Science, Springer-Verlag, 1462 (1998), 257–267. doi: 10.1007/BFb0055733. [22] A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Advances in Cryptology CRYPTO'99, Lecture Notes in Computer Sci., Springer-Verlag, 1666 (1999), 19–30. doi: 10.1007/3-540-48405-1_2. [23] W. Keith Nicholson, Introduction to Abstract Algebra, 2$^nd$ edition, John Wiley & Sons, Inc., New York, 1999. [24] Performance of Optimized Implementations of the NESSIE primitives, version 2.0, http://www.cryptonessie.org. [25] J. Patarin, Cryptanalysis of the matsumoto and imai public key scheme of Eurocrypt'88, Advances in Cryptology CRYPTO'95, Lecture Notes in Computer Science, Springer-Verlag, 963 (1995), 248–261. doi: 10.1007/3-540-44750-4_20. [26] J. Patarin, The Oil and Vinegar Algorithm for Signatures, presented at the Dagstuhl Workshop on Cryptography, 1997. [27] J. Patarin and L. Goubin, Improved algorithms for isomorphisms of polynomials, Advances in Cryptology - EUROCRYPT 1998, Lecture Notes in Computer Science, Springer-Verlag, 1403 (1998), 184–200. [28] J.-M. Shy, Theory of XLT Algorithm and Its Analysis, Master thesis. [29] L.-C. Wang, Y.-H. Hu, F. Lai, C.-Y. Chou and B.-Y. Yang, Tractable rational map signature, Public Key Cryptography PKC 2005, Lecture Notes in Computer Science, Springer-Verlag, 3386 (2005), 244–257. doi: 10.1007/978-3-540-30580-4_17. [30] L.-C. Wang, B.-Y. Yang, Y.-H. Hu and F. Lai, A "mdeium- field" multivariate public-key encryption scheme, Topics in cryptology–CT-RSA 2006, Lecture Notes in Computer Science, Springer-Verlag, 3860 (2006), 132–149. doi: 10.1007/11605805_9. [31] C. Wolf, A. Braeken and B. Preneel, Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC, Security in Communication Networks, 4th International Conference, SCN 2004, Lecture Notes in Computer Science, Springer-Verlag, 3352 (2005), 294–309. [32] B.-Y. Yang and J.-M. Chen, All in the XL family: Theory and practice, Information Security and Cryptology ICISC 2004, Lecture Notes in Computer Science, Springer-Verlag, 3506 (2005), 67–86. doi: 10.1007/11496618_7. [33] B.-Y. Yang and J.-M. Chen, Theoretical analysis of XL over small fields,, ACISP 2004: Information Security and Privacy, 3108 (2004), 277-288.  doi: 10.1007/978-3-540-27800-9_24. [34] B.-Y. Yang and J.-M. Chen, Building secure tame-like multivariate public-key cryptosystems the new TTS, Information Security and Privacy, 35th Australasian Conference, ACISP 2005, Lecture Notes in Computer Science, Springer-Verlag, 3574 (2005), 518–531. [35] B.-Y. Yang, J.-M. Chen and N. Courtois, On Asymptotic security estimates in XL and gröbner bases-Related algebraic cryptanalysis, Information and Communications Security, 6th International Conference ICICS 2004, Lecture Notes in Computer Science Springer-Verlag, 3269 (2004), 401–413. [36] Version V 2: 13 - 14 released on 2007/07/06, in http://magma.maths.usyd. edu.au/magma/, Online, Demo http://magma.maths.usyd.edu.au/calc, CPU: Opteron 2.6G.
The complexity estimate of XLT
 Step $t_{FM}+t_{FA}$ $t_{FM}$ $t_{FA}$ 1 $\frac{n(n+1)}{2}m^{2}$ 2 $nv_{d}$ 3 $m_{d+1}(m_{d,I}r_{d}+\sum^{d}_{k = 0}(r_{d,k}n_{k+1}))+m_{d,F}m_{d,I}$ $(n_{d+1}+m_{d,I})\frac{m_{d,I}(m_{d,I}-1)}{2}(n_{d+1}+m_{d,I}-r_{d}-m_{d,F})$ $-\frac{m_{d,I}(m_{d,I}-1)(2m_{d,I}-1)}{6}$ 4 5 $(n_{D_{XL_{T}}}-1)\sum^{D_{XL_{T}}-1}_{k = 0}(r_{k}n_{k+1})$ $2n_{D_{XL_{T}}}$
 Step $t_{FM}+t_{FA}$ $t_{FM}$ $t_{FA}$ 1 $\frac{n(n+1)}{2}m^{2}$ 2 $nv_{d}$ 3 $m_{d+1}(m_{d,I}r_{d}+\sum^{d}_{k = 0}(r_{d,k}n_{k+1}))+m_{d,F}m_{d,I}$ $(n_{d+1}+m_{d,I})\frac{m_{d,I}(m_{d,I}-1)}{2}(n_{d+1}+m_{d,I}-r_{d}-m_{d,F})$ $-\frac{m_{d,I}(m_{d,I}-1)(2m_{d,I}-1)}{6}$ 4 5 $(n_{D_{XL_{T}}}-1)\sum^{D_{XL_{T}}-1}_{k = 0}(r_{k}n_{k+1})$ $2n_{D_{XL_{T}}}$
Detailed figures of parameters, for $m = 13$, $n = 12$
 $d$ $m_{d}$ $n_{d}$ $r_{d}$ $m_{d,F}$ $m_{d,I}$ # of $t_{FM}$ in $log_{2}$ 2 13 78 65 89 67 22.557 3 169 286 208 722 214 28.337 4 1105 715 429 3331 465 32.471 5 4901 1287 572 11249 698 35.277 6 16848 1716 429 31119 705 36.952 7 48672 1716 0
 $d$ $m_{d}$ $n_{d}$ $r_{d}$ $m_{d,F}$ $m_{d,I}$ # of $t_{FM}$ in $log_{2}$ 2 13 78 65 89 67 22.557 3 169 286 208 722 214 28.337 4 1105 715 429 3331 465 32.471 5 4901 1287 572 11249 698 35.277 6 16848 1716 429 31119 705 36.952 7 48672 1716 0
Table for the running time and the time complexity
 $(m,n)$ Cycle numbers $(C)$ in $log_{2}$ Finite multiplications $(M)$ in $log_{2}$ Ratio $(\frac{C}{M})$ in $log_{2}$ $(9,8)$ 27.85 24.31 3.54 $(10,9)$ 30.85 27.87 2.98 $(11,10)$ 33.91 30.62 3.29 $(12,11)$ 36.90 34.23 2.67 $(10,8)$ 26.85 23.31 3.54 $(11,9)$ 28.85 26.01 2.84 $(12,10)$ 32.06 29.22 2.84 $(13,11)$ 34.67 32.03 2.64 $(11,8)$ 25.20 21.84 3.36 $(12,9)$ 27.56 24.97 2.59 $(13,10)$ 30.35 27.68 2.67 $(14,11)$ 32.86 29.92 2.94
 $(m,n)$ Cycle numbers $(C)$ in $log_{2}$ Finite multiplications $(M)$ in $log_{2}$ Ratio $(\frac{C}{M})$ in $log_{2}$ $(9,8)$ 27.85 24.31 3.54 $(10,9)$ 30.85 27.87 2.98 $(11,10)$ 33.91 30.62 3.29 $(12,11)$ 36.90 34.23 2.67 $(10,8)$ 26.85 23.31 3.54 $(11,9)$ 28.85 26.01 2.84 $(12,10)$ 32.06 29.22 2.84 $(13,11)$ 34.67 32.03 2.64 $(11,8)$ 25.20 21.84 3.36 $(12,9)$ 27.56 24.97 2.59 $(13,10)$ 30.35 27.68 2.67 $(14,11)$ 32.86 29.92 2.94
Comparison of the time complexity, converted to $log_{2}$
 $(m,n)$ XL with Lanczos XL$_{T}$ $(11,8)$ 29.03 21.84 $(11,9)$ 33.54 26.01 $(11,10)$ 47.27 30.62 $(14,11)$ 36.78 29.92 $(14,12)$ 44.26 34.51 $(14,13)$ 60.21 40.63
 $(m,n)$ XL with Lanczos XL$_{T}$ $(11,8)$ 29.03 21.84 $(11,9)$ 33.54 26.01 $(11,10)$ 47.27 30.62 $(14,11)$ 36.78 29.92 $(14,12)$ 44.26 34.51 $(14,13)$ 60.21 40.63
Comparison of the space complexity, converted to $log_{2}$
 $(m,n)$ XL with Lanczos XL$_{T}$ $(11,8)$ 20.64 15.48 $(11,9)$ 24.64 18.54 $(11,10)$ 37.27 21.69 $(14,11)$ 27.33 21.00 $(14,12)$ 34.27 24.30 $(14,13)$ 49.24 29.08
 $(m,n)$ XL with Lanczos XL$_{T}$ $(11,8)$ 20.64 15.48 $(11,9)$ 24.64 18.54 $(11,10)$ 37.27 21.69 $(14,11)$ 27.33 21.00 $(14,12)$ 34.27 24.30 $(14,13)$ 49.24 29.08
Comparison of the running time, converted to $log_{2}$
 $(m,n)$ F$_{4}$ in Magma XL$_{T}$ $(9,8)$ 28.98 27.85 $(10,9)$ 31.38 30.85 $(11,10)$ 34.28 33.91 $(10,8)$ 27.54 26.85 $(11,9)$ 29.44 28.85 $(12,10)$ 32.20 32.06
 $(m,n)$ F$_{4}$ in Magma XL$_{T}$ $(9,8)$ 28.98 27.85 $(10,9)$ 31.38 30.85 $(11,10)$ 34.28 33.91 $(10,8)$ 27.54 26.85 $(11,9)$ 29.44 28.85 $(12,10)$ 32.20 32.06
Comparison of the space complexity in mega bytes
 $(m,n)$ F$_{4}$ in Magma XL$_{T}$ $(9,8)$ 7.5 1.4 $(10,9)$ 8.8 3.8 $(11,10)$ 13.5 11.1 $(10,8)$ 7.5 1.2 $(11,9)$ 7.9 2.1 $(12,10)$ 10.6 7.0
 $(m,n)$ F$_{4}$ in Magma XL$_{T}$ $(9,8)$ 7.5 1.4 $(10,9)$ 8.8 3.8 $(11,10)$ 13.5 11.1 $(10,8)$ 7.5 1.2 $(11,9)$ 7.9 2.1 $(12,10)$ 10.6 7.0
Comparison of the number of operations, converted to $log_{2}$
 $(m,n,{K})$ Hybrid method XL$_{T}$ $(10,9,\ GF(2^{8}))$ 37.75 35.22 $(20,18,\ GF(2^{8}))$ 67.79 64.34 $(20,19,\ GF(2^{8}))$ 66.73 62.39 $(24,22,\ GF(2^{8}))$ 79.06 75.18 $(24,23,\ GF(2^{8}))$ 78.09 72.70 $(20,20,\ GF(2^{32}))$ 82.00 n/a $(23,22,\ GF(2^{16}))$ 81.00 77.76 $(26,25,\ GF(2^{8}))$ 83.00 77.36 $(30,23,\ GF(2^{4}))$ 83.00 80.61 $(41,18,\ GF(2^{2}))$ 82.00 81.59
 $(m,n,{K})$ Hybrid method XL$_{T}$ $(10,9,\ GF(2^{8}))$ 37.75 35.22 $(20,18,\ GF(2^{8}))$ 67.79 64.34 $(20,19,\ GF(2^{8}))$ 66.73 62.39 $(24,22,\ GF(2^{8}))$ 79.06 75.18 $(24,23,\ GF(2^{8}))$ 78.09 72.70 $(20,20,\ GF(2^{32}))$ 82.00 n/a $(23,22,\ GF(2^{16}))$ 81.00 77.76 $(26,25,\ GF(2^{8}))$ 83.00 77.36 $(30,23,\ GF(2^{4}))$ 83.00 80.61 $(41,18,\ GF(2^{2}))$ 82.00 81.59
Time complexity of some cryptosystems, converted to $log_{2}$
 Cryptosystem Name Parameters FXL with Lanczos FXL$_{T}$ SFLASH$^{v2}$ n = 26, $GF(2^{7})$ 87.53 78.25 HFE Challenge 2 n = 32, $GF(2^{4})$ 88.27 85.01 TTS n = 20, $GF(2^{8})$ 72.55 62.06 TRMS n = 20, $GF(2^{8})$ 72.55 62.06
 Cryptosystem Name Parameters FXL with Lanczos FXL$_{T}$ SFLASH$^{v2}$ n = 26, $GF(2^{7})$ 87.53 78.25 HFE Challenge 2 n = 32, $GF(2^{4})$ 88.27 85.01 TTS n = 20, $GF(2^{8})$ 72.55 62.06 TRMS n = 20, $GF(2^{8})$ 72.55 62.06
Space complexity of some cryptosystems, converted to $log_{2}$
 Cryptosystem Name Parameters FXL with Lanczos FXL$_{T}$ SFLASH$^{v2}$ n = 26, $GF(2^{7})$ 60.04 51.29 HFE Challenge 2 n = 32, $GF(2^{4})$ 50.14 41.41 TTS n = 20, $GF(2^{8})$ 50.84 42.87 TRMS n = 20, $GF(2^{8})$ 50.84 42.87
 Cryptosystem Name Parameters FXL with Lanczos FXL$_{T}$ SFLASH$^{v2}$ n = 26, $GF(2^{7})$ 60.04 51.29 HFE Challenge 2 n = 32, $GF(2^{4})$ 50.14 41.41 TTS n = 20, $GF(2^{8})$ 50.84 42.87 TRMS n = 20, $GF(2^{8})$ 50.84 42.87
The complexity estimate of XL$_{T}$ with $m = 16,\cdots,40$, $n = m,\cdots,m-6$, over the field $GF(2^{8})$
 $m$ $n = m$ $n = m-1$ $n = m-2$ $n = m-3$ $n = m-4$ $n = m-5$ $n = m-6$ 16 45.48 38.90 34.71 30.48 25.48 22.53 18.89 17 47.14 42.71 38.29 33.28 28.92 24.94 22.32 18 50.93 44.27 39.89 35.67 31.43 27.02 24.24 19 52.64 48.08 41.61 38.38 34.42 30.42 26.52 20 56.39 49.67 45.19 40.88 36.69 32.90 29.82 21 58.19 53.47 46.93 42.52 39.68 35.99 31.96 22 61.88 55.10 50.52 46.13 41.85 37.70 34.38 23 63.76 57.23 52.29 47.74 43.45 41.03 37.38 24 67.14 60.56 55.85 49.82 47.08 42.79 38.70 25 69.82 62.76 57.65 52.96 48.55 44.39 42.36 26 73.13 66.25 59.94 55.10 50.63 48.09 43.71 27 75.66 68.88 63.10 58.19 53.67 49.37 45.35 28 78.43 72.65 65.70 60.35 55.71 51.46 49.06 29 81.53 75.32 69.32 62.92 58.23 54.46 50.18 30 84.05 78.46 72.00 66.43 61.22 56.39 52.33 31 87.20 81.51 74.48 68.98 63.75 58.95 55.42 32 89.72 84.01 77.92 72.27 67.06 62.07 57.51 33 92.89 87.05 80.86 75.20 69.83 64.77 59.91 34 95.97 89.53 84.41 77.63 72.25 67.07 63.16 35 98.39 92.60 86.69 80.93 75.83 70.63 65.79 36 101.70 95.03 89.84 83.95 78.44 73.21 68.16 37 104.32 98.17 91.93 87.50 80.79 75.46 71.41 38 102.03 101.21 95.30 89.62 84.38 79.22 74.16 39 105.76 103.76 98.27 92.69 87.08 79.77 76.50 40 108.79 104.92 100.70 94.58 88.54 83.39 79.86
 $m$ $n = m$ $n = m-1$ $n = m-2$ $n = m-3$ $n = m-4$ $n = m-5$ $n = m-6$ 16 45.48 38.90 34.71 30.48 25.48 22.53 18.89 17 47.14 42.71 38.29 33.28 28.92 24.94 22.32 18 50.93 44.27 39.89 35.67 31.43 27.02 24.24 19 52.64 48.08 41.61 38.38 34.42 30.42 26.52 20 56.39 49.67 45.19 40.88 36.69 32.90 29.82 21 58.19 53.47 46.93 42.52 39.68 35.99 31.96 22 61.88 55.10 50.52 46.13 41.85 37.70 34.38 23 63.76 57.23 52.29 47.74 43.45 41.03 37.38 24 67.14 60.56 55.85 49.82 47.08 42.79 38.70 25 69.82 62.76 57.65 52.96 48.55 44.39 42.36 26 73.13 66.25 59.94 55.10 50.63 48.09 43.71 27 75.66 68.88 63.10 58.19 53.67 49.37 45.35 28 78.43 72.65 65.70 60.35 55.71 51.46 49.06 29 81.53 75.32 69.32 62.92 58.23 54.46 50.18 30 84.05 78.46 72.00 66.43 61.22 56.39 52.33 31 87.20 81.51 74.48 68.98 63.75 58.95 55.42 32 89.72 84.01 77.92 72.27 67.06 62.07 57.51 33 92.89 87.05 80.86 75.20 69.83 64.77 59.91 34 95.97 89.53 84.41 77.63 72.25 67.07 63.16 35 98.39 92.60 86.69 80.93 75.83 70.63 65.79 36 101.70 95.03 89.84 83.95 78.44 73.21 68.16 37 104.32 98.17 91.93 87.50 80.79 75.46 71.41 38 102.03 101.21 95.30 89.62 84.38 79.22 74.16 39 105.76 103.76 98.27 92.69 87.08 79.77 76.50 40 108.79 104.92 100.70 94.58 88.54 83.39 79.86

2021 Impact Factor: 1.015