Paper 2011/464

Private and Oblivious Set and Multiset Operations

Marina Blanton and Everaldo Aguiar

Abstract

Privacy-preserving set operations, and set intersection in particular, are a popular research topic. Despite a large body of literature, the great majority of the available solutions are two-party protocols and are not composable. In this work we design a comprehensive suite of secure multi-party protocols for set and multiset operations that are composable, do not assume any knowledge of the sets by the parties carrying out the secure computation, and can be used for secure outsourcing. All of our protocols have communication and computation complexity of $O(m \log m)$ for sets or multisets of size $m$, which compares favorably with prior work. Furthermore, we are not aware of any results that realize composable operations. Our protocols are secure in the information theoretic sense and are designed to minimize the round complexity. Practicality of our solutions is shown through experimental results.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Full version of ASIACCS'12 paper.
Contact author(s)
mblanton @ nd edu
History
2014-04-21: last of 3 revisions
2011-08-29: received
See all versions
Short URL
https://ia.cr/2011/464
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/464,
      author = {Marina Blanton and Everaldo Aguiar},
      title = {Private and Oblivious Set and Multiset Operations},
      howpublished = {Cryptology ePrint Archive, Paper 2011/464},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/464}},
      url = {https://eprint.iacr.org/2011/464}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.