Paper 2015/1160

Cryptanalysis of multi-HFE

Yasufumi Hashimoto

Abstract

Multi-HFE (Chen et al., 2009) is one of cryptosystems whose public key is a set of multivariate quadratic forms over a finite field. Its quadratic forms are constructed by a set of multivariate quadratic forms over an extension field. Recently, Bettale et al. (2013) have studied the security of HFE and multi-HFE against the min-rank attack and found that multi-HFE is not more secure than HFE of similar size. In the present paper, we propose a new attack on multi-HFE by using a diagonalization approach. As a result, our attack can recover equivalent secret keys of multi-HFE in polynomial time for odd characteristic case. In fact, we experimentally succeeded to recover equivalent secret keys of several examples of multi-HFE in about fifteen seconds on average, which was recovered in about nine days by the min-rank attack.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
hashimoto @ math u-ryukyu ac jp
History
2015-12-02: received
Short URL
https://ia.cr/2015/1160
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1160,
      author = {Yasufumi Hashimoto},
      title = {Cryptanalysis of multi-HFE},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1160},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1160}},
      url = {https://eprint.iacr.org/2015/1160}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.