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 Original: eprint.iacr.org/2025/1623 ↗

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

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.
History: 2025-09-09: last updated; 2025-09-09: published
Short URL: https://ia.cr/2025/1623
License: https://creativecommons.org/licenses/by/4.0/

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}
}