Optimization of Homomorphic Comparison Algorithm in RNS-CKKS Scheme

Library Questions
1

Hi there,
Are you planning on implementing in CKKSrns module the following comparison methodolagy:
“Optimization of Homomorphic Comparison Algorithm on RNS-CKKS Scheme” by Lee et al.?
Thanks.

2 Likes
2

We are not currently planning to add the method proposed in Optimization of Homomorphic Comparison Algorithm on RNS-CKKS Scheme to OpenFHE. We recently developed an alternative approach that is already implemented in OpenFHE: Large-Precision Homomorphic Sign Evaluation using FHEW/TFHE Bootstrapping See section 8.2 of the paper for the comparison between these approaches. We will also add scheme switching in v1.1 to support the use of the FHEW/TFHE approach in a CKKS setting.

Note that OpenFHE currently supports an evaluation of an arbitrary function using Chebyshev interpolation; see openfhe-development/FUNCTION_EVALUATION.md at main · openfheorg/openfhe-development · GitHub for details.

1 Like
3

Thank you Yuriy, this was very helpful.

How about comparison in BGV/BFV?
Is there a better way of doing it in openFHE than Fermat’s little theorem (with regarding to multiplicative depth and number of computations)?

4

To the best of my knowledge, the most efficient approach is Faster homomorphic comparison operations for BGV and BFV It is not currently supported in OpenFHE. We may add support for this after adding the bootstrapping for BGV/BFV (only a prototype of this has been written). The high-level idea is that this comparison method requires fast polynomial evaluation, e.g., using Paterson-Stockmeyer method, that is also needed for digit extraction in bootstrapping. Currently we support it only for CKKS and CKKS bootstrapping. It will take a while before we add this BGV/BFV comparison method to OpenFHE.

5

Hi, is it possible to apply the BGV/BFV comparison method in that paper to CKKS?

6

It would not be a trivial task (and probably not possible) as this approach is based on finite fields. It is better to use other approaches for CKKS.

7

Hi Yuriy, thanks for your reply. I see that the BGV comparison is built upon the polynomial interpolation, which is based on the finite field. And since CKKS operates on real numbers, it is reasonable that the interpolation based method is not (directly) appliable.