Počet záznamů: 1
The hardness of being private
- 1.
SYSNO ASEP 0386317 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název The hardness of being private Tvůrce(i) Ada, A. (CA)
Chattopadhyay, A. (CA)
Cook, S.A. (CA)
Fontes, L. (CA)
Koucký, Michal (MU-W) RID, SAI, ORCID
Pitassi, T. (CA)Zdroj.dok. 2012 IEEE 27th Annual Conference on Computational Complexity (CCC). - New York : IEEE, 2012 - ISSN 1093-0159 - ISBN 978-0-7695-4708-4 Rozsah stran s. 192-202 Poč.str. 11 s. Forma vydání Tištěná - P Akce Computational Complexity (CCC), 2012 IEEE 27th Annual Conference Datum konání 26.06.2012-29.6.2012 Místo konání Porto Země PT - Portugalsko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova privacy ; communication complexity ; Vickrey auctions Vědní obor RIV BA - Obecná matematika CEP GAP202/10/0854 GA ČR - Grantová agentura ČR 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy IAA100190902 GA AV ČR - Akademie věd Institucionální podpora MU-W - RVO:67985840 UT WOS 000308976600020 EID SCOPUS 84866510748 DOI 10.1109/CCC.2012.24 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2013
Počet záznamů: 1