The hardness of being private

0386317 - MÚ 2013 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
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]
Grant CEP: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institucionální podpora: RVO:67985840
Klíčová slova: privacy * communication complexity * Vickrey auctions
Kód oboru RIV: BA - Obecná matematika
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6243395

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.
Trvalý link: http://hdl.handle.net/11104/0215655