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
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'.