International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jintai Ding
Lei Hu
Xuyun Nie
Jianyu li
John Wagner
Download:
URL: http://eprint.iacr.org/2006/336
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21827,
  title={High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / multivariate PKC; algebraic cryptanalysis, high order linearization equation},
  url={http://eprint.iacr.org/2006/336},
  note={ ding@math.uc.edu 13425 received 4 Oct 2006},
  author={Jintai Ding and Lei Hu and Xuyun Nie and Jianyu li and John Wagner},
  year=2006
}