Epäsymmetrisiä avainalgoritmeja käyttävät kryptojärjestelmät eivät myöskään välttele ongelmaa. Se, että julkinen avain voi olla kaikkien tiedossa vaarantamatta salausalgoritmin turvallisuutta (joidenkin tällaisten algoritmien osalta, joskaan ei kaikkien), on varmasti hyödyllistä, mutta ei estä tietynlaisia hyökkäyksiä. Esimerkiksi väärennöshyökkäys, jossa julkinen avain A väitetään julkisesti käyttäjän Alice:n avaimeksi, mutta todellisuudessa se on julkinen avain, joka kuuluu väliinputoajahyökkääjä Malletille, on helposti mahdollinen. Mikään julkinen avain ei ole luonnostaan sidottu mihinkään tiettyyn käyttäjään, ja kaikki käyttäjät, jotka luottavat virheelliseen sidontaan (mukaan lukien Alice itse, kun hän lähettää itselleen suojattuja viestejä), joutuvat vaikeuksiin.
Yleisin ratkaisu tähän ongelmaan on julkisten avainten varmenteiden ja varmenteiden myöntäjien (CA) käyttö julkisen avaimen infrastruktuurijärjestelmässä (PKI). Varmenneviranomainen (CA) toimii ”luotettuna kolmantena osapuolena” kommunikoiville käyttäjille ja edustaa kryptografisia sidontamenetelmiä (esim. digitaalisia allekirjoituksia) käyttäen molemmille osapuolille, että kummankin hallussa olevat julkiset avaimet, joiden väitetään kuuluvan toiselle osapuolelle, todella kuuluvat. Kyseessä on ikään kuin digitaalinen notaaripalvelu. Tällaiset varmentajat voivat olla yksityisiä organisaatioita, jotka tarjoavat tällaisia vakuutuksia, tai valtion virastoja tai jokin näiden kahden yhdistelmä. Merkittävässä mielessä tämä kuitenkin vain siirtää avainten todentamisongelmaa yhden tason taaksepäin, sillä mikä tahansa varmentaja voi vilpittömässä mielessä varmentaa jonkin avaimen, mutta erehtyä virheestä tai pahantahtoisuudesta johtuen. Kaikki luottamus siihen, että virheellinen avaintodistus ”todentaa” julkisen avaimen, aiheuttaa ongelmia. Tämän vuoksi monet ihmiset pitävät kaikkia PKI-malleja sietämättömän turvattomina.
Kaikki avainten todentamismenetelmiä tutkitaan aktiivisesti.