(57)【要約】【課題】順次更新される更新情報から所定の識別子を抽出する処理に用いられる事前計算テーブルを作成する際の演算量を低減する。【解決手段】まず、識別子ｉと順次更新される補助更新情報Ｓｉとを対応付けた補助テーブル２００を補助テーブルメモリ１０２に格納し、複数のスタートポイント情報（ｉｋ，ｊｋ）２１０をスタートポイントメモリ１０４に格納し、スタートポイント情報の複製を初期値とする複数のエンドポイント情報（ｉｋ’，ｊｋ’）２２０をエンドポイントメモリ１０６に格納する。そして、エンドポイント情報２２０のｉｋ’と一致する識別子ｉに対応付けられている補助更新情報Ｓｉを用い、ｊｋ’回更新された更新情報Ｆｔ（ｉ’，ｊ’）を生成し、これにリダクション関数をＲt（ｒ）を作用させた結果 (ik’’,jk’’)を新たなエンドポイント情報（ｉｋ’，ｊｋ’）２２０とする処理を繰り返す。【選択図】図２
2007141004.tif 000002
【特許請求の範囲】
【請求項１】
順次更新される更新情報から所定の識別子を抽出する処理に用いられる事前計算テーブルを作成するテーブル作成装置であって、
識別子と、更新関数を順次作用させることにより更新される補助更新情報と、を対応付けた補助テーブルを格納する補助テーブルメモリと、
第１値と第２値とを対応付けた複数のスタートポイント情報を格納するスタートポイントメモリと、
上記スタートポイント情報の複製を初期値とする複数のエンドポイント情報を格納するエンドポイントメモリと、
上記エンドポイント情報が具備する上記第１値と一致する識別子に対応付けられている上記補助更新情報を用い、当該第１値に対応する第２値が示す数だけ更新された更新情報を生成する第１演算部と、
１つの入力値に対して第１出力値と第２出力値との組を出力するリダクション関数を、上記第１演算部で生成された更新情報に作用させ、第１出力値と第２出力値との組を生成する第２演算部と、
上記第２演算部で生成された上記第１出力値及び第２出力値を、それぞれ新たな第１値及び第２値として上記エンドポイントメモリの上記エンドポイント情報を更新するエンドポイント更新部と、
複数の上記スタートポイント情報に対し、上記第１演算部と、上記第２演算部と、上記エンドポイント更新部との処理を繰り返し実行させる制御部と、
を有することを特徴とするテーブル作成装置。
【請求項２】
請求項１に記載のテーブル作成装置であって、
上記リダクション関数から出力される第２出力値の値域は、更新情報の更新回数の最大値から１を減じた値と０との間の一部の範囲に限定される、
ことを特徴とするテーブル作成装置。
【請求項３】
請求項２に記載のテーブル作成装置であって、
上記補助テーブルにおいて各識別子に対応付けられる上記補助更新情報の個数は、それぞれ、上記更新情報の更新回数の最大値未満である、
ことを特徴とするテーブル作成装置。
【請求項４】
請求項３に記載のテーブル作成装置であって、
上記補助テーブルにおいて各識別子に対応付けられる上記補助更新情報の個数は、それぞれ、更新することなく上記リダクション関数から出力され得る第２出力値の要素数と同一である、
ことを特徴とするテーブル作成装置。
【請求項５】
請求項３に記載のテーブル作成装置であって、
上記第１演算部は、
上記エンドポイント情報が具備する上記第１値に一致する識別子に対応付けられている上記補助更新情報に上記更新関数を作用させて、当該第１値に対応する第２値が示す数だけ更新された更新情報を生成する、
ことを特徴とするテーブル作成装置。
【請求項６】
請求項３に記載のテーブル作成装置であって、
上記補助テーブルは、
各識別子に対し、更新回数が上記エンドポイント情報の上記第２値と一致し得る上記補助更新情報のみをそれぞれ対応付けたテーブルである、
ことを特徴とするテーブル作成装置。
【請求項７】
請求項２に記載のテーブル作成装置であって、
上記エンドポイント更新部による上記エンドポイントの更新後、上記補助テーブルメモリに格納された補助更新情報を更新する補助更新情報更新部を有し、
上記リダクション関数から出力される第２出力値の値域は、
上記エンドポイント更新部による上記エンドポイント情報の更新に伴って変化する、
ことを特徴とするテーブル作成装置。
【請求項８】
請求項７に記載のテーブル作成装置であって、
上記補助更新情報更新部は、
上記補助テーブルメモリに格納された補助更新情報に新たな補助更新情報を上書きして、補助更新情報の更新を行う、
ことを特徴とするテーブル作成装置。
【請求項９】
順次更新される更新情報から所定の識別子を抽出する処理に用いられる事前計算テーブルを作成するテーブル作成方法であって、
識別子と、更新関数を順次作用させることにより更新される補助更新情報と、を対応付けた補助テーブルが補助テーブルメモリに格納され、
第１値と第２値とを対応付けた複数のスタートポイント情報がスタートポイントメモリに格納され、
上記スタートポイント情報の複製を初期値とする複数のエンドポイント情報がエンドポイントメモリに格納されたことを前提に、
第１演算部が、上記エンドポイント情報が具備する上記第１値と一致する識別子に対応付けられている上記補助更新情報を用い、当該第１値に対応する第２値が示す数だけ更新された更新情報を生成するステップと、
第２演算部が、１つの入力値に対して第１出力値と第２出力値との組を出力するリダクション関数を、上記第１演算部で生成された更新情報に作用させ、第１出力値と第２出力値との組を生成するステップと、
エンドポイント更新部が、上記第２演算部で生成された上記第１出力値及び第２出力値を、それぞれ新たな第１値及び第２値として上記エンドポイントメモリの上記エンドポイント情報を更新するステップとを、
複数の上記スタートポイント情報に対し、それぞれ繰り返し実行する、
ことを特徴とするテーブル作成方法。
【請求項１０】
請求項１から８の何れかに記載のテーブル作成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、順次更新される更新情報から所定の識別子を抽出する処理に用いられる事前計算テーブルを作成する技術に関する。
【背景技術】
【０００２】
物品や人に識別子〔例えば、商品シリアルナンバーやＩＳＢＮ（International Standard Book Number），バーコード，パスポート番号等〕を割り当てる場合、基本的に１つの物品や人、或いは１つのカテゴリに対して一意となる識別子がただ１つ与えられる。また、ＩＳＢＮ，バーコード等は、一般にその番号体系が公開されており、識別子をみれば如何なる商品であるかが誰にでも特定できる。また、従来のバーコードや商品シリアルナンバー等の識別子は物品或いはタグ等に印刷されて提供されており、その識別子を認識できるのは識別子を目視できる者に限られていた。
【０００３】
これに対し、近年、印刷の代わりにＲＦ（Radio Frequency）タグを用いて物品に識別子を付する研究がさかんに行われている（例えば、非特許文献１参照）。一般に、ＲＦタグとは、アンテナとＩＣチップ等から構成される微小な装置であり、外部の無線装置（ＲＦＩＤリーダ）と無線通信で情報のやり取りを行うことができるものである。無線装置は、無線が到達できる範囲内にＲＦタグが存在する限り、当該ＲＦタグ内に格納されたバーコードや商品シリアルナンバー等を一度に大量に取得することができるため、ＲＦタグを物品に添付或いは物品内に格納しておけば、このＲＦタグを物品の流通や在庫の管理等に活用することができる。また、ＲＦＩＤを用いた入退室管理システムや、高級ブランド品や紙幣或いはイベントや施設の入場券等にＲＦＩＤタグを用いる応用など、ＲＦＩＤを用いた認証や真贋判定の研究もさかんに行われている。
【０００４】
しかし、一般に、ＲＦＩＤを使って物品を管理する場合、ＲＦタグの機能を明示的に停止させない限り、「最終消費者等が如何なる物品を所持しているか」「物品の現在位置（或いは所有者の現在位置）はどこか」「その他ＲＦタグが提供する情報（気温，湿度等）」等のプライバシ情報が外部の無線装置によって不正に取得されてしまう可能性がある。すなわち、ＲＦタグを用いて物品管理を行った場合、物品の所有者が気付かぬうちにプライバシ情報が任意の第三者に取得されてしまい、結果的に物品の所持者が無意識のうちに何らかの監視を受けていることとなってしまう。
【０００５】
また、ＲＦＩＤを用いて認証や真贋判定を行う場合は、ＲＦＩＤタグはＲＦＩＤリーダからの要求に従って誰にでも識別できるＩＤを出力するので、特に無意識の監視を受ける可能性が大きい。そのため、ＲＦＩＤを用いた認証や真贋判定とプライバシ保護を両立させることはＲＦＩＤの分野で大きな課題となっていた。
このようなＲＦＩＤのプライバシ保護の問題に対し、大久保らは、以下の方法を提案した（例えば、非特許文献２参照）。
大久保らの方法
準備：ｈ（ｘ），ｇ（ｘ）を互いに相関のない２つの暗号学的ハッシュ（Hash）関数とする。
【０００６】
タグ初期設定：タグｉのメモリ領域ｓに乱数ｓｉを記録する。ｉ，ｓｉの組は鍵となる情報である。
タグの処理：タグｉはＩＤが要求されたらｇ（ｓｉ）を出力し、メモリ領域ｓにｈ（ｓｉ）を上書き保存する。
サーバの初期設定：サーバは、ｉ，ｓｉの対応表から、あり得るタグの出力ｇ（ｈｊ（ｓｉ））を予め計算し、ｇ（ｈｊ（ｓｉ））とｉとの対応表を作る。
サーバ装置の処理：タグから与えられたｇ（ｓｉ）を検索キーとしてｇ（ｈｊ（ｓｉ））とｉとの対応表を検索し、ｇ（ｓｉ）に対応するｉを出力する。
【０００７】
このようなｈ（ｘ）を一方向性関数、ｇ（ｘ）をランダムオラクルとする大久保らの方法は上記のプライバシの問題を解決する。すなわち、タグはｇ（ｓｉ）を出力するたびにメモリ領域ｓの値ｓｉを更新するため、第三者からみると、タグが各時点において出力するｇ（ｓｉ）は相互にランダムな関係にみえる。その結果、第三者はタグが出力した情報から上記のプライバシ情報を取得することが困難となる。
しかし、この方法は、ｇ（ｈｊ（ｓｉ））とｉとの対応表が大きいという問題点があった。これに対し、Avoineらは、従来、暗号の攻撃に用いられていたタイムメモリトレードオフ（Time-Memory Trade-off）法をこの問題に適用することを提案した（例えば、非特許文献３参照）。
【０００８】
Avoineらの方法
サーバ初期設定：
０≦ｉ≦ｎ，０≦ｊ≦ｍとし、Ｆ（ｉ，ｊ）＝ｇ（ｈｊ（ｓｉ））とし、ｆ（ｉ，ｊ）＝Ｒ（Ｆ（ｉ，ｊ））とする。なお、ｎはタグ数を示し、ｍは最大チェーン数（タグから出力される情報の最大更新回数）を示す。また、Ｒ（ｒ）は、定義域を一次元とし、値域を二次元とする関数であり、例えば、
【０００９】
【数１】
2007141004.tif 000003
まず、０≦ｋ≦Ｋに関してランダムに、スタートポイント情報（ｉｋ，ｊｋ）∈［０，ｎ−１］×［０，ｍ−１］を選ぶ。次に、Ｌを十分大きな値として、エンドポイント情報（ｉｋ’，ｊｋ’）＝ｆＬ（ｉｋ，ｊｋ）を計算し、スタートポイント情報（ｉｋ，ｊｋ）とエンドポイント情報（ｉｋ’，ｊｋ’）との対応表である事前計算テーブルを作る。
【００１０】
サーバの処理：
Ｓｔｅｐ ０：ｔ＝０とする。
Ｓｔｅｐ １：タグから与えられたｒより、（ｉ’’，ｊ’’）＝Ｒ（ｒ）を計算する。
Ｓｔｅｐ ２：（ｉ’’，ｊ’’）と一致する（ｉｋ’，ｊｋ’）を、上述の事前計算テーブルから検索する。
Ｓｔｅｐ ３：（ｉ’’，ｊ’’）と一致する（ｉｋ’，ｊｋ’）が見つかった場合、一致する（ｉｋ’，ｊｋ’）に対応する（ｉｋ，ｊｋ）より、
ｒ’＝Ｆ（ｆ（Ｌ−ｔ−１）（ｉｋ，ｊｋ））
を計算し、ｒ’＝ｒならば、ｉｋを出力する。
Ｓｔｅｐ ４：ｔ＝ｔ＋１とする。
Ｓｔｅｐ ５：もしｔ＝ＬならＩＤ解決失敗として終了。
Ｓｔｅｐ ６：（ｉ’’，ｊ’’）＝ｆ（ｉ’’，ｊ’’）としてＳｔｅｐ ２へ戻る。
また、Avoineらは、より成功率の高い方法として、Ｒ或いはｆを適用するたびに変化させるrainbow table法について言及している。このrainbow table法では、例えば、上述したＲ（ｒ）の代わりに、
【００１１】
【数２】
2007141004.tif 000004
を用い、上述のサーバ初期設定やサーバの処理を実行する。
【非特許文献１】EPC global, Inc.、”EPCglobal”、[online]、[平成１７年１１月１０日検索]、インターネット＜http://www.epcglobalinc.org/＞
【非特許文献２】Miyako Ohkubo, Koutarou Suzuki, Shingo Kinosita, "Cryptographic Approach to "Privacy-Friendly" Tags", In RFID Privacy Workshop, MIT, MA, USA, November 2003．
【非特許文献３】Gildas Avoine, Etienne Dysli, and Philippe Oechslin. Reducing Time Complexity in RFID Systems. In SAC 2005, 12th Annual Workshop on Selected Areas in Cryptography, 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかし、Avoineらの方法は、上述の事前計算テーブルを作成するための演算量が大きいという問題点がある。すなわち、Avoineらの方法においてこの事前計算テーブルを作成する場合、タグ数ｎ、最大チェーン数ｍとしたときにｎ・ｍ２／２回のハッシュ関数の呼び出しが必要であり（例えば、非特許文献３参照）、この処理を行うための演算量が非常に大きい。
本発明はこのような点に鑑みてなされたものであり、このような順次更新される更新情報から所定の識別子を抽出する処理に用いられる事前計算テーブルを作成する際の演算量を低減させることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、識別子と、更新関数を順次作用させることにより更新される補助更新情報と、を対応付けた補助テーブルが補助テーブルメモリに格納され、第１値と第２値とを対応付けた複数のスタートポイント情報がスタートポイントメモリに格納され、スタートポイント情報の複製を初期値とする複数のエンドポイント情報がエンドポイントメモリに格納されたことを前提に、第１演算部が、エンドポイント情報が具備する第１値と一致する識別子に対応付けられている補助更新情報を用い、当該第１値に対応する第２値が示す数だけ更新された更新情報を生成するステップと、第２演算部が、１つの入力値に対して第１出力値と第２出力値との組を出力するリダクション関数を、第１演算部で生成された更新情報に作用させ、第１出力値と第２出力値との組を生成するステップと、エンドポイント更新部が、第２演算部で生成された第１出力値及び第２出力値を、それぞれ新たな第１値及び第２値としてエンドポイントメモリのエンドポイント情報を更新するステップとを、複数のスタートポイント情報に対し、それぞれ繰り返し実行する。
【００１４】
ここで、エンドポイント情報を構成する第１値は、リダクション関数から出力された第１出力値によって順次更新される。よって、異なるスタートポイント情報に基づいてそれぞれ生成されたエンドポイント情報の第１値が互いに一致する場合も起こりうる。また、第１演算部は、エンドポイント情報が具備する第１値と一致する識別子に対応付けられている補助更新情報を用いて更新情報を生成する。そのため、異なるスタートポイント情報に基づいてそれぞれ生成されたエンドポイント情報の第１値が互いに一致した場合、第１演算部は、同じ補助更新情報を重複して利用し、各更新情報を生成することになる。もちろん、本発明でも補助テーブルメモリに格納される補助更新情報の生成には更新関数を順次作用させる演算が必要である。しかし、本発明では、一旦生成された補助更新情報を補助テーブルメモリに格納し、これを異なるスタートポイント情報に対応する第１演算部の処理に再利用する。その結果、重複した演算を繰り返す必要がなくなり、全体的な演算量を低減させることができる。
【００１５】
また、本発明において好ましくは、リダクション関数から出力される第２出力値の値域は、更新情報の更新回数の最大値から１を減じた値と０との間の一部の範囲に限定される。
ここで、エンドポイント情報を構成する第２値は、リダクション関数から出力された第２出力値によって順次更新され、第１演算部は、エンドポイント情報が具備する第１値と一致する識別子に対応付けられている補助更新情報を用い、当該第１値に対応する第２値が示す数だけ更新された更新情報を生成する。そのため、リダクション関数から出力される第２出力値の値域を制限した場合、第１演算部が生成すべき更新情報の更新回数も制限できる。これにより、補助テーブルを構成する補助更新情報のデータ量や、第１演算部が行うべきデータ検索量や更新演算回数を低減させることができる。
【００１６】
さらにこの場合、補助テーブルにおいて各識別子に対応付けられる補助更新情報の個数を、それぞれ、更新情報の更新回数の最大値未満とすることが好ましい。このような構成は、上述のようにリダクション関数から出力される第２出力値の値域を制限することによって可能となる。そして、このような構成により、補助テーブルのデータ量を低減させることができるとともに、第１演算部が行うべきデータ検索量も削減できる。
さらにこの場合、補助テーブルにおいて各識別子に対応付けられる補助更新情報の個数を、それぞれ、更新することなくリダクション関数から出力され得る第２出力値の要素数と同一とすることが好ましい。このような構成は、上述のようにリダクション関数から出力される第２出力値の値域を制限することによって可能となる。そして、このような構成により、補助テーブルのデータサイズを低減させることができるとともに、第１演算部が行うべきデータ検索量も削減できる。
【００１７】
また、本発明において好ましくは、第１演算部は、エンドポイント情報が具備する第１値に一致する識別子に対応付けられている補助更新情報に更新関数を作用させて、当該第１値に対応する第２値が示す数だけ更新された更新情報を生成する。ここで、第２値は、上述のようにリダクション関数から出力される第２出力値によって更新される値である。そのため、上述のようにリダクション関数から出力される第２出力値の値域を制限した場合、この更新情報を生成する際の演算回数も低減できる。
また、本発明において好ましくは、補助テーブルは、各識別子に対し、更新回数がエンドポイント情報の第２値と一致し得る補助更新情報のみをそれぞれ対応付けたテーブルである。この場合、第１演算部は、補助テーブルを構成する補助更新情報に対する更新演算を行うことなく更新情報を生成できる。そして、上述のようにリダクション関数から出力される第２出力値の値域を制限した場合には、補助テーブルのデータサイズを低減させることができるとともに、第１演算部が行うべきデータ検索量も削減できる。
【００１８】
また、本発明において、好ましくは、補助更新情報更新部において、エンドポイント更新部によるエンドポイントの更新後、補助テーブルメモリに格納された補助更新情報を更新し、リダクション関数から出力される第２出力値の値域は、エンドポイント更新部による上記エンドポイント情報の更新に伴って変化する。これにより、異なるスタートポイント情報に対応するエンドポイント情報が同一となってしまう可能性を低減させることができる。
さらに、この場合、補助更新情報更新部が、補助テーブルメモリに格納された補助更新情報に新たな補助更新情報を上書きして補助更新情報の更新を行うことが望ましい。これにより、補助テーブルメモリに要求される記憶容量を低減させることができる。
【発明の効果】
【００１９】
本発明では、補助テーブルメモリに格納された補助更新情報を、異なるスタートポイント情報に対応する複数の第１演算部の処理に再利用することとしたため、事前計算テーブルを作成する際の演算量を低減させることができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔第１の実施の形態〕
第１の実施の形態では、補助テーブルを用い、上述のようなタイムメモリトレードオフ法に用いる事前計算テーブルを生成する。この構成により、スタートポイント情報が異なるエンドポイント情報の生成過程において、ハッシュ演算結果の一部を再利用することが可能となる。これにより、事前計算テーブルを作成する際の演算量を削減する。
また、本形態では、エンドポイント情報の生成に用いるリダクション関数の値域を制限する。これにより、補助テーブルを用いて事前計算テーブルを生成する際の演算量を抑制する。これによっても、事前計算テーブルを作成する際の演算量を削減することができる。
【００２１】
以下、本発明の第１の実施の形態について詳細に説明する。
＜ハードウェア構成＞
図１は、第１の実施の形態におけるテーブル作成装置１００のハードウェア構成を例示したブロック図である。
図１に例示するように、この例のテーブル作成装置１００は、ＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００２２】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、この例の入力部１２は、データが入力される入力ポート、キーボード、マウス等であり、出力部１３は、データを出力する出力ポート、ディスプレイ等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、本形態の処理を実行するためのプログラムを格納したプログラム領域１４ａ及びタグ出力情報等の各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、例えば、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが書き込まれるプログラム領域１６ａ及び各種データが書き込まれるデータ領域１６ｂを有している。また、この例のバス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を、データのやり取りが可能なように接続する。
【００２３】
＜ハードウェアとソフトウェアとの協働＞
この例のＣＰＵ１１は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されているプログラムを、ＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データをＲＡＭ１６のデータ領域１６ｂに書き込む。さらに、ＣＰＵ１１は、当該プログラムや各種データが書き込まれたＲＡＭ１６上のアドレスをレジスタ１１ｃに格納する。そして、ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００２４】
図２は、このようにＣＰＵ１１にプログラムが読み込まれることにより構成されるテーブル作成装置１００の機能ブロック図の例示である。なお、図２における矢印はデータの流れを示すが、制御部１１２に入出力されるデータの流れの記載は省略してある。
図２に示すように、本形態のテーブル作成装置１００は、補助更新情報初期化部１０１、補助テーブルメモリ１０２、スタートポイント情報生成部１０３、スタートポイントメモリ１０４、複製部１０５、エンドポイントメモリ１０６、第１演算部１０７、第２演算部１０８、エンドポイント更新部１０９、補助更新情報更新部１１０、事前計算テーブル抽出部１１１、制御部１１２及び一時メモリ１１３を有している。
【００２５】
なお、補助テーブルメモリ１０２、スタートポイントメモリ１０４、エンドポイントメモリ１０６及び一時メモリ１１３は、例えば、図１に記載したレジスタ１１ｃ、補助記憶装置１４、ＲＡＭ１６、或いはこれらを結合した記憶領域に相当する。また、補助更新情報初期化部１０１、スタートポイント情報生成部１０３、複製部１０５、第１演算部１０７、第２演算部１０８、エンドポイント更新部１０９、補助更新情報更新部１１０、事前計算テーブル抽出部１１１及び制御部１１２は、それぞれ所定のプログラムがＣＰＵ１１に読み込まれることにより構成されるものである。また、テーブル作成装置１００は、制御部１１２の制御のもと各処理を実行する。また、特に断りがない限り、各演算過程で生成されたデータは、次の演算処理に用いられるまで一時メモリ１１３に一時格納され、必要に応じて読み出されるものとする。
【００２６】
＜事前計算テーブル作成処理＞
図３及び図４は、第１の実施の形態の事前計算テーブル作成処理を説明するためのフローチャートであり、図５は、本形態の処理を説明するための図である。以下、これらの図を用いて、本形態の事前計算テーブル作成処理を説明する。
まず、補助更新情報初期化部１０１（図２）に、各タグに対応する種（seed）情報ｓｉ〔ｉ＝（０，...，ｎ−１）〕が入力される（ステップＳ１）。ここで、ｉは、各タグを示す識別子であり、ｎはタグの総数である。また、種情報ｓｉとは、順次更新されるタグの出力情報を生成するための秘密情報である。本形態の例では、ｇ（ｈｊ（ｓｉ））〔ｊ＝（１，...，ｍ）〕をタグの出力情報とする。なお、ｇ及びｈは、相互に独立な一方向性関数を意味し、本形態ではＳＨＡ−１等のハッシュ関数をｇ及びｈとする。また、ｈ（ｓｉ）とは、種情報ｓｉにハッシュ関数ｈを作用させることを意味し、ｇ（ｈｊ（ｓｉ））とは、ｈｊ（ｓｉ）にハッシュ関数ｇを作用させることを意味する。ここで、ある値にハッシュ関数を作用させるとは、ある値をハッシュ関数の変数に代入し、当該ハッシュ関数の演算を行うことを意味する。また、ｈｊ（ｓｉ）とは、ｓｉにハッシュ関数ｈをｊ回作用させることを意味する。すなわち、ｈｊ（ｓｉ））＝ｈ（ｈ（…（ｈ（ｈ（ｓｉ））））…）である。また、、ｍは、タグの出力情報の更新回数の最大値（上限）である。
【００２７】
補助更新情報初期化部１０１は、入力された各種情報ｓｉを用いて補助テーブル２００を初期化する。すなわち、入力された各種情報ｓｉを補助更新情報Ｓｉの初期値とし（Ｓｉ＝ｓｉ）、当該補助更新情報Ｓｉと識別子ｉとを関連付けた補助テーブル２００を生成して、これを補助テーブルメモリ１０２に格納する（ステップＳ２）。図５の例では、補助更新情報を（Ｓ０，Ｓ１，...，Ｓｉ，...，Ｓｎ−１）＝（１２７５，２５４２，...，０４２５，...，７９８２）としている。
【００２８】
次に、スタートポイント情報生成部１０３が、第１値ｉｋ〔ｉｋ∈｛０，...，ｎ−１｝，ｋ＝（１，...，Ｋ）〕と第２値ｊｋ〔ｊｋ∈｛０，...，δ−１｝〕とを対応付けた複数のスタートポイント情報（ｉｋ，ｊｋ）２１０をランダムに生成し、これをスタートポイントメモリ１０４に格納する（ステップＳ３）。なお、Ｋは十分に大きな自然数であり、δは１以上ｍ未満の自然数である。また、スタートポイント情報（ｉｋ，ｊｋ）２１０の第１値ｉｋ〔ｋ＝（１，...，Ｋ）〕と第２値ｊｋとの生成は、例えば、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される計算量理論に基づく擬似乱数生成アルゴリズムを用いて行われる。スタートポイントメモリ１０４は、値ｋの指定により、対応するスタートポイント情報（ｉｋ，ｊｋ）２１０を抽出できるようにデータを格納する。例えば、スタートポイントメモリ１０４は、ｋを変数とした関数の出力値を（ｉｋ，ｊｋ）のアドレスとする。
【００２９】
次に、複製部１０５が、スタートポイントメモリ１０４から各スタートポイント情報（ｉｋ，ｊｋ）２１０を読み込み、それらを複製したエンドポイント情報（ｉｋ’，ｊｋ’）２２０の初期値を生成し〔（ｉｋ’，ｊｋ’）＝（ｉｋ，ｊｋ）〕、これらをエンドポイントメモリ１０６に格納する（ステップＳ４）。なお、エンドポイントメモリ１０６は、値ｋの指定により、対応するエンドポイント情報（ｉｋ’，ｊｋ’）２２０を抽出できるようにデータを格納する。例えば、エンドポイントメモリ１０６は、ｋを変数とした関数の出力値を（ｉｋ，ｊｋ）のアドレスとする。
【００３０】
次に、制御部１１２が、変数ｔ，ｋにそれぞれ０を代入し（ｔ＝０，ｋ＝０）、これらを一時メモリ１１３に格納する（ステップＳ５）。
次に、第１演算部１０７が、一時メモリ１１３から変数ｋを読み込み、この変数ｋの値に対応するエンドポイント情報（ｉｋ’，ｊｋ’）２２０をエンドポイントメモリ１０６から読み込む。そして、第１演算部１０７は、読み込んだエンドポイント情報（ｉｋ’，ｊｋ’）２２０の値を変数（ｉ’，ｊ’）に代入し〔（ｉ’，ｊ’）＝（ｉｋ’，ｊｋ’）〕、これを一時メモリ１１３に格納する。さらに、第１演算部１０７は、一時メモリ１１３からこの変数ｉ’（変数ｉ’にはエンドポイント情報の第１値ｉｋ’が代入されている）を読み込み、この変数ｉ’に対応する補助更新情報Ｓｉ’（変数ｉ’に一致する識別子に対応付けられている補助更新情報Ｓｉ’）を補助テーブルメモリ１０２の補助テーブル２００から抽出する（ステップＳ６）。次に、第１演算部１０７は、一時メモリ１１３から変数ｊ’（変数ｊ’にはエンドポイント情報の第２値ｊｋ’が代入されている）を読み込み、補助更新情報Ｓｉ’を用い、初期値からｊ’回更新された更新情報Ｆｔ（ｉ’，ｊ’）＝ｇ（ｈｊ’−ｔ（Ｓｉ’））を生成する（ステップＳ７）。なお、初期値からｊ’回更新された更新情報Ｆｔ（ｉ’，ｊ’）がｇ（ｈｊ’−ｔ（Ｓｉ’））によって算出できるのは、補助更新情報Ｓｉ’がＳｉ’＝ｈｔ（ｓｉ’）の関係を満たしているからである（後述のステップＳ１４及び図６（ｂ）参照）。
【００３１】
算出された更新情報Ｆｔ（ｉ’，ｊ’）は第２演算部１０８に転送され、第２演算部１０８は、この更新情報Ｆｔ（ｉ’，ｊ’）にリダクション関数Ｒｔ（ｒ）を作用させ、第１出力値ｉｋ’’と第２出力値ｊｋ’’との組（ｉｋ’’，ｊｋ’’）＝Ｒｔ（Ｆｔ（ｉ’，ｊ’））＝ｆｔ（ｉ’，ｊ’）を生成する（ステップＳ８）。ここで、リダクション関数Ｒｔ（ｒ）は、１つの入力値に対して一義的に定まる第１出力値と第２出力値との組を出力する関数である。本形態ではさらに、以下の条件を満たすリダクション関数Ｒｔ（ｒ）を用いる。
【００３２】
条件１：リダクション関数Ｒｔ（ｒ）から出力される第２出力値ｊｋ’’の値域は、０とｍ−１との間の一部の範囲に限定される（ｍは更新情報Ｆｔ（ｉ’，ｊ’）の更新回数ｊ’の最大値）。
条件２：リダクション関数Ｒｔ（ｒ）から出力される第２出力値ｊｋ’’の値域は、エンドポイント情報の更新に伴って変化する。
このようなリダクション関数Ｒｔ（ｒ）の一例として、本形態では、
【００３３】
【数３】
2007141004.tif 000005
を用いる。なお、δは前述の１以上ｍ未満の自然数である。
生成された第１出力値ｉｋ’’と第２出力値ｊｋ’’との組（ｉｋ’’，ｊｋ’’）はエンドポイント更新部１０９に転送される。エンドポイント更新部１０９は、転送された第１出力値ｉｋ’’と第２出力値ｊｋ’’との組（ｉｋ’’，ｊｋ’’）を、新たな第１値ik’及び第２値jk’としてエンドポイントメモリ１０６に格納されたエンドポイント情報（ｉｋ’，ｊｋ’）を上書更新（（ｉｋ’，ｊｋ’）＝（ｉｋ’’，ｊｋ’’））する（ステップＳ９）。例えば、図５の例では、ｋ＝ｔ＝０の際に、エンドポイント情報が（ｉｋ’，ｊｋ’）＝（３，０）から（１，１）に更新されている。なお、上書更新とは、あるアドレスに格納されていたデータを消去或いは他のアドレスに退避させ、代わりに他のデータを格納することを意味する。
【００３４】
次に、制御部１１２は、ｋ＝Ｋ−１であるか否か（すなわち、ステップＳ９でエンドポイント情報（ｉＫ−１’，ｊＫ−１’）の更新が行われたか否か）を判断する（ステップＳ１０）。ここで、ｋ＝Ｋ−１でなければ、制御部１１２は、一時メモリ１１３に格納された変数ｋの値をｋ＋１で更新し、処理をステップＳ６に戻す（ステップＳ１１）。一方、ｋ＝Ｋ−１であれば、次に、制御部１１２は、一時メモリ１１３から変数ｔを読み込み、ｔ＜Ｌであるか否かを判定する（ステップＳ１２）。なお、Ｌは例えば事前にプログラムに設定された十分に大きな自然数である。
【００３５】
ここで、ｔ＜Ｌであると判断された場合、制御部１１２は、一時メモリ１１３に格納された変数ｋの値を０にし、変数ｔの値をｔ＋１とし（ステップＳ１３）、さらに、補助更新情報更新部１１０が、補助テーブルメモリ１０２に格納された補助テーブル２００の全ての補助更新情報Ｓｉ〔ｉ＝（０，...，ｎ−１）〕を、ハッシュ関数ｈ（「更新関数」に相当）を作用させることにより上書更新（Ｓｉ＝ｈ（Ｓｉ））する（ステップＳ１４）。その後、処理がステップＳ６に戻される。なお、ステップＳ６〜Ｓ１４の処理の繰り返しにより、図５の例では、補助更新情報が（Ｓ０，Ｓ１，...，Ｓｉ，...，Ｓｎ−１）＝（１２７５，２５４２，...，０４２５，...，７９８２）→（５５８１，８７３６，...，７５０１，...，００２５）→・・・→１７２３，７７８１，...，９５８２，...，７４１０）と更新される。
【００３６】
一方、ステップＳ１２でｔ＜Ｌでないと判断された場合、エンドポイント情報２２０は、（ｉｋ’，ｊｋ’）＝ｆＬ−１（ｆＬ−２（…ｆ1（ｆ０（ｉｋ，ｊｋ））…））となっている。この場合、事前計算テーブル抽出部１１１は、スタートポイントメモリ１０４のスタートポイント情報２１０と、エンドポイントメモリ１０６のエンドポイント情報２２０とを読み込み、これらの組（ｉｋ，ｊｋ），（ｉｋ’，ｊｋ’）〔ｋ＝（０，...，Ｋ−１）〕を事前計算テーブルとして出力し、制御部１１２が一連の処理を終了させる（ステップＳ１５）。
【００３７】
＜本形態の特徴＞
図６（ａ）（ｂ）は、本形態の特徴を説明するための概念図である。
上述のように、ステップＳ４の処理によってスターとポイント情報（ｉｋ，ｊｋ）が、エンドポイント情報（ｉｋ’，ｊｋ’）の初期値として複製され、その後、ステップＳ６〜Ｓ１５の処理によって、エンドポイント情報（ｉｋ’，ｊｋ’）が順次更新される（図６（ａ））。この場合、例えば、図６（ａ）のｔ＝２において（ｉ０’，ｊ０’）＝（５，４），（ｉ２’，ｊ２’）＝（５，５）となっているように、異なるスタートポイント情報（ｉｋ，ｊｋ）に基づいてそれぞれ生成されたエンドポイント情報（ｉｋ’，ｊｋ’）の第１値ｉｋ’が互いに一致する場合も起こりうる。
【００３８】
また、ステップＳ６〜Ｓ９で示したように、エンドポイント情報（ｉｋ’，ｊｋ’）の更新は、（ｉｋ’，ｊｋ’）＝Ｒｔ（ｇ（ｈｊ’−ｔ（Ｓｉ’）））〔（ｉ’，ｊ’）＝（ｉｋ’，ｊｋ’）〕によって行われる。ここで用いられる補助更新情報Ｓｉ’は、ｉ’をキーとして補助テーブル２００から検索されるものである。よって、上述のように、異なるスタートポイント情報（ｉｋ，ｊｋ）に基づいてそれぞれ生成されたエンドポイント情報（ｉｋ’，ｊｋ’）の第１値ｉｋ’が互いに一致していた場合、それらのエンドポイント情報（ｉｋ’，ｊｋ’）の更新には、補助テーブル２００から抽出された同じ補助更新情報Ｓｉが用いられることになる。これにより、補助更新情報Ｓｉに相当するハッシュ演算を別々に行う場合に比べ、演算量を低減させることができる。
【００３９】
また、図６（ｂ）に示すように、式（１）のリダクション関数Ｒｔ（ｒ）を用いた場合、リダクション関数Ｒｔ（ｒ）の第２出力値ｊｋ’’の値域は、ｔ≦ｊｋ’’＜ｔ＋δとなる。また、この際、補助テーブル２００の各補助更新情報Ｓｉの値はＳｉ＝ｈｔ（ｓｉ）となっている。よって、上述ステップＳ７では、δ−１回以下のハッシュ関数ｈの演算と１回のハッシュ件数ｇの演算との合計δ回以下のハッシュ演算により、更新情報Ｆｔ（ｉ’，ｊ’）＝ｇ（ｈｊ’−ｔ（Ｓｉ’））を計算できる。なお、式（１）のリダクション関数Ｒｔ（ｒ）の場合、ｍを法とした演算により第２出力値ｊｋ’’を計算しているため、ｔ＋δ＜ｍの場合でもｔ＋δ≧ｍの場合でも、合計δ回以下のハッシュ演算により、更新情報Ｆｔ（ｉ’，ｊ’）＝ｇ（ｈｊ’−ｔ（Ｓｉ’））を計算できる。
【００４０】
以上より、例えば、Ｌ＝ｍとした場合、本形態では、平均ｎ・ｍ・δ／２回のハッシュ演算により事前計算テーブルを計算することが可能となり、従来構成に比べて演算量が削減される。
〔第２の実施の形態〕
次に、本発明における第２の実施の形態について説明する。
本形態は、第１の実施の形態の変形例である。前述のように第１の実施の形態では、各識別子ｉに補助更新情報を１つずつ対応付けた補助テーブル２００を用い、第１演算部１０７において、ハッシュ関数ｈを必要な分だけ作用させ、さらにハッシュ関数ｇを１回作用させて更新情報を生成した。これに対し、第２の実施の形態では、複数の補助更新情報を各識別子ｉに対応付けた補助テーブルを用いる。ここで、本形態の補助テーブルにおいて、各識別子ｉに対応付けられる補助更新情報の個数は、それぞれ、更新情報の更新回数の最大値ｍ未満であり、より好ましくは、更新することなく（ｔの値を固定した場合における）リダクション関数から出力され得る第２出力値の要素数と同一である。さらに好ましくは、本形態の補助テーブルは、各識別子ｉに対し、更新回数がエンドポイント情報の第２値と一致し得る補助更新情報のみをそれぞれ対応付けたテーブルである。
【００４１】
このように本形態では、複数の補助更新情報を各識別子ｉに対応付けた補助テーブルを用いるため、第１演算部でのハッシュ関数ｈの演算回数を削減できる。特に、各識別子ｉに対し、更新回数がエンドポイント情報の第２値と必ず一致するような補助更新情報をそれぞれ対応付けた補助テーブルを用いた場合には、第１演算部でのハッシュ関数ｈの演算が不要となる。
以下では、最良の実施の形態として、各識別子ｉに対し、更新回数がエンドポイント情報の第２値と一致し得る補助更新情報のみをそれぞれ対応付けた補助テーブルを用いた例について説明する。なお、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を簡略化する。
【００４２】
図７は、ＣＰＵに所定のプログラムが読み込まれることにより構成される本形態のテーブル作成装置３００の機能ブロック図の例示である。なお、図７において、第１の実施の形態と共通する部分については図２と同じ符号を付した。
＜テーブル作成装置の構成＞
本形態のテーブル作成装置３００と第１の実施の形態のテーブル作成装置３００との相違点は、本形態のテーブル作成装置３００が、補助更新情報初期化部１０１の代わりに補助更新情報初期化部３０１を具備する点、補助テーブル２００を格納する補助テーブルメモリ１０２の代わりに補助テーブル４００を格納する補助テーブルメモリ３０２を具備する点、第１演算部１０７の代わりに第１演算部３０７を具備する点である。
【００４３】
＜事前計算テーブル作成処理＞
図８及び図９は、第２の実施の形態の事前計算テーブル作成処理を説明するためのフローチャートであり、図１０は、本形態の補助更新情報が更新される様子を説明するための図である。以下、これらの図を用いて、本形態の事前計算テーブル作成処理を説明する。
まず、補助更新情報初期化部３０１（図７）に、各タグに対応する種（seed）情報ｓｉ〔ｉ＝（０，...，ｎ−１）〕が入力される（ステップＳ２１）。
補助更新情報初期化部３０１は、入力された各種情報ｓｉを用いて補助テーブル４００を初期化する。本形態の補助更新情報初期化部３０１は、入力された各種情報ｓｉを補助更新情報Ｓｉ，０の初期値とし、Ｓｉ，α＝ｈα（ｓｉ）〔α＝（１，．．．，δ−１）〕の演算結果を補助更新情報Ｓｉ，αの初期値として生成し、これら複数の補助更新情報Ｓｉ，０，Ｓｉ，αを
識別子ｉに関連付けた補助テーブル４００を生成し、これを補助テーブルメモリ３０２に格納する（ステップＳ２２）。図１０に、このように初期設定された補助更新情報の構成を示す（ｔ＝０）。
【００４４】
次に、スタートポイント情報生成部１０３が、第１値ｉｋ〔ｉｋ∈｛０，...，ｎ−１｝，ｋ＝（１，...，Ｋ）〕と第２値ｊｋ〔ｊｋ∈｛０，...，δ−１｝〕とを対応付けた複数のスタートポイント情報（ｉｋ，ｊｋ）２１０をランダムに生成し、これをスタートポイントメモリ１０４に格納する（ステップＳ２３）。また、複製部１０５が、スタートポイントメモリ１０４から各スタートポイント情報（ｉｋ，ｊｋ）２１０を読み込み、それらを複製したエンドポイント情報（ｉｋ’，ｊｋ’）２２０の初期値を生成し〔（ｉｋ’，ｊｋ’）＝（ｉｋ，ｊｋ）〕、これらをエンドポイントメモリ１０６に格納する（ステップＳ２４）。
【００４５】
次に、制御部１１２が、変数ｔ，ｋにそれぞれ０を代入し（ｔ＝０，ｋ＝０）、これらを一時メモリ１１３に格納する（ステップＳ２５）。
次に、第１演算部３０７が、一時メモリ１１３から変数ｋを読み込み、この変数ｋの値に対応するエンドポイント情報（ｉｋ’，ｊｋ’）２２０をエンドポイントメモリ１０６から読み込む。そして、第１演算部３０７は、読み込んだエンドポイント情報（ｉｋ’，ｊｋ’）２２０の値を変数（ｉ’，ｊ’）に代入し〔（ｉ’，ｊ’）＝（ｉｋ’，ｊｋ’）〕、これを一時メモリ１１３に格納する。さらに、第１演算部３０７は、一時メモリ１１３から変数（ｉ’，ｊ’）と変数ｔとを読み込み、ｉ’，ｊ’−ｔに対応する補助更新情報Ｓｉ’，ｊ’−ｔを、補助テーブルメモリ３０２の補助テーブル４００から抽出する（ステップＳ２６）。次に、第１演算部３０７は、抽出した補助更新情報Ｓｉ’，ｊ’−ｔを用い、初期値からｊ’回更新された更新情報Ｆｔ（ｉ’，ｊ’）＝ｇ（Ｓｉ’，ｊ’−ｔ）を生成する（ステップＳ２７）。なお、初期値からｊ’回更新された更新情報Ｆｔ（ｉ’，ｊ’）がｇ（Ｓｉ’，ｊ’−ｔ）によって算出できるのは、補助更新情報Ｓｉ’，ｊ’−ｔが、ｔ＝０においてＳｉ，０＝ｓｉ，Ｓｉ，α＝ｈα（ｓｉ）〔α＝（１，．．．，δ−１）〕の関係を満たし（ステップＳ２２及び図１０参照）、ｔ≧１において、Ｓｉ，β＝Ｓｉ，β＋１〔β＝（０，．．．，δ−２）〕及び
Ｓｉ，δ−１＝ｈ（Ｓｉ，δ−２）によって更新されるからである
（後述するステップＳ３４及び図１０参照）。
【００４６】
算出された更新情報Ｆｔ（ｉ’，ｊ’）は、第２演算部１０８に転送され、第２演算部１０８は、この更新情報Ｆｔ（ｉ’，ｊ’）にリダクション関数Ｒｔ（ｒ）を作用させ、第１出力値ｉｋ’’と第２出力値ｊｋ’’との組（ｉｋ’’，ｊｋ’’）＝Ｒｔ（Ｆｔ（ｉ’，ｊ’））＝ｆｔ（ｉ’，ｊ’）を生成する（ステップＳ２８）。なお、本形態でも、第１の実施の形態と同じリダクション関数Ｒｔ（ｒ）〔式（１）〕を用いるものとする。
生成された第１出力値ｉｋ’’と第２出力値ｊｋ’’との組（ｉｋ’’，ｊｋ’’）はエンドポイント更新部１０９に転送される。エンドポイント更新部１０９は、転送された第１出力値ｉｋ’’と第２出力値ｊｋ’’との組（ｉｋ’’，ｊｋ’’）を、新たな第１値ik’及び第２値jk’としてエンドポイントメモリ１０６に格納されたエンドポイント情報（ｉｋ’，ｊｋ’）を上書更新（（ｉｋ’，ｊｋ’）＝（ｉｋ’’，ｊｋ’’））する（ステップＳ２９）。
【００４７】
次に、制御部１１２は、ｋ＝Ｋ−１であるか否かを判断する（ステップＳ３０）。ここで、ｋ＝Ｋ−１でなければ、制御部１１２は、一時メモリ１１３に格納された変数ｋの値をｋ＋１で更新し、処理をステップＳ２６に戻す（ステップＳ３１）。
一方、ｋ＝Ｋ−１であれば、次に、制御部１１２は、一時メモリ１１３から変数ｔを読み込み、ｔ＜Ｌであるか否かを判定する（ステップＳ３２）。
ここで、ｔ＜Ｌであると判断された場合、制御部１１２は、一時メモリ１１３に格納された変数ｋの値を０にし、変数ｔの値をｔ＋１とし（ステップＳ３３）、さらに、更新情報更新部３１０が、補助テーブルメモリ３０２に格納された補助テーブル４００の全ての補助更新情報Ｓｉ，γ〔ｉ＝（０，...，ｎ−１），γ＝（０，...，δ−１）〕を更新する（ステップＳ３４）。前述したように、この更新はＳｉ，β＝Ｓｉ，β＋１〔β＝（０，．．．，δ−２）〕及び
Ｓｉ，δ−１＝ｈ（Ｓｉ，δ−２）の演算により行われる。すなわち、更新情報更新部３１０は、図１０に示すように、補助更新情報Ｓｉ，１，...，Ｓｉ，δ−１の値を、新たな補助更新情報Ｓｉ，０，...，Ｓｉ，δ−２の値として上書更新し、上書更新された新たな補助更新情報Ｓｉ，δ−２の値にハッシュ関数ｈを作用させたｈ（Ｓｉ，δ−２）を新たな補助更新情報Ｓｉ，δ−１とする。なお、新たな補助更新情報Ｓｉ，０，...，Ｓｉ，δ−２を上書更新する前に、更新前の補助更新情報Ｓｉ，δ−１にハッシュ関数ｈを作用させたｈ（Ｓｉ，δ−１）を新たな補助更新情報Ｓｉ，δ−１とし、その後、補助更新情報Ｓｉ，１，...，Ｓｉ，δ−１の値を、新たな補助更新情報Ｓｉ，０，...，Ｓｉ，δ−２の値として上書更新してもよい。
【００４８】
一方、ステップＳ３２でｔ＜Ｌでないと判断された場合、事前計算テーブル抽出部１１１は、スタートポイントメモリ１０４のスタートポイント情報２１０と、エンドポイントメモリ１０６のエンドポイント情報２２０とを読み込み、これらの組（ｉｋ，ｊｋ），（ｉｋ’，ｊｋ’）〔ｋ＝（０，...，Ｋ−１）〕を事前計算テーブルとして出力し、制御部１１２が一連の処理を終了させる（ステップＳ３５）。
＜本形態の特徴＞
ステップＳ２６〜Ｓ２９で示したように、エンドポイント情報（ｉｋ’，ｊｋ’）の更新は、（ｉｋ’，ｊｋ’）＝Ｒｔ（ｇ（Ｓｉ’，ｊ’−ｔ））〔（ｉ’，ｊ’）＝（ｉｋ’，ｊｋ’）〕よって行われる。ここで用いられる補助更新情報Ｓｉ’，ｊ’−ｔは、ｉ’及びｊ’−ｔをキーとして補助テーブル４００から検索されるものである。よって、異なるスタートポイント情報（ｉｋ，ｊｋ）に基づいてそれぞれ生成されたエンドポイント情報（ｉｋ’，ｊｋ’）が互いに一致していた場合、それらのエンドポイント情報（ｉｋ’，ｊｋ’）の更新には、補助テーブル４００から抽出された同じ補助更新情報が用いられることになる。これにより、補助更新情報に相当するハッシュ演算を別々に行う場合に比べ、演算量を低減させることができる。例えば、Ｌ＝ｍとした場合、本形態では、平均２ｎ・ｍ回のハッシュ演算により事前計算テーブルを計算することが可能となり、従来構成に比べて演算量が削減される。
【００４９】
また、式（１）のリダクション関数Ｒｔ（ｒ）を用いた場合、リダクション関数Ｒｔ（ｒ）の第２出力値ｊｋ’’の値域は、ｔ≦ｊｋ’’＜ｔ＋δに制限される。そのため、補助テーブル４００を構成する補助更新情報Ｓｉ，γ〔ｉ＝（０，...，ｎ−１），γ＝（０，...，δ−１）〕も、各識別子ｉに対し、ｈｔ（ｓｉ），...，ｈδ−１＋ｔ（ｓｉ）の範囲だけ用意しておけば足りる。これにより、補助テーブル４００のデータサイズを制限できる。
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の実施の形態では、タグから出力される情報ｇ（ｈｊ（ｓｉ））を更新情報とした例について説明したが、所定の関数を作用させることによって順次更新されるのであれば、その他の情報を更新情報としてもよい。例えば、ｈｊ（ｓｉ）を更新情報としてもよく、ＩＣカードからの出力情報、コンピュータから出力される認証情報等を更新情報としてもよい。
【００５０】
また、上述の実施の形態では、更新関数としてハッシュ関数を用いたが、ハッシュ関数の代わりにその他の関数を用いてもよい。例えば、更新関数として共通鍵暗号関数や公開鍵暗号関数を用いてもよい。
また、上述の実施の形態の補助テーブルは、識別子のカラムと補助更新情報とのカラムとを有するテーブルであったが、識別子と補助更新情報との対応付けが可能な他の構成の補助テーブルを用いてもよい。例えば、識別子のカラムを構成せず、補助更新情報を対応する識別子から算出したアドレスに格納する構成としてもよい。
【００５１】
また、補助テーブルにおいて各識別子に対応付けられる補助更新情報の数は、上述の各実施の形態に限定されず、それ以外の数の補助更新情報を各識別子に対応付けることとしてもよい。
さらに、第１の実施の形態と第２の実施の形態とを融合し、必要な更新回数の補助更新情報が補助テーブルに存在する場合には、第１演算部が、その補助更新情報をそのまま用いて更新情報を生成し、必要な更新回数の補助更新情報が補助テーブルに存在しない場合には、第１演算部が、必要な更新回数に最も近い補助更新情報に更新関数を作用させて更新情報を生成する構成としてもよい。
また、１つの入力値に対して一義的に定まる第１出力値と第２出力値との組を出力する関数であれば、上述した以外の関数をリダクション関数として用いてもよい。以下にリダクション関数の変形例を示す。
【００５２】
【数４】
2007141004.tif 000006
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力或いは必要に応じて並列的に或いは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００５４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００５６】
本発明の産業上の利用分野としては、ＲＦＩＤ等のタグシステムにおけるタグ認証、タグやＩＣカードを用いた真贋判定等の分野を例示できる。
【図面の簡単な説明】
【００５７】
【図１】図１は、第１の実施の形態におけるテーブル作成装置のハードウェア構成を例示したブロック図である。
【図２】図２は、第１の実施の形態のテーブル作成装置の機能ブロック図の例示である。
【図３】図３は、第１の実施の形態の事前計算テーブル作成処理を説明するためのフローチャートである。
【図４】図４は、第１の実施の形態の事前計算テーブル作成処理を説明するためのフローチャートである。
【図５】図５は、第１の実施の形態の処理を説明するための図である。
【図６】図６（ａ）（ｂ）は、第１の実施の形態の特徴を説明するための概念図である。
【図７】図７は、第２の実施の形態のテーブル作成装置の機能ブロック図の例示である。
【図８】図８は、第２の実施の形態の事前計算テーブル作成処理を説明するためのフローチャートである。
【図９】図９は、第２の実施の形態の事前計算テーブル作成処理を説明するためのフローチャートである。
【図１０】図１０は、第２の実施の形態の補助更新情報が更新される様子を説明するための図である。
【符号の説明】
【００５８】
１００，３００  テーブル作成装置
２００，４００  補助テーブル
【図１】
2007141004.tif 000007
【図２】
2007141004.tif 000008
【図３】
2007141004.tif 000009
【図４】
2007141004.tif 000010
【図５】
2007141004.tif 000011
【図６】
2007141004.tif 000012
【図７】
2007141004.tif 000013
【図８】
2007141004.tif 000014
【図９】
2007141004.tif 000015
【図１０】
2007141004.tif 000016