Paper 2021/1335

Integer Functions Suitable for Homomorphic Encryption over Finite Fields

Ilia Iliashenko, Christophe Nègre, and Vincent Zucca

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 $\mathbb{F}_p$ can be reduced from the generic bound $\sqrt{2p} + \mathcal{O}(\log(p))$ homomorphic multiplications, to $\sqrt{p} + \mathcal{O}(\log(p))$, $\mathcal{O}(\log (p))$, $\mathcal{O}(\sqrt{p/\log (p)})$ and $\mathcal{O}(\sqrt{p/\log (p)})$ 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 $\mathbb{F}_p$ for $p\geq 5$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. WAHC 2021
Keywords
fully homomorphic encryptionfinite fieldspolynomial evaluation
Contact author(s)
ilia @ esat kuleuven be
christophe negre @ upvd fr
vincent zucca @ upvd fr
History
2021-10-06: revised
2021-10-05: received
See all versions
Short URL
https://ia.cr/2021/1335
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1335,
      author = {Ilia Iliashenko and Christophe Nègre and Vincent Zucca},
      title = {Integer Functions Suitable for Homomorphic Encryption over Finite Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1335},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1335}},
      url = {https://eprint.iacr.org/2021/1335}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.