データベースにおいてＩＤを検索可能なプライバシ保護型認証システムおよび装置
【課題】送受信データからＩＤを追跡することを困難にしつつ，サーバ側における照合の負荷を軽減する認証技術を提供する。
【解決手段】タグがサーバに送信するデータを可変ＩＤと照合用ハッシュ値の組とし，可変ＩＤを検索キーとしてデータベースからタグの固定IDを検索することで，認証時のサーバの負荷を大幅に削減する。また，タグはタグ固有鍵を記憶しておき，ＩＤ取得要求への応答があるたびに可変ＩＤを上記タグ固有鍵を使って更新することで，追跡困難性を実現する。
【解決手段】タグがサーバに送信するデータを可変ＩＤと照合用ハッシュ値の組とし，可変ＩＤを検索キーとしてデータベースからタグの固定IDを検索することで，認証時のサーバの負荷を大幅に削減する。また，タグはタグ固有鍵を記憶しておき，ＩＤ取得要求への応答があるたびに可変ＩＤを上記タグ固有鍵を使って更新することで，追跡困難性を実現する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，ユーザのIDを認証する技術に関する。
【背景技術】
【０００２】
現在，携帯電話や非接触型ICカード，商品タグなどを含むユビキタスネットワークが急速に拡大している。これらの携帯端末の用途は多岐に渡るが，1つの大きな用途として端末とそれを持つユーザ（もしくは商品など）を関連付け，ユーザの位置や状態などを把握するシステムが検討されている。携帯電話やICカードを使った電子マネーサービスや入退出管理システム，バーコードの代わりに無線タグを使った商品管理などはその実例である。
【０００３】
これらの機器(以下，一括してタグと称す)は各々が固有のＩＤを持ち，タグリーダからの要求に応えてＩＤやその他のデータをリーダを介してシステムを管理するサーバに送信する。このデータを蓄積することで，タグと関連付けられたユーザ(もしくは機器，商品)の管理が可能となり，商品の流通経路監視やユーザの位置確認などを行うことができる。このようなシステムで重要なことは，タグから送信されるデータの信頼性であり，データが（１）正規のタグから送信されたデータであること，（２）通信路上でデータが改ざんされていないこと，などをチェックするための仕組みが必要となる。このため，ＩＤやデータの完全性を検証するための認証コードを送信データに付加することが望ましい。
【０００４】
ユーザＩＤの正当性を検証するためにもっとも広く用いられているのがパスワード認証であるが，通常のパスワード認証ではパスワード自体が通信路上を流れるため，インターネット通信や無線通信での利用には適していない。このような公開通信路では，ＣＨＡＰ(Ｃｈａｌｌｅｎｇｅ Ｈａｎｄｓｈａｋｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ Ｐｒｏｔｏｃｏｌ)などを利用する。
【０００５】
ＣＨＡＰ認証は，公開通信路上で利用してもタグの秘密情報(固有鍵k(I)など)が漏洩しない他，ＩＤ取得要求ごとにサーバが乱数を生成し，認証コード(ハッシュ値)の再利用ができない。このため，リプレイ攻撃を防止することができる。
【０００６】
このようにＣＨＡＰ認証は優れた認証技術であるが，ユビキタスネットワークには適さない面もある。たとえば近年，プライバシ保護の観点から追跡可能性という新しい安全性の概念が発生した。追跡可能性とは，文字通りある特定のユーザやＩＤの行動を追跡できるかどうか，というものである。ＣＨＡＰなどの既存の認証技術では，まずサーバにＩＤを送信するため，通信を傍受する攻撃者は常にＩＤを得ることができる。したがって，通信を傍受し続けることで個人の位置を把握することが可能である。また，他のＩＤ（商品タグ）との組み合わせにより，ある個人の嗜好などを分析することも可能となる。これは上記のプライバシ保護の観点からして望ましくない性質である。また，通信を傍受し続けることで，第三者により行動が追跡される畏れもある。このような用途においては，タグの追跡が困難な認証方法を使用する必要がある。
【０００７】
これに対し，ＩＤを秘匿したまま認証を行う方法が提案されている。通常の認証では，タグのＩＤを検索キーとして，検証に必要なデータをデータベースから抽出するが，これらの方法では検索キーを使わずに，データベースの全件検索を行うことを基本アイデアとしている(非特許文献１，２参照)。
【０００８】
【非特許文献１】Stephen A. Weis Security and privacy in Radio-Frequency Identification Devices ，[Online]， MIT，２００３年５月９日，ｐ．４０−４２，[２００５年１月２８日検索]，インターネット＜URL: http://theory.lcs.mit.edu/~sweis/pdfs/masters.pdf＞
【非特許文献２】大久保美也子，鈴木幸太郎，木下真吾，「Forward-secure RFID privacy protection for low-cost RFID」， コンピュータセキュリティシンポジウム CSS 2003予稿集，２００３年１０月３１日，ｐ．４９３−４９４
【発明の開示】
【発明が解決しようとする課題】
【０００９】
非特許文献１に記載されている認証方法では，認証の際にIDを送信せず，乱数に依存するハッシュ値のみを送信して認証を行うことで，追跡困難性を実現している。また，非特許文献２に記載されている認証方法では，ＩＤを通信を行うたびに更新し，ＩＤから計算されるハッシュ値を送信して認証を行うことで追跡困難性を実現している。
【００１０】
しかし，非特許文献１，２に記載されている認証方法は，いずれも検索用のキーを送信しないことでプライバシをIDを秘匿したまま認証を行い，照合の際にデータベースに登録されているIDすべてについて照合を行う。すなわち，IDをデータベースから検索するためのキーがないため，データベースの全件検索を行う必要がある。
【００１１】
このため，データベース(もしくは認証用サーバ)の負荷が従来のCHAPなどに比べてひじょうに大きく，大規模なシステムには不向きであった。しかしその一方で，このようなプライバシ保護が可能な認証方法はユビキタス環境においてその真価を発揮する。また，主な用途として期待されているのも不特定多数のユーザを識別する大規模システムである。
【００１２】
したがって，プライバシ保護が可能で，かつ，大規模システムに適した認証技術が望まれている。
【課題を解決するための手段】
【００１３】
本発明は，このような事情を鑑みてなされたもので，送受信データからIDを追跡することを困難にしつつ，サーバ側における照合の負荷を軽減する認証技術を提供するものである。
【００１４】
本発明はIDの追跡を困難にする認証方法であって，非特許文献１に記載されている認証方法の欠点を克服する技術を提供する。本発明は以下の３点を主な特徴とする。
【００１５】
１．送信するデータに検索キーとして可変のＩＤを含める
２．可変のＩＤは通信を行うたびに更新する
３．可変のＩＤを更新するときには秘密鍵を利用し，異なる可変のＩＤを結びつけることを困難にする
さらに詳しく述べると，本発明の提供する認証方法では，タグに対して，固有の固定ＩＤと固有の秘密鍵を定める。これらの値はタグごとに異なる。さらに，タグごとに異なる，通信を行うたびに変更される値を定める。この値を以下では可変ＩＤと称す。タグは秘密鍵と可変ＩＤを記憶しており，タグがサーバに送信するデータを（可変ＩＤ，照合用ハッシュ値）の組とする。ここで，照合用ハッシュ値は可変ＩＤと秘密鍵から計算される値である。サーバでは，受信したデータのうち，可変ＩＤを検索キーとしてデータベースからタグの固定IDを検索することで，認証時のサーバの負荷を大幅に削減することができる。また，タグはＩＤ取得要求への応答があるたびに，可変ＩＤと秘密鍵から新しい可変ＩＤを計算することで追跡困難性を実現する。
【００１６】
より具体的な，本発明の態様は，たとえば，通信装置１と記憶装置１と暗号処理装置１とを備える１個以上のタグと，通信装置２と記憶装置２と暗号処理装置２とを備えるタグ認証装置からなるシステムにおいてタグ認証装置がタグからの通信を識別するための方法であって，タグが備える記憶装置１には秘密鍵１と1回の通信ごとに更新される可変ＩＤ１が記憶されており，タグ認証装置の記憶装置２には各々のタグの情報を記録したタグテーブルが記憶されており，タグテーブルはタグのＩＤと各タグに対応する秘密鍵２と各タグに対応する可変ＩＤ２の値を項目として含んでおり，タグが備える暗号処理装置１は認証コード生成装置１，可変ＩＤ更新装置１を備え，タグ認証装置の暗号処理装置２は認証コード生成装置２，可変ＩＤ更新装置２を備え，タグ認証装置は，通信装置２を介して，繰り返し（例えば定期的に）タグに対して認証を要求する信号を発信し，タグは，信号を受信すると可変ＩＤ１と秘密鍵１とを認証コード生成装置１の入力として認証コード１を生成し，信号に対する応答として，可変ＩＤ１と，認証コード１とを通信装置１を介してタグ認証装置に送信し，秘密鍵１と可変ＩＤ１とを可変ＩＤ更新装置１の入力として新しい可変ＩＤを計算し，その結果を記憶装置１に記憶し，タグ認証装置は，タグからの応答を受信すると応答に含まれる可変ＩＤ１を検索キーとしてタグテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，可変ＩＤ１と秘密鍵２を可変ＩＤ更新装置２の入力として新しい可変ＩＤを計算し，その結果を記憶装置２に記憶することを特徴とする。
【００１７】
さらに，暗号処理装置１および暗号処理装置２は，一方向性ハッシュ関数を１つ以上備えてもよい。
【００１８】
さらに，認証コード生成装置は，一方向性ハッシュ関数Hashを使って，認証コードC
C = Hash(k||v(t)||0)
(ただし，kは該当タグの秘密鍵，v(t)はタグが現在記憶している可変ＩＤとし，k||v(t)||0は秘密鍵と可変ＩＤと０からなるビット列のビット列としての連結を指す)
を生成してもよい。
【００１９】
さらに，可変ＩＤ更新装置は，一方向性ハッシュ関数Hashを使って，新しい可変ＩＤ v(t+1)
v(t+1) = Hash(k||v(t)||1)
(ただし，kは該当タグの秘密鍵，v(t)はタグが現在記憶している可変ＩＤとし，k||v(t)||1は秘密鍵と可変ＩＤと1からなるビット列のビット列としての連結を指す)
を生成してもよい。
【００２０】
さらに，タグテーブルは，さらにすべてのタグについて複数回分の可変ＩＤ v(t+1)〜v(t+M)を記憶してもよい。
【００２１】
さらに，検索キーがタグテーブルに記載されている可変ＩＤ v(t)に該当しない場合に，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行ってもよい。
【００２２】
さらに，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，タグテーブルに記憶されているすべてのタグＩＤごとに対応する秘密鍵と応答に含まれる可変ＩＤ１とを，認証コード生成装置２に入力して得られた値と応答に含まれている認証コード１とを照合し，２つの値が一致するタグＩＤを該当タグと識別してもよい。
【００２３】
さらに，タグ認証装置が発信する認証を要求する信号は乱数情報を含んでおり，タグは信号を受信すると，可変ＩＤ１と秘密鍵１と信号に含まれる乱数情報とを認証コード生成装置１の入力として認証コード１を生成し，信号に対する応答として，可変ＩＤ１と，認証コード１とを通信装置１を介してタグ認証装置に送信し，タグ認証装置はタグからの応答を受信すると，応答に含まれる可変ＩＤ１を検索キーとしてタグテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，応答に含まれる可変ＩＤ１と秘密鍵2と発信した乱数情報とを認証コード生成装置２に入力して得られた値と，応答に含まれる認証コード1を照合することで，応答が発信した信号に対する応答であることを確認してもよい。
【００２４】
また，本発明のほかの具体的態様は，無線通信装置１と記憶装置１と暗号処理装置１とを備える１個以上のタグと，通信装置２と記憶装置２と暗号処理装置２とを備えるタグ認証装置と，タグと通信するための無線通信装置２と，タグ認証装置と通信するための通信装置１とを備える１個以上のタグリーダとからなる無線タグ位置登録システムであって，タグが備える記憶装置１には秘密鍵１と1回の通信ごとに更新される可変ＩＤ１が記憶されており，タグ認証装置の記憶装置２には各々のタグの情報を記録したタグテーブルとタグリーダの情報を記録したリーダテーブルが記憶されており，タグテーブルはタグのＩＤと各タグの現在位置，各タグに対応する秘密鍵２，各タグに対応する可変ＩＤ２の値を項目として含んでおり，リーダテーブルはタグリーダのＩＤと各タグリーダを設置した場所の情報を項目として含んでおり，タグが備える暗号処理装置１は認証コード生成装置１，可変ＩＤ更新装置１を備え，タグ認証装置の暗号処理装置２は認証コード生成装置２，可変ＩＤ更新装置２を備え，無線通信装置１と無線装置２は一定距離以下でのみ通信可能であり，タグリーダは無線通信装置２を介して，繰り返し（例えば定期的に）認証を要求する信号をブロードキャストし，タグは前記ブロードキャストされた信号を受信すると，可変ＩＤ１と秘密鍵１とを認証コード生成装置１の入力として認証コード１を生成し，信号に対する応答として，可変ＩＤ１と，認証コード１とを含むデータを通信装置１を介してタグリーダに送信し，秘密鍵１と可変ＩＤ１とを可変ＩＤ更新装置１の入力として新しい可変ＩＤを計算し，その結果を記憶装置１に記憶し，タグリーダは，タグからの通信を受信するとタグからの通信で受信したデータにタグリーダのＩＤを付加し，通信装置２を介してタグ認証装置に位置登録要求信号として送信し，タグ認証装置は，タグリーダからの位置登録要求信号を受信すると位置情報登録要求信号に含まれる可変ＩＤ１を検索キーとしてタグテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，可変ＩＤ１と秘密鍵２を可変ＩＤ更新装置２の入力として新しい可変ＩＤを計算し，位置情報登録要求信号に含まれるタグリーダのＩＤを検索キーとしてリーダテーブルからタグリーダの位置情報を取得し，タグリーダの位置情報と新しい可変ＩＤを記憶装置２に記憶することを特徴とする。
【００２５】
さらに，暗号処理装置１および暗号処理装置２は，一方向性ハッシュ関数を１つ以上備えてもよい。
【００２６】
さらに，認証コード生成装置は，一方向性ハッシュ関数Hashを使って，認証コードC
C = Hash(k||v(t)||0)
(ただし，kは該当タグの秘密鍵，v(t)はタグが現在記憶している可変ＩＤとし，k||v(t)||0は秘密鍵と可変ＩＤと０からなるビット列のビット列としての連結を指す)
を生成してもよい。
【００２７】
さらに，可変ＩＤ更新装置は，一方向性ハッシュ関数Hashを使って，新しい可変ＩＤ v(t+1)
v(t+1) = Hash(k||v(t)||1)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||1は前記秘密鍵と前記可変ＩＤと1からなるビット列のビット列としての連結を指す)
を生成してもよい。
【００２８】
さらに，タグテーブルは，さらにすべてのタグについて複数回分の可変ＩＤ v(t+1)〜v(t+M)を記憶してもよい。
【００２９】
さらに，検索キーがタグテーブルに記載されている可変ＩＤ v(t)に該当しない場合に，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行ってもよい。
【００３０】
さらに，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，タグテーブルに記憶されているすべてのタグＩＤごとに対応する秘密鍵と応答に含まれる可変ＩＤ１とを，認証コード生成装置２に入力して得られた値と応答に含まれている認証コード１とを照合し，２つの値が一致するタグＩＤを該当タグと識別してもよい。
【００３１】
さらに，リーダテーブルは各々のタグリーダに近い位置にあるタグリーダのＩＤとを項目として含んでおり，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，位置情報登録要求に含まれているタグリーダのＩＤを検索キーとして，リーダテーブルから位置情報登録要求を送信したタグリーダに近い位置にあるタグリーダのリストを取得し，位置情報登録要求に含まれているタグリーダとリストに含まれるタグリーダに対応する位置情報を検索キーとしてタグテーブルを検索し，タグテーブルの位置情報の項目が検索キーのいずれかに合致するすべてのタグＩＤごとに対応する秘密鍵と応答に含まれる可変ＩＤ１とを，認証コード生成装置２に入力して得られた値と応答に含まれている認証コード１とを照合し，２つの値が一致するタグＩＤを該当タグと識別してもよい。
【００３２】
また，タグリーダが発信する認証を要求する信号は乱数情報を含んでおり，タグは上記信号を受信すると，可変ＩＤ１と秘密鍵１と乱数情報とを認証コード生成装置１の入力として認証コード１を生成し，信号に対する応答として，可変ＩＤ１と，認証コード１とを通信装置１を介してタグ認証装置に送信し，タグリーダはタグからの応答を受信すると，タグからの通信で受信したデータにタグリーダのＩＤと上記乱数情報とを付加し，通信装置２を介してタグ認証装置に位置登録要求信号を送信し，タグ認証装置は，位置登録要求信号を受信すると位置登録要求信号に含まれる可変ＩＤ１を検索キーとしてテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，位置登録要求信号に含まれる可変ＩＤ１と秘密鍵2と発信した乱数情報とを認証コード生成装置２に入力して得られた値と，位置登録要求信号に含まれる認証コード1を照合することで，タグの応答がタグリーダが発信した信号に対する応答であることを確認してもよい。
【００３３】
また，タグリーダは，さらに記憶装置３と暗号処理装置３とを備え，記憶装置３は秘密鍵３を記憶しており，暗号処理装置３は乱数生成装置３と認証コード生成装置３とを備え，タグリーダはタグからの通信を受信すると，暗号処理装置３を用いて乱数を生成し，秘密鍵３と上記乱数を認証コード生成装置３への入力とし，得られた値をタグリーダＩＤに対する認証コードとして，タグ認証装置に送信する位置登録要求信号に付加してタグ認証装置に送信してもよい。
【００３４】
さらに，通信装置４を備える１個以上の表示用端末と，通信装置５を備える１個以上のアクセスポイントと，を備え，表示用端末は，通信装置４を介して上記アクセスポイントに接続し，タグ認証装置にタグ位置閲覧要求を送信し，タグの現在位置を取得してもよい。
【００３５】
さらに，タグ認証装置の記憶装置２は表示用端末テーブルとを備え，表示端末テーブルは端末のＩＤと，各タグが閲覧してよいタグのＩＤからなるリストとを含み，タグ位置閲覧要求は表示用端末のＩＤを含み，タグ認証装置は，表示用端末からのタグ位置閲覧要求に対し，タグ位置閲覧要求に含まれる表示用端末のＩＤを検索キーとして表示用端末テーブルを検索し，要求を行った表示用端末が閲覧可能なタグＩＤのリストを取得し，リストに含まれる各タグＩＤを検索キーとしてタグテーブルを検索し，各タグの位置情報を取得し，取得した情報を表示用端末に返信してもよい。
【００３６】
さらに，表示用端末は，さらに暗号処理装置を備え，タグ認証装置との通信を暗号化してもよい。
【００３７】
上記のように，本発明の認証方法ではサーバに送信するデータに検索キーとして使用できる可変のＩＤを含めるため，サーバは受信したデータがどのタグから送信されたものかを少ない負荷で，データベースから探し出すことができる。
【発明の効果】
【００３８】
本発明によれば，認証時のサーバの負荷を大幅に削減することができる。この結果，大規模なシステムにおいてＩＤの追跡困難性を実現可能な認証システムを提供できる。
【発明を実施するための最良の形態】
【００３９】
以下に，本発明を適用する実施形態を説明する。
【００４０】
本実施形態は無線タグを利用したユーザの位置確認システムであり，ユーザは無線タグを携帯しているものとする。システムは一定の監視区域を対象とし，この区域内にタグリーダを設置する。タグリーダは一定時間おきにタグＩＤ取得要求をブロードキャストする。通信可能距離内に無線タグが存在すれば，タグは要求に対して応答する。タグリーダは受信した応答を認証サーバに転送し，認証サーバはタグの認証を行う。本実施形態では，タグリーダがタグからの応答を認証サーバに転送する際にタグリーダのＩＤを同時に送信することで，タグリーダの設置位置とタグを関連付け，タグの現在位置を確認する。
【００４１】
このようなシステムでは，通信可能距離を半径とする円で監視区域を充填することで，区域内のユーザの行動を完全に捕捉することができる。たとえば，遊園地などの大型レジャー施設で，幼児などにタグを配布して迷子の捜索を容易にするようなシステムでは，このように監視区域を充填するようにタグリーダを配置することで，漏れなく幼児の位置を確認することができる。
【００４２】
また，大型店舗などでは，たとえばエレベータや階段などフロアへの出入り口にタグリーダを設置することで，大雑把にユーザが何階にいるかを確認することができる。同様に，ビルの入口などで緩やかな入退出管理を行うことも可能である。
＜図1＞
図１は本実施形態のシステム構成を表した図である。本実施形態は，タグ（２０１），タグリーダ（２１１），認証サーバ（２２１），データベース（ＤＢ）サーバ（２３１），表示用携帯端末（２４１）からなるシステムである。
【００４３】
タグ（２０１）は記憶装置（２０３）と通信装置（２０２），タグ（２０１）の認証コードの生成などを行うための暗号処理装置（２０４），データ処理を統括するデータ登録装置（２０５）からなる。
【００４４】
タグリーダ（２１１）はタグ（２０１）と通信するための通信装置１（２１２），認証サーバと通信するための通信装置２（２１３），リーダの認証コード生成などを行う暗号化装置（２１４），データ処理を統括するデータ登録・参照装置（２１５）からなる。図ではタグ，タグリーダは１つであるが，一般には一つ以上のタグ，一つ以上のタグリーダからなるシステムである。
【００４５】
認証サーバ（２２１）はタグリーダ（２１１）や表示用携帯端末（２４１）と通信を行うための通信装置（２２２），ＤＢアクセス装置（２２３），タグ（２０１）やタグリーダ（２１１）の認証を行うための認証装置（２２５），検証用の認証コード生成などを行う暗号化装置（２２６），データ処理を統括するデータ登録・参照装置（２２４）からなる。
【００４６】
ＤＢサーバ（２３１）はタグリーダのＩＤと位置情報（タグリーダの設置位置）からなるリーダテーブル（２３２），表示用携帯端末のＩＤと各端末が閲覧可能なタグのＩＤからなる携帯端末テーブル（２３３），タグのＩＤとタグの固有鍵，タグの可変ＩＤからなるタグテーブル（２３４）からなる。
【００４７】
表示用携帯端末（２４１）は認証サーバと通信するための通信装置（２４２），記憶装置（２４３）と携帯端末の認証に必要な計算を行う暗号化装置（２４４），表示装置（２４５），およびデータ処理を統括するデータ登録・参照装置（２４６）からなる。
【００４８】
これらの機器はネットワーク（２５１）を通じて互いに通信することができる。
【００４９】
本実施形態では，ユビキタスネットワークで用いられるＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）タグと同じく，タグ（２０１）とタグリーダ（２１１）の間の通信は無線通信を想定しているが，通常の有線による通信でも良い。また，タグリーダ（２１１），認証サーバ（２２１），表示用携帯端末（２４１）はＬＡＮなどの有線ネットワークで繋がっていることを想定しているが，表示用携帯端末（２４１）などは無線通信でこのネットワークに接続しても良い。また，ＤＢサーバ（２３１）もこのネットワークに接続しても良い。
＜図2＞
次に，認証サーバ（２２１）を実現するものとして，たとえば図２のＰＣ（１０１）を例に説明する。ＰＣ（１０１）はＣＰＵ（１０２），メモリ（１０３），ハードディスクなどの外部記憶装置（１０４），通信インターフェース（ＩＦ）（１０５），周辺機器接続ＩＦ（１０６）からなり，周辺接続機器ＩＦ（１０６）を通じてモニタ（１０７）と接続している。
【００５０】
外部記憶装置（１０４）には，暗号処理装置（２２６）を実現する暗号処理プログラム（１０８），認証装置（２２５）を実現する認証プログラム（１０９）などが格納されている。また，外部記憶装置（１０４）には，ＬＡＮやインターネットなどのネットワーク（１１０）に接続する通信ＩＦ（１０５）と協働して通信装置（２２２）を実現するプログラムや，周辺機器接続ＩＦ（１０６）と協働してDBアクセス装置（２２３）を実現するプログラムも格納されている。さらにＤＢサーバプログラムを外部記憶装置（１０４）内に内蔵しても良い。
【００５１】
そして，ＣＰＵ（１０２）がメモリ（１０３），外部記憶装置（１０４）に格納されたプログラムを実行することにより，認証サーバ（２２１）の各機能が実現する。
【００５２】
その他，タグ（２０１），タグリーダ（２１１），ＤＢサーバ（２３１），表示用携帯端末（２４１）は，いずれもＰＣ（１０１）と同様の構成を備える情報処理装置において，ＣＰＵ（１０２）がメモリ（１０３），または外部記憶装置（１０４）に格納されたプログラムを実行することにより具現化されるものである。
【００５３】
これらのプログラムは，あらかじめ，上記ＰＣ（１０１）または情報処理装置内のメモリに格納されていても良いし，必要なときに，情報処理装置が利用可能な，着脱可能な記憶媒体または通信媒体を介して，他の装置から導入されてもよい。通信媒体とは，ネットワークまたはネットワーク上の搬送波やデジタル信号を指す。
【００５４】
なお，ＤＢサーバ（２３１）は周辺機器接続ＩＦ（１０６）や通信ＩＦ（１０５）を通じて外部接続のハードディスクなどの外部記憶装置やネットワーク（２５１）に接続された別のＰＣやストレージとして実現されたＤＢサーバ（２３１）として実現しても良い。
【００５５】
また，認証サーバ（２２１），タグ（２０１），タグリーダ（２１１），ＤＢサーバ（２３１），表示用携帯端末（２４１）のいずれかの，一部または全部をハードウェアで実現することも可能である。
＜図3＞
図３はＤＢサーバ（２３１）に記憶されているリーダテーブル（２３２）の構成図である。リーダテーブル（２３２）の項目はタグリーダＩＤ（３０１）と位置情報（３０２）である。位置情報（３０２）は，タグリーダ（２１１）を設置した位置を表す情報で，システムの構成時に設定する。
＜図4＞
図４はＤＢサーバ（２３１）に記憶されている表示端末テーブル（２３３）の構成図である。表示端末テーブル（２３３）の項目は表示端末ＩＤ（４０１）と，各表示端末から情報を取得できるタグ（２０１）のリスト（４０２）である。
＜図５＞
図５はＤＢサーバ（２３１）に記憶されているタグテーブル（２３４）の構成図である。タグテーブル（２３４）の項目はタグリーダＩＤ（５０１）とタグの固有鍵（５０２），タグの位置情報（５０３），そしてタグの可変ＩＤ（５０４）である。タグの可変ＩＤは現在時刻tについてのみ記憶しても良いが，本実施形態では同期ずれ(後述)に対応するために何回か先の可変ＩＤについてもあらかじめ計算して可変ＩＤの未来値（５０５）として記憶しておく。
＜図6＞
図６はタグの位置情報をＤＢサーバに登録するためのプロトコルである。ステップ４のタグ（２０１）からのタグＩＤ取得応答（６０１）とステップ８のタグ認証は固定ＩＤを秘匿する認証方法によるものである。タグ（２０１）と認証サーバ（２２１）の処理の詳細は後述する。
【００５６】
ステップ１．タグリーダ（２１１）から近傍のタグ（２０１）に対し，タグID取得要求（６０１）を行う。
【００５７】
ステップ２．タグ（２０１）は，タグリーダ（２１１）にタグID取得応答（６０２）を行う。
【００５８】
ステップ３．タグリーダ（２１１）は，認証サーバ（２２１）に位置情報登録要求（６０３）を行う。
【００５９】
ステップ４．認証サーバ（２２１）は，ＤＢサーバ（２３１）にリーダID検索要求（６０４）を行う。
【００６０】
ステップ５．ＤＢサーバ（２３１）は，リーダテーブル（２３２）からリーダID ridを検索し，認証サーバ（２２１）にリーダID検索応答（６０５）を行う。
【００６１】
ステップ６．認証サーバ（２２１）は，タグリーダ（２１１）を認証後，ＤＢサーバ（２３１）にタグID検索要求（６０６）を行う。
【００６２】
ステップ７．ＤＢサーバ（２３１）は，タグテーブル（２３４）からタグIDを検索し，認証サーバ（２２１）にタグID検索応答（６０７）を行う。
【００６３】
ステップ８．認証サーバ（２２１）は，タグIDを認証後，ＤＢサーバ（２３１）に位置情報登録要求（６０８）を行う。
【００６４】
ステップ９．ＤＢサーバ（２３１）は，タグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を行う。
【００６５】
ステップ１０．認証サーバ（２２１）は，タグリーダ（２１１）に位置情報登録応答（６１０）を行う。
＜図7＞
図７はタグリーダ（２１１）からＩＤ取得要求（６０１）を受信したタグ（２０１）の動作を表すフローチャートである。タグ（２０１）は記憶装置（２０３）にタグ固有鍵k(i)（５０２）と可変ＩＤ v(i, t) （５０４）を記憶しているものとする。タグ（２０１）はタグリーダ（２１１）からＩＤ取得要求（６０１）を受信すると，以下の以下のステップにしたがって処理を行う。
【００６６】
ステップ１（２００２）．タグ（２０１）は暗号処理装置（２０４）にタグ固有鍵k(i) （５０２）と可変ＩＤ v(i, t) （５０４）を入力し，認証コードを次のように計算する。
【００６７】
h(i, t) = Mac(k(i), v(i, t))
ここで，Mac(x, y)は認証コードを計算するための関数である。この関数はＳＨＡ−１などのハッシュ関数を用いたＨＭＡＣや，ＡＥＳなどのブロック暗号を用いたＣＭＡＣなどの標準的なメッセージ認証子生成方法を用いれば良い。また，単にタグ固有鍵k(i) （５０２）と可変ＩＤ v(i, t) （５０４）を連結したものをＳＨＡ−１などのハッシュ関数で処理し，その出力を認証コードh(i, t)としても良い。
【００６８】
ステップ２（２００３）．タグ（２０１）はＩＤ取得応答（６０２）としてT(i, t) = (v(i, t),h(i, t))をタグリーダ（２１１）に送信する。
【００６９】
ステップ３（２００４）．タグ（２０１）は暗号処理装置（２０４）にタグ固有鍵k(i)（５０２）と時刻t(現在)の可変ＩＤ v(i, t)（５０４）を入力し，時刻t+1の可変ＩＤを次のように計算する。
【００７０】
v(i, t+1) = Next(k(i), v(i, t))
ここで，Nextは可変ＩＤの更新を行う関数であり，認証コードを計算するための関数Macとは異なるものを用いる。たとえば，認証コードを計算する関数MacとしてSHA1(k(i)||v(i, t)||0)，状態更新を行う関数NextとしてSHA1(k(i)||v(i, t)||1)などを用いる。
【００７１】
新しい可変ＩＤ v(i, t+1)はデータ登録装置（２０５）を介して記憶装置（２０３）に格納される。
【００７２】
ステップ４（２００６）．タグ（２０１）は処理を終了し，待機状態に移行する。
【００７３】
待機状態にあるタグ（２０１）はＩＤ取得要求（６０１）を受けると上記のステップを繰り返す。タグリーダ（２１１）からのＩＤ取得要求（６０１）が頻繁にある場合や，タグリーダ1個あたりの通信可能エリアが広い場合には，一定時間の休止を設定すれば良い。
＜図8＞
図８はタグリーダ（２１１）からの位置情報登録要求（６０３）を受信した認証サーバ（２２１）およびＤＢサーバ（２３１）の動作を表すフローチャートである。以下，このフローチャートに従って認証サーバの動作を説明する。
【００７４】
ステップ１（２１０２）．認証サーバ（２２１）はタグリーダ（２１１）から位置情報登録要求を受信すると，まずタグリーダ（２１１）の認証を行う。この認証は別途ＣＨＡＰなどのプロトコルを実行しても良いし，電子署名などを用いた認証を行っても良い。電子署名を用いた認証であれば，認証サーバ（２２１）はリーダＩＤ検索要求（６０４）をＤＢサーバ（２３１）に送信し，ＤＢサーバ（２３１）からのリーダＩＤ検索応答（６０５）としてタグリーダ（２１１）の公開鍵を受け取り，位置情報登録要求（６０３）に含まれているタグリーダ（２１１）の署名を検証する。また，この際にＤＢサーバ（２３１）からタグリーダ（２１１）の位置情報posを取得しておく。
【００７５】
なお，ＣＨＡＰによる認証の概要は次の通りである。
【００７６】
ステップA．サーバSはタグリーダＲにＩＤ取得要求を送信する。
【００７７】
ステップB．サーバＳは乱数randを生成し，タグリーダＲに送信する。
【００７８】
ステップC．タグリーダＲはサーバSにＩＤと乱数rand，ハッシュ値h = Hash(k(Ｒ), rand)の組 (Ｒ, rand, h) を送信する。ここでk(Ｒ)はタグリーダＲの固有鍵である。
【００７９】
ステップD．サーバSはデータベースに登録されているタグリーダのリストからタグＲに対応する固有鍵k（Ｒ）を取り出し， ハッシュ値h’ = Hash(k(Ｒ), rand) を計算する。
【００８０】
ステップE．サーバＳはh = h’ であればＩＤを認証する。 h ≠ h’ であれば，サーバS はタグリーダからの応答が不正なものであると判断する。
【００８１】
ステップ２（２１０３）．ＤＢサーバ（２３１）にタグＩＤ検索要求（６０６）を送信し，タグ（２０１）の可変ＩＤ v(i, t)を検索キーとしてDBのタグテーブル（２３４）から時刻tの可変IDを検索する。
【００８２】
ステップ３（２１０４，２１０５）．ＤＢサーバ（２３１）はステップ２（２１０３）の検索で該当するタグＩＤが見つからなければ例外処理（１）に移行する。
【００８３】
ステップ４（２１０６）．ＤＢサーバ（２３１）はステップ２（２１０３）の検索で該当するタグＩＤを見つけると，タグＩＤ検索応答（６０７）として該当するタグのID（５０１）と付随するエントリ（５０２〜５０５）を認証サーバ（２２１）に送信する。，認証サーバ（２２１）は可変ＩＤの未来値（５０５）の最後の値(時刻t+Mの値) v(i', t+M)を取り出し，時刻t+M+1の可変ＩＤを次のように計算する。
【００８４】
v(i', t+M+1) = Next(k(i'), v(i', t+M))
ステップ５（２１０７）．認証サーバ（２２１）は，受信したエントリについて「現在の可変ＩＤ」（５０４）の項目をv(i', t+1)で書き換える。また，可変ＩＤの未来値（５０５）についても，一つずつ位置を繰り上げていき，リストの最後に新しく計算した時刻t+M+1の可変ＩＤ v(i', t+M+1)を追加する。さらにエントリの位置情報（５０３）を位置情報登録要求（６０３）に含まれる位置情報posに書き換える。
【００８５】
認証サーバ（２２１）はＤＢサーバ（２３１）に位置情報登録要求（６０８）を送信し，計算した新しいエントリをＤＢサーバ（２３１）に送信する。ＤＢサーバ（２３１）は位置情報登録要求（６０８）を受信すると，その情報に基づきタグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を返信する。
【００８６】
ステップ６（２１０８，２１０９，）．認証サーバ（２２１）はタグリーダ（２１１）に位置情報登録応答（６１０）を行い，タグ（２０１）が認証されたことをタグリーダ（２１１）に伝え，セッションを終了する。
【００８７】
このように，本実施形態ではタグから受信した可変ＩＤに対応する値がタグテーブル（２３４）から見つかればタグからの通信が正当なものであるとみなす。
【００８８】
なお，ここでは認証サーバ（２２１）はタグリーダ（２１１）からの位置情報登録要求（６０３）ごとにＤＢサーバ（２３１）にタグＩＤ検索要求（６０６）を出しているが，システムを稼動させるにあたって，あらかじめＤＢのタグテーブル（２３４）などを認証サーバ（２２１）のメモリ上などに展開しておくことでＤＢサーバ（２３１）へのアクセスを削減し，検索を高速に処理することができる。また，認証サーバ（２２１）からタグリーダ（２１１）への位置情報登録応答（６１０）は省略しても良い。
＜図9＞
図９は図８のフローチャートのステップ３で例外処理（１）に移行した場合のＤＢサーバ（２３１）および認証サーバ（２２１）の動作を表したフローチャートである。
【００８９】
例外処理（１）は，可変ＩＤの同期ずれを想定したものである。本実施形態の主眼はデータベースの検索キーとして可変ＩＤを使うことで，ＩＤの秘匿性とデータベースの検索可能性を同時に実現することである。ＩＤの秘匿性(追跡困難性)を実現するために，可変ＩＤは通信を行うごとに更新する必要がある。しかしたとえば，ユーザがタグリーダ（２１１）の通信可能領域の縁を掠めた場合や電波障害などが発生した場合には，タグ（２０１）はタグＩＤ取得要求（６０１）を受け取り図７のフローに従ってタグＩＤ取得応答を返すが，タグリーダ（２１１）がタグ（２０１）からのタグＩＤ取得応答（６０２）を受信できない可能性がある。このような場合には，タグ（２０１）のみが可変ＩＤの更新を行い，タグテーブル（２３４）の情報は更新されない。すなわち，タグの記憶している可変ＩＤとタグテーブル（２３４）の記憶している現在の可変ＩＤ（５０４）の間にずれが生じる。これが可変ＩＤの同期ずれである。
【００９０】
以下，図９に従って可変ＩＤの同期ずれが発生した場合の処理について説明する。
【００９１】
ステップ１（２２０２）．図８のフローチャートのステップ３（２１０４）で該当する現在の可変ＩＤ（５０４）が見つからなかった場合，ＤＢサーバはv(i, t)を検索キーとしてDBのタグテーブル（２３４）から可変IDの予測値のリスト（５０５）を検索する。
【００９２】
ステップ２（２２０３，２２０４）．タグテーブル（２３４）のリストにv(i, t)と一致する可変ＩＤが見つからなかった場合には例外処理（２）へ移行する。一致する可変ＩＤが見つかった場合にはステップ３以下の処理を行う。
【００９３】
ステップ３（２２０５）．ＤＢサーバ（２３１）はタグＩＤ検索応答（６０７）として該当するタグのID（５０１）と付随するエントリ（５０２〜５０５），同期ずれの量d (v(i, t) = v(i', t+p))を認証サーバ（２２１）に送信する。
【００９４】
，認証サーバ（２２１）はタグ（２０１）の新しい情報からなるエントリを以下のように作成する。
【００９５】
位置情報（５０３）：pos
現在の可変ＩＤ（５０４）：v(i', t+d+1)
可変ＩＤの未来値のリスト（５０５）：
v(i', t+x) = v(i', t+d+1+x), 0 < x < M-d
v(i', t+x) = Next(k(i'), v(i', t+d+x)), M-d <= x <= M
ステップ４（２２０６）．認証サーバ（２２１）はＤＢサーバ（２３１）に位置情報登録要求（６０８）を送信し，ステップ６で計算した新しいエントリをＤＢサーバ（２３１）に送信する。ＤＢサーバ（２３１）は位置情報登録要求（６０８）を受信すると，その情報に基づきタグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を返信する。
【００９６】
ステップ５（２２０７，２２０８，）．認証サーバ（２２１）はタグリーダ（２１１）に位置情報登録応答（６１０）を行い，タグ（２０１）が認証されたことをタグリーダ（２１１）に伝え，セッションを終了する。
【００９７】
例外処理（１）におけるステップ３以降の処理は正常処理を表す図８のフローチャートのステップ４以降とほぼ同様の処理を行う。ただし，ステップ３ではＤＢサーバ（２３１）がずれの量dを認証サーバ（２２１）に送信し，ステップ６では認証サーバ（２２１）が同期ずれを補正するため，ずれに相当する回数について可変ＩＤの未来値の計算を行い，新しいエントリを生成する。
【００９８】
なおステップ３では，見つかったタグＩＤについて，同期ずれが発生したことをログなどに記録しても良いし，タグテーブル（２３４）に記録するための項目を設けても良い。あまり頻繁に同期ずれが発生する場合には，タグリーダの設置箇所に何らかの障害が発生している可能性がある。また，単一のタグについて同期ずれが頻繁に発生する場合には，タグの破損や（該当タグを検索不可能にすることを目的とする）攻撃者の存在などが懸念される。同期ずれの発生についてログを取ることにより，このような障害の発生を検出することができる。，ある程度以上の頻度で同期ずれが発生する場合には，システム管理者に警告信号を送信するなどの対策を取る。
【００９９】
本実施形態では図６の通信順序などにより，構成同期ずれが発生した場合には常にタグの可変ＩＤが先行する(時刻t+dの値になる)ように設定している。このため，タグテーブルには可変ＩＤの未来値のみを保持しており，同期ずれが発生した場合の検索が容易である。
【０１００】
本実施形態ではタグの位置情報のみを取り扱うシステムを想定しているが，認証後にタグに対してデータの書き込みを行うようなシステムでは，タグリーダからの応答を待ってタグの可変ＩＤを更新することも考えられる。このようなケースでは，タグがタグリーダからの応答を受信できない可能性があり，逆にタグの可変ＩＤがタグテーブルの現在の可変ＩＤ（５０４）に対して遅れることも想定する必要がある。したがって，そのような場合にはタグテーブルは可変ＩＤの未来値だけではなく，過去の値の履歴をある程度保存しておき，照合時にはその双方について検索を行う必要がある。
＜図10＞
図10は図９のフローチャートのステップ２で例外処理（２）に移行した場合のＤＢサーバ（２３１）および認証サーバ（２２１）の動作を表したフローチャートである。例外処理（２）は極端な同期ずれが発生し，タグの可変ＩＤに対応する値がＤＢサーバの可変ＩＤリストに見つからない場合を処理するものである。以下，図10に従って例外処理（２）を説明する。
【０１０１】
ステップ１（２３０２）．ＤＢサーバ（２３１）はタグテーブル（２３４）の可変IDの未来値のリスト（５０５）からv(i, t)と一致する値を見つけられなかった場合，タグＩＤ検索応答（６０７）としてタグテーブル（２３４）のすべてのID（N個）についてタグＩＤ jとタグ固有鍵k(j)を認証サーバに送信する。
【０１０２】
ステップ２（２３０３）．認証サーバは，タグＩＤ用のカウンタを初期化する。
【０１０３】
ステップ３（２３０４，２３０５）． もしカウンタの値がN以下であれば，ステップ５以下のルーチンを実行する。カウンタの値がNを超えていたら（すべてのタグについて計算を終了したら），位置情報登録要求は不正なものと判断し，位置情報登録要求（６０８）をＤＢサーバに送信する。ＤＢサーバ（２３１）はログにエラーを記録する。
【０１０４】
ステップ４（２３０６，２３０７）．認証サーバ（２２１）は位置情報登録応答（６１０）として，タグリーダ（２１１）に認証が失敗したことを伝え，処理を終了する。
【０１０５】
ステップ５（２３０８）．認証サーバ（２２１）はj番目のタグＩＤ（５０１）について照合のための以下の認証コード値を次のようにして計算する。
【０１０６】
x(j) = Mac(k(j), v(i, t))
ステップ６（２３０９）．認証サーバ（２２１）は位置情報登録要求（６０３）で受け取った認証コードと，ステップ５（２３０８）で生成した検証用の認証コードの照合を行う。２つの認証コードが一致すればステップ７（２３１０）に移行する。一致しない場合にはステップ１０（２３１４）に移行する。
【０１０７】
ステップ７（２３１０）．認証コードが一致した場合には，認証サーバ（２２１）はタグ（２０１）の新しい情報からなるエントリを以下のように作成する。
【０１０８】
位置情報（５０３）：pos
現在の可変ＩＤ（５０４）：v(j, t) = Next(k(j), v(i, t))
可変ＩＤの未来値のリスト（５０５）：v(j, t+x) = Next(k(j), v(j, t+x-1)), 0 < x <= M
ステップ８（２３１１）．認証サーバ（２２１）はＤＢサーバ（２３１）に位置情報登録要求（６０８）を送信し，ステップ７で計算した新しいエントリをＤＢサーバ（２３１）に送信する。ＤＢサーバ（２３１）は位置情報登録要求（６０８）を受信すると，その情報に基づきタグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を返信する。
【０１０９】
ステップ９（２３１２，２３１３）．認証サーバ（２２１）はタグリーダ（２１１）に位置情報登録応答（６１０）を行い，タグ（２０１）が認証されたことをタグリーダ（２１１）に伝え，セッションを終了する。
【０１１０】
ステップ１０（２３１４）．認証コードが一致しない場合には，カウンタの値に1を加え，ステップ３（２３０４）に戻る。
＜図12，13＞：位置情報を用いた探索空間の絞込み
例外処理（２）では，タグテーブル（２３４）に登録されているすべてのタグについて認証コードを計算するが，タグテーブル（２３４）に記録されいてる位置情報（５０３）pos(i, t-1)を使って照合を行うタグ候補を絞り込むことができる。
【０１１１】
図12はタグリーダ（２１１）の配置を表したイメージ図である。図中の黒丸「●」（２４０１〜２４０６）はそれぞれタグリーダ（２１１）を表す。また，それぞれのタグリーダを中心とする大きな円はタグリーダ（２１１）の通信可能圏を表す。図中でタグリーダR(i)（２４０１）の通信可能圏はタグリーダR(j1)（２４０２）〜R(j4)（２４０５）に隣接しており，タグリーダR(j5)（２４０６）とは隣接していない。図中では，隣接しているタグリーダ（２１１）を太い実線で結んでいる。
【０１１２】
また，図13はタグテーブル（２３４）に記録されいてる位置情報（５０３）pos(i, t-1)を使って照合を行うタグ候補を絞り込む場合のリーダテーブル（２３２）の構成図である。リーダテーブル（２３２）の項目は，タグリーダID（３０１）とタグリーダの位置情報（３０２），そして各々のタグリーダ（２１１）に隣接しているタグリーダ（２１１）のID（１３０３）のリストである。
【０１１３】
時刻tにおいてタグリーダR(i)（２４０１）から認証サーバ（２２１）に位置情報登録要求（６０３）が送信されたとする。このとき，タグリーダ（２４０１）にタグID取得応答（６０２）を送信したタグ（２０１）は，時刻t-1においてタグリーダR(i)（２４０１）もしくはそれに隣接するタグリーダR(j1)（２４０２）〜R(j4)（２４０５）の通信可能圏にいたことが期待できる。したがって，タグテーブルに記録されている時刻t-1の位置情報を検索キーとして，タグリーダR(i)（２４０１）およびそれに隣接するタグリーダR(j1)（２４０２）〜R(j4)（２４０５）に対応する位置情報を持つタグを抜き出し，これらのタグについて認証コードの照合を行えばよい。このステップにおいて認証コードが一致するタグ候補が見つからない場合には，改めて残りのタグリストについて図10の処理を行う。
【０１１４】
このように，タグテーブル（２３４）に記憶されている位置情報を用いることで，例外処理（２）の場合にも照合を行うタグ候補を絞り込むことができる。
＜図14＞：リプレイ攻撃対策
本実施形態において，図７の認証コード生成方法では，認証コードにタグリーダ（２１１）のチャレンジコードが含まれていないため，リプレイ攻撃（なりすまし）に対して安全でない可能性がある。リプレイ攻撃の概要を以下に述べる。
【０１１５】
ステップＡ．攻撃者はタグID取得要求（６０１）を送信し，タグID取得応答（６０２）を受信する。
【０１１６】
ステップＢ．攻撃者は正規のタグリーダ（２１１）から送信されるタグID取得要求を受信し，ステップＡで受信したタグID取得応答（６０２）をタグリーダ（２１１）に送信する。
【０１１７】
認証サーバ（２２１）は攻撃者から受信した認証用データと正規のタグ（２０１）から受信したデータを区別できないので，攻撃者は正規のタグになりすますことができる。
【０１１８】
そこで，図6のタグID取得要求に認証用のチャレンジコードr(t)を含める。また，タグ（２０１）は図7の認証コードを計算するステップ（７０２）において，チャレンジコードを認証コードを計算する関数の入力とし，認証コードを次のように計算する。
【０１１９】
h(i, t, r) = Mac(k(i), v(i, t), r(t))
このチャレンジコードr(t)は予測不可能な乱数を含む値で，時刻情報などを含んでも良い。
【０１２０】
図14はタグリーダのチャレンジを含む認証における認証サーバ（２２１）とＤＢサーバ（２３１）の動作を表すフローチャートである。以下，このフローチャートに従って認証サーバの動作を説明する。
【０１２１】
ステップ１（２６０２）．認証サーバ（２２１）はタグリーダ（２１１）から位置情報登録要求を受信すると，まずタグリーダ（２１１）の認証を行う。
【０１２２】
ステップ２（２６０３）．ＤＢサーバ（２３１）にタグＩＤ検索要求（６０６）を送信し，タグ（２０１）の可変ＩＤ v(i, t)を検索キーとしてDBのタグテーブル（２３４）から時刻tの可変IDを検索する。
【０１２３】
ステップ３（２６０４，２６０５）．ＤＢサーバ（２３１）はステップ２（２６０３）の検索で該当するタグＩＤが見つからなければ例外処理（１）に移行する。
【０１２４】
ステップ４（２６０６）．ＤＢサーバ（２３１）はステップ２（２１０３）の検索で該当するタグＩＤを見つけると，認証サーバ（２２１）は該当タグＩＤ（５０１）について照合のための認証コード値を次のようにして計算する。
【０１２５】
x(j) = Mac(k(j), v(i, t), r(t))
ステップ５（２６０７）．認証サーバ（２２１）は位置情報登録要求（６０３）で受け取った認証コードと，ステップ４（２６０６）で生成した検証用の認証コードの照合を行う。２つの認証コードが一致すればステップ６（２６０８）に移行する。一致しない場合にはステップ９（２６１２）に移行する。
【０１２６】
ステップ６（２６０８）．認証コードが一致した場合には，認証サーバ（２２１）はタグ（２０１）の新しい情報からなるエントリを以下のように作成する。
【０１２７】
位置情報（５０３）：pos
時刻t+1の可変ＩＤ（５０４）：v(j, t+1) = Next(k(j), v(i, t))
ステップ７（２６０９）．認証サーバ（２２１）はＤＢサーバ（２３１）に位置情報登録要求（６０８）を送信し，ステップ６で計算した新しいエントリをＤＢサーバ（２３１）に送信する。ＤＢサーバ（２３１）は位置情報登録要求（６０８）を受信すると，その情報に基づきタグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を返信する。
【０１２８】
ステップ８（２６１０，２６１１）．認証サーバ（２２１）はタグリーダ（２１１）に位置情報登録応答（６１０）を行い，タグ（２０１）が認証されたことをタグリーダ（２１１）に伝え，セッションを終了する。
【０１２９】
ステップ９（２６１２）．認証コードが一致しない場合には，位置情報登録要求は不正なものと判断し，位置情報登録要求（６０８）をＤＢサーバに送信する。ＤＢサーバ（２３１）はログにエラーを記録する。
【０１３０】
ステップ１０（２６１３，２６１４）．認証サーバ（２２１）は位置情報登録応答（６１０）として，タグリーダ（２１１）に認証が失敗したことを伝え，処理を終了する。
【０１３１】
図９に記載した例外処理（１）においても，同様に認証コードのチェックを行う。
【０１３２】
このように，タグの認証にチャレンジコードを含めることで，リプレイ攻撃を防ぐことができる。
＜図11＞
図１１は表示用携帯端末（２４１）からタグ（２０１）の現在位置を確認するためのプロトコルの概要を表した図である。以下，図１１に従って位置確認プロトコルを説明する。
【０１３３】
ステップ１．表示用携帯端末（２４１）は，アクセスポイント（１１０１）を介し，認証サーバ（２２１）に位置情報参照要求（１１０２）を行う。表示用端末（２４１）から認証サーバ（２２１）に送られる情報は端末のＩＤと認証コード，閲覧したいタグＩＤのリストである。必要であればこれらの情報は暗号化しておく。また，端末の認証はＨＭＡＣ認証方法の他，電子署名を利用した認証でも良い。
【０１３４】
ステップ２．認証サーバ（２２１）は，ＤＢサーバ（２３１）に端末ID検索要求（１１０３）を行う。
【０１３５】
ステップ３．ＤＢサーバ（２３１）は，表示端末テーブル（２３３）から端末IDを検索し，認証サーバ（２２１）に端末ID検索応答（１１０４）を行う。
【０１３６】
ステップ４．認証サーバ（２２１）は，端末ＩＤ検索応答（１１０４）を基に端末IDを認証後，ＤＢサーバ（２３１）に位置情報検索要求（１１０５）を行う。位置情報検索要求（１１０５）はタグＩＤのリストを含む。
【０１３７】
ステップ５．ＤＢサーバ（２３１）は，タグテーブル（２３４）とリーダテーブル（２３２）からタグの位置情報を検索し，認証サーバ（２２１）にタグの位置情報を含む位置情報検索応答（１１０６）を行う。
【０１３８】
ステップ６．認証サーバ（２２１）は，タグIDリストのタグIDの数だけステップ４），５）を繰り返し，すべてのタグについて位置情報を取得したら，アクセスポイント（１１０１）を介し，表示用携帯端末（２４１）に全タグIDの位置情報を含む位置情報検索応答（１１０７）を行う。
【０１３９】
ステップ７．表示用携帯端末（２４１）は，該当するタグの位置情報を表示装置（２４５）に表示する。
【０１４０】
このように，本実施形態によれば，
タグがサーバに送信するデータを（可変ＩＤ，照合用ハッシュ値）の組とし，可変ＩＤを検索キーとしてデータベースからタグの固定IDを検索することで，認証時のサーバの負荷を大幅に削減しつつ，IDの追跡を困難にする認証が可能である。このような特徴により，本実施形態の提供するタグ認証方法は大規模なシステムにおいてＩＤの追跡困難性を実現可能な認証システムを提供できる。
【０１４１】
プライバシを考慮した位置確認システムは，たとえば，来園者の多い大型レジャーパークなどにおける迷子捜索などにも応用することができる。
【図面の簡単な説明】
【０１４２】
【図１】本実施形態の機器構成を例示する図である。
【図２】本実施形態の機器構成における機器の実現例を例示する図である。
【図３】本実施形態のリーダテーブルの構成を例示する図である。
【図４】本実施形態の表示用端末テーブルの構成を例示する図である。
【図５】本実施形態のタグテーブルの構成を例示する図である。
【図６】本実施形態におけるタグ位置情報を登録するプロトコルの概要を例示する図である。
【図７】本実施形態のタグ位置情報を登録するプロトコルにおけるタグの処理を例示するフローチャートである。
【図８】本実施形態のタグ位置情報を登録するプロトコルにおける認証サーバおよびＤＢサーバの正常処理を例示するフローチャートである。
【図９】本実施形態のタグ位置情報を登録するプロトコルにおいて，同期ずれが発生した場合の認証サーバおよびＤＢサーバの処理を例示するフローチャートである。
【図１０】本実施形態のタグ位置情報を登録するプロトコルにおいて，タグテーブルの検索で要求に該当するタグを発見できなかった場合の認証サーバおよびＤＢサーバの処理を例示するフローチャートである。
【図１１】本実施形態において表示用携帯端末がタグの位置を確認するためのプロトコルの概要を例示する図である。
【図１２】本実施形態のタグリーダの配置を例示するイメージ図である。
【図１３】本実施形態のリーダテーブルの構成を例示する図である。
【図１４】本実施形態のタグ位置情報を登録する際にタグリーダの発信する乱数情報を利用するプロトコルにおける認証サーバおよびＤＢサーバの正常処理を例示するフローチャートである。
【符号の説明】
【０１４３】
２０１：タグ，２０２：通信装置，２０３：記憶装置，２０４：暗号処理装置，２０５：データ登録装置，
２１１：タグリーダ，２１２：通信装置，２１３：通信装置，２１４：暗号処理装置，２１５：データ登録・参照装置，
２２１：認証サーバ，２２２：通信装置，２２３：ＤＢアクセス装置，２２４：データ登録・参照装置，２２５：認証装置，２２６：暗号処理装置，
２３１：ＤＢ（データベース）サーバ，２３２：リーダテーブル，２３３：表示端末テーブル，２３４：タグテーブル，
２４１：表示用携帯端末，２４２：通信装置，２４３：記憶装置，２４４：暗号処理装置，２４５：表示装置，２４６：データ登録・参照装置，
【技術分野】
【０００１】
本発明は，ユーザのIDを認証する技術に関する。
【背景技術】
【０００２】
現在，携帯電話や非接触型ICカード，商品タグなどを含むユビキタスネットワークが急速に拡大している。これらの携帯端末の用途は多岐に渡るが，1つの大きな用途として端末とそれを持つユーザ（もしくは商品など）を関連付け，ユーザの位置や状態などを把握するシステムが検討されている。携帯電話やICカードを使った電子マネーサービスや入退出管理システム，バーコードの代わりに無線タグを使った商品管理などはその実例である。
【０００３】
これらの機器(以下，一括してタグと称す)は各々が固有のＩＤを持ち，タグリーダからの要求に応えてＩＤやその他のデータをリーダを介してシステムを管理するサーバに送信する。このデータを蓄積することで，タグと関連付けられたユーザ(もしくは機器，商品)の管理が可能となり，商品の流通経路監視やユーザの位置確認などを行うことができる。このようなシステムで重要なことは，タグから送信されるデータの信頼性であり，データが（１）正規のタグから送信されたデータであること，（２）通信路上でデータが改ざんされていないこと，などをチェックするための仕組みが必要となる。このため，ＩＤやデータの完全性を検証するための認証コードを送信データに付加することが望ましい。
【０００４】
ユーザＩＤの正当性を検証するためにもっとも広く用いられているのがパスワード認証であるが，通常のパスワード認証ではパスワード自体が通信路上を流れるため，インターネット通信や無線通信での利用には適していない。このような公開通信路では，ＣＨＡＰ(Ｃｈａｌｌｅｎｇｅ Ｈａｎｄｓｈａｋｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ Ｐｒｏｔｏｃｏｌ)などを利用する。
【０００５】
ＣＨＡＰ認証は，公開通信路上で利用してもタグの秘密情報(固有鍵k(I)など)が漏洩しない他，ＩＤ取得要求ごとにサーバが乱数を生成し，認証コード(ハッシュ値)の再利用ができない。このため，リプレイ攻撃を防止することができる。
【０００６】
このようにＣＨＡＰ認証は優れた認証技術であるが，ユビキタスネットワークには適さない面もある。たとえば近年，プライバシ保護の観点から追跡可能性という新しい安全性の概念が発生した。追跡可能性とは，文字通りある特定のユーザやＩＤの行動を追跡できるかどうか，というものである。ＣＨＡＰなどの既存の認証技術では，まずサーバにＩＤを送信するため，通信を傍受する攻撃者は常にＩＤを得ることができる。したがって，通信を傍受し続けることで個人の位置を把握することが可能である。また，他のＩＤ（商品タグ）との組み合わせにより，ある個人の嗜好などを分析することも可能となる。これは上記のプライバシ保護の観点からして望ましくない性質である。また，通信を傍受し続けることで，第三者により行動が追跡される畏れもある。このような用途においては，タグの追跡が困難な認証方法を使用する必要がある。
【０００７】
これに対し，ＩＤを秘匿したまま認証を行う方法が提案されている。通常の認証では，タグのＩＤを検索キーとして，検証に必要なデータをデータベースから抽出するが，これらの方法では検索キーを使わずに，データベースの全件検索を行うことを基本アイデアとしている(非特許文献１，２参照)。
【０００８】
【非特許文献１】Stephen A. Weis Security and privacy in Radio-Frequency Identification Devices ，[Online]， MIT，２００３年５月９日，ｐ．４０−４２，[２００５年１月２８日検索]，インターネット＜URL: http://theory.lcs.mit.edu/~sweis/pdfs/masters.pdf＞
【非特許文献２】大久保美也子，鈴木幸太郎，木下真吾，「Forward-secure RFID privacy protection for low-cost RFID」， コンピュータセキュリティシンポジウム CSS 2003予稿集，２００３年１０月３１日，ｐ．４９３−４９４
【発明の開示】
【発明が解決しようとする課題】
【０００９】
非特許文献１に記載されている認証方法では，認証の際にIDを送信せず，乱数に依存するハッシュ値のみを送信して認証を行うことで，追跡困難性を実現している。また，非特許文献２に記載されている認証方法では，ＩＤを通信を行うたびに更新し，ＩＤから計算されるハッシュ値を送信して認証を行うことで追跡困難性を実現している。
【００１０】
しかし，非特許文献１，２に記載されている認証方法は，いずれも検索用のキーを送信しないことでプライバシをIDを秘匿したまま認証を行い，照合の際にデータベースに登録されているIDすべてについて照合を行う。すなわち，IDをデータベースから検索するためのキーがないため，データベースの全件検索を行う必要がある。
【００１１】
このため，データベース(もしくは認証用サーバ)の負荷が従来のCHAPなどに比べてひじょうに大きく，大規模なシステムには不向きであった。しかしその一方で，このようなプライバシ保護が可能な認証方法はユビキタス環境においてその真価を発揮する。また，主な用途として期待されているのも不特定多数のユーザを識別する大規模システムである。
【００１２】
したがって，プライバシ保護が可能で，かつ，大規模システムに適した認証技術が望まれている。
【課題を解決するための手段】
【００１３】
本発明は，このような事情を鑑みてなされたもので，送受信データからIDを追跡することを困難にしつつ，サーバ側における照合の負荷を軽減する認証技術を提供するものである。
【００１４】
本発明はIDの追跡を困難にする認証方法であって，非特許文献１に記載されている認証方法の欠点を克服する技術を提供する。本発明は以下の３点を主な特徴とする。
【００１５】
１．送信するデータに検索キーとして可変のＩＤを含める
２．可変のＩＤは通信を行うたびに更新する
３．可変のＩＤを更新するときには秘密鍵を利用し，異なる可変のＩＤを結びつけることを困難にする
さらに詳しく述べると，本発明の提供する認証方法では，タグに対して，固有の固定ＩＤと固有の秘密鍵を定める。これらの値はタグごとに異なる。さらに，タグごとに異なる，通信を行うたびに変更される値を定める。この値を以下では可変ＩＤと称す。タグは秘密鍵と可変ＩＤを記憶しており，タグがサーバに送信するデータを（可変ＩＤ，照合用ハッシュ値）の組とする。ここで，照合用ハッシュ値は可変ＩＤと秘密鍵から計算される値である。サーバでは，受信したデータのうち，可変ＩＤを検索キーとしてデータベースからタグの固定IDを検索することで，認証時のサーバの負荷を大幅に削減することができる。また，タグはＩＤ取得要求への応答があるたびに，可変ＩＤと秘密鍵から新しい可変ＩＤを計算することで追跡困難性を実現する。
【００１６】
より具体的な，本発明の態様は，たとえば，通信装置１と記憶装置１と暗号処理装置１とを備える１個以上のタグと，通信装置２と記憶装置２と暗号処理装置２とを備えるタグ認証装置からなるシステムにおいてタグ認証装置がタグからの通信を識別するための方法であって，タグが備える記憶装置１には秘密鍵１と1回の通信ごとに更新される可変ＩＤ１が記憶されており，タグ認証装置の記憶装置２には各々のタグの情報を記録したタグテーブルが記憶されており，タグテーブルはタグのＩＤと各タグに対応する秘密鍵２と各タグに対応する可変ＩＤ２の値を項目として含んでおり，タグが備える暗号処理装置１は認証コード生成装置１，可変ＩＤ更新装置１を備え，タグ認証装置の暗号処理装置２は認証コード生成装置２，可変ＩＤ更新装置２を備え，タグ認証装置は，通信装置２を介して，繰り返し（例えば定期的に）タグに対して認証を要求する信号を発信し，タグは，信号を受信すると可変ＩＤ１と秘密鍵１とを認証コード生成装置１の入力として認証コード１を生成し，信号に対する応答として，可変ＩＤ１と，認証コード１とを通信装置１を介してタグ認証装置に送信し，秘密鍵１と可変ＩＤ１とを可変ＩＤ更新装置１の入力として新しい可変ＩＤを計算し，その結果を記憶装置１に記憶し，タグ認証装置は，タグからの応答を受信すると応答に含まれる可変ＩＤ１を検索キーとしてタグテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，可変ＩＤ１と秘密鍵２を可変ＩＤ更新装置２の入力として新しい可変ＩＤを計算し，その結果を記憶装置２に記憶することを特徴とする。
【００１７】
さらに，暗号処理装置１および暗号処理装置２は，一方向性ハッシュ関数を１つ以上備えてもよい。
【００１８】
さらに，認証コード生成装置は，一方向性ハッシュ関数Hashを使って，認証コードC
C = Hash(k||v(t)||0)
(ただし，kは該当タグの秘密鍵，v(t)はタグが現在記憶している可変ＩＤとし，k||v(t)||0は秘密鍵と可変ＩＤと０からなるビット列のビット列としての連結を指す)
を生成してもよい。
【００１９】
さらに，可変ＩＤ更新装置は，一方向性ハッシュ関数Hashを使って，新しい可変ＩＤ v(t+1)
v(t+1) = Hash(k||v(t)||1)
(ただし，kは該当タグの秘密鍵，v(t)はタグが現在記憶している可変ＩＤとし，k||v(t)||1は秘密鍵と可変ＩＤと1からなるビット列のビット列としての連結を指す)
を生成してもよい。
【００２０】
さらに，タグテーブルは，さらにすべてのタグについて複数回分の可変ＩＤ v(t+1)〜v(t+M)を記憶してもよい。
【００２１】
さらに，検索キーがタグテーブルに記載されている可変ＩＤ v(t)に該当しない場合に，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行ってもよい。
【００２２】
さらに，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，タグテーブルに記憶されているすべてのタグＩＤごとに対応する秘密鍵と応答に含まれる可変ＩＤ１とを，認証コード生成装置２に入力して得られた値と応答に含まれている認証コード１とを照合し，２つの値が一致するタグＩＤを該当タグと識別してもよい。
【００２３】
さらに，タグ認証装置が発信する認証を要求する信号は乱数情報を含んでおり，タグは信号を受信すると，可変ＩＤ１と秘密鍵１と信号に含まれる乱数情報とを認証コード生成装置１の入力として認証コード１を生成し，信号に対する応答として，可変ＩＤ１と，認証コード１とを通信装置１を介してタグ認証装置に送信し，タグ認証装置はタグからの応答を受信すると，応答に含まれる可変ＩＤ１を検索キーとしてタグテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，応答に含まれる可変ＩＤ１と秘密鍵2と発信した乱数情報とを認証コード生成装置２に入力して得られた値と，応答に含まれる認証コード1を照合することで，応答が発信した信号に対する応答であることを確認してもよい。
【００２４】
また，本発明のほかの具体的態様は，無線通信装置１と記憶装置１と暗号処理装置１とを備える１個以上のタグと，通信装置２と記憶装置２と暗号処理装置２とを備えるタグ認証装置と，タグと通信するための無線通信装置２と，タグ認証装置と通信するための通信装置１とを備える１個以上のタグリーダとからなる無線タグ位置登録システムであって，タグが備える記憶装置１には秘密鍵１と1回の通信ごとに更新される可変ＩＤ１が記憶されており，タグ認証装置の記憶装置２には各々のタグの情報を記録したタグテーブルとタグリーダの情報を記録したリーダテーブルが記憶されており，タグテーブルはタグのＩＤと各タグの現在位置，各タグに対応する秘密鍵２，各タグに対応する可変ＩＤ２の値を項目として含んでおり，リーダテーブルはタグリーダのＩＤと各タグリーダを設置した場所の情報を項目として含んでおり，タグが備える暗号処理装置１は認証コード生成装置１，可変ＩＤ更新装置１を備え，タグ認証装置の暗号処理装置２は認証コード生成装置２，可変ＩＤ更新装置２を備え，無線通信装置１と無線装置２は一定距離以下でのみ通信可能であり，タグリーダは無線通信装置２を介して，繰り返し（例えば定期的に）認証を要求する信号をブロードキャストし，タグは前記ブロードキャストされた信号を受信すると，可変ＩＤ１と秘密鍵１とを認証コード生成装置１の入力として認証コード１を生成し，信号に対する応答として，可変ＩＤ１と，認証コード１とを含むデータを通信装置１を介してタグリーダに送信し，秘密鍵１と可変ＩＤ１とを可変ＩＤ更新装置１の入力として新しい可変ＩＤを計算し，その結果を記憶装置１に記憶し，タグリーダは，タグからの通信を受信するとタグからの通信で受信したデータにタグリーダのＩＤを付加し，通信装置２を介してタグ認証装置に位置登録要求信号として送信し，タグ認証装置は，タグリーダからの位置登録要求信号を受信すると位置情報登録要求信号に含まれる可変ＩＤ１を検索キーとしてタグテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，可変ＩＤ１と秘密鍵２を可変ＩＤ更新装置２の入力として新しい可変ＩＤを計算し，位置情報登録要求信号に含まれるタグリーダのＩＤを検索キーとしてリーダテーブルからタグリーダの位置情報を取得し，タグリーダの位置情報と新しい可変ＩＤを記憶装置２に記憶することを特徴とする。
【００２５】
さらに，暗号処理装置１および暗号処理装置２は，一方向性ハッシュ関数を１つ以上備えてもよい。
【００２６】
さらに，認証コード生成装置は，一方向性ハッシュ関数Hashを使って，認証コードC
C = Hash(k||v(t)||0)
(ただし，kは該当タグの秘密鍵，v(t)はタグが現在記憶している可変ＩＤとし，k||v(t)||0は秘密鍵と可変ＩＤと０からなるビット列のビット列としての連結を指す)
を生成してもよい。
【００２７】
さらに，可変ＩＤ更新装置は，一方向性ハッシュ関数Hashを使って，新しい可変ＩＤ v(t+1)
v(t+1) = Hash(k||v(t)||1)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||1は前記秘密鍵と前記可変ＩＤと1からなるビット列のビット列としての連結を指す)
を生成してもよい。
【００２８】
さらに，タグテーブルは，さらにすべてのタグについて複数回分の可変ＩＤ v(t+1)〜v(t+M)を記憶してもよい。
【００２９】
さらに，検索キーがタグテーブルに記載されている可変ＩＤ v(t)に該当しない場合に，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行ってもよい。
【００３０】
さらに，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，タグテーブルに記憶されているすべてのタグＩＤごとに対応する秘密鍵と応答に含まれる可変ＩＤ１とを，認証コード生成装置２に入力して得られた値と応答に含まれている認証コード１とを照合し，２つの値が一致するタグＩＤを該当タグと識別してもよい。
【００３１】
さらに，リーダテーブルは各々のタグリーダに近い位置にあるタグリーダのＩＤとを項目として含んでおり，あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，位置情報登録要求に含まれているタグリーダのＩＤを検索キーとして，リーダテーブルから位置情報登録要求を送信したタグリーダに近い位置にあるタグリーダのリストを取得し，位置情報登録要求に含まれているタグリーダとリストに含まれるタグリーダに対応する位置情報を検索キーとしてタグテーブルを検索し，タグテーブルの位置情報の項目が検索キーのいずれかに合致するすべてのタグＩＤごとに対応する秘密鍵と応答に含まれる可変ＩＤ１とを，認証コード生成装置２に入力して得られた値と応答に含まれている認証コード１とを照合し，２つの値が一致するタグＩＤを該当タグと識別してもよい。
【００３２】
また，タグリーダが発信する認証を要求する信号は乱数情報を含んでおり，タグは上記信号を受信すると，可変ＩＤ１と秘密鍵１と乱数情報とを認証コード生成装置１の入力として認証コード１を生成し，信号に対する応答として，可変ＩＤ１と，認証コード１とを通信装置１を介してタグ認証装置に送信し，タグリーダはタグからの応答を受信すると，タグからの通信で受信したデータにタグリーダのＩＤと上記乱数情報とを付加し，通信装置２を介してタグ認証装置に位置登録要求信号を送信し，タグ認証装置は，位置登録要求信号を受信すると位置登録要求信号に含まれる可変ＩＤ１を検索キーとしてテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，位置登録要求信号に含まれる可変ＩＤ１と秘密鍵2と発信した乱数情報とを認証コード生成装置２に入力して得られた値と，位置登録要求信号に含まれる認証コード1を照合することで，タグの応答がタグリーダが発信した信号に対する応答であることを確認してもよい。
【００３３】
また，タグリーダは，さらに記憶装置３と暗号処理装置３とを備え，記憶装置３は秘密鍵３を記憶しており，暗号処理装置３は乱数生成装置３と認証コード生成装置３とを備え，タグリーダはタグからの通信を受信すると，暗号処理装置３を用いて乱数を生成し，秘密鍵３と上記乱数を認証コード生成装置３への入力とし，得られた値をタグリーダＩＤに対する認証コードとして，タグ認証装置に送信する位置登録要求信号に付加してタグ認証装置に送信してもよい。
【００３４】
さらに，通信装置４を備える１個以上の表示用端末と，通信装置５を備える１個以上のアクセスポイントと，を備え，表示用端末は，通信装置４を介して上記アクセスポイントに接続し，タグ認証装置にタグ位置閲覧要求を送信し，タグの現在位置を取得してもよい。
【００３５】
さらに，タグ認証装置の記憶装置２は表示用端末テーブルとを備え，表示端末テーブルは端末のＩＤと，各タグが閲覧してよいタグのＩＤからなるリストとを含み，タグ位置閲覧要求は表示用端末のＩＤを含み，タグ認証装置は，表示用端末からのタグ位置閲覧要求に対し，タグ位置閲覧要求に含まれる表示用端末のＩＤを検索キーとして表示用端末テーブルを検索し，要求を行った表示用端末が閲覧可能なタグＩＤのリストを取得し，リストに含まれる各タグＩＤを検索キーとしてタグテーブルを検索し，各タグの位置情報を取得し，取得した情報を表示用端末に返信してもよい。
【００３６】
さらに，表示用端末は，さらに暗号処理装置を備え，タグ認証装置との通信を暗号化してもよい。
【００３７】
上記のように，本発明の認証方法ではサーバに送信するデータに検索キーとして使用できる可変のＩＤを含めるため，サーバは受信したデータがどのタグから送信されたものかを少ない負荷で，データベースから探し出すことができる。
【発明の効果】
【００３８】
本発明によれば，認証時のサーバの負荷を大幅に削減することができる。この結果，大規模なシステムにおいてＩＤの追跡困難性を実現可能な認証システムを提供できる。
【発明を実施するための最良の形態】
【００３９】
以下に，本発明を適用する実施形態を説明する。
【００４０】
本実施形態は無線タグを利用したユーザの位置確認システムであり，ユーザは無線タグを携帯しているものとする。システムは一定の監視区域を対象とし，この区域内にタグリーダを設置する。タグリーダは一定時間おきにタグＩＤ取得要求をブロードキャストする。通信可能距離内に無線タグが存在すれば，タグは要求に対して応答する。タグリーダは受信した応答を認証サーバに転送し，認証サーバはタグの認証を行う。本実施形態では，タグリーダがタグからの応答を認証サーバに転送する際にタグリーダのＩＤを同時に送信することで，タグリーダの設置位置とタグを関連付け，タグの現在位置を確認する。
【００４１】
このようなシステムでは，通信可能距離を半径とする円で監視区域を充填することで，区域内のユーザの行動を完全に捕捉することができる。たとえば，遊園地などの大型レジャー施設で，幼児などにタグを配布して迷子の捜索を容易にするようなシステムでは，このように監視区域を充填するようにタグリーダを配置することで，漏れなく幼児の位置を確認することができる。
【００４２】
また，大型店舗などでは，たとえばエレベータや階段などフロアへの出入り口にタグリーダを設置することで，大雑把にユーザが何階にいるかを確認することができる。同様に，ビルの入口などで緩やかな入退出管理を行うことも可能である。
＜図1＞
図１は本実施形態のシステム構成を表した図である。本実施形態は，タグ（２０１），タグリーダ（２１１），認証サーバ（２２１），データベース（ＤＢ）サーバ（２３１），表示用携帯端末（２４１）からなるシステムである。
【００４３】
タグ（２０１）は記憶装置（２０３）と通信装置（２０２），タグ（２０１）の認証コードの生成などを行うための暗号処理装置（２０４），データ処理を統括するデータ登録装置（２０５）からなる。
【００４４】
タグリーダ（２１１）はタグ（２０１）と通信するための通信装置１（２１２），認証サーバと通信するための通信装置２（２１３），リーダの認証コード生成などを行う暗号化装置（２１４），データ処理を統括するデータ登録・参照装置（２１５）からなる。図ではタグ，タグリーダは１つであるが，一般には一つ以上のタグ，一つ以上のタグリーダからなるシステムである。
【００４５】
認証サーバ（２２１）はタグリーダ（２１１）や表示用携帯端末（２４１）と通信を行うための通信装置（２２２），ＤＢアクセス装置（２２３），タグ（２０１）やタグリーダ（２１１）の認証を行うための認証装置（２２５），検証用の認証コード生成などを行う暗号化装置（２２６），データ処理を統括するデータ登録・参照装置（２２４）からなる。
【００４６】
ＤＢサーバ（２３１）はタグリーダのＩＤと位置情報（タグリーダの設置位置）からなるリーダテーブル（２３２），表示用携帯端末のＩＤと各端末が閲覧可能なタグのＩＤからなる携帯端末テーブル（２３３），タグのＩＤとタグの固有鍵，タグの可変ＩＤからなるタグテーブル（２３４）からなる。
【００４７】
表示用携帯端末（２４１）は認証サーバと通信するための通信装置（２４２），記憶装置（２４３）と携帯端末の認証に必要な計算を行う暗号化装置（２４４），表示装置（２４５），およびデータ処理を統括するデータ登録・参照装置（２４６）からなる。
【００４８】
これらの機器はネットワーク（２５１）を通じて互いに通信することができる。
【００４９】
本実施形態では，ユビキタスネットワークで用いられるＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）タグと同じく，タグ（２０１）とタグリーダ（２１１）の間の通信は無線通信を想定しているが，通常の有線による通信でも良い。また，タグリーダ（２１１），認証サーバ（２２１），表示用携帯端末（２４１）はＬＡＮなどの有線ネットワークで繋がっていることを想定しているが，表示用携帯端末（２４１）などは無線通信でこのネットワークに接続しても良い。また，ＤＢサーバ（２３１）もこのネットワークに接続しても良い。
＜図2＞
次に，認証サーバ（２２１）を実現するものとして，たとえば図２のＰＣ（１０１）を例に説明する。ＰＣ（１０１）はＣＰＵ（１０２），メモリ（１０３），ハードディスクなどの外部記憶装置（１０４），通信インターフェース（ＩＦ）（１０５），周辺機器接続ＩＦ（１０６）からなり，周辺接続機器ＩＦ（１０６）を通じてモニタ（１０７）と接続している。
【００５０】
外部記憶装置（１０４）には，暗号処理装置（２２６）を実現する暗号処理プログラム（１０８），認証装置（２２５）を実現する認証プログラム（１０９）などが格納されている。また，外部記憶装置（１０４）には，ＬＡＮやインターネットなどのネットワーク（１１０）に接続する通信ＩＦ（１０５）と協働して通信装置（２２２）を実現するプログラムや，周辺機器接続ＩＦ（１０６）と協働してDBアクセス装置（２２３）を実現するプログラムも格納されている。さらにＤＢサーバプログラムを外部記憶装置（１０４）内に内蔵しても良い。
【００５１】
そして，ＣＰＵ（１０２）がメモリ（１０３），外部記憶装置（１０４）に格納されたプログラムを実行することにより，認証サーバ（２２１）の各機能が実現する。
【００５２】
その他，タグ（２０１），タグリーダ（２１１），ＤＢサーバ（２３１），表示用携帯端末（２４１）は，いずれもＰＣ（１０１）と同様の構成を備える情報処理装置において，ＣＰＵ（１０２）がメモリ（１０３），または外部記憶装置（１０４）に格納されたプログラムを実行することにより具現化されるものである。
【００５３】
これらのプログラムは，あらかじめ，上記ＰＣ（１０１）または情報処理装置内のメモリに格納されていても良いし，必要なときに，情報処理装置が利用可能な，着脱可能な記憶媒体または通信媒体を介して，他の装置から導入されてもよい。通信媒体とは，ネットワークまたはネットワーク上の搬送波やデジタル信号を指す。
【００５４】
なお，ＤＢサーバ（２３１）は周辺機器接続ＩＦ（１０６）や通信ＩＦ（１０５）を通じて外部接続のハードディスクなどの外部記憶装置やネットワーク（２５１）に接続された別のＰＣやストレージとして実現されたＤＢサーバ（２３１）として実現しても良い。
【００５５】
また，認証サーバ（２２１），タグ（２０１），タグリーダ（２１１），ＤＢサーバ（２３１），表示用携帯端末（２４１）のいずれかの，一部または全部をハードウェアで実現することも可能である。
＜図3＞
図３はＤＢサーバ（２３１）に記憶されているリーダテーブル（２３２）の構成図である。リーダテーブル（２３２）の項目はタグリーダＩＤ（３０１）と位置情報（３０２）である。位置情報（３０２）は，タグリーダ（２１１）を設置した位置を表す情報で，システムの構成時に設定する。
＜図4＞
図４はＤＢサーバ（２３１）に記憶されている表示端末テーブル（２３３）の構成図である。表示端末テーブル（２３３）の項目は表示端末ＩＤ（４０１）と，各表示端末から情報を取得できるタグ（２０１）のリスト（４０２）である。
＜図５＞
図５はＤＢサーバ（２３１）に記憶されているタグテーブル（２３４）の構成図である。タグテーブル（２３４）の項目はタグリーダＩＤ（５０１）とタグの固有鍵（５０２），タグの位置情報（５０３），そしてタグの可変ＩＤ（５０４）である。タグの可変ＩＤは現在時刻tについてのみ記憶しても良いが，本実施形態では同期ずれ(後述)に対応するために何回か先の可変ＩＤについてもあらかじめ計算して可変ＩＤの未来値（５０５）として記憶しておく。
＜図6＞
図６はタグの位置情報をＤＢサーバに登録するためのプロトコルである。ステップ４のタグ（２０１）からのタグＩＤ取得応答（６０１）とステップ８のタグ認証は固定ＩＤを秘匿する認証方法によるものである。タグ（２０１）と認証サーバ（２２１）の処理の詳細は後述する。
【００５６】
ステップ１．タグリーダ（２１１）から近傍のタグ（２０１）に対し，タグID取得要求（６０１）を行う。
【００５７】
ステップ２．タグ（２０１）は，タグリーダ（２１１）にタグID取得応答（６０２）を行う。
【００５８】
ステップ３．タグリーダ（２１１）は，認証サーバ（２２１）に位置情報登録要求（６０３）を行う。
【００５９】
ステップ４．認証サーバ（２２１）は，ＤＢサーバ（２３１）にリーダID検索要求（６０４）を行う。
【００６０】
ステップ５．ＤＢサーバ（２３１）は，リーダテーブル（２３２）からリーダID ridを検索し，認証サーバ（２２１）にリーダID検索応答（６０５）を行う。
【００６１】
ステップ６．認証サーバ（２２１）は，タグリーダ（２１１）を認証後，ＤＢサーバ（２３１）にタグID検索要求（６０６）を行う。
【００６２】
ステップ７．ＤＢサーバ（２３１）は，タグテーブル（２３４）からタグIDを検索し，認証サーバ（２２１）にタグID検索応答（６０７）を行う。
【００６３】
ステップ８．認証サーバ（２２１）は，タグIDを認証後，ＤＢサーバ（２３１）に位置情報登録要求（６０８）を行う。
【００６４】
ステップ９．ＤＢサーバ（２３１）は，タグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を行う。
【００６５】
ステップ１０．認証サーバ（２２１）は，タグリーダ（２１１）に位置情報登録応答（６１０）を行う。
＜図7＞
図７はタグリーダ（２１１）からＩＤ取得要求（６０１）を受信したタグ（２０１）の動作を表すフローチャートである。タグ（２０１）は記憶装置（２０３）にタグ固有鍵k(i)（５０２）と可変ＩＤ v(i, t) （５０４）を記憶しているものとする。タグ（２０１）はタグリーダ（２１１）からＩＤ取得要求（６０１）を受信すると，以下の以下のステップにしたがって処理を行う。
【００６６】
ステップ１（２００２）．タグ（２０１）は暗号処理装置（２０４）にタグ固有鍵k(i) （５０２）と可変ＩＤ v(i, t) （５０４）を入力し，認証コードを次のように計算する。
【００６７】
h(i, t) = Mac(k(i), v(i, t))
ここで，Mac(x, y)は認証コードを計算するための関数である。この関数はＳＨＡ−１などのハッシュ関数を用いたＨＭＡＣや，ＡＥＳなどのブロック暗号を用いたＣＭＡＣなどの標準的なメッセージ認証子生成方法を用いれば良い。また，単にタグ固有鍵k(i) （５０２）と可変ＩＤ v(i, t) （５０４）を連結したものをＳＨＡ−１などのハッシュ関数で処理し，その出力を認証コードh(i, t)としても良い。
【００６８】
ステップ２（２００３）．タグ（２０１）はＩＤ取得応答（６０２）としてT(i, t) = (v(i, t),h(i, t))をタグリーダ（２１１）に送信する。
【００６９】
ステップ３（２００４）．タグ（２０１）は暗号処理装置（２０４）にタグ固有鍵k(i)（５０２）と時刻t(現在)の可変ＩＤ v(i, t)（５０４）を入力し，時刻t+1の可変ＩＤを次のように計算する。
【００７０】
v(i, t+1) = Next(k(i), v(i, t))
ここで，Nextは可変ＩＤの更新を行う関数であり，認証コードを計算するための関数Macとは異なるものを用いる。たとえば，認証コードを計算する関数MacとしてSHA1(k(i)||v(i, t)||0)，状態更新を行う関数NextとしてSHA1(k(i)||v(i, t)||1)などを用いる。
【００７１】
新しい可変ＩＤ v(i, t+1)はデータ登録装置（２０５）を介して記憶装置（２０３）に格納される。
【００７２】
ステップ４（２００６）．タグ（２０１）は処理を終了し，待機状態に移行する。
【００７３】
待機状態にあるタグ（２０１）はＩＤ取得要求（６０１）を受けると上記のステップを繰り返す。タグリーダ（２１１）からのＩＤ取得要求（６０１）が頻繁にある場合や，タグリーダ1個あたりの通信可能エリアが広い場合には，一定時間の休止を設定すれば良い。
＜図8＞
図８はタグリーダ（２１１）からの位置情報登録要求（６０３）を受信した認証サーバ（２２１）およびＤＢサーバ（２３１）の動作を表すフローチャートである。以下，このフローチャートに従って認証サーバの動作を説明する。
【００７４】
ステップ１（２１０２）．認証サーバ（２２１）はタグリーダ（２１１）から位置情報登録要求を受信すると，まずタグリーダ（２１１）の認証を行う。この認証は別途ＣＨＡＰなどのプロトコルを実行しても良いし，電子署名などを用いた認証を行っても良い。電子署名を用いた認証であれば，認証サーバ（２２１）はリーダＩＤ検索要求（６０４）をＤＢサーバ（２３１）に送信し，ＤＢサーバ（２３１）からのリーダＩＤ検索応答（６０５）としてタグリーダ（２１１）の公開鍵を受け取り，位置情報登録要求（６０３）に含まれているタグリーダ（２１１）の署名を検証する。また，この際にＤＢサーバ（２３１）からタグリーダ（２１１）の位置情報posを取得しておく。
【００７５】
なお，ＣＨＡＰによる認証の概要は次の通りである。
【００７６】
ステップA．サーバSはタグリーダＲにＩＤ取得要求を送信する。
【００７７】
ステップB．サーバＳは乱数randを生成し，タグリーダＲに送信する。
【００７８】
ステップC．タグリーダＲはサーバSにＩＤと乱数rand，ハッシュ値h = Hash(k(Ｒ), rand)の組 (Ｒ, rand, h) を送信する。ここでk(Ｒ)はタグリーダＲの固有鍵である。
【００７９】
ステップD．サーバSはデータベースに登録されているタグリーダのリストからタグＲに対応する固有鍵k（Ｒ）を取り出し， ハッシュ値h’ = Hash(k(Ｒ), rand) を計算する。
【００８０】
ステップE．サーバＳはh = h’ であればＩＤを認証する。 h ≠ h’ であれば，サーバS はタグリーダからの応答が不正なものであると判断する。
【００８１】
ステップ２（２１０３）．ＤＢサーバ（２３１）にタグＩＤ検索要求（６０６）を送信し，タグ（２０１）の可変ＩＤ v(i, t)を検索キーとしてDBのタグテーブル（２３４）から時刻tの可変IDを検索する。
【００８２】
ステップ３（２１０４，２１０５）．ＤＢサーバ（２３１）はステップ２（２１０３）の検索で該当するタグＩＤが見つからなければ例外処理（１）に移行する。
【００８３】
ステップ４（２１０６）．ＤＢサーバ（２３１）はステップ２（２１０３）の検索で該当するタグＩＤを見つけると，タグＩＤ検索応答（６０７）として該当するタグのID（５０１）と付随するエントリ（５０２〜５０５）を認証サーバ（２２１）に送信する。，認証サーバ（２２１）は可変ＩＤの未来値（５０５）の最後の値(時刻t+Mの値) v(i', t+M)を取り出し，時刻t+M+1の可変ＩＤを次のように計算する。
【００８４】
v(i', t+M+1) = Next(k(i'), v(i', t+M))
ステップ５（２１０７）．認証サーバ（２２１）は，受信したエントリについて「現在の可変ＩＤ」（５０４）の項目をv(i', t+1)で書き換える。また，可変ＩＤの未来値（５０５）についても，一つずつ位置を繰り上げていき，リストの最後に新しく計算した時刻t+M+1の可変ＩＤ v(i', t+M+1)を追加する。さらにエントリの位置情報（５０３）を位置情報登録要求（６０３）に含まれる位置情報posに書き換える。
【００８５】
認証サーバ（２２１）はＤＢサーバ（２３１）に位置情報登録要求（６０８）を送信し，計算した新しいエントリをＤＢサーバ（２３１）に送信する。ＤＢサーバ（２３１）は位置情報登録要求（６０８）を受信すると，その情報に基づきタグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を返信する。
【００８６】
ステップ６（２１０８，２１０９，）．認証サーバ（２２１）はタグリーダ（２１１）に位置情報登録応答（６１０）を行い，タグ（２０１）が認証されたことをタグリーダ（２１１）に伝え，セッションを終了する。
【００８７】
このように，本実施形態ではタグから受信した可変ＩＤに対応する値がタグテーブル（２３４）から見つかればタグからの通信が正当なものであるとみなす。
【００８８】
なお，ここでは認証サーバ（２２１）はタグリーダ（２１１）からの位置情報登録要求（６０３）ごとにＤＢサーバ（２３１）にタグＩＤ検索要求（６０６）を出しているが，システムを稼動させるにあたって，あらかじめＤＢのタグテーブル（２３４）などを認証サーバ（２２１）のメモリ上などに展開しておくことでＤＢサーバ（２３１）へのアクセスを削減し，検索を高速に処理することができる。また，認証サーバ（２２１）からタグリーダ（２１１）への位置情報登録応答（６１０）は省略しても良い。
＜図9＞
図９は図８のフローチャートのステップ３で例外処理（１）に移行した場合のＤＢサーバ（２３１）および認証サーバ（２２１）の動作を表したフローチャートである。
【００８９】
例外処理（１）は，可変ＩＤの同期ずれを想定したものである。本実施形態の主眼はデータベースの検索キーとして可変ＩＤを使うことで，ＩＤの秘匿性とデータベースの検索可能性を同時に実現することである。ＩＤの秘匿性(追跡困難性)を実現するために，可変ＩＤは通信を行うごとに更新する必要がある。しかしたとえば，ユーザがタグリーダ（２１１）の通信可能領域の縁を掠めた場合や電波障害などが発生した場合には，タグ（２０１）はタグＩＤ取得要求（６０１）を受け取り図７のフローに従ってタグＩＤ取得応答を返すが，タグリーダ（２１１）がタグ（２０１）からのタグＩＤ取得応答（６０２）を受信できない可能性がある。このような場合には，タグ（２０１）のみが可変ＩＤの更新を行い，タグテーブル（２３４）の情報は更新されない。すなわち，タグの記憶している可変ＩＤとタグテーブル（２３４）の記憶している現在の可変ＩＤ（５０４）の間にずれが生じる。これが可変ＩＤの同期ずれである。
【００９０】
以下，図９に従って可変ＩＤの同期ずれが発生した場合の処理について説明する。
【００９１】
ステップ１（２２０２）．図８のフローチャートのステップ３（２１０４）で該当する現在の可変ＩＤ（５０４）が見つからなかった場合，ＤＢサーバはv(i, t)を検索キーとしてDBのタグテーブル（２３４）から可変IDの予測値のリスト（５０５）を検索する。
【００９２】
ステップ２（２２０３，２２０４）．タグテーブル（２３４）のリストにv(i, t)と一致する可変ＩＤが見つからなかった場合には例外処理（２）へ移行する。一致する可変ＩＤが見つかった場合にはステップ３以下の処理を行う。
【００９３】
ステップ３（２２０５）．ＤＢサーバ（２３１）はタグＩＤ検索応答（６０７）として該当するタグのID（５０１）と付随するエントリ（５０２〜５０５），同期ずれの量d (v(i, t) = v(i', t+p))を認証サーバ（２２１）に送信する。
【００９４】
，認証サーバ（２２１）はタグ（２０１）の新しい情報からなるエントリを以下のように作成する。
【００９５】
位置情報（５０３）：pos
現在の可変ＩＤ（５０４）：v(i', t+d+1)
可変ＩＤの未来値のリスト（５０５）：
v(i', t+x) = v(i', t+d+1+x), 0 < x < M-d
v(i', t+x) = Next(k(i'), v(i', t+d+x)), M-d <= x <= M
ステップ４（２２０６）．認証サーバ（２２１）はＤＢサーバ（２３１）に位置情報登録要求（６０８）を送信し，ステップ６で計算した新しいエントリをＤＢサーバ（２３１）に送信する。ＤＢサーバ（２３１）は位置情報登録要求（６０８）を受信すると，その情報に基づきタグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を返信する。
【００９６】
ステップ５（２２０７，２２０８，）．認証サーバ（２２１）はタグリーダ（２１１）に位置情報登録応答（６１０）を行い，タグ（２０１）が認証されたことをタグリーダ（２１１）に伝え，セッションを終了する。
【００９７】
例外処理（１）におけるステップ３以降の処理は正常処理を表す図８のフローチャートのステップ４以降とほぼ同様の処理を行う。ただし，ステップ３ではＤＢサーバ（２３１）がずれの量dを認証サーバ（２２１）に送信し，ステップ６では認証サーバ（２２１）が同期ずれを補正するため，ずれに相当する回数について可変ＩＤの未来値の計算を行い，新しいエントリを生成する。
【００９８】
なおステップ３では，見つかったタグＩＤについて，同期ずれが発生したことをログなどに記録しても良いし，タグテーブル（２３４）に記録するための項目を設けても良い。あまり頻繁に同期ずれが発生する場合には，タグリーダの設置箇所に何らかの障害が発生している可能性がある。また，単一のタグについて同期ずれが頻繁に発生する場合には，タグの破損や（該当タグを検索不可能にすることを目的とする）攻撃者の存在などが懸念される。同期ずれの発生についてログを取ることにより，このような障害の発生を検出することができる。，ある程度以上の頻度で同期ずれが発生する場合には，システム管理者に警告信号を送信するなどの対策を取る。
【００９９】
本実施形態では図６の通信順序などにより，構成同期ずれが発生した場合には常にタグの可変ＩＤが先行する(時刻t+dの値になる)ように設定している。このため，タグテーブルには可変ＩＤの未来値のみを保持しており，同期ずれが発生した場合の検索が容易である。
【０１００】
本実施形態ではタグの位置情報のみを取り扱うシステムを想定しているが，認証後にタグに対してデータの書き込みを行うようなシステムでは，タグリーダからの応答を待ってタグの可変ＩＤを更新することも考えられる。このようなケースでは，タグがタグリーダからの応答を受信できない可能性があり，逆にタグの可変ＩＤがタグテーブルの現在の可変ＩＤ（５０４）に対して遅れることも想定する必要がある。したがって，そのような場合にはタグテーブルは可変ＩＤの未来値だけではなく，過去の値の履歴をある程度保存しておき，照合時にはその双方について検索を行う必要がある。
＜図10＞
図10は図９のフローチャートのステップ２で例外処理（２）に移行した場合のＤＢサーバ（２３１）および認証サーバ（２２１）の動作を表したフローチャートである。例外処理（２）は極端な同期ずれが発生し，タグの可変ＩＤに対応する値がＤＢサーバの可変ＩＤリストに見つからない場合を処理するものである。以下，図10に従って例外処理（２）を説明する。
【０１０１】
ステップ１（２３０２）．ＤＢサーバ（２３１）はタグテーブル（２３４）の可変IDの未来値のリスト（５０５）からv(i, t)と一致する値を見つけられなかった場合，タグＩＤ検索応答（６０７）としてタグテーブル（２３４）のすべてのID（N個）についてタグＩＤ jとタグ固有鍵k(j)を認証サーバに送信する。
【０１０２】
ステップ２（２３０３）．認証サーバは，タグＩＤ用のカウンタを初期化する。
【０１０３】
ステップ３（２３０４，２３０５）． もしカウンタの値がN以下であれば，ステップ５以下のルーチンを実行する。カウンタの値がNを超えていたら（すべてのタグについて計算を終了したら），位置情報登録要求は不正なものと判断し，位置情報登録要求（６０８）をＤＢサーバに送信する。ＤＢサーバ（２３１）はログにエラーを記録する。
【０１０４】
ステップ４（２３０６，２３０７）．認証サーバ（２２１）は位置情報登録応答（６１０）として，タグリーダ（２１１）に認証が失敗したことを伝え，処理を終了する。
【０１０５】
ステップ５（２３０８）．認証サーバ（２２１）はj番目のタグＩＤ（５０１）について照合のための以下の認証コード値を次のようにして計算する。
【０１０６】
x(j) = Mac(k(j), v(i, t))
ステップ６（２３０９）．認証サーバ（２２１）は位置情報登録要求（６０３）で受け取った認証コードと，ステップ５（２３０８）で生成した検証用の認証コードの照合を行う。２つの認証コードが一致すればステップ７（２３１０）に移行する。一致しない場合にはステップ１０（２３１４）に移行する。
【０１０７】
ステップ７（２３１０）．認証コードが一致した場合には，認証サーバ（２２１）はタグ（２０１）の新しい情報からなるエントリを以下のように作成する。
【０１０８】
位置情報（５０３）：pos
現在の可変ＩＤ（５０４）：v(j, t) = Next(k(j), v(i, t))
可変ＩＤの未来値のリスト（５０５）：v(j, t+x) = Next(k(j), v(j, t+x-1)), 0 < x <= M
ステップ８（２３１１）．認証サーバ（２２１）はＤＢサーバ（２３１）に位置情報登録要求（６０８）を送信し，ステップ７で計算した新しいエントリをＤＢサーバ（２３１）に送信する。ＤＢサーバ（２３１）は位置情報登録要求（６０８）を受信すると，その情報に基づきタグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を返信する。
【０１０９】
ステップ９（２３１２，２３１３）．認証サーバ（２２１）はタグリーダ（２１１）に位置情報登録応答（６１０）を行い，タグ（２０１）が認証されたことをタグリーダ（２１１）に伝え，セッションを終了する。
【０１１０】
ステップ１０（２３１４）．認証コードが一致しない場合には，カウンタの値に1を加え，ステップ３（２３０４）に戻る。
＜図12，13＞：位置情報を用いた探索空間の絞込み
例外処理（２）では，タグテーブル（２３４）に登録されているすべてのタグについて認証コードを計算するが，タグテーブル（２３４）に記録されいてる位置情報（５０３）pos(i, t-1)を使って照合を行うタグ候補を絞り込むことができる。
【０１１１】
図12はタグリーダ（２１１）の配置を表したイメージ図である。図中の黒丸「●」（２４０１〜２４０６）はそれぞれタグリーダ（２１１）を表す。また，それぞれのタグリーダを中心とする大きな円はタグリーダ（２１１）の通信可能圏を表す。図中でタグリーダR(i)（２４０１）の通信可能圏はタグリーダR(j1)（２４０２）〜R(j4)（２４０５）に隣接しており，タグリーダR(j5)（２４０６）とは隣接していない。図中では，隣接しているタグリーダ（２１１）を太い実線で結んでいる。
【０１１２】
また，図13はタグテーブル（２３４）に記録されいてる位置情報（５０３）pos(i, t-1)を使って照合を行うタグ候補を絞り込む場合のリーダテーブル（２３２）の構成図である。リーダテーブル（２３２）の項目は，タグリーダID（３０１）とタグリーダの位置情報（３０２），そして各々のタグリーダ（２１１）に隣接しているタグリーダ（２１１）のID（１３０３）のリストである。
【０１１３】
時刻tにおいてタグリーダR(i)（２４０１）から認証サーバ（２２１）に位置情報登録要求（６０３）が送信されたとする。このとき，タグリーダ（２４０１）にタグID取得応答（６０２）を送信したタグ（２０１）は，時刻t-1においてタグリーダR(i)（２４０１）もしくはそれに隣接するタグリーダR(j1)（２４０２）〜R(j4)（２４０５）の通信可能圏にいたことが期待できる。したがって，タグテーブルに記録されている時刻t-1の位置情報を検索キーとして，タグリーダR(i)（２４０１）およびそれに隣接するタグリーダR(j1)（２４０２）〜R(j4)（２４０５）に対応する位置情報を持つタグを抜き出し，これらのタグについて認証コードの照合を行えばよい。このステップにおいて認証コードが一致するタグ候補が見つからない場合には，改めて残りのタグリストについて図10の処理を行う。
【０１１４】
このように，タグテーブル（２３４）に記憶されている位置情報を用いることで，例外処理（２）の場合にも照合を行うタグ候補を絞り込むことができる。
＜図14＞：リプレイ攻撃対策
本実施形態において，図７の認証コード生成方法では，認証コードにタグリーダ（２１１）のチャレンジコードが含まれていないため，リプレイ攻撃（なりすまし）に対して安全でない可能性がある。リプレイ攻撃の概要を以下に述べる。
【０１１５】
ステップＡ．攻撃者はタグID取得要求（６０１）を送信し，タグID取得応答（６０２）を受信する。
【０１１６】
ステップＢ．攻撃者は正規のタグリーダ（２１１）から送信されるタグID取得要求を受信し，ステップＡで受信したタグID取得応答（６０２）をタグリーダ（２１１）に送信する。
【０１１７】
認証サーバ（２２１）は攻撃者から受信した認証用データと正規のタグ（２０１）から受信したデータを区別できないので，攻撃者は正規のタグになりすますことができる。
【０１１８】
そこで，図6のタグID取得要求に認証用のチャレンジコードr(t)を含める。また，タグ（２０１）は図7の認証コードを計算するステップ（７０２）において，チャレンジコードを認証コードを計算する関数の入力とし，認証コードを次のように計算する。
【０１１９】
h(i, t, r) = Mac(k(i), v(i, t), r(t))
このチャレンジコードr(t)は予測不可能な乱数を含む値で，時刻情報などを含んでも良い。
【０１２０】
図14はタグリーダのチャレンジを含む認証における認証サーバ（２２１）とＤＢサーバ（２３１）の動作を表すフローチャートである。以下，このフローチャートに従って認証サーバの動作を説明する。
【０１２１】
ステップ１（２６０２）．認証サーバ（２２１）はタグリーダ（２１１）から位置情報登録要求を受信すると，まずタグリーダ（２１１）の認証を行う。
【０１２２】
ステップ２（２６０３）．ＤＢサーバ（２３１）にタグＩＤ検索要求（６０６）を送信し，タグ（２０１）の可変ＩＤ v(i, t)を検索キーとしてDBのタグテーブル（２３４）から時刻tの可変IDを検索する。
【０１２３】
ステップ３（２６０４，２６０５）．ＤＢサーバ（２３１）はステップ２（２６０３）の検索で該当するタグＩＤが見つからなければ例外処理（１）に移行する。
【０１２４】
ステップ４（２６０６）．ＤＢサーバ（２３１）はステップ２（２１０３）の検索で該当するタグＩＤを見つけると，認証サーバ（２２１）は該当タグＩＤ（５０１）について照合のための認証コード値を次のようにして計算する。
【０１２５】
x(j) = Mac(k(j), v(i, t), r(t))
ステップ５（２６０７）．認証サーバ（２２１）は位置情報登録要求（６０３）で受け取った認証コードと，ステップ４（２６０６）で生成した検証用の認証コードの照合を行う。２つの認証コードが一致すればステップ６（２６０８）に移行する。一致しない場合にはステップ９（２６１２）に移行する。
【０１２６】
ステップ６（２６０８）．認証コードが一致した場合には，認証サーバ（２２１）はタグ（２０１）の新しい情報からなるエントリを以下のように作成する。
【０１２７】
位置情報（５０３）：pos
時刻t+1の可変ＩＤ（５０４）：v(j, t+1) = Next(k(j), v(i, t))
ステップ７（２６０９）．認証サーバ（２２１）はＤＢサーバ（２３１）に位置情報登録要求（６０８）を送信し，ステップ６で計算した新しいエントリをＤＢサーバ（２３１）に送信する。ＤＢサーバ（２３１）は位置情報登録要求（６０８）を受信すると，その情報に基づきタグテーブル（２３４）を更新し，認証サーバ（２２１）に位置情報登録応答（６０９）を返信する。
【０１２８】
ステップ８（２６１０，２６１１）．認証サーバ（２２１）はタグリーダ（２１１）に位置情報登録応答（６１０）を行い，タグ（２０１）が認証されたことをタグリーダ（２１１）に伝え，セッションを終了する。
【０１２９】
ステップ９（２６１２）．認証コードが一致しない場合には，位置情報登録要求は不正なものと判断し，位置情報登録要求（６０８）をＤＢサーバに送信する。ＤＢサーバ（２３１）はログにエラーを記録する。
【０１３０】
ステップ１０（２６１３，２６１４）．認証サーバ（２２１）は位置情報登録応答（６１０）として，タグリーダ（２１１）に認証が失敗したことを伝え，処理を終了する。
【０１３１】
図９に記載した例外処理（１）においても，同様に認証コードのチェックを行う。
【０１３２】
このように，タグの認証にチャレンジコードを含めることで，リプレイ攻撃を防ぐことができる。
＜図11＞
図１１は表示用携帯端末（２４１）からタグ（２０１）の現在位置を確認するためのプロトコルの概要を表した図である。以下，図１１に従って位置確認プロトコルを説明する。
【０１３３】
ステップ１．表示用携帯端末（２４１）は，アクセスポイント（１１０１）を介し，認証サーバ（２２１）に位置情報参照要求（１１０２）を行う。表示用端末（２４１）から認証サーバ（２２１）に送られる情報は端末のＩＤと認証コード，閲覧したいタグＩＤのリストである。必要であればこれらの情報は暗号化しておく。また，端末の認証はＨＭＡＣ認証方法の他，電子署名を利用した認証でも良い。
【０１３４】
ステップ２．認証サーバ（２２１）は，ＤＢサーバ（２３１）に端末ID検索要求（１１０３）を行う。
【０１３５】
ステップ３．ＤＢサーバ（２３１）は，表示端末テーブル（２３３）から端末IDを検索し，認証サーバ（２２１）に端末ID検索応答（１１０４）を行う。
【０１３６】
ステップ４．認証サーバ（２２１）は，端末ＩＤ検索応答（１１０４）を基に端末IDを認証後，ＤＢサーバ（２３１）に位置情報検索要求（１１０５）を行う。位置情報検索要求（１１０５）はタグＩＤのリストを含む。
【０１３７】
ステップ５．ＤＢサーバ（２３１）は，タグテーブル（２３４）とリーダテーブル（２３２）からタグの位置情報を検索し，認証サーバ（２２１）にタグの位置情報を含む位置情報検索応答（１１０６）を行う。
【０１３８】
ステップ６．認証サーバ（２２１）は，タグIDリストのタグIDの数だけステップ４），５）を繰り返し，すべてのタグについて位置情報を取得したら，アクセスポイント（１１０１）を介し，表示用携帯端末（２４１）に全タグIDの位置情報を含む位置情報検索応答（１１０７）を行う。
【０１３９】
ステップ７．表示用携帯端末（２４１）は，該当するタグの位置情報を表示装置（２４５）に表示する。
【０１４０】
このように，本実施形態によれば，
タグがサーバに送信するデータを（可変ＩＤ，照合用ハッシュ値）の組とし，可変ＩＤを検索キーとしてデータベースからタグの固定IDを検索することで，認証時のサーバの負荷を大幅に削減しつつ，IDの追跡を困難にする認証が可能である。このような特徴により，本実施形態の提供するタグ認証方法は大規模なシステムにおいてＩＤの追跡困難性を実現可能な認証システムを提供できる。
【０１４１】
プライバシを考慮した位置確認システムは，たとえば，来園者の多い大型レジャーパークなどにおける迷子捜索などにも応用することができる。
【図面の簡単な説明】
【０１４２】
【図１】本実施形態の機器構成を例示する図である。
【図２】本実施形態の機器構成における機器の実現例を例示する図である。
【図３】本実施形態のリーダテーブルの構成を例示する図である。
【図４】本実施形態の表示用端末テーブルの構成を例示する図である。
【図５】本実施形態のタグテーブルの構成を例示する図である。
【図６】本実施形態におけるタグ位置情報を登録するプロトコルの概要を例示する図である。
【図７】本実施形態のタグ位置情報を登録するプロトコルにおけるタグの処理を例示するフローチャートである。
【図８】本実施形態のタグ位置情報を登録するプロトコルにおける認証サーバおよびＤＢサーバの正常処理を例示するフローチャートである。
【図９】本実施形態のタグ位置情報を登録するプロトコルにおいて，同期ずれが発生した場合の認証サーバおよびＤＢサーバの処理を例示するフローチャートである。
【図１０】本実施形態のタグ位置情報を登録するプロトコルにおいて，タグテーブルの検索で要求に該当するタグを発見できなかった場合の認証サーバおよびＤＢサーバの処理を例示するフローチャートである。
【図１１】本実施形態において表示用携帯端末がタグの位置を確認するためのプロトコルの概要を例示する図である。
【図１２】本実施形態のタグリーダの配置を例示するイメージ図である。
【図１３】本実施形態のリーダテーブルの構成を例示する図である。
【図１４】本実施形態のタグ位置情報を登録する際にタグリーダの発信する乱数情報を利用するプロトコルにおける認証サーバおよびＤＢサーバの正常処理を例示するフローチャートである。
【符号の説明】
【０１４３】
２０１：タグ，２０２：通信装置，２０３：記憶装置，２０４：暗号処理装置，２０５：データ登録装置，
２１１：タグリーダ，２１２：通信装置，２１３：通信装置，２１４：暗号処理装置，２１５：データ登録・参照装置，
２２１：認証サーバ，２２２：通信装置，２２３：ＤＢアクセス装置，２２４：データ登録・参照装置，２２５：認証装置，２２６：暗号処理装置，
２３１：ＤＢ（データベース）サーバ，２３２：リーダテーブル，２３３：表示端末テーブル，２３４：タグテーブル，
２４１：表示用携帯端末，２４２：通信装置，２４３：記憶装置，２４４：暗号処理装置，２４５：表示装置，２４６：データ登録・参照装置，
【特許請求の範囲】
【請求項１】
通信装置１と記憶装置１と暗号処理装置１とを備える１個以上のタグと，通信装置２と記憶装置２と暗号処理装置２とを備えるタグ認証装置と，からなるシステムにおいて，前記タグ認証装置が前記タグからの通信を識別するための方法であって，
前記タグが備える記憶装置１には秘密鍵１と1回の通信ごとに更新される可変ＩＤ１が記憶されており，
前記タグ認証装置が備える記憶装置２には各々のタグの情報を記録したテーブルが記憶されており，
前記テーブルはタグのＩＤと各タグに対応する秘密鍵２と各タグに対応する可変ＩＤ２の値を項目として含んでおり，
前記タグが備える暗号処理装置１は，認証コード生成装置１，可変ＩＤ更新装置１を備え，
前記タグ認証装置が備える暗号処理装置２は認証コード生成装置２，可変ＩＤ更新装置２を備え，
前記タグ認証装置は，通信装置２を介して定期的にタグに対して認証を要求する信号を発信し，
前記タグは，前記信号を受信すると
， 前記可変ＩＤ１と前記秘密鍵１とを前記認証コード生成装置１の入力として認証コード１を生成し，
信号に対する応答として，前記可変ＩＤ１と，前記認証コード１とを前記通信装置１を介して前記タグ認証装置に送信し，
前記秘密鍵１と前記可変ＩＤ１とを前記可変ＩＤ更新装置１の入力として新しい可変ＩＤを計算し，その結果を前記記憶装置１に記憶し，
前記タグ認証装置は，前記タグからの応答を受信すると
前記応答に含まれる前記可変ＩＤ１を検索キーとして前記テーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，
前記可変ＩＤ１と前記秘密鍵２を前記可変ＩＤ更新装置２の入力として新しい可変ＩＤを計算し，その結果を前記記憶装置２に記憶する
ことを特徴とするタグ識別方法。
【請求項２】
請求項１に記載のタグ識別方法であって，
前記暗号処理装置１および前記暗号処理装置２は，一方向性ハッシュ関数を１つ以上備える
ことを特徴とするタグ識別方法。
【請求項３】
請求項２に記載のタグ識別方法であって，
前記認証コード生成装置は，前記一方向性ハッシュ関数Hashを使って，認証コードC
C = Hash(k||v(t)||0)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||0は前記秘密鍵と前記可変ＩＤと０からなるビット列のビット列としての連結を指す)
を生成する
ことを特徴とするタグ識別方法。
【請求項４】
請求項２に記載のタグ識別方法であって，
前記可変ＩＤ更新装置は，前記一方向性ハッシュ関数Hashを使って，新しい可変ＩＤ v(t+1)
v(t+1) = Hash(k||v(t)||1)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||1は前記秘密鍵と前記可変ＩＤと1からなるビット列のビット列としての連結を指す)
を生成する
ことを特徴とするタグ識別方法。
【請求項５】
請求項１に記載のタグ識別方法であって，
前記テーブルは，さらにすべてのタグについて複数回分の可変ＩＤ v(t+1)〜v(t+M)を記憶する
ことを特徴とするタグ識別方法。
【請求項６】
請求項５記載のタグ識別方法であって，
前記検索キーが前記テーブルに記載されている可変ＩＤ v(t)に該当しない場合に，前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行う
ことを特徴とするタグ識別方法。
【請求項７】
請求項６記載のタグ識別方法であって，
前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，前記テーブルに記憶されているすべてのタグＩＤごとに対応する秘密鍵と前記応答に含まれる可変ＩＤ１とを，前記認証コード生成装置２に入力して得られた値と前記応答に含まれている認証コード１とを照合し，
２つの値が一致するタグＩＤを該当タグと識別する
ことを特徴とするタグ識別方法。
【請求項８】
請求項１に記載のタグ識別方法であって，
前記タグ認証装置が発信する認証を要求する信号は乱数情報を含んでおり，
前記タグは，上記信号を受信すると，
前記可変ＩＤ１と前記秘密鍵１と上記信号に含まれる乱数情報とを前記認証コード生成装置１の入力として認証コード１を生成し，
信号に対する応答として，前記可変ＩＤ１と，前記認証コード１とを前記通信装置１を介して前記タグ認証装置に送信し，
前記タグ認証装置は，前記タグからの応答を受信すると
前記応答に含まれる前記可変ＩＤ１を検索キーとして前記テーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，
前記応答に含まれる前記可変ＩＤ１と前記秘密鍵2と前記発信した乱数情報とを前記認証コード生成装置２に入力して得られた値と，前記応答に含まれる認証コード1を照合することで，前記応答が前記発信した信号に対する応答であることを確認する
ことを特徴とするタグ識別方法。
【請求項９】
無線通信装置１と記憶装置１と暗号処理装置１とを備える１個以上のタグと，
通信装置２と記憶装置２と暗号処理装置２とを備えるタグ認証装置と，
タグと通信するための無線通信装置２と，タグ認証装置と通信するための通信装置１とを備える１個以上のタグリーダと，
からなる無線タグ位置登録システムであって，
前記タグが備える記憶装置１には秘密鍵１と1回の通信ごとに更新される可変ＩＤ１が記憶されており，
前記タグ認証装置が備える記憶装置２には各々のタグの情報を記録したタグテーブルとタグリーダの情報を記録したリーダテーブルが記憶されており，
前記タグテーブルはタグのＩＤと各タグの現在位置，各タグに対応する秘密鍵２，各タグに対応する可変ＩＤ２の値を項目として含んでおり，
前記リーダテーブルはタグリーダのＩＤと各タグリーダを設置した場所の情報を項目として含んでおり，
前記タグが備える暗号処理装置１は，認証コード生成装置１，可変ＩＤ更新装置１を備え，
前記タグ認証装置が備える暗号処理装置２は認証コード生成装置２，可変ＩＤ更新装置２を備え，
前記無線通信装置１と前記無線装置２は一定距離以下でのみ通信可能であり，
前記タグリーダは無線通信装置２を介して定期的に認証を要求する信号をブロードキャストし，
前記タグは，前記ブロードキャストされた信号を受信すると
， 前記可変ＩＤ１と前記秘密鍵１とを前記認証コード生成装置１の入力として認証コード１を生成し，
信号に対する応答として，前記可変ＩＤ１と，前記認証コード１とを含むデータを前記通信装置１を介して前記タグリーダに送信し，
前記秘密鍵１と前記可変ＩＤ１とを前記可変ＩＤ更新装置１の入力として新しい可変ＩＤを計算し，その結果を前記記憶装置１に記憶し，
前記タグリーダは，前記タグからの通信を受信すると
前記タグからの通信で受信したデータにタグリーダのＩＤを付加し，前記通信装置２を介して前記タグ認証装置に位置登録要求信号として送信し，
前記タグ認証装置は，前記タグリーダからの前記位置登録要求信号を受信すると
前記位置情報登録要求信号に含まれる前記可変ＩＤ１を検索キーとして前記タグテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，
前記可変ＩＤ１と前記秘密鍵２を前記可変ＩＤ更新装置２の入力として新しい可変ＩＤを計算し，
前記位置情報登録要求信号に含まれるタグリーダのＩＤを検索キーとして前記リーダテーブルからタグリーダの位置情報を取得し，
タグリーダの位置情報と新しい可変ＩＤを前記記憶装置２に記憶する
ことを特徴とする無線タグ位置登録システム。
【請求項１０】
請求項９に記載の無線タグ位置登録システムであって，
前記暗号処理装置１および前記暗号処理装置２は，一方向性ハッシュ関数を１つ以上備える
ことを特徴とする無線タグ位置登録システム。
【請求項１１】
請求項１０に記載の無線タグ位置登録システムであって，
前記認証コード生成装置は，前記一方向性ハッシュ関数Hashを使って，認証コードC
C = Hash(k||v(t)||0)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||0は前記秘密鍵と前記可変ＩＤと０からなるビット列のビット列としての連結を指す)
ことを特徴とする無線タグ位置登録システム。
【請求項１２】
請求項１０に記載の無線タグ位置登録システムであって，
前記可変ＩＤ更新装置は，前記一方向性ハッシュ関数Hashを使って，新しい可変ＩＤ v(t+1)
v(t+1) = Hash(k||v(t)||1)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||1は前記秘密鍵と前記可変ＩＤと1からなるビット列のビット列としての連結を指す)
ことを特徴とする無線タグ位置登録システム。
【請求項１３】
請求項９に記載の無線タグ位置登録システムであって，
前記タグテーブルは，さらにすべてのタグについて複数回分の可変ＩＤ v(t+1)〜v(t+M)を記憶する
ことを特徴とする無線タグ位置登録システム。
【請求項１４】
請求項１３記載の無線タグ位置登録システムであって，
前記検索キーが前記タグテーブルに記載されている可変ＩＤ v(t)に該当しない場合に，前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行う
ことを特徴とする無線タグ位置登録システム。
【請求項１５】
請求項１４記載のタグ識別方法であって，
前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，前記タグテーブルに記憶されているすべてのタグＩＤごとに対応する秘密鍵と前記応答に含まれる可変ＩＤ１とを，前記認証コード生成装置２に入力して得られた値と前記応答に含まれている認証コード１とを照合し，
２つの値が一致するタグＩＤを該当タグと識別する
ことを特徴とする無線タグ位置登録システム。
【請求項１６】
請求項１４に記載の無線タグ位置登録システムであって，
前記リーダテーブルはさらに各々のタグリーダに近い位置にあるタグリーダのＩＤとを項目として含んでおり，
前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，前記位置情報登録要求に含まれている前記タグリーダのＩＤを検索キーとして，前記リーダテーブルから前記位置情報登録要求を送信したタグリーダに近い位置にあるタグリーダのリストを取得し，
前記位置情報登録要求に含まれている前記タグリーダと上記リストに含まれるタグリーダに対応する位置情報を検索キーとして前記タグテーブルを検索し，
前記タグテーブルの位置情報の項目が上記検索キーのいずれかに合致するすべてのタグＩＤごとに対応する秘密鍵と前記応答に含まれる可変ＩＤ１とを，前記認証コード生成装置２に入力して得られた値と前記応答に含まれている認証コード１とを照合し，
２つの値が一致するタグＩＤを該当タグと識別する
ことを特徴とする無線タグ位置登録システム。
【請求項１７】
請求項９記載の無線タグ位置登録システムであって，
前記タグリーダが発信する認証を要求する信号は乱数情報を含んでおり，
前記タグは，上記信号を受信すると，
前記可変ＩＤ１と前記秘密鍵１と上記信号に含まれる乱数情報とを前記認証コード生成装置１の入力として認証コード１を生成し，
信号に対する応答として，前記可変ＩＤ１と，前記認証コード１とを前記通信装置１を介して前記タグ認証装置に送信し，
前記タグリーダは，前記タグからの応答を受信すると
前記タグからの通信で受信したデータにタグリーダのＩＤと上記乱数情報とを付加し，前記通信装置２を介して前記タグ認証装置に位置登録要求信号を送信し，
前記タグ認証装置は，前記タグリーダからの位置登録要求信号を受信すると
前記位置登録要求信号に含まれる前記可変ＩＤ１を検索キーとして前記テーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，
前記位置登録要求信号に含まれる前記可変ＩＤ１と前記秘密鍵2と前記発信した乱数情報とを前記認証コード生成装置２に入力して得られた値と，前記位置登録要求信号に含まれる認証コード1を照合することで，前記タグの応答が前記タグリーダが発信した信号に対する応答であることを確認する
ことを特徴とする無線タグ位置登録システム。
【請求項１８】
請求項９記載の無線タグ位置登録システムであって，
前記タグリーダは，さらに記憶装置３と暗号処理装置３とを備え，
前記記憶装置３は，秘密鍵３を記憶しており，
前記暗号処理装置３は，乱数生成装置３と認証コード生成装置３とを備え，
タグリーダは，前記タグからの通信を受信すると，
前記暗号処理装置３を用いて乱数を生成し，
前記秘密鍵３と上記乱数を前記認証コード生成装置３への入力とし，
得られた値をタグリーダＩＤに対する認証コードとして，前記タグ認証装置に送信する位置登録要求信号に付加してタグ認証装置に送信する
ことを特徴とする無線タグ位置登録システム。
【請求項１９】
請求項９に記載のシステムであって，さらに，
通信装置４を備える１個以上の表示用端末と，通信装置５を備える１個以上のアクセスポイントと，を備え，
上記表示用端末は，通信装置４を介して上記アクセスポイントに接続し，
タグ認証装置にタグ位置閲覧要求を送信し，
タグの現在位置を取得する
ことを特徴とするタグ位置確認システム。
【請求項２０】
請求項１９に記載のタグ位置確認システムであって，
前記タグ認証装置が備える記憶装置２はさらに表示用端末テーブルとを備え，
上記表示端末テーブルは端末のＩＤと，各タグが閲覧してよいタグのＩＤからなるリストとを含み，
前記タグ位置閲覧要求は表示用端末のＩＤを含み，
前記タグ認証装置は，表示用端末からのタグ位置閲覧要求に対し，
タグ位置閲覧要求に含まれる表示用端末のＩＤを検索キーとして上記表示用端末テーブルを検索し，
要求を行った表示用端末が閲覧可能なタグＩＤのリストを取得し，
上記リストに含まれる各タグＩＤを検索キーとして前記タグテーブルを検索し，
各タグの位置情報を取得し，
取得した情報を表示用端末に返信する
ことを特徴とするタグ位置確認システム。
【請求項２１】
請求項１９に記載のタグ位置確認システムであって，
前記表示用端末は，さらに暗号処理装置を備え，
前記タグ認証装置との通信を暗号化する
ことを特徴とするタグ位置確認システム。
【請求項１】
通信装置１と記憶装置１と暗号処理装置１とを備える１個以上のタグと，通信装置２と記憶装置２と暗号処理装置２とを備えるタグ認証装置と，からなるシステムにおいて，前記タグ認証装置が前記タグからの通信を識別するための方法であって，
前記タグが備える記憶装置１には秘密鍵１と1回の通信ごとに更新される可変ＩＤ１が記憶されており，
前記タグ認証装置が備える記憶装置２には各々のタグの情報を記録したテーブルが記憶されており，
前記テーブルはタグのＩＤと各タグに対応する秘密鍵２と各タグに対応する可変ＩＤ２の値を項目として含んでおり，
前記タグが備える暗号処理装置１は，認証コード生成装置１，可変ＩＤ更新装置１を備え，
前記タグ認証装置が備える暗号処理装置２は認証コード生成装置２，可変ＩＤ更新装置２を備え，
前記タグ認証装置は，通信装置２を介して定期的にタグに対して認証を要求する信号を発信し，
前記タグは，前記信号を受信すると
， 前記可変ＩＤ１と前記秘密鍵１とを前記認証コード生成装置１の入力として認証コード１を生成し，
信号に対する応答として，前記可変ＩＤ１と，前記認証コード１とを前記通信装置１を介して前記タグ認証装置に送信し，
前記秘密鍵１と前記可変ＩＤ１とを前記可変ＩＤ更新装置１の入力として新しい可変ＩＤを計算し，その結果を前記記憶装置１に記憶し，
前記タグ認証装置は，前記タグからの応答を受信すると
前記応答に含まれる前記可変ＩＤ１を検索キーとして前記テーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，
前記可変ＩＤ１と前記秘密鍵２を前記可変ＩＤ更新装置２の入力として新しい可変ＩＤを計算し，その結果を前記記憶装置２に記憶する
ことを特徴とするタグ識別方法。
【請求項２】
請求項１に記載のタグ識別方法であって，
前記暗号処理装置１および前記暗号処理装置２は，一方向性ハッシュ関数を１つ以上備える
ことを特徴とするタグ識別方法。
【請求項３】
請求項２に記載のタグ識別方法であって，
前記認証コード生成装置は，前記一方向性ハッシュ関数Hashを使って，認証コードC
C = Hash(k||v(t)||0)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||0は前記秘密鍵と前記可変ＩＤと０からなるビット列のビット列としての連結を指す)
を生成する
ことを特徴とするタグ識別方法。
【請求項４】
請求項２に記載のタグ識別方法であって，
前記可変ＩＤ更新装置は，前記一方向性ハッシュ関数Hashを使って，新しい可変ＩＤ v(t+1)
v(t+1) = Hash(k||v(t)||1)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||1は前記秘密鍵と前記可変ＩＤと1からなるビット列のビット列としての連結を指す)
を生成する
ことを特徴とするタグ識別方法。
【請求項５】
請求項１に記載のタグ識別方法であって，
前記テーブルは，さらにすべてのタグについて複数回分の可変ＩＤ v(t+1)〜v(t+M)を記憶する
ことを特徴とするタグ識別方法。
【請求項６】
請求項５記載のタグ識別方法であって，
前記検索キーが前記テーブルに記載されている可変ＩＤ v(t)に該当しない場合に，前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行う
ことを特徴とするタグ識別方法。
【請求項７】
請求項６記載のタグ識別方法であって，
前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，前記テーブルに記憶されているすべてのタグＩＤごとに対応する秘密鍵と前記応答に含まれる可変ＩＤ１とを，前記認証コード生成装置２に入力して得られた値と前記応答に含まれている認証コード１とを照合し，
２つの値が一致するタグＩＤを該当タグと識別する
ことを特徴とするタグ識別方法。
【請求項８】
請求項１に記載のタグ識別方法であって，
前記タグ認証装置が発信する認証を要求する信号は乱数情報を含んでおり，
前記タグは，上記信号を受信すると，
前記可変ＩＤ１と前記秘密鍵１と上記信号に含まれる乱数情報とを前記認証コード生成装置１の入力として認証コード１を生成し，
信号に対する応答として，前記可変ＩＤ１と，前記認証コード１とを前記通信装置１を介して前記タグ認証装置に送信し，
前記タグ認証装置は，前記タグからの応答を受信すると
前記応答に含まれる前記可変ＩＤ１を検索キーとして前記テーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，
前記応答に含まれる前記可変ＩＤ１と前記秘密鍵2と前記発信した乱数情報とを前記認証コード生成装置２に入力して得られた値と，前記応答に含まれる認証コード1を照合することで，前記応答が前記発信した信号に対する応答であることを確認する
ことを特徴とするタグ識別方法。
【請求項９】
無線通信装置１と記憶装置１と暗号処理装置１とを備える１個以上のタグと，
通信装置２と記憶装置２と暗号処理装置２とを備えるタグ認証装置と，
タグと通信するための無線通信装置２と，タグ認証装置と通信するための通信装置１とを備える１個以上のタグリーダと，
からなる無線タグ位置登録システムであって，
前記タグが備える記憶装置１には秘密鍵１と1回の通信ごとに更新される可変ＩＤ１が記憶されており，
前記タグ認証装置が備える記憶装置２には各々のタグの情報を記録したタグテーブルとタグリーダの情報を記録したリーダテーブルが記憶されており，
前記タグテーブルはタグのＩＤと各タグの現在位置，各タグに対応する秘密鍵２，各タグに対応する可変ＩＤ２の値を項目として含んでおり，
前記リーダテーブルはタグリーダのＩＤと各タグリーダを設置した場所の情報を項目として含んでおり，
前記タグが備える暗号処理装置１は，認証コード生成装置１，可変ＩＤ更新装置１を備え，
前記タグ認証装置が備える暗号処理装置２は認証コード生成装置２，可変ＩＤ更新装置２を備え，
前記無線通信装置１と前記無線装置２は一定距離以下でのみ通信可能であり，
前記タグリーダは無線通信装置２を介して定期的に認証を要求する信号をブロードキャストし，
前記タグは，前記ブロードキャストされた信号を受信すると
， 前記可変ＩＤ１と前記秘密鍵１とを前記認証コード生成装置１の入力として認証コード１を生成し，
信号に対する応答として，前記可変ＩＤ１と，前記認証コード１とを含むデータを前記通信装置１を介して前記タグリーダに送信し，
前記秘密鍵１と前記可変ＩＤ１とを前記可変ＩＤ更新装置１の入力として新しい可変ＩＤを計算し，その結果を前記記憶装置１に記憶し，
前記タグリーダは，前記タグからの通信を受信すると
前記タグからの通信で受信したデータにタグリーダのＩＤを付加し，前記通信装置２を介して前記タグ認証装置に位置登録要求信号として送信し，
前記タグ認証装置は，前記タグリーダからの前記位置登録要求信号を受信すると
前記位置情報登録要求信号に含まれる前記可変ＩＤ１を検索キーとして前記タグテーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，
前記可変ＩＤ１と前記秘密鍵２を前記可変ＩＤ更新装置２の入力として新しい可変ＩＤを計算し，
前記位置情報登録要求信号に含まれるタグリーダのＩＤを検索キーとして前記リーダテーブルからタグリーダの位置情報を取得し，
タグリーダの位置情報と新しい可変ＩＤを前記記憶装置２に記憶する
ことを特徴とする無線タグ位置登録システム。
【請求項１０】
請求項９に記載の無線タグ位置登録システムであって，
前記暗号処理装置１および前記暗号処理装置２は，一方向性ハッシュ関数を１つ以上備える
ことを特徴とする無線タグ位置登録システム。
【請求項１１】
請求項１０に記載の無線タグ位置登録システムであって，
前記認証コード生成装置は，前記一方向性ハッシュ関数Hashを使って，認証コードC
C = Hash(k||v(t)||0)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||0は前記秘密鍵と前記可変ＩＤと０からなるビット列のビット列としての連結を指す)
ことを特徴とする無線タグ位置登録システム。
【請求項１２】
請求項１０に記載の無線タグ位置登録システムであって，
前記可変ＩＤ更新装置は，前記一方向性ハッシュ関数Hashを使って，新しい可変ＩＤ v(t+1)
v(t+1) = Hash(k||v(t)||1)
(ただし，kは該当タグの秘密鍵，v(t)は前記タグが現在記憶している可変ＩＤとし，k||v(t)||1は前記秘密鍵と前記可変ＩＤと1からなるビット列のビット列としての連結を指す)
ことを特徴とする無線タグ位置登録システム。
【請求項１３】
請求項９に記載の無線タグ位置登録システムであって，
前記タグテーブルは，さらにすべてのタグについて複数回分の可変ＩＤ v(t+1)〜v(t+M)を記憶する
ことを特徴とする無線タグ位置登録システム。
【請求項１４】
請求項１３記載の無線タグ位置登録システムであって，
前記検索キーが前記タグテーブルに記載されている可変ＩＤ v(t)に該当しない場合に，前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行う
ことを特徴とする無線タグ位置登録システム。
【請求項１５】
請求項１４記載のタグ識別方法であって，
前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，前記タグテーブルに記憶されているすべてのタグＩＤごとに対応する秘密鍵と前記応答に含まれる可変ＩＤ１とを，前記認証コード生成装置２に入力して得られた値と前記応答に含まれている認証コード１とを照合し，
２つの値が一致するタグＩＤを該当タグと識別する
ことを特徴とする無線タグ位置登録システム。
【請求項１６】
請求項１４に記載の無線タグ位置登録システムであって，
前記リーダテーブルはさらに各々のタグリーダに近い位置にあるタグリーダのＩＤとを項目として含んでおり，
前記あらかじめ計算しておいた複数回分の可変ＩＤのリストから検索を行っても該当するタグが無い場合に，前記位置情報登録要求に含まれている前記タグリーダのＩＤを検索キーとして，前記リーダテーブルから前記位置情報登録要求を送信したタグリーダに近い位置にあるタグリーダのリストを取得し，
前記位置情報登録要求に含まれている前記タグリーダと上記リストに含まれるタグリーダに対応する位置情報を検索キーとして前記タグテーブルを検索し，
前記タグテーブルの位置情報の項目が上記検索キーのいずれかに合致するすべてのタグＩＤごとに対応する秘密鍵と前記応答に含まれる可変ＩＤ１とを，前記認証コード生成装置２に入力して得られた値と前記応答に含まれている認証コード１とを照合し，
２つの値が一致するタグＩＤを該当タグと識別する
ことを特徴とする無線タグ位置登録システム。
【請求項１７】
請求項９記載の無線タグ位置登録システムであって，
前記タグリーダが発信する認証を要求する信号は乱数情報を含んでおり，
前記タグは，上記信号を受信すると，
前記可変ＩＤ１と前記秘密鍵１と上記信号に含まれる乱数情報とを前記認証コード生成装置１の入力として認証コード１を生成し，
信号に対する応答として，前記可変ＩＤ１と，前記認証コード１とを前記通信装置１を介して前記タグ認証装置に送信し，
前記タグリーダは，前記タグからの応答を受信すると
前記タグからの通信で受信したデータにタグリーダのＩＤと上記乱数情報とを付加し，前記通信装置２を介して前記タグ認証装置に位置登録要求信号を送信し，
前記タグ認証装置は，前記タグリーダからの位置登録要求信号を受信すると
前記位置登録要求信号に含まれる前記可変ＩＤ１を検索キーとして前記テーブルを検索し，該当するタグのＩＤと対応する秘密鍵２を取り出し，
前記位置登録要求信号に含まれる前記可変ＩＤ１と前記秘密鍵2と前記発信した乱数情報とを前記認証コード生成装置２に入力して得られた値と，前記位置登録要求信号に含まれる認証コード1を照合することで，前記タグの応答が前記タグリーダが発信した信号に対する応答であることを確認する
ことを特徴とする無線タグ位置登録システム。
【請求項１８】
請求項９記載の無線タグ位置登録システムであって，
前記タグリーダは，さらに記憶装置３と暗号処理装置３とを備え，
前記記憶装置３は，秘密鍵３を記憶しており，
前記暗号処理装置３は，乱数生成装置３と認証コード生成装置３とを備え，
タグリーダは，前記タグからの通信を受信すると，
前記暗号処理装置３を用いて乱数を生成し，
前記秘密鍵３と上記乱数を前記認証コード生成装置３への入力とし，
得られた値をタグリーダＩＤに対する認証コードとして，前記タグ認証装置に送信する位置登録要求信号に付加してタグ認証装置に送信する
ことを特徴とする無線タグ位置登録システム。
【請求項１９】
請求項９に記載のシステムであって，さらに，
通信装置４を備える１個以上の表示用端末と，通信装置５を備える１個以上のアクセスポイントと，を備え，
上記表示用端末は，通信装置４を介して上記アクセスポイントに接続し，
タグ認証装置にタグ位置閲覧要求を送信し，
タグの現在位置を取得する
ことを特徴とするタグ位置確認システム。
【請求項２０】
請求項１９に記載のタグ位置確認システムであって，
前記タグ認証装置が備える記憶装置２はさらに表示用端末テーブルとを備え，
上記表示端末テーブルは端末のＩＤと，各タグが閲覧してよいタグのＩＤからなるリストとを含み，
前記タグ位置閲覧要求は表示用端末のＩＤを含み，
前記タグ認証装置は，表示用端末からのタグ位置閲覧要求に対し，
タグ位置閲覧要求に含まれる表示用端末のＩＤを検索キーとして上記表示用端末テーブルを検索し，
要求を行った表示用端末が閲覧可能なタグＩＤのリストを取得し，
上記リストに含まれる各タグＩＤを検索キーとして前記タグテーブルを検索し，
各タグの位置情報を取得し，
取得した情報を表示用端末に返信する
ことを特徴とするタグ位置確認システム。
【請求項２１】
請求項１９に記載のタグ位置確認システムであって，
前記表示用端末は，さらに暗号処理装置を備え，
前記タグ認証装置との通信を暗号化する
ことを特徴とするタグ位置確認システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００８−１５６３９（Ｐ２００８−１５６３９Ａ）
【公開日】平成２０年１月２４日（２００８．１．２４）
【国際特許分類】
【出願番号】特願２００６−１８３９７７（Ｐ２００６−１８３９７７）
【出願日】平成１８年７月４日（２００６．７．４）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成１８年度、独立行政法人情報通信研究機構 「ＩＣカード等における認証のための高度な暗号技術に関する研究開発」委託研究、産業再生法第３０条の適用を受ける特許出願）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２０年１月２４日（２００８．１．２４）
【国際特許分類】
【出願日】平成１８年７月４日（２００６．７．４）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成１８年度、独立行政法人情報通信研究機構 「ＩＣカード等における認証のための高度な暗号技術に関する研究開発」委託研究、産業再生法第３０条の適用を受ける特許出願）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]