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.