Ok, so if I understand correctly, it's impossible to write a program which hides its intent? That is, reverse engineering of what a program is doing will always be possible?
Something doesn't seem quite right, though. Programs are data. If it's possible to perform operations on data without knowing the data, then shouldn't it be possible to perform (useful) computation without revealing the algorithm? If not, why not?
No. It's because they're different things. The idea here is that we perform the operation, but the output is not known either. So my data can pass through my system with me doing whatever I want to it, and when it comes out it can be decrypted again.
The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output.
The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output.
Thanks for your time. That's what I was trying to get to, yes. Would you help me understand why encrypted output would be a problem for the interpreter? If the input data is encrypted, and the data defines a program which can be executed, and the result of that execution is more encrypted data, then (for example) why can't that encrypted data be fed back into the interpreter as further input? Or transmitted over the network to a computer with the decryption key (so that the encrypted output can be used in a meaningful way, without revealing to the original computer what was computed)? In other words, why is encrypted output any more of a problem than operating on encrypted data in the first place?
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:
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.
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.)
Comments
Ok, so if I understand correctly, it's impossible to write a program which hides its intent? That is, reverse engineering of what a program is doing will always be possible?
Something doesn't seem quite right, though. Programs are data. If it's possible to perform operations on data without knowing the data, then shouldn't it be possible to perform (useful) computation without revealing the algorithm? If not, why not?
No. It's because they're different things. The idea here is that we perform the operation, but the output is not known either. So my data can pass through my system with me doing whatever I want to it, and when it comes out it can be decrypted again.
The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output.
The closest analogy (I think you are trying to get to this) is that one might be able to make a series of operations that would execute an encrypted program. The problem is that this would result in encrypted output.
Thanks for your time. That's what I was trying to get to, yes. Would you help me understand why encrypted output would be a problem for the interpreter? If the input data is encrypted, and the data defines a program which can be executed, and the result of that execution is more encrypted data, then (for example) why can't that encrypted data be fed back into the interpreter as further input? Or transmitted over the network to a computer with the decryption key (so that the encrypted output can be used in a meaningful way, without revealing to the original computer what was computed)? In other words, why is encrypted output any more of a problem than operating on encrypted data in the first place?
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.
They can; the output is an encrypted boolean.
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:
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:
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.)