公開鍵暗号のソースを表示

{{出典の明記|date=2012-02}}
[[画像:Public-key-crypto-1.svg|250px|thumb|推測できない数（典型的には[[ランダム]]に生成した巨大な数）を用いて、最初に非対称鍵アルゴリズムに適した[[鍵 (暗号)|鍵]]のペアを生成する。]]
[[画像:Public_key encryption.svg|250px|thumb|非対称鍵暗号化のスキームでは、公開鍵を使用して誰でもメッセージを暗号化できるが、そのメッセージを復号できるのはペアの秘密鍵の所有者だけである。システムの安全性は、秘密鍵が秘匿されているという点に依存するので、秘密鍵は決して他の誰にも知られてはいけない。]]
<!--ここに本文中に説明のない鍵交換スキームを入れると、かえって理解の妨げになる。
[[画像:Public key shared secret.svg|280px|thumb|[[Diffie-Hellman鍵交換|Diffie–Hellman鍵交換]]のスキームでは、各パーティが公開鍵と秘密鍵のペアを生成し、ペアのうち公開鍵を配布する。互いの公開鍵の本物の（この点が非常に重要である）コピーを取得すれば、AliceとBobはオフラインで共有鍵を計算できる。共有鍵は、たとえば、基本的にすべての場合にはるかに高速な[[共通鍵暗号|対称暗号]]の鍵として利用できる。]]
-->
[[画像:Private key signing.svg|250px|thumb|この例では、メッセージは暗号化された[[デジタル署名]]である。まず、Aliceはメッセージを秘密鍵で署名する。次に、Bobは、Aliceがメッセージを送ったこと、そしてそのメッセージが変更されていないことを検証できる。]]
'''公開鍵暗号'''（こうかいかぎあんごう、{{Lang-en|Public-key cryptography}}）とは、[[暗号化]]と[[復号]]とに異なる[[鍵 (暗号)|鍵]]（手順）を用い、暗号化用の鍵は公開できるようにした[[暗号方式]]である（復号用の鍵は秘匿）。対照的な暗号方式として、[[暗号化]]と[[復号]]に同一の鍵を用いる[[共通鍵暗号]]がある。

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

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

以下では、通信の秘匿を目的とした狭義での公開鍵暗号について扱う。

== 共通鍵暗号の問題点 ==
1976年以前には、数理による暗号といえば[[共通鍵暗号]]であった。これは暗号化と復号に共通の鍵を使う方式である。共通鍵暗号には、鍵の受け渡しを密かに行わなければならないという課題（鍵配送問題）があった。

共通鍵暗号を用いた通信手順の概略は次のようになる。
# あらかじめ、受信者と送信者は密かに共通鍵 c の受け渡しをしておく。
# 送信者は c を使ってメッセージを暗号化し、受信者に送信する。
# 受信者は c を使って暗号文を復号し、メッセージを読む。

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

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

公開鍵暗号を用いた通信手順の概略：
# 通信を受ける者（受信者）は自分の[[鍵 (暗号)|公開鍵]]（暗号化のための鍵）p を全世界に公開する。
# 受信者に対して暗号通信をする者（送信者）は、公開鍵 p を使ってメッセージを暗号化してから送信する。
# 受信者は、公開鍵 p と対になる秘密鍵（復号のための鍵）s を密かにもっている。この s を使って受信内容を復号し、送信者からのメッセージを読む。

暗号通信を不正に傍受しようとする者（傍受者）が公開鍵暗号の方式によって暗号化されたメッセージを傍受したとしても、公開鍵 p から秘密鍵 s を導き出すことは、[[計算量的安全性を持つ暗号|計算時間の観点から]]極めて難しいため、暗号文を復号することはおよそできない。

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

なお、暗号の用語については、[[暗号理論#用語|暗号理論の用語]]、[[暗号#用語|暗号の用語]]を参照。

== 公開鍵暗号方式の直観的な定義 ==
=== モデル ===
公開鍵暗号方式では、'''鍵生成アルゴリズム'''、'''暗号化アルゴリズム'''、'''復号アルゴリズム'''を用いる。

鍵生成アルゴリズムは事前準備のためのアルゴリズムであり、（将来暗号文を受け取りたい）ユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵（それぞれ、そのように呼ばれるデータ）を出力する。<!--公開鍵と秘密鍵はちょうど「錠」と「鍵」の関係に対応しており、-->公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。<!--（注：公開「鍵」という名前だが、実際は「錠」）。--><!--「錠」と「鍵」に例えることも「可能」だが...-->

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

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

各ユーザは秘密鍵を密かに保管し、公開鍵を公開する。ユーザの秘密鍵を知っているのはそのユーザ自身だけであり、ユーザの公開鍵を知っている(知ることができる)のは全てのユーザである。

メッセージを秘匿する暗号通信をするときの公開鍵、秘密鍵を、それぞれ'''暗号化鍵'''、'''復号鍵'''ともいう。<!-- 認証時には逆転する -->

暗号文を送る際は、送りたいメッセージおよびそのメッセージの送信先（受信者）の公開鍵を入力として暗号化アルゴリズムを実行する。
受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。
公開鍵を使えば'''誰でも'''暗号文を作成できるが、その暗号文を正しく復号できるのは受信者本人だけである。

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

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

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

== 歴史 ==
1960年代、イギリスの[[政府通信本部]] (GCHQ) に所属する{{仮リンク|ジェイムズ・エリス|en|James H. Ellis}}が公開鍵暗号（非秘密暗号）を考案し提案は受諾された。しかし理論的には有用性が認められたが、[[一方向性関数]]が見つけられずこのアイデアは実用化されなかった。1973年、同機関に入所した{{仮リンク|クリフォード・コックス|en|Clifford Cocks}}がこのアイデアに取り組み「作用は可能だが、逆転させられない関数」から素数と素因数分解を基に30分程度で数式を組み立て、さらに{{仮リンク|マルコム・ウィリアムソン|en|Malcolm J. Williamson}}が鍵配送問題に解決の糸口を見つけ、今日の"[[RSA暗号|RSA]]"と呼ばれる暗号システムの基礎を確立した。同時期に、彼らとは無関係な米国のアマチュア数学者、[[ウィットフィールド・デフィー]]が独学で公開鍵暗号開発に取り組んでいた。[[1976年]]に、[[ラルフ・マークル]]の研究の影響を受けたデフィーと[[マーティン・ヘルマン]]が公開鍵暗号に関する世界最初の論文「''New Directions in Cryptography<ref name=newdirections>{{cite journal|title=New directions in cryptography|journal=IEEE Transactions on Information Theory |volume=22|issue=6|pages=644|doi=10.1109/TIT.1976.1055638|author1=Whitfield Diffie|author2=Martin Hellman|year=1976|citeseerx = 10.1.1.37.9720}}</ref>''」を発表した。

公開鍵暗号という新規な発明は、本来、エリス＝コックス＝ウィリアムソン組が先であったが、論文にして公表し、その有用性を広く伝えたのは、デフィー＝ヘルマン＝マークル組となったため、本発明の特許権と栄誉は彼らが得た。先に考案していたエリス＝コックス＝ウィリアムソン組は、英軍の管理下であったGCHQが国家機密となっていたために、後発組が公開鍵暗号の論文を発表しても、契約により口外できなかった。後年、公開鍵暗号が広く普及したことで本暗号に関する機密扱いが解除され、エリス＝コックス＝ウィリアムソン組の功績が世に知られることになった<ref>井上孝司著、「通信と情報の保全 暗号化の話」『軍事研究2011年11月号』、（株）ジャパン・ミリタリー・レビュー、雑誌 03241-11、ISSN 0533-6716、227-228頁</ref>。デフィーの「先に開発していたのは本当ですか？」との問いに、エリスは「我々より、君達の方がより多くの事をやっている」と答えている。

公開鍵暗号の概念を実現する具体的な方式は、MITの研究者であった[[ロナルド・リベスト]]、[[アディ・シャミア]]、[[レオナルド・エーデルマン]]の3人が[[1977年]]に開発した。この方式は、開発者各人の頭文字を取って「RSA方式」と呼ばれるようになった。1982年、彼らはカリフォリニア州レッドウッド市にデータセキュリティ専門の会社「RSAデータセキュリティ社」を設立した<ref>[http://www.rsa.com/press_release.aspx?id=716 Press Releases] {{webarchive|url=https://web.archive.org/web/20110929142639/http://www.rsa.com/press_release.aspx?id=716 |date=2011年9月29日 }} - RSA社サイト（英語、2012年2月19日閲覧）</ref>。

1990年代初頭、[[フィル・ジマーマン]]がパーソナル・コンピュータに搭載可能なプログラム「PGP（[[Pretty Good Privacy]]）」を開発し公開した。PGPが世界に普及したことで、誰でも公開鍵暗号が使用できるようになった。
<!--　この文章は多くの誤解を招きますが、共通鍵暗号の記事では無いので推敲するよりも削除した方がすっきりします。
普通にイメージすれば、暗号化する方法を知っているなら逆手順で復号できそうなものである。'''共通鍵暗号'''の場合はまさにそうであって、傍受者に暗号化手順を知られれば即、暗号通信の安全性が損なわれてしまうという欠点があった。暗号通信を安全に行うためには、[[第二次世界大戦]]で[[ドイツ]]軍が使用した[[エニグマ (暗号機)|エニグマ暗号]]のように鍵の保管に手間暇を掛けねばならなかったし、そのエニグマ暗号にしても大戦末期には[[連合国]]側に暗号化の手順を（つまりは復号の手順をも）知られていたのである。-->

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

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

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

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

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

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

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

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

== 公開鍵暗号方式の厳密な定義 ==
=== モデル ===
kをセキュリティ・パラメータとする。<math>\Pi=(G,E,D)</math> を、次を満たす平均[[多項式時間]]確率アルゴリズム3つ組とする。
#<math>G</math> は'''鍵生成アルゴリズム''' (key generation algorithm) と呼ばれ、<math>1^k</math> を入力されると公開鍵秘密鍵ペア <math>(\mathrm{pk},\mathrm{sk})</math> を出力する<ref group="注">入力の<math>1^k</math>は、1が<math>k</math>個並んだもののことであり、セキュリティパラメータを[[一進法]]で表したものである。もし<math>k</math>を2進数で（つまり、<math>log_2 k</math>ビットで）表して入力することにすると、<math>k</math>ビットを出力するために指数時間かかることになり、多項式時間アルゴリズムではなくなってしまう。一進法を使うことで、これを回避できる。</ref>。
#<math>E</math>は'''暗号化アルゴリズム''' (encryption algorithm) と呼ばれ、<math>G</math> の出力した公開鍵 <math>\mathrm{pk}</math> と'''平文'''と呼ばれるビット列 <math>m</math> を入力されると、<math>m</math> の'''暗号文'''(Ciphertext) を出力する。
#<math>D</math> は'''復号アルゴリズム''' (decryption algorithm) と呼ばれ、<math>G</math> の出力した秘密鍵 <math>\mathrm{sk}</math> と <math>E</math> の出力した暗号文 <math>C</math> とを入力されると平文を出力する。

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

=== 要件 ===
公開鍵暗号方式は、次の2つの要件を満たさねばならない。
#正当性 (correctness) : 正当な受信者は、正当な方法で作成された暗号文を復号できる。
#秘匿性 (security) : 正当な方法で作成された暗号文を復号できる（またはメッセージのなんらかの部分情報が得られる）のは、正当な受信者だけである。

=== 正当性 ===
; 定義
: <math>\Pi=(G,E,D)</math> が以下の条件を満たすとき、<math>\Pi</math> は正当性を満たすという :
: 任意の平文 m に対し、Pr((pk, sk) ← G(1<sup>k</sup>), C ← E<sub>pk</sub>(m) : D<sub>sk</sub>(C) = m) は[[圧倒的]] (overwhelming) である。

=== 秘匿性 ===
==== 識別不可能性 ====
===== 直観的な定義 =====
<math>M_0</math>、<math>M_1</math> を攻撃者が指定した2つのメッセージとし、<math>C</math> を <math>M_0</math> もしくは<math>M_1</math> を暗号化した暗号文とする。

このとき、攻撃者は <math>C</math> が <math>M_0</math>、<math>M_1</math> のいずれを暗号化したものであるかを（1/2よりも有意な確率で）知る事はできない。

===== 厳密な定義 =====
<math>O_1</math>, <math>O_2</math> を2つのオラクル、<math>b</math> をビットとする。

暗号に対する攻撃者 <math>A</math> を用いて次の'''実験''' (Experiment, '''ゲーム''' (game) ともいう) をする。
: <math>\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{IND}-b}(A,k)</math>
:: <math>\mathsf{(pk,sk)}\gets G(1^k)</math>
:: <math>(m_0,m_1,\mathsf{St}) \gets A^{O_1}(\mathsf{pk})</math>
:: <math>C\gets E_{\mathsf{pk}}(m_b)</math>
:: <math>b' \gets A^{O_2}(\mathsf{pk},C,\mathsf{St})</math>
:: Return <math>b'</math>.
攻撃者 <math>A</math> の'''アドバンテージ'''(advantage)を :<math>\mathsf{Adv}^{(O_1,O_2)}_{\Pi-\mathsf{IND}}(A,k)=|\mathsf{Pr}(\mathsf{Exp}{}^{(O_1,O_2)}_{\Pi-\mathsf{IND}-0}(A,k)=1)-\mathsf{Pr}(\mathsf{Exp}{}^{(O_1,O_2)}_{\Pi-\mathsf{IND}-1}(A,k)=1)|</math>
により定義する。

; 定義
: 任意の平均多項式時間確率アルゴリズム <math>A</math> ('''攻撃者'''と呼ぶ) に対し、
:: <math>\mathsf{Adv}^{(O_1,O_2)}_{\Pi}(A,k)</math> が ''k'' に関して無視できるとき、暗号方式 <math>\Pi</math> は <math>(O_1,O_2)</math>-'''識別不可能''' (indistinguishable) であるという。
: （注：この「<math>(O_1,O_2)</math>-識別不可能」という言葉はあまり一般的ではない）
: 特に、
:# <math>O_1=\bot</math>、<math>O_2=\bot</math> のとき、公開鍵暗号方式 <math>\Pi</math> は'''Key Only Attack'''に対し、識別不可能であるという。
:# <math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=\bot</math> であるとき、公開鍵暗号方式<math>\Pi</math> は'''選択暗号文攻撃''' (Chosen Chiphertext Attack,(略してCCA1)) に対して識別不可能であるという。
:# <math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=O_{\mathsf{dec}}(\mathsf{sk},\{m_0,m_1\},\cdot)</math> であるとき、公開鍵暗号方式 <math>\Pi</math> は'''適応的選択暗号文攻撃'''（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して識別不可能であるという。

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

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

===== 復号オラクル =====
復号オラクル <math>O_{\mathsf{dec}}(\mathsf{sk},X,\cdot)</math> は、攻撃者が任意の暗号文 <math>C</math> を復号オラクル<math>O_{\mathsf{dec}}(\mathsf{sk},X,\cdot)</math> に送信すると、<math>C\notin X</math> である限り、<math>\mathsf{sk}</math> を使って <math>C</math> を復号した <math>D_{\mathsf{sk}}(C)</math> を攻撃者に送り返してくれるオラクルである。（下図参照）
: '''復号オラクル'''<math>O_{\mathsf{dec}}(\mathsf{sk},X,C)</math>
:: If <math>C\in X</math> return <math>\bot</math>.
:: Otherwise return <math>D_{\mathsf{sk}}(C)</math>.

==== 強秘匿性 (Semantic Security) ====
===== 直観的定義 =====
暗号文を知っていることは、平文を知る上で何の役にもたたない。すなわち、暗号文を知っている状況で攻撃者が知ることができる平文についての部分情報は、暗号文を知らなくても攻撃者が知ることができる情報だけである。

===== 厳密な定義 =====
<math>k</math> をセキュリティ・パラメータとし、<math>\Pi=(G,E,D)</math> を公開鍵暗号方式とする。<math>A,B</math> を多項式時間機械とする。

さらに、<math>O_1,O_2</math> をオラクルとする。

次の2つのゲームを考える。ただしゲーム中で、<math>M,f</math> は多項式時間機械（の動作を記したプログラム）、<math>St</math> はビット列で、<math>A</math> の'''状態'''と呼ばれる。
: <math>\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{SS-Real}}(A,k)</math>
:: <math>\mathsf{(pk,sk)}\gets G(1^k)</math>
:: <math>(M,\mathsf{St}) \gets A^{O_1}(\mathsf{pk})</math>
:: <math>m \gets M</math>
:: <math>C \gets E_{\mathsf{pk}}(m)</math>
:: <math>(y,f) \gets A^{O_2}(C,\mathsf{St})</math>
:: If <math>y=f(m)</math>, return 1.
:: Otherwise return 0.

: <math>\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{SS-Ideal}}(B,k)</math>
:: <math>\mathsf{(pk,sk)}\gets G(1^k)</math>
:: <math>(M,\mathsf{St}) \gets B^{O_1}(\mathsf{pk})</math>
:: <math>m \gets M</math>
:: <math>(y,f) \gets B^{O_2}(\mathsf{St})</math>
:: If <math>y=f(m)</math>, return 1.
:: Otherwise return 0.

任意の多項式時間機械 <math>A</math> に対し、ある多項式時間機械 <math>B</math> が存在し、
: <math>|\Pr(\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{SS-Real}}(A,k)=1)-\Pr(\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{SS-Ideal}}(B,k))|</math>
が ''k'' に関して無視できるとき、公開鍵暗号方式 <math>\Pi=(G,E,D)</math> は <math>(O_1,O_2)</math>-'''強秘匿''' (Semantic Secure) であるという。

# <math>O_1=\bot</math>、<math>O_2=\bot</math> のとき、公開鍵暗号方式 <math>\Pi</math> は'''Key Only Attack'''に対し、強秘匿であるという。
# <math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=\bot</math> であるとき、公開鍵暗号方式 <math>\Pi</math> は'''選択暗号文攻撃'''（Chosen Chiphertext Attack,（略してCCA1）） に対して強秘匿であるという。
# <math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=O_{\mathsf{dec}}(\mathsf{sk},\{m_0,m_1\},\cdot)</math> であるとき、公開鍵暗号方式 <math>\Pi</math> は'''適応的選択暗号文攻撃'''（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して強秘匿であるという。

==== 頑強性 (Non Malleability) (Bellare等による定義) ====
<math>A</math> を攻撃者とし、以下のゲームを考える。
: <math>\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{NM}-b}(A,k)</math>
:: <math>\mathsf{(pk,sk)}\gets G(1^k)</math>
:: <math>(M,\mathsf{St})\gets A^{O_1}(\mathsf{pk})</math>
:: <math>m_0,m_1 \gets M</math>
:: <math>C \gets E_{\mathsf{pk}}(m_b)</math>
:: <math>(R,C'_1,\ldots,C'_n) \gets A^{O_2}(C,\mathsf{St})</math>
:: <math>m'_1 \gets D_{\mathsf{sk}}(C'_1),\ldots,m'_n \gets D_{\mathsf{sk}}(C'_n)</math>
:: If <math>C=C'_i</math> for some <math>i</math>, return 0.
:: If <math>m'_i=\bot</math> for some <math>i</math>, return 0.
:: If <math>R(m_b,m'_1,\ldots,m'_n)=0</math> return 0.
:: Return 1.
ただし、上のゲームで、<math>M</math> は、常に同じビット数のメッセージを出力するアルゴリズムでなければならない。

任意の多項式時間機械 <math>A</math> に対し、
: <math>|\Pr(\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{NM}-1}(A,k)=1)-\Pr(\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{NM}-0}(A,k)=1)|</math>

が ''k'' に関して無視できるとき、公開鍵暗号方式 <math>\Pi=(G,E,D)</math> は <math>(O_1,O_2)</math>-'''non malleable'''であるという。
# <math>O_1=\bot</math>、<math>O_2=\bot</math>のとき、公開鍵暗号方式<math>\Pi</math>は'''Key Only Attack'''に対し、頑強である (non malleable) という。
# <math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=\bot</math>であるとき、公開鍵暗号方式<math>\Pi</math>は'''選択暗号文攻撃'''（Chosen Chiphertext Attack,（略してCCA1））に対して頑強であるという。
# <math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=O_{\mathsf{dec}}(\mathsf{sk},\{m_0,m_1\},\cdot)</math>であるとき、公開鍵暗号方式<math>\Pi</math>は'''適応的選択暗号文攻撃'''（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して頑強であるという。

== 参考文献 ==
=== 論文 ===
* [https://cseweb.ucsd.edu/~mihir/papers/relations.html Relations among notions of security for public-key encryption schemes], M. Bellare, A. Desai, D. Pointcheval and P. Rogaway
* [https://cseweb.ucsd.edu/~mihir/papers/anonenc.html Key-Privacy in Public-Key Encryption], Mihir Bellare, Alexandra Boldyreva, Anand Desai, David Pointcheval

== 関連項目 ==
* [[秘匿通信]]
* [[電子署名]]
* [[素因数分解]]<!--
* [[エニグマ (暗号機)|エニグマ]] -第二次大戦時、ドイツ軍が採用したローター式暗号機。非秘密暗号は開発以前にGCHQによるエニグマ解読チームが組まれた事にあった、チームの内訳は数学、統計、物理学者らの他にクロスワードパズルを得意としている者らからなり、総当たりで解読を行った。←この記事には不要 -->

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

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist2}}
=== 出典 ===
{{Reflist}}

== 外部リンク ==
* {{高校数学の美しい物語|1142|共通鍵暗号と公開鍵暗号の仕組み}}

{{cryptography navbox|public-key}}
{{SSL/TLS}}
{{Authority control}}

{{DEFAULTSORT:こうかいかきあんこう}}
[[Category:公開鍵暗号|*]]
[[Category:暗号技術]]