Large-Precision Homomorphic Sign Evaluation Using FHEW/TFHE Bootstrapping

Zeyu Liu, Daniele Micciancio, Yuriy Polyakov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsShweta Agrawal, Dongdai Lin
PublisherSpringer Science and Business Media Deutschland GmbH
Pages130-160
Number of pages31
ISBN (Print)9783031229657
DOIs
StatePublished - 2022
Externally publishedYes
Event28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022 - Taipei, Taiwan, Province of China
Duration: Dec 5 2022Dec 9 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13792 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022
Country/TerritoryTaiwan, Province of China
CityTaipei
Period12/5/2212/9/22

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Large-Precision Homomorphic Sign Evaluation Using FHEW/TFHE Bootstrapping'. Together they form a unique fingerprint.

Cite this