Privacy preserving information sharing
Johannes E. Gehrke, Alexandre Evfimievski · 2004
Modern business creates an increasing need for sharing, querying and mining information across autonomous enterprises while maintaining privacy of their own data records. The capability of preserving privacy in query processing algorithms can be demonstrated in two ways: through statistics and through cryptography. Statistical approach evaluates disclosure by its effect on an adversary's probability assumptions regarding privacy-sensitive data properties, while cryptographic approach gives comparative lower bounds on the computational complexity of learning these properties. This dissertation presents results in both approaches. First, it considers the setup with one central server and a large number of clients connected only to the server, each client having a private data record. The server wants to generate an aggregate model of clients' data, and the clients want to limit disclosure of their individual records. Before sending to the server, each client hides its record using randomization, i.e. replaces the record with another one drawn from a certain distribution that depends on the original record. Disclosure is limited statistically by providing guarantees against “privacy breaches”: situations when the randomized record significantly alters the server's probability for answer “yes” to some sensitive question about the original record. Privacy preserving mining of association rules is used as a concrete application for the method, with private records being small sets of items. More generally, a novel upper bound on privacy breaches is given, which at once covers all questions about an individual client's record, and which works regardless of the client's data distribution. The bound is easy to use with many different types of randomization. Second, the dissertation proposes a paradigm of minimal information sharing across several private databases, and instantiates it by developing cryptographic protocols for intersection, equijoin, intersection size, and equijoin size queries over two tables owned by two enterprises. Given a database query spanning multiple private databases, the paradigm suggests to compute the answer to the query while revealing minimal additional information apart from the query result. The protocols for intersection and equijoin are constructed using commutative encryption as well as Boolean circuits, and compared. The use of protocols is illustrated by applications.