HElib-2 向量内积

本文翻译自：
https://mshcruz.wordpress.com/2016/09/27/scalar-product-using-helib/

假设输入两个向量 $u=[1,2,3,4],v=[1,2,3,4]$ ,目的是计算两个向量的内积。

以下介绍三种方式可以在密文下进行运算，首先假设已经初始化（需要的公共参数以及密钥都已经创建好了）， $VEC\_SIZE$ 表示输入向量的大小（此处为4）。

方法一：

单独加密向量的每一个数字，得到一个密文向量：

std::vector<Ctxt> encU;
std::vector<Ctxt> encV;

for (int i=0; i<VEC_SIZE; i++) {
    Ctxt tempU(pk);
    pk.Encrypt(tempU, to_ZZX(u[i]));
    encU.push_back(tempU);
    Ctxt tempV(pk);
    pk.Encrypt(tempV, to_ZZX(v[i]));
    encV.push_back(tempV);
}

之后将两个密文向量相乘：

// Store the result in encU
for (int i=0; i<VEC_SIZE; i++) {
    encU[i] *= encV[i];
}

最后计算encU向量中所有元素的总和：

// Save the result in the first position of the vector
for (int i=0; i<VEC_SIZE; i++) {
    encU[0] += encU[i];
}

解密向量中的第一个元素，获得结果：

// Decrypt the first position, which holds the value of the scalar product
// ZZX is a class from the NTL library that represents polynomials
ZZX result;
sk.Decrypt(result, encU[0]);

return result[0];

HElib提供了 $ciphertext \ packing$ 操作，将整个向量加密成一个密文。

方法二：

将向量中的元素编码成多项式的系数，对于向量 $u$ ，得到多项式 $u(x)=1+2x+3x^2+4x^3$ .
可以通过将一个向量编码成的多项式乘以另一个向量以“逆形式”编码的多项式（比如向量 $v$ 的逆形式为 $v(x)=4+3x+2x^2+x^3$ ），并且找到一个特定项的系数来表示两个向量的内积。

ZZX U,V;

U.SetLength(VEC_SIZE);
V.SetLength(VEC_SIZE);

for (int i=0; i<VEC_SIZE; i++) {
    SetCoeff(U, i, u[i]); // u(x) = 1 + 2x + 3x^2 + 4x^3
    SetCoeff(V, VEC_SIZE-1-i, v[i]);  // v(x) = 4 + 3x + 2x^2 + 1x^3
}

之后，将每个多项式加密成一个密文：

// Ciphertexts that will hold the polynomials encrypted using public key pk
Ctxt encU(pk);
Ctxt encV(pk);

// Encrypt the polynomials into the ciphertexts
pk.Encrypt(encU, U);
pk.Encrypt(encV, V);

密文乘法：

// Multiply the ciphertexts and store the result in encU
encU *= encV;

解密之后，运算的结果为多项式第( $VEC\_SIZE-1$ )项的系数:

// Decrypt the multiplied ciphertext into a polynomial using the secret key sk
ZZX result;
sk.Decrypt(result, encU); 

return result[VEC_SIZE - 1];

这种方法利用密文打包技术，避免加密每一个元素，节省了时间。但同时，我们失去了访问每个元素的能力。

方法三

仍然利用密文打包技术，但不是用多项式，需要用到HElib库中的EncryptedArray类。密文向量应该和EncryptedArray具有相同的大小，由初始化的参数决定，如果输入数组中的元素不能填充密文的向量，可以用0填充，因为利用0不会改变最终的运算结果。

// Create a helper object based on the context
EncryptedArray ea(context, context.alMod.getFactorsOverZZ()[0]);

// Create vectors from the values from the arrays
// The vectors should have the same size as the EncryptedArray (ea.size),
// so fill the other positions with 0. This won't affect the result.
vector<long int> U(u, u + VEC_SIZE);
vector<long int> V(v, v + VEC_SIZE);
for (int i = VEC_SIZE; i < ea.size(); i++) {
    U.push_back(0);
    V.push_back(0);
}

利用EncryptedArray进行加密：

// Ciphertexts that will hold the encrypted vectors
Ctxt encU(pk);
Ctxt encV(pk);

// Encrypt the whole vector into one ciphertext using packing
ea.encrypt(encU, pk, U);
ea.encrypt(encV, pk, V);

计算密文的乘法，使用函数 $totalSums()$ 来计算向量中元素的和，并将结果存在向量的第一个元素：

// Multiply ciphertexts and store the result in encU
encU.multiplyBy(encV);

// Use the totalSums functions to sum all the elements
// The result will have the sum in all positions of the vector
totalSums(ea, encU);

解密，并返回解密的结果:

// Decrypt the result (i.e., the scalar product value)
ZZX result;
sk.Decrypt(result, encU);

return result[0];

注：这种方法也避免了单独对元素进行加密，但是它失去了一点灵活性，因为我们必须使用与创建的EncryptedArray大小相同的向量。

结论

综合考虑，如果仅仅计算向量的乘法，则方法二是最好的选择；若其他的操作也在密文上执行，则方法三可能是最好的选择。