(57)【要約】  本発明の一実施形態に係るグループ署名システムは、互いに通信可能なグループ管理者装置１０、署名者装置２０１〜２０ｎ及び検証者装置３０を備えている。ここで、各装置１０，２０１〜２０ｎ，３０が用いるグループ署名方式は、ＲＳＡのように位数が未知となる乗法巡回群を一切用いず、素数位数ｑの乗法巡回群Ｇのみを用いる方式であり、且つリプレゼンテーションｋｉ１，ｋｉ２をメンバ秘密鍵としている。また、署名者を特定するための情報としてＴｉ＝ｇ１＾｛ｋｉ１｝を利用している。このため、従来の［ＣＧ０４］方式に比べ、計算量を減らして計算速度を向上できる。
2009008069.tif 000002
【特許請求の範囲】
【請求項１】
互いに通信可能なグループ管理者装置（１０）、署名者装置（２０ｉ）及び検証者装置（３０）を備え、各装置がグループ署名方式を用いるグループ署名システムであって、
前記グループ管理者装置は、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータを記憶するパラメータ記憶手段（１１）と、
前記パラメータ記憶手段内の公開パラメータに基づいて、値ａ，ｂ∈Ｚｑを含むグループ秘密鍵と、第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂを満たす値ｇ２，ｆ及び前記生成元ｇ１を含むグループ公開鍵とを生成するグループ鍵生成手段（１４）と、
前記グループ秘密鍵、前記グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて、第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵を算出するメンバ秘密鍵生成手段（但し、＾はベキ乗を表す記号）（１５）と、
前記メンバ秘密鍵及び前記生成元ｇ１に基づいて、署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝を算出する署名者特定情報算出手段（１５）と、を備えており、
前記署名者装置は、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータと、前記グループ公開鍵、前記メンバ秘密鍵、前記署名者特定情報Ｔｉ及びメッセージを記憶する署名者用記憶手段（２１）と、
前記署名者用記憶手段内の公開パラメータ及びグループ公開鍵に基づいて前記署名者特定情報Ｔｉを暗号化し、当該署名者特定情報Ｔｉの暗号文データを生成する暗号文生成手段（２５）と、
前記署名者用記憶手段内の公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及び前記メッセージと、前記署名者特定情報Ｔｉの暗号文データとに基づいて、当該メンバ秘密鍵を知っていて、且つ、前記暗号文データが当該署名者特定情報Ｔｉを基に正しく生成されていることを示す零知識証明を生成する零知識証明生成手段（２５）と、
前記暗号文データ及び前記零知識証明からなるグループ署名と前記メッセージとを前記検証者装置に送信する手段（２３）と、を備えており、
前記検証者装置は、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータと前記グループ公開鍵とを記憶する検証者用記憶手段（３１）と、
前記署名者装置から前記グループ署名及びメッセージを受信する手段（３３）と、
前記受信したグループ署名及びメッセージと前記検証者用記憶手段内の公開パラメータ及びグループ公開鍵とに基づいて、当該グループ署名の正当性を検証する検証手段（３４）と、
前記検証した結果を前記署名者装置に送信する手段（３３）と、
を備えたことを特徴とするグループ署名システム。
【請求項２】
グループ署名方式を用いる署名者装置（２０ｉ）及び検証者装置（３０）に通信可能なグループ管理者装置（１０）であって、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータを記憶するパラメータ記憶手段（１１）と、
前記パラメータ記憶手段内の公開パラメータに基づいて、値ａ，ｂ∈Ｚｑを含むグループ秘密鍵と、第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂを満たす値ｇ２，ｆ及び前記生成元ｇ１を含むグループ公開鍵とを生成するグループ鍵生成手段（１４）と、
前記グループ秘密鍵、前記グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて、第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵を算出するメンバ秘密鍵生成手段（但し、＾はベキ乗を表す記号）（１５）と、
前記メンバ秘密鍵及び前記生成元ｇ１に基づいて、署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝を算出する署名者特定情報算出手段（１５）と、
前記グループ署名方式におけるグループ署名を生成するための前記公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及び前記署名者特定情報Ｔｉを前記署名者装置に送信する手段（１３）と、
前記グループ署名方式におけるグループ署名を検証するための前記公開パラメータ及び前記グループ公開鍵を前記検証者装置に送信する手段（１３）と、
を備えたことを特徴とするグループ管理者装置。
【請求項３】
請求項２に記載のグループ管理者装置において、
前記署名者特定情報Ｔｉ及びユーザ識別情報ＩＤ（ｉ）が互いに関連付けて記憶されているユーザ情報記憶手段（１１）と、
前記署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝に関し、前記メンバ秘密鍵を知っていて、且つ、前記暗号文データが前記署名者特定情報Ｔｉを基に正しく生成されていることを示す零知識証明と、前記署名者特定情報Ｔｉの暗号文データとからなるグループ署名及びメッセージを前記署名者装置から受信する手段（１３）と、
前記受信したグループ署名及びメッセージと前記パラメータ記憶手段内の公開パラメータと前記生成したグループ秘密鍵及びグループ公開鍵とに基づいて、当該グループ署名の正当性を検証する署名検証手段（１６）と、
前記検証した結果が正当性を示すとき、前記グループ秘密鍵に基づいて前記暗号文データから署名者特定情報Ｔｉを計算し、得られた署名者特定情報Ｔｉに対応するユーザ識別情報ＩＤ（ｉ）を前記ユーザ情報記憶手段から特定する署名者特定手段（１７）と、を備えており、
前記暗号文データは、前記公開パラメータ及びグループ公開鍵に基づいて前記署名者特定情報Ｔｉが前記署名者装置により暗号化されたデータであり、
前記零知識証明は、前記公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及びメッセージと、前記署名者特定情報Ｔｉの暗号文データとに基づいて前記署名者装置により生成されたデータであることを特徴とするグループ管理者装置。
【請求項４】
グループ署名方式を用いるグループ管理者装置（１０）及び検証者装置（３０）に通信可能な署名者装置（２０ｉ）であって、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータと、前記公開パラメータに基づいて、値ａ，ｂ∈Ｚｑと第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂとを満たすように生成された値ｇ２，ｆ及び前記生成元ｇ１を含むグループ公開鍵と、前記値ａ，ｂ∈Ｚｑ、前記グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて、第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすように生成（但し、＾はベキ乗を表す記号）されたリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵と、前記メンバ秘密鍵及び前記生成元ｇ１に基づいて生成された署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝とを前記グループ管理者装置から受信する手段（２３）と、
前記受信した公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及び前記署名者特定情報Ｔｉとメッセージとを記憶するための署名者用記憶手段（２１）と、
前記メッセージを作成して前記署名者用記憶手段に書き込む手段（２４）と、
前記署名者用記憶手段内の公開パラメータ及びグループ公開鍵に基づいて前記署名者特定情報Ｔｉを暗号化し、当該署名者特定情報Ｔｉの暗号文データを生成する暗号文生成手段（２５）と、
前記署名者用記憶手段内の公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及び前記メッセージと、前記署名者特定情報Ｔｉの暗号文データとに基づいて、当該メンバ秘密鍵を知っていて、且つ、前記暗号文データが当該署名者特定情報Ｔｉを基に正しく生成されていることを示す零知識証明を生成する零知識証明生成手段（２５）と、
前記暗号文データ及び前記零知識証明からなるグループ署名と前記メッセージとを前記検証者装置に送信する手段（２３）と、
を備えたことを特徴とする署名者装置。
【請求項５】
グループ署名方式を用いるグループ管理者装置（１０）及び署名者装置（２０ｉ）に通信可能な検証者装置（３０）であって、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータと、前記公開パラメータに基づいて、値ａ，ｂ∈Ｚｑと第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂとを満たすように生成された値ｇ２，ｆ及び前記生成元ｇ１を含むグループ公開鍵とを前記グループ管理者装置から受信する手段（３３）と、
前記受信した公開パラメータと前記グループ公開鍵とを記憶する検証者用記憶手段（３１）と、
前記値ａ，ｂ∈Ｚｑ、前記グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすように生成（但し、＾はベキ乗を表す記号）されたリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵と、前記メンバ秘密鍵及び前記生成元ｇ１に基づいて生成された署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝とに関し、前記メンバ秘密鍵を知っていて、且つ、前記暗号文データが前記署名者特定情報Ｔｉを基に正しく生成されていることを示す零知識証明と、前記署名者特定情報Ｔｉの暗号文データとからなるグループ署名及びメッセージを前記署名者装置から受信する手段（３３）と、
前記受信したグループ署名及びメッセージと前記検証者用記憶手段内の公開パラメータ及びグループ公開鍵とに基づいて、当該グループ署名の正当性を検証する検証手段（３４）と、
前記検証した結果を前記署名者装置に送信する手段（３３）と、を備えており、
前記暗号文データは、前記公開パラメータ及びグループ公開鍵に基づいて前記署名者特定情報Ｔｉが前記署名者装置により暗号化されたデータであり、
前記零知識証明は、前記公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及びメッセージと、前記署名者特定情報Ｔｉの暗号文データとに基づいて前記署名者装置により生成されたデータであることを特徴とする検証者装置。
【請求項６】
グループ署名方式を用いる署名者装置（２０ｉ）及び検証者装置（３０）に通信可能なグループ管理者装置（１０）のプログラムであって、
前記グループ管理者装置のコンピュータを、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータを前記コンピュータのメモリ（１１）に書き込む手段（１３）、
前記メモリ内の公開パラメータに基づいて、値ａ，ｂ∈Ｚｑを含むグループ秘密鍵と、第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂを満たす値ｇ２，ｆ及び前記生成元ｇ１を含むグループ公開鍵とを生成するグループ鍵生成手段（１４）、
前記グループ秘密鍵、前記グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて、第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵を算出するメンバ秘密鍵生成手段（但し、＾はベキ乗を表す記号）（１５）、
前記メンバ秘密鍵及び前記生成元ｇ１に基づいて、署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝を算出する署名者特定情報算出手段（１５）、
前記グループ署名方式におけるグループ署名を生成するための前記公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及び前記署名者特定情報Ｔｉを前記署名者装置に送信する手段（１３）、
前記グループ署名方式におけるグループ署名を検証するための前記公開パラメータ及び前記グループ公開鍵を前記検証者装置に送信する手段（１３）、
として機能させるためのプログラム。
【請求項７】
請求項６に記載のプログラムにおいて、
前記コンピュータを、
前記署名者特定情報Ｔｉ及びユーザ識別情報ＩＤ（ｉ）を互いに関連付けて前記メモリに書き込む手段（１５）、
前記署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝に関し、前記メンバ秘密鍵を知っていて、且つ、前記暗号文データが前記署名者特定情報Ｔｉを基に正しく生成されていることを示す零知識証明と、前記署名者特定情報Ｔｉの暗号文データとからなるグループ署名及びメッセージを前記署名者装置から受信する手段（１３）、
前記受信したグループ署名及びメッセージと前記パラメータ記憶手段内の公開パラメータと前記生成したグループ秘密鍵及びグループ公開鍵とに基づいて、当該グループ署名の正当性を検証する署名検証手段（１６）、
前記検証した結果が正当性を示すとき、前記グループ秘密鍵に基づいて前記暗号文データから署名者特定情報Ｔｉを計算し、得られた署名者特定情報Ｔｉに対応するユーザ識別情報ＩＤ（ｉ）を前記メモリから特定する署名者特定手段（１７）と、として機能させ、
前記暗号文データは、前記公開パラメータ及びグループ公開鍵に基づいて前記署名者特定情報Ｔｉが前記署名者装置により暗号化されたデータであり、
前記零知識証明は、前記公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及びメッセージと、前記署名者特定情報Ｔｉの暗号文データとに基づいて前記署名者装置により生成されたデータであることを特徴とするプログラム。
【請求項８】
グループ署名方式を用いるグループ管理者装置（１０）及び検証者装置（３０）に通信可能な署名者装置（２０ｉ）のプログラムであって、
前記署名者装置のコンピュータを、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータと、前記公開パラメータに基づいて、値ａ，ｂ∈Ｚｑと第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂとを満たすように生成された値ｇ２，ｆ及び前記生成元ｇ１を含むグループ公開鍵と、前記値ａ，ｂ∈Ｚｑ、前記グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて、第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすように生成（但し、＾はベキ乗を表す記号）されたリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵と、前記メンバ秘密鍵及び前記生成元ｇ１に基づいて生成された署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝とを前記グループ管理者装置から受信する手段（２３）、
前記受信した公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及び前記署名者特定情報Ｔｉとメッセージとを前記コンピュータのメモリ（２１）に書き込む手段（２３）、
前記メッセージを作成して前記メモリに書き込む手段（２４）、
前記メモリ内の公開パラメータ及びグループ公開鍵に基づいて前記署名者特定情報Ｔｉを暗号化し、当該署名者特定情報Ｔｉの暗号文データを生成する暗号文生成手段（２５）、
前記メモリ内の公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及び前記メッセージと、前記署名者特定情報Ｔｉの暗号文データとに基づいて、当該メンバ秘密鍵を知っていて、且つ、前記暗号文データが当該署名者特定情報Ｔｉを基に正しく生成されていることを示す零知識証明を生成する零知識証明生成手段（２５）、
前記暗号文データ及び前記零知識証明からなるグループ署名と前記メッセージとを前記検証者装置に送信する手段（２３）、
として機能させるためのプログラム。
【請求項９】
グループ署名方式を用いるグループ管理者装置（１０）及び署名者装置（２０ｉ）に通信可能な検証者装置（３０）のプログラムであって、
前記検証者装置のコンピュータを、
前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータと、前記公開パラメータに基づいて、値ａ，ｂ∈Ｚｑと第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂとを満たすように生成された値ｇ２，ｆ及び前記生成元ｇ１を含むグループ公開鍵とを前記グループ管理者装置から受信する手段（３３）、
前記受信した公開パラメータと前記グループ公開鍵とを前記コンピュータのメモリ（３１）に書き込む手段（３３）、
前記値ａ，ｂ∈Ｚｑ、前記グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすように生成（但し、＾はベキ乗を表す記号）されたリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵と、前記メンバ秘密鍵及び前記生成元ｇ１に基づいて生成された署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝とに関し、前記メンバ秘密鍵を知っていて、且つ、前記暗号文データが前記署名者特定情報Ｔｉを基に正しく生成されていることを示す零知識証明と、前記署名者特定情報Ｔｉの暗号文データとからなるグループ署名及びメッセージを前記署名者装置から受信する手段（３３）、
前記受信したグループ署名及びメッセージと前記メモリ内の公開パラメータ及びグループ公開鍵とに基づいて、当該グループ署名の正当性を検証する検証手段（３４）、
前記検証した結果を前記署名者装置に送信する手段（３３）、として機能させ、
前記暗号文データは、前記公開パラメータ及びグループ公開鍵に基づいて前記署名者特定情報Ｔｉが前記署名者装置により暗号化されたデータであり、
前記零知識証明は、前記公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及びメッセージと、前記署名者特定情報Ｔｉの暗号文データとに基づいて前記署名者装置により生成されたデータであることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループ署名システム、装置及びプログラムに係り、例えば、計算量を減らして計算速度を向上し得るグループ署名システム、装置及びプログラムに関する。
【背景技術】
【０００２】
グループ署名方式は、匿名性を持った電子署名として１９９１年にチャウム（Chaum）らによって提案された（D. Chaum and E. van Heyst, “Group Signatures,” In Proc. of EUROCRYPT ’91, LNCS 547, pp.257-265, 1991.参照）。通常の電子署名方式では、署名検証のための公開鍵と署名生成のための秘密鍵が１対１で対応するため、署名生成者の匿名性を保てない。【０００３】
これに対し、グループ署名方式では、署名検証のためのグループ公開鍵と署名生成のためのメンバ秘密鍵が１対ｎで対応するため、署名生成者の匿名性を保っている。すなわち、グループ署名方式は、１個のグループ公開鍵と、ｎ個のメンバ秘密鍵とが対応するため、署名検証の際に、署名生成者を特定できない性質がある。また、グループ署名方式は、特権者であるグループ管理者だけが署名者を特定できるという性質を持っている。【０００４】
しかしながら、当初のグループ署名方式は、署名長や署名生成計算量がメンバ数に比例するため、多数のメンバをもつグループでの効率が非常に低く、運用に適さないものである。【０００５】
これに対し、効率がメンバ数に依存しないグループ署名方式が１９９７年にカメニッシュ（Camenisch）らにより提案された（J. Camenisch and M. Stadler, “Efficient group signature schemes for large groups,” In Proc. of CRYPTO ’97, LNCS 1294, pp.410-424, 1997.参照）。この方式では、メンバ秘密鍵に対するグループ管理者の署名をメンバ証明書（membership certificate）として用いる。グループ署名には、グループ管理者の公開鍵で暗号化されたメンバ証明書（またはその一部）と、メンバ証明書が正しく暗号化されていることと、メンバ秘密鍵及びメンバ証明書を保持することとを示す非対話的知識証明が含まれる。署名検証者は、非対話的知識証明の検証により、メンバによる署名であることを検証できる。さらにグループ管理者は、メンバ証明書の復号により、署名者を特定できる。このようなメンバ証明書を用いる概念は、その後のグループ署名方式の基礎となる重要なものである。【０００６】
しかしながら、このカメニッシュらの方式は、効率がメンバ数に依存しないものの、実用的な観点からは効率が低いものである。【０００７】
効率的（practical）な最初のグループ署名方式は、２０００年にアテニース（Ateniese）らによって提案された方式（G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik, “A practical and provably secure coalition-resistant group signature scheme,” In Proc.of CRYPTO 2000, LNCS 1880,pp.255-270, 2002. 以下、[ＡＣＪＴ００]方式という。）である。アテニースのグループ署名方式は、大幅に効率化されており、実用化が検討可能となっている。アテニースのグループ署名方式は、署名生成の際にＲＳＡ署名生成の２００倍程度の計算量が必要であるため、継続的に改良が検討されている。アテニースの方式は、安全性が強ＲＳＡ問題（strong-RSA problem）に基づいている。【０００８】
現在、広く知られている高速なグループ署名方式は、２００４年にカメニッシュ（Camenisch）らによって提案された方式（J. Camenisch and J. Groth, “Group Signatures: Better Efficiency and New Theoretical Aspects,” Forth Int. Conf. on Security in Communication Networks − SCN 2004, LNCS 3352, 120-133, 2005. 以下、[ＣＧ０４]方式という。full paper は以下のＵＲＬから取得可能（２００７年６月現在）http://www.brics.dk/jg/）である。[ＣＧ０４]方式の署名生成計算量は、ＲＳＡ署名生成の８倍程度にまで低減されている。[ＣＧ０４]方式の安全性も強ＲＳＡ問題に基づいている。
【発明の開示】
【０００９】
以上のような［ＣＧ０４］方式のグループ署名方式は、[ＡＣＪＴ００]方式よりも計算量が小さくなっているが、本発明者の検討によれば、グループ署名方式に対する実用的な側面も強化する必要があると考え、さらに計算量を減らして計算速度を向上させる余地がある。
【００１０】
本発明の目的は、計算量を減らして計算速度を向上し得るグループ署名システム、装置及びプログラムを提供することにある。
【００１１】
本発明の第１の局面(aspect)は、互いに通信可能なグループ管理者装置、署名者装置及び検証者装置を備え、各装置がグループ署名方式を用いるグループ署名システムであって、前記グループ管理者装置としては、前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータを記憶するパラメータ記憶手段と、前記パラメータ記憶手段内の公開パラメータに基づいて、値ａ，ｂ∈Ｚｑを含むグループ秘密鍵と、第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂを満たす値ｇ２，ｆ及び前記生成元ｇ１を含むグループ公開鍵とを生成するグループ鍵生成手段と、前記グループ秘密鍵、前記グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて、第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵を算出するメンバ秘密鍵生成手段（但し、＾はベキ乗を表す記号）と、前記メンバ秘密鍵及び前記生成元ｇ１に基づいて、署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝を算出する署名者特定情報算出手段と、を備えており、前記署名者装置としては、前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータと、前記グループ公開鍵、前記メンバ秘密鍵、前記署名者特定情報Ｔｉ及びメッセージを記憶する署名者用記憶手段と、前記署名者用記憶手段内の公開パラメータ及びグループ公開鍵に基づいて前記署名者特定情報Ｔｉを暗号化し、当該署名者特定情報Ｔｉの暗号文データを生成する暗号文生成手段と、前記署名者用記憶手段内の公開パラメータ、前記グループ公開鍵、前記メンバ秘密鍵及び前記メッセージと、前記署名者特定情報Ｔｉの暗号文データとに基づいて、当該メンバ秘密鍵及び当該署名者特定情報Ｔｉを知っていることを示す零知識証明を生成する零知識証明生成手段と、前記暗号文データ及び前記零知識証明からなるグループ署名と前記メッセージとを前記検証者装置に送信する手段と、を備えており、前記検証者装置としては、前記グループ署名方式に用いる素数位数ｑ、及び前記ｑの乗法巡回群Ｇの生成元ｇ１を含む公開パラメータと前記グループ公開鍵とを記憶する検証者用記憶手段と、前記署名者装置から前記グループ署名及びメッセージを受信する手段と、前記受信したグループ署名及びメッセージと前記検証者用記憶手段内の公開パラメータ及びグループ公開鍵とに基づいて、当該グループ署名の正当性を検証する検証手段と、前記検証した結果を前記署名者装置に送信する手段と、署名者特定のためにグループ管理者装置にメッセージとグループ署名を送信する手段と、を備えたグループ署名システムである。
【００１２】
第１の局面によれば、素数位数ｑの乗法巡回群Ｇを用いて乗法巡回群として位数が未知のものを利用せずに、位数が既知のもののみを利用したグループ署名方式とし、且つリプレゼンテーションｋｉ１，ｋｉ２をメンバ秘密鍵としたグループ署名方式を実現したことにより、従来の［ＣＧ０４］方式に比べ、計算量を減らして計算速度を向上することができる。
【００１３】
なお、以上の局面は、各装置からなる「システム」として表現したが、これに限らず、各装置の集合又は装置毎の「装置」、「プログラム」、「コンピュータ読み取り可能な記憶媒体」又は「方法」として表現してもよい。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の一実施形態に係るグループ署名システムの構成を示す模式図である。
【図２】図２は、同実施形態におけるグループ管理者装置の構成を示す模式図である。
【図３】図３は、同実施形態におけるグループ管理者用記憶部の構成を示す模式図である。
【図４】図４は、同実施形態における署名者装置の構成を示す模式図である。
【図５】図５は、同実施形態における署名者用記憶部の構成を示す模式図である。
【図６】図６は、同実施形態における検証者装置の構成を示す模式図である。
【図７】図７は、同実施形態における検証者用記憶部の構成を示す模式図である。
【図８】図８は、同実施形態における鍵ペアの生成処理を説明するためのフローチャートである。
【図９】図９は、同実施形態におけるメンバ秘密鍵の生成処理を説明するためのフローチャートである。
【図１０】図１０は、同実施形態における署名者特定情報の算出処理を説明するためのフローチャートである。
【図１１】図１１は、同実施形態における暗号化処理を説明するためのフローチャートである。
【図１２】図１２は、同実施形態における零知識証明の算出処理を説明するためのフローチャートである。
【図１３】図１３は、同実施形態における署名検証処理を説明するためのフローチャートである。
【図１４】図１４は、同実施形態における署名検証処理を説明するためのフローチャートである。
【図１５】図１５は、同実施形態における署名者特定処理を説明するためのフローチャートである。
【図１６】図１６は、同実施形態の効果を従来と比較して示す図である。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の一実施形態について図面を参照して詳細に説明するが、その前に本発明の一実施形態に係るグループ署名方式（以下、実施形態方式という）の概要を述べる。【００１６】
実施形態方式は極めて効率が良いことが最大の特長である。高速にベキ乗剰余演算を行う手法である指数同時乗算（Simultaneous Multiple Exponentiation）法を用いた場合、[ＣＧ０４]方式がＲＳＡ署名生成の８倍以上の計算量であるのに対し、実施形態方式ではＲＳＡ署名生成のわずか３倍程度の計算量で署名生成を行える。また、指数同時乗算法では底の値によってテーブルの事前計算を行う必要があるが、実施形態方式ではベキ乗剰余演算の底が常に固定であるため、テーブルの事前計算を毎回行う必要がなく、テーブルを保持することで計算量をさらに若干減らすことができる。【００１７】
さらに、実施形態方式は署名生成に利用するメンバ秘密鍵が非常に短く、そのビット長は[ＣＧ０４]方式の１/１０、ＲＳＡ方式の１/９でしかない。【００１８】
[ＡＣＪＴ００]方式や[ＣＧ０４]方式の安全性が強ＲＳＡ問題に基づくのに対し、実施形態方式は、安全性がＤＤＨ（decisional Diffie-Hellman）問題に基づいている。これに伴い、実施形態方式は、楕円曲線上でも効率よく実装でき、署名長及び鍵長を大幅に短縮でき、高速化が可能となる。実施形態方式はＤＤＨ問題のみに基づく効率的なグループ署名として最初の方式である。さらに、実施形態方式は、単純な演算の組み合わせで実装可能であるため、広範囲のプラットフォーム上での応用が期待できる。【００１９】
＜グループ署名＞
以下では、実施形態方式の前提となるグループ署名の機能と安全性について定義する。【００２０】
［グループ署名の機能］
効率のよい既存方式のほとんどは、メンバ秘密鍵に対するグループ管理者の署名をメンバ証明書として利用する。実施形態方式では、グループ管理者の署名を利用しないため、従来方式のメンバ証明書と区別するために署名者特定情報（tracing information）という用語を用いる。グループ署名においては、暗号化された署名者特定情報と、署名者特定情報が正しく暗号化されていることを示す非対話的知識証明と、メンバ秘密鍵及び署名者特定情報を持っていることを示す非対話的知識証明とが含まれることはメンバ証明書と同様である。【００２１】
グループ署名方式ＧＳは以下の４つの多項式時間アルゴリズムＧＫｇ，ＧＳｉｇ，ＧＶｆ，Ｏｐｅｎから成る。【００２２】
［鍵生成アルゴリズムＧＫｇ］
鍵生成アルゴリズムＧＫｇは、公開パラメータとグループのメンバ数ｎを入力とし、グループ公開鍵ｇｐｋ、グループ秘密鍵ｇｍｓｋ、メンバ秘密鍵の集合ｇｓｋ＝（ｇｓｋ［１］，…，ｇｓｋ［ｎ］）、それに対応する署名者特定情報Ｔ＝（Ｔ１，…，Ｔｎ）を生成して出力するための確率的多項式時間アルゴリズムである。【００２３】
［署名生成アルゴリズムＧＳｉｇ］
署名生成アルゴリズムＧＳｉｇは、グループ公開鍵ｇｐｋ、メンバ秘密鍵ｇｓｋ［ｉ］、署名者特定情報Ｔｉ、メッセージｍｓｇに対し、グループ署名σを生成する確率的多項式時間アルゴリズムである。【００２４】
［署名検証アルゴリズムＧＶｆ］
署名検証アルゴリズムＧＶｆは、グループ公開鍵ｇｐｋ、メッセージｍｓｇ、グループ署名σを入力とし、署名が正しければ有効（valid）を、正しくなければ無効（invalid）を出力する確定的多項式時間アルゴリズムである。【００２５】
［署名者特定アルゴリズムＯｐｅｎ］
署名者特定アルゴリズムＯｐｅｎは、グループ公開鍵ｇｐｋ、グループ秘密鍵ｇｍｓｋ、メッセージｍｓｇ、グループ署名σを入力とし、署名が正しければその署名を生成したユーザのＩＤ＝ｉを、正しくなければ無効（invalid）を出力する確定的多項式時間アルゴリズムである。【００２６】
［グループ署名の安全性］
グループ署名の安全性について当初は数多くの要件が定義されていた。その後、ベラー（Bellare）らが、静的グループ（static group）のグループ署名の安全性の要件をまとめている（M. Bellare, D. Micciancio, and B. Warinschi, “Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions,” In Proc. of EUROCRYPT 2003, LNCS 2656, pp.614-629, 2003.参照）。なお、静的グループとは、メンバの追加・削除機能を持たず一度グループが生成されるとメンバの変更がないグループをいう。ここで、ベラーの要件は非常に厳しいものであり、グループメンバ全員の結託に対する安全性が考慮されている。このため、一般的には、ベラーの要件を弱めて安全性が定義されている。ここでは、ベラーの要件に基づき、グループ管理者やメンバの結託がない場合の安全性を再定義する。結託以外の定義はベラーの定義と同様である。【００２７】
以下の正当性（correctness）、匿名性（anonymity）、追跡可能性（traceability）の３つの性質を持つとき、グループ署名方式ＧＳは安全であるという。【００２８】
［１．正当性（correctness）］
ＧＶｆ（ｇｐｋ，ｍｓｇ，ＧＳｉｇ（ｇｓｋ［ｉ］，ｍｓｇ））＝ valid かつ  
Ｏｐｅｎ（ｇｍｓｋ，ｍｓｇ，ＧＳｉｇ（ｇｓｋ［ｉ］，ｍｓｇ））＝ｉ  
すなわち、正しく生成された署名は、署名検証アルゴリズムＧＶｆにより検証に成功し、署名者特定アルゴリズムＯｐｅｎにより署名者を特定できる。【００２９】
［２．匿名性（anonymity）］
以下のゲームを考える。【００３０】
（１）セットアップ：鍵生成アルゴリズムＧＫｇ（ｎ）を実行して、グループ公開鍵ｇｐｋ、グループ秘密鍵ｇｍｓｋ、メンバ秘密鍵の集合ｇｓｋ、署名者特定情報Ｔを生成し、敵（adversary）Ａにグループ公開鍵ｇｐｋを与える。【００３１】
（２）質問（queries）：敵Ａは次の２種類の質問（ａ）,（ｂ）を行える。ただし、買収質問（corruption query）は１回のみに限られる。【００３２】
（ａ）署名（signing）：ユーザｉとメッセージｍｓｇを指定し、署名質問(signing query)を行い、グループ署名σ＝ＧＳｉｇ（ｇｐｋ，ｇｓｋ［ｉ］，ｍｓｇ）を得る。【００３３】
（ｂ）買収（corruption）：ユーザｕ（１≦ｕ≦ｎ）を指定し、買収質問を行い、メンバ秘密鍵ｇｓｋ［ｕ］を得る。【００３４】
（３）チャレンジ（challenge）：敵ＡはメッセージｍｓｇとユーザＩＤ ｉ０，ｉ１を出力する。このときｕ＝ｉ０またはｕ＝ｉ１であってはならない。挑戦者（challenger）は、ユーザＩＤ ｂ←｛０，１｝をランダムに選び、グループ署名σ＊←ＧＳｉｇ（ｇｐｋ，ｇｓｋ［ｉｂ］，ｍｓｇ）を計算して敵Ａに返す。【００３５】
（４）限定された質問（restricted queries）:次の質問（ａ），（ｂ）
（ａ）署名（signing）:上記と同様。  
（ｂ）買収（corruption）：上記と同様。ただし既に１回行われていた場合は質問できない。また、このときｕ＝ｉ０またはｕ＝ｉ１であってはならない。【００３６】
（５）出力（output）：敵Ａは、ユーザＩＤ ｂ’を出力する。  
ｂ’＝ｂのとき、“敵Ａは攻撃に成功した”という。敵Ａの成功確率が無視できるとき、グループ署名方式は匿名性（anonymity）を持つという。【００３７】
［３．追跡可能性（traceability）］
以下のゲームを考える。【００３８】
（１）セットアップ（setup）： 鍵生成アルゴリズムＧＫｇ（ｎ）を実行してグループ公開鍵ｇｐｋ、グループ秘密鍵ｇｍｓｋ、メンバ秘密鍵ｇｓｋ、署名者特定情報Ｔを生成し、敵Ａにグループ公開鍵ｇｐｋを与える。【００３９】
（２）質問（queries）：敵Ａは次の２種類の質問（ａ）,（ｂ）を行える。ただし、買収質問（corruption query）は１回のみに限られる。  
（ａ）署名（signing）：ユーザｉとメッセージｍｓｇを指定し、署名質問(signing query)を行い、グループ署名σ＝ＧＳｉｇ（ｇｐｋ，ｇｓｋ［ｉ］，ｍｓｇ）を得る。  
（ｂ）買収（corruption）：ユーザｕ（１≦ｕ≦ｎ）を指定し、買収質問を行い、メンバ秘密鍵ｇｓｋ［ｕ］を得る。【００４０】
（３）応答（response）：敵Ａはメッセージｍｓｇ＊とグループ署名σ＊を出力する。署名者特定アルゴリズムＯｐｅｎの結果がＯｐｅｎ（ｇｍｓｋ，ｍｓｇ＊，σ＊）＝ｉ≠ｕであり、ｉ、ｍｓｇ＊が署名質問(signing query)で指定されていないとき、“敵Ａは攻撃に成功した”という。敵Ａの成功確率が無視できるとき、グループ署名方式は追跡可能性（traceability）を持つという。【００４１】
＜準備＞
以下では、実施形態方式を理解するうえで重要なＤＤＨ（decisional Diffie-Hellman）問題、リプレゼンテーション（representation）、クラマー−シャウプ（Cramer-Shoup）暗号について説明する。【００４２】
［ＤＤＨ問題］
素数位数ｑの乗法巡回群をＧとする。ランダムな４つ組（quadruples）（ｇ１，ｇ２，ｕ１，ｕ２）∈Ｇ４の分布をＲとする。ｇ１，ｇ２∈Ｇとｒ∈Ｚｑとをランダムに選び、ｕ１＝ｇｒ、ｕ２＝ｇｒとした４つ組（ｇ１，ｇ２，ｕ１，ｕ２）∈Ｇ４の分布をＤとする。このとき、任意に与えられた４つ組（ｇ１，ｇ２，ｕ１，ｕ２）が分布Ｒ，Ｄのいずれに属するかを見分ける問題をＤＤＨ問題と呼ぶ。実施形態方式の安全性はＤＤＨ問題の困難性に帰着される。【００４３】
なお、離散対数問題（discrete logarithm problem）を解くことができれば、ＤＨ問題（Diffie-Hellman problem）を解くことができ、ＤＨ問題を解くことができればＤＤＨ問題を解くことができる。ＤＨ問題は、与えられたｇ，ｇｘ，ｇｙから、ｇｘｙを計算する問題である。離散対数問題は、与えられたｇ，ｇｘから、ｘを計算する問題である。これらＤＤＨ問題、ＤＨ問題及び離散対数問題は、いずれも解くことが困難であると信じられている。【００４４】
［リプレゼンテーション（representation）］
乗法巡回群Ｇ上の演算において、ｈ＝ｇ１＾｛ｅ１｝ｇ２＾｛ｅ２｝…ｇｋ＾｛ｅｋ｝を満たす（ｅ１，ｅ２，…，ｅｋ）を、ｇ１，ｇ２，…，ｇｋを底としたｈのリプレゼンテーションと呼ぶ。なお、“＾”はベキ乗を表す記号である。【００４５】
リプレゼンテーションは、暗号理論の分野でも古くは緩和離散対数（relaxed discrete log（ＲＤＬ））として用いられ（D. Chaum, J.H. Evertse, and J. van de Graaf, “An improved protocol for demonstrating possession of discrete logarithms and some generalizations,” In Proc. of EUROCRYPT ’87, LNCS 304, pp.127-141, 1987. 参照）、その後もしばしば用いられている。１９９７年のカメニッシュの方式では、シュノア（Schnorr）署名（C.P. Schnorr, “Efficient Signature Generation by Smart Cards,” Journal of Cryptology, Vol.4, pp.161-174, 1991. 参照）を応用したリプレゼンテーションの非対話的知識証明が用いられている。実施形態方式ではメンバ秘密鍵をリプレゼンテーションとし、グループ署名にはリプレゼンテーションについての非対話的知識証明を含んでいる。【００４６】
［クラマー−シャウプ（Cramer-Shoup）暗号］
実施形態方式では、署名者特定情報の暗号化にクラマー−シャウプ暗号（R. Cramer and V. Shoup, “A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack,” In Proc. of CRYPTO ’98, LNCS 1462, pp.13-25, 1998. 参照）を利用する。但し、実施形態方式はクラマー−シャウプ暗号に限定されない。  
以下にクラマー−シャウプ暗号を説明する。【００４７】
［公開鍵（public key）・秘密鍵（private key）ペア生成］
公開パラメータとして素数位数ｑの乗法巡回群Ｇとその生成元ｇ１と汎用一方向性ハッシュ（universal one-way hash）関数を入力とし、以下の処理を行う。【００４８】
（１）ｇ１，ｇ２∈Ｇをランダムに選択する。  
（２）ｘ１，ｘ２，ｙ１，ｙ２，ｚ∈Ｚｑをランダムに選択する。  
（３）ｃ＝ｇ１＾｛ｘ１｝ｇ２＾｛ｘ２｝、ｄ＝ｇ１＾｛ｙ１｝ｇ２＾｛ｙ２｝、ｈ＝ｇ１ｚを計算する。  
（４）ハッシュ関数Ｈを汎用一方向性ハッシュ関数の集合から選択する。  
（５）公開鍵ｐｋ＝（ｇ１，ｇ２，ｃ，ｄ，ｈ，Ｈ）、秘密鍵ｓｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｚ）を出力する。【００４９】
［暗号化］
公開鍵ｐｋ＝（ｇ１，ｇ２，ｃ，ｄ，ｈ，Ｈ）、メッセージｍ∈Ｇを入力とし、以下の処理を行う。【００５０】
（１）ｒ∈Ｚｑをランダムに選択する。  
（２）ｕ１＝ｇ１ｒ、ｕ２＝ｇ２ｒ、ｅ＝ｈｒｍを計算する。  
（３）α＝Ｈ（ｕ１，ｕ２，ｅ）を計算する。  
（４）ｖ＝ｃｒｄｒαを計算する。  
（５）暗号文（ｕ１，ｕ２，ｅ，ｖ）を出力する。【００５１】
［復号］
暗号文（ｕ１，ｕ２，ｅ，ｖ）を入力とし、以下の処理を行う。【００５２】
（１）α＝Ｈ（ｕ１，ｕ２，ｅ）を計算する。  
（２）ｕ１＾｛ｘ１＋ｙ１α｝ｕ２＾｛ｘ２＋ｙ２α｝＝ｖが成り立つか否かを検証し、否の場合には無効な暗号文として拒絶して処理を終了する。  
（３）ｍ＝ｅ／ｕ１ｚを計算し、平文として出力する。  
以上がクラマー−シャウプ暗号の処理である。【００５３】
＜実施形態方式の概要＞
続いて、実施形態方式の概要を説明する。【００５４】
本実施形態は、離散対数ベースの方式により、グループ署名方式の高速化を図るものである。理由は、ＲＳＡベースの方式ではベキ指数が長いので、位数を知らない群における非対話的知識証明の効率が低いため、全体的な効率も低いからである。なお、[ＡＣＪＴ００]方式や[ＣＧ０４]方式もＲＳＡベースの方式であるため、実施形態方式に比べ、効率が低い。【００５５】
補足すると、[ＡＣＪＴ００]方式がＲＳＡベースの方式であるのに対し、[ＣＧ０４]方式は一部を離散対数ベースとして大幅に効率を改善したが、ＲＳＡベースの部分も残っている。これに対し、実施形態方式では全て離散対数ベースの方式として高速化を図っている。【００５６】
実施形態方式は、さらにリプレゼンテーションをメンバ秘密鍵としている。離散対数が秘密鍵の場合、１つの公開鍵に対して１つの秘密鍵しか持てない。これに対し、リプレゼンテーションが秘密鍵の場合、１つの公開鍵に対して複数の秘密鍵を作れるため、多数のメンバをもつグループに適している。カイアス（Kiayias）らの方式（A. Kiayias and M. Yung, “Extracting Group Signatures from Traitor Tracing Schemes,” In Proc. of EUROCRYPT 2003, LNCS 2656, pp.630-648, 2003. 参照）でもリプレゼンテーションを用いるが、署名者特定情報としてリプレゼンテーション自体を用いるため、効率が低い。【００５７】
これに対し、実施形態方式では、リプレゼンテーション自体ではなく、リプレゼンテーションから一意に計算される値を署名者特定情報として用いるので、効率が高い。【００５８】
（実施形態方式）
図１は本発明の一実施形態に係るグループ署名システムの構成を示す模式図である。このグループ署名システムは、互いに通信可能な１台のグループ管理者装置１０、ｎ台の署名者装置２０１，…，２０ｉ，…，２０ｊ，…，２０ｎ及び１台の検証者装置３０を備えている。各装置１０，２０１，…，２０ｎ，３０は、装置毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体Ｍから対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。また、各署名者装置２０１，…，２０ｎは、互いに同一のハードウェア構成のため、以下の説明ではｉ番目の署名者装置２０ｉを代表させて述べる。また、本実施形態のグループ署名方式は、後述する図８乃至図１５に一例を示すように、クラマー−シャウプ暗号を暗号化方式に用い、シュノア（Schnorr）署名を応用した方式を零知識証明方式に用いているが、これらの暗号化方式及び零知識証明方式には限定されない。すなわち、本実施形態のグループ署名方式は、図８乃至図１５に示した方式に限らず、他の暗号化方式及び零知識証明方式を用いても実現可能となっている。【００５９】
ここで、グループ署名管理者装置１０は、図２に示すように、管理者用記憶部１１、入力部１２、通信部１３、グループ鍵生成部１４、メンバ秘密鍵生成部１５、署名検証部１６、署名者特定部１７及び出力部１８を備えている。【００６０】
管理者用記憶部１１は、各部１２〜１７からアクセス可能な記憶装置であり、図３に示すように、公開パラメータ、グループ公開鍵ｇｐｋ、グループ秘密鍵ｇｍｓｋ、メンバ情報、ユーザ管理情報、計算テーブル、メッセージｍｓｇ及びグループ署名σが記憶される。このメッセージｍｓｇやグループ署名σは一時的に記憶されるものであっても構わない。【００６１】
公開パラメータは、グループ署名方式に用いる素数位数ｑと、ｑの乗法巡回群Ｇの生成元ｇ１とを少なくとも含んでおり、ここでは更にハッシュ関数Ｈを含んでいる。【００６２】
グループ秘密鍵ｇｍｓｋは、公開パラメータに基づいて選択された値ａ，ｂ∈Ｚｑを少なくとも含んでおり、ここでは更に値ｘ１，ｘ２，ｙ１，ｙ２，ｚ∈Ｚｑを含んでいる。【００６３】
グループ公開鍵ｇｐｋは、第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂを満たす値ｇ２，ｆ及び生成元ｇ１を少なくとも含んでおり、ここでは更に値ｃ，ｄ，ｈ及びハッシュ関数Ｈを含んでいる。なお、ｃ＝ｇ１＾｛ｘ１｝ｇ２＾｛ｘ２｝、ｄ＝ｇ１＾｛ｙ１｝ｇ２＾｛ｙ２｝、ｈ＝ｇ１ｚである。【００６４】
メンバ情報は、ユーザ識別情報ＩＤ（ｉ）毎に、メンバ秘密鍵ｇｓｋ［ｉ］及び署名者特定情報Ｔｉが互いに関連付けられてなる情報である（１≦ｉ≦ｎ）。【００６５】
ユーザ管理情報は、ユーザ識別情報ＩＤ（ｉ）毎に、ユーザ情報が関連付けられてなる情報である（１≦ｉ≦ｎ）。ユーザ情報は、例えばユーザの名前及び連絡先情報（電話番号、電子メールアドレスなど）を含んでおり、グループ署名の目的が電子商取引の場合には更に決済情報を含んでいる。【００６６】
計算テーブルは、各部１４〜１６が指数同時乗算（simultaneous multiple exponentiation）法を用いる場合に参照される情報である。指数同時乗算法は、ｇ１＾｛ｅ１｝ｇ２＾｛ｅ２｝…ｇｋ＾｛ｅｋ｝の形の計算を高速に実行する方法であり、最大２ｋ回の掛け算を予め実行し、最大２ｋの大きさの計算テーブルを作成する必要がある。このため、底ｇ１，…，ｇｋの個数ｋに応じて計算テーブルに必要なメモリ量が大きくなる。但し、底が固定であれば、毎回計算テーブルを作る必要がなく、事前計算によってベキ乗１回分程度の計算量で計算できる。すなわち、例えばｇ１＾｛ｅ１｝ｇ２＾｛ｅ２｝というベキ乗２回分の計算であっても、計算テーブルの参照により、ベキ乗１回分の計算量で実行できる。したがって、グループ管理者及び検証者装置として‘１’，‘ｇ１’，‘ｇ２’，‘ｇ１×ｇ２’，‘ｆ’，‘ｆ×ｇ１’，‘ｆ×ｇ２’，‘ｆ×ｇ１×ｇ２’と‘１’，‘ｈ’，‘ｇ１’，‘ｈ×ｇ１’を、署名者装置として‘１’，‘ｈ’，‘ｇ１’，‘ｈ×ｇ１’と‘１’，‘ｃ’，‘ｄ’，‘ｃ×ｄ’をそれぞれ計算テーブルとして持てば、後述するステップＳＴ４，ＳＴ５，ＳＴ３４，ＳＴ３６，ＳＴ４２，ＳＴ４４，ＳＴ５２，ＳＴ５４，ＳＴ６２，ＳＴ６４でのベキ乗２回または３回分の計算がベキ乗１回分の計算量で実行可能となる。【００６７】
メッセージｍｓｇは、署名者装置２０ｉにより生成された任意の情報である。【００６８】
グループ署名σは、後述する暗号文（ｕ１，ｕ２，ｅ，ｖ）と、零知識証明（Ａ，Ｂ，Ｃ，ｓ１，ｓ２，ｓｒ）とからなり、署名者装置２０ｉにより生成された情報である。ここでメッセージｍｓｇやグループ署名σは管理者用記憶部１１に一時的に記憶されるものであっても構わない。【００６９】
入力部１２は、グループ管理者装置１０内部と外部との間の入力インターフェイスであり、キーボード及びマウス等の入力デバイスが用いられる。【００７０】
通信部１３は、グループ管理者装置１０内部と外部との間の通信インターフェイスである。通信部１３は、例えば、グループ署名方式におけるグループ署名を生成するための公開パラメータ、グループ公開鍵、メンバ秘密鍵及び署名者特定情報Ｔｉを暗号化通信などの安全な手法により、署名者装置２０１〜２０ｎに送信する機能をもっている。また、通信部１３は、例えば、グループ署名方式におけるグループ署名を検証するための公開パラメータ及びグループ公開鍵を検証者装置３０に送信する機能をもっている。さらに、通信部１３は、メッセージｍｓｇやグループ署名σを検証者装置３０から受信する機能も持っている。【００７１】
グループ鍵生成部１４は、管理者用記憶部１１内の公開パラメータに基づいて、値ａ，ｂ∈Ｚｑを含むグループ秘密鍵と、第１関係式ｇ２＝ｇ１ａ及び第２関係式ｆ＝ｇ１ｂを満たす値ｇ２，ｆ及び生成元ｇ１を含むグループ公開鍵とを生成するものである。ここでは、グループ鍵生成部１４は、図８に示す処理を実行する機能をもっている。なお、グループ鍵生成部１４は、計算テーブルを参照して指数同時乗算法により、ベキ乗演算を実行してもよく、このことはメンバ秘密鍵生成部１５及び署名検証部１６でも同様である。【００７２】
メンバ秘密鍵生成部１５は、グループ秘密鍵、グループ公開鍵及び第３関係式ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑに基づいて、第４関係式ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を満たすリプレゼンテーションｋｉ１，ｋｉ２からなるメンバ秘密鍵を算出すると共に、メンバ秘密鍵及び生成元ｇ１に基づいて、署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝を算出するものである。ここでは、メンバ秘密鍵生成部１５は、図９及び図１０に示す処理を実行する機能をもっている。【００７３】
署名検証部１６は、管理者用記憶部１１内のグループ署名、メッセージ、公開パラメータ及びグループ公開鍵に基づいて、当該グループ署名内の零知識証明の正当性を検証すると共に、管理者用記憶部１１内のグループ署名、グループ秘密鍵及びグループ公開鍵に基づいて、当該グループ署名内の暗号文データの正当性を検証するものである。ここでは、署名検証部１６は、後述する図１４に示す処理を実行する機能をもっている。【００７４】
署名者特定部１７は、管理者用記憶部１１内のグループ署名及びグループ秘密鍵に基づいて、署名者特定情報Ｔを算出するものである。ここでは、署名者特定部１７は、後述する図１５に示す処理を実行する機能をもっている。【００７５】
出力部１８は、グループ管理者装置１０内部と外部との間の出力インターフェイスであり、ディスプレイ装置及びプリンタ等の出力デバイスが用いられる。【００７６】
署名者装置２０ｉは、図４に示すように、署名者用記憶部２１、入力部２２、通信部２３、メッセージ作成部２４、グループ署名生成部２５及び出力部２６を備えている。【００７７】
署名者用記憶部２１は、各部２２〜２５からアクセス可能な記憶装置であり、図５に示すように、公開パラメータ、グループ公開鍵ｇｐｋ、計算テーブル、メンバ秘密鍵、署名者特定情報、メッセージ及びグループ署名が記憶される。【００７８】
入力部２２は、署名者装置２０ｉ内部と外部との間の入力インターフェイスであり、キーボード及びマウス等の入力デバイスが用いられる。【００７９】
通信部２３は、署名者装置２０ｉ内部と外部との間の通信インターフェイスである。通信部２３は、例えば、グループ署名方式におけるグループ署名を生成するための公開パラメータ、グループ公開鍵、メンバ秘密鍵及び署名者特定情報Ｔｉを暗号化通信などの安全な手法により、グループ管理者装置１０から受信する機能をもっている。また、通信部２３は、例えば、署名者の入力部２２の操作により、署名者用記憶部２１内の暗号文データ及び零知識証明からなるグループ署名と、メッセージとを検証者装置３０に送信する機能をもっている。【００８０】
メッセージ作成部２４は、署名者の入力部２２の操作により、メッセージｍｓｇを作成して署名者用記憶部２１に書き込む機能をもっている。【００８１】
グループ署名生成部２５は、署名者用記憶部２１内の公開パラメータ及びグループ公開鍵に基づいて署名者特定情報Ｔｉを暗号化し、当該署名者特定情報Ｔｉの暗号文データを生成して署名者用記憶部２１に書き込む機能をもっている。また、グループ署名生成部２５は、署名者用記憶部２１内の公開パラメータ、グループ公開鍵、メンバ秘密鍵及びメッセージと、署名者特定情報Ｔｉの暗号文データとに基づいて、当該メンバ秘密鍵及び当該署名者特定情報Ｔｉを知っていることを示す零知識証明を生成し、零知識証明を暗号文データに関連付けて署名者用記憶部２１に書き込む機能をもっている。なお、暗号文データと零知識証明とはグループ署名を構成する。また、ここでは、グループ署名生成部２５は、図１１及び図１２に示す処理を実行する機能をもっている。また、図１２に示す零知識証明においては、暗号化された署名者特定情報Ｔｉを知っていることと、リプレゼンテーションの一つを知っていることと、署名者特定情報Ｔｉが正しく暗号化されていることの、メッセージｍｓｇに基づく零知識証明となっている。また、グループ署名生成部２５は、計算テーブルを参照して指数同時乗算法により、ベキ乗演算を実行してもよい。【００８２】
出力部２６は、署名者装置２０ｉ内部と外部との間の出力インターフェイスであり、ディスプレイ装置及びプリンタ等の出力デバイスが用いられる。【００８３】
検証者装置３０は、図６に示すように、検証者用記憶部３１、入力部３２、通信部３３、署名検証部３４及び出力部３５を備えている。【００８４】
検証者用記憶部３１は、各部３２〜３４からアクセス可能な記憶装置であり、図７に示すように、公開パラメータ、グループ公開鍵ｇｐｋ、計算テーブル、メッセージ及びグループ署名が記憶される。【００８５】
入力部３２は、検証者装置３０内部と外部との間の入力インターフェイスであり、キーボード及びマウス等の入力デバイスが用いられる。【００８６】
通信部３３は、検証者装置３０内部と外部との間の通信インターフェイスである。通信部３３は、例えば、グループ署名方式におけるグループ署名を生成するための公開パラメータ及びグループ公開鍵を暗号化通信などの安全な手法により、グループ管理者装置１０から受信する機能をもっている。また、通信部３３は、例えば、暗号文データ及び零知識証明からなるグループ署名と、メッセージとを署名者装置２０ｉから受信する機能と、受信したグループ署名とメッセージとを検証者用記憶部３１に書き込む機能と、署名検証部３４による検証結果を署名者装置２０ｉに送信する機能と、検証の結果ＯＫであり且つ署名者特定要求が入力された場合に署名者特定のためにメッセージとグループ署名をグループ管理者装置１０に送信する機能とをもっている。なお、通信部３３は、署名検証部３４による検証結果を必ずしも署名者装置２０ｉに送信する必要はない。検証結果を送信しない場合としては、例えば、検証者装置３０がオンラインでリアルタイムに検証しない場合などである。【００８７】
署名検証部３４は、検証者用記憶部３１内のグループ署名、メッセージ、公開パラメータ及びグループ公開鍵に基づいて、当該グループ署名の正当性を検証し、検証結果を通信部３３及び出力部３５に送出するものである。ここでは、署名検証部３４は、図１３に示す処理を実行する機能をもっている。また、署名検証部３４は、計算テーブルを参照して指数同時乗算法により、ベキ乗演算を実行してもよい。また、署名検証部３４は、検証結果を必ずしも通信部３３及び／又は出力部３５に送出する必要はない。【００８８】
出力部３５は、検証者装置３０内部と外部との間の出力インターフェイスであり、ディスプレイ装置及びプリンタ等の出力デバイスが用いられる。出力部３５は、例えば署名検証部３４から受けた検証結果を表示する。【００８９】
次に、以上のように構成されたグループ署名システムの動作を図８乃至図１５のフローチャートを用いて説明する。【００９０】
（グループ公開鍵・グループ秘密鍵ペア生成：図８）
グループ管理者装置１０では、グループ管理者の入力部１２の操作により、公開パラメータ（ｑ，Ｇ，ｇ１，Ｈ）が管理者用記憶部１１に保存された後、グループ鍵生成部１４が起動されたとする。【００９１】
グループ鍵生成部１４は、管理者用記憶部１１内の素数位数ｑを参照し、７つ組（ａ，ｂ，ｘ１，ｘ２，ｙ１，ｙ２，ｚ）∈Ｚｑ７をランダムに選択する（ＳＴ１）。なお、Ｚｑは、０以上ｑ未満の整数の集合｛０，…，ｑ−１｝である。また、ａ，ｂは、複数のリプレゼンテーションを効率よく計算するために必要な値である。【００９２】
続いて、グループ鍵生成部１４は、管理者用記憶部１１内の生成元ｇ１とステップＳＴ１で得られた７つ組とに基づいて、ｇ２＝ｇ１ａ、ｆ＝ｇ１ｂ、ｃ＝ｇ１＾｛ｘ１｝ｇ２＾｛ｘ２｝、ｄ＝ｇ１＾｛ｙ１｝ｇ２＾｛ｙ２｝、ｈ＝ｇ１ｚを計算する（ＳＴ２〜ＳＴ６）。ｇ１，ｇ２はｆのリプレゼンテーションの底である。【００９３】
また、グループ鍵生成部１４は、管理者用記憶部１１内の公開パラメータから汎用一方向性ハッシュ関数Ｈを読み出す。【００９４】
しかる後、グループ鍵生成部１４は、グループ秘密鍵ｇｍｓｋ＝（ａ，ｂ，ｘ１，ｘ２，ｙ１，ｙ２，ｚ）と、グループ公開鍵ｇｐｋ＝（ｇ１，ｇ２，ｆ，ｃ，ｄ，ｈ，Ｈ）とを管理者用記憶部１１に保存する（ＳＴ７）。【００９５】
これにより、グループ鍵生成部１４は、グループ公開鍵ｇｐｋ及びグループ秘密鍵ｇｍｓｋの生成完了メッセージを出力部１８に送出し、処理を終了する。出力部１８は、この生成完了メッセージを表示出力する。【００９６】
（メンバ秘密鍵生成：図９）
グループ管理者装置１０では、予めグループ管理者の入力部１２の操作により、メンバ数ｎに対応するｎ人分のユーザ識別情報ＩＤ（１），…，ＩＤ（ｉ），…，ＩＤ（ｊ），…，ＩＤ（ｎ）が管理者用記憶部１１に保存されたとする。なお、ユーザ識別情報ＩＤ（１），…，ＩＤ（ｎ）は、メンバ数ｎが入力されたメンバ秘密鍵生成部１５により生成され、メンバ秘密鍵生成部１５から管理者用記憶部１１に書き込まれてもよい。【００９７】
メンバ秘密鍵生成部１５は、管理者用記憶部１１内の素数位数ｑを参照し、メンバ秘密鍵の一部ｋｉ２∈Ｚｑをランダムに選択する（ＳＴ１１）。【００９８】
このとき、メンバ秘密鍵生成部１５は、管理者用記憶部１１を参照し、ｋｉ２＝ｋｊ２なるメンバ秘密鍵ｇｓｋｊ＝（ｋｊ１，ｋｊ２）を持つメンバが存在している場合にはｋｉ２を選択しなおす。すなわち、ｋｉ２はユーザ毎に全て異なっている必要がある。【００９９】
続いて、メンバ秘密鍵生成部１５は、管理者用記憶部１１内の素数位数ｑ及びグループ秘密鍵ｇｍｓｋに基づいて、メンバ秘密鍵の他の一部ｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑを計算する（ＳＴ１２）。【０１００】
しかる後、メンバ秘密鍵生成部１５は、得られたｋｉ１，ｋｉ２からなるメンバ秘密鍵（ｋｉ１，ｋｉ２＝ｇｓｋ［ｉ］）をユーザ識別情報ＩＤ（ｉ）に関連付けて管理者用記憶部１１に保存する（ＳＴ１３）。【０１０１】
ここで、メンバ秘密鍵（ｋｉ１，ｋｉ２）は、（ｇ１，ｇ２）を底としたｆのリプレゼンテーションである。すなわち、前述したｆ＝ｇ１ｂ、ｇ２＝ｇ１ａ及びｋｉ１＝ｂ−ａｋｉ２  ｍｏｄ  ｑの式に基づいて、ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝と表される。また、グループ秘密鍵ｇｍｓｋに含まれるａ，ｂを用いることにより、複数のメンバ秘密鍵を効率よく計算できる。このリプレゼンテーションｋｉ１，ｋｉ２を計算できるのは、グループ管理者のみである。リプレゼンテーションｋｉ１，ｋｉ２を知っていることは、グループ管理者に認められたグループメンバである旨を意味する。【０１０２】
メンバ秘密鍵生成部１５は、以上のステップＳＴ１１〜ＳＴ１３の処理をメンバ数ｎと同じ回数ｎだけ繰り返し、ｎ人分のメンバ秘密鍵ｇｓｋ［１］〜ｇｓｋ［ｎ］をユーザ識別情報ＩＤ（１）〜ＩＤ（ｎ）に個別に関連付けて管理者用記憶部１１に保存した後、処理を終了する。【０１０３】
（署名者特定情報算出処理：図１０）
次に、メンバ秘密鍵生成部１５は、管理者用記憶部１１内の生成元ｇ１及びメンバ秘密鍵ｇｓｋ［ｉ］（＝ｋｉ１，ｋｉ２）に基づいて、署名者特定情報Ｔｉ＝ｇ１＾｛ｋｉ１｝を計算する（ＳＴ２１）。すなわち、署名者特定情報Ｔｉは、リプレゼンテーション自体ではなく、リプレゼンテーションの一部をベキ指数とした値である。【０１０４】
しかる後、メンバ秘密鍵生成部１５は、得られた署名者特定情報Ｔｉをユーザ識別情報ＩＤ（ｉ）に関連付けて管理者用記憶部１１に保存する（ＳＴ２２）。【０１０５】
メンバ秘密鍵生成部１５は、以上のステップＳＴ２１〜ＳＴ２２の処理をメンバ数ｎと同じ回数ｎだけ繰り返し、ｎ人分のメンバ秘密鍵ｇｓｋ［１］〜ｇｓｋ［ｎ］をユーザ識別情報ＩＤ（１）〜ＩＤ（ｎ）に個別に関連付けて管理者用記憶部１１に保存した後、処理を終了する。【０１０６】
（署名生成の準備）
ユーザｉは、オンライン又はオフラインにより、ユーザ情報をグループ管理者装置１０に登録する。これにより、ユーザｉは、公開パラメータ、グループ公開鍵ｇｐｋ＝（ｇ１，ｇ２，ｆ，ｃ，ｄ，ｈ，Ｈ）、メンバ秘密鍵ｇｓｋ［ｉ］（＝ｋｉ１，ｋｉ２）及び署名者特定情報Ｔｉを暗号化通信又は記憶媒体の郵送などの安全な手法によりグループ管理者から取得する。【０１０７】
しかる後、署名者装置２０ｉは、ユーザｉによる入力部２２の操作により、これら公開パラメータ、グループ公開鍵ｇｐｋ、メンバ秘密鍵ｇｓｋ［ｉ］及び署名者特定情報Ｔｉを署名者用記憶部２１に保存する。これにより、署名者装置２０ｉは、署名生成処理が可能となる。【０１０８】
また、署名者装置２０ｉは、ユーザｉによる入力部２２の操作により、メッセージ作成部２４がメッセージｍｓｇ∈｛０，１｝＊を出力部２６に表示させながら作成し、得られたメッセージｍｓｇを署名者用記憶部２１に保存する。なお、メッセージｍｓｇは、メッセージ作成部２４が作成したものを用いる場合に限らず、グループ管理者や署名検証者から取得したものを用いてもよい。例えば電子商取引の場合にはメッセージ作成部２４が作成したメッセージｍｓｇを用い、２０歳以上などの資格証明の場合にはグループ管理者から取得したメッセージｍｓｇを用い、認証に利用する場合には署名検証者から取得したメッセージｍｓｇを用いるようにしてもよい。【０１０９】
（暗号化処理：図１１）
署名者装置２０ｉでは、ユーザｉの入力部２２の操作により、グループ署名生成部２５が起動されたとする。【０１１０】
グループ署名生成部２５は、署名者用記憶部２１内の素数位数ｑを参照し、秘密の乱数ｒ∈Ｚｑをランダムに選択する（ＳＴ３１）。【０１１１】
続いて、グループ署名生成部２５は、署名者用記憶部２１内のグループ公開鍵ｇｐｋ＝（ｇ１，ｇ２，ｆ，ｃ，ｄ，ｈ，Ｈ）及び署名者特定情報Ｔｉと、ステップＳＴ３１で得られた乱数ｒとに基づいて、ｕ１＝ｇ１ｒ，ｕ２＝ｇ２ｒ，ｅ＝ｈｒＴｉを計算する（ＳＴ３２〜ＳＴ３４）。なお、署名者特定情報Ｔｉ（＝ｇ１＾｛ｋｉ１｝）は、毎回、メンバ秘密鍵ｇｍｓｋ［ｉ］（＝ｋｉ１，ｋｉ２）から計算してもよい。この場合、署名者特定情報Ｔｉは署名者用記憶部２１から省略してもよい。【０１１２】
また、グループ署名生成部２５は、署名者用記憶部２１内のグループ公開鍵ｇｐｋとステップＳＴ３２〜ＳＴ３４で得られた値ｕ１，ｕ２，ｅとに基づいて、ハッシュ値α＝Ｈ（ｕ１，ｕ２，ｅ）を計算する（ＳＴ３５）。【０１１３】
さらに、グループ署名生成部２５は、このハッシュ値αと、ステップＳＴ３１で得られた乱数ｒと、グループ公開鍵ｇｐｋとに基づいて、値ｖ＝ｃｒｄｒαを計算する（ＳＴ３６）。【０１１４】
これにより、グループ署名生成部２５は、署名者特定情報Ｔｉに対して得られた暗号文（ｕ１，ｕ２，ｅ，ｖ）を署名者用記憶部２１に保存する（ＳＴ３７）。【０１１５】
（零知識証明（zero-knowledge proof）算出処理：図１２）
次に、グループ署名生成部２５は、署名者用記憶部２１内の素数位数ｑを参照し、メンバ秘密鍵（ｋｉ１，ｋｉ２）及びステップＳＴ３１で得られた乱数ｒを隠すための乱数ｒ１,ｒ２，ｒｒ∈Ｚｑをランダムに選択する（ＳＴ４１）。【０１１６】
続いて、グループ署名生成部２５は、署名者用記憶部２１内のグループ公開鍵ｇｐｋ＝（ｇ１，ｇ２，ｆ，ｃ，ｄ，ｈ，Ｈ）と、ステップＳＴ４１で得られた乱数ｒ１,ｒ２，ｒｒとに基づいて、零知識証明の一部となるパラメータＡ＝ｇ１＾｛ｒ１｝ｇ２＾｛ｒ２｝、Ｂ＝ｇ１＾｛ｒｒ｝、Ｃ＝ｈ＾｛ｒｒ｝ｇ１＾｛ｒ１｝を計算する（ＳＴ４２〜ＳＴ４４）。【０１１７】
また、グループ署名生成部２５は、署名者用記憶部２１内のグループ公開鍵ｇｐｋ＝（ｇ１，ｇ２，ｆ，ｃ，ｄ，ｈ，Ｈ）、暗号文（ｕ１，ｕ２，ｅ，ｖ）及びメッセージｍｓｇと、ステップＳＴ４２〜ＳＴ４４で得られた零知識証明の一部となるパラメータＡ，Ｂ，Ｃとに基づいて、ハッシュ値β＝Ｈ（ｇ１，ｇ２，ｈ，ｕ１，ｕ２，ｅ，ｖ，Ａ，Ｂ，Ｃ，ｍｓｇ）を計算する（ＳＴ４５）。【０１１８】
さらに、グループ署名生成部２５は、このハッシュ値βと、ステップＳＴ４１で得られた乱数ｒ１,ｒ２，ｒｒと、署名者用記憶部２１内のメンバ秘密鍵ｋｉ１，ｋｉ２及び素数位数ｑとに基づいて、他の零知識証明の一部となるパラメータｓ１＝ｒ１＋βｋｉ１  ｍｏｄ  ｑ、ｓ２＝ｒ２＋βｋｉ２  ｍｏｄ  ｑ、ｓｒ＝ｒｒ＋βｒ  ｍｏｄ  ｑを計算する（ＳＴ４６〜ＳＴ４８）。【０１１９】
これにより、グループ署名生成部２５は、最終的に得られた零知識証明（Ａ，Ｂ，Ｃ，ｓ１，ｓ２，ｓｒ）を暗号文（ｕ１，ｕ２，ｅ，ｖ）と関連付けて署名者用記憶部２１に保存し（ＳＴ４９）、処理を終了する。以後、これら暗号文（ｕ１，ｕ２，ｅ，ｖ）及び零知識証明（Ａ，Ｂ，Ｃ，ｓ１，ｓ２，ｓｒ）は、グループ署名σ＝（ｕ１，ｕ２，ｅ，ｖ，Ａ，Ｂ，Ｃ，ｓ１，ｓ２，ｓｒ）として用いられる。【０１２０】
このグループ署名σは、署名者特定情報Ｔｉの暗号文（ｕ１，ｕ２，ｅ，ｖ）と、ｇ１，ｇ２を底としたｆのリプレゼンテーションｋｉ１，ｋｉ２を知っている正しいユーザであることとそれに対応する署名者特定情報Ｔｉが正しく暗号化されていることを示す零知識証明（Ａ，Ｂ，Ｃ，ｓ１，ｓ２，ｓｒ）とから構成されている。【０１２１】
以後、署名者装置２０ｉは、署名者の入力部２２の操作により、署名者用記憶部２１内のグループ署名σ及びメッセージｍｓｇを出力部２６に表示させ、通信部２３から検証者装置３０に送信する。これにより、メンバ秘密鍵ｋｉ１，ｋｉ２を示すことなく、グループに属する正しいメンバであり、かつ、グループ管理者は署名者を特定できる旨を証明できる。【０１２２】
（署名検証処理：図１３）
検証者装置３０は、予め検証者の入力部３２の操作により、公開パラメータ（ｑ，Ｇ，ｇ１，Ｈ）及びグループ公開鍵ｇｐｋ＝（ｇ１，ｇ２，ｆ，ｃ，ｄ，ｈ，Ｈ）をグループ管理者装置１０から取得して検証者用記憶部３１に保存しているとする。これにより、検証者装置３０は、署名検証処理が可能となっている。【０１２３】
検証者装置３０では、署名者装置２０ｉから送信されたメッセージｍｓｇ、グループ署名σ＝（ｕ１，ｕ２，ｅ，ｖ，Ａ，Ｂ，Ｃ，ｓ１，ｓ２，ｓｒ）及び検証要求を通信部３３が受信して検証者用記憶部３１に保存すると共に、この検証要求を通信部３３が署名検証部３４に送出する。【０１２４】
署名検証部３４は、検証要求を受けると、検証者用記憶部３１内のグループ公開鍵ｇｐｋ、メッセージｍｓｇ及びグループ署名σに基づいて、ハッシュ値β＝Ｈ（ｇ１，ｇ２，ｈ，ｕ１，ｕ２，ｅ，ｖ，Ａ，Ｂ，Ｃ，ｍｓｇ）を計算する（ＳＴ５１）。なお、署名検証部３４は、グループ署名σの値の範囲を所定の基準範囲に基づいて確認してもよい。【０１２５】
続いて、署名検証部３４は、グループ公開鍵ｇｐｋ及びグループ署名σに基づいて、零知識証明の検証式Ａ＝ｆ＾｛−β｝ｇ１＾｛ｓ１｝ｇ２＾｛ｓ２｝、Ｂ＝ｕ１＾｛−β｝ｇ１＾｛ｓｒ｝、Ｃ＝ｅ＾｛−β｝ｈ＾｛ｓｒ｝ｇ１＾｛ｓ１｝が成り立つか否かを検証する（ＳＴ５２〜ＳＴ５４）。【０１２６】
ステップＳＴ５２〜ＳＴ５４の結果、全ての検証式Ａ，Ｂ，Ｃが成り立てば有効（valid）と判定して判定結果ＯＫを通信部３３及び出力部３５に出力し（ＳＴ５５）、１つでも検証式が成り立たなければ無効（invalid）と判定して判定結果ＮＧを通信部３３及び出力部３５に出力する（ＳＴ５６）。【０１２７】
通信部３３は判定結果ＯＫ／ＮＧを署名者装置２０ｉに送信して処理を終了する。但し、通信部３３は判定結果ＯＫ／ＮＧを必ずしも送信する必要はない。出力部３５は、判定結果ＯＫ／ＮＧを表示出力する。【０１２８】
（署名者検証処理及び署名者特定処理：図１４及び図１５）
例えば不正の発覚や、サービス利用料金の徴収のためといった何らかの事情により、署名者を特定する必要が生じた場合について述べる。【０１２９】
グループ管理者装置１０は、検証者装置３０から送信されたメッセージｍｓｇ、グループ署名σ及び署名者特定要求を通信部１３が受信して管理者用記憶部１１に保存すると共に、この署名者特定要求を通信部１３が署名検証部１６に送出する。【０１３０】
署名検証部１６は、署名者特定要求を受けると、図１４に示すように、管理者用記憶部１１内のグループ公開鍵ｇｐｋ、メッセージｍｓｇ及びグループ署名σに基づいて、ハッシュ値β＝Ｈ（ｇ１，ｇ２，ｈ，ｕ１，ｕ２，ｅ，ｖ，Ａ，Ｂ，Ｃ，ｍｓｇ）を計算する（ＳＴ６１）。なお、署名検証部１６は、グループ署名σの値の範囲を所定の基準範囲に基づいて確認してもよい。【０１３１】
続いて、署名検証部１６は、グループ公開鍵ｇｐｋ及びグループ署名σに基づいて、零知識証明の値Ａ＝ｆ＾｛−β｝ｇ１＾｛ｓ１｝ｇ２＾｛ｓ２｝、Ｂ＝ｕ１＾｛−β｝ｇ１＾｛ｓｒ｝、Ｃ＝ｅ＾｛−β｝ｈ＾｛ｓｒ｝ｇ１＾｛ｓ１｝が成り立つか否かを検証する（ＳＴ６２〜ＳＴ６４）。【０１３２】
ステップＳＴ６２〜ＳＴ６４の結果、１つでも検証式が成り立たなければ無効（invalid）と判定してＮＧを通信部１３に出力する（ＳＴ６５）。通信部１３は判定結果ＮＧを検証者装置３０に送信して処理を終了する。【０１３３】
一方、ステップＳＴ６２〜ＳＴ６４の結果、全てが成り立てば有効（valid）と判定し、署名検証部１６は、グループ公開鍵ｇｐｋ及びグループ署名σに基づいて、ハッシュ値α＝Ｈ（ｕ１，ｕ２，ｅ）を計算する（ＳＴ６６）。【０１３４】
しかる後、署名検証部１６は、管理者用記憶部１１内のグループ署名σ＝（ｕ１，ｕ２，ｅ，ｖ，Ａ，Ｂ，Ｃ，ｓ１，ｓ２，ｓｒ）、グループ秘密鍵ｇｍｓｋ＝（ａ，ｂ，ｘ１，ｘ２，ｙ１，ｙ２，ｚ）及びハッシュ値αに基づいて、検証式ｕ１＾｛ｘ１＋ｙ１α｝ｕ２＾｛ｘ２＋ｙ２α｝＝ｖが成り立つか否かを検証し（ＳＴ６７）、ステップＳＴ６５に進んで処理を終了する。【０１３５】
一方、ステップＳＴ６７の結果、検証式が成り立てば有効（valid）と判定し、署名検証部１６は、判定結果ＯＫ及び署名者特定要求を署名者特定部１７に送出して、処理を終了する。【０１３６】
署名者特定部１７は、判定結果ＯＫ及び署名者特定要求を受けると、図１５に示すように、管理者用記憶部１１内のグループ署名σ及びグループ秘密鍵ｇｍｓｋに基づいて、署名者特定情報Ｔ＝ｅ／ｕ１ｚを計算し（ＳＴ７１）、署名者特定情報Ｔを得る（ＳＴ７２）。【０１３７】
続いて、署名者特定部１７は、署名者特定情報Ｔに基づいて管理者用記憶部１１を検索し、署名者特定情報Ｔに対応するユーザ識別情報ＩＤ（j）（ただし、１≦ｊ≦ｎ）を出力部１８に出力する。さらに、署名者特定部１７は、ユーザ識別情報ＩＤ（ ）に基づいて管理者用記憶部１１を検索し、ユーザ識別情報ＩＤ（ｊ）に対応するユーザ情報を出力部１８に出力することもできる。【０１３８】
出力部１８は、これらユーザ識別情報ＩＤ（ｊ）及びユーザ情報を表示出力する。【０１３９】
＜実施形態方式の安全性＞
ここでは実施形態方式の安全性を証明する。【０１４０】
［定理１］提案グループ署名方式はランダムオラクルモデルにおいてＤＤＨ問題が困難であるという仮定の下で安全である。  
［補題１］実施形態方式は正当性（correctness）を持つ。  
（証明）実施形態方式の定義より明らか。【０１４１】
［補題２］実施形態方式はランダムオラクルモデルにおいてＤＤＨ問題が困難であるという仮定の下で匿名性（anonymity）を持つ。  
（証明スケッチ）実施形態方式の匿名性を無視できない確率で破る敵Ａａｎｏｎを利用してＤＤＨ問題を無視できない確率で破る解く敵ＡＤＤＨを構成する。  
敵ＡＤＤＨへの入力を（ｇ１，ｇ２，ｕ１，ｕ２）とする。【０１４２】
鍵生成アルゴリズムＧＫｇを以下のようにシミュレートする。【０１４３】
ｘ１，ｘ２，ｙ１，ｙ２，ｚ∈Ｚｑをランダムに選択する。  
ｉ∈｛１，…，ｎ｝をランダムに選択する。  
ｋｉ１，ｋｉ２∈Ｚｑをランダムに選択する。  
ｆ＝ｇ１＾｛ｋｉ１｝ｇ２＾｛ｋｉ２｝を計算する。  
Ｔｉ＝ｇ１＾｛ｋｉ１｝とする。  
ｊ∈｛１，…ｎ｝＼｛ｉ｝に対してＴｊ∈Ｇをランダムに選択する。  
ｃ＝ｇ１＾｛ｘ１｝ｇ２＾｛ｘ２｝、ｄ＝ｇ１＾｛ｙ１｝ｇ２＾｛ｙ２｝、ｈ＝ｇ１ｚを計算する。  
ハッシュ関数Ｈを汎用一方向性ハッシュ関数の集合から選択する。  
グループ公開鍵ｇｐｋ＝（ｇ１，ｇ２，ｆ，ｃ，ｄ，ｈ，Ｈ）、ユーザｉのメンバ秘密鍵ｇｓｋ［ｉ］＝（ｋｉ１，ｋｉ２）とする。  
ユーザｊに対する買収質問（corruption query）の応答を以下のようにシミュレートする。  
ｊ＝ｉの場合はｇｓｋ［ｉ］＝（ｋｉ１，ｋｉ２）を返し、それ以外のユーザが指定された場合はエラーとして終了する。【０１４４】
ユーザｊ、メッセージｍｓｇの署名要求に対し、署名質問（signing query）に対する応答を以下のようにシミュレートする。  
署名者特定情報の暗号文の部分はＴｊのクラマー−シャウプ（Cramer-Shoup）暗号化を行う。  
非対話的知識証明の部分はランダムオラクルを利用したシミュレーションを行う。これは、一般的な手法であるため、詳細の説明を省略する。【０１４５】
挑戦者（challenger）を以下のようにシミュレートする。  
ｂ∈｛０，１｝をランダムに選択する。  
署名者特定情報の暗号文の部分はクラマー−シャウプ暗号の安全性証明と同様にシミュレートする。  
非対話的知識証明の部分はランダムオラクルを利用したシミュレーションを行う。  
敵ＡＤＤＨは、ｂ＝ｂ’の場合には１を出力し、それ以外の場合は０を出力する。  
上述のシミュレーションはいずれも正しく行われているため、敵ＡＤＤＨはＤＤＨ問題を無視できない確率で解く。【０１４６】
しかしながら、この敵ＡＤＤＨはＤＤＨ問題が困難であるという仮定に反する。従って、前提とした、匿名性を無視できない確率で破る敵Ａａｎｏｎは存在しない。【０１４７】
［補題３］実施形態方式はランダムオラクルモデルにおいて離散対数問題が困難であるという仮定の下で追跡可能性（traceability）を持つ。  
（証明スケッチ）実施形態方式の追跡可能性を無視できない確率で破る敵Ａｔｒａｃｅを利用して離散対数問題を無視できない確率で破る解く敵ＡＤＬを構成する。  
敵ＡＤＬへの入力を（ｇ１，ｆ）とする。【０１４８】
鍵生成アルゴリズムＧＫｇを以下のようにシミュレートする。  
ｉ∈｛１，…，ｎ｝をランダムに選択する。  
ｋｉ１，ｋｉ２∈Ｚｑをランダムに選択する。  
ｇ２＝（ｆｇ１＾｛−ｋｉ１｝）＾｛１／ｋｉ２｝とする。  
Ｔｉ＝ｇ１＾｛ｋｉ１｝とする。  
ｊ∈｛１，…，ｎ｝＼｛ｉ｝に対してＴｊ∈Ｇをランダムに選択する。  
ｘ１，ｘ２，ｙ１，ｙ２，ｚ∈Ｚｑをランダムに選択する。  
ｃ＝ｇ１＾｛ｘ１｝ｇ２＾｛ｘ２｝、ｄ＝ｇ１＾｛ｙ１｝ｇ２＾｛ｙ２｝、ｈ＝ｇ１ｚを計算する。  
ハッシュ関数Ｈを汎用一方向性ハッシュ関数から選択する。  
グループ公開鍵ｇｐｋ＝（ｇ１，ｇ２，ｆ，ｃ，ｄ，ｈ，Ｈ）、ユーザｉのメンバ秘密鍵ｇｓｋ［ｉ］＝（ｋｉ１，ｋｉ２）とする。【０１４９】
署名質問（signing query）と買収質問（corruption query）の応答を匿名性（anonymity）の証明と同様にシミュレートする。  
巻き戻し（rewind）によって２つの異なる署名  
σ＝（ｕ１，ｕ２，ｅ，ｖ，Ａ，Ｂ，Ｃ，ｓ１，ｓ２，ｓｒ）と、
σ’＝（ｕ１’，ｕ２’，ｅ’，ｖ’，Ａ’，Ｂ’，Ｃ’，ｓ１’，ｓ２’，ｓｒ’）を得る。【０１５０】
β＝Ｈ（ｇ１，ｇ２，ｈ，ｕ１，ｕ２，ｅ，ｖ，Ａ，Ｂ，Ｃ，ｍｓｇ）、
β’＝Ｈ（ｇ１，ｇ２，ｈ，ｕ１’，ｕ２’，ｅ’，ｖ’，Ａ’，Ｂ’，Ｃ’，ｍｓｇ）とし、ｋ１’＝（ｓ１−ｓ１’）／（β−β’）、ｋ２’＝（ｓ２−ｓ２’）／（β−β’）とすると、ｆ＝ｇ１＾｛ｋ１’｝ｇ２＾｛ｋ２’｝である。また、追跡可能性の定義より（ｋ１’，ｋ２’）≠ｊ（ｋｉ１，ｋｉ２）であるため、ｇ２＝ｇ１＾｛−（ｋｉ１−ｋ１’）／（ｋｉ２−ｋ２’）｝が成り立つ。【０１５１】
−（ｋｉ１−ｋ１’）／（ｋｉ２−ｋ２’）＝Γとするとｌｏｇｇ_１ｆ＝ｋｉ１＋Γｋｉ２として敵ＡＤＬは無視できない確率で離散対数を求められる。なお、下付の“_”は添字を表す。すなわち、“ｌｏｇｇ_１ｆ”は、ｇ１を底としたｆの対数を表す。【０１５２】
しかしながら、この敵ＡＤＬは離散対数問題が困難であるという仮定に反する。従って、前提とした、追跡可能性を無視できない確率で破る敵Ａｔｒａｃｅは存在しない。【０１５３】
＜実施形態方式の効率＞
実施形態方式の効率を評価するために、通常の電子署名であるＲＳＡ署名方式の署名生成の計算量を基準にしたときの従来のグループ署名方式及び実施形態方式の計算量とデータ長を考える。【０１５４】
従来のグループ署名方式としては非常に高速な［ＣＧ０４］方式と比較する。［ＣＧ０４］方式は、[ＡＣＪＴ００]方式と比較しても２６倍以上も高速であり、また、双線形写像（bilinear map）を利用した方式（D. Boneh, X. Boyen, and H. Shacham, “Short group signatures,” In Proc. of CRYPTO 2004, LNCS 3152, pp.41-55, 2004.及びJ. Furukawa and H. Imai, “An efficient group signature scheme from bilinear maps,” In Proc. of ACISP 2005, LNCS 3574, pp.455-467, 2005. 参照）と比較しても高速である。【０１５５】
まず、計算量の比較方法の考え方を以下にまとめる。  
比較する方式の計算量の大部分はベキ乗剰余演算にかかる。このため、ベキ乗剰余演算以外の計算量を無視し、ベキ乗剰余演算の計算量に注目する。  
ベキ乗剰余演算の計算量は（法のビット長）２×ベキ指数のビット長に比例するため、法のビット長が同じ場合には全体の計算量がベキ指数のビット長の総和に比例する。【０１５６】
また、法の素因数分解を知っている場合、中国人剰余定理（Chinese remainder theorem：ＣＲＴ）を利用できるため、計算量は素因数分解を知らない場合に対してＲＳＡモジュラス（modulus（ｎ＝ｐｑ、ｐ，ｑ：素数（prime）、
【数１】
2009008069.tif 000003
【０１５７】
））の場合で１／４から１／３程度になる。ここでは計算量が１／４になるものとして計算量を見積もる。【０１５８】
さらに、ベキ乗演算の高速処理手法である指数同時乗算（simultaneous multiple exponentiation）法を利用することでΠi ｇｉ＾｛ｅｉ｝の形の計算は、ｍａｘｉ（｛ｅｉ｝）＝ｅｊなるｇｊ＾｛ｅｊ｝の計算と同程度で処理可能である。【０１５９】
比較する際のセキュリティパラメータは、［ＣＧ０４］方式の推奨パラメータを利用した場合を基準とする。推奨パラメータは、２０４８ビットのＲＳＡモジュラスを利用しているため、ＲＳＡ方式では同じく２０４８ビットのＲＳＡモジュラスを利用する。実施形態方式で利用する乗法巡回群Ｇについては、Ｚｐ＊と楕円曲線との２つを利用する。Ｚｐ＊では、ｐを２０４８ビットの素数、ｐ−１を割り切るｑを２２４ビットの素数としたときの位数ｑのＺｐ＊の部分群を利用する。ｐ，ｑの値はＦＩＰＳ（federal information processing standard）１８６−３のドラフト(draft)（“March 13, 2006: Draft Federal Information Processing Standard (FIPS) 186-3 − Digital Signature Standard (DSS),” http://csrc.nist.gov/publications/drafts.html （2007 年6 月現在） 参照）でも利用されている値であり、２０４８ビットのＲＳＡモジュラスと同程度のセキュリティパラメータとみなせる。楕円曲線では、これと同等のセキュリティパラメータである２２４ビットの素数から生成される楕円曲線を利用する。【０１６０】
以上を考慮したうえで、ＲＳＡ署名方式、［ＣＧ０４］方式、本実施形態方式の主な処理の計算量とデータ長を図１６に示す。なお、署名生成計算量及び署名検証計算量は、ベキ指数のビット長の総和を示しており、ＣＲＴを利用可能な場合には１／４で計算している。ＲＳＡ方式の署名検証計算量は、公開鍵ｄの長さに依存し、一般に小さい。ＲＳＡ方式の署名鍵長は、素数ｐ，ｑと秘密鍵ｅを持つ場合の値である。ＲＳＡ方式の検証鍵長は、公開鍵ｄを小さくした場合の値である。【０１６１】
本実施形態方式の署名生成計算量はＲＳＡ方式の３倍であるので、ＲＳＡ方式の約８倍の［ＣＧ０４］方式に比べ、低く抑えられている。このため、本実施形態方式の署名生成は高速に実行することができる。【０１６２】
本実施形態方式の署名鍵長（メンバ秘密鍵長）は、ＲＳＡ方式の１／９倍であるので、ＲＳＡ方式の約１．１倍の［ＣＧ０４］方式に比べ、短くなっている。【０１６３】
なお、本実施形態方式のグループ秘密鍵長は、［ＣＧ０４］方式よりも長くなっている。しかしながら、グループ秘密鍵長の増加は、グループ管理者装置１０以外の装置２０１〜２０ｎ，３０の計算量には影響せず、一般的にはグループ管理者装置は高性能・高信頼な計算機であるなど署名者装置や検証者装置と比べて計算量的な制約が少ない場合が多く、実用上問題ない。【０１６４】
また、本実施形態方式は、楕円曲線暗号方式で実装した場合、署名長がＲＳＡ方式の１．５倍となるので、［ＣＧ０４］方式に比べ、署名長を大幅に短縮することができる。【０１６５】
すなわち、本実施形態方式は、［ＣＧ０４］方式に比べ、署名鍵長及び検証鍵長が短く、署名生成及び署名検証を高速に実行することができる。理由は、本実施形態方式が素数位数ｑを法とした完全離散対数ベースの方式であるのに対し、［ＣＧ０４］方式が合成数ｎ＝ｐｑを法としたＲＳＡベースの方式であることによる。【０１６６】
例えば、離散対数ベースの方式では、ｙ＝ｇｘ  ｍｏｄ  ｑの演算において、法ｑが２０４８ビットの場合、離散対数ｘが２２４ビット程度となる。【０１６７】
一方、ＲＳＡベースの方式では、Ｃ＝ｍｅ  ｍｏｄ  ｎの演算において、法ｎが２０４８ビットの場合、公開鍵ｅも２０４８ビット程度となる。従って、ＲＳＡベースの［ＣＧ０４］方式では、本実施形態方式のような鍵長の短縮化及び演算の高速化が不可能となっている。【０１６８】
上述したように本実施形態によれば、素数位数ｑの乗法巡回群Ｇを用いて完全な離散対数ベースのグループ署名方式とし、且つリプレゼンテーションｋｉ１，ｋｉ２をメンバ秘密鍵としたグループ署名方式を実現したことにより、従来の［ＣＧ０４］方式に比べ、計算量を減らして計算速度を向上することができる。なお、「完全な離散対数ベースのグループ署名方式」とは、素数位数ｑの乗法巡回群Ｇを用いて乗法巡回群として位数が未知のものを利用せずに、位数が既知のもののみを利用したグループ署名方式を意味している。【０１６９】
例えば、本実施形態によれば、完全な離散対数ベースの方式であるため、図１６に示した通り、ＲＳＡベースの［ＣＧ０４］方式では不可能な位に、非常に高速でデータ長が短いグループ署名方式を実現することができる。【０１７０】
補足すると、グループ管理者装置１０においては、グループ公開鍵に値ｇ１，ｇ２，ｆを含むことにより、効率よくグループ署名を生成することができる。また、グループ秘密鍵に値ａ，ｂを含むことにより、メンバ数ｎ個のメンバ秘密鍵を効率よく生成することができる。【０１７１】
署名者装置２０ｉにおいては、リプレゼンテーションの一部ｋｉ１に基づく署名特定情報Ｔｉを用いることにより、零知識証明を効率よく生成することができる。すなわち、リプレゼンテーション自体ではなく、リプレゼンテーションから一意に計算される値を署名者特定情報として用いるので、零知識証明の生成及び検証効率を向上できる。【０１７２】
検証者装置３０及びグループ管理者装置１０においては、零知識証明を含むグループ署名σにより、零知識証明を効率よく検証でき、もって、グループ署名σを効率よく検証することができる。【０１７３】
さらに、グループ管理者装置１０においては、グループ署名σが署名者特定情報Ｔｉの暗号文データを含むことにより、暗号文データを復号するだけで署名者特定情報Ｔｉを得られるので、署名者を効率よく特定することができる。【０１７４】
また、本実施形態によれば、ＤＤＨ問題に基づく最初の実用的グループ署名方式を実現することができる。【０１７５】
また、本実施形態によれば、署名生成におけるベキ乗演算の底が固定されるので、指数同時乗算法の計算テーブルを事前に計算しておくことにより、効率よくベキ乗演算を実行することができる。【０１７６】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。【０１７７】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。【０１７８】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。【０１７９】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。【０１８０】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。【０１８１】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。【０１８２】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。【０１８３】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【産業上の利用可能性】
【０１８４】
以上説明したように本発明によれば、計算量を減らして計算速度を向上できるグループ署名システム、装置及びプログラムを提供できる。
【図１】
2009008069.tif 000004
【図２】
2009008069.tif 000005
【図３】
2009008069.tif 000006
【図４】
2009008069.tif 000007
【図５】
2009008069.tif 000008
【図６】
2009008069.tif 000009
【図７】
2009008069.tif 000010
【図８】
2009008069.tif 000011
【図９】
2009008069.tif 000012
【図１０】
2009008069.tif 000013
【図１１】
2009008069.tif 000014
【図１２】
2009008069.tif 000015
【図１３】
2009008069.tif 000016
【図１４】
2009008069.tif 000017
【図１５】
2009008069.tif 000018
【図１６】
2009008069.tif 000019
【国際調査報告】
2009008069.tif 000020
2009008069.tif 000021