取引に対する電子保証人方式

本節では，取引に対する電子保証人方式を実現し，その安全性を考察する．こ の場合，保証者の生成する情報である保証書は固定された取引内容(メッセージ) とユーザの組に対して作成され，ユーザの生成する情報は保証書を用いて作成さ れるべきである．即ち保証者の公開鍵を用いてのみ署名の正当性の検証をおこな うことができるようにすることで，保証の単独検証を可能にする．

4.3.1 ^{プロトコル}

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

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

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

KGU(1ⁿ)(xU, yU), KGG(1ⁿ)(xG, yG)

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

– ユーザU，保証者Gともに，秘密鍵x_U ∈RZ^∗q, x_G ∈RZ^∗q を生成し，yU :=

g^xU modp, y_G:=g^xG modp をそれぞれ公開鍵とする．

3. 電子保証付署名生成: 電子保証付署名生成プロトコル

InSigU(x_U), G(x_G) (m, y_U, y_G)σ_{U G}

は，Uによるプライベート入力x_U，Gによるプライベート入力x_G，共通入 力m, y_U, y_G に対してメッセージmに対するUのGによる保証付署名σ_{U G} を出力する．

Step 1. ユーザUは，r_U ∈RZ^∗qに対してt_U :=g^rU modpを計算し，メッセー ジmとtUを保証者Gに送る．

Step 2. 保証者Gは，r_G ∈R Z^∗qを選択し，t_G :=g^rG modp, R:= 0ⁿ||y_Uを計 算し，t_Gを鍵として用いたRの暗号文c_G :=Ct_G(R), e :=H(m, t_Uy_Ut_G, c_G) を求める．また，sG :=r_G−ex_G modq とし(e, s_G, c_G)をUに送る．

Step 3. U は˜t_G := g^sGy_G^eに対し，e = H(m, t_Uy_Ut˜_G, c_G)が成り立つかどう か検証し，正しければs_U :=r_U−ex_U modqとし， メッセージmに対 する署名としてσ_{U G} = (e, s_U, s_G, c_G)を出力する．

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

InV er_(U,G)(m, σ_{U G}, y_U, y_G) {1,0}

は，メッセージm，署名σ_{U G}，ユーザと検証者の公開鍵y_U, y_Gに対し，σ_{U G}∈ InSigU(x_U), G(x_G) (m, y_U, y_G) である場合は圧倒的確率で1を，そうでな い場合は0をそれぞれ出力する．

–検証者V は，σU G = (e, s_U, s_G, c_G)に対し，˜t:=g^sU+sG(y_Uy_G)^ey_U modpを 計算し，e =H(m,t, c˜ _G)がなりたつならば，σ_{U G}をU によるGの保証付署 名として受理し，そうでない場合には拒否する．

4-2. 保証書単独検証: 保証書単独検証アルゴリズム InV erG(m, σU G, yG) {1,0}

は，メッセージm，署名σ_{U G}，保証者の公開鍵yGに対し，σ_{U G} ∈InSigU(x_U), G(x_U) (m, y_U, y_G) である場合には圧倒的確率で1を出力し，そうでない場 合は0をそれぞれ出力する．

– 検証者V は，˜t_G :=g^sGy_G^emodp を鍵としてc_Gを復号しR˜ :=Cr˜_G−1(c_G) の上位nビットをbとし，b || βに分割する．このとき，b = 0ⁿかつ，e = H(m, g^sUβ^e+1t˜_G, c_G) ならば，σU GをGの保証付署名として受理し，そうで ない場合には拒否する．

4.3.2 ^{安全性の考察}

ここで，取引に対する電子保証人方式の安全性について考察する．

システムパラメータ，公開鍵が与えられ，ランダム・オラクルHと理想的共通 鍵暗号関数C，または復号関数C⁻¹にアクセスを許された攻撃者InAdvを仮定す る．このとき，ユーザ，及び保証者に対する安全性について以下の定理が与えら れる．

定理 1 (ユーザに対する安全性) 保証人Gと結託することで，適応的に選択した

メッセージ m_i (1 ≤ i ≤ )に対するU_iによる署名σ_UiG(m_i)を得ることができる 攻撃者InAdvが，(m, U)=∀(m_i, U_i)(1 ≤i≤)に対して，

InV er_(U,G)(m, σ_{U G}(m), y_U, y_G) = 1∨InV er_G(m, σ_{U G}(m), y_G) = 1 をみたすσ_{U G}(m)を生成できる確率は無視できる．

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

σ_{U G}(m)を偽造することができたと仮定する．このとき，Forking Lemma[?] より InAdvはUの署名(t_U, e, s_U)と(t_U,e,˜ s˜_U)を得ることができる．このとき，t_Uy_Ut_G ≡ g^sU+sG(y_Uy_G)^ey_U ≡g^˜sU+sG(y_Uy_G)˜ey_U (modp)より，これらはt_U =g^sU(y_Uy_G)^e = g^s˜U(y_Uy_G)^e˜modpをみたすので，g^sU−s˜U = (g^xU+xG)^e−˜e modpより，xU = (s_U −

˜

s_U)/(˜e−e)−x_G modqを得る．これは，yU, g ∈Z^∗pに対する離散対数問題の解で あり，離散対数問題の困難さの仮定に反する．従って，InAdvが正当な署名を生 成する確率は無視できる．

定理 2 (保証者に対する安全性) ユーザU と結託することで，適応的に選択した メッセージ m_i (1≤ i≤ )に対するG_iによる保証付署名σ_{U Gi}(m_i)を得ることが できる攻撃者InAdvが，(m, G)=∀(m_i, G_i)に対して，

InV er_(U,G)(m, σ_{U G}(m), y_U, y_G) = 1∨InV er_G(m, σ_{U G}(m), y_G) = 1 をみたすσ_{U G}(m)を生成できる確率は無視できる．

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

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^sU+sG(y_Uy_G)^ey_U ≡ g^s˜U+sG(y_Uy_G)^e˜y_U (modp)より，これらはt_G=g^sG(y_Uy_G)^e=g^s˜G(y_Uy_G)^e˜mod pをみたすので，g^sG−˜sG = (g^xU+xG)^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 が検証式をみたす保証付署名を生成できる確率は無視

できることがいえる．