Lea Kissner

Privacy-Preserving Distributed Information Sharing Degree Type: Ph.D. in Computer Science
Advisor(s): Dawn Song
Graduated: December 2006

Abstract:

In many important applications, a collection of mutually distrustful parties must share information, without compromising their privacy. Currently, these applications are often performed by using some form of a trusted third party (TTP); this TTP receives all players¡Ç inputs, computes the desired function, and returns the result. However, the level of trust that must be placed in such a TTP is often inadvisable, undesirable, or even illegal. In order to make many applications practical and secure, we must remove the TTP, replacing it with efficient protocols for privacy-preserving distributed information sharing. Thus, in this thesis we explore techniques for privacy-preserving distributed information sharing that are efficient, secure, and applicable to many situations.

As an example of privacy-preserving information sharing, 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, including the Set-Intersection, Over-Threshold Set-Union, Cardinality Set-Intersection, and Threshold Set-Union problems. Additionally, we address the problem of determining Subset relations, and even use our techniques to evaluate CNF boolean formulae.

We then examine the problem of hot item identification and publication, a problem closely related to Over-Threshold Set-Union. Many applications of this problem require greater efficiency and robustness than any previously-designed secure protocols for this problem. In order to achieve sufficiently efficient protocols for these problems, we define two new privacy properties: owner privacy and data privacy. Protocols that achieve these properties protect the privacy of each player's personal input set, as well as protecting information about the players¡Ç collective inputs. By designing our protocols to achieve owner and data privacy, we are able to significantly increase efficiency over our privacy-preserving set operations, while still protecting the privacy of participants. In addition, our protocols are extremely flexible - nodes can join and leave at any time.

Thesis Committee:
Dawn Song (Chair)
Manuel Blum
Michael Reiter
Dan Boneh (Stanford University)
Benny Pinkas (Haifa University)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Privacy, distributed information sharing, multiset operations, hot-item identification