公開鍵暗号

公開鍵暗号（こうかいかぎあんごう、英語: Public-key cryptography）とは、暗号化と復号とに異なる鍵（手順）を用い、暗号化用の鍵は公開できるようにした暗号方式である（復号用の鍵は秘匿）。これと対照的なものは、暗号化と復号とに同一の鍵（共通鍵）を用いる暗号方式がある。

推測できない数（典型的には巨大なランダムな数）を用いて、最初に非対称鍵アルゴリズムに適した鍵のペアを生成する。

非対称鍵暗号化のスキームでは、公開鍵を使用して誰でもメッセージを暗号化できるが、そのメッセージを復号できるのはペアの秘密鍵の所有者だけである。システムの安全性は、秘密鍵が秘匿されているという点に依存するので、秘密鍵は決して他の誰にも知られてはいけない。

この例では、メッセージは暗号化されたデジタル署名である。まず、Aliceはメッセージを秘密鍵で署名する。次に、Bobは、Aliceがメッセージを送ったこと、そしてそのメッセージが変更されていないことを検証できる。

暗号化は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いるための障害であった。この問題に対して、暗号化鍵の配送問題を解決したのが公開鍵暗号である。

また広い意味で、秘匿を目的とした公開鍵暗号で使われるのと同じ数学的な理論に基づいて、通信の安全性を保障する暗号技術全般を指して公開鍵暗号（あるいは公開鍵暗号技術、非対称暗号技術）と呼ぶこともある。この場合、（秘匿を目的とした）公開鍵暗号方式だけでなく、デジタル署名（秘匿機能は無い）、公開鍵通信路のみを用いて共通鍵を合意することのできるディフィー・ヘルマン鍵交換なども、広い意味での公開鍵暗号である。 以下では、秘匿を目的とした狭い意味での公開鍵暗号について扱う。

共通鍵暗号の問題点

1976年以前には、暗号といえば共通鍵暗号であった。これは、暗号化と復号に同じ（共通の）鍵を使うものである。共通鍵暗号には、鍵の配送を極秘に行わねばならないという課題（鍵配送問題）があった。

共通鍵暗号を用いた通信手順の概略は次のようになる。

1. 受信者は あらかじめ送信者に対して密かに共通鍵 c を渡しておく（両者が逆でもよい）。
2. 送信者は c を使ってメッセージを暗号化し、受信者に送信する。
3. 受信者は c を使って暗号文を復号し、メッセージを読む。

もし段階 1. で、送信者に対してセキュリティの保証されていない通信路を使って鍵を配送した場合、傍受者に共通鍵 c を傍受されてしまうと、この暗号通信は容易に解読されてしまう。共通鍵暗号方式では鍵の取扱いが難しい。

公開鍵暗号の考案

共通鍵暗号に生じる鍵配送問題は、送信者と受信者の両者がただ1つで共通の鍵を用いるために起こる問題である。そこで両者が異なる鍵を用いる方法、すなわち公開鍵暗号が考案された。これが鍵の配送問題を解決した。

公開鍵暗号を用いた通信手順の概略：

1. 通信を受ける者（受信者）は自分の公開鍵（暗号化のための鍵）p を全世界に公開する。
2. 受信者に対して暗号通信をしたい者（送信者）は、公開鍵 p を使ってメッセージを暗号化してから送信する。
3. 受信者は、公開鍵 p と対になる秘密鍵（復号のための鍵）s を密かにもっている。この s を使って受信内容を復号し、送信者からのメッセージを読む。
4. 暗号通信を不正に傍受しようとする者（傍受者）が、送信者が送信した暗号化されたメッセージを傍受したとする。傍受者は、公開鍵 p を知っているが、秘密鍵 s は受信者だけが知っている情報であるので分からない。公開鍵 p から秘密鍵 s を導き出すことは、計算時間の観点から極めて難しい。したがって、暗号文を復号することはおよそできない。

暗号化のための鍵 p と、復号のための鍵 s を異なるものにしたことで、鍵配送問題を解決したのである。

暗号の用語については、(暗号理論の用語)、(暗号の用語)を参照。

公開鍵暗号方式の直観的な定義

モデル

公開鍵暗号方式では、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムを用いる。

鍵生成アルゴリズムは事前準備にあたるアルゴリズムであり、（将来暗号文を受け取りたいと思う）全てのユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵（と呼ばれるデータ）を出力する。公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。

ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータという値をこのアルゴリズムに入力する。セキュリティ・パラメータは、秘密鍵なしで暗号文の解読がどれだけ困難かの尺度である。

さらに鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムは実行ごとに異なる乱数を選ぶので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる。

各ユーザは秘密鍵を秘密裏に保管し、公開鍵を皆に公開する。よってユーザの秘密鍵を知っているのはそのユーザ自身だけであるが、それに対しユーザの公開鍵を知っているのは全てのユーザである。

メッセージを秘匿する暗号通信をするときの 公開鍵、秘密鍵を、それぞれ暗号化鍵、復号鍵ともいう。

暗号文を送るには、送りたいメッセージと、そのメッセージの送信先（受信者）の公開鍵を、入力として暗号化アルゴリズムを実行する（公開鍵は公開情報なので、暗号文の送信者は受信者の公開鍵を手に入れる事ができる）。

それに対し、受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。

復号アルゴリズムでもとのメッセージを復元することを、復号（ふくごう、decryption）と呼ぶ。それに対し、悪意のあるユーザ（攻撃者）が、復号アルゴリズムに（必ずしも）頼らず無理矢理メッセージを復元しようとする試みを解読（cryptanalysis）と呼ぶ。

公開鍵は公開情報であり、それに対応する秘密鍵は受信者本人しか知らない。よって公開されている公開鍵を使えば誰でも暗号文を作成できるが、それに対しその暗号文を復号できるのは受信者本人だけである。

公開鍵の認証

安全性を確保するには、どの公開鍵がどのユーザのものであるのかという対応をきちんとつけておく必要がある。暗号化するときは、受信者の公開鍵 p を用いている。もし、公開鍵 p とユーザとの対応が誤っていると、誤ったユーザの公開鍵を使って暗号文を送信してしまう。これを悪用して、前もってあえて誤った対応表を作成しておくことによって暗号文を解くという攻撃が可能である。（攻撃者はまず、自分の公開鍵をあたかも受信者の公開鍵であるかのような対応表を作る。受信者に当てて暗号文が送られたら、攻撃者はその暗号文を傍受し、自身の秘密鍵で復号する。）

公開鍵とその持ち主を対応させる方法はいくつか考案されている。代表的な方法は次の2つである。どちらも、(信頼できる第三者機関)（英語版）（Trusted Third Party、TTP）が必要になる。

1. 信頼できる第三者機関が各人のIDと公開鍵を対応付けた表（公開鍵簿）を作成し、公開する。
2. 信頼できる第三者機関（複数）が認証局を運営し、公開鍵基盤 (PKI) の仕組みを使って各人のIDと公開鍵とを対応付ける。

歴史

1960年代、イギリスの政府通信本部 (GCHQ) に所属する(ジェイムズ・エリス)（英語版）が公開鍵暗号（非秘密暗号）を考案し提案は受諾された。しかし理論的には有用性が認められたが、一方向性関数が見つけられずこのアイデアは実用化されなかった。1973年、同機関に入所した(クリフォード・コックス)（英語版）がこのアイデアに取り組み「作用は可能だが、逆転させられない関数」から素数と素因数分解を基に30分程度で数式を組み立て、さらに(マルコム・ウィリアムソン)（英語版）が鍵配送問題に解決の糸口を見つけ、今日の"RSA"と呼ばれる暗号システムの基礎を確立した。同時期に、彼らとは無関係な米国のアマチュア数学者、ウィットフィールド・デフィーが独学で公開鍵暗号開発に取り組んでいた。1976年に、ラルフ・マークルの研究の影響を受けたデフィーとマーティン・ヘルマンが公開鍵暗号に関する世界最初の論文「New Directions in Cryptography^[1]」を発表した。

公開鍵暗号という新規な発明は、本来、エリス＝コックス＝ウィリアムソン組が先であったが、論文にして公表し、その有用性を広く伝えたのは、デフィー＝ヘルマン＝マークル組となったため、本発明の特許権と栄誉は彼らが得た。先に考案していたエリス＝コックス＝ウィリアムソン組は、英軍の管理下であったGCHQが国家機密となっていたために、後発組が公開鍵暗号の論文を発表しても、契約により口外できなかった。後年、公開鍵暗号が広く普及したことで本暗号に関する機密扱いが解除され、エリス＝コックス＝ウィリアムソン組の功績が世に知られることになった^[2]。デフィーの「先に開発していたのは本当ですか？」との問いに、エリスは「我々より、君達の方がより多くの事をやっている」と答えている。

公開鍵暗号の概念を実現する具体的な方式は、MITの研究者であったロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの3人が1977年に開発した。この方式は、開発者各人の頭文字を取って「RSA方式」と呼ばれるようになった。1982年、彼らはカリフォリニア州レッドウッド市にデータセキュリティ専門の会社「RSAデータセキュリティ社」を設立した^[3]。

1990年代初頭、フィル・ジマーマンがパーソナル・コンピュータに搭載可能なプログラム「PGP（Pretty Good Privacy）」を開発し公開した。PGPが世界に普及したことで、誰でも公開鍵暗号が使用できるようになった。

公開鍵暗号は、1980年ごろには「公衆暗号 (public cryptography)」とも呼ばれていた。用語「公衆暗号系 (public cryptosystem)」も使われていたが、DES のような公衆が用いる共通鍵暗号を含むかどうかが紛らわしかったので、これらの用語はすぐに使われなくなった。

RSA暗号

公開鍵暗号にはさまざまな方式がある。ここでは典型的な公開鍵暗号方式であるRSA暗号方式を説明する。

この方式の安全性は素因数分解の困難性に基づいている。詳しくはRSA暗号を参照。

大きな素数 p, q が与えられたとき、その積 n = pq を計算することは容易である。しかし逆に、2つの大きな素数の積である自然数 n が与えられたとき、n = pq と素因数分解することは難しい。例えば n=21 のとき p=7, q=3 を求めるのは容易だが、鍵の大きさ（すなわち p, q のビット数）が十分に大きければ、素因数分解にはとてつもない時間が掛かる。

暗号化には n を、復号には p と q を必要とするようなうまい仕組みを作っておく。そして、n を公開鍵として公開する。傍受者は n から p, q を割り出そうとするが、これは時間が掛かりすぎて現実的でない。

もちろん、根気強く分解を試みればいつかは復号に成功するわけである。しかし、一般市民の個人的な通信程度であれば、解読に数年を要する規模の暗号化を施しておけば、それ以上の手間暇を掛けて解読しようとする者はまずいない。これは、事実上秘密が守られているといえる（計算量的安全性）。

軍事用暗号の場合、専用のコンピュータで専門のプログラムを走らせても解読には数億年～数兆年を要するように設計されている。これは、事実上解読不可能といってよい。

実際の使われ方

一般的に、公開鍵暗号は共通鍵暗号よりも暗号化、復号に時間がかかる。そのため、実際の運用では、データの暗号化には「その場限りの共通鍵」を使用し、その共通鍵の配送だけを公開鍵暗号で行う方式がとられることが多い。

公開鍵暗号を初めて実現したのがRSA暗号である。RSA暗号は公開鍵暗号として、実際に広く利用されることとなった。

公開鍵暗号方式の厳密な定義

モデル

kをセキュリティ・パラメータとする。${\displaystyle \Pi =(G,E,D)}$  を、次を満たす平均多項式時間確率アルゴリズム3つ組とする。

1. ${\displaystyle G}$  は鍵生成アルゴリズム (key generation algorithm) と呼ばれ、${\displaystyle 1^{k}}$  を入力されると公開鍵秘密鍵ペア ${\displaystyle (\mathrm {pk} ,\mathrm {sk} )}$  を出力する^{[注 1]}。
2. ${\displaystyle E}$ は暗号化アルゴリズム (encryption algorithm) と呼ばれ、${\displaystyle G}$  の出力した公開鍵 ${\displaystyle \mathrm {pk} }$  と平文と呼ばれるビット列 ${\displaystyle m}$  を入力されると、${\displaystyle m}$  の暗号文(Ciphertext) を出力する。
3. ${\displaystyle D}$  は復号アルゴリズム (decryption algorithm) と呼ばれ、${\displaystyle G}$  の出力した秘密鍵 ${\displaystyle \mathrm {sk} }$  と ${\displaystyle E}$  の出力した暗号文 ${\displaystyle C}$  とを入力されると平文を出力する。

${\displaystyle \Pi =(G,E,D)}$  が後述する正当性を満たすとき、${\displaystyle \Pi }$  は公開鍵暗号方式であるといい、後述する秘匿性をさらに満たすとき、公開鍵暗号方式は安全であるという。

要件

公開鍵暗号方式は、次の2つの要件を満たさねばならない。

1. 正当性 (correctness) : 正当な受信者は、正当な方法で作成された暗号文を復号できる。
2. 秘匿性 (security) : 正当な方法で作成された暗号文を復号できる（またはメッセージのなんらかの部分情報が得られる）のは、正当な受信者だけである。

正当性

定義

${\displaystyle \Pi =(G,E,D)}$  が以下の条件を満たすとき、${\displaystyle \Pi }$  は正当性を満たすという :

任意の平文 m に対し、Pr((pk, sk) ← G(1^k), C ← E_pk(m) : D_sk(C) = m) は圧倒的 (overwhelming) である。

秘匿性

識別不可能性

直観的な定義

${\displaystyle M_{0}}$ 、${\displaystyle M_{1}}$  を攻撃者が指定した2つのメッセージとし、${\displaystyle C}$  を ${\displaystyle M_{0}}$  もしくは${\displaystyle M_{1}}$  を暗号化した暗号文とする。

このとき、攻撃者は ${\displaystyle C}$  が ${\displaystyle M_{0}}$ 、${\displaystyle M_{1}}$  のいずれを暗号化したものであるかを（1/2よりも有意な確率で）知る事はできない。

厳密な定義

${\displaystyle O_{1}}$ , ${\displaystyle O_{2}}$  を2つのオラクル、${\displaystyle b}$  をビットとする。

暗号に対する攻撃者 ${\displaystyle A}$  を用いて次の実験 (Experiment, ゲーム (game) ともいう) をする。

${\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {IND}}-b}^{(O_{1},O_{2})}(A,k)}$ 

${\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})}$ 

${\displaystyle (m_{0},m_{1},{\mathsf {St}})\gets A^{O_{1}}({\mathsf {pk}})}$ 

${\displaystyle C\gets E_{\mathsf {pk}}(m_{b})}$ 

${\displaystyle b'\gets A^{O_{2}}({\mathsf {pk}},C,{\mathsf {St}})}$ 

Return ${\displaystyle b'}$ .

攻撃者 ${\displaystyle A}$  のアドバンテージ(advantage)を :${\displaystyle {\mathsf {Adv}}_{\Pi -{\mathsf {IND}}}^{(O_{1},O_{2})}(A,k)=|{\mathsf {Pr}}({\mathsf {Exp}}{}_{\Pi -{\mathsf {IND}}-0}^{(O_{1},O_{2})}(A,k)=1)-{\mathsf {Pr}}({\mathsf {Exp}}{}_{\Pi -{\mathsf {IND}}-1}^{(O_{1},O_{2})}(A,k)=1)|}$  により定義する。

定義

任意の平均多項式時間確率アルゴリズム ${\displaystyle A}$  (攻撃者と呼ぶ) に対し、

${\displaystyle {\mathsf {Adv}}_{\Pi }^{(O_{1},O_{2})}(A,k)}$  が k に関して無視できるとき、暗号方式 ${\displaystyle \Pi }$  は ${\displaystyle (O_{1},O_{2})}$ -識別不可能 (indistinguishable) であるという。

（注：この「${\displaystyle (O_{1},O_{2})}$ -識別不可能」という言葉はあまり一般的ではない）

特に、

1. ${\displaystyle O_{1}=\bot }$ 、${\displaystyle O_{2}=\bot }$  のとき、公開鍵暗号方式 ${\displaystyle \Pi }$  はKey Only Attackに対し、識別不可能であるという。
2. ${\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )}$ 、${\displaystyle O_{2}=\bot }$  であるとき、公開鍵暗号方式${\displaystyle \Pi }$  は選択暗号文攻撃 (Chosen Chiphertext Attack,(略してCCA1)) に対して識別不可能であるという。
3. ${\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )}$ 、${\displaystyle O_{2}=O_{\mathsf {dec}}({\mathsf {sk}},\{m_{0},m_{1}\},\cdot )}$  であるとき、公開鍵暗号方式 ${\displaystyle \Pi }$  は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して識別不可能であるという。

ただしここで ${\displaystyle O_{\mathsf {dec}}}$  は次の節で述べる復号オラクルである。

公開鍵暗号方式の場合暗号化用の鍵が公開されているので、攻撃者は（オラクルの助けを借りずとも）任意の平文を暗号化する事ができる。このため、Key Only Attackの事を選択平文攻撃（Chosen Plaintest Attack, CPAと略す）ともいう。

復号オラクル

復号オラクル ${\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,\cdot )}$  は、攻撃者が任意の暗号文 ${\displaystyle C}$  を復号オラクル${\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,\cdot )}$  に送信すると、${\displaystyle C\notin X}$  である限り、${\displaystyle {\mathsf {sk}}}$  を使って ${\displaystyle C}$  を復号した ${\displaystyle D_{\mathsf {sk}}(C)}$  を攻撃者に送り返してくれるオラクルである。（下図参照）

復号オラクル${\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,C)}$ 

If ${\displaystyle C\in X}$  return ${\displaystyle \bot }$ .

Otherwise return ${\displaystyle D_{\mathsf {sk}}(C)}$ .

強秘匿性 (Semantic Security)

直観的定義

暗号文を知っていることは、平文を知る上で何の役にもたたない。すなわち、暗号文を知っている状況で攻撃者が知ることができる平文についての部分情報は、暗号文を知らなくても攻撃者が知ることができる情報だけである。

厳密な定義

${\displaystyle k}$  をセキュリティ・パラメータとし、${\displaystyle \Pi =(G,E,D)}$  を公開鍵暗号方式とする。${\displaystyle A,B}$  を多項式時間機械とする。

さらに、${\displaystyle O_{1},O_{2}}$  をオラクルとする。

次の2つのゲームを考える。ただしゲーム中で、${\displaystyle M,f}$  は多項式時間機械（の動作を記したプログラム）、${\displaystyle St}$  はビット列で、${\displaystyle A}$  の状態と呼ばれる。

${\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {SS-Real}}}^{(O_{1},O_{2})}(A,k)}$ 

${\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})}$ 

${\displaystyle (M,{\mathsf {St}})\gets A^{O_{1}}({\mathsf {pk}})}$ 

${\displaystyle m\gets M}$ 

${\displaystyle C\gets E_{\mathsf {pk}}(m)}$ 

${\displaystyle (y,f)\gets A^{O_{2}}(C,{\mathsf {St}})}$ 

If ${\displaystyle y=f(m)}$ , return 1.

Otherwise return 0.

${\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {SS-Ideal}}}^{(O_{1},O_{2})}(B,k)}$ 

${\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})}$ 

${\displaystyle (M,{\mathsf {St}})\gets B^{O_{1}}({\mathsf {pk}})}$ 

${\displaystyle m\gets M}$ 

${\displaystyle (y,f)\gets B^{O_{2}}({\mathsf {St}})}$ 

If ${\displaystyle y=f(m)}$ , return 1.

Otherwise return 0.

任意の多項式時間機械 ${\displaystyle A}$  に対し、ある多項式時間機械 ${\displaystyle B}$  が存在し、

${\displaystyle |\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {SS-Real}}}^{(O_{1},O_{2})}(A,k)=1)-\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {SS-Ideal}}}^{(O_{1},O_{2})}(B,k))|}$ 

が k に関して無視できるとき、公開鍵暗号方式 ${\displaystyle \Pi =(G,E,D)}$  は ${\displaystyle (O_{1},O_{2})}$ -強秘匿 (Semantic Secure) であるという。

1. ${\displaystyle O_{1}=\bot }$ 、${\displaystyle O_{2}=\bot }$  のとき、公開鍵暗号方式 ${\displaystyle \Pi }$  はKey Only Attackに対し、強秘匿であるという。
2. ${\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )}$ 、${\displaystyle O_{2}=\bot }$  であるとき、公開鍵暗号方式 ${\displaystyle \Pi }$  は選択暗号文攻撃（Chosen Chiphertext Attack,（略してCCA1）） に対して強秘匿であるという。
3. ${\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )}$ 、${\displaystyle O_{2}=O_{\mathsf {dec}}({\mathsf {sk}},\{m_{0},m_{1}\},\cdot )}$  であるとき、公開鍵暗号方式 ${\displaystyle \Pi }$  は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して強秘匿であるという。

頑強性 (Non Malleability) (Bellare等による定義)

${\displaystyle A}$  を攻撃者とし、以下のゲームを考える。

${\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {NM}}-b}^{(O_{1},O_{2})}(A,k)}$ 

${\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})}$ 

${\displaystyle (M,{\mathsf {St}})\gets A^{O_{1}}({\mathsf {pk}})}$ 

${\displaystyle m_{0},m_{1}\gets M}$ 

${\displaystyle C\gets E_{\mathsf {pk}}(m_{b})}$ 

${\displaystyle (R,C'_{1},\ldots ,C'_{n})\gets A^{O_{2}}(C,{\mathsf {St}})}$ 

${\displaystyle m'_{1}\gets D_{\mathsf {sk}}(C'_{1}),\ldots ,m'_{n}\gets D_{\mathsf {sk}}(C'_{n})}$ 

If ${\displaystyle C=C'_{i}}$  for some ${\displaystyle i}$ , return 0.

If ${\displaystyle m'_{i}=\bot }$  for some ${\displaystyle i}$ , return 0.

If ${\displaystyle R(m_{b},m'_{1},\ldots ,m'_{n})=0}$  return 0.

Return 1.

ただし、上のゲームで、${\displaystyle M}$  は、常に同じビット数のメッセージを出力するアルゴリズムでなければならない。

任意の多項式時間機械 ${\displaystyle A}$  に対し、

${\displaystyle |\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {NM}}-1}^{(O_{1},O_{2})}(A,k)=1)-\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {NM}}-0}^{(O_{1},O_{2})}(A,k)=1)|}$ 

が k に関して無視できるとき、公開鍵暗号方式 ${\displaystyle \Pi =(G,E,D)}$  は ${\displaystyle (O_{1},O_{2})}$ -non malleableであるという。

1. ${\displaystyle O_{1}=\bot }$ 、${\displaystyle O_{2}=\bot }$ のとき、公開鍵暗号方式${\displaystyle \Pi }$ はKey Only Attackに対し、頑強である (non malleable) という。
2. ${\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )}$ 、${\displaystyle O_{2}=\bot }$ であるとき、公開鍵暗号方式${\displaystyle \Pi }$ は選択暗号文攻撃（Chosen Chiphertext Attack,（略してCCA1））に対して頑強であるという。
3. ${\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )}$ 、${\displaystyle O_{2}=O_{\mathsf {dec}}({\mathsf {sk}},\{m_{0},m_{1}\},\cdot )}$ であるとき、公開鍵暗号方式${\displaystyle \Pi }$ は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して頑強であるという。

参考文献

論文

• Relations among notions of security for public-key encryption schemes, M. Bellare, A. Desai, D. Pointcheval and P. Rogaway
• Key-Privacy in Public-Key Encryption, Mihir Bellare, Alexandra Boldyreva, Anand Desai, David Pointcheval

関連項目

• 秘匿通信
• 電子署名
• 素因数分解

暗号関連

• 暗号理論
• 暗号
• ディフィー・ヘルマン鍵共有
• RSA暗号
• ElGamal暗号
• 楕円曲線暗号
• Merkle-Hellmanナップサック暗号 - ラルフ・マークル - マークルのパズル
• NTRU暗号
• アリスとボブ

脚注

[脚注の使い方]

注釈

1. ^ 入力の${\displaystyle 1^{k}}$ は、1が${\displaystyle k}$ 個並んだもののことであり、セキュリティパラメータを一進法で表したものである。もし${\displaystyle k}$ を2進数で（つまり、${\displaystyle log_{2}k}$ ビットで）表して入力することにすると、${\displaystyle k}$ ビットを出力するために指数時間かかることになり、多項式時間アルゴリズムではなくなってしまう。一進法を使うことで、これを回避できる。

出典

1. ^ Whitfield Diffie; Martin Hellman (1976). “New directions in cryptography”. IEEE Transactions on Information Theory 22 (6): 644. doi:10.1109/TIT.1976.1055638. 
2. ^ 井上孝司著、「通信と情報の保全 暗号化の話」『軍事研究2011年11月号』、（株）ジャパン・ミリタリー・レビュー、雑誌 03241-11、ISSN 0533-6716、227-228頁
3. ^ Press Releases 2011年9月29日, at the Wayback Machine. - RSA社サイト（英語、2012年2月19日閲覧）

外部リンク

• 『共通鍵暗号と公開鍵暗号の仕組み』 - 高校数学の美しい物語