Ontology type: schema:Chapter Open Access: True
2014
AUTHORSRan Canetti , Omer Paneth , Dimitrios Papadopoulos , Nikos Triandopoulos
ABSTRACTWe study the problem of verifiable delegation of computation over outsourced data, whereby a powerful worker maintains a large data structure for a weak client in a verifiable way. Compared to the well-studied problem of verifiable computation, this setting imposes additional difficulties since the verifier also needs to check the consistency of updates succinctly and without maintaining large state. We present a scheme for verifiable evaluation of hierarchical set operations (unions, intersections and set-differences) applied to a collection of dynamically changing sets of elements from a given domain. The verification cost incurred is proportional only to the size of the final outcome set and to the size of the query, and is independent of the cardinalities of the involved sets. The cost of updates is optimal (involving O(1) modular operations per update). Our construction extends that of [Papamanthou et al., CRYPTO 2011] and relies on a modified version of the extractable collision-resistant hash function (ECRH) construction, introduced in [Bitansky et al., ITCS 2012] that can be used to succinctly hash univariate polynomials. More... »
PAGES113-130
Public-Key Cryptography – PKC 2014
ISBN
978-3-642-54630-3
978-3-642-54631-0
http://scigraph.springernature.com/pub.10.1007/978-3-642-54631-0_7
DOIhttp://dx.doi.org/10.1007/978-3-642-54631-0_7
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1004765388
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/0806",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information Systems",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Dept. of Computer Science, Tel Aviv University, Israel",
"id": "http://www.grid.ac/institutes/grid.12136.37",
"name": [
"Dept. of Computer Science, Boston University, USA",
"Dept. of Computer Science, Tel Aviv University, Israel"
],
"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": "Dept. of Computer Science, Boston University, USA",
"id": "http://www.grid.ac/institutes/grid.189504.1",
"name": [
"Dept. of Computer Science, Boston University, USA"
],
"type": "Organization"
},
"familyName": "Paneth",
"givenName": "Omer",
"id": "sg:person.014073524511.68",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Dept. of Computer Science, Boston University, USA",
"id": "http://www.grid.ac/institutes/grid.189504.1",
"name": [
"Dept. of Computer Science, Boston University, USA"
],
"type": "Organization"
},
"familyName": "Papadopoulos",
"givenName": "Dimitrios",
"id": "sg:person.016045423157.47",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016045423157.47"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Dept. of Computer Science, Boston University, USA",
"id": "http://www.grid.ac/institutes/grid.189504.1",
"name": [
"RSA Laboratories, Cambridge, MA, USA",
"Dept. of Computer Science, Boston University, USA"
],
"type": "Organization"
},
"familyName": "Triandopoulos",
"givenName": "Nikos",
"id": "sg:person.011055225645.89",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011055225645.89"
],
"type": "Person"
}
],
"datePublished": "2014",
"datePublishedReg": "2014-01-01",
"description": "We study the problem of verifiable delegation of computation over outsourced data, whereby a powerful worker maintains a large data structure for a weak client in a verifiable way. Compared to the well-studied problem of verifiable computation, this setting imposes additional difficulties since the verifier also needs to check the consistency of updates succinctly and without maintaining large state. We present a scheme for verifiable evaluation of hierarchical set operations (unions, intersections and set-differences) applied to a collection of dynamically changing sets of elements from a given domain. The verification cost incurred is proportional only to the size of the final outcome set and to the size of the query, and is independent of the cardinalities of the involved sets. The cost of updates is optimal (involving O(1) modular operations per update). Our construction extends that of [Papamanthou et al., CRYPTO 2011] and relies on a modified version of the extractable collision-resistant hash function (ECRH) construction, introduced in [Bitansky et al., ITCS 2012] that can be used to succinctly hash univariate polynomials.",
"editor": [
{
"familyName": "Krawczyk",
"givenName": "Hugo",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-54631-0_7",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-642-54630-3",
"978-3-642-54631-0"
],
"name": "Public-Key Cryptography \u2013 PKC 2014",
"type": "Book"
},
"keywords": [
"large data structures",
"cost of updates",
"hash function construction",
"outsourced databases",
"weak client",
"verifiable computation",
"verifiable delegation",
"data structure",
"verification cost",
"verifiable evaluation",
"verifiable way",
"set operations",
"set of elements",
"function construction",
"computation",
"univariate polynomials",
"queries",
"verifier",
"update",
"set",
"additional difficulties",
"cost",
"operation",
"powerful workers",
"clients",
"scheme",
"database",
"delegation",
"cardinality",
"collection",
"construction",
"large state",
"version",
"domain",
"way",
"consistency",
"data",
"difficulties",
"evaluation",
"polynomials",
"state",
"size",
"final outcome",
"elements",
"setting",
"structure",
"workers",
"outcomes",
"problem"
],
"name": "Verifiable Set Operations over Outsourced Databases",
"pagination": "113-130",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1004765388"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-54631-0_7"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-54631-0_7",
"https://app.dimensions.ai/details/publication/pub.1004765388"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-06-01T22:35",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_451.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-54631-0_7"
}
]
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-54631-0_7'
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-54631-0_7'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-54631-0_7'
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-54631-0_7'
This table displays all metadata directly associated to this object as RDF triples.
135 TRIPLES
23 PREDICATES
75 URIs
68 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-3-642-54631-0_7 | schema:about | anzsrc-for:08 |
2 | ″ | ″ | anzsrc-for:0806 |
3 | ″ | schema:author | N38807370c442427ca7dbcced4a629824 |
4 | ″ | schema:datePublished | 2014 |
5 | ″ | schema:datePublishedReg | 2014-01-01 |
6 | ″ | schema:description | We study the problem of verifiable delegation of computation over outsourced data, whereby a powerful worker maintains a large data structure for a weak client in a verifiable way. Compared to the well-studied problem of verifiable computation, this setting imposes additional difficulties since the verifier also needs to check the consistency of updates succinctly and without maintaining large state. We present a scheme for verifiable evaluation of hierarchical set operations (unions, intersections and set-differences) applied to a collection of dynamically changing sets of elements from a given domain. The verification cost incurred is proportional only to the size of the final outcome set and to the size of the query, and is independent of the cardinalities of the involved sets. The cost of updates is optimal (involving O(1) modular operations per update). Our construction extends that of [Papamanthou et al., CRYPTO 2011] and relies on a modified version of the extractable collision-resistant hash function (ECRH) construction, introduced in [Bitansky et al., ITCS 2012] that can be used to succinctly hash univariate polynomials. |
7 | ″ | schema:editor | N04b474c78c3549729f5bc72eb02493ab |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | true |
11 | ″ | schema:isPartOf | N778022ce357b4102b0fa6544d8087fc4 |
12 | ″ | schema:keywords | additional difficulties |
13 | ″ | ″ | cardinality |
14 | ″ | ″ | clients |
15 | ″ | ″ | collection |
16 | ″ | ″ | computation |
17 | ″ | ″ | consistency |
18 | ″ | ″ | construction |
19 | ″ | ″ | cost |
20 | ″ | ″ | cost of updates |
21 | ″ | ″ | data |
22 | ″ | ″ | data structure |
23 | ″ | ″ | database |
24 | ″ | ″ | delegation |
25 | ″ | ″ | difficulties |
26 | ″ | ″ | domain |
27 | ″ | ″ | elements |
28 | ″ | ″ | evaluation |
29 | ″ | ″ | final outcome |
30 | ″ | ″ | function construction |
31 | ″ | ″ | hash function construction |
32 | ″ | ″ | large data structures |
33 | ″ | ″ | large state |
34 | ″ | ″ | operation |
35 | ″ | ″ | outcomes |
36 | ″ | ″ | outsourced databases |
37 | ″ | ″ | polynomials |
38 | ″ | ″ | powerful workers |
39 | ″ | ″ | problem |
40 | ″ | ″ | queries |
41 | ″ | ″ | scheme |
42 | ″ | ″ | set |
43 | ″ | ″ | set of elements |
44 | ″ | ″ | set operations |
45 | ″ | ″ | setting |
46 | ″ | ″ | size |
47 | ″ | ″ | state |
48 | ″ | ″ | structure |
49 | ″ | ″ | univariate polynomials |
50 | ″ | ″ | update |
51 | ″ | ″ | verifiable computation |
52 | ″ | ″ | verifiable delegation |
53 | ″ | ″ | verifiable evaluation |
54 | ″ | ″ | verifiable way |
55 | ″ | ″ | verification cost |
56 | ″ | ″ | verifier |
57 | ″ | ″ | version |
58 | ″ | ″ | way |
59 | ″ | ″ | weak client |
60 | ″ | ″ | workers |
61 | ″ | schema:name | Verifiable Set Operations over Outsourced Databases |
62 | ″ | schema:pagination | 113-130 |
63 | ″ | schema:productId | N7a9840d54abf489fa108a2b6120cc381 |
64 | ″ | ″ | N9540ce99042e4bbc8a932317667069c4 |
65 | ″ | schema:publisher | N0cce9786c96742b5ae9924000647ee14 |
66 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1004765388 |
67 | ″ | ″ | https://doi.org/10.1007/978-3-642-54631-0_7 |
68 | ″ | schema:sdDatePublished | 2022-06-01T22:35 |
69 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
70 | ″ | schema:sdPublisher | Nb441d7b538e5428cbaa33eee8b342655 |
71 | ″ | schema:url | https://doi.org/10.1007/978-3-642-54631-0_7 |
72 | ″ | sgo:license | sg:explorer/license/ |
73 | ″ | sgo:sdDataset | chapters |
74 | ″ | rdf:type | schema:Chapter |
75 | N04b474c78c3549729f5bc72eb02493ab | rdf:first | N65784d357b964bf49098faa770da68dd |
76 | ″ | rdf:rest | rdf:nil |
77 | N0cce9786c96742b5ae9924000647ee14 | schema:name | Springer Nature |
78 | ″ | rdf:type | schema:Organisation |
79 | N38807370c442427ca7dbcced4a629824 | rdf:first | sg:person.012320111457.74 |
80 | ″ | rdf:rest | N96dd923093de42729ca771b870e97b87 |
81 | N5568dd5ec4c345268f0198ebf1f02ac0 | rdf:first | sg:person.011055225645.89 |
82 | ″ | rdf:rest | rdf:nil |
83 | N65784d357b964bf49098faa770da68dd | schema:familyName | Krawczyk |
84 | ″ | schema:givenName | Hugo |
85 | ″ | rdf:type | schema:Person |
86 | N778022ce357b4102b0fa6544d8087fc4 | schema:isbn | 978-3-642-54630-3 |
87 | ″ | ″ | 978-3-642-54631-0 |
88 | ″ | schema:name | Public-Key Cryptography – PKC 2014 |
89 | ″ | rdf:type | schema:Book |
90 | N7a9840d54abf489fa108a2b6120cc381 | schema:name | dimensions_id |
91 | ″ | schema:value | pub.1004765388 |
92 | ″ | rdf:type | schema:PropertyValue |
93 | N9540ce99042e4bbc8a932317667069c4 | schema:name | doi |
94 | ″ | schema:value | 10.1007/978-3-642-54631-0_7 |
95 | ″ | rdf:type | schema:PropertyValue |
96 | N96dd923093de42729ca771b870e97b87 | rdf:first | sg:person.014073524511.68 |
97 | ″ | rdf:rest | Nda98790000fc4863bdd70f7ee382b720 |
98 | Nb441d7b538e5428cbaa33eee8b342655 | schema:name | Springer Nature - SN SciGraph project |
99 | ″ | rdf:type | schema:Organization |
100 | Nda98790000fc4863bdd70f7ee382b720 | rdf:first | sg:person.016045423157.47 |
101 | ″ | rdf:rest | N5568dd5ec4c345268f0198ebf1f02ac0 |
102 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |
103 | ″ | schema:name | Information and Computing Sciences |
104 | ″ | rdf:type | schema:DefinedTerm |
105 | anzsrc-for:0806 | schema:inDefinedTermSet | anzsrc-for: |
106 | ″ | schema:name | Information Systems |
107 | ″ | rdf:type | schema:DefinedTerm |
108 | sg:person.011055225645.89 | schema:affiliation | grid-institutes:grid.189504.1 |
109 | ″ | schema:familyName | Triandopoulos |
110 | ″ | schema:givenName | Nikos |
111 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011055225645.89 |
112 | ″ | rdf:type | schema:Person |
113 | sg:person.012320111457.74 | schema:affiliation | grid-institutes:grid.12136.37 |
114 | ″ | schema:familyName | Canetti |
115 | ″ | schema:givenName | Ran |
116 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74 |
117 | ″ | rdf:type | schema:Person |
118 | sg:person.014073524511.68 | schema:affiliation | grid-institutes:grid.189504.1 |
119 | ″ | schema:familyName | Paneth |
120 | ″ | schema:givenName | Omer |
121 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68 |
122 | ″ | rdf:type | schema:Person |
123 | sg:person.016045423157.47 | schema:affiliation | grid-institutes:grid.189504.1 |
124 | ″ | schema:familyName | Papadopoulos |
125 | ″ | schema:givenName | Dimitrios |
126 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016045423157.47 |
127 | ″ | rdf:type | schema:Person |
128 | grid-institutes:grid.12136.37 | schema:alternateName | Dept. of Computer Science, Tel Aviv University, Israel |
129 | ″ | schema:name | Dept. of Computer Science, Boston University, USA |
130 | ″ | ″ | Dept. of Computer Science, Tel Aviv University, Israel |
131 | ″ | rdf:type | schema:Organization |
132 | grid-institutes:grid.189504.1 | schema:alternateName | Dept. of Computer Science, Boston University, USA |
133 | ″ | schema:name | Dept. of Computer Science, Boston University, USA |
134 | ″ | ″ | RSA Laboratories, Cambridge, MA, USA |
135 | ″ | rdf:type | schema:Organization |