HElib-2 向量内积

(29) 2024-03-24 10:01:01

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

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

以下介绍三种方式可以在密文下进行运算,首先假设已经初始化(需要的公共参数以及密钥都已经创建好了), VEC_SIZE V E C _ S I Z E 表示输入向量的大小(此处为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 c i p h e r t e x t   p a c k i n g 操作,将整个向量加密成一个密文。

方法二:

将向量中的元素编码成多项式的系数,对于向量 u u ,得到多项式

u ( x ) = 1 + 2 x + 3 x 2 + 4 x 3
.
可以通过将一个向量编码成的多项式乘以另一个向量以“逆形式”编码的多项式(比如向量 v v 的逆形式为

v ( x ) = 4 + 3 x + 2 x 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_SIZE1 V E C _ S I Z E − 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() t o t a l S u m s ( ) 来计算向量中元素的和,并将结果存在向量的第一个元素:

// 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大小相同的向量。

结论

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

THE END

发表回复