-
Previous Article
Additive Toeplitz codes over $ \mathbb{F}_{4} $
- AMC Home
- This Issue
-
Next Article
New classes of strictly optimal low hit zone frequency hopping sequence sets
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] |
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] |
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 |
[3] |
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 |
[4] |
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 |
[5] |
Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117 |
[6] |
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 |
[7] |
Jinkui Liu, Shengjie Li. Multivariate spectral DY-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2017, 13 (1) : 283-295. doi: 10.3934/jimo.2016017 |
[8] |
Gusein Sh. Guseinov. Spectral method for deriving multivariate Poisson summation formulae. Communications on Pure & Applied Analysis, 2013, 12 (1) : 359-373. doi: 10.3934/cpaa.2013.12.359 |
[9] |
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 |
[10] |
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 |
[11] |
Zhong Wan, Chunhua Yang. New approach to global minimization of normal multivariate polynomial based on tensor. Journal of Industrial & Management Optimization, 2008, 4 (2) : 271-285. doi: 10.3934/jimo.2008.4.271 |
[12] |
Richard D. Neidinger. Efficient recurrence relations for univariate and multivariate Taylor series coefficients. Conference Publications, 2013, 2013 (special) : 587-596. doi: 10.3934/proc.2013.2013.587 |
[13] |
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 |
[14] |
Ke Gu, Xinying Dong, Linyu Wang. Efficient traceable ring signature scheme without pairings. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020016 |
[15] |
Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046 |
[16] |
Yaxian Xu, Ajay Jasra. Particle filters for inference of high-dimensional multivariate stochastic volatility models with cross-leverage effects. Foundations of Data Science, 2019, 1 (1) : 61-85. doi: 10.3934/fods.2019003 |
[17] |
Victor Meng Hwee Ong, David J. Nott, Taeryon Choi, Ajay Jasra. Flexible online multivariate regression with variational Bayes and the matrix-variate Dirichlet process. Foundations of Data Science, 2019, 1 (2) : 129-156. doi: 10.3934/fods.2019006 |
[18] |
Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215 |
[19] |
Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1 |
[20] |
Filippo Dell'Oro, Olivier Goubet, Youcef Mammeri, Vittorino Pata. A semidiscrete scheme for evolution equations with memory. Discrete & Continuous Dynamical Systems - A, 2019, 39 (10) : 5637-5658. doi: 10.3934/dcds.2019247 |
2018 Impact Factor: 0.879
Tools
Article outline
[Back to Top]