Security Definitions for Hash Functions: Combining UCE and Indifferentiability View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-03

AUTHORS

Daniel Jost , Ueli Maurer

ABSTRACT

Hash functions are one of the most important cryptographic primitives, but their desired security properties have proven to be remarkably hard to formalize. To prove the security of a protocol using a hash function, nowadays often the random oracle model (ROM) is used due to its simplicity and its strong security guarantees. Moreover, hash function constructions are commonly proven to be secure by showing them to be indifferentiable from a random oracle when using an ideal compression function. However, it is well known that no hash function realizes a random oracle and no real compression function realizes an ideal one.As an alternative to the ROM, Bellare et al. recently proposed the notion of universal computational extractors (UCE). This notion formalizes that a family of functions “behaves like a random oracle” for “real-world” protocols while avoiding the general impossibility results. However, in contrast to the indifferentiability framework, UCE is formalized as a multi-stage game without clear composition guarantees.As a first contribution, we introduce context-restricted indifferentiability (CRI), a generalization of indifferentiability that allows us to model that the random oracle does not compose generally but can only be used within a well-specified set of protocols run by the honest parties, thereby making the provided composition guarantees explicit. We then show that UCE and its variants can be phrased as a special case of CRI. Moreover, we show how our notion of CRI leads to generalizations of UCE. As a second contribution, we prove that the hash function constructed by Merkle-Damgåd satisfies one of the well-known UCE variants, if we assume that the compression function satisfies one of our generalizations of UCE, basing the overall security on a plausible assumption. This result further validates the Merkle-Damgård construction and shows that UCE-like assumptions can serve both as a valid reference point for modular protocol analyses, as well as for the design of hash functions, linking those two aspects in a framework with explicit composition guarantees. More... »

PAGES

83-101

Book

TITLE

Security and Cryptography for Networks

ISBN

978-3-319-98112-3
978-3-319-98113-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-98113-0_5

DOI

http://dx.doi.org/10.1007/978-3-319-98113-0_5

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jost", 
        "givenName": "Daniel", 
        "id": "sg:person.013356446515.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013356446515.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maurer", 
        "givenName": "Ueli", 
        "id": "sg:person.01316567627.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-08-03", 
    "datePublishedReg": "2018-08-03", 
    "description": "Hash functions are one of the most important cryptographic primitives, but their desired security properties have proven to be remarkably hard to formalize. To prove the security of a protocol using a hash function, nowadays often the random oracle model (ROM) is used due to its simplicity and its strong security guarantees. Moreover, hash function constructions are commonly proven to be secure by showing them to be indifferentiable from a random oracle when using an ideal compression function. However, it is well known that no hash function realizes a random oracle and no real compression function realizes an ideal one.As an alternative to the ROM, Bellare et al. recently proposed the notion of universal computational extractors (UCE). This notion formalizes that a family of functions \u201cbehaves like a random oracle\u201d for \u201creal-world\u201d protocols while avoiding the general impossibility results. However, in contrast to the indifferentiability framework, UCE is formalized as a multi-stage game without clear composition guarantees.As a first contribution, we introduce context-restricted indifferentiability (CRI), a generalization of indifferentiability that allows us to model that the random oracle does not compose generally but can only be used within a well-specified set of protocols run by the honest parties, thereby making the provided composition guarantees explicit. We then show that UCE and its variants can be phrased as a special case of CRI. Moreover, we show how our notion of CRI leads to generalizations of UCE. As a second contribution, we prove that the hash function constructed by Merkle-Damg\u00e5d satisfies one of the well-known UCE variants, if we assume that the compression function satisfies one of our generalizations of UCE, basing the overall security on a plausible assumption. This result further validates the Merkle-Damg\u00e5rd construction and shows that UCE-like assumptions can serve both as a valid reference point for modular protocol analyses, as well as for the design of hash functions, linking those two aspects in a framework with explicit composition guarantees.", 
    "editor": [
      {
        "familyName": "Catalano", 
        "givenName": "Dario", 
        "type": "Person"
      }, 
      {
        "familyName": "De Prisco", 
        "givenName": "Roberto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-98113-0_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-98112-3", 
        "978-3-319-98113-0"
      ], 
      "name": "Security and Cryptography for Networks", 
      "type": "Book"
    }, 
    "keywords": [
      "universal computational extractors", 
      "random oracle model", 
      "hash function", 
      "random oracles", 
      "strong security guarantees", 
      "important cryptographic primitive", 
      "compression function", 
      "ideal compression function", 
      "Bellare et al", 
      "set of protocols", 
      "hash function construction", 
      "security properties", 
      "cryptographic primitives", 
      "overall security", 
      "security guarantees", 
      "security definitions", 
      "oracle model", 
      "indifferentiability framework", 
      "Merkle-Damg\u00e5rd construction", 
      "honest parties", 
      "general impossibility", 
      "oracle", 
      "second contribution", 
      "guarantees", 
      "multi-stage game", 
      "first contribution", 
      "security", 
      "valid reference point", 
      "function construction", 
      "indifferentiability", 
      "framework", 
      "protocol", 
      "primitives", 
      "extractor", 
      "protocol analysis", 
      "satisfies one", 
      "reference point", 
      "family of functions", 
      "game", 
      "generalization", 
      "special case", 
      "set", 
      "notion", 
      "ideal one", 
      "one", 
      "construction", 
      "simplicity", 
      "design", 
      "parties", 
      "assumption", 
      "definition", 
      "model", 
      "variants", 
      "aspects", 
      "function", 
      "contribution", 
      "point", 
      "et al", 
      "results", 
      "alternative", 
      "impossibility", 
      "analysis", 
      "cases", 
      "plausible assumptions", 
      "properties", 
      "al", 
      "contrast", 
      "family"
    ], 
    "name": "Security Definitions for Hash Functions: Combining UCE and Indifferentiability", 
    "pagination": "83-101", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1105982673"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-98113-0_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-98113-0_5", 
      "https://app.dimensions.ai/details/publication/pub.1105982673"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_180.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-98113-0_5"
  }
]
 

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-319-98113-0_5'

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-319-98113-0_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98113-0_5'

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-319-98113-0_5'


 

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

140 TRIPLES      23 PREDICATES      93 URIs      86 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-98113-0_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N39d94e5491cf4eb1977599987314ea19
4 schema:datePublished 2018-08-03
5 schema:datePublishedReg 2018-08-03
6 schema:description Hash functions are one of the most important cryptographic primitives, but their desired security properties have proven to be remarkably hard to formalize. To prove the security of a protocol using a hash function, nowadays often the random oracle model (ROM) is used due to its simplicity and its strong security guarantees. Moreover, hash function constructions are commonly proven to be secure by showing them to be indifferentiable from a random oracle when using an ideal compression function. However, it is well known that no hash function realizes a random oracle and no real compression function realizes an ideal one.As an alternative to the ROM, Bellare et al. recently proposed the notion of universal computational extractors (UCE). This notion formalizes that a family of functions “behaves like a random oracle” for “real-world” protocols while avoiding the general impossibility results. However, in contrast to the indifferentiability framework, UCE is formalized as a multi-stage game without clear composition guarantees.As a first contribution, we introduce context-restricted indifferentiability (CRI), a generalization of indifferentiability that allows us to model that the random oracle does not compose generally but can only be used within a well-specified set of protocols run by the honest parties, thereby making the provided composition guarantees explicit. We then show that UCE and its variants can be phrased as a special case of CRI. Moreover, we show how our notion of CRI leads to generalizations of UCE. As a second contribution, we prove that the hash function constructed by Merkle-Damgåd satisfies one of the well-known UCE variants, if we assume that the compression function satisfies one of our generalizations of UCE, basing the overall security on a plausible assumption. This result further validates the Merkle-Damgård construction and shows that UCE-like assumptions can serve both as a valid reference point for modular protocol analyses, as well as for the design of hash functions, linking those two aspects in a framework with explicit composition guarantees.
7 schema:editor N95ef2e82fc594ffcbcd218cbd4c2f5da
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N41b8c0eb5d85409bbd6f5716af03969e
12 schema:keywords Bellare et al
13 Merkle-Damgård construction
14 al
15 alternative
16 analysis
17 aspects
18 assumption
19 cases
20 compression function
21 construction
22 contrast
23 contribution
24 cryptographic primitives
25 definition
26 design
27 et al
28 extractor
29 family
30 family of functions
31 first contribution
32 framework
33 function
34 function construction
35 game
36 general impossibility
37 generalization
38 guarantees
39 hash function
40 hash function construction
41 honest parties
42 ideal compression function
43 ideal one
44 important cryptographic primitive
45 impossibility
46 indifferentiability
47 indifferentiability framework
48 model
49 multi-stage game
50 notion
51 one
52 oracle
53 oracle model
54 overall security
55 parties
56 plausible assumptions
57 point
58 primitives
59 properties
60 protocol
61 protocol analysis
62 random oracle model
63 random oracles
64 reference point
65 results
66 satisfies one
67 second contribution
68 security
69 security definitions
70 security guarantees
71 security properties
72 set
73 set of protocols
74 simplicity
75 special case
76 strong security guarantees
77 universal computational extractors
78 valid reference point
79 variants
80 schema:name Security Definitions for Hash Functions: Combining UCE and Indifferentiability
81 schema:pagination 83-101
82 schema:productId N36a1ad30702a4059aa9efc1a67730bb2
83 N81bdd7e263b249708b2b834346dc8849
84 schema:publisher Na4e14ae024b1441c95955e6bc38a2cb2
85 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105982673
86 https://doi.org/10.1007/978-3-319-98113-0_5
87 schema:sdDatePublished 2022-05-20T07:42
88 schema:sdLicense https://scigraph.springernature.com/explorer/license/
89 schema:sdPublisher N132bcff9ef9b4f79b1c9ccdff7210a83
90 schema:url https://doi.org/10.1007/978-3-319-98113-0_5
91 sgo:license sg:explorer/license/
92 sgo:sdDataset chapters
93 rdf:type schema:Chapter
94 N0dfe60114c0640a89607d09cb7dd0ab8 rdf:first sg:person.01316567627.91
95 rdf:rest rdf:nil
96 N132bcff9ef9b4f79b1c9ccdff7210a83 schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 N17067935b9fb47a9bc3ba5b154bccfec schema:familyName Catalano
99 schema:givenName Dario
100 rdf:type schema:Person
101 N36a1ad30702a4059aa9efc1a67730bb2 schema:name doi
102 schema:value 10.1007/978-3-319-98113-0_5
103 rdf:type schema:PropertyValue
104 N39d94e5491cf4eb1977599987314ea19 rdf:first sg:person.013356446515.02
105 rdf:rest N0dfe60114c0640a89607d09cb7dd0ab8
106 N3aa34adcc9da4c45a4f9ed366fc33132 rdf:first N9716aa6f7e5b48e5baa7cb966e6901bc
107 rdf:rest rdf:nil
108 N41b8c0eb5d85409bbd6f5716af03969e schema:isbn 978-3-319-98112-3
109 978-3-319-98113-0
110 schema:name Security and Cryptography for Networks
111 rdf:type schema:Book
112 N81bdd7e263b249708b2b834346dc8849 schema:name dimensions_id
113 schema:value pub.1105982673
114 rdf:type schema:PropertyValue
115 N95ef2e82fc594ffcbcd218cbd4c2f5da rdf:first N17067935b9fb47a9bc3ba5b154bccfec
116 rdf:rest N3aa34adcc9da4c45a4f9ed366fc33132
117 N9716aa6f7e5b48e5baa7cb966e6901bc schema:familyName De Prisco
118 schema:givenName Roberto
119 rdf:type schema:Person
120 Na4e14ae024b1441c95955e6bc38a2cb2 schema:name Springer Nature
121 rdf:type schema:Organisation
122 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
123 schema:name Information and Computing Sciences
124 rdf:type schema:DefinedTerm
125 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
126 schema:name Computation Theory and Mathematics
127 rdf:type schema:DefinedTerm
128 sg:person.01316567627.91 schema:affiliation grid-institutes:grid.5801.c
129 schema:familyName Maurer
130 schema:givenName Ueli
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91
132 rdf:type schema:Person
133 sg:person.013356446515.02 schema:affiliation grid-institutes:grid.5801.c
134 schema:familyName Jost
135 schema:givenName Daniel
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013356446515.02
137 rdf:type schema:Person
138 grid-institutes:grid.5801.c schema:alternateName Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland
139 schema:name Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland
140 rdf:type schema:Organization
 




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


...