(57)【要約】【課題】１個のグループ署名データで、署名人が複数のグループに対して署名人特定者を指定できる署名生成装置などを提供する。【解決手段】本発明に係る署名生成装置２００は、グループの発行管理者公開鍵と失効管理者公開鍵、および署名人特定者についての情報である署名人特定者情報の入力を受け付ける入力部１３と、署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶する記憶部２２０と、署名人特定者情報に対応する署名人特定者公開鍵を取得する署名人特定者公開鍵取得手段２１２ａ１と、署名人特定者公開鍵と、全ての署名人特定者に対して共通する乱数とを利用してメンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成する署名生成手段２１２ａ２と、生成されたグループ署名データおよび署名人特定者情報を出力する出力部１３とを有する。【選択図】図１
2011024011.tif 000002
【特許請求の範囲】
【請求項１】
グループのメンバーである一の署名人が前記グループに属することを証明する電子署名データとしてのグループ署名を生成して出力する署名生成装置であって、
前記グループの発行管理者公開鍵と失効管理者公開鍵、および前記署名人を特定することを許可したい複数の署名人特定者についての情報である署名人特定者情報の入力を受け付ける入力部と、
前記署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶する記憶部と、
前記署名人特定者情報に対応する署名人特定者公開鍵を取得する署名人特定者公開鍵取得手段と、
前記署名人特定者公開鍵と、全ての前記署名人特定者に対して共通する乱数とを利用して前記メンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成する署名生成手段と、
生成された前記グループ署名データおよび入力された前記署名人特定者情報を出力する出力部と
を有することを特徴とする署名生成装置。
【請求項２】
前記入力部が、２名以上の前記署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、
前記署名生成手段が、前記署名人特定者論理構造を利用して前記グループ署名データを生成することを特徴とする、請求項１に記載の署名生成装置。
【請求項３】
グループのメンバーである一の署名人が前記グループに属することを証明する電子署名データであるグループ署名について前記グループに属する前記署名人が誰であるかを特定する署名人特定装置であって、
外部の署名生成装置から出力された前記グループ署名と署名人特定者情報の入力を受け付ける入力部と、
署名人特定者秘密鍵と前記グループ署名に含まれる署名人情報に対応するメンバー特定子を記憶したメンバーリストとをあらかじめ記憶する記憶部と、
前記記憶部から前記署名人特定者秘密鍵を取得する署名人特定者秘密鍵取得手段と、
前記署名人特定者秘密鍵に対応する署名人特定者公開鍵が前記署名人特定者情報に含まれている場合に前記署名人特定者秘密鍵を利用して前記グループ署名を復号して署名人情報を得る署名人特定手段と、
復号して得られた前記署名人情報に対応するメンバー特定子を前記メンバーリストから検索するメンバー検索手段と、
検索された前記メンバー特定子を出力する出力部と
を有することを特徴とする署名人特定装置。
【請求項４】
前記入力部が、２名以上の前記署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、
前記署名人特定手段が、前記署名人特定者論理構造を利用して前記グループ署名を復号することを特徴とする、請求項３に記載の署名人特定装置。
【請求項５】
グループのメンバーである一の署名人が前記グループに属することを証明する電子署名データであるグループ署名を生成して出力する署名生成装置と、前記グループ署名が前記グループに属する前記署名人によって正当に生成されたものであるか否かを検証する検証装置と、前記グループ署名について前記署名人が誰であるかを特定する署名人特定装置とを含むグループ署名システムであって、
前記署名生成装置が、前記グループの発行管理者公開鍵と失効管理者公開鍵、および前記署名人を特定することを許可したい署名人特定者についての情報である署名人特定者情報の入力を受け付ける第１の入力部と、前記署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶する第１の記憶部と、前記署名人特定者情報に対応する署名人特定者公開鍵を取得する署名人特定者公開鍵取得手段と、前記署名人特定者公開鍵と、全ての前記署名人特定者に対して共通する乱数とを利用して前記メンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成する署名生成手段と、生成された前記グループ署名データおよび前記署名人特定者情報を出力する第１の出力部とを有し、
前記検証装置が、前記署名生成装置から出力された前記グループ署名データと前記署名人特定者情報、および前記グループの発行管理者公開鍵と失効管理者公開鍵の入力を受け付ける第２の入力部と、自らの署名人特定者秘密鍵を記憶する第２の記憶部と、前記グループ署名データ前記グループに属する前記署名人によって正当に生成されたものであるか否かを検証する検証部と、前記検証の結果を出力する第２の出力部とを有し、
前記署名人特定装置が、外部の署名生成装置から出力された前記グループ署名と署名人特定者情報の入力を受け付ける第３の入力部と、署名人特定者秘密鍵と署名人情報に対応するメンバー特定子を記憶したメンバーリストとをあらかじめ記憶する第３の記憶部と、前記記憶部から前記署名人特定者秘密鍵を取得する署名人特定者秘密鍵取得手段と、前記署名人特定者秘密鍵に対応する署名人特定者公開鍵が前記署名人特定者情報に含まれている場合に前記署名人特定者秘密鍵を利用して前記グループ署名を復号して署名人情報を得る署名人特定手段と、復号して得られた前記署名人情報に対応するメンバー特定子を前記メンバーリストから検索するメンバー検索手段と、検索された前記メンバー特定子を出力する第３の出力部とを有することを特徴とするグループ署名システム。
【請求項６】
前記第１の入力部が、２名以上の前記署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、
前記署名生成手段が、前記署名人特定者論理構造を利用して前記グループ署名データを生成し、
前記署名人特定手段が、前記署名人特定者論理構造を利用して前記グループ署名を復号することを特徴とする、請求項５に記載のグループ署名システム。
【請求項７】
グループのメンバーである一の署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶している署名生成装置にあって、前記署名人が前記グループに属することを証明する電子署名データであるグループ署名を生成して出力する署名生成方法であって、
前記グループの発行管理者公開鍵と失効管理者公開鍵、および前記署名人を特定することを許可したい署名人特定者についての情報である署名人特定者情報の入力を受け付け、
前記署名人特定者情報に対応する署名人特定者公開鍵を取得し、
前記署名人特定者公開鍵と、全ての前記署名人特定者に対して共通する乱数とを利用して前記メンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成し、
生成された前記グループ署名データおよび前記署名人特定者情報を出力する
ことを特徴とする署名生成方法。
【請求項８】
前記入力を受け付ける工程が、２名以上の前記署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、
前記グループ署名データを生成する工程が、前記署名人特定者論理構造を利用して前記グループ署名データを生成することを特徴とする、請求項７に記載の署名生成方法。
【請求項９】
署名人特定者秘密鍵とグループ署名に含まれる署名人情報に対応するメンバー特定子を記憶したメンバーリストとをあらかじめ記憶している署名人特定装置にあって、グループのメンバーである一の署名人が前記グループに属することを証明する電子署名データであるグループ署名について前記グループに属する前記署名人が誰であるかを特定する署名人特定方法であって、
外部の署名生成装置から出力された前記グループ署名と署名人特定者情報の入力を受け付け、
前記署名人特定者秘密鍵を取得し、
前記署名人特定者秘密鍵に対応する署名人特定者公開鍵が前記署名人特定者情報に含まれているか否かを判断し、
前記署名人特定者公開鍵が前記署名人特定者情報に含まれている場合に前記署名人特定者秘密鍵を利用して前記グループ署名を復号して署名人情報を得て、
復号して得られた前記署名人情報に対応するメンバー特定子を前記メンバーリストから検索し、
検索された前記メンバー特定子を出力する
ことを特徴とする署名人特定方法。
【請求項１０】
前記入力を受け付ける工程が、２名以上の前記署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、
前記グループ署名を復号する工程が、前記署名人特定者論理構造を利用して前記グループ署名を復号することを特徴とする、請求項９に記載の署名人特定方法。
【請求項１１】
グループのメンバーである一の署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶している署名生成装置にあって、前記署名生成装置が備えるコンピュータに、
前記グループの発行管理者公開鍵と失効管理者公開鍵、および前記署名人を特定することを許可したい署名人特定者についての情報である署名人特定者情報の入力を受け付ける手順と、
前記署名人特定者情報に対応する署名人特定者公開鍵を取得する手順と、
前記署名人特定者公開鍵と、全ての前記署名人特定者に対して共通する乱数とを利用して前記メンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成する手順と、
生成された前記グループ署名データおよび前記署名人特定者情報を出力する手順と
を実行させることを特徴とする署名生成プログラム。
【請求項１２】
前記入力を受け付ける手順が、２名以上の前記署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、
前記グループ署名データを生成する手順とが、前記署名人特定者論理構造を利用して前記グループ署名データを生成することを特徴とする、請求項１１に記載の署名生成プログラム。
【請求項１３】
署名人特定者秘密鍵とグループ署名に含まれる署名人情報に対応するメンバー特定子を記憶したメンバーリストとをあらかじめ記憶している署名人特定装置にあって、前記署名人特定装置が備えるコンピュータに、
外部の署名生成装置から出力された前記グループ署名と署名人特定者情報の入力を受け付ける手順と、
前記署名人特定者秘密鍵を取得する手順と、
前記署名人特定者秘密鍵に対応する署名人特定者公開鍵が前記署名人特定者情報に含まれているか否かを判断する手順と、
前記署名人特定者公開鍵が前記署名人特定者情報に含まれている場合に前記署名人特定者秘密鍵を利用して前記グループ署名を復号して署名人情報を得る手順と、
復号して得られた前記署名人情報に対応するメンバー特定子を前記メンバーリストから検索する手順と、
検索された前記メンバー特定子を出力する手順と
を実行させることを特徴とする署名人特定プログラム。
【請求項１４】
前記入力を受け付ける手順が、２名以上の前記署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、
前記グループ署名を復号する手順が、前記署名人特定者論理構造を利用して前記グループ署名を復号することを特徴とする、請求項１３に記載の署名人特定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はグループ署名方式に関し、特に該方式における署名人特定者の指定に関する。
【背景技術】
【０００２】
グループ署名方式は、たとえば特定の企業や特定の部署などのような特定のグループに所属するメンバーが、署名装置を操作して該グループのメンバーであることを示す電子署名を生成する署名方式である。グループ署名方式では、特別な権限を持つ者が、署名を生成したメンバーを特定する機能を備えている。この権限を持つ者を、署名人特定者という。署名人特定者以外の者は、確かに該グループのメンバーがその署名を生成したか否かを検証することはできるが、該メンバー個人を特定することはできない。
【０００３】
たとえば、クレジットカード（「該グループのメンバー」＝「該カードの会員」）であれば、メンバーが通常は店舗側に自らの個人情報を公開せずに該カードのサービスを利用することができる。かつ、不正使用が発生した場合などには署名人特定者がその不正使用を行ったメンバーを特定することが可能であるので、不正使用によるリスクを抑制することができる。署名人特定者は、メンバーがそのグループ署名を生成する際に指定する。
【０００４】
このグループ署名方式については、次に示す各々の技術文献が開示されている。特許文献１には、映像などのコンテンツの有料配信で、鍵の漏洩に対する被害を抑制するためにグループ署名方式を利用した配信システムが記載されている。特許文献２には、会員向けサービスを外部業者にアウトソーシングする際に、グループ署名方式を利用して該会員の個人情報をその外部業者に開示せずに済むというサービス提供システムが記載されている。特許文献３には、グループ署名方式において、グループの公開鍵の大きさを該グループのメンバー数に比例させずに済むという署名処理方法が記載されている。
【０００５】
また、非特許文献１〜２にはＲＳＡ（Rivest Shamir Adleman）ベースの暗号化方式を利用したグループ署名方式、非特許文献３〜４にはペアリング（Pairing）ベースの暗号化方式を利用したグループ署名方式が、それぞれ記載されている。非特許文献５には、ファイルの作成、閲覧、改変，印刷などのたびにグループ署名を作成し、このグループ署名データをログ管理サーバーで記憶しているというログ管理システムが記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−２０３８１９号公報
【特許文献２】特開２００７−００４４６１号公報
【特許文献３】特許３５１３３２４号公報
【非特許文献】
【０００７】
【非特許文献１】J. Camenisch and J. Groth. Group Signatures: Better Efficiency and New Theoretical Aspects. Security in Communication Networks (SCN2004), vol. 3352 of LNCS, pp. 120--133.
【非特許文献２】Toshiyuki Isshiki, Kengo Mori, Kazue Sako, Isamu Teranishi, and Shoko Yonezawa. Using Group Signature for Identity Management and its Implementation. Workshop on Digital Identity Management (DIM2006), pp. 73--78.
【非特許文献３】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.
【非特許文献５】尾花賢、一色寿幸、佐古和恵、宮崎邦彦、藤井康広、本多義則、「プライバシを考慮した来歴管理を実現する墨塗りグループ署名」, SCIS2009, 3B2-4.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
グループＡ、Ｂ、Ｃという３つのグループが存在する場合、その中のグループＡの属する署名人が作成したグループＡの一員としてのグループ署名データは、グループＡ、Ｂ、Ｃのいずれに属する検証者が検証しても、グループＡの一員が正当に作成した署名データであることのみがわかるが、その署名人がグループＡの中の誰であるかは、署名人があらかじめ指定した署名人特定者にしか特定されない。ここで、署名人がグループＡ、Ｂ、Ｃの各々に対して署名人特定者を指定することを考えた場合、各グループで指定された署名人特定者が署名人を特定した場合の結果は必ず一致することが必要となる。
【０００９】
しかしながら、特許文献１〜３および非特許文献１〜５に記載されたグループ署名方式では、署名人は１人の署名人特定者しか指定できなかったため、上記のようにグループごとに署名人特定者を指定したグループ署名を生成することは不可能であった。また、これを解決するために、同一の署名人がグループＡ、Ｂ、およびＣの各々に対して異なる署名人特定者を指定したグループ署名データを作成することも考えられるが、前述したグループ署名の性質上、検証者はそれらのグループ署名データが本当に同じ署名人によって作成されたものなのかを確認することはできない。
【００１０】
この場合、複数のグループ署名データが同じ署名人によって生成されたものであることをゼロ知識証明によって署名人のＩＤを秘匿したまま証明することも考えられる。しかしながら、この場合に必要になる署名データのデータ長は、指定した署名人特定者の数に比例するグループ署名データとゼロ知識証明のデータ長との合計となる。例えば、非特許文献２の方式でこれを行った場合、推奨されているセキュリティパラメータを利用した場合、署名人特定者１人に対するデータ長は約６０００ビットとなる。これが指定する署名人特定者の数だけ生成されるので、そのデータ長および必要となる計算量は非現実的なものとなる。
【００１１】
本発明の目的は、１個のグループ署名データで、署名人が複数のグループに対して署名人特定者を指定し、その署名人特定者の各々が同一の署名人を特定でき、かつ署名生成に必要な計算量の小さいグループ署名データを生成および署名人特定することを可能とする署名生成装置、署名人特定装置、グループ署名システム、およびそれらの方法とプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明に係る署名生成装置は、グループのメンバーである一の署名人がグループに属することを証明する電子署名データとしてのグループ署名を生成して出力する署名生成装置であって、グループの発行管理者公開鍵と失効管理者公開鍵、および署名人を特定することを許可したい複数の署名人特定者についての情報である署名人特定者情報の入力を受け付ける入力部と、署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶する記憶部と、署名人特定者情報に対応する署名人特定者公開鍵を取得する署名人特定者公開鍵取得手段と、署名人特定者公開鍵と、全ての署名人特定者に対して共通する乱数とを利用してメンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成する署名生成手段と、生成されたグループ署名データおよび入力された署名人特定者情報を出力する出力部とを有することを特徴とする。
【００１３】
上記目的を達成するため、本発明に係る署名人特定装置は、グループのメンバーである一の署名人がグループに属することを証明する電子署名データであるグループ署名についてグループに属する署名人が誰であるかを特定する署名人特定装置であって、外部の署名生成装置から出力されたグループ署名と署名人特定者情報の入力を受け付ける入力部と、署名人特定者秘密鍵とグループ署名に含まれる署名人情報に対応するメンバー特定子を記憶したメンバーリストとをあらかじめ記憶する記憶部と、記憶部から署名人特定者秘密鍵を取得する署名人特定者秘密鍵取得手段と、署名人特定者秘密鍵に対応する署名人特定者公開鍵が署名人特定者情報に含まれている場合に署名人特定者秘密鍵を利用してグループ署名を復号して署名人情報を得る署名人特定手段と、復号して得られた署名人情報に対応するメンバー特定子をメンバーリストから検索するメンバー検索手段と、検索されたメンバー特定子を出力する出力部とを有することを特徴とする。
【００１４】
上記目的を達成するため、本発明に係るグループ署名システムは、グループのメンバーである一の署名人がグループに属することを証明する電子署名データであるグループ署名を生成して出力する署名生成装置と、グループ署名がグループに属する署名人によって正当に生成されたものであるか否かを検証する検証装置と、グループ署名について署名人が誰であるかを特定する署名人特定装置とを含むグループ署名システムであって、署名生成装置が、グループの発行管理者公開鍵と失効管理者公開鍵、および署名人を特定することを許可したい署名人特定者についての情報である署名人特定者情報の入力を受け付ける第１の入力部と、署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶する第１の記憶部と、署名人特定者情報に対応する署名人特定者公開鍵を取得する署名人特定者公開鍵取得手段と、署名人特定者公開鍵と、全ての署名人特定者に対して共通する乱数とを利用してメンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成する署名生成手段と、生成されたグループ署名データおよび署名人特定者情報を出力する第１の出力部とを有し、検証装置が、署名生成装置から出力されたグループ署名データと署名人特定者情報、およびグループの発行管理者公開鍵と失効管理者公開鍵の入力を受け付ける第２の入力部と、自らの署名人特定者秘密鍵を記憶する第２の記憶部と、グループ署名データグループに属する署名人によって正当に生成されたものであるか否かを検証する検証部と、検証の結果を出力する第２の出力部とを有し、署名人特定装置が、外部の署名生成装置から出力されたグループ署名と署名人特定者情報の入力を受け付ける第３の入力部と、署名人特定者秘密鍵と署名人情報に対応するメンバー特定子を記憶したメンバーリストとをあらかじめ記憶する第３の記憶部と、記憶部から署名人特定者秘密鍵を取得する署名人特定者秘密鍵取得手段と、署名人特定者秘密鍵に対応する署名人特定者公開鍵が署名人特定者情報に含まれている場合に署名人特定者秘密鍵を利用してグループ署名を復号して署名人情報を得る署名人特定手段と、復号して得られた署名人情報に対応するメンバー特定子をメンバーリストから検索するメンバー検索手段と、検索されたメンバー特定子を出力する第３の出力部とを有することを特徴とする。
【００１５】
上記目的を達成するため、本発明に係る署名生成方法は、グループのメンバーである一の署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶している署名生成装置にあって、署名人がグループに属することを証明する電子署名データであるグループ署名を生成して出力する署名生成方法であって、グループの発行管理者公開鍵と失効管理者公開鍵、および署名人を特定することを許可したい署名人特定者についての情報である署名人特定者情報の入力を受け付け、署名人特定者情報に対応する署名人特定者公開鍵を取得し、署名人特定者公開鍵と、全ての署名人特定者に対して共通する乱数とを利用してメンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成し、生成されたグループ署名データおよび署名人特定者情報を出力することを特徴とする。
【００１６】
上記目的を達成するため、本発明に係る署名人特定方法は、署名人特定者秘密鍵とグループ署名に含まれる署名人情報に対応するメンバー特定子を記憶したメンバーリストとをあらかじめ記憶している署名人特定装置にあって、グループのメンバーである一の署名人がグループに属することを証明する電子署名データであるグループ署名についてグループに属する署名人が誰であるかを特定する署名人特定方法であって、外部の署名生成装置から出力されたグループ署名と署名人特定者情報の入力を受け付け、署名人特定者秘密鍵を取得し、署名人特定者秘密鍵に対応する署名人特定者公開鍵が署名人特定者情報に含まれているか否かを判断し、署名人特定者公開鍵が署名人特定者情報に含まれている場合に署名人特定者秘密鍵を利用してグループ署名を復号して署名人情報を得て、復号して得られた署名人情報に対応するメンバー特定子をメンバーリストから検索し、検索されたメンバー特定子を出力することを特徴とする。
【００１７】
上記目的を達成するため、本発明に係る署名生成プログラムは、グループのメンバーである一の署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶している署名生成装置にあって、署名生成装置が備えるコンピュータに、グループの発行管理者公開鍵と失効管理者公開鍵、および署名人を特定することを許可したい署名人特定者についての情報である署名人特定者情報の入力を受け付ける手順と、署名人特定者情報に対応する署名人特定者公開鍵を取得する手順と、署名人特定者公開鍵と、全ての署名人特定者に対して共通する乱数とを利用してメンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成する手順と、生成されたグループ署名データおよび署名人特定者情報を出力する手順とを実行させることを特徴とする。
【００１８】
上記目的を達成するため、本発明に係る署名人特定プログラムは、署名人特定者秘密鍵とグループ署名に含まれる署名人情報に対応するメンバー特定子を記憶したメンバーリストとをあらかじめ記憶している署名人特定装置にあって、署名人特定装置が備えるコンピュータに、外部の署名生成装置から出力されたグループ署名と署名人特定者情報の入力を受け付ける手順と、署名人特定者秘密鍵を取得する手順と、署名人特定者秘密鍵に対応する署名人特定者公開鍵が署名人特定者情報に含まれているか否かを判断する手順と、署名人特定者公開鍵が署名人特定者情報に含まれている場合に署名人特定者秘密鍵を利用してグループ署名を復号して署名人情報を得る手順と、復号して得られた署名人情報に対応するメンバー特定子をメンバーリストから検索する手順と、検索されたメンバー特定子を出力する手順とを実行させることを特徴とする。
【発明の効果】
【００１９】
本発明は、上述したように署名人特定者情報に対応する署名人特定者公開鍵を利用してメンバー秘密鍵に含まれる署名人情報を暗号化するように構成したので、これに対応する署名人特定者秘密鍵を持つ署名人特定者のみが署名人情報を復号化して署名人を特定することができる。さらに、全ての署名人特定者に対して共通する乱数を利用して署名人情報を暗号化するので、暗号化に必要な計算量を抑制することができる。これによって、１個のグループ署名データで、署名人特定者が何人であっても、その署名人特定者の各々が同一の署名人を特定でき、かつ署名生成に必要な計算量およびデータ容量の小さいグループ署名データを生成および署名人特定することが可能である署名生成装置、署名人特定装置、グループ署名システム、およびそれらの方法とプログラムを提供することができる。
【図面の簡単な説明】
【００２０】
【図１】、本発明の第１の実施形態に係るグループ署名システム全体の構成を示す説明図である。
【図２】図１に示した発行者装置、メンバー装置、検証装置、署名人特定装置、失効管理者装置として機能するコンピュータ装置のハードウェアとしての構成を示す説明図である。
【図３】図１に示したメンバー装置がグループ署名を生成する動作について示すフローチャートである。
【図４】図１に示した検証装置がグループ署名を検証する動作について示すフローチャートである。
【図５】図１に示した署名人特定装置が署名人を特定する動作について示すフローチャートである。
【図６】本発明の第２の実施形態に係るグループ署名システム全体の構成を示す説明図である。
【図７】図６に示したメンバー装置がグループ署名を生成する動作について示すフローチャートである。
【図８】図６に示した検証装置がグループ署名を検証する動作について示すフローチャートである。
【図９】図６に示した署名人特定装置が署名人を特定する動作について示すフローチャートである。
【図１０】本発明の第３の実施形態に係るグループ署名システム全体の構成を示す説明図である。
【図１１】図１０に示したメンバー装置がグループ署名を生成する動作について示すフローチャートである。
【図１２】図１０に示した検証装置がグループ署名を検証する動作について示すフローチャートである。
【図１３】図１０に示した署名人特定装置が行う署名人を特定する動作について示すフローチャートである。
【図１４】本発明の第４の実施形態に係るグループ署名システム全体の構成を示す説明図である。
【図１５】図１４に示したメンバー装置がグループ署名を生成する動作について示すフローチャートである。
【図１６】図１４に示した検証装置がグループ署名を検証する動作について示すフローチャートである。
【図１７】図１４に示した署名人特定装置が行う署名人を特定する動作について示すフローチャートである。
【発明を実施するための形態】
【００２１】
（第１の実施形態）
以下、本発明の実施形態の構成について添付図に基づいて説明する。
最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。
本実施形態に係る署名生成装置（メンバー装置２００）は、グループのメンバーである一の署名人がグループに属することを証明する電子署名データとしてのグループ署名を生成して出力する署名生成装置であって、グループの発行管理者公開鍵と失効管理者公開鍵、および署名人を特定することを許可したい署名人特定者についての情報である署名人特定者情報の入力を受け付ける入力部（入出力部１３）と、署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶する記憶部（メンバー記憶部２２０）と、署名人特定者情報に対応する署名人特定者公開鍵を取得する署名人特定者公開鍵取得手段２１２ａと、署名人特定者公開鍵と、全ての署名人特定者に対して共通する乱数とを利用してメンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成する署名生成手段２１２ｂと、生成されたグループ署名データおよび署名人特定者情報を出力する出力部（入出力部１３）とを有する。
【００２２】
また、本実施形態に係る署名人特定装置４００は、グループのメンバーである一の署名人がグループに属することを証明する電子署名データであるグループ署名についてグループに属する署名人が誰であるかを特定する署名人特定装置であって、外部の署名生成装置から出力されたグループ署名と署名人特定者情報の入力を受け付ける入力部（入出力部１３）と、署名人特定者秘密鍵とグループ署名に含まれる署名人情報に対応するメンバー特定子（ＩＤ）を記憶したメンバーリスト４２１とをあらかじめ記憶する記憶部（署名人特定者記憶部４２０）と、記憶部から署名人特定者秘密鍵を取得する署名人特定者秘密鍵取得手段４１２ａ１と、署名人特定者秘密鍵に対応する署名人特定者公開鍵が署名人特定者情報に含まれている場合に署名人特定者秘密鍵を利用してグループ署名を復号して署名人情報を得る署名人特定手段４１２ａ２と、復号して得られた署名人情報に対応するメンバー特定子をメンバーリストから検索するメンバー検索手段４１２ａ３と、検索されたメンバー特定子を出力する出力部（入出力部１３）とを有する。
【００２３】
この構成を備えることにより、本実施形態は、１個のグループ署名データで、署名人特定者が何人であっても、その署名人特定者の各々が同一の署名人を特定できるグループ署名データを生成して使用することが可能となる。
以下、これをより詳細に説明する。
【００２４】
本明細書ではまず、以下のような各々の区分の者が本発明の実施形態に係るグループ署名システムを使用する。
「メンバー（署名人）」−特定のグループに属し、そのグループの一員としての署名データであるグループ署名を生成して使用する。
「発行者」−グループのメンバーに対して、グループ署名の生成に使用するグループ鍵を生成および発行する。
「検証者」−グループ署名を受け取り、このグループ署名が該グループのメンバーによって正当に作成されたものであるか否かを検証する。
「署名人特定者」−グループ署名を受け取り、このグループ署名を生成したメンバーが誰であるかを特定する。
「失効管理者」−グループの中で特定のメンバーが持つグループ鍵を失効させる。
【００２５】
本明細書では、このグループ署名を生成したメンバーが誰であるかを示す情報を「署名人情報」といい、署名人特定者の中で誰がそのメンバーを特定することができるかを示す情報を「署名人特定者情報」という。
【００２６】
本明細書の数式以外の行では、ａ＾ｂは「ａのｂ乗」を意味し、ａ＿ｂは「ａに下付き添え字ｂ」がついた状態を示す。さらに、整数Ｎの剰余群をＺ＿Ｎと記す。すなわち、Ｚ＿Ｎ＝｛０，１，…，Ｎ−１｝である。そして、整数Ｎに対して、ｙ＝ｘ＾２  ｍｏｄ  Ｎを満たすｘを持つＺ＿Ｎの要素ｙの集合をＱＲ（Ｎ）と記す。
【００２７】
図１は、本発明の第１の実施形態に係るグループ署名システム１全体の構成を示す説明図である。グループ署名システム１は、発行管理者がグループのメンバーに対してメンバー鍵を生成および発行する発行者装置１００、発行されたメンバー鍵によって各メンバーがグループ署名を生成するメンバー装置２００、生成されたグループ署名の正当性を検証する検証装置３００、生成されたグループ署名を行ったメンバーを特定する署名人特定装置４００、および特定のメンバーのメンバー鍵を失効させる失効管理者装置５００が、ネットワーク６００によって相互に接続されて構成される。
【００２８】
発行者装置１００、メンバー装置２００、検証装置３００、署名人特定装置４００、失効管理者装置５００は、いずれも後述の図２で説明するコンピュータ装置である。メンバー装置２００および署名人特定装置４００はネットワーク６００に何台接続されていてもよいが、図１には簡単のため各１台ずつのみ記載している。
【００２９】
図２は、図１に示した発行者装置１００、メンバー装置２００、検証装置３００、署名人特定装置４００、失効管理者装置５００として機能するコンピュータ装置１０のハードウェアとしての構成を示す説明図である。コンピュータ装置１０は、コンピュータプログラムを実行する主体となるプロセッサ１１と、コンピュータプログラムおよびデータを記憶する記憶部１２と、データの入出力を行う入出力部１３と、ネットワーク６００を介して他のコンピュータ装置とのデータ通信を行う通信部１４とを備える。
【００３０】
図１に戻って、発行者装置１００の備えるプロセッサ１１および記憶部１２を、各々プロセッサ１１０および発行者記憶部１２０と表記する。プロセッサ１１０では、発行者鍵生成部１１１と発行部１１２が、各々コンピュータプログラムとして動作する。同様に、メンバー装置２００の備えるプロセッサ１１および記憶部１２を、各々プロセッサ２１０およびメンバー記憶部２２０と表記する。プロセッサ２１０では、参加部２１１と署名生成部２１２が、各々コンピュータプログラムとして動作する。
【００３１】
検証装置３００の備えるプロセッサ１１および記憶部１２を、各々プロセッサ３１０および検証者記憶部３２０と表記する。プロセッサ３１０では、検証部３１１がコンピュータプログラムとして動作する。署名人特定装置４００の備えるプロセッサ１１および記憶部１２を、各々プロセッサ４１０および署名人特定者記憶部４２０と表記する。プロセッサ４１０では、署名人特定者鍵生成部４１１と署名人特定部４１２が、各々コンピュータプログラムとして動作する。
【００３２】
失効管理者装置５００の備えるプロセッサ１１および記憶部１２を、各々プロセッサ５１０および失効管理者記憶部５２０と表記する。プロセッサ５１０では、失効管理者鍵生成部５１１と失効部５１２が、各々コンピュータプログラムとして動作する。
【００３３】
グループ署名システム１では、あらかじめ以下に示す鍵データが何らかの方法によって作成されている。以下に示す各々の鍵の名称で、略称の２文字目が「ｓ」（secret）であるものが秘密鍵、２文字目が「ｐ」（public）であるものが公開鍵である。
（１）発行管理者秘密鍵と発行管理者公開鍵（ｉｓｋ，ｉｐｋ）
（２）失効管理者秘密鍵と失効管理者公開鍵（ｒｓｋ，ｒｐｋ）
（３）Ｎ人（Ｎは自然数）の署名人特定者各々に対する署名人特定者秘密鍵と署名人特定者公開鍵（ｏｓｋ［１］，ｏｐｋ［１］）〜（ｏｓｋ［Ｎ］，ｏｐｋ［Ｎ］）
（４）メンバー秘密鍵とメンバー公開鍵（ｍｓｋ，ｍｐｋ）
【００３４】
各々の公開鍵ｉｐｋ，ｒｐｋ，ｏｐｋ［１］〜ｏｐｋ［Ｎ］，ｍｐｋは、グループ署名システム１の全装置に対して公開されている。発行管理者秘密鍵ｉｓｋは発行者記憶部１２０にのみ記憶され、発行者装置１００からのみ参照できる。同様に、失効管理者秘密鍵ｒｓｋは失効管理者記憶部５２０にのみ記憶され、失効管理者装置５００からのみ参照できる。署名人特定者秘密鍵ｏｓｋ［ｉ］（ｉは自然数、かつ１≦ｉ≦Ｎ）は、該署名人特定者の署名人特定者記憶部４２０にのみ記憶され、該署名人特定者の署名人特定装置４００からのみ参照できる。メンバー秘密鍵ｍｓｋは該メンバーのメンバー記憶部２２０にのみ記憶され、該メンバーのメンバー装置２００からのみ参照できる。
【００３５】
上記の各々の公開鍵と秘密鍵のペアは、たとえば非特許文献２などに記載された公知の鍵生成部によって生成されたものである。ただし、安全性の観点から、Ｎ人の署名人特定者は各々共通のパラメータを利用していることが望ましい。ここでいう共通のパラメータとは、例えば非特許文献２に記載の方法では、鍵の生成に用いられる楕円曲線とその基点である。
【００３６】
発行者装置１００で動作する発行者鍵生成部１１１は、与えられたセキュリティパラメータを入力として、ｉｓｋおよびｉｐｋを出力する。同じく発行者装置１００で動作する発行部１１２は、メンバー装置２００で動作する参加部２１１と連携して、各々のメンバーに対してｍｓｋおよびｍｐｋを発行する。発行部１１２はセキュリティパラメータとｉｓｋとｉｐｋを、参加部２１１はセキュリティパラメータとｉｐｋとｒｐｋとｏｐｋを、それぞれ入力とする。
【００３７】
署名人特定装置４００で動作する署名人特定者鍵生成部４１１は、セキュリティパラメータを入力として、ｏｓｋ［ｉ］およびｏｐｋ［ｉ］（ｉは自然数、かつ１≦ｉ≦Ｎ）を出力する。失効管理者装置５００で動作する失効管理者鍵生成部５１１は、セキュリティパラメータを入力として、ｒｓｋおよびｒｐｋを出力する。同じく失効管理者装置５００で動作する失効部５１２は、ｒｓｋおよびｒｐｋと、失効するメンバーのｍｐｋを入力として、更新されたｒｐｋを出力する。更新されたｒｐｋを使用すると、失効したメンバーの生成したグループ署名は無効となる。
【００３８】
メンバー装置２００で動作する署名生成部２１２は、署名人特定者公開鍵取得手段２１２ａ１と、署名生成手段２１２ａ２とを有する。署名人特定装置４００で動作する署名人特定部４１２は、署名人特定者秘密鍵取得手段４１２ａ１と、署名人特定手段４１２ａ２と、メンバー検索手段４１２ａ３とを有する。これらと、検証装置３００で動作する検証部３１１の各々の動作については後述する。
【００３９】
また、ｍｐｋにはメンバーごとに異なる署名人情報ｈが必ず含まれ、この署名人情報ｈとメンバーを特定するＩＤとを一意に対応させるリストが発行者記憶部１２０および署名人特定者記憶部４２０に記憶されている。これを各々メンバーリスト１２１および４２１という。
【００４０】
図３は、図１に示したメンバー装置２００がグループ署名を生成する動作について示すフローチャートである。発行者が管理するグループに所属するメンバーは、Ｎ人の署名人特定者の中から署名人（該メンバー自分自身）を特定させたいと思うｊ人の署名人特定者ｉ＿１〜ｉ＿ｊを選択して（ｊは自然数、かつｊ≦Ｎ）、メンバー装置２００の署名生成部２１２に対してｉｐｋ、ｒｐｋ、署名人特定者情報、メッセージＭ、以上の各データを入力し、メンバー装置２００の入出力部１３がこの入力を受け取る（ステップＳ１１）。
【００４１】
ここで、メンバー記憶部２２０には、署名人が指定した署名人特定者の公開鍵が記憶されている署名人特定者リスト２２１が予め記憶されている。または、署名人特定者リスト２２１には署名人特定者の名前や公開鍵が公開されている場所の情報やＵＲＬなど、公開鍵とリンクする情報が予め記憶されているようにしてもよい。
【００４２】
署名人特定者公開鍵取得手段２１２ａ１は、この署名人特定者リスト２２１を参照して、ユーザが指定した署名人特定者の公開鍵ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］を取得する。これらの公開鍵ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］が署名人特定者情報である。そして署名人特定者公開鍵取得手段２１２ａ１は、メンバー記憶部２２０から該メンバーのｍｐｋとｍｓｋとを読み込む。（ステップＳ１２）。
【００４３】
ｉｐｋ、ｒｐｋ、ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、ｍｐｋ、ｍｓｋ、メッセージＭ、以上のデータをここまでで受け取った署名生成手段２１２ａ２は、ｍｐｋに含まれる署名人情報ｈをｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］を用いてそれぞれ暗号化して、ＥＮＣ［ｏｐｋ［ｉ＿１］］（ｈ）〜ＥＮＣ［ｏｐｋ［ｉ＿ｊ］］（ｈ）を生成する（ステップＳ１３）。
【００４４】
続いて署名生成手段２１２ａ２は、ＥＮＣ［ｏｐｋ［ｉ＿１］］（ｈ）〜ＥＮＣ［ｏｐｋ［ｉ＿ｊ］］（ｈ）を含むグループ署名データσと、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］とを出力する（ステップＳ１４）。
【００４５】
図４は、図１に示した検証装置３００がグループ署名を検証する動作について示すフローチャートである。メンバー装置２００によって図３に示す動作で生成されたグループ署名データσ、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、さらにｉｐｋおよびｒｐｋを、検証者が検証装置３００に入力する（ステップＳ２１）。検証部３１１は、これらのデータに対してグループ署名検証の演算を行い、このグループ署名データσが正当であるか否かを判断して（ステップＳ２２）、正当であれば受理（ステップＳ２３）、そうでなければ不受理（ステップＳ２４）をそれぞれ出力する。
【００４６】
図５は、図１に示した署名人特定装置４００が署名人を特定する動作について示すフローチャートである。メンバー装置２００によって図３に示す動作で生成されたグループ署名データ、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］を、署名人特定者が署名人特定装置４００に入力する（ステップＳ３１）。
【００４７】
署名人特定者秘密鍵取得手段４１２ａは、署名人特定者記憶部４２０に記憶されている自らの署名人特定者秘密鍵ｏｓｋ［ｉ］を読み込む（ステップＳ３２）。署名人特定手段４１２ａ２は、受け取った署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］の中に自らの署名人特定者秘密鍵ｏｓｋ［ｉ］に対応する公開鍵ｏｐｋ［ｉ］が含まれているか否かを判断し（ステップＳ３３）、含まれていればこの秘密鍵ｏｓｋ［ｉ］でσに含まれる暗号を復号して署名人情報ｈを得る（ステップＳ３４）。ステップＳ３３で、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］の中に公開鍵ｏｐｋ［ｉ］が含まれていなければ特定失敗を出力して処理を終了する（ステップＳ３７）。
【００４８】
ステップＳ３４までの処理で署名人情報ｈを得たメンバー検索手段４１２ａ３は、メンバーリスト４２１を読み込んで署名人情報ｈに対応するメンバーのＩＤを検索して、そのＩＤを出力する（ステップＳ３５〜３６）。
【００４９】
（第１の実施形態の全体的な動作）
次に、上記の実施形態の全体的な動作について説明する。本実施形態に係る署名生成方法は、グループのメンバーである一の署名人のメンバー秘密鍵およびメンバー公開鍵をあらかじめ記憶している署名生成装置（メンバー装置２００）にあって、署名人がグループに属することを証明する電子署名データであるグループ署名を生成して出力する署名生成方法であって、グループの発行管理者公開鍵と失効管理者公開鍵、および署名人を特定することを許可したい署名人特定者についての情報である署名人特定者情報の入力を受け付け（図３：ステップＳ１１）、署名人特定者情報に対応する署名人特定者公開鍵を取得し（図３：ステップＳ１２）、署名人特定者公開鍵と、全ての署名人特定者に対して共通する乱数とを利用してメンバー秘密鍵に含まれる署名人情報を暗号化したデータを含むグループ署名データを生成し（図３：ステップＳ１３）、生成されたグループ署名データおよび署名人特定者情報を出力する（図３：ステップＳ１４）。
【００５０】
そして、本実施形態に係る署名人特定方法は、署名人特定者秘密鍵とグループ署名に含まれる署名人情報に対応するメンバー特定子（ＩＤ）を記憶したメンバーリストとをあらかじめ記憶している署名人特定装置４００にあって、グループのメンバーである一の署名人がグループに属することを証明する電子署名データであるグループ署名についてグループに属する署名人が誰であるかを特定する署名人特定方法であって、外部の署名生成装置から出力されたグループ署名と署名人特定者情報の入力を受け付け（図５：ステップＳ３１）、署名人特定者秘密鍵を取得し（図５：ステップＳ３２）、署名人特定者秘密鍵に対応する署名人特定者公開鍵が署名人特定者情報に含まれているか否かを判断し（図５：ステップＳ３３）、署名人特定者公開鍵が署名人特定者情報に含まれている場合に署名人特定者秘密鍵を利用してグループ署名を復号して署名人情報を得て（図５：ステップＳ３４）、復号して得られた署名人情報に対応するメンバー特定子をメンバーリストから検索し（図５：ステップＳ３５）、検索されたメンバー特定子を出力する（図５：ステップＳ３６）。
【００５１】
ここで、上記各動作ステップについては、これをコンピュータで実行可能にプログラム化し、これらを前記各ステップを直接実行するコンピュータであるメンバー装置２００および署名人特定装置４００に実行させるようにしてもよい。
この構成および動作により、本実施形態は以下のような効果を奏する。
【００５２】
本実施形態では、署名人特定者が何人であっても、１個のグループ署名データで、その署名人特定者の各々が同一の署名人を特定できるグループ署名データを生成して使用することが可能となる。処理に係るグループ署名データなどのデータ量の総計は、署名人特定者の数に比例して増大するなどのようなことはない。
【００５３】
本実施形態では、グループ署名データの生成に当たっては、前述の特許文献および非特許文献にあるような任意の公知技術を適用することができるが、特に非特許文献１、非特許文献３、非特許文献４に記載された方式に適している。これらの方式には失効管理装置が存在しないが、失効管理者の鍵ペアｒｓｋおよびｒｐｋを空データとすることによって容易に適用することができる。この場合、非特許文献１に記載の方式における共通パラメータはエルガマル暗号の群およびその生成元であり、非特許文献３と４記載の方式における共通パラメータは利用する楕円曲線およびその基点である。
【００５４】
（第２の実施形態）
本発明の第２の実施形態は、前述の第１の実施形態の構成に加えて、署名装置（メンバー装置２００ｂ）の入力部（入出力部１３）が、２名以上の署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、署名生成部２１２ｂが、署名人特定者論理構造を利用してグループ署名データを生成するように構成した。
【００５５】
さらに、これに対して署名人特定装置４００の入力部（入出力部１３）が、２名以上の署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、署名人特定部４１２ｂが、署名人特定者論理構造を利用してグループ署名を復号する。
【００５６】
この構成を備えることにより、署名人が２名以上の署名人特定者が協力して署名人を特定するという条件を含むグループ署名データを生成することができるようになる。
以下、これをより詳細に説明する。
【００５７】
図６は、本発明の第２の実施形態に係るグループ署名システム１ｂ全体の構成を示す説明図である。グループ署名システム１ｂは、ハードウェアおよびソフトウェアの構成は第１の実施形態で説明したものと同一であるが、後述するように署名生成部、検証部、署名人特定部の各々の動作が第１の実施形態で説明したものと異なる。これらを各々、署名生成部２１２ｂ、検証部３１１ｂ、署名人特定部４１２ｂという。署名生成部２１２ｂは、署名人特定者公開鍵取得手段２１２ｂ１と、署名生成手段２１２ｂ２とを有する。署名人特定部４１２ｂは、署名人特定者秘密鍵取得手段４１２ｂ１と、署名人特定手段４１２ｂ２と、メンバー検索手段４１２ｂ３とを有する。また、メンバー装置、検証装置、署名人特定装置を各々、メンバー装置２００ｂ、検証装置３００ｂ、署名人特定装置４００ｂという。これら各々の装置のハードウェア的な構成は、図２で説明したものと同一である。
【００５８】
第１の実施形態に係るグループ署名システム１では、たとえば署名人特定者情報によって指定された署名人特定者がＡ、Ｂ、Ｃの３名であった場合、このＡ、Ｂ、Ｃのうちいずれか１名が署名人を特定できた。これに対して第２の実施形態に係るグループ署名システム１ｂでは、署名人特定者情報に「２名以上の署名人特定者が協力して署名人を特定する」という条件を含むことができる。この条件が含まれた場合、たとえば「署名人特定者Ａは単独で署名人を特定可能。署名人特定者ＢとＣは各々単独では署名人を特定できないが、署名人特定者ＢとＣが協力すれば署名人を特定可能である」などのようなという任意の論理構造を持つ条件をつけることが可能となる。
【００５９】
第２の実施形態に係るグループ署名システム１ｂでは、第１の実施形態に係るグループ署名システム１と同様の鍵データがあらかじめ作成され、各装置に与えられている。また、発行者記憶部１２０および署名人特定者記憶部４２０には第１の実施形態と同様の各々メンバーリスト１２１および４２１が記憶されている。
【００６０】
図７は、図６に示したメンバー装置２００ｂがグループ署名を生成する動作について示すフローチャートである。発行者が管理するグループに所属するメンバーは、Ｎ人の署名人特定者の中から署名人（該メンバー自分自身）を特定させたいと思うｊ人の署名人特定者ｉ＿１〜ｉ＿ｊを選択して（ｊは自然数、かつｊ≦Ｎ）、メンバー装置２００の署名生成部２１２に対してｉｐｋ、ｒｐｋ、署名人特定者情報、署名人特定者論理構造、メッセージＭ、以上の各データを入力し、メンバー装置２００ｂの入出力部１３がこの入力を受け取る（ステップＳ１１１）。
【００６１】
ここで、メンバー記憶部２２０には、署名人が指定した署名人特定者の公開鍵が記憶されている署名人特定者リスト２２１が予め記憶されている。または、署名人特定者リスト２２１には署名人特定者の名前や公開鍵が公開されている場所の情報やＵＲＬなど、公開鍵とリンクする情報が予め記憶されているようにしてもよい。
【００６２】
また、署名人特定者論理構造は、署名人特定者情報によって指定された署名人特定者ｉ＿１〜ｉ＿ｊの署名人特定権限に対する論理構造を指定するものである。例えば、「１人で特定可能：ｉ＿１，ｉ＿２」「協力して特定可能：（ｉ＿３，ｉ＿４），（ｉ＿５，ｉ＿６，ｉ＿７）」のように記載されている。または「ｉ＿１  ＯＲ  ｉ＿２  ＯＲ（ｉ＿３  ＡＮＤ  ｉ＿４）ＯＲ（ｉ＿５  ＡＮＤ  ｉ＿６  ＡＮＤ  ｉ＿７）」のように記載することもできる。ここでは、簡単のために、「１人で特定可能：ｉ＿１，ｉ＿２」「協力して特定可能：（ｉ＿３，ｉ＿４），（ｉ＿５，ｉ＿６，ｉ＿７）」と記載されているものとする。
【００６３】
署名人特定者公開鍵取得手段２１２ｂ１は、署名人特定者リスト２２１を参照して、ユーザが指定した署名人特定者の公開鍵ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］を取得する。そして署名人特定者公開鍵取得手段２１２ｂ１は、メンバー記憶部２２０から該メンバーのｍｐｋとｍｓｋとを読み込む。（ステップＳ１１２）
ｉｐｋ、ｒｐｋ、ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、署名人特定者論理構造、ｍｐｋ、ｍｓｋ、メッセージＭ、以上のデータをここまでで受け取った署名生成手段２１２ｂ２は、この署名人特定者論理構造にしたがって、署名人情報ｈを暗号化する。１人で特定可能である署名人特定者ｉ＿１およびｉ＿２に対しては、署名生成部２１２ｂは各々単独で特定可能な暗号であるＥＮＣ［ｏｐｋ［ｉ＿１］］（ｈ）、ＥＮＣ［ｏｐｋ［ｉ＿２］］（ｈ）を生成する。
【００６４】
協力して特定可能である署名人特定者ｉ＿３〜ｉ＿４の組に対して、署名生成部２１２ｂはｏｓｋ［ｉ＿３］とｏｓｋ［ｉ＿４］に対応する公開鍵であるｏｐｋ［ｉ＿３，ｉ＿４］を生成する。同様に署名生成部２１２ｂは、協力して特定可能である署名人特定者ｉ＿５〜ｉ＿７の組に対して、ｏｓｋ［ｉ＿５］、ｏｓｋ［ｉ＿６］およびｏｓｋ［ｉ＿７］に対応する公開鍵ｏｐｋ［ｉ＿５，ｉ＿６，ｉ＿７］を生成する。その上で署名生成部２１２ｂは、それらの各々の暗号鍵を利用して、署名人情報ｈを暗号化してＥＮＣ［ｏｐｋ［ｉ＿３，ｉ＿４］］（ｈ）、ＥＮＣ［ｏｐｋ［ｉ＿５，ｉ＿６，ｉ＿７］］を生成する（ステップＳ１１３）。
【００６５】
続いて署名生成手段２１２ｂ２は、ＥＮＣ［ｉ＿１］（ｈ），ＥＮＣ［ｉ＿２］（ｈ），ＥＮＣ［ｏｐｋ［ｉ＿３，ｉ＿４］］（ｈ）、ＥＮＣ［ｏｐｋ［ｉ＿５，ｉ＿６，ｉ＿７］］を含むグループ署名データσと、署名人特定者情報である署名人特定者の公開鍵（ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］）、および署名人特定者論理構造を出力する（ステップＳ１１４）。
【００６６】
図８は、図６に示した検証装置３００ｂがグループ署名を検証する動作について示すフローチャートである。メンバー装置２００ｂによって図７に示す動作で生成されたグループ署名データ、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、署名人特定者論理構造、さらにｉｐｋおよびｒｐｋを、検証者が検証装置３００に入力する（ステップＳ１２１）。
【００６７】
協力して特定可能である署名人特定者ｉ＿３〜ｉ＿４の組に対して、検証部３１１ｂはｏｓｋ［ｉ＿３］とｏｓｋ［ｉ＿４］に対応するｏｐｋ［ｉ＿３，ｉ＿４］を生成する。署名人特定者ｉ＿５〜ｉ＿７の組に対しては、検証部３１１ｂはｏｓｋ［ｉ＿５］、ｏｓｋ［ｉ＿６］とｏｓｋ［ｉ＿７］に対応するｏｐｋ［ｉ＿５，ｉ＿６，ｉ＿７］を生成する。そして検証部３１１ｂは、これらのｏｐｋ［ｉ＿１］、ｏｐｋ［ｉ＿２］，ｏｐｋ［ｉ＿３，ｉ＿４］，ｏｐｋ［ｉ＿５，ｉ＿６，ｉ＿７］を用いて、グループ署名データσが正当であるか否かを判断して（ステップＳ１２２）、正当であれば受理（ステップＳ１２３）、そうでなければ不受理（ステップＳ１２４）をそれぞれ出力する。
【００６８】
図９は、図６に示した署名人特定装置４００ｂが署名人を特定する動作について示すフローチャートである。メンバー装置２００によって図３に示す動作で生成されたグループ署名データσ、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、および署名人特定者論理構造を、署名人特定者が署名人特定装置４００ｂに入力する（ステップＳ１３１）。
【００６９】
署名人特定者秘密鍵取得手段４１２ｂ１は、署名人特定者記憶部４２０から署名人特定者の秘密鍵の集合ＯＳＫを読み込む。ここで、入力される署名人特定者の秘密鍵は１つ以上であればいくつでも構わない。以下では、ＯＳＫ＝（ｏｓｋ［ｉ＿３］，ｏｓｋ［ｉ＿４］）が入力された場合を例に説明を行う（ステップＳ１３２）。
【００７０】
署名人特定手段４１２ｂ２は、ステップＳ１３１で入力された署名人特定者論理構造を、ＯＳＫが満たすことを確認する。すなわち、ＯＳＫに含まれる秘密鍵が、署名人特定者論理構造に指定された条件を満たし、署名人特定を行うことができることを確認する（ステップＳ１３３）。満たしていなければ特定失敗を出力して処理を終了する（ステップＳ１３７）。満たしていれば、必要な秘密鍵ｏｓｋ［ｉ＿３］，ｏｓｋ［ｉ＿４］を用いてσに含まれる暗号ＥＮＣ［ｏｐｋ［ｉ＿３］，ｏｐｋ［ｉ＿４］］（ｈ）を復号し、署名人情報ｈを得る（ステップＳ１３４）。
【００７１】
ステップＳ１３４までの処理で署名人情報ｈを得たメンバー検索手段４１２ｂ３は、メンバーリスト４２１を読み込んで署名人情報ｈに対応するメンバーのＩＤを検索して、そのＩＤを出力する（ステップＳ１３５〜１３６）。
【００７２】
（第２の実施形態の全体的な動作）
次に、上記の実施形態の全体的な動作について説明する。本実施形態に係る署名生成方法は、前述の第１の実施形態の動作に加えて、入力を受け付ける工程が、２名以上の署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け（図７：ステップＳ１１１）、グループ署名データを生成する工程が、署名人特定者論理構造を利用してグループ署名データを生成する（図７：ステップＳ１１３）。
【００７３】
そして、本実施形態に係る署名人特定方法は、前述の第１の実施形態の動作に加えて、入力を受け付ける工程が、２名以上の署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け（図９：ステップＳ１３１）、グループ署名を復号する工程が、署名人特定者論理構造を利用してグループ署名を復号する（図９：ステップＳ１３４）。
【００７４】
ここで、上記各動作ステップについては、これをコンピュータで実行可能にプログラム化し、これらを前記各ステップを直接実行するコンピュータである署名生成装置（メンバー装置２００ｂ）および署名人特定装置４００ｂに実行させるようにしてもよい。
この構成および動作により、本実施形態は以下のような効果を奏する。
【００７５】
本実施形態では、署名人が２名以上の署名人特定者が協力して署名人を特定するという条件を含むグループ署名データを生成できるので、第１の実施形態と比べてユーザおよび署名人特定者にとっての利便性を増加させることができる。しかも、処理に係るグループ署名データなどのデータ量の総計は、署名人特定者論理構造に相当する分が増すだけであるので、署名人特定者の数に比例して増大するなどのようなことはない。
【００７６】
前述の第１の実施形態と同様に、本実施形態では、グループ署名データの生成に当たっては、前述の特許文献および非特許文献にあるような任意の公知技術を適用することができるが、特に非特許文献１、非特許文献３、非特許文献４に記載された方式に適している。これらの方式には失効管理装置が存在しないが、失効管理者の鍵ペアｒｓｋおよびｒｐｋを空データとすることによって容易に適用することができる。この場合、非特許文献１に記載の方式における共通パラメータは楕円エルガマル暗号の群およびその生成元であり、非特許文献３と４記載の方式における共通パラメータは利用する楕円曲線およびその基点である。
【００７７】
（第３の実施形態）
本発明の第３の実施形態は、前述の第１の実施形態の構成に加えて、署名装置（メンバー装置２００ｃ）の署名生成手段２１２ｃ２は、全ての署名人特定者に対して共通する乱数を利用して署名人情報を暗号化したデータを含むグループ署名データを生成するように構成した。
【００７８】
この構成を備えることにより、本実施形態は、グループ署名データのデータ長が署名人特定者の人数に応じて増大することがなくなる。
以下、これをより詳細に説明する。
【００７９】
図１１は、本発明の第３の実施形態に係るグループ署名システム１ｃ全体の構成を示す説明図である。グループ署名システム１ｃは、ハードウェアおよびソフトウェアの構成は第１および第２の実施形態で説明したものと同一であるが、後述するように署名生成部、検証部、署名人特定部の各々の動作が第１の実施形態で説明したものと異なる。これらを各々、署名生成部２１２ｃ、検証部３１１ｃ、署名人特定部４１２ｃという。署名生成部２１２ｃは、署名人特定者公開鍵取得手段２１２ｃ１と、署名生成手段２１２ｃ２とを有する。署名人特定部４１２ｃは、署名人特定者秘密鍵取得手段４１２ｃ１と、署名人特定手段４１２ｃ２と、メンバー検索手段４１２ｃ３とを有する。また、メンバー装置、検証装置、署名人特定装置を各々、メンバー装置２００ｃ、検証装置３００ｃ、署名人特定装置４００ｃという。これら各々の装置のハードウェア的な構成は、図２で説明したものと同一である。
【００８０】
本発明の第３の実施形態は、前述した第１の実施形態によるグループ署名システム１を、非特許文献２に記載のグループ署名方式における発行者、署名人特定者、失効管理者、メンバーの公開鍵・秘密鍵を用いて実現した例である。
【００８１】
本実施形態でも採用する非特許文献２に記載のグループ署名方式では、発行者、署名人特定者、失効管理者、メンバーの公開鍵・秘密鍵は以下のようになっている。ただし，κ＿ｎ、κ＿ｌ、κ＿ｅ、κ＿｛ｅ’｝、κ、κ＿ｃ、κ＿Ｓはいずれもセキュリティパラメータである。安全性の観点から、各セキュリティパラメータはκ＿ｎ＝κ＿ｌ＝１０２４、κ＿ｅ＝５０４、κ＿｛ｅ’｝＝６０、κ＝１６０、κ＿ｃ＝１６０、κ＿Ｓ＝６０以上であることが望ましい。
【００８２】
発行者公開鍵ｉｐｋ＝（ｎ，ａ＿０，ａ＿１，ａ＿２）、発行者秘密鍵ｉｓｋ＝（ｐ＿１，ｐ＿２）
ここでｐ＿１，ｐ＿２はそれぞれκ＿ｎ／２ビットの安全素数（Safe Prime）、つまり、ｐ＿１＝２ｐ’＿１＋１，ｐ＿２＝２ｐ’＿２＋１を満たす素数ｐ’＿１，ｐ’＿２が存在する素数である。ここで、ｎ＝ｐ＿１ｐ＿２である。また、ａ＿０、ａ＿１、ａ＿２はＱＲ（ｎ）の元である。
【００８３】
署名人特定者公開鍵ｏｐｋ＝（ｑ，ｇ，Ｈ＿１，Ｈ＿２），署名人特定者秘密鍵ｏｓｋ＝（ｙ＿１，ｙ＿２）
ここで、ｑはＤＤＨ（Computational Diffie-Hellman）仮定が成り立つ群Ｇ、Ｇの位数である。また、群Ｇの生成元ｇ、Ｈ＿１＝［ｙ＿１］ｇ、Ｈ＿２＝［ｙ＿２］ｇである。
【００８４】
ただし、安全性の観点から、署名人特定者１〜Ｎは共通パラメータ（ｑ，ｇ）を利用していることが望ましい。すなわち、署名人特定者ｉ（１≦ｉ≦Ｎ）の鍵ペアをｏｐｋ［ｉ］およびｏｓｋ［ｉ］と記載することにすると、以下に示す数１が成立する。
【数１】
2011024011.tif 000003
【００８５】
失効管理者公開鍵ｒｐｋ＝（ｌ，ｂ，ｗ），失効管理者秘密鍵ｒｓｋ＝（ｌ＿１，ｌ＿２）
ｌ＿１，ｌ＿２はそれぞれκ＿ｌ／２ビットの安全素数であり、ｌ＝ｌ＿１ｌ＿２である。また、ｂ，ｗはＱＲ（ｌ）の元である。
【００８６】
メンバーＵ＿ｉの公開鍵ｍｐｋ＝（ｈ＿ｉ，Ａ＿ｉ，ｅ’＿ｉ，Ｂ＿ｉ），メンバーＵ＿ｉの秘密鍵ｍｓｋ＝ｘ＿ｉ
ここでｈ＿ｉ、Ｂ＿ｉおよびａ＿０ａ＿１は、以下に示す数２に示す関係を満たす。
【数２】
2011024011.tif 000004
【００８７】
図１１は、図１０に示したメンバー装置２００ｃがグループ署名を生成する動作について示すフローチャートである。発行者が管理するグループに所属するメンバーは、Ｎ人の署名人特定者の中から署名人（該メンバー自分自身）を特定させたいと思うｊ人の署名人特定者ｉ＿１〜ｉ＿ｊを選択して（ｊは自然数、かつｊ≦Ｎ）、メンバー装置２００の署名生成部２１２に対してｉｐｋ、ｒｐｋ、署名人特定者情報、メッセージＭ、以上の各データを入力し、メンバー装置２００ｃの入出力部１３がこの入力を受け取る（ステップＳ２１１）。
【００８８】
ここで、メンバー記憶部２２０には、署名人が指定した署名人特定者の公開鍵が記憶されている署名人特定者リスト２２１が予め記憶されている。または、署名人特定者リスト２２１には署名人特定者の名前や公開鍵が公開されている場所の情報やＵＲＬなど、公開鍵とリンクする情報が予め記憶されているようにしてもよい。
【００８９】
署名人特定者公開鍵取得手段２１２ｃ１は、この署名人特定者リスト２２１を参照して、ユーザが指定した署名人特定者の公開鍵ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］を取得する。そして署名人特定者公開鍵取得手段２１２ｃ１は、メンバー記憶部２２０から該メンバーのｍｐｋ＿ｉ＝（ｈ＿ｉ，Ａ＿ｉ，ｅ’＿ｉ，Ｂ＿ｉ）、ｍｓｋ＿ｉ＝ｘ＿ｉを読み込む。（ステップＳ２１２）ｉｐｋ、ｒｐｋ、ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、ｍｐｋ＿ｉ、ｍｓｋ＿ｉ、メッセージＭを受け取った署名生成手段２１２ｃ２は、以下のステップＳ２１３〜２２３に示す演算処理を行う。
【００９０】
署名生成手段２１２ｃ２は、Ｚ＿［ｑ］の要素ρ＿Ｅをランダムに選び、数３で示すＥを計算する（ステップＳ２１３）。
【数３】
2011024011.tif 000005
【００９１】
この数３で、ρ＿Ｅが、本願の請求項でいう「共通の乱数」となる。１人の署名人特定者に対して、署名生成手段２１２ｃ２は数４に示すように３つの要素を計算するので、署名人特定者がｊ人いるとすると３ｊ個の要素を計算することになる。
【数４】
2011024011.tif 000006
【００９２】
本実施形態では、これらの３ｊ個の要素で使用される乱数ρ＿Ｅをすべての署名人特定者に対して共通化しているので、３つの要素のうちの１つである［ρ＿Ｅ］ｇがすべての署名人特定者にとって共通となる。従って、実際には要素の計算は２ｊ＋１個で済み、計算量をほぼ３分の２に削減することができる。
【００９３】
これに続いて署名生成手段２１２ｃ２は、κ＿ｎ／２ビットのρ＿ｍをランダムに選び、数５で示すＡ＿［ｃｏｍ］およびｓを計算する。ただし、ｅ＿ｉ＝２＾｛κ＿｛ｅ｝｝＋ｅ’＿ｉである（ステップＳ２１４）。
【数５】
2011024011.tif 000007
【００９４】
署名生成手段２１２ｃ２は、κ＿ｌ／２ビットのρ＿ｒをランダムに選び、数６で示すＢ＿［ｃｏｍ］およびｔを計算する（ステップＳ２１５）。
【数６】
2011024011.tif 000008
【００９５】
署名生成手段２１２ｃ２は、λ＝κ＿ｎ＋κ＋κ＿Ｓとし、λビットのμ＿ｘをランダムに選ぶ。また、κ＿ｅ＋（κ＿ｎ／２）＋κ＿ｃ＋κ＿Ｓ  ビットのμ＿Ｓ、κ＿｛ｅ’｝＋κ＿ｃ＋κ＿Ｓビットのμ＿｛ｅ’｝、κ＿｛ｅ’｝＋κ＿ｌ／２＋κ＿ｃ＋κ＿Ｓビットのμ＿ｔ、およびＺ＿ｑの要素μ＿Ｅの各々をそれぞれランダムに選ぶ（ステップＳ２１６）。
【００９６】
署名生成手段２１２ｃ２は、数７で示すＶ＿Ｃを計算する（ステップＳ２１７）。
【数７】
2011024011.tif 000009
【００９７】
署名生成手段２１２ｃ２は、数８で示すＶ＿Ｍを計算する（ステップＳ２１８）。
【数８】
2011024011.tif 000010
【００９８】
署名生成手段２１２ｃ２は、数９で示すＶ＿Ｒを計算する（ステップＳ２１９）。
【数９】
2011024011.tif 000011
【００９９】
署名生成手段２１２ｃ２は、数１０で示すｃを計算する（ステップＳ２２０）。
【数１０】
2011024011.tif 000012
【０１００】
署名生成手段２１２ｃ２は、数１１で示すτ＿ｘ、τ＿ｓ、τ＿ｔ、τ＿｛ｅ’｝、τ＿Ｅの各々を計算する（ステップＳ２２１）。
【数１１】
2011024011.tif 000013
【０１０１】
署名生成手段２１２ｃ２は、数１２で示す各条件が成立することを確認する（ステップＳ２２２）。成立しない場合上記ステップＳ２１６に戻って他のμ＿ｘ、μ＿Ｓ、μ＿｛ｅ’｝、μ＿ｔ、μ＿Ｅの各々をそれぞれランダムに選び直す。
【数１２】
2011024011.tif 000014
【０１０２】
署名生成手段２１２ｃ２は、以上の計算で得られた（σ＝（（Ｅ，Ａ＿［ｃｏｍ］，Ｂ＿［ｃｏｍ］，ｃ，τ＿ｘ，τ＿Ｓ，τ＿｛ｅ’｝，τ＿ｔ，τ＿Ｅ），Ｍ），署名人特定者情報）を、グループ署名データとして出力する（ステップＳ２２３）。
【０１０３】
図１２は、図１０に示した検証装置３００ｃがグループ署名を検証する動作について示すフローチャートである。メンバー装置２００ｃによって図１２に示す動作で生成されたグループ署名データσ、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、さらにｉｐｋおよびｒｐｋを、検証者が検証装置３００に入力する（ステップＳ３２１）。検証部３１１ｃは、これらのデータに対して以下のステップＳ３２２〜３２４に示す演算を行い、このグループ署名を検証する。
【０１０４】
検証部３１１ｃは、数１３で示す各条件が成立することを確認する（ステップＳ３２２）。成立すればステップＳ３２３以降の処理に進み、成立しなければ不受理を出力して処理を終了する（ステップＳ３２６）。
【数１３】
2011024011.tif 000015
【０１０５】
検証部３１１ｃは、数１４で示すτ＿ｅ、Ｖ’＿Ｃ、Ｖ’＿Ｍ、Ｖ’＿Ｒの各々を計算する（ステップＳ３２３）。
【数１４】
2011024011.tif 000016
【０１０６】
検証部３１１ｃは、数１５で示す条件が成立しているか否かを確認し（ステップＳ３２４）、成立していれば受理を出力し（ステップＳ３２５）、そうでなければ不受理を出力して処理を終了する（ステップＳ３２６）。
【数１５】
2011024011.tif 000017
【０１０７】
図１３は、図１０に示した署名人特定装置４００ｃが行う署名人を特定する動作について示すフローチャートである。メンバー装置２００ｃによって図１２に示す動作で生成されたグループ署名データ、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］を、署名人特定者が署名人特定装置４００ｃに入力する（ステップＳ３３１）。
【０１０８】
署名人特定者秘密鍵取得手段４１２ｃ１は、署名人特定者記憶部４２０に記憶されている自らの署名人特定者秘密鍵ｏｓｋ［ｉ］を読み込む（ステップＳ３３２）。署名人特定手段４１２ｃ２は、受け取った署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］の中に自らの署名人特定者秘密鍵ｏｓｋ［ｉ］に対応する公開鍵ｏｐｋ［ｉ］が含まれているか否かを判断する（ステップＳ３３３）。ここで、ｏｓｋ＿［ｉ］＝（ｙ＿｛ｉ，１｝，ｙ＿｛ｉ＿２｝）であるため，数１６に示す条件を満たすｉ＿ｋが存在すれば、受け取った署名人特定者情報の中に自らの署名人特定者秘密鍵に対応する公開鍵が含まれていることになる。
【数１６】
2011024011.tif 000018
【０１０９】
ステップＳ３３３で含まれていると判断されれば、ステップＳ３３４以降の処理に進む。含まれていないと判断されれば、失敗を出力して処理を終了する（ステップＳ３３７）。含まれていれば、署名人特定手段４１２ｃ２はこの秘密鍵ｏｓｋ［ｉ＿ｋ］でσに含まれる暗号を復号して署名人情報ｈを得る（ステップＳ３３４）。
【０１１０】
より具体的には、グループ署名データσの要素Ｅに含まれるｏｐｋ［ｉ］で暗号化された部分をＥ＿１およびＥ＿２とする。このとき、署名人特定手段４１２ｃ２は数１７で示すＳ＿１およびＳ＿２を計算し、Ｓ＿１＝Ｓ＿２であれば署名人情報ｈ＝Ｓ＿１である。
【数１７】
2011024011.tif 000019
【０１１１】
ステップＳ３３４までの処理で署名人情報ｈを得たメンバー検索手段４１２ｃ３は、メンバーリスト４２１を読み込んで署名人情報ｈに対応するメンバーのＩＤを検索して、そのＩＤを出力する（ステップＳ３３５〜３３６）。
【０１１２】
以上で説明したように、本実施形態は次の効果を奏する。
本実施形態は、全ての署名人特定者に対して共通する乱数を利用して署名人情報を暗号化したデータを含むグループ署名データを生成するように構成したので、署名人特定者の人数をｊとすると、計算量を３ｊ個から２ｊ＋１個に削減することができる。
【０１１３】
（第４の実施形態）
本発明の第４の実施形態は、前述の第２の実施形態の構成に加えて、署名装置（メンバー装置２００ｄ）の入力部（入出力部１３）が、２名以上の署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、署名生成部２１２ｄが、署名人特定者論理構造を利用してグループ署名データを生成するように構成した。
【０１１４】
さらに、これに対して署名人特定装置４００の入力部（入出力部１３）が、２名以上の署名人特定者が協力して署名人を特定する旨の論理条件を含みうる署名人特定者論理構造の入力を受け付け、署名人特定部４１２ｄが、署名人特定者論理構造を利用してグループ署名を復号する。
【０１１５】
この構成を備えることにより、前述の第２および第３の実施形態の両方の効果を同時に得ることが可能となる。
以下、これをより詳細に説明する。
【０１１６】
図１４は、本発明の第４の実施形態に係るグループ署名システム１ｄ全体の構成を示す説明図である。グループ署名システム１ｄは、ハードウェアおよびソフトウェアの構成は第１〜第３の実施形態で説明したものと同一であるが、後述するように署名生成部、検証部、署名人特定部の各々の動作が第１の実施形態で説明したものと異なる。これらを各々、署名生成部２１２ｄ、検証部３１１ｄ、署名人特定部４１２ｄという。署名生成部２１２ｄは、署名人特定者公開鍵取得手段２１２ｄ１と、署名生成手段２１２ｄ２とを有する。署名人特定部４１２ｄは、署名人特定者秘密鍵取得手段４１２ｄ１と、署名人特定手段４１２ｄ２と、メンバー検索手段４１２ｄ３とを有する。また、メンバー装置、検証装置、署名人特定装置を各々、メンバー装置２００ｄ、検証装置３００ｄ、署名人特定装置４００ｄという。これら各々の装置のハードウェア的な構成は、図２で説明したものと同一である。
【０１１７】
本発明の第４の実施形態は、前述した第２の実施形態によるグループ署名システム１ｂを、非特許文献２に記載のグループ署名方式における発行者、署名人特定者、失効管理者、メンバーの公開鍵・秘密鍵を用いて実現する場合の例である。
【０１１８】
本実施形態でも採用する非特許文献２に記載のグループ署名方式では、発行者、署名人特定者、失効管理者、メンバーの公開鍵・秘密鍵は以下のようになっている。ただし，κ＿ｎ、κ＿ｌ、κ＿ｅ、κ＿｛ｅ’｝、κ、κ＿ｃ、κ＿Ｓはいずれもセキュリティパラメータである。安全性の観点から、各セキュリティパラメータはκ＿ｎ＝κ＿ｌ＝１０２４、κ＿ｅ＝５０４、κ＿｛ｅ’｝＝６０、κ＝１６０、κ＿ｃ＝１６０、κ＿Ｓ＝６０以上であることが望ましい。
【０１１９】
発行者公開鍵ｉｐｋ＝（ｎ，ａ＿０，ａ＿１，ａ＿２）、発行者秘密鍵ｉｓｋ＝（ｐ＿１，ｐ＿２）
ここでｐ＿１，ｐ＿２はそれぞれκ＿ｎ／２ビットの安全素数（Safe Prime）、つまり、ｐ＿１＝２ｐ’＿１＋１，ｐ＿２＝２ｐ’＿２＋１を満たす素数ｐ’＿１，ｐ’＿２が存在する素数である。ここで、ｎ＝ｐ＿１ｐ＿２である。また、ａ＿０、ａ＿１、ａ＿２はＱＲ（ｎ）の元である。
【０１２０】
署名人特定者公開鍵ｏｐｋ＝（ｑ，ｇ，Ｈ＿１，Ｈ＿２），署名人特定者秘密鍵ｏｓｋ＝（ｙ＿１，ｙ＿２）
ここで、ｑはＤＤＨ（Computational Diffie-Hellman）仮定が成り立つ群Ｇ、Ｇの位数である。また、群Ｇの生成元ｇ、Ｈ＿１＝［ｙ＿１］ｇ、Ｈ＿２＝［ｙ＿２］ｇである。
【０１２１】
ただし、安全性の観点から、署名人特定者１〜Ｎは共通パラメータ（ｑ，ｇ）を利用していることが望ましい。すなわち、署名人特定者ｉ（１≦ｉ≦Ｎ）の鍵ペアをｏｐｋ［ｉ］およびｏｓｋ［ｉ］と記載することにすると、以下に示す数１８が成立する。
【数１８】
2011024011.tif 000020
【０１２２】
失効管理者公開鍵ｒｐｋ＝（ｌ，ｂ，ｗ），失効管理者秘密鍵ｒｓｋ＝（ｌ＿１，ｌ＿２）
ｌ＿１，ｌ＿２はそれぞれκ＿ｌ／２ビットの安全素数であり、ｌ＝ｌ＿１ｌ＿２である。また、ｂ，ｗはＱＲ（ｌ）の元である。
【０１２３】
メンバーＵ＿ｉの公開鍵ｍｐｋ＝（ｈ＿ｉ，Ａ＿ｉ，ｅ’＿ｉ，Ｂ＿ｉ），メンバーＵ＿ｉの秘密鍵ｍｓｋ＝ｘ＿ｉ
ここでｈ＿ｉ、Ｂ＿ｉおよびａ＿０ａ＿１は、以下に示す数１９に示す関係を満たす。
【数１９】
2011024011.tif 000021
【０１２４】
図１５は、図１４に示したメンバー装置２００ｄがグループ署名を生成する動作について示すフローチャートである。発行者が管理するグループに所属するメンバーは、Ｎ人の署名人特定者の中から署名人（該メンバー自分自身）を特定させたいと思うｊ人の署名人特定者ｉ＿１〜ｉ＿ｊを選択して（ｊは自然数、かつｊ≦Ｎ）、メンバー装置２００の署名生成部２１２に対してｉｐｋ、ｒｐｋ、署名人特定者情報、署名人特定者論理構造、メッセージＭ、以上の各データを入力する（ステップＳ４１１）。
【０１２５】
本実施例では、簡単のため、署名人情報は署名人特定者の公開鍵ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿７］、署名人特定者論理構造は第２の実施形態で説明したものと同様に「１人で特定可能：ｉ＿１，ｉ＿２」「協力して特定可能：（ｉ＿３，ｉ＿４），（ｉ＿５，ｉ＿６，ｉ＿７）」が入力されたものとして説明を行う。署名人特定者の公開鍵は１つ以上であればいくつ入力されてもよいし、論理構造は充足可能な論理式であればどのような論理式でもよい。
【０１２６】
署名人特定者公開鍵取得手段２１２ｃ１は、署名人特定者リスト２２１を参照して、ユーザが指定した署名人特定者の公開鍵ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］を取得する。そして署名人特定者公開鍵取得手段２１２ｃ１は、メンバー記憶部２２０から該メンバーのｍｐｋ＿ｉ＝（ｈ＿ｉ，Ａ＿ｉ，ｅ’＿ｉ，Ｂ＿ｉ），ｍｓｋ＿ｉ＝ｘ＿ｉとを読み込む（ステップＳ４１２）。
【０１２７】
ｉｐｋ、ｒｐｋ、ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、署名人特定者論理構造、ｍｐｋ＿ｉ、ｍｓｋ＿ｉ、メッセージＭ、以上のデータをここまでで受け取った署名生成部２１２ｄは、この署名人特定者論理構造にしたがって、以下のステップＳ４１３〜４２３に示す演算処理を行う。
【０１２８】
署名生成手段２１２ｄ２は、以下に示す数２０に示す演算によってｏｐｋ［ｉ＿３，ｉ＿４］およびｏｐｋ［ｉ＿５，ｉ＿６，ｉ＿７］を算出する（ステップＳ４１３）。
【数２０】
2011024011.tif 000022
【０１２９】
続いて署名生成手段２１２ｄ２は、Ｚ＿｛ｑ｝の要素ρ＿Ｅをランダムに選び、以下の数２１に示す演算によってＥを算出する（ステップＳ４１４）。
【数２１】
2011024011.tif 000023
【０１３０】
この数２１で、ρ＿Ｅが、本願の請求項でいう「共通の乱数」となる。この「共通の乱数」による効果は、前述の第３の実施形態の所（図１２のステップＳ２１３）で説明したものと同一である。
【０１３１】
続いて署名生成手段２１２ｄ２は、κ＿ｎ／２ビットのρ＿ｍをランダムに選び、以下の数２２に示す演算によってＡ＿［ｃｏｍ］およびｓを算出する（ステップＳ４１５）。ただし、ｅ＿ｉ＝２＾｛κ＿｛ｅ｝｝＋ｅ’＿ｉである。
【数２２】
2011024011.tif 000024
【０１３２】
続いて署名生成手段２１２ｄ２は、κ＿ｎ／２ビットのρ＿ｒをランダムに選び、以下の数２３に示す演算によってＢ＿［ｃｏｍ］およびｔを算出する（ステップＳ４１６）。
【数２３】
2011024011.tif 000025
【０１３３】
続いて署名生成手段２１２ｄ２は、λ＝κ＿ｎ＋κ＋κ＿Ｓとし、λビットのμ＿ｘをランダムに選ぶ。また、κ＿ｅ＋（κ＿ｎ／２）＋κ＿ｃ＋κ＿Ｓビットのμ＿Ｓと、κ＿｛ｅ’｝＋κ＿ｃ＋κ＿Ｓビットのμ＿｛ｅ’｝と、κ＿｛ｅ’｝＋κ＿ｌ／２＋κ＿ｃ＋κ＿Ｓビットのμ＿ｔと、Ｚ＿ｑの要素μ＿Ｅとをそれぞれランダムに選ぶ（ステップＳ４１７）。
【０１３４】
続いて署名生成手段２１２ｄ２は、以下の数２４に示す演算によってＶ＿Ｃを算出する（ステップＳ４１８）。
【数２４】
2011024011.tif 000026
【０１３５】
続いて署名生成手段２１２ｄ２は、以下の数２５に示す演算によってＶ＿Ｍを算出する（ステップＳ４１９）。
【数２５】
2011024011.tif 000027
【０１３６】
続いて署名生成手段２１２ｄ２は、以下の数２６に示す演算によってＶ＿Ｒを算出する（ステップＳ４２０）。
【数２６】
2011024011.tif 000028
【０１３７】
続いて署名生成手段２１２ｄ２は、以下の数２７に示す演算によってｃを算出する（ステップＳ４２１）。
【数２７】
2011024011.tif 000029
【０１３８】
続いて署名生成手段２１２ｄ２は、以下の数２８に示す演算によってτ＿ｘ、τ＿ｓ、τ＿ｔ、τ＿｛ｅ’｝、τ＿Ｅの各々を算出する（ステップＳ４２２）。
【数２８】
2011024011.tif 000030
【０１３９】
署名生成手段２１２ｄ２は、数２９で示す各条件が成立することを確認する（ステップＳ４２３）。成立しない場合上記ステップＳ４１７に戻って他のμ＿ｘ、μ＿Ｓ、μ＿｛ｅ’｝、μ＿ｔ、μ＿Ｅの各々をそれぞれランダムに選び直す。
【数２９】
2011024011.tif 000031
【０１４０】
署名生成手段２１２ｄ２は、以上の計算で得られた（σ＝（（Ｅ，Ａ＿［ｃｏｍ］，Ｂ＿［ｃｏｍ］，ｃ，τ＿ｘ，τ＿Ｓ，τ＿｛ｅ’｝，τ＿ｔ，τ＿Ｅ），Ｍ），署名人特定者情報）をグループ署名データとして出力する（ステップＳ４２４）。
【０１４１】
図１６は、図１４に示した検証装置３００ｄがグループ署名を検証する動作について示すフローチャートである。メンバー装置２００ｄによって図１５に示す動作で生成されたグループ署名データσ、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、署名人特定者論理構造、さらにｉｐｋおよびｒｐｋを、検証者が検証装置３００に入力する（ステップＳ５２１）。検証部３１１ｄは、これらのデータに対して以下のステップＳ５２２〜５２４に示す演算を行い、このグループ署名を検証する。
【０１４２】
本実施例では、簡単のため、署名人情報は署名人特定者の公開鍵ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿７］、署名人特定者論理構造は第２の実施形態で説明したものと同様に「１人で特定可能：ｉ＿１，ｉ＿２」「協力して特定可能：（ｉ＿３，ｉ＿４），（ｉ＿５，ｉ＿６，ｉ＿７）」が入力されたものとして説明を行う。署名人特定者の公開鍵は１つ以上であればいくつ入力されてもよいし、論理構造は充足可能な論理式であればどのような論理式でもよい。
【０１４３】
検証部３１１ｃは、数３０で示す計算を行い、数３１で示す各条件が成立することを確認する（ステップＳ５２２）。成立すればステップＳ５２３以降の処理に進み、成立しなければ不受理を出力して処理を終了する（ステップＳ５２６）。
【数３０】
2011024011.tif 000032
【数３１】
2011024011.tif 000033
【０１４４】
検証部３１１ｃは、数３２で示す各々を計算する（ステップＳ５２３）。
【数３２】
2011024011.tif 000034
【０１４５】
検証部３１１ｄは、数３３で示す条件が成立しているか否かを確認し（ステップＳ５２４）、成立していれば受理を出力し（ステップＳ５２５）、そうでなければ不受理を出力して処理を終了する（ステップＳ５２６）。
【数３３】
2011024011.tif 000035
【０１４６】
図１７は、図１４に示した署名人特定装置４００ｄが行う署名人を特定する動作について示すフローチャートである。メンバー装置２００ｄによって図１５に示す動作で生成されたグループ署名データ、署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］、および署名人特定者論理構造を、署名人特定者ｉ＿３およびｉ＿４がそれぞれの署名人特定装置４００ｄに入力する（ステップＳ５３１）。
【０１４７】
それぞれの署名人特定部４１２ｄは、署名人特定者記憶部４２０に記憶されているそれぞれの署名人特定者秘密鍵ｏｓｋ［ｉ＿３］およびｏｓｋ［ｉ＿４］を読み込み（ステップＳ５３２）、受け取った署名人特定者情報ｏｐｋ［ｉ＿１］〜ｏｐｋ［ｉ＿ｊ］の中に自らの署名人特定者秘密鍵ｏｓｋ［ｉ］に対応する公開鍵ｏｐｋ［ｉ］が含まれ、かつそれらが署名人特定者論理構造を満たしているか否かを判断する（ステップＳ５３３）。
【０１４８】
ステップＳ５３３で満たしていると判断されれば、ステップＳ５３４以降の処理に進む。満たしていないと判断されれば、失敗を出力して処理を終了する（ステップＳ５３７）。満たしていれば、署名人特定部４１２ｄはこの秘密鍵ｏｓｋ［ｉ＿３］およびｏｓｋ［ｉ＿４］でσに含まれる暗号（Ｅ＿０，Ｅ＿｛ｉ＿３，ｉ＿４，１｝，Ｅ＿｛ｉ＿３，ｉ＿４，２｝）を復号して署名人情報ｈを得る（ステップＳ５３４）。
【０１４９】
より具体的には、署名人特定部４１２ｄは数３４で示す各々のｏｐｋおよびｏｓｋを計算し、さらにそこから数３５で示すＳ＿１およびＳ＿２を計算し、Ｓ＿１＝Ｓ＿２であれば署名人情報ｈ＝Ｓ＿１である。
【数３４】
2011024011.tif 000036
【数３５】
2011024011.tif 000037
【０１５０】
ステップＳ５３４までの処理で署名人情報ｈを得た署名人特定部４１２ｄは、メンバーリスト４２１を読み込んで署名人情報ｈに対応するメンバーのＩＤを検索して、そのＩＤを出力する（ステップＳ５３５〜５３６）。
【０１５１】
以上で説明したように、本実施形態は次の効果を奏する。
本実施形態は、第３の実施形態と同様に、全ての署名人特定者に対して共通する乱数を利用して署名人情報を暗号化したデータを含むグループ署名データを生成するように構成したので、署名人特定者の人数をｊとすると、計算量を３ｊ個から２ｊ＋１個に削減することができる。かつ、署名人が２名以上の署名人特定者が協力して署名人を特定するという条件を含むグループ署名データを生成できるので、ユーザおよび署名人特定者にとっての利便性を増加させることができる。
【０１５２】
これまで本発明について図面に示した特定の実施形態をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、本発明の効果を奏する限り、これまで知られたいかなる構成であっても採用することができる。
【産業上の利用可能性】
【０１５３】
本発明は、電子署名を使用するデジタルデータ全般に適用できる。特に、署名人が特定のグループに所属していることを証明することが必要である電子署名において有用である。
【符号の説明】
【０１５４】
１、１ｂ、１ｃ、１ｄ  グループ署名システム
１０  コンピュータ装置
１１、１１０、２１０、３１０、４１０、５１０  プロセッサ
１２  記憶部
１３  入出力部
１４  通信部
１００  発行者装置
１１１  発行者鍵生成手段
１１２  発行手段
１２０  発行者記憶部
１２１、４２１  メンバーリスト
２００、２００ｂ、２００ｃ、２００ｄ  メンバー装置
２１１  参加手段
２１２、２１２ｂ、２１２ｃ、２１２ｄ  署名生成手段
２２０  メンバー記憶部
２２１  署名人特定者リスト
３００、３００ｂ、３００ｃ、３００ｄ  検証装置
３１１、３１１ｂ、３１１ｃ、３１１ｄ  検証手段
３２０  検証者記憶部
４００、４００ｂ、４００ｃ、４００ｄ  署名人特定装置
４１１  署名人特定者鍵生成手段
４１２、４１２ｂ、４１２ｃ、４１２ｄ  署名人特定手段
４２０  署名人特定者記憶部
５００  失効管理者装置
５１１  失効管理者鍵生成手段
５１２  失効手段
５２０  失効管理者記憶部
６００  ネットワーク
【図１】
2011024011.tif 000038
【図２】
2011024011.tif 000039
【図３】
2011024011.tif 000040
【図４】
2011024011.tif 000041
【図５】
2011024011.tif 000042
【図６】
2011024011.tif 000043
【図７】
2011024011.tif 000044
【図８】
2011024011.tif 000045
【図９】
2011024011.tif 000046
【図１０】
2011024011.tif 000047
【図１１】
2011024011.tif 000048
【図１２】
2011024011.tif 000049
【図１３】
2011024011.tif 000050
【図１４】
2011024011.tif 000051
【図１５】
2011024011.tif 000052
【図１６】
2011024011.tif 000053
【図１７】
2011024011.tif 000054