0386317 - MÚ 2013 RIV US eng C - Conference Paper (international conference)
Ada, A. - Chattopadhyay, A. - Cook, S.A. - Fontes, L. - Koucký, Michal - Pitassi, T.
The hardness of being private.
2012 IEEE 27th Annual Conference on Computational Complexity (CCC). New York: IEEE, 2012, s. 192-202. Annual IEEE Conference on Computational Complexity. ISBN 978-0-7695-4708-4. ISSN 1093-0159.
[Computational Complexity (CCC), 2012 IEEE 27th Annual Conference. Porto (PT), 26.06.2012-29.6.2012]
R&D Projects: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institutional support: RVO:67985840
Keywords : privacy * communication complexity * Vickrey auctions
Subject RIV: BA - General Mathematics
Result website:
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6243395DOI: https://doi.org/10.1109/CCC.2012.24

In 1989 Kushilevitz 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. The unattainability of perfect privacy for many functions motivated the study of approximate privacy. In Feigenbaum et al. (2010), they define notions of worst-case as well as average-case approximate privacy, and present several interesting upper bounds, and some open problems for further study. In this paper, we obtain asymptotically tight bounds on the tradeoffs 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.
Permanent Link: http://hdl.handle.net/11104/0215655