American Institute of Mathematical Sciences

Advanced
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, 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]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[2]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100
[3]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380
[4]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073
[5]

Thomas Bartsch, Tian Xu. Strongly localized semiclassical states for nonlinear Dirac equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 29-60. doi: 10.3934/dcds.2020297
[6]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264
[7]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272
[8]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020050
[9]

Nguyen Thi Kim Son, Nguyen Phuong Dong, Le Hoang Son, Alireza Khastan, Hoang Viet Long. Complete controllability for a class of fractional evolution equations with uncertainty. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020104
[10]

Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323
[11]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[12]

Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249
[13]

Xuhui Peng, Rangrang Zhang. Approximations of stochastic 3D tamed Navier-Stokes equations. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5337-5365. doi: 10.3934/cpaa.2020241
[14]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377
[15]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047
[16]

Alberto Bressan, Wen Shen. A posteriori error estimates for self-similar solutions to the Euler equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 113-130. doi: 10.3934/dcds.2020168
[17]

Serena Dipierro, Benedetta Pellacci, Enrico Valdinoci, Gianmaria Verzini. Time-fractional equations with reaction terms: Fundamental solutions and asymptotics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 257-275. doi: 10.3934/dcds.2020137
[18]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336
[19]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051
[20]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (131)
  • HTML views (470)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences