Easy way to evaluate N/2 polynomials over N/2 slots

Library Questions
1

Hi everyone :slight_smile:

I have a quick question: in CKKS we can evaluate a polynomial by a set of coefficients on the whole slots of a ciphertext. Does OpenFHE allow for the SIMD evaluation of n/2 polynomials (of same degree), one for each slot? I guess theoretically it should be possible, but I don’t know if it is maybe already implemented as a subroutine somewhere or it should be written by scratch (I guess by replacing constants with plaintexts in evalpoly functions).

Thanks!

2

No, this is not implemented. And you are correct that the way to do it is to change the current implementation from scalar x vector to vector x vector, by packing the different coefficients corresponding to a power in a plaintext. Note that despite the conceptually simple changes, the implementation changes might be extensive. For one, it might be better to preprocess all the recursive long divisions done in the Paterson-Stockmeyer algorithm for the n/2 polynomials. Moreover, although the degrees of the n/2 polynomials is the same, the coefficients are different across polynomials and you won’t be able to take advantage by multiplications by zeros or ones in the coefficients.

1 Like
3

when you say

you won’t be able to take advantage by multiplications by zeros or ones in the coefficients.

you mean that the current PS algorithm, when it has to evaluate c \cdot X^k:

  • Does not add anything if c = 0
  • Simply adds X^k if c=1
  • Perform the actual multiplication otherwise

Correct? Or you mean something more sophisticated? Thanks!

4

Yes. When you have a vector of constants, some of them might be 0 or 1 but not all, and you will use a Hadamard product.