Paper 2006/336

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

Jintai Ding, Lei Hu, Xuyun Nie, Jianyu li, and 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
multivariate PKCalgebraic cryptanalysishigh order linearization equation
Contact author(s)
ding @ math uc edu
History
2006-10-05: received
Short URL
https://ia.cr/2006/336
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/336,
      author = {Jintai Ding and Lei Hu and Xuyun Nie and Jianyu li and John Wagner},
      title = {High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2006/336},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/336}},
      url = {https://eprint.iacr.org/2006/336}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.