# American Institute of Mathematical Sciences

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

## The singularity attack to the multivariate signature scheme HIMQ-3

 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.

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.

2020 Impact Factor: 0.935