Cryptanalysis of multi-HFE

Yasufumi Hashimoto

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: CC BY

BibTeX

@misc{cryptoeprint:2015/1160,
      author = {Yasufumi Hashimoto},
      title = {Cryptanalysis of multi-{HFE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/1160},
      year = {2015},
      url = {https://eprint.iacr.org/2015/1160}
}