A hospital that wants a cloud service to train a classifier on its data faces two separate leaks. The first is the server seeing the data. Homomorphic encryption, which lets a server compute on encrypted numbers without ever decrypting them, closes that leak. The second is the finished model memorizing individual patients. Differential privacy (DP), which adds calibrated random noise so that no single record measurably changes the output, closes that one. Recent work combines the two by running noisy private gradient descent entirely inside the encryption. That approach pays the heavy cost of encrypted arithmetic for every noise step, and it still handles only low-dimensional, pre-compressed inputs. We argue that when a single data owner holds the decryption key, the noise usually belongs at the other end of the pipeline. The server runs a short, noise-free encrypted training loop on a strongly regularized linear head over randomly projected embeddings. The client decrypts the final weights once and adds a single Gaussian draw, sized using a stability bound that we can certify before seeing any data.
The same draw may also cover a third, less appreciated leak. In CKKS, the standard approximate encryption scheme for machine learning, releasing decrypted values can reveal the secret key to anyone who also holds the ciphertexts. Only post-decryption noise of sufficient size prevents this (Securing Approximate Homomorphic Encryption Using Differential Privacy). The projection dimension $k$ is the single dial that trades cryptographic cost against privacy noise. Fewer dimensions mean fewer ciphertext operations and less total noise, at the price of distortion from the projection.
Core Claim
For encrypted fine-tuning of a classification head on frozen embeddings, releasing a model through client-side output perturbation can do three things at once. It can match or beat in-ciphertext private gradient descent at the same privacy level $\epsilon$. It removes all noise handling and clipping from the encrypted circuit. It can also satisfy the post-decryption noise requirement that keeps CKKS keys safe. Client-side random projection of the embeddings to dimension $k$ reduces the encrypted cost and the DP noise simultaneously. Because the regularizer bounds the weights, the input range of the polynomial softmax is fixed in advance, so no barrier term or run-time range tracking is needed.
What Prior Work Does and Leaves Open
The closest work is Revisiting ML Training under Fully Homomorphic Encryption. It adds a log-barrier term to logistic regression so that DP noise can be injected inside the encryption without per-sample clipping. This cuts the encrypted multiplication depth per iteration from 24 to 9 and runs 3–5x faster than clipping-based DP gradient descent. It does so on binary tasks, with PCA computed offline in the clear. That paper supplies our main comparison. We keep its insight that clipping must leave the circuit, but we move the noise out of the circuit as well.
HETAL supplies the encrypted training machinery:
- multiclass softmax heads trained on ViT and MPNet embeddings under CKKS;
- polynomial approximations that stay accurate over inputs in $[-128,128]$;
- matrix products engineered around "rotations," the slot-shuffling operations that dominate encrypted run time.
HETAL has no DP, so its released weights are open to membership inference. It also trains on the full 768-dimensional embeddings. Its early stopping decrypts validation logits mid-training, which makes the stopping time depend on the data.
The case that random projection is safe under DP comes from two plaintext methods. DP-GRAPE shows that DP noise flattens the spectrum of gradients, so Gaussian random projections do as well as learned SVD bases. D2P2-SGD combines projection with decaying noise schedules. Neither addresses encryption.
PILLAR supplies the data-dependent competitor. It projects onto principal components computed from public data and shows large gains at small $\epsilon$. SF-PCA computes PCA under multiparty encryption, but its output carries no DP guarantee. We use it only as evidence that private, data-dependent subspaces carry real cost and leakage.
The attack literature establishes that trained outputs leak and that encryption alone is not enough: gradients (Deep Leakage from Gradients; Dimitrov et al.) and intermediate features (Abuadbba et al.).
FHAIM injects client-sampled encrypted noise and relies on an external decryption service. Its design shows how much machinery in-ciphertext noise requires, which is part of our motivation.
Research Program
The client computes embeddings with a public backbone. It rescales them to a fixed norm $B$ and multiplies them by a public Gaussian matrix $R \in \mathbb{R}^{k \times d}$, where $d$ is the backbone's embedding width. It then encrypts the result. All of this happens in plaintext and costs almost nothing.
The server runs $T$ steps of full-batch gradient descent with step size $\eta$ on the multiclass cross-entropy loss plus $\tfrac{\lambda}{2}\|W\|^2$. Here $W$ is the $c \times k$ weight matrix and $c$ the number of classes. The softmax uses a HETAL-style polynomial approximation. The hyperparameters $T$, $\eta$ and $\lambda$ are chosen without looking at the data, following Zhou et al.
The analysis proceeds in four steps.
- Per-example gradient bound. With norm-bounded features, each per-example gradient of the exact loss is bounded by $G = \sqrt{2}\,B'$. Here $B'$ bounds the projected feature norm, and the $\sqrt{2}$ comes from the norm of the softmax residual.
- Weight bound. The regularizer keeps the iterates inside a ball of radius $G/\lambda$. The logits are therefore confined to a range known before training. This range is the domain the polynomial must cover, and it replaces the barrier.
- Contraction. For a $\lambda$-strongly convex, $\beta$-smooth objective and $\eta \le 1/\beta$, two runs on neighboring datasets of size $n$ contract toward each other at each step. Summing the per-step perturbations gives the sensitivity bound
$$ \Delta_T \;\le\; \frac{2\,\tilde G}{n\,(\lambda - \delta)}\left(1-(1-\eta(\lambda-\delta))^{T}\right), $$
where $\Delta_T$ is the largest possible distance between final iterates. The approximate-loss terms $\tilde G$ and $\delta$ are defined in step 4.
- Polynomial correction. $\tilde G$ is the per-example gradient bound of the polynomial-approximated loss over the certified domain. $\delta$ is the largest amount by which the polynomial softmax lowers the minimum curvature below $\lambda$. Because the domain depends only on $B$, $\lambda$ and $k$, we certify both constants numerically before seeing any data. This step is the technical core: it turns an approximate encrypted computation into a sound DP sensitivity bound.
After the analysis, the client releases $W_T + \mathcal{N}(0, \sigma^2 I)$, with $\sigma$ set from $\Delta_T$ by the Gaussian mechanism. We then compare $\sigma$ with the post-decryption noise size that Li et al. require for the scheme's parameters. The analysis should identify when the DP draw already meets that requirement and how much must be added when it does not.
Finally, we derive the cost dependence on $k$. Rotation counts and ciphertext counts scale with $k$ in HETAL's matrix products, and the total noise norm scales as $\sqrt{ck}\,\sigma$. We then locate the $k$ that minimizes error at a fixed encrypted-time budget.
Baselines
The naive reference points are two plaintext bounds. The first is a non-private linear head on full embeddings, which gives the utility ceiling. The second is HETAL run as published, with encryption and no DP. It reports a maximum accuracy drop of 0.51% relative to plaintext and 567–3442 seconds of encrypted training across its benchmarks. That run time is the cost envelope we must stay within or beat. We rerun HETAL on our own hardware and treat those numbers as references, not targets.
The strongest existing competitor on the core question is in-ciphertext no-clipping DP gradient descent from Revisiting ML Training under FHE. It reports an accuracy drop under 1.82%, an AUC drop of 0.78% versus plaintext DP gradient descent, and depth 9 per iteration. We extend it to multiclass softmax, which is required for the comparison. We run it on the same projected embeddings, with the same CKKS parameters, the same number of iterations and the same $\epsilon$ and $\delta$, and with an equal grid over step size and regularization. Beating it means equal or higher accuracy at matched $\epsilon$ together with lower encrypted wall-clock time and fewer bootstraps. A result of "same accuracy, less circuit" also counts as a win.
The strongest plaintext DP competitor is PILLAR's public-PCA projection followed by DP-SGD. It reports CIFAR-100 accuracy rising from 7.5% to 18.3% at $\epsilon=0.7$ with 10% of the training data, and Flower-16 rising from 41.2% to 69.3% at $\epsilon=0.1$ with $k=40$. We reproduce these runs and also train our output-perturbed head in the clear on the same features. This separates the effect of the privacy mechanism from the effect of encryption.
Three ablations isolate the key ingredients:
- random projection versus PILLAR's public-PCA basis, at the same $k$ and inside the same encrypted pipeline;
- no projection ($k=d$) versus projection;
- a DP draw on its own versus a DP draw plus a separate post-decryption draw sized to Li et al.'s requirement, which measures what the "one draw" claim actually saves.
D2P2-SGD reports 78.5% versus 57.0% for standard DP-SGD on FashionMNIST at $\epsilon=6$. That comparison is for full-network training, so we cite it for context only and not as a head-to-head baseline.
Why not just…?
Why not just train the head on the client, since the client already holds the embeddings? This is the most serious threat. A linear head on 768-dimensional features is cheap in plaintext. The proposal only matters where outsourcing is imposed, for example when the training service is proprietary or the client is a thin device. We will report client-side plaintext training cost next to every encrypted number so readers can judge the premise. We will not argue that encryption is always worthwhile.
Why not project inside the ciphertext, as a public matrix times encrypted vectors? When the client holds plaintext embeddings, projecting before encryption is free and adds neither depth nor noise. Doing it inside the ciphertext would only add rotations. We therefore project on the client, and treat in-ciphertext projection as relevant only when the embeddings are themselves computed under encryption.
Why not keep noise inside the encryption, as Zhou et al. do? Per-step noise supports stronger threat models: intermediate decryptions, or a server that also sees iterates. In the single-owner setting it adds circuit work and yields no extra guarantee on the released model. The matched-$\epsilon$ comparison in the Baselines section settles whether output perturbation also loses utility. If it loses more than about one accuracy point at small $\epsilon$, we will report in-ciphertext noise as preferable in that regime.
Why not use the client's own PCA instead of random projection? A PCA basis computed on private data consumes privacy budget or leaks. SF-PCA shows that locally computed components correlate below 0.75 with the global ones. DP-GRAPE suggests random bases lose little under DP noise, and our random-versus-public-PCA ablation tests this directly.
Why not skip DP, since the data is encrypted? Decrypted weights leak training records through the attacks cited above. Releasing them also exposes CKKS to key recovery (Li et al.).
Proposed Experiments
The feature sets are:
- HETAL's ViT features on MNIST, CIFAR-10, DermaMNIST and Face Mask Detection;
- HETAL's MPNet features on SNIPS;
- PILLAR's domains Flower-16, GTSRB, PCAM and Pneumonia, together with CIFAR-100 at 10% of the training data.
We sweep $\epsilon \in \{0.1, 0.7, 1, 3, 6\}$ and $k \in \{32, 64, 128, 256, d\}$. For each run we report test accuracy, encrypted wall-clock time, rotation and bootstrap counts, ciphertext bytes transferred, and the certified constants $\tilde G$ and $\delta$.
Four checks decide the outcome:
- Utility at matched privacy. At each $\epsilon$, output perturbation should come within one accuracy point of in-ciphertext DP gradient descent or beat it, while cutting encrypted time.
- The $k$ trade-off. Error as a function of $k$ should be U-shaped under a fixed time budget, with the minimum well below $d$.
- Sensitivity bound holds empirically. Membership-inference audits on released heads should show no advantage beyond what the certified $\epsilon$ allows. A violation would mean the polynomial correction in step 4 of the analysis is unsound.
- Key protection. For the CKKS parameters in use, we check whether the DP $\sigma$ meets Li et al.'s requirement of $\kappa/2+\tilde O(1)$ noise bits. We then run their decryption-query key-recovery setting on un-noised and noised releases.
If the DP draw is consistently far smaller than the key-protection requirement, the "one draw" claim fails and becomes a measured cost of two draws. That is still a useful answer to a question the file shows nobody has asked.
References
- Securing Approximate Homomorphic Encryption Using Differential Privacy
- Revisiting ML Training under Fully Homomorphic Encryption: Convergence Guarantees, Differential Privacy, and Efficient Algorithms
- HETAL: Efficient Privacy-preserving Transfer Learning with Homomorphic Encryption
- Memory-Efficient Differentially Private Training with Gradient Random Projection
- Balancing Utility and Privacy: Dynamically Private SGD with Random Projection
- PILLAR: How to make semi-private learning more effective
- Scalable and Privacy-Preserving Federated Principal Component Analysis
- Deep Leakage from Gradients
- LAMP: Extracting Text from Gradients with Language Model Priors
- Can We Use Split Learning on 1D CNN Models for Privacy Preserving Training?
- FHAIM: Fully Homomorphic AIM For Private Synthetic Data Generation