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.