IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
1
Decision-Aware Quadratic ReLU Replacement for HE-Friendly Inference
arXiv:2605.22237v1 [cs.CR] 21 May 2026
Rui Li , Wenyuan Wu , and Weijie Miao
Abstract—Fully homomorphic encryption (FHE) supports only additions and multiplications, so FHE-only neural-network inference typically replaces ReLU with polynomials fitted over empirical activation intervals. Such interval fitting often requires higher-degree polynomials to control activation error, incurring homomorphic evaluation costs, while classification is determined by the final logit decision. We revisit ReLU replacement from a decision-aware perspective: given a trained single-hiddenlayer ReLU MLP and a specified calibration set, can an HEfriendly low-degree polynomial replace ReLU without retraining while preserving calibration-set decisions? We focus on quadratic replacement, the lowest-degree choice that retains a genuine perunit nonlinearity. For calibration sets positive-margin separable in the lifted space, we formulate quadratic replacement as a linear separation problem, yielding necessary and sufficient conditions for calibration-lossless replacement and a constructive algorithm for the coefficients. When the positive-margin condition fails— typically due to a few misclassified calibration samples—we extend the same geometric framework via reduced convex hulls and Lagrangian-dual soft-margin relaxations, which bound the influence of any single sample, converting the problem into smaller convex quadratic programs that yield approximately feasible coefficients with high empirical agreement on calibrationset decisions. In particular, at the maximal weight cap µ = 1, the reduced-convex-hull relaxation reduces to the convex-hull separation of the strictly separable case; the relaxation thus continuously extends the exact theory. Under CKKS, the quadratic replacement matches plaintext top-1 accuracy on multiple benchmarks, running 3.7–4.1× faster than Remez-7 in the activation module and 1.18–1.68× faster end-to-end. Index Terms—Fully homomorphic encryption, privacypreserving machine learning, convex geometry, MLP, posttraining certification.
I. I NTRODUCTION ULLY homomorphic encryption (FHE) enables a server to evaluate arithmetic circuits over encrypted data without decrypting the input [1]–[3]. This property makes FHE a natural tool for privacy-preserving neural-network inference. However, encrypted computation is efficient mainly when the network can be expressed as a low-depth circuit of additions and multiplications. Affine layers fit this model, whereas
F
This work was supported in part by the National Key Research Project of China under Grant 2025YFA1017201, and in part by the National Natural Science Foundation of China (NSFC) under Grant 12571553. (Corresponding author: Wenyuan Wu.) Rui Li and Wenyuan Wu are with the Chongqing Key Laboratory of Secure Computing for Biology, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, 266 Fangzheng Avenue, Beibei District, Chongqing 400714, China (e-mail: [email protected]; [email protected]). Weijie Miao is with the Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong, China (email: [email protected]).
comparisons, max operations, and ReLU activations are costly when inference uses only FHE arithmetic. We use FHEonly inference to mean this noninteractive arithmetic-circuit route, without interactive or hybrid nonlinear subprotocols. This tension makes nonlinear activations a central issue in HEfriendly neural-network inference [7]–[10], [19]–[21], [23]. Existing private-inference systems address nonlinear activations through several routes. The first route is FHE-only evaluation: the network is compiled into a polynomial arithmetic circuit, and nonlinear activations are replaced by polynomial functions [7]–[11], [19]. This route keeps the online protocol simple, but its accuracy and efficiency depend strongly on polynomial degree, multiplicative depth, rescaling, and modulus-chain budget. The second route is secure multiparty computation (MPC), which can evaluate comparisons and ReLU-like operations through interactive protocols, but pays communication, synchronization, and system-level costs [5], [6], [14], [15]. The third route combines FHE with MPC or garbled circuits, using FHE for linear layers and interactive protocols for nonlinear layers [12], [13], [16]. These hybrid systems can support exact or high-fidelity nonlinearities, but they also introduce protocol complexity. This paper follows the FHE-only route and asks how far one can go with a very low-degree, HE-friendly polynomial replacement. A common FHE-only strategy is to replace ReLU by a polynomial fitted over an empirical activation interval. The polynomial may be the square function, a Chebyshev or leastsquares approximation, a Remez/minimax polynomial, or a composite polynomial approximation [17], [19]–[23]. Such methods are FHE-compatible because they avoid comparisons, but high-degree polynomials are not necessarily HE-friendly: controlling activation error over a broad interval often requires higher degree, incurring additional ciphertext-ciphertext multiplications, rescaling operations, modulus-chain length, and latency. Their design objective is module-local, meaning that the activation module is optimized in isolation. A typical replacement solves a scalar approximation problem of the form min
sup |p(u) − max{0, u}| ,
p∈Πd u∈[a,b]
(1)
where [a, b] is chosen from activation statistics or from a conservative range. Objective (1) is a meaningful numerical approximation criterion, but it is only a proxy for the deployed classification objective. A classifier returns the label with the largest final output logit; hence the relevant event is whether the final top1 logit ordering is preserved. Equivalently, a replacement is harmless for a sample as long as its score perturbation does
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
2
not cross the sample’s top-1/top-2 margin; the same activation error can be harmless for a large-margin sample and harmful for a low-margin sample. This margin view is consistent with the geometry of margin-based classification and with the broader observation that small perturbations can change neural-network decisions when they align with vulnerable directions [24], [28], [29]. Conversely, a polynomial that is not a close pointwise approximation to ReLU at intermediate activations may still preserve all final top-1 decisions on a declared calibration set. Fixed-interval approximations also inherit a range-selection issue: if future pre-activations fall outside the interval used for fitting, polynomial behavior is no longer controlled by the stated approximation error, a classical concern in polynomial approximation [17]. To obtain a mathematically transparent yet practically common setting, this paper studies single-hidden-layer ReLU MLPs and MLP heads on frozen representations. A single replaced nonlinear layer is the minimal setting in which the trained hidden representation, the output head, and the final decision rule can be analyzed exactly. The setting covers tabular MLPs as well as DINOv2 visual features and Qwen3Embedding text features followed by MLP heads [33], [34]. Related representation-transfer and student-model settings also use compact MLP or MLP-like heads/backbones [30]–[32]. For frozen-backbone experiments, the privacy claim is encrypted MLP-head inference: the feature extractor runs on the client and the resulting embedding is encrypted before serverside head evaluation. Theoretical formulation.: Instead of first approximating ReLU locally and then hoping the final classifier remains unchanged, we globally impose conditions on the final logit ordering induced by the trained classifier. Given a trained single-hidden-layer ReLU MLP and a specified calibration set, we ask whether ReLU can be replaced by a low-degree polynomial, without retraining, while preserving the model’s decisions on that calibration set. The coefficients are computed offline; the online encrypted circuit contains only the resulting polynomialized model. We focus on a shared quadratic replacement q(u; α, β, η) = αu2 + βu + η.
(2)
This is the lowest-degree replacement that retains a genuine per-unit nonlinear response: the shared quadratic acts on each hidden pre-activation yj through the self-term yj2 , introducing no cross-unit terms yj yk . A linear replacement would instead collapse a single-hidden-layer ReLU MLP into an affine classifier once the trained head is fixed, whereas degrees above two require additional encrypted multiplications and rescalings. Quadratic replacement is therefore a natural boundary point: it keeps nonlinearity while remaining HE-friendly. Our exact theory starts from positive-margin separability in the lifted calibration space. For binary classification, quadratic replacement reduces to positive-margin hyperplane separation of two lifted convex hulls [18]: this condition is necessary and sufficient for calibration-lossless replacement, and when it holds valid quadratic coefficients can be constructed. For multiclass heads, the corresponding condition is strict feasibil-
ity of pairwise affine logit-margin inequalities in the quadratic coefficients. Many practical calibration sets fail these positive-margin conditions under such a small quadratic family. When positivemargin separation or pairwise margin feasibility is unavailable, we extend the same geometric framework through reducedconvex-hull and Lagrangian-dual soft-margin relaxations [28], [29], which convert the calibration logit-ordering constraints into small convex quadratic programs. The relaxed solution is not an exact certificate; it is an approximately feasible set of coefficients, reported together with margins, slacks, and calibration/test agreement diagnostics. Contributions.: The contributions of this paper are as follows. Decision-aware formulation for HE-friendly ReLU replacement. We formulate post-training activation replacement as a calibration-set logit-ordering problem rather than a module-local ReLU approximation problem. The benefit is direct alignment with classification output: the polynomial is chosen to preserve the trained model’s top1 decisions on the declared calibration set, while the online encrypted circuit remains a low-degree arithmetic circuit. • Exact finite-sample theory via positive-margin separation. For trained single-hidden-layer ReLU MLPs, we use algebraic identity transformations to express quadratic replacement through lifted statistics induced by the fixed model. In the binary case, exact calibration-lossless replacement is possible if and only if the lifted positive and negative convex hulls admit a positive-margin hyperplane separator; when feasible, the closest-pair construction yields quadratic coefficients and a margin diagnostic in O(n log n) time after the lifted statistics are computed. In the multiclass case, exact calibration-lossless preservation becomes strict feasibility of pairwise affine logit-margin inequalities. • Reduced-hull and soft-margin relaxations beyond positive-margin feasibility. When the positive-margin conditions fail, we connect the exact geometry to practical surrogates through reduced convex hulls and Lagrangian-dual soft-margin relaxations. These relaxations produce smaller convex quadratic programs and return approximately feasible coefficients with explicit slack and agreement diagnostics, rather than claiming exact preservation where none is certified. At the maximal weight cap, the reduced convex hull reduces to the standard convex hull, so this relaxation continuously extends the exact theory of the previous contribution rather than forming a separate method. • Algorithms, library, and encrypted validation. We implement the coefficient-construction pipeline in the open-source Q UAD 4FHE library,1 including hiddenstatistic computation, hard-case testing, reduced-convexhull search, soft-margin fallback, and regime reporting. The coefficient search is performed offline and does not •
1 https://github.com/LeeRay629/Rethinking_ReLU_Replacement_in_MLP_ Classifiers
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
alter the online encrypted circuit. Using the resulting coefficients, CKKS evaluation of the quadratic replacement model matches the corresponding plaintext top1 accuracy on MLP/Otto, DINOv2/FGVC-Aircraft, and Qwen3/MASSIVE, while running 3.7–4.1× faster than Remez-7 in the activation module and 1.18–1.68× faster end-to-end. II. R ELATED W ORK A. HE-friendly and secure neural inference Early encrypted and secure machine-learning systems studied private classification and neural-network prediction under cryptographic constraints [4]–[6]. CryptoNets [7] showed that neural-network inference can be evaluated over encrypted data when the network is expressed as a low-degree arithmetic circuit. Subsequent FHE-only and HE-compiler systems improved encrypted linear algebra, batching, packing, and circuit optimization: LoLa optimized low-latency encrypted inference [8]; CHET [9] and EVA [10] compiled homomorphic tensor computations; and nGraph-HE2 [11] integrated CKKSbased encrypted inference into a deep-learning framework. These systems establish a common design principle for FHEonly inference: reducing multiplicative depth and avoiding expensive nonlinear encrypted operations are critical for practical latency. Another line of work handles nonlinearities through MPC, garbled circuits, or hybrid FHE–MPC protocols. GAZELLE [12] combines homomorphic linear layers with garbled-circuit nonlinearities. DELPHI [13] provides cryptographic inference with exact ReLU subprotocols or polynomial approximations. CrypTFlow2, XONN, and Cheetah improve secure two-party inference through optimized comparison, binary-network, or nonlinear-layer protocols [14]–[16]. These systems are complementary to ours: they securely compute nonlinearities through additional protocol machinery, whereas we remain FHE-only and ask whether an HE-friendly polynomial replacement can preserve the trained classifier’s top-1 decisions on a declared calibration set. B. Post-training polynomial treatment of ReLU Polynomial activation replacement is a standard strategy for FHE-only neural-network inference because it removes comparisons and piecewise-linear operations from the encrypted circuit. The square activation is the cheapest nonlinear choice, but directly substituting it for ReLU can substantially shift a trained model’s decision boundary. Classical approximation theory provides Chebyshev, least-squares, minimax, and Remez tools for reducing pointwise approximation error on a fixed interval [17]. CryptoDL-style networks adopt this polynomial viewpoint for encrypted inference [19]. More accurate post-training methods include Precise Approximation, which composes low-degree minimax polynomials to approximate ReLU and max-pooling without retraining [20]; OLA, which selects layerwise approximation degrees and modulus chains according to layer impact and input distributions [21]; SAFENet, which uses mixed-degree approximations to balance accuracy and cost [22]; and AutoFHE, which searches
3
over polynomial activations and FHE evaluation architectures [23]. These approaches are FHE-compatible, but higherdegree polynomials can still be costly in practice because they require more encrypted multiplications, rescalings, and modulus levels. Most post-training polynomial replacements optimize a module-local objective: they choose an empirical activation interval and approximate ReLU, or an activation-related surrogate, accurately on that interval. Our work is also post-training, but the mathematical object is different. We do not fit ReLU locally on [a, b]; instead, we globally fit the logit-ordering inequalities induced by the fixed hidden layer, the fixed output head, and the declared calibration set. Thus intermediate activation values need not be close to ReLU as long as the final top-1 label is preserved. This decision-aware formulation turns scalar activation approximation into a convex-geometric feasibility and relaxation problem: positive-margin separability of the lifted calibration sets gives a calibration-lossless certificate, while failures of the positive-margin condition are handled by reduced-convex-hull and soft-margin convex programs. III. P ROBLEM F ORMULATION A. A single replaced layer Let Dcal = {xi }ni=1 be a declared finite calibration set. Before fitting the replacement polynomial, each sample is assigned a fixed target decision ti . In this paper and in all reported experiments, ti is the decision of the original trained ReLU model on xi (the positive/negative decision for binary classifiers, the top-1 class for multiclass classifiers). The fitting objective is thus post-training agreement with the trained classifier, not retraining against new labels; the same algebra would apply to externally supplied labels, but that is not the setting evaluated here. Definition 1 (Calibration-lossless replacement). For a fixed calibration set and fixed targets {ti }ni=1 , a polynomial replacement is calibration-lossless if the predicted decision of the polynomialized model equals ti for every xi ∈ Dcal . Scope and guarantee.: The guarantees in this paper are deliberately scoped, and we state that scope once here. (i) Architecture. The construction applies to a single replaced ReLU layer—a single-hidden-layer MLP, or an MLP head on a frozen backbone—because the lifted geometry is planar only when one nonlinear layer lies between fixed affine maps. (ii) Calibration dependence. The fitted coefficients depend on the declared calibration set, exactly as fixed-interval baselines depend on their empirical fitting interval [a, b]; the trained network is itself already data-dependent. (iii) Nature of the certificate. An exact certificate states only that the declared calibration-set decisions are unchanged; it is a finite-sample statement, not a distribution-free guarantee for unseen inputs. A relaxed RCH or soft-margin solution provides high empirical agreement rather than certified losslessness, and is always reported with explicit margin, slack, and calibration/test agreement diagnostics. (iv) Empirical claims. Small-pool results are single fixed-split ablations that diagnose calibration-pool size, not estimates of sampling variance over random pools.
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
4
Generalization is assessed, as for any learned model, through held-out test results. We begin with a trained binary single-hidden-layer ReLU MLP m X F (x) = aj σ yj (x) + b, σ(u) = max{0, u}, (3) j=1
where aj and b are the trained output weights and bias, and yj (x) is the jth hidden pre-activation. The first-layer weights, output weights, and bias are fixed; no model retraining is performed. Only the three replacement coefficients are fitted in a post-training calibration step. We separate the replacement process into an offline calibration phase, in which the trained ReLU model is evaluated on the calibration set and the coefficients (α, β, η) are computed, and an online encrypted inference phase, in which the server evaluates only the resulting polynomialized arithmetic circuit on encrypted inputs. This separation is essential: the coefficient computation may use plaintext calibration data, convex-hull operations, or small convex programs, but none of these appears inside the encrypted inference circuit. We replace every ReLU in the layer by a shared quadratic polynomial q(u; α, β, η) = αu2 + βu + η, giving Feα,β,η (x) =
m X
aj αyj (x)2 + βyj (x) + η + b
Equivalently, all replaced positive scores exceed all replaced negative scores. Since Cβ,η is common to all samples, the existence of such a threshold depends only on the direction θ = (α, β) in the lifted plane. If deployment requires preserving the original zero threshold, then the offset controlled by η must additionally place the separated score interval around zero; this case is handled after the constructive result in Section IV. B. Frozen representations The same algebra holds when the replaced layer follows an arbitrary frozen representation. Let g : X → Rm be fixed and consider m X F (x) = aj σ gj (x) + b. (8) j=1
Replacing yj (x) by gj (x) in (4) defines Qg (x), Hg (x), Φg (x). Therefore all binary feasibility and coefficient-construction results below apply to frozen DINOv2 or Qwen3-Embedding features followed by a single-hidden-layer ReLU MLP head. C. Multiclass heads For K classes, let the trained ReLU logits be Fc (x) =
j=1
=α
X
X
aj yj (x)2 +β
aj yj (x) + b
{z H(x)
}
j
{z Q(x)
|
}
+ (1 − β)b + η
X
aj .
(4)
j
| Let B =
ac,j σ yj (x) + bc ,
c = 1, . . . , K.
{z Cβ,η
}
P
j aj , so that Cβ,η = (1 − β)b + ηB.
j
In the reported experiments, the target class is ti = Top1(F1 (xi ), . . . , FK (xi )), with a fixed deterministic tie rule if needed. Exact preservation below is expressed with positive pairwise logit margins; thus, when the original ReLU logits have a unique top-1 class, these inequalities preserve that top1 decision with positive margin. Define class-wise quantities X X Qc (x) = ac,j yj (x)2 , Lc (x) = ac,j yj (x), j
Definition 2 (Binary quadratic lift). For the fixed trained binary head and the shared quadratic replacement above, define X X aj yj (x)2 , H(x) = aj yj (x) + b, (5) Q(x) = j
and
j
Hc (x) = Lc (x) + bc ,
Bc =
X
⊤
θ = (α, β) .
(6)
We call Φ(x) the binary quadratic lift. It is two-dimensional because, after the trained head is fixed, a shared quadratic replacement can change the binary score only through θ⊤ Φ(x) plus the sample-independent offset Cβ,η . Let D+ and D− denote the positive and negative target calibration sets induced by the original ReLU decisions. For binary classifiers, the exact feasibility analysis below uses an adjustable post-replacement threshold. A replacement is calibration-lossless for the binary split if there exists a threshold τ such that min Fe (x) > τ > max− Fe(x). x∈D
(7)
(10)
ac,j .
j
Here Lc is the bias-free linear statistic, while Hc is the affine statistic analogous to the binary notation. After the replacement, Fec (x) = αQc (x) + βLc (x) + ηBc + bc
⊤ Φ(x) = Q(x), H(x) ∈ R2 ,
x∈D +
(9)
j=1
j
|
m X
= αQc (x) + βHc (x) + ηBc + (1 − β)bc .
(11)
The replacement preserves the target top-1 decision of xi exactly when Feti (xi ) > Fec (xi ) ∀c ̸= ti .
(12)
For each pair (i, c), where c ̸= ti , define target-minuscompetitor quantities ∆Qi,c = Qti (xi ) − Qc (xi ), ∆Bi,c = Bti − Bc ,
∆Li,c = Lti (xi ) − Lc (xi ), (13) ∆bi,c = bti − bc . (14)
Then the pairwise logit margin is the affine function Mi,c (α, β, η) = α∆Qi,c + β∆Li,c + η∆Bi,c + ∆bi,c . (15)
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
5
TABLE I M AIN NOTATION FOR THE BINARY GEOMETRIC FORMULATION .
Symbol +
D ,D yj (x) Q(x) H(x) Lc (x) Hc (x) B Φ(x) S± C± K m(θ) ρ(θ)
−
Meaning positive and negative target calibration sets induced by original ReLU decisions fixed pre-activation of hidden Punit j weighted quadratic statistic j aj yj (x)2 P weighted affine statistic j aj yj (x) + b P multiclass bias-free statistic j ac,j yj (x) multiclass affine statistic Lc (x) + bc (not lifted in MC-QP) P output-weight sum j aj binary quadratic lift (Q(x), H(x))⊤ ∈ R2 lifted point clouds {Φ(x) : x ∈ D± } convex hulls conv(S ± ) difference hull C + − C − directional decision margin in direction θ = (α, β)⊤ normalized margin m(θ)/∥θ∥2
Equivalently, since ∆Li,c = ∆Hi,c − ∆bi,c , Mi,c = α∆Qi,c + β∆Hi,c + (1 − β)∆bi,c + η∆Bi,c . (16) The homogeneous multiclass optimization in Section IV uses the bias-free feature ∆Li,c in (15). This avoids doublecounting the output bias: if one instead stores ∆Hi,c inside the lifted vector, the last coordinate must be (λ − β̃)∆bi,c rather than λ∆bi,c , where β̃ is the homogeneous coordinate corresponding to β in Section IV. We therefore use (15) throughout the QPs and the implementation. The multiclass exact condition is a finite set of affine inequalities in (α, β, η). Once these inequalities are infeasible, the soft-margin formulation below is a convex surrogate for high agreement, not an exact calibration-lossless certificate. IV. C ONVEX -G EOMETRIC T HEORY A. Binary exact replacement Let S + = {Φ(x) : x ∈ D+ },
S − = {Φ(x) : x ∈ D− },
(17)
and let C + = conv(S + ), C − = conv(S − ). For θ = (α, β)⊤ define the directional margin m(θ) = min+ θ⊤ u − max− θ⊤ v. u∈C
v∈C
(18)
Theorem 1 (Exact binary replacement). Assume that both D+ and D− are nonempty and that the deployment threshold may be chosen after replacement. A shared quadratic replacement q(u; α, β, η) is calibration-lossless for the binary target split on Dcal if and only if there exists θ = (α, β) ̸= 0 such that m(θ) > 0. The following five conditions are equivalent: 1) there exists θ ̸= 0 with m(θ) > 0; 2) C + and C − admit a positive-margin hyperplane separator, i.e., there exist θ ̸= 0 and t ∈ R such that min θ⊤ u > t > max− θ⊤ v;
u∈C +
v∈C
(19)
3) the lifted calibration sets S + and S − are positive-margin separable;
Fig. 1. Binary post-training quadratic replacement as positive-margin hyperplane separation in the lifted plane. Calibration-lossless binary replacement is possible iff the positive and negative convex hulls of Φ(x) = (Q(x), H(x)) admit a positive-margin hyperplane separator. The maximum-margin direction θb∗ = (u∗ −v ∗ )/∥u∗ −v ∗ ∥2 is the unit vector along the closest-pair segment (u∗ , v ∗ ), and m∗ = ∥u∗ −v ∗ ∥2 = dist(C + , C − ) is the optimal directional margin.
4) C + ∩ C − = ∅; 5) 0 ∈ / K := C + − C − . Theorem 1 gives both a positive and a negative answer on the calibration set. If the hulls are disjoint, a calibrationlossless post-training quadratic replacement exists. If the hulls intersect, no choice of (α, β, η) can separate all positive and negative target calibration decisions under the shared quadratic replacement family, even if a post-replacement threshold is allowed. The positive-margin separation equivalences are standard; the contribution is the reduction of a trained ReLUreplacement problem to this two-dimensional condition. Theorem 1 assumes the deployment threshold may be chosen after replacement; preserving the original zero threshold is a strictly stronger requirement, handled constructively in the fixed-zero result below (Eq. (22)), and the reported binary feasibility logs already enforce it. The condition is low-dimensional but not weak. The two coordinates Q(x) and H(x) are not hand-designed features; they are exactly the two sample-dependent statistics through which a shared quadratic can affect the binary score once the trained affine head is fixed. Theorem 1 therefore characterizes every possible post-training shared quadratic replacement for this binary layer: overlapping lifted hulls make every affine separator fail on some positive–negative convex combination, while disjoint hulls yield a valid quadratic direction. Figure 1 illustrates this binary geometry: a high-dimensional hidden layer, once the trained output weights are fixed, reduces to two planar statistics whose hulls decide replacement feasibility. B. Constructive maximum-margin coefficients With K = C + −C − as in Theorem 1, m(θ) = minz∈K θ⊤ z. If 0 ∈ / K, let z ∗ ∈ arg min ∥z∥2 , z∈K
θb∗ = z ∗ /∥z ∗ ∥2 .
(20)
Theorem 2 (Maximum-margin direction). If C + ∩ C − = ∅, then θb∗ maximizes the normalized margin ρ(θ) = m(θ)/∥θ∥2 , and the optimal margin equals the distance between the two convex hulls: m(θ) max = dist(C + , C − ). (21) θ̸=0 ∥θ∥2
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
6
If (u∗ , v ∗ ) ∈ arg minu∈C + ,v∈C − ∥u − v∥2 , then θb∗ = (u∗ − v ∗ )/∥u∗ − v ∗ ∥2 . Because the hulls are planar, the construction is efficient. After computing the hidden pre-activations and the lifted points, the two convex hulls can be built in O(n log n) time; intersection testing and nearest-point computation are linear in the number of hull vertices. When deployment must use the original zero threshold rather than a selected post-replacement threshold, the constant Cβ,η must place the separated score interval around zero. If B ̸= 0, this can be done by selecting η=
−(ℓ+ + h− )/2 − (1 − β)b , B
(22)
where ℓ+ = minx∈D+ θ⊤ Φ(x) and h− = maxx∈D− θ⊤ Φ(x). If B = 0, η does not shift the binary scores, so zero-threshold preservation must be checked directly. C. Quantization-tolerance certificate The same margin also certifies robustness to coefficient quantization, which is essential because CKKS encodings have finite precision and deployment-time scale. Corollary 3 (Quantization tolerance). Let θb∗ be the unitnorm maximum-margin direction of Theorem 2, and let m∗ = m(θb∗ ) > 0. Define M=
max
x+ ∈D + , x− ∈D −
+
−
∥Φ(x ) − Φ(x )∥2 .
(23)
Here M = diam(K): since K = C + − C − is a polytope, maxz∈K ∥z∥2 is attained at a vertex,2 i.e., at a difference of extreme points of C ± , which are original calibration samples; hence the hull-level diameter coincides with the sample-pair maximum in (23). If a quantized coefficient vector b > 0 and all θb satisfies ∥θb − θb∗ ∥2 < m∗ /M , then m(θ) binary calibration decisions remain preserved. Quantitatively, b ≥ m∗ − M ∥θb − θb∗ ∥2 . m(θ) D. Relaxation beyond positive-margin feasibility The preceding subsections characterize when a trained ReLU layer admits calibration-lossless quadratic replacement: the lifted positive and negative convex hulls must admit a positive-margin separator. This condition can fail even when the original ReLU model is accurate—because the ReLU decision margins are small, because a few calibration points dominate the convex hulls, or because multiclass pairwise constraints are mutually inconsistent. Geometrically, a small fraction of misclassified or near-boundary calibration samples then produces lifted points that bring the two hulls into contact. An immediate remedy is to discard these samples and recompute the closest-pair construction; if only a few are removed, the problem reduces to the separable regime of Theorem 1. We avoid this hard-deletion route, because the fitted coefficients are calibration-set dependent: aggressive removal distorts the empirical distribution they are tuned to, and no a priori bound limits how many samples must be 2 A vertex-reduction lemma and the complete proofs of Theorems 1–6 and
Corollary 3 are given in the supplementary material.
discarded, especially when the failure reflects intrinsic margin degradation rather than a few outliers. Instead, we relax the geometric object itself, using two large-margin relaxations. Replacing standard convex hulls with reduced convex hulls (RCH) caps the maximum weight any single sample may carry in the convex combination, limiting the influence of extreme points without a discrete deletion set. As shown below, this relaxation admits an equivalent ν-SVM-type convex quadratic program and reduces to the closest-pair construction of Theorem 2 at µ = 1, so the family indexed by µ continuously extends the exact theory rather than replacing it. Reduced convex hull (RCH): The first is a reducedconvex-hull (RCH) relaxation [28], [29], a geometric largemargin relaxation that limits the influence of any single calibration point. For a finite set S = {zi }ni=1 and µ ∈ [1/n, 1], define nP o P RCHµ (S) = (24) i λi zi : i λi = 1, 0 ≤ λi ≤ µ . Replacing C + , C − by reduced hulls limits the effect of extreme points. For µ < 1, positive-margin separation of reduced hulls is a relaxation rather than a certificate of exact preservation on the full calibration set; after coefficients are returned, agreement with all original ReLU decisions is measured directly. Theorem 4 (Positive-margin RCH separation). For µ+ ∈ [1/n+ , 1], µ− ∈ [1/n− , 1], the reduced hulls Cµ++ = RCHµ+ (S + ), Cµ−− = RCHµ− (S − ) are nonempty, compact, and convex. The same five-fold equivalence of Theorem 1 holds with C ± replaced by Cµ±± , and the maximum-margin direction is again the normalized closest-point direction between the two reduced hulls. E. RCH duality and a ν-SVM-type quadratic program Although this reduced-hull separation is geometrically clean, in practice it is often more convenient to solve an equivalent convex QP. We make this precise. With S ± as in Theorem 4, consider the primal P P min± 12 ∥θ∥22 − ρ + c+ i ξi+ + c− j ξj− θ,t,ρ,ξ
s.t. θ⊤ zi+ − t ≥ ρ − ξi+ ,
ξi+ ≥ 0,
t − θ⊤ zj− ≥ ρ − ξj− ,
ξj− ≥ 0.
(P-RCH)
Theorem 5 (RCH–ν-SVM duality). The Lagrangian dual of (P-RCH), after the change of variables λi = 2ai , κj = 2bj , µ+ = 2c+ , µ− = 2c− , equals the two-hull closest-point problem 2 P P + − min i λi zi − j κj zj λ,κ 2 X X s.t. λi = 1, κj = 1, 0 ≤ λi ≤ µ+ , 0 ≤ κj ≤ µ− . i
j
(D-RCH) In particular, any optimal (θ∗ , t∗ , ρ∗ ) for (P-RCH) satisfies θ∗ ∝ z ∗ = u∗ − v ∗ where u∗ , v ∗ are the closest points of Cµ++ and Cµ−− . Theorem 5 unifies the geometric closest-point view of Theorem 4 with the large-margin QP view of (P-RCH); either form may be solved in practice.
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
7
Algorithm 1 Binary hard/RCH/soft cascade.
F. Multiclass: pairwise margin theory Theorem 6 (Multiclass exact preservation). Let ti denote the target class for sample xi . The replacement preserves all target top-1 decisions on Dcal if and only if Mi,c (α, β, η) > 0 for every i and every c ̸= ti , with Mi,c as in (15). The feasible set Tmc = {(α, β, η) : Γ > 0}, where Γ = mini,c̸=ti Mi,c , is an open convex polyhedron, possibly empty. Hard- and soft-margin formulations: Definition 3 (Multiclass pairwise lift). For each sample– competitor pair (i, c) with c ̸= ti , define the four-dimensional pairwise lift z̄i,c = (∆Qi,c , ∆Li,c , ∆Bi,c , ∆bi,c )⊤ .
(25)
This lift stores exactly the coefficients of the affine margin Mi,c (α, β, η) in (15). The last coordinate is the fixed outputbias difference, which is why the homogeneous formulation below uses a separate scale coordinate. Let θ̄ = (α̃, β̃, η̃, λ)⊤ ∈ R4 , where (α̃, β̃, η̃) are the homogeneous lifts of (α, β, η). For any λ > 0, ! β̃ η̃ α̃ , , . (26) θ̄⊤ z̄i,c = λ Mi,c λ λ λ Thus α = α̃/λ, β = β̃/λ, η = η̃/λ recovers the original replacement parameters. The hard-margin feasibility QP is min 21 ∥θ̄∥22 θ̄
s.t. θ̄⊤ z̄i,c ≥ 1 ∀i, c ̸= ti , λ ≥ 1.
(MC-H)
When (MC-H) is infeasible, we solve the soft-margin variant P min 12 ∥θ̄∥22 + C i ξi θ̄,ξ
s.t. θ̄⊤ z̄i,c ≥ 1 − ξi ∀i, c ̸= ti ,
(MC-S)
ξi ≥ 0, λ ≥ 1. Both (MC-H) and (MC-S) are convex QPs. The hard-margin problem is an exact feasibility test for multiclass calibrationlossless replacement under the shared quadratic family. The soft-margin problem is a surrogate that trades margin size against violations of the original ReLU target decisions. Implementation choices for solving these QPs at scale are described in Section V; each run records the regime, the minimum calibration margin or aggregate slack, and calibration/test agreement. V. A LGORITHMS , C OMPLEXITY, AND FHE C OST The coefficient search is an offline post-training procedure. It uses the trained ReLU model and a declared calibration set to compute the three shared quadratic coefficients; the encrypted online path then evaluates only the polynomialized network. The algorithms below summarize the binary and multiclass cascades used in Q UAD 4FHE. Complete implementation-level pseudocode, solver settings, and logging fields are provided in the supplementary material and the public repository.
Input: trained binary ReLU MLP; calibration set Dcal ; original ReLU decisions ti ∈ {+1, −1}; RCH cap grid M; optional soft-margin grid. Procedure: 1) Cache hidden pre-activations yj (xi ) and compute the binary lift Φi = (Qi , Hi ) from Definition 2. 2) Split lifted points into S + = {Φi : ti = +1} and S − = {Φi : ti = −1}. 3) Hard test. Compute the closest pair between conv(S + ) and conv(S − ). If their distance is positive, return the normalized closest-pair direction and the resulting quadratic coefficients with regime HARD. 4) RCH scan. Otherwise scan µ ∈ M and test positive-margin separation of RCHµ+ (S + ) and RCHµ− (S − ), where µ± = max{µ, 1/n± }. Return the first selected positive-margin RCH solution and measure full calibration agreement. 5) Soft fallback. If no RCH cap separates, solve the binary softmargin fallback and select coefficients by calibration agreement, slack, and margin diagnostics. Output: (α, β, η); regime; margin/slack statistics; calibration agreement; mismatch indices.
Algorithm 2 Multiclass hard/soft-margin coefficient construction. Input: trained K-class ReLU MLP head; calibration set Dcal ; original ReLU top-1 targets ti ; soft-margin grid C. Procedure: 1) Cache hidden pre-activations and compute class-wise statistics Qi,c , Li,c , Bc and output-bias terms. 2) For each sample–competitor pair (i, c) with c ̸= ti , form or stream the pairwise lift z̄i,c from Definition 3. 3) Hard QP. Attempt the hard-margin QP (MC-H). For large constraint matrices, use an active-set/cutting-plane loop: solve on an active subset, sweep all margins, add the worst violated rows, and repeat. 4) Hard recovery. If the hard problem is feasible with positive margins, recover (α, β, η) from the homogeneous variables and return regime HARD. 5) Soft fallback. Otherwise solve the soft-margin problem (MC-S) over C ∈ C, using warm starts or the analytically eliminated persample slacks. Select C by ReLU-decision agreement, aggregate slack, worst margin, and coefficient norm. Output: (α, β, η); selected C if applicable; slack trace; margins; calibration/test agreement; mismatch counts.
A. Binary complexity For a dense first layer, evaluating hidden pre-activations from raw inputs costs O(nmd) for n calibration samples, input dimension d, and hidden width m. Once the pre-activations are cached, computing Qi , Hi costs O(nm) and the lifted points lie in R2 . We distinguish a structural result from the executed pipeline. The O(n log n) bound is structural: it characterizes the intrinsic difficulty of the hard positive-margin binary case, since the planar hulls, their intersection, and the closest pair are all computable in O(n log n). The shipped implementation, however, does not run this planar-hull routine; it uses a shared convex-QP back-end for the hard boundary case, the RCH scan, and the soft fallback, an engineering choice that keeps the HARD, RCH, and SOFT branches numerically consistent. For an RCH grid of size Gµ , the offline cost is that of up to Gµ two-hull closest-point QPs in two lifted dimensions.
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
8
TABLE II C OEFFICIENT- CONSTRUCTION REGIMES REPORTED BY Q UAD 4FHE. T HE OPTIMIZATION DIMENSION IS THE NUMBER OF REPLACEMENT COEFFICIENTS , NOT THE NUMBER OF NETWORK WEIGHTS .
Regime
Condition checked
Output meaning
HARD (binary)
C + ∩C − = ∅ in R2
HARD (multiclass)
all pairwise affine margins feasible reduced hulls admit a positivemargin separator hard problem infeasible
exact calibration-lossless coefficients; O(n log n) after lift exact positive-margin feasible coefficients
RCH (µ)
SOFT (C)
relaxed coefficients; fullset agreement measured afterward slack-controlled coefficients for high empirical agreement
No RCH or soft-margin optimization is part of the encrypted inference circuit. B. Multiclass and relaxed complexity For a K-class head, computing the class-wise quadratic and linear statistics from cached hidden pre-activations costs O(nmK). Each sample contributes K − 1 pairwise margin constraints, so a materialized multiclass constraint matrix has O(n(K − 1)) rows and four columns in the homogeneous formulation. The exact multiclass problem is low-dimensional in the replacement coefficients but may contain millions of constraints; for this reason the solver is run offline and can stream constraints or use active sets. In the hard-margin branch, a direct QP solve is used for moderate constraint counts. When the number of pairwise rows exceeds the implementation threshold, Q UAD 4FHE uses the active-set/cutting-plane loop in Algorithm 2. Each outer iteration solves a small QP on the current active set and then performs one full margin sweep costing O(n(K − 1)) arithmetic operations in the four-dimensional lift. In the softmargin branch, the per-sample slacks can be eliminated as ξi (θ) = max{0, 1 − min Mi,c (θ)}, c̸=ti
(27)
so each objective and subgradient evaluation over a fixed C again requires a full pairwise margin sweep. The C grid is selected by agreement with the original ReLU decisions on the calibration set, then by aggregate slack, worst margin, and coefficient norm. These costs are offline fitting costs; the online encrypted model remains the same degree-2 arithmetic circuit for all regimes. C. Encrypted arithmetic cost For each encrypted pre-activation u, Q UAD 4FHE evaluates q(u) = αu2 + βu + η. The activation module therefore uses one ciphertext-ciphertext multiplication to form u2 , followed by plaintext multiplications, additions, and the required CKKS rescaling/relinearization steps. In contrast, a degree-d fixedinterval polynomial requires a deeper evaluation schedule under Horner, Paterson–Stockmeyer, or related strategies, and
generally consumes more multiplication levels and coefficientmodulus budget as d increases. The advantage of Q UAD 4FHE is not that a quadratic is a universally better pointwise approximation to ReLU. Its advantage is that the quadratic coefficients are chosen against the trained classifier’s calibration logit-ordering constraints while preserving the circuit shape of a degree-2 activation. A shorter multiplicative path can use a shorter coefficientmodulus chain and, within a declared CKKS parameter-search grid, may allow a lower-latency configuration. Section VIII reports this effect relative to Remez-7; whereas against schemes that already fit in the same depth-4 circuit, latency is similar, and the relevant comparison is accuracy at the same encrypted depth. VI. E XPERIMENTAL M ETHODOLOGY A. Models and datasets We evaluate two model families. Family A: single-hidden-layer MLP on raw task features.: We test on 8 datasets covering tabular, vision, and text modalities: AG News, Breast Cancer Wisconsin (BWC), CIFAR-10, CIFAR-100, Diabetes, Otto Group, Shuttle, and SST-5. Family B: frozen backbone + single-hidden-layer MLP head.: We use DINOv2 features [33] on CIFAR-100, FGVCAircraft, StanfordCars, and Tiny-ImageNet, and Qwen3Embedding-0.6B features [34] on SIB-200, MASSIVE, and Banking77. B. Splits and coefficient-fitting protocol For full-train experiments, the model-training, validation, and testing proportions are 60%, 20%, and 20% when a fixed public split is not imposed. CIFAR-10, CIFAR-100, and StanfordCars use their official train/test partitions; only the available training side is subdivided when a validation or calibration subset is needed. Hidden widths m ∈ {64, 128, 256} are evaluated; the main tables report m = 256, which is also used for the ciphertext experiments. For small-pool experiments, the model itself is trained from a 50% training split, with 10% for validation and 20% for testing. The remaining 20% is reserved as a replacementfitting pool, and only 1%, 5%, 10%, or 20% of the full dataset is used to estimate the quadratic coefficients. Unless otherwise stated, these are single fixed stratified splits with seed 2026 rather than repeated random splits; the purpose is to diagnose calibration-pool size, not to estimate sampling variance. If a tiny stratified pool misses one or more classes, the run is reported as unavailable rather than forcing an illposed coefficient fit. This protocol models deployments where the trained network is available but the practitioner has only a small public or otherwise representative calibration pool rather than the full training data. All coefficient fits use original ReLU decisions as targets, and the resulting coefficients are fixed before plaintext and CKKS evaluation. Thus Q UAD 4FHE is evaluated as a posttraining agreement method rather than as model retraining.
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
C. Baselines We compare against Square, least-squares polynomial fits of degrees 2/3/5/7, Remez polynomials of degrees 2/3/5/7, Precise Approximation [20], and OLA [21]. The leastsquares baselines are fit to the scalar activation on a dense grid over the empirical min–max range of hidden pre-activations in the fitting split; the Remez baselines use the same interval with a dense-grid minimax/Remez routine and an LP minimax fallback. No validation tuning or percentile clipping is applied to these fixed-interval baselines, which keeps them reproducible without claiming every interval choice is globally optimal. OLA is evaluated as a Gaussian-weighted layerwise posttraining approximation with its configured degree/bandwidth sweep, and Precise uses its published composed approximation with the empirical B = max |y| scaling and clipping. The main plaintext tables report Square as the cheapest fixed polynomial, Remez-7 as a high-degree fixed-interval baseline, and OLA/Precise as strong post-training approximation baselines. We emphasize that OLA and Precise are competitive in plaintext accuracy, and on several tasks match or exceed the quadratic replacement; our claim is therefore not plaintextaccuracy superiority. The distinguishing property is encryptedcircuit depth. OLA and Precise attain their accuracy through higher-degree or composed polynomials whose best CKKS use requires schedule-specific composition, modulus-chain design, and Paterson–Stockmeyer-style evaluation, all of which raise multiplicative depth. The thesis of this paper is sharper and narrower: a decision-aware degree-2 replacement reaches accuracy comparable to these stronger baselines while fitting in the lowest encrypted depth we evaluate. Accordingly, the ciphertext tables include Square and Remez-2/3/5/7 as depthmatched fixed-polynomial circuits; we do not reimplement OLA/Precise in CKKS, since their value lies in approximation quality rather than in the low-depth regime that this paper targets. D. Metrics For plaintext experiments we report top-1 accuracy against ground truth, macro-F1, and agreement of Q UAD 4FHE with the original ReLU model. We also record the returned regime, exactness on the calibration set, margin/slack diagnostics, calibration/test agreement, coefficients, and any coefficient quantization. For CKKS experiments we report plaintext and ciphertext top-1 accuracy, ciphertext–plaintext mismatch counts, logit errors, CKKS parameters (N, depth, log Q), packing/batch size, and amortized latency per sample. All evaluated ciphertext configurations are leveled CKKS evaluations without bootstrapping. E. Encrypted-inference threat model Our FHE experiments use the standard semi-honest CKKS encrypted-inference setting. The client owns the sensitive input or feature vector and the CKKS secret key; the server evaluates a public or server-owned classifier with plaintext-encoded weights on ciphertexts; and the client decrypts the returned logits. Security is therefore the usual semantic security of
9
leveled CKKS in this semi-honest setting. We do not claim model confidentiality against the client, malicious-security guarantees, side-channel protection, or robustness against malformed ciphertexts. For raw-feature MLP tasks, the encrypted value is the task feature vector. For DINOv2 and Qwen3 experiments, the evaluated system is encrypted MLP-head inference on encrypted features. Privacy for raw images or text therefore requires client-side feature extraction before encryption; otherwise FHE protects only the head computation on the provided features. F. Relaxation hyperparameters The exact hard-margin problem is attempted first. For binary fits where the positive-margin condition fails, we then scan the RCH cap on the fixed implementation grid µbase ∈ {0.80, 0.60, 0.40, 0.30, 0.20, 0.15, 0.10, 0.08, 0.05, 0.03, 0.02, 0.01}.
(28)
For the two classes we use µ± = max{µbase , 1/n± }, so that the reduced hulls are nonempty even on small calibration sets. We select the largest base cap yielding a positive reducedhull margin, with ties resolved by validation agreement and then normalized margin; this keeps the relaxation as close as possible to the exact hull while suppressing points that dominate the infeasibility certificate. The Diabetes setting in Table IV is selected by this rule, giving µbase = 0.01. For multiclass soft-margin fits we use the logarithmic grid C ∈ {10−3 , 10−2 , 10−1 , 1, 10, 102 }.
(29)
The selected C maximizes calibration agreement with the original PReLU decisions; ties are broken by smaller aggregate slack i ξi , then larger worst pairwise margin, then smaller homogeneous coefficient norm. We report C, the slack-positive P sample count, i ξi , and the soft-selection trace whenever SOFT(C) is used. VII. P LAINTEXT R ESULTS A. Interpreting the regime diagnostics Table V is central to interpreting the experiments. Only BWC is in the theorem-backed HARD exact regime in the full-train main runs; Diabetes requires the RCH relaxation; and every full-train multiclass benchmark is in SOFT(C). The multiclass accuracy numbers should therefore not be read as evidence that exact calibration-lossless quadratic replacement is generally feasible; they show instead that the soft-margin surrogate can often recover high empirical agreement despite negative worst-case pairwise margins. The calibration/test columns quantify the extrapolation gap: on many tasks the two agreements are close, supporting the empirical use of the calibration pool. B. Single-hidden-layer MLPs Table III reports the main MLP results at width 256. Q UAD 4FHE is the best (or tied for best) non-ReLU replacement on 4 of 6 multiclass tasks (AG News, CIFAR-10, CIFAR100, SST-5), and matches or exceeds the original ReLU model
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
10
TABLE III F ULL - TRAIN SINGLE - HIDDEN - LAYER MLP RESULTS AT WIDTH m = 256. VALUES ARE TOP -1 ACCURACIES IN %; “AGR .” IS THE AGREEMENT OF Q UAD 4FHE WITH THE ORIGINAL R E LU MODEL ON THE TEST SPLIT, AND “MF1” IS THE MACRO -F1 OF Q UAD 4FHE. B EST NON -R E LU VALUE PER ROW IS IN BOLD ; SECOND - BEST IS UNDERLINED .
Dataset
ReLU
Sq.
Rmz-7
OLA
Prec.
Quad.
Agr.
MF1
AG News CIFAR-10 CIFAR-100 Otto Shuttle SST-5
89.83 52.14 20.53 79.71 99.69 36.43
73.30 35.84 12.03 38.53 82.56 29.19
89.73 49.68 18.95 71.87 84.21 36.33
89.80 52.25 20.52 77.74 88.55 36.43
89.82 52.13 20.53 79.72 99.33 36.43
89.95 52.64 20.71 76.05 97.04 36.43
98.64 87.41 82.29 87.05 97.30 92.31
89.94 52.31 19.53 69.36 49.32 31.41
TABLE IV B INARY FEASIBILITY / COEFFICIENT SUMMARY AT m = 256 FROM THE FULL - TRAIN LOGS . “M ARGIN ” IS THE EMPIRICAL DECISION MARGIN ON THE TRAINING SPLIT. RCH (µ) MEANS THE REDUCED - CONVEX - HULL REGIME WITH CAP PARAMETER µ. B OTH ROWS USE THE FIXED - ZERO THRESHOLD AND RECORD CALIBRATION / TEST AGREEMENT IN TABLE V.
Dataset BWC Diabetes
Regime
α
β
η Margin
0.397 0.918 +0.771 RCH (µ=0.010) 0.110 0.994 −5.202 HARD
only a small fraction of the dataset is available for coefficient fitting; frozen-head settings are typically more stable than rawfeature MLPs. These results are calibration-pool sensitivity diagnostics under one stratified split rather than repeated-seed statistical claims.
0.548 0.452
on all four (per-task gaps Quad−ReLU range from 0.00 to +0.50 pp). By contrast, on Otto, exact multiclass preservation is infeasible and the soft-margin relaxation loses 3.66 pp; on Shuttle the corresponding gap is 2.65 pp. Even in these two harder cases, Q UAD 4FHE substantially exceeds Square (by 37.52 pp on Otto and 14.48 pp on Shuttle) and Remez-7 (by 4.18 pp on Otto, 12.83 pp on Shuttle). OLA and Precise are strong post-training approximation baselines; their near-ReLU accuracy on several tasks highlights that the comparison is not merely between low and high polynomial degree, but between interval-level activation approximation and task-level decision agreement. BWC and Diabetes are reported separately in Table IV for coefficient interpretability; their diagnostics also appear in Table V. Two rows require careful reading. On SST-5, Quad and ReLU have nearly identical top-1 accuracy even though test agreement is only 92.31%; this is possible because changed predictions can include both newly correct and newly incorrect samples. Agreement is therefore the appropriate decisionagreement metric, not accuracy alone. On Shuttle, top-1 accuracy remains high because the dataset is highly imbalanced, but the Quad macro-F1 is low; top-1 therefore overstates minority-class behavior. We report macro-F1 in the table and do not claim that Quad is minority-class preserving on Shuttle. The binary feasibility logs in Table IV illustrate the role of the exact theorem (Theorem 1). BWC is hard-margin feasible at all widths; therefore the replacement parameters come from the exact geometric condition. Diabetes is not hardmargin feasible under the full-train logs but obtains a positivemargin RCH solution after the RCH relaxation (Theorem 4) at µ = 0.01, which is consistent with the presence of noisy or influential extreme points in the diabetes patient features. C. Small-pool replacement Table VI reports the small-pool ablation. Across this fixed split, the quadratic replacement remains usable even when
D. Frozen representations with MLP heads Table VII evaluates the head-only frozen-representation extension. Q UAD 4FHE is within 0.41 pp of the original ReLU head on 6 of 7 tasks and within 1.15 pp on all 7, an average absolute gap of 0.33 pp. OLA and Precise are also close to the ReLU heads here, while Square remains much less stable. On DINOv2/StanfordCars Q UAD 4FHE is the best nonReLU replacement, exceeding the ReLU head by +0.19 pp. These results confirm that the coefficient construction is not tied to raw-input MLPs; it applies whenever a fixed feature extractor is followed by a single-hidden-layer ReLU head and an affine classifier. The privacy claim for DINOv2/Qwen3 remains head-only encrypted inference on encrypted features, not full encrypted image/text inference. VIII. C IPHERTEXT R ESULTS AND A NALYSIS We report CKKS inference on three representative tasks: Otto (tabular MLP), DINOv2/FGVC-Aircraft, and Qwen3/MASSIVE. A. CKKS implementation and parameter search The ciphertext implementation uses Microsoft SEAL 4.1 with CKKS on an Intel Xeon Gold 6530 and 32 threads for the main latency runs. The server evaluates plaintext weights on ciphertexts, the client holds the secret key, and no bootstrapping is used. For the main log2 ∆ = 40 runs, the coefficient-modulus chains are {60, 40, 40, 40, 40, 60} (log Q = 280), {60, 40, 40, 40, 40, 40, 60} (log Q = 320), {60, 40, 40, 40, 40, 40, 40, 60} (log Q = 360), (30) and the precision sweep log2 ∆ ∈ {25, 30, 35, 40, 45} adjusts the middle primes consistently. All configurations instantiate the SEAL context with sec_level_type::tc128 and pass the realized-level check, with the total modulus kept below SEAL’s 128-bit maximum for each ring degree; N = 215 is used in the larger-resource configurations. Packing interleaves B = slot_count/m samples per hidden coordinate (B = 32 at N = 214 , B = 64 at depth 4 : depth 5 : depth 6 :
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
11
TABLE V D ECISION - AGREEMENT AND REGIME DIAGNOSTICS FOR THE FULL - TRAIN WIDTH -256 RUNS . nc IS THE CALIBRATION SIZE AND |P| THE NUMBER OF MULTICLASS PAIRWISE CONSTRAINTS ( BINARY ROWS HAVE NONE ). “C AL ./T EST AGR .” ARE AGREEMENT WITH THE ORIGINAL R E LU MODEL , NOT GROUND - TRUTH ACCURACY. “N ORM . MARG .” IS THE NORMALIZED EMPIRICAL DECISION MARGIN ; FOR P SOFT ROWS NEGATIVE VALUES ARE ACCOMPANIED BY THE PER - SAMPLE SLACK STATISTICS #ξi >0 AND i ξi . |P| Exact Cal. Agr. Test Agr. Cal. mis Test mis Norm. marg. #ξi >0 (%) (%)
Regime
nc
BWC Diabetes
HARD
455 7630
– –
Y N
100.00 99.38
100.00 99.48
0 47
0 10
0.55 0.45
AG News CIFAR-10 CIFAR-100 Otto Shuttle SST-5
SOFT(100.0)
96000 50000 SOFT(0.1) 50000 SOFT(0.001) 49502 SOFT(0.001) 46400 SOFT(1.0) 9645
288k 450k 4.95M 396k 278k 39k
N N N N N N
98.40 88.74 83.01 86.13 97.26 92.63
98.64 87.41 82.29 87.05 97.30 92.31
1535 5630 8494 6864 1272 711
327 1259 1771 1603 313 170
-3.93 -5.85 -10.89 -107.71 -549.98 -0.57
DINOv2/CIFAR-100 DINOv2/FGVC DINOv2/Cars DINOv2/Tiny
SOFT(1.0)
48000 4.75M 8000 792k SOFT(10.0) 12948 2.52M SOFT(100.0) 88000 17.51M
N N N N
99.14 97.21 98.49 98.60
98.76 94.55 95.74 98.47
411 223 196 1234
149 109 138 337
-1.64 -0.51 -1.93 -0.98
969 531 469 2905
967.0 526.1 470.6 2906.0
SOFT(10.0)
N N N
99.42 98.58 99.19
99.26 98.69 98.47
28 1152 81
9 233 47
-0.80 -0.89 -1.64
73 2822 247
72.2 2819.1 218.3
RCH (0.010)
SOFT(1.0)
Qwen3/SIB-200 Qwen3/MASSIVE Qwen3/Banking77
SOFT(10.0)
SOFT(10.0) SOFT(0.1)
4800 81282 9993
29k 4.80M 759k
TABLE VI S MALL - POOL DETAILED RESULTS AT WIDTH m = 256. E NTRIES ARE Q UAD 4FHE TOP -1 ACCURACY IN %; THE RIGHTMOST COLUMN IS THE ORIGINAL R E LU ACCURACY IN THE SAME SPLIT. A LL ROWS USE ONE FIXED STRATIFIED SPLIT WITH SEED 2026. “–” MARKS FITS WHERE THE REQUESTED POOL IS UNUSABLE BECAUSE CLASS IMBALANCE LEAVES AT LEAST ONE CLASS ABSENT ( E . G ., BWC AND DINOV 2/S TANFORD C ARS AT 1%).
1%
5%
10%
20%
ReLU
Single-hidden-layer MLP AG News 89.95 BWC – CIFAR-10 49.38 CIFAR-100 18.66 Diabetes 95.07 Otto 76.46 Shuttle 98.72 SST-5 34.30
90.09 91.23 49.45 18.67 98.64 76.39 98.64 34.48
90.15 98.25 49.58 18.65 98.79 76.28 96.22 34.66
90.12 96.49 49.84 18.65 98.43 76.51 96.91 34.43
89.99 99.12 50.32 18.86 98.85 79.72 99.74 34.71
DINOv2 backbone + MLP head DINOv2/CIFAR-100 89.52 89.42 DINOv2/FGVC 76.60 76.40 DINOv2/Cars – 85.51 DINOv2/Tiny 86.23 86.20
89.38 76.60 85.63 86.20
89.38 76.65 85.60 86.21
89.41 77.75 85.70 86.20
Task
P
Task
Qwen3 backbone + MLP head Qwen3/SIB-200 93.86 94.44 94.44 94.44 94.77 Qwen3/MASSIVE 89.40 89.45 89.49 89.42 89.90 Qwen3/Banking77 90.44 90.86 90.90 90.74 90.63
N = 215 , m = 256); features larger than m are chunked, each chunk evaluated by a baby-step/giant-step diagonal matvec, and the chunk results accumulated. Latencies are amortized per-sample (sequential-equivalent); Table VIII reports perbatch operation counts. A configuration is called minimum feasible only relative to the explicit search grid (N, d, log Q) ∈ {(214 , 4, 280), (214 , 5, 320), (215 , 5, 320), (215 , 6, 360)}.
(31)
A scheme is feasible on a row if its compile-time depth does not exceed the available rescale budget, inference completes
i ξi
– –
– –
3800 3800.2 14337 14328.1 20762 20636.8 17702 17450.7 6081 5822.9 1884 1764.0
without bootstrapping, and the ciphertext top-1 predictions match the plaintext polynomialized top-1 predictions on every evaluated test sample. Thus “HE–Plain=0” below means zero top-1 mismatches, not zero numerical logit error; max/mean logit errors are logged separately. B. Minimum feasible CKKS configuration Table IX reports each scheme’s minimum feasible CKKS configuration within our declared search grid on the three tasks. Across all three tasks, Q UAD 4FHE, Square, and Remez2/Remez-3 remain feasible at N = 214 , depth 4, and log Q = 280, whereas Remez-5 and Remez-7 require depth 5 at log Q = 320. The phrase “minimum feasible” is therefore relative to this grid, scale policy, packing strategy, and accuracy criterion; it is not a proof of global optimality over all CKKS schedules. The latency comparison should be read in two layers. First, at the same depth-4 configuration, Q UAD 4FHE has latency comparable to Remez-2/3 (e.g., Otto: 7.43 ms vs 7.30– 7.42 ms), so the quadratic is not intrinsically much faster than every other low-degree circuit; its advantage is that the decision-aware quadratic retains higher task accuracy than the low-degree interval fits while still fitting in the lowest evaluated depth. Second, relative to Remez-7, which often offers the strongest fixed-interval accuracy among the CKKS baselines but requires depth 5, the activation-block speedup is 3.7–4.1× across the three tasks and the end-to-end speedup is 1.18– 1.68× (full numbers in Table IX); Q UAD 4FHE leads Remez7 by +4.18 pp on Otto, is within 0.50 pp on DINOv2/FGVC, and matches Remez-7 within 0.04 pp on Qwen3/MASSIVE. C. Precision sweep Figure 2 shows the HE accuracy of all six schemes as the CKKS scaling factor log2 ∆ ranges from 25 to 45. Accuracy is essentially flat across the precision range for all schemes on all three tasks, confirming that within the evaluated CKKS precision the polynomialized circuits are numerically stable.
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
12
TABLE VII F ROZEN BACKBONE + SINGLE - HIDDEN - LAYER MLP HEAD AT WIDTH m = 256. VALUES ARE TOP -1 ACCURACIES IN %; “AGR .” IS Q UAD 4FHE AGREEMENT WITH THE ORIGINAL R E LU HEAD .
Task
ReLU
Sq.
Rmz-7
OLA
Prec.
Quad.
Agr.
DINOv2/CIFAR-100 DINOv2/FGVC DINOv2/Cars DINOv2/Tiny Qwen3/SIB-200 Qwen3/MASSIVE Qwen3/Banking77
89.53 79.40 87.30 86.48 89.30 85.56 91.91
78.03 25.50 36.92 70.75 52.53 52.40 71.07
89.59 78.75 87.33 86.54 89.79 85.49 91.68
89.56 79.40 87.33 86.46 89.30 85.56 91.84
89.53 79.40 87.30 86.47 89.30 85.56 91.91
89.57 78.25 87.49 86.52 89.71 85.45 91.55
98.76 94.55 95.74 98.47 99.26 98.69 98.47
Average |Quad − ReLU| gap across the 7 tasks: 0.33 pp. TABLE VIII T HEORETICAL CKKS OPERATION COUNTS PER ENCRYPTED BATCH FOR THE SELECTED FULL - SWEEP CONFIGURATIONS . “ CT- CT ” AND “ CT- PT ” ARE CIPHERTEXT- CIPHERTEXT AND CIPHERTEXT- PLAINTEXT MULTIPLICATIONS . ROTATIONS INCLUDE BOTH BSGS INPUT ROTATIONS AND OUTPUT- TREE REDUCTIONS . Task
Scheme
Otto Otto FGVC FGVC MASSIVE MASSIVE
Quad Remez-7 Quad Remez-7 Quad Remez-7
Enc ct-ct 1 1 3 3 4 4
ct-pt Rot. Rescale
2 139 5 141 2 870 5 872 2 1086 5 1088
93 93 890 890 600 600
14 19 105 110 65 70
rather than generic exact preservation. Repeated-seed statistics, per-class F1, and low-margin/outlier sensitivity remain useful follow-up diagnostics. The encrypted experiments compare depth-matched fixedpolynomial circuits under one packing and modulussearch framework, isolating the effect of multiplicative depth. Optimized CKKS schedules for OLA/Precise, polynomial-only training, bootstrapped deeper networks, and lookup/comparison-based protocols are outside this controlled comparison. The DINOv2 and Qwen3 experiments are encrypted MLP-head inference on encrypted features; they do not protect raw images or text unless feature extraction is performed on the client. X. C ONCLUSION
Fig. 2. HE top-1 accuracy versus the CKKS scaling factor log2 ∆ on the three encrypted tasks.
The relative ordering between schemes is preserved at every precision: Q UAD 4FHE leads on Otto, while Remez-7 has a small plaintext-level edge on FGVC and MASSIVE at the cost of the depth-5 circuit. The single visible degradation event in the sweep is the Remez-7 dip on MASSIVE at log2 ∆ = 25, consistent with high-degree polynomials being more sensitive to large-magnitude pre-activations. IX. D ISCUSSION AND L IMITATIONS The exact theorems certify calibration-set preservation only. Table V shows that exact feasibility is rare in the full-train benchmarks: BWC falls into the HARD regime, Diabetes uses RCH, and multiclass tasks use SOFT(C). The multiclass results are therefore evidence for a practical decision-aware surrogate
We presented a decision-aware framework for HE-friendly quadratic ReLU replacement, implemented in the open-source Q UAD 4FHE library. The framework shifts activation replacement from module-local approximation fidelity to calibrationset logit-ordering agreement. For binary single-hidden-layer MLPs, exact calibration-lossless preservation is equivalent to positive-margin hyperplane separation of two lifted convex hulls, yielding constructive coefficients in O(n log n) time and a quantization certificate; for harder binary and multiclass settings, RCH and soft-margin relaxations provide practical surrogates. CKKS experiments confirm ciphertext accuracies matching plaintext polynomial accuracies and 1.18–1.68× end-to-end speedups over Remez-7. R EFERENCES [1] R. L. Rivest, L. Adleman, and M. L. Dertouzos, “On data banks and privacy homomorphisms,” in Foundations of Secure Computation, 1978, pp. 169–179. [2] C. Gentry, “A fully homomorphic encryption scheme,” Ph.D. dissertation, Stanford University, 2009. [3] J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in Proc. ASIACRYPT, 2017, pp. 409–437. [4] R. Bost, R. A. Popa, S. Tu, and S. Goldwasser, “Machine learning classification over encrypted data,” in Proc. NDSS, 2015. [5] P. Mohassel and Y. Zhang, “SecureML: A system for scalable privacy-preserving machine learning,” in Proc. IEEE S&P, 2017, pp. 19–38. [6] J. Liu, M. Juuti, Y. Lu, and N. Asokan, “Oblivious neural network predictions via MiniONN transformations,” in Proc. ACM CCS, 2017, pp. 619–631. [7] N. Dowlin, R. Gilad-Bachrach, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, “CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy,” in Proc. ICML, 2016, pp. 201–210. [8] A. Brutzkus, R. Gilad-Bachrach, and O. Elisha, “Low latency privacy preserving inference,” in Proc. ICML, 2019, pp. 812–821. [9] R. Dathathri et al., “CHET: an optimizing compiler for fully-homomorphic neuralnetwork inferencing,” in Proc. ACM PLDI, 2019, pp. 142–156. [10] R. Dathathri et al., “EVA: An encrypted vector arithmetic language and compiler for efficient homomorphic computation,” in Proc. ACM PLDI, 2020, pp. 546–561.
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
13
TABLE IX M INIMUM FEASIBLE CKKS CONFIGURATION FROM THE CIPHERTEXT LOGS (Q UAD 4FHE ROWS ARE SHADED ). PH-mis IS THE INTEGER NUMBER OF TOP -1 MISMATCHES BETWEEN PLAINTEXT POLYNOMIAL EVALUATION AND CKKS EVALUATION ON THE EVALUATED TEST SET; IT IS ZERO FOR EVERY SELECTED ROW, SO A SINGLE Acc. COLUMN REPORTS BOTH PLAINTEXT AND CIPHERTEXT ACCURACY. Lat-Act IS THE PER - SAMPLE COST OF THE POLYNOMIAL - EVALUATION BLOCK (P OWERS + ACTIVATION ); Lat-Tot IS THE END - TO - END PER - SAMPLE LATENCY. Spd-Act AND Spd-Tot ARE THE CORRESPONDING SPEEDUPS VERSUS R EMEZ -7. L ATENCIES ARE AMORTIZED PER - SAMPLE MILLISECONDS ( SEQUENTIAL - EQUIVALENT, 32- THREAD FULL SWEEP ). Task Activation Otto / MLP Q UAD 4FHE Square Remez-2 Remez-3 Remez-5 Remez-7
Deg. Acc. (%) PH-mis Depth log Q Lat-Act Lat-Tot Spd-Act Spd-Tot (ms) (ms) vs Rmz-7 vs Rmz-7 76.05 38.53 60.59 61.10 68.63 71.87
0 0 0 0 0 0
4 4 4 4 5 5
280 280 280 280 320 320
0.219 0.180 0.210 0.309 0.670 0.826
7.43 7.30 7.30 7.42 9.10 9.27
3.77× 4.59× 3.93× 2.67× 1.23× 1.00×
1.25× 1.27× 1.27× 1.25× 1.02× 1.00×
DINOv2 / FGVC-Aircraft Q UAD 4FHE 2 78.25 Square 2 25.50 Remez-2 2 73.80 Remez-3 3 75.70 Remez-5 5 78.10 Remez-7 7 78.75
0 0 0 0 0 0
4 4 4 4 5 5
280 280 280 280 320 320
0.222 0.167 0.202 0.314 0.771 0.912
46.81 46.39 46.49 46.53 79.24 78.83
4.11× 5.46× 4.51× 2.90× 1.18× 1.00×
1.68× 1.70× 1.70× 1.69× 0.99× 1.00×
Qwen3 / MASSIVE Q UAD 4FHE 2 Square 2 Remez-2 2 Remez-3 3 Remez-5 5 Remez-7 7
0 0 0 0 0 0
4 4 4 4 5 5
280 280 280 280 320 320
0.231 0.186 0.217 0.318 0.711 0.863
50.05 49.68 49.35 49.55 58.75 58.96
3.74× 4.64× 3.98× 2.71× 1.21× 1.00×
1.18× 1.19× 1.19× 1.19× 1.00× 1.00×
2 2 2 3 5 7
85.45 52.40 83.51 85.14 85.40 85.49
[11] F. Boemer, A. Costache, R. Cammarota, and C. Wierzynski, “nGraph-HE2: A high-throughput framework for neural network inference on encrypted data,” in Proc. WAHC, 2019, pp. 45–56. [12] C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, “GAZELLE: A low latency framework for secure neural network inference,” in Proc. USENIX Security, 2018, pp. 1651–1669. [13] P. Mishra et al., “DELPHI: A cryptographic inference service for neural networks,” in Proc. USENIX Security, 2020, pp. 2505–2522. [14] D. Rathee et al., “CrypTFlow2: Practical 2-party secure inference,” in Proc. ACM CCS, 2020, pp. 325–342. [15] M. S. Riazi et al., “XONN: XNOR-based oblivious deep neural network inference,” in Proc. USENIX Security, 2019, pp. 1501–1518. [16] Z. Huang et al., “Cheetah: Lean and fast secure two-party deep neural network inference,” in Proc. USENIX Security, 2022, pp. 809–826. [17] L. N. Trefethen, Approximation Theory and Approximation Practice. SIAM, 2013. [18] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge Univ. Press, 2004. [19] E. Hesamifard, H. Takabi, and M. Ghasemi, “CryptoDL: Deep neural networks over encrypted data,” arXiv:1711.05189, 2017. [20] J.-W. Lee et al., “Precise approximation of convolutional neural networks for homomorphically encrypted data,” IEEE Access, vol. 11, pp. 62962–62974, 2023. [21] S. Lee et al., “OLA: An adaptive layer-wise approximation framework for FHEfriendly inference,” in Proc. ICCV, 2023. [22] Q. Lou and L. Jiang, “SAFENet: A secure, accurate, and fast neural network inference,” in Proc. ICLR, 2021. [23] W. Ao et al., “AutoFHE: Automated polynomial activation and FHE architecture search,” in Proc. USENIX Security, 2024. [24] I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” in Proc. ICLR, 2015. [25] T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed. Springer, 2009. [26] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning. MIT Press, 2016. [27] R. Kohavi, “A study of cross-validation and bootstrap for accuracy estimation and model selection,” in Proc. IJCAI, 1995, pp. 1137–1145. [28] C. Cortes and V. Vapnik, “Support-vector networks,” Machine Learning, vol. 20, no. 3, pp. 273–297, 1995. [29] K. P. Bennett and E. J. Bredensteiner, “Duality and geometry in SVM classifiers,” in Proc. ICML, 2000, pp. 57–64. [30] I. O. Tolstikhin et al., “MLP-Mixer: An all-MLP architecture for vision,” in Proc. NeurIPS, 2021. [31] H. Touvron et al., “ResMLP: Feedforward networks for image classification with data-efficient training,” IEEE TPAMI, vol. 45, no. 4, pp. 5314–5321, 2023. [32] S. Zhang et al., “GLNN: Bridging GNNs and MLPs via knowledge distillation,” in Proc. ICLR, 2022. [33] M. Oquab et al., “DINOv2: Learning robust visual features without supervision,” TMLR, 2023. [34] Qwen Team, “Qwen3-Embedding,” arXiv:2506.05176, 2025.