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

摘要

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.