Deduping is per-user not across users. For the sort of content here, this works well. E.g., static assets of web pages are the ones that are dedup-ed.

The basic algo is to generate a HMAC of the plaintext and compare it against a table of previously uploaded blobs' HMACs. HMAC is keyed with a key derived from the user's password. When a blob is uploaded, the ciphertext and HMAC of the plain text are both uploaded.