DIMACS Discrete Math/Theory of Computing Seminar

Title: Revealing information while preserving privacy

Speaker: Kobbi Nissim, DIMACS and NEC Institute, Princeton

Date: Tuesday, November 19, 4:30 PM



Consider a hospital database, containing medical data of some large population. The hospital is interested in using this data for medical research. On the other hand, the hospital should keep the privacy of its patients by not leaking sensitive information related to specific patients.

This situation is different from what is customary in cryptography, where we usually state which information (functionality) should be revealed, and privacy is achieved if no other information is leaked. For database privacy we need to reverse the order, and state which information should not be leaked, with the goal of enabling as much functionality as possible.

We research the case of statistical databases (containing attributes), and propose a mathematical model for the problem. We show tight lower bounds, strongly limiting the amount of information that may be revealed without violating privacy.