0

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);
            ...
        }
    }
}
4

1 回答 1

3

您在发布的代码片段中省略了很多内容，因此我的回答基于您正在实现矩阵乘法的假设（因为您的代码中有 3 个嵌套的四个循环，并且向量点积很容易实现仅使用 1 个循环）。我猜你已经选择了简单的实现，这是一个三次算法（具有O(n^3)复杂性），所以你的代码需要这么长时间来执行也就不足为奇了。

存在更好的算法，但它们也有自己的缺点。例如，Coppersmith-Winograd 算法具有近似O(n^2.37)复杂性，但在实践中使用并不实用。在算法理论中经常使用它来证明包含矩阵乘法的其他算法的复杂性。另一种较快的算法（Strassen 算法）具有O(n^2.8074)复杂性，在实践中很有用，但缺点是它只对足够大的矩阵有用，并且实现比简单的更复杂。

这意味着，如果速度改进值得使您的实现复杂化，那么您将不得不尝试找到 Strassen 算法变得更快的大小，并实现一种混合算法，该算法对较小的矩阵使用简单的实现，而对较大的矩阵使用 Strassen . 该算法的细节过于复杂，无法在此处解释，但您可以在我发布的 Wikipedia 文章中找到它们。

于 2019-12-20T10:07:38.917 回答