Efficient Homomorphic Evaluation on Large Intervals

Abstract

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 of k while preserving the feature of the original function on its original domain interval. By repeatedly iterating the domain-extension process with DEPs, we can extend with O(log K) operations the domain of a given function by a factor of K while 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., lim(x ->infinity) f(x) and lim(x ->-infinity) f(x) exist in R. To uniformly approximate the function on [- R, R], our method exploits O(log R) operations and O(1) memory. This is more efficient than the previous approach, the minimax approximation and Paterson-Stockmeyer algorithm, which uses Omega(root R) multiplications and Omega(root 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 using O(log R) additional multiplications. As a realworld 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].