International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Kipnis-Shamir's Attack on HFE Revisited

Authors:
Xin Jiang
Jintai Ding
Lei Hu
Download:
URL: http://eprint.iacr.org/2007/203
Search ePrint
Search Google
Abstract: In this paper, we show that the claims in the original Kipnis-Shamir's attack on the HFE cryptosystems and the improved attack by Courtois that the complexity of the attacks is polynomial in terms of the number of variables are invalid. We present computer experiments and a theoretical argument using basic algebraic geometry to explain why it is so. Furthermore we show that even with the help of the powerful new Gr\"{o}bner basis algorithm like $F_4$, the Kipnis-Shamir's attack still should be exponential not polynomial. This again is supported by our theoretical argument.
BibTeX
@misc{eprint-2007-13484,
  title={Kipnis-Shamir's Attack on HFE Revisited},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography /},
  url={http://eprint.iacr.org/2007/203},
  note={ ding@math.uc.edu 13663 received 30 May 2007},
  author={Xin Jiang and Jintai Ding and Lei Hu},
  year=2007
}