Kryptosystem som använder asymmetriska nyckelalgoritmer undviker inte heller problemet. Att en offentlig nyckel kan vara känd av alla utan att säkerheten för en krypteringsalgoritm äventyras (för vissa sådana algoritmer, men inte för alla) är förvisso användbart, men förhindrar inte vissa typer av attacker. Det är till exempel lätt att genomföra en spoofing-attack där den offentliga nyckeln A påstås vara användarens Alice, men i själva verket är en offentlig nyckel som tillhör angriparen Mallet, som är en man-in-the-middle-angripare. Ingen offentlig nyckel är av naturliga skäl bunden till en viss användare, och alla användare som förlitar sig på en bristfällig bindning (inklusive Alice själv när hon skickar skyddade meddelanden till sig själv) kommer att få problem.
Den vanligaste lösningen på detta problem är användningen av certifikat för offentliga nycklar och certifikatutfärdare (CAs) för dem i ett PKI-system (Public Key Infrastructure). Certifikatmyndigheten (CA) fungerar som en ”betrodd tredje part” för de kommunicerande användarna och representerar med hjälp av kryptografiska bindningsmetoder (t.ex. digitala signaturer) för båda inblandade parter att de offentliga nycklar som var och en av dem innehar och som påstås tillhöra den andra verkligen gör det. En digital notarietjänst, om man så vill. Sådana certifikatutfärdare kan vara privata organisationer som tillhandahåller sådana garantier, eller statliga organ, eller någon kombination av de två. På ett väsentligt sätt flyttar detta dock bara problemet med nyckelautentisering en nivå bakåt, eftersom alla certifikatutfärdare kan utfärda en certifiering av en nyckel i god tro men genom fel eller illvilja ta fel. Varje förlitande på att ett felaktigt nyckelcertifikat ”autentiserar” en offentlig nyckel kommer att skapa problem. Därför anser många människor att alla PKI-konstruktioner är oacceptabelt osäkra.
Det forskas aktivt om metoder för nyckelautentisering.