Paper 2025/216

Practical TFHE Ciphertext Sanitization for Oblivious Circuit Evaluation

Abstract

Homomorphic encryption (FHE) enables the computation of arbitrary circuits over encrypted data. A widespread application of HE is oblivious circuit evaluation, where a sender evaluates its private circuit over a receiver's encrypted data, covering scenarios such as oblivious inference and oblivious PRF protocols. However, while the security of HE guarantees the receiver's privacy against the sender, the privacy of the sender's circuit is not solely derived from the security of HE. One effective solution to this problem is ciphertext sanitization, an algorithm that removes any information contained in a ciphertext except for the plaintext. Since its introduction by Ducas and Stehlé (Eurocrypt 2016), several approaches have been proposed for constructing sanitization algorithms for TFHE, but they remain highly impractical. In this work, we present a novel sanitization algorithm for TFHE ciphertexts that is practically deployable. Unlike prior methods that introduce randomization throughout the entire bootstrapping procedure or require repeated bootstrappings, our approach involves only two lightweight randomization steps at the input and output of the original TFHE bootstrapping, without modifying its core operations. As a result, our algorithm achieves sanitization with a single bootstrapping and minimal randomization, fully leveraging the fast performance of TFHE bootstrapping. In addition, we design a zero-knowledge argument of knowledge (ZKAoK) for TFHE ciphertexts and bootstrapping keys to address malicious receivers. To the best of our knowledge, this work is the first to construct a concrete ZKAoK that covers all receiver-sent materials, enabling a secure TFHE-based protocol against a malicious receiver. We provide a proof-of-concept implementation to demonstrate the practicality of our solution. Our experiments show that it takes approximately 42.17 ms to sanitize a single TFHE ciphertext, achieving up to a 31× speedup compared to the state-of-the-art method by Kluczniak (CiC 2025).