Trust-Preserving Set Operations

View/ Open
Date
2003-09-25Author
Morselli, Ruggero
Bhattacharjee, Bobby
Katz, Jonathan
Keleher, Pete
Metadata
Show full item recordAbstract
We describe a method of performing trust-preserving set operations by
untrusted parties. Our motivation for this is the problem of securely
reusing content-based search results in peer-to-peer networks. We model
search results and indexes as data sets. Such sets have value for
answering a new query only if they are \emph{trusted}. In the absence of
any system-wide security mechanism, a data set is trusted by a node $a$
only if it was generated by some node trusted by $a$.
Our main contributions are a formal definition of the problem, and an
efficient scheme that solves this problem by allowing untrusted peers to
perform set operations on trusted data sets, and to produce unforgeable
proofs of correctness. This is accomplished by requiring trusted nodes to
sign appropriately-defined \emph{digests} of generated sets; each such digest consists of an RSA accumulator and a Bloom filter. The scheme is
general, and can be applied to other applications as well. We give an
analysis that demonstrates the low overhead of the scheme and we include
experimental data which confirm the analysis.
(UMIACS-TR-2003-68)