(57)【特許請求の範囲】
【請求項１】
入力手段と、計算手段と、出力手段とを有する検証装置のグループ署名方式において、
前記入力手段は、計算に必要なデータを読み込むステップを実行し、
前記計算手段は、
事前に定められた群の元の組（ａ，Ｃ）の離散対数の知識の証明を検証するとき、各ｊ=1〜Ｎについてチャレンジｃ＿ｊを取得するステップと、
前記ｃ＿ｊの符号反転させた値で前記Ｃをべき乗した値と、前記ａを前記入力されたデータの一部であるξ＿｛ｊ｝でべき乗した値とを乗算し、前記群の元Ｌ＿｛ｊ｝＾＊を算出するステップと、
前記Ｌ＿｛ｊ｝＾＊を含むデータのハッシュ値と前記チャレンジｃ＿ｊとが一致するか否かを確認するステップとを実行し、
前記出力手段は、前記Ｌ＿｛ｊ｝＾＊を含むデータのハッシュ値と前記チャレンジｃ＿ｊとが一致しなかったとき、前記（ａ，Ｃ）の離散対数の知識の証明が正当でない旨を出力するステップを実行することを特徴とするグループ署名方式。
【請求項２】
イッシュアー装置との通信によりメンバー秘密鍵、メンバー公開鍵、及びユーザ特定情報を生成するユーザ装置のグループ署名方式において、
イッシュアーの公開鍵を含む必要なデータを読み込む第１のステップと、
ランダムに整数ｘ'を生成し、べき乗剰余を計算して前記べき乗剰余の計算結果Ｃを前記イッシュアー装置に送信する第２のステップと、
前記イッシュアー装置において生成された整数ｘ''を受信し、前記ｘ'とｘ''とを用いて整数ｘを算出し、前記ｘを前記メンバー秘密鍵又はその一部としてセットし、少なくとも二回のべき乗剰余を算出し、前記二回のべき乗剰余の計算結果である前記群の元β及びＢのうち少なくともβを前記イッシュアー装置に送信し、前記Ｂを前記ユーザ特定情報としてセットし、前記βは前記イッシュアー装置の前記公開鍵の一部分である前記群の元Ｇを底とし、前記ｘを指数とするべき乗剰余を算出する第３のステップと、
前記イッシュアー装置から整数ｅと前記ＲＳＡモジュラスを法とする前記平方剰余群の元ｂとを受信する第４のステップとを実行し、
前記出力手段は、（ｂ，ｅ）を前記メンバー公開鍵又はその一部に付加し、前記メンバー公開鍵及び前記メンバー秘密鍵を出力するステップを実行し、
前記べき乗剰余計算は、前記イッシュアー装置の公開鍵の一部であるａを底とし、前記ｘ'が指数であり、
前記Ｂは、前記ａを底とし、前記ｘを指数とするべき乗剰余によって計算され、
前記Ｇは、位数が公開された群の元であり、
前記ａは、ＲＳＡモジュラスを法とする平方剰余群の元であることを特徴とするグループ署名方式であって、
前記第２のステップは、前記Ｃのストレートライン・エクストラクタブルな正当性証明文と、前記ａを底とした前記Ｃの離散対数が定められた区間に入っていること証明する証明文とを算出するステップと、前記Ｃとともにストレートライン・エクストラクタブルな前記正当性証明文と、定められた区間に入っていることを証明する前記証明文とを前記イッシュアー装置に送信するステップとを有し、
前記第３のステップは、前記（β，Ｂ）の正当性証明文を生成し、前記（β，Ｂ）の前記正当性証明文を前記イッシュアー装置に送信するステップを有し、
前記ストレートライン・エクストラクタブルな前記正当性証明文を作成するステップは、
必要なデータを読み込み、ランダムに正数Ｘ＿｛０１｝，・・・，Ｘ＿｛０Ｎ｝を選択するステップと、
各ｊについて前記ｘ'を前記Ｘ＿｛０ｊ｝に加えたＸ＿｛１ｊ｝と、ビット列ｒをランダムに選択し、各ｉｊについてＸ＿｛ｉｊ｝とｒとを含むビット列のハッシュ値Ｃ＿｛ｉｊ｝と、前記ハッシュ値Ｃ＿｛ｉｊ｝を含むビット列のハッシュ値Ｖとを算出するステップと、
Ｘ＿｛０１｝，・・・，Ｘ＿｛０Ｎ｝からなるベクトルとＶとの内積Ｘを算出するステップと、
イッシュアーの公開情報の一部であるデータａをＸ乗することで得られる前記群の元Ｌを含むデータのハッシュ値からｃ＿１，・・・，ｃ＿Ｎを生成するステップと、
前記ストレートライン・エクストラクタブルな前記正当性証明文としてｒ、｛Ｃ＿｛ｉｊ｝｝、Ｌ、及びΞを含むデータを出力するステップとを有し、
Ｘ＿｛ｃ＿ｊｊ｝がξ＿ｊであり、前記Ξがξ＿１，・・・，ξ＿Ｎを含む組であることを特徴とするグループ署名方式。
【請求項３】
前記ストレートライン・エクストラクタブルな前記正当性証明文を生成することを特徴とする請求項２記載のグループ署名方式。
【請求項４】
ユーザ装置と通信しながらメンバー秘密鍵、メンバー公開鍵、及びユーザ特定情報を生成するイッシュアー装置のグループ署名方式において、
公開鍵と秘密鍵を含むデータを読み込む第１のステップと、
ランダムに整数ｘ''を生成し、前記ｘ''を前記ユーザ装置に送信する第２のステップと、
前記ユーザ装置から受信したデータ又はその一部であるβを用い、前記（ｂ，ｅ）を算出する第３のステップとを有し、
前記βは、ＲＳＡモジュラスｎを法とする平方剰余群の元であり、
前記ｅは、ランダムに選択され、
前記ｂは、前記βを前記ｎの法として１／ｅ乗して生成されることを特徴とするグループ署名方式であって、
前記第２のステップは、
前記ユーザ装置から前記群の元データＣ、前記データＣのストレートラインエクストラクタブルな正当性証明文、及びイッシュアーの公開鍵の一部であるａを底とした前記データＣの離散対数が定められた区間に入っていることを証明する証明文を受信し、
前記ストレートラインエクストラクタブルな正当性証明文、及び区間に入っていることを証明する前記証明文の正当性を検証し、
前記第３のステップは、
前記データＢと前記（β，Ｂ）の正当性証明文を受信し、
前記（β，Ｂ）の前記正当性証明文の正当性を検証し、
ストレートラインエクストラクタブルな前記正当性証明文の前記検証は、
前記ストレートラインエクストラクタブルな正当性証明文を含む必要なデータを読み込み、
読み込んだストレートラインエクストラクタブルな前記正当性証明文がビット列rとハッシュ値の組｛Ｃ＿｛ｉｊ｝｝と事前に定められた群の元Ｌと正数の組Ξとを含み、前記｛Ｃ＿｛ｉｊ｝｝を含むデータのハッシュ値をＶとし、｛Ｃ＿｛ｉｊ｝｝とＬとｒとを含むデータのハッシュ値からＫ＝（ｃ＿１，・・・，Ｃ＿Ｎ）を生成し、
全てｊについてＣ＿｛ｃ＿ｊｊ｝がξ＿ｊ、ｃ＿ｊ、及びｒを含むデータのハッシュ値であり、かつイッシュアー装置の公開鍵の一部である群の元ａをＶとΞとの内積でべき乗した値が、前記データＣをＶとＫとの内積でべき乗した値にＬを乗算した値に等しいとき、正当性証明文を受理することを特徴とするグループ署名方式。
【請求項５】
ストレートラインエクストラクタブルな前記正当性証明文の前記検証を実行することを特徴とする請求項４記載のグループ署名方式。
【請求項６】
入力手段と、暗号化手段と、コミットメント手段と、チャレンジ手段と、レスポンス手段と、出力手段とを有するユーザ装置のグループ署名方式であって、
前記入力手段が、前記ユーザ装置の公開鍵と前記ユーザ装置の秘密鍵とオープナー装置の公開鍵とを読み込むステップを実行し、
前記暗号化手段が、乱数ρを選択し、前記オープナー装置の前記公開鍵又はその一部と前記ρとを用いて、ユーザ特定情報である群の元Ｂを暗号化した暗号文Cipherを生成するステップを実行し、
前記コミットメント手段が整数ｕ，ｅ'をランダムに選択し、前記ユーザ装置の前記公開鍵の一部である群の元ｂのコミットメントχ＿ｂ、前記ユーザ装置の前記公開鍵の一部であるeのコミットメントχ＿ｅ、前記ｕのコミットメントχ＿ｕ、ＲＳＡモジュラスに係る検証式の成立の検証に使用するコミットメント（ｄ＿１，ｄ＿２）、ｅ'のコミットメントｄ＿ｅ、及び前記Cipherが正当な暗号文であることを検証するためのコミットメントComCipherを取得するステップを実行し、
前記チャレンジ手段がチャレンジである整数ｌを取得するステップを実行し、
前記レスポンス手段が前記ユーザ装置の秘密鍵である整数ｘの知識を表すレスポンスである整数ｘ''、前記ｅの知識を表すレスポンスである整数ｅ''、前記ｕの知識を示すレスポンスである整数ｕ''、前記ｕと前記ｅとの積の知識を示すレスポンスである整数ｕ''＿ｅ、及びρの知識を示すレスポンスである整数ρ’’を取得するステップを実行し、
前記出力手段が前記各レスポンスを出力するステップを実行することを特徴とするグループ署名方式。
【請求項７】
前記Cipherの算出に用いる前記オープナー装置の前記公開鍵又はその一部は、群の元Ｐ、Ｑ＿１、及びＱ＿２を有し、
前記Cipherは、群の元Ｇ'、Ｈ'＿１、及びＨ'＿２を有し、
前記ComCipherは、前記Ｇを前記ρ’でスカラー倍することにより算出される前記Ｕ、前記Ｇを前記ｘ'でスカラー倍した値に前記Ｈ＿１を前記ρ’でスカラー倍した値を加えた前記Ｖ＿１、及び前記Ｇを前記ｘ'でスカラー倍した値に前記Ｈ＿２を前記ρ’でスカラー倍した値を加えた前記Ｖ＿２を有し、
前記Ｇ'，Ｈ'＿１，及びＨ'＿２を生成するとき、前記ユーザ装置は、数ρをランダムに選択し、Ｐのρによるスカラー倍であるＧ'、Ｑ＿１のρによるスカラー倍にＢを加えたＨ'＿１、及びＱ＿２のρによるスカラー倍にＢを加えたＨ'＿２を算出し、
前記コミットメント手段は、整数ｓ，ｔ，ｘ'，ｔ'，ｕ'＿ｅ，ｔ'＿ｅ，ρ'をランダムに選択し、ｕ'のコミットメントｄ＿ｕを算出し、
前記χ＿ｂは、イッシュアーの公開鍵の一部である群の元ｈをｕ乗した値にユーザの公開鍵の一部であるｂを乗算して算出され、
前記χ＿ｅは、ｅからセキュリティパラメータから決まる値γで２をべき乗した値を引いた整数Ｅを算出し、イッシュアーの公開鍵の一部である群の元ｇを前記Ｅでべき乗した値に前記ｈをｓでべき乗した値を乗算することにより算出され、
前記χ#ｕは、前記ｇを前記ｕでべき乗した値に、前記ｈを前記ｔでべき乗した値を乗算することにより算出され、
前記ｄ＿１は、前記イッシュアーの前記公開鍵の一部であるａを−ｘ'でべき乗することにより算出される値と、前記χ＿ｂをｅ'でべき乗して算出される値と、前記ｈを整数Ｕでべき乗して算出される値とを乗算することにより算出され、
前記Ｕは、２を前記γでべき乗した値に前記ｕ'を乗算した値に前記ｕ'＿ｅを加えた値を符号反転することにより算出され、
前記ｄ＿２は、前記χ＿ｕを−ｅ'でべき乗することにより算出される値と、前記ｇを前記ｕ'＿ｅでべき乗することにより算出される値と、前記ｈを前記ｔ'＿ｅでべき乗することにより算出される値とを乗算することにより算出され、
前記ｄ＿ｅは、前記ｇを前記ｅ'でべき乗した値に前記ｈを前記ｓ'でべき乗した値を乗算することにより算出され、
前記ｄ＿ｕは、前記ｇを前記ｕ'でべき乗した値に前記ｈを前記ｔ'でべき乗した値を乗算することにより算出されることを特徴とする請求項６記載のグループ署名方式。
【請求項８】
前記ｓの知識を示すレスポンスである整数ｓ''、前記ｔの知識を示すレスポンスである整数ｔ''、及び前記ｔと前記ｅとの積の知識を示すレスポンスである整数ｔ''＿ｅを算出するステップを有し、
前記ｘ''は、前記ｘに前記lを乗算した値に前記ｘ'を加えた値であり、
前記ｅ''は、２を前記λでべき乗した値を前記ｅから減算した値に前記ｌを乗算し前記ｅ'を加えた値であり、
前記ｕ''は、前記ｕに前記ｌを乗算した値に前記ｕ'を加えた値であり、
前記ｓ''は、前記ｓに前記ｌを乗算した値に前記ｓ'を加えた値であり、
前記ｔ''は、前記ｔに前記ｌを乗算した値に前記ｔ'を加えた値であり、
前記ｕ''＿ｅは、２を前記λでべき乗した値を前記ｅから減算した値に前記ｕと前記ｌを乗算し、前記ｕ‘ｅを加えた値であり、
前記ｔ''＿ｅは、２を前記λでべき乗した値を前記eから減算した値に前記ｔと前記ｌを乗算し、前記ｔ'＿ｅを加えた値であり、
前記ρ’’は、前記ρに前記ｌを乗算した値に前記ρ’を加えた値であり、
前記χ＿ｂ、前記χ＿ｅ、前記χ＿ｕ、前記ｘ''、前記ｅ''、前記ｕ''、前記ｓ''、前記ｔ''、前記ｕ''＿ｅ、前記ｔ''＿ｅ、前記ρ’’をデータの一部として出力することを特徴とする請求項７記載のグループ署名方式。
【請求項９】
前記ｌは、前記（χ＿ｂ,（χ＿ｅ,χ＿ｕ）,ｄ＿１,ｄ＿２,（ｄ＿ｅ,ｄ＿ｕ）,（Ｕ，Ｖ＿１，Ｖ＿２））を含むデータのハッシュ値であることを特徴とする請求項８記載のグループ署名方式。
【請求項１０】
前記ｌが出力されるデータの一部として含まれていることを特徴とする請求項９記載のグループ署名方式。
【請求項１１】
前記（χ＿ｂ,（χ＿ｅ,χ＿ｕ），ｄ＿１，ｄ＿２，（ｄ＿ｅ，ｄ＿ｕ），（Ｕ，Ｖ＿１，Ｖ＿２））が出力されるデータの一部として含まれていることを特徴とする請求項１０記載のグループ署名方式。
【請求項１２】
データを入力する入力手段と、前記データを検証する検証手段と、前記検証手段による検証結果を出力する出力手段とを有する検証装置のグループ署名方式において、
前記入力手段は、ユーザ装置が出力したデータ及び公開情報と、チャレンジｌとを入力し、
前記データは、コミットメントχ＿ｂ、χ＿ｅ、χ＿ｕ、レスポンスである整数ｘ''、ｅ''、ｕ''、ｓ''、ｔ''、ｕ''＿ｅ、ｔ''＿ｅ、及びρ’’を有し、
前記出力手段は、署名文がメッセージの正当な署名文であるか否かを表すデータを出力し、
前記検証手段は、コミットメント計算手段と、正当性検証手段と、区間検証手段とを有し、
前記コミットメント計算手段は、群の元ｄ＿１＾＊、ｄ＿２＾＊、ｄ＿ｅ＾＊、ｄ＿ｕ＾＊、Ｕ＾＊、Ｖ＿１＾＊、及びＶ＿２＾＊を算出し、
前記ｄ＿１＾＊は、前記ｌを符号反転した値でイッシュアー装置の公開鍵の一部であるａ＿０をべき乗した値と、前記ｘ''を符号反転した値で前記イッシュアー装置の前記公開鍵の一部である群の元ａをべき乗した値と、セキュリティパラメータによって決定される値γで２をべき乗した値にｌを乗算し、ｅ''を加えた値を指数してχ＿ｂを底としてべき乗した値と、２を前記γ乗した値に前記ｕ''を乗じた値に前記ｕ''＿ｅを加えた値とを乗算した値であり、
前記ｄ＿２＾＊は、前記χ＿ｕを−ｅ''乗した値と、前記イッシュアー装置の前記公開鍵の一部であるｇを前記ｕ''＿ｅ乗した値と、前記イッシュアー装置の前記公開鍵の一部であるｈを前記ｔ''＿ｅ乗した値とを乗算した値であり、
前記ｄ＿ｅ＾＊は、前記ｌを符号反転した値で前記χ＿ｅをべき乗した値、前記ｇを前記ｕ''＿ｅ乗した値、前記ｈを前記ｓ''乗した値とを乗算した値であり、
前記ｄ＿ｕ＾＊は、前記ｌを符号反転した値で前記χ＿ｕをべき乗した値と、前記ｇを前記ｕ''乗した値と、前記ｈを前記ｔ''乗した値とを乗算した値であり、
前記Ｕ＾＊は、前記ｌを符号反転した値でＰをスカラー倍した値に前記ρ’’で前記Ｇをスカラー倍した値を加えた値であり、
前記Ｖ＿１＾＊は、前記ｌを符号反転した値でＱ＿１をスカラー倍した値と、前記ｘ''で前記Ｇをスカラー倍した値と、前記ρ’’で前記Ｈ＿１をスカラー倍した値とを加算した値であり、
前記Ｖ＿２＾＊は、前記ｌを符号反転した値でＱ＿２をスカラー倍した値と、前記ｘ''で前記Ｇをスカラー倍した値と、前記ρ’’で前記Ｈ＿２をスカラー倍した値とを加算した値であり、
前記区間検証手段は、ｘ''及びｅ''が予め定められた範囲に属する数であるか否かを検証することを特徴とするグループ署名方式。
【請求項１３】
前記ユーザ装置が出力した前記データの中に前記ｌが含まれていることを特徴とする請求項１２記載のグループ署名方式。
【請求項１４】
前記ｌが前記（χ＿ｂ，（χ＿ｅ，χ＿ｕ），ｄ＿１＾＊，ｄ＿２＾＊，（ｄ＿ｅ＾＊，ｄ＿ｕ＾＊），（Ｕ＾＊，Ｖ＿１＾＊，Ｖ＿２＾＊））を含むデータのハッシュ値であることを特徴とする請求項１３記載のグループ署名方式。
【請求項１５】
前記ユーザ装置が出力したデータは、７種類のデータを有し、
前記検証手段は、前記ｌとして前記７種類のデータを含むデータのハッシュ値を用い、かつ前記検証装置が前記７種類のデータが前記ｄ＿１＾＊、前記ｄ＿２＾＊、前記ｄ＿ｅ＾＊、前記ｄ＿ｕ＾＊、前記Ｕ＾＊、前記Ｖ＿１＾＊、前記Ｖ＿２＾＊に等しいか否かを検証することを特徴とする請求項１４記載のグループ署名方式。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループ署名方式に関し、特に、効率的かつ安全なグループ署名方式に関する。
【背景技術】
【０００２】
グループ署名方式は、権限者によってグループのメンバーと認められたユーザだけがグループメンバーとしての署名文を匿名で作成することができ、かつ権限者だけが署名者を特定することができる署名方式である。【０００３】
近年、複数のグループ署名方式が提案されている。提案されているグループ署名には、ＲＳＡベースのもの（非特許文献１及び６）、Pairingベースのもの（非特許文献３、４、及び７）、Nyberg-Rueppelベースのもの（非特許文献２）がある。
【非特許文献１】G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik.A Practical and Provably Secure Coalition-Resistant  Group Signature Scheme.In Advances in Cryptology --- CRYPTO 2000, vol. 1880 of LNCS, pp. 255-270, Springer-Verlag, 2000.
【非特許文献２】Giuseppe Ateniese and Breno de Medeiros. Efficient Group Signatures without Trapdoors. In Advances in Cryptology --- ASIACRYPT 2003, vol. 2094 of LNCS, pp. 246-268, Springer-Verlag, 2003.
【非特許文献３】Dan Boneh, Xavier Boyen, and Hovav Shacham. Short Group Signatures. Advances in Cryptology --- CRYPTO 2004, vol. 2656 of LNCS, pp. 614-629, Springer-Verlag, 2004.
【非特許文献４】Jan Camenisch, Anna Lysyanskaya. Signature Schemes and Anonymous Credentials from Bilinear Maps. Advances in Cryptology --- CRYPTO 2004, vol. 2139 of LNCS, pp. 388-407, Springer-Verlag, 2004.
【非特許文献５】Jan Camenisch and Markus Michels. Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes. In Advances in Cryptology --- EUROCRYPT'99, vol. 1592 of LNCS, pp. 107-122, Springer-Verlag, 1999.
【非特許文献６】Aggelos Kiayias, and Moti Yung. Group Signatures: Provable Secure, Efficient Constructions and Anonymity from Trapdoor Holders. http://eprint.iacr.org/2004/076.ps
【非特許文献７】Lan Nguyen and Rei Safavi-Naini. Efficient and Provably Secure Trapdoor-free Group Signature Schemes from Bilinear Pairings. In Advances in Cryptology --- ASIACRYPT 2004, vol. 2729 of LNCS, pp. 316-337, Springer-Verlag, 2004.
【非特許文献８】Victor Shoup and Rosario Gennaro. Secureing Threshold Cryptosystems against Chosen Ciphertext Attack. In Advances in Cryptology --- EUROCRYPT'98,  vol. 1403 of \emph[LNCS], pp. 1-16, Springer-Verlag, 1998.
【非特許文献９】Dan Boneh, Xavier Boyen. Short Signatures Without Random Oracles. In Advances in Cryptology --- EUROCRYPT 2004 vol 3027 of \emph[LNCS], pp.56-73, Springer-Verlag, 2004.
【非特許文献１０】Rafael Pass. On Deniability in the Common Reference String and Random Oracle Model. In Advances in Cryptology --- CRYPTO 2003,  vol. 2729 of LNCS, pp. 316-337, Springer-Verlag, 2003.
【非特許文献１１】Fabrice Boudot. Efficient Proofs that a Committed Number Lies in an Interval. In EUROCRYPT 2000, LNCS 1807, pp. 255-270, Springer-Verlag, 2000.
【非特許文献１２】Joe Kilian, and Erez Petrank. Identity Escrow. In CRYPTO'98,  LNCS 1462, pp. 169-185, Springer-Verlag, 1998.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、上記の発明は以下の問題を有している。【０００５】
非特許文献（１、２、６、及び７）記載の安全性証明には不備がある。具体的には、暗号方式に対する攻撃（非特許文献８）と類似の攻撃をユーザ追加のプロシージャに対して行うことができ、かつこの攻撃はたとえ攻撃者がsequentialにしかユーザ追加のプロシージャを呼び出さないと仮定して行うことができる。【０００６】
また、非特許文献（１、及び６）記載の方式の場合、権限者は自分の公開鍵を不正な方法で作成することにより、ユーザの秘密鍵を知ることができる。また、たとえ権限者に公開鍵の正当性証明文の出力を義務づけたとしても、安全性は証明できない。また、権限者に公開鍵の正当性証明文を出力させ、各ユーザがその証明文を検証するという方法は効率が悪い。さらに、公開鍵の一部ｎがＲＳＡモジュラスであることを示すために、２×１０＾｛１０｝回の巾乗剰余算が必要である（非特許文献５）。【０００７】
非特許文献（３、４）記載の方式は、q-SDH仮定（非特許文献９）、非特許文献４の方式はＬＲＳＷ仮定（非特許文献４）というartificialな仮定に基づいて安全性を証明している。【０００８】
そこで、本発明は、イッシュアーではなくオープナーがオープン手段を保持し、オープン手段を実行する際に必要なデータがイッシュアーの鍵ペアを有しないため、イッシュアーが不正な方法で作成した公開鍵を作成したとしてもオープン手段を適正に実行することができるグループ署名方式を提案することを目的としている。
【課題を解決するための手段】
【０００９】
請求項１記載の発明は、入力手段と、計算手段と、出力手段とを有する証明装置のグループ署名方式において、前記入力手段は、計算に必要なデータを読み込むステップを有し、前記計算手段は、Ｎをセキュリティパラメータの１つとして（ａ，Ｃ）の離散対数の知識を証明するとき、前記Ｎ個の正数Ｘ＿｛１ｊ｝をランダムに選択し、各ｊについて秘密情報ｘ'と前記Ｘ＿｛０ｊ｝を用いてＸ＿｛１ｊ｝を算出するステップと、各ｊについてｒ＿｛ｉｊ｝を選択し、前記Ｘ＿｛ｉｊ｝と前記ｒ＿｛ｉｊ｝とを含むデータのハッシュ値をＣ＿｛ｉｊ｝を算出するステップと、各ｊについて前記ａを前記Ｘ＿｛０ｊ｝乗したＬ＿｛ｊ｝を算出するステップと、各ｊについてチャレンジｃ＿ｊを選択し、各ｊについてのξ＿｛ｊ｝を前記Ｘ＿｛ｃ＿ｊｊ｝とするステップとを有し、前記出力手段は、前記｛Ｃ＿｛ｉｊ｝｝及び前記｛ξ＿｛ｊ｝｝を含むデータを出力するステップを有することを特徴とする。【００１０】
請求項２記載の発明は、入力手段と、計算手段と、出力手段とを有する検証装置のグループ署名方式において、前記入力手段は、計算に必要なデータを読み込むステップを有し、前記計算手段は、（ａ，Ｃ）の離散対数の知識の証明を検証するとき、各ｊについてチャレンジｃ＿ｊを取得するステップと、前記ｃ＿ｊの符号反転させた値で前記Ｃをべき乗した値と、前記ａを前記入力されたデータの一部であるξ＿｛ｊ｝でべき乗した値とを乗算し、Ｌ＿｛ｊ｝＾＊を算出するステップと、前記Ｌ＿｛ｊ｝＾＊を含むデータのハッシュ値と前記チャレンジｃ＿ｊとが一致するか否かを確認するステップとを有し、前記出力手段は、前記Ｌ＿｛ｊ｝＾＊を含むデータのハッシュ値と前記チャレンジｃ＿ｊとが一致しなかったとき、前記（ａ，Ｃ）の離散対数の知識の証明が正当でない旨を出力するステップを有することを特徴とする。【００１１】
請求項３記載の発明は、イッシュアー装置との通信によりメンバー秘密鍵、メンバー公開鍵、及びユーザ特定情報を生成するユーザ装置のグループ署名方式において、イッシュアーの公開鍵を含む必要なデータを読み込む第１のステップと、ランダムに整数ｘ'を生成し、べき乗剰余を計算して前記べき乗剰余の計算結果Ｃを前記イッシュアー装置に送信する第２のステップと、前記イッシュアー装置において生成された数ｘ''を受信し、前記ｘ'とｘ''とを用いて数ｘを算出し、前記ｘを前記メンバー秘密鍵又はその一部としてセットし、少なくとも二回のべき乗剰余を算出し、前記二回のべき乗剰余の計算結果β及びＢのうち少なくともβを前記イッシュアー装置に送信し、前記Ｂを前記ユーザ特定情報としてセットし、前記βは前記イッシュアー装置の前記公開鍵の一部分Ｇを底とし、前記ｘを指数とするべき乗剰余を算出する第３のステップと、前記イッシュアー装置から整数ｅと前記ＲＳＡモジュラスを法とする前記平方剰余群の元ｂとを受信する第４のステップとを有し、前記出力手段は、前記（ｂ，ｅ）を前記メンバー公開鍵又はその一部に付加し、前記メンバー公開鍵及び前記メンバー秘密鍵を出力するステップを有し、前記べき乗剰余計算は、前記イッシュアー装置の公開鍵の一部であるａを底とし、前記ｘ'が指数であり、前記Ｂは、前記ａを底とし、前記ｘを指数とするべき乗剰余によって計算され、前記Ｇは、位数が公開された群の元であり、前記ａは、ＲＳＡモジュラスを法とする平方剰余群の元であることを特徴とする。【００１２】
請求項４記載の発明は、請求項３記載のグループ署名方式において、前記第２のステップは、前記Ｃのストレートライン・エクストラクタブルな正当性証明文と、前記ａを底とした前記Ｃの離散対数が定められた区間に入っていること証明する証明文とを算出するステップと、前記Ｃとともにストレートライン・エクストラクタブルな前記正当性証明文と、定められた区間に入っていることを証明する前記証明文とを前記イッシュアー装置に送信するステップとを有し、前記第３のステップは、前記（β，Ｂ）の正当性証明文を生成し、前記（β，Ｂ）の前記正当性証明文を前記イッシュアー装置に送信するステップを有することを特徴とする。【００１３】
請求項５記載の発明は、請求項４記載のグループ署名方式において、前記ストレートライン・エクストラクタブルな前記正当性証明文を作成するステップは、必要なデータを読み込み、ランダムにＸ＿｛０１｝，・・・，Ｘ＿｛０Ｎ｝を選択するステップと、各ｊについて前記ｘ'を前記Ｘ＿｛０ｊ｝に加えたＸ＿｛１ｊ｝と、数ｒをランダムに選択し、各ｉｊについてＸ＿｛ｉｊ｝とｒとを含むビット列のハッシュ値Ｃ＿｛ｉｊ｝と、前記ハッシュ値Ｃ＿｛ｉｊ｝を含むビット列のハッシュ値Ｖとを算出するステップと、Ｘ＿｛０１｝，・・・，Ｘ＿｛０Ｎ｝からなるベクトルとＶとの内積Ｘを算出するステップと、イッシュアーの公開情報の一部であるデータａをＸ乗したＬを含むデータのハッシュ値からｃ＿１，・・・，ｃ＿Ｎを生成するステップと、前記ストレートライン・エクストラクタブルな前記正当性証明文としてｒ、｛Ｃ＿｛ｉｊ｝｝、Ｌ、及びΞを含むデータを出力するステップとを有し、Ｘ＿｛ｃ＿ｊｊ｝がξ＿ｊであり、ξ＿１，・・・，ξ＿ＮがΞであることを特徴とする。【００１４】
請求項６記載の発明は、請求項５記載のグループ署名方式において、前記ストレートライン・エクストラクタブルな前記正当性証明文を生成することを特徴とする。【００１５】
請求項７記載の発明は、ユーザ装置と通信しながらメンバー秘密鍵、メンバー公開鍵、及びユーザ特定情報を生成するイッシュアー装置のグループ署名方式において、公開鍵と秘密鍵を含むデータを読み込む第１のステップと、ランダムに数ｘ''を生成し、前記ｘ''を前記ユーザ装置に送信する第２のステップと、前記ユーザ装置から受信したデータ又はその一部であるβを用い、（ｂ，ｅ）を算出する第３のステップとを有し、前記βは、ＲＳＡモジュラスｎを法とする平方剰余群の元であり、前記ｅは、ランダムに選択され、前記ｂは、前記βを前記ｎの法として１／ｅ乗して生成されることを特徴とする。【００１６】
請求項８記載の発明は、請求項７記載のグループ署名方式において、前記第２のステップは、前記ユーザ装置からデータＣ、前記データＣのストレートラインエクストラクタブルな正当性証明文、及びイッシュアーの公開鍵の一部であるａを底とした前記データＣの離散対数が定められた区間に入っていることを証明する証明文を受信し、前記ストレートラインエクストラクタブルな正当性証明文、及び区間に入っていることを証明する前記証明文の正当性を検証し、前記第３のステップは、前記データＢと前記（β，Ｂ）の正当性証明文を受信し、前記（β，Ｂ）の前記正当性証明文の正当性を検証することを特徴とする。【００１７】
請求項９記載の発明は、請求項８記載のグループ署名方式において、ストレートラインエクストラクタブルな前記正当性証明文の前記検証は、前記ストレートラインエクストラクタブルな正当性証明文を含む必要なデータを読み込み、読み込んだストレートラインエクストラクタブルな前記正当性証明文がrと｛Ｃ＿｛ｉｊ｝｝とＬとΞとを有し、前記｛Ｃ＿｛ｉｊ｝｝を含むデータのハッシュ値をＶとし、｛Ｃ＿｛ｉｊ｝｝とＬとｒとを含むデータのハッシュ値からＫ＝（ｃ＿１，・・・，Ｃ＿Ｎ）を生成し、全てｊについてＣ＿｛ｃ＿ｊｊ｝がξ＿ｊ、ｃ＿ｊ、及びｒを含むデータのハッシュ値であり、かつイッシュアー装置の公開鍵の一部であるａをＶとΞとの内積でべき乗した値が、前記データＣをＶとＫとの内積でべき乗した値にＬを乗算した値に等しいとき、正当性証明文を受理することを特徴とする。【００１８】
請求項１０記載の発明は、請求項８記載のグループ署名方式において、ストレートラインエクストラクタブルな前記正当性証明文の前記検証を実行することを特徴とする。【００１９】
請求項１１記載のグループ署名方式は、乱数ρを選択し、オープナー装置の公開鍵又はその一部と前記ρとを用いて、ユーザ特定情報Ｂを暗号化したCipherを生成するステップと、入力手段が計算に必要なデータを読み込むステップと、コミットメント手段がｕ，ｅ'をランダムに選択し、前記ユーザ装置の公開鍵の一部であるｂのコミットメントχ＿ｂ、ユーザ装置の前記公開鍵の一部であるeのコミットメントχ＿ｅ、ｕのコミットメントχ＿ｕ、ＲＳＡモジュラスに係る検証式の成立の検証に使用するコミットメント（ｄ＿１，ｄ＿２）、ｅ'のコミットメントｄ＿ｅ、及び前記Cipherが正当な暗号文であることを検証するためのコミットメントComCipherを取得するステップと、チャレンジ手段がチャレンジｌを取得するステップと、レスポンス手段が前記ユーザ装置の秘密鍵ｘの知識を表すレスポンスｘ''、前記ｅの知識を表すレスポンスｅ''、前記ｕの知識を示すレスポンスｕ''、前記ｕと前記ｅとの積の知識を示すレスポンスｕ''＿ｅ、及びρの知識を示すレスポンスρ’’を取得するステップと、出力手段が前記各レスポンスを出力するステップとを有することを特徴とする。【００２０】
請求項１２記載の発明は、請求項１１記載のグループ署名方式において、前記Cipherの算出に用いる前記オープナー装置の前記公開鍵又はその一部は、Ｐ、Ｑ＿１、及びＱ＿２を有し、前記Cipherは、Ｇ'、Ｈ'＿１、及びＨ'＿２を有し、前記ComCipherは、前記Ｇを前記ρ’でスカラー倍することにより算出される前記Ｕ、前記Ｇを前記ｘ'でスカラー倍した値に前記Ｈ＿１を前記ρ’でスカラー倍した値を加えた前記Ｖ＿１、及び前記Ｇを前記ｘ'でスカラー倍した値に前記Ｈ＿２を前記ρ’でスカラー倍した値を加えた前記Ｖ＿２を有し、前記Ｇ'，Ｈ'＿１，及びＨ'＿２を生成するとき、前記ユーザ装置は、数ρをランダムに選択し、Ｐのρによるスカラー倍であるＧ'、Ｑ＿１のρによるスカラー倍にＢを加えたＨ'＿１、及びＱ＿２のρによるスカラー倍にＢを加えたＨ'＿２を算出し、前記コミットメント手段は、数ｓ，ｔ，ｘ'，ｔ'，ｕ'＿ｅ，ｔ'＿ｅ，ρ'をランダムに選択し、ｕ'のコミットメントｄ＿ｕを算出し、前記χ＿ｂは、イッシュアーの公開鍵の一部であるｈをｕ乗した値にユーザの公開鍵の一部であるｂを乗算して算出され、前記χ＿ｅは、ｅからセキュリティパラメータから決まる値γで２をべき乗した値を引いたＥを算出し、イッシュアーの公開鍵の一部であるｇを前記Ｅでべき乗した値に前記ｈをｓでべき乗した値を乗算することにより算出され、前記χ#ｕは、前記ｇを前記ｕでべき乗した値に、前記ｈを前記ｔでべき乗した値を乗算することにより算出され、前記ｄ＿１は、前記イッシュアーの前記公開鍵の一部であるａを−ｘ'でべき乗することにより算出される値と、前記χ＿ｂをｅ'でべき乗して算出される値と、前記ｈを数Ｕでべき乗して算出される値とを乗算することにより算出され、前記Ｕは、２を前記γでべき乗した値に前記ｕ'を乗算した値に前記ｕ'＿ｅを加えた値を符号反転することにより算出され、前記ｄ＿２は、前記χ＿ｕを−ｅ'でべき乗することにより算出される値と、前記ｇを前記ｕ'＿ｅでべき乗することにより算出される値と、前記ｈを前記ｔ'＿ｅでべき乗することにより算出される値とを乗算することにより算出され、前記ｄ＿ｅは、前記ｇを前記ｅ'でべき乗した値に前記ｈを前記ｓ'でべき乗した値を乗算することにより算出され、前記ｄ＿ｕは、前記ｇを前記ｕ'でべき乗した値に前記ｈを前記ｔ'でべき乗した値を乗算することにより算出されることを特徴とする。【００２１】
請求項１３記載の発明は、請求項１２記載のグループ署名方式において、前記ｓの知識を示すレスポンスｓ''、前記ｔの知識を示すレスポンスｔ''、及び前記ｔと前記ｅとの積の知識を示すｔ''＿ｅを算出するステップを有し、前記ｘ''は、前記ｘに前記ｌを乗算した値に前記ｘ'を加えた値であり、前記ｅ''は、２を前記λでべき乗した値を前記ｅから減算した値に前記ｌを乗算し前記ｅ'を加えた値であり、前記ｕ''は、前記ｕに前記ｌを乗算した値に前記ｕ'を加えた値であり、前記ｓ''は、前記ｓに前記lを乗算した値に前記ｓ'を加えた値であり、前記ｔ''は、前記ｔに前記ｌを乗算した値に前記ｔ'を加えた値であり、前記ｕ''＿ｅは、２を前記λでべき乗した値を前記ｅから減算した値に前記ｕと前記ｌを乗算し、前記ｕ‘ｅを加えた値であり、前記ｔ''＿ｅは、２を前記λでべき乗した値を前記eから減算した値に前記ｔと前記ｌを乗算し、前記ｔ'＿ｅを加えた値であり、前記ρ’’は、前記ρに前記ｌを乗算した値に前記ρ’を加えた値であり、前記χ＿ｂ、前記χ＿ｅ、前記χ＿ｕ、前記ｘ''、前記ｅ''、前記ｕ''、前記ｓ''、前記ｔ''、前記ｕ''＿ｅ、前記ｔ''＿ｅ、前記ρ’’をデータの一部として出力することを特徴とする。【００２２】
請求項１４記載の発明は、請求項１３記載のグループ署名方式において、前記ｌは、前記（χ＿ｂ,（χ＿ｅ,χ＿ｕ）,ｄ＿１,ｄ＿２,（ｄ＿ｅ,ｄ＿ｕ）,（Ｕ，Ｖ＿１，Ｖ＿２））を含むデータのハッシュ値であることを特徴とする。【００２３】
請求項１５記載の発明は、請求項１４記載のグループ署名方式において、前記ｌが出力されるデータの一部として含まれていることを特徴とする。【００２４】
請求項１６記載の発明は、請求項１４記載のグループ署名方式において、前記（χ＿ｂ,（χ＿ｅ,χ＿ｕ），ｄ＿１，ｄ＿２，（ｄ＿ｅ，ｄ＿ｕ），（Ｕ，Ｖ＿１，Ｖ＿２））が出力されるデータの一部として含まれていることを特徴とする。【００２５】
請求項１７記載の発明は、データを入力する入力手段と、前記データを検証する検証手段と、前記検証手段による検証結果を出力する出力手段とを有する検証装置のグループ署名方式において、前記入力手段は、ユーザ装置が出力したデータ及び公開情報と、チャレンジｌとを入力し、前記データは、χ＿ｂ、χ＿ｅ、χ＿ｕ、ｘ''、ｅ''、ｕ''、ｓ''、ｔ''、ｕ''＿ｅ、ｔ''＿ｅ、及びρ’’を有し、前記出力手段は、署名文がメッセージの正当な署名文であるか否かを表すデータを出力し、前記検証手段は、コミットメント計算手段と、正当性検証手段と、区間検証手段とを有し、前記コミットメント計算手段は、ｄ＿１＾＊、ｄ＿２＾＊、ｄ＿ｅ＾＊、ｄ＿ｕ＾＊、Ｕ＾＊、Ｖ＿１＾＊、及びＶ＿２＾＊を算出し、前記ｄ＿１＾＊は、前記ｌを符号反転した値でイッシュアー装置の公開鍵の一部であるａ＿０をべき乗した値と、前記ｘ''を符号反転した値で前記イッシュアー装置の前記公開鍵の一部であるａをべき乗した値と、セキュリティパラメータによって決定される値γで２をべき乗した値にｌを乗算し、ｅ''を加えた値を指数してχ＿ｂを底としてべき乗した値と、２を前記γ乗した値に前記ｕ''を乗じた値に前記ｕ''＿ｅを加えた値とを乗算した値であり、前記ｄ＿２＾＊は、前記χ＿ｕを−ｅ''乗した値と、前記イッシュアー装置の前記公開鍵の一部であるｇを前記ｕ''＿ｅ乗した値と、前記イッシュアー装置の前記公開鍵の一部であるｈを前記ｔ''＿ｅ乗した値とを乗算した値であり、前記ｄ＿ｅ＾＊は、前記ｌを符号反転した値で前記χ＿ｅをべき乗した値、前記ｇを前記ｕ''＿ｅ乗した値、前記ｈを前記ｓ''乗した値とを乗算した値であり、前記ｄ＿ｕ＾＊は、前記ｌを符号反転した値で前記χ＿ｕをべき乗した値と、前記ｇを前記ｕ''乗した値と、前記ｈを前記ｔ''乗した値とを乗算した値であり、前記Ｕ＾＊は、前記lを符号反転した値でＰをスカラー倍した値に前記ρ’’で前記Ｇをスカラー倍した値を加えた値であり、前記Ｖ＿１＾＊は、前記ｌを符号反転した値でＱ＿１をスカラー倍した値と、前記ｘ''で前記Ｇをスカラー倍した値と、前記ρ’’で前記Ｈ＿１をスカラー倍した値とを加算した値であり、前記Ｖ＿２＾＊は、前記ｌを符号反転した値でＱ＿２をスカラー倍した値と、前記ｘ''で前記Ｇをスカラー倍した値と、前記ρ’’で前記Ｈ＿２をスカラー倍した値とを加算した値であり、前記区間検証手段は、ｘ''及びｅ''が予め定められた範囲に属する数であるか否かを検証することを特徴とする。【００２６】
請求項１８記載の発明は、請求項１７記載のグループ署名方式において、前記ユーザ装置が出力した前記データの中に前記ｌが含まれていることを特徴とする。【００２７】
請求項１９記載の発明は、請求項１８記載のグループ署名方式において、前記ｌが前記（χ＿ｂ，（χ＿ｅ，χ＿ｕ），ｄ＿１＾＊，ｄ＿２＾＊，（ｄ＿ｅ＾＊，ｄ＿ｕ＾＊），（Ｕ＾＊，Ｖ＿１＾＊，Ｖ＿２＾＊））を含むデータのハッシュ値であることを特徴とする。【００２８】
請求項２０記載の発明は、請求項１７記載のグループ署名方式において、前記ユーザ装置が出力したデータは、７種類のデータを有し、前記検証手段は、前記ｌとして前記７種類のデータを含むデータのハッシュ値を用い、かつ前記検証装置が前記７種類のデータが前記ｄ＿１＾＊、前記ｄ＿２＾＊、前記ｄ＿ｅ＾＊、前記ｄ＿ｕ＾＊、前記Ｕ＾＊、前記Ｖ＿１＾＊、前記Ｖ＿２＾＊に等しいか否かを検証することを特徴とする。
【発明の効果】
【００２９】
本発明は、イッシュアーではなくオープナーがオープン手段を保持し、オープン手段を実行する際に必要なデータにイッシュアーの鍵ペアが含まれないため、イッシュアーが不正な方法で作成した公開鍵を作成したとしてもオープン手段を適正に実行することができる。【００３０】
また、本発明は、メンバーの鍵ペアを偽造できないことを非特許文献１と同様の方法で証明でき、ElGamal暗号方式が安全であることを示す方法と同様の方法により署名文の一部である暗号文をオープナー以外は解読できないことを離散対数仮定から示すことができ、かつSchnorr署名が安全であることの証明と同様の方法で知識の署名がextractabilityを持つことをランダムオラクル仮定から示すことができる。【００３１】
また、本発明は、イッシュアーが不正な方法で作成した公開鍵を公開したとしてもオープン手段は正しく動作するため、非特許文献１とは異なりイッシュアーの公開鍵の一部であるｎがＲＳＡモジュラスであることの証明文を作成する必要がない。【００３２】
また、本発明は、強ＲＳＡ仮定、Ｌ上のdecision Diffie Helman仮定、及びランダムオラクル仮定のみで安全性が証明でき、非特許文献１と異なりｎの素因数を法とする有限体上での離散対数問題が困難である必要がないため、ｎのビット数を非特許文献１の方式の半分にすることができる。
【発明を実施するための最良の形態】
【００３３】
［第１の実施形態］
本実施形態において、Ｎ、Ｚ、Ｚｎ、ＱＺ（ｎ）によりそれぞれ自然数全体のなす集合、整数環、０以上ｎ−１以下の整数のなす環、Ｚｎ上の平方剰余全体のなす乗法群を表す。Ｈ＿Ｘで集合Ｘのハッシュ関数を表す。整数ｎについて｜ｎ｜のビット数を｜｜ｎ｜｜で表す。素数ｐであり、かつ（ｐ−１）／２が素数になるものをsafe primeとする。整数ｎであり、ビット長が等しい２つのsafe primeの積をrigid integer（rigidモジュラス）とする。［ａ，ｂ）は、ａ以上ｂ未満の実数全体の集合を表す。【００３４】
θ、κ、μ、εをセキュリティパラメータとする。さらに、λ＝θ＋κ＋ε、γ＝λ＋μ＋ε＋８、Λ＝[０，２＾λ]∩Ｎ、Γ＝（２＾γ，２＾γ＋２＾λ）とする。【００３５】
本実施形態に係る装置の構成を図１に従って説明する。【００３６】
本実施形態に係る装置構成は、イッシュアー装置ＭＩ、ユーザ特定情報記憶装置ＭＬ、オープナー装置ＭＯ、ユーザ装置ＭＵ、及び検証装置ＭＶを有して構成される。【００３７】
本実施形態においては、５種類の装置がある場合を説明しているが、例えばイッシュアー装置ＭＩの機能とオープナー装置ＭＯの機能を同じ装置内に実装するというように、一台の装置が複数の装置の機能を兼ね備える構成としてもよい。また、図には各種類の装置がそれぞれ一台ずつしかない場合が描かれているが、各種類の装置が複数台あってもよい。【００３８】
イッシュアー装置ＭＩ、ユーザ特定情報記憶装置ＭＬ、オープナー装置ＭＯ、ユーザ装置ＭＵ、及び検証装置ＭＶは、それぞれ通信手段（ＭＩＣ、ＭＬＣ、ＭＯＣ、ＭＵＣ、ＭＶＣ）を有し、これらの通信手段を用いて他の装置と通信する。通信手段としては、例えばインターネットを利用したもの、無線を利用したもの、電話線を用いたものを用いることができるが、これらに限定されるものではない。【００３９】
イッシュアー装置ＭＩ、オープナー装置ＭＯ、ユーザ装置ＭＵ、及び検証装置ＭＶは、それぞれ公開情報記憶部（ＭＩＩ、ＭＯＩ、ＭＵＩ、ＭＶＩ）を有し、ここに他の装置が公開している公開情報を記憶する。【００４０】
他の装置が公開している公開情報を入手する方法としては例えば通信手段を使って入手する方法、公開情報を保管する為の専用装置を作成してそこから入手するといった方法があるが、これらに限定されるものではない。また、各装置がいつ他の装置の公開情報を入手するのかは問わない。【００４１】
次に、通信手段、公開情報記憶部が有する手段、及び記憶部について説明する。【００４２】
イッシュアー装置は、イッシュアーズセキュリティパラメータ入力手段ＦＩＡ、イッシュアーズ鍵ペア生成手段ＦＩＧ、秘密鍵記憶部ＭＩＳ、公開鍵記憶部ＭＩＰ、イッシュイング手段ＦＩＩを有している。【００４３】
また、イッシュアーズ鍵ペア生成手段ＦＩＧは、サブルーチンとしてイッシュアーズ鍵正当性証明文作成手順ＳＩＰを有している。【００４４】
また、イッシュイング手段ＦＩＩは、サブルーチンとして第一検証手順ＳＩ１Ｖと第二検証手順ＳＩ２Ｖを有している。【００４５】
オープナー装置ＭＯは、オープナーズセキュリティパラメータ入力手段ＦＯＡ、オープナーズ鍵ペア生成手段ＦＯＧ、公開鍵記憶部ＭＯＰ、秘密鍵記憶部ＭＯＳ、オープン手段ＦＯＯ、及び出力手段ＦＯＢを有している。【００４６】
また、オープナーズ鍵ペア生成手段ＦＯＧは、サブルーチンとして暗号用鍵ペア生成手順ＳＯＧを有している。【００４７】
ユーザ特定情報記憶装置ＭＬは、ユーザ特定情報リスト記憶部ＭＬＬを有している。【００４８】
ユーザ装置ＭＵは、ジョイニング手段ＭＵＪ、平文入力手段ＦＵＭ、署名手段ＦＵＳ、及び出力手段ＦＯＢを有している。【００４９】
また、ジョイニング手段ＭＵＪは、イッシュアーズ鍵正当性証明文検証手順ＳＵＶ、第一検証手順ＳＵ１Ｐ、及び第一検証手順ＳＵ２Ｐを有している。【００５０】
また、署名手段ＭＵＳは、サブルーチンとして暗号化手順ＳＵＥ、知識の署名作成手順ＳＵＳを有している。【００５１】
検証装置ＭＶは、検証手段ＦＶＶ、及び出力手段ＦＶＢを有している。【００５２】
また、検証手段ＦＶＶは、サブルーチンとして知識の署名検証手順ＳＶＶを有している。【００５３】
次に、各装置の動作について説明する。【００５４】
イッシュアー装置ＭＩは、ユーザ装置からなるグループを運営しており、ユーザ装置ＭＵをグループに追加する。グループのメンバーであるユーザ装置ＭＵは、グループの一員としての署名文を作成することができる。検証装置ＭＶは、署名文の正当性を検証できる。オープナー装置ＭＯは、ユーザ特定情報記憶装置ＭＬと通信することにより署名文を作成したユーザ装置を特定する。ユーザ特定情報記憶装置ＭＬは、ユーザ装置の特定に必要な情報であるユーザ特定情報という情報と各ユーザ装置とを何らかの形で対応付けした表を記憶している。対応法の例としては、各ユーザ装置にＩＤを割り振り、各ユーザ装置のユーザ特定情報とユーザ装置のＩＤとを対応させるという方法がある。以下この方法により対応付けがなされている場合について説明する。【００５５】
イッシュアー装置ＭＩは、まず、セキュリティパラメータθ,μ,εを受け取ると、θ,μ,εを公開情報記憶部ＭＩＩに格納する（ＦＩＡ）。【００５６】
オープナー装置ＭＯは、まずセキュリティパラメータκを受け取ると、κを公開情報記憶部ＭＯＩに格納する（ＦＯＡ）。【００５７】
次に、イッシュアー装置ＭＩは、θ、μ、ε、κを入力としてイッシュアーズ鍵ペア生成手段ＦＩＧにおける処理を経て、イッシュアーズ公開鍵ｉｐｋとイッシュアーズ秘密鍵ｉｓｋとを作成し、イッシュアーズ公開鍵ｉｐｋを公開鍵記憶部ＭＩＰ、イッシュアーズ秘密鍵ｉｓｋを秘密鍵記憶部ＭＩＳに格納する。【００５８】
次に、オープナー装置ＭＯは、θ、μ、ε、κを入力としてイッシュアーズ鍵ペア生成手段ＦＯＧにおける処理を経て、オープナー公開鍵ｏｐｋとオープナー秘密鍵ｏｓｋとを作成し、オープナー公開鍵ｏｐｋを公開鍵記憶部ＭＯＰ、オープナー秘密鍵ｏｓｋを秘密鍵記憶部ＭＯＳに格納する。【００５９】
ユーザ装置ＭＵは、イッシュアー装置ＭＩと通信を行うことによりグループに加わることができる。ユーザ装置ＭＵとイッシュアー装置ＭＩとの通信は、通信装置（ＭＩＣ、ＭＵＣ）によって行われる。グループに加わる際、イッシュアー装置ＭＩはイッシュイング手段ＦＩＩにおける処理を実行する。ユーザ装置ＭＵは、ジョイニング手段ＦＵＪにおける処理を実行する。イッシュイング手段ＦＩＩは、θ、μ、ε、κ、イッシュアーズ公開鍵ｉｐｋ、オープナー公開鍵ｏｐｋ、イッシュアーズ秘密鍵ｉｓｋを入力として用い、ジョイニング手段ＦＵＪはθ、μ、ε、κ、イッシュアーズ公開鍵ｉｐｋ、オープナー公開鍵ｏｐｋを入力として用いる。【００６０】
これらの手段における処理を実行することにより、ユーザ装置ＭＵの公開鍵ｕｐｋ、秘密鍵ｕｓｋ、ユーザ特定情報ｕｔｉが生成される。また、これらの手段が終了するまでにユーザ特定情報ｕｔｉがユーザ特定情報記憶装置のユーザ特定情報記憶部ＭＬＬに記憶される。また、ユーザ装置ＭＵは、公開鍵ｕｐｋ、秘密鍵ｕｓｋをそれぞれ公開鍵記憶部ＭＵＰ、秘密鍵記憶部ＭＵＳに書き込む。【００６１】
グループのメンバーであるユーザ装置ＭＵは、署名文を作成することができる。ユーザ装置ＭＵは、平文入力手段ＦＵＭからメッセージＭを受け取り、メッセージＭ、公開鍵ｕｐｋ、秘密鍵ｕｓｋ、及び公開情報（θ、μ、ε、κ、イッシュアーズ公開鍵ｉｐｋ、オープナー公開鍵ｏｐｋ）を用いて署名手段ＭＵＳにおける処理を実行することにより、署名文Signatureを作成する。ユーザ装置ＭＵは、作成した署名文Signatureを出力手段ＦＯＢにより出力する。【００６２】
検証装置ＭＶは、検証手段ＦＶＶにおける処理を実行することにより、署名文Signatureの正当性を検証する。検証手段ＦＶＶは、メッセージＭ、署名文Signature、及び公開情報（θ、μ、ε、κ、イッシュアーズ公開鍵ｉｐｋ、オープナー公開鍵ｏｐｋ）を入力として用いる。【００６３】
検証手段ＦＶＶは、署名文Signatureが正当なものである旨を示すメッセージ、又は署名文Signatureが不当なものである旨の示すメッセージを出力する。以下、署名文Signatureが正当なものであることを示すメッセージをACCEPT、署名文Signatureが不当なものであることを示すメッセージをREJECTとする。検証手段ＦＶＶは、検証結果を出力手段ＦＶＢによって出力する。【００６４】
オープナー装置ＭＯは、オープン手段ＦＯＯにおける処理を実行することにより、署名文Signatureを作成したユーザ装置を特定する。オープン手段ＦＯＯは、メッセージＭ、署名文Signature、秘密鍵ｏｓｋ、および公開情報（θ、μ、ε、κ、イッシュアーズ公開鍵ｉｐｋ、オープナー公開鍵ｏｐｋ）を入力として用いる。【００６５】
オープン手段ＦＯＯは、ユーザ特定情報記憶装置ＭＬがユーザ特定情報リスト記憶部に保管しているデータを用いて署名文Signatureを作成したユーザ装置を特定する。そして、どのユーザ装置が署名文Signatureを作成したのかを出力手段ＦＯＢによって出力する。【００６６】
図２を用いイッシュアーズセキュリティパラメータ入力手段ＦＩＡにおける具体的な処理について説明する。【００６７】
まず、イッシュアーズセキュリティパラメータ入力手段ＦＩＡは、セキュリティパラメータθ、μ、εを公開情報記憶部ＭＩＩから読み込み（ＦＩＡ１）、θ、μ、εを公開情報記憶部に書き込む（ＦＩＡ２）。【００６８】
図２を用いイッシュアーズ鍵ペア生成手段ＦＩＧにおける具体的な処理について説明する。【００６９】
イッシュアーズ鍵ペア生成手段ＦＩＧは、まずθ、κ、εを公開情報記憶部から読み込み（ＦＩＧ１）、θ／２ビットの素数ｐ＿１、ｐ＿２をランダムに選択する（ＦＩＧ２）。次に、ｎ＝ｐ＿１ｐ＿２を算出し（ＦＩＧ３）、ａ∈ＱＲ（ｎ）をランダムに選択する（ＦＩＧ４）。次に、κ＋εビットの数Ｔ＿｛０｝、Ｔ＿｛１｝、Ｔ＿｛２｝をランダムに選択する（ＦＩＧ５）。次にａ＿０＝ａ＾｛Ｔ＿｛０｝｝，ｇ＝ａ＾｛Ｔ＿｛１｝｝，ｈ＝ａ＾｛Ｔ＿｛２｝｝ｍｏｄｎを算出する（ＦＩＧ６）。【００７０】
次に、イッシュアーズ鍵正当性証明文作成手順ＳＩＰを実行し、Proof＿｛Iss｝を作成する（ＦＩＧ７）。【００７１】
次に、イッシュアーズ公開鍵ｉｐｋ＝（ｎ，ａ，ａ＿０，ｇ，ｈ，Proof＿[Iss]）とし、イッシュアーズ公開鍵ｉｐｋを公開鍵記憶装置に保存する（ＦＩＧ８）。【００７２】
次にイッシュアーズ秘密鍵ｉｓｋ＝（ｐ＿１，ｐ＿２）とし、秘密記憶装置に保存する（ＦＩＧ９）。安全性の観点から、イッシュアーズ鍵正当性証明文作成手順ＳＩＰに従ってProof#[Iss]を作成し、イッシュアーズ公開鍵ｉｐｋ＝（ｎ，ａ，ａ＿０，ｇ，ｈ，Proof#[Iss]）とすることが望ましいが、イッシュアーズ鍵正当性証明文作成手順ＳＩＰを省略してイッシュアーズ公開鍵ｉｐｋ＝（ｎ，ａ，ａ＿０，ｇ，ｈ）とすることもできる。イッシュアーズ鍵正当性証明文作成手順ＳＩＰを省略する場合には、ジョイニング手段ＦＵＪにおけるイッシュアーズ鍵正当性証明文検証手順ＳＵＶも省略する。また、Proof#[Iss]の作成を省略する場合には、ａ＿０、ｇ、ｈの生成方法を簡略化できる。ＦＩＧ５及びＦＩＧ６における操作を省略し、単にＱＲ（ｎ）からａ＿０,ｇ，ｈをランダムに選択する。【００７３】
また、上記の例においてはイッシュアーズ公開鍵ｉｐｋ＝（ｎ，ａ，ａ＿０，ｇ，ｈ，Proof#[Iss]）として（ｎ，ａ，ａ＿０，ｇ，ｈ）とProof#[Iss]とをセットにして公開する場合について述べたが、（ｎ，ａ，ａ＿０，ｇ，ｈ）とProof#[Iss]とを別々に公開してもよい。【００７４】
図３に従ってオープナーズセキュリティパラメータ入力手段ＦＯＡの具体的な動作について説明する。【００７５】
オープナーズセキュリティパラメータ入力手段ＦＯＡは、κを読み込み（ＦＯＡ１）、κを公開情報記憶部に書き込む（ＦＯＡ２）。【００７６】
次に、図３に従ってオープナーズ鍵ペア生成手段ＦＯＧの具体的な動作について説明する。【００７７】
オープナーズ鍵ペア生成手段ＦＯＧは、まずκを公開情報記憶部ＭＯＩから読み込む（ＦＯＧ１）。次に、群の記述Ｖ、群位数ｑ、群の基点Ｇを読み込む（ＦＯＧ２）。なお、ＦＯＧ２における処理の詳細については、後述する。【００７８】
次に、暗号用鍵ペア生成手順に従って、暗号用鍵ペア（ｅｐｋ，ｅｓｋ）を作成する（ＦＯＧ３）。そして、オープナー公開鍵ｏｐｋ＝（Ｖ，ｑ，Ｇ，ｅｐｋ）として公開鍵記憶装置に保存する（ＦＯＧ４）。次に、イッシュアーズ秘密鍵ｉｓｋ＝ｅｓｋとし、秘密記憶装置に保存する（ＦＯＧ５）。【００７９】
なお、ＦＯＧ２において、群の記述Ｖ、群位数ｑ、群の基点Ｇをどの装置がどのような方法で作成し、オープナー装置がどのような方法でこれらを入手するのかは問わない。また安全性の観点から群上のDecision Diffie Hellman問題が困難であることが望ましいが、どのような群を用いるのかは問わない。Decision Diffie Hellman問題が困難であると予想されている群の例としては、巡回群における乗法群の素数位数の部分群や楕円曲線群の素数位数の部分群がある。【００８０】
図４から６に従ってイッシュイング手段ＦＩＩとジョイニング手段ＦＵＪにおける処理について説明する。【００８１】
イッシュアー装置ＭＩは、(θ,μ,ε,κ,ｉｐｋ，ｏｐｋ，ｉｓｋ)を公開情報記憶部ＭＩＩから読み込む（ＦＩＩ１）。ユーザ装置ＭＵは、（θ,μ,ε,κ,ｉｐｋ，ｏｐｋ）を公開情報記憶部ＭＵＩから読み込み（ＦＵＪ１）、イッシュアー公開鍵正当性証明文検証手順に従ってProof#[Iss]の正当性を確認する（ＦＵＪ２）。次に、ユーザ装置ＭＵは、（Ｖ，ｑ，Ｇ）の正当性を確認する（ＦＵＪ３）。なお、安全性の観点からＦＵＪ３における処理を実行することが望ましいが、効率化の為にＦＵＪ３を省略することも可能である。次に、ユーザ装置ＭＵは、ランダムにx'∈Λ、r∈[０，２＾[θ＋ε]]を選択し、Ｃ＝ａ＾｛ｘ'｝を算出する（ＦＵＪ４）。【００８２】
次に、ユーザ装置ＭＵは、第一証明手順ＳＵ１Ｐにおける処理によってＣの正当性証明文Proof#[C]を作成し、区間証明手順ＳＵＩＰに従ってｘ’がΛの元であることを証明する正当性証明文ProofI#[C]を作成する（ＦＵＪ５）。【００８３】
次に、ユーザ装置ＭＵは、通信手段ＭＵＣを用いてＣ、Proof#[C]、及びProofI#[C]をイッシュアー装置ＭＩに送信する（ＦＵＪ６）。【００８４】
一方、イッシュアー装置ＭＩは、通信手段ＭＩＣを用いてＣ、Proof#[C]、ProofI#[C]を受信し（ＦＩＩ２）、第一検証手順ＳＩ１Ｖに従ってProof#[C]の正当性を検証し、区間検証手順ＳＩＩＶに従ってProofI#[C]の正当性を証明する。そして、Proof#[C]、及びProofI#[C]の少なくとも一方が正当でなければ終了する（ＦＩＩ３、ＦＩＩ４ＦＩＩ５）。なお、安全性の観点からＦＵＪ６、ＦＩＩ２、ＦＩＩ３、ＦＩＩ４、ＦＩＩ５を実行することが望ましいが、効率化の為にＦＵＪ６、ＦＩＩ２、ＦＩＩ３、ＦＩＩ４、ＦＩＩ５を省略することも可能である。【００８５】
次に、イッシュアー装置ＭＩは、ランダムにｘ''∈Λを選択し（ＦＩＩ６）、通信手段ＭＩＣを用いてｘ''を送信する（ＦＩＩ７）。ユーザ装置ＭＵは、通信手段ＭＵＣを用いてｘ''を受信し（ＦＵＪ７）、ｘ＝ｘ'＋ｘ''ｍｏｄ２＾λとする（ＦＵＪ８）。さらに、ユーザ装置ＭＵは、β＝ａ＾ｘｍｏｄｎを算出する（ＦＵＪ９）。次に、ユーザ装置ＭＵは、Ｂ＝ｘＧを算出する（ＦＵＪ１０）。【００８６】
そして、ユーザ装置ＭＵは、通信手段を用いて（ｉ，Ｂ）をユーザ特定情報リスト記憶装置ＭＬに送信し（ＦＵＪ１１）、ユーザ特定情報リスト記憶装置ＭＬは通信装置ＭＬＣを用いて（ｉ，Ｂ）を受信し（ＦＬＲ１）、ユーザ特定情報リスト記憶部ＭＬＬに保存する（ＦＬＲ２）。【００８７】
イッシュアー装置ＭＩは、イッシュイング手段ＦＩＩの処理を継続する前に（ｉ，Ｂ）がユーザ特定情報リスト記憶部ＭＬＬに格納されているか否かを確認する（ＦＩＩ９）。したがって、イッシュアー装置ＭＩは、ユーザ特定情報リスト記憶装置ＭＬから（ｉ，Ｂ）を受信する（ＦＬＲ３，ＦＩＩ８）。受信に失敗した場合、イッシュアー装置ＭＩは、イッシュイング手段における処理を終了する（ＦＩＩ１０）。なお、安全性の観点からＦＩＩ（８、９、１０）及びＦＬＲ３における処理を実行することが望ましいが、効率化の為にＦＩＩ（８、９、１０）及びＦＬＲ３における処理を省略し、ユーザ装置ＭＵから直接（ｉ，Ｂ）を受信してもよい。なお、（ｉ，Ｂ）の送受信には、通信装置（ＭＬＣ，ＭＩＣ）を用いる。（ｉ，Ｂ）の送受信は、イッシュアー装置ＭＩが先に（ｉ，Ｂ）の送信要求を出してからユーザ特定情報リスト記憶装置ＭＬが送信を行う場合と送信要求なしにユーザ特定情報リスト記憶装置ＭＬがイッシュアー装置ＭＩに（ｉ，Ｂ）を送信する場合がある。【００８８】
次に、ユーザ装置ＭＵは、第二証明手段ＳＵ２Ｐにおける処理を実行し、（β，Ｂ）の正当性証明文Proof#[(β,Ｂ)]を作成し（ＦＵＪ１２）、通信手段を用いてProof#[(β,Ｂ)]を送信する（ＦＵＪ１３）。イッシュアー装置ＭＩは、通信手段を用いてProof#[(β,Ｂ)]を受信し（ＦＩＩ１１）、Proof #[(β,Ｂ)]が正当であるか否かを確認する（ＦＩＩ１２）。ここで、Proof #[(β,Ｂ)]の正当性が確認されなかった場合、イッシュアー装置ＭＩはイッシュイング手段を終了する（ＦＩＩ１３）。なお、安全性の観点からＦＵＪ（１２、１３）、ＦＩＩ（１１、１２、１３）における処理を実行することが望ましいが、効率化の為にＦＵＪ（１２、１３）、ＦＩＩ（１１、１２、１３）における処理を省略してもよい。【００８９】
Proof #[(β,Ｂ)]の正当性が確認された場合、イッシュアー装置ＭＩはｅ∈Γとなる素数をランダムに選択し（ＦＩＩ１４）、ｂ＝（β，ａ＿０）＾｛１／ｅ｝ｍｏｄｎを算出する（ＦＩＩ１５）。算出された（ｅ，ｂ）は通信手段ＭＵＣによってユーザ装置ＭＵに送信される（ＦＩＩ１６）。【００９０】
ユーザ装置ＭＵは、（ｅ，ｂ）を受信し（ＦＵＪ１４）、ａ＾ｘａ＿０＝ｂ＾ｅｍｏｄｎが成立するか否かを判定し、成立しない場合、ジョイニング手段ＦＵＪを終了する（ＦＵＪ１５、ＦＵＪ１６）。次に、ユーザ装置ＭＵは、ｅ∈Γが成立するか否かを判定し、もしe∈Γが成立しない場合、ジョイニング手段ＦＵＪにおける処理を終了する（ＦＵＪ１７、ＦＵＪ１８）。なお、安全性の観点からＦＵＪ（１７、１８）を行うことが望ましいが、効率化の為に省略してもよい。【００９１】
次に、ユーザ装置ＭＵは、（β，ｂ，Ｂ）を公開鍵記憶部に格納し（ＦＵＪ１９）、さらにｘを秘密鍵記憶部に格納する（ＦＵＪ２０）。【００９２】
次に、図７を用いて署名手段ＭＵＳにおける処理について説明する。【００９３】
署名装置ＭＵは、まず（θ，μ，ε，κ，イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ，公開鍵ｕｐｋ，秘密鍵ｕｓｋ）を読み込み（ＦＵＳ１）、暗号化手順ＳＵＥに従って処理を実行し、Ｂの暗号文Cipherを作成する（ＦＵＳ２）。次に、書名作成手順ＳＵＳに従って処理を実行し、知識の署名Proof(M)を作成し（ＦＵＳ３）、（Cipher，Proof(M)）を署名文としてセットし、出力する（ＦＵＳ４）。【００９４】
図７を用いて検証手順ＦＶＶについて説明する。【００９５】
検証装置ＭＶは、まず（θ，μ，ε，κ，イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ，Signature）を読み込む（ＦＶＶ１）。次に、知識の署名検証手順を行い、Proof(M)の正当性を検証する（ＦＶＶ２）。そして、Proof(M)が正当なら正当である旨のメッセージを出力し（ＦＶＶ４）、Proof(M)が正当でないならば不当である旨のメッセージを出力する（ＦＶＶ５）。【００９６】
図８を用いてオープン手段における処理について説明する。【００９７】
オープナー装置ＭＯは、まず（θ，μ，ε，κ，イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ，オープナー秘密鍵ｏｓｋ）を読み込む（ＦＯＯ１）。次に、知識の署名検証手順に従って処理を実行し、Proof(M)の正当性を検証し（ＦＯＯ２）、復号手順を行ってCipherを復号し（ＦＯＯ３）、通信装置を用いてＢをユーザ特定情報記憶装置ＭＬに送信する（ＦＯＯ４、ＦＯＯ５）。【００９８】
ユーザ特定情報記憶装置ＭＬは、Ｂを受信すると（ＦＬＯ１）、Ｂに対応するユーザのＩＤであるユーザ名ｉを検索し、ユーザ名ｉを保持している場合は通信装置を用いてオープナー装置ＭＯに送信する（ＦＬＯ２）。一方、ユーザ名ｉを保持していなかった場合は、ユーザ名ｉを保持していない旨をオープナー装置ＭＯに通知する。【００９９】
オープナー装置ＭＯは、ユーザ特定情報記憶装置ＭＬからの返信を受信し（ＦＯＯ５）、ユーザ特定情報記憶装置ＭＬから受信した返信がユーザ名ｉであった場合は、ユーザ名ｉを出力して停止し（ＦＯＯ６、ＦＯＯ７）、ユーザ名ｉでなかった場合はユーザ名ｉが存在しない旨を示すメッセージを出力して停止する。【０１００】
なお、本実施形態では、オープナー装置ＭＯがユーザ名Ｉ（又はユーザ名ｉが存在しない旨を示すメッセージ）を出力する場合について説明したが、ユーザ特定情報記憶装置ＭＬがユーザ名Ｉ（又はユーザ名ｉが存在しない旨を示すメッセージ）を出力してもよい。【０１０１】
次に、図９を用いて暗号用鍵ペア生成手順について説明する。【０１０２】
まず、ユーザ特定情報記憶装置ＭがＬκを読み込み（ＳＯＧ１）、ランダムにｙ∈Ｚｑを選択し（ＳＯＧ２）、Ｑ＿１＝ｙＰとし（ＳＯＧ３）、さらにＱ＿２∈Ｇをランダムに選択する（ＳＯＧ４）。そして、（Ｐ，Ｑ＿１，Ｑ＿２）を公開鍵とし（ＳＯＧ５）、ｙを秘密鍵とする（ＳＯＲ６）。【０１０３】
図９を用いて暗号化手順について説明する。【０１０４】
ユーザ装置ＭＵは、まずκ及び暗号鍵ペアｅｐｋを読み込み（ＦＯＧ１）、ρ∈Ｚｑをランダムに選択する（ＦＯＧ２）。次に、（Ｇ'，Ｈ'，Ｈ'＿１，Ｈ'＿２）＝（ρＧ，Ｂ＋ρＨ＿１，Ｂ＋ρＨ＿２）を算出し（ＦＯＧ３）、暗号文（Ｇ'，Ｈ'＿１，Ｈ'＿２）を出力する（ＦＯＧ４）。【０１０５】
図９を用いて復号化手順について説明する。【０１０６】
オープナー装置ＭＯは、まず暗号鍵ペア（ｅｐｋ、ｅｓｋ）を読み込み（ＦＯＤ１）、Ｍ＝Ｇ'−ｘＨ＿１'を算出し（ＦＯＤ２）、平分Ｍを出力する（ＦＯＤ３）。【０１０７】
図１０を用いてイッシュアーズ鍵正当性証明文作成手順について説明する。【０１０８】
イッシュアー装置ＭＩは、ａ＿１＝ｇ，ａ＿２＝ｈｍｏｄｎとし（ＳＩＰ１）、ｉ＝０，１，２に対してＳ＿｛ｉ｝＝Ｔ＿｛ｉ｝＾｛−１｝ｍｏｄφ（ｎ）を算出する（ＳＩＰ２）。次に、イッシュアー装置ＭＩは、ｉ＝０，１，２に対しκ＋εビットの数Ｓ'＿｛ｉ｝を選択し（ＳＩＰ３）、さらにｉ＝０，１，２に対しκ＋εビットの数Ｔ'＿｛ｉ｝を選択する（ＳＩＰ４）。次に、ｂ'＿ｉ＝ａ＾｛Ｓ'＿｛ｉ｝｝ｍｏｄｎ、ａ'＿ｉ＝ａ＿ｉ＾｛Ｔ'＿｛ｉ｝｝ｍｏｄｎ、ｃ＝Ｈａｓｈ＿｛κ＋ε＋μ｝（｛ａ＿ｉ｝，｛ｂ'＿ｉ｝，｛ａ'＿ｉ｝）を算出する（ＳＩＰ５、ＳＩＰ６、ＳＩＰ７）。【０１０９】
次に、イッシュアー装置ＭＩは、ｉ＝０，１，２についてＳ''｛ｉ｝＝ｃＳ＿｛ｉ｝＋Ｓ'＿｛ｉ｝、及びＴ''＿｛ｉ｝＝ｃＴ＿｛ｉ｝＋Ｔ'＿｛ｉ｝を算出し（ＳＩＰ８、ＳＩＰ）、（ｃ，｛Ｓ''＿｛ｉ｝｝，｛Ｔ＿｛ｉ｝｝）を出力する（ＳＩＰ１０）。【０１１０】
図１１を用いて知識の署名作成手順ＳＵＳについて説明する。【０１１１】
ユーザ装置ＭＵは、まず（θ，μ，ε，κ，イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ，公開鍵ｕｐｋ，秘密鍵ｕｓｋ）を読み込み（ＳＵＳ１）、ｓ，ｔ，ｕ∈（０，２＾｛θ＋ε｝）∩Ｎを選択し（ＳＵＳ２）、χ＿ｂ＝ｂｈ＾ｕｍｏｄｎを算出する（ＳＵＳ３）。次に、（χ＿ｅ，χ＿ｕ）＝（ｇ＾｛ｅ−２＾｛γ｝｝ｈ＾ｓ，ｇ＾ｕｈ＾ｔ）ｍｏｄｎを算出し（ＳＵＳ４）、｜｜ｘ'｜｜＝｜｜ｅ'｜｜＝λ＋θ＋２ε＋μを満たす正数ｘ'，ｅ'，ｕ'，ｓ'，ｔ'，ｕ'＿ｅ，ｔ'＿ｅをランダムに選択する（ＳＵＳ５）。次に、ρ'∈Ｚｑをランダムに選択し（ＳＵＳ６）、ｄ＿１＝ａ＾｛−ｘ'｝χ＿ｂ＾｛ｅ'｝ｈ＾｛−（ｕ'＿ｅ＋２＾｛γ｝ｕ'）｝ｍｏｄｎを算出する（ＳＵＳ７）。次に、ｄ＿２＝χ＿ｕ'｛−ｅ｝ｇ＾｛ｕ'＿ｅ｝ｈ＾｛ｔ'＿ｅ｝ｍｏｄｎを算出し（ＳＵＳ８）、（ｄ＿ｅ，ｄ＿ｕ）＝（ｇ＾｛ｅ'｝ｈ＾｛ｓ'｝，ｇ＾｛ｕ'｝ｈ｛ｔ'｝）ｍｏｄｎを算出する（ＳＵＳ９）。次に、（Ｕ，Ｖ＿１，Ｖ＿２）＝（ρ'Ｇ，ｘ'Ｇ＋ρ'Ｈ＿１，ｘ'Ｇ＋ρ'Ｈ＿２）を算出し（ＳＵＳ１０）、Ｃｏｍｍｉｔ＝（χ＿ｂ，（χ＿ｅ，χ＿ｕ），ｄ＿１，ｄ＿２，（ｄ＿ｅ，ｄ＿ｕ），（Ｕ，Ｖ＿１，Ｖ＿２））とする（ＳＵＳ１１）。１＝Ｈａｓｈ＿｛μビットの正数｝｛イッシュアーズ秘密鍵ｉｐｋ，オープナー公開鍵ｏｐｋ，Cipher，Commit，Ｍ｝とする（ＳＵＳ１２）。次に、ｘ''＝ｌｘ＋ｘ'，ｅ''＝ｌ（ｅ−２＾｛γ｝）＋ｅ'、ｕ''＝ｌｕ＋ｕ'、ｓ''＝ｌｓ＋ｓ'、ｔ''＝ｌｔ＋ｔ'、ｕ''＿ｅ＝ｌｕ（ｅ−２＾｛γ｝）＋ｅ'＋ｕ'＿ｅ、ｔ''＿ｅ＝ｌｔ（ｅ―２＾｛γ｝）＋ｔ'＿ｅ、ρ''＝ｌρ＋ρ'を算出する（ＳＵＳ１３）。次に、Response＝（ｘ''，ｅ''，ｕ''，ｓ''，ｔ''，ｕ''＿ｅ，ｔ''＿ｅ，ρ''）とし（ＳＵＳ１４）、Signature＝（（χ＿ｂ，（χ＿ｅ，χ＿ｕ）），ｌ，Response）を出力する（ＳＵＳ１５）。【０１１２】
図１２を用いて知識の署名検証手順について説明する。【０１１３】
検証装置ＭＶは、（Ｍ，Signature）が入力されると、（θ，μ，ε，κ，イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ）を読み込む（ＳＶＶ１）。ここで、Signature＝（Cipher，（χ＿ｂ，（χ＿ｅ，χ＿ｕ）），ｌ，Response）であり、Cipher＝（Ｇ'，Ｈ'＿１，Ｈ'＿２）、かつResponse＝（ｘ''，ｅ''，ｕ''，ｓ''，ｔ''，ｕ''＿ｅ，ｔ''＿ｅ，ρ''）である。次に、検証装置ＭＶは、ｄ＿１＾＊＝ａ＿０＾｛−１｝ａ＾｛−ｘ''｝χ＿ｂ＾｛ｅ''＋ｌ２＾｛γ｝｝ｈ＾｛−（ｕ''＿ｅ＋２＾｛γ｝ｕ''）｝ｍｏｄｎを算出する（ＳＶＶ２）。次に、ｄ＿２＾＊＝χ＿ｕ｛−ｅ''｝ｇ＾｛ｕ''＿ｅ｝ｈ＾｛ｔ''＿ｅ｝ｍｏｄｎを算出する（ＳＶＶ３）。次に、（ｄ＿ｅ＾＊，ｄ＿ｕ＾＊）＝（χ＿ｅ＾｛−１｝ｇ＾｛ｅ''｝ｈ＾｛ｓ''｝，χ＿ｕ＾｛−１｝ｇ＾｛ｕ''｝ｈ＾｛ｔ''｝）ｍｏｄｎを算出する（ＳＶＶ４）。次に、（Ｕ＾＊，Ｖ＿１＾＊，Ｖ＿２＾＊）＝（−ｌＰ＋ρ''Ｇ，−ｌＱ＿１＋ｘ''Ｇ＋ρ''Ｈ＿１，−ｌＱ＿２＋ｘ''Ｇ＋ρ''Ｈ＿２）を算出する（ＳＶＶ５）。次に、Commit＾＊＝（χ＿ｂ，（χ＿ｅ，χ＿ｕ），ｄ＿１＾＊，ｄ＿２＾＊，（ｄ＿ｅ＾＊，ｄ＿ｕ＾＊），（Ｕ＾＊，Ｖ＿１＾＊，Ｖ＿２＾＊））とする（ＳＶＶ６）。【０１１４】
次に、検証装置ＭＶは、ｌ＝Ｈａｓｈ＿｛μビットの正数｝（イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ，Commit^＊，Cipher，Response，Ｍ）が成立するか否かを確認し（ＳＶＶ７）、成立しない場合はRejectを出力する（ＳＶＶ１０）。そして、最後に、｜｜ｘ''｜｜，｜｜ｅ''｜｜＜λ＋ε＋μ＋１が成立するか否かを確認し（ＳＶＶ８）、成立する場合はAcceptを出力し（ＳＶＶ９）、不成立の場合はRejectを出力する（ＳＶＶ１０）。【０１１５】
次に、ストレートラインエクストラクタブルによってＣの正当性を証明する第一証明手順について図１３を用いて説明する。なお、ストレートラインエクストラクダブルによる正当性の証明の具体的な手順については非特許文献１０を参照されたい。【０１１６】
ストレートラインエクストラクタブルによる正当性の証明方法はいくつかあるが、どの方法で行ってもよく、下記の方法に限定されるものではない。【０１１７】
Ｎ、νをセキュリティパラメータとする。ベクトルａの第ｉ成分をａ＿ｉと表す。さらに、＜・,・＞により内積を表す。すなわち、ベクトルａ，ｂの内積は、＜ａ，ｂ＞＝ａ＿１ｂ＿１＋・・・＋ａ＿Ｎｂ＿Ｎと表す。そして、Ｒ＿｛λ＋ε｝＝Ｚ∩［０，２＾｛λ＋ε｝］とする。さらに集合Ｘについて、Ｈ＿ＸによりＸ値ハッシュ関数をあらわす。【０１１８】
ユーザ装置ＭＵは、まずａ，Ｃ，ｘ'，イッシュアー公開鍵ｉｐｋの一部ｎ、及びＮ，ν，ε，λを読み込み（ＳＵＰ１Ｐ１）、Ｘ＿｛０１｝，．．．，Ｘ＿｛０Ｎ｝をＲ＿｛λ＋ε｝からランダムに選択する（ＳＵＰ１Ｐ２）。次に、各ｊについてＸ＿｛１ｊ｝＝ｘ'＋Ｘ＿｛０ｊ｝を算出し（ＳＵＰ１Ｐ３）、ｉ＝０，１についてＹ＿ｉ＝（Ｘ＿｛ｉ１｝，．．．，Ｘ＿｛ｉＮ｝とする（ＳＵＰ１Ｐ４）。次に、ランダムにνビットのビット列ｒを選択し（ＳＵＰ１Ｐ５）、Ｃ＿｛ｉｊ｝＝Ｈ＿｛｛０，１｝＾ν｝｛ａ，Ｃ，Ｘ＿｛ｉｊ｝，ｉ，ｊ，ｒ｝を算出する（ＳＵＰ１Ｐ６）。次に、Ｖ＝（ｕ＿１，．．．，ｕ＿Ｎ）＝Ｈ＿｛（Ｒ＿｛λ＋ε｝＼｛０｝）＾｛Ｎ｝｝（ａ，Ｃ，｛Ｃ＿｛ｉｊ｝｝）を算出する（ＳＵＰ１Ｐ７）。次に、Ｘ＝＜Ｖ，Ｙ＿０＞を算出し（ＳＵＰ１Ｐ８）、Ｌ＝ａ＾｛Ｘ｝を算出し（ＳＵＰ１Ｐ９）、Ｋ＝（ｃ＿１，．．．，ｃ＿Ｎ）＝Ｈ＿｛｛０，１｝＾Ｎ｝（ａ，Ｃ，｛Ｃ＿｛ｉｊ｝｝，Ｌ，ｒ）を算出し（ＳＵＰ１Ｐ１０）、さらに各ｊについてξ＿｛ｊ｝＝Ｘ＿｛ｃ＿ｊｊ｝を算出する（ＳＵＰ１Ｐ１１）。ここで、Ξ＝（ξ＿１，．．．，ξ＿λ）とし（ＳＵＰ１Ｐ１２）、最後に署名文（ｒ，｛Ｃ＿｛ｉｊ｝，Ｌ，Ξ｝を出力する（ＳＵＰ１Ｐ１３）。【０１１９】
次に、第一検証手段における具体的な処理について図１４を用いて説明する。【０１２０】
イッシュアー装置ＭＩは、まず（ａ，Ｃ，ｎ，（ｒ，｛Ｃ＿｛ｉｊ｝｝，Ｌ，Ξ），Ｎ，ν，ε，λ）を読み込み（ＳＩ１Ｖ１）、Ｖ＾＊＝（ｕ＿１＾＊，．．．，ｕ＿Ｎ＾＊）＝Ｈ＿｛（Ｒ＿｛λ＋ε｝＼｛０｝＾｛Ｎ｝）（ａ，Ｃ，｛Ｃ＿｛ｉｊ｝｝）を算出する（ＳＩ１Ｖ２）。次に、Ｋ＾＊＝（ｃ＿１＾＊，．．．，ｃ＿Ｎ＾＊）＝Ｈ＿｛｛０，１｝＾Ｎ｝（ａ，Ｃ，｛Ｃ＿｛ｉｊ｝｝，Ｌ，ｒ）を算出する（ＳＩ１Ｖ３）。次に、全てのｊについてＨ＿｛｛０，１｝＾｛ν｝｝（ａ，Ｃ，ξ＿｛ｊ｝，ｃ＿ｊ＾＊，ｊ，ｒ）＝Ｃ＿｛ｃ＿ｊｊ｝が成立するか否かを確認し、成立する場合はｂ＝acceptに、不成立の場合はｂ＝rejectにする（ＳＩ１Ｖ４）。そして、ｂがacceptか否かを確認し（ＳＩ１Ｖ５）、ｂがrejectならばｂを出力する。一方、ｂがacceptならイッシュアー装置ＭＩは、ｇ＾｛＜Ｖ＾＊，Ξ＞｝＝ｈ＾｛Ｖ＾＊，Ｋ＾＊＞｝Ｌが成立するか否かを確認し、ａ＾｛＜Ｖ＾＊，Ξ＞｝＝ｈ＾｛＜Ｖ＾＊，Ｋ＾＊＞｝Ｌ出ない場合はｂをrejectに更新し（ＳＩ１Ｖ６）、ｂを出力する。【０１２１】
区間証明手順ＳＵＩＰ及び区間検証手順ＳＩＩＶについて説明する。【０１２２】
前述のように、区間証明手順ＳＵＩＰは、Ｃのａを底とした離散対数ｘ'が区間Λに属していることを証明する正当性証明文ProofI#[C]を作成し、区間検証手順ＳＩＩＶはProofI#[C]の正当性を検証する。【０１２３】
区間証明手順ＳＵＩＰ・区間検証手順ＳＩＩＶは、離散対数が事前に定められた区間に属することを証明する証明検証方法であればいずれの方法を使用してもよい。このような証明検証方法としては、例えば非特許文献１１に記載された方法がある。【０１２４】
第二証明手順ＳＵ２Ｐの具体的な処理手順について図１５を用いて説明する。【０１２５】
まず、（β，Ｂ，ｘ，イッシュアーズ公開鍵ｉｐｋ、オープナー公開鍵ｏｐｋ）を読み込み（ＳＵ２Ｐ１）、λ＋μ＋εビットの正数ｘ'をランダムに選択する（ＳＵ２Ｐ２）。次に、β'＝β＾｛ｘ'｝ｍｏｄｎ，Ｂ'＝Ｂ＾｛ｘ'｝を算出し（ＳＵ２Ｐ３）、ｃ＝Ｈ＿｛｛０，１｝＾μ｝（β'，Ｂ'，β，Ｂ，ｘ，イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ）を算出する（ＳＵ２Ｐ４）。さらに、Ｘ＝ｃｘ＋ｘ'を算出し（ＳＵ２Ｐ６）、最後に（β'，Ｂ'，Ｘ）を出力する（ＳＵ２Ｐ６）。【０１２６】
第二検証手順ＳＩ２Ｖの具体的な処理手順について図１５を用いて説明する。【０１２７】
イッシュアー装置ＭＩは、まず（（β'，Ｂ'，Ｘ），イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ）を読み込み（ＳＩ２Ｖ１）、ｃ＝Ｈ＿｛｛０，１｝＾μ｝（β'，Ｂ'，β，Ｂ，ｘ，イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ）を算出する（ＳＩ２Ｖ２）。そして、Ｘ≦λ＋μ＋εビットが成立するか否かを確認し（ＳＩ２Ｖ３）、成立しない場合はrejectを出力する（ＳＩ２Ｖ６）。Ｘ≦λ＋μ＋εが成立する場合は、ａ＾Ｘ＝β＾ｃβ'ｍｏｄｎ、かつＸＧ＝ｃＢ＋Ｂ'が成立するか否かを確認する（ＳＩ２Ｖ４）。成立する場合は、acceptを出力し（ＳＩ２Ｖ５）、不成立の場合は、rejectを出力する（ＳＩ２Ｖ６）。【０１２８】
［第２の実施形態］
本実施形態の装置構成は、署名手段ＦＵＳ及び検証手段ＦＶＶを除き、第１の実施形態と同様である。【０１２９】
署名手段ＦＵＳは、第１の実施形態における署名手段ＦＵＳと同様にCommit，ｌ，Responseを生成する。そして、署名文として（Commit，Response）をセットする。【０１３０】
検証手段ＦＶＶにおける処理について図１６を用いて説明する。（Ｍ，Signature）が入力されると、検証装置ＭＶは、まず（θ，μ，ε，κ，イッシュアーズ公開鍵ｉｐｋ，オープナー公開鍵ｏｐｋ）を読み込む（ＳＶＶ１）。ただし、ここでSignature＝（Cipher，（Commit，Response）であり、Cipher＝（Ｇ'，Ｈ'＿１，Ｈ'＿２）、Commit＝（χ＿ｂ，（χ＿ｅ，χ＿ｕ），ｄ＿１，ｄ＿２，（ｄ＿ｅ，ｄ＿ｕ），（Ｕ，Ｖ＿１，Ｖ＿２））、かつResponse＝（ｘ''，ｅ''，ｕ''，ｓ''，ｔ''，ｕ''＿ｅ，ｔ''＿ｅ，ρ''）である。【０１３１】
検証手段ＦＶＶは、まず署名文の一部であるCommitを用い、ｌ＝Ｈａｓｈ＿｛μビットの正数｝（イッシュアーズ公開鍵ｉｐｋ、オープナー公開鍵ｏｐｋ，Cipher，Ｃｏｍｍｉｔ，Ｍ）を算出する（ＳＶＶ２）。そして、ｌを用いて第１の実施形態に係る検証手段ＦＶＶ（図１２に示す）のＳＶＶ２からＳＶＶ６と同様の処理により、Commit＾＊を算出する（ＳＶＶ３からＳＶＶ７）。次に、算出したCommit＾＊が署名文の一部であるCommit＾＊と一致するか否かを確認し、不一致の場合はRejectを出力する（ＳＶＶ８）。一致していた場合は、第１の実施形態に係る検証手段ＦＶＶ（図１２に示す）のＳＶＶ８以下と同様に、｜｜ｘ''｜｜，｜｜ｅ''｜｜＜λ＋ε＋μ＋１が成立するか否かを確認する（ＳＶＶ９）、成立する場合はAcceptを出力し（ＳＶＶ１０）、不成立の場合はRejectを出力する（ＳＶＶ１１）。【０１３２】
［第３の実施形態］
本実施形態においては、Identity Escrow方式を実現する。Identity Escrow方式については非特許文献１２を参照されたい。【０１３３】
本実施形態の装置構成は、第１の実施形態と類似するが（図１７に示す）、署名手段ＦＵＳの代わりに被認証手段ＦＵＡがあり、署名作成手順ＳＵＳの代わりに証明手順ＳＵＰがある。また、第１の実施形態の検証手段ＳＵＶと第３の実施形態の検証手段ＳＵＶとは異なる手段である。被認証手段ＦＵＡと検証手段ＳＵＶとは、互いに通信をしながら計算を進める。また、第１の実施形態と異なり、ユーザ装置ＭＵは署名を出力するための手段ＦＯＢを有しない。【０１３４】
被認証手段ＦＵＡ及び検証手段ＳＵＶにおける具体的な処理について説明する。まず、ユーザ装置ＭＵは、第１の実施形態に係る知識の署名手段と同じ方法で暗号化手順ＳＵＥを実行し、Ｂの暗号文Ｃｉｐｈｅｒを生成する（図９に示す）。【０１３５】
そして、ユーザ装置ＭＵは、証明手順ＳＵＰを開始し、検証装置は検証手段ＳＶＶにおける処理を開始する。証明手順ＳＵＰ及び検証手段ＳＶＶについて、図１８から図２１に即して説明する。【０１３６】
まず、ユーザ装置ＭＵは、第１の実施形態の署名手段ＦＵＳ（図１１に示す）のＳＵＳ２からＳＵＳ１１と同じ方法によりCommit＝（χ＿ｂ，（χ＿ｅ，χ＿ｕ），ｄ＿１，ｄ＿２，（ｄ＿ｅ，ｄ＿ｕ），（Ｕ，Ｖ＿１，Ｖ＿２））を算出する（ＳＵＳ２からＳＵＳ１１）。【０１３７】
次に、ユーザ装置ＭＵは、通信装置を用いてCommitを検証装置ＭＹに送信する（ＳＵＳ１２）。検証装置ＭＶは、Commitを受信すると（ＳＶＶ１）、μビットの正数lをランダムに選択し、通信装置を用いてｌをユーザ装置に送信する（ＳＶＶ２）。【０１３８】
ユーザ装置ＭＵは、ｌを受信すると（ＳＵＳ１３）、ｌを用いて第１の実施形態に係る署名手段ＦＵＳ（図１１に示す）のＳＵＳ１４と同様の方法に従ってResponseを算出し、通信装置を用いてResponseを検証装置ＭＶに送信する（ＳＵＳ１４，１５）。【０１３９】
検証装置ＭＶは、Responseを受信するとResponseとχ＿ｂ，（χ＿ｅ，χ＿ｕ）とを用いて第１の実施形態の検証手段ＦＶＶ（図１２に示す）のＳＶＶ１からＳＶＶ６と同様の計算を実行し、Commit＾＊を算出する（ＳＶＶ５からＳＶＶ１０）。【０１４０】
そして、検証装置ＭＶは、Commit＝Commit＾＊が成立するか否かを確認し（ＳＶＶ１１）、不成立の場合はRejectを出力しる（ＳＶＶ１４）。一方、成立した場合は、第１の実施形態に係る検証装置ＭＶ（図１２に示す）のＳＶＶ８以下の処理を実行する。【０１４１】
すなわち、｜｜ｘ''｜｜，｜｜ｅ''｜｜＜λ＋ε＋μ＋１であるか否かを判定し（ＳＶＶ１２）、成立する場合はAcceptを出力し（ＳＶＶ１３）、不成立の場合はRejectを出力する（ＳＶＶ１４）。【０１４２】
［第４の実施形態］
本実施形態は、第一証明手段ＳＵ１Ｐと第一検証手順ＳＩ１Ｖを除き、第１の実施形態と同様である。第１の実施形態で述べたように、第一証明手順ＳＵ１Ｐにはストレートラインエクストラクタブルの証明方法であればどのようなものを用いてもよい。しかし、本実施形態では、第１の実施形態とは異なるストレートラインエクストラクタブル証明方法を用いる。【０１４３】
第一証明手段ＳＵ１Ｐにおける処理について図２２を用いて説明する。【０１４４】
Ｎ、νをセキュリティーパラメータとする。【０１４５】
ユーザ装置ＭＵは、まず（ａ，Ｃ，ｘ'，ｎ，Ｎ，ν，ε，λ）を読み込み（ＳＵＰ１Ｐ１）、ｊ＝１，．．．，Ｎについてλ＋εビットの正数Ｘ＿｛０ｊ｝をランダムに選択する（ＳＵＰ１Ｐ２）。次に、ｊ＝１，．．．，ＮについてＸ＿｛１ｊ｝＝ｘ'＋Ｘ＿｛０ｊ｝をランダムに選択する（ＳＵＰ１Ｐ３）。ｉ＝０，１、ｊ＝１，・・・，Ｎについてεビットの正数ｒ＿｛ｉｊ｝をランダムに選択する（ＳＵＰ１Ｐ４）。【０１４６】
そして、ｊ＝１，・・・，ＮについてＣ＿｛ｉｊ｝＝Ｈａｓｈ＿｛｛０，１＾ν｝（ａ，Ｃ，Ｘ＿｛ｉｊ｝，ｒ＿｛ｉｊ｝）を算出し（ＳＵＰ１Ｐ５）、ｊ＝１，・・・，ＮについてＬ＿｛ｊ｝＝ａ＾｛Ｘ＿｛０ｊ｝｝ｍｏｄｎを算出する（ＳＵＰ１Ｐ６）。【０１４７】
次に、ｊ＝１，・・・，Ｎについてｃ＿ｊ＝Ｈａｓｈ＿｛｛０，１｝｝（ａ，Ｃ，Ｌ＿｛ｊ｝，ｊ）を算出し（ＳＵＰ１Ｐ７）、ｊ＝１，・・・，Ｎについてξ＿｛ｊ｝＝Ｘ＿｛ｃ＿ｊｊｊ｝とする（ＳＵＰ１Ｐ８）。そして、最後に、証明文（｛Ｃ＿｛ｉｊ｝｝，｛ｃ＿ｊ｝，｛ξ＿｛ｊ｝｝））を出力する（ＳＵＰ１Ｐ９）。【０１４８】
第一検証手順ＳＩ１Ｖについて図２２を用いて説明する。【０１４９】
イッシュアー装置ＭＩは、まず（ａ，Ｃ，ｎ，（｛Ｃ＿｛ｉｊ｝｝，｛ξ＿｛ｊ＊｝｝）を読み込み（ＳＩ１Ｖ１）、ｊ＝１，・・・，ＮについてＬ＿｛ｊ｝＾＊＝ａ＾｛ξ＿｛ｊ｝｝Ｃ＾｛−ｃ＿ｊ｝を算出する（ＳＩ１Ｖ２）。【０１５０】
次に、ｊ＝１，・・・，Ｎについて、ｃ＿ｊ＝Ｈａｓｈ＿｛｛０，１｝｝（ａ，Ｃ，Ｌ＿｛ｊ｝＾＊，ｊ）が成立するか否かを確認する（ＳＩ１Ｖ３）。そして、全てのｊ＝１，・・・，Ｎについてｃ＿ｊ＝Ｈａｓｈ＿｛｛０，１｝｝（ａ，Ｃ，Ｌ＿｛ｊ｝＾＊，ｊ）が成立している場合は、Acceptを出力し（ＳＩ１Ｖ４）、成立しない場合はRejectを出力する（ＳＩ１Ｖ５）。【０１５１】
なお、第２及び３の実施形態に係る第一証明手段ＳＵ１Ｐも第１の実施形態の第一証明手段ＳＵ１Ｐと同様にストレートラインエクストラクタブルなものであれば、これに限定されない。よって、第２及び３の実施形態に係る第一証明手段ＳＵ１Ｐ、第一検証手順ＳＩ１Ｖを第４の実施形態の第一証明手段ＳＵ１Ｐ、第一検証手順ＳＩ１Ｖに置き換えてもよい。
【図面の簡単な説明】
【０１５２】
【図１】本実施形態に係るグループ署名方式の構成を示すブロック図である。
【図２】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図３】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図４】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図５】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図６】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図７】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図８】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図９】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１０】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１１】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１２】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１３】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１４】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１５】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１６】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１７】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図１８】本実施形態に係るグループ署名方式の構成を示すブロック図である。
【図１９】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図２０】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図２１】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【図２２】本実施形態に係るグループ署名方式の処理を示すフローチャートである。
【符号の説明】
【０１５３】
ＭＩ    イッシュアー装置
ＭＬ    ユーザ特定情報記憶装置
ＭＯ    オープナー装置
ＭＶ    検証装置
ＭＵ    ユーザ装置
ＦＩＡ    イッシュアーズセキュリティパラメータ入力手段
ＦＩＧ    イッシュアーズ鍵ペア生成手段
ＭＩＳ    秘密鍵記憶部
ＭＩＰ    公開鍵記憶部
ＦＩＩ    イッシュイング手段
ＦＯＡ    オープナーズセキュリティパラメータ入力手段
ＦＯＧ    オープナーズ鍵ペア生成手段
ＭＯＰ    公開鍵記憶部
ＭＯＳ    秘密鍵記憶部
ＦＯＯ    オープン手段
ＦＯＢ    出力手段
【図１】
0004899867.tif 000002
【図２】
0004899867.tif 000003
【図３】
0004899867.tif 000004
【図４】
0004899867.tif 000005
【図５】
0004899867.tif 000006
【図６】
0004899867.tif 000007
【図７】
0004899867.tif 000008
【図８】
0004899867.tif 000009
【図９】
0004899867.tif 000010
【図１０】
0004899867.tif 000011
【図１１】
0004899867.tif 000012
【図１２】
0004899867.tif 000013
【図１３】
0004899867.tif 000014
【図１４】
0004899867.tif 000015
【図１５】
0004899867.tif 000016
【図１６】
0004899867.tif 000017
【図１７】
0004899867.tif 000018
【図１８】
0004899867.tif 000019
【図１９】
0004899867.tif 000020
【図２０】
0004899867.tif 000021
【図２１】
0004899867.tif 000022
【図２２】
0004899867.tif 000023