A Complete Cryptanalysis of the Post-Quantum Multivariate Signature Scheme Himq-3

Jintai Ding Department of Mathematical Science, University of Cincinnati, Cincinnati, USA Zheng Zhang Department of Mathematical Science, University of Cincinnati, Cincinnati, USA Joshua Deaton Department of Mathematical Science, University of Cincinnati, Cincinnati, USA Lih-Chung Wang Department of Applied Mathematics, National Dong Hwa University, Shoufeng, Taiwan

TBD mathscidoc:2207.43091

ICICS 2020, 422-440, 2020.8
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.
No keywords uploaded!
[ Download ] [ 2022-07-15 11:04:09 uploaded by dingjt ] [ 374 downloads ] [ 0 comments ]
@inproceedings{jintai2020a,
  title={A Complete Cryptanalysis of the Post-Quantum Multivariate Signature Scheme Himq-3},
  author={Jintai Ding, Zheng Zhang, Joshua Deaton, and Lih-Chung Wang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220715110409656882670},
  booktitle={ICICS 2020},
  pages={422-440},
  year={2020},
}
Jintai Ding, Zheng Zhang, Joshua Deaton, and Lih-Chung Wang. A Complete Cryptanalysis of the Post-Quantum Multivariate Signature Scheme Himq-3. 2020. In ICICS 2020. pp.422-440. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220715110409656882670.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved