求提高微软印章库计算效率的方法

Question

我正在使用微软的同态加密库 seal 来计算两个密文向量的点积。我发现当密文向量的大小为600时，大约需要12秒。不知道有没有办法提高我的代码效率，或者这是同态加密计算速度的上限？

...
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

你在发布的代码片段中省略了很多，所以我的回答基于你正在实现矩阵乘法的假设（因为你的代码中有 3 个嵌套的四个循环，并且 vector仅使用 1 个循环即可轻松实现点积）。我猜你已经选择了直接的实现，这是一个三次算法（具有 O(n^3) 复杂度），所以你的代码执行这么长时间也就不足为奇了。

存在更好的算法，但它们有自己的缺点。例如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)，复杂度O(n^2.8074)，在实践中很有用，但缺点是只对足够大的矩阵有用，实现起来比直接的复杂。

这意味着如果速度的提高值得使您的实施复杂化，那么您将不得不通过试验找到 Strassen 算法变得更快的大小，并实施一种混合算法，该算法对较小的矩阵使用直接实施，和 Strassen 更大的。算法的细节过于复杂，无法在这里解释，但您可以在我发布的维基百科文章中找到它们。

求提高微软印章库计算效率的方法

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

c++

encryption

algorithm

seal