Cryptosystemen die gebruik maken van asymmetrische sleutelalgoritmen omzeilen het probleem evenmin. Dat een openbare sleutel door iedereen kan worden gekend zonder de veiligheid van een versleutelingsalgoritme in gevaar te brengen (voor sommige van dergelijke algoritmen, maar niet voor alle) is zeker nuttig, maar voorkomt bepaalde soorten aanvallen niet. Zo is een “spoofing”-aanval, waarbij de openbare sleutel A openbaar wordt gemaakt als die van gebruiker Alice, maar in feite een openbare sleutel is van de “man-in-the-middle”-aanvaller Mallet, gemakkelijk mogelijk. Geen enkele publieke sleutel is inherent gebonden aan een bepaalde gebruiker, en iedere gebruiker die vertrouwt op een gebrekkige binding (inclusief Alice zelf wanneer zij zichzelf beschermde berichten stuurt) zal problemen ondervinden.
De meest gebruikelijke oplossing voor dit probleem is het gebruik van publieke sleutelcertificaten en certificaatautoriteiten (CA’s) voor hen in een publieke-sleutelinfrastructuur (PKI) systeem. De certificaatautoriteit (CA) fungeert als een “trusted third party” voor de communicerende gebruikers en verklaart met behulp van cryptografische bindingsmethoden (bijv. digitale handtekeningen) aan beide betrokken partijen dat de openbare sleutels die elk bezit en die zogenaamd aan de ander toebehoren, dat ook werkelijk zijn. Een digitale notarisdienst, zo men wil. Dergelijke CA’s kunnen particuliere organisaties zijn die dergelijke garanties verstrekken, of overheidsinstanties, of een combinatie van beide. In belangrijke zin verplaatst dit echter het probleem van sleutelauthenticatie slechts één niveau terug, want elke CA kan te goeder trouw een certificatie van een sleutel afgeven, maar zich door een fout of kwaadwilligheid vergissen. Vertrouwen op een gebrekkig sleutelcertificaat dat een openbare sleutel “authentiek” verklaart, zal problemen veroorzaken. Als gevolg hiervan vinden veel mensen alle PKI-ontwerpen onaanvaardbaar onveilig.
Aan methoden voor sleutelauthenticatie wordt actief onderzoek gedaan.