The Singularity Attack to the Multivariate Signature Scheme Himq-3

Jintai Ding; Zheng Zhang; Joshua Deaton; Vishakha

Paper 2019/895

The Singularity Attack to the Multivariate Signature Scheme Himq-3

Jintai Ding, Zheng Zhang, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Multivariate public key cryptosystem Cryptanalysis Oil Vinegar Signature Scheme
Contact author(s): zhzhang1989 @ gmail com
History: 2019-09-14: last of 3 revisions; 2019-08-05: received; See all versions
Short URL: https://ia.cr/2019/895
License: CC BY

BibTeX

@misc{cryptoeprint:2019/895,
      author = {Jintai Ding and Zheng Zhang and Joshua Deaton and Vishakha},
      title = {The Singularity Attack to the Multivariate Signature Scheme Himq-3},
      howpublished = {Cryptology ePrint Archive, Paper 2019/895},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/895}},
      url = {https://eprint.iacr.org/2019/895}
}