プロトコル

本章では，効率よく複数機関への登録を証明するためのプロトコルを提案する．

初期設定

システムパラメータを以下のように設定する．RSAの法のサイズを_nビット，

セキュリティパラメータを >1する．また，_Γ = 2_n, _∆ = _Γ, 2^Λ >2(2^Γ+2) とし，各区間をΓ =]−2^Γ,2^Γ[, ∆ =]−2^∆,2^∆[, Λ =]2^Λ,2^Λ+Σ[と設定する．

鍵生成プロトコル KG

鍵生成プロトコルKGIO, KGO_iとKGUは

KGIO(1^k)(XIO,YIO), KGO_i(1^k,YIO)(xO, yO), KGU xU

であらわされ，KGIOとKGO_iは，それぞれ証明書発行機関IOと機関Oiの秘密 鍵,公開鍵の組を，KGUはユーザU の秘密鍵を生成する．(XIO,YIO)をIOの鍵，

(x_Oi, y_Oi)を機関O_iの鍵，そしてx_UをユーザU の秘密鍵とする．上記は，KGIO

とKG_Uは1^kの入力に対し，(XIO,YIO)またはx_Uを，KGO_iは1^kとIOの公開鍵 YIOに対し，(xO_i, y_Oi)を出力することを意味する．

Step 1. 証明書発行機関IOは，p:= 2p+ 1, q= 2q+ 1を素数とする_n/2ビット の素数p, qをランダムに選び，n :=pqとする．また，d, e, f, g, h, v∈R Z^∗n2

を選び，(p, q)を秘密鍵，(n, d, e, f, g, h, v)を公開鍵とする．

Step 2. 属性認証機関O_iは，秘密鍵x_Oi ∈R Γを選択し，それに対応する公開鍵を y_Oi :=v^xOi modnとする．

Step 3. ユーザUは，秘密鍵としてx_U ∈Γと，証明書生成に用いる情報として素

数E_U ∈Λを選択し，保管しておく．

仮名生成プロトコル P G

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

P GU(x_U), X (YIO)[U(s_(U,X))](P_(U,X))

であらわされる．上記は，P GはU とX ∈ {O, IO}の対話によっておこなわれ，

これは，Uによる入力x_Uと共通入力YIOから，Uへs_(U,X)をU へプライベート出 力し，Uの仮名P_(U,X)を共通出力とすることを意味する．また，P Gは出力P_(U,X) が正しい型であること，即ちx_U ∈Γ, s_(U,X) ∈∆を用いてP_(U,X) =g^xUh^s(U,X) にあ らわされることを保証する．

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

Step 1. U はr₁ ∈R ∆, r₂, r₃ ∈R {0,1}²ⁿ を選び，c₁ :=d^r1e^r2, c₂ :=d^xUe^r3 を計算 し，Xに送る．また，

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

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

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

˜

s =r₁+r/(2^∆+1−1) を計算し，P₍U,X):=g^xUh^s(U,X)を仮名とする．また r₄ ∈R {0,1}ⁿに対しc₃ :=d^˜se^r4 とP_(U,X)をXに送信し，それが正しく生成 されたことを以下のゼロ知識証明によって証明する．

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

∧ c₂ =d^γe^δ

∧ c₃ =d^εe^ζ

∧ P_(U,X) =g^γh^ϑ

∧ (c₁d^r−2∆+1)/(c₃^2∆+1+1) =d^ϑe^ξ

∧ γ ∈Γ∧ϑ ∈∆}. Step 4. Xは仮名リストにP_(U,X)を保管する．

Step 5. U はP_(U,X)の生成に用いた秘密情報s_(U,X)とP_(U,X)をXの登録情報とし て秘密に保管する．

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

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

GGU(x_U, s_(U,O)), O_i(x_Oi) (YIO, y_Oi, P_(U,Oi))[U(σ_(U,Oi), r_(U,Oi))]

であらわされ，Uのプライベート入力x_Uに対し，P_(U,Oi) ∈P GU(x_U), O_i のとき のみU の仮名P_(U,Oi)に対する仮名証明書σ_(U,Oi)をプライベート出力としてU に 与える．

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

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

によって証明する．

Step 2. O_iはr ∈R {0,1}²ⁿに対して，t₁ :=v^r, t₂ = P_(U,Oi)^r, Q_(U,Oi) :=P_(U,Oi)^xOi を計算し，それらをU に送る．

Step 3. U はr₁, r₂, r_(U,Oi)∈ {0,1}²ⁿを選択し，˜t₁ :=t₁v^r1y_Oi^r2, ˜t₂ := (t₂P_(U,Oi)^r1 Q_(U,Oi)^r2)^r(U,Oi),P˜ :=P_(U,Oi)^r(U,Oi),Q˜ :=Q_(U,Oi)^r(U,Oi)xU を計算する．

次に，˜e:=H(˜t₁,˜t₂),e:= ˜ex_U −r₂ を計算し，eをO_iに送る．

Step 4. O_iは秘密鍵x_Oiを用いて，s :=r−ex_Oi を生成し，Uに送る.

Step 5. U はt₁ =v^sy_Oi^e,t₂ =P_(U,Oi)^sQ_(U,Oi)^e が成り立つかどうかを検証し，それ が正しければ，˜s :=s+r₁ とし，P₍U,O_i)に対する登録証明書が発行されるま で，σ₍U,O_i) := (˜s,˜t₁,˜t₂,P ,˜ Q)˜ とr_(U,Oi)を保管する．

登録証明書発行プロトコル CI

CIは，証明書発行機関IOが登録証明書を発行するのに用いられ，

CIU(x_U, s_(U,IO), s_(U,Oi), P_(U,Oi), r_(U,Oi), y_Oi), IO(XIO) (YIO, P_(U,IO), σ_(U,Oi)) C(U,IO)

であらわされる．CIは U のプライベート入力x_U, P_(U,Oi), y_Oi に対し，σ_(U,Oi) ∈

GGU(xU), Oi (P_(U,Oi))かつP_(U,IO) ∈P GU(xU), IO であるとき，C_(U,Oi)≡(yO_ix_Uf)^1/EU (mod n)をみたす登録証明書C_(U,Oi)を出力する．CIはlog_vy˜= log_P˜Q˜ =xUをみ

たすy˜に対して発行されるため，˜y^1/xUを公開鍵としてもつ機関への登録証明書と なる．

また，CIにおいてU はσ_(U,Oi)に対応するユーザであること，即ちP˜に対応す る仮名がP_(U,IO)と同じ秘密鍵を用いて生成されていることのみを証明し，σ₍U,O_i)

の作成機関に関する情報は何ら与えない．

UとIOは以下のように構成される:

Step 1. U は，σ₍U,O_i)をIOに送信し，σ₍U,O_i)に対応するユーザであることを証明 するため，以下の対話証明をおこなう:

P K²{(α, β, γ, δ, ε, ζ) : P_(U,IO) =g^αh^β

∧ P˜=g^γh^δ

∧ 1 =P_(U,IO)^ε/(g^γh^ζ)

∧ α∈Γ, β∈∆}.

Step 2. IOは˜e=H(˜t₁,˜t₂)に対して，˜t₂≡P˜^s˜Q˜^˜e が成り立つかどうかを検証し，正 しければy˜:= (˜t₁/v^˜s)^1/˜eに対し，C₍U,O_i) := (˜yf)^1/EU modnとしUに送る．

Step 3. U は，C₍U,O_i)E_U≡y_Oi^xUf (mod n) が成り立つかどうか検証する．もし正 しければ，C₍U,O_i) をO_iの登録証明書として保管する．

登録証明プロトコル CS

CSは，ユーザUが検証者V に任意の複数機関への登録を証明するのに用いら れる．ここで，U が既に証明書の発行を受けている機関の集合をOU，V に証明す る機関の集合をOS ⊂ OU とすると，CSは，

CSU(x_U,{C₍U,G)}_OS), V (YIO,{y_O}_OS) {0,1}

であらわされ，{C_(U,O)∈CIU(x_U, y_O), IO }OSの入力に対して圧倒的確率で1を，

そうでないときは0を出力する．

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

Step 1. U はC_U :=

OsC_(U,Oi)を計算し，r₁, r₂ ∈R {0,1}²ⁿに対し，c₁:=C_Ue^r1, c₂:=e^r1d^r2 を生成し，検証者V に送信する．

Step 2. U とV は以下のP Kを実行する:

P K²{(α, β, γ, δ, ε, ζ) : f^|OS| =c₁^α/((

OSy_Oi)^βe^γ)

∧ c₂ =e^δd^ε

∧ 1 = c₂^α/e^γd^ζ

∧ α ∈Λ∧β ∈Γ}.

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

CT は，ユーザUが検証機関O_jにUの全ての属性OSに対するOS ⊂ OU への 登録を示すとともに，OjにおけるP_(U,Oj)に対応するユーザであることを証明する のに用いられる．

CTU(x_U,{C(U,G_I)}OS), O_j (YIO,{y_O}OSP_(U,Oj)) {0,1}

であらわされ，証明者Uが{C(U,O) ∈CIU, IO (P_(U,O)), P_(U,O) ∈P GU(x_U), O }OS

かつP_(U,Oj)∈P GU(x_U), O_j をみたす{C_(U,O)}OSを入力したとき，圧倒的確率で 1を，そうでないときは0を出力する．

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

Step 1. U はCU :=

OsC_(U,Oi)を計算し，r₁, r₂ ∈R {0,1}²ⁿに対し，c₁:=CUe^r1, c₂:=e^r1d^r2 を生成し，機関Ojに送信する．

Step 2. U とO_jは，Oj に登録されている仮名P_(U,Oj)に対して以下のP Kを実行 する:

P K²{(α, β_i, γ, δ, ε, ζ, ξ, η, ϕ) : f^|OS|=c₁^α/((

OSy_Oi)^βe^γ)

∧ c₂ =e^δd^ε

∧ 1 =c₂^α/e^γd^ζ

∧ P_(U,Oj)=g^βh^ξ

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