First of all thank you for this amazing library!
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().
First of all thank you for this amazing library!
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()isand 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 likewould only execute 7 multiplications.
EDIT There was a small mistake in my implementation of
fast_exponentiate().