One thing Alice and Bob could do to make sure they exchange genuine public keys is to meet face-to-face (assuming neither has been coerced into deceiving while face-to-face) and tell each other their public keys. Or Alice and Bob might have a previous secure channel already established (but if so, why would they need our protocol?). However, face-to-face meetings are likely to be inconvenient. Fortunately, Alice and Bob have another option. They can rely on a trusted intermediary, Trent. In real-life transactions, notary publics, banks, escrow lawyers, police, and others play this kind of role. For our protocol, we need some sort of "authenticatable" contact with Trent, as well (and, of course, we need to trust Trent). In "public-key infrastructure" lingo, Trent is known as a "key certifying authority."

Trent has a face-to-face meeting with Alice, and exchanges PUB_A and PUB_T. Trent also has a similar meeting with Bob. In order to reliably obtain Bob's public key, Alice encrypts (but need not sign) the following message with PUB_T: "Hi Trent, what is Bob's public key?" Trent responds with a message signed with PRIV_T: "Bob's public key is PUB_B." In fact, Trent probably will not send this message to Alice personally, but will make it public knowledge via Trent's Web site, newspaper, etc. Mallory can easily get PUB_B this way, but that is fine -- he is welcome to have PUB_B. Since Trent's message is signed with PRIV_T, anyone can determine that the message really comes from Trent (assuming everyone knows they have a genuine copy of PUB_T, hence the face-to-face meetings with Trent).

Protocols like PGP actually distribute Trent's role through a "web of trust" rather than with a hierarchical authority. With a web of trust you can find that a lot of people whom you trust at least a little bit have vouched for Bob's public key. If you have had face-to-face (or other secure) contact with any of these vouchers, you can trust PUB_B.