(57)【要約】【課題】認証デバイスが複数の被認証デバイスを一括して認証する。【解決手段】複数の被認証デバイスが、秘密鍵Ｓを保有しており、認証デバイスが、乱数Ｒを生成し、生成した乱数を複数の被認証デバイスに送信する。次いで、複数の被認証デバイスから受信した値から加算に対して一意に分解可能な複数の被認証デバイスのＩＤの加算値を求め、加算値から複数の被認証デバイスのＩＤを特定して認証を行う。【選択図】図３
2012034303.tif 000002
【特許請求の範囲】
【請求項１】
認証デバイスが複数の被認証デバイスを認証する多重認証システムであって、
前記複数の被認証デバイスが、秘密鍵Ｓを保有しており、
前記認証デバイスが、
乱数Ｒを生成する第１の乱数生成手段と、
該生成した乱数を前記複数の被認証デバイスに送信する第１の送信手段と、
前記複数の被認証デバイスから受信した値から加算に対して一意に分解可能な前記複数の被認証デバイスのＩＤの加算値を求める第１の演算手段と、
該加算値から前記複数の被認証デバイスのＩＤを特定して認証を行う認証手段と、
を備えたことを特徴とする多重認証システム。
【請求項２】
前記複数の被認証デバイスがそれぞれ、
乱数ｒ＿ｉを生成する第２の乱数生成手段と、
暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する第１の暗号化手段と、
該生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する第２の演算手段と、
を備え、
前記認証デバイスが、
前記Ａ＿ｉおよびＢ＿ｉを受信する受信手段と、
暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する乱数取得手段と、
を備え、
前記第１の演算手段が、前記Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、前記Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求めることを特徴とする請求項１に記載の多重認証システム。
【請求項３】
認証デバイスが複数の被認証デバイスを認証する多重認証システムであって、
前記複数の被認証デバイスが、異なる秘密鍵ｘ＿ｉを保有しており、
前記認証デバイスが、
乱数Ｒを生成する第１の乱数生成手段と、
該生成した乱数を前記複数の被認証デバイスに送信する第１の送信手段と、
前記複数の被認証デバイスから受信した値を用いて、所定の演算を行い、演算値を求める第１の演算手段と、
該演算値を検証することにより認証を行う認証手段と、
を備えたことを特徴とする多重認証システム。
【請求項４】
前記複数の被認証デバイスがそれぞれ、
乱数ｒ＿ｉを生成する第２の乱数生成手段と、
自己の秘密鍵ｘ＿ｉ、前記認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する第２の演算手段と、
を備え、
前記認証デバイスが、
前記Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信する受信手段と、
を備え、
前記第１の演算手段が、該受信したＡ＿ｉをすべて乗算してＡを求め、該受信したＢ＿ｉをすべて乗算してＢを求め、該受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算することを特徴とする請求項３に記載の多重認証システム。
【請求項５】
前記複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、前記求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した前記複数の非認証デバイスのＩＤを取得するＩＤ取得手段を備えたことを特徴とする請求項４に記載の多重認証システム。
【請求項６】
認証デバイスが複数の被認証デバイスを認証する多重認証システムにおける多重認証方法であって、
前記複数の被認証デバイスが、秘密鍵Ｓを保有しており、
前記認証デバイスが、乱数Ｒを生成する第１のステップと、
前記認証デバイスが、該生成した乱数を前記複数の被認証デバイスに送信する第２のステップと、
前記認証デバイスが、前記複数の被認証デバイスから受信した値から加算に対して一意に分解可能な前記複数の被認証デバイスのＩＤの加算値を求める第３のステップと、
前記認証デバイスが、該加算値から前記複数の被認証デバイスのＩＤを特定して認証を行う第４のステップと、
を備えたことを特徴とする多重認証方法。
【請求項７】
前記複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成する第５のステップと、
前記複数の被認証デバイスが暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する第６のステップと、
前記複数の被認証デバイスが該生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する第７のステップと、
を備え、
前記認証デバイスが、前記Ａ＿ｉおよびＢ＿ｉを受信する第８のステップと、
前記認証デバイスが、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する第９のステップと、
を備え、
前記第３のステップが、前記Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、前記Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求めることを特徴とする請求項６に記載の多重認証方法。
【請求項８】
認証デバイスが複数の被認証デバイスを認証する多重認証システムにおける多重認証方法であって、
前記複数の被認証デバイスが、異なる秘密鍵ｘ＿ｉを保有しており、
前記認証デバイスが、乱数Ｒを生成する第１のステップと、
前記認証デバイスが、該生成した乱数を前記複数の被認証デバイスに送信する第２のステップと、
前記認証デバイスが、前記複数の被認証デバイスから受信した値を用いて、所定の演算を行い、演算値を求める第３のステップと、
前記認証デバイスが、該演算値を検証することにより認証を行う第４のステップと、
を備えたことを特徴とする多重認証方法。
【請求項９】
前記複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成する第５のステップと、
前記複数の被認証デバイスが自己の秘密鍵ｘ＿ｉ、前記認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する第６のステップと、
を備え、
前記認証デバイスが、前記Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信する第７のステップと、
を備え、
前記第３のステップが、該受信したＡ＿ｉをすべて乗算してＡを求め、該受信したＢ＿ｉをすべて乗算してＢを求め、該受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算することを特徴とする請求項８に記載の多重認証方法。
【請求項１０】
前記複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、前記求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した前記複数の非認証デバイスのＩＤを取得する第８のステップをさらに備えたことを特徴とする請求項９に記載の多重認証方法。
【請求項１１】
認証デバイスが複数の被認証デバイスを認証する多重認証システムにおける多重認証方法をコンピュータに実行させるためのプログラムであって、
前記複数の被認証デバイスが、秘密鍵Ｓを保有しており、
前記認証デバイスが、乱数Ｒを生成する第１のステップと、
前記認証デバイスが、該生成した乱数を前記複数の被認証デバイスに送信する第２のステップと、
前記複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成する第３のステップと、
前記複数の被認証デバイスが暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する第４のステップと、
前記複数の被認証デバイスが該生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する第５のステップと、
前記認証デバイスが、前記Ａ＿ｉおよびＢ＿ｉを受信する第６のステップと、
前記認証デバイスが、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する第７のステップと、
前記認証デバイスが、前記Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、前記Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求める第８のステップと、
前記認証デバイスが、該加算値から前記複数の被認証デバイスのＩＤを特定して認証を行う第９のステップと、
を備えたことを特徴とする多重認証方法。
【請求項１２】
認証デバイスが複数の被認証デバイスを認証する多重認証システムにおける多重認証方法をコンピュータに実行させるためのプログラムであって、
前記複数の被認証デバイスが、異なる秘密鍵ｘ＿ｉを保有しており、
前記認証デバイスが、乱数Ｒを生成する第１のステップと、
前記認証デバイスが、該生成した乱数を前記複数の被認証デバイスに送信する第２のステップと、
前記複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成する第３のステップと、
前記複数の被認証デバイスが自己の秘密鍵ｘ＿ｉ、前記認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する第４のステップと、
前記認証デバイスが、前記Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信する第５のステップと、
前記認証デバイスが、該受信したＡ＿ｉをすべて乗算してＡを求め、該受信したＢ＿ｉをすべて乗算してＢを求め、該受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算する第６のステップと、
前記認証デバイスが、該演算値を検証することにより認証を行う第７のステップと、
前記複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、前記認証デバイスが、前記求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した前記複数の被認証デバイスのＩＤを取得する第８のステップと、
を備えたことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認証デバイスが複数の被認証デバイスを一括して認証する多重認証システム、多重認証方法およびプログラムに関する。
【背景技術】
【０００２】
近年、ＩＤ情報を埋め込んだＲＦタグから、電磁界や電波等を用いた近距離（周波数帯によって数ｃｍ〜数ｍ）の無線通信によって情報をやりとりするＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ  ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）が注目を集め、非接触カード等に用いられ、広く普及している。また、ＲＦＩＤを小型センサーデバイスとして利用したサービスも検討されている（例えば、非特許文献１参照。）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｍ. Ｏｈｋｕｂｏ, Ｋ. Ｓｕｚｋｉ, ａｎｄ Ｓ. Ｋｉｎｏｓｈｉｔａ．Ｃｒｙｐｔｏｇｒａｐｈｉｃ ａｐｐｒｏａｃｈ ｔｏ “ｐｒｉｖａｃｙ−ｆｒｉｅｎｄｌｙ” ｔａｇｓ. Ｉｎ  ＲＦＩＤ  Ｐｒｉｖａｃｙ Ｗｏｒｋｓｈｏｐ,  ＭＩＴ, ＭＡ, ＵＳＡ, Ｎｏｖｅｍｂｅｒ  ２００３.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、ＲＦＩＤとリーダとの間では通常認証処理が行なわれるが、１対１で認証することが前提となっていた。そのため、認証が非効率であるという問題があった。
【０００５】
そこで、本発明は、上述の課題に鑑みてなされたものであり、認証デバイスが複数の被認証デバイスを一括して認証する多重認証システム、多重認証方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記の課題を解決するために以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【０００７】
（１）本発明は、認証デバイスが複数の被認証デバイスを認証する多重認証システムであって、前記複数の被認証デバイスが、秘密鍵Ｓを保有しており、前記認証デバイスが、乱数Ｒを生成する第１の乱数生成手段（例えば、図２の乱数生成部１１１に相当）と、該生成した乱数を前記複数の被認証デバイスに送信する第１の送信手段（例えば、図２の送信部１１２に相当）と、前記複数の被認証デバイスから受信した値から加算に対して一意に分解可能な前記複数の被認証デバイスのＩＤの加算値を求める第１の演算手段（例えば、図２の演算部１１３に相当）と、該加算値から前記複数の被認証デバイスのＩＤを特定して認証を行う認証手段（例えば、図２の認証部１１４に相当）と、を備えたことを特徴とする多重認証システムを提案している。
【０００８】
この発明によれば、複数の被認証デバイスが、秘密鍵Ｓを保有しており、認証デバイスの第１の乱数生成手段は、乱数Ｒを生成する。第１の送信手段は、生成した乱数を複数の被認証デバイスに送信する。第１の演算手段は、複数の被認証デバイスから受信した値から加算に対して一意に分解可能な複数の被認証デバイスのＩＤの加算値を求める。認証手段は、加算値から複数の被認証デバイスのＩＤを特定して認証を行う。したがって、複数の被認証デバイスを一括して認証することができる。
【０００９】
（２）本発明は、（１）の多重認証システムについて、前記複数の被認証デバイスがそれぞれ、乱数ｒ＿ｉを生成する第２の乱数生成手段（例えば、図５の乱数生成部２２１に相当）と、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する第１の暗号化手段（例えば、図５の暗号化部２２２に相当）と、該生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する第２の演算手段（例えば、図５の演算部２２３に相当）と、を備え、前記認証デバイスが、前記Ａ＿ｉおよびＢ＿ｉを受信する受信手段（例えば、図４の受信部１２１に相当）と、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する乱数取得手段（例えば、図４の乱数取得部１２２に相当）と、を備え、前記第１の演算手段が、前記Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、前記Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求めることを特徴とする多重認証システムを提案している。
【００１０】
この発明によれば、複数の被認証デバイスのそれぞれにおいて、第２の乱数生成手段は、乱数ｒ＿ｉを生成する。第１の暗号化手段は、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する。第２の演算手段は、生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する。認証デバイスにおいて、受信手段は、Ａ＿ｉおよびＢ＿ｉを受信する。乱数取得手段は、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する。そして、第１の演算手段は、Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求める。したがって、すべての被認証デバイスが秘密鍵Ｓを共有している場合に、軽量な演算で、複数の被認証デバイス個々のＩＤを特定した上で、一括して認証処理を行うことができる。
【００１１】
（３）本発明は、認証デバイスが複数の被認証デバイスを認証する多重認証システムであって、前記複数の被認証デバイスが、異なる秘密鍵ｘ＿ｉを保有しており、前記認証デバイスが、乱数Ｒを生成する第１の乱数生成手段（例えば、図７の乱数生成部１３１に相当）と、該生成した乱数を前記複数の被認証デバイスに送信する第１の送信手段（例えば、図７の送信部１３２に相当）と、前記複数の被認証デバイスから受信した値を用いて、所定の演算を行い、演算値を求める第１の演算手段（例えば、図７の演算部１３３に相当）と、該演算値を検証することにより認証を行う認証手段（例えば、図７の認証部１３４に相当）と、を備えたことを特徴とする多重認証システムを提案している。
【００１２】
この発明によれば、認証デバイスについて、第１の乱数生成手段は、乱数Ｒを生成する。第１の送信手段は、生成した乱数を複数の被認証デバイスに送信する。第１の演算手段は、複数の被認証デバイスから受信した値を用いて、所定の演算を行い、演算値を求める。認証手段は、演算値を検証することにより認証を行う。したがって、複数の認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合においても、複数の被認証デバイスを一括して認証することができる。
【００１３】
（４）本発明は、（３）の多重認証システムについて、前記複数の被認証デバイスがそれぞれ、乱数ｒ＿ｉを生成する第２の乱数生成手段（例えば、図１０の乱数生成部２４１に相当）と、自己の秘密鍵ｘ＿ｉ、前記認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する第２の演算手段（例えば、図１０の演算部２４２に相当）と、を備え、前記認証デバイスが、前記Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信する受信手段（例えば、図９の受信部１４１に相当）と、を備え、前記第１の演算手段が、該受信したＡ＿ｉをすべて乗算してＡを求め、該受信したＢ＿ｉをすべて乗算してＢを求め、該受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算することを特徴とする多重認証システムを提案している。
【００１４】
この発明によれば、複数の被認証デバイスのそれぞれについて、第２の乱数生成手段は、乱数ｒ＿ｉを生成する。第２の演算手段は、自己の秘密鍵ｘ＿ｉ、認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する。認証デバイスの受信手段は、Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信する。そして、第１の演算手段が、受信したＡ＿ｉをすべて乗算してＡを求め、受信したＢ＿ｉをすべて乗算してＢを求め、受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算する。したがって、すべての被認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合でも、軽量な演算で、一括して認証処理を行うことができる。
【００１５】
（５）本発明は、（４）の多重認証システムについて、前記複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、前記求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した前記複数の非認証デバイスのＩＤを取得するＩＤ取得手段を備えたことを特徴とする多重認証システムを提案している。
【００１６】
この発明によれば、複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、ＩＤ取得手段は、求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した複数の非認証デバイスのＩＤを取得する。したがって、すべての被認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合でも、それぞれのＩＤを特定した上で、認証処理を行うことができる。
【００１７】
（６）本発明は、認証デバイスが複数の被認証デバイスを認証する多重認証システムにおける多重認証方法であって、前記複数の被認証デバイスが、秘密鍵Ｓを保有しており、前記認証デバイスが、乱数Ｒを生成する第１のステップ（例えば、図３のステップＳ１０１に相当）と、前記認証デバイスが、該生成した乱数を前記複数の被認証デバイスに送信する第２のステップ（例えば、図３のステップＳ１０２に相当）と、前記認証デバイスが、前記複数の被認証デバイスから受信した値から加算に対して一意に分解可能な前記複数の被認証デバイスのＩＤの加算値を求める第３のステップ（例えば、図３のステップＳ１０３に相当）と、前記認証デバイスが、該加算値から前記複数の被認証デバイスのＩＤを特定して認証を行う第４のステップ（例えば、図３のステップＳ１０４に相当）と、を備えたことを特徴とする多重認証方法を提案している。
【００１８】
この発明によれば、複数の被認証デバイスが、秘密鍵Ｓを保有しており、認証デバイスが、乱数Ｒを生成し、生成した乱数を複数の被認証デバイスに送信する。次いで、複数の被認証デバイスから受信した値から加算に対して一意に分解可能な複数の被認証デバイスのＩＤの加算値を求め、加算値から複数の被認証デバイスのＩＤを特定して認証を行う。したがって、複数の被認証デバイスを一括して認証することができる。
【００１９】
（７）本発明は、（６）の多重認証方法について、前記複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成する第５のステップ（例えば、図６のステップＳ２０３に相当）と、前記複数の被認証デバイスが暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する第６のステップ（例えば、図６のステップＳ２０４に相当）と、前記複数の被認証デバイスが該生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する第７のステップ（例えば、図６のステップＳ２０５に相当）と、を備え、前記認証デバイスが、前記Ａ＿ｉおよびＢ＿ｉを受信する第８のステップ（例えば、図６のステップＳ２０６に相当）と、前記認証デバイスが、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する第９のステップ（例えば、図６のステップＳ２０７に相当）と、を備え、前記第３のステップが、前記Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、前記Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求めることを特徴とする多重認証方法を提案している。
【００２０】
この発明によれば、複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成し、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化して、生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する。認証デバイスは、Ａ＿ｉおよびＢ＿ｉを受信し、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する。そして、Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求める。したがって、すべての被認証デバイスが秘密鍵Ｓを共有している場合に、軽量な演算で、複数の被認証デバイス個々のＩＤを特定した上で、一括して認証処理を行うことができる。
【００２１】
（８）本発明は、認証デバイスが複数の被認証デバイスを認証する多重認証システムにおける多重認証方法であって、前記複数の被認証デバイスが、異なる秘密鍵ｘ＿ｉを保有しており、前記認証デバイスが、乱数Ｒを生成する第１のステップ（例えば、図８のステップＳ３０１に相当）と、前記認証デバイスが、該生成した乱数を前記複数の被認証デバイスに送信する第２のステップ（例えば、図８のステップＳ３０２に相当）と、前記認証デバイスが、前記複数の被認証デバイスから受信した値を用いて、所定の演算を行い、演算値を求める第３のステップ（例えば、図８のステップＳ３０３に相当）と、前記認証デバイスが、該演算値を検証することにより認証を行う第４のステップ（例えば、図８のステップＳ３０４に相当）と、を備えたことを特徴とする多重認証方法。
【００２２】
この発明によれば、複数の被認証デバイスが、異なる秘密鍵ｘ＿ｉを保有しており、認証デバイスが、乱数Ｒを生成し、生成した乱数を複数の被認証デバイスに送信する。そして、認証デバイスが、複数の被認証デバイスから受信した値を用いて、所定の演算を行い、演算値を求め、演算値を検証することにより認証を行う。したがって、複数の認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合においても、複数の被認証デバイスを一括して認証することができる。
【００２３】
（９）本発明は、（８）の多重認証方法について、前記複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成する第５のステップ（例えば、図１１のステップＳ４０３に相当）と、前記複数の被認証デバイスが自己の秘密鍵ｘ＿ｉ、前記認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する第６のステップ（例えば、図１１のステップＳ４０４に相当）と、を備え、前記認証デバイスが、前記Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信する第７のステップ（例えば、図１１のステップＳ４０５に相当）と、を備え、前記第３のステップが、該受信したＡ＿ｉをすべて乗算してＡを求め、該受信したＢ＿ｉをすべて乗算してＢを求め、該受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算することを特徴とする多重認証方法を提案している。
【００２４】
この発明によれば、複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成し、自己の秘密鍵ｘ＿ｉ、認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する。認証デバイスは、Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信し、受信したＡ＿ｉをすべて乗算してＡを求め、受信したＢ＿ｉをすべて乗算してＢを求め、受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算する。したがって、すべての被認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合でも、軽量な演算で、一括して認証処理を行うことができる。
【００２５】
（１０）本発明は、（９）の多重認証方法について、前記複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、前記求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した前記複数の非認証デバイスのＩＤを取得する第８のステップをさらに備えたことを特徴とする多重認証方法を提案している。
【００２６】
この発明によれば、複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した複数の非認証デバイスのＩＤを取得する。したがって、すべての被認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合でも、それぞれのＩＤを特定した上で、認証処理を行うことができる。
【００２７】
（１１）本発明は、認証デバイスが複数の被認証デバイスを認証する多重認証システムにおける多重認証方法をコンピュータに実行させるためのプログラムであって、前記複数の被認証デバイスが、秘密鍵Ｓを保有しており、前記認証デバイスが、乱数Ｒを生成する第１のステップ（例えば、図６のステップＳ２０１に相当）と、前記認証デバイスが、該生成した乱数を前記複数の被認証デバイスに送信する第２のステップ（例えば、図６のステップＳ２０２に相当）と、前記複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成する第３のステップ（例えば、図６のステップＳ２０３に相当）と、前記複数の被認証デバイスが暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する第４のステップ（例えば、図６のステップＳ２０４に相当）と、前記複数の被認証デバイスが該生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する第５のステップ（例えば、図６のステップＳ２０５に相当）と、前記認証デバイスが、前記Ａ＿ｉおよびＢ＿ｉを受信する第６のステップ（例えば、図６のステップＳ２０６に相当）と、前記認証デバイスが、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する第７のステップ（例えば、図６のステップＳ２０７に相当）と、前記認証デバイスが、前記Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、前記Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求める第８のステップ（例えば、図６のステップＳ２０８に相当）と、前記認証デバイスが、該加算値から前記複数の被認証デバイスのＩＤを特定して認証を行う第９のステップ（例えば、図６のステップＳ２０９に相当）と、を備えたことを特徴とする多重認証方法を提案している。
【００２８】
この発明によれば、複数の被認証デバイスが、秘密鍵Ｓを保有しており、認証デバイスが、乱数Ｒを生成し、生成した乱数を複数の被認証デバイスに送信する。次いで、複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成し、複数の被認証デバイスが暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化して、生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する。認証デバイスは、Ａ＿ｉおよびＢ＿ｉを受信し、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する。次いで、Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求め、加算値から複数の被認証デバイスのＩＤを特定して認証を行う。したがって、すべての被認証デバイスが秘密鍵Ｓを共有している場合に、軽量な演算で、複数の被認証デバイス個々のＩＤを特定した上で、一括して認証処理を行うことができる。
【００２９】
（１２）本発明は、認証デバイスが複数の被認証デバイスを認証する多重認証システムにおける多重認証方法をコンピュータに実行させるためのプログラムであって、前記複数の被認証デバイスが、異なる秘密鍵ｘ＿ｉを保有しており、前記認証デバイスが、乱数Ｒを生成する第１のステップ（例えば、図１１のステップＳ４０１に相当）と、前記認証デバイスが、該生成した乱数を前記複数の被認証デバイスに送信する第２のステップ（例えば、図１１のステップＳ４０２に相当）と、前記複数の被認証デバイスがそれぞれ乱数ｒ＿ｉを生成する第３のステップ（例えば、図１１のステップＳ４０３に相当）と、前記複数の被認証デバイスが自己の秘密鍵ｘ＿ｉ、前記認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する第４のステップ（例えば、図１１のステップＳ４０４に相当）と、前記認証デバイスが、前記Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信する第５のステップ（例えば、図１１のステップＳ４０５に相当）と、前記認証デバイスが、該受信したＡ＿ｉをすべて乗算してＡを求め、該受信したＢ＿ｉをすべて乗算してＢを求め、該受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算する第６のステップ（例えば、図１１のステップＳ４０６に相当）と、前記認証デバイスが、該演算値を検証することにより認証を行う第７のステップ（例えば、図１１のステップＳ４０７に相当）と、前記複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、前記認証デバイスが、前記求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した前記複数の被認証デバイスのＩＤを取得する第８のステップ（例えば、図１１のステップＳ４０８に相当）と、を備えたことを特徴とするプログラムを提案している。
【００３０】
この発明によれば、複数の被認証デバイスが、異なる秘密鍵ｘ＿ｉを保有しており、認証デバイスが、乱数Ｒを生成し、生成した乱数を複数の被認証デバイスに送信する。複数の被認証デバイスは、それぞれ乱数ｒ＿ｉを生成し、自己の秘密鍵ｘ＿ｉ、認証デバイスの公開鍵ｇｓと秘密鍵ｓと各被認証デバイスの公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する。認証デバイスは、Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信し、受信したＡ＿ｉをすべて乗算してＡを求め、受信したＢ＿ｉをすべて乗算してＢを求め、受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算する。そして、演算値を検証することにより認証を行い、さらに、複数の被認証デバイスの個別のＩＤがｈ（ｇｘ＿ｉ）であり、求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した複数の被認証デバイスのＩＤを取得する。したがって、すべての被認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合でも、軽量な演算で、一括して認証処理を行うことができる。また、すべての被認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合でも、それぞれのＩＤを特定した上で、認証処理を行うことができる。
【発明の効果】
【００３１】
本発明によれば、認証デバイスが複数の被認証デバイスを一括して認証できるため、認証処理を従来よりも効率化することができる。
【図面の簡単な説明】
【００３２】
【図１】本発明に係る多重認証システムの構成を示す図である。
【図２】本発明の第１の実施形態に係る認証デバイスの構成を示す図である。
【図３】本発明の第１の実施形態に係る多重認証システムの処理フローである。
【図４】本発明の第２の実施形態に係る認証デバイスの構成を示す図である。
【図５】本発明の第２の実施形態に係る被認証デバイスの構成を示す図である。
【図６】本発明の第２の実施形態に係る多重認証システムの処理フローである。
【図７】本発明の第３の実施形態に係る認証デバイスの構成を示す図である。
【図８】本発明の第３の実施形態に係る多重認証システムの処理フローである。
【図９】本発明の第４の実施形態に係る認証デバイスの構成を示す図である。
【図１０】本発明の第４の実施形態に係る被認証デバイスの構成を示す図である。
【図１１】本発明の第４の実施形態に係る多重認証システムの処理フローである。
【発明を実施するための形態】
【００３３】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３４】
＜多重認証システムの構成＞
図１を用いて、本発明の多重認証システムの構成について説明する。
【００３５】
本発明の多重認証システムは、図１に示すように、認証デバイス１００と複数の被認証デバイス２００とから構成されている。ここで、認証デバイス１００は、例えば、ＲＦＩＤリーダであり、被認証デバイス２００は、例えば、ＲＦＩＤタグである。本発明では、認証デバイス１００が複数の被認証デバイス２００を一括して認証する。
【００３６】
＜第１の実施形態＞
図２および図３を用いて、本発明の第１の実施形態について説明する。なお、本実施形態では、すべての被認証デバイス２００において、秘密鍵Ｓが共通であることを前提とする。
【００３７】
＜認証デバイスの構成＞
図２を用いて、本実施形態に係る認証デバイス１００の構成について説明する。
本実施形態に係る認証デバイス１００は、図２に示すように、乱数生成部１１１と、送信部１１２と、演算部１１３と、認証部１１４とから構成されている。
【００３８】
乱数生成部１１１は、乱数Ｒを生成する。送信部１１２は、生成した乱数を複数の被認証デバイス２００に送信する。演算部１１３は、複数の被認証デバイス２００から受信した値から加算に対して一意に分解可能な複数の被認証デバイス２００のＩＤの加算値を求める。認証部１１４は、加算値から複数の被認証デバイス２００のＩＤを特定して認証を行う。
【００３９】
＜多重認証システムの処理＞
図３を用いて、本実施形態に係る多重認証システムの処理について説明する。
認証デバイス１００は、乱数Ｒを生成し（ステップＳ１０１）、生成した乱数を複数の被認証デバイス２００に送信する（ステップＳ１０２）。
【００４０】
そして、複数の被認証デバイス２００から受信した値から加算に対して一意に分解可能な複数の被認証デバイス２００のＩＤの加算値を求め（ステップＳ１０３）、加算値から複数の被認証デバイス２００のＩＤを特定して認証を行う（ステップＳ１０４）。
【００４１】
以上、説明したように、本実施形態によれば、複数の被認証デバイスを一括して認証することができる。
【００４２】
＜第２の実施形態＞
図４から図６を用いて、本発明の第２の実施形態について説明する。なお、本実施形態では、すべての被認証デバイス２００において、秘密鍵Ｓが共通であることを前提とする。
【００４３】
＜認証デバイスの構成＞
図４を用いて、本実施形態に係る認証デバイス１００の構成について説明する。
本実施形態に係る認証デバイス１００は、図４に示すように、乱数生成部１１１と、送信部１１２と、認証部１１４、受信部１２１と、乱数取得部１２２と、演算部１２３とから構成されている。なお、第１の実施形態と同様の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は、省略する。
【００４４】
受信部１２１は、複数の被認証デバイス２００が演算したＡ＿ｉおよびＢ＿ｉを受信する。乱数取得部１２２は、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する。
【００４５】
演算部１２３は、Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求める。
【００４６】
＜被認証デバイスの構成＞
図５を用いて、本実施形態に係る被認証デバイス２００の構成について説明する。
本実施形態に係る被認証デバイス２００は、図５に示すように、乱数生成部２２１と、暗号化部２２２と、演算部２２３とから構成されている。
【００４７】
乱数生成部２２１は、乱数ｒ＿ｉを生成する。暗号化部２２２は、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する。演算部２２３は、生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する。
【００４８】
＜多重認証システムの処理＞
図６を用いて、本実施形態に係る多重認証システムの処理について説明する。
認証デバイス１００が、乱数Ｒを生成し（ステップＳ２０１）、生成した乱数を複数の被認証デバイス２００に送信する（ステップＳ２０２）。
【００４９】
複数の被認証デバイス２００がそれぞれ乱数ｒ＿ｉを生成し（ステップＳ２０３）、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化する（ステップＳ２０４）。次いで、生成した乱数ｒ＿ｉと暗号化したＥ（Ｓ、Ｒ）と自己のＩＤであるＩＤ＿ｉとに基づいて、Ａ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）およびＢ＿ｉ＝ＩＤ＿ｉ＋ｒ＿ｉを演算する（ステップＳ２０５）。
【００５０】
認証デバイス１００は、Ａ＿ｉおよびＢ＿ｉを受信し（ステップＳ２０６）、暗号アルゴリズムＥと秘密鍵ＳとによりＲをＥ（Ｓ、Ｒ）に暗号化してＡ＿ｉ＝ｒ＿ｉ  ＸＯＲ  Ｅ（Ｓ、Ｒ）を求めて、ｒ＿ｉを取得する（ステップＳ２０７）。
【００５１】
そして、Ａ＿ｉとＥ（Ｓ、Ｒ）の排他的論理和演算を行って、乱数ｒ＿ｉを復元し、すべての乱数ｒ＿ｉを加算してｒを求め、Ｂ＿ｉを加算してＢを求め、Ｂ−ｒを計算して、一意に分解可能な各被認証デバイスのＩＤの加算値を求め（ステップＳ２０８）、加算値から複数の被認証デバイス２００のＩＤを特定して認証を行う（ステップＳ２０９）。
【００５２】
以上、説明したように、本実施形態によれば、すべての被認証デバイスが秘密鍵Ｓを共有している場合に、軽量な演算で、複数の被認証デバイス個々のＩＤを特定した上で、一括して認証処理を行うことができる。
【００５３】
＜第３の実施形態＞
図７および図８を用いて、本発明の第３の実施形態について説明する。なお、本実施形態では、すべての被認証デバイス２００が保持する秘密鍵ｘ＿ｉが異なることを前提とする。
【００５４】
＜認証デバイスの構成＞
図７を用いて、本実施形態に係る認証デバイス１００の構成について説明する。
本実施形態に係る認証デバイス１００は、図７に示すように、乱数生成部１３１と、送信部１３２と、演算部１３３と、認証部１３４とから構成されている。
【００５５】
乱数生成部１３１は、乱数Ｒを生成する。送信部１３２は、生成した乱数を複数の被認証デバイス２００に送信する。演算部１３３は、複数の被認証デバイス２００から受信した値を用いて、所定の演算を行い、演算値を求める。認証部１３４は、演算値を検証することにより認証を行う。
【００５６】
＜多重認証システムの処理＞
図８を用いて、本実施形態に係る多重認証システムの処理について説明する。
認証デバイス１００は、乱数Ｒを生成し（ステップＳ３０１）、生成した乱数を複数の被認証デバイス２００に送信する（ステップＳ３０２）。
【００５７】
そして、複数の被認証デバイス２００から受信した値を用いて、所定の演算を行い、演算値を求め（ステップＳ３０３）、演算値を検証することにより認証を行う（ステップＳ３０４）。
【００５８】
以上、説明したように、本実施形態によれば、複数の認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合においても、複数の被認証デバイスを一括して認証することができる。
【００５９】
＜第４の実施形態＞
図９から図１１を用いて、本発明の第４の実施形態について説明する。なお、本実施形態では、すべての被認証デバイス２００において、秘密鍵Ｓが共通であることを前提とする。
【００６０】
＜認証デバイスの構成＞
図９を用いて、本実施形態に係る認証デバイス１００の構成について説明する。
本実施形態に係る認証デバイス１００は、図９に示すように、乱数生成部１３１と、送信部１３２と、認証部１３４、受信部１４１と、演算部１４２とから構成されている。なお、第３の実施形態と同様の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は、省略する。
【００６１】
受信部１４１は、複数の被認証デバイス２が演算した００Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信する。
【００６２】
演算部１４２は、受信したＡ＿ｉをすべて乗算してＡを求め、受信したＢ＿ｉをすべて乗算してＢを求め、受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算する。
【００６３】
＜被認証デバイスの構成＞
図１０を用いて、本実施形態に係る被認証デバイス２００の構成について説明する。
本実施形態に係る被認証デバイス２００は、図１０に示すように、乱数生成部２４１と、演算部２４２とから構成されている。
【００６４】
乱数生成部２４１は、乱数ｒ＿ｉを生成する。演算部２４２は、自己の秘密鍵ｘ＿ｉ、認証デバイス１００の公開鍵ｇｓと秘密鍵ｓと各被認証デバイス２００の公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する。
【００６５】
＜多重認証システムの処理＞
図１１を用いて、本実施形態に係る多重認証システムの処理について説明する。
認証デバイス１００が、乱数Ｒを生成し（ステップＳ４０１）、生成した乱数を複数の被認証デバイスに送信する（ステップＳ４０２）。
【００６６】
複数の被認証デバイス２００がそれぞれ乱数ｒ＿ｉを生成し（ステップＳ４０３）、自己の秘密鍵ｘ＿ｉ、認証デバイス１００の公開鍵ｇｓと秘密鍵ｓと各被認証デバイス２００の公開鍵ｇｘ＿ｉと秘密鍵ｘ＿ｉとハッシュ関数ｈ（）とを用いて、Ａ＿ｉ＝ｇｒ＿ｉ＋ｈ（Ｒ）＋ｘ＿ｉ、Ｂ＿ｉ＝ｇｓｈ（Ｒ）ｘ＿ｉ、Ｃ＿ｉ＝ｇｓｒ＿ｉを演算する（ステップＳ４０４）。
【００６７】
認証デバイスは、Ａ＿ｉ、Ｂ＿ｉ、Ｃ＿ｉを受信し（ステップＳ４０５）、受信したＡ＿ｉをすべて乗算してＡを求め、受信したＢ＿ｉをすべて乗算してＢを求め、受信したＣ＿ｉをすべて乗算してＣを求め、さらに、Ｂ´＝Ｂ（１／ｓｈ（Ｒ））、Ｃ´＝Ｃ（１／ｓ）を演算し、受信したメッセージの個数ｎを用いて、Ａ／Ｂ´／Ｃ´＝ｇｎｈ（Ｒ）を演算する（ステップＳ４０６）。
【００６８】
また、演算値を検証することにより認証を行い（ステップＳ４０７）、複数の被認証デバイス２００の個別のＩＤがｈ（ｇｘ＿ｉ）であり、認証デバイス１００が、求めた各Ｂ＿ｉについて、Ｂ＿ｉ（１／ｓｈ（Ｒ））を演算することにより、認証した複数の被認証デバイス２００のＩＤを取得する（ステップＳ４０８）。
【００６９】
以上、説明したように、本実施形態によれば、すべての被認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合でも、軽量な演算で、一括して認証処理を行うことができる。また、すべての被認証デバイスがそれぞれ異なる秘密鍵ｘ＿ｉを保有している場合でも、それぞれのＩＤを特定した上で、認証処理を行うことができる。
【００７０】
なお、多重認証システムの処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを認証デバイスおよび被認証デバイスに読み込ませ、実行することによって本発明の多重認証システムを実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００７１】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００７２】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００７３】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００７４】
１００；認証デバイス
１１１；乱数生成部
１１２；送信部
１１３；演算部
１１４；認証部
１２１；受信部
１２２；乱数取得部
１２３；演算部
１３１；乱数生成部
１３２；送信部
１３３；演算部
１３４；認証部
１４１；受信部
１４２；演算部
２００；被認証デバイス
２２１；乱数生成部
２２２；暗号化部
２２３；演算部
２４１；乱数生成部
２４２；演算部
【図１】
2012034303.tif 000003
【図２】
2012034303.tif 000004
【図３】
2012034303.tif 000005
【図４】
2012034303.tif 000006
【図５】
2012034303.tif 000007
【図６】
2012034303.tif 000008
【図７】
2012034303.tif 000009
【図８】
2012034303.tif 000010
【図９】
2012034303.tif 000011
【図１０】
2012034303.tif 000012
【図１１】
2012034303.tif 000013