JP4768752B2 - 無線周波数識別タグセキュリティシステム - Google Patents

Description

本発明は、概してＲＦＩＤ（無線周波数識別）技術に関し、特にこのような技術の使用において安全で個人的なシステムを動作するための装置及び方法を説明する。

無線周波数識別（ＲＦＩＤ）は、物理的世界において情報が収集される方法を革新的に変更し得る実現可能性の高い技術である。ＲＦＩＤタグは、典型的には、視認または人手の介入を必要とせずに複数の対象物を識別するために使用される。ＲＦＩＤを用いると、供給チェーン（chain)内の製品のパレットを、降ろしたり、梱包を解いたりすることなく在庫管理することができる。ＲＦＩＤが消費製品に埋め込まれることにより、消費者はレジで待たなくてよく、偽造が抑制された新しい買い物を体験することができる。当初の販売時点の後、ＲＦＩＤタグは、消費者によって自宅の中でサービスを使用可能にするために使用され得るし、あるいは製品の返却、リサイクル及び中古販売のためにも使用され得る。自動識別装置は、図書館及び媒体レンタル会社において、在庫システムの回転効率を高めるために既に成功している。将来、さらに多くの商品がタグを付けられ、多くの新しいアプリケーションが使用可能になるのを目にするであろう。ＲＦＩＤの展開は消費者の購買習慣に影響を及ぼす可能性が高い。消費者はインターネット上でタグＩＤを参照することによりより良い製品情報を取得できる。ＲＦＩＤによれば、受領書のない返却や、販売後の盗難の低減を可能とすることが約束される。しかしながら、これらの予期される優位点はあるが、ＲＦＩＤ技術はプライバシーに関する懸念を提起している。ＲＦＩＤシステム、その構成要素及び、動作の紹介のため、読者は、出版物が以下に参照され、この参照により組み込まれているＳａｍａ、Ｗｅｉｓ及びＥｎｇｅｌｓによる論文を参照されたい。

ＲＦＩＤタグは、視認を必要とせずに読み取ることができ、消費製品に不可視に埋め込むことができるため、プライバシーの管理が困難である。ユビキタスアプリケーションの場合、タグは安価でなければならず（したがって、セキュリティに関するタグの能力を譲歩し）、同時にタグは高速で読み取られなければならない（したがって、複雑な通知及び認証を命令することが困難になる）。プライバシーのリスクにより、２つの根本的な要件――つまり、情報の漏洩防止、及び追跡防止―が必要となる。さらに、タグは、タグの性質上、単一の所有権領域にとどまらず、タグは譲渡可能でなければならないが、タグの所有が通過する現在の（及び過去の）所有者のそれぞれのプライバシーを保護しなければならない。ＲＦＩＤの適用においては、所有権が移動しなくても、複数の団体が同じタグを読み取らなければならないので、ＲＦＩＤシステムは、二次的な団体にタグに対するアクセスを委任する能力を含むことが理想的である。

もし、同じＲＦＩＤタグが製品寿命を通して使用されれば、あるいは変更されない秘密鍵でＩＤが暗号化されれば、製品は供給チェーンに沿って追跡され得る。タグにアクセスできるいかなる団体も、現在の所有者のプライバシーを無視して、タグの寿命の間、タグを追跡することができる。このようなタグは、例えば産業スパイ活動またはさらに悪いもの等の状況に照らして、非認証のアクセスに対して脆弱である。

したがって、ＲＦＩＤタグの使用におけるセキュリティのレベルを高めることが望ましい。特に、タグはタグが付けられた商品の保持者のプライバシーを危険にさらしてはならない。これは、非認証の団体はタグ情報にアクセスできてはならないことを意味する。この１つの態様は―特に供給チェーンに照らして関連する―過去に認証された（が、現在は非認証である）読出者による追跡を許すような長期の関連付けがあってはならないということである。

本発明は、セキュリティ及びプライバシーが改善されたＲＦＩＤに基づいたシステムを動作するための装置及び方法を説明している。例示を目的として、以下の説明は消費者商品の供給チェーンに照らして行われるが、本発明は広範囲の適用が可能であり、したがって特定の状況に制限されないことが理解されよう。

以下は、前述されたプライバシー及びセキュリティの問題に対処するためのいくつかの公知の方法である。

１つの方法はタグに書かれた情報量を最小限に抑えることである。供給チェーンの業務を可能にするが、望まれない団体に対する情報の開示を制限できるように、製品情報が符号化されている。ＥＰＣｇｌｏｂａｌ規格及びＩＳＯ−１８０００規格によるタグは、アクセス制御能力を提供するために、パスワードで保護されている「キル（ｋｉｌｌ）」コマンド及び４８ビット読み取りパスワードを組み込んだプライバシー保護コマンドをサポートしている。ここでの着想は、タグを見つけ、使用不可にすることができることであり、これによりタグ及びタグが付けられた商品がその後匿名になる。例えば、小売の状況では、タグは売り渡し時点で「キル」することができる。この解決策の１つの問題は、柔軟性が欠如していることである。すなわち、「キル」される前には誰でもタグに無差別にアクセスできるが、「キル」された後は誰もアクセスできない。これは、例えば消費者が販売後に欠陥のある商品の返却を希望するときには不便となるであろう。キルコマンド方式は、タグの読取範囲内にあるいかなる団体も自由に、タグＩＤにアクセスできることを前提としている。タグがキルコマンドを発行される前に、供給チェーン内の団体間の、あるいは他の団体からのプライバシーに対する規定はない。

別の公知の方法は、タグを再コード化することである。現在、タグを付けられた製品が販売されるとき、小売業者は、該タグが付けられた商品の制御が自分から離れてしまっても該タグが付けられた商品を依然として追跡調査できる。タグの再コード化には、書き込み可能タグの使用、及び製品の所有者が変わる際の再コード化処理を実行することが含まれる。この場合、読取装置が、新しい情報のセットでタグを書き換え、元の電子製品コード（ＥＰＣ）と新しいコードの間にマッピングを保持するであろう。製品の過去の所有者または将来の所有者は、マッピングにアクセスできなければタグ情報にアクセスすることはできない。該マッピングへのアクセスは、該マッピングを保持するデータベースによって強制されるプライバシー方針により制御できる―すなわち、セキュリティを強制するタスクはリソースが制限されているタグからデータベースに移る。この方式の欠点はインフラストラクチャを使用するコスト及び管理である。タグが付けられた商品の所有者または制御が変わるたびに、供給チェーン上の各団体は、再コード化処理を実行するために必要な装置を有さなければならない―これは追加のコストを表す。さらに、再コード化は、何らかの形式のアクセス制御が提供されない限り、悪意のある団体による再コード化に対して脆弱である。

さらに別の公知の手法は、タグが読取装置によって照会されるたびにタグの識別子を修正することである。製品識別子と製品情報の間の関連は安全なデータベース内に維持されている。したがって、タグはハッシュ関数の使用によりその識別子を新たにすることによって読取装置に予想通りに応答しない。安全なデータベースはタグ出力のシーケンスを生成するために使用される秘密値にアクセスできるため、該データベースはタグ出力を製品情報にマッピングできる。

以下を含むセキュリティを改善するための多様な提案が行われている。

−Ａ Ｊｕｅｌｓ及びＲ Ｐａｐｐｕ：「密告するユーロ：ＲＦＩＤが使用可能にされた紙幣におけるプライバシー保護（Ｓｑｕｅａｌｉｎｇ Ｅｕｒｏｓ：Ｐｒｉｖａｃｙ−Ｐｒｏｔｅｃｔｉｏｎ ｉｎ ＲＦＩＤ−Ｅｎａｂｌｅｄ Ｂａｎｋｎｏｔｅｓ）」、（金融暗号法２００３年（Ｆｉｎａｎｃｉａｌ Ｃｒｙｐｔｏｇｒａｐｈｙ‘０３）、１０３〜１２１ページ、Ｒ．Ｗｒｉｇｈｔ編集。Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ．２００３年、ＬＮＣＳ第２７４２号）
−Ｓａｎｊａｙ Ｅ Ｓａｒｍａ、Ｓｔｅｐｈｅｎ Ａ Ｗｅｉｓ及びＤａｎｉｅｌ Ｗ Ｅｎｇｅｌｓ：「ＲＦＩＤシステムと、セキュリティ及びプライバシーとの係わり合い（ＲＦＩＤ Ｓｙｓｔｅｍｓ ａｎｄ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ Ｉｍｐｌｉｃａｔｉｏｎｓ）」、（暗号ハードウェア及び埋め込みシステムに関するワークショップ（Ｗｏｒｋｓｈｏｐ ｏｎ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ）、４５４〜４７０ページ、コンピュータサイエンスのレクチャーノート（Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）、２００２年）
−Ａ Ｊｕｅｌｓ「ＲＦＩＤタグのための最小主義暗号法（Ｍｉｎｉｍａｌｉｓｔ Ｃｒｙｐｔｏｇｒａｐｈｙ ｆｏｒ ＲＦＩＤ Ｔａｇｓ）」、（通信ネットワークのセキュリティ（Ｓｅｃｕｒｉｔｙ ｏｆ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｎｅｔｗｏｒｋ）（ＳＣＮ）、Ｃ．Ｂｌｕｎｄｏ編集、２００４年）
本発明の第１の態様によると、無線周波数識別システムを動作する方法が提供される。

前記システムは、タグと、読取装置と、サードパーティ認証機関を含み、
前記タグはタグアイデンティティ及び秘密値を備えるタグ名を有し、前記秘密値は前記タグアイデンティティにマッピングされ、
前記方法は、
（ｉ）前記読取装置が前記タグを問い合わせるステップと、
（ｉｉ）応えて前記タグが、前記タグアイデンティティ及び前記秘密値の暗号を備える仮名を送信するステップと、
（ｉｉｉ）前記読取装置は復号キーのリリースを求める要求であって、前記タグから受け取られる前記仮名を含む要求を前記サードパーティ認証機関に送信するステップと、
（ｉｖ）前記読取装置は前記復号キーを受け取ることを認証されると判断した前記サードパーティ認証機関が前記読取装置に前記復号キーを送信するステップと、
（ｖ）前記読取装置が前記タグアイデンティティを取得するために前記復号キーを使用するステップと、を備え、
前記復号キーが、前記読取装置と前記サードパーティ認証機関の間で追加のコンタクトなしに、前記タグアイデンティティを取得するために所定の複数の回数前記読取装置によって使用できる。

本発明の第２の態様によると、無線周波数識別システムを動作する方法が提供される。

前記システムがタグと、読取装置と、サードパーティ認証機関とを含み、
前記タグはタグアイデンティティ及び秘密値を備えるタグ名を有し、前記秘密値は前記タグアイデンティティにマッピングされ、
前記方法は、
（ｉ）前記読取装置が前記タグを問い合わせするステップと、
（ｉｉ）応えて前記タグは、一方向ハッシュツリーの中の復号キーの場所を説明する場所的情報を送信するステップと、
（ｉｉｉ）前記読取装置が復号キーのリリースを求める要求であって、前記タグから受け取られた前記場所的情報を含む要求を前記サードパーティ認証機関に送信するステップと、
（ｉｖ）前記読取装置が前記復号キーを受け取ることを認証されると判断した前記サードパーティ認証機関が、前記読取装置に前記復号キーを送信するステップと、
（ｖ）前記読取装置が前記タグアイデンティティを取得するために前記復号キーを使用するステップと、を備え、
前記復号キーが、前記読取装置と前記サードパーティ認証機関の間でさらなるコンタクトなしに、前記タグアイデンティティを取得するために所定の複数の回数前記読取装置によって使用できる。

本発明は、供給チェーン（chain)上を、あるいは複数の所有者の間で移動する商品(items)上のＲＦＩＤタグであって、認証された団体によってのみ、及び限られた回数の読取動作のためだけに識別されるべきＲＦＩＤタグの使用により生じるプライバシー及びセキュリティの問題に取り組む。これは、タグと読取装置間の結合をより短期的なものとすることによる仮名方式の使用、及び、読取装置に与えられるキーを信頼できるサードパーティによって準備することにより達成される。

すべての読み取りのたびに読取装置がサードパーティに問い合わせることを必要とすることが従来の技術により考えられる手法であったが、代わりに、読取装置は、指定された数の読取動作の後に期限切れとなる一時的なキーを与えられる。これにより、商品が供給チェーンに沿って移動するにつれて、所望されるとおりに認証された読取装置を追加または削除できる柔軟なシステムが可能になる。

本発明はこのようなＲＦＩＤシステムで使用可能な非常に限られたリソースも考慮に入れる。コスト検討のため、最も基本的なタグのみが、例えば消費者商品供給チェーンにおけるユビキタス展開のために検討される可能性が高い。このため、簡単な機能のみがタグで実施されなければならない。本発明は、タグ装置内での一方向ハッシュ関数、または擬似ランダム関数、あるいは一方向ハッシュ関数と擬似ランダム関数の組み合わせを使用することを必要とするであろう。

ここで、本発明の実施形態は、添付図面に関して単なる一例として説明される。

図１は、本発明によるＲＦＩＤシステムの３つの主要な構成要素間の関係及び通信を示す、本発明の一実施形態の全体概略図である。多くのやり取りＥ１からＥ５が、イベントの過程において、タグ、読取装置、及びサードパーティ認証機関の間で行われる。

図２は、典型的な読取及びアクセスのセッションのステップを説明するフローチャートである。

本発明の実施形態は、図１及び図２に関連してここで説明される。

図２のステップＳ１では、読取装置（４）が、適切な無線周波数の放射によりタグを走査することによりタグ（２）との初期接触する。これは、図１のＥ１とラベルが付けられた矢印で描かれている。

ステップ２では、タグは該読取装置に対して、「仮名」を組み込んだ出力Ｅ２を送信することによって応答する。

ステップ３では、読取装置が仮名（出力Ｅ２）を受け取る。読取装置が該読取装置の中に、読取装置が仮名を「復号する」ことを可能にする情報を有する場合（「イエス」）、読取装置はサードパーティ認証機関から復号キー（本説明の中では「シード」と呼ばれることもある）を求める必要はない。読取装置がこの情報を有さない場合（「ノー」）、プロセスは認証段階に進む。

ステップ４は、認証プロセスの開始を表す。これはオプションのステップであり、読取装置からの異なるコマンドに応えて生成され得る。この段階の読取装置は、復号動作を可能にするためにタグからさらに多くの情報を取得してもよい。この情報は「ヒントメッセージ」の形であってもよいし、あるいはさらに長い仮名の形であってもよい。

ステップ５では、読取装置は、読取装置（６）によって必要とされる情報を有するサードパーティ認証機関に認証要求（Ｅ５）を送信する。認証要求は、仮名、読取装置の信用証明書、及びオプションとしてヒントメッセージの組み合わせを含むことができる。読取装置の信用証明書は、特定の読取装置にタグの実際のＩＤに対する認証及びアクセスを認めるべきかどうかを判断する目的でサードパーティ認証機関が受け入れるであろう事前に合意された事項であってもよい。例えば、信用証明書は、読取装置自体のＩＤを含むか、読取装置自体のＩＤであろう。信用証明書は、加えて、または代わりに、供給チェーンにおける以前の団体によって読取装置に、電子請求書等によって渡される情報であろう。サードパーティ認証機関は、情報をリリースする前に読取装置を認証するために、証明書等の信用証明書をチェックする。読取装置がいったん認証されると、読取装置に許可されたアクセス権を検索することができ、これらの権利に従って情報をリリースされることができる。

ステップ６では、サードパーティ認証機関は、該認証要求（Ｅ５）の有効性を判断する。読取装置が認証されるべきであることを確信すると、サードパーティ認証機関は読取装置に復号キー及びタグＩＤ（Ｅ６）をリリースしてもよい。読取装置によって接触される認証機関が、読取装置によって渡される情報を理解するほど十分なキーを有さない、あるいは読取装置のためのアクセスキー（複数の場合がある）を生成しない場合がある。この場合、認証機関はさらに大きなアクセス権を有する別の認証機関に該要求を渡してもよい。

ステップ７では、読取装置はここで復号キーを有する。これにより読取装置は仮名を復号し、後述される方法によって実際のタグＩＤを取得することができる。ステップＳ３と関連して前述されたように、読取装置がその段階でキーを既に有している場合には、該読取装置は認証プロセス（ステップＳ１からＳ６）を迂回し、Ｓ７の復号プロセスに直接進むことができる。

図１のやり取りＥ７とＥ８は、図４に関連して後述される。これらのやり取りは、使用においてさらに大きなセキュリティを提供する、タグと読取装置の相互認証のオプションのステップに関係する。

本発明のこの実施形態では、読取装置はタグに対する一時的なアクセスのみを有するだろう。これは、限られた回数の読取だけを読取装置に認めることによって達成される。この制限に達し、読取装置がさらなるアクセスを必要とすると、新しい認証段階が申請されなければならない。

サードパーティ認証機関の役割は、前述されたようにタグ製造者、もしくは発行者、あるいはタグの第１のユーザによって実現できる。該役割は、本願出願人の同時係属特許出願ＧＢ第０４２８５４３．３号に説明されている装置によっても実行できるであろう。少なくとも１つの認証機関がタグによって生成され得る仮名の全体的な集合の知識を有さなければならないが、追加の認証機関は、追加の認証機関がタグの寿命のうち一定期間だけアクセスを認めることが可能となる該知識の部分集合を委任されてもよい。認証機関を階層状につなげることにより、一次的な認証機関に課される負荷を削減できる。

サードパーティ認証機関は、限られた回数、ある特定のタグ用の仮名を復号する能力を読取装置に与える時限秘密を計算できる。特に、サードパーティ認証機関は次のｎ回の仮名の識別を可能にする秘密を計算することが許され、ここで、ｎは適用方針によって指定される。秘密は安全なチャネルを通じて読取装置に通信される。

問題は、過剰に複雑にすることなく、どのように大多数のタグに対して仮名システムを拡大させるのかである。ｎ個のタグのデータベースでは、仮名を復号する１つの方法はｎ個すべてのタグを通して線形走査を実施することである。本発明の方式では、所有権及び時限秘密を移行させる追加の特長によっては復号の複雑さは増加せず、現在のＲＦＩＤ仮名解決策における複雑さと同程度のままである。

図３は、前述のステップ４に関連して簡略に説明される、タグからヒントメッセージを生成する方法の表示である。読取装置がタグ（Ｅ３）からヒントメッセージを要求すると、次の仮名（Ｅ１）に対する要求からの異なるコマンドが使用されてよい。代わりに、単一の読取装置コマンドを使用でき、タグが周期的に―例えば、ｎ個の仮名が生成されるたびに１つのヒントメッセージを―リリースできる。

タグの出力（図１のやり取りＥ２）は読取動作ごとに変化する。特に、タグの各出力を、非認証の読取装置によって他のいかなる以前のタグまたは将来のタグと相互に関連付けることはできない。これは追跡を防止するために重要な特性であり、ヒントメッセージは同様に繰り返されてはならない。これは、（コマンドＥ３を通して）ヒントメッセージを特に必要とする読取装置は、ヒントがリリースされる前に、タグ仮名を（例えば複数の読取動作を行うことにより）ｎ個のステップまで前進させなければならない。他の読取装置が該タグに対する同時アクセスを所望する場合は、ヒントを出力するこの方法が最も効率的ではない可能性がある。図１０に関連する後述の説明は、ヒントメッセージに関して別の解決策も提供する。

以下は、図１及び図２に説明されている該方法がどのようにして製薬業界の供給チェーンの状況で適用できるのかを示す図である。

（薬物等の）医薬商品は、医薬商品の製造時にタグを固定される。タグは本発明による安全な方式を実現する。このような医薬商品は、通常複数一緒に梱包され、供給チェーンの次の団体―例えば販売業者―に送られる。各商品上のタグは、タグが供給チェーンを離れて、消費者領域に入る前に異なる団体によって複数回読み取られる。

医薬商品が製造領域と卸売り領域の間を移動するとき、通常、請求書は移動先（例えば卸売業者）に送られる。請求書は製品の説明（例えば、製品のＥＰＣ）及びサードパーティ認証機関の場所（例えばユニフォームリソースロケータ）を含むことができる。これのみで、あるいは他の情報と結合されて、前述のステップＳ５で参照される読取装置の信用証明書のすべてまたは一部としての役割を果たす。商品が卸売業者に達すると、読取装置はタグの出力を読み取り、サードパーティ認証機関からのアクセス認証を要求するであろう。アクセスが認められた後、卸売業者はタグＩＤにアクセスできるであろう。このようなアクセスがあれば、卸売業者は次に請求書に一覧表示されたすべての製品が到着したことを検証できる。さらに、卸売業者は、データベースのタグと関連付けられる情報であって商品の製造日等の事柄についての情報を示し得る情報も調べることができるであろう。このようなデータベースは該卸売業者に局所的であってもよいし、あるいは、例えば、製造メーカによって維持され、最新の製品情報等を提供できるであろう、集中データベースであってもよい。

薬局が医薬商品を注文すると、卸売業者は出荷及び請求書発行を手配する。該卸売業者は該薬局に該製品のＥＰＣ及び該サードパーティ認証機関の（ＵＲＬ等の）連絡先詳細を渡す。この情報は再び電子請求書に含まれてもよい。これらの詳細は、商品が該卸売業者から該薬局に出荷されるときに該商品に添付されてもよいが、もし、これらの詳細が別個に、好ましくは安全な方法で送信されれば、セキュリティが強化される。該医薬商品は該卸売業者から該薬局への該請求書または他のメッセージ上にも表示されるであろう包装ＩＤまたは出荷ＩＤを有し、これにより商品のＥＰＣ及び関連するＵＲＬは薬局によって受け取られる出荷品と明確に関連付けることができる。

商品が薬局に到達すると、タグは再び読み取られ、サードパーティ認証機関から認証が再び要求される。

もちろん、前述のプロセスのいかなる段階における出荷者もタグに対するアクセスを必要とする可能性があり、これはサードパーティ認証機関に要求を送信することによって同じように取得できるであろう。

小売薬局に到達後、該商品は次に販売のために該薬局の棚の上に置かれる。商品が販売されると、所有権はエンドユーザに渡される。本発明によるセキュリティ解決策は、タグに対する該薬局のアクセスを無効にし、制御をユーザに渡す方法を含む。これは、システムの重要な特長である。例えば、３ＴＣを処方された人はヒト免疫不全ウィルスを有する可能性が高く、このような情報が秘密に保持されることを望む可能性がある。

ここで、タグは消費者領域内にある。消費者は２つのオプションを有する。第１のオプションは、ユーザは、さらなるサービスのためにタグを利用する必要がないというものである。この場合、本発明による解決策はユーザのプライバシーを保証する―、医療情報の追跡及び読み取りは不可能である。復号キーを使用しないでタグを読み取ろうとするいかなる試みも失敗するであろう。しかしながら、消費者はタグのＩＤにアクセスする必要がある場合がある。例えば、消費者は、特定の薬物が摂取されなければならないときを消費者に通知するような「知的棚（ｉｎｔｅｌｌｉｇｅｎｔ ｓｈｅｌｆ）」上に商品を載せる場合がある。この場合、消費者の読み取り装置はサードパーティ認証機関からタグＩＤアクセスを要求する必要があるであろう。

ユーザが未使用の薬物の入った薬物容器を処分するとき、処分会社はリサイクル目的でタグを使用できるであろう。この場合、本方式は消費者のプライバシーを保護するが、処分会社自体のデータベースに関する情報を追跡し、リンクする目的のタグの機能も維持する。

図４は、ハッシュに基づいた仮名方式で発生するタグと読取装置の間のやり取りを描いている。例えば「ＨＭＡＣ：メッセージ認証のための鍵付きハッシュ法（ＨＭＡＣ：Ｋｅｙｅｄ−Ｈａｓｈｉｎｇ ｆｏｒ Ｍｅｓｓａｇｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ）」（ＲＦＣ２１０４、１９９７年９月）にＫｒａｗｃｚｙｋ、Ｈ．Ｂｅｌｌａｒｅ、Ｍ ａｎｄ Ｒ Ｃａｎｅｔｔｉによって説明されている鍵付きハッシュメッセージの使用に基づいた非認証の追跡及びタグの識別を防ぐことができる。

セットアップ時、タグには一意の識別子の組（ＹＩＤ，ＩＤ）が与えられている。ＹＩＤはタグと認証された読取装置の間で共有される（ビットのシーケンスを含む）秘密である。Ｇは一方向関数（例えば、ＳＨＡ１、あるいは擬似ランダム関数）であり、関数の作用は、関数の出力が入力についての情報をまったく明らかにしないというものである。照会時、タグは秘密「ＹＩＤ」に対する一方向関数の適用から生じる新しい要素を生成し、複数回の読み取りで一連の要素ＹＩＤ １、ＹＩＤ ２．．．ＹＩＤ ｎ−１、ＹＩＤ ｎを取得する。処理ごとに仮名Ｓｋ＝ｒ１、Ｇ（ｒ１，Ｇ（ｒ１，ＹＩＤ ｋ））が生成され、タグによって読取装置に送信される。

読取装置は、タグメッセージがオプションで、ＩＤ ＸＯＲ Ｇ（ｒ１，ＹＩＤ ｋ）でタグに返答してもよいことを立証する組（ＹＩＤ，ＩＤ）を特定する。該タグと同じ組（ＹＩＤ，ＩＤ）を共有する読取装置によってだけＧ（ｒ１，ＹＩＤ ｋ）が生成できるので、この情報はタグに対して読取装置のＩＤを認証し、相互認証を可能にする。

該組（ＹＩＤ，ＩＤ）を知らない読取装置にとっては、該タグの単一の出力は乱数値から区別することができず、以前の出力または将来の出力と相互に関連付けることができない。該タグと読取装置間の通信上の盗聴者は、該タグについて、いかなるさらなる情報をも獲得することはできない。

前述された相互認証方法によれば、悪意のあるユーザがハッシュチェーン(hash chain)に沿ってタグ値を循環させる可能性や、またはタグもしくは本出願人の同時係属中の特許出願番号ＧＢ第０４２８５４３．３号に説明されている装置のような装置が合法的な読取装置を特定する可能性を制限することができる。

前述されたような一方向関数によってタグ識別子を生成する公知の認証方法は、効率的な解決策であるとはいえない。第１に、該方法では、読取装置が、ハッシュ値を取得する際に、考えられるタグのすべての組み合わせを調べなければならないので、スケーラビリティの問題がある。第２に、該方法では、所有権の安全な移動をサポートしていない。以前にタグに対するアクセスが認められた読取装置は該タグを読み取り続けることができる。しかしながら、本発明の装置及び方法は両方の問題に対処する。

図５は、２つの一方向関数を有する２分岐一方向ツリーを示している。該関数はここではそれぞれ「左」関数と「右」関数と呼ばれている。通常、該関数はＳＨ１またはＭＤ５アルゴリズム等の一方向ハッシュ関数を使用して構築できるであろう。

ツリーにおけるキーのシーケンスは以下のように構築できる。初期のルートシード「Ｓ（ルート）」はツリーと関連付けられており、深さＤのパラメータはツリーのリーフの数Ｎ＝２ｄ−１を表している。

中間値は以下のように生成される。

１．Ｄレベルのキー値は、Ｚ（０）＝左｛Ｚ（ｒｏｏｔ）｝、Ｚ（１）＝右｛Ｚ（ｒｏｏｔ）｝である。

２．キーのＤ−１レベルは、Ｚ（００）＝左｛Ｚ（０）｝、Ｚ（０１）＝右｛Ｚ（０）｝、Ｚ（１０）＝左｛Ｚ（１）｝、Ｚ（１１）＝右｛Ｚ（１）｝となるであろう。

３．ツリーのＤ−２レベルは以下のとおりになるであろう。Ｚ（０００）＝左｛Ｚ（００）｝、Ｚ（００１）＝右｛Ｚ（００）｝、Ｚ（０１０）＝左｛Ｚ（０１）｝、Ｚ（０１１）＝右｛Ｚ（０１）｝、Ｚ（１００）＝左｛Ｚ（１０）｝、Ｚ（１０１）＝右｛Ｚ（１０）｝、Ｚ（１１０）＝左｛Ｚ（１１）｝、Ｚ（１１１）＝右｛Ｚ（１１）｝等であり、Ｄレベルの深さに対して中間シード値の２分岐ツリーを作成する。

この例では、以下が確認される。

・レベル「ｉ」でのシードはレベルの２＾（ｉ−１）個のリーフを生成する。

・シードの子供たちは、「左」一方向関数と「右」一方向関数のおかげで互いに似ていない。

・親は２倍の数のリーフを生成することができ、その結果、タグ識別子により大きなアクセスを与えるという点で、ツリーの中の子供は、親の半分の重要度である。ツリーの一部に対するアクセスが認められる場合、開示されるツリーの中のすべてのキーの計算を可能にするリーフに最も近いシードの、より小さな方の集合へのアクセスが与えられる。シードに対するアクセスが与えられると、受信機は、シードがツリーの中のどこに存在するのかを知る必要がある。

例えば、Ｄ＝８というツリーでは、アクセスがレベル３のシード（例えばＳ００１）に与えられると、受信機は４つのリーフキーを生成できるであろう。他のすべてのキーは隠されたままとなる。レベルの選択が開示されるキーの数を制限する。読取装置によってさらに多くのキーがアクセスされる必要がある場合、読取装置アクセスを拡張するために１つまたは複数の新しいキーが開示されてもよい。

前述のツールは、図４で前述されたハッシュに基づいた認証方式に適用することにより、読取装置に一時的なアクセスを認めるために使用され得るが、読取装置にとって使用可能な読み取り動作の数を制限する。かつていったん認証されたが、もはや認証されていない読取装置によるタグアクセスを制限する目的を達成することに加えて、これは読取装置にとって計算の複雑さを削減するのに役立つ。

本発明のこの態様によると、認証プロトコルで使用されるシードＹＩＤ ｋは２分岐一方向ツリーのリーフである。前述されたように、ＹＩＤ ｋは読み取り動作ごとに変更される。ＹＩＤ ｋはツリーのリーフに沿って進行する。

本発明によるとこのように実現される方式の優位点は以下のとおりである。

・明確なシーケンスが読取装置に提示されることにより、読取装置と該シーケンスの知識を共有するタグとが通信できる。

・ツリーの中の中間値を明らかにすると、読み取り装置にサブシーケンスを明らかにすることができる。（読取装置は、読取装置が理解するツリーリーフ値を使い果たすので）読取装置は限られた数の読取動作に対するタグを認証し、アクセスできるにすぎない。

「ｎ」回の動作のためのタグへのアクセスを得るために、読取装置は、ｌｏｇ（ｎ）＋１のレベルでのわずか１シードが与えられればよい。例えば、レベル４での単一のシード値を知ることによって８回の読み取り動作を認めることができる。代わりに、８回の読み取り動作は、それぞれがレベル３での２つのシードによって認められてもよい。「ｎ」回の動作のために付与されなければならないキーの数は、ツリーの中の開始位置に応じて変化する。

ツリーの値を知っている読取装置は、今及び十分なシードが分かっている読み取り動作の間だけ、タグに緩やかに結合されている。すべてのタグは、読み取り照会ごとに新しい仮名を生成する。読取装置は、該読取装置に認められている読み取り動作の回数だけ、該タグを追跡し、アクセスすることができるにすぎないため、商品の所有者が変わるときにタグ再コード化処理は必要とされない。読取装置が該読取装置に認められている、認められた数の動作の最後に達すると、該読取装置の該タグに対するアクセスは自動的に終了する。読み取り動作が以前の団体によって未使用なまま、ある団体から供給チェーン上の次の団体にタグが移動する場合、これらの動作を廃棄することが可能である。これは、該タグの複数回の読み取りによって達成でき、あるいは読み取りプロトコルが拡張される場合は、ツリーのリーフに沿っていくらかの距離にある値まで直接的にスキップすることが可能となる。これは、該タグに新しい秘密を書き込む必要なく、該タグに対する以前のアクセス権を取り消すために役立つ。

読取装置とタグの間の結合はサードパーティ認証機関に任されている。考えられるシナリオでは、元の製造者が組（ＹＩＤ，ＩＤ）を制御し、タグが読取装置の信用証明書を記憶し、アクセスを認める、もしくは拒否するためのサードパーティ認証機関としての機能を果たす。読取装置が特定のタグにアクセスする必要があるときには、それはシードの集合（またはツリーの要素）を要求する。集合は、要求された回数の読み取り動作のアクセスを与える、ツリーの中間ノードからなる。許可された動作の回数は、新しい認証要求によって拡大され得る。

認証を要求するとき、新たな読取装置はサードパーティ認証機関にタグの現在の状態を知らせなければならない。これは、サードパーティ認証機関がタグの現在の状態、及びタグがどのリーフ(leaf)の値を使用しているのかを知らないためである。サードパーティ認証機関は、タグＩＤとツリーシーケンスの現在の状態の両方を、タグによって生成される該仮名値から計算できるであろう。

サードパーティ認証機関はある特定の読取装置に対し、該読取装置が該タグのＩＤを事前に知ることなく、どのシードを分配するべきかを知る必要がある。該タグが現在認証されていない読取装置に、該タグＩＤについての情報をリリースできない場合、タグＩＤ／現在のキー値の組の単一化（ｓｉｎｇｕｌａｔｉｏｎ）を助けるために、ツリーシーケンスの状態についての情報を代わりにリリースすることができる。

１つの手法は、読取装置が、アクセス要求する際に、サードパーティ認証機関に対して、現在のタグメッセージ及びルートから現在使用されているリーフの値までの経路に沿って仮名ツリーの中の中間ノードから生成されるヒントメッセージとともに、通常の信用証明書を提供することである。

前述された方式を用いる場合、サードパーティ認証機関がタグから仮名だけを受け取るならば、その特定のタグの正しいＩＤを特定するためのプロセスはＯ（（ｎ）（Ｎ））のオーダーの複雑さを有し、ここで、ｎはツリーによって生成されているリーフの数を表し、Ｎはサードパーティ認証機関によって管理されているタグの数を表す。

ヒントメッセージを使用することにより、タグを特定するための計算の複雑さをＯ（Ｎ）のオーダーの複雑さにまで削減できる。本発明の方式においては、すべての考えられる仮名空間を検索するよりも迅速にタグを特定するためにヒントが使用され得る。ツリー場所ヒント及びルートからリーフへのヒントという２つの異なるヒント機構解決策が提案される。

一例として、セットアップ時、タグには再び一意の組（ＹＩＤ，ＩＤ）が提供され、ここで、ＹＩＤはそのタグのためのツリーのルートシードである。ツリー深さがｌｏｇ（ｎ）＋１である場合に「ｎ」回の読み取り動作のためのツリーがあると仮定される。

ｎ＝４０９６のタグは、深さｄ＝１２＋１のツリーを必要とする。タグが中間ノード値を維持するならば、２個の一方向ハッシュ関数の平均（最小１，最大ｌｏｇ（ｎ））が、読み取り動作ごとに計算される必要がある。ツリーを維持するために、タグは、例えばカウンタを用いて、ツリーの中の現在の位置を記憶することが要求される。照会時、タグは新しいリーフ「Ｙｌｅａｆ」（以前はＹＩＤ ｋと呼ばれていた）を生成し、メッセージＳｋ＝Ｇ（ｒ１，Ｇ（ｒ１，（Ｙｌｅａｆ））を生成する。

認証された読取装置はツリーの部分集合に対するアクセスを認められていると仮定する。タグは組（Ｙｉ，ＩＤ）により読取装置によって特定され、ここでＹｉはレベル「ｉ」でのツリーの要素である。レベル「ｉ」（ｉ＝１がツリーのリーフである）での秘密は２（ｉ−１）回の読み取り動作に対するアクセスを認める。効率化のために、読取装置によって特定のタグにアクセスするために実行される必要のある作業量（２（２（ｉ−１））−２回までのハッシュ関数評価）を制限するよう、「ｉ」は小さい値を選ばれる。タグメッセージを受け取る際、読取装置は、タグメッセージを検証する組（Ｙｉ，ＩＤ）を見つける。

平均して、タグに対して４回の一方向ハッシュ関数の呼び出し（つまり、２分岐ツリーに対して２回とＧに対して２回）が、読み出しサイクルごとに必要とされる。ツリー情報はサイクルごとに更新される必要がある。この例は２分岐一方向ツリーを使用し、タグはルート秘密からツリーの現在のリーフまでｌｏｇ（ｎ）＋１の秘密を記憶することができる。

読取装置がタグのアイデンティティを知らないときに、タグアイデンティティがどのようにして特定できるのかという問題でスケーラビリティの問題が生じる。例えば、読取装置は新しいタグを受け取り、該読取装置は仮名を復号するためにどの秘密が使用されなければならないのかを知らない。サードパーティ認証機関はアクセスを認めることができるが、そのためにはサードパーティ認証機関はタグによって使用されている現在のツリーのリーフについての何らかの情報を有している必要がある。

図７は本発明による解決策を描いている。

タグは、ツリー場所ヒントを生成できる。ヒントメッセージは、２分岐一方向ツリーの中のシードを指す情報を含んでいる。したがって、該ヒントは、該ツリーのどの部分が現在使用されているのかを示すインジケータとして機能することができる。ヒントメッセージを利用することにより、サードパーティ認証機関はタグを特定し、認証されている読取装置に、その時点から有効な、該タグにアクセスするためのシードの有効な集合を開示することができる。ヒントメッセージは、仮名を生成するために使用されるルートシードと、現在の仮名自体の間の異なるレベルでリリースできる。

ここで説明されている方式においては、図３で前述されたように仮名値は、ツリーの中間ノードから生成されるヒントとインタリーブされる。実際には、レベルがタグの出力によって明確に示されている限り多くのレベルを使用することができるが、この例では、中間ノードの１つのレベルだけがヒントメッセージを生成するために使用されている。（異なるレベルの）ヒントと仮名をインタリーブすることの欠点の１つは、何らかのシーケンス情報が非認証の読取装置にとって明らかとなり、制限された範囲でのタグの追跡に使用される可能性があるという点である。別の欠点は、タグの仮名はヒント値を取得するために慎重に前進されなければならないという点である。これらの問題点は、図１０に関連して後述されるヒントメッセージを提供する代替方法によって対処される。

以下のステップでは、現在のタグを特定するためにヒントメッセージがどのように使用され得るのかを示す。

２ｉ回の読み取り動作ごとに、タグはヒントメッセージを開示する。ヒントはＨ（Ｙｉ）であってもよく、ここで、Ｙｉは、２（ｉ−１）回の動作へのアクセスを認めるレベルｉにおけるシードであり、Ｈはハッシュ関数である。Ｈ（Ｙｉ）は一方向関数であるため、ツリーについてのいかなる情報をも敵対者に開示しない。Ｈ（Ｙｉ）はサードパーティ認証機関によって共有されて（知られて）いる。

このヒントは、アクセスを要求するために読取装置により使用される。読取装置が新しいタグを受け取ると、読取装置はＨ（Ｙｉ）を取り出す必要がある。図３に示されている方式による読取装置は、ヒント値が開示されるまで繰り返しタグを読み取る。この時点で、読取装置はサードパーティ認証機関にアクセスし、認証機関にヒントメッセージを提供することによりアクセスを要求できるであろう。

読取装置が認証されると、サードパーティ認証機関は次に該シード値Ｙｉを読取装置に通信する。読取装置は一時的にアクセスが認められる。

ヒントメッセージの使用は、使用によって複雑さが極端に削減されるため、有益である。ヒントメッセージを使用しない場合、以下のどちらかのときに問題が発生する。

・タグが、新しい所有者に予期せずに到達し、タグとともに情報が転送されない。

・タグが特定の読取装置によって前回走査されて以来、他の団体が該タグに対して未知数の読み取りを実行した。

これらの例では、読取装置は、考えられるタグごとに仮名チェーンに沿って制限されたチェックを行った後にあきらめ、該タグは知らされていないものであると結論付けなければならない。読取装置は、知らされていないタグに対する応答と、知らされているタグからの仮名であるが、読取装置がチェックした点を越えているものとを区別できない。

ヒントメッセージを用いると、複雑さはＯ（（ｋ）（Ｎ））にまで削減され、ここでｋは開示されているシードのレベルに依存している。レベルが高い場合（ヒントがルートに近い場合）、サードパーティ認証機関は、正しいツリーを見つけ、タグを特定するために限られた数のハッシュ動作を実行しなければならないであろう。例えば、ｄ＝１０（ツリーディメンジョン）、ｉ＝８であれば、キー認証機関はタグを特定するため２（ｄ−ｉ）＝４個の秘密にわたって処理する。検索の複雑さはＯ（４^＊Ｎ）である。

この第１の実施形態では、プロセスは以下のように働く。

１．該読取装置は、タグから現在の仮名を読み取り、該仮名を、予想される仮名値の空間に突き合わせようと試みる。

２．この突き合わせが失敗すると、読取装置はタグからヒント値を取得する。これは、ヒント値が得られるまで反復的に読み取ることによって、あるいはヒント値が与えられるまでタグを自動的に前進させる特別な指令によって取得できる。

３．ヒント値が、読取装置に知らされているキーによってカバーされることができる、ハッシュツリー中のあるレベルにある場合、読取装置はヒント値を知らされているタグと付き合わせようと試みることができる。例えば、ツリーのリーフから４レベル分上のヒント値に突き合わせようと試みることは、ツリーのリーフに沿って３２個の仮名の空間を検索することに同等である。したがって、より高レベルの知らされているヒント値に沿って検索することによって、タグが知らされている場合には読取装置は迅速に特定できる。タグは、使用されているヒントのレベルについての情報を読取装置に提供しなければならない。

４．取得されたヒント値が、読取装置が知らされているよりツリーの中で高い場合、あるいはヒント値が読取装置に知らされているシーケンスを越えて下にあるためにヒント値を突き合わせることができない場合には、読取装置はサードパーティ認証機関に尋ねなければならない。この認証機関はルートシードを知っている可能性があり、したがってツリーのすべて、あるいはツリーの一部にすぎないが、読取装置自体が知らされているより多くのシードを有する部分を知っている可能性がある。

５．前述の認証機関がヒントメッセージを復号できない場合、要求は、該ヒント値を復号するために、ツリー全体の知識を有するルート認証機関のような別の認証機関に問い合わされてよい。

ルート認証機関は、認証機関がツリーのルート秘密を知っているためにタグを常に復号することができる。ルート認証機関の場合、ヒント値を復号する経費はツリーにおけるヒントのレベルに依存している。ヒントがルート値自体である場合には、認証機関はルートシードの一覧表示の中の値を即座に調べることができる。ルートからいくらかのレベルだけ下の場合、タグごとに考えられる値のすべてを事前に計算しておき、即座に調べることもできる。この突き合わせが失敗する場合、タグは認証機関に知らされていないものである。ツリーの中のさらに低いヒント値の場合、認証機関はツリーの中の最新の知らされている位置を記憶し、値の限られた空間に沿ってチェックする。この検索が失敗すると、タグは知られていないものであるか、あるいは仮名ツリーに沿って、識別が失敗するほど十分に前進されたものである可能性がある。ヒントメッセージの限られた集合を検索することは、ツリーのリーフに沿ってはるかに大きな仮名空間を検索することに同等であることが再び留意されるべきである。

ツリーの中の複数のレベルが、本発明によるシステムにおけるヒント値として使用され得ることが留意されるべきである。実際には、１つの解決策は、「ルートからリーフまでのヒント」を提供することによってツリーの中のすべてのレベルを使用することである。ヒントをすべてのレベルでリリースする１つの適用は以下のように説明される。

インタリーブされた仮名値及びヒントメッセージは、読取装置の要求に応えて生成され得る。タグは両方の場合で同じ方式で応えることができるが、リーフにおけるハッシュ値の代わりに、ツリーの中の中間ノードの、すなわち該リーフよりルートにさらに近いノードのハッシュ値を使用する。ヒントメッセージのリリースは、このようにして仮名シーケンスに一体化され得る。例えば、ハッシュ値は、図５に描かれているツリーの中の値であって左から右へ明らかにされるものであってもよい。

この図では、タグ応答を生成するために使用されるハッシュ値は以下のように進行してよい。つまり、Ｚ０００、Ｚ００、Ｚ００１、Ｚ０、Ｚ０１０、Ｚ０１、Ｚ０１１等である。読取装置がどのハッシュ値と一致させようと試みるのかを突き止められるように、各リリースは、使用されるレベルで特定されなければならない。

本発明のシステムにおいてヒントメッセージを含むことの費用の利点がここで説明される。上記において留意されたように、仮名を受け取っている読取装置は、ヒントメッセージなしでタグを特定するのに困難を感じることがある。仮名は予想される仮名及びタグの集合に突き合わされる。タグの集合は（どの製品が、その日に、ある特定の読取装置の前に到達するのか等についてのプロセス／在庫知識等の）知識によって制限され得る。しかしながら、前回知られている仮名値から検索を開始することによって、仮名検索は制限できる。ヒントメッセージを使用することにより、ツリーの中の中間レベルでの、はるかに小さな値の集合にわたって検索を実行することが可能となる。さらに、ツリーの複数のレベルから取得されるヒントは、（高レベルヒントから）タグの迅速な識別と、現在のリーフの仮名まで下る（しかし、中間レベルのヒントに一致する）ナビゲーションの容易化の両方を同時に可能にすることができる。

ここで、仮名を、結合されたタグメッセージ中のヒントと結合することによって、該タグ読み取り動作の効率を改善する第２の実施形態を提示する。

（図８、図９及び図１０に示されている）この手法は、ヒント情報を、仮名とともにタグ応答の一体化した一部としてリリースする。タグ応答がより大きくなっても、上記において図３との関連で説明されている実施形態のために必要とされるように、ヒント値を取得するために読取装置によって仮名を前進させる必要がないため、優位点は相当である。また、仮名と同時にリリースされたヒント値によって、読取装置（または認証機関）は、突き合わせのために空間を検索する代わりに仮名まで直接にナビゲーションできる。

該代替手法は、バックエンドシステムの複雑さを減ずるが、読取装置とタグの間でやり取りされるメッセージという点では通信の複雑さを大きくする。

ここでは、Ｈは一方向ハッシュ関数として定義され、Ｒは擬似乱数として定義されている。タグは１組の識別子（ＹＩＤ，ＩＤ）により特定され、ここでＹＩＤは秘密であり、ＩＤがタグ識別子である。読み取り動作中、読取装置は乱数Ｒ１を送信し、応えてタグはメッセージＲ１、Ｒ２、Ｈ（Ｒ１，Ｒ２，ＹＩＤ）を送信する。該組（ＹＩＤ，ＩＤ）にアクセスできる読取装置だけが該タグを特定できる。

乱数の生成は、（ｉ）乱数発生器によって、または（ｉｉ）一方向ハッシュ関数によっての２通りで行うことができる。一方向ハッシュ関数の使用では、乱数であるＲをＲ＝Ｈ（ＣＮＴ，Ｓ）によって生成し、ここで、ＣＮＴは読み取り動作ごとに増分されるカウンタであり、Ｓは１２８ビットの（共有されていない）秘密であり、Ｈは一方向ハッシュ関数または擬似乱数−関数である。

この方式は、Ｄａｖｉｄ Ｍｏｌｎａｒ、Ｄａｖｉｄ Ｗａｇｎｅｒによる出版物、「ライブラリＲＦＩＤ問題におけるプライバシーとセキュリティ、実践及びアーキテクチャ（Ｐｒｉｖａｃｙ ａｎｄ ｓｅｃｕｒｉｔｙ ｉｎ ｌｉｂｒａｒｙ ＲＦＩＤ ｉｓｓｕｅｓ、Ｐｒａｃｔｉｃｅｓ ａｎｄ Ａｒｃｈｉｔｅｃｔｕｒｅｓ）」（２００４年ＡＣＭコンピュータ及び通信セキュリティ会議に提案されている示唆のいくつかを実現する。しかしながら、Ｍｏｌｎａｒ及びＷａｇｎｅｒの方式は、タグの付けられている商品の制御者または所有者が変わることを許さないのに対して、２分岐一方向ハッシュツリーを適用する本発明者らの手法はタグアイデンティティに対する制限されたアクセスの提供を可能にする。

上記に提示された一方向２分岐ツリーツールを適用する際に、バックエンドシステムの計算の複雑さは削減される。秘密ＹＩＤは２分岐一方向ツリーにおけるシードと関連付けられている。前述された第１の方式とは異なり、タグは、ツリーのリーフと関連付けられている単一の出力を生じさせるのではなく、ツリーのルートからリーフまでの異なる秘密と関連付けられている複数の出力を生じさせる。

図８に図示されているように、該タグは、セットアップ時に識別子の一意の組（Ｚ−Ｒｏｏｔ，ＩＤ）を提供され、ここで、ＹＩＤ＝ＺＲｏｏｔはツリーのルートシードである。その結果、「ｎ」回の読み取り動作のためのツリーがあり、ここで、ツリー深さＤ＝ｌｏｇ（ｎ）である。２個の一方向ハッシュ関数の平均が読み取り動作ごとに計算される必要があるであろう。

読取装置によって問い合わせられるとき、タグは新しい枝を含むツリーの新しいリーフを生成する。読取装置は乱数Ｒ１を送信し、タグはメッセージＲ１、Ｒ２、Ｈ（Ｒ１，Ｒ２，Ｚ−Ｒｏｏｔ）、Ｈ（Ｒ１，Ｒ２，Ｚｉ）、Ｈ（Ｒ１，Ｒ２，Ｚｉ＋１）、Ｈ（Ｒ１，Ｒ２，Ｚｌｏｇ（ｎ））のシーケンスを送信する。シーケンスのメッセージは、ツリーのルートからリーフまでの異なるシードと関連付けられている。

この場合、タグはリーフから生成される単一の仮名で特定されるのではなく、メッセージのシーケンスで特定される。読取装置またはサードパーティ認証機関は、共有されているシードから複雑さＯ（Ｎ．ｌｏｇ（ｎ））を有するリーフまでタグの認証を進める必要はなく、複雑さＯ（Ｎ）を有するシードに直接にアクセスする。

上述の場合におけるように、認証された読取装置は、ツリーの部分集合に対するアクセスを認められたと仮定できる。図９では、タグは、組を通して読取装置によって特定される。

上記に提示された一方向２分岐ツリーツールを適用すると、バックエンドシステムの計算の複雑さが削減される。秘密Ｙ_ＩＤは２分岐一方向ツリーにおけるシードと関連付けられている。前述された第１の方式とは異なり、タグはツリーのリーフと関連付けられている単一の出力を生成するのではなく、ツリーのルートからリーフまでの異なる秘密と関連付けられる複数の出力を生成する。

図８に示されているように、タグはセットアップ時に識別子の一意の組（Ｚ−Ｒｏｏｔ，ＩＤ）を提供され、ここでＹ_ＩＤ＝ＺＲｏｏｔはツリーのルートシードである。その結果、ｎ回の読み取り動作のためのツリーが存在し、ここで、ツリーの深さはＤ＝ｌｏｇ（ｎ）である。２つの一方向ハッシュ関数の平均は、読み取り動作ごとに計算される必要があるであろう。

ここで図８の該ハッシュツリーを参照すると、読み取り動作ごとに２つの新しい乱数、「Ｒ１」、「Ｒ２」が生成され、ツリーにおける値のシーケンスが更新される。

タグ出力は以下のとおりである。

第１の読み取り動作：

第２の読み取り動作：

したがって、例えば、読取装置が秘密Ｚ０１へのアクセスを取得する場合、２回の読み取り動作が読取装置に認められる。代わりに、読取装置が秘密Ｚ１へのアクセスを取得する場合、４回の読み取り動作が読取装置に認められる。

「ｎ」回の動作のためのタグへのアクセスを取得するために、読取装置はレベルｌｏｇ（ｎ）＋１でわずか１シードが与えられてもよい。例えば８回の読み取り動作はレベル４で単一のシード値を知ることによって認められてもよい。代わりに、８回の読み取り動作は、それぞれレベル３での２個のシードによって認められてもよい。「ｎ」回の動作のために認められなければならないキーの数は、ツリーの中の開始位置に応じて変化する。

読取装置によって問い合わせられると、タグは、新しい枝を含むツリーの新しいリーフを生成する。読取装置は乱数Ｒ１を送信し、タグはメッセージＲ１、Ｒ２、Ｈ（Ｒ１，Ｒ２，Ｚ−ｒｏｏｔ）、Ｈ（Ｒ１，Ｒ２，Ｚｉ）、Ｈ（Ｒ１，Ｒ２，Ｚｉ＋１）、Ｈ（Ｒ１，Ｒ２，Ｚｌｏｇ（ｎ））のシーケンスを送信する。

シーケンスのメッセージはツリーのルートからリーフまでの異なるシードと関連付けられている。

この場合、タグはリーフから生成される単一の仮名で特定されるのではなく、メッセージのシーケンスで特定される。読取装置またはサードパーティ認証機関は、共有されるシードから、複雑さＯ（Ｎ．ｌｏｇ（ｎ））を有するリーフまでタグの認証を進める必要はなく、複雑さＯ（Ｎ）を有するシードに直接アクセスする。

上述の場合におけるように、認証されている読取装置は該ツリーの部分集合に対するアクセスを認められたと仮定できる。図９では、タグは１組（Ｙｉ，ＩＤ）によって読取装置によって特定され、ここでＹｉはレベル「ｉ」でのツリーの要素である。レベル「ｉ」での秘密は、２^{（ｉ−１）}回の読み取り動作に対するアクセスを与える。タグメッセージを受け取ると、バックエンドシステムはタグメッセージを検証する組（Ｙｉ，ＩＤ）を見つける。

したがって、例えば、読取装置が秘密Ｚ０１にアクセスする場合、２回の読み取り動作が読取装置に認められる。

図９の（上部に位置する）第１のハッシュツリーを参照すると、読取装置は次の２つの出力にアクセスできる。

タグは単一のハッシュ関数で検証できる。読取装置は、秘密Ｚ０１が特定のタグ識別子を参照することを知っている。ハッシュ値Ｈ（Ｒ１，Ｒ２，Ｚ０１）を計算することによって、読取装置はタグの正しいアイデンティティを検証できる。

図９の（下部に位置する）第２のハッシュツリーを参照すると、読取装置システムはシードＺ１にアクセスできる。このシードが４回の読み取り動作に対するアクセスを与える。

読取装置は次の４つの出力にアクセスできる。

タグは単一のハッシュ関数で検証できる。読取装置は、秘密Ｚ１が特定のタグ識別子を参照することを知っている。ハッシュ値Ｈ（Ｒ１，Ｒ２，Ｚ１）を計算することによって、読取装置はタグの正しいアイデンティティを検証できる。

本方式は従来と同程度にプライベートなものであるが、方式は限られたコストでタグの認証を可能にする。タグの数Ｏ（Ｎ）に線形なコスト、及び通信コストは、Ｏ（ｌｏｇ（ｎ））の複雑さを有している。この方式では異なるメッセージの出力を、少ないビットに切り捨てることができ、通信コストを改善できることに留意することが重要である。

図１０は、本実施形態におけるヒントメッセージの役割を描いている。ここでは、読取装置はタグ出力をキーマネージャ（認証役）に伝達する。この場合、タグ出力が「ヒントメッセージ」である。メッセージＭはプライバシー方針と関連付けることができる。認証役は、特定のプライバシー方針に対して読取装置のアイデンティティを検証する。読取装置は、次に読取装置にシードを渡すことができ、タグアクセスは特定回数の読み取り動作について開示される。

例えば図１に関連して説明されている前記の第１の方式では、タグがいくつかの明白なヒントを生成する。ヒントメッセージを利用することにより、サードパーティ認証機関はタグを特定し、タグにアクセスするために有効なシードを認証されている読取装置に開示できる。

しかしながら、この場合、明白なヒントメッセージを生成する必要はない。読取装置が認証されないメッセージを受信すると、読取装置はメッセージを、ルートシードを検証し、タグを特定できるサードパーティ認証機関に渡す。この場合、タグの出力は暗示的にインデックス情報を含む。タグを特定後、サードパーティ認証機関は特定の回数の読み取り動作のための特定のタグへのアクセスを認める。

まとめると、本発明は、認証されている読取装置のみに、限られた期間、該読取装置に関連する情報にアクセスできるようにする安全で効率的な方法を説明している。これは、タグ識別子を絶えず変更し、タグアクセスを制御するためのさらに多くの柔軟性を与えることにより達成される。

当業者は、本発明を実現するほかの方法もあってよく、したがって本発明が本明細書に説明されている特定の実現例に制限されておらず、本発明が説明されている特定の状況での使用に制限されていないことも理解するであろう。例えば、前述されたツリー構造の使用は２分岐のツリーに制限されず、もっと多くの枝のあるツリーも使用できるであろう。

ＲＦＩＤシステム内のタグに対する一時アクセスを読取装置に提供するための本発明の一実施形態を描く。 図１に描かれている方法のステップを説明するフローチャートである。 どのように、タグがタグ仮名及びヒントメッセージを生成できるのかの第１の実施形態を描く。 ハッシュ方式に基づいたプライベート認証方式を描く。 ２分岐一方向ツリーを描く。 一方向２分岐ツリーを有するハッシュ方式に基づいたプライベート認証方式を描く。 一方向２分岐ツリーと関連してタグにアクセスするためにヒントメッセージがどのようにして使用されるのかを描く。 本発明の代替実施形態における一方向２分岐ツリーの使用を描く。 本発明の代替実施形態における読取動作を描く。 本発明の代替実施形態のヒントメッセージの処理を描く。

Claims (11)

1. 無線周波数識別システムを動作する方法であって、
   前記システムはタグと、読取装置と、サードパーティ認証機関とを含み、
   前記タグは、タグアイデンティティ及び秘密値を備えるタグ名を有し、前記秘密値は前記タグアイデンティティにマッピングされ、
   前記方法は、
   （ｉ）前記読取装置が前記タグを問い合わせるステップと、
   （ｉｉ）応答して前記タグは、前記タグアイデンティティ及び前記秘密値の暗号を備える仮名を送信するステップと、
   （ｉｉｉ）前記読取装置は復号キーのリリースを求める要求であって、前記タグから受け取られる前記仮名を含む要求を前記サードパーティ認証機関に送信するステップと、
   （ｉｖ）前記読取装置は前記復号キーを受け取ることを認証されると判断した前記サードパーティ認証機関が、前記復号キーを前記読取装置に送信するステップと、
   （ｖ）前記読取装置は前記タグアイデンティティを取得するために前記復号キーを使用するステップと、を備え、
   前記復号キーは、前記読取装置と前記サードパーティ認証機関の間で追加のコンタクトなしに前記タグアイデンティティを取得するために所定の複数の回数前記読取装置によって使用できる方法。
2. ステップ（ｉｉ）で送信される前記仮名は、前記読取装置による各問い合わせに応えて変化する、請求項１に記載の方法。
3. ステップ（ｉｉ）において、前記秘密値は一方向ハッシュ関数を使用して暗号化される、請求項１または請求項２に記載の方法。
4. ステップ（ｉｉ）において、前記秘密値は複数の一方向ハッシュ関数を使用して暗号化される、請求項３に記載の方法。
5. 前記仮名は一方向ハッシュツリーの一部である、請求項４に記載の方法。
6. 前記復号キーは一方向ハッシュツリーの一部である、請求項５に記載の方法。
7. ステップ（ｉｉ）における前記タグの応答は、前記一方向ハッシュツリーの中の復号キーの場所を説明する場所的情報をさらに含む、請求項６に記載の方法。
8. 無線周波数識別システムを動作する方法であって、
   前記システムはタグと、読取装置と、サードパーティ認証機関とを含み、
   前記タグは、タグアイデンティティ及び秘密値を備えるタグ名を有し、前記秘密値は前記タグアイデンティティにマッピングされ、
   （ｉ）前記読取装置が前記タグを問い合わせるステップと、
   （ｉｉ）応答して前記タグは、一方向ハッシュツリーの中の復号キーの場所を説明する場所的情報を前記読取装置に送信するステップと、
   （ｉｉｉ）前記読取装置は復号キーのリリースを求める要求であって、前記タグから受け取られる前記場所的情報を含む要求を前記サードパーティ認証機関に送信するステップと、
   （ｉｖ）前記読取装置は前記復号キーを受け取ることを認証されると判断した前記サードパーティ認証機関が、前記復号キーを前記読取装置に送信するステップと、
   （ｖ）前記読取装置は前記タグアイデンティティを取得するために前記復号キーを使用するステップと、を備え、
   前記復号キーは、前記読取装置と前記サードパーティ認証機関の間で追加のコンタクトなしに前記タグアイデンティティを取得するために所定の複数の回数前記読取装置によって使用できる方法。
9. 請求項１または請求項８による無線周波数識別システムを動作する方法で使用するための装置。
10. 請求項１または請求項８による無線周波数識別システムを動作する方法で使用するための無線周波数識別トランスポンダ。
11. 請求項１または請求項８による無線周波数識別システムを動作する方法を実行するためのシステム。

Images