Cryptology ePrint Archive: Report 2018/801

Faster PCA and Linear Regression through Hypercubes in HElib

Deevashwer Rathee and 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.

Category / Keywords: Leveled homomorphic encryption; PCA; Linear Regression; Hypercube arrangement

Original Publication (in the same form): Workshop on Privacy in the Electronic Society (WPES) at CCS 2018
DOI:
10.1145/3267323.3268952

Date: received 28 Aug 2018, last revised 2 Sep 2018

Contact author: deevashwer student cse15 at iitbhu ac in

Available format(s): PDF | BibTeX Citation

Version: 20180902:134631 (All versions of this report)

Short URL: ia.cr/2018/801


[ Cryptology ePrint archive ]