TY - JOUR
T1 - Implementation and performance evaluation of RNS variants of the BFV homomorphic encryption scheme
AU - Al Badawi, Ahmad
AU - Polyakov, Yuriy
AU - Aung, Khin Mi Mi
AU - Veeravalli, Bharadwaj
AU - Rohloff, Kurt
N1 - Funding Information:
This work was supported by A * STAR Institute for Info-comm Research (I2R) and the National University of Singapore. Polyakov and Rohloff’s work was supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA). The views expressed are those of the authors and do not necessarily reflect the official policy or position of the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
Publisher Copyright:
© 2013 IEEE.
PY - 2021/4/1
Y1 - 2021/4/1
N2 - 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.
AB - 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.
KW - BFV SHE
KW - Secure computation
KW - homomorphic encryption
KW - lattice-based cryptography
KW - parallel processing
KW - residue number system
UR - http://www.scopus.com/inward/record.url?scp=85107516558&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85107516558&partnerID=8YFLogxK
U2 - 10.1109/TETC.2019.2902799
DO - 10.1109/TETC.2019.2902799
M3 - Article
AN - SCOPUS:85107516558
SN - 2168-6750
VL - 9
SP - 941
EP - 956
JO - IEEE Transactions on Emerging Topics in Computing
JF - IEEE Transactions on Emerging Topics in Computing
IS - 2
M1 - 8657794
ER -