Number of the records: 1  

The hardness of being private

    1.
    SYSNO ASEP0386317
    Document TypeC - Proceedings Paper (int. conf.)
    R&D Document TypeConference Paper
    TitleThe hardness of being private
    Author(s) Ada, A. (CA)
    Chattopadhyay, A. (CA)
    Cook, S.A. (CA)
    Fontes, L. (CA)
    Koucký, Michal (MU-W) RID, SAI, ORCID
    Pitassi, T. (CA)
    Source Title2012 IEEE 27th Annual Conference on Computational Complexity (CCC). - New York : IEEE, 2012 - ISSN 1093-0159 - ISBN 978-0-7695-4708-4
    Pagess. 192-202
    Number of pages11 s.
    Publication formPrint - P
    ActionComputational Complexity (CCC), 2012 IEEE 27th Annual Conference
    Event date26.06.2012-29.6.2012
    VEvent locationPorto
    CountryPT - Portugal
    Event typeWRD
    Languageeng - English
    CountryUS - United States
    Keywordsprivacy ; communication complexity ; Vickrey auctions
    Subject RIVBA - General Mathematics
    R&D ProjectsGAP202/10/0854 GA ČR - Czech Science Foundation (CSF)
    1M0545 GA MŠk - Ministry of Education, Youth and Sports (MEYS)
    IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
    Institutional supportMU-W - RVO:67985840
    UT WOS000308976600020
    EID SCOPUS84866510748
    DOI10.1109/CCC.2012.24
    AnnotationIn 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.
    WorkplaceMathematical Institute
    ContactJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Year of Publishing2013
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.

Accept allSettingsReject all