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

Jintai Ding Department of Mathematical Sciences,University of Cincinnati, OH, 45221, USA; TU Darmstadt, Fachbereich Informatik, 64289, Darmstadt, Germany Lei Hu State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing 100049, China Xuyun Nie State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing 100049, China Jianyu Li State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing 100049, China John Wagner Department of Mathematical Sciences,University of Cincinnati, OH, 45221, USA

TBD mathscidoc:2207.43020

Public Key Cryptography – PKC 2007, 233-248, 2007.4
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}-multiplications, after performing once for any given 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.
No keywords uploaded!
[ Download ] [ 2022-07-11 11:23:37 uploaded by dingjt ] [ 301 downloads ] [ 0 comments ]
@inproceedings{jintai2007high,
  title={High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems},
  author={Jintai Ding, Lei Hu, Xuyun Nie, Jianyu Li, and John Wagner},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220711112337078720597},
  booktitle={Public Key Cryptography – PKC 2007},
  pages={233-248},
  year={2007},
}
Jintai Ding, Lei Hu, Xuyun Nie, Jianyu Li, and John Wagner. High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems. 2007. In Public Key Cryptography – PKC 2007. pp.233-248. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220711112337078720597.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved