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. ArsJ.-C. FaugèreH. ImaiM. 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. 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.

[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. ArsJ.-C. FaugèreH. ImaiM. 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. 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.

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

Table 1.  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}}}$
Table 2.  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 3.  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
Table 4.  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
Table 5.  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
Table 6.  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
Table 7.  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
Table 8.  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
Table 9.  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
Table 10.  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
Table 11.  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
[1]

Ana-Maria Acu, Laura Hodis, Ioan Rasa. Multivariate weighted kantorovich operators. Mathematical Foundations of Computing, 2020, 3 (2) : 117-124. doi: 10.3934/mfc.2020009

[2]

Bin Han. Some multivariate polynomials for doubled permutations. Electronic Research Archive, 2021, 29 (2) : 1925-1944. doi: 10.3934/era.2020098

[3]

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

[4]

Ling-Xiong Han, Wen-Hui Li, Feng Qi. Approximation by multivariate Baskakov–Kantorovich operators in Orlicz spaces. Electronic Research Archive, 2020, 28 (2) : 721-738. doi: 10.3934/era.2020037

[5]

Gusein Sh. Guseinov. Spectral method for deriving multivariate Poisson summation formulae. Communications on Pure and Applied Analysis, 2013, 12 (1) : 359-373. doi: 10.3934/cpaa.2013.12.359

[6]

Wenxue Huang, Qitian Qiu. Forward supervised discretization for multivariate with categorical responses. Big Data & Information Analytics, 2016, 1 (2&3) : 217-225. doi: 10.3934/bdia.2016005

[7]

Sumit Kumar Debnath, Tanmay Choudhury, Pantelimon Stănică, Kunal Dey, Nibedita Kundu. Delegating signing rights in a multivariate proxy signature scheme. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021016

[8]

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

[9]

Jintai Ding, Zheng Zhang, Joshua Deaton. The singularity attack to the multivariate signature scheme HIMQ-3. Advances in Mathematics of Communications, 2021, 15 (1) : 65-72. doi: 10.3934/amc.2020043

[10]

Richard D. Neidinger. Efficient recurrence relations for univariate and multivariate Taylor series coefficients. Conference Publications, 2013, 2013 (special) : 587-596. doi: 10.3934/proc.2013.2013.587

[11]

Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial and Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117

[12]

Danilo Costarelli, Gianluca Vinti. Asymptotic expansions and Voronovskaja type theorems for the multivariate neural network operators. Mathematical Foundations of Computing, 2020, 3 (1) : 41-50. doi: 10.3934/mfc.2020004

[13]

Nana Xu, Jun Sun, Jingjing Liu, Xianchao Xiu. A novel scheme for multivariate statistical fault detection with application to the Tennessee Eastman process. Mathematical Foundations of Computing, 2021, 4 (3) : 167-184. doi: 10.3934/mfc.2021010

[14]

Vikas Srivastava, Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Saibal Kumar Pal. A multivariate identity-based broadcast encryption with applications to the internet of things. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021050

[15]

Lucian Coroianu, Danilo Costarelli, Sorin G. Gal, Gianluca Vinti. Approximation by multivariate max-product Kantorovich-type operators and learning rates of least-squares regularized regression. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4213-4225. doi: 10.3934/cpaa.2020189

[16]

Jinkui Liu, Shengjie Li. Multivariate spectral DY-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial and Management Optimization, 2017, 13 (1) : 283-295. doi: 10.3934/jimo.2016017

[17]

Victor Meng Hwee Ong, David J. Nott, Taeryon Choi, Ajay Jasra. Flexible online multivariate regression with variational Bayes and the matrix-variate Dirichlet process. Foundations of Data Science, 2019, 1 (2) : 129-156. doi: 10.3934/fods.2019006

[18]

Yaxian Xu, Ajay Jasra. Particle filters for inference of high-dimensional multivariate stochastic volatility models with cross-leverage effects. Foundations of Data Science, 2019, 1 (1) : 61-85. doi: 10.3934/fods.2019003

[19]

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

[20]

Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1

2021 Impact Factor: 1.015

Article outline

Figures and Tables

[Back to Top]