You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Evaluator::exponentiate_inplace() has suboptimal performance #592
When trying to raise a ciphertext to the 128-th power with SEAL, I have noticed that the corresponding function performs a linear amount of multiplications (w.r.t. the exponent), instead of a logarithmic amount, as possible with square-and-multiply approach.
More concretely, the code for exponentiate_inplace() is
void Evaluator::exponentiate_inplace(
Ciphertext &encrypted, uint64_t exponent, const RelinKeys &relin_keys, MemoryPoolHandle pool) const
{
// Verify parameters.
...
// Fast case
if (exponent == 1)
{
return;
}
// Create a vector of copies of encrypted
vector<Ciphertext> exp_vector(static_cast<size_t>(exponent), encrypted);
multiply_many(exp_vector, relin_keys, encrypted, move(pool));
}
and thus uses (in my case) 127 multiplications. Since multiply_many() performs a tree-reduction, the noisy growth is optimal, but the runtime is not. As opposed to that, something like
void fast_exponentiate(const Ciphertext& ciphertext, size_t exponent, const Evaluator& evaluator, const RelinKeys& rk, Ciphertext& result) {
// we let result uninitialized until we have to, this is represented by result_is_one == true
bool result_is_one = true;
// a classical square-and-multiply algorithm
for (int64_t i = std::numeric_limits<size_t>::digits - 1; i >= 0; --i) {
if (!result_is_one) {
evaluator.square_inplace(result);
evaluator.relinearize_inplace(result, rk);
}
if (((exponent >> i) & 1) == 1) {
// multiplying ciphertext to the result here will cause it to be
// squared exactly i times
if (!result_is_one) {
evaluator.multiply_inplace(result, ciphertext);
evaluator.relinearize_inplace(result, rk);
}
else {
result = ciphertext;
result_is_one = false;
}
}
}
}
would only execute 7 multiplications.
EDIT There was a small mistake in my implementation of fast_exponentiate().
Took a shot at this. Square-and-multiply actually breaks decryption at popcount-heavy exponents (e=127, e=255) because it doubles multiplicative depth and exhausts the noise budget.
Using precomputed squares + tree-reduce over set-bit powers gets the speedup without the noise regression: ⌊log₂(e)⌋ + popcount(e) − 1 multiplications at depth at most ⌊log₂(e)⌋ + ⌈log₂(popcount(e))⌉..
Activity
BAder82t commentedon Apr 24, 2026
Took a shot at this. Square-and-multiply actually breaks decryption at popcount-heavy exponents (e=127, e=255) because it doubles multiplicative depth and exhausts the noise budget.
Using precomputed squares + tree-reduce over set-bit powers gets the speedup without the noise regression:
⌊log₂(e)⌋ + popcount(e) − 1 multiplications at depth at most ⌊log₂(e)⌋ + ⌈log₂(popcount(e))⌉..Implementation on my fork: BAder82t/SEAL@aa5c941e.
Happy to open a PR.
perf: log-time Evaluator::exponentiate_inplace (microsoft#592)
kimlaine commentedon Apr 25, 2026
Thank you Bader (@BAder82t). Could you open a PR please?