TY - GEN
T1 - Revisiting Homomorphic Encryption Schemes for Finite Fields
AU - Kim, Andrey
AU - Polyakov, Yuriy
AU - Zucca, Vincent
N1 - Funding Information:
Andrey Kim and Yuriy Polyakov’s NJIT work was supported in part by the Defense Advanced Research Projects Agency (DARPA) and the US Navy SPAWAR Systems Center Pacific (SSCPAC) under Contract Number N66001-17-1-4043 and the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via Contract No. 2019-1902070006. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the Department of Defense, ODNI, IARPA, or the U.S. Government. Vincent Zucca’s KU Leuven work was supported in part by the Research Council KU Leuven grant C14/18/067, CyberSecurity Research Flanders with reference number VR20192203, and the IARPA HECTOR project under the solicitation number IARPA-BAA-17-05. We also thank Charlotte Bonte for a careful review of the first version of the paper, her feedback, and fruitful discussions that helped us to improve the paper.
Funding Information:
Acknowledgments. Andrey Kim and Yuriy Polyakov’s NJIT work was supported in part by the Defense Advanced Research Projects Agency (DARPA) and the US Navy SPAWAR Systems Center Pacific (SSCPAC) under Contract Number N66001-17-1-4043 and the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via Contract No. 2019-1902070006. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the Department of Defense, ODNI, IARPA, or the U.S. Government. Vincent Zucca’s KU Leuven work was supported in part by the Research Council KU Leuven grant C14/18/067, CyberSecurity Research Flanders with reference number VR20192203, and the IARPA HECTOR project under the solicitation number IARPA-BAA-17-05. We also thank Charlotte Bonte for a careful review of the first version of the paper, her feedback, and fruitful discussions that helped us to improve the paper.
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/ Fan-Vercauteren (BFV) schemes are the two main homomorphic encryption (HE) schemes to perform exact computations over finite fields and integers. Although the schemes work with the same plaintext space, there are significant differences in their noise management, algorithms for the core homomorphic multiplication operation, message encoding, and practical usability. The main goal of our work is to revisit both schemes, focusing on closing the gap between the schemes by improving their noise growth, computational complexity of the core algorithms, and usability. The other goal of our work is to provide both theoretical and experimental performance comparison of BGV and BFV. More precisely, we propose an improved variant of BFV where the encryption operation is modified to significantly reduce the noise growth, which makes the BFV noise growth somewhat better than for BGV (in contrast to prior results showing that BGV has smaller noise growth for larger plaintext moduli). We also modify the homomorphic multiplication procedure, which is the main bottleneck in BFV, to reduce its algorithmic complexity. Our work introduces several other novel optimizations, including lazy scaling in BFV homomorphic multiplication and an improved BFV decryption procedure in the Residue Number System (RNS) representation. We also develop a usable variant of BGV as a more efficient alternative to BFV for common practical scenarios. We implement our improved variants of BFV and BGV in PALISADE and evaluate their experimental performance for several benchmark computations. The experimental results suggest that our BGV implementation is faster for intermediate and large plaintext moduli, which are often used in practical scenarios with ciphertext packing, while our BFV implementation is faster for small plaintext moduli.
AB - The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/ Fan-Vercauteren (BFV) schemes are the two main homomorphic encryption (HE) schemes to perform exact computations over finite fields and integers. Although the schemes work with the same plaintext space, there are significant differences in their noise management, algorithms for the core homomorphic multiplication operation, message encoding, and practical usability. The main goal of our work is to revisit both schemes, focusing on closing the gap between the schemes by improving their noise growth, computational complexity of the core algorithms, and usability. The other goal of our work is to provide both theoretical and experimental performance comparison of BGV and BFV. More precisely, we propose an improved variant of BFV where the encryption operation is modified to significantly reduce the noise growth, which makes the BFV noise growth somewhat better than for BGV (in contrast to prior results showing that BGV has smaller noise growth for larger plaintext moduli). We also modify the homomorphic multiplication procedure, which is the main bottleneck in BFV, to reduce its algorithmic complexity. Our work introduces several other novel optimizations, including lazy scaling in BFV homomorphic multiplication and an improved BFV decryption procedure in the Residue Number System (RNS) representation. We also develop a usable variant of BGV as a more efficient alternative to BFV for common practical scenarios. We implement our improved variants of BFV and BGV in PALISADE and evaluate their experimental performance for several benchmark computations. The experimental results suggest that our BGV implementation is faster for intermediate and large plaintext moduli, which are often used in practical scenarios with ciphertext packing, while our BFV implementation is faster for small plaintext moduli.
UR - http://www.scopus.com/inward/record.url?scp=85121918901&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85121918901&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-92078-4_21
DO - 10.1007/978-3-030-92078-4_21
M3 - Conference contribution
AN - SCOPUS:85121918901
SN - 9783030920777
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 608
EP - 639
BT - Advances in Cryptology – ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 3
A2 - Tibouchi, Mehdi
A2 - Wang, Huaxiong
PB - Springer Science and Business Media Deutschland GmbH
T2 - 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
Y2 - 6 December 2021 through 10 December 2021
ER -