Geometric Noise for Locally Private Counting Queries

Lefki Kacem (1) , Catuscia Palamidessi (2)

1 Université Paris-Saclay
2 COMETE - Concurrency, Mobility and Transactions

Local differential privacy (LDP) is a variant of differential privacy (DP) where the noise is added directly on the individual records, before being collected. The main advantage with respect to DP is that we do not need a trusted third party to collect and sanitise the sensitive data of the user. The main disadvantage is that the trade-off between privacy and utility is usually worse than in DP, and typically to retrieve reasonably good statistics from the locally sanitised data it is necessary to have access to a huge collection of them. In this paper, we focus on the problem of estimating the counting queries on numerical data, and we propose a variant of LDP based on the addition of geometric noise. Such noise function is known to have appealing properties in the case of counting queries. In particular, it is universally optimal for DP, i.e., it provides the best utility for a given level of DP, regardless of the side knowledge of the attacker. We explore the properties of geometric noise for counting queries in the LDP setting, and we conjecture an optimality property, similar to the one that holds in the DP setting.

Mots clés: CCS CONCEPTS • Security and privacy → Formal security models; Information flow control; Information-theoretic techniques; Privacy-preserving protocols; Local differential privacy; counting queries; geometric noise

Domaines: Cryptographie et sécurité [cs.CR]; Théorie de l'information [cs.IT]

Lefki Kacem, Catuscia Palamidessi. Geometric Noise for Locally Private Counting Queries. Proceedings of the 13th Workshop on Programming Languages and Analysis for Security (PLAS 2018), 2018, Toronto, Canada. pp.13-16, ⟨10.1145/3264820.3264827⟩. ⟨hal-01966872⟩