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", 
    "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

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.

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
 




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


...