Los sistemas de cifrado que utilizan algoritmos de clave asimétrica tampoco evitan el problema. El hecho de que una clave pública pueda ser conocida por todos sin comprometer la seguridad de un algoritmo de cifrado (para algunos de estos algoritmos, aunque no para todos) es ciertamente útil, pero no evita algunos tipos de ataques. Por ejemplo, un ataque de suplantación de identidad en el que se afirma públicamente que la clave pública A es la del usuario Alice, pero en realidad es una clave pública perteneciente al atacante «hombre en el medio» Mallet, es fácilmente posible. Ninguna clave pública está intrínsecamente vinculada a ningún usuario en particular, y cualquier usuario que confíe en una vinculación defectuosa (incluida la propia Alice cuando se envía a sí misma mensajes protegidos) tendrá problemas.
La solución más común a este problema es el uso de certificados de clave pública y autoridades de certificación (CA) para ellos en un sistema de infraestructura de clave pública (PKI). La autoridad de certificación (CA) actúa como una «tercera parte de confianza» para los usuarios que se comunican y, utilizando métodos de vinculación criptográfica (por ejemplo, firmas digitales) representa para ambas partes implicadas que las claves públicas que cada una posee y que supuestamente pertenecen a la otra, realmente lo hacen. Un servicio de notario digital, por así decirlo. Dichas CAs pueden ser organizaciones privadas que ofrezcan tales garantías, o agencias gubernamentales, o alguna combinación de ambas. Sin embargo, en un sentido significativo, esto simplemente hace retroceder el problema de la autenticación de claves un nivel, ya que cualquier CA puede hacer una certificación de buena fe de alguna clave pero, por error o malicia, estar equivocada. Cualquier confianza en un certificado de clave defectuoso que «autentifique» una clave pública causará problemas. Como resultado, muchas personas consideran que todos los diseños de PKI son inaceptablemente inseguros.
En consecuencia, se están investigando activamente métodos de autenticación de claves.