Paper 2019/281

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

Phillipp Schoppmann, Adria Gascon, Mariana Raykova, and Benny Pinkas


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM Conference on Computer and Communications Security (CCS '19)
secure computationmachine learningsparsity
Contact author(s)
schoppmann @ informatik hu-berlin de
agascon @ turing ac uk
mpr2111 @ columbia edu
benny @ pinkas net
2019-12-13: revised
2019-03-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Phillipp Schoppmann and Adria Gascon and Mariana Raykova and Benny Pinkas},
      title = {Make Some ROOM for the Zeros: Data Sparsity in Secure Distributed Machine Learning},
      howpublished = {Cryptology ePrint Archive, Paper 2019/281},
      year = {2019},
      doi = {10.1145/3319535.3339816},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.