Problému se nevyhnou ani šifrovací systémy využívající algoritmy asymetrických klíčů. To, že veřejný klíč mohou znát všichni, aniž by byla ohrožena bezpečnost šifrovacího algoritmu (pro některé takové algoritmy, i když ne pro všechny), je jistě užitečné, ale některým druhům útoků to nezabrání. Například je snadno možný podvržený útok, při kterém je veřejně prohlášen veřejný klíč A za klíč uživatele Alice, ale ve skutečnosti se jedná o veřejný klíč patřící útočníkovi Malletovi. Žádný veřejný klíč není ze své podstaty vázán na konkrétního uživatele a každý uživatel, který se spoléhá na vadnou vazbu (včetně samotné Alice, když si posílá chráněné zprávy), bude mít problémy.
Nejběžnějším řešením tohoto problému je použití certifikátů veřejných klíčů a certifikačních autorit pro ně v systému infrastruktury veřejných klíčů (PKI). Certifikační autorita (CA) funguje jako „důvěryhodná třetí strana“ pro komunikující uživatele a pomocí kryptografických vazebních metod (např. digitálních podpisů) oběma zúčastněným stranám reprezentuje, že veřejné klíče, které každá z nich drží a které údajně patří druhé straně, tomu tak skutečně je. Digitální notářská služba, chcete-li. Takovými certifikačními autoritami mohou být soukromé organizace poskytující takováto ujištění nebo vládní agentury, případně nějaká kombinace obojího. V podstatném smyslu to však pouze posouvá problém ověřování klíčů o jednu úroveň zpět, protože každá certifikační autorita může v dobré víře provést certifikaci nějakého klíče, ale v důsledku chyby nebo zlého úmyslu se zmýlí. Jakékoli spoléhání se na chybný certifikát klíče, který „ověřuje“ veřejný klíč, způsobí problémy. V důsledku toho mnoho lidí považuje všechny návrhy PKI za nepřijatelně nezabezpečené.
V souladu s tím se aktivně zkoumají metody ověřování klíčů.
.