[tialaramex]

Two humans who know each other can use the Socialist Millionaire's Protocol, this does some fancy mathematics to prove they were both thinking of the same number (for Bill and Ted this would be "69, dude") and of course we can encode any answer e.g. "Sarah", "Washington", "Lakers Game Six" as a large number trivially. The SMP would be weak if you could iterate it many times, but it's for humans, after "Ted" guesses 4, 19, and 22, Bill will stop asking and assume it's not Ted at the far end.

A machine can obtain Certificates from a CA which show the CA validated its identity, and use Public Key Cryptography to prove this is its certificate. This is how HTTPS works when you connect to a remote web site, but it can be mutually authenticated too, that's just not how web browsers use it.