Improved Counting under Continual Observation with Pure Differential Privacy

Counting under continual observation is a well-studied problem in the area of differential privacy. Given a stream of updates $x_1,x_2,\dots,x_T \in \{0,1\}$ the problem is to continuously release estimates of the prefix sums $\sum_{i=1}^t x_i$ for $t=1,\dots,T$ while protecting each input $x_i$ in the stream with differential privacy. Recently, significant leaps have been made in our understanding of this problem under $\textit{approximate}$ differential privacy, aka. $(\varepsilon,\delta)$$\textit{-differential privacy}$. However, for the classical case of $\varepsilon$-differential privacy, we are not aware of any improvement in mean squared error since the work of Honaker (TPDP 2015). In this paper we present such an improvement, reducing the mean squared error by a factor of about 4, asymptotically. The key technique is a new generalization of the binary tree mechanism that uses a $k$-ary number system with $\textit{negative digits}$ to improve the privacy-accuracy trade-off. Our mechanism improves the mean squared error over all 'optimal' $(\varepsilon,\delta)$-differentially private factorization mechanisms based on Gaussian noise whenever $\delta$ is sufficiently small. Specifically, using $k=19$ we get an asymptotic improvement over the bound given in the work by Henzinger, Upadhyay and Upadhyay (SODA 2023) when $\delta = O(T^{-0.92})$.