The simplest solution for this kind of problem is for the two concerned users to communicate and exchange keys.
[1] Crypto systems using asymmetric key algorithms do not evade the problem either.
The certificate authority (CA) acts as a 'trusted third party' for the communicating users and, using cryptographic binding methods (e.g., digital signatures) represents to both parties involved that the public keys each holds which allegedly belong to the other, actually do so.
Such CAs can be private organizations providing such assurances, or government agencies, or some combination of the two.
As a result, many people find all PKI designs unacceptably insecure.