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
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.