



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

1 安全性の根拠となる問題
1.1 RSA 問題
1.1.1 RSA 関数n を n = pq なる相異なる素数 p, q の積とする。このとき、環 Z/nZ の乗法群 (Z/nZ)× の位数はオイラー関数より ϕ(n) = (p − 1)(q − 1) である。全ての a ∈ (Z/nZ)× は、Lagrange の定理より、#⟨a⟩|ϕ(n) である。

⟨a⟩ の位数と a の位数（aλ = 1 となる最小の正の整数 λ）は、準同型定理より Z/λZ ∼= ⟨a⟩ であり等しい。さらに(Z/nZ)× ∼= (Z/pZ)× × (Z/qZ)×であるから、a = (ap , aq ) ∈ (Z/pZ)× × (Z/qZ)× と同一視すると、a の位数 λ は、λ(n) := lcm(p − 1, q − 1)の約数であるから、全ての a ∈ (Z/nZ)× に対して、aλ(n) ≡ 1 (mod n) が成り立つ。
問題 1

位数がちょうど λ(n) となる a ∈ (Z/nZ)× はどんな値か。

定義 2

整数 e を gcd(e, λ(n)) = 1 とし、f(n,e) (x) := xe mod nと定義された関数 fn,e : (Z/nZ)× → (Z/nZ)× を RSA 関数と呼ぶことにする。
補題 3

fn,e は (Z/nZ)× 上の置換（全単射写像）になる。

(証明)• (単射) fn,e (x) = fn,e (y)、すなわち xe ≡ y e (mod n) ならば、x ≡ y (mod n) を示せば良い。
d := e−1 mod λ(pq) とおくと、(xe )d ≡ xed ≡ x1+kλ(n) ≡ x (mod n).
(xe )d ≡ (y e )d (mod n) であるので、x ≡ y (mod n) となる。
• (全射) 任意の y ∈ (Z/nZ)× に対して、x := y d mod n とすると、y = xe mod n である。よって全射。

1.1.2 RSA 仮定
定義 4（RSA 問題） 相異なる素数 p, q の積 n = pq 、gcd(e, λ(pq)) = 1 である奇素数 e(≥ 3)、y ∈ (Z/nZ)×が与えられたとき、xe ≡ y (mod n) なる x ∈ (Z/nZ)× を求める問題を RSA 問題という。

KGenrsa を次のような確率的アルゴリズムとする。
1. KGenrsa はセキュリティパラメータ 1κ を入力として受け取る。

1

2. |pq| = κ となる相異なる素数 p, q を、|p| = |q| かつ、λ(pq) が大きな素数の倍数となるように（ある分布から）選ぶ。ここで、正の整数 x に対して、|x| := ⌊log2 (x)⌋（x をビット列としてみたときの長さ）を表し、λ(pq) := gcd(p − 1, q − 1) とする。

3. gcd(e, λ(pq)) = 1 なる素数 e ≥ 3 を選ぶ。
4. d := e−1 mod λ(pq) を計算する。
5. n := pq として、pk := (n, e) と sk := (pk, d) を出力する。
KGenrsa を RSA 鍵生成アルゴリズムと呼び、このアルゴリズムの試行を(pk, sk) ← KGenrsa (1κ ).
と書く *1 。

RSA 仮定とは次のように定義される。
定義 5（RSA 仮定） KGenrsa を上記のようなアルゴリズムとする。RSA 問題を解くアルゴリズム A の成功
確率を
k
×
d
×
Advow
A,KGenrsa (κ) := Pr[(pk, sk) ← KGenrsa (1 ); y ← (Z/nZ) : A(pk, y) = y ∈ (Z/nZ) .]と定義する。ある鍵生成アルゴリズム KGenrsa が存在して、いかなる多項式時間アルゴリズムの敵 A に対しても Advow
A,KGenrsa (κ) = negl(κ) となるとする。このような鍵生成アルゴリズム KGenrsa の存在を仮定することを RSA 仮定と言う。

RSA 仮定とは、ある鍵生成アルゴリズム KGenrsa が存在して、それにより作られる関数族 fn,e が、一方向性関数であると仮定することと同義である。
特に、任意の t-時間アルゴリズム（の族）A に対して、Advow（KGenrsa によA,KGenrsa (κ) ≤ ϵ であるならば、り導出される）RSA 関数（族）fn,e は (t, ϵ)-OW であるという。
−1fn,e(x) = xd

(mod n)−1を関数 fn,e の落し戸 (trapdoor) とよぶ。
は効率よく計算できる（バイナリー法）。fn,e

定義 6（落し戸付き一方向性関数（One-Way Trapdoor Function）） 落し戸をもつ一方向性関数（族）を、落し戸付き一方向性関数（族）とよぶ。

1.2 離散対数問題、DH 問題、DDH 問題
1.2.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 は素数*1 実際は、e, p, q の選び方にさらなる制限がついているが細かいことは今回は気にしない。

2

であるから、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 への同型写像である。

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

h = g x なる x を、x = logg (h) と書く。
定義 8（Diﬃe-Hellman (DH) 問題） Gq を素数位数 q の巡回群（演算を乗法で書くことにする）とする。元g, h1 , h2 ∈ Gq が与えられたとき、k = g xy = hx2 = hy1 なる k ∈ Gq を求める問題を Gq 上の DH 問題という。
ここで、x := logg (h1 ), y := logg (h2 ) とする。
別の言い方をすると、g, h1 = g x , h2 = g y から、x, y は教えられずに g xy を計算する問題を DH 問題という。
定義 9（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

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

KGengroup を次のような確率的アルゴリズムとする。
1. KGengroup はセキュリティパラメータ 1κ を入力として受け取る。
2. |q| = κ となる素数と、q を位数とする巡回群 Gq を選ぶ。
3. (Gq , , q) を出力する。
このアルゴリズムの試行を(Gq , q) ← KGengroup (1κ )
3

%

ℎ"

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

図 1 DDH 関係の図と書く。
定義 11（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 仮定と言う。
定義 12（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 仮定と言う。
定義 13（DDH 仮定） DDH 関係を判定するアルゴリズム D の成功確率を

Advdh
D,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 仮定と言う。

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

4

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

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

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

2.2 教科書的 RSA 暗号と El Gamal 暗号
2.2.1 RSA 暗号
一方向性落とし戸置換族は, 公開鍵暗号の定義を満たすので、RSA 関数から公開鍵暗号を容易に作れる。鍵生成アルゴリズムを K = KGenrsa とする。暗号化アルゴリズム Epk (m) := fn,e (m) = me mod n（ここで、−1
pk = {n, e}）。復号アルゴリズム Dsk (c) := fn,e(c) = cd mod n（ここで、sk = {pk, d}）。

2.2.2 El Gamal 暗号
El Gamal 暗号 Π = (K, E, D) は次のようなアルゴリズムの組である。それぞれのアルゴリズムの試行は
図 2 になる。ここで、M = Gq 、C = Gq × Gq であり、Epk (m; r) = (g r , m · hr )、Dsk (ct) = c2 /cx1 となる。

(pk, sk) ← K(1κ ).

ct ← Epk (m).

m ← Dsk (ct).

κInput 1 .
(Gq , q) ← KGengroup (1κ );Input (pk, m).

g ← Gq \{1}; x ← Z/qZ;r ← Z/qZ;xr

Input (sk, ct).
Parse ct = (c1 , c2 );h := g ;c1 := g ;k := cx1 ;pk := (Gq , q, g, h);k := hr ;m := c2 /k;

sk := (pk, x);c2 := m · k;

Return (pk, sk).

Return ct := (c1 , c2 ).

Return m.

図 2 El Gamal

2.3 公開鍵暗号の安全性のクラス
公開鍵暗号の安全性は, 攻撃者 (adversary) の解読目標（「部分解読」か「完全解読」等）と, 攻撃者の利用可能な環境（選択平文攻撃, 選択暗号文攻撃）の２つの独立な要素の組み合わせによって定義される。
「解読目標」には, 「一方向性（ one-wayness, 完全解読不可）」, 「識別不可能性（ indistinguishability, いかなる部分
解読も不可）」, 「頑強性（ non-malleability ）」などが存在する。一方, 攻撃者の環境には, 「受動的攻撃（選択平文攻撃 (chosen-plaintext attack) 」, 「非適応的選択暗号文攻撃 (non-adaptive chosen-ciphertext attack

or lunch-time attack) 」, 「適応的選択暗号文攻撃 (adaptive chosen-ciphertext attack) 」などがある。
■識別不可能性 (indistinguishability) 公開鍵暗号が暗号が通信情報を秘匿するものであることを鑑みると, 一
方向性は暗号の安全性を定義するのに十分な概念とは言えない。公開鍵暗号のいかなる部分情報解読も不可で5

あることを示すのに, 次のようなゲームが利用される。

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

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

1. 挑戦者 S は, K を起動して (pk, sk) ← K(1k ) を得た後, 攻撃者 A に pk を与える。
2. 攻撃者 A は, 二つの平文 m0 , m1 ∈ M を出力する。
3. 挑戦者 S は, コイン b ∈ {0, 1} をふり, m0 , m1 のどちらを暗号化するか決める。
4. 攻撃者 A に 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) と呼ぶが, ここでは単に選択暗号文攻撃 (chosen-ciphertext attack) と呼ぶことにする。
■IND-CPA-安全, IND-CCA-安全

以下は, 環境が b を選んだとき, 選択平文（および暗号文）攻撃で攻撃′

者 A がビット b を出力する事象をあらわしている。

Acpa (Epk (mb )) = b′ ⇔(pk, sk) ← K(1k ); (m0 , m1 ) ← A(pk) : A(pk, Epk (mb )) = b′ .
Acca (Epk (mb )) = b′ ⇔(pk, sk) ← K(1k ); (m0 , m1 ) ← ADsk (pk) : ADsk (pk, Epk (mb )) = b′ .
Pbcpa := Pr[Acpa (Epk (mb )) = 1], Pbcca := Pr[Acca (Epk (mb )) = 1] と定義し, 攻撃者 A の Π に対する選択平文（および選択暗号文）攻撃成功確率を
cpa
Advind-cpa− P0cpa |A,Π (k) := |P1
cca
cca
Advind-cca
A,Π (k) := |P1 − P0 |と定義する。上記確率は K, Epk , A（の内部コインに）依存する。
定義 15

ind-cpa

任意の t(k)-時間アルゴリズム（族）の攻撃者 A に対して, 十分大きな全ての k ∈ N で, AdvA,Π (k) ≤ϵ(k) が成立するとき, 公開鍵暗号 Π は, (t(k), ϵ(k))-IND-CPA-安全であるという。
特に t : N → R+ が多項式制限, ϵ : N → R+ が無視できる関数のとき, Π は IND-CPA-安全であるという。
同様に, IND-CCA-安全を定義する。

6

定義 16

攻撃者 A は t(k)-時間アルゴリズムで, 作動時間内に q(k) 回まで復号オラクルにアクセスできるとする。任意の t(k)-時間アルゴリズム（族）の攻撃者 A に対して, 十分大きな全ての k ∈ N で, Advind-cca
A,Π (k) ≤ ϵ(k)が成立するとき, 公開鍵暗号 Π は, (t(k), q(k), ϵ(k))-IND-CCA-安全であるという。ただし, q(k) はセキュリ
ティパラメータが k のときの A の復号オラクル Dsk への質問回数を示す。
特に t : N → R+ が多項式制限, ϵ : N → R+ が無視できる関数, さらに q : N → N が多項式制限であるとき, Π は IND-CCA-安全であるという。

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

3
12#
(⋅)

'∗

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

, ,

+

∗

3
12#
(⋅)

+

(,(/, ,((), … , (,/0 , ,( 0 )'(∗ , … … … , '+∗0,( , . . , ,+,: = !"# (': )5 = 1, … , 89'"∗ = 12# (,3" ∗ ).
図4

複数チャレンジ IND-CCA 安全性モデル

2.4 Blum-Goldwasser 暗号
f : {0, 1}∗ → {0, 1}∗ を一方向性落とし戸付き置換とする（本当は置換の族であるが省略）。b : {0, 1}∗ →{0, 1} を f のハードコア述語とする。関数 G : {0, 1}n → {0, 1}ℓ(n) を()G(x) :=
b(x), b(f 1 (x)), . . . , b(f ℓ−1 (x)) ∈ {0, 1}ℓ7と定義する。すると, pk = {f }, sk = {f −1 }, M = {0, 1}ℓ , CT = {0, 1}n+ℓ , Epk (x; r) := (f ℓ (x), m ⊕ G(x))
iz }| {(ただし f (x) := f (. . . (f ( x) . . . )) で公開鍵暗号が定義できる。復号アルゴリズム
Dsk は, y := f ℓ (x),()
ic = m ⊕ G(x) とすると, Dsk (y, c) := c ⊕ b(f −ℓ (y)), . . . , b(f −1 (y) となる。
定理 17

f が，一方向性落とし戸付き置換で, b が f のハードコア述語であれば, BG 暗号は，CPA 安全な公開鍵暗号である。
この定理は下記の補題から容易に導ける。
補題 18

一方向性置換 f のハードコア述語 b を (t, ϵ)-HC と仮定する。すると, 確率変数 (f (Un ), G(Un )) と(f (Un ), Uℓ )は, (t′ , ϵ′ )-計算量的識別不可で,

t′ (n) = t(n) − (ℓ(n) − 1)τf (n) − τR (n),ϵ′ (n) ≤ ϵ(n)ℓ(n).
である。ここで, Un , Uℓ は, それぞれ {0, 1}n , {0, 1}ℓ 上の一様分布に従って選ばれた独立な確率変数であり,

τf (n) は f を一回実行する計算時間, TR (n) は, n ビットの乱数列の生成時間をあらわす。

3 ディジタル署名
3.1 ディジタル署名の定義
SIG = (KGen, Sign, Vrfy) をセキュリティパラメータ κ ∈ N に依存する三つのアルゴリズムの組とし次のよ
うに定義する：• 鍵生成アルゴリズム KGen: 1κ を入力としてとり、検証鍵と署名鍵 (vk, sk) を出力する確率的多項式
時間アルゴリズム。この試行を (vk, sk) ← KGen(1k ) と書く。

• 署名生成アルゴリズム Sign: 署名鍵 sk と 平文 m ∈ {0, 1}∗ を入力としてとり，署名 σ を出力する確率的多項式時間アルゴリズム。この試行を σ ← Sign(sk, m) と書く。

• 署名検証アルゴリズム Vrfy: 検証鍵 vk, 平文と署名の組 (m, σ) を入力としてとり，承認か拒絶を意味
する 1 ビットを出力する確定的多項式時間アルゴリズム。この試行を b ← Vrfy(vk, m, σ) と書く。
定義 19 SIG = (KGen, Sign, Vrfy) が、十分大きな全ての κ ∈ N に対して、(vk, sk) ∈ KGen(1k )、m ∈ {0, 1}∗ 、

σ ∈ Sign(sk, m) なら、常に Vrfy(vk, m, σ) = 1 を満足するとき、SIG をディジタル署名とよぶ。

3.2 ディジタル署名の安全性のクラス■EUF-CMA 安全性

ディジタル署名 SIG に対する次のような攻撃者 A を考える。A は検証鍵 vk を受け取り, 署名オラクル Signsk に q 回まで平文を送ることができる。署名オラクル Signsk は各質問された平文に正しい署名をそのつど返す。A の署名オラクル Signsk へ質問した平文と対応する署名の集合を

L = {(m1 , σ1 ), . . . , (mq , σq )} とし、平文の集合を特に L(m) = {m1 , . . . , mq } と書くことにする。A が最終的に L(m) に含まれない平文 m∗ への正しい署名 σ ∗ （正しい署名とは, Vrfy(vk, m∗ , σ ∗ ) = 1 なる署名のこと）を出力して来た場合、A の勝ちと定義する。

A が、ディジタル署名 SIG に対する EUF-CMA ゲームに勝つ確率を、A の SIG に対するアドバンテージ

8

euf-cmaと呼び、AdvA,SIG(λ) :=

Pr[(vk, sk) ← KGen(1κ ); (m∗ , σ ∗ ) ← ASignsk (vk) : Vrfy(vk, m∗ , σ ∗ ) = 1 ∧ m∗ ̸∈ L(m)]によって表す。上記確率は, KGen, Sign, A（の内部コイン）に依存する。

!"# (⋅)/0'( , … , '+,( , . . , ,+('∗ , , ∗ )図 5 EUF-CMA 安全性モデル

定義 20（EUF-CMA 安全性） 署名オラクルに q 回までアクセスできる任意の t-時間アルゴリズム（族）の攻撃者 A に対して, 十分大きな全ての κ で, Adveuf-cma
A,SIG (κ) ≤ ϵ が成立するとき、ディジタル署名 SIG は (t, q, ϵ)-EUF-CMA 安全という。特に, t, q = O(poly(κ)) で、ϵ(κ) = negl(κ) であるとき、SIG は EUF-CMA 安全、または選択平文攻撃 (chosen-message attack) に対して存在的偽造不可 (existentially-unforgeable)という。
■sEUF-CMA 安全性

sEUF-CMA ゲームは、EUF-CMA ゲームとほぼ同じだが、A の勝利条件が、L に含まれない平文と正しい署名の組 (m∗ , σ ∗ )（すなわち、(m∗ , σ ∗ ) ∈ L）を出力して来た場合, A の勝ちと定義する。 これは EUF-CMA ゲームの勝利条件より厳しくなっている。A が、ディジタル署名 SIG に対する

sEUF-CMA ゲームに勝つ確率を、A の SIG に対するアドバンテージと呼び、Advseuf-cma
A,SIG (κ) :=Pr[(vk, sk) ← KGen(1n ); (m∗ , σ ∗ ) ← ASignsk (vk) : Vrfy(vk, m∗ , σ ∗ ) = 1 ∧ (m∗ , σ ∗ ) ̸∈ L]によって評価される。上記確率は, KGen, Sign, A（の内部コイン）に依存する。
定義 21（sEUF-CMA 安全性） 署名オラクルに q 回までアクセスできる任意の t-時間アルゴリズム（族）の攻撃者 A に対して, 十分大きな全ての κ で, Advseuf-cma
A,SIG (κ) ≤ ϵ が成立するとき、ディジタル署名 SIG は,(t, q, ϵ)-sEUF-CMA 安全という。特に, t, q = O(poly(κ)) で、ϵ(κ) = negl(κ) であるとき、SIG は sEUFCMA 安全、または選択平文攻撃 (chosen-message attack) に対して強存在的偽造不可 (strongly
existentially-unforgeable) という。

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

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

4.1 署名の場合
現実の署名方式では、署名すべき平文をハッシュ関数という短いデータに圧縮してから署名生成アルゴリズ
ムに入力する場合がほとんどである (hash-then-sign)。署名 SIG のランダムオラクルモデルでの sEUF-CMA
安全性を示すにはそのハッシュ関数 H をランダム関数と扱いつぎのことを証明する。A の SIG に対するラン
ダムオラクルモデルでの sEUF-CMA 偽造成功確率は, Advseuf-cma(κ) :=A,Σ

Pr[H ← Func; (vk, sk) ← KGen(1n ); (m∗ , σ ∗ ) ← ASignsk ,H (vk) : VrfyH (vk, m∗ , σ ∗ ) = 1 ∧ (m∗ , σ ∗ ) ̸∈ L]
H

によって評価される。上記確率は, H, KGen, Sign, A に依存する。A はランダム関数 H をオラクルとして利用できる。

t-時間確率的アルゴリズム A の H オラクルへの質問回数が qh (n) 回, 署名オラクル SignH
sk への質問回数がqs (n) 回とすると、上と同様に署名 SIGH に対する

(t, qh , qs , ϵ)-sEUF-CMA 安全性が定義出来る。同様に,

t, qh , qs が多項式制限で、ϵ が無視できる関数であるとき, SIG はランダムオラクルモデルで sEUF-CMA 安全
という。

/0

!"# (⋅)'( , … , '+,( , . . , ,+9 (, …

1(⋅), 9+ :

1 (9 ( ),…,1(9+ :)('∗ , , ∗ )1 ← Func(7, 8)

図 6 EUF-CMA in ROM

4.2 公開鍵暗号の場合
公開鍵暗号の安全性も同様に定義できる。

5 Full-Domain Hash 署名
F = {f } を落とし戸つき一方向置換族とする。F -FDH 署名 SIG = (KGen, Sign, Vrfy) を次のように定義する。鍵生成アルゴリズム KGen はセキュリティパラメタ κ をとり、落とし戸つき一方向性置換

f : {0, 1}κ → {0, 1}κ を選び、vk := f , sk := f −1 を出力する。(f, f −1 ) ← KGen(1κ ). 署名生成アルゴリズ
ム Sign は、秘密鍵 sk(= f −1 ) と平文 m をとり、fi−1 (H(m)) を出力する。σ ← SignH
sk (m). 署名検証アルゴ

10

BC

!"# (⋅)'( , … , '+,

@(

H(⋅)

'∗

, … , @+ A,
7 (@ ( )∗(-1 , -( )-′( , . . , -′+,

4
23#
(⋅)
' ∗ = 23# (-4∗ )@ )… , 7( +A

7 ← Func(=, >)0

図 7 IND-CCA in ROM

リズム Vrfy は、検証鍵 vk(= f ) と (m, σ) をとり、H(m) = f (σ) の時、1 を出力し、それ以外の時は 0 を出力する。b ← Vrfy(vk, m, σ).
特に RSA 関数を使った場合、RSA-FDH 署名と呼ばれる。
定理 22

落とし戸付き置換族 F が, (t, ϵ)-OW であるならば, F -FDH 署名はランダムオラクルモデルで′(t , qh , qs , ϵ′ )-sEUF-CMA 安全であり,t′ ≤ t − (qh + qs − 1) · (TR (κ) + TF (κ))()ϵ′ ≤ qh + gs · ϵ(n) + 2−κ .
ただし, κ ビットの乱数列の生成時間を TR (κ), f : {0, 1}κ → {0, 1}κ の計算時間を TF (κ) とする。

(証明)
■証明の概要F -FDH 署名を sEUF-CMA ゲームで、ランダムオラクルと署名オラクルへの質問回数がそれ

ぞれ qh (k), qs (k) 回で t′ -時間で走る確率的アルゴリズム ASIG を考える。この ASIG のアドバンテージを上から抑えるために、一方向性置換族 F を攻撃するアルゴリズム AF を ASIG を用いて作ることを考える。AF
は、ASIG を内部で使っているため、AF の成功確率は ASIG のアドバンテージに依存する。一方、AF の走行
時間が t 以内であれば、その成功確率は、仮定により ϵ で抑えられなければいけない。よって、ASIG の走行時間を AF の走行時間が t 以内となるように調整してやれば、ASIG のアドバンテージは、AF の限界 ϵ によって抑えられる。
■AF の構成 AF は, (f, y ∗ ) を入力として, ASIG を使いながら f −1 (y ∗ ) を出力するアルゴリズム。

[アルゴリズム AF ]1. I ← {1, . . . , qh + qs }.
2. qh + qs − 1 個の独立な乱数 x1 , . . . , xI−1 , xI+1 , . . . , xqh +qs ← {0, 1}κ を計算する。
3. リスト L を用意する。初めは L = ∅ である。
4. pk := f とし, ASIG に入力。
5. ASIG がランダムオラクル H に質問してきたとき、（a）リスト L に登録されている平文（質問）であれば、登録されている対応する y を返す。
（b）もし i 回目の新しい質問 mi (1 ≤ i ≤ qh + qs ) である場合、

11

i. i ̸= I であれば、yi := f (xi ) を計算し、yi を答えとして返し、L に (mi , xi , yi ) を登録する。
ii. i = I のときは、yI := y ∗ とし、yI を答えとして返し、L に (⋆, yI ) を登録する。
6. ASIG が署名オラクル SignH
sk に質問してきたとき、（a）H にまだ質問されていない i 回目の新しい質問 mi (1 ≤ i ≤ qh + qs ) である場合、i. i ̸= I であれば、yi := f (xi ) を計算し、xi を答えとして返し、L に (mi , xi , yi ) を登録する。
ii. i = I のときは、アルゴリズムを停止する。
（b）過去にランダムオラクル H に質問した平文である場合、i. その平文が mI と異なる場合は、L に登録されている x を署名として返してやる。
ii. mI であるときは、アルゴリズムを停止する。
7. ASIG が 平文と署名の組 (m∗ , σ ∗ ) を出力したとき、m∗ = mI なら、σ ∗ を出力し、それ以外のときは停止する。
■AF の成功確率の解析

ASIG が m∗ をオラクル H に質問する事象を AskH と書くことにする。また、ASIG

が勝つ事象を Succ(ASIG ) と書くことにする。AF が成功する事象は、(m∗ = mI ) ∧ Succ(ASIG ) が起きる事象である。m∗ = mI が起きるということは、AskH が起きていないといけないので、この確率は

Pr[(m∗ = mI ) ∧ Succ(ASIG ) ∧ AskH] = Pr[(m∗ = mI ) ∧ Succ(ASIG ) | AskH] Pr[AskH]= Pr[m∗ = mI |AskH] · Pr[Succ(ASIG )|AskH] · Pr[AskH]
1=
Pr[Succ(ASIG )|AskH] · Pr[AskH]
qh + qsと展開できる。ここで、AF がコインを振って選んだ I と ASIG が I 番目の質問に署名をし偽造に成功する確率は独立であるので、

Pr[(m∗ = mI ) ∧ Succ(ASIG ) | AskH] = Pr[m∗ = mI | AskH] · Pr[Succ(ASIG ) | AskH]
1を使った。これより、AF の走行時間が t 以内であれば、仮定から AF のと、Pr[m∗ = mI | AskH] = qh +qs

成功確率は ϵ で抑えられるので、Pr[Succ(ASIG )|AskH]P r[AskH] ≤ (qh + qs )ϵである。
事象 Succ(ASIG ) の確率（アドバンテージ）は、Advseuf-cma
ASIG ,SIG (κ) = Pr[Succ(ASIG )|AskH] · Pr[AskH] + Pr[Succ(ASIG )|¬AskH] · Pr[¬AskH]≤ Pr[Succ(ASIG )|AskH] · Pr[AskH] + 2−κと評価できる。ここで２行目は、H に質問せずに H(m∗ ) を正しく出力できる確率は高々 2−κ を使った。

t′ ≤ t − (qh + qs − 1) · (TR (κ) + TF (κ)) とすると、Pr[Succ(ASIG )|AskH] Pr[AskH] ≤ (qh + qs )ϵ を代入できるので、−κ
Advseuf-cma.
ASIG ,SIG (κ) ≤ (qh + qs ) · ϵ(κ) + 2である。よって定理の式を得る。

付録 A

有限体上の楕円曲線

K を標数 chr(K) ≠ 2, 3 なる体とする（標数が 5 以上の有限体、または無限位数の体）。このとき、K 係数の曲線

y 2 = x3 + ax + b
12(a, b ∈ K)

を考える。4a3 + 27b2 ̸= 0 (*) のとき、この曲線を K 上の楕円曲線という（chr(K) = 2, 3 のときは別の式で楕円曲線は与えられる）。(*) の条件は、f (x) = x3 + ax + b が重根を持たないのと同じである。

図8

f (x) = 0 の根が一つ

図9

f (x) = 0 の根が３つ楕円曲線の点 (x, y) ∈ K 2 （K-有理点）を (x, y) ∈ E(K) と書くことにする。K 上の楕円曲線には K-有理点が必ず存在し、（楕円曲線上にはない）特別な点 O を加えた集合を E(K) と書く。E(K) は、下記の演算により O を零元とする加法群になる。P = (x1 , y1 ), Q = (x2 , y2 ) とし P + Q = (x3 , y3 ) を、

x3 := λ2 − x1 − x2 ,と定義する。ただし、

y3 := λ(x1 − x3 ) − y1

{ y −y2

λ :=(P ̸= Q)1x2 −x13x21 +a2y1(P = Q)とする。K = Fq なる有限体とすると、Hasse の定理により、群 E(Fq ) の位数は√√
q + 1 − 2 q ≤ #E(Fq ) ≤ q + 1 + 2 q
であることが知られている。
楕円曲線上の演算は、次のように幾何学的に定義できる。

• y ̸= 0 である K-有理点 P ∈ E(K) を通り、y-軸と平行な直線は、K-有理点 P ′ とのみ交わる。
P + P ′ = O と演算を定義し、P ′ = −P と定義する。ここで、y 2 = x3 + ax + b は、x 軸に対して対象なので、P = (x, y) とすれば、−P = (x, −y) であることがわかる。また、O に対しては O = −O と定義する。

• P, Q ∈ E(K) を通る直線が第３点 R′ で楕円曲線と交わった場合、これも K-有理点 R′ となり、
P + Q + R′ = O と定義することで、R := −R′ = P + Q と定義できる。
• 2P (= P + P ) は、楕円曲線の P での接線を考え、第３点 R′ で交わった場合、2P + R′ = O と定義することで R := −R′ = 2P と定義できる。交わる点がない場合、2P = O と定義する。そのとき

R := O = −O = 2P と定義する。













図 10

P + (−P ) = O



図 11

R=P +Q

13

図 12 R = 2P