Multi-user deduplication also leaks information via timing attacks (user2 can upload a million key files to see if user1 already stored one).

It's better to only deduplicate on a per-user basis.