(57)【要約】  本発明の鍵発行方法は、発行者装置とネットワークを介して接続されるユーザ装置による鍵発行方法であって、発行者装置から発行者公開鍵をユーザ記憶部に読み込み、発行者装置において発行者公開鍵を群の元の情報を含む元データ用いて秘匿化処理された秘匿文を１または複数含む第１の秘匿データを発行者装置から受信し、発行者公開鍵および第１の秘匿データを用いて第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または元データを定数倍したものの和を秘匿文とする第２の秘匿データを生成して発行者装置に送信し、発行者装置において生成され、第２の秘匿データに対応する元データに基づいた情報を発行者装置から受信し、第２の秘匿データの元データに基づいた情報を用いて、自装置に対応するメンバー公開鍵およびメンバー秘密鍵を生成してユーザ記憶部に書き込むものである。【特許請求の範囲】
【請求項１】
ユーザ装置、および該ユーザ装置とネットワークを介して接続される発行者装置を有するグループ署名システムにおける該ユーザ装置による鍵発行方法であって、  前記ネットワークを介して前記発行者装置から発行者公開鍵をユーザ記憶部に読み込み、  前記発行者装置において前記発行者公開鍵を群の元の情報を含む元データ用いて秘匿化処理された秘匿文を１または複数含む第１の秘匿データを前記発行者装置から前記ネットワークを介して受信し、  前記発行者公開鍵および前記第１の秘匿データを用いて該第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または該元データを定数倍したものの和を秘匿文とする第２の秘匿データを生成する第２の秘匿データ生成処理を行い、  前記第２の秘匿データを前記発行者装置に前記ネットワークを介して送信し、  前記発行者装置において生成され、前記第２の秘匿データに対応する元データに基づいた情報を前記発行者装置から前記ネットワークを介して受信し、  前記第２の秘匿データの元データに基づいた情報を用いて、自装置に対応する公開鍵であるメンバー公開鍵、および自装置に対応する秘密鍵であるメンバー秘密鍵を生成して前記ユーザ記憶部に書き込む、鍵発行方法。
【請求項２】
請求項１記載の鍵発行方法において、  前記第２の秘匿データ生成処理の前記べき乗剰余における冪または定数倍における定数のうち一部は秘密のデータであり、  前記秘密のデータから前記メンバー秘密鍵を生成する秘密鍵計算処理を行い、  前記第２の秘匿データの元データに基づいた情報から前記メンバー公開鍵を生成する公開鍵計算処理を行う、鍵発行方法。
【請求項３】
請求項２記載の鍵発行方法において、  前記ユーザ装置が前記発行者装置から受信する、前記第２の秘匿データの元データに基づいた情報には２つのデータを含み、  前記公開鍵計算処理では、前記２つのデータから所定の計算により求まる第１の算出データと所定の複数のデータの積である第２の算出データとが一致するか否かを判定し、判定の結果、これらの算出データが一致すると前記メンバー公開鍵を生成し、  前記所定の複数のデータは前記発行者公開鍵の一部を底とした所定のデータのべき乗剰余であり、該所定のデータは前記秘密のデータを含むものである、鍵発行方法。
【請求項４】
請求項３記載の鍵発行方法において、  前記第１の算出データは、前記第２の秘匿データの元データに基づいた情報に含まれる２つのデータのうち一方のデータyを底とし、該２つのデータのうち他方のデータに一致するデータEを冪とするべき乗剰余であり、  前記ユーザ装置が前記発行者装置から受信する第１の秘匿データは、前記公開鍵計算処理で用いられた前記発行者公開鍵の一部を1/E乗した後、秘匿化処理されたものである、鍵発行方法。
【請求項５】
請求項４記載の鍵発行方法において、  前記ユーザ装置が前記発行者装置から受信する前記第１の秘匿データは少なくとも２つの秘匿文g’およびh’を含み、  前記第２の秘匿データ生成処理では、まず秘密のデータxおよびr’を選択し、次に、前記秘匿文C＿｛g’｝に対応する元データに対して前記秘密のデータxでべき乗し、前記C＿｛h’｝に対応する元データに対して前記秘密のデータr’でべき乗した秘匿文Cを算出し、  前記ユーザ装置が前記発行者装置に送信する前記第２の秘匿データは、前記秘匿文Cを含み、  前記ユーザ装置が前記発行者装置から受信する、前記第２の秘匿データの元データに基づいた情報に含まれる２つのデータのうち他方のデータは巡回群の元r’’であり、  前記秘密鍵計算処理では、前記データr’とr’’との和からrを算出し、組(x,  r)を含むものをメンバー秘密鍵とし、  前記公開鍵計算処理において、前記第２の算出データに含まれる所定の複数のデータは、前記発行者公開鍵に含まれる第１のデータを前記xでべき乗したデータと、該発行者公開鍵に含まれ、該第１のデータと異なる第２のデータを前記rでべき乗したデータとを含むものである、鍵発行方法。
【請求項６】
請求項２記載の鍵発行方法において、  前記ユーザ装置が前記発行者装置から受信する、前記第２の秘匿データの元データに基づいた情報は２つのデータを含み、  前記公開鍵計算処理では、前記２つのデータから所定の計算により求まる第１の算出データと所定の複数のペアリングの積である第２の算出データとが一致するか否かを判定し、判定の結果、これらの算出データが一致すると前記メンバー公開鍵を生成し、  前記所定の複数のペアリングには、所定の複数のデータの和を前記発行者公開鍵の一部とペアリングしたものを含み、  前記所定の複数のデータには前記発行者公開鍵の一部を底として所定のデータで定数倍したものを含み、該所定のデータは前記秘密のデータを含むものである、鍵発行方法。
【請求項７】
請求項６記載の鍵発行方法において、  前記第１の算出データは所定の２つのデータのペアリングであり、  前記第２の算出データに含まれる前記複数のペアリングのうち所定のペアリングに入力されるデータである第１のペアリングデータは前記第２の秘匿データの元データに基づいた情報に含まれる２つのデータのうち一方のデータA＿Uであり、  前記所定のペアリングに入力されるデータで、前記第１のペアリングデータと異なる第２のペアリングデータは、前記発行者公開鍵の一部に巡回群の元wを乗じたものと該発行者公開鍵のうち該一部のデータと異なるデータから計算されるデータとの和であり、  前記wは前記第２の秘匿データの元データに基づいた情報に含まれる２つのデータのうち他方に一致し、  前記ユーザ装置が前記発行者装置から受信する前記第１の秘匿データが所定の元データを秘匿化したものであり、  前記所定の元データが前記発行者公開鍵の一部に所定の数値を乗算したものであり、  前記所定の数値は前記wと前記発行者装置の秘密のデータとの和の逆数である、鍵発行方法。
【請求項８】
請求項７記載の鍵発行方法において、  前記ユーザ装置が前記発行者装置から受信する前記第１の秘匿データは少なくとも２つの秘匿文H’およびK’を含み、  前記第２の秘匿データ生成処理では、まず秘密のデータx＿Uおよびz’＿Uを選択し、次に、前記H’に対応する元データには前記x＿Uを乗じ、前記K’に対応する元データに前記z’＿Uを乗じた秘匿文Cipherを計算し、  前記ユーザ装置が前記発行者装置に送信する前記第２の秘匿データは前記秘匿文Cipherを含み、  前記ユーザ装置が前記発行者装置から受信する、前記第２の秘匿データの元データに基づいた情報に含まれる２つのデータのうち他方のデータは巡回群の元z’’＿Uであり、  前記秘密鍵計算処理では、前記z’＿Uと前記z’’＿Uとの和からz＿Uを算出し、組(x＿U,  z＿U)を含むものをメンバー秘密鍵とし、  前記公開鍵計算処理では、前記A＿Uおよび前記z＿Uを含むデータを公開鍵とし、  前記第２の算出データに含まれる前記複数のペアリングには前記x＿Uをデータとして含むペアリングと前記z＿Uをデータとして含むペアリングとを有する、鍵発行方法。
【請求項９】
前記第１の秘匿データに含まれる前記秘匿文は、前記発行者装置において、前記群の元の情報が入力されると、乱数ρが選択され、該元をρ乗して生成され、  前記第２の秘匿データに対応する元データは、前記発行者装置において、該第２の秘匿データに含まれる秘匿文を前記乱数ρの逆元で乗じて生成される、請求項１から８のいずれか１項記載の鍵発行方法。
【請求項１０】
ユーザ装置、および該ユーザ装置とネットワークを介して接続される発行者装置を有するグループ署名システムにおける該発行者装置による、追加メンバーへの鍵発行方法であって、  発行者公開鍵および発行者秘密鍵を発行者記憶部から読み出し、  前記発行者公開鍵の一部から計算されるデータを群の元の情報を含む元データを用いて秘匿化処理することにより１または複数の秘匿文を生成する秘匿文生成処理を行い、  前記１または複数の秘匿文を含む第１の秘匿データを前記ネットワークを介して前記ユーザ装置に送信し、  前記ユーザ装置において前記第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または該元データを定数倍したものの和を秘匿文とする第２の秘匿データを前記ユーザ装置から前記ネットワークを介して受信し、  前記第２の秘匿データを元に戻したデータであるg’’を計算し、該g’’から送信用データを生成する送信用データ生成処理を行い、  前記送信用データを前記ネットワークを介して前記ユーザ装置に送信する、鍵発行方法。
【請求項１１】
請求項１０記載の鍵発行方法において、  前記秘匿文生成処理では、所定の式を満たす素数のデータEを発行者記憶部から選択すると、前記発行者公開鍵の一部を1/E乗したものを秘匿化処理し、  前記送信用データは前記Eを含む、鍵発行方法。
【請求項１２】
請求項１１記載の鍵発行方法において、  前記送信用データ生成処理では、巡回群の元r’’をランダムに選択すると、前記発行者公開鍵の一部をr’’でべき乗したものに前記g’’を掛け合せたものを含むデータを前記送信用データとする、鍵発行方法。
【請求項１３】
請求項１０記載の鍵発行方法において、  前記秘匿文生成処理では、巡回群の元yをランダムに選択すると、該yと前記発行者秘密鍵wとの和w+yを計算し、前記発行者公開鍵に含まれる複数のデータのうち第１のデータに1/(w+y)を乗じたものを秘匿化処理し、  前記送信用データは前記yを含む、鍵発行方法。
【請求項１４】
請求項１３記載の鍵発行方法において、  前記送信用データ生成処理では、巡回群の元z’’＿Uをランダムに選択すると、前記発行者公開鍵に含まれる複数のデータのうち前記第１のデータと異なる第２のデータにz’’＿Uを乗じたものと前記g""との和を含む計算式から求まるデータを前記送信用データとする、鍵発行方法。
【請求項１５】
前記秘匿文生成処理では、前記群の元の情報が入力されると、乱数ρを選択し、該元をρ乗して前記秘匿文を生成し、  前記送信用データ生成処理では、前記第２の秘匿データに含まれる秘匿文を前記乱数ρの逆元で乗じて前記ｇ’’を生成する、請求項１０から１４のいずれか１項記載の鍵発行方法。
【請求項１６】
ユーザ装置、および該ユーザ装置とネットワークを介して接続される発行者装置を有するグループ署名システムにおける該ユーザ装置による鍵発行方法であって、  前記ネットワークを介して前記発行者装置から発行者公開鍵をユーザ記憶部に読み込み、  素数のデータX＿1およびX＿2の積xを計算し、  前記xを含むデータを前記ネットワークを介して発行者装置に送信し、  前記発行者装置において前記xが所定の条件を満たしていると、該発行者装置において生成され、所定の式を満たす素数のデータEから計算されるデータyと該データEを含むデータを該発行者装置から受信し、  前記データyおよび前記データEを含むデータを受信すると、データyをE乗したデータである第１の算出データと、前記発行者公開鍵の一部を前記x乗したものに前記発行者公開鍵のうち該一部と異なるデータを掛け合わせた第２の算出データとが一致するか否かを調べ、前記発行者公開鍵の一部であるRSAモジュラスを法として等しいか否かを判定し、判定の結果、等しければ前記データyおよびデータEを含むメンバー公開鍵を生成し、前記データｘを含むメンバー秘密鍵を生成する、鍵発行方法。
【請求項１７】
ユーザ装置、および該ユーザ装置とネットワークを介して接続される発行者装置を有するグループ署名システムにおける該発行者装置による鍵発行方法であって、  発行者公開鍵および発行者秘密鍵を発行者記憶部から読み出し、  素数のデータX＿1およびX＿2の積のデータxを前記ネットワークを介して前記ユーザ装置から受信し、  前記xが所定の条件を満たしているか否かを判定し、判定の結果、条件を満たしていると、所定の式を満たす素数のデータEを選択し、前記発行者公開鍵の一部であるデータgを前記x乗した第１の算出データを算出し、該第１の算出データに前記発行者公開鍵の一部であるデータaを掛けた第２の算出データを算出し、該第２の算出データに1/E乗したものに対して前記発行者公開化鍵の一部であるRSAモジュラスnを法として剰余した第３の算出データを求め、  前記第３の算出データを含むデータを前記ネットワークを介して前記ユーザ装置に送信する、鍵発行方法。
【請求項１８】
発行者公開鍵が格納された発行者記憶部、および該発行者公開鍵をネットワークを介して送出し、該発行者公開鍵を群の元の情報を含む元データを用いて秘匿化処理された１または複数の秘匿文を生成して該１または複数の秘匿文を含む第１の秘匿データをネットワークを介して外部に送出し、該第１の秘匿データが秘匿化処理された第２の秘匿データを受信すると、該第２の秘匿データの元データを生成し、該元データに基づいた情報を前記ネットワークを介して外部に送出する発行者装置制御部を有する発行者装置と、  前記ネットワークを介して前記発行者公開鍵を格納するためのユーザ記憶部、および前記発行者装置から受信する前記発行者公開鍵を該ユーザ記憶部に格納し、前記第１の秘匿データを受信すると、該発行者公開鍵および該第１の秘匿データを用いて該第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または該元データを定数倍したものの和を秘匿文とする前記第２の秘匿データを生成して前記ネットワークを介して前記発行者装置に送信し、前記元データに基づいた情報を受信すると、自装置に対応する公開鍵であるメンバー公開鍵、および自装置に対応する秘密鍵であるメンバー秘密鍵を生成して該ユーザ記憶部に書き込むユーザ装置制御部を有するユーザ装置と、を含むグループ署名システム。
【請求項１９】
前記発行者装置は、前記群の元の情報が入力されると、乱数ρを選択し、該元をρ乗して前記秘匿文を生成し、  前記第２の秘匿データを受信すると、該第２の秘匿データに含まれる秘匿文を前記乱数ρの逆元で乗じて該第２の秘匿データの元データを生成する、請求項１８記載のグループ署名システム。
【請求項２０】
発行者公開鍵が格納された発行者装置とネットワークを介して接続される情報処理装置であって、  前記発行者公開鍵を格納するための記憶部と、  前記発行者装置から前記発行者公開鍵を受信すると前記記憶部に格納し、該発行者装置において該発行者公開鍵を群の元の情報を含む元データを用いて秘匿化処理された秘匿文を１または複数含む第１の秘匿データを該発行者装置から受信すると、該発行者公開鍵および該第１の秘匿データを用いて該第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または該元データを定数倍したものの和を秘匿文とする第２の秘匿データを生成して該発行者装置に送信し、該発行者装置において生成され、該第２の秘匿データの元データに基づいた情報を該発行者装置から受信すると、該第２の秘匿データの元データに基づいた情報を用いて、自装置に対応する公開鍵であるメンバー公開鍵、および自装置に対応する秘密鍵であるメンバー秘密鍵を生成して前記記憶部に書き込む制御部と、を有する情報処理装置。
【請求項２１】
前記第１の秘匿データに含まれる前記秘匿文は、前記発行者装置において、前記群の元の情報が入力されると、乱数ρが選択され、該元をρ乗して生成され、  前記第２の秘匿データの元データは、前記発行者装置において、該第２の秘匿データに含まれる秘匿文を前記乱数ρの逆元で乗じて生成される請求項２０記載の情報処理装置。
【請求項２２】
グループに新規に追加されるユーザ側のユーザ装置とネットワークを介して接続される情報処理装置であって、  発行者公開鍵が格納された記憶部と、  前記発行者公開鍵の一部から計算されるデータを群の元の情報を含む元データを用いて秘匿化することにより１または複数の秘匿文に生成すると、該１または複数の秘匿文を含む第１の秘匿データを前記ユーザ装置に送信し、該ユーザ装置において該第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または該元データを定数倍したものの和を秘匿文とする第２の秘匿データを該ユーザ装置から受信すると、該第２の秘匿データを元に戻したデータであるg’’を計算し、該g’’から送信用データを生成して該ユーザ装置に送信する制御部と、を有する情報処理装置。
【請求項２３】
前記制御部は、前記群の元の情報が入力されると、乱数ρを選択し、該元をρ乗して前記秘匿文を生成し、  前記第２の秘匿データを受信すると、該第２の秘匿データに含まれる秘匿文を前記乱数ρの逆元で乗じて該第２の秘匿データの元データを生成する、請求項２２記載の情報処理装置。
【請求項２４】
発行者公開鍵が格納された発行者装置とネットワークを介して接続されるコンピュータに実行させるためのプログラムであって、  前記ネットワークを介して前記発行者装置から発行者公開鍵をコンピュータの記憶部に読み込み、  前記発行者装置において前記発行者公開鍵を群の元の情報を含む元データを用いて秘匿化処理された秘匿文を１または複数含む第１の秘匿データを前記発行者装置から前記ネットワークを介して受信し、  前記発行者公開鍵および前記第１の秘匿データを用いて該第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または該元データを定数倍したものの和を秘匿文とする第２の秘匿データを生成し、  前記第２の秘匿データを前記発行者装置に前記ネットワークを介して送信し、  前記発行者装置において生成され、前記第２の秘匿データの元データに基づいた情報を前記発行者装置から前記ネットワークを介して受信し、  前記第２の秘匿データの元データに基づいた情報を用いて、自装置に対応する公開鍵であるメンバー公開鍵、および自装置に対応する秘密鍵であるメンバー秘密鍵を生成して前記コンピュータの記憶部に書き込む処理を、前記コンピュータに実行させるためのプログラム。
【請求項２５】
前記第１の秘匿データに含まれる前記秘匿文は、前記発行者装置において、前記群の元の情報が入力されると、乱数ρが選択され、該元をρ乗して生成され、  前記第２の秘匿データの元データは、前記発行者装置において、該第２の秘匿データに含まれる秘匿文を前記乱数ρの逆元で乗じて生成される請求項２４記載のプログラム。
【請求項２６】
グループに新規に追加されるユーザ側のユーザ装置とネットワークを介して接続されるコンピュータに実行させるためのプログラムであって、  発行者公開鍵および発行者秘密鍵をコンピュータの記憶部から読み出し、  前記発行者公開鍵の一部から計算されるデータを群の元の情報を含む元データを用いて秘匿化することにより１または複数の秘匿文に生成する秘匿文生成処理を行い、  前記１または複数の秘匿文を含む第１の秘匿データを前記ネットワークを介して前記ユーザ装置に送信し、  前記ユーザ装置において前記第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または該元データを定数倍したものの和を秘匿文とする第２の秘匿データを前記ユーザ装置から前記ネットワークを介して受信し、  前記第２の秘匿データを元に戻したデータであるg’’を計算し、該g’’から送信用データを生成する送信用データ生成処理を行い、  前記送信用データを前記ネットワークを介して前記ユーザ装置に送信する処理を、前記コンピュータに実行させるためのプログラム。
【請求項２７】
前記秘匿文生成処理では、前記群の元の情報が入力されると、乱数ρを選択し、該元をρ乗して前記秘匿文を生成し、  前記送信用データ生成処理では、前記第２の秘匿データに含まれる秘匿文を前記乱数ρの逆元で乗じて前記ｇ’’を生成する、請求項２６記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、グループに所属するメンバーによる署名を可能にし、また、その署名を確認可能にするためのグループ署名システムと、情報処理装置と、グループ署名システムに新たにメンバーを追加する際の鍵発行方法と、その方法をコンピュータに実行させるためのプログラムに関する。
【背景技術】
【０００２】  従来のグループ署名システムについて、「Jan  Camenisch.  Jens  Groth.  Group  Signatures:  Better  Efficiency  and  New  Theoretical  Aspects.  SCN  2004,  vol.  3352  of  LNCS,  pp.  120-133,  2004.」（以下では、非特許文献１と称する）および「Furukawa,  Imai.  An  Efficient  Group  Signature  Scheme  from  Bilinear  Maps.    ACISP  2005,  vol.  3574  of  LNCS,  pp.455-467.」（以下では、非特許文献２と称する）などに開示されている。これらの文献の従来のグループ署名システムにおいて、グループのメンバーを追加するためのジョイン・プロトコルは、次のような構造上の特徴を持っている。【０００３】  従来のグループ署名システムのジョイン・プロトコルでは、ユーザ装置がまず秘密鍵を使ってデータを計算する。続いて、ユーザ装置はそのデータを発行者装置(非特許文献１ではgroup  managerと称され、非特許文献２ではmembership  managerと称されている)に送信する。その後、ユーザ装置が発行者装置にそのデータの正当性を証明する。そして、発行者装置が発行者装置の秘密鍵を使ってそのデータを加工する。
【発明の開示】
【０００４】  従来のグループ署名システムでは、上述したように、ユーザ装置が先にデータの正当性を証明し、その後に発行者装置が発行者装置の秘密鍵を使ってデータを加工している。ユーザ装置と発行者装置との情報のやり取りは、１人のメンバーの鍵発行処理が終了するまで、一対一で行われていた。そのため、発行者装置が複数のユーザ装置に対してジョイン・プロトコルをコンカレントに行った場合には、情報の秘匿性などの安全性が保証できないという問題がある。
【０００５】  本発明は上述したような従来の技術が有する問題点を解決するためになされたものであり、グループのメンバー追加のためのジョイン・プロトコルをコンカレントに行うことを可能にした鍵発行方法、グループ署名システム、情報処理装置、および、コンピュータに実行させるためのプログラムを提供することを目的とする。
【０００６】  上記目的を達成するための本発明の鍵発行方法は、ユーザ装置、およびユーザ装置とネットワークを介して接続される発行者装置を有するグループ署名システムにおけるユーザ装置による鍵発行方法であって、ネットワークを介して発行者装置から発行者公開鍵をユーザ記憶部に読み込み、発行者装置において発行者公開鍵を群の元の情報を含む元データ用いて秘匿化処理された秘匿文を１または複数含む第１の秘匿データを発行者装置からネットワークを介して受信し、発行者公開鍵および第１の秘匿データを用いて第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または元データを定数倍したものの和を秘匿文とする第２の秘匿データを生成する第２の秘匿データ生成処理を行い、第２の秘匿データを発行者装置にネットワークを介して送信し、発行者装置において生成され、第２の秘匿データに対応する元データに基づいた情報を発行者装置からネットワークを介して受信し、第２の秘匿データの元データに基づいた情報を用いて、自装置に対応する公開鍵であるメンバー公開鍵、および自装置に対応する秘密鍵であるメンバー秘密鍵を生成してユーザ記憶部に書き込むものである。
【０００７】  また、本発明の鍵発行方法は、ユーザ装置、およびユーザ装置とネットワークを介して接続される発行者装置を有するグループ署名システムにおける発行者装置による、追加メンバーへの鍵発行方法であって、発行者公開鍵および発行者秘密鍵を発行者記憶部から読み出し、発行者公開鍵の一部から計算されるデータを群の元の情報を含む元データを用いて秘匿化処理することにより１または複数の秘匿文を生成する秘匿文生成処理を行い、１または複数の秘匿文を含む第１の秘匿データをネットワークを介してユーザ装置に送信し、ユーザ装置において第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または元データを定数倍したものの和を秘匿文とする第２の秘匿データをユーザ装置からネットワークを介して受信し、第２の秘匿データを元に戻したデータであるg’’を計算し、g’’から送信用データを生成する送信用データ生成処理を行い、送信用データをネットワークを介してユーザ装置に送信するものである。
【０００８】  一方、上記目的を達成するための本発明のグループ署名システムは、発行者公開鍵が格納された発行者記憶部、および発行者公開鍵をネットワークを介して送出し、発行者公開鍵を群の元の情報を含む元データを用いて秘匿化処理された１または複数の秘匿文を生成して１または複数の秘匿文を含む第１の秘匿データをネットワークを介して外部に送出し、第１の秘匿データが秘匿化処理された第２の秘匿データを受信すると、第２の秘匿データの元データを生成し、元データに基づいた情報をネットワークを介して外部に送出する発行者装置制御部を有する発行者装置と、ネットワークを介して発行者公開鍵を格納するためのユーザ記憶部、および発行者装置から受信する発行者公開鍵をユーザ記憶部に格納し、第１の秘匿データを受信すると、発行者公開鍵および第１の秘匿データを用いて第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または元データを定数倍したものの和を秘匿文とする第２の秘匿データを生成してネットワークを介して発行者装置に送信し、元データに基づいた情報を受信すると、自装置に対応する公開鍵であるメンバー公開鍵、および自装置に対応する秘密鍵であるメンバー秘密鍵を生成してユーザ記憶部に書き込むユーザ装置制御部を有するユーザ装置と、を含む構成である。
【０００９】  本発明では、発行者装置が発行者装置の秘密鍵を使って先にデータを作成し、次にユーザ装置がそのデータを加工して別のデータを作り、そしてユーザ装置がその加工されたデータの正当性を発行者装置に証明している。ユーザ装置がデータの正当性を証明する前に発行者装置が発行者装置の秘密鍵を使ってデータを加工するので、発行者装置は、１人のメンバーの鍵発行処理が終了する前に、途中で他のユーザ装置から受信するデータの加工をすることが可能となる。
【００１０】  また、上記目的を達成するための本発明の情報処理装置は、発行者公開鍵が格納された発行者装置とネットワークを介して接続される情報処理装置であって、発行者公開鍵を格納するための記憶部と、発行者装置から発行者公開鍵を受信すると記憶部に格納し、発行者装置において発行者公開鍵を群の元の情報を含む元データを用いて秘匿化処理された秘匿文を１または複数含む第１の秘匿データを発行者装置から受信すると、発行者公開鍵および第１の秘匿データを用いて第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または元データを定数倍したものの和を秘匿文とする第２の秘匿データを生成して発行者装置に送信し、発行者装置において生成され、第２の秘匿データの元データに基づいた情報を発行者装置から受信すると、第２の秘匿データの元データに基づいた情報を用いて、自装置に対応する公開鍵であるメンバー公開鍵、および自装置に対応する秘密鍵であるメンバー秘密鍵を生成して記憶部に書き込む制御部と、を有する構成である。
【００１１】  また、本発明の情報処理装置は、グループに新規に追加されるユーザ側のユーザ装置とネットワークを介して接続される情報処理装置であって、発行者公開鍵が格納された記憶部と、発行者公開鍵の一部から計算されるデータを群の元の情報を含む元データを用いて秘匿化することにより１または複数の秘匿文に生成すると、１または複数の秘匿文を含む第１の秘匿データをユーザ装置に送信し、ユーザ装置において第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または元データを定数倍したものの和を秘匿文とする第２の秘匿データをユーザ装置から受信すると、第２の秘匿データを元に戻したデータであるg’’を計算し、g’’から送信用データを生成してユーザ装置に送信する制御部と、を有する構成である。
【００１２】  また、上記目的を達成するための本発明のプログラムは、発行者公開鍵が格納された発行者装置とネットワークを介して接続されるコンピュータに実行させるためのプログラムであって、ネットワークを介して発行者装置から発行者公開鍵をコンピュータの記憶部に読み込み、発行者装置において発行者公開鍵を群の元の情報を含む元データを用いて秘匿化処理された秘匿文を１または複数含む第１の秘匿データを発行者装置からネットワークを介して受信し、発行者公開鍵および第１の秘匿データを用いて第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または元データを定数倍したものの和を秘匿文とする第２の秘匿データを生成し、第２の秘匿データを発行者装置にネットワークを介して送信し、発行者装置において生成され、第２の秘匿データの元データに基づいた情報を発行者装置からネットワークを介して受信し、第２の秘匿データの元データに基づいた情報を用いて、自装置に対応する公開鍵であるメンバー公開鍵、および自装置に対応する秘密鍵であるメンバー秘密鍵を生成してコンピュータの記憶部に書き込む処理を、コンピュータに実行させるものである。
【００１３】  さらに、本発明のプログラムは、グループに新規に追加されるユーザ側のユーザ装置とネットワークを介して接続されるコンピュータに実行させるためのプログラムであって、発行者公開鍵および発行者秘密鍵をコンピュータの記憶部から読み出し、発行者公開鍵の一部から計算されるデータを群の元の情報を含む元データを用いて秘匿化することにより１または複数の秘匿文に生成する秘匿文生成処理を行い、１または複数の秘匿文を含む第１の秘匿データをネットワークを介してユーザ装置に送信し、ユーザ装置において第１の秘匿データに含まれる秘匿文に対応する元データをべき乗剰余したものの積を秘匿文とする、または元データを定数倍したものの和を秘匿文とする第２の秘匿データをユーザ装置からネットワークを介して受信し、第２の秘匿データを元に戻したデータであるg’’を計算し、g’’から送信用データを生成する送信用データ生成処理を行い、送信用データをネットワークを介してユーザ装置に送信する処理を、コンピュータに実行させるものである。
【００１４】  上述したように、本発明では、ユーザ装置がデータの正当性を証明する前に発行者装置が発行者装置の秘密鍵を使ってデータを加工するので、複数のユーザ装置と発行者装置との間でジョイン・プロトコルによるデータの送受信をコンカレントに行っても、情報秘匿の安全性が従来よりも向上する。
【図面の簡単な説明】
【００１５】
【図１】図１はグループ署名システムの一構成例を示すブロック図である。
【図２】図２は実施形態１における発行者鍵生成手順を示すフローチャートである。
【図３】図３は実施形態１における開示者鍵生成手順を示すフローチャートである。
【図４】図４は実施形態１における発行手順１を示すフローチャートである。
【図５】図５は実施形態１における参加手順１を示すフローチャートである。
【図６】図６は実施形態１における発行手順２を示すフローチャートである。
【図７】図７は実施形態１における参加手順２を示すフローチャートである。
【図８】図８はpf＿αの生成手順を示すフローチャートである。
【図９】図９はpf＿αの検証手順を示すフローチャートである。
【図１０】図１０はElGamal暗号化手順を示すフローチャートである。
【図１１】図１１はElGamal暗号文線形積再暗号化手順を示すフローチャートである。
【図１２】図１２はElGamal暗号文復号手順を示すフローチャートである。
【図１３】図１３は(Y,C)の正当性証明手順を示すフローチャートである。
【図１４】図１４は(Y,C)の正当性証明検証手順を示すフローチャートである。
【図１５】図１５は実施形態２における発行者鍵生成手順を示すフローチャートである。
【図１６】図１６は実施形態２における開示者鍵生成手順を示すフローチャートである。
【図１７】図１７は実施形態２における発行手順１を示すフローチャートである。
【図１８】図１８は実施形態２における参加手順１を示すフローチャートである。
【図１９】図１９は実施形態２における発行手順２を示すフローチャートである。
【図２０】図２０は実施形態２における参加手順２を示すフローチャートである。
【図２１】図２１はLinear暗号方式鍵生成手順を示すフローチャートである。
【図２２】図２２はLinear暗号化手順を示すフローチャートである。
【図２３】図２３はLinear暗号文線形和再暗号化手順を示すフローチャートである。
【図２４】図２４はLinear暗号文復号手順を示すフローチャートである。
【図２５】図２５は(Ider＿U,  Cipher)の正当性証明手順を示すフローチャートである。
【図２６】図２６は(Ider＿U,  Cipher)の正当性証明検証手順を示すフローチャートである。
【図２７】図２７は実施形態３における発行者鍵生成手順を示すフローチャートである。
【図２８】図２８は実施形態３における開示者鍵生成手順を示すフローチャートである。
【図２９】図２９は実施形態３における参加手順１を示すフローチャートである。
【図３０】図３０は実施形態３における発行手順１を示すフローチャートである。
【図３１】図３１は実施形態３における参加手順２を示すフローチャートである。
【図３２】図３２は実施形態４における発行手順１を示すフローチャートである。
【図３３】図３３は実施形態４における参加手順１を示すフローチャートである。
【図３４】図３４は実施形態４における発行手順２を示すフローチャートである。
【図３５】図３５は(Y,C)の正当性証明手順を示すフローチャートである。
【図３６】図３６は(Y,C)の正当性証明検証手順を示すフローチャートである。
【図３７】図３７は実施形態５における発行者鍵生成手順を示すフローチャートである。
【図３８】図３８は実施形態５における発行手順１を示すフローチャートである。
【図３９】図３９は実施形態５における参加手順１を示すフローチャートである。
【図４０】図４０は実施形態５における発行手順２を示すフローチャートである。
【図４１】図４１は(Ider＿U,  Cipher)の正当性証明手順を示すフローチャートである。
【図４２】図４２は(Ider＿U,  Cipher)の正当性証明検証手順を示すフローチャートである。
【符号の説明】
【００１６】  １００    発行者装置  １１０    発行者装置制御部  １２０    発行者記憶部  ２００    ユーザ装置  ２１０    ユーザ装置制御部  ２２０    ユーザ記憶部
【発明を実施するための最良の形態】
【００１７】（実施形態１）[装置構成]  本実施形態のグループ署名システムの構成を説明する。図１はグループ署名システムの一構成例を示すブロック図である。図１に示すように、グループ署名システムには、グループのメンバーに鍵を発行する発行者装置１００と、メンバーが操作するためのユーザ装置２００とを有する。また、グループ署名システムに、検証者装置３００および開示者装置４００が接続されている。発行者装置１００、ユーザ装置２００、検証者装置３００および開示者装置４００は記憶部および制御部等を有する情報処理装置である。【００１８】  発行者装置１００には、発行者装置制御部１１０、発行者記憶部１２０および通信部（不図示）が設けられている。発行者装置制御部１１０は発行者鍵生成手段１１２と発行手段１１４とを有する。ユーザ装置２００には、ユーザ装置制御部２１０、ユーザ記憶部２２０および通信部（不図示）が設けられている。ユーザ装置制御部２１０は参加手段２１２と署名生成手段２１４とを有する。【００１９】  検証者装置３００には、検証者装置制御部３１０、検証者記憶部３２０および通信部（不図示）が設けられている。検証者装置制御部３１０は検証手段３１４を有する。開示者装置４００には、開示者装置制御部４１０、開示者記憶部４２０および通信部（不図示）が設けられている。開示者装置制御部４１０は開示者鍵生成手段４１２と開示手段４１４とを有する。【００２０】  各装置の制御部は通信部および記憶部の制御の他に、データの演算処理を実行する。制御部には、プログラムにしたがって所定の処理を実行するＣＰＵ（Central  Processing  Unit）、およびプログラムを格納するためのメモリが設けられている。【００２１】  発行者装置１００、ユーザ装置２００、検証者装置３００および開示者装置４００は、インターネットおよびＬＡＮ（Local  Area  Network）等の通信ネットワークを介して相互に通信可能に接続されている。通信ネットワークは、有線および無線のどちらでもよく、また、これらの組み合わせであってもよい。なお、図１では、装置間における情報の流れをわかり易くするために、各装置の通信部を図に示すことを省略している。【００２２】  発行者記憶部１２０、ユーザ記憶部２２０、検証者記憶部３２０および開示者記憶部４２０としては、ハードディスクや半導体メモリ等がある。【００２３】  各装置の記憶部には、セキュリティ・パラメータl＿n、l＿E、l＿Q、l＿c、l＿e、l＿sが事前に入力されているものとする。どのような方法でl＿n、l＿E、l＿Q、l＿c、l＿e、l＿sが入力されるのかは問わない。Γを位数Qの巡回群で、Qのビット数がl＿Qビットであるものとする。Γとして、例えば、(Z/PZ)の乗法群や、楕円曲線群を用いることが可能である。ここでは、Γが(Z/PZ)の乗法群である場合を例にとって説明する。また、Zもしくは(Z/QZ)を巡回群と称する。【００２４】  また、各装置の記憶部には、Γを記述するパラメータと、Qとが事前に入力されているものとする。どのような方法でΓを記述するパラメータと、Qとが入力されるのかは問わない。【００２５】  なお、発行者装置１００は、入力部、出力部、記憶部および制御部からなる一般的なコンピュータにより構成されるものであり、発行者鍵生成手段１１２および��行手段１１４はＣＰＵがプログラムを実行することで、コンピュータ内に仮想的に構成される。このことは、ユーザ装置２００、検証者装置３００、および開示者装置４００についても同様である。【００２６】また、発行者装置１００、ユーザ装置２００および開示者装置４００においては、各制御部のＣＰＵがプログラムを実行することで、秘匿すべき情報として乗法群Γの元、巡回群(Z/QZ)の元、および(Z/nZ)の元がランダムに選択される。(Z/nZ)のnについては、次の[発行者鍵生成手順ISS-GEN]のところで説明する。複数の元の中からランダムに選択する方法として、例えば、乱数を利用するものがある。【００２７】  次に、本実施形態のグループ署名システムによる鍵発行方法について説明する。なお、本実施形態では、発行者装置が秘匿すべき情報に対して暗号化を行って秘匿性を保つ。以下では、暗号化などの秘匿化処理により秘匿化された情報を秘匿文と称する。また、元の情報を含むデータを元データと称するが、暗号化処理においては元の情報を含むデータが平文に相当する。【００２８】  [発行者鍵生成手順ISS-GEN]  発行者鍵生成手段１１２による発行者鍵生成手順ISS-GENを説明する。図２は発行者鍵生成手順を示すフローチャートである。図２に示すように、発行者装置１００は以下のISS-GEN1,…,ISS-GEN5を順に行う。ISS-GEN1:  セキュリティ・パラメータl＿nを発行者記憶部１２０から読み込む（ステップ１００１）。ISS-GEN2:  素数p,  qで、その積n  =  p  qがl＿nビットであるものを選ぶ（ステップ１００２）。ISS-GEN3:  QR(n)の元a,  g、およびn以下の非負整数αをランダムに選び、h  =  g^α  mod  nを計算する（ステップ１００３）。ISS-GEN4:  (α,  g,  h)を入力して後述する[pf＿αの生成手順]を行い、αの知識の証明文pf＿αを作成する（ステップ１００４）。ISS-GEN5:  発行者公開鍵ipkを(n,  a,  g,  h,  pf＿α)に、発行者秘密鍵iskを(p,  q,  α)にセットし、ipk、iskを発行者記憶部１２０に書き込み（ステップ１００５）、発行者鍵生成手順ISS-GENを終了する。【００２９】  発行者公開鍵ipkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にipkを載せるという方法が考えられるが、どのような方法でipkを公開してもよい。ユーザ装置２００のユーザ装置制御部２１０は、公開された発行者公開鍵ipkをユーザ記憶部２２０に格納する。【００３０】  [開示者鍵生成手順OPN-GEN]  開示者鍵生成手段４１２による開示者鍵生成手順OPN-GENを説明する。図３は開示者鍵生成手順を示すフローチャートである。図３に示すように、開示者装置４００は以下のOPN-GEN1、OPN-GEN2、OPN-GEN3を順に行う。OPN-GEN1:  Qを開示者記憶部４２０から読み込む（ステップ１０１１）。OPN-GEN2:  (Z/QZ)の元X＿G、X＿H、Γの元Fをランダムに選び、G  =  F^｛X＿G｝、H  =  F^｛X＿H｝とする（ステップ１０１２）。OPN-GEN3:  開示者公開鍵opkを(F,  G,  H)に、開示者秘密鍵oskを(X＿G,  X＿H)にセットし、opk、oskを開示者記憶部４２０に書き込み（ステップ１０１３）、開示者鍵生成手順OPN-GENを終了する。【００３１】  開示者公開鍵opkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にopkを載せるという方法が考えられるが、どのような方法でopkを公開してもよい。ユーザ装置２００のユーザ装置制御部２１０は、公開された開示者公開鍵opkをユーザ記憶���２２０に格納する。また、発行者装置１００の発行者装置制御部１１０は、公開された開示者公開鍵opkを発行者記憶部１２０に格納する。【００３２】  [発行手順ISS-ISSUEと参加手順USR-JOIN]  発行者装置１００とユーザ装置２００は相互通信を行いながら、それぞれ発行手順ISS-ISSUEと参加手順USR-JOINとを行う。まず、発行者装置１００が後述の[発行手順1  ISS-ISSUE-1]を行い、続いて、ユーザ装置２００が後述の[参加手順1  USR-JOIN-1]を行う。さらに、発行者装置１００が後述の[発行手順2  ISS-ISSUE-2]を行い、最後にユーザ装置２００が後述の[参加手順2  USR-JOIN-2]を行う。上述の手順の途中で、メンバー公開鍵upkとメンバー秘密鍵uskが生成される。メンバー公開鍵upkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にupkを載せるという方法が考えられるが、どのような方法でupkを公開してもよい。【００３３】  [署名手順  USR-SIGN]  署名生成手段２１４は、メッセージmを入力として受け取ったら、vk  =  ipk、sk  =  (vk,  usk)として非特許文献1のSign(m,  vk,  sk)を行い、mに対する署名文σを得る。[検証手順  VER-VERIFY]  検証手段３１４は、メッセージmとmに対する署名文σとを受け取ったら、vk  =  ipkとして非特許文献1のVerify(vk,  m,  σ)を行う。[開示手順  OPN-OPEN]  開示手段４１４は、メッセージmとmに対する署名文σとを受け取ったら、gusk  =  (ipk,  opk)として非特許文献1のOpen(gusk,  m,  σ)を行う。【００３４】  [発行手順1  ISS-ISSUE-1]  発行手段１１４による発行手順1  ISS-ISSUE-1を説明する。図４は発行手順１を示すフローチャートである。図４に示すように、発行者装置１００は以下のISS-ISSUE-1-1、…、ISS-ISSUE-1-4を順に行う。ISS-ISSUE-1-1:  ipk  =  (n,  a,  g,  h,  pf＿α)、opk  =  (F,  G,  H)、isk  =  (p,  q,  α)を発行者記憶部１２０から読み込む（ステップ１０２１）。ISS-ISSUE-1-2:  l＿eビットの非負整数eで、E  =  2^｛l＿E｝+eが素数となるものをランダムに選び、g’  =  g^｛1/E｝  mod  n、h’  =  h^｛1/E｝  mod  nを計算する（ステップ１０２２）。ISS-ISSUE-1-3:  ((n,  g,  h),  g’)を入力して後述する[ElGamal暗号化手順]を行い、C＿｛g’｝を作る。同様に((n,  g,  h),  h’)を入力して[ElGamal暗号化手順]を行い、C＿｛h’｝を作る（ステップ１０２３）。ISS-ISSUE-1-4:  (C＿｛g’｝,  C＿｛h’｝)をユーザ装置２００に送信する（ステップ１０２４）。【００３５】  [参加手順1  USR-JOIN-1]  参加手段２１２による参加手順1  USR-JOIN-1を説明する。図５は参加手順１の手順を示すフローチャートである。図５に示すように、ユーザ装置２００は以下のUSR-JOIN-1-1,…,  USR-JOIN-1-7を順に行う。USR-JOIN-1-1:  (C＿｛g’｝,  C＿｛h’｝)を受信する（ステップ１０３１）。USR-JOIN-1-2:  ipk  =  (n,  a,  g,  h,  pf＿α)、opk  =  (F,  G,  H)をユーザ記憶部２２０から読み込む（ステップ１０３２）。USR-JOIN-1-3:  (ipk,  pf＿α)を入力して後述する[pf＿αの検証手順]を行う。[pf＿αの検証手順]がrejectを出力したら参加手順を終了する（ステップ１０３３）。USR-JOIN-1-4:  (Z/QZ)の元x、(Z/nZ)の元r’をランダムに選び、Y  =  G^｛x｝を計算する（ステップ１０３４）。USR-JOIN-1-5:  (ipk,  x,  r’,  C＿｛g’｝,  C＿｛h’｝)を入力して後述する[ElGamal暗号文線形積再暗号化手順]を行い、(C,  r’’’)を作る（ステップ１０３５）。USR-JOIN-1-6:  (n,  g,  h,  x,  r’,  C＿｛g’｝,  C＿｛h’｝,  Y,  C)を入力して後述する[(Y,  C)の正当性証明手順]を��い、pf＿｛Y,  C｝を作る（ステップ１０３６）。USR-JOIN-1-7:  (Y,  C,  pf＿｛Y,  C｝)を発行者装置１００に送信する（ステップ１０３７）。【００３６】  [発行手順2  ISS-ISSUE-2]  発行手段１１４による発行手順2  ISS-ISSUE-2を説明する。図６は発行手順２を示すフローチャートである。図６に示すように、発行者装置１００は以下のISS-ISSUE-2-1、…、ISS-ISSUE-2-5を順に行う。ISS-ISSUE-2-1:  (Y,  C,  pf＿｛Y,  C｝)を受信する（ステップ１０４１）。ISS-ISSUE-2-2:  (n,  g,  h,  C＿｛g’｝,  C＿｛h’｝,  Y,  C,  pf＿｛Y,  C｝)を入力して後述する[(Y,  C)の正当性証明検証手順]を行う。もし[(Y,  C)の正当性証明検証手順]がrejectを出力したら参加手順を終了する（ステップ１０４２）。ISS-ISSUE-2-3:  (ipk,  isk,  C)を入力して後述する[ElGamal暗号文復号手順]を行って平文g’’を得、(Z/EZ)の元r’’をランダムに選び、y  =  a^｛1/E｝g’’h^｛r’’｝  mod  nを計算する（ステップ１０４３）。ISS-ISSUE-2-4:  YをユーザのIDと組にして開示者装置４００に送る（ステップ１０４４）。ISS-ISSUE-2-5:  (y,  r’’)をユーザ装置２００に送って（ステップ１０４５）、発行手順を終了する。【００３７】  [参加手順2  USR-JOIN-2]  参加手段２１２による参加手順2  USR-JOIN-2を説明する。図７は参加手順２を示すフローチャートである。図７に示すように、ユーザ装置２００は以下のUSR-JOIN-2-1,…,  USR-JOIN-2-4を順に行う。USR-JOIN-2-1:  (y,  r’’)を受信する（ステップ１０５１）。USR-JOIN-2-2:  r  =  r’+r’’を計算する（ステップ１０５２）。USR-JOIN-2-3:  ag^｛x｝h^｛r｝  =  y^Eが成立するかどうかを確認し、成立しなければ参加手順を終了する（ステップ１０５３）。USR-JOIN-2-4:  成立すれば、メンバー公開鍵upkを(Y,  y,  E)に、メンバー秘密鍵uskを(x,  r)にセットし、upk、uskをユーザ記憶部２２０に書き込み（ステップ１０５４）、参加手順を終了する。【００３８】  [pf＿αの生成手順]  発行者装置制御部１１０による、pf＿αの生成手順を説明する。図８はpf＿α生成手順を示すフローチャートである。図８に示すように、発行者装置１００は以下のpf-α-GEN-1,…,  pf-α-GEN-5を順に行う。pf−α−GEN−1:  入力(α,  g,  h)を受け取る（ステップ１０６１）。pf−α−GEN−2:  l＿n+l＿sビットの乱数α＿｛0,1｝を選び、h＿｛0,  1｝  =  g^｛α＿｛0,  1｝｝  mod  nを計算する（ステップ１０６２）。l＿cビットのビット列を出力するハッシュ関数をH＿｛l＿c｝と書く。pf-α-GEN-3:  c  =  H＿｛l＿c｝(g,  h,  h＿｛0,1｝)を計算する（ステップ１０６３）。pf-α-GEN-4:  α＿｛0,  2｝  =  cα+  α＿｛0,  1｝  とする（ステップ１０６４）。pf-α-GEN-5:  pf＿α  =  (h＿｛0,  1｝,  α＿｛0,  2｝)とする（ステップ１０６５）。【００３９】  [pf＿αの検証手順]  ユーザ装置制御部２１０による、pf＿αの検証手順を説明する。図９はpf＿α検証手順を示すフローチャートである。図９に示すように、ユーザ装置２００は以下のpf-α-VER-1,…,  pf-α-GEN-3を順に行う。pf-α-VER-1:  入力(ipk,  pf＿α)を受け取り、ipk  =  (n,  a,  g,  h,  pf＿α)、pf＿α  =  (h＿｛0,  1｝,  α＿｛0,  2｝)とパースする（ステップ１０７１）。pf-α-VER-2:  c  =  H＿｛l＿c｝(g,  h,  h＿｛0,  1｝)を計算する（ステップ１０７２）。pf-α-GEN-3:  g^｛α＿｛0,2｝｝  =  h^ch＿｛0,  1｝  mod  nが成立すればacceptを、そうでなければrejectを出力する（ステップ１０７３）。【００４０】  [ElGamal暗号化手順]  発行者装置制御部１１０によるElGamal暗号化手順を説明する。図１０はElGamal暗号化手順を示すフローチャートである。図１０に示すように、発行者装置１００は以下のELGAMAL-ENC-1,…,  ELGAMAL-ENC-3を順に行う。ELGAMAL-ENC-1:  入力((n,  g,  h),  g’)を受け取る（ステップ１０８１）。ELGAMAL-ENC-2:  l＿Nビットの元r＿1をランダムに選び、g＿1  =  g^｛r＿1｝  mod  n、h＿1  =  g’h^｛r＿1｝  mod  nとする（ステップ１０８２）。ELGAMAL-ENC-3:  C＿｛g’｝  =  (g＿1,  h＿1)とする（ステップ１０８３）。このようにして、準同型性暗号方式の暗号化手段により暗号文を生成する。【００４１】  [ElGamal暗号文線形積再暗号化手順]  発行者装置制御部１１０によるElGamal暗号文線形積再暗号化手順を説明する。図１１はElGamal暗号文線形積再暗号化手順を示すフローチャートである。図１１に示すように、発行者装置１００は以下のELGAMAL-MUL-1,…,3を順に行う。ELGAMAL-MUL-1:  入力(ipk,  x,  r’,  C＿｛g’｝,  C＿｛h’｝)を受け取る（ステップ１０９１）。ELGAMAL-MUL-2:  ipk  =  (n,  a,  g,  h,  pf＿α)、C＿｛g’｝  =  (g＿｛1,  g’｝,  h＿｛1,  g’｝)、C＿｛h’｝  =  (g＿｛1,  h’｝,  h＿｛1,  h’｝)とパースする（ステップ１０９２）。ELGAMAL-MUL-3:  l＿nビットの自然数r’’’を選び、C  =  (g＿｛1,  g’｝^｛x｝h＿｛1,  h’｝^｛r’｝g^｛r’’’｝,  h＿｛1,  g’｝^｛x｝g＿｛1,  h’｝^｛r’｝  h^｛r’’’｝)を計算する（ステップ１０９３）。【００４２】  [ElGamal暗号文復号手順]  発行者装置制御部１１０によるElGamal暗号文復号手順を説明する。図１２はElGamal暗号文復号手順を示すフローチャートである。図１２に示すように、発行者装置１００は以下のELGAMAL-DEC-1,…,  ELGAMAL-DEC-3を順に行う。ELGAMAL-DEC-1:入力(ipk,  isk,  C)を受け取る（ステップ１１０１）。ELGAMAL-DEC-2:  ipk  =  (n,  a,  g,  h,  pf＿α)、isk  =  (p,  q,  α)、C  =  (g＿C,  h＿C)とパースする（ステップ１１０２）。ELGAMAL-DEC-3:  g’’  =  h＿C/g＿C^｛α｝  mod  nを計算する（ステップ１１０３）。【００４３】  [(Y,C)の正当性証明手順]  ユーザ装置制御部２１０による、(Y,C)の正当性証明手順を説明する。図１３は(Y,C)正当性証明手順を示すフローチャートである。図１３に示すように、ユーザ装置２００は以下のPF-YC-GEN-1,…,  PF-YC-GEN-5を順に行う。PF-YC-GEN-1:(n,  g,  h,  x,  r’,  r’’’,  C＿｛g’｝,  C＿｛h’｝,  Y,  C)を受け取り、C＿｛g’｝  =  (g＿｛1,  g’｝,  h＿｛1,  g’｝)、C＿｛h’｝  =  (g＿｛1,  h’｝,  h＿｛1,  h’｝)とパースする（ステップ１１１１）。PF-YC-GEN-2:  l＿q+l＿sビットの自然数x＿｛0,1｝とl＿n+l＿sビットの自然数r’＿｛0,  1｝、r’’’＿｛0,  1｝とをランダムに選び、g＿｛1,  g,  0,  1｝  =  g＿｛1,  g’｝^｛x＿｛0,  1｝｝g＿｛1,  h’｝^｛r’＿｛0,  1｝｝g^｛r’’’＿｛0,  1｝｝  mod  n、h＿｛1,  h,  0,  1｝  =  h＿｛1,  g’｝^｛x＿｛0,  1｝｝g＿｛1,  h’｝^｛r’  ｛0,  1｝｝h^｛r’’’＿｛0,  1｝｝  mod  n、Y＿｛0,  1｝  =  G^｛x＿｛0,  1｝｝とする（ステップ１１１２）。PF-YC-GEN-3:  c  =  H＿｛l＿c｝(n,  g,  h,  C＿｛g’｝,  C＿｛h’｝,  Y,  C,  C＿｛g,  0,  1｝,  C＿｛h,  0,  1｝,  Y＿｛0,  1｝)を計算する（ステップ１１１３）。PF-YC-GEN-4:  x＿｛0,  2｝  =  cx  +  x＿｛0,  1｝、r’＿｛0,  2｝  =  cr’+  r’＿｛0,  1｝、r’’’＿｛0,  2｝  =  c  r’’’+  r’’’＿｛0,  1｝を計算する（ステップ１１１４）。PF-YC-GEN-5:  pf＿｛Y,  C｝=  (g＿｛1,  g,  0,  1｝,  h＿｛1,  h,  0,  1｝,  Y＿｛0,  1｝,  x＿｛0,  2｝,  r’＿｛0,  2｝,  r’’’＿｛0,  2｝)とする（ステップ１１１５）。【００４４】  [(Y,C)の正当性証明検証手順]  発行者装置制御部１１０による、(Y,C)の正当性証明検証手順を説明する。図１４は(Y,C)正当性証明検証手順を示すフローチャートである。図１４に示すように、発行者装置１００は以下のPF-YC-VER-1,…,  PF-YC-VER-3を順に行う。PF-YC-VER-1:  入力(n,  g,  h,  C＿｛g’｝,  C＿｛h’｝,  Y,  C,  pf＿｛Y,  C｝)  を受け取り、C＿｛g’｝  =  (g＿｛1,  g’｝,  h＿｛1,  g’｝)、C＿｛h’｝  =  (g＿｛1,  h’｝,  h＿｛1,  h’｝)、C  =  (g＿｛1,  g｝,  C＿｛1,  h｝)、pf＿｛Y,  C｝  =  (g＿｛1,  g,  0,  1｝,  h＿｛1,  h,  0,  1｝,Y＿｛0,  1｝,  x＿｛0,  2｝,  r’＿｛0,  2｝,  r’’’＿｛0,  2｝)  とパースする（ステップ１１２１）。PF-YC-VER-2:  c  =  H＿｛l＿c｝(n,  g,  h,  C＿｛g’｝,  C＿｛h’｝,  Y,  C,  C＿｛g,  0,  1｝,  C＿｛h,  0,  1｝,  Y＿｛0,  1｝)  を計算する（ステップ１１２２）。PF-YC-VER-3:  g＿｛1,  g｝^cg＿｛1,  g,  0,  1｝  =  g＿｛1,  g’｝^｛x＿｛0,  2｝｝g＿｛1,  h’｝^｛r’＿｛0,  2｝｝g^｛r’’’＿｛0,  2｝｝  mod  n、h＿｛1,  h｝^ch＿｛1,  h,  0,  1｝  =  h＿｛1,  g’｝^｛x＿｛0,  2｝｝g＿｛1,  h’｝^｛r’  ｛0,  2｝｝h^｛r’’’＿｛0,2｝｝  mod  n、Y^cY＿｛0,  1｝  =  G^｛x＿｛0,  2｝｝、-2^｛l＿Q+l＿c+l＿s｝  ≦  x＿｛0,  2｝  ≦  2^｛l＿Q+l＿c+l＿s｝  が成立したらacceptし、そうでなければrejectする（ステップ１１２３）。【００４５】  本実施形態の追加メンバーへの鍵発行方法およびグループ署名システムでは、発行者装置が発行者装置の秘密鍵を使って先に第１の秘匿データを作成し、次にユーザ装置がその第１の秘匿データを加工して別の第２の秘匿データを作り、そしてユーザ装置がその加工されたデータの正当性を発行者装置に証明している。このようにして、従来のグループ署名システムとは異なり、ユーザ装置がデータの正当性を証明する前に発行者装置が発行者装置の秘密鍵を使ってデータを加工するので、複数のユーザ装置と発行装置とのジョイン・プロトコルによるデータの送受信をコンカレントに行った場合にも情報の安全性が向上する。【００４６】  （実施形態２）[装置構成]  本実施形態のグループ署名システムについて説明する。装置構成については、実施形態１で説明した装置と同様であるため、ここではその詳細な説明を省略する。以下では、実施形態１と異なる処理について詳細に説明する。【００４７】  各装置の記憶部にはセキュリティ・パラメータkが事前に入力されているものとする。どのような方法でkが入力されるのかは問わない。Γ＿1,  Γ＿2,  Γ＿Tを位数pの巡回群で、Γ＿1×Γ＿2からΓ＿Tへの双線形写像eが定義されていて、しかもpのビット数がkであるものとする。さらにΓを位数pの巡回群とする。各装置の記憶部にはΓ＿1,  Γ＿2,  Γ＿Tを記述するパラメータと、pとが事前に入力されているものとする。どのような方法でΓ＿1,  Γ＿2,  Γ＿Tを記述するパラメータと、pとが入力されるのかは問わない。【００４８】  次に、本実施形態のグループ署名システムによる鍵発行方法について説明する。本実施形態も、実施形態１と同様に、発行者装置が秘匿すべき情報に対して暗号化を行って秘匿性を保つ場合とする。【００４９】  [発行者鍵生成手順  ISS-GEN]  発行者鍵生成手段１１２による発行者鍵生成手順ISS-GENを説明する。図１５は発行者鍵生成���順を示すフローチャートである。図１５に示すように、発行者装置１００は以下のISS-GEN-1,…,ISS-GEN-3を順に行う。ISS-GEN-1:  Γ＿1の元G＿1,  H,  K,  Γ＿2の元G＿2、および(Z/pZ)の元wをランダムに選び、Y  =  wG＿2とする（ステップ１２０１）。ISS-GEN-2:  G＿1を入力して後述する[Linear暗号方式鍵生成手順]を行い、Linear暗号方式公開鍵lpkとLinear暗号方式秘密鍵lskを作る（ステップ１２０２）。ISS-GEN-3:  発行者公開鍵ipkを(G＿1,  G＿2,  H,  K,  Y,  lpk)にセットし、発行者秘密鍵iskを(w,  lsk)にセットし、ipkとiskを発行者記憶部１２０に記憶する（ステップ１２０３）。【００５０】  発行者公開鍵ipkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にipkを載せるという方法が考えられるが、どのような方法でipkを公開してもよい。ユーザ装置２００のユーザ装置制御部２１０は、公開された発行者公開鍵ipkをユーザ記憶部２２０に格納する。【００５１】  [開示者鍵生成手順  OPN-GEN]  開示者鍵生成手段４１２による開示者鍵生成手順OPN-GENを説明する。図１６は開示者鍵生成手順を示すフローチャートである。図１６に示すように、開示者装置４００は以下のOPN-GEN-1、OPN-GEN-2を順に行う。OPN-GEN-1:  Γの元G、(Z/pZ)の元s,  tをランダムに選び、S  =  sG,  T  =  tGとする（ステップ１２１１）。OPN-GEN-2:  開示者公開鍵opkを(G,  Γの元G、S,  T)にセットし、開示者秘密鍵oskを(s,  t)にセットし、opk、oskを開示者記憶部４２０に書き込む（ステップ１２１２）。【００５２】  開示者公開鍵opkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にopkを載せるという方法が考えられるが、どのような方法でopkを公開してもよい。ユーザ装置２００のユーザ装置制御部２１０は、公開された開示者公開鍵opkをユーザ記憶部２２０に格納する。また、発行者装置１００の発行者装置制御部１１０は、公開された開示者公開鍵opkを発行者記憶部１２０に格納する。【００５３】  [発行手順  ISS-ISSUE  と  参加手順USR-JOIN]  発行者装置１００とユーザ装置２００は相互通信を行いながら、それぞれ発行手順  ISS-ISSUEと参加手順USR-JOINとを行う。まず、発行者装置１００が後述の[発行手順1  ISS-ISSUE-1]を行い、続いて、ユーザ装置２００が後述の[参加手順1  USR-JOIN-1]を行う。さらに、発行者装置１００が後述の[発行手順2  ISS-ISSUE-2]を行い、最後にユーザ装置２００が後述の[参加手順2  USR-JOIN-2]を行う。上述の手順の途中で、メンバー公開鍵upkとメンバー秘密鍵uskが生成される。メンバー公開鍵upkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にupkを載せるという方法が考えられるが、どのような方法でupkを公開してもよい。【００５４】  [署名手順  USR-SIGN]  署名生成手段２１４は、メッセージmを入力として受け取ったら、mpk  =  ipk、tpk  =  opk、cert＿U  =  upk、sk＿U  =  uskとして非特許文献２のSign(m,  upk,  tpk,  cert＿U,  sk＿U)を行い、mに対する署名文gsを得る。[検証手順  VER-VERIFY]  検証手段３１４は、メッセージmとmに対する署名文gsとを受け取ったら、mpk  =  ipk、tpk  =  opkとしとして非特許文献2のVerify(m,  gs,  mpk,  tpk)を行う。[開示手順  OPN-OPEN]  開示手段４１４は、メッセージmとmに対する署名文gsとを受け取ったら、mpk  =  ipk、tpk  =  opk、tsk  =  oskとして非特許文献2のOpen(m,  σ,  mpk,  tpk,  tsk)を行う。【００５５】  [発行手順1  ISS-ISSUE-1]  発行手段１１４による発行手順1  ISS-ISSUE-1を説明する。図１７は発行手順１を示すフローチャートである。図１７に示すように、発行者装置１００は以下のISS-ISSUE-1-1,…,  ISS-ISSUE-1-4を順に行う。ISS-ISSUE-1-1:  ipk  =  (G＿1,  G＿2,  H,  K,  Y,  lpk)、opk  =  (G,  S,  T)、isk  =  (w,  lsk)を発行者記憶部１２０から読み込む（ステップ１２２１）。ISS-ISSUE-1-2:  (Z/pZ)の元y＿Uをランダムに選び、H’  =  (1/(w+y＿U))  H、K’  =  (1/(w+y＿U))  Kを計算する（ステップ１２２２）。ISS-ISSUE-1-3:  (G＿1,  lpk,  H’)を入力して後述する[Linear暗号化手順]を行い、Cipher＿｛H’｝を作る。同様に(G＿1,  lpk,  K’)を入力して[Linear暗号化手順]を行い、Cipher＿｛K’｝を作る（ステップ１２２３）。ISS-ISSUE-1-4:  (Cipher＿｛H’｝,  Cipher＿｛K’｝)をユーザ装置２００に送信する（ステップ１２２４）。【００５６】  [参加手順1  USR-JOIN-1]  参加手段２１２による参加手順1  USR-JOIN-1を説明する。図１８は参加手順１を示すフローチャートである。図１８に示すように、ユーザ装置２００は以下のUSR-JOIN-1-1,…,  USR-JOIN-1-6を順に行う。USR-JOIN-1-1:  (Cipher＿｛H’｝,  Cipher＿｛K’｝)を受信する（ステップ１２３１）。USR-JOIN-1-2:  ipk  =  (G＿1,  G＿2,  H,  K,  Y,  lpk)、opk  =  (G,  S,  T)をユーザ記憶部２２０から読み込む（ステップ１２３２）。USR-JOIN-1-3:  (Z/pZ)の元x＿U、z’＿Uをランダムに選び、Ider＿U  =  x＿U  G、を計算する（ステップ１２３３）。USR-JOIN-1-4:  (G＿1,  x＿U,  z’＿U,  Cipher＿｛H’｝,  Cipher＿｛K’｝)を入力して後述する[Linear暗号文線形積再暗号化手順]を行い、(Cipher,  β,  β’)を作る（ステップ１２３４）。USR-JOIN-1-5:  (G,  lpk,  x＿U,  z’＿U,  β,  β’,  Cipher＿｛H’｝,  Cipher＿｛K’｝,  Ider＿U,  Cipher)を入力して後述する[(Ider＿U,  Cipher)の正当性証明手順]を行い、pf＿｛Ider＿U,  Cipher｝を作る（ステップ１２３５）。USR-JOIN-1-6:  (Ider＿U,  Cipher,  pf＿｛Ider＿U,  Cipher｝)を発行者装置１００に送信する（ステップ１２３６）。【００５７】  [発行手順2  ISS-ISSUE-2]  発行手段１１４による発行手順2  ISS-ISSUE-2を説明する。図１９は発行手順２を示すフローチャートである。図１９に示すように、発行者装置１００は以下のISS-ISSUE-2-1、…、ISS-ISSUE-2-5を順に行う。ISS-ISSUE-2-1:  (Ider＿U,  Cipher,  pf＿｛Ider＿U,  Cipher｝)を受信する（ステップ１２４１）。ISS-ISSUE-2-2:  (G,  lpk,  Cipher＿｛H’｝,  Cipher＿｛K’｝,  Ider＿U,  Cipher,  pf＿｛Ider＿U,  Cipher｝)を入力して後述する[(Ider＿U,  Cipher)の正当性証明検証手順]を行う。もし[(Ider＿U,  Cipher)の正当性証明検証手順]がrejectを出力したら参加手順を終了する（ステップ１２４２）。ISS-ISSUE-2-3:  (G＿1,  lpk,  lsk,  Cipher)を入力して後述する[Linear暗号文復号手順]を行って平文G＿1’’を得、(Z/eZ)の元z’’＿Uをランダムに選び、A＿U  =  (1/(w+y＿U))  G＿1-  G＿1’’-  z’’＿UKを計算する（ステップ１２４３）。なお、平文G＿1’’は実施形態１では平文g’’に相当する。ISS-ISSUE-2-4:  Ider＿UをユーザのIDと組にして開示者装置４００に送る（ステップ１２４４）。ISS-ISSUE-2-5:  (A＿U,  z’’＿U)をユーザ装置２００に送って（ステップ１２４５）、発行手順を終了する。【００５８】  [参加手順2  USR-JOIN-2]  参加手段２１２による参加手順2  USR-JOIN-2を説明する。図２０は参加手順２を示すフローチャートである。図２０に示すように、ユーザ装置２００は以下のUSR-JOIN-2-1,…,  USR-JOIN-2-4を順に行う。USR-JOIN-2-1:  (A＿U,  z’’＿U)を受信する（ステップ１２５１）。USR-JOIN-2-2:  z＿U  =  z’＿U+  z’’＿U  mod  pを計算する（ステップ１２５２）。USR-JOIN-2-3:  e(A＿U,  Y+  y＿UG＿1)e(x＿UH,  G＿2)e(z＿UK,  G＿2)  =  e(G＿1,  G＿2)が成立するかどうかを確認し、成立しなければ参加手順を終了する（ステップ１２５３）。USR-JOIN-2-4:  成立すれば、メンバー公開鍵upkを(A＿U,  y＿U,  z＿U)に、メンバー秘密鍵uskを(x＿U,  z＿U)にセットし、upk、uskをユーザ記憶部２２０に書き込み（ステップ１２５４）、参加手順を終了する。【００５９】  [Linear暗号方式鍵生成手順]  発行者装置制御部１１０によるLinear暗号方式鍵生成手順を説明する。図２１はLinear暗号方式鍵生成手順を示すフローチャートである。図２１に示すように、発行者装置１００は次のLIN-GEN-1,…,  LIN-GEN-3を順に行う。LIN-GEN-1:  入力G＿1を読み込む（ステップ１２６１）。LIN-GEN-2:  (Z/pZ)の元α、α’をランダムに選び、L  =  (1/α)G＿1,  L’  =  (1/α’)G＿1とする（ステップ１２６２）。LIN-GEN-3:  Liniar暗号方式公開鍵lpkを(L,  L’)にセットし、Liniar暗号方式秘密鍵lskを(α,  α’)にセットする（ステップ１２６３）。【００６０】  [Linear暗号化手順]  発行者装置制御部１１０によるLinear暗号化手順を説明する。図２２はLinear暗号化手順を示すフローチャートである。図２２に示すように、発行者装置１００は次のLIN-ENC-1,LIN-ENC-2を順に行う。LIN-ENC-1:  入力(G＿1,  lpk,  H’)を受け取り、lpk  =  (L,  L’)とパースする（ステップ１２７１）。LIN-ENC-2:  (Z/pZ)の元γ,  γ’をランダムに選び、  (G＿｛Cipher,  H’｝,  L＿｛Cipher,  H’｝,  L’＿｛Cipher,  H’｝)  =  (H’+  (γ+  γ’)G,  γL,  γ’L’)とし、Cipher＿｛H’｝  =  (G＿｛Cipher,  H’｝,  L＿｛Cipher,  H’｝,  L’＿｛Cipher,  H’｝)とする（ステップ１２７２）。【００６１】  [Linear暗号文線形和再暗号化手順]  ユーザ装置制御部２１０によるLinear暗号文線形和再暗号化手順を説明する。図２３はLinear暗号文線形和再暗号化手順を示すフローチャートである。図２３に示すように、ユーザ装置２００は次のLIN-SUM-1,LIN-SUM-2を順に行う。LIN-SUM-1:  入力(G＿1,  x＿U,  z’＿U,  Cipher＿｛H’｝,  Cipher＿｛K’｝)を受け取り、lpk  =  (L,  L’)とパースし、Cipher＿｛H’｝  =  (G＿｛Cipher,  H’｝,  L＿｛Cipher,  H’｝,  L’＿｛Cipher,  H’｝)とパースし、Cipher＿｛K’｝  =  (G＿｛Cipher,  K’｝,  L＿｛Cipher,  K’｝,  L’＿｛Cipher,  K’｝)とパースする（ステップ１２８１）。LIN-SUM-2:  (Z/pZ)の元β、β’をランダムに選び、(G＿｛Cipher｝,  L＿｛Cipher｝,  L’＿｛Cipher｝)  =  (x＿UG＿｛Cipher,  H’｝+  z’＿UG＿｛Cipher,  K’｝+  (β+  β’)G＿1,  x＿UL＿｛Cipher,  H’｝+  z’＿UL＿｛Cipher,  K’｝+βL,  x＿UL’＿｛Cipher,  H’｝+  z’＿UL’＿｛Cipher,  K’｝+  β’L’)とし、Cipher  =  (G＿｛Cipher｝,  L＿｛Cipher｝,  L’＿｛Cipher｝)とする（ステップ１２８２）。このようにして、平文を定数倍したものの和から暗号文を生成している。なお、実施形態１では、平文をべき乗剰余したものの積から暗号文を生成している。実施形態１の再暗号化手順を本実施形態に適用してもよく、実施形態１に本実施形態の再暗号化手順を適用してもよい。【００６２】  [Linear暗号文復号手順]  発行者装置制御部１１０によるLinear暗号文復号手順を説明する。図２４はLinear暗号文復号手順を示すフローチャートである。図２４に示すように、発行者装置１００は次���LIN-DEC-1,LIN-DEC-2を順に行う。LIN-DEC-1:  入力(G＿1,  lpk,  lsk,  Cipher)を受け取り、lpk  =  (L,  L’)とパース氏、lsk  =  (α,  α’)とパースし、Cipher  =  (G＿｛Cipher｝,  L＿｛Cipher｝,  L’＿｛Cipher｝)とパースする（ステップ１２９１）。LIN-DEC-2:  G＿1’’  =  G＿｛Cipher｝-αL＿｛Cipher｝-α’L’＿｛Cipher｝とする（ステップ１２９２）。【００６３】  [(Ider＿U,  Cipher)の正当性証明手順  ID-CI-PF-GEN]  ユーザ装置制御部２１０による、(Ider＿U,  Cipher)の正当性証明手順を説明する。図２５は(Ider＿U,  Cipher)正当性証明手順を示すフローチャートである。図２５に示すように、ユーザ装置２００は以下のID-CI-PF-GEN-1,…,  ID-CI-PF-GEN-5を順に行う。ID-CI-PF-GEN-1  :  入力(G,  lpk,  x＿U,  z’＿U,  β,  β’,  Cipher＿｛H’｝,  Cipher＿｛K’｝,  Ider＿U,  Cipher)を受け取り、lpkを(L,  L’)とパースし、Cipher＿｛H’｝を(G＿｛Cipher,  H’｝,  L＿｛Cipher,  H’｝,  L’＿｛Cipher,  H’｝)とパースし、Cipher＿｛K’｝を(G＿｛Cipher,  K’｝,  L＿｛Cipher,  K’｝,  L’＿｛Cipher,  K’｝)とパースする（ステップ１３０１）。ID-CI-PF-GEN-2  :  (Z/pZ)の元x＿｛U,  0,  1｝,  z’＿｛U,  0,  1｝,  β＿｛U,  0,  1｝,  β’＿｛U,  0,  1｝をランダムに選び、(G＿｛Cipher,  0,  1｝,  L＿｛Cipher,  0,  1｝,  L’＿｛Cipher,  0,  1｝)  =  (x＿｛U,  0,  1｝G＿｛Cipher,  H’｝+  z’＿｛U,  0,  1｝G＿｛Cipher,  K’｝+  (β＿｛0,  1｝+β’＿｛0,  1｝)G＿1,  x＿｛U,  0,  1｝L＿｛Cipher,  H’｝+  z’＿｛U,  0,  1｝L＿｛Cipher,  K’｝+  β＿｛0,  1｝L,  x＿｛U,  0,  1｝L’＿｛Cipher,  H’｝+  z’＿｛U,  0,  1｝L’＿｛Cipher,  K’｝+  β’＿｛0,  1｝L’)とし、Ider＿｛U,  0,  1｝  =  x＿｛U,  0,  1｝Gとする（ステップ１３０２）。H＿｛Z/pZ｝を、(Z/pZ)に値をとるハッシュ関数とする。【００６４】  ID-CI-PF-GEN-3:  c  =  H＿｛Z/pZ｝(G,  lpk,  Cipher＿｛H’｝,  Cipher＿｛K’｝,  Ider＿U,  Cipher  G＿｛Cipher,  0,  1｝,  L＿｛Cipher,  0,  1｝,  L’＿｛Cipher,  0,  1｝,  Ider＿｛U,  0,  1｝)とする（ステップ１３０３）。ID-CI-PF-GEN-4:  x＿｛U,  0,  2｝  =  cx＿U  +  x＿｛U,  0,  1｝  mod  p、z’＿｛U,  0,  2｝  =  cz’＿U  +  z’＿｛U,  0,  2｝  mod  p、β＿｛0,  2｝=cβ  +  β＿｛0,  1｝  mod  p、  β’＿｛0,  2｝  =  cβ’  +  β’＿｛0,  1｝  mod  pとする（ステップ１３０４）。ID-CI-PF-GEN-5:  pf＿｛Ider＿U,  Cipher｝  =  (G＿｛Cipher,  0,  1｝,  L＿｛Cipher,  0,  1｝,  L’＿｛Cipher,  0,  1｝,  Ider＿｛U,  0,  1｝,  x＿｛U,  0,  2｝,  z’＿｛U,  0,  2｝,  β＿｛0,  2｝,  β’＿｛0,  2｝)とする（ステップ１３０５）。【００６５】  [(Ider＿U,Cipher)の正当性証明検証手順  ID-CI-PF-VER]  発行者装置制御部１１０による、(Ider＿U,Cipher)の正当性証明検証手順を説明する。図２６は(Ider＿U,Cipher)正当性証明検証手順を示すフローチャートである。図２６に示すように、発行者装置１００は以下のID-CI-PF-VER-1,…,  ID-CI-PF-VER-3を順に行う。ID-CI-PF-VER-1:  入力(G,  lpk,  Cipher＿｛H’｝,  Cipher＿｛K’｝,  Ider＿U,  Cipher,  pf＿｛Ider＿U,  Cipher｝)を受け取り、lpk  =  (L,  L’)とパースし、Cipher  =  (G＿｛Cipher｝,  L＿｛Cipher｝,  L’＿｛Cipher｝)とパースし、Cipher＿｛H’｝  =  (G＿｛Cipher,  H’｝,  L＿｛Cipher,  H’｝,  L’＿｛Cipher,  H’｝)とパースし、Cipher＿｛K’｝  =  (G＿｛Cipher,  K’｝,  L＿｛Cipher,  K’｝,  L’＿｛Cipher,  K’｝)とパースし、pf＿｛Ider＿U,  Cipher  ｝  =  (G＿｛Cipher,  0,  1｝,  L＿｛Cipher,  0,  1｝,  L’＿｛Cipher,  0,  1｝,  Ider＿｛U,  0,  1｝,  x＿｛U,  0,  2｝,  z’＿｛U,  0,  2｝,  β＿｛0,  2｝,  β’＿��0,  2｝)  とパースする（ステップ１３１１）。【００６６】  ID-CI-PF-VER-2:  c  =  H＿｛Z/pZ｝(G,  lpk,  Cipher＿｛H’｝,  Cipher＿｛K’｝,  Ider＿U,  Cipher  G＿｛Cipher,  0,  1｝,  L＿｛Cipher,  0,  1｝,  L’＿｛Cipher,  0,  1｝,  Ider＿｛U,  0,  1｝)  とする（ステップ１３１２）。ID-CI-PF-VER-3:  (cG＿｛Cipher｝+  G＿｛Cipher,  0,  1｝,  cL＿｛Cipher｝+  L＿｛Cipher,  0,  1｝,  cL’＿｛Cipher｝+  L’＿｛Cipher,  0,  1｝)  =  (x＿｛U,  0,  2｝G＿｛Cipher,  H’｝+  z’＿｛U,  0,  2｝G＿｛Cipher,  K’｝+  (β＿｛0,  2｝+β’＿｛0,  2｝)G＿1,  x＿｛U,  0,  2｝L＿｛Cipher,  H’｝+z’＿｛U,  0,  2｝L＿｛Cipher,  K’｝+  β＿｛0,  2｝L,  x＿｛U,  0,  2｝L’＿｛Cipher,  H’｝+z’＿｛U,  0,  2｝L’＿｛Cipher,  K’｝+β’＿｛0,  2｝L’)  であり、しかもc・Ider＿｛U,  0,  1｝+  Ider＿｛U,  0,  2｝  =  x＿｛U,  0,  2｝G  であればacceptを出力し、そうでなければrejectを出力する（ステップ１３１３）。【００６７】  本実施形態の鍵発行方法およびグループ署名システムにおいても、実施形態１と同様の効果が得られる。【００６８】  （実施形態３）[装置構成]  本実施形態のグループ署名システムについて説明する。装置構成については、実施形態１で説明した装置と同様であるため、ここではその詳細な説明を省略する。以下では、実施形態１と異なる処理について詳細に説明する。【００６９】  各装置の記憶部にはセキュリティ・パラメータl＿n、l＿E、l＿Q、l＿c、l＿e、l＿sが事前に入力されているものとする。どのような方法でl＿n、l＿E、l＿Q、l＿c、l＿e、l＿sが入力されるのかは問わない。Γを位数Qの巡回群で、Qのビット数がl＿Qビットであるものとする。として例えば、(Z/PZ)の乗法群や、楕円曲線群を用いる事ができる。ここではΓが(Z/PZ)の乗法群である場合を例にとって説明する。各装置の記憶部にはΓを記述するパラメータと、Qとが事前に入力されているものとする。どのような方法でΓを記述するパラメータと、Qとが入力されるのかは問わない。【００７０】  次に、本実施形態のグループ署名システムによる鍵発行方法について説明する。【００７１】  [発行者鍵生成手順ISS-GEN]  発行鍵生成手段１１２による発行者鍵生成手順ISS-GENを説明する。図２７は発行者鍵生成手順を示すフローチャートである。図２７に示すように、発行者装置１００は以下のISS-GEN1,…,ISS-GEN5を順に行う。ISS-GEN1:  セキュリティ・パラメータl＿nを発行者記憶部１２０から読み込む（ステップ１４０１）。ISS-GEN2:  素数p,qで、その積n=pqがl＿nビットであるものを選ぶ（ステップ１４０２）。ISS-GEN3:  QR(n)の元a,  g、およびn以下の非負整数αをランダムに選び、h  =  g^α  mod  nを計算する（ステップ１４０３）。ISS-GEN4:  (α,  g,  h)を入力し、実施形態１で説明した[pf＿αの生成手順]を行い、αの知識の証明文pf＿αを作成する（ステップ１４０４）。ISS-GEN5:  発行者公開鍵ipkを(n,  a,  g,  h,  pf＿α)に、発行者秘密鍵をiskを(p,  q,  α)にセットし、ipk、iskを発行者記憶部１２０に書き込み、発行者鍵生成手順ISS-GENを終了する（ステップ１４０５）。【００７２】  発行者公開鍵ipkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にipkを載せるという方法が考えられるが、どのような方法でipkを公開してもよい。ユーザ装置２００のユーザ装置制御部２１０は、公開された発行者公開鍵ipkをユーザ記憶部２２０に格納する。【００７３】  [開示者鍵生成手順OPN-GEN]  開示者鍵生成手段４１２による開示者鍵生成手順OPN-GENを説明する。図２８は開示者鍵生成手順を示すフローチャートである。図２８に示すように、開示者装置４００は以下のOPN-GEN1、OPN-GEN2、OPN-GEN3を順に行う。OPN-GEN1:  Qを開示者記憶部４２０から読み込む（ステップ１４１１）。OPN-GEN2:  (Z/qZ)の元X＿G、X＿H、Γの元Fをランダムに選び、G  =  F^｛X＿G｝、H  =  F^｛X＿H｝とする（ステップ１４１２）。OPN-GEN3:  開示者公開鍵opkを(F,  G,  H)に、開示者秘密鍵oskを(X＿G,  X＿H)にセットし、opk、oskを開示者記憶部４２０に書き込み（ステップ１４１３）、開示者鍵生成手順OPN-GENを終了する。【００７４】  開示者公開鍵opkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にopkを載せるという方法が考えられるが、どのような方法でopkを公開してもよい。ユーザ装置２００のユーザ装置制御部２１０は、公開された開示者公開鍵opkをユーザ記憶部２２０に格納する。また、発行者装置１００の発行者装置制御部１１０は、公開された開示者公開鍵opkを発行者記憶部１２０に格納する。【００７５】  [発行手順  ISS-ISSUEと参加手順USR-JOIN]  発行者装置１００とユーザ装置２００は相互通信を行いながら、それぞれ発行手順  ISS-ISSUEと参加手順USR-JOINとを行う。まず、ユーザ装置２００が後述の[参加手順1  USR-JOIN-1]を行い、続いて、発行者装置１００が後述の[発行手順1  ISS-ISSUE-1]を行う。さらに、ユーザ装置２００が後述の[参加手順2  USR-JOIN-2]を行う。上述の手順の途中で、メンバー公開鍵upkとメンバー秘密鍵uskが生成される。メンバー公開鍵upkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にupkを載せるという方法が考えられるが、どのような方法でupkを公開してもよい。【００７６】  [署名手順  USR-SIGN]  署名生成手段２１４は、メッセージmを入力として受け取ったら、upk=(x,  e,  y)とパースし、(Z/NZ)の元βをランダムに選び、(F’,  G’,  H’)=(F^β,  F^xG^β,  F^xH^β)を計算し、(G’,  H’)の正当性証明文pf＿｛(G’,  H’)｝を計算する。[検証手順  VER-VERIFY]  検証手段３１４は、pf＿｛(G’,  H’)｝の正当性を検証する。[開示手順  OPN-OPEN]  開示手段４１４は、G’/F’^｛X＿G｝を計算し、メンバー公開鍵upk  =  (x,  e,  y)がG’/F’^｛X＿G｝  =  G^xを満たすユーザのIDを出力する。【００７７】  [参加手順1  USR-JOIN-1]  参加手段２１２による参加手順1  USR-JOIN-1を説明する。図２９は参加手順１を示すフローチャートである。図２９に示すように、ユーザ装置２００は次のUSR-JOIN-1-1,…,  USR-JOIN-1-3を順に行う。USR-JOIN-1-1:  ipk  =  (n,  a,  g,  h,  pf＿α)、opk  =  (F,  G,  H)をユーザ記憶部２２０から読み込む（ステップ１４２１）。USR-JOIN-1-2:  素数X＿1,  X＿2で、その積x  =  X＿1X＿2がl＿nビットであるものを選ぶ（ステップ１４２２）。USR-JOIN-1-3:  xを発行者装置１００に送信する（ステップ１４２３）。【００７８】  [発行手順1  ISS-ISSUE-1]  発行手段２１２による発行手順1  ISS-ISSUE-1を説明する。図３０は発行手順１を示すフローチャートである。図３０に示すように、発行者装置１００は次のISS-ISSUE-1-1,…,  ISS-ISSUE-1-5を順に行う。ISS-ISSUE-1-1:  ipk  =  (n,  a,  g,  h,  pf＿α)、opk  =  (F,  G,  H)、isk  =  (p,  q,  α)を発行者記憶部１２０から読み込む（ステップ１４３１）。ISS-ISSUE-1-2:  xがl＿nビット未満で���るかどうかを調べ、もしそうでないなら発行手順ISS-ISSUEを終了する（ステップ１４３２）。ISS-ISSUE-1-3:  l＿eビットの非負整数eで、E  =  2^｛l＿E｝  +  eが素数となるものとをランダムに選び、y  =  (ag^x)^｛1/E｝  mod  nを計算する（ステップ１４３３）。つまり、(ag^x)^｛1/E｝に対してRSAモジュラスnを法として剰余した値を求める。ISS-ISSUE-1-4:  xをユーザのIDと組にして開示者装置４００に送る（ステップ１４３４）。ISS-ISSUE-1-5:  (E,  y)をユーザ装置２００に送信する（ステップ１４３５）。【００７９】  [参加手順2  USR-JOIN-2]  参加手段２１２による参加手順2  USR-JOIN-2を説明する。図３１は参加手順２を示すフローチャートである。図３１に示すように、ユーザ装置２００は次のUSR-JOIN-2-1,  USR-JOIN-2-2を順に行う。USR-JOIN-2-1:  ag^x  =  y^Eが成立するかどうかを確認し、成立しなければ参加手順を終了する（ステップ１４４１）。つまり、２つの素数の積であるRSAモジュラスを法として等しいか否かを判定する。USR-JOIN-2-2:  成立すれば、メンバー公開鍵upkを(Y,  y,  E)に、メンバー秘密鍵uskを(x,  r)にセットし、upk、uskをユーザ記憶部２２０に書き込み（ステップ１４４２）、参加手順を終了する。【００８０】  本実施形態の鍵発行方法およびグループ署名システムにおいても、複数のユーザ装置と発行者装置との間でジョイン・プロトコルによるデータの送受信をコンカレントに行っても情報秘匿の安全性が向上する。また、実施形態１および実施形態２と比べて、発行者装置による発行手順２が省略可能であるため、工程が簡略化できる。【００８１】（実施形態４）  本実施形態のグループ署名システムについて説明する。装置構成については、実施形態１で説明した装置と同様であるため、ここではその詳細な説明を省略する。以下に、本実施形態のグループ署名システムによる鍵発行方法について説明する。本実施形態では、発行者装置によるデータの秘匿化処理の仕方を実施形態１から３とは異なる方法を用いている。【００８２】  実施形態１と同様にして、[発行者鍵生成手順ISS-GEN]および[開示者鍵生成手順OPN-GEN]の処理を行う。【００８３】  [発行手順ISS-ISSUEと参加手順USR-JOIN]  発行者装置１００とユーザ装置２００は相互通信を行いながら、それぞれ発行手順ISS-ISSUEと参加手順USR-JOINとを行う。まず、発行者装置１００が後述の[発行手順1  ISS-ISSUE-1]を行い、続いて、ユーザ装置２００が後述の[参加手順1  USR-JOIN-1]を行う。さらに、発行者装置１００が後述の[発行手順2  ISS-ISSUE-2]を行い、最後にユーザ装置２００が後述の[参加手順2  USR-JOIN-2]を行う。上述の手順の途中で、メンバー公開鍵upkとメンバー秘密鍵uskが生成される。メンバー公開鍵upkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にupkを載せるという方法が考えられるが、どのような方法でupkを公開してもよい。そして、実施形態１と同様にして、[署名手順  USR-SIGN]、[検証手順  VER-VERIFY]および[開示手順  OPN-OPEN]の処理を行う。【００８４】  [発行手順1  ISS-ISSUE-1]  発行手段１１４による発行手順1  ISS-ISSUE-1を説明する。図３２は発行手順１を示すフローチャートである。図３２に示すように、発行者装置１００は以下のISS-ISSUE-1-1,…,  ISS-ISSUE-1-4を順に行う。ISS-ISSUE-1-1:  ipk  =  (n,  a,  g,  h,  pf＿α)、opk  =  (F,  G,  H)、isk  =  (p,  q,  α)を発行者記憶部１２０から読み込む（ステップ１４５１）。ISS-ISSUE-1-2:  l＿eビットの非負整数eで、E  =  2^｛l＿E｝+eが素数となるものをランダムに選ぶ。さらに、l＿n+l＿sビットの非負整数ρをランダムに選び、g’  =  g^｛ρ/E｝  mod  n、h’  =  h^｛ρ/E｝  mod  nを計算する（ステップ１４５２）。ISS-ISSUE-1-3:  (g’,  h’)をユーザ装置２００に送信する（ステップ１４５３）。【００８５】  [参加手順1  USR-JOIN-1]  参加手段２１２による参加手順1  USR-JOIN-1を説明する。図３３は参加手順１の手順を示すフローチャートである。図３３に示すように、ユーザ装置２００は以下のUSR-JOIN-1-1,…,  USR-JOIN-1-7を順に行う。USR-JOIN-1-1:  (g’,  h’)を受信する（ステップ１４６１）。USR-JOIN-1-2:  ipk  =  (n,  a,  g,  h,  pf＿α)、opk  =  (F,  G,  H)をユーザ記憶部２２０から読み込む（ステップ１４６２）。USR-JOIN-1-3:  (ipk,  pf＿α)を入力して後述する[pf＿αの検証手順]を行う。[pf＿αの検証手順]がrejectを出力したら参加手順を終了する（ステップ１４６３）。USR-JOIN-1-4:  (Z/QZ)の元x、(Z/nZ)の元r’をランダムに選び、Y  =  G^｛x｝を計算する（ステップ１４６４）。USR-JOIN-1-5:  C  =  g’^｛x｝h’^｛r’｝  mod  nを計算する（ステップ１４６５）。USR-JOIN-1-6:  (n,  g,  h,  x,  r’,  g’,  h’,  Y,  C)を入力して後述する[(Y,  C)の正当性証明手順]を行い、pf＿｛Y,  C｝を作る（ステップ１４６６）。USR-JOIN-1-7:  (Y,  C,  pf＿｛Y,  C｝)を発行者装置１００に送信する（ステップ１４６７）。【００８６】  [発行手順2  ISS-ISSUE-2]  発行手段１１４による発行手順2  ISS-ISSUE-2を説明する。図３４は発行手順２を示すフローチャートである。図３４に示すように、発行者装置１００は以下のISS-ISSUE-2-1,…,  ISS-ISSUE-2-5を順に行う。ISS-ISSUE-2-1:  (Y,  C,  pf＿｛Y,  C｝)を受信する（ステップ１４７１）。ISS-ISSUE-2-2:  (n,  g,  h,  g’,  h’,  Y,  C,  pf＿｛Y,  C｝)を入力して後述する[(Y,  C)の正当性証明検証手順]を行う。もし[(Y,  C)の正当性証明検証手順]がrejectを出力したら参加手順を終了する（ステップ１４７２）。ISS-ISSUE-2-3:  g’’  =  g’^｛1/ρ｝を計算し、(Z/EZ)の元r’’をランダムに選び、y  =  a^｛1/E｝g’’h^｛r’’｝  mod  nを計算する（ステップ１４７３）。ISS-ISSUE-2-4:  YをユーザのIDと組にして開示者装置４００に送る（ステップ１４７４）。ISS-ISSUE-2-5:  (y,  r’’)をユーザ装置２００に送って（ステップ１４７５）、発行手順を終了する。【００８７】  また、実施形態１と同様にして、[参加手順2  USR-JOIN-2]、[pf＿αの生成手順]および[pf＿αの検証手順]の処理を行う。【００８８】  [(Y,  C)の正当性証明手順]  ユーザ装置制御部２１０による、(Y,C)の正当性証明手順を説明する。図３５は(Y,C)のフローチャートである。図３５に示すように、ユーザ装置２００は以下のPF-YC-GEN-1,…,  PF-YC-GEN-5を順に行う。PF-YC-GEN-1:  (n,  g,  h,  x,  r’,  g’,  h’,  Y,  C)を受け取る（ステップ１４８１）。PF-YC-GEN-2:  l＿q+l＿sビットの自然数x＿｛0,1｝とl＿n+l＿sビットの自然数r’＿｛0,1｝をランダムに選び、Y＿｛0,1｝  =  G^｛x＿｛0,1｝｝、C＿｛0,1｝  =  g’^｛x＿｛0,1｝｝h’^｛r’＿｛0,1｝｝を計算する（ステップ１４８２）。PF-YC-GEN-3:  c  =  H＿｛l＿c｝(n,  g,  h,  g’,  h’,  Y,  C,  Y＿｛0,1｝,  C＿｛0,1｝)を計算する（ステップ１４８３）。PF-YC-GEN-4:  x＿｛0,2｝  =  cx+x＿｛0,1｝、r’＿｛0,2｝  =  cr’+r’＿｛0,1｝を計算する（ステップ１４８４）。PF-YC-GEN-5:  pf＿｛Y,C｝  =  (c,  x＿｛0,2｝,  r’＿｛0,2｝)とする（ステップ１４８５）。【００８９】  [(Y,  C)の正当性証明検証手順]  発行者装置制御部１１０による、(Y,C)の正当性証明検証手順を説明する。図３６は(Y,C)正当性証明検証手順を示すフローチャートである。図３６に示すように、発行者装置１００は以下のPF-YC-VER-1,…,  PF-YC-VER-3を順に行う。PF-YC-VER-1:  (n,  g,  h,  g’,  h’,  Y,  C,  pf＿｛Y,  C｝)を受け取り、pf＿｛Y,  C｝  =  (c,x＿｛0,2｝,r’＿｛0,2｝)とパースする（ステップ１４９１）。PF-YC-VER-2:  Y’＿｛0,1｝  =  Y^｛-c｝  G^｛x＿｛0,2｝｝とC’＿｛0,1｝  =  C^｛-c｝  g’^｛x＿｛0,2｝｝h’^｛r’＿｛0,2｝｝を計算する（ステップ１４９２）。PF-YC-VER-3:  c  =  H＿｛l＿c｝(n,  g,  h,  g’,  h’,  Y,  C,  Y’＿｛0,1｝,  C’＿｛0,1｝)が成立すればacceptし、そうでなければrejectする（ステップ１４９３）。【００９０】  本実施形態の追加メンバーへの鍵発行方法およびグループ署名システムでは、発行者装置が発行者装置の秘密鍵を使って先に第１の秘匿データを作成し、次にユーザ装置がその第１の秘匿データを加工して別の第２の秘匿データを作り、そしてユーザ装置がその加工されたデータの正当性を発行者装置に証明している。このようにして、従来のグループ署名システムとは異なり、ユーザ装置がデータの正当性を証明する前に発行者装置が発行者装置の秘密鍵を使ってデータを加工するので、複数のユーザ装置と発行装置とのジョイン・プロトコルによるデータの送受信をコンカレントに行った場合にも情報の安全性が向上する。【００９１】  また、本実施形態における情報秘匿化処理は、データの暗号化処理および復号化処理などを必要としないため、実施形態１に比べて情報処理速度が速くなる。【００９２】  （実施形態５）  本実施形態のグループ署名システムについて説明する。装置構成については、実施形態１で説明した装置と同様であるため、ここではその詳細な説明を省略する。以下では、実施形態１と異なる構成について説明する。【００９３】  各装置の記憶部にはセキュリティ・パラメータkが事前に入力されているものとする。どのような方法でkが入力されるのかは問わない。Γ＿1,  Γ＿2,  Γ＿Tを位数pの巡回群で、Γ＿1×Γ＿2からΓ＿Tへの双線形写像eが定義されていて、しかもpのビット数がkであるものとする。さらにΓを位数pの巡回群とする。各装置の記憶部にはΓ＿1,  Γ＿2,  Γ＿Tを記述するパラメータと、pとが事前に入力されているものとする。どのような方法でΓ＿1,  Γ＿2,  Γ＿Tを記述するパラメータと、pとが入力されるのかは問わない。【００９４】  次に、本実施形態のグループ署名システムによる鍵発行方法について説明する。本実施形態の鍵発行方法は、発行者装置による情報秘匿化処理が実施形態２と異なる他は、実施形態２で説明した方法と同様であるため、以下では、実施形態２と異なる処理について詳細に説明する。【００９５】  [発行者鍵生成手順  ISS-GEN]  発行者鍵生成手段１１２による発行者鍵生成手順ISS-GENを説明する。図３７は発行者鍵生成手順を示すフローチャートである。図３７に示すように、発行者装置１００は以下のISS-GEN-1とISS-GEN-2を順に行う。ISS-GEN-1:  Γ＿1の元G＿1,  H,  K,  Γ＿2の元G＿2、および(Z/pZ)の元wをランダムに選び  、Y  =  wG＿2とする（ステップ１５０１）。ISS-GEN-2:  発行者公開鍵ipkを(G＿1,  G＿2,  H,  K,  Y)にセットし、発行者秘密鍵iskをwにセットし、ipkとiskを発行者記憶部１２０に記憶する（ステップ１５０２）。また、開示者装置４００は、実施形態２と同様にして[開示者鍵生成手順  OPN-GEN]の処理を行う。【００９６】  [発行手順  ISS-ISSUE  と  参加手順USR-JOIN]  発行者装置１００とユーザ装置２００は相互通信を行いながら、それぞれ発行手順  ISS-ISSUEと参加手順USR-JOINとを行う。まず、発行者装置１００が後述の[発行手順1  ISS-ISSUE-1]を行い、続いて、ユーザ装置２００が後述の[参加手順1  USR-JOIN-1]を行う。さらに、発行者装置１００が後述の[発行手順2  ISS-ISSUE-2]を行い、最後にユーザ装置２００が後述の[参加手順2  USR-JOIN-2]を行う。上述の手順の途中で、メンバー公開鍵upkとメンバー秘密鍵uskが生成される。メンバー公開鍵upkは何らかの方法で全ての装置に公開される。例えば、ネット上の公開掲示板にupkを載せるという方法が考えられるが、どのような方法でupkを公開してもよい。そして、実施形態２と同様にして、[署名手順  USR-SIGN]、[検証手順  VER-VERIFY]および[開示手順  OPN-OPEN]の処理を行う。【００９７】  [発行手順1  ISS-ISSUE-1]  発行手段１１４による発行手順1  ISS-ISSUE-1を説明する。図３８は発行手順１を示すフローチャートである。図３８に示すように、発行者装置１００は以下のISS-ISSUE-1-1,ISS-ISSUE-1-2を順に行う。ISS-ISSUE-1-1:  ipk  =  (G＿1,  G＿2,  H,  K,  Y)、opk  =  (G,  S,  T)、isk  =  (w,  lsk)を発行者記憶部１２０から読み込む（ステップ１５１１）。ISS-ISSUE-1-2:  (Z/pZ)の元y＿Uとρとをランダムに選び、H’  =  (ρ/(w+y＿U))  H、K’  =  (ρ/(w+y＿U))  Kを計算し、H’とK’とをユーザ装置２００に送信する（ステップ１５１２）。【００９８】  [参加手順1  USR-JOIN-1]  参加手段２１２による参加手順1  USR-JOIN-1を説明する。図３９は参加手順１を示すフローチャートである。図３９に示すように、ユーザ装置２００は以下のUSR-JOIN-1-1,…,  USR-JOIN-1-6を順に行う。USR-JOIN-1-1:  (H’,K’)を受信する（ステップ１５２１）。USR-JOIN-1-2:  ipk  =  (G＿1,  G＿2,  H,  K,  Y)、opk  =  (G,  S,  T)をユーザ記憶部２２０から読み込む（ステップ１５２２）。USR-JOIN-1-3:  (Z/pZ)の元x＿U、z’＿Uをランダムに選び、Ider＿U  =  x＿U  G、を計算する（ステップ１５２３）。USR-JOIN-1-4:  C  =  H’^｛x＿U｝K’^｛z’＿U｝を計算する（ステップ１５２４）。USR-JOIN-1-5:  (G,H’,K’,  x＿U,  z'＿U,  Ider＿U,  C)を入力して後述する[(Ider＿U,  C)の正当性証明手順]を行い、pf＿｛Ider＿U,  C｝を作る（ステップ１５２５）。USR-JOIN-1-6:  (Ider＿U,  Cipher,  pf＿｛Ider＿U,  C｝)を発行者装置１００に送信する（ステップ１５２６）。【００９９】  [発行手順2  ISS-ISSUE-2]  発行手段１１４による発行手順2  ISS-ISSUE-2を説明する。図４０は発行手順２を示すフローチャートである。図４０に示すように、発行者装置１００は以下のISS-ISSUE-2-1,…,  ISS-ISSUE-2-5を順に行う。ISS-ISSUE-2-1:  (Ider＿U,  Cipher,  pf＿｛Ider＿U,  C｝)を受信する（ステップ１５３１）。ISS-ISSUE-2-2:  (G,  H’,K’,  Ider＿U,  C,  pf＿｛Ider＿U,  C｝)を入力して後述する[(Ider＿U,  C)の正当性証明検証手順]を行う。もし[(Ider＿U,  C)の正当性証明検証手順]がrejectを出力したら参加手順を終了する（ステップ１５３２）。ISS-ISSUE-2-3:  G＿1’’  =  C^｛1/ρ｝を計算し、(Z/eZ)の元z’’＿Uをランダムに選び、A＿U  =  (1/(w+y＿U))  G＿1-  G＿1’’-  z’’＿UKを計算���る（ステップ１５３３）。なお、G＿1’’は実施形態４ではg''に相当し、秘匿化が解除されたデータである。ISS-ISSUE-2-4:  Ider＿UをユーザのIDと組にして開示者装置４００に送る（ステップ１５３４）。ISS-ISSUE-2-5:  (A＿U,  z’’＿U)をユーザ装置２００に送って（ステップ１５３５）、発行手順を終了する。【０１００】  実施形態２と同様にして、[参加手順2  USR-JOIN-2]の処理を行う。【０１０１】  [(Ider＿U,  C)の正当性証明手順]  参加手段２１２による[(Ider＿U,C)の正当性証明手順]を説明する。図４１は[(Ider＿U,C)の正当性証明手順]を示すフローチャートである。図４１に示すように、ユーザ装置２００は以下のUSR-PF-1,…,  USR-PF-5を順に行う。USR-PF-1:  (G,  H’,  K’,  x＿U,  z’＿U,  Ider＿U,  C)を受け取る（ステップ１５４１）。USR-PF-2:  (Z/qZ)の元x＿｛U,0,1｝,  z’＿｛U,0,1｝をランダムに選び、C＿｛0,1｝  =  H’^｛x＿｛U,0,1｝｝K’^｛z’＿｛U,0,1｝｝を計算する（ステップ１５４２）。USR-PF-3:  c  =  H＿｛Z/qZ｝  (G,  H’,  K’,  x＿U,  z’＿U,  Ider＿U,  C,  C＿｛0,1｝)を計算する（ステップ１５４３）。USR-PF-4:  x＿｛U,0,2｝  =  cx＿U+x＿｛U,0,2｝、z＿｛U,0,2｝  =  cz＿U+z＿｛U,0,2｝を計算する（ステップ１５４４）。USR-PF-5:  pf＿｛Ider＿U,C｝  =  (c,x＿｛U,0,2｝,  z＿｛U,0,2｝)とする（ステップ１５４５）。【０１０２】  [(Ider＿U,C)の正当性証明検証手順]  発行手段１１４による[(Ider＿U,  C)の正当性証明検証手順]を説明する。図４２は[(Ider＿U,  C)の正当性証明検証手順]を示すフローチャートである。図４２に示すように、発行者装置１００は以下のUSR-VER-1,…,  USR-VER-4を順に行う。USR-VER-1:  (G,  H’,  K’,  Ider＿U,  C,  pf＿｛Ider＿U,C｝)を受け取る（ステップ１５５１）。USR-VER-2:  pf＿｛Ider＿U,C｝  =  (c,x＿｛U,0,2｝,z＿｛U,0,2｝)とパースする（ステップ１５５２）。USR-VER-3:  C’＿｛0,1｝  =  H’^｛x＿｛U,0,2｝｝K’^｛z’＿｛U,0,2｝｝C^｛-c｝を計算する（ステップ１５５３）。USR-VER-4:  c  =  H＿｛Z/qZ｝(G,  H’,  K’,  x＿U,  z’＿U,  Ider＿U,  C,  C’＿｛0,1｝)が成立すればacceptを、そうでなければrejectを出力する（ステップ１５５４）。【０１０３】  本実施形態の鍵発行方法およびグループ署名システムにおいても、データの暗号化処理および復号化処理などを必要としないため、実施形態２に比べて情報処理速度が速くなる。【０１０４】  なお、上記実施形態の鍵発行方法をコンピュータに実行させるためのプログラムに適用してもよい。また、このプログラムをコンピュータが読み取り可能な記録媒体に記録してもよい。【０１０５】  また、本発明は上記実施例に限定されることなく、発明の範囲内で種々の変形が可能であり、それらも本発明の範囲内に含まれることはいうまでもない。
【図１】
2007010903.tif 000002
【図２】
2007010903.tif 000003
【図３】
2007010903.tif 000004
【図４】
2007010903.tif 000005
【図５】
2007010903.tif 000006
【図６】
2007010903.tif 000007
【図７】
2007010903.tif 000008
【図８】
2007010903.tif 000009
【図９】
2007010903.tif 000010
【図１０】
2007010903.tif 000011
【図１１】
2007010903.tif 000012
【図１２】
2007010903.tif 000013
【図１３】
2007010903.tif 000014
【図１４】
2007010903.tif 000015
【図１５】
2007010903.tif 000016
【図１６】
2007010903.tif 000017
【図１７】
2007010903.tif 000018
【図１８】
2007010903.tif 000019
【図１９】
2007010903.tif 000020
【図２０】
2007010903.tif 000021
【図２１】
2007010903.tif 000022
【図２２】
2007010903.tif 000023
【図２３】
2007010903.tif 000024
【図２４】
2007010903.tif 000025
【図２５】
2007010903.tif 000026
【図２６】
2007010903.tif 000027
【図２７】
2007010903.tif 000028
【図２８】
2007010903.tif 000029
【図２９】
2007010903.tif 000030
【図３０】
2007010903.tif 000031
【図３１】
2007010903.tif 000032
【図３２】
2007010903.tif 000033
【図３３】
2007010903.tif 000034
【図３４】
2007010903.tif 000035
【図３５】
2007010903.tif 000036
【図３６】
2007010903.tif 000037
【図３７】
2007010903.tif 000038
【図３８】
2007010903.tif 000039
【図３９】
2007010903.tif 000040
【図４０】
2007010903.tif 000041
【図４１】
2007010903.tif 000042
【図４２】
2007010903.tif 000043
【国際調査報告】
2007010903.tif 000044
2007010903.tif 000045
2007010903.tif 000046
2007010903.tif 000047
2007010903.tif 000048
2007010903.tif 000049