Query-Complexity Amplification for Random Oracles View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015

AUTHORS

Grégory Demay , Peter Gaži , Ueli Maurer , Björn Tackmann

ABSTRACT

Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it c times, for some parameter c, in the hope that any query to the scheme requires c evaluations of the underlying hash function. However, results by Dodis et al. (Crypto 2012) imply that plain iteration falls short of achieving this goal, and designing schemes which provably have such a desirable property remained an open problem.This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing R queries (for the adversary) into one provably allowing only r < R queries. Turned around, this means that making r queries to the scheme requires at least R queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve c-fold QCA for both the honest parties and the adversary, for any fixed parameter c. More... »

PAGES

159-180

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-17470-9_10

DOI

http://dx.doi.org/10.1007/978-3-319-17470-9_10

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Demay", 
        "givenName": "Gr\u00e9gory", 
        "id": "sg:person.015232157523.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015232157523.41"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Science and Technology, Klosterneuburg, Austria", 
          "id": "http://www.grid.ac/institutes/grid.33565.36", 
          "name": [
            "Institute of Science and Technology, Klosterneuburg, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ga\u017ei", 
        "givenName": "Peter", 
        "id": "sg:person.012620015221.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012620015221.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science and Engineering, University of California, San Diego, USA", 
          "id": "http://www.grid.ac/institutes/grid.266100.3", 
          "name": [
            "Computer Science and Engineering, University of California, San Diego, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tackmann", 
        "givenName": "Bj\u00f6rn", 
        "id": "sg:person.07617171521.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07617171521.69"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015", 
    "datePublishedReg": "2015-01-01", 
    "description": "Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it c\u00a0times, for some parameter c, in the hope that any query to the scheme requires c evaluations of the underlying hash function. However, results by Dodis et al. (Crypto 2012) imply that plain iteration falls short of achieving this goal, and designing schemes which provably have such a desirable property remained an open problem.This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing R queries (for the adversary) into one provably allowing only r\u2009<\u2009R queries. Turned around, this means that making r queries to the scheme requires at least R queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve c-fold QCA for both the honest parties and the adversary, for any fixed parameter\u00a0c.", 
    "editor": [
      {
        "familyName": "Lehmann", 
        "givenName": "Anja", 
        "type": "Person"
      }, 
      {
        "familyName": "Wolf", 
        "givenName": "Stefan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-17470-9_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-17469-3", 
        "978-3-319-17470-9"
      ], 
      "name": "Information Theoretic Security", 
      "type": "Book"
    }, 
    "keywords": [
      "hash function", 
      "random oracles", 
      "proof of work", 
      "random oracle model", 
      "brute force attack", 
      "honest users", 
      "cryptographic schemes", 
      "legitimate users", 
      "oracle model", 
      "computational complexity", 
      "queries", 
      "Dodis et al", 
      "honest parties", 
      "query complexity", 
      "oracle", 
      "open problem", 
      "adversary", 
      "users", 
      "natural approach", 
      "new scheme", 
      "complexity", 
      "scheme", 
      "iteration", 
      "desirable properties", 
      "computation", 
      "attacks", 
      "indifferentiability", 
      "goal", 
      "certain amount", 
      "proof", 
      "useful technique", 
      "technique", 
      "example", 
      "parties", 
      "work", 
      "model", 
      "parameter c", 
      "function", 
      "evaluation", 
      "time", 
      "et al", 
      "amount", 
      "sense", 
      "results", 
      "QCA", 
      "C evaluation", 
      "parameters", 
      "hope", 
      "properties", 
      "al", 
      "amplifier scheme", 
      "amplification", 
      "problem", 
      "approach", 
      "paper"
    ], 
    "name": "Query-Complexity Amplification for Random Oracles", 
    "pagination": "159-180", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044900178"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-17470-9_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-17470-9_10", 
      "https://app.dimensions.ai/details/publication/pub.1044900178"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:41", 
    "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_131.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-17470-9_10"
  }
]
 

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-17470-9_10'

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-17470-9_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-17470-9_10'

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-17470-9_10'


 

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

147 TRIPLES      23 PREDICATES      81 URIs      74 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-17470-9_10 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Naf963dccd4754789b393e044abfe86d7
4 schema:datePublished 2015
5 schema:datePublishedReg 2015-01-01
6 schema:description Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it c times, for some parameter c, in the hope that any query to the scheme requires c evaluations of the underlying hash function. However, results by Dodis et al. (Crypto 2012) imply that plain iteration falls short of achieving this goal, and designing schemes which provably have such a desirable property remained an open problem.This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing R queries (for the adversary) into one provably allowing only r < R queries. Turned around, this means that making r queries to the scheme requires at least R queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve c-fold QCA for both the honest parties and the adversary, for any fixed parameter c.
7 schema:editor N7ea086b581b54f18807b87f0ab99827a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ncaa177a7aed144f399b608625d6f821a
12 schema:keywords C evaluation
13 Dodis et al
14 QCA
15 adversary
16 al
17 amount
18 amplification
19 amplifier scheme
20 approach
21 attacks
22 brute force attack
23 certain amount
24 complexity
25 computation
26 computational complexity
27 cryptographic schemes
28 desirable properties
29 et al
30 evaluation
31 example
32 function
33 goal
34 hash function
35 honest parties
36 honest users
37 hope
38 indifferentiability
39 iteration
40 legitimate users
41 model
42 natural approach
43 new scheme
44 open problem
45 oracle
46 oracle model
47 paper
48 parameter c
49 parameters
50 parties
51 problem
52 proof
53 proof of work
54 properties
55 queries
56 query complexity
57 random oracle model
58 random oracles
59 results
60 scheme
61 sense
62 technique
63 time
64 useful technique
65 users
66 work
67 schema:name Query-Complexity Amplification for Random Oracles
68 schema:pagination 159-180
69 schema:productId Nc2f632b8042b4818975f55e1e9acbd3c
70 Nd7a69b72042643fe96f1656c2bcb0478
71 schema:publisher N71e70c1fd35445ea807a9b4c441b3d0b
72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044900178
73 https://doi.org/10.1007/978-3-319-17470-9_10
74 schema:sdDatePublished 2022-05-20T07:41
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher N81445666daee42149e06657633213469
77 schema:url https://doi.org/10.1007/978-3-319-17470-9_10
78 sgo:license sg:explorer/license/
79 sgo:sdDataset chapters
80 rdf:type schema:Chapter
81 N08a88b823ab34950b839ae8a4a6a47aa schema:familyName Wolf
82 schema:givenName Stefan
83 rdf:type schema:Person
84 N27ddab1262e64e57a81b59122fc5080c schema:familyName Lehmann
85 schema:givenName Anja
86 rdf:type schema:Person
87 N2826d62cd8e54372b26c95324001da57 rdf:first sg:person.01316567627.91
88 rdf:rest N312dc8fe20c744eeac24d5b29958f0cb
89 N312dc8fe20c744eeac24d5b29958f0cb rdf:first sg:person.07617171521.69
90 rdf:rest rdf:nil
91 N71e70c1fd35445ea807a9b4c441b3d0b schema:name Springer Nature
92 rdf:type schema:Organisation
93 N7ea086b581b54f18807b87f0ab99827a rdf:first N27ddab1262e64e57a81b59122fc5080c
94 rdf:rest N883b28b6e70247fa8bd9d401288495e0
95 N81445666daee42149e06657633213469 schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 N883b28b6e70247fa8bd9d401288495e0 rdf:first N08a88b823ab34950b839ae8a4a6a47aa
98 rdf:rest rdf:nil
99 Naf963dccd4754789b393e044abfe86d7 rdf:first sg:person.015232157523.41
100 rdf:rest Ncad0e79a6fb84cb891762cfd26c8e07d
101 Nc2f632b8042b4818975f55e1e9acbd3c schema:name dimensions_id
102 schema:value pub.1044900178
103 rdf:type schema:PropertyValue
104 Ncaa177a7aed144f399b608625d6f821a schema:isbn 978-3-319-17469-3
105 978-3-319-17470-9
106 schema:name Information Theoretic Security
107 rdf:type schema:Book
108 Ncad0e79a6fb84cb891762cfd26c8e07d rdf:first sg:person.012620015221.67
109 rdf:rest N2826d62cd8e54372b26c95324001da57
110 Nd7a69b72042643fe96f1656c2bcb0478 schema:name doi
111 schema:value 10.1007/978-3-319-17470-9_10
112 rdf:type schema:PropertyValue
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
117 schema:name Data Format
118 rdf:type schema:DefinedTerm
119 sg:person.012620015221.67 schema:affiliation grid-institutes:grid.33565.36
120 schema:familyName Gaži
121 schema:givenName Peter
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012620015221.67
123 rdf:type schema:Person
124 sg:person.01316567627.91 schema:affiliation grid-institutes:grid.5801.c
125 schema:familyName Maurer
126 schema:givenName Ueli
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91
128 rdf:type schema:Person
129 sg:person.015232157523.41 schema:affiliation grid-institutes:grid.5801.c
130 schema:familyName Demay
131 schema:givenName Grégory
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015232157523.41
133 rdf:type schema:Person
134 sg:person.07617171521.69 schema:affiliation grid-institutes:grid.266100.3
135 schema:familyName Tackmann
136 schema:givenName Björn
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07617171521.69
138 rdf:type schema:Person
139 grid-institutes:grid.266100.3 schema:alternateName Computer Science and Engineering, University of California, San Diego, USA
140 schema:name Computer Science and Engineering, University of California, San Diego, USA
141 rdf:type schema:Organization
142 grid-institutes:grid.33565.36 schema:alternateName Institute of Science and Technology, Klosterneuburg, Austria
143 schema:name Institute of Science and Technology, Klosterneuburg, Austria
144 rdf:type schema:Organization
145 grid-institutes:grid.5801.c schema:alternateName Department of Computer Science, ETH Zürich, Zürich, Switzerland
146 schema:name Department of Computer Science, ETH Zürich, Zürich, Switzerland
147 rdf:type schema:Organization
 




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


...