Algebraic Attack on HFE Revisited View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008

AUTHORS

Jintai Ding , Dieter Schmidt , Fabian Werner

ABSTRACT

In this paper, we study how the algebraic attack on the HFE multivariate public key cryptosystem works if we build an HFE cryptosystem on a finite field whose characteristic is not two. Using some very basic algebraic geometry we argue that when the characteristic is not two the algebraic attack should not be polynomial in the range of the parameters which are used in practical applications. We further support our claims with extensive experiments using the Magma implementation of F4, which is currently the best publicly available implementation of the Gröbner basis algorithm. We present a new variant of the HFE cryptosystems, where we project the public key of HFE to a space of one dimension lower. This protects the system from the Kipnis-Shamir attack and makes the decryption process avoid multiple candidates for the plaintext. We propose an example for a practical application on GF(11) and suggest a test challenge on GF(7). More... »

PAGES

215-227

References to SciGraph publications

  • 2003. Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases in ADVANCES IN CRYPTOLOGY - CRYPTO 2003
  • 2006. Multivariate Public Key Cryptosystems in NONE
  • 1988. Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’88
  • 2001. The Security of Hidden Field Equations (HFE) in TOPICS IN CRYPTOLOGY — CT-RSA 2001
  • 2008. Kipnis-Shamir Attack on HFE Revisited in INFORMATION SECURITY AND CRYPTOLOGY
  • 2006. Inverting HFE Is Quasipolynomial in ADVANCES IN CRYPTOLOGY - CRYPTO 2006
  • 1999. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization in ADVANCES IN CRYPTOLOGY — CRYPTO’ 99
  • Book

    TITLE

    Information Security

    ISBN

    978-3-540-85884-3
    978-3-540-85886-7

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-85886-7_15

    DOI

    http://dx.doi.org/10.1007/978-3-540-85886-7_15

    DIMENSIONS

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


    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": [
          {
            "affiliation": {
              "alternateName": "University of Cincinnati", 
              "id": "https://www.grid.ac/institutes/grid.24827.3b", 
              "name": [
                "University of Cincinnati"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ding", 
            "givenName": "Jintai", 
            "id": "sg:person.010723403013.04", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Cincinnati", 
              "id": "https://www.grid.ac/institutes/grid.24827.3b", 
              "name": [
                "University of Cincinnati"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Schmidt", 
            "givenName": "Dieter", 
            "id": "sg:person.015464666561.44", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015464666561.44"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technical University of Darmstadt", 
              "id": "https://www.grid.ac/institutes/grid.6546.1", 
              "name": [
                "Technical University of Darmstadt"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Werner", 
            "givenName": "Fabian", 
            "id": "sg:person.010621103143.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010621103143.01"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45353-9_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003163768", 
              "https://doi.org/10.1007/3-540-45353-9_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/780506.780516", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007436250"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-36946-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026168664", 
              "https://doi.org/10.1007/978-0-387-36946-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1026168664", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45961-8_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035601256", 
              "https://doi.org/10.1007/3-540-45961-8_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-4049(99)00005-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040947089"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-79499-8_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041791996", 
              "https://doi.org/10.1007/978-3-540-79499-8_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48405-1_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045972569", 
              "https://doi.org/10.1007/3-540-48405-1_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11818175_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048753453", 
              "https://doi.org/10.1007/11818175_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11818175_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048753453", 
              "https://doi.org/10.1007/11818175_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049476263", 
              "https://doi.org/10.1007/978-3-540-45146-4_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049476263", 
              "https://doi.org/10.1007/978-3-540-45146-4_3"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008", 
        "datePublishedReg": "2008-01-01", 
        "description": "In this paper, we study how the algebraic attack on the HFE multivariate public key cryptosystem works if we build an HFE cryptosystem on a finite field whose characteristic is not two. Using some very basic algebraic geometry we argue that when the characteristic is not two the algebraic attack should not be polynomial in the range of the parameters which are used in practical applications. We further support our claims with extensive experiments using the Magma implementation of F4, which is currently the best publicly available implementation of the Gr\u00f6bner basis algorithm. We present a new variant of the HFE cryptosystems, where we project the public key of HFE to a space of one dimension lower. This protects the system from the Kipnis-Shamir attack and makes the decryption process avoid multiple candidates for the plaintext. We propose an example for a practical application on GF(11) and suggest a test challenge on GF(7).", 
        "editor": [
          {
            "familyName": "Wu", 
            "givenName": "Tzong-Chen", 
            "type": "Person"
          }, 
          {
            "familyName": "Lei", 
            "givenName": "Chin-Laung", 
            "type": "Person"
          }, 
          {
            "familyName": "Rijmen", 
            "givenName": "Vincent", 
            "type": "Person"
          }, 
          {
            "familyName": "Lee", 
            "givenName": "Der-Tsai", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-85886-7_15", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-85884-3", 
            "978-3-540-85886-7"
          ], 
          "name": "Information Security", 
          "type": "Book"
        }, 
        "name": "Algebraic Attack on HFE Revisited", 
        "pagination": "215-227", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-85886-7_15"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c1dbddb4205939987ceb12d3fa70c504d6c6f77097faad573080f2f95270cc30"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1040695999"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-85886-7_15", 
          "https://app.dimensions.ai/details/publication/pub.1040695999"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T06:09", 
        "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/0000000350_0000000350/records_77557_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-85886-7_15"
      }
    ]
     

    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/978-3-540-85886-7_15'

    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/978-3-540-85886-7_15'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-85886-7_15'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-85886-7_15'


     

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

    133 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-85886-7_15 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N6986694144ca49ff9eb8377f65b27640
    4 schema:citation sg:pub.10.1007/11818175_20
    5 sg:pub.10.1007/3-540-45353-9_20
    6 sg:pub.10.1007/3-540-45961-8_39
    7 sg:pub.10.1007/3-540-48405-1_2
    8 sg:pub.10.1007/978-0-387-36946-4
    9 sg:pub.10.1007/978-3-540-45146-4_3
    10 sg:pub.10.1007/978-3-540-79499-8_31
    11 https://app.dimensions.ai/details/publication/pub.1026168664
    12 https://doi.org/10.1016/s0022-4049(99)00005-5
    13 https://doi.org/10.1145/780506.780516
    14 schema:datePublished 2008
    15 schema:datePublishedReg 2008-01-01
    16 schema:description In this paper, we study how the algebraic attack on the HFE multivariate public key cryptosystem works if we build an HFE cryptosystem on a finite field whose characteristic is not two. Using some very basic algebraic geometry we argue that when the characteristic is not two the algebraic attack should not be polynomial in the range of the parameters which are used in practical applications. We further support our claims with extensive experiments using the Magma implementation of F4, which is currently the best publicly available implementation of the Gröbner basis algorithm. We present a new variant of the HFE cryptosystems, where we project the public key of HFE to a space of one dimension lower. This protects the system from the Kipnis-Shamir attack and makes the decryption process avoid multiple candidates for the plaintext. We propose an example for a practical application on GF(11) and suggest a test challenge on GF(7).
    17 schema:editor N30d76549d8f043b3a53f0a7cda14f3f7
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N8262730cc0ec4c0aba7c75ba3cceee46
    22 schema:name Algebraic Attack on HFE Revisited
    23 schema:pagination 215-227
    24 schema:productId N2f359318fdd74d93a74ff5d5ae03dd5e
    25 Ncc8bc589c36b43adb487ec2ea894946d
    26 Nd35ea0ef44b54c03ad4a0fc8db5cdbf9
    27 schema:publisher N1d0325d71dd544489d311c7a6856bf10
    28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040695999
    29 https://doi.org/10.1007/978-3-540-85886-7_15
    30 schema:sdDatePublished 2019-04-16T06:09
    31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    32 schema:sdPublisher N58d3d139266b43959c4b9450d9609e5c
    33 schema:url https://link.springer.com/10.1007%2F978-3-540-85886-7_15
    34 sgo:license sg:explorer/license/
    35 sgo:sdDataset chapters
    36 rdf:type schema:Chapter
    37 N1d0325d71dd544489d311c7a6856bf10 schema:location Berlin, Heidelberg
    38 schema:name Springer Berlin Heidelberg
    39 rdf:type schema:Organisation
    40 N28cc5cc20b8e4832b51090e37b7bc65f schema:familyName Wu
    41 schema:givenName Tzong-Chen
    42 rdf:type schema:Person
    43 N2f359318fdd74d93a74ff5d5ae03dd5e schema:name doi
    44 schema:value 10.1007/978-3-540-85886-7_15
    45 rdf:type schema:PropertyValue
    46 N30d76549d8f043b3a53f0a7cda14f3f7 rdf:first N28cc5cc20b8e4832b51090e37b7bc65f
    47 rdf:rest Ncf1560302456490984e9d18bb9268be0
    48 N3307b0fc31c249ec864f289b25f23e77 rdf:first Nb92342ea5c6b4cebb09c7f05723fa5c8
    49 rdf:rest rdf:nil
    50 N5238c6d35a414a9589fdee60b999a4d4 rdf:first N92bac92799ef4c2fbf7e021d426be88f
    51 rdf:rest N3307b0fc31c249ec864f289b25f23e77
    52 N58d3d139266b43959c4b9450d9609e5c schema:name Springer Nature - SN SciGraph project
    53 rdf:type schema:Organization
    54 N6986694144ca49ff9eb8377f65b27640 rdf:first sg:person.010723403013.04
    55 rdf:rest N8e8761f6229a430e9e0b95a5e27155a6
    56 N72403df216ce4924946b4d5c37953bdc rdf:first sg:person.010621103143.01
    57 rdf:rest rdf:nil
    58 N8262730cc0ec4c0aba7c75ba3cceee46 schema:isbn 978-3-540-85884-3
    59 978-3-540-85886-7
    60 schema:name Information Security
    61 rdf:type schema:Book
    62 N8e8761f6229a430e9e0b95a5e27155a6 rdf:first sg:person.015464666561.44
    63 rdf:rest N72403df216ce4924946b4d5c37953bdc
    64 N92bac92799ef4c2fbf7e021d426be88f schema:familyName Rijmen
    65 schema:givenName Vincent
    66 rdf:type schema:Person
    67 Na6010a88c0b54f43a56a3a5ca8a34c31 schema:familyName Lei
    68 schema:givenName Chin-Laung
    69 rdf:type schema:Person
    70 Nb92342ea5c6b4cebb09c7f05723fa5c8 schema:familyName Lee
    71 schema:givenName Der-Tsai
    72 rdf:type schema:Person
    73 Ncc8bc589c36b43adb487ec2ea894946d schema:name readcube_id
    74 schema:value c1dbddb4205939987ceb12d3fa70c504d6c6f77097faad573080f2f95270cc30
    75 rdf:type schema:PropertyValue
    76 Ncf1560302456490984e9d18bb9268be0 rdf:first Na6010a88c0b54f43a56a3a5ca8a34c31
    77 rdf:rest N5238c6d35a414a9589fdee60b999a4d4
    78 Nd35ea0ef44b54c03ad4a0fc8db5cdbf9 schema:name dimensions_id
    79 schema:value pub.1040695999
    80 rdf:type schema:PropertyValue
    81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Mathematical Sciences
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Pure Mathematics
    86 rdf:type schema:DefinedTerm
    87 sg:person.010621103143.01 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
    88 schema:familyName Werner
    89 schema:givenName Fabian
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010621103143.01
    91 rdf:type schema:Person
    92 sg:person.010723403013.04 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
    93 schema:familyName Ding
    94 schema:givenName Jintai
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
    96 rdf:type schema:Person
    97 sg:person.015464666561.44 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
    98 schema:familyName Schmidt
    99 schema:givenName Dieter
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015464666561.44
    101 rdf:type schema:Person
    102 sg:pub.10.1007/11818175_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048753453
    103 https://doi.org/10.1007/11818175_20
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/3-540-45353-9_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003163768
    106 https://doi.org/10.1007/3-540-45353-9_20
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/3-540-45961-8_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035601256
    109 https://doi.org/10.1007/3-540-45961-8_39
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/3-540-48405-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045972569
    112 https://doi.org/10.1007/3-540-48405-1_2
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-0-387-36946-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026168664
    115 https://doi.org/10.1007/978-0-387-36946-4
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-540-45146-4_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049476263
    118 https://doi.org/10.1007/978-3-540-45146-4_3
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-540-79499-8_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041791996
    121 https://doi.org/10.1007/978-3-540-79499-8_31
    122 rdf:type schema:CreativeWork
    123 https://app.dimensions.ai/details/publication/pub.1026168664 schema:CreativeWork
    124 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1145/780506.780516 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007436250
    127 rdf:type schema:CreativeWork
    128 https://www.grid.ac/institutes/grid.24827.3b schema:alternateName University of Cincinnati
    129 schema:name University of Cincinnati
    130 rdf:type schema:Organization
    131 https://www.grid.ac/institutes/grid.6546.1 schema:alternateName Technical University of Darmstadt
    132 schema:name Technical University of Darmstadt
    133 rdf:type schema:Organization
     




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


    ...