(57)【要約】【課題】効率的な擬似ランダム関数及びそれを用いた効率的な回数制限匿名認証方式を実現する。【解決手段】擬似ランダム関数計算装置１は、鍵生成手段２と、擬似ランダム関数計算手段３とを有する。鍵生成手段２は、有限群の元を成す要素として第一及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、秘密鍵を秘密鍵記憶部３に秘密裡に保管し、公開鍵を公開する。擬似ランダム関数計算手段３は、整数が入力されると、擬似ランダム関数の関数値として有限群の元を出力する。このとき、公開鍵の前記第一の要素を底とし、入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、公開鍵の第二の要素を底とし、秘密鍵と入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元との積を出力する。【選択図】  図２
2006330462.tif 000002
【特許請求の範囲】
【請求項１】
有限群の元を構成する要素として少なくとも第一の要素及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管し、生成された前記公開鍵を公開する鍵生成手段と、
整数が入力されると、擬似ランダム関数の関数値として、前記有限群の元を出力する擬似ランダム関数計算手段とを有し、
前記擬似ランダム関数計算手段は、前記有限群の元として、
前記公開鍵の前記第一の要素を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記公開鍵の前記第二の要素を底とし、前記秘密鍵と前記入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元と、
の積を出力することを特徴とする擬似ランダム関数計算装置。
【請求項２】
整数からなる秘密鍵を生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管する鍵生成手段と、
ビット列と整数との組が入力されると、擬似ランダム関数の関数値として、有限群の元を出力する擬似ランダム関数計算手段とを有し、
前記擬似ランダム関数計算手段は、前記有限群の元として、
前記入力された値で決まる値を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記入力された値で決まる値を底とし、前記秘密鍵と前記入力された整数の和の逆数を指数として、べき乗剰余を計算して得られる値を指数として、べき乗剰余演算により得られる値からなる第二の元と、
の積を出力することを特徴とする擬似ランダム関数計算装置。
【請求項３】
前記底は、前記入力された値のハッシュ値であることを特徴とする請求項２記載の擬似ランダム関数計算装置。
【請求項４】
請求項１に記載の擬似ランダム関数計算装置を用いた回数制限匿名認証システムであって、
識別子と、整数ｋ、ｉ、ｙ、及びｌと、有限群の元ｔとを入力するための入力手段と、
前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算手段と、
前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をｌ乗した値にｔを乗じた値を計算する第二タグ計算手段と、
前記第一タグ計算手段の計算結果と前記第二タグ計算手段の計算結果との組を出力する出力手段とを有するタグ生成手段を備えたことを特徴とする回数制限匿名認証システム。
【請求項５】
請求項２又は３に記載の擬似ランダム関数計算装置を用いた回数制限匿名認証システムであって、
識別子と、整数ｋ、ｉ、ｙ、及びｌと、有限群の元ｔとを入力するための入力手段と、
前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算手段と、
前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をｌ乗した値にｔを乗じた値を計算する第二タグ計算手段と、
前記第一タグ計算手段の計算結果と前記第二タグ計算手段の計算結果との組を出力する出力手段と、
を有するタグ生成手段を備えたことを特徴とする回数制限匿名認証システム。
【請求項６】
整数ｋを入力するための入力手段と、
電子署名方式の公開鍵及び秘密鍵ペアを選ぶ電子署名用鍵生成手段と、
ｋ個の整数を選ぶ平文選択手段と、
前記ｋ個の整数各々に対する署名文を前記公開鍵及び秘密鍵ペアを用いて計算する電子署名計算手段と、
前記電子署名方式の公開鍵と前記ｋ個の整数と前記ｋ個の署名文とからなる組を、前記タグ生成手段の計算に使用されるタグ用公開鍵として出力する出力手段と、
を有するタグ用鍵生成手段を更に備えたことを特徴とする請求項４記載の回数制限匿名認証システム。
【請求項７】
前記電子署名計算手段は、
平文として整数を入力するための手段と、
平文と整数の和の有限体での逆元を計算する手段と、
計算された前記逆元を指数としてべき乗剰余を計算し、前記べき乗剰余の計算結果を含む組を前記タグ用公開鍵として出力する手段とを有することを特徴とする請求項６記載の回数制限匿名認証システム。
【請求項８】
前記電子署名用鍵生成手段は、
有限群から元を選ぶ手段と、
整数を選ぶ手段と、
前記元を底とし、前記整数を指数として、べき乗剰余を計算する手段と、
選ばれた前記有限群の元と前記べき乗剰余の計算結果とからなる組を出力する手段とを有することを特徴とする請求項７記載の回数制限匿名認証システム。
【請求項９】
前記タグ生成手段に整数ｌを入力して計算される計算結果をτとし、前記タグ生成手段に整数ｌ’を入力して計算される計算結果をτ’としたとき、前記τ、ｌ、τ’、ｌ’の四つのデータを入力するための入力手段と、
前記τを前記τ’で割った値を底とし、前記ｌから前記ｌ’を減じた値の有限体での逆数を指数として、べき乗剰余を計算する計算手段と、
前記べき乗剰余の計算結果を出力する出力手段と、
を有するメンバー特定情報抽出手段を更に備えたことを特徴とする請求項４記載の回数制限匿名認証システム。
【請求項１０】
前記タグ生成手段に整数ｌを入力して計算される計算結果をτとし、前記タグ生成手段に整数ｌ’を入力して計算される計算結果をτ’としたとき、前記τ、ｌ、τ’、ｌ’の四つのデータを入力するための入力手段と、
前記τを前記τ’で割った値を底とし、前記ｌから前記ｌ’を減じた値の有限体での逆数を指数として、べき乗剰余を計算する計算手段と、
前記べき乗剰余の計算結果を出力する出力手段と、
を有するメンバー特定情報抽出手段を更に備えたことを特徴とする請求項５記載の回数制限匿名認証システム。
【請求項１１】
グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者（以下、ＡＰ）装置の公開鍵と、前記ＡＰ装置の識別子と、整数ｋ、ｉ、及びｌとを入力するための入力手段と、
前記グループメンバーとしての秘密鍵から整数ｙを作り、前記ＡＰ装置の識別子と、前記ｋ、ｉ、ｌ、及びｙとを入力として、前記タグ生成手段によりタグを成すデータを計算する手段と、
前記タグの正当性証明文を計算する正当性証明手段と、
前記タグと前記正当性証明文とを出力する出力手段と、
を有するグループ証明手段を更に備えたことを特徴とする請求項４記載の回数制限匿名認証システム。
【請求項１２】
グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者（以下、ＡＰ）装置の公開鍵と、前記ＡＰ装置の識別子と、整数ｋ、ｉ、及びｌとを入力するための入力手段と、
前記グループメンバーとしての秘密鍵から整数ｙを作り、前記ＡＰ装置の識別子と、前記ｋ、ｉ、ｌ、及びｙとを入力として、前記タグ生成手段によりタグを成すデータを計算する手段と、
前記タグの正当性証明文を計算する正当性証明手段と、
前記タグと前記正当性証明文とを出力する出力手段と、
を有するグループ証明手段を更に備えたことを特徴とする請求項５記載の回数制限匿名認証システム。
【請求項１３】
有限群の元τと有限群の元μと整数ｌと証明文ｐとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数ｌ’と証明文ｐ’とを要素とする第二の組とを入力するための入力手段と、
前記τと前記τ’とが同一であるか否かを判定する第一判定手段と、
前記ｌと前記ｌ’とが同一であるか否かを判定する第二判定手段と、
前記証明文ｐが正当であるか否かを判定する第三判定手段と、
前記証明文ｐ’が正当であるか否かを判定する第四判定手段と、
予め設定された対応表に基づいて、前記メンバー特定情報抽出手段の計算結果と対応する識別子を取得する識別子取得手段と、
を有するトレース手段を更に有することを特徴とする請求項９記載の回数制限匿名認証システム。
【請求項１４】
有限群の元τと有限群の元μと整数ｌと証明文ｐとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数ｌ’と証明文ｐ’とを要素とする第二の組とを入力するための入力手段と、
前記τと前記τ’とが同一であるか否かを判定する第一判定手段と、
前記ｌと前記ｌ’とが同一であるか否かを判定する第二判定手段と、
前記証明文ｐが正当であるか否かを判定する第三判定手段と、
前記証明文ｐ’が正当であるか否かを判定する第四判定手段と、
予め設定された対応表に基づいて、前記メンバー特定情報抽出手段の計算結果と対応する識別子を取得する識別子取得手段と、
を有するトレース手段を更に有することを特徴とする請求項１０記載の回数制限匿名認証システム。
【請求項１５】
有限群の元を構成する要素として少なくとも第一の要素及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管し、生成された前記公開鍵を公開する鍵生成ステップと、
整数が入力されると、擬似ランダム関数の関数値として、前記有限群の元を出力する擬似ランダム関数計算ステップとを有し、
前記擬似ランダム関数計算ステップは、前記有限群の元として、
前記公開鍵の前記第一の要素を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記公開鍵の前記第二の要素を底とし、前記秘密鍵と前記入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元と、
の積を出力することを特徴とする擬似ランダム関数計算方法。
【請求項１６】
整数からなる秘密鍵を生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管する鍵生成ステップと、
ビット列と整数との組が入力されると、擬似ランダム関数の関数値として、有限群の元を出力する擬似ランダム関数計算ステップとを有し、
前記擬似ランダム関数計算ステップは、前記有限群の元として、
前記入力された値で決まる値を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記入力された値で決まる値を底とし、前記秘密鍵と前記入力された整数の和の逆数を指数として、べき乗剰余を計算して得られる値を指数として、べき乗剰余演算により得られる値からなる第二の元と、
の積を出力することを特徴とする擬似ランダム関数計算方法。
【請求項１７】
前記底は、前記入力された値のハッシュ値であることを特徴とする請求項１６記載の擬似ランダム関数計算方法。
【請求項１８】
請求項１５に記載の擬似ランダム関数計算方法を用いた回数制限匿名認証方法であって、
識別子と、整数ｋ、ｉ、ｙ、及びｌと、有限群の元ｔとを入力するためのステップと、
前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算ステップと、
前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をｌ乗した値にｔを乗じた値を計算する第二タグ計算ステップと、
前記第一タグ計算ステップの計算結果と前記第二タグ計算ステップの計算結果との組を出力するステップとを有するタグ生成ステップを備えたことを特徴とする回数制限匿名認証方法。
【請求項１９】
請求項１６又は１７に記載の擬似ランダム関数計算方法を用いた回数制限匿名認証方法であって、
識別子と、整数ｋ、ｉ、ｙ、及びｌと、有限群の元ｔとを入力するためのステップと、
前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算ステップと、
前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をｌ乗した値にｔを乗じた値を計算する第二タグ計算ステップと、
前記第一タグ計算手段の計算結果と前記第二タグ計算手段の計算結果との組を出力するステップと、
を有するタグ生成ステップを備えたことを特徴とする回数制限匿名認証方法。
【請求項２０】
整数ｋを入力するための入力ステップと、
電子署名方式の公開鍵及び秘密鍵ペアを選ぶ電子署名用鍵生成ステップと、
ｋ個の整数を選ぶ平文選択ステップと、
前記ｋ個の整数各々に対する署名文を前記公開鍵及び秘密鍵ペアを用いて計算する電子署名計算ステップと、
前記電子署名方式の公開鍵と前記ｋ個の整数と前記ｋ個の署名文とからなる組を、前記タグ生成手段の計算に使用されるタグ用公開鍵として出力する出力ステップと、
を有するタグ用鍵生成ステップを更に備えたことを特徴とする請求項１８記載の回数制限匿名認証方法。
【請求項２１】
前記電子署名計算ステップは、
平文として整数を入力するためのステップと、
平文と整数の和の有限体での逆元を計算するステップと、
計算された前記逆元を指数としてべき乗剰余を計算し、前記べき乗剰余の計算結果を含む組を前記タグ用公開鍵として出力するステップとを有することを特徴とする請求項２０記載の回数制限匿名認証方法。
【請求項２２】
前記電子署名用鍵生成ステップは、
有限群から元を選ぶステップと、
整数を選ぶステップと、
前記元を底とし、前記整数を指数として、べき乗剰余を計算するステップと、
選ばれた前記有限群の元と前記べき乗剰余の計算結果とからなる組を出力するステップとを有することを特徴とする請求項２１記載の回数制限匿名認証方法。
【請求項２３】
前記タグ生成ステップにて整数ｌを入力して計算される計算結果をτとし、前記タグ生成ステップにて整数ｌ’を入力して計算される計算結果をτ’としたとき、前記τ、ｌ、τ’、ｌ’の四つのデータを入力するためのステップと、
前記τを前記τ’で割った値を底とし、前記ｌから前記ｌ’を減じた値の有限体での逆数を指数として、べき乗剰余を計算するステップと、
前記べき乗剰余の計算結果を出力するステップと、
を有するメンバー特定情報抽出ステップを更に備えたことを特徴とする請求項１８記載の回数制限匿名認証方法。
【請求項２４】
前記タグ生成ステップにて整数ｌを入力して計算される計算結果をτとし、前記タグ生成ステップにて整数ｌ’を入力して計算される計算結果をτ’としたとき、前記τ、ｌ、τ’、ｌ’の四つのデータを入力するためのステップと、
前記τを前記τ’で割った値を底とし、前記ｌから前記ｌ’を減じた値の有限体での逆数を指数として、べき乗剰余を計算するステップと、
前記べき乗剰余の計算結果を出力するステップと、
を有するメンバー特定情報抽出ステップを更に備えたことを特徴とする請求項１９記載の回数制限匿名認証方法。
【請求項２５】
グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者（以下、ＡＰ）装置の公開鍵と、前記ＡＰ装置の識別子と、整数ｋ、ｉ、及びｌとを入力するためのステップと、
前記グループメンバーとしての秘密鍵から整数ｙを作り、前記ＡＰ装置の識別子と、前記ｋ、ｉ、ｌ、及びｙとを入力として、前記タグ生成ステップにてタグを成すデータを計算するステップと、
前記タグの正当性証明文を計算するステップと、
前記タグと前記正当性証明文とを出力するステップと、
を有するグループ証明ステップを更に備えたことを特徴とする請求項１８記載の回数制限匿名認証方法。
【請求項２６】
グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者（以下、ＡＰ）装置の公開鍵と、前記ＡＰ装置の識別子と、整数ｋ、ｉ、及びｌとを入力するためのステップと、
前記グループメンバーとしての秘密鍵から整数ｙを作り、前記ＡＰ装置の識別子と、前記ｋ、ｉ、ｌ、及びｙとを入力として、前記タグ生成ステップにてタグを成すデータを計算するステップと、
前記タグの正当性証明文を計算するステップと、
前記タグと前記正当性証明文とを出力するステップと、
を有するグループ証明ステップを更に備えたことを特徴とする請求項１９記載の回数制限匿名認証方法。
【請求項２７】
有限群の元τと有限群の元μと整数ｌと証明文ｐとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数ｌ’と証明文ｐ’とを要素とする第二の組とを入力するためのステップと、
前記τと前記τ’とが同一であるか否かを判定するステップと、
前記ｌと前記ｌ’とが同一であるか否かを判定するステップと、
前記証明文ｐが正当であるか否かを判定するステップと、
前記証明文ｐ’が正当であるか否かを判定するステップと、
予め設定された対応表に基づいて、前記メンバー特定情報抽出ステップの計算結果と対応する識別子を取得するステップと、
を有するトレースステップを更に備えたことを特徴とする請求項２３記載の回数制限匿名認証方法。
【請求項２８】
有限群の元τと有限群の元μと整数ｌと証明文ｐとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数ｌ’と証明文ｐ’とを要素とする第二の組とを入力するためのステップと、
前記τと前記τ’とが同一であるか否かを判定するステップと、
前記ｌと前記ｌ’とが同一であるか否かを判定するステップと、
前記証明文ｐが正当であるか否かを判定するステップと、
前記証明文ｐ’が正当であるか否かを判定するステップと、
予め設定された対応表に基づいて、前記メンバー特定情報抽出ステップの計算結果と対応する識別子を取得するステップと、
を有するトレースステップを更に備えたことを特徴とする請求項２４記載の回数制限匿名認証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、擬似ランダム関数計算装置及び方法、並びに回数制限匿名認証システム及び方法に係り、特に効率的な擬似ランダム関数及びそれを用いた効率的な回数制限匿名認証方式に関する。
【背景技術】
【０００２】
一方向性関数を用いて擬似ランダム関数を実現する方法が知られている（例えば、非特許文献５参照）が、この方法で実現した擬似ランダム関数ｆは、ｙ＝ｆ（ｘ）を満たすｘの知識のゼロ知識証明を効率的に行うことはできない。ｙ＝ｆ（ｘ）を満たすｘの知識のゼロ知識証明を効率的に行うことができれば、様々な暗号プロトコルを効率的に実現できるので、擬似ランダム関数で効率的なものが望まれる。
【０００３】
一方、電子投票、電子現金、電子クーポン、回数制限付き視聴といった多くのアプリケーションでは、ユーザのプライバシーを守るため、ユーザが匿名でこれらのアプリケーションを使える必要がある。しかも、これらのアプリケーションでは、これと同時に、ユーザがアプリケーションを使用できる回数を制限する必要がある。
【０００４】
回数制限匿名認証方式（例えば、非特許文献４参照）は、このようなアプリケーションを実現するのに適した方式である。ユーザがアプリケーションを利用する度に、アプリケーション提供者（ＡＰ）がユーザをこの方式に従って認証することで、回数制限を守っている正直なユーザには匿名性を提供し、そうでないユーザは皆に特定されてしまうようにできる。
【０００５】
特に非特許文献４では、タグ・メカニズムという、ユーザの認証回数を匿名のままカウントする仕組みを提案し、ＡＣＪＴグループ署名方式（例えば、非特許文献１参照）のメンバー追加プロシージャとタグ・メカニズムとを組み合わせることで、回数制限匿名認証方式を実現している。
【０００６】
しかし、上記の回数制限匿名認証方式で用いられるタグ・メカニズムは、効率が悪く、認証時には、ＡＰとユーザは、ともに制限回数ｋに比例した回数の巾乗剰余を計算する必要がある。例えば、電子クーポンや回数制限つき視聴の場合には、制限回数が１０を越えることも十分考えられる。このため、上記の非特許文献４の方式は、これらに応用するには効率が悪い。
【非特許文献１】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
【非特許文献２】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
【非特許文献３】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
【非特許文献４】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
【非特許文献５】Oded Goldreich, “Foundation of Cryptography, Basic Tools”, Cambridge University Press, ISBN 0-521-79172-3, USA, 2001, pp. 148-169
【発明の開示】
【発明が解決しようとする課題】
【０００７】
既存の擬似ランダム関数の問題点は、擬似ランダム関数ｆは、ｙ＝ｆ（ｘ）を満たすｘの知識のゼロ知識証明を効率的に行うことはできないことにある。その理由は、ｆの計算方法が複雑なためである。
【０００８】
既存の回数制限匿名認証方式の問題点は、認証時におけるユーザの計算量が回数制限ｋに比例することである。
【０００９】
本発明は、このような従来の事情を考慮してなされたもので、効率的な擬似ランダム関数及びそれを用いた効率的な回数制限匿名認証方式を実現することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、本発明に係る擬似ランダム関数計算装置は、有限群の元を構成する要素として少なくとも第一の要素及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管し、生成された前記公開鍵を公開する鍵生成手段と、整数が入力されると、擬似ランダム関数の関数値として、前記有限群の元を出力する擬似ランダム関数計算手段とを有し、前記擬似ランダム関数計算手段は、前記有限群の元として、前記公開鍵の前記第一の要素を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、
前記公開鍵の前記第二の要素を底とし、前記秘密鍵と前記入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元と、の積を出力することを特徴とする。
【００１１】
本発明の別の側面に係る擬似ランダム関数計算装置は、整数からなる秘密鍵を生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管する鍵生成手段と、ビット列と整数との組が入力されると、擬似ランダム関数の関数値として、有限群の元を出力する擬似ランダム関数計算手段とを有し、前記擬似ランダム関数計算手段は、前記有限群の元として、前記入力された値で決まる値を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、前記入力された値で決まる値を底とし、前記秘密鍵と前記入力された整数の和の逆数を指数として、べき乗剰余を計算して得られる値を指数として、べき乗剰余演算により得られる値からなる第二の元と、の積を出力することを特徴とする。本発明において、前記底は、前記入力された値のハッシュ値であってもよい。
【００１２】
本発明に係る回数制限匿名認証システムは、上記いずれかに記載の擬似ランダム関数計算装置を用いた回数制限匿名認証システムであって、識別子と、整数ｋ、ｉ、ｙ、及びｌと、有限群の元ｔとを入力するための入力手段と、前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算手段と、前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をｌ乗した値にｔを乗じた値を計算する第二タグ計算手段と、前記第一タグ計算手段の計算結果と前記第二タグ計算手段の計算結果との組を出力する出力手段とを有するタグ生成手段を備えたことを特徴とする回数制限匿名認証システム。
【００１３】
本発明において、整数ｋを入力するための入力手段と、電子署名方式の公開鍵及び秘密鍵ペアを選ぶ電子署名用鍵生成手段と、ｋ個の整数を選ぶ平文選択手段と、前記ｋ個の整数各々に対する署名文を前記公開鍵及び秘密鍵ペアを用いて計算する電子署名計算手段と、
前記電子署名方式の公開鍵と前記ｋ個の整数と前記ｋ個の署名文とからなる組を、前記タグ生成手段の計算に使用されるタグ用公開鍵として出力する出力手段と、を有するタグ用鍵生成手段を更に備えてもよい。
【００１４】
前記電子署名計算手段は、平文として整数を入力するための手段と、平文と整数の和の有限体での逆元を計算する手段と、計算された前記逆元を指数としてべき乗剰余を計算し、前記べき乗剰余の計算結果を含む組を前記タグ用公開鍵として出力する手段とを有してもよい。
【００１５】
前記電子署名用鍵生成手段は、有限群から元を選ぶ手段と、整数を選ぶ手段と、前記元を底とし、前記整数を指数として、べき乗剰余を計算する手段と、選ばれた前記有限群の元と前記べき乗剰余の計算結果とからなる組を出力する手段とを有してもよい。
【００１６】
本発明において、前記タグ生成手段に整数ｌを入力して計算される計算結果をτとし、前記タグ生成手段に整数ｌ’を入力して計算される計算結果をτ’としたとき、前記τ、ｌ、τ’、ｌ’の四つのデータを入力するための入力手段と、前記τを前記τ’で割った値を底とし、前記ｌから前記ｌ’を減じた値の有限体での逆数を指数として、べき乗剰余を計算する計算手段と、前記べき乗剰余の計算結果を出力する出力手段と、を有するメンバー特定情報抽出手段を更に備えてもよい。
【００１７】
本発明において、グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者（以下、ＡＰ）装置の公開鍵と、前記ＡＰ装置の識別子と、整数ｋ、ｉ、及びｌとを入力するための入力手段と、前記グループメンバーとしての秘密鍵から整数ｙを作り、前記ＡＰ装置の識別子と、前記ｋ、ｉ、ｌ、及びｙとを入力として、前記タグ生成手段によりタグを成すデータを計算する手段と、前記タグの正当性証明文を計算する正当性証明手段と、前記タグと前記正当性証明文とを出力する出力手段と、を有するグループ証明手段を更に備えてもよい。
【００１８】
本発明において、有限群の元τと有限群の元μと整数ｌと証明文ｐとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数ｌ’と証明文ｐ’とを要素とする第二の組とを入力するための入力手段と、前記τと前記τ’とが同一であるか否かを判定する第一判定手段と、前記ｌと前記ｌ’とが同一であるか否かを判定する第二判定手段と、前記証明文ｐが正当であるか否かを判定する第三判定手段と、前記証明文ｐ’が正当であるか否かを判定する第四判定手段と、予め設定された対応表に基づいて、前記メンバー特定情報抽出手段の計算結果と対応する識別子を取得する識別子取得手段と、を有するトレース手段を更に有してもよい。
【００１９】
本発明に係る擬似ランダム関数計算方法は、有限群の元を構成する要素として少なくとも第一の要素及び第二の要素を持つ組からなる公開鍵と、整数からなる秘密鍵とを生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管し、生成された前記公開鍵を公開する鍵生成ステップと、整数が入力されると、擬似ランダム関数の関数値として、前記有限群の元を出力する擬似ランダム関数計算ステップとを有し、前記擬似ランダム関数計算ステップは、前記有限群の元として、前記公開鍵の前記第一の要素を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、前記公開鍵の前記第二の要素を底とし、前記秘密鍵と前記入力された整数との和の有限体での逆数を指数として、べき乗剰余を計算して得られる値からなる第二の元と、の積を出力することを特徴とする。
【００２０】
本発明の別の側面に係る擬似ランダム関数計算方法は、整数からなる秘密鍵を生成し、生成された前記秘密鍵を記憶装置に秘密裡に保管する鍵生成ステップと、ビット列と整数との組が入力されると、擬似ランダム関数の関数値として、有限群の元を出力する擬似ランダム関数計算ステップとを有し、前記擬似ランダム関数計算ステップは、前記有限群の元として、前記入力された値で決まる値を底とし、前記入力された整数を指数として、べき乗剰余を計算して得られる値からなる第一の元と、前記入力された値で決まる値を底とし、前記秘密鍵と前記入力された整数の和の逆数を指数として、べき乗剰余を計算して得られる値を指数として、べき乗剰余演算により得られる値からなる第二の元と、の積を出力することを特徴とする。本発明において、前記底は、前記入力された値のハッシュ値であってもよい。
【００２１】
本発明に係る回数制限匿名認証方法は、上記いずれかに記載の擬似ランダム関数計算方法を用いた回数制限匿名認証方法であって、識別子と、整数ｋ、ｉ、ｙ、及びｌと、有限群の元ｔとを入力するためのステップと、前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算する第一タグ計算ステップと、前記ｙを秘密鍵として用い、前記識別子と前記ｋと前記ｉとから決まる値を入力して、前記有限群に値をとる擬似ランダム関数の関数値を計算し、計算された擬似ランダム関数の関数値をｌ乗した値にｔを乗じた値を計算する第二タグ計算ステップと、前記第一タグ計算ステップの計算結果と前記第二タグ計算ステップの計算結果との組を出力するステップとを有するタグ生成ステップを備えたことを特徴とする。
【００２２】
本発明において、整数ｋを入力するための入力ステップと、電子署名方式の公開鍵及び秘密鍵ペアを選ぶ電子署名用鍵生成ステップと、ｋ個の整数を選ぶ平文選択ステップと、前記ｋ個の整数各々に対する署名文を前記公開鍵及び秘密鍵ペアを用いて計算する電子署名計算ステップと、前記電子署名方式の公開鍵と前記ｋ個の整数と前記ｋ個の署名文とからなる組を、前記タグ生成手段の計算に使用されるタグ用公開鍵として出力する出力ステップと、を有するタグ用鍵生成ステップを更に備えてもよい。
【００２３】
前記電子署名計算ステップは、平文として整数を入力するためのステップと、平文と整数の和の有限体での逆元を計算するステップと、計算された前記逆元を指数としてべき乗剰余を計算し、前記べき乗剰余の計算結果を含む組を前記タグ用公開鍵として出力するステップとを有してもよい。
【００２４】
前記電子署名用鍵生成ステップは、有限群から元を選ぶステップと、整数を選ぶステップと、前記元を底とし、前記整数を指数として、べき乗剰余を計算するステップと、選ばれた前記有限群の元と前記べき乗剰余の計算結果とからなる組を出力するステップとを有してもよい。
【００２５】
本発明において、前記タグ生成ステップにて整数ｌを入力して計算される計算結果をτとし、前記タグ生成ステップにて整数ｌ’を入力して計算される計算結果をτ’としたとき、前記τ、ｌ、τ’、ｌ’の四つのデータを入力するためのステップと、前記τを前記τ’で割った値を底とし、前記ｌから前記ｌ’を減じた値の有限体での逆数を指数として、べき乗剰余を計算するステップと、前記べき乗剰余の計算結果を出力するステップと、
を有するメンバー特定情報抽出ステップを更に備えてもよい。
【００２６】
本発明において、グループメンバーとしての公開鍵及び秘密鍵ペアと、アプリケーション提供者（以下、ＡＰ）装置の公開鍵と、前記ＡＰ装置の識別子と、整数ｋ、ｉ、及びｌとを入力するためのステップと、前記グループメンバーとしての秘密鍵から整数ｙを作り、前記ＡＰ装置の識別子と、前記ｋ、ｉ、ｌ、及びｙとを入力として、前記タグ生成ステップにてタグを成すデータを計算するステップと、前記タグの正当性証明文を計算するステップと、前記タグと前記正当性証明文とを出力するステップと、を有するグループ証明ステップを更に備えてもよい。
【００２７】
本発明において、有限群の元τと有限群の元μと整数ｌと証明文ｐとを要素とする第一の組と、有限群の元τ’と有限群の元μ’と整数ｌ’と証明文ｐ’とを要素とする第二の組とを入力するためのステップと、前記τと前記τ’とが同一であるか否かを判定するステップと、前記ｌと前記ｌ’とが同一であるか否かを判定するステップと、前記証明文ｐが正当であるか否かを判定するステップと、前記証明文ｐ’が正当であるか否かを判定するステップと、予め設定された対応表に基づいて、前記メンバー特定情報抽出ステップの計算結果と対応する識別子を取得するステップと、を有するトレースステップを更に備えてもよい。
【発明の効果】
【００２８】
本発明によれば、効率的な擬似ランダム関数及びそれを用いた効率的な回数制限匿名認証方式を実現できる。
【００２９】
即ち、擬似ランダム関数は、少ない回数の逆数計算とべき乗剰余とで関数値を計算できる。関数値の計算アルゴリズムが単純単純になり、これにより、ｙ＝ｆ（ｘ）を満たすｘの知識のゼロ知識証明を効率的に行うことができ、既存の擬似ランダム関数の問題点を解決できる。
【００３０】
また、回数制限匿名認証では、既存の方式とは異なり、ユーザが計算すべきデータ個数がＯ（ｌｏｇ  ｋ）個である。よって、認証時におけるユーザの計算量は制限回数ｋに比例しない。
【発明を実施するための最良の形態】
【００３１】
以下、本発明に係る擬似ランダム関数計算装置及び方法、並びに回数制限匿名認証システム及び方法を実施するための最良の形態について、添付図面を参照して説明する。
【実施例１】
【００３２】
本実施例は、擬似ランダム関数計算装置に適用したものである。
【００３３】
図２を参照して、本実施例の装置構成を説明する。図２に示す擬似ランダム関数計算装置１は、機能上、擬似ランダム関数用鍵生成手段２、秘密鍵記憶部３、公開鍵記憶部４、入力手段５、擬似ランダム関数計算手段６、及び出力手段７を有している。
【００３４】
擬似ランダム関数計算装置１は、一例としてコンピュータ機のＣＰＵ、記憶装置、その他の各種入出力装置によって実現される。この例では、擬似ランダム関数用鍵生成手段２及び擬似ランダム関数計算手段６は、コンピュータ機のＣＰＵが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、各手段２、６の処理アルゴリズム（後述参照）に応じて予め設定される。また、秘密鍵記憶部３及び公開鍵記憶部４は、コンピュータ機の記憶装置により実装される。さらに、入力手段５及び出力手段７は、コンピュータ機の入出力装置に対応する。
【００３５】
以下の説明では、ωをセキュリティ・パラメータとし、Ｇ＿１を有限巡回群でＧ＿１の位数がωビットの整数であるものとし、ｑをＧ＿１の位数とする。本実施例の擬似ランダム関数計算装置１は、なんらかの方法でＧ＿１のパラメータ、ω、およびｑを事前に入手しており、Ｇ＿１のパラメータ、ω、およびｑが公開鍵記憶部４に書き込まれているものとする。Ｇ＿１のパラメータ、ω、およびｑを入手する方法は、どのようなものでもよい。例えば、外部からの入力として得る、装置の回路にハードウェア的に書き込んでおく、といった方法がある。
【００３６】
次に、擬似ランダム関数用鍵生成手段２及び擬似ランダム関数計算手段６の処理手順を図３に従って説明する。図３に示す処理手順は、コンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、コンピュータ機のＣＰＵにより実行される。
【００３７】
図３において、擬似ランダム関数用鍵生成手段２は、次の処理を実行する。まず、Ｇ＿１の元ｇ、ｈをランダムに選ぶ（ステップＳ１）。次に、Ｚ＿ｑの元ｙをランダムに選ぶ（ステップＳ２）。次に、ｙを秘密鍵記憶部３に、（ｇ，ｈ）を公開鍵記憶部４にそれぞれ書き込む（ステップＳ３）。最後に、（ｇ，ｈ）を出力する（ステップＳ４）。
【００３８】
図３において、擬似ランダム関数計算手段６は、次の処理を実行する。まず、Ｇ＿１の元ｉを入力として受け取る（ステップＳ５）。次に、ｆ（ｉ）＝ｇ＾｛ｉ｝ｈ＾｛１／（ｙ＋ｉ）｝を計算する（ステップＳ６）。最後に、ｆ（ｉ）を出力する（ステップＳ７）。
【００３９】
従って、本実施例によれば、少ない回数の逆数計算とべき乗剰余とで擬似ランダム関数の関数値を計算できるため、関数値の計算アルゴリズムが単純になり、これにより、ｙ＝ｆ（ｘ）を満たすｘの知識のゼロ知識証明を効率的に行うことができる。
【実施例２】
【００４０】
本実施例は、擬似ランダム関数計算装置に適用したものである。
【００４１】
図４を参照して、本実施例の装置構成を説明する。図４に示す本実施例の擬似ランダム関数計算装置１は、機能上、擬似ランダム関数用鍵生成手段２、秘密鍵記憶部３、公開鍵記憶部４、入力手段５、擬似ランダム関数計算手段６、及び出力手段７を有している。
【００４２】
擬似ランダム関数計算装置１は、一例としてコンピュータ機のＣＰＵ、記憶装置、その他の各種入出力装置によって実現される。この例では、擬似ランダム関数用鍵生成手段２及び擬似ランダム関数計算手段６は、コンピュータ機のＣＰＵが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、各手段２、６の処理アルゴリズム（後述参照）に応じて予め設定される。また、秘密鍵記憶部３及び公開鍵記憶部４は、コンピュータ機の記憶装置により実装される。さらに、入力手段５及び出力手段７は、コンピュータ機の入出力装置に対応する。
【００４３】
以下の説明では、ωをセキュリティ・パラメータとし、Ｇ＿１を有限巡回群でＧ＿１の位数がωビットの整数であるものとし、ｑをＧ＿１の位数とする。本実施例の擬似ランダム関数計算装置は、なんらかの方法でＧ＿１のパラメータ、ω、およびｑを事前に入手しており、Ｇ＿１のパラメータ、ω、およびｑが公開鍵記憶部４に書き込まれているものとする。Ｇ＿１のパラメータ、ω、およびｑを入手する方法はどのようなものでもよい。例えば、外部からの入力として得る、装置の回路にハードウェア的に書き込んでおく、といった方法がある。
【００４４】
次に、擬似ランダム関数用鍵生成手段２の処理手順を図５に従って説明する。図５に示す処理手順は、コンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、コンピュータ機のＣＰＵにより実行される。
【００４５】
図５において、擬似ランダム関数用鍵生成手段２は、Ｚ＿ｑの元ｙをランダムに選び（ステップＳ１１）、ｙを秘密鍵記憶部３に書き込む（ステップＳ１２）。
【００４６】
図５において、擬似ランダム関数計算手段６は、次の処理を実行する。
【００４７】
まず、ビット列ＸとＧ＿１の元ｉを入力として受け取る（ステップＳ１３）。
【００４８】
次に、（ｇ＿｛Ｘ｝，ｈ＿｛Ｘ｝）＝Ｈ＿｛Ｇ＿１＾２｝（Ｘ）を計算する（ステップＳ１４）。ここで、Ｈ＿｛Ｇ＿１＾２｝は、Ｇ＿１＾２に値を取るハッシュ関数を示す。
【００４９】
次に、ｆ［ｙ］＿｛ω｝（ｉ，Ｘ）＝ｇ＿｛Ｘ｝＾｛ｉ｝ｈ＿｛Ｘ｝＾｛１／（ｙ＋ｉ）｝を計算する（ステップＳ１５）。
【００５０】
最後に、ｆ［ｙ］＿｛ω｝（ｉ，Ｘ）を出力する（ステップＳ１６）。
【００５１】
従って、本実施例でも、前述の実施例１と同様に、少ない回数の逆数計算とべき乗剰余とで擬似ランダム関数の関数値を計算できるため、関数値の計算アルゴリズムが単純になり、これにより、ｙ＝ｆ（ｘ）を満たすｘの知識のゼロ知識証明を効率的に行うことができる。
【実施例３】
【００５２】
本実施例は、前述した擬似ランダム関数計算装置を用いた回数制限匿名認証システムに適用したものである。
【００５３】
図６を参照して、本実施例の装置構成を説明する。図６に示すシステムは、機能上、メンバー特定情報生成装置１０、乱数生成装置２０、タグ生成装置３０、メンバー特定情報抽出装置４０、及び鍵生成装置５０を有している。前述した擬似ランダム関数計算装置は、タグ生成装置３０により用いられている。
【００５４】
メンバー特定情報生成装置１０は、機能上、秘密鍵生成手段１１、公開情報記憶部１２、メンバー特定情報生成手段１３、書き込み手段１４、及び通信手段１５を備える。
【００５５】
乱数生成装置２０は、機能上、公開情報記憶部２１、乱数選択手段２２、及び通信手段２３を備える。
【００５６】
タグ生成装置３０は、前述した擬似ランダム関数計算装置を用いたもので、機能上、公開情報記憶部３１、タグ計算手段３２、入力手段３３、及び通信装置３４を備える。
【００５７】
メンバー特定情報抽出装置４０は、機能上、公開情報記憶部４１、メンバー特定情報抽出手段４２、一致性判定手段４３、出力手段４４、及び通信装置４５を備える。
【００５８】
鍵生成装置５０は、機能上、入力手段５１、公開情報記憶部５２、タグ用鍵生成手段５３、及び通信手段５４を備える。
【００５９】
上記の各装置１０〜５０は、一例としてコンピュータ機のＣＰＵ、記憶装置、ネットワークインターフェース部、その他の各種入出力装置によって実現される。この例では、各手段１１、１３、１４、２２、３２、４２、４３、５３は、各コンピュータ機のＣＰＵが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、各手段の処理アルゴリズム（後述参照）に応じて予め設定される。また、公開情報記憶部１２、２１、３１、４１、５２は、各コンピュータ機の記憶装置により実装される。通信手段１５、２３、５４、及び通信装置３４，４５は、各コンピュータ機のネットワークインターフェース部に、また入力手段２３、５１、及び出力手段４４は、各コンピュータ機の入出力装置にそれぞれ対応する。
【００６０】
図６では、もっとも単純な場合として、５種類の装置１０〜５０がそれぞれ一台ずつしかない場合を描いているが、各種類の装置が複数台あってもかまわない。また、図６では、各装置１０〜５０が別々の機械である場合を描いているが、一つの機械が二種類の装置の機能を兼ねていてもかまわない。
【００６１】
メンバー特定情報生成装置１０、乱数生成装置２０、タグ生成装置３０、メンバー特定情報抽出装置４０、及び鍵生成装置５０は、それぞれ通信手段１４、２３、３４、４５、５４を使って相互に通信できる。通信媒体としては、どのような通信媒体を用いてもかまわない。例えばインターネット、電波、電話回線といったものを用いることができる。
【００６２】
各装置１０〜５０は、他の装置が公開している公開情報をなんらかの方法で入手できるものとする。公開情報の入手手段は、どのような方法を用いてもかまわない。例えば、公開情報を公開している装置から前述の通信手段を用いて直接受け取る方法、公開情報のリストを持っているサーバから前述の通信手段を用いて受け取る方法、を用いることができる。
【００６３】
次に、本実施例の動作を図７及び図８に従って説明する。図７及び図８に示す処理手順は、各装置に対応するコンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、各コンピュータ機のＣＰＵにより実行される。
【００６４】
以下の説明では、ωをセキュリティ・パラメータとし、Ｇ＿１を有限巡回群でＧ＿１の位数がωビットの整数であるものとし、ｑをＧ＿１の位数とする。本実施例で適用される擬似ランダム関数計算装置は、なんらかの方法でＧ＿１のパラメータ、ω、およびｑを事前に入手しており、Ｇ＿１のパラメータ、ω、およびｑが各装置１０〜５０の公開情報記憶部１２、２１、３１、４１、５２に書き込まれているものとする。Ｇ＿１のパラメータ、ω、およびｑを入手する方法はどのようなものでもよい。例えば外部からの入力として得る、装置の回路にハードウェア的に書き込んでおく、といった方法がある。各装置１０〜５０は、必要に応じてこれらのデータを読み込む。
【００６５】
図７において、まず、メンバー特定情報生成装置１０は、秘密鍵生成手段１１の処理を行って、Ｚ＿ｑの元ｙをランダムに選ぶ（ステップＳ２１）。ｇ＿１をＧ＿１の元とし、ν＿｛ω｝（ｙ）＝ｇ＿１＾｛ｙ｝とする。ｇ＿１は事前に何らかの方法で選ばれ、全ての装置１０〜５０の公開情報記憶部１２、２１、３１、４１、５２に事前に記憶されているものとする。ｇ＿１をどのような方法で選び、どのような方法で各装置１０〜５０に配布してもかまわないが、安全性の観点から言えば、ｇ＿１を何らかの値のハッシュ値にセットすることが望ましい。
【００６６】
次にメンバー特定情報生成装置１０は、メンバー特定情報生成手段４２の処理を行って、ｔ＿１＝ν＿｛ω｝（ｙ）とする（ステップＳ２２）。
【００６７】
ここで、Ｇ＿２、Ｈ＿２、Ｇ＿３を、位数がｑである有限巡回群とし、＜・，・＞はＧ＿２×Ｈ＿２の元（ｇ，ｈ’）にＧ＿３の元＜ｇ，ｈ’＞を対応させる写像で、＜ｇ＾ｘ，ｈ’＾ｙ＞＝＜ｇ，ｈ’＞＾｛ｘｙ｝が任意のｇ，ｈ’，ｘ，ｙに対して成立するものとする。このような組（Ｇ＿２、Ｈ＿２、Ｇ＿３、＜・，・＞）の生成方法、および＜・，・＞の計算方法は様々なものが知られているが、そのどれを用いてもよい（例えば、非特許文献２参照）。
【００６８】
次に、鍵生成装置５０がタグ用鍵生成手段５３の処理を行う。
【００６９】
タグ用鍵生成手段５３は、ステップＳ２３、Ｓ２４にて、それぞれ電子署名用鍵生成手段、電子署名手段による処理を行うので、タグ用鍵生成手段５３の処理を説明する前に、電子署名用鍵生成手段と、電子署名手段との各処理を図８に従って説明する。
【００７０】
図８において、電子署名用鍵生成手段は、まず、Ｇ＿２の元ｇ＿２をランダムに選ぶ（ステップＳ４１）。次に、Ｈ＿２の元ｇ’＿２をランダムに選ぶ（ステップＳ４２）。次に、Ｚ＿ｑの元ｓｓｋをランダムに選ぶ（ステップＳ４３）。
【００７１】
次に、ｈ’＿２＝ｇ’＿２＾｛ｓｓｋ｝を計算する（ステップＳ４４）。
【００７２】
最後に、（ｇ＿２，ｇ’＿２，ｈ’＿２）を電子署名用公開鍵ｓｐｋとしてセットする（ステップＳ４５）。
【００７３】
電子署名手段は、まず、ｓｐｋを（ｇ＿２，ｇ’＿２，ｈ’＿２）とパースする（ステップＳ４６）。次に、平文βに対する署名文Ｓ＝ｇ＿２＾｛１／（ｓｓｋ＋β）｝を計算する（ステップＳ４７）。
【００７４】
鍵生成装置５０は、非負整数ｋを入力として受け取ったら、図７に示すタグ用鍵生成手段５３の処理を行う。
【００７５】
図７において、まず、鍵生成装置５０は、電子署名用鍵生成手段の処理を行い、電子署名用公開鍵ｓｐｋと、電子署名用秘密鍵ｓｓｋとを生成する（ステップＳ２３）。
【００７６】
次に、鍵生成装置５０は、平文β＿１，…，β＿ｋを選び、（ｓｐｋ，ｓｓｋ）を使って電子署名手段の処理を行い、各β＿ｉに対する署名文Ｓ＿ｉを作成する（ステップＳ２４）。
【００７７】
最後に鍵生成装置５０は、ａｐｋ＝（ｓｐｋ，（β＿１，Ｓ＿１），…，（β＿ｋ，Ｓ＿ｋ））とする（ステップＳ２５）。
【００７８】
次に乱数生成装置２０は、乱数選択手段２１の処理を行い、Ｚ＿ｑの元ｌをランダムに選んで出力する（ステップＳ２６）。
【００７９】
次にタグ生成装置３０は、通信手段２３、３４を使って乱数生成装置２０と通信して、ｌを受信し、通信装置５４、３４を使って鍵生成装置５０と通信して、ａｐｋを受信し、タグ生成手段３２の処理を開始する。このタグ生成手段３２の処理を説明する。
【００８０】
まず、タグ生成装置３０は、タグ生成手段３２の処理により、タグ生成装置３０のＩＤ、タグ生成装置３２がアクセスを許す回数の上限値ｋ，および現時点でのアクセス回数ｉ（ｉ≦ｋ）を受け取る（ステップＳ２７）。
【００８１】
次にタグ生成装置３０は、ａｐｋを（ｓｐｋ，（β＿１，Ｓ＿１），…，（β＿ｋ，Ｓ＿ｋ））とパースする（ステップＳ２８）。
【００８２】
次にタグ生成装置３０は、ｆ［ｙ］＿｛ω｝を実施例２の擬似ランダム関数とし、Ｆ［ｙ］＿｛ω｝（Ｘ，ｉ）＝ｆ［ｙ］＿｛ω｝（Ｘ，−ｉ）とする。
【００８３】
最後に、タグ生成装置３０は、（τ，μ）＝（ｆ［ｙ］＿｛ω｝（ＩＤ｜｜ｋ，β＿ｉ），Ｆ［ｙ］＿｛ω｝（ＩＤ｜｜ｋ，β＿ｉ））を計算する（ステップＳ２９）。ｆ［ｙ］＿｛ω｝とＦ［ｙ］＿｛ω｝は、前述した実施例２の擬似ランダム関数計算手段６の処理を行うことで計算する。
【００８４】
次に、タグ生成手段３２の処理が同じ入力（ＩＤ，ｋ，ｉ）を使って二度行われたとする。各タグ生成手段３２の出力を（τ，μ，ｌ）、（τ，μ’，ｌ’）とする。
【００８５】
この場合、メンバー特定情報抽出装置４０は、通信手段３４、４５を使って、タグ生成装置３０から（μ，ｌ）、（μ’，ｌ’）を受け取り、メンバー特定情報抽出手段４２と一致性判定手段４３の各処理を順に行う。
【００８６】
メンバー特定情報抽出装置４０は、メンバー特定情報抽出手段４２の処理を行い、（μ／μ’）＾｛１／（ｌ−ｌ’）｝を計算する（ステップＳ３０、Ｓ３１）。
【００８７】
メンバー特定情報抽出装置４０は、一致性判定手段４３の処理を行い、ｔ＿１と（μ／μ’）＾｛１／（ｌ−ｌ’）｝とが入力されたら、ｔ＿１＝（τ／τ’）＾｛１／（ｌ−ｌ’）｝であるかどうかを出力する（ステップＳ３２）。
【００８８】
従って、本実施例によれば、回数制限匿名認証は既存の方式とは異なり、ユーザが計算すべきデータ個数がＯ（ｌｏｇ  ｋ）個であるため、認証時におけるユーザの計算量は制限回数ｋに比例しないから、効率的な回数制限匿名認証方式を実現することができる。
【実施例４】
【００８９】
本実施例は、前述した擬似ランダム関数計算装置を用いた回数制限匿名認証システムに適用したものである。
【００９０】
図９を参照して、本実施例の装置構成を説明する。図９に示すシステムは、機能上、メンバー特定情報生成装置１０、乱数生成装置２０、タグ生成装置３０、及びメンバー特定情報抽出装置４０を有している。前述した擬似ランダム関数計算装置は、タグ生成装置３０により用いられている。
【００９１】
メンバー特定情報生成装置１０は、機能上、秘密鍵生成手段１１、公開情報記憶部１２、メンバー特定情報生成手段１３、通信手段１４、及び書き込み手段１５を備える。
【００９２】
乱数生成装置２０は、機能上、公開情報記憶部２１、乱数選択手段２２、及び通信手段２３を備える。
【００９３】
タグ生成装置３０は、前述した擬似ランダム関数計算装置を用いたもので、機能上、公開情報記憶部３１、入力手段３３、通信装置３４、及びタグ計算手段３５を備える。
【００９４】
メンバー特定情報抽出装置４０は、機能上、公開情報記憶部４１、メンバー特定情報抽出手段４２、一致性判定手段４３、出力手段４４、及び通信装置４５を備える。
【００９５】
上記の各装置１０〜５０は、一例としてコンピュータ機のＣＰＵ、記憶装置、ネットワークインターフェース部、その他の各種入出力装置によって実現される。この例では、各手段１１、１３、１４、２２、４２、４３、５３は、各コンピュータ機のＣＰＵが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、これら各手段の処理アルゴリズム（後述参照）に応じて予め設定される。また、公開情報記憶部１２、２１、３１、４１、５２は、コンピュータ機の記憶装置により実装される。通信手段１５、２３、５４、及び通信装置３４，４５は、各コンピュータ機のネットワークインターフェース部に、また入力手段２３、５１、及び出力手段４４は、各コンピュータ機の入出力装置にそれぞれ対応する。
【００９６】
図９では、もっとも単純な場合として、５種類の装置がそれぞれ一台ずつしかない場合を描いているが、各種類の装置が複数台あってもかまわない。また、図では、各装置が別々の機械である場合を描いているが、一つの機械が二種類の装置の機能を兼ねていてもかまわない。
【００９７】
メンバー特定情報生成装置１０、乱数生成装置２０、タグ生成装置３０、メンバー特定情報抽出装置４０は、それぞれ通信手段１４、２３、３４、４５を使って相互に通信できる。通信媒体としてどのような通信媒体を用いてもかまわない。例えばインターネット、電波、電話回線といったものを用いることができる。
【００９８】
各装置１０〜４０は、他の装置が公開している公開情報をなんらかの方法で入手できるものとする。公開情報の入手手段は、どのような方法を用いてもかまわない。例えば、公開情報を公開している装置から前述の通信手段を用いて直接受け取る方法、公開情報のリストを持っているサーバから前述の通信手段を用いて受け取る方法、を用いることができる。
【００９９】
実施例４のメンバー特定情報生成装置１０、乱数生成装置２０、メンバー特定情報抽出装置４０は、前述した実施例３のメンバー特定情報生成装置１０、乱数生成装置２０、及びメンバー特定情報抽出装置４０と同じ動作をする。
【０１００】
また、実施例４のタグ生成装置３０の通信装置３４、公開情報記憶部３１、入力手段３３は、前述した実施例３のタグ生成装置３０の通信装置３４、公開情報記憶部３１、及び入力手段３３と同じ機能を持っている。
【０１０１】
次に、図１０を参照して、実施例４のタグ計算手段３５を説明する。図１０に示す処理手順は、コンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、コンピュータ機のＣＰＵにより実行される。
【０１０２】
以下の説明では、ωをセキュリティ・パラメータとし、Ｇ＿１を有限巡回群でＧ＿１の位数がωビットの整数であるものとし、ｑをＧ＿１の位数とする。擬似ランダム関数計算装置は、なんらかの方法でＧ＿１のパラメータ、ω、およびｑを事前に入手しており、Ｇ＿１のパラメータ、ω、およびｑが各装置の公開情報記憶部に書き込まれているものとする。Ｇ＿１のパラメータ、ω、およびｑを入手する方法どのようなものでもよい。例えば外部からの入力として得る、装置の回路にハードウェア的に書き込んでおく、といった方法がある。各装置１０〜５０は、必要に応じてこれらのデータを読み込む。
【０１０３】
図１０において、タグ生成装置３は、タグ計算手段３５の処理を行い、タグ生成装置のＩＤ、タグ生成装置がアクセスを許す回数の上限値ｋ、および現時点でのアクセス回数ｉ≦ｋを受け取る（ステップＳ５１）。
【０１０４】
ｆ［ｙ］＿｛ω｝を前述した実施例２の擬似ランダム関数とし、Ｆ［ｙ］＿｛ω｝（Ｘ，ｉ）＝ｆ［ｙ］＿｛ω｝（Ｘ，−ｉ）とする。
【０１０５】
最後に、タグ生成装置３は、（τ，μ）＝（ｆ［ｙ］＿｛ω｝（ＩＤ｜｜ｋ，ｉ），Ｆ［ｙ］＿｛ω｝（ＩＤ｜｜ｋ，ｉ））を計算する（ステップＳ５２）。
【０１０６】
ｆ［ｙ］＿｛ω｝とＦ［ｙ］＿｛ω｝は、実施例２の擬似ランダム関数計算手順ＢＰＲＦ５を行うことで計算する。
【０１０７】
従って、本実施例でも、前述の実施例３と同様に、回数制限匿名認証は既存の方式とは異なり、ユーザが計算すべきデータ個数がＯ（ｌｏｇ  ｋ）個であるため、認証時におけるユーザの計算量は制限回数ｋに比例しないから、効率的な回数制限匿名認証方式を実現することができる。
【実施例５】
【０１０８】
本実施例は、前述した擬似ランダム関数計算装置を用いた回数制限匿名認証システムに適用したものである。
【０１０９】
図１を参照して、本実施例の装置構成を説明する。
【０１１０】
図１に示す本実施例の回数制限匿名認証システムは、前述した実施例３、４のシステムに様々な計算手順を追加して構成されており、機能上、ＧＭ（Group Manager）装置（グループ管理装置）１００、リスト記憶装置２００、ユーザ装置３００、ＡＰ（Application Provider）装置（アプリケーション提供装置）４００、及びトレース装置５００の５種類の装置を備える。前述した擬似ランダム関数計算装置は、後述するグループ署名手段（グループ証明手段、グループ検証手段）に適用されている。
【０１１１】
ＧＭ装置１００は、機能上、ＧＭセットアップ手段１０１、発行手段１０２、秘密情報記憶部１０３、公開情報記憶部１０４、及び通信手段１０５を備える。
【０１１２】
リスト記憶装置２００は、機能上、リスト記憶部２０１、及び通信手段２０２を備える。
【０１１３】
ユーザ装置３００は、機能上、参加手段３０１、グループ証明手段３０２、秘密情報記憶部３０３、及び公開情報記憶部３０４、及び通信手段３０５を備える。
【０１１４】
ＡＰ装置４００は、機能上、ＡＰセットアップ手段４０１、グループ検証手段４０２、公開情報記憶部４０３、履歴記憶部４０４、及び通信手段４０５を備える。
【０１１５】
トレース装置５００は、機能上、トレース手段５０１、公開情報記憶部５０２、及び通信手段５０３を備える。
【０１１６】
上記の各装置１００〜５００は、一例としてコンピュータ機（サーバ機、クライアント機等）のＣＰＵ、記憶装置、ネットワークインターフェース部、その他の各種入出力装置によって実現される。この例では、各手段１０１、１０２、３０１、３０２、４０１、４０１、５０１は、各コンピュータ機のＣＰＵが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、これら各手段の処理アルゴリズム（後述参照）に応じて予め設定される。また、公開情報記憶部１０４、３０４、４０３、５０２、秘密情報記憶部１０３、３０３、リスト記憶部２０１、履歴記憶部４０４は、各コンピュータ機の記憶装置により実装される。通信手段１０５、２０２、３０５、４０５、５０３は、各コンピュータ機のネットワークインターフェース部に対応する。
【０１１７】
図１では、もっとも単純な場合として５種類の装置がそれぞれ一台ずつしかない場合を描いているが、各種類の装置が複数台あってもかまわない。また、図１では、各装置１００〜５００が別々の機械である場合を描いているが、一つの機械が二種類の装置の機能を兼ねていてもかまわない。例えばＧＭ装置１００の機能とリスト装置２００の機能を両方持つ機械を使ってもかまわない。
【０１１８】
ＧＭ装置１００、リスト記憶装置２００、ユーザ装置３００、ＡＰ装置４００、トレース装置５００は、それぞれ通信手段１０５、２０２、３０５、４０５、５０３を使って相互に通信できる。通信媒体としては、例えばインターネット、電波、電話回線といったものを用いることができるが、本発明ではどのような通信媒体を用いてもかまわない。
【０１１９】
ＧＭ装置１００、ユーザ装置３００、ＡＰ装置４００、トレース装置５００は、それぞれの公開情報記憶部１０４、３０４、４０３、５０２に、自分自身や他の装置が公開している公開情報を記憶する。また、リスト記憶装置２００は、リスト記憶部２０１という、公開情報を記憶するための部分を持っている。リスト記憶装置２００は、自分自身や他の装置が公開している公開情報をリスト記憶部２０１に記憶する。
【０１２０】
各装置１００〜５００は、他の装置が公開している公開情報をなんらかの方法で入手できるものとする。公開情報の入手手段としては例えば、公開情報を公開している装置から前述の通信手段を用いて直接受け取る方法、公開情報のリストを持っているサーバから前述の通信手段を用いて受け取る方法、といったものが考えられるが、どのような方法を用いてもかまわない。
【０１２１】
ＧＭ装置１００、ユーザ装置３００は、それぞれ秘密情報記憶部１０３、３０３にそれぞれの秘密情報を記憶する。
【０１２２】
各装置１００〜５００には、事前にセキュリティ・パラメータωが配布されている。セキュリティ・パラメータをどのような方法で配布するのか、セキュリティ・パラメータをどのような方法で決定するのかは問わない。
【０１２３】
ユーザ装置３００、ＡＰ装置４００には、事前に固有のＩＤが割り振られており、各装置１００〜５００は、全てのユーザ装置３００、ＡＰ装置４００のＩＤを事前に知っている。ＩＤとしてどのようなデータを用いるのか、ＩＤをどのように配布するのかは問わない。例えば、装置保有者の名前、装置に割り振られたＩＰアドレス、装置に割り振られたＭＡＣアドレス、および乱数といったものを装置のＩＤとして用いることができる。
【０１２４】
ＧＭ装置１００は、ＧＭセットアップ手段１０１により、発行者用鍵生成手段の処理を行う。以下、発行者用鍵生成手段の詳細を略して、ＧＭセットアップ手段１０１の処理を説明し、後で発行者用鍵生成手段の詳細を説明する。
【０１２５】
次に、本実施例の動作を図１１〜図２１を参照して説明する。図１１〜図２１に示す処理手順は、各装置に対応するコンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、各コンピュータ機のＣＰＵにより実行される。
【０１２６】
まず、ＧＭセットアップ手段１０１の処理を図１１に従って説明する。
【０１２７】
図１１において、ＧＭ装置１００は、まずセキュリティ・パラメータωを公開情報記憶部１０４から読み込む（ステップＳ６１）。ＧＭ装置１００は、次に発行者用鍵生成手段の処理を行い、ＧＭ公開鍵ｇｐｋとＧＭ秘密鍵ｇｓｋを作り（ステップＳ６２）、ｇｐｋを公開情報記憶部１０４に、ｇｓｋを秘密情報記憶部１０３に記憶する（ステップＳ６３）。
【０１２８】
次に、発行者用鍵生成手段の処理を図１６に従って説明する。
【０１２９】
以下の説明では、Ｇ＿２、Ｈ＿２、Ｇ＿３を有限巡回群とし、＜・，・＞はＧ＿２×Ｈ＿２の元（ｇ，ｈ’）にＧ＿３の元＜ｇ，ｈ’＞を対応させる写像で、＜ｇ＾ｘ，ｈ’＾ｙ＞＝＜ｇ，ｈ’＞＾｛ｘｙ｝が任意のｇ，ｈ’，ｘ，ｙに対して成立するものとする。このような組（Ｇ＿２、Ｈ＿２、Ｇ＿３、＜・，・＞）の生成方法、および＜・，・＞の計算方法は様々なものが知られているが、そのどれを用いてもよい。例えば非特許文献２を参照されたい。ｑをＧ＿２の位数とし、整数環ＺをイデアルｑＺで割った商環をＺ＿ｑと書く。
【０１３０】
図１６において、ＧＭ装置１００は、Ｇ＿２の元ｇ＿３、ｈ＿３、ａ＿３とＨ＿２の元ｇ’＿３をランダムに選ぶ（ステップＳ１３１、Ｓ１３２）。次に、ＧＭ装置１は、Ｚ＿ｑの元ｇｓｋをランダムに選ぶ（ステップＳ１３３）。次に、ＧＭ装置１は、ｕ’＿３＝ｇ＿３＾｛ｓｓｋ｝を計算する（ステップＳ１３４）。最後にＧＭ装置１は、（ｇ＿３，ｈ＿３，ａ＿３，ｇ’＿３，ｕ’＿３）を発行者用公開鍵ｇｐｋとしてセットする（ステップＳ１３５）。
【０１３１】
次に、ＧＭ装置１００の発行手段１０２とユーザ装置３００の参加手段３０２の各処理を説明する。
【０１３２】
ＧＭ装置１００とユーザ装置３００は、相互通信をしながら、それぞれ発行手段１０２、参加手段３０２の処理を行う。
【０１３３】
ＧＭ装置１００は、発行手段１０２により、第一発行手段、第二発行手段の各処理を行う。ユーザ装置３００は、参加手段３０２により、第一参加手段、ファイ計算手段、メンバー特定情報生成手段、第二参加手段、メンバー鍵検証手段の各処理を行う。
【０１３４】
まず、第一発行手段、第一参加手段、ファイ計算手段、メンバー特定情報生成手段、第二発行手段、第二参加手段、およびメンバー鍵検証手段の詳細を略して、発行手段１０２と参加手段３０２の説明を行い、その後で、第一発行手段、第一参加手段、ファイ計算手段、メンバー特定情報生成手段、第二発行手段、第二参加手段、及びメンバー鍵検証手段の詳細を説明する。
【０１３５】
最初に、ＧＭ装置１００の発行手段１０２とユーザ装置３００の参加手段３０２の各処理を図１２に従って説明する。
【０１３６】
図１２において、ＧＭ装置１００は、まず（ω，ｇｐｋ）を公開情報記憶部１０４から、ｇｓｋを秘密情報記憶部１０３から読み込む（ステップＳ７１）。
【０１３７】
ユーザ装置３００は、（ω，ｇｐｋ）を公開情報記憶部３０４から読み込む（ステップＳ８１）。
【０１３８】
次にＧＭ装置１００とユーザ装置３００は、互いに通信しながら、それぞれ第一発行手段、第一参加手段を行い、ＧＭ装置１００は、Ｓｔ＿｛ＧＭ｝を、ユーザ装置３００は、Ｓｔ＿｛Ｕ｝とメンバー秘密鍵ｍｓｋをそれぞれ得る（ステップＳ７２、Ｓ８２）。ただし、ＧＭ装置１００とユーザ装置３００のいずれかが、それぞれ第一発行手段、第一参加手段の各処理の途中で異常終了した場合は、それぞれ発行手段１０２、参加手段３０１の各処理を終了する（ステップＳ７２、Ｓ８２）。
【０１３９】
次にＧＭ装置１００は、ｇｐｋを公開情報記憶部１０４に、ｇｓｋを秘密情報記憶部１０３に書き込む（ステップＳ７３）。
【０１４０】
次にユーザ装置３００は、ファイ計算手段の処理を行い、ｙ＝φ＿｛ω｝（ｍｓｋ）を計算する（ステップＳ８３）。
【０１４１】
次にユーザ装置３００は、メンバー特定情報生成手段の処理を行い、メンバー特定情報ｔ＿１を得る（ステップＳ８４）。次に、ユーザ装置３００は、ｔ＿１とリスト記憶装置２００に送信する（ステップＳ８５）。
【０１４２】
リスト記憶装置２００は、受信したｔ＿１をユーザ装置３００のＩＤと組にしてリスト記憶部２０１に記憶する（ステップＳ８０）。
【０１４３】
次に、ＧＭ装置１００は、リスト装置２００からｔ＿１を受け取る（ステップＳ７４４）。もしリスト装置２００がｔ＿１を保管していなかったら、ＧＭ装置１００は、発行手段の処理を終了する（ステップＳ７５）。リスト装置２００からｔ＿１を受け取るのに成功したら、次に、ユーザ装置３００は、ｔ＿１の正当性をＧＭ装置１００に証明し、ＧＭ装置１００は、その証明を検証する（ステップＳ８６、Ｓ７６）。正当性証明は、どのような方法で行ってもよい。例えば非特許文献３の方法で行うことができる。
【０１４４】
ユーザ装置３００の証明が正当でなければ、ＧＭ装置１００は、発行手段の処理を終了する（ステップＳ７７）。ユーザ装置３００の証明が正当であれば、ＧＭ装置１００とユーザ装置３００は、それぞれ第二発行手段、第二参加手段の各処理を行い、ともにメンバー公開鍵ｍｐｋを得る（ステップＳ７８、Ｓ８７）。
【０１４５】
次にＧＭ装置１００は、ｍｐｋを公開情報記憶部１０４に書き込む（ステップＳ７９）。
【０１４６】
ユーザ装置３００は、メンバー鍵検証手段の処理を行うことで、ｖｅｒｋｅｙ（ｍｐｋ，ｍｓｋ）を計算し、ｖｅｒｋｅｙ（ｍｐｋ，ｍｓｋ）＝ａｃｃｅｐｔなら、（ｍｐｋ，ｍｓｋ）を公開情報記憶部３０４に書き込む（ステップＳ８８）。
【０１４７】
次に、第一発行手段と第一参加手段の各処理を図１７に従って説明する。
【０１４８】
図１７において、ＧＭ装置１００は、まずＧＭ公開鍵ｇｐｋを（ｇ＿３，ｈ＿３，ａ＿３，ｇ’＿３，ｕ’＿３）とパースする（ステップＳ１４１）。ユーザ装置３００も、ＧＭ公開鍵ｇｐｋを（ｇ＿３，ｈ＿３，ａ＿３，ｇ’＿３，ｕ’＿３）とパースする（ステップＳ１４５）。
【０１４９】
次にユーザ装置３００は、Ｚ＿ｑの元ｘ，ｒ’をランダムに選ぶ（ステップＳ１４６）。次に、ユーザ装置３００は、ｗ＝ａ＿３ｇ＿３＾｛ｘ｝・ｈ＿３＾｛ｒ’｝を計算する（ステップＳ１４７）。次に、ユーザ装置３００は、ｗをＧＭ装置１に送信する（ステップＳ１４８）。次に、ＧＭ装置１００は、ｗを受信する（ステップＳ１４２）。
【０１５０】
次にユーザ装置３００は、ｗの正当性をＧＭ装置１に証明し、ＧＭ装置１００は、その証明を検証する（ステップＳ１４９、Ｓ１４３）。証明は、どのような方法で行ってもよいが、例えば非特許文献３の方法で証明することができる。
【０１５１】
次にＧＭ装置１００は、ｗが正当なら、Ｓｔ＿｛ＧＭ｝＝ｗとして、第一発行手段の処理を正常終了し、そうでなければ、異常終了する（ステップＳ１４４）。最後に、ユーザ装置３００は、Ｓｔ＿｛Ｕ｝＝ｗとして、第一参加手段の処理を正常終了する（ステップＳ１５０）。
【０１５２】
次に、ファイ計算手段の処理を図１８に従って説明する。
【０１５３】
図１８において、ユーザ装置３００は、ｍｓｋを（ｘ，ｒ’）とパースする（ステップＳ１６１）。ユーザ装置３００は、ｙ＝ｘとする（ステップＳ１６２）。
【０１５４】
次に、メンバー特定情報生成手段の処理を図７に従って説明する。
【０１５５】
ユーザ装置３００は、前述した実施例３のメンバー特定情報生成手段の処理（図７）を行い、ｔ＿１＝ν＿｛ω｝（ｙ）＝ｇ＿１＾ｙを計算する（ステップＳ２２）。ここで、ｇ＿１は事前に決められた公開情報である。ｇ＿１は、どの装置がどのような方法で公開してもよいが、安全性の観点から言えば、ｇ＿１はなんらかのデータのハッシュ値であることが望ましい。
【０１５６】
次に、第二発行手段と第二参加手段の各処理を図１８に従って説明する。
【０１５７】
図１８において、ＧＭ装置１００は、Ｚ＿ｑの元ｅ，ｒ”をランダムに選び（ステップＳ１５１、Ｓ１５２）、ｖ＝（ｗｈ＿３＾｛ｒ”｝）＾｛１／（ｇｓｋ＋ｅ）｝を計算する（ステップＳ１５３）。次にＧＭ装置１００は、ｍｐｋ＝（ｖ，ｅ）とする（ステップＳ１５４）。次にＧＭ装置１００は、（ｍｐｋ，ｒ”）をユーザ装置３００に送信する（ステップＳ１５５）。
【０１５８】
次にユーザ装置３００は、（ｍｐｋ，ｒ”）を受信したら（ステップＳ１５６）、ｒ＝ｒ’＋ｒ”ｍｏｄ  ｑとし、ｍｓｋ＝（ｘ，ｒ）とする（ステップＳ１５７、Ｓ１５８）。
【０１５９】
次に、メンバー鍵検証手段の処理を図１８に従って説明する。
【０１６０】
図１８において、ユーザ装置３００は、ｍｐｋを（ｖ，ｅ）とパースする（ステップＳ１５９）。
【０１６１】
ユーザ装置３００は、＜ｗ，ｕ’＿３ｇ’＿３＾｛ｅ｝＞＝＜ｖ，ｇ’＿３＞が成立するかどうかを調べ、＜ｗ，ｕ’＿３ｇ’＿３＾｛ｅ｝＞＝＜ｖ，ｇ’＿３＞が正当ならｍｐｋ＝（ｖ，ｅ）とし、そうでなければ異常終了する（ステップＳ１６０）。
【０１６２】
次に、ＡＰ装置４００のＡＰセットアップ手段４０１の処理を図１１に従って説明する。
【０１６３】
図１１において、ＡＰ装置４００は、ＡＰセットアップ手段４０１の処理を行う前に、各ユーザ装置３００にアクセスを許す上限回数ｋを決めておく必要がある。どのような方法でｋを決めてもよい。
【０１６４】
ＡＰ装置４００は、まずセキュリティ・パラメータω、自分の識別子ＩＤ、および上限値ｋを公開情報記憶部４０３から読み込む（ステップＳ６４）。
【０１６５】
次にＡＰ装置４００は、実施例３のタグ用鍵生成手段の処理（図７）を行い、ＡＰ公開鍵ａｐｋを得る（ステップＳ６５）。最後に、ＡＰ装置４００は、ａｐｋを公開情報記憶部ＡＰ３に書き込む（ステップＳ６６）。
【０１６６】
ユーザ装置３００とＡＰ装置４００は、互いに通信しながら、それぞれグループ証明手段３０２、グループ検証手段４０３の各処理を行う。
【０１６７】
次に、ユーザ装置３００のグループ証明手段３０２とＡＰ装置４００のグループ検証手段３０３を図１３に従って説明する。
【０１６８】
図１３において、まずユーザ装置３００は、（ω，ｇｐｋ，ＩＤ，ｋ，ａｐｋ，ｍｐｋ，ｍｓｋ）を公開情報記憶部３０４から読み込む（ステップＳ９１）。
【０１６９】
ＡＰ装置４００は、（ω，ｇｐｋ，ＩＤ，ｋ，ａｐｋ）を公開情報記憶部４０４から読み込む（ステップＳ１０１）。
【０１７０】
次にＡＰ装置４００は、ランダムにｌを選び（ステップＳ１０２）、ｌをユーザ装置３００に送信する（ステップＳ１０３）。
【０１７１】
次にユーザ装置３００は、ｌを受信したら（ステップＳ９２）、実施例３のタグ生成手段の処理（図７）を行い、知識（τ，μ）を生成する（ステップＳ９３）。
【０１７２】
ｖｅｒ＿｛ｓｐｋ｝（β，Ｓ）を、＜Ｓ，ｈ’＿２ｇ’＿２＾β＞＝＜ｇ＿２，ｇ’＿２＞が成立すれば、ａｃｃｅｐｔを、そうでなければ、ｒｅｊｅｃｔを出力する関数とする。
【０１７３】
次にユーザ装置３００は、知識（τ，μ）の正当性証明文ｐｆ＿｛τ，μ｝を作成し（ステップＳ９４）、（τ，μ，ｐｆ＿｛τ，μ｝）をＡＰ装置４００に送信する（ステップＳ９５）。
【０１７４】
ここで、証明文ｐｆ＿｛τ，μ｝の作成方法を図１９、及び図２０に従って説明する。
【０１７５】
図１９において、まずユーザ装置３００は、Ｚ＿ｑの元βを選び、ｖ＿｛４｝＝ｖ・ｈ＿３＾｛−β｝を計算する（ステップＳ１７１）。
【０１７６】
次にユーザ装置３００は、Ｚ＿ｑの元ｘ＿｛４｝、ｅ＿｛４｝、γ＿｛４｝、β＿｛４｝をランダムに選び、Ｘ＿｛４｝＝＜ｇ＿３＾｛ｘ＿｛４｝｝ｖ＿｛４｝＾｛ｅ＿｛４｝｝ｈ＿３＾｛γ｝，ｇ’＿３＞＜ｈ＿３＾｛β＿｛４｝｝，ｕ’＿３＞を計算する（ステップＳ１７２）。
【０１７７】
次にユーザ装置３００は、Ｚ＿ｑの元ｓをランダムに選び、ｓ’＝（ｘ＋ｉ）ｓ、ｂ＝τ・ｇ＾｛−ｉ｝ａ＿３＾ｓを計算する（ステップＳ１７３）。
【０１７８】
次にユーザ装置３００は、Ｚ＿ｑの元ｉ＿｛４｝、ｓ＿｛４｝、ｓ’＿｛４｝を選び、Ｚ＿ｑの元ｓ’＿｛４｝＝（ｘ＿｛４｝＋ｉ＿｛４｝）ｓ＿｛４｝  ｍｏｄ  ｑ、ｂ＿｛４｝＝ｇ＾｛−ｉ＿｛４｝｝ａ＿３＾｛ｓ＿｛４｝｝、ｈ＿｛４｝＝ｂ＾｛ｘ＿｛４｝＋ｉ＿｛４｝｝ａ＿３＾｛−ｓ’＿｛４｝｝を計算する（ステップＳ１７４）。
【０１７９】
次にユーザ装置３００は、Ｚ＿ｑの元ｔをランダムに選び、ｔ’＝（ｘ＋ｉ）ｔ  ｍｏｄ  ｑ、Ｂ＝μｇ＿１＾｛−ｌｘ｝ｇ＾｛−ｉ｝ａ＿３＾｛ｔ｝を計算する（ステップＳ１７５）。
【０１８０】
次にユーザ装置３００は、Ｚ＿ｑの元ｔ＿｛４｝、ｔ’＿｛４｝を選び、Ｂ＿｛４｝＝ｇ＿１＾｛−ｌ・ｘ＿｛４｝｝ｇ＾｛−ｉ＿｛４｝｝ａ＿３＾｛ｔ＿｛４｝｝、Ｈ＿｛４｝＝Ｂ＾｛−ｘ＿｛４｝−ｉ＿｛４｝｝ａ＿３＾｛−ｔ’＿｛４｝｝を計算する（ステップＳ１７６）。
【０１８１】
次にユーザ装置３００は、Ｚ＿ｑの元ρをランダムに選び、θ＝ρｘ  ｍｏｄ  ｑ、Ｔ＝Ｓｈ＾｛ρ｝を計算する（ステップＳ１７７）。
【０１８２】
図２０において、次にユーザ装置３００は、Ｚ＿ｑの元θ＿｛４｝、ρ＿｛４｝をランダムに選び、Ｙ＿｛４｝＝＜Ｔ，ｈ’＿２＞＜Ｔ，ｇ’＿２＞＾｛ｘ＿｛４｝｝＜ｈ，ｇ’＿２＞＾｛−θ＿｛４｝｝＜ｈ，ｈ’＿２＞＾｛−ρ＿｛４｝｝を計算する（ステップＳ１７８）。
【０１８３】
次にユーザ装置３００は、ｃ＝Ｈａｓｈ＿｛Ｚ＿ｑ｝（ｇｐｋ，ａｐｋ，ｖ＿｛４｝，Ｘ＿｛４｝，ｂ，ｂ＿｛４｝，ｈ＿｛４｝，Ｂ，Ｂ＿｛４｝，Ｈ＿｛４｝，Ｙ＿｛４｝）
を計算する（ステップＳ１７９）。Ｈａｓｈ＿｛Ｚ＿ｑ｝は、Ｚ＿ｑに値をとるハッシュ関数を表す。
【０１８４】
次にユーザ装置３００は、ｘ＿｛５｝＝ｃｘ＋ｘ＿｛４｝  ｍｏｄ  ｑ、ｅ＿｛５｝＝ｃｅ＋ｅ＿｛４｝  ｍｏｄ  ｑ、ｒ＿｛５｝＝ｃ（ｒ＋βｅ）＋γ  ｍｏｄ  ｑ、ｉ＿｛５｝＝ｃｉ＋ｉ＿｛４｝  ｍｏｄ  ｑ、ｓ＿｛５｝＝ｃｓ＋ｓ＿｛４｝  ｍｏｄ  ｑ、ｓ’＿｛５｝＝ｃｓ’＋ｓ’＿｛４｝  ｍｏｄ  ｑ、ｔ＿｛５｝＝ｃｔ＋ｔ＿｛４｝  ｍｏｄ  ｑ、ｔ’＿｛５｝＝ｃｔ’＋ｔ’＿｛４｝  ｍｏｄ  ｑ、ρ＿｛５｝＝ｃρ＋ρ＿｛４｝  ｍｏｄ  ｑ、θ＿｛５｝＝ｃθ＋θ＿｛４｝  ｍｏｄ  ｑを計算する（ステップＳ１８０）。
【０１８５】
最後にユーザ装置３００は、ｐｆ＿｛τ，μ｝＝（ｂ，Ｂ，ｃ，ｘ＿｛５｝，ｅ＿｛５｝，ｒ＿｛５｝，ｉ＿｛５｝，ｓ＿｛５｝，ｓ’＿｛５｝，ｔ＿｛５｝，ｔ’＿｛５｝，ρ＿｛５｝，θ＿｛５｝）とする。
【０１８６】
ここで、図１３に戻り、説明を続ける。
【０１８７】
図１３において、ＡＰ装置４００は、（τ，μ，ｐｆ＿｛τ，μ｝）を受信したら（ステップＳ１０４）、τがすでに履歴記憶部４０４に記載されているかどうかを調べ、記載されていたら、ｒｅｊｅｃｔを出力してグループ検証手段４０３の処理を終了する（ステップＳ１０５）。
【０１８８】
次にＡＰ装置４００は、ｐｆ＿｛τ，μ｝が正当性を検証し、ｐｆ＿｛τ，μ｝が正当でなければ、ｒｅｊｅｃｔを出力してグループ検証手段を終了し（ステップＳ１０６）、ｐｆ＿｛τ，μ｝が正当であれば、（τ，μ，ｌ，ｐｆ＿｛τ，μ｝）を履歴記憶部４０４に記載し、ａｃｃｅｐｔを出力して、グループ検証手段４０３の処理を終了する（ステップＳ１０７）。
【０１８９】
ここで、ｐｆ＿｛τ，μ｝の正当性を検証する方法を図２１に従って説明する。
【０１９０】
図２１において、まずＡＰ装置４００は、Ｘ＿｛４｝＝＜ｇ＿３＾｛ｘ＿｛５｝｝ｖ＿｛４｝＾｛ｅ＿｛５｝｝ｈ＿３＾｛ｒ＿｛５｝｝，ｇ’＿３＞＜ｈ＿３＾｛ｒ＿｛５｝｝，ｕ’＿３＞（＜ａ＿３，ｇ＿３＞／＜ｖ＿｛４｝，ｕ’＿３＞）＾ｃを計算する（ステップＳ１８１）。
【０１９１】
次にＡＰ装置４００は、ｂ＿｛４｝＝（τｂ＾｛−１｝）＾｛−ｃ｝ｇ＾｛−ｉ＿｛５｝｝ａ＿３＾｛ｓ＿｛５｝｝を計算する（ステップＳ１８２）。
【０１９２】
次にＡＰ装置４００は、ｈ＿｛４｝＝ｈ＾｛−ｃ｝ｂ＾｛ｘ＿｛４｝＋ｉ＿｛４｝｝ａ＿３＾｛−ｓ’＿｛５｝｝を計算する（ステップＳ１８３）。
【０１９３】
次にＡＰ装置４００は、Ｂ＿｛４｝＝（Ｂ＾｛−１｝μ）＾｛ｃ｝ｇ＿１＾｛−ｌ・ｘ＿｛５｝｝ｇ＾｛−ｉ＿｛５｝｝ａ＿３＾｛ｔ＿｛５｝｝を計算する（ステップＳ１８４）。
【０１９４】
次にＡＰ装置４００は、Ｈ＿｛４｝＝Ｂ＾｛−ｘ＿｛５｝−ｉ＿｛ｒｅｊ｝｝ａ＿３＾｛−ｔ’＿｛５｝｝を計算する（ステップＳ１８５）。
【０１９５】
次にＡＰ装置４００は、Ｃ＿｛４｝＝Ｃ＾｛−ｃ｝ｇ＾｛ｘ＿｛５｝｝ｈ＾｛ρ＿｛５｝｝を計算する（ステップＳ１８６）。
【０１９６】
次にＡＰ装置４００は、Ｙ＿｛４｝＝＜ｇ＿２，ｇ’＿２＞＾｛−ｃ｝＜Ｔ，ｈ’＿２＞＜Ｔ，ｇ’＿２＞＾｛ｘ＿｛４｝｝＜ｈ，ｇ’＿２＞＾｛−θ＿｛４｝｝＜ｈ，ｈ’＿２＞＾｛−ρ＿｛４｝｝を計算する（ステップＳ１８７）。
【０１９７】
最後にＡＰ装置４００は、ｃ＝Ｈａｓｈ＿｛Ｚ＿ｑ｝（ｇｐｋ，ａｐｋ，ｖ＿｛４｝，Ｘ＿｛４｝，ｂ，ｂ＿｛４｝，ｈ＿｛４｝，Ｂ，Ｂ＿｛４｝，Ｈ＿｛４｝）が成立するかどうかを確認し、ｃ＝Ｈａｓｈ＿｛Ｚ＿ｑ｝（ｇｐｋ，ａｐｋ，ｖ＿｛４｝，Ｘ＿｛４｝，ｂ，ｂ＿｛４｝，ｈ＿｛４｝，Ｂ，Ｂ＿｛４｝，Ｈ＿｛４｝，Ｙ＿｛４｝）が成立していれば、ｐｆ＿｛τ，μ｝をａｃｃｅｐｔし、そうでなければｒｅｊｅｃｔする（ステップＳ１８８）。
【０１９８】
次に、トレース装置５００のトレース手段５０１の処理を図１４、図１５に従って説明する。
【０１９９】
図１４において、まずトレース装置５００は、（ω，ｇｐｋ，ＩＤ，ｋ，ａｐｋ）を公開情報記憶部５０２から読み込む（ステップＳ１１１）。
【０２００】
次にトレース装置５００は、ＡＰ装置４００の履歴記憶部４０４に記憶されているデータ（τ，μ，ｌ，ｐｆ＿｛τ，μ｝）、（τ’，μ’，ｌ’，ｐｆ’＿｛τ’，μ’｝）を受信する（ステップＳ１１２）。このとき、ＡＰ装置４００がいつトレース装置５００に（τ，μ，ｐｆ＿｛τ，μ｝）、（τ’，μ’，ｌ’，ｐｆ’＿｛τ’，μ’｝）を送信するのかは問わない。
【０２０１】
次にトレース装置５００は、τ＝τ’であるかどうかを調べ、τ＝τ’でないなら、「ＡＰ装置４００が不正なデータ（τ，μ，ｌ，ｐｆ＿｛τ，μ｝）、（τ’，μ’，ｌ’，ｐｆ’＿｛τ’，μ’｝）をトレース装置５００に送った」ことを意味する文字列を出力してトレース手段５０１の処理を終了する（ステップＳ１１３）。
【０２０２】
次にトレース装置５００は、ｌ＝ｌ’であるかどうかを調べ、ｌ＝ｌ’でないなら、「ＡＰ装置４が不正なデータ（τ，μ，ｌ，ｐｆ＿｛τ，μ｝）、（τ’，μ’，ｌ’，ｐｆ’＿｛τ’，μ’｝）をトレース装置５００に送った」ことを意味する文字列を出力してトレース手段５０１の処理を終了する（ステップＳ１１４）。
【０２０３】
次にトレース装置５００は、ｐｆ＿｛τ，μ｝が正当であるかどうかを調べ、正当でなければ、「ＡＰ装置４００が不正なデータ（τ，μ，ｌ，ｐｆ＿｛τ，μ｝）、（τ’，μ’，ｌ’，ｐｆ’＿｛τ’，μ’｝）をトレース装置５に送った」ことを意味する文字列を出力してトレース手段５０１の処理を終了する（ステップＳ１１５）。
【０２０４】
次にトレース装置５００は、ｐｆ’＿｛τ’，μ’｝が正当であるかどうかを調べ、正当でなければ、「ＡＰ装置４００が不正なデータ（τ，μ，ｌ，ｐｆ＿｛τ，μ｝）、（τ’，μ’，ｌ’，ｐｆ’＿｛τ’，μ’｝）をトレース装置５００に送った」ことを意味する文字列を出力してトレース手段５０１の処理を終了する（ステップＳ１１６）。
【０２０５】
図１５において、次にトレース装置５００は、実施例３のメンバー特定情報抽出手段の処理（図７）を行い、メンバー特定情報ｔ＿１を得る（ステップＳ１１７）。
【０２０６】
次にトレース装置５００は、ｔ＿１をリスト記憶装置２００に送信する（ステップＳ１１８）。リスト記憶装置２００は、ｔ＿１を受信すると（ステップＳ１２１）、ｔ＿１に対応するＩＤをトレース装置５００に送信する（ステップＳ１２２）。そのようなＩＤがなければ、ＩＤ＝ＧＭとし、ＩＤ＝ＧＭを送信する。
【０２０７】
次にトレース装置５００は、ｔ＿１に対応するＩＤを受け取る（ステップＳ１２２、Ｓ１１９）。最後にトレース装置５００は、ＩＤを出力する（ステップＳ１２０）。
【０２０８】
従って、本実施例でも、前述の実施例３、４と同様に、回数制限匿名認証は既存の方式とは異なり、ユーザが計算すべきデータ個数がＯ（ｌｏｇ  ｋ）個であるため、認証時におけるユーザの計算量は制限回数ｋに比例しないから、効率的な回数制限匿名認証方式を実現することができる。
【実施例６】
【０２０９】
本実施例は、前述した擬似ランダム関数計算装置を用いた回数制限匿名認証システムに適用したものである。
【０２１０】
前述の図１を参照して、本実施例の装置構成を説明する。
【０２１１】
図１に示す本実施例の回数制限匿名認証システムは、前述した実施例３、４のシステムに様々な計算手順を追加して構成されており、機能上、ＧＭ装置１００、リスト記憶装置２００、ユーザ装置３００、ＡＰ装置４００、及びトレース装置５００の５種類の装置を備える。前述した擬似ランダム関数計算装置は、後述するグループ署名手段（グループ証明手段、グループ検証手段）に適用されている。
【０２１２】
このうち、ＧＭ装置１００、リスト記憶装置２００、ユーザ装置３００、およびトレース装置５００の装置構成は、前述した実施例５の装置構成と同じである。ＡＰ装置４００は、前述した実施例５と同様に、グループ検証手段４０２、公開情報記憶部４０３、履歴記憶部４０４、通信手段４０５を備えるが、本実施例では、実施例５とは異なり、ＡＰセットアップ手段４０１が含まれない。従って、本実施例の装置構成は、図１の装置構成からＡＰセットアップ手段４０１を削除したものに対応する。
【０２１３】
上記の各装置１００〜５００は、一例としてコンピュータ機（サーバ機、クライアント機等）のＣＰＵ、記憶装置、ネットワークインターフェース部、その他の各種入出力装置によって実現される。この例では、各手段１０１、１０２、３０１、３０２、５０１は、各コンピュータ機のＣＰＵが記憶装置上のコンピュータプログラムの命令を実行することにより実現される。ここで用いられるコンピュータプログラムは、これら各手段の処理アルゴリズム（後述参照）に応じて予め設定される。また、公開情報記憶部１０４、３０４、４０３、５０２、秘密情報記憶部１０３、３０３、リスト記憶部２０１、履歴記憶部４０４は、各コンピュータ機の記憶装置により実装される。通信手段１０５、２０２、３０５、４０５、５０３は、各コンピュータ機のネットワークインターフェース部に対応する。
【０２１４】
図１では、もっとも単純な場合として５種類の装置がそれぞれ一台ずつしかない場合を描いているが、各種類の装置が複数台あってもかまわない。また、図１では、各装置が別々の機械である場合を描いているが、一つの機械が二種類の装置の機能を兼ねていてもかまわない。例えば、ＧＭ装置１００の機能とリスト装置２００の機能を両方持つ機械を使ってもかまわない。
【０２１５】
ＧＭ装置１００、リスト記憶装置２００、ユーザ装置３００、ＡＰ装置４００、トレース装置５００は、それぞれ通信手段１０５、２０２、３０５、４０５、５０３を使って相互に通信できる。通信媒体として、例えばインターネット、電波、電話回線といったものを用いることができるが、どのような通信媒体を用いてもかまわない。
【０２１６】
ＧＭ装置１００、ユーザ装置３００、ＡＰ装置４００、トレース装置５００は、それぞれの公開情報記憶部１０４、３０４、４０３、５０２に、自分自身や他の装置が公開している公開情報を記憶する。また、リスト記憶装置２００は、リスト記憶部２０１という、公開情報を記憶するための部分を持っている。リスト記憶装置２００は、自分自身や他の装置が公開している公開情報をリスト記憶部２０１に記憶する。
【０２１７】
各装置１００〜５００は、他の装置が公開している公開情報をなんらかの方法で入手できるものとする。公開情報の入手手段としては例えば、公開情報を公開している装置から前述の通信手段を用いて直接受け取る方法、公開情報のリストを持っているサーバから前述の通信手段を用いて受け取る方法、といったものが考えられるが、どのような方法を用いてもかまわない。
【０２１８】
ＧＭ装置１００とユーザ装置３００は、それぞれ秘密情報記憶部１０３、３０３にそれぞれの秘密情報を記憶する。
【０２１９】
各装置１００〜３００には、事前にセキュリティ・パラメータωが配布されている。セキュリティ・パラメータωをどのような方法で配布するのか、セキュリティ・パラメータωをどのような方法で決定するのかは問わない。
【０２２０】
ユーザ装置３００とＡＰ装置４００には、事前に固有のＩＤが割り振られており、各装置１００〜５００は、全てのユーザ装置３００、ＡＰ装置４００のＩＤを事前に知っている。ＩＤとしてどのようなデータを用いるのか、ＩＤをどのように配布するのかは問わない。例えば、装置保有者の名前、装置に割り振られたＩＰアドレス、装置に割り振られたＭＡＣアドレス、および乱数といったものを装置のＩＤとして用いることができる。
【０２２１】
グループ証明手段３０２、グループ検証手段４０２、トレース手段５０１以外の、実施例６の各手段は、実施例５のそれと同じである。
【０２２２】
次に、本実施例の動作を図１３、図２２〜図２４を参照して説明する。図１３、図２２〜図２４に示す処理手順は、各装置に対応するコンピュータ機の記憶装置上に格納されるコンピュータプログラムとして実現され、各コンピュータ機のＣＰＵにより実行される。
【０２２３】
まず、グループ証明手段３０２とグループ検証手段４０２の各処理を図１３に従って説明する。
【０２２４】
図１３のステップＳ９３、Ｓ９４以外の処理は、前述した実施例５のグループ証明手段３０２と同じである。図１３のステップＳ１０４以外の処理は、前述した実施例５のグループ検証手段４０２と同じである。
【０２２５】
グループ証明手段３０２は、ステップＳ９３にて、実施例３ではなく実施例４のタグ生成手段の処理（図１０）を行い、ステップＳ１０４にて、図１９、図２０の代わりに図２２、図２３に従って、証明文ｐｆ＿｛τ，μ｝を作成する。
【０２２６】
図２２及び図２３を参照して、証明文ｐｆ＿｛τ，μ｝の作成方法を説明する。
【０２２７】
図２２において、まずユーザ装置３００は、Ｚ＿ｑの元βを選び、ｖ＿｛４｝＝ｖ・ｈ＿３＾｛−β｝を計算する（ステップＳ１９１）。
【０２２８】
次にユーザ装置３００は、Ｚ＿ｑの元ｘ＿｛４｝、ｅ＿｛４｝、γ＿｛４｝、β＿｛４｝をランダムに選び、Ｘ＿｛４｝＝＜ｇ＿３＾｛ｘ＿｛４｝｝ｖ＿｛４｝＾｛ｅ＿｛４｝｝ｈ＿３＾｛γ｝，ｇ’＿３＞＜ｈ＿３＾｛β＿｛４｝｝，ｕ’＿３＞を計算する（ステップＳ１９２）。
【０２２９】
次にユーザ装置３００は、Ｚ＿ｑの元ｓをランダムに選び、ｓ’＝（ｘ＋ｉ）ｓ、ｂ＝τ・ｇ＾｛−ｉ｝ａ＿３＾ｓを計算する（ステップＳ１９３）。
【０２３０】
次にユーザ装置３００は、Ｚ＿ｑの元ｉ＿｛４｝、ｓ＿｛４｝、ｓ’＿｛４｝を選び、Ｚ＿ｑの元ｓ’＿｛４｝＝（ｘ＿｛４｝＋ｉ＿｛４｝）ｓ＿｛４｝  ｍｏｄ  ｑ、ｂ＿｛４｝＝ｇ＾｛−ｉ＿｛４｝｝ａ＿３＾｛ｓ＿｛４｝｝、ｈ＿｛４｝＝ｂ＾｛ｘ＿｛４｝＋ｉ＿｛４｝｝ａ＿３＾｛−ｓ’＿｛４｝｝を計算する（ステップＳ１９４）。
【０２３１】
次にユーザ装置３００は、Ｚ＿ｑの元ｔをランダムに選び、ｔ’＝（ｘ＋ｉ）ｔ  ｍｏｄ  ｑ  、Ｂ＝μｇ＿１＾｛−ｌｘ｝ｇ＾｛−ｉ｝ａ＿３＾｛ｔ｝を計算する（ステップＳ１９５）。
【０２３２】
次にユーザ装置３００は、Ｚ＿ｑの元ｔ＿｛４｝、ｔ’＿｛４｝を選び、Ｂ＿｛４｝＝ｇ＿１＾｛−ｌ・ｘ＿｛４｝｝ｇ＾｛−ｉ＿｛４｝｝ａ＿３＾｛ｔ＿｛４｝｝、Ｈ＿｛４｝＝Ｂ＾｛−ｘ＿｛４｝−ｉ＿｛４｝｝ａ＿３＾｛−ｔ’＿｛４｝｝
を計算する（ステップＳ１９６）。
【０２３３】
次にユーザ装置３００は、ｌｏｇ＿２  ｋ以上の整数で最も小さい整数をＮとする（ステップＳ１９７）。
【０２３４】
図２３において、次にユーザ装置３００は、整数ｉ＝０，．．，Ｎに対し、ｘの第ｉビットをｘ＿ｉとし、ｘ’＿ｉ＝１−ｘ＿ｉとし、ｚ＝ｋ−ｘとし、ｚの第ｉビットをｚ＿ｉとし、ｚ’＿ｉ＝１−ｚ＿ｉとする（ステップＳ１９８）。
【０２３５】
次にユーザ装置３００は、Ｚ＿ｑのρ＿１，…，ρ＿Ｎ、θ＿１，…，θ＿Ｎで、ρ＿１＋…＋ρ＿Ｎ＝θ＿１＋…＋θ＿Ｎが成立するものを選び、ρ＝ρ＿１＋…＋ρ＿Ｎ、Ｃ＿１＝ｈ＾｛ρ＿１｝，…，Ｃ＿Ｎ＝ｈ＾｛ρ＿Ｎ｝、Ｄ＿１＝ｈ＾｛θ＿１｝，…，Ｄ＿Ｎ＝ｈ＾｛θ＿Ｎ｝、Ｃ＝ｇ＾｛ｘ｝ｈ＾｛ρ｝、Ｄ＝ｇ＾｛ｋ−ｘ｝ｈ＾｛ρ｝を計算する（ステップＳ１９９）。
【０２３６】
次にユーザ装置３００は、ｉ＝１，…，Ｎ，ｊ＝０，１に対し、Ｚ＿ｑの元ρ＿｛４，ｉ｝，θ＿｛４，ｉ｝，ｃ’＿｛ｉ，ｘ’＿ｉ｝，ｄ’＿｛ｉ，ｚ’＿ｉ｝，ρ＿｛５，ｉ，ｘ’＿ｉ｝，θ＿｛５，ｉ，ｚ’＿ｉ｝をランダムに選び、Ｃ＿｛４，ｉ，ｘ＿ｉ｝＝ｇ＾｛ｘ＿ｉ｝ｈ＾｛ρ＿｛４，ｉ｝｝、Ｄ＿｛４，ｉ，ｘ＿ｉ｝＝ｇ＾｛ｚ＿ｉ｝ｈ＾｛θ＿｛４，ｉ｝｝、Ｃ＿｛４，ｉ，ｘ’＿ｉ｝＝Ｃ＾｛−ｃ’＿｛ｉ，ｘ’＿ｉ｝｝ｇ＾｛ｘ’＿ｉ｝ｈ＾｛ρ＿｛５，ｉ，ｘ’＿ｉ｝｝、Ｄ＿｛４，ｉ，ｘ’＿ｉ｝＝Ｄ＾｛−ｄ’＿｛ｉ，ｚ’＿ｉ｝｝ｇ＾｛ｚ’＿ｉ｝ｈ＾｛θ＿｛５，ｉ，ｚ’＿ｉ｝｝
を計算する（ステップＳ２００）。
【０２３７】
次にユーザ装置３００は、ｃ＝Ｈａｓｈ＿｛Ｚ＿ｑ｝（ｇｐｋ，ａｐｋ，ｖ＿｛４｝，Ｘ＿｛４｝，ｂ，ｂ＿｛４｝，ｈ＿｛４｝，Ｂ，Ｂ＿｛４｝，Ｈ＿｛４｝，Ｃ＿｛４｝，｛Ｃ＿｛４，ｉ，ｊ｝｝＿｛ｉ＝１，…，Ｎ，ｊ＝０，１｝，｛Ｄ＿｛４，ｉ，ｊ｝｝＿｛ｉ＝１，…，Ｎ，ｊ＝０，１｝）を計算する（ステップＳ２０１）。Ｈａｓｈ＿｛Ｚ＿ｑ｝は、Ｚ＿ｑに値をとるハッシュ関数を表す。
【０２３８】
次にユーザ装置３００は、ｘ＿｛５｝＝ｃｘ＋ｘ＿｛４｝  ｍｏｄ  ｑ、ｅ＿｛５｝＝ｃｅ＋ｅ＿｛４｝  ｍｏｄ  ｑ、ｒ＿｛５｝＝ｃ（ｒ＋βｅ）＋γ  ｍｏｄ  ｑ、ｉ＿｛５｝＝ｃｉ＋ｉ＿｛４｝  ｍｏｄ  ｑ、ｓ＿｛５｝＝ｃｓ＋ｓ＿｛４｝  ｍｏｄ  ｑ、ｓ’＿｛５｝＝ｃｓ’＋ｓ’＿｛４｝  ｍｏｄ  ｑ、ｔ＿｛５｝＝ｃｔ＋ｔ＿｛４｝  ｍｏｄ  ｑ、ｔ’＿｛５｝＝ｃｔ’＋ｔ’＿｛４｝  ｍｏｄ  ｑ、ｃ＿ｉ＝ｃ−ｃ’＿ｉ  ｍｏｄ  ｑ、ｄ＿ｉ＝ｄ−ｄ’＿ｉ  ｍｏｄ  ｑ、ρ＿｛５，ｉ，ｘ＿ｉ｝＝ｃ＿ｉρ＿ｉ＋ρ＿｛４，ｉ｝  ｍｏｄ  ｑ、θ＿｛５，ｉ，ｘ＿ｉ｝＝ｃ＿ｉθ＿ｉ＋θ＿｛４，ｉ｝  ｍｏｄ  ｑを計算する（ステップＳ２０２）。
【０２３９】
最後にユーザ装置３は、ｐｆ＿｛τ，μ｝＝（ｂ，Ｂ，Ｃ，ｃ，ｘ＿｛５｝，ｅ＿｛５｝，ｒ＿｛５｝，ｉ＿｛５｝，ｓ＿｛５｝，ｓ’＿｛５｝，ｔ＿｛５｝，ｔ’＿｛５｝，｛ｃ＿｛ｉｊ｝｝）とする（ステップＳ２０３）。
【０２４０】
図１３において、ＡＰ装置４００は、（τ，μ，ｐｆ＿｛τ，μ｝）を受信したら（ステップＳ１０４）、τがすでに履歴記憶部ＢＡＰ４に記載されているかどうかを調べ、記載されていたらｒｅｊｅｃｔを出力してグループ検証手段４０２の処理を終了する（ステップＳ１０５）。
【０２４１】
次にＡＰ装置４００は、ｐｆ＿｛τ，μ｝が正当性を検証し、ｐｆ＿｛τ，μ｝が不当なら、ｒｅｊｅｃｔを出力してグループ検証手段４０２の処理を終了し（ステップＳ１０６）、ｐｆ＿｛τ，μ｝が正当なら、ＡＰ装置４００は、（τ，μ，ｌ，ｐｆ＿｛τ，μ｝）を履歴記憶部４０４に記載し、ａｃｃｅｐｔを出力してグループ検証手段４０２の処理を終了する（ステップＳ１０７）。
【０２４２】
次に、ｐｆ＿｛τ，μ｝の正当性を検証する方法を図２４に従って説明する。
【０２４３】
図２４において、まずＡＰ装置４００は、Ｘ＿｛４｝＝＜ｇ＿３＾｛ｘ＿｛５｝｝ｖ＿｛４｝＾｛ｅ＿｛５｝｝ｈ＿３＾｛ｒ＿｛５｝｝，ｇ’＿３＞＜ｈ＿３＾｛ｒ＿｛５｝｝，ｕ’＿３＞（＜ａ＿３，ｇ＿３＞／＜ｖ＿｛４｝，ｕ’＿３＞）＾ｃを計算する（ステップＳ２１１）。
【０２４４】
次にＡＰ装置４００は、ｂ＿｛４｝＝（τｂ＾｛−１｝）＾｛−ｃ｝ｇ＾｛−ｉ＿｛５｝｝ａ＿３＾｛ｓ＿｛５｝｝を計算する（ステップＳ２１２）。
【０２４５】
次にＡＰ装置４００は、ｈ＿｛４｝＝ｈ＾｛−ｃ｝ｂ＾｛ｘ＿｛４｝＋ｉ＿｛４｝｝ａ＿３＾｛−ｓ’＿｛５｝｝を計算する（ステップＳ２１３）。
【０２４６】
次にＡＰ装置４００は、Ｂ＿｛４｝＝（Ｂ＾｛−１｝μ）＾｛ｃ｝ｇ＿１＾｛−ｌ・ｘ＿｛５｝｝ｇ＾｛−ｉ＿｛５｝｝ａ＿３＾｛ｔ＿｛５｝｝を計算する（ステップＳ２１４）。
【０２４７】
次にＡＰ装置４００は、Ｈ＿｛４｝＝Ｂ＾｛−ｘ＿｛５｝−ｉ＿｛ｒｅｊ｝｝ａ＿３＾｛−ｔ’＿｛５｝｝を計算する（ステップＳ２１５）。
【０２４８】
次にＡＰ装置４００は、Ｃ＿｛４｝＝Ｃ＾｛−ｃ｝ｇ＾｛ｘ＿｛５｝｝ｈ＾｛ρ＿｛５｝｝を計算する（ステップＳ２１６）。
【０２４９】
次にＡＰ装置４００は、ｉ＝１，．．，Ｎ、ｊ＝０，１に対し、Ｃ＿｛４，ｉ，ｊ｝＝     Ｃ＿｛−ｃ＿｛ｉｊ｝｝ｇ＾｛ｊ｝ｈ＾｛ρ＿｛５，ｉｊ｝｝、Ｄ＿｛４，ｉ，ｊ｝＝Ｄ＿｛−ｃ＿｛ｉｊ｝｝ｇ＾｛ｊ｝ｈ＾｛θ＿｛５，ｉｊ｝｝を計算する（ステップＳ２１７）。
【０２５０】
最後にＡＰ装置４００は、ｃ＝Ｈａｓｈ＿｛Ｚ＿ｑ｝（ｇｐｋ，ａｐｋ，ｖ＿｛４｝，Ｘ＿｛４｝，ｂ，ｂ＿｛４｝，ｈ＿｛４｝，Ｂ，Ｂ＿｛４｝，Ｈ＿｛４｝，｛Ｃ＿｛ｉｊ｝｝＿｛ｉ＝１，…，Ｎ，ｊ＝０，１｝，｛Ｄ＿｛ｉｊ｝｝＿｛ｉ＝１，…，Ｎ，ｊ＝０，１｝）と、ｃ＝ｃ＿１＋ｃ’＿１＝…＝ｃ＿Ｎ＋ｃ’＿Ｎ  ｍｏｄ  ｑが成立するかどうかを確認し、ともに成立していれば、ｐｆ＿｛τ，μ｝をａｃｃｅｐｔし、そうでなければｒｅｊｅｃｔする（ステップＳ２１８）。
【０２５１】
従って、本実施例でも、前述の実施例３〜５と同様に、回数制限匿名認証は既存の方式とは異なり、ユーザが計算すべきデータ個数がＯ（ｌｏｇ  ｋ）個であるため、認証時におけるユーザの計算量は制限回数ｋに比例しないから、効率的な回数制限匿名認証方式を実現することができる。
【図面の簡単な説明】
【０２５２】
【図１】本発明の実施例５、６による回数制限匿名認証システムの全体構成を示す図である。
【図２】本発明の実施例１による擬似ランダム関数計算装置の全体構成を示す図である。
【図３】図２に示す擬似ランダム関数用鍵生成手段と擬似ランダム関数計算手段の処理手順を説明する概略フローチャートである（実施例１）。
【図４】本発明の実施例２による擬似ランダム関数計算装置の全体構成を示す図である。
【図５】図４に示す擬似ランダム関数用鍵生成手段と擬似ランダム関数計算手段の処理手順を説明する概略フローチャートである（実施例２）。
【図６】本発明の実施例３による回数制限匿名認証システムの全体構成を示す図である。
【図７】図６に示す回数制限匿名認証システムの各手段の処理手順を説明する概略フローチャートである（実施例３）。
【図８】図７に示すタグ用鍵生成手段で用いる電子署名用鍵生成手段と電子署名手段の処理手順を説明する概略フローチャートである（実施例３）。
【図９】本発明の実施例４による回数制限匿名認証システムの全体構成を示す図である。
【図１０】図９に示すタグ計算手段の処理手順を説明する概略フローチャートである（実施例４）。
【図１１】図１に示すＧＭセットアップ手段とＡＰセットアップ手段の処理手順を説明する概略フローチャートである（実施例５）。
【図１２】図１に示す発行手段と参加手段の処理手順を説明する概略フローチャートである（実施例５）。
【図１３】図１に示すグループ証明手段とグループ検証手段の処理手順を説明する概略フローチャートである（実施例５）。
【図１４】図１に示すトレース手段の処理手順を説明する概略フローチャートである（実施例５）。
【図１５】図１に示すトレース手段とリスト記憶部の処理手順を説明する概略フローチャートである（実施例５）。
【図１６】図１に示すＧＭセットアップ手段で用いる発行者用鍵生成手段の処理手順を説明する概略フローチャートである（実施例５）。
【図１７】図１に示す発行手段及び参加手段で用いる第一発行手段及び第一参加手段の処理手順を説明する概略フローチャートである（実施例５）。
【図１８】図１に示す発行手段及び参加手段で用いる第二発行手段、第二参加手段、及びファイ計算手段の処理手順を説明する概略フローチャートである（実施例５）。
【図１９】図１に示すユーザ装置による証明文の作成方法の処理手順を説明する概略フローチャートである（実施例５）。
【図２０】図１に示すユーザ装置による証明文の作成方法の処理手順を説明する概略フローチャートである（実施例５）。
【図２１】図１に示すＡＰ装置による証明文の正当性検証方法の処理手順を説明する概略フローチャートである（実施例５）。
【図２２】図１に示すユーザ装置による証明文の作成方法の処理手順を説明する概略フローチャートである（実施例６）。
【図２３】図１に示すユーザ装置による証明文の作成方法の処理手順を説明する概略フローチャートである（実施例６）。
【図２４】図１に示すＡＰ装置による証明文の正当性検証方法の処理手順を説明する概略フローチャートである（実施例６）。
【符号の説明】
【０２５３】
１  擬似ランダム関数計算装置
２  擬似ランダム関数用鍵生成手段
３  秘密鍵記憶部
４  公開鍵記憶部
５  入力手段
６  擬似ランダム関数計算手段
７  出力手段
１０  メンバー特定情報生成装置
１１  秘密鍵生成手段
１２  公開情報記憶部
１３  メンバー特定情報生成手段
１４  通信装置
１５  書き込み手段
２０  乱数生成装置
２１  公開情報記憶部
２２  乱数選択手段
２３  通信手段
３０  タグ生成装置
３１  公開情報記憶部
３２  タグ生成手段
３３  入力手段
３４  通信装置
３５  タグ計算手段
４０  メンバー特定情報抽出装置
４１  公開情報記憶部
４２  メンバー特定情報抽出手段
４３  一致性判定手段
４４  出力手段
４５  通信装置
５０  鍵生成装置
５１  入力手段
５２  公開情報記憶部
５３  タグ用鍵生成手段
５４  通信手段
１００  ＧＭ装置
１０１  ＧＭセットアップ手段
１０２  発行手段
１０３  秘密情報記憶部
１０４  公開情報記憶部
１０５  通信手段
２００  リスト記憶装置
２０１  リスト記憶部
２０２  通信手段
３００  ユーザ装置
３０１  参加手段
３０２  グループ証明手段
３０３  秘密情報記憶部
３０４  公開情報記憶部
３０５  通信手段
４００  ＡＰ装置
４０１  ＡＰセットアップ手段
４０２  グループ検証手段
４０３  公開情報記憶部
４０４  履歴記憶部
４０５  通信手段
５００  トレース装置
５０１  トレース手段
５０２  公開情報記憶部
５０３  通信手段
【図１】
2006330462.tif 000003
【図２】
2006330462.tif 000004
【図３】
2006330462.tif 000005
【図４】
2006330462.tif 000006
【図５】
2006330462.tif 000007
【図６】
2006330462.tif 000008
【図７】
2006330462.tif 000009
【図８】
2006330462.tif 000010
【図９】
2006330462.tif 000011
【図１０】
2006330462.tif 000012
【図１１】
2006330462.tif 000013
【図１２】
2006330462.tif 000014
【図１３】
2006330462.tif 000015
【図１４】
2006330462.tif 000016
【図１５】
2006330462.tif 000017
【図１６】
2006330462.tif 000018
【図１７】
2006330462.tif 000019
【図１８】
2006330462.tif 000020
【図１９】
2006330462.tif 000021
【図２０】
2006330462.tif 000022
【図２１】
2006330462.tif 000023
【図２２】
2006330462.tif 000024
【図２３】
2006330462.tif 000025
【図２４】
2006330462.tif 000026