Verifiable set operations over outsourced databases

Ran Canetti; Omer Paneth; Dimitrios Papadopoulos; Nikos Triandopoulos

doi:10.1007/978-3-642-54631-0_7

Verifiable set operations over outsourced databases

Ran Canetti^*
, Omer Paneth
, Dimitrios Papadopoulos
, Nikos Triandopoulos

^*Corresponding author for this work

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

45 Citations (Scopus)

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.

Original language	English
Title of host publication	Public-Key Cryptography, PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
Publisher	Springer Verlag
Pages	113-130
Number of pages	18
ISBN (Print)	9783642546303
DOIs	https://doi.org/10.1007/978-3-642-54631-0_7
Publication status	Published - 2014
Externally published	Yes
Event	17th IACR International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014 - Buenos Aires, Argentina Duration: 26 Mar 2014 → 28 Mar 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8383 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th IACR International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014
Country/Territory	Argentina
City	Buenos Aires
Period	26/03/14 → 28/03/14

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Access to Document

10.1007/978-3-642-54631-0_7

Cite this

Canetti, R., Paneth, O., Papadopoulos, D., & Triandopoulos, N. (2014). Verifiable set operations over outsourced databases. In Public-Key Cryptography, PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings (pp. 113-130). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8383 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-54631-0_7

Canetti, Ran ; Paneth, Omer ; Papadopoulos, Dimitrios et al. / Verifiable set operations over outsourced databases. Public-Key Cryptography, PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Springer Verlag, 2014. pp. 113-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f0e7f31602e54a91937be4d7857cb8f5,

title = "Verifiable set operations over outsourced databases",

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

author = "Ran Canetti and Omer Paneth and Dimitrios Papadopoulos and Nikos Triandopoulos",

year = "2014",

doi = "10.1007/978-3-642-54631-0\_7",

language = "English",

isbn = "9783642546303",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "113--130",

booktitle = "Public-Key Cryptography, PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings",

note = "17th IACR International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014 ; Conference date: 26-03-2014 Through 28-03-2014",

}

Canetti, R, Paneth, O, Papadopoulos, D & Triandopoulos, N 2014, Verifiable set operations over outsourced databases. in Public-Key Cryptography, PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8383 LNCS, Springer Verlag, pp. 113-130, 17th IACR International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014, Buenos Aires, Argentina, 26/03/14. https://doi.org/10.1007/978-3-642-54631-0_7

Verifiable set operations over outsourced databases. / Canetti, Ran; Paneth, Omer; Papadopoulos, Dimitrios et al.
Public-Key Cryptography, PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Springer Verlag, 2014. p. 113-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8383 LNCS).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Verifiable set operations over outsourced databases

AU - Canetti, Ran

AU - Paneth, Omer

AU - Papadopoulos, Dimitrios

AU - Triandopoulos, Nikos

PY - 2014

Y1 - 2014

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

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

UR - https://openalex.org/W189940358

U2 - 10.1007/978-3-642-54631-0_7

DO - 10.1007/978-3-642-54631-0_7

M3 - Conference Paper published in a book

SN - 9783642546303

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 113

EP - 130

BT - Public-Key Cryptography, PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings

PB - Springer Verlag

T2 - 17th IACR International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014

Y2 - 26 March 2014 through 28 March 2014

ER -

Canetti R, Paneth O, Papadopoulos D, Triandopoulos N. Verifiable set operations over outsourced databases. In Public-Key Cryptography, PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Springer Verlag. 2014. p. 113-130. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-54631-0_7

Verifiable set operations over outsourced databases

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this