説明

擬似ランダム関数計算装置及び方法、並びに回数制限匿名認証システム及び方法

【課題】効率的な擬似ランダム関数及びそれを用いた効率的な回数制限匿名認証方式を実現する。
【解決手段】擬似ランダム関数計算装置1は、鍵生成手段2と、擬似ランダム関数計算手段3とを有する。鍵生成手段2は、有限群の元を成す要素として第一及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、秘密鍵を秘密鍵記憶部3に秘密裡に保管し、公開鍵を公開する。擬似ランダム関数計算手段3は、整数が入力されると、擬似ランダム関数の関数値として有限群の元を出力する。このとき、公開鍵の前記第一の要素を底とし、入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、公開鍵の第二の要素を底とし、秘密鍵と入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元との積を出力する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、擬似ランダム関数計算装置及び方法、並びに回数制限匿名認証システム及び方法に係り、特に効率的な擬似ランダム関数及びそれを用いた効率的な回数制限匿名認証方式に関する。
【背景技術】
【0002】
一方向性関数を用いて擬似ランダム関数を実現する方法が知られている(例えば、非特許文献5参照)が、この方法で実現した擬似ランダム関数fは、y=f(x)を満たすxの知識のゼロ知識証明を効率的に行うことはできない。y=f(x)を満たすxの知識のゼロ知識証明を効率的に行うことができれば、様々な暗号プロトコルを効率的に実現できるので、擬似ランダム関数で効率的なものが望まれる。
【0003】
一方、電子投票、電子現金、電子クーポン、回数制限付き視聴といった多くのアプリケーションでは、ユーザのプライバシーを守るため、ユーザが匿名でこれらのアプリケーションを使える必要がある。しかも、これらのアプリケーションでは、これと同時に、ユーザがアプリケーションを使用できる回数を制限する必要がある。
【0004】
回数制限匿名認証方式(例えば、非特許文献4参照)は、このようなアプリケーションを実現するのに適した方式である。ユーザがアプリケーションを利用する度に、アプリケーション提供者(AP)がユーザをこの方式に従って認証することで、回数制限を守っている正直なユーザには匿名性を提供し、そうでないユーザは皆に特定されてしまうようにできる。
【0005】
特に非特許文献4では、タグ・メカニズムという、ユーザの認証回数を匿名のままカウントする仕組みを提案し、ACJTグループ署名方式(例えば、非特許文献1参照)のメンバー追加プロシージャとタグ・メカニズムとを組み合わせることで、回数制限匿名認証方式を実現している。
【0006】
しかし、上記の回数制限匿名認証方式で用いられるタグ・メカニズムは、効率が悪く、認証時には、APとユーザは、ともに制限回数kに比例した回数の巾乗剰余を計算する必要がある。例えば、電子クーポンや回数制限つき視聴の場合には、制限回数が10を越えることも十分考えられる。このため、上記の非特許文献4の方式は、これらに応用するには効率が悪い。
【非特許文献1】G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik, “A Practical and Provably Secure Coalition-Resistant Group Signature Scheme”, In Advances in Cryptology --- CRYPTO 2000, vol. 1880 of LNCS, pp. 255-270, Springer-Verlag, 2000
【非特許文献2】P. S. L. M. Barreto, H. Y. Kim, B. Lynn, M. Scott, “Efficient Algorithms for Pairing-Based Cryptosystems”, In Advances in Cryptology -- Crypto’2002, vol. 2442 of LNCS, pp. 354-368, Springer-Verlag, 2002
【非特許文献3】Rafael Pass, “On Deniability in the Common Reference String and Random Oracle Model”, In Advances in Cryptology --- CRYPTO 2003, vol. 2729 of LNCS, pp. 316-337, Springer-Verlag, 2003
【非特許文献4】Isamu Teranishi, Jun Furukawa, and Kazue Sako, “k-Times Anonymous Authentication (Extended Abstract)”, In Advances in Cryptology --- ASIACRYPT 2004, vol. 3329 of LNCS, pp. 308-322, Springer-Verlag, 2004
【非特許文献5】Oded Goldreich, “Foundation of Cryptography, Basic Tools”, Cambridge University Press, ISBN 0-521-79172-3, USA, 2001, pp. 148-169
【発明の開示】
【発明が解決しようとする課題】
【0007】
既存の擬似ランダム関数の問題点は、擬似ランダム関数fは、y=f(x)を満たすxの知識のゼロ知識証明を効率的に行うことはできないことにある。その理由は、fの計算方法が複雑なためである。
【0008】
既存の回数制限匿名認証方式の問題点は、認証時におけるユーザの計算量が回数制限kに比例することである。
【0009】
本発明は、このような従来の事情を考慮してなされたもので、効率的な擬似ランダム関数及びそれを用いた効率的な回数制限匿名認証方式を実現することを目的とする。
【課題を解決するための手段】
【0010】
上記目的を達成するため、本発明に係る擬似ランダム関数計算装置は、有限群の元を構成する要素として少なくとも第一の要素及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管し、生成された前記公開鍵を公開する鍵生成手段と、整数が入力されると、擬似ランダム関数の関数値として、前記有限群の元を出力する擬似ランダム関数計算手段とを有し、前記擬似ランダム関数計算手段は、前記有限群の元として、前記公開鍵の前記第一の要素を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記公開鍵の前記第二の要素を底とし、前記秘密鍵と前記入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元と、の積を出力することを特徴とする。
【0011】
本発明の別の側面に係る擬似ランダム関数計算装置は、整数からなる秘密鍵を生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管する鍵生成手段と、ビット列と整数との組が入力されると、擬似ランダム関数の関数値として、有限群の元を出力する擬似ランダム関数計算手段とを有し、前記擬似ランダム関数計算手段は、前記有限群の元として、前記入力された値で決まる値を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、前記入力された値で決まる値を底とし、前記秘密鍵と前記入力された整数の和の逆数を指数として、べき乗剰余を計算して得られる値を指数として、べき乗剰余演算により得られる値からなる第二の元と、の積を出力することを特徴とする。本発明において、前記底は、前記入力された値のハッシュ値であってもよい。
【0012】
本発明に係る回数制限匿名認証システムは、上記いずれかに記載の擬似ランダム関数計算装置を用いた回数制限匿名認証システムであって、識別子と、整数k、i、y、及びlと、有限群の元tとを入力するための入力手段と、前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算手段と、前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をl乗した値にtを乗じた値を計算する第二タグ計算手段と、前記第一タグ計算手段の計算結果と前記第二タグ計算手段の計算結果との組を出力する出力手段とを有するタグ生成手段を備えたことを特徴とする回数制限匿名認証システム。
【0013】
本発明において、整数kを入力するための入力手段と、電子署名方式の公開鍵及び秘密鍵ペアを選ぶ電子署名用鍵生成手段と、k個の整数を選ぶ平文選択手段と、前記k個の整数各々に対する署名文を前記公開鍵及び秘密鍵ペアを用いて計算する電子署名計算手段と、
前記電子署名方式の公開鍵と前記k個の整数と前記k個の署名文とからなる組を、前記タグ生成手段の計算に使用されるタグ用公開鍵として出力する出力手段と、を有するタグ用鍵生成手段を更に備えてもよい。
【0014】
前記電子署名計算手段は、平文として整数を入力するための手段と、平文と整数の和の有限体での逆元を計算する手段と、計算された前記逆元を指数としてべき乗剰余を計算し、前記べき乗剰余の計算結果を含む組を前記タグ用公開鍵として出力する手段とを有してもよい。
【0015】
前記電子署名用鍵生成手段は、有限群から元を選ぶ手段と、整数を選ぶ手段と、前記元を底とし、前記整数を指数として、べき乗剰余を計算する手段と、選ばれた前記有限群の元と前記べき乗剰余の計算結果とからなる組を出力する手段とを有してもよい。
【0016】
本発明において、前記タグ生成手段に整数lを入力して計算される計算結果をτとし、前記タグ生成手段に整数l’を入力して計算される計算結果をτ’としたとき、前記τ、l、τ’、l’の四つのデータを入力するための入力手段と、前記τを前記τ’で割った値を底とし、前記lから前記l’を減じた値の有限体での逆数を指数として、べき乗剰余を計算する計算手段と、前記べき乗剰余の計算結果を出力する出力手段と、を有するメンバー特定情報抽出手段を更に備えてもよい。
【0017】
本発明において、グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者(以下、AP)装置の公開鍵と、前記AP装置の識別子と、整数k、i、及びlとを入力するための入力手段と、前記グループメンバーとしての秘密鍵から整数yを作り、前記AP装置の識別子と、前記k、i、l、及びyとを入力として、前記タグ生成手段によりタグを成すデータを計算する手段と、前記タグの正当性証明文を計算する正当性証明手段と、前記タグと前記正当性証明文とを出力する出力手段と、を有するグループ証明手段を更に備えてもよい。
【0018】
本発明において、有限群の元τと有限群の元μと整数lと証明文pとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数l’と証明文p’とを要素とする第二の組とを入力するための入力手段と、前記τと前記τ’とが同一であるか否かを判定する第一判定手段と、前記lと前記l’とが同一であるか否かを判定する第二判定手段と、前記証明文pが正当であるか否かを判定する第三判定手段と、前記証明文p’が正当であるか否かを判定する第四判定手段と、予め設定された対応表に基づいて、前記メンバー特定情報抽出手段の計算結果と対応する識別子を取得する識別子取得手段と、を有するトレース手段を更に有してもよい。
【0019】
本発明に係る擬似ランダム関数計算方法は、有限群の元を構成する要素として少なくとも第一の要素及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管し、生成された前記公開鍵を公開する鍵生成ステップと、整数が入力されると、擬似ランダム関数の関数値として、前記有限群の元を出力する擬似ランダム関数計算ステップとを有し、前記擬似ランダム関数計算ステップは、前記有限群の元として、前記公開鍵の前記第一の要素を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、前記公開鍵の前記第二の要素を底とし、前記秘密鍵と前記入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元と、の積を出力することを特徴とする。
【0020】
本発明の別の側面に係る擬似ランダム関数計算方法は、整数からなる秘密鍵を生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管する鍵生成ステップと、ビット列と整数との組が入力されると、擬似ランダム関数の関数値として、有限群の元を出力する擬似ランダム関数計算ステップとを有し、前記擬似ランダム関数計算ステップは、前記有限群の元として、前記入力された値で決まる値を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、前記入力された値で決まる値を底とし、前記秘密鍵と前記入力された整数の和の逆数を指数として、べき乗剰余を計算して得られる値を指数として、べき乗剰余演算により得られる値からなる第二の元と、の積を出力することを特徴とする。本発明において、前記底は、前記入力された値のハッシュ値であってもよい。
【0021】
本発明に係る回数制限匿名認証方法は、上記いずれかに記載の擬似ランダム関数計算方法を用いた回数制限匿名認証方法であって、識別子と、整数k、i、y、及びlと、有限群の元tとを入力するためのステップと、前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算ステップと、前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をl乗した値にtを乗じた値を計算する第二タグ計算ステップと、前記第一タグ計算ステップの計算結果と前記第二タグ計算ステップの計算結果との組を出力するステップとを有するタグ生成ステップを備えたことを特徴とする。
【0022】
本発明において、整数kを入力するための入力ステップと、電子署名方式の公開鍵及び秘密鍵ペアを選ぶ電子署名用鍵生成ステップと、k個の整数を選ぶ平文選択ステップと、前記k個の整数各々に対する署名文を前記公開鍵及び秘密鍵ペアを用いて計算する電子署名計算ステップと、前記電子署名方式の公開鍵と前記k個の整数と前記k個の署名文とからなる組を、前記タグ生成手段の計算に使用されるタグ用公開鍵として出力する出力ステップと、を有するタグ用鍵生成ステップを更に備えてもよい。
【0023】
前記電子署名計算ステップは、平文として整数を入力するためのステップと、平文と整数の和の有限体での逆元を計算するステップと、計算された前記逆元を指数としてべき乗剰余を計算し、前記べき乗剰余の計算結果を含む組を前記タグ用公開鍵として出力するステップとを有してもよい。
【0024】
前記電子署名用鍵生成ステップは、有限群から元を選ぶステップと、整数を選ぶステップと、前記元を底とし、前記整数を指数として、べき乗剰余を計算するステップと、選ばれた前記有限群の元と前記べき乗剰余の計算結果とからなる組を出力するステップとを有してもよい。
【0025】
本発明において、前記タグ生成ステップにて整数lを入力して計算される計算結果をτとし、前記タグ生成ステップにて整数l’を入力して計算される計算結果をτ’としたとき、前記τ、l、τ’、l’の四つのデータを入力するためのステップと、前記τを前記τ’で割った値を底とし、前記lから前記l’を減じた値の有限体での逆数を指数として、べき乗剰余を計算するステップと、前記べき乗剰余の計算結果を出力するステップと、
を有するメンバー特定情報抽出ステップを更に備えてもよい。
【0026】
本発明において、グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者(以下、AP)装置の公開鍵と、前記AP装置の識別子と、整数k、i、及びlとを入力するためのステップと、前記グループメンバーとしての秘密鍵から整数yを作り、前記AP装置の識別子と、前記k、i、l、及びyとを入力として、前記タグ生成ステップにてタグを成すデータを計算するステップと、前記タグの正当性証明文を計算するステップと、前記タグと前記正当性証明文とを出力するステップと、を有するグループ証明ステップを更に備えてもよい。
【0027】
本発明において、有限群の元τと有限群の元μと整数lと証明文pとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数l’と証明文p’とを要素とする第二の組とを入力するためのステップと、前記τと前記τ’とが同一であるか否かを判定するステップと、前記lと前記l’とが同一であるか否かを判定するステップと、前記証明文pが正当であるか否かを判定するステップと、前記証明文p’が正当であるか否かを判定するステップと、予め設定された対応表に基づいて、前記メンバー特定情報抽出ステップの計算結果と対応する識別子を取得するステップと、を有するトレースステップを更に備えてもよい。
【発明の効果】
【0028】
本発明によれば、効率的な擬似ランダム関数及びそれを用いた効率的な回数制限匿名認証方式を実現できる。
【0029】
即ち、擬似ランダム関数は、少ない回数の逆数計算とべき乗剰余とで関数値を計算できる。関数値の計算アルゴリズムが単純単純になり、これにより、y=f(x)を満たすxの知識のゼロ知識証明を効率的に行うことができ、既存の擬似ランダム関数の問題点を解決できる。
【0030】
また、回数制限匿名認証では、既存の方式とは異なり、ユーザが計算すべきデータ個数がO(log k)個である。よって、認証時におけるユーザの計算量は制限回数kに比例しない。
【発明を実施するための最良の形態】
【0031】
以下、本発明に係る擬似ランダム関数計算装置及び方法、並びに回数制限匿名認証システム及び方法を実施するための最良の形態について、添付図面を参照して説明する。
【実施例1】
【0032】
本実施例は、擬似ランダム関数計算装置に適用したものである。
【0033】
図2を参照して、本実施例の装置構成を説明する。図2に示す擬似ランダム関数計算装置1は、機能上、擬似ランダム関数用鍵生成手段2、秘密鍵記憶部3、公開鍵記憶部4、入力手段5、擬似ランダム関数計算手段6、及び出力手段7を有している。
【0034】
擬似ランダム関数計算装置1は、一例としてコンピュータ機のCPU、記憶装置、その他の各種入出力装置によって実現される。この例では、擬似ランダム関数用鍵生成手段2及び擬似ランダム関数計算手段6は、コンピュータ機のCPUが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、各手段2、6の処理アルゴリズム(後述参照)に応じて予め設定される。また、秘密鍵記憶部3及び公開鍵記憶部4は、コンピュータ機の記憶装置により実装される。さらに、入力手段5及び出力手段7は、コンピュータ機の入出力装置に対応する。
【0035】
以下の説明では、ωをセキュリティ・パラメータとし、G_1を有限巡回群でG_1の位数がωビットの整数であるものとし、qをG_1の位数とする。本実施例の擬似ランダム関数計算装置1は、なんらかの方法でG_1のパラメータ、ω、およびqを事前に入手しており、G_1のパラメータ、ω、およびqが公開鍵記憶部4に書き込まれているものとする。G_1のパラメータ、ω、およびqを入手する方法は、どのようなものでもよい。例えば、外部からの入力として得る、装置の回路にハードウェア的に書き込んでおく、といった方法がある。
【0036】
次に、擬似ランダム関数用鍵生成手段2及び擬似ランダム関数計算手段6の処理手順を図3に従って説明する。図3に示す処理手順は、コンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、コンピュータ機のCPUにより実行される。
【0037】
図3において、擬似ランダム関数用鍵生成手段2は、次の処理を実行する。まず、G_1の元g、hをランダムに選ぶ(ステップS1)。次に、Z_qの元yをランダムに選ぶ(ステップS2)。次に、yを秘密鍵記憶部3に、(g,h)を公開鍵記憶部4にそれぞれ書き込む(ステップS3)。最後に、(g,h)を出力する(ステップS4)。
【0038】
図3において、擬似ランダム関数計算手段6は、次の処理を実行する。まず、G_1の元iを入力として受け取る(ステップS5)。次に、f(i)=g^{i}h^{1/(y+i)}を計算する(ステップS6)。最後に、f(i)を出力する(ステップS7)。
【0039】
従って、本実施例によれば、少ない回数の逆数計算とべき乗剰余とで擬似ランダム関数の関数値を計算できるため、関数値の計算アルゴリズムが単純になり、これにより、y=f(x)を満たすxの知識のゼロ知識証明を効率的に行うことができる。
【実施例2】
【0040】
本実施例は、擬似ランダム関数計算装置に適用したものである。
【0041】
図4を参照して、本実施例の装置構成を説明する。図4に示す本実施例の擬似ランダム関数計算装置1は、機能上、擬似ランダム関数用鍵生成手段2、秘密鍵記憶部3、公開鍵記憶部4、入力手段5、擬似ランダム関数計算手段6、及び出力手段7を有している。
【0042】
擬似ランダム関数計算装置1は、一例としてコンピュータ機のCPU、記憶装置、その他の各種入出力装置によって実現される。この例では、擬似ランダム関数用鍵生成手段2及び擬似ランダム関数計算手段6は、コンピュータ機のCPUが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、各手段2、6の処理アルゴリズム(後述参照)に応じて予め設定される。また、秘密鍵記憶部3及び公開鍵記憶部4は、コンピュータ機の記憶装置により実装される。さらに、入力手段5及び出力手段7は、コンピュータ機の入出力装置に対応する。
【0043】
以下の説明では、ωをセキュリティ・パラメータとし、G_1を有限巡回群でG_1の位数がωビットの整数であるものとし、qをG_1の位数とする。本実施例の擬似ランダム関数計算装置は、なんらかの方法でG_1のパラメータ、ω、およびqを事前に入手しており、G_1のパラメータ、ω、およびqが公開鍵記憶部4に書き込まれているものとする。G_1のパラメータ、ω、およびqを入手する方法はどのようなものでもよい。例えば、外部からの入力として得る、装置の回路にハードウェア的に書き込んでおく、といった方法がある。
【0044】
次に、擬似ランダム関数用鍵生成手段2の処理手順を図5に従って説明する。図5に示す処理手順は、コンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、コンピュータ機のCPUにより実行される。
【0045】
図5において、擬似ランダム関数用鍵生成手段2は、Z_qの元yをランダムに選び(ステップS11)、yを秘密鍵記憶部3に書き込む(ステップS12)。
【0046】
図5において、擬似ランダム関数計算手段6は、次の処理を実行する。
【0047】
まず、ビット列XとG_1の元iを入力として受け取る(ステップS13)。
【0048】
次に、(g_{X},h_{X})=H_{G_1^2}(X)を計算する(ステップS14)。ここで、H_{G_1^2}は、G_1^2に値を取るハッシュ関数を示す。
【0049】
次に、f[y]_{ω}(i,X)=g_{X}^{i}h_{X}^{1/(y+i)}を計算する(ステップS15)。
【0050】
最後に、f[y]_{ω}(i,X)を出力する(ステップS16)。
【0051】
従って、本実施例でも、前述の実施例1と同様に、少ない回数の逆数計算とべき乗剰余とで擬似ランダム関数の関数値を計算できるため、関数値の計算アルゴリズムが単純になり、これにより、y=f(x)を満たすxの知識のゼロ知識証明を効率的に行うことができる。
【実施例3】
【0052】
本実施例は、前述した擬似ランダム関数計算装置を用いた回数制限匿名認証システムに適用したものである。
【0053】
図6を参照して、本実施例の装置構成を説明する。図6に示すシステムは、機能上、メンバー特定情報生成装置10、乱数生成装置20、タグ生成装置30、メンバー特定情報抽出装置40、及び鍵生成装置50を有している。前述した擬似ランダム関数計算装置は、タグ生成装置30により用いられている。
【0054】
メンバー特定情報生成装置10は、機能上、秘密鍵生成手段11、公開情報記憶部12、メンバー特定情報生成手段13、書き込み手段14、及び通信手段15を備える。
【0055】
乱数生成装置20は、機能上、公開情報記憶部21、乱数選択手段22、及び通信手段23を備える。
【0056】
タグ生成装置30は、前述した擬似ランダム関数計算装置を用いたもので、機能上、公開情報記憶部31、タグ計算手段32、入力手段33、及び通信装置34を備える。
【0057】
メンバー特定情報抽出装置40は、機能上、公開情報記憶部41、メンバー特定情報抽出手段42、一致性判定手段43、出力手段44、及び通信装置45を備える。
【0058】
鍵生成装置50は、機能上、入力手段51、公開情報記憶部52、タグ用鍵生成手段53、及び通信手段54を備える。
【0059】
上記の各装置10〜50は、一例としてコンピュータ機のCPU、記憶装置、ネットワークインターフェース部、その他の各種入出力装置によって実現される。この例では、各手段11、13、14、22、32、42、43、53は、各コンピュータ機のCPUが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、各手段の処理アルゴリズム(後述参照)に応じて予め設定される。また、公開情報記憶部12、21、31、41、52は、各コンピュータ機の記憶装置により実装される。通信手段15、23、54、及び通信装置34,45は、各コンピュータ機のネットワークインターフェース部に、また入力手段23、51、及び出力手段44は、各コンピュータ機の入出力装置にそれぞれ対応する。
【0060】
図6では、もっとも単純な場合として、5種類の装置10〜50がそれぞれ一台ずつしかない場合を描いているが、各種類の装置が複数台あってもかまわない。また、図6では、各装置10〜50が別々の機械である場合を描いているが、一つの機械が二種類の装置の機能を兼ねていてもかまわない。
【0061】
メンバー特定情報生成装置10、乱数生成装置20、タグ生成装置30、メンバー特定情報抽出装置40、及び鍵生成装置50は、それぞれ通信手段14、23、34、45、54を使って相互に通信できる。通信媒体としては、どのような通信媒体を用いてもかまわない。例えばインターネット、電波、電話回線といったものを用いることができる。
【0062】
各装置10〜50は、他の装置が公開している公開情報をなんらかの方法で入手できるものとする。公開情報の入手手段は、どのような方法を用いてもかまわない。例えば、公開情報を公開している装置から前述の通信手段を用いて直接受け取る方法、公開情報のリストを持っているサーバから前述の通信手段を用いて受け取る方法、を用いることができる。
【0063】
次に、本実施例の動作を図7及び図8に従って説明する。図7及び図8に示す処理手順は、各装置に対応するコンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、各コンピュータ機のCPUにより実行される。
【0064】
以下の説明では、ωをセキュリティ・パラメータとし、G_1を有限巡回群でG_1の位数がωビットの整数であるものとし、qをG_1の位数とする。本実施例で適用される擬似ランダム関数計算装置は、なんらかの方法でG_1のパラメータ、ω、およびqを事前に入手しており、G_1のパラメータ、ω、およびqが各装置10〜50の公開情報記憶部12、21、31、41、52に書き込まれているものとする。G_1のパラメータ、ω、およびqを入手する方法はどのようなものでもよい。例えば外部からの入力として得る、装置の回路にハードウェア的に書き込んでおく、といった方法がある。各装置10〜50は、必要に応じてこれらのデータを読み込む。
【0065】
図7において、まず、メンバー特定情報生成装置10は、秘密鍵生成手段11の処理を行って、Z_qの元yをランダムに選ぶ(ステップS21)。g_1をG_1の元とし、ν_{ω}(y)=g_1^{y}とする。g_1は事前に何らかの方法で選ばれ、全ての装置10〜50の公開情報記憶部12、21、31、41、52に事前に記憶されているものとする。g_1をどのような方法で選び、どのような方法で各装置10〜50に配布してもかまわないが、安全性の観点から言えば、g_1を何らかの値のハッシュ値にセットすることが望ましい。
【0066】
次にメンバー特定情報生成装置10は、メンバー特定情報生成手段42の処理を行って、t_1=ν_{ω}(y)とする(ステップS22)。
【0067】
ここで、G_2、H_2、G_3を、位数がqである有限巡回群とし、<・,・>はG_2×H_2の元(g,h’)にG_3の元<g,h’>を対応させる写像で、<g^x,h’^y>=<g,h’>^{xy}が任意のg,h’,x,yに対して成立するものとする。このような組(G_2、H_2、G_3、<・,・>)の生成方法、および<・,・>の計算方法は様々なものが知られているが、そのどれを用いてもよい(例えば、非特許文献2参照)。
【0068】
次に、鍵生成装置50がタグ用鍵生成手段53の処理を行う。
【0069】
タグ用鍵生成手段53は、ステップS23、S24にて、それぞれ電子署名用鍵生成手段、電子署名手段による処理を行うので、タグ用鍵生成手段53の処理を説明する前に、電子署名用鍵生成手段と、電子署名手段との各処理を図8に従って説明する。
【0070】
図8において、電子署名用鍵生成手段は、まず、G_2の元g_2をランダムに選ぶ(ステップS41)。次に、H_2の元g’_2をランダムに選ぶ(ステップS42)。次に、Z_qの元sskをランダムに選ぶ(ステップS43)。
【0071】
次に、h’_2=g’_2^{ssk}を計算する(ステップS44)。
【0072】
最後に、(g_2,g’_2,h’_2)を電子署名用公開鍵spkとしてセットする(ステップS45)。
【0073】
電子署名手段は、まず、spkを(g_2,g’_2,h’_2)とパースする(ステップS46)。次に、平文βに対する署名文S=g_2^{1/(ssk+β)}を計算する(ステップS47)。
【0074】
鍵生成装置50は、非負整数kを入力として受け取ったら、図7に示すタグ用鍵生成手段53の処理を行う。
【0075】
図7において、まず、鍵生成装置50は、電子署名用鍵生成手段の処理を行い、電子署名用公開鍵spkと、電子署名用秘密鍵sskとを生成する(ステップS23)。
【0076】
次に、鍵生成装置50は、平文β_1,…,β_kを選び、(spk,ssk)を使って電子署名手段の処理を行い、各β_iに対する署名文S_iを作成する(ステップS24)。
【0077】
最後に鍵生成装置50は、apk=(spk,(β_1,S_1),…,(β_k,S_k))とする(ステップS25)。
【0078】
次に乱数生成装置20は、乱数選択手段21の処理を行い、Z_qの元lをランダムに選んで出力する(ステップS26)。
【0079】
次にタグ生成装置30は、通信手段23、34を使って乱数生成装置20と通信して、lを受信し、通信装置54、34を使って鍵生成装置50と通信して、apkを受信し、タグ生成手段32の処理を開始する。このタグ生成手段32の処理を説明する。
【0080】
まず、タグ生成装置30は、タグ生成手段32の処理により、タグ生成装置30のID、タグ生成装置32がアクセスを許す回数の上限値k,および現時点でのアクセス回数i(i≦k)を受け取る(ステップS27)。
【0081】
次にタグ生成装置30は、apkを(spk,(β_1,S_1),…,(β_k,S_k))とパースする(ステップS28)。
【0082】
次にタグ生成装置30は、f[y]_{ω}を実施例2の擬似ランダム関数とし、F[y]_{ω}(X,i)=f[y]_{ω}(X,−i)とする。
【0083】
最後に、タグ生成装置30は、(τ,μ)=(f[y]_{ω}(ID||k,β_i),F[y]_{ω}(ID||k,β_i))を計算する(ステップS29)。f[y]_{ω}とF[y]_{ω}は、前述した実施例2の擬似ランダム関数計算手段6の処理を行うことで計算する。
【0084】
次に、タグ生成手段32の処理が同じ入力(ID,k,i)を使って二度行われたとする。各タグ生成手段32の出力を(τ,μ,l)、(τ,μ’,l’)とする。
【0085】
この場合、メンバー特定情報抽出装置40は、通信手段34、45を使って、タグ生成装置30から(μ,l)、(μ’,l’)を受け取り、メンバー特定情報抽出手段42と一致性判定手段43の各処理を順に行う。
【0086】
メンバー特定情報抽出装置40は、メンバー特定情報抽出手段42の処理を行い、(μ/μ’)^{1/(l−l’)}を計算する(ステップS30、S31)。
【0087】
メンバー特定情報抽出装置40は、一致性判定手段43の処理を行い、t_1と(μ/μ’)^{1/(l−l’)}とが入力されたら、t_1=(τ/τ’)^{1/(l−l’)}であるかどうかを出力する(ステップS32)。
【0088】
従って、本実施例によれば、回数制限匿名認証は既存の方式とは異なり、ユーザが計算すべきデータ個数がO(log k)個であるため、認証時におけるユーザの計算量は制限回数kに比例しないから、効率的な回数制限匿名認証方式を実現することができる。
【実施例4】
【0089】
本実施例は、前述した擬似ランダム関数計算装置を用いた回数制限匿名認証システムに適用したものである。
【0090】
図9を参照して、本実施例の装置構成を説明する。図9に示すシステムは、機能上、メンバー特定情報生成装置10、乱数生成装置20、タグ生成装置30、及びメンバー特定情報抽出装置40を有している。前述した擬似ランダム関数計算装置は、タグ生成装置30により用いられている。
【0091】
メンバー特定情報生成装置10は、機能上、秘密鍵生成手段11、公開情報記憶部12、メンバー特定情報生成手段13、通信手段14、及び書き込み手段15を備える。
【0092】
乱数生成装置20は、機能上、公開情報記憶部21、乱数選択手段22、及び通信手段23を備える。
【0093】
タグ生成装置30は、前述した擬似ランダム関数計算装置を用いたもので、機能上、公開情報記憶部31、入力手段33、通信装置34、及びタグ計算手段35を備える。
【0094】
メンバー特定情報抽出装置40は、機能上、公開情報記憶部41、メンバー特定情報抽出手段42、一致性判定手段43、出力手段44、及び通信装置45を備える。
【0095】
上記の各装置10〜50は、一例としてコンピュータ機のCPU、記憶装置、ネットワークインターフェース部、その他の各種入出力装置によって実現される。この例では、各手段11、13、14、22、42、43、53は、各コンピュータ機のCPUが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、これら各手段の処理アルゴリズム(後述参照)に応じて予め設定される。また、公開情報記憶部12、21、31、41、52は、コンピュータ機の記憶装置により実装される。通信手段15、23、54、及び通信装置34,45は、各コンピュータ機のネットワークインターフェース部に、また入力手段23、51、及び出力手段44は、各コンピュータ機の入出力装置にそれぞれ対応する。
【0096】
図9では、もっとも単純な場合として、5種類の装置がそれぞれ一台ずつしかない場合を描いているが、各種類の装置が複数台あってもかまわない。また、図では、各装置が別々の機械である場合を描いているが、一つの機械が二種類の装置の機能を兼ねていてもかまわない。
【0097】
メンバー特定情報生成装置10、乱数生成装置20、タグ生成装置30、メンバー特定情報抽出装置40は、それぞれ通信手段14、23、34、45を使って相互に通信できる。通信媒体としてどのような通信媒体を用いてもかまわない。例えばインターネット、電波、電話回線といったものを用いることができる。
【0098】
各装置10〜40は、他の装置が公開している公開情報をなんらかの方法で入手できるものとする。公開情報の入手手段は、どのような方法を用いてもかまわない。例えば、公開情報を公開している装置から前述の通信手段を用いて直接受け取る方法、公開情報のリストを持っているサーバから前述の通信手段を用いて受け取る方法、を用いることができる。
【0099】
実施例4のメンバー特定情報生成装置10、乱数生成装置20、メンバー特定情報抽出装置40は、前述した実施例3のメンバー特定情報生成装置10、乱数生成装置20、及びメンバー特定情報抽出装置40と同じ動作をする。
【0100】
また、実施例4のタグ生成装置30の通信装置34、公開情報記憶部31、入力手段33は、前述した実施例3のタグ生成装置30の通信装置34、公開情報記憶部31、及び入力手段33と同じ機能を持っている。
【0101】
次に、図10を参照して、実施例4のタグ計算手段35を説明する。図10に示す処理手順は、コンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、コンピュータ機のCPUにより実行される。
【0102】
以下の説明では、ωをセキュリティ・パラメータとし、G_1を有限巡回群でG_1の位数がωビットの整数であるものとし、qをG_1の位数とする。擬似ランダム関数計算装置は、なんらかの方法でG_1のパラメータ、ω、およびqを事前に入手しており、G_1のパラメータ、ω、およびqが各装置の公開情報記憶部に書き込まれているものとする。G_1のパラメータ、ω、およびqを入手する方法どのようなものでもよい。例えば外部からの入力として得る、装置の回路にハードウェア的に書き込んでおく、といった方法がある。各装置10〜50は、必要に応じてこれらのデータを読み込む。
【0103】
図10において、タグ生成装置3は、タグ計算手段35の処理を行い、タグ生成装置のID、タグ生成装置がアクセスを許す回数の上限値k、および現時点でのアクセス回数i≦kを受け取る(ステップS51)。
【0104】
f[y]_{ω}を前述した実施例2の擬似ランダム関数とし、F[y]_{ω}(X,i)=f[y]_{ω}(X,−i)とする。
【0105】
最後に、タグ生成装置3は、(τ,μ)=(f[y]_{ω}(ID||k,i),F[y]_{ω}(ID||k,i))を計算する(ステップS52)。
【0106】
f[y]_{ω}とF[y]_{ω}は、実施例2の擬似ランダム関数計算手順BPRF5を行うことで計算する。
【0107】
従って、本実施例でも、前述の実施例3と同様に、回数制限匿名認証は既存の方式とは異なり、ユーザが計算すべきデータ個数がO(log k)個であるため、認証時におけるユーザの計算量は制限回数kに比例しないから、効率的な回数制限匿名認証方式を実現することができる。
【実施例5】
【0108】
本実施例は、前述した擬似ランダム関数計算装置を用いた回数制限匿名認証システムに適用したものである。
【0109】
図1を参照して、本実施例の装置構成を説明する。
【0110】
図1に示す本実施例の回数制限匿名認証システムは、前述した実施例3、4のシステムに様々な計算手順を追加して構成されており、機能上、GM(Group Manager)装置(グループ管理装置)100、リスト記憶装置200、ユーザ装置300、AP(Application Provider)装置(アプリケーション提供装置)400、及びトレース装置500の5種類の装置を備える。前述した擬似ランダム関数計算装置は、後述するグループ署名手段(グループ証明手段、グループ検証手段)に適用されている。
【0111】
GM装置100は、機能上、GMセットアップ手段101、発行手段102、秘密情報記憶部103、公開情報記憶部104、及び通信手段105を備える。
【0112】
リスト記憶装置200は、機能上、リスト記憶部201、及び通信手段202を備える。
【0113】
ユーザ装置300は、機能上、参加手段301、グループ証明手段302、秘密情報記憶部303、及び公開情報記憶部304、及び通信手段305を備える。
【0114】
AP装置400は、機能上、APセットアップ手段401、グループ検証手段402、公開情報記憶部403、履歴記憶部404、及び通信手段405を備える。
【0115】
トレース装置500は、機能上、トレース手段501、公開情報記憶部502、及び通信手段503を備える。
【0116】
上記の各装置100〜500は、一例としてコンピュータ機(サーバ機、クライアント機等)のCPU、記憶装置、ネットワークインターフェース部、その他の各種入出力装置によって実現される。この例では、各手段101、102、301、302、401、401、501は、各コンピュータ機のCPUが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、これら各手段の処理アルゴリズム(後述参照)に応じて予め設定される。また、公開情報記憶部104、304、403、502、秘密情報記憶部103、303、リスト記憶部201、履歴記憶部404は、各コンピュータ機の記憶装置により実装される。通信手段105、202、305、405、503は、各コンピュータ機のネットワークインターフェース部に対応する。
【0117】
図1では、もっとも単純な場合として5種類の装置がそれぞれ一台ずつしかない場合を描いているが、各種類の装置が複数台あってもかまわない。また、図1では、各装置100〜500が別々の機械である場合を描いているが、一つの機械が二種類の装置の機能を兼ねていてもかまわない。例えばGM装置100の機能とリスト装置200の機能を両方持つ機械を使ってもかまわない。
【0118】
GM装置100、リスト記憶装置200、ユーザ装置300、AP装置400、トレース装置500は、それぞれ通信手段105、202、305、405、503を使って相互に通信できる。通信媒体としては、例えばインターネット、電波、電話回線といったものを用いることができるが、本発明ではどのような通信媒体を用いてもかまわない。
【0119】
GM装置100、ユーザ装置300、AP装置400、トレース装置500は、それぞれの公開情報記憶部104、304、403、502に、自分自身や他の装置が公開している公開情報を記憶する。また、リスト記憶装置200は、リスト記憶部201という、公開情報を記憶するための部分を持っている。リスト記憶装置200は、自分自身や他の装置が公開している公開情報をリスト記憶部201に記憶する。
【0120】
各装置100〜500は、他の装置が公開している公開情報をなんらかの方法で入手できるものとする。公開情報の入手手段としては例えば、公開情報を公開している装置から前述の通信手段を用いて直接受け取る方法、公開情報のリストを持っているサーバから前述の通信手段を用いて受け取る方法、といったものが考えられるが、どのような方法を用いてもかまわない。
【0121】
GM装置100、ユーザ装置300は、それぞれ秘密情報記憶部103、303にそれぞれの秘密情報を記憶する。
【0122】
各装置100〜500には、事前にセキュリティ・パラメータωが配布されている。セキュリティ・パラメータをどのような方法で配布するのか、セキュリティ・パラメータをどのような方法で決定するのかは問わない。
【0123】
ユーザ装置300、AP装置400には、事前に固有のIDが割り振られており、各装置100〜500は、全てのユーザ装置300、AP装置400のIDを事前に知っている。IDとしてどのようなデータを用いるのか、IDをどのように配布するのかは問わない。例えば、装置保有者の名前、装置に割り振られたIPアドレス、装置に割り振られたMACアドレス、および乱数といったものを装置のIDとして用いることができる。
【0124】
GM装置100は、GMセットアップ手段101により、発行者用鍵生成手段の処理を行う。以下、発行者用鍵生成手段の詳細を略して、GMセットアップ手段101の処理を説明し、後で発行者用鍵生成手段の詳細を説明する。
【0125】
次に、本実施例の動作を図11〜図21を参照して説明する。図11〜図21に示す処理手順は、各装置に対応するコンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、各コンピュータ機のCPUにより実行される。
【0126】
まず、GMセットアップ手段101の処理を図11に従って説明する。
【0127】
図11において、GM装置100は、まずセキュリティ・パラメータωを公開情報記憶部104から読み込む(ステップS61)。GM装置100は、次に発行者用鍵生成手段の処理を行い、GM公開鍵gpkとGM秘密鍵gskを作り(ステップS62)、gpkを公開情報記憶部104に、gskを秘密情報記憶部103に記憶する(ステップS63)。
【0128】
次に、発行者用鍵生成手段の処理を図16に従って説明する。
【0129】
以下の説明では、G_2、H_2、G_3を有限巡回群とし、<・,・>はG_2×H_2の元(g,h’)にG_3の元<g,h’>を対応させる写像で、<g^x,h’^y>=<g,h’>^{xy}が任意のg,h’,x,yに対して成立するものとする。このような組(G_2、H_2、G_3、<・,・>)の生成方法、および<・,・>の計算方法は様々なものが知られているが、そのどれを用いてもよい。例えば非特許文献2を参照されたい。qをG_2の位数とし、整数環ZをイデアルqZで割った商環をZ_qと書く。
【0130】
図16において、GM装置100は、G_2の元g_3、h_3、a_3とH_2の元g’_3をランダムに選ぶ(ステップS131、S132)。次に、GM装置1は、Z_qの元gskをランダムに選ぶ(ステップS133)。次に、GM装置1は、u’_3=g_3^{ssk}を計算する(ステップS134)。最後にGM装置1は、(g_3,h_3,a_3,g’_3,u’_3)を発行者用公開鍵gpkとしてセットする(ステップS135)。
【0131】
次に、GM装置100の発行手段102とユーザ装置300の参加手段302の各処理を説明する。
【0132】
GM装置100とユーザ装置300は、相互通信をしながら、それぞれ発行手段102、参加手段302の処理を行う。
【0133】
GM装置100は、発行手段102により、第一発行手段、第二発行手段の各処理を行う。ユーザ装置300は、参加手段302により、第一参加手段、ファイ計算手段、メンバー特定情報生成手段、第二参加手段、メンバー鍵検証手段の各処理を行う。
【0134】
まず、第一発行手段、第一参加手段、ファイ計算手段、メンバー特定情報生成手段、第二発行手段、第二参加手段、およびメンバー鍵検証手段の詳細を略して、発行手段102と参加手段302の説明を行い、その後で、第一発行手段、第一参加手段、ファイ計算手段、メンバー特定情報生成手段、第二発行手段、第二参加手段、及びメンバー鍵検証手段の詳細を説明する。
【0135】
最初に、GM装置100の発行手段102とユーザ装置300の参加手段302の各処理を図12に従って説明する。
【0136】
図12において、GM装置100は、まず(ω,gpk)を公開情報記憶部104から、gskを秘密情報記憶部103から読み込む(ステップS71)。
【0137】
ユーザ装置300は、(ω,gpk)を公開情報記憶部304から読み込む(ステップS81)。
【0138】
次にGM装置100とユーザ装置300は、互いに通信しながら、それぞれ第一発行手段、第一参加手段を行い、GM装置100は、St_{GM}を、ユーザ装置300は、St_{U}とメンバー秘密鍵mskをそれぞれ得る(ステップS72、S82)。ただし、GM装置100とユーザ装置300のいずれかが、それぞれ第一発行手段、第一参加手段の各処理の途中で異常終了した場合は、それぞれ発行手段102、参加手段301の各処理を終了する(ステップS72、S82)。
【0139】
次にGM装置100は、gpkを公開情報記憶部104に、gskを秘密情報記憶部103に書き込む(ステップS73)。
【0140】
次にユーザ装置300は、ファイ計算手段の処理を行い、y=φ_{ω}(msk)を計算する(ステップS83)。
【0141】
次にユーザ装置300は、メンバー特定情報生成手段の処理を行い、メンバー特定情報t_1を得る(ステップS84)。次に、ユーザ装置300は、t_1とリスト記憶装置200に送信する(ステップS85)。
【0142】
リスト記憶装置200は、受信したt_1をユーザ装置300のIDと組にしてリスト記憶部201に記憶する(ステップS80)。
【0143】
次に、GM装置100は、リスト装置200からt_1を受け取る(ステップS744)。もしリスト装置200がt_1を保管していなかったら、GM装置100は、発行手段の処理を終了する(ステップS75)。リスト装置200からt_1を受け取るのに成功したら、次に、ユーザ装置300は、t_1の正当性をGM装置100に証明し、GM装置100は、その証明を検証する(ステップS86、S76)。正当性証明は、どのような方法で行ってもよい。例えば非特許文献3の方法で行うことができる。
【0144】
ユーザ装置300の証明が正当でなければ、GM装置100は、発行手段の処理を終了する(ステップS77)。ユーザ装置300の証明が正当であれば、GM装置100とユーザ装置300は、それぞれ第二発行手段、第二参加手段の各処理を行い、ともにメンバー公開鍵mpkを得る(ステップS78、S87)。
【0145】
次にGM装置100は、mpkを公開情報記憶部104に書き込む(ステップS79)。
【0146】
ユーザ装置300は、メンバー鍵検証手段の処理を行うことで、verkey(mpk,msk)を計算し、verkey(mpk,msk)=acceptなら、(mpk,msk)を公開情報記憶部304に書き込む(ステップS88)。
【0147】
次に、第一発行手段と第一参加手段の各処理を図17に従って説明する。
【0148】
図17において、GM装置100は、まずGM公開鍵gpkを(g_3,h_3,a_3,g’_3,u’_3)とパースする(ステップS141)。ユーザ装置300も、GM公開鍵gpkを(g_3,h_3,a_3,g’_3,u’_3)とパースする(ステップS145)。
【0149】
次にユーザ装置300は、Z_qの元x,r’をランダムに選ぶ(ステップS146)。次に、ユーザ装置300は、w=a_3g_3^{x}・h_3^{r’}を計算する(ステップS147)。次に、ユーザ装置300は、wをGM装置1に送信する(ステップS148)。次に、GM装置100は、wを受信する(ステップS142)。
【0150】
次にユーザ装置300は、wの正当性をGM装置1に証明し、GM装置100は、その証明を検証する(ステップS149、S143)。証明は、どのような方法で行ってもよいが、例えば非特許文献3の方法で証明することができる。
【0151】
次にGM装置100は、wが正当なら、St_{GM}=wとして、第一発行手段の処理を正常終了し、そうでなければ、異常終了する(ステップS144)。最後に、ユーザ装置300は、St_{U}=wとして、第一参加手段の処理を正常終了する(ステップS150)。
【0152】
次に、ファイ計算手段の処理を図18に従って説明する。
【0153】
図18において、ユーザ装置300は、mskを(x,r’)とパースする(ステップS161)。ユーザ装置300は、y=xとする(ステップS162)。
【0154】
次に、メンバー特定情報生成手段の処理を図7に従って説明する。
【0155】
ユーザ装置300は、前述した実施例3のメンバー特定情報生成手段の処理(図7)を行い、t_1=ν_{ω}(y)=g_1^yを計算する(ステップS22)。ここで、g_1は事前に決められた公開情報である。g_1は、どの装置がどのような方法で公開してもよいが、安全性の観点から言えば、g_1はなんらかのデータのハッシュ値であることが望ましい。
【0156】
次に、第二発行手段と第二参加手段の各処理を図18に従って説明する。
【0157】
図18において、GM装置100は、Z_qの元e,r”をランダムに選び(ステップS151、S152)、v=(wh_3^{r”})^{1/(gsk+e)}を計算する(ステップS153)。次にGM装置100は、mpk=(v,e)とする(ステップS154)。次にGM装置100は、(mpk,r”)をユーザ装置300に送信する(ステップS155)。
【0158】
次にユーザ装置300は、(mpk,r”)を受信したら(ステップS156)、r=r’+r”mod qとし、msk=(x,r)とする(ステップS157、S158)。
【0159】
次に、メンバー鍵検証手段の処理を図18に従って説明する。
【0160】
図18において、ユーザ装置300は、mpkを(v,e)とパースする(ステップS159)。
【0161】
ユーザ装置300は、<w,u’_3g’_3^{e}>=<v,g’_3>が成立するかどうかを調べ、<w,u’_3g’_3^{e}>=<v,g’_3>が正当ならmpk=(v,e)とし、そうでなければ異常終了する(ステップS160)。
【0162】
次に、AP装置400のAPセットアップ手段401の処理を図11に従って説明する。
【0163】
図11において、AP装置400は、APセットアップ手段401の処理を行う前に、各ユーザ装置300にアクセスを許す上限回数kを決めておく必要がある。どのような方法でkを決めてもよい。
【0164】
AP装置400は、まずセキュリティ・パラメータω、自分の識別子ID、および上限値kを公開情報記憶部403から読み込む(ステップS64)。
【0165】
次にAP装置400は、実施例3のタグ用鍵生成手段の処理(図7)を行い、AP公開鍵apkを得る(ステップS65)。最後に、AP装置400は、apkを公開情報記憶部AP3に書き込む(ステップS66)。
【0166】
ユーザ装置300とAP装置400は、互いに通信しながら、それぞれグループ証明手段302、グループ検証手段403の各処理を行う。
【0167】
次に、ユーザ装置300のグループ証明手段302とAP装置400のグループ検証手段303を図13に従って説明する。
【0168】
図13において、まずユーザ装置300は、(ω,gpk,ID,k,apk,mpk,msk)を公開情報記憶部304から読み込む(ステップS91)。
【0169】
AP装置400は、(ω,gpk,ID,k,apk)を公開情報記憶部404から読み込む(ステップS101)。
【0170】
次にAP装置400は、ランダムにlを選び(ステップS102)、lをユーザ装置300に送信する(ステップS103)。
【0171】
次にユーザ装置300は、lを受信したら(ステップS92)、実施例3のタグ生成手段の処理(図7)を行い、知識(τ,μ)を生成する(ステップS93)。
【0172】
ver_{spk}(β,S)を、<S,h’_2g’_2^β>=<g_2,g’_2>が成立すれば、acceptを、そうでなければ、rejectを出力する関数とする。
【0173】
次にユーザ装置300は、知識(τ,μ)の正当性証明文pf_{τ,μ}を作成し(ステップS94)、(τ,μ,pf_{τ,μ})をAP装置400に送信する(ステップS95)。
【0174】
ここで、証明文pf_{τ,μ}の作成方法を図19、及び図20に従って説明する。
【0175】
図19において、まずユーザ装置300は、Z_qの元βを選び、v_{4}=v・h_3^{−β}を計算する(ステップS171)。
【0176】
次にユーザ装置300は、Z_qの元x_{4}、e_{4}、γ_{4}、β_{4}をランダムに選び、X_{4}=<g_3^{x_{4}}v_{4}^{e_{4}}h_3^{γ},g’_3><h_3^{β_{4}},u’_3>を計算する(ステップS172)。
【0177】
次にユーザ装置300は、Z_qの元sをランダムに選び、s’=(x+i)s、b=τ・g^{−i}a_3^sを計算する(ステップS173)。
【0178】
次にユーザ装置300は、Z_qの元i_{4}、s_{4}、s’_{4}を選び、Z_qの元s’_{4}=(x_{4}+i_{4})s_{4} mod q、b_{4}=g^{−i_{4}}a_3^{s_{4}}、h_{4}=b^{x_{4}+i_{4}}a_3^{−s’_{4}}を計算する(ステップS174)。
【0179】
次にユーザ装置300は、Z_qの元tをランダムに選び、t’=(x+i)t mod q、B=μg_1^{−lx}g^{−i}a_3^{t}を計算する(ステップS175)。
【0180】
次にユーザ装置300は、Z_qの元t_{4}、t’_{4}を選び、B_{4}=g_1^{−l・x_{4}}g^{−i_{4}}a_3^{t_{4}}、H_{4}=B^{−x_{4}−i_{4}}a_3^{−t’_{4}}を計算する(ステップS176)。
【0181】
次にユーザ装置300は、Z_qの元ρをランダムに選び、θ=ρx mod q、T=Sh^{ρ}を計算する(ステップS177)。
【0182】
図20において、次にユーザ装置300は、Z_qの元θ_{4}、ρ_{4}をランダムに選び、Y_{4}=<T,h’_2><T,g’_2>^{x_{4}}<h,g’_2>^{−θ_{4}}<h,h’_2>^{−ρ_{4}}を計算する(ステップS178)。
【0183】
次にユーザ装置300は、c=Hash_{Z_q}(gpk,apk,v_{4},X_{4},b,b_{4},h_{4},B,B_{4},H_{4},Y_{4})
を計算する(ステップS179)。Hash_{Z_q}は、Z_qに値をとるハッシュ関数を表す。
【0184】
次にユーザ装置300は、x_{5}=cx+x_{4} mod q、e_{5}=ce+e_{4} mod q、r_{5}=c(r+βe)+γ mod q、i_{5}=ci+i_{4} mod q、s_{5}=cs+s_{4} mod q、s’_{5}=cs’+s’_{4} mod q、t_{5}=ct+t_{4} mod q、t’_{5}=ct’+t’_{4} mod q、ρ_{5}=cρ+ρ_{4} mod q、θ_{5}=cθ+θ_{4} mod qを計算する(ステップS180)。
【0185】
最後にユーザ装置300は、pf_{τ,μ}=(b,B,c,x_{5},e_{5},r_{5},i_{5},s_{5},s’_{5},t_{5},t’_{5},ρ_{5},θ_{5})とする。
【0186】
ここで、図13に戻り、説明を続ける。
【0187】
図13において、AP装置400は、(τ,μ,pf_{τ,μ})を受信したら(ステップS104)、τがすでに履歴記憶部404に記載されているかどうかを調べ、記載されていたら、rejectを出力してグループ検証手段403の処理を終了する(ステップS105)。
【0188】
次にAP装置400は、pf_{τ,μ}が正当性を検証し、pf_{τ,μ}が正当でなければ、rejectを出力してグループ検証手段を終了し(ステップS106)、pf_{τ,μ}が正当であれば、(τ,μ,l,pf_{τ,μ})を履歴記憶部404に記載し、acceptを出力して、グループ検証手段403の処理を終了する(ステップS107)。
【0189】
ここで、pf_{τ,μ}の正当性を検証する方法を図21に従って説明する。
【0190】
図21において、まずAP装置400は、X_{4}=<g_3^{x_{5}}v_{4}^{e_{5}}h_3^{r_{5}},g’_3><h_3^{r_{5}},u’_3>(<a_3,g_3>/<v_{4},u’_3>)^cを計算する(ステップS181)。
【0191】
次にAP装置400は、b_{4}=(τb^{−1})^{−c}g^{−i_{5}}a_3^{s_{5}}を計算する(ステップS182)。
【0192】
次にAP装置400は、h_{4}=h^{−c}b^{x_{4}+i_{4}}a_3^{−s’_{5}}を計算する(ステップS183)。
【0193】
次にAP装置400は、B_{4}=(B^{−1}μ)^{c}g_1^{−l・x_{5}}g^{−i_{5}}a_3^{t_{5}}を計算する(ステップS184)。
【0194】
次にAP装置400は、H_{4}=B^{−x_{5}−i_{rej}}a_3^{−t’_{5}}を計算する(ステップS185)。
【0195】
次にAP装置400は、C_{4}=C^{−c}g^{x_{5}}h^{ρ_{5}}を計算する(ステップS186)。
【0196】
次にAP装置400は、Y_{4}=<g_2,g’_2>^{−c}<T,h’_2><T,g’_2>^{x_{4}}<h,g’_2>^{−θ_{4}}<h,h’_2>^{−ρ_{4}}を計算する(ステップS187)。
【0197】
最後にAP装置400は、c=Hash_{Z_q}(gpk,apk,v_{4},X_{4},b,b_{4},h_{4},B,B_{4},H_{4})が成立するかどうかを確認し、c=Hash_{Z_q}(gpk,apk,v_{4},X_{4},b,b_{4},h_{4},B,B_{4},H_{4},Y_{4})が成立していれば、pf_{τ,μ}をacceptし、そうでなければrejectする(ステップS188)。
【0198】
次に、トレース装置500のトレース手段501の処理を図14、図15に従って説明する。
【0199】
図14において、まずトレース装置500は、(ω,gpk,ID,k,apk)を公開情報記憶部502から読み込む(ステップS111)。
【0200】
次にトレース装置500は、AP装置400の履歴記憶部404に記憶されているデータ(τ,μ,l,pf_{τ,μ})、(τ’,μ’,l’,pf’_{τ’,μ’})を受信する(ステップS112)。このとき、AP装置400がいつトレース装置500に(τ,μ,pf_{τ,μ})、(τ’,μ’,l’,pf’_{τ’,μ’})を送信するのかは問わない。
【0201】
次にトレース装置500は、τ=τ’であるかどうかを調べ、τ=τ’でないなら、「AP装置400が不正なデータ(τ,μ,l,pf_{τ,μ})、(τ’,μ’,l’,pf’_{τ’,μ’})をトレース装置500に送った」ことを意味する文字列を出力してトレース手段501の処理を終了する(ステップS113)。
【0202】
次にトレース装置500は、l=l’であるかどうかを調べ、l=l’でないなら、「AP装置4が不正なデータ(τ,μ,l,pf_{τ,μ})、(τ’,μ’,l’,pf’_{τ’,μ’})をトレース装置500に送った」ことを意味する文字列を出力してトレース手段501の処理を終了する(ステップS114)。
【0203】
次にトレース装置500は、pf_{τ,μ}が正当であるかどうかを調べ、正当でなければ、「AP装置400が不正なデータ(τ,μ,l,pf_{τ,μ})、(τ’,μ’,l’,pf’_{τ’,μ’})をトレース装置5に送った」ことを意味する文字列を出力してトレース手段501の処理を終了する(ステップS115)。
【0204】
次にトレース装置500は、pf’_{τ’,μ’}が正当であるかどうかを調べ、正当でなければ、「AP装置400が不正なデータ(τ,μ,l,pf_{τ,μ})、(τ’,μ’,l’,pf’_{τ’,μ’})をトレース装置500に送った」ことを意味する文字列を出力してトレース手段501の処理を終了する(ステップS116)。
【0205】
図15において、次にトレース装置500は、実施例3のメンバー特定情報抽出手段の処理(図7)を行い、メンバー特定情報t_1を得る(ステップS117)。
【0206】
次にトレース装置500は、t_1をリスト記憶装置200に送信する(ステップS118)。リスト記憶装置200は、t_1を受信すると(ステップS121)、t_1に対応するIDをトレース装置500に送信する(ステップS122)。そのようなIDがなければ、ID=GMとし、ID=GMを送信する。
【0207】
次にトレース装置500は、t_1に対応するIDを受け取る(ステップS122、S119)。最後にトレース装置500は、IDを出力する(ステップS120)。
【0208】
従って、本実施例でも、前述の実施例3、4と同様に、回数制限匿名認証は既存の方式とは異なり、ユーザが計算すべきデータ個数がO(log k)個であるため、認証時におけるユーザの計算量は制限回数kに比例しないから、効率的な回数制限匿名認証方式を実現することができる。
【実施例6】
【0209】
本実施例は、前述した擬似ランダム関数計算装置を用いた回数制限匿名認証システムに適用したものである。
【0210】
前述の図1を参照して、本実施例の装置構成を説明する。
【0211】
図1に示す本実施例の回数制限匿名認証システムは、前述した実施例3、4のシステムに様々な計算手順を追加して構成されており、機能上、GM装置100、リスト記憶装置200、ユーザ装置300、AP装置400、及びトレース装置500の5種類の装置を備える。前述した擬似ランダム関数計算装置は、後述するグループ署名手段(グループ証明手段、グループ検証手段)に適用されている。
【0212】
このうち、GM装置100、リスト記憶装置200、ユーザ装置300、およびトレース装置500の装置構成は、前述した実施例5の装置構成と同じである。AP装置400は、前述した実施例5と同様に、グループ検証手段402、公開情報記憶部403、履歴記憶部404、通信手段405を備えるが、本実施例では、実施例5とは異なり、APセットアップ手段401が含まれない。従って、本実施例の装置構成は、図1の装置構成からAPセットアップ手段401を削除したものに対応する。
【0213】
上記の各装置100〜500は、一例としてコンピュータ機(サーバ機、クライアント機等)のCPU、記憶装置、ネットワークインターフェース部、その他の各種入出力装置によって実現される。この例では、各手段101、102、301、302、501は、各コンピュータ機のCPUが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、これら各手段の処理アルゴリズム(後述参照)に応じて予め設定される。また、公開情報記憶部104、304、403、502、秘密情報記憶部103、303、リスト記憶部201、履歴記憶部404は、各コンピュータ機の記憶装置により実装される。通信手段105、202、305、405、503は、各コンピュータ機のネットワークインターフェース部に対応する。
【0214】
図1では、もっとも単純な場合として5種類の装置がそれぞれ一台ずつしかない場合を描いているが、各種類の装置が複数台あってもかまわない。また、図1では、各装置が別々の機械である場合を描いているが、一つの機械が二種類の装置の機能を兼ねていてもかまわない。例えば、GM装置100の機能とリスト装置200の機能を両方持つ機械を使ってもかまわない。
【0215】
GM装置100、リスト記憶装置200、ユーザ装置300、AP装置400、トレース装置500は、それぞれ通信手段105、202、305、405、503を使って相互に通信できる。通信媒体として、例えばインターネット、電波、電話回線といったものを用いることができるが、どのような通信媒体を用いてもかまわない。
【0216】
GM装置100、ユーザ装置300、AP装置400、トレース装置500は、それぞれの公開情報記憶部104、304、403、502に、自分自身や他の装置が公開している公開情報を記憶する。また、リスト記憶装置200は、リスト記憶部201という、公開情報を記憶するための部分を持っている。リスト記憶装置200は、自分自身や他の装置が公開している公開情報をリスト記憶部201に記憶する。
【0217】
各装置100〜500は、他の装置が公開している公開情報をなんらかの方法で入手できるものとする。公開情報の入手手段としては例えば、公開情報を公開している装置から前述の通信手段を用いて直接受け取る方法、公開情報のリストを持っているサーバから前述の通信手段を用いて受け取る方法、といったものが考えられるが、どのような方法を用いてもかまわない。
【0218】
GM装置100とユーザ装置300は、それぞれ秘密情報記憶部103、303にそれぞれの秘密情報を記憶する。
【0219】
各装置100〜300には、事前にセキュリティ・パラメータωが配布されている。セキュリティ・パラメータωをどのような方法で配布するのか、セキュリティ・パラメータωをどのような方法で決定するのかは問わない。
【0220】
ユーザ装置300とAP装置400には、事前に固有のIDが割り振られており、各装置100〜500は、全てのユーザ装置300、AP装置400のIDを事前に知っている。IDとしてどのようなデータを用いるのか、IDをどのように配布するのかは問わない。例えば、装置保有者の名前、装置に割り振られたIPアドレス、装置に割り振られたMACアドレス、および乱数といったものを装置のIDとして用いることができる。
【0221】
グループ証明手段302、グループ検証手段402、トレース手段501以外の、実施例6の各手段は、実施例5のそれと同じである。
【0222】
次に、本実施例の動作を図13、図22〜図24を参照して説明する。図13、図22〜図24に示す処理手順は、各装置に対応するコンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、各コンピュータ機のCPUにより実行される。
【0223】
まず、グループ証明手段302とグループ検証手段402の各処理を図13に従って説明する。
【0224】
図13のステップS93、S94以外の処理は、前述した実施例5のグループ証明手段302と同じである。図13のステップS104以外の処理は、前述した実施例5のグループ検証手段402と同じである。
【0225】
グループ証明手段302は、ステップS93にて、実施例3ではなく実施例4のタグ生成手段の処理(図10)を行い、ステップS104にて、図19、図20の代わりに図22、図23に従って、証明文pf_{τ,μ}を作成する。
【0226】
図22及び図23を参照して、証明文pf_{τ,μ}の作成方法を説明する。
【0227】
図22において、まずユーザ装置300は、Z_qの元βを選び、v_{4}=v・h_3^{−β}を計算する(ステップS191)。
【0228】
次にユーザ装置300は、Z_qの元x_{4}、e_{4}、γ_{4}、β_{4}をランダムに選び、X_{4}=<g_3^{x_{4}}v_{4}^{e_{4}}h_3^{γ},g’_3><h_3^{β_{4}},u’_3>を計算する(ステップS192)。
【0229】
次にユーザ装置300は、Z_qの元sをランダムに選び、s’=(x+i)s、b=τ・g^{−i}a_3^sを計算する(ステップS193)。
【0230】
次にユーザ装置300は、Z_qの元i_{4}、s_{4}、s’_{4}を選び、Z_qの元s’_{4}=(x_{4}+i_{4})s_{4} mod q、b_{4}=g^{−i_{4}}a_3^{s_{4}}、h_{4}=b^{x_{4}+i_{4}}a_3^{−s’_{4}}を計算する(ステップS194)。
【0231】
次にユーザ装置300は、Z_qの元tをランダムに選び、t’=(x+i)t mod q 、B=μg_1^{−lx}g^{−i}a_3^{t}を計算する(ステップS195)。
【0232】
次にユーザ装置300は、Z_qの元t_{4}、t’_{4}を選び、B_{4}=g_1^{−l・x_{4}}g^{−i_{4}}a_3^{t_{4}}、H_{4}=B^{−x_{4}−i_{4}}a_3^{−t’_{4}}
を計算する(ステップS196)。
【0233】
次にユーザ装置300は、log_2 k以上の整数で最も小さい整数をNとする(ステップS197)。
【0234】
図23において、次にユーザ装置300は、整数i=0,..,Nに対し、xの第iビットをx_iとし、x’_i=1−x_iとし、z=k−xとし、zの第iビットをz_iとし、z’_i=1−z_iとする(ステップS198)。
【0235】
次にユーザ装置300は、Z_qのρ_1,…,ρ_N、θ_1,…,θ_Nで、ρ_1+…+ρ_N=θ_1+…+θ_Nが成立するものを選び、ρ=ρ_1+…+ρ_N、C_1=h^{ρ_1},…,C_N=h^{ρ_N}、D_1=h^{θ_1},…,D_N=h^{θ_N}、C=g^{x}h^{ρ}、D=g^{k−x}h^{ρ}を計算する(ステップS199)。
【0236】
次にユーザ装置300は、i=1,…,N,j=0,1に対し、Z_qの元ρ_{4,i},θ_{4,i},c’_{i,x’_i},d’_{i,z’_i},ρ_{5,i,x’_i},θ_{5,i,z’_i}をランダムに選び、C_{4,i,x_i}=g^{x_i}h^{ρ_{4,i}}、D_{4,i,x_i}=g^{z_i}h^{θ_{4,i}}、C_{4,i,x’_i}=C^{−c’_{i,x’_i}}g^{x’_i}h^{ρ_{5,i,x’_i}}、D_{4,i,x’_i}=D^{−d’_{i,z’_i}}g^{z’_i}h^{θ_{5,i,z’_i}}
を計算する(ステップS200)。
【0237】
次にユーザ装置300は、c=Hash_{Z_q}(gpk,apk,v_{4},X_{4},b,b_{4},h_{4},B,B_{4},H_{4},C_{4},{C_{4,i,j}}_{i=1,…,N,j=0,1},{D_{4,i,j}}_{i=1,…,N,j=0,1})を計算する(ステップS201)。Hash_{Z_q}は、Z_qに値をとるハッシュ関数を表す。
【0238】
次にユーザ装置300は、x_{5}=cx+x_{4} mod q、e_{5}=ce+e_{4} mod q、r_{5}=c(r+βe)+γ mod q、i_{5}=ci+i_{4} mod q、s_{5}=cs+s_{4} mod q、s’_{5}=cs’+s’_{4} mod q、t_{5}=ct+t_{4} mod q、t’_{5}=ct’+t’_{4} mod q、c_i=c−c’_i mod q、d_i=d−d’_i mod q、ρ_{5,i,x_i}=c_iρ_i+ρ_{4,i} mod q、θ_{5,i,x_i}=c_iθ_i+θ_{4,i} mod qを計算する(ステップS202)。
【0239】
最後にユーザ装置3は、pf_{τ,μ}=(b,B,C,c,x_{5},e_{5},r_{5},i_{5},s_{5},s’_{5},t_{5},t’_{5},{c_{ij}})とする(ステップS203)。
【0240】
図13において、AP装置400は、(τ,μ,pf_{τ,μ})を受信したら(ステップS104)、τがすでに履歴記憶部BAP4に記載されているかどうかを調べ、記載されていたらrejectを出力してグループ検証手段402の処理を終了する(ステップS105)。
【0241】
次にAP装置400は、pf_{τ,μ}が正当性を検証し、pf_{τ,μ}が不当なら、rejectを出力してグループ検証手段402の処理を終了し(ステップS106)、pf_{τ,μ}が正当なら、AP装置400は、(τ,μ,l,pf_{τ,μ})を履歴記憶部404に記載し、acceptを出力してグループ検証手段402の処理を終了する(ステップS107)。
【0242】
次に、pf_{τ,μ}の正当性を検証する方法を図24に従って説明する。
【0243】
図24において、まずAP装置400は、X_{4}=<g_3^{x_{5}}v_{4}^{e_{5}}h_3^{r_{5}},g’_3><h_3^{r_{5}},u’_3>(<a_3,g_3>/<v_{4},u’_3>)^cを計算する(ステップS211)。
【0244】
次にAP装置400は、b_{4}=(τb^{−1})^{−c}g^{−i_{5}}a_3^{s_{5}}を計算する(ステップS212)。
【0245】
次にAP装置400は、h_{4}=h^{−c}b^{x_{4}+i_{4}}a_3^{−s’_{5}}を計算する(ステップS213)。
【0246】
次にAP装置400は、B_{4}=(B^{−1}μ)^{c}g_1^{−l・x_{5}}g^{−i_{5}}a_3^{t_{5}}を計算する(ステップS214)。
【0247】
次にAP装置400は、H_{4}=B^{−x_{5}−i_{rej}}a_3^{−t’_{5}}を計算する(ステップS215)。
【0248】
次にAP装置400は、C_{4}=C^{−c}g^{x_{5}}h^{ρ_{5}}を計算する(ステップS216)。
【0249】
次にAP装置400は、i=1,..,N、j=0,1に対し、C_{4,i,j}= C_{−c_{ij}}g^{j}h^{ρ_{5,ij}}、D_{4,i,j}=D_{−c_{ij}}g^{j}h^{θ_{5,ij}}を計算する(ステップS217)。
【0250】
最後にAP装置400は、c=Hash_{Z_q}(gpk,apk,v_{4},X_{4},b,b_{4},h_{4},B,B_{4},H_{4},{C_{ij}}_{i=1,…,N,j=0,1},{D_{ij}}_{i=1,…,N,j=0,1})と、c=c_1+c’_1=…=c_N+c’_N mod qが成立するかどうかを確認し、ともに成立していれば、pf_{τ,μ}をacceptし、そうでなければrejectする(ステップS218)。
【0251】
従って、本実施例でも、前述の実施例3〜5と同様に、回数制限匿名認証は既存の方式とは異なり、ユーザが計算すべきデータ個数がO(log k)個であるため、認証時におけるユーザの計算量は制限回数kに比例しないから、効率的な回数制限匿名認証方式を実現することができる。
【図面の簡単な説明】
【0252】
【図1】本発明の実施例5、6による回数制限匿名認証システムの全体構成を示す図である。
【図2】本発明の実施例1による擬似ランダム関数計算装置の全体構成を示す図である。
【図3】図2に示す擬似ランダム関数用鍵生成手段と擬似ランダム関数計算手段の処理手順を説明する概略フローチャートである(実施例1)。
【図4】本発明の実施例2による擬似ランダム関数計算装置の全体構成を示す図である。
【図5】図4に示す擬似ランダム関数用鍵生成手段と擬似ランダム関数計算手段の処理手順を説明する概略フローチャートである(実施例2)。
【図6】本発明の実施例3による回数制限匿名認証システムの全体構成を示す図である。
【図7】図6に示す回数制限匿名認証システムの各手段の処理手順を説明する概略フローチャートである(実施例3)。
【図8】図7に示すタグ用鍵生成手段で用いる電子署名用鍵生成手段と電子署名手段の処理手順を説明する概略フローチャートである(実施例3)。
【図9】本発明の実施例4による回数制限匿名認証システムの全体構成を示す図である。
【図10】図9に示すタグ計算手段の処理手順を説明する概略フローチャートである(実施例4)。
【図11】図1に示すGMセットアップ手段とAPセットアップ手段の処理手順を説明する概略フローチャートである(実施例5)。
【図12】図1に示す発行手段と参加手段の処理手順を説明する概略フローチャートである(実施例5)。
【図13】図1に示すグループ証明手段とグループ検証手段の処理手順を説明する概略フローチャートである(実施例5)。
【図14】図1に示すトレース手段の処理手順を説明する概略フローチャートである(実施例5)。
【図15】図1に示すトレース手段とリスト記憶部の処理手順を説明する概略フローチャートである(実施例5)。
【図16】図1に示すGMセットアップ手段で用いる発行者用鍵生成手段の処理手順を説明する概略フローチャートである(実施例5)。
【図17】図1に示す発行手段及び参加手段で用いる第一発行手段及び第一参加手段の処理手順を説明する概略フローチャートである(実施例5)。
【図18】図1に示す発行手段及び参加手段で用いる第二発行手段、第二参加手段、及びファイ計算手段の処理手順を説明する概略フローチャートである(実施例5)。
【図19】図1に示すユーザ装置による証明文の作成方法の処理手順を説明する概略フローチャートである(実施例5)。
【図20】図1に示すユーザ装置による証明文の作成方法の処理手順を説明する概略フローチャートである(実施例5)。
【図21】図1に示すAP装置による証明文の正当性検証方法の処理手順を説明する概略フローチャートである(実施例5)。
【図22】図1に示すユーザ装置による証明文の作成方法の処理手順を説明する概略フローチャートである(実施例6)。
【図23】図1に示すユーザ装置による証明文の作成方法の処理手順を説明する概略フローチャートである(実施例6)。
【図24】図1に示すAP装置による証明文の正当性検証方法の処理手順を説明する概略フローチャートである(実施例6)。
【符号の説明】
【0253】
1 擬似ランダム関数計算装置
2 擬似ランダム関数用鍵生成手段
3 秘密鍵記憶部
4 公開鍵記憶部
5 入力手段
6 擬似ランダム関数計算手段
7 出力手段
10 メンバー特定情報生成装置
11 秘密鍵生成手段
12 公開情報記憶部
13 メンバー特定情報生成手段
14 通信装置
15 書き込み手段
20 乱数生成装置
21 公開情報記憶部
22 乱数選択手段
23 通信手段
30 タグ生成装置
31 公開情報記憶部
32 タグ生成手段
33 入力手段
34 通信装置
35 タグ計算手段
40 メンバー特定情報抽出装置
41 公開情報記憶部
42 メンバー特定情報抽出手段
43 一致性判定手段
44 出力手段
45 通信装置
50 鍵生成装置
51 入力手段
52 公開情報記憶部
53 タグ用鍵生成手段
54 通信手段
100 GM装置
101 GMセットアップ手段
102 発行手段
103 秘密情報記憶部
104 公開情報記憶部
105 通信手段
200 リスト記憶装置
201 リスト記憶部
202 通信手段
300 ユーザ装置
301 参加手段
302 グループ証明手段
303 秘密情報記憶部
304 公開情報記憶部
305 通信手段
400 AP装置
401 APセットアップ手段
402 グループ検証手段
403 公開情報記憶部
404 履歴記憶部
405 通信手段
500 トレース装置
501 トレース手段
502 公開情報記憶部
503 通信手段

【特許請求の範囲】
【請求項1】
有限群の元を構成する要素として少なくとも第一の要素及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管し、生成された前記公開鍵を公開する鍵生成手段と、
整数が入力されると、擬似ランダム関数の関数値として、前記有限群の元を出力する擬似ランダム関数計算手段とを有し、
前記擬似ランダム関数計算手段は、前記有限群の元として、
前記公開鍵の前記第一の要素を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記公開鍵の前記第二の要素を底とし、前記秘密鍵と前記入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元と、
の積を出力することを特徴とする擬似ランダム関数計算装置。
【請求項2】
整数からなる秘密鍵を生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管する鍵生成手段と、
ビット列と整数との組が入力されると、擬似ランダム関数の関数値として、有限群の元を出力する擬似ランダム関数計算手段とを有し、
前記擬似ランダム関数計算手段は、前記有限群の元として、
前記入力された値で決まる値を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記入力された値で決まる値を底とし、前記秘密鍵と前記入力された整数の和の逆数を指数として、べき乗剰余を計算して得られる値を指数として、べき乗剰余演算により得られる値からなる第二の元と、
の積を出力することを特徴とする擬似ランダム関数計算装置。
【請求項3】
前記底は、前記入力された値のハッシュ値であることを特徴とする請求項2記載の擬似ランダム関数計算装置。
【請求項4】
請求項1に記載の擬似ランダム関数計算装置を用いた回数制限匿名認証システムであって、
識別子と、整数k、i、y、及びlと、有限群の元tとを入力するための入力手段と、
前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算手段と、
前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をl乗した値にtを乗じた値を計算する第二タグ計算手段と、
前記第一タグ計算手段の計算結果と前記第二タグ計算手段の計算結果との組を出力する出力手段とを有するタグ生成手段を備えたことを特徴とする回数制限匿名認証システム。
【請求項5】
請求項2又は3に記載の擬似ランダム関数計算装置を用いた回数制限匿名認証システムであって、
識別子と、整数k、i、y、及びlと、有限群の元tとを入力するための入力手段と、
前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算手段と、
前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をl乗した値にtを乗じた値を計算する第二タグ計算手段と、
前記第一タグ計算手段の計算結果と前記第二タグ計算手段の計算結果との組を出力する出力手段と、
を有するタグ生成手段を備えたことを特徴とする回数制限匿名認証システム。
【請求項6】
整数kを入力するための入力手段と、
電子署名方式の公開鍵及び秘密鍵ペアを選ぶ電子署名用鍵生成手段と、
k個の整数を選ぶ平文選択手段と、
前記k個の整数各々に対する署名文を前記公開鍵及び秘密鍵ペアを用いて計算する電子署名計算手段と、
前記電子署名方式の公開鍵と前記k個の整数と前記k個の署名文とからなる組を、前記タグ生成手段の計算に使用されるタグ用公開鍵として出力する出力手段と、
を有するタグ用鍵生成手段を更に備えたことを特徴とする請求項4記載の回数制限匿名認証システム。
【請求項7】
前記電子署名計算手段は、
平文として整数を入力するための手段と、
平文と整数の和の有限体での逆元を計算する手段と、
計算された前記逆元を指数としてべき乗剰余を計算し、前記べき乗剰余の計算結果を含む組を前記タグ用公開鍵として出力する手段とを有することを特徴とする請求項6記載の回数制限匿名認証システム。
【請求項8】
前記電子署名用鍵生成手段は、
有限群から元を選ぶ手段と、
整数を選ぶ手段と、
前記元を底とし、前記整数を指数として、べき乗剰余を計算する手段と、
選ばれた前記有限群の元と前記べき乗剰余の計算結果とからなる組を出力する手段とを有することを特徴とする請求項7記載の回数制限匿名認証システム。
【請求項9】
前記タグ生成手段に整数lを入力して計算される計算結果をτとし、前記タグ生成手段に整数l’を入力して計算される計算結果をτ’としたとき、前記τ、l、τ’、l’の四つのデータを入力するための入力手段と、
前記τを前記τ’で割った値を底とし、前記lから前記l’を減じた値の有限体での逆数を指数として、べき乗剰余を計算する計算手段と、
前記べき乗剰余の計算結果を出力する出力手段と、
を有するメンバー特定情報抽出手段を更に備えたことを特徴とする請求項4記載の回数制限匿名認証システム。
【請求項10】
前記タグ生成手段に整数lを入力して計算される計算結果をτとし、前記タグ生成手段に整数l’を入力して計算される計算結果をτ’としたとき、前記τ、l、τ’、l’の四つのデータを入力するための入力手段と、
前記τを前記τ’で割った値を底とし、前記lから前記l’を減じた値の有限体での逆数を指数として、べき乗剰余を計算する計算手段と、
前記べき乗剰余の計算結果を出力する出力手段と、
を有するメンバー特定情報抽出手段を更に備えたことを特徴とする請求項5記載の回数制限匿名認証システム。
【請求項11】
グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者(以下、AP)装置の公開鍵と、前記AP装置の識別子と、整数k、i、及びlとを入力するための入力手段と、
前記グループメンバーとしての秘密鍵から整数yを作り、前記AP装置の識別子と、前記k、i、l、及びyとを入力として、前記タグ生成手段によりタグを成すデータを計算する手段と、
前記タグの正当性証明文を計算する正当性証明手段と、
前記タグと前記正当性証明文とを出力する出力手段と、
を有するグループ証明手段を更に備えたことを特徴とする請求項4記載の回数制限匿名認証システム。
【請求項12】
グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者(以下、AP)装置の公開鍵と、前記AP装置の識別子と、整数k、i、及びlとを入力するための入力手段と、
前記グループメンバーとしての秘密鍵から整数yを作り、前記AP装置の識別子と、前記k、i、l、及びyとを入力として、前記タグ生成手段によりタグを成すデータを計算する手段と、
前記タグの正当性証明文を計算する正当性証明手段と、
前記タグと前記正当性証明文とを出力する出力手段と、
を有するグループ証明手段を更に備えたことを特徴とする請求項5記載の回数制限匿名認証システム。
【請求項13】
有限群の元τと有限群の元μと整数lと証明文pとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数l’と証明文p’とを要素とする第二の組とを入力するための入力手段と、
前記τと前記τ’とが同一であるか否かを判定する第一判定手段と、
前記lと前記l’とが同一であるか否かを判定する第二判定手段と、
前記証明文pが正当であるか否かを判定する第三判定手段と、
前記証明文p’が正当であるか否かを判定する第四判定手段と、
予め設定された対応表に基づいて、前記メンバー特定情報抽出手段の計算結果と対応する識別子を取得する識別子取得手段と、
を有するトレース手段を更に有することを特徴とする請求項9記載の回数制限匿名認証システム。
【請求項14】
有限群の元τと有限群の元μと整数lと証明文pとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数l’と証明文p’とを要素とする第二の組とを入力するための入力手段と、
前記τと前記τ’とが同一であるか否かを判定する第一判定手段と、
前記lと前記l’とが同一であるか否かを判定する第二判定手段と、
前記証明文pが正当であるか否かを判定する第三判定手段と、
前記証明文p’が正当であるか否かを判定する第四判定手段と、
予め設定された対応表に基づいて、前記メンバー特定情報抽出手段の計算結果と対応する識別子を取得する識別子取得手段と、
を有するトレース手段を更に有することを特徴とする請求項10記載の回数制限匿名認証システム。
【請求項15】
有限群の元を構成する要素として少なくとも第一の要素及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管し、生成された前記公開鍵を公開する鍵生成ステップと、
整数が入力されると、擬似ランダム関数の関数値として、前記有限群の元を出力する擬似ランダム関数計算ステップとを有し、
前記擬似ランダム関数計算ステップは、前記有限群の元として、
前記公開鍵の前記第一の要素を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記公開鍵の前記第二の要素を底とし、前記秘密鍵と前記入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元と、
の積を出力することを特徴とする擬似ランダム関数計算方法。
【請求項16】
整数からなる秘密鍵を生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管する鍵生成ステップと、
ビット列と整数との組が入力されると、擬似ランダム関数の関数値として、有限群の元を出力する擬似ランダム関数計算ステップとを有し、
前記擬似ランダム関数計算ステップは、前記有限群の元として、
前記入力された値で決まる値を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記入力された値で決まる値を底とし、前記秘密鍵と前記入力された整数の和の逆数を指数として、べき乗剰余を計算して得られる値を指数として、べき乗剰余演算により得られる値からなる第二の元と、
の積を出力することを特徴とする擬似ランダム関数計算方法。
【請求項17】
前記底は、前記入力された値のハッシュ値であることを特徴とする請求項16記載の擬似ランダム関数計算方法。
【請求項18】
請求項15に記載の擬似ランダム関数計算方法を用いた回数制限匿名認証方法であって、
識別子と、整数k、i、y、及びlと、有限群の元tとを入力するためのステップと、
前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算ステップと、
前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をl乗した値にtを乗じた値を計算する第二タグ計算ステップと、
前記第一タグ計算ステップの計算結果と前記第二タグ計算ステップの計算結果との組を出力するステップとを有するタグ生成ステップを備えたことを特徴とする回数制限匿名認証方法。
【請求項19】
請求項16又は17に記載の擬似ランダム関数計算方法を用いた回数制限匿名認証方法であって、
識別子と、整数k、i、y、及びlと、有限群の元tとを入力するためのステップと、
前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算ステップと、
前記yを秘密鍵として用い、前記識別子と前記kと前記iとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をl乗した値にtを乗じた値を計算する第二タグ計算ステップと、
前記第一タグ計算手段の計算結果と前記第二タグ計算手段の計算結果との組を出力するステップと、
を有するタグ生成ステップを備えたことを特徴とする回数制限匿名認証方法。
【請求項20】
整数kを入力するための入力ステップと、
電子署名方式の公開鍵及び秘密鍵ペアを選ぶ電子署名用鍵生成ステップと、
k個の整数を選ぶ平文選択ステップと、
前記k個の整数各々に対する署名文を前記公開鍵及び秘密鍵ペアを用いて計算する電子署名計算ステップと、
前記電子署名方式の公開鍵と前記k個の整数と前記k個の署名文とからなる組を、前記タグ生成手段の計算に使用されるタグ用公開鍵として出力する出力ステップと、
を有するタグ用鍵生成ステップを更に備えたことを特徴とする請求項18記載の回数制限匿名認証方法。
【請求項21】
前記電子署名計算ステップは、
平文として整数を入力するためのステップと、
平文と整数の和の有限体での逆元を計算するステップと、
計算された前記逆元を指数としてべき乗剰余を計算し、前記べき乗剰余の計算結果を含む組を前記タグ用公開鍵として出力するステップとを有することを特徴とする請求項20記載の回数制限匿名認証方法。
【請求項22】
前記電子署名用鍵生成ステップは、
有限群から元を選ぶステップと、
整数を選ぶステップと、
前記元を底とし、前記整数を指数として、べき乗剰余を計算するステップと、
選ばれた前記有限群の元と前記べき乗剰余の計算結果とからなる組を出力するステップとを有することを特徴とする請求項21記載の回数制限匿名認証方法。
【請求項23】
前記タグ生成ステップにて整数lを入力して計算される計算結果をτとし、前記タグ生成ステップにて整数l’を入力して計算される計算結果をτ’としたとき、前記τ、l、τ’、l’の四つのデータを入力するためのステップと、
前記τを前記τ’で割った値を底とし、前記lから前記l’を減じた値の有限体での逆数を指数として、べき乗剰余を計算するステップと、
前記べき乗剰余の計算結果を出力するステップと、
を有するメンバー特定情報抽出ステップを更に備えたことを特徴とする請求項18記載の回数制限匿名認証方法。
【請求項24】
前記タグ生成ステップにて整数lを入力して計算される計算結果をτとし、前記タグ生成ステップにて整数l’を入力して計算される計算結果をτ’としたとき、前記τ、l、τ’、l’の四つのデータを入力するためのステップと、
前記τを前記τ’で割った値を底とし、前記lから前記l’を減じた値の有限体での逆数を指数として、べき乗剰余を計算するステップと、
前記べき乗剰余の計算結果を出力するステップと、
を有するメンバー特定情報抽出ステップを更に備えたことを特徴とする請求項19記載の回数制限匿名認証方法。
【請求項25】
グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者(以下、AP)装置の公開鍵と、前記AP装置の識別子と、整数k、i、及びlとを入力するためのステップと、
前記グループメンバーとしての秘密鍵から整数yを作り、前記AP装置の識別子と、前記k、i、l、及びyとを入力として、前記タグ生成ステップにてタグを成すデータを計算するステップと、
前記タグの正当性証明文を計算するステップと、
前記タグと前記正当性証明文とを出力するステップと、
を有するグループ証明ステップを更に備えたことを特徴とする請求項18記載の回数制限匿名認証方法。
【請求項26】
グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者(以下、AP)装置の公開鍵と、前記AP装置の識別子と、整数k、i、及びlとを入力するためのステップと、
前記グループメンバーとしての秘密鍵から整数yを作り、前記AP装置の識別子と、前記k、i、l、及びyとを入力として、前記タグ生成ステップにてタグを成すデータを計算するステップと、
前記タグの正当性証明文を計算するステップと、
前記タグと前記正当性証明文とを出力するステップと、
を有するグループ証明ステップを更に備えたことを特徴とする請求項19記載の回数制限匿名認証方法。
【請求項27】
有限群の元τと有限群の元μと整数lと証明文pとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数l’と証明文p’とを要素とする第二の組とを入力するためのステップと、
前記τと前記τ’とが同一であるか否かを判定するステップと、
前記lと前記l’とが同一であるか否かを判定するステップと、
前記証明文pが正当であるか否かを判定するステップと、
前記証明文p’が正当であるか否かを判定するステップと、
予め設定された対応表に基づいて、前記メンバー特定情報抽出ステップの計算結果と対応する識別子を取得するステップと、
を有するトレースステップを更に備えたことを特徴とする請求項23記載の回数制限匿名認証方法。
【請求項28】
有限群の元τと有限群の元μと整数lと証明文pとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数l’と証明文p’とを要素とする第二の組とを入力するためのステップと、
前記τと前記τ’とが同一であるか否かを判定するステップと、
前記lと前記l’とが同一であるか否かを判定するステップと、
前記証明文pが正当であるか否かを判定するステップと、
前記証明文p’が正当であるか否かを判定するステップと、
予め設定された対応表に基づいて、前記メンバー特定情報抽出ステップの計算結果と対応する識別子を取得するステップと、
を有するトレースステップを更に備えたことを特徴とする請求項24記載の回数制限匿名認証方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate


【公開番号】特開2006−330462(P2006−330462A)
【公開日】平成18年12月7日(2006.12.7)
【国際特許分類】
【出願番号】特願2005−155496(P2005−155496)
【出願日】平成17年5月27日(2005.5.27)
【出願人】(000004237)日本電気株式会社 (19,353)
【Fターム(参考)】