Approximation of square root without chebyshev interpolation

Hi guys,
I was searching for algorithms to approximate the square root without using Chebyshev interpolation.
I want to show you my code for implementing the algorithm from https://eprint.iacr.org/2019/417.pdf Section 3.2. It approximates the square root of values in an encrypted vector. Maybe this can also be helpful for you.

Here is my code for this algorithm:

    auto ct_a = ct_input; // make sure to scale down your input values if necessary to meet the condition 0 ≤ x ≤ 1,
    auto ct_b = cc->EvalSub(ct_a, 1);

    int d = 7; // you need to play around with this to reach your required precision. A higher d consumes more levels!
    for (int n = 0; n < d; n++) {
        auto ct1 = cc->EvalSub(1, cc->EvalMult(ct_b, 0.5));
        ct_a = cc->EvalMult(ct_a, ct1);
        auto ct2 = cc->EvalMult(cc->EvalSub(ct_b, 3), 0.25);
        ct_b = cc->EvalMult(cc->EvalSquare(ct_b), ct2);
    }

// Don't forget to scale back ct_a if you scaled it down

With this code i reach very good precision for my use case.

2 Likes

Remark: A tighter lower/upper bound on x requires less iterations.

Hi @DenisRed,

thank you for your insights.
As you are looking around for square root approximations without Chebyshev, I recommend looking into this paper.
It uses Newton’s method to approximate the function and is therefore not dependent on the range [0,1)

1 Like

Thanks for the recommendation, it’s very interesting! But I try to keep the multiplicative depth as low as possible. As your recommendation also says, the algorithm described above is the one with the lowest multiplicative depth.

Another question: Do you perhaps have a recommendation for comparing two vectors in CKKS (without changing the scheme)?

Thank you and Happy New Year!