International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Private and Continual Release of Statistics

T-H. Hubert Chan
Elaine Shi
Dawn Song
Search ePrint
Search Google
Abstract: We ask the question – how can websites and data aggregators continually release updated statistics, and meanwhile preserve each individual user’s privacy? Suppose we are given a stream of 0’s and 1’s. We propose a differentially private continual counter that outputs at every time step the approximate number of 1’s seen thus far. Our counter construction has error that is only poly-log in the number of time steps. We can extend the basic counter construction to allow websites to continually give top-k and hot items suggestions while preserving users’ privacy.
  title={Private and Continual Release of Statistics},
  booktitle={IACR Eprint archive},
  keywords={differential privacy, continual, streaming algorithm},
  note={ICALP 2010 14757 received 11 Feb 2010, last revised 28 May 2010},
  author={T-H. Hubert Chan and Elaine Shi and Dawn Song},