Optimality of the Laplace Mechanism in Differential Privacy

Abstract

In the highly interconnected realm of Internet of Things, exchange of sensitive information raises severe privacy concerns. The Laplace mechanism -- adding Laplace-distributed artificial noise to sensitive data -- is one of the widely used methods of providing privacy guarantees within the framework of differential privacy. In this work, we present Lipschitz privacy, a slightly tighter version of differential privacy. We prove that the Laplace mechanism is optimal in the sense that it minimizes the mean-squared error for identity queries which provide privacy with respect to the ${\ell }_1$-norm. In addition to the ${\ell }_1$-norm which respects individuals' participation, we focus on the use of the ${\ell }_2$-norm which provides privacy of high-dimensional data. A variation of the Laplace mechanism is proven to have the optimal mean-squared error from the identity query. Finally, the optimal mechanism for the scenario in which individuals submit their high-dimensional sensitive data is derived.

References in corpus (2)

• Differentially Private Distributed Constrained Optimization
• The Optimal Mechanism in Differential Privacy

Cited by in corpus (8)

• Privacy-Preserving Obfuscation for Distributed Power Systems
• OptStream: Releasing Time Series Privately
• The Podium Mechanism: Improving on the Laplace and Staircase Mechanisms
• Splintering with distributions: A stochastic decoy scheme for private computation
• PPSM: A Privacy-Preserving Stackelberg Mechanism: Privacy Guarantees for the Coordination of Sequential Electricity and Gas Markets
• Bilevel Optimization for Differentially Private Optimization in Energy Systems
• Infinitely Divisible Noise in the Low Privacy Regime
• Asymmetric Differential Privacy