5 ms·

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 o

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.

by gaigepr 12y ago

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.