Paper 2022/225

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation Using Completely Bounded Norms

Monika Henzinger and Jalaj Upadhyay

Abstract

We study fine-grained 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 lower-triangular 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)
PDF
Category
Applications
Publication info
Preprint.
Keywords
Differential privacycontinual observationconcrete bounds
Contact author(s)
jalaj kumar upadhyay @ gmail com
History
2022-02-25: received
Short URL
https://ia.cr/2022/225
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/225,
      author = {Monika Henzinger and Jalaj Upadhyay},
      title = {Constant matters:  Fine-grained Complexity of Differentially Private Continual Observation Using Completely Bounded Norms},
      howpublished = {Cryptology ePrint Archive, Paper 2022/225},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/225}},
      url = {https://eprint.iacr.org/2022/225}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.