(57)【要約】【課題】公開鍵の大きさを小さくすることにより通信負荷を低減させた匿名認証システムを提供する。【解決手段】管理装置と、メンバ用装置と、認証装置とからなる匿名認証システムにおいて、管理装置には、メンバを複数のサブグループに分けて、サブグループ用ＩＤと個人用ＩＤとに基づいて生成した所属証明書を記憶した所属証明書用テーブルと、各サブグループの有効なメンバの個人用ＩＤを用いてアキュームレータにより定義された値を公開鍵として記憶した公開鍵用テーブルと、サブグループ用ＩＤにより特定されるサブグループの公開鍵とサブグループ用ＩＤとを用いて生成した補助証明書を記憶した補助証明書用テーブルとを設けて、メンバ用装置の記憶手段に、当該メンバ用の所属証明書と補助証明書を記憶させるとともに、公開鍵を記憶させることとした。【選択図】図２
2011114504.tif 000002
【特許請求の範囲】
【請求項１】
グループに所属するメンバにそれぞれ付与する所属証明書、失効状態のメンバの情報である失効情報、及び公開鍵を管理する管理手段を備えた管理装置と、
前記所属証明書を記憶する記憶手段、及びこの記憶手段に記憶された前記所属証明書を用いて署名を生成する署名生成手段を備えたメンバ用装置と、
前記メンバ用装置から送信されてきた前記署名を検証する検証手段を備えた認証装置と
からなるグループ署名システムにおいて、
前記管理装置には、
前記メンバを複数のサブグループに分けて、サブグループ用ＩＤと個人用ＩＤとに基づいて生成した前記所属証明書を記憶した所属証明書用テーブルと、
各サブグループの有効なメンバの個人用ＩＤを用いてアキュームレータにより定義された値を公開鍵として記憶した公開鍵用テーブルと、
前記サブグループ用ＩＤにより特定されるサブグループの公開鍵と前記サブグループ用ＩＤとを用いて生成した補助証明書を記憶した補助証明書用テーブルと
を設けて、前記メンバ用装置の前記記憶手段に、当該メンバ用の所属証明書と補助証明書を記憶させるとともに、前記公開鍵を記憶させているグループ署名システム。
【請求項２】
前記管理装置は、前記失効情報が更新されるたびに前記公開鍵用テーブルに記憶された前記公開鍵を更新する公開鍵更新手段を有する請求項１に記載のグループ署名システム。
【請求項３】
前記サブグループの数は、前記メンバの総数をＮとした場合に、Ｎ1/2以上で最小の整数とする請求項１または請求項２に記載のグループ署名システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、匿名認証システムに関するものであり、特に、グループ署名を利用した匿名認証システムに関するものである。
【背景技術】
【０００２】
インターネットなどのネットワークを利用したサービス提供においては、そのサービスを利用するユーザを管理するために、一般的にＩＤとパスワードを用いた個人認証が行われており、この個人認証をパスしたユーザのみにサービスを提供するようにしている。
【０００３】
この個人認証は、認証サーバと呼ばれる認証装置を用いて行われているが、認証サーバによる認証処理に基づいて、認証サーバには認証履歴がログとして蓄積されることとなっている。
【０００４】
この認証履歴は、どのユーザが、いつ、何をしたかといった情報で構成されており、この情報を解析することにより、ユーザのアクセス履歴などの個人情報の取得が可能であり、認証履歴の漏洩は、個人情報の漏洩と同じ意味合いを持っていることとなっている。
【０００５】
したがって、認証サーバでは、認証履歴が漏洩することを防止する必要があり、厳重な管理が求められている。
【０００６】
このような認証サーバにおける個人ユーザの認証履歴の蓄積を回避するために、匿名での認証を可能とする方法としてグループ署名が提案されている。
【０００７】
グループ署名では、各ユーザが所定のグループに所属していることを認証するものであり、認証の際にユーザを個々に特定することなく認証可能としている。
【０００８】
すなわち、グループ署名において、管理者は、個々のユーザを識別するためのＩＤを設けているが、ユーザにはそのＩＤに基づいて生成した所属証明書をＩＤの代わりに付与し、各ユーザは、個々の所属証明書に基づいて、所属証明書の所持をその所属証明書自体を漏らすことなく保証する署名を生成し、この署名を所定の認証サーバで検証している。
【０００９】
より具体的に説明すると、管理者は、管理上、ユーザｉのＩＤをxiとして管理しており、各ユーザ用の所属証明書Cert(xi)を生成して、この所属証明書Cert(xi)をユーザｉに付与している。
【００１０】
ユーザｉは、インターネットなどの電気通信回線を介して所定のサービスを受ける場合に、所属証明書Cert(xi)から生成した署名を認証サーバに送信し、認証サーバでは、公開鍵を用いて、送信されてきた署名が正しい署名であるかどうかを検証して、署名が正しければユーザｉの利用を許可することとしている。なお、署名からxiを特定できないことは、数学的に保証されている。また、管理者は、所定の公開鍵を公開している。
【００１１】
このように、認証サーバには、個人を特定できる秘密情報のxiではなく署名が蓄積されるだけであり、この署名からxiが特定できないという匿名性を有していることから、個人情報の漏洩の問題を解消可能となっている。
【００１２】
一方で、ユーザｉのＩＤであるxiを管理している管理者だけは、署名からユーザｉを特定でき、管理者だけが厳重な情報漏洩対策を施すことにより情報漏洩を防止でき、認証サーバにおける情報漏洩対策を不要として、管理コストを低減可能となっている。そして、不正行為などでユーザｉを特定する必要がある場合のみ、管理者がユーザｉを特定することにより、信頼性を維持可能としている。なお、グループ署名では、一般的に「ユーザ」を「メンバ」と称しており、本発明においては、「メンバ」の呼称を用いることとする。
【００１３】
しかしながら、このような匿名認証を可能とするグループ署名には、個々のメンバを特定しないことのデメリットとして、サービスの利用の停止を申告したメンバや、メンバとしての権限を剥奪されたメンバなどの失効者を特定することが困難となっていた。
【００１４】
すなわち、認証サーバに署名データを送信したメンバが、失効者であるかどうかを判断するための処理を、メンバを特定することなく行わなければならないからである。
【００１５】
このような、失効者を判別する失効処理を行う方法として、いくつかの方法が提案されている。
【００１６】
その一つとして、全メンバのＩＤの集合、すなわち、x1,・・・,xnを用いてアキュームレータによりf(x1,・・・,xn)＝ｙとして定義される値ｙをグループの公開鍵として用いるとともに、失効者が発生するごとにグループの公開鍵を更新し、更新されたグループの公開鍵に基づいて各メンバのアキュームレータに関する秘密鍵wjを更新させて、この新しい秘密鍵wjに基づいて署名を生成させる方法が提案されている（例えば、非特許文献１及び非特許文献２参照。）。
【００１７】
この場合には、失効の設定がされたメンバは秘密鍵wjを生成できないため、署名を生成して認証サーバで検証された際に正しい署名とは認識できず、失効者を確実に排除することができる。
【００１８】
この方式では、xiがアキュームレートされていることを保証するための演算負荷が、失効されたメンバの数に依存しないため、演算を高速化できることとなっている。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】Camenish, Lysyanskaya: Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. CRYPTO 2002, pp. 61-76, 2002.
【非特許文献１】Camenish, Kohlweiss, Soriente: An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. PKC 2009, pp. 481-500, 2009.
【発明の概要】
【発明が解決しようとする課題】
【００２０】
しかしながら、アキュームレータによりf(x1,・・・,xn)＝ｙとして定義される値ｙをグループの公開鍵として用いた場合には、グループの公開鍵に全メンバのＩＤを用いるため、大規模なグループを構成した際に公開鍵が極めて大きくなり、グループの公開鍵を各メンバに受け渡すための通信負荷が大きくなって、この通信負荷の影響が無視できなくなるおそれがあった。
【００２１】
そこで、本発明者は、公開鍵の大きさを小さくすることにより通信負荷を低減させるべく研究開発を行って本発明を成すに至ったものである。
【課題を解決するための手段】
【００２２】
本発明の匿名認証システムでは、グループに所属するメンバにそれぞれ付与する所属証明書、失効状態のメンバの情報である失効情報、及び公開鍵を管理する管理手段を備えた管理装置と、前記所属証明書を記憶する記憶手段、及びこの記憶手段に記憶された前記所属証明書を用いて署名を生成する署名生成手段を備えたメンバ用装置と、前記メンバ用装置から送信されてきた前記署名を検証する検証手段を備えた認証装置とからなる匿名認証システムにおいて、前記管理装置には、前記メンバを複数のサブグループに分けて、サブグループ用ＩＤと個人用ＩＤとに基づいて生成した前記所属証明書を記憶した所属証明書用テーブルと、各サブグループの有効なメンバの個人用ＩＤを用いてアキュームレータにより定義された値を公開鍵として記憶した公開鍵用テーブルと、前記サブグループ用ＩＤにより特定されるサブグループの公開鍵と前記サブグループ用ＩＤとを用いて生成した補助証明書を記憶した補助証明書用テーブルとを設けて、前記メンバ用装置の前記記憶手段に、当該メンバ用の所属証明書と補助証明書を記憶させるとともに、前記公開鍵を記憶させることとした。
【００２３】
また、本発明の匿名認証システムでは、管理装置が、失効情報が更新されるたびに公開鍵用テーブルに記憶された公開鍵を更新する公開鍵更新手段を有することにも特徴を有するものである。
【００２４】
さらに、本発明の匿名認証システムでは、サブグループの数を、メンバの総数をＮとした場合にＮ1/2以上で最小の整数とすることにも特徴を有するものである。
【発明の効果】
【００２５】
本発明によれば、メンバをサブグループに分けることにより公開鍵の鍵長を短くすることができ、公開鍵の通信負荷を低減して、高速に匿名認証を実行できる。
【００２６】
また、公開鍵の鍵長が短く成ることにより、公開鍵を用いた演算の速度を向上させることができ、演算処理の高速化をはかることもできる。
【００２７】
特に、メンバの総数をＮとした場合に、Ｎ1/2以上で最小の整数の数のサブグループを設けた場合には、各サブグループに所属するメンバの数をＮ1/2程度とすることができ、例えばメンバの総数が100万人の場合、サブグループのメンバの総数は1000人となって、最も高速に匿名認証を実行できる。
【図面の簡単な説明】
【００２８】
【図１】本実施形態に係る匿名認証システムのシステム構成説明図である。
【図２】本実施形態に係る匿名認証システムの動作シーケンスの説明図である。
【発明を実施するための形態】
【００２９】
本発明の匿名認証システムは、グループ署名を利用したものであり、図１に示すように、インターネットなどの電気通信回線10には、管理者が使用する管理装置20と、メンバが使用するメンバ用装置30と、認証処理を実行する認証装置40を接続して、メンバ用装置30で生成した署名の検証を認証装置40で行うこととしている。
【００３０】
管理装置20と、メンバ用装置30と、認証装置40は、それぞれ電子計算機で構成しており、電気通信回線10に接続可能としている。特に、管理装置20と認証装置40は、単一の電子計算機で構成する場合に限定するものではなく、複数台の電子計算機で構成してもよい。
【００３１】
また、図１では、管理装置20を、認証装置40から独立させて設けているが、管理装置20は必ずしも認証装置40から独立している必要はなく、管理装置20と認証装置40とを専用回線で接続し、認証装置40を経由させて管理装置20を電気通信回線10に接続させてもよい。
【００３２】
管理装置20には、グループに所属するメンバにそれぞれ付与する所属証明書、失効状態のメンバの情報である失効情報、及び公開鍵を管理する管理手段を設けている。
【００３３】
特に、メンバは複数のサブグループに分けおり、所属するサブグループのＩＤと、サブグループ内での個人用ＩＤとを一組として１人のメンバを特定するＩＤとしている。ここで、説明の便宜上、サブグループのＩＤをSjとし、サブグループ内での個人用ＩＤをxiで表すこととする。
【００３４】
管理装置20に設けた管理手段は、具体的には、サブグループ用ＩＤと個人用ＩＤとに基づいて生成した所属証明書を記憶した所属証明書用テーブルと、各サブグループの有効なメンバの個人用ＩＤを用いてアキュームレータにより定義された値を公開鍵として記憶した公開鍵用テーブルと、サブグループ用ＩＤにより特定されるサブグループの公開鍵とサブグループ用ＩＤとを用いて生成した補助証明書を記憶した補助証明書用テーブルである。
【００３５】
ここで、説明の便宜上、サブグループ用ＩＤであるSjと個人用ＩＤであるとxiに基づいて生成した所属証明書をCert(Sj,xi)と表すこととする。なお、ｉ＝1,2,・・・,m、ｊ＝1,2,・・・,kである。
【００３６】
所属証明書用テーブルには、全メンバのCert(Sj,xi)(ｉ＝1,2,・・・,m、ｊ＝1,2,・・・,k)を記憶している。
【００３７】
また、公開鍵用テーブルに記憶される公開鍵はサブグループごとに設けており、サブグループの有効なメンバの個人用ＩＤを用いてアキュームレータｆにより、f(x1,・・・,xn)＝yj(ｊ＝1,2,・・・,k)として定義し、公開鍵用テーブルに記憶している。
【００３８】
補助証明書用テーブル記憶している補助証明書は、サブグループ用ＩＤであるSjと、当該サブグループの公開鍵であるyjとから生成しており、説明の便宜上、補助証明書をCert(Sj,yj)と表すこととする。
【００３９】
上述したように、公開鍵は、サブグループの有効なメンバの個人用ＩＤを用いて生成しており、サービスの利用の停止を申告したメンバや、メンバとしての権限を剥奪されたメンバなどの失効者が発生した場合に、管理装置20は、公開鍵を更新している。
【００４０】
具体的に説明すると、例えば、x1,x2,x3,x4,x5の５人のメンバでサブグループを構成していた場合、公開鍵はf(x1,x2,x3,x4,x5)＝yであり、メンバx3が失効処理されると、管理装置20は、公開鍵更新手段によりf(x1,x2,x4,x5)＝y'として新たな公開鍵を生成し、この新たな公開鍵を公開鍵用テーブルに記憶させている。
【００４１】
さらに、公開鍵の更新にともなって、管理装置20では、公開鍵を用いて生成される補助証明書Cert(Sj,yj)を補助証明書更新手段により更新して、新たな補助証明書を補助証明書用テーブルに記憶させている。
【００４２】
公開鍵更新手段及び補助証明書更新手段は、それぞれ所定のプログラムであって、管理装置20での失効処理にともなって適宜起動させて、公開鍵及び補助証明書をそれぞれ更新している。
【００４３】
なお、管理装置20では、想定される最大のメンバ総数に基づいて所属証明書をあらかじめ準備しておき、所属証明書を付与していないメンバを失効者としておくことにより、メンバの増減に容易に対応できる。また、あらかじめ想定していたメンバの総数を超える人数のメンバを管理する必要が生じた場合には、サブグループ単位でメンバの総数を増やすことにより、比較的容易に対応できる。
【００４４】
メンバ用装置30には、管理装置20を管理している管理者から付与された当該メンバ用の所属証明書Cert(Sj,xi)及び補助証明書Cert(Sj,yj)を記憶するとともに、管理装置20で公開されている公開鍵yjを記憶する記憶手段と、この所属証明書Cert(Sj,xi)と補助証明書Cert(Sj,yj)と公開鍵を用いて署名を生成する署名生成手段を設けている。
【００４５】
ここで、所属証明書Cert(Sj,xi)と補助証明書Cert(Sj,yj)と公開鍵を記憶する記憶手段としては、一般的にはハードディスクであるが、ハードディスクに限定するものではなく、適宜の記憶装置であってもよい。特に、公開鍵は、署名の生成段階で電気通信回線10を介して管理装置20から取得して、適宜のメモリに記憶させてもよい。
【００４６】
また、本実施形態では、メンバ用装置30は、署名を生成する際に、管理装置20から公開鍵yjを取得することとして、失効情報が反映された公開鍵yjを用いて署名を生成することとしている。さらに、メンバ用装置30では、取得した公開鍵yjを用いて補助証明書Cert(Sj,yj)を更新し、更新された補助証明書Cert(Sj,yj)を用いて署名を生成することとしている。
【００４７】
署名生成手段は、メンバ用装置30で実行される所定のプログラムであって、記憶手段に記憶された所属証明書Cert(Sj,xi)と補助証明書Cert(Sj,yj)と公開鍵を用いて署名を生成している。特に、本実施形態では、ゼロ知識証明により所定の演算を行って署名を生成している。
【００４８】
メンバ用装置30は、電気通信回線10を介して生成した署名を認証装置40に送信している。
【００４９】
認証装置40には、メンバ用装置30から送信されてきた署名を検証する検証手段を設けている。
【００５０】
検証手段は、認証装置40で実行される所定のプログラムであって、メンバ用装置30から送信されてきた署名と、管理装置20で公開されている公開鍵を用いて、送信されてきた署名の真偽を判定し、送信されてきた署名が正しい署名である場合、当該メンバによる所定のサービスの利用を許可することとしている。
【００５１】
以下において、図２に示す説明図を用いて、本実施形態の匿名認証システムの動作について説明する。なお、以下においては、メンバ用装置30において署名を生成する際に公開鍵yjを取得する場合について説明する。
【００５２】
また、通常、メンバ用装置30が署名を生成する操作はバックグラウンド処理として行われ、メンバがメンバ用装置30を用いて所定のサービスを利用しようとした場合に、バックグラウンドにおいて実行される動作である。
【００５３】
ここで、管理装置20には、メンバxiがメンバとして登録されているものとし、メンバ用装置30の記憶手段には所属証明書Cert(Sj,xi)及び補助証明書Cert(Sj,yj)が記憶されているものとする。また、メンバ用装置30の記憶手段には、公開鍵yjも記憶されているものとする。
【００５４】
まず、メンバ用装置30において、メンバが所定のサイトへのアクセスを要求すると（ステップS101）、メンバ用装置30は、管理装置20に公開鍵yjを送信するように要求する（ステップS102）。
【００５５】
管理装置20は、要求に応じてメンバ用装置30に公開鍵yjを送信する（ステップS103）。なお、公開鍵yjは、管理装置20から取得する場合に限定するものではなく、認証装置40から取得してもよい。
【００５６】
メンバ用装置30は、取得した公開鍵yjが失効情報に基づいて更新された公開鍵yjである場合に、メンバ用装置30の記憶手段に記憶した公開鍵yjを更新し、補助証明書Cert(Sj,yj)を更新させる（ステップS104）。
【００５７】
次いで、メンバ用装置30は、所属証明書Cert(Sj,xi)と、更新した公開鍵yj及び補助証明書Cert(Sj,yj)を用いて署名を生成し（ステップS105）、生成した署名を認証装置40に送信する（ステップS106）。
【００５８】
認証装置40では、署名を受信すると、管理装置20に公開鍵yjを送信するように要求する（ステップS107）。管理装置20は、要求に応じて認証装置40に公開鍵yjを送信し（ステップS108）、取得した公開鍵yjを用いて署名の検証処理を実行する（ステップS109）。
【００５９】
認証装置40は、署名が正しい場合に、メンバによる所定のサイトへのアクセスを許可して（ステップS110）、当該サイトにアクセスさせている。
【００６０】
上述したように、本実施形態の匿名認証システムでは、メンバをサブグループに分けておくことにより、公開鍵yjの鍵長を短くすることができ、公開鍵yjの通信負荷を低減して、高速に匿名認証を実行できる。
【００６１】
また、公開鍵yjの鍵長が短くなることにより、公開鍵を用いた補助証明書Cert(Sj,yj)の送信処理を高速化できる。
【００６２】
特に、メンバの総数をＮとした場合に、Ｎ1/2以上で最小の整数の数のサブグループを設けた場合には、各サブグループに所属するメンバの数をＮ1/2程度とすることができ、例えばメンバの総数が100万人の場合、サブグループのメンバの総数は1000人となって、最も高速に匿名認証を実行できる。
【００６３】
しかも、個人ＩＤには、通常、拡大体の元が用いられるが、サブグループのＩＤと、サブグループ内の個人ＩＤとでメンバを特定することにより、個人ＩＤ用として必要となる拡大体の元の数を大きく削減できるので、これによっても演算の高速化をはかることができる。
【符号の説明】
【００６４】
10  電気通信回線
20  管理装置
30  メンバ用装置
40  認証装置
【図１】
2011114504.tif 000003
【図２】
2011114504.tif 000004