Cryptology ePrint Archive: Report 2019/281

Make Some ROOM for the Zeros: Data Sparsity in Secure Distributed Machine Learning

Phillipp Schoppmann and Adria Gascon and Mariana Raykova and Benny Pinkas

Abstract: Exploiting data sparsity is crucial for the scalability of many data analysis tasks. However, while there is an increasing interest in efficient secure computation protocols for distributed machine learning, data sparsity has so far not been considered in a principled way in that setting.

We propose sparse data structures together with their corresponding secure computation protocols to address common data analysis tasks while utilizing data sparsity. In particular, we define a Read-Only Oblivious Map primitive (ROOM) for accessing elements in sparse structures, and present several instantiations of this primitive with different trade-offs. Then, using ROOM as a building block, we propose protocols for basic linear algebra operations such as Gather, Scatter, and multiple variants of sparse matrix multiplication. Our protocols are easily composable by using secret sharing. We leverage this, at the highest level of abstraction, to build secure end-to-end protocols for non-parametric models ($k$-nearest neighbors and naive Bayes classification) and parametric models (logistic regression) that enable secure analysis on high-dimensional datasets. The experimental evaluation of our protocol implementations demonstrates a manyfold improvement in the efficiency over state-of-the-art techniques across all applications.

Our system is designed and built mirroring the modular architecture in scientific computing and machine learning frameworks, and inspired by the Sparse BLAS standard.

Category / Keywords: cryptographic protocols / secure computation, machine learning, sparsity

Original Publication (in the same form): ACM Conference on Computer and Communications Security (CCS '19)

Date: received 12 Mar 2019, last revised 13 Dec 2019

Contact author: schoppmann at informatik hu-berlin de, agascon at turing ac uk, mpr2111 at columbia edu, benny at pinkas net

Available format(s): PDF | BibTeX Citation

Version: 20191213:134701 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]