Perhaps, a much simpler possibility than the other proposed in this thread, is that, in addition to uploading the encrypted file, the service uploads hashes of chunks of plaintext data. That way the service can just compares hashes of data, just like a regular dedup implementation.