Multivariates Polynomials for Hashing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Jintai Ding , Bo-Yin Yang

ABSTRACT

We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials. More... »

PAGES

358-371

References to SciGraph publications

  • 2002. Solving Underdefined Systems of Multivariate Quadratic Equations in PUBLIC KEY CRYPTOGRAPHY
  • 2006. QUAD: A Practical Stream Cipher with Provable Security in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2006
  • 2005. How to Break MD5 and Other Hash Functions in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2005
  • 2007-01. Another Look at "Provable Security" in JOURNAL OF CRYPTOLOGY
  • 2006. On the Importance of Public-Key Validation in the MQV and HMQV Key Agreement Protocols in PROGRESS IN CRYPTOLOGY - INDOCRYPT 2006
  • 1999. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization in ADVANCES IN CRYPTOLOGY — CRYPTO’ 99
  • 2005. Finding Collisions in the Full SHA-1 in ADVANCES IN CRYPTOLOGY – CRYPTO 2005
  • 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_28

    DOI

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

    DIMENSIONS

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


    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/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "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": {
              "name": [
                "University of Cincinnati and Technische Universit\u00e4t Darmstadt,"
              ], 
              "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": "Academia Sinica", 
              "id": "https://www.grid.ac/institutes/grid.28665.3f", 
              "name": [
                "Institute of Information Science, Academia Sinica,"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yang", 
            "givenName": "Bo-Yin", 
            "id": "sg:person.010017213117.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010017213117.39"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11535218_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002819603", 
              "https://doi.org/10.1007/11535218_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11535218_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002819603", 
              "https://doi.org/10.1007/11535218_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45664-3_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007371554", 
              "https://doi.org/10.1007/3-540-45664-3_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11941378_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013352440", 
              "https://doi.org/10.1007/11941378_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11941378_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013352440", 
              "https://doi.org/10.1007/11941378_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11761679_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018935992", 
              "https://doi.org/10.1007/11761679_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11761679_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018935992", 
              "https://doi.org/10.1007/11761679_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00145-005-0432-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020805853", 
              "https://doi.org/10.1007/s00145-005-0432-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043264875", 
              "https://doi.org/10.1007/11426639_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043264875", 
              "https://doi.org/10.1007/11426639_2"
            ], 
            "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"
          }
        ], 
        "datePublished": "2008", 
        "datePublishedReg": "2008-01-01", 
        "description": "We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials.", 
        "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_28", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-79498-1", 
            "978-3-540-79499-8"
          ], 
          "name": "Information Security and Cryptology", 
          "type": "Book"
        }, 
        "name": "Multivariates Polynomials for Hashing", 
        "pagination": "358-371", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-79499-8_28"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "815396603ed02080a75dfe488b153c84b1b5981dfa232eafbe65aaf76c0152c3"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1027148888"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-79499-8_28", 
          "https://app.dimensions.ai/details/publication/pub.1027148888"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T11:35", 
        "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_8660_00000260.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-540-79499-8_28"
      }
    ]
     

    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_28'

    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_28'

    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_28'

    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_28'


     

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

    117 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-79499-8_28 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author N5b4fb2d447d9445a83f7f07e61e5a87c
    4 schema:citation sg:pub.10.1007/11426639_2
    5 sg:pub.10.1007/11535218_2
    6 sg:pub.10.1007/11761679_8
    7 sg:pub.10.1007/11941378_11
    8 sg:pub.10.1007/3-540-45664-3_15
    9 sg:pub.10.1007/3-540-48405-1_2
    10 sg:pub.10.1007/s00145-005-0432-z
    11 schema:datePublished 2008
    12 schema:datePublishedReg 2008-01-01
    13 schema:description We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials.
    14 schema:editor N007b5568c3e049d9abad9cfe083cd9ba
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf Nc516dda47c384eb79f3dfa285b7ed076
    19 schema:name Multivariates Polynomials for Hashing
    20 schema:pagination 358-371
    21 schema:productId N331b898e86704cb4bbe5cfa4a7380689
    22 N7643dec0791f4672ae44306c5fb04a8e
    23 Nfa2f771c06144f4f8f562b0dc1435d75
    24 schema:publisher N203052e1d89f4a138e21157704e548a8
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027148888
    26 https://doi.org/10.1007/978-3-540-79499-8_28
    27 schema:sdDatePublished 2019-04-15T11:35
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N4037db076da04c3c993196274cbc6952
    30 schema:url http://link.springer.com/10.1007/978-3-540-79499-8_28
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N007b5568c3e049d9abad9cfe083cd9ba rdf:first Ncfc991059cc14e02b48ca41f49f3e219
    35 rdf:rest Ndebbd38772884b878e934ca140c54985
    36 N203052e1d89f4a138e21157704e548a8 schema:location Berlin, Heidelberg
    37 schema:name Springer Berlin Heidelberg
    38 rdf:type schema:Organisation
    39 N331b898e86704cb4bbe5cfa4a7380689 schema:name readcube_id
    40 schema:value 815396603ed02080a75dfe488b153c84b1b5981dfa232eafbe65aaf76c0152c3
    41 rdf:type schema:PropertyValue
    42 N4037db076da04c3c993196274cbc6952 schema:name Springer Nature - SN SciGraph project
    43 rdf:type schema:Organization
    44 N5b4fb2d447d9445a83f7f07e61e5a87c rdf:first sg:person.010723403013.04
    45 rdf:rest Nfc2e8fb7f2054d4bb851d7fd6c30253c
    46 N6a0378599f8744cdafc2d8b9a217b41a schema:familyName Wu
    47 schema:givenName Chuankun
    48 rdf:type schema:Person
    49 N7643dec0791f4672ae44306c5fb04a8e schema:name doi
    50 schema:value 10.1007/978-3-540-79499-8_28
    51 rdf:type schema:PropertyValue
    52 N96d2a23bef8b49a389ccd43b1aa98ca2 rdf:first Na8c5f480bf4b4bff945a11be8b1cf6f2
    53 rdf:rest Nc007da6fe81949ad9295dde0522ce35b
    54 Na8c5f480bf4b4bff945a11be8b1cf6f2 schema:familyName Lin
    55 schema:givenName Dongdai
    56 rdf:type schema:Person
    57 Nc007da6fe81949ad9295dde0522ce35b rdf:first N6a0378599f8744cdafc2d8b9a217b41a
    58 rdf:rest rdf:nil
    59 Nc516dda47c384eb79f3dfa285b7ed076 schema:isbn 978-3-540-79498-1
    60 978-3-540-79499-8
    61 schema:name Information Security and Cryptology
    62 rdf:type schema:Book
    63 Ncfc991059cc14e02b48ca41f49f3e219 schema:familyName Pei
    64 schema:givenName Dingyi
    65 rdf:type schema:Person
    66 Nd6298798de0247ef984c569995c09a88 schema:familyName Yung
    67 schema:givenName Moti
    68 rdf:type schema:Person
    69 Ndebbd38772884b878e934ca140c54985 rdf:first Nd6298798de0247ef984c569995c09a88
    70 rdf:rest N96d2a23bef8b49a389ccd43b1aa98ca2
    71 Nfa2f771c06144f4f8f562b0dc1435d75 schema:name dimensions_id
    72 schema:value pub.1027148888
    73 rdf:type schema:PropertyValue
    74 Nfc2e8fb7f2054d4bb851d7fd6c30253c rdf:first sg:person.010017213117.39
    75 rdf:rest rdf:nil
    76 Nfec2e6a463134a7ba90d98cf06218b0e schema:name University of Cincinnati and Technische Universität Darmstadt,
    77 rdf:type schema:Organization
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Data Format
    83 rdf:type schema:DefinedTerm
    84 sg:person.010017213117.39 schema:affiliation https://www.grid.ac/institutes/grid.28665.3f
    85 schema:familyName Yang
    86 schema:givenName Bo-Yin
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010017213117.39
    88 rdf:type schema:Person
    89 sg:person.010723403013.04 schema:affiliation Nfec2e6a463134a7ba90d98cf06218b0e
    90 schema:familyName Ding
    91 schema:givenName Jintai
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
    93 rdf:type schema:Person
    94 sg:pub.10.1007/11426639_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043264875
    95 https://doi.org/10.1007/11426639_2
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/11535218_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002819603
    98 https://doi.org/10.1007/11535218_2
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/11761679_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018935992
    101 https://doi.org/10.1007/11761679_8
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/11941378_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013352440
    104 https://doi.org/10.1007/11941378_11
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/3-540-45664-3_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007371554
    107 https://doi.org/10.1007/3-540-45664-3_15
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/3-540-48405-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045972569
    110 https://doi.org/10.1007/3-540-48405-1_2
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/s00145-005-0432-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1020805853
    113 https://doi.org/10.1007/s00145-005-0432-z
    114 rdf:type schema:CreativeWork
    115 https://www.grid.ac/institutes/grid.28665.3f schema:alternateName Academia Sinica
    116 schema:name Institute of Information Science, Academia Sinica,
    117 rdf:type schema:Organization
     




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


    ...