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 N299c2b9168a847e997005d00a128186a
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 N81eeb677f86a4dccb0b6e334caadb7ef
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf Ndfc952b008c14047b9b289fd3e60ed53
13 schema:name Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization
14 schema:pagination 19-30
15 schema:productId N16e4113dd7cb4b06b0f210e65873426b
16 N3b0d1a6c59d443689ddf38b8251cb948
17 Nd48e4eb0ce534d5fb9546a931f36fd4e
18 schema:publisher N42ccb65798684ab9b55fa1ce11ab307d
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 N5af3e428ce6d40b388f0d03f7f6ae5d0
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 N16e4113dd7cb4b06b0f210e65873426b schema:name readcube_id
29 schema:value dafc9fc5d771110681acaa617941f6888f1268dc5d6ef17eab52508e8a7a54e8
30 rdf:type schema:PropertyValue
31 N299c2b9168a847e997005d00a128186a rdf:first sg:person.011340712735.51
32 rdf:rest N3a3b7343b0ce4eee884d4cab3e73ad55
33 N3a3b7343b0ce4eee884d4cab3e73ad55 rdf:first sg:person.013646242633.29
34 rdf:rest Nfc20c6392caa44a5ad89ff7995067343
35 N3b0d1a6c59d443689ddf38b8251cb948 schema:name doi
36 schema:value 10.1007/3-540-48405-1_2
37 rdf:type schema:PropertyValue
38 N42ccb65798684ab9b55fa1ce11ab307d schema:location Berlin, Heidelberg
39 schema:name Springer Berlin Heidelberg
40 rdf:type schema:Organisation
41 N5af3e428ce6d40b388f0d03f7f6ae5d0 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N81eeb677f86a4dccb0b6e334caadb7ef rdf:first N8c99b21124f94511ac4a6afba8f63b11
44 rdf:rest rdf:nil
45 N8c99b21124f94511ac4a6afba8f63b11 schema:familyName Wiener
46 schema:givenName Michael
47 rdf:type schema:Person
48 Nad2616a548374f7fbd3ebd6a960e1f6d rdf:first sg:person.013052746407.28
49 rdf:rest rdf:nil
50 Nb6a5b5d2c30245e891f15e0975f5959e schema:name NDS Technologies, Jerusalem, Israel
51 rdf:type schema:Organization
52 Nd48e4eb0ce534d5fb9546a931f36fd4e schema:name dimensions_id
53 schema:value pub.1045972569
54 rdf:type schema:PropertyValue
55 Ndfc952b008c14047b9b289fd3e60ed53 schema:isbn 978-3-540-48405-9
56 978-3-540-66347-8
57 schema:name Advances in Cryptology — CRYPTO’ 99
58 rdf:type schema:Book
59 Nebcef2d43cba40e68abe050458f489ba rdf:first sg:person.016464474377.73
60 rdf:rest Nad2616a548374f7fbd3ebd6a960e1f6d
61 Nfc20c6392caa44a5ad89ff7995067343 rdf:first sg:person.015623462027.31
62 rdf:rest Nebcef2d43cba40e68abe050458f489ba
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 Nb6a5b5d2c30245e891f15e0975f5959e
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)


...