Paper 2022/225
Constant matters: Finegrained Complexity of Differentially Private Continual Observation Using Completely Bounded Norms
Monika Henzinger and Jalaj Upadhyay
Abstract
We study finegrained error bounds for differentially private algorithms for averaging and counting in the continual observation model. For this, we use the completely bounded spectral norm (cb norm) from operator algebra. For a matrix $W$, its cb norm is defined as \[ \{W}\_{\mathsf{cb}} = \max_{Q} \left\{ \frac{\{Q \bullet W}\}{\{Q}\} \right\}, \] where $Q \bullet W$ denotes the Schur product and $\{\cdot}\$ denotes the spectral norm. We bound the cb norm of two fundamental matrices studied in differential privacy under the continual observation model: the counting matrix $M_{\mathsf{counting}}$ and the averaging matrix $M_{\mathsf{average}}$. For $M_{\mathsf{counting}}$, we give lower and upper bound whose additive gap is $1 + \frac{1}{\pi}$. Our factorization also has two desirable properties sufficient for streaming setting: the factorization contains of lowertriangular matrices and the number of distinct entries in the factorization is exactly $T$. This allows us to compute the factorization on the fly while requiring the curator to store a $T$dimensional vector. For $M_{\mathsf{average}}$, we show an additive gap between the lower and upper bound of $\approx 0.64$.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Preprint.
 Keywords
 Differential privacycontinual observationconcrete bounds
 Contact author(s)
 jalaj kumar upadhyay @ gmail com
 History
 20220225: received
 Short URL
 https://ia.cr/2022/225
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/225, author = {Monika Henzinger and Jalaj Upadhyay}, title = {Constant matters: Finegrained Complexity of Differentially Private Continual Observation Using Completely Bounded Norms}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/225}, year = {2022}, url = {https://eprint.iacr.org/2022/225} }