Resource-Restricted Indifferentiability View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Grégory Demay , Peter Gaži , Martin Hirt , Ueli Maurer

ABSTRACT

A major general paradigm in cryptography is the following argument: Whatever an adversary could do in the real world, it could just as well do in the ideal world. The standard interpretation of “just as well” is that the translation from the real to the ideal world, usually called a simulator, is achieved by a probabilistic polynomial-time algorithm. This means that a polynomial blow-up of the adversary’s time and memory requirements is considered acceptable.In certain contexts this interpretation of “just as well” is inadequate, for example if the concrete amount of memory used by the adversary is relevant. The example of Ristenpart et al. (Eurocrypt 2011), for which the original indifferentiability notion introduced by Maurer et al. (Eurocrypt 2004) is shown to be insufficient, turns out to be exactly of this type. It requires a fine-grained statement about the adversary’s memory capacity, calling for a generalized treatment of indifferentiability where specific resource requirements can be taken into account by modeling them explicitly.We provide such treatment and employ the new indifferentiability notion to prove lower bounds on the memory required by any simulator in a domain extension construction of a public random function. In particular, for simulators without memory, even domain extension by a single bit turns out to be impossible. Moreover, for the construction of a random oracle from an ideal compression function, memory roughly linear in the length of the longest query is required. This also implies the impossibility of such domain extension in any multi-party setting with potential individual misbehavior by parties (i.e., no central adversary). More... »

PAGES

664-683

Book

TITLE

Advances in Cryptology – EUROCRYPT 2013

ISBN

978-3-642-38347-2
978-3-642-38348-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38348-9_39

DOI

http://dx.doi.org/10.1007/978-3-642-38348-9_39

DIMENSIONS

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


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 Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich, 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": "Department of Computer Science, ETH Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich, Switzerland"
          ], 
          "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 Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hirt", 
        "givenName": "Martin", 
        "id": "sg:person.010611500757.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010611500757.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, ETH Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH 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": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "A major general paradigm in cryptography is the following argument: Whatever an adversary could do in the real world, it could just as well do in the ideal world. The standard interpretation of \u201cjust as well\u201d is that the translation from the real to the ideal world, usually called a simulator, is achieved by a probabilistic polynomial-time algorithm. This means that a polynomial blow-up of the adversary\u2019s time and memory requirements is considered acceptable.In certain contexts this interpretation of \u201cjust as well\u201d is inadequate, for example if the concrete amount of memory used by the adversary is relevant. The example of Ristenpart et al. (Eurocrypt 2011), for which the original indifferentiability notion introduced by Maurer et al. (Eurocrypt 2004) is shown to be insufficient, turns out to be exactly of this type. It requires a fine-grained statement about the adversary\u2019s memory capacity, calling for a generalized treatment of indifferentiability where specific resource requirements can be taken into account by modeling them explicitly.We provide such treatment and employ the new indifferentiability notion to prove lower bounds on the memory required by any simulator in a domain extension construction of a public random function. In particular, for simulators without memory, even domain extension by a single bit turns out to be impossible. Moreover, for the construction of a random oracle from an ideal compression function, memory roughly linear in the length of the longest query is required. This also implies the impossibility of such domain extension in any multi-party setting with potential individual misbehavior by parties (i.e., no central adversary).", 
    "editor": [
      {
        "familyName": "Johansson", 
        "givenName": "Thomas", 
        "type": "Person"
      }, 
      {
        "familyName": "Nguyen", 
        "givenName": "Phong Q.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-38348-9_39", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-38347-2", 
        "978-3-642-38348-9"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2013", 
      "type": "Book"
    }, 
    "keywords": [
      "probabilistic polynomial time algorithm", 
      "ideal compression function", 
      "specific resource requirements", 
      "multi-party setting", 
      "public random function", 
      "polynomial time algorithm", 
      "long queries", 
      "random oracles", 
      "memory requirements", 
      "resource requirements", 
      "real world", 
      "memory capacity", 
      "domain extension", 
      "individual misbehavior", 
      "compression function", 
      "single bit", 
      "adversary", 
      "simulator", 
      "general paradigm", 
      "ideal world", 
      "Maurer et al", 
      "indifferentiability", 
      "lower bounds", 
      "queries", 
      "cryptography", 
      "requirements", 
      "memory", 
      "oracle", 
      "algorithm", 
      "random function", 
      "certain contexts", 
      "misbehavior", 
      "bits", 
      "paradigm", 
      "extension", 
      "example", 
      "world", 
      "concrete amount", 
      "notion", 
      "construction", 
      "extension construction", 
      "bounds", 
      "et al", 
      "time", 
      "parties", 
      "context", 
      "translation", 
      "function", 
      "interpretation", 
      "amount", 
      "statements", 
      "impossibility", 
      "setting", 
      "account", 
      "types", 
      "generalized treatment", 
      "standard interpretation", 
      "capacity", 
      "al", 
      "argument", 
      "length", 
      "treatment", 
      "such treatment"
    ], 
    "name": "Resource-Restricted Indifferentiability", 
    "pagination": "664-683", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007567403"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-38348-9_39"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-38348-9_39", 
      "https://app.dimensions.ai/details/publication/pub.1007567403"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:48", 
    "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_428.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-38348-9_39"
  }
]
 

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-642-38348-9_39'

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-642-38348-9_39'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38348-9_39'

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-642-38348-9_39'


 

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

149 TRIPLES      23 PREDICATES      89 URIs      82 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38348-9_39 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Ncdabd314ff264e76b6ce460456c201a6
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description A major general paradigm in cryptography is the following argument: Whatever an adversary could do in the real world, it could just as well do in the ideal world. The standard interpretation of “just as well” is that the translation from the real to the ideal world, usually called a simulator, is achieved by a probabilistic polynomial-time algorithm. This means that a polynomial blow-up of the adversary’s time and memory requirements is considered acceptable.In certain contexts this interpretation of “just as well” is inadequate, for example if the concrete amount of memory used by the adversary is relevant. The example of Ristenpart et al. (Eurocrypt 2011), for which the original indifferentiability notion introduced by Maurer et al. (Eurocrypt 2004) is shown to be insufficient, turns out to be exactly of this type. It requires a fine-grained statement about the adversary’s memory capacity, calling for a generalized treatment of indifferentiability where specific resource requirements can be taken into account by modeling them explicitly.We provide such treatment and employ the new indifferentiability notion to prove lower bounds on the memory required by any simulator in a domain extension construction of a public random function. In particular, for simulators without memory, even domain extension by a single bit turns out to be impossible. Moreover, for the construction of a random oracle from an ideal compression function, memory roughly linear in the length of the longest query is required. This also implies the impossibility of such domain extension in any multi-party setting with potential individual misbehavior by parties (i.e., no central adversary).
7 schema:editor N9346895b8e9d4dcaac7535b09f22794f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N99bc74ff258a4895b99f453254f258d3
12 schema:keywords Maurer et al
13 account
14 adversary
15 al
16 algorithm
17 amount
18 argument
19 bits
20 bounds
21 capacity
22 certain contexts
23 compression function
24 concrete amount
25 construction
26 context
27 cryptography
28 domain extension
29 et al
30 example
31 extension
32 extension construction
33 function
34 general paradigm
35 generalized treatment
36 ideal compression function
37 ideal world
38 impossibility
39 indifferentiability
40 individual misbehavior
41 interpretation
42 length
43 long queries
44 lower bounds
45 memory
46 memory capacity
47 memory requirements
48 misbehavior
49 multi-party setting
50 notion
51 oracle
52 paradigm
53 parties
54 polynomial time algorithm
55 probabilistic polynomial time algorithm
56 public random function
57 queries
58 random function
59 random oracles
60 real world
61 requirements
62 resource requirements
63 setting
64 simulator
65 single bit
66 specific resource requirements
67 standard interpretation
68 statements
69 such treatment
70 time
71 translation
72 treatment
73 types
74 world
75 schema:name Resource-Restricted Indifferentiability
76 schema:pagination 664-683
77 schema:productId Nd12c9aa9b1c14b7289dd324e6bea18e0
78 Nf5b87e6804674b20938dd1d355b5920d
79 schema:publisher N3d19229d320a43be952484aff66b5aac
80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007567403
81 https://doi.org/10.1007/978-3-642-38348-9_39
82 schema:sdDatePublished 2022-05-20T07:48
83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
84 schema:sdPublisher Ne8b4841625be4aa196463f98e42b21e5
85 schema:url https://doi.org/10.1007/978-3-642-38348-9_39
86 sgo:license sg:explorer/license/
87 sgo:sdDataset chapters
88 rdf:type schema:Chapter
89 N092fd8db93394bfa8642231ea43c4829 schema:familyName Nguyen
90 schema:givenName Phong Q.
91 rdf:type schema:Person
92 N0b250cbd99b448638bed16ddb112ee38 rdf:first sg:person.01316567627.91
93 rdf:rest rdf:nil
94 N3d19229d320a43be952484aff66b5aac schema:name Springer Nature
95 rdf:type schema:Organisation
96 N73538d2cc5d941a6862d7aad6ebcaf21 rdf:first sg:person.012620015221.67
97 rdf:rest Nfd90b9f197fd4f3eba697c0c24e6bdd5
98 N8f118cc86ab54f3b82132c2279c1ad8d schema:familyName Johansson
99 schema:givenName Thomas
100 rdf:type schema:Person
101 N9346895b8e9d4dcaac7535b09f22794f rdf:first N8f118cc86ab54f3b82132c2279c1ad8d
102 rdf:rest Nf11233a9d7db4887aec9e2f812dc6d60
103 N99bc74ff258a4895b99f453254f258d3 schema:isbn 978-3-642-38347-2
104 978-3-642-38348-9
105 schema:name Advances in Cryptology – EUROCRYPT 2013
106 rdf:type schema:Book
107 Ncdabd314ff264e76b6ce460456c201a6 rdf:first sg:person.015232157523.41
108 rdf:rest N73538d2cc5d941a6862d7aad6ebcaf21
109 Nd12c9aa9b1c14b7289dd324e6bea18e0 schema:name doi
110 schema:value 10.1007/978-3-642-38348-9_39
111 rdf:type schema:PropertyValue
112 Ne8b4841625be4aa196463f98e42b21e5 schema:name Springer Nature - SN SciGraph project
113 rdf:type schema:Organization
114 Nf11233a9d7db4887aec9e2f812dc6d60 rdf:first N092fd8db93394bfa8642231ea43c4829
115 rdf:rest rdf:nil
116 Nf5b87e6804674b20938dd1d355b5920d schema:name dimensions_id
117 schema:value pub.1007567403
118 rdf:type schema:PropertyValue
119 Nfd90b9f197fd4f3eba697c0c24e6bdd5 rdf:first sg:person.010611500757.30
120 rdf:rest N0b250cbd99b448638bed16ddb112ee38
121 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
122 schema:name Information and Computing Sciences
123 rdf:type schema:DefinedTerm
124 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
125 schema:name Data Format
126 rdf:type schema:DefinedTerm
127 sg:person.010611500757.30 schema:affiliation grid-institutes:grid.5801.c
128 schema:familyName Hirt
129 schema:givenName Martin
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010611500757.30
131 rdf:type schema:Person
132 sg:person.012620015221.67 schema:affiliation grid-institutes:grid.5801.c
133 schema:familyName Gaži
134 schema:givenName Peter
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012620015221.67
136 rdf:type schema:Person
137 sg:person.01316567627.91 schema:affiliation grid-institutes:grid.5801.c
138 schema:familyName Maurer
139 schema:givenName Ueli
140 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91
141 rdf:type schema:Person
142 sg:person.015232157523.41 schema:affiliation grid-institutes:grid.5801.c
143 schema:familyName Demay
144 schema:givenName Grégory
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015232157523.41
146 rdf:type schema:Person
147 grid-institutes:grid.5801.c schema:alternateName Department of Computer Science, ETH Zurich, Switzerland
148 schema:name Department of Computer Science, ETH Zurich, Switzerland
149 rdf:type schema:Organization
 




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


...