Tetris: Versatile TFHE LUT and Its Application to FHE Instruction Set Architecture

Ruida Wang; Jikang Bai; Xuan Shen; Xianhui Lu; Zhihao Li; Binwu Xiang; Zhiwei Wang; Hongyu Wang; Lutan Zhao; Kunpeng Wang; Rui Hou

Paper 2025/1623

Tetris: Versatile TFHE LUT and Its Application to FHE Instruction Set Architecture

Ruida Wang, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cybersecurity, UCAS

Jikang Bai, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cybersecurity, UCAS

Xuan Shen, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cybersecurity, UCAS

Xianhui Lu, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cybersecurity, UCAS

Zhihao Li, Digital Technologies, Ant Group

Binwu Xiang, East China Normal University

Zhiwei Wang, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cybersecurity, UCAS

Hongyu Wang, Shanxi University

Lutan Zhao, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cybersecurity, UCAS

Kunpeng Wang, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cybersecurity, UCAS

Rui Hou, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cybersecurity, UCAS

Abstract

Fully Homomorphic Encryption (FHE) enables computation over encrypted data, but deployment is hindered by the gap between plaintext and ciphertext programming models. FHE compilers aim to automate this translation, with a promising approach being FHE Instruction Set Architecture (FHE-ISA) based on homomorphic look-up-tables (LUT). However, existing FHE LUT techniques are limited to 16-bit precision and face critical performance bottlenecks. We introduce Tetris, a versatile TFHE LUT framework for high-precision FHE instructions. Tetris incorporates three advances: a) A GLWE-based design with refined noise control, enabling up to 32-bit LUTs; b) A batched TFHE circuit bootstrapping algorithm that enhances the LUT performance; and c) Adaptive parameterization and parallel execution strategy that is optimized for high-precision evaluation. These techniques deliver: a) The first general FHE instruction set with 16-bit bivariate and 32-bit univariate operations; b) Performance improvements of 2×-863× over modern TFHE LUT approaches, and 2901× lower latency than the leading CKKS-based solution [CRYPTO'25]; (c) Up to 65× speedups over existing FHE-ISA implementations, and 3×-40× faster than related FHE compilers.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: TFHE LUT Circuit Bootstrapping
Contact author(s): wangruida @ iie ac cn
baijikang @ iie ac cn
shenxuan @ iie ac cn
luxianhui @ iie ac cn
lzh458070 @ antgroup com
bwxiang @ sc ecnu edu cn
wangzhiwei @ iie ac cn
18235109593 @ 163 com
zhaolutan @ iie ac cn
wangkunpeng @ iie ac cn
hourui @ iie ac cn
History: 2025-09-11: approved; 2025-09-09: received; See all versions
Short URL: https://ia.cr/2025/1623
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1623,
      author = {Ruida Wang and Jikang Bai and Xuan Shen and Xianhui Lu and Zhihao Li and Binwu Xiang and Zhiwei Wang and Hongyu Wang and Lutan Zhao and Kunpeng Wang and Rui Hou},
      title = {Tetris: Versatile {TFHE} {LUT} and Its Application to {FHE} Instruction Set Architecture},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1623},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1623}
}