I believe if you could verify two separately encrypted files were the same it would defeat the purpose of encryption completely. By definition a secure encryption system cannot allow this.
The keyword is "convergent" encryption. We used something like this at Iron Mountain Digital many years ago (they still do, AFAIK), and it is used in BitCasa today.
You should read the papers, but essentially the concept can be boiled down to encrypting the plaintext with a hash of the plaintext.
Since there is no way to derive the hash of a plaintext from an encrypted block, there is no way to hack the key other than regular old brute force. But if the same data is uploaded twice, the same hash is computed, and thus the same encryption is used, and thus the encrypted cipher text is identical.
The encryption keys can be stored separately from the cipher text. In particular, the user who uploaded the data would store the hashes (this would already happen in most backup applications anyway). Then, for retrieval, they give the hash and the block location to the server, who is now able to decrypt it. By stealing the server, you gain zero access to plaintext data.
Very cool stuff :)
But your 'random salt' idea suffers from the attacker just generating all possible encryptions of the plaintext due to the small number possibilities. The "convergence key" is solely a security-parameter-length key that you can pass around to your friends so that your files will dedupe with theirs while not being susceptible to confirmation attacks by others.
I understand is possible to do operations on encrypted data (which results in an encrypted result) all without having the key to the data (or the result), and maybe there's a way to do this to allow the duplication.
If there is it could (but shouldn't ?) be used.
The issue here, to me at least, is that someone malicious that has exactly the same data could encrypt it and then verify the above.
It's also highly experimental at this point, from what I remember.
[1] As a trivial example, let's say you give me a very large number, and your encryption scheme is to add some number, n, of zero bits at the end. Only you know how many bits you're adding - n is your private key. Regardless of what you pick for n, I can multiply your number by 2 (i.e. bit-shift it) and give the result back to you, which you would then be able to decrypt to the result of the calculation.
This works for any value of n, so I can't tell if two original numbers are the same by inspecting the ciphertexts.