(57)【要約】【課題】メンバ署名鍵を簡単にリボークできるようにする。【解決手段】ＧＭ端末１１内のグループ情報生成部１１１は、グループに所属する複数のユーザにそれぞれ固有のメンバ署名鍵のうちの特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ公開鍵ｐｋを含むグループ公開情報ＧＰＵＢＩを生成すると共に、復号関数ｄｅｃを含む、秘密に保持すべきグループ秘密情報ＧＰＲＶＩを生成する。ＧＭ端末１１内のメンバ署名鍵生成部１１２は、上記秘密情報をもとに、上記グループに所属するユーザに配布される当該ユーザに固有のメンバ署名鍵を生成する。ＧＭ端末１１内のメンバ署名鍵リボーク部１１４は、上記公開情報を更新することにより、複数のユーザに配布されたメンバ署名鍵のうち一部のメンバ署名鍵を無効化する。【選択図】      図４
2005210638.tif 000002
【特許請求の範囲】
【請求項１】
デジタル署名を管理するデジタル署名管理装置と、
前記デジタル署名管理装置によって生成される、グループに所属するユーザに固有のメンバ署名鍵及び前記グループに所属する複数のユーザに共通の公開情報を用いて、任意のデジタル情報に対するデジタル署名を生成する複数のデジタル署名装置と、
前記デジタル署名装置によって生成されたデジタル署名を検証する署名検証装置とを具備し、
前記デジタル署名管理装置は、
前記グループに所属する前記複数のユーザにそれぞれ固有のメンバ署名鍵のうちの特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ公開鍵を含む公開情報を、前記グループに所属する前記複数のユーザに共通の前記公開情報として生成すると共に、前記デジタル署名の生成に関与したユーザを特定するのに必要な復号関数を含む、秘密に保持すべき秘密情報を生成する情報生成手段と、
前記秘密情報をもとに、前記グループに所属するユーザに配布される当該ユーザに固有のメンバ署名鍵を生成するメンバ署名鍵生成手段と、
前記デジタル署名の生成に関与したユーザを当該デジタル署名及び前記秘密情報をもとに特定する署名開示手段と、
前記公開情報を更新することにより、前記複数のユーザにそれぞれ配布されたメンバ署名鍵のうち一部のメンバ署名鍵を無効化するメンバ署名鍵リボーク手段とを備え、
前記署名検証装置は、前記デジタル署名の正当性を、当該デジタル署名及び前記公開情報を用いて検証する署名検証手段を備えている
ことを特徴とするデジタル署名システム。
【請求項２】
前記メンバ署名鍵リボーク手段は、前記一部のメンバ署名鍵が前記特定のメンバ署名鍵集合から排除されるように、前記公開情報に含まれている前記公開鍵を更新する公開鍵更新手段を含むことを特徴とする請求項１記載のデジタル署名システム。
【請求項３】
前記秘密情報は乱数を含み、
前記メンバ署名鍵リボーク手段は、前記秘密情報に含まれている前記乱数を更新する乱数更新手段を更に含むことを特徴とする請求項２記載のデジタル署名システム。
【請求項４】
前記デジタル署名装置は、前記デジタル署名として、前記メンバ署名鍵について零知識であることが証明可能なデジタル署名を生成することを特徴とする請求項１記載のデジタル署名システム。
【請求項５】
デジタル署名を管理するデジタル署名管理装置において、
グループに所属する複数のユーザに共通の公開情報であって、前記複数のユーザにそれぞれ固有のメンバ署名鍵のうちの特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ公開鍵を含む公開情報と、前記デジタル署名の生成に関与したユーザを特定するのに必要な復号関数を含む、秘密に保持すべき秘密情報とを生成する情報生成手段と、
前記秘密情報をもとに、前記グループに所属するユーザに配布される当該ユーザに固有のメンバ署名鍵を生成するメンバ署名鍵生成手段と、
前記メンバ署名鍵及び前記公開情報を用いてデジタル署名装置によって生成された、任意のデジタル情報に対するデジタル署名を受けて、当該デジタル署名の生成に関与したユーザを当該デジタル署名及び前記秘密情報をもとに特定する署名開示手段と、
前記公開情報を更新することにより、前記複数のユーザにそれぞれ配布されたメンバ署名鍵のうち一部のメンバ署名鍵を無効化するメンバ署名鍵リボーク手段と
を具備することを特徴とするデジタル署名管理装置。
【請求項６】
デジタル署名を管理するデジタル署名管理装置と、任意のデジタル情報に対するデジタル署名を生成する複数のデジタル署名装置と、前記デジタル署名装置によって生成されたデジタル署名を検証する署名検証装置とを備えたデジタル署名システムに適用されるデジタル署名管理方法において、
前記デジタル署名管理装置が、グループに所属する複数のユーザにそれぞれ固有のメンバ署名鍵のうちの特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ公開鍵を含む公開情報を、前記グループに所属する前記複数のユーザに共通の前記公開情報として生成すると共に、前記デジタル署名の生成に関与したユーザを特定するのに必要な復号関数を含む、秘密に保持すべき秘密情報を生成するステップと、
前記秘密情報を第３者から秘匿された状態で前記デジタル署名管理装置の秘密情報記憶装置に記憶するステップと、
前記秘密情報記憶装置に記憶されている前記秘密情報をもとに、前記グループに所属するユーザに配布される当該ユーザに固有のメンバ署名鍵を前記デジタル署名管理装置が生成するステップと、
前記デジタル署名装置が前記メンバ署名鍵及び前記公開情報を用いて任意のデジタル情報に対するデジタル署名を生成するデジタル署名生成ステップと、
前記デジタル署名生成ステップで生成されたデジタル署名を受けて、前記署名検証装置が、当該デジタル署名の正当性を、当該デジタル署名及び前記公開情報を用いて検証するステップと、
前記デジタル署名生成ステップで生成されたデジタル署名を受けて、前記デジタル署名管理装置が、当該デジタル署名の生成に関与したユーザを当該デジタル署名及び前記秘密情報をもとに特定するステップと、
前記公開情報を更新することにより、前記複数のユーザにそれぞれ配布されたメンバ署名鍵のうち一部のメンバ署名鍵を無効化するステップと
を具備することを特徴とするデジタル署名管理方法。
【請求項７】
デジタル署名を管理するデジタル署名管理装置に適用されるデジタル署名管理方法において、
グループに所属する複数のユーザに共通の公開情報であって、前記複数のユーザにそれぞれ固有のメンバ署名鍵のうちの特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ公開鍵を含む公開情報と、前記デジタル署名の生成に関与したユーザを特定するのに必要な復号関数を含む、秘密に保持すべき秘密情報とを生成するステップと、
前記秘密情報を第３者から秘匿された状態で秘密情報記憶装置に記憶するステップと、
前記秘密情報記憶装置に記憶されている前記秘密情報をもとに、前記グループに所属するユーザに配布される当該ユーザに固有のメンバ署名鍵を生成するステップと、
前記メンバ署名鍵及び前記公開情報を用いてデジタル署名装置によって生成された、任意のデジタル情報に対するデジタル署名を受けて、当該デジタル署名の生成に関与したユーザを当該デジタル署名及び前記秘密情報記憶装置に記憶されている前記秘密情報をもとに特定するステップと、
前記公開情報を更新することにより、前記複数のユーザにそれぞれ配布されたメンバ署名鍵のうち一部のメンバ署名鍵を無効化するメンバ署名鍵リボークステップと
を具備することを特徴とするデジタル署名管理方法。
【請求項８】
デジタル署名を管理するデジタル署名管理装置に、
グループに所属する複数のユーザに共通の公開情報であって、前記複数のユーザにそれぞれ固有のメンバ署名鍵のうちの特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ公開鍵を含む公開情報と、前記デジタル署名の生成に関与したユーザを特定するのに必要な復号関数を含む、秘密に保持すべき秘密情報とを生成する情報生成ステップと、
前記秘密情報を第３者から秘匿された状態で秘密情報記憶装置に記憶するステップと、
前記秘密情報記憶装置に記憶されている前記秘密情報をもとに、前記グループに所属するユーザに配布される当該ユーザに固有のメンバ署名鍵を生成するメンバ署名鍵生成ステップと、
前記メンバ署名鍵及び前記公開情報を用いてデジタル署名装置によって生成された、任意のデジタル情報に対するデジタル署名を受けて、当該デジタル署名の生成に関与したユーザを当該デジタル署名及び前記秘密情報記憶装置に記憶されている前記秘密情報をもとに特定する署名開示ステップと、
前記公開情報を更新することにより、前記複数のユーザにそれぞれ配布されたメンバ署名鍵のうち一部のメンバ署名鍵を無効化するメンバ署名鍵リボークステップと
を実行させるためのプログラム。
【請求項９】
前記メンバ署名鍵リボークステップは、前記一部のメンバ署名鍵が前記特定のメンバ署名鍵集合から排除されるように、前記公開情報に含まれている前記公開鍵を更新する公開鍵更新ステップを含むことを特徴とする請求項８記載のプログラム。
【請求項１０】
前記秘密情報は乱数を更に含み、
前記メンバ署名鍵リボークステップは、前記秘密情報に含まれている前記乱数を更新する乱数更新ステップを更に含むことを特徴とする請求項９記載のプログラム。
【請求項１１】
前記公開鍵は、前記特定のメンバ署名鍵集合から外れたメンバ署名鍵の識別子の集合を含み、
前記公開鍵更新ステップでは、前記公開鍵に含まれているメンバ署名鍵の識別子の一部が、無効化すべき前記一部のメンバ署名鍵の識別子で置き換えられる
ことを特徴とする請求項９または請求項１０記載のプログラム。
【請求項１２】
前記デジタル署名装置に実行させるためのステップであって、前記メンバ署名鍵生成ステップで生成された前記メンバ署名鍵が配布されたユーザのユーザ識別子と当該メンバ署名鍵の識別子とのペアを前記秘密情報記憶装置に記憶するステップを更に具備し、
前記署名開示ステップは、
前記デジタル署名の生成に用いられたメンバ署名鍵の識別子を当該デジタル署名及び前記秘密情報記憶装置に記憶されている前記秘密情報をもとに特定するメンバ署名鍵識別子特定ステップと、
前記メンバ署名鍵識別子特定ステップで特定されたメンバ署名鍵識別子とペアをなして前記秘密情報記憶装置に記憶されているユーザ識別子を検索することにより、前記デジタル署名の生成に用いられたメンバ署名鍵が配布されたユーザを特定するステップと
を含むことを特徴とする請求項８記載のプログラム。
【請求項１３】
前記デジタル署名装置によって生成された前記デジタル署名が、前記メンバ署名鍵について零知識であることが証明可能なデジタル署名であることを特徴とする請求項８記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル署名方式を適用するデジタル署名システムに係り、特に、グループ署名方式と呼ばれるデジタル署名方式を適用するデジタル署名システム、デジタル署名管理装置、デジタル署名管理方法及びプログラムに関する。
【背景技術】
【０００２】
デジタル署名方式として、従来からグループ署名方式が知られている（例えば、非特許文献１参照）。この非特許文献１に記載されたグループ署名方式とは、以下の第１乃至第３の性質を持つデジタル署名方式である。第１は、あるグループに所属する任意のメンバがグループの代表として署名を生成することが可能であるという性質である。第２は、検証者はグループのメンバにより生成された署名であることは検証可能であるが、署名者を特定することは困難であるという性質である。第３は、特定の情報により、グループ署名から署名を生成したメンバを特定することが可能な性質である。
【０００３】
グループ署名方式では、署名鍵のリボーク(無効化)が要求される。署名鍵のリボークは、有効期限管理や不正者排除などを実現するために実用上必須な機能である。そこで署名鍵のリボークに関し、従来から幾つかの方式が提案されている（例えば、特許文献２及び３参照）。特許文献２に記載された方式は、ＣＲＬ（Certificate Revocation List）によるリボークを実現している。特許文献３に記載された方式は、公開掲示板にグループ参加／リボークリストを掲示し、それらのリストからダイナミック・アキムレータ（dynamic accumulator）を用いてグループ公開鍵を更新することによりリボークを実現している。
【非特許文献１】Ｄ．チャウム、Ｅ．ファン・ホイスト（D.Chaum, E.van Heyst）著、「グループ・シグネチャ（Group signatures）」、ユーロクリプト'９１（EUROCRYPT'91）、ＬＮＣＳ ５４７、シュプリンガー・フェアラーク（Springer-Verlag）、ｐｐ.２５７−２６５、１９９１年
【非特許文献２】Ｇ．アテニーズ、Ｄ．ソング、Ｇ．ツジク（G.Ateniese, D.Song, G.Tsudik）著、「クワァジ・エフィシェント・リボケーション・イン・グループ・シグネチャ（Quasi-efficient revocation in group signatures）」、フィナンシャル・クリプトグラフィ２００２（Financial Cryptography 2002）、ＬＮＣＳ ２３５７、シュプリンガー・フェアラーク（Springer-Verlag）、２００２年
【非特許文献３】Ｊ．カメニッシ、Ａ．リジアンスカヤ（J.Camenisch, A.Lysyanskaya）著、「ダイナミック・アキムレータ・アンド・アプリケーション・トゥ・エフィシェント・リボケーション・オブ・アノニマス・クリデンシャル（Dynamic accumulators and application to efficient revocation of anonymous credentials）」、クリプト（Crypto）２００２、ＬＮＣＳ ２４４２、シュプリンガー・フェアラーク（Springer-Verlag）、ｐｐ.６１−７６、２００２年
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上記非特許文献２に記載されたリボーク方式は、署名サイズ及び署名生成の計算量がリボーク数によらず一定というメリットがある。しかし、この方式は、署名生成にダブル・ディスクリート・ログ（double discrete-log）を計算しなければならないため、実計算量は非常に大きく実用的とはいえない。一方、上記特許文献３に記載されたリボーク方式では、リボーク時だけではなく，グループにユーザが参加する毎にグループ公開鍵を更新しなければならない。また、署名生成時に、リストを参照して署名鍵を更新しなければならない。このため特許文献３に記載されたリボーク方式は、署名生成に最悪グループメンバ数に比例した計算量が必要となる。つまり従来のリボーク方式は、リボーク効率の点で問題がある。
【０００５】
本発明は上記事情を考慮してなされたものでその目的は、メンバ署名鍵を簡単にリボークできるデジタル署名システム、デジタル署名管理装置、デジタル署名管理方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
本発明の１つの観点によれば、デジタル署名を管理するデジタル署名管理装置と、このデジタル署名管理装置によって生成される、グループに所属するユーザに固有のメンバ署名鍵及び上記グループに所属する複数のユーザに共通の公開情報を用いて、任意のデジタル情報に対するデジタル署名を生成する複数のデジタル署名装置と、このデジタル署名装置によって生成されたデジタル署名を検証する署名検証装置とを備えたデジタル署名システムが提供される。上記デジタル署名管理装置は、上記グループに所属する上記複数のユーザにそれぞれ固有のメンバ署名鍵のうちの特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ公開鍵を含む公開情報を、上記グループに所属する上記複数のユーザに共通の上記公開情報として生成すると共に、上記デジタル署名の生成に関与したユーザを特定するのに必要な復号関数を含む、秘密に保持すべき秘密情報を生成する情報生成手段と、上記秘密情報をもとに、上記グループに所属するユーザに配布される当該ユーザに固有のメンバ署名鍵を生成するメンバ署名鍵生成手段と、上記デジタル署名の生成に関与したユーザを当該デジタル署名及び上記秘密情報をもとに特定する署名開示手段と、上記公開情報を更新することにより、上記複数のユーザにそれぞれ配布されたメンバ署名鍵のうち一部のメンバ署名鍵を無効化するメンバ署名鍵リボーク手段とを備える。上記署名検証装置は、上記デジタル署名の正当性（つまりデジタル署名が上記グループに所属するユーザのいずれかの関与により生成されたこと）を、当該デジタル署名及び上記公開情報を用いて検証する署名検証手段とを備える。
【０００７】
上記の構成において、デジタル署名装置によって任意のデジタル情報に対するデジタル署名を生成するのに用いられる公開情報は、グループに所属する複数のユーザにそれぞれ固有のメンバ署名鍵のうちの特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ公開鍵を含む。この公開鍵は、放送型暗号方式における暗号文に相当する情報であり、メンバ署名鍵は当該暗号文を復号するための、放送型暗号方式における復号鍵に相当する情報である。したがって、この公開鍵を含む公開情報（好ましくは公開鍵）を更新するだけで、複数のユーザにそれぞれ配布されたメンバ署名鍵のうち一部のメンバ署名鍵を簡単に無効化することができる。特に、公開鍵が、上記特定のメンバ署名鍵集合から外れたメンバ署名鍵の識別子の集合を含む構成とすると共に、一部のメンバ署名鍵を無効化（リボーク）する必要がある場合、上記公開鍵に含まれているメンバ署名鍵の識別子の一部が、無効化すべき上記一部のメンバ署名鍵の識別子で置き換えられる構成とするならば、メンバ署名鍵の無効化を一層効率的に行うことができる。
【０００８】
また、上記秘密情報が乱数を含む構成とすると共に、上記一部のメンバ署名鍵を無効化するために、上記公開情報に含まれている公開鍵を更新する際には、上記秘密情報に含まれている上記乱数も更新する構成とすると良い。このようにすると、メンバ署名鍵を無効化する前に生成されたデジタル署名の匿名性及び非結合性が損なわれずに済む。非結合性とは、複数のデジタル署名が，同じメンバ署名鍵で生成されたものかどうか、上記秘密情報を知り得ない署名検証装置からは特定困難な性質である。
【０００９】
また、上記デジタル署名装置が、上記デジタル署名として、上記メンバ署名鍵について零知識であることが証明可能なデジタル署名を生成する構成とするならば、上記匿名性及び非結合性の安全性を数学的に困難な問題に帰着させること、つまり匿名性及び非結合性の安全性を証明することが可能となる。
【発明の効果】
【００１０】
本発明によれば、公開鍵を含む公開情報を更新するだけで、複数のユーザに配布されたメンバ署名鍵のうち一部のメンバ署名鍵を簡単に無効化することができる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明の一実施形態につき図面を参照して説明する。  
図１は本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図である。図１のシステムは、グループマネージャ（グループ管理者）端末（以下、ＧＭ端末と称する）１１、複数のユーザ端末１２及びユーザ端末１３を備えている。複数のユーザ端末１２は、ユーザｕのユーザ端末１２とユーザｋのユーザ端末１２とを含む。ユーザｕ及びｋはグループ１４に所属する。ユーザ端末は、グループ１４に所属するユーザのユーザ端末１２と、グループ１４に所属しないユーザのユーザ端末１３とに分類される。ここでは、ユーザ端末１３のユーザはユーザｖである。
【００１２】
ユーザ端末１２は、当該端末１２のユーザがグループ１４に所属する際、ＧＭ端末１１から安全な通信路１５を介してメンバ署名鍵を受け取る。安全な通信路１５とは、例えばネットワーク上で従来から知られている認証及び秘匿手段によって保護された方法により実現される通信路である。また、安全な通信路１５が、グループマネージャ（以下、ＧＭと称する）からユーザ端末１２のユーザにメンバ署名鍵を直接接手渡しする方法により実現される通信路であっても構わない。この場合、ユーザがユーザ端末１２を用いてメンバ署名鍵を入力する操作を行うことで、ユーザ端末１２は、当該メンバ署名鍵を受け取ることができる。
【００１３】
また、図１のシステムは、ＧＭ端末１１が生成した情報を安全に公開するための手段、例えば公開情報掲示板サーバ１６を備えている。公開情報掲示板サーバ１６は、公開される情報を記憶する公開情報記憶装置１６１を有する。この公開情報掲示板サーバ１６によって実現される情報公開（掲載）手段を公開情報掲示板と呼ぶ。公開情報掲示板は、一種の電子掲示板であり、ユーザ端末１２及び１３を含む全てのユーザ端末からアクセスでき、かつ改竄などの不正が行われないよう適切に管理されている。また、ユーザ端末１２及び１３を含む全てのユーザ端末は、ネットワーク１７に接続されている。ネットワーク１７は、例えばインターネットである。しかし、ネットワーク１７が必ずしもインターネットである必要はない。例えば、ネットワーク１７に接続されるユーザ端末のユーザの匿名性を必要とする場合には、ネットワーク１７が匿名ネットワークであっても良い。
【００１４】
ＧＭ端末１１は、ＧＭ（グループマネージャ）がグループ署名（デジタル署名）を管理するのに用いられるグループ署名（デジタル署名）管理装置である。ＧＭ端末１１は、グループ情報生成部１１１、メンバ署名鍵生成部１１２、署名開示部１１３及びメンバ署名鍵リボーク部１１４の各処理部を備えている。
【００１５】
グループ情報生成部１１１は、グループ公開情報ＧＰＵＢＩ及びグループ秘密情報ＧＰＲＶＩを生成する。グループ公開情報ＧＰＵＢＩは、グループ１４に所属する複数のユーザ（メンバ）に共通の公開情報である。グループ公開情報ＧＰＵＢＩは、グループ公開鍵ｐｋを含む。グループ公開鍵ｐｋは、グループ１４に所属する複数のユーザに配布されるメンバ署名鍵のうち、特定のメンバ署名鍵集合に含まれるメンバ署名鍵によってのみ復号可能となる性質を持つ一種の暗号文である。つまり、本実施形態で適用されるグループ公開鍵ｐｋは、放送型暗号方式においてユーザに配信される暗号文に相当する情報である。また、本実施形態で適用されるメンバ署名鍵は、放送型暗号方式においてユーザに配信される暗号文の復号に用いられる復号鍵に相当する、ユーザに固有の情報である。放送型暗号方式において、ユーザに配信される暗号文を復号可能な復号鍵の集合は、暗号化毎に動的に変えることができる。ここでは、復号鍵自体を変更する必要はない。このことは、本実施形態で適用されるメンバ署名鍵についても同様である。
【００１６】
メンバ署名鍵生成部１１２は、グループ秘密情報ＧＰＲＶＩをもとに、グループ１４に所属するユーザが署名を生成するためのメンバ署名鍵を生成する。メンバ署名鍵生成部１１２は、生成されたメンバ署名鍵を該当するユーザのユーザ端末１２に秘密に送信するメンバ署名鍵秘密送信機能を有している。ＧＭ端末１１において、このメンバ署名鍵秘密送信機能を有する手段を、メンバ署名鍵生成部１１２から独立に備える構成とすることも可能である。
【００１７】
署名開示部１１３は、メッセージｍに対する署名（グループ署名）σがいずれのユーザにより生成されたかを、グループ秘密情報ＧＰＲＶＩをもとに特定する。メンバ署名鍵リボーク部１１４は、グループ公開情報ＧＰＵＢＩを更新（具体的には、グループ公開情報ＧＰＵＢＩに含まれているグループ公開鍵ｐｋを更新）することにより、一部のメンバ署名鍵をリボーク（無効化）する。メンバ署名鍵をリボークするとは、当該メンバ署名鍵によるグループ署名σの生成を不可能とすることである。
【００１８】
ＧＭ端末１１はまた、当該ＧＭ端末１１が生成した秘密情報を記憶する秘密情報記憶装置１１５を備えている。この秘密情報は、グループ情報生成部１１１によって生成されたグループ秘密情報ＧＰＲＶＩと、ユーザＩＤ及びメンバ署名鍵ＩＤのペアのリストとを含む。このリストは、グループ１４に所属する全てのユーザについて、当該ユーザのＩＤ（ユーザＩＤ）と、当該ユーザのユーザ端末１２に送信された当該ユーザに固有のメンバ署名鍵のＩＤ（メンバ署名鍵ＩＤ）とのペアのリストである。
【００１９】
ユーザ端末１２は、グループ参加要求部１２１及び署名生成部１２２の各処理部を備えている。グループ参加要求部１２１は、ユーザ端末１２のユーザがグループ１４に参加をする際に、グループ参加要求（グループ参加要求メッセージ）ＧＪＲをＧＭ端末１１へ送信する。署名生成部１２２は、メッセージｍに対するグループ署名σを、メッセージｍ及びユーザ端末１２のユーザに配布されたメンバ署名鍵をもとに生成する。ユーザ端末１２はまた、メンバ署名鍵記憶装置１２３を備えている。メンバ署名鍵記憶装置１２３は、ＧＭ端末１１から送信されたメンバ署名鍵を記憶するのに用いられる。
【００２０】
ユーザ端末１３は署名検証部１３１を備えている。署名検証部１３１は、ユーザ端末１２で生成されたグループ署名が、グループ１４に所属するユーザのユーザ端末１２のうちのいずれかにより生成されたことを、グループ公開情報ＧＰＵＢＩを用いて検証する処理部である。
【００２１】
このように、本実施形態においては、ユーザ端末１２が署名生成部１２２を備えたグループ署名（デジタル署名）装置として用いられ、ユーザ端末１３が署名検証部１３１を備えた署名検証装置として用いられている。しかし、ユーザ端末１２が、グループ参加要求部１２１、署名生成部１２２及びメンバ署名鍵記憶装置１２３に加えて、署名検証部１３１を備えていても良い。この場合、ユーザ端末１２のユーザは、署名検証者となることも可能となる。同様に、ユーザ端末１３が、署名検証部１３１に加えて、グループ参加要求部１２１、署名生成部１２２及びメンバ署名鍵記憶装置１２３を備えていても良い。この場合、ユーザ端末１３のユーザは、グループ（例えばグループ１４）に所属して署名者（グループ署名者）となることも可能となる。また、図１では、１つのグループだけが示されている。しかし、図１のシステムに複数のグループが存在しても構わない。
【００２２】
ＧＭ端末１１内の上記各処理部、ユーザ端末１２内の上記各処理部及びユーザ端末１３内の上記処理部は、それぞれ、当該ＧＭ端末１１、ユーザ端末１２及びユーザ端末１３にインストールされた特定のソフトウェアプログラムを当該端末が読み取って実行することにより実現される。このプログラムは、コンピュータで読み取り可能な記憶媒体（フロッピーディスク（登録商標）に代表される磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤに代表される光ディスク、フラッシュメモリに代表される半導体メモリ等）に予め格納して頒布可能である。また、このプログラムが、ネットワークを介してダウンロード（頒布）されても構わない。
【００２３】
次に、図１のシステムにおけるグループ署名（デジタル署名）について、グループ１４に所属するユーザｕが署名者となり、グループ１４に所属しないユーザｖが署名検証者となる場合を例に、図２乃至図６を参照して説明する。図２は、ＧＭ端末１１、ユーザｕ（署名者）のユーザ端末１２及びユーザｖ（署名検証者）のユーザ端末１３の動作手順を示すシーケンスチャートである。図３は、ＧＭ端末１１、ユーザ端末１２及びユーザ端末１３で生成される情報と、ＧＭ端末１１、ユーザ端末１２及びユーザ端末１３の間で送受信される情報の一例を示す図である。図４は、ＧＭ端末１１内の各部、ユーザ端末１２及び公開情報掲示板サーバ１６の間で授受される情報の流れを示す図である。図５は、ユーザ端末１２及び１３内の各部、ＧＭ端末１１並びに公開情報掲示板サーバ１６の間で授受される情報の流れを示す図である。図６は、リボークメンバ署名鍵リスト、並びにメンバ署名鍵のリボーク実行後の、グループ秘密情報及びグループ公開情報の一例を示す図である。なお、署名検証者はグループ１４内のユーザに限らず、グループ１４外のユーザでも構わない。
【００２４】
図１のシステムにおけるデジタル署名は、以下の実行ステップＳ１乃至Ｓ６に従い実行される。
【００２５】
ステップＳ１(グループの準備)：
ＧＭ端末１１内のグループ情報生成部１１１は、グループ秘密情報ＧＰＲＶＩ（ｄｅｃ,ａ0,...,ａv,ｒ）及びグループ公開情報ＧＰＵＢＩ（ｐ,ｑ,ｅｎｃ,ｈ,ｐｋ）を生成する（ステップＳ１ａ）。グループ秘密情報ＧＰＲＶＩは、ＧＭ端末１１が秘密に保持する情報である。グループ公開情報ＧＰＵＢＩは、グループ１４に所属するユーザに共通の情報である。グループ情報生成部１１１は、生成されたグループ公開情報ＧＰＵＢＩを、公開情報掲示板サーバ１６が管理する公開情報掲示板によって公開可能なように、当該サーバ１６に送信する（ステップＳ１ｂ）。ＧＭ端末１１はまた、生成されたグループ秘密情報ＧＰＲＶＩを第３者から秘匿された状態で秘密情報記憶装置１１５に記憶する（ステップＳ１ｃ）。
【００２６】
グループ秘密情報ＧＲＰＲＶ（ｄｅｃ,ａ0,...,ａv,ｒ）及びグループ公開情報ＧＲＰＵＢ（ｐ,ｑ,ｅｎｃ,ｈ,ｐｋ）は次のように作成される。  
まずグループ情報生成部１１１は、素数位数ｑの巡回群Ｇとその生成元ｇを選び公開情報掲示板サーバ１６により公開情報掲示板に公開させる。ここでは、例として、ｑ|ｐ-１を満たす十分大きな素数ｐ,ｑを選び、位数がｑとなるＺp*の部分群をＧとし、ｐ,ｑ,ｇを公開するとする。またグループ情報生成部１１１は、強秘匿な確率的公開鍵暗号(例えばElGamal暗号)の暗号化関数ｅｎｃ：Ｒ×Ｐ→Ｄ（集合Ｒ及びＰを集合Ｄに変換するための関数）を公開情報掲示板サーバ１６により公開情報掲示板に公開させる。
【００２７】
ここで、本実施形態で適用される表記について説明する。本実施形態では、“ｔe”を“ｔ_e”で表すことがある。明らかなように、記号“_”は、後続のｅが先行するｔの下付文字（添字）であることを表す。したがって、例えば“r_j”は、“rj”を表す。
【００２８】
今、ｈj＝ｇ{r_j},ｒj∈Ｚq,ｊ＝0,...,vを満たすｈ0,...,ｈv∈Ｇを考える。このとき、ｙ∈Ｇについてｈ0δ_0...ｈvδ_vを満たすベクトルΔ＝＜δ0,...,δv＞を、ｙのｈ0,...,ｈvをベースとしたＤＬＯＧ表記と呼ぶ。ｙ,ｈ0,...,ｈvが与えられたときにｙのＤＬＯＧ表記を求めることは、Ｇ上の離散対数問題と同等に困難であることが知られている。また、ｍ（＜ｖ）個のＤＬＯＧ表記Δ1からΔm与えられたときに、与えられたＤＬＯＧ表記の凸結合（convex combination）となるＤＬＯＧ表記しか得られないことが知られている。凸結合とは、ベクトルΔ1からΔmの線形結合ΣμiΔiのうち，係数μ1からμmがΣμi＝１を満たす結合である。ただし、ΣμiΔiはμiΔiのｉ＝１からｉ＝ｍまでの総和を表し、Σμiはμiのｉ＝１からｉ＝ｍまでの総和を表す。
【００２９】
またグループ情報生成部１１１は、復号関数ｄｅｃを秘密情報記憶装置１１５に記憶する。即ちＧＭ端末１１は、復号関数ｄｅｃを秘密に保持する。さらにグループ情報生成部１１１は、一方向性ハッシュ関数ｈ：{０,１}*→{０,１}lを任意に選び公開する。一方向性ハッシュ関数ｈは、任意の長さのビット列を長さｌ（ｌビット）のビット列に変換するのに用いられる。またグループ情報生成部１１１は、Ｇ上のランダムなｖ次多項式
ｆ(x)＝ａ0+ａ1ｘ+...+ａvｘv (ｍｏｄ ｑ)
を選び、係数ａ0,...,ａvを、復号関数ｄｅｃと同様に、秘密情報記憶装置１１５に記憶する。
【００３０】
さらにグループ情報生成部１１１は、ｒ∈Ｚq及びｘ1,...,ｘv∈Ｚqをランダムに選ぶ。ｒは乱数である。グループ情報生成部１１１は、乱数ｒを秘密情報記憶装置１１５に記憶する。グループ情報生成部１１１は、ｒ及びｘ1,...,ｘvを用いて、以下の(ｙ,ｈ0,ｈ1,...,ｈv)
ｙ＝ｇ{(a_0)r}
ｈ0＝ｇr
ｈi＝ｇ{r×f(x_i)}  (i=1,...,v)
を計算する。
【００３１】
次にグループ情報生成部１１１は、(ｙ,ｈ0,ｈ1,...,ｈv)及び(ｘ1,...,ｘv)を含む、以下のグループ公開鍵ｐｋ
ｐｋ＝{(ｙ,ｈ0,ｈ1,...,ｈv),(ｘ1,...,ｘv)}
を生成して公開する。
【００３２】
このようにグループ情報生成部１１１は、グループ公開鍵ｐｋを含むグループ公開情報ＧＰＵＢＩ（ｐ,ｑ,ｅｎｃ,ｈ,ｐｋ）を生成し、公開情報掲示板サーバ１６により公開させる。またグループ情報生成部１１１は、グループ秘密情報ＧＰＲＶＩ（ｄｅｃ,ａ0,...,ａv,ｒ）を生成し、第３者から秘匿された状態で秘密情報記憶装置１１５に記憶する
ステップＳ２（グループへの参加）：
ユーザ端末、例えばユーザｕのユーザ端末１２は、当該ユーザｕがグループ（ここではグループ１４）に参加をする際、当該ユーザｕの操作に従い、ＧＭ端末１１との間で以下のプロトコルを実行する。
【００３３】
まずユーザ端末１２内のグループ参加要求部１２１は、グループ参加要求ＧＪＲをＧＭ端末１１へ送信する（ステップＳ２ａ）。ＧＭ端末１１内のメンバ署名鍵生成部１１２は、ユーザ端末１２からグループ参加要求ＧＪＲを受け取ると、グループ公開情報ＧＰＵＢＩ（グループ公開鍵ｐｋ）に含まれている(ｘ1,...,ｘv)、及びこれまでにグループ１４へ参加したユーザのユーザ端末へ配布した全てのｘiのいずれとも一致しないｘu∈Ｚqをランダムに選ぶ（ステップＳ２ｂ）。ＧＭ端末１１は、選ばれたｘuと上記多項式ｆ(x)とから、以下の値
ｓｋu＝(ｘu,ｆ(ｘu))
をユーザｕのメンバ署名鍵ｓｋuとして生成する（ステップＳ２ｃ）。ここで、ｘuは、ユーザｕのメンバ署名鍵ｓｋuのＩＤ（つまりメンバ署名鍵ＩＤ）として用いられる。メンバ署名鍵生成部１１２は、生成されたメンバ署名鍵ｓｋuを、ＧＭ端末１１とユーザ端末１２との間の安全な通信路１５により当該ユーザ端末１２へ秘密に送信（配布）する（ステップＳ２ｄ）。またメンバ署名鍵生成部１１２は、ユーザｕのＩＤ（ユーザ識別子）であるｕとメンバ署名鍵ｓｋuのＩＤ（メンバ署名鍵ＩＤ）であるｘuとのペア(ｕ,ｘu)を秘密情報記憶装置１１５に記憶する（ステップＳ２ｅ）。つまりＧＭ端末１１は、(ｕ,ｘu)を秘密（安全）に保持する。ここで、ｘuと多項式ｆ(x)とから、メンバ署名鍵ｓｋuが生成されることから、(ｕ,ｘu)を保持することは、ユーザｕのＩＤとメンバ署名鍵ｓｋuとのペア(ｕ,ｓｋu)を保持することと等価である。一方、ユーザ端末１２は、メンバ署名鍵生成部１１２から送信されたメンバ署名鍵ｓｋuをメンバ署名鍵記憶装置１２３に記憶する（ステップＳ２ｆ）。
【００３４】
ステップＳ３（グループ署名の生成）：
ユーザ端末１２内の署名生成部１２２は、メッセージｍに対するグループ署名σの生成が必要な場合、メンバ署名鍵ｓｋu及びメッセージｍを入力すると共に、公開情報掲示板サーバ１６により公開情報掲示板に公開されているグループ公開情報ＧＰＵＢＩを入力する（ステップＳ３ａ）。署名生成部１２２は、メンバ署名鍵ｓｋu、メッセージｍ及びグループ公開情報ＧＰＵＢＩをもとに、以下の手順によりグループ署名σを生成する（ステップＳ３ｂ）。
【００３５】
(1) 署名生成部１２２は、メンバ署名鍵ｓｋuと、グループ公開情報ＧＰＵＢＩに含まれているグループ公開鍵ｐｋとから、次式（１）及び（２）に従って、値λ0及びλj(j=1,...,v)を計算する。ここで、ベクトル＜λ0,...,λv＞は、ｈ0,...,ｈvをベースとしたＤＬＯＧ表記である。
【数１】
2005210638.tif 000003
【００３６】
(2) 署名生成部１２２は、i=1,...,l, j=0,...,v について、以下の乱数
乱数ｒ{i,j}∈Ｚq
乱数＜ρ(0){i,j},ρ(1){i,j}＞∈Ｒ2
をランダムに選ぶ。
【００３７】
(3) 署名生成部１２２は、i=1,...,lについて、以下のｄi
ｄi＝ｈ0{r_{i,0}}×...×ｈv{r_{i,v}}
を計算する。
【００３８】
(4) 署名生成部１２２は、i=1,...,l, j=0,...,v について、暗号化関数ｅｎｃを用いて以下の値Ｃ(0){i,j},Ｃ(1){i,j}
Ｃ(0){i,j}＝ｅｎｃ(ρ(0){i,j},ｒ{i,j})
Ｃ(1){i,j}＝ｅｎｃ(ρ(1){i,j},ｒ{i,j}-λj)
を計算する。
【００３９】
(5) 署名生成部１２２は、一方向性ハッシュ関数ｈを用いて、以下の値ｃ（チャレンジｃ）
ｃ＝ｈ(ｍ‖ｄ1‖...‖ｄl‖Ｃ(0){1,0}‖Ｃ(1){1,0}‖
...‖Ｃ(0){l,v}‖Ｃ(1){l,v})
を計算する。ここで“‖”はデータの連結を表す。
【００４０】
(6) 署名生成部１２２は、i=1,...,l, j=0,...,v について、以下の値
ｓ{i,j}＝ｒ{i,j}-ｃ[i]λj (ｍｏｄ ｑ)
ρ{i,j}＝ρ(ｃ[i]){i,j}
を計算する。ここでｃ[i]はｃのi番目のビットを表す。
【００４１】
(7) 署名生成部１２２は、i=1,...,l, j=0,...,v, b=0,1 について
以下の値σ
σ＝({ｄi},{Ｃ(b){i,j}},{ｓ{i,j}},{ρ{i,j}})
を、グループ署名σとして生成する。
【００４２】
このように、ｈ0,...,ｈvをベースとしたｙのＤＲＯＧ表記＜λ0,...,λδv＞を求めることによって生成されたグループ署名σは、いわゆる非対話型零知識証明プロトコルで用いられる零知識証明のための情報である。即ち、グループ署名σは、公開鍵ｐｋ（暗号文）を復号可能なメンバ署名鍵ｓｋu（復号鍵）がユーザ端末１２のユーザｖに配布されていることを、検証者（ユーザ端末１３）に教えることなく、証明するための情報（メンバ署名鍵について零知識であることが証明可能なグループ署名）である。
【００４３】
署名生成部１２２は、グループ署名σを生成すると、当該グループ署名σの生成の対象となったメッセージｍと当該グループ署名σとのペア（ｍ,σ）を、署名検証者（ユーザｖ）のユーザ端末１３へ送信する（ステップＳ３ｃ）。また署名生成部１２２は、(ｍ,σ)をＧＭ端末１１へも送信する（ステップＳ３ｄ）。
【００４４】
ステップＳ４（グループ署名の検証）：
ユーザ端末１３内の署名検証部１３１は、ユーザ端末１２から送られるメッセージｍと当該メッセージｍに対するグループ署名σとのペア（ｍ,σ）を受け取る。すると署名検証部１３１は、（ｍ,σ）及び公開情報掲示板サーバ１６から取得可能なグループ公開情報ＧＰＵＢＩを用いて、以下の手順でグループ署名σの正当性を検証する。
【００４５】
(1) 署名検証部１３１は、非対話型零知識プロトコルに従い、メッセージｍ及びグループ署名σ（つまり({ｄi},{Ｃ(b){i,j}},{ｓ{i,j}},{ρ{i,j}})）から、グループ公開情報ＧＰＵＢＩに含まれている一方向性ハッシュ関数ｈを用いて以下の値
ｃ＝ｈ(ｍ‖ｄ1‖...‖ｄl‖Ｃ(0){1,0}‖Ｃ(1){1,0}‖
...‖Ｃ(0){l,v}‖Ｃ(1){l,v})
を計算する。
【００４６】
(2) 署名検証部１３１は、算出されたｃ（つまりｃ[1]‖...‖ｃ[l]）を用いて、i=1,...,l, j=0,...,v について、以下の式（３）及び（４）が成り立つことを検証する。
【００４７】
Ｃ(ｃ[i]){i,j}＝ｅｎｃ(ρ{i,j},ｓ{i,j})                    （３）
ｈ0{s_{i,0}}×...×ｈv{s_{i,v}}＝ｄi／ｙc[i] (ｍｏｄ ｐ)     （４）
署名検証部１３１は、式（３）及び（４）が成り立つ場合は、グループ署名σが正当であることを示すメッセージ（ＯＫメッセージ）を、例えばユーザ端末１３の表示器に出力する。一方、式（３）及び（４）の少なくとも一方が成り立たない場合は、署名検証部１３１は、グループ署名σが正当でないことを示すメッセージ（ＮＧメッセージ）を、例えばユーザ端末１３の表示器に出力する。
【００４８】
ステップＳ５（署名者の開示）：
ＧＭ端末１１内の署名開示部１１３は、ユーザ端末１２から送られるメッセージｍと当該メッセージｍに対するグループ署名σとのペア（ｍ,σ）を受け取る。すると署名開示部１１３は、（ｍ,σ）及び秘密情報記憶装置１１５に記憶されているグループ秘密情報ＧＰＲＶＩを用いて、以下の手順でグループ署名σの生成に関与した署名者のＩＤを特定する（ステップＳ５ａ）。
【００４９】
まず署名開示部１１３は、グループ署名σから、復号関数ｄｅｃを用いて、次式
λj＝ｄｅｃ(Ｃ(0){i,j})-ｄｅｃ(Ｃ(1){i,j}) (ｍｏｄ ｑ)
により、ベクトル＜λ0,...,λv＞を得る。すると署名開示部１１３は、以下の(a)または(b)の方法により、グループ署名を生成したユーザ(署名者)のＩＤを特定する。
【００５０】
(a)正規のメンバ署名鍵を用いて生成されたグループ署名の場合
この場合、署名開示部１１３は、ベクトル＜λ0,...,λv＞と上記式（２）とから、メンバ署名鍵ＩＤであるｘuを取得する。署名開示部１１３は、秘密情報記憶装置１１５に記憶されている、ユーザＩＤとメンバ署名鍵ＩＤとのペア(ｉ,ｘi)のリストの中から、ｘuをメンバ署名鍵ＩＤとして含むペア、つまり（ｕ,ｘu)を検索する。署名開示部１１３は、検索された（ｕ,ｘu)から、グループ署名σを生成したユーザ(署名者)のＩＤ（つまりｕ）を特定する。この署名者のＩＤを特定するのに必要な計算量は、Ｏ(vl)、つまりｖとｌの積のオーダーである。署名開示部１１３は、特定されたユーザ(署名者)のＩＤを、例えばＧＭ端末１１の表示器に出力する。
【００５１】
(b)偽造されたメンバ署名鍵を用いて生成されたグループ署名の場合
ユーザが結託して、複数のメンバ署名鍵から、ステップＳ４でのグループ署名の検証に成功するメンバ署名鍵を偽造し、その偽造されたメンバ署名鍵を用いてグループ署名が生成されたものとする。この場合、グループ署名σから、復号関数ｄｅｃを用いて取得されるベクトルを、＜λ0',...,λv'＞と表現する。このグループ署名σから得られるλ0',...,λv'は、各メンバ署名鍵から得られるλ0,...,λvの凸結合となっている。この場合、署名開示部１１３は、Berlekamp-Welch拡張Reed-Solomon符号復号アルゴリズムにより、結託したメンバ署名鍵数がｖ／２以下ならば、結託した全てのメンバ署名鍵に対応するλ0,...,λvを特定できる。これにより署名開示部１１３は、結託した全てのメンバ署名鍵のＩＤ（ｘi）を特定する。この結託した全てのメンバ署名鍵のＩＤを特定するのに必要な計算量は、Ｏ(n(log n)2)(n:グループのメンバ署名鍵の総数)、つまりn(log n)2のオーダーである。署名開示部１１３は、結託した全てのメンバ署名鍵のＩＤ（ｘi）を特定すると、秘密情報記憶装置１１５に記憶されている、ユーザＩＤとｘiとのペア(ｉ,ｘi)から、グループ署名σを生成したユーザ(署名者)のＩＤ（つまりｉ）を特定する。署名開示部１１３は、特定されたユーザ(署名者)のＩＤを、例えばＧＭ端末１１の表示器に出力する。
【００５２】
ステップＳ６（メンバ署名鍵のリボーク)：
ＧＭ端末１１内のメンバ署名鍵リボーク部１１４は、以下の手順によってグループ公開鍵を更新することにより、ｖ個以下のメンバ署名鍵をリボークする。ここでは、ｍ個(ただしｍ≦ｖ)のメンバ署名鍵ｓｋ{R_1},..,ｓｋ{R_m}をリボークするものとする。このリボークすべきメンバ署名鍵のＩＤのリスト（リボークメンバ署名鍵リスト）ＲＭＳＫＬは、図６（ａ）に示すように、(ｘ{R_1},..,ｘ{R_m})である。
【００５３】
まずメンバ署名鍵リボーク部１１４は、乱数ｒ'∈Ｚqをランダムに選び、以下の値
y'＝ｇ{(a_0)r'}
ｈ0'＝ｇr'
ｈi'＝ｇ{r'×f(x_{R_i})}  (i=1,...,m)
ｈj'＝ｇ{r'×f(x_j)}      (j=m+1,...,v)
を計算する。このときメンバ署名鍵リボーク部１１４は、秘密情報記憶装置１１５に記憶されているグループ秘密情報ＧＰＲＶＩ中の乱数ｒをｒ'に更新する（ステップＳ６ａ）。この乱数ｒがｒ'に更新されたグループ秘密情報ＧＰＲＶＩ（つまり更新後のグループ秘密情報ＧＰＲＶＩ）を図６（ｂ）に示す。この乱数の更新により、以下に述べるようにメンバ署名鍵ｓｋ{R_1},..,ｓｋ{R_m}がリボークされても、当該メンバ署名鍵がリボークされる以前に生成されたグループ署名の匿名性及び非結合性が損なわれずに済む。
【００５４】
次にメンバ署名鍵リボーク部１１４は、算出されたy',ｈ0',ｈi'(i=1,...,m)及びｈj'(j=m+1,...,v)をもとに、新しいグループ公開鍵ｐｋ'
ｐｋ'={(ｙ',ｈ0',ｈ1',...,ｈv'), (ｘ{R_1},...,ｘ{R_m},ｘm+1,...,ｘv)}
を生成する。この新しいグループ公開鍵ｐｋ'を元のグループ公開鍵ｐｋ＝{(ｙ,ｈ0,ｈ1,...,ｈv),((ｘ1,...,ｘv)}と比較すると、元のグループ公開鍵ｐｋに含まれているメンバ署名鍵ＩＤ(ｘ1,...,ｘv)中のｘ1,...,ｘmがｘ{R_1},...,ｘ{R_m}に置換されている点に注意されたい。メンバ署名鍵リボーク部１１４は、公開情報掲示板サーバ１６によって公開情報掲示板に公開されているグループ公開情報ＧＰＵＢＩ中のグループ公開鍵ｐｋを、新しいグループ公開鍵ｐｋ'に更新させる（ステップＳ６ｂ）。このグループ公開鍵ｐｋがｐｋ'に更新されたグループ公開情報ＧＰＵＢＩ（つまり更新後のグループ公開情報ＧＰＵＢＩ）を図６（ｃ）に示す。
【００５５】
このようにして更新されたグループ公開情報ＧＰＵＢＩを用いた場合、リボークされていないメンバ署名鍵ｓｋi (i≠R_1,...,R_m)が配布された（割り当てられた）ユーザのユーザ端末は、上記ステップＳ３において，前記式（１）および式（２）のｘ1,...,ｘmをｘ{R_1},...,ｘ{R_m}に置き換えることによりグループ署名を生成することができる。一方、リボークされたメンバ署名鍵ｓｋ{R_i}=(ｘ{R_i},ｆ(ｘ{R_i})) (i=1,...,m)が配布されたユーザのユーザ端末は、λjを計算することができない。その理由は、更新されたグループ公開鍵ｐｋ'中のメンバ署名鍵ＩＤ集合ｘj (j=R_1,...,R_m,m+1,...,v)には、リボークされたメンバ署名鍵のＩＤ（つまりｘ{R_i}）に一致するｘjが含まれているため、前記式（２）中の分母(ｘj-ｘu)に相当する(ｘj-ｘ{R_i})が０となることによる。したがって、λjの計算に、リボークされたメンバ署名鍵ｓｋ{R_i}のＩＤ（つまりｘ{R_i}）を用いるユーザ端末は、グループ署名を生成することができない。このことは、リボークすべきメンバ署名鍵ｓｋ{R_i}（放送型暗号方式における復号鍵に相当）が、公開鍵（放送型暗号方式における暗号文に相当）を復号可能なメンバ署名鍵の集合から排除されたこと、つまり公開鍵を復号可能なメンバ署名鍵の集合が、メンバ署名鍵ｓｋ{R_i}を排除した別のメンバ署名鍵の集合に動的に変更されたことを表す。
【００５６】
ステップＳ３によって生成されるグループ署名は、以下の仮定のもとで、メンバ署名鍵について零知識であることが証明可能である。この仮定とは、数学的に解くことが困難と広く知られているDecision Diffie-Hellman（ＤＤＨ）問題の困難性の仮定（いわゆるＤＤＨ仮定）と、安全性の証明で広く用いられているランダムオラクルモデル（つまり一方向ハッシュ関数を理想的なランダム関数とするモデル）の仮定である。よって、本実施形態においては、ＧＭ端末１１以外のユーザ端末が、グループ署名から署名者を特定することは困難である。つまり、グループ署名の匿名性が保たれる（Anonymity）。同様に、グループ署名はメンバ署名鍵について零知識であることから、同じメンバ署名鍵で複数のグループ署名を生成しても、同じメンバ署名鍵により生成されたものかを特定することが困難である。よってグループ署名の非結合性（Unlinkability）が保たれる。また本実施形態においては、ステップＳ５により、ｖ／２個以下のメンバが結託してもグループ署名を偽造することは困難である（Coalition-Resistance/ Traceability）。さらに本実施形態においては、ステップＳ６により、グループ公開鍵を更新するだけで、ｖ個以下のメンバ署名鍵をリボークすることができる（Revokability）。
【図面の簡単な説明】
【００５７】
【図１】本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図。
【図２】ＧＭ端末１１、ユーザｕ（署名者）のユーザ端末１２及びユーザｖ（署名検証者）のユーザ端末１３の動作手順を示すシーケンスチャート。
【図３】ＧＭ端末１１、ユーザ端末１２及びユーザ端末１３で生成される情報と、ＧＭ端末１１、ユーザ端末１２及びユーザ端末１３の間で送受信される情報の一例を示す図。
【図４】ＧＭ端末１１内の各部、ユーザ端末１２及び公開情報掲示板サーバ１６の間で授受される情報の流れを示す図。
【図５】ユーザ端末１２及び１３内の各部、ＧＭ端末１１並びに公開情報掲示板サーバ１６の間で授受される情報の流れを示す図。
【図６】リボークメンバ署名鍵リスト、並びにメンバ署名鍵のリボーク実行後の、グループ秘密情報及びグループ公開情報の一例を示す図。
【符号の説明】
【００５８】
１１…グループマネージャ端末（ＧＭ端末、デジタル署名管理装置）、１２…ユーザ端末（グループに所属するユーザの端末、デジタル署名装置）、１３…ユーザ端末（グループに所属しないユーザの端末、署名検証装置）、１４…グループ、１５…安全な通信路、１６…公開情報掲示板サーバ、１７…ネットワーク、１１１…グループ情報生成部、１１２…メンバ署名鍵生成部、１１３…署名開示部、１１４…メンバ署名鍵リボーク部、１１５…秘密情報記憶装置、１２１…グループ参加要求部、１２２…署名生成部、１２３…メンバ署名鍵記憶装置、１３１…署名検証部。
【図１】
2005210638.tif 000004
【図２】
2005210638.tif 000005
【図３】
2005210638.tif 000006
【図４】
2005210638.tif 000007
【図５】
2005210638.tif 000008
【図６】
2005210638.tif 000009