Cryptology ePrint Archive: Report 2018/289

Private Nearest Neighbors Classification in Federated Databases

Phillipp Schoppmann and AdriÓ Gascˇn and Borja Balle

Abstract: Privacy-preserving data analysis in the context of federated databases distributed across multiple parties has the potential to produce richer and more accurate models than what each party can learn with their own data. Secure Multi-Party Computation (MPC) offers a robust cryptographic approach to this problem, and in fact several protocols have been proposed for various learning tasks on parametric models. In this paper we focus on $k$-NN, shifting the attention towards non-parametric models. We tackle several challenges arising in privacy-preserving $k$-NN classification on federated databases, and implement a concrete protocol for document classification. Our solution is faster than the state-of-the-art custom MPC protocol by at least one an order of magnitude.

Category / Keywords: cryptographic protocols / Multi-Party Computation, Text Classification, Machine Learning, Non-Parametric Models, k-Nearest-Neighbors

Date: received 23 Mar 2018

Contact author: schoppmann at informatik hu-berlin de

Available format(s): PDF | BibTeX Citation

Version: 20180328:023109 (All versions of this report)

Short URL: ia.cr/2018/289


[ Cryptology ePrint archive ]