I'm guessing tarsnap doesn't satisfy the 3rd criteria, nor is tarsnap able to decrypt the user's files, even when the client is connected. Perhaps cperciva can comment.
3rd criteria can be considered a vulnerability, it may allow to know that certain user has a known file. It can be exploited to reveal information about the encrypted files.
Yes, I read that article too. That information leakage vulnerability can be eliminated by requiring the user always upload the file the first time they store it. Subsequent uploads of the same file for the same user could be skipped. De-duplication across users in storage is also possible without leaking information.
What is not possible (AFAIK) is the combination of the two requirements: 1) de-duplication across users, and 2) service provider is not able to decrypt your files. The latter requires the encryption/decryption be done on the client only (service provider doesn't have the keys at all). The former requires access to the unencrypted file, or for the clients to share keys.
