Kipnis-Shamir Attack on HFE Revisited View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008

AUTHORS

Xin Jiang , Jintai Ding , Lei Hu

ABSTRACT

In this paper, we show the claims in the original Kipnis-Shamir attack on the HFE cryptosystems and the improved attack by Courtois that the complexity of the attacks is polynomial in terms of the number of variables are invalid. We present computer experiments and a theoretical argument using basic algebraic geometry to explain why it is so. Furthermore we show that even with the help of the powerful new Gröbner basis algorithm like F 4, the Kipnis-Shamir attack still should be exponential but not polynomial. This again is supported by our theoretical argument. More... »

PAGES

399-411

References to SciGraph publications

  • 2001-07-13. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’96
  • 2005. Cryptanalysis of HFEv and Internal Perturbation of HFE in PUBLIC KEY CRYPTOGRAPHY - PKC 2005
  • 1988. Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’88
  • 2001. QUARTZ, 128-Bit Long Digital Signatures in TOPICS IN CRYPTOLOGY — CT-RSA 2001
  • 2001. The Security of Hidden Field Equations (HFE) in TOPICS IN CRYPTOLOGY — CT-RSA 2001
  • 2004. The XL-Algorithm and a Conjecture from Commutative Algebra in ADVANCES IN CRYPTOLOGY - ASIACRYPT 2004
  • 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
  • 2000. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations in ADVANCES IN CRYPTOLOGY — EUROCRYPT 2000
  • Book

    TITLE

    Information Security and Cryptology

    ISBN

    978-3-540-79498-1
    978-3-540-79499-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-79499-8_31

    DOI

    http://dx.doi.org/10.1007/978-3-540-79499-8_31

    DIMENSIONS

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


    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": "Chinese Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.9227.e", 
              "name": [
                "State Key Lab of Information Security, Chinese Academy of Sciences, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Jiang", 
            "givenName": "Xin", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "University of Cincinnati, USA and Technical University of Darmstadt, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ding", 
            "givenName": "Jintai", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Chinese Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.9227.e", 
              "name": [
                "State Key Lab of Information Security, Chinese Academy of Sciences, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hu", 
            "givenName": "Lei", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45539-6_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000285811", 
              "https://doi.org/10.1007/3-540-45539-6_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "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": "sg:pub.10.1007/3-540-45353-9_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016354034", 
              "https://doi.org/10.1007/3-540-45353-9_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30580-4_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032831457", 
              "https://doi.org/10.1007/978-3-540-30580-4_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30580-4_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032831457", 
              "https://doi.org/10.1007/978-3-540-30580-4_20"
            ], 
            "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/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-30539-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050327206", 
              "https://doi.org/10.1007/978-3-540-30539-2_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30539-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050327206", 
              "https://doi.org/10.1007/978-3-540-30539-2_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68339-9_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051894160", 
              "https://doi.org/10.1007/3-540-68339-9_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68339-9_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051894160", 
              "https://doi.org/10.1007/3-540-68339-9_4"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008", 
        "datePublishedReg": "2008-01-01", 
        "description": "In this paper, we show the claims in the original Kipnis-Shamir attack on the HFE cryptosystems and the improved attack by Courtois that the complexity of the attacks is polynomial in terms of the number of variables are invalid. We present computer experiments and a theoretical argument using basic algebraic geometry to explain why it is so. Furthermore we show that even with the help of the powerful new Gr\u00f6bner basis algorithm like F 4, the Kipnis-Shamir attack still should be exponential but not polynomial. This again is supported by our theoretical argument.", 
        "editor": [
          {
            "familyName": "Pei", 
            "givenName": "Dingyi", 
            "type": "Person"
          }, 
          {
            "familyName": "Yung", 
            "givenName": "Moti", 
            "type": "Person"
          }, 
          {
            "familyName": "Lin", 
            "givenName": "Dongdai", 
            "type": "Person"
          }, 
          {
            "familyName": "Wu", 
            "givenName": "Chuankun", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-79499-8_31", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-79498-1", 
            "978-3-540-79499-8"
          ], 
          "name": "Information Security and Cryptology", 
          "type": "Book"
        }, 
        "name": "Kipnis-Shamir Attack on HFE Revisited", 
        "pagination": "399-411", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-79499-8_31"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c71422e2fa1ef06cce8d85b89a6875af54846990bc733c265356cfd0418e7382"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1041791996"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-79499-8_31", 
          "https://app.dimensions.ai/details/publication/pub.1041791996"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T22:57", 
        "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_8695_00000269.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-540-79499-8_31"
      }
    ]
     

    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-79499-8_31'

    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-79499-8_31'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-79499-8_31'

    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-79499-8_31'


     

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

    132 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-79499-8_31 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nfc5ad8d6bed24f408d99e7dd10e33149
    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-45353-9_21
    7 sg:pub.10.1007/3-540-45539-6_27
    8 sg:pub.10.1007/3-540-45961-8_39
    9 sg:pub.10.1007/3-540-48405-1_2
    10 sg:pub.10.1007/3-540-68339-9_4
    11 sg:pub.10.1007/978-3-540-30539-2_23
    12 sg:pub.10.1007/978-3-540-30580-4_20
    13 https://doi.org/10.1016/s0022-4049(99)00005-5
    14 schema:datePublished 2008
    15 schema:datePublishedReg 2008-01-01
    16 schema:description In this paper, we show the claims in the original Kipnis-Shamir attack on the HFE cryptosystems and the improved attack by Courtois that the complexity of the attacks is polynomial in terms of the number of variables are invalid. We present computer experiments and a theoretical argument using basic algebraic geometry to explain why it is so. Furthermore we show that even with the help of the powerful new Gröbner basis algorithm like F 4, the Kipnis-Shamir attack still should be exponential but not polynomial. This again is supported by our theoretical argument.
    17 schema:editor N8b76a6621bd34741a87a2556e0a7b941
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf Nd88b96efee2e4c57917e3abbbda0a62f
    22 schema:name Kipnis-Shamir Attack on HFE Revisited
    23 schema:pagination 399-411
    24 schema:productId N21360f4c015245a1a75cd992d2fe4983
    25 N9af2711fb0834bed8117ffc8e3aa6d9f
    26 N9c4e382494e340e48c2813f3eabe00d4
    27 schema:publisher Nf9de3c8867004af595304e05fdcb17d9
    28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041791996
    29 https://doi.org/10.1007/978-3-540-79499-8_31
    30 schema:sdDatePublished 2019-04-15T22:57
    31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    32 schema:sdPublisher Nde2da484dd1c476bb75699ae5c858ecf
    33 schema:url http://link.springer.com/10.1007/978-3-540-79499-8_31
    34 sgo:license sg:explorer/license/
    35 sgo:sdDataset chapters
    36 rdf:type schema:Chapter
    37 N0f535baeb66e4b53b88c5f810b8a0777 rdf:first N9ee8bca8a9ba4500a5724a8036145a46
    38 rdf:rest Naa77a8486ed34ab19634b39a60b30a34
    39 N21360f4c015245a1a75cd992d2fe4983 schema:name doi
    40 schema:value 10.1007/978-3-540-79499-8_31
    41 rdf:type schema:PropertyValue
    42 N4170076a5bb9476f8a0157d44ca88f27 schema:familyName Wu
    43 schema:givenName Chuankun
    44 rdf:type schema:Person
    45 N5fc83f76646444ab8715edf16396bddf rdf:first Nc7ab816849b14bc49e733893f1697cea
    46 rdf:rest rdf:nil
    47 N74044169ed42412cbbd78817285b92ba schema:affiliation Nf11d4a55df4b448e920d5e40c8bd01aa
    48 schema:familyName Ding
    49 schema:givenName Jintai
    50 rdf:type schema:Person
    51 N8b76a6621bd34741a87a2556e0a7b941 rdf:first Nb5d6bbba87fb4d8ab74baab65aa6bf68
    52 rdf:rest N0f535baeb66e4b53b88c5f810b8a0777
    53 N98460bc554f04158881d2d9eeaef5ae4 rdf:first N4170076a5bb9476f8a0157d44ca88f27
    54 rdf:rest rdf:nil
    55 N9af2711fb0834bed8117ffc8e3aa6d9f schema:name readcube_id
    56 schema:value c71422e2fa1ef06cce8d85b89a6875af54846990bc733c265356cfd0418e7382
    57 rdf:type schema:PropertyValue
    58 N9c4e382494e340e48c2813f3eabe00d4 schema:name dimensions_id
    59 schema:value pub.1041791996
    60 rdf:type schema:PropertyValue
    61 N9ee8bca8a9ba4500a5724a8036145a46 schema:familyName Yung
    62 schema:givenName Moti
    63 rdf:type schema:Person
    64 Na4c20c41eda34161a9d8cc8bd948c678 schema:familyName Lin
    65 schema:givenName Dongdai
    66 rdf:type schema:Person
    67 Naa77a8486ed34ab19634b39a60b30a34 rdf:first Na4c20c41eda34161a9d8cc8bd948c678
    68 rdf:rest N98460bc554f04158881d2d9eeaef5ae4
    69 Nb5d6bbba87fb4d8ab74baab65aa6bf68 schema:familyName Pei
    70 schema:givenName Dingyi
    71 rdf:type schema:Person
    72 Nc7ab816849b14bc49e733893f1697cea schema:affiliation https://www.grid.ac/institutes/grid.9227.e
    73 schema:familyName Hu
    74 schema:givenName Lei
    75 rdf:type schema:Person
    76 Ncaee0fc640ee42a5a2b5eac72f8ab8d3 rdf:first N74044169ed42412cbbd78817285b92ba
    77 rdf:rest N5fc83f76646444ab8715edf16396bddf
    78 Nd88b96efee2e4c57917e3abbbda0a62f schema:isbn 978-3-540-79498-1
    79 978-3-540-79499-8
    80 schema:name Information Security and Cryptology
    81 rdf:type schema:Book
    82 Nde2da484dd1c476bb75699ae5c858ecf schema:name Springer Nature - SN SciGraph project
    83 rdf:type schema:Organization
    84 Nf11d4a55df4b448e920d5e40c8bd01aa schema:name University of Cincinnati, USA and Technical University of Darmstadt, Germany
    85 rdf:type schema:Organization
    86 Nf9de3c8867004af595304e05fdcb17d9 schema:location Berlin, Heidelberg
    87 schema:name Springer Berlin Heidelberg
    88 rdf:type schema:Organisation
    89 Nfc5ad8d6bed24f408d99e7dd10e33149 rdf:first Nff44735e89f04fec8a6f368cabc7b555
    90 rdf:rest Ncaee0fc640ee42a5a2b5eac72f8ab8d3
    91 Nff44735e89f04fec8a6f368cabc7b555 schema:affiliation https://www.grid.ac/institutes/grid.9227.e
    92 schema:familyName Jiang
    93 schema:givenName Xin
    94 rdf:type schema:Person
    95 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Mathematical Sciences
    97 rdf:type schema:DefinedTerm
    98 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Pure Mathematics
    100 rdf:type schema:DefinedTerm
    101 sg:pub.10.1007/11818175_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048753453
    102 https://doi.org/10.1007/11818175_20
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/3-540-45353-9_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003163768
    105 https://doi.org/10.1007/3-540-45353-9_20
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/3-540-45353-9_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016354034
    108 https://doi.org/10.1007/3-540-45353-9_21
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/3-540-45539-6_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
    111 https://doi.org/10.1007/3-540-45539-6_27
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/3-540-45961-8_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035601256
    114 https://doi.org/10.1007/3-540-45961-8_39
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/3-540-48405-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045972569
    117 https://doi.org/10.1007/3-540-48405-1_2
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/3-540-68339-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051894160
    120 https://doi.org/10.1007/3-540-68339-9_4
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-3-540-30539-2_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050327206
    123 https://doi.org/10.1007/978-3-540-30539-2_23
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-3-540-30580-4_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032831457
    126 https://doi.org/10.1007/978-3-540-30580-4_20
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
    129 rdf:type schema:CreativeWork
    130 https://www.grid.ac/institutes/grid.9227.e schema:alternateName Chinese Academy of Sciences
    131 schema:name State Key Lab of Information Security, Chinese Academy of Sciences, Beijing, China
    132 rdf:type schema:Organization
     




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


    ...