(57)【要約】      （修正有）【課題】被認証者装置のユーザが特定のグループに属するか否かを正確に認証判定する。【解決手段】被認証者装置２０から送り込まれた認証用データから暗号文を抽出すると共に、ユーザ装置により指定された検証補助装置４０に対して暗号文を転送する検証装置３０と、予め設定されたメンバリストにユーザ識別子が含まれる場合に、秘密鍵に対応して予め設定された公開鍵を利用して復号されたユーザ署名の検証を行い、この検証の結果を検証装置３０に対して通知する検証補助装置４０を備えた匿名認証システムであって、検証装置３０は検証補助装置４０から送り込まれたユーザ署名の検証結果が全て受理を示す場合に認証要求に対する認証成功を提示する。【選択図】図１
2012032952.tif 000002
【特許請求の範囲】
【請求項１】
ユーザ装置からの要求に応じてユーザ登録を行うと共に当該登録ユーザのグループをメンバリストにより管理するグループ管理装置と、前記ユーザ装置から送り込まれた認証用データに対するユーザ認証判定を行う認証検証装置と、前記メンバリストに基づき前記ユーザ装置の特定を行うユーザ特定装置と、前記ユーザ認証判定に先立ち前記認証検証装置からの要求に応じて前記認証用データの検証を行う検証補助装置とを備えた匿名認証システムであって、
前記ユーザ装置は、
前記認証検証装置から送り込まれた認証開始応答を予め設定された秘密鍵を利用することによりユーザ署名を生成するユーザ署名生成部と、
自己であるユーザ特定装置を特定する処理を行う前記ユーザ特定装置と前記検証補助装置とをそれぞれ選択指定すると共に、当該選択指定されたユーザ特定装置および検証補助装置を示す特定装置指定情報を生成する特定装置指定部と、
前記グループに対応して設定されたグループ用暗号化鍵を利用して前記ユーザ識別子およびユーザ署名を暗号化した暗号文を生成すると共に当該暗号文および前記特定装置指定情報を含むデータを前記認証用データとして前記認証検証装置に送信する認証用データ生成送信部とを備え、
前記認証検証装置は、
前記認証用データから前記暗号文を抽出すると共に当該暗号文を前記特定装置指定情報に基づき前記選択指定された検証補助装置に対して転送する暗号文転送部と、
前記ユーザ装置を特定する必要が生じた場合に、前記特定装置指定情報で指定された前記ユーザ特定装置に対して利用者特定要求として送信する利用者特定要求部と、
前記検証補助装置から送り込まれた前記検証結果に基き前記ユーザ認証判定を行う認証判定部とを備え、
前記ユーザ特定装置は、
前記利用者特定要求に応じて前記ユーザ装置を特定し前記ユーザ装置を示すユーザ装置特定情報を前記認証検証装置に通知するユーザ装置特定通知機能を備え、
前記検証補助装置は、
予め設定された前記グループ用復号鍵を利用して前記暗号文を前記ユーザ署名およびユーザ識別子に復号する暗号文復号部と、
前記グループ管理装置から取得した前記メンバリストに前記ユーザ識別子が含まれる場合に、前記秘密鍵に対応して設定された公開鍵を利用して前記復号されたユーザ署名の検証を行うユーザ署名検証部とを備えたことを特徴とする匿名認証システム。
【請求項２】
請求項１に記載の匿名認証システムにおいて、
前記前記認証検証装置の暗号文転送部は、前記ユーザ装置により選択指定された異なる複数の検証補助装置それぞれに対して前記暗号文を転送する複数転送機能を備え、
前記認証判定部は、前記異なる複数の検証補助装置それぞれから送り込まれた前記検証結果が全て検証成功を示す場合に前記ユーザ装置に対するユーザ認証判定の結果として認証成功を通知する判定成功通知機能を備えたことを特徴とした匿名認証システム。
【請求項３】
請求項１に記載の匿名認証システムにおいて、
前記認証検証装置が、前記特定装置指定情報により指定された異なる複数の前記ユーザ特定装置に対して前記利用者特定要求を送信した場合に、前記利用者特定要求を受信したユーザ特定装置は、前記メンバリストに前記ユーザ識別子が含まれるか否かを判定するメンバリスト判定部と、
前記メンバリストに前記ユーザ識別子が含まれる場合に、公開鍵を利用して前記ユーザ署名の検証を行うユーザ特定処理部と、
前記利用者特定要求を受信した他のユーザ特定装置と前記ユーザ署名の検証成功を相互に認証した場合に、前記認証用データの作成者としての前記ユーザ装置の識別子を前記認証検証装置に通知する特定情報通知部とを備えたことを特徴とする匿名認証システム。
【請求項４】
請求項２に記載の匿名認証システムにおいて、
前記検証補助装置は、グループ用復号鍵を用いて前記認証用データに含まれる暗号文を復号することにより前記認証用データに対応するＩＤおよび署名データを特定するＩＤ署名データ特定機能と、
前記グループ管理装置から取得したメンバリストに前記ＩＤおよび署名データが含まれるか否かの検証を行う検証判定機能とを備えたことを特徴とする匿名認証システム。
【請求項５】
請求項１、２、又は３に記載の匿名認証システムにおいて、
前記認証検証装置は、前記ユーザ装置から一定回数以上の認証要求があった場合に、当該認証要求の送信元が秘匿された認証用データを生成する認証要求元秘匿機能を備えたことを特徴とする匿名認証システム。
【請求項６】
請求項４に記載の匿名認証システムにおいて、
前記認証検証装置から前記認証用データが転送された場合に、当該認証用データを復号することによりＩＤおよび署名データを特定し、前記認証用データ生成したユーザが前記グループに属するか否かを前記グループ管理装置から取得した前記メンバリストと前記ＩＤおよび署名データとに基づき検証する認証補助装置を備えたことを特徴とする匿名認証システム。
【請求項７】
ユーザ装置からの要求に応じてユーザ登録を行うと共に当該登録ユーザのグループをメンバリストにより管理するグループ管理装置と、前記ユーザ装置から送り込まれた認証用データに対するユーザ認証判定を行う認証検証装置と、前記ユーザ認証判定に先立ち前記認証検証装置からの要求に応じて前記認証用データの検証を行う検証補助装置とを備えた匿名認証システムにあって、前記ユーザ装置の認証を行う匿名認証方法であって、
前記ユーザ装置が、前記認証検証装置から送り込まれた認証開始応答を予め設定された秘密鍵を利用することによりユーザ署名を生成し、
前記グループに対応するグループ用暗号化鍵を利用して前記ユーザ識別子およびユーザ署名を暗号化した暗号文を生成すると共に、
前記１または複数の検証補助装置をそれぞれ選択指定することにより当該選択指定された検証補助装置を示す特定装置指定情報を生成し、
前記暗号文および前記特定装置指定情報を含む前記認証用データを前記認証検証装置に送信し、
前記認証検証装置は、前記ユーザ装置から送り込まれた前記認証用データから前記暗号文を抽出すると共に、前記特定装置指定情報に基づき前記ユーザ装置が指定した検証補助装置に対して前記暗号文を転送し、
前記検証補助装置は、予め設定された前記グループ用復号鍵を利用して前記暗号文を前記ユーザ署名およびユーザ識別子に復号し、
前記グループ管理装置から取得した前記メンバリストに前記ユーザ識別子が含まれる場合に、前記秘密鍵に対応して予め設定された公開鍵を利用して前記復号されたユーザ署名の検証を行うと共に当該検証結果を前記認証検証装置に対して通知し、
前記認証検証装置が、前記検証補助装置から送り込まれた前記ユーザ署名の検証結果に基き前記ユーザ認証判定を行うことを特徴とした匿名認証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、被認証者のグループ所属に係る認証を行う認証システムに関し、特に、被認証者の匿名性を確保しつつ認証処理を行う匿名認証システムに関する。
【背景技術】
【０００２】
ネットワークセキュリティの重要性が広く認識されている。セキュリティを実現するために、ネットワーク上の様々な認証サービスでは、特定の人に対してのみ許容されたサービスを会員にだけ提供される構成となっている。このため、これらのサービスにおいては、サービスの利用に際してサービス利用者が会員であるか否かについて、個人認証が行われる。
【０００３】
しかしながら、個人認証に係り各サービス利用者のネットワーク利用履歴などが収拾された場合、各サービス利用者がいつ、どこで、どのようなネットワークサービスを利用したかといった、個人のプライバシーに係る情報が被認証者の同意なく収集され、更には、この情報が漏洩されてしまうといった不都合が生じ得る。
【０００４】
このため、特定のグループに所属する被認証者の匿名性を高めるための施策として、例えば、サービスの会員全員に共通のＩＤとパスワードを発行し個人認証を行うといった手法が利用されている。
この手法では、会員全員が同一のＩＤとパスワードを用いて認証を行うため、個人が特定されることなく、認証処理を行うことが可能である。
しかしながら、会員のうちの誰かが、会員以外の人にパスワードを漏らしてしまった場合、会員にだけサービスを提供するためには、パスワードを再発行し、会員全員に新規のパスワードを伝えなくてはならず、そのための手間、工数、そして時間が膨大にかかってしまうといった不都合がある。
また、被認証者の振る舞いが規約などによって個人を特定するための行為であったとしても、管理者は被認証者を特定することができないといった不都合が生じ得る。
【０００５】
これに対して、被認証者の匿名性を保ちつつ、管理者が必要に応じて被認証者を特定又は除外することができ、さらには、複数回の認証要求に対して、それが同一の被認証者による要求行為であるか、異なる被認証者による要求行為であるかを誰でも判別することが可能な匿名認証方式が開示されている（特許文献１）。
【０００６】
また、この関連技術として、複数回の認証要求に対しそれらが同一の被認証者による認証要求行為であるか異なる被認証者による認証要求行為であるかを識別することなく、グループ署名を用いて、管理者による会員のなりすましを抑制しつつ、非認証者の認証処理を行う認証方式が開示されている（非特許文献１，２）。
【０００７】
また、上記非特許文献１および２の内容では、グループ内における被認証者を特定する処理を行うために、グループに属するメンバーについて、被認証者特定者の分類が行われる。
具体的には、例えば、グループに属するメンバーを課金のための被認証者の特定を行う被認証者特定者、規則に違反した被認証者を特定する被認証者特定者、被認証者の趣向を調査するための被認証者特定者などに分類し、これにより、例えば、自分の趣向を知らせたくない被認証者を、被認証者の趣向を調査するための被認証者特定者としては選択しない設定とすることにより、選択されていない被認証者特定者によって被認証者の特定処理動作が実行されるのを抑制することが可能となる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００６−２３５６６１公報
【非特許文献】
【０００９】
【非特許文献１】J. Camenisch and J. Groth. Group signatures: better efficiency and new theoretical aspects. Forth Int. Conf. on Security in Communication Networks -- SCN 2004, LNCS 3352, Springer, 2005.
【非特許文献２】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.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記特許文献１に記載の匿名認証方式としての営利目的の会員制サービスでは、リピーターに関する情報を管理者が得られるというメリットが考えられる。
しかしながら、この場合、何らかの理由により被認証者の特定が行われた場合には、この被認証者の過去の認証履歴がすべて明らかになってしまうといった不都合があり、更には、会員制サービスの管理者が会員全員のＩＤとパスワードを知っているため、管理者による会員のなりすましを行うことが可能であるという不都合がある。
【００１１】
しかしながら、被認証者特定者が1人によって被認証者を特定することができる構成では、被認証者特定装置によって、不必要に被認証者の特定が行われ、更には、この情報が公開されてしまう不都合が生じ得る。
【００１２】
そのため、例えば、１０人の被認証者特定者のうち６人以上が被認証者の特定用に相互通信を行うことにより相互協調処理を行わなければ被認証者の特定が行えない、などの条件を付けられることが望ましい。このような条件を付けることにより、１０人の被認証者特定者のうち、６人以上が上述の不必要な被認証者の特定に参加しない限り、被認証者の特定が行えなくなる。
【００１３】
また、被認証者の匿名性を確保しつつ、被認証者によって指定された1人以上の被認証者特定者が必要に応じて、匿名性を剥奪でき、更には、複数回の認証に対して、それが同一の被認証者による認証要求行為であるか否か、つまり、別の被認証者の行為であるかを判別されることなく、グループを管理するグループ管理者による会員のなりすまし行為を抑制し、かつ被認証者の認証データ生成に必要な計算コスト（計算負荷）を軽減することができないという不都合がある。
【００１４】
また、認証時にユーザは自らの署名を生成し、自らが指定する複数人の被認証者特定者に対応した複数個のグループの暗号化鍵を用いて、署名を暗号化し、生成された全ての暗号文を認証データとすることにより、上記の問題は解決可能であるが、この方法では、認証データおよび認証データ生成コストが膨大になってしまうという不都合がある。
【００１５】
［発明の目的］
本発明は、上記関連技術の有する不都合を改善し、ユーザ装置の利用者である被認証者の匿名性を確保しつつ被認証者のグループ所属に係る認証判定を確実に行う匿名認証システム、匿名認証方法を提供することを、その目的とする。
【課題を解決するための手段】
【００１６】
上記目的を達成するために、本発明に係る匿名認証システムは、ユーザ装置からの要求に応じてユーザ登録を行うと共に当該登録ユーザのグループをメンバリストにより管理するグループ管理装置と、前記ユーザ装置から送り込まれた認証用データに対するユーザ認証判定を行う認証検証装置と、前記メンバリストに基づき前記ユーザ装置の特定を行うユーザ特定装置と、前記ユーザ認証判定に先立ち前記認証検証装置からの要求に応じて前記認証用データの検証を行う検証補助装置とを備えた匿名認証システムであって、前記ユーザ装置は、前記認証検証装置から送り込まれた認証開始応答を予め設定された秘密鍵を利用することによりユーザ署名を生成するユーザ署名生成部と、自己であるユーザ特定装置を特定する処理を行う前記ユーザ特定装置と前記検証補助装置とをそれぞれ選択指定すると共に、当該選択指定されたユーザ特定装置および検証補助装置を示す特定装置指定情報を生成する特定装置指定部と、前記グループに対応して設定されたグループ用暗号化鍵を利用して前記ユーザ識別子およびユーザ署名を暗号化した暗号文を生成すると共に当該暗号文および前記特定装置指定情報を含むデータを前記認証用データとして前記認証検証装置に送信する認証用データ生成送信部とを備え、前記認証検証装置は、前記認証用データから前記暗号文を抽出すると共に当該暗号文を前記特定装置指定情報に基づき前記選択指定された検証補助装置に対して転送する暗号文転送部と、前記ユーザ装置を特定する必要が生じた場合に、前記特定装置指定情報で指定された前記ユーザ特定装置に対して利用者特定要求として送信する利用者特定要求部と、前記検証補助装置から送り込まれた前記検証結果に基き前記ユーザ認証判定を行う認証判定部とを備え、前記ユーザ特定装置は、前記利用者特定要求に応じて前記ユーザ装置を特定し前記ユーザ装置を示すユーザ装置特定情報を前記認証検証装置に通知するユーザ装置特定通知機能を備え、前記検証補助装置は、予め設定された前記グループ用復号鍵を利用して前記暗号文を前記ユーザ署名およびユーザ識別子に復号する暗号文復号部と、前記グループ管理装置から取得した前記メンバリストに前記ユーザ識別子が含まれる場合に、前記秘密鍵に対応して設定された公開鍵を利用して前記復号されたユーザ署名の検証を行うユーザ署名検証部とを備えた構成を有している。
【００１７】
また、本発明にかかる匿名認証方法は、ユーザ装置からの要求に応じてユーザ登録を行うと共に当該登録ユーザのグループをメンバリストにより管理するグループ管理装置と、前記ユーザ装置から送り込まれた認証用データに対するユーザ認証判定を行う認証検証装置と、前記ユーザ認証判定に先立ち前記認証検証装置からの要求に応じて前記認証用データの検証を行う検証補助装置とを備えた匿名認証システムにあって、前記ユーザ装置の認証を行う匿名認証方法であって、前記ユーザ装置が、前記認証検証装置から送り込まれた認証開始応答を予め設定された秘密鍵を利用することによりユーザ署名を生成し、前記グループに対応するグループ用暗号化鍵を利用して前記ユーザ識別子およびユーザ署名を暗号化した暗号文を生成すると共に、前記１または複数の検証補助装置をそれぞれ選択指定することにより当該選択指定された検証補助装置を示す特定装置指定情報を生成し、前記暗号文および前記特定装置指定情報を含む前記認証用データを前記認証検証装置に送信し、前記認証検証装置は、前記ユーザ装置から送り込まれた前記認証用データから前記暗号文を抽出すると共に、前記特定装置指定情報に基づき前記ユーザ装置が指定した検証補助装置に対して前記暗号文を転送し、前記検証補助装置は、予め設定された前記グループ用復号鍵を利用して前記暗号文を前記ユーザ署名およびユーザ識別子に復号し、前記グループ管理装置から取得した前記メンバリストに前記ユーザ識別子が含まれる場合に、前記秘密鍵に対応して予め設定された公開鍵を利用して前記復号されたユーザ署名の検証を行うと共に当該検証結果を前記認証検証装置に対して通知し、前記認証検証装置が、前記検証補助装置から送り込まれた前記ユーザ署名の検証結果に基き前記ユーザ認証判定を行うことを特徴としている。
【発明の効果】
【００１８】
本発明は、以上のように構成され機能するので、これによると、被認証者の匿名性を確保しつつ、ユーザ装置からの認証要求に応じてユーザ装置が指定した検証補助装置に対して認証要求を転送し、検証補助装置からの検証結果に基き前記認証要求に対する認証判定を行う認証検証装置を備えた構成としたことにより、ユーザ装置の利用者である被認証者の匿名性を確保しつつ被認証者のグループ所属に係る認証判定を正確に行うことを可能とする匿名認証システム、匿名認証方法を提供することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明による匿名認証システムの一実施形態を示す概略ブロック図である。
【図２】図１に開示した匿名認証システムにおけるグループ管理装置の内部構成を示す概略ブロック図である。
【図３】図１に開示した匿名認証システムにおける被認証者装置の内部構成を示す概略ブロック図である。
【図４】図１に開示した匿名認証システムにおける検証装置の内部構成を示す概略ブロック図である。
【図５】図１に開示した匿名認証システムにおける検証補助装置の内部構成を示す概略ブロック図である。
【図６】図１に開示した匿名認証システムにおける被認証者特定装置の内部構成を示す概略ブロック図である。
【図７】図１に開示した匿名認証システムにおけるグループ登録処理の動作処理ステップを示すフローチャートである。
【図８】図１に開示した匿名認証システムにおける認証判定処理の動作処理ステップを示すフローチャートである。
【図９】図１に開示した匿名認証システムにおける被認証者特定処理の動作処理ステップを示すフローチャートである。
【図１０】本発明による匿名認証システムの一実施形態を示す概略ブロック図である。
【図１１】図１０に開示した匿名認証システムにおける被認証者装置の内部構成を示す概略ブロック図である。
【図１２】図１０に開示した匿名認証システムにおける認証補助装置の内部構成を示す概略ブロック図である。
【図１３】図１０に開示した匿名認証システムにおける検証装置の内部構成を示す概略ブロック図である。
【図１４】図１０に開示した匿名認証システムにおける認証判定処理の動作処理ステップを示すフローチャートである。
【図１５】本発明による匿名認証システムの一実施形態を示す概略ブロック図である。
【図１６】図１５に開示した匿名認証システムにおける構成内容を示す概略ブロック図である。
【図１７】図１５に開示した匿名認証システムにおける認証補助装置の内部構成を示す概略ブロック図である。
【図１８】図１５に開示した匿名認証システムにおける検証補助装置の内部構成を示す概略ブロック図である。
【図１９】図１５に開示した匿名認証システムにおける被認証者特定処理の動作処理ステップを示すフローチャートである。
【図２０】図１５に開示した匿名認証システムにおける被認証者特定処理の動作処理ステップを示すフローチャートである。
【発明を実施するための形態】
【００２０】
［実施形態１］
次に、本発明を実施するための実施形態について図面を参照して説明する。
尚、以下に示す実施形態の説明においては、例えば、ａ＾{ｂ}はａのｂ乗を意味し、ａ＿ｂは、ａに下付き添字ｂが付いた変数を示す。
また、ビットの連結を「｜」と表記する（例えば、ａ＝１０（バイナリ表記）、ｂ＝０１とした場合、ａ｜ｂ＝１００１を示すものとする）。
【００２１】
本発明の実施形態１としての匿名認証システムは、図１に示すように、グループに属する被認証者装置に係る情報を管理するグループ管理装置１０、グループ管理装置１０に対して認証要求を行う被認証者装置２０と、認証要求を行った被認証者装置２０のユーザが上記グループに所属している否かの検証を行う検証装置３０と、検証装置３０による検証の補助を行う検証補助装置４０−１、４０−２〜４０−ｔと、被認証者装置におけるユーザＩＤ被認証者を特定する処理を行うと共に予め設定された条件に基づきグループ内における被認証者装置２０の匿名性（ユーザＩＤの秘匿性）を剥奪する制御を行う被認証者特定装置５０−１、５０−２、・・・、５０−ｔを備えた構成を有する。
【００２２】
尚、本実施形態１では、グループ管理装置１０および被認証者装置２０、グループ管理装置１０と各検証補助装置４０−１〜４０−ｔ、グループ管理装置１０と各被認証者特定装置５０−１〜５０−ｔ、被認証者装置２０と検証装置３０、検証装置３０と各検証補助装置４０−１〜４０−ｔ、はそれぞれインターネットなどのネットワーク介して通信可能に接続されているものとする。
また、本実施形態では、設定されたグループごとにグループ管理装置が設定されているものとする。尚、各グループに複数の被認証者装置や検証装置が存在する構成であってもよい。
【００２３】
ここで、各グループに対応したグループの暗号化鍵（ｅｎｃ＿ｇ−１〜ｅｎｃ＿ｇ−ｔ）がユーザにより被認証者装置２０に入力されるものとする。
また、グループの暗号化鍵ｅｎｃ＿ｇ−ｉに対応したグループの復号鍵ｄｅｃ＿ｇ−ｉが、検証補助装置４０−ｉ（４０−１〜４０−ｔそれぞれを示す）および被認証者特定装置５０−ｉ（５０−１〜５０−ｔそれぞれを示す）それぞれ入力されるものとする。
尚、これらの暗号化鍵および復号鍵からなるペア鍵は、グループごとに複数個存在するものとする。
【００２４】
グループ管理装置１０は、図２に示すように、被認証者装置２０からの要求（登録要求メッセージ）に応じて被認証者装置ユーザ（以下「ユーザ」という）のグループへの参加登録処理を行うと共に、登録したユーザに割当てたユーザＩＤを被認証者装置２０に送信する登録処理部１０−１と、グループに在籍するメンバーユーザのリストを登録情報リスト（以下、メンバリスト）として記憶するメンバー登録情報記憶装置１０−２を有する。
【００２５】
被認証者装置２０は、図３に示すように、グループ管理装置１０に登録要求メッセージを送信する登録要求部２０−１と、グループ管理装置１０によって割り振られたユーザＩＤと、ユーザの署名鍵および検証鍵ペアとを対応付けて記憶するＩＤ・鍵ペア記憶装置２０−２と、検証装置３０に対して認証要求を示す認証要求メッセージを送信する認証要求部２０−３と、認証データが生成される際にユーザの署名鍵を用いて署名生成を行う署名生成部２０−４と、グループの暗号化鍵および認証者特定者を指定する論理構造を受信した場合に認証データを生成する認証データ生成部２０−５を有する。
【００２６】
検証装置３０は、図４に示すように、被認証装置２０（認証要求部２０−３）からの認証要求を受信した場合にランダムに選択生成されるチャレンジ（チャレンジコード）を生成するチャレンジ生成部３０−１と、被認証装置２０（認証要求部２０−３）からの認証データを受信した場合に、この認証データに応じた検証補助要求を検証補助装置４０に送信する検証補助要求部３０−２と、検証補助装置４０から送り込まれた検証補助結果に基づく検証を行う検証部３０−３と、認証処理（結果）の履歴情報としての認証データを記憶する認証データ記憶装置３０−４と、認証データ記憶装置３０−４に記憶されている認証データに基づき匿名性剥奪要求を生成すると共に、この匿名性剥奪要求を予め設定された異なる被認証者特定装置（５０−１、・・・、５０−ｔ）それぞれに対して送信する被認証者特定要求部３０−５を有する。
【００２７】
検証補助装置４０−ｉは、図５に示すように、検証装置３０から送り込まれた検証補助要求に応じて認証データの復号処理を行う認証データ復号部４０−１−１と、グループ管理装置１０から取得したメンバリストに基づき復号した認証データにおける署名の検証を行う署名検証部４０−ｉ−２を有する。
尚、検証補助装置４０−１〜４０−ｔはそれぞれ、上記検証補助装置４０−ｉと同一の内部構成を有するものとする。
【００２８】
被認証者特定装置５０−１は、図６に示すように、検証装置３０から送り込まれた匿名性剥奪要求とユーザが指定した論理構造を満たすグループの復号鍵を受信し、認証データの復号処理を行う認証データ復号部５０−ｉ−１と、グループ管理装置１０から取得したメンバリストに基づき被認証者（ユーザ）の特定を行う被認証者特定部５０−ｉ−２を備えている。
【００２９】
本実施形態では、公開鍵暗号方式および電子署名方式を利用して、上記匿名認証システムを実現する。
【００３０】
ここで、本実施形態で利用される公開鍵暗号方式について、説明する。
本実施形態１では、公開鍵暗号方式として、例えば、文献「Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack」（非特許文献３）に記載されている公開鍵暗号方式（以下、「Cramer-Shoup 暗号方式」という）を用いることができる。
さらに、本実施形態では電子署名方式として、文献「Signature Schemes Based on the Strong RSA Assumption」（非特許文献４）に記載されている電子署名方式（以下、Cramer-Shoup 署名方式）が利用可能であるものとする。
【００３１】
また、本実施形態では、例えばＲＳＡ−ＯＡＥＰ暗号方式など、暗号文からメッセージに関する情報の漏洩を有効に抑制し得ること、つまり、情報漏洩に対する安全性が数学的に証明可能な他の公開鍵暗号方式を利用する構成であってもよい。
【００３２】
更に、本実施形態では、非特許文献４に記載のCramer-Shoup署名方式などに限られず、例えばＥｌ  Ｇａｍａｌ署名方式などのように、ある検証鍵で受理される署名データがその検証鍵に対応した署名鍵を知らない場合に生成することが困難であることが数学的に証明可能な他の電子署名方式を利用する設定であってもよい。
【００３３】
さらに、本実施形態では、上記文献「Randomness re-use in multi-recipient encryption schemes」（非特許文献５）に記載されている、複数回の暗号化を行う際に、同じ乱数を用いても安全な方式を利用する設定であってもよい。
本実施形態では、非特許文献５に示される技術を利用することにより、認証データ生成に必要な乱数の個数を減らすことができ、更には、認証データサイズを小さくするによる効率化を行うことが可能となる。
【００３４】
例えば、同じ被認証者により異なる被認証者特定者を指定した認証データが作成される手法では、認証データのデータ長は、指定した被認証者特定者の数分の認証データと、ゼロ知識証明のデータ長の合計となる。
すなわち、この手法では、被認証者特定者を1人としたときのデータ長をＡ、ゼロ知識証明のデータ長をＢとした場合、被認証者特定者をｔ人としたときのデータ長はｔ×Ａ＋Ｂとなる。
これに対して、本実施形態で利用される上記非特許文献５に記載の技術では、認証データのデータ長はＡ＋（ｔ−１）ａ＋Ｂ（ただし、ａ＜Ａとする）とすることできる。
【００３５】
ここで、Ｅｌ  Ｇａｍａｌ暗号について説明する。Ｅｌ  Ｇａｍａｌ暗号は、公開鍵暗号方式の一つの手法であって、ＤＤＨ仮定と呼ばれる数学的な仮定をおくことにより、その安全性を証明可能な公開鍵暗号方式であることが知られている。
Ｅｌ  Ｇａｍａｌ暗号の処理要素は、以下に示す鍵セットアップ、暗号化処理、復号処理の３つの構成要素からなり、本実施形態におけるグループ管理装置などで計算が行われるものとする。
【００３６】
まず、Ｅｌ  Ｇａｍａｌ暗号における処理要素としての鍵セットアップ処理の計算手順について説明する。ここでは、セキュリティパラメータｋ、ｋビットの素数ｑ、位数ｑの群Ｇ、群Ｇの生成元ｇが鍵セットアップの入力値として与えられているものとする。
また、ｑの剰余群を、Ｚ＿ｑ＝｛０，１，２，．．．，ｑ−１｝とし、このとき、Ｚ＿ｑからランダムに要素ｘを選ぶものとする。
さらに、Ｘ＝ｇ＾ｘを計算する。このとき、公開鍵ｐｋ＝（ｑ，ｇ，Ｘ）、秘密鍵＝ｘとなる。
【００３７】
次に、Ｅｌ  Ｇａｍａｌ暗号における処理要素としての、暗号化処理の計算手順について説明する。
ここでは、前述の鍵セットアップ処理によって、公開鍵ｐｋ＝（ｑ，ｇ，Ｘ）が生成され、この値が暗号化処理の入力値として与えられているものとする。また、このとき暗号化されるメッセージをＭとする。
ここで、Ｚ＿ｑの要素ｒをランダムに選出し、Ｙ＝ｇ＾ｒを計算すると共に、Ｗ＝Ｍ（Ｘ）＾ｒを計算し、これに基づき、暗号文Ｃ＝（Ｙ，Ｗ）を出力する。
【００３８】
次に、Ｅｌ  Ｇａｍａｌ暗号における処理要素としての、復号処理の計算手順について説明する。
ここでは、前述の鍵セットアップによって生成された公開鍵ｐｋに対応する秘密鍵ｓｋ＝ｘが、復号処理における入力値として与えられているものとする。
また、前述の暗号化処理によって生成された暗号文Ｃ＝（Ｙ，Ｗ）も入力値として与えられているものとする。
ここでは、Ｔ＝Ｙ＾ｘを計算すると共に、このＴを利用して、Ｍ＝ＷＴ＾｛−１｝を計算し、最後に、このＭを平文として出力する。
【００３９】
次に、Ｅｌ  Ｇａｍａｌ署名方式について説明する。
Ｅｌ  Ｇａｍａｌ署名方式は、電子署名方式のひとつであって、離散対数仮定と呼ばれる数学的な仮定をおくことにより、安全性を証明できる電子署名方式であることが知られている。
Ｅｌ  Ｇａｍａｌ署名方式は、鍵セットアップ、署名生成処理、署名検証処理の３つの処理要素からなる。
ここで、Ｈを衝突困難な、つまり、Ｈ（ｘ）＝Ｈ（ｙ）を満たす（ｘ，ｙ）を見つけることが困難であるハッシュ関数とする。また、素数ｐをＺ＿ｐ上で離散対数問題が困難であるような素数とする。さらに、ｇ＿ｓをＺ＿ｐの生成元とする。
【００４０】
まず、鍵セットアップについて説明する。この鍵セットアップでは、はじめに、（ｐ，ｇ＿ｓ）を鍵セットアップの入力として与えられる。次に、Ｚ＿ｐからランダムにｘ（ただし、ｘは０以外）を選ぶ。ここで、ｙ＝ｇ＿ｓ＾ｘを計算し、最後に、検証鍵ｖｋ＝（ｐ，ｇ＿ｓ，ｙ）、署名鍵ｓｋ＝ｘとして出力する。
【００４１】
次に、署名生成（処理の内容）について説明する。
ここでは、署名対象メッセージＭ、署名鍵ｓｋ、検証鍵ｖｋが署名生成処理の入力値として与えられているものとする。
ここで、Ｚ＿ｐからランダムにｋ（ただし、ｋは０以外）を選出し、ｒ＝ｇ＿ｓ＾ｋを計算し、次いで、ｓ＝（Ｈ（Ｍ）−ｘｒ）ｋ＾｛−１｝ｍｏｄ（ｐ−１）を計算する。ここで、もしｓ＝０である場合は初めからやり直す。これにより、σ＝（ｒ，ｓ）を署名として出力する。
【００４２】
次に、署名検証の処理内容について説明する。
まず、平文Ｍ、署名σ＝（ｒ，ｓ）、検証鍵ｖｋが、署名検証処理の入力（値）として与えられる。ここで、０＜ｒ＜ｐかつ０＜ｓ＜ｐ−１であることを確認する。
次いで、ｇ＿ｓ＾｛Ｈ（Ｍ）｝＝ｙ＾ｒｒ＾ｓｍｏｄｐであることを確認し、上記両者が確認された場合に、署名σを受理し、この受理（内容）を出力する。ここで、署名σが受理されない場合、不受理を示す情報を出力する。
【００４３】
次に、本実施形態である匿名認証システムの構成内容について、詳説する。
ここでは、本実施形態である匿名認証システムにおいて、Ｅｌ  Ｇａｍａｌ暗号方式および Ｅｌ  Ｇａｍａｌ署名方式を利用して、匿名認証処理を行う場合について、説明する。
【００４４】
尚、本実施形態では、Ｅｌ  Ｇａｍａｌ暗号の暗号化鍵として暗号化鍵ｅｎｃ＿ｇ−ｉ＝（ｑ，ｇ，Ｘ＿ｉ）が公開されているものとする。また、これに対応する復号鍵は、復号鍵ｄｅｃ＿ｇ−ｉ＝（ｘ＿ｉ）であるものとする。
さらに、グループに加入しようとするユーザＵは、Ｅｌ  Ｇａｍａｌ署名の署名鍵ｓｋ＿ｕ＝（Ｘ＿ｕ）、および、これに対応する検証鍵ｖｋ＿ｕ＝（ｐ，ｇ＿ｓ，ｙ）を有するものとする。
【００４５】
まず、認証処理の実行に先立ち行われる事前処理としての入会登録処理の内容について説明する。
ユーザＵにより署名鍵・検証鍵のペア（ｓｋ＿ｕ，ｖｋ＿ｕ）が被認証者装置２０に入力された場合に、登録要求部２０−１は、受信した検証鍵ｖｋ＿ｕに基づき登録要求（ｒｅｑ＿ｒ）を設定しグループ管理装置１０に送信する（登録要求送信機能）。
このとき登録要求（ｒｅｑ＿ｒ）には、ユーザＵの検証鍵ｖｋ＿ｕ、および住所、氏名、年齢など、登録に必要な個人情報が含まれているものとする。
【００４６】
登録要求ｒｅｑ＿ｒを受信した登録処理部１０−１は、ユーザＵに対してユーザＵ固有のＩＤであるＩＤ＿ｕを発行し、このＩＤ＿ｕを被認証者装置２０に送信する（ユーザＩＤ設定機能）。
ただし、登録について予め設定された条件（例えば、性別制限、年齢制限、２重登録禁止など）がある場合、登録処理部１０−１は、登録要求（ｒｅｑ＿ｒ）の内容に基づき、登録処理部１０−１が審査を行う（登録要求審査機能）。
ここで、登録処理部１０−１は、条件を満たさないユーザＵからの登録要求であった場合、登録不可を被認証者装置２０に送信する設定であってもよい。
尚、ユーザが登録不可であった場合、そのユーザに対して、以下に示す処理を中止する。
【００４７】
また、登録処理部１０−１は、メンバー登録情報記憶装置１０−２よりメンバリスト（Ｌｉｓｔ）を取得し、（ＩＤ＿ｕ，ｒｅｑ＿ｒ）をメンバリスト（Ｌｉｓｔ）に追記することによりメンバリストを更新するメンバリスト更新機能を有する。ここで、登録処理部１０−１は、更新されたメンバリストＬｉｓｔをメンバー登録情報記憶装置１０−２に記憶するものとする。
【００４８】
また、登録処理部１０−１からのＩＤ＿ｕを受信した被認証者装置２０は、（ＩＤ＿ｕ，（ｓｋ＿ｕ，ｖｋ＿ｕ））をＩＤ・鍵ペア記憶装置２０−２に記憶するユーザＩＤ・鍵ペア格納機能を有する。
【００４９】
（認証処理（１））
次いで、本実施形態における、認証処理の処理内容について説明する。
ここでは、ユーザＵが、署名鍵ｓｋ＿ｕ、検証鍵ｖｋ＿ｕの登録を完了しており、これにより、ＩＤ・鍵ペア記憶装置２０−２には、（ＩＤ＿ｕ，（ｓｋ＿ｕ，ｖｋ＿ｕ））が予め記憶されているものとする。
【００５０】
被認証者装置２０の認証要求部２０−３は、検証装置３０に認証要求（ｒｅｑ＿ａ）を送信する認証要求送信機能を有する。このとき、認証要求ｒｅｑ＿ａは、システムに予め定められた定型文であってよい。
また、認証要求（ｒｅｑ＿ａ）を受信した検証装置３０のチャレンジ生成部３０−１は、認証要求（ｒｅｑ＿ａ）に対応してランダムにチャレンジ（ｎｏｎｃｅ）を選出すると共に、このチャレンジｎｏｎｃｅを被認証者装置２０に送信する（チャレンジ返信機能）。
【００５１】
チャレンジ（ｎｏｎｃｅ）を受信した署名生成部２０−４は、ＩＤ・鍵ペア記憶装置２０−２に記憶されているｓｋ＿ｕを用いてチャレンジ（ｎｏｎｃｅ）に署名データを付与する（署名データ付与機能）。
ここで、署名生成部２０−４は、まずＺ＿ｐからランダムにｋを選び、ｒ＝ｇ＿ｓ＾ｋを計算し、更に、ｓ＝（Ｈ（ｎｏｎｃｅ）−ｘｒ）ｋ＾｛−１｝ｍｏｄ（ｐ−１）を計算する。
尚、ここで算出結果がｓ＝０である場合、署名データ付与機能を初めからやり直すものとする。ここで、署名生成部２０−４は、算出された値からなるσ＝（ｒ，ｓ）を署名データとして設定する。
【００５２】
認証データ生成部２０−５は、被認証者特定者を指定する、被認証者におり生成された論理構造と、グループの暗号化鍵（ｅｎｃ＿ｇ−１＝（ｑ，ｇ，Ｘ＿１），．．．，ｅｎｃ＿ｇ−ｔ＝（ｑ，ｇ，Ｘ＿ｔ））を受信した場合に、署名データ（σ）の暗号文を作成する（署名データ暗号化機能）。
【００５３】
ここでは、被認証者により入力された論理構造により指定された各被認証者特定装置５０−ｉ（１≦ｉ≦ｔ）が単独で被認証者を特定できる場合、すなわち、「被認証者特定装置のうち何れか1台が特定できる（ＯＲ構造）」という場合について説明するものとする。
【００５４】
尚、他に、異なる被認証者特定装置（例えば、５０−ａと５０−ｂ）が相互に連携処理を行うことにより、被認証者を特定する（ＡＮＤ構造）場合や、例えば、１０台の被認証者特定装置のうち、予め設定された台数の装置が相互に連携処理を行うことにより、被認証者を特定することができる（ｔｈｒｅｓｈｏｌｄ構造）場合などが設定可能であるものとする。これらのケースについては後述する。
【００５５】
また、本実施形態では、上記ＯＲ構造およびＡＮＤ構造を組み合わせることにより、設定された任意の論理構造に基づき、被認証者の特定を行う構成としてもよいものとする。
例えば、３台の被認証者特定者装置Ａ，Ｂ，Ｃのうち、任意の２台で特定可能という条件下においては、「ＡおよびＢ」または「ＢおよびＣ」または「ＡおよびＣ」が相互に連携処理を行うことにより、被認証者を特定することが可能となり、これは、ＯＲ構造とＡＮＤ構造を用いてｔｈｒｅｓｈｏｌｄ構造が実現されることを意味する。このようにして、ＯＲ構造とＡＮＤ構造を組み合わせることにより、任意の論理構造が構成できることは広く知られている。
【００５６】
ここで、本実施形態における認証データ生成部２０−５は、Z_{q} からランダムに値（ここでは「r」）を選出すると共に、このｒを用いて、Ｙ＝ｇ^ｒ， W_1=(ID||σ)X_1^r, …，W_t=(ID||σ)X_t^r をそれぞれ計算する。ここで、予め設定された暗号文ＣをＣ＝(Y, W_1, …, W_t) とする。
次いで、被認証者装置２０（認証要求部２０−３）は、認証データとしてのｒｅｓｐｏｎｓｅ（response=(ｎｏｎｃｅ, Ｃ)とする）を検証装置３０に送信する。
【００５７】
検証装置３０の検証補助要求部３０−２は、被認証者装置２０から送り込まれた認証データ（ｒｅｓｐｏｎｓｅ）に基づき、暗号文Ｃを含む検証補助要求データ（req_v=response）を設定すると共に、この検証補助要求データを検証補助装置４０−１〜４０−ｔそれぞれに対して送信する（検証補助要求送信機能）。
【００５８】
検証補助装置４０−ｉ（４０−１〜４０−ｔ）では、検証補助要求データ（req_v）と
グループの復号鍵（dec_g-i=(x_i)）を受信した場合に、認証データ復号部４０−ｉ−１が、検証補助要求データ（req_v）に含まれる暗号文（Ｃ＝(Y, W_1, …, W_t)）から、Ｃ＿ｉ＝（Y，Ｗ＿ｉ） を抽出すると共に、このＣ＿ｉを復号する処理を行う（復号処理機能）。
【００５９】
ここで、認証データ復号部４０−ｉ−１における上記復号処理の内容について、詳説する。
まず、検証補助装置４０−ｉは、T_i=Y^{x_i} を計算し、次いで、算出されたT_i を利用してM=W_iT_i^{-1} を計算する。
ここで、認証データ復号部４０−ｉ−１は、得られたメッセージＭを（ＩＤ｜｜σ）とパースする、つまり、ＭをＩＤおよびσ＝（ｒ，ｓ）に分解する（復号処理終わり）。
【００６０】
次に、署名検証部４０−２が、グループ管理装置１０のメンバー登録情報記憶装置１０−２に記憶されているメンバリスト（Ｌｉｓｔ）を受信すると共に、メンバリスト（Ｌｉｓｔ）にＩＤが記載されているか否かの確認判定を行う。
【００６１】
ここで、署名検証部４０−２は、ＩＤが記載されていない場合、不受理である旨を示す検証補助データ（ａｎｓ＿ｖ）を検証装置３０に送信する。
一方、メンバリストにＩＤが記載されている場合、ＩＤに対応する検証鍵（ｖｋ＿ｕ＝(p, g_s, y_u)） を用いて、署名データ（σ）の検証を行う（検証処理）。
【００６２】
ここで、署名検証部４０−２における上記検証処理の内容について説明する。
まず、署名検証部４０−２は、値ｒ、ｓについて、0<r<p かつ 0<s<p-1が成り立つか否かを確認し、次に、g_s^{H(ｎｏｎｃｅ)}=y^r r^s mod p が成立することを確認する。
上記すべてが成立していることが確認された場合に、署名検証部４０−２は、「受理」を示す署名検証結果（情報）を設定し、それ以外の場合は、「不受理」を示す署名検証結果（情報）を設定する（検証処理の内容説明終わり）。
【００６３】
次いで、署名検証部４０−ｉ−２は、署名検証結果（受理または不受理を示す）を検証補助データ（ans_v-i）として検証装置３０に送信する。
次に、検証部３０−３は、署名検証部４０−ｉ−２それぞれから検証補助データ （ans_v-1〜ans_v-t）を受信した場合に、受信したすべての検証補助データの検証結果が「受理」を示す場合に、認証結果（ｒｅｓｕｌｔ）を認証成功として出力する。
【００６４】
一方、検証部３０−３は、受信した検証補助データにひとつでも（つまり、一つ以上）「不受理」を示す検証結果が含まれていた場合、認証結果（ｒｅｓｕｌｔ）を認証失敗として出力する。
さらに、検証部３０−３は、認証成功を示す認証データ（ｒｅｓｐｏｎｓｅ）を、認証データ記憶装置３０−４に記憶する。尚、検証部３０−３は、認証成功を示す認証データと同様に、認証失敗を示す認証データも認証データ記憶装置３０−４に対して格納する設定であってもよい。
【００６５】
次に、本実施形態における、認証データに基づき被認証者の特定を行う処理について説明する。
【００６６】
（被認証者特定処理（１））
次に、認証データから被認証者（被認証者装置）の特定を行う処理（被認証者特定処理）について説明する。
ここでは、検証装置３０の認証データ記憶装置３０−４に記憶された認証データ （response_i）を生成した被認証者のＩＤを特定する場合の動作処理ついて説明する。
尚、被認証者特定装置５０−ｉそれぞれが単独で認証データに基づき被認証者（被認証者のＩＤ）を特定できるものとする（ＯＲ構造）。
【００６７】
まず、検証装置３０の被認証者特定要求部３０−５は、認証データ記憶装置３０−４に記憶されている認証データ（response_i=(ｎｏｎｃｅ_i, C_i)）を取得すると共に、この認証データに基づき被認証者特定要求データ（ｒｅｑ＿ｔ＝Ｒｒｅｓｐｏｎｓｅ＿ｉ）を生成して被認証者装置５０−ｉに送信する。
【００６８】
ここで、認証データ復号部５０−ｉ−１は、グループ管理装置１０から予め送り込まれたグループの復号鍵（dec_g-j=(x_j)）と被認証者特定要求データ（ｒｅｑ＿ｔ）とを取得する。
このとき、認証データ復号部５０−ｉ−１は、被認証者特定要求データ（ｒｅｑ＿ｔ）に含まれる暗号文（Ｃ_ｊ＝（Ｙ，Ｗ＿ｊ））から、Ｔ＝Ｙ^｛ｘ＿ｊ｝を計算する。
【００６９】
次に、認証データ復号部５０−ｉ−１は、Ｍ＿ｊ＝Ｗ＿ｊＴ^｛−１｝を計算し、次いで、上記結果得られたメッセージ（Ｍ＿ｊ）を（ＩＤ＿ｉ｜｜σ＿ｉ）とパースすることにより、メッセージ（Ｍ＿ｊ）をＩＤ＿ｉおよびσ＿ｉ＝（e_i, y_i, y'_i）に分解する処理を行う。
【００７０】
次に、被認証者特定部５０−ｉ−２が、グループ管理装置１０のメンバー登録情報記憶装置１０−２に記憶されているメンバリスト（Ｌｉｓｔ）を取得すると共に、ＩＤ＿ｉがメンバリスト（Ｌｉｓｔ）に記載されているか否かの確認を行う（ＩＤ＿ｉ確認判定）。
【００７１】
ここで、被認証者特定部５０−ｉ−２は、ＩＤ＿ｉがメンバリスト（Ｌｉｓｔ）に記載されている場合、ＩＤに対応する検証鍵（vk_u＝（p, g_s, y_u））を用いて、署名データ（σ）の検証処理を行う。
【００７２】
ここで、被認証者特定部５０−ｉ−２における上記検証処理内容について説明する。
まず、被認証者特定部５０−ｉ−２は、０<ｒ<ｐかつ０<ｓ<ｐ−１を確認し、次に、g_s^{H(ｎｏｎｃｅ)}=y^r・r^s mod p が成立することを確認する。
このとき、すべての（g_s^{H(ｎｏｎｃｅ)}=y^r・r^s mod p）が成立していた場合に、被認証者特定部５０−ｉ−２は、「受理」を示す署名検証結果を設定する。
一方、g_s^{H(ｎｏｎｃｅ)}=y^r r^s mod pが成立していない署名データが一つでも含まれていた場合には、被認証者特定部５０−ｉ−２は、「不受理」を示す署名検証結果を設定する（検証処理内容の説明終わり）。
【００７３】
次いで、被認証者特定部５０−ｉ−２は、上記署名検証結果（受理または不受理を示す）を検証補助データ（ａｎｓ＿ｖ−ｉ）として検証装置３０に送信する。
【００７４】
検証部３０−３は、異なる被認証者特定装置５０−ｉから受信した検証補助データ（ａｎｓ＿ｖ−１〜ａｎｓ＿ｖ−ｔ）のすべてが署名検証結果として「受理」を示す場合に、認証結果（ｒｅｓｕｌｔ）を認証成功として出力する。
一方、検証部３０−３は、受信した検証補助データ（ａｎｓ＿ｖ−１〜ａｎｓ＿ｖ−ｔ）における署名検証結果として「不受理」を示すものが一つでも（つまり、１以上）含まれていた場合、認証結果（ｒｅｓｕｌｔ）を認証失敗として出力する。
【００７５】
また、検証部３０−３は、検証結果が受理であった場合に、認証データ（ｒｅｓｐｏｎｓｅ＿ｉ）は、対応するＩＤ（ID_i） を持つユーザにより作成された認証データであることを示すメッセージを出力する。ＩＤ（ID_i）がメンバリスト（Ｌｉｓｔ）に記載されていない、あるいは、署名データ（σ_i）の検証結果が不受理であった場合、検証部３０−３は、被認証者特定を要求された認証データ（ｒｅｓｐｏｎｓｅ＿ｉ）は受理されず、受理されない認証データであると出力する。
【００７６】
（被認証者特定処理（２）：ＡＮＤ構造）
次に、被認証者が指定した被認証者特定装置を示す論理構造情報に基づき、指定された複数の被認証者特定装置が相互に協力した場合に、被認証者の特定が可能となる構造（ＡＮＤ構造）について、説明する。
ここでは、例えば、異なる被認証者特定者としての被認証者特定者Ａと被認証者特定者Ｂとが協力（相互連携処理を行わなければ）しなければ、被認証者を特定することができないものとする（ＡＮＤ構造）。
【００７７】
ここでは、被認証者特定者Ａに対応したグループの暗号化鍵（enc_g−A=(q, g, X_A)）、被認証者特定者Ｂに対応したグループの暗号化鍵enc_g−B=(q, g, X_B)、それぞれの秘密鍵を x_A, x_B とする。
このとき、enc_g-AB = (q, g, X_A・X_B) と公開鍵を置き換え、Ｅｌ  Ｇａｍａｌ 暗号の暗号化処理を行う。
【００７８】
また、その暗号文の復号処理時に、秘密鍵を（ｘ＿Ａ＋ｘ＿Ｂ）と置き換えることにより復号処理が可能となる。
したがって、検証補助装置４０−Ａおよび４０−Ｂ、被認証者特定装置５０−Ａおよび５０−Ｂは、検証補助および被認証者特定処理の際に、相互に通信を行うことによりそれぞれ（ｘ＿Ａ＋ｘ＿Ｂ）を生成し、（ｘ＿Ａ＋ｘ＿Ｂ）を秘密鍵とすることにより復号処理を行う。
これにより、指定された複数の被認証者特定装置（被認証者特定者ＡおよびＢとする）が相互に協力した場合に被認証者の特定することが実現される。
【００７９】
（認証処理３：ｔｈｒｅｓｈｏｌｄ構造）
次に、被認証者が指定した被認証者特定装置を示す論理構造情報に基づき、予め設定されたグループｍ人の被認証者特定者（ｍ台の被認証者特定装置）のうちのn人（ｎ台）以上の被認証者特定装置が相互に協力した場合に被認証者の特定が可能となる構造（ｔｈｒｅｓｈｏｌｄ構造）について、説明する。
ここでは、上記ＯＲ構造およびＡＮＤ構造を組み合わせると共に、Ｅｌ  Ｇａｍａｌ 暗号を利用することにより、上記ｔｈｒｅｓｈｏｌｄ構造を実現する。
【００８０】
まず、グループ管理装置（グループ管理者）１０は、 グループを構成するｍ台の被認証者特定装置の数に対応してm 個のグループの暗号化鍵 （enc_g-1=(q,g,X_1)，enc_g-２=(q,g,X_２)，…，enc_g-m=(q,g,X_m)）と、それぞれに対応した秘密鍵（x_1,・・・, x_m）を生成する（ペア鍵生成処理）。
【００８１】
ここで、グループ管理装置（グループ管理者）１０におけるm 個（台）の被認証者装置から構成されるグループの暗号化鍵および秘密鍵を生成する処理（上記ペア鍵生成処理）について、説明する。
【００８２】
まず、登録処理部１０−１は、グループの秘密鍵ｘを生成する。ここで、ｘは、Ｚ＿ｑの元値であるものとする。また、X_0=g^x とし、enc_g-0=(q,g,X_0)をグループの暗号化鍵として公開する。
【００８３】
次いで、登録処理部１０−１は、次数（ｎ−１）のランダムな多項式 ｆ（ｔ）を設定する。尚、ｆ（ｔ）は、ｆ（０）＝ｘを満たすものとする。つまり、ｆ（ｔ）＝ x + r_1 t + r_2 t^2 +… +r_{n-1} t^{n-1} であるものとする。x_1=f(1), x_2=f(2),・・・,x_m=f(m) とし、更には、X_1=g^{x_1}, X_2=g^{x_2},…, X_m=g^{x_m} とする（ペア鍵生成処理終わり）。
【００８４】
上述のように、ｍ人の被認証者特定者のうち，n人以上が協力しないと被認証者を特定できない、スレッショルド構造における認証処理では、被認証者装置２０は、グループの公開鍵（ｅｎｃ＿ｇ−０＝(q, g, X_0)） を用いて「Ｅｌ  Ｇａｍａｌ暗号」の暗号化処理を行う。
【００８５】
また、検証補助および被認証者特定処理においては、以下に示すように、復号処理が行われる。尚、ここでは、被認証者特定処理における場合について説明する。
【００８６】
ここで、入力された暗号文を Ｃ＝（Ｙ，Ｗ）とする。また、復号処理に参加する被認証者特定装置の有する秘密鍵をそれぞれｘ＿{ｉ＿１}，・・・，ｘ＿{ｉ＿ｎ}とする。
このとき、被認証者特定装置（被認証者特定者）ｉ＿ｊは、λ＿｛０，１｝＝(ｉ＿１)／(ｉ＿１−ｉ＿ｊ)・(ｉ＿２)／(ｉ＿２−ｉ＿ｊ)・…・(ｉ＿ｎ)／(ｉ＿ｎ−ｉ＿ｊ)を計算する。ただし、(ｉ＿ｊ)／(ｉ＿ｊ−ｉ＿ｊ)は含まないものとする。
【００８７】
さらに、被認証者特定装置（被認証者特定者）ｉ＿ｊは、Ｙ＿｛ｉ＿ｊ｝＝Ｙ＾｛ｘ＿｛ｉ＿ｊ｝・λ＿｛０，１｝｝を計算し、被認証者特定装置５０（ｉ＿１，・・・，ｉ＿ｎ）に送付する。
すべてのＹ＿｛ｉ＿１｝，・・・，Ｙ＿｛ｉ＿ｎ｝を受信した被認証者特定装置５０−ｉは、Ｍ＝Ｗ／(Ｙ＿｛ｉ＿１｝・・・・・Ｙ＿｛ｉ＿ｎ｝）を計算する（ここで、Ｍを復号結果とする）。
【００８８】
尚、上述の復号方法では、一般にシャミアの秘密分散法を元にして構成されているため、ｎ台未満の被認証者特定装置による連携処理では復号を行うことができない。
ｍ人中任意のｎ人以上の被認証者特定装置（５０−１〜５０−ｔ）による連携処理によって復号が可能となる。
また、これらの暗号化処理および復号処理を組み合わせることにより、被認証者は任意の論理構造を指定することが可能となる。
【００８９】
尚、本実施形態１である匿名認証システムにおけるグループ管理装置１０は、例えば、グループを管理する事業者（以下、グループ管理事業者と呼ぶ）により運営されるサーバコンピュータであるものとする。このグループ管理事業者は、例えば、インターネットサービスプロバイダであってもよい。
【００９０】
また、被認証者装置２０は、例えば、ユーザにより操作されるパーソナルコンピュータであるものとする。また、このユーザは、例えば、インターネットサービスプロバイダの会員であるものとする。
【００９１】
検証装置３０は、例えば、ユーザの登録確認を行い、サービスの提供を行う事業者（以下，サービスプロバイダと呼ぶ）によって運営されるサーバコンピュータであるものとする。
また、このサービスプロバイダは、例えば、公共の無線ＬＡＮサービスを提供し、上記検証装置３０は、この無線ＬＡＮサービスシステムにおける無線アクセスポイントであってもよい。
【００９２】
検証補助装置４０は、例えば、検証装置３０とインターネットなどで接続され、検証装置３０からの検証補助要求に応じてサービス提供を行う事業者（以下、検証補助事業者と呼ぶ）により運営されるサーバコンピュータであってもよい。
また、この検証補助事業者は、例えば、インターネットサービスプロバイダのオンライン検証部門であってもよい。
【００９３】
各被認証者特定装置５０−１〜５０−ｔは、例えば、必要に応じて被認証者の匿名性を剥奪する事業者（以下、「被認証者特定事業者」という）によって運営されるサーバコンピュータであって、
【００９４】
この被認証者特定事業者は、例えば、インターネットサービスプロバイダの課金部門、ユーザの趣向情報の統計データを生成する部門、違反など問題行為を行ったユーザを特定する部門などであるものとする。
【００９５】
ここでは、それぞれ異なる被認証者特定事業者であり、異なる被認証者特定装置を動作させていてもよい。
【００９６】
上記の事業形態においては、まず、グループ管理事業者が、グループの暗号化鍵ｅｎｃ＿ｇ−１からｅｎｃ＿ｇ−ｔと、それぞれに対応したグループの復号鍵ｄｅｃ＿ｇ−１〜ｄｅｃ＿ｇ−ｔを決定し、
グループに関する情報とともにグループの暗号化鍵ｅｎｃ＿ｇ−１〜ｅｎｃ＿ｇ−ｔを、例えば新聞・ホームページなどによって公知する。
さらに、グループの復号鍵ｄｅｃ＿ｇ−１〜ｄｅｃ＿ｇ−ｔを、検証補助事業者および被認証者特定事業者に送付する設定であってもよい。
【００９７】
次に、ユーザがグループ管理事業者の管理するグループへの入会を希望する。
グループ管理事業者は、入会を希望してきたユーザがグループに加入する条件を満たしているか（年齢など）を確認し、条件を満たすユーザに対して入会手続きを行う（例えば、会員証を発行し、ユーザに送付する）。
【００９８】
次に、ユーザが、被認証者装置２０にグループの暗号化鍵ｅｎｃ＿ｇ−１〜ｅｎｃ＿ｇ−ｔを入力し、認証データを検証装置３０に送信させる（例えば、無線ＬＡＮサービス
を利用する際に、インターネットサービスプロバイダの会員であることを証明する認証データを送付する）。
認証データを受信した検証装置３０は、検証補助要求を検証補助装置４０−１〜４０−ｔに送信し、検証補助データを得ることにより検証を行い、認証結果を出力する（例えば、アクセスポイントは、ユーザがインターネットサービスプロバイダの会員である事を確認し、無線ＬＡＮサービスを提供する）。
【００９９】
さらに、検証事業者は、被認証者特定装置５０−ｉに対して、各ユーザの認証データを含む被認証者特定要求を送信させる。
被認証者特定事業者は、このようにして送信されたアンリンカブル認証データを受信して、被認証者の特定を行う（例えば、無線ＬＡＮサービスを利用したユーザを特定する事業者に認証データを送付した場合、この事業者は被認証者の特定を行う事により、その利用状況により課金を行う）。
尚、グループ管理事業者、検証補助事業者、被認証者特定事業者は、異なる事業者であっても、同一事業者であってもよい。
【０１００】
また、匿名認証システムの場合には、例えば、認証補助装置は認証補助を行う事業者（以下、認証補助事業者と呼ぶ）によって運営される。なお、グループ管理事業者と認証補助事業者は、同一事業者であってもよい。
【０１０１】
［実施形態１の動作説明］
次に、上記実施形態１である匿名認証システムにおける動作について詳説する。ここでは、Ｅｌ  Ｇａｍａｌ暗号方式およびＥｌ  Ｇａｍａｌ署名方式を用いて、以下に示す、登録処理、認証処理、および被認証者特定処理が実施されるものとする。
【０１０２】
尚、ここでは、グループの暗号化鍵をｅｎｃ＿ｇ＿ｉとし、Ｅｌ  Ｇａｍａｌ暗号の暗号化鍵ｅｎｃ＿ｇ−ｉ＝(ｑ，ｇ，Ｘ＿ｉ)は予め公開されているものとする。また、この暗号化鍵に対応する復号鍵（ｄｅｃ＿ｇ−ｉ）をｄｅｃ＿ｇ＝(ｘ＿ｉ)とし、さらに、グループに加入しようとするユーザＵは、Ｅｌ  Ｇａｍａｌ署名の署名鍵（ｓｋ＿ｕ＝(ｘ＿ｕ)）、およびこの署名鍵に対応する検証鍵（ｖｋ＿ｕ＝(ｐ，ｇ＿ｓ，ｙ)）を有するものとする。
【０１０３】
まず、認証処理に先立って行われる入会登録処理（事前登録処理）について、図７のフローチャートに基づき説明する。
【０１０４】
ここでは、上述のように、署名鍵ｓｋ＿ｕ、および検証鍵ｖｋ＿ｕを有する被認証者装置（ユーザＵ）２０が登録を行うものとして説明する。
尚、ユーザＵの署名鍵・検証鍵ペア（ｓｋ＿ｕ，ｖｋ＿ｕ）は、予めＩＣカードやフラッシュメモリなどのメモリ機器に予め格納されており、被認証者装置２０はこのメモリ機器にアクセスするためのインターフェースを有しているものとする。
【０１０５】
まず、ユーザＵにより上記署名鍵・検証鍵からなるペア鍵（ｓｋ＿ｕ，ｖｋ＿ｕ）が被認証者装置２０に入力される（ＲＥＧ１０）。
登録要求部２０−１は、入力された検証鍵ｖｋ＿ｕに基づき登録要求（ｒｅｑ＿ｒ）を生成すると共に、この登録要求（ｒｅｑ＿ｒ）をグループ管理装置１０に送信する（ＲＥＧ２０）。
尚、登録要求（ｒｅｑ＿ｒ）には、ユーザＵの検証鍵ｖｋ＿ｕおよび、ユーザＵの住所、
氏名、年齢など、登録に必要な個人情報が含まれているものとする。
【０１０６】
次いで、登録要求（ｒｅｑ＿ｒ）を受信した登録処理部１０−１は、ユーザＵに対する固有のＩＤであるユーザＩＤ（ＩＤ＿ｕ）を発行すると共に、このＩＤ＿ｕを被認証者装置２０に送信する（ＲＥＧ３０）。
【０１０７】
ここで、検証鍵および個人情報の登録に何らかの条件（性別制限、年齢制限、２重登録禁止など）が予め設定されている場合、登録処理部１０−１は、登録要求（ｒｅｑ＿ｒ）の内容に基づき、登録処理部１０−１が審査を行うものとする。
このとき、条件を満たさないユーザＵからの登録要求であった場合、登録処理部１０−１は、登録不可を示すメッセージを被認証者装置２０に対して送信する設定であってもよい。尚、ユーザが登録不可であった場合、そのユーザに対する以降のやり取りは中止する。
【０１０８】
登録処理部１０−１は、メンバー登録情報記憶装置１０−２からメンバリスト（Ｌｉｓｔ）を取得すると共に、メンバリスト（Ｌｉｓｔ）に（ＩＤ＿ｕ，ｒｅｑ＿ｒ）を追記し、更新されたメンバリスト（Ｌｉｓｔ）をメンバー登録情報記憶装置１０−２に格納する（ＲＥＧ４０）。
【０１０９】
また、ユーザＩＤ（ＩＤ＿ｕ）を受信した被認証者装置２０は、(ＩＤ＿ｕ，(ｓｋ＿ｕ，ｖｋ＿ｕ))を、ＩＤ・鍵ペア記憶装置２０−２に記憶する（ＲＥＧ５０：登録終了）。
【０１１０】
次に、本実施形態における認証処理（１）の動作について、図８のフローチャートに基づき説明する。
ここでは、ユーザＵが、署名鍵（ｓｋ＿ｕ）および検証鍵（ｖｋ＿ｕ）の登録を済ませており、このため、ＩＤ・鍵ペア記憶装置２０−２には、（ＩＤ＿ｕ，(ｓｋ＿ｕ，ｖｋ＿ｕ)）が予め記憶されているものとする。
【０１１１】
まず、被認証者装置２０の認証要求部２０−３は、検証装置３０に対して認証要求（ｒｅｑ＿ａ）を送信する（ＡＵＴ１０）。
次いで、チャレンジ生成部３０−１は、送り込まれた認証要求ｒｅｑ＿ａに応じて、ランダムなメッセージであるチャレンジ（ｎｏｎｃｅ）を選出生成し、被認証者装置２０に返信する（ＡＵＴ２０）。
【０１１２】
尚、本実施形態においては、上記ＡＵＴ１０およびＡＵＴ２０を省略した設定であってもよい。この場合、チャレンジｎｏｎｃｅに代えて、被認証者装置２０により選ばれた任意のメッセージ（ｍ）を利用するものとする。また、この場合、認証データ（ｒｅｓｐｏｎｓｅ）を署名データとする。
更に、この場合、署名データは、グループの復号鍵（ｄｅｃ＿ｇ）を入力として持たない検証装置に対しては、グループに所属するメンバーの署名であることしか伝わらないが、被認証者特定装置により署名したメンバーのＩＤを特定することが可能である。
【０１１３】
次いで、チャレンジ（ｎｏｎｃｅ）を受信した署名生成部２０−４は、ＩＤ・鍵ペア記憶装置２０−２に記憶された書名鍵（ｓｋ＿ｕ）を利用して、チャレンジ（ｎｏｎｃｅ）に対するユーザＵの署名データ（σ）を生成する（ＡＵＴ３０）。
【０１１４】
次に、認証データ生成部２０−５は、被認証者が指定する被認証者特定装置を示す論理構造情報、および、グループの暗号化鍵ｅｎｃ＿ｇ−１〜ｅｎｃ＿ｇ−ｔを取得した場合に、ユーザＩＤと署名データからなるデータ（ＩＤ＿ｕ｜｜σ）を暗号化して、暗号文Ｃを生成する。
さらに、認証データ生成部２０−５は、この暗号文Ｃを含む、認証データ（ｒｅｓｐｏｎｓｅ）を検証装置３０に対して送信する（ＡＵＴ４０）。
【０１１５】
認証データｒｅｓｐｏｎｓｅを受信した検証補助要求部３０−２は、暗号文Ｃを含む検証補助要求データ（ｒｅｑ＿ｖ）を、論理構造情報に示される検証補助装置（４０−１〜４０−ｔのいずれか）それぞれに対して送信する（ＡＵＴ５０）。
【０１１６】
ここでは、検証補助装置４０−ｉそれぞれが単独で暗号文Ｃを復号可能である場合について、説明する。
尚、検証補助装置４０−ｉが単独で暗号文Ｃを復号できず、暗号文Ｃを復号するためには他の検証補助装置との連携処理を行う必要がある場合は、認証データ復号部４０−ｉ−１は他の検証補助装置の認証データ復号部との相互通信および連携処理を行うことにより暗号文Ｃの復号化処理を行うものとする。
【０１１７】
認証データ復号部４０−ｉ−１は、検証補助要求データ（ｒｅｑ−ｖ）とグループの復号鍵（ｄｅｃ＿ｇ−ｉ）を受信すると共に、検証補助要求データ（ｒｅｑ−ｖ）に含まれる暗号文Ｃを復号する処理を行うと共に、復号処理の結果得られた復号データを（ＩＤ｜｜σ）へとパースする、つまり、復号データをＩＤとσとに分解する（ＡＵＴ６０）。
【０１１８】
次に、署名検証部４０−ｉ−２が、グループ管理装置１０のメンバー登録情報記憶装置１０−２からメンバリストを受信した場合に、このメンバリスト内に上記パースにより得られたＩＤが記載（登録）されているか否かを判定する。
【０１１９】
ここで、ＩＤが記載されていない場合、署名検証部４０−ｉ−２は「不受理」であることを示す検証補助データａｎｓ＿ｖを生成し、検証装置３０に送信する。
一方、ＩＤが記載されている場合、署名検証部４０−ｉ−２は、このＩＤに対応する検証鍵（ｖｋ）を用いて、署名データ（σ）の検証を行う（署名検証）。
この署名検証の結果（受理または不受理を示す）を、検証補助データ（ａｎｓ＿ｖ）として検証装置３０に送信する（ＡＵＴ７０）。
【０１２０】
次いで、検証装置３０の検証部３０−３は、すべての検証補助装置から送り込まれた署名検証結果が「受理」を示す場合に、検証補助データ（ａｎｓ＿ｖ）を受信し、認証結果（ｒｅｓｕｌｔ）を生成して出力する。すなわち、すべての検証補助データ（ａｎｓ＿ｖ）が受理を示すものであった場合に、認証成功を示す認証結果（ｒｅｓｕｌｔ）を生成し、この認証データを、認証データ記憶装置３０−４に記憶する（ＡＵＴ８０）。
【０１２１】
また、検証部３０−３は、異なる検証補助装置それぞれから送り込まれた署名検証結果の中に「不受理」を示す検証補助データ（ａｎｓ＿ｖ）が１つでも含まれる場合には、認証失敗を示す認証結果（ｒｅｓｕｌｔ）を生成する
尚、検証部３０−３は、認証失敗を示す認証データを認証データ記憶装置３０−４に格納する設定であってもよい。
【０１２２】
このとき、被認証者装置２０のＩＤに関する情報はグループの暗号化鍵 ｅｎｃ＿ｇ−1〜ｅｎｃ＿ｇ−t によって暗号化されているため、グループの復号鍵 ｄｅｃ＿ｇ−１〜ｄｅｃ＿ｇ−ｔを入力として持たない検証装置３０には、被認証者装置２０のＩＤに関する情報は、２つの認証データが同じ被認証者によるものか異なる被認証者によるものかという情報すら伝わらない。
【０１２３】
グループの復号鍵ｄｅｃ＿ｇ−ｉを入力として受け取る検証補助装置４０−ｉでは、検証装置３０から受け取った検証補助要求データｒｅｑ＿ｖに含まれる暗号文Ｃを、グループの復号鍵ｄｅｃ＿ｇ−iを用いて復号し、ＩＤおよび署名データσを得る。
検証補助装置４０−ｉでは、ＩＤがメンバリストＬｉｓｔに含まれ、かつ、ＩＤに対応する検証鍵を用いて署名データσを検証すると受理されることを確認する。
【０１２４】
したがって、登録されていないユーザ、すなわちメンバリストに登録されている検証鍵に対応した署名鍵を持たないユーザは、メンバリストに含まれる検証鍵を用いて受理される署名データを生成することが不可能であるため、認証を成功させることが不可能となり、さらに、グループを管理する管理者であっても、メンバリストＬｉｓｔに登録されている検証鍵に対応した署名鍵を知らないため、認証を成功させることが不可能であるため、
セキュリティを確保することができる。
【０１２５】
［被認証者を特定する処理（被認証者特定処理）］
次に、認証データから被認証者の特定を行う（被認証者特定処理）動作について、図９のフローチャートに基づき説明する。
尚、ここでは、被認証者特定装置５０−ｉが単独で被認証者を特定できることとして説明する。また、検証装置３０の備える認証データ記憶装置３０−４に記憶されている、認証データ（ｒｅｓｐｏｎｓｅ＿ｊ）を生成した被認証者のＩＤを特定する。
【０１２６】
尚、被認証者特定装置５０−ｉが単独で被認証者を特定できず、他の被認証者特定装置と協力する。ここで、特定することが可能である場合は、被認証者特定装置５０−ｉは他の被認証者特定装置と相互通信を行い、被認証者装置の特定処理を実施するものとする。
【０１２７】
ここでは、認証データ記憶装置３０−４に記憶されている認証データ（ｒｅｓｐｏｎｓｅ＿ｊ）を受信した被認証者特定要求部３０−５が、被認証者特定要求データ（ｒｅｑ＿ｔ）を被認証者装置５０−ｉに送信する（ＴＲＡ１０）。
尚、被認証者特定要求データ（ｒｅｑ＿ｔ）は、認証データ（ｒｅｓｐｏｎｓｅ＿ｊ）を含むものとする。
【０１２８】
次に、認証データ復号部５０−ｉ−１は、被認証者特定要求データ（ｒｅｑ＿ｔ）、およびグループの復号鍵（ｄｅｃ＿ｇ）を受信した場合に、認証データ（ｒｅｓｐｏｎｓｅ＿ｊ）に含まれる暗号文（Ｃ＿ｊ）を復号し、これにより得られた復号データをＩＤ＿ｊ||σ＿ｊにパースする（ＴＲＡ２０）。
【０１２９】
次に、被認証者特定部５０−ｉ−２は、グループ管理装置１０の具備するメンバー登録情報記憶装置１０−２に記憶されているメンバリスト（Ｌｉｓｔ）を取得すると共に、復号されたＩＤ＿ｊ がメンバリスト（Ｌｉｓｔ）に記載されているか否かの確認判定を行う。
ここで、ＩＤ＿ｊがメンバリストに記載されている場合、ＩＤ＿ｊに対応して設定された検証鍵（ｖｋ＿ｊ）を用いて、署名データ（σ＿ｊ）の検証を行う（ＴＲＡ３０）。
【０１３０】
この検証結果が「受理」を示すものであった場合（ＯＫ）、被認証者特定部５０−ｉ−２は、認証データ（ｒｅｓｐｏｎｓｅ＿ｊ）がＩＤ＿ｊを持つユーザにより作成された認証データであると判定し、特定された被認証者のＩＤであるＩＤ＿ｊの出力を行う。
【０１３１】
ＩＤ＿ｊがメンバリスト（Ｌｉｓｔ）に記載されていない、あるいは、署名データ（σ＿ｊ）の検証結果が不受理であった場合、被認証者特定部５０−ｉ−２は、被認証者特定を要求された認証データ（ｒｅｓｐｏｎｓｅ＿ｊ）は受理されない認証データであると判定し、検証装置３０に対して返す
示すメッセージを出力する
（被認証者特定処理終了）。
【０１３２】
以上のように、本実施形態（実施形態１）では、匿名性を剥奪できる被認証者特定者を１人または複数人指定できる構成であるため、被認証者の匿名性を確保しつつ、被認証者からの認証要求に対して、この被認証者が特定のグループに所属しているか否かを確実に認証判定することができる。
【０１３３】
更には、一定期間内における連続した認証要求や、一定回数以上の連続した認証要求に対しても、それが同一の被認証者による認証要求であるか、別の被認証者による認証要求であるかを判別（特定）することなく、つまり、被認証者の特定を行うことなく、認証処理を行うことができる。
【０１３４】
［実施形態２］
次に、本発明に係る実施形態２の匿名認証システムについて、説明する。ここで、前述した実施形態１と同一の部分については、同一の符号を付するものとする。
この実施形態２は、実施形態１における検証補助装置４０−１、４０−２〜４０−ｔに代えて、認証補助装置６１−１、６１−２、・・・６１−ｔを備えた点が実施形態１の場合と相違する。
以下これを詳述する。
【０１３５】
本発明の実施形態２としての匿名認証システムは、図１０に示すように、グループに属する被認証者装置に係る情報を管理するグループ管理装置１０、グループ管理装置１０に対して認証要求を行う被認証者装置２１（被認証者装置２０に対応（図１））と、上記認証要求時に認証データの生成補助を行う認証補助装置６１−１、６１−２、・・・６１−ｔと、認証要求を行った被認証者装置２１のユーザが上記グループに所属している否かの検証を行う検証装置３１（検証装置３０に対応（図１））と、被認証者装置２１におけるユーザＩＤ被認証者を特定する処理を行うと共に予め設定された条件に基づきグループ内における被認証者装置２０の匿名性（ユーザＩＤの秘匿性）を剥奪する制御を行う被認証者特定装置５０−１、５０−２、・・・、５０−ｔを備えた構成を有する。
【０１３６】
ここで、各グループに対応したグループの暗号化鍵（ｅｎｃ＿ｇ−１〜ｅｎｃ＿ｇ−ｔ）がユーザにより被認証者装置２０に入力されるものとする。
また、グループの暗号化鍵ｅｎｃ＿ｇ−ｉに対応したグループの復号鍵ｄｅｃ＿ｇ−ｉが、認証補助装置６１−ｉ（６１−１〜６１−ｔそれぞれを示す）および被認証者特定装置５０−ｉ（５０−１〜５０−ｔそれぞれを示す）それぞれに入力され、予め保持しているものとする。
尚、これらの暗号化鍵および復号鍵からなる鍵ペアは、グループごとに複数個存在するものとする。
【０１３７】
被認証者装置２１は、図１１に示すように、グループ管理装置１０に登録要求メッセージを送信する登録要求部２１−１と、グループ管理装置１０によって割り振られたユーザＩＤとユーザの署名鍵および検証鍵ペアとを対応付けて記憶するＩＤ・鍵ペア記憶装置２１−２と、検証装置３１に対して認証要求を示す認証要求メッセージを送信する認証要求部２１−３と、認証データが生成される際にユーザの署名鍵を用いて署名生成を行う署名生成部２１−４と、グループの暗号化鍵を取得しこれにより暗号文を生成すると共に認証に対して認証補助要求データを送信する認証補助要求部２１−５と、認証補助装置６１−ｉから認証補助データを受信した場合に、これに基づき認証データを生成する認証データ生成部２１−６を有する。
【０１３８】
認証補助装置６１−ｉは、図１２に示すように、被認証者装置２１からの認証補助要求とグループの復号鍵（ｄｅｃ＿ｇ−ｉ）を取得した場合に暗号文の復号を行う復号部６１−ｉ−１と、グループ管理装置１０からメンバリストを受信した場合に復号された署名データの検証を行う署名検証部６１−ｉ−２と、グループの署名鍵を受信した場合に、暗号文にグループの署名を施すグループの署名生成部６１−ｉ−３を備えた構成を有する。
【０１３９】
検証装置３１は、図１３に示すように、被認証者装置２１からの認証要求を受信した場合にこれに対するチャレンジを生成するチャレンジ生成部３１−１と、受信した認証データおよびグループの検証鍵に基づき検証を行う検証部３１−２と、検証部３１−２における認証（検証）処理の履歴として、認証データを記憶保持する認証データ記憶装置３１−３と、認証データ記憶装置３１−３に記憶されている認証データに対して、匿名性剥奪要求を被認証者特定装置に送信する被認証者特定要求部３１−４を有する。
【０１４０】
［実施形態２の動作説明］
次に、上記実施形態２である匿名認証システムにおける動作について、図１４のフローチャートに基づき説明する。
尚、上記登録処理、および認証データから被認証者の特定を行う処理は実施形態１と同様であるものとする。
【０１４１】
ここでは、上述のように、署名鍵ｓｋ＿ｕ、および検証鍵ｖｋ＿ｕを有する被認証者装置（ユーザＵ）２１が、実施形態１の場合と同様に、登録を行っているものとして説明する。
尚、ユーザＵの署名鍵・検証鍵ペア（ｓｋ＿ｕ，ｖｋ＿ｕ）は、予めＩＣカードやフラッシュメモリなどのメモリ機器に予め格納されており、被認証者装置２１はこのメモリ機器にアクセスするためのインターフェースを有しているものとする。
【０１４２】
まず、被認証者装置２１の認証要求部２１−３が、検証装置３１に対して認証要求（ｒｅｑ＿ａ）を送信する（ＡＵＴ１１）。認証要求（ｒｅｑ＿ａ）を受信したチャレンジ生成部３１−１は、ランダムなメッセージであるチャレンジ（ｎｏｎｃｅ）を選出して被認証者装置２１に送信する（ＡＵＴ２１）。
【０１４３】
署名生成部２１−４は、チャレンジ（ｎｏｎｃｅ）を受信した場合に、ＩＤ・鍵ペア記憶装置２１−２に記憶されているｓｋ＿ｕを用いて、チャレンジ（ｎｏｎｃｅ）に対するユーザＵの署名データ（σ）を生成する（ＡＵＴ３１）。
【０１４４】
次いで、認証補助要求部２１−５は、被認証者特定者を指定する論理構造およびグループの暗号化鍵（ｅｎｃ＿ｇ−１，・・・，ｅｎｃ＿ｇ−ｔ）を受信した場合に、ＩＤ＿ｕ｜｜σを暗号化し、暗号文Ｃを生成し、更に、認証補助要求部２１−５は、暗号文Ｃを含む、認証補助要求データ（（ｒｅｑ＿ｈ））を生成すると共に認証補助装置（６１−１〜６１−ｔ）に送信する（ＡＵＴ４１）。
【０１４５】
尚、ここでは、認証補助装置６１−ｉが単独で暗号文Ｃを復号できることとして説明する。
また、認証補助装置６１−ｉが単独で暗号文Ｃを復号できず、暗号文Ｃを復号するためには他の認証補助装置と相互協力する必要がある場合は、復号部６１−ｉ−１は他の認証補助装置の復号部と協力して暗号文Ｃの復号を行うものとする。
【０１４６】
次いで、認証補助装置６１−ｉの復号部６１−ｉ−１は、認証補助要求データ（ｒｅｑ＿ｈ）とグループの復号鍵（ｄｅｃ＿ｇ−ｉ）を受信した場合に、認証補助要求データ（ｒｅｑ＿ｈ）に含まれる暗号文Ｃを復号し、復号データを（ＩＤ｜｜σ）とパースする（ＡＵＴ５１）。
【０１４７】
次に、メンバリストを受信した署名検証部６１−ｉ−２が、グループ管理装置１０のメンバー登録情報記憶装置１０−２に記憶されているＩＤがメンバリストに記載されているか確認する。
ここで、ＩＤがメンバリストに記載されていた場合、ＩＤに対応する検証鍵（ｖｋ）を用いて署名データ（σ）の検証を行う（ＡＵＴ６１）。
【０１４８】
ここで、ＩＤがメンバリストに記載されていない、あるいは、（σ）の検証結果が不受理を示す場合、以降の動作を停止する（不受理：ＡＵＴ６１）。
【０１４９】
一方、ＩＤがメンバリストに記載されている、かつ、ＩＤに対応する検証鍵（ｖｋ）を用いて（σ）が受理された場合、グループの署名鍵（ｓｋ＿ｇ）を受信したグループの署名生成部６１−ｉ−３は、暗号文Ｃにグループの署名鍵（ｓｋ＿ｇ）を用いて署名を施し、署名データ（σ＿ｇ）を生成する。
【０１５０】
さらに、署名データ（σ＿ｇ）を含む認証補助データ（ａｎｓ＿ｈ）を被認証者装置２１に送信する（ＡＵＴ７１）。
次いで、認証補助データ（ａｎｓ＿ｈ）を受信した認証データ生成部２１−６は、すべての検証結果が「受理」を示す場合に、認証補助データ（ａｎｓ＿ｈ）に含まれる署名（σ＿ｇ）を含む認証データ（ｒｅｓｐｏｎｓｅ）を検証装置３１に送信する（ＡＵＴ８１）。
一方、受信した検証結果中にひとつでも「不受理」を示すものがあった場合、処理動作を停止するものとする。
【０１５１】
次に、認証データ（ｒｅｓｐｏｎｓｅ）およびグループの検証鍵（ｖｋ＿ｇ）を受信した検証部３１−２は、認証データに含まれる署名（σ＿ｇ）の検証を行う。
ここで、この検証結果が受理であった場合に、検証部３１−２は、認証結果（ｒｅｓｕｌｔ）を認証成功として出力し、認証データ（ｒｅｓｐｏｎｓｅ）を認証データ記憶装置３１−３に保存する（ＡＵＴ９１）。
【０１５２】
また、検証結果が不受理であった場合、検証部３１−２は、認証失敗を示す認証結果（ｒｅｓｕｌｔ）を出力する。
尚、認証が失敗した認証データも、認証データ記憶装置３１−３に格納する設定であってもよい。
【０１５３】
次に、本発明に係る実施形態３の匿名認証システムについて、説明する。ここで、前述した実施形態１および２と同一の部分については、同一の符号を付するものとする。
この実施形態３は、実施形態１の実施形態に対して実施形態２で示した認証補助装置６１−ｉを組み込んだ点が実施形態１、２の場合と相違する。
以下これを詳述する。
【０１５４】
本発明の実施形態３としての匿名認証システムは、図１５および１６に示すように、グループに属する被認証者装置に係る情報を管理するグループ管理装置１０、グループ管理装置１０に対して認証要求を行う被認証者装置２１（被認証者装置２０に対応（図１））と、上記認証要求時に認証データの生成補助を行う認証補助装置（６２：図１５）６２−１、６２−２、・・・６２−ｔと、認証要求を行った被認証者装置２１のユーザが上記グループに所属している否かの検証を行う検証装置３０と、検証装置３０による検証の補助を行う検証補助装置（４２：図１５）４２−１、４２−２〜４２−ｔと、被認証者装置２１におけるユーザＩＤ被認証者を特定する処理を行うと共に予め設定された条件に基づきグループ内における被認証者装置２０の匿名性（ユーザＩＤの秘匿性）を剥奪する制御を行う被認証者特定装置５０−１、５０−２、・・・、５０−ｔを備えた構成を有する。
【０１５５】
また、本実施形態３においても、実施形態１および２と同様に、グループに対応したグループの暗号化鍵（ｅｎｃ＿ｇ−ｉ）が被認証者装置６２−ｉに入力され、各グループの暗号化鍵（ｅｎｃ＿ｇ−ｉ）に対応したグループの復号鍵（ｄｅｃ＿ｇ−ｉ）が、認証補助装置６２−ｉおよび被認証者特定装置５２−ｉに入力されるものとする。
また、これらの暗号化・復号鍵は、グループごとに存在し、さらに、認証用共有鍵（ｃｋ＿ｇ）が、認証補助装置（６２−１〜６２−ｔ）および検証補助装置（４２−１〜４２−ｔ）に入力されるものとする。
【０１５６】
認証補助装置６２−ｉは、図１７に示すように、被認証者装置２１からの認証補助要求とグループの復号鍵（ｄｅｃ＿ｇ−ｉ）を受信した場合に、暗号文の復号を行う復号部６２−ｉ−１と、グループ管理装置１０から取得したメンバリストに基づき署名の検証を行う署名検証部６２−ｉ−２と、認証用共有鍵を受信した場合に、暗号文にメッセージ認証子を付ける修理を行うメッセージ認証子生成部６２−ｉ−３を備えた構成を有する。
【０１５７】
検証補助装置４２−ｉは、図１８に示すように、検証補助要求を受信した場合に、この検証補助要求に含まれる暗号文につけられたメッセージ認証子の検証を行うメッセージ認証子検証部４２−ｉ−１を備えた構成を有する。
【０１５８】
［実施形態３の動作説明］
次に、上記実施形態３である匿名認証システムにおける動作について、図１９および２０のフローチャートに基づき説明する。
尚、上記登録処理、および認証データから被認証者の特定を行う処理は実施形態１と同様であるものとする。
【０１５９】
ここでは、上述の実施形態２と同様に、署名鍵（ｓｋ＿ｕ）、および検証鍵（ｖｋ＿ｕ）を有する被認証者装置（ユーザＵ）２１が、実施形態１の場合と同様に、登録を行っており、更に、ＩＤ・鍵ペア記憶装置２１−２には、(ＩＤ＿ｕ， (ｓｋ＿ｕ， ｖｋ＿ｕ))が予め記憶されてものとして説明する。
尚、ユーザＵの署名鍵・検証鍵ペア（ｓｋ＿ｕ，ｖｋ＿ｕ）は、予めＩＣカードやフラッシュメモリなどのメモリ機器に予め格納されており、被認証者装置２１はこのメモリ機器にアクセスするためのインターフェースを有しているものとする。
【０１６０】
まず、被認証者装置２１の認証要求部２１−３は、検証装置３１に認証要求（ｒｅｑ＿ａ）を送信する（ＡＵＴ１２）。
次に、認証要求（ｒｅｑ＿ａ）を受信したチャレンジ生成部３１−１が、ランダムなメッセージであるチャレンジ（ｎｏｎｃｅ）を、被認証者装置２１に送信する（ＡＵＴ２２）。
【０１６１】
チャレンジを受信した署名生成部２１−４は、ＩＤ・鍵ペア記憶装置２１−２に記憶されている（ｓｋ＿ｕ）を用いて、チャレンジに対するユーザＵの署名（σ）を生成する（ＡＵＴ３２）。
次に、認証補助要求部２１−５が、被認証者が指定する被認証者特定者の論理構造およびグループの暗号化鍵（ｅｎｃ＿ｇ−１，…，ｅｎｃ＿ｇ−ｔ）を受信した場合に、（ＩＤ＿ｕ｜｜σ）を暗号化し、これにより、暗号文Ｃを生成すると共に、暗号文Ｃを含む、認証補助要求データ（（ｒｅｑ＿ｈ））を認証補助装置６２−１〜６２−ｔに送信する（ＡＵＴ４２）。
【０１６２】
尚、ここでは、簡単のため、認証補助装置６２−ｉが単独で暗号文Ｃを復号することが可能であるものとして説明する。
また、認証補助装置６２−ｉが単独で暗号文Ｃを復号できず、暗号文Ｃを復号するためには他の検証補助装置と協力する必要がある場合は、復号部６２−ｉ−１は他の認証補助装置の復号部と相互協力して暗号文Ｃを復号するものとする。
【０１６３】
次いで、復号部（６２−ｉ−１）が、認証補助要求データ（（ｒｅｑ＿ｈ））とグループの復号鍵（ｄｅｃ＿ｇ−ｉ）を受信した場合に、認証補助要求データ（（ｒｅｑ＿ｈ））に含まれる暗号文Ｃを復号し、復号データを（ＩＤ｜｜σ）とパースする（ＡＵＴ５２）。
【０１６４】
次に、署名検証部６２−ｉ−２が、グループ管理装置１０のメンバー登録情報記憶装置１０−２に記憶されているメンバリストを取得すると共に、当該メンバリストにＩＤが記載されているか確認する。
ここで、ＩＤがメンバリストに記載されていた場合、ＩＤに対応する検証鍵（ｖｋ）を用いて書名（σ）の検証を行う。
一方、ＩＤがメンバリストに記載されていない、あるいは、署名データ（σ）の検証結果が不受理を示すものであった場合、以降の動作処理を停止する（ＡＵＴ６２）。
【０１６５】
ここで、ＩＤがメンバリストに記載されており、かつ、ＩＤに対応する検証鍵（ｖｋ）を用いて署名データ（σ）が受理された場合、認証用共有鍵（ｃｋ＿ｇ）を受信したメッセージ認証子生成部６２−ｉ−３は、暗号文Ｃのメッセージ認証子（ＭＡＣ＿Ｃ）を生成すると共に、(Ｃ， ＭＡＣ＿Ｃ)を含む認証補助データ（ａｎｓ＿ｈ）を被認証者装置２１に送信する（ＡＵＴ７２）。
【０１６６】
次いで、認証補助データ（ans_h）を受信した認証データ生成部２１−６は、認証補助データ（ａｎｓ＿ｈ）に含まれる、(Ｃ， ＭＡＣ＿Ｃ)を含む認証データ（ｒｅｓｐｏｎｓｅ）を検証装置３０に送信する（ＡＵＴ８２）。
認証データ（ｒｅｓｐｏｎｓｅ）を受信した検証補助要求部３０−２は、認証データに含まれる、(Ｃ， ＭＡＣ＿Ｃ)を含む検証補助要求データ（ｒｅｑ＿ｖ）を、検証補助装置４２−１〜４２−ｔに対して送信する（Ｂ（図２０）へ続くＡＵＴ９２）。
【０１６７】
次いで、検証補助要求データ（ｒｅｑ＿ｖ）と認証用共有鍵（ｃｋ＿ｇ）とを受信したメッセージ認証子検証部４２−ｉ−１は、検証補助要求データ（ｒｅｑ＿ｖ）に含まれる(Ｃ，ＭＡＣ＿Ｃ)の検証を行う。ここで、検証結果（受理または不受理）を検証補助データ（ａｎｓ＿ｖ）として、検証装置３０に送信する（ＡＵＴ１０２）。
【０１６８】
ここで、検証補助データ（ａｎｓ＿ｖ）を受信した検証部３０−３は、認証結果（ｒｅｓｕｌｔ）を生成し、出力する。
尚、すべての検証補助データ（ａｎｓ＿ｖ）が受理を示すものであった場合、検証結果（ｒｅｓｕｌｔ）は認証成功を、それ以外の場合、検証結果（ｒｅｓｕｌｔ）は認証失敗を示すものとする。
【０１６９】
ここで、検証部３０−３は、認証に成功した認証データを、認証データ記憶装置３０−４に格納する（ＡＵＴ１１２）。尚、認証が失敗した認証データも、認証データ記憶装置３０−４に記憶する設定であってもよい。
【０１７０】
［変形例］
尚、上記実施形態１、３において、認証データを受け取った検証装置３０は、被認証者２０（２１）が指定した被認証者特定者に対応する検証補助装置４０−ｉに対して、検証補助要求、あるいは認証補助要求を送付しており、また、実施例２、３においては、被認証者装置２１は、自らが指定する被認証者特定装置５０−ｉに対応する認証補助装置６２−ｉに対して、検証補助要求、あるいは認証補助要求を送付している。
【０１７１】
また、被認証者装置２０が、認証データに対して、「複数の暗号文に対して平文が同一であることのゼロ知識証明」を付与することにより、すべての被認証者特定者が被認証者を特定した結果が同一であることを保証したまま、検証補助要求あるいは認証補助要求を送付する検証補助装置あるいは認証補助装置をそれぞれ１台に減らすことが可能となる。
【０１７２】
また、認証データに、ゼロ知識証明を付与しなくてもシステムは動作するが、２名以上の被認証者の結託（協力）により、すべての被認証者特定者が被認証者を特定した結果が同じでなくすことが可能となる。
尚、本システムを導入するアプリケーションによって、すべての被認証者特定者が被認証者を特定した結果が同じである必要がなければ、ゼロ知識証明の付与を行わない設定であってもよい。
【０１７３】
以下、変形例における認証処理動作について、説明する。ここでは、実施形態１（図１）の構成内容に基づき認証処理が行われる場合について、説明する。
【０１７４】
尚、この変形例では、署名鍵（ｓｋ＿ｕ）、検証鍵（ｖｋ＿ｕ）を持つユーザＵが登録を済ませ、ＩＤ・鍵ペア記憶装置２０−２には、(ＩＤ＿ｕ， (ｓｋ＿ｕ， ｖｋ＿ｕ))が予め記憶されているものとして説明する。
まず、被認証者装置２０の認証要求部２０−３は、検証装置３０に認証要求（req_a）を送信する。こここで、認証要求（ｒｅｑ＿ａ）は、予め定められた定型文でよいものとする。
次いで、認証要求（ｒｅｑ＿ａ）を受信したチャレンジ生成部３０−１は、ランダムに選出した、ｎｏｎｃｅを被認証者装置２０に送信し、チャレンジ（ｎｏｎｃｅ）を受信した署名生成部２０−４は、ＩＤ・鍵ペア記憶装置２０−２に記憶されている（ｓｋ＿ｕ）を用いてチャレンジに対して署名を付与する処理を行う。
【０１７５】
ここで、署名生成部２０−４は、まず、集合Z_pからランダムにｋを選び、ｒ＝ｇ＿ｓ＾ｋを計算し、さらに、ｓ＝(Ｈ(ｎｏｎｃｅ)−ｘｒ)ｋ＾{−１}ｍｏｄ(ｐ−１)を計算する。
尚、この計算結果として、ｓ＝０が算出された場合は計算を初めからやり直すものとする。ここで、σ＝(ｒ， ｓ)を署名データとする。
【０１７６】
次に、認証データ生成部２０−５は、グループの暗号化鍵（ｅｎｃ＿ｇ−１＝(ｑ，ｇ，Ｘ＿１)，・・・，ｅｎｃ＿ｇ−ｔ＝(ｑ，ｇ，Ｘ＿ｔ)を受信した場合に、ランダムな値（ｒ）をＺ＿{ｑ}から選出する。
さらに、認証データ生成部２０−５は、Ｙ＝ｇ＾ｒ，Ｗ＿１＝(ＩＤ｜｜σ)Ｘ＿１＾ｒ，・・・，Ｗ＿ｔ＝(ＩＤ｜｜σ)Ｘ＿ｔ＾ｒを計算し、暗号文Ｃ＝(Ｙ，Ｗ＿１，・・・，Ｗ＿ｔ)とする。
【０１７７】
次に、認証データ生成部２０−５は、１＜ａ＜（ｑ−１）を満たすａをランダムに選び、(ＩＤ｜｜σ)＾ａ＝ｈとする。これにより、ＩＤ｜｜σ＝ｈ＾{１／ａ}となる。
【０１７８】
ここで、認証データ生成部２０−５は、ｂ＝１／ａと表記し、さらに、１＜μ＿ｒ， μ＿ｘ＜ｑ−１をランダムに選択すると共に、Ｖ＿Ｃ＝(Ｖ＿Ｙ＝ｇ＾{μ＿ｒ}，Ｖ＿１＝ｈ＾{μ＿ｘ}・Ｘ＿１＾{μ＿ｒ}，・・・，Ｖ＿ｔ＝ｈ＾{μ＿ｘ}・Ｘ＿ｔ＾{μ＿ｒ})を計算する。
【０１７９】
ここで、ｃ＝Ｈ(Ｃ，Ｖ＿Ｃ)、さらに、τ＿ｒ＝ｃ・ｒ＋μ＿ｒ，τ＿ｘ＝ｃ・ｂ＋μ＿ｘとする。また、認証データ（ｒｅｓｐｏｎｓｅ）＝(ｎｏｎｃｅ，Ｃ，Ｖ＿Ｃ，τ＿ｒ，τ＿ｘ，ｈ)を検証装置３０に送付する。
【０１８０】
次いで、認証データを受信した検証補助要求部３０−２は、暗号文Ｃを含む検証補助要求データ（ｒｅｑ＿ｖ）＝ｒｅｓｐｏｎｓｅを、検証補助装置４０−ｉに送信する。
【０１８１】
検証補助装置４０−ｉは、検証補助要求データ（ｒｅｑ＿ｖ）を受信した場合に、検証補助要求データ（ｒｅｑ＿ｖ）とグループの復号鍵（ｄｅｃ＿ｇ−ｉ）＝(ｘ＿ｉ)を受信する。
次いで、認証データ復号部４０−ｉ−１が、検証補助要求データ（ｒｅｑ＿ｖ）に含まれる暗号文Ｃ＝(Ｙ， Ｗ＿１，・・・，Ｗ＿ｔ)からＣ＿ｉ＝(Ｙ， Ｗ＿ｉ)を抜き出すと共に、このＣ＿ｉを復号する。
【０１８２】
ここで、検証補助装置４０−ｉは、まず、Ｔ＿ｉ＝Ｙ＾{ｘ＿ｉ}を計算する。
次に、Ｍ＝Ｗ＿ｉＴ＿ｉ＾{−１}を計算し、得られたメッセージ（Ｍ）を（ＩＤ｜｜σ）とパースする、つまり、ＭをＩＤ，σ＝(ｒ，ｓ)に分解する。
【０１８３】
次に、署名検証部４０−２は、グループ管理装置１０のメンバー登録情報記憶装置１０−２に記憶されているメンバリストを受信した場合に、メンバリストにＩＤが記載されているか確認する。
ここで、ＩＤが記載されていない場合、不受理である旨を検証補助データ（ａｎｓ＿ｖ）として検証装置３０に送信する。
一方、ＩＤ記載されている場合、署名検証部４０−２は、ＩＤに対応する検証鍵（ｖｋ＿ｕ＝(ｐ， ｇ＿ｓ， ｙ＿ｕ)）を用いて、署名データ（σ）の検証を行う（署名検証）。
【０１８４】
ここで、上記署名検証の動作内容について、説明する。
まず、署名検証部４０−２は、０＜ｒ＜ｐかつ０＜ｓ＜（ｐ−１）を確認する。次に、ｇ＿ｓ＾{Ｈ(ｎｏｎｃｅ)}＝ｙ＾ｒ  ｒ＾ｓ  mod pが成立することを確認する。
【０１８５】
このとき、署名検証部４０−２は、上記内容すべてが成立していた場合に「受理」を、そうでない場合には「不受理」を検証結果として設定する。
さらに、署名検証部４０−２は、１≦ｊ≦ｔの場合に（ただしｊはｉ以外であるものとする）、ｇ＾{τ＿ｒ}＝Ｙ＾ｃ・Ｖ＿Ｙ，ｈ＾{τ＿ｘ}・Ｘ＿ｊ＾{τ＿ｒ} ＝Ｗ＿ｊ＾{ｃ}・Ｖ＿ｊが成立するか否かを確認する。
ここで、署名検証部４０−２は、上記式内容のすべてが成立していた場合に「受理」を、そうでなかったら「不受理」とする。
次いで、署名検証部４０−２は、その署名検証結果（受理または不受理）を検証補助データ（ａｎｓ＿ｖ）として検証装置３０に送信する。
【０１８６】
このとき、検証補助データ（ａｎｓ＿ｖ）を受信した検証部３０−３は、検証補助データが受理であったら認証結果（ｒｅｓｕｌｔ）を認証成功として出力する。また、検証補助データのうち「不受理」が一つでも含まれている場合、認証結果を認証失敗として出力する。
【０１８７】
尚、検証部３０−３は、認証が成功した認証データを、認証データ記憶装置３０−４に格納する。ここで、認証が失敗した認証データについても、認証データ記憶装置３０−４に格納する設定であってもよい。
【０１８８】
以上のように、上記変形例では、被認証者がすべての暗号文に対して平文が同じであるということを示すゼロ知識証明を付与することにより、1つのグループの秘密鍵を保持していればすべての被認証者特定者が被認証者を特定した結果が同じ認証データであることを確認できる。
これにより、検証装置は複数の検証補助装置に検証補助要求を送信する必要がないため、例えば、被認証者と被認証者特定者の信頼関係と、検証者と検証補助者の信頼関係とが異なる場合、例えば、被認証者が１０人の被認証者特定者を指定した認証データを生成したが検証者が信頼できる検証補助装置が１台しかない場合などに、有効に適用することができる。
【０１８９】
以上のように、実施形態１〜３、および変形例に記載の匿名認証システムでは、匿名性を剥奪できる被認証者特定者を１人または複数人指定できる構成であるため、被認証者の匿名性を確保しつつ、被認証者からの認証要求に対して、この被認証者が特定のグループに所属しているか否かを確実に認証判定することができる。
また、被認証者によって指定された1人以上の被認証者特定者（被認証者特定装置）が必要に応じて被認証者を特定し、その匿名性を剥奪することができるため、被認証者のネットワーク利用規約に振る舞い反する振る舞いを有効に抑制することができる。
【０１９０】
更には、一定期間内における連続した認証要求や、一定回数以上の連続した認証要求に対しても、それが同一の被認証者による認証要求であるか、別の被認証者による認証要求であるかを判別（特定）することなく、つまり、被認証者の特定を行うことなく、認証処理を行うことができる。
【０１９１】
更に、本実施形態では、公開鍵暗号方式を用いることにより、復号に用いる復号鍵を持たない検証者に被認証者のＩＤに関する情報を与えることなく認証を行い、更には、グループ管理者に対してユーザのＩＤおよびパスワードを知らせることなく、認証を行うことができるため、これにより、グループ管理者によるユーザのなりすまし行為などを有効に抑制することができる。
【０１９２】
また、本発明の匿名認証システムでは、被認証者が２人以上の被認証者特定者を指定可能とする構成であることにより、被認証者装置の暗号化部において、２つ以上のグループ公開情報が記載されたリストを入力とし、それぞれのグループ公開情報と乱数を用いてＩＤの暗号化を行う。
さらに、暗号化に用いる共通の乱数を設定することにより、認証データのサイズ長を一定値内に抑制することができ、これにより、システムにおける認証処理に係る処理負荷を有効に軽減することができる。
【０１９３】
上述した実施形態については、その新規な技術的内容の要点をまとめると、以下のようになる。
尚、上記の実施形態の一部又は全部は、新規な技術として以下のようにまとめられるが、本発明は必ずしもこれに限定されるものではない。
【０１９４】
（付記１）
ユーザ装置からの要求に応じてユーザ登録を行うと共に当該登録ユーザのグループをメンバリストにより管理するグループ管理装置と、前記ユーザ装置から送り込まれた認証用データに対するユーザ認証判定を行う認証検証装置と、前記メンバリストに基づき前記ユーザ装置の特定を行うユーザ特定装置と、前記ユーザ認証判定に先立ち前記認証検証装置からの要求に応じて前記認証用データの検証を行う検証補助装置とを備えた匿名認証システムであって、
前記ユーザ装置は、
前記認証検証装置から送り込まれた認証開始応答を予め設定された秘密鍵を利用することによりユーザ署名を生成するユーザ署名生成部と、
自己であるユーザ特定装置を特定する処理を行う前記ユーザ特定装置と前記検証補助装置とをそれぞれ選択指定すると共に、当該選択指定されたユーザ特定装置および検証補助装置を示す特定装置指定情報を生成する特定装置指定部と、
前記グループに対応して設定されたグループ用暗号化鍵を利用して前記ユーザ識別子およびユーザ署名を暗号化した暗号文を生成すると共に当該暗号文および前記特定装置指定情報を含むデータを前記認証用データとして前記認証検証装置に送信する認証用データ生成送信部とを備え、
前記認証検証装置は、
前記認証用データから前記暗号文を抽出すると共に当該暗号文を前記特定装置指定情報に基づき前記選択指定された検証補助装置に対して転送する暗号文転送部と、
前記ユーザ装置を特定する必要が生じた場合に、前記特定装置指定情報で指定された前記ユーザ特定装置に対して利用者特定要求として送信する利用者特定要求部と、
前記検証補助装置から送り込まれた前記検証結果に基き前記ユーザ認証判定を行う認証判定部とを備え、
前記ユーザ特定装置は、
前記利用者特定要求に応じて前記ユーザ装置を特定し前記ユーザ装置を示すユーザ装置特定情報を前記認証検証装置に通知するユーザ装置特定通知機能を備え、
前記検証補助装置は、
予め設定された前記グループ用復号鍵を利用して前記暗号文を前記ユーザ署名およびユーザ識別子に復号する暗号文復号部と、
前記グループ管理装置から取得した前記メンバリストに前記ユーザ識別子が含まれる場合に、前記秘密鍵に対応して設定された公開鍵を利用して前記復号されたユーザ署名の検証を行うユーザ署名検証部とを備えたことを特徴とする匿名認証システム。
【０１９５】
（付記２）
付記１に記載の匿名認証システムにおいて、
前記前記認証検証装置の暗号文転送部は、前記ユーザ装置により選択指定された異なる複数の検証補助装置それぞれに対して前記暗号文を転送する複数転送機能を備え、
前記認証判定部は、前記異なる複数の検証補助装置それぞれから送り込まれた前記検証結果が全て検証成功を示す場合に前記ユーザ装置に対するユーザ認証判定の結果として認証成功を通知する判定成功通知機能を備えたことを特徴とした匿名認証システム。
【０１９６】
（付記３）
付記１に記載の匿名認証システムにおいて、
前記認証検証装置が、前記特定装置指定情報により指定された異なる複数の前記ユーザ特定装置に対して前記利用者特定要求を送信した場合に、前記利用者特定要求を受信したユーザ特定装置は、前記メンバリストに前記ユーザ識別子が含まれるか否かを判定するメンバリスト判定部と、
前記メンバリストに前記ユーザ識別子が含まれる場合に、公開鍵を利用して前記ユーザ署名の検証を行うユーザ特定処理部と、
前記利用者特定要求を受信した他のユーザ特定装置と前記ユーザ署名の検証成功を相互に認証した場合に、前記認証用データの作成者としての前記ユーザ装置の識別子を前記認証検証装置に通知する特定情報通知部とを備えたことを特徴とする匿名認証システム。
【０１９７】
（付記４）
付記２に記載の匿名認証システムにおいて、
前記検証補助装置は、グループ用復号鍵を用いて前記認証用データに含まれる暗号文を復号することにより前記認証用データに対応するＩＤおよび署名データを特定するＩＤ署名データ特定機能と、
前記グループ管理装置から取得したメンバリストに前記ＩＤおよび署名データが含まれるか否かの検証を行う検証判定機能とを備えたことを特徴とする匿名認証システム。
【０１９８】
（付記５）
付記１、２、又は３に記載の匿名認証システムにおいて、
前記認証検証装置は、前記ユーザ装置から一定回数以上の認証要求があった場合に、当該認証要求の送信元が秘匿された認証用データを生成する認証要求元秘匿機能を備えたことを特徴とする匿名認証システム。
【０１９９】
（付記６）
付記４に記載の匿名認証システムにおいて、
前記認証検証装置から前記認証用データが転送された場合に、当該認証用データを復号することによりＩＤおよび署名データを特定し、前記認証用データ生成したユーザが前記グループに属するか否かを前記グループ管理装置から取得した前記メンバリストと前記ＩＤおよび署名データとに基づき検証する認証補助装置を備えたことを特徴とする匿名認証システム。
【０２００】
（付記７）
ユーザ装置からの要求に応じてユーザ登録を行うと共に当該登録ユーザのグループをメンバリストにより管理するグループ管理装置と、前記ユーザ装置から送り込まれた認証用データに対するユーザ認証判定を行う認証検証装置と、前記ユーザ認証判定に先立ち前記認証検証装置からの要求に応じて前記認証用データの検証を行う検証補助装置とを備えた匿名認証システムにあって、前記ユーザ装置の認証を行う匿名認証方法であって、
前記ユーザ装置が、前記認証検証装置から送り込まれた認証開始応答を予め設定された秘密鍵を利用することによりユーザ署名を生成し、
前記グループに対応するグループ用暗号化鍵を利用して前記ユーザ識別子およびユーザ署名を暗号化した暗号文を生成すると共に、
前記１または複数の検証補助装置をそれぞれ選択指定することにより当該選択指定された検証補助装置を示す特定装置指定情報を生成し、
前記暗号文および前記特定装置指定情報を含む前記認証用データを前記認証検証装置に送信し、
前記認証検証装置は、前記ユーザ装置から送り込まれた前記認証用データから前記暗号文を抽出すると共に、前記特定装置指定情報に基づき前記ユーザ装置が指定した検証補助装置に対して前記暗号文を転送し、
前記検証補助装置は、予め設定された前記グループ用復号鍵を利用して前記暗号文を前記ユーザ署名およびユーザ識別子に復号し、
前記グループ管理装置から取得した前記メンバリストに前記ユーザ識別子が含まれる場合に、前記秘密鍵に対応して予め設定された公開鍵を利用して前記復号されたユーザ署名の検証を行うと共に当該検証結果を前記認証検証装置に対して通知し、
前記認証検証装置が、前記検証補助装置から送り込まれた前記ユーザ署名の検証結果に基き前記ユーザ認証判定を行うことを特徴とした匿名認証方法。
【産業上の利用可能性】
【０２０１】
本発明は、大規模コンピュータネットワークシステムにおけるグループメンバの認証判定を、ユーザのＩＤを秘匿した状態で行う認証システムに対して有用に適用することができる。
【符号の説明】
【０２０２】
１０  グループ管理装置
１０−１  登録処理部Б
１０−２  メンバー登録情報記憶装置
２０、２１  被認証者装置
２０−１、２１−１  登録要求部
２０−２、２１−２  ＩＤ・鍵ペア記憶装置
２０−３、２１−３  認証要求部
２０−４、２１−４  署名生成部
２１−５  認証補助要求部
２０−５、２１−６    複数被認証者特定者用認証データ生成部
３０、３１  検証装置
３０−１、３１−１  チャレンジ生成部
３０−２  検証補助要求部
３０−３、３１−２  検証部
３０−４、３１−３  認証データ記憶装置
３０−５、３１−４  被認証者特定要求部
３１  検証装置
４０  検証補助装置
４０−ｉ−１  認証データ復号部
４０−ｉ−２、６１−ｉ−２  署名検証部
４２、６２  検証補助装置
４２−ｉ  検証補助装置
４２−ｉ−１  メッセージ認証子検証部
５０  被認証者特定装置
５０−ｉ−１  認証データ復号部
５０−ｉ−２  被認証者特証部
６１−ｉ  検証補助装置
６１−ｉ−１、６２−ｉ−１  復号部
６１−ｉ−３  グループの署名生成部
６２−ｉ−２  署名検証部
６２−ｉ−３  メッセージ認証子生成部
【図１】
2012032952.tif 000003
【図２】
2012032952.tif 000004
【図３】
2012032952.tif 000005
【図４】
2012032952.tif 000006
【図５】
2012032952.tif 000007
【図６】
2012032952.tif 000008
【図７】
2012032952.tif 000009
【図８】
2012032952.tif 000010
【図９】
2012032952.tif 000011
【図１０】
2012032952.tif 000012
【図１１】
2012032952.tif 000013
【図１２】
2012032952.tif 000014
【図１３】
2012032952.tif 000015
【図１４】
2012032952.tif 000016
【図１５】
2012032952.tif 000017
【図１６】
2012032952.tif 000018
【図１７】
2012032952.tif 000019
【図１８】
2012032952.tif 000020
【図１９】
2012032952.tif 000021
【図２０】
2012032952.tif 000022