Smarter Starting Points Slash the Cost of Encrypted Division and Square Root

Computing on encrypted data has long been one of the most tantalizing promises in modern cryptography. Homomorphic encryption allows a server to add and multiply ciphertexts without ever seeing the plaintexts underneath, which means sensitive records can be processed in the cloud while remaining encrypted throughout their entire lifecycle. As regulations such as the European Union’s General Data Protection Regulation tighten the rules around how personal information may be analyzed, and as high-profile cloud breaches continue to make headlines, the appeal of a technology that never requires decryption for processing is obvious. Yet the scheme at the center of practical privacy-preserving machine learning, known as CKKS, supports only addition and multiplication out of the box. Everything else that a neural network needs, including division and square root, must be painstakingly constructed from those two primitive operations.

A new study published in Discover Artificial Intelligence tackles a deceptively narrow question with wide consequences: how should the starting values for homomorphic division and square root be chosen? The work, carried out by Simon Engel, Lukas Horn, Thomas Prantl and Samuel Kounev, builds on the Newton–Raphson method, an iterative root-finding technique that previous research identified as the best-suited approach for these functions inside CKKS. The Newton–Raphson method is a workhorse of classical numerical computing, and it converges to the reciprocal of a number or to an inverse square root through repeated multiplication and addition. That is exactly what CKKS can do natively. But the method has a well-known Achilles heel: it only converges to a meaningful result if it begins from a good initial guess, and even slight deviations in that guess can cause the iteration to diverge entirely.

On a conventional processor, the initial guess problem is solved with tools that homomorphic encryption simply cannot use. Standard libraries, comparisons, bit shifts and lookup tables are all unavailable inside a CKKS ciphertext, which renders most of the classical literature on division and square root unusable. The famous inverse square root trick from the 1999 video game Quake, which relies on subtracting a magic constant after a bit shift, is a case in point: elegant on hardware, impossible in CKKS. The approach that does work homomorphically is a linear helper function. Given a ciphertext whose encrypted values are known to lie within a predefined interval, the helper function computes a start value from the input itself using a straight line, adding just one level of multiplicative depth to the overall circuit. The parameters of that line are generated in plaintext ahead of time, based on the expected interval, and then applied as ciphertext-plaintext operations during the encrypted computation.

The prior state of the art generated these line parameters by brute-force search, testing every combination of coefficients over a defined grid. The method yields good results, but it has two serious drawbacks. First, it is slow: for large intervals, parameter generation can take multiple hours. Second, there is no guarantee that optimal or even near-optimal parameters lie within the sampled search space, and small differences in the coefficients can have a large impact on whether the Newton iteration converges. The new work reformulates the entire task as a black-box optimization problem. For a given interval, the goal is to find the two real coefficients of the helper function that minimize the resulting approximation error, measured as the root mean square error over one thousand samples uniformly distributed across the interval.

To solve this low-dimensional problem, the researchers implemented and compared three widely used optimization algorithms, deliberately chosen because the problem involves only two real-valued parameters and a single objective. Gradient descent is a deterministic, gradient-based local search that steps along the steepest-descent direction, with adaptive learning-rate tuning implemented for this study. Hill climbing, in the form of a random-restart first-choice variant, greedily accepts neighboring states only when they improve the objective, running ten parallel climbers and keeping the best result. Simulated annealing, inspired by the physical process of cooling metals, can occasionally accept worse solutions with a probability governed by a Boltzmann distribution, allowing it to escape local minima; the implementation uses quadratic cooling and an adaptive initial variance search. Population-based methods such as genetic algorithms and particle swarm optimization were excluded because their computational overhead is disproportionate for a problem of this dimension.

The evaluation was exhaustive. The team generated parameters for all valid intervals for the square root function, spanning zero to two hundred in 0.1-step increments, and for the division function, spanning negative one hundred to positive one hundred, each with one to five Newton iterations. That amounts to 20,100 distinct intervals per function per iteration count, or 603,000 evaluated configurations in total. The homomorphic experiments ran on the OpenFHE library, version 1.4.2, on a machine equipped with an AMD EPYC 9354P processor and 128 gigabytes of memory, with the same cryptographic context and keys reused across measurements to rule out confounding effects. To enable direct comparison with the brute-force baseline, the researchers determined for each interval the smallest number of Newton iterations such that 95 percent of the computed values lie within a tolerance of 0.1 of the true result.

The results are striking. For the square root function, gradient descent failed to produce valid parameters for 99.1 to 99.6 percent of the test intervals, a consequence of the non-convex error landscape that this greedy method cannot navigate. Hill climbing and simulated annealing, by contrast, generated parameters that enabled the square root to be computed on every single test interval with at most five Newton iterations. The brute-force parameters required at most ten iterations on most intervals, and intervals close to zero could not be evaluated with fewer than ten. Because each Newton iteration for the square root consumes three levels of multiplicative depth plus a constant, this translates directly into shallower circuits: the maximum multiplicative depth across all test intervals drops from at least 32 with brute-force parameters to 17 with optimized parameters, and with simulated annealing, a single Newton iteration suffices for most intervals, requiring only five consecutive multiplications. Overall, the optimization-based approach saves up to 27 consecutive multiplications, depending on the interval.

Division proved harder, as expected, because the reciprocal function is unbounded near zero. Intervals containing only positive or only negative numbers satisfied the accuracy criterion, with most achieving it in a single Newton iteration, while intervals spanning zero remained difficult to approximate with a straight-line helper. Even so, for intervals that start or end at zero, the optimized parameters met the same accuracy criterion as the brute-force approach but with one to five iterations instead of ten or more, saving ten to eighteen consecutive multiplications. In terms of raw accuracy, simulated annealing achieved the lowest root mean square error on the largest share of intervals: 93.6 percent down to 59.5 percent of intervals for one to five Newton iterations on the square root, and 56.1 to 75.2 percent for two to five iterations on the inverse. Hill climbing delivered slightly worse but more stable results, bounding the worst-case square root error at 2.5 times ten to the negative second, and both stochastic methods produced valid parameters for every interval-iteration combination. For most intervals not containing zero, the error fell below one times ten to the negative tenth, and some intervals reached one times ten to the negative thirteenth with only four iterations.

The practical payoff extends beyond accuracy to generation time itself. Because an equal number of samples is used for parameter generation, runtime depends only on the generator, and the optimization algorithms outperformed brute-force search by two to three orders of magnitude. Finding a suitable helper function now takes a few hundred milliseconds instead of seconds to minutes, a significant advantage for applications that need to adapt parameters on the fly. The researchers also measured run-to-run variation across 30 random seeds, finding that the stochastic methods show some variance in final accuracy, which in practice could be reduced by running simulated annealing multiple times with different seeds or with adjusted cooling schedules. The authors present their systematic results as a reference guide for developers, allowing them to verify whether the Newton-based approach is feasible for a given application and to select reasonable parameters for a desired accuracy. Future work aims to combine the strengths of simulated annealing and hill climbing into a joint parameter generation scheme, to extend the method to higher-degree polynomials, particularly for division near zero, and to apply the optimization approach to other Newton-based homomorphic evaluations, including the approximation of neural network activation functions.

Subject of Research: Optimizing initial guesses for homomorphic reciprocal and square root evaluation with CKKS

Article Title: De Pace: Optimizing initial guesses for homomorphic reciprocal and square root evaluation with CKKS

Article References: Engel, S., Horn, L., Prantl, T., & Kounev, S. (2026). De Pace: Optimizing initial guesses for homomorphic reciprocal and square root evaluation with CKKS. Discover Artificial Intelligence, 6(1), Article 1568. https://doi.org/10.1007/s44163-026-02443-1

Image Credits: AI Generated

DOI: 10.1007/s44163-026-02443-1

Keywords: homomorphic encryption, CKKS, Newton-Raphson, simulated annealing, hill climbing, gradient descent, privacy-preserving machine learning, black-box optimization, multiplicative depth, OpenFHE, division, square root