{"ID":6267000,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-12T01:18:25.524530907Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.08042","arxiv_id":"2607.08042","title":"Degree-Constrained Interval Optimization for Minimax Polynomial Approximation in Homomorphic Encryption","abstract":"Homomorphic encryption (HE) enables privacy-preserving inference under arithmetic constraints that restrict encrypted evaluation to additions and multiplications. As a result, non-polynomial activation functions must be replaced by polynomial approximations. Among polynomial approximation methods, minimax approximation, typically computed by the Remez algorithm, is a standard approach because it minimizes the maximum approximation error over a given design interval. For minimax polynomial design, the approximation interval is a critical hyperparameter: a wider interval improves robustness to large-magnitude inputs while increasing the minimax approximation error under a fixed degree budget. In this paper, we formulate this trade-off as a distribution-aware interval optimization problem, where the approximation interval is chosen to minimize the mean-squared error (MSE) with respect to the pre-activation distribution of interest. To effectively control outside-interval inputs, we combine minimax polynomials with domain extension functions (DEFs) and their HE-realizable polynomial counterparts, domain extension polynomials (DEPs), which approximate a clipping operation outside the design interval and thereby suppress uncontrolled polynomial extrapolation. We first derive an analytically tractable DEF-based proxy objective that captures the trade-off between within-interval minimax approximation error and outside-interval clipping error. We then connect this idealized objective to HE-realizable DEP constructions through an implementation-error decomposition with an accompanying upper bound.","short_abstract":"Homomorphic encryption (HE) enables privacy-preserving inference under arithmetic constraints that restrict encrypted evaluation to additions and multiplications. As a result, non-polynomial activation functions must be replaced by polynomial approximations. Among polynomial approximation methods, minimax approximation...","url_abs":"https://arxiv.org/abs/2607.08042","url_pdf":"https://arxiv.org/pdf/2607.08042v1","authors":"[\"Jiheon Woo\",\"Donggyun Ryu\",\"Yongjune Kim\"]","published":"2026-07-09T01:33:24Z","proceeding":"cs.CR","tasks":"[\"cs.CR\"]","methods":"[]","has_code":false}