Unlinkable ID Matching Protocol for Large-scale RFID Systems

近年急速に，IC カードやRFID タグといったデバイスの普及が進んできている．しかし，第 三者がユーザに無断でデバイスのID を読み取ることにより，ユーザの履歴情報を収集し，個人の行動を 追跡できてしまうという問題がある．この問題を解決する方法として，デバイスの出力を毎回可変にす るRandomized Hash Lock 方式やID 照合方式がある．しかしながら，これらの方式はデバイス数 $ N $ に 対して，1 回のID 解決毎にサーバ側でハッシュ計算を$ O(N) $ 回必要とし，大規模システムに適用するに は問題があった．本稿で提案する方式は，ID を分割し，各部分ID についてそれぞれID 解決を行うこと により，サーバ側で必要なハッシュ計算を $ O(log N) $ 回に抑えることができる