Napkin-cryptographic way how Dropbox could fix this while still getting full deduplication: currently, when the client discovers that a file has been added locally, it sends hashes of 4MB blocks, and the server considers the file added.
Additional measure at that point: the server could challenge the client to provide the values of bytes at a couple of arbitrarily chosen byte offsets of the original file. (Could precompute that, provided the queries don't repeat often).
Additional measure at that point: the server could challenge the client to provide the values of bytes at a couple of arbitrarily chosen byte offsets of the original file. (Could precompute that, provided the queries don't repeat often).