TY - GEN
T1 - A Complete Cryptanalysis of the Post-Quantum Multivariate Signature Scheme Himq-3
AU - Ding, Jintai
AU - Zhang, Zheng
AU - Deaton, Joshua
AU - Wang, Lih Chung
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - In 2017 Kyung-Ah Shim et al. proposed a multivariate signature scheme called Himq-3 which is a submission to National Institute of Standards and Technology (NIST) standardization process of post-quantum cryptosystems. The Himq-3 signature scheme can be classified into the oil vinegar signature scheme family. Similar to the rainbow signature scheme, the Himq-3 signature scheme uses a multilayer structure to shorten the signature size. Moreover the signing process is very fast due to a special system called L-inveritble cycle system that is used to invert the central map. In this paper, we provide a complete cryptanalysis to the Himq-3 signature scheme. We describe a new attack method called the singularity attack. This attack is based on the observation that the variables in the L-invertible cycle system are not allowed to be zero in a valid signature. For the completeness, we show step by step how variables and layers can be separated so that signature forgery can be performed. We claim that the complexity of our attack is much lower than the proposed security level.
AB - In 2017 Kyung-Ah Shim et al. proposed a multivariate signature scheme called Himq-3 which is a submission to National Institute of Standards and Technology (NIST) standardization process of post-quantum cryptosystems. The Himq-3 signature scheme can be classified into the oil vinegar signature scheme family. Similar to the rainbow signature scheme, the Himq-3 signature scheme uses a multilayer structure to shorten the signature size. Moreover the signing process is very fast due to a special system called L-inveritble cycle system that is used to invert the central map. In this paper, we provide a complete cryptanalysis to the Himq-3 signature scheme. We describe a new attack method called the singularity attack. This attack is based on the observation that the variables in the L-invertible cycle system are not allowed to be zero in a valid signature. For the completeness, we show step by step how variables and layers can be separated so that signature forgery can be performed. We claim that the complexity of our attack is much lower than the proposed security level.
KW - Cryptanalysis
KW - Multivariate public key cryptography
KW - Oil vinegar signature scheme
KW - Post-quantum cryptography
UR - http://www.scopus.com/inward/record.url?scp=85097654043&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-61078-4_24
DO - 10.1007/978-3-030-61078-4_24
M3 - Conference Proceeding
AN - SCOPUS:85097654043
SN - 9783030610777
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 422
EP - 440
BT - Information and Communications Security - 22nd International Conference, ICICS 2020, Proceedings
A2 - Meng, Weizhi
A2 - Gollmann, Dieter
A2 - Jensen, Christian D.
A2 - Zhou, Jianying
PB - Springer Science and Business Media Deutschland GmbH
T2 - 22nd International Conference on Information and Communications Security, ICICS 2020
Y2 - 24 August 2020 through 26 August 2020
ER -