Accurate, Private, Secure, Federated U-statistics with Higher Degree

We study the problem of computing a U-statistic with a kernel function $f$ of degree $k \geq 2$, i.e., the average of some function $f$ over all $k$-tuples of instances, in a federated learning setting. U-statistics of degree $2$ include several useful statistics such as Kendall's $\tau$ coefficient, the Area under the Receiver-Operator Curve and the Gini mean difference. Existing methods provide solutions only under the lower-utility local differential privacy model and/or scale poorly in the size of the domain discretization. In this work, we propose a protocol that securely computes U-statistics of degree $k \geq 2$ under central differential privacy by leveraging Multi Party Computation (MPC). Our method substantially improves accuracy when compared to prior solutions. We provide a detailed theoretical analysis of its accuracy, communication and computational properties. We evaluate its performance empirically, obtaining favorable results, e.g., for Kendall's $\tau$ coefficient, our approach reduces the Mean Squared Error by up to four orders of magnitude over existing baselines.

Collaborating on data analysis is essential for modern research, but if multiple data owners need to share their data this threatens privacy. In this paper, we consider the problem of computing averages over all k-sets of instances. Existing solutions either require a trusted central authority or degrade the accuracy of the output by injecting noise into the data. To address this, we developed a cryptographic protocol that enables data owners to collectively compute complex statistics without revealing their private information. This work provides guarantees of privacy alongside a massive gain in accuracy and a tractable computation and communication cost. This allows organizations to securely unlock insights from sensitive information without sacrificing their privacy or output quality.