プロトコル - 匿名性を強化した証明書方式 - 電子商取引の高セキュリティ化に関する研究

5.3 匿名性を強化した証明書方式

5.3.2 プロトコル

プロトコルCT⁺では，id₍_O_i_,G₎を検証者に与え，

C₍U,O_i)E₍_U,Oi₎ ≡gG_Ix_U

hG_Is₍_U,Oi₎

dG_Iid₍_Oi,G₎

fG_I (modnG_I)

P₍_U,O_j₎ ≡g_G_J^x^Uh_G_J^s⁽^U,Oj⁾ (mod n_G_J)

を同時にみたす，C₍_U,O_i₎, E₍_U,O_i₎, x_U, s₍_U,O_i₎, s₍_U,O_j₎の知識証明をおこなうことで，P₍_U,O_j₎に対応するユーザのO_iへの登録を示すことができ，プロトコルCT⁻ではid₍_O_i_,G₎を検証者に与えず，C₍_U,O_i₎, E₍_U,O_i₎, x_U, s₍_U,O_i₎, s₍_U,O_j₎ に加えてid₍_O_i_,G₎の知識証明をおこなう．

Step 1. 機関管理者M_G ∈Gは，p_G := 2p_G+ 1かつq_G := 2q_G + 1が素数となるようなn/2ビットの素数p_G, q_Gを選択し，nG := pGqGを計算する．また，

dG, eG, fG, gG, hG, vG∈R Z^∗n_G2を選択し，XG:= (pG, qG)をグループの秘密鍵，

YG:= (nG, dG, eG, fG, gG, hG, vG)をグループの公開鍵とする．

Step 2. 各組織Oiは，x₍O_i,G) ∈RΓに対してy₍_O_i_,G₎:=gGx₍_Oi,G₎

modnG を計算し，

y₍_O_i_,G₎をグループGへの登録鍵とする．

Step 3. ユーザUは，システム内で用いる秘密鍵としてxU ∈Γを選択し，保管し

ておく．

仮名生成プロトコル P G

仮名生成プロトコルP Gは，

P GU(x_U), X (YG)[U(s₍_U,X₎)](P₍_U,X₎)

であらわされる．上記は，P GはUとX ∈ {O ∈G, M_G∈G}の対話によっておこなわれ，これは，Uによる入力x_Uと共通入力YGから，Uへs₍_U,X₎をプライベート出力し，P₍U,X)をUとXへ共通出力することを意味する．また，P Gは出力P₍_U,X₎ が正しい型であること，即ちx_U ∈Γ, s₍_U,X₎ ∈∆を用いてP₍_U,X₎ =g_G^x^Uh_G^s^(U,X) にあらわされることを保証する．

プロトコルP Gは以下のように構成される:

Step 1. U はr₁ ∈R ∆, r₂, r₃ ∈R {0,1}²ⁿ に対し，c₁ :=d_G^r¹e_G^r², c₂ :=d_G^x^Ue_G^r³ を計算し，それらをXに送る．

P K²{(α, β, γ, δ) : c₁ =d_G^αe_G^β ∧c₂ =d_G^γe_G^δ} によって，c₁, c₂が正しく生成されていることを証明する．

Step 2. Xはr∈R ∆を選択し，U に送信する．

Step 3. U は，s₍U,X) := (r₁ +r (mod 2^∆⁺¹ + 1))−2^∆ + 1と˜s =

r₁+r 2^∆+1−1

を計算し，P₍U,X) := g_G^x^Uh_G^s^(U,X) を仮名とする．また r₄ ∈R {0,1}ⁿ に対し

c₃ :=d_G^s^˜e_G^r⁴とP₍_U,X₎をXに送信し，それが正しく生成されたことを以下のP K²によって証明する:

P K²{(α, β, γ, δ, ε, ζ, ϑ, ξ) : c₁ =dGα

eGβ

∧ c₂ =d_G^γe_G^δ

∧ c₃ =d_G^εe_G^ζ

∧ P₍_U,X₎ =g_G^γh_G^ϑ

∧ (c₁d_G^r⁻²^∆⁺¹)/(c₃²^∆+1⁺¹) =d_G^ϑe_G^ξ

∧ γ ∈Γ∧ϑ ∈∆}.

Step 4. Xは仮名リストにP₍_U,X₎を保管する．

Step 5. U はP₍_U,X₎の生成に用いた秘密情報s₍_U,X₎とP₍_U,X₎をXの登録情報として秘密に保管する．

グループ登録証明書発行プロトコル CIG

CI_Gは，機関管理者M_G∈Gがグループ登録証明書を発行するのに用いられ，

CI_GU(x_U, s₍_U,G₎), M_G(XG) (YG, P₍_U,G₎) C₍U,G)

であらわされる．CIGはU によるプライベート入力x_U, s₍_U,G₎と，MGによるプライベート入力XG，共通入力YG, P₍_U,G₎に対して，P₍U,G) ∈ P GU, M_G に対する証明書 C₍U,G) を出力する．この証明書C₍U,G) は仮名P₍_U,G₎ に対して C₍_U,G₎ ≡ (P₍_U,G₎f_G)¹^/E^(U,G) (modn_G)をみたす(E₍_U,G₎, C₍_U,G₎)の組であらわされる．

プロトコルCI_Gは，以下のように構成される:

Step 1. ユーザUはP K²{(α, β) : P₍_U,G₎ =g_G^αh_G^β}によってM_Gのデータベースに登録されているP₍_U,G₎に対応するユーザであることを証明する．

Step 2. 機関管理者M_Gは素数E₍_U,G₎∈R Λを選択し，C₍_U,G₎:= (P₍_U,G₎f_G)¹^/E^(U,G) mod n_Gを計算する．またUにグループ登録証明書として(E₍_U,G₎, C₍_U,G₎) を送る．

機関管理者M_GはC(U,G) = (E₍_U,G₎, C₍_U,G₎)をそれに対応する仮名P₍_U,G₎とともに保管する．

Step 3. U はC₍_U,G₎^E^(U,G) ≡ P₍_U,G₎f_G (modn_G) かつE₍_U,G₎ ∈ Λであるかどうかを検証し，正しければC(U,G) = (E₍_U,G₎, C₍_U,G₎)をグループGの登録証明書として保管する．

グループ登録証明プロトコル CS_G

CSGは，ユーザU が検証者V にグループGへの登録を証明するのに用いられる．これは

CS_GU(C(U,G), x_U, s₍_U,G₎), V (YG) {0,1}

であらわされ，証明者U がC₍U,G) ∈ CI_GU, M_G を保持するとき圧倒的確率で1 を，そうでないときは0を出力する．

プロトコルCS_Gは以下のように構成される:

Step 1. U はr₁, r₂ ∈R {0,1}²ⁿを選択し，c₁ := C₍_U,G₎e_G^r¹, c₂ := e_G^r¹d_G^r² を計算し，検証者V にc₁, c₂を送る．

Step 2. U は以下のP K²によって検証者V に登録証明をおこなう:

P K²{(α, β, γ, δ, ε, ζ, ξ) : f_G=c₁^α/g_G^βh_G^γe_G^δ

∧ c₂ =e_G^εd_G^ζ

∧ 1 =c₂^α/e_G^δd_G^ξ

∧ α∈Λ∧β ∈Γ∧γ ∈∆}.

検証機関に対するグループ登録証明プロトコル CTG

CT_Gは，ユーザU がエンティティX ∈ {O_j ∈ GJ, M_G_J ∈ GJ}にグループGI

の登録を示すとともに，XにおけるP₍_U,X₎に対応するユーザであることを証明するのに用いられる．

CT_GU(x_U, s₍_U,G_I₎, s₍_U,G_J₎, P₍_U,G_I₎,C₍U,G_I)), X (YG_I,YG_J, P₍_U,X₎) {0,1} であらわされ，証明者UがC(U,G_I)∈CI_GU, M_G_I (P₍_U,G_I₎), P₍_U,G_I₎∈P GU(x_U), M_G_I かつP₍_U,X₎ ∈ P GU(x_U), X をみたすC(U,G_I), P₍_U,G_I₎を入力したとき，共通入力 P₍_U,X₎に対して圧倒的確率で1を，そうでないときは0を出力する．

プロトコルCT_Gは以下のように構成される:

Step 1. ユーザUはr₁, r₂ ∈R{0,1}²ⁿを選択し，c₁ :=C₍_U,G_I₎e_G^r¹とc₂ :=e_G_I^r¹d_G_I^r² を計算し，c₁, c₂を検証機関Xに送る．

Step 2. U は以下のP K²によって，検証機関Xに登録証明をおこなう:

P K²{(α, β, γ, δ, ε, ζ, ξ, η) : f_G_I =c₁^α/g_G_I^βh_G_I^γe_G_I^δ

∧ c₂ =e_G_I^εd_G_I^ζ

∧ 1 =c₂^α/e_G_I^δd_G_I^ξ

∧ P₍_U,X₎ =g_G_J^βh_G_J^η

∧ α∈Λ∧β ∈Γ∧γ ∈∆}.

仮名保証書生成プロトコル GG

GGによって，ユーザUは仮名を登録した機関O_i ∈Gから，登録済みであることを保証する情報を得ることができる．このプロトコルは，

GGU(x_U, s₍_U,O_i₎), O_i(x₍_O_i_,G₎) (YG, y₍_O_i_,G₎, P₍_U,O_i₎)[U(σ₍_U,O_i₎, r₍_U,O_i₎)]

であらわされ，Uのプライベート入力x_Uに対し，P₍_U,O_i₎ ∈P GU(x_U), O_i のときのみU の仮名P₍_U,O_i₎に対する仮名保証書σ₍_U,O_i₎ = (˜e,˜s,P ,˜ Q)˜ と乱数r₍_U,O_i₎をプライベート出力としてUに与える．

また，Ii ∈Gによって生成された正しい仮名保証書σ₍_U,O_i₎ は，公開鍵y₍_O_i_,G₎に対して，

e =H(gG, y₍_O_i_,G₎,P ,˜ Q, g˜ G˜s

y₍_U,O_i₎^˜^e,P˜^s^˜Q˜^e^˜) をみたす．プロトコルGGは以下のように構成される:

Step 1. U はOiに登録済みの仮名P₍U,O_i)に対応するユーザであることを P K²{(α, β) : P₍_U,O_i₎=g_G^αh_G^β}

によって証明する．

Step 2. O_i は，r ∈R {0,1}²ⁿ に対して t₁ := g_G^r, t₂ := P₍_U,O_i₎^r と Q₍_U,O_i₎ :=

P₍_U,O_i₎^x⁽^Oi,G⁾ を計算し，それらをU に送る．

Step 3. U は，r₁, r₂, r₍_U,O_i₎ ∈R {0,1}²ⁿ を選択し，˜t₁ := t₁g_G^r¹y₍_O_i_,G₎^r², ˜t₂ :=

(t₂P₍_U,O_i₎^r¹Q₍_U,O_i₎^r²)^r⁽^U,Oi⁾, ˜P := P₍_U,O_i₎^r⁽^U,Oi⁾ とQ˜ := Q₍_U,O_i₎^r⁽^U,Oi⁾ を計算する．次に，˜e := H(g_G, y₍_O_i_,G₎,P ,˜ Q,˜ ˜t₁,˜t₂), e := ˜e−r₂を計算し，eをO_iに送る．

Step 4. O_iは秘密鍵x₍_O_i_,G₎を用いてs:=r−ex₍_O_i_,G₎を計算し，U に送る．

Step 5. U はt₁ =g_G^sy₍_O_i_,G₎^eかつt₂ =P₍_U,O_i₎^sQ₍_U,O_i₎^eがなりたつかどうかを検証し，正しければ˜s:=s+r₁を計算し，P₍_U,O_i₎に対する登録証明書が発行されるまでσ₍_U,O_i₎ := (˜e,s,˜ P ,˜ Q)˜ とr₍_U,O_i₎を保管する．

機関登録証明書発行プロトコル CI_O

CIO は機関管理者MG ∈ GがユーザU に機関Oi ∈ Gの登録証明書，即ち Oi ∈Gに登録された仮名に対する証明書を発行するのに用いられる．CIOは，

CI_OU(x_U, s₍_U,G₎, s₍_U,O_i₎, P₍_U,O_i₎, r₍_U,O_i₎), M_G(XG) (YG,Y₍O_i,G), P₍_U,G₎, σ₍_U,O_i₎) [U(C₍U,O_i))]

であらわされる．入力σ₍_U,O_i₎ ∈ GGU, O_i (P₍_U,O_i₎)に対し，P₍U,O_i) に対する機関登録証明書C₍U,O_i)をプライベート出力としてU に与える．出力されるC₍U,O_i)は C₍_U,O_i₎ ≡(P₍_U,O_i₎d_G^id⁽^Oi,G⁾f_G)¹^/E⁽^U,Oi⁾をみたす(E₍_U,O_i₎, C₍_U,O_i₎)の組で与えられる．

ユーザUはこの時点で，既にグループGの機関管理者M_Gに仮名P₍_U,G₎，機関 O_i ∈Gに仮名P₍_U,O_i₎を登録している．よって，仮名の関連付けを防ぐため，ユーザは機関管理者にP₍_U,O_i₎を見せることなく，σ₍U,O_i)がO_iによってUの仮名に対して生成されていることを証明する．また，σ₍U,O_i)はU へのプライベート出力であるため，機関管理者と各機関の結託によるユーザ情報の連結を防ぐことができる．

但し，機関管理者はP₍_U,G₎がどの機関に登録しているかという情報のみを管理できる．

プロトコルCIOは以下のように構成される:

Step 1. ユーザUはランダムに選択した素数E₍_U,O_i₎ ∈R Λとr∈RZn_G, id₍_O_i_,G₎∈∆ に対し，c:= r^E⁽U,Oi)P₍_U,O_i₎d_G^id⁽^Oi,G⁾f_Gを計算し，c, E₍_U,O_i₎, σ₍_U,O_i₎をGに送

る．さらに，そのσ₍_U,O_i₎に対応するユーザであることを証明する: U はランダムに選択したr₁ ∈R {0,1}²ⁿ に対してc₁ :=reGr₁ を計算し，Gに登録されている仮名P₍_U,G₎に対して以下のP K²を実行する:

P K²{(α, β, γ, δ, ε, ζ, ξ, η) : P₍_U,G₎ =g_G^αh_G^β

∧ 1 =P₍_U,G₎^γ/g_G^δh_G^ε

∧ P˜ =g_G^δh_G^ζ

∧ P˜ =c^γ(e_G^E⁽^U,Oi⁾)^ξ/(c₁^E⁽^U,Oi⁾d_G^id⁽^Oi,G⁾f_G)^γ

∧ α∈Γ, β ∈∆}.

Step 2. M_Gはt₁ :=g_G^˜^sy₍_O_i_,G₎^e^˜,t₂ := ˜P^s^˜Q˜^˜^eに対してe˜=H(g_G, y₍_O_i_,G₎,P ,˜ Q, t˜ ₁, t₂) が成り立つかどうか検証し，正しければc :=c¹^/E⁽^U,Oi⁾ とし，Uに送る．

Step 3. UはC₍_U,O_i₎ :=c/rを計算し，C₍U,O_i)E₍_U,Oi₎ ≡P₍_U,O_i₎d_G^id⁽^Oi,G⁾f_G (modn_G) が成り立つかどうか検証する．正しければ(E₍_U,O_i₎, C₍_U,O_i₎)を機関O_iの登録証明書として保管する．

機関登録証明プロトコル CS⁺

CS⁺は，ユーザU が検証者V に機関O_i ∈ Gへの登録を証明するのに用いられる．

CS⁺U(x_U, s₍_U,O_i₎, P₍_U,O_i₎,C₍U,O_i)), V (YG, y₍_O_i_,G₎) {1,0}

は，P₍U,O_i) ∈ P GU, O_i かつC(U,O_i) ∈ CI_OU(P₍_U,O_i₎), M_G をみたすP₍_U,O_i₎ と C(U,O_i) の入力に対して圧倒的確率で1を出力する．

プロトコルCS⁺は以下のように構築される:

Step 1. Uはr₁, r₂ ∈R {0,1}²ⁿに対し，c₁:=C₍_U,O_i₎eGr₁とc₂:=eGr₁dGr₂

を計算し，

それらをV におくる．

Step 2. U は以下のP K²によって，検証者V に機関O_iの登録証明をおこなう:

P K²{(α, β, γ, δ, ε, ζ, ξ) : f_Gd_G^id⁽^Oi,G⁾ =c₁^α/g_G^βh_G^γe_G^δ

∧ c₂ =e_G^εd_G^ζ

∧ 1 = c₂^α/e_G^δd_G^ξ

∧ α ∈Λ∧β ∈Γ∧γ ∈∆}.

機関情報をもたない機関登録証明プロトコル CS⁻

CS⁻は，ユーザUが検証者V にグループG内のある機関に登録していることを証明するのに用いられる．

CS⁻U(x_U, s₍_U,O_i₎, P₍_U,O_i₎,C(U,O_i),Y(O_i,G)), V (YG) {1,0}

は，P₍U,O_i) ∈ P GU, O_i かつC(U,O_i) ∈ CI_OU(P₍_U,O_i₎), M_G をみたすP₍_U,O_i₎ と C(U,O_i) の入力に対して圧倒的確率で1を出力する．

プロトコルCS⁻は以下のように構築される:

Step 1. U は，r₁, r₂ ∈R {0,1}²ⁿに対し，c₁:=C₍_U,O_i₎eGr₁ とc₂:=eGr₁dGr₂

を計算し，それらをV に送る．

Step 2. U は以下のP K²によって，検証者V に機関情報をもたない機関登録証明

をおこなう:

P K²{(α, β, γ, δ, ε, ζ, ξ, η) : f_G =c₁^α/g_G^βh_G^γd_G^δe_G^ε

∧ c₂ =e_G^ζd_G^ξ

∧ 1 =c₂^α/e_G^εd_G^η

∧ α∈Λ∧β ∈Γ∧γ ∈∆}.

検証機関への機関登録認証プロトコル CT⁺

CT⁺において，ユーザU はエンティティX ∈ {Oj ∈ GJ, MG_J ∈ GJ}に機関 Oi ∈ GIへの登録を示すとともに，XにおけるP₍_U,X₎に対応するユーザであることを示すことができる．

CT⁺U(x_U, s₍_U,O_i₎, s₍_U,O_j₎, P₍_U,O_i₎,C₍U,O_i)), X (YG_I,YG_J, y₍_O_i_,G_I₎, P₍_U,X₎) {1,0}

は，C₍U,O_i) ∈CI_OU(P₍_U,O_i₎), M_G_J ,P₍_U,O_i₎ ∈P GU(x_U), O_i かつP₍_U,X₎∈P GU(x_U), X をみたすP₍_U,O_i₎, P₍_U,X₎とC₍U,O_i) に対して圧倒的確率で1を出力する．

プロトコルCT⁺は以下のように構築される:

Step 1. U は，r₁, r₂ ∈R {0,1}²ⁿに対して，c₁ := C₍_U,O_i₎e_G_I^r¹ とc₂ := e_G_I^r¹d_G_I^r² を計算し，それらをX に送る．

Step 2. U は，以下のP K²によって機関登録証明をおこなう:

P K²{(α, β, γ, δ, ε, ζ, ξ, η) : f_G_Id_G_I^id⁽^Oi,GI⁾ =c₁^α/g_G_I^βh_G_I^γe_G_I^δ

∧ c₂ =e_G_I^εd_G_I^ζ

∧ 1 =c₂^α/e_G_I^δd_G_I^ξ

∧ P₍_U,X₎ =g_G_J^βh_G_J^η

∧ α∈Λ∧β ∈Γ∧γ ∈∆}.

検証機関への機関登録証明プロトコル CT⁻

CT⁻において，ユーザU はエンティティX ∈ {O_j ∈GJ, M_G_J ∈GJ}にグループGI内のある機関への登録を示すとともに，XにおけるP₍_U,X₎におけるP₍_U,X₎ に対応するユーザであることを示すことができる．

CT⁻U(x_U, s₍_U,O_i₎, s₍_U,O_j₎, P₍_U,O_i₎,C(U,O_i), y₍_O_i_,G_I₎), X (YG_I,YG_J, P₍_U,X₎) {1,0}

は，C₍U,O_i) ∈CI_OU(P₍_U,O_i₎), M_G_I ,P₍_U,O_i₎ ∈P GU(x_U), O_i かつP₍_U,X₎ ∈P GU(x_U), O_j をみたすP₍_U,O_i₎, P₍_U,X₎とC(U,O_i) に対して圧倒的確率で1を出力する．

プロトコルCT⁻は以下のように構築される:

1. Uはr₁, r₂ ∈R{0,1}²ⁿに対し，c₁ :=C₍_U,O_i₎e_G_I^r¹, c₂ :=e_G_I^r¹d_G_I^r²を計算し，c₁ とc₂をXに送信する．

2. Uは，以下のP K²によって機関登録証明をおこなう:

P K²{(α, β, γ, δ, ε, ζ, ξ, η, ϕ) : f_G_I =c₁^α/g_G_I^βh_G_I^γd_G_I^δe_G_I^ε

∧ c₂ =e_G_I^ζd_G_I^ξ

∧ 1 = c₂^α/e_G_I^εd_G_I^η

∧ P₍_U,X₎ =g_G_J^βh_G_J^ϕ

∧ α ∈Λ∧β ∈Γ∧γ∈ ∆}.

ドキュメント内電子商取引の高セキュリティ化に関する研究 (ページ 53-61)