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?
4
-
$\begingroup$ 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. $\endgroup$– Squeamish OssifrageApr 20, 2019 at 3:36
-
$\begingroup$ 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? $\endgroup$– SR007Apr 20, 2019 at 4:44
-
$\begingroup$ For some of the circuits for FHE, please look at here which includes equality under ciphertext with the result is ciphertext, too. $\endgroup$– kelalakaApr 20, 2019 at 6:16
-
$\begingroup$ 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/… $\endgroup$– Geoffroy CouteauApr 20, 2019 at 6:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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<t<\ell}g(a_t, b_t)) \mod 2$$
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.
answered Apr 22, 2019 at 6:49
-
$\begingroup$ 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. $\endgroup$– RexcirusAug 30, 2019 at 21:44