Polynomial Multiplication in CKKS

FHE Questions
1

Hello,

is it possible to perform a polynomial multiplication between two ciphertexts?

for example:

c_1 = [2, 3, 1]\\ c_2 = [1, 2, 4]\\ (2x^2 + 3x + 1) \times (x^2 + 2x + 4)

results in:

2x^4 + 7x^3 + 15x^2 + 14x + 4

I would like to extract the first three slots c_{res} = [2, 7, 15] of the resulting multiplication, would it be possible? Thank you

2

I would like to extract the first three slots

Depends on what you mean by extract, but you can multiply by a mask and that will zero out everything else that’s not of interest

3

By performing c_1 \cdot c_2 slot-wise, we would obtain [2, 6, 4], but I’d like to get the result of the actual c_1, c_2 polynomial multiplication

4

Ahh, sorry, I skimmed the numbers which led to my misunderstanding.

5

In CKKS, we only support the CRT/Evaluation encoding (you can go to coefficient encoding using the SlotsToCoef subroutine in CKKS bootstrapping). The coefficient encoding is natively supported in BGV/BFV (along with CRT encoding).

You are asking about doing a multiplication in the coefficient encoding and then doing extraction. Extraction can be done by homomorphically switching to the CRT encoding (expensive) and then doing a masked multiplication or using LWE extraction. Extracting coefficients (via LWE) in the coefficient encoding can be done using automorphisms (a subroutine for this is implemented as part of CKKS scheme switching) - this is cheaper.

At a high level, these are advanced operations that require FHE expertise.

6

So you don’t think there’s an easy way to perform it? I saw this paper in which they perform a CNN convolution using polynomial multiplication but they used lattigo

7

I checked the paper and it seems that they do not encode values “as usual”, values are encoded as polynomial coefficients (therefore they also use N slots and not N/2), I think this method has a slower ReLU evaluation and bootstrapping though, since slot-wise operations are not easy with that encoding. It is the first thing I thought when reading, but I am curious and will try to go into details!

8

@marc-alonso I think the drawback about their approach is about ReLU evaluation, since slot-wise multiplications are more difficult (check this recent thread)

Edit: ReLU was ok (is indeed computed after the CtoS step, on the re-encoded ciphertext), I think the way they consider convolutions as polynomial negacyclic convolutions is cool, it indeed avoids to run multiple multiplications and rotations. I guess the main issue is about packing LWE ciphertexts (which needs many rotation keys), but as soon as you have enough RAM, it is ok.

1 Like
9

Thank you. I got it now