Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases
Identifieur interne : 007F83 ( Main/Merge ); précédent : 007F82; suivant : 007F84Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases
Auteurs : Jean-Charles Faugere [France] ; Antoine Joux [France]Source :
- Lecture notes in computer science [ 0302-9743 ] ; 2003.
Descripteurs français
- Pascal (Inist)
- Wicri :
- topic : Cryptographie.
English descriptors
- KwdEn :
Abstract
In this paper, we review and explain the existing algebraic cryptanalysis of multivariate cryptosystems from the hidden field equation (HFE) family. These cryptanalysis break cryptosystems in the HFE family by solving multivariate systems of equations. In this paper we present a new and efficient attack of this cryptosystem based on fast algorithms for computing Gröbner basis. In particular it was was possible to break the first HFE challenge (80 bits) in only two days of CPU time by using the new algorithm F5 implemented in C. From a theoretical point of view we study the algebraic properties of the equations produced by instance of the HFE cryptosystems and show why they yield systems of equations easier to solve than random systems of quadratic equations of the same sizes. Moreover we are able to bound the maximal degree occuring in the Gröbner basis computation. As a consequence, we gain a deeper understanding of the algebraic cryptanalysis against these cryptosystems. We use this understanding to devise a specific algorithm based on sparse linear algebra. In general, we conclude that the cryptanalysis of HFE can be performed in polynomial time. We also revisit the security estimates for existing schemes in the *FE family.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000697
- to stream PascalFrancis, to step Curation: 000344
- to stream PascalFrancis, to step Checkpoint: 000724
Links to Exploration step
Pascal:04-0201048Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases</title><author><name sortKey="Faugere, Jean Charles" sort="Faugere, Jean Charles" uniqKey="Faugere J" first="Jean-Charles" last="Faugere">Jean-Charles Faugere</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>1 Projet SPACES LIP6/LORIA CNRS/UPMC/INRIA DCSSI/Crypto Lab, 51 Bd de Latour-Maubourg</s1><s2>75700 PARIS </s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">PARIS </settlement></placeName></affiliation></author><author><name sortKey="Joux, Antoine" sort="Joux, Antoine" uniqKey="Joux A" first="Antoine" last="Joux">Antoine Joux</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>1 Projet SPACES LIP6/LORIA CNRS/UPMC/INRIA DCSSI/Crypto Lab, 51 Bd de Latour-Maubourg</s1><s2>75700 PARIS </s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">PARIS </settlement></placeName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">04-0201048</idno><date when="2003">2003</date><idno type="stanalyst">PASCAL 04-0201048 INIST</idno><idno type="RBID">Pascal:04-0201048</idno><idno type="wicri:Area/PascalFrancis/Corpus">000697</idno><idno type="wicri:Area/PascalFrancis/Curation">000344</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000724</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000724</idno><idno type="wicri:doubleKey">0302-9743:2003:Faugere J:algebraic:cryptanalysis:of</idno><idno type="wicri:Area/Main/Merge">007F83</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases</title><author><name sortKey="Faugere, Jean Charles" sort="Faugere, Jean Charles" uniqKey="Faugere J" first="Jean-Charles" last="Faugere">Jean-Charles Faugere</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>1 Projet SPACES LIP6/LORIA CNRS/UPMC/INRIA DCSSI/Crypto Lab, 51 Bd de Latour-Maubourg</s1><s2>75700 PARIS </s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">PARIS </settlement></placeName></affiliation></author><author><name sortKey="Joux, Antoine" sort="Joux, Antoine" uniqKey="Joux A" first="Antoine" last="Joux">Antoine Joux</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>1 Projet SPACES LIP6/LORIA CNRS/UPMC/INRIA DCSSI/Crypto Lab, 51 Bd de Latour-Maubourg</s1><s2>75700 PARIS </s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">PARIS </settlement></placeName></affiliation></author></analytic><series><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno><imprint><date when="2003">2003</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algebraic equation</term><term>Cryptanalysis</term><term>Cryptography</term><term>Fast algorithm</term><term>Field equation</term><term>Gröbner basis</term><term>Linear algebra</term><term>Polynomial time</term><term>Probabilistic approach</term><term>Quadratic equation</term><term>Quadratic system</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Cryptanalyse</term><term>Cryptographie</term><term>Temps polynomial</term><term>Equation algébrique</term><term>Equation champ</term><term>Base Gröbner</term><term>Algorithme rapide</term><term>Approche probabiliste</term><term>Système quadratique</term><term>Equation quadratique</term><term>Algèbre linéaire</term></keywords><keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Cryptographie</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In this paper, we review and explain the existing algebraic cryptanalysis of multivariate cryptosystems from the hidden field equation (HFE) family. These cryptanalysis break cryptosystems in the HFE family by solving multivariate systems of equations. In this paper we present a new and efficient attack of this cryptosystem based on fast algorithms for computing Gröbner basis. In particular it was was possible to break the first HFE challenge (80 bits) in only two days of CPU time by using the new algorithm F5 implemented in C. From a theoretical point of view we study the algebraic properties of the equations produced by instance of the HFE cryptosystems and show why they yield systems of equations easier to solve than random systems of quadratic equations of the same sizes. Moreover we are able to bound the maximal degree occuring in the Gröbner basis computation. As a consequence, we gain a deeper understanding of the algebraic cryptanalysis against these cryptosystems. We use this understanding to devise a specific algorithm based on sparse linear algebra. In general, we conclude that the cryptanalysis of HFE can be performed in polynomial time. We also revisit the security estimates for existing schemes in the *FE family.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Île-de-France</li></region><settlement><li>PARIS </li></settlement></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Faugere, Jean Charles" sort="Faugere, Jean Charles" uniqKey="Faugere J" first="Jean-Charles" last="Faugere">Jean-Charles Faugere</name></region><name sortKey="Joux, Antoine" sort="Joux, Antoine" uniqKey="Joux A" first="Antoine" last="Joux">Antoine Joux</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007F83 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 007F83 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= Pascal:04-0201048
|texte= Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases
}}
| This area was generated with Dilib version V0.6.33. |  |