Sistemas de criptografia usando algoritmos de chaves assimétricas também não evitam o problema. Que uma chave pública pode ser conhecida por todos sem comprometer a segurança de um algoritmo de criptografia (para alguns desses algoritmos, embora não para todos) é certamente útil, mas não impede alguns tipos de ataques. Por exemplo, um ataque de spoofing no qual a chave pública A é alegada publicamente como sendo a do usuário Alice, mas na verdade é uma chave pública pertencente ao homem no meio do atacante Mallet, é facilmente possível. Nenhuma chave pública está inerentemente ligada a qualquer utilizador em particular, e qualquer utilizador que confie numa ligação defeituosa (incluindo a própria Alice quando envia mensagens protegidas) terá problemas.
A solução mais comum para este problema é o uso de certificados de chave pública e autoridades de certificados (CAs) para eles num sistema de infra-estrutura de chave pública (PKI). A autoridade certificadora (AC) age como uma ‘terceira parte confiável’ para os usuários comunicantes e, utilizando métodos de encadernação criptográfica (por exemplo, assinaturas digitais) representa para ambas as partes envolvidas que as chaves públicas que cada uma possui e que supostamente pertencem à outra, na verdade o fazem. Um serviço de notário digital, se preferir. Tais ACs podem ser organizações privadas que fornecem tais garantias, ou agências governamentais, ou alguma combinação das duas. No entanto, num sentido significativo, isto apenas faz recuar o problema da autenticação da chave um nível para qualquer AC pode fazer uma certificação de boa fé de alguma chave mas, através de erro ou malícia, estar enganado. Qualquer confiança em um certificado de chave defeituoso ‘autenticando’ uma chave pública irá causar problemas. Como resultado, muitas pessoas acham todos os designs de PKI inaceitavelmente inseguros.
De acordo, métodos de autenticação de chave estão sendo ativamente pesquisados.