-
Previous Article
A class of linear codes and their complete weight enumerators
- AMC Home
- This Issue
-
Next Article
A new class of $ p $-ary regular bent functions
The singularity attack to the multivariate signature scheme HIMQ-3
Department of Mathematical Science, University of Cincinnati, USA |
We present a cryptanalysis of a signature scheme HIMQ-3 due to Kyung-Ah Shim et al [
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. |
[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. 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. |
[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. |
[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. |
[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. 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. |
[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. 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. |
[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. |
[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. |
[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. 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
Other articles
by authors
[Back to Top]