Cryptology ePrint Archive: Report 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.
Category / Keywords: cryptographic protocols /
Publication Info: Full version of ASIACCS'12 paper.
Date: received 25 Aug 2011, last revised 29 Apr 2012
Contact author: mblanton at nd edu
Available formats: PDF | BibTeX Citation
Version: 20120430:020207 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]