Article Contents

2024, Volume 18, Issue 1: 55-90. Doi: 10.3934/amc.2022001

This issue Previous Article Constructions of optimal low hit zone frequency hopping sequence sets with large family size Next Article Galois LCD codes over rings

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
^*Corresponding author: Lih-Chung Wang

Received: September 2019

Revised: November 2021

Early access: February 2022

Published: February 2024

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

Abstract / Introduction Full Text(HTML) Figure(0) / Table(11) Related Papers Cited by

Abstract

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.

Keywords:

multivariate quadratic (MQ) problem,
multivariate cryptosystem.

Mathematics Subject Classification: Primary: 68W30, 13P10, 13P15.

Citation:

Full Text(HTML)

Table 1. The complexity estimate of 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}}}$

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.