I am developing software that will be used for data backup.

The server will run on Linux. Security in transportation is not an issue (HTTPS or SSH), but the data must be stored encrypted on the server.

The data is not tied to a single computer, so multiple computers should be able to access the same data, if given a key (shared key is acceptable).

The customer should be assured that the data cannot be viewed on the server, either by a curious employee or a hacker. This means that the server should not store the key used to decipher the encryption, but could use it in a transaction if needed.

Being a file server, the network will be saturated, so sending deltas is preferred over sending entire files. The files will also be managed (on the server) by a version control system; whereas the client may or may not have version control. Space is a consideration.

This is what I've come up with:

  • Each user has his/her own mount point
  • Each mount point will be encrypted
  • Files will be decrypted, have the delta applied, then re-encrypted

This sounds a bit inefficient, so I've come here for guidance.

Can file deltas be applied to an encrypted file?

The most important requirements are:

  • Data integrity (updates should never break a file)
  • Minimize network/storage overhead (conserving CPU/ram would be nice, but not necessary)
  • Must be able to be version controlled
  • What is the relationship of the backup service to the version control service?
    – this.josh
    Aug 28, 2011 at 5:43
  • Does the system need to be centraly controlled or could it be distributed?
    – this.josh
    Aug 28, 2011 at 5:44
  • @this.josh - It will totally be distributed. I doubt I can support 10,000,000 or so users on a single system.
    – beatgammit
    Aug 28, 2011 at 16:32
  • In "Files will be decrypted, have the delta applied, then re-encrypted" do you mean "the [VCS] file [containing the previous version(s) of the end-user file] will be decrypted, the delta to the new version of the end-user file calculated, the delta appended to the [VCS] file, and the [VCS] file re-encrypted"? Which bit of that "sounds a bit inefficient" -- the de/re-encryption of the VCS file?
    – Misha
    Aug 29, 2011 at 14:40
  • What are the constraints, more precisely? Does "the network will be saturated sending deltas is preferred" mean that the network is saturated "up" (writes from clients to server) or "down" (reads) or both? Does "the client [might] not have version control" mean that the client may not keep a copy of the "previous version" of the file (which would allow it to calculate the delta itself)? Is it acceptable for the client to run any custom software at all, or must the server present a standard file server interface (NFS/CIFS/WebDAV/sftp/whatever) suitable for direct usage by the end-user?
    – Misha
    Aug 29, 2011 at 14:44

6 Answers 6


Not yet. You are basically describing homomorphic encryption.

Basically you have a file f that you encrypt with function E() notated as E(f).

Now you have delta d which you encrypt with function E() notated as E(d).

You want the new file f' to be equal to f with the delta applied: f'=f+d

Only you dont want to decrypt either E(f) or E(d).

You want E(f) + E(d) = E(f').

And that's homorphic encryption, but it's not ready for production yet. THere are partially homomorphic cryptosystems, but I'm not sure if the file delta would fit into any of the systems. There is one fully homomorphic cryptosystem in development at IBM, but it takes a good amount of computation power and memory and is still slow for large problems.

IBM Research's page on homomorphic encryption http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.homoenc.html

Craig Gentry's PhD Thesis "Fully homomorphic encryption using ideal lattices" This is a break through paper.

Prior to Gentry's thesis there were fully homomorphic systems but those systems could not be made practical. Some existing cryptosystems, RSA for example, are partially homomorphic, meaning that homomorphic operates work for one operation (multiplication for example) but not the other (addition). They also degrade and can only do a limited number of homomorphic operations before causing errors.

Gentry's breakthrough was to establish bootstraping. In my limited understanding, bootstraping establishes a hidden struture capable of maintaining its coherence across operations.

In May of 2011 "Fully Homomorphic Encryption without Bootstrapping" was published bring homomorphic encryption one step closer to real use.

  • I've heard about homomorphic encryption, but I didn't know there was one in development. Do you have any links?
    – beatgammit
    Aug 27, 2011 at 22:15

What about keeping the baseline encrypted and unmodified, and encrypting and storing the deltas separately? When a user wants a particular version of the file, they'd need the baseline and all the deltas to that point. This would be pretty close to space-optimal and network-optimal for writes from the perspective of the file server, but would require additional client-side storage and network bandwidth for reads. Then again, once a client is brought current, any future reads are network-optimal as well. The client is free to use additional space to improve performance in ways that should be pretty obvious.

You could also store encrypted delta-sets, where a client with the key merges a few deltas and encrypts the result, as a way to speed up the initial load by the client. This could be done intelligently to do better than the naive approach would lead to, in terms of network and space on writes, and in any case, would be network- and space-efficient on reads.

Tuning is dependent on the characteristics of the app.

Disclaimer: I am just making this up as I go here; I have no idea if I have described someone else's idea or something.

  • This seems like an SVN-style version control with encryption. Do you know if something like that exists?
    – beatgammit
    Aug 27, 2011 at 22:16
  • No, I don't. I don't know SVN that well (Perforce FTW!) but I thought some of those systems saved the current version whole and previous revisions as diffs. That would dramatically change the network and storage characteristics of what I've proposed. Aug 28, 2011 at 14:10

Beside homomorphic cryptosystem (which RSA is partially one), your 2nd requirement may be achievable depending on how you encrypt the data in the first place.

Assuming you use block cipher in ECB mode, then each block is independent of all others. Which means you are free to decrypt and encrypt any single block in isolation. This would allow you to apply the delta to each block nicely. CTR mode is also a possible mode here. For best result, however, I would recommend ESSIV mode. See http://en.wikipedia.org/wiki/Disk_encryption_theory. This all assumes that you know exactly which sector to modify.

Your 1st and 3rd requirements are not really solvable by encryption alone. Think about disk failure half way through the update. Of course the write will fail, procuding an integrity error.

On the other hand, why don't you use encrypted disk (such as dm-crypt) and mount it on demand, modify the files, and finally unmount it?

  • Lets say I have 10,000,000 clients. If I mount/decrypt/encrypt/unmount each one each time someone pushes a change, that seems like a lot of overhead. I would like the sync to be as real-time as possible, so I could have millions of writes every hour. Would this still be a viable solution in this case?
    – beatgammit
    Aug 27, 2011 at 22:06
  • +1 For the first bit; that sounds quite reasonable. I could send which blocks changed, and then just send the replacement blocks. I could do something like for every 1000 bytes, store it in a 1024 byte block (to allow for incremental change of a file).
    – beatgammit
    Aug 27, 2011 at 22:24
  • It actually is mount/write/unmount. The decrypt/encrypt part is transparent to you. But at the number of clients you quoted, this obviously cannot satisfy due to limited number of loopback devices. So, the best is roll your own based on disk encryption idea. Maybe an abstraction IO filter layer on top of regular C++/Java IO classes?
    – Nam Nguyen
    Aug 28, 2011 at 1:40
  • I can do something clever for the loopback device constraint. It's not 100% necessary that each client has it's own filesystem, but this makes things much simpler from an admin point of view (easy to migrate servers, etc). Do you think that the decrypt/encrypt (although transparent) would make sense on a scale like this? I know it doesn't matter too much for a single user (I use TrueCrypt and don't notice any major performance issues).
    – beatgammit
    Aug 28, 2011 at 5:13
  • 1
    ECB mode is not secure and should not be used.
    – D.W.
    Aug 28, 2011 at 8:33

You have some sensitive local plaintext files, you want to keep a backup copy of (encrypted versions of) those files on some remote server, you have a limited network bandwidth, and you want to set things up so that if the server is compromised by the bad guys, they can't read the plaintext of your files.

That sounds like exactly the situation rsyncrypto was designed to handle:

Sometimes it is necessary to store files on a remote server for backup purposes.

How do you keep the privacy of files stored on a remote server? Encrypt the files prior to sending them. Keep the key locally.

How do you keep the bandwidth usage to a minimum? Use rsync to only transfer the changes.

There is just one problem - the two solutions contradict.

rsyncrypto comes to the rescue.

With rsyncrypto, both objectives can be achieved simultaneously.

-- slightly paraphrased from the rsyncrypto home page

The rsyncrypto algorithm ensures that two almost identical files, when encrypted with rsyncrypto and the same key, will produce almost identical encrypted files. This allows for the low-overhead data transfer achieved by rsync while providing encryption for secure transfer and storage of sensitive data in a remote location.

-- from Wikipedia: rsync variations

Related questions: "Is there an encrypted version control system?" and "How to do rsync-like encrypted backup?"


The primary issue that you need to address is someone compromising the version control system. My impression is that the VCS will be unencrypted as it is responsible for storing the plaintext, but prior to transmission it gets encrypted. If this is not the case than ignore my previous statement. Regardless applying diffs to binary files is quite intensive and causes a huge overhead in terms of space requirements. This can give some extra information

Update to comment

The version control will only be on the server end (git style preferably, but others work too).

My initial comment still stands about it being vulnerable.

The main focus is that I (as the admin) should never be able to read someone else's data

The encryption will handle that, use an algorithm that is lattice based, this is allegedly immune to both classical and quantum algorithms. MIT lattice
description of homomorphic algorithm
I also want to minimize storage space

This is the crux of Disk encryption theory

  • I noticed from your answer that my question was not very clear. The version control will only be on the server end (git style preferably, but others work too). Transmission to the server will be encrypted (SSL/ssh), so that isn't an issue, and encryption should be applied on the server. The main focus is that I (as the admin) should never be able to read someone else's data, but I also want to minimize storage space (if possible). Otherwise I'd just git control the encrypted files as binary.
    – beatgammit
    Aug 27, 2011 at 22:22
  • @tjameson I have updated my post with some extra information.
    – Woot4Moo
    Aug 27, 2011 at 23:33
  • Good point. Do you think that decrypting and encrypting a filesystem (if it was only a few gigabytes) relatively frequently (several times a second [different users, different filesystems]) is viable?
    – beatgammit
    Aug 28, 2011 at 5:04
  • Warning to the original poster: There is a lot of bad advice in this answer. For instance, suggesting lattice-based encryption is poor advice. Homomorphic encryption is not relevant here (and not practical).
    – D.W.
    Aug 28, 2011 at 8:32
  • @dw I would be most curious as to why lattice based encryption is poor advice and also why homomorphic encryption is equally as poor. Any other comments are greatly appreciated as I try to not look foolish :)
    – Woot4Moo
    Aug 28, 2011 at 13:23

The main focus is that I (as the admin) should never be able to read someone else's data, but I also want to minimize storage space (if possible).

A very different approach to minimizing storage space, while never entirely trusting the admin of the remote storage server, is discussed in "Is Convergent Encryption really secure?".

Convergent Encryption is designed to allow the remote storage server to de-duplicate common files, without the admin of the storage server ever getting quite enough information to decrypt whatever is in those files (other than the fact that file A is, in fact, the same as file B, and therefore only needs to be stored once).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.