2014 | OriginalPaper | Buchkapitel
Verifiable Set Operations over Outsourced Databases
verfasst von : Ran Canetti, Omer Paneth, Dimitrios Papadopoulos, Nikos Triandopoulos
Erschienen in: Public-Key Cryptography – PKC 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.