A "soon to enter beta" online backup service, Bitcasa, claims to have both de-duplication (you don't backup something already in the cloud) and client side encryption.

http://techcrunch.com/2011/09/12/with-bitcasa-the-entire-cloud-is-your-hard-drive-for-only-10-per-month/

A patent search yields nothing with their company name but the patents may well be in the pipeline and not granted yet.

I find the claim pretty dubious with the level of information I have now, anyone knows more about how they claim to achieve that? Had the founders of the company not had a serious business background (Verisign, Mastercard...) I would have classified the product as snake oil right away but maybe there is more to it.

Edit: found a worrying tweet : https://twitter.com/#!/csoghoian/status/113753932400041984, encryption key per file would be derived from its hash, so definitely looking like not the place to store your torrented film collection, not that I would ever do that.