ユーザに対する電子保証人方式

Case 1. m∈ {0,1}^∗, t_U, y_U, t_G ∈RZ^∗p, c ∈R{0,1}^∗をHに質問し，答えとしてeを得た後，tGを鍵としたRの暗号文をCに求め，c =Ct_G(R)を得る．このとき，既に選択したcに対してc=cとなる確率は無視できるほど小さい．

Case 2. m∈ {0,1}^∗, tU, yU, tG ∈RZ^∗p, c ∈R{0,1}^∗をHに質問し，答えとしてeを得た後，tGを鍵としたcの復号文をC⁻¹を求め，R =Ct⁻¹_G(c)を得る．このとき，Rがnビットの冗長をもつ，即ち0ⁿ || βという形になる確率は無視できるほど小さい．

Case 3. t_G ∈R Z^∗q, c∈ {0,1}^∗を選択し，t_Gを鍵としたcの復号文をC⁻¹に求め，R を得る．その後，m ∈ {0,1}^∗, t_U, y_U ∈RZ^∗_qに対し，m, tU, y_U, t_G, cをHに質問し，eを得る．このとき，Forking Lemmaより無視できない確率で正しい署名(t_G, e, s_G)と(t_G,˜e,˜s_G)を得る．このとき，t_Uy_Ut_G≡g^s^U⁺^s^G(y_Uy_G)^ey_U ≡ g^s^˜^U⁺^s^G(y_Uy_G)^e^˜y_U (modp)より，これらはt_G=g^s^G(y_Uy_G)^e=g^s^˜^G(y_Uy_G)^e^˜mod pをみたすので，g^s^G^−˜^s^G = (g^x^U⁺^x^G)^e^−˜^e modpより，x_G = (s_G−˜s_G)/(˜e−e)− x_U modqを得る．これは，yG, g∈Z^∗pに対する離散対数問題の解であり，離散対数問題の困難さの仮定に反する．従って，InAdvが正当な署名を生成する確率は無視できる．

Case 4. t_G ∈R Z^∗p, c ∈ {0,1}^∗を選択し，tGを鍵としたcの暗号文をCに求め，c を得る．その後，m ∈ {0,1}^∗, t_U, y_U, y_G ∈R Z^∗p に対し，m, t, cをHに質問し，eを得る．このとき，3と同様の議論によって離散対数問題が解けることとなる．

Case 1,2,3,4より，InAdv が検証式をみたす保証付署名を生成できる確率は無視

できることがいえる．

4.4.1 ^{プロトコル}

ユーザに対する電子保証方式を実現するためのプロトコルを以下で与える:

1. 初期設定: q|p−1をみたす十分大きな素数p, qとqを位数とするg ∈Z^∗pを用意する．また，共通鍵暗号化関数，および共通鍵復号関数CK，CK−1と，ハッシュ関数H:{0,1}^∗ → {0,1}^|ⁿ^|を用意する．

2. 鍵生成: 鍵生成アルゴリズム

KG_U(1ⁿ)(x_U, y_U), KG_G(1ⁿ)(x_G, y_G)

はセキュリティパラメータnに対し，1ⁿの入力によって，鍵の組を出力する多項式時間アルゴリズムである．出力される(x_U, y_U)と(x_G, y_G)は，それぞれU とGの秘密鍵と公開鍵の組である．ここで，KG(1ⁿ) (x, y)は(x, y) がアルゴリズムKGへの入力1ⁿによって出力されることを意味する．

– ユーザU，保証者Gともに，秘密鍵としてx_U ∈RZ^∗q, x_G ∈RZ^∗q を選択し，

yU :=g^x^U modp, yG :=g^x^G modp をそれぞれ公開鍵とする．

3. 保証書生成: 保証書生成アルゴリズム

Gua(yU, xG, yG)αU G

は，ユーザU の公開鍵y_U，保証者Gの鍵の組(x_G, y_G)の入力に対して，U への保証書α_{U G}を出力する．

–保証者Gは，r_G ∈RZ^∗qを選択し，保証対象となるユーザの公開鍵y_Uを用いてt_G :=g^r^G modp, R₁ := 0ⁿ ||y_U^k^G, R₂ := 0ⁿ ||y_U^k^G⁺¹ を計算し，tGを鍵としたR₁とR₂の暗号文c_G₁ :=Ct_G(R₁), c_G₂ :=Ct_G(R₂)を求める．また，e_G:=

H(y_G, c_G₁, c_G₂), s_G :=k_G−e_Gx_G modq とし，保証書α_{U G} = (s_G, c_G₁, c_G₂)を

U に送る．

4. 保証書を用いた署名生成: 署名生成アルゴリズム

Sig(m, x_U, y_U, y_G, α_{U G})σ_{U G}

は，メッセージm，ユーザU の鍵の組(x_U, y_U)，保証者の公開鍵y_G，保証書αU Gの入力に対し，保証付署名σU Gを出力する．

– ユーザU は，rU ∈R Z^∗q を選択し，˜e_G := H(y_G, c_G₁, c_G₂)に対してt_U₁ :=

g^r^U modp, t_U₂ := (g^s^Gy_G^˜^e^G)^r^U modp を計算し，eU := H(m, t_U₁t_U₂), s_U :=

r_U−e_Ux_U modqとし，保証書付署名としてσ_{U G} = (e_U, s_U, s_G,(c_G₁, c_G₂))を出力する．

5-1. 一般検証: 一般検証アルゴリズム

V er₍_U,G₎(m, α_{U G}, σ_{U G}, y_U, y_G) {1,0}

は，メッセージm，保証書α_{U G}，署名σ_{U G}，公開鍵y_U, y_Gに対し，σU G ∈ Sig(m, x_U, y_U, y_G, α_{U G})かつ，αU G ∈Gua(y_U, x_G, y_G)のときに圧倒的確率で 1を，そうでないときは0を出力する．

– 検証者V は，˜e_G :=H(y_G, c_G₁, c_G₂)に対し，˜t_G:=g^s^Gy_G^˜^e^G modpを計算する．˜t_Gを鍵としてc_G₁ の復号文R˜₁ := C˜t_G−1(c_G₁)を求め，R˜₁の上位nビットをbとし，b||β˜に分割する．もし，t˜:= (gt_G)^s^U(y_Uβ)^e^U modpに対して，

b = 0ⁿかつe_U =H(m,˜t)が成り立つならば，σU GをUのGの保証付署名として受理し，そうでない場合は拒否する．

5-2. 保証書単独検証: 保証書単独検証アルゴリズム

V er_G(m, α_{U G}, σ_{U G}, y_G) {1,0}

は，メッセージm，保証書α_{U G}，署名σ_{U G}，保証者の公開鍵y_Gに対し，σ_{U G}∈ Sig(m, x_U, y_U, y_G, α_{U G})かつ，σU G ∈Gua(y_U, x_G, y_G)のときに圧倒的確率で 1を，そうでないときは0を出力する．

– 検証者V は，˜e_G :=H(y_G, c_G₁, c_G₂)に対し，˜t_G:=g^s^Gy_G^˜^e^G modpを計算する．˜t_Gを鍵としてc_G₂の復号文R˜₂ :=C˜t_G−1(c_G₂)を求め，R˜₂の上位nビットをbとし，b||β˜に分割する．もし，˜t:= (gt_G)^s^Uβ^e^U modpに対して，b = 0ⁿ かつe_U =H(m,˜t)が成り立つならば，σU GをGの保証付署名として受理し，

そうでない場合は拒否する．

4.4.2 ^{安全性の考察}

ここで，ユーザに対する電子保証人方式の安全性について考察する．システム・

パラメータ，公開鍵が与えられ，ランダム・オラクルHと理想的共通鍵暗号関数 C，または復号関数C⁻¹にアクセスを許された攻撃者Advを仮定する．このとき，

ユーザ，及び保証者に対する安全性について以下の定理が与えられる．

定理 3 (保証者に対する安全性) ユーザU と結託することによって，適応的に選

択した公開鍵y_U_i (1≤i≤)に対応する正当な保証書α_U_i_Gを得ることのできる攻撃者Advが，yU =∀y_U_iに対して

V er₍U,G)(m, αU G, σU G, yU, yG) = 1∨V erG(m, αU G, σU G, yG) をみたす保証書α_{U G}を生成できる確率は無視できる．

Proof. 攻撃者Advの動きを以下の4つに分類し，それぞれについて考察する．

Case 1. y_U, t_G ∈R Z^∗p, c₁, c₂ ∈R {0,1}^∗をH に質問し，答えとしてe_Gを得た後，

t_Gを鍵としたR₁, R₂の暗号文をCに求め，c₁ =Ct_G(R₁)，及びc₂ =Ct_G(R₂) を得る．このとき，既に選択したc₁, c₂に対してc₁ =c₁またはc₂ =c₂となる確率は無視できるほど小さい．

Case 2. y_U, t_G ∈R Z^∗p, c₁, c₂ ∈R{0,1}^∗をHに質問し，答えとしてe_Gを得た後，t_G を鍵としたc₁, c₂の復号文をC⁻¹を求め，R₁ =Ct_G−1(c₁)，及びR₂ =Ct_G−1(c₂) を得る．このとき，R₁またはR₂がnビットの冗長をもつ，即ち0ⁿ || βという形になる確率は無視できるほど小さい．

Case 3. t_G ∈R Z^∗_q, c₁, c₂ ∈ {0,1}^∗を選択し，tGを鍵としたc₁, c₂の復号文をC⁻¹ に求め，R₁，及びR₂を得る．その後，m ∈ {0,1}^∗，tU, y_U ∈R Z^∗q, c₁, c₂ ∈ {0,1}^∗をHに質問し，eGを得る．このとき，Forking Lemmaより無視できない確率で正しい保証書(t_G, e_G, s_G)と(t_G,˜e_G,˜s_G) を得る．このとき，tG ≡ g^s^Gy_G^e^G ≡g^˜^s^Gy_G^e^˜^G (mod p)より，g^s^G^−˜^s^G ≡y_G^˜^e^G⁻^e^G (modp)を得る．これよりx_G ≡ (s_G−˜s_G)/(˜e_G−e_G) (mod q) を得るが，これはy_G, g ∈ Z^∗pに対する離散対数問題の解であり，離散対数問題の困難さの仮定に反する．従って，Advが正当な署名を生成する確率は無視できる．

Case 4. t_G ∈R Z^∗p, R₁, R₂ ∈ {0,1}^∗を選択し，t_Gを鍵としたR₁, R₂の暗号文をCに求め，c₁, c₂を得る．その後，yU ∈R Z^∗p に対し，m, t, cをHに質問し，e_Gを得る．このとき，3と同様の議論によって離散対数問題が解けることとなる．

Case 1,2,3,4より，Advが検証式をみたす保証付署名を生成できる確率は無視でき

ることがいえる．

定理 4 (署名者に対する安全性) 保証者Gと結託することによって，適応的に選択したメッセージm_i (1≤i≤)に対するU_iの署名σ_U_i_G(m_i)を得ることができる攻撃者Advが(m, U)=∀(m_i, U_i)に対して

V er₍_U,G₎(m, α_{U G}, σ_{U G}, y_U, y_G) = 1∨V er_G(m, α_{U G}, σ_{U G}, y_G) = 1 をみたす保証付署名σ_{U G}を生成できる確率は無視できる．

Proof. ランダム・オラクル仮定の下，Advがメッセージm に対するU の署名

σ_{U G}(m)を偽造できたと仮定する．このとき，Forking LemmaよりAdvはUの署名 (t, e_U, s_U)と(t,e˜_U,s˜_U)を得ることができ，t≡(g^k^G⁺¹)^s^U(y_U^k^G⁺¹)^e^U ≡(g^k^G⁺¹)^˜^s^U(y_U^k^G⁺¹)^e^˜^U り，xU = (s_U−˜s_U)/(e_U−e˜_U) modqを得る．これは，yU, g ∈Z^∗_pに対する離散対数問題の解であり，離散対数問題の困難さの仮定に反する．従って，Advが正当な署名を生成する確率は無視できる．

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

4.4.1 プロトコル

4.4.2 安全性の考察

4.4.1 ^{プロトコル}

4.4.2 ^{安全性の考察}