Paper 2023/544

PARMESAN: Parallel ARithMEticS over ENcrypted data

Jakub Klemsa, Czech Technical University in Prague, EURECOM
Melek Önen, EURECOM

Fully Homomorphic Encryption enables the evaluation of an arbitrary computable function over encrypted data. Among all such functions, particular interest goes for integer arithmetics. In this paper, we present a bundle of methods for fast arithmetic operations over encrypted data: addition/subtraction, multiplication, and some of their special cases. On top of that, we propose techniques for signum, maximum, and rounding. All methods are specifically tailored for computations with data encrypted with the TFHE scheme (Chillotti et al., Asiacrypt '16) and we mainly focus on parallelization of non-linear homomorphic operations, which are the most expensive ones. This way, evaluation times can be reduced significantly, provided that sufficient parallel resources are available. We implement all presented methods in the Parmesan Library and we provide an experimental evaluation. Compared to integer arithmetics of the Concrete Library, we achieve considerable speedups for all comparable operations. Major speedups are achieved for the multiplication of an encrypted integer by a cleartext one, where we employ special addition-subtraction chains, which save a vast amount of homomorphic operations.

Note: Update April'23: new version of Parmesan on top of TFHE-rs, preliminary results. :: This paper also serves as a report for the PARMESAN Library. :: Git repo: :: Rust crate:

Available format(s)
Publication info
Fully homomorphic encryptionParallelizationFast arithmeticTFHE schemeBenchmarking
Contact author(s)
jakub klemsa @ eurecom fr
melek onen @ eurecom fr
2023-04-26: last of 2 revisions
2023-04-17: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Jakub Klemsa and Melek Önen},
      title = {PARMESAN: Parallel ARithMEticS over ENcrypted data},
      howpublished = {Cryptology ePrint Archive, Paper 2023/544},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.