  The goal of this paper is to propose and analyze a differentially private
randomized mechanism for the $K$-means query. The goal is to ensure that the
information received about the cluster-centroids is differentially private. The
method consists in adding Gaussian noise with an optimum covariance. The main
result of the paper is the analytical solution for the optimum covariance as a
function of the database. Comparisons with the state of the art prove the
efficacy of our approach.
