Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases
Identifieur interne : 000724 ( PascalFrancis/Checkpoint ); précédent : 000723; suivant : 000725Algebraic 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.
Affiliations:
Links toward previous steps (curation, corpus...)
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></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><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0></fA01><fA05><s2>2729</s2></fA05><fA08 i1="01" i2="1" l="ENG"><s1>Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases</s1></fA08><fA09 i1="01" i2="1" l="ENG"><s1>Advances in cryptology : CRYPTO 2003 : Santa Barbara CA, 17-21 August 2003</s1></fA09><fA11 i1="01" i2="1"><s1>FAUGERE (Jean-Charles)</s1></fA11><fA11 i1="02" i2="1"><s1>JOUX (Antoine)</s1></fA11><fA12 i1="01" i2="1"><s1>BONEH (Dan)</s1><s9>ed.</s9></fA12><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></fA14><fA20><s1>44-60</s1></fA20><fA21><s1>2003</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA26 i1="01"><s0>3-540-40674-3</s0></fA26><fA43 i1="01"><s1>INIST</s1><s2>16343</s2><s5>354000117805670030</s5></fA43><fA44><s0>0000</s0><s1>© 2004 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>25 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>04-0201048</s0></fA47><fA60><s1>P</s1><s2>C</s2></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0></fA64><fA66 i1="01"><s0>DEU</s0></fA66><fC01 i1="01" l="ENG"><s0>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.</s0></fC01><fC02 i1="01" i2="X"><s0>001D02B01</s0></fC02><fC02 i1="02" i2="X"><s0>001D04A04E</s0></fC02><fC02 i1="03" i2="X"><s0>001D02B07C</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Cryptanalyse</s0><s5>02</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Cryptanalysis</s0><s5>02</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Criptoanálisis</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Cryptographie</s0><s5>03</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Cryptography</s0><s5>03</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Criptografía</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Temps polynomial</s0><s5>04</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Polynomial time</s0><s5>04</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>Tiempo polinomial</s0><s5>04</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Equation algébrique</s0><s5>16</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Algebraic equation</s0><s5>16</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Ecuación algebraica</s0><s5>16</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Equation champ</s0><s5>17</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Field equation</s0><s5>17</s5></fC03><fC03 i1="05" i2="X" l="SPA"><s0>Ecuación campo</s0><s5>17</s5></fC03><fC03 i1="06" i2="X" l="FRE"><s0>Base Gröbner</s0><s5>18</s5></fC03><fC03 i1="06" i2="X" l="ENG"><s0>Gröbner basis</s0><s5>18</s5></fC03><fC03 i1="06" i2="X" l="SPA"><s0>Base Gröbner</s0><s5>18</s5></fC03><fC03 i1="07" i2="X" l="FRE"><s0>Algorithme rapide</s0><s5>19</s5></fC03><fC03 i1="07" i2="X" l="ENG"><s0>Fast algorithm</s0><s5>19</s5></fC03><fC03 i1="07" i2="X" l="SPA"><s0>Algoritmo rápido</s0><s5>19</s5></fC03><fC03 i1="08" i2="X" l="FRE"><s0>Approche probabiliste</s0><s5>20</s5></fC03><fC03 i1="08" i2="X" l="ENG"><s0>Probabilistic approach</s0><s5>20</s5></fC03><fC03 i1="08" i2="X" l="SPA"><s0>Enfoque probabilista</s0><s5>20</s5></fC03><fC03 i1="09" i2="X" l="FRE"><s0>Système quadratique</s0><s5>21</s5></fC03><fC03 i1="09" i2="X" l="ENG"><s0>Quadratic system</s0><s5>21</s5></fC03><fC03 i1="09" i2="X" l="SPA"><s0>Sistema cuadrático</s0><s5>21</s5></fC03><fC03 i1="10" i2="X" l="FRE"><s0>Equation quadratique</s0><s5>22</s5></fC03><fC03 i1="10" i2="X" l="ENG"><s0>Quadratic equation</s0><s5>22</s5></fC03><fC03 i1="10" i2="X" l="SPA"><s0>Ecuación segundo grado</s0><s5>22</s5></fC03><fC03 i1="11" i2="X" l="FRE"><s0>Algèbre linéaire</s0><s5>23</s5></fC03><fC03 i1="11" i2="X" l="ENG"><s0>Linear algebra</s0><s5>23</s5></fC03><fC03 i1="11" i2="X" l="SPA"><s0>Algebra lineal</s0><s5>23</s5></fC03><fN21><s1>138</s1></fN21><fN82><s1>PSI</s1></fN82></pA><pR><fA30 i1="01" i2="1" l="ENG"><s1>Annual international cryptology conference</s1><s2>23</s2><s3>Santa Barbara CA USA</s3><s4>2003-08-17</s4></fA30></pR></standard></inist><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/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000724 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000724 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Checkpoint
|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. |  |