I am new to this area of homomorphic encryption and I wonder how to compute a comparison between 2 ciphertexts using Microsoft SEAL. Using the BFV scheme, how could I compare 2 ciphertexts? My main goal is to find the maximum value in an encrypted array. Thanks!
2 Answers
Comparison is not implemented in SEAL. Moreover, creating an exact comparison circuit for BFV is certainly possible, but very challenging and probably would not have the kind of performance you would hope. It's very close to the complexity of bootstrapping for BFV: both require bit-extraction from batching slots.
Instead, in the CKKS scheme it is possible to implement approximate comparison algorithms which are vastly more performant, but only work in some predetermined intervals. Some recent work in this direction is in https://eprint.iacr.org/2019/1234. This is probably going to be the approach you'll want to take, unless you have some very strong reason to use BFV.
There are novel methods to perform exact comparison in BFV/BGV, implemented using Helib, yet they require a particular form of encoding that might be hard to reuse for other SIMD operations (multiplication/addition).
Related