小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記小型デバイスがID情報にノイズを加えたID ́と前記認証装置から受信した乱数とからなるベクトルの距離を複数求めて、該複数のベクトルの距離から前記認証装置が前記小型デバイスの認証を行うことを特徴とする認証システム。小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての乱数を生成する乱数生成手段と、前記小型デバイスに対し、該生成した乱数を送信する第1の送信手段と、を備え、前記小型デバイスが、前記乱数を受信する受信手段と、該受信した乱数のMAC値を演算する第1のMAC値演算手段と、前記ID情報にノイズを加えたID ́を生成するID ́生成手段と、該生成したID ́と乱数との距離を演算する距離演算手段と、該演算したMAC値と距離とを前記認証装置に送信する第2の送信手段と、を備え、前記乱数生成手段、第1の送信手段、受信手段、MAC値演算手段、ID ́生成手段、距離演算手段、第2の送信手段の処理を繰り返し、前記認証装置が、前記ID情報を特定するID特定手段と、該特定したIDのMAC値を演算する第2のMAC値演算手段と、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う認証手段と、を備えたことを特徴とする認証システム。前記乱数生成手段が生成する乱数がランダムに選択されたn次元ベクトルであることを特徴とする請求項2に記載の認証システム。前記乱数生成手段がn次元座標上で、前記マップ上のIDと一直線上に並ぶ乱数を生成することを特徴とする請求項2に記載の認証システム。前記ID ́生成手段は、攻撃者が意図的な乱数を送る場合に、ノイズ量を大きくしてID ́を生成することを特徴とする請求項2に記載の認証システム。小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての複数の乱数を生成する乱数生成手段と、前記小型デバイスに対し、該生成した複数の乱数を送信する第1の送信手段と、を備え、前記小型デバイスが、前記複数の乱数を受信する受信手段と、該受信した複数の乱数のMAC値を演算する第1のMAC値演算手段と、前記ID情報にノイズを加えたID ́を生成するID ́生成手段と、該生成したID ́と複数の乱数との距離をそれぞれ演算する距離演算手段と、該演算したMAC値と複数の距離情報とを前記認証装置に送信する第2の送信手段と、を備え、前記認証装置が、前記ID情報を特定するID特定手段と、該特定したIDのMAC値を演算する第2のMAC値演算手段と、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う認証手段と、を備えたことを特徴とする認証システム。前記乱数生成手段が生成する乱数がランダムに選択されたn次元ベクトルであることを特徴とする請求項6に記載の認証システム。前記乱数生成手段がn次元座標上で、前記マップ上のIDと一直線上に並ぶ乱数を生成することを特徴とする請求項6に記載の認証システム。前記ID ́生成手段は、攻撃者が意図的な乱数を送る場合に、ノイズ量を大きくしてID ́を生成することを特徴とする請求項6に記載の認証システム。小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムにおける認証方法であって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有し、前記認証装置が、チャレンジとしての乱数を生成する第1のステップと、前記認証装置が、前記小型デバイスに対し、該生成した乱数を送信する第2のステップと、前記小型デバイスが、前記乱数を受信する第3のステップと、前記小型デバイスが、該受信した乱数のMAC値を演算する第4のステップと、前記小型デバイスが、前記ID情報にノイズを加えたID ́を生成する第5のステップと、前記小型デバイスが、該生成したID ́と乱数との距離を演算する第6のステップと、前記小型デバイスが、該演算したMAC値と距離とを前記認証装置に送信する第7のステップと、前記第1のステップから第7のステップの処理を繰り返す第8のステップと、前記認証装置が、前記ID情報を特定する第9のステップと、前記認証装置が、該特定したIDのMAC値を演算する第10のステップと、前記認証装置が、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う第11のステップと、を備えたことを特徴とする認証方法。小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムにおける認証方法であって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有し、前記認証装置が、チャレンジとしての複数の乱数を生成する第1のステップと、前記認証装置が、前記小型デバイスに対し、該生成した複数の乱数を送信する第2のステップと、前記小型デバイスが、前記複数の乱数を受信する第3のステップと、前記小型デバイスが、該受信した複数の乱数のMAC値を演算する第4のステップと、前記小型デバイスが、前記ID情報にノイズを加えたID ́を生成する第5のステップと、前記小型デバイスが、該生成したID ́と複数の乱数との距離をそれぞれ演算する第6のステップと、前記小型デバイスが、該演算したMAC値と複数の距離情報とを前記認証装置に送信する第7のステップと、前記認証装置が、前記ID情報を特定する第8のステップと、前記認証装置が、該特定したIDのMAC値を演算する第9のステップと、前記認証装置が、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う第10のステップと、を備えたことを特徴とする認証方法。小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムにおける認証方法をコンピュータに実行させるためのプログラムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての乱数を生成する第1のステップと、前記認証装置が、前記小型デバイスに対し、該生成した乱数を送信する第2のステップと、前記小型デバイスが、前記乱数を受信する第3のステップと、前記小型デバイスが、該受信した乱数のMAC値を演算する第4のステップと、前記小型デバイスが、前記ID情報にノイズを加えたID ́を生成する第5のステップと、前記小型デバイスが、該生成したID ́と乱数との距離を演算する第6のステップと、前記小型デバイスが、該演算したMAC値と距離とを前記認証装置に送信する第7のステップと、前記第1のステップから第7のステップの処理を繰り返す第8のステップと、前記認証装置が、前記ID情報を特定する第9のステップと、前記認証装置が、該特定したIDのMAC値を演算する第10のステップと、前記認証装置が、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う第11のステップと、をコンピュータに実行させるためのプログラム。小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムにおける認証方法をコンピュータに実行させるためのプログラムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての複数の乱数を生成する第1のステップと、前記認証装置が、前記小型デバイスに対し、該生成した複数の乱数を送信する第2のステップと、前記小型デバイスが、前記複数の乱数を受信する第3のステップと、前記小型デバイスが、該受信した複数の乱数のMAC値を演算する第4のステップと、前記小型デバイスが、前記ID情報にノイズを加えたID ́を生成する第5のステップと、前記小型デバイスが、該生成したID ́と複数の乱数との距離をそれぞれ演算する第6のステップと、前記小型デバイスが、該演算したMAC値と複数の距離情報とを前記認証装置に送信する第7のステップと、前記認証装置が、前記ID情報を特定する第8のステップと、前記認証装置が、該特定したIDのMAC値を演算する第9のステップと、前記認証装置が、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う第10のステップと、をコンピュータに実行させるためのプログラム。しかしながら、非特許文献1に記載の技術では、中間者攻撃が可能といった脆弱性があった。つまり、IDの特定方法がないために、IDそのものをやりとりして認証を行うため、中間攻撃者にIDが露見してしまう危険性が高いという問題があった。また、IDの探索に時間を要し、計算能力が低い、例えば、RFID等の小型デバイスには適用することができなかったという問題点があった。さらに、小型デバイス向けに提案されたプロトコルも認証するタグのIDを効率的に求めることができないという問題点があった。そこで、本発明は、上述の課題に鑑みてなされたものであり、RFIDなどの小型デバイスに適用できる従来よりも効率的で安全性の高い認証方式を実現する認証システム、認証方法およびプログラムを提供することを目的とする。本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。1本発明は、小型デバイス例えば、図1のRFID100に相当と該小型デバイスを認証する認証装置例えば、図1の認証装置200に相当とからなる認証システムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記小型デバイスがID情報にノイズを加えたID ́と前記認証装置から受信した乱数とからなるベクトルの距離を複数求めて、該複数のベクトルの距離から前記認証装置が前記小型デバイスの認証を行うことを特徴とする認証システムを提案している。この発明によれば、小型デバイスと認証装置とが、小型デバイスごとに一意であるID情報を共有するとともに、認証装置が各小型デバイスのIDを配置したマップを有し、小型デバイスがID情報にノイズを加えたID ́と認証装置から受信した乱数とからなるベクトルの距離を複数求めて、複数のベクトルの距離から認証装置が小型デバイスの認証を行う。したがって、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。2本発明は、小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての乱数を生成する乱数生成手段例えば、図3の乱数生成部210に相当と、前記小型デバイスに対し、該生成した乱数を送信する第1の送信手段例えば、図3の第1の送信部220に相当と、を備え、前記小型デバイスが、前記乱数を受信する受信手段例えば、図2の第1の受信部110に相当と、該受信した乱数のMAC値を演算する第1のMAC値演算手段例えば、図2の第1のMAC値演算部120に相当と、前記ID情報にノイズを加えたID ́を生成するID ́生成手段例えば、図2のID ́生成部130に相当と、該生成したID ́と乱数との距離を演算する距離演算手段例えば、図2の距離演算部140に相当と、該演算したMAC値と距離とを前記認証装置に送信する第2の送信手段例えば、図2の第2の送信部150に相当と、を備え、前記乱数生成手段、第1の送信手段、受信手段、MAC値演算手段、ID ́生成手段、距離演算手段、第2の送信手段の処理を繰り返し、前記認証装置が、前記ID情報を特定するID特定手段例えば、図3のID特定部240に相当と、該特定したIDのMAC値を演算する第2のMAC値演算手段例えば、図3の第2のMAC値演算部250に相当と、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う認証手段例えば、図3の認証部260に相当と、を備えたことを特徴とする認証システムを提案している。この発明によれば、小型デバイスと認証装置とが、小型デバイスごとに一意であるID情報を共有するとともに、認証装置が各小型デバイスのIDを配置したマップを有し、認証装置の乱数生成手段が、チャレンジとしての乱数を生成し、第1の送信手段が、小型デバイスに対し、生成した乱数を送信する。小型デバイスの受信手段は、乱数を受信する。第1のMAC値演算手段は、受信した乱数のMAC値を演算する。ID ́生成手段は、ID情報にノイズを加えたID ́を生成する。距離演算手段は、生成したID ́と乱数との距離を演算する。第2の送信手段は、演算したMAC値と距離とを認証装置に送信する。そして、乱数生成手段、第1の送信手段、受信手段、MAC値演算手段、ID ́生成手段、距離演算手段、第2の送信手段の処理を繰り返し、認証装置のID特定手段は、ID情報を特定し、第2のMAC値演算手段が、特定したIDのMAC値を演算して、認証手段が受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行う。したがって、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。3本発明は、2の認証システムについて、前記乱数生成手段が生成する乱数がランダムに選択されたn次元ベクトルであることを特徴とする認証システムを提案している。この発明によれば、乱数生成手段が生成する乱数がランダムに選択されたn次元ベクトルである。したがって、匿名性を保ちつつ、ID情報を効率的に、検索することができる。4本発明は、2の認証システムについて、前記乱数生成手段がn次元座標上で、前記マップ上のIDと一直線上に並ぶ乱数を生成することを特徴とする認証システムを提案している。この発明によれば、乱数生成手段がn次元座標上で、マップ上のIDと一直線上に並ぶ乱数を生成する。したがって、認証装置が認証に有効な乱数を選択することにより、効率的に認証処理を行うことができる。5本発明は、2の認証システムについて、前記ID ́生成手段は、攻撃者が意図的な乱数を送る場合に、ノイズ量を大きくしてID ́を生成することを特徴とする認証システムを提案している。この発明によれば、ID ́生成手段は、攻撃者が意図的な乱数を送る場合に、ノイズ量を大きくしてID ́を生成する。つまり、攻撃者が認証処理を妨害したり、誤った認証処理を誘発するために、同じ乱数を繰り返し送信したり、類似の乱数を繰り返し送信するなど意図的な乱数を送る場合に、IDの特定ができないように、ノイズ量を大きくしてID ́を生成する。6本発明は、小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての複数の乱数を生成する乱数生成手段例えば、図3の乱数生成部211に相当と、前記小型デバイスに対し、該生成した複数の乱数を送信する第1の送信手段例えば、図3の第1の送信部221に相当と、を備え、前記小型デバイスが、前記複数の乱数を受信する受信手段例えば、図2の第1の受信部111に相当と、該受信した複数の乱数のMAC値を演算する第1のMAC値演算手段例えば、図2の第1のMAC値演算部121に相当と、前記ID情報にノイズを加えたID ́を生成するID ́生成手段例えば、図2のID ́生成部130に相当と、該生成したID ́と複数の乱数との距離を演算する距離演算手段例えば、図2の距離演算部141に相当と、該演算したMAC値と複数の距離とを前記認証装置に送信する第2の送信手段例えば、図2の第2の送信部151に相当と、を備え、前記乱数生成手段、第1の送信手段、受信手段、MAC値演算手段、ID ́生成手段、距離演算手段、第2の送信手段の処理を繰り返し、前記認証装置が、前記ID情報を特定するID特定手段例えば、図3のID特定部240に相当と、該特定したIDのMAC値を演算する第2のMAC値演算手段例えば、図3の第2のMAC値演算部250に相当と、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う認証手段例えば、図3の認証部260に相当と、を備えたことを特徴とする認証システムを提案している。この発明によれば、小型デバイスと認証装置とが、小型デバイスごとに一意であるID情報を共有するとともに、認証装置が各小型デバイスのIDを配置したマップを有し、認証装置の乱数生成手段が、チャレンジとしての複数の乱数を生成し、第1の送信手段が、小型デバイスに対し、生成した複数の乱数を送信する。小型デバイスの受信手段は、複数の乱数を受信する。第1のMAC値演算手段は、受信した複数の乱数のMAC値を演算する。ID ́生成手段は、ID情報にノイズを加えたID ́を生成する。距離演算手段は、生成したID ́と複数の乱数との距離をそれぞれ演算する。第2の送信手段は、演算したMAC値と複数の距離情報とを認証装置に送信する。そして、認証装置のID特定手段が、ID情報を特定し、第2のMAC値演算手段が特定したIDのMAC値を演算して、認証手段が、受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行う。したがって、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。特に、認証装置の乱数生成手段が、チャレンジとしての複数の乱数を生成し、第1の送信手段が、小型デバイスに対し、生成した複数の乱数を送信するとともに、小型デバイスの第1のMAC値演算手段が、受信した複数の乱数のMAC値を演算し、ID ́生成手段が、ID情報にノイズを加えたID ́を生成して、距離演算手段が、生成したID ́と複数の乱数との距離をそれぞれ演算するとともに、第2の送信手段が、演算したMAC値と複数の距離情報とを認証装置に送信することから、これらの処理を一括して実行することができるため、さらに効率化を図ることができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。7本発明は、6の認証システムについて、前記乱数生成手段が生成する乱数がランダムに選択されたn次元ベクトルであることを特徴とする認証システムを提案している。この発明によれば、乱数生成手段が生成する乱数がランダムに選択されたn次元ベクトルである。したがって、匿名性を保ちつつ、ID情報を効率的に、検索することができる。8本発明は、6の認証システムについて、前記乱数生成手段がn次元座標上で、前記マップ上のIDと一直線上に並ぶ乱数を生成することを特徴とする認証システムを提案している。この発明によれば、乱数生成手段がn次元座標上で、マップ上のIDと一直線上に並ぶ乱数を生成する。したがって、認証装置が認証に有効な乱数を選択することにより、効率的に認証処理を行うことができる。9本発明は、6の認証システムについて、前記ID ́生成手段は、攻撃者が意図的な乱数を送る場合に、ノイズ量を大きくしてID ́を生成することを特徴とする認証システムを提案している。この発明によれば、ID ́生成手段は、攻撃者が意図的な乱数を送る場合に、ノイズ量を大きくしてID ́を生成する。つまり、攻撃者が認証処理を妨害したり、誤った認証処理を誘発するために、同じ乱数を繰り返し送信したり、類似の乱数を繰り返し送信するなど意図的な乱数を送る場合に、IDの特定ができないように、ノイズ量を大きくしてID ́を生成する。10本発明は、小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムにおける認証方法であって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての乱数を生成する第1のステップ例えば、図5のステップS101に相当と、前記認証装置が、前記小型デバイスに対し、該生成した乱数を送信する第2のステップ例えば、図5のステップS102に相当と、前記小型デバイスが、前記乱数を受信する第3のステップ例えば、図5のステップS103に相当と、前記小型デバイスが、該受信した乱数のMAC値を演算する第4のステップ例えば、図5のステップS104に相当と、前記小型デバイスが、前記ID情報にノイズを加えたID ́を生成する第5のステップ例えば、図5のステップS105に相当と、前記小型デバイスが、該生成したID ́と乱数との距離を演算する第6のステップ例えば、図5のステップS106に相当と、前記小型デバイスが、該演算したMAC値と距離とを前記認証装置に送信する第7のステップ例えば、図5のステップS107に相当と、前記第1のステップから第7のステップの処理を繰り返す第8のステップ例えば、図5のステップS108に相当と、前記認証装置が、前記ID情報を特定する第9のステップ例えば、図5のステップS109に相当と、前記認証装置が、該特定したIDのMAC値を演算する第10のステップ例えば、図5のステップS110に相当と、前記認証装置が、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う第11のステップ例えば、図5のステップS111に相当と、を備えたことを特徴とする認証方法を提案している。この発明によれば、小型デバイスと認証装置とが、小型デバイスごとに一意であるID情報を共有するとともに、認証装置が各小型デバイスのIDを配置したマップを有し、認証装置が、チャレンジとしての乱数を生成し、小型デバイスに対し、生成した乱数を送信する。小型デバイスは、乱数を受信し、受信した乱数のMAC値を演算する。さらに、ID情報にノイズを加えたID ́を生成し、生成したID ́と乱数との距離を演算して、演算したMAC値と距離とを認証装置に送信する。そして、第1のステップから第7のステップの処理を繰り返す。認証装置は、ID情報を特定し、特定したIDのMAC値を演算して、受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行う。したがって、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。11本発明は、小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムにおける認証方法であって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての複数の乱数を生成する第1のステップ例えば、図8のステップS201に相当と、前記認証装置が、前記小型デバイスに対し、該生成した複数の乱数を送信する第2のステップ例えば、図8のステップS202に相当と、前記小型デバイスが、前記複数の乱数を受信する第3のステップ例えば、図8のステップS203に相当と、前記小型デバイスが、該受信した複数の乱数のMAC値を演算する第4のステップ例えば、図8のステップS204に相当と、前記小型デバイスが、前記ID情報にノイズを加えたID ́を生成する第5のステップ例えば、図8のステップS205に相当と、前記小型デバイスが、該生成したID ́と複数の乱数との距離をそれぞれ演算する第6のステップ例えば、図8のステップS206に相当と、前記小型デバイスが、該演算したMAC値と複数の距離情報とを前記認証装置に送信する第7のステップ例えば、図8のステップS207に相当と、前記認証装置が、前記ID情報を特定する第8のステップ例えば、図8のステップS208に相当と、前記認証装置が、該特定したIDのMAC値を演算する第9のステップ例えば、図8のステップS209に相当と、前記認証装置が、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う第10のステップ例えば、図8のステップS210に相当と、を備えたことを特徴とする認証方法を提案している。この発明によれば、小型デバイスと認証装置とが、小型デバイスごとに一意であるID情報を共有するとともに、認証装置が各小型デバイスのIDを配置したマップを有し、認証装置が、チャレンジとしての複数の乱数を生成し、小型デバイスに対し、生成した複数の乱数を送信する。小型デバイスは、複数の乱数を受信し、受信した複数の乱数のMAC値を演算する。さらに、ID情報にノイズを加えたID ́を生成し、生成したID ́と複数の乱数との距離をそれぞれ演算して、演算したMAC値と複数の距離情報とを認証装置に送信する。そして、認証装置が、ID情報を特定し、特定したIDのMAC値を演算して、受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行う。したがって、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。特に、第1のステップから第7のステップの処理を一括して実行することができるため、さらに効率化を図ることができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。12本発明は、小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムにおける認証方法をコンピュータに実行させるためのプログラムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての乱数を生成する第1のステップ例えば、図5のステップS101に相当と、前記認証装置が、前記小型デバイスに対し、該生成した乱数を送信する第2のステップ例えば、図5のステップS102に相当と、前記小型デバイスが、前記乱数を受信する第3のステップ例えば、図5のステップS103に相当と、前記小型デバイスが、該受信した乱数のMAC値を演算する第4のステップ例えば、図5のステップS104に相当と、前記小型デバイスが、前記ID情報にノイズを加えたID ́を生成する第5のステップ例えば、図5のステップS105に相当と、前記小型デバイスが、該生成したID ́と乱数との距離を演算する第6のステップ例えば、図5のステップS106に相当と、前記小型デバイスが、該演算したMAC値と距離とを前記認証装置に送信する第7のステップ例えば、図5のステップS107に相当と、前記第1のステップから第7のステップの処理を繰り返す第8のステップ例えば、図5のステップS108に相当と、前記認証装置が、前記ID情報を特定する第9のステップ例えば、図5のステップS109に相当と、前記認証装置が、該特定したIDのMAC値を演算する第10のステップ例えば、図5のステップS110に相当と、前記認証装置が、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う第11のステップ例えば、図5のステップS111に相当と、をコンピュータに実行させるためのプログラムを提案している。この発明によれば、小型デバイスと認証装置とが、小型デバイスごとに一意であるID情報を共有するとともに、認証装置が各小型デバイスのIDを配置したマップを有し、認証装置が、チャレンジとしての乱数を生成し、小型デバイスに対し、生成した乱数を送信する。小型デバイスは、乱数を受信し、受信した乱数のMAC値を演算する。さらに、ID情報にノイズを加えたID ́を生成し、生成したID ́と乱数との距離を演算して、演算したMAC値と距離とを認証装置に送信する。そして、第1のステップから第7のステップの処理を繰り返す。認証装置は、ID情報を特定し、特定したIDのMAC値を演算して、受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行う。したがって、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。13本発明は、小型デバイスと該小型デバイスを認証する認証装置とからなる認証システムにおける認証方法をコンピュータに実行させるためのプログラムであって、前記小型デバイスと認証装置とが、前記小型デバイスごとに一意であるID情報を共有するとともに、前記認証装置が前記各小型デバイスのIDを配置したマップを有し、前記認証装置が、チャレンジとしての複数の乱数を生成する第1のステップ例えば、図8のステップS201に相当と、前記認証装置が、前記小型デバイスに対し、該生成した複数の乱数を送信する第2のステップ例えば、図8のステップS202に相当と、前記小型デバイスが、前記複数の乱数を受信する第3のステップ例えば、図8のステップS203に相当と、前記小型デバイスが、該受信した複数の乱数のMAC値を演算する第4のステップ例えば、図8のステップS204に相当と、前記小型デバイスが、前記ID情報にノイズを加えたID ́を生成する第5のステップ例えば、図8のステップS205に相当と、前記小型デバイスが、該生成したID ́と複数の乱数との距離をそれぞれ演算する第6のステップ例えば、図8のステップS206に相当と、前記小型デバイスが、該演算したMAC値と複数の距離情報とを前記認証装置に送信する第7のステップ例えば、図8のステップS207に相当と、前記認証装置が、前記ID情報を特定する第8のステップ例えば、図8のステップS208に相当と、前記認証装置が、該特定したIDのMAC値を演算する第9のステップ例えば、図8のステップS209に相当と、前記認証装置が、前記受信したMAC値と該演算したMAC値のすべてが一致したときに、認証を行う第10のステップ例えば、図8のステップS210に相当と、をコンピュータに実行させるためのプログラムを提案している。この発明によれば、小型デバイスと認証装置とが、小型デバイスごとに一意であるID情報を共有するとともに、認証装置が各小型デバイスのIDを配置したマップを有し、認証装置が、チャレンジとしての複数の乱数を生成し、小型デバイスに対し、生成した複数の乱数を送信する。小型デバイスは、複数の乱数を受信し、受信した複数の乱数のMAC値を演算する。さらに、ID情報にノイズを加えたID ́を生成し、生成したID ́と複数の乱数との距離をそれぞれ演算して、演算したMAC値と複数の距離情報とを認証装置に送信する。そして、認証装置が、ID情報を特定し、特定したIDのMAC値を演算して、受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行う。したがって、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。特に、第1のステップから第7のステップの処理を一括して実行することができるため、さらに効率化を図ることができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。本発明によれば、小型デバイスにも適用可能で、従来よりも効率的な認証処理を実現することができるという効果がある。特に、匿名性を保ちつつ、ID情報を効率的に探索する認証処理を実現することができるという効果がある。以下、本発明の実施形態について、図面を用いて、詳細に説明する。なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。<認証システムの構成>図1を用いて、本発明に係る認証システムの構成について説明する。本発明に係る認証システムは、図1に示すように、小型デバイスである例えば、RFID100と、認証装置200とから構成されている。本発明に係る認証システムは、RFID100と認証装置200とが、RFID100ごとに一意であるID情報を共有し、RFID100がID情報にノイズを加えたID ́と認証装置から受信した乱数とからなるベクトルの距離を複数求めて、複数のベクトルの距離から認証装置が前記RFID100の認証を行うものである。以下、RFID100および認証装置200の詳細な構成について説明する。<第1の実施形態>以下、図2から図5を用いて、本実施形態に係る認証システムについて説明する。<RFIDの構成>本実施形態に係るRFIDは、図2に示すように、第1の受信部110と、第1のMAC値演算部120と、ID ́生成部130と、距離演算部140と、第2の送信部150とから構成されている。第1の受信部110は、乱数を受信する。なお、IDは、RFIDごとに一意であり、n次元のベクトルとして定義される。第1のMAC値演算部120は、受信した乱数のMAC値を演算する。MAC値の演算においては、秘密鍵を用いる。ID ́生成部130は、ID情報にノイズを加えたID ́を生成する。なお、攻撃者が意図的な乱数を送る場合に、ノイズ量を大きくしてID ́を生成する。つまり、攻撃者が認証処理を妨害したり、誤った認証処理を誘発するために、同じ乱数を繰り返し送信したり、類似の乱数を繰り返し送信するなど意図的な乱数を送る場合に、IDの特定ができないように、ノイズ量を大きくしてID ́を生成する。距離演算部140は、生成したID ́と乱数との距離を演算する。第2の送信部150は、演算したMAC値と距離とを認証装置200に送信する。<認証装置の構成>本実施形態に係る認証装置は、例えば、RFIDのリーダーであり、図3に示すように、乱数生成部210と、第1の送信部220と、第2の受信部230と、ID特定部240と、第2のMAC値演算部250と、認証部260とから構成されている。乱数生成部210は、チャレンジとしての乱数を生成する。ここで、チャレンジとしての乱数は、ランダムに選択されたn次元ベクトルである。また、乱数生成部210は、n次元座標上で、一直線上に並ぶ乱数を生成するようにしてもよい。第1の送信部220は、RFID100に対し、生成した乱数を送信する。第2の受信部230は、演算したMAC値と距離とをRFID100から受信する。ID特定部240は、乱数生成部210、第1の送信部220、RFID100の第1の受信部110、第1のMAC値演算部120、ID ́生成部130、距離演算部140、第2の送信部150の処理を繰り返し、ID情報を特定する。なお、認証装置200が保有するIDと乱数の関係は、図4のようになっている。この例では、乱数R1とその距離L1、乱数R2とその距離L2、乱数R3とその距離L3が得られれば、乱数R1、R2、R3を中心として、距離L1、L2、L3を半径とする円を描き、これらの円が交わるエリアに存在するID図4では、ID_Dを検索することにより、IDを特定することができる。なお、図4では、説明を簡略化するために2次元の例を示している。第2のMAC値演算部250は、特定したIDのMAC値を演算する。認証部260は、受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行う。<認証システムの処理>図5を用いて、本実施形態に係る認証システムの処理について説明する。まず、認証装置200が、チャレンジとしての乱数を生成しステップS101、RFID100に対し、生成した乱数を送信するステップS102。RFID100は、乱数を受信しステップS103、受信した乱数のMAC値を演算するステップS104。そして、ID情報にノイズを加えたID ́を生成しステップS105、生成したID ́と乱数との距離を演算してステップS106、演算したMAC値と距離とを認証装置200に送信するステップS107。さらに、ステップS101からステップS107の処理を繰り返すステップS108。認証装置200は、ID情報を特定しステップS109、特定したIDのMAC値を演算してステップS110、受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行うステップS111。以上、説明したように、本実施形態によれば、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。<第2の実施形態>以下、図6から図8を用いて、本実施形態に係る認証システムについて説明する。<RFIDの構成>本実施形態に係るRFIDは、図6に示すように、第1の受信部111と、第1のMAC値演算部121と、ID ́生成部130と、距離演算部141と、第2の送信部151とから構成されている。なお、第1の実施形態と同一の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は、省略する。第1の受信部111は、複数の乱数を受信する。なお、IDは、RFIDごとに一意であり、n次元のベクトルとして定義される。第1のMAC値演算部121は、受信した複数の乱数のMAC値を演算する。MAC値の演算においては、秘密鍵を用いる。距離演算部141は、生成したID ́と複数の乱数との距離を演算する。第2の送信部151は、演算したMAC値と複数の距離とを認証装置200に送信する。<認証装置の構成>本実施形態に係る認証装置は、例えば、RFIDのリーダーであり、図7に示すように、乱数生成部211と、第1の送信部221と、第2の受信部231と、ID特定部240と、第2のMAC値演算部250と、認証部260とから構成されている。乱数生成部211は、チャレンジとしての複数の乱数を生成する。ここで、チャレンジとしての乱数は、ランダムに選択されたn次元ベクトルである。また、乱数生成部211は、n次元座標上で、一直線上に並ぶ乱数を生成するようにしてもよい。第1の送信部221は、RFID100に対し、生成した複数の乱数を送信する。第2の受信部231は、演算したMAC値と距離とをRFID100から受信する。なお、認証装置200が保有するIDと乱数の関係は、図4のようになっている。この例では、乱数R1とその距離L1、乱数R2とその距離L2、乱数R3とその距離L3が得られれば、乱数R1、R2、R3を中心として、距離L1、L2、L3を半径とする円を描き、これらの円が交わるエリアに存在するID図4では、ID_Dを検索することにより、IDを特定することができる。なお、図4では、説明を簡略化するために2次元の例を示している。<認証システムの処理>図8を用いて、本実施形態に係る認証システムの処理について説明する。まず、認証装置200が、チャレンジとしての複数の乱数を生成しステップS201、RFID100に対し、生成した複数の乱数を送信するステップS202。RFID100は、複数の乱数を受信しステップS203、受信した複数の乱数のMAC値を演算するステップS204。そして、ID情報にノイズを加えたID ́を生成しステップS205、生成したID ́と複数の乱数との距離を演算してステップS206、演算したMAC値と複数の距離とを認証装置200に送信するステップS207。認証装置200は、ID情報を特定しステップS208、特定したIDのMAC値を演算してステップS209、受信したMAC値と演算したMAC値のすべてが一致したときに、認証を行うステップS210。以上、説明したように、本実施形態によれば、演算負荷が小さいため、小型デバイスに適用でき、効率的に認証処理を行うことができる。特に、第1のステップから第7のステップの処理を一括して実行することができるため、さらに効率化を図ることができる。また、認証処理に直接IDを用いないため、不正な第三者のIDの特定が困難になる。さらに、ID自体にもノイズを加えて処理しているため、秘匿性が高い。なお、小型デバイスおよび認証装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを小型デバイスおよび認証装置に読み込ませ、実行することによって本発明の認証システムを実現することができる。ここでいうコンピュータシステムとは、OSや周辺装置等のハードウェアを含む。また、コンピュータシステムは、WWWWorldWideWebシステムを利用している場合であれば、ホームページ提供環境あるいは表示環境も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する伝送媒体は、インターネット等のネットワーク通信網や電話回線等の通信回線通信線のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル差分プログラムであっても良い。以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。