What you describe is nearly exactly how an encrypted backup service called tarsnap works. Basically, it provides de-duplicated, compressed backups to the Amazon S3 cloud using local key files. The difference here is that it deals with data in blocks, not explicit deltas. This means you have no concept of 'history', and separate archives on the service have no strict dependencies on each other (they merely reference certain blocks that have been uploaded). It uses a cli-only interface inspired from tar, and is very handy for cron backups of important data.

There is also a project called ddar, which is designed to provide merely the de-duplication of tarsnap so you can setup your own repository (tarsnap only works with its service).