This paper presents the first practical construction for privacy-preserving
evaluation of sample set similarity, based on the well-known Jaccard index
measure. In this problem, two mutually distrustful entities determine how
similar their sets are, without disclosing their content to each other. We
propose two efficient protocols: the first securely computes the Jaccard index
of two sets; the second approximates it using MinHash techniques, at a
significantly lower cost and with same privacy guarantees.