JP4576341B2 - 管理装置、通信装置、通信情報探索装置、それらのシステム、それらの方法及びそれらのプログラム - Google Patents

Description

本発明は、情報セキュリティ技術の応用に関し、特に、自動認識技術を用いた通信技術に関する。

近年、ＲＦＩＤ(Radio Frequency Identification：電波方式認識)等のタグ自動認識技術を用いた無線タグシステムの導入が進んでいる。このシステムは、小型の情報記録媒体であるタグ装置、読み取り機であるリーダ装置、データベースを管理するサーバ装置から構成され、物流管理等に利用されるものである。以下、この技術の要点を示す。
〔タグ装置の処理〕
タグ装置は、無線通信により、各タグ装置固有のＩＤをリーダ装置に送信する。
〔リーダ装置の処理〕
リーダ装置は、無線通信によりタグ装置からＩＤを読み取り、そのＩＤを用いたサーバ装置のデータベースへの問い合わせにより、タグ装置の物流情報などを得る。
〔サーバ装置の処理〕
サーバ装置は、各タグ装置のＩＤと物流情報等のデータベースを管理し、リーダ装置からのＩＤによる問い合わせに対する回答を行う。

このような技術の代表的な例として、ハッシュチェイン（hash chain）により、タグ装置の出力値を出力ごとに変化させ、タグ装置が追跡（trace）されることを防ぎ、タグ装置の所有者のプライバシを保護する方式がある（例えば、非特許文献１参照）。
この方式では、各タグ装置のメモリに、それぞれのＩＤに対応する秘密値ｓ_ｉを格納しておく。そして、リーダ装置からの呼び出しに対し、タグ装置は、メモリの秘密値ｓ_ｉのハッシュ値Ｇ（ｓ_ｉ）を出力値として出力する。その際、タグ装置は、メモリから秘密値ｓ_ｉを読み込み、そのハッシュ値Ｈ（ｓ_ｉ）によってメモリ内の秘密値を上書き更新する。一方、サーバ装置では、各タグ装置に対応するＩＤと秘密値ｓ_ｉとの対応データベースを保持している。そして、サーバ装置は、タグ装置からの出力値が、秘密値ｓ_ｉのハッシュチェイン値と一致するか否かを総当りで探索し、この出力値に対応するＩＤを決定する。

この方式の場合、タグ装置が出力値を出力する度にメモリ内の秘密値が上書き更新される。そのため、タグ装置の出力値は出力ごとに異なり、これらの出力値は攻撃者からは単なる乱数にみえる。また、攻撃者がタンパー等によりメモリに格納された秘密値を取得しても、更新後の秘密値は更新前にタグ装置から送信された出力値には対応していない。そして、この更新は、秘密値にハッシュ関数を作用させることにより行われる。ハッシュ関数の一方向性から、ある時点の秘密値から更新前の秘密値を求めることは困難である。よって、攻撃者は、タグ装置と通信履歴との対応を知ることができない。これにより、タグ装置の追跡を防止できる。
Miyako Ohkubo, Koutarou Suzuki, and Shingo Kinoshita, Cryptographic Approach to "Privacy-Friendly" Tags, RFID Privacy Workshop, November 2003.

しかし、非特許文献１の方式の場合、サーバ装置のデータベース管理者が変わった後であっても、旧データベース管理者は、タグ装置を追跡できるという問題点がある。すなわち、非特許文献１の方式の場合、旧データベース管理者は、各タグ装置に対応するＩＤと秘密値とを知っている。よって、この旧データベース管理者は、他者がデータベース管理者となった後であっても、タグ装置を追跡することができる。
また、タグ装置の所有者が、そのメモリに格納された秘密値を知ることができた場合にも同様な問題が生じる。すなわち、この場合、旧所有者は、タグ装置を他者に譲渡した後であっても、その後にタグ装置から出力される値を容易に求めることができる。よって、この旧所有者は、譲渡後のタグ装置を追跡できる。

このような問題は、タグ自動認識技術を用いた無線タグシステムに限らず、一方向性関数によって更新される通信情報の自動認識を行うシステムに共通するものである。そして、このような問題は、通信情報の取扱い権限を一旦付与すると、その後、その権限を制限することができないということに起因する。
本発明はこのような点に鑑みてなされたものであり、一方向性関数によって更新される通信情報の自動認識を行うシステムにおいて、通信情報の取扱い権限を制限し、プライバシの保護を図る技術を提供することを目的とする。

本発明では上記課題を解決するために、一方向性関数によって更新される通信情報の取扱い権限を付与する管理装置が提供される。この管理装置は、識別子と第１秘密値とを対応付けた秘密値テーブルを格納する秘密値テーブル記憶部と、一方向性関数を特定するための情報をノードとし、兄弟ノードに対応する一方向性関数が相互に異なり、親ノードに対応する一方向性関数と所定の一方向性関数との合成写像が子ノードに対応する一方向性関数となる木構造データから、ノードを選択するノード選択部と、ノード選択部が選択したノードに対応する一方向性関数を抽出する一方向性関数抽出部と、一方向性関数抽出部が抽出した一方向性関数を第１秘密値に作用させた一方向性関数値を生成する一方向性関数演算部と、一方向性関数値を含む権限情報を生成する権限情報生成部と、権限情報を出力する権限情報出力部とを有する。木構造データの「一方向性関数を特定するための情報」には、対応する一方向性関数が存在しない〔一方向性関数が空である（例えばルートノードに対応）〕旨の情報をも含む。

ここで、権限情報が具備する一方向性関数値は、第１秘密値に一方向性関数を作用させた値であり、この一方向性関数は、上記木構造データの何れかのノードに対応する。そして、この木構造データのノードに対応する一方向性関数は、「兄弟ノードに対応する一方向性関数が相互に異なる」という条件を満たす。また、この木構造データのノードに対応する一方向性関数は、「親ノードに対応する一方向性関数と所定の一方向性関数との合成写像」が「子ノードに対応する一方向性関数」になるという関係をも満たす。よって、権限情報が具備する一方向性関数値に一方向性関数を順次作用させて得られる値は、この「一方向性関数値の生成に用いた一方向性関数に対応するノード」の子孫ノードに対応する一方向性関数を第１秘密値に作用させた値のみである。すなわち、この権限情報のみからは、この「一方向性関数値の生成に用いた一方向性関数に対応するノード」の先祖ノードや兄弟ノードや当該兄弟ノードの子孫ノードに対応する一方向性関数を第１秘密値に作用させた値を得ることはできない。上記木構造データの特徴及び一方向性関数の性質に基づく。その結果、権限情報が付与された者には、その一方向性関数値の生成に用いられた一方向性関数に対応するノードの子孫ノードに対応する一方向性関数を第１秘密値に作用させた値から得られる通信情報のみの取扱い権限が付与されたことになる。

また、本発明において好ましくは、権限情報は、通信情報の生成権限を付与するための情報である。この権限情報は、一方向性関数によって更新される通信情報を出力する通信装置（例えばタグ装置）に付与される。この通信装置は、付与された権限情報が具備する一方向性関数値の生成に用いた一方向性関数に対応するノードの子孫ノードに対応する一方向性関数を第１秘密値に作用させた値から得られる通信情報のみを生成できる。

また、本発明において好ましくは、権限情報は、通信情報の探索権限を付与するための情報であり、一方向性関数値とその生成に用いられた第１秘密値に対応する識別子とを含む。この権限情報は、一方向性関数によって更新される通信情報から、それに対応する識別子を特定する通信情報探索装置（例えば、前述のサーバ装置）に付与される。この通信情報探索装置は、付与された権限情報が具備する一方向性関数値の生成に用いた一方向性関数に対応するノードの子孫ノードに対応する一方向性関数を第１秘密値に作用させた値から得られる通信情報のみを探索できる。

また、本発明において好ましくは、権限情報生成部は、通信情報の探索権限を付与するための権限情報と、通信情報の生成権限を付与するための権限情報とを生成し、通信情報の探索権限を付与するための権限情報は、一方向性関数値とその生成に用いられた第１秘密値に対応する識別子とを含む。ここで、通信情報の探索権限を付与するための権限情報は、一方向性関数によって更新される通信情報を出力する通信装置に付与されるものである。また、通信情報の生成権限を付与するための権限情報は、一方向性関数によって更新される通信情報から、それに対応する識別子を特定する通信情報探索装置に付与されるものである。

また、本発明において好ましくは、秘密値テーブルは、識別子と第１秘密値と第２秘密値とを対応付けたテーブルであり、権限情報生成部は、一方向性関数値と第２秘密値とを含む権限情報を生成する。
また、本発明の通信装置は、上述の管理装置から出力された権限情報（一方向性関数値を含む）を格納する生成権限情報記憶部と、生成権限情報記憶部から読み込んだ一方向性関数値を含む情報に所定の一方向性関数を作用させ、通信情報を生成する通信情報生成部と、通信情報を出力する通信情報出力部とを有する。この通信装置は、付与された権限情報が具備する一方向性関数値の生成に用いた一方向性関数に対応するノードの子孫ノードに対応する一方向性関数を第１秘密値に作用させた値から得られる通信情報のみを生成できる。

また、本発明の通信情報探索装置は、上述の管理装置から出力された権限情報（一方向性関数値とその生成に用いられた第１秘密値に対応する識別子とを含む）を格納する探索権限情報記憶部と、通信情報の入力を受け付ける入力部と、権限情報の一方向性関数値を含む情報に所定の一方向性関数を作用させた探索値を生成する探索値生成部と、通信情報と探索値とが一致するか否かを判断する比較部と、通信情報と一致した探索値に対応する識別子を探索権限情報記憶部から抽出する抽出部とを有する。この通信情報探索装置は、付与された権限情報が具備する一方向性関数値の生成に用いた一方向性関数に対応するノードの子孫ノードに対応する一方向性関数を第１秘密値に作用させた値から得られる通信情報のみを探索できる。

本発明では、一方向性関数によって更新される通信情報の自動認識を行うシステムにおいて、通信情報の取扱い権限を制限し、プライバシの保護を図ることが可能となる。

以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔第１の実施の形態〕
まず、本発明における第１の実施の形態について説明する。
本形態は、通信情報の生成権限を付与するための権限情報をタグ装置に与え、通信情報の探索権限を付与するための権限情報をサーバ装置に与え、タグ装置の通信情報の生成範囲とサーバ装置の探索範囲とを制限する形態である。以下、この詳細を説明する。
＜全体構成＞
図１は、第１の実施の形態のタグ通信システム１の全体構成を示した概念図である。

図１に例示するように、タグ通信システム１は、管理サーバ装置１０（「管理装置」に相当）、タグ装置２０（「通信装置」に相当）、サーバ装置４０（「通信情報探索装」に相当）、リーダ装置６０、ライタ装置７０及びネットワーク８０を有しており、サーバ装置４０とリーダ装置６０、管理サーバ装置１０とサーバ装置４０、管理サーバ装置１０とライタ装置７０は、それぞれインターネット等のネットワーク８０を通じて通信可能に構成されている。なお、図１には、１つのタグ装置２０のみを図示しているが、実際はｋ個（ｋは自然数）のタグ装置２０が存在する。また、図１には、それぞれ１個の管理サーバ装置１０、サーバ装置４０、リーダ装置６０及びライタ装置７０を図示しているが、管理サーバ装置１０、サーバ装置４０、リーダ装置６０及びライタ装置７０の数は、これ以上であってもよい。

＜管理サーバ装置１０の構成＞
図２は、第１の実施の形態における管理サーバ装置１０の機能構成を示したブロック図である。
図２に例示するように、管理サーバ装置１０は、メモリ１１、乱数生成部１２、ノード選択部１３、一方向性関数抽出部１４、一方向性関数演算部１５、権限情報生成部１６、権限情報出力部１７、制御部１８及び一時メモリ１９を有している。ここで、メモリ１１は、データを記憶する領域である記憶部１１ａ〜１１ｇを有しており、記憶部１１ａは、「秘密値テーブル記憶部」に相当する。

なお、管理サーバ装置１０は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ハードディスク等の外部記憶装置、ＬＡＮカード等の通信装置をバスで接続した公知のノイマン型コンピュータに所定のプログラムを実行させることにより構成される。この場合、メモリ１１及び一時メモリ１９は、レジスタ、ＲＡＭ、外部記憶装置等又はそれらが複合された記憶領域に相当する。これらのメモリ１１及び一時メモリ１９に格納されるデータについては後述する。また、乱数生成部１２、ノード選択部１３、一方向性関数抽出部１４、一方向性関数演算部１５及び権限情報生成部１６は、所定のプログラムが読み込まれたＣＰＵに相当する。さらに、権限情報出力部１７は、所定のプログラムが読み込まれたＣＰＵの制御によって駆動する通信装置に相当する。

また、管理サーバ装置１０は、制御部１８の制御のもと各演算処理を実行する。また、明示しない限り、各データは、適宜、逐一一時メモリ１９に格納され、各処理に利用される。また、図２における矢印はデータの流れを示すが、制御部１８及び一時メモリ１９に入出力するデータの流れの記載は省略してある。
＜タグ装置２０の構成＞
図３は、第１の実施の形態におけるタグ装置２０の機能構成を示したブロック図である。
図３に例示するように、タグ装置２０は、メモリ２１、通信情報生成部２２、通信情報出力部２３、更新部２４、カウンタ２５、入力部２６、書き込み部２７、カウント初期化部２８、一時メモリ２９及び制御部３０を有している。ここで、メモリ２１は、記憶部２１ａ〜２１ｄを有しており、記憶部２１ａ，２１ｂは、「生成権限情報記憶部」に相当する。また、メモリ２１に格納されるデータについては後述する。

なお、メモリ２１及び一時メモリ２９は、例えば、ＥＥＰＲＯＭ（Electronically Erasable and Programmable Read Only Memory）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）、フラッシュメモリ、ＮＶ（Nonvolatile）ＲＡＭ等の読書き可能なメモリである。また、通信情報生成部２２、更新部２４、カウンタ２５、カウント初期化部２８及び制御部３０は、例えば、各処理を実行する集積回路又は所定のプログラムが読み込まれたＣＰＵである。また、入力部２６及び通信情報出力部２３は、それぞれデータの入力及び出力を行うハードウェアである。例えば、入力部２６及び通信情報出力部２３は、ＮＲＺ符号やマンチェスター符号化やミラー符号や単極ＲＺ符号化等によって符号化・復号化を行う符号化・復号化回路、ＡＳＫ(Amplitude Shift Keying)やＰＳＫ(Phase Shift Keying)やＦＳＫ(Frequency Shift Keying)等によって変・復調を行う変・復調回路、ダイポールアンテナやマイクロストリップアンテナやループコイルやコア入りコイル等のアンテナを有し、ＩＳＭ帯（Industry Science Medical band）の周波数等を用いて信号の送受信を行うハードウェアである。また、書き込み部２７は、制御部３０の制御のもとメモリ２１に対してデータを読み書きするハードウェアである。

また、タグ装置２０は、制御部３０の制御のもと各処理を実行する。また、明示しない限り、各データは、適宜、逐一一時メモリ２９に格納され、各処理に利用される。また、図３における矢印はデータの流れを示すが、制御部３０及び一時メモリ２９に入出力するデータの流れの記載は省略してある。
＜サーバ装置４０の構成＞
図４は、第１の実施の形態におけるサーバ装置４０の機能構成を示したブロック図である。

図４に例示するように、サーバ装置４０は、メモリ４１、入力部４２、書き込み部４３、カウンタ４４，４５、探索値生成部４６、比較部４７、抽出部４８、出力部４９、制御部５０及び一時メモリ５１を有している。
なお、サーバ装置４０は、例えば、ＣＰＵ、ＲＡＭ、ＲＯＭ、ハードディスク等の外部記憶装置、ＬＡＮカード等の通信装置をバスで接続した公知のノイマン型コンピュータに所定のプログラムを実行させることにより構成される。この場合、メモリ４１及び一時メモリ５１は、レジスタ、ＲＡＭ、外部記憶装置等又はそれらが複合された記憶領域に相当する。これらのメモリ４１及び一時メモリ５１に格納されるデータについては後述する。また、カウンタ４４，４５、探索値生成部４６、比較部４７及び制御部５０は、所定のプログラムが読み込まれたＣＰＵに相当する。さらに、入力部４２及び出力部４９は、所定のプログラムが読み込まれたＣＰＵの制御によって駆動する通信装置に相当する。また、書き込み部４３及び抽出部４８は、所定のプログラムが読み込まれたＣＰＵの制御のもとメモリ４１に対するデータの読書きを行うハードウェアに相当する。

また、サーバ装置４０は、制御部５０の制御のもと各処理を実行する。また、明示しない限り、各データは、適宜、逐一一時メモリ５１に格納され、各処理に利用される。また、図４における矢印はデータの流れを示すが、制御部５０及び一時メモリ５１に入出力するデータの流れの記載は省略してある。
＜リーダ装置６０の構成＞
リーダ装置６０は、例えば、ＣＰＵ、ＲＡＭ、ＲＯＭ、ハードディスク等の外部記憶装置、タグ装置２０と信号の無線通信を行う通信装置、ＬＡＮカード等の通信装置をバスで接続した公知のノイマン型コンピュータに所定のプログラムを実行させることにより構成される。

＜ライタ装置７０の構成＞
ライタ装置７０は、例えば、ＣＰＵ、ＲＡＭ、ＲＯＭ、ハードディスク等の外部記憶装置、タグ装置２０と信号の無線通信を行う通信装置、ＬＡＮカード等の通信装置をバスで接続した公知のノイマン型コンピュータに所定のプログラムを実行させることにより構成される。
＜前処置＞
次に、本形態のタグ通信システム１を作動させるための前処理について説明する。

［管理サーバ装置１０に対する前処理］
まず、各タグ装置２０に対応する識別子ｉｄ_ｍ（m∈[0,k-1])を秘密値テーブル１００のカラム１０１のデータとし、管理サーバ装置１０のメモリ１１の記憶部１１ａに格納する。なお、[0,k-1]は、０以上ｋ−１以下の整数の集合を意味する。次に、管理サーバ装置１０の乱数生成部１２が、発生させた擬似乱数を用い、各ｍに対して秘密値ｓ_{ｃｈａｉｎ，ｍ}（「第２秘密値」に相当）と秘密値ｔ_{ｔｒｅｅ，ｍ}（「第１秘密値」に相当）とを生成し、それらをそれぞれ秘密値テーブル１００のカラム１０２，１０３のデータとして識別子ｉｄ_ｍに対応付け、管理サーバ装置１０のメモリ１１の記憶部１１ａに格納する。なお、秘密値ｓ_{ｃｈａｉｎ，ｍ}，ｔ_{ｔｒｅｅ，ｍ}は、２進数Ｌビットで表記される（s_chain,m,t_tree,m∈{0,1}^L）。

また、一方向性関数である２つのハッシュ関数Ｆ_０，Ｆ_１を管理サーバ装置１０のメモリ１１の記憶部１１ｄに格納する。ハッシュ関数Ｆ_０，Ｆ_１は、｛０，１｝^Ｌ→｛０，１｝^Ｌの一方向性写像であり、例えば、ＳＨＡ−１等を例示できる。
さらに、一方向性関数を特定するための情報をノードとし、兄弟ノードに対応する一方向性関数が相互に異なり、親ノードに対応する一方向性関数と所定の一方向性関数との合成写像が子ノードに対応する一方向性関数となる木構造データ１１０を、管理サーバ装置１０のメモリ１１の記憶部１１ｂに格納する。このような木構造データ１１０の構成には制限はないが、本形態の例では、各ノードに以下のような文字列を対応させた深さｄの二分木データを木構造データ１１０とする。

(a)ルートノードは、空の文字列φ∈{0,1}⁰である。
(b)深さｄ’(d'∈[1,d])のノードは、２進数ｄ’ビットで表記される文字列ω∈{0,1}^d'である。
(c)深さｄ’のノードが文字列ω∈{0,1}^d'であるとき、その左の子ノードはω|0∈{0,1}^d'+1であり、右の子ノードはω|1∈{0,1}^d'+1である。なお、ω|0は、文字列ωと０とのビット結合を意味する。
(d)リーフノードの文字列ω∈{0,1}^dが整数ｉに対応する。

(e)各ノードの文字列ωにハッシュ関数Ｆ_ωが対応する。なお、ハッシュ関数Ｆ_ωは、２進表記された文字列ωの各ビットに対応するハッシュ関数Ｆ_０，Ｆ_１（ビット「０」にはハッシュ関数Ｆ_０が対応し、ビット「１」にはハッシュ関数Ｆ_１が対応する）の合成写像である。なお、この合成写像は、文字列ωの最上位ビットから最下位ビットに向かう順序で対応するハッシュ関数を作用させる写像である。例えば、ω=ab…z（a,b,…,z∈{0,1}）である場合、ハッシュ関数Ｆ_ωは、合成写像F_ω=F_z…F_bF_aとなる。

図５は、このような木構造データ１１０を例示した図である。なお、図５は、ｄ＝３の場合の例である。図５の例の木構造データ１１０は、ノード１１２ａ〜１１２ｐで構成され、各ノード１１２ａ〜１１２ｐは、上述の(a)から(d)の条件を満たしている。また、図６は、図５に例示した木構造データ１１０の各ノード１１２ａ〜１１２ｐに対応するハッシュ関数Ｆ_ωをノード１２２ａ〜１２２ｐとした木構造データである一方向性関数木データ１２０を示した図である。なお、各ノード１２２ａ〜１２２ｐは、上述の(e)の条件を満たしている。また、木構造データ１１０の記憶部１１ｂへの実装方法にも特に制限はないが、本形態では、各ノードに子ノードのポインタのリストを対応付けたテーブルを木構造データ１１０とする。この場合、図２に例示するように、木構造データ１１０は、各ノードに対応するポインタ「ｐ」を示すカラム１１１と、各ノードに対応する文字列「ω（又はφ）」を示すカラム１１２と、各ノードの子ノードに対応するポインタ「ｐ_１」「ｐ_２」をそれぞれ示すカラム１１３，１１４とからなるテーブルとなる。

［タグ装置２０に対する前処理］
タグ装置２０に対する前処理として、各タグ装置２０のメモリ２１の記憶部２１ｃに上述のハッシュ関数Ｆ_０，Ｆ_１を格納しておく。また、通信情報生成部２２及び更新部２４が、それぞれ一方向性関数であるハッシュ関数Ｈ，Ｇを利用可能なようにしておく。そのために、例えば、通信情報生成部２２及び更新部２４を実現するプログラムにハッシュ関数Ｈ，Ｇを組み込んでおいてもよいし、メモリ２１の図示していない領域にハッシュ関数Ｈ，Ｇを格納しておいてもよい。なお、ハッシュ関数Ｈ，Ｇは、｛０，１｝^＊→｛０，１｝^Ｌの一方向性写像であり、例えば、ＳＨＡ−１等を例示できる。なお、｛０，１｝^＊は任意のビット長の２進数ビットを示す。また、カウント初期化部２８が、上述の木構造データ１１０の深さを示す値ｄを利用可能としておく。そのために、例えば、カウント初期化部２８を実現するプログラムに値ｄを組み込んでおいてもよいし、メモリ２１の図示していない領域に値ｄを格納しておいてもよい。

［サーバ装置４０に対する前処理］
サーバ装置４０に対する前処理として、サーバ装置４０のメモリ４１の記憶部４１ｂに上述のハッシュ関数Ｆ_０，Ｆ_１を格納しておく。また、探索値生成部４６が一方向性関数であるハッシュ関数Ｈ，Ｇを利用可能なようにしておく。また、カウンタ４５が、上述の木構造データ１１０の深さを示す値ｄを利用可能としておく。
＜権限付与処理＞
次に、管理サーバ装置１０が行う権限付与処理について説明する。本形態では、通信情報の生成権限を付与するための権限情報を各タグ装置２０に与え、通信情報の探索権限を付与するための権限情報をサーバ装置４０に与える。

［通信情報の生成権限付与処理］
図７は、第１の実施の形態における通信情報の生成権限付与処理を説明するためのフローチャートである。以下、この図を用いて本形態における通信情報の生成権限付与処理を説明する。
まず、ノード選択部１３が、メモリ１１の記憶部１１ｂに格納された木構造データ１１０からノードω（「ω_Ｔ」と表記する）を選択し、これを記憶部１１ｃに格納する（ステップＳ１）。なお、この選択は、例えば、入力値に基づいて行う。例えば、管理サーバ装置１０の管理者が、通信情報の生成権限を付与しようとする範囲の整数ｉに対応するリーフノードの先祖ノードを特定し、このノードを特定するため情報を入力部（図示しない）から入力し、ノード選択部１３が、この入力情報に対応するノードをノードω_Ｔとして選択する。なお、別の形態として、このノードω_Ｔの選択を予め決定されている順序に従って行うこととしてもよい。また、タグ装置２０ごとにノードω_Ｔが異なっていてもよい。

次に、一方向性関数抽出部１４が、記憶部１１ｃから上述のノードω_Ｔを読み込み、その値に基づき、記憶部１１ｄからハッシュ関数Ｆ_０，Ｆ_１を読み込み、読み込んだハッシュ関数Ｆ_０，Ｆ_１を合成することにより、ノードω_Ｔに対応するハッシュ関数Ｆ_ωＴ（「一方向性関数」に相当）を抽出する。なお、ハッシュ関数Ｆ_ωＴの下付添え字のωＴは、ω_Ｔを意味する。なお、ハッシュ関数Ｆ_ωＴの構成は、上述の(e)に示した通りであり、生成されたハッシュ関数Ｆ_ωＴは、記憶部１１ｅに格納される（ステップＳ２）。

次に、制御部１８が、変数ｍに０を代入し、この変数ｍを一時メモリ１９に格納する（ステップＳ３）。次に、一方向性関数演算部１５が、一時メモリ１９から変数ｍを読み込み、記憶部１１ａの秘密値テーブル１００から、秘密値ｔ_{ｔｒｅｅ，ｍ}を読み込み、一方向性関数値t_ωT,m=F_ωT(t_tree,m)を算出し、これを記憶部１１ｆに格納する（ステップＳ４）。なお、F_ωT(T_tree,m)は、ハッシュ関数Ｆ_ωＴの入力値をｔ_{ｔｒｅｅ，ｍ}とし、ｔ_{ｔｒｅｅ，ｍ}にハッシュ関数Ｆ_ωＴを作用させ、その演算結果を求める処理を意味する。次に、権限情報生成部１６が、一時メモリ１９から変数ｍを読み込み、記憶部１１ａの秘密値テーブル１００から秘密値ｓ_{ｃｈａｉｎ，ｍ}を抽出し、記憶部１１ｃからノードω_Ｔを読み込み、記憶部１１ｆから一方向性関数値ｔ_ωＴ，ｍを読み込む。そして、権限情報生成部１６は、秘密値s_0,m=s_chain,mとして、生成権限情報k_T,m=(s_0,m,t_ωT,m,ω_T)を生成し、この生成権限情報ｋ_Ｔ，ｍを記憶部１１ｇに格納する（ステップＳ５）。なお、(α，β，γ）は、αとβとγのビット列を具備するビット列を意味する。

その後、制御部１８が、一時メモリ１９に格納された変数ｍがm=k-1を満たすか否かを判断する（ステップＳ６）。ここで、m=k-1を満たさないと判断された場合、制御部１８は、変数ｍの値に１を加算した値を新たな変数ｍの値とし、この変数ｍを一時メモリ１９に格納し（ステップＳ７）、処理をステップＳ４に戻す。一方、m=k-1を満たすと判断された場合、権限情報出力部１７は、記憶部１１ｇに格納されている各生成権限情報k_T,m(m∈[0,k-1])を、ネットワーク８０を通じてライタ装置７０に送信する。ライタ装置７０は、各生成権限情報k_T,mを各識別子id_mに対応するタグ装置２０に対して出力する。各タグ装置２０は、入力部２６において、自らの識別子id_mに対応する生成権限情報k_T,mを受信する。各タグ装置２０の書き込み部２７は、受信された生成権限情報k_T,m=(s_0,m,t_ωT,m,ω_T)の秘密値ｓ_０，ｍをメモリ２１の記憶部２１ａに格納し、一方向性関数値t_ωT,m及びノードω_Ｔを記憶部２１ｂに格納する。また、カウント初期化部２８は、記憶部２１ｂに格納されたノードω_Ｔを上位桁ビットとし、その下位桁ビットを０ビット（或いは０ビット列）とした合計ｄビットの初期のカウント値ｉ=ω_Ｔ|0...0（２進表記）を生成し、この初期のカウント値ｉを記憶部２１ｄに格納する。例えば、図５の木構造データ１１０において、ω_Ｔ=1である場合（ノード１１２ｊ／d=3）、初期のカウント値ｉは、ｉ=ω_Ｔ|0...0=100（２進表記）となり、１０進表記ではi=4となる。また、更新部２４は、記憶部２１ａに格納された秘密値ｓ_０，ｍにハッシュ関数Ｇをｉ回作用させた値を秘密値ｓ_ｉ，ｍとして記憶部２１ａに格納する（ステップＳ８）。

［通信情報の探索権限付与処理］
図８は、第１の実施の形態における通信情報の探索権限付与処理を説明するためのフローチャートである。以下、この図を用いて本形態における通信情報の探索権限付与処理を説明する。
まず、ノード選択部１３が、メモリ１１の記憶部１１ｂに格納された木構造データ１１０からノードω（「ω_Ｓ」と表記する）を選択し、これを記憶部１１ｃに格納する（ステップＳ１１）。なお、この選択は、例えば、入力値に基づいて行う。例えば、管理サーバ装置１０の管理者が、通信情報の探索権限を付与しようとする範囲の整数ｉに対応するリーフノードの先祖ノードを特定し、このノードを特定するため情報を入力部（図示しない）から入力し、ノード選択部１３が、この入力情報に対応するノードをノードω_Ｓとして選択する。なお、別の形態として、このノードω_Ｓの選択を予め決定されている順序に従って行うこととしてもよい。また、タグ装置２０ごとにノードω_Ｓが異なっていてもよい。

次に、一方向性関数抽出部１４が、記憶部１１ｃから上述のノードω_Ｓを読み込み、その値に基づき、記憶部１１ｄからハッシュ関数Ｆ_０，Ｆ_１を読み込み、読み込んだハッシュ関数Ｆ_０，Ｆ_１を合成することにより、ノードω_Ｓに対応するハッシュ関数Ｆ_ωＳ（「一方向性関数」に相当）を抽出する。なお、ハッシュ関数Ｆ_ωＳの下付添え字のωＳは、ω_Ｓを意味する。なお、ハッシュ関数Ｆ_ωＳの構成は、上述の(e)に示した通りであり、生成されたハッシュ関数Ｆ_ωＳは、記憶部１１ｅに格納される（ステップＳ１２）。

次に、制御部１８が、変数ｍに０を代入し、この変数ｍを一時メモリ１９に格納する（ステップＳ１３）。次に、一方向性関数演算部１５が、一時メモリ１９から変数ｍを読み込み、記憶部１１ａの秘密値テーブル１００から、秘密値ｔ_{ｔｒｅｅ，ｍ}を読み込み、一方向性関数値t_ωS,m=F_ωS(T_tree,m)を算出し、これを記憶部１１ｆに格納する（ステップＳ１４）。次に、権限情報生成部１６が、一時メモリ１９から変数ｍを読み込み、記憶部１１ａの秘密値テーブル１００から識別子ｉｄ_ｍと秘密値ｓ_{ｃｈａｉｎ，ｍ}を抽出し、記憶部１１ｃからノードω_Ｓを読み込み、記憶部１１ｆから一方向性関数値ｔ_ωＳ，ｍを読み込む。そして、権限情報生成部１６は、秘密値s_0,m=s_chain,mとして、探索権限情報k_S,m=(id_m,s_0,m,t_ωS,m,ω_S)を生成し、この探索権限情報ｋ_Ｓ，ｍを記憶部１１ｇに格納する（ステップＳ１５）。

その後、制御部１８が、一時メモリ１９に格納された変数ｍがm=k-1を満たすか否かを判断する（ステップＳ１６）。ここで、m=k-1を満たさないと判断された場合、制御部１８は、変数ｍの値に１を加算した値を新たな変数ｍの値とし、この変数ｍを一時メモリ１９に格納し（ステップＳ１７）、処理をステップＳ１４に戻す。一方、m=k-1を満たすと判断された場合、権限情報出力部１７は、記憶部１１ｇに格納されている各探索権限情報k_S,m(m∈[0,k-1])を、ネットワーク８０を通じてサーバ装置４０に送信する。サーバ装置４０は、入力部４２において、これらの各探索権限情報k_S,mを受信する。サーバ装置４０の書き込み部４３は、受信された各探索権限情報k_S,m=(id_m,s_0,m,t_ωS,m,ω_S)の識別子ｉｄ_ｍをカラム２０１のデータとし、秘密値ｓ_０，ｍをカラム２０２のデータとし、一方向性関数値t_ωS,mをカラム２０３のデータとし、ノードω_Ｓカラム２０４のデータとしたテーブルである権限情報２００をメモリ４１の記憶部４１ａに格納する（ステップＳ１８）。

＜通信処理＞
以上のような処理の後行われる通信処理について説明する。この処理では、タグ装置２０が、上述の生成権限情報k_T,mを用いて通信情報ａ_ｉ，ｍを生成・出力し、サーバ装置４０が、受信した通信情報ａ_ｉ，ｍに対応する識別子ｉｄ_ｍを探索する。なお、サーバ装置４０は、受信した通信情報ａ_ｉ，ｍがどのタグ装置２０から出力されたものなのかを知らない。
図９は、第１の実施の形態の通信処理を説明するためのフローチャートである。なお、図９における実線の矢印は、各装置内での処理の時間的な流れを示し、破線の矢印は装置間の処理の時間的な流れを示す。以下、この図を用いて、本形態の通信処理を説明する。

［タグ装置２０の処理］
タグ装置２０の処理は、例えば、タグ装置２０がリーダ装置６０の通信圏内に入り、リーダ装置６０から送信されたトリガ信号を受信することにより開始される。このようなトリガがあった場合、タグ装置２０の通信情報生成部２２は、メモリ２１の記憶部２１ａから秘密値ｓ_ｉ，ｍを読み込み、記憶部２１ｂから一方向性関数値t_ωT,m及びノードω_Ｔを読み込み、記憶部２１ｃからハッシュ関数Ｆ_０，Ｆ_１を読み込み、記憶部２１ｄからカウント値ｉを読み込む。そして、通信情報生成部２２は、通信情報a_i,m=H(s_i,m,F_ω’(t_ωT,m))を生成する（ステップＳ２１）。なお、ステップＳ２１でのω’はi=ω_T|ω’を満たす値である。すなわち、２進表記されたカウント値ｉの上位ビットω_Ｔを除いたビットがω’である。そして、t_ωT,m=F_ωT(t_tree,m)であるから、F_ω’(t_ωT,m)はF_ω’(t_ωT,m)=F_ω’(F_ωT(t_tree,m))=F_i(t_tree,m)を満たし、F_iは、木構造データ１１０のリーフノードに対応するハッシュ関数である。

このように生成された通信情報a_i,mは、通信情報出力部２３から出力される（ステップＳ２２）。
次に、タグ装置２０の更新部２４は、メモリ２１の記憶部２１ａから秘密値ｓ_ｉ，ｍを読み込み、秘密値ｓ_ｉ，ｍにハッシュ関数Ｇを施した値Ｇ（ｓ_ｉ，ｍ）を新たな秘密値ｓ_{ｉ＋１，ｍ}とし、これによって記憶部２１ａを上書きし、秘密値を更新する（ステップＳ２３）。なお、ここでの上書きとは、記憶部２１ａに格納されていた秘密値を消去（復元困難なデータに変換することも含む）し、記憶部２１ａに新たな秘密値を格納することを意味する。そして、カウンタ２５が、記憶部２１ｄからカウント値ｉを読み込み、ｉ＋１を新たなカウント値ｉとし、この新たなカウント値ｉを記憶部２１ｄに格納する（ステップＳ２４）。これにより、記憶部２１ｄに格納されたカウント値ｉが更新される。
その後、タグ装置２０は、所定のトリガがあるたびに、上述のステップＳ２１からＳ２４の処理を実行する。

［リーダ装置６０の処理］
リーダ装置６０は、上述のようにタグ装置２０から出力された通信情報ａ_ｉ，ｍ（ステップＳ２２）を受信し（ステップＳ２５）、これを、ネットワーク８０を通じてサーバ装置４０に送信する（ステップＳ２６）。

［サーバ装置４０の処理］
サーバ装置４０は、入力部４２において、リーダ装置６０から送信された通信情報ａ_ｉ，ｍを受信し、書き込み部４３において、この通信情報ａ_ｉ，ｍを記憶部４１ｃに格納する（ステップＳ２７）。次に、カウンタ４４は、カウント値ｐを０にし、このカウント値ｐを一時メモリ５１に格納する（ステップＳ２８）。また、カウンタ４５は、記憶部４１ａの権限情報２００のカラム２０４からノードω_Ｓを抽出し、このノードω_Ｓを上位桁ビットとし、その下位桁ビットを０ビット（或いは０ビット列）とした合計ｄビットの初期のカウント値ｊ=ω_Ｓ|0...0（２進表記）を生成し、この初期のカウント値ｊを一時メモリ５１に格納する（ステップＳ２９）。次に、探索値生成部４６は、一時メモリ５１からカウント値ｐ，ｊを読み込み、記憶部４１ａに格納された権限情報２００のカラム２０１〜２０４から識別子ｉｄ_ｐと秘密値ｓ_０，ｐと一方向性関数値t_ωS,pとノードω_Ｓとをそれぞれ読み込み、記憶部４１ｂからハッシュ関数Ｆ_０，Ｆ_１を読み込む。そして、探索値生成部４６は、探索値a_j,p’=H(G^j(s_0,p), F_ω’’(t_ωS,p))を生成する（ステップＳ３０）。なお、ステップＳ３０でのω’’は、j=ω_s|ω’’を満たす値である。すなわち、２進表記されたカウント値ｊの上位ビットω_Ｓを除いたビットがω’’である。このように生成された探索値ａ_ｊ，ｐ’は、一時メモリ５１に格納される。

次に、比較部４７は、記憶部４１から通信情報ａ_ｉ，ｍを読み込み、一時メモリ５１から探索値ａ_ｊ，ｐ’を読み込み、通信情報ａ_ｉ，ｍと探索値ａ_ｊ，ｐ’とが等しいか否かを判断する（ステップＳ３１）。ここで、a_i,m=a_j,p’であった場合、抽出部４８は、一時メモリ５１からカウント値ｐを読み込み、記憶部４１ａの権限情報２００のカラム２０１から識別子ｉｄ_ｐ（＝ｉｄ_ｍである）を抽出し、これを出力部４９から出力し（ステップＳ３６）、処理を終了する。

一方、a_i,m=a_j,p’でなかった場合、制御部５０は、一時メモリ５１に格納されているカウント値ｊがj=2^d-1であるか否かを判断し（ステップＳ３２）、j=2^d-1でなければ、カウンタ４５がカウント値ｊに１を加算した値を新たなカウント値ｊとし、このカウント値ｊを一時メモリ５１に格納し、処理をステップＳ３０に戻す（ステップＳ３３）。一方、カウント値ｊがj=2^d-1であれば、制御部５０は、一時メモリ５１に格納されているカウント値ｐがp=k-1であるか否かを判断する（ステップＳ３４）。ここで、p=k-1でなければ、カウンタ４４がカウント値ｐに１を加算した値を新たなカウント値ｐとし、このカウント値ｐを一時メモリ５１に格納し、処理をステップＳ２９に戻す（ステップＳ３５）。一方、p=k-1であれば、出力部４９が探索失敗を示すエラー出力を行い（ステップＳ３７）、処理を終了する。

＜本形態の特徴＞
以下に本形態の特徴を示す。
［通信情報の生成権限の制限］
上述したように、本形態のタグ装置２０には、管理サーバ装置１０から生成権限情報k_T,m=(s_0,m,t_ωT,m,ω_T)が付与され、タグ装置２０は、これを用いて通信情報a_i,m=H(s_i,m, F_ω’(t_ωT,m))を生成する。
ここで、生成権限情報k_T,mが具備するt_ωT,mは、t_ωT,m=F_ωT(ｔ_tree,m)を満たす一方向性関数値であり、通常、t_ωT,mから秘密値ｔ_tree,mを求めることは困難である。よって、生成権限情報k_T,mが与えられたタグ装置２０が生成できるF_ω’(t_ωT,m)=F_ω’(F_ωT(ｔ_tree,m))は、秘密値ｔ_tree,mにハッシュ関数F_ω’,F_ωTの合成写像を施した値のみとなる。図１０は、このことを説明するための一方向性関数木データ１２０を示した図である。例えば、ハッシュ関数F_ωTがノード１２２ｊに対応するとする。この場合、ハッシュ関数F_ω’,F_ωTの合成写像は、ノード１２２ｋ〜１２２ｐに対応するハッシュ関数のみであり、タグ装置２０は、秘密値ｔ_tree,mにノード１２２ｋ〜１２２ｐに対応するハッシュ関数を施した値しか求めることができない。すなわち、この範囲に通信情報a_i,mの生成権限を制限することができる。

そして、タグ装置２０の所有者が、このタグ装置２０に付与された生成権限情報k_T,m=(s_0,m,t_ωT,m,ω_T)を知ることができたとしても、その所有者が知り得る通信情報a_i,mの範囲、すなわち追跡範囲は、この生成権限の範囲に制限される。そのため、タグ装置２０の所有者が変更になった後に、旧所有者が追跡できる範囲もこの範囲に制限され、新所有者のプライバシを保護することが可能となる。
［通信情報の追跡権限の制限］
上述したように、本形態のサーバ装置４０には、管理サーバ装置１０から探索権限情報k_S,m=(id_m,s_0,m,t_ωS,m,ω_S)が付与され、これを用いて探索値a_j,p’=H(G^j(s_0,p),F_ω’’(t_ωS,p))を生成し、この探索値a_j,p’と通信情報a_i,mとを比較し、通信情報a_i,mに対応する識別子ｉｄ_ｍを探索する。

ここで、探索値a_j,p’が具備するt_ωS,pは、t_ωS,p=F_ωS(t_tree,p)を満たす一方向性関数値であり、通常、t_ωS,mから秘密値ｔ_tree,pを求めることは困難である。よって、探索権限情報k_S,mが与えられたサーバ装置４０が生成できるF_ω’’(t_ωS,p)=F_ω’’(F_ωS(t_tree,p))は、秘密値ｔ_tree,pにハッシュ関数F_ω’',F_ωＳの合成写像を施した値のみとなる。すなわち、この範囲で探索値a_j,p’の生成権限、すなわち通信情報a_i,mの探索権限を制限することができる。これを、図１０を用いて説明する。例えば、ハッシュ関数F_ωＳがノード１２２ｊに対応するとする。この場合、ハッシュ関数F_ω’’,F_ωＳの合成写像は、ノード１２２ｋ〜１２２ｐに対応するハッシュ関数のみであり、サーバ装置４０は、秘密値ｔ_tree,ｐにノード１２２ｋ〜１２２ｐに対応するハッシュ関数を施した値しか求めることができない。そして、前述のように、通信情報a_i,mの生成に用いられるF_ω’(t_ωT,m)は、秘密値t_tree,mに木構造データ１１０のリーフノードに対応するハッシュ関数を作用させた値なのである。よって、実質的には、サーバ装置４０には、ノード１２２ｌ,１２２ｍ,１２２ｏ,１２２ｐのハッシュ関数を用いて生成された通信情報a_i,mの探索権限のみが付与されることになる。

そして、サーバ装置４０の管理者が、このサーバ装置４０に付与された探索権限情報k_S,m=(id_m,s_0,m,t_ωS,m,ω_S)を知ることができたとしても、その管理者が知り得る探索値a_j,p’の範囲、すなわち追跡範囲は、この探索権限の範囲に制限される。そのため、サーバ装置４０の管理者が変更になった後に、旧管理者が追跡できる範囲もこの範囲に制限され、管理者変更後におけるタグ装置２０所有者のプライバシを保護することが可能となる。

［効率性］
タグ装置２０の演算処理を、主にハッシュ関数演算のみによって実現できるため、タグ装置２０に組み込む回路規模を小さくできる。これは、低価格が要求されるタグ装置２０に適している。また、上述のような木構造のノードに対応付けたハッシュ関数を用いて通信情報a_i,mを生成することとしたため、サーバ装置４０の探索時、サーバ装置４０が１つの探索値a_j,p’=H(G^j(s_0,p), F_ω’’(t_ωS,p))のF_ω’’(t_ωS,p)を求めるために必要なハッシュ関数Ｆ_０,Ｆ_１の回数はlog₂(n)回のみであり、サーバ装置４０の探索効率もよい。なお、ここでのｎは、タグ装置２０の最大応答回数である。

［第三者による追跡不可能性］
また、ハッシュ関数Ｈの識別不能性から、通信情報ａ_ｉ,ｍはランダムにみえる。よって、秘密情報であるｉｄ_ｍ，ｓ_ｉ，ｍ，ｔ_ωＴ，ｍを知らずに、２つの通信情報ａ_ｉ,ｍが同じタグ装置２０から出力されたかどうかを判定することはできない。
［フォワードセキュリティ］
さらに、ハッシュ関数Ｇの一方向性から、タグ装置２０がタンパーされるなどして秘密情報であるｓ_ｉ，ｍ等が漏洩しても、過去のｓ_{ｉ−ｑ，ｍ}が知られることはない。その結果、このような事態が生じても、過去の通信履歴を用い、タグ装置２０の過去の振る舞いが追跡されることもない。

〔第２の実施の形態〕
次に、本発明における第２の実施の形態を説明する。
本形態は、第１の実施の形態の変形例であり、第１の実施の形態と同様に制限された探索権限をサーバ装置に与え、制限のない通信情報の生成権限をタグ装置に与える形態である。以下、この詳細を説明する。なお、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
＜全体構成＞
管理サーバ装置１０が管理サーバ装置３１０に置換され、タグ装置２０がタグ装置３２０に置換される以外は、第１の実施の形態と同様である。

＜管理サーバ装置の構成＞
図１１は、第２の実施の形態における管理サーバ装置３１０の機能構成を示したブロック図である。なお、図１１において第１の実施の形態と共通する部分については図２と同じ符号を付した。
図１１に例示するように、管理サーバ装置３１０は、メモリ１１、乱数生成部１２、ノード選択部３１３、一方向性関数抽出部３１４、一方向性関数演算部３１５、権限情報生成部３１６、権限情報出力部１７、制御部１８及び一時メモリ１９を有している。
なお、第１の実施の形態と同様、管理サーバ装置３１０も、例えば、ＣＰＵ、ＲＡＭ、ＲＯＭ、ハードディスク等の外部記憶装置、ＬＡＮカード等の通信装置をバスで接続した公知のノイマン型コンピュータに所定のプログラムを実行させることにより構成される。この場合、ノード選択部３１３、一方向性関数抽出部３１４、一方向性関数演算部３１５及び権限情報生成部３１６は、所定のプログラムが読み込まれたＣＰＵに相当する。

また、管理サーバ装置３１０は、制御部１８の制御のもと各演算処理を実行する。また、明示しない限り、各データは、適宜、逐一一時メモリ１９に格納され、各処理に利用される。また、図１１における矢印はデータの流れを示すが、制御部１８及び一時メモリ１９に入出力するデータの流れの記載は省略してある。
＜タグ装置３２０の構成＞
図１２は、第２の実施の形態におけるタグ装置３２０の機能構成を示したブロック図である。なお、図１２において第１の実施の形態と共通する部分については図３と同じ符号を付した。

図１２に例示するように、タグ装置３２０は、メモリ２１、通信情報生成部３２２、通信情報出力部２３、更新部２４、カウンタ２５、入力部２６、書き込み部３２７、一時メモリ２９及び制御部３０を有している。
なお、通信情報生成部３２２、例えば、各処理を実行する集積回路又は所定のプログラムが読み込まれたＣＰＵである。また、書き込み部３２７は、制御部３０の制御のもとメモリ２１に対してデータを読み書きするハードウェアである。
また、タグ装置３２０は、制御部３０の制御のもと各処理を実行する。また、明示しない限り、各データは、適宜、逐一一時メモリ２９に格納され、各処理に利用される。また、図３における矢印はデータの流れを示すが、制御部３０及び一時メモリ２９に入出力するデータの流れの記載は省略してある。

＜前処置＞
次に、本形態のタグ通信システムを作動させるための前処理について説明する。
［管理サーバ装置３１０に対する前処理］
第１の実施の形態における管理サーバ装置１０に対する前処理と同じである。
［タグ装置３２０に対する前処理］
タグ装置２０に対する前処理として、各タグ装置２０のメモリ２１の記憶部２１ｃに上述のハッシュ関数Ｆ_０，Ｆ_１を格納しておく。また、通信情報生成部２２及び更新部２４が、それぞれ一方向性関数であるハッシュ関数Ｈ，Ｇを利用可能なようにしておく。

［サーバ装置４０に対する前処理］
第１の実施の形態と同じである。
＜権限付与処理＞
次に、管理サーバ装置３１０が行う権限付与処理について説明する。本形態では、通信情報の生成権限を付与するための制限のない権限情報を各タグ装置３２０に与え、通信情報の探索権限を付与するための権限情報をサーバ装置４０に与える。
［通信情報の生成権限付与処理］
権限情報生成部３１６が、各m∈[0,k-1]について、メモリ１１の記憶部１１ａの秘密値テーブル１００から秘密値ｓ_{ｃｈａｉｎ，ｍ},ｔ_{ｔｒｅｅ，ｍ}を抽出し、秘密値s_0,m=s_chain,mとして、生成権限情報k_T,m=(s_0,m,t_tree,m)を生成し、この生成権限情報ｋ_Ｔ，ｍを記憶部１１ｇに格納する。

その後、権限情報出力部１７は、記憶部１１ｇに格納されている各生成権限情報k_T,m
(m∈[0,k-1])を、ネットワーク８０を通じてライタ装置７０に送信する。ライタ装置７０は、各生成権限情報k_T,mを各識別子id_mに対応するタグ装置３２０に対して出力する。各タグ装置３２０は、入力部２６において、自らの識別子id_mに対応する生成権限情報k_T,mを受信する。各タグ装置３２０の書き込み部３２７は、受信された生成権限情報k_T,m=s_0,m,t_tree,m)の秘密値ｓ_０，ｍをメモリ２１の記憶部２１ａに格納し、秘密値ｔ_{ｔｒｅｅ,ｍ}を記憶部２１ｂに格納する。また、カウンタ２５は、カウント値ｉを０とし、このカウント値ｉを記憶部２１ｄに格納する。

［通信情報の探索権限付与処理］
通信情報の探索権限付与処理は、ノード選択部１３、一方向性関数抽出部１４、一方向性関数演算部１５及び権限情報生成部１６の処理を、ノード選択部３１３、一方向性関数抽出部３１４、一方向性関数演算部３１５及び権限情報生成部３１６がそれぞれ実行する以外は、第１の実施の形態と同じである（図８）。

＜通信処理＞
以上のような処理の後行われる通信処理について説明する。
図１３は、第２の実施の形態の通信処理を説明するためのフローチャートである。なお、図１３における実線の矢印は、各装置内での処理の時間的な流れを示し、破線の矢印は装置間の処理の時間的な流れを示す。以下、この図を用いて、本形態の通信処理を説明する。なお、以下では、ｉ回目にタグ装置３２０が通信情報を出力した際の処理を説明する。

［タグ装置３２０の処理］
第１の実施の形態と同様なトリガがあった場合、タグ装置３２０の通信情報生成部３２２は、メモリ２１の記憶部２１ａから秘密値ｓ_ｉ，ｍを読み込み、記憶部２１ｂから秘密値ｔ_{ｔｒｅｅ,ｍ}を読み込み、記憶部２１ｃからハッシュ関数Ｆ_０，Ｆ_１を読み込み、記憶部２１ｄからカウント値ｉを読み込む。そして、通信情報生成部３２２は、通信情報a_i,m=H(s_i,m, F_ｉ(t_tree,m))を生成する（ステップＳ４１）。
このように生成された通信情報a_i,mは、通信情報出力部２３から出力される（ステップＳ４２）。

次に、タグ装置２０の更新部２４は、メモリ２１の記憶部２１ａから秘密値ｓ_ｉ，ｍを読み込み、秘密値ｓ_ｉ，ｍにハッシュ関数Ｇを施した値Ｇ（ｓ_ｉ，ｍ）を新たな秘密値ｓ_{ｉ＋１，ｍ}とし、これによって記憶部２１ａを上書きし、秘密値を更新する（ステップＳ４３）。そして、カウンタ２５が、記憶部２１ｄからカウント値ｉを読み込み、ｉ＋１を新たなカウント値ｉとし、この新たなカウント値ｉを記憶部２１ｄに格納する（ステップＳ４４）。これにより、記憶部２１ｄに格納されたカウント値ｉが更新される。

その後、タグ装置２０は、所定のトリガがあるたびに、上述のステップＳ４１からＳ４４の処理を実行する。
その後のリーダ装置・サーバ装置の処理（ステップＳ４５〜Ｓ５７）は、第１の実施の形態のステップＳ２５〜Ｓ３７と同じである。
＜本形態の特徴＞
第１の実施の形態と同様にサーバ装置４０の管理者の追跡権限を制限でき、プライバシの保護を実現できる（［通信情報の追跡権限の制限］）。その他、第１の実施の形態と同様の［効率性］［第三者による追跡不可能性］［フォワードセキュリティ］を実現できる。

〔第３の実施の形態〕
次に、本発明における第３の実施の形態を説明する。
本形態は、第１の実施の形態の変形例であり、第１の実施の形態と同様に制限された通信情報の生成権限をタグ装置に与え、制限のない探索権限をサーバ装置に与える形態である。以下、この詳細を説明する。なお、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
＜全体構成＞
管理サーバ装置１０が管理サーバ装置４１０に置換され、サーバ装置４０がサーバ装置４４０に置換される以外は、第１の実施の形態と同様である。

＜管理サーバ装置４１０の構成＞
図１４は、第３の実施の形態における管理サーバ装置４１０の機能構成を示したブロック図である。なお、図１４において第１の実施の形態と共通する部分については図２と同じ符号を付した。
図１４に例示するように、管理サーバ装置４１０は、メモリ１１、乱数生成部１２、ノード選択部４１３、一方向性関数抽出部４１４、一方向性関数演算部４１５、権限情報生成部４１６、権限情報出力部１７、制御部１８及び一時メモリ１９を有している。

なお、第１の実施の形態と同様、管理サーバ装置４１０も、例えば、ＣＰＵ、ＲＡＭ、ＲＯＭ、ハードディスク等の外部記憶装置、ＬＡＮカード等の通信装置をバスで接続した公知のノイマン型コンピュータに所定のプログラムを実行させることにより構成される。この場合、ノード選択部４１３、一方向性関数抽出部４１４、一方向性関数演算部４１５及び権限情報生成部４１６は、所定のプログラムが読み込まれたＣＰＵに相当する。
また、管理サーバ装置４１０は、制御部１８の制御のもと各演算処理を実行する。また、明示しない限り、各データは、適宜、逐一一時メモリ１９に格納され、各処理に利用される。また、図１１における矢印はデータの流れを示すが、制御部１８及び一時メモリ１９に入出力するデータの流れの記載は省略してある。

＜サーバ装置４４０の構成＞
図１５は、第３の実施の形態におけるサーバ装置４４０の機能構成を示したブロック図である。なお、図１５において第１の実施の形態と共通する部分については図４と同じ符号を付した。
図１５に例示するように、サーバ装置４４０は、メモリ４１、入力部４２、書き込み部４４３、カウンタ４４，４４５、探索値生成部４４６、比較部４７、抽出部４８、出力部４９、制御部５０及び一時メモリ５１を有している。

なお、サーバ装置４４０は、例えば、ＣＰＵ、ＲＡＭ、ＲＯＭ、ハードディスク等の外部記憶装置、ＬＡＮカード等の通信装置をバスで接続した公知のノイマン型コンピュータに所定のプログラムを実行させることにより構成される。この場合、書き込み部４４３は、所定のプログラムが読み込まれたＣＰＵの制御のもとメモリ４１に対するデータの読書きを行うハードウェアに相当し、カウンタ４４５及び探索値生成部４４６は、所定のプログラムが読み込まれたＣＰＵに相当する。
また、サーバ装置４４０は、制御部５０の制御のもと各処理を実行する。また、明示しない限り、各データは、適宜、逐一一時メモリ５１に格納され、各処理に利用される。また、図１５における矢印はデータの流れを示すが、制御部５０及び一時メモリ５１に入出力するデータの流れの記載は省略してある。

＜前処置＞
次に、本形態のタグ通信システムを作動させるための前処理について説明する。
［管理サーバ装置４１０に対する前処理］
第１の実施の形態における管理サーバ装置１０に対する前処理と同じである。
［タグ装置２０に対する前処理］
第１の実施の形態と同じである。
［サーバ装置４４０に対する前処理］
サーバ装置４４０に対する前処理として、サーバ装置４４０のメモリ４１の記憶部４１ｂに上述のハッシュ関数Ｆ_０，Ｆ_１を格納しておく。また、探索値生成部４４６が一方向性関数であるハッシュ関数Ｈ，Ｇを利用可能なようにしておく。また、カウンタ４４５が、上述の木構造データ１１０の深さを示す値ｄを利用可能としておく。

＜権限付与処理＞
次に、管理サーバ装置４１０が行う権限付与処理について説明する。本形態では、第１の実施の形態と同様に制限された通信情報の生成権限をタグ装置２０に与え、制限のない探索権限をサーバ装置４４０に与える。
［通信情報の生成権限付与処理］
通信情報の探索権限付与処理は、ノード選択部１３、一方向性関数抽出部１４、一方向性関数演算部１５及び権限情報生成部１６の処理を、ノード選択部４１３、一方向性関数抽出部４１４、一方向性関数演算部４１５及び権限情報生成部４１６がそれぞれ実行する以外は、第１の実施の形態と同じである（図７）。

［通信情報の探索権限付与処理］
権限情報生成部４１６が、各m∈[0,k-1]について、メモリ１１の記憶部１１ａの秘密値テーブル１００から識別子ｉｄ_ｍと秘密値ｓ_{ｃｈａｉｎ，ｍ},ｔ_{ｔｒｅｅ，ｍ}を抽出し、秘密値s_0,m=s_chain,mとして、探索権限情報k_S,m=(id_m,s_0,m,t_tree,m)を生成し、この探索権限情報ｋ_Ｓ，ｍを記憶部１１ｇに格納する。
その後、権限情報出力部１７は、記憶部１１ｇに格納されている各探索権限情報ｋ_Ｓ，ｍ(m∈[0,k-1])を、ネットワーク８０を通じてサーバ装置４４０に送信する。サーバ装置４４０は、入力部４２において、これらの各探索権限情報k_S,mを受信する。サーバ装置４０の書き込み部４４３は、受信された各探索権限情報k_S,m=(id_m,s_0,m,t_tree,m)の識別子ｉｄ_ｍをカラム５０１のデータとし、秘密値ｓ_０，ｍをカラム５０２のデータとし、秘密値ｔ_{ｔｒｅｅ,ｍ}をカラム５０３のデータとしたテーブルである権限情報５００をメモリ４１の記憶部４１ａに格納する。

＜通信処理＞
以上のような処理の後行われる通信処理について説明する。
図１６は、第３の実施の形態の通信処理を説明するためのフローチャートである。なお、図１６における実線の矢印は、各装置内での処理の時間的な流れを示し、破線の矢印は装置間の処理の時間的な流れを示す。以下、この図を用いて、本形態の通信処理を説明する。
［タグ装置２０・リーダ装置６０の処理］
タグ装置２０・リーダ装置６０の処理（ステップＳ６１〜Ｓ６６）は、第１の実施の形態と同じである（ステップＳ２１〜Ｓ２６）。

［サーバ装置４４０の処理］
サーバ装置４０は、入力部４２において、リーダ装置６０から送信された通信情報ａ_ｉ，ｍを受信し、書き込み部４３において、この通信情報ａ_ｉ，ｍを記憶部４１ｃに格納する（ステップＳ６７）。次に、カウンタ４４は、カウント値ｐを０にし、このカウント値ｐを一時メモリ５１に格納する（ステップＳ６８）。また、カウンタ４４５は、カウント値ｊを０にし、このカウント値ｊを一時メモリ５１に格納する（ステップＳ６９）。次に、探索値生成部４４６は、一時メモリ５１からカウント値ｐ，ｊを読み込み、記憶部４１ａに格納された権限情報５００のカラム５０１〜２０３から識別子ｉｄ_ｐと秘密値ｓ_０，ｐ,ｔ_{ｔｒｅｅ,ｐ}とをそれぞれ読み込み、記憶部４１ｂからハッシュ関数Ｆ_０，Ｆ_１を読み込む。そして、探索値生成部４４６は、探索値a_j,p’=H(G^j(s_0,p), F_ｊ(t_{ｔｒｅｅ,p}))を生成する（ステップＳ７０）。のように生成された探索値ａ_ｊ，ｐ’は、一時メモリ５１に格納される。

次に、比較部４７は、記憶部４１から通信情報ａ_ｉ，ｍを読み込み、一時メモリ５１から探索値ａ_ｊ，ｐ’を読み込み、通信情報ａ_ｉ，ｍと探索値ａ_ｊ，ｐ’とが等しいか否かを判断する（ステップＳ７１）。ここで、a_i,m=a_j,p’であった場合、抽出部４８は、一時メモリ５１からカウント値ｐを読み込み、記憶部４１ａの権限情報５００のカラム５０１から識別子ｉｄ_ｐ（＝ｉｄ_ｍである）を抽出し、これを出力部４９から出力し（ステップＳ７６）、処理を終了する。

一方、a_i,m=a_j,p’でなかった場合、制御部５０は、一時メモリ５１に格納されているカウント値ｊがj=2^d-1であるか否かを判断し（ステップＳ７２）、j=2^d-1でなければ、カウンタ４５がカウント値ｊに１を加算した値を新たなカウント値ｊとし、このカウント値ｊを一時メモリ５１に格納し、処理をステップＳ７０に戻す（ステップＳ７３）。一方、カウント値ｊがj=2^d-1であれば、制御部５０は、一時メモリ５１に格納されているカウント値ｐがp=k-1であるか否かを判断する（ステップＳ７４）。ここで、p=k-1でなければ、カウンタ４４がカウント値ｐに１を加算した値を新たなカウント値ｐとし、このカウント値ｐを一時メモリ５１に格納し、処理をステップＳ６９に戻す（ステップＳ７５）。一方、p=k-1であれば、出力部４９が探索失敗を示すエラー出力を行い（ステップＳ７７）、処理を終了する。

＜本形態の特徴＞
第１の実施の形態と同様にサーバ装置２０の通信情報の生成権限を制限でき、その旧所有者の追跡権限を制限できる。その結果、プライバシの保護を実現できる（［通信情報の生成権限の制限］）。その他、第１の実施の形態と同様の［効率性］［第三者による追跡不可能性］［フォワードセキュリティ］を実現できる。

〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各形態では、リーダ装置を介してタグ装置とサーバ装置とが通信を行うこととしたが、リーダ装置がサーバ装置の機能を具備することとし、タグ装置とリーダ装置との間で通信処理を行う構成としてもよい。この場合、通信情報の探索権限は、サーバ装置ではなく、リーダ装置に付与されることになる。

また、上述の各実施の形態では、一方向性関数としてハッシュ関数を用いる場合を説明した。しかし、一方向性関数として逆像を求めることが困難な他の関数を用いてもよい。このような関数としては、例えば、ＡＥＳやCamellia等の共通鍵暗号関数を用いてもよい。この場合、一方向性関数の入力値に相当するのが平文となり、一方向性関数値に相当するのが暗号文となる。

また、上述の各実施の形態では、通信情報a_i,mの生成に秘密値ｓ_０，ｍのハッシュチェイン値ｓ_ｉ，ｍを用いることとしたが、ハッシュチェイン値ｓ_ｉ，ｍを用いることなく通信情報a_i,mを生成することとしてもよい。この場合、通信情報a_i,mは、a_i,m=H(F_ω’(t_ωT,m)),a_i,m=H(F_ｉ(t_tree,m))やa_i,m=F_ω’(t_ωT,m),a_i,m=F_ｉ(t_tree,m)等となり、探索値a_ｊ,ｐ'は、a_j,p'=H(F_ω’’(t_ωT,m))=H(F_j(t_tree,p))やa_j,p'=F_ω’’(t_ωT,p)=F_j(t_tree,p)等となる。

また、上述の各実施の形態では、秘密値ｓ_０，ｍのハッシュチェイン回数とt_tree,mに対するハッシュ関数Ｆ_０,Ｆ_１の作用回数とが同じｉであった。しかし、秘密値ｓ_０，ｍのハッシュチェイン回数とt_tree,mに対するハッシュ関数Ｆ_０,Ｆ_１の作用回数とを異なる値にしてもよい。

また、一方向性関数を特定するための情報をノードとし、兄弟ノードに対応する一方向性関数が相互に異なり、親ノードに対応する一方向性関数と所定の一方向性関数との合成写像が子ノードに対応する一方向性関数となるのであれば、木構造データ１１０は、上述のものに限定されない。例えば、木構造データ１１０の少なくとも一部のノードの子ノードが左右入れ替わっていてもよい。また、木構造データ１１０を２分木データではなく、多分木データとしてもよい。例えば、木構造データ１１０をｒ分木データとした場合、木構造データ１１０の各ノードに対応する文字列はｒ進表記された数値となり、上述の実施の形態では２つのハッシュ関数Ｆ_０,Ｆ_１を用いていたところを、ｒ個のハッシュ関数Ｆ_０,…,Ｆ_ｒ−１を用いることになる。この場合、木構造データ１１０に対応する一方向性関数木データ１２０の構成も変化する。

また、本形態では、前処理において、管理サーバ装置のメモリに木構造データ１１０を格納することとした。しかし、前処理で木構造データ１１０を生成するのではなく、木構造データ１１０の生成ルールのみをメモリに格納しておき、権限付与の際、この生成ルールに従って木構造データ１１０のノードを生成する構成としてもよい。その場合、必ずしも木構造データ１１０の全てのノードを生成する必要はない。

また、第１の実施の形態では、タグ装置２０に生成権限情報k_T,m=(s_0,m,t_ωT,m,ω_T)が付与され、タグ装置２０は、ノードω_Tを用いてカウント値ｉを初期設定し、初期設定されたカウント値ｉに対応する秘密値ｓ_０，ｍのハッシュチェイン値ｓ_ｉ，ｍを記憶部２１ａに初期設定する構成とした。しかし、ハッシュチェイン値ｓ_ｉ，ｍの生成を管理サーバ装置１０で行い、生成権限情報をk_T,m=(s_i,m,t_ωT,m,ω_T)とする構成としてもよい。この場合、タグ装置２０でのハッシュチェイン値ｓ_ｉ，ｍの初期設定処理が不要となる。

また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

本発明の利用分野としては、例えば、ＲＦＩＤ等のタグ認証システムや、ＩＣカード等の個人認証システム等を例示できる。

図１は、第１の実施の形態のタグ通信システム１の全体構成を示した概念図である。 図２は、第１の実施の形態における管理サーバ装置の機能構成を示したブロック図である。 図３は、第１の実施の形態におけるタグ装置の機能構成を示したブロック図である。 図４は、第１の実施の形態におけるサーバ装置の機能構成を示したブロック図である。 図５は、木構造データの構造を例示するための図である。 図６は、図５に例示した木構造データの各ノードに対応するハッシュ関数Ｆ_ωをノードとした木構造データである一方向性関数木データを示した図である。 図７は、第１の実施の形態における通信情報の生成権限付与処理を説明するためのフローチャートである。 図８は、第１の実施の形態における通信情報の探索権限付与処理を説明するためのフローチャートである。 図９は、第１の実施の形態の通信処理を説明するためのフローチャートである。 図１０は、一方向性関数木データを示した図である。 図１１は、第２の実施の形態における管理サーバ装置の機能構成を示したブロック図である。 図１２は、第２の実施の形態におけるタグ装置の機能構成を示したブロック図である。 図１３は、第２の実施の形態の通信処理を説明するためのフローチャートである。 図１４は、第３の実施の形態における管理サーバ装置の機能構成を示したブロック図である。 図１５は、第３の実施の形態におけるサーバ装置の機能構成を示したブロック図である。 図１６は、第３の実施の形態の通信処理を説明するためのフローチャートである。

符号の説明

１ タグ通信システム
１０,３１０,４１０ 管理サーバ装置
２０,３２０ タグ装置
４０,４４０ サーバ装置

Claims (15)

1. 一方向性関数によって更新される通信情報の取扱い権限を付与する管理装置であって、
   識別子と第１秘密値とを対応付けた秘密値テーブルを格納する秘密値テーブル記憶部と、
   一方向性関数を特定するための情報をノードとし、兄弟ノードに対応する一方向性関数が相互に異なり、親ノードに対応する一方向性関数と所定の一方向性関数集合に属する何れかの一方向性関数との合成写像が子ノードに対応する一方向性関数となる木構造データから、ノードを選択するノード選択部と、
   上記ノード選択部が選択したノードに対応する一方向性関数を抽出する一方向性関数抽出部と、
   上記一方向性関数抽出部が抽出した上記一方向性関数を上記第１秘密値に作用させた一方向性関数値を生成する一方向性関数演算部と、
   上記一方向性関数値を含む権限情報を生成する権限情報生成部と、
   一方向性関数によって通信情報の更新を行う通信装置に対し、上記権限情報を出力する権限情報出力部と、を有し、
   上記権限情報は、上記権限情報に含まれる上記一方向性関数値に前記一方向性関数集合から選択した一方向性関数を作用させて得られる値に対応する通信情報の生成権限を上記通信装置に付与するための情報であることを特徴とする管理装置。
2. 請求項１の管理装置であって、
   上記権限情報生成部は、さらに、上記一方向性関数値とその生成に用いられた上記第１秘密値に対応する上記識別子とを含む第２権限情報を生成し、
   上記権限情報出力部は、さらに、一方向性関数によって更新される通信情報に対応する識別子の探索を行う通信情報探索装置に対し、上記第２権限情報を出力し、
   上記第２権限情報は、
   上記ノード選択部が選択したノード又はその子孫ノードに対応する一方向性関数を上記第１秘密値に作用させて得られる値に対応する通信情報に対応する識別子を探索する権限を上記通信情報探索装置に付与するための情報である、
   ことを特徴とする管理装置。
3. 一方向性関数によって更新される通信情報の取扱い権限を付与する管理装置であって、
   識別子と第１秘密値とを対応付けた秘密値テーブルを格納する秘密値テーブル記憶部と、
   一方向性関数を特定するための情報をノードとし、兄弟ノードに対応する一方向性関数が相互に異なり、親ノードに対応する一方向性関数と所定の一方向性関数集合に属する何れかの一方向性関数との合成写像が子ノードに対応する一方向性関数となる木構造データから、ノードを選択するノード選択部と、
   上記ノード選択部が選択したノードに対応する一方向性関数を抽出する一方向性関数抽出部と、
   上記一方向性関数抽出部が抽出した上記一方向性関数を上記第１秘密値に作用させた一方向性関数値を生成する一方向性関数演算部と、
   上記一方向性関数値とその生成に用いられた上記第１秘密値に対応する上記識別子とを含む権限情報を生成する権限情報生成部と、
   一方向性関数によって更新される通信情報に対応する識別子の探索を行う通信情報探索装置に対し、上記権限情報を出力する権限情報出力部と、を有し、
   上記権限情報は、
   上記ノード選択部が選択したノード又はその子孫ノードに対応する一方向性関数を上記第１秘密値に作用させて得られる値に対応する通信情報に対応する識別子を探索する権限を上記通信情報探索装置に付与するための情報である、
   ことを特徴とする管理装置。
4. 請求項１から３のいずれかの管理装置であって、
   上記秘密値テーブルは、
   上記識別子と上記第１秘密値と第２秘密値とを対応付けたテーブルであり、
   上記権限情報生成部は、
   上記一方向性関数値と上記第２秘密値とを含む上記権限情報を生成する、
   ことを特徴とする管理装置。
5. 一方向性関数によって更新される通信情報を出力する通信装置であって、
   請求項１又は２に記載の管理装置から出力された一方向性関数値を含む権限情報を格納する生成権限情報記憶部と、
   上記生成権限情報記憶部から読み込んだ上記一方向性関数値を含む情報に所定の一方向性関数集合から選択した一方向性関数を作用させ、それによって得られる値に対応する通信情報を生成する通信情報生成部と、
   上記通信情報を出力する通信情報出力部と、
   を有することを特徴とする通信装置。
6. 一方向性関数によって更新される通信情報から、それに対応する識別子を特定する通信情報探索装置であって、
   請求項３の管理装置から出力された上記権限情報に含まれる一方向性関数値とその生成に用いられた第１秘密値に対応する識別子とを対応付けて格納する探索権限情報記憶部と、
   通信情報の入力を受け付ける入力部と、
   上記権限情報に含まれる上記一方向性関数値を含む情報に所定の一方向性関数集合から選択した一方向性関数を作用させ、それによって得られる値に対応する探索値を生成する探索値生成部と、
   上記通信情報と上記探索値とが一致するか否かを判断する比較部と、
   上記通信情報と一致した上記探索値に対応する上記一方向性関数値に対応付けられた上記識別子を、上記探索権限情報記憶部から抽出する抽出部と、
   を有することを特徴とする通信情報探索装置。
7. 請求項１の管理装置と、請求項５の通信装置と、を有することを特徴とする通信システム。
8. 請求項３の管理装置と、請求項６の通信情報探索装置と、を有することを特徴とする通信システム。
9. 請求項２の管理装置と、請求項５の通信装置と、請求項６の通信情報探索装置と、を有することを特徴とする通信システム。
10. 一方向性関数によって更新される通信情報の取扱い権限を付与する管理方法であって、
    請求項１から４の何れかの管理装置が有する秘密値テーブル記憶部とノード選択部と一方向性関数抽出部と一方向性関数演算部と権限情報生成部と権限情報出力部がそれぞれ実行する処理を行う管理方法。
11. 一方向性関数によって更新される通信情報を出力する通信方法であって、
    請求項５の通信装置が有する生成権限情報記憶部と通信情報生成部と通信情報出力部とがそれぞれ実行する処理を行う通信方法。
12. 一方向性関数によって更新される通信情報から、それに対応する識別子を特定する通信情報探索方法であって、
    請求項６の探索権限情報記憶部と入力部と探索値生成部と比較部と抽出部とがそれぞれ実行する処理を行う通信情報探索方法。
13. 請求項１から４の何れかの管理装置としてコンピュータを機能させるためのプログラム。
14. 請求項５の通信装置としてコンピュータを機能させるためのプログラム。
15. 請求項６の通信情報探索装置としてコンピュータを機能させるためのプログラム。

Images