Cryptanalysis of Rational Multivariate Public Key Cryptosystems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Jintai Ding , John Wagner

ABSTRACT

In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC. More... »

PAGES

124-136

References to SciGraph publications

  • 1986. Analysis of a Public Key Approach Based on Polynomial Substitution in ADVANCES IN CRYPTOLOGY — CRYPTO ’85 PROCEEDINGS
  • 2006. Cryptanalysis of 2R− Schemes in ADVANCES IN CRYPTOLOGY - CRYPTO 2006
  • Book

    TITLE

    Post-Quantum Cryptography

    ISBN

    978-3-540-88402-6
    978-3-540-88403-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_9

    DOI

    http://dx.doi.org/10.1007/978-3-540-88403-3_9

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Cincinnati", 
              "id": "https://www.grid.ac/institutes/grid.24827.3b", 
              "name": [
                "Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH\u00a045220, USA"
              ], 
              "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": [
                "Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH\u00a045220, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wagner", 
            "givenName": "John", 
            "id": "sg:person.010671250305.52", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010671250305.52"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11818175_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006466475", 
              "https://doi.org/10.1007/11818175_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11818175_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006466475", 
              "https://doi.org/10.1007/11818175_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-39799-x_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009274988", 
              "https://doi.org/10.1007/3-540-39799-x_24"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008", 
        "datePublishedReg": "2008-01-01", 
        "description": "In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.", 
        "editor": [
          {
            "familyName": "Buchmann", 
            "givenName": "Johannes", 
            "type": "Person"
          }, 
          {
            "familyName": "Ding", 
            "givenName": "Jintai", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-88403-3_9", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-88402-6", 
            "978-3-540-88403-3"
          ], 
          "name": "Post-Quantum Cryptography", 
          "type": "Book"
        }, 
        "name": "Cryptanalysis of Rational Multivariate Public Key Cryptosystems", 
        "pagination": "124-136", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-88403-3_9"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "32ec2e79cdc07407acc70ef5a19fac405af66e4649e8bd47ed9bdd47d9760481"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1010688833"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-88403-3_9", 
          "https://app.dimensions.ai/details/publication/pub.1010688833"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T00:47", 
        "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_8700_00000249.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-540-88403-3_9"
      }
    ]
     

    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-88403-3_9'

    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-88403-3_9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_9'

    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-88403-3_9'


     

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

    85 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-88403-3_9 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N318dc0c22960401ca7b9ac2f82f1679f
    4 schema:citation sg:pub.10.1007/11818175_21
    5 sg:pub.10.1007/3-540-39799-x_24
    6 schema:datePublished 2008
    7 schema:datePublishedReg 2008-01-01
    8 schema:description In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.
    9 schema:editor Ne240885028884d98be29126632c95f79
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf N33edbedbf0464325a7b0a1c1eec69afe
    14 schema:name Cryptanalysis of Rational Multivariate Public Key Cryptosystems
    15 schema:pagination 124-136
    16 schema:productId N58afcec3de3349cfbc0615cdce77a19f
    17 Nb15585cbfcfd46c8a2eb0ee2c017ca2c
    18 Nf378386d8d43446ab898cbfe5e7ab9a6
    19 schema:publisher N425c96791fba4766894c9b9a327f24fe
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010688833
    21 https://doi.org/10.1007/978-3-540-88403-3_9
    22 schema:sdDatePublished 2019-04-16T00:47
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher Nddb1adf580624c3b92b214421aa26477
    25 schema:url http://link.springer.com/10.1007/978-3-540-88403-3_9
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset chapters
    28 rdf:type schema:Chapter
    29 N07ace7506b0d48b7b4625a257987dc0d schema:familyName Buchmann
    30 schema:givenName Johannes
    31 rdf:type schema:Person
    32 N12920e4ff7d247669de6a7c661b17cc3 schema:familyName Ding
    33 schema:givenName Jintai
    34 rdf:type schema:Person
    35 N318dc0c22960401ca7b9ac2f82f1679f rdf:first sg:person.010723403013.04
    36 rdf:rest N3ac59403b76e4b718428ac7881de023b
    37 N33edbedbf0464325a7b0a1c1eec69afe schema:isbn 978-3-540-88402-6
    38 978-3-540-88403-3
    39 schema:name Post-Quantum Cryptography
    40 rdf:type schema:Book
    41 N3ac59403b76e4b718428ac7881de023b rdf:first sg:person.010671250305.52
    42 rdf:rest rdf:nil
    43 N425c96791fba4766894c9b9a327f24fe schema:location Berlin, Heidelberg
    44 schema:name Springer Berlin Heidelberg
    45 rdf:type schema:Organisation
    46 N58afcec3de3349cfbc0615cdce77a19f schema:name readcube_id
    47 schema:value 32ec2e79cdc07407acc70ef5a19fac405af66e4649e8bd47ed9bdd47d9760481
    48 rdf:type schema:PropertyValue
    49 N9f453767465b41fda906a4a0a9babd38 rdf:first N12920e4ff7d247669de6a7c661b17cc3
    50 rdf:rest rdf:nil
    51 Nb15585cbfcfd46c8a2eb0ee2c017ca2c schema:name dimensions_id
    52 schema:value pub.1010688833
    53 rdf:type schema:PropertyValue
    54 Nddb1adf580624c3b92b214421aa26477 schema:name Springer Nature - SN SciGraph project
    55 rdf:type schema:Organization
    56 Ne240885028884d98be29126632c95f79 rdf:first N07ace7506b0d48b7b4625a257987dc0d
    57 rdf:rest N9f453767465b41fda906a4a0a9babd38
    58 Nf378386d8d43446ab898cbfe5e7ab9a6 schema:name doi
    59 schema:value 10.1007/978-3-540-88403-3_9
    60 rdf:type schema:PropertyValue
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Computation Theory and Mathematics
    66 rdf:type schema:DefinedTerm
    67 sg:person.010671250305.52 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
    68 schema:familyName Wagner
    69 schema:givenName John
    70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010671250305.52
    71 rdf:type schema:Person
    72 sg:person.010723403013.04 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
    73 schema:familyName Ding
    74 schema:givenName Jintai
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
    76 rdf:type schema:Person
    77 sg:pub.10.1007/11818175_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006466475
    78 https://doi.org/10.1007/11818175_21
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1007/3-540-39799-x_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009274988
    81 https://doi.org/10.1007/3-540-39799-x_24
    82 rdf:type schema:CreativeWork
    83 https://www.grid.ac/institutes/grid.24827.3b schema:alternateName University of Cincinnati
    84 schema:name Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH 45220, USA
    85 rdf:type schema:Organization
     




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


    ...