Verifiable Set Operations over Outsourced Databases View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Ran Canetti , Omer Paneth , Dimitrios Papadopoulos , Nikos Triandopoulos

ABSTRACT

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. More... »

PAGES

113-130

Book

TITLE

Public-Key Cryptography – PKC 2014

ISBN

978-3-642-54630-3
978-3-642-54631-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-54631-0_7

DOI

http://dx.doi.org/10.1007/978-3-642-54631-0_7

DIMENSIONS

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


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/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", 
    "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 way", 
      "verifiable evaluation", 
      "set operations", 
      "set of elements", 
      "function construction", 
      "computation", 
      "univariate polynomials", 
      "queries", 
      "verifier", 
      "update", 
      "set", 
      "additional difficulties", 
      "cost", 
      "operation", 
      "powerful workers", 
      "clients", 
      "scheme", 
      "database", 
      "cardinality", 
      "delegation", 
      "large state", 
      "collection", 
      "construction", 
      "domain", 
      "version", 
      "way", 
      "consistency", 
      "data", 
      "difficulties", 
      "evaluation", 
      "polynomials", 
      "final outcome", 
      "state", 
      "size", 
      "setting", 
      "elements", 
      "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-08-04T17:22", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_416.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

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-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.

134 TRIPLES      22 PREDICATES      74 URIs      67 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 Nbceeeae2573641c898d137f21bd2ec8c
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 N246b7d73f2d441f09b34cec4ee113df9
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nc5170c2945664f7f8e0c4210254e30dd
11 schema:keywords additional difficulties
12 cardinality
13 clients
14 collection
15 computation
16 consistency
17 construction
18 cost
19 cost of updates
20 data
21 data structure
22 database
23 delegation
24 difficulties
25 domain
26 elements
27 evaluation
28 final outcome
29 function construction
30 hash function construction
31 large data structures
32 large state
33 operation
34 outcomes
35 outsourced databases
36 polynomials
37 powerful workers
38 problem
39 queries
40 scheme
41 set
42 set of elements
43 set operations
44 setting
45 size
46 state
47 structure
48 univariate polynomials
49 update
50 verifiable computation
51 verifiable delegation
52 verifiable evaluation
53 verifiable way
54 verification cost
55 verifier
56 version
57 way
58 weak client
59 workers
60 schema:name Verifiable Set Operations over Outsourced Databases
61 schema:pagination 113-130
62 schema:productId N5d4201df5b5840ecbb63e0026189134e
63 Neb4270092f534d829a5225dae883470a
64 schema:publisher N235e5033448c488fa1441ad9b394d4ba
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004765388
66 https://doi.org/10.1007/978-3-642-54631-0_7
67 schema:sdDatePublished 2022-08-04T17:22
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N923b91722b974e58aa3fc4afdcfe1f46
70 schema:url https://doi.org/10.1007/978-3-642-54631-0_7
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N13f5cec006fc41e39c55e7eceb23dc2e schema:familyName Krawczyk
75 schema:givenName Hugo
76 rdf:type schema:Person
77 N235e5033448c488fa1441ad9b394d4ba schema:name Springer Nature
78 rdf:type schema:Organisation
79 N246b7d73f2d441f09b34cec4ee113df9 rdf:first N13f5cec006fc41e39c55e7eceb23dc2e
80 rdf:rest rdf:nil
81 N33ecbfd5eb3a41b8ad675feb3479aa98 rdf:first sg:person.011055225645.89
82 rdf:rest rdf:nil
83 N57b8c6e850054a84b90d91278f9a656a rdf:first sg:person.016045423157.47
84 rdf:rest N33ecbfd5eb3a41b8ad675feb3479aa98
85 N5d4201df5b5840ecbb63e0026189134e schema:name doi
86 schema:value 10.1007/978-3-642-54631-0_7
87 rdf:type schema:PropertyValue
88 N923b91722b974e58aa3fc4afdcfe1f46 schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 Nbceeeae2573641c898d137f21bd2ec8c rdf:first sg:person.012320111457.74
91 rdf:rest Ne92ca32312dd49319189b01da5870a10
92 Nc5170c2945664f7f8e0c4210254e30dd schema:isbn 978-3-642-54630-3
93 978-3-642-54631-0
94 schema:name Public-Key Cryptography – PKC 2014
95 rdf:type schema:Book
96 Ne92ca32312dd49319189b01da5870a10 rdf:first sg:person.014073524511.68
97 rdf:rest N57b8c6e850054a84b90d91278f9a656a
98 Neb4270092f534d829a5225dae883470a schema:name dimensions_id
99 schema:value pub.1004765388
100 rdf:type schema:PropertyValue
101 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
102 schema:name Information and Computing Sciences
103 rdf:type schema:DefinedTerm
104 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
105 schema:name Information Systems
106 rdf:type schema:DefinedTerm
107 sg:person.011055225645.89 schema:affiliation grid-institutes:grid.189504.1
108 schema:familyName Triandopoulos
109 schema:givenName Nikos
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011055225645.89
111 rdf:type schema:Person
112 sg:person.012320111457.74 schema:affiliation grid-institutes:grid.12136.37
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.014073524511.68 schema:affiliation grid-institutes:grid.189504.1
118 schema:familyName Paneth
119 schema:givenName Omer
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
121 rdf:type schema:Person
122 sg:person.016045423157.47 schema:affiliation grid-institutes:grid.189504.1
123 schema:familyName Papadopoulos
124 schema:givenName Dimitrios
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016045423157.47
126 rdf:type schema:Person
127 grid-institutes:grid.12136.37 schema:alternateName Dept. of Computer Science, Tel Aviv University, Israel
128 schema:name Dept. of Computer Science, Boston University, USA
129 Dept. of Computer Science, Tel Aviv University, Israel
130 rdf:type schema:Organization
131 grid-institutes:grid.189504.1 schema:alternateName Dept. of Computer Science, Boston University, USA
132 schema:name Dept. of Computer Science, Boston University, USA
133 RSA Laboratories, Cambridge, MA, USA
134 rdf:type schema:Organization
 




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


...