Approximate privacy: foundations and quantification

Full textClick to download.
CitationEC 2010
AuthorsJoan Feigenbaum
Aaron D. Jaggard
Michael Schapira


Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of online sensitive data about individuals and organizations. Consequently, concern about the privacy of these data has become a top priority, particularly those data that are created and used in electronic commerce. Despite many careful formulations and extensive study, there are still open questions about the feasibility of maintaining meaningful privacy 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 many well studied contexts: the 2nd-price Vickrey auction, the millionaires problem of Yao, the provisioning of a public good, and also set disjointness and set intersection. We present both positive and negative results and many interesting directions for future research.

Back to publications
Back to previous page