公開鍵基盤
1976年にディフィー(Whitfield Diffie)、ヘルマン(Martin Hellman)の両名によって発表された安全な鍵交換の仕組みであるDiffie-Hellman(DH)、そして1978年にロナルド・リベスト(Ron Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Leonard Adleman)の3名によって発表された非対称鍵アルゴリズムであるRSAは、安全な通信について劇的な変化をもたらした。高速デジタル通信(インターネットやその前身)の更なる発展により、利用者がお互いに安全に通信できる方法や、更に利用者が実際に対話していた人を確認できる方法の必要性が明白になった。利用者の同一性を公開鍵に結び付ける、暗号的に保護された証明書のアイデアが精力的に研究された。
初期の暗号技術の中から効果的な使い方ができる組み合わせが発明および分析された。World Wide Web(WWW)の発明とその急速な普及と共に、認証(authentication)と安全な通信の必要性が更に深刻となった。(電子商取引や、Webブラウザから商用データベースへのオンラインアクセスなど)商用の理由だけで十分だった。
ネットスケープコミュニケーションズ(Netscape Communications Corporation)のテヘール・エルガメル(Taher ElGamal)たちは、鍵の立証やサーバ認証(v3より前は片方向のみ)などを含む、Secure Sockets Layer(SSL)プロトコル(httpsプロトコル)を開発した。このようにPKIの構造はWebの利用者/サイトが望む(あるいはそれ以上の)安全な通信のために造られた
ベンダーや起業家が広大な市場の可能性を予測し、新しい会社や企業内プロジェクトを始め、責任からの保護と法的な承認について議論され始めた。米国弁護士協会(American Bar Association、ABA)のテクノロジ・プロジェクトはPKI運用に関して予測し得る法的な側面について広範囲に渡る分析を発表し(ABA digital signature guidelines(英語版) 参照)、その後間もなくして、(1995年の米国ユタ州を皮切りに)世界中のあらゆる国や自治体が、法律の制定および規則の採択をし始めた。消費者団体などは、プライバシー、アクセス、責任について、幾つかの地域では更に考慮するべきであるという問題を挙げた。
公開鍵証明書には有効期限が定まっており、この有効期限を超えた期限切れの証明書は無効になってしまう。
そこでPKIの利用者は証明書の期限が切れる前に新しい鍵ペアを生成し、新しい鍵ペアに対する証明書を発行してもらう必要がある。この作業を証明書の更新という。
更新時には古い鍵ペアを使って認証局から認証を受ける事ができるので、新しい証明書の発行の際にはネットワーク越しに更新手続きを行うことができる。
更新手続きを行ってから古い証明書が有効期限切れになるまでの間は、新旧両方の証明書がある事になる。この新旧の証明書を関連付けるため、リンク証明書という証明書を認証局から発行してもらう。リンク証明書にはNewWithOld、OldWithNewなどの証明書がある。NewWithOldは古い鍵ペアを使って作成した新しい公開鍵に対する証明書で、OldWithNewは逆に新しい鍵ペアを使って作成した古い公開鍵に対する証明書である。
利用者Aの古い公開鍵とその証明書(OldWithOld証明書という)をすでに所有している(Aとは別の)利用者Bは、利用者Aの新しい公開鍵とともにNewWithOld証明書を受け取る事で新しい公開鍵の真正性を確認できる。これにより利用者Bは利用者Aが新しい鍵ペアで署名した署名文の正当性を検証する事ができる。
逆に利用者Aの新しい公開鍵とその証明書(NewWithNew証明書という)をすでに所有している(Aとは別の)利用者Cは、利用者Aの古い公開鍵とともにOldWithNew証明書を受け取る事で古い公開鍵の真正性を確認できる。これにより利用者Cは利用者Aが古い鍵ペアで署名した署名文の正当性を検証する事ができる。