10 ms·

Homomorphic encryption implementation

117 points by gaigepr 12y ago

gaigepr 12y 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.
- swordswinger12 12y 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 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 http://eprint.iacr.org/2014/106.pdf
  - deleted 12y ago
    [deleted]
  - gaigepr 12y 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.
    - swordswinger12 12y ago
      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.
    - anonymousDan 12y ago
      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.
    - danbruc 12y ago
      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.
      - gaigepr 12y ago
        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 https://news.ycombinator.com/item?id=7787791 [2] -- http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Cipher-block_chaining_.28CBC.29 http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#...
- X4 12y 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.
- TallGuyShort 12y 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.
  - TallGuyShort 12y ago
    Here's a link if anyone's interested: https://dl.acm.org/citation.cfm?id=28417 https://dl.acm.org/citation.cfm?id=28417
- JoachimSchipper 12y 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 12y 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).
- CHY872 12y 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.
  - anonymousDan 12y 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.
sillysaurus3 12y ago
Would anyone comment on http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf 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!
- swordswinger12 12y 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.
  - sillysaurus3 12y 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?
    - CHY872 12y ago
      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).
X4 12y 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.
- gaigepr 12y ago
  Glad I to be of help, I would be interested to read your paper when it is publicly available!
guelo 12y ago
According to https://hcrypt.com/scarab-library/ 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 12y 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.
- danbruc 12y 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/ https://hcrypt.com/shape-cpu/
- dvanduzer 12y ago
  You may want to start here: https://en.wikipedia.org/wiki/Group_homomorphism 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.
  - darkxanthos 12y 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 12y 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 12y ago
Sometimes I am really glad that Bootstrap exists.
opnitro 12y ago
Totally read this as homophobic encryption...
emocakes 12y ago
I was hoping for some homophobic encryption.

117 points by gaigepr 12y 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.

swordswinger12 12y 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 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 http://eprint.iacr.org/2014/106.pdf
- deleted 12y ago
  [deleted]
- gaigepr 12y 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.
  - swordswinger12 12y ago
    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.
  - anonymousDan 12y ago
    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.
  - danbruc 12y ago
    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.
    - gaigepr 12y ago
      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 https://news.ycombinator.com/item?id=7787791 [2] -- http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Cipher-block_chaining_.28CBC.29 http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#...
X4 12y 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.
TallGuyShort 12y 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.
- TallGuyShort 12y ago
  Here's a link if anyone's interested: https://dl.acm.org/citation.cfm?id=28417 https://dl.acm.org/citation.cfm?id=28417
JoachimSchipper 12y 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 12y 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).

CHY872 12y 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.
- anonymousDan 12y 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.

sillysaurus3 12y ago

Would anyone comment on http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf 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!

swordswinger12 12y 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.
- sillysaurus3 12y 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?
  - CHY872 12y ago
    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).

X4 12y 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.

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

guelo 12y ago

According to https://hcrypt.com/scarab-library/ 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 12y 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.
danbruc 12y 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/ https://hcrypt.com/shape-cpu/
dvanduzer 12y ago
You may want to start here: https://en.wikipedia.org/wiki/Group_homomorphism 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.
- darkxanthos 12y 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 12y 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 12y ago

Sometimes I am really glad that Bootstrap exists.

opnitro 12y ago

Totally read this as homophobic encryption...

emocakes 12y ago

I was hoping for some homophobic encryption.