Sum of Encrypted Vectors

Recently I received a question about what would be a good way to do the element wise summation between two encrypted vectors.

I have written before about how to do the secure sum of single values using HElib and using Paillier lib, and also about how to do the secure scalar product between vectors using HElib, but I believe summing vectors is also a common thing to do, so I decided to try a few different ways to do it and compared them.

The first three methods are the same as the ones I mentioned in the inner product using HElib post (i.e., no packing, polynomial packing and subfield packing), and I also tried to do it using Paillier lib.

The source code is available at GitHub.

For all the methods, what is being done is basically initializing two vectors of fixed size (VEC\_SIZE). One contains even numbers, and the other contains odd numbers:

// Array u will have even numbers, and array v will have odd numbers
  for (int i = 0; i < VEC_SIZE; i++) {
    u[i] = 2*i;
    v[i] = 2*i + 1;
}

After that, we do three steps which depend on the cryptosystem: encryption, element wise sum and decryption.

Method 1

The first method uses HElib and encrypts the elements of the vectors individually, so we have one ciphertext for each element.

// Vectors to hold the ciphertexts created from the elements of u and v
  std::vector<Ctxt> encU(VEC_SIZE, Ctxt(pk));
  std::vector<Ctxt> encV(VEC_SIZE, Ctxt(pk));

// Each element is encrypted individually
  for (int i = 0; i < VEC_SIZE; i++) {
    Ctxt tempU(pk);
    pk.Encrypt(tempU, to_ZZX(u[i]));
    encU[i] = tempU;

    Ctxt tempV(pk);
    pk.Encrypt(tempV, to_ZZX(v[i]));
    encV[i] = tempV;
}

The sum and the decryption also work on each vector position independently:

// Sum vectors element wise. The sum is stored in U
for (int i = 0; i < VEC_SIZE; i++) {
  encU[i] += encV[i];
}

// Decrypt result
for (int i = 0; i < VEC_SIZE; i++) {
  ZZX element;
  sk.Decrypt(element, encU[i]);
  result[i] = conv<long>(element[0]);
}

Method 2

For Method 2 and Method 3, we use HElib’s very useful ciphertext packing feature to reduce the number of ciphertexts generated and, consequently, reduce the overall execution time.

The second method uses the polynomial packing, which embeds a vector’s elements in the coefficients of a polynomial:

// ZZX is a class for polynomials from the NTL library, on top of which HElib is built
ZZX U, V;                               

// Set the length of the polynomial U(x) and V(x)
U.SetLength(VEC_SIZE);
V.SetLength(VEC_SIZE);

// Set the coefficients of the polynomials U(x) and V(x).
for (int i = 0; i < VEC_SIZE; i++) {
  SetCoeff(U, i, u[i]);
  SetCoeff(V, i, v[i]);
}

The polynomials are then encrypted as just one ciphertext each:

// 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);

After that, we do the sum and the decryption of the resulting polynomial:

// Multiply the ciphertexts and store the result into encU
encU += encV;

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

The final step for this method is to unpack the polynomial into the original result form (array of integers):

// Assign the values of the polynomial's coefficients to the result vector
for (int i = 0; i < VEC_SIZE; i++) {
  result[i] = conv<long>(resultPoly[i]);
}

Method 3

The third method is similar to the second one, but uses HElib’s subfield packing. A way to think about subfield packing is that we still have the vector representation of our data (instead of transforming them to polynomials), but all the elements are packed into one single ciphertext.

Despite the similarities with the second method, one difference is that we need to create an EncryptedArray object that helps us work with this kind of packing. Another difference is that the length of the EncryptedArray depends on the context we are using (which depends on the initialization parameters) and not on the vectors we want to process. This means that if our vectors are shorter than the EncryptedArray, we just fill the rest of the positions with zero until the lengths of our vectors and of the EncryptedArray are the same:

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

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

The encryption works in a way similar to the second method:

// 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);

After that, we do the summation, the decryption and the unpacking just like before:

// Sum ciphertexts and set the result to encU
encU += encV;

// Decrypt the result
std::vector<long> res(ea.size(), 0);
ea.decrypt(encU, sk, res);

// Assign the values of the polynomial's coefficients to the result vector
for (int i = 0; i < VEC_SIZE; i++) {
  result[i] = conv<long>(res[i]);
}

Method 4

The final method I tested is to use Paillier lib instead of HElib. Since we are just doing summation, we don’t need the homomorphic multiplication provided by HElib, and the homomorphic addition property from Paillier lib is enough.

I don’t know if there are ways to do ciphertext packing using the Paillier cryptosystem (let me know in the comments if there is), so, like the first one, the fourth method also creates one ciphertext per element:

// Vectors that will hold the ciphertexts
std::vector<paillier_ciphertext_t*> encU(VEC_SIZE);
std::vector<paillier_ciphertext_t*> encV(VEC_SIZE);    

// Encrypt elements
for (int i = 0; i < VEC_SIZE; i++) {
  paillier_plaintext_t* ptxtU = paillier_plaintext_from_ui((int)u[i]);
  paillier_ciphertext_t* ctxtU = paillier_enc(NULL, pubKey, ptxtU, paillier_get_rand_devurandom);
  encU[i] = ctxtU;

  paillier_plaintext_t* ptxtV = paillier_plaintext_from_ui((int)v[i]);
  paillier_ciphertext_t* ctxtV = paillier_enc(NULL, pubKey, ptxtV, paillier_get_rand_devurandom);
  encV[i] = ctxtV;
}

Then, we use the paillier\_mul function on each pair of encrypted elements to give us the sum of the plaintext values:

// Sum encrypted vectors element wise
for (int i = 0; i < VEC_SIZE; i++) {
  paillier_ciphertext_t* encryptedSum = paillier_create_enc_zero();
  paillier_mul(pubKey, encryptedSum, encU[i], encV[i]);
  encU[i] = encryptedSum;
}

Finally, we do the decryption:

// Decrypt the result
for (int i = 0; i < VEC_SIZE; i++) { paillier_plaintext_t* dec; dec = paillier_dec(NULL, pubKey, secKey, encU[i]); result[i] = mpz_get_ui(dec->m);
}

I did not include memory management code in the snippets, but the code at GitHub does the proper cleaning.

Checking Results

For all the methods, we can check the result of the summation to confirm that it is correct:

// Checking results
  for (int i = 0; i < VEC_SIZE; i++) {
  std::cout << u[i] << "+" << v[i] << " = " << result[i] << std::endl;
}

Evaluation

Both cryptosystems used are probabilistic and give us semantic security.

Regarding the performance, I ran a few experiments to compare the methods in terms of execution time (in seconds) when summing vectors of different lengths.

The server used was an Intel(R) Core(TM) i7-2600 3.40Ghz 8GB RAM and the next figure summarizes the results:

Approaches Serial Comparison

Although all the approaches using HElib take much more time than the Paillier lib, the breakdown of the execution time (in seconds) for summing vectors of length 1000 gives an interesting insight on the reason for that:

Steps Method 1 Method 2 Method 3 Method 4
Initialization 9.4 9.4 9.4 0.003
Encryption 80.63 0.08 0.13 1.50
Sum 0.15 0.0002 0.0002 0.0004
Decryption 18.09 0.02 0.37 0.03

So we can see that HElib’s initialization takes a lot of time, and constitutes most of the execution time in Method 2 and Method 3. In fact, if we don’t consider the initialization step, using HElib with ciphertext packing gives a better performance than even the partially homomorphic Paillier cryptosystem.

Also, we see that varying the length of the vectors doesn’t affect much the execution time for the methods that use packing. Since the whole vector is encrypted as a single ciphertext, the number of elements in it didn’t have much effect using the values from 100 to 1000.

But I would imagine that this has a limit, and eventually a vector length would be too much for that size of ciphertext, so we’d need to have a bigger ciphertext that would take more time to process. I’m not sure about this though, but I’ll update this post if I find some more details about it.

Parallelization

The sum of vectors is an operation that offers opportunities for parallel processing, because the processing of vector elements is independent from each other.

I tried to do a basic form of parallelization using OpenMP, by just adding #pragma omp parallel for a few times here and there (check the code at GitHub to see where). I know there are other (and probably better) ways to do this, but I just wanted to make it a simple test that doesn’t take our focus from the security to the performance.

The following figure shows the result of the comparison between the serial and the parallel versions using 8 threads.

comparisonSerialParallel

From the figure we can see that Method 1 benefits the most from parallelization, and the others don’t show much improvement. I believe the main reason for this is the length of vectors being too short, so the performance gains don’t stand out much because the initialization phase is still the bottleneck.

Conclusion

Although ciphertext packing using HElib gives us a good scalability, the initialization phase takes a long time and, for the short vectors used in the tests, the benefits of packing are hidden by the initialization.

The comment section welcomes suggestions about other methods to do the summation of encrypted vectors as a whole or about other topics in this post.

Advertisements

2 thoughts on “Sum of Encrypted Vectors

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s