Algebraic attack on HFE revisited

Jintai Ding*, Dieter Schmidt, Fabian Werner

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

26 Citations (Scopus)

Abstract

In this paper, we study how the algebraic attack on the HFE multivariate public key cryptosystem works if we build an HFE cryptosystem on a finite field whose characteristic is not two. Using some very basic algebraic geometry we argue that when the characteristic is not two the algebraic attack should not be polynomial in the range of the parameters which are used in practical applications. We further support our claims with extensive experiments using the Magma implementation of F 4, which is currently the best publicly available implementation of the Gröbner basis algorithm. We present a new variant of the HFE cryptosystems, where we project the public key of HFE to a space of one dimension lower. This protects the system from the Kipnis-Shamir attack and makes the decryption process avoid multiple candidates for the plaintext. We propose an example for a practical application on GF(11) and suggest a test challenge on GF(7).

Original languageEnglish
Title of host publicationInformation Security - 11th International Conference, ISC 2008, Proceedings
Pages215-227
Number of pages13
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event11th International Conference on Information Security, ISC 2008 - Taipei, Taiwan, Province of China
Duration: 15 Sept 200818 Sept 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5222 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Information Security, ISC 2008
Country/TerritoryTaiwan, Province of China
CityTaipei
Period15/09/0818/09/08

Keywords

  • Gröbner basis
  • HFE
  • Multivariate public key cryptosystem

Fingerprint

Dive into the research topics of 'Algebraic attack on HFE revisited'. Together they form a unique fingerprint.

Cite this