Comment by frereit

Well, the nonce is (usually) public information. It is shared along with the ciphertext, so that the other party can use the same nonce to validate and decrypt the ciphertext. So it is trivial to detect which two messages share a nonce, if any do.