Yeah, I had a similar intuition about that approach possibly being weak or problematic. However, if my cursory reading of the algorithm is at all correct, the goal may simply be to consistently choose another hash value (a different min hash) and it may work fine. In other words, the same hash values would be considered the minimum after XORing with a random number and they will be different from the initial hash that was selected as the minimum without XORing. Those are the behaviors that matter and not so much that the hashes that result from the XORing are cryptographically secure.

Can't edit the post. I meant to say "the same two hash values."

MinHash is a CPU hog due to precisely this step -- cheap rehashes are the order of the day.

I don't think xor works, but simple arithmetic, IIRC h_i(key) = i*h(key) + C mod 2^32, is viable and SIMD-friendly. Look up minwise-independent hash functions.