Collusion attacks described above cannot be prevented other than by a culture of honest behaviour. They have minimal returns, the fake accounts gained is percentageColluding^2 and scale with an inverse square law, and the protocol considers them to be allowed and an unavoidable (and minimal) cost. Man in the middle attacks on the other hand, are entirely defendable. There are different ways to defend against that attack, I will here describe the one I think works best for the protocol.
Man in the middle attacks are well known in communication systems such as key exchange protocols. One approach to defend against them is by using a third party to authenticate the channel. The defense protocol I prefer for Pseudonym Pairs relies on a form of third party authentication, but in contrast to a certificate authority in key exchange protocol, the third party here is another person within the Pseudonym Pairs population.
The pair agrees on a third party authenticator, and they do so in