Implementation and Performance Evaluation of RNS Variants of the BFV Homomorphic Encryption Scheme

By A. Al Badawi, Yuriy Polyakov, Khin Mi Mi Aung, Bharadwaj Veeravalli, Kurt Rohloff. 2019

132 citations recorded by the source corpus.

Homomorphic encryption is an emerging form of encryption that provides the ability to compute on encrypted data without ever decrypting them. Potential applications include aggregating sensitive encrypted data on a cloud environment and computing on the data in the cloud without compromising data privacy. There have been several recent advances resulting in new homomorphic encryption schemes and optimized variants. We implement and evaluate the performance of two optimized variants, namely Bajard-Eynard-Hasan-Zucca (BEHZ) and Halevi-Polyakov-Shoup (HPS), of the most promising homomorphic encryption scheme in CPU and GPU. The most interesting (and also unexpected) result of our performance evaluation is that the HPS variant in practice scales significantly better (typically by 15-30 percent) with increase in multiplicative depth of the computation circuit than BEHZ, implying that the HPS variant will always outperform BEHZ for most practical applications. For the multiplicative depth of 98, our fastest GPU implementation performs homomorphic multiplication in 51 ms for 128-bit security settings, which is faster by two orders of magnitude than prior results and already practical for cloud environments supporting GPU computations. Large multiplicative depths supported by our implementations are required for applications involving deep neural networks, logistic regression learning, and other important machine learning problems.

Subfields: Artificial Intelligence, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

HEAX: An Architecture for Computing on Encrypted Data (2019, methodology): “We evaluate our design on a wide range of FHE parameters: from ciphertext polynomial size ( n ) of 2 12 and 109-bit ciphertext modulus ( ⌊ log qp ⌋ + 1) to 2 14 with 438-bit ciphertext modulus.”
FPGA-Based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data (2019, methodology): “A very recent implementation [33] by Badawi et al. presents performances of the FV scheme for various parameter sets on CPUs and GPUs.”
HEAX: High-Performance Architecture for Computation on Homomorphically Encrypted Data in the Cloud (2019, methodology): “In [5], a comprehensive study is reported for multithreaded CPU execution as well as GPU implementation of the BFV scheme.”