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  February 2021 Early access  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.

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

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

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

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

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

[7]

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

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

[9]

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

[10]

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

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

[12]

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

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

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.

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

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

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

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

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

[7]

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

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

[9]

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

[10]

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

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

[12]

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

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

[1]

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
[2]

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
[3]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[4]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[5]

Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022031
[6]

Yang Lu, Quanling Zhang, Jiguo Li. An improved certificateless strong key-insulated signature scheme in the standard model. Advances in Mathematics of Communications, 2015, 9 (3) : 353-373. doi: 10.3934/amc.2015.9.353
[7]

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
[8]

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
[9]

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
[10]

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
[11]

Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247
[12]

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

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
[14]

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
[15]

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
[16]

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
[17]

Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87
[18]

Ke Gu, Xinying Dong, Linyu Wang. Efficient traceable ring signature scheme without pairings. Advances in Mathematics of Communications, 2020, 14 (2) : 207-232. doi: 10.3934/amc.2020016
[19]

Philip Lafrance, Alfred Menezes. On the security of the WOTS-PRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185-193. doi: 10.3934/amc.2019012
[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (462)
  • HTML views (560)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy