About implementing sgn(x) function

[narger-ef]

Hello everyone, I've got a question about implementing f_1(x) function from this paper (page 12) in CKKS scheme.

My question is about scales: the function gives a result that has been scaled (at least) three times (the first term needs to square and to multiply twice), but I run the function multiple times (let's say 10, so I'm sure that it will converge), does that mean that I need to "go down" by 30 chain indexes? Or is there a way to "ease" the chain index from one function call to another?

I'm asking because, putting the function inside an hypothetical program that runs a cycle of 1000 iterations, I would need 30000 chain indexes...

Thank you in advance for your time!

[Pro7ech]

You will need ceil(log2(degree(f_1(x))+1)) levels per call of f_1(x). If you want to chain 10 iterations on the same value using an f_1(x) of degree 4 to 7, then you are correct, you will need 30 levels.

Note that their technique only works for values between -1 and 1. If your values are outside of this interval, you need to normalize them, which will compress already small values even more near the origin and require more iterations to account for the worst case.

[narger-ef]

Currenlty I'm assuming that all the values are in [-1, 1], I'm gonna face that problem later :D

For what concern the second question, is what I wrote correct?

[WeiDaiWD]

By f_1(x) do you mean -0.5x^3+1.5x? You can rewrite this expression to -0.5(x^2+3)x. First there is a square on x, after which is the first rescaling. Then (x^2+3) is multiplied by x, after which is the second rescaling. Naively, multiplying by -0.5 requires a third rescaling. Then for 1000 iterations, you will need 3000 rescalings, therefore 3000 "chain indexes".

A better way is as follows:

1. compute -0.5x and rescale;
2. compute x^2 and rescale;
3. compute -0.5x * (x^2+3) and rescale. The difference here is that step 1 and 2 consumes the same "chain index" since they can be operated independently. Therefore after 3 steps only 2 "chain indexes" are consumed.

[sloede]

Just as a practical question: What is the maximum useful algorithmic depth for the CKKS scheme, if you want at least 128 bit security and approximately single precision accuracy? 3000 chain indices sounds to me like a theoretical number, but maybe Ia m missing something here?

[WeiDaiWD]

With 32768 degree and 128-bit security, 20+ chain indices with ~40-bit primes that might be able to preserve single precision accuracy. This varies largely in reality depending on the application. I'm just giving a rough estimate here. With 65536 degree, 40+. You see how it grows.

A larger degree means much slower computation. We rarely use 65536 or more. Truly 3000 is not feasible. With bootstrapping, the chain indices can be reset, then 3000 is doable. Bootstrapping is extremely slow. I won't say that 3000 is practical with bootstrapping.

[sloede]

@WeiDaiWD Thanks for this estimate. Bootstrapping is not implemented in SEAL, though, and not available for CKKS in general, right?

[narger-ef]

I think I got it, even though I don't understand how to put such a calculation into practice.

I mean: in order to get a decent result, f_1(x) needs, let's say, almost 7/8 iterations; this means 7 * 2 = 14 chain indexes "spent" on it.

With 2^15 = 32768 as a degree, we're not even able to run two times sgn(x)... Putting into perspective, a sgn(x) function is just a little piece of a larger puzzle, so how to handle this situation if bootstrapping is not an option?

[WeiDaiWD]

@WeiDaiWD Thanks for this estimate. Bootstrapping is not implemented in SEAL, though, and not available for CKKS in general, right?

BFV/CKKS bootstrapping are implemented internally for a proof-of-concept. It is not yet fully integrated into SEAL's latest version and current is not planned for release. We are seeking a way to add bootstrapping while keep SEAL's API user-friendly. I believe that the HEAAN library or the HElib library might have CKKS bootstrapping available for use.

[WeiDaiWD]

I think I got it, even though I don't understand how to put such a calculation into practice.

I mean: in order to get a decent result, f_1(x) needs, let's say, almost 7/8 iterations; this means 7 * 2 = 14 chain indexes "spent" on it.

With 2^15 = 32768 as a degree, we're not even able to run two times sgn(x)... Putting into perspective, a sgn(x) function is just a little piece of a larger puzzle, so how to handle this situation if bootstrapping is not an option?

sgn(x) can also be approximated by a polynomial with degree 5, 7, or more. If you search for the proceedings of the iDASH Privacy and Security Workshop, there should be more than one papers that implemented several iterations of sgn(x) without bootstrapping.

[narger-ef]

Can you please link an example paper ? I searched for iDASH Privacy and Security Workshop but there are tons of different papers... can you please give me a tip about where to search better without reading all the papers ? :P

[WeiDaiWD]

This paper section 2.6.