Cryptology ePrint Archive: Report 2010/076
Private and Continual Release of Statistics
T-H. Hubert Chan, Elaine Shi, Dawn Song
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.
Category / Keywords: differential privacy, continual
Publication Info: ICALP 2010, full version to appear in TISSEC
Date: received 11 Feb 2010, last revised 13 Dec 2011
Contact author: runting at cs cmu edu
Available format(s): PDF | BibTeX Citation
Note: Minor edits.
Version: 20111214:051623 (All versions of this report)
Short URL: ia.cr/2010/076
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]