The no obfuscation paper requires plaintext input, FHE requires encrypted input. What's unclear here?
There's no contradiction: If you have the plaintext input, you are required to have at least a (non garbled) function describing your operation, so it doesn't imply obfuscation.
Anything that can be written as a function can exploit FHE, as long as the output doesn't grow (i.e. you have to account for growth before)
Where in the no-obfuscation paper does it say it requires plaintext input? Searching for the word "plaintext" only reveals three results, and all of them are talking about a chosen plaintext attack. The paper doesn't seem to specify any requirements about the input.
And as I asked of swordswinger, since you seem to have a good enough understanding of this to vouch for it, could you summarize how you implement a FHE operation without knowing what the operation ("plainfunction") is?
Instead of writing your "plainfunction" in FHE operations, you write some type of interpreter in FHE operations. This interpreter can then operate on encrypted data that has your actual function encoded in it. Thus an attacker would know that you are running some type of interpreter, but not what your function is.
That method doesn't get around the limitations of writing the plainfunction directly as FHE operations. The FHE interpreter still acts on the equivalent of opcodes, with known behavior corresponding to each code, every bit as apparent as knowing that you're ANDing two HE values. It's obfuscated, but no more than you can do with plain ol' obfuscated code.
I still don't see your point. Afaik, we could have something like:
Input = FHE(data|opcode1|opcode2|...|opcodeN)
The server won't know what are the (opcode1|...|opcodeN) if the FHE scheme is properly implemented. That is, the actual implementation would be something like
It still has to execute the opcodes, revealing the computation in that sense. All the randomness adds (if I understand your example) is additional "junk" computation, that's unrelated to the output you really want -- but that's no different than you can already get with "plain" FHE, with obfuscation, or with adding pointless operations to a regular program.
Indeed, and that directly contradicts the paper I originally cited. The paper seems to claim it's impossible. That's the mystery, and it's very interesting! There's a contradiction that no one seems to know the answer to, which is the best kind of mystery.
The program in this case is the FHE virtual machine and indeed we cannot obfuscate that per the result of the paper. The "plaintext" input is the encrypted program along with its data. It is implicit in the definition of a program is the fact that the input to it is "plain".
Additionally, you should keep in mind that when doing the weird virtual machine thing you are not dealing with a single program. There are in fact 4. The actual program, call this P, you want to run on your data, the program to encrypt your program P along with its data, call this E, the virtual machine to run this encrypted program on the server, call this V, and finally the program to decrypt the result from running V on the output of E, call this E'.
Clearly, if we compose all these programs and run it on some data D, we get E'(V(E(P, D))) = P(D). However, the server doesn't know E, D and P and certainly doesn't know E'. The only thing the server knows is the value of E(P, D) and what V is. I haven't looked at the paper to deeply but I suspect it's vitally important to their result that you have some type of oracle that given a D, tells you the output of P(D), but the server cannot have that or else it would be pointless wasting your time with this FHE thing.
There is no contradiction. You are conflating the concept of 'obfuscation' and the very specific (and rigidly formalized) cryptographic primitive called 'indistinguishability obfuscation'.
Comments
The no obfuscation paper requires plaintext input, FHE requires encrypted input. What's unclear here?
There's no contradiction: If you have the plaintext input, you are required to have at least a (non garbled) function describing your operation, so it doesn't imply obfuscation.
Anything that can be written as a function can exploit FHE, as long as the output doesn't grow (i.e. you have to account for growth before)
Where in the no-obfuscation paper does it say it requires plaintext input? Searching for the word "plaintext" only reveals three results, and all of them are talking about a chosen plaintext attack. The paper doesn't seem to specify any requirements about the input.
And as I asked of swordswinger, since you seem to have a good enough understanding of this to vouch for it, could you summarize how you implement a FHE operation without knowing what the operation ("plainfunction") is?
Instead of writing your "plainfunction" in FHE operations, you write some type of interpreter in FHE operations. This interpreter can then operate on encrypted data that has your actual function encoded in it. Thus an attacker would know that you are running some type of interpreter, but not what your function is.
That method doesn't get around the limitations of writing the plainfunction directly as FHE operations. The FHE interpreter still acts on the equivalent of opcodes, with known behavior corresponding to each code, every bit as apparent as knowing that you're ANDing two HE values. It's obfuscated, but no more than you can do with plain ol' obfuscated code.
I still don't see your point. Afaik, we could have something like:
Input = FHE(data|opcode1|opcode2|...|opcodeN)
The server won't know what are the (opcode1|...|opcodeN) if the FHE scheme is properly implemented. That is, the actual implementation would be something like
Input' = FHE(data|opcode1|opcode2|...|opcodeN|randomness)
Output' = InverseHE(FHEval(Input'))
Output = Output' - randomness
I.e. the server can't uncover the (data,opcode1,...,opcodeN) tuple by enumeration if exp(randomness) is large enough. Is this what you had in mind?
See my reply to nullc: https://news.ycombinator.com/item?id=7790084
It still has to execute the opcodes, revealing the computation in that sense. All the randomness adds (if I understand your example) is additional "junk" computation, that's unrelated to the output you really want -- but that's no different than you can already get with "plain" FHE, with obfuscation, or with adding pointless operations to a regular program.
Indeed, and that directly contradicts the paper I originally cited. The paper seems to claim it's impossible. That's the mystery, and it's very interesting! There's a contradiction that no one seems to know the answer to, which is the best kind of mystery.
The program in this case is the FHE virtual machine and indeed we cannot obfuscate that per the result of the paper. The "plaintext" input is the encrypted program along with its data. It is implicit in the definition of a program is the fact that the input to it is "plain".
Additionally, you should keep in mind that when doing the weird virtual machine thing you are not dealing with a single program. There are in fact 4. The actual program, call this P, you want to run on your data, the program to encrypt your program P along with its data, call this E, the virtual machine to run this encrypted program on the server, call this V, and finally the program to decrypt the result from running V on the output of E, call this E'.
Clearly, if we compose all these programs and run it on some data D, we get E'(V(E(P, D))) = P(D). However, the server doesn't know E, D and P and certainly doesn't know E'. The only thing the server knows is the value of E(P, D) and what V is. I haven't looked at the paper to deeply but I suspect it's vitally important to their result that you have some type of oracle that given a D, tells you the output of P(D), but the server cannot have that or else it would be pointless wasting your time with this FHE thing.
There is no contradiction. You are conflating the concept of 'obfuscation' and the very specific (and rigidly formalized) cryptographic primitive called 'indistinguishability obfuscation'.