Sharing the Mask: TFHE Bootstrapping on Packed Messages

Fully Homomorphic Encryption (FHE) schemes typically experience significant data expansion during encryption, leading to increased computational costs and memory demands during homomorphic evaluations compared to their plaintext counterparts. This work builds upon prior methods aimed at reducing ciphertext expansion by leveraging matrix secrets under the Matrix-LWE assumption. In particular, we consider a ciphertext format referred to in this work as common mask (CM) ciphertexts, which comprises a shared mask and multiple message bodies. Each body encrypts a distinct message while reusing the common random mask. We demonstrate that all known FHEW/TFHE-style ciphertext variants and operations can be naturally extended to this CM format. Our benchmarks highlight the potential for amortizing operations using the CM structure, significantly reducing overhead. For instance, in the boolean setting, we have up to a 51% improvement when packing 8 messages. Beyond ciphertext compression and amortized evaluations, the CM format also enables the generalization of several core-TFHE operations. Specifically, we support applying distinct lookup tables on different encrypted messages within a single CM ciphertext and private linear operations on messages encrypted within the same CM ciphertext.