I can verify their existence, but you don't need to take my word for it - much of the research on fully homomorphic encryption is publicly available through the IACR's online preprint database, http://eprint.iacr.org . I doubt FHE is a good solution for your project, though. The technique is not quite ready for primetime due to seriously slow performance. It gets better every year but it will be a while yet before you'll be able to diff an encrypted file using FHE.
EDIT: Though now that I think about it you might be able to code a custom diff circuit for FHE that borders on feasibility. It depends on the algorithm used, really. File diff seems spiritually similar to some of the bioinformatics work being done with privacy-preserving edit distance computation on encrypted DNA sequences.
I was not aware of the lackluster performance. That is really too bad.
The consistent feedback I get about file sync (from techies) is they really don't want to be uploading a whole file every time they change something. I agree, but to have client-side encryption such that you're data is protected from the server host as well as people who gain access to said server seems to preclude efficient sync with current tech. Which is again too bad.
I am no crypto expert so rolling my own / building off this FHE is not really possible. I do understand usage of things like AES and RSA well enough though to know that adequate security precludes diffing/efficient sync.
Think of it this way - any (current) crypto solution is likely to be much slower and more bandwidth-intensive than simply re-uploading the file every time they change something. In theory you could also use a secure multiparty computation scheme to apply file diffs generated by the client.
FHE is currently not practical for performance reasons. However, there are lots of papers out there on 'somewhat homomorphic encryption', where you restrict the types of operation you perform on encrypted data in order to get reasonable performance. For example, if you google for 'CryptDB' you'll find a paper describing a somewhat homomorphic database system. I think there was also a paper called Autocrypt or somesuch in last year's CCS that describes a system that automatically transforms certain web applications to use somewhat homomorphic encryption. I'm sure both of those papers will have relevant references that you can find out more from.
If you are willing to pay a different price - additionally to the current version keep also the last version locally, calculate, encrypt and upload the diff and later download the base version and all the diffs and apply the diffs after decrypting everything. This trades storage space on both sides and download volume for upload volume and it obviously heavily depends on the usage patter whether this is a good trade-off or not.
I touched on this in an above comment[1] (after you posted so I didn't expect you to see it), but essentially because of how AES CBC[2] encryption works, an encrypted block relies on the previous block to correctly be decrypted. Uploading and replacing blocks that are different will not work; the next time that file is decrypted every block after the first newly uploaded one will not be correct.
You could for example use ECB, OFB or CTR mode and actually update the file (some options are obviously a bad choice) but I thought of storing the file and the diff together and only apply the diff after decryption so there is no need to mess with the encrypted data in the first place.
> seems to preclude efficient sync with current tech.
I disagree. You can deterministically chunk the large file with one of the existing rolling checksum schemes, and then use the chunks as your primitive instead of whole files. The server only sees encrypted chunks. The client knows to only upload changed chunks.
That still leaves important choices to be made about cipher mode, key management, etc. But it's not intractable.
Assuming you are using AES with CBC, best case you will have to resend every block after and including the first one that changed.
My understanding is that CBC is among the most secure forms of AES encryption because it is essentially impossible to have patterns in data (unlike EBC). Practically speaking then one must assume that it is common to upload most of a file. Any software that boasts this security cannot effectively 'diff' your files.
You don't have to apply the CBC mode to complete files. If it is secure for a 1 MB file, I don't see why it would be insecure for 100 parts of a 100 MB file.
If you manage to merge small files into the same blocks, you even gain some privacy because the server can't even tell the number of files anymore.
[1] also has a discussion of the trade-offs of the different modes of operation for whole disk encryption. That seems related here because nobody wants to rewrite the whole disk after changing the first byte.
There are other modes that are more suitable for random access. For example, TrueCrypt uses XTS mode. Tarsnap uses CTR mode. Either would satisfy the requirement of allowing you to edit one block without rewriting all the blocks that follow.
I also need an implementation, but my fellow crypo researcher told me that there is the problem that no FHE can exist until we don't find a way to write onto the encrypted container as often as required, without damaging it's structure after only a few edits. So basically all current implementation existing (known to him) were not able to really qualify as a solution, because the inevitable destruction of the data after a limited number of edits. Another point was performance, but that wouldn't be a deal breaker according to him.
But he also said, that if someone finds a way to truly create an FHE-Scheme that works for unlimited amounts of edits, then it would be truly a ground-breaking thing to the whole crypto community. It's highly welcomed, but he is not that optimistic about it for the near future.
I know of no general system, but you may be interested in the paper "On Hiding Information from an Oracle". I'd give you a link, but I'm on my phone right now. It discusses homomorphic encryption schemes for 3 functions that are relevant to cryptography. Quadratic root, discrete logarithm... and one other (maybe prime factorization? Probably not). Their scheme is quantifiably strong and a function of the size of the inputs.
Look into tarsnap, which solves exactly this problem; looking around Colin's site should give you an idea how it works without needing to delve into the code (which _may_ be ok; it's not OSS.)
Basically, generate a tarball, split that into chunks at e.g. zero bytes (tarsnap uses a smarter algorithm), upload any chunks that the server does not have.
If I were Google I would fund the heck out of homomorphic encryption research.
As Google tries to gobble up even more of everyone's data and every waking habit as they try to improve Google Now and other services, the privacy concerns are only going to grow bigger. It will be not just a drain on their public image (just like it is on Facebook's image), but it would also give competitors a lot more opportunities to take jabs at them. Think Scroogled, but 10 fold.
Homomorphic encryption would pretty much fix all of that, and they wouldn't even need to give up their data collection (or not as much).
Unfortunately not. HE has some performance issues (that might be solveable with time) but the primary issue is that Google do actually want to see exactly what you're doing. It's important for basically everything Google does that makes it money.
Furthermore, the privacy concerns are nowhere near great enough. All of the mainstream privacy concerns have come from Google releasing your information to others (Google Buzz, that recent ECHR case etc) and not Google keeping information themselves. Furthermore, since I assume that what you're really talking about here is emails, it would be impossible to practically implement a HE system for emails that would allow for searching (because one could derive meaning from emails by sending them the right queries). It'd be no better than client-side encryption, and no one really wants that.
No, the people for which this is really useful is large non-IT companies like Boeing or healthcare companies etc. They have huge data processing or storage requirements, and frequently have to run around hoops in order to ensure data is not transmitted in a way that would breach commercial agreements or confidentiality requirements.
The problem is that frequently these workloads (especially for companies like Boeing) will involve much data, and HE tends to come with a large size increase and performance drop - so it's often too costly, which is a shame.
Can you expand a bit more on the type of commercial agreements and confidentiality requirements of Boeing? In particular, what kind of data would the agreements pertain to, and who would the other parties be? Would the 'hoops' occur only for internal data transmission, or is it because they need to share it with 3rd-party organisations? I'm a researcher in the area, and I'm familiar with stuff like that from the healthcare domain, where you have e.g. lots of different hospitals that want to share certain data for research purposes, but I'm curious as to the use cases more commercial organisations might have.
It's neither. They make the assumption that their combined cloud partners aren't all in cahoots, and distribute their data such that the probability that a) one can intercept enough chunks and b) one can infer meaning from the chunks is very low.
The cynical part of me wants to say that it's very similar to a standard mapreduce, and the security properties came for free/very little.
I think you are wrong. Google's current business requires that they are able to match your interests to ads. Contrary to popular belief, it has nothing to do with selling you out to advertisers and it doesn't even strictly require Google to know all about you.
If they can efficiently apply FHE to your data and produce an encrypted set of ads that only you can unscramble, they'll make plenty of money.
It's not at all clear that this is feasible, but if I had billions of dollars burning a hole in my pocket, I'd probably fund FHE research.
No, it relies on them being able to do that, but also to be able to improve their products such that they stay relevant. Things like A/B testing require Google to know what the user is doing in order to test their effectiveness - a FHE setup would ruin that.
In any case, I'm not sure how this would stop them from tracking in the first place.
CHY872 is right. Who benefits most from this are governments, spy-agencies, military and a small a solid number of security-aware civilists. This is right as long as nobody enforces FHE to the government, but I doubt that it would occur in the USA at this time from that side. If it happens at all, which I also highly doubt, then it maybe somewhere in Europe.
"In this work, we initiate a theoretical investigation of obfuscation. Our main result is that,
even under very weak formalizations of the above intuition, obfuscation is impossible."
I haven't spent too much time meditating on the implications of the paper, so I was hoping to hear from someone who has. Does this paper strike a mortal blow to FHE? Or is this paper pointing out a result that can be ignored in practice?
When I get a few hours I'll spend some time trying to come up with examples of what the paper is talking about and hopefully discover the truth for myself, but if someone here has already done that, please chime in!
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.
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.
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.
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.
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?
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.
>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.
>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.
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)
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.
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.
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)?
(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.
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'.
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.
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.
>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.
As other said, their not talking about the same obfuscation. If you are interested in code obfuscation and a way to prove that a formally correct obfuscator is impossible, you might want to read a paper called “Can a Program Reverse-Engineer Itself?” [1] I worked on as an undergrad.
The idea is that a correct obfuscator should only obfuscate and not change the program's semantics, which means that it can't change constants that may be displayed to the users, like hardcoded integers and strings. If you use these in a Quine [2] structure to be able to retrieve your original code, then the obfuscator can't do anything: it it breaks the Quine it is not a correct obfuscator, if it doesn't then you can trivially get back the original code. And what is interesting here is that it is possible to take any source code and make a Quine which has it as a payload (it will do the same thing as the original source code except that it will also be a Quine), which is something we had done already for another paper [3].
You can build everything on top of that - (a AND b) XOR 1 = a NAND b and you can build any boolean function out of NAND gates. So just make the cipher text the (encrypted) memory of a virtual machine, design a processor out of the mentioned primitives just like you design any ordinary processor and then execute it. And that is what they actually did with the Shape CPU [1].
The way I've understood it is that only addition has been possible so far. With a multiplication operation, you can get a field, and do "everything" with the real/complex numbers.
Well a homomorphism applies to a group and a group can only have one operator by definition. That won't change probably. Rings have two operators, fields are rings that support cancellation and integral fields I believe support inverses as a rule and where you'd get "everything" I believe.
HE is supposed to be the holy grail of cloud computing, but last time I looked at it, it was dog slow. I glanced at the site, but saw no performance figures...
100 comments
[ 3.9 ms ] story [ 118 ms ] threadThis would be great for an encrypted file synchronization project I am working on; being able to diff an encrypted file would be amazing.
EDIT: Though now that I think about it you might be able to code a custom diff circuit for FHE that borders on feasibility. It depends on the algorithm used, really. File diff seems spiritually similar to some of the bioinformatics work being done with privacy-preserving edit distance computation on encrypted DNA sequences.
EDIT2: Here's a paper that discusses an FHE 'hardware platform': http://eprint.iacr.org/2014/106.pdf
The consistent feedback I get about file sync (from techies) is they really don't want to be uploading a whole file every time they change something. I agree, but to have client-side encryption such that you're data is protected from the server host as well as people who gain access to said server seems to preclude efficient sync with current tech. Which is again too bad.
I am no crypto expert so rolling my own / building off this FHE is not really possible. I do understand usage of things like AES and RSA well enough though to know that adequate security precludes diffing/efficient sync.
[1] -- https://news.ycombinator.com/item?id=7787791
[2] -- http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#...
I disagree. You can deterministically chunk the large file with one of the existing rolling checksum schemes, and then use the chunks as your primitive instead of whole files. The server only sees encrypted chunks. The client knows to only upload changed chunks.
That still leaves important choices to be made about cipher mode, key management, etc. But it's not intractable.
My understanding is that CBC is among the most secure forms of AES encryption because it is essentially impossible to have patterns in data (unlike EBC). Practically speaking then one must assume that it is common to upload most of a file. Any software that boasts this security cannot effectively 'diff' your files.
EDIT: Formatting
If you manage to merge small files into the same blocks, you even gain some privacy because the server can't even tell the number of files anymore.
[1] also has a discussion of the trade-offs of the different modes of operation for whole disk encryption. That seems related here because nobody wants to rewrite the whole disk after changing the first byte.
1: https://en.wikipedia.org/wiki/Disk_encryption_theory
But he also said, that if someone finds a way to truly create an FHE-Scheme that works for unlimited amounts of edits, then it would be truly a ground-breaking thing to the whole crypto community. It's highly welcomed, but he is not that optimistic about it for the near future.
Basically, generate a tarball, split that into chunks at e.g. zero bytes (tarsnap uses a smarter algorithm), upload any chunks that the server does not have.
As Google tries to gobble up even more of everyone's data and every waking habit as they try to improve Google Now and other services, the privacy concerns are only going to grow bigger. It will be not just a drain on their public image (just like it is on Facebook's image), but it would also give competitors a lot more opportunities to take jabs at them. Think Scroogled, but 10 fold.
Homomorphic encryption would pretty much fix all of that, and they wouldn't even need to give up their data collection (or not as much).
No, the people for which this is really useful is large non-IT companies like Boeing or healthcare companies etc. They have huge data processing or storage requirements, and frequently have to run around hoops in order to ensure data is not transmitted in a way that would breach commercial agreements or confidentiality requirements. The problem is that frequently these workloads (especially for companies like Boeing) will involve much data, and HE tends to come with a large size increase and performance drop - so it's often too costly, which is a shame.
The cynical part of me wants to say that it's very similar to a standard mapreduce, and the security properties came for free/very little.
If they can efficiently apply FHE to your data and produce an encrypted set of ads that only you can unscramble, they'll make plenty of money.
It's not at all clear that this is feasible, but if I had billions of dollars burning a hole in my pocket, I'd probably fund FHE research.
"On the (Im)possibility of Obfuscating Programs"
"In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible."
I haven't spent too much time meditating on the implications of the paper, so I was hoping to hear from someone who has. Does this paper strike a mortal blow to FHE? Or is this paper pointing out a result that can be ignored in practice?
When I get a few hours I'll spend some time trying to come up with examples of what the paper is talking about and hopefully discover the truth for myself, but if someone here has already done that, please chime in!
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?
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).
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?
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?
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.
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.
> 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.)
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).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...
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.)
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.
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.
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.
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?
> 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.
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.
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.
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.
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.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 you guys figured out how to securely implement control ( halting, loops, etc ), without functional encryption, that would be a huge breakthrough in FHE.
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.
I'll e-mail you guys offline.
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.
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.
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.
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)
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.
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?
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.
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.
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.
The idea is that a correct obfuscator should only obfuscate and not change the program's semantics, which means that it can't change constants that may be displayed to the users, like hardcoded integers and strings. If you use these in a Quine [2] structure to be able to retrieve your original code, then the obfuscator can't do anything: it it breaks the Quine it is not a correct obfuscator, if it doesn't then you can trivially get back the original code. And what is interesting here is that it is possible to take any source code and make a Quine which has it as a payload (it will do the same thing as the original source code except that it will also be a Quine), which is something we had done already for another paper [3].
[1] http://eprint.iacr.org/2011/497
[2] https://en.wikipedia.org/wiki/Quine_%28computing%29
[3] http://eprint.iacr.org/2011/099
Add with carry-out seems like it could be use to build some complex systems.
[1] https://hcrypt.com/shape-cpu/
https://en.wikipedia.org/wiki/Group_homomorphism
The way I've understood it is that only addition has been possible so far. With a multiplication operation, you can get a field, and do "everything" with the real/complex numbers.
Not so. The notion's far more general: https://en.wikipedia.org/wiki/Ring_homomorphism
This gives us a notion of homomorphisms between fields.
https://en.wikipedia.org/wiki/Homomorphism for more general notions of homomorphisms.