4 ms·

That 'something' is virtual black-box indistinguishability obfuscation. It's a way of 'hiding' (in some sense) a program rather than the data a program acts on.

That 'something' is virtual black-box indistinguishability obfuscation. It's a way of 'hiding' (in some sense) a program rather than the data a program acts on. FHE is a way of carrying out any program over encrypted data. It hides the data but not the program acting on it. IO hides the program but not the data.

sillysaurus3 12y ago
Since programs are data, shouldn't it be possible to write an interpreter which executes encrypted bytecode? That is, the only thing a reverse engineer would be able to conclude is "an interpreter is executing some bytecode, but we don't know what it's executing." The bytecode (the algorithm itself) is data, and since FHE hides the data, the algorithm remains encrypted and hidden. If it's possible to add or multiply without knowing what's being added or multiplied, then it seems like it should be possible to do computation without revealing the algorithm being used.
- dllthomas 12y ago
  It is possible that you could have FHE primitives that are not sufficient to build a Turing complete interpreter. Otherwise, you can clearly construct a completely obfuscated system by nesting FHE inside an interpreter run inside FHE... though that is likely to be slow enough to be completely impractical.
- icambron 12y ago
  EDIT: I should disclaim that I have exactly no expertise here. This is all me having fun speculating. I think you're being too handwavy about what FHE is capable of. FHE means that specific operations performed on encrypted data result in data that, when decrypted, have the right result in cleartext. It's not "hiding the data". So it can't run your encrypted bytecode, only transform it into other, also encrypted bytecode, which it also can't interpret. Executing encrypted bytecode doesn't really make sense, because the bytecode tells its interpreter what to do. Either the interpreter can read that information and do it, or it can't. The former means its not encrypted in the first place, and the latter means it won't work. You're trying to use a scheme by which the interpreter doesn't how to evaluate a function, but evaluates it correctly anyway.
  - sillysaurus3 12y ago
    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.
      - 12y ago
- pjungwir 12y ago
  I'm not an expert, but I think this is the difference: FHE uses known (unencrypted) operations to transform unknown (encrypted) data. It's true the program is data, but to run it you'd have to decrypt it. With FHE the operations are supplied from outside the ciphertext.

sillysaurus3 12y ago

Since programs are data, shouldn't it be possible to write an interpreter which executes encrypted bytecode? That is, the only thing a reverse engineer would be able to conclude is "an interpreter is executing some bytecode, but we don't know what it's executing." The bytecode (the algorithm itself) is data, and since FHE hides the data, the algorithm remains encrypted and hidden. If it's possible to add or multiply without knowing what's being added or multiplied, then it seems like it should be possible to do computation without revealing the algorithm being used.

dllthomas 12y ago
It is possible that you could have FHE primitives that are not sufficient to build a Turing complete interpreter. Otherwise, you can clearly construct a completely obfuscated system by nesting FHE inside an interpreter run inside FHE... though that is likely to be slow enough to be completely impractical.
icambron 12y ago
EDIT: I should disclaim that I have exactly no expertise here. This is all me having fun speculating. I think you're being too handwavy about what FHE is capable of. FHE means that specific operations performed on encrypted data result in data that, when decrypted, have the right result in cleartext. It's not "hiding the data". So it can't run your encrypted bytecode, only transform it into other, also encrypted bytecode, which it also can't interpret. Executing encrypted bytecode doesn't really make sense, because the bytecode tells its interpreter what to do. Either the interpreter can read that information and do it, or it can't. The former means its not encrypted in the first place, and the latter means it won't work. You're trying to use a scheme by which the interpreter doesn't how to evaluate a function, but evaluates it correctly anyway.
- sillysaurus3 12y ago
  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.
    - 12y ago
pjungwir 12y ago
I'm not an expert, but I think this is the difference: FHE uses known (unencrypted) operations to transform unknown (encrypted) data. It's true the program is data, but to run it you'd have to decrypt it. With FHE the operations are supplied from outside the ciphertext.