Paper 2018/589

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

Ahmad Al Badawi and Yuriy Polyakov and Khin Mi Mi Aung and Bharadwaj Veeravalli and Kurt Rohloff

Abstract

Homomorphic encryption 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 of existing schemes. Two efficient Residue-Number-System variants of the Brakerski-Fan-Vercauteren homomorphic encryption scheme were recently proposed: the Bajard-Eynard-Hasan-Zucca (BEHZ) variant based on integer arithmetic with auxiliary moduli, and the Halevi-Polyakov-Shoup (HPS) variant based on a combination of integer and floating-point arithmetic techniques. We implement and evaluate the performance of both variants in CPU (both single- and multi-threaded settings) 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%) with increase in multiplicative depth of the computation circuit than BEHZ. This implies that the runtime performance and supported circuit depth for HPS will always be better for most practical applications. The comparison of the homomorphic multiplication runtimes for CPU and GPU demonstrates that our best GPU performance results are 3x-33x faster than our best multi-threaded results for a modern server CPU environment. For the multiplicative depth of 98, our fastest GPU implementation performs decryption in 0.5 ms and homomorphic multiplication in 51 ms for 128-bit security settings, which is already practical for cloud environments supporting GPU computations. Our best runtime results are at least two orders of magnitude faster than all previously reported results for any variant of the Brakerski-Fan-Vercauteren scheme.