提案方式

前で述べたとおり，文献[53]の方式は，ACMA & RAIAに対してのみ安全であった．本節

では，ACMA & AIA.に対して安全な新しい追跡不可能電子現金方式をブラインド多重署名を

guarantee banks   issuing bank   user

{B_j}j∈L\{0}  B₀ U

Verify_pk

U(L,msg, σU) Verify_pk

U(L,msg, σU) ←−−−−−−−−−−−−−−−−^{L,msg,σU,IDU} σU←^SignskU(L,msg) z1← H1(rnd||σ_U) ←−−−−−−−−−−−−−−−−−−−rnd,L,msg,σU,IDU rnd∈R{0,1}^∗

z2← _z^z

1 z1← H1(rnd||σU)

u_j,s_1,j,s_2,j,d_j∈RZq z₂← _z^z

a_j←g^{u j} u₀,s_1,01,s_2,0,d₀∈RZq 

b1,j←g^s1,jz^{d j}₁ a0←g^u0 b_2,j←h^s2,jz^{d j}₂ ^{{a j,}

b1,j,b2,j}j

−−−−−−−−−−−−−−−−−−−−→ b_1,0←g^s1z^d₁⁰ b_2,0←h^s2z^d₂⁰

・Record a←∏

i∈Lai

rnd_,a,{b1,i,b2,i}i

−−−−−−−−−−−−−−−−−→ fori∈ Ldob1,i,b2,i

∈ ⟨? g⟩;

ID_U,σUandz₁ z₁← H1(rnd||σU)

on database. ・Record γ, τ,t1∈RZ^∗q

ID_U,σUandz1 ζ←z^γ,ζ1←z^γ₁,ζ2←_ζ1^ζ

on database. fori∈ Ldo

t2,i,t3,i,t4,i,t5,i, τi∈RZq, β1,i←b^γ_1,ig^t3,iζ^t₁^4,i, β2,i←b^γ_2,ih^t5,iζ^t₂^4,i, ηi←z^τi; α←ag^t1y^t2,0_1,0 ∏

j∈L\{0}y^t_2,^2,_j^j B ←⊎

i∈L(β1,i||β2,i||ηi) ϵ← H2(ζ||ζ1||α||B||z^τ||L) fori∈ Ldo

cj←ej−djmodq ←−−−−−−−−−−−−−−−−−−−−−^{{e j}j} c0←e0−d0modq ←−−−−−−−−−−−−−−−−−−−−−^{ei}i ei←ϵ−t_2,i−t_4,imodq;

rj←uj−cjx2,j r0←u0−c0x1,0modq       modq ^{{c j,r j,}

s1,j,s2,j,d j}j

−−−−−−−−−−−−−−−−−−−→ r←∑

i∈Lrimodq −−−−−−−−−−−−−−−−→^{r,{ci,s1,i,s2,i,di}i} a=^?g^ry^c₁⁰_,0∏

j∈L\{0}y^{c j}_2,j fori∈ Ldo

b1,i

=? g^s1,iz^d,i₁ , b2,i

=? g^s2,iz^d,i₂ ; ρ←r+t₁modq fori∈ Ldo

ωi←ci+t2,imodq, σ1,i←γs_1,i+t_3,imodq, σ2,i←γs2,i+t5,imodq, δi←di+t4,imodq, µi←τi−γδimodq;

図5.1 提案の電子現金方式(発行プロトコル)

使って構成する．提案方式中で用いるブラインド多重署名は，Abe[6]のブラインド署名方式 から構成する．

■前提 簡単のため，システムパラメータをセットアップして各銀行が生成した公開鍵を認可 する，信頼できる第三者機関PKIの存在を前提とする．

{B₀,B₁, . . . ,B_n−1}は，互いに協力して電子現金を発行する銀行の集合とする．各銀行は，個

別の発行鍵，個別の保証鍵，共通のタグ鍵の3種の鍵を持っており，それらの役割は次の通り でである．銀行は，自身の発行鍵とタグ鍵を用いて電子現金を発行する．特に，発行鍵はその 電子現金が発行銀行により発行されたことを保証し，タグ鍵は同じ電子現金を二重使用する不

正なユーザーを発行銀行が追跡できることを保証している．一方，銀行は，他の発行銀行によ り発行される電子現金の保証に保証鍵を利用する．

Uはユーザーで，発行銀行B0*4に口座を持っているとする. U^は，B0といくつかの保証銀 行に対して，電子現金発行の問い合わせを行う．提案方式では，保証銀行はU^{が選択すると} する．L ⊆ {0,1, . . . ,n−1}はU によって選ばれた銀行のIDのリストとし，a||bはビット列a とbの連結とし，

⊎

i∈{0,...,n−1}

(β1,i||β2,i||ηi)=β1,0||β2,0||η0||. . .||β1,n−1||β2,n−1||ηn−1

とする．ここで，各参加者は，鍵生成プロトコルを連続的に行うとする．各ユーザーは，

適応的選択メッセージ攻撃に対して存在的偽造不可能 (EUF-ACMA)[50] である署名方式 (Gen,Sign,Verify)を使うとする．

5.3.1 初期設定

PKIは，セキュリティパラメタkで確率的多項式時間アルゴリズムを実行して，システムパ ラメータ(p,q,g,h,z)を生成する．ただし，pとqはq|p−1を満たす大きな素数で，gは位数 qの乗法巡回群⟨g⟩ ⊆ Z^∗p の生成元で，ランダムにh,z∈ ⟨g⟩は選択されているとする．もし，

h,z=1ならば，PKIはそのパラメータを捨て，新しいパラメータを設定する．また，PKIは，

次の3種のハッシュ関数H1 :{0,1}^∗ → ⟨g⟩^，H2,H3 :{0,1}^∗ →Zq を決定する．

5.3.2 鍵生成プロトコル

各銀行 Bi(i = 0,1, . . . ,n−1)は，秘密鍵 x1,i,x2,i ∈R Zq をランダムに選択して，発行公開鍵 y_1,i ←g^x1,i mod pと保証公開鍵y_2,i ← g^x2,i mod pを計算する．次に，B_i は，ZKIP^*5[84]を用 いて，それら公開鍵に対応する秘密鍵の知識x1,i =log_gy1,iとx2,i =log_gy2,i をPKIに示す．も し，ZKIPが正しく完了したら，PKIはその公開鍵を登録する．Bi の公開鍵は(y1,i,y2,i)であ り， 秘密鍵は(x_1,i,x_2,i)である．各ユーザーU^は，(pk_U,sk_U)←Genを実行し，自身の公開 鍵pk_U とIDID_U をPKIに登録する．

*4 0をユーザーが口座を持っている銀行のインデックスとしても，一般性を失わない．

*5ZKIPを用いなければ，不正な公開鍵を登録することで，不正な銀行は多重署名を偽造することが出来る．詳細 は，文献[72]を参照すること．

5.3.3 発行プロトコル

L= {0; j, . . . ,k}は，発行プロトコルに参加する銀行のIDのリストとする．ただし，k≤n−1

であり，0は発行銀行のIDで，{j, . . . ,k}^{は保証銀行の}IDである．以降では，特に断りがない 限り，すべての代数的演算はZp 上で行われるものとする。図5.1は，発行プロトコルの処理 を表している．

Step 1.ユーザーU^は，ID_U，msg，発行銀行B0のIDと 保証銀行{Bj}j のIDを含む リストL^，σU ←Sign_skU(L,msg)を発行銀行B0 に送る．

Step 2.もし，Verify_pk

U(L,msg,σU)→trueかつσU がB0のデータベースに記録されて いなければ，以下の処理を行う．B₀ は，ランダムなビット列rnd∈ {0,1}^{∗を選択し，タ} グ鍵z1 ← H1(rnd∥σU)とz2 ←z/z1 を計算する．B0は，銀行{Bj}j∈L に，電子現金の 保証のリクエストとID_U，rnd，L^，msg，σU を送る．z1，σU，ID_U は，B0.のデータ ベースに記録される．

Step 3. もし，Verify_pk

U(L, msg, σU) → trueかつ σU が Bj のデータベースに記録さ れていなければ，各 Bj は次の処理を実行する．Bj は，タグ鍵z1 ← H1(rnd ∥ σU)と z₂ ←z/z₁ を計算する．そして，B_j は，ランダムにu_j,s_1,j,s_2,j,d_j ∈Zq を選択して，コ ミットメントaj ← g^uj，b1,j ← g^s1,jz^d₁^j とb2,j ← h^s2,jz^d₂^j. を計算する．Bj は，それらの コミットメントをB0に送り，z1，σU，ID_U をデータベースに記録する．

Step 4. B₀ は，u₀,s_1,0,s_2,0,d₀ ∈ Zq をランダムに選んで，コミットメント a₀ ← g^u0， b1,0 ← g^s1,0z^d₁⁰，b2,0 ← h^s2,0z^d₂⁰ を計算する．B0 が全ての保証銀行から{aj,b1,j,b2,j}j を 受け取った時，B0 は，a ← ∏

i∈Lai を計算する．そして，これらのコミットメント (a,{b_1,i,b_2,i}i)とrndをU.に送る．

Step 5. U ^は，b_1,i,b_2,i ∈ ⟨g⟩が成り立つか否かを検査する．もし，成り立たなければ，

Uは失敗を出力する．成り立てば，U^も，z1 ← H1(rnd∥ σU)を計算する．U ^は，ラ ンダムにγ ∈Zq を選択し，それを用いて，ブラインドしたタグ鍵ζ ← z^γ,ζ1 ←z^γ₁ and ζ2 ← _ζ^ζ₁ を計算する．Uは，ランダムに選択したt₁,{t_2,i,t_3,i,t_4,i,t_5,i}i∈L ∈R Zq を用いて，

コミットメントa,{b1,i}i∈L，{b2,i}i∈L を α←ag^t1y^t₁²_,^,₀⁰ ∏

j∈L\{0}

y^t₂²_,^,j_j, β1,i ← b^γ_1,ig^t3,iζ₁^t4,i, β2,i ←b^γ_2,ih^t5,iζ₂^t4,i

に変形する．そして，Uは，ランダムに選択した{τi ∈RZq}i∈Lを使って，コミットメン トηi ←z^τi を計算する．B ← ⊎

i∈L(β1,i ∥β2,i ∥ηi)とする．U^{は，ランダムに}τ∈Zq を

選択し，ϵ ← H2(ζ ∥ζ1 ∥α∥ B ∥z^τ ∥ L)とチャレンジ{e_i ← ϵ−t_2,i−t_4,i modq}i∈L.を 計算する．最終に，U ^は，{e_i}i をB₀ に送る．

Step 6. B0は，c0 ←e0−d0 modqとして，回答r0 ←u0−c0x1,0 modqを計算し，{ej}j

を{Bj}j に送る．

Step 7. 各 B_j は ，c_j ← e_j − d_j modq，r_j ← u_j − c_jx_2,j modq を 計 算 し ，B₀ に (cj,rj,s1,j,s2,j,dj)を返す．

Step 8. B0は，r ←∑

i∈Lri modqを計算する．そして，B0 は，回答(r,{ci,s1,i,s2,i,di}i) をU^に送る．

Step 9.U は，受け取った回答が以下の等式を満たすか否かを検査する．

a=^? g^ry^c₁⁰_,0 ∏

j∈L\{0}

y^c₂^j_,j, (5.1)

for i∈ Ldo b_1,i =^? g^s1,iz^d₁ⁱ, b_2,i =^? h^s2,iz^d₂ⁱ. (5.2) もし，式(5.1)，式(5.2) を満たすならば，U ^{は，その回答を}ρ ← r+t1 modq, ωi ← ci+t2,i modq，σ1,i ← γs1,i+t3,i modq，σ2,i ← γs2,i+t5,i modq，δi ←di +t4,i modq と変形する．そして，U^は

µi ←τi−γδi modq (5.3)

を計算し，(ρ,{ωi, σ1,i, σ2,i, µi, δi}i∈L)が次の式(5.4)を満たすか否かを検査する．

B ←⊎

i∈L

(

g^σ1,iζ₁^δi ∥ h^σ2,i (ζ

ζ1

)δi

∥z^µiζ^δi)

ω0 +δ0

=? · · ·=^? ωn+δn

=? H2

(ζ ∥ζ1 ∥ g^ρy^ω_1,0⁰ ∏

j∈L\{0}

y^ω_2,i^j ∥ B ∥z^τ ∥ L)

(5.4)

もし，式(5.4)が成り立つならば，U^は，

e-cash←(ζ, ζ1, ρ,{ωi, σ1,i, σ2,i, µi, δi}i,L) とし，(e-cash, τ, γ)をUのデータベースに記録する．

5.3.4 支払いプロトコル

U^{が電子現金}(ζ, ζ1, ρ,{ωi, σ1,i, σ2,i, µi, δi}i,L)を商店Sで使う場合，次の処理を行う．

Step 1.U ^{は，電子現金}e-cashをS^に送る．

Step 2.S^{は，チャレンジ}cha∈ {0,1}^{∗ を選択し，}chaをU^に送る．

Step 3.U ^は，ϵp ← H3(z^τ∥ e-cash∥cha)とµp ←τ−ϵpγmodq,を計算し，(µp, ϵp)を S^に送る．

Step 4.Sは，次の式(5.5)と式(5.6)が成立するか否かを調べる．

B ←⊎

i∈L

(

g^σ1,iζ₁^δi ∥h^σ2,i (ζ

ζ1

)_δi

∥z^µiζ^δi )

ω0+δ0

=? · · ·=^? ωn+δn

=? H2



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

j∈L\{0}

y^ω_2,^j_i ∥ B ∥z^µpζ^ϵp ∥ L



 (5.5)

ϵp

=? H3(z^µpζ^ϵp ∥e-cash∥cha) (5.6)

どちらの式も成立する場合，S ^{は，サービスや商品を}U に提供し，使用された電子現金 e-cashとその取引履歴(cha, µp, ϵp)をデータベースに記録する．

5.3.5 清算プロトコル

最後に，Sは，使用済み電子現金とその取引履歴を発行銀行 B0 に送る．もし，その電子現 金と取引履歴の組がB₀のデータベースに記録されていなければ，B₀ は，式(5.5)と式(5.6)が 成り立つか調べ，成り立った場合，現金をSに送り，その電子現金と取引履歴を記録する．も し，同じ組が記録されていれば，同じ電子現金を不正に二回以上にわたって清算しようとした と判断し，式(5.5) と式(5.6)が成り立たなければ不正な電子現金であると判断し，共に換金 を拒否する．清算後，B₀ は，データベースを検査し，同じ電子現金がデータベース上に無い か（つまり，二重使用が無いか）を検査する．もし，二重使用を見つけたら，B0は不正なユー ザーを追跡^*6し，被害を受けた金額を請求したり，そのユーザーと以降の取引を停止するなど する．

ドキュメント内 形式検証を活用した暗号システムの安全性証明技術 花谷 嘉一 (ページ 98-103)