Homomorphic encryption implementation

by gaigepr • 12 years ago

117 96 12 years ago

gaigepr6• 12 years ago

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.

swordswinger126• 12 years ago

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

gaigepr6• 12 years ago

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.

X43• 12 years ago

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.

TallGuyShort2• 12 years ago

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.

TallGuyShort2• 12 years ago

Here's a link if anyone's interested: https://dl.acm.org/citation.cfm?id=28417

JoachimSchipper• 12 years ago

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.

higherpurpose• 12 years ago

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).

CHY8727• 12 years ago

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.

anonymousDan2• 12 years ago

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.

arebop• 12 years ago

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.

X43• 12 years ago

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.

sillysaurus316• 12 years ago

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!

swordswinger126• 12 years ago

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.

sillysaurus316• 12 years ago

Would you expand on this?

From the abstract: "Informally, an obfuscator O is an (eﬃcient, 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?

pbsd• 12 years ago

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.

SilasX8• 12 years ago

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.

darkmighty3• 12 years ago

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.

p4bl0• 12 years ago

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

X43• 12 years ago

Thank you so much for posting this now! I was writing a paper about this topic and this arrives just in the right time! Awesome.

gaigepr6• 12 years ago

Glad I to be of help, I would be interested to read your paper when it is publicly available!

guelo• 12 years ago

According to https://hcrypt.com/scarab-library/, the functions that you can do on encrypted texts are

  Add cyphertexts (= XOR)
  Multiply cyphertexts (= AND)
  Add with carry in and carry out
  Add with carry out

I'm not really familiar with homomorphic theory, but it doesn't seem like you could build that much on top of these primitives.

CGamesPlay• 12 years ago

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.

danbruc3• 12 years ago

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/

dvanduzer2• 12 years ago

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.

darkxanthos2• 12 years ago

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.

toolslive• 12 years ago

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...

sneak• 12 years ago

Sometimes I am really glad that Bootstrap exists.

opnitro• 12 years ago

Totally read this as homophobic encryption...

emocakes• 12 years ago

I was hoping for some homophobic encryption.

Homomorphic encryption implementation

Related Stories