Using Homomorphic Encryption for Large Scale Statistical Analysis

David J. Wu and Jacob Haven



The development of fully homomorphic encryption schemes in recent years has generated considerable interest in the field of secure computing. In this paper, we consider the problem of performing statistical analysis on encrypted data. Specifically, we focus on two tasks: computing the mean and variance of univariate and multivariate data as well as performing linear regression on a multidimensional, encrypted corpus. Due to the high overhead of homomorphic computation, previous implementations of similar methods have been restricted to small datasets (on the order of a few hundred to a thousand elements) or data with low dimension (generally 1-4). In this paper, we first construct a working implementation of the scale-invariant leveled homomorphic encryption system in [Bra12]. Then, by taking advantage of batched computation as well as a message encoding technique based on the Chinese Remainder Theorem, we show that it becomes not only possible, but computationally feasible, to perform statistical analysis on encrypted datasets with over four million elements and dimension as high as 24. By using these methods along with some additional optimizations, we demonstrate the viability of using leveled homomorphic encryption for large scale statistical analysis.

  author = {David J. Wu and Jacob Haven},
  title  = {Using Homomorphic Encryption for Large Scale Statistical Analysis},
  year   = {2012}