On Computing Pairwise Statistics with Local Differential Privacy

We study the problem of computing pairwise statistics, i.e., ones of the form binomn2-1 sumi ne j f(xi, xj), where xi denotes the input to the ith user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's τ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries.