Actually, you can use convergent encryption to dedup encrypted files. It leaks information (because I can tell whether a file that I possess already exists on the server if the server is silly enough to tell me that it took no space/time) but it is indeed encrypted.

Check out this discussion of Mega for more info: https://news.ycombinator.com/item?id=5072680