公開鍵暗号
復号オラクル
復号オラクル O d e c ( s k , X , ⋅ ) {\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,\cdot )} は、攻撃者が任意の暗号文 C {\displaystyle C} を復号オラクル O d e c ( s k , X , ⋅ ) {\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,\cdot )} に送信すると、 C ∉ X {\displaystyle C\notin X} である限り、 s k {\displaystyle {\mathsf {sk}}} を使って C {\displaystyle C} を復号した D s k ( C ) {\displaystyle D_{\mathsf {sk}}(C)} を攻撃者に送り返してくれるオラクルである。(下図参照)
復号オラクル O d e c ( s k , X , C ) {\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,C)} If C ∈ X {\displaystyle C\in X} return ⊥ {\displaystyle \bot } . Otherwise return D s k ( C ) {\displaystyle D_{\mathsf {sk}}(C)} .
1960年代、イギリスの政府通信本部 (GCHQ) に所属するジェイムズ・エリス(英語版)が公開鍵暗号(非秘密暗号)を考案し提案は受諾された。しかし理論的には有用性が認められたが、一方向性関数が見つけられずこのアイデアは実用化されなかった。1973年、同機関に入所したクリフォード・コックス(英語版)がこのアイデアに取り組み「作用は可能だが、逆転させられない関数」から素数と素因数分解を基に30分程度で数式を組み立て、さらにマルコム・ウィリアムソン(英語版)が鍵配送問題に解決の糸口を見つけ、今日の"RSA"と呼ばれる暗号システムの基礎を確立した。同時期に、彼らとは無関係な米国のアマチュア数学者、ウィットフィールド・デフィーが独学で公開鍵暗号開発に取り組んでいた。1976年に、ラルフ・マークルの研究の影響を受けたデフィーとマーティン・ヘルマンが公開鍵暗号に関する世界最初の論文「New Directions in Cryptography」を発表した。
公開鍵暗号という新規な発明は、本来、エリス=コックス=ウィリアムソン組が先であったが、論文にして公表し、その有用性を広く伝えたのは、デフィー=ヘルマン=マークル組となったため、本発明の特許権と栄誉は彼らが得た。先に考案していたエリス=コックス=ウィリアムソン組は、英軍の管理下であったGCHQが国家機密となっていたために、後発組が公開鍵暗号の論文を発表しても、契約により口外できなかった。