



I240 暗号理論 2019
公開鍵暗号と署名（２）2019/11/22 講師 藤崎

1 はじめにCramer-Shoup 公開鍵暗号を紹介し、これが IND-CCA 安全を満たすことを証明する。
（追記）証明の順番を間違えたので、ハッシュ関数の仮定が TCR 安全性ではなく、CR 安全性になってしまっています。今回は CR 安全性にして、資料を修正しておきます。その他、微細な修正（２倍を忘れたとか）。

2 公開鍵暗号
2.1 公開鍵暗号の定義
Π = (K, E, D) はセキュリティパラメータ κ ∈ N に依存する三つのアルゴリズムの組みであり次のように定義される：• 鍵生成アルゴリズム K: 1κ を入力としてとり、(pk, sk) を出力する確率的多項式時間アルゴリズム。
この試行を (pk, sk) ← K(1κ ) と書く。(pk, sk) をそれぞれ公開鍵、秘密鍵と呼ぶ。

• 暗号化アルゴリズム E: 公開鍵 pk と m ∈ M を入力としてとり、ct を出力する確率的多項式時間アルゴリズム。この試行を ct ← Epk (m) と書く。m を平文、ct を暗号文と呼ぶ。

• 復号化アルゴリズム D: 秘密鍵 sk と暗号文 ct ∈ C を入力としてとり m を出力する確定的多項式時間
アルゴリズム。この試行を m ← Dsk (ct) と書く。
平文空間 M と暗号文空間 C は pk に依存して {0, 1}∗ の部分集合として一意に定まるものとする。
定義 1

Π = (K, E, D) が、十分大きな全てのセキュリティパラメータ κ ∈ N に対して、(pk, sk) ∈ K(1κ ),m ∈ M, ct ∈ Epk (m) なら Dsk (ct) = m を常に満足する (Correctness) とき、Π を公開鍵暗号とよぶ。

2.2 公開鍵暗号の安全性のクラス
公開鍵暗号の安全性は, 攻撃者 (adversary) の解読目標（「部分解読」か「完全解読」等）への耐性と、攻撃者の利用可能な環境（選択平文攻撃、選択暗号文攻撃）の２つの独立な要素の組み合わせによって定義される。
「解読目標耐性」には、「一方向性（ one-wayness (OW), 完全解読不可）」「識別不可能性（ indistinguishability(IND), いかなる部分解読も不可）」「頑強性（ non-malleability (NM)）」などが存在する。一方、攻撃者の環境には「受動的攻撃（選択平文攻撃 (chosen-plaintext attack (CPA)) 」「非適応的選択暗号文攻撃(non-adaptive chosen-ciphertext attack or lunch-time attack (CCA1)) 」「適応的選択暗号文攻撃 (adaptive
chosen-ciphertext attack (CCA2)) 」などがある。
以下では、IND-CPA 安全性（選択平文攻撃に対する識別不可能性）と IND-CCA2 安全性（適応的選択暗
号文攻撃に対する識別不可能性）について説明する。IND-CCA1 安全性を扱わないので、IND-CCA2 安
全性を紛れがないときは単に IND-CCA 安全性とよぶことにする。

1

■識別不可能性 (indistinguishability) 公開鍵暗号が暗号が通信情報を秘匿するものであることを鑑みると、一方向性は暗号の安全性を定義するのに十分な概念とは言えない。公開鍵暗号のいかなる部分情報解読も不可であることを示すのに次のようなゲームが利用される。

[公開鍵暗号 Π の識別ゲーム]

ゲームは, 攻撃者 A と攻撃者に問題を与える挑戦者 S からなる。

1. 挑戦者 S は, K を起動して (pk, sk) ← K(1κ ) を得た後, 攻撃者 A に pk を与える。
2. 攻撃者 A は, 二つの平文 m0 , m1 ∈ M を出力する。
3. 挑戦者 S は, コイン b∗ ∈ {0, 1} をふり, m0 , m1 のどちらを暗号化するか決める。
4. 攻撃者 A に ct∗ = Epk (mb∗ ) を入力する。
5. 攻撃者 A は, ビット b ∈ {0, 1} を出力する。
6. b = b∗ の時, A の勝利、それ以外のときは S の勝利とする。
仮に, Π がいかなる部分情報も漏らさないのであれば, A が勝利できる確率は、高々 1/2 である。A の 1/2 を超えて勝利できる確率を（正規化したものを）A の成功確率（アドバンテージ）として定義する。しかしまず,
このゲームにバリエーションを与えてやることを考える。
■選択平文攻撃・（適応的）選択暗号文攻撃

A が, 暗号化オラクル Epk 、復号化オラクル Dsk を利用できるかで、上記のゲームは二つのバリエーションができる。暗号化オラクル Epk を利用できる環境を, 選択平文攻撃という。一方, 復号化オラクル Dsk を利用できる環境を, 選択暗号文攻撃という。
公開鍵暗号では, A は pk を知っているので, 自分で Epk を利用して任意の平文 m を暗号化できる。よって選択平文攻撃はもっとも弱い A の攻撃法である。
選択暗号文攻撃では, A は上記のゲームにおいていかなる時でも、復号化オラクル Dsk を利用できる。唯一の制限は, ステップ (4) で入力されたチャレンジ暗号文 Epk (mb∗ ) を復号化オラクルに質問してはいけないということである。このようなチャレンジ暗号文をもらった後、復号オラクルにアクセスできる攻撃法を適応的選択暗号文攻撃 (adaptive chosen-ciphertext attack (CCA2)) と呼ぶが、ここでは単に選択暗号文攻撃(chosen-ciphertext attack (CCA)) と呼ぶことにする。
■IND-CPA-安全, IND-CCA-安全 以下に、INDATK ゲームで攻撃者 A = (A1 , A2 ) が正しく b∗ を推測できた場合、1 を出力するような試行（確率変数）を定義する。

Exptind-atk
Π,A (κ):(pk, sk) ← K(1κ )1(m0 , m1 , st) ← AO
1 (pk)b∗ ← {0, 1}; ct∗ ← E(pk, mb∗ )∗2b ← AO2 (st, ct )If b = b∗ , return 1 else return 0.
図 1 Security Experiment for IND-ATKと定義する。上記確率は K, Epk , A（の内部コインに）依存する。

• ATK=CPA (IND-CPA Game): O1 = O2 = ⊥. A はオラクルに質問できない。
• ATK=CCA1 (IND-CCA1 Game): O1 = Dsk (·), O2 = ⊥. A はチャレンジ暗号文をもらった後はオラクルに質問できない。

2• ATK=CCA2 (IND-CCA2 Game): O1 = O2 = Dsk (·), A はチャレンジ暗号文をもらった後もチャレンジ暗号文以外であればオラクルに質問できる。
攻撃者 A の Π に対する IND-ATK 攻撃成功確率（アドバンテージ）を
ind-atk
Advind-atk
Π,A (κ) := 2 Pr[ExptΠ,A (κ) = 1] − 1と定義する。
今回、IND-CCA1 はあまり考えないので、IND-CCA2 を IND-CCA と書き、IND-CPA 安全性とIND-CCA 安全性についてのみ定義する。
定義 2（IND-CPA, IND-CCA 安全性） 復号オラクル（O1 オラクル、O2 オラクル）に最大 q 回質問する
任意の t-時間アルゴリズム（族）の攻撃者 A を考える。この A に対して、十分大きな全ての κ ∈ N
で, Advind-cca
A,Π (κ) ≤ ϵ が成立するとき, 公開鍵暗号 Π は, (t(κ), q(κ), ϵ(κ))-IND-CCA-安全であるとよぶ。

q(κ) = 0 のとき、特に (t, ϵ)-IND-CPA-安全とよぶ。特に、t, q = O(poly(κ)), ϵ(κ) = negl(κ) ならば、Π は
IND-CCA-安全（q(κ) = 0 なら IND-CPA-安全）であるという。
次のような試行を考える。
∗

ind-atk-b
ExptΠ,A(κ)(pk, sk) ← K(1κ );1(m0 , m1 , st) ← AO
1 (pk)ct∗ ← E(pk, mb∗ );∗2
b ← AO2 (st, ct )return bit b.
図 2 Security Experiment for IND-ATK-b∗

図 2 のように試行が定義された時、
ind-atk-1(κ) = 1](κ) = 1] − Pr[Exptind-atk-0
Advind-atk
Π,AΠ,A (κ) = Pr[ExptΠ,A(1)が成り立つ。
問題 3

式 (1) を証明せよ。

3 ハッシュ関数（族）
ハッシュ関数族 H = {Hi }i∈I は、（ハッシュ）関数 Hi : {0, 1}∗ → {0, 1}p(κ) （i ∈ Iκ ）の族である。
ハッシュ関数族の安全性として、「ターゲット衝突困難性 (Target Collision Resistance)」、「衝突困難性(Collision Resistance)」を定義する。
定義 4（ターゲット衝突困難性 (TCR)） H = {Hi }i∈I のターゲット衝突困難性を攻撃する敵 A = (A1 , A2 )による攻撃成功確率を、

(x, st) ← A1 (1κ );tcr
AdvH,A (κ) := Pr i ← Iκ ;y ← A2 (Hi , st): x ̸= y and Hi (x) = Hi (y) と定義する。任意の t-時間の敵 A に対しても、Advtcr
H,A (κ) ≤ ϵ を満足するのであれば、H は、(t, ϵ)-TCR であると言う。t(κ) = O(poly(κ)), ϵ(κ) = negl(κ) ならば、H は、ターゲット衝突困難 (TCR) であると言う。

3

78!"# (⋅)'( , … , '+(,0 , ,( )'∗,′( , . . , ,′+

∗

3
12#
(⋅)
' ∗ = 12# (,3∗ ),′6 = !"# ('6 )/図 3 IND-CCA 安全性モデル

定義 5（衝突困難性 (CR)）

H = {Hi }i∈I の衝突困難性を攻撃する敵 A による攻撃成功確率を、

Advcr
H,A (κ) := Pr[i ← Iκ ; (x, y) ← A(Hi ) : x ̸= y and Hi (x) = Hi (y)]と定義する。任意の t-時間の敵 A に対しても、Advcr
H,A (κ) ≤ ϵ を満足するのであれば、H は、(t, ϵ)-CR であると言う。t(κ) = O(poly(κ)), ϵ(κ) = negl(κ) ならば、H は、衝突困難 (CR) であると言う。
仮定の強弱でいうと、「一方向性」=「ターゲット衝突困難性」< 「衝突困難性」であり、ターゲット衝突困
難ハッシュ関数は一方向性関数があれば構成できることが知られているが、衝突困難ハッシュ関数が一方向性関数から構成できるかは知られていない。しかし、現実に使われる SHA2,3 等のハッシュ関数などは「衝突困難性」を当然満たすべき条件としていて、仮に衝突が見つかった場合、危殆化したと判断されるはずである。

4 Cramer-Shoup 暗号
Cramer と Shoup によって提案された Cramer-Shoup 暗号（以下、CS 暗号）を紹介する [CS98, CS02,
CS03]。
■HPS-CS 暗号: KGengroup を付録 付録 B で定義される DDH 仮定を満足するアルゴリズムとする。HPS-CS
暗号 HPS-CS = (K, E, D) は以下のようなアルゴリズムの組である。

• 鍵生成アルゴリズム K:

入力 1κ . 出力 (pk, sk).

1. H ← H;
2. (Gq , q) ← KGengroup (1κ );3. g ← Gq \{1};4. α1 , α2 ← Z/qZ; g1 := g α1 ; g2 := g α2 ;5. z1 , z2 ← Z/qZ; h := g1z1 g2z2 ;6. x1 , x2 , y1 , y2 ← Z/qZ; c := g1x1 g2x2 ; d := g1y1 g2y2 ;7. pk := (Gq , q, g1 , g2 , h, c, d); sk := (pk, z1 , z2 , x1 , x2 , y1 , y2 ).
• 暗号化アルゴリズム E:

入力 (pk, m). 出力 ct.

1. m ̸∈ Gq なら停止。それ以外は次のステップへ。
2. r ← Z/qZ; u1 := g1r ; u2 := g2r ;4

3. e := m · hr ;4. t := H(u1 , u2 , e);
5. v := (cdt )r ;6. ct := (u1 , u2 , e, v).
• 復号アルゴリズム D:

入力 (sk, ct). 出力 m.

1. ct = (u1 , u2 , e, v) ∈ G4q と正しく分解できなければ、m := ⊥ を出力し停止。それ以外は次のステップへ。

2. t′ := H(u1 , u2 , e);′′

3. v ̸= u1x1 +t y1 ux2 2 +t y2 の場合、m := ⊥ を出力し停止。それ以外は次のステップへ。
4. m := e · (uz11 uz22 )−1 を出力。
定理 6

H が (tcr , ϵcr )-CR, KGengroup が (tddh , ϵddh )-DDH を満足するものとする。そのとき、公開鍵暗号

HPS-CS は、(t, Q, ϵ)-IND-CCA-安全であり、t ≤ max{ttcr , tddh − Q · TE (κ)}
Qϵ ≤ 2ϵtcr + 2ϵddh + 2 .
q
ここで、TE (κ) は、|q| = κ のとき暗号化アルゴリズム Epk が暗号文を生成する実行時間とする。また、|q| = κ
より、q ≈ 2κ 。

H が CR 安全、KGengroup が DDH 安全とする。すると、tcr , tddh = O(poly(κ)) のとき、ϵcr , ϵddh = negl(κ)
が成立する。多項式時間のアルゴリズムはオラクルアクセスも多項式回しかできないので、Q = O(poly(κ))として良い。よって、t = O(poly(κ)) なら、ϵ = negl(κ) である。よって、CR 安全ハッシュ関数族と DDH
仮定を満たす群生成アルゴリズムがあるなら、HPS-CS は IND-CCA 安全。

(証明) ゲーム変換によって証明する。ゲーム Gi での敵 A が b∗ を正しく推測できる確率を pi := PrGi [b =b∗ ] とする。
■Game G0 : これは、オリジナルの IND-CCA ゲームである。特にチャレンジ暗号文を作成する暗号化オラ
クル、復号オラクルの手順を改めて記載する。

• 暗号化オラクル Epk :入力 (m0 , m1 ).

出力 ct∗ :∗1. b ← {0, 1};
2. mb∗ ̸∈ Gq なら停止。それ以外は次のステップへ。
∗∗

3. r∗ ← Z/qZ; u∗1 := g1r ; u∗2 := g2r ;∗4. Λ∗ := hr ;5. e∗ := mb∗ · Λ∗ ;6. t∗ := H(u∗1 , u∗2 , e∗ );∗∗7. v ∗ := (cdt )r ;8. ct∗ := (u∗1 , u∗2 , e∗ , v ∗ ).
• 復号オラクル Dsk :入力 ct. 出力 m:∗

1. ct = ct なら、m := ⊥ を出力し停止。
2. ct = (u1 , u2 , e, v) ∈ G4q と正しく分解できなければ、m := ⊥ を出力し停止。それ以外は次のス
テップへ。

5

3. t′ := H(u1 , u2 , e);′′

4. v ̸= u1x1 +t y1 ux2 2 +t y2 の場合、m := ⊥ を出力し停止。それ以外は次のステップへ。
5. m := e · (uz11 uz22 )−1 を出力。
■Game G1 : Game G0 の暗号化オラクルの Step 4 の手順を次のように変更する。他は Game G0 と同じとする。

• 暗号化オラクル Epk :入力 (m0 , m1 ).

出力 ct∗ :1. b∗ ← {0, 1};
2. mb∗ ̸∈ Gq なら停止。それ以外は次のステップへ。
∗∗

3. r∗ ← Z/qZ; u∗1 := g1r ; u∗2 := g2r ;4. Λ∗ := (u∗1 )z1 (u∗2 )z2 ;5. e∗ := mb∗ · Λ∗ ;6. t∗ := H(u∗1 , u∗2 , e∗ );∗7. v ∗ := (cdr )t ;8. ct∗ := (u∗1 , u∗2 , e∗ , v ∗ ).
ここで、u∗1 := g1r , u∗2 := g2r であるので、hr = (g1z1 g2z2 )r = uz11 uz22 。よって、確率変数 ct∗ は、Game G0 とGame G1 で（分布が）同一である。よって、敵 A に与えられる情報の分布は G0 , G1 で同一である。よって、
p0 = p1 .
■Game G2 :Game G1 の復号オラクルの Step 3 の手順を次のように変更する。他は Game G1 と同じとする。

• 復号オラクル Dsk :入力 ct. 出力 m:∗

1. ct = ct なら、m := ⊥ を出力し停止。
2. ct = (u1 , u2 , e, v) ∈ G4q と正しく分解できなければ、m := ⊥ を出力し停止。それ以外は次のステップへ。

3. t′ := H(u1 , u2 , e). もし t′ = t∗ であれば、（復号ではなく）ゲームを中止する。
′′

4. v ̸= u1x1 +t y1 ux2 2 +t y2 の場合、m := ⊥ を出力し停止。それ以外は次のステップへ。
5. m := e · (uz11 uz22 )−1 を出力。
Game G2 の実行時間 t ≤ tcr とする。すると、t′ = t∗ が起きる確率は ϵcr で抑えられる。補題 8 を使うことにより、

p1 − p2 ≤ ϵcrが成り立つ。
■Game G3 : Game G2 の暗号化オラクルの Step 3 の手順を次のように変更する。他は Game G2 と同じとする。

• 暗号化オラクル Epk :入力 (m0 , m1 ).

出力 ct∗ :1. b∗ ← {0, 1};6

2. mb∗ ̸∈ Gq なら停止。それ以外は次のステップへ。
r∗r∗

3. r1∗ , r2∗ ← Z/qZ; u∗1 := g11 ; u∗2 := g22 ;4. Λ∗ := (u∗1 )z1 (u∗2 )z2 ;5. e∗ := mb∗ · Λ∗ ;6. t∗ := H(u∗1 , u∗2 , e∗ );∗7. v ∗ := (cdr )t ;8. ct∗ := (u∗1 , u∗2 , e∗ , v ∗ ).
G2 では、(g1 , g2 , u∗1 , u∗2 ) ← DDH(Gq ) であり、G3 では、(g1 , g2 , u∗1 , u∗2 ) ← G4q であることに注意せよ。
G2 と G3 での A の成功確率の差 p2 − p3 は、DDH 問題の識別確率で抑えられる。実際、A を使った DDH
識別アルゴリズムを次のように作ることができる。

DDH 識別アルゴリズム DA :入力 (g1 , g2 , u∗1 , u∗2 ).

出力 b.

基本 G2 の挑戦者の役割と同じことをするが、鍵生成アルゴリズムと暗号化オラクルを以下のように変更する。暗号化オラクルを次のようにする。

• 鍵生成アルゴリズム K:

入力 (g1 , g2 ). 出力 (pk, sk).

1. H ← H;
2. z1 , z2 ← Z/qZ; h := g1z1 g2z2 ;3. x1 , x2 , y1 , y2 ← Z/qZ; c := g1x1 g2x2 ; d := g1y1 g2y2 ;4. pk := (Gq , q, g1 , g2 , h, c, d); sk := (pk, z1 , z2 , x1 , x2 , y1 , y2 ).
• 暗号化オラクル Epk :入力: (u∗1 , u∗2 ) , (m0 , m1 ).

出力: ct∗ .

1. b∗ ← {0, 1};
2. mb∗ ̸∈ Gq なら停止。それ以外は次のステップへ。
3. Λ∗ := (u∗1 )z1 (u∗2 )z2 ;4. e∗ := mb∗ · Λ∗ ;5. t∗ := H(u∗1 , u∗2 , e∗ );∗6. v ∗ := (cdr )t ;7. ct∗ := (u∗1 , u∗2 , e∗ , v ∗ ).
最後に、A が出力したビット b と b∗ を比べて b = b∗ であれば、D は 1 を出力し、そうでなければ 0 を出力する。
も し 、(g1 , g2 , u1 , u2 ) ∈ DDH(Gq ) な ら 、D は 、Game G2 の 挑 戦 者 と 全 く 同 じ こ と を し て お り 、(g1 , g2 , u1 , u2 ) ∈ G4q なら Game G3 の挑戦者と全く同じことをしている。よって、D の実行時間が tddh 以下
ならば、p2 − p3 ≤ ϵddh となる。D の実行時間は t + Q · TE (κ) であるから、t + Q · TE (κ) ≤ tddh であれば、

p2 − p3 ≤ ϵddh .
■Game G4 : Game G3 の復号オラクルに次のように一つ手順を追加する。他は Game G3 と同じとする。

• 復号オラクル Dsk :入力 ct. 出力 m:∗

1. ct = ct なら、m := ⊥ を出力し停止。
2. ct = (u1 , u2 , e, v) ∈ G4q と正しく分解できなければ、m := ⊥ を出力し停止。それ以外は次のス
テップへ。

7

3. t′ := H(u1 , u2 , e). もし t′ = t∗ であれば、（復号ではなく）ゲームを中止する。
′′

4. v ̸= u1x1 +t y1 ux2 2 +t y2 の場合、m := ⊥ を出力し停止。それ以外は次のステップへ。
5. logg1 (u1 ) ̸= logg2 (u2 ) の場合、（復号ではなく）ゲームを中止する。
6. m := e · (uz11 uz22 )−1 を出力。
Step 5 は、挑戦者が多項式時間では実行できないが仮想的試みとして出来たとしよう。実際、G3 と G4 での事象の確率の違いは純粋に情報量のみの違いになるので、G4 の挑戦者は無限の実行時間を使うと仮定してもかまわない。
今、Game G4 において、秘密情報 (z1 , z2 ) が情報理論的にどの程度敵 A に漏れているか考えてみる。g をGq の任意の生成元とすると、logg (h), α := logg (g1 ), α2 := logg (g2 ) は公開鍵から一意に決まってしまう。
よって、pk が決まると (z1 , z2 ) は、A の視点から見ると

logg (h) = α1 · z1 + α2 · z2(2)という直線の上を動く不定の値となる。A が復号オラクルへ ct = (u1 , u2 , e, v) を送り、平文 m（m ̸= ⊥）を得られたとする。Λ := e/m(= uz11 uz22 ) と定義する。r1 := logg1 (u1 ), r2 := logg2 (u2 ) は、暗号文から一意に決まっているから、一回復号オラクルにアクセスすると A は新たに

logg (Λ) = α1 r1 · z1 + α2 r2 · z2(3)という直線の情報を得る。ところが、Game G4 では、r1 = r2 の場合しか直線 (3) の情報は得られない。その場合、二つは直線は同一になり、復号オラクルからの情報で、(z1 , z2 ) の情報は A にとって一切増えない（(z1 , z2 ) の情報量が減らない）。
一方、チャレンジ暗号文 ct∗ の中の Λ∗ は、（α1 , α2 , r1∗ , r2∗ が既知の）logg (Λ∗ ) = α1 r1∗ · z1 + α2 r2∗ · z2(4)という直線により決まる。(z1 , z2 ) はこの直線と直線 (2) の交点である。(z1 , z2 ) は元々 (Z/qZ)2 から一様ランダムに選ばれているので、直線 (2) が与えられたときは、直線 (2) 上を一様に分布する。直線 (4) と直線 (2)は交点 (z1 , z2 ) の一点で交わっており、(z1 , z2 ) が直線 (2) 上を一様に分布するのであれば、logg (Λ∗ ) も Gq
上を一様に分布する。
よって、Game G4 では、e∗ = mb∗ · Λ∗ は mb∗ の one-time pad である。すなわち、mb∗ と e∗ の分布は完全に独立になってしまうので、b = b∗ となる確率は 1/2 になる。よって、

p4 =

1
2

である後は p3 − p4 を考えれば良い。

G4 で、復号オラクルの Step 5 で、r1 ̸= r2 が起きる事象を事象 F とする。差分確率補題（補題 8）から、
p3 − p4 ≤ Pr[F ]である。次の補題が成り立つ。
補題 7

Pr[F ] ≤ Qq

この補題はあとで証明する。これが成り立ったとすると、p3 − p4 ≤ Q
q . まとめると、t ≤ max{ttcr , tddh −Q · TE (κ) のとき、三角不等式によりAdvind-cca
HPS-CS,A (κ) = |2(p0 − p4 )| ≤ 2

3
∑
i=0

8

|pi − pi+1 | = 2ϵcr + 2ϵddh +

2Q
.
q

以上。
′

′

(証明) [補題 7 の証明] 復号オラクルで、A から来た暗号文 (u1 , u2 , e, v) が、v = ux1 1 +t y1 u2x2 +t y2 でありながら、r1 ̸= r2 のとき、事象 F が起きる。次の式を考える。

 logg (c)α1
 logg (d)   0 logg (v ∗ ) = α1 r1∗
α1 r1
logg (v)α20
α2 r2∗
α2 r2

0α1
α1 r1∗ t∗
α1 r1 t′

 
0
x1
x2 
α2 
 
α2 r2∗ t∗   y1 
α2 r2 t′y2

(5)(logg (c), logg (d), logg (v ∗ )) と行列の要素は、全て公開鍵とチャレンジ暗号文から一意に決まる値であるので情報量はゼロ。よって A に取って既知の値として良い。ct ̸= ct∗ かつ t′ ̸= t∗ より、式 (5) の行列は正則である。
最初の３つの連立一次方程式は４次元空間の中の直線を与え、(x1 , x2 , y1 , y2 ) はその直線上一様に分布している。式 (5) の行列が正則なので、４つ目の方程式が定める超平面とその直線は一点で交わり、logg (v) と交点 (x1 , x2 , y1 , y2 ) は一対一の対応をしているため、式 (5) を満たす logg (v) は Z/qZ 上を一様に分布している。よって、A が v を正しく推測できる確率は高々 1q である。A は復号オラクルに Q 回までアクセスできる
ので、ゲーム中に式 (5) を満たす v を復号オラクルに送ることができる確率は Q
q となる。よって、

Pr[F ] ≤Q.
q以上で補題が証明できた。

参考文献[CS98] Ronald Cramer and Victor Shoup. A practical public key cryptosystem provably secure against
adaptive chosen ciphertext attack. In Hugo Krawczyk, editor, CRYPTO’98, volume 1462 of
LNCS, pages 13–25. Springer, Heidelberg, August 1998.
[CS02] Ronald Cramer and Victor Shoup. Universal hash proofs and a paradigm for adaptive chosenciphertext secure public-key encryption. In Lars R. Knudsen, editor, EUROCRYPT 2002, volume2332 of LNCS, pages 45–64. Springer, Heidelberg, April / May 2002.
[CS03] Ronald Cramer and Victor Shoup. Design and analysis of practical public-key encryption schemes
secure against adaptive chosen ciphertext attack. SIAM Journal on Computing, 33(1):167–226,
2003.

付録 A
補題 8

差分確率補題（再掲載）

A, B, F をある確率空間 (probability space) の事象 (event) とする。このとき、A ∩ F = B ∩ F な

らば、|P r[A] − Pr[B]| ≤ Pr[F ]

9

付録 B

離散対数問題、DH 問題、DDH 問題

B.0.1 巡回群
G を有限群とする（演算は乗法で表す）このとき、⟨g⟩（g ∈ G）は、G の有限可換部分群であり、準同型定
理により、⟨g⟩ の位数と g の位数は一致し（それを q とおく）、

f : x ∈ Z/qZ → g x ∈ ⟨g⟩は同型写像である（Z/qZ は加法で定義された群）。今後、Gq := ⟨g⟩ と書くことにする。我々は、q が素数となるようなものに特に興味がある。Lagrange の定理により、群 Gq の部分群を H とすると、#H|q. q は素数であるから、H は、{1} または Gq のどちらかである。よって、任意の g ′ ∈ Gq \{1} は Gq の生成元であり、⟨g ′ ⟩ = Gq .
具体例 1: 有限体 Fp (= Z/pZ)（p は素数）を考える。有限体の乗法群は巡回群であるので、乗法群 F×
p は
×
×
×
ある生成元 g̃ ∈ F×p が存在し、⟨g̃⟩ = Fp となる。体では、Fp = Fp \{0} であるから、#Fp = p − 1 である。

q を q|p − 1 なる奇素数とする。すると、g := g̃ k （p − 1 = qk ）と置くと、f (x) = g x mod p は、
f : x ∈ Z/qZ → g x ∈ Gq (= ⟨g⟩)の同型写像である。
具体例２: E(Fp ) を、有限体 Fp 上の楕円曲線 E の Fp -有理点から作られる群とする。Hasse の定理により、√√E(Fp ) の位数は p + 1 − 2 p ≤ #E(Fp ) ≤ p + 1 + 2 p である。q|#E(Fp ) なる素数を位数とする P ∈ E(Fp )の作る巡回群を ⟨P ⟩ = Gq と置くと、

f : x ∈ Z/qZ → xP ∈ Gq ⊂ E(Fp )は Z/qZ から Gq への同型写像である。

B.0.2 離散対数問題、DH 問題、DDH 問題
定義 9（離散対数 (Discrete-log (DL)) 問題） Gq を素数位数 q の巡回群（演算を乗法で書くことにする）とする。元 g, h ∈ Gq が与えられたとき、h = g x なる x ∈ Z/qZ を求める問題を Gq 上の離散対数問題という。

h = g x なる x を、x = logg (h) と書く。
定義 10（Diﬃe-Hellman (DH) 問題） Gq を素数位数 q の巡回群（演算を乗法で書くことにする）とする。
y

元 g, h1 , h2 ∈ Gq が与えられたとき、k = g xy = hx2 = h1 なる k ∈ Gq を求める問題を Gq 上の DH 問題という。ここで、x := logg (h1 ), y := logg (h2 ) とする。
別の言い方をすると、g, h1 = g x , h2 = g y から、x, y は教えられずに g xy を計算する問題を DH 問題という。
定義 11（Decisional Diﬃe-Hellman (DDH) 問題） Gq を素数位数 q の巡回群（演算を乗法で書くことにする）とする。Gq の元 g1 , g2 , h1 , h2 ∈ Gq に対して、logg1 (h1 ) = logg2 (h2 ) であるとき、DDH 関係を満たしているという。

DDH(G4q ) := {(g1 , g2 , h1 , h2 ) ∈ G4q | logg1 (h1 ) = logg2 (h2 )}.
DDH 関係か、否かを判定する問題を Gq 上の DDH 問題という。
Gq の元の４つ組の集合 G4q = {(g1 , g2 , h1 , h2 ) | g1 , g2 , h1 , h2 ∈ Gq } とすると、DDH(G4q ) ⊂ G4q .
10

注釈 12

DDH 関係とは、図 4 のように４元のうち３元を選んだとき、最後の１元が DH 問題の解になっている関係と言い直すことができる。

%ℎ"ℎ" = ℎ#+ℎ# = ℎ"+ℎ#)*(ℎ# = !#(ℎ" = !"&&( )*!" = ℎ"( )*!" = ℎ#%!"!# = !"+!#+ )*!" = !#

図 4 DDH 関係の図

KGengroup を次のような確率的アルゴリズムとする。
1. KGengroup はセキュリティパラメータ 1κ を入力として受け取る。
2. |q| = κ となる素数と、q を位数とする巡回群 Gq を選ぶ。
3. (Gq , , q) を出力する。
このアルゴリズムの試行を(Gq , q) ← KGengroup (1κ )と書く。
定義 13（DL 仮定） DL 問題を解くアルゴリズム A の成功確率を
κ
2
x
Advdl
A,KGengroup (κ) := Pr[(Gq , q) ← KGengroup (1 ); (g, h) ← Gq ; x ← A(g, h) : y = g ]と定義する。ある巡回群生成アルゴリズム KGengroup が存在して、いかなる多項式時間アルゴリズムの敵 Aに対しても Advdl
A,KGengroup (κ) = negl(κ) となるとする。このような KGengroup の存在を仮定することを DL 仮定と言う。
定義 14（DH 仮定） DH 問題を解くアルゴリズム A の成功確率を
κ
3
xy
Advdh
A,KGengroup (κ) := Pr[(Gq , q) ← KGengroup (1 ); (g, h1 , h2 ) ← Gq : A(g, h1 , h2 ) = g ]と定義する（ただし x = logg (h1 ), y = logg (h2 )）。ある巡回群生成アルゴリズム KGengroup が存在して、いかなる多項式時間アルゴリズムの敵 A に対しても Advdh
A,KGengroup (κ) = negl(κ) となるとする。このような

KGengroup の存在を仮定することを DH 仮定と言う。
定義 15（DDH 仮定） DDH 関係を判定するアルゴリズム D の成功確率をAdvddhD,KGengroup (κ) := |Pr

[D(Uddh (G4q )) = 1] −Gq ,Uddh (G4q )Pr[D(U (G4q )) = 1]|

Gq ,U (G4q )と定義する。ただし、Gq は、KGengroup (1κ ) の分布に従った確率変数、Uddh (G4q ) は、DDH(G4q ) 上の一様分布に従う確率変数、U (G4q ) は、G4q 上の一様分布に従う確率変数である。ある巡回群生成アルゴリズム KGengroupが存在して、いかなる多項式時間アルゴリズムの敵 D に対しても Advddh
D,KGengroup (κ) = negl(κ) となるとする。
このような KGengroup の存在を仮定することを DDH 仮定と言う。

11

付録 C

ランダムオラクルモデル (Random Oracle Model)

ランダムオラクルモデルとは、攻撃者を含む全てのアルゴリズムがランダム関数にオラクルアクセスできる環境のことを言う。例えばハッシュ関数 H : X → Y をランダム関数とみなすとは、H が全ての関数の集合

Func(X, Y ) = {f : X → Y } からランダムに選ばれたものと考えるということである。ハッシュ関数をランダム関数とみなし、そのハッシュ関数へは誰もがオラクルアクセスできるモデルで暗号方式の安全性を証明したとき、その暗号方式はランダムオラクルモデルで安全という。

C.1 公開鍵暗号の場合
公開鍵暗号 Π で使われるハッシュ関数をランダム関数と扱うと、ランダムオラクルモデルでの IND-CCA
安全性ゲームでの敵 A の試行は、次のようになる。
cca-roExptΠ,A(κ):

H ← Func(pk, sk) ← KH (1κ )DH ,H(m0 , m1 , st) ← A1 sk(pk)b∗ ← {0, 1}; ct∗ ← EH (pk, mb∗ )DH ,Hb ← A2 sk(st, ct∗ )If b = b∗ , return 1 else return 0.
A のアドバンテージは次のようになる。
cca-ro(κ) = 2 Pr[Exptcca
AdvA,Π
Π,A (κ) = 1] − 1 .

!"# (⋅)BC'( , … , '+,(-1 , -( )-′( , . . , -′+,'∗, @+ A@ (, …

H(⋅)

7 (@ ( ),…,7(@+ A)

7 ← Func(=, >)0

図 5 IND-CCA in ROM

12

∗

4
23#
(⋅)
' ∗ = 23# (-4∗ )