(57)【特許請求の範囲】
【請求項１】
グループ管理装置、グループメンバ装置、代理グループ署名生成装置及び署名検証装置を備えたグループ署名システムであって、
前記グループ管理装置は、
互いに対応するグループ公開鍵及びグループ秘密鍵が記憶されるグループ情報記憶手段と、
前記グループメンバ装置からメンバ公開鍵を含むグループ参加要求を受信する手段と、
前記グループ秘密鍵に基づいて、前記受信したメンバ公開鍵に対する署名を生成する手段と、
この署名をメンバ証明書として前記グループメンバ装置に送信する手段とを備えており、
前記グループメンバ装置は、
互いに対応するメンバ公開鍵及びメンバ署名鍵と、前記メンバ証明書とが互いに関連付けられて記憶されるメンバ情報記憶手段と、
外部からの要求により、前記メンバ情報記憶手段内のメンバ公開鍵、メンバ署名鍵及びメンバ証明書に基づいて、前記代理グループ署名生成装置に対してグループ署名生成の権限を委託するための委託情報を生成する手段と、
前記委託情報を前記代理グループ署名生成装置に送信する手段とを備えており、
前記代理グループ署名生成装置は、
代理グループ署名鍵が記憶される秘密情報記憶手段と、
前記グループメンバ装置から受信した委託情報の正当性を、前記グループ公開鍵に基づいて検証する手段と、
この検証結果が正当性を示すとき、前記委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵を前記秘密情報記憶手段に書き込む手段と、
平文に対する署名要求に応じて、前記秘密情報記憶手段内の代理グループ署名鍵に基づいて、前記平文に対する代理グループ署名を生成する手段とを備えており、
前記署名検証装置は、
前記代理グループ署名生成装置により生成された代理グループ署名を、前記グループ公開鍵に基づいて検証する手段と、
を備えたことを特徴とするグループ署名システム。
【請求項２】
グループメンバ装置及び代理グループ署名生成装置を備えたグループ署名生成システムであって、
前記グループメンバ装置は、
互いに対応するメンバ公開鍵及びメンバ署名鍵と、互いに対応するグループ公開鍵及びグループ秘密鍵を保持するグループ管理装置のグループ秘密鍵により当該メンバ公開鍵が署名処理されてなるメンバ証明書とが互いに関連付けられて記憶されるメンバ情報記憶手段と、
外部からの要求により、前記メンバ情報記憶手段内のメンバ公開鍵、メンバ署名鍵及びメンバ証明書に基づいて、前記代理グループ署名生成装置に対してグループ署名生成の権限を委託するための委託情報を生成する手段と、
前記委託情報を前記代理グループ署名生成装置に送信する手段とを備えており、
前記代理グループ署名生成装置は、
代理グループ署名鍵が記憶される秘密情報記憶手段と、
前記グループメンバ装置から受信した委託情報の正当性を、前記グループ公開鍵に基づいて検証する手段と、
この検証結果が正当性を示すとき、前記委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵を前記秘密情報記憶手段に書き込む手段と、
平文に対する署名要求に応じて、前記秘密情報記憶手段内の代理グループ署名鍵に基づいて、前記平文に対する代理グループ署名を生成する手段と、
を備えたことを特徴とするグループ署名生成システム。
【請求項３】
請求項２に記載のグループ署名生成システムにおいて、
前記代理グループ署名生成装置は、
前記委託情報の正当性を検証する前に、失効する全てのメンバ証明書を特定可能な情報をリスト化してなるメンバ証明書失効リストを前記グループ管理装置から取得する手段と、
前記メンバ証明書失効リスト内に、前記グループメンバ装置から受信したメンバ証明書を特定可能な情報が含まれるか否かを検証する手段と、
前記検証の結果、前記受信したメンバ証明書を特定可能な情報が含まれる場合には、前記委託情報の正当性を検証せずに処理を終了する手段と、
を備えたことを特徴とするグループ署名生成システム。
【請求項４】
グループ署名生成の権限を委託するための委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵に基づいて、平文に対する代理グループ署名を生成する代理グループ署名生成装置に対し、前記委託情報を送信可能なグループメンバ装置であって、
互いに対応するメンバ公開鍵及びメンバ署名鍵と、互いに対応するグループ公開鍵及びグループ秘密鍵を保持するグループ管理装置のグループ秘密鍵により当該メンバ公開鍵が署名処理されてなるメンバ証明書とが互いに関連付けられて記憶されるメンバ情報記憶手段と、
外部からの要求により、前記メンバ情報記憶手段内のメンバ公開鍵、メンバ署名鍵及びメンバ証明書に基づいて、前記代理グループ署名生成装置に対してグループ署名生成の権限を委託するための委託情報を生成する手段と、
を備えたことを特徴とするグループメンバ装置。
【請求項５】
互いに対応するメンバ公開鍵及びメンバ署名鍵と、互いに対応するグループ公開鍵及びグループ秘密鍵を保持するグループ管理装置のグループ秘密鍵により当該メンバ公開鍵が署名処理されてなるメンバ証明書とを互いに関連付けて記憶し、外部からの要求により、前記メンバ公開鍵、メンバ署名鍵及びメンバ証明書とに基づいて、グループ署名生成の権限を委託するための委託情報を生成し、この委託情報を送信可能なグループメンバ装置に対し、前記委託情報を受信可能な代理グループ署名生成装置であって、
代理グループ署名鍵が記憶される秘密情報記憶手段と、
前記グループメンバ装置から受信した委託情報の正当性を検証する手段と、
この検証結果が正当性を示すとき、前記委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵を前記秘密情報記憶手段に書き込む手段と、
平文に対する署名要求に応じて、前記秘密情報記憶手段内の代理グループ署名鍵に基づいて、前記平文に対する代理グループ署名を生成する手段と、
前記グループ公開鍵により代理グループ署名を検証可能な署名検証装置に対し、前記生成した代理グループ署名を送信する手段と、
を備えたことを特徴とする代理グループ署名生成装置。
【請求項６】
請求項５に記載の代理グループ署名生成装置において、
前記委託情報の正当性を検証する前に、前記グループ管理装置からメンバ証明書失効リストを取得する手段と、
前記メンバ証明書失効リスト内に、前記メンバ証明書を特定可能な情報が含まれるか否かを検証する手段と、
前記検証の結果、前記メンバ証明書を特定可能な情報が含まれる場合には、前記委託情報の正当性を検証せずに処理を終了する手段と、
を備えたことを特徴とする代理グループ署名生成装置。
【請求項７】
グループ署名生成の権限を委託するための委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵に基づいて、平文に対する代理グループ署名する代理グループ署名生成装置に対し、前記委託情報を送信可能なグループメンバ装置に用いられるプログラムであって、
前記グループメンバ装置のコンピュータを、
互いに対応するメンバ公開鍵及びメンバ署名鍵と、互いに対応するグループ公開鍵及びグループ秘密鍵を保持するグループ管理装置のグループ秘密鍵により当該メンバ公開鍵が署名処理されてなるメンバ証明書とが互いに関連付けられて記憶されるメンバ情報記憶手段、
外部からの要求により、前記メンバ情報記憶手段内のメンバ公開鍵、メンバ署名鍵及びメンバ証明書に基づいて、前記代理グループ署名生成装置に対してグループ署名生成の権限を委託するための委託情報を生成する手段、
として機能させるためのプログラム。
【請求項８】
互いに対応するメンバ公開鍵及びメンバ署名鍵と、互いに対応するグループ公開鍵及びグループ秘密鍵を保持するグループ管理装置のグループ秘密鍵により当該メンバ公開鍵が署名処理されてなるメンバ証明書とを互いに関連付けて記憶し、外部からの要求により、前記メンバ公開鍵、メンバ署名鍵及びメンバ証明書とに基づいて、グループ署名生成の権限を委託するための委託情報を生成し、この委託情報を送信可能なグループメンバ装置に対し、前記委託情報を受信可能な代理グループ署名生成装置に用いられるプログラムであって、
前記代理グループ署名生成装置のコンピュータを、
代理グループ署名鍵が記憶される秘密情報記憶手段、
前記グループメンバ装置から受信した委託情報の正当性を、前記グループ公開鍵に基づいて検証する手段、
この検証結果が正当性を示すとき、前記委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵を前記秘密情報記憶手段に書き込む手段、
平文に対する署名要求に応じて、前記秘密情報記憶手段内の代理グループ署名鍵に基づいて、前記平文に対する代理グループ署名を生成する手段、
前記グループ公開鍵により代理グループ署名を検証可能な署名検証装置に対し、前記生成した代理グループ署名を送信する手段、
として機能させるためのプログラム。
【請求項９】
請求項８に記載のプログラムにおいて、
前記代理グループ署名生成装置のコンピュータを、
前記委託情報の正当性を検証する前に、前記グループ管理装置からメンバ証明書失効リストを取得する手段、
前記メンバ証明書失効リスト内に、前記メンバ証明書を特定可能な情報が含まれるか否かを検証する手段、
前記検証の結果、前記メンバ証明書を特定可能な情報が含まれる場合には、前記委託情報の正当性を検証せずに処理を終了する手段、
として機能させるためのプログラム。
【請求項１０】
グループ管理装置、グループメンバ装置、代理グループ署名生成装置及び署名検証装置が実行するグループ署名方法であって、
前記グループ管理装置が、互いに対応するグループ公開鍵及びグループ秘密鍵をグループ情報記憶装置に記憶するグループ情報記憶工程と、
前記グループ管理装置が、前記グループメンバ装置からメンバ公開鍵を含むグループ参加要求を受信する工程と、
前記グループ管理装置が、前記グループ秘密鍵に基づいて、前記受信したメンバ公開鍵に対する署名を生成する工程と、
前記グループ管理装置が、この署名をメンバ証明書として前記グループメンバ装置に送信する工程と、
前記グループメンバ装置が、互いに対応するメンバ公開鍵及びメンバ署名鍵と、前記メンバ証明書とを互いに関連付けてメンバ情報記憶装置に記憶するメンバ情報記憶工程と、
前記グループメンバ装置が、外部からの要求により、前記メンバ情報記憶装置内のメンバ公開鍵、メンバ署名鍵及びメンバ証明書に基づいて、前記代理グループ署名生成装置に対してグループ署名生成の権限を委託するための委託情報を生成する工程と、
前記グループメンバ装置が、前記委託情報を前記代理グループ署名生成装置に送信する工程と、
前記代理グループ署名生成装置が、代理グループ署名鍵を秘密情報記憶装置に記憶する秘密情報記憶工程と、
前記代理グループ署名生成装置が、前記グループメンバ装置から受信した委託情報の正当性を、前記グループ公開鍵に基づいて検証する工程と、
この検証結果が正当性を示すとき、前記代理グループ署名生成装置が、前記委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵を前記秘密情報記憶装置に書き込む工程と、
前記代理グループ署名生成装置が、平文に対する署名要求に応じて、前記秘密情報記憶装置内の代理グループ署名鍵に基づいて、前記平文に対する代理グループ署名を生成する工程と、
前記署名検証装置が、前記代理グループ署名生成装置により生成された代理グループ署名を、前記グループ公開鍵に基づいて検証する工程と、
を備えたことを特徴とするグループ署名方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループ署名システム、装置、プログラム及び方法に係り、特に、グループ署名を生成する際に、メンバ側装置における計算量と、情報の授受回数とを低減し得るグループ署名システム、装置、プログラム及び方法に関する。
【背景技術】
【０００２】
デジタル署名方式の一種として、グループ署名方式が知られている（例えば、非特許文献１、２参照）。グループ署名方式は、非特許文献１によれば、以下の第１乃至第３の性質を持っている。
【０００３】
第１の性質は、あるグループに所属する任意のメンバがグループ署名を生成可能という性質である。第２の性質は、検証者側において、グループ署名がメンバにより生成されたことを検証可能である性質と、署名を生成したメンバ（以下、署名者という）を特定することが困難という性質（匿名性）とからなる。第３の性質は、特定の情報により、グループ署名から署名者を特定可能という性質である。
【０００４】
このようなグループ署名方式は、様々な方式が提案されている。中でも非特許文献２に記載の方式（以下、非特許文献２方式という）は、安全かつ一般的なデジタル署名方式及び公開鍵暗号化方式を用いて構成可能である。これに加え、非特許文献２方式は、安全性が証明されている。
【０００５】
しかしながら、これらのグループ署名方式は、署名者によるグループ署名生成に多くの計算量を必要とする。このため、携帯電話の如き、低い計算能力のデバイスを署名者が用いる場合、グループ署名生成の計算を行うことが実用上困難となっている。
【０００６】
一方、この困難を解決可能な技術として、特許文献１に記載の方式（以下、特許文献１方式という）がある。
【０００７】
特許文献１方式によれば、低い計算能力の耐タンパー装置と、高い計算能力の利用者端末とを用いている。この利用者端末は、この耐タンパー装置を着脱自在に保持し、耐タンパー装置から情報を授受する。情報の授受回数は、往復で２．５回（片道５回）である（特許文献１の図９、ＳＴ３５〜ＳＴ３９参照）。そして、特許文献１方式においては、高い計算能力をもつ利用者端末が、グループ署名生成の計算のうち、ほとんどの計算を実行する。
【０００８】
従って、特許文献１方式によれば、低い計算能力の耐タンパー装置を用いる場合でも、グループ署名生成の計算を行うことが実用上容易となっている。
【非特許文献１】D. Chaum, E. van Heyst, Group Signatures, Proceedings of EUROCRYPT'91, LNCS 547, Springer-Verlag, pp.257-265, 1991.
【非特許文献２】M. Bellare, D. Micciancio, B. Warinschi, Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions, Proceedings of Eurocrypt 2003, LNCS 2656, Springer-Verlag, pp.614-629, 2003.
【特許文献１】特開２００４−３２０５６２号公報（特に、第１８２乃至第１９０段落、図８及び図９等）
【非特許文献３】渡辺 治, 計算可能性／計算の複雑さ入門, 近代科学社, 1992.
【非特許文献４】U. Feige, D. Lapidot, A. Shamir, Multiple non-interactive zero-knowledge proofs under general assumptions, SIAM Journal of Computing, 29(1), pp.1-28, 1999.
【非特許文献５】A.Sahai, Non-malleable non-interactive zero-knowledge and adaptive chosen-ciphertext security, FOCS'99, pp.543-553, IEEE Computer Society Press, 1999.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
以上のような特許文献１方式は、通常、何の問題も無い。しかしながら、特許文献１方式は、本発明者の検討によれば、グループ署名を生成する際に、メンバ側装置（耐タンパ装置及び利用者端末）における計算量を減らせる可能性があると考えられる。また、特許文献１方式は、本発明者の検討によれば、グループ署名を生成する際に、情報の授受を片道５回よりも低減できる可能性があると考えられる。
【００１０】
本発明は上記実情を考慮してなされたもので、グループ署名を生成する際に、メンバ側装置における計算量と、情報の授受回数とを低減し得るグループ署名システム、装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
第１の発明は、グループ管理装置、グループメンバ装置、代理グループ署名生成装置及び署名検証装置を備えたグループ署名システムであって、前記グループ管理装置としては、互いに対応するグループ公開鍵及びグループ秘密鍵が記憶されるグループ情報記憶手段と、前記グループメンバ装置からメンバ公開鍵を含むグループ参加要求を受信する手段と、前記グループ秘密鍵に基づいて、前記受信したメンバ公開鍵に対する署名を生成する手段と、この署名をメンバ証明書として前記グループメンバ装置に送信する手段とを備えており、前記グループメンバ装置としては、互いに対応するメンバ公開鍵及びメンバ署名鍵と、前記メンバ証明書とが互いに関連付けられて記憶されるメンバ情報記憶手段と、外部からの要求により、前記メンバ情報記憶手段内のメンバ公開鍵、メンバ署名鍵及びメンバ証明書に基づいて、前記代理グループ署名生成装置に対してグループ署名生成の権限を委託するための委託情報を生成する手段と、前記委託情報を前記代理グループ署名生成装置に送信する手段とを備えており、前記代理グループ署名生成装置としては、代理グループ署名鍵が記憶される秘密情報記憶手段と、前記グループメンバ装置から受信した委託情報の正当性を、前記グループ公開鍵に基づいて検証する手段と、この検証結果が正当性を示すとき、前記委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵を前記秘密情報記憶手段に書き込む手段と、平文に対する署名要求に応じて、前記秘密情報記憶手段内の代理グループ署名鍵に基づいて、前記平文に対する代理グループ署名を生成する手段とを備えており、前記署名検証装置としては、前記代理グループ署名生成装置により生成された代理グループ署名を、前記グループ公開鍵に基づいて検証する手段とを備えたグループ署名システムである。
【００１２】
第２の発明は、グループメンバ装置及び代理グループ署名生成装置を備えたグループ署名生成システムであって、前記グループメンバ装置としては、互いに対応するメンバ公開鍵及びメンバ署名鍵と、互いに対応するグループ公開鍵及びグループ秘密鍵を保持するグループ管理装置のグループ秘密鍵により当該メンバ公開鍵が署名処理されてなるメンバ証明書とが互いに関連付けられて記憶されるメンバ情報記憶手段と、外部からの要求により、前記メンバ情報記憶手段内のメンバ公開鍵、メンバ署名鍵及びメンバ証明書に基づいて、前記代理グループ署名生成装置に対してグループ署名生成の権限を委託するための委託情報を生成する手段と、前記委託情報を前記代理グループ署名生成装置に送信する手段とを備えており、前記代理グループ署名生成装置としては、代理グループ署名鍵が記憶される秘密情報記憶手段と、前記グループメンバ装置から受信した委託情報の正当性を、前記グループ公開鍵に基づいて検証する手段と、この検証結果が正当性を示すとき、前記委託情報を含む代理グループ署名鍵を生成し、この代理グループ署名鍵を前記秘密情報記憶手段に書き込む手段と、平文に対する署名要求に応じて、前記秘密情報記憶手段内の代理グループ署名鍵に基づいて、前記平文に対する代理グループ署名を生成する手段と、を備えたグループ署名生成システムである。
【００１３】
（作用）
従って、第１及び第２の各発明は以上のような手段を講じたことにより、グループメンバ装置がグループ署名の生成権限の委託情報を１回だけ代理グループ署名生成装置に送り、代理グループ署名生成装置が代理グループ署名を生成する構成により、グループ署名を生成する際に、メンバ側装置における計算量と、情報の授受回数とを低減させることができる。
【００１４】
なお、第１及び第２の各発明は、各装置からなる構成を「システム」として表現したが、これに限らず、各装置からなる構成又は各装置を「装置」、「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」として表現してもよい。
【発明の効果】
【００１５】
以上説明したように本発明によれば、グループ署名を生成する際に、メンバ側装置における計算量と、情報の授受回数とを低減できる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の各実施形態を図面を用いて説明する。なお、以下の説明中、Sig(x <y>)の表記は、鍵ｘにより、署名対象ｙを署名処理して得られたデジタル署名を意味する。同様に、Enc(x <y>)の表記は、鍵ｘにより、暗号化対象ｙを暗号化処理して得られた暗号文を意味する。さらに、Vrfy(x <y> z)の表記は、鍵xにより、署名zが署名対象yに対する署名であることを検証処理して得られた結果を意味し、検証結果が正しければ1を、検証結果が正しくなければ0を表す。
【００１７】
（第１の実施形態）
図１は本発明の第１の実施形態に係るグループ署名システムの構成を示す模式図であり、図２乃至図４は同システム内の各記憶部の構成を示す模式図である。このグループ署名システムは、グループ管理装置１０、グループメンバ装置２０、代理グループ署名生成装置３０、代理グループ署名検証装置４０を備えている。各装置１０，２０，３０，４０はそれぞれ複数存在しても良いが、ここでは１台ずつの構成として説明する。
【００１８】
さらに本システムでは、公開鍵公開装置５０を用いる。公開鍵公開装置５０は、公開鍵を管理し、公開鍵を任意の第三者から取得可能に公開する。公開鍵公開装置５０は、公開鍵暗号基盤（ＰＫＩ： Public Key Infrastructure）において、一般的に用いられる。
【００１９】
なお、各装置１０、２０、３０、４０は、それぞれコンピュータにより実現される場合、各装置１０、２０、３０、４０の機能をコンピュータに実現させるためのプログラムが予め記憶媒体又はネットワークからインストールされている。これは以下の各実施形態でも同様である。
【００２０】
ここで、グループ管理装置１０は、グループ情報記憶部１１、グループ初期化部１２、グループ情報管理部１３、メンバ証明書生成部１４、グループメンバ特定部１５を備えている。
【００２１】
グループ情報記憶部１１は、グループ情報管理部１３から読出／書込可能なハードウェア資源としての記憶装置である。グループ情報記憶部１１は、図２に示すように、グループのグループＩＤ（＝g）、グループ公開鍵PKg 、グループ秘密鍵SKgが互いに関連付けられて記憶される。ここで、１つのグループＩＤに対して複数組のグループ公開鍵及びグループ秘密鍵が関連付けられていても良い。但しこの場合、グループ公開鍵及びグループ秘密鍵の組を識別できるようにＩＤを付加することが望ましい。また、１つのグループＩＤに対して、対応するグループに参加する全てのメンバのメンバ証明書が関連付けられて記憶される。
【００２２】
グループ初期化部１２は、次の機能(f12-1)〜(f12-3)をもっている。  
(f12-1) 外部からの指示に従い、グループのグループＩＤ（＝g）毎に、互いに対応するグループ公開鍵PKg 及びグループ秘密鍵SKgを生成する機能。  
(f12-2) と、生成されたグループ公開鍵PKg 及びグループ秘密鍵SKgをグループ情報管理部１３へ送る機能。  
(f12-3) グループ公開鍵PKgを公開鍵公開装置５０へ送る機能。
【００２３】
グループ情報管理部１３は、次の機能(f13-1)〜(f13-2)をもっている。  
(f13-1) グループ初期化部１２から送られたグループ公開鍵PKg及びグループ秘密鍵SKgと、メンバ証明書生成部１４より送られたメンバ証明書cert_uとをグループＩＤ毎にグループ情報記憶部１１に書き込む機能。  
(f13-2) メンバ証明書生成部１４又はグループメンバ特定部１５からの要求に応じてグループ情報記憶部１１の記憶内容を要求元に提供する機能。
【００２４】
メンバ証明書生成部１４は、次の機能(f14-1)〜(f14-3)をもっている。  
(f14-1) グループメンバ装置２０からのグループ参加要求に基づいて、メンバ署名鍵SKuに対する零知識証明情報proof_uの正当性を検証する機能。なお、グループ参加要求は、メンバＩＤ（＝ｕ）、メンバ公開鍵PKu及び零知識証明情報proof_uから構成されている。 (f14-2) 検証に成功した場合に、グループ情報管理部１３から取得したグループ秘密鍵SKgを用いてメンバＩＤ（＝ｕ）及びメンバ公開鍵PKuに対して署名を生成する機能。  
(f14-3) この署名をメンバ証明書cert_uとしてグループ情報管理部１３及びグループメンバ装置２０へ送信する機能。
【００２５】
ここで、メンバＩＤはグループメンバ装置２０毎に予め割り当てられた、グループメンバ装置２０を特定可能なＩＤである。しかしながら、メンバＩＤはメンバ公開鍵Pku毎に割り当てられても良い。この場合、グループメンバ装置２０からはメンバＩＤを受信せず、メンバ証明書生成部１４においてメンバ公開鍵Pku毎にメンバＩＤを割り当てる。そして、このメンバＩＤをメンバ証明書cert_uとともにグループ情報管理部１３へ送信してグループ情報記憶部１１へ書き込むとともに、グループメンバ装置２０へも送信する。  グループメンバ特定部１５は、次の機能(f15-1)〜(f15-2)をもっている。  
(f15-1)外部より入力された代理グループ署名ρに関し、グループ情報管理部１３から取得したグループ秘密鍵SKgに基づいて、代理グループ署名ρに含まれる暗号文Ｃを復号する機能。  
(f15-2) 復号結果に含まれるメンバＩＤ（＝ｕ）を出力する機能。
【００２６】
グループメンバ装置２０は、メンバ情報記憶部２１、メンバ登録部２２、グループ署名生成権限委託部２３を備えている。
【００２７】
メンバ情報記憶部２１は、メンバ登録部２１から書込可能で且つグループ署名生成権限委託部２３から読出可能なハードウェア資源としての記憶装置である。メンバ情報記憶部２１は、図３に示すように、メンバＩＤ（＝ｕ）、メンバ公開鍵PKu、メンバ署名鍵SKu及びメンバ証明書cert_uが互いに関連付けられて記憶される。なお、メンバ公開鍵PKu及びメンバ署名鍵SKuは、互いに対応する一対の公開鍵ペアである。
【００２８】
メンバ登録部２２は、次の機能(f22-1)〜(f22-5)をもっている。  
(f22-1) 外部からの要求により、メンバ署名鍵SKu及びメンバ公開鍵PKuを生成する機能。  
(f22-2) メンバ署名鍵SKu及びメンバ公開鍵PKuに基づいて、メンバ公開鍵PKuに対応するメンバ署名鍵SKuの所有を証明する零知識証明情報proof_uを生成する機能。  
(f22-3) メンバＩＤ（＝ｕ）、メンバ公開鍵PKu及び零知識証明情報proof_uをグループ管理装置１０へ送信する機能。  
(f22-4) グループ管理装置１０から受信したメンバ証明書cert_uの正当性を、公開鍵公開装置５０から取得したグループ公開鍵PKgに基づいて検証する機能。  
(f22-5) 正当性が検証されたメンバ証明書cert_u、メンバ署名鍵SKu、メンバ公開鍵PKuをメンバ情報記憶部２１へ書き込む機能。
【００２９】
なお、メンバ登録部２２は、必須の機能ではない。例えば予めメンバ情報がメンバ情報記憶部２１に記憶されている場合には、メンバ登録部２２は省略可能である。
【００３０】
グループ署名生成権限委託部２３は、次の機能(f23-1)〜(f23-5)をもっている。  
(f23-1) 外部からの要求により、メンバ情報記憶部２１内のメンバＩＤ（＝ｕ）、メンバ証明書cert_u、メンバ署名鍵SKu、メンバ公開鍵PKuに基づいて、グループ署名生成の権限を代理グループ署名生成装置３０に委託するための委託情報Dlg_uを生成する機能。  
(f23-1) この委託情報Dlg_uを代理グループ署名生成装置３０へ送信する機能。
【００３１】
代理グループ署名生成装置３０は、秘密情報記憶部３１、グループ署名生成権限受託部３２、代理グループ署名生成部３３を備えている。
【００３２】
秘密情報記憶部３１は、グループ署名生成権限受託部３２から書込可能で且つ代理グループ署名生成部３３から読出可能なハードウェア資源としての記憶装置である。秘密情報記憶部３１は、図４（ａ）に示すように、代理署名鍵SKp 、代理公開鍵PKp及び代理グループ署名鍵SKpgが互いに関連付けられて記憶される。ここで、１組の代理署名鍵SKp 、代理公開鍵PKpに対して、複数の代理グループ署名鍵が関連付けられて記憶されても良い。
【００３３】
ここで、代理署名鍵SKp 及び代理公開鍵PKpは、予め外部より入力され、代理グループ署名生成装置３０固有の一対の鍵データ（公開鍵暗号の鍵ペア）である。代理公開鍵PKpは、予め公開鍵公開装置５０により公開されている。なお、代理グループ署名鍵SKpgは、図４（ｂ）に示すように、委託情報Dlg_u及び代理署名鍵SKp を備えている。委託情報Dlg_uは、メンバＩＤ（＝ｕ）、メンバ公開鍵PKu、メンバ証明書cert_u、連結委託情報<PKp, w> 及び委託証明書cert_pを備えている。メンバ証明書cert_uは、メンバ公開鍵PKuに対するグループ管理装置１０の署名Sig(SKs <PKu>)である。委託証明書cert_pは、連結委託情報<PKp, w>に対するグループメンバ装置３０の署名Sig(SKu <PKp, w>)である。
【００３４】
グループ署名生成権限受託部３２は、次の機能(f32-1)〜(f32-2)をもっている。  
(f32-1) グループメンバ装置２０から受信した委託情報Dlg_uの正当性を公開鍵公開装置５０から取得したグループ公開鍵PKgを用いて検証する機能。  
(f32-2) 委託情報Dlg_uを含む代理グループ署名鍵SKpgを生成して秘密情報記憶部３１へ書き込む機能。
【００３５】
代理グループ署名生成部３３は、次の機能(f33-1)〜(f33-2)をもっている。  
(f33-1) 外部からの平文mに対する署名要求に応じて、秘密情報記憶部３１内の代理グループ署名鍵SKpgを用いて、代理グループ署名ρを生成する機能。  
(f33-2) 代理グループ署名ρを出力する機能。
【００３６】
代理グループ署名検証装置４０は、代理グループ署名検証部４１とを備えている。
【００３７】
代理グループ署名検証部４１は、次の機能(f41-1)〜(f41-3)からなる。  
(f41-1) 外部からの代理グループ署名検証要求に従い、平文mと代理グループ署名ρを受信する機能。なお、代理グループ署名検証部４１は、平文mと代理グループ署名ρとを代理グループ署名生成装置３０から受信してもよく、代理グループ署名生成装置３０から図示しない検証要求装置を介して受信してもよい。すなわち、代理グループ署名生成装置３０と代理グループ署名検証装置４０との間において、平文mとグループ署名ρの送受信の経路は、特に限定されない。  
(f41-2) 公開鍵公開装置５０から取得したグループ公開鍵PKgを用いて、代理グループ署名ρが平文mの代理グループ署名であることを検証する機能。なお、グループ公開鍵PKgは代理グループ署名検証要求を受けたときに公開鍵公開装置５０から取得してメモリ（図示せず）に記憶してもよく、予めグループ公開鍵PKgを取得して記憶しておいてもよい。
【００３８】
(f41-3) 検証結果(OK/NG)を出力する機能。
【００３９】
次に、以上のように構成されたグループ署名システムにおいて行われる処理について、具体的な方式を用いて説明する。
【００４０】
（準備）
本システムでは、鍵生成アルゴリズムGen_S、署名アルゴリズムSig、署名検証アルゴリズムVrfy からなる署名方式DS = (Gen_S, Sig, Vrfy)を用いる。署名方式DSは、例えば、RSA署名方式やElGamal署名方式などである。さらに、この署名方式DSは、選択平文攻撃に対して偽造不可能と仮定する。
【００４１】
また、本システムでは、鍵生成アルゴリズムGen_E、暗号化アルゴリズムEnc、復号アルゴリズムDecからなる公開鍵暗号方式AE = (Gen_E, Enc, Dec)を用いる。公開鍵暗号方式AEは、例えばRSA公開鍵暗号方式や、ElGamal暗号方式などである。さらに、公開鍵暗号方式AEは、選択暗号文攻撃に対して識別不可能(IND-CCA)な方式と仮定する。
【００４２】
さらに、ある任意長のビット列からなるドメイン上のNP-関係σ⊂{0,1}*×{0,1}*により決定されるNP言語をL = {x ∈ L | あるwが存在して(x, w)∈σを満たす}とし、このσに対する非対話零知識証明システムを(P, V)とする。ここで、{0,1}*は任意の長さのビット列の集合、×は集合の直積、⊂は部分集合を表す。
【００４３】
ここで、NP-関係σとは、次の条件(NP-i)(NP-ii)を満たす関係である。  
(NP-i) (x, w)が与えられた場合に(x, w)∈σか否かを入力xの長さの多項式時間で判定できる。
【００４４】
(NP-ii) xだけが与えられた場合には(x, w)∈σを満たすか否かを多項式時間で判定することが困難である。
【００４５】
また、σに対する非対話零知識証明システム(P, V)とは、次の条件(PV-i)(PV-ii)を満たす関係である。  
(PV-i) 入力(x, w)が与えられた場合にP(x, w, R) = αならば必ずV(x, α, R) = 1である。ここで、Rは、P, V共通の入力乱数である。  
(PV-ii) 言語Lに含まれない入力xだけが与えられた場合にはV(x, β ,R) = 1となるβを求めることが困難である。
【００４６】
ここで、任意のNP-関係σにより決定されるNP言語Lはグラフのハミルトン経路問題δにより決定される言語Hに多項式時間還元可能であることが広く知られている。この言語Hのように、任意のNP言語が多項式時間還元可能な言語はNP完全言語と呼ばれる。
【００４７】
ここでグラフのハミルトン経路問題δとは、グラフxが与えられたとき、グラフxにハミルトン経路(グラフ上の全ての点を通る経路)が含まれるか否かを判定する問題であり、グラフxとそのグラフに含まれるハミルトン経路wからなる組(x,w)の集合がδである。このδはNP-関係の性質(NP-i)及び(NP-ii)を満たす。
【００４８】
また、多項式時間還元可能とは、(x,w)∈σ ⇔ (f(x),g(w))∈δを満たす、入力xの長さの多項式時間で計算可能な関数f,gが構成可能という意味である。このような関数f,gの構成法は、例えば非特許文献３に記述されている。
【００４９】
一方、グラフのハミルトン経路問題δにより決定される言語Hに対する非対話零知識証明システム(P,V)の構成法は、例えば非特許文献４や非特許文献５に記述されている。
【００５０】
以上より、NP関係σにより決定されるNP言語Lに対する非対話零知識証明システム(P',V')は、前述の関数f,g及び言語Hに対する非対話零知識証明システム(P,V)を用いて  
P'(x,w,R)=P(f(x),g(w),R), V'(x,α,R)=V(f(x),α,R)  
と構成することができる。
【００５１】
本システムでは、σを後述の通り定義し、このσに対する非対話零知識証明システム(P,V)を前述の通り構成する。
【００５２】
（前提）
代理グループ署名生成装置３０の秘密情報記憶部３１には、予め署名方式DSの鍵生成アルゴリズムGen_sを用いて生成された代理公開鍵PKpと代理秘密鍵SKpが記憶されているものとする。また、代理公開鍵PKpは公開鍵公開装置５０に公開されているものとする。
【００５３】
（グループの初期化処理）
グループ管理装置１０は、外部からの要求により、グループg毎に、以下のように初期化処理を行う。
【００５４】
グループ初期化部１２は、署名方式DSの鍵生成アルゴリズムGen_S及び公開鍵暗号方式AEの鍵生成アルゴリズムGen_Eにより、２つの鍵ペア(PKs, SKs)、(PKe, SKe)をそれぞれ生成する。
【００５５】
また、グループ初期化部１２は、非対話零知識証明システム(P, V)の共通入力となる乱数Rを生成する。そして、グループ初期化部１２は、グループ公開鍵をPKg = (R, PKs, PKe)、グループ秘密鍵をSKg = (SKs, SKe)とし、グループ情報管理部１３へ送る。
【００５６】
公開鍵公開装置５０はグループ公開鍵PKgを公開する。
【００５７】
グループ情報管理部１３では、グループＩＤ＝g毎にグループ公開鍵PKg、グループ秘密鍵SKgをグループ情報記憶部１１に書き込む。
【００５８】
（グループメンバのグループ参加処理）
次に、グループ管理装置１０とグループメンバ装置２０の間で実行されるグループ参加処理について説明する。  
まず、グループメンバ装置２０は、外部からの要求により、グループメンバ(ID=u)の参加処理を開始する。
【００５９】
始めに、メンバ登録部２２は、署名方式DSの鍵生成アルゴリズムGen_Sにより、メンバ署名鍵SKu及びメンバ公開鍵PKuの鍵ペアを生成する。
【００６０】
次に、メンバ登録部２２は、メンバ公開鍵PKuに対応するメンバ署名鍵SKuを確かに所有していることを証明する零知識証明情報proof_uを生成する。例えば、ElGamal署名方式の場合、公開鍵y = g^x mod p に対する秘密鍵x mod q の(非対話)零知識証明情報proof_u = (c, s)は、次式のように計算できる。  
c = H(y‖g‖g^r) 
s = r - cx mod q 
ここで、pは素数、qはp-1を割り切る素数、gは位数qである素体GF(p)の原始元、Hは安全なハッシュ関数、^はべき乗計算、‖はデータの連結を表す。
【００６１】
そして、メンバ登録部２２は、グループ参加要求としてメンバID u 、メンバ公開鍵PKu及び零知識証明情報proof_uをグループ管理装置１０へ送信する。
【００６２】
グループ管理装置１０においては、メンバ証明書生成部１４が、この零知識証明情報proof_uの正当性を検証する。例えば、前述した零知識証明情報proof_u = (c, s)の場合、c = H(y‖g‖g^s * y^c mod p)が成り立つか否かを検証すればよい。ここで、*は掛算を表す。
【００６３】
なお、ここでは非対話の零知識証明を用いたが、これに限らず、対話的な零知識証明を用いてもよい。対話的な零知識証明を用いる場合、グループメンバ装置２０とグループ管理装置１０の間で情報を授受することにより、グループメンバ装置２０がメンバ公開鍵PKuに対応するメンバ署名鍵SKuを確かに所有していることを証明すればよい。
【００６４】
また、零知識証明情報proof_uの検証が成功した場合、メンバ証明書生成部１４は、グループ情報管理部１３から取得したグループ秘密鍵SKsを用いて、署名アルゴリズムSigによりメンバID uとメンバ公開鍵Pkuの連結<u, Pku>に対して署名Sig(SKs<u, PKu>)を生成する。メンバ証明書生成部１４は、この署名Sig(SKs<u, PKu>)をメンバ証明書cert_uとしてグループ情報管理部１３及びグループメンバ装置２０へ送信する。
【００６５】
グループ情報管理部１３は、メンバ証明書cert_uをグループ情報記憶部１１に書き込む。
【００６６】
一方、グループメンバ装置２０においては、メンバ登録部２２が、このメンバ証明書cert_uの正当性を、公開鍵公開装置５０から取得したグループ公開鍵のPKsを用いて検証する。
【００６７】
検証に成功した場合、メンバ登録部２２は、メンバ証明書cert_u、メンバ署名鍵SKu、メンバ公開鍵PKuをメンバ情報記憶部２１へ書き込む。
【００６８】
（グループ署名権限委託処理）
次に、グループメンバ装置２０と代理グループ署名生成装置３０の間で実行されるグループ署名生成権限委託処理について説明する。
【００６９】
グループメンバ装置２０においては、グループ署名生成権限委託部２３が、外部からの要求により、委託情報Dlg_uを以下により生成する。なお、委託情報Dlg_uは、代理グループ署名生成装置３０に対してグループ署名生成の権限を委託するための情報である。
【００７０】
グループ署名生成権限委託部２３は、メンバ情報記憶部２１からメンバID u、メンバ証明書cert_u、メンバ署名鍵SKu、メンバ公開鍵PKuを読み出す。
【００７１】
また、グループ署名生成権限委託部２３は、公開鍵公開装置５０から代理グループ署名生成装置３０の代理公開鍵PKpを取得する。ここで、代理公開鍵PKpは、予め公開鍵公開装置５０から取得して記憶しておいてもよく、権限委託処理実行毎に取得してもよい。
【００７２】
次に、グループ署名生成権限委託部２３は、外部からの要求に従い、委託するグループ署名生成権限の有効期限、使用制限などの情報が記述された委託書wを生成する。委託書wは、例えば有効期限、使用制限などの文字列が連結された情報などである。特に有効期限や使用制限を指定しない場合は、以降の処理で委託書wは無くても良い。
【００７３】
次に、グループ署名生成権限委託部２３は、代理公開鍵PKpと委託書wとを連結させて連結委託情報<PKp, w>を作成する。そして、グループ署名生成権限委託部２３は、メンバ署名鍵Skuを用いて、署名アルゴリズムSigにより、連結委託情報<PKp, w>に対する署名Sig(Sku <PKp, w>)を生成する。この署名Sig(Sku <PKp, w>)が委託証明書cert_pである。
【００７４】
最後に、グループ署名生成権限委託部２３は、委託情報をDlg_u = (u, PKu, cert_u, w, cert_p)として、代理グループ署名生成装置３０へ送信する。
【００７５】
代理グループ署名生成装置３０においては、グループ署名生成権限受託部３２が、この委託情報Dlg_u内のメンバ証明書cert_uの正当性をグループ公開鍵PKgのPKsを用いて、署名検証アルゴリズムVrfyにより検証する。ここで、グループ公開鍵PKgは予め公開鍵公開装置５０から取得して記憶しておいてもよく、権限委託処理実行毎に取得してもよい。
【００７６】
さらに、グループ署名生成権限委託部２３は、委託情報Dlg_u内の委託証明書cert_pの正当性を、委託情報Dlg_u内のメンバ公開鍵PKuを用いて、署名検証アルゴリズムVrfyにより検証する。
【００７７】
両者の検証に成功した場合、グループ署名生成権限委託部２３は、代理グループ署名鍵をSKpg = (u, PKu, cert_u, <PKp, w>, cert_p, SKp)として、秘密情報記憶部３１へ書き込む。
【００７８】
（代理グループ署名生成処理）
次に、代理グループ署名生成装置３０において実行される代理グループ署名生成処理について説明する。
【００７９】
代理グループ署名生成装置３０においては、外部から要求により、署名対象の平文mが代理グループ署名生成部３３に入力される。代理グループ署名生成部３３は、平文ｍに対し、以下の方法により代理グループ署名ρを生成する。
【００８０】
最初に、代理グループ署名生成部３３は、秘密情報記憶部３１から代理グループ署名鍵SKpgを取得する。続いて、代理グループ署名生成部３３は、この代理グループ署名鍵SKpg内の代理署名鍵SKpを用いて、署名アルゴリズムSigにより、メンバ公開鍵PKu及び平文mの連結<PKu, m>に対する署名sigp(SKp <PKu, m>)を生成する。
【００８１】
次に、代理グループ署名生成部３３は、公開鍵公開装置５０から取得したグループ公開鍵のPKeを用いて、暗号化アルゴリズムEncにより、暗号文C = Enc(PKe, <u, PKu, cert_u, cert_p, sigp>; r) を生成する。ここで、rは暗号化に用いる乱数である。
【００８２】
代理グループ署名生成部３３は、非対話零知識証明システムのPを用いて、α = P((PKe, PKs, PKp, w, m, C), (u, PKu, cert_u, cert_p, sigp, r), R) を計算する。しかる後、代理グループ署名生成部３３は、代理グループ署名ρ=(PKp, w, C, α) を出力する。ここで、非対話零知識証明システム(P, V)は、以下のNP-関係σ上で前述の通り構成する。
【００８３】
((PKe,PKs,PKp,w,m,C),(u,PKu,cert_u,cert_p,sigp,r))∈σ
⇔ Vrfy(PKs,<u,PKu>,cert_u)=1 かつ Vrfy(PKu,<PKp,w>,cert_p)=1 かつ
Vrfy(PKp,<PKu,m>,sigp)=1 かつ Enc(pk_e,<u,PKu,cert_u,cert_p,sigp>;r)=C。
【００８４】
（代理グループ署名検証処理）
次に、代理グループ署名検証装置４０で行われる代理グループ署名検証方法について説明する。
【００８５】
代理グループ署名検証装置においては、外部からの要求により、平文mとそれに対する代理グループ署名ρとが代理グループ署名検証部４１に入力される。
【００８６】
代理グループ署名検証部４１は、代理グループ署名ρが委託書wに記載された有効期限や署名対象平文に関する制限に従っているか否かを検証する。委託書wに従っていない場合、代理グループ署名検証部４１は、NGを出力する。
【００８７】
委託書wに従っている場合、代理グループ署名検証部４１は、公開鍵公開装置５０よりグループ公開鍵PKgを取得する。ここで、グループ公開鍵PKgは予め公開鍵公開装置５０から取得して記憶しておいてもよく、検証処理実行毎に取得してもよい。
【００８８】
次に、代理グループ署名検証部４１は、このグループ公開鍵PKgと、非対話零知識証明システムのVを用いて、以下の式が成り立つことを検証する。  
V((PKe, PKs, PKp, w, m, C), α, R) = 1。
【００８９】
そして、代理グループ署名検証部４１は、この検証結果(OK/NG)を出力する。
【００９０】
（グループメンバ特定処理）
最後に、グループ管理装置１０で行われるグループメンバの特定方法について説明する。
【００９１】
グループ管理装置１０においては、外部からの要求により、平文mとそれに対する代理グループ署名σがグループメンバ特定部１５に入力される。
【００９２】
グループメンバ特定部１５は、代理グループ署名検証装置４０内の代理グループ署名検証部４１と同様の動作により、代理グループ署名σの正当性を検証する。このとき、グループメンバ特定部１５は、グループ公開鍵PKgをグループ情報管理部１３から取得する。検証に失敗した場合、グループメンバ特定部１５は処理を終了する。
【００９３】
次に、グループメンバ特定部１５は、グループ情報管理部１３からグループ秘密鍵SKg内の特定用秘密鍵SKeを取得する。そして、グループメンバ特定部１５は、特定用秘密鍵SKeを用いて、復号アルゴリズムDecにより、代理グループ署名σ内の暗号文Cを復号する。
【００９４】
Dec(SKe, C) = <u, pk_u, cert_u, cert_p, sigp>
グループメンバ特定部１５は、復号結果に含まれるグループメンバID（＝ u）を出力する。
【００９５】
上述したように本実施形態によれば、グループメンバ装置２０がグループ署名の生成権限の委託情報Dlg_uを１回だけ代理グループ署名生成装置３０に送り、代理グループ署名生成装置３０が代理グループ署名ρを生成する構成により、グループ署名を生成する際に、メンバ側装置における計算量と、情報の授受回数とを低減させることができる。
【００９６】
補足すると、グループメンバ装置２０と代理グループ署名生成装置３０へグループ署名生成の権限を委託するための委託情報Dlg_uを１回送るだけで、代理グループ署名生成装置３０のみで代理グループ署名ρを生成することができる。すなわち、従来は装置２０、３０間で情報の授受を複数回行う必要があるが、本実施形態では片道１回の情報送信だけでグループ署名が生成でき、情報の授受回数を大幅に低減できる。
【００９７】
この場合、代理グループ署名生成装置３０が、グループメンバの意図しないメッセージに代理グループ署名ρを生成してしまう不正が考えられる。
【００９８】
しかしながら、本実施形態によれば、委託書wによる有効期限や平文等の制限を検証し、さらに、代理グループ署名を検証できるため、代理グループ署名装置３０による不正を防ぐことができる。
【００９９】
さらに、グループメンバ装置２０のグループ署名権限委託処理は、高々一般的な署名方式の署名生成処理１回だけであり、従来と比較して１０分の１以下の計算量に抑えることができる。このように、従来の１０分の１以下の計算量に抑制できる理由は、計算量の多い部分を代理グループ署名装置３０に委託したからである。現状では、携帯電話やスマートカードのように低い計算能力のデバイスでも、例えばRSA署名といった一般的な署名生成処理の計算が実用化されている。このため、本実施形態は、十分に実用的であると考えられる。
【０１００】
（第２の実施形態）
図５は本発明の第２の実施形態に係るグループメンバ認証システムの構成を示す模式図であり、図１と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した説明を省略する。
【０１０１】
すなわち、本実施形態は、第１の実施形態の変形例であり、第１の実施形態のグループ署名システムを適用したグループメンバ認証システムである。
【０１０２】
このグループメンバ認証システムは、グループメンバ装置２０を備えた認証要求装置２００と、代理グループ署名生成装置３０を備えた代理認証情報生成装置３００と、代理グループ署名検証装置４０を備えた認証装置４００とから構成されている。
【０１０３】
このグループメンバ認証システムにおいては、認証要求装置２００がメンバ署名鍵SKuを保持していることを、代理認証情報生成装置３００が認証装置４００に証明することにより、認証装置４００がグループメンバの認証を行う。
【０１０４】
ここで、認証要求装置２００は、グループメンバ装置２０及び認証要求部２０１を備えている。
【０１０５】
グループメンバ装置２０は、第１の実施形態におけるグループ参加処理を実行し、メンバ情報記憶部２１にメンバ証明書cert_u、メンバ秘密鍵SKu、メンバ公開鍵PKuが記憶されているものとする。
【０１０６】
認証要求部２０１は、次の機能(f201-1)〜(f201-5)をもっている。  
(f201-1) 認証装置４００へ認証要求を送信する機能。  
(f201-2) 認証装置４００から受信した認証チャレンジ情報cを受信する機能。  
(f201-3) この認証チャレンジ情報cのみを署名対象平文とする制限をつけて委託情報Dlg_uの生成要求をグループメンバ装置２０へ送る機能。  
(f201-4) グループメンバ装置２０から委託情報Dlg_uを受信する機能。  
(f201-5) 認証チャレンジ情報cと委託情報Dlg_uを代理認証情報生成装置３００へ送信する機能。
【０１０７】
代理認証情報生成装置３００は、代理グループ署名生成装置３０及び制御部３０１を備えている。
【０１０８】
制御部３０１は、次の機能(f301-1)〜(f301-4)をもっている。  
(f301-1) 認証要求装置２００から認証チャレンジ情報cと委託情報Dlg_uを受信する機能。  
(f301-2) 委託情報Dlg_uを代理グループ署名生成装置３０へ送る機能。  
(f301-3) 認証チャレンジ情報cに対する代理グループ署名の生成要求を代理グループ署名生成装置３０へ送る機能。  
(f301-4) 代理グループ署名生成装置３０が出力した代理グループ署名ρを認証装置４００へ送信する機能。
【０１０９】
認証装置４００は、代理グループ署名検証装置４０及び認証部４０１を備えている。
【０１１０】
認証部４０１は、次の機能(f401-1)〜(f401-4)をもっている。  
(f401-1) 認証要求装置２００からの認証要求に対して、乱数や時刻情報を含んだ認証チャレンジ情報cを生成する機能。  
(f401-2) 認証チャレンジ情報cを認証要求装置２００へ送信する機能。  
(f401-3) 代理認証情報生成装置３００から代理グループ署名ρを受信する機能。  
(f401-4) この代理グループ署名ρと、認証要求装置２００に送信した認証チャレンジ情報cとを代理グループ署名検証装置４０へ送る機能。  
(f401-5) 代理グループ署名検証装置４０から出力された代理グループ署名ρの正当性検証結果をグループメンバの認証結果として出力する機能。
【０１１１】
次に、以上のように構成されたグループメンバ認証システムにおいて実現される認証方法について説明する。
【０１１２】
始めに、認証要求装置２００においては、外部からの認証実行要求に従い、認証要求部２０１が認証装置４００へ認証要求を送信する。
【０１１３】
認証装置４００においては、この認証要求に対し、認証部４０１が、乱数や時刻情報を含んだ認証チャレンジ情報cを生成し、認証要求装置２００へ返信する。
【０１１４】
認証要求装置２００においては、認証要求部２０１がこの認証チャレンジ情報cと、この認証チャレンジ情報cのみを署名対象平文とする制限情報と、グループ署名生成権限委託情報の生成要求とをグループメンバ装置２０へ入力する。
【０１１５】
グループメンバ装置２０は、署名対象平文を認証チャレンジ情報cのみに制限することを委託書wに記述する。グループメンバ装置２０は、この委託書wを含む委託情報Dlg_uを生成し、この委託情報Dlg_uを認証要求部２０１に出力する。
【０１１６】
認証要求部２０１は、認証チャレンジ情報c及び委託情報Dlg_uを代理認証情報生成装置３００へ送信する。
【０１１７】
代理認証情報生成装置３００においては、制御部３０１がこの委託情報Dlg_uを代理グループ署名生成装置３０へ入力する。
【０１１８】
代理グループ署名生成装置３０は、前述した通り、代理グループ署名鍵SKpgを生成し、秘密情報記憶部３１へ書き込む。
【０１１９】
次に、制御部３０１は、受信した認証チャレンジ情報cと、代理グループ署名生成要求とを代理グループ署名生成装置３０へ入力する。
【０１２０】
代理グループ署名生成装置３０は、前述同様に、代理グループ署名ρを生成して制御部３０１に出力する。但し、代理グループ署名ρの生成過程において、前述した平文ｍに代えて、認証チャレンジ情報ｃが用いられる。
【０１２１】
制御部３０１は、この代理グループ署名ρを認証装置４００へ送信する。
【０１２２】
認証装置４００においては、この代理グループ署名ρの正当性の検証要求を認証部４０１が代理グループ署名検証装置４０へ入力する。
【０１２３】
代理グループ署名検証装置４０は、前述した通り、代理グループ署名の正当性を検証し、検証結果（ＯＫ／ＮＧ）を認証部４０１に出力する。
【０１２４】
認証部４０１は、この出力結果がＯＫならば認証成功（ＯＫ）を出力し、出力結果がＮＧならば認証失敗（ＮＧ）を出力する。
【０１２５】
上述したように本実施形態によれば、第１の実施形態で述べたグループ署名システムの性質により、低い計算能力の携帯電話やスマートカードなどの装置でも、メンバを特定されずにグループメンバであることを認証装置４００に証明することができる。
【０１２６】
（第３の実施形態）
図６は本発明の第３の実施形態に係るグループ署名生成システムの構成を示す模式図である。本実施形態は、第１の実施形態の変形例であり、メンバ署名鍵SKuのリボケーション（revocation: 失効）処理を実現する形態となっている。
【０１２７】
グループ署名システムにおけるメンバ署名鍵SKuのリボケーション(失効)は、有効期限管理や不正者排除などを実現するために実用上必須な機能である。
【０１２８】
しかしながら、メンバ署名鍵SKuのリボケーションは、過去の代理グループ署名ρの匿名性を維持する等の条件があるため、実現が困難である。例えば、従来提案されたリボケーション方式は、署名生成処理及び署名検証処理が煩雑かつ非実用的であるという欠点や、匿名性が損なわれるという欠点がある。このように、メンバ署名鍵SKuの有効なリボケーション方法は知られていない。
【０１２９】
本実施形態では、第１の実施形態に加え、代理グループ署名生成装置３０において、権限委託された際にメンバ署名鍵SKuのリボケーションを行うことにより、従来のPKIにおけるリボケーションと同程度の処理でメンバ署名鍵SKuのリボケーションを実行する方法を述べる。
【０１３０】
具体的には、グループ管理装置１０は、前述した機能に加え、メンバ証明書失効情報生成部１６を備えている。
【０１３１】
また、代理グループ署名生成装置３０は、前述した機能に加え、メンバ証明書失効情報取得部３４及びメンバ証明書検証部３５を備えている。
【０１３２】
これに伴い、グループ署名生成権限受託部３２は、前述した機能(f32-1)〜(f32-2)に加え、次の機能(f32-3)〜(f32-4)をもっている。
【０１３３】
(f32-3) メンバ証明書cert_uの検証依頼をメンバ証明書検証部３５に送出する機能。
【０１３４】
(f32-4) 検証結果がＯＫ（有効）のとき、前述した代理グループ署名SKpgを秘密情報記憶部３１に書き込む機能。
【０１３５】
ここで、メンバ証明書失効情報生成部１６は、次の機能(f16-1)〜(f16-3)をもっている。  
(f16-1) 外部からの要求により、失効する全てのメンバ証明書cert_uからなるリストCertListに対し、グループ秘密鍵SKgにおける秘密鍵SKsに基づいて署名Sig(SKs <CertList>)を生成する機能。ここで、失効するメンバ証明書cert_uに代えて、cert_uを特定可能な情報、例えばcert_uにIDが付与されている場合はそれらIDからなるリストをCertListとしても良い。
【０１３６】
(f16-2) このリストCertListと署名Sig(SKs < CertList>)からなるメンバ証明書失効リストcrlを生成する機能する機能。  
(f16-3) このメンバ証明書失効リストcrlを代理グループ署名生成装置３０のみに開示する機能。
【０１３７】
一方、メンバ証明書失効情報取得部３４は、次の機能(f34-1)〜(f34-3)をもっている。  
(f34-1) メンバ証明書検証部３５から要求されたとき又は定期的に、グループ管理装置１０からメンバ証明書失効リストcrlを安全な通信路を介して取得する機能。  
(f34-2) 取得したメンバ証明書失効リストcrlの署名Sig(SKs <CertList>)の正当性を、公開鍵公開装置５０から取得したグループ公開鍵PKgのPKsを用いて検証する機能。  
(f34-3) この検証結果(OK/NG)をグループ署名生成権限受託部３２に送出する機能。  
メンバ証明書検証部３５は、次の機能(f35-1)〜(f35-3)をもっている。  
(f35-1) グループ署名生成権限受託部３２からのメンバ証明書cert_uの検証依頼に対し、メンバ証明書失効情報取得部３４により取得されたメンバ証明書失効リストcrlに、当該メンバ証明書cert_uが含まれるか否かを検証する機能。  
(f35-2) 検証の結果、含まれていればNG（失効）をグループ署名生成権限受託部３２に返す機能。  
(f35-3) 検証の結果、含まれていなければOK（有効）をグループ署名生成権限受託部３２に返す機能。  
次に、以上のように構成されたグループ署名システムにおいて実現されるグループ署名生成時のメンバ署名鍵SKuのリボケーション処理について図７の模式図を用いて説明する。
【０１３８】
始めに、グループの初期化処理及びグループメンバのグループ参加処理については、第１の実施形態と同様に実行される。
【０１３９】
次に、グループ管理装置１０においては、メンバ証明書失効情報生成部１６が、外部からの要求により、失効する全てのメンバ証明書cert_uからなるリストCertListに対して、グループ秘密鍵SKgの秘密鍵SKsによって署名Sig(SKs < CertList>)を生成する。また、メンバ証明書失効情報生成部１６は、このリストCertListと署名Sig(SKs <CertList>)とからなるメンバ証明書失効リストcrlを生成する。
【０１４０】
しかる後、メンバ証明書失効情報生成部１６は、このメンバ証明書失効リストcrlを代理グループ署名生成装置３０のみに開示する。ここで、メンバ証明書失効リストcrlに代えて、メンバ公開鍵失効リストを用いても同様の効果が得られる。なお、メンバ公開鍵失効リストは、失効するメンバ公開鍵PKuを特定可能な情報のリストPubkeyList及び署名Sig(SKs <PubkeyList>)からなるものとする。
【０１４１】
次に、グループ署名権限委託処理においては、グループメンバ装置２０は、前述同様に、グループ署名生成権限の委託情報Dlg_uを生成する。そして、グループメンバ装置２０は、この委託情報Dlg_uを代理グループ署名生成装置３０へ送信する。
【０１４２】
代理グループ署名生成装置３０においては、グループ署名生成権限受託部３２が、受信した委託情報Dlg_uに対し、第１の実施形態に述べた検証処理を行う前に、委託情報Dlg_u内のメンバ証明書cert_uの検証依頼をメンバ証明書検証部３５へ送る。この検証依頼は、メンバ証明書cert_uが失効しているか否かの検証を依頼するものである。
【０１４３】
メンバ証明書検証部３５は、この検証依頼に基づいて、メンバ証明書失効情報取得部３４にメンバ証明書失効リストcrlを要求する。
【０１４４】
メンバ証明書失効情報取得部３４は、メンバ証明書検証部３５から要求されたとき又は定期的に、グループ管理装置１０からメンバ証明書失効リストcrlを安全な通信路を介して取得する。
【０１４５】
メンバ証明書失効情報取得部３４は、このメンバ証明書失効リストcrlの署名Sig(SKs <CertList>)の正当性を、公開鍵公開装置５０から取得したグループ公開鍵PKsを用いて検証する。検証の結果、正当性があれば、メンバ証明書失効情報取得部３４は、このメンバ証明書失効リストcrlをメンバ証明書検証部３５に送出する。
【０１４６】
メンバ証明書検証部３５は、メンバ証明書cert_uがメンバ証明書失効リストcrlに含まれるか否かを検証する。メンバ証明書検証部３５は、この検証の結果、含まれていればNGを、含まれていなければOKをグループ署名生成権限受託部３２に出力する。
【０１４７】
グループ署名生成権限受託部３２は、メンバ証明書検証部３５の出力がNGならば、第１の実施形態に述べた検証処理を実行せず、NGを出力して処理を終了する。
【０１４８】
メンバ証明書検証部３５の出力がOKならば、以降の全ての処理は第１の実施形態と同様に実行される。
【０１４９】
上述したように本実施形態によれば、第１の実施形態の作用効果に加え、グループ署名を生成する前にメンバ署名鍵のリボケーションを確実に実行できる。
【０１５０】
これに加え、本実施形態は、代理グループ署名生成装置３０におけるメンバ署名鍵のリボケーションの処理が、従来のPKIにおけるリボケーションと同程度の処理であることから、容易に実用化することができる。
【０１５１】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１５２】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１５３】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１５４】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【０１５５】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１５６】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１５７】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１５８】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１５９】
【図１】本発明の第１の実施形態に係るグループ署名システムの構成を示す模式図である。
【図２】同実施形態におけるグループ情報記憶部の構成を示す模式図である。
【図３】同実施形態におけるメンバ情報記憶部の構成を示す模式図である。
【図４】同実施形態における秘密情報記憶部の構成を示す模式図である。
【図５】本発明の第２の実施形態に係るグループ署名システムの構成を示す模式図である。
【図６】本発明の第３の実施形態に係るグループ署名システムの構成を示す模式図である。
【図７】同実施形態におけるメンバ認証方法を説明するための模式図である。
【符号の説明】
【０１６０】
１０…グループ管理装置、１１…グループ情報記憶部、１２…グループ初期化部、１３…グループ情報管理部、１４…メンバ証明書生成部、１５…グループメンバ特定部、１６…メンバ証明書失効情報生成部、２０…グループメンバ装置、２１…メンバ情報記憶部、２２…メンバ登録部、２３…グループ署名生成権限委託部、３０…代理グループ署名生成装置、３１…秘密情報記憶部、３２…グループ署名生成権限受託部、３３…代理グループ署名生成部、３４…メンバ証明書失効情報取得部、３５…メンバ証明書検証部、４０…代理グループ署名検証装置、４１…代理グループ署名検証部、５０…公開鍵公開装置、２００…認証要求装置、２０１…認証要求部、３００…代理認証情報生成装置、３０１…制御部、４００…認証装置、４０１…認証部。
【図１】
0004791828.tif 000002
【図２】
0004791828.tif 000003
【図３】
0004791828.tif 000004
【図４】
0004791828.tif 000005
【図５】
0004791828.tif 000006
【図６】
0004791828.tif 000007
【図７】
0004791828.tif 000008