Fast Private Set Operations with SEPIA

Abstract

Private set operations allow correlation of sensitive data from multiple data owners. Although intensely researched, current solutions still exhibit limited scalability in terms of the supported maximum set size and number of sets. To address these issues, we propose a new approach to private set operations based on a combination of efficient secure multiparty computation and bloom filters, a space-efficient probabilistic data structure for set representation. We design, implement and evaluate protocols for counting and non-counting set intersection, set union, threshold set union, weighted set intersection, and set cardinality estimation. Evaluation in realistic settings shows that our protocols are between twenty times and several orders of magnitudes faster than the state-of-the-art.