Integer Functions Suitable for Homomorphic Encryption over Finite Fields - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2021

Integer Functions Suitable for Homomorphic Encryption over Finite Fields

Abstract

Fully Homomorphic Encryption (FHE) gives the ability to evaluate any function over encrypted data. However, despite numerous improvements during the last decade, the computational overhead caused by homomorphic computations is still very important. As a consequence, optimizing the way of performing the computations homomorphically remains fundamental. Several popular FHE schemes such as BGV and BFV encode their data, and thus perform their computations, in finite fields. In this work, we study and exploit algebraic relations occurring in prime characteristic allowing to speed-up the homomorphic evaluation of several functions over prime fields. More specifically we give several examples of unary functions: “modulo”, “is power of b”, “Hamming weight” and “Mod2” whose homomorphic evaluation complexity over Fp can be reduced from the generic bound (2p)^(1/2) + O(log(p)) homomorphic multiplications, to (p)^(1/2) + O(log(p)), O(log(p)), O((p/ log(p))^(1/2) ) and O((p/ log(p))^(1/2) ) respectively. Additionally we provide a proof of a recent claim regarding the structure of the polynomial interpolation of the “less-than” bivariate function which confirms that this function can be evaluated in 2p − 6 homomorphic multiplications instead of 3p − 5 over Fp for p >= 5.
wahc21.pdf (931.96 Ko) Télécharger le fichier

Dates and versions

lirmm-04462570 , version 1 (16-02-2024)

Identifiers

Cite

Ilia Iliashenko, Christophe Negre, Vincent Zucca. Integer Functions Suitable for Homomorphic Encryption over Finite Fields. WAHC 2021 – 9th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Nov 2021, Séoul, South Korea. pp.1-10, ⟨10.1145/3474366.3486925⟩. ⟨lirmm-04462570⟩
11 View
3 Download

Altmetric

Share

More