Can we query an encrypted vector and output matching values?

FHE Questions
1

Hey guys I’m still trying to figure out the possibilities i have with this library. I was wondering if I could also create some kind of “queries” to get values out of an encrypted vector, that match the condition.

Just think of a vector that acts like a database:

vector<double> v = {0.4567, 1.4567, 0.4634, 5.7870, 2.9087};
auto ct_v = Enc(v);

The query is: “Give me all values lower than 1 out of ct_v”
The result i would wish for is (pseudocode):

auto ct_result = queryEncVector(ct_v, condition);
Plaintext ptResult;
cc->Decrypt(sk, ct_result, &ptResult);

So the result vector looks like this:

ptResult = {0.4567, 0.4634};

So I know there is not straightforward way for this but i wonder how that could work with the operations we have. Do you have an approach for this?

2

You need to implement a homomorphic comparison - less than in your case.

  1. Evaluate less than on your vector to get an encrypted indicator vector of ones and zeros - one where ‘less than’ is true, and zero otherwise.
  2. Multiply the encrypted indicator vector with your encrypted data point-wise and return the result.

Implementing homomorphic comparison is possible but quite involved. Check the literature on that considering the scheme(s) you work with.

1 Like
3

I have to roll out this topic again. I have implemented this and it works well so far. However, I then have unnecessary zeros or approximate zeros in some places. Is there a way to remove the zeros from the encrypted vector and only keep the digits that have been multiplied by 1?

And perhaps an additional question:
Does the size of the ciphertext increase with the number of values in the vector?

4

If you mean compressing below original vector size, then the simple answer is no (unless something really complicated/expensive is done). Each ciphertext should be treated as a vector of constant size.

The ciphertext supports a maximum number of slots (equal to ring dimension in BGV/BFV and half the ring dimension in CKKS). Up to the maximum number of slots (we often call it as the batch size), the size of the ciphertext is not increased. If you go beyond the batch size, then you need another ciphertext.

5

Thanks for this information! So, theres no need for reducing the vector size inside a ciphertext because the size of the ciphertext is the same with 1 value and 10.000 values . Is that right?

6

Yes, this is correct.

1 Like
7

@Caesar can you tell me what you exactly meant by multiplying point-wise? You meant in a SIMD manner or is there another way?

8

It means component-wise as in the Hadamard product. The alternative is polynomial (convolution) multiplication, which is not SIMD.

9

@ypolyakov thanks your reply. Can you provide a Code example bc i have no idea how to do that.=(

10

This is the default behavior when you multiply two ciphertexts where each encodes a vector in slots: the resulting ciphertext will contain the element-wise product.