New Directions in Cryptography ── 鍵を配らずに秘密を共有する

1976年11月、 IEEE Transactions on Information Theory 誌 IT-22巻6号の644–654頁に、 Whitfield Diffie と Martin Hellman の招待論文 "New Directions in Cryptography" が載った。 冒頭の一文は、 論文の書き出しとしては異例なほど直截である ── "We stand today on the brink of a revolution in cryptography."（我々は今日、 暗号における革命の瀬戸際に立っている）。

論文が受理されたのは1976年6月3日。 内容の一部はそれ以前に、 1975年6月のマサチューセッツ州レノックスでの IEEE Information Theory Workshop と、 1976年6月のスウェーデン・ロンネビーでの IEEE International Symposium on Information Theory で発表されている。

何を解こうとしたのか

論文が名指しした問題は2つである。

鍵配送。 それまでの暗号は、 送り手と受け手が同じ鍵を持っていることを前提としていた。 だから通信の前に、 手渡し・書留・信頼できる運び屋といった安全な別経路で鍵を届けなければならない。 商取引の相手は初対面のこともある。 通信網が世界規模になったとき、 この前提はそのまま費用と遅延になる。

認証。 紙の契約は署名で成立する。 署名は、 受け取った側が第三者（裁判所）に示せるという性質を持つ。 電子的な取引を紙の置き換えにするなら、 これに相当するものが要る。

解いたのは鍵配送、 残したのは暗号系

ここが最も取り違えられる。

そして示さなかったもの ── 動く公開鍵暗号系そのものである。 論文は公開鍵暗号系を作るための技法をいくつか示唆するが、 問題は依然として大きく未解決である、 と自ら書いている。 実際に動く公開鍵暗号系は、 翌1977年に MIT の Ronald Rivest・Adi Shamir・Leonard Adleman が技術メモとして出し、 1978年2月に Communications of the ACM 21巻2号120–126頁に載せた RSA である。

言い換えると、 1976年の論文で解決したのは鍵配送のほうであって、 暗号化と署名は設計目標として定式化されたにとどまる。 公開鍵暗号 という言葉が指すものの半分は、 この論文の外で完成した。

Ralph Merkle という先行者

論文の参考文献 [1] は、 Ralph Merkle の "Secure communication over an insecure channel" を「CACM に投稿中」として挙げている。 バークレーの学生だった Merkle は、 のちに「Merkle のパズル」と呼ばれる方式を1974年に着想していた ── 攻撃者の計算量が正規利用者の計算量の2乗で増える鍵合意である。 Diffie–Hellman 論文は、 Merkle の方式を「公開鍵配送方式（public key distribution system）」と呼んで区別し、 その帯域の重さを具体的に検討したうえで、 自分たちの方式を提示している。 Merkle の論文が実際に印刷されたのは1978年4月、 CACM 21巻4号294–299頁 ── Diffie–Hellman より1年半あとだった。

ACM のチューリング賞記録によれば、 Diffie は Merkle を公開鍵の物語で最も発明的な人物とみなし、 Hellman は後年、 功績は Diffie–Hellman–Merkle と呼ばれるべきだと主張している。 実際、 IEEE の Kobayashi 賞（1999年）と Hamming メダル（2010年）は3人が共同で受けた。 2015年の ACM チューリング賞は Diffie と Hellman の2人である。 受賞理由は、 デジタル署名への応用を含む非対称公開鍵暗号と、 実用的な鍵交換方式の両方を発明し普及させたこと。

すでに英国政府は知っていた

1997年12月16日、 英国の CESG（GCHQ の情報保証部門）が、 James Ellis が1987年に書いた内部文書 "The Story of Non-Secret Encryption" を公開した。 Ellis はその3週間前に死去している。 文書が明かした年表は次のとおり。

• 1970年1月 ── Ellis, "The Possibility of Secure Non-Secret Digital Encryption"。 鍵を事前に共有せずに秘密通信ができるという存在証明
• 1973年11月20日 ── Clifford Cocks, "A Note on Non-Secret Encryption"。 Ellis 自身が「本質的に RSA アルゴリズムである」と記す
• 1974年1月21日 ── Malcolm Williamson, "Non-Secret Encryption Using a Finite Field"。 冪乗の可換性を使う3パス方式
• 1976年8月10日 ── Williamson, "Thoughts on Cheaper Non-Secret Encryption"。 Ellis によれば Williamson は「思いついてからずっと後になって」これを書いた

最後のものが Diffie–Hellman 鍵交換と同じ方式である。 Ellis の書き方は率直だ ── Diffie と Hellman が公表した方式は "identical to Williamson's version, except that they restricted q to be prime"（q を素数に限定した点を除けば Williamson の版と同一）。 なお、 Williamson の1976年8月の報告書は、 Diffie–Hellman 論文の受理（同年6月3日）より後の日付である。 秘密の側が先だったのは着想であって、 文書ではない。

ただし、 秘密の側は世界を変えなかった。 ACM の記録が指摘するとおり、 公開の研究者たちの仕事が安全な通信と電子認証を可能にしたのであって、 GCHQ と NSA の仕事はそうしなかった。 Claude Shannon の1949年の秘匿系の理論を論文が引いているように、 この分野は公開の系譜の上にだけ積み上がる。

ECDHE から量子計算機まで

Diffie–Hellman 鍵交換と RSA は、 HTTPS、 SSH、 PGP、 そして エンドツーエンド暗号化 の土台になった。 現在のウェブでは、 楕円曲線上の Diffie–Hellman（ECDHE）が毎回の接続ごとに使い捨ての鍵を作る形が標準である。 1976年に定式化された「安全な別経路なしに鍵を共有する」という問題設定は、 いまも毎秒何百万回と解かれ続けている。

そして、 その解が依存している「離散対数は難しい」「素因数分解は難しい」という仮定は、 大規模な量子計算機が現れれば崩れる。 2025年度のチューリング賞 が量子鍵配送に与えられたのは、 まさにこの前提そのものを別の土台へ移す試みに対してである。