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.

  • 2
    $\begingroup$ The NAND operation is complete. Only given NANDs, all combinatorial circuits can be built (and are in fact built on modern CPUs). $\endgroup$
    – SEJPM
    Sep 11, 2016 at 12:56

2 Answers 2


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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