Seeking ways to improve the calculation efficiency of Microsoft's seal library

Question

I'm using Microsoft's homomorphic encryption library seal to calculate the dot product of two ciphertext vectors. I found that when the size of the ciphertext vector is 600, it takes about 12 seconds. I don't know if there is a way to improve the efficiency of my code, or is this the upper limit of the calculation speed of homomorphic encryption?

...
EncryptionParameters parms(scheme_type::BFV);
size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::BFVDefault(poly_modulus_degree));
parms.set_plain_modulus(1ll<<20);
auto context = SEALContext::Create(parms);
...
for(int i=1;i<=M;i++){
    for(int j=i;j<=M;j++){
        for(int k=1;k<=N;k++){
            ...
            evaluator.multiply_inplace(ca,cb);
            evaluator.add_inplace(c_sum,ca);
            ...
        }
    }
}

Answer 1

You've omitted a lot in the code snippet you've posted, so I am basing my answer on the assumption that you are implementing a matrix multiplication (because there are 3 nested four loops in your code, and vector dot product is easily implemented by using only 1 loop). I am guessing that you've gone for the straightforward implementation, which is a cubic algorithm (with O(n^3) complexity), so it is not surprising that you code is taking that long to execute.

Better algorithms exist, but they have their own downsides. For example, Coppersmith–Winograd algorithm has approximately O(n^2.37) complexity, but is not practical to be used in practice. It is often used in algorithm theory to prove complexity of other algorithms that contain matrix multiplication. Another faster algorithm (Strassen algorithm) with O(n^2.8074) complexity and it is useful in practice, but the downsides are that it is only useful for large enough matrices, and the implementation is more complicated than the straightforward one.

This means that if the speed improvement is worth to complicate your implementation, then you will have to experiment to find the size after which the Strassen algorithm becomes faster, and implement a hybrid algorithm that uses straightforward implementation for smaller matrices, and Strassen for bigger ones. The details of the algorithm are too complicated to be explained here, but you can find them in the Wikipedia article I've posted.