**High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems**

*Jintai Ding, Lei Hu, Xuyun Nie, Jianyu li, John Wagner*

**Abstract: **In the CT-track of the 2006 RSA conference, a new multivariate
public key cryptosystem, which is called the Medium Field Equation
(MFE) multivariate public key cryptosystem, is proposed by Wang,
Yang, Hu and Lai. We use the second order linearization equation
attack method by Patarin to break MFE. Given a ciphertext, we can
derive the plaintext within $2^{23}$ $\F_{2^{16}}$-operations,
after performing once for any public key a computation of
complexity less than $2^{52}$. We also propose a high order
linearization equation (HOLE) attack on multivariate public key
cryptosystems, which is a further generalization of the (first and
second order) linearization equation (LE). This method can be used
to attack extensions of the current MFE.

**Category / Keywords: **public-key cryptography / multivariate PKC; algebraic cryptanalysis, high order linearization equation

**Date: **received 4 Oct 2006

**Contact author: **ding at math uc edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20061005:145310 (All versions of this report)

**Short URL: **ia.cr/2006/336

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]