The hardness of being private

0430344 - MÚ 2015 RIV US eng J - Journal Article
Ada, A. - Chattopadhyay, S. - Cook, S.A. - Fontes, L. - Koucký, Michal - Pitassi, T.
The hardness of being private.
ACM Transactions on Computation Theory. Roč. 6, č. 1 (2014), s. 1. ISSN 1942-3454
R&D Projects: GA ČR GAP202/10/0854; GA AV ČR IAA100190902
Institutional support: RVO:67985840
Keywords : approximate privacy * communication complexity * information theory
Subject RIV: BA - General Mathematics
http://dl.acm.org/citation.cfm?doid=2600088.2567671

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.
Permanent Link: http://hdl.handle.net/11104/0235297