Approximate Privacy
Abstract
The proliferation of online sensitive data about individuals and organizations makes concern about the privacy of these data a top priority. There have been many formulations of privacy and, unfortunately, many negative results about the feasibility of maintaining privacy of sensitive data in realistic networked environments. We formulate communication-complexity-based definitions, both worst case and average case, of a problem’s privacy-approximation ratio . We use our definitions to investigate the extent to which approximate privacy is achievable in a number of standard problems: the 2 nd -price Vickrey auction, Yao’s millionaires problem, the public-good problem, and the set-theoretic disjointness and intersection problems.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 01, 2014
- Source ID
- 10.1145/2601067
Entities
People
- Aaron D. Jaggard
- Joan Feigenbaum
- Michael Schapira
Organizations
- Intelligence Advanced Research Projects Activity
- National Science Foundation
- Rutgers University
- Yale University