Differentially Private Sketches for Jaccard Similarity Estimation
  This paper describes two locally-differential private algorithms for
releasing user vectors such that the Jaccard similarity between these vectors
can be efficiently estimated. The basic building block is the well known
MinHash method. To achieve a privacy-utility trade-off, MinHash is extended in
two ways using variants of Generalized Randomized Response and the Laplace
Mechanism. A theoretical analysis provides bounds on the absolute error and
experiments show the utility-privacy trade-off on synthetic and real-world
data. The paper ends with a critical discussion of related work.
