Hacker News Reader

Comment by gaigepr | Hacker News Reader

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.

View on HN

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

I was not aware of the lackluster performance. That is really too bad.

The consistent feedback I get about file sync (from techies) is they really don't want to be uploading a whole file every time they change something. I agree, but to have client-side encryption such that you're data is protected from the server host as well as people who gain access to said server seems to preclude efficient sync with current tech. Which is again too bad.

I am no crypto expert so rolling my own / building off this FHE is not really possible. I do understand usage of things like AES and RSA well enough though to know that adequate security precludes diffing/efficient sync.

Think of it this way - any (current) crypto solution is likely to be much slower and more bandwidth-intensive than simply re-uploading the file every time they change something. In theory you could also use a secure multiparty computation scheme to apply file diffs generated by the client.

FHE is currently not practical for performance reasons. However, there are lots of papers out there on 'somewhat homomorphic encryption', where you restrict the types of operation you perform on encrypted data in order to get reasonable performance. For example, if you google for 'CryptDB' you'll find a paper describing a somewhat homomorphic database system. I think there was also a paper called Autocrypt or somesuch in last year's CCS that describes a system that automatically transforms certain web applications to use somewhat homomorphic encryption. I'm sure both of those papers will have relevant references that you can find out more from.

If you are willing to pay a different price - additionally to the current version keep also the last version locally, calculate, encrypt and upload the diff and later download the base version and all the diffs and apply the diffs after decrypting everything. This trades storage space on both sides and download volume for upload volume and it obviously heavily depends on the usage patter whether this is a good trade-off or not.

I touched on this in an above comment[1] (after you posted so I didn't expect you to see it), but essentially because of how AES CBC[2] encryption works, an encrypted block relies on the previous block to correctly be decrypted. Uploading and replacing blocks that are different will not work; the next time that file is decrypted every block after the first newly uploaded one will not be correct.

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

> seems to preclude efficient sync with current tech.

I disagree. You can deterministically chunk the large file with one of the existing rolling checksum schemes, and then use the chunks as your primitive instead of whole files. The server only sees encrypted chunks. The client knows to only upload changed chunks.

That still leaves important choices to be made about cipher mode, key management, etc. But it's not intractable.

Assuming you are using AES with CBC, best case you will have to resend every block after and including the first one that changed.

My understanding is that CBC is among the most secure forms of AES encryption because it is essentially impossible to have patterns in data (unlike EBC). Practically speaking then one must assume that it is common to upload most of a file. Any software that boasts this security cannot effectively 'diff' your files.

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

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.

I also need an implementation, but my fellow crypo researcher told me that there is the problem that no FHE can exist until we don't find a way to write onto the encrypted container as often as required, without damaging it's structure after only a few edits. So basically all current implementation existing (known to him) were not able to really qualify as a solution, because the inevitable destruction of the data after a limited number of edits. Another point was performance, but that wouldn't be a deal breaker according to him.

But he also said, that if someone finds a way to truly create an FHE-Scheme that works for unlimited amounts of edits, then it would be truly a ground-breaking thing to the whole crypto community. It's highly welcomed, but he is not that optimistic about it for the near future.

I know of no general system, but you may be interested in the paper "On Hiding Information from an Oracle". I'd give you a link, but I'm on my phone right now. It discusses homomorphic encryption schemes for 3 functions that are relevant to cryptography. Quadratic root, discrete logarithm... and one other (maybe prime factorization? Probably not). Their scheme is quantifiably strong and a function of the size of the inputs.

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.

Reply on news.ycombinator.com