Krypteringssystemer, der anvender asymmetriske nøglealgoritmer, undgår heller ikke problemet. At en offentlig nøgle kan være kendt af alle uden at kompromittere sikkerheden i en krypteringsalgoritme (for nogle af disse algoritmer, men ikke for alle) er bestemt nyttigt, men forhindrer ikke visse former for angreb. F.eks. er et spoofing-angreb, hvor den offentlige nøgle A påstås offentligt at tilhøre brugeren Alice, men i virkeligheden er en offentlig nøgle tilhørende man-in-the-middle-angriberen Mallet, let muligt. Ingen offentlig nøgle er i sagens natur bundet til en bestemt bruger, og enhver bruger, der stoler på en mangelfuld binding (herunder Alice selv, når hun sender sig selv beskyttede meddelelser), vil få problemer.
Den mest almindelige løsning på dette problem er brugen af certifikater for offentlige nøgler og certifikatmyndigheder (CA’er) for dem i et PKI-system (Public Key Infrastructure). Certifikatmyndigheden (CA) fungerer som en “betroet tredjepart” for de kommunikerende brugere og repræsenterer ved hjælp af kryptografiske bindingsmetoder (f.eks. digitale signaturer) over for begge involverede parter, at de offentlige nøgler, som de hver især er i besiddelse af, og som angiveligt tilhører den anden part, rent faktisk også gør det. En digital notartjeneste, om man vil. Sådanne CA’er kan være private organisationer, der giver sådanne garantier, eller offentlige myndigheder, eller en kombination af de to. I en væsentlig forstand flytter dette dog blot problemet med nøgleautentificering et niveau tilbage, for enhver CA kan i god tro certificere en nøgle, men kan ved fejl eller ond vilje tage fejl. Enhver tillid til et mangelfuldt nøglecertifikat, der “autentificerer” en offentlig nøgle, vil skabe problemer. Som følge heraf finder mange mennesker alle PKI-designs uacceptabelt usikre.
Der forskes aktivt i metoder til nøgleautentificering.