Ontology type: schema:Chapter Open Access: True
2013
AUTHORSGrégory Demay , Peter Gaži , Martin Hirt , Ueli Maurer
ABSTRACTA 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... »
PAGES664-683
Advances in Cryptology – EUROCRYPT 2013
ISBN
978-3-642-38347-2
978-3-642-38348-9
http://scigraph.springernature.com/pub.10.1007/978-3-642-38348-9_39
DOIhttp://dx.doi.org/10.1007/978-3-642-38348-9_39
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1007567403
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
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 |