Les systèmes de cryptage utilisant des algorithmes à clé asymétrique n’échappent pas non plus au problème. Qu’une clé publique puisse être connue de tous sans compromettre la sécurité d’un algorithme de chiffrement (pour certains de ces algorithmes, mais pas pour tous) est certes utile, mais n’empêche pas certains types d’attaques. Par exemple, une attaque par usurpation dans laquelle la clé publique A est présentée publiquement comme étant celle de l’utilisateur Alice, mais qui est en fait une clé publique appartenant à l’attaquant man-in-the-middle Mallet, est facilement possible. Aucune clé publique n’est intrinsèquement liée à un utilisateur particulier, et tout utilisateur s’appuyant sur une liaison défectueuse (y compris Alice elle-même lorsqu’elle s’envoie des messages protégés) aura des problèmes.
La solution la plus courante à ce problème est l’utilisation de certificats de clé publique et d’autorités de certification (CA) pour ceux-ci dans un système d’infrastructure à clé publique (PKI). L’autorité de certification (CA) agit en tant que « tiers de confiance » pour les utilisateurs qui communiquent et, à l’aide de méthodes de liaison cryptographique (par exemple, les signatures numériques), représente pour les deux parties concernées que les clés publiques que chacun détient et qui appartiennent prétendument à l’autre, le font réellement. Un service de notaire numérique, en quelque sorte. Ces AC peuvent être des organisations privées fournissant de telles garanties, des agences gouvernementales ou une combinaison des deux. Toutefois, dans un sens important, cela ne fait que déplacer le problème de l’authentification des clés d’un niveau, car toute autorité de certification peut certifier de bonne foi une clé mais, par erreur ou par malveillance, se tromper. Toute confiance dans un certificat de clé défectueux « authentifiant » une clé publique posera des problèmes. En conséquence, de nombreuses personnes trouvent que toutes les conceptions d’ICP sont inacceptablement peu sûres.
En effet, les méthodes d’authentification des clés font l’objet de recherches actives.