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 N6aabe21a115e40af9700314eefaac730
    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 Nc68764cc68734c9fa6f0dee615c259e1
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N4407b0edf75348efaa995b624b8699c3
    19 schema:name Multivariates Polynomials for Hashing
    20 schema:pagination 358-371
    21 schema:productId N692b9f7edfe74d3186c130451e79622b
    22 N9ff18c8ee53f49e2b91098ee2c4c9c36
    23 Nd48dfff610da453e9c93184262ff06ac
    24 schema:publisher N65e1e94e02d0401ea3c5c3b8c9220846
    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 N664f6d08591e497c8ec210ac873e5cd9
    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 N1ed8d3085cff46619e4f569bf282b8ec rdf:first N761d256f77234d38b9f56fe326e12e87
    35 rdf:rest rdf:nil
    36 N35dc6004f1b744488ea4b767582c7036 rdf:first sg:person.010017213117.39
    37 rdf:rest rdf:nil
    38 N3dae4e86cfc74de886e0b6560a40ad8b rdf:first N68b5dfba2ed54c7aa96154896a9011c8
    39 rdf:rest Ncfa1384d995c4856a796bf183451a7c0
    40 N3fc3f5d8129e4feda21e30d59cd163eb schema:name University of Cincinnati and Technische Universität Darmstadt,
    41 rdf:type schema:Organization
    42 N4407b0edf75348efaa995b624b8699c3 schema:isbn 978-3-540-79498-1
    43 978-3-540-79499-8
    44 schema:name Information Security and Cryptology
    45 rdf:type schema:Book
    46 N65e1e94e02d0401ea3c5c3b8c9220846 schema:location Berlin, Heidelberg
    47 schema:name Springer Berlin Heidelberg
    48 rdf:type schema:Organisation
    49 N664f6d08591e497c8ec210ac873e5cd9 schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 N68b5dfba2ed54c7aa96154896a9011c8 schema:familyName Yung
    52 schema:givenName Moti
    53 rdf:type schema:Person
    54 N692b9f7edfe74d3186c130451e79622b schema:name readcube_id
    55 schema:value 815396603ed02080a75dfe488b153c84b1b5981dfa232eafbe65aaf76c0152c3
    56 rdf:type schema:PropertyValue
    57 N6aabe21a115e40af9700314eefaac730 rdf:first sg:person.010723403013.04
    58 rdf:rest N35dc6004f1b744488ea4b767582c7036
    59 N761d256f77234d38b9f56fe326e12e87 schema:familyName Wu
    60 schema:givenName Chuankun
    61 rdf:type schema:Person
    62 N9ff18c8ee53f49e2b91098ee2c4c9c36 schema:name dimensions_id
    63 schema:value pub.1027148888
    64 rdf:type schema:PropertyValue
    65 Na7cb09be73824ef1b011cbb386f6089c schema:familyName Lin
    66 schema:givenName Dongdai
    67 rdf:type schema:Person
    68 Nc68764cc68734c9fa6f0dee615c259e1 rdf:first Neff190e01e5e48a2a9073eceb7b99571
    69 rdf:rest N3dae4e86cfc74de886e0b6560a40ad8b
    70 Ncfa1384d995c4856a796bf183451a7c0 rdf:first Na7cb09be73824ef1b011cbb386f6089c
    71 rdf:rest N1ed8d3085cff46619e4f569bf282b8ec
    72 Nd48dfff610da453e9c93184262ff06ac schema:name doi
    73 schema:value 10.1007/978-3-540-79499-8_28
    74 rdf:type schema:PropertyValue
    75 Neff190e01e5e48a2a9073eceb7b99571 schema:familyName Pei
    76 schema:givenName Dingyi
    77 rdf:type schema:Person
    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 N3fc3f5d8129e4feda21e30d59cd163eb
    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)


    ...