Paper 2018/801

Faster PCA and Linear Regression through Hypercubes in HElib

Deevashwer Rathee, Pradeep Kumar Mishra, and Masaya Yasuda

Abstract

The significant advancements in the field of homomorphic encryption have led to a grown interest in securely outsourcing data and computation for privacy critical applications. In this paper, we focus on the problem of performing secure predictive analysis, such as principal component analysis (PCA) and linear regression, through exact arithmetic over encrypted data. We improve the plaintext structure of Lu et al.'s protocols (from NDSS 2017), by switching over from linear array arrangement to a two-dimensional hypercube. This enables us to utilize the SIMD (Single Instruction Multiple Data) operations to a larger extent, which results in improving the space and time complexity by a factor of matrix dimension. We implement both Lu et al.'s method and ours for PCA and linear regression over HElib, a software library that implements the Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption scheme. In particular, we show how to choose optimal parameters of the BGV scheme for both methods. For example, our experiments show that our method takes 45 seconds to train a linear regression model over a dataset with 32k records and 6 numerical attributes, while Lu et al.'s method takes 206 seconds.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Workshop on Privacy in the Electronic Society (WPES) at CCS 2018
DOI
10.1145/3267323.3268952
Keywords
Leveled homomorphic encryptionPCALinear RegressionHypercube arrangement
Contact author(s)
deevashwer student cse15 @ iitbhu ac in
History
2018-09-02: received
Short URL
https://ia.cr/2018/801
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/801,
      author = {Deevashwer Rathee and Pradeep Kumar Mishra and Masaya Yasuda},
      title = {Faster PCA and Linear Regression through Hypercubes in HElib},
      howpublished = {Cryptology ePrint Archive, Paper 2018/801},
      year = {2018},
      doi = {10.1145/3267323.3268952},
      note = {\url{https://eprint.iacr.org/2018/801}},
      url = {https://eprint.iacr.org/2018/801}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.