Ciphertext- and Polynomial-Level Optimization for Fully Homomorphic Encryption
Cryptography and SecuritySoftware Engineering
Summary
The authors introduce Recifhe, a new compiler for fully homomorphic encryption (FHE) that improves performance by optimizing both entire encrypted blocks (ciphertexts) and the smaller polynomial operations inside them. Existing compilers only optimize at the ciphertext level, missing chances to speed things up. Recifhe finds and removes repeated work done on polynomials during encryptions, making encrypted computations faster by about 25%. This can help make privacy-preserving services more efficient.
Authors
Seongho Kim, Heelim Choi, Jaemin Kim, Seonyoung Cheon, Dongkwan Kim, Jaeho Lee, Hoyun Youm, Dongyoon Lee, Hanjun Kim, Yongwoo Lee
Abstract
Fully homomorphic encryption (FHE) schemes such as RNS-CKKS enable privacy-preserving services by allowing direct computation on encrypted data. While recent FHE compilers optimize FHE programs, they operate at the coarse-grained ciphertext level, where each ciphertext operation comprises a sequence of polynomial operations. At this granularity, the compilers miss optimization opportunities across ciphertext operations. This work presents Recifhe, a new multi-level compiler that supports not only ciphertext-level but also polynomial-level optimization. At the ciphertext level, Recifhe transforms a non-FHE input program into an FHE program by inserting ciphertext management operations and applies global optimizations. At the polynomial level, Recifhe eliminates redundant polynomial computations across ciphertext operations. Recifhe achieves a 1.25x speedup over ciphertext-level-only optimization.