Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999

AUTHORS

Gerhard Goos , Juris Hartmanis , Jan van Leeuwen , Aviad Kipnis , Adi Shamir

ABSTRACT

The RSA public key cryptosystem is based on a single modular equation in one variable. A natural generalization of this approach is to consider systems of several modular equations in several variables. In this paper we consider Patarin’s Hidden Field Equations (HFE) scheme, which is believed to be one of the strongest schemes of this type. We represent the published system of multivariate polynomials by a single univariate polynomial of a special form over an extension field, and use it to reduce the cryptanalytic problem to a system of ∈m 2 quadratic equations in m variables over the extension field. Finally, we develop a new relinearization method for solving such systems for any constant ∈ > 0 in expected polynomial time. The new type of attack is quite general, and in a companion paper we use it to attack other multivariate algebraic schemes, such as the Dragon encryption and signature schemes. However, we would like to emphasize that the polynomial time complexities may be infeasibly large for some choices of the parameters, and thus some variants of these schemes may remain practically unbroken in spite of the new attack. More... »

PAGES

19-30

Book

TITLE

Advances in Cryptology — CRYPTO’ 99

ISBN

978-3-540-66347-8
978-3-540-48405-9

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48405-1_2

DOI

http://dx.doi.org/10.1007/3-540-48405-1_2

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1045972569


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "familyName": "Goos", 
        "givenName": "Gerhard", 
        "id": "sg:person.011340712735.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011340712735.51"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Hartmanis", 
        "givenName": "Juris", 
        "id": "sg:person.013646242633.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013646242633.29"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "id": "sg:person.015623462027.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015623462027.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "NDS Technologies, Jerusalem, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kipnis", 
        "givenName": "Aviad", 
        "id": "sg:person.016464474377.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016464474377.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science", 
          "id": "https://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Computer Science Dept., The Weizmann Institute, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shamir", 
        "givenName": "Adi", 
        "id": "sg:person.013052746407.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052746407.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1109/tit.1987.1057350", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061649462"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "The RSA public key cryptosystem is based on a single modular equation in one variable. A natural generalization of this approach is to consider systems of several modular equations in several variables. In this paper we consider Patarin\u2019s Hidden Field Equations (HFE) scheme, which is believed to be one of the strongest schemes of this type. We represent the published system of multivariate polynomials by a single univariate polynomial of a special form over an extension field, and use it to reduce the cryptanalytic problem to a system of \u2208m 2 quadratic equations in m variables over the extension field. Finally, we develop a new relinearization method for solving such systems for any constant \u2208 > 0 in expected polynomial time. The new type of attack is quite general, and in a companion paper we use it to attack other multivariate algebraic schemes, such as the Dragon encryption and signature schemes. However, we would like to emphasize that the polynomial time complexities may be infeasibly large for some choices of the parameters, and thus some variants of these schemes may remain practically unbroken in spite of the new attack.", 
    "editor": [
      {
        "familyName": "Wiener", 
        "givenName": "Michael", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48405-1_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66347-8", 
        "978-3-540-48405-9"
      ], 
      "name": "Advances in Cryptology \u2014 CRYPTO\u2019 99", 
      "type": "Book"
    }, 
    "name": "Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization", 
    "pagination": "19-30", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48405-1_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "dafc9fc5d771110681acaa617941f6888f1268dc5d6ef17eab52508e8a7a54e8"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045972569"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48405-1_2", 
      "https://app.dimensions.ai/details/publication/pub.1045972569"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T22:01", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8693_00000271.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-48405-1_2"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-48405-1_2'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-48405-1_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48405-1_2'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48405-1_2'


 

This table displays all metadata directly associated to this object as RDF triples.

95 TRIPLES      23 PREDICATES      28 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48405-1_2 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N7ef64e80aaa9456f9423d126443baab7
4 schema:citation https://doi.org/10.1109/tit.1987.1057350
5 schema:datePublished 1999
6 schema:datePublishedReg 1999-01-01
7 schema:description The RSA public key cryptosystem is based on a single modular equation in one variable. A natural generalization of this approach is to consider systems of several modular equations in several variables. In this paper we consider Patarin’s Hidden Field Equations (HFE) scheme, which is believed to be one of the strongest schemes of this type. We represent the published system of multivariate polynomials by a single univariate polynomial of a special form over an extension field, and use it to reduce the cryptanalytic problem to a system of ∈m 2 quadratic equations in m variables over the extension field. Finally, we develop a new relinearization method for solving such systems for any constant ∈ > 0 in expected polynomial time. The new type of attack is quite general, and in a companion paper we use it to attack other multivariate algebraic schemes, such as the Dragon encryption and signature schemes. However, we would like to emphasize that the polynomial time complexities may be infeasibly large for some choices of the parameters, and thus some variants of these schemes may remain practically unbroken in spite of the new attack.
8 schema:editor Naf871e7c1110404892982830c1dd8695
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf Ndf2e55c531c84a2ca5376991b3656e62
13 schema:name Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization
14 schema:pagination 19-30
15 schema:productId N1900c69838314b8c8fbfd5097d2be765
16 N1a2082920ad34ba8a468f6a3fff527c9
17 N942a18f739754d97a8dcd5844269fbd6
18 schema:publisher N227956a9fdba4418a9cc98cceb8f7229
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045972569
20 https://doi.org/10.1007/3-540-48405-1_2
21 schema:sdDatePublished 2019-04-15T22:01
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher Nd3d6de0790bb475ab8af01d4542f5fff
24 schema:url http://link.springer.com/10.1007/3-540-48405-1_2
25 sgo:license sg:explorer/license/
26 sgo:sdDataset chapters
27 rdf:type schema:Chapter
28 N1900c69838314b8c8fbfd5097d2be765 schema:name readcube_id
29 schema:value dafc9fc5d771110681acaa617941f6888f1268dc5d6ef17eab52508e8a7a54e8
30 rdf:type schema:PropertyValue
31 N1a2082920ad34ba8a468f6a3fff527c9 schema:name doi
32 schema:value 10.1007/3-540-48405-1_2
33 rdf:type schema:PropertyValue
34 N227956a9fdba4418a9cc98cceb8f7229 schema:location Berlin, Heidelberg
35 schema:name Springer Berlin Heidelberg
36 rdf:type schema:Organisation
37 N4c1812c4243b47469c6cce8333e1179f schema:familyName Wiener
38 schema:givenName Michael
39 rdf:type schema:Person
40 N59cbd385db1441929fb553b09e2aec4c rdf:first sg:person.013052746407.28
41 rdf:rest rdf:nil
42 N679a39b8a9b1464ea96b80beb4fa59e0 rdf:first sg:person.016464474377.73
43 rdf:rest N59cbd385db1441929fb553b09e2aec4c
44 N7ef64e80aaa9456f9423d126443baab7 rdf:first sg:person.011340712735.51
45 rdf:rest Nba92bec1221241adbc0aa6391c436af6
46 N942a18f739754d97a8dcd5844269fbd6 schema:name dimensions_id
47 schema:value pub.1045972569
48 rdf:type schema:PropertyValue
49 Nacc9b95b6dee42869c7e617a8755f2db rdf:first sg:person.015623462027.31
50 rdf:rest N679a39b8a9b1464ea96b80beb4fa59e0
51 Naf871e7c1110404892982830c1dd8695 rdf:first N4c1812c4243b47469c6cce8333e1179f
52 rdf:rest rdf:nil
53 Nba92bec1221241adbc0aa6391c436af6 rdf:first sg:person.013646242633.29
54 rdf:rest Nacc9b95b6dee42869c7e617a8755f2db
55 Nbcf1ad6bf6854a0197fd98fa411efcb0 schema:name NDS Technologies, Jerusalem, Israel
56 rdf:type schema:Organization
57 Nd3d6de0790bb475ab8af01d4542f5fff schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 Ndf2e55c531c84a2ca5376991b3656e62 schema:isbn 978-3-540-48405-9
60 978-3-540-66347-8
61 schema:name Advances in Cryptology — CRYPTO’ 99
62 rdf:type schema:Book
63 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
64 schema:name Mathematical Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
67 schema:name Pure Mathematics
68 rdf:type schema:DefinedTerm
69 sg:person.011340712735.51 schema:familyName Goos
70 schema:givenName Gerhard
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011340712735.51
72 rdf:type schema:Person
73 sg:person.013052746407.28 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
74 schema:familyName Shamir
75 schema:givenName Adi
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052746407.28
77 rdf:type schema:Person
78 sg:person.013646242633.29 schema:familyName Hartmanis
79 schema:givenName Juris
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013646242633.29
81 rdf:type schema:Person
82 sg:person.015623462027.31 schema:familyName van Leeuwen
83 schema:givenName Jan
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015623462027.31
85 rdf:type schema:Person
86 sg:person.016464474377.73 schema:affiliation Nbcf1ad6bf6854a0197fd98fa411efcb0
87 schema:familyName Kipnis
88 schema:givenName Aviad
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016464474377.73
90 rdf:type schema:Person
91 https://doi.org/10.1109/tit.1987.1057350 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061649462
92 rdf:type schema:CreativeWork
93 https://www.grid.ac/institutes/grid.13992.30 schema:alternateName Weizmann Institute of Science
94 schema:name Computer Science Dept., The Weizmann Institute, Rehovot, Israel
95 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...