International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalysis of HFE

Authors:
Ilia Toli
Download:
URL: http://eprint.iacr.org/2003/101
Search ePrint
Search Google
Abstract: Out of the public key ($\mathcal{PK}$) we recover a polynomial of the same shape as the private polynomial. Then we give an algorithm for solving such a special-form polynomial. This fact puts an eavesdropper in the same position with a legitimate user in decryption. An upper bound for the complexity of that all is $\mathcal{O}(n^6)$ bit operations for $n$ the degree of the field extension.
BibTeX
@misc{eprint-2003-11816,
  title={Cryptanalysis of HFE},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography /},
  url={http://eprint.iacr.org/2003/101},
  note={ toli@posso.dm.unipi.it 12199 received 14 May 2003, last revised 27 May 2003, withdrawn 27 May 2003},
  author={Ilia Toli},
  year=2003
}