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.

Let's try a direct question: why can't the third party perform the operation "is x equal to 5"?

The point of HE is that you can do add and mul. FHE extends HE to do arbitrary computation. "Is x equal to 5?" is an arbitrary computation, so it seems like FHE must support it.

If comparison ops are supported, then you can make an FHE based interpreter. Thus far, no one has been able to explain why specifically it wouldn't be possible. And if it's possible, then programs are naturally obfuscated: the interpreter is operating on encrypted bytecode input. But the original paper I cited says this is impossible! So there seems to be an interesting mystery here.

> why can't the third party perform the operation "is x equal to 5"?

They can; the output is an encrypted boolean.

> And if it's possible, then programs are naturally obfuscated: the interpreter is operating on encrypted bytecode input. But the original paper I cited says this is impossible!

No it doesn't. Isn't your paper talking about an obfuscated program Ob(P) that does the same thing as P? P takes plaintext to plaintext, so Ob(P) takes plaintext to plaintext.

Homomorphic encryption is a different thing. Hom(P), if it exists, takes ciphertext to ciphertext. (Or possibly plaintext to ciphertext if it's a public-key cryptosystem.)

How is the output to a conditional an encrypted boolean? A conditional is "if this, do that." That means if the conditional is true, the branch is executed. The output wouldn't be an encrypted boolean; the output would be whatever the branch does. Right?

I am sure they meant that the output of a conditional expression would be an encrypted boolean.

A conditional branch would become an encrypted conditional branch. That means, you wouldn't be able to infer the branch from the encrypted output.

Let's take a simple example. I have an algorithm X which takes two integers and returns an integer.

Let's say I want to run this algorithm on a third-party VPS. I obfuscate the algorithm X, in order to hide the operations that X does. Let's called the obfuscated version OX.

I host the OX algorithm on the third-party server, and start supplying it pairs of integers. The third-party is observing the set of inputs and outputs:

  (4, 4) => 8
  (3, 2) => 5
  (1, 0) => 1

From these observations, the third-party would be able to infer what OX does. (simple addition in this case).

Now, however, if I use HE, I will get an algorithm (HX) which takes encrypted input and spits out encrypted output. A third-party will see the corresponding log of inputs and outputs like this:

  h3830120cjfakj, 102309123clals => 293sdlzlxdf
  94ka3lkc.zdkf, 102kksdllz => 1923939nddd

From these observations, it is impossible to know what HX does (as per the theory).

Yes, that's the big caveat that needs to be added when someone tells you that XOR and AND are enough to implement arbitrary functions. What that means is, for an arbitrary function you can write a program that takes that function plus the input size, and generates the (XOR/AND-only) boolean circuit that implements the function for that input size.

Note that the output size is fixed too. So yeah, any program you actually try implement this way is going to involve a very roundabout (er, circuitous) process. If-branching? Hah! That just means you get to designate half the remaining portion of the circuit to one branch and the other half to the other branch. While loops? You get to unroll each step into another set of gates.

Here's my post from when I first discovered the FHE paper: http://blog.tyrannyofthemouse.com/2013/05/i-added-your-numbe...

I somehow can't reply to your other post - but this isn't proposing a model of computation that allows you to perform those operations (if x1 == 5) - that would defeat the purpose. The goal is to allow you to perform some commonly used operations (matrix multiplications etc) in a zero knowledge way. Checking for equality would just destroy the encryption.

No, FHE supports arbitrary computation. That's the point of FHE.

You may be thinking of HE. HE only allows add and mult operations. FHE extends HE to perform arbitrary computation.

(EDIT: To reply, click on "link". That will let you type out a reply while bypassing the flamewar prevention system. "Link" is next to my username, next to the "parent" link.)