Analysis of Multivariate Hash Functions View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Jean-Philippe Aumasson , Willi Meier

ABSTRACT

We analyse the security of new hash functions whose compression function is explicitly defined as a sequence of multivariate equations. First we prove non-universality of certain proposals with sparse equations, and deduce trivial collisions holding with high probability. Then we introduce a method inspired from coding theory for solving underdefined systems with a low density of non-linear monomials, and apply it to find collisions in certain functions. We also study the security of message authentication codes HMAC and NMAC built on multivariate hash functions, and demonstrate that families of low-degree functions over GF(2) are neither pseudo-random nor unpredictable. More... »

PAGES

309-323

Book

TITLE

Information Security and Cryptology - ICISC 2007

ISBN

978-3-540-76787-9
978-3-540-76788-6

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-76788-6_25

DOI

http://dx.doi.org/10.1007/978-3-540-76788-6_25

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "FHNW, 5210 Windisch, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.410380.e", 
          "name": [
            "FHNW, 5210 Windisch, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Aumasson", 
        "givenName": "Jean-Philippe", 
        "id": "sg:person.012606440341.66", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012606440341.66"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "FHNW, 5210 Windisch, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.410380.e", 
          "name": [
            "FHNW, 5210 Windisch, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Meier", 
        "givenName": "Willi", 
        "id": "sg:person.07653531142.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "We analyse the security of new hash functions whose compression function is explicitly defined as a sequence of multivariate equations. First we prove non-universality of certain proposals with sparse equations, and deduce trivial collisions holding with high probability. Then we introduce a method inspired from coding theory for solving underdefined systems with a low density of non-linear monomials, and apply it to find collisions in certain functions. We also study the security of message authentication codes HMAC and NMAC built on multivariate hash functions, and demonstrate that families of low-degree functions over GF(2) are neither pseudo-random nor unpredictable.", 
    "editor": [
      {
        "familyName": "Nam", 
        "givenName": "Kil-Hyun", 
        "type": "Person"
      }, 
      {
        "familyName": "Rhee", 
        "givenName": "Gwangsoo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-76788-6_25", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-76787-9", 
        "978-3-540-76788-6"
      ], 
      "name": "Information Security and Cryptology - ICISC 2007", 
      "type": "Book"
    }, 
    "keywords": [
      "non-linear monomials", 
      "low-degree functions", 
      "sparse equations", 
      "multivariate equations", 
      "certain functions", 
      "equations", 
      "monomials", 
      "high probability", 
      "hash functions", 
      "function", 
      "theory", 
      "probability", 
      "certain proposals", 
      "new hash function", 
      "system", 
      "NMAC", 
      "collisions", 
      "compression function", 
      "analysis", 
      "sequence", 
      "security", 
      "proposal", 
      "family", 
      "density", 
      "low density", 
      "HMAC", 
      "method", 
      "trivial collisions", 
      "underdefined systems", 
      "message authentication codes HMAC", 
      "authentication codes HMAC", 
      "codes HMAC", 
      "multivariate hash functions"
    ], 
    "name": "Analysis of Multivariate Hash Functions", 
    "pagination": "309-323", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044926303"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-76788-6_25"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-76788-6_25", 
      "https://app.dimensions.ai/details/publication/pub.1044926303"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:11", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_203.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-76788-6_25"
  }
]
 

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-76788-6_25'

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-76788-6_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-76788-6_25'

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-76788-6_25'


 

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

105 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-76788-6_25 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N960ff272fcce42d7ae7f9ea245d50f01
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description We analyse the security of new hash functions whose compression function is explicitly defined as a sequence of multivariate equations. First we prove non-universality of certain proposals with sparse equations, and deduce trivial collisions holding with high probability. Then we introduce a method inspired from coding theory for solving underdefined systems with a low density of non-linear monomials, and apply it to find collisions in certain functions. We also study the security of message authentication codes HMAC and NMAC built on multivariate hash functions, and demonstrate that families of low-degree functions over GF(2) are neither pseudo-random nor unpredictable.
7 schema:editor N14af277266ef4b2da2ead8fffc9f1610
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N4d778bd415cc4899ae152a29d47ef84b
12 schema:keywords HMAC
13 NMAC
14 analysis
15 authentication codes HMAC
16 certain functions
17 certain proposals
18 codes HMAC
19 collisions
20 compression function
21 density
22 equations
23 family
24 function
25 hash functions
26 high probability
27 low density
28 low-degree functions
29 message authentication codes HMAC
30 method
31 monomials
32 multivariate equations
33 multivariate hash functions
34 new hash function
35 non-linear monomials
36 probability
37 proposal
38 security
39 sequence
40 sparse equations
41 system
42 theory
43 trivial collisions
44 underdefined systems
45 schema:name Analysis of Multivariate Hash Functions
46 schema:pagination 309-323
47 schema:productId N38584099c6b8439282380c5cf4fe177f
48 N58710a1ce7894f4294aab462cd665696
49 schema:publisher N36596e85c872441e8ecf0cebbd95e480
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044926303
51 https://doi.org/10.1007/978-3-540-76788-6_25
52 schema:sdDatePublished 2022-01-01T19:11
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N1392b2ddb4c84ba1a588c18e1bed20e9
55 schema:url https://doi.org/10.1007/978-3-540-76788-6_25
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N1392b2ddb4c84ba1a588c18e1bed20e9 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 N14af277266ef4b2da2ead8fffc9f1610 rdf:first N2df3f324660f444587b1b47f2ae16754
62 rdf:rest N2ddd61ae82224502927de3735ae80b17
63 N2579c151a73540b9a5e66b45c5e032bc rdf:first sg:person.07653531142.18
64 rdf:rest rdf:nil
65 N2ddd61ae82224502927de3735ae80b17 rdf:first N6a6cd8cc7d424309ad07bc33bae9c4c4
66 rdf:rest rdf:nil
67 N2df3f324660f444587b1b47f2ae16754 schema:familyName Nam
68 schema:givenName Kil-Hyun
69 rdf:type schema:Person
70 N36596e85c872441e8ecf0cebbd95e480 schema:name Springer Nature
71 rdf:type schema:Organisation
72 N38584099c6b8439282380c5cf4fe177f schema:name doi
73 schema:value 10.1007/978-3-540-76788-6_25
74 rdf:type schema:PropertyValue
75 N4d778bd415cc4899ae152a29d47ef84b schema:isbn 978-3-540-76787-9
76 978-3-540-76788-6
77 schema:name Information Security and Cryptology - ICISC 2007
78 rdf:type schema:Book
79 N58710a1ce7894f4294aab462cd665696 schema:name dimensions_id
80 schema:value pub.1044926303
81 rdf:type schema:PropertyValue
82 N6a6cd8cc7d424309ad07bc33bae9c4c4 schema:familyName Rhee
83 schema:givenName Gwangsoo
84 rdf:type schema:Person
85 N960ff272fcce42d7ae7f9ea245d50f01 rdf:first sg:person.012606440341.66
86 rdf:rest N2579c151a73540b9a5e66b45c5e032bc
87 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
88 schema:name Mathematical Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
91 schema:name Pure Mathematics
92 rdf:type schema:DefinedTerm
93 sg:person.012606440341.66 schema:affiliation grid-institutes:grid.410380.e
94 schema:familyName Aumasson
95 schema:givenName Jean-Philippe
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012606440341.66
97 rdf:type schema:Person
98 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
99 schema:familyName Meier
100 schema:givenName Willi
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
102 rdf:type schema:Person
103 grid-institutes:grid.410380.e schema:alternateName FHNW, 5210 Windisch, Switzerland
104 schema:name FHNW, 5210 Windisch, Switzerland
105 rdf:type schema:Organization
 




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


...