Reference of EvalCoeffsToSlots function

Library Questions
1

Hi,

I am currently examining the CKKS bootstrapping code, and I am having difficulty understanding the EvalCoeffsToSlots function. Based on the code you provided, I understand that if the level budget equals 1, EvalLinearTransform is used to compute the result of CoeffToSlot. I am also familiar with the hoisted baby-step giant-step algorithm used in EvalLinearTransform.

ctxtDec = (isLTBootstrap) ? EvalLinearTransform(precom->m_U0Pre, ctxtEnc) :
                            EvalSlotsToCoeffs(precom->m_U0PreFFT, ctxtEnc);

However, when I read the description of EvalCoeffsToSlots, I was unable to grasp the computational flow of the function. Is there a reference or algorithm you can provide to help me understand it better? Although it appears that EvalCoeffsToSlots handles the CoeffToSlot process with different level budgets, I have not yet come across any relevant algorithms.

Additionally, I have noticed that the algorithm used in EvalLinearTransform appears to be the double-hoisted automorphism algorithm proposed in “Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys.” Could you clarify this point for me?

Please let me know if you have any further questions or if I can assist you in any other way.

2

See “Improved Bootstrapping for Approximate
Homomorphic Encryption” (Chen, Chillotti, Song) paper for a description of the level budget. I am not sure about your other questions.

3

OpenFHE uses double hoisting, similar to what was described in Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys. For EvalCoeffsToSlots, OpenFHE uses the collapsed FFT approach proposed in Improved Bootstrapping for Approximate Homomorphic Encryption. The OpenFHE implementation also uses some CKKS enhancements suggested in Approximate Homomorphic Encryption with Reduced Approximation Error

1 Like