I am trying to implement a simple version of the (cleaning) binary bootstrapping introduced in [BCKS24] for bits. In particular I constructed another function in ckksrns-fhe.cpp called EvalBootstrapBinary and I would like to work there.
I am starting from a copy-pasted version of the bootstrapping, where the function to be approximated is:
f(x) =\frac{1}{2\pi} \sin(2\pi x K).
Since I am using encapsulated secrets, I know that K=16. Also I am aware that this is approximated using a combination of Chebyshev + 3 double angle iterations. What I am missing is about some scaling performed in the raised ciphertext and implicity in the precomputations. If I had to change f(x) to something like
f_\text{bin}(x) = \frac{1}{4\pi} (1- \cos(4\pi x K))
where zeros and ones lie on the bottom and top part of the function, how the scaling of the function should be set? (figure follows)
I am not sure I understood your question. Is your question about bootstrapping or about functional evaluation with identity for bits? In the latter case, the function you want to evaluate is f_\text{binboot}(x) = \frac{1}{2}(1 - \cos(2\pi x)) = 1 - \cos^2(\pi x) = ... and continue with the double-angle formula. The initial function is of course on [-K, K]. The output will not be scaled (unless you add additional scalings in the process).
Thanks for the answer! So you are right that my use case is simply the identity bootstrap, I am working with bits and I simply want to reduce a bit the error while bootstrapping.
I got the idea of the function to be used, I think Its more of a engineering problem…
The sin-based function used in the “standard” bootstrapping should be replaced with the one you mentioned (based on cos). Let us ignore the double angle thing, I guess the f_\text{binboot} function you mentioned should have local maximum in x=1, periodically (so that cleaning actually works). However, due to scalings, the actual openfhe input will not be really in x=1, am I correct?
For instance, I saw that, in EvalBootstrap the content of the ciphertext is scaled by something like
\text{pre} * 1 / (k * N)
before the actual ctos->modred->stoc. In such case, the f_\text{binboot} function should be scaled accordingly… Also, I noticed that CtoS and StoC apply some scaling, and the output of the bootstrapping is also scaled by a correction factor (something like 256), so I should take that into account as well.
So the question I’m trying to answer is how would I change the f_\text{binboot} to work in the openfhe bootstrapping pipeline. Or, linking to my previous question, how should I tweak f_\text{binboot} in such a way that given x=1, it will output 1 (with reduced noise).
Finally, here’s my question: which are the scalings applied to the input before and after the application of the “mod reduction” function?
The CKKS-only binary functional bootstrapping has the following order of operations, StC → ModRaise → CtS → EvalFunc. Both the message and the overflows need to be in slots, because you want to evaluate a function on the message too, not just to remove the overflows. We will merge this flavor of CKKS bootstrapping in v1.5 (it is already implemented, you can check the PR).
In your case, with this order:
the pre scaling is optional, so start by removing it.
the division by N is cancelled out by CtS, which happens before the function evaluation.
the division by k is to bring the input to the Chebyshev interpolation to [-1, 1].
In conclusion, you would not need to scale your function.
I see! So since we work over the message we must use the StC-first type of bootstrap, correct?
Edit: is it my understanding correct that if one runs StC \rightarrow ModRaise \rightarrow CtS and prints the content of the ciphertext will obtain (approximately) the original messages m_i + q_0k for some (random) k \in [-K, K]?
Edit 2: i checked manually and it seems like that:) thank you for your help
but lemme know