(57)【要約】  本発明のグループ署名システムは、グループに登録するユーザ装置４００は、巡回群の位数Nならびにその元a＿0、a＿1およびa＿2を含む組の発行装置公開鍵を受信すると、素数eから素数eよりも小さい定数を減じた結果が素数e’となる素数eおよび素数e’を求め、a＿0とa＿1を数xでべき乗剰余したものとの積にa＿2を数rでべき乗剰余したものの積が第１の巡回群の元Aをe乗したものに位数Nを法として等しい関係にあるものとする数xおよび数rを含む組のユーザ装置秘密鍵と、素数e、素数e’および元Aを含む組のユーザ装置公開鍵とを生成し、素数e’を失効管理装置３００に送信し、素数e’を基に算出されたBを失効管理装置３００から受信し、メッセージ入力により、Bの値、ユーザ装置公開鍵、ユーザ装置秘密鍵およびメッセージを用いてメッセージに対する署名文を生成してメッセージと共に検証装置５００に送信する。
2007105749.tif 000002
【特許請求の範囲】
【請求項１】
発行装置、開示装置、失効管理装置、ユーザ装置および検証装置がネットワークを介して互いに接続されたグループ署名システムであって、
前記発行装置は、第１の巡回群の元が格納された発行装置記憶部と、該第１の巡回群の位数Nならびに該第１の巡回群の元a＿0、a＿1およびa＿2を含む組の発行装置公開鍵ipkを生成すると、該発行装置公開鍵ipkを公開する発行装置制御部とを有し、
前記ユーザ装置は、素数の集合が格納されたユーザ装置記憶部と、公開された前記発行装置公開鍵ipkを受信すると、素数eから該素数eよりも小さい定数を減じた結果が素数e’となる該素数eおよび該素数e’を求め、前記a＿0と前記a＿1を数xでべき乗剰余したものとの積に前記a＿2を数rでべき乗剰余したものの積が前記第１の巡回群の元Aを前記素数e乗したものに前記位数Nを法として等しい関係にあるものとする前記数xおよび前記数rを含む組のユーザ装置秘密鍵mskと前記素数e、前記素数e’および前記元Aを含む組のユーザ装置公開鍵mpkとを生成し、該素数e’を前記失効管理装置に送信し、該素数e’を基にして算出されたBを前記失効管理装置から受信し、メッセージが入力されると、該Bの値、前記ユーザ装置公開鍵mpk、前記ユーザ装置秘密鍵msk、および該メッセージを用いて、該メッセージに対する署名文を生成し、該メッセージと該署名文を前記検証装置に送信するユーザ装置制御部とを有し、
前記失効管理装置は、第２の巡回群の元が格納された失効管理装置記憶部と、該第２の巡回群の位数Lおよび該第２の巡回群の元bを含む組の失効管理装置公開鍵rpkを生成し、前記ユーザ装置から前記素数e’を受信すると、前記元bを前記素数e’の逆数で前記位数Lを法としてべき乗剰余した前記Bの値を算出して前記ユーザ装置に送信する失効管理装置制御部とを有し、
前記検証装置は、前記メッセージおよび前記署名文を格納するための検証装置記憶部と、該メッセージおよび該署名文を受信すると、該メッセージと該署名文の候補を用いて検証を行って該署名文の候補の正当性を検証し、前記署名文の候補が正当であるか否かを出力する検証装置制御部とを有し、
前記開示装置は、前記メッセージおよび前記署名文を格納するための開示装置記憶部と、該メッセージおよび該署名文を受信し、該署名文が正当であると認識すると、該メッセージおよび該署名文と生成した開示装置公開鍵opkおよび開示装置秘密鍵oskを用いた復号化によるhを算出して出力する開示装置制御部とを有する、グループ署名システム。
【請求項２】
発行装置、開示装置、失効管理装置、ユーザ装置および検証装置がネットワークを介して互いに接続されたグループ署名システムであって、
前記発行装置は、第１の巡回群の元が格納された発行装置記憶部と、該第１の巡回群の位数Nならびに該第１の巡回群の元a＿0およびa＿1を含む組の発行装置公開鍵ipkを生成すると、該発行装置公開鍵ipkを公開する発行装置制御部とを有し、
前記ユーザ装置は、素数の集合が格納されたユーザ装置記憶部と、公開された前記発行装置公開鍵ipkを受信すると、素数eから該素数eよりも小さい定数を減じた結果が素数e’となる該素数eおよび該素数e’を求め、前記a＿0と前記a＿1を数xでべき乗剰余したものとの積が前記第１の巡回群の元Aを前記素数e乗したものに前記位数Nを法として等しい関係にあるものとする前記数xを含むユーザ装置秘密鍵mskと前記素数e、前記素数e’および前記元Aを含む組のユーザ装置公開鍵mpkとを生成し、該素数e’を前記失効管理装置に送信し、該素数e’を基にして算出されたBを前記失効管理装置から受信し、メッセージが入力されると、該Bの値、前記ユーザ装置公開鍵mpk、前記ユーザ装置秘密鍵msk、および該メッセージを用いて、該メッセージに対する署名文を生成し、該メッセージと該署名文を前記検証装置に送信するユーザ装置制御部とを有し、
前記失効管理装置は、第２の巡回群の元が格納された失効管理装置記憶部と、該第２の巡回群の位数Lおよび該第２の巡回群の元bを含む組の失効管理装置公開鍵rpkを生成し、前記ユーザ装置から前記素数e’を受信すると、前記元bを前記素数e’の逆数で前記位数Lを法としてべき乗剰余した前記Bの値を算出して前記ユーザ装置に送信する失効管理装置制御部とを有し、
前記検証装置は、前記メッセージおよび前記署名文を格納するための検証装置記憶部と、該メッセージおよび該署名文を受信すると、該メッセージと該署名文の候補を用いて検証を行って該署名文の候補の正当性を検証し、前記署名文の候補が正当であるか否かを出力する検証装置制御部とを有し、
前記開示装置は、前記メッセージおよび前記署名文を格納するための開示装置記憶部と、該メッセージおよび該署名文を受信し、該署名文が正当であると認識すると、該メッセージおよび該署名文と生成した開示装置公開鍵opkおよび開示装置秘密鍵oskを用いた復号化によるhを算出して出力する開示装置制御部とを有する、グループ署名システム。
【請求項３】
前記失効管理装置制御部は、前記失効管理装置公開鍵rpkと、グループから脱退するユーザ装置の前記素数e’を用いて前記Bの値を算出し、前記元bを該Bの値に置換し、前記失効管理装置公開鍵rpkを前記位数Lおよび前記Bの値を含む組のものに更新する、請求の範囲１または２記載のグループ署名システム。
【請求項４】
前記失効管理装置制御部は、更新された前記失効管理装置公開鍵rpkを公開し、
グループに残るユーザ装置の前記ユーザ装置制御部は、更新された前記失効管理装置公開鍵rpkを受信すると、グループから脱退したユーザ装置の前記素数e’と、e’＿0=  eとして定義されたe’＿0と、前記Bの値とを用いて、整数ξに前記e’＿0を乗じたものと整数ηに前記素数e’を乗じたものの和が１となるξおよびηを求め、さらに、前記Bの値をξ乗したものと前記元bから置換された該Bの値をη乗したものとの積を前記位数Lで剰余したものB’を計算し、前記Bの値を該B’の値に更新する、請求の範囲３記載のグループ署名システム。
【請求項５】
前記ユーザ装置制御部は、前記Bの値を受信すると、発行装置公開鍵ipk、失効管理装置公開鍵rpk、ユーザ装置公開鍵mpk、ユーザ装置秘密鍵mskおよび前記Bの値から、前記Bの知識の証明文となる前記署名文を求める、請求の範囲１または２記載のグループ署名システム。
【請求項６】
前記ユーザ装置制御部は、前記Bの値を受信すると、任意に乱数μ’＿e、乱数μ＿tおよび乱数ρ＿｛rev｝を選択し、予め定められた値wを前記ρ＿｛rev｝でべき乗剰余したものに前記Bの値をかけたものに対して前記位数Lを法として剰余したものB＿｛COM｝を算出し、前記素数e’に前記ρ＿｛rev｝を乗じたものtを算出し、前記値wを前記μ＿tでべき乗剰余したものに前記B＿｛COM｝をμ’＿eを-1倍したものでべき乗剰余したものを乗じたものに対して前記位数Lを法として剰余したものCOM＿｛rev｝を算出し、前記発行装置公開鍵ipkからメンバー公開鍵用コミットとなるCOM＿｛mpk｝を算出し、前記B＿｛COM｝、前記COM＿｛rev｝、および前記COM＿｛mpk｝を含む組のハッシュ値cを算出し、該ハッシュ値cに前記素数e’を乗じたものに前記μ’＿eを加えたものτ’＿eを算出し、さらに前記ハッシュ値cに前記tの値を乗じたものに前記μ＿tを加えたものτ＿tを算出し、前記τ’＿eと前記τ＿tを含む組を前記署名文として出力する、請求の範囲５記載のグループ署名システム。
【請求項７】
前記ユーザ装置制御部は、前記Bの値を受信すると、任意に乱数μ＿x、乱数μ＿s、乱数μ＿｛mpk｝および乱数ρ＿｛mpk｝を選択し、前記a＿2を前記ρ＿｛mpk｝でべき乗剰余したものに前記元Aを乗じたものに対して前記位数Nで剰余したものA＿｛COM｝を計算し、前記素数eに前記ρ＿｛mpk｝を乗じたものに前記数rを加えたものsを算出し、メンバー公開鍵用コミットとして、前記a＿1を前記μ＿xでべき乗剰余したものに前記a＿2をμ＿sでべき乗剰余したものを乗じたものに対して前記A＿｛COM｝をμ＿eを-1倍したものでべき乗剰余したものCOM＿｛mpk｝を計算し、予め定められた値wを前記ρ＿｛rev｝でべき乗剰余したものに前記Bの値をかけたものに対して前記位数Lを法として剰余したものB＿｛COM｝を算出し、前記素数e’に前記ρ＿｛rev｝を乗じたものtを算出し、前記値wを前記μ＿tでべき乗剰余したものに前記B＿｛COM｝をμ’＿eを-1倍したものでべき乗剰余したものを乗じたものに対して前記位数Lを法として剰余したものCOM＿｛rev｝を算出し、前記B＿｛COM｝と前記COM＿｛rev｝と前記A＿｛COM｝と前記COM＿｛mpk｝とを含む組のハッシュ値cを算出し、該ハッシュ値cに前記数xを乗じたものに前記μ＿xを加えたものτ＿xを算出し、前記ハッシュ値cに前記sの値を乗じたものに前記μ＿sを加えたものτ＿sを算出し、前記τ’＿e、前記τ＿x、前記τ＿t、および前記τ＿sを含む組を知識の証明文として前記署名文を出力する、請求の範囲１記載のグループ署名システム。
【請求項８】
前記ユーザ装置制御部は、前記Bの値を受信すると、任意に乱数μ＿x、乱数μ＿s、乱数μ＿｛mpk｝および乱数ρ＿｛mpk｝を選択し、定数a＿2を前記ρ＿｛mpk｝でべき乗剰余したものに前記元Aを乗じたものに対して前記位数Nで剰余したものA＿｛COM｝を算出し、前記素数eに前記ρ＿｛mpk｝を乗じたものsを算出し、メンバー公開鍵用コミットとして、前記a＿1を前記μ＿xでべき乗剰余したものに前記a＿2をμ＿sでべき乗剰余したものを乗じたもの前記A＿｛COM｝をμ＿eを-1倍したものでべき乗剰余したものCOM＿｛mpk｝を算出し、予め定められた値wを前記ρ＿｛rev｝でべき乗剰余したものに前記Bの値をかけたものに対して前記位数Lを法として剰余したものB＿｛COM｝を算出し、前記素数e’に前記ρ＿｛rev｝を乗じたものtを算出し、前記値wを前記μ＿tでべき乗剰余したものに前記B＿｛COM｝をμ’＿eを-1倍したものでべき乗剰余したものを乗じたものに対して前記位数Lを法として剰余したものCOM＿｛rev｝を算出し、前記B＿｛COM｝と前記COM＿｛rev｝と前記A＿｛COM｝と前記COM＿｛mpk｝とを含む組のハッシュ値cを算出し、該ハッシュ値cに前記数xを乗じたものに前記μ＿xを加えたものτ＿xを算出し、前記ハッシュ値cに前記sの値を乗じたものに前記μ＿sを加えたものτ＿sを算出し、前記τ’＿e、前記τ＿x、前記τ＿t、および前記τ＿sを含む組を知識の証明文として前記署名文を出力する、請求の範囲２記載のグループ署名システム。
【請求項９】
発行装置、開示装置、失効管理装置、ユーザ装置および検証装置がネットワークを介して互いに接続されたグループ署名システムによる情報処理方法であって、
前記発行装置が、第１の巡回群の位数Nならびに該第１の巡回群の元a＿0、a＿1およびa＿2を含む組の発行装置公開鍵ipkを生成すると、該発行装置公開鍵ipkを公開し、
前記ユーザ装置が、公開された前記発行装置公開鍵ipkを受信すると、素数eから該素数eよりも小さい定数を減じた結果が素数e’となる該素数eおよび該素数e’を求め、前記a＿0と前記a＿1を数xでべき乗剰余したものとの積に前記a＿2を数rでべき乗剰余したものの積が前記第１の巡回群の元Aを前記素数e乗したものに前記位数Nを法として等しい関係にあるものとする前記数xおよび前記数rを含む組のユーザ装置秘密鍵mskと前記素数e、前記素数e’および前記元Aを含む組のユーザ装置公開鍵mpkとを生成し、該素数e’を前記失効管理装置に送信し、
前記失効管理装置が、第２の巡回群の位数Lおよび該第２の巡回群の元bを含む組の失効管理装置公開鍵rpkを生成し、前記ユーザ装置から前記素数e’を受信すると、前記元bを前記素数e’の逆数で前記位数Lを法としてべき乗剰余したBの値を算出して前記ユーザ装置に送信し、
前記ユーザ装置が、前記Bの値を前記失効管理装置から受信し、メッセージが入力されると、該Bの値、前記ユーザ装置公開鍵mpk、前記ユーザ装置秘密鍵msk、および該メッセージを用いて、該メッセージに対する署名文を生成し、該メッセージと該署名文を前記検証装置に送信し、
前記検証装置が、前記メッセージと前記署名文を受信すると、該メッセージと該署名文の候補を用いて検証を行って該署名文の候補の正当性を検証し、前記署名文の候補が正当であるか否かを出力し、
前記開示装置が、前記メッセージと前記署名文とを受信し、該署名文が正当であると認識すると、該メッセージおよび該署名文と生成した開示装置公開鍵opkおよび開示装置秘密鍵oskを用いた復号化によるhを算出して出力する、情報処理方法。
【請求項１０】
発行装置、開示装置、失効管理装置、ユーザ装置および検証装置がネットワークを介して互いに接続されたグループ署名システムによる情報処理方法であって、
前記発行装置が、第１の巡回群の位数Nならびに該第１の巡回群の元a＿0およびa＿1を含む組の発行装置公開鍵ipkを生成すると、該発行装置公開鍵ipkを公開し、
前記ユーザ装置が、公開された前記発行装置公開鍵ipkを受信すると、素数eから該素数eよりも小さい定数を減じた結果が素数e’となる該素数eおよび該素数e’を求め、前記a＿0と前記a＿1を数xでべき乗剰余したものとの積が前記第１の巡回群の元Aを前記素数e乗したものに前記位数Nを法として等しい関係にあるものとする前記数xを含むユーザ装置秘密鍵mskと前記素数e、前記素数e’および前記元Aを含む組のユーザ装置公開鍵mpkとを生成し、該素数e’を前記失効管理装置に送信し、
前記失効管理装置が、第２の巡回群の位数Lおよび該第２の巡回群の元bを含む組の失効管理装置公開鍵rpkを生成し、前記ユーザ装置から前記素数e’を受信すると、前記元bを前記素数e’の逆数で前記位数Lを法としてべき乗剰余したBの値を算出して前記ユーザ装置に送信し、
前記ユーザ装置が、前記Bの値を前記失効管理装置から受信し、メッセージが入力されると、該Bの値、前記ユーザ装置公開鍵mpk、前記ユーザ装置秘密鍵msk、および該メッセージを用いて、該メッセージに対する署名文を生成し、該メッセージと該署名文を前記検証装置に送信し、
前記検証装置が、前記メッセージと前記署名文を受信すると、該メッセージと該署名文の候補を用いて検証を行って該署名文の候補の正当性を検証し、前記署名文の候補が正当であるか否かを出力し、
前記開示装置が、前記メッセージと前記署名文とを受信し、該署名文が正当であると認識すると、該メッセージおよび該署名文と生成した開示装置公開鍵opkおよび開示装置秘密鍵oskを用いた復号化によるhを算出して出力する、情報処理方法。
【請求項１１】
前記失効管理装置が、前記失効管理装置公開鍵rpkと、グループから脱退するユーザ装置の前記素数e’を用いて前記Bの値を算出し、前記元bを該Bの値に置換し、前記失効管理装置公開鍵rpkを前記位数Lおよび前記Bの値を含む組のものに更新する、請求の範囲９または１０記載の情報処理方法。
【請求項１２】
前記失効管理装置が、更新された前記失効管理装置公開鍵rpkを公開し、
グループに残るユーザ装置が、更新された前記失効管理装置公開鍵rpkと、グループから脱退したユーザ装置の前記素数e’と、e’＿0=  eとして定義されたe’＿0と、前記Bの値とを用いて、整数ξに前記e’＿0を乗じたものと整数ηに前記素数e’を乗じたものの和が１となるξおよびηを求め、さらに、前記Bの値をξ乗したものと前記元bから置換された該Bの値をη乗したものとの積を前記位数Lで剰余したものB’を計算し、前記Bの値を該B’の値に更新する、請求の範囲１１記載の情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザ装置をメンバーから脱退させる際の計算が効率的なグループ署名システム、および情報処理方法に関する。
【背景技術】
【０００２】
グループ署名方式はグループのメンバーに匿名で署名を生成することを可能にする方式である。この方式は電子投票、匿名委任、IDエスクローといったものに応用できるため、産業上の利用価値が高い。【０００３】
従来のグループ署名方式のシステムは、発行装置と、ユーザ装置と、検証装置とが設けられ、これらの装置が通信可能に接続されている。ユーザ装置が発行装置という権限にアクセスし、ユーザ装置が参加手段という手順を行い、発行装置が発行手順という手順を行うことでユーザ装置はグループのメンバーになることができる。グループのメンバーであるユーザ装置はグループのメンバーとしての署名文を生成できる。検証装置は、署名文の正当性を検証できるが、どの装置が署名文を作成したのかを特定することはできない。ただし、開示装置という権限のみはどの装置が署名文作成したのかを特定できる。【０００４】
一方、上記構成の他に、失効機能を持った方式がある。失効機能を持ったグループ署名方式には失効管理装置という権限がいる。ユーザ装置はグループのメンバーになる際に、失効管理装置にもアクセスし登録手段を行う。ユーザ装置がグループから抜ける際には、失効管理装置が失効手段を行うことでユーザ装置をグループから脱退させることができる。【０００５】
何台かのユーザ装置がグループから脱退したら、残りのユーザ装置は鍵更新手段を行うことで自分の持っている公開鍵・秘密鍵ペアをアップデートする。失効機能を持ったグループ署名方式の１つが、「Jan  Camenisch.  Jens  Groth.  Group  Signatures:  Better  Efficiency  and  New  Theoretical  Aspects.  SCN  2004,  vol.  3352  of  LNCS,  pp.  120-133,  2004.」（以下では、文献１と称する）で提案されている。【０００６】
また、別のグループ署名方式が、「G.  Ateniese,  J.  Camenisch,  M.  Joye,  and  G.  Tsudik.  A  Practical  and  Provably  Secure  Coalition-Resistant  Group  Signature  Scheme.  In  Advances  in  Cryptology  ---  CRYPTO  2000,  vol.  1880  of  LNCS,  pp.  255-270,  Springer-Verlag,  2000.」で提案されている。
【発明の開示】
【０００７】
鍵更新手段はユーザ装置がグループから脱退するたびに行わねばならない手順なので、グループに残るユーザ装置は頻繁に鍵更新手段を行わねばならない。このためグループ署名方式を実運用する際には鍵更新手段の計算量が可能な限り少ないことが望ましい。なお、ユーザ装置がグループに新規に加入する際の登録手段やグループから脱退する際の失効手段についても同様である。
【０００８】
本発明の目的は、上述したような従来の技術が有する問題点を解決するためになされたものであり、ユーザ装置のグループへの登録やグループからの脱退の際における情報処理の計算量を低減したグループ署名システム、および情報処理方法を提供することにある。
【０００９】
上記目的を達成するための本発明のグループ署名システムは、発行装置、開示装置、失効管理装置、ユーザ装置および検証装置がネットワークを介して互いに接続されたグループ署名システムであって、発行装置は、第１の巡回群の元が格納された発行装置記憶部と、第１の巡回群の位数Nならびに第１の巡回群の元a＿0、a＿1およびa＿2を含む組の発行装置公開鍵ipkを生成すると、発行装置公開鍵ipkを公開する発行装置制御部とを有し、ユーザ装置は、素数の集合が格納されたユーザ装置記憶部と、公開された発行装置公開鍵ipkを受信すると、素数eから該素数eよりも小さい定数を減じた結果が素数e’となる素数eおよび素数e’を求め、上記a＿0と上記a＿1を数xでべき乗剰余したものとの積に上記a＿2を数rでべき乗剰余したものの積が第１の巡回群の元Aを素数e乗したものに上記位数Nを法として等しい関係にあるものとする上記数xおよび上記数rを含む組のユーザ装置秘密鍵mskと素数e、素数e’および元Aを含む組のユーザ装置公開鍵mpkとを生成し、素数e’を失効管理装置に送信し、素数e’を基にして算出されたBを失効管理装置から受信し、メッセージが入力されると、受信したBの値、ユーザ装置公開鍵mpk、ユーザ装置秘密鍵msk、およびそのメッセージを用いて、メッセージに対する署名文を生成し、メッセージと署名文を検証装置に送信するユーザ装置制御部とを有し、失効管理装置は、第２の巡回群の元が格納された失効管理装置記憶部と、第２の巡回群の位数Lおよび第２の巡回群の元bを含む組の失効管理装置公開鍵rpkを生成し、ユーザ装置から素数e’を受信すると、上記元bを素数e’の逆数で上記位数Lを法としてべき乗剰余した上記Bの値を算出してユーザ装置に送信する失効管理装置制御部とを有し、検証装置は、上記メッセージおよび署名文を格納するための検証装置記憶部と、メッセージおよび署名文を受信すると、メッセージと署名文の候補を用いて検証を行って署名文の候補の正当性を検証し、署名文の候補が正当であるか否かを出力する検証装置制御部とを有し、開示装置は、上記メッセージおよび署名文を格納するための開示装置記憶部と、メッセージおよび署名文を受信し、署名文が正当であると認識すると、メッセージおよび署名文と生成した開示装置公開鍵opkおよび開示装置秘密鍵oskを用いた復号化によるhを算出して出力する開示装置制御部とを有する構成である。
【００１０】
また、本発明のグループ署名システムは、発行装置、開示装置、失効管理装置、ユーザ装置および検証装置がネットワークを介して互いに接続されたグループ署名システムであって、発行装置は、第１の巡回群の元が格納された発行装置記憶部と、第１の巡回群の位数Nならびに第１の巡回群の元a＿0およびa＿1を含む組の発行装置公開鍵ipkを生成すると、発行装置公開鍵ipkを公開する発行装置制御部とを有し、ユーザ装置は、素数の集合が格納されたユーザ装置記憶部と、公開された発行装置公開鍵ipkを受信すると、素数eから該素数eよりも小さい定数を減じた結果が素数e’となる素数eおよび素数e’を求め、上記a＿0と上記a＿1を数xでべき乗剰余したものとの積が第１の巡回群の元Aを素数e乗したものに上記位数Nを法として等しい関係にあるものとする上記数xを含むユーザ装置秘密鍵mskと素数e、素数e’および元Aを含む組のユーザ装置公開鍵mpkとを生成し、素数e’を失効管理装置に送信し、素数e’を基にして算出されたBを失効管理装置から受信し、メッセージが入力されると、上記Bの値、ユーザ装置公開鍵mpk、ユーザ装置秘密鍵msk、およびメッセージを用いて、メッセージに対する署名文を生成し、メッセージと署名文を検証装置に送信するユーザ装置制御部とを有し、失効管理装置は、第２の巡回群の元が格納された失効管理装置記憶部と、第２の巡回群の位数Lおよび第２の巡回群の元bを含む組の失効管理装置公開鍵rpkを生成し、ユーザ装置から素数e’を受信すると、上記元bを素数e’の逆数で上記位数Lを法としてべき乗剰余した上記Bの値を算出してユーザ装置に送信する失効管理装置制御部とを有し、検証装置は、上記メッセージおよび署名文を格納するための検証装置記憶部と、メッセージおよび署名文を受信すると、メッセージと署名文の候補を用いて検証を行って署名文の候補の正当性を検証し、署名文の候補が正当であるか否かを出力する検証装置制御部とを有し、開示装置は、上記メッセージおよび署名文を格納するための開示装置記憶部と、メッセージおよび署名文を受信し、署名文が正当であると認識すると、メッセージおよび署名文と生成した開示装置公開鍵opkおよび開示装置秘密鍵oskを用いた復号化によるhを算出して出力する開示装置制御部とを有する構成である。
【００１１】
一方、上記目的を達成するための本発明の情報処理方法は、発行装置、開示装置、失効管理装置、ユーザ装置および検証装置がネットワークを介して互いに接続されたグループ署名システムによる情報処理方法であって、発行装置が、第１の巡回群の位数Nならびに第１の巡回群の元a＿0、a＿1およびa＿2を含む組の発行装置公開鍵ipkを生成すると、発行装置公開鍵ipkを公開し、ユーザ装置が、公開された発行装置公開鍵ipkを受信すると、素数eから該素数eよりも小さい定数を減じた結果が素数e’となる素数eおよび素数e’を求め、上記a＿0と上記a＿1を数xでべき乗剰余したものとの積に上記a＿2を数rでべき乗剰余したものの積が第１の巡回群の元Aを素数e乗したものに上記位数Nを法として等しい関係にあるものとする上記数xおよび上記数rを含む組のユーザ装置秘密鍵mskと素数e、素数e’および元Aを含む組のユーザ装置公開鍵mpkとを生成し、素数e’を失効管理装置に送信し、失効管理装置が、第２の巡回群の位数Lおよび第２の巡回群の元bを含む組の失効管理装置公開鍵rpkを生成し、ユーザ装置から素数e’を受信すると、上記元bを素数e’の逆数で上記位数Lを法としてべき乗剰余したBを算出してユーザ装置に送信し、ユーザ装置が、上記Bの値を失効管理装置から受信し、メッセージが入力されると、上記Bの値、ユーザ装置公開鍵mpk、ユーザ装置秘密鍵msk、およびメッセージを用いて、メッセージに対する署名文を生成し、メッセージと署名文を検証装置に送信し、検証装置が、上記メッセージと署名文を受信すると、メッセージと署名文の候補を用いて検証を行って署名文の候補の正当性を検証し、署名文の候補が正当であるか否かを出力し、開示装置が、上記メッセージと署名文とを受信し、署名文が正当であると認識すると、メッセージおよび署名文と生成した開示装置公開鍵opkおよび開示装置秘密鍵oskを用いた復号化によるhを算出して出力するものである。
【００１２】
また、本発明の情報処理方法は、発行装置、開示装置、失効管理装置、ユーザ装置および検証装置がネットワークを介して互いに接続されたグループ署名システムによる情報処理方法であって、発行装置が、第１の巡回群の位数Nならびに第１の巡回群の元a＿0およびa＿1を含む組の発行装置公開鍵ipkを生成すると、発行装置公開鍵ipkを公開し、ユーザ装置が、公開された発行装置公開鍵ipkを受信すると、素数eから該素数eよりも小さい定数を減じた結果が素数e’となる素数eおよび素数e’を求め、上記a＿0と上記a＿1を数xでべき乗剰余したものとの積が第１の巡回群の元Aを素数e乗したものに上記位数Nを法として等しい関係にあるものとする上記数xを含むユーザ装置秘密鍵mskと素数e、素数e’および元Aを含む組のユーザ装置公開鍵mpkとを生成し、素数e’を失効管理装置に送信し、失効管理装置が、第２の巡回群の位数Lおよび第２の巡回群の元bを含む組の失効管理装置公開鍵rpkを生成し、ユーザ装置から素数e’を受信すると、上記元bを素数e’の逆数で上記位数Lを法としてべき乗剰余したBを算出してユーザ装置に送信し、ユーザ装置が、上記Bの値を失効管理装置から受信し、メッセージが入力されると、上記Bの値、ユーザ装置公開鍵mpk、ユーザ装置秘密鍵msk、およびメッセージを用いて、メッセージに対する署名文を生成し、メッセージと署名文を検証装置に送信し、検証装置が、上記メッセージと署名文を受信すると、メッセージと署名文の候補を用いて検証を行って署名文の候補の正当性を検証し、署名文の候補が正当であるか否かを出力し、開示装置が、上記メッセージと署名文とを受信し、署名文が正当であると認識すると、メッセージおよび署名文と生成した開示装置公開鍵opkおよび開示装置秘密鍵oskを用いた復号化によるhを算出して出力するものである。
【００１３】
本発明では、ユーザ装置が従来ビット数の長い素数eとは別のe’を用いることで、秘密鍵および公開鍵の生成についての計算量が低減する。また、このe’の値を用いてユーザ装置の登録に関する情報を計算する失効管理装置の計算量も低減する。したがって、新たにグループに加入するユーザ装置が登録のために行う計算量などが従来よりも少なくなる。
【図面の簡単な説明】
【００１４】
【図１】図１は実施形態1のグループ署名システムの一構成例を示したブロック図である。
【図２】図２は実施形態1のデータの送受信を示したフローチャートである。
【図３】図３は実施形態1のデータの送受信を示したフローチャートである。
【図４】図４は実施形態1の発行装置鍵生成手段を示したフローチャートである。
【図５】図５は実施形態1の開示装置鍵生成手段を示したフローチャートである。
【図６】図６は実施形態1の失効管理装置鍵生成手段を示したフローチャートである。
【図７】図７は実施形態1の発行参加手段を示したフローチャートである。
【図８】図８は実施形態1の参加第一手段を示したフローチャートである。
【図９】図９は実施形態1の発行手段を示したフローチャートである。
【図１０】図１０は実施形態1の参加第二手段を示したフローチャートである。
【図１１】図１１は実施形態1の登録手段を示したフローチャートである。
【図１２】図１２は実施形態1の失効手段を示したフローチャートである。
【図１３】図１３は実施形態1の鍵更新手段を示したフローチャートである。
【図１４】図１４は実施形態1の署名手段を示したフローチャートである。
【図１５】図１５は実施形態1の署名手段を示したフローチャートである。
【図１６】図１６は実施形態1の暗号文用コミット手段を示したフローチャートである。
【図１７】図１７は実施形態1のメンバー公開鍵用コミット手段を示したフローチャートである。
【図１８】図１８は実施形態1の失効データ用コミット手段を示したフローチャートである。
【図１９】図１９は実施形態1の検証手段を示したフローチャートである。
【図２０】図２０は実施形態1の暗号文用コミット再生手段を示したフローチャートである。
【図２１】図２１は実施形態1のメンバー公開鍵用コミット再生手段を示したフローチャートである。
【図２２】図２２は実施形態1の失効データ用コミット再生手段を示したフローチャートである。
【図２３】図２３は実施形態1の開示手段を示したフローチャートである。
【図２４】図２４は実施形態1の暗号鍵生成手段を示したフローチャートである。
【図２５】図２５は実施形態1の暗号化手段を示したフローチャートである。
【図２６】図２６は実施形態1の復号化手段を示したフローチャートである。
【図２７】図２７は実施形態2の発行装置鍵生成手段を示したフローチャートである。
【図２８】図２８は実施形態2の発行参加手段を示したフローチャートである。
【図２９】図２９は実施形態2の参加第一手段を示したフローチャートである。
【図３０】図３０は実施形態2の発行第一手段を示したフローチャートである。
【図３１】図３１は実施形態2の参加第二手段を示したフローチャートである。
【図３２】図３２は実施形態2の発行第二手段を示したフローチャートである。
【図３３】図３３は実施形態2の参加第三手段を示したフローチャートである。
【図３４】図３４は実施形態2の署名手段を示したフローチャートである。
【図３５】図３５は実施形態2の署名手段を示したフローチャートである。
【符号の説明】
【００１５】
１００    発行装置
２００    開示装置
３００    失効管理装置
４００    ユーザ装置
５００    検証装置
【発明を実施するための最良の形態】
【００１６】
（実施形態１）
[装置構成]
本実施形態のグループ署名システムの構成を説明する。図1は実施形態1のグループ署名システムの一構成例を示すブロック図である。図1に示すように、グループ署名システムは、発行装置100と、開示装置200と、失効管理装置300と、ユーザ装置400と、検証装置500とを有する。【００１７】
発行装置100は、発行装置制御部190と、発行装置記憶部110と、発行装置通信手段（不図示）とを有する。発行装置制御部190は、発行装置鍵生成手段120と、発行手段130とを有する。【００１８】
開示装置200は、開示装置制御部290と、開示装置記憶部210と、開示装置通信手段（不図示）とを有する。開示装置制御部290は、開示装置鍵生成手段220と、開示手段230とを有する。【００１９】
失効管理装置300は、失効管理装置制御部390と、失効管理装置記憶部310と、失効管理装置通信手段（不図示）とを有する。失効管理装置制御部390は、失効管理装置鍵生成手段320と、登録手段330と、失効手段340とを有する。【００２０】
ユーザ装置400は、ユーザ装置制御部490と、ユーザ装置記憶部410と、ユーザ装置通信手段（不図示）とを有する。ユーザ装置制御部490は、参加手段420と、鍵更新手段430と、署名手段440とを有する。ユーザ装置400はグループに属する数だけ他の装置と通信可能に接続されるが、本実施形態では、説明を簡単にするために、ユーザ装置を１台だけ図１に示す。【００２１】
検証装置500は、検証装置制御部590と、検証装置記憶部510と、検証装置通信手段（不図示）とを有する。検証装置制御部590 は検証手段520を有する。
[装置の実装]
各装置の制御部は、通信部の制御、記憶部の制御、およびデータの演算処理を行う。制御部には、プログラムに従って所定の処理を実行するCPU（Central  Processing  Unit）、およびプログラムを格納するためのメモリが設けられている。各制御部の手段は、CPUがプログラムを実行することで装置内に仮想的に構成される。【００２２】
各装置の記憶部にはハードディスクや半導体メモリなどを用いることができる。【００２３】
各装置は通信ネットワークを介して相互に接続されている。通信ネットワークとして、例えば、インターネットやLAN（Local  Area  Network）を用いることができる。通信ネットワークは有線および無線のいずれでもよく、また有線と無線の組み合わせでもよい。なお、図１では装置間における情報の流れをわかりやすくするために、各装置の通信部を図に示すことを省略している。【００２４】
[記号]
κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）をセキュリティ・パラメータで、κ’＿e＜κ＿eを満たしているものとする。
安全性の観点から言えばκ'＿e+κ＿c+κ＿S＜κ＿qとκ＿q+κ＿c+κ＿S＜κ＿e＜κ＿N/2を満たしていることが望ましい。
自然数Nに対し、位数Nの巡回群｛0,…,N-1｝をZ＿Nと書き、Z＿N上の平方剰余全体の集合をQR（N）と書く。
Uを有限巡回群とし、gをUの元とし、qをUの位数とする。
Uとしてどのようなものを選んでもかまわないが、安全性の観点から言えばある素数pに対するZ＿pの乗法群の部分群、もしくは楕円曲線群の部分群であることが望ましい。
Hashを｛0,…,2^｛κ＿c｝｝に値を取るハッシュ関数とする。【００２５】
[データ送受信]
各装置は事前にUの詳細、κ、g、およびqを事前に自身の記憶部に保管していると仮定する。これらのデータをどのように共有するのかは問わない。
本発明ではProt1-1,…,Prot1-16が執り行われる（図2、図3）。
Prot1-1:発行装置100は発行装置鍵生成手段120を行い、発行装置公開鍵ipkと発行装置秘密鍵iskを生成し、発行装置公開鍵ipkを公開する（ステップ910101）。
Prot1-2:開示装置200は開示装置鍵生成手段220を行い、開示装置公開鍵opkと開示装置秘密鍵oskを生成し、開示装置公開鍵opkを公開する（ステップ910102）。
Prot1-3:失効管理装置300は失効管理装置鍵生成手段320を行い、失効管理装置公開鍵rpkと失効管理装置秘密鍵rskを生成し、失効管理装置公開鍵rpkを公開する（ステップ910103）。
公開鍵の公開方法は問わない。公開方法として、例えば、PKIを使う、各装置に直接公開鍵を送る、といった方法がある。以後の手順では全ての装置がipk、opk、rpkを自身の記憶部に保存していると仮定する。【００２６】
Prot1-4:発行装置100とユーザ装置400は発行参加手段を行う（ステップ910104）。
発行参加手段は発行装置100が行う手順とユーザ装置400が行う手順とに分かれ、前を発行手段130、後を参加手段420という。
発行参加手段が終了すると、発行装置100はユーザ装置400の公開鍵mpkを取得し、ユーザ装置400は自身の公開鍵mpkと秘密鍵mskを得る。
発行参加手段を終えたユーザ装置400をグループのメンバーとも呼ぶ。【００２７】
Prot1-5:ユーザ装置400はmpkの一部であるデータe’を失効管理装置300に送信する（ステップ910105）。
Prot1-6:失効管理装置300はe’を受信したら失効管理装置記憶部310に書き込む（ステップ9101106）。
Prot1-7:受信したe’を使って登録手段300を行い、登録手段300の出力Bをユーザ装置400に送信する（ステップ910107）。
Prot1-8:ユーザ装置400はBを受信したらBをユーザ装置記憶部410に書き込む（ステップ910108）。
グループのメンバーであるユーザ装置400は、署名手段440を行うことでメッセージに署名することができる。メッセージを誰がどのように選び、どのようにユーザ装置400に入力するかは問わない。例えば、ユーザ装置400を動かしている人がキーボードでメッセージをユーザ装置に入力するという方法がある。【００２８】
Prot1-9:検証装置500はメッセージ・署名文ペアで受け取り、検証装置記憶部510に保存する（ステップ910109）。
Prot1-10:検証装置500はメッセージ・署名文ペアを使って検証手段520を行うことで、署名文の正当性を検証する（ステップ910110）。
Prot1-11:検証手段520を終えたら検証装置500は、署名文が正当であったか否かを出力する（ステップ910111）。
検証装置500がいつどのような手段で署名文を受け取ったのかは問わない。例えば、ユーザ装置400がインターネットを使って検証装置500に署名文を送るという方法がある。【００２９】
本実施形態では、署名文が正当であった場合には、「accept」という文字列を、そうでなければ「reject」という文字列を出力するものとして説明しているが、他の文字列ないし文字列でないデータを出力してもかまわない。これは、他の実施形態についても同様である。
開示装置200は何らかの方法でメッセージ・署名文ペアを受け取る。どのようにしてメッセージ・署名文ペアを得たのかは問わない。例えば、検証装置500がインターネットを使って開示装置200に送信するという方法がある。【００３０】
Prot1-12:開示装置200は受け取ったメッセージ・署名文ペアを開示装置記憶部210に書き込む（ステップ910112）。
Prot1-13:開示装置200はメッセージ・署名文ペアを入力して開示手段230を行う（ステップ910113）。
Prot1-14:開示手段230は署名を行ったユーザ装置400の公開鍵の一部hを出力するので、開示装置200はhを出力する（ステップ910114）。
失効管理装置300はグループから脱退させたいユーザ装置400のe’を入力して失効手段340を行うことでそのユーザ装置400をグループから脱退させることができる。【００３１】
Prot1-15:失効手段340を行うと失効管理装置300の公開鍵rpkが更新されるので、新しいrpkを公開する。さらに失効手段340はメンバーの資格を失効したユーザ装置400に関する情報のリストREVLISTを出力するので、REVLISTも公開する（ステップ910115）。【００３２】
LEVRISTや新しいrpkの公開方法は問わない。公開方法として例えば、PKIを使う、各装置に直接公開鍵を送る、といった方法がある。以後の手順では全ての装置がREVLISTや新しいrpkを自身の記憶部に保存していると仮定する。
Prot1-16:各ユーザ装置400はLEVRISTを使って鍵更新手段430を行い、ユーザ装置400のBを更新する（ステップ910116）。【００３３】
[メンバー公開鍵リスト]
本発明を用いる際には、グループのメンバーであるユーザ装置のIDとそのユーザ装置の公開鍵mpkとのペアのリストを公開しておく必要がある。誰がどのような形でこのリストを公開してもよいが、リスト中のデータが正確であることを保証する必要がある。【００３４】
リスト中のデータの正確性を保証する方法の一つを説明する。リストは発行装置100が管理する。リスト中には、IDとmpkのみならず、IDとmpkに対するユーザ装置400の（PKIの公開鍵を用いて作成した）署名文を載せる。
そして発行はリスト全体に（PKIの公開鍵を用いて）署名をつけてリストと署名文を公開する。開示装置がhを出力したら、リストに載っているmpkでhを部分として含むものを探し出し、そのmpkに対応するIDを探すことで、署名であるユーザ装置400を特定できる。【００３５】
[発行装置鍵生成手段120]
発行装置100は以下のISSGEN1-1,…,ISSGEN1-5を順に行う（図4）。
ISSGEN1-1:発行装置記憶部110からκ＿Nを読み込む（ステップ120101）。
ISSGEN1-2:素数p＿1,  p＿2で積N=p＿1p＿2がκ＿Nビットのものを選ぶ（ステップ120102）。
ISSGEN1-3:QR（N）の元a＿0,a＿1,a＿2をランダムに選ぶ（ステップ120103）。
ISSGEN1-4:（p＿1,p＿2）を発行装置100秘密鍵iskにセットし、iskを発行装置記憶部110に書き込む（ステップ120104）。
ISSGEN1-5:（N,a＿0,a＿1,a＿2）を発行装置100公開鍵ipkにセットし、ipkを発行装置記憶部110に書き込み、そしてipkを出力する（ステップ120105）。
安全性の観点から言えば、ISS1-1で（p＿1-1）/2,  （p＿2-1）/2も素数であることが望ましい。また、ISS1-1でp＿1のビット数とp＿2のビット数はほぼ同じであることが望ましい。【００３６】
[開示装置鍵生成手段220]
開示装置200は以下のOPNGEN1-1,…,OPNGEN1-3を行う（図5）。
OPNGEN1-1:[暗号鍵生成手段]を行い、公開鍵opkと秘密鍵oskを生成する（ステップ220101）。
OPNGEN1-2:oskを開示装置200秘密鍵にセットし、oskを開示装置記憶部210に書き込む（ステップ220102）。
OPNGEN1-3:opkを開示装置200公開鍵にセットし、opkを開示装置記憶部210に書き込み、そしてopkを出力する（ステップ220103）。【００３７】
[失効管理装置鍵生成手段320]
失効管理装置300は以下のREVGEN1-1,…,REVGEN1-7を行う（図6）。
REVGEN1-1:失効管理装置記憶部310からκ＿Lを読み込む（ステップ320101）。
REVGEN1-2:素数l＿1,  l＿2で積N=l＿1l＿2がκ＿Lビットのものを選ぶ（ステップ320102）。
REVGEN1-3:QR（L）の元b、wをランダムに選ぶ（ステップ320103）。
REVGEN1-4:（l＿1,l＿2）を失効管理装置300秘密鍵rskにセットし、rskを失効管理装置記憶部310に書き込む（ステップ320104）。
REVGEN1-5:REVLISTを空集合にセットし、REVLISTを失効管理装置記憶部310に書き込む（ステップ320105）。
REVGEN1-6:（L,b,w）を失効管理装置300公開鍵rpkにセットし、rpkを失効管理装置記憶部310に書き込む（ステップ320106）。
REVGEN1-7:REVLISTとrpkを出力する（ステップ320107）。
安全性の観点から言えば、REVGEN1-1で（l＿1-1）/2,  （l＿2-1）/2も素数であることが望ましい。また、REVGEN1-1でl＿1のビット数とl＿2のビット数はほぼ同じであることが望ましい。【００３８】
[発行参加手段]
発行参加手段では発行装置100とユーザ装置400とがそれぞれ発行手段130と参加手段420を行う。参加手段420は参加第一手段と参加第二手段とからなる。発行参加手段では以下のISSJOIN1-1,…,ISSJOIN1-5が順に行われる（図7）。
ISSJOIN1-1:ユーザ装置400は参加第一手段を行い、参加第一手段の出力を発行装置100に送信する（ステップ920101）。
ISSJOIN1-2:発行装置100は受信したデータを発行装置記憶部110に書き込む（ステップ920102）。
ISSJOIN1-3:発行装置100は発行手段130を行い、発行手段130の出力をユーザ装置400に送信する（ステップ920103）。
ISSJOIN1-4:ユーザ装置400は受信したデータをユーザ装置記憶部410に書き込む（ステップ920104）。
ISSJOIN1-5:ユーザ装置400は参加第二手段を行う（ステップ920105）。【００３９】
[参加第一手段]
ユーザ装置400は以下のJOIN1-1-1,…,JOIN1-1-5を順に行う（図8）。
JOIN1-1-1:κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）、ipk=（N,a＿0,a＿1,a＿2）、q、gをユーザ装置記憶部410から読み込む（ステップ4201101）。
JOIN1-1-2:0以上q未満の整数xと、0以上N未満の整数r’をランダムに選ぶ（ステップ4201102）。
JOIN1-1-3:A’=a＿1^xa＿2^｛r’｝  mod  Nとh=g^xを計算し、A’とhの正当性証明文pf＿｛A’,h｝を計算する（ステップ4201103）。
JOIN1-1-4:x、r’、A’、h、pf＿｛A’,h｝  をユーザ装置記憶部410に書き込む（ステップ4201104）。
JOIN1-1-5:A’、h、pf＿｛A’,h｝  を出力する（ステップ4201105）。
なお、pf＿｛A’,h｝の計算方法の詳細は[文献1]に開示されているため、ここでは、その説明を省略する。【００４０】
[発行手段130]
発行装置100は以下のISSUE1-1,…,ISSUE1-7を順に行う（図9）。
ISSUE1-1:κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）、ipk=（N,a＿0,a＿1,a＿2）、isk=（p＿1,p＿2）、g、A’、h、pf＿｛A’,h｝を発行装置記憶部110から読み込む（ステップ130101）。
ISSUE1-2:pf＿｛A’,h｝の正当性を検証し、もし正当でなければ発行参加手段130を終了する（ステップ130102）。
ISSUE1-3:κ'＿eビットの素数e’で、e=2^｛κ＿e｝+e’も素数であるものをランダムに選ぶ（ステップ130103）。
ISSUE1-4:0以上e未満の整数r’’をランダムに選ぶ（ステップ130104）。
ISSUE1-5:A’’=（a＿0A’a＿2^｛r’’｝）^｛1/e｝  mod  Nを計算する（ステップ130105）。
ISSUE1-6:（A’’,e’,r’’）を発行装置記憶部110に書き込む（ステップ130106）。
ISSUE1-7:（A’’,e’,r’’）を出力する（ステップ130107）。
なお、pf＿｛A’,h｝の検証方法の詳細は[文献1]に開示されているため、ここでは、その説明を省略する。【００４１】
[参加第二手段]
ユーザ装置400は以下のJOIN1-2-1,…,JOIN1-2-7を順に行う（図10）。
JOIN1-2-1:ユーザ装置記憶部410からa＿0,a＿1,a＿2,x,r’,r’’,A’’,  N,  e’,hを読み込む（ステップ4201201）。
JOIN1-2-2:e=2^｛κ＿e｝+e’を計算する（ステップ4201202）。
JOIN1-2-3:r’+r’’をeで割ったときの商をRとし、余りをrとする（ステップ4201203）。
JOIN1-2-4:A=A’’/a＿2^R  mod  Nとする（ステップ4201204）。
JOIN1-2-5:a＿0a＿1^xa＿2^r=A^e  mod  Nが成立するかどうかを確認し、もし成立していなければ発行参加手段130を終了する（ステップ4201205）。
JOIN1-2-6:（x,r）をメンバー秘密鍵mskにセットし、mskをユーザ装置記憶部410に書き込む（ステップ4201206）。
JOIN1-2-7:（A,e,e’,h）をメンバー公開鍵mpkにセットし、mpkをユーザ装置記憶部410に書き込む（ステップ4201207）。【００４２】
[登録手段330]
失効管理装置300は以下のADD1-1,…,ADD1-4を順に行う（図11）。
ADD1-1:rpk=（L,b,w）とe’を失効管理装置記憶部310から読み込む（ステップ330101）。
ADD1-2:e’が素数であるかどうかを確認し、もし素数でなければ終了する（ステップ330102）。
ADD1-3:B=b^｛1/e’｝  mod  Lを計算する（ステップ330103）。
ADD1-4:Bを出力する（ステップ330104）。【００４３】
[失効手段340]
失効管理装置300はグループから脱退させたいユーザ装置のe’を使って以下のREV1-1,…,REV1-4を順に行う（図12）。
REV1-1:rpk=（L,b,w）、e’を失効管理装置記憶部310から読み込む（ステップ340101）。
REV1-2:B=b^｛1/e’｝  mod  Lを計算する（ステップ340102）。
REV1-3:bをBに置き換え、rpkを（L,B,w）に再セットする（ステップ340103）。
REV1-4:e’＿0=e’とする（ステップ340104）。
REV1-5:rpkを失効管理装置記憶部310に書き込み、e’＿0と新しいrpkとを出力する（ステップ340105）。【００４４】
[鍵更新手段430]
ユーザ装置400は以下のUPDATE1-1,…,UPDATE1-4を順に行う（図13）。
UPDATE1-1:B,e’,e’＿0,rpk=（L,b,w）をユーザ装置記憶部410から読み込む（ステップ430101）。
UPDATE1-2:整数ξ、ηでξe’＿0+ηe’=1を満たすものを見つける（ステップ430102）。
UPDATE1-3:B’=B^ξb^η  mod  Lを計算する（ステップ430103）。
UPDATE1-4:BをB’に再セットし、新しいBを記憶部に書き込む（ステップ430104）。
UPDATE1-2で、例えば、拡張ユークリッド互助法を行うことでξ、ηを見つけることができる。【００４５】
[署名手段440]
ユーザ装置400は以下のSIGN1-1,…,  SIGN1-15を行う（図14、図15）。
SIGN1-1:  κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）、ipk=（N,a＿0,a＿1,a＿2）、opk、q、rpk=（L,b,w）、mpk=（A,e,e’,h）、msk=（x,r）、Bをユーザ装置記憶部410から読み込む（ステップ440101）。
SIGN1-2:  メッセージMを読み込む（ステップ440102）。
SIGN1-3:  Z＿qの元ρ＿｛Cipher｝をランダムに選び、[暗号化手段]を行って  Cipherを計算する（ステップ440103）。
SIGN1-4:  κ＿N/2ビットの自然数ρ＿｛mpk｝をランダムに選び、A＿｛COM｝=Aa＿2^｛ρ＿｛mpk｝｝  mod  Nを計算する（ステップ440104）。
SIGN1-5:  s=r+ρ＿｛mpk｝eを計算する（ステップ440105）。
SIGN1-6:  κ＿L/2ビットの自然数ρ＿｛rev｝をランダムに選び、B＿｛COM｝=Bw^｛ρ＿｛rev｝｝  mod  L  を計算する（ステップ440106）。
SIGN1-7:  t=e’ρ＿｛rev｝を計算する（ステップ440107）。
SIGN1-8:  κ＿Q+κ＿c+κ＿Sビットの自然数μ＿x、（κ＿N/2）  +κ＿c+κ＿Sビットの自然数μ＿s、κ’＿e+κ＿c+κ＿Sビットの自然数μ’＿e、（κ＿L/2）  +κ＿c+κ＿Sビットの自然数μ＿t、Z＿qの元μ＿｛Cipher｝、（κ＿N/2）  +κ＿c+κ＿Sビットの自然数μ＿｛mpk｝、（κ＿L/2）  +κ＿c+κ＿Sビットの自然数μ＿｛rev｝ランダムに選ぶ（ステップ440108）。
SIGN1-9:  Cipher、μ＿x、μ＿｛Cipher｝、opk、gを入力して[暗号文用コミット手段]を行ってその出力COM＿｛Cipher｝を得る（ステップ440109）。
SIGN1-10:μ＿x、μ＿s、μ’＿e、A＿｛COM｝、ipkを入力して[メンバー公開鍵用コミット手段]を行ってその出力COM＿｛mpk｝を得る（ステップ440110）。
SIGN1-11:  μ’＿e、μ＿t、B＿｛COM｝、rpkを入力して[失効データ用コミット手段]を行ってその出力COM＿｛rev｝を得る（ステップ440111）。
SIGN1-12:  c=Hash（κ,  ipk,  opk,  q,  rpk,  Cipher,  A＿｛COM｝,  B＿｛COM｝,  COM＿｛Cipher｝,  COM＿｛mpk｝,  COM＿｛rev｝,  M）を計算する（ステップ440112）。
SIGN1-13:  τ＿x=cx+μ＿x、τ＿s=cs+μ＿s、τ’＿e=ce’+μ’＿e、τ＿t=ct+μ＿tを計算する（ステップ440113）。
SIGN1-14:  τ＿｛Cipher｝=cμ＿｛Cipher｝+ρ＿｛Cipher｝  mod  qを計算する。（ステップ440114）
SIGN1-15:  （Cipher,A＿｛COM｝,B＿｛COM｝,c,τ＿x,τ＿s,τ’＿e,τ＿t,τ＿｛Cipher｝,τ＿｛mpk｝,τ＿｛rev｝）をSignatureにセットし、Signatureを出力する（ステップ440115）。【００４６】
[暗号文用コミット手段]
ユーザ装置400は以下のCOMCIPHER1-1,…,  COMCIPHER1-3を行う（図16）。
COMCIPHER1-1:  Cipher=（Cipher＿0,Cipher＿1,Cipher＿2）、μ＿x、μ＿｛Cipher｝、opk=（u＿0,u＿1,u＿2）、gを入力として受け取る（ステップ940101）。
COMCIPHER1-2:  COM＿｛Cipher＿0｝  =  u＿0^｛μ＿｛Cipher｝｝、COM＿｛Cipher＿1｝  =  u＿1^｛μ＿｛Cipher｝｝、COM＿｛Cipher＿2｝  =  g^｛μ＿x｝u＿2^｛μ＿｛Cipher｝｝とする（ステップ940102）。
COMCIPHER1-3:  COM＿｛Cipher｝=（COM＿｛Cipher＿0｝,COM＿｛Cipher＿1｝,COM＿｛Cipher＿2｝）を計算する（ステップ940103）。【００４７】
[メンバー公開鍵用コミット手段]
ユーザ装置400は以下のCOMMPK1-1,COMMPK1-2を行う（図17）。
COMMPK1-1:  μ＿x、μ＿s、μ’＿e、A＿｛COM｝、ipk=（N,a＿0,a＿1,a＿2）を入力して受け取る（ステップ950101）。
COMMPK1-2:  COM＿｛mpk｝=  a＿1^｛μ＿x｝a＿2^｛μ＿s｝A＿｛COM｝^｛-μ＿e｝  mod  N  を計算する（ステップ950102）。【００４８】
[失効データ用コミット手段]
ユーザ装置400は以下のCOMREV1-1,COMREV1-2を行う（図18）。
COMREV1-1:  μ’＿e、μ＿t、B＿｛COM｝、rpk=（L,b,w）を入力として受け取る（ステップ960101）。
COMREV1-2:  COM＿｛rev｝  =  w^｛μ＿t｝B＿｛COM｝^｛-μ’＿e｝  mod  Lを計算する（ステップ960102）。【００４９】
[検証手段520]
検証装置500は以下のVER1-1,…,VER1-7を行う（図19）。
VER1-1:  κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）、ipk=（N,a＿0,a＿1,a＿2）、opk=（u＿0,u＿1,u＿2）、q、rpk=（L,b,w）、M、Signature=（  Cipher,A＿｛COM｝,B＿｛COM｝,c,  τ＿x,τ＿s,τ’＿e,τ＿t,τ＿｛Cipher｝,τ＿｛mpk｝,τ＿｛rev｝）を検証装置記憶部510から読み込む。（ステップ520101）
VER1-2:  τ＿e  =2^｛κ＿e｝+τ’＿eとする（ステップ520102）。
VER1-3:  c,  opk,  Cipher,τ＿x,τ＿｛Cipher｝を入力して[暗号文用コミット再生手段]を行い、その出力COM＿｛Cipher｝を得る（ステップ520103）。
VER1-4:  c,  ipk,  A＿｛COM｝,τ＿x,  τ＿s,τ＿eを入力して[メンバー公開鍵用コミット再生手段]を行い、その出力COM＿｛mpk｝を得る（ステップ520104）。
VER1-5:  c,  rpk,  B＿｛COM｝,τ＿t,τ’＿e  を入力して[失効データ用コミット再生手段]を行い、その出力COM＿｛rev｝を得る（ステップ520105）。
VER1-6:  Hash（κ,  ipk,  opk,  q,  rpk,  Cipher,  A＿｛COM｝,  B＿｛COM｝,  COM＿｛Cipher｝,  COM＿｛mpk｝,  COM＿｛rev｝,  M）を計算し、c=  Hash（κ,  ipk,  opk,  q,  rpk,  Cipher,  A＿｛COM｝,  B＿｛COM｝,  COM＿｛Cipher｝,  COM＿｛mpk｝,  COM＿｛rev｝,M）が成立しなければrejectを出力して終了する（ステップ520106）。
VER1-7:  τ’＿xがκ＿q+κ＿c+κ＿Sビット未満であることとτ’＿eがκ’＿e+κ＿c+κ＿Sビット未満であることを確認し、もし共に満たされていればacceptを出力して終了し、そうでなければrejectを出力して停止する（ステップ520107）。【００５０】
[暗号文用コミット再生手段]
検証装置500は以下のRECCOMCIPHER1-1,…,RECCOMCIPHER1-3を行う（図20）。
RECCOMCIPHER1-1:  c,  opk=（u＿0,u＿1,u＿2）,  Cipher=（Cipher＿0,Cipher＿1,Cipher＿2）,τ＿x,τ＿｛Cipher｝を入力して受け取る（ステップ970101）。
RECCOMCIPHER1-2:  COM＿｛Cipher＿0｝=u＿0^｛τ＿｛Cipher｝｝Cipher＿0^｛-c｝、COM＿｛Cipher＿1｝=u＿1^｛τ＿｛Cipher｝｝Cipher＿1^｛-c｝、COM＿｛Cipher＿2｝=g^｛τ＿x｝u＿2^｛τ＿｛Cipher｝｝Cipher＿2^｛-c｝を計算する（ステップ970102）。
RECCOMCIPHER1-3:  COM＿｛Cipher｝=（COM＿｛Cipher＿0｝,COM＿｛Cipher＿1｝,COM＿｛Cipher＿2｝）とする（ステップ970103）。【００５１】
[メンバー公開鍵用コミット再生手段]
検証装置500は以下のRECCOMMPK1-1,RECCOMMPK1-2を行う（図21）。
RECCOMMPK1-1:  ipk=（N,a＿0,a＿1,a＿2）,  A＿｛COM｝,τ＿x,  τ＿s,τ＿eを入力として受け取る（ステップ980101）。
RECCOMMPK1-2:  COM＿｛mpk｝=  a＿1^｛τ＿x｝a＿2^｛τ＿s｝A＿｛COM｝^｛-τ＿e｝  mod  N  を計算する（ステップ980102）。【００５２】
[失効データ用コミット再生手段]
検証装置500は以下のRECCOMREV1-1,RECCOMREV1-2を行う（図22）。
RECCOMREV1-1:  c,  rpk=（L,b,w）,  B＿｛COM｝,τ＿t,τ’＿e  を入力として受け取る（ステップ990101）。
RECCOMREV1-2:  COM＿｛rev｝  =  w^｛τ＿t｝B＿｛COM｝^｛-τ’＿e｝  mod  Lを計算する（ステップ990102）。【００５３】
[開示手段230]
開示装置200は以下のOPN1-1,…,OPN1-4を行う（図23）。
OPN1-1:  κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）、ipk=（N,a＿0,a＿1,a＿2）、opk=（u＿0,u＿1,u＿2）、osk=（z＿1,z＿2）、q、rpk=（L,b,w）、M、Signature=（  Cipher,A＿｛COM｝,B＿｛COM｝,c,  τ＿x,τ＿s,τ’＿e,τ＿t,τ＿｛Cipher｝,τ＿｛mpk｝,τ＿｛rev｝）を開示装置記憶部210から読み込む（ステップ230101）。
OPN1-2:  VER1-1,…,VER1-6を行う。Signatureがrejectされたら、開示手段230を終了する（ステップ230102）。
OPN1-3:  opk、osk、Cipherを入力して[復号化手段]を行い、出力hを得る（ステップ230103）。
OPN1-4:  hを出力する（ステップ230104）。【００５４】
[暗号鍵生成手段]
開示装置200は以下のEKEYGEN1-1,…,EKEYGEN1-4を行う（図24）。
EKEYGEN1-1:  Uの元u＿0をランダムに選ぶ（ステップ1000101）。
EKEYGEN1-2:  z＿1,z＿2をランダムに選ぶ（ステップ1000102）。
EKEYGEN1-3:  u＿1=u＿0^｛z＿1｝、u＿2=u＿0^｛z＿2｝を計算する（ステップ1000103）。
EKEYGEN1-4:  （u＿0,u＿1,u＿2）を公開鍵opkにセットし、（z＿1,z＿2）を秘密鍵oskにセットする（ステップ1000104）。【００５５】
[暗号化手段]
ユーザ装置400は以下のENC1-1,…,ENC1-3を行う（図25）。
ENC1-1:  乱数ρ＿｛Cipher｝とUの元hを入力として受け取る（ステップ1010101）。
ENC1-2:  Cipher＿0  =  u＿0^｛ρ＿｛Cipher｝｝、Cipher＿1  =  u＿1^｛ρ＿｛Cipher｝｝、Cipher＿2  =  hu＿2^｛ρ＿｛Cipher｝｝を計算する（ステップ1010102）。
ENC1-3:  Cipher  =  （Cipher＿0,Cipher＿1,Cipher＿2）とする（ステップ1010103）。【００５６】
[復号化手段]
開示装置200は以下のDEC1-1,…,DEC1-2を行う（図26）。
DEC1-1:  公開鍵opk=（u＿0,u＿1,u＿2）、秘密鍵osk=（z＿1,z＿2）、暗号文Cipher  =  （Cipher＿0,Cipher＿1,Cipher＿2）を入力として受け取る（ステップ1020101）。
DEC1-2:  h=Cipher＿2/Cipher＿0^｛z＿1｝を計算する（ステップ1020102）。【００５７】
本実施形態では、ビット数が長いデータであるeの代わりに別のデータe’を用いて登録手段、失効手段および鍵更新手段を行っているので、これらの手段を実行する際の計算量が従来よりも少なくなる。ただし、安全性上の理由から、e’を素数とし、eとe’がなんらかの関係を持つデータでなければならない。そのため、本実施形態では、e’としてe=2^｛κ＿e｝+e’を満たす素数とした。【００５８】
（実施形態２）
本実施形態では、発行参加手順と署名手段とが実施形態１と異なる方法である。以下に、本実施形態を説明する。[装置構成]、[装置の実装]、[記号]、[データの送受信]、および[メンバー公開鍵リスト]は実施形態１と同様であるため、その詳細な説明を省略する。【００５９】
[発行装置鍵生成手段120]
発行装置100は以下のISSGEN2-1,…,ISSGEN2-5を順に行う（図27）。
ISSGEN2-1:  発行装置記憶部110からκ＿Nを読み込む。（ステップ120201）
ISSGEN2-2:  素数p＿1,  p＿2で積N=p＿1p＿2がκ＿Nビットのものを選ぶ（ステップ120202）。
ISSGEN2-3:  QR（N）の元a＿0,a＿1をランダムに選ぶ（ステップ120203）。
ISSGEN2-4:  （p＿1,p＿2）を発行装置100秘密鍵iskにセットし、iskを発行装置記憶部110に書き込む（ステップ120204）。
ISSGEN2-5:  （N,a＿0,a＿1,a＿2）を発行装置100公開鍵ipkにセットし、ipkを発行装置記憶部110に書き込み、そしてipkを出力する（ステップ120205）。
安全性の観点から言えば、ISS2-1で（p＿1-1）/2,  （p＿2-1）/2も素数であることが望ましい。また、ISS2-1でp＿1のビット数とp＿2のビット数はほぼ同じであることが望ましい。【００６０】
続いて、[開示装置鍵生成手段220]と[失効管理装置鍵生成手段320]を実行するが、これらの手段は実施形態１と同様であるため、ここでは、詳細な説明を省略する。【００６１】
[発行参加手段]
発行参加手段では発行装置100とユーザ装置400とがそれぞれ発行手段130と参加手段420を行う。発行手段130は発行第一手段と発行第二手段からなる。参加手段420は参加第一手段、参加第二手段、参加第三手段からなる。
発行参加手段では以下のISSJOIN2-1,…,ISSJOIN2-9が順に行われる（図28）。
ISSJOIN2-1:  ユーザ装置400は参加第一手段を行い、参加第一手段の出力を発行装置100に送信する（ステップ920201）。
ISSJOIN2-2:  発行装置100は受信したデータを発行装置記憶部110に書き込む（ステップ920202）。
ISSJOIN2-3:  発行装置100は発行第一手段130を行い、発行第一手段130の出力をユーザ装置400に送信する（ステップ920203）。
ISSJOIN2-4:  ユーザ装置400は受信したデータをユーザ装置記憶部410に書き込む（ステップ920204）。
ISSJOIN2-5:  ユーザ装置400は参加第二手段を行い、参加第二手段の出力を発行装置100に送信する（ステップ920205）。
ISSJOIN2-6:  発行装置100は受信したデータを発行装置記憶部110に書き込む（ステップ920206）。
ISSJOIN2-7:  発行装置100は発行第二手段130を行い、発行第二手段130の出力をユーザ装置400に送信する（ステップ920207）。
ISSJOIN2-8:  ユーザ装置400は受信したデータをユーザ装置記憶部410に書き込む（ステップ920208）。
ISSJOIN2-9:  ユーザ装置400は参加第三手段を行う（ステップ920209）。【００６２】
[参加第一手段]
ユーザ装置400は以下のJOIN2-1-1,…,JOIN2-1-4を順に行う（図29）。
JOIN2-1-1:  κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）とipk=（N,a＿0,a＿1,a＿2）をユーザ装置記憶部410から読み込む（ステップ4202101）。
JOIN2-1-2:  0以上q未満の整数x’をランダムに選ぶ（ステップ4202102）。
JOIN2-1-3:  A’’’=a＿1^｛x’｝  mod  Nを計算し、x’とA’’’  をユーザ装置記憶部410に書き込む（ステップ4202103）。
JOIN2-1-4:  A’’’を出力する（ステップ4202104）。【００６３】
[発行第一手段]
発行装置100は以下のISSUE2-1-1を行う（図30）。
ISSUE2-1-1:  qビットの自然数x’’をランダムに選び、x’’を出力する（ステップ1302101）。【００６４】
[参加第二手段]
ユーザ装置400は以下のJOIN2-2-1,…,JOIN2-2-4を順に行う（図31）。
JOIN2-2-1:  x’、x’’、qをユーザ装置記憶部410から読み込む（ステップ4202201）。
JOIN2-2-2:  x’  +  x’’をqで割った商をXとし、余りをxとする（ステップ4202202）。
JOIN2-2-3:  A’=  a^xとh=g^xを計算し、（A’,h）の正当性証明文pf＿｛A’,h｝を作成する（ステップ4202203）。
JOIN2-2-4:  x、A’、pf＿｛A’｝  をユーザ装置記憶部410に書き込む（ステップ4202204）。
なお、pf＿｛A’｝の計算方法の詳細は[文献1]に開示されているため、ここでは、その説明を省略する。【００６５】
[発行第二手段]
発行装置100は以下のISSUE2-2-1,…,  ISSUE2-2-6を順に行う（図32）。
ISSUE2-2-1:  κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）、ipk=（N,a＿0,a＿1,a＿2）、isk=（p＿1,p＿2）を発行装置記憶部110から読み込む（ステップ1302201）。
ISSUE2-2-2:  pf＿｛A’,h｝の正当性を検証し、もし正当でなければ発行参加手段130を終了する（ステップ1302202）。
ISSUE2-2-3:  κ'＿eビットの素数e’で、e=2^｛κ＿e｝+e’も素数であるものをランダムに選ぶ（ステップ1302203）。
ISSUE2-2-4:  A  =（a＿0A’）^｛1/e｝  mod  Nを計算する（ステップ1302204）。
ISSUE2-2-5:  （A,e’）を発行装置記憶部110に書き込む（ステップ1302205）。
ISSUE2-2-6:  （A,e’）を出力する（ステップ1302206）。
なお、pf＿｛A’｝の検証方法の詳細は[文献1]に開示されているため、ここでは、その説明を省略する。【００６６】
[参加第三手段]
ユーザ装置400は以下のJOIN2-3-1,…,JOIN2-3-5を順に行う（図33）。
JOIN2-3-1:  ユーザ装置記憶部410からa＿0,a＿1,a＿2,x,A’’,  N,  e’をユーザ装置記憶部410から読み込む（ステップ4202301）。
JOIN2-3-2:  e=2^｛κ＿e｝+e’を計算する（ステップ4202302）。
JOIN2-3-3:  a＿0a＿1^x=A^e  mod  Nが成立するかどうかを確認し、もし成立していなければ発行参加手段130を終了する（ステップ4202303）。
JOIN2-3-4:  xをメンバー秘密鍵mskにセットし、mskをユーザ装置記憶部410に書き込む（ステップ4202304）。
JOIN2-3-5:  （A,e,e’,h）をメンバー公開鍵mpkにセットし、mpkをユーザ装置記憶部410に書き込む（ステップ4202305）。【００６７】
続いて、[登録手段330]、[失効手段340]、[鍵更新手段430]、および[鍵更新内部関数手段]を実行するが、これらの手段は実施形態１と同様であるため、ここでは、その詳細な説明を省略する。【００６８】
[署名手段440]
ユーザ装置400は以下のSIGN1-1,…,  SIGN1-14を行う（図34、図35）。
SIGN1-1:  κ=（κ＿N、κ＿L、κ＿q、κ＿e、κ'＿e、κ＿c、κ＿S）、ipk=（N,a＿0,a＿1,a＿2）、opk、q、rpk=（L,b,w）、mpk=（A,e,e’,h）、msk=x、Bをユーザ装置記憶部410から読み込む（ステップ440201）。
SIGN1-2:  メッセージMを読み込む（ステップ440202）。
SIGN1-3:  Z＿qの元ρ＿｛Cipher｝をランダムに選び、[暗号化手段]を行って  Cipherを計算する（ステップ440203）。
SIGN1-4:  κ＿N/2ビットの自然数sをランダムに選び、A＿｛COM｝=Aa＿2^｛s｝  mod  Nを計算する（ステップ440204）。
SIGN1-5:  κ＿L/2ビットの自然数ρ＿｛rev｝をランダムに選び、B＿｛COM｝=Bw^｛ρ＿｛rev｝｝  mod  Lを計算する（ステップ440205）。
SIGN1-6:  t=e’ρ＿｛rev｝を計算する（ステップ440206）。
SIGN1-7:  κ＿Q+κ＿c+κ＿Sビットの自然数μ＿x、（κ＿N/2）  +κ＿c+κ＿Sビットの自然数μ＿s、κ’＿e+κ＿c+κ＿Sビットの自然数μ’＿e、（κ＿L/2）  +κ＿c+κ＿Sビットの自然数μ＿t、Z＿qの元μ＿｛Cipher｝、（κ＿N/2）  +κ＿c+κ＿Sビットの自然数μ＿｛mpk｝、（κ＿L/2）  +κ＿c+κ＿Sビットの自然数μ＿｛rev｝ランダムに選ぶ（ステップ440207）。
SIGN1-8:  Cipher、μ＿x、μ＿｛Cipher｝、opk、gを入力して[暗号文用コミット手段]を行ってその出力COM＿｛Cipher｝を得る（ステップ440208）。
SIGN1-9:μ＿x、μ＿s、μ’＿e、A＿｛COM｝、ipkを入力して[メンバー公開鍵用コミット手段]を行ってその出力COM＿｛mpk｝を得る（ステップ440209）。
SIGN1-10:  μ’＿e、μ＿t、B＿｛COM｝、rpkを入力して[失効データ用コミット手段]を行ってその出力COM＿｛rev｝を得る（ステップ440210）。
SIGN1-11:  c=Hash（κ,ipk,opk,q,rpk,  Cipher,A＿｛COM｝,B＿｛COM｝,COM＿｛Cipher｝,COM＿｛mpk｝,COM＿｛rev｝,M）を計算する（ステップ440211）。
SIGN1-12:  τ＿x=cx+μ＿x、τ＿s=cs+μ＿s、τ’＿e=ce’+μ’＿e、τ＿t=ct+μ＿tを計算する（ステップ440212）。
SIGN1-13:  τ＿｛Cipher｝=cμ＿｛Cipher｝+ρ＿｛Cipher｝  mod  qを計算する（ステップ440213）。
SIGN1-14:  （Cipher,A＿｛COM｝,B＿｛COM｝,c,τ＿x,τ＿s,τ’＿e,τ＿t,τ＿｛Cipher｝,τ＿｛mpk｝,τ＿｛rev｝）をSignatureにセットし、Signatureを出力する（ステップ440214）。【００６９】
その後、[暗号文用コミット手段]、[メンバー公開鍵用コミット手段]、[失効データ用コミット手段]、[検証手段520]、[暗号文用コミット再生手段]、[メンバー公開鍵用コミット再生手段]、[失効データ用コミット再生手段]、[開示手段230]、[暗号鍵生成手段]、[暗号化手段]、および[復号化手段]を実行するが、これらの手段は、実施形態１と同様であるため、ここでは、その詳細な説明を省略する。【００７０】
本実施形態でも、実施形態１と同様に、ビット数が長いデータであるeの代わりに別のデータe’を用いて登録手段、失効手段および鍵更新手段を行っているので、これらの手段を実行する際の計算量が従来よりも少なくなる効果が得られる。【００７１】
また、本発明は上記実施例に限定されることなく、発明の範囲内で種々の変形が可能であり、それらも本発明の範囲内に含まれることはいうまでもない。
【図１】
2007105749.tif 000003
【図２】
2007105749.tif 000004
【図３】
2007105749.tif 000005
【図４】
2007105749.tif 000006
【図５】
2007105749.tif 000007
【図６】
2007105749.tif 000008
【図７】
2007105749.tif 000009
【図８】
2007105749.tif 000010
【図９】
2007105749.tif 000011
【図１０】
2007105749.tif 000012
【図１１】
2007105749.tif 000013
【図１２】
2007105749.tif 000014
【図１３】
2007105749.tif 000015
【図１４】
2007105749.tif 000016
【図１５】
2007105749.tif 000017
【図１６】
2007105749.tif 000018
【図１７】
2007105749.tif 000019
【図１８】
2007105749.tif 000020
【図１９】
2007105749.tif 000021
【図２０】
2007105749.tif 000022
【図２１】
2007105749.tif 000023
【図２２】
2007105749.tif 000024
【図２３】
2007105749.tif 000025
【図２４】
2007105749.tif 000026
【図２５】
2007105749.tif 000027
【図２６】
2007105749.tif 000028
【図２７】
2007105749.tif 000029
【図２８】
2007105749.tif 000030
【図２９】
2007105749.tif 000031
【図３０】
2007105749.tif 000032
【図３１】
2007105749.tif 000033
【図３２】
2007105749.tif 000034
【図３３】
2007105749.tif 000035
【図３４】
2007105749.tif 000036
【図３５】
2007105749.tif 000037
【国際調査報告】
2007105749.tif 000038
2007105749.tif 000039