Hmm, this is a point of confusion for me then, because isn't that exactly what FHE allows you to do (and in fact its entire point)? HE allows you to add or multiply encrypted values, and FHE extends HE so that you can perform arbitrary computation. That must mean the == operator is supported, so it seems like it must be possible to do this.
Also, thank you for talking through this with me. It's much appreciated.
FHE doesn't extend HE in the sense that it adds operation types other than addition and multiplication but it allows unlimited chaining of the two operations. This in turn enables arbitrary operations because you can express any function (i. e. any chain of atomic operations) by means of additions mod 2 and multiplications mod 2 (which is equivalent to XOR and AND) when you turn it into a boolean circuit representation. The contribution of FHE is a way to a) clean operands from noise or to b) do not add noise to the operands in the first place because noise is the limiting factor for circuit depth in HE, where "depth" means the number of possible subsequent multiplications.
> That must mean the == operator is supported, so it seems like it must be possible to do this.
OK, I understand what you meant with the code now, but the problem is you won't know the answer to your equality comparison. In the same way that add(encryptedIntegerA, encryptedIntegerB) gives you encryptedIntegerC whose value is unknown but which you know decrypts to a + b, you know that equals(encryptedIntegerA, encryptedIntegerB) results in encryptedBooleanC, but you don't know whether that decrypts to true or false. So what do you execute next? It's not that it doesn't know until runtime which branch to take; it's that it doesn't know ever. The whole point FHE is that the executing machine doesn't know the answers themselves, just what they encrypt to. So I'm not sure--no matter how much meta eval you make it do--how it can decide what code to actually execute without decrypting something.
Edit: though I appear to be wrong about this. From Wikipedia:
If the morphisms of some wide supercategory of C include the primitive recursive functions or even all computable functions, then any encryption operation which qualifies as an endofunctor of this supercategory is "more fully" homeomorphic since additional operations on encrypted data (for example conditionals and loops) are possible.
That certainly supports your point. I suppose--more speculation by me-- it must compute both sides of the conditional (in this case, execute the OP_ADD branch and the OP_MULT branch) and then pick one in a way that makes it impossible to tell which "won". That would make a bytecode interperter really impractical, since it would have to compute a huge superset of what any actual bytecode program does, but not logically impossible.
You don't need to know the answer, though.
if (x == 5) { print "hello world"; }
else { print "goodbye world"; }
If I'm wrong about this, I don't understand why.
The ability to evaluate statements such as x == 5 falls under the realm of functional encryption ( see Boneh, Sahai, and Waters for a good intro http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.383... ).
You have to be very careful when mixing functional schemes with FHE schemes as it is very easy to create a completely insecure system.
For example, if you could evaluate arbitrary circuits consider what happens if you can evaluate equals and bitwise AND, two simple circuits.
({x}&{0x1}) == {0x1}
({x}&{0x2}) == {0x2}
({x}&{0x4}) == {0x4}
One more thing worth mentioning is that a direct comparison of ciphertexts doesn't work for semantically secure schemes. Anything that is IND-CPA, for example RSA-OAEP, will have the same plaintext encrypt to two different ciphertexts. Giving the untrusted server the ability to determine whether two ciphertexts will destroy the semantic security of the scheme, by definition.
Think of it this way: A conditional is "if this, do that." If the conditional is true, then the branch is executed. The output of the branch is still encrypted, but it's not true that you need the decryption key just to evaluate the branch. Right?