Privacy Preserving Function Evaluation Using Lookup Tables with Word-Wise FHE

Ruixiao Li*, Hayato Yamana

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Homomorphic encryption (HE) is a promising approach for privacy-preserving applications, enabling a third party to assess functions on encrypted data. However, problems persist in implementing privacy-preserving applications through HE, including 1) long function evaluation latency and 2) limited HE primitives only allowing us to perform additions and multiplications. A homomorphic lookup-table (LUT) method has emerged to solve the above problems and enhance function evaluation efficiency. By leveraging homomorphic LUTs, intricate operations can be substituted. Previously proposed LUTs use bit-wise HE, such as TFHE, to evaluate single-input functions. However, the latency increases with the bit-length of the function's input(s) and output. Additionally, an efficient implementation of multi-input functions remains an open question. This paper proposes a novel LUT-based privacy-preserving function evaluation method to handle multi-input functions while reducing the latency by adopting word-wise HE. Our optimization strategy adjusts table sizes to minimize the latency while preserving function output accuracy, especially for common machine-learning functions. Through our experimental evaluation utilizing the BFV scheme of the Microsoft SEAL library, we confirmed the runtime of arbitrary functions whose LUTs consist of all input-output combinations represented by given input bits: 1) single-input 12-bit functions in 0.14 s, 2) single-input 18-bit functions in 2.53 s, 3) two-input 6-bit functions in 0.17 s, and 4) three-input 4-bit functions in 0.20 s, employing four threads. Besides, we confirmed that our proposed table size optimization strategy worked well, achieving 1.2 times speed up with the same absolute error of order of magnitude of -4 (a × 10-4 where 1/ √ 10 ≤ a < √ 10) for Swish and 1.9 times speed up for ReLU while decreasing the absolute error from order -2 to -4 compared to the baseline, i.e., polynomial approximation.

Original languageEnglish
Pages (from-to)1163-1177
Number of pages15
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
VolumeE107.A
Issue number8
DOIs
Publication statusPublished - 2024 Aug

Keywords

  • fully homomorphic encryption
  • function evaluation
  • lookup table
  • privacy preserving

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Privacy Preserving Function Evaluation Using Lookup Tables with Word-Wise FHE'. Together they form a unique fingerprint.

Cite this