In this meetup, we present a bundle of methods for fast arithmetic operations over encrypted data: addition/subtraction, (scalar) multiplication, and some other operations or special cases. To achieve low evaluation times, we employ a particular non-standard integer representation, which enables parallel addition, upon which we construct other operations with a strong focus on their parallelization.
A particular interest goes for scalar multiplication (i.e., multiplication of an encrypted integer by an unencrypted one), for which we define a specific flavor of addition-subtraction chains (ASC). Interestingly, our brute-forced optimal ASCs for 12-bit integers require 20% less additions on average than the double-and-add method, and they might be re-used for other kinds of integer representations as well.
We conclude by presenting selected experimental results of our implementation—the PARMESAN Library—running on a 128-threaded super-computer node.
Jakub Klemsa is about to finish his PhD at CTU in Prague, Czechia, and at the same time, he has just finished a one and a half year long research stay at EURECOM, France, under the supervision of Melek Önen. During his stay, he focused on the applicability of parallel addition algorithms and other arithmetic operations over TFHE-encrypted data, including TFHE parameter optimization, as well as he studied multi-key FHE.
The newsletter where we post community announcements: https://fheorg.substack.com/
The discord server where you can discuss FHE related topics with the community: https://discord.fhe.org
Make sure to join either (or both) of these to stay informed about future events!