This is talking about a completely different primitive (indistinguishability obfuscation) so FHE is fine. In fact this is talking about an exceptionally strong characterization of IO (virtual black-box) which is not used in current research on the subject.
From the abstract: "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"
That sounds like an exact description of FHE, and the paper seems to claim something is impossible. So I'm trying to figure out: If the paper isn't claiming FHE is impossible, then what is that "something" and how does it relate to FHE?
So the obvious difference is that if I run an obfuscated program, I'd expect to get the same output as the original program - the obfuscated program is to an extent expected to perform as a normal program, but be unreadable.
With HE, you operate on encrypted data and what you get out is still encrypted data - you never have knowledge of what the data is, you just know you've done something to it. So I could perhaps add two encrypted numbers together to obtain something I know to be the sum (but have no idea what the sum is).
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.)
That 'something' is virtual black-box indistinguishability obfuscation. It's a way of 'hiding' (in some sense) a program rather than the data a program acts on. FHE is a way of carrying out any program over encrypted data. It hides the data but not the program acting on it. IO hides the program but not the data.
Since programs are data, shouldn't it be possible to write an interpreter which executes encrypted bytecode? That is, the only thing a reverse engineer would be able to conclude is "an interpreter is executing some bytecode, but we don't know what it's executing." The bytecode (the algorithm itself) is data, and since FHE hides the data, the algorithm remains encrypted and hidden.
If it's possible to add or multiply without knowing what's being added or multiplied, then it seems like it should be possible to do computation without revealing the algorithm being used.
EDIT: I should disclaim that I have exactly no expertise here. This is all me having fun speculating.
I think you're being too handwavy about what FHE is capable of. FHE means that specific operations performed on encrypted data result in data that, when decrypted, have the right result in cleartext. It's not "hiding the data". So it can't run your encrypted bytecode, only transform it into other, also encrypted bytecode, which it also can't interpret. Executing encrypted bytecode doesn't really make sense, because the bytecode tells its interpreter what to do. Either the interpreter can read that information and do it, or it can't. The former means its not encrypted in the first place, and the latter means it won't work. You're trying to use a scheme by which the interpreter doesn't how to evaluate a function, but evaluates it correctly anyway.
So my understanding of FHE is that it can take an arbitrary circuit (any arbitrary program) and convert it into a circuit which operates on encrypted data.
That means it must be possible to write the equivalent of
etc, where "op" is encrypted data. By extension, you can write an entire interpreter for encrypted bytecodes.
Now, when the program executes, it's obviously possible to monitor it and watch what's being done. However, until it executes, the bytecode remains secret. That means it should be possible to ship programs which are impossible to analyze until they're actually executed.
It's a common malware technique to write a program which contains an encrypted subprogram, which is only decryptable on a certain target machine. (For example, you could use a specific computer's MAC address as an ecryption key, which means no reverse engineer can analyze it except on that specific machine.)
FHE, on the other hand, provides the opportunity to ship a turing-complete interpreter to everyone, which executes encrypted bytecodes which can't be analyzed until execution time. That means a FHE program could be a timebomb set to wipe your harddrive at some specific date and you wouldn't know it, since the best you could determine beforehand is "this interpreter sometimes tries to execute shell commands" without actually seeing which commands it's capable of executing in practice until it's too late.
Now, when the program executes, it's obviously possible to monitor it and watch what's being done.
That's the trick. It isn't. Let's loosely stick to your example.
if (var == op)
{
do this
}
else
{
do that
}
This, when compiled for the hcrypt VM, turns into something like
0 La var //look at var
1 CMPa op //var==op?
2 BEQ 5 //yes
3 <do that>
4 JMP 6
5 <do this>
6 <continue>
The obvious question is: How do you hide what branch is taken? The hcrypt VM (as all processors and TMs) is a state machine. The states essentially are the status flags (zero result, addition overflow, minus result,...) and the program counter PC. In line (address) 1, the machine decides, whether op is equal to var and sets the zero-flag to 1 if this is the case. The comparison is an implicit subtraction, so if the two values are equal, then the result is 0 and the zero flag switches to 1. In the next machine cycle (PC is 3) we want to branch. The branch operation is just a simple assignment (PC=address). The assigned value can be expressed bitwise
PC = ((branch AND zero-flag) XOR (PC+1 AND !zero-flag))
Case 1: var==op
PC = ((5 AND 1) XOR (3 AND 0))
Case 2: var!=op
PC = ((5 AND 0) XOR (3 AND 1))
Thinking in wires, this is the implementation of a demultiplexer or selector. This is the essential curcuit for the hcrypt VM and oblivious to an observer. The most basic application is the command selector. Assume, we have the opcode in a register OP and the operands in OP1 and OP2. The ALU then operates like
res_add = OP1 + OP2
res_sub = OP1 - OP2
res_mul = OP1 * OP2
res_div = OP1 / OP2
result = ((res_add AND OP==ADD) XOR (res_sub AND OP==SUB) XOR (res_mul AND OP==MUL) XOR (res_div AND OP==DIV))
Since all the operands and registers (this incudes the machine opcodes) are encrypted, the observer does know, she's looking at a branch selector or an encrypted ALU but she cannot decide what branch is taken or what operation is executed.
Curious about a detail here. If this machine can evaluate AND and XOR, then how do you prevent a malicious attacker with the public key from performing encrypted each power of two, performing an AND and comparing with zero?
{x&0x2} = {0x2}
Does this imply that hcrypt VM is not necessarily equal to a Turing machine? The program counter seems like it could definitely cover finite automata, but it doesn't seem expressive enough to simulate a stack. If PC is always encrypted then it ends up having to encode both current state and the information necessary to evaluate the branch implicitly as a state change, which again seems more like finite automata.
If you guys figured out how to securely implement control ( halting, loops, etc ), without functional encryption, that would be a huge breakthrough in FHE.
The attacker can do whatever she wants. You can't prevent her from doing anything. But maybe you can elaborate on what you mean with "each power of two". When trying to compare with zero (what zero?), keep in mind we're talking about a probabilistic cryptosystem. The machine is just an application of the underlying scheme, so it's not the machine that provides the atomic functions.
To be precise, the state of the machine includes the flags, the PC and memory. It's easy to implement a simple stack pattern in circuits but you don't need it in order to implement arbitrary functions.
We already published the solution for encrypted memory access and encrypted program flow control (without unfolding) but halting is an issue you (at least to my knowledge) cannot solve under the assumptions we made.
VII. OPEN ISSUES AND FUTURE WORK
...
One of the main issues of our concept is the termination problem. To solve this problem, a crypto-system that can selectively decrypt information is required.
Doing the above will make it very difficult to prove the security of malleable cryptosystem, something that Boneh, Sahai, and Waters have written multiple papers on. The approach of finding a minimum number of cycles to complete the computation seems much more effective, if restrictive in the number of operations that can be evaluated.
The termination problem is the major issue. You cannot generate a selectively decryptable signal from inside the encrypted code. In other words, being able to generate a halt signal to mark the end of the program flow immediately invalidates the security of the entire container.
Wow, this is fantastic! Thank you so much for your reply. I'm going to sleep soon, so I'll need some time to study this, but I just wanted to say how much I appreciate your comment. And welcome to HN, by the way!
Do you happen to have an email address I could reach you at with further questions? (If you don't want to post it publicly, please feel free to email me if you'd like: sillysaurus3@gmail.com)
if (op == OP_ADD) { /* interpret addition bytecode */ }
where "op" is encrypted data.
Ah, but that's why it doesn't work. The trick would be to test if if op == OP_ADD when decrypted, which is precisely what you don't know. If you're merely testing that op == OP_ADD as an encrypted value (i.e. OP_ADD is actually the encrypted form of your add opcode), then the program is actually not encrypted, but merely has annoying-to-read semantics. To analogize: it's like encrypting a password on the client before sending it to the server, and then just straight string comparing them; it means your passwords aren't encrypted on the server, merely that your passwords are uglier than what the user entered.
The trick would be to test if if op == OP_ADD when decrypted
Hmm, this is a point of confusion for me then, because isn't that exactly what FHE allows you to do (and in fact its entire point)? HE allows you to add or multiply encrypted values, and FHE extends HE so that you can perform arbitrary computation. That must mean the == operator is supported, so it seems like it must be possible to do this.
Also, thank you for talking through this with me. It's much appreciated.
FHE extends HE so that you can perform arbitrary computation
FHE doesn't extend HE in the sense that it adds operation types other than addition and multiplication but it allows unlimited chaining of the two operations. This in turn enables arbitrary operations because you can express any function (i. e. any chain of atomic operations) by means of additions mod 2 and multiplications mod 2 (which is equivalent to XOR and AND) when you turn it into a boolean circuit representation. The contribution of FHE is a way to a) clean operands from noise or to b) do not add noise to the operands in the first place because noise is the limiting factor for circuit depth in HE, where "depth" means the number of possible subsequent multiplications.
You're very welcome, this is totally fun, and hopefully we'll both come out wiser.
That must mean the == operator is supported, so it seems like it must be possible to do this.
OK, I understand what you meant with the code now, but the problem is you won't know the answer to your equality comparison. In the same way that add(encryptedIntegerA, encryptedIntegerB) gives you encryptedIntegerC whose value is unknown but which you know decrypts to a + b, you know that equals(encryptedIntegerA, encryptedIntegerB) results in encryptedBooleanC, but you don't know whether that decrypts to true or false. So what do you execute next? It's not that it doesn't know until runtime which branch to take; it's that it doesn't know ever. The whole point FHE is that the executing machine doesn't know the answers themselves, just what they encrypt to. So I'm not sure--no matter how much meta eval you make it do--how it can decide what code to actually execute without decrypting something.
Edit: though I appear to be wrong about this. From Wikipedia:
If the morphisms of some wide supercategory of C include the primitive recursive functions or even all computable functions, then any encryption operation which qualifies as an endofunctor of this supercategory is "more fully" homeomorphic since additional operations on encrypted data (for example conditionals and loops) are possible.
That certainly supports your point. I suppose--more speculation by me-- it must compute both sides of the conditional (in this case, execute the OP_ADD branch and the OP_MULT branch) and then pick one in a way that makes it impossible to tell which "won". That would make a bytecode interperter really impractical, since it would have to compute a huge superset of what any actual bytecode program does, but not logically impossible.
The output of the above program would be either "hello world" or "goodbye world". The output is encrypted, so you won't be able to tell. However, it's not true that you needed the decryption key to evaluate "x == 5". That must mean you can do arbitrary conditionals, loops, branching etc without the decryption key.
Did you see my edit above? I think you're right based on working back through the Wikipedia FHE article, but I also think it would mean executing every possible path, i.e. you'd need to at least evaluate "hello world" and "goodbye world", since the computer executing it doesn't know which it turns out to be. As applied to a bytecode interpreter, that would seem to mean it has to execute every possible program the same length as your bytecode, since it doesn't know what any of them do.
Keep going for all the powers of two expressible in the system and you can quickly check if every bit is set. This makes proving security for functional schemes that allow malleability very difficult, since you have to prove that the reachable set of states with the built in malleability does not reveal sufficient information for the attacker to compromise the security of the system.
One more thing worth mentioning is that a direct comparison of ciphertexts doesn't work for semantically secure schemes. Anything that is IND-CPA, for example RSA-OAEP, will have the same plaintext encrypt to two different ciphertexts. Giving the untrusted server the ability to determine whether two ciphertexts will destroy the semantic security of the scheme, by definition.
If you can do arbitrary computations, you can do loops and conditionals and whatever else you want. FHE claims to support arbitrary computations, so by definition it must support the ability to do any loop or any conditional.
Think of it this way: A conditional is "if this, do that." If the conditional is true, then the branch is executed. The output of the branch is still encrypted, but it's not true that you need the decryption key just to evaluate the branch. Right?
It is possible that you could have FHE primitives that are not sufficient to build a Turing complete interpreter. Otherwise, you can clearly construct a completely obfuscated system by nesting FHE inside an interpreter run inside FHE... though that is likely to be slow enough to be completely impractical.
I'm not an expert, but I think this is the difference: FHE uses known (unencrypted) operations to transform unknown (encrypted) data. It's true the program is data, but to run it you'd have to decrypt it. With FHE the operations are supplied from outside the ciphertext.
FTR, hcrypt predates indistinguishability obfuscation by a couple of years. As far as I can tell this really is a straightforward VM working with homomorphically-encrypted opcodes and data, and not an implementation of Garg and friends's work.
Theoretically speaking, I doubt this method holds: there is no theoretical analysis of it at all in the papers to support it. It certainly doesn't hold in the virtual blackbox model, which is what the theorem alluded above assumes.
Comments
This is talking about a completely different primitive (indistinguishability obfuscation) so FHE is fine. In fact this is talking about an exceptionally strong characterization of IO (virtual black-box) which is not used in current research on the subject.
Would you expand on this?
From the abstract: "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"
That sounds like an exact description of FHE, and the paper seems to claim something is impossible. So I'm trying to figure out: If the paper isn't claiming FHE is impossible, then what is that "something" and how does it relate to FHE?
So the obvious difference is that if I run an obfuscated program, I'd expect to get the same output as the original program - the obfuscated program is to an extent expected to perform as a normal program, but be unreadable.
With HE, you operate on encrypted data and what you get out is still encrypted data - you never have knowledge of what the data is, you just know you've done something to it. So I could perhaps add two encrypted numbers together to obtain something I know to be the sum (but have no idea what the sum is).
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.)
That 'something' is virtual black-box indistinguishability obfuscation. It's a way of 'hiding' (in some sense) a program rather than the data a program acts on. FHE is a way of carrying out any program over encrypted data. It hides the data but not the program acting on it. IO hides the program but not the data.
Since programs are data, shouldn't it be possible to write an interpreter which executes encrypted bytecode? That is, the only thing a reverse engineer would be able to conclude is "an interpreter is executing some bytecode, but we don't know what it's executing." The bytecode (the algorithm itself) is data, and since FHE hides the data, the algorithm remains encrypted and hidden.
If it's possible to add or multiply without knowing what's being added or multiplied, then it seems like it should be possible to do computation without revealing the algorithm being used.
EDIT: I should disclaim that I have exactly no expertise here. This is all me having fun speculating.
I think you're being too handwavy about what FHE is capable of. FHE means that specific operations performed on encrypted data result in data that, when decrypted, have the right result in cleartext. It's not "hiding the data". So it can't run your encrypted bytecode, only transform it into other, also encrypted bytecode, which it also can't interpret. Executing encrypted bytecode doesn't really make sense, because the bytecode tells its interpreter what to do. Either the interpreter can read that information and do it, or it can't. The former means its not encrypted in the first place, and the latter means it won't work. You're trying to use a scheme by which the interpreter doesn't how to evaluate a function, but evaluates it correctly anyway.
Agreed, it's fun to speculate! I love this stuff.
So my understanding of FHE is that it can take an arbitrary circuit (any arbitrary program) and convert it into a circuit which operates on encrypted data.
That means it must be possible to write the equivalent of
etc, where "op" is encrypted data. By extension, you can write an entire interpreter for encrypted bytecodes.Now, when the program executes, it's obviously possible to monitor it and watch what's being done. However, until it executes, the bytecode remains secret. That means it should be possible to ship programs which are impossible to analyze until they're actually executed.
It's a common malware technique to write a program which contains an encrypted subprogram, which is only decryptable on a certain target machine. (For example, you could use a specific computer's MAC address as an ecryption key, which means no reverse engineer can analyze it except on that specific machine.)
FHE, on the other hand, provides the opportunity to ship a turing-complete interpreter to everyone, which executes encrypted bytecodes which can't be analyzed until execution time. That means a FHE program could be a timebomb set to wipe your harddrive at some specific date and you wouldn't know it, since the best you could determine beforehand is "this interpreter sometimes tries to execute shell commands" without actually seeing which commands it's capable of executing in practice until it's too late.
That's the trick. It isn't. Let's loosely stick to your example.
This, when compiled for the hcrypt VM, turns into something like The obvious question is: How do you hide what branch is taken? The hcrypt VM (as all processors and TMs) is a state machine. The states essentially are the status flags (zero result, addition overflow, minus result,...) and the program counter PC. In line (address) 1, the machine decides, whether op is equal to var and sets the zero-flag to 1 if this is the case. The comparison is an implicit subtraction, so if the two values are equal, then the result is 0 and the zero flag switches to 1. In the next machine cycle (PC is 3) we want to branch. The branch operation is just a simple assignment (PC=address). The assigned value can be expressed bitwise Case 1: var==op Case 2: var!=op Thinking in wires, this is the implementation of a demultiplexer or selector. This is the essential curcuit for the hcrypt VM and oblivious to an observer. The most basic application is the command selector. Assume, we have the opcode in a register OP and the operands in OP1 and OP2. The ALU then operates like Since all the operands and registers (this incudes the machine opcodes) are encrypted, the observer does know, she's looking at a branch selector or an encrypted ALU but she cannot decide what branch is taken or what operation is executed.Curious about a detail here. If this machine can evaluate AND and XOR, then how do you prevent a malicious attacker with the public key from performing encrypted each power of two, performing an AND and comparing with zero?
Does this imply that hcrypt VM is not necessarily equal to a Turing machine? The program counter seems like it could definitely cover finite automata, but it doesn't seem expressive enough to simulate a stack. If PC is always encrypted then it ends up having to encode both current state and the information necessary to evaluate the branch implicitly as a state change, which again seems more like finite automata.If you guys figured out how to securely implement control ( halting, loops, etc ), without functional encryption, that would be a huge breakthrough in FHE.
The attacker can do whatever she wants. You can't prevent her from doing anything. But maybe you can elaborate on what you mean with "each power of two". When trying to compare with zero (what zero?), keep in mind we're talking about a probabilistic cryptosystem. The machine is just an application of the underlying scheme, so it's not the machine that provides the atomic functions.
To be precise, the state of the machine includes the flags, the PC and memory. It's easy to implement a simple stack pattern in circuits but you don't need it in order to implement arbitrary functions.
We already published the solution for encrypted memory access and encrypted program flow control (without unfolding) but halting is an issue you (at least to my knowledge) cannot solve under the assumptions we made.
Just went and read your paper.
Doing the above will make it very difficult to prove the security of malleable cryptosystem, something that Boneh, Sahai, and Waters have written multiple papers on. The approach of finding a minimum number of cycles to complete the computation seems much more effective, if restrictive in the number of operations that can be evaluated.I'll e-mail you guys offline.
The termination problem is the major issue. You cannot generate a selectively decryptable signal from inside the encrypted code. In other words, being able to generate a halt signal to mark the end of the program flow immediately invalidates the security of the entire container.
Wow, this is fantastic! Thank you so much for your reply. I'm going to sleep soon, so I'll need some time to study this, but I just wanted to say how much I appreciate your comment. And welcome to HN, by the way!
Do you happen to have an email address I could reach you at with further questions? (If you don't want to post it publicly, please feel free to email me if you'd like: sillysaurus3@gmail.com)
The trick would be to test if if op == OP_ADD when decrypted
Hmm, this is a point of confusion for me then, because isn't that exactly what FHE allows you to do (and in fact its entire point)? HE allows you to add or multiply encrypted values, and FHE extends HE so that you can perform arbitrary computation. That must mean the == operator is supported, so it seems like it must be possible to do this.
Also, thank you for talking through this with me. It's much appreciated.
FHE doesn't extend HE in the sense that it adds operation types other than addition and multiplication but it allows unlimited chaining of the two operations. This in turn enables arbitrary operations because you can express any function (i. e. any chain of atomic operations) by means of additions mod 2 and multiplications mod 2 (which is equivalent to XOR and AND) when you turn it into a boolean circuit representation. The contribution of FHE is a way to a) clean operands from noise or to b) do not add noise to the operands in the first place because noise is the limiting factor for circuit depth in HE, where "depth" means the number of possible subsequent multiplications.
You're very welcome, this is totally fun, and hopefully we'll both come out wiser.
OK, I understand what you meant with the code now, but the problem is you won't know the answer to your equality comparison. In the same way that add(encryptedIntegerA, encryptedIntegerB) gives you encryptedIntegerC whose value is unknown but which you know decrypts to a + b, you know that equals(encryptedIntegerA, encryptedIntegerB) results in encryptedBooleanC, but you don't know whether that decrypts to true or false. So what do you execute next? It's not that it doesn't know until runtime which branch to take; it's that it doesn't know ever. The whole point FHE is that the executing machine doesn't know the answers themselves, just what they encrypt to. So I'm not sure--no matter how much meta eval you make it do--how it can decide what code to actually execute without decrypting something.
Edit: though I appear to be wrong about this. From Wikipedia:
If the morphisms of some wide supercategory of C include the primitive recursive functions or even all computable functions, then any encryption operation which qualifies as an endofunctor of this supercategory is "more fully" homeomorphic since additional operations on encrypted data (for example conditionals and loops) are possible.
That certainly supports your point. I suppose--more speculation by me-- it must compute both sides of the conditional (in this case, execute the OP_ADD branch and the OP_MULT branch) and then pick one in a way that makes it impossible to tell which "won". That would make a bytecode interperter really impractical, since it would have to compute a huge superset of what any actual bytecode program does, but not logically impossible.
the problem is you won't know the answer to your equality comparison.
You don't need to know the answer, though.
The output of the above program would be either "hello world" or "goodbye world". The output is encrypted, so you won't be able to tell. However, it's not true that you needed the decryption key to evaluate "x == 5". That must mean you can do arbitrary conditionals, loops, branching etc without the decryption key.If I'm wrong about this, I don't understand why.
Did you see my edit above? I think you're right based on working back through the Wikipedia FHE article, but I also think it would mean executing every possible path, i.e. you'd need to at least evaluate "hello world" and "goodbye world", since the computer executing it doesn't know which it turns out to be. As applied to a bytecode interpreter, that would seem to mean it has to execute every possible program the same length as your bytecode, since it doesn't know what any of them do.
tl;dr here be dragons.
The ability to evaluate statements such as x == 5 falls under the realm of functional encryption ( see Boneh, Sahai, and Waters for a good intro http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.383... ).
You have to be very careful when mixing functional schemes with FHE schemes as it is very easy to create a completely insecure system.
For example, if you could evaluate arbitrary circuits consider what happens if you can evaluate equals and bitwise AND, two simple circuits.
Keep going for all the powers of two expressible in the system and you can quickly check if every bit is set. This makes proving security for functional schemes that allow malleability very difficult, since you have to prove that the reachable set of states with the built in malleability does not reveal sufficient information for the attacker to compromise the security of the system.One more thing worth mentioning is that a direct comparison of ciphertexts doesn't work for semantically secure schemes. Anything that is IND-CPA, for example RSA-OAEP, will have the same plaintext encrypt to two different ciphertexts. Giving the untrusted server the ability to determine whether two ciphertexts will destroy the semantic security of the scheme, by definition.
You can do arbitrary computations, but you only get the encrypted result. So you can't actually tell whether x == y unless you have the key.
If you can do arbitrary computations, you can do loops and conditionals and whatever else you want. FHE claims to support arbitrary computations, so by definition it must support the ability to do any loop or any conditional.
Think of it this way: A conditional is "if this, do that." If the conditional is true, then the branch is executed. The output of the branch is still encrypted, but it's not true that you need the decryption key just to evaluate the branch. Right?
It is possible that you could have FHE primitives that are not sufficient to build a Turing complete interpreter. Otherwise, you can clearly construct a completely obfuscated system by nesting FHE inside an interpreter run inside FHE... though that is likely to be slow enough to be completely impractical.
I'm not an expert, but I think this is the difference: FHE uses known (unencrypted) operations to transform unknown (encrypted) data. It's true the program is data, but to run it you'd have to decrypt it. With FHE the operations are supplied from outside the ciphertext.
FTR, hcrypt predates indistinguishability obfuscation by a couple of years. As far as I can tell this really is a straightforward VM working with homomorphically-encrypted opcodes and data, and not an implementation of Garg and friends's work.
Theoretically speaking, I doubt this method holds: there is no theoretical analysis of it at all in the papers to support it. It certainly doesn't hold in the virtual blackbox model, which is what the theorem alluded above assumes.