(57)【要約】【課題】リーダを介してアクセスされるタグの非追跡可能性を、従来に比べて少ない処理量で達成できる通信方法を提供する。【解決手段】管理装置７は、ＳＴ８の式を満たすｋ’を、テーブルデータＴＤの項目Ｋ，Ｋｌａｓｔの中から検索し、検索したエントリのＩＤを特定する。管理装置７は、上記検索で所定の値ｋ’が、項目Ｋのなかから検索された場合には、そのエントリの項目Ｋの値を、そのエントリの項目Ｋｌａｓｔにコピーする。また、ｋ’のハッシュ値を項目Ｋに設定する。【選択図】図４
2007189643.tif 000002
【特許請求の範囲】
【請求項１】
タグ、リーダおよび管理装置の間で行われる通信方法であって、
前記リーダが、乱数ｓを前記タグに送信する第１の工程と、
前記タグが、第１の秘密データｒｉと第２の秘密データｋｊとを引数として得たハッシュ値を第１の秘密データｒｉ＋１として前記リーダを介して前記管理装置に送信する第２の工程と、
前記タグが、前記第１の工程で受信した前記乱数ｓと、前記第２の工程で生成した前記第１の秘密データｒｉ＋１とを基に、第１の秘密データｒｉ＋２を生成し、これを前記リーダを介して管理装置に送信する第３の工程と、
前記リーダが、乱数ｓと、前記第３の工程で受信した前記第１の秘密データｒｉ＋２とを、前記管理装置に送信する第４の工程と、
前記管理装置が、前記第２の工程で受信した前記第１の秘密データｒｉ＋１と、前記第４の工程で受信した乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定する第５の工程と、
前記管理装置が、複数のタグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを参照して、前記第５の工程で特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索する第６の工程と、
前記管理装置が、所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する第７の工程と
有する通信方法。
【請求項２】
前記管理装置が、前記第３の工程で受信した前記第１の秘密データｒｉ＋２と、前記第５の工程で特定した前記所定の値ｋ’とを基に第１ハッシュ値ｒ’ｉ＋３を生成し、これを前記タグに送信する第８の工程と、
前記タグが、前記第３の工程で生成した前記第１の秘密データｒｉ＋２と、前記第２の秘密データｋｊとを基に、第２のハッシュ値ｒｉ＋３を生成し、当該第２のハッシュ値ｒｉ＋３と、前記第８の工程で受信した前記第１ハッシュ値ｒ’ｉ＋３とが一致したことを条件に、前記第２の秘密データｋｊのハッシュ値を、更新後の第２の秘密データｋｊ＋１として設定する第９の工程と
をさらに有する請求項１に記載の通信方法。
【請求項３】
タグ、リーダおよび管理装置を有する通信システムであって、
前記リーダが、乱数ｓを前記タグに送信し、
前記タグが、第１の秘密データｒｉと第２の秘密データｋｊとを引数として得たハッシュ値を第１の秘密データｒｉ＋１として前記リーダを介して前記管理装置に送信し、
前記タグが、前記受信した前記乱数ｓと、前記生成した前記第１の秘密データｒｉ＋１とを基に、第１の秘密データｒｉ＋２を生成し、これを前記リーダを介して管理装置に送信し、
前記リーダが、乱数ｓと、前記受信した前記第１の秘密データｒｉ＋２とを、前記管理装置に送信し、
前記管理装置が、前記受信した前記第１の秘密データｒｉ＋１と、前記受信した乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定し、
前記管理装置が、複数のタグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを参照して、前記特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索し、
前記管理装置が、所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する
通信システム。
【請求項４】
リーダを介してタグと通信を行う通信装置が実行する通信方法であって、
第１の秘密データｒｉと第２の秘密データｋｊとを引数として前記タグが生成したハッシュ値である第１の秘密データｒｉ＋１を前記タグから前記リーダを介して受信する第１の工程と、
前記タグが前記リーダから受信した乱数ｓと前記第１の秘密データｒｉ＋１とを基に生成した第１の秘密データｒｉ＋２を前記タグから前記リーダを介して受信する第２の工程と、
前記乱数ｓと前記第１の秘密データｒｉ＋２とを前記リーダから受信する第３の工程と、
前記第１の工程で受信した前記第１の秘密データｒｉ＋１と、前記第３の工程で受信した乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定する第４の工程と、
複数の前記タグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを参照して、前記第４の工程で特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索する第５の工程と、
前記所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する第６の工程と
を有する通信方法。
【請求項５】
リーダを介してタグと通信を行う通信装置であって、
第１の秘密データｒｉと第２の秘密データｋｊとを引数として前記タグが生成したハッシュ値である第１の秘密データｒｉ＋１を前記タグから前記リーダを介して受信し、前記タグが前記リーダから受信した乱数ｓと前記第１の秘密データｒｉ＋１とを基に生成した第１の秘密データｒｉ＋２を前記タグから前記リーダを介して受信し、前記乱数ｓと前記第１の秘密データｒｉ＋２とを前記リーダから受信するインターフェースと、
複数の前記タグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを記憶するメモリと、
前記インターフェースが受信した前記第１の秘密データｒｉ＋１と、乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定し、前記テーブルデータを参照して、前記特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索し、前記所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する処理回路と
を有する通信装置。
【請求項６】
リーダを介してタグと通信を行う通信装置が実行するプログラムであって、
第１の秘密データｒｉと第２の秘密データｋｊとを引数として前記タグが生成したハッシュ値である第１の秘密データｒｉ＋１を前記タグから前記リーダを介して受信する第１の手順と、
前記タグが前記リーダから受信した乱数ｓと前記第１の秘密データｒｉ＋１とを基に生成した第１の秘密データｒｉ＋２を前記タグから前記リーダを介して受信する第２の手順と、
前記乱数ｓと前記第１の秘密データｒｉ＋２とを前記リーダから受信する第３の手順と、
前記第１の手順で受信した前記第１の秘密データｒｉ＋１と、前記第３の手順で受信した乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定する第４の手順と、
複数の前記タグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを参照して、前記第４の手順で特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索する第５の手順と、
前記所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する第６の手順と
を前記通信装置に実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リーダを介してタグと管理装置との間の通信を、タグと管理装置との間でセキュアに行う通信方法、通信システム、通信装置およびプログラムに関する。
【背景技術】
【０００２】
例えば、ＲＦＩＤ(Radio Frequency Identification)は、マイクロチップ内に識別情報を格納させ、それを無線周波数で検出して、管理したオブジェクトに関する情報を自動的に検出するために用いられる。
ＲＦＩＤ技術は、物理的あるいは視覚的なコンタクトをとることなく、無線周波数により多数のタグを瞬時に識別きるため、光学式バーコードよりも便利である。ＲＦＩＤシステムは、自動化分野の多くに用いることができ、ユビキタスコンピュータ環境に有用である。
しかしながら、ＲＦＩＤ技術は、便利であるという反面、セキュリティに関しての問題もある。例えば、ＲＦＩＤがその情報を知りたい相手に発信するために、会社や個人の情報が漏れてしまうという問題がある。
例えば、あるユーザが持つタグがＡ地点でリーダ（リーダライタ）に反応して検出され、その後にＢ地点で検出されたとすると、当該ユーザがＡ地点からＢ地点に移動したことが攻撃者（盗聴者）に知られてしまい、当該ユーザのプライバシが侵害されてしまう。また、タグ内の秘密情報が漏れた場合でも、当該タグが関係した処理を追跡できないようにする必要がある。
このような問題を解決するために、タグとリーダとの通信を追跡できない、追跡不可能性を持つシステムが提案されている。当該システムは、攻撃者が物理的にタグを攻撃（タンパー）してメモリの秘密情報を入手したとしても、過去の多数のタグとリーダとの通信のなかで、このタグが関与したものを特定できない、Forward Securityの性質を持つ。これらの性質を持つシステムとして、下記非特許文献１に開示されたものがある。
【非特許文献１】Miyako Ohkubo, Koutarou Suzuki, and Shingo Kinoshita. “Cryptographic approach to privacy-friendly' tag.” In RFID Privacy Workshop, MIT, MA, USA, November 2003.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記非特許文献１のシステムでは、システム中のタグの総数をｍ、各タグに許されるリーダとの間のインタラクションの最大回数をｎとして、１回のインタラクション毎にサーバがｍ＊ｎ回のハッシュ関数の演算を行う必要があり、処理負担が大きいという問題がある。
【０００４】
本発明は上述した従来技術に鑑みてなされたものであり、リーダを介してアクセスされるタグの非追跡可能性を、従来に比べて少ない処理量で達成できる通信方法、通信システム、通信装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
上述した従来技術の問題点を解決し、上述した目的を達成するため、第１の観点の発明の通信方法は、タグ、リーダおよび管理装置の間で行われる通信方法であって、前記リーダが、乱数ｓを前記タグに送信する第１の工程と、前記タグが、第１の秘密データｒｉと第２の秘密データｋｊとを引数として得たハッシュ値を第１の秘密データｒｉ＋１として前記リーダを介して前記管理装置に送信する第２の工程と、前記タグが、前記第１の工程で受信した前記乱数ｓと、前記第２の工程で生成した前記第１の秘密データｒｉ＋１とを基に、第１の秘密データｒｉ＋２を生成し、これを前記リーダを介して管理装置に送信する第３の工程と、前記リーダが、乱数ｓと、前記第３の工程で受信した前記第１の秘密データｒｉ＋２とを、前記管理装置に送信する第４の工程と、前記管理装置が、前記第２の工程で受信した前記第１の秘密データｒｉ＋１と、前記第４の工程で受信した乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定する第５の工程と、前記管理装置が、複数のタグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを参照して、前記第５の工程で特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索する第６の工程と、前記管理装置が、所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する第７の工程と有する。
【０００６】
第２の観点の発明の通信システムは、タグ、リーダおよび管理装置を有する通信システムであって、前記リーダが、乱数ｓを前記タグに送信し、前記タグが、第１の秘密データｒｉと第２の秘密データｋｊとを引数として得たハッシュ値を第１の秘密データｒｉ＋１として前記リーダを介して前記管理装置に送信し、前記タグが、前記受信した前記乱数ｓと、前記生成した前記第１の秘密データｒｉ＋１とを基に、第１の秘密データｒｉ＋２を生成し、これを前記リーダを介して管理装置に送信し、前記リーダが、乱数ｓと、前記受信した前記第１の秘密データｒｉ＋２とを、前記管理装置に送信し、前記管理装置が、前記受信した前記第１の秘密データｒｉ＋１と、前記受信した乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定し、前記管理装置が、複数のタグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを参照して、前記特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索し、前記管理装置が、所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する。
【０００７】
第３の観点の発明の通信方法は、リーダを介してタグと通信を行う通信装置が実行する通信方法であって、第１の秘密データｒｉと第２の秘密データｋｊとを引数として前記タグが生成したハッシュ値である第１の秘密データｒｉ＋１を前記タグから前記リーダを介して受信する第１の工程と、前記タグが前記リーダから受信した乱数ｓと前記第１の秘密データｒｉ＋１とを基に生成した第１の秘密データｒｉ＋２を前記タグから前記リーダを介して受信する第２の工程と、前記乱数ｓと前記第１の秘密データｒｉ＋２とを前記リーダから受信する第３の工程と、前記第１の工程で受信した前記第１の秘密データｒｉ＋１と、前記第３の工程で受信した乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定する第４の工程と、複数の前記タグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを参照して、前記第４の工程で特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索する第５の工程と、前記所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する第６の工程とを有する。
【０００８】
第４の観点の発明の通信装置は、リーダを介してタグと通信を行う通信装置であって、第１の秘密データｒｉと第２の秘密データｋｊとを引数として前記タグが生成したハッシュ値である第１の秘密データｒｉ＋１を前記タグから前記リーダを介して受信し、前記タグが前記リーダから受信した乱数ｓと前記第１の秘密データｒｉ＋１とを基に生成した第１の秘密データｒｉ＋２を前記タグから前記リーダを介して受信し、前記乱数ｓと前記第１の秘密データｒｉ＋２とを前記リーダから受信するインターフェースと、複数の前記タグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを記憶するメモリと、前記インターフェースが受信した前記第１の秘密データｒｉ＋１と、乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定し、前記テーブルデータを参照して、前記特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索し、前記所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する処理回路とを有する。
【０００９】
第５の観点の発明のプログラムは、リーダを介してタグと通信を行う通信装置が実行するプログラムであって、第１の秘密データｒｉと第２の秘密データｋｊとを引数として前記タグが生成したハッシュ値である第１の秘密データｒｉ＋１を前記タグから前記リーダを介して受信する第１の手順と、前記タグが前記リーダから受信した乱数ｓと前記第１の秘密データｒｉ＋１とを基に生成した第１の秘密データｒｉ＋２を前記タグから前記リーダを介して受信する第２の手順と、前記乱数ｓと前記第１の秘密データｒｉ＋２とを前記リーダから受信する第３の手順と、前記第１の手順で受信した前記第１の秘密データｒｉ＋１と、前記第３の手順で受信した乱数ｓと、所定の値ｋ’とを基にして得たハッシュ値が、前記第１の秘密データｒｉ＋２となる前記所定の値ｋ’を特定する第４の手順と、複数の前記タグの識別データについて当該識別データと第１の値Ｋと第２の値Ｋｌａｓｔとを対応付けて示すテーブルデータを参照して、前記第４の手順で特定した所定の値ｋ’と前記第１の値Ｋあるいは前記第２の値Ｋｌａｓｔが一致するエントリを検索する第５の手順と、前記所定の値ｋ’と前記第１の値Ｋとが一致するエントリが前記テーブルデータ内に存在した場合に、前記第１の値Ｋを第２の値Ｋｌａｓｔにコピーし、前記所定の値ｋ’のハッシュ値を前記第１の値Ｋに設定する第６の手順とを前記通信装置に実行させる。
【発明の効果】
【００１０】
本発明によれば、リーダを介してアクセスされるタグの非追跡可能性を、従来に比べて少ない処理量で達成できる通信方法、通信システム、通信装置およびプログラムを提供することができる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明の実施形態に係わる通信システムについて説明する。
〔本発明の構成との対応関係〕
先ず、本実施形態の構成要素と、本発明の構成要素との対応関係を説明する。
ＲＦタグ３が本発明のタグの一例であり、タグリーダ５が本発明のリーダの一例であり、管理装置７が本発明の管理装置および通信装置の一例である。
また、管理装置７が実行するプログラムＰＲＧ３が本発明のプログラムの一例である。
また、図３に示すテーブルデータＴＤが本発明のテーブルデータの一例である。
【００１２】
図１は、本発明の実施形態に係わる通信システム１の全体構成図である。
図１に示すように、通信システム１は、例えば、ＲＦタグ３、タグリーダ５および管理装置７を有する。
【００１３】
図１に示す通信システム１において、ＲＦタグ３およびタグリーダ５は、実際には複数存在する。
ＲＦタグ３とタグリーダ５との間の通信は非セキュアであり、タグリーダ５と管理装置７との間の通信はセキュアである。
【００１４】
通信システム１は、ＲＦタグ３における演算量を小さいプロトコルを採用する。このプロトコルは、従来から提案されている様々なプロトコルで採用さているハッシュ関数に加えて、ＲＦタグ３と管理装置７とで共用される２つの秘密データを用いる。また、管理装置７において後述するテーブルデータＴＤを使用する。これにより、管理装置７における計算量を削減できる。このように２つの秘密データとテーブルデータＴＤを用いることにより、管理装置７における計算の複雑さを少なくできると共に、リーダが取得した情報を基にしたタグの追跡を不可能にする追跡不可能性(untraceability)を完全に達成でき、タグからの情報が適切なものであるかを判断でき、且つ、タグの秘密情報が漏れた場合でも、当該タグが関係した処理を特定不可能にできる(detect forgery)。
【００１５】
先ず、ＲＦタグ３、タグリーダ５および管理装置７の構成について説明する。
図２は、図１に示すＲＦタグ３およびタグリーダ５の構成図である。
［ＲＦタグ３］
図２に示すように、ＲＦタグ３は、例えば、ＲＦ回路１１、メモリ１３および処理回路１５を有する。
ＲＦ回路１１は、タグリーダ５のＲＦ回路２１と所定の無線周波数により無線通信を行うアンテナコイルを含む回路である。
ＲＦ回路１１は、ＲＦタグ３がバッテリーを持たない受動型である場合には、タグリーダ５からの電波を受信し、共振作用により、起電力を発生する。ＲＦタグ３の処理回路１５は、当該起電力により動作する。
本実施形態において、メモリ１３および処理回路１５は対タンパ性の回路である。
【００１６】
メモリ１３は、例えば、処理回路１５の処理を規定したプログラムＰＲＧ１、処理回路１５の処理に用いられる各種のデータを記憶する。 
メモリ１３としては、ＥＥＰＲＯＭやＦｅＲＡＭなどが用いられる。
【００１７】
処理回路１５は、メモリ１３から読み出したプログラムＰＲＧ１を実行し、タグリーダ５との間の通信処理、管理装置７との間の認証処理、並びに内部での秘密データｒ，ｋの更新処理等を行う。
【００１８】
［タグリーダ５］
図２に示すように、タグリーダ５は、例えば、ＲＦ回路２１、インタフェース２３、メモリ２５および処理回路２７を有する。
ＲＦ回路２１は、ＲＦタグ３のＲＦ回路１１と所定の無線周波数により無線通信を行う。
【００１９】
インタフェース２３は、セキュアなネットワークを介して管理装置７と通信を行う。
メモリ２５は、例えば、処理回路２７の処理を規定したプログラムＰＲＧ２、処理回路２７の処理に用いられる各種のデータを記憶する。
処理回路２７は、メモリ２５から読み出したプログラムＰＲＧ２を実行し、ＲＦタグ３および管理装置７の間の通信処理などを行う。
なお、処理回路２７は、乱数発生機能を有している。
本実施形態においては、タグリーダ５は、ＲＦタグ３からデータを読み出す機能の他、ＲＦタグ３にデータを書き込む機能も有している。
【００２０】
［管理装置７］
図３は、図１に示す管理装置７の構成図である。
図３に示すように、管理装置７は、例えば、インタフェース３１、メモリ３３および処理回路３５を有する。
インタフェース３１は、セキュアなネットワークを介してタグリーダ５と通信を行う。
メモリ３３は、例えば、処理回路３５の処理を規定したプログラムＰＲＧ３、処理回路３５の処理に用いられる各種のデータを記憶する。
処理回路３５は、メモリ３３から読み出したプログラムＰＲＧ３を実行し、ＲＦタグ３およびタグリーダ５との間の通信処理などを行う。
【００２１】
［全体動作例］
図４および図５は、図１に示す通信システム１の全体動作例を説明するためのフロー図である。
ステップＳＴ１：
図２に示すタグリーダ５の処理回路２７は、乱数ｓを発生する。
【００２２】
ステップＳＴ２：
処理回路２７は、ＲＦ回路２１を介してＲＦタグ３にステップＳＴ１で生成した乱数ｓを送信する。
【００２３】
ステップＳＴ３：
ＲＦタグ３の処理回路１５は、下記式（１）に示すように、メモリ１３から読み出した秘密データｒｉ，ｋｊを基にハッシュ値を生成し、これを秘密データｒｉ＋１に設定する。本実施形態において、「ＸＯＲ」は排他的論理和を示す。ｈ（）はハッシュ関数を示す。
本実施形態において、ＲＦタグ３の処理回路１５および管理装置７の処理回路３５がハッシュ値の生成に用いるハッシュ関数Ｈは、「Ｈ：｛０，１｝ｌ→｛０，１｝ｌ」で定義される。
【００２４】
［数１］
ｒｉ＋１←ｈ（ｒｉ  ＸＯＲ  ｋｊ）
…（１）
【００２５】
ステップＳＴ４：
ＲＦタグ３の処理回路１５は、ＲＦ回路１１を介して、ステップＳＴ３で生成した秘密データｒｉ＋１を、タグリーダ５に送信する。
タグリーダ５の処理回路２７は、ＲＦ回路２１で受信した秘密データｒｉ＋１を、インタフェース２３を介して管理装置７に送信する。
処理回路２７が用いる秘密データｒｘ，ｋｘ（ｘ＝ｉ，ｉ＋１，．．．）は、ｌビットのデータである。ここで、ｋｘは、ＲＦタグ３を識別するために用いられる複数のＲＦタグ３の各々において異なる値を示す。ｋｘの初期値は、複数のＲＦタグ３の各々において異なる値が割り当てられることを保証するために、予め計算した値を割り当てる。
通信システム１内のＲＦタグ３の数をｍとし、各ＲＦタグ３が認証を行う最高回数をｎとした場合、不正な攻撃に対して十分な耐性を備える必要がある。そのため、通信システム１では、上記ハッシュ値を生成する場合に、以下に示すようにハッシュ・チェーン(hash chain)を構築する。
上記ハッシュ・チェーンは、秘密シードｔから始まり、２番目のｋ２はｈ（ｔ）であり、ｘ番目のｋｘはｈ（ｋｘ−１）である。ここで、「３≦ｘ≦ｍｎ」である。本実施形態では、ハッシュ・チェーンを、ｍｎより長くするように秘密シードｔを選択する。各ＲＦタグ３の秘密データｋの初期値は、上記ハッシュ・チェーンのｋｎｐ番目の要素から選択される。ここで、「１≦ｐ≦ｍ」が成り立つ。各秘密データｋの値は、各ＲＦタグ３のメモリ１３に格納され、管理装置７のテーブルデータＴＤにおいて各ＲＦタグ３の識別データＩＤＲに対応付けられる。ＲＦタグ３および管理装置７は、認証が成功すると、秘密データｋを、ハッシュ・チェーンの次の値に更新する。
【００２６】
ステップＳＴ５：
ＲＦタグ３の処理回路１５は、下記式（２）に示すように、ステップＳＴ３で生成した秘密データｒｉ＋１と、メモリ１３から読み出した秘密データｋｊと、ステップＳＴ２で受信した乱数ｓとを基にハッシュ値を生成し、これを秘密データｒｉ＋２とする。
【００２７】
［数２］
ｒｉ＋２←ｈ（ｒｉ＋１  ＸＯＲ  ｋｊ  ＸＯＲ  ｓ）
…（２）
【００２８】
ステップＳＴ６：
ＲＦタグ３の処理回路１５は、ＲＦ回路１１を介して、ステップＳＴ５で生成した秘密データｒｉ＋２を、タグリーダ５に送信する。
タグリーダ５の処理回路２７は、ステップＳＴ１で生成した乱数ｓと、ＲＦ回路２１で受信した秘密データｒｉ＋２とを、インタフェース２３を介して管理装置７に送信する。
【００２９】
ステップＳＴ７：
ＲＦタグ３の処理回路１５は、下記式（３）に示すように、ステップＳＴ５で生成した秘密データｒｉ＋２と、メモリ１３から読み出した秘密データｋｊとを基にハッシュ値を生成し、これを秘密データｒｉ＋３に設定する。
【００３０】
［数３］
ｒｉ＋３←ｈ（ｒｉ＋２  ＸＯＲ  ｋｊ）
…（３）
【００３１】
ステップＳＴ８：
管理装置７の処理回路３５は、ステップＳＴ４で受信した秘密データｒｉ＋１と、ステップＳＴ６で受信した乱数ｓおよび秘密データｒｉ＋２とを基に、下記式（４）を満たす所定の値ｋ’を、図３に示すテーブルデータＴＤの項目Ｋ，Ｋｌａｓｔのなかから検索する。
【００３２】
［数４］
ｈ（ｒｉ＋１  ＸＯＲ  ｋ’  ＸＯＲ  ｓ）＝  ｒｉ＋２
…（４）
【００３３】
図３に示すように、テーブルデータＴＤの各エントリは、項目ＩＤＲ，Ｋ，Ｋｌａｓｔを有し、それぞれＲＦタグ３のＩＤ、現在の秘密データｋ、前の秘密データｋ（現在の秘密データｋに更新される前の値）を示している。テーブルデータＴＤでは、最初に項目ＩＤＲ，Ｋにそれぞれ各ＲＦタグ３の識別データＩＤと秘密データｋの初期値とが設定され、項目Ｋｌａｓｔはｎｕｌｌ値になっている。項目Ｋｌａｓｔは、非同期（desynchronization）問題を解決するために用いられる。管理装置７がＲＦタグ３の秘密データｋ（例えば、そのＲＦタグ３に対応する項目Ｋの値）を更新し、ＲＦタグ３が攻撃あるいは通信エラーにより、その情報を管理装置７から受信しない場合でも、管理装置７はテーブルデータＴＤの項目Ｋｌａｓｔを参照することで、ＲＦタグ３の以前の識別データＩＤを特定できる。
【００３４】
ステップＳＴ９：
処理回路３５は、上記検索で所定の値ｋ’が、項目Ｋのなかから検索された場合には、下記式（５）に示すように、そのエントリの項目Ｋの値を、そのエントリの項目Ｋｌａｓｔにコピーする。また、処理回路３５は、下記式（６）に示すように、ｋ’のハッシュ値を項目Ｋに設定する。
【００３５】
［数５］
（検索されたエントリの項目Ｋｌａｓｔの値）←（検索されたエントリの項目Ｋの値）
…（５）
【００３６】
［数６］
（検索されたエントリの項目Ｋの値）←ｈ（ｋ’）
…（６）
【００３７】
処理回路３５は、上記検索で所定の値ｋ’が、項目Ｋｌａｓｔのなかから検索された場合には、テーブルデータＴＤの更新を行わない。
なお、処理回路３５は、ステップＳＴ９における検索によって特定されたエントリの識別データＩＤＲと、その検索に用いられたタグリーダ５の識別データなどから、ＲＦタグ３の利用履歴などを追跡可能な情報を取得できる。このような情報は、処理回路３５が生成してもよいし、処理回路３５が取得した情報を基に、管理装置７以外のサーバ装置が行っても良い。
【００３８】
ステップＳＴ１０：
管理装置７の処理回路３５は、下記式（７）に示すように、ステップＳＴ６で受信した秘密データｒｉ＋２と、ステップＳＴ８で検索した所定の値ｋ’とを基にハッシュ値を生成し、これを秘密データｒｉ＋３’に設定する。
【００３９】
［数７］
ｒｉ＋３’←ｈ（ｒｉ＋２  ＸＯＲ  ｋ’）
…（７）
【００４０】
ステップＳＴ１１：
管理装置７の処理回路３５は、ステップＳＴ１０で生成した秘密データｒｉ＋３’をタグリーダ５を介してＲＦタグ３に送信する。
【００４１】
ステップＳＴ１２：
ＲＦタグ３の処理回路１５は、ステップＳＴ１１で受信した秘密データｒｉ＋３’と、ステップＳＴ７で生成した秘密データｒｉ＋３とを比較し、一致していればステップＳＴ１３に進む。
【００４２】
ステップＳＴ１３：
ＲＦタグ３の処理回路１５は、下記式（８）に示すように、ステップＳＴ７で生成した秘密データｒｉ＋３と、秘密データｋｊとを基にハッシュ値を生成し、これを秘密データｒｉ＋４に設定する。
【００４３】
［数８］
ｒｉ＋４←ｈ（ｒｉ＋３  ＸＯＲ  ｋｊ）
…（８）
【００４４】
ステップＳＴ１４：
ＲＦタグ３の処理回路１５は、下記式（９）に示すように、秘密データｋｊのハッシュ値を生成し、これを秘密データｋｊ＋１に設定する。
【００４５】
［数９］
ｋｊ＋１←ｈ（ｋｊ）
…（９）
【００４６】
［ＲＦタグ３の動作例］
図６は、図１に示すＲＦタグ３の動作例を説明するためのフローチャートである。
ステップＳＴ２１：
図２に示すＲＦ回路１１は、タグリーダ５のＲＦ回路２１と無線通信を行って、タグリーダ５が生成した乱数ｓを受信する。
【００４７】
ステップＳＴ２２：
ＲＦタグ３の処理回路１５は、上記式（１）に示すように、メモリ１３から読み出した秘密データｒｉ，ｋｊを基にハッシュ値を生成し、これを秘密データｒｉ＋１に設定する。
【００４８】
ステップＳＴ２３：
ＲＦタグ３の処理回路１５は、ＲＦ回路１１を介して、ステップＳＴ２２で生成した秘密データｒｉ＋１を、タグリーダ５に送信する。
【００４９】
ステップＳＴ２４：
ＲＦタグ３の処理回路１５は、上記式（２）に示すように、ステップＳＴ２３で生成した秘密データｒｉ＋１と、メモリ１３から読み出した秘密データｋｊと、ステップＳＴ２１で受信した乱数ｓとを基にハッシュ値を生成し、これを秘密データｒｉ＋２に設定する。
【００５０】
ステップＳＴ２５：
ＲＦタグ３の処理回路１５は、ＲＦ回路１１を介して、ステップＳＴ２４で生成した秘密データｒｉ＋２を、タグリーダ５に送信する。
【００５１】
ステップＳＴ２６：
ＲＦタグ３の処理回路１５は、上記式（３）に示すように、ステップＳＴ２４で生成した秘密データｒｉ＋２と、メモリ１３から読み出した秘密データｋｊとを基にハッシュ値を生成し、これを秘密データｒｉ＋３に設定する。
【００５２】
ステップＳＴ２７：
ＲＦタグ３の処理回路１５は、ＲＦ回路１１が管理装置７からの応答を受信したか否かを判断し、受信したと判断した場合にステップＳＴ２８に進み、そうでない場合にステップＳＴ２１に戻る。
【００５３】
ステップＳＴ２８：
ＲＦタグ３の処理回路１５は、ＲＦ回路１１が上記受信した応答がＲＥＳＥＴ信号であるか否かを判断し、ＲＥＳＥＴ信号であると判断した場合にはステップＳＴ２１に戻り、そうでない場合にはステップＳＴ２９に進む。
【００５４】
ステップＳＴ２９：
ＲＦタグ３の処理回路１５は、ＲＦ回路１１が上記受信した応答がＦＩＮ信号であるか否かを判断し、ＦＩＮ信号であると判断した場合には処理を終了し、そうでない場合にはステップＳＴ３０に進む。
【００５５】
ステップＳＴ３０：
ＲＦタグ３の処理回路１５は、ＲＦ回路１１が上記受信した応答である秘密データｒｉ＋３’と、ステップＳＴ２６で生成した秘密データｒｉ＋３とを比較し、一致していればステップＳＴ３１に進み、そうでない場合には処理を終了する。
【００５６】
ステップＳＴ３１：
ＲＦタグ３の処理回路１５は、上記式（８）に示すように、ステップＳＴ２６で生成した秘密データｒｉ＋３と、秘密データｋｊとを基にハッシュ値を生成し、これを秘密データｒｉ＋４に設定する。
【００５７】
ステップＳＴ３２：
ＲＦタグ３の処理回路１５は、上記式（９）に示すように、秘密データｋｊのハッシュ値を生成し、これを秘密データｋｊ＋１に設定する。
【００５８】
ＲＦタグ３の処理回路１５は、図６に示す処理を、ＲＦ回路１１がＲＦ回路２１からエネルギが提供されなくなったとき、強制的に終了する。
【００５９】
［タグリーダ５の動作例］
図７は、図１に示すタグリーダ５の動作例を説明するためのフローチャートである。
ステップＳＴ４１：
図２に示すタグリーダ５の処理回路２７は、乱数ｓを発生する。
【００６０】
ステップＳＴ４２：
タグリーダ５の処理回路２７は、ＲＦ回路２１を介してＲＦタグ３にステップＳＴ１で生成した乱数ｓを送信する。
【００６１】
ステップＳＴ４３：
タグリーダ５の処理回路２７は、ＲＦタグ３からの秘密データｒｉ＋１，ｒｉ＋２をＲＦ回路２１が受信するまで、例えば、予め決められた時間Ｔだけ待機する。
【００６２】
ステップＳＴ４４：
タグリーダ５の処理回路２７は、待機時間が上記時間Ｔを経過していないか否かを判断し、経過していないと判断するとステップＳＴ４５に進み、そうでない場合にはステップＳＴ４５に進む。
【００６３】
ステップＳＴ４５：
タグリーダ５の処理回路２７は、ＲＦ回路２１を介してＲＦタグ３に、ＦＩＮ信号を送信する。
【００６４】
ステップＳＴ４６：
タグリーダ５の処理回路２７は、ＲＦ回路２１を介して管理装置７に、ステップＳＴ４１で生成した乱数ｓと、ＲＦタグ３から受信した秘密データｒｉ＋１，ｒｉ＋２とを送信する。
【００６５】
ステップＳＴ４７：
タグリーダ５の処理回路２７は、管理装置７から応答を受信する。
【００６６】
ステップＳＴ４８：
タグリーダ５の処理回路２７は、ステップＳＴ４７で受信した応答が秘密データｒｉ＋３’であるか否かを判断し、そうであると判断するとステップＳＴ４９に進み、そうでないと判断するとステップＳＴ５０に進む。
【００６７】
ステップＳＴ４９：
タグリーダ５の処理回路２７は、ＲＦ回路２１を介してＲＦタグ３に、上記受信した秘密データｒｉ＋３’を送信する。
【００６８】
ステップＳＴ５０：
タグリーダ５の処理回路２７は、ステップＳＴ４７で受信した応答がＣＯＬＬＩＳＩＯＮ信号であるか否かを判断し、そうであると判断するとステップＳＴ５１に進み、そうでないと判断するとステップＳＴ５２に進む。
【００６９】
ステップＳＴ５１：
タグリーダ５の処理回路２７は、ＲＦ回路２１を介してＲＦタグ３に、ＲＥＳＥＴ信号を送信する。
【００７０】
ステップＳＴ５２：
タグリーダ５の処理回路２７は、ＲＦ回路２１を介してＲＦタグ３に、ＦＩＮ信号を送信する。
【００７１】
［管理装置７］
図８は、図３に示す管理装置７の動作例を説明するためのフローチャートである。
ステップＳＴ６１：
管理装置７のインタフェース３１は、タグリーダ５から、乱数ｓ、秘密データｒｉ＋１，ｒｉ＋２を受信し、これらをメモリ３３に書き込む。
【００７２】
ステップＳＴ６２：
管理装置７の処理回路３５は、メモリ３３から読み出した乱数ｓ、秘密データｒｉ＋１，ｒｉ＋２を基に、上記式（４）を満たす所定の値ｋ’を、メモリ３３から読み出した図３に示すテーブルデータＴＤの項目Ｋ，Ｋｌａｓｔのなかから検索する。
【００７３】
ステップＳＴ６３：
管理装置７の処理回路３５は、ステップＳＴ６２の検索で、１個以上のｋ’が検索されたと判断するとステップＳＴ６３に進み、そうでない場合にはステップＳＴ６４に進む。
【００７４】
ステップＳＴ６４：
管理装置７の処理回路３５は、インタフェース３１を介してタグリーダ５にＦＡＩＬＵＲＥ信号を送信する。
【００７５】
ステップＳＴ６５：
管理装置７の処理回路３５は、ステップＳＴ６２の検索で、１個のｋ’が検索されたと判断するとステップＳＴ６７に進み、そうでない場合にはステップＳＴ６６に進む。
【００７６】
ステップＳＴ６６：
管理装置７の処理回路３５は、インタフェース３１を介してタグリーダ５にＣＯＬＬＩＳＩＯＮ信号を送信する。
【００７７】
ステップＳＴ６７：
管理装置７の処理回路３５は、ステップＳＴ６２の検索で所定の値ｋ’が、項目Ｋのなかから検索されたと判断するとステップＳＴ６８に進み、そうでない場合には処理を終了する。
【００７８】
ステップＳＴ６８：
管理装置７の処理回路３５は、上記式（５）に示すように、ステップＳＴ６２で所定の値ｋ’が検索されたエントリの項目Ｋの値を、そのエントリの項目Ｋｌａｓｔにコピーする。
また、処理回路３５は、上記式（６）に示すように、ｋ’のハッシュ値を当該エントリの項目Ｋに設定する。
なお、処理回路３５は、上記検索で所定の値ｋ’が、項目Ｋｌａｓｔのなかから検索された場合には、テーブルデータＴＤの更新を行わない。
【００７９】
ステップＳＴ６９：
管理装置７の処理回路３５は、上記式（７）に示すように、ステップＳＴ６１で受信した秘密データｒｉ＋２と、ステップＳＴ６２で検索した所定の値ｋ’とを基にハッシュ値を生成し、これを秘密データｒｉ＋３’に設定する。
そして、処理回路３５は、インタフェース３１を介して、上記生成した秘密データｒｉ＋３’をタグリーダ５に送信する。
【００８０】
以上説明したように、通信システム１によれば、管理装置７において上述したようにテーブルデータＴＤを用いてＲＦタグ３のＩＤを特定することで、ＲＦタグ３の総数をｍ、各タグに許されるタグリーダ５との間のインタラクションの最大回数をｎとした場合に、ハッシュ関数の演算を２ｍ回にでき、非特許文献１のシステムのｍ＊ｎ回に対して管理装置７の演算量を大幅に削減できる。
すなわち、非特許文献１のシステムでは、引数の初期値として各タグに予め割り当てられたシードを用い、各タグについて、前回のハッシュ値を引数としてハッシュ値を順に生成する。そして、各タグについて、各段階で生成されたハッシュ値とタグから入力した値とを基にＩＤを検索する。そのため、各タグのＩＤ検索に、ｎ回のハッシュ演算を行う必要があり、ｍ個のタグについては合計ｍ＊ｎ回のハッシュ演算を行う必要がある。
これに対して、通信システム１では、上述したテーブルデータＴＤを用いることで、各タグについて、上記式（４）を基にｋ’を生成するためのハッシュ演算と、テーブルデータＴＤを構成するためのハッシュ演算との２回のみを行えばよい。そのため、ＲＦタグ３の数がｍ（テーブルデータＴＤのエントリ数がｍ）の場合には、合計ｍ＊ｎ回のハッシュ演算を行えばよく、管理装置７の演算量を大幅に削減できる。
【００８１】
また、通信システム１によれば、以下に示すように十分なセキュリティ性を持つことができる。
以下、上述した通信システム１のセキュリティ性について説明する。
ハッシュ値ｈ（）はランダムなオラクル(oracle)と仮定すると、通信システム１は、ＲＦタグ３のメモリ１３の不正変更を除いて全ての想定できる攻撃に対して安全である。また一方、メモリ１３の情報をアップデートすることによって、この攻撃が成功する可能性は低くなる。下記は、各々の攻撃に対するセキュリティ分析である。
【００８２】
傍受による攻撃については、傍受によって、攻撃者は１つの認証プロセスの間に乱数ｓと３つの連続した秘密データrを集めることができる。ｓはランダムな値なので、ＲＦタグ３を追跡することはできない。その結果、攻撃者は値ｒを利用しなければならない。その一方、もしｈがランダムなオラクルと仮定すると、ＲＦタグ３のｋｊを知らない攻撃者は、ランダムな値からＲＦタグ３の各々のアウトプットを区別できない。ランダムなオラクルのアウトプットから本物のランダムな値を区別する唯一の方法は、同じインプットでランダムなオラクルを再び生成し、同じ出力を得ることである。その一方、攻撃者はｈのインプットを知ることができない。これは、攻撃者は、ｋｊがｈ（）のパラメータのひとつであるということを知らないためである。その結果、攻撃者はＲＦタグ３のアウトプットをランダムな値のように考える。従って、ＲＦタグ３からの値の全てが本物のランダムな値又は、攻撃者にはランダムな値として見られたため、攻撃者はＲＦタグ３を追跡できない。
【００８３】
偽造については、攻撃者はＲＦタグ３のｋを知らないため、ｒｉ＋１からｒｉ＋２を生成できない攻撃者は反復攻撃を行う必要がある。その結果、攻撃者は２つのランダムな値を送ることができ、この攻撃が特殊なタグを偽造する可能性はｌ・２ｌ−１である。なぜなら、ＫとＫｌａｓｔの項目に２つの値があり、上記式（４）の検証のために使われるためと、それがシステムの任意のタグを偽造する可能性はｍ／２ｌ−１と無視できる程度になる。一方、攻撃者は正規の相互作用の偽造によって、反復攻撃することを試みる可能性がある。ここで、ｓは偽造によって使われ、タグリーダ５が送信したものとは違い、攻撃者の反復攻撃は成功しない。
【００８４】
乱数ｓを制御する攻撃については、攻撃者がＲＦタグ３の応答を生成すること試みるが、乱数ｓを制御することによって追跡しなければならないパターンは多数ある。攻撃者が乱数ｓを送る前にｒｉ＋１を推測することが出来れば、攻撃者はデータの応答が継続的に値ｒｉ＋１を乱数Ｓとして送ることによってデータの返答がいつも同じにできる。その場合、ｒｉ＋２はいつも固定値ｈ（ｋｊ）で、攻撃者はタグを追跡できる。一方、秘密でータｋｊは秘密の値のため、攻撃者はｒｉ＋１を予測できず、この攻撃によりタグを追跡することはできない。
【００８５】
タグのアップデートによる攻撃については、攻撃者はタグ３の秘密キーをアップデートすることによって、非同期攻撃を試みる可能性がある。一方、管理装置７の助けなしで、攻撃者はｒｉ＋３を知ることができない。なぜなら、攻撃者は現在のｋｊを知らないし、ｋｊはｒｉ＋２からｒｉ＋３の計算を必要とするためである。
【００８６】
データベースのアップデートによる攻撃については、攻撃者は、管理装置７のデータベースとタグの間の非同期ｋを介入者攻撃することを試みる可能性がある。通信システム１は、タグ３がタグリーダ５から離れてることと、攻撃者が二つのコメントの間のデータを配信することが出来ると推測する。タグリーダ５が認証処理を開始した時、攻撃者はｓをタグリーダ５からＲＦタグ３に移動し、その後、タグリーダ５にｒｉ＋１とｒｉ＋２を移動する。それから、管理装置７がｋをアップデートする。その後、タグリーダ５がＲＦタグ３のｋを更新したにも係わらず、サーバはｒｉ＋３’を送信する。この時、攻撃者がそれをタグ３に配信しなければ、ｋはデータベースとタグの間で異なる。もし、管理装置７がＩＤを見つけるために最新のｋのみを使用する場合、このタグ３は使用できなくなる。一方、管理装置７は、もう一つのｋを記憶し、それはＫｌａｓｔの項目において、最新のｋが設定される。これを利用して、管理装置７は、タグ３を識別する。タグ３がＫｌａｓｔの項目を使って識別してる時、管理装置７は、ｋをアップデートしないため、項目ＫとＫｌａｓｔの２つは、非同期攻撃からシステムを守るのに充分である。
【００８７】
エネルギーの制御による攻撃については、タグ３のキャパシターが一度に全てのプロセスを操作するため充分なキャパシティを持たないと仮定し、それから、攻撃者が任務操作を除外したい時に、タグの処理をいつでも止めることが出来ると仮定する。この仮定では、他のスキームが弱くなる可能性がある。例えば、上記非特許文献１のシステムは、データを送り、メモリのコンテンツをアップデートします。攻撃者は、タグ３がメモリの内容を更新する直前に、タグの認証処理を停止させ、毎回同じ応答を取得する。しかしながら、通信システム１は、このような攻撃に十分な耐性がある。すなわち、通信システム１は、データを送信する前にそれを更新する。これは、このような攻撃に対してのタグ３の応答のバラツキを保証する。
【００８８】
ハッシュ・チェーンに基づく攻撃については、タグの認証処理の最大回数ｎは、メモリタンパーに基づく攻撃に対して耐えうるために十分に多くする必要がる。最初に攻撃者はタグのｋ，ｋｔａｍｐｅｒを不正に読み出す。その後、攻撃者は、以下に示すようにして、他のターゲットのタグのｋ、ｋｔａｒｇｅｔを取得する。ハッシュ・チェーン内のｋｔａｍｐｅｒより１つ前のｋｔａｍｐｅｒが幸運にも攻撃者が取得したとする。攻撃者は、乱数ｓを用いて管理装置に問い合わせを行い、ｒｉ＋１，ｒｉ＋２を取得する。攻撃者は、ｋｔａｍｐｅｒからスタートしたハッシュ・チェーンの全ての値であるｋ’との間で一致するか否かのテストを行って、ｋｔａｍｐｅｒを検索できる。これは、ハッシュ・チェーンの長さが２ｌではなく、２ｌ／２と短いためである。このような問題は、通信システム１のみならず、ハッシュ・チェーンを用いる全てのシステムに存在する。
【００８９】
メモリタンパーによる攻撃については、攻撃者がタグ３のメモリをタンパーすることによってｋを取得すると共に、管理装置と様々なタグとの間の通信を傍受した場合に、攻撃者はタグの以前のイベントを追跡できる。攻撃者は、固定値ｋと、傍受により収集した情報とを用いて上記式（４）をテストする。そして、攻撃者は、傍受した情報のいずれかが当該テストに合格した場合に、その情報を特定する。しかしながら、このフォアワード・トレースは、ｋの最後の更新前に生成された情報が通信で使われる場合には適用できない。すなわち、攻撃者は、カレントのｋを知り得た場合でも、ｋは一方向性関数ｈによって更新されているため、タグ３の以前のｋを知りえない。従って、フォアワード・トレースは、短期間に限定され、連続して認証が行われるようなプロセスには用いることができない。
【００９０】
本発明は上述した実施形態には限定されない。
すなわち、当業者は、本発明の技術的範囲またはその均等の範囲内において、上述した実施形態の構成要素に関し、様々な変更、コンビネーション、サブコンビネーション、並びに代替を行ってもよい。
【図面の簡単な説明】
【００９１】
【図１】図１は、本発明の実施形態の通信システムの全体構成図である。
【図２】図２は、図１に示すＲＦタグおよびタグリーダの構成図である。
【図３】図３は、図１に示す管理装置の構成図である。
【図４】図４は、図１に示す通信システムの全体動作例を説明するためのフロー図である。
【図５】図５は、図１に示す通信システムの全体動作例を説明するための図４の続きのフロー図である。
【図６】図６は、図１に示すＲＦタグの動作例を説明するためのフローチャートである。
【図７】図７は、図１に示すタグリーダの動作例を説明するためのフローチャートである。
【図８】図８は、図３に示す管理装置の動作例を説明するためのフローチャートである。
【符号の説明】
【００９２】
１…通信システム、３…ＲＦタグ、５…タグリーダ、７…管理装置、１１…ＲＦ回路、１３…メモリ、１５…処理回路、２１…ＲＦ回路、２３…インタフェース、２５…メモリ、２７…処理回路、３１…インタフェース、３３…メモリ、３５…処理回路、ＴＤ…テーブルデータ
【図１】
2007189643.tif 000003
【図２】
2007189643.tif 000004
【図３】
2007189643.tif 000005
【図４】
2007189643.tif 000006
【図５】
2007189643.tif 000007
【図６】
2007189643.tif 000008
【図７】
2007189643.tif 000009
【図８】
2007189643.tif 000010