-
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. |
[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
Other articles
by authors
[Back to Top]