  This paper proposes concentrated geo-privacy (CGP), a privacy notion that can
be considered as the counterpart of concentrated differential privacy (CDP) for
geometric data. Compared with the previous notion of geo-privacy [ABCP13,
CABP13], which is the counterpart of standard differential privacy, CGP offers
many benefits including simplicity of the mechanism, lower noise scale in high
dimensions, and better composability known as advanced composition. The last
one is the most important, as it allows us to design complex mechanisms using
smaller building blocks while achieving better utilities. To complement this
result, we show that the previous notion of geo-privacy inherently does not
admit advanced composition even using its approximate version. Next, we study
three problems on private geometric data: the identity query, k nearest
neighbors, and convex hulls. While the first problem has been previously
studied, we give the first mechanisms for the latter two under geo-privacy. For
all three problems, composability is essential in obtaining good utility
guarantees on the privatized query answer.
