Cryptology ePrint Archive: Report 2003/101

Cryptanalysis of HFE

Ilia Toli

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.

Category / Keywords: public-key cryptography /

Date: received 14 May 2003, last revised 27 May 2003, withdrawn 27 May 2003

Contact author: toli at posso dm unipi it

Available format(s): (-- withdrawn --)

Note: Minor changes expected.

Version: 20030527:165230 (All versions of this report)

Short URL: ia.cr/2003/101

Discussion forum: Show discussion | Start new discussion