The Hardness of Being Private

Kushilevitz [1989] initiated the study of information-theoretic privacy within the context of communication complexity. Unfortunately, it has been shown that most interesting functions are not privately computable [Kushilevitz 1989, Brandt and Sandholm 2008]. The unattainability of perfect privacy f...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on computation theory 2014-03, Vol.6 (1), p.1-24
Main Authors: Ada, Anil, Chattopadhyay, Arkadev, Cook, Stephen A., Fontes, Lila, Koucký, Michal, Pitassi, Toniann
Format: Article
Language:English
Subjects:
Approximation
Asymptotic properties
Hardness
Mathematical analysis
Mathematical models
Privacy
Tradeoffs
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Kushilevitz [1989] initiated the study of information-theoretic privacy within the context of communication complexity. Unfortunately, it has been shown that most interesting functions are not privately computable [Kushilevitz 1989, Brandt and Sandholm 2008]. The unattainability of perfect privacy for many functions motivated the study of approximate privacy . Feigenbaum et al. [2010a, 2010b] define notions of worst-case as well as average-case approximate privacy and present several interesting upper bounds as well as some open problems for further study. In this article, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey auctions. Further, we relate the notion of average-case approximate privacy to other measures based on information cost of protocols. This enables us to prove exponential lower bounds on the subjective approximate privacy of protocols for computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al. [2010a].
ISSN:1942-3454
1942-3462
DOI:10.1145/2567671