Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases
Identifieur interne :
000697 ( PascalFrancis/Corpus );
précédent :
000696;
suivant :
000698
Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases
Auteurs : Jean-Charles Faugere ;
Antoine JouxSource :
-
Lecture notes in computer science [ 0302-9743 ] ; 2003.
RBID : Pascal:04-0201048
Descripteurs français
- Pascal (Inist)
- Cryptanalyse,
Cryptographie,
Temps polynomial,
Equation algébrique,
Equation champ,
Base Gröbner,
Algorithme rapide,
Approche probabiliste,
Système quadratique,
Equation quadratique,
Algèbre linéaire.
English descriptors
- KwdEn :
- Algebraic equation,
Cryptanalysis,
Cryptography,
Fast algorithm,
Field equation,
Gröbner basis,
Linear algebra,
Polynomial time,
Probabilistic approach,
Quadratic equation,
Quadratic system.
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.
Notice en format standard (ISO 2709)
Pour connaître la documentation sur le format Inist Standard.
| pA |
| A01 | 01 | 1 | | @0 0302-9743 |
|---|
| A05 | | | | @2 2729 |
|---|
| A08 | 01 | 1 | ENG | @1 Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases |
|---|
| A09 | 01 | 1 | ENG | @1 Advances in cryptology : CRYPTO 2003 : Santa Barbara CA, 17-21 August 2003 |
|---|
| A11 | 01 | 1 | | @1 FAUGERE (Jean-Charles) |
|---|
| A11 | 02 | 1 | | @1 JOUX (Antoine) |
|---|
| A12 | 01 | 1 | | @1 BONEH (Dan) @9 ed. |
|---|
| A14 | 01 | | | @1 1 Projet SPACES LIP6/LORIA CNRS/UPMC/INRIA DCSSI/Crypto Lab, 51 Bd de Latour-Maubourg @2 75700 PARIS @3 FRA @Z 1 aut. @Z 2 aut. |
|---|
| A20 | | | | @1 44-60 |
|---|
| A21 | | | | @1 2003 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A26 | 01 | | | @0 3-540-40674-3 |
|---|
| A43 | 01 | | | @1 INIST @2 16343 @5 354000117805670030 |
|---|
| A44 | | | | @0 0000 @1 © 2004 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 25 ref. |
|---|
| A47 | 01 | 1 | | @0 04-0201048 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | 01 | 1 | | @0 Lecture notes in computer science |
|---|
| A66 | 01 | | | @0 DEU |
|---|
| C01 | 01 | | ENG | @0 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. |
|---|
| C02 | 01 | X | | @0 001D02B01 |
|---|
| C02 | 02 | X | | @0 001D04A04E |
|---|
| C02 | 03 | X | | @0 001D02B07C |
|---|
| C03 | 01 | X | FRE | @0 Cryptanalyse @5 02 |
|---|
| C03 | 01 | X | ENG | @0 Cryptanalysis @5 02 |
|---|
| C03 | 01 | X | SPA | @0 Criptoanálisis @5 02 |
|---|
| C03 | 02 | X | FRE | @0 Cryptographie @5 03 |
|---|
| C03 | 02 | X | ENG | @0 Cryptography @5 03 |
|---|
| C03 | 02 | X | SPA | @0 Criptografía @5 03 |
|---|
| C03 | 03 | X | FRE | @0 Temps polynomial @5 04 |
|---|
| C03 | 03 | X | ENG | @0 Polynomial time @5 04 |
|---|
| C03 | 03 | X | SPA | @0 Tiempo polinomial @5 04 |
|---|
| C03 | 04 | X | FRE | @0 Equation algébrique @5 16 |
|---|
| C03 | 04 | X | ENG | @0 Algebraic equation @5 16 |
|---|
| C03 | 04 | X | SPA | @0 Ecuación algebraica @5 16 |
|---|
| C03 | 05 | X | FRE | @0 Equation champ @5 17 |
|---|
| C03 | 05 | X | ENG | @0 Field equation @5 17 |
|---|
| C03 | 05 | X | SPA | @0 Ecuación campo @5 17 |
|---|
| C03 | 06 | X | FRE | @0 Base Gröbner @5 18 |
|---|
| C03 | 06 | X | ENG | @0 Gröbner basis @5 18 |
|---|
| C03 | 06 | X | SPA | @0 Base Gröbner @5 18 |
|---|
| C03 | 07 | X | FRE | @0 Algorithme rapide @5 19 |
|---|
| C03 | 07 | X | ENG | @0 Fast algorithm @5 19 |
|---|
| C03 | 07 | X | SPA | @0 Algoritmo rápido @5 19 |
|---|
| C03 | 08 | X | FRE | @0 Approche probabiliste @5 20 |
|---|
| C03 | 08 | X | ENG | @0 Probabilistic approach @5 20 |
|---|
| C03 | 08 | X | SPA | @0 Enfoque probabilista @5 20 |
|---|
| C03 | 09 | X | FRE | @0 Système quadratique @5 21 |
|---|
| C03 | 09 | X | ENG | @0 Quadratic system @5 21 |
|---|
| C03 | 09 | X | SPA | @0 Sistema cuadrático @5 21 |
|---|
| C03 | 10 | X | FRE | @0 Equation quadratique @5 22 |
|---|
| C03 | 10 | X | ENG | @0 Quadratic equation @5 22 |
|---|
| C03 | 10 | X | SPA | @0 Ecuación segundo grado @5 22 |
|---|
| C03 | 11 | X | FRE | @0 Algèbre linéaire @5 23 |
|---|
| C03 | 11 | X | ENG | @0 Linear algebra @5 23 |
|---|
| C03 | 11 | X | SPA | @0 Algebra lineal @5 23 |
|---|
| N21 | | | | @1 138 |
|---|
| N82 | | | | @1 PSI |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 Annual international cryptology conference @2 23 @3 Santa Barbara CA USA @4 2003-08-17 |
|---|
|
|---|
Format Inist (serveur)
| NO : | PASCAL 04-0201048 INIST |
|---|
| ET : | Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases |
|---|
| AU : | FAUGERE (Jean-Charles); JOUX (Antoine); BONEH (Dan) |
|---|
| AF : | 1 Projet SPACES LIP6/LORIA CNRS/UPMC/INRIA DCSSI/Crypto Lab, 51 Bd de Latour-Maubourg/75700 PARIS /France (1 aut., 2 aut.) |
|---|
| DT : | Publication en série; Congrès; Niveau analytique |
|---|
| SO : | Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2003; Vol. 2729; Pp. 44-60; Bibl. 25 ref. |
|---|
| LA : | Anglais |
|---|
| EA : | 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. |
|---|
| CC : | 001D02B01; 001D04A04E; 001D02B07C |
|---|
| FD : | Cryptanalyse; Cryptographie; Temps polynomial; Equation algébrique; Equation champ; Base Gröbner; Algorithme rapide; Approche probabiliste; Système quadratique; Equation quadratique; Algèbre linéaire |
|---|
| ED : | Cryptanalysis; Cryptography; Polynomial time; Algebraic equation; Field equation; Gröbner basis; Fast algorithm; Probabilistic approach; Quadratic system; Quadratic equation; Linear algebra |
|---|
| SD : | Criptoanálisis; Criptografía; Tiempo polinomial; Ecuación algebraica; Ecuación campo; Base Gröbner; Algoritmo rápido; Enfoque probabilista; Sistema cuadrático; Ecuación segundo grado; Algebra lineal |
|---|
| LO : | INIST-16343.354000117805670030 |
|---|
| ID : | 04-0201048 |
|---|
Links to Exploration step
Pascal:04-0201048
Le 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><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><author><name sortKey="Joux, Antoine" sort="Joux, Antoine" uniqKey="Joux A" first="Antoine" last="Joux">Antoine Joux</name>
<affiliation><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><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>
</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><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><author><name sortKey="Joux, Antoine" sort="Joux, Antoine" uniqKey="Joux A" first="Antoine" last="Joux">Antoine Joux</name>
<affiliation><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><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><seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt><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><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><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><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><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><server><NO>PASCAL 04-0201048 INIST</NO>
<ET>Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases</ET>
<AU>FAUGERE (Jean-Charles); JOUX (Antoine); BONEH (Dan)</AU>
<AF>1 Projet SPACES LIP6/LORIA CNRS/UPMC/INRIA DCSSI/Crypto Lab, 51 Bd de Latour-Maubourg/75700 PARIS /France (1 aut., 2 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2003; Vol. 2729; Pp. 44-60; Bibl. 25 ref.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D02B01; 001D04A04E; 001D02B07C</CC>
<FD>Cryptanalyse; Cryptographie; Temps polynomial; Equation algébrique; Equation champ; Base Gröbner; Algorithme rapide; Approche probabiliste; Système quadratique; Equation quadratique; Algèbre linéaire</FD>
<ED>Cryptanalysis; Cryptography; Polynomial time; Algebraic equation; Field equation; Gröbner basis; Fast algorithm; Probabilistic approach; Quadratic system; Quadratic equation; Linear algebra</ED>
<SD>Criptoanálisis; Criptografía; Tiempo polinomial; Ecuación algebraica; Ecuación campo; Base Gröbner; Algoritmo rápido; Enfoque probabilista; Sistema cuadrático; Ecuación segundo grado; Algebra lineal</SD>
<LO>INIST-16343.354000117805670030</LO>
<ID>04-0201048</ID>
</server>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000697 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000697 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Corpus
|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.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022 |  |
