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.
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.
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.
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)?
It doesn't contradict the impossibility result because the homorphic circuit evaluation cannot output a decryption.
With FHE the untrusted party can (usually) provide inputs (e.g. you can give them encryption of 1 and 0 that they can supply at some point in the circuit). But they cannot get _any_ non-encrypted output from the function without knowing the encryption keys (which would let them see everything).
FHE for secret operations is very straight forward. You first define a universal circuit— that is a circuit that can compute the result of any circuit (of the size) depending on its inputs. You then have the FHE environment run that universal circuit with the operations you really want specified as an input.
The result precluding blackbox obfuscation is really more about the formalism than a true practical impossibility, see Gentry's recent candidate indistinguishably obfuscation for NC circuts, which he boosts into full obfuscation for arbitrary circuts by implementing a pair of homorphic encryption decryption circuits under it.
FHE for secret operations is very straight forward. You first define a universal circuit— that is a circuit that can compute the result of any circuit (of the size) depending on its inputs. You then have the FHE environment run that universal circuit with the operations you really want specified as an input.
Okay, the issue isn't whether you can obfuscate, but whether you can do it in a stronger sense than "regular" FHE or plain ol binaries or deliberate obfuscation. And what you've described doesn't do that.
The universal FHE circuit still sees the operations "you really want to execute", as it has to implement them in the first place. It's certainly obscured "gee, what do all these ANDs in this structure mean", but that's no different from eg an FHE scheme where you compute the circuit for the specific input size/function pair you want to compute rather than let the untrusted server generate it from knowledge of the algorithm you pass it.
So yeah, it's obfuscated, but no more than you get through regular computing; FHE has added nothing in this respect.
(This is exactly the question I've been trying to ask throughout this thread. Thank you for asking it directly. Hopefully someone here knows the answer, but it's looking more and more to be a mystery that will require some new effort to solve.)
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
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.
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.
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.
The details are more complicated, but he/she might be talking about http://eprint.iacr.org/2013/229.pdf
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)?
It doesn't contradict the impossibility result because the homorphic circuit evaluation cannot output a decryption.
With FHE the untrusted party can (usually) provide inputs (e.g. you can give them encryption of 1 and 0 that they can supply at some point in the circuit). But they cannot get _any_ non-encrypted output from the function without knowing the encryption keys (which would let them see everything).
FHE for secret operations is very straight forward. You first define a universal circuit— that is a circuit that can compute the result of any circuit (of the size) depending on its inputs. You then have the FHE environment run that universal circuit with the operations you really want specified as an input.
The result precluding blackbox obfuscation is really more about the formalism than a true practical impossibility, see Gentry's recent candidate indistinguishably obfuscation for NC circuts, which he boosts into full obfuscation for arbitrary circuts by implementing a pair of homorphic encryption decryption circuits under it.
Okay, the issue isn't whether you can obfuscate, but whether you can do it in a stronger sense than "regular" FHE or plain ol binaries or deliberate obfuscation. And what you've described doesn't do that.
The universal FHE circuit still sees the operations "you really want to execute", as it has to implement them in the first place. It's certainly obscured "gee, what do all these ANDs in this structure mean", but that's no different from eg an FHE scheme where you compute the circuit for the specific input size/function pair you want to compute rather than let the untrusted server generate it from knowledge of the algorithm you pass it.
So yeah, it's obfuscated, but no more than you get through regular computing; FHE has added nothing in this respect.
(This is exactly the question I've been trying to ask throughout this thread. Thank you for asking it directly. Hopefully someone here knows the answer, but it's looking more and more to be a mystery that will require some new effort to solve.)
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'.