検証デバイスを使用してエンティティを探索するための方法、および関連するデバイス
本発明は、検証デバイス(1)を使用してエンティティのセットに属するエンティティを探索するための方法に関し、検証デバイスとそれらのエンティティは、少なくとも1つの通信チャネル(2)を介して情報を交換するように構成され、エンティティのセットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能である。この方法によれば、検証デバイスにおいて、探索が実行されているエンティティ(4)と関係する第1の識別語(mi;p(xi))が獲得され、第1の識別語は、探索が実行されているエンティティの第1の識別子に、第1の識別子から獲得され得る複数の代表の下位部分に依存するように第1の符号化関数を適用することによって形成され、この下位部分は、少なくとも1つの可変のパラメータ(i)によって決定され、検証デバイスから、通信チャネルを介して、獲得された第1の識別語が送信される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エンティティのセットに属するエンティティを探索することに関する。
【背景技術】
【０００２】
エンティティというのは、任意にデバイス、システム、または個人に関連する任意のハードウェア要素および/またはソフトウェア要素のことである。非限定的な例として、RFID(無線周波数ID)ラベル、アクセスバッジ、チップカード、モバイル電話機、ネットワークに接続されたコンピュータ、その他などのワイヤレスIDタグが挙げられることが可能である。
【０００３】
エンティティを探索するのに、検証デバイスを使用することが知られている。検証デバイスもやはり、そのデバイスが探索することを意図するエンティティのタイプに応じて、様々な形態をとることが可能である。検証デバイスは、例えば、RFID読み取り装置、センサ、サーバ、その他などのワイヤレスID読み取り装置であることが可能である。
【０００４】
検証デバイスとエンティティは、必要に応じて、有線であることも、ワイヤレスであることも可能な、少なくとも1つの通信チャネルを介して互いに通信し、このチャネルは、その目的で提供される。
【０００５】
第1の知られている方法によれば、検証デバイスを使用したエンティティのセットに属するエンティティの探索は、各エンティティから通信チャネルを介してそれぞれの識別子を送信すること、および検証デバイスにおいて、探索されているエンティティが存在すること、または存在しないことについて結論に達するため、受信された識別子を分析することによって実行される。
【０００６】
第2の知られている方法によれば、探索は、検証デバイスから、通信チャネルを介して、探索されているエンティティの識別子を送信し、その後、必要な場合、通信チャネルを介して、この送信の中でそのエンティティの識別子を認識したエンティティから応答を受信することによって実行される。
【０００７】
この第2の方法は、この方法が、通信チャネルを介して交換されるメッセージの数、ならびに探索されているエンティティを見出すのに検証デバイスに要求される処理を制限することを可能にするため、第1の方法より経済的である。
【０００８】
しかし、この第2の方法に問題がないわけではない。
【０００９】
特に、第2の方法は、エンティティのIDを保護しない。このことは、エンティティが個人と関係する場合、それらの個人の私生活の尊重が確実にされないことになるので、特に問題である。また、このことは、第三者による追跡可能性を防止することが望ましい、市場価値および/または金銭的価値を有するハードウェアと関係するエンティティの場合にも問題である。
【００１０】
通信チャネルをリッスンしている攻撃者は、検証デバイスによって送信された識別子をインターセプトして、送られた応答を検出することによって、いずれのエンティティに、この識別子が属するかを見出すことができる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Rudolf AhlswedeおよびGunter Dueck、「Identification via Channels」、IEEE transactions in information theory、Vol.35、No.1、1989年1月
【非特許文献２】Pierre MoulinおよびRalf Koetterによる「A framework for the Design of Good Watermark Identification Codes」、Security, Steganography, and Watermarking of Multimedia Contents VIII, San Jose, California, 565〜574頁、ISBN/ISSN:0-8194-6112-1、2006年1月
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、エンティティのIDの保護を向上させながら、エンティティの探索を許すことである。
【課題を解決するための手段】
【００１３】
このため、本発明は、検証デバイスを使用してエンティティのセットに属するエンティティを探索するための方法を提案し、検証デバイスとエンティティのセットからのエンティティは、少なくとも1つの通信チャネルを介して情報のアイテムを交換するように構成され、エンティティのセットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能である。この方法は、以下のステップを備える。すなわち、
検証デバイスにおいて、探索が実行されているエンティティと関係する第1の識別語を獲得し、第1の識別語は、探索が実行されているエンティティの第1の識別子に、第1の識別子から獲得され得る複数の代表の下位部分に依存するように第1の符号化関数を適用することによって形成され、この下位部分は、少なくとも1つの可変のパラメータによって決定されるステップ、および
検証デバイスから、通信チャネルを介して獲得された第1の識別語を送信するステップである。
【００１４】
代表の1つの部分だけに依存して第1の識別語を生成することができる符号化関数を使用することは、序論で述べた従来技術と比べて、エンティティのIDの保護を大幅に向上させることを可能にする。
【００１５】
考えられ得るすべての仕方で組み合わされることが可能である有利な実施形態によれば、
この方法は、通信チャネルをリッスンしているエンティティのセットからの各エンティティによって実行される、以下のステップをさらに備え、すなわち、
通信チャネルを介して送信された第1の識別語に対応する識別語を受信するステップと、
受信された識別語に第1の符号化関数に関連する第1の識別関数を適用し、さらにそのエンティティの第1の識別子と、その第1の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、そのエンティティによって知られている情報に第1の符号化関数に関連する第1の識別関数を適用して、そのエンティティが探索されているエンティティに対応するかどうかを検証するようにするステップとを備え、さらに/または
獲得された第1の識別語を形成するのに使用された可変のパラメータの値の通知が、検証デバイスから通信チャネルを介して送信され、さらに通信チャネルをリッスンしているエンティティのセットからの各エンティティに関して、第1の識別関数の適用は、受信された可変のパラメータの値の通知を考慮に入れ、さらに/または
第1の識別関数の適用の結果が、そのエンティティが探索されているエンティティに対応することを明らかにした場合、そのエンティティは、通信チャネルを介して検証デバイスに応答を送り、さらに/または
そのエンティティは、第2の識別子を有し、第2の識別子からは、複数の代表が獲得されることが可能であり、第2の識別語が、そのエンティティにおいて、そのエンティティの第2の識別子と、その第2の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、そのエンティティによって知られている情報に、第2の符号化関数を適用して、その第2の識別子から獲得され得る複数の代表の下位部分に依存するようにすることによって獲得され、その下位部分は、少なくとも1つの可変のパラメータによって決定され、そのエンティティによって通信チャネルを介して検証デバイスに送られる応答は、第2の識別語を含み、さらに/または
その応答に含まれる第2の識別語に対応する識別語が、検証デバイスにおいて受信され、検証デバイスは、検証デバイスにおいて受信された識別語に第2の符号化関数に関連する第2の識別関数を適用し、さらにそのエンティティの第2の識別子と、その第2の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、検証デバイスによって知られている情報に第2の符号化関数に関連する第2の識別関数を適用して、そのエンティティと、探索されているエンティティ間の対応のさらなる検証をもたらすようにし、さらに/または
第1の符号化関数は、第1の符号化関数が、探索されているエンティティの第1の識別子に適用されると、可変のパラメータが、第1の識別子から獲得され得る複数の代表のうち少なくとも1つの代表を選択するようになるように構成され、第1の識別関数の適用は、可変のパラメータによって選択される代表と、そのエンティティの第1の識別子から獲得され得る複数の代表のうち少なくとも1つの代表の比較を備え、さらに/または
獲得される第1の識別語を形成するのに使用される可変のパラメータの値は、ランダムに、または準ランダムに選択され、さらに/または
獲得される第1の識別語は、検証デバイスから通信チャネルを介して、誤り訂正符号を使用して符号化されて送信され、さらに/または
通信チャネルは、無線チャネルなどのワイヤレスチャネルであり、さらに検証デバイスは、ワイヤレスID読み取り装置を備え、エンティティのセットからのエンティティの少なくともいくつかは、ワイヤレスIDタグを備え、さらに/または
識別子から獲得され得る複数の代表を獲得する能力は、エンティティのセットからの、その識別子を有するエンティティ、および検証デバイスだけにしか付与されず、さらに/または
第1の符号化関数は、単一の第1の識別語が、可能なすべての識別子のセットからの異なる複数の識別子に第1の符号化関数を適用した結果であることが可能であるように構成される。
【００１６】
本発明は、少なくとも1つの通信チャネルを介してエンティティのセットと情報のアイテムを交換するように構成された検証デバイスをさらに提案し、エンティティのセットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能である。この検証デバイスは、
探索が実行されているエンティティの第1の識別子に第1の符号化関数を適用して、少なくとも1つの可変のパラメータによって決定される、第1の識別子から獲得され得る複数の代表の下位部分に依存するようにすることによって形成される、探索が実行されるエンティティと関係する第1の識別語を獲得するユニットと、
獲得するユニットによって獲得された第1の識別語を、通信チャネルを介して送信するユニットとを備える。
【００１７】
また、本発明は、少なくとも1つの通信チャネルを介して検証デバイスと情報のアイテムを交換することができるとともに、それぞれの第1の識別子をそれぞれが有し、第1の識別子からは、複数の代表が獲得され得る、エンティティのセットに属するエンティティも提案する。このエンティティは、
検証デバイスによって通信チャネルを介して送信された第1の識別語に対応する識別語を受信し、第1の識別語は、探索が実行されているエンティティの第1の識別子に第1の符号化関数を適用して、少なくとも1つの可変のパラメータによって決定される、第1の識別子から獲得され得る複数の代表の下位部分に依存するようにすることによって形成されるユニットと、
受信された識別語に第1の符号化関数に関連する第1の識別関数を適用し、さらにそのエンティティの第1の識別子と、その第1の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、そのエンティティによって知られている情報に第1の符号化関数に関連する第1の識別関数を適用して、そのエンティティが探索されているエンティティに対応するかどうかを検証するようにするユニットとを備える。
【００１８】
本発明は、検証デバイスを使用してエンティティのセットに属するエンティティを探索するためのシステムも提案し、このシステムは、前述した方法を実行するために適合された手段を備える。
【００１９】
本発明のその他の詳細および利点は、添付の図面を参照する、非限定的な実施例の以下の説明から明白となろう。
【図面の簡単な説明】
【００２０】
【図１】本発明を実施することができるシステムの実施例のためのアーキテクチャを示す図である。
【図２】本発明の非限定的な実施例を示す図である。
【図３】本発明の非限定的な実施例を示す図である。
【図４】本発明の非限定的な実施例を示す図である。
【発明を実施するための形態】
【００２１】
図1は、通信チャネル2を介して情報のアイテムを交換するように構成された検証デバイス1とエンティティのセットを示す。図示されるエンティティ3〜5は、これらだけで、既存のエンティティのセットを構成することが可能である。代替として、エンティティ3〜5は、所与の時点で通信チャネルを介して通信することができるエンティティのみに対応することが可能である。その場合、他のエンティティが、観察される他の時点で任意にエンティティ3〜5に追加される、またはエンティティ3〜5に取って代わることが可能である。
【００２２】
序論で述べたとおり、各エンティティ3〜5は、任意にデバイス、システム、または個人に関連する任意のハードウェア要素および/またはソフトウェア要素から成ることが可能である。図1の例では、エンティティ3〜5は、RFID(無線周波数ID)ラベルなどのワイヤレスIDタグであるものとして表されている。代替として、エンティティ3〜5は、アクセスバッジ、チップカード、モバイル電話機、ネットワークに接続されたコンピュータ、その他であることも可能である。さらに、エンティティ3〜5は、すべて同一の性質である必要はない。例として、エンティティ3〜5は、第1の事例でモバイル電話機と関係し、第2の事例で物品に関連付けられたRFIDラベルと関係し、さらに第3の事例でコンピュータと関係することも可能である。
【００２３】
検証デバイス1は、やはり序論で指摘されるとおり、このデバイスが探索することが意図されるエンティティのタイプに応じて、様々な形態をとることも可能である。検証デバイスは、例えば、図1に示されるRFID読み取り装置、センサ、サーバ、その他などのワイヤレスID読み取り装置であることが可能である。
【００２４】
通信チャネル2は、検証デバイス1とエンティティ3〜5の間で情報のアイテムを交換するために適合される。要件に応じて、通信チャネル2は、有線であることも、ワイヤレスであることも可能である。図1の例では、通信チャネル2は、検証デバイス1がRFID読み取り装置であり、エンティティ3〜5の一部またはすべてがRFIDラベルであるので、無線チャネルである。異なる性質の複数のエンティティが検証デバイスと通信することができなければならない場合、いくつかの通信チャネルが使用されることが可能である。例えば、有線通信チャネルおよびワイヤレス通信チャネルが、それぞれ、有線エンティティおよびワイヤレスエンティティに対して使用されることが可能である。
【００２５】
さらに、通信チャネル2は、単純である、すなわち、通信チャネル2は、例えば、所与の無線周波数を介して、検証デバイス1とエンティティ3〜5の間で直接の通信を提供することが可能である。代替として、この通信チャネル2は、より複雑であることが可能である。通信チャネル2は、例えば、コンピュータネットワーク、遠隔通信ネットワーク、その他などの通信ネットワークからの通信リソースのセットから成ることが可能である。
【００２６】
本発明によれば、前述したエンティティのセットに属するエンティティ、例えば、エンティティ4が、検証デバイス1を使用して探索される。つまり、エンティティ4が通信チャネル2をリッスンしているかどうかについての知識が、検証デバイス1を使用して求められる。通信チャネル2が短距離のチャネルである場合、このことは、エンティティ4が検証デバイス1の近くにあるかどうかを探り出すことに相当する。
【００２７】
検証デバイス1、エンティティ3〜5、および通信チャネル2の性質は、目的とされる用途に適合されることが理解されよう。このため、機密情報を扱う場所の内部の個人の存在、または機密情報を扱う場所への少数の個人のアクセスをチェックすることができることが所望される場合、個人に関連付けられたRFIDチップを備えたアクセスバッジをエンティティとして、RFID読み取り装置を検証デバイスとして、さらにRFID技術に適合された周波数を使用する無線チャネルを通信チャネルとして使用することが可能である。代替として、オンラインコンピュータアプリケーションの実施がIDチェックを条件とするようにすることが所望される場合、通信チャネルは、コンピュータネットワークにおける通信リソースから成ることが可能であり、使用されるエンティティは、このネットワークに接続されたコンピュータを備えることが可能であり、検証デバイスは、例えば、このネットワークに接続されたサーバである。
【００２８】
もちろん、当業者には明白となるように、本発明の原理に従って他の用途例が想定されることも可能である。
【００２９】
エンティティ3〜5のそれぞれは、そのエンティティとそれぞれの識別子の間に関連付けが存在するという意味で、それぞれの識別子を有する。そのような識別子から複数の代表が獲得されることが可能である。例えば、或るエンティティと関係する識別子mは、複数の代表mkによって直接に構成されることが可能であり、kは、1から整数nまでの範囲内にあり、すなわち、m=(m1,m2,...,mn)である。この事例において、各代表mkは、mの範囲内の単純な選択によって識別子mから獲得されることが可能である。より一般的には、複数の代表mkは、1つまたは複数の生成関数fkを使用して、対応する識別子mから獲得されることが可能であり、生成関数fkは、その目的で提案される。このことは、以下のとおり表現されることが可能である。すなわち、mk =fk(m)。また、単一の生成関数fが、例えば、反復プロセスによって、既に獲得された1つまたは複数の代表から異なる代表を次々に獲得することで、識別子mからすべての代表mkを導くことを許すようにすることも可能である。
【００３０】
識別子は、例えば、値の連鎖、例えば、2進文字、バイト、その他である。m=(m1,m2,...,mn)である事例において、各代表mkは、例えば、mの1つまたは複数の連続する値を構成することが可能である。もちろん、当業者には明白なとおり、他の設計も可能である。
【００３１】
各識別子は、そのように識別されたエンティティの間の曖昧さを回避するために、好ましくは、一意である。他方、いくつかの識別子は、共通の代表を任意に有することが可能である。
【００３２】
識別子は、与えられたモデルに応じて形成されることが可能である。例として、識別子は、n個の2進文字の連鎖として形成されることが可能であり、このことは、合計で2n個の識別子を得ることを可能にする。このため、実際に関与するエンティティの数より多くの可能な識別子を獲得することが可能である。
【００３３】
エンティティ3〜5のそれぞれは、そのエンティティ3〜5の識別子、またはそのエンティティ3〜5の識別子から獲得され得る複数の代表を知ることができる。この知識は、その識別子および/または対応する代表が、当該のエンティティのメモリの中に格納されることに由来する。代替として、この知識は、外部メモリを調べることによって、外部メモリからそれらの情報のアイテムを受け取ることによって、またはその他のことによって獲得されることも可能である。
【００３４】
検証デバイス1は、エンティティのセットからのエンティティの各エンティティの識別子、および/またはその識別子から獲得され得る複数の代表を知ることができる。この場合も、この知識は、検証デバイス1のメモリの中に格納されること、外部メモリを調べること、外部メモリからそれらの情報のアイテムを受け取ること、またはその他のことに由来することが可能である。
【００３５】
有利には、識別子から獲得され得る複数の代表を獲得する能力は、その識別子を有するエンティティ、および検証デバイスだけにしか付与されない。このことは、いくつかの仕方で実現されることが可能である。
【００３６】
例えば、当該の識別子が、一方で、その識別子を有するエンティティだけしかアクセスすることができず、他方で、検証デバイスだけしかアクセスすることができない、保護されたメモリの中に格納されることが可能である。その識別子は、決して通信チャネルを介して送信されることがない。そのエンティティの識別子は、第三者によって知られていないので、第三者は、その識別子の代表を獲得することができない。
【００３７】
代替として、またはさらに、当該の識別子の代表が、一方でその識別子を有するエンティティだけしかアクセスすることができず、他方で、検証デバイスだけしかアクセスすることができない、保護されたメモリの中に格納されることが可能である。それらの代表は、通信チャネルを介してすべて同時に送信されることはない。したがって、第三者は、そのエンティティと関係する代表を知ることができない。
【００３８】
また、当該の識別子が公開のデータであるが、対応する代表を獲得することを許す生成関数が秘密であるようにすることも可能である。このようにして、識別子を有する第三者が、その識別子から、対応する代表を導くことができることが防止される。
【００３９】
本発明によるエンティティの探索は、識別符号の概念を用いる。識別符号の概念の例は、Rudolf AhlswedeおよびGunter Dueckによる「Identification via Channels」という題名の論文、IEEE transactions in information theory、Vol.35、No.1、1989年1月刊行において説明されている。
【００４０】
一般に、以降、識別語と呼ばれる、そのような識別符号の語cが、識別子mに符号化関数を適用することによって計算され、識別子mからは、kが1から整数nまでの範囲内にある、複数の代表mkが獲得され得る。符号化関数fcは、獲得される識別語が、複数の代表mkの下位部分に依存するように選択される。つまり、識別語は、mの1つまたは複数の代表mkに依存することが可能であるが、すべての代表m1、m2、...、mnに依存することは可能でない。識別語が依存する複数の代表mkの下位部分は、少なくとも1つの可変のパラメータによって決定される。
【００４１】
識別関数fiが、識別子mから識別語cを計算するのに使用される符号化関数fcに関連する。
【００４２】
識別符号の特性は、例えば、以下のとおりである。すなわち、
y1が、識別子mに符号化関数fcを適用することによって獲得された語である場合、y1に識別関数fiを適用し、さらにm、またはmの代表の少なくともいくつかに識別関数fiを適用することは、λ1より低い確率で対応が存在しないと誤って結論付け、さらに
y2が、mとは異なる識別子m'に符号化関数fcを適用することによって獲得された語である場合、y2に識別関数fiを適用し、さらにm、またはmの代表の少なくともいくつかに識別関数fiを適用することは、λ2より低い確率で対応が存在すると誤って結論付ける。
【００４３】
λ1およびλ2が小さいほど、識別符号は信頼性が高い。
【００４４】
有利には、本発明の枠組み内で使用される符号化関数fcは、単一の識別語が、可能なすべての識別子のセットからの異なるいくつかの識別子にその符号化関数fcを適用したことの結果であり得るようにさらに構成されることが可能である。非限定的な例として、識別子がそれぞれ、少なくとも異なる2つの識別子の間でいくつかが共通であることが可能な一連の代表から構成される場合、一連の代表の中から所与の順位の代表を選択することにある符号化関数fcは、異なる2つの識別子に適用されて、ときとして、同一の値を戻す可能性がある。
【００４５】
本発明の枠組み内で使用されることが可能な識別符号の特定の有用な例が、Pierre MoulinおよびRalf Koetterによる「A framework for the Design of Good Watermark Identification Codes」という題名の論文、Security, Steganography, and Watermarking of Multimedia Contents VIII, San Jose, California, 565〜574頁、ISBN/ISSN:0-8194-6112-1、2006年1月刊行において説明されている識別符号である。もちろん、他の任意の識別符号が、この識別符号の代わりに、またはこの識別符号に加えて使用されることも可能である。
【００４６】
本発明によるエンティティの探索は、検証デバイス1の獲得するユニットにおいて、探索されているエンティティと関係する識別語cを獲得することで実施される。この獲得は、前段で開示される原理による計算によって実行されること、検証デバイスにおいて実行されること、検証デバイスに計算された識別語を送信する、異なるデバイスにおいて実行されること、またはこの2つのデバイスの間で分担されるように実行されることが可能である。代替として、この獲得は、例えば、検証デバイス1のメモリの中で、探索されているエンティティと関係する識別語cを見出すことで実現されることも可能である。
【００４７】
検証デバイス1において識別語cが獲得されると、検証デバイス1の送信するユニットが、識別語cを通信チャネル2を介して送信する。通信チャネル2は、すべてのエンティティに共通であるので、送信される識別語は、このチャネルをリッスンしている任意のエンティティ3〜5によって受信され得る。
【００４８】
各エンティティ3〜5は、適切な受信するユニットを使用して、送信された識別語に対応する識別語を受信すると(通信チャネル2が、例えば、雑音があるために、誤りを生じさせる場合に、伝送誤りがある可能性があることを例外として)、次に、適切な適用するユニットを使用して、有利には、受信された識別語に符号化関数fcに関連する識別関数fiを適用し、さらにそのエンティティ3〜5の識別子と、そのエンティティ3〜5の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、そのエンティティ3〜5によって知られている情報に符号化関数fcに関連する識別関数fiを適用して、そのエンティティ3〜5が探索されているエンティティに対応するかどうかを検証するようにすることが可能である。
【００４９】
各エンティティ3〜5によって実行される検証の信頼性を高めるために、検証デバイス1によって獲得された識別語は、有利には、誤り訂正符号である送信符号と一緒に送信される。知られている任意の誤り訂正符号が、その目的で使用されることが可能である。その場合、各エンティティ3〜5は、有利には、そのエンティティ3〜5が、検証デバイス1によって送信された識別語を、誤りなしに、または少なくとも限られた量の誤りしか伴わずに見出すことを許す、関連する復号関数を有する。
【００５０】
エンティティ3〜5、検証デバイス1、および通信チャネル2の性質に適合された誤り訂正符号が選好される。例として、情報のアイテムの交換が、ワイヤレスの、雑音の多い通信チャネル2を介して行われる場合、例えば、高い冗長性を有する、堅牢な誤り訂正符号が選好される。
【００５１】
また、識別子、および識別子の代表が構築される仕方も、使用される誤り訂正符号を選択する際に考慮に入れられることが可能である。例えば、前述した確率λ1とλ2の少なくともいずれかが、より高い場合、識別の低いパフォーマンスを悪化させないために、大量の誤りを訂正することができる誤り訂正符号を選好することが望ましい可能性がある。
【００５２】
次に、本発明により可能な検証のタイプを例示するために非限定的な実施例が説明される。これらすべて実施例において、図1のアーキテクチャが採用され、検証デバイス1を使用してエンティティ4が探索されるものと想定する。
【００５３】
図2に示される例では、エンティティの識別子は、代表の系列から成る値の連鎖である。詳細には、エンティティ4は、識別として、m1、m2、...、mnが代表であるm=(m1,m2,...,mn)を有する。
【００５４】
最初に、検証デバイス1が、1からnまでの間の或る数iを選択する。iの選択は、ランダムに、または準ランダムに実行されることが可能である。次に、検証デバイス1が、連鎖m=(m1,m2,...,mn)の中から順位iのmの代表miを選択する。この場合、識別語cを構成するのは、この代表miである。
【００５５】
この例において、識別子mにおける代表の順位による代表の選択は、この実例では、n個の代表のうちの1つだけである、識別子mから獲得され得る複数の代表の下位部分を決定する可変のパラメータである。
【００５６】
代替として、複数の代表を選択するために、単一のインデックスiではなく、いくつかのインデックスが選択されることも可能である。例えば、1からnまでの間の数(i,j)を任意にランダムに抽出することが、タイプ(mi,mj)の識別語cを獲得すること、あるいは、例えば、mi+mjなどのmiとmjの間の任意の組合せを獲得することを許すことも可能である。
【００５７】
図2のステップ6で、検証デバイス1が、獲得された識別語miを、通信チャネル2を介して送信する。有利には、検証デバイス1は、通信チャネル2を介して、代表miを選択するのに使用された数i、またはiの値の他の任意の通知も送信する。これら2つの情報のアイテムは、単一のメッセージの中で送信されることも、異なる2つのメッセージの中で送信されることも可能である。
【００５８】
その後、通信チャネル2をリッスンしているエンティティ3〜5のそれぞれが、検証デバイス1によって送信された識別語miに対応する識別語を受信して、そのエンティティ3〜5が探索されているエンティティであるかどうかを検証することが可能である。
【００５９】
詳細には、エンティティ4が、いくつかの伝送誤りがある可能性があることを例外として、miに対応する識別語
【００６０】
【数１】
【００６１】
を受信する。また、エンティティ4は、有利には、いくつかの伝送誤りがある可能性があることを例外として、iに対応する数
【００６２】
【数２】
【００６３】
も受信する。
【００６４】
検証デバイス1によって使用された符号化関数fcは、エンティティ4の複数の代表m1、m2、...、mnの中から或る代表を選択することにあった。この符号化関数に関連し、エンティティ4によって(さらに、通信チャネル2をリッスンしているその他のエンティティのそれぞれによっても)使用される識別関数fiは、エンティティ4の識別子mにおいて順位
【００６５】
【数３】
【００６６】
の代表を見出し、次に、その代表を受信された識別語
【００６７】
【数４】
【００６８】
と比較することにある。
【００６９】
合致した場合、エンティティ4は、エンティティ4が実際に探索されているエンティティであると考え、有利には、そのことを検証デバイス1に知らせるために、通信チャネル2を介して検証デバイスに応答7を送る。
【００７０】
数iが検証デバイス1によって送信されない場合、検証はそれでも、エンティティ4において可能であるが、識別語
【００７１】
【数５】
【００７２】
を、順位
【００７３】
【数６】
【００７４】
の単一の代表だけとではなく、代表m1、m2、...、mnの一部またはすべてと比較することによることに留意されたい。
【００７５】
前述の例において、エンティティ4は、例えば、エンティティ4が、エンティティ4の識別子mをメモリの中に格納しているため、識別子mを知ることができたものと考えられた。mの代表m1、m2、...、mnだけがエンティティによって知られており、mにおけるこれらの代表の順序は知られていない場合、受信された識別語
【００７６】
【数７】
【００７７】
を、エンティティ4の知られている代表の一部またはすべてと比較することをやはり行うことが可能である。
【００７８】
この前述の2つの事例において、受信された識別語
【００７９】
【数８】
【００８０】
と、エンティティ4によって知られている、またはmから獲得された代表のいずれか1つが合致することで、エンティティ4が実際に探索されているエンティティであると結論付けるのに十分であり得る。
【００８１】
エンティティ4が通信チャネル2を介して検証デバイス1に応答7を送る場合、この応答は、エンティティ4が、探索されているエンティティに自らが対応すると考えることを単に意味することが可能である。逆に、エンティティ3および5が、探索されているエンティティに自らが対応すると考えない場合、エンティティ3および5は、検証デバイス1に応答を送らない。すると、検証デバイス1は、エンティティ4が実際に、検証デバイス1が探索しているエンティティであると結論付けることができる。
【００８２】
符号化関数は、確率論的であり、決定論的ではないので、いくつかのエンティティが、自らを探索されているエンティティであると考えることが可能である。この場合、検証デバイス1は、通信チャネル2を介して、いくつかのエンティティから、検証デバイス1の要求6に対するいくつかの応答7を受信することが可能である。その場合、有利には、探索されているエンティティを識別するために探索をより細かくすることが可能である。例として、(i,mi)とは異なるペア(j,mj)を選択して、送信することで、エンティティ3〜5に再び問い合わせることが可能である。有利には、送信されるペア(j,mj)は、応答7を送ったエンティティの間の新たな曖昧さを回避するように、つまり、これらのエンティティのうち1つだけが、探索されているエンティティに自らが対応すると考えるように選択される。
【００８３】
図2に示される例において、通信チャネル2を介してエンティティ4によって送られる応答7は、要求6と同一の原理に基づく情報を含む。
【００８４】
この目的で、mに加えて、エンティティ4は、例えば、エンティティ4のメモリの中に格納することによって、第2の識別子M=(M1,M2,...,Mn)、または第2の識別子Mの代表M1、M2、...、Mnの一部またはすべてを、順序を考慮することなしに知っている。エンティティ4は、fcと異なることも、同一であることも可能な第2の符号化関数Fcをも有する。その場合、エンティティ4は、M、および代表M1、M2、...、Mnの少なくとも1つのうちでエンティティ4が知っている情報に第2の符号化関数Fcを適用することによって、第2の識別語を獲得することができる。
【００８５】
図2の例において、第2の符号化関数Fcは、fcと同一であり、第2の符号化関数Fcの可変のパラメータは、検証デバイス1によって選択された値と同一の値に、すなわち、iに固定される。このため、エンティティ4によって送られる応答7は、第2の識別語Miを含む。数iは、検証デバイス1が、第2の符号化関数Fcがfcと同一の、可変のパラメータの値を使用することを知らない場合、Miに加えて、任意で送信されることが可能である。
【００８６】
第2の識別子Mが実際、第1の識別子mと同一であることが可能である。この場合、応答7は、好ましくは、(i,mi)とは異なるペア(j,mj)を含む。
【００８７】
このように応答7の中にさらなる情報を含めることは、検証デバイス1が、IDのさらなる検証を実行することを許すことが可能である。このように機能することは、図2に関連して説明されるタイプの識別子に限定されず、使用される識別子フォーマットがいずれであれ、当てはまり得ることに留意されたい。
【００８８】
IDのそのようなさらなる検証を実行するために、検証デバイス1は、有利には、第2の符号化関数Fcに関連する第2の識別関数Fiを有する。エンティティ4と関係して説明されたとおり、検証デバイス1は、検証デバイス1において受信された識別語
【００８９】
【数９】
【００９０】
に第2の識別関数Fiを適用し、さらにエンティティ4の識別子M、および識別子Mの代表M1、M2、...、Mnの少なくとも1つのうちから、検証デバイス1によって知られている情報に第2の識別関数Fiを適用する。
【００９１】
このさらなる検証は、エンティティ4が探索されているエンティティであることを確認すること、または逆に否定することを可能にする。このオプションは、このオプションが、本発明の確率論的モデルにおいて生じる可能性がある識別の誤りを限定するため、有用である。
【００９２】
序論で述べた従来技術の方法と比較して、以上に説明された実施例は、本発明が、エンティティのIDの保護を向上させるエンティティの探索を可能にすることができることを理解することを許す。
【００９３】
通信チャネル2をリッスンしており、エンティティの識別子、および識別子の代表の知識をアプリオリに有さない攻撃者は、一般に、送信された代表miおよびMiからエンティティ4の識別子mを見出すことができない。
【００９４】
通信チャネル2をリッスンしている攻撃者の作業は、実施される符号化が確率論的であり、決定論的ではないことにより、符号化が少なくとも1つの可変のパラメータに依存するので、特に困難にされる。このことから、異なる識別語が、単一のエンティティを識別することを許すことが可能である。
【００９５】
さらに、可能な識別語の総数は、識別子の総数よりはるかに多い。したがって、攻撃者が、限られた時間にわたって通信チャネル2をリッスンすることで、所与のエンティティと関係するすべての識別語を見出すことは、ほぼ不可能である。
【００９６】
さらに、攻撃者が、いくつかのエンティティの識別子、および/またはそれらの識別子の代表を知ることができるとした場合でも、攻撃者は、特に、符号化関数が、異なる複数の識別子に適用された場合に、単一の識別語をもたらす可能性がある場合に、応答を送ったエンティティのIDについて確実に結論付けることは必ずしもできない。
【００９７】
このようにして、本発明は、個人の私生活の尊重を向上させること、およびデバイスの追跡可能性をより困難にする。
【００９８】
本発明の別の利点は、本発明の効率にある。図2に関連して説明される例において、識別子mを構成する各代表m1、m2、...、mnが1バイト、すなわち、8ビットであると想定した場合、探索は、おおよそで1バイトの送信(ステップ6におけるm1の送信)だけしか要求しないことが可能である。これと比較して、従来技術の場合のような、検証デバイスによる識別子m=(m1,m2,...,mn)の全部の送信は、nバイトを必要とする。
【００９９】
前述した利点は、当業者には明白となるように、図2に関連して説明される実施例に限定されない。
【０１００】
図3は、本発明の別の実施例を示す。この実施例において、エンティティ3〜5のそれぞれは、それぞれの多項式の形態で識別子を有する。そのような識別子から獲得されることが可能な代表は、例えば、異なるポイントにおける、この多項式の評価、またはこの多項式の係数である。
【０１０１】
例えば、エンティティ4と関係する識別子は、多項式p(x)であることが可能であり、対応する代表は、nが整数である所定のポイントx1、x2、...、xnのセットにおける、この多項式の評価、すなわち、p(x1)、p(x2)、...、p(xn)であることが可能である。
【０１０２】
この場合に検証デバイス1によって使用される符号化関数fcは、例えば、これらの評価のうち1つ、例えば、p(xi)をランダムに選択することにあることが可能である。この識別語p(xi)は、ステップ8で、検証デバイス1から通信チャネル2を介して送信される。
【０１０３】
対応する識別語を受信すると、通信チャネル2をリッスンしているエンティティ3〜5のそれぞれは、合致の可能性を判定するために、その識別語を、そのエンティティが、例えば、そのエンティティのメモリの中に有する評価の一部またはすべてと比較する。
【０１０４】
例えば、エンティティ4に関して合致した場合、エンティティ4が、通信チャネル2を介して検証デバイス1に応答9を送る。この応答は、例えば、x1、x2、...、xnとは異なるポイントXiに多項式pを適用することによって獲得された評価p(Xi)を含むことが可能である。代替として、応答9は、Pがpとは異なる多項式である評価P(xi)を含むことも可能である。別の代替として、応答9は、jがiとは異なる評価p(xj)を含むことも可能である。
【０１０５】
図4は、各エンティティが、例えば、1,000から10,000までの間の或る数を識別子として有し、さらにこの識別子から獲得され得る代表が、固定長、例えば、20,000であるとともに、対応する識別子と等しい重みが付けられた二値ベクトルである、別の実施例を示す。このため、Nが1,000から10,000までの間にある識別子Nから獲得され得るすべての代表m1、m2、...、mnは、例えば、Nと等しい数の1と、20,000-Nと等しい数の0とを有し、これらの代表は、0および1の位置によって互いに異なる。これらの数値は、単に例として与えられており、主題の一般性を限定するものではないことが理解されよう。
【０１０６】
識別子Nのエンティティ4を探索する検証デバイス1は、例えば、識別子Nの代表mi、すなわち、Nビットが1であり、20,000-Nビットが0である二値ベクトルをランダムに選択する。次に、検証デバイス1は、ステップ10で、代表miを識別語として通信チャネル2を介して送信する。
【０１０７】
エンティティ4は、エンティティ4の識別子Nを、例えば、エンティティ4が、識別子Nをエンティティ4のメモリの中に格納しているため、知っている。送信された代表miに対応する、長さ20,000の識別語を受信すると、エンティティ4は、この識別語の重み、つまり、この識別語の1の数を計算し、その数をNと比較する。このことには、受信された識別語、およびエンティティ4の識別子Nに識別関数が適用されることがかかわる。
【０１０８】
等しい場合、エンティティ4は、エンティティ4が、探索されているエンティティであると考え、通信チャネル2を介して検証デバイス1に応答11を送る。この応答は、検証デバイス1によってそのように解釈されることが可能である。この例では、応答11は、他の有用な情報は含まない。
【０１０９】
図2から図4を参照して説明される例は、限定的ではないことが当業者には理解されよう。前述した本発明の一般的な原理により、他の多数の可能性が想定されることが可能である。詳細には、説明されたのとは異なる符号化関数および/または識別関数が使用されることが可能である。
【０１１０】
様々な図を参照して説明される動作の一部またはすべては、部分的に、または完全にソフトウェアで実施される、つまり、その目的に適合されたコード命令を備えるコンピュータプログラム製品を使用して実施されることが可能であることに留意されたい。代替として、またはさらに、これらのステップの少なくともいくつかは、電子回路を使用して実施されることが可能である。
【符号の説明】
【０１１１】
1 検証デバイス
2 通信チャネル
3、4、5 エンティティ
6 要求
7、9、11 応答
【技術分野】
【０００１】
本発明は、エンティティのセットに属するエンティティを探索することに関する。
【背景技術】
【０００２】
エンティティというのは、任意にデバイス、システム、または個人に関連する任意のハードウェア要素および/またはソフトウェア要素のことである。非限定的な例として、RFID(無線周波数ID)ラベル、アクセスバッジ、チップカード、モバイル電話機、ネットワークに接続されたコンピュータ、その他などのワイヤレスIDタグが挙げられることが可能である。
【０００３】
エンティティを探索するのに、検証デバイスを使用することが知られている。検証デバイスもやはり、そのデバイスが探索することを意図するエンティティのタイプに応じて、様々な形態をとることが可能である。検証デバイスは、例えば、RFID読み取り装置、センサ、サーバ、その他などのワイヤレスID読み取り装置であることが可能である。
【０００４】
検証デバイスとエンティティは、必要に応じて、有線であることも、ワイヤレスであることも可能な、少なくとも1つの通信チャネルを介して互いに通信し、このチャネルは、その目的で提供される。
【０００５】
第1の知られている方法によれば、検証デバイスを使用したエンティティのセットに属するエンティティの探索は、各エンティティから通信チャネルを介してそれぞれの識別子を送信すること、および検証デバイスにおいて、探索されているエンティティが存在すること、または存在しないことについて結論に達するため、受信された識別子を分析することによって実行される。
【０００６】
第2の知られている方法によれば、探索は、検証デバイスから、通信チャネルを介して、探索されているエンティティの識別子を送信し、その後、必要な場合、通信チャネルを介して、この送信の中でそのエンティティの識別子を認識したエンティティから応答を受信することによって実行される。
【０００７】
この第2の方法は、この方法が、通信チャネルを介して交換されるメッセージの数、ならびに探索されているエンティティを見出すのに検証デバイスに要求される処理を制限することを可能にするため、第1の方法より経済的である。
【０００８】
しかし、この第2の方法に問題がないわけではない。
【０００９】
特に、第2の方法は、エンティティのIDを保護しない。このことは、エンティティが個人と関係する場合、それらの個人の私生活の尊重が確実にされないことになるので、特に問題である。また、このことは、第三者による追跡可能性を防止することが望ましい、市場価値および/または金銭的価値を有するハードウェアと関係するエンティティの場合にも問題である。
【００１０】
通信チャネルをリッスンしている攻撃者は、検証デバイスによって送信された識別子をインターセプトして、送られた応答を検出することによって、いずれのエンティティに、この識別子が属するかを見出すことができる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Rudolf AhlswedeおよびGunter Dueck、「Identification via Channels」、IEEE transactions in information theory、Vol.35、No.1、1989年1月
【非特許文献２】Pierre MoulinおよびRalf Koetterによる「A framework for the Design of Good Watermark Identification Codes」、Security, Steganography, and Watermarking of Multimedia Contents VIII, San Jose, California, 565〜574頁、ISBN/ISSN:0-8194-6112-1、2006年1月
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、エンティティのIDの保護を向上させながら、エンティティの探索を許すことである。
【課題を解決するための手段】
【００１３】
このため、本発明は、検証デバイスを使用してエンティティのセットに属するエンティティを探索するための方法を提案し、検証デバイスとエンティティのセットからのエンティティは、少なくとも1つの通信チャネルを介して情報のアイテムを交換するように構成され、エンティティのセットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能である。この方法は、以下のステップを備える。すなわち、
検証デバイスにおいて、探索が実行されているエンティティと関係する第1の識別語を獲得し、第1の識別語は、探索が実行されているエンティティの第1の識別子に、第1の識別子から獲得され得る複数の代表の下位部分に依存するように第1の符号化関数を適用することによって形成され、この下位部分は、少なくとも1つの可変のパラメータによって決定されるステップ、および
検証デバイスから、通信チャネルを介して獲得された第1の識別語を送信するステップである。
【００１４】
代表の1つの部分だけに依存して第1の識別語を生成することができる符号化関数を使用することは、序論で述べた従来技術と比べて、エンティティのIDの保護を大幅に向上させることを可能にする。
【００１５】
考えられ得るすべての仕方で組み合わされることが可能である有利な実施形態によれば、
この方法は、通信チャネルをリッスンしているエンティティのセットからの各エンティティによって実行される、以下のステップをさらに備え、すなわち、
通信チャネルを介して送信された第1の識別語に対応する識別語を受信するステップと、
受信された識別語に第1の符号化関数に関連する第1の識別関数を適用し、さらにそのエンティティの第1の識別子と、その第1の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、そのエンティティによって知られている情報に第1の符号化関数に関連する第1の識別関数を適用して、そのエンティティが探索されているエンティティに対応するかどうかを検証するようにするステップとを備え、さらに/または
獲得された第1の識別語を形成するのに使用された可変のパラメータの値の通知が、検証デバイスから通信チャネルを介して送信され、さらに通信チャネルをリッスンしているエンティティのセットからの各エンティティに関して、第1の識別関数の適用は、受信された可変のパラメータの値の通知を考慮に入れ、さらに/または
第1の識別関数の適用の結果が、そのエンティティが探索されているエンティティに対応することを明らかにした場合、そのエンティティは、通信チャネルを介して検証デバイスに応答を送り、さらに/または
そのエンティティは、第2の識別子を有し、第2の識別子からは、複数の代表が獲得されることが可能であり、第2の識別語が、そのエンティティにおいて、そのエンティティの第2の識別子と、その第2の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、そのエンティティによって知られている情報に、第2の符号化関数を適用して、その第2の識別子から獲得され得る複数の代表の下位部分に依存するようにすることによって獲得され、その下位部分は、少なくとも1つの可変のパラメータによって決定され、そのエンティティによって通信チャネルを介して検証デバイスに送られる応答は、第2の識別語を含み、さらに/または
その応答に含まれる第2の識別語に対応する識別語が、検証デバイスにおいて受信され、検証デバイスは、検証デバイスにおいて受信された識別語に第2の符号化関数に関連する第2の識別関数を適用し、さらにそのエンティティの第2の識別子と、その第2の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、検証デバイスによって知られている情報に第2の符号化関数に関連する第2の識別関数を適用して、そのエンティティと、探索されているエンティティ間の対応のさらなる検証をもたらすようにし、さらに/または
第1の符号化関数は、第1の符号化関数が、探索されているエンティティの第1の識別子に適用されると、可変のパラメータが、第1の識別子から獲得され得る複数の代表のうち少なくとも1つの代表を選択するようになるように構成され、第1の識別関数の適用は、可変のパラメータによって選択される代表と、そのエンティティの第1の識別子から獲得され得る複数の代表のうち少なくとも1つの代表の比較を備え、さらに/または
獲得される第1の識別語を形成するのに使用される可変のパラメータの値は、ランダムに、または準ランダムに選択され、さらに/または
獲得される第1の識別語は、検証デバイスから通信チャネルを介して、誤り訂正符号を使用して符号化されて送信され、さらに/または
通信チャネルは、無線チャネルなどのワイヤレスチャネルであり、さらに検証デバイスは、ワイヤレスID読み取り装置を備え、エンティティのセットからのエンティティの少なくともいくつかは、ワイヤレスIDタグを備え、さらに/または
識別子から獲得され得る複数の代表を獲得する能力は、エンティティのセットからの、その識別子を有するエンティティ、および検証デバイスだけにしか付与されず、さらに/または
第1の符号化関数は、単一の第1の識別語が、可能なすべての識別子のセットからの異なる複数の識別子に第1の符号化関数を適用した結果であることが可能であるように構成される。
【００１６】
本発明は、少なくとも1つの通信チャネルを介してエンティティのセットと情報のアイテムを交換するように構成された検証デバイスをさらに提案し、エンティティのセットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能である。この検証デバイスは、
探索が実行されているエンティティの第1の識別子に第1の符号化関数を適用して、少なくとも1つの可変のパラメータによって決定される、第1の識別子から獲得され得る複数の代表の下位部分に依存するようにすることによって形成される、探索が実行されるエンティティと関係する第1の識別語を獲得するユニットと、
獲得するユニットによって獲得された第1の識別語を、通信チャネルを介して送信するユニットとを備える。
【００１７】
また、本発明は、少なくとも1つの通信チャネルを介して検証デバイスと情報のアイテムを交換することができるとともに、それぞれの第1の識別子をそれぞれが有し、第1の識別子からは、複数の代表が獲得され得る、エンティティのセットに属するエンティティも提案する。このエンティティは、
検証デバイスによって通信チャネルを介して送信された第1の識別語に対応する識別語を受信し、第1の識別語は、探索が実行されているエンティティの第1の識別子に第1の符号化関数を適用して、少なくとも1つの可変のパラメータによって決定される、第1の識別子から獲得され得る複数の代表の下位部分に依存するようにすることによって形成されるユニットと、
受信された識別語に第1の符号化関数に関連する第1の識別関数を適用し、さらにそのエンティティの第1の識別子と、その第1の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、そのエンティティによって知られている情報に第1の符号化関数に関連する第1の識別関数を適用して、そのエンティティが探索されているエンティティに対応するかどうかを検証するようにするユニットとを備える。
【００１８】
本発明は、検証デバイスを使用してエンティティのセットに属するエンティティを探索するためのシステムも提案し、このシステムは、前述した方法を実行するために適合された手段を備える。
【００１９】
本発明のその他の詳細および利点は、添付の図面を参照する、非限定的な実施例の以下の説明から明白となろう。
【図面の簡単な説明】
【００２０】
【図１】本発明を実施することができるシステムの実施例のためのアーキテクチャを示す図である。
【図２】本発明の非限定的な実施例を示す図である。
【図３】本発明の非限定的な実施例を示す図である。
【図４】本発明の非限定的な実施例を示す図である。
【発明を実施するための形態】
【００２１】
図1は、通信チャネル2を介して情報のアイテムを交換するように構成された検証デバイス1とエンティティのセットを示す。図示されるエンティティ3〜5は、これらだけで、既存のエンティティのセットを構成することが可能である。代替として、エンティティ3〜5は、所与の時点で通信チャネルを介して通信することができるエンティティのみに対応することが可能である。その場合、他のエンティティが、観察される他の時点で任意にエンティティ3〜5に追加される、またはエンティティ3〜5に取って代わることが可能である。
【００２２】
序論で述べたとおり、各エンティティ3〜5は、任意にデバイス、システム、または個人に関連する任意のハードウェア要素および/またはソフトウェア要素から成ることが可能である。図1の例では、エンティティ3〜5は、RFID(無線周波数ID)ラベルなどのワイヤレスIDタグであるものとして表されている。代替として、エンティティ3〜5は、アクセスバッジ、チップカード、モバイル電話機、ネットワークに接続されたコンピュータ、その他であることも可能である。さらに、エンティティ3〜5は、すべて同一の性質である必要はない。例として、エンティティ3〜5は、第1の事例でモバイル電話機と関係し、第2の事例で物品に関連付けられたRFIDラベルと関係し、さらに第3の事例でコンピュータと関係することも可能である。
【００２３】
検証デバイス1は、やはり序論で指摘されるとおり、このデバイスが探索することが意図されるエンティティのタイプに応じて、様々な形態をとることも可能である。検証デバイスは、例えば、図1に示されるRFID読み取り装置、センサ、サーバ、その他などのワイヤレスID読み取り装置であることが可能である。
【００２４】
通信チャネル2は、検証デバイス1とエンティティ3〜5の間で情報のアイテムを交換するために適合される。要件に応じて、通信チャネル2は、有線であることも、ワイヤレスであることも可能である。図1の例では、通信チャネル2は、検証デバイス1がRFID読み取り装置であり、エンティティ3〜5の一部またはすべてがRFIDラベルであるので、無線チャネルである。異なる性質の複数のエンティティが検証デバイスと通信することができなければならない場合、いくつかの通信チャネルが使用されることが可能である。例えば、有線通信チャネルおよびワイヤレス通信チャネルが、それぞれ、有線エンティティおよびワイヤレスエンティティに対して使用されることが可能である。
【００２５】
さらに、通信チャネル2は、単純である、すなわち、通信チャネル2は、例えば、所与の無線周波数を介して、検証デバイス1とエンティティ3〜5の間で直接の通信を提供することが可能である。代替として、この通信チャネル2は、より複雑であることが可能である。通信チャネル2は、例えば、コンピュータネットワーク、遠隔通信ネットワーク、その他などの通信ネットワークからの通信リソースのセットから成ることが可能である。
【００２６】
本発明によれば、前述したエンティティのセットに属するエンティティ、例えば、エンティティ4が、検証デバイス1を使用して探索される。つまり、エンティティ4が通信チャネル2をリッスンしているかどうかについての知識が、検証デバイス1を使用して求められる。通信チャネル2が短距離のチャネルである場合、このことは、エンティティ4が検証デバイス1の近くにあるかどうかを探り出すことに相当する。
【００２７】
検証デバイス1、エンティティ3〜5、および通信チャネル2の性質は、目的とされる用途に適合されることが理解されよう。このため、機密情報を扱う場所の内部の個人の存在、または機密情報を扱う場所への少数の個人のアクセスをチェックすることができることが所望される場合、個人に関連付けられたRFIDチップを備えたアクセスバッジをエンティティとして、RFID読み取り装置を検証デバイスとして、さらにRFID技術に適合された周波数を使用する無線チャネルを通信チャネルとして使用することが可能である。代替として、オンラインコンピュータアプリケーションの実施がIDチェックを条件とするようにすることが所望される場合、通信チャネルは、コンピュータネットワークにおける通信リソースから成ることが可能であり、使用されるエンティティは、このネットワークに接続されたコンピュータを備えることが可能であり、検証デバイスは、例えば、このネットワークに接続されたサーバである。
【００２８】
もちろん、当業者には明白となるように、本発明の原理に従って他の用途例が想定されることも可能である。
【００２９】
エンティティ3〜5のそれぞれは、そのエンティティとそれぞれの識別子の間に関連付けが存在するという意味で、それぞれの識別子を有する。そのような識別子から複数の代表が獲得されることが可能である。例えば、或るエンティティと関係する識別子mは、複数の代表mkによって直接に構成されることが可能であり、kは、1から整数nまでの範囲内にあり、すなわち、m=(m1,m2,...,mn)である。この事例において、各代表mkは、mの範囲内の単純な選択によって識別子mから獲得されることが可能である。より一般的には、複数の代表mkは、1つまたは複数の生成関数fkを使用して、対応する識別子mから獲得されることが可能であり、生成関数fkは、その目的で提案される。このことは、以下のとおり表現されることが可能である。すなわち、mk =fk(m)。また、単一の生成関数fが、例えば、反復プロセスによって、既に獲得された1つまたは複数の代表から異なる代表を次々に獲得することで、識別子mからすべての代表mkを導くことを許すようにすることも可能である。
【００３０】
識別子は、例えば、値の連鎖、例えば、2進文字、バイト、その他である。m=(m1,m2,...,mn)である事例において、各代表mkは、例えば、mの1つまたは複数の連続する値を構成することが可能である。もちろん、当業者には明白なとおり、他の設計も可能である。
【００３１】
各識別子は、そのように識別されたエンティティの間の曖昧さを回避するために、好ましくは、一意である。他方、いくつかの識別子は、共通の代表を任意に有することが可能である。
【００３２】
識別子は、与えられたモデルに応じて形成されることが可能である。例として、識別子は、n個の2進文字の連鎖として形成されることが可能であり、このことは、合計で2n個の識別子を得ることを可能にする。このため、実際に関与するエンティティの数より多くの可能な識別子を獲得することが可能である。
【００３３】
エンティティ3〜5のそれぞれは、そのエンティティ3〜5の識別子、またはそのエンティティ3〜5の識別子から獲得され得る複数の代表を知ることができる。この知識は、その識別子および/または対応する代表が、当該のエンティティのメモリの中に格納されることに由来する。代替として、この知識は、外部メモリを調べることによって、外部メモリからそれらの情報のアイテムを受け取ることによって、またはその他のことによって獲得されることも可能である。
【００３４】
検証デバイス1は、エンティティのセットからのエンティティの各エンティティの識別子、および/またはその識別子から獲得され得る複数の代表を知ることができる。この場合も、この知識は、検証デバイス1のメモリの中に格納されること、外部メモリを調べること、外部メモリからそれらの情報のアイテムを受け取ること、またはその他のことに由来することが可能である。
【００３５】
有利には、識別子から獲得され得る複数の代表を獲得する能力は、その識別子を有するエンティティ、および検証デバイスだけにしか付与されない。このことは、いくつかの仕方で実現されることが可能である。
【００３６】
例えば、当該の識別子が、一方で、その識別子を有するエンティティだけしかアクセスすることができず、他方で、検証デバイスだけしかアクセスすることができない、保護されたメモリの中に格納されることが可能である。その識別子は、決して通信チャネルを介して送信されることがない。そのエンティティの識別子は、第三者によって知られていないので、第三者は、その識別子の代表を獲得することができない。
【００３７】
代替として、またはさらに、当該の識別子の代表が、一方でその識別子を有するエンティティだけしかアクセスすることができず、他方で、検証デバイスだけしかアクセスすることができない、保護されたメモリの中に格納されることが可能である。それらの代表は、通信チャネルを介してすべて同時に送信されることはない。したがって、第三者は、そのエンティティと関係する代表を知ることができない。
【００３８】
また、当該の識別子が公開のデータであるが、対応する代表を獲得することを許す生成関数が秘密であるようにすることも可能である。このようにして、識別子を有する第三者が、その識別子から、対応する代表を導くことができることが防止される。
【００３９】
本発明によるエンティティの探索は、識別符号の概念を用いる。識別符号の概念の例は、Rudolf AhlswedeおよびGunter Dueckによる「Identification via Channels」という題名の論文、IEEE transactions in information theory、Vol.35、No.1、1989年1月刊行において説明されている。
【００４０】
一般に、以降、識別語と呼ばれる、そのような識別符号の語cが、識別子mに符号化関数を適用することによって計算され、識別子mからは、kが1から整数nまでの範囲内にある、複数の代表mkが獲得され得る。符号化関数fcは、獲得される識別語が、複数の代表mkの下位部分に依存するように選択される。つまり、識別語は、mの1つまたは複数の代表mkに依存することが可能であるが、すべての代表m1、m2、...、mnに依存することは可能でない。識別語が依存する複数の代表mkの下位部分は、少なくとも1つの可変のパラメータによって決定される。
【００４１】
識別関数fiが、識別子mから識別語cを計算するのに使用される符号化関数fcに関連する。
【００４２】
識別符号の特性は、例えば、以下のとおりである。すなわち、
y1が、識別子mに符号化関数fcを適用することによって獲得された語である場合、y1に識別関数fiを適用し、さらにm、またはmの代表の少なくともいくつかに識別関数fiを適用することは、λ1より低い確率で対応が存在しないと誤って結論付け、さらに
y2が、mとは異なる識別子m'に符号化関数fcを適用することによって獲得された語である場合、y2に識別関数fiを適用し、さらにm、またはmの代表の少なくともいくつかに識別関数fiを適用することは、λ2より低い確率で対応が存在すると誤って結論付ける。
【００４３】
λ1およびλ2が小さいほど、識別符号は信頼性が高い。
【００４４】
有利には、本発明の枠組み内で使用される符号化関数fcは、単一の識別語が、可能なすべての識別子のセットからの異なるいくつかの識別子にその符号化関数fcを適用したことの結果であり得るようにさらに構成されることが可能である。非限定的な例として、識別子がそれぞれ、少なくとも異なる2つの識別子の間でいくつかが共通であることが可能な一連の代表から構成される場合、一連の代表の中から所与の順位の代表を選択することにある符号化関数fcは、異なる2つの識別子に適用されて、ときとして、同一の値を戻す可能性がある。
【００４５】
本発明の枠組み内で使用されることが可能な識別符号の特定の有用な例が、Pierre MoulinおよびRalf Koetterによる「A framework for the Design of Good Watermark Identification Codes」という題名の論文、Security, Steganography, and Watermarking of Multimedia Contents VIII, San Jose, California, 565〜574頁、ISBN/ISSN:0-8194-6112-1、2006年1月刊行において説明されている識別符号である。もちろん、他の任意の識別符号が、この識別符号の代わりに、またはこの識別符号に加えて使用されることも可能である。
【００４６】
本発明によるエンティティの探索は、検証デバイス1の獲得するユニットにおいて、探索されているエンティティと関係する識別語cを獲得することで実施される。この獲得は、前段で開示される原理による計算によって実行されること、検証デバイスにおいて実行されること、検証デバイスに計算された識別語を送信する、異なるデバイスにおいて実行されること、またはこの2つのデバイスの間で分担されるように実行されることが可能である。代替として、この獲得は、例えば、検証デバイス1のメモリの中で、探索されているエンティティと関係する識別語cを見出すことで実現されることも可能である。
【００４７】
検証デバイス1において識別語cが獲得されると、検証デバイス1の送信するユニットが、識別語cを通信チャネル2を介して送信する。通信チャネル2は、すべてのエンティティに共通であるので、送信される識別語は、このチャネルをリッスンしている任意のエンティティ3〜5によって受信され得る。
【００４８】
各エンティティ3〜5は、適切な受信するユニットを使用して、送信された識別語に対応する識別語を受信すると(通信チャネル2が、例えば、雑音があるために、誤りを生じさせる場合に、伝送誤りがある可能性があることを例外として)、次に、適切な適用するユニットを使用して、有利には、受信された識別語に符号化関数fcに関連する識別関数fiを適用し、さらにそのエンティティ3〜5の識別子と、そのエンティティ3〜5の識別子から獲得され得る複数の代表の少なくとも1つの代表のうちから、そのエンティティ3〜5によって知られている情報に符号化関数fcに関連する識別関数fiを適用して、そのエンティティ3〜5が探索されているエンティティに対応するかどうかを検証するようにすることが可能である。
【００４９】
各エンティティ3〜5によって実行される検証の信頼性を高めるために、検証デバイス1によって獲得された識別語は、有利には、誤り訂正符号である送信符号と一緒に送信される。知られている任意の誤り訂正符号が、その目的で使用されることが可能である。その場合、各エンティティ3〜5は、有利には、そのエンティティ3〜5が、検証デバイス1によって送信された識別語を、誤りなしに、または少なくとも限られた量の誤りしか伴わずに見出すことを許す、関連する復号関数を有する。
【００５０】
エンティティ3〜5、検証デバイス1、および通信チャネル2の性質に適合された誤り訂正符号が選好される。例として、情報のアイテムの交換が、ワイヤレスの、雑音の多い通信チャネル2を介して行われる場合、例えば、高い冗長性を有する、堅牢な誤り訂正符号が選好される。
【００５１】
また、識別子、および識別子の代表が構築される仕方も、使用される誤り訂正符号を選択する際に考慮に入れられることが可能である。例えば、前述した確率λ1とλ2の少なくともいずれかが、より高い場合、識別の低いパフォーマンスを悪化させないために、大量の誤りを訂正することができる誤り訂正符号を選好することが望ましい可能性がある。
【００５２】
次に、本発明により可能な検証のタイプを例示するために非限定的な実施例が説明される。これらすべて実施例において、図1のアーキテクチャが採用され、検証デバイス1を使用してエンティティ4が探索されるものと想定する。
【００５３】
図2に示される例では、エンティティの識別子は、代表の系列から成る値の連鎖である。詳細には、エンティティ4は、識別として、m1、m2、...、mnが代表であるm=(m1,m2,...,mn)を有する。
【００５４】
最初に、検証デバイス1が、1からnまでの間の或る数iを選択する。iの選択は、ランダムに、または準ランダムに実行されることが可能である。次に、検証デバイス1が、連鎖m=(m1,m2,...,mn)の中から順位iのmの代表miを選択する。この場合、識別語cを構成するのは、この代表miである。
【００５５】
この例において、識別子mにおける代表の順位による代表の選択は、この実例では、n個の代表のうちの1つだけである、識別子mから獲得され得る複数の代表の下位部分を決定する可変のパラメータである。
【００５６】
代替として、複数の代表を選択するために、単一のインデックスiではなく、いくつかのインデックスが選択されることも可能である。例えば、1からnまでの間の数(i,j)を任意にランダムに抽出することが、タイプ(mi,mj)の識別語cを獲得すること、あるいは、例えば、mi+mjなどのmiとmjの間の任意の組合せを獲得することを許すことも可能である。
【００５７】
図2のステップ6で、検証デバイス1が、獲得された識別語miを、通信チャネル2を介して送信する。有利には、検証デバイス1は、通信チャネル2を介して、代表miを選択するのに使用された数i、またはiの値の他の任意の通知も送信する。これら2つの情報のアイテムは、単一のメッセージの中で送信されることも、異なる2つのメッセージの中で送信されることも可能である。
【００５８】
その後、通信チャネル2をリッスンしているエンティティ3〜5のそれぞれが、検証デバイス1によって送信された識別語miに対応する識別語を受信して、そのエンティティ3〜5が探索されているエンティティであるかどうかを検証することが可能である。
【００５９】
詳細には、エンティティ4が、いくつかの伝送誤りがある可能性があることを例外として、miに対応する識別語
【００６０】
【数１】
【００６１】
を受信する。また、エンティティ4は、有利には、いくつかの伝送誤りがある可能性があることを例外として、iに対応する数
【００６２】
【数２】
【００６３】
も受信する。
【００６４】
検証デバイス1によって使用された符号化関数fcは、エンティティ4の複数の代表m1、m2、...、mnの中から或る代表を選択することにあった。この符号化関数に関連し、エンティティ4によって(さらに、通信チャネル2をリッスンしているその他のエンティティのそれぞれによっても)使用される識別関数fiは、エンティティ4の識別子mにおいて順位
【００６５】
【数３】
【００６６】
の代表を見出し、次に、その代表を受信された識別語
【００６７】
【数４】
【００６８】
と比較することにある。
【００６９】
合致した場合、エンティティ4は、エンティティ4が実際に探索されているエンティティであると考え、有利には、そのことを検証デバイス1に知らせるために、通信チャネル2を介して検証デバイスに応答7を送る。
【００７０】
数iが検証デバイス1によって送信されない場合、検証はそれでも、エンティティ4において可能であるが、識別語
【００７１】
【数５】
【００７２】
を、順位
【００７３】
【数６】
【００７４】
の単一の代表だけとではなく、代表m1、m2、...、mnの一部またはすべてと比較することによることに留意されたい。
【００７５】
前述の例において、エンティティ4は、例えば、エンティティ4が、エンティティ4の識別子mをメモリの中に格納しているため、識別子mを知ることができたものと考えられた。mの代表m1、m2、...、mnだけがエンティティによって知られており、mにおけるこれらの代表の順序は知られていない場合、受信された識別語
【００７６】
【数７】
【００７７】
を、エンティティ4の知られている代表の一部またはすべてと比較することをやはり行うことが可能である。
【００７８】
この前述の2つの事例において、受信された識別語
【００７９】
【数８】
【００８０】
と、エンティティ4によって知られている、またはmから獲得された代表のいずれか1つが合致することで、エンティティ4が実際に探索されているエンティティであると結論付けるのに十分であり得る。
【００８１】
エンティティ4が通信チャネル2を介して検証デバイス1に応答7を送る場合、この応答は、エンティティ4が、探索されているエンティティに自らが対応すると考えることを単に意味することが可能である。逆に、エンティティ3および5が、探索されているエンティティに自らが対応すると考えない場合、エンティティ3および5は、検証デバイス1に応答を送らない。すると、検証デバイス1は、エンティティ4が実際に、検証デバイス1が探索しているエンティティであると結論付けることができる。
【００８２】
符号化関数は、確率論的であり、決定論的ではないので、いくつかのエンティティが、自らを探索されているエンティティであると考えることが可能である。この場合、検証デバイス1は、通信チャネル2を介して、いくつかのエンティティから、検証デバイス1の要求6に対するいくつかの応答7を受信することが可能である。その場合、有利には、探索されているエンティティを識別するために探索をより細かくすることが可能である。例として、(i,mi)とは異なるペア(j,mj)を選択して、送信することで、エンティティ3〜5に再び問い合わせることが可能である。有利には、送信されるペア(j,mj)は、応答7を送ったエンティティの間の新たな曖昧さを回避するように、つまり、これらのエンティティのうち1つだけが、探索されているエンティティに自らが対応すると考えるように選択される。
【００８３】
図2に示される例において、通信チャネル2を介してエンティティ4によって送られる応答7は、要求6と同一の原理に基づく情報を含む。
【００８４】
この目的で、mに加えて、エンティティ4は、例えば、エンティティ4のメモリの中に格納することによって、第2の識別子M=(M1,M2,...,Mn)、または第2の識別子Mの代表M1、M2、...、Mnの一部またはすべてを、順序を考慮することなしに知っている。エンティティ4は、fcと異なることも、同一であることも可能な第2の符号化関数Fcをも有する。その場合、エンティティ4は、M、および代表M1、M2、...、Mnの少なくとも1つのうちでエンティティ4が知っている情報に第2の符号化関数Fcを適用することによって、第2の識別語を獲得することができる。
【００８５】
図2の例において、第2の符号化関数Fcは、fcと同一であり、第2の符号化関数Fcの可変のパラメータは、検証デバイス1によって選択された値と同一の値に、すなわち、iに固定される。このため、エンティティ4によって送られる応答7は、第2の識別語Miを含む。数iは、検証デバイス1が、第2の符号化関数Fcがfcと同一の、可変のパラメータの値を使用することを知らない場合、Miに加えて、任意で送信されることが可能である。
【００８６】
第2の識別子Mが実際、第1の識別子mと同一であることが可能である。この場合、応答7は、好ましくは、(i,mi)とは異なるペア(j,mj)を含む。
【００８７】
このように応答7の中にさらなる情報を含めることは、検証デバイス1が、IDのさらなる検証を実行することを許すことが可能である。このように機能することは、図2に関連して説明されるタイプの識別子に限定されず、使用される識別子フォーマットがいずれであれ、当てはまり得ることに留意されたい。
【００８８】
IDのそのようなさらなる検証を実行するために、検証デバイス1は、有利には、第2の符号化関数Fcに関連する第2の識別関数Fiを有する。エンティティ4と関係して説明されたとおり、検証デバイス1は、検証デバイス1において受信された識別語
【００８９】
【数９】
【００９０】
に第2の識別関数Fiを適用し、さらにエンティティ4の識別子M、および識別子Mの代表M1、M2、...、Mnの少なくとも1つのうちから、検証デバイス1によって知られている情報に第2の識別関数Fiを適用する。
【００９１】
このさらなる検証は、エンティティ4が探索されているエンティティであることを確認すること、または逆に否定することを可能にする。このオプションは、このオプションが、本発明の確率論的モデルにおいて生じる可能性がある識別の誤りを限定するため、有用である。
【００９２】
序論で述べた従来技術の方法と比較して、以上に説明された実施例は、本発明が、エンティティのIDの保護を向上させるエンティティの探索を可能にすることができることを理解することを許す。
【００９３】
通信チャネル2をリッスンしており、エンティティの識別子、および識別子の代表の知識をアプリオリに有さない攻撃者は、一般に、送信された代表miおよびMiからエンティティ4の識別子mを見出すことができない。
【００９４】
通信チャネル2をリッスンしている攻撃者の作業は、実施される符号化が確率論的であり、決定論的ではないことにより、符号化が少なくとも1つの可変のパラメータに依存するので、特に困難にされる。このことから、異なる識別語が、単一のエンティティを識別することを許すことが可能である。
【００９５】
さらに、可能な識別語の総数は、識別子の総数よりはるかに多い。したがって、攻撃者が、限られた時間にわたって通信チャネル2をリッスンすることで、所与のエンティティと関係するすべての識別語を見出すことは、ほぼ不可能である。
【００９６】
さらに、攻撃者が、いくつかのエンティティの識別子、および/またはそれらの識別子の代表を知ることができるとした場合でも、攻撃者は、特に、符号化関数が、異なる複数の識別子に適用された場合に、単一の識別語をもたらす可能性がある場合に、応答を送ったエンティティのIDについて確実に結論付けることは必ずしもできない。
【００９７】
このようにして、本発明は、個人の私生活の尊重を向上させること、およびデバイスの追跡可能性をより困難にする。
【００９８】
本発明の別の利点は、本発明の効率にある。図2に関連して説明される例において、識別子mを構成する各代表m1、m2、...、mnが1バイト、すなわち、8ビットであると想定した場合、探索は、おおよそで1バイトの送信(ステップ6におけるm1の送信)だけしか要求しないことが可能である。これと比較して、従来技術の場合のような、検証デバイスによる識別子m=(m1,m2,...,mn)の全部の送信は、nバイトを必要とする。
【００９９】
前述した利点は、当業者には明白となるように、図2に関連して説明される実施例に限定されない。
【０１００】
図3は、本発明の別の実施例を示す。この実施例において、エンティティ3〜5のそれぞれは、それぞれの多項式の形態で識別子を有する。そのような識別子から獲得されることが可能な代表は、例えば、異なるポイントにおける、この多項式の評価、またはこの多項式の係数である。
【０１０１】
例えば、エンティティ4と関係する識別子は、多項式p(x)であることが可能であり、対応する代表は、nが整数である所定のポイントx1、x2、...、xnのセットにおける、この多項式の評価、すなわち、p(x1)、p(x2)、...、p(xn)であることが可能である。
【０１０２】
この場合に検証デバイス1によって使用される符号化関数fcは、例えば、これらの評価のうち1つ、例えば、p(xi)をランダムに選択することにあることが可能である。この識別語p(xi)は、ステップ8で、検証デバイス1から通信チャネル2を介して送信される。
【０１０３】
対応する識別語を受信すると、通信チャネル2をリッスンしているエンティティ3〜5のそれぞれは、合致の可能性を判定するために、その識別語を、そのエンティティが、例えば、そのエンティティのメモリの中に有する評価の一部またはすべてと比較する。
【０１０４】
例えば、エンティティ4に関して合致した場合、エンティティ4が、通信チャネル2を介して検証デバイス1に応答9を送る。この応答は、例えば、x1、x2、...、xnとは異なるポイントXiに多項式pを適用することによって獲得された評価p(Xi)を含むことが可能である。代替として、応答9は、Pがpとは異なる多項式である評価P(xi)を含むことも可能である。別の代替として、応答9は、jがiとは異なる評価p(xj)を含むことも可能である。
【０１０５】
図4は、各エンティティが、例えば、1,000から10,000までの間の或る数を識別子として有し、さらにこの識別子から獲得され得る代表が、固定長、例えば、20,000であるとともに、対応する識別子と等しい重みが付けられた二値ベクトルである、別の実施例を示す。このため、Nが1,000から10,000までの間にある識別子Nから獲得され得るすべての代表m1、m2、...、mnは、例えば、Nと等しい数の1と、20,000-Nと等しい数の0とを有し、これらの代表は、0および1の位置によって互いに異なる。これらの数値は、単に例として与えられており、主題の一般性を限定するものではないことが理解されよう。
【０１０６】
識別子Nのエンティティ4を探索する検証デバイス1は、例えば、識別子Nの代表mi、すなわち、Nビットが1であり、20,000-Nビットが0である二値ベクトルをランダムに選択する。次に、検証デバイス1は、ステップ10で、代表miを識別語として通信チャネル2を介して送信する。
【０１０７】
エンティティ4は、エンティティ4の識別子Nを、例えば、エンティティ4が、識別子Nをエンティティ4のメモリの中に格納しているため、知っている。送信された代表miに対応する、長さ20,000の識別語を受信すると、エンティティ4は、この識別語の重み、つまり、この識別語の1の数を計算し、その数をNと比較する。このことには、受信された識別語、およびエンティティ4の識別子Nに識別関数が適用されることがかかわる。
【０１０８】
等しい場合、エンティティ4は、エンティティ4が、探索されているエンティティであると考え、通信チャネル2を介して検証デバイス1に応答11を送る。この応答は、検証デバイス1によってそのように解釈されることが可能である。この例では、応答11は、他の有用な情報は含まない。
【０１０９】
図2から図4を参照して説明される例は、限定的ではないことが当業者には理解されよう。前述した本発明の一般的な原理により、他の多数の可能性が想定されることが可能である。詳細には、説明されたのとは異なる符号化関数および/または識別関数が使用されることが可能である。
【０１１０】
様々な図を参照して説明される動作の一部またはすべては、部分的に、または完全にソフトウェアで実施される、つまり、その目的に適合されたコード命令を備えるコンピュータプログラム製品を使用して実施されることが可能であることに留意されたい。代替として、またはさらに、これらのステップの少なくともいくつかは、電子回路を使用して実施されることが可能である。
【符号の説明】
【０１１１】
1 検証デバイス
2 通信チャネル
3、4、5 エンティティ
6 要求
7、9、11 応答
【特許請求の範囲】
【請求項１】
検証デバイス(1)を使用してエンティティのセットに属するエンティティを探索するための方法であって、
前記検証デバイスとエンティティの前記セットからの前記エンティティは、少なくとも1つの通信チャネル(2)を介して情報のアイテムを交換するように構成され、エンティティの前記セットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能であり、
前記検証デバイスにおいて、探索が実行されているエンティティ(4)と関係する第1の識別語(mi;p(xi))を獲得し、前記第1の識別語は、探索が実行されている前記エンティティの前記第1の識別子に、前記第1の識別子から獲得され得る複数の代表の下位部分に依存するように第1の符号化関数を適用することによって形成され、前記下位部分は、少なくとも1つの可変のパラメータ(i)によって決定されるステップと、
前記検証デバイスから、前記通信チャネルを介して獲得された前記第1の識別語を送信するステップとを備える方法。
【請求項２】
前記通信チャネル(2)をリッスンしているエンティティの前記セットからの各エンティティ(3〜5)によって実行される、
前記通信チャネルを介して送信された前記第1の識別語(mi;p(xi))に対応する識別語を受信するステップと、
前記受信された識別語に前記第1の符号化関数に関連する第1の識別関数を適用し、さらに前記エンティティの前記第1の識別子と、前記第1の識別子から獲得され得る前記複数の代表の少なくとも1つの代表のうちから、前記エンティティによって知られている情報に前記第1の符号化関数に関連する第1の識別関数を適用して、前記エンティティが前記探索されているエンティティ(4)に対応するかどうかを検証するようにするステップとをさらに備える請求項1に記載の方法。
【請求項３】
獲得された前記第1の識別語(mi)を形成するのに使用された前記可変のパラメータ(i)の値の通知が、前記検証デバイス(1)から前記通信チャネル(2)を介して送信され、さらに前記通信チャネルをリッスンしているエンティティの前記セットからの各エンティティ(3〜5)に関して、前記第1の識別関数の前記適用は、受信された可変のパラメータの値の前記通知を考慮に入れる請求項2に記載の方法。
【請求項４】
前記第1の識別関数の前記適用の結果が、前記エンティティ(3〜5)が前記探索されているエンティティ(4)に対応することを明らかにした場合、前記エンティティは、前記通信チャネル(2)を介して検証デバイス(1)に応答(7;9;11)を送る請求項2または3に記載の方法。
【請求項５】
前記エンティティ(3〜5)は、第2の識別子を有し、第2の識別子からは、複数の代表が獲得されることが可能であり、第2の識別語(Mi;p(Xi))が、前記エンティティにおいて、前記エンティティの前記第2の識別子と、前記第2の識別子から獲得され得る前記複数の代表の少なくとも1つの代表のうちから、前記エンティティによって知られている情報に、第2の符号化関数を適用して、前記第2の識別子から獲得され得る前記複数の代表の下位部分に依存するようにすることによって獲得され、前記下位部分は、少なくとも1つの可変のパラメータ(i)によって決定され、さらに前記エンティティによって前記通信チャネル(2)を介して前記検証デバイス(1)に送られる前記応答(7;9;11)は、前記第2の識別語を含む請求項4に記載の方法。
【請求項６】
前記応答(7;9;11)に含まれる前記第2の識別語(Mi;p(Xi))に対応する識別語が、前記検証デバイス(1)において受信され、さらに前記検証デバイスは、前記検証デバイスにおいて受信された前記識別語に前記第2の符号化関数に関連する第2の識別関数を適用し、さらに前記エンティティ(3〜5)の前記第2の識別子と、前記第2の識別子から獲得され得る前記複数の代表の少なくとも1つの代表のうちから、前記検証デバイスによって知られている情報に前記第2の符号化関数に関連する第2の識別関数を適用して、前記エンティティと、前記探索されているエンティティの対応のさらなる検証をもたらすようにする請求項5に記載の方法。
【請求項７】
前記第1の符号化関数は、前記第1の符号化関数が、前記探索されているエンティティ(4)の前記第1の識別子に適用されると、前記可変のパラメータ(i)が、前記第1の識別子から獲得され得る前記複数の代表のうち少なくとも1つの代表(mi)を選択するようになるように構成され、さらに前記第1の識別関数の前記適用は、前記可変のパラメータによって選択される前記代表と、前記エンティティの前記第1の識別子から獲得され得る前記複数の代表のうち少なくとも1つの代表の比較を備える請求項2から6のいずれか一項に記載の方法。
【請求項８】
獲得される前記第1の識別語(mi)を形成するのに使用される前記可変のパラメータ(i)の値は、ランダムに、または準ランダムに選択される請求項1から7のいずれか一項に記載の方法。
【請求項９】
獲得される前記第1の識別語(mi)は、前記検証デバイス(1)から前記通信チャネル(2)を介して、誤り訂正符号を使用して符号化されて送信される請求項1から8のいずれか一項に記載の方法。
【請求項１０】
前記通信チャネル(2)は、無線チャネルなどのワイヤレスチャネルであり、さらに前記検証デバイス(1)は、ワイヤレスID読み取り装置を備え、エンティティ(3〜5)の前記セットからの前記エンティティの少なくともいくつかは、ワイヤレスIDタグを備える請求項1から9のいずれか一項に記載の方法。
【請求項１１】
識別子から獲得され得る前記複数の代表を獲得する能力は、エンティティの前記セットからの、前記識別子を有する前記エンティティ(3〜5)、および前記検証デバイス(1)だけにしか付与されない請求項1から10のいずれか一項に記載の方法。
【請求項１２】
前記第1の符号化関数は、単一の第1の識別語が、可能なすべての識別子のセットからの異なる複数の識別子に前記第1の符号化関数を適用した結果であることが可能であるように構成される請求項1から11のいずれか一項に記載の方法。
【請求項１３】
少なくとも1つの通信チャネル(2)を介してエンティティのセットと情報のアイテムを交換するように構成された検証デバイス(1)であって、
エンティティの前記セットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能であり、
探索が実行されているエンティティ(4)の前記第1の識別子に第1の符号化関数を適用して、少なくとも1つの可変のパラメータ(i)によって決定される、前記第1の識別子から獲得され得る前記複数の代表の下位部分に依存するようにすることによって形成される、前記探索が実行されるエンティティと関係する第1の識別語(mi;p(xi))を獲得するユニットと、
前記獲得するユニットによって獲得された前記第1の識別語を、前記通信チャネルを介して送信するユニットとを備える検証デバイス(1)。
【請求項１４】
少なくとも1つの通信チャネル(2)を介して検証デバイス(1)と情報のアイテムを交換することができるとともに、それぞれの第1の識別子をそれぞれが有し、第1の識別子からは、複数の代表が獲得され得る、エンティティのセットに属するエンティティ(3〜5)であって、
前記検証デバイスによって前記通信チャネルを介して送信された第1の識別語(mi;p(xi))に対応する識別語を受信し、前記第1の識別語は、探索が実行されているエンティティ(4)の前記第1の識別子に第1の符号化関数を適用して、少なくとも1つの可変のパラメータ(i)によって決定される、前記第1の識別子から獲得され得る前記複数の代表の下位部分に依存するようにすることによって形成されるユニットと、
前記受信された識別語に前記第1の符号化関数に関連する第1の識別関数を適用し、さらに前記エンティティの前記第1の識別子と、前記第1の識別子から獲得され得る前記複数の代表の少なくとも1つの代表のうちから、前記エンティティによって知られている情報に前記第1の符号化関数に関連する第1の識別関数を適用して、前記エンティティが前記探索されているエンティティに対応するかどうかを検証するようにするユニットとを備えるエンティティ(3〜5)。
【請求項１５】
検証デバイス(1)を使用してエンティティのセットに属するエンティティ(4)を探索するためのシステムであって、
請求項1から12のいずれか一項に記載の方法を実行するために適合された手段を備えるシステム。
【請求項１】
検証デバイス(1)を使用してエンティティのセットに属するエンティティを探索するための方法であって、
前記検証デバイスとエンティティの前記セットからの前記エンティティは、少なくとも1つの通信チャネル(2)を介して情報のアイテムを交換するように構成され、エンティティの前記セットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能であり、
前記検証デバイスにおいて、探索が実行されているエンティティ(4)と関係する第1の識別語(mi;p(xi))を獲得し、前記第1の識別語は、探索が実行されている前記エンティティの前記第1の識別子に、前記第1の識別子から獲得され得る複数の代表の下位部分に依存するように第1の符号化関数を適用することによって形成され、前記下位部分は、少なくとも1つの可変のパラメータ(i)によって決定されるステップと、
前記検証デバイスから、前記通信チャネルを介して獲得された前記第1の識別語を送信するステップとを備える方法。
【請求項２】
前記通信チャネル(2)をリッスンしているエンティティの前記セットからの各エンティティ(3〜5)によって実行される、
前記通信チャネルを介して送信された前記第1の識別語(mi;p(xi))に対応する識別語を受信するステップと、
前記受信された識別語に前記第1の符号化関数に関連する第1の識別関数を適用し、さらに前記エンティティの前記第1の識別子と、前記第1の識別子から獲得され得る前記複数の代表の少なくとも1つの代表のうちから、前記エンティティによって知られている情報に前記第1の符号化関数に関連する第1の識別関数を適用して、前記エンティティが前記探索されているエンティティ(4)に対応するかどうかを検証するようにするステップとをさらに備える請求項1に記載の方法。
【請求項３】
獲得された前記第1の識別語(mi)を形成するのに使用された前記可変のパラメータ(i)の値の通知が、前記検証デバイス(1)から前記通信チャネル(2)を介して送信され、さらに前記通信チャネルをリッスンしているエンティティの前記セットからの各エンティティ(3〜5)に関して、前記第1の識別関数の前記適用は、受信された可変のパラメータの値の前記通知を考慮に入れる請求項2に記載の方法。
【請求項４】
前記第1の識別関数の前記適用の結果が、前記エンティティ(3〜5)が前記探索されているエンティティ(4)に対応することを明らかにした場合、前記エンティティは、前記通信チャネル(2)を介して検証デバイス(1)に応答(7;9;11)を送る請求項2または3に記載の方法。
【請求項５】
前記エンティティ(3〜5)は、第2の識別子を有し、第2の識別子からは、複数の代表が獲得されることが可能であり、第2の識別語(Mi;p(Xi))が、前記エンティティにおいて、前記エンティティの前記第2の識別子と、前記第2の識別子から獲得され得る前記複数の代表の少なくとも1つの代表のうちから、前記エンティティによって知られている情報に、第2の符号化関数を適用して、前記第2の識別子から獲得され得る前記複数の代表の下位部分に依存するようにすることによって獲得され、前記下位部分は、少なくとも1つの可変のパラメータ(i)によって決定され、さらに前記エンティティによって前記通信チャネル(2)を介して前記検証デバイス(1)に送られる前記応答(7;9;11)は、前記第2の識別語を含む請求項4に記載の方法。
【請求項６】
前記応答(7;9;11)に含まれる前記第2の識別語(Mi;p(Xi))に対応する識別語が、前記検証デバイス(1)において受信され、さらに前記検証デバイスは、前記検証デバイスにおいて受信された前記識別語に前記第2の符号化関数に関連する第2の識別関数を適用し、さらに前記エンティティ(3〜5)の前記第2の識別子と、前記第2の識別子から獲得され得る前記複数の代表の少なくとも1つの代表のうちから、前記検証デバイスによって知られている情報に前記第2の符号化関数に関連する第2の識別関数を適用して、前記エンティティと、前記探索されているエンティティの対応のさらなる検証をもたらすようにする請求項5に記載の方法。
【請求項７】
前記第1の符号化関数は、前記第1の符号化関数が、前記探索されているエンティティ(4)の前記第1の識別子に適用されると、前記可変のパラメータ(i)が、前記第1の識別子から獲得され得る前記複数の代表のうち少なくとも1つの代表(mi)を選択するようになるように構成され、さらに前記第1の識別関数の前記適用は、前記可変のパラメータによって選択される前記代表と、前記エンティティの前記第1の識別子から獲得され得る前記複数の代表のうち少なくとも1つの代表の比較を備える請求項2から6のいずれか一項に記載の方法。
【請求項８】
獲得される前記第1の識別語(mi)を形成するのに使用される前記可変のパラメータ(i)の値は、ランダムに、または準ランダムに選択される請求項1から7のいずれか一項に記載の方法。
【請求項９】
獲得される前記第1の識別語(mi)は、前記検証デバイス(1)から前記通信チャネル(2)を介して、誤り訂正符号を使用して符号化されて送信される請求項1から8のいずれか一項に記載の方法。
【請求項１０】
前記通信チャネル(2)は、無線チャネルなどのワイヤレスチャネルであり、さらに前記検証デバイス(1)は、ワイヤレスID読み取り装置を備え、エンティティ(3〜5)の前記セットからの前記エンティティの少なくともいくつかは、ワイヤレスIDタグを備える請求項1から9のいずれか一項に記載の方法。
【請求項１１】
識別子から獲得され得る前記複数の代表を獲得する能力は、エンティティの前記セットからの、前記識別子を有する前記エンティティ(3〜5)、および前記検証デバイス(1)だけにしか付与されない請求項1から10のいずれか一項に記載の方法。
【請求項１２】
前記第1の符号化関数は、単一の第1の識別語が、可能なすべての識別子のセットからの異なる複数の識別子に前記第1の符号化関数を適用した結果であることが可能であるように構成される請求項1から11のいずれか一項に記載の方法。
【請求項１３】
少なくとも1つの通信チャネル(2)を介してエンティティのセットと情報のアイテムを交換するように構成された検証デバイス(1)であって、
エンティティの前記セットからの各エンティティは、それぞれの第1の識別子を有し、第1の識別子からは、複数の代表が獲得されることが可能であり、
探索が実行されているエンティティ(4)の前記第1の識別子に第1の符号化関数を適用して、少なくとも1つの可変のパラメータ(i)によって決定される、前記第1の識別子から獲得され得る前記複数の代表の下位部分に依存するようにすることによって形成される、前記探索が実行されるエンティティと関係する第1の識別語(mi;p(xi))を獲得するユニットと、
前記獲得するユニットによって獲得された前記第1の識別語を、前記通信チャネルを介して送信するユニットとを備える検証デバイス(1)。
【請求項１４】
少なくとも1つの通信チャネル(2)を介して検証デバイス(1)と情報のアイテムを交換することができるとともに、それぞれの第1の識別子をそれぞれが有し、第1の識別子からは、複数の代表が獲得され得る、エンティティのセットに属するエンティティ(3〜5)であって、
前記検証デバイスによって前記通信チャネルを介して送信された第1の識別語(mi;p(xi))に対応する識別語を受信し、前記第1の識別語は、探索が実行されているエンティティ(4)の前記第1の識別子に第1の符号化関数を適用して、少なくとも1つの可変のパラメータ(i)によって決定される、前記第1の識別子から獲得され得る前記複数の代表の下位部分に依存するようにすることによって形成されるユニットと、
前記受信された識別語に前記第1の符号化関数に関連する第1の識別関数を適用し、さらに前記エンティティの前記第1の識別子と、前記第1の識別子から獲得され得る前記複数の代表の少なくとも1つの代表のうちから、前記エンティティによって知られている情報に前記第1の符号化関数に関連する第1の識別関数を適用して、前記エンティティが前記探索されているエンティティに対応するかどうかを検証するようにするユニットとを備えるエンティティ(3〜5)。
【請求項１５】
検証デバイス(1)を使用してエンティティのセットに属するエンティティ(4)を探索するためのシステムであって、
請求項1から12のいずれか一項に記載の方法を実行するために適合された手段を備えるシステム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公表番号】特表２０１３−５０１２８６（Ｐ２０１３−５０１２８６Ａ）
【公表日】平成２５年１月１０日（２０１３．１．１０）
【国際特許分類】
【出願番号】特願２０１２−５２３３６４（Ｐ２０１２−５２３３６４）
【出願日】平成２２年７月２８日（２０１０．７．２８）
【国際出願番号】ＰＣＴ／ＦＲ２０１０／０５１５９４
【国際公開番号】ＷＯ２０１１／０１５７６８
【国際公開日】平成２３年２月１０日（２０１１．２．１０）
【出願人】（５０８２５６６７３）
【Ｆターム（参考）】
【公表日】平成２５年１月１０日（２０１３．１．１０）
【国際特許分類】
【出願日】平成２２年７月２８日（２０１０．７．２８）
【国際出願番号】ＰＣＴ／ＦＲ２０１０／０５１５９４
【国際公開番号】ＷＯ２０１１／０１５７６８
【国際公開日】平成２３年２月１０日（２０１１．２．１０）
【出願人】（５０８２５６６７３）
【Ｆターム（参考）】
[ Back to top ]