PARMESAN: Parallel ARithMEticS over ENcrypted data

Jakub Klemsa; Melek Önen

Paper 2023/544

PARMESAN: Parallel ARithMEticS over ENcrypted data

Jakub Klemsa, Czech Technical University in Prague, EURECOM

Melek Önen

, EURECOM

Abstract

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: https://github.com/fakub/parmesan :: Rust crate: https://crates.io/crates/parmesan

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Fully homomorphic encryption Parallelization Fast arithmetic TFHE scheme Benchmarking
Contact author(s): jakub klemsa @ eurecom fr
melek onen @ eurecom fr
History: 2023-04-26: last of 2 revisions; 2023-04-17: received; See all versions
Short URL: https://ia.cr/2023/544
License: CC BY-SA

BibTeX

@misc{cryptoeprint:2023/544,
      author = {Jakub Klemsa and Melek Önen},
      title = {{PARMESAN}: Parallel {ARithMEticS} over {ENcrypted} data},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/544},
      year = {2023},
      url = {https://eprint.iacr.org/2023/544}
}