I’m currently working on a compiler to translate C++ code to OpenFHE C++ equivalent. I’m mainly focusing on scheme switching capabilities between CKKS and FHEW. As far as I’m aware, Evalsign is the only available library function (well other than floor and decomp) in binFHE that works on high precision LWE ctxts (large plaintext moduli p). My main goal is to do high precision computations other than Evalsign after switching from CKKS to FHEW.
There seems to be a branch named “sch-swtch-changes-2” in the repository which adds support for conversion of high precision FHEW ctxts to CKKS. Can this branch be used for my use case?
Is it possible to do computations other than Evalsign (for example AND) on high precision FHEW ctxts generated from CKKS scheme switching? from looking at previous discussions there seems to be a Decomp function that decomposes a ctxt into smaller precision ctxts. I’m not sure how to use this function to do high precision computations. Is there any code example of the decomp function being used for implementing high precision operations in FHEW?
There are several layers to your question, so let me approach this in a systematic way, especially since “high precision” can have different meanings depending on the context.
First, you can switch any CKKS ciphertext to FHEW ciphertexts by appropriately selecting the Q modulus for the FHEW ciphertexts (which will support a maximum plaintext size of Q/256). Then, you can write your own code to process these FHEW ciphertexts. However, currently in the main branch, returning from FHEW to CKKS requires the encrypted messages to be small compared to the plaintext modulus. The reason for this is that modular reduction via sine approximation requires messages to be very small to work, which implies the constraint of m << p. By using a higher order sine approximation or homomorphically composing with arcsine allows one to switch messages of up to p/4 (but this p/4 is an inherent limitation). This is what the code in sch-swtch-changes-2 does for arcsine approximations of various degrees and sine series approximations. You are welcome to use that code and choose the best trade-off between cost in terms of levels and precision of the result for your application (currently, the arcsine approximation of degree 6 is enabled, you can change the coefficients for other degrees between 4 and 7 or uncomment the code for sine series approximation of 4th order). If you need to switch messages higher than p/4 back to CKKS, you can break the FHEW message in pieces each up to p/4, switch them to CKKS, and them re-combine them in CKKS.
Second, about the high-precision computations in FHEW. Theoretically, you can perform functional bootstrapping in FHEW for any plaintext/ciphertext modulus; the problem is that it becomes prohibitively slow for plaintext moduli larger than 6-8 bits. Therefore, you should decompose the FHEW ciphertexts into small digits, and perform the functional bootstrapping over the digits. Sign-like computations can be expressed as a chain of look-up tables over the digits (obtained by doing homomorphic floor) https://eprint.iacr.org/2021/1337.pdf, which is what is implemented in OpenFHE. For other functions, you should come up with a way of writing it by combining look-up tables on each digit; see some ideas in Revisiting the functional bootstrap in TFHE | IACR Transactions on Cryptographic Hardware and Embedded Systems.
For a function such as AND, try to think of the best way of expressing it based on digits. For instance, you could split each ciphertexts into digits, perform an AND gate over each corresponding pair (e.g., via a look-up table and EvalFunc for digits larger than bits), then AND the result of each pair etc. Alternatively, you can convert the results from the first AND back to CKKS and multiply the results there.
Thank you for you thorough response. I’ve been looking into the links and playing around with the OpenFHE look up table functionality, and I understand what I need to do. However, I seem to be having an issue with a mismatch between the output of the EvalDecomp function and the look up table functionality. For example, in the SwitchCKKSToFHEW function in this link, the digits of the decomposed ctxts are in base 16 (so a digit can be between 0 and 15), but lookup tables support input between 0 and 8. When I try to process each digit with a look up table like below, it throws an error.
auto fp = [](NativeInteger m, NativeInteger p1) -> NativeInteger {
return m / 2;
};
Is there anyway around this?
I tried setting the arbitrary functionality to true (so it decomposes to base 8) using this:
Unfortunately, the experimental scheme switching capability was not integrated with the arbitrary large-precision function evaluation for FHEW in OpenFHE, since the implemented arbitrary function evaluation is limited. You would need to indeed change the internals to add separate parameters for the large precision Q (to not be overwritten by 2048 in the arbitrary function case), so that EvalDecomp would still work, and to make sure the bootstrapping keys are generated and stored correctly for all parameters.
On a related note, a more powerful capability than the CKKS<->FHEW scheme switching is https://eprint.iacr.org/2024/1623.pdf. We are focusing on this now, but it will take some time before we can integrate it in OpenFHE.
I agree with @andreea.alexandru The current capability is primarily focused on large-precision EvalSign (comparison-like operations) and small-precision (3-bit) arbitrary LUT. One can extend small LUTs to large LUTs using the tree- or chain-based method + EvalDecomp, but this is outside the scope of the current OpenFHE implementation. If you decide to add large-precision LUT support to OpenFHE, we would be glad to consider this contribution.