6 ms·

This is talking about a completely different primitive (indistinguishability obfuscation) so FHE is fine. In fact this is talking about an exceptionally strong

This is talking about a completely different primitive (indistinguishability obfuscation) so FHE is fine. In fact this is talking about an exceptionally strong characterization of IO (virtual black-box) which is not used in current research on the subject.

sillysaurus3 12y ago
Would you expand on this? From the abstract: "Informally, an obfuscator O is an (eﬃcient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is “unintelligible” in some sense" That sounds like an exact description of FHE, and the paper seems to claim something is impossible. So I'm trying to figure out: If the paper isn't claiming FHE is impossible, then what is that "something" and how does it relate to FHE?
- CHY872 12y ago
  So the obvious difference is that if I run an obfuscated program, I'd expect to get the same output as the original program - the obfuscated program is to an extent expected to perform as a normal program, but be unreadable. With HE, you operate on encrypted data and what you get out is still encrypted data - you never have knowledge of what the data is, you just know you've done something to it. So I could perhaps add two encrypted numbers together to obtain something I know to be the sum (but have no idea what the sum is).
  - sillysaurus3 12y ago
    Ok, so if I understand correctly, it's impossible to write a program which hides its intent? That is, reverse engineering of what a program is doing will always be possible? Something doesn't seem quite right, though. Programs are data. If it's possible to perform operations on data without knowing the data, then shouldn't it be possible to perform (useful) computation without revealing the algorithm? If not, why not?
    - CHY872 12y ago
      No. It's because they're different things. The idea here is that we perform the operation, but the output is not known either. So my data can pass through my system with me doing whatever I want to it, and when it comes out it can be decrypted again. The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output.
      - sillysaurus3 12y ago
        The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output. Thanks for your time. That's what I was trying to get to, yes. Would you help me understand why encrypted output would be a problem for the interpreter? If the input data is encrypted, and the data defines a program which can be executed, and the result of that execution is more encrypted data, then (for example) why can't that encrypted data be fed back into the interpreter as further input? Or transmitted over the network to a computer with the decryption key (so that the encrypted output can be used in a meaningful way, without revealing to the original computer what was computed)? In other words, why is encrypted output any more of a problem than operating on encrypted data in the first place?
        akiselev 12y ago
        Obfusticators are pretty different from FHE. Instruction based obfustication takes common instructions like mov eax, 0xff and replaces them with more complex instructions that do the same thing but in a very indirect way while other common methods include mostly name mangling, compression, and encryption. To modify the code or dump it, you need the unpacker to somehow decrypt the code and load it into memory. The point of FHE, however, is to encrypt private data to send it to a third party to perform operations on that data without that third party having the keys necessary to decrypt the data (and thus see what it is). With FHE, the third party can modify the data but must then send the encrypted result back to the client who then uses the original keys to decrypt the result and look at it. The client can't see exactly which operations were performed and the third party can't see the original data. I don't know if a FHE based interpreter is possible but since you need to have the original keys to read from an FHE payload, I don't think so.
- swordswinger12 12y ago
  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.
pbsd 12y ago
FTR, hcrypt predates indistinguishability obfuscation by a couple of years. As far as I can tell this really is a straightforward VM working with homomorphically-encrypted opcodes and data, and not an implementation of Garg and friends's work. Theoretically speaking, I doubt this method holds: there is no theoretical analysis of it at all in the papers to support it. It certainly doesn't hold in the virtual blackbox model, which is what the theorem alluded above assumes.

sillysaurus3 12y ago

Would you expand on this? From the abstract: "Informally, an obfuscator O is an (eﬃcient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is “unintelligible” in some sense" That sounds like an exact description of FHE, and the paper seems to claim something is impossible. So I'm trying to figure out: If the paper isn't claiming FHE is impossible, then what is that "something" and how does it relate to FHE?

CHY872 12y ago
So the obvious difference is that if I run an obfuscated program, I'd expect to get the same output as the original program - the obfuscated program is to an extent expected to perform as a normal program, but be unreadable. With HE, you operate on encrypted data and what you get out is still encrypted data - you never have knowledge of what the data is, you just know you've done something to it. So I could perhaps add two encrypted numbers together to obtain something I know to be the sum (but have no idea what the sum is).
- sillysaurus3 12y ago
  Ok, so if I understand correctly, it's impossible to write a program which hides its intent? That is, reverse engineering of what a program is doing will always be possible? Something doesn't seem quite right, though. Programs are data. If it's possible to perform operations on data without knowing the data, then shouldn't it be possible to perform (useful) computation without revealing the algorithm? If not, why not?
  - CHY872 12y ago
    No. It's because they're different things. The idea here is that we perform the operation, but the output is not known either. So my data can pass through my system with me doing whatever I want to it, and when it comes out it can be decrypted again. The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output.
    - sillysaurus3 12y ago
      The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output. Thanks for your time. That's what I was trying to get to, yes. Would you help me understand why encrypted output would be a problem for the interpreter? If the input data is encrypted, and the data defines a program which can be executed, and the result of that execution is more encrypted data, then (for example) why can't that encrypted data be fed back into the interpreter as further input? Or transmitted over the network to a computer with the decryption key (so that the encrypted output can be used in a meaningful way, without revealing to the original computer what was computed)? In other words, why is encrypted output any more of a problem than operating on encrypted data in the first place?
      - akiselev 12y ago
        Obfusticators are pretty different from FHE. Instruction based obfustication takes common instructions like mov eax, 0xff and replaces them with more complex instructions that do the same thing but in a very indirect way while other common methods include mostly name mangling, compression, and encryption. To modify the code or dump it, you need the unpacker to somehow decrypt the code and load it into memory. The point of FHE, however, is to encrypt private data to send it to a third party to perform operations on that data without that third party having the keys necessary to decrypt the data (and thus see what it is). With FHE, the third party can modify the data but must then send the encrypted result back to the client who then uses the original keys to decrypt the result and look at it. The client can't see exactly which operations were performed and the third party can't see the original data. I don't know if a FHE based interpreter is possible but since you need to have the original keys to read from an FHE payload, I don't think so.
swordswinger12 12y ago
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.

pbsd 12y ago

FTR, hcrypt predates indistinguishability obfuscation by a couple of years. As far as I can tell this really is a straightforward VM working with homomorphically-encrypted opcodes and data, and not an implementation of Garg and friends's work. Theoretically speaking, I doubt this method holds: there is no theoretical analysis of it at all in the papers to support it. It certainly doesn't hold in the virtual blackbox model, which is what the theorem alluded above assumes.