(57)【特許請求の範囲】
【請求項１】
Ｎ台の署名生成装置、署名検証装置、追跡装置を備えるグループ署名システムであって、
ｐとｑを互いに素の正の整数、ｎとｋを正の整数、Ｚｑを−ｑ／２より大きくｑ／２以下の整数からなる整数環、Ｚｑ［Ｘ］を整数環Ｚｑの元を係数とするＸの多項式全体の集合、ｆ（Ｘ）を整数環Ｚｑの元を係数とするｎ次モニック既約多項式、Ｒを多項式集合Ｚｑ［Ｘ］のｆ（Ｘ）を法とした剰余環上の多項式全体からなる集合、集合Ｒの元同士の演算は前記剰余環上の演算、ｔを正の整数、ＣをＲの部分集合、Ｃｔをｔ個の集合Ｃの元からなるベクトルを示す記号、‖‖∞を集合Ｒの元である多項式の係数の中で絶対値が最大の係数の絶対値を示す記号、γを正の整数、Ｂ（γ）をすべての係数の絶対値がγ以下の集合Ｒ中の多項式の集合、Ｒｖ×ｗを（ｖ×ｗ）個の集合Ｒの元からなるｖ行ｗ列の行列を示す記号（ただしｖとｗは正の整数）、βをｑ１／ｋ以上の正の整数、ＧをＧ＝［１，β，β２，…，βｋ−１］であるベクトル、δＮＴＲＵとδＴＥＸＴをｑ／２以下の正の整数、Ｂ∞をｑ／２以下の正の整数、Ｍを正の数、｛０，１｝＊を“０”と“１”からなる任意のビット長のビット列、Ｈを正の整数をＢ（δＴＥＸＴ）の元に変換するハッシュ関数、Ｈ２を（｛０，１｝＊，Ｒｋ×１，Ｒｋ×１，Ｒ１×１，Ｒ（３Ｋ＋２）×１，…，Ｒ（３Ｋ＋２）×１）をＣｔに変換するハッシュ関数（ただしＲ（３Ｋ＋２）×１の数はｔ個）、｜を行ベクトル同士の要素を同じ行に並べることを示す記号、；を列ベクトル同士の要素を同じ列に並べることを示す記号、Ｉｋを要素が集合Ｒの元であるｋ行ｋ列の単位行列、Ｄμ，εθをθ個の多項式を要素とするベクトルを出力する分布であって中心ベクトルμで標準偏差εの分布を示す記号、Ｄεを１個の多項式を出力する中心ベクトルがゼロベクトルの分布Ｄμ，εθを示す記号、ＦＤμ，εθを分布Ｄμ，εθの確率密度関数、ＤｓとＤαをあらかじめ定めた分布とし、
ａは集合Ｒからランダムに選ばれた多項式、Ａは集合Ｒからランダムに選ばれたｋ個の多項式からなる行ベクトル、Ｔは集合Ｂ（β）からランダムに選ばれた（ｋ×ｋ）個の多項式からなるｋ行ｋ列の行列、ｕは集合Ｒからランダムに選ばれた多項式、ＢはＢ＝Ａ・Ｔにより得られるｋ個の多項式からなる行ベクトルとし、
ｆは集合Ｂ（δＮＴＲＵ）からランダムに選ばれた多項式、ｇは（ｍｏｄ  ｑ）および（ｍｏｄ  ｐ）で逆元を持つ集合Ｂ（δＮＴＲＵ）からランダムに選ばれた多項式、ｈはｈ＝ｆ／ｇにより得られる多項式とし、
ｉ＝１，…，Ｎについて、ｍｉはｍｉ＝Ｈ（ｉ）により得られる多項式、Ｓｉ，１とＳｉ，２は［Ａ｜（Ｂ＋ｍｉＧ）］・［Ｓｉ，１；Ｓｉ，２］＝ｕとなる集合Ｒからｋ個の多項式からなる列ベクトルとし、
グループ公開鍵ｇｐｋをＡ，Ｂ，ｕ，ｈ，ａの組、ｉ番目の前記署名生成装置に対する秘密鍵ｇｓｋｉをＳｉ，１，Ｓｉ，２，ｍｉの組、追跡鍵ｇｏｋをｇ、μを｛０，１｝＊であるメッセージとし、
ｉ番目の前記署名生成装置は、
グループ公開鍵ｇｐｋ、秘密鍵ｇｓｋｉ、メッセージμを入力とし、
ｒ２，ｅ２，ｒ３，ｅ３をｋ個の多項式からなる列ベクトル、ｒ４，ｅ４を多項式とし、
集合Ｒから分布Ｄｓにしたがって多項式を選ぶことでｒ２，ｅ２，ｒ３，ｅ３，ｒ４，ｅ４を生成し、
Ｃ２＝ｐ（ａｒ２＋ｅ２）＋Ｓｉ，２
Ｃ３＝ｐ（ａｒ３＋ｅ３）＋ｍｉＳｉ，２
Ｃ４＝ｐ（ｈｒ４＋ｅ４）＋ｍｉ
のように初期コミットＣ２，Ｃ３，Ｃ４を生成する初期コミット生成部と、
行列Ｚを
【数１３】
0006386963.tif 000014
のように求め、
ｒ３−＝ｒ３−ｍｉｒ２
ｅ３−＝ｅ３−ｍｉｅ２
を求め、
列ベクトルΣを、Σ＝［ｒ２；ｅ２；ｒ３；ｅ３；ｒ４；ｅ４；ｒ３−；ｅ３−；Ｓｉ，１；Ｓｉ，２；ｍｉＳｉ，２；ｍｉ］のように求める署名事前準備部と、
コミットＷ１，…，Ｗｔ、レスポンスＶ１，…，Ｖｔを求める非対話証明生成部と、
前記非対話証明生成部が求めたレスポンスＶ１，…，Ｖｔにエラーを示すレスポンスが含まれていた場合は前記非対話証明生成部の処理を繰り返させ、レスポンスＶ１，…，Ｖｔにエラーを示すレスポンスが含まれていない場合はＣ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ，Ｖ１，…，Ｖｔの組を署名σとして出力する最終処理部と、
を備え、
前記非対話証明生成部は、
Ｙｊを（９ｋ＋３）個の多項式からなる列ベクトルとし、
ｊ＝１，…，ｔについて、集合Ｒから分布Ｄαにしたがって（９ｋ＋３）個の多項式を選ぶことでＹｊを生成し、Ｗｊ＝ＺＹｊを計算して（３ｋ＋２）個の多項式からなる列ベクトルであるコミットＷｊを求めるコミット生成部と、
チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める検証チャレンジ生成部と、
ｊ＝１，…，ｔについて、Ｖｊ＝Σｃｊ＋ＹｊのようにレスポンスＶｊを求め、
【数１４】
0006386963.tif 000015
の確率で、レスポンスＶｊをエラーを示すデータに書き換えるレスポンス生成部と、
を有し、
前記署名検証装置は、
グループ公開鍵ｇｐｋ、メッセージμ、署名σを入力とし、
行列Ｚを
【数１５】
0006386963.tif 000016
のように、列ベクトルτをτ＝［Ｃ２；Ｃ３；Ｃ４；Ｃ３；ｕ］のように求める検証事前準備部と、
チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める検証チャレンジ再生成部と、
ｊ＝１，…，ｔについて、ＺＶｊ＝ｔｃｊ＋Ｗｊかつ‖Ｖｊ‖∞≦Ｂ∞が成り立つことを確認し、すべて成り立つときは署名σが正当であることを示す情報を出力し、成り立たないものがあるときは署名σが正当ではないことを示す情報を出力する検証メイン部と、
を備え、
前記追跡装置は、
グループ公開鍵ｇｐｋ、追跡鍵ｇｏｋ、メッセージμ、署名σを入力とし、
署名σが正当かを確認する正当性確認部と、
ｍ＝（（ｇＣ４  ｍｏｄ  ｑ）ｍｏｄ  ｐ）・（ｇ−１  ｍｏｄ  ｐ）ｍｏｄ  ｐ
のようにｍを求め、
Ｈ（ｉ）＝ｍが成り立つｉが１，…，Ｎの中に存在すれば当該ｉを出力し、存在しなければエラーを示す情報を出力する署名生成者特定部と
を備え、
前記正当性確認部は、
行列Ｚを
【数１６】
0006386963.tif 000017
のように、列ベクトルτをτ＝［Ｃ２；Ｃ３；Ｃ４；Ｃ３；ｕ］のように求める追跡事前準備部と、
チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める追跡チャレンジ再生成部と、
ｊ＝１，…，ｔについて、ＺＶｊ＝ｔｃｊ＋Ｗｊかつ‖Ｖｊ‖∞≦Ｂ∞が成り立つことを確認し、すべて成り立つときは署名σが正当であることを示す情報を出力し、成り立たないものがあるときは署名σが正当ではないことを示す情報を出力する追跡検証部と、
を有する
グループ署名システム。
【請求項２】
請求項１記載のグループ署名システムを構成するＮ台の前記署名生成装置の１つである署名生成装置。
【請求項３】
請求項１記載のグループ署名システムを構成する前記署名検証装置である署名検証装置。
【請求項４】
請求項１記載のグループ署名システムを構成する前記追跡装置である追跡装置。
【請求項５】
Ｎ台の署名生成装置、署名検証装置、追跡装置によって実行されるグループ署名方法であって、
ｐとｑを互いに素の正の整数、ｎとｋを正の整数、Ｚｑを−ｑ／２より大きくｑ／２以下の整数からなる整数環、Ｚｑ［Ｘ］を整数環Ｚｑの元を係数とするＸの多項式全体の集合、ｆ（Ｘ）を整数環Ｚｑの元を係数とするｎ次モニック既約多項式、Ｒを多項式集合Ｚｑ［Ｘ］のｆ（Ｘ）を法とした剰余環上の多項式全体からなる集合、集合Ｒの元同士の演算は前記剰余環上の演算、ｔを正の整数、ＣをＲの部分集合、Ｃｔをｔ個の集合Ｃの元からなるベクトルを示す記号、‖‖∞を集合Ｒの元である多項式の係数の中で絶対値が最大の係数の絶対値を示す記号、γを正の整数、Ｂ（γ）をすべての係数の絶対値がγ以下の集合Ｒ中の多項式の集合、Ｒｖ×ｗを（ｖ×ｗ）個の集合Ｒの元からなるｖ行ｗ列の行列を示す記号（ただしｖとｗは正の整数）、βをｑ１／ｋ以上の正の整数、ＧをＧ＝［１，β，β２，…，βｋ−１］であるベクトル、δＮＴＲＵとδＴＥＸＴをｑ／２以下の正の整数、Ｂ∞をｑ／２以下の正の整数、Ｍを正の数、｛０，１｝＊を“０”と“１”からなる任意のビット長のビット列、Ｈを正の整数をＢ（δＴＥＸＴ）の元に変換するハッシュ関数、Ｈ２を（｛０，１｝＊，Ｒｋ×１，Ｒｋ×１，Ｒ１×１，Ｒ（３Ｋ＋２）×１，…，Ｒ（３Ｋ＋２）×１）をＣｔに変換するハッシュ関数（ただしＲ（３Ｋ＋２）×１の数はｔ個）、｜を行ベクトル同士の要素を同じ行に並べることを示す記号、；を列ベクトル同士の要素を同じ列に並べることを示す記号、Ｉｋを要素が集合Ｒの元であるｋ行ｋ列の単位行列、Ｄμ，εθをθ個の多項式を要素とするベクトルを出力する分布であって中心ベクトルμで標準偏差εの分布を示す記号、Ｄεを１個の多項式を出力する中心ベクトルがゼロベクトルの分布Ｄμ，εθを示す記号、ＦＤμ，εθを分布Ｄμ，εθの確率密度関数、ＤｓとＤαをあらかじめ定めた分布とし、
ａは集合Ｒからランダムに選ばれた多項式、Ａは集合Ｒからランダムに選ばれたｋ個の多項式からなる行ベクトル、Ｔは集合Ｂ（β）からランダムに選ばれた（ｋ×ｋ）個の多項式からなるｋ行ｋ列の行列、ｕは集合Ｒからランダムに選ばれた多項式、ＢはＢ＝Ａ・Ｔにより得られるｋ個の多項式からなる行ベクトルとし、
ｆは集合Ｂ（δＮＴＲＵ）からランダムに選ばれた多項式、ｇは（ｍｏｄ  ｑ）および（ｍｏｄ  ｐ）で逆元を持つ集合Ｂ（δＮＴＲＵ）からランダムに選ばれた多項式、ｈはｈ＝ｆ／ｇにより得られる多項式とし、
ｉ＝１，…，Ｎについて、ｍｉはｍｉ＝Ｈ（ｉ）により得られる多項式、Ｓｉ，１とＳｉ，２は［Ａ｜（Ｂ＋ｍｉＧ）］・［Ｓｉ，１；Ｓｉ，２］＝ｕとなる集合Ｒからｋ個の多項式からなる列ベクトルとし、
グループ公開鍵ｇｐｋをＡ，Ｂ，ｕ，ｈ，ａの組、ｉ番目の前記署名生成装置に対する秘密鍵ｇｓｋｉをＳｉ，１，Ｓｉ，２，ｍｉの組、追跡鍵ｇｏｋをｇ、μを｛０，１｝＊であるメッセージとし、
ｉ番目の前記署名生成装置が、
グループ公開鍵ｇｐｋ、秘密鍵ｇｓｋｉ、メッセージμを入力とし、
ｒ２，ｅ２，ｒ３，ｅ３をｋ個の多項式からなる列ベクトル、ｒ４，ｅ４を多項式とし、
集合Ｒから分布Ｄｓにしたがって多項式を選ぶことでｒ２，ｅ２，ｒ３，ｅ３，ｒ４，ｅ４を生成し、
Ｃ２＝ｐ（ａｒ２＋ｅ２）＋Ｓｉ，２
Ｃ３＝ｐ（ａｒ３＋ｅ３）＋ｍｉＳｉ，２
Ｃ４＝ｐ（ｈｒ４＋ｅ４）＋ｍｉ
のように初期コミットＣ２，Ｃ３，Ｃ４を生成する初期コミット生成ステップと、
行列Ｚを
【数１７】
0006386963.tif 000018
のように求め、
ｒ３−＝ｒ３−ｍｉｒ２
ｅ３−＝ｅ３−ｍｉｅ２
を求め、
列ベクトルΣを、Σ＝［ｒ２；ｅ２；ｒ３；ｅ３；ｒ４；ｅ４；ｒ３−；ｅ３−；Ｓｉ，１；Ｓｉ，２；ｍｉＳｉ，２；ｍｉ］のように求める署名事前準備ステップと、
コミットＷ１，…，Ｗｔ、レスポンスＶ１，…，Ｖｔを求める非対話証明生成ステップと、
前記非対話証明生成ステップが求めたレスポンスＶ１，…，Ｖｔにエラーを示すレスポンスが含まれていた場合は前記非対話証明生成ステップの処理を繰り返させ、レスポンスＶ１，…，Ｖｔにエラーを示すレスポンスが含まれていない場合はＣ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ，Ｖ１，…，Ｖｔの組を署名σとして出力する最終処理ステップと、
を実行し、
前記非対話証明生成ステップは、
Ｙｊを（９ｋ＋３）個の多項式からなる列ベクトルとし、
ｊ＝１，…，ｔについて、集合Ｒから分布Ｄαにしたがって（９ｋ＋３）個の多項式を選ぶことでＹｊを生成し、Ｗｊ＝ＺＹｊを計算して（３ｋ＋２）個の多項式からなる列ベクトルであるコミットＷｊを求めるコミット生成サブステップと、
チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める検証チャレンジ生成サブステップと、
ｊ＝１，…，ｔについて、Ｖｊ＝Σｃｊ＋ＹｊのようにレスポンスＶｊを求め、
【数１８】
0006386963.tif 000019
の確率で、レスポンスＶｊをエラーを示すデータに書き換えるレスポンス生成サブステップと、
を有し、
前記署名検証装置が、
グループ公開鍵ｇｐｋ、メッセージμ、署名σを入力とし、
行列Ｚを
【数１９】
0006386963.tif 000020
のように、列ベクトルτをτ＝［Ｃ２；Ｃ３；Ｃ４；Ｃ３；ｕ］のように求める検証事前準備ステップと、
チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める検証チャレンジ再生成ステップと、
ｊ＝１，…，ｔについて、ＺＶｊ＝ｔｃｊ＋Ｗｊかつ‖Ｖｊ‖∞≦Ｂ∞が成り立つことを確認し、すべて成り立つときは署名σが正当であることを示す情報を出力し、成り立たないものがあるときは署名σが正当ではないことを示す情報を出力する検証メインステップと、
を実行し、
前記追跡装置が、
グループ公開鍵ｇｐｋ、追跡鍵ｇｏｋ、メッセージμ、署名σを入力とし、
署名σが正当かを確認する正当性確認ステップと、
ｍ＝（（ｇＣ４  ｍｏｄ  ｑ）ｍｏｄ  ｐ）・（ｇ−１  ｍｏｄ  ｐ）ｍｏｄ  ｐ
のようにｍを求め、
Ｈ（ｉ）＝ｍが成り立つｉが１，…，Ｎの中に存在すれば当該ｉを出力し、存在しなければエラーを示す情報を出力する署名生成者特定ステップと
を実行し、
前記正当性確認ステップは、
行列Ｚを
【数２０】
0006386963.tif 000021
のように、列ベクトルτをτ＝［Ｃ２；Ｃ３；Ｃ４；Ｃ３；ｕ］のように求める追跡事前準備サブステップと、
チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める追跡チャレンジ再生成サブステップと、
ｊ＝１，…，ｔについて、ＺＶｊ＝ｔｃｊ＋Ｗｊかつ‖Ｖｊ‖∞≦Ｂ∞が成り立つことを確認し、すべて成り立つときは署名σが正当であることを示す情報を出力し、成り立たないものがあるときは署名σが正当ではないことを示す情報を出力する追跡検証サブステップと、
を有する
グループ署名方法。
【請求項６】
請求項２記載の署名生成装置としてコンピュータを機能させるための署名生成プログラム。
【請求項７】
請求項３記載の署名検証装置としてコンピュータを機能させるための署名検証プログラム。
【請求項８】
請求項４記載の追跡装置としてコンピュータを機能させるための追跡プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループ署名方式を実行するためのグループ署名システム、署名生成装置、署名検証装置、追跡装置、グループ署名方法、署名生成プログラム、署名検証プログラム、追跡プログラムに関する。
【背景技術】
【０００２】
グループ署名方式はChaumとvan Heyst（非特許文献１）によって提案された署名方式であり、特徴は、（１）グループのメンバのみが署名を作成できる、（２）検証者は署名が正しいかどうかは分かるが、どのメンバがそれを作成したからは分からない、（３）追跡者は必要があれば署名からどのメンバが作成したかが分かる。その後、非特許文献２〜４に示されたような格子に基づくグループ署名方式が提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Chaum, D., & van Heyst, E., “Group Signatures”, In EUROCRYPT ’91: Advances in Cryptology, pp.257-265, 1991.
【非特許文献２】Gordon, S. D., Katz, J., & Vaikuntanathan, V., “A Group Signature Scheme from Lattice Assumptions”, In M. Abe (Ed.), ASIACRYPT 2010: Advances in Cryptology, pp.395-412, 2010.
【非特許文献３】Laguillaumie, F., Langlois, A., Libert, B., & Stehle D., “Lattice-Based Group Signatures with Logarithmic Signature Size”, In ASIACRYPT 2013: Advances in Cryptology, pp.41-61, 2013.
【非特許文献４】Langlois, A., Ling, S., Nguyen, K., & Wang, H., “Lattice-based Group Signature Scheme with Verifier-local Revocation”, In PKC 2014: Public Key Cryptography, pp.345-361, 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術では公開鍵および署名のサイズはＮの関数に依存する。たとえば、非特許文献２のグループ署名方式では鍵サイズはＮに依存し、非特許文献３および非特許文献４のグループ署名方式では鍵サイズはｌｏｇ（Ｎ）に依存する。
【０００５】
本発明は、グループ公開鍵および署名のサイズがグループメンバ数Ｎに依存しないグループ署名方式を構成することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のグループ署名方式は、少なくともＮ台の署名生成装置、署名検証装置、追跡装置を備える。まず、ｐとｑを互いに素の正の整数、ｎとｋを正の整数、Ｚｑを−ｑ／２より大きくｑ／２以下の整数からなる整数環、Ｚｑ［Ｘ］を整数環Ｚｑの元を係数とするＸの多項式全体の集合、ｆ（Ｘ）を整数環Ｚｑの元を係数とするｎ次モニック既約多項式、Ｒを多項式集合Ｚｑ［Ｘ］のｆ（Ｘ）を法とした剰余環上の多項式全体からなる集合、集合Ｒの元同士の演算は前記剰余環上の演算、ｔを正の整数、ＣをＲの部分集合、Ｃｔをｔ個の集合Ｃの元からなるベクトルを示す記号、‖‖∞を集合Ｒの元である多項式の係数の中で絶対値が最大の係数の絶対値を示す記号、γを正の整数、Ｂ（γ）をすべての係数の絶対値がγ以下の集合Ｒ中の多項式の集合、Ｒｖ×ｗを（ｖ×ｗ）個の集合Ｒの元からなるｖ行ｗ列の行列を示す記号（ただしｖとｗは正の整数）、βをｑ１／ｋ以上の正の整数、ＧをＧ＝［１，β，β２，…，βｋ−１］であるベクトル、δＮＴＲＵとδＴＥＸＴをｑ／２以下の正の整数、Ｂ∞をｑ／２以下の正の整数、Ｍを正の数、｛０，１｝＊を“０”と“１”からなる任意のビット長のビット列、Ｈを正の整数をＢ（δＴＥＸＴ）の元に変換するハッシュ関数、Ｈ２を（｛０，１｝＊，Ｒｋ×１，Ｒｋ×１，Ｒ１×１，Ｒ（３Ｋ＋２）×１，…，Ｒ（３Ｋ＋２）×１）をＣｔに変換するハッシュ関数（ただしＲ（３Ｋ＋２）×１の数はｔ個）、｜を行ベクトル同士の要素を同じ行に並べることを示す記号、；を列ベクトル同士の要素を同じ列に並べることを示す記号、Ｉｋを要素が集合Ｒの元であるｋ行ｋ列の単位行列、Ｄμ，εθをθ個の多項式を要素とするベクトルを出力する分布であって中心ベクトルμで標準偏差εの分布を示す記号、Ｄεを１個の多項式を出力する中心ベクトルがゼロベクトルの分布Ｄμ，εθを示す記号、ＦＤμ，εθを分布Ｄμ，εθの確率密度関数とする。そして、ＤｓとＤαをあらかじめ定めた分布とする。
【０００７】
また、ａは集合Ｒからランダムに選ばれた多項式、Ａは集合Ｒからランダムに選ばれたｋ個の多項式からなる行ベクトル、Ｔは集合Ｂ（β）からランダムに選ばれた（ｋ×ｋ）個の多項式からなるｋ行ｋ列の行列、ｕは集合Ｒからランダムに選ばれた多項式、ＢはＢ＝Ａ・Ｔにより得られるｋ個の多項式からなる行ベクトルとする。ｆは集合Ｂ（δＮＴＲＵ）からランダムに選ばれた多項式、ｇは（ｍｏｄ  ｑ）および（ｍｏｄ  ｐ）で逆元を持つ集合Ｂ（δＮＴＲＵ）からランダムに選ばれた多項式、ｈはｈ＝ｆ／ｇにより得られる多項式とする。さらに、ｉ＝１，…，Ｎについて、ｍｉはｍｉ＝Ｈ（ｉ）により得られる多項式、Ｓｉ，１とＳｉ，２は［Ａ｜（Ｂ＋ｍｉＧ）］・［Ｓｉ，１；Ｓｉ，２］＝ｕとなる集合Ｒから選ばれたｋ個の多項式からなる列ベクトルとする。そして、グループ公開鍵ｇｐｋをＡ，Ｂ，ｕ，ｈ，ａの組、ｉ番目の前記署名生成装置に対する秘密鍵ｇｓｋｉをＳｉ，１，Ｓｉ，２，ｍｉの組、追跡鍵ｇｏｋをｇ、μを｛０，１｝＊であるメッセージとする。
【０００８】
ｉ番目（ｉ＝１，…，Ｎ）の署名生成装置は、グループ公開鍵ｇｐｋ、秘密鍵ｇｓｋｉ、メッセージμを入力とする。ｉ番目（ｉ＝１，…，Ｎ）の署名生成装置は、初期コミット生成部、署名事前準備部、非対話証明生成部、最終処理部を備える。初期コミット生成部は、
（１）集合Ｒから分布Ｄｓにしたがって多項式を選ぶことでｒ２，ｅ２，ｒ３，ｅ３，ｒ４，ｅ４を生成する。なお、ｒ２，ｅ２，ｒ３，ｅ３はｋ個の多項式からなる列ベクトル、ｒ４，ｅ４は多項式である。
（２）初期コミットＣ２，Ｃ３，Ｃ４を、
Ｃ２＝ｐ（ａｒ２＋ｅ２）＋Ｓｉ，２
Ｃ３＝ｐ（ａｒ３＋ｅ３）＋ｍｉＳｉ，２
Ｃ４＝ｐ（ｈｒ４＋ｅ４）＋ｍｉ
のように生成する。署名事前準備部は、行列Ｚを
【０００９】
【数１】
0006386963.tif 000002
【００１０】
のように求め、
ｒ３−＝ｒ３−ｍｉｒ２
ｅ３−＝ｅ３−ｍｉｅ２
を計算し、列ベクトルΣを、Σ＝［ｒ２；ｅ２；ｒ３；ｅ３；ｒ４；ｅ４；ｒ３−；ｅ３−；Ｓｉ，１；Ｓｉ，２；ｍｉＳｉ，２；ｍｉ］のように求める。
【００１１】
非対話証明生成部は、コミット生成部、検証チャレンジ生成部、レスポンス生成部を有し、コミットＷ１，…，Ｗｔ、レスポンスＶ１，…，Ｖｔを求める。コミット生成部は、ｊ＝１，…，ｔについて、集合Ｒから分布Ｄαにしたがって（９ｋ＋３）個の多項式を選ぶことでＹｊを生成し、Ｗｊ＝ＺＹｊを計算して（３ｋ＋２）個の多項式からなる列ベクトルであるコミットＷｊを求める。なお、Ｙｊを（９ｋ＋３）個の多項式からなる列ベクトルである。検証チャレンジ生成部は、チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める。レスポンス生成部は、ｊ＝１，…，ｔについて、Ｖｊ＝Σｃｊ＋ＹｊのようにレスポンスＶｊを求める。そして、
【００１２】
【数２】
0006386963.tif 000003
【００１３】
の確率で、レスポンスＶｊをエラーを示すデータに書き換える。最終処理部は、非対話証明生成部が求めたレスポンスＶ１，…，Ｖｔにエラーを示すレスポンスが含まれていた場合は非対話証明生成部の処理を繰り返させ、レスポンスＶ１，…，Ｖｔにエラーを示すレスポンスが含まれていない場合はＣ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ，Ｖ１，…，Ｖｔの組を署名σとして出力する。
【００１４】
署名検証装置は、グループ公開鍵ｇｐｋ、メッセージμ、署名σを入力とし、検証事前準備部、検証チャレンジ再生成部、検証メイン部を備える。検証事前準備部は、行列Ｚを
【００１５】
【数３】
0006386963.tif 000004
【００１６】
のように、列ベクトルτをτ＝［Ｃ２；Ｃ３；Ｃ４；Ｃ３；ｕ］のように求める。検証チャレンジ再生成部は、チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める。検証メイン部は、ｊ＝１，…，ｔについて、ＺＶｊ＝ｔｃｊ＋Ｗｊかつ‖Ｖｊ‖∞≦Ｂ∞が成り立つことを確認する。検証メイン部は、すべて成り立つときは署名σが正当であることを示す情報を出力し、成り立たないものがあるときは署名σが正当ではないことを示す情報を出力する。
【００１７】
追跡装置は、グループ公開鍵ｇｐｋ、追跡鍵ｇｏｋ、メッセージμ、署名σを入力とし、正当性確認部と署名生成者特定部を備える。正当性確認部は、追跡事前準備部、追跡チャレンジ再生成部、追跡検証部を有し、署名σが正当かを確認する。追跡事前準備部は、行列Ｚを
【００１８】
【数４】
0006386963.tif 000005
【００１９】
のように、列ベクトルτをτ＝［Ｃ２；Ｃ３；Ｃ４；Ｃ３；ｕ］のように求める。追跡チャレンジ再生成部は、チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める。追跡検証部は、ｊ＝１，…，ｔについて、ＺＶｊ＝ｔｃｊ＋Ｗｊかつ‖Ｖｊ‖∞≦Ｂ∞が成り立つことを確認する。追跡検証部は、すべて成り立つときは署名σが正当であることを示す情報を出力し、成り立たないものがあるときは署名σが正当ではないことを示す情報を出力する。署名生成者特定部は、
ｍ＝（（ｇＣ４  ｍｏｄ  ｑ）ｍｏｄ  ｐ）・（ｇ−１  ｍｏｄ  ｐ）ｍｏｄ  ｐ
のようにｍを求める。そして、署名生成者特定部は、Ｈ（ｉ）＝ｍが成り立つｉが１，…，Ｎの中に存在すれば当該ｉを出力し、存在しなければエラーを示す情報を出力する。
【発明の効果】
【００２０】
本発明のグループ署名システムによれば、グループメンバのＩＤ（何番目の署名生成装置であるか）を多項式に直接埋め込むことで、１要素としている。このことにより、グループ公開鍵のサイズおよび署名サイズがグループメンバ数であるＮに依存しないグループ署名方式にできる。
【図面の簡単な説明】
【００２１】
【図１】グループ署名システムの構成例を示す図。
【図２】パラメータ生成装置の処理フローを示す図。
【図３】署名生成装置の処理フローを示す図。
【図４】署名検証装置の処理フローを示す図。
【図５】追跡装置の処理フローを示す図。
【発明を実施するための形態】
【００２２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２３】
図１にグループ署名システムの構成例を示す。グループ署名システムは、少なくともＮ台の署名生成装置１００１，…，１００Ｎ、署名検証装置２００、追跡装置３００を備える。パラメータ生成装置４００は、グループ署名システムに含めてもよいしグループ署名システムの外部の装置としてもよい。また、Ｎ台の署名生成装置１００１，…，１００Ｎ、署名検証装置２００、追跡装置３００、パラメータ生成装置４００はネットワーク８００を介して接続しておけばよい。図２にパラメータ生成装置の処理フロー、図３に署名生成装置の処理フロー、図４に署名検証装置の処理フロー、図５に追跡装置の処理フローを示す。
【００２４】
＜準備＞
まず、ｐとｑを互いに素の正の整数、ｎとｋを正の整数、Ｚｑを−ｑ／２より大きくｑ／２以下の整数からなる整数環、Ｚｑ［Ｘ］を整数環Ｚｑの元を係数とするＸの多項式全体の集合、ｆ（Ｘ）を整数環Ｚｑの元を係数とするｎ次モニック既約多項式、Ｒを多項式集合Ｚｑ［Ｘ］のｆ（Ｘ）を法とした剰余環上の多項式全体からなる集合とする。なお、整数環Ｚｑ上では、ｑで除した余りを−ｑ／２より大きくｑ／２以下の整数としていることに注意されたい。また、以降、特に明示しない場合は、集合Ｒの元同士の演算は前記剰余環上の演算である。例えば、ｋは、１３またはｌｏｇ２ｑを下回らない最小の整数とすればよい。また、例えば、ｎ＝２ｋ，ｆ（Ｘ）＝Ｘｎ＋１，ｑは素数かつ（ｑ−１）が２ｎの倍数となる組、ｎ＝２ｋ，ｆ（Ｘ）＝Ｘｎ＋１，ｑは素数かつｑ＝５（ｍｏｄ  ８）となる組などのように設定すればよい。
【００２５】
ｔは正の整数であって、以降の処理における並列度を決めるパラメータである。ＣはＲの部分集合、Ｃｔはｔ個の集合Ｃの元からなるベクトルを示す記号とする。例えば、Ｃ＝｛０，１｝，｛−１，０、＋１｝，｛±Ｘｎ−１，…，±Ｘ，０｝のように集合Ｃを定めればよい。‖‖∞を集合Ｒの元である多項式の係数の中で絶対値が最大の係数の絶対値を示す記号とする。例えば、ｇをＲの元でありｇ＝ｇ０＋ｇ１Ｘ＋…＋ｇｎ−１Ｘｎ−１のように表現できる多項式とすると、‖ｇ‖∞は｜ｇ０｜，…，｜ｇｎ−１｜の中の最大のものである。γを正の整数、Ｂ（γ）をすべての係数の絶対値がγ以下の集合Ｒ中の多項式の集合、Ｒｖ×ｗを（ｖ×ｗ）個の集合Ｒの元からなるｖ行ｗ列の行列を示す記号（ただしｖとｗは正の整数）とする。
【００２６】
βをｑ１／ｋ以上の正の整数、ＧをＧ＝［１，β，β２，…，βｋ−１］であるベクトル、δＮＴＲＵとδＴＥＸＴをｑ／２以下の正の整数、Ｂ∞をｑ／２以下の正の整数、Ｍを正の数とする。δＮＴＲＵは、追跡用鍵生成での秘密鍵空間を定める値である。δＴＥＸＴは、ユーザＩＤ空間を定める値である。Ｂ∞は検証装置で用いられるしきい値であり、Ｍはレスポンス生成での成功率を決めるパラメータである。
【００２７】
｛０，１｝＊を“０”と“１”からなる任意のビット長のビット列、Ｈを正の整数をＢ（δＴＥＸＴ）の元に変換するハッシュ関数、Ｈ２を（｛０，１｝＊，Ｒｋ×１，Ｒｋ×１，Ｒ１×１，Ｒ（３Ｋ＋２）×１，…，Ｒ（３Ｋ＋２）×１）をＣｔに変換するハッシュ関数（ただしＲ（３Ｋ＋２）×１の数はｔ個）とする。｜を行ベクトル同士の要素を同じ行に並べることを示す記号とする。例えばＡとＢをそれぞれ要素の数がｋ個の行ベクトルとすると、［Ａ｜Ｂ］は２ｋ個の要素を持つ行ベクトルである。；を列ベクトル同士の要素を同じ列に並べることを示す記号とする。例えば、Ｓｉ，１とＳｉ，２をそれぞれ要素の数がｋ個の列ベクトルとすると、［Ｓｉ，１；Ｓｉ，２］は２ｋ個の要素を持つ列ベクトルを示している。
【００２８】
Ｉｋを要素が集合Ｒの元であるｋ行ｋ列の単位行列とする。Ｄμ，εθをθ個の集合Ｒの多項式を要素とするベクトルを出力する分布であって、中心ベクトルμで標準偏差εの分布を示す記号とする。Ｄεを１個の多項式を出力する中心ベクトルがゼロベクトルの場合の分布Ｄμ，εθを示す記号、ＦＤμ，εθを分布Ｄμ，εθの確率密度関数とする（ただし、θは正の整数、μはθ個の集合Ｒの多項式を要素とするベクトル（θ次元Ｒベクトル）、εは正実数）。そして、ＤｓとＤαをあらかじめ定めた分布とする。
【００２９】
例えば、分布Ｄμ，εθは、以下のような分布とすればよい。ここで、Ｚをすべての整数の集合、Ｚ［Ｘ］を集合Ｚの元を係数とするＸの多項式全体の集合、ＲＺを多項式集合Ｚ［Ｘ］のｆ（Ｘ）を法とした剰余環中のｎ−１次以下の多項式全体からなる集合とする。またＲＺθ中の多項式の係数をθｎ次元整数ベクトルに写す関数をωとする。そして、正整数λ、λ次元実数ベクトルξ、正実数εについて、ガウス関数ρπ,ελをλ次元実数ベクトルｘについて
【００３０】
【数５】
0006386963.tif 000006
【００３１】
で定義する。正整数λについて、中心がλ次元実数ベクトルξ、標準偏差が正実数εとなるλ次元整数空間上の離散ガウス分布Ｅμ，ελの確率密度関数ＦＥμ，ελをλ次元整数ベクトルｘについて、
【００３２】
【数６】
0006386963.tif 000007
【００３３】
で定義する。また、正整数θについて、中心がθ次元Ｒベクトルμ、標準偏差が正実数ｓとなるθ次元ＲＺ空間上の離散ガウス分布Ｄμ，εθの確率密度関数ＦＤμ，εθを
【００３４】
【数７】
0006386963.tif 000008
【００３５】
で定義する。このような分布の場合、正実数αは正実数ｓよりも大きい値とすればよい。
【００３６】
＜パラメータ生成装置＞
パラメータ生成装置４００は、安全性指数とグループの人数（署名生成装置１００の数）Ｎを入力とし、マスタ鍵生成部４１０、署名用鍵生成部４２０、追跡用鍵生成部４３０、秘密鍵生成部４４０、鍵設定部４５０を備える。マスタ鍵生成部４１０は、集合Ｒからランダムに多項式を選び、ａとする（Ｓ４１０）。署名用鍵生成部４２０は、集合Ｒからランダムにｋ個の多項式を選び、ｋ個の要素からなる行ベクトルＡを生成する。また、集合Ｂ（β）からランダムに（ｋ×ｋ）個の多項式を選び、ｋ行ｋ列の行列Ｔを生成する。集合Ｒからランダムに多項式を選び、多項式ｕとする。として、Ｂ＝Ａ・Ｔによりｋ個の要素を持つ行ベクトルＢを求める（Ｓ４２０）。
【００３７】
追跡用鍵生成部４３０は、集合Ｂ（δＮＴＲＵ）からランダムに多項式を選びｆとする。集合Ｂ（δＮＴＲＵ）から（ｍｏｄ  ｑ）および（ｍｏｄ  ｐ）で逆元を持つ多項式をランダムに選び、多項式ｇとする。ｈ＝ｆ／ｇにより多項式ｈを求める（Ｓ４３０）。秘密鍵生成部４４０は、ｉ＝１，…，Ｎについて、ｍｉ＝Ｈ（ｉ）により得られる多項式ｍｉを求める。そして、秘密鍵生成部４４０は、それぞれが集合Ｒの元である多項式をｋ個ずつ要素とし、［Ａ｜（Ｂ＋ｍｉＧ）］・［Ｓｉ，１；Ｓｉ，２］＝ｕを満たす列ベクトルＳｉ，１，Ｓｉ，２を求める（Ｓ４４０）。なお、行列Ｔを用いれば、係数の値が小さい多項式からなる列ベクトルＳｉ，１，Ｓｉ，２を選定しやすいことが知られている。
【００３８】
鍵設定部４５０は、グループ公開鍵ｇｐｋをＡ，Ｂ，ｕ，ｈ，ａの組、ｉ番目の前記署名生成装置に対する秘密鍵ｇｓｋｉをＳｉ，１，Ｓｉ，２，ｍｉの組、追跡鍵ｇｏｋをｇとする（Ｓ４５０）。
【００３９】
＜署名生成装置＞
μを｛０，１｝＊であるメッセージとする。ｉ番目（ｉ＝１，…，Ｎ）の署名生成装置１００ｉは、グループ公開鍵ｇｐｋ、秘密鍵ｇｓｋｉ、メッセージμを入力とする。ｉ番目（ｉ＝１，…，Ｎ）の署名生成装置１００ｉは、初期コミット生成部１１０ｉ、署名事前準備部１２０ｉ、非対話証明生成部１３０ｉ、最終処理部１７０ｉを備える。
【００４０】
初期コミット生成部１１０ｉは、
（１）集合Ｒから分布Ｄｓにしたがって多項式を選ぶことでｒ２，ｅ２，ｒ３，ｅ３，ｒ４，ｅ４を生成する。なお、ｒ２，ｅ２，ｒ３，ｅ３はｋ個の多項式からなる列ベクトル、ｒ４，ｅ４は多項式である。
（２）初期コミットＣ２，Ｃ３，Ｃ４を、
Ｃ２＝ｐ（ａｒ２＋ｅ２）＋Ｓｉ，２
Ｃ３＝ｐ（ａｒ３＋ｅ３）＋ｍｉＳｉ，２
Ｃ４＝ｐ（ｈｒ４＋ｅ４）＋ｍｉ
のように生成する（Ｓ１１０ｉ）。
【００４１】
署名事前準備部１２０ｉは、行列Ｚを
【００４２】
【数８】
0006386963.tif 000009
【００４３】
のように求める。なお、上記の式の“０”はｋ行ｋ列の行列を示しているときはすべての要素が“０”のｋ行ｋ列の行列であり、ベクトルを示しているときはすべての要素が０のベクトルであり、１つの要素を示しているときは数値の“０”を示している。そして、
ｒ３−＝ｒ３−ｍｉｒ２
ｅ３−＝ｅ３−ｍｉｅ２
を計算し、列ベクトルΣを、Σ＝［ｒ２；ｅ２；ｒ３；ｅ３；ｒ４；ｅ４；ｒ３−；ｅ３−；Ｓｉ，１；Ｓｉ，２；ｍｉＳｉ，２；ｍｉ］のように求める（Ｓ１２０ｉ）。
【００４４】
非対話証明生成部１３０ｉは、コミット生成部１４０ｉ、検証チャレンジ生成部１５０ｉ、レスポンス生成部１６０ｉを有し、コミットＷ１，…，Ｗｔ、レスポンスＶ１，…，Ｖｔを求める（Ｓ１３０ｉ）。具体的には、コミット生成部１４０ｉが、ｊ＝１，…，ｔについて、集合Ｒから分布Ｄαにしたがって（９ｋ＋３）個の多項式を選ぶことでＹｊを生成し、Ｗｊ＝ＺＹｊを計算して（３ｋ＋２）個の多項式からなる列ベクトルであるコミットＷｊを求める（Ｓ１４０ｉ）。なお、Ｙｊを（９ｋ＋３）個の多項式からなる列ベクトルである。検証チャレンジ生成部１５０ｉは、チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める（Ｓ１５０ｉ）。レスポンス生成部１６０ｉは、ｊ＝１，…，ｔについて、Ｖｊ＝Σｃｊ＋ＹｊのようにレスポンスＶｊを求める。そして、
【００４５】
【数９】
0006386963.tif 000010
【００４６】
の確率で、レスポンスＶｊをエラーを示すデータに書き換える（Ｓ１６０ｉ）。なお、分母にあらわれるＭはｖをＲ９ｋ＋３上の離散ガウス分布Ｄ０，α９ｋ＋３に従ってとった際に
【００４７】
【数１０】
0006386963.tif 000011
【００４８】
となる確率が圧倒的になるような1より大きい実数とすればよい。
【００４９】
最終処理部１７０ｉは、非対話証明生成部１３０ｉが求めたレスポンスＶ１，…，Ｖｔにエラーを示すレスポンスが含まれていた場合は非対話証明生成部１３０ｉの処理を繰り返させ（Ｓ１７１ｉ）、レスポンスＶ１，…，Ｖｔにエラーを示すレスポンスが含まれていない場合はＣ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ，Ｖ１，…，Ｖｔの組を署名σとして出力する（Ｓ１７２ｉ）。
【００５０】
＜署名検証装置＞
署名検証装置２００は、グループ公開鍵ｇｐｋ（Ａ，Ｂ，ｕ，ｈ，ａの組）、メッセージμ、署名σ（Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ，Ｖ１，…，Ｖｔの組）を入力とし、検証事前準備部２２０、検証チャレンジ再生成部２３０、検証メイン部２４０を備える。検証事前準備部２２０は、行列Ｚを
【００５１】
【数１１】
0006386963.tif 000012
【００５２】
のように、列ベクトルτをτ＝［Ｃ２；Ｃ３；Ｃ４；Ｃ３；ｕ］のように求める（Ｓ２２０）。
【００５３】
検証チャレンジ再生成部２３０は、チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める（Ｓ２３０）。検証メイン部２４０は、ｊ＝１，…，ｔについて、ＺＶｊ＝ｔｃｊ＋Ｗｊかつ‖Ｖｊ‖∞≦Ｂ∞が成り立つことを確認する。検証メイン部２４０は、すべて成り立つときは署名σが正当であることを示す情報（例えば“１”）を出力し、成り立たないものがあるときは署名σが正当ではないことを示す情報（例えば“０”）を出力する（Ｓ２４０）。
【００５４】
＜追跡装置＞
追跡装置３００は、グループ公開鍵ｇｐｋ（Ａ，Ｂ，ｕ，ｈ，ａの組）、追跡鍵ｇｏｋ（多項式ｇ）、メッセージμ、署名σ（Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ，Ｖ１，…，Ｖｔの組）を入力とし、正当性確認部３１０と署名生成者特定部３５０を備える。正当性確認部３１０は、追跡事前準備部３２０、追跡チャレンジ再生成部３３０、追跡検証部３４０を有し、署名σが正当かを確認する（Ｓ３１０）。追跡事前準備部３２０は、行列Ｚを
【００５５】
【数１２】
0006386963.tif 000013
【００５６】
のように、列ベクトルτをτ＝［Ｃ２；Ｃ３；Ｃ４；Ｃ３；ｕ］のように求める（Ｓ３２０）。
【００５７】
追跡チャレンジ再生成部３３０は、チャレンジｃ１，…，ｃｔを、（ｃ１，…，ｃｔ）＝Ｈ２（μ，Ｃ２，Ｃ３，Ｃ４，Ｗ１，…，Ｗｔ）のように求める（Ｓ３３０）。追跡検証部３４０は、ｊ＝１，…，ｔについて、ＺＶｊ＝ｔｃｊ＋Ｗｊかつ‖Ｖｊ‖∞≦Ｂ∞が成り立つことを確認する（Ｓ３４０）。追跡検証部３４０は、すべて成り立つときは署名σが正当であることを示す情報（例えば“１”）を出力し、成り立たないものがあるときは署名σが正当ではないことを示す情報（例えば“０”）を出力する。また、署名σが正当ではない場合は、処理を停止すればよい。
【００５８】
署名生成者特定部３５０は、
ｍ＝（（ｇＣ４  ｍｏｄ  ｑ）ｍｏｄ  ｐ）・（ｇ−１  ｍｏｄ  ｐ）ｍｏｄ  ｐ
のようにｍを求める。そして、署名生成者特定部３５０は、Ｈ（ｉ）＝ｍが成り立つｉが１，…，Ｎの中に存在すれば当該ｉを出力し、存在しなければエラーを示す情報を出力する（Ｓ３５０）。なお、図５（Ａ）は正当性確認部３１０の処理と署名生成者特定部３５０の処理を直列に行った場合を示し、図５（Ｂ）は正当性確認部３１０の処理と署名生成者特定部３５０の処理を並列に行った場合を示している。追跡装置３００の処理はどちらでもよい。
【００５９】
＜効果＞
本発明のグループ署名システムによれば、グループメンバのＩＤ（何番目の署名生成装置であるか）を多項式に直接埋め込むことで、１要素としている。このことにより、グループ公開鍵ｇｐｋを構成するＡは要素数ｋ個の行ベクトル、Ｂは要素数ｋ個の行ベクトル，ｕは多項式，ｈは多項式，ａは多項式であり、サイズはＮに依存しない。また、署名σを構成するＣ２は要素数ｋ個の列ベクトル、Ｃ３は要素数ｋ個の列ベクトル、Ｃ４は多項式、Ｗ１，…，Ｗｔは要素数（３ｋ＋２）個の列ベクトル、Ｖ１，…，Ｖｔは要素数（９ｋ＋３）個の列ベクトルであり、サイズはＮに依存しない。このように、Ｎに依存しないグループ署名方式にできる。
【００６０】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６１】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００６６】
１００  署名生成装置                    １１０  初期コミット生成部
１２０  署名事前準備部                  １３０  非対話証明生成部
１４０  コミット生成部                  １５０  検証チャレンジ生成部
１６０  レスポンス生成部                １７０  最終処理部
２００  署名検証装置                    ２２０  検証事前準備部
２３０  検証チャレンジ再生成部          ２４０  検証メイン部
３００  追跡装置                        ３１０  正当性確認部
３２０  追跡事前準備部                  ３３０  追跡チャレンジ再生成部
３４０  追跡検証部                      ３５０  署名生成者特定部
４００  パラメータ生成装置              ４１０  マスタ鍵生成部
４２０  署名用鍵生成部                  ４３０  追跡用鍵生成部
４４０  秘密鍵生成部                    ４５０  鍵設定部
８００  ネットワーク
【図１】
0006386963.tif 000022
【図２】
0006386963.tif 000023
【図３】
0006386963.tif 000024
【図４】
0006386963.tif 000025
【図５】
0006386963.tif 000026