Aszimmetrikus kulcsú algoritmusokat használó kriptorendszerek sem kerülik meg a problémát. Az, hogy egy nyilvános kulcsot mindenki ismerhet anélkül, hogy a titkosítási algoritmus biztonságát veszélyeztetné (néhány ilyen algoritmus esetében, bár nem mindegyiknél), természetesen hasznos, de nem akadályozza meg a támadások bizonyos fajtáit. Könnyen lehetséges például egy olyan hamisító támadás, amelyben az A nyilvános kulcsról nyilvánosan azt állítják, hogy az Alice felhasználóé, de valójában a közbeavatkozó támadó Mallet nyilvános kulcsa. Egyetlen nyilvános kulcs sincs eredendően egy adott felhasználóhoz kötve, és minden olyan felhasználó, aki hibás kötésre támaszkodik (beleértve magát Alice-t is, amikor védett üzeneteket küld magának), bajba kerül.
A probléma legelterjedtebb megoldása a nyilvános kulcsú tanúsítványok és a hozzájuk tartozó tanúsítványhivatalok (CA-k) használata egy nyilvános kulcsú infrastruktúra (PKI) rendszerben. A tanúsító hatóság (CA) “megbízható harmadik félként” működik a kommunikáló felhasználók számára, és kriptográfiai kötési módszerek (pl. digitális aláírások) segítségével mindkét érintett fél számára azt képviseli, hogy az egyes felek birtokában lévő nyilvános kulcsok, amelyek állítólag a másikéi, valóban azok. Ha úgy tetszik, digitális közjegyzői szolgáltatás. Az ilyen hitelesítésszolgáltatók lehetnek ilyen biztosítékokat nyújtó magánszervezetek, kormányzati szervek vagy a kettő valamilyen kombinációja. Jelentős értelemben azonban ez csak egy szinttel hátrébb helyezi a kulcshitelesítés problémáját, mivel bármelyik hitelesítésszolgáltató jóhiszeműen tanúsíthat valamilyen kulcsot, de tévedés vagy rosszhiszeműség miatt tévedhet. A nyilvános kulcsot “hitelesítő”, hibás kulcstanúsítványra való hagyatkozás problémákat fog okozni. Ennek eredményeként sokan minden PKI-konstrukciót elfogadhatatlanul bizonytalannak tartanak.
A kulcshitelesítési módszereket aktívan kutatják.