[rrrrtttt]

S3QL may be a good fit for your needs. It's a FUSE filesystem for S3 that supports encrypted dedup snapshots. You can do backups by rsyncing your current state into the filesystem and snapshotting it. I considered using it for my backups but ended up choosing Attic, so I can't say how well it works in practice.

[Freaky]

Unfortunately S3QL uses MAC-then-encrypt[1], which is pretty strongly discouraged[2]. Very nice there's a detailed writeup on the details in the docs though, wish more projects did that.

1: http://www.rath.org/s3ql-docs/impl_details.html (last paragraph) 2: http://www.daemonology.net/blog/2009-06-24-encrypt-then-mac....