Efficient slot-wise masking operation in CKKS

[yyang172]

For a given ciphertext that encodes a vector of size N/2, a slot-wise masking operation is defined as multiplying this ciphertext with a plaintext, where the N/2 numbers in the plaintext are either 1 or 0.

A simple solution is to multiply the ciphertext with the plaintext. I wonder if there are other implementations that is more efficient (in terms of time complexity or run time) than the simple solution?

[Pro7ech]

Plaintext multiplication in CKKS is actually one of the most efficient operation (its a series of point-wise vector multiplications if both operands are in the NTT domain), hence it has the same order of magnitude of a ciphertext-ciphertext addition (not including the following rescaling operation). The main downside of masking is that it consumes a level. However, this can be mitigated by including the masking in the previous operation if it also makes use of plaintext multiplication and/or by using a smaller scale for the plaintext mask.

[yyang172]

Thanks for the explanation!

Could you explain how to avoid one additional level by using a smaller scale for the plaintext mask?

Is it possible to implement this in SEAL?

[Pro7ech]

You cannot "avoid" consuming an additional level, but you can reduce the number of bits of the total modulus Q that you use by using smaller scales for plaintext multiplications. This allows to allocate more bits to the ciphertext-ciphertext operations as these require a proportionally larger scale to get the same precision. However, if your goal is only to use less primes in total (for computational efficiency), regardless of the number of bits consumed, you can allocate a prime that is twice the scale that you will use for your operations. This way you can do two multiplications using one prime only.

[yyang172]

I remember that in CKKS the size of each prime should be roughly the same (in terms of the number of bits). Is this statement correct?

From your description, it seems different primes which have significantly different size can be selected for different purposes (e.g., for masking or for normal ct-ct mult). Is my understanding correct?

Another question... how do we find out the scale that is used in SEAL CKKS (so that we can select the prime ~twice the size)?

[Pro7ech]

There is no special requirement for the modulus used in RLWE based scheme outside of an upper bound on its bit-size given the ring degree and the error distribution. So as long as the product of all your primes remains equal or smaller than the upper bound given by your security parameter you are good to go and can chose any size for the primes.

For a given circuit you can optimize its bit-consumption by selecting each prime independently, such that each step of the circuit preserves a similar precision. Doing so, instead of having all primes be the same size, can sometime lead to a reduction in the total consumption of modulus that is large enough to allow you to use a smaller ring degree, which makes everything more efficient.

To select the primes accordingly you have to compute yourself what will be the scale of your ciphertext at each step of your circuit.

[yyang172]

Hi @Pro7ech

I try to implement this on SEAL. Regarding your comment this can be mitigated by including the masking in the previous operation if it also makes use of plaintext multiplication:

This is what I want to achieve:

pt x ct x mask0 pt x ct x mask1 ... pt x ct x mask_n

I can change the order of operation to:

pt x mask0 x ct pt x mask1 x ct ... pt x mask_n x ct

The pt x mask_i operations have to be performed on the fly (not offline). In that case, I think we need to do mod_switch (rescale) after the the pt x mask_i operations. So although we save one level on the ciphertext, we pay an extra mod_switch on the plaintext. Is my understanding correct?

[WeiDaiWD]

@yyang172 Set the scales of pt and mask to half of the scale of ct; set the scale of ct to the next prime to drop; perform one rescale after pt x ct x mask0.