American Institute of Mathematical Sciences

Advanced
February  2021, 15(1): 65-72. doi: 10.3934/amc.2020043

The singularity attack to the multivariate signature scheme HIMQ-3

Jintai Ding , Zheng Zhang and  Joshua Deaton

Department of Mathematical Science, University of Cincinnati, USA

Received  March 2019 Revised  September 2019 Published  November 2019

We present a cryptanalysis of a signature scheme HIMQ-3 due to Kyung-Ah Shim et al [10], which is a submission to National Institute of Standards and Technology (NIST) standardization process of post-quantum cryptosystems in 2017. We will show that inherent to the signing process is a leakage of information of the private key. Using this information one can forge a signature.

Keywords: Multivariate public key cryptography, cryptanalysis, oil vinegar signature scheme, multivariate qudratic equations.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.
Citation: 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
References:
[1]

M. Albrecht, G. Bard and C. Pernet, Efficient dense Gaussian elimination over the finite field with two elements, preprint, arXiv: 1111.6549. Google Scholar

[2]

H. Cohn, R. Kleinberg, B. Szegedy and C. Umans, Group-theoretic algorithms for matrix multiplication, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), (2005), 379–388. doi: 10.1109/SFCS.2005.39.  Google Scholar

[3]

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Journal of symbolic computation, 9 (1990), 251-280.  doi: 10.1016/S0747-7171(08)80013-2.  Google Scholar

[4]

J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, International Conference on Applied Cryptography and Network Security Springer, (2005), 164–175. doi: 10.1007/11496137_12.  Google Scholar

[5]

National Institute of Standards and Technology, Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process, 2017. Available from: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf. Google Scholar

[6]

J. T. Ding, C. Wolf and B.-Y. Yang, $l$-invertible cycles for $M$ultivariate $Q$uadratic $(MQ)$ public key cryptography, Public Key Cryptography-PKC 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4450 (2007), 226-281.  doi: 10.1007/978-3-540-71677-8_18.  Google Scholar

[7]

J. Dumas and C. Pernet, Computational linear algebra over finite fields, preprint, arXiv: 1204.3735. Google Scholar

[8]

A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, Advances in Cryptology—EUROCRYPT '99 (Prague), Lecture Notes in Comput. Sci., Springer, Berlin, 1592 (1999), 206-222.  doi: 10.1007/3-540-48910-X_15.  Google Scholar

[9]

J. Patarin, The oil and vinegar algorithm for signatures, in Dagstuhl Workshop on Cryptography, (1997). Google Scholar

[10]

K. Shim, C. Park and A. Kim, Himq-3: A high speed signature scheme based on multivariate quadratic equations, (2017). Google Scholar

[11]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011.  Google Scholar

[12]

V. Strassen, Gaussian elimination is not optimal, Numerische Mathematik, 13 (1969), 354-356.  doi: 10.1007/BF02165411.  Google Scholar

[13]

V. V. Williams, Breaking the Coppersmith-Winograd barrier, CiteSeer, Available from: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.228.9947&rep=rep1&type=pdf. Google Scholar

show all references

References:
[1]

M. Albrecht, G. Bard and C. Pernet, Efficient dense Gaussian elimination over the finite field with two elements, preprint, arXiv: 1111.6549. Google Scholar

[2]

H. Cohn, R. Kleinberg, B. Szegedy and C. Umans, Group-theoretic algorithms for matrix multiplication, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), (2005), 379–388. doi: 10.1109/SFCS.2005.39.  Google Scholar

[3]

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Journal of symbolic computation, 9 (1990), 251-280.  doi: 10.1016/S0747-7171(08)80013-2.  Google Scholar

[4]

J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, International Conference on Applied Cryptography and Network Security Springer, (2005), 164–175. doi: 10.1007/11496137_12.  Google Scholar

[5]

National Institute of Standards and Technology, Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process, 2017. Available from: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf. Google Scholar

[6]

J. T. Ding, C. Wolf and B.-Y. Yang, $l$-invertible cycles for $M$ultivariate $Q$uadratic $(MQ)$ public key cryptography, Public Key Cryptography-PKC 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4450 (2007), 226-281.  doi: 10.1007/978-3-540-71677-8_18.  Google Scholar

[7]

J. Dumas and C. Pernet, Computational linear algebra over finite fields, preprint, arXiv: 1204.3735. Google Scholar

[8]

A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, Advances in Cryptology—EUROCRYPT '99 (Prague), Lecture Notes in Comput. Sci., Springer, Berlin, 1592 (1999), 206-222.  doi: 10.1007/3-540-48910-X_15.  Google Scholar

[9]

J. Patarin, The oil and vinegar algorithm for signatures, in Dagstuhl Workshop on Cryptography, (1997). Google Scholar

[10]

K. Shim, C. Park and A. Kim, Himq-3: A high speed signature scheme based on multivariate quadratic equations, (2017). Google Scholar

[11]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011.  Google Scholar

[12]

V. Strassen, Gaussian elimination is not optimal, Numerische Mathematik, 13 (1969), 354-356.  doi: 10.1007/BF02165411.  Google Scholar

[13]

V. V. Williams, Breaking the Coppersmith-Winograd barrier, CiteSeer, Available from: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.228.9947&rep=rep1&type=pdf. Google Scholar

[1]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[2]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[3]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409
[4]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009
[5]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044
[6]

Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020127
[7]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182
[8]

Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827
[9]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277
[10]

María J. Garrido-Atienza, Bohdan Maslowski, Jana  Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088
[11]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[12]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[13]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203
[14]

Guangying Lv, Jinlong Wei, Guang-an Zou. Noise and stability in reaction-diffusion equations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021005
[15]

Madalina Petcu, Roger Temam. The one dimensional shallow water equations with Dirichlet boundary conditions on the velocity. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 209-222. doi: 10.3934/dcdss.2011.4.209
[16]

Zhouxin Li, Yimin Zhang. Ground states for a class of quasilinear Schrödinger equations with vanishing potentials. Communications on Pure & Applied Analysis, 2021, 20 (2) : 933-954. doi: 10.3934/cpaa.2020298
[17]

Yimin Zhang, Youjun Wang, Yaotian Shen. Solutions for quasilinear Schrödinger equations with critical Sobolev-Hardy exponents. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1037-1054. doi: 10.3934/cpaa.2011.10.1037
[18]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[19]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[20]

Daoyuan Fang, Ting Zhang. Compressible Navier-Stokes equations with vacuum state in one dimension. Communications on Pure & Applied Analysis, 2004, 3 (4) : 675-694. doi: 10.3934/cpaa.2004.3.675

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (229)
  • HTML views (547)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences