Evaluation of solving time for multivariate quadratic equation system using XL algorithm over small finite fields on GPU. (English) Zbl 1327.94076

Mohapatra, Ram N. (ed.) et al., Mathematics and computing. Selected papers based on the presentations at the 2nd international conference, ICMC, Haldia, India, January 5–10, 2015. New Delhi: Springer (ISBN 978-81-322-2451-8/hbk; 978-81-322-2452-5/ebook). Springer Proceedings in Mathematics & Statistics 139, 349-361 (2015).
Summary: The security of multivariate public-key cryptography is largely determined by the complexity of solving multivariate quadratic equations over finite fields, a.k.a. the MQ problem. XL (eXtended Linearization) is an efficient algorithm for solving the MQ problem, so its running time is an important indicator for the complexity of solving the MQ problem. In this work, we implement XL on graphics processing unit (GPU) and evaluate its solving time for the MQ problem over several small finite fields, namely, \(\mathrm{GF}(2)\), \(\mathrm{GF}(3)\), \(\mathrm{GF}(5)\), and \(\mathrm{GF}(7)\). Our implementations can solve MQ instances of 74 equations in 37 unknowns over \(\mathrm{GF}(2)\) in 36,972 s, 48 equations in 24 unknowns over \(\mathrm{GF}(3)\) in 933 s, 42 equations in 21 unknowns over \(\mathrm{GF}(5)\) in 347 s, as well as 42 equations in 21 unknowns over \(\mathrm{GF}(7)\) in 387 s. Moreover, we can also solve the MQ instance of 48 equations in 24 unknowns over \(\mathrm{GF}(5)\) in 34,882 s, whose complexity is about \(O(2^{67})\) with exhaustive search.
For the entire collection see [Zbl 1325.00054].


94A60 Cryptography
68W30 Symbolic computation and algebraic computation
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)


Full Text: DOI


[1] cuSPARSE::cuda toolkit documentation.
[2] Optimizing parallel reduction in cuda.
[3] Ars, G,, Faugere, J.-C., Imai, H., Kawazoe, M., Sugita, M.: Comparison between XL and Gröbner basis algorithms. In; Advances in cryptology-ASIACRYPT, pp. 338-353. Springer, Berlin (2004) · Zbl 1094.94024
[4] Bard, G.V.: Algebraic cryptanalysis, Springer, Berlin (2009) · Zbl 1183.94019
[5] Berbain, C., Gilbert, H., Patarin, J.: Quad: a practical stream cipher with provable security. In: Advances in cryptology-EUROCRYPT, pp. 109-128. Springer, Berlin (2006) · Zbl 1140.94322
[6] Cheng, C.-M., Chou, T., Niederhagen, R., Yang, B.-Y.: Solving quadratic equations with XL on parallel architectures. In: Cryptographic hardware and embedded systems-CHES, pp. 356-373. Springer, Berlin (2012) · Zbl 1295.68202
[7] Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Advances in cryptology-EUROCRYPT, pp. 392-407. Springer, Berlin (2000) · Zbl 1082.94514
[8] Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Advances in cryptology-EUROCRYPT 99, pp. 206-222. Springer, Berlin (1999) · Zbl 0933.94031
[9] Mohamed, M.S.E,, Cabarcas, D., Ding, J., Buchmann, J,, Bulygin, S.: Mxl3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals. In: Information, security and cryptology-ICISC, pp. 87-100. Springer, Berlin (2010) · Zbl 1305.94066
[10] Mohamed, M.S.E., Ding, J., Buchmann, J.: Towards algebraic cryptanalysis of hfe challenge 2. In: The 5th international conference on information security and assurance, CCIS, vol. 200, pp. 123-131. Springer, Berlin (2011)
[11] Mohamed, W.S.A., Ding, J., Kleinjung, T., Bulygin, S., Buchmann, J.: Pwxl: a parallel Wiedemann-XL algorithm for solving polynomial equations over
[12] Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Advances in cryptology-Eurocrypt 96, pp. 33-48. Springer, Berlin (1996) · Zbl 1301.94125
[13] Rønjom, S., Raddum, H.: On the number of linearly independent equations generated by XL. In: Sequences and their applications-SETA, pp. 239-251. Springer, Berlin (2008) · Zbl 1206.94088
[14] Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32(1), 54-62 (1986) · Zbl 0607.65015
[15] Yang, B.-Y., Chen, O.C.-H., Bernstein, D.J., Chen, J.-M.: Analysis of quad. In: Fast software encryption, pp. 290-308. Springer, Berlin (2007) · Zbl 1186.94476
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.