Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime. (arXiv:2207.00420v1 [cs.CR])

Most differential privacy mechanisms are applied (i.e., composed) numerous
times on sensitive data. We study the design of optimal differential privacy
mechanisms in the limit of a large number of compositions. As a consequence of
the law of large numbers, in this regime the best privacy mechanism is the one
that minimizes the Kullback-Leibler divergence between the conditional output
distributions of the mechanism given two different inputs. We formulate an
optimization problem to minimize this divergence subject to a cost …

differential privacy large privacy