Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography /

Date: received 30 Nov 2015

Contact author: hashimoto at math u-ryukyu ac jp

Available format(s): PDF | BibTeX Citation

Version: 20151202:010602 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]