Comparison on Gentry's Fully homomorphic Encryption? [duplicate]

This question already has an answer here:

This topic is very new to me. Is it possible to do comparison on the encrypted data(data is encrypted using Gentry's FHE)? If so, how can it be done?

marked as duplicate by Geoffroy Couteau, AleksanderRas, Squeamish Ossifrage, kelalaka, Maarten Bodewes♦Apr 23 at 9:23

• I assume you mean you want a circuit that is applied to the ciphertext. Do you mean for the result of the comparison to be encrypted or not? If the result is to be encrypted, then you can presumably just compile a comparison circuit on plaintext so that it operates homomorphically on ciphertext. If the result is not to be encrypted, this would kinda damage the security of the encryption. – Squeamish Ossifrage Apr 20 at 3:36
• This is the scenario, I have two numbers a=4, b=8, I encrypt these two numbers using Gentry's FHE c1, c2. I need to check if c1 is greater than c2. Do I need to compile a comparison circuit on plaintext in this case? – SR007 Apr 20 at 4:44
• For some of the circuits for FHE, please look at here which includes equality under ciphertext with the result is ciphertext, too. – kelalaka Apr 20 at 6:16
• Hello, welcome on the website! Remember to search through the site before asking a question, since many questions were already answered. Here is a highly related question: crypto.stackexchange.com/questions/57714/… – Geoffroy Couteau Apr 20 at 6:43

Yes, it is possible. I remember at least of the article Low Depth Circuits for Efficient Homomorphic Sorting in which comparisons are discussed.

Encrypt you $$\ell$$-bit integers $$a$$ and $$b$$ bit by bit generating to $$\ell$$-dimensional vectors $$(a_1, ..., a_\ell)$$ and ($$b_1, ..., b_\ell)$$.

Than, to test homomorphically whether $$a \le b$$, do

$$C_{LT} = \sum_{k=1}^{\ell} (f(a_k, b_k) \cdot \prod_{k

Where $$f(a_k, b_k) = b_k \cdot (a_k + 1) \mod 2$$ is "less than" for bits and $$g(a_t, b_t) = b_t + a_t + 1 \mod 2$$ is a "equal to" for bits.

Notice that the product from $$k$$ to $$\ell$$ can be performed in depth $$\log(\ell - k)$$ instead of in depth $$\ell - k$$.

You will probably find other results about homomorphically comparison by searching for articles that cite the one I put here.

• Thanks for the reference, but there are some typos with respect to the paper. Also in the paper f appears two times with b (in your notation), that one should be a typo of the paper. – Rexcirus Aug 30 at 21:44