Which bitlevel operations must a fully homorphic crypto system support?

Question

My question is: If I want to develop an turing complete programming language (for example some kind of assembly language) on top of a homomorphic encryption system, which bitlevel operations does this encryption system need to support so we can carry out all sorts of functions?

Bonus question: What operations is a usual CPU capable of carrying out at the lowest level? Because if you look at the number of operations in the x86 assembly language it seems obvious not all of them are supported a the lowest hardware level.

Answer 1

Any set of functionally complete operations should be sufficient. As SEJPM says in his comment this could be simply the NAND operation as it is complete on its own. Thus a good test to see if the supported set of operations is complete is to check if you can use them to evaluate the NAND operation.

AFAIK many FHE schemes supporting Boolean operations are built to support the AND and XOR operations. These are actually not complete on their own as you also need an operation that outputs the constant 1 (in order to implement the NOT operation together with XOR). This, however, is easily achieved in FHE as you can simply use the public key to encrypt the value 1.

Answer 2

Likely none of the homomorphic Gates will be directly supported by your Hardware. The problem isn't the operation needed to express the gate, but actually the scale of the operation needed to securely evaluate the gate.

In some homomorphic encryption systems, You could perform optimizations by studying how much noise certain Gates introduce and restructuring them. This can also work in the circuit level. This, however, still does not reduce the problem to practical.