Polynomial function approximations with leading integer coefficients for efficient encrypted implementations
Loading...
Date
2025-09-04
Journal Title
Journal ISSN
Volume Title
Publisher
Alternative Title(s)
Abstract
Computations on encrypted data can, in principle, be performed using homomorphic encryption. However, due to certain limitations, only algorithms based on polynomial functions can be efficiently implemented in an encrypted setting. Consequently, polynomial approximations of non-polynomial functions are essential for efficient encrypted computations. In particular, low- to moderate-degree polynomial approximations of activation functions in neural networks are of special interest.We show that the accuracy of encryption-friendly approximations can be improved through a simple yet effective extension of state-of-the-art methods. Specifically, we show that enforcing a leading integer coefficient enables the use of polynomials of one degree higher than all existing approaches. Incorporating this novel integer constraint into classical regression problems initially leads to mixed-integer programs (MIPs). However, we develop tailored solution schemes that avoid MIP solving. Using these schemes, we compute new polynomial approximations for various test cases and demonstrate the effectiveness of our method compared to existing approaches.
Description
Table of contents
Keywords
Polynomial regression, Optimization, Homomorphic encryption, Chebyshev regression, Privacy-preserved machine learning
Subjects based on RSWK
Polynomiale Regression, Optimierung, Homomorphismus, Chiffrierung, Čebyšev-Polynome, Maschinelles Lernen, Datenschutz