不正なユーザーの追跡可能性

5.4.4 (l , l + 1) - 偽造不可能性

ランダムオラクルモデルにおいて，提案方式はACMA & AIAに対して(l,l+1)-偽造不可 能であることを示す．証明は，提案方式の電子現金の偽造問題を，一人の署名者によって発行 されるブラインド署名[6]の偽造問題に帰着することで行う．つまり，Abeのブラインド署名 [6]の署名者の公開鍵(p,q,g,h,y,z)と対応する署名オラクルOΣ が与えられたとき，提案の電 子現金方式に対する偽造者FM を利用して，ブラインド署名[6]の偽造者が構成できることを 示す．F ^{は，ランダムオラクル}H1,H2 と署名オラクルOΣ にアクセスすることができ，FM

は，ランダムオラクルH₁^∗,H₂^∗,H₃^{∗ と銀行オラクル}{B_i}i ，商店オラクルS^{， 信頼できる第三} 者機関 PKIにアクセスすることが出来る．FM が呼び出すすべてのオラクルは，F ^がシミュ レートする．

Abeのブラインド署名は，ランダムオラクルモデルにおいて，離散対数問題仮定の下で偽造 不可能であることが証明されている[6]ので，上述の帰着は，提案方式の電子現金もまた偽造 不可能であることを示している．

補題10 提案方式では，F ^がFM が登録した公開鍵に対応するn−1個の秘密鍵を入手できる 確率は，少なくとも(1− ¹_q)ⁿ⁻¹ である．

証明:

偽造者FM は， 任意の鍵の組(pk^∗,sk^∗)を生成し，pk^∗をcorruptされた銀行B^∗の公開鍵とし てPKIに登録することが出来る．FM が確率ϵ^′で pk^∗を登録するとき，ZKIP[84]の健全性よ り，F ^は，FM をrewindすることで，少なくとも確率(1− ¹_q)ϵ^{′2 で} sk^∗ を計算できる．ZKIP の健全性より，sk^∗ の知識なしでは，FM は，確率ϵ^′ = ¹_q (negligible)でしか pk^∗ をPKIに登 録することが出来ない．よって，pk^∗を無視できない確率で登録するFM は，対応するsk^∗を 知っているとし，ZKIPを適切に(ϵ^′ = 1)実行するとする．つまり，FM が登録した公開鍵に 対応するn−1個の秘密鍵をF が入手できる確率は，少なくとも(1− ¹_q)ⁿ⁻¹ である．

定理8 離散対数問題が困難ならば，ランダムオラクルモデルにおいて，提案方式は，ACMA

& AIAに対して(l,l+1)-偽造不可能性を満たす．

証明:

提案の電子現金方式には，次の2通りの偽造が考えられる．

• ^発行銀行B₀ をターゲットとした偽造．

• ^保証銀行B_j をターゲットとした偽造．

我々の証明は，これら両方の攻撃に対するものである．いずれの場合も，もし，FM が無視 できない確率で電子現金の(l,l+1)-偽造に成功するならば，Abeのブラインド署名に対する (l,l+1)-偽造者F もまた，無視できない確率で偽造に成功することを示す．

まず，B₀に対する偽造が不可能であることを示す．FM は，B₀に対する偽造を行うとする．

簡単のため，B0 を除くすべての銀行とすべての商店は，FM にcorruptされているとする．ϵ0

は，FM がB0 が発行した電子現金の(l,l+1)-偽造に成功し，corruptされた商店でその使用に 成功する確率とする．

■初期設定: 公開鍵(p,q,g,h,y,z)より，F は電子現金方式の初期設定を行う．

Step 1.F ^は，(p,q,g,h,z)をシステムパラメータに設定する．

Step 2. F は，攻撃対象となる銀行B₀を予測し，B₀ の公開鍵をy_1,0 ← y y_2,0 ← g^x2,0 とし，対応する秘密鍵を x2,0 ∈RZq と設定する．

Step 3.FM は，corruptした銀行の公開鍵を生成する． しかし，FM は，ZKIPを用いて PKIに公開鍵を登録しなければならない．そのため，F ^は，ZKIPをrewindすること で，銀行の秘密鍵を抽出することができる．

Step 4.FM は，ユーザーの公開鍵をPKIに登録する，

■電子現金と取引履歴の偽造: FM から電子現金の発行の問い合わせがあった場合，各オラク ルの回答を次のようにシミュレートする．

• H₁^{∗のシミュレーション}:H₁^∗がrnd∈ {0,1}^∗とσU を入力として受け取った時，H₁^∗は，

rndをH1 に転送する．H1 が回答を返したら，H₁^{∗ はそれを出力する．}

• H₂^{∗ のシミュレーション}:H₂^∗は，(ζ ∥ζ1 ∥α∥ ⊎

i∈L(β1,i ∥ β2,i ∥ηi)∥z^τ ∥ L)を入力とし て受け取った時，

– (ζ ∥ζ1 ∥α∥⊎

i∈L(β1,i ∥β2,i ∥ηi)∥z^τ ∥ L)<H₂^∗-listの場合: H₂^∗は，m∈ {0,1}^∗をラ ンダムに選択し，(ζ||ζ1||α||β1,0||β2,0||η0||m)をH2 に送る．H2 が回答を返したとき，

H₂^∗ はそれを出力し，入力とmとその回答をH₂^∗-listに記録する．

– (ζ ∥ζ1 ∥α∥ ⊎

i∈L(β1,i ∥β2,i ∥ηi)∥z^τ ∥ L)∈ H₂^∗-listの場合:H₂^{∗は記録している回答} を返す．

• H₃^{∗ のシミュレーション}:H₃^∗は，(η||e-cash||cha)を入力として受け取ったら，

– (η||e-cash||cha) < H₃^∗-list の 場 合: H₃^{∗ は ，}ϵp ∈ Zq を ラ ン ダ ム に 選 択 し ， (η||e-cash||cha)とϵp の組をH₃^∗-listに記録し，ϵpを出力する．

– (η||e-cash||cha)∈ H₃^∗-listの場合:H₃^∗は，対応して記録されている回答を出力する．

• B0 のシミュレーション:

Step 1. B₀が銀行のリストL,msg,σU，ID_U をFM から受け取った時，B₀は，σU

が正しい署名であるかを検査する．σU が正しいとき，B0 はm ∈ {0,1}^{∗ をランダ} ムに選択し，メッセージmに対する署名を署名オラクルOΣ に問い合わせ，コミッ トメント(a₀,b_1,0,b_2,0,rnd)を受け取る．

Step 2. B0 は，保証のために，保証銀行にrnd，L,msg, σU，ID_U に送り，それら から{aj,b1,j,b2,j}j∈L\{0} を受け取る．

Step 3. B₀ は， 発行プロトコルに従ってa← ∑

ia_i を計算し，(a,{b_1,i,b_2,i}i, rnd)を FM に送って，{e_i}i をFM から受け取る．

Step 4. B0 は，e0 をOΣに送り，署名(r0,c0,s1,0,s2,0,d0)を受け取る．そして，B0

はej を各保証銀行 Bj に送る．

Step 5. B₀ は，{r_j,c_j,s_1,j,s_2,j,d_j}j∈L\{0} を各B_jから受け取る．

Step 6. B0 は，発行プロトコルに従ってr を計算し，ブラインドされた電子現金

(r,{ci,s1,i,s2,i,di}i)をFM に送る．

もし，F ^がB0 のシミュレートに成功したら，FM は，(l,l+1)-偽造の結果の電子現金と，FM

とcorruptされたS^∗が，(l,l+1)-偽造された電子現金を使って支払プロトコルを実行した結果 の取引履歴の組{(ζ^k, ζ₁^k, ρ^k,{ω^k_i, σ^k_1,i, σ^k_2,i, µ^k_i, δ^k_i}i∈L^k,L^k),cha^k, ϵ^kp, µ^kp}^l_k=1^{+1 を無視できない確率で} 返す．

電子現金からブラインド署名への変換: (l,l+ 1)-偽造された電子現金から，Abeのブライン ド署名[6]の(l,l+1)-偽造署名を得る方法を以下に示す．k = 1,2, . . . ,l+1に対して，F ^は，

(ρ^k,{ω^k_i}i)と 他の銀行の秘密鍵{x2,j}j∈L\{0} を使って，

ρ˜^k ←ρ^k+ ∑

j∈L\{0}

ω^k_jx2,j modq (5.12)

を計算できる．よって，F ^は，OΣ の署名{(

ζ^k, ζ₁^k,ρ˜^k, ω^k, σ^k₁, σ^k₂, µ^k, δ^k,m^k)

}^l+1_k=1 ^の(l,l+1)-偽造 に成功する．

■評価: F の成功確率を評価する．

F が初期設定フェーズで攻撃対象の予測に成功する確率は，少なくとも1/nである．補題 10より,F ^がcorruptされた銀行の秘密鍵を手に入れる確率は，少なくとも(1− ¹_q)ⁿ⁻¹である．

十分に大きなqに対して，

( 1− 1

q )_n−1

>

( 1− 1

q )q

≥ 1 e

が成り立つ．ただし，eは ネピアの定数である．

よって，F ^が(l,l+1)-偽造の出力に成功する確率ϵ1 は，

ϵ1 ≥ ϵ0

en である．

次に，偽造銀行に対する偽造不可能性を証明する．その手順は，上記の手順とほとんど同じ である．初期設定フェーズ二おいて、F ^{は攻撃対象となる銀行}Bj を予測し，その保証公開鍵 をy_2,j = yと設定する．他の鍵は，上記の手順と同様に決定する．その他の手順は上記と同様 に行う. もし，攻撃対象の予測が正しければ，F ^は(l,l+1)-偽造に成功する．

よって，もし，無視できない確率ϵ0 で電子現金のに成功するFM が存在すれば，無視できな い確率でAbeのブラインド署名の偽造に成功するF が存在することを示した．しかし，Abe のブラインド署名は，離散対数問題が困難ならば偽造不可能であることが証明されているた め，そのような F は存在しない．よって，離散対数仮定とランダムオラクルモデルの下で，

FM が存在しないことを示せた．

発行プロトコルの実行ごとにUの署名が必要であるから，次の定理が成り立つ，

定理9 署名方式がEUF-ACMA安全であるとき，ユーザーが電子現金の発行を依頼したこと のある銀行のリストLに含まれる銀行のうち，少なくとも一つの銀行が正直に振る舞えば，他 のすべての銀行が結託したたとしても，ユーザーが電子現金の発行に同意しない限り，発行プ ロトコルを正しく実行することはできない．

定理5から定理9より，提案方式は，ランダムオラクルモデルにおいて，DDH問題が困難 ならば安全である．