Paper 2021/1337

Large-Precision Homomorphic Sign Evaluation using FHEW/TFHE Bootstrapping

Zeyu Liu, Duality Technologies
Daniele Micciancio, Duality Technologies
Yuriy Polyakov, Duality Technologies

A comparison of two encrypted numbers is an important operation needed in many machine learning applications, for example, decision tree or neural network inference/training. An efficient instantiation of this operation in the context of fully homomorphic encryption (FHE) can be challenging, especially when a relatively high precision is sought. The conventional FHE way of evaluating the comparison operation, which is based on the sign function evaluation using FHEW/TFHE bootstrapping (often referred in literature as programmable bootstrapping), can only support very small precision (practically limited to 4-5 bits or so). For higher precision, the runtime complexity scales linearly with the ciphertext (plaintext) modulus (i.e., exponentially with the modulus bit size). We propose sign function evaluation algorithms that scale logarithmically with the ciphertext (plaintext) modulus, enabling the support of large-precision comparison in practice. Our sign evaluation algorithms are based on an iterative use of homomorphic floor function algorithms, which are also derived in our work. Further, we generalize our procedures for floor function evaluation to arbitrary function evaluation, which can be used to support both small plaintext moduli (directly) and larger plaintext moduli (by using a homomorphic digit decomposition algorithm, also suggested in our work). We implement all these algorithms using the PALISADE lattice cryptography library, introducing several implementation-specific optimizations along the way, and discuss our experimental results.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2022
fully homomorphic encryption programmable bootstrapping comparison sign FHEW TFHE DM CGGI implementation
Contact author(s)
ypolyakov @ dualitytech com
2022-09-17: last of 2 revisions
2021-10-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zeyu Liu and Daniele Micciancio and Yuriy Polyakov},
      title = {Large-Precision Homomorphic Sign Evaluation using FHEW/TFHE Bootstrapping},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1337},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.