11 ms·

Would anyone comment on http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf ? "On the (Im)possibility of Obfu

Would anyone comment on http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf ? "On the (Im)possibility of Obfuscating Programs" "In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible." I haven't spent too much time meditating on the implications of the paper, so I was hoping to hear from someone who has. Does this paper strike a mortal blow to FHE? Or is this paper pointing out a result that can be ignored in practice? When I get a few hours I'll spend some time trying to come up with examples of what the paper is talking about and hopefully discover the truth for myself, but if someone here has already done that, please chime in!

swordswinger12 12y ago
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.
SilasX 12y ago
FHE means you hide the input and processed output from the processor, not the operation. From the abstract, it's talking about hiding the operation [1]. IOW, FHE means: "I know I added your numbers, but I don't know what they are or what their sum is. Here's the encrypted sum." [1] First sentence: Informally, an obfuscator O is an (efficient, 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.
- darkmighty 12y ago
  Actually, FHE can hide the operation. Since it can execute arbitrary non-linear operations, one that it can do is "Do a step in this encrypted Turing machine". What Black box obfuscation demands which is impossible is "Take this plaintext, do a step in an obfuscated Turing machine and return me the plaintext solution", i.e. there's no obfuscation which makes it "hard" to determine the operations for arbitrary Turing machines/circuits given plaintext I/O.
  - SilasX 12y ago
    >Actually, FHE can hide the operation. Since it can execute arbitrary non-linear operations, one that it can do is "Do a step in this encrypted Turing machine". Do you have a source on that? Because it sounds suspect. FHE works by constructing a (malleability-exploiting) circuit to implement the desired logic on the (malleable) ciphertext. So it seems it would have to decrypt the relevant step in that Turing machine to build the circuit.
    - swordswinger12 12y ago
      The details are more complicated, but he/she might be talking about http://eprint.iacr.org/2013/229.pdf http://eprint.iacr.org/2013/229.pdf
      - SilasX 12y ago
        Since you understand the paper well enough to vouch for the claim, could you spell out how you can encrypt operations like that in a way that doesn't contradict the "no obfuscation" paper (or otherwise show the latter wrong)?
p4bl0 12y ago
As other said, their not talking about the same obfuscation. If you are interested in code obfuscation and a way to prove that a formally correct obfuscator is impossible, you might want to read a paper called “Can a Program Reverse-Engineer Itself?” [1] I worked on as an undergrad. The idea is that a correct obfuscator should only obfuscate and not change the program's semantics, which means that it can't change constants that may be displayed to the users, like hardcoded integers and strings. If you use these in a Quine [2] structure to be able to retrieve your original code, then the obfuscator can't do anything: it it breaks the Quine it is not a correct obfuscator, if it doesn't then you can trivially get back the original code. And what is interesting here is that it is possible to take any source code and make a Quine which has it as a payload (it will do the same thing as the original source code except that it will also be a Quine), which is something we had done already for another paper [3]. [1] http://eprint.iacr.org/2011/497 http://eprint.iacr.org/2011/497 [2] https://en.wikipedia.org/wiki/Quine_%28computing%29 https://en.wikipedia.org/wiki/Quine_%28computing%29 [3] http://eprint.iacr.org/2011/099 http://eprint.iacr.org/2011/099

swordswinger12 12y ago

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.

SilasX 12y ago

FHE means you hide the input and processed output from the processor, not the operation. From the abstract, it's talking about hiding the operation [1]. IOW, FHE means: "I know I added your numbers, but I don't know what they are or what their sum is. Here's the encrypted sum." [1] First sentence: Informally, an obfuscator O is an (efficient, 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.

darkmighty 12y ago
Actually, FHE can hide the operation. Since it can execute arbitrary non-linear operations, one that it can do is "Do a step in this encrypted Turing machine". What Black box obfuscation demands which is impossible is "Take this plaintext, do a step in an obfuscated Turing machine and return me the plaintext solution", i.e. there's no obfuscation which makes it "hard" to determine the operations for arbitrary Turing machines/circuits given plaintext I/O.
- SilasX 12y ago
  >Actually, FHE can hide the operation. Since it can execute arbitrary non-linear operations, one that it can do is "Do a step in this encrypted Turing machine". Do you have a source on that? Because it sounds suspect. FHE works by constructing a (malleability-exploiting) circuit to implement the desired logic on the (malleable) ciphertext. So it seems it would have to decrypt the relevant step in that Turing machine to build the circuit.
  - swordswinger12 12y ago
    The details are more complicated, but he/she might be talking about http://eprint.iacr.org/2013/229.pdf http://eprint.iacr.org/2013/229.pdf
    - SilasX 12y ago
      Since you understand the paper well enough to vouch for the claim, could you spell out how you can encrypt operations like that in a way that doesn't contradict the "no obfuscation" paper (or otherwise show the latter wrong)?

p4bl0 12y ago

As other said, their not talking about the same obfuscation. If you are interested in code obfuscation and a way to prove that a formally correct obfuscator is impossible, you might want to read a paper called “Can a Program Reverse-Engineer Itself?” [1] I worked on as an undergrad. The idea is that a correct obfuscator should only obfuscate and not change the program's semantics, which means that it can't change constants that may be displayed to the users, like hardcoded integers and strings. If you use these in a Quine [2] structure to be able to retrieve your original code, then the obfuscator can't do anything: it it breaks the Quine it is not a correct obfuscator, if it doesn't then you can trivially get back the original code. And what is interesting here is that it is possible to take any source code and make a Quine which has it as a payload (it will do the same thing as the original source code except that it will also be a Quine), which is something we had done already for another paper [3]. [1] http://eprint.iacr.org/2011/497 http://eprint.iacr.org/2011/497 [2] https://en.wikipedia.org/wiki/Quine_%28computing%29 https://en.wikipedia.org/wiki/Quine_%28computing%29 [3] http://eprint.iacr.org/2011/099 http://eprint.iacr.org/2011/099