A polynomial-based QCQP solver for encrypted optimization

Sebastian Schlor, Andrea Iannelli, Junsoo Kim, Hyungbo Shim, Frank Allgöwer

Abstract

In this paper, we present a novel method for solving a class of quadratically constrained quadratic optimization problems using only additions and multiplications. This approach enables solving constrained optimization problems on private data since the operations involved are compatible with the capabilities of homomorphic encryption schemes. To solve the constrained optimization problem, a sequence of polynomial penalty functions of increasing degree is introduced, which are sufficiently steep at the boundary of the feasible set. Adding the penalty function to the original cost function creates a sequence of unconstrained optimization problems whose minimizer always lies in the admissible set and converges to the minimizer of the constrained problem. A gradient descent method is used to generate a sequence of iterates associated with these problems. For the algorithm, it is shown that the iterate converges to a minimizer of the original problem, and the feasible set is positively invariant under the iteration. Finally, the method is demonstrated on an illustrative cryptographic problem, finding the smaller value of two numbers, and the encrypted implementability is discussed.

Introduction

Optimization algorithms are the backbone of modern control systems and machine learning. However, when these systems process sensitive data, privacy becomes a critical concern. Homomorphic Encryption (HE) allows for computation directly on encrypted data, but it is mathematically restricted to polynomial operations: addition and multiplication.

Standard constrained optimization algorithms, such as projected gradient descent or ADMM, rely on non-polynomial operations like projections, divisions, and comparisons. Existing workarounds often require trusted third parties or communication-heavy protocols. This paper introduces a novel algorithm for solving quadratically constrained quadratic programs (QCQPs) using only additions and multiplications, enabling purely polynomial constrained optimization that can run natively and autonomously on encrypted data.

Methodology: Polynomial Penalty Functions

The core innovation lies in transforming the constrained optimization problem into a sequence of unconstrained polynomial optimization problems. Traditional barrier or penalty methods are unsuitable for HE because they utilize non-polynomial functions (e.g., logarithms or piecewise functions).

Instead, the authors introduce a sequence of polynomial penalty functions $p_k(x)$ of increasing degree. These polynomials are designed to remain near zero within the feasible set $\mathcal{C}$ and grow rapidly outside of it. At each iteration $k$, an auxiliary cost function $J_k(x)$ is formed by adding the $k$-th degree penalty polynomial to the original cost function $f(x)$.

Visualization of the polynomial penalty method showing objective, penalty, and combined cost functions.

Because $J_k(x)$ is a polynomial, its gradient is also a polynomial. The optimization proceeds via sequential gradient descent. Each update step involves only multiplication by a step size and addition, making the entire process perfectly suited for homomorphic encryption.

Theoretical Insights

  • Dynamic Penalty Scaling: Unlike traditional methods that scale a fixed penalty function by a scalar weight, this method increases the degree of the polynomial penalty. This mimics the behavior of interior point methods while maintaining a purely polynomial structure.
  • Positive Invariance: A major theoretical result of this algorithm is that if the initial guess is within the feasible set, all subsequent iterates are mathematically guaranteed to remain within the feasible set.
  • Convergence Guarantee: The authors rigorously prove that as the polynomial degree $k \to \infty$, the minimizers $x_k^*$ of the auxiliary problems converge to the true minimizer $x^\star$ of the original constrained problem.

Key Results and Applications

The paper provides theoretical proofs for the convergence of the cost function $f(x_k)$ to the optimal cost $f(x^\star)$. To demonstrate practical utility, the authors apply the solver to a common cryptographic challenge: finding the minimum of two encrypted numbers. This is formulated as a QCQP, and the authors derive:

  1. A precise formula for the distance to the true minimizer at any step $k$.
  2. A method to pre-calculate the exact number of iterations $N$ required to reach a target precision $\delta$.

Limitations and Future Outlook

While promising, the method has limitations inherent to HE environments. Since comparisons are non-polynomial, the algorithm cannot use dynamic stopping criteria; the total number of iterations must be fixed in advance. Additionally, certain problem parameters must be upper-bounded offline before encrypted computation begins. Finally, the multiplicative depth of the algorithm impacts cryptographic noise, requiring careful management through Leveled or Fully Homomorphic Encryption.

Future research will focus on analyzing general convergence speeds, comparing performance against non-polynomial methods, and extending the framework to handle encrypted parameters within the constraints themselves.

Summary updated

Abstract

In this paper, we present a novel method for solving a class of quadratically constrained quadratic optimization problems using only additions and multiplications. This approach enables solving constrained optimization problems on private data since the operations involved are compatible with the capabilities of homomorphic encryption schemes. To solve the constrained optimization problem, a sequence of polynomial penalty functions of increasing degree is introduced, which are sufficiently steep at the boundary of the feasible set. Adding the penalty function to the original cost function creates a sequence of unconstrained optimization problems whose minimizer always lies in the admissible set and converges to the minimizer of the constrained problem. A gradient descent method is used to generate a sequence of iterates associated with these problems. For the algorithm, it is shown that the iterate converges to a minimizer of the original problem, and the feasible set is positively invariant under the iteration. Finally, the method is demonstrated on an illustrative cryptographic problem, finding the smaller value of two numbers, and the encrypted implementability is discussed.
BibTeX
@misc{schlor2025polynomial,
  author = {Sebastian Schlor and Andrea Iannelli and Junsoo Kim and Hyungbo Shim and Frank Allgöwer},
  title = {{A polynomial-based QCQP solver for encrypted optimization}},
  year = {2025},
  eprint = {2510.17294},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.17294},
}
Figure