Privacy-Preserving Set Operations

By Lea Kissner, Dawn Song. 2005

845 citations recorded by the source corpus.

In many important applications, a collection of mutually distrustful parties must perform private computation over multisets. Each party's input to the function is his private input multiset. In order to protect these private sets, the players perform privacy-preserving computation; that is, no party learns more information about other parties' private input sets than what can be deduced from the result. In this paper, we propose efficient techniques for privacy-preserving operations on multisets. By building a framework of multiset operations, employing the mathematical properties of polynomials, we design efficient, secure, and composable methods to enable privacy-preserving computation of the union, intersection, and element reduction operations. We apply these techniques to a wide range of practical problems, achieving more efficient results than those of previous work.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Secure Federated Submodel Learning (2019, neutral): “In the cryptography field, according to the representation format of a set, the protocols can be generally divided into two categories: polynomial based [87]–[91] and Bloom filter based [92]–[94].”
Federated Tensor Factorization for Computational Phenotyping (2017, background): “We assume Honest-but-Curious adversary model, in which the server and hospitals are curious on data of others but do not maliciously manipulate intermediate results [18].”
Secure Multiparty Computation for Privacy-Preserving Data Mining (2009, background): “This problem was investigated in (17) and is denoted as the set intersection problem or as the private matching problem (the multiparty case was investigated in (30)).”
Efficient and Quasi-accurate Multiparty Private Set Union (2018, methodology): “The amount of broadcast communication in [1] is reduced in [6].”
Fast and Private Computation of Cardinality of Set Intersection and Union (2012, background): “Whereas, [29] extends OPE-s to more than two players, all learning the intersection/union, with quadratic computational and linear communication complexities.”
Collaborative, Privacy-Preserving Data Aggregation at Scale (2010, background): “Kissner and Song [20] extended and further improved this polynomial-based protocol for a multi-party decentralized setting, yet their computational complexity remains O ( nℓ 2 ) and communication complexity is O ( n 2 ℓ ) , where n is the number of participants and ℓ is the number of input elements ”
Practical Private Set Intersection Protocols with Linear Complexity (2010, methodology): “Subsequently, the work by Kissner and Song (KS) [20] has proposed OPE-based protocols that apply to several set operations (e.”
L G ] 1 1 A pr 2 01 7 Federated Tensor Factorization for Computational Phenotyping (2018, background): “Hospitals use polynomial properties of set intersection [18]:”
Distributed Measurement with Private Set-Union Cardinality (2017, background): “Several protocols to securely compute set-union cardinality (or the related problem of set-intersection cardinality) have been proposed [12, 18, 32, 48].”
DJoin: Differentially Private Join Queries over Distributed Databases (2012, positive): “Since then, a number of improvements have been proposed; for instance , Kissner and Song [17] extended the protocols to multiple parties, and Vaidya and Clifton [37] reduced the computational overhead.”
Privacy-Preserving Set Union (2007, methodology): “Recently there has been a signiﬁcant amount of work on privacy-preserving set operations, including: set intersection [14,6,21,9], testing set disjointness [17], multi-set operations [18], and set union [16,1,18].”
Secure Multiparty Computation (2011, neutral): “This has been useful for set operations (which are described in detail in the next section), including [12,13,20].”
Faster Private Set Intersection Based on OT Extension (2014, methodology): “A protocol that uses polynomial interpolation and differentiation for finding intersections between multi-sets was presented in [37].”
Constant-Round Privacy Preserving Multiset Union (2013, methodology): “PPMU is firstly addressed by Kissner and Song (KS) in [16].”
Computational Differential Privacy (2009, background): “The problem of secure Hamming distance computation, together with closely related problems of secure scalar product and secure set-intersection cardinality [14,15,16,17,18], may”