Fully homomorphic encryption (FHE) enables clients with small devices to securely delegate their computations to powerful servers. However, to delegate these computations, a client should generate and transmit several gigabytes of FHE keys to the server. Reducing the size of FHE keys without compromising efficiency is therefore highly desirable, particularly for applications involving mobile and IoT devices.

Garam Lee, Minsoo Kim, Jai Hyun Park, Seung-won Hwang, Jung Hee Cheon. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

Homomorphic encryption (HE) is being widely used for privacy-preserving computation. Since HE schemes only support polynomial operations, it is prevalent to use polynomial approximations of non-polynomial functions. We cannot monitor the intermediate values during the homomorphic evaluation; as a consequence, we should utilize polynomial approximations with sufficiently large approximation intervals to prevent the failure of the evaluation. However, the large approximation interval potentially accompanies computational overheads, and it is a serious bottleneck of HE application on real-world data. In this work, we introduce domain extension polynomials (DEPs) that extend the domain interval of functions by a factor ofkwhile preserving the feature of the original function on its original domain interval. By repeatedly iterating the domainextension process with DEPs, we can extend withO(logK) operations the domain of a given function by a factor ofKwhile the feature of the original function is preserved in its original domain interval. By using DEPs, we can efficiently evaluate in an encrypted state a function that converges at infinities, i.e., limx→∞f(x)and limx→-∞f(x)exist in R. To uniformly approximate the function on [–R,R], our method exploitsO(logR) operations andO(1) memory. This is more efficient than the previous approach, the minimax approximation and Paterson-Stockmeyer algorithm, which uses Ω(√R) multiplications and Ω(√R) memory for the evaluation. As another application of DEPs, we also suggest a method to manage the risky outliers from a large interval [–R,R] by usingO(logR) additional multiplications. As a real-world application, we trained the logistic regression classifier on large public datasets in an encrypted state by using our method. We exploit our method to the evaluation of the logistic function on large intervals, e.g., [-7683, 7683].