4 ms·

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

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)?
    - sillysaurus3 12y ago
      (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.)
      - darkmighty 12y ago
        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)
        sillysaurus3 12y ago
        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.
        SilasX 12y ago
        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?
        kosievdmerwe 12y ago
        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.
        sillysaurus3 12y ago
        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.
    - nullc 12y ago
      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.
      - SilasX 12y ago
        >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.
- deleted 12y ago
  [deleted]
- wyager 12y ago
  >FHE works by constructing a (malleability-exploiting) circuit to implement the desired logic on the (malleable) ciphertext. That's a very simplistic view of FHE. There are much more complex homomorphisms that you can take advantage of, that I don't think can be called "malleability". There is a lot of research going into FHE based on ring homomorphisms, because you can e.g. encode any logical operations as addition and multiplication over GF(2). I would not be surprised at all if you could encrypt computations with FHE.

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)?
  - sillysaurus3 12y ago
    (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.)
    - darkmighty 12y ago
      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)
      - sillysaurus3 12y ago
        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.
      - SilasX 12y ago
        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?
        kosievdmerwe 12y ago
        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.
        sillysaurus3 12y ago
        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.
  - nullc 12y ago
    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.
    - SilasX 12y ago
      >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.
deleted 12y ago
[deleted]
wyager 12y ago
>FHE works by constructing a (malleability-exploiting) circuit to implement the desired logic on the (malleable) ciphertext. That's a very simplistic view of FHE. There are much more complex homomorphisms that you can take advantage of, that I don't think can be called "malleability". There is a lot of research going into FHE based on ring homomorphisms, because you can e.g. encode any logical operations as addition and multiplication over GF(2). I would not be surprised at all if you could encrypt computations with FHE.