Cryptology ePrint Archive: Report 2019/895

The Singularity Attack to the Multivariate Signature Scheme Himq-3

Jintai Ding and Zheng Zhang and Joshua Deaton and Vishakha

Abstract: 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 oil vinegar signature scheme family. It has a multilayer structure but it uses a cycle system to invert the central map. The signing process of Himq-3 is very fast, and it has small signatures.

In this paper we present a cryptanalysis of Himq-3. We show that inherent to the signing process is a leakage of information of the private key. Using this information one can forge a signature.

Category / Keywords: public-key cryptography / Multivariate public key cryptosystem, Cryptanalysis, Oil Vinegar Signature Scheme

Date: received 2 Aug 2019, last revised 13 Sep 2019

Contact author: zhzhang1989 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190914:004437 (All versions of this report)

Short URL: ia.cr/2019/895


[ Cryptology ePrint archive ]