(57)【特許請求の範囲】
【請求項１】
グループ公開鍵と、追跡用公開鍵と、メンバ証明書と、メンバ秘密鍵と、メッセージと、が入力され、前記メッセージに対するグループ署名を出力するグループ署名装置であって、
位数が同じである群１、群２、群Ｔ、群Ｅの４個の群に対する記述と、群１と群２から群Ｔへの双線形写像の記述と、群１、群２、群Ｔ、群Ｅの各生成子と、前記群１、前記群２、前記群Ｔを用いた署名方式の署名公開鍵と、が含まれた前記グループ公開鍵と、群Ｂの要素からなる前記追跡用公開鍵と、前記メンバ秘密鍵とから、前記メンバ秘密鍵から生成したメンバ証拠の一部を追跡用公開鍵により暗号化した暗号文を生成する暗号化装置を有することを特徴とし、特に群Ｅが群１、群２、群Ｔとは異なる群で、ディフィヘルマン判別問題を解くことが困難であることを特徴とするグループ署名装置。
【請求項２】
請求項１に記載のグループ署名装置において、
前記暗号文に暗号化された秘密鍵と、該秘密鍵に対する署名が入力されたデータから計算できることを証明するデータである知識の証明文を生成する知識の証明文生成装置を備え、出力する前記グループ署名が前記知識の証明文生成装置による知識の証明文を含むことを特徴とするグループ署名装置。
【請求項３】
請求項２に記載のグループ署名装置において、
前記知識の証明文生成装置が、
前記グループ公開鍵と、前記追跡用公開鍵と、前記メンバ秘密鍵と、前記メンバ証明書と、前記乱数と、が入力され、暗号化の乱数の知識を証明するためのデータである暗号化のコミットメントと、署名およびメンバ秘密鍵の知識を証明する為のデータであるメンバ証明書のコミットメントとを生成し、前記暗号化のコミットメントと前記メンバ証明書のコミットメントをコミットメントとして出力するコミットメント生成装置と、
前記グループ公開鍵と、前記追跡用公開鍵と、前記暗号文と、前記コミットメントとが入力され、これらの値のハッシュ値を挑戦値として出力する挑戦値生成装置と、
前記グループ公開鍵と、前記メンバ秘密鍵と、前記メンバ証明書と、前記乱数と、前記挑戦値が入力され、暗号化のレスポンスと、メンバ証明のレスポンスとをレスポンスとして出力するレスポンス生成装置と、
から構成されることを特徴とするグループ署名装置。
【請求項４】
請求項３に記載のグループ署名装置において、
前記グループ署名が、前記暗号文と、前記コミットメントと、前記レスポンスとからなることを特徴とするグループ署名装置。
【請求項５】
請求項３に記載のグループ署名装置において、
前記グループ署名が、前記暗号文と、前記挑戦値と、前記レスポンスとからなることを特徴とするグループ署名装置。
【請求項６】
グループ公開鍵と、追跡用公開鍵と、メッセージと、グループ署名と、が入力され、前記グループ署名が前記メッセージに対する正当なグループ署名であるかを判断して、「正当」あるいは「不当」を出力するグループ署名検証装置であって、
位数が同じである群１、群２、群Ｔ、群Ｅの４個の群に対する記述と、群１と群２から群Ｔへの双線形写像の記述と、群１、群２、群Ｔ、群Ｅの各生成子と、前記群１、前記群２、前記群Ｔを用いた署名方式の署名公開鍵と、が含まれたグループ公開鍵と、群Ｅの要素からなる追跡用公開健と、メンバ秘密鍵から生成されるメンバ証拠の一部を追跡用公開鍵により暗号化した暗号文を含むグループ署名が入力されると、前記グループ署名が前記メッセージに対する正当なグループ署名であるかを判断して、「正当」あるいは「不当」を出力することを特徴とし、特に群Ｅが群１、群２、群Ｔとは異なる群で、ディフィヘルマン判別問題を解くことが困難であることを特徴とするグループ署名検証装置。
【請求項７】
請求項６に記載のグループ署名検証装置において、
前記暗号文に暗号化されたメンバ証拠の一部を生成する為に用いた秘密鍵と、この秘密鍵に対する署名がグループ署名装置に入力されたデータとグループ署名装置に含まれるデータとから計算できることを証明するデータである知識の証明文であることを検証する知識の証明文検証装置を備え、
前記グループ署名が前記証明文検証装置により検証された知識の証明文を含むことを特徴とするグループ署名検証装置。
【請求項８】
請求項７に記載のグループ署名装置において、
前記グループ署名が、前記暗号文と、前記コミットメントと、前記レスポンスとからなり、
前記知識の証明文検証装置が、
前記グループ公開鍵と、前記追跡用公開鍵と、前記暗号文と、前記コミットメントとが入力され、これらの値のハッシュ値を挑戦値として出力する挑戦値生成装置と、
前記グループ公開鍵と、前記追跡用公開鍵と、前記暗号文と、前記コミットメントと、前記挑戦値と、前記レスポンスとが入力され、これらの入力がある式を満たすかどうかに応じて正当又は不当を出力するレスポンス検証装置と、からなり、レスポンス検証装置の出力をグループ署名検証装置の出力として出力することを特徴とするグループ署名検証装置。
【請求項９】
請求項７に記載のグループ署名検証装置において、
前記グループ署名が、前記暗号文と、前記挑戦値と、前記レスポンスとからなり、
前記知識の証明文検証装置が、
前記グループ公開鍵と、前記追跡用公開鍵と、前記レスポンスと、前記挑戦値と、が入力され、暗号化のコミットメントとメンバ証明書のコミットメントをコミットメントとして出力するコミットメント生成装置と、
前記グループ公開鍵と、前記追跡用公開鍵と、前記暗号文、前記コミットメントが入力され、これらの値のハッシュ値が前記挑戦値に一致するかどうかに応じて正当又は不当を出力するレスポンス検証装置と、からなり、
前記レスポンス検証装置の出力をグループ署名検証装置の出力として出力することを特徴とするグループ署名検証装置。
【請求項１０】
グループ公開鍵と乱数とが入力され、メンバ証明書発行装置と通信することによりメンバ証明書とメンバ秘密鍵とを出力するメンバ証明書獲得装置であって、位数が同じである群１、群２、群Ｔ、群Ｅの４個の群に対する記述と、群１と群２から群Ｔへの双線形写像の記述と、群１、群２、群Ｔ、群Ｅの各生成子と、前記群１、前記群２、前記群Ｔを用いた署名方式の署名公開鍵とが含まれる前記グループ公開鍵が入力されると、前記位数以下の整数を含む前記メンバ秘密鍵と、前記群Ｅの前記生成子に前記メンバ秘密鍵を乗じた値であるメンバ証拠と、前記群１あるいは群２の前記生成子に前記メンバ秘密鍵を乗じた値である前記群１あるいは群２の要素と、を前記メンバ証明書発行装置に送信し、その後、前記メンバ証明書発行装置より前記署名公開鍵で検証可能な、前記メンバ秘密鍵に対する署名を受信すると、該署名を前記メンバ証明書とすることを特徴とし、特に群Ｅが群１、群２、群Ｔ、とは異なる群で、ディフィヘルマン判別問題を解くことが困難であることを特徴とするメンバ証明書獲得装置と、
グループ公開鍵とグループ秘密鍵と乱数とが入力され、メンバ証明書獲得装置と通信することによりメンバを識別するために使うメンバ証拠を出力するメンバ証明書発行装置であって、位数が同じである群１、群２、群Ｔ、群Ｅの４個の群に対する記述と、群１と群２から群Ｔへの双線形写像の記述と、群１、群２、群Ｔ、群Ｅの各生成子と、前記群１、前記群２、前記群Ｔを用いた署名方式の署名公開鍵とが含まれた前記グループ公開鍵と、前記群１、前記群２、前記群Ｔを用いた署名方式の前記署名公開鍵に対応する署名秘密鍵と、が含まれた前記グループ秘密鍵と、が入力され、前記メンバ証明書獲得装置より前記群Ｅの前記生成子にメンバ秘密鍵を乗じた値であるメンバ証拠と、前記群１あるいは群２の前記生成子にメンバ秘密鍵を乗じた値である前記群１あるいは群２の要素と、受信すると、前記署名秘密鍵を用いて前記メンバ秘密鍵に対する署名を生成し、該署名を前記メンバ証明書としてメンバ証明書獲得装置に送信することを特徴とし、特に群Ｅが群１、群２、群Ｔとは異なる群で、ディフィヘルマン判別問題を解くことが困難であることを特徴とするメンバ証明書発行装置と、
請求項１に記載のグループ署名装置と、
請求項６に記載のグループ署名検証装置と、
グループ公開鍵と、追跡用公開鍵と、グループ署名と、追跡用秘密鍵と、が入力され、グループ署名に含まれているメンバ秘密鍵から生成されたメンバ証拠の一部の暗号文を復号してメンバ秘密鍵から一意的に決定される値であるメンバ証拠の一部を出力する追跡装置とからなるグループ署名システムであって、
前記メンバ証明書獲得装置が前記メンバ証明書発行装置と通信することでメンバ証明書とメンバ秘密鍵を獲得し、獲得した前記メンバ証明書と獲得した前記メンバ秘密鍵とメッセージとグループ公開鍵と追跡用公開鍵とを前記グループ署名装置に入力し、前記メッセージに対するグループ署名を獲得し、前記メッセージと獲得した前記グループ署名を前記グループ署名検証装置に入力し、前記獲得した前記グループ署名が前記メッセージに対する正当なグループ署名であることを検証するとともに、前記グループ署名を前記追跡装置に入力してグループ署名を生成したメンバを表すメンバ証拠を出力することを特徴とするグループ署名システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループに所属するメンバーが、グループのメンバーであることを証明するための署名を作成し、また確認するグループ署名システムに関し、特に、双線形写像を利用するグループ署名システムに関する。
【背景技術】
【０００２】
従来の双線形写像を用いたグループ署名についての技術として、Dan Boneh,
Xavier Boyen: Short Group Signature. Advances in Cryptology -- CRYPTO 2004,
Lecture Notes in Computer Science 3152, pp. 41-55, 2004, Springer.に記されているグループ署名があげられる。このグループ署名の概略を以下に記す。【０００３】
グループ秘密鍵は、pをある素数として無作為に選ばれた体Z/pZの元γとする。【０００４】
グループ公開鍵は、素数pと、位数pである群1と群2と群Tと、群1と群2から群Tへの双線形写像eと、群2から群1への同型写像φと、文字列を体(Z/pZ)へと写像するハッシュ関数Hashと、を記述する文字列と、群2の生成子G2と、φ(G2=G1なる群1の生成子G1と、無作為に選ばれた群1の元Hと、W=[γ]G2とする。【０００５】
但し、WはG2のγ倍点である。【０００６】
追跡用秘密鍵は、無作為に選ばれた体Z/pZ上の2点、ξ1,ξ2とする。【０００７】
追跡用の公開鍵は、[ξ1]U=[ξ2]V=Hなる群2上の2点とする。メンバ秘密鍵は、無作為に選ばれた体Z/pZ上の点、xとする。【０００８】
メンバ証明書は、無作為に選ばれた体Z/pZ上の点yと、A=[1/(γ+y)]([1-x]G1)なるAとする。【０００９】
以下、グループ署名装置を説明する。【００１０】
グループ署名装置には、署名をするメッセージと、グループ公開鍵と、追跡用公開鍵と、メンバ秘密鍵と、メンバ証明書と、乱数とが入力される。【００１１】
グループ署名装置は、入力された乱数を用いて無作為にZ/pZ上の点αとβを選び、暗号文、T1=[α]U、T2=[β]V、T3=[α+β]Hを生成する。【００１２】
さらに、入力された乱数を用いて無作為にZ/pZ上の点α'とβ'とδ'1とδ'2とy'を選び、コミットメントR1=[α']U、R2=[β']V、R3=e(T3,G2)^(x')・e(H,W)^(-α'-β')・e(H,G2)^(-δ'1-δ'2)・e(H,G2)^(y')、R4=[x']T1-[\delta'1]U、R5=[x']T2-[\delta'2]Vを生成する。ここで記号「^」は冪乗剰余算を意味する。【００１３】
グループ署名装置は、グループ公開鍵と、追跡用公開鍵と、メッセージと、U,V,T1,T2,T3,R1,R2,R3,R4,R5のハッシュ値を生成し、これを挑戦値cとする。【００１４】
グループ署名装置は、レスポンスsα=α'+cα、sβ= β'+cβ、sx=x'+cx、sδ1=δ'1+cxα、sδ2=δ'2+cxβ、sy=y'+xyを生成する。【００１５】
グループ署名は、T1,T2,T3,c,sα, sβ,sx,sδ1,sδ2,syをメッセージmに対するグループ署名として出力する。【００１６】
以下、グループ署名検証装置を説明する。【００１７】
グループ署名検証装置には、署名がなされたメッセージと、グループ公開鍵と、追跡用公開鍵と、が入力される。【００１８】
グループ署名検証装置は、R1=[sα]U-[c]T1、R2=[sβ]V-[c]T2、R3=e(T3,G2)^(sx)・e(H,W)^(-sα-sβ)・e(H,G2)^(-sδ1-sδ2)・e(H,G2)^(sy)(e(G1,G2)/e(T3,W))^(c)、R4=[sx]T1-[sδ1]U、R5=[sx]T2-[sδ2]Uを生成し、グループ公開鍵と、追跡用公開鍵と、署名がなされたメッセージと、U,V,T1,T2,T3,R1,R2,R3,R4,R5のハッシュ値を生成し、これが挑戦値cと一致するかを確認する。一致すればグループ署名は正当、一致しなければ不当と判断する。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
上述した従来の技術の第一の問題点は、グループ署名で使われている暗号文の安全性が、線形ディフィヘルマン判別問題を解くことが難しいという仮定に依拠していることである。ゆえに、グループ署名方式全体の安全性もこの仮定に基づくことになる。本仮定は、文献１の論文で初めて提案グループ署名の安全性を示すために提案された仮定であり、この問題を解く方法の考案を試みた人は少ない。そのため、近い将来解放が提案される可能性が高く、提案されたグループ署名は十分な安全性を備えていない可能性がある。【００２０】
第二の問題点は、グループ署名で使われている暗号文の安全性が、線形-ディフィヘルマン判別問題を解くことが難しいという仮定に加えて、一般群模型(generic group model)に依拠していることである。一般群模型で安全性が示されていても、実際には危険な暗号方式が存在するなど、この模型を用いて安全性を示された方式の安全性は単なる予想に過ぎない。そのため、近い将来解放が提案される可能性が高く、提案されたグループ署名は十分な安全性を備えていない可能性がある。【００２１】
第三の問題点は、計算量と署名のデータ量が多いという点にある。グループ署名をより使いやすいものとするためには、計算量、署名のデータ量を減らすことが望まれる。
【課題を解決するための手段】
【００２４】
本発明のグループ署名装置は、グループ公開鍵と、追跡用公開鍵と、メンバ証明書と、メンバ秘密鍵と、メッセージと、が入力され、前記メッセージに対するグループ署名を出力するグループ署名装置であって、
位数が同じである群１、群２、群Ｔ、群Ｅの４個の群に対する記述と、群１と群２から群Ｔへの双線形写像の記述と、群１、群２、群Ｔ、群Ｅの各生成子と、前記群１、前記群２、前記群Ｔを用いた署名方式の署名公開鍵と、が含まれた前記グループ公開鍵と、群Ｅの要素からなる前記追跡用公開鍵と、前記メンバ秘密鍵とから、前記メンバ秘密鍵から生成したメンバ証拠の一部を追跡用公開鍵により暗号化した暗号文を生成する暗号化装置を有することを特徴とする。【００２５】
この場合、前記暗号文に暗号化された秘密鍵と、該秘密鍵に対する署名が入力されたデータから計算できることを証明するデータである知識の証明文を生成する知識の証明文生成装置を備え、出力する前記グループ署名が前記知識の証明文生成装置による知識の証明文を含むこととしてもよい。【００２６】
また、前記知識の証明文生成装置が、
前記グループ公開鍵と、前記追跡用公開鍵と、前記メンバ秘密鍵と、前記メンバ証明書と、前記乱数と、が入力され、暗号化の乱数の知識を証明するためのデータである暗号化のコミットメントと、署名およびメンバ秘密鍵の知識を証明する為のデータであるメンバ証明書のコミットメントとを生成し、前記暗号化のコミットメントと前記メンバ証明書のコミットメントをコミットメントとして出力するるコミットメント生成装置と、
前記グループ公開鍵と、前記追跡用公開鍵と、前記暗号文と、前記コミットメントとが入力され、これらの値のハッシュ値を挑戦値として出力する挑戦値生成装置と、  前記グループ公開鍵と、前記メンバ秘密鍵と、前記メンバ証明書と、前記乱数と、前記挑戦値が入力され、暗号化のレスポンスと、メンバ証明のレスポンスとをレスポンスとして出力するレスポンス生成装置と、
から構成されることとしてもよい。【００２７】
さらに、前記グループ署名が、前記暗号文と、前記コミットメントと、前記レスポンスとからなるとしてもよい。【００２８】
さらに、前記グループ署名が、前記暗号文と、前記挑戦値と、前記レスポンスとからなるとしてもよい。【００２９】
本発明のグループ署名検証装置は、グループ公開鍵と、追跡用公開鍵と、メッセージと、グループ署名と、が入力され、前記グループ署名が前記メッセージに対する正当なグループ署名であるかを判断して、「正当」あるいは「不当」を出力するグループ署名検証装置であって、
位数が同じである群１、群２、群Ｔ、群Ｅの４個の群に対する記述と、群１と群２から群Ｔへの双線形写像の記述と、群１、群２、群Ｔ、群Ｅの各生成子と、前記群１、前記群２、前記群Ｔを用いた署名方式の署名公開鍵と、が含まれたグループ公開鍵と、群Ｅの要素からなる追跡用公開鍵と、メンバ秘密鍵から生成されるメンバ証拠の一部を追跡用公開鍵により暗号化した暗号文を含むグループ署名が入力されると、前記グループ署名が前記メッセージに対する正当なグループ署名であるかを判断して、「正当」あるいは「不当」を出力する。【００３０】
この場合、前記暗号文に暗号化されたメンバ証拠の一部を生成する為に用いた秘密鍵と、この秘密鍵に対する署名がグループ署名装置に入力されたデータとグループ署名装置に含まれるデータとから計算できることを証明するデータである知識の証明文であることを検証する知識の証明文検証装置を備え、
前記グループ署名が前記証明文検証装置により検証された知識の証明文を含むこととしてもよい。【００３１】
また、前記グループ署名が、前記暗号文と、前記コミットメントと、前記レスポンスとからなり、
前記知識の証明文検証装置が、
前記グループ公開鍵と、前記追跡用公開鍵と、前記暗号文と、前記コミットメントとが入力され、これらの値のハッシュ値を挑戦値として出力する挑戦値生成装置と、
前記グループ公開鍵と、前記追跡用公開鍵と、前記暗号文と、前記コミットメントと、前記挑戦値と、前記レスポンスとが入力され、これらの入力がある式を満たすかどうかに応じて正当又は不当を出力するレスポンス検証装置と、からなり、レスポンス検証装置の出力をグループ署名検証装置の出力として出力するとしてもよい。【００３２】
さらに、前記グループ署名が、前記暗号文と、前記挑戦値と、前記レスポンスとからなり、
前記知識の証明文検証装置が、
前記グループ公開鍵と、前記追跡用公開鍵と、前記レスポンスと、前記挑戦値と、が入力され、暗号化のコミットメントとメンバ証明書のコミットメントをコミットメントとして出力するコミットメント生成装置と、
前記グループ公開鍵と、前記追跡用公開鍵と、前記暗号文、前記コミットメントが入力され、これらの値のハッシュ値が前記挑戦値に一致するかどうかに応じて正当又は不当を出力するレスポンス検証装置と、からなり、
前記レスポンス検証装置の出力をグループ署名検証装置の出力として出力するとしてもよい。【００３４】
本発明のグループ署名システムは、グループ公開鍵と乱数とが入力され、メンバ証明書発行装置と通信することによりメンバ証明書とメンバ秘密鍵とを出力するメンバ証明書獲得装置であって、位数が同じである群１、群２、群Ｔ、群Ｅの４個の群に対する記述と、群１と群２から群Ｔへの双線形写像の記述と、群１、群２、群Ｔ、群Ｅの各生成子と、前記群１、前記群２、前記群Ｔを用いた署名方式の署名公開鍵とが含まれる前記グループ公開鍵が入力されると、前記位数以下の整数を含む前記メンバ秘密鍵と、前記群Ｅの前記生成子に前記メンバ秘密鍵を乗じた値であるメンバ証拠と、前記群１あるいは群２の前記生成子に前記メンバ秘密鍵を乗じた値である前記群１あるいは群２の要素と、を前記メンバ証明書発行装置に送信し、その後、前記メンバ証明書発行装置より前記署名公開鍵で検証可能な、前記メンバ秘密鍵に対する署名を受信すると、該署名を前記メンバ証明書とすることを特徴とし、特に群Ｅが群１、群２、群Ｔ、とは異なる群で、ディフィヘルマン判別問題を解くことが困難であることを特徴とするメンバ証明書獲得装置と、
グループ公開鍵とグループ秘密鍵と乱数とが入力され、メンバ証明書獲得装置と通信することによりメンバを識別するために使うメンバ証拠を出力するメンバ証明書発行装置であって、位数が同じである群１、群２、群Ｔ、群Ｅの４個の群に対する記述と、群１と群２から群Ｔへの双線形写像の記述と、群１、群２、群Ｔ、群Ｅの各生成子と、前記群１、前記群２、前記群Ｔを用いた署名方式の署名公開鍵とが含まれた前記グループ公開鍵と、前記群１、前記群２、前記群Ｔを用いた署名方式の前記署名公開鍵に対応する署名秘密鍵と、が含まれた前記グループ秘密鍵と、が入力され、前記メンバ証明書獲得装置より前記群Ｅの前記生成子にメンバ秘密鍵を乗じた値であるメンバ証拠と、前記群１あるいは群２の前記生成子にメンバ秘密鍵を乗じた値である前記群１あるいは群２の要素と、受信すると、前記署名秘密鍵を用いて前記メンバ秘密鍵に対する署名を生成し、該署名を前記メンバ証明書としてメンバ証明書獲得装置に送信することを特徴とし、特に群Ｅが群１、群２、群Ｔとは異なる群で、ディフィヘルマン判別問題を解くことが困難であることを特徴とするメンバ証明書発行装置と、
上記のグループ署名装置と、
上記のグループ署名検証装置と、
グループ公開鍵と、追跡用公開鍵と、グループ署名と、追跡用秘密鍵と、が入力され、グループ署名に含まれているメンバ秘密鍵から生成されたメンバ証拠の一部の暗号文を復号してメンバ秘密鍵から一意的に決定される値であるメンバ証拠の一部を出力する追跡装置とからなるグループ署名システムであって、
前記メンバ証明書獲得装置が前記メンバ証明書発行装置と通信することでメンバ証明書とメンバ秘密鍵を獲得し、獲得した前記メンバ証明書と獲得した前記メンバ秘密鍵とメッセージとグループ公開鍵と追跡用公開鍵とを前記グループ署名装置に入力し、前記メッセージに対するグループ署名を獲得し、前記メッセージと獲得した前記グループ署名を前記グループ署名検証装置に入力し、前記獲得した前記グループ署名が前記メッセージに対する正当なグループ署名であることを検証するとともに、前記グループ署名を前記追跡装置に入力してグループ署名を生成したメンバを表すメンバ証拠を出力することを特徴とする。
【００３５】
本発明方式では、第一の問題点を解決するため、群1、群2、群Tの他に、双線形写像が存在しない群Tを用いて、この群上でElGamal暗号文を、上述した文献で使われた暗号文の代りに用いる。このようなElGamal暗号文の安全性は、ディフィヘルマン判別問題を解くことの難しさに依存している。この問題を解く方法は長い間研究されており、現在のところ十分に難しいと考えることは妥当である.
第二の問題点を解決するため、本発明方式では、先に述べた暗号文を、単なるElGamal暗号文ではなく、選択暗号文攻撃に対しても安全なElGamal型暗号文を用いる。【００３６】
第三の問題点に関しては、上記二つの問題を解決する方法を採用したところ、本発明のグループ署名方法は、従来技術よりより効率的なものとなった。
【発明の効果】
【００３７】
本発明によれば、安全性の根拠が線形-ディフィヘルマン判別問題を解くことが難しいという仮定に依拠しない。また、一般群模型(generic group model)にも依拠しない。これらから、より安全なグループ署名を生成, 検証することができる。【００３８】
本発明におけるグループ署名装置と、グループ署名検証装置が必要とする計算量、署名長を、従来の技術と比較してみると以下の通りとなる。【００３９】
本発明では、グループ署名装置が必要とする、群Eあるいは群1,群2上でのスカラー倍、群Tでの冪乗剰余算、双線形写像の計算は、それぞれ、7,4,1個、検証装置のそれらは、6,5,2個である。また、署名長はpの長さの１０倍となる。【００４０】
従来方法では、グループ署名装置が必要とする、群Eあるいは群1,群2上でのスカラー倍、群Tでの冪乗剰余算、双線形写像の計算は、それぞれ、13,4,1個、検証装置のそれらは、12,5,2個である。また、署名長はpの長さの１２倍となる。【００４１】
以上、具体的に示したように本発明は従来の方法より効率的なものとなっている。
【図面の簡単な説明】
【００４２】
【図１】本発明の実施の形態１におけるメンバ証明書獲得装置の構成を示す図である。
【図２】本発明の実施の形態２におけるメンバ証明書発行装置の構成を示す図である。
【図３】本発明の実施の形態３におけるグループ署名装置の構成を示す図である。
【図４】本発明の実施の形態４におけるグループ署名装置の構成を示す図である。
【図５】本発明の実施の形態５におけるグループ署名検証装置の構成を示す図である。
【図６】本発明の実施の形態６におけるグループ署名検証装置の構成を示す図である。
【図７】本発明の実施の形態７における追跡装置の構成を示す図である。
【図８】本発明の実施の形態８におけるグループ署名システムの構成を示す図である。
【符号の説明】
【００４３】
１００  メンバ証明獲得装置
１０１    グループ公開鍵
１０２    乱数
１０３    メンバ証拠生成装置
１０４    メンバ証拠
１０７    メンバ秘密鍵
１０８    コミットメント生成装置
１０９    コミットメント
１１１    チャレンジ獲得装置
１１２    挑戦値
１１３    レスポンス生成装置
１１４    レスポンス
１１６    メンバ証明書源
１１７    メンバ証明書源検証装置
１１９    メンバ証明書
２００    メンバ証明書発行装置
２０９    グループ秘密鍵
２１０    メンバ秘密鍵
２０２    メンバ証拠獲得装置
２０５    チャレンジ生成装置
２０７    レスポンス検証装置
２０８    メンバ証明書源生成装置
３００    グループ署名装置
３０１    追跡用公開鍵
３０２    メッセージ
３０３    乱数
３１３    グループ署名
３０３    群Eを用いた暗号化装置
３０４    メンバ証拠暗号文
３０６    コミットメント生成装置
３０７    コミットメント
３０８    挑戦値生成装置
３０９    挑戦値
３１０    レスポンス生成装置
３１１    レスポンス
３１２    グループ署名出力装置
５００    グループ署名検証装置
５０２    コミットメント生成装置
５０３    コミットメント
５０４    挑戦値生成装置
５０５    挑戦値
５０６    レスポンス装置
７００    追跡装置
７０１    追跡用秘密鍵
７０２    乱数
７０３    群Eを用いた復号装置
７０４    メンバ証拠の一部
７０４’    メンバ証拠
７０６    コミットメント生成装置
７０７    コミットメント
７０８    挑戦値生成装置
７０９    挑戦値
７１０    レスポンス生成装置
７１１    レスポンス
７１２    出力装置
７１３    復号正当性証明
【発明を実施するための最良の形態】
【００４４】
本発明の一実施形態について図面を参照して詳細に説明する。【００４５】
最初に前提となることを説明する。
pは素数とする。
群1と群2と群Tと群Eをそれぞれ位数p群とする。
群1と群2から群Tへの双線形写像eが存在するとする。
群Eは、素体上の乗法群や、一般の楕円曲線等でディフィヘルマン判別問題を解くことが困難な群とする。
群2から群1への同型写像φとする。
文字列を体(Z/pZ)へと写像するハッシュ関数Hashとする。
G2は群2の生成子、G1はφ(G2=G1なる群1の生成子とする。
Gは群Eの生成子とする。
H,Kを無作為に選ばれた群1の元とする。
γを無作為に選ばれた体Z/pZの元とする。
Y=[γ]G2とする。
sとtを無作為に選ばれた体Z/pZ上の2点とする。
SとTをS=[s]G,T=[t]Gとする。
グループ秘密鍵をγとする。
グループ公開鍵を、pと、群1,群2,群T,双線形写像e,同型写像φ,ハッシュ関数Hashと、を記述する文字列と、G1,G2,G,H,K,Yとする。
追跡用秘密鍵を、(s,t)とする。
追跡用の公開鍵を、(S,T)とする。【００４６】
［実施の形態１］
［メンバー証明書獲得装置１００］
図１は本発明によるメンバ証明書獲得装置１００の構成を示すブロック図である。【００４７】
メンバ証明書獲得装置１００はメンバ証明書発行装置２００と送受信し、グループ公開鍵１０１および乱数１０２を入力し、メンバ秘密鍵１０７およびメンバ証明書１１９を出力するもので、メンバ証拠生成装置１０３、コミットメント生成装置１０８、チャレンジ獲得装置１１１、レスポンス生成装置１１３、メンバ証明書源検証装置１１７から構成されている。メンバ証明書獲得装置１００は、メンバ証明書発行装置２００との通信の過程で、メンバ証拠１０４とコミットメント１０９とレスポンス１１４とをメンバ証明書発行装置２００に送付し、挑戦値１１２とメンバ証明書源１１６とを受信する。【００４８】
なお、メンバ証明書獲得装置１００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、メンバ証拠１０４、メンバ秘密鍵１０７、コミットメント１０９、挑戦値１１２、レスポンス１１４、メンバ証明書源１１６は記憶部内に設定される、また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の構成要件のうち、コミットメント生成装置１０８、コミットメント１０９、チャレンジ獲得装置１１１、挑戦値１１２、レスポンス生成装置１１３、レスポンス１１４により、以下に説明する手続１０６が行なわれる。【００４９】
メンバー証明書獲得装置１００には、グループ公開鍵１０１と乱数１０２とが入力される。メンバ証拠生成装置１０３は入力された乱数１０２よりメンバ秘密鍵１０７（xU）を体(Z/pZ)よりランダムに選び、続いて、
xUより、
QU=[xU]G
HU= [xU]H+[z'U]K
を生成する。これをメンバ証拠１０４と呼ばれ、(QU,HU)はメンバ証明書発行装置２００に送られる。【００５０】
以下の手続き１０６により、二式、
QU= [xU]G
HU= [xU]H+[z'U]K
を満たす(xU,z'U)の知識をメンバ証明書発行装置に対して証明する。【００５１】
［手続き１０６始め］
コミットメント生成装置１０８は入力された乱数１０２より、x'U,z'を体(Z/pZ)よりランダムに選び、以下の内容のコミットメント１０９を生成し、メンバ証明書発行装置２００に送る。
Q'U=[x'_U]G
H'U=[x'_U]H+[z']K
この後、メンバ証明書獲得装置１００はメンバ証明書発行装置２００より、体Z/pZの元である挑戦値１１２（cU）が送られるのを待つ。【００５２】
挑戦値１１２（cU）を受信したならば、レスポンス生成装置１１３は以下のレスポンス１１４を計算し、メンバ証明書発行装置２００に送る。
rU=cUxU+x'U
sU= cUz'U+z'
［手続き１０６終わり］
この後、メンバ証明書獲得装置１００はメンバ証明書発行装置２００より、以下の内容のメンバ証明書源１１６が送られてくるのを待つ。
yU∈Z/pZ,
z''U∈Z/pZ,
AU∈群1,
上の値を受信したならば、メンバ証明書源検証装置１１７は、
zU=z'U+z''U
を計算し、
e(AU,Y+[yU]G2)・e([xU]H,G2)・e([zU]K,G2)=e(G1,G2)
が成り立つことを確認した後に、(AU,yU,zU)をメンバ証明書１１９とし、xUをメンバ秘密鍵１０７として出力する。【００５３】
［実施の形態２］
［メンバー証明書発行装置２００］
図２は本発明によるメンバー証明書発行装置２００の構成を示すブロック図である。【００５４】
メンバ証明書発行装置２００はメンバー証明書獲得装置１００と送受信し、グループ公開鍵１０１、乱数１０２およびグループ秘密鍵２０９を入力し、メンバ証拠１０４を出力するもので、チャレンジ生成装置２０５、レスポンス検証装置２０７、メンバ証明書源生成装置２０８、メンバ証拠獲得装置２０２から構成されている。メンバ証明書発行装置２００は、メンバ証明書獲得装置１００との通信の過程で、挑戦値１１２とメンバ証明書源１１６とをメンバ証明書獲得装置１００に送付し、メンバ証拠１０４とコミットメント１０９とレスポンス１１４とを受信する。【００５５】
なお、メンバ証明書発行装置２００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、メンバ証拠１０４、コミットメント１０９、挑戦値１１２、レスポンス１１４、メンバ証明書源１１６は記憶部内に設定される、また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の構成要件のうち、コミットメント１０９、挑戦値１１２、レスポンス１１４、メンバ証明書源１１６、チャレンジ生成装置２０５、レスポンス検証装置２０７、メンバ証明書源生成装置２０８により、以下に説明する手続２０３が行なわれる。【００５６】
メンバ証明書発行装置２００には、グループ公開鍵１０１と、グループ秘密鍵２０９と、乱数２０１とが入力され、動作開始となると、メンバ証拠１０４(QU,HU)∈(群E,群1)がメンバ証明書獲得装置100より送られるのを待つ。【００５７】
メンバ証拠１０４がメンバ証明書獲得装置１００より送られてくると、手続き２０３により、以下の二式を満たすxU,z'Uの知識をメンバ証明書獲得装置２０２が保持していることを検証する。
QU=[xU]G
HU=[xU]H+[z'U]K
［手続き２０３始め］
チャレンジ生成装置２０５は、コミットメント１０９（(Q'U,H'U)∈(群E,群1)）がメンバ証明書獲得装置１００より送られてくるのを待つ。【００５８】
コミットメント１０９が送られてきたならば、チャレンジ生成装置２０５は、入力された乱数２０１より、挑戦値１１２（cU）を体(Z/pZ)よりランダムに選び、メンバ証明書獲得装置１００に送付する。【００５９】
この後、レスポンス１１４（(rU,sU)∈(Z/pZ)2)がメンバ証明書獲得装置１００より送られてくると、レスポンス検証装置２０７は、
[rU]G=[cU]QU+Q'U
[rU]H+[sU]K=[cU]HU+H'U
が成り立つことを確認する。【００６０】
［手続き２０３終わり］
メンバ証明書源生成装置２０８は、入力された乱数より、(yU,z''U)∈(Z/pZ,Z/pZ)を選び、,AU=[1/(γ+yU)](G1-HU-[z''U]Kを生成し、(AU,yU,z''U)をメンバー証明書源１１６として、メンバー証明書獲得装置１００に送る。
メンバ証拠１０４(QU)を出力する。【００６１】
［実施の形態３］
［グループ署名装置３００］
図３は本発明によるグループ署名装置３００の構成を示すブロック図である。【００６２】
グループ署名装置３００は、グループ公開鍵１０１、メンバ秘密鍵１０７、メンバ証明書１１６、追跡用公開鍵３０１、メッセージ３０２、乱数３０３を入力し、グループ署名３１３を出力するもので、群Eを用いた暗号化装置３０３、メンバ証拠暗号文３０４、コミットメント生成装置３０６、コミットメント３０７、挑戦値生成装置３０８、挑戦値３０９、レスポンス生成装置３１０、レスポンス３１１、グループ署名出力装置３１２から構成されている。【００６３】
なお、グループ署名装置３００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、メンバ証拠暗号文３０４、コミットメント３０７、挑戦値３０９、レスポンス３１１は記憶部内に設定される、また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の構成要件のうち、コミットメント生成装置３０６、コミットメント３０７、挑戦値生成装置３０８、挑戦値３０９、レスポンス生成装置３１０、レスポンス３１１により、知識の証明文生成装置３０５が構成されている。【００６４】
グループ署名装置３００には、グループ公開鍵１０１と、追跡用公開鍵３０１と、メンバ証明書１１６と、メンバ秘密鍵１０７と、メッセージ３０２（m）と、乱数３０３とが入力される。【００６５】
群Eを用いた暗号化装置３０３は、体Z/pZよりq,rをランダムに選び、以下の内容の暗号文３０４を生成する。
B=AU+[q]K
U=[xU+r]G
V=[r]S
W=[r]T
続いて、知識の証明文生成装置３０５で以下の処理を行う。この処理は、(AU,yU,zU,xU,q,r)の知識の証明である。【００６６】
［知識の証明文生成始め］
コミットメント生成装置３０６を用いて、体Z/pZよりt,u,v,w,oをランダムに選び、
X'=e(H,G2)^t・e(B,G2)^u・e(K,G2)^v・e(K,Y)^w
U'=[t+o]G
V'=[o]S
W'=[o]T
を生成し、(X',U',V',W')をコミットメント３０７とする。【００６７】
続いて、挑戦値生成装置３０８を用いて、以下の内容の挑戦値３０９を生成する。
c=Hash(p,G_1,G_2,G_T,G,ψ,Y,S,T,H,K,B,U,V,W,X',V',W',U',m)
次に、レスポンス生成装置３１０を用いて、
x'=cxU+t
y'=cyU+u
z'=c(zU-qyU)+v
q'=-cq+w
r'=cr+o
を生成し、(x,y',z',q',r')をレスポンス３１１とする。【００６８】
［知識の証明文生成終わり］
グループ署名装置３００は、(B,U,V,W,c,x',y',z',q',r')をメッセージmに対するグループ署名３１３としてグループ署名出力装置３１２より出力する。【００６９】
［実施の形態４］
［グループ署名装置４００］
図４は本発明によるグループ署名装置４００の構成を示すブロック図である。【００７０】
グループ署名装置４００は、図３に示したグループ署名装置３００と同様の構成の装置であり、出力するグループ署名がコミットメントを含む(B,U,V,W,X',U',V',W',x',y',z',q',r')
である点のみが異なる。【００７１】
［実施の形態５］
［グループ署名検証装置５００］
図５は本発明によるグループ署名検証装置５００の構成を示すブロック図である。【００７２】
グループ署名検証装置５００は、グループ公開鍵１０１、追跡用公開鍵３０１、メッセージ３０２、グループ署名３１３を入力し、正当／不当５０７を出力するもので、コミットメント生成装置５０２、コミットメント５０３、挑戦値生成装置５０４、挑戦値５０５、レスポンス装置５０６から構成されている。【００７３】
なお、グループ署名検証装置５００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、コミットメント５０３、挑戦値５０５は記憶部内に設定される、また、これら以外の装置もコンピュータシステム内に仮想的に構成される。【００７４】
グループ署名検証装置５００には、グループ公開鍵１０１と、追跡用公開鍵３０１と、メッセージ３０２（m）と、グループ署名313(B,U,V,W,c,x',y',z',q',r')とが入力される。【００７５】
コミットメント生成装置５０２は、以下の内容のコミットメント５０３(X',U',V',W')を生成する。
X'=e(H,G2)^(x')e(B,G2)^(y')e(K,G2)^(z')e(K,Y)^(q')(e(G1,G2)/e(B,Y))^(c)
U'=[x'+r']G-[c]U
V'=[r']S-[c]V
W'=[r']T-[c]W
挑戦値生成装置５０４は、以下の内容の挑戦値５０５を計算する。
c'=Hash(p,G_1,G_2,G_T,G,ψ,Y,S,T,H,K,B,U,V,W,X',V',W',U',m)
レスポンス装置５０６は、挑戦値生成装置５０４が生成した挑戦値c'がグループ署名に含まれるcに一致するかを確認し、一致すれば正当／不当５０７の出力として「正当」を出力し、一致しなければ「不当」を出力する。【００７６】
［実施の形態６］
［グループ署名検証装置６００］
図６は本発明によるグループ署名検証装置６００の構成を示すブロック図である。【００７７】
グループ署名検証装置６００は、グループ公開鍵１０１、追跡用公開鍵３０１、メッセージ３０２、グループ署名３１３を入力し、正当／不当６０５を出力するもので、コミットメント６０１、挑戦値生成装置６０２、挑戦値６０３、レスポンス装置６０４から構成されている。コミットメント６０１、挑戦値生成装置６０２、挑戦値６０３、レスポンス装置６０４は図５に示したコミットメント５０３、挑戦値生成装置５０４、挑戦値５０５、レスポンス装置５０６と同様のものである。【００７８】
グループ署名検証装置６００が図５に示したグループ署名検証装置５００と異なる点は、入力されるグループ署名が(B,U,V,W,X',U',V',W',x',y',z',q',r')であることと、コミットメント生成装置を用いずに、グループ署名に含まれる(X',U',V',W')をコミットメント６０１とすることと、レスポンス装置６０４が挑戦値生成装置６０２を用いて生成した挑戦値６０３（c'）を用いて、
X'=e(H,G2)^(x')e(B,G2)^(y')e(K,G2)^(z')e(K,Y)^(q')(e(G1,G2)/e(B,Y))^(c')
U'=[x'+r']G-[c']U
V'=[r']S-[c']V
W'=[r']T-[c']W
が全てなり立てば、正当／不当６０５の出力として「正当」を出力し、一つでも成り立たなければ「不当」を出力することである。【００７９】
［実施の形態７］
［追跡装置７００］
図７は本発明による追跡装置７００の構成を示すブロック図である。【００８０】
追跡装置７００は、グループ公開鍵１０１、追跡用公開鍵３０１、メッセージ３０２、グループ署名３１３、追跡用秘密鍵７０１、乱数７０２を入力し、メンバ証拠７０４’、復号正当性証明７１３を出力するもので、群Eを用いた復号装置７０３、メンバ証拠の一部７０４、コミットメント生成装置７０６、コミットメント７０７、挑戦値生成装置７０８、挑戦値７０９、レスポンス生成装置７１０、レスポンス７１１、出力装置７１２から構成されている。【００８１】
なお、追跡装置７００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、メンバ証拠の一部７０４、コミットメント７０７、挑戦値７０９、レスポンス７１１は記憶部内に設定される、また、これら以外の装置もコンピュータシステム内に仮想的に構成される。【００８２】
また、上記の構成要件のうち、コミットメント生成装置７０６、コミットメント７０７、挑戦値生成装置７０８、挑戦値７０９、レスポンス生成装置７１０、レスポンス７１１により、復号照明装置７０５が構成されている。【００８３】
追跡装置７００には、グループ公開鍵１０１と、追跡用公開鍵３０１と、追跡用秘密鍵７０１と、メッセージ３０２（m）と、グループ署名313(B,U,V,W,c,x',y',z',q',r')と、乱数７０２とが入力される。【００８４】
群Eを用いた復号装置７０３は、メンバ証拠の一部の暗号文と追跡用秘密鍵７０１から以下の内容のメンバ証拠の一部704を生成する。
Q=U-[1/s]V
コミットメント生成装置７０６は、乱数７０２を用いて体Z/pZの元rを選び、以下の内容のコミットメント７０７を生成する。
V''=[r]V
G''=[r]G
挑戦値生成装置７０８は以下の内容の挑戦値７０９を生成する。
c''=Hash(p,G_1,G_2,G_T,G,ψ,Y,S,T,H,K,B,U,V,W,X',V',W',U',m,V'',G'')
レスポンス生成装置７１０は以下の内容のレスポンス７１１を生成する。
r''=c''/s+r
出力装置７１２は(V'',G'',r'')を復号正当性証明７１３とし、メンバ証拠の一部７０４（Q）をメンバ証拠７０４’として出力する。【００８５】
［実施の形態８］
［グループ署名システム８００］
図８は本発明によるグループ署名システム８００の構成を示すブロック図である。【００８６】
本実施例は、図１に示したメンバ証明書獲得装置１００、図２に示したメンバ証明書発行装置２００、図３に示したグループ署名装置３００、図５に示したグループ署名検証装置５００、図７に示した追跡装置７００からなるシステムである。グループ署名装置３００は図４に示したグループ署名装置４００としてもよく、また、グループ署名検証装置５００は図６に示したグループ署名検証装置６００としてもよい。【００８７】
メンバ証明書獲得装置１００がメンバ証明書発行装置２００と通信することで、メンバ証明書１１６とメンバ秘密鍵１０７とを獲得する。【００８８】
グループ署名装置３００には、メッセージ３０２、グループ公開鍵１０１、追跡用公開鍵３０１とともに、メンバ証明書獲得装置１００が獲得したメンバ証明書１１６と獲得したメンバ秘密鍵１０７とが入力され、グループ署名装置３００はメッセージ３０２に対するグループ署名３１３を出力する。【００８９】
グループ署名検証装置５００には、メッセージ３０２、グループ公開鍵１０１、追跡用公開鍵３０１、メッセージ３０２、グループ署名３１３とが入力され、グループ署名検証装置５００はグループ署名３１３がメッセージに対する正当なグループ署名であるかを検証し、その結果を示す正当／不当６０５を出力する。【００９０】
追跡装置７００には、追跡用公開鍵３０１、グループ署名３１３、追跡用秘密鍵７０１が入力され、追跡装置７００はグループ署名を生成したメンバを表すメンバ証拠７０４を出力する。
【図１】
0004872908.tif 000002
【図２】
0004872908.tif 000003
【図３】
0004872908.tif 000004
【図４】
0004872908.tif 000005
【図５】
0004872908.tif 000006
【図６】
0004872908.tif 000007
【図７】
0004872908.tif 000008
【図８】
0004872908.tif 000009