(Question) How the magic poly rp1, rp2 in bootstrapping work ?

[fionser]

Hi, I am reading the implementation of HEAANBOOT, which can work greatly. I am still digging into the math. Could anyone tell me how the rp1, rp2 polynomials in the bootContext work ?

[kimandrik]

Hello, when we do linear transformation (coeffToSlot) we have 2n non-zero coefficients of m(x) that are encrypted in a ciphertext in a way X = (m0 + i*m{N/2}, m{N/2n} + m{N/2 + N/2n}, ... ). If n < N/2 we have enough slots to pack all 2n coefficients as Y = (m0, m{N/2n}, ...). These rp1 and rp2 encodes some masks (1, 1, 1, ...1,0,... 0,0,0) and (0,0,0,...,0,1,...,1,1,1) and used to transform X to Y.

[fionser]

Hi, Does X = (m_0 + i*m_{N/2}, m_{N/2n} + m_{N/2 + N/2n}, ... ) be X = (m_0 + i*m_{N/2}, m_{N/2n} + i*m_{N/2 + N/2n}, ... ) ?

[kimandrik]

right)

[fionser]

One more question related here is that, the rp1 and rp2 transform is done AFTER the sine function. Also, before the sine function, we cancel out the real part of the encrypted coefficients by one conjugate followed by a sub. As a result, the slots should contains (i * m_{N/2}, i * m_{N/2 + N/2n}, ... ) before doing the sine iteration.

Then we iteratively evaluate the approximate sine, and then we apply the rp1, and rp1 transform, which is not well understood by me.

[kimandrik]

Oh, sorry for confusing you, you are right, we doing rp1 and rp2 transformations after the sine function (we use exp instead in the implementation) to restore the structure (m0 + i*m{N/2}, m{N/2n} + i*m{N/2 + N/2n}, ... ) from (m_i). In the coeffToSlot we used rpvec, and this rpvec is constructed in some other way if the number of slots is less than N/2 so that after coeffToSlot you already have 2*n slots instead of n slots, and in imaginary parts you already have all required m_i. I'm not fully sure here, but the intuition is like if you have less than full slots you can make some interesting linear transformation. Please check how the rpvec is constructed in void Ring::addBootContext when the number of slots is less than N/2.

[fionser]

Thanks ! It would be nice to have these optimizations documented somewhere : ).