0
$\begingroup$

Im reading about FHE and the libraries implementing it (SEAL, HELib). I saw that SEAL doesn't support bitwise operations but I wondered if its theoretically feasible. For example, bitwise-ing XOR an encrypted value with itself, gets us an encrypted 0. Bitwise it with the not of itself to get an encrypted 1. Using shifts with the computed two I would then be able to extract the encrypted number. Shift right/left can be made using multiplication or division by (powers of) 2. But XOR-ing is the main problem. Is it theoretically possible under any FHE/HE scheme? What are the limitations? Thanks

$\endgroup$
4
  • $\begingroup$ Use some other library? HeLib or TFHE? $\endgroup$ – kelalaka Sep 8 '20 at 6:44
  • $\begingroup$ HELib doesn't seem to support XOR. TFHE does, and it seem interesting. I will check that, thanks! $\endgroup$ – Senia Kalma Sep 9 '20 at 21:38
  • $\begingroup$ In terms of feasibility, you can always work on single bits and implement XOR(a,b) as $a+b-2ab$. $\endgroup$ – Fractalice Oct 8 '20 at 20:18
  • $\begingroup$ Helib supports XOR. Just choose the plaintext modulus as 2. $\endgroup$ – Marcellus Jun 5 at 20:15
0
$\begingroup$

The answer to the GitHub issue specifically mentions what you're looking for

The reason why SEAL does not support bit operations is that bit operations require a non-power-of-two polynomial ring degree which leads to much less efficient polynomial arithmetic and hurts the performance of either homomorphic evaluation or encryption or both.

This states that with a non-power of 2 ring degree they could implement bitwise arithmetic, but it would hurt the performance of the algorithm.

We are evaluating the necessity and feasibility of adding support for bit operations. Perhaps we will adopt a different HE scheme for that rather than using BFV (definitely not CKKS).

This second quote states that, to avoid the efficiency issue, they would use a different homomorphic encryption scheme.

It seems to me you have your answer right there: they're confirming it's possible, and that they know how to do it. They're also confirming it wouldn't require changing the homomorphic encryption scheme. But since it would affect performance they're choosing not to.

$\endgroup$
4
  • $\begingroup$ Thanks for the comment :) I've seen that but I'm still bothered with my theoretical idea of "decrypting" the cipher: "For example, bitwise-ing XOR an encrypted value with itself, gets us an encrypted 0. Bitwise it with the not of itself to get an encrypted 1. Using shifts with the computed two I would then be able to extract the encrypted number." Why isn't it possible? By HE definitions $\endgroup$ – Senia Kalma Sep 9 '20 at 21:47
  • $\begingroup$ Consider this: they find $0$ by multiplying by $0$ or subtracting it from itself. Then, they divide the data by $2$ until they find $0$. Now they know the upper-bound and lower-bound of the data. Then, they subtract the lower bound and repeat. They effectively reconstruct the data bit-by-bit, without having to do any decryption. $\endgroup$ – Serpent27 Sep 9 '20 at 22:46
  • $\begingroup$ You would, however, need to verify this actually works. There could be many possible $0$ states, in which case you might end up wasting your time anyway. I haven't actually tested this theory, since I'm too lazy. $\endgroup$ – Serpent27 Sep 9 '20 at 23:07
  • $\begingroup$ This is what my question is about.. $\endgroup$ – Senia Kalma Jan 23 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.