The trick would be to test if if op == OP_ADD when decrypted
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 extends HE so that you can perform arbitrary computation
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.
You're very welcome, this is totally fun, and hopefully we'll both come out wiser.
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.
The output of the above program would be either "hello world" or "goodbye world". The output is encrypted, so you won't be able to tell. However, it's not true that you needed the decryption key to evaluate "x == 5". That must mean you can do arbitrary conditionals, loops, branching etc without the decryption key.
Did you see my edit above? I think you're right based on working back through the Wikipedia FHE article, but I also think it would mean executing every possible path, i.e. you'd need to at least evaluate "hello world" and "goodbye world", since the computer executing it doesn't know which it turns out to be. As applied to a bytecode interpreter, that would seem to mean it has to execute every possible program the same length as your bytecode, since it doesn't know what any of them do.
Keep going for all the powers of two expressible in the system and you can quickly check if every bit is set. This makes proving security for functional schemes that allow malleability very difficult, since you have to prove that the reachable set of states with the built in malleability does not reveal sufficient information for the attacker to compromise the security of the system.
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.
If you can do arbitrary computations, you can do loops and conditionals and whatever else you want. FHE claims to support arbitrary computations, so by definition it must support the ability to do any loop or any conditional.
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?
Comments
The trick would be to test if if op == OP_ADD when decrypted
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.
You're very welcome, this is totally fun, and hopefully we'll both come out wiser.
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.
the problem is you won't know the answer to your equality comparison.
You don't need to know the answer, though.
The output of the above program would be either "hello world" or "goodbye world". The output is encrypted, so you won't be able to tell. However, it's not true that you needed the decryption key to evaluate "x == 5". That must mean you can do arbitrary conditionals, loops, branching etc without the decryption key.If I'm wrong about this, I don't understand why.
Did you see my edit above? I think you're right based on working back through the Wikipedia FHE article, but I also think it would mean executing every possible path, i.e. you'd need to at least evaluate "hello world" and "goodbye world", since the computer executing it doesn't know which it turns out to be. As applied to a bytecode interpreter, that would seem to mean it has to execute every possible program the same length as your bytecode, since it doesn't know what any of them do.
tl;dr here be dragons.
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.
Keep going for all the powers of two expressible in the system and you can quickly check if every bit is set. This makes proving security for functional schemes that allow malleability very difficult, since you have to prove that the reachable set of states with the built in malleability does not reveal sufficient information for the attacker to compromise the security of the system.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.
You can do arbitrary computations, but you only get the encrypted result. So you can't actually tell whether x == y unless you have the key.
If you can do arbitrary computations, you can do loops and conditionals and whatever else you want. FHE claims to support arbitrary computations, so by definition it must support the ability to do any loop or any conditional.
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?