Transieve: A Framework for Fair Evaluation of Transciphering Overhead

Abstract

Fully homomorphic encryption (FHE) allows computation on encrypted data without decryption, providing strong privacy guarantees for outsourced computation. However, two major costs limit practical adoption: ciphertext expansion, which increases data size by orders of magnitude, and computational overhead, as operations on ciphertext are far slower than on plaintext. Transciphering, also known as hybrid homomorphic encryption, addresses the bandwidth issue by encrypting data under a symmetric cipher while encrypting only the symmetric key under FHE. The server then homomorphically evaluates the cipher’s decryption to recover FHE ciphertexts. This reduces upload bandwidth at the expense of additional server computation.

This thesis introduces Transieve, an evaluation framework designed to compare transciphering pipelines fairly and systematically. The framework separates a transciphering pipeline into three independent layers: application workload, symmetric cipher, and FHE backend. This modular design allows new workloads, ciphers, and backends to be evaluated under consistent conditions.

Threshold Private Set Intersection (TPSI) is used as the case-study workload. In TPSI, items appearing in at least T out of N parties’ datasets are recovered without revealing private data to the service provider. Each party encodes its dataset as a Bloom filter, after which the server homomorphically evaluates a threshold circuit over encrypted filters.

The framework compares both direct-FHE and transciphering approaches across three FHE backends: TFHE-Boolean, TFHE-shortint, and BFV. These are paired with five symmetric ciphers: AES-128, Kreyvium, Grain-128a, Rasta, and Pasta. All configurations are evaluated at 128-bit security based on server compute cost, upload bandwidth, ciphertext expansion, latency, throughput, and recovery accuracy.

Results confirm that transciphering significantly reduces bandwidth requirements. At the largest set size, a plaintext Bloom filter is approximately 3.4 MiB. Direct Boolean FHE increases upload size to around 87 GiB, whereas transciphering reduces it to about 3.8 MiB, close to plaintext size and more than four orders of magnitude smaller than direct FHE.

This bandwidth reduction comes at the cost of additional server computation, and no single configuration performs best across all metrics. The cost of homomorphic decryption varies by nearly four orders of magnitude depending on the cipher-backend combination. Kreyvium on TFHE-Boolean is the most bandwidth-efficient option at roughly 310 milliseconds per output bit, while Pasta on BFV is the fastest at roughly 4 milliseconds per bit due to efficient SIMD packing, though with higher upload costs and limitations on the number of supported parties.

Performance is largely determined by how well a cipher matches the underlying FHE backend. Stream ciphers perform well on the bit-oriented Boolean backend. AES serves as a computationally expensive but standardized reference. Rasta performs poorly on both TFHE backends due to dense XOR operations. Pasta aligns well with BFV because of its prime-field arithmetic structure.

As party count increases, threshold circuit complexity grows rapidly. On Boolean backends, threshold evaluation eventually dominates computation cost. BFV handles threshold evaluation more efficiently using SIMD packing, but faces scalability limits due to security constraints. Overall, the results show a trade-off: bandwidth-constrained applications favour Boolean stream-cipher pipelines, while compute-constrained settings with moderate party counts favour BFV-based pipelines.