Privacy-preserving disjunctive normal form-operations on distributed sets

Abstract

Privacy-preserving set operations such as set union and set intersection on distributed sets are widely used in data mining in which the preservation of privacy is of the utmost concern. In this paper, we extended privacy-preserving set operations and considered privacy-preserving disjunctive normal form (DNF) operations on distributed sets. A privacy-preserving DNF operation on distributed sets can be used to find a set S-F satisfying S-F = (S-1,S-1 boolean AND ... boolean AND S-1,S-t2) boolean OR ... boolean OR (S-t1,S-1 boolean AND ... boolean AND S-t1,S-t2) without revealing any other information besides just the information which could be inferred from the DNF operations, where S-i,S-j is an element of {A(1), ..., An, (A(1)) over bar, ..., (A(n)) over bar} and set A(k) is known only to a party P-k. A complement set (A(k)) over bar is defined as (A(k)) over bar = (A(1) boolean OR ... boolean OR A(n)) - A(k). Using privacy-preserving DNF operations on distributed sets, it is possible to find set union, (threshold) set intersection, and a set of k-repeated elements. (C) 2011 Elsevier Inc. All rights reserved.