Homomorphic encryption implementation(hcrypt.com)
hcrypt.com
Homomorphic encryption implementation
https://hcrypt.com/
9 comments
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].
[1] https://hcrypt.com/shape-cpu/
[1] https://hcrypt.com/shape-cpu/
You may want to start here:
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.
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.
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.
"Well a homomorphism applies to a group"
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.
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.
You're right. My bad. Thanks for correcting me.
You could run transactions on a signed wallet and even compute interest... I'm sure there are also other, less obvious, use cases as well.
Add with carry-out seems like it could be use to build some complex systems.
Add with carry-out seems like it could be use to build some complex systems.
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).
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.
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.
Yup - Ars can explain it better than me!
http://arstechnica.com/information-technology/2014/04/how-bo...
Clearly, though, this would be a case where homomorphic encryption would not be required - because they've solved the problem without it.
Boeing's technique sounds more like steganography than cryptography.
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.
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.
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.
Can anyone else verify the existence of a truly homomorphic encryption scheme?
This would be great for an encrypted file synchronization project I am working on; being able to diff an encrypted file would be amazing.
This would be great for an encrypted file synchronization project I am working on; being able to diff an encrypted file would be amazing.
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.
EDIT2: Here's a paper that discusses an FHE 'hardware platform': http://eprint.iacr.org/2014/106.pdf
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
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.
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.
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.
> 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.
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.
EDIT: Formatting
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
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.
1: https://en.wikipedia.org/wiki/Disk_encryption_theory
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
I understand now. that is a clever idea; I like it a lot.
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.
Looks like http://en.wikipedia.org/wiki/Duplicity_%28software%29 does something like this.
Ie. client-side encryption that is still rdiffable.
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.
[1] -- https://news.ycombinator.com/item?id=7787791
[2] -- http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#...
[1] -- https://news.ycombinator.com/item?id=7787791
[2] -- http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#...
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.
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.
[deleted]
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.
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.
Here's a link if anyone's interested: https://dl.acm.org/citation.cfm?id=28417
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.
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.
Would anyone comment on http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf ?
"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!
"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!
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.
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.
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.
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.
The details are more complicated, but he/she might be talking about http://eprint.iacr.org/2013/229.pdf
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)?
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.
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.
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.
(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)
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.
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
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?
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?
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.
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'.
[deleted]
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?
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).
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?
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.
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?
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.
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.
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.)
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:
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:
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
Now, however, if I use HE, I will get an algorithm (HX) which takes encrypted input and spits out encrypted output. A third-party will see the corresponding log of inputs and outputs like this:
h3830120cjfakj, 102309123clals => 293sdlzlxdf
94ka3lkc.zdkf, 102kksdllz => 1923939nddd
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...
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.)
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.
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.
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
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.
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
if (op == OP_ADD) { /* interpret addition bytecode */ }
else if (op == OB_MUL) { /* interpret multiplication bytecode */ }
...
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.
That's the trick. It isn't. Let's loosely stick to your example.
if (var == op)
{
do this
}
else
{
do that
}
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>
PC = ((branch AND zero-flag) XOR (PC+1 AND !zero-flag))
PC = ((5 AND 1) XOR (3 AND 0))
PC = ((5 AND 0) XOR (3 AND 1))
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))
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?
If you guys figured out how to securely implement control ( halting, loops, etc ), without functional encryption, that would be a huge breakthrough in FHE.
{x&0x2} = {0x2}
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.
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.
I'll e-mail you guys offline.
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.
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: [email protected])
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: [email protected])
if (op == OP_ADD) { /* interpret addition bytecode */ }
where "op" is encrypted data.
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.
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.
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.
> 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 problem is you won't know the answer to your equality comparison.
You don't need to know the answer, though.
If I'm wrong about this, I don't understand why.
You don't need to know the answer, though.
if (x == 5) { print "hello world"; }
else { print "goodbye world"; }
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.
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?
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?
[deleted]
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.
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.
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].
[1] http://eprint.iacr.org/2011/497
[2] https://en.wikipedia.org/wiki/Quine_%28computing%29
[3] http://eprint.iacr.org/2011/099
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
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...
Sometimes I am really glad that Bootstrap exists.
I was hoping for some homophobic encryption.
Totally read this as homophobic encryption...
I'm not really familiar with homomorphic theory, but it doesn't seem like you could build that much on top of these primitives.