Počet záznamů: 1  

The hardness of being private

  1. 1.
    SYSNO ASEP0386317
    Druh ASEPC - Konferenční příspěvek (mezinárodní konf.)
    Zařazení RIVD - Článek ve sborníku
    NázevThe 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 strans. 192-202
    Poč.str.11 s.
    Forma vydáníTištěná - P
    AkceComputational 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 akceWRD
    Jazyk dok.eng - angličtina
    Země vyd.US - Spojené státy americké
    Klíč. slovaprivacy ; communication complexity ; Vickrey auctions
    Vědní obor RIVBA - Obecná matematika
    CEPGAP202/10/0854 GA ČR - Grantová agentura ČR
    1M0545 GA MŠk - Ministerstvo školství, mládeže a tělovýchovy
    IAA100190902 GA AV ČR - Akademie věd
    Institucionální podporaMU-W - RVO:67985840
    UT WOS000308976600020
    EID SCOPUS84866510748
    DOI10.1109/CCC.2012.24
    AnotaceIn 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
    KontaktJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Rok sběru2013
Počet záznamů: 1