Comparing different hashes to confirm they came from the same string Is there any safe hashing algorithm that returns a different hash each time (like bcrypt) but has the possibility to compare 2 different hashes and determine that they were hashed from the same password/string without knowing this password/string?
Here's a thought; we work in a pairing-friendly elliptic curve where the discrete log problem is hard, and we generate a 'hash' of a value $p$ [1] by selecting a random value $r$, and outputting the two points $(rG, rpG)$.

Then, given two such hashes $(rG, rpG)$ and $(r'G, r'p'G)$, we can check if they are hashes of the same password by computing the two pairing operations $e(rG, r'p'G)$ and $e(r'G, rpG)$.  If $p = p'$, then both values will be the same, namely the value $e(G, G)^{rr'p}$.

Reversing the hash, that is, given $(rG, rpG)$, recover $p$, is a discrete log problem, this is assumed to be hard.

And, given a long list of hash passwords $(rG, rpG), (r'G, r'p'G), (r''G, r''p''G), ...$, there doesn't appear to be any obvious way to compare all of then against an attacker chosen password with less than $O(n)$ pairing operations or point multiplications.

The attacker can test a single hash $(rG, rpG)$ against a test password $p'$ by checking if $p'(rG) = rpG$; however with any such primitive where there is a primitive to compare hashes, the attacker could perform this test by hashing the password $p'$ and using the comparison primitive to see if that hash matches the one under test, and so this is not a vulnerability.



[1] The value $p$ might be a conventional hash of the actual password; that detail isn't important for this idea.