(57)【要約】【課題】  ２台の装置間で情報を授受しながらグループ署名生成の計算を行う際に、両装置間の情報の授受回数を低減する。【解決手段】  メンバ署名生成装置１０により、メッセージｍに対するグループ署名を生成するとき、メンバ証明書certをグループ署名生成装置２０に送信し、グループ署名生成装置２０により、メンバ証明書certに基づいて生成した情報σ’をメンバ署名生成装置１０に送信し、メンバ署名生成装置１０により、情報σ’に基づいて生成したメンバ署名σ”をグループ署名生成装置２０に送信し、グループ署名生成装置２０により、メンバ署名σ”及びメンバ証明書certに基づいて、グループ署名σを生成し出力する。これにより、両装置１０，２０間において、情報の授受回数を１．５回の往復回数（片道３回）とし、従来の２．５回の往復回数よりも低減させることができる。【選択図】  図２
2006203827.tif 000002
【特許請求の範囲】
【請求項１】
メンバ証明書（cert）、メッセージ（ｍ）及びメンバ秘密鍵（ｘ）を有するメンバ署名生成装置と、グループ署名生成装置との間で情報を授受しながら、証明書関連情報（Ｔ1，Ｔ2，Ｔ3）、メンバ署名（ｃ，ｓ2）及びメンバ署名関連情報（ｓ1，ｓ3，ｓ4）からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成システムであって、
前記グループ署名生成装置は、
前記メンバ署名生成装置からメンバ証明書を受けると、このメンバ証明書に基づいて前記証明書関連情報及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）を生成する署名関連情報生成手段と、
この証明書関連情報及び演算パラメータを前記メンバ署名生成装置に送信する証明書関連情報送信手段と、
前記メンバ署名生成装置からメンバ署名を受けると、このメンバ署名及び前記メンバ証明書に基づいて、前記メンバ署名関連情報を生成する署名関連情報生成手段と、
このメンバ署名関連情報、前記証明書関連情報及び前記メンバ署名からなる前記グループ署名を生成するグループ署名生成手段と、
このグループ署名を出力するグループ署名出力手段とを備えており、
前記メンバ署名生成装置は、
前記メンバ証明書及びメンバ秘密鍵が記憶される記憶装置と、
前記メッセージを入力するためのメッセージ入力手段と、
このメッセージに対するグループ署名を生成するとき、前記記憶装置内のメンバ証明書を前記グループ署名生成装置に送信する証明書送信手段と、
前記証明書関連情報及び前記演算パラメータを受けると、この証明書関連情報、演算パラメータ、前記メッセージ及びメンバ秘密鍵に基づいて、前記メンバ署名を生成するメンバ署名生成手段と、
このメンバ署名を前記グループ署名生成装置に送信するメンバ署名送信手段と
を備えたことを特徴とするグループ署名生成システム。
【請求項２】
請求項１に記載のグループ署名生成システムにおいて、
前記メンバ署名生成装置が携帯電話装置であり、
前記グループ署名生成装置が前記携帯電話装置に通信するための通信手段を更に備えたサーバ装置であるとき、
前記メッセージを前記サーバ装置を介して前記携帯電話装置に送信し、前記サーバ装置から出力されたグループ署名を受けると、このグループ署名の正当性を検証するグループ署名検証装置を更に備えたことを特徴とするグループ署名生成システム。
【請求項３】
請求項１に記載のグループ署名生成システムにおいて、
前記メンバ署名生成装置がスマートカード装置であり、
前記グループ署名生成装置が前記スマートカード装置を着脱自在に保持し且つこのスマートカードに読出／書込するための読出／書込手段を更に備えた操作端末であるとき、
前記メッセージを前記操作端末を介して前記スマートカード装置に送信し、前記操作端末から出力されたグループ署名を受けると、このグループ署名の正当性を検証するグループ署名検証装置を更に備えたことを特徴とするグループ署名生成システム。
【請求項４】
メンバ証明書（cert）、メッセージ（ｍ）及びメンバ秘密鍵（ｘ）を有するメンバ署名生成装置と、グループ署名生成装置との間で情報を授受しながら、証明書関連情報（Ｔ1，Ｔ2，Ｔ3）、メンバ署名（ｃ，ｓ2）及びメンバ署名関連情報（ｓ1，ｓ3，ｓ4）からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成システムに用いられる前記グループ署名生成装置であって、
前記メンバ署名生成装置からメンバ証明書を受けると、このメンバ証明書に基づいて前記証明書関連情報及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）を生成する署名関連情報生成手段と、
この証明書関連情報及び演算パラメータを前記メンバ署名生成装置に送信する証明書関連情報送信手段と、
前記メンバ署名生成装置により前記証明書関連情報、前記演算パラメータ、前記メッセージ及びメンバ秘密鍵に基づいてメンバ署名が生成され、このメンバ署名を当該メンバ署名生成装置から受けると、このメンバ署名及び前記メンバ証明書に基づいて、前記メンバ署名関連情報を生成する署名関連情報生成手段と、
このメンバ署名関連情報、前記証明書関連情報及び前記メンバ署名からなる前記グループ署名を生成するグループ署名生成手段と、
このグループ署名を出力するグループ署名出力手段と
を備えたことを特徴とするグループ署名生成装置。
【請求項５】
公開されているグループ公開鍵ｐｋ＝（ｎ，ａ，ａ0，ｙ，ｇ，ｈ）を利用可能であり、メンバ証明書cert＝（Ａ，ｅ）（但しＡ＝(ａｘａ0)1/e mod ｎであり、ｅは素数、ｘはメンバ秘密鍵）、メッセージｍ及びメンバ秘密鍵ｘを有するメンバ署名生成装置との間で情報を授受しながら、証明書関連情報Ｔ1，Ｔ2，Ｔ3、メンバ署名ｃ，ｓ2及びメンバ署名関連情報ｓ1，ｓ3，ｓ4からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成装置であって、
前記メンバ署名生成装置からメンバ証明書certを受けると、このメンバ証明書cert、第１乱数情報ｗ及び前記グループ公開鍵ｐｋに基づいて、以下の第１式乃至第３式：
第１式  Ｔ1 ＝ Ａｙｗ mod ｎ，
第２式  Ｔ2 ＝ ｇｗ mod ｎ，
第３式  Ｔ3 ＝ ｇｅｈｗ mod ｎ．
の計算により、前記証明書関連情報Ｔ1，Ｔ2，Ｔ3を生成する手段と、
前記証明書関連情報Ｔ1，Ｔ2、第２乃至第４乱数情報ｒ1，ｒ3，ｒ4及び前記グループ公開鍵ｐｋに基づいて、以下の第４式乃至第７式：
第４式  ｄ1’＝Ｔ1{r_1} ／ ｙ{r_3} mod ｎ，（但し_は下付添字を表す）
第５式  ｄ2 ＝ Ｔ2{r_1} ／ ｇ{r_3} mod ｎ，
第６式  ｄ3 ＝ ｇ{r_4} mod ｎ，
第７式  ｄ4 ＝ ｇ{r_1}ｈ{r_4} mod ｎ．
の計算により、演算パラメータｄ1’，ｄ2，ｄ3，ｄ4を生成する手段と、
前記証明書関連情報Ｔ1，Ｔ2，Ｔ3及び演算パラメータｄ1’，ｄ2，ｄ3，ｄ4を前記メンバ署名生成装置に送信する証明書関連情報送信手段と、
前記メンバ署名生成装置により前記証明書関連情報、前記演算パラメータ、前記メッセージｍ、メンバ秘密鍵ｘ及びハッシュ関数Ｈに基づいて、以下の第８式乃至第１０式：
第８式  ｄ1＝ｄ1’／ａ{r_2} mod ｎ，
第９式  ｃ＝Ｈ(ｇ‖ｈ‖ｙ‖ａ0‖ａ‖Ｔ1‖Ｔ2‖Ｔ3‖ｄ1‖ｄ2‖ｄ3‖ｄ4‖ｍ),  （但し、‖はデータの連接を表す）
第１０式  ｓ2＝ｒ2−ｃ（ｘ−２{λ_1}).  （但しλ1はシステムパラメータ）
の計算によりメンバ署名ｃ，ｓ2が生成され、このメンバ署名を当該メンバ署名生成装置から受けると、このメンバ署名及び前記メンバ証明書に基づいて、以下の第１１式乃至第１３式：
第１１式  ｓ1＝ｒ1−ｃ（ｅ−２{γ_1})，  （但しγ1はシステムパラメータ），
第１２式  ｓ3＝ｒ3−ｃｅｗ，
第１３式  ｓ4＝ｒ4−ｃｗ．
の計算により、前記メンバ署名関連情報ｓ1，ｓ3，ｓ4を生成する署名関連情報生成手段と、
このメンバ署名関連情報ｓ1，ｓ3，ｓ4、前記証明書関連情報Ｔ1，Ｔ2，Ｔ3及び前記メンバ署名ｃ，ｓ2からなる前記グループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するグループ署名生成手段と、
このグループ署名を出力するグループ署名出力手段と
を備えたことを特徴とするグループ署名生成装置。
【請求項６】
請求項４又は請求項５に記載のグループ署名生成装置において、
前記メンバ署名生成装置が携帯電話装置であるとき、
前記携帯電話装置及び外部のグループ署名検証装置に通信するための通信手段を更に備えており、
前記通信手段は、
外部のグループ署名検証装置から受けた前記メッセージを前記携帯電話装置に送信するメッセージ送信手段と、
前記出力されたグループ署名を前記グループ署名検証装置に送信するグループ署名送信手段とを備えたことを特徴とするグループ署名生成装置。
【請求項７】
請求項４又は請求項５に記載のグループ署名生成装置において、
前記メンバ署名生成装置がスマートカード装置であるとき、
前記スマートカード装置を着脱自在に保持する保持手段と、
前記スマートカード装置及び外部のグループ署名検証装置に通信するための通信手段を更に備えており、
前記通信手段は、
外部のグループ署名検証装置から受けた前記メッセージを前記携帯電話装置に送信するメッセージ送信手段と、
前記出力されたグループ署名を前記グループ署名検証装置に送信するグループ署名送信手段とを備えたことを特徴とするグループ署名生成装置。
【請求項８】
メンバ証明書（cert）、メッセージ（ｍ）及びメンバ秘密鍵（ｘ）を有するメンバ署名生成装置と、グループ署名生成装置との間で情報を授受しながら、証明書関連情報（Ｔ1，Ｔ2，Ｔ3）、メンバ署名（ｃ，ｓ2）及びメンバ署名関連情報（ｓ1，ｓ3，ｓ4）からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成システムに用いられる前記メンバ署名生成装置であって、
前記メンバ証明書及びメンバ秘密鍵が記憶される記憶装置と、
前記メッセージを入力するためのメッセージ入力手段と、
このメッセージに対するグループ署名を生成するとき、前記記憶装置内のメンバ証明書を前記グループ署名生成装置に送信する証明書送信手段と、
前記グループ署名生成装置により前記メンバ証明書に基づいて前記証明書関連情報及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）が生成され、この証明書関連情報及び演算パラメータを当該グループ署名生成装置から受けると、この証明書関連情報、演算パラメータ、前記メッセージ及びメンバ秘密鍵に基づいて、前記メンバ署名を生成するメンバ署名生成手段と、
このメンバ署名を前記グループ署名生成装置に送信することにより、前記グループ署名生成装置に対し、このメンバ署名及び前記メンバ証明書に基づいて前記メンバ署名関連情報を生成させると共に、このメンバ署名関連情報、前記証明書関連情報及び前記メンバ署名からなる前記グループ署名を出力させるためのメンバ署名送信手段と
を備えたことを特徴とするメンバ署名生成装置。
【請求項９】
公開されているグループ公開鍵ｐｋ＝（ｎ，ａ，ａ0，ｙ，ｇ，ｈ）を利用可能であり、メンバ証明書cert＝（Ａ，ｅ）（但しＡ＝(ａｘａ0)1/e mod ｎであり、ｅは素数、ｘはメンバ秘密鍵）、メッセージｍ及びメンバ秘密鍵ｘを有し、グループ署名生成装置との間で情報を授受しながら、証明書関連情報Ｔ1，Ｔ2，Ｔ3、メンバ署名ｃ，ｓ2及びメンバ署名関連情報ｓ1，ｓ3，ｓ4からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を前記グループ署名生成装置に生成させるためのメンバ署名生成装置であって、
前記メンバ証明書及びメンバ秘密鍵が記憶される記憶装置と、
前記メッセージを入力するためのメッセージ入力手段と、
このメッセージに対するグループ署名を生成するとき、前記記憶装置内のメンバ証明書を前記グループ署名生成装置に送信する証明書送信手段と、
前記グループ署名生成装置により前記メンバ証明書、第１乃至第４乱数情報ｗ，ｒ1，ｒ3，ｒ4及び前記グループ公開鍵ｐｋに基づいて、以下の第１式乃至第７式：
第１式  Ｔ1 ＝ Ａｙｗ mod ｎ，
第２式  Ｔ2 ＝ ｇｗ mod ｎ，
第３式  Ｔ3 ＝ ｇｅｈｗ mod ｎ，
第４式  ｄ1’＝Ｔ1{r_1} ／ ｙ{r_3} mod ｎ，（但し_は下付添字を表す）
第５式  ｄ2 ＝ Ｔ2{r_1} ／ ｇ{r_3} mod ｎ，
第６式  ｄ3 ＝ ｇ{r_4} mod ｎ，
第７式  ｄ4 ＝ ｇ{r_1}ｈ{r_4} mod ｎ．
の計算により前記証明書関連情報Ｔ1，Ｔ2，Ｔ3及び演算パラメータｄ1’，ｄ2，ｄ3，ｄ4が生成され、この証明書関連情報及び演算パラメータを当該グループ署名生成装置から受けると、この証明書関連情報、演算パラメータ、前記メッセージｍ、メンバ秘密鍵ｘ及びハッシュ関数Ｈに基づいて、以下の第８式乃至第１０式：
第８式  ｄ1＝ｄ1’／ａ{r_2} mod ｎ，
第９式  ｃ＝Ｈ(ｇ‖ｈ‖ｙ‖ａ0‖ａ‖Ｔ1‖Ｔ2‖Ｔ3‖ｄ1‖ｄ2‖ｄ3‖ｄ4‖ｍ),  （但し、‖はデータの連接を表す）
第１０式  ｓ2＝ｒ2−ｃ（ｘ−２{λ_1}).  （但しλ1はシステムパラメータ）
の計算により前記メンバ署名ｃ，ｓ2を生成するメンバ署名生成手段と、
このメンバ署名を前記グループ署名生成装置に送信することにより、前記グループ署名生成装置に対し、このメンバ署名及び前記メンバ証明書に基づいて、以下の第１１式乃至第１３式：
第１１式  ｓ1＝ｒ1−ｃ（ｅ−２{γ_1})，  （但しγ1はシステムパラメータ），
第１２式  ｓ3＝ｒ3−ｃｅｗ，
第１３式  ｓ4＝ｒ4−ｃｗ．
の計算により前記メンバ署名関連情報ｓ1，ｓ3，ｓ4を生成させると共に、このメンバ署名関連情報ｓ1，ｓ3，ｓ4、前記証明書関連情報Ｔ1，Ｔ2，Ｔ3及び前記メンバ署名ｃ，ｓ2からなる前記グループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を出力させるためのメンバ署名送信手段と
を備えたことを特徴とするメンバ署名生成装置。
【請求項１０】
請求項８又は請求項９に記載のメンバ署名生成装置において、
前記メンバ署名生成装置本体は携帯電話装置であり、
前記メッセージ入力手段は、外部のグループ署名検証装置により生成され前記グループ署名生成装置から受けたメッセージを前記携帯電話装置本体に入力することを特徴とするメンバ署名生成装置。
【請求項１１】
請求項８又は請求項９に記載のメンバ署名生成装置において、
前記メンバ署名生成装置本体はスマートカード装置であり、
前記メッセージ入力手段は、外部のグループ署名検証装置により生成され前記グループ署名生成装置から受けたメッセージを前記スマートカード装置本体に入力することを特徴とするメンバ署名生成装置。
【請求項１２】
メンバ証明書（cert）、メッセージ（ｍ）及びメンバ秘密鍵（ｘ）を有するメンバ署名生成装置とグループ署名生成装置との間で情報を授受しながら、証明書関連情報（Ｔ1，Ｔ2，Ｔ3）、メンバ署名（ｃ，ｓ2）及びメンバ署名関連情報（ｓ1，ｓ3，ｓ4）からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成システムに用いられる前記グループ署名生成装置のプログラムであって、
前記グループ署名生成装置のコンピュータを、
前記メンバ署名生成装置からメンバ証明書を受けると、このメンバ証明書をメモリに書き込む手段、
前記メモリ内のメンバ証明書に基づいて前記証明書関連情報及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）を生成する署名関連情報生成手段、
この証明書関連情報及び演算パラメータを前記メンバ署名生成装置に送信する証明書関連情報送信手段、
前記メンバ署名生成装置により前記証明書関連情報、前記演算パラメータ、前記メッセージ及びメンバ秘密鍵に基づいてメンバ署名が生成され、このメンバ署名を当該メンバ署名生成装置から受けると、このメンバ署名をメモリに書き込む手段、
前記メモリ内のメンバ署名及び前記メンバ証明書に基づいて、前記メンバ署名関連情報を生成する署名関連情報生成手段、
このメンバ署名関連情報、前記証明書関連情報及び前記メンバ署名からなる前記グループ署名を生成するグループ署名生成手段、
このグループ署名を出力するグループ署名出力手段、
として機能させるためのプログラム。
【請求項１３】
公開されているグループ公開鍵ｐｋ＝（ｎ，ａ，ａ0，ｙ，ｇ，ｈ）を利用可能であり、メンバ証明書cert＝（Ａ，ｅ）（但しＡ＝(ａｘａ0)1/e mod ｎであり、ｅは素数、ｘはメンバ秘密鍵）、メッセージｍ及びメンバ秘密鍵ｘを有するメンバ署名生成装置との間で情報を授受しながら、証明書関連情報Ｔ1，Ｔ2，Ｔ3、メンバ署名ｃ，ｓ2及びメンバ署名関連情報ｓ1，ｓ3，ｓ4からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成装置に用いられるプログラムであって、
前記グループ署名生成装置のコンピュータを、
前記メンバ署名生成装置からメンバ証明書certを受けると、このメンバ証明書certをメモリに書き込む手段、
前記メモリ内のメンバ証明書cert、第１乱数情報ｗ及び前記グループ公開鍵ｐｋに基づいて、以下の第１式乃至第３式：
第１式  Ｔ1 ＝ Ａｙｗ mod ｎ，
第２式  Ｔ2 ＝ ｇｗ mod ｎ，
第３式  Ｔ3 ＝ ｇｅｈｗ mod ｎ．
の計算により、前記証明書関連情報Ｔ1，Ｔ2，Ｔ3を生成する手段、
前記証明書関連情報Ｔ1，Ｔ2、第２乃至第４乱数情報ｒ1，ｒ3，ｒ4及び前記グループ公開鍵ｐｋに基づいて、以下の第４式乃至第７式：
第４式  ｄ1’＝Ｔ1{r_1} ／ ｙ{r_3} mod ｎ，（但し_は下付添字を表す）
第５式  ｄ2 ＝ Ｔ2{r_1} ／ ｇ{r_3} mod ｎ，
第６式  ｄ3 ＝ ｇ{r_4} mod ｎ，
第７式  ｄ4 ＝ ｇ{r_1}ｈ{r_4} mod ｎ．
の計算により、演算パラメータｄ1’，ｄ2，ｄ3，ｄ4を生成する手段、
前記証明書関連情報Ｔ1，Ｔ2，Ｔ3及び演算パラメータｄ1’，ｄ2，ｄ3，ｄ4を前記メンバ署名生成装置に送信する証明書関連情報送信手段、
前記メンバ署名生成装置により前記証明書関連情報、前記演算パラメータ、前記メッセージｍ、メンバ秘密鍵ｘ及びハッシュ関数Ｈに基づいて、以下の第８式乃至第１０式：
第８式  ｄ1＝ｄ1’／ａ{r_2} mod ｎ，
第９式  ｃ＝Ｈ(ｇ‖ｈ‖ｙ‖ａ0‖ａ‖Ｔ1‖Ｔ2‖Ｔ3‖ｄ1‖ｄ2‖ｄ3‖ｄ4‖ｍ),  （但し、‖はデータの連接を表す）
第１０式  ｓ2＝ｒ2−ｃ（ｘ−２{λ_1}).  （但しλ1はシステムパラメータ）
の計算によりメンバ署名ｃ，ｓ2が生成され、このメンバ署名を当該メンバ署名生成装置から受けると、このメンバ署名をメモリに書き込む手段、
前記メモリ内のメンバ署名及び前記メンバ証明書に基づいて、以下の第１１式乃至第１３式：
第１１式  ｓ1＝ｒ1−ｃ（ｅ−２{γ_1})，  （但しγ1はシステムパラメータ），
第１２式  ｓ3＝ｒ3−ｃｅｗ，
第１３式  ｓ4＝ｒ4−ｃｗ．
の計算により、前記メンバ署名関連情報ｓ1，ｓ3，ｓ4を生成する署名関連情報生成手段、
このメンバ署名関連情報ｓ1，ｓ3，ｓ4、前記証明書関連情報Ｔ1，Ｔ2，Ｔ3及び前記メンバ署名ｃ，ｓ2からなる前記グループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するグループ署名生成手段、
このグループ署名を出力するグループ署名出力手段、
として機能させるためのプログラム。
【請求項１４】
請求項１２又は請求項１３に記載のプログラムにおいて、
前記メンバ署名生成装置が携帯電話装置であるとき、
前記グループ署名生成装置のコンピュータを、
前記携帯電話装置及び外部のグループ署名検証装置に通信するための通信手段として機能させ、
前記通信手段は、
外部のグループ署名検証装置から受けた前記メッセージを前記携帯電話装置に送信するメッセージ送信手段と、
前記出力されたグループ署名を前記グループ署名検証装置に送信するグループ署名送信手段とを含んでいるプログラム。
【請求項１５】
請求項１２又は請求項１３に記載のプログラムにおいて、
前記メンバ署名生成装置がスマートカード装置であるとき、
前記グループ署名生成装置のコンピュータを、
前記スマートカード装置を着脱自在に保持する保持手段と、
前記スマートカード装置及び外部のグループ署名検証装置に通信するための通信手段として機能させ、
前記通信手段は、
外部のグループ署名検証装置から受けた前記メッセージを前記携帯電話装置に送信するメッセージ送信手段と、
前記出力されたグループ署名を前記グループ署名検証装置に送信するグループ署名送信手段とを含んでいるプログラム。
【請求項１６】
メンバ証明書（cert）、メッセージ（ｍ）及びメンバ秘密鍵（ｘ）を有するメンバ署名生成装置とグループ署名生成装置との間で情報を授受しながら、証明書関連情報（Ｔ1，Ｔ2，Ｔ3）、メンバ署名（ｃ，ｓ2）及びメンバ署名関連情報（ｓ1，ｓ3，ｓ4）からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成システムに用いられ、前記メンバ証明書及びメンバ秘密鍵が記憶される記憶装置を備えた前記メンバ署名生成装置のプログラムであって、
前記メンバ署名生成装置のコンピュータを、
前記メッセージを入力するためのメッセージ入力手段、
このメッセージに対するグループ署名を生成するとき、前記記憶装置内のメンバ証明書を前記グループ署名生成装置に送信する証明書送信手段、
前記グループ署名生成装置により前記メンバ証明書に基づいて前記証明書関連情報及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）が生成され、この証明書関連情報及び演算パラメータを当該グループ署名生成装置から受けると、この証明書関連情報、演算パラメータ、前記メッセージ及びメンバ秘密鍵に基づいて、前記メンバ署名を生成するメンバ署名生成手段、
このメンバ署名を前記グループ署名生成装置に送信することにより、前記グループ署名生成装置に対し、このメンバ署名及び前記メンバ証明書に基づいて前記メンバ署名関連情報を生成させると共に、このメンバ署名関連情報、前記証明書関連情報及び前記メンバ署名からなる前記グループ署名を出力させるためのメンバ署名送信手段、
として機能させるためのプログラム。
【請求項１７】
公開されているグループ公開鍵ｐｋ＝（ｎ，ａ，ａ0，ｙ，ｇ，ｈ）を利用可能であり、メンバ証明書cert＝（Ａ，ｅ）（但しＡ＝(ａｘａ0)1/e mod ｎであり、ｅは素数、ｘはメンバ秘密鍵）及びメンバ秘密鍵ｘが記憶される記憶装置を有し、グループ署名生成装置との間で情報を授受しながら、証明書関連情報Ｔ1，Ｔ2，Ｔ3、メンバ署名ｃ，ｓ2及びメンバ署名関連情報ｓ1，ｓ3，ｓ4からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を前記グループ署名生成装置に生成させるためのメンバ署名生成装置に用いられるプログラムであって、
前記メンバ署名生成装置のコンピュータを、
メッセージｍを入力するためのメッセージ入力手段、
このメッセージｍに対するグループ署名を生成するとき、前記記憶装置内のメンバ証明書を前記グループ署名生成装置に送信する証明書送信手段、
前記グループ署名生成装置により前記メンバ証明書、第１乃至第４乱数情報ｗ，ｒ1，ｒ3，ｒ4及び前記グループ公開鍵ｐｋに基づいて、以下の第１式乃至第７式：
第１式  Ｔ1 ＝ Ａｙｗ mod ｎ，
第２式  Ｔ2 ＝ ｇｗ mod ｎ，
第３式  Ｔ3 ＝ ｇｅｈｗ mod ｎ，
第４式  ｄ1’＝Ｔ1{r_1} ／ ｙ{r_3} mod ｎ，（但し_は下付添字を表す）
第５式  ｄ2 ＝ Ｔ2{r_1} ／ ｇ{r_3} mod ｎ，
第６式  ｄ3 ＝ ｇ{r_4} mod ｎ，
第７式  ｄ4 ＝ ｇ{r_1}ｈ{r_4} mod ｎ．
の計算により前記証明書関連情報Ｔ1，Ｔ2，Ｔ3及び演算パラメータｄ1’，ｄ2，ｄ3，ｄ4が生成され、この証明書関連情報及び演算パラメータを当該グループ署名生成装置から受けると、この証明書関連情報、演算パラメータ、前記メッセージｍ、メンバ秘密鍵ｘ及びハッシュ関数Ｈに基づいて、以下の第８式乃至第１０式：
第８式  ｄ1＝ｄ1’／ａ{r_2} mod ｎ，
第９式  ｃ＝Ｈ(ｇ‖ｈ‖ｙ‖ａ0‖ａ‖Ｔ1‖Ｔ2‖Ｔ3‖ｄ1‖ｄ2‖ｄ3‖ｄ4‖ｍ),  （但し、‖はデータの連接を表す）
第１０式  ｓ2＝ｒ2−ｃ（ｘ−２{λ_1}).  （但しλ1はシステムパラメータ）
の計算により前記メンバ署名ｃ，ｓ2を生成するメンバ署名生成手段、
このメンバ署名を前記グループ署名生成装置に送信することにより、前記グループ署名生成装置に対し、このメンバ署名及び前記メンバ証明書に基づいて、以下の第１１式乃至第１３式：
第１１式  ｓ1＝ｒ1−ｃ（ｅ−２{γ_1})，  （但しγ1はシステムパラメータ），
第１２式  ｓ3＝ｒ3−ｃｅｗ，
第１３式  ｓ4＝ｒ4−ｃｗ．
の計算により前記メンバ署名関連情報ｓ1，ｓ3，ｓ4を生成させると共に、このメンバ署名関連情報ｓ1，ｓ3，ｓ4、前記証明書関連情報Ｔ1，Ｔ2，Ｔ3及び前記メンバ署名ｃ，ｓ2からなる前記グループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を出力させるためのメンバ署名送信手段、
として機能させるためのプログラム。
【請求項１８】
請求項１６又は請求項１７に記載のプログラムにおいて、
前記メンバ署名生成装置本体は携帯電話装置であり、
前記メッセージ入力手段は、外部のグループ署名検証装置により生成され前記グループ署名生成装置から受けたメッセージを前記携帯電話装置本体に入力することを特徴とするプログラム。
【請求項１９】
請求項１６又は請求項１７に記載のプログラムにおいて、
前記メンバ署名生成装置本体はスマートカード装置であり、
前記メッセージ入力手段は、外部のグループ署名検証装置により生成され前記グループ署名生成装置から受けたメッセージを前記スマートカード装置本体に入力することを特徴とするプログラム。
【請求項２０】
メンバ証明書（cert）、メッセージ（ｍ）及びメンバ秘密鍵（ｘ）を有するメンバ署名生成装置とグループ署名生成装置との間で情報を授受しながら、証明書関連情報（Ｔ1，Ｔ2，Ｔ3）、メンバ署名（ｃ，ｓ2）及びメンバ署名関連情報（ｓ1，ｓ3，ｓ4）からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成方法であって、
前記メンバ署名生成装置により、前記メンバ証明書及びメンバ秘密鍵が記憶装置に記憶される工程と、
前記メンバ署名生成装置により、前記メッセージを入力する工程と、
前記メンバ署名生成装置により、このメッセージに対するグループ署名を生成するとき、前記記憶装置内のメンバ証明書を前記グループ署名生成装置に送信する工程と、
前記グループ署名生成装置により、前記メンバ署名生成装置から受信したメンバ証明書に基づいて前記証明書関連情報及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）を生成する工程と、
この証明書関連情報及び演算パラメータを前記メンバ署名生成装置に送信する工程と、
前記メンバ署名生成装置により、前記グループ署名生成装置から前記証明書関連情報及び前記演算パラメータを受けると、この証明書関連情報、演算パラメータ、前記メッセージ及びメンバ秘密鍵に基づいて、前記メンバ署名を生成する工程と、
前記メンバ署名生成装置により、このメンバ署名を前記グループ署名生成装置に送信する工程と、
前記グループ署名生成装置により、前記メンバ署名生成装置からメンバ署名を受けると、このメンバ署名及び前記メンバ証明書に基づいて、前記メンバ署名関連情報を生成する工程と、
前記グループ署名生成装置により、このメンバ署名関連情報、前記証明書関連情報及び前記メンバ署名からなる前記グループ署名を生成する工程と、
前記グループ署名生成装置により、このグループ署名を出力する工程と
を備えたことを特徴とするグループ署名生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループ署名生成システム、装置、プログラム及び方法に係り、特に、２台の装置間で情報を授受しながらグループ署名生成の計算を行う際に、両装置間の情報の授受回数を低減し得るグループ署名生成システム、装置、プログラム及び方法に関する。
【背景技術】
【０００２】
デジタル署名方式の一種として、グループ署名方式が知られている（例えば、非特許文献１，２参照）。グループ署名方式は、非特許文献１によれば、以下の第１乃至第３の性質を持っている。
【０００３】
第１の性質は、あるグループに所属する任意のメンバがグループの代表として署名を生成することが可能な性質である。第２の性質は、検証者側においては、グループのメンバにより生成された署名である旨を検証可能であるものの、署名を生成したメンバ（以下、署名者という）を特定することが困難であるという匿名性を持つ性質である。第３の性質は、特定の情報により、グループ署名から署名者を特定することが可能な性質である。
【０００４】
このようなグループ署名方式は、様々な方式が提案されている。中でも非特許文献２に記載の方式（以下、非特許文献２方式という）は、強ＲＳＡ仮定、ＤＤＨ(decisional Diffie - Hellman)仮定及びランダムオラクルモデルの下で安全性が証明されており、最も実用的な方式の一つである。
【０００５】
しかしながら、これらのグループ署名方式は、署名者によるグループ署名生成に多くの計算量を必要とする。このため、署名者のデバイスが携帯電話などの計算能力の低いデバイスの場合、グループ署名生成の計算を行うことが実用上極めて困難となっている。
【０００６】
一方、この困難を解決可能な技術として、特許文献１に記載の方式（以下、特許文献１方式という）がある。
【０００７】
特許文献１方式によれば、計算能力の低い耐タンパー装置と、この耐タンパー装置を着脱自在に保持し且つ計算能力の高い利用者端末とを用いている。そして、特許文献１方式によれば、耐タンパー装置と利用者端末との間で情報を授受しながら、グループ署名生成の計算のうち、ほとんどの計算を利用者端末側で実行している。なお、情報の授受回数は、往復で２．５回（片道５回）である（特許文献１の図９、ＳＴ３５〜ＳＴ３９参照）。従って、特許文献１方式では、計算能力の低い耐タンパー装置を用いる場合でも、グループ署名生成の計算を行うことが実用上容易となっている。
【非特許文献１】D. Chaum, E. van Heyst, Group Signatures, Proceedings of EUROCRYPT'91, LNCS 547, Springer-Verlag, pp.257-265, 1991.
【非特許文献２】G. Ateniese, J. Camenisch, M.Joye, G.Tsudik, A practical and provably secure coalition-resistant group signature scheme, Proceedings of CRYPTO 2000, LNCS 1880, Springer-Verlag, pp.255-270, 2000.
【特許文献１】特開２００４−３２０５６２号公報（特に、第１８２乃至第１９０段落、図８及び図９等）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、以上のような特許文献１に記載のグループ署名方式は、通常、何の問題も無いが、本発明者の検討によれば、利用者端末と耐タンパー装置との間の情報の授受に関し、授受の回数を減らせる余地があると考えられる。
【０００９】
本発明は上記実情を考慮してなされたもので、２台の装置間で情報を授受しながらグループ署名生成の計算を行う際に、両装置間の情報の授受回数を低減し得るグループ署名生成システム、装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
第１の発明は、メンバ証明書（cert）、メッセージ（ｍ）及びメンバ秘密鍵（ｘ）を有するメンバ署名生成装置と、グループ署名生成装置との間で情報を授受しながら、証明書関連情報（Ｔ1，Ｔ2，Ｔ3）、メンバ署名（ｃ，ｓ2）及びメンバ署名関連情報（ｓ1，ｓ3，ｓ4）からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成するためのグループ署名生成システムであって、前記グループ署名生成装置としては、前記メンバ署名生成装置からメンバ証明書を受けると、このメンバ証明書に基づいて前記証明書関連情報及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）を生成する署名関連情報生成手段と、この証明書関連情報及び演算パラメータを前記メンバ署名生成装置に送信する証明書関連情報送信手段と、前記メンバ署名生成装置からメンバ署名を受けると、このメンバ署名及び前記メンバ証明書に基づいて、前記メンバ署名関連情報を生成する署名関連情報生成手段と、このメンバ署名関連情報、前記証明書関連情報及び前記メンバ署名からなる前記グループ署名を生成するグループ署名生成手段と、このグループ署名を出力するグループ署名出力手段とを備えており、前記メンバ署名生成装置としては、前記メンバ証明書及びメンバ秘密鍵が記憶される記憶装置と、前記メッセージを入力するためのメッセージ入力手段と、このメッセージに対するグループ署名を生成するとき、前記記憶装置内のメンバ証明書を前記グループ署名生成装置に送信する証明書送信手段と、前記証明書関連情報及び前記演算パラメータを受けると、この証明書関連情報、演算パラメータ、前記メッセージ及びメンバ秘密鍵に基づいて、前記メンバ署名を生成するメンバ署名生成手段と、このメンバ署名を前記グループ署名生成装置に送信するメンバ署名送信手段とを備えたグループ署名生成システムである。
【００１１】
（作用）
従って、第１の発明は以上のような手段を講じたことにより、メンバ署名生成装置とグループ署名生成装置との間において、情報の授受回数を１．５回の往復回数（片道３回）として、グループ署名を生成することができる。
【００１２】
すなわち、２台の装置間で情報を授受しながらグループ署名生成の計算を行う際に、従来よりも１往復（特許文献１の図９のＳＴ３６，ＳＴ３７）分だけ、両装置間の情報の授受回数を低減できる。
【００１３】
なお、第１の発明は、各装置からなる全体構成を「システム」として表現したが、これに限らず、全体構成又は各装置を「装置」、「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」として表現してもよい。
【発明の効果】
【００１４】
以上説明したように本発明によれば、２台の装置間で情報を授受しながらグループ署名生成の計算を行う際に、両装置間の情報の授受回数を低減できる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の各実施形態について図面を参照しながら説明するが、その前に各実施形態に共通したグループ署名方式について説明する。  
ここでは、スマートカードや携帯電話などの耐タンパデバイスにメンバ秘密鍵を保管し、このデバイスをもっていればグループ署名を生成可能なモデルを説明する。補足すると、従来の非特許文献２方式は計算量が大きく、計算能力が低いこれらのデバイス内で全ての計算を行なうことは、現状では実現上困難である。そこで、本明細書では、グループ署名計算の一部、特に署名者の匿名性に関する計算を外部モジュールに委託することにより、計算能力の低いデバイス内での計算量を軽減させるモデルを述べると共に、これと類似した特許文献１方式よりも情報の授受回数を低減させたモデルを述べる。
【００１６】
モデルとしては、図７に示すように、従来のグループ管理者ＧＭ、グループメンバMen、検証者Veriの３エンティティに加え、グループ署名の匿名性に関する計算を行なうエンティティである匿名プロキシＡＰを新たに定義したモデルを考える。
【００１７】
但し、匿名プロキシＡＰは、グループメンバMemに関する情報を保持せず、且つ、グループメンバMemに関する情報をグループ管理者ＧＭへ参照しないと仮定する。また、グループメンバMemが単独で実行する署名処理Signに代えて、グループメンバMemと匿名プロキシＡＰ間で実行されるグループ署名生成プロトコルを以下の通り定義する。
【００１８】
「グループ署名生成プロトコル」とは、グループメンバMemと匿名プロキシＡＰ間で実行されるプロトコルであり、安全な通信路上で実行されると仮定される。匿名プロキシＡＰは、入力メッセージに対するグループメンバMemのグループ署名を出力する。
【００１９】
（安全性）
本明細書では、匿名プロキシＡＰは、グループ管理者ＧＭの管理下にあると想定する。よって、匿名プロキシＡＰの安全性を以下のように仮定又は定義する。
【００２０】
匿名プロキシＡＰは、半正直(semi-honest；セミ・オネスト)と仮定する。すなわち、以下の２つの仮定を満たすとする。  
仮定１：匿名プロキシＡＰは、“グループ署名生成プロトコル”を正しく実行する。  
仮定２：匿名プロキシＡＰは、“グループ署名生成プロトコル”で得られた情報を外部に漏らさない。
【００２１】
また、匿名プロキシＡＰに対する安全性として、以下の偽造不可能力(unforgeability；アンフォージャビリティ)を定義する。
【００２２】
匿名プロキシＡＰにおける偽造不可能力とは、匿名プロキシＡＰがグループ署名生成プロトコルで実行された以外のメッセージに対して、検証に成功するグループ署名を生成することが困難である旨をいう。
【００２３】
匿名プロキシＡＰは、グループ管理者ＧＭの管理下にあると想定するため、匿名プロキシＡＰにおける匿名性(anonymity；アノニミティ)及び非結合能力(unlinkability；アンリンカビリティ)は必ずしも保たれなくても良い。なお、「匿名性」とは、グループ内の２人のメンバのいずれかが生成したグループ署名から、どちらのメンバが生成したかを識別することが困難なことを意味する。「非結合能力」とは、２つのグループ署名が同じメンバにより生成された署名か否かを判別することが困難なことを意味する。
【００２４】
（非特許文献２方式と本発明方式の概要）
ここでは、非特許文献２の概要を説明し、しかる後、これを改良しつつ、特許文献１方式よりも情報の授受回数を低減させた本発明方式の概要について述べる。また、本発明方式の安全性と計算効率について述べる。
【００２５】
（１．準備）
ｎ＝ｐｑ（ｐ,ｑ：素数）、ｇなどのパラメータを設定する。このとき、強ＲＳＡ仮定が成り立つと仮定する（非特許文献２参照）。
【００２６】
（２．非特許文献２方式）
非特許文献２方式の概要を説明する。セキュリティパラメータＬp，ｋ，εとし、セキュリティパラメータを満たす範囲でパラメータλ1，λ2，γ1，γ2を定める。また、パラメータλ1，λ2，γ1，γ2に基づいて、Λ，Γの範囲を定める。
【００２７】
（立ち上げ処理；Set up）
グループ管理者ＧＭは、グループ公開鍵ｐｋ＝（ｎ, ａ, ａ0, ｙ, ｇ, ｈ）及びグループ秘密鍵ｓｋ＝（ｐ’, ｑ’, ｘ）を計算する。
【００２８】
（参加プロトコル；Join protocol）
参加プロトコルの詳細は、非特許文献２に記載されている。参加プロトコルの結果、グループメンバMemは、メンバ秘密鍵ｘを秘密に得る。また、グループ管理者ＧＭは、メンバ秘密鍵に対するメンバ証明書cert＝（Ａ, e）を生成してグループメンバMemに送り、メンバ証明書とユーザ情報のペアを秘密に保管する。
【００２９】
（署名処理；Sign）
グループメンバは、メンバ秘密鍵ｘとメンバ証明書certを用いて、メッセージmに対するグループ署名σ＝（ｃ，ｓ1, ｓ2, ｓ3, ｓ4, Ｔ1, Ｔ2, Ｔ3）を生成する。なお、この非特許文献２方式では、計算の途中結果ｄ1を次式で計算している。
【数１】
2006203827.tif 000003
【００３０】
（検証処理；Verify）
検証者は、グループ公開鍵ｐｋを用いて、メッセージｍに対するグループ署名σ＝（ｃ，ｓ1, ｓ2, ｓ3, ｓ4, Ｔ1, Ｔ2, Ｔ3）の正当性を以下により検証する。
【００３１】
以下のハッシュ値ｃ’を計算する。
【数２】
2006203827.tif 000004
【００３２】
（開示処理；Open）
署名の正当性を検証する。証明書情報Ａ＝Ｔ1／Ｔ2ｘ（ｍｏｄ  ｎ）を計算し、証明書情報Ａが含まれるメンバ証明書certを検出することによりグループメンバを特定する。
【００３３】
（本発明方式の概要）
本明細書では、非特許文献２方式の署名処理Signに代えて、メンバ秘密鍵ｘとメンバ証明書certを保持するグループメンバMemと匿名プロキシＡＰ間で実行されるグループ署名生成プロトコルによりグループ署名を生成する方式を示す。
【００３４】
（署名生成プロトコル；Signing Protocol）
１．グループメンバMemは、メンバ証明書certを匿名プロキシＡＰに送る。
【００３５】
２．匿名プロキシＡＰは、署名Signと同様に（Ｔ1, Ｔ2, Ｔ3）及び（ｄ2, ｄ3, ｄ4）を計算する。また、匿名プロキシＡＰは、ｄ1’を計算する。そして、匿名プロキシＡＰは、（ｄ1’, ｄ2, ｄ3, ｄ4, Ｔ1, Ｔ2, Ｔ3）をグループメンバMemに送る。
【００３６】
３．グループメンバMemは、ｄ1’に基づいて、ｄ1を計算する。次に、グループメンバMemは、非特許文献２方式の署名処理Signと同様に、ハッシュ値ｃを計算する。最後に、グループメンバMemは、メンバ秘密鍵ｘを用いて、ｓ2を計算し、（ｃ，ｓ2）を匿名プロキシＡＰに送る。
【００３７】
４．匿名プロキシＡＰは、署名Signと同様に、ｓ1，ｓ3，ｓ4を計算し、グループ署名σ＝（ｃ，ｓ1, ｓ2, ｓ3, ｓ4, Ｔ1, Ｔ2, Ｔ3）を出力する。
【００３８】
（４．安全性）
非特許文献２方式におけるグループ署名の安全性は、強ＲＳＡ仮定、ＤＤＨ仮定及びランダムオラクルモデルの下で証明されている。本発明方式で得られるグループ署名は、非特許文献２方式と同じため、同様の安全性が成り立つ。
【００３９】
また、本発明方式では、匿名プロキシＡＰに対して以下の安全性が成り立つことが証明可能である。
【００４０】
匿名プロキシＡＰに対する安全性…強ＲＳＡ仮定とランダムオラクルモデルの下で、匿名プロキシＡＰが署名生成プロトコルで実行された以外のメッセージに対して、検証に成功するグループ署名を生成することは困難である。
【００４１】
（証明；sketch）  署名生成プロトコルにおいて、グループメンバMemから匿名プロキシＡＰに送られる（ｃ, ｓ2）は、メッセージ（ｇ, ｈ, ｙ, ａ0, Ｔ2, Ｔ3, ｄ2, ｄ3, ｄ4, ｍ）に依存した、メンバ証明書に含まれるａｘの平方剰余群ＱＲ（ｎ）上の離散対数ｘの知識の署名(signature of knowledge)[CS97][Sch91]に他ならない。
【００４２】
[CS97]  J. Camenisch, M. Stadler, “Efficient group signature schemes for large groups”, CRYPT’ 97, LNCS 1269, PP.410-424, 1997.
[Sch91]  C. P. Schnorr, “Efficient Signature generation by smart cards”, Journal of Cryptology, 4(3), pp. 161-174, 1991.
実際、匿名プロキシＡＰはグループメンバMemから送られる(ｃ’, ｓ2’)に対して下式が成り立つことを検証することにより、この知識の署名の正当性を検証可能である。
【数３】
2006203827.tif 000005
【００４３】
この知識の署名のもととなるプロトコルは、強ＲＳＡ仮定の下で統計的零知識であることが証明可能である（非特許文献２参照）。これより、ランダムオラクルモデルの下で匿名プロキシＡＰがグループ署名を偽造することが困難であることを証明可能である。
【００４４】
（５．計算効率）
グループ署名生成計算における非特許文献２方式でのグループメンバのべき指数ビット数と、特許文献１方式及び本発明方式での算出情報及び情報の授受回数（往復回数）の比較を図８に示す。また、グループメンバMem、匿名プロキシＡＰのべき指数ビット数の比較を図９に示す。ここで、セキュリティパラメータは｜Ｌp｜＝５１２、｜ｋ｜＝１６０、ε＝５／４とした。
【００４５】
特許文献１方式及び本発明方式は、非特許文献２方式に比べ、グループメンバMemの算出情報及び計算量が著しく少なくなっている。これに加え、本発明方式は、特許文献１方式に比べ、グループメンバMemと匿名プロキシＡＰとの間の情報の授受回数が往復１回分だけ低減されている。
【００４６】
このように、本発明方式によれば、グループメンバMemの計算量を１／１０以下に軽減でき、且つ情報の授受回数を１回分だけ低減させることができる。
【００４７】
（付言）
以上の概要説明では、匿名プロキシＡＰを介してグループ署名を生成するモデルを述べたが、これに限らず、図１０に示すように、匿名プロキシＡＰをグループ署名のサブルーチンとして用いるモデルにも対応可能である。このモデルでは、前述同様に、匿名プロキシＡＰにメッセージｍを知られること無く、グループ署名σを生成可能である。このモデルは、署名生成プロトコルにおいて、最後に（ｓ1, ｓ3, ｓ4）を匿名プロキシＡＰからグループメンバMemへ返送するだけで実現できる。
【００４８】
また、図１１に示すように、グループ管理者ＧＭ、グループメンバMem、匿名プロキシＡＰ及び検証者Veriがリング状に接続されるモデルにも対応可能である。後述する各実施形態は、この図１１に示すモデルに対応している。
【００４９】
また、上記説明では、グループ署名生成計算についてのみ匿名プロキシＡＰを用いる手法を述べたが、参加プロトコルについても、グループ管理者ＧＭ、グループメンバMem、匿名プロキシＡＰの三者間プロトコルにより、無罪の証明能力（exculpability；エクスカルパビリティ）を満たし、且つグループ署名の計算量を軽減することが可能である。ここで、「無罪の証明能力」とは、グループ管理者ＧＭがグループメンバMemになりすまして検証に成功するグループ署名を生成することが困難なことを意味している。
【００５０】
応用としては、第３の実施形態で述べるが、匿名プロキシＡＰを耐タンパ化された（ソフトウエア）モジュールとすることにより、このモジュールがインストールされた任意のＰＣ（personal computer）、例えばネットカフェのＰＣなどでもメンバ秘密鍵を保存したスマートカードさえあれば、グループ署名の生成が可能となる。但し、耐タンパ化モジュールとスマートカード間は、別機構により、安全な通信路を確保する必要がある。
【００５１】
他の応用としては、第２の実施形態で述べるが、携帯キャリアの用意する匿名プロキシサーバにより、携帯電話によるグループ署名の生成も可能となる。この際、匿名プロキシサーバは、グループメンバMem情報を参照及び管理する必要がなく、簡易なサーバ構成で実現可能である。
【００５２】
以上が本発明の各実施形態に共通したグループ署名方式の概要である。続いて、本発明の各実施形態を述べる。なお、各実施形態においては、グループメンバMemがメンバ署名生成装置１０に対応し、匿名プロキシＡＰがグループ署名生成装置２０に対応する。また、グループ管理者ＧＭはグループ署名管理装置３１に対応し、検証者Veriはグループ署名検証装置４２に対応する。
【００５３】
（第１の実施形態）
図１は本発明の第１の実施形態に係るグループ署名生成システムの構成を示す模式図である。このグループ署名生成システムは、メンバ署名生成装置１０及びグループ署名生成装置２０を備えている。なお、各装置１０，２０は、それぞれコンピュータにより実現される場合、各装置１０，２０の機能をコンピュータに実現させるためのプログラムが予め記憶媒体又はネットワークからインストールされている。これは以下の各実施形態でも同様である。
【００５４】
ここで、メンバ署名生成装置１０は、メンバ情報管理部１１及びメンバ署名生成部１２を備えている。
【００５５】
メンバ情報管理部１１は、メンバ証明書cert及びメンバ秘密鍵ｘなどが記憶されるハードウェア資源としての記憶装置であり、メンバ署名生成部１２から読出／書込可能となっている。
【００５６】
メンバ署名生成部１２は、証明書出力部１３及びσ”算出部１４を備えている。
【００５７】
証明書出力部１３は、外部からメッセージｍ及びグループ公開鍵ｐｋを入力するための機能と、このメッセージｍに対するグループ署名を生成するとき、メンバ情報管理部１１内のメンバ証明書cert及び入力されたグループ公開鍵ｐｋをグループ署名生成装置２０に送信する機能とをもっている。
【００５８】
σ”算出部１４は、グループ署名生成装置２０から証明書関連情報（Ｔ1，Ｔ2，Ｔ3）及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）を受けると、この証明書関連情報、演算パラメータ、メッセージｍ及びメンバ秘密鍵ｘに基づいて、メンバ署名σ”＝（ｃ，ｓ2）を生成する機能と、このメンバ署名σ”をグループ署名生成装置２０に送信する機能とをもっている。
【００５９】
グループ署名生成装置２０は、ハードウェア資源としてのメモリ（図示せず）と、このメモリに読出／書込可能なグループ署名生成部２１とを備えている。グループ署名生成部２１は、σ’算出部２２及びσ算出部２３を備えている。
【００６０】
σ’算出部２２は、メンバ署名生成装置１０からメンバ証明書cert及びグループ公開鍵ｐｋを受けると、このメンバ証明書cert及びグループ公開鍵ｐｋをメモリ（図示せず）に書き込む機能と、メモリ内のメンバ証明書cert及びグループ公開鍵ｐｋに基づいて証明書関連情報（Ｔ1，Ｔ2，Ｔ3）及び演算パラメータ（ｄ1’，ｄ2，ｄ3，ｄ4）を生成する機能と、この証明書関連情報及び演算パラメータからなる情報σ’=（Ｔ1，Ｔ2，Ｔ3，ｄ1’，ｄ2，ｄ3，ｄ4）をメンバ署名生成装置１０に送信する機能とをもっている。なお、グループ署名生成装置２０は、予めグループ公開鍵ｐｋをメモリ（図示せず）に記憶していてもよく、この場合、メンバ署名生成装置１０によるグループ公開鍵ｐｋの送信が省略される。
【００６１】
σ算出部２３は、メンバ署名生成装置１０からメンバ署名σ”＝（ｃ，ｓ2）を受けると、このメンバ署名σ”をメモリ（図示せず）に書き込む機能と、メモリ内のメンバ署名σ”及びメンバ証明書certに基づいて、メンバ署名関連情報（ｓ1，ｓ3，ｓ4）を生成する機能と、このメンバ署名関連情報、証明書関連情報及びメンバ署名からなるグループ署名σ＝（Ｔ1，Ｔ2，Ｔ3，ｓ1，ｓ2，ｓ3，ｓ4，ｃ）を生成する機能と、このグループ署名を出力する機能とをもっている。
【００６２】
次に、以上のように構成されたグループ署名生成システムによるグループ署名生成方法を図２のフローチャートを用いて説明する。  
なお、グループ署名方式における、グループ公開鍵ｐｋ及びグループ秘密鍵ｓｋの生成、グループメンバ署名生成鍵ｘの生成、メンバ証明書certの発行、検証処理Verify及び開示処理Openは非特許文献２と同様に実行されるものとする。これは以下の各実施形態でも同様である。  
よって、図示しないグループ管理者ＧＭにより、グループ公開鍵ｐｋ＝（ｎ, ａ, ａ0, ｙ, ｇ, ｈ）が公開される。  
また、メンバ署名生成装置１０内のメンバ情報管理部１１にメンバ署名生成鍵ｘ及びメンバ証明書cert＝（Ａ, ｅ）が保管される。
【００６３】
ここで、Ｌp，ｋ，ε＞１はセキュリティパラメータであり、λ1，λ2，γ1，γ2はそれぞれ以下を満たすパラメータである: λ1 ＞ ε(λ2＋ｋ)＋２，λ2 ＞ ４Ｌp，γ1 ＞ ε(γ2＋ｋ)＋２，γ2 ＞ λ1＋２．
また、Λ，Γは以下を満たす範囲である:
【数４】
2006203827.tif 000006
【００６４】
ｎ＝ｐｑ，  ｐ＝２ｐ’＋１，  ｑ＝２ｑ’＋１（但し、ｐ’とｑ’はＬpビットの素数）はグループ管理者にランダムに選択される。
【００６５】
ａ ∈ ＱＲ（ｎ），ａ0 ∈ ＱＲ（ｎ），ｇ ∈ ＱＲ（ｎ），ｈ ∈ ＱＲ（ｎ）も同様にグループ管理者にランダムに選択される（但し、ＱＲ（ｎ）は、ｎの平方剰余群）。
【００６６】
また、グループ管理者は以下のｙ，Ａの計算を行う。
【数５】
2006203827.tif 000007
【００６７】
以上により、立ち上げ処理が終了する。
【００６８】
続いて、メンバ署名生成装置１０及びグループ署名生成装置２０は、以下の手順によりグループ署名σを生成する。
【００６９】
ステップＳＴ１：  
メンバ署名生成装置１０においては、証明書出力部１３が、外部から入力された署名対象のメッセージｍとグループ公開鍵ｐｋ、及び、メンバ情報管理部１１に保管されているメンバ証明書σをグループ署名生成装置２０内のグループ署名生成部２１へ送信する。
【００７０】
但し、図１ではグループ公開鍵ｐｋは外部から入力されるとしているが、予めメンバ情報管理部１１に保管されていてもよい。
【００７１】
ステップＳＴ２：  
グループ署名生成部２１は、メッセージｍ、グループ公開鍵ｐｋ、メンバ証明書σを受信する。続いて、グループ署名生成部２１は、σ’算出部２２により、以下の手順を実行する。
【数６】
2006203827.tif 000008
【００７２】
ステップＳＴ５：
σ’算出部２２は、得られた情報σ’=（Ｔ1，Ｔ2，Ｔ3，ｄ1’，ｄ2，ｄ3，ｄ4）をメンバ署名生成装置１０内のメンバ署名生成部１２に送信する。
【００７３】
ステップＳＴ６：
メンバ署名生成部１２は、情報σ’を受信する。
【００７４】
続いて、メンバ署名生成部１２は、メンバ情報管理部１１に保管されているメンバ署名生成鍵ｘを用いて以下のステップＳＴ７〜ＳＴ９を実行する。
【数７】
2006203827.tif 000009
【００７５】
ステップＳＴ１０：
メンバ署名σ”=（ｃ，ｓ2）をグループ署名生成装置２０内のグループ署名生成部２１へ送る。
【００７６】
ステップＳＴ１１：
グループ署名生成部２１はメンバ署名σ”＝（ｃ，ｓ2）を受信する。  
続いて、グループ署名生成部２１は以下のステップＳＴ１２及びＳＴ１３を実行する。
【数８】
2006203827.tif 000010
【００７７】
ステップＳＴ１３：
グループ署名σ＝（Ｔ1, Ｔ2, Ｔ3, ｓ1, ｓ2, ｓ3, ｓ4, ｃ）をグループ署名検証者装置（図示せず）に出力する。  
以上の手順により、非特許文献２と同じグループ署名σが生成される。よって、非特許文献２に示されている検証(Verify)アルゴリズムにより同様にグループ署名の正当性が検証可能である。また、グループ署名から署名者を特定する開示(Open)アルゴリズムにより同様に署名者を特定可能である。
【００７８】
上述したように本実施形態によれば、メンバ署名生成装置１０とグループ署名生成装置２０との間において、図１及び図２等に示すように、情報の授受回数を１．５回の往復回数（片道３回）として、グループ署名σを生成することができる。
【００７９】
すなわち、２台の装置１０，２０間で情報を授受しながらグループ署名生成の計算を行う際に、従来よりも１往復（特許文献１の図９のＳＴ３６，ＳＴ３７）分だけ、両装置間の情報の授受回数を低減できる。
【００８０】
また、以上の手順においてメンバ署名生成装置１０内で行われる計算は、主にｄ1，ｃ，ｓ2の計算のみであり、適切なパラメータの下で、ｄ1，ｃ，ｓ2の計算量は全てのグループ署名生成計算の１０分の１以下である。
【００８１】
よって、メンバ署名生成装置１０を計算能力の低いデバイス内に配置し、グループ署名生成装置２０を計算能力の高いデバイス内に配置することにより、全てのグループ署名生成計算を計算能力の低いデバイス内で行う場合に比べ、計算能力の低いデバイス内での計算量を大幅に軽減することができる。
【００８２】
また、メンバ署名生成鍵ｘに関する情報がグループ署名生成装置２０に一切漏れない。このため、仮にグループ署名生成装置２０によるグループ署名の偽造を心配したとしても、グループ署名生成装置２０がメンバ署名生成装置１０と通信を行うことなく、上記手順により生成されたグループ署名以外のグループ署名を偽造することが数学的に困難な問題と同等に困難であることが証明できる。但し、メンバ署名生成装置１０とグループ署名生成装置２０の間の通信は、図示しない方法により確立された安全な通信路を用いて行われることが望ましい。
【００８３】
さらに、本実施形態では、メッセージｍがグループ署名生成装置２０に一切漏れない。このため、メッセージｍを変えて何度もグループ署名を生成させた際のデータの変化を解析するといった、いわゆるリプレイ攻撃が不可能となっている。
【００８４】
（第２の実施形態）
図３は本発明の第２の実施形態に係るグループ署名生成システムを携帯電話の認証システムに適用した構成を示す模式図であり、図１と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した説明を省略する。
【００８５】
すなわち、本実施形態は、第１の実施形態を携帯電話に適用した例であり、グループ管理者ＧＭとしてのグループ署名管理装置３１を備えた携帯電話会社３０と、図１に示したメンバ署名生成装置１０を備えた携帯電話装置１７と、図１に示したグループ署名生成装置２０を備えたゲートウェイサーバ２５と、検証者Veriとしてのグループ署名検証装置４２を備えた検証システム４０とから構成されている。
【００８６】
携帯電話装置１７、ゲートウェイサーバ２５、検証システム４０はそれぞれ通信制御装置１６，２４，４１を備えており、携帯電話装置１７と検証システム４０間の通信は、常にゲートウェイサーバ２５を介して行われる。
【００８７】
携帯電話装置１７は、前述したメンバ署名生成装置１０及び通信制御装置１６に加え、メンバ署名鍵生成装置１６を備えている。
【００８８】
メンバ署名鍵生成装置１６は、メンバ署名生成鍵ｘを生成する機能と、グループ参加要求をグループ署名管理装置３１に送信する機能と、グループ署名管理装置３１から受けたメンバ証明書cert及びグループ公開鍵ｐｋをメンバ署名生成装置１０に送出する機能とをもっている。
【００８９】
検証システム４０は、通信制御装置４１により、メッセージｍをゲートウェイサーバ２５を介して携帯電話装置１７に送信し、ゲートウェイサーバ２５から出力されたグループ署名を受けると、このグループ署名σをグループ署名検証装置４２に送出する機能をもっている。
【００９０】
グループ署名検証装置４２は、公開されているグループ公開鍵ｐｋに基づいて、通信制御装置４１から受けたグループ署名σの正当性を検証する機能をもっている。
【００９１】
次に、以上のように構成されたグループ署名生成システムを備えた認証システムの動作を図４のシーケンス図を用いて説明する。
【００９２】
（前提）
始めに、前提条件として、携帯電話会社３０は、グループ署名管理装置３１によりグループ公開鍵ｐｋ及びグループ秘密鍵ｐｋの生成を行い、グループ公開鍵ｐｋを公開しているとする。
【００９３】
携帯電話装置１７は、予めメンバ署名鍵生成装置１６によりメンバ署名生成鍵ｘを生成し、携帯電話会社３０のグループ管理装置３１に対してグループ参加要求を送信する。
【００９４】
これに対し、グループ署名管理装置３１はメンバ署名生成鍵ｘに対するメンバ証明書certを発行し、携帯電話装置１７へ送信する。
【００９５】
携帯電話装置１７は、生成したメンバ署名生成鍵ｘと受信したメンバ証明書cert及び公開されているグループ公開鍵ｐｋを、メンバ署名生成装置１０内のメンバ情報管理部１１へ保管する。
【００９６】
これらの携帯電話会社３０と携帯電話装置１７の間の通信は、図にはない方法により確立された安全な通信路を用いて行われることが望ましい。また、グループ公開鍵ｐｋは、メンバ署名生成装置１０実行毎に、図にはない手段により携帯電話装置１７外部からメンバ署名生成装置１０に入力されても良い。
【００９７】
続いて、検証システム４０が携帯電話装置１７がグループのメンバのものであることを認証する手順について述べる。
【００９８】
（署名生成及び認証）
検証システム４０は、認証する携帯電話装置１７に対して、認証のチャレンジとなるメッセージｍを送信する（ＳＴ２１）。このメッセージｍは、乱数や時間情報などの一意に定まる値であることが望ましい。メッセージｍは、ゲートウェイサーバ２５を介して携帯電話装置１７の通信制御装置１６に受信される（ＳＴ２２）。
【００９９】
携帯電話装置１７の通信制御装置１６は、このメッセージｍをメンバ署名生成装置１０へ入力し、グループ署名の生成を開始させる。
【０１００】
メンバ署名生成装置１０は、ゲートウェイサーバ２５内のグループ署名生成装置２０との間で第１の実施形態による手順を実行する（ＳＴ２３〜ＳＴ２５）。
【０１０１】
その結果、グループ署名生成装置２０は、得られたグループ署名σをゲートウェイサーバ２５内の通信制御装置２４に出力する。通信制御装置２４は、このグループ署名σをメッセージｍに対するグループ署名σとして、検証システム４０へ送り返す（ＳＴ２６）。なお、図３ではメンバ署名生成装置１０とグループ署名生成装置２０が直接通信を行っているが、それぞれ携帯電話装置１７の通信制御装置１６とゲートウェイサーバ２５の通信制御装置２４を介して通信を行っても良い。
【０１０２】
検証システム４０は、グループ署名σを受信すると、グループ署名検証装置４２により、公開されているグループ公開鍵ｐｋを用いてグループ署名σがメッセージmに対するグループ署名であるかを検証する（ＳＴ２７）。
【０１０３】
検証に成功した場合、検証システム４０は、携帯電話装置１７がメンバ署名生成鍵ｘ及びメンバ証明書certを保持していること、すなわち携帯電話装置１７がグループのメンバのものであることを認証できる。
【０１０４】
上述したように本実施形態によれば、第１の実施形態のメンバ署名生成装置１０を携帯電話装置１７に有し、グループ署名生成装置２０をゲートウェイサーバ２５に備えた構成としても、第１の実施形態と同様に、両装置１０，２０間での情報の授受回数を低減させることができる（ＳＴ２３〜ＳＴ２５の往復１．５回）。
【０１０５】
また、グループ署名を生成する際、携帯電話装置１７内ではメンバ署名生成装置１０によるｄ1’，ｃ，ｓ2の生成が実行可能であればよく、携帯電話の計算能力が低い場合でも実用的な時間でグループ署名の生成が可能となる。
【０１０６】
（第３の実施形態）
図５は本発明の第３の実施形態に係るグループ署名生成システムをスマートカードの認証システムに適用した構成を示す模式図である。
【０１０７】
本実施形態は、第１の実施形態をスマートカードに適用した例であり、図１に示したメンバ署名生成装置１０を備えたスマートカード装置１９と、図１に示したグループ署名生成装置２０を備えた操作端末としてのＰＣ（パーソナルコンピュータ）装置２７と、検証者Veriとしてのグループ署名検証装置４２を備えた検証システム４０ａとから構成されている。これに伴い、ＰＣ装置２７は、スマートカード装置１９を着脱自在に保持し且つこのスマートカード装置１９に読出／書込するための図示しないカードリーダライタを備えている。
【０１０８】
ここで、ＰＣ装置２７、スマートカード装置１９、検証システム４０ａはそれぞれ通信制御装置２６，１８，４１ａを備えている。なお、検証システム４０ａ及び通信制御装置４１ａ等における添字ａは、前述した携帯電話との間の通信方式とは異なり、ＰＣ及びスマートカードとの間との通信方式に対応する旨を表している。
【０１０９】
スマートカード装置１９内のメンバ署名生成装置１０は、予めメンバ署名生成鍵ｘ，メンバ証明書cert，グループ公開鍵ｐｋが保管されているとする。
【０１１０】
ＰＣ装置２７内のグループ署名生成装置２０は、例えばソフトウェアでもよく、その場合このソフトウェアが不正に改変されたりデータを搾取されないよう耐タンパ化されていることが望ましい。
【０１１１】
次に、以上のように構成されたグループ署名生成システムが適用された認証システムの動作を図６のシーケンス図を用いて説明する。具体的には、検証システム４０ａがスマートカード装置１９がグループのメンバのものであることを認証する手順について述べる。
【０１１２】
検証システム４０ａは、認証するスマートカード装置１９に対して、認証のチャレンジとなるメッセージｍを送信する（ＳＴ２１ａ）。このメッセージｍは、ＰＣ装置２７の通信制御装置２６を介してスマートカード装置１９の通信制御装置に受信される（ＳＴ２２ａ）。
【０１１３】
スマートカード装置１９の通信制御装置１８は、このメッセージｍをメンバ署名生成装置１０へ入力し、グループ署名の生成を開始させる。
【０１１４】
メンバ署名生成装置１０は、ＰＣ装置２７内のグループ署名生成装置２０との間で第１の実施形態による手順を実行する（ＳＴ２３ａ〜ＳＴ２５ａ）。
【０１１５】
その結果、グループ署名生成装置２０は、得られたグループ署名σをＰＣ装置２７内の通信制御装置２６に出力する。通信制御装置２６は、このグループ署名σをメッセージｍに対するグループ署名として、検証システム４０ａへ送り返す（ＳＴ２６ａ）。
【０１１６】
以下、第２の実施形態と同様にグループ署名検証装置４２がグループ署名σの正当性を検証する。これにより、グループ署名検証装置は４２ａは、スマートカード装置１９がメンバ署名生成鍵ｘ及びメンバ証明書certを保持していること、つまりグループのメンバのものであることを認証できる。
【０１１７】
上述したように本実施形態によれば、第１の実施形態のメンバ署名生成装置１０をスマートカード装置１９に有し、グループ署名生成装置２０をＰＣ装置２７に備えた構成としても、第１の実施形態と同様に、両装置１０，２０間での情報の授受回数を低減させることができる（ＳＴ２３ａ〜ＳＴ２５ａの往復１．５回）。
【０１１８】
また、グループ署名を生成する際、スマートカード装置１９内ではメンバ署名生成装置１０によるｄ1’，ｃ，ｓ2の生成が実行可能であればよく、スマートカードの計算能力が低い場合でも実用的な時間でグループ署名の生成が可能となる。
【０１１９】
（第４の実施形態）
本実施形態では、非特許文献２方式以外の従来知られているグループ署名方式について、前述同様の改良により、本発明方式を適用する場合について述べる。
【０１２０】
始めに、従来知られている効率的なグループ署名方式（例えば、［ＢＭＷ０３］［ＣＳ９７］）は、非特許文献２方式と同様に、メンバ証明書型のグループ署名方式である。
【０１２１】
[BMW03] M.Bellare, D.Micciancio, B.Warinschi, “Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions”, EUROCRYPT 2003, LNCS 2656, pp.614-629, 2003.
[CS97] J.Camenisch, M.Stadler, “Efficient group signature schemes for large groups”, CRYPTO'97, LNCS 1269, pp.410-424, 1997.
メンバ証明書型グループ署名方式の一般的なアルゴリズムは以下の通りである。  
（立ち上げ処理；Set up）  グループ管理者は、署名方式（Sign，Vrfy）に対応する公開鍵ペア（ｐｋg，ｓｋg）と、公開鍵暗号方式（Ｅｎｃ，Ｄｅｃ）に対応する公開鍵ペア（ｐｋe，ｓｋe）を生成し、グループ公開鍵ｐｋ＝（ｐｋg，ｐｋe）とし、グループ秘密鍵ｓｋ＝（ｓｋg，ｓｋe）とする。
【０１２２】
（参加プロトコル；Join protocol）  ユーザは公開鍵ペア（ｐｋu，ｓｋu）を生成し、ｐｋuに対するｓｋuを知っていることをグループ管理者に対して証明する。そして、ユーザは、メンバ秘密鍵をｓｋuとする。
【０１２３】
一方、グループ管理者は、ｐｋuの正当性を検証した後、メンバ証明書certu＝Signskg（ｐｋu）を生成し、グループメンバへ送信する。また、グループ管理者は、ｐｋuとユーザ情報のペアを秘密に保管する。
【０１２４】
（署名処理；Sign）  ユーザは、メンバ秘密鍵を用いてメッセージｍに対する署名Ｓ＝Signsk_u（ｍ）を生成する。次に、ユーザは、メンバ秘密鍵ｓｋuに対応する公開鍵ｐｋuとメンバ証明書certuをグループ公開鍵ｐｋeにより暗号化した値Ｃ＝Encpk_e（ｐｋu，certu）を計算する。そして、以下が成り立つことをメンバ秘密鍵ｓｋuとメンバ証明書certuに対する非対話零知識証明（ＮＩＺＫ）によって証明する。
【０１２５】
１．Vrfypk_u（ｍ，Ｓ）＝１，
２．Vrfypk_g（ｐｋu，certu）＝１，
３．Ｃ＝Encpk_e（ｐｋu，certu）．
そして、非対話零知識証明ＮＩＺＫにより得られた証明（proof；プルーフ）と暗号文Ｃをグループ署名とする。
【０１２６】
（検証処理；Verify）  検証者は、証明（proof）の正当性を検証する。
【０１２７】
（開示処理；Open）  グループ管理者は、グループ秘密鍵ｓｋeを用いて暗号文Ｃを復号することにより、メンバ秘密鍵ｓｋu，メンバ証明書certuを得る。これより、メンバ情報を特定する。
【０１２８】
以上がメンバ証明型グループ署名方式の一般的なアルゴリズムである。
【０１２９】
続いて、本発明の第４の実施形態に係るグループ署名生成システムについて説明する。  本実施形態は、第１の実施形態の変形例であり、本発明方式を非特許文献２方式以外の方式に適用した構成により、一般化を図るものである。
【０１３０】
具体的には、署名生成における非対話零知識証明ＮＩＺＫにおいて、メンバ秘密鍵ｓｋuの知識が必要な証明は最初のメッセージｍに対する署名の正当性証明のみであり、残りの２つはメンバ公開鍵ｐｋuとメンバ証明書certuのみの知識で可能であることを利用している。
【０１３１】
すなわち、本実施形態は、非対話零知識証明ＮＩＺＫにおいて、最初のメッセージｍに対する署名の正当性証明をグループメンバが計算し、残りの２つの証明を匿名プロキシが計算する構成となっている。
【０１３２】
以上のように非対話零知識証明ＮＩＺＫを分離した構成により、任意のメンバ証明型グループ署名を本発明方式に適用でき、グループメンバの計算量を低減させることができる。
【０１３３】
なお、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１３４】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１３５】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１３６】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１３７】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１３８】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１３９】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１４０】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１４１】
【図１】本発明の第１の実施形態に係るグループ署名生成システムの構成を示すブロック図である。
【図２】同実施形態におけるグループ署名生成方法を説明するためのフローチャートである。
【図３】本発明の第２の実施形態に係るグループ署名生成システムを携帯電話の認証システムに適用した構成を示す模式図である。
【図４】同実施形態における動作を説明するためのシーケンス図である。
【図５】本発明の第３の実施形態に係るグループ署名生成システムをスマートカードの認証システムに適用した構成を示す模式図である。
【図６】同実施形態における動作を説明するためのシーケンス図である。
【図７】本発明方式の一例を説明するためのモデルを示す模式図である。
【図８】本発明方式における情報の授受回数（往復回数）などを非特許文献２方式及び特許文献１方式と比較して示す図である。
【図９】本発明方式における計算量を非特許文献２方式及び特許文献１方式と比較して示す図である。
【図１０】本発明方式の他の例を説明するためのモデルを示す模式図である。
【図１１】本発明方式の更に他の例を説明するためのモデルを示す模式図である。
【符号の説明】
【０１４２】
１０…メンバ署名生成装置、１１…メンバ情報管理部、１２…メンバ署名生成部、１３…証明書出力部、１４…σ”算出部、１５…メンバ署名鍵生成装置、１６，２４，２６，４１，４１ａ…通信制御装置、１７…携帯電話装置、２０…グループ署名生成装置、２１…グループ署名生成部、２２…σ’算出部、２３…σ算出部、２５…ゲートウェイサーバ、２７…ＰＣ装置、３０…携帯電話会社、３１…グループ署名管理装置、４０，４０ａ…検証システム、４２…グループ署名検証装置。
【図１】
2006203827.tif 000011
【図２】
2006203827.tif 000012
【図３】
2006203827.tif 000013
【図４】
2006203827.tif 000014
【図５】
2006203827.tif 000015
【図６】
2006203827.tif 000016
【図７】
2006203827.tif 000017
【図８】
2006203827.tif 000018
【図９】
2006203827.tif 000019
【図１０】
2006203827.tif 000020
【図１１】
2006203827.tif 000021