3 ms·

if (op == OP_ADD) { /* interpret addition bytecode */ } where "op" is encrypted data. Ah, but that's why it doesn't work. The trick would be to test if if

if (op == OP_ADD) { /* interpret addition bytecode */ } where "op" is encrypted data. Ah, but that's why it doesn't work. The trick would be to test if if op == OP_ADD when decrypted, which is precisely what you don't know. If you're merely testing that op == OP_ADD as an encrypted value (i.e. OP_ADD is actually the encrypted form of your add opcode), then the program is actually not encrypted, but merely has annoying-to-read semantics. To analogize: it's like encrypting a password on the client before sending it to the server, and then just straight string comparing them; it means your passwords aren't encrypted on the server, merely that your passwords are uglier than what the user entered.

sillysaurus3 12y ago
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.
- zwegner 12y ago
  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.
  - sillysaurus3 12y ago
    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?
- icambron 12y ago
  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.
  - sillysaurus3 12y ago
    the problem is you won't know the answer to your equality comparison. You don't need to know the answer, though. if (x == 5) { print "hello world"; } else { print "goodbye world"; } 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.
    - icambron 12y ago
- hcrypt 12y ago
  >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.

sillysaurus3 12y ago

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.

zwegner 12y ago
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.
- sillysaurus3 12y ago
  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?
icambron 12y ago
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.
- sillysaurus3 12y ago
  the problem is you won't know the answer to your equality comparison. You don't need to know the answer, though. if (x == 5) { print "hello world"; } else { print "goodbye world"; } 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.
  - icambron 12y ago
hcrypt 12y ago
>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.