Homomorphic encryption lets an untrusted server compute on data it cannot read. Every encrypted multiplication, however, adds error ("noise") to the ciphertext, and after a fixed number of sequential multiplications the result can no longer be decrypted. An encrypted optimizer therefore has to fix its whole computation in advance. It cannot test "have I converged?", it cannot project back onto constraints, and it cannot shrink its step size when things go wrong. The existing purely polynomial solver for constrained problems handles constraints by raising the degree of a penalty polynomial (A polynomial-based QCQP solver for encrypted optimization). It chooses the iteration count from coarse offline bounds. Both choices directly increase the number of sequential multiplications, so they consume the noise budget quickly. The real question is not how to run gradient descent under encryption. It is how to know, before encrypting anything, the smallest penalty degree, step size, iteration count and numerical precision that provably deliver a feasible, accurate answer for every admissible secret input.
We propose to answer that question with sum-of-squares (SOS) programming, a technique that proves a polynomial is nonnegative by writing it as a sum of squared polynomials, which turns the proof into a convex semidefinite program. The proof concerns the encrypted solver's own update map, and it runs offline in plaintext over the public range of the secret parameters. It must hold for all parameter values and all iterate pairs, so it involves several times more variables than the original problem, and dense SOS cannot handle that size. Correlative sparsity solves the problem. This is the observation that variables in physical systems interact only locally, so a problem splits into small overlapping groups of variables called cliques (CS-TSSOS). The verification problem inherits the clique structure of the optimization problem. Sparsity therefore buys a tractable proof about the ciphertext computation, and that proof sets the noise budget. Making the encrypted arithmetic itself cheaper is a secondary benefit.
Core Claim
Consider an encrypted solver that runs the iteration
$$x_{t+1} = x_t - \alpha \nabla J_k(x_t;\theta) + w_t,$$
where $x_t$ is the encrypted iterate, $\theta$ the encrypted problem data (loads, cost coefficients, limits), $J_k = f + p_k$ the objective plus a degree-$k$ polynomial penalty, $\alpha$ a step size, and $w_t$ the per-iteration error introduced by approximate CKKS arithmetic, bounded by a precision-dependent $\varepsilon$. Suppose we find a set $S$ that the map keeps iterates inside, and a quadratic function $V(z) = z^\top P z$ such that, for all $x,y \in S$ and $\theta \in \Theta$,
$$V\big(T(x;\theta) - T(y;\theta)\big) \le \rho\, V(x-y), \quad \rho<1.$$
Here $T$ is the noiseless update and $\Theta$ the public box of admissible parameters. Then after $N$ iterations the iterate sits within roughly $\rho^{N/2}\,\mathrm{diam}(S) + \varepsilon/(1-\sqrt{\rho})$ of the penalized fixed point. This follows from summing the geometric series that contraction gives for the disturbed iteration. The same certificate yields three things: the iteration count $N$, the CKKS precision $\varepsilon$ the run can tolerate, and proof that ciphertext error does not compound. The last point is what failed for recursive encrypted controllers in Comparison and performance analysis of dynamic encrypted control approaches. Total multiplicative depth is $N$ times the depth of one step, and the depth of one step grows like $\lceil\log_2 k\rceil$ plus a constant. So the certificate gives a direct objective for searching over $(k, \alpha, N, \varepsilon)$ for the cheapest configuration that is still certified.
The program in $(x, y, \theta)$ has three times the original variables. Its interaction graph is the original graph with each node tripled, so the chordal extension and the running intersection property (Lasserre et al.) carry over clique by clique. We restrict $P$ to the same chordal pattern. The sparse Positivstellensatz of Anh et al. and the convergence rates in Convergence rates for sums-of-squares hierarchies with correlative sparsity then say that cost scales with the largest clique rather than the total variable count.
One caveat shapes the whole design. Problems such as AC power flow are nonconvex, so no contraction certificate will hold over the full feasible set. We therefore target encrypted re-dispatch around a public operating point. The nominal solution and grid topology are public, and the secret deviations in load and cost lie in a public box. Contraction is plausible in that regime, and the question of whether it can be certified is a real one. The threat model follows Exploiting Unstructured Sparsity in Fully Homomorphic Encrypted DNNs, which reveals the sparsity pattern but not the values. In our setting the clique tree and the parameter box are public. We will state explicitly what the box leaks.
Relation to Prior Work
Two papers motivate the proposal. A polynomial-based QCQP solver for encrypted optimization supplies the polynomial-penalty gradient iteration that we reuse. It proves that the iterates stay feasible and converge as the degree $k\to\infty$. It does not exploit sparsity, it derives the iteration count analytically for a two-variable example, and it leaves the degree–depth conflict unresolved. We keep its solver and replace its offline analysis with a computed, parameter-uniform certificate that also models CKKS error. Comparison and performance analysis of dynamic encrypted control approaches shows that repeated encrypted updates accumulate error. It uses linear matrix inequalities to bound the performance lost to bootstrapping and resets. We carry that robust-control style of reasoning to nonlinear, polynomial iteration maps, which requires SOS rather than linear matrix inequalities.
Three papers constrain the design. Encrypted Accelerated Least Squares Regression shows that gradient descent has depth independent of dimension, while coordinate-wise methods have depth linear in dimension. This tells us that sparsity alone does not reduce depth per iteration, so our gain has to come from smaller $N$ and smaller $k$. The same paper offers van Wijngaarden acceleration at one extra level, which we test as an add-on. Cloud-Based Quadratic Optimization With Partially Homomorphic Encryption avoids non-polynomial projections by using interactive comparisons. That is a different trust and latency model, and we include it as a reference point. Minimal Sparsity for Second-Order Moment-SOS Relaxations of the AC-OPF Problem shows that dropping the running intersection property makes AC-OPF relaxations far cheaper, at the cost of guarantees. We treat it as a speed option for the verification program, to be checked for soundness.
The method comes from CS-TSSOS and the TSSOS library, which we use to solve the certificate programs. The CKKS circuit is compiled with HEIR, whose bootstrap placement serves as the noise-management baseline. Closest in spirit on the machine-learning side are ULD-Net and HEAT. Both reduce depth by tuning approximations empirically against training data. We tune solver hyperparameters against a proof instead.
Research Program
The first component is a verification compiler. It takes a polynomial problem with symbolic parameters, the public box $\Theta$ and a candidate $(k,\alpha)$. It builds the invariance and incremental-contraction conditions, then extracts the clique tree of the lifted $(x,y,\theta)$ graph. Finally it calls TSSOS to find the smallest certified $\rho$ and the largest certified $\varepsilon$. An outer search over $(k,\alpha)$ and CKKS precision minimizes the predicted bootstrap count. That prediction combines total depth $N(\rho)\cdot \mathrm{depth}(k)$ with the per-level costs that HEIR reports.
The second component is the encrypted executor. It packs ciphertext slots clique by clique, so that the only rotations needed are those that move variables shared between neighboring cliques. Iteration counts and bootstrap points are set by the certificate.
The analysis component asks one question: when does the sparse certificate exist, and how conservative is it? We will measure the gap between the certified $N$ and the smallest $N$ that works empirically, and see how that gap depends on the box width, clique size and relaxation order. Order 1.5 relaxations are especially relevant, given their gains in Certifying Global Optimality of AC-OPF Solutions via sparse polynomial optimization.
Baselines
The naive reference point is the dense polynomial-penalty solver of A polynomial-based QCQP solver for encrypted optimization, with its analytically derived iteration count and a penalty degree raised until worst-case feasibility holds. It runs under the same CKKS parameters, the same HEIR compilation and the same hardware. That paper reports no encrypted runtime or depth figure for problems beyond its two-number example, so no reported result was found on Lacuna for this baseline at scale, and we will implement it ourselves. Beating it means fewer bootstraps and lower wall-clock time, with constraint violation and suboptimality equal or better on every test parameter.
The strongest practical competitor is the same solver with its hyperparameters chosen by large-scale plaintext simulation. We sample $\theta$ from $\Theta$, simulate the CKKS error, and take the cheapest $(k,\alpha,N,\varepsilon)$ that succeeds on all samples. HEIR schedules the bootstraps. This baseline gets the same compute budget as our certificate solve, so if certification takes an hour, sampling gets an hour of simulation. To beat it, our configuration must be no more expensive and must have zero failures on adversarially searched worst-case parameters. On those parameters we expect sampling to fail at least sometimes.
As a cross-model reference, we compare against the interactive Paillier protocol of Cloud-Based Quadratic Optimization With Partially Homomorphic Encryption. That paper reports approximately 140–160 seconds for 30 iterations on random QPs with 100 variables and 95 constraints under its fully private protocol, and 40–60 seconds with multiplicative blinding. We will run our solver on random QPs of the same size, given sparse structure, and report latency both with zero network delay and under the 10–20 ms delays that the Paillier paper found its protocol sensitive to.
Three ablations isolate the key ingredient. The first certifies with dense SOS on the same lifted problem, which tests whether sparsity is what makes verification feasible. The second certifies without the noise term $w_t$, which tests whether modeling ciphertext error changes the chosen precision or iteration count. The third is a minimal-sparsity certificate that drops the running intersection property, in the style of Minimal Sparsity for Second-Order Moment-SOS Relaxations of the AC-OPF Problem; for it we check whether the resulting configurations ever fail empirically. Ground truth for suboptimality is the plaintext CS-TSSOS global bound.
Why not just…?
Why not just pick the iteration count and degree by plaintext simulation? This is the real threat. If the sampled configuration matches the certified one in cost and never fails, then the certificate's only value is the guarantee itself. That still matters for grid operators running a blind computation that cannot be checked mid-run. We will report this outcome honestly if it occurs. The experiment that settles it searches for worst-case parameters, using the certificate's dual information or local optimization over $\Theta$. It then checks whether simulation-chosen configurations break on those parameters, and measures how much cheaper the certificate's choice is when sampling turns out to be conservative.
Why not just use bootstrapping whenever the budget runs out, as compilers already do? HEIR and Cheetah (Cheetah) optimize where noise is refreshed for a fixed circuit, but they cannot decide how many iterations or what penalty degree the circuit needs. Our work sets those inputs, and then HEIR schedules the result in both arms. Each bootstrap also adds approximation error, which degraded the controller in Comparison and performance analysis of dynamic encrypted control approaches from an $\ell_2$-gain bound of 1.8030 to 2.0332. Our certificate treats that error as part of $w_t$ rather than ignoring it.
Why not just use interactive comparisons for projections and stopping? This is a legitimate alternative under a different trust model, and the Paillier figures above give its cost at 100 variables. Our claim is limited to settings where the data owner is offline. The latency comparison under network delay shows where the crossover lies.
Why not just use the dense certificate on small problems? It works on small problems, and we will use it there to validate the sparse one. The dense ablation is the test of whether sparsity is required. We expect the dense certificate to become impossible to set up once the lifted problem exceeds a few dozen variables, which is the regime that Hohmann et al. describe for dense SOS.
Proposed Experiments
The first test bed uses chained constrained POPs, namely the Chained Wood and Broyden tridiagonal functions from CS-TSSOS, with encrypted coefficients and dimension swept from about 10 to several hundred. This measures certificate solve time, certified versus empirical $N$, bootstrap count and encrypted wall-clock time as the problem grows while clique size stays fixed.
The second is random sparse QPs matched to the sizes of Cloud-Based Quadratic Optimization With Partially Homomorphic Encryption.
The third is encrypted AC-OPF re-dispatch. We start from PGLiB instances, from the smallest cases up to the modified IEEE 57-bus case used in Minimal Sparsity for Second-Order Moment-SOS Relaxations of the AC-OPF Problem. Loads are perturbed in boxes of increasing width around the public base solution. Metrics are constraint violation, the gap to the CKKS-free plaintext optimum, the gap to the CS-TSSOS global bound, bootstrap count and latency. We also record the largest box width at which a certificate still exists, since this maps out how far the approach reaches.
Two outcomes would decide the proposal. The first is whether sparse certificates exist at all for realistic box widths on the 57-bus case. The second is whether certified configurations need fewer bootstraps than the naive analytic baseline while never failing where the simulation-tuned baseline fails.
References
- A polynomial-based QCQP solver for encrypted optimization
- CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization
- Comparison and performance analysis of dynamic encrypted control approaches
- Positivity and Optimization for Semi-Algebraic Functions
- A Sparse Version of Reznick's Positivstellensatz
- Convergence rates for sums-of-squares hierarchies with correlative sparsity
- Exploiting Unstructured Sparsity in Fully Homomorphic Encrypted DNNs
- Encrypted Accelerated Least Squares Regression
- Cloud-Based Quadratic Optimization With Partially Homomorphic Encryption
- Minimal Sparsity for Second-Order Moment-SOS Relaxations of the AC-OPF Problem
- TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization
- HEIR: A Unified Representation for Cross-Scheme Compilation of Fully Homomorphic Computation
- ULD-Net: Enabling Ultra-Low-Degree Fully Polynomial Networks for Homomorphically Encrypted Inference
- HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation
- Certifying global optimality of AC-OPF solutions via sparse polynomial optimization
- Cheetah: Optimizing and Accelerating Homomorphic Encryption for Private Inference
- A moment and sum-of-squares extension of dual dynamic programming with application to nonlinear energy storage problems