4 ms·

Agreed, it's fun to speculate! I love this stuff. So my understanding of FHE is that it can take an arbitrary circuit (any arbitrary program) and convert it i

Agreed, it's fun to speculate! I love this stuff. So my understanding of FHE is that it can take an arbitrary circuit (any arbitrary program) and convert it into a circuit which operates on encrypted data. That means it must be possible to write the equivalent of if (op == OP_ADD) { /* interpret addition bytecode */ } else if (op == OB_MUL) { /* interpret multiplication bytecode */ } ... etc, where "op" is encrypted data. By extension, you can write an entire interpreter for encrypted bytecodes. Now, when the program executes, it's obviously possible to monitor it and watch what's being done. However, until it executes, the bytecode remains secret. That means it should be possible to ship programs which are impossible to analyze until they're actually executed. It's a common malware technique to write a program which contains an encrypted subprogram, which is only decryptable on a certain target machine. (For example, you could use a specific computer's MAC address as an ecryption key, which means no reverse engineer can analyze it except on that specific machine.) FHE, on the other hand, provides the opportunity to ship a turing-complete interpreter to everyone, which executes encrypted bytecodes which can't be analyzed until execution time. That means a FHE program could be a timebomb set to wipe your harddrive at some specific date and you wouldn't know it, since the best you could determine beforehand is "this interpreter sometimes tries to execute shell commands" without actually seeing which commands it's capable of executing in practice until it's too late.

icambron 12y ago
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.
deleted 12y ago
[deleted]
hcrypt 12y ago
>Now, when the program executes, it's obviously possible to monitor it and watch what's being done. That's the trick. It isn't. Let's loosely stick to your example. if (var == op) { do this } else { do that } This, when compiled for the hcrypt VM, turns into something like 0 La var //look at var 1 CMPa op //var==op? 2 BEQ 5 //yes 3 <do that> 4 JMP 6 5 <do this> 6 <continue> The obvious question is: How do you hide what branch is taken? The hcrypt VM (as all processors and TMs) is a state machine. The states essentially are the status flags (zero result, addition overflow, minus result,...) and the program counter PC. In line (address) 1, the machine decides, whether op is equal to var and sets the zero-flag to 1 if this is the case. The comparison is an implicit subtraction, so if the two values are equal, then the result is 0 and the zero flag switches to 1. In the next machine cycle (PC is 3) we want to branch. The branch operation is just a simple assignment (PC=address). The assigned value can be expressed bitwise PC = ((branch AND zero-flag) XOR (PC+1 AND !zero-flag)) Case 1: var==op PC = ((5 AND 1) XOR (3 AND 0)) Case 2: var!=op PC = ((5 AND 0) XOR (3 AND 1)) Thinking in wires, this is the implementation of a demultiplexer or selector. This is the essential curcuit for the hcrypt VM and oblivious to an observer. The most basic application is the command selector. Assume, we have the opcode in a register OP and the operands in OP1 and OP2. The ALU then operates like res_add = OP1 + OP2 res_sub = OP1 - OP2 res_mul = OP1 * OP2 res_div = OP1 / OP2 result = ((res_add AND OP==ADD) XOR (res_sub AND OP==SUB) XOR (res_mul AND OP==MUL) XOR (res_div AND OP==DIV)) Since all the operands and registers (this incudes the machine opcodes) are encrypted, the observer does know, she's looking at a branch selector or an encrypted ALU but she cannot decide what branch is taken or what operation is executed.
- sillysaurus3 12y ago
  Wow, this is fantastic! Thank you so much for your reply. I'm going to sleep soon, so I'll need some time to study this, but I just wanted to say how much I appreciate your comment. And welcome to HN, by the way! Do you happen to have an email address I could reach you at with further questions? (If you don't want to post it publicly, please feel free to email me if you'd like: sillysaurus3@gmail.com)
- geekbeast 12y ago
  Curious about a detail here. If this machine can evaluate AND and XOR, then how do you prevent a malicious attacker with the public key from performing encrypted each power of two, performing an AND and comparing with zero? {x&0x2} = {0x2} Does this imply that hcrypt VM is not necessarily equal to a Turing machine? The program counter seems like it could definitely cover finite automata, but it doesn't seem expressive enough to simulate a stack. If PC is always encrypted then it ends up having to encode both current state and the information necessary to evaluate the branch implicitly as a state change, which again seems more like finite automata. If you guys figured out how to securely implement control ( halting, loops, etc ), without functional encryption, that would be a huge breakthrough in FHE.

icambron 12y ago

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.

deleted 12y ago

[deleted]

hcrypt 12y ago

>Now, when the program executes, it's obviously possible to monitor it and watch what's being done. That's the trick. It isn't. Let's loosely stick to your example. if (var == op) { do this } else { do that } This, when compiled for the hcrypt VM, turns into something like 0 La var //look at var 1 CMPa op //var==op? 2 BEQ 5 //yes 3 <do that> 4 JMP 6 5 <do this> 6 <continue> The obvious question is: How do you hide what branch is taken? The hcrypt VM (as all processors and TMs) is a state machine. The states essentially are the status flags (zero result, addition overflow, minus result,...) and the program counter PC. In line (address) 1, the machine decides, whether op is equal to var and sets the zero-flag to 1 if this is the case. The comparison is an implicit subtraction, so if the two values are equal, then the result is 0 and the zero flag switches to 1. In the next machine cycle (PC is 3) we want to branch. The branch operation is just a simple assignment (PC=address). The assigned value can be expressed bitwise PC = ((branch AND zero-flag) XOR (PC+1 AND !zero-flag)) Case 1: var==op PC = ((5 AND 1) XOR (3 AND 0)) Case 2: var!=op PC = ((5 AND 0) XOR (3 AND 1)) Thinking in wires, this is the implementation of a demultiplexer or selector. This is the essential curcuit for the hcrypt VM and oblivious to an observer. The most basic application is the command selector. Assume, we have the opcode in a register OP and the operands in OP1 and OP2. The ALU then operates like res_add = OP1 + OP2 res_sub = OP1 - OP2 res_mul = OP1 * OP2 res_div = OP1 / OP2 result = ((res_add AND OP==ADD) XOR (res_sub AND OP==SUB) XOR (res_mul AND OP==MUL) XOR (res_div AND OP==DIV)) Since all the operands and registers (this incudes the machine opcodes) are encrypted, the observer does know, she's looking at a branch selector or an encrypted ALU but she cannot decide what branch is taken or what operation is executed.

sillysaurus3 12y ago
Wow, this is fantastic! Thank you so much for your reply. I'm going to sleep soon, so I'll need some time to study this, but I just wanted to say how much I appreciate your comment. And welcome to HN, by the way! Do you happen to have an email address I could reach you at with further questions? (If you don't want to post it publicly, please feel free to email me if you'd like: sillysaurus3@gmail.com)
geekbeast 12y ago
Curious about a detail here. If this machine can evaluate AND and XOR, then how do you prevent a malicious attacker with the public key from performing encrypted each power of two, performing an AND and comparing with zero? {x&0x2} = {0x2} Does this imply that hcrypt VM is not necessarily equal to a Turing machine? The program counter seems like it could definitely cover finite automata, but it doesn't seem expressive enough to simulate a stack. If PC is always encrypted then it ends up having to encode both current state and the information necessary to evaluate the branch implicitly as a state change, which again seems more like finite automata. If you guys figured out how to securely implement control ( halting, loops, etc ), without functional encryption, that would be a huge breakthrough in FHE.