Pan-private algorithms via statistics on sketches

Darakhshan Mir, S. Muthukrishnan, Aleksandar Nikolov, Rebecca N. Wright

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Consider fully dynamic data, where we track data as it gets inserted and deleted. There are well developed notions of private data analyses with dynamic data, for example, using differential privacy. We want to go beyond privacy, and consider privacy together with security, formulated recently as pan-privacy by Dwork et al. (ICS 2010). Informally, pan-privacy preserves differential privacy while computing desired statistics on the data, even if the internal memory of the algorithm is compromised (say, by a malicious breakin or insider curiosity or by flat by the government or law). We study pan-private algorithms for basic analyses, like estimating distinct count, moments, and heavy hitter count, with fully dynamic data. We present the first known panprivate algorithms for these problems in the fully dynamic model. Our algorithms rely on sketching techniques popular in streaming: in some cases, we add suitable noise to a previously known sketch, using a novel approach of calibrating noise to the underlying problem structure and the projection matrix of the sketch; in other cases, we maintain certain statistics on sketches; in yet others, we define novel sketches. We also present the first known lower bounds explicitly for pan privacy, showing our results to be nearly optimal for these problems. Our lower bounds are stronger than those implied by differential privacy or dynamic data streaming alone and hold even if unbounded memory and/or unbounded processing time are allowed. The lower bounds use a noisy decoding argument and exploit a connection between pan-private algorithms and data sanitization.

    Original languageEnglish (US)
    Title of host publicationPODS'11 - Proceedings of the 30th Symposium on Principles of Database Systems
    Pages37-48
    Number of pages12
    DOIs
    StatePublished - 2011
    Event30th Symposium on Principles of Database Systems, PODS'11 - Athens, Greece
    Duration: May 13 2011May 15 2011

    Publication series

    NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

    Conference

    Conference30th Symposium on Principles of Database Systems, PODS'11
    Country/TerritoryGreece
    CityAthens
    Period5/13/115/15/11

    Keywords

    • Differential privacy
    • Pan-privacy

    ASJC Scopus subject areas

    • Software
    • Information Systems
    • Hardware and Architecture

    Fingerprint

    Dive into the research topics of 'Pan-private algorithms via statistics on sketches'. Together they form a unique fingerprint.

    Cite this