Case 4. tG ∈R Z∗p, R1, R2 ∈ {0,1}∗を選択し，tGを鍵としたR1, R2の暗号文をCに 求め，c1, c2を得る．その後，yU ∈R Z∗p に対し，m, t, cをHに質問し，eGを 得る．このとき，3と同様の議論によって離散対数問題が解けることとなる．
Case 1,2,3,4より，Advが検証式をみたす保証付署名を生成できる確率は無視でき
ることがいえる．
定理 4 (署名者に対する安全性) 保証者Gと結託することによって，適応的に選 択したメッセージmi (1≤i≤)に対するUiの署名σUiG(mi)を得ることができる 攻撃者Advが(m, U)=∀(mi, Ui)に対して
V er(U,G)(m, αU G, σU G, yU, yG) = 1∨V erG(m, αU G, σU G, yG) = 1 をみたす保証付署名σU Gを生成できる確率は無視できる．
Proof. ランダム・オラクル仮定の下，Advがメッセージm に対するU の署名
σU G(m)を偽造できたと仮定する．このとき，Forking LemmaよりAdvはUの署名 (t, eU, sU)と(t,e˜U,s˜U)を得ることができ，t≡(gkG+1)sU(yUkG+1)eU ≡(gkG+1)˜sU(yUkG+1)e˜U り，xU = (sU−˜sU)/(eU−e˜U) modqを得る．これは，yU, g ∈Z∗pに対する離散対 数問題の解であり，離散対数問題の困難さの仮定に反する．従って，Advが正当 な署名を生成する確率は無視できる．
れ(7|q|/2)M(p)が必要となるため，一般検証には全体で(21|q|/4)M(p)の計算コ ストが必要となる．また，保証単独検証は保証者の公開鍵検証のみを必要とする ため，(7|q|/4)M(p)の計算を加えた(21|q|/4)M(p) +Cの計算が必要となる．よっ て，実際の保証書単独検証は，一般検証に必要な計算コストに加え，1回の復号処 理を必要とするが，ユーザの公開鍵を参照するための通信コストを必要としない ため，検証者への負担を軽くすることができると考えられる．また，ユーザに対 する電子保証においても，公開鍵証明書の適用とほぼ同等の計算コストで実現す ることができている．
表 4.1: 電子保証人方式における効率性の比較
方式 一般検証 保証書単独検証 満たさない性質
多重署名[39] (15|q|/8)M(p) — 保証単独検証可能性
署名単独検証不可能性 提案方式(取引保証) (7|q|/4)M(p) (7|q|/2)M(p) +C
公開鍵証明書[47] (7|q|/2)M(p) (7|q|/4)M(p) 署名単独検証不可能性 提案手法(ユーザ保証) (7|q|/2)M(p) +C (7|q|/2)M(p) +C
第 5 章
匿名証明書方式
5.1 はじめに
近年のオンライン・システムの普及に伴い，個人情報の拡散が問題となってい る．このため，ユーザのプライバシ確保のためには，個人が自らの情報の流通を 制御できるアプリケーションが必要であり，このような問題を解決するのが匿名 証明書方式[15, 17, 18, 7, 32, 11]である．匿名証明書方式では，ユーザが異なる仮
名(Pseudonym)を取引機関へ登録する．各機関はその仮名によってユーザの情報
を管理・識別するため，それぞれの機関のもつ情報のリンクによる個人情報の拡 散を防ぐことができ，機関との取引は，登録した仮名に対応するユーザであるこ とを証明することでおこなわれる．また，各機関は登録されたユーザの仮名に対 する登録証明書(Credential)を発行し，対応するユーザは証明書の保持証明をお こなうことで，別機関にその機関への登録者であるという事実のみを示すことが できる．このとき，仮名に関する情報を検証者である別機関に何ら与えないため，
登録証明による仮名の関連付けを防ぐことができる．ここで，匿名証明書方式に 必要な性質を挙げる．
ユーザの匿名性: 検証者，および検証機関はそのユーザの証明書保持の事実以外，
ユーザに関する情報を何も得ることはできない．
仮名の関連付け不可能性: 同一ユーザの異なる仮名が関連付けされることはない．
匿名証明書の偽造不可能性: 機関によって発行される登録証明書の偽造をおこなう
ことはできない．