Systemy kryptograficzne wykorzystujące algorytmy klucza asymetrycznego również nie unikają tego problemu. To, że klucz publiczny może być znany przez wszystkich bez naruszania bezpieczeństwa algorytmu szyfrującego (dla niektórych takich algorytmów, choć nie dla wszystkich) jest z pewnością użyteczne, ale nie zapobiega niektórym rodzajom ataków. Na przykład, łatwo możliwy jest atak typu spoofing, w którym klucz publiczny A jest podawany publicznie jako klucz użytkownika Alice, ale w rzeczywistości jest kluczem publicznym należącym do atakującego man-in-the-middle Malleta. Żaden klucz publiczny nie jest nierozerwalnie związany z konkretnym użytkownikiem, a każdy użytkownik polegający na wadliwym powiązaniu (w tym sama Alicja, gdy wysyła sobie chronione wiadomości) będzie miał kłopoty.
Najczęstszym rozwiązaniem tego problemu jest użycie certyfikatów klucza publicznego i urzędów certyfikacji (CA) dla nich w systemie infrastruktury klucza publicznego (PKI). Urząd certyfikacji (CA) działa jako „zaufana trzecia strona” dla komunikujących się użytkowników i używając kryptograficznych metod wiązania (np. podpisów cyfrowych) przedstawia obu zaangażowanym stronom, że klucze publiczne, które każda z nich posiada i które rzekomo należą do drugiej strony, rzeczywiście tak jest. Cyfrowa usługa notarialna, jeśli można tak powiedzieć. Takie CA mogą być prywatnymi organizacjami dostarczającymi takich zapewnień, lub agencjami rządowymi, lub jakąś kombinacją tych dwóch. Jednakże, w istotnym sensie, to tylko przesuwa problem uwierzytelniania kluczy o jeden poziom wstecz, ponieważ każdy CA może w dobrej wierze poświadczyć jakiś klucz, ale przez błąd lub złośliwość, może się pomylić. Każde poleganie na wadliwym certyfikacie klucza „uwierzytelniającym” klucz publiczny spowoduje problemy. W rezultacie wiele osób uważa, że wszystkie projekty PKI są niedopuszczalnie mało bezpieczne.
Zgodnie z tym, metody uwierzytelniania kluczy są aktywnie badane.
.