Paper 2010/076

Private and Continual Release of Statistics

T-H. Hubert Chan, Elaine Shi, and Dawn Song


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.

Note: Minor edits.

Available format(s)
Publication info
Published elsewhere. ICALP 2010, full version to appear in TISSEC
differential privacycontinual
Contact author(s)
runting @ cs cmu edu
2011-12-14: last of 5 revisions
2010-02-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {T-H.  Hubert Chan and Elaine Shi and Dawn Song},
      title = {Private and Continual Release of Statistics},
      howpublished = {Cryptology ePrint Archive, Paper 2010/076},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.