Cryptology ePrint Archive: Report 2016/108

Computing Private Set Operations with Linear Complexities

Alex Davidson and Carlos Cid

Abstract: Private set operation (PSO) protocols provide a natural way of securely performing operations on data sets, such that crucial details of the input sets are not revealed. Such protocols have an ever-increasing number of practical applications, particularly when implementing privacy-preserving data mining schemes. Protocols for computing private set operations have been prevalent in multi-party computation literature over the past decade, and in the case of private set intersection (PSI), have become practically feasible to run in real applications. In contrast, other set operations such as union have received less attention from the research community, and the few existing designs are often limited in their feasibility. In this work we aim to fill this gap, and present a new technique using Bloom filter data structures and additive homomorphic encryption to develop the first private set union (PSU) protocol with both linear computation and communication complexities. The overheads of our protocol scale better with increasing set sizes than existing PSU designs and we thus provide the first potentially practical realisation of the PSU functionality. Moreover, we show how to adapt this protocol to give novel ways of computing PSI and private set intersection/union cardinality (PSI/PSU-CA). The resulting schemes have complexities that are comparable to current solutions that are considered practical. We therefore present an adaptable way for efficiently computing the main set operations, with linear complexities, and with the possibility of extending to compute other more complex functionalities. Our constructions can be proven secure with respect to semi-honest and (in the case of input-privacy) malicious adversaries when considered in the authenticated set scenario.

Category / Keywords: Private set operations, Bloom filters, additively homomorphic encryption, secure computation, data mining.

Date: received 9 Feb 2016, last revised 10 Jun 2016

Contact author: alex davidson 2014 at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20160610:104152 (All versions of this report)

Short URL: ia.cr/2016/108

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]