Paper 2010/076
Private and Continual Release of Statistics
T-H. Hubert Chan, Elaine Shi, and 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.
Note: Minor edits.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. ICALP 2010, full version to appear in TISSEC
- Keywords
- differential privacycontinual
- Contact author(s)
- runting @ cs cmu edu
- History
- 2011-12-14: last of 5 revisions
- 2010-02-16: received
- See all versions
- Short URL
- https://ia.cr/2010/076
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2010/076,
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},
url = {https://eprint.iacr.org/2010/076}
}
