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

もし，DDH問題が困難であるならば，ユーザーがある電子現金をただ1回のみ使っている 限り，そのユーザーは誰からも追跡を受けないことを示す．

定理6 ランダムオラクルモデルとDDH仮定の下では，銀行と商店が互いに結託したとして も，ユーザーが電子現金を1回のみ使うならば，その電子現金と支払プロトコルの取引履歴か らユーザーを無視できないアドバンテージで追跡する攻撃者は存在しない．

証明:

以下のような，確率的多項式時間対話型Turing機械({B^∗_i},S^∗,D^∗)が存在するとする．識別者 D^∗は， ACMA & AIAのシナリオに従うとする．つまり，D^{∗ は全ての銀行}{Bi}i と商店S^∗ をcorruptすることができ，

• {Bi}iは，正直なユーザーU0とU1の双方に電子現金を発行する．VbB^∗ は，Ub と発行 プロトコルを行っている間に{B^∗_i}i が得るviewの集合とする．

• U0 とU1 に発行された電子現金のうち，どちらか1つがS^{∗ で使用される．}V_bS∗ は，

Ub に発行された電子現金に関する支払プロトコルを行っている間に，S^{∗ が得る}view とする．

• D^{∗ は，}(V0B^∗,V1B^∗,VbS^∗)が与えられ，b^′を出力する．

({B^∗_i},S^∗,D^∗)は，

Adv_D∗ =|Pr[D^∗(V0B^∗,V1B^∗,VbS^∗)→b]−Pr[D^∗(V0B^∗,V1B^∗,V(1−b)S^∗)→b]|=ϵ を満たすとする． ただし，ϵは無視できないとする．

このとき，({B^∗},S^∗,D^∗)をオラクルとして使って，DDH問題を解くアルゴリズムD^が構成 できることを示す．DH = {(p,g,g^a,g^b,g^ab)|a,b ∈ Zq}}^，R = {(p,g,g^a,g^b,g^c)|a,b,c ∈ Zq}^と し，(p,A,B,C,D)はΠ^{とする．ただし，}A,B,C,D∈ ⟨A⟩^である．X←RY^は，XをY^からラ ンダムに選択して決定することを意味する．D^は，Π←R DH ^であるかΠ←R R^{を見分ける} ことが目的である．Dの構成は次のとおりである．

Step 1. Π =(p,A,B,C,D)が入力されると，Dは，システムパラメータ(p,q,g,h,z)を 次のように決定する．D^{は，入力された} pをそのままシステムパラメータにする．qは

⟨A⟩^{の位数で，}g← Aとする．hは⟨g⟩からランダムに選択し， ランダムにκ ∈Zq を 選択してz←g^κ とする．そして，DはPKIをシミュレートし，{B_i}i と鍵生成プロトコ ルを実行する．

Step 2.D^は，b∈R{0,1}^{を選択する．そして，}D^∗は，U0 とU1をシミュレートして，

{B^∗_i}i，S^∗，D^∗で，発行プロトコルと支払プロトコルを実行する．

Step 3.U0 は，自身のID，L^，msg₀，σU₀ をB^∗₀に送り，発行プロトコルを実行する．

これをrun0 と呼ぶ． もし，B^∗₀ がランダムなビット列rndとσU0 をH1に問い合わせ，

かつb= 0ならば，D^は，z₁ = H1(rnd∥ σU0)← B^κ として回答する．B^∗₀ がrndとσU0

をH1に問い合わせ，かつb=1ならば，D^は，z1 ∈ ⟨g⟩をランダムに回答する．

Step 4. U1 は，自身のIDと，run0 と同じリストL^，msg₁，σU1 をB^∗₀ に送り，発行プ ロトコルを実行する．これをrun₁ と呼ぶ． もし，B^∗₀ がrnd^′ とσU1 をH1 に問い合わ せ， かつb= 1ならば，D^は，z^′₁ =H1(rnd^′ ∥σU1)← B^κ として回答する．B^∗₀ がrnd^′ とσU₁ をH1に問い合わせ，かつb= 0ならば，D^は，z^′₁ ∈ ⟨g⟩^{をランダムに選択して} 回答する．

Step 5. Dは，(ζ, ζ1)= (C^κ,D^κ)と設定し，ランダムにρ,{σ1,i, σ2,i, µi}i, ϵp, µp, ϵ ∈Zq を 選択する．さらに，D ^は，{ωi, δi ∈ Zq|ϵ = ωi +δi modq}i をランダムに選択する．H2

の出力は，

H2



ζ ∥ζ1 ∥g^ρy^ω_1,⁰₀· ∏

j∈L\{0}

y^ω_2,^j_j ∥⊎

i∈L

(g^σ1,iζ₁^δi ∥ h^σ2,iζ₂^δi ∥z^µiζ^δi)

∥z^µpζ^ϵp ∥ L



←ϵ でシミュレートする．そして，e-cash = (ζ, ζ1,{ρi, ωi, σ1,i, σ2,i, µi, δi}i,L)を電子現金と する．

Step 6.D^は，商店S^∗と支払プロトコルを実行し，その電子現金を使用する．もし，D

がランダムなビット列chaをS^∗から受け取ったら，D^は，

H3(z^µpζ^ϵp ∥e-cash∥cha)←ϵp

と設定して，(ϵp, µp)をS^{∗に返す．}

Step 7.D^は，(V0B^∗,V1B^∗,VbS^∗)をD^{∗に入力して}b^′ を受け取る．

Step 8.もし，b=b^′ ならばD^はtrueを出力し，b,b^′ ならばfalseを出力する．

特に断りがない限り，ランダムオラクルは，リストに記録されている問い合わせに対しては対 応して記録されている回答を返し，そうでないものに対してはランダムに回答し，その問い合 わせと回答をリストに記録するとする．上記のように構成したD^は，DDH問題を無視できな いアドバンテージで解くことが出来る．

もし，(p,A,B,C,D)∈ DH ^ならば, log_zz₁ = log_AB= log_CD = log_ζζ1 であるから，その電 子現金は， runb でのみ生成される．実際， ブラインドする成分t1,{t2,i,t3,i,t4,i,t5,i}i は，VbB

を step 5 で生成された e-cash に変形する．他方，run1−b では，圧倒的確率 (1− negl1) で log_zz₁ ,log_ζζ1となるから，e-cashを生成することはできない．つまり，bは，Step 5で生成 したe-cashが，run0 とrun1 のどちらに対応するかを決定している．よって，(V0B^∗,V1B^∗,VS^∗) から正しいユーザーの追跡不可能性を破るD^{∗は，少なくとも確率}(¹₂ +ϵ)(1−negl1)で，正し いbを出力する．

一方, (p,A,B,C,D)∈ R\DH^{であるとき，}run0,run1共に，log_zz1 =log_AB,log_C D=log_ζζ1

が成り立つ．つまり，Step 5で生成されるe-cashには，確率(1−negl2)で，V0B^∗ かV1B^∗ を e-cash に変形できるようなブラインド要素 t₁,{t_2,i,t_3,i,t_4,i,t_5,i}i が存在しない．よって, b は run0,run1とは独立となり，b^′ =bが成り立つ確率は，高々 ¹₂(1−negl2)である．

以上より，

Pr[D(Π)→true|Π∈ DH]≥ (1

2 +ϵ)(1−negl1), Pr[D(Π)→true|Π∈ R\DH]≥ 1

2(1−negl₂)

が成り立つことを示した．次に，D^{のアドバンテージ}ϵ^{′ を評価する．}

|Pr[D(Π)→true|Π←RDH]−Pr[D(Π)→true|Π←R R]|=ϵ^′ (5.9) Π^がRからランダムに選択されているとき，

Pr[Π∈ DH|Π←R R]= 1

q, (5.10)

Pr[Π∈ R\DH|Π←R R]= 1− 1

q (5.11)

が成り立つ．式(5.9)の左辺の第一項より，

Pr[D(Π)→true|Π←R DH]

=Pr[D(Π)→ true∧Π∈ DH|Π←RDH] +Pr[D(Π)→true∧Π∈ R\DH|Π←RDH]

=Pr[D(Π)→ true∧Π∈ DH ∧Π←R DH]/Pr[Π←R DH]

=Pr[D(Π)→ true|Π∈ DH ∧Π←RDH].

式(5.9)の左辺の第二項より，

Pr[D(Π)→true|Π←R R]

=Pr[D(Π)→ true∧Π∈ DH|Π←RR] +Pr[D(Π)→true∧Π∈ R\DH|Π←R R]

=Pr[D(Π)→ true|Π∈ DH ∧Π←RR]·Pr[Π∈ DH|Π←R R]

+Pr[D(Π)→true|Π∈ R\DH ∧Π←R R]·Pr[Π∈ R\DH|Π←RR]

= 1

qPr[D(Π)→ true|Π∈ DH ∧Π←R R] +(1− 1

q) Pr[D(Π)→true|Π∈ R\DH ∧Π←RR]. よって，

|Pr[D(Π)→true|Π←RDH]−Pr[D(Π)→true|Π←R R]| ≥(1− 1

q)(ϵ−negl1−negl2) が示せた．以上で，少なくともアドバンテージ(1− ¹_q)(ϵ−negl₁ −negl₂)でDDH問題を解く アルゴリズムが構成できることを示した．もし，ϵ ^{が無視できないとき，}DDH仮定に矛盾す るため，DDH仮定の下では，無視できないϵ^を持つDは存在しないことが示せた．