Amplifying Collision Resistance: A Complexity-Theoretic Treatment View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007-01-01

AUTHORS

Ran Canetti , Ron Rivest , Madhu Sudan , Luca Trevisan , Salil Vadhan , Hoeteck Wee

ABSTRACT

We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into strongly collision-resistant ones in the standard model of computation. We measure the level of collision resistance by the maximum probability, over the choice of the key, for which an efficient adversary can find a collision. The goal is to obtain constructions with short output, short keys, small loss in adversarial complexity tolerated, and a good trade-off between compression ratio and computational complexity. We provide an analysis of several simple constructions, and show that many of the parameters achieved by our constructions are almost optimal in some sense. More... »

PAGES

264-283

Book

TITLE

Advances in Cryptology - CRYPTO 2007

ISBN

978-3-540-74142-8
978-3-540-74143-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74143-5_15

DOI

http://dx.doi.org/10.1007/978-3-540-74143-5_15

DIMENSIONS

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


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/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IBM Research", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "IBM Research"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Canetti", 
        "givenName": "Ran", 
        "id": "sg:person.012320111457.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT CSAIL", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT CSAIL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rivest", 
        "givenName": "Ron", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT CSAIL", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT CSAIL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sudan", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Berkeley", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "id": "sg:person.015761757701.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Harvard University", 
          "id": "http://www.grid.ac/institutes/grid.38142.3c", 
          "name": [
            "Harvard University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vadhan", 
        "givenName": "Salil", 
        "id": "sg:person.015435416464.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015435416464.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Berkeley", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wee", 
        "givenName": "Hoeteck", 
        "id": "sg:person.011724333061.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724333061.15"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into strongly collision-resistant ones in the standard model of computation. We measure the level of collision resistance by the maximum probability, over the choice of the key, for which an efficient adversary can find a collision. The goal is to obtain constructions with short output, short keys, small loss in adversarial complexity tolerated, and a good trade-off between compression ratio and computational complexity. We provide an analysis of several simple constructions, and show that many of the parameters achieved by our constructions are almost optimal in some sense.", 
    "editor": [
      {
        "familyName": "Menezes", 
        "givenName": "Alfred", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-74143-5_15", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-74142-8", 
        "978-3-540-74143-5"
      ], 
      "name": "Advances in Cryptology - CRYPTO 2007", 
      "type": "Book"
    }, 
    "keywords": [
      "computational complexity", 
      "maximum probability", 
      "hardness amplification", 
      "collision-resistant hash functions", 
      "short keys", 
      "simple construction", 
      "short output", 
      "complexity", 
      "collision resistance", 
      "computation", 
      "construction", 
      "efficient adversary", 
      "hash functions", 
      "standard model", 
      "probability", 
      "function", 
      "compression ratio", 
      "sense", 
      "model", 
      "parameters", 
      "small loss", 
      "output", 
      "transformation", 
      "one", 
      "choice", 
      "adversary", 
      "goal", 
      "analysis", 
      "collisions", 
      "key", 
      "ratio", 
      "loss", 
      "levels", 
      "amplification", 
      "treatment", 
      "resistance", 
      "complexity-theoretic treatment", 
      "weakly collision-resistant hash functions", 
      "collision-resistant ones", 
      "adversarial complexity"
    ], 
    "name": "Amplifying Collision Resistance: A Complexity-Theoretic Treatment", 
    "pagination": "264-283", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1033227371"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-74143-5_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-74143-5_15", 
      "https://app.dimensions.ai/details/publication/pub.1033227371"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:10", 
    "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_175.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-74143-5_15"
  }
]
 

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-74143-5_15'

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-74143-5_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74143-5_15'

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-74143-5_15'


 

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

143 TRIPLES      23 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74143-5_15 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N1203550dcdd241c3bd78bbc41ff2a688
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into strongly collision-resistant ones in the standard model of computation. We measure the level of collision resistance by the maximum probability, over the choice of the key, for which an efficient adversary can find a collision. The goal is to obtain constructions with short output, short keys, small loss in adversarial complexity tolerated, and a good trade-off between compression ratio and computational complexity. We provide an analysis of several simple constructions, and show that many of the parameters achieved by our constructions are almost optimal in some sense.
7 schema:editor N603d64e42a1742c9a77476918841c638
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3aa3c5a2caa84412856aa9e6f414c06b
12 schema:keywords adversarial complexity
13 adversary
14 amplification
15 analysis
16 choice
17 collision resistance
18 collision-resistant hash functions
19 collision-resistant ones
20 collisions
21 complexity
22 complexity-theoretic treatment
23 compression ratio
24 computation
25 computational complexity
26 construction
27 efficient adversary
28 function
29 goal
30 hardness amplification
31 hash functions
32 key
33 levels
34 loss
35 maximum probability
36 model
37 one
38 output
39 parameters
40 probability
41 ratio
42 resistance
43 sense
44 short keys
45 short output
46 simple construction
47 small loss
48 standard model
49 transformation
50 treatment
51 weakly collision-resistant hash functions
52 schema:name Amplifying Collision Resistance: A Complexity-Theoretic Treatment
53 schema:pagination 264-283
54 schema:productId Na188d758d9754ad581d7b5ad6c602cc2
55 Ne2f0fc7bad8b4823a67bcd50c9f9dc3b
56 schema:publisher N55d84623275547fa9dc67b910105c200
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033227371
58 https://doi.org/10.1007/978-3-540-74143-5_15
59 schema:sdDatePublished 2022-01-01T19:10
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N2a191c4de4cc435480f970a3e3e53b51
62 schema:url https://doi.org/10.1007/978-3-540-74143-5_15
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N1203550dcdd241c3bd78bbc41ff2a688 rdf:first sg:person.012320111457.74
67 rdf:rest N5a20e825ec5d4c31a4645ddf7617ed29
68 N2a191c4de4cc435480f970a3e3e53b51 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 N3aa3c5a2caa84412856aa9e6f414c06b schema:isbn 978-3-540-74142-8
71 978-3-540-74143-5
72 schema:name Advances in Cryptology - CRYPTO 2007
73 rdf:type schema:Book
74 N4fe2cac8c6714e23a165e49c1f585112 rdf:first sg:person.015761757701.03
75 rdf:rest N65fd26f57cb341cab15294cda25ced6e
76 N55d84623275547fa9dc67b910105c200 schema:name Springer Nature
77 rdf:type schema:Organisation
78 N5a20e825ec5d4c31a4645ddf7617ed29 rdf:first Nb4cea7877f9b48bda5e58ad88ae534aa
79 rdf:rest N5e328a48dbc34755a5c1e51449d69f8f
80 N5e328a48dbc34755a5c1e51449d69f8f rdf:first sg:person.014663420265.17
81 rdf:rest N4fe2cac8c6714e23a165e49c1f585112
82 N603d64e42a1742c9a77476918841c638 rdf:first Ndb4652de9f1a48dcba01d1516bc7ecff
83 rdf:rest rdf:nil
84 N65fd26f57cb341cab15294cda25ced6e rdf:first sg:person.015435416464.10
85 rdf:rest Nef47e11d7f7a481d98a0a766b73b79b7
86 Na188d758d9754ad581d7b5ad6c602cc2 schema:name dimensions_id
87 schema:value pub.1033227371
88 rdf:type schema:PropertyValue
89 Nb4cea7877f9b48bda5e58ad88ae534aa schema:affiliation grid-institutes:grid.116068.8
90 schema:familyName Rivest
91 schema:givenName Ron
92 rdf:type schema:Person
93 Ndb4652de9f1a48dcba01d1516bc7ecff schema:familyName Menezes
94 schema:givenName Alfred
95 rdf:type schema:Person
96 Ne2f0fc7bad8b4823a67bcd50c9f9dc3b schema:name doi
97 schema:value 10.1007/978-3-540-74143-5_15
98 rdf:type schema:PropertyValue
99 Nef47e11d7f7a481d98a0a766b73b79b7 rdf:first sg:person.011724333061.15
100 rdf:rest rdf:nil
101 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
102 schema:name Mathematical Sciences
103 rdf:type schema:DefinedTerm
104 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
105 schema:name Statistics
106 rdf:type schema:DefinedTerm
107 sg:person.011724333061.15 schema:affiliation grid-institutes:grid.47840.3f
108 schema:familyName Wee
109 schema:givenName Hoeteck
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724333061.15
111 rdf:type schema:Person
112 sg:person.012320111457.74 schema:affiliation grid-institutes:None
113 schema:familyName Canetti
114 schema:givenName Ran
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74
116 rdf:type schema:Person
117 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
118 schema:familyName Sudan
119 schema:givenName Madhu
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
121 rdf:type schema:Person
122 sg:person.015435416464.10 schema:affiliation grid-institutes:grid.38142.3c
123 schema:familyName Vadhan
124 schema:givenName Salil
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015435416464.10
126 rdf:type schema:Person
127 sg:person.015761757701.03 schema:affiliation grid-institutes:grid.47840.3f
128 schema:familyName Trevisan
129 schema:givenName Luca
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03
131 rdf:type schema:Person
132 grid-institutes:None schema:alternateName IBM Research
133 schema:name IBM Research
134 rdf:type schema:Organization
135 grid-institutes:grid.116068.8 schema:alternateName MIT CSAIL
136 schema:name MIT CSAIL
137 rdf:type schema:Organization
138 grid-institutes:grid.38142.3c schema:alternateName Harvard University
139 schema:name Harvard University
140 rdf:type schema:Organization
141 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley
142 schema:name UC Berkeley
143 rdf:type schema:Organization
 




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


...