HI I’m a newbie in FHE implementation.
For my master’s thesis, I want to perform benchmarking where I need to perform a calculation where 4 participants need to compute their coordinates with each other. For this, I would like to use the Haversine formula under the CKKS bootstrapping (Multiparty). Do you believe the library can perform this calculation?"
It would be helpful to elaborate further on the use case you want to implement. Maybe there are other simpler (or FHE friendlier) methods to implement it.
What you want to calculate is likely feasible in CKKS, but the accuracy depends on the range of the arguments.
Assuming all these arguments are real numbers (since the current OpenFHE’s implementation of CKKS only supports real numbers). You need to approximate the transcendental functions using polynomials. The quality of the polynomial approximation, in terms of error, depends on the chosen polynomial degree, the argument range, and the chosen approximation algorithm. We recommend the Chebyshev polynomial approximation algorithm (which is implemented in OpenFHE), but you still need to determine the polynomial degree and the argument range. Specifically, for your calculation, you would need to approximate sin, cos, sqrt, and (division and arctan) for atan2. The division seems challenging, but if it is over a small range, you might get a good approximation. Division by 2 is straightforward since 2 is a constant, and you can multiply by 0.5.
Overall, your computation seems feasible. However, it’s also advisable to explore whether simpler methods exist to achieve the same results. In general, if possible, try to avoid divisions or transcendental functions over large ranges for better computational efficiency.
FYI: I’ll just point out that Haversine is an approximation that assumes earth is a sphere. It will not give high-accuracy results (see GIS FAQ Q5.1: Great circle distance between 2 points for suggestions based on the application domain). It really depends on how far away from each other the participants are, and how much precision and accuracy you want the answer to contain in your use case.
Dave
Hello Dave, thank you very much for your response. It’s not really about the specific calculation of the distance, but rather about benchmarking with the use of CKKS bootstrapping. That’s why the question was whether such an implementation is possible in principle. Many thanks, Hassib.