UCL  IRIS
Institutional Research Information Service
UCL Logo
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at https://www.ucl.ac.uk/finance/research/rs-contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
The security of Hidden Field Equations (HFE)
  • Publication Type:
    Conference
  • Authors:
    Courtois N
  • Publisher:
    Springer-Verlag
  • Publication date:
    2001
  • Place of publication:
    Berlin/Heidelberg, Germany
  • Pagination:
    266, 281
  • Published proceedings:
    Topics in Cryptology: CT-RSA 2001: The Cryptographers’ Track at RSA Conference 2001 San Francisco, CA, USA, April 8 -12, 2001: Proceedings
  • Volume:
    2020
  • Series:
    Lecture Notes in Computer Science
  • Editors:
    Naccache D
  • ISBN-10:
    3540418989
  • Status:
    Published
  • Language:
    English
  • Keywords:
    HFE Public Key Cryptosystem, Cryptanalysis
Abstract
We consider the basic version of the asymmetric cryptosy- stem HFE from Eurocrypt 96. We propose a notion of non-trivial equations as a tentative to account for a large class of attacks on one-way functions. We found equations that give experimental evidence that basic HFE can be broken in expected polynomial time for any constant degree d. It has been independently proven by Shamir and Kipnis [Crypto’99]. We designed and implemented a series of new advanced attacks that are much more efficient that the Shamir-Kipnis attack. They are practical for HFE degree d ≤ 24 and realistic up to d = 128. The 80-bit, 500$ Patarin’s 1st challenge on HFE can be broken in about 262. Our attack is subexponential and requires n 32log d computations. The original Shamir-Kipnis attack was in at least n log2 d . We show how to improve the Shamir-Kipnis attack, by using a better method of solving the involved algebraical problem MinRank. It becomes then in n 3 log d+O(1). All attacks fail for modified versions of HFE: HFE- (Asiacrypt’98), vHFE (Eurocrypt’99), Quartz (RSA’2000) and even for Flash (RSA’2000).
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
There are no UCL People associated with this publication
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by