Efficient Homomorphic Evaluation on Large Intervals¶
Authors: Jung Hee Cheon; Wootae Kim; Jai Hyun Park
Year: 2022
Venue: IEEE Access 2022
type: technique collection: catalogue, sok-references status: auto
Links: DOI · ePrint 2022/280
Summary¶
Auto-extracted summary (unreviewed)
Introduces domain extension polynomials (DEPs) that iteratively widen the domain on which a polynomial approximation of a function remains valid, so that functions converging at infinities (e.g. the logistic function) can be evaluated homomorphically on [-R, R] with O(log R) multiplications and O(1) memory instead of the Omega(sqrt(R)) cost of minimax approximation with Paterson-Stockmeyer. Using CKKS, the logistic function on [-7683, 7683] is evaluated in 9.43 s versus an estimated 172 s for the minimax approach, and the method is used for encrypted logistic regression training on MNIST and the Swarm Behavior dataset; a DEP-based outlier-handling method is also proposed.
Abstract¶
Homomorphic encryption (HE) is being widely used for privacypreserving 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., limx→∞f(x) and limx→−∞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 Ω( √ 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 using O(log R) 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]. © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. DOI: 10.1109/TIFS.2022.3188145
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Domain extension polynomials (DEPs) extending approximation intervals by a factor k per iteration | llm | 0.85 |
| contribution | O(log R) operation / O(1) memory homomorphic evaluation of functions converging at infinities on [-R, R] | llm | 0.85 |
| contribution | Method to manage risky outliers on large intervals with O(log R) extra multiplications | llm | 0.85 |
| contribution | Encrypted logistic regression training on large public datasets using the logistic function on large intervals | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| libraries | chebfun | llm | 0.85 |
| libraries | OpenPEGASUS | llm | 0.85 |
| models | logistic regression | llm | 0.85 |
| datasets | MNIST | llm | 0.85 |
| datasets | Swarm Behavior | llm | 0.85 |
| tasks | encrypted logistic regression training | llm | 0.85 |
| tasks | polynomial approximation of non-polynomial functions | llm | 0.85 |
| hardware | Intel Xeon Silver 4114 CPU @ 2.20 GHz (single thread) | llm | 0.85 |
| security level | 128-bit | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://bitbucket.org/malb/lwe-estimator.30 (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/Alibaba-Gemini-Lab/OpenPEGASUS (URL found in the full text) | regex | 0.50 |
| limitations | Method applies to functions that converge at infinities (or differ from a low-degree polynomial by such a function); efficient evaluation of arbitrary functions on large intervals is left open | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | runtime of logistic function evaluation: 9.43 s (DEP) vs est. 172.46 s (minimax) (domain size 15366, max error < 0.045, CKKS N=2^16, single thread) | llm | 0.85 |
| key result | runtime of logistic function evaluation: 6.72 s (DEP) vs 39.28 s (minimax) (domain size 2560, max error < 0.045) | llm | 0.85 |
| key result | complexity: O(log R) multiplications, O(1) memory vs Omega(sqrt(R)) for minimax + Paterson-Stockmeyer (uniform approximation on [-R, R]) | llm | 0.85 |
System card: Large-interval evaluation¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | CKKS function evaluation |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Active |
| Relation to the SoK | Extends approximation domains for non-linear functions. |
| Note | SoK cites it for robustness when encrypted activations fall outside the fitted interval. |
| Systems page | Large-interval evaluation |
SoK reference [106]¶
J. H. Cheon, W. Kim, and J. H. Park, “Efficient homomorphic evaluation on large intervals,” IEEE Transactions on Information Forensics and Security, vol. 17, pp. 2553–2568, 2022.
Listed on the reference page of the site.
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 27 [p.6], TFHE 13 [p.6]
- model: Logistic regression 38 [p.1], CNN 1 [p.5]
- dataset: MNIST 9 [p.5]
- hardware: Intel Xeon 2 [p.25]
- technique: Minimax approximation 71 [p.1], Polynomial approximation 47 [p.1], Paterson-Stockmeyer 15 [p.3], Bootstrapping 7 [p.17], Chebyshev 5 [p.6], ReLU 4 [p.5], SIMD packing 3 [p.20], Programmable bootstrapping 2 [p.19], Remez 2 [p.7]
- task: Medical / healthcare 3 [p.33]
- topic: Homomorphic encryption 90 [p.1]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-044_efficient-homomorphic-evaluation-on-large-intervals.pdf |
catalogue | 34 | 900.5 KB | 94236d2d9b1d |
|
references/sok-references/106_efficient-homomorphic-evaluation-on-large-intervals.pdf |
sok-references | 34 | 900.5 KB | 94236d2d9b1d |
byte-identical to references/catalogue/3-044_efficient-homomorphic-evaluation-on-large-intervals.pdf |
Database key: efficient-homomorphic-evaluation-on-large-intervals · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set efficient-homomorphic-evaluation-on-large-intervals COLUMN VALUE