# Trust-Preserving Set Operations

 dc.contributor.author Morselli, Ruggero en_US dc.contributor.author Bhattacharjee, Bobby en_US dc.contributor.author Katz, Jonathan en_US dc.contributor.author Keleher, Pete en_US dc.date.accessioned 2004-05-31T23:29:56Z dc.date.available 2004-05-31T23:29:56Z dc.date.created 2003-07 en_US dc.date.issued 2003-09-25 en_US dc.identifier.uri http://hdl.handle.net/1903/1293 dc.description.abstract We describe a method of performing trust-preserving set operations by en_US 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) dc.format.extent 196654 bytes dc.format.mimetype application/pdf dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-4499 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-2003-68 en_US dc.title Trust-Preserving Set Operations en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt UMIACS Technical Reports en_US
﻿