This is about requests for stored data and then the encryption is moot, that mostly affects data in-flight or seized computers if the data is stored. In the latter case you will probably be forced to cough up the decryption keys.
When we're talking about protection against government data requests, only companies that make sure they have access to the absolute minimum client information they possible can do truly have our backs. Everyone else just has good intentions.
That's why I keep recommending tarsnap to customers.
Obviously there could be a tarsnap option to stream the data to be uploaded through an encryption program of your choice, but doing it just as you suggest would nerf a few of tarsnap's prime advantages.
Tarsnap is a combination client-side application and remote service.
I am suggesting instead to use/recommend one of the existing client-side tools that work similar to the tarsnap client does, but don't lock the user into a single service provider.
By using a client-side tool that just generates archives (and isn't tied to a single storage service provider), you can store them anywhere - AWS, iCloud, Google Drive, Rsync.net, a rented VPS, a friends computer, an external hard drive, all of the above. You name it.
Edit: I used 'specify the storage location' very loosely. I.e., I realise it could mean simply piping the archive data to yet another program in the shell.
Personally, I use git-annex, which isn't exactly a backup tool but a general distributed file manager which can, among other things, automatically make encrypted copies of the files to various places (SSH servers, S3, Google Drive, etc).
Both do dedup and encryption, Attic can also store the data remotely via SSH (either with or without installation on the remote end) and Obnam can handle remote storage to an SFTP server.
However, until I have reason to dislike tarsnap's archiving or encryption or AWS, it's simply easier to use a single tool.
It's an almost completely transparent user-space filesystem. Basically you store your files in a given folder, and it automatically stores a parallel encrypted copy in a different folder.
http://www.howtogeek.com/121737/how-to-encrypt-cloud-storage...
Edit: sounds like EncFS has some significant security issues: http://sourceforge.net/p/encfs/mailman/message/31849549/. No recent information in that discussion, so I don't know whether it's all been resolved. Here's an HN discussion of the audit: https://news.ycombinator.com/item?id=7384730
Not if you make the users password the key.
Seems like the only way.
I'm honestly interested because I'm building a distributed system where only the user has the decryption key, and I've always just assumed that password recovery is a lost cause in such systems.