Auch Verschlüsselungssysteme, die asymmetrische Schlüsselalgorithmen verwenden, entgehen dem Problem nicht. Die Tatsache, dass ein öffentlicher Schlüssel allen bekannt sein kann, ohne die Sicherheit eines Verschlüsselungsalgorithmus zu beeinträchtigen (für einige solcher Algorithmen, wenn auch nicht für alle), ist sicherlich nützlich, verhindert aber nicht einige Arten von Angriffen. So ist beispielsweise ein Spoofing-Angriff, bei dem der öffentliche Schlüssel A als der des Benutzers Alice ausgegeben wird, in Wirklichkeit aber ein öffentlicher Schlüssel ist, der dem Man-in-the-Middle-Angreifer Mallet gehört, leicht möglich. Kein öffentlicher Schlüssel ist von Natur aus an einen bestimmten Benutzer gebunden, und jeder Benutzer, der sich auf eine fehlerhafte Bindung verlässt (einschließlich Alice selbst, wenn sie sich selbst geschützte Nachrichten sendet), wird Probleme bekommen.
Die gebräuchlichste Lösung für dieses Problem ist die Verwendung von Zertifikaten für öffentliche Schlüssel und Zertifizierungsstellen (CAs) für diese in einem Public-Key-Infrastruktur-System (PKI). Die Zertifizierungsstelle (CA) fungiert als „vertrauenswürdige dritte Partei“ für die kommunizierenden Benutzer und stellt mit Hilfe von kryptographischen Bindungsmethoden (z. B. digitalen Signaturen) für beide beteiligten Parteien sicher, dass die öffentlichen Schlüssel, die jeder besitzt und die angeblich dem anderen gehören, dies auch tatsächlich tun. Ein digitaler Notardienst, wenn Sie so wollen. Bei solchen Zertifizierungsstellen kann es sich um private Organisationen handeln, die solche Zusicherungen geben, oder um staatliche Stellen oder eine Kombination aus beidem. Dies verschiebt das Problem der Schlüsselauthentifizierung jedoch lediglich um eine Stufe nach hinten, denn jede CA kann in gutem Glauben einen Schlüssel zertifizieren, sich aber durch einen Irrtum oder böswillig irren. Jedes Vertrauen auf ein fehlerhaftes Schlüsselzertifikat, das einen öffentlichen Schlüssel „authentifiziert“, führt zu Problemen. Infolgedessen halten viele Menschen alle PKI-Konzepte für inakzeptabel unsicher.
Dementsprechend wird aktiv an Methoden zur Schlüsselauthentifizierung geforscht.