他サービス環境でのＩＤデバイスのリンク不能性を守るＩＤ管理装置と方法
【課題】多サービスが可能なＩＤデバイスにおいて、第2者サービスにのみリンク可能性を許し、第3者サービスを含むそれ以外の者にはリンク不能性を保証するような高速なＩＤの識別の方式を提供する。
【解決手段】ＩＤデバイスに唯一に与えられるユーザＩＤと、ユーザＩＤの一部を抽出したサブＩＤと、サブＩＤを用いてユーザを識別するサービスシステムと、サービスシステムが持つ複数のユーザに対するサブＩＤリストと、サブＩＤ以外の一部を抽出した他サブＩＤを用いてユーザを識別する複数の他サービスシステムと、他サービスシステムそれぞれがもつ複数のユーザに対する他サブＩＤリストと、サービスシステムに唯一に与えられるサービスＩＤと、を備えた識別方法において、ＩＤデバイスとサービスシステムがユーザＩＤやサブＩＤをそのままの値でやりとりすることなくサービスシステムがサブＩＤを識別し、他サービスシステムにはサブＩＤを識別させない。
【解決手段】ＩＤデバイスに唯一に与えられるユーザＩＤと、ユーザＩＤの一部を抽出したサブＩＤと、サブＩＤを用いてユーザを識別するサービスシステムと、サービスシステムが持つ複数のユーザに対するサブＩＤリストと、サブＩＤ以外の一部を抽出した他サブＩＤを用いてユーザを識別する複数の他サービスシステムと、他サービスシステムそれぞれがもつ複数のユーザに対する他サブＩＤリストと、サービスシステムに唯一に与えられるサービスＩＤと、を備えた識別方法において、ＩＤデバイスとサービスシステムがユーザＩＤやサブＩＤをそのままの値でやりとりすることなくサービスシステムがサブＩＤを識別し、他サービスシステムにはサブＩＤを識別させない。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＲＦＩＤ（Radio Frequency Identification）タグやＩＣカード、携帯電話といったＩＤデバイスのセキュリティおよび、個人情報保護、リンク不能性、認証、識別に関する。
【背景技術】
【０００２】
現在、ＩＣカードやＲＦＩＤタグ、携帯電話といった小型のデバイスが物品や利用者に与えられ、種々のサービスを利用者が享受する際に、これらのデバイスとサービス機器の間の近距離通信により物品や利用者を識別することが多くなってきている。
【０００３】
ＩＣカードは、サービス機器と、接触あるいは非接触の状態で通信をおこなうことのできるカード形状のデバイスであり、内部にアンテナをはじめ、計算能力をもつプロセッサや通信が終わっても記憶をつづけることができる不揮発性メモリを持つ。
【０００４】
ＲＦＩＤタグは、サービス機器と、非接触の状態で通信をおこなうことのできる小型のデバイスであり、内部にアンテナをはじめ、計算能力をもつプロセッサや通信が終わっても記憶をつづけることができる不揮発性メモリを持つ。
【０００５】
これらのデバイスは、他のデバイスと区別して識別されるように、サービスの中で唯一の識別子（ＩＤ）を保持する。
【０００６】
そこで、これらＩＤを持つデバイスはＩＤデバイスと呼ばれる。
【０００７】
しかし、これらＩＤは、その利用者が気づかないうちに任意の第3者に読み取られてしまう可能性があり、その結果ＩＤデバイスの位置や、ＩＤに関連する個人情報が漏洩してしまうという問題が発生する。
【０００８】
特に、複数のＩＤデバイスの識別の履歴の中から、１つのＩＤデバイスについての履歴を第3者が選別し知ることができてしまうというリンク可能性の問題がある。
【０００９】
リンク可能性の問題は、利用者の名前や住所といった個人に関する情報を知らなくても、第3者にとって目の前にいる人の行動履歴を知ることができてしまうというように、個人情報が脅かされる問題である。
【００１０】
リンク可能性の問題は、ＩＤを単純に暗号化して識別に用いるだけでは解決できないという意味で、通常の個人情報の保護よりも難しい問題である。
【００１１】
これをふまえて、ＩＤを識別する際に、乱数などの毎回変化する値をＩＤの暗号化の際の入力に加えて、第3者にとっては毎回異なる値が得られるような方式が提案された（特許文献１）。
【００１２】
一方、世の中に情報サービスが普及するにつれ、ＩＣカードを利用者がたくさん保持することが多くなり、1枚のＩＣカードを複数のサービスのＩＤデバイスとして用いる要求が大きくなってきた。
【００１３】
また、物品につけられるＲＦＩＤタグに関しても、物品のライフサイクルの複数の場面で異なる目的に用いられることが望まれており、この場合も1つのＩＤデバイスを複数のサービスに用いるという要求と合致する。
【００１４】
しかし、1つのＩＤデバイスが多数のサービスに用いられるようになればなるほど、そのＩＤがサービスやＩＤデバイスから漏洩した際の被害は大きくなる。
【００１５】
リンク可能性の問題も同様に増大し、個人の行動を常に追跡する恐れが大きくなる。
【００１６】
そこで、ＩＤデバイスに与えられるＩＤの一部を抽出して与えられるサブＩＤを個々のサービスのために用い、別のサービスにはＩＤの別の一部を抽出して与えられる別のサブＩＤを用いることにより、被害の拡大を防ぐ方法が提案された（非特許文献1、特許文献2）。
【００１７】
【非特許文献１】Stephen A。 Weis他著 鉄ecurity and Privacy Aspects of Low-Cost Radio Frequency Identification Systems煤ASpringer Verlag社、「Security in Pervasive Computing」、Lecture Notes in Computer Science、Volume 2802、201-212ページ、2003年
【特許文献１】特開２００４−３１７７６４号公報
【特許文献２】特開２００４−１９２４８７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
以上説明したように、多サービスを実現するＩＤデバイスにおいては、複数のＩＤデバイスの識別の履歴の中から、１つのＩＤデバイスについての履歴を第3者が選別し知ることができないことを保証するというリンク不能性を達成することが重要である。
【００１９】
非特許文献1と特許文献1は、ＩＤを識別する際に、毎回変化する値とともにＩＤを暗号化することにより、第3者にとっては毎回異なる値が得られるようにすることにより第3者に対するリンク不能性を実現する方法である。
【００２０】
しかし、多サービスの環境においては、第3者には、第2者となるサービス以外のサービス（第3者サービス）も含まれる。
【００２１】
非特許文献1や特許文献1はこのような多サービスを想定していないために、第2者サービスと第3者サービスの区別をすることができない。
【００２２】
この結果、サービスの資格を持たない者に対するリンク不能性は実現できても、サービスの資格を持つ第3者に対するリンク不能性は実現できない。
【００２３】
また、特許文献2は多サービスを志向しているものの、ＩＤデバイスの識別の方式については記述がないため、リンク不能性は実現できていない。
【００２４】
本発明は、多サービスが可能なＩＤデバイスにおいて、第2者サービスにのみリンク可能性を許し、第3者サービスを含むそれ以外の者にはリンク不能性を保証するようなＩＤの識別の方式を提供することを目的とする。
【００２５】
また本発明は、上記のような第2者サービスにのみリンク可能性を許す識別の際に、ＩＤデバイスとサービスが相互に安全に認証をおこなう方式を提供することを目的とする。
【００２６】
さらに本発明は、上記のような第2者サービスにのみリンク可能性を許す識別および認証の際に問題となる、処理時間の長大化を抑え高速化する方式を提供することを目的とする。
【課題を解決するための手段】
【００２７】
この目的を達成するために、本発明の識別方法は、ＩＤデバイスとサービスシステムがユーザＩＤやサブＩＤをそのままの値でやりとりすることなく前記サービスシステムが前記サブＩＤを識別し、他サービスシステムにはサブＩＤを識別させないことを特徴とし、これを実現するために、複数のユーザと、前記ユーザそれぞれが保有するＩＤデバイスと、前記ＩＤデバイスに唯一に与えられるユーザＩＤと、前記ユーザＩＤの一部を抽出して与えられるサブＩＤと、前記サブＩＤを用いてユーザを識別するサービスシステムと、前記サービスシステムが持つ複数の前記ユーザに対するサブＩＤリストと、前記ユーザＩＤの前記サブＩＤ以外の一部を抽出して与えられる他サブＩＤを用いて前記ユーザを識別する複数の他サービスシステムと、前記他サービスシステムそれぞれがもつ複数の前記ユーザに対する他サブＩＤリストと、前記サービスシステムに唯一に与えられるサービスＩＤを備えるように構成する。
【００２８】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を達成できる。
【００２９】
このように構成される本発明の識別方法は、以下に説明する６つの構成にしたがって、ＩＤデバイスの識別におけるリンク不能性を達成する。
【００３０】
第1の構成として、前記サービスシステムが、前記サービス乱数発生装置を用いてサービス乱数を生成し、前記サービスシステムが、前記サービスＩＤと前記サービス乱数を前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが、前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが、前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記サービス乱数と前記サブＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数とともに前記サービスシステムに渡し、その後、前記サービスシステムが前記サービスハッシュ装置および前記サービス乱数、前記ユーザ乱数および自己がもつ前記サブＩＤリストを用いて前記ユーザハッシュ値に対応する前記サブＩＤを検索することによりＩＤデバイスを識別するように処理する。
【００３１】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を達成できる。
【００３２】
第2の構成として、前記サービスシステムが、前記サービス乱数発生装置を用いてサービス乱数を生成し、前記サービスシステムが、前記サービスＩＤと前記サービス乱数を前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記公開鍵と前記公開鍵暗号化装置を用いて前記ユーザ乱数と前記サービス乱数と前記サブＩＤとを暗号化した暗号値を前記サービスシステムに渡し、その後、前記サービスシステムが前記秘密鍵と前記公開鍵復号化装置を用いて前記暗号値を前記サブＩＤに復号化することによりＩＤデバイスを識別するように処理する。
【００３３】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を達成できる。
【００３４】
第3の構成として、前記サービスシステムが、前記サービスＩＤを前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記ユーザＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数および前期グループＩＤとともに前記サービスシステムに渡し、その後、前記サービスシステムが前記グループＩＤと前記グループＩＤリストを元に前記ＩＤデバイスが属するグループを特定し、その後、前記サービスシステムが前記サービスハッシュ装置と前期ユーザ乱数および自己がもつ前記ユーザＩＤリストを用いて前記ユーザハッシュ値に対応する前記ユーザＩＤを前記グループに属するユーザの中から検索することによりＩＤデバイスを識別するように処理する。
【００３５】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を一定のレベルで達成できるのと同時に、サービスシステム側で必要なサブＩＤリストの検索処理を高速化することができる。
【００３６】
第4の構成として、前記サービスシステムが、前記サービスＩＤを前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置を用いて前記ユーザ乱数とひとつの前記部分サブＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数とともに前記サービスシステムに渡すという部分サブＩＤ開示処理を実行し、その後、前記サービスシステムが前記サービスハッシュ装置と前期ユーザ乱数および自己がもつ前記ユーザＩＤリストを用いて前記ユーザハッシュ値に対応する複数の前記ユーザＩＤを絞り込むというサブＩＤ絞込み処理を実行し、その後、サブＩＤが1つに絞り込まれるまで前記部分サブＩＤ開示処理と前記サブＩＤ絞込み処理を繰り返すことによりＩＤデバイスを識別するように処理する。
【００３７】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を最大のレベルまで達成できるのと同時に、サービスシステム側で必要なサブＩＤリストの検索処理を高速化することができる。
【００３８】
第5の構成として、第3または4の構成に加えて、すべての前記ユーザについての前記ユーザＩＤと前記サブＩＤが一致するようにサブＩＤを抽出し、すべての前記サービスの前記サービスＩＤが空値を含む固定値であるように構成する。
【００３９】
これにより、多サービス環境だけでなく、従来からの1つのサービスの環境においてリンク不能性が求められる場合においても、リンク不能性の達成を行いながらサービスシステム側で必要なサブＩＤリストの検索処理を高速化することができる。
【００４０】
第6の構成として、前記第1〜5のいずれかの構成に加え、前記サービスシステムと前記ＩＤデバイスが相互に認証するように構成する。
【００４１】
これにより、リンク不能性の達成を行いながらのＩＤデバイスの識別と同時に、リンク不能性の達成を行いながらのＩＤデバイスとサービスシステムの間の相互認証が可能になる。
【００４２】
第6の構成は、以下に説明する2つの構成に従って、リンク不能性を保ったままでのＩＤデバイスとサービスシステムの間の相互認証を実現する。
【００４３】
第6aの構成として、第1〜5のいずれかの構成に加え、前記サービスシステムが前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記サブＩＤをハッシュ変換したサービスハッシュ値を前記ＩＤデバイスに渡し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置と前記サービス乱数および自己が持つ前記サブＩＤを用いて前記サービスハッシュ値が前期ユーザＩＤに対応するかを確認し、対応すれば前期ＩＤデバイスが前記サービスシステムを正しいサービスシステムであると認証することによって相互認証を実現するように処理する。
【００４４】
これにより、リンク不能性を保ったままでのＩＤデバイスとサービスシステムの間の相互認証が実現できる。
【００４５】
第6aの構成として、第1〜5のいずれかの構成に加え、前記サービスシステムが前記公開鍵と前記公開鍵暗号化装置を用いて前記サービス乱数と前記サブＩＤを暗号化したサービス暗号値を前記ＩＤデバイスに渡し、その後、前記ＩＤデバイスが前記ユーザ秘密鍵と前記ユーザ公開鍵復号化装置を前記サービス暗号値を復号化し、これが前記サブＩＤに一致すれば前期ＩＤデバイスが前記サービスシステムを正しいサービスシステムであると認証することによって相互認証を実現するように処理する。
【００４６】
これにより、リンク不能性を保ったままでのＩＤデバイスとサービスシステムの間の相互認証が実現できる。
【発明の効果】
【００４７】
本発明の識別方法によれば、ＩＤデバイスは第２者サービスシステムにのみ識別させ、第３者サービスシステムや第３者に対しては識別させることがない。
【００４８】
ＩＤデバイスは、第２者サービスシステムからサービスＩＤを受け取った後で第２者サービスシステムにのみ識別できる値をもちいて識別に必要な値を出力するため、第２者サービスシステム以外にはＩＤデバイスが毎回異なる値を出しているように見え、複数のＩＤデバイスの識別の履歴を元に、同一のＩＤデバイスの履歴を抽出することができず、リンク不能性を達成することができる。
【００４９】
また本発明の相互認証方法によれば、ＩＤデバイスを第２者サービスシステムにのみ識別させながら相互認証をすることができる。
【００５０】
ＩＤデバイスと第２者サービスシステムの間で、識別に必要な値も暗号化またはハッシュかしながら相互認証を行うため、第２者サービスシステム以外の者に対するリンク不能性を保障しながら相互認証を行うことができる。
【発明を実施するための最良の形態】
【００５１】
A||Bは、AとBという2つの情報の結合を表す。情報の結合としては、2つの情報を単に連接する方法や2つの情報の排他的論理和をとる方法などがある。
【００５２】
H(A)は、Aという情報を一方向性ハッシュ関数によって変換したハッシュ値を表す。
【００５３】
一般に一方向性ハッシュ関数は、任意長の入力に対応することを求められるが、本発明で用いる一方向性ハッシュ関数は、固定長の入力にのみ対応するものも含む。
【００５４】
(実施の形態1)
本発明の実施例1を説明する。
【００５５】
本実施例において、ＩＤデバイスとして非接触ＩＣカードを想定する。
【００５６】
図１にＩＤデバイスを用いたサービスシステムの一例を図示する。
【００５７】
図１において、１a〜１ｃはユーザ、２ａ〜２ｃは各ユーザが持つＩＤデバイス、３ａ〜３ｃはサービスシステム、４ａ〜４ｃは各サービスシステムが持つリーダ（ＩＤデバイス読み取り機）、５ａ〜５ｃは各サービスシステムが持つ情報システム、６ａ〜６ｃは各サービスシステムが持つデータベースシステムである。
【００５８】
図２は、ＩＣカードの構成である。
【００５９】
図２において、１４はＩＣカード、１５はハッシュ装置や乱数生成装置をもつ暗号計算部、１６は計算を行う論理計算部、１７は無線通信部、１９はデータを格納する不揮発性メモリ、１８はユーザＩＤを格納するＲＯＭ領域、２０はアンテナからの波形を電力に変える電力供給部、２１は無線によって外部と通信を行うためのアンテナである。
【００６０】
本発明のＩＣカードでは、サービスＩＤから対応するサービスシステムのサブＩＤの先頭アドレスと終端アドレスを取り出すための関数f、ハッシュ装置、乱数発生装置を有するものとする。
【００６１】
関数fの例としては、サブＩＤの先頭アドレスとして「サービスＩＤ×サブＩＤの長さ」を、終端アドレスとして「(サービスＩＤ+1)×サブＩＤの長さ-1」を出力する関数が考えられる。
【００６２】
また関数fとして、あらかじめサービスＩＤとそのサービスシステムのサブＩＤのアドレスをＲＯＭに記録してあるルックアップテーブルを用いることも考えられる。
【００６３】
図３は、ユーザとサービスシステムにおけるサブＩＤの配置である。
【００６４】
図３において、２９ａ〜２９ｃはＩＣカードにそれぞれ保持されるユーザＩＤ、３０ａ〜３０ｃは、各ユーザＩＤのサービスシステム１に対するサブＩＤ、３１ａ〜３１ｂはサービスシステム、３２ａ〜３２ｃは各ユーザＩＤのサービスシステム１に対するサブＩＤ、３２ｄ〜３２ｆは各ユーザＩＤのサービスシステム１に対するサブＩＤである。
【００６５】
ハッシュ装置に実装されるハッシュ関数として、SHA(Secure Hash Algorithm)-256やSHA-512、MD5などを用いることができる。
【００６６】
サービスシステムの情報システムは、ＩＣカードの発行機関から発行されたサービスを提供する全ユーザに対応するサブＩＤをデータベースに保存しておく。
【００６７】
また、ＩＣカードの発行機関から発行された当該サービスシステムを特定するためのサービスＩＤをデータベースに保存しておく。
【００６８】
図４は、ＩＣカードとサービスシステムの間の、ハッシュ関数を用いた識別方法の手順である。
【００６９】
ＩＣカードが接近したことを感知したリーダは、乱数発生装置によって乱数Rsを生成し（Ｓｔｅｐ１５）、データベースに保存されているサービスＩＤの取り出し（Ｓｔｅｐ１６）を行う。
【００７０】
情報システムは、リーダを通じて乱数RsとサービスＩＤをＩＣカードに送信する（Ｓｔｅｐ１７）。
【００７１】
乱数Rsは、情報システムのメモリに保存される。
【００７２】
リーダからサービスＩＤを受け取った（Ｓｔｅｐ２）ＩＣカードは、関数fにより当該サービスＩＤに対応するサービスシステムのサブＩＤの先頭アドレスと終端アドレスを取り出す（Ｓｔｅｐ４）。
【００７３】
ＩＣカードは、取り出されたアドレスを指定することにより、ユーザＩＤを格納するＲＯＭ領域からサブＩＤを取り出す（Ｓｔｅｐ５）。
【００７４】
ＩＣカードは、乱数発生装置によって乱数Ruを生成し（Ｓｔｅｐ３）、サブＩＤと乱数Rsと乱数Ruのデータを結合する。
【００７５】
ＩＣカードは、乱数Rsと乱数RuとサブＩＤ SIDの結合データをハッシュ装置によって、ハッシュ値に変換し（Ｓｔｅｐ６）、ハッシュ値Hu=H(Rs || Ru || SID)と乱数Ruをリーダを通じて情報システムに送付する（Ｓｔｅｐ７）（Ｓｔｅｐ１８）。
【００７６】
情報システムは、ＩＣカードから送付された乱数Ruとメモリに保持されている乱数Rsを用いて、H(Rs || Ru || SID)の計算をデータベースに含まれる全てのサブＩＤについて計算し、ＩＣカードから送られてきたハッシュ値Huと一致するものを検索する（Ｓｔｅｐ１９〜２１）。
【００７７】
ハッシュ値Huと一致するH(Rs || Ru || SID)に対応するサブＩＤが、ＩＣカードのＩＤとなる。対応するサブＩＤが見つからなかった場合、情報システムはプロトコルを終了する（Ｓｔｅｐ２５）。
【００７８】
情報システムは、サブＩＤとＩＣカードから送信された乱数をハッシュ化したHs=H(SID || Ru)をリーダを通じてＩＣカードに送信する（Ｓｔｅｐ２２、２３、８）。
【００７９】
ＩＣカードは、リーダから送られてきたHsがH(SID || Ru)と一致するか検証する（Ｓｔｅｐ９）。
【００８０】
一致した場合、ＩＣカードはリーダに対して認証成功を伝える（Ｓｔｅｐ１０、１２、２３）。
【００８１】
一致しなかった場合、ＩＣカードはリーダに対して認証失敗を伝え（Ｓｔｅｐ１１、１２、２３）、認証プロトコルを終了する（Ｓｔｅｐ１３）。
【００８２】
認証が成功した場合、ＩＣカードと情報システムの間で各種サービスが行われる。
【００８３】
小売店におけるポイントサービスやマーケティングシステムを考える。
【００８４】
小売店は、商品の購入時にＩＣカードの提示を客に求めることにより、その客が購入した商品の情報をサブＩＤをもとに紐付けしていくことが可能となる。よって、小売店は紐付けされた商品情報に客ごとの購入パターンを分析することができ、マーケティングに生かすことができる利点がある。また、小売店が客の購入金額に応じたポイントをサブＩＤを元に累算していくことにより、客は累積ポイント数に応じた買い物をできるという利点がある。
【００８５】
図４は、ＩＣカードとサービスシステムの間の、ハッシュ装置を用いたＩＤの識別方法の手順である。
【００８６】
ＩＣカードが接近したことを感知したリーダは、乱数発生装置によって乱数Rsを生成し（Ｓｔｅｐ１５）、データベースに保存されているサービスＩＤの取り出し（Ｓｔｅｐ１６）を行う。
【００８７】
情報システムは、リーダを通じて乱数RsとサービスＩＤをＩＣカードに送信する（Ｓｔｅｐ１７）。
【００８８】
乱数Rsは、情報システムのメモリに保存される。
【００８９】
リーダからサービスＩＤを受け取った（Ｓｔｅｐ２）ＩＣカードは、関数fにより当該サービスＩＤに対応するサービスシステムのサブＩＤの先頭アドレスと終端アドレスを取り出す（Ｓｔｅｐ４）。
【００９０】
ＩＣカードは、取り出されたアドレスを指定することにより、ユーザＩＤを格納するＲＯＭ領域からサブＩＤを取り出す（Ｓｔｅｐ５）。
【００９１】
ＩＣカードは、乱数発生装置によって乱数Ruを生成し（Ｓｔｅｐ３）、サブＩＤと乱数Rsと乱数Ruのデータを結合する。
【００９２】
ＩＣカードは、乱数Rsと乱数RuとサブＩＤの結合データをハッシュ装置によって、ハッシュ値に変換し（Ｓｔｅｐ６）、ハッシュ値Hu=H(Rs || Ru || SID)と乱数Ruをリーダを通じて情報システムに送付する（Ｓｔｅｐ７）（Ｓｔｅｐ１８）。
【００９３】
情報システムは、ＩＣカードから送付された乱数Ruとメモリに保持されている乱数Rsを用いて、H(Rs || Ru || SID)の計算をデータベースに含まれる全てのサブＩＤについて計算し、ＩＣカードから送られてきたハッシュ値Huと一致するものを検索する（Ｓｔｅｐ１９〜２１）。
【００９４】
ハッシュ値Huと一致するH(Rs || Ru || SID)に対応するサブＩＤが、ＩＣカードのＩＤとなる。対応するサブＩＤが見つからなかった場合、情報システムはプロトコルを終了する（Ｓｔｅｐ２５）。
【００９５】
情報システムは、サブＩＤとＩＣカードから送信された乱数をハッシュ化したHs=H(SID || Ru)をリーダを通じてＩＣカードに送信する（Ｓｔｅｐ２２、２３、８）。
【００９６】
ＩＣカードは、リーダから送られてきたHsがH(SID || Ru)と一致するか検証する（Ｓｔｅｐ９）。
【００９７】
一致した場合、ＩＣカードはリーダに対して認証成功を伝える（Ｓｔｅｐ１０、１２、２３）。
【００９８】
一致しなかった場合、ＩＣカードはリーダに対して認証失敗を伝え（Ｓｔｅｐ１１、１２、２３）、認証プロトコルを終了する（Ｓｔｅｐ１３）。
【００９９】
認証が成功した場合、ＩＣカードと情報システムの間で各種サービスが行われる。
【０１００】
建物の入退出管理である場合を考える。
【０１０１】
建物のドアにはリーダが取り付けられている。取り出されたサブＩＤにより、ユーザが部屋のドアを開閉する権限を有するかを判定できる。
【０１０２】
また、ＩＣカードのメモリに、ＩＣカードを保有するユーザの生体情報、例えば指紋情報や目の虹彩情報が格納されているものとする。
【０１０３】
認証成功後、ＩＣカードのメモリにある生体情報へのアクセスが許可され、情報システムは生体情報を取り出す。情報システムには生体情報読取装置、例えば指紋読み取り器や虹彩読み取り器が接続されており、ユーザは生体情報読み取り機に指紋や虹彩などを読み取らせる。
【０１０４】
カード内の生体情報と生体情報読み取り機からの情報を比較することにより、情報システムは認証者が正規のＩＣカードの持ち主であることを確認できる。
【０１０５】
カード内に生体情報が格納されているため、情報システム側でユーザの個人情報である生体情報を管理する必要がない。
【０１０６】
また、識別方法には公開鍵暗号を用いた手法も可能である。
【０１０７】
図５は、ＩＣカードとサービスシステムの間の、公開鍵暗号を用いた識別方法の手順である。
【０１０８】
ＩＣカードが接近したことを感知したリーダは、乱数発生装置によって乱数Rsを生成し（Ｓｔｅｐ１５）、データベースに保存されているサービスＩＤの取り出し（Ｓｔｅｐ１６）を行う。
【０１０９】
情報システムは、リーダを通じて乱数RsとサービスＩＤをＩＣカードに送信する（Ｓｔｅｐ１７）。
【０１１０】
乱数Rsは、情報システムのメモリに保存される。
【０１１１】
リーダからサービスＩＤを受け取った（Ｓｔｅｐ２）ＩＣカードは、関数fにより当該サービスＩＤに対応するサービスシステムのサブＩＤの先頭アドレスと終端アドレスを取り出す（Ｓｔｅｐ４）。
【０１１２】
ＩＣカードは、取り出されたアドレスを指定することにより、ユーザＩＤを格納するＲＯＭ領域からサブＩＤを取り出す（Ｓｔｅｐ５）。
【０１１３】
ＩＣカードは、乱数発生装置によって乱数Ruを生成し（Ｓｔｅｐ３）、サブＩＤと乱数Rsと乱数Ruのデータを結合する。
【０１１４】
ＩＣカードは、乱数Rsと乱数RuとサブＩＤ SIDの結合データを公開鍵暗号化装置Ｅによって、暗号値に変換し（Ｓｔｅｐ６）、暗号値Eu=Ｅ(Rs || Ru || SID)と乱数Ruをリーダを通じて情報システムに送付する（Ｓｔｅｐ７）（Ｓｔｅｐ１８）。
【０１１５】
情報システムは、ＩＣカードから送付された乱数Ruとメモリに保持されている乱数Rsを用いて、Ｅ(Rs || Ru || SID)を復号化しサブID SIDとRsとRuを得る（Ｓｔｅｐ１９）。
【０１１６】
対応するサブＩＤがサブＩＤリストに見つからなかった場合、情報システムはプロトコルを終了する（Ｓｔｅｐ２０、２６）。
【０１１７】
情報システムは、Rsがもとの値と同じであることを確認し（Ｓｔｅｐ２１）、同じでなければプロトコルを終了する（Ｓｔｅｐ２６）。
【０１１８】
サブＩＤとＩＣカードから送信された乱数を暗号化したEs=Ｅ(SID || Ru)をリーダを通じてＩＣカードに送信する（Ｓｔｅｐ２２、２３、８）。
【０１１９】
ＩＣカードは、リーダから送られてきたEsがＥ(SID || Ru)と一致するか検証する（Ｓｔｅｐ９）。
【０１２０】
一致した場合、ＩＣカードはリーダに対して認証成功を伝える（Ｓｔｅｐ１０、１２、２４）。
【０１２１】
一致しなかった場合、ＩＣカードはリーダに対して認証失敗を伝え（Ｓｔｅｐ１１、１２、２４）、認証プロトコルを終了する（Ｓｔｅｐ１３）。
【０１２２】
認証が成功した場合、ＩＣカードと情報システムの間で各種サービスが行われる。
(実施の形態2)
本発明の実施例2を説明する。
【０１２３】
図６にＩＤデバイスを用いたサービスシステムの一例を図示する。
【０１２４】
本実施例において、ＩＤデバイスとしてＲＦＩＤタグを想定する。
【０１２５】
図６において、７a〜７ｂはユーザ、８ａ〜８ｄは各ユーザが持つ物品、９ａ〜９ｄは各物品につけられたＲＦＩＤタグ、１０ａ〜１０ｃはサービスシステム、１１ａ〜１１ｃは各サービスシステムが持つリーダ（ＩＤデバイス読み取り機）、１２ａ〜１２ｃは各サービスシステムが持つ情報システム、１３ａ〜１３ｃは各サービスシステムが持つデータベースシステムである。
【０１２６】
図７は、ＲＦＩＤタグの構成である。
【０１２７】
図７において、２２はＲＦＩＤタグ、 ２３はハッシュ装置や乱数生成装置をもつ暗号計算部、２４は計算を行う論理計算部、２５は無線通信部、２６はユーザＩＤを格納するＲＯＭ領域、２７はアンテナからの波形を電力に変える電力供給部、２８は無線によって外部と通信を行うためのアンテナである。
【０１２８】
情報システムには、データベースがあり、情報システムがシステム内における全ＲＦＩＤタグに格納されたサブＩＤ情報が格納される。
【０１２９】
システムで用いられるサブＩＤの作成方法は次の通りである。
【０１３０】
深さKのラベル付き木(labeled tree)を考える(図８参照)。
【０１３１】
木はN個の葉を持ち、各葉が各ＲＦＩＤタグi(1<=i<=N)に対応している。
【０１３２】
ある同じ親を持つ子達には、それぞれユニークなラベルが付けられる。
【０１３３】
根から葉に向かって進んで行った場合の各ラベルを集めたものが、その葉の持つサブＩＤであり、対応する各ＲＦＩＤタグiに付与される。
【０１３４】
また、ＲＦＩＤタグiのk(1<=k<=s(i))番目のラベルをＩＤ(i)[k]と表記する。
【０１３５】
各接点につけられたラベルが部分サブＩＤに相当する。
【０１３６】
図８は、ＲＦＩＤタグと情報システムにおけるサブＩＤおよび部分サブＩＤの配置である。
【０１３７】
図８において、４０ａ〜４０ｃは、各ＲＦＩＤタグにおける、１つのサービスシステムに対するサブＩＤ、３３は情報システムにおけるサブＩＤ情報、 ３４はＩＤ(i)[1]、３５はＩＤ(i)[2]、３６はＩＤ(i)[3]、３７はＩＤ(i)[4]、３８はＩＤ(i)[5]、３９ａ〜３９ｇは根から葉に向かって進んで行った場合の各ラベルを集めたサブＩＤである。
【０１３８】
ただしここではＩＤ(i)[k]においてkは１〜５の値であるが、実際にはもっと多くても少なくてもよい。
【０１３９】
ただし、S(i)はＲＦＩＤタグiに対応する葉の深さであり、1<=S(i)<=Kである。
【０１４０】
情報システムはラベル付き木を木構造のまま保存しておく。
【０１４１】
図９は、ＲＦＩＤタグとサービスシステムの間のＩＤの識別方法の手順である。
【０１４２】
ＲＦＩＤタグがリーダの通信圏内に入ると、ＲＦＩＤタグは乱数Rを生成する（Ｓｔｅｐ２）。
【０１４３】
ＲＦＩＤタグは、各部分サブＩＤについて、Hu[k]=H(ＩＤ_{i}[k] || R) (1<=k<=S(i))を計算し（Ｓｔｅｐ３、４、５）、乱数Rと各部分サブＩＤに対応するハッシュ値(Hu[1]、Hu[2]、・・・、Hu[S(i)])の組を情報システムに送信する。
【０１４４】
なお、S(i)<Kの場合は、(Hu[1]、Hu[2]、・・・、Hu[S(i)])に代えて、Hu[l] (S(i)+1<=l<=K)として乱数をパディングした(Hu[1]、Hu[2]、・・・、Hu[S(i)]、Hu[S(i)+1]、・・・、Hu[K])を情報システムに送信する（Ｓｔｅｐ６、７、８）ことにより、Huの個数の違いによって、第三者に対するリンク不能性が悪化することを防止できる。
【０１４５】
サービスシステムは、RとHu[1]、Hu[2]、・・・、Hu[K]を受け取るとＳｔｅｐ１２〜２３の手順で処理する。
【０１４６】
認証が成功した場合、ＩＣカードと情報システムの間で各種サービスが行われる。
【０１４７】
任意のＲＦＩＤタグと情報システム間における可変ＩＤ情報のやりとりの頻度が、等しく同じであるならば、木構造を完全α分木、すなわち葉を除く各接点から出る枝の数がすべて等しく同じα本の木を構成することにより、情報システム側で必要なハッシュ計算の平均計算量を最小化することができる。
【０１４８】
すなわちK＝N^{1/K}、ただし、α=N^{1/K}である。
【図面の簡単な説明】
【０１４９】
【図１】ＩＤデバイスを用いたサービスシステム
【図２】ＩＣカードの構成
【図３】ユーザとサービスシステムにおけるサブＩＤの配置
【図４】ＩＣカードとサービスシステムの間の、ハッシュ関数を用いた識別方法の手順
【図５】ＩＣカードとサービスシステムの間の、公開鍵を用いたＩＤの識別方法の手順
【図６】ＲＦＩＤタグを用いたサービスシステム
【図７】ＲＦＩＤタグの構成
【図８】ＲＦＩＤタグと情報システムにおけるサブＩＤおよび部分サブＩＤの配置
【図９】ＲＦＩＤタグとサービスシステムの間の、ハッシュ関数を用いた識別方法の手順
【符号の説明】
【０１５０】
１a〜１ｃ ユーザ
２ａ〜２ｃ 各ユーザが持つＩＤデバイス
３ａ〜３ｃ サービスシステム
４ａ〜４ｃ 各サービスシステムが持つリーダ（ＩＤデバイス読み取り機）
５ａ〜５ｃ 各サービスシステムが持つ情報システム
６ａ〜６ｃ 各サービスシステムが持つデータベースシステム
７a〜７ｂ ユーザ
８ａ〜８ｄ 各ユーザが持つ物品
９ａ〜９ｄ 各物品につけられたＲＦＩＤタグ
１０ａ〜１０ｃ サービスシステム
１１ａ〜１１ｃ 各サービスシステムが持つリーダ（ＩＤデバイス読み取り機）
１２ａ〜１２ｃ 各サービスシステムが持つ情報システム
１３ａ〜１３ｃ 各サービスシステムが持つデータベースシステム
１４ ＩＣカード
１５ ハッシュ装置や乱数生成装置をもつ暗号計算部
１６ 計算を行う論理計算部
１７ 無線通信部
１９ データを格納する不揮発性メモリ
１８ ユーザＩＤを格納するＲＯＭ領域
２０ アンテナからの波形を電力に変える電力供給部
２１ 無線によって外部と通信を行うためのアンテナ
２２ ＲＦＩＤタグ
２３ ハッシュ装置や乱数生成装置をもつ暗号計算部
２４ 計算を行う論理計算部、２５は無線通信部
２６ ユーザＩＤを格納するＲＯＭ領域
２７ アンテナからの波形を電力に変える電力供給部
２８ 無線によって外部と通信を行うためのアンテナである。
２９ａ〜２９ｃ ＩＣカードにそれぞれ保持されるユーザＩＤ
３０ａ〜３０ｃ、各ユーザＩＤのサービスシステム１に対するサブＩＤ、
３１ａ〜３１ｂ サービスシステム、
３２ａ〜３２ｃ 各ユーザＩＤのサービスシステム１に対するサブＩＤ、
３２ｄ〜３２ｆ 各ユーザＩＤのサービスシステム１に対するサブＩＤ
３３ 情報システムにおけるサブＩＤ情報
３４ ＩＤ(i)[1]、
３５ ＩＤ(i)[2]
３６ ＩＤ(i)[3]、
３７ ＩＤ(i)[4]、
３８ ＩＤ(i)[5]、
３９ａ〜３９ｇ 根から葉に向かって進んで行った場合の各ラベルを集めたサブＩＤ
４０ａ〜４０ｃ 各ＲＦＩＤタグにおける、１つのサービスシステムに対するサブＩＤ
【技術分野】
【０００１】
本発明は、ＲＦＩＤ（Radio Frequency Identification）タグやＩＣカード、携帯電話といったＩＤデバイスのセキュリティおよび、個人情報保護、リンク不能性、認証、識別に関する。
【背景技術】
【０００２】
現在、ＩＣカードやＲＦＩＤタグ、携帯電話といった小型のデバイスが物品や利用者に与えられ、種々のサービスを利用者が享受する際に、これらのデバイスとサービス機器の間の近距離通信により物品や利用者を識別することが多くなってきている。
【０００３】
ＩＣカードは、サービス機器と、接触あるいは非接触の状態で通信をおこなうことのできるカード形状のデバイスであり、内部にアンテナをはじめ、計算能力をもつプロセッサや通信が終わっても記憶をつづけることができる不揮発性メモリを持つ。
【０００４】
ＲＦＩＤタグは、サービス機器と、非接触の状態で通信をおこなうことのできる小型のデバイスであり、内部にアンテナをはじめ、計算能力をもつプロセッサや通信が終わっても記憶をつづけることができる不揮発性メモリを持つ。
【０００５】
これらのデバイスは、他のデバイスと区別して識別されるように、サービスの中で唯一の識別子（ＩＤ）を保持する。
【０００６】
そこで、これらＩＤを持つデバイスはＩＤデバイスと呼ばれる。
【０００７】
しかし、これらＩＤは、その利用者が気づかないうちに任意の第3者に読み取られてしまう可能性があり、その結果ＩＤデバイスの位置や、ＩＤに関連する個人情報が漏洩してしまうという問題が発生する。
【０００８】
特に、複数のＩＤデバイスの識別の履歴の中から、１つのＩＤデバイスについての履歴を第3者が選別し知ることができてしまうというリンク可能性の問題がある。
【０００９】
リンク可能性の問題は、利用者の名前や住所といった個人に関する情報を知らなくても、第3者にとって目の前にいる人の行動履歴を知ることができてしまうというように、個人情報が脅かされる問題である。
【００１０】
リンク可能性の問題は、ＩＤを単純に暗号化して識別に用いるだけでは解決できないという意味で、通常の個人情報の保護よりも難しい問題である。
【００１１】
これをふまえて、ＩＤを識別する際に、乱数などの毎回変化する値をＩＤの暗号化の際の入力に加えて、第3者にとっては毎回異なる値が得られるような方式が提案された（特許文献１）。
【００１２】
一方、世の中に情報サービスが普及するにつれ、ＩＣカードを利用者がたくさん保持することが多くなり、1枚のＩＣカードを複数のサービスのＩＤデバイスとして用いる要求が大きくなってきた。
【００１３】
また、物品につけられるＲＦＩＤタグに関しても、物品のライフサイクルの複数の場面で異なる目的に用いられることが望まれており、この場合も1つのＩＤデバイスを複数のサービスに用いるという要求と合致する。
【００１４】
しかし、1つのＩＤデバイスが多数のサービスに用いられるようになればなるほど、そのＩＤがサービスやＩＤデバイスから漏洩した際の被害は大きくなる。
【００１５】
リンク可能性の問題も同様に増大し、個人の行動を常に追跡する恐れが大きくなる。
【００１６】
そこで、ＩＤデバイスに与えられるＩＤの一部を抽出して与えられるサブＩＤを個々のサービスのために用い、別のサービスにはＩＤの別の一部を抽出して与えられる別のサブＩＤを用いることにより、被害の拡大を防ぐ方法が提案された（非特許文献1、特許文献2）。
【００１７】
【非特許文献１】Stephen A。 Weis他著 鉄ecurity and Privacy Aspects of Low-Cost Radio Frequency Identification Systems煤ASpringer Verlag社、「Security in Pervasive Computing」、Lecture Notes in Computer Science、Volume 2802、201-212ページ、2003年
【特許文献１】特開２００４−３１７７６４号公報
【特許文献２】特開２００４−１９２４８７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
以上説明したように、多サービスを実現するＩＤデバイスにおいては、複数のＩＤデバイスの識別の履歴の中から、１つのＩＤデバイスについての履歴を第3者が選別し知ることができないことを保証するというリンク不能性を達成することが重要である。
【００１９】
非特許文献1と特許文献1は、ＩＤを識別する際に、毎回変化する値とともにＩＤを暗号化することにより、第3者にとっては毎回異なる値が得られるようにすることにより第3者に対するリンク不能性を実現する方法である。
【００２０】
しかし、多サービスの環境においては、第3者には、第2者となるサービス以外のサービス（第3者サービス）も含まれる。
【００２１】
非特許文献1や特許文献1はこのような多サービスを想定していないために、第2者サービスと第3者サービスの区別をすることができない。
【００２２】
この結果、サービスの資格を持たない者に対するリンク不能性は実現できても、サービスの資格を持つ第3者に対するリンク不能性は実現できない。
【００２３】
また、特許文献2は多サービスを志向しているものの、ＩＤデバイスの識別の方式については記述がないため、リンク不能性は実現できていない。
【００２４】
本発明は、多サービスが可能なＩＤデバイスにおいて、第2者サービスにのみリンク可能性を許し、第3者サービスを含むそれ以外の者にはリンク不能性を保証するようなＩＤの識別の方式を提供することを目的とする。
【００２５】
また本発明は、上記のような第2者サービスにのみリンク可能性を許す識別の際に、ＩＤデバイスとサービスが相互に安全に認証をおこなう方式を提供することを目的とする。
【００２６】
さらに本発明は、上記のような第2者サービスにのみリンク可能性を許す識別および認証の際に問題となる、処理時間の長大化を抑え高速化する方式を提供することを目的とする。
【課題を解決するための手段】
【００２７】
この目的を達成するために、本発明の識別方法は、ＩＤデバイスとサービスシステムがユーザＩＤやサブＩＤをそのままの値でやりとりすることなく前記サービスシステムが前記サブＩＤを識別し、他サービスシステムにはサブＩＤを識別させないことを特徴とし、これを実現するために、複数のユーザと、前記ユーザそれぞれが保有するＩＤデバイスと、前記ＩＤデバイスに唯一に与えられるユーザＩＤと、前記ユーザＩＤの一部を抽出して与えられるサブＩＤと、前記サブＩＤを用いてユーザを識別するサービスシステムと、前記サービスシステムが持つ複数の前記ユーザに対するサブＩＤリストと、前記ユーザＩＤの前記サブＩＤ以外の一部を抽出して与えられる他サブＩＤを用いて前記ユーザを識別する複数の他サービスシステムと、前記他サービスシステムそれぞれがもつ複数の前記ユーザに対する他サブＩＤリストと、前記サービスシステムに唯一に与えられるサービスＩＤを備えるように構成する。
【００２８】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を達成できる。
【００２９】
このように構成される本発明の識別方法は、以下に説明する６つの構成にしたがって、ＩＤデバイスの識別におけるリンク不能性を達成する。
【００３０】
第1の構成として、前記サービスシステムが、前記サービス乱数発生装置を用いてサービス乱数を生成し、前記サービスシステムが、前記サービスＩＤと前記サービス乱数を前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが、前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが、前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記サービス乱数と前記サブＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数とともに前記サービスシステムに渡し、その後、前記サービスシステムが前記サービスハッシュ装置および前記サービス乱数、前記ユーザ乱数および自己がもつ前記サブＩＤリストを用いて前記ユーザハッシュ値に対応する前記サブＩＤを検索することによりＩＤデバイスを識別するように処理する。
【００３１】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を達成できる。
【００３２】
第2の構成として、前記サービスシステムが、前記サービス乱数発生装置を用いてサービス乱数を生成し、前記サービスシステムが、前記サービスＩＤと前記サービス乱数を前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記公開鍵と前記公開鍵暗号化装置を用いて前記ユーザ乱数と前記サービス乱数と前記サブＩＤとを暗号化した暗号値を前記サービスシステムに渡し、その後、前記サービスシステムが前記秘密鍵と前記公開鍵復号化装置を用いて前記暗号値を前記サブＩＤに復号化することによりＩＤデバイスを識別するように処理する。
【００３３】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を達成できる。
【００３４】
第3の構成として、前記サービスシステムが、前記サービスＩＤを前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記ユーザＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数および前期グループＩＤとともに前記サービスシステムに渡し、その後、前記サービスシステムが前記グループＩＤと前記グループＩＤリストを元に前記ＩＤデバイスが属するグループを特定し、その後、前記サービスシステムが前記サービスハッシュ装置と前期ユーザ乱数および自己がもつ前記ユーザＩＤリストを用いて前記ユーザハッシュ値に対応する前記ユーザＩＤを前記グループに属するユーザの中から検索することによりＩＤデバイスを識別するように処理する。
【００３５】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を一定のレベルで達成できるのと同時に、サービスシステム側で必要なサブＩＤリストの検索処理を高速化することができる。
【００３６】
第4の構成として、前記サービスシステムが、前記サービスＩＤを前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置を用いて前記ユーザ乱数とひとつの前記部分サブＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数とともに前記サービスシステムに渡すという部分サブＩＤ開示処理を実行し、その後、前記サービスシステムが前記サービスハッシュ装置と前期ユーザ乱数および自己がもつ前記ユーザＩＤリストを用いて前記ユーザハッシュ値に対応する複数の前記ユーザＩＤを絞り込むというサブＩＤ絞込み処理を実行し、その後、サブＩＤが1つに絞り込まれるまで前記部分サブＩＤ開示処理と前記サブＩＤ絞込み処理を繰り返すことによりＩＤデバイスを識別するように処理する。
【００３７】
これにより、ユーザや第2者サービスシステム以外の者にとっては、識別において発生する通信を盗み見たとしてもサブＩＤを知ることができず、第３者サービスシステムや第３者に対するリンク不能性を最大のレベルまで達成できるのと同時に、サービスシステム側で必要なサブＩＤリストの検索処理を高速化することができる。
【００３８】
第5の構成として、第3または4の構成に加えて、すべての前記ユーザについての前記ユーザＩＤと前記サブＩＤが一致するようにサブＩＤを抽出し、すべての前記サービスの前記サービスＩＤが空値を含む固定値であるように構成する。
【００３９】
これにより、多サービス環境だけでなく、従来からの1つのサービスの環境においてリンク不能性が求められる場合においても、リンク不能性の達成を行いながらサービスシステム側で必要なサブＩＤリストの検索処理を高速化することができる。
【００４０】
第6の構成として、前記第1〜5のいずれかの構成に加え、前記サービスシステムと前記ＩＤデバイスが相互に認証するように構成する。
【００４１】
これにより、リンク不能性の達成を行いながらのＩＤデバイスの識別と同時に、リンク不能性の達成を行いながらのＩＤデバイスとサービスシステムの間の相互認証が可能になる。
【００４２】
第6の構成は、以下に説明する2つの構成に従って、リンク不能性を保ったままでのＩＤデバイスとサービスシステムの間の相互認証を実現する。
【００４３】
第6aの構成として、第1〜5のいずれかの構成に加え、前記サービスシステムが前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記サブＩＤをハッシュ変換したサービスハッシュ値を前記ＩＤデバイスに渡し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置と前記サービス乱数および自己が持つ前記サブＩＤを用いて前記サービスハッシュ値が前期ユーザＩＤに対応するかを確認し、対応すれば前期ＩＤデバイスが前記サービスシステムを正しいサービスシステムであると認証することによって相互認証を実現するように処理する。
【００４４】
これにより、リンク不能性を保ったままでのＩＤデバイスとサービスシステムの間の相互認証が実現できる。
【００４５】
第6aの構成として、第1〜5のいずれかの構成に加え、前記サービスシステムが前記公開鍵と前記公開鍵暗号化装置を用いて前記サービス乱数と前記サブＩＤを暗号化したサービス暗号値を前記ＩＤデバイスに渡し、その後、前記ＩＤデバイスが前記ユーザ秘密鍵と前記ユーザ公開鍵復号化装置を前記サービス暗号値を復号化し、これが前記サブＩＤに一致すれば前期ＩＤデバイスが前記サービスシステムを正しいサービスシステムであると認証することによって相互認証を実現するように処理する。
【００４６】
これにより、リンク不能性を保ったままでのＩＤデバイスとサービスシステムの間の相互認証が実現できる。
【発明の効果】
【００４７】
本発明の識別方法によれば、ＩＤデバイスは第２者サービスシステムにのみ識別させ、第３者サービスシステムや第３者に対しては識別させることがない。
【００４８】
ＩＤデバイスは、第２者サービスシステムからサービスＩＤを受け取った後で第２者サービスシステムにのみ識別できる値をもちいて識別に必要な値を出力するため、第２者サービスシステム以外にはＩＤデバイスが毎回異なる値を出しているように見え、複数のＩＤデバイスの識別の履歴を元に、同一のＩＤデバイスの履歴を抽出することができず、リンク不能性を達成することができる。
【００４９】
また本発明の相互認証方法によれば、ＩＤデバイスを第２者サービスシステムにのみ識別させながら相互認証をすることができる。
【００５０】
ＩＤデバイスと第２者サービスシステムの間で、識別に必要な値も暗号化またはハッシュかしながら相互認証を行うため、第２者サービスシステム以外の者に対するリンク不能性を保障しながら相互認証を行うことができる。
【発明を実施するための最良の形態】
【００５１】
A||Bは、AとBという2つの情報の結合を表す。情報の結合としては、2つの情報を単に連接する方法や2つの情報の排他的論理和をとる方法などがある。
【００５２】
H(A)は、Aという情報を一方向性ハッシュ関数によって変換したハッシュ値を表す。
【００５３】
一般に一方向性ハッシュ関数は、任意長の入力に対応することを求められるが、本発明で用いる一方向性ハッシュ関数は、固定長の入力にのみ対応するものも含む。
【００５４】
(実施の形態1)
本発明の実施例1を説明する。
【００５５】
本実施例において、ＩＤデバイスとして非接触ＩＣカードを想定する。
【００５６】
図１にＩＤデバイスを用いたサービスシステムの一例を図示する。
【００５７】
図１において、１a〜１ｃはユーザ、２ａ〜２ｃは各ユーザが持つＩＤデバイス、３ａ〜３ｃはサービスシステム、４ａ〜４ｃは各サービスシステムが持つリーダ（ＩＤデバイス読み取り機）、５ａ〜５ｃは各サービスシステムが持つ情報システム、６ａ〜６ｃは各サービスシステムが持つデータベースシステムである。
【００５８】
図２は、ＩＣカードの構成である。
【００５９】
図２において、１４はＩＣカード、１５はハッシュ装置や乱数生成装置をもつ暗号計算部、１６は計算を行う論理計算部、１７は無線通信部、１９はデータを格納する不揮発性メモリ、１８はユーザＩＤを格納するＲＯＭ領域、２０はアンテナからの波形を電力に変える電力供給部、２１は無線によって外部と通信を行うためのアンテナである。
【００６０】
本発明のＩＣカードでは、サービスＩＤから対応するサービスシステムのサブＩＤの先頭アドレスと終端アドレスを取り出すための関数f、ハッシュ装置、乱数発生装置を有するものとする。
【００６１】
関数fの例としては、サブＩＤの先頭アドレスとして「サービスＩＤ×サブＩＤの長さ」を、終端アドレスとして「(サービスＩＤ+1)×サブＩＤの長さ-1」を出力する関数が考えられる。
【００６２】
また関数fとして、あらかじめサービスＩＤとそのサービスシステムのサブＩＤのアドレスをＲＯＭに記録してあるルックアップテーブルを用いることも考えられる。
【００６３】
図３は、ユーザとサービスシステムにおけるサブＩＤの配置である。
【００６４】
図３において、２９ａ〜２９ｃはＩＣカードにそれぞれ保持されるユーザＩＤ、３０ａ〜３０ｃは、各ユーザＩＤのサービスシステム１に対するサブＩＤ、３１ａ〜３１ｂはサービスシステム、３２ａ〜３２ｃは各ユーザＩＤのサービスシステム１に対するサブＩＤ、３２ｄ〜３２ｆは各ユーザＩＤのサービスシステム１に対するサブＩＤである。
【００６５】
ハッシュ装置に実装されるハッシュ関数として、SHA(Secure Hash Algorithm)-256やSHA-512、MD5などを用いることができる。
【００６６】
サービスシステムの情報システムは、ＩＣカードの発行機関から発行されたサービスを提供する全ユーザに対応するサブＩＤをデータベースに保存しておく。
【００６７】
また、ＩＣカードの発行機関から発行された当該サービスシステムを特定するためのサービスＩＤをデータベースに保存しておく。
【００６８】
図４は、ＩＣカードとサービスシステムの間の、ハッシュ関数を用いた識別方法の手順である。
【００６９】
ＩＣカードが接近したことを感知したリーダは、乱数発生装置によって乱数Rsを生成し（Ｓｔｅｐ１５）、データベースに保存されているサービスＩＤの取り出し（Ｓｔｅｐ１６）を行う。
【００７０】
情報システムは、リーダを通じて乱数RsとサービスＩＤをＩＣカードに送信する（Ｓｔｅｐ１７）。
【００７１】
乱数Rsは、情報システムのメモリに保存される。
【００７２】
リーダからサービスＩＤを受け取った（Ｓｔｅｐ２）ＩＣカードは、関数fにより当該サービスＩＤに対応するサービスシステムのサブＩＤの先頭アドレスと終端アドレスを取り出す（Ｓｔｅｐ４）。
【００７３】
ＩＣカードは、取り出されたアドレスを指定することにより、ユーザＩＤを格納するＲＯＭ領域からサブＩＤを取り出す（Ｓｔｅｐ５）。
【００７４】
ＩＣカードは、乱数発生装置によって乱数Ruを生成し（Ｓｔｅｐ３）、サブＩＤと乱数Rsと乱数Ruのデータを結合する。
【００７５】
ＩＣカードは、乱数Rsと乱数RuとサブＩＤ SIDの結合データをハッシュ装置によって、ハッシュ値に変換し（Ｓｔｅｐ６）、ハッシュ値Hu=H(Rs || Ru || SID)と乱数Ruをリーダを通じて情報システムに送付する（Ｓｔｅｐ７）（Ｓｔｅｐ１８）。
【００７６】
情報システムは、ＩＣカードから送付された乱数Ruとメモリに保持されている乱数Rsを用いて、H(Rs || Ru || SID)の計算をデータベースに含まれる全てのサブＩＤについて計算し、ＩＣカードから送られてきたハッシュ値Huと一致するものを検索する（Ｓｔｅｐ１９〜２１）。
【００７７】
ハッシュ値Huと一致するH(Rs || Ru || SID)に対応するサブＩＤが、ＩＣカードのＩＤとなる。対応するサブＩＤが見つからなかった場合、情報システムはプロトコルを終了する（Ｓｔｅｐ２５）。
【００７８】
情報システムは、サブＩＤとＩＣカードから送信された乱数をハッシュ化したHs=H(SID || Ru)をリーダを通じてＩＣカードに送信する（Ｓｔｅｐ２２、２３、８）。
【００７９】
ＩＣカードは、リーダから送られてきたHsがH(SID || Ru)と一致するか検証する（Ｓｔｅｐ９）。
【００８０】
一致した場合、ＩＣカードはリーダに対して認証成功を伝える（Ｓｔｅｐ１０、１２、２３）。
【００８１】
一致しなかった場合、ＩＣカードはリーダに対して認証失敗を伝え（Ｓｔｅｐ１１、１２、２３）、認証プロトコルを終了する（Ｓｔｅｐ１３）。
【００８２】
認証が成功した場合、ＩＣカードと情報システムの間で各種サービスが行われる。
【００８３】
小売店におけるポイントサービスやマーケティングシステムを考える。
【００８４】
小売店は、商品の購入時にＩＣカードの提示を客に求めることにより、その客が購入した商品の情報をサブＩＤをもとに紐付けしていくことが可能となる。よって、小売店は紐付けされた商品情報に客ごとの購入パターンを分析することができ、マーケティングに生かすことができる利点がある。また、小売店が客の購入金額に応じたポイントをサブＩＤを元に累算していくことにより、客は累積ポイント数に応じた買い物をできるという利点がある。
【００８５】
図４は、ＩＣカードとサービスシステムの間の、ハッシュ装置を用いたＩＤの識別方法の手順である。
【００８６】
ＩＣカードが接近したことを感知したリーダは、乱数発生装置によって乱数Rsを生成し（Ｓｔｅｐ１５）、データベースに保存されているサービスＩＤの取り出し（Ｓｔｅｐ１６）を行う。
【００８７】
情報システムは、リーダを通じて乱数RsとサービスＩＤをＩＣカードに送信する（Ｓｔｅｐ１７）。
【００８８】
乱数Rsは、情報システムのメモリに保存される。
【００８９】
リーダからサービスＩＤを受け取った（Ｓｔｅｐ２）ＩＣカードは、関数fにより当該サービスＩＤに対応するサービスシステムのサブＩＤの先頭アドレスと終端アドレスを取り出す（Ｓｔｅｐ４）。
【００９０】
ＩＣカードは、取り出されたアドレスを指定することにより、ユーザＩＤを格納するＲＯＭ領域からサブＩＤを取り出す（Ｓｔｅｐ５）。
【００９１】
ＩＣカードは、乱数発生装置によって乱数Ruを生成し（Ｓｔｅｐ３）、サブＩＤと乱数Rsと乱数Ruのデータを結合する。
【００９２】
ＩＣカードは、乱数Rsと乱数RuとサブＩＤの結合データをハッシュ装置によって、ハッシュ値に変換し（Ｓｔｅｐ６）、ハッシュ値Hu=H(Rs || Ru || SID)と乱数Ruをリーダを通じて情報システムに送付する（Ｓｔｅｐ７）（Ｓｔｅｐ１８）。
【００９３】
情報システムは、ＩＣカードから送付された乱数Ruとメモリに保持されている乱数Rsを用いて、H(Rs || Ru || SID)の計算をデータベースに含まれる全てのサブＩＤについて計算し、ＩＣカードから送られてきたハッシュ値Huと一致するものを検索する（Ｓｔｅｐ１９〜２１）。
【００９４】
ハッシュ値Huと一致するH(Rs || Ru || SID)に対応するサブＩＤが、ＩＣカードのＩＤとなる。対応するサブＩＤが見つからなかった場合、情報システムはプロトコルを終了する（Ｓｔｅｐ２５）。
【００９５】
情報システムは、サブＩＤとＩＣカードから送信された乱数をハッシュ化したHs=H(SID || Ru)をリーダを通じてＩＣカードに送信する（Ｓｔｅｐ２２、２３、８）。
【００９６】
ＩＣカードは、リーダから送られてきたHsがH(SID || Ru)と一致するか検証する（Ｓｔｅｐ９）。
【００９７】
一致した場合、ＩＣカードはリーダに対して認証成功を伝える（Ｓｔｅｐ１０、１２、２３）。
【００９８】
一致しなかった場合、ＩＣカードはリーダに対して認証失敗を伝え（Ｓｔｅｐ１１、１２、２３）、認証プロトコルを終了する（Ｓｔｅｐ１３）。
【００９９】
認証が成功した場合、ＩＣカードと情報システムの間で各種サービスが行われる。
【０１００】
建物の入退出管理である場合を考える。
【０１０１】
建物のドアにはリーダが取り付けられている。取り出されたサブＩＤにより、ユーザが部屋のドアを開閉する権限を有するかを判定できる。
【０１０２】
また、ＩＣカードのメモリに、ＩＣカードを保有するユーザの生体情報、例えば指紋情報や目の虹彩情報が格納されているものとする。
【０１０３】
認証成功後、ＩＣカードのメモリにある生体情報へのアクセスが許可され、情報システムは生体情報を取り出す。情報システムには生体情報読取装置、例えば指紋読み取り器や虹彩読み取り器が接続されており、ユーザは生体情報読み取り機に指紋や虹彩などを読み取らせる。
【０１０４】
カード内の生体情報と生体情報読み取り機からの情報を比較することにより、情報システムは認証者が正規のＩＣカードの持ち主であることを確認できる。
【０１０５】
カード内に生体情報が格納されているため、情報システム側でユーザの個人情報である生体情報を管理する必要がない。
【０１０６】
また、識別方法には公開鍵暗号を用いた手法も可能である。
【０１０７】
図５は、ＩＣカードとサービスシステムの間の、公開鍵暗号を用いた識別方法の手順である。
【０１０８】
ＩＣカードが接近したことを感知したリーダは、乱数発生装置によって乱数Rsを生成し（Ｓｔｅｐ１５）、データベースに保存されているサービスＩＤの取り出し（Ｓｔｅｐ１６）を行う。
【０１０９】
情報システムは、リーダを通じて乱数RsとサービスＩＤをＩＣカードに送信する（Ｓｔｅｐ１７）。
【０１１０】
乱数Rsは、情報システムのメモリに保存される。
【０１１１】
リーダからサービスＩＤを受け取った（Ｓｔｅｐ２）ＩＣカードは、関数fにより当該サービスＩＤに対応するサービスシステムのサブＩＤの先頭アドレスと終端アドレスを取り出す（Ｓｔｅｐ４）。
【０１１２】
ＩＣカードは、取り出されたアドレスを指定することにより、ユーザＩＤを格納するＲＯＭ領域からサブＩＤを取り出す（Ｓｔｅｐ５）。
【０１１３】
ＩＣカードは、乱数発生装置によって乱数Ruを生成し（Ｓｔｅｐ３）、サブＩＤと乱数Rsと乱数Ruのデータを結合する。
【０１１４】
ＩＣカードは、乱数Rsと乱数RuとサブＩＤ SIDの結合データを公開鍵暗号化装置Ｅによって、暗号値に変換し（Ｓｔｅｐ６）、暗号値Eu=Ｅ(Rs || Ru || SID)と乱数Ruをリーダを通じて情報システムに送付する（Ｓｔｅｐ７）（Ｓｔｅｐ１８）。
【０１１５】
情報システムは、ＩＣカードから送付された乱数Ruとメモリに保持されている乱数Rsを用いて、Ｅ(Rs || Ru || SID)を復号化しサブID SIDとRsとRuを得る（Ｓｔｅｐ１９）。
【０１１６】
対応するサブＩＤがサブＩＤリストに見つからなかった場合、情報システムはプロトコルを終了する（Ｓｔｅｐ２０、２６）。
【０１１７】
情報システムは、Rsがもとの値と同じであることを確認し（Ｓｔｅｐ２１）、同じでなければプロトコルを終了する（Ｓｔｅｐ２６）。
【０１１８】
サブＩＤとＩＣカードから送信された乱数を暗号化したEs=Ｅ(SID || Ru)をリーダを通じてＩＣカードに送信する（Ｓｔｅｐ２２、２３、８）。
【０１１９】
ＩＣカードは、リーダから送られてきたEsがＥ(SID || Ru)と一致するか検証する（Ｓｔｅｐ９）。
【０１２０】
一致した場合、ＩＣカードはリーダに対して認証成功を伝える（Ｓｔｅｐ１０、１２、２４）。
【０１２１】
一致しなかった場合、ＩＣカードはリーダに対して認証失敗を伝え（Ｓｔｅｐ１１、１２、２４）、認証プロトコルを終了する（Ｓｔｅｐ１３）。
【０１２２】
認証が成功した場合、ＩＣカードと情報システムの間で各種サービスが行われる。
(実施の形態2)
本発明の実施例2を説明する。
【０１２３】
図６にＩＤデバイスを用いたサービスシステムの一例を図示する。
【０１２４】
本実施例において、ＩＤデバイスとしてＲＦＩＤタグを想定する。
【０１２５】
図６において、７a〜７ｂはユーザ、８ａ〜８ｄは各ユーザが持つ物品、９ａ〜９ｄは各物品につけられたＲＦＩＤタグ、１０ａ〜１０ｃはサービスシステム、１１ａ〜１１ｃは各サービスシステムが持つリーダ（ＩＤデバイス読み取り機）、１２ａ〜１２ｃは各サービスシステムが持つ情報システム、１３ａ〜１３ｃは各サービスシステムが持つデータベースシステムである。
【０１２６】
図７は、ＲＦＩＤタグの構成である。
【０１２７】
図７において、２２はＲＦＩＤタグ、 ２３はハッシュ装置や乱数生成装置をもつ暗号計算部、２４は計算を行う論理計算部、２５は無線通信部、２６はユーザＩＤを格納するＲＯＭ領域、２７はアンテナからの波形を電力に変える電力供給部、２８は無線によって外部と通信を行うためのアンテナである。
【０１２８】
情報システムには、データベースがあり、情報システムがシステム内における全ＲＦＩＤタグに格納されたサブＩＤ情報が格納される。
【０１２９】
システムで用いられるサブＩＤの作成方法は次の通りである。
【０１３０】
深さKのラベル付き木(labeled tree)を考える(図８参照)。
【０１３１】
木はN個の葉を持ち、各葉が各ＲＦＩＤタグi(1<=i<=N)に対応している。
【０１３２】
ある同じ親を持つ子達には、それぞれユニークなラベルが付けられる。
【０１３３】
根から葉に向かって進んで行った場合の各ラベルを集めたものが、その葉の持つサブＩＤであり、対応する各ＲＦＩＤタグiに付与される。
【０１３４】
また、ＲＦＩＤタグiのk(1<=k<=s(i))番目のラベルをＩＤ(i)[k]と表記する。
【０１３５】
各接点につけられたラベルが部分サブＩＤに相当する。
【０１３６】
図８は、ＲＦＩＤタグと情報システムにおけるサブＩＤおよび部分サブＩＤの配置である。
【０１３７】
図８において、４０ａ〜４０ｃは、各ＲＦＩＤタグにおける、１つのサービスシステムに対するサブＩＤ、３３は情報システムにおけるサブＩＤ情報、 ３４はＩＤ(i)[1]、３５はＩＤ(i)[2]、３６はＩＤ(i)[3]、３７はＩＤ(i)[4]、３８はＩＤ(i)[5]、３９ａ〜３９ｇは根から葉に向かって進んで行った場合の各ラベルを集めたサブＩＤである。
【０１３８】
ただしここではＩＤ(i)[k]においてkは１〜５の値であるが、実際にはもっと多くても少なくてもよい。
【０１３９】
ただし、S(i)はＲＦＩＤタグiに対応する葉の深さであり、1<=S(i)<=Kである。
【０１４０】
情報システムはラベル付き木を木構造のまま保存しておく。
【０１４１】
図９は、ＲＦＩＤタグとサービスシステムの間のＩＤの識別方法の手順である。
【０１４２】
ＲＦＩＤタグがリーダの通信圏内に入ると、ＲＦＩＤタグは乱数Rを生成する（Ｓｔｅｐ２）。
【０１４３】
ＲＦＩＤタグは、各部分サブＩＤについて、Hu[k]=H(ＩＤ_{i}[k] || R) (1<=k<=S(i))を計算し（Ｓｔｅｐ３、４、５）、乱数Rと各部分サブＩＤに対応するハッシュ値(Hu[1]、Hu[2]、・・・、Hu[S(i)])の組を情報システムに送信する。
【０１４４】
なお、S(i)<Kの場合は、(Hu[1]、Hu[2]、・・・、Hu[S(i)])に代えて、Hu[l] (S(i)+1<=l<=K)として乱数をパディングした(Hu[1]、Hu[2]、・・・、Hu[S(i)]、Hu[S(i)+1]、・・・、Hu[K])を情報システムに送信する（Ｓｔｅｐ６、７、８）ことにより、Huの個数の違いによって、第三者に対するリンク不能性が悪化することを防止できる。
【０１４５】
サービスシステムは、RとHu[1]、Hu[2]、・・・、Hu[K]を受け取るとＳｔｅｐ１２〜２３の手順で処理する。
【０１４６】
認証が成功した場合、ＩＣカードと情報システムの間で各種サービスが行われる。
【０１４７】
任意のＲＦＩＤタグと情報システム間における可変ＩＤ情報のやりとりの頻度が、等しく同じであるならば、木構造を完全α分木、すなわち葉を除く各接点から出る枝の数がすべて等しく同じα本の木を構成することにより、情報システム側で必要なハッシュ計算の平均計算量を最小化することができる。
【０１４８】
すなわちK＝N^{1/K}、ただし、α=N^{1/K}である。
【図面の簡単な説明】
【０１４９】
【図１】ＩＤデバイスを用いたサービスシステム
【図２】ＩＣカードの構成
【図３】ユーザとサービスシステムにおけるサブＩＤの配置
【図４】ＩＣカードとサービスシステムの間の、ハッシュ関数を用いた識別方法の手順
【図５】ＩＣカードとサービスシステムの間の、公開鍵を用いたＩＤの識別方法の手順
【図６】ＲＦＩＤタグを用いたサービスシステム
【図７】ＲＦＩＤタグの構成
【図８】ＲＦＩＤタグと情報システムにおけるサブＩＤおよび部分サブＩＤの配置
【図９】ＲＦＩＤタグとサービスシステムの間の、ハッシュ関数を用いた識別方法の手順
【符号の説明】
【０１５０】
１a〜１ｃ ユーザ
２ａ〜２ｃ 各ユーザが持つＩＤデバイス
３ａ〜３ｃ サービスシステム
４ａ〜４ｃ 各サービスシステムが持つリーダ（ＩＤデバイス読み取り機）
５ａ〜５ｃ 各サービスシステムが持つ情報システム
６ａ〜６ｃ 各サービスシステムが持つデータベースシステム
７a〜７ｂ ユーザ
８ａ〜８ｄ 各ユーザが持つ物品
９ａ〜９ｄ 各物品につけられたＲＦＩＤタグ
１０ａ〜１０ｃ サービスシステム
１１ａ〜１１ｃ 各サービスシステムが持つリーダ（ＩＤデバイス読み取り機）
１２ａ〜１２ｃ 各サービスシステムが持つ情報システム
１３ａ〜１３ｃ 各サービスシステムが持つデータベースシステム
１４ ＩＣカード
１５ ハッシュ装置や乱数生成装置をもつ暗号計算部
１６ 計算を行う論理計算部
１７ 無線通信部
１９ データを格納する不揮発性メモリ
１８ ユーザＩＤを格納するＲＯＭ領域
２０ アンテナからの波形を電力に変える電力供給部
２１ 無線によって外部と通信を行うためのアンテナ
２２ ＲＦＩＤタグ
２３ ハッシュ装置や乱数生成装置をもつ暗号計算部
２４ 計算を行う論理計算部、２５は無線通信部
２６ ユーザＩＤを格納するＲＯＭ領域
２７ アンテナからの波形を電力に変える電力供給部
２８ 無線によって外部と通信を行うためのアンテナである。
２９ａ〜２９ｃ ＩＣカードにそれぞれ保持されるユーザＩＤ
３０ａ〜３０ｃ、各ユーザＩＤのサービスシステム１に対するサブＩＤ、
３１ａ〜３１ｂ サービスシステム、
３２ａ〜３２ｃ 各ユーザＩＤのサービスシステム１に対するサブＩＤ、
３２ｄ〜３２ｆ 各ユーザＩＤのサービスシステム１に対するサブＩＤ
３３ 情報システムにおけるサブＩＤ情報
３４ ＩＤ(i)[1]、
３５ ＩＤ(i)[2]
３６ ＩＤ(i)[3]、
３７ ＩＤ(i)[4]、
３８ ＩＤ(i)[5]、
３９ａ〜３９ｇ 根から葉に向かって進んで行った場合の各ラベルを集めたサブＩＤ
４０ａ〜４０ｃ 各ＲＦＩＤタグにおける、１つのサービスシステムに対するサブＩＤ
【特許請求の範囲】
【請求項１】
前記ユーザそれぞれが保有するＩＤデバイスと、前記ＩＤデバイスに唯一に与えられるユーザＩＤと、前記ユーザＩＤの一部を抽出して与えられるサブＩＤと、前記サブＩＤを用いてユーザを識別するサービスシステムと、前記サービスシステムが持つ複数の前記ユーザに対するサブＩＤリストと、前記ユーザＩＤの前記サブＩＤ以外の一部を抽出して与えられる他サブＩＤを用いて前記ユーザを識別する複数の他サービスシステムと、前記他サービスシステムそれぞれがもつ複数の前記ユーザに対する他サブＩＤリストと、前記サービスシステムに唯一に与えられるサービスＩＤと、を備えた識別方法において、前記ＩＤデバイスと前記サービスシステムが前記ユーザＩＤや前記サブＩＤをそのままの値でやりとりすることなく前記サービスシステムが前記サブＩＤを識別し、前記他サービスシステムには前記サブＩＤを識別させない、ことを特徴とする識別方法。
【請求項２】
前記ＩＤデバイスが、備え付けられたユーザハッシュ装置と、ユーザ乱数発生装置と、を備え、前記サービスシステムが、前記ユーザハッシュ装置と同じ入出力を持つサービスハッシュ装置と、サービス乱数発生装置と、を備え、前記サービスシステムが、前記サービス乱数発生装置を用いてサービス乱数を生成し、その後、前記サービスシステムが、前記サービスＩＤと前記サービス乱数を前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが、前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが、前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記サービス乱数と前記サブＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数とともに前記サービスシステムに渡し、その後、前記サービスシステムが前記サービスハッシュ装置および前記サービス乱数、前記ユーザ乱数および自己がもつ前記サブＩＤリストを用いて前記ユーザハッシュ値に対応する前記サブＩＤを検索することを特徴とする請求項１記載の識別方法。
【請求項３】
前記ＩＤデバイスが、ユーザ乱数発生装置と、公開鍵暗号化装置と、公開鍵と、前記サービスシステムが、サービス乱数発生装置と、秘密鍵と、公開鍵復号化装置と、を備え、前記サービスシステムが、前記サービス乱数発生装置を用いてサービス乱数を生成し、その後、前記サービスシステムが、前記サービスＩＤと前記サービス乱数を前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記公開鍵と前記公開鍵暗号化装置を用いて前記ユーザ乱数と前記サービス乱数と前記サブＩＤとを暗号化した暗号値を前記サービスシステムに渡し、その後、前記サービスシステムが前記秘密鍵と前記公開鍵復号化装置を用いて前記暗号値を前記サブＩＤに復号化することを特徴とする請求項１記載の識別方法。
【請求項４】
前記ＩＤデバイスが、複数の前記ユーザからなるグループに唯一に与えられるグループＩＤと、複数の前記ユーザに対するグループＩＤリストを備え、前記サービスシステムが、前記サービスＩＤを前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記ユーザＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数および前期グループＩＤとともに前記サービスシステムに渡し、その後、前記サービスシステムが前記グループＩＤと前記グループＩＤリストを元に前記ＩＤデバイスが属するグループを特定し、その後、前記サービスシステムが前記サービスハッシュ装置と前期ユーザ乱数および自己がもつ前記ユーザＩＤリストを用いて前記ユーザハッシュ値に対応する前記ユーザＩＤを前記グループに属するユーザの中から検索することを特徴とする請求項１記載の識別方法。
【請求項５】
前期ＩＤデバイスと前期サービスシステムが、前記サブＩＤから複数の部分列を前記サブＩＤについてのぬけがないように取り出して得られる複数の部分サブＩＤ、を備え、前記サービスシステムが、前記サービスＩＤを前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置を用いて前記ユーザ乱数とひとつの前記部分サブＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数とともに前記サービスシステムに渡すという部分サブＩＤ開示処理を実行し、その後、前記サービスシステムが前記サービスハッシュ装置と前期ユーザ乱数および自己がもつ前記ユーザＩＤリストを用いて前記ユーザハッシュ値に対応する複数の前記ユーザＩＤを絞り込むというサブＩＤ絞込み処理を実行し、その後、サブＩＤが1つに絞り込まれるまで前記部分サブＩＤ開示処理と前記サブＩＤ絞込み処理を繰り返すことを特徴とする請求項１記載の識別方法。
【請求項６】
すべての前記ユーザについての前記ユーザＩＤと前記サブＩＤが一致するようにサブＩＤを抽出し、すべての前記サービスの前記サービスＩＤが空値を含む固定値であることを特徴とする請求項１〜５のいずれかに記載の識別方法。
【請求項７】
前記サービスシステムと前記ＩＤデバイスが相互に認証することを特徴とする請求項１〜６のいずれかに記載の識別方法。
【請求項８】
前記システム乱数を空値することを特徴とする請求項１〜７のいずれかに記載の識別方法。
【請求項９】
前記サービスシステムが前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記サブＩＤをハッシュ変換したサービスハッシュ値を前記ＩＤデバイスに渡し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置と前記サービス乱数および自己が持つ前記サブＩＤを用いて前記サービスハッシュ値が前期ユーザＩＤに対応するかを確認し、対応すれば前期ＩＤデバイスが前記サービスシステムを正しいサービスシステムであると認証することを特徴とする請求項１〜８のいずれかに掲載の識別方法。
【請求項１０】
前記ＩＤデバイスが、ユーザ秘密鍵と、ユーザ公開鍵復号化装置と、前記サービスシステムが、公開鍵と、前記ユーザ公開鍵復号化装置に対応した公開鍵暗号化装置と、を備え、前記サービスシステムが前記公開鍵と前記公開鍵暗号化装置を用いて前記サービス乱数と前記サブＩＤを暗号化したサービス暗号値を前記ＩＤデバイスに渡し、その後、前記ＩＤデバイスが前記ユーザ秘密鍵と前記ユーザ公開鍵復号化装置を前記サービス暗号値を復号化し、これが前記サブＩＤに一致すれば前期ＩＤデバイスが前記サービスシステムを正しいサービスシステムであると認証することを特徴とする請求項１〜９に記載の識別方法。
【請求項１】
前記ユーザそれぞれが保有するＩＤデバイスと、前記ＩＤデバイスに唯一に与えられるユーザＩＤと、前記ユーザＩＤの一部を抽出して与えられるサブＩＤと、前記サブＩＤを用いてユーザを識別するサービスシステムと、前記サービスシステムが持つ複数の前記ユーザに対するサブＩＤリストと、前記ユーザＩＤの前記サブＩＤ以外の一部を抽出して与えられる他サブＩＤを用いて前記ユーザを識別する複数の他サービスシステムと、前記他サービスシステムそれぞれがもつ複数の前記ユーザに対する他サブＩＤリストと、前記サービスシステムに唯一に与えられるサービスＩＤと、を備えた識別方法において、前記ＩＤデバイスと前記サービスシステムが前記ユーザＩＤや前記サブＩＤをそのままの値でやりとりすることなく前記サービスシステムが前記サブＩＤを識別し、前記他サービスシステムには前記サブＩＤを識別させない、ことを特徴とする識別方法。
【請求項２】
前記ＩＤデバイスが、備え付けられたユーザハッシュ装置と、ユーザ乱数発生装置と、を備え、前記サービスシステムが、前記ユーザハッシュ装置と同じ入出力を持つサービスハッシュ装置と、サービス乱数発生装置と、を備え、前記サービスシステムが、前記サービス乱数発生装置を用いてサービス乱数を生成し、その後、前記サービスシステムが、前記サービスＩＤと前記サービス乱数を前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが、前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが、前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記サービス乱数と前記サブＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数とともに前記サービスシステムに渡し、その後、前記サービスシステムが前記サービスハッシュ装置および前記サービス乱数、前記ユーザ乱数および自己がもつ前記サブＩＤリストを用いて前記ユーザハッシュ値に対応する前記サブＩＤを検索することを特徴とする請求項１記載の識別方法。
【請求項３】
前記ＩＤデバイスが、ユーザ乱数発生装置と、公開鍵暗号化装置と、公開鍵と、前記サービスシステムが、サービス乱数発生装置と、秘密鍵と、公開鍵復号化装置と、を備え、前記サービスシステムが、前記サービス乱数発生装置を用いてサービス乱数を生成し、その後、前記サービスシステムが、前記サービスＩＤと前記サービス乱数を前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記公開鍵と前記公開鍵暗号化装置を用いて前記ユーザ乱数と前記サービス乱数と前記サブＩＤとを暗号化した暗号値を前記サービスシステムに渡し、その後、前記サービスシステムが前記秘密鍵と前記公開鍵復号化装置を用いて前記暗号値を前記サブＩＤに復号化することを特徴とする請求項１記載の識別方法。
【請求項４】
前記ＩＤデバイスが、複数の前記ユーザからなるグループに唯一に与えられるグループＩＤと、複数の前記ユーザに対するグループＩＤリストを備え、前記サービスシステムが、前記サービスＩＤを前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記ユーザＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数および前期グループＩＤとともに前記サービスシステムに渡し、その後、前記サービスシステムが前記グループＩＤと前記グループＩＤリストを元に前記ＩＤデバイスが属するグループを特定し、その後、前記サービスシステムが前記サービスハッシュ装置と前期ユーザ乱数および自己がもつ前記ユーザＩＤリストを用いて前記ユーザハッシュ値に対応する前記ユーザＩＤを前記グループに属するユーザの中から検索することを特徴とする請求項１記載の識別方法。
【請求項５】
前期ＩＤデバイスと前期サービスシステムが、前記サブＩＤから複数の部分列を前記サブＩＤについてのぬけがないように取り出して得られる複数の部分サブＩＤ、を備え、前記サービスシステムが、前記サービスＩＤを前記ＩＤデバイスに送信し、その後、前記ＩＤデバイスが、前記サービスＩＤから前期サービスシステムに対応する前記サブＩＤを検索し、その後、前記ＩＤデバイスが前記ユーザ乱数発生装置を用いてユーザ乱数を生成し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置を用いて前記ユーザ乱数とひとつの前記部分サブＩＤをハッシュ変換したユーザハッシュ値を、前記ユーザ乱数とともに前記サービスシステムに渡すという部分サブＩＤ開示処理を実行し、その後、前記サービスシステムが前記サービスハッシュ装置と前期ユーザ乱数および自己がもつ前記ユーザＩＤリストを用いて前記ユーザハッシュ値に対応する複数の前記ユーザＩＤを絞り込むというサブＩＤ絞込み処理を実行し、その後、サブＩＤが1つに絞り込まれるまで前記部分サブＩＤ開示処理と前記サブＩＤ絞込み処理を繰り返すことを特徴とする請求項１記載の識別方法。
【請求項６】
すべての前記ユーザについての前記ユーザＩＤと前記サブＩＤが一致するようにサブＩＤを抽出し、すべての前記サービスの前記サービスＩＤが空値を含む固定値であることを特徴とする請求項１〜５のいずれかに記載の識別方法。
【請求項７】
前記サービスシステムと前記ＩＤデバイスが相互に認証することを特徴とする請求項１〜６のいずれかに記載の識別方法。
【請求項８】
前記システム乱数を空値することを特徴とする請求項１〜７のいずれかに記載の識別方法。
【請求項９】
前記サービスシステムが前記ユーザハッシュ装置を用いて前記ユーザ乱数と前記サブＩＤをハッシュ変換したサービスハッシュ値を前記ＩＤデバイスに渡し、その後、前記ＩＤデバイスが前記ユーザハッシュ装置と前記サービス乱数および自己が持つ前記サブＩＤを用いて前記サービスハッシュ値が前期ユーザＩＤに対応するかを確認し、対応すれば前期ＩＤデバイスが前記サービスシステムを正しいサービスシステムであると認証することを特徴とする請求項１〜８のいずれかに掲載の識別方法。
【請求項１０】
前記ＩＤデバイスが、ユーザ秘密鍵と、ユーザ公開鍵復号化装置と、前記サービスシステムが、公開鍵と、前記ユーザ公開鍵復号化装置に対応した公開鍵暗号化装置と、を備え、前記サービスシステムが前記公開鍵と前記公開鍵暗号化装置を用いて前記サービス乱数と前記サブＩＤを暗号化したサービス暗号値を前記ＩＤデバイスに渡し、その後、前記ＩＤデバイスが前記ユーザ秘密鍵と前記ユーザ公開鍵復号化装置を前記サービス暗号値を復号化し、これが前記サブＩＤに一致すれば前期ＩＤデバイスが前記サービスシステムを正しいサービスシステムであると認証することを特徴とする請求項１〜９に記載の識別方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００６−２４６２６９（Ｐ２００６−２４６２６９Ａ）
【公開日】平成１８年９月１４日（２００６．９．１４）
【国際特許分類】
【出願番号】特願２００５−６１７２２（Ｐ２００５−６１７２２）
【出願日】平成１７年３月７日（２００５．３．７）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ２００４年１０月２０日 社団法人情報処理学会発行の「情報処理学会シンポジウムシリーズ Ｖｏｌ．２００４，Ｎｏ．１１ コンピュータセキュリティシンポジウム２００４論文集 Ｖｏｌｕｍｅ １ ｏｆ ２」に発表
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成１７年１月２５日 ２００５年暗号と情報セキュリティシンポジウム実行委員会事務局発行の「２００５年 暗号と情報セキュリティシンポジウム 予稿集 Ｖｏｌｕｍｅ ３ ｏｆ ４」に発表
【出願人】（５０４１４５３４２）国立大学法人九州大学 (960)
【Ｆターム（参考）】
【公開日】平成１８年９月１４日（２００６．９．１４）
【国際特許分類】
【出願日】平成１７年３月７日（２００５．３．７）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ２００４年１０月２０日 社団法人情報処理学会発行の「情報処理学会シンポジウムシリーズ Ｖｏｌ．２００４，Ｎｏ．１１ コンピュータセキュリティシンポジウム２００４論文集 Ｖｏｌｕｍｅ １ ｏｆ ２」に発表
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成１７年１月２５日 ２００５年暗号と情報セキュリティシンポジウム実行委員会事務局発行の「２００５年 暗号と情報セキュリティシンポジウム 予稿集 Ｖｏｌｕｍｅ ３ ｏｆ ４」に発表
【出願人】（５０４１４５３４２）国立大学法人九州大学 (960)
【Ｆターム（参考）】
[ Back to top ]