(57)【要約】  認証までの遅延や通信量、計算量を抑え、かつ、安全性の高いブロードキャスト認証を行う。  サーバ（１００）は、共通鍵を用いて生成した、送信データに係るタグと、一方向性関数を用いて生成されたチェインにおける、送信順序に対応するチェイン値と、を合成して、送信データの認証情報を生成する。ノード（２００）は、共通鍵を用いて生成した、受信データに係るタグと、受信データの認証情報と、を用いて抽出したチェイン値に一方向性関数を適用して、過去に受信したデータの送信順序に対応するチェイン値が生成されるかどうかを検証する。
2016067565.tif 000002
【特許請求の範囲】
【請求項１】
送信データに係るタグを、共通鍵を用いて生成する第１のタグ生成手段と、
一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成するチェイン生成手段と、
前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する合成手段と、
前記送信データ、及び、当該送信データの認証情報を、第２の情報処理装置に送信する送信手段と、
を含む、第１の情報処理装置と、
前記第１の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信する受信手段と、
前記受信データに係るタグを、前記共通鍵を用いて生成する第２のタグ生成手段と、
前記受信データの認証情報から当該受信データに係るタグを用いて前記チェインの値を抽出する分離手段と、
前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う検証手段と、
を含む、前記第２の情報処理装置と、
を備えた情報処理システム。
【請求項２】
複数の前記第２の情報処理装置を備え、
前記送信手段は、前記複数の前記第２の情報処理装置に、前記送信データ、及び、当該送信データの認証情報を送信する、
請求項１に記載の情報処理システム。
【請求項３】
前記チェイン生成手段は、前記複数の第２の情報処理装置の内の１以上の第２の情報処理装置を含むグループ毎に前記チェインを生成し、
前記合成手段は、前記送信データの受信対象のグループに対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する、
請求項２に記載の情報処理システム。
【請求項４】
前記第１のタグ生成手段は、複数の共通鍵を用いて、前記送信データに係る複数のタグを、それぞれ生成し、
前記合成手段は、前記送信データの送信順序に対応する前記チェインの値と前記複数のタグとを合成して、当該送信データの複数の認証情報を、それぞれ生成し、
前記送信手段は、前記送信データ、及び、当該送信データの複数の認証情報を送信し、
前記複数の前記第２の情報処理装置には、前記複数の共通鍵の内の、互いに異なる共通鍵が割り当てられ、
前記受信手段は、前記受信データ、及び、当該受信データの複数の認証情報を受信し、
前記第２のタグ生成手段は、前記第２の情報処理装置に割り当てられた共通鍵を用いて、前記受信データに係るタグを生成し、
前記分離手段は、前記受信データの複数の認証情報の内の、前記第２の情報処理装置に割り当てられた共通鍵に対応する認証情報から当該受信データに係るタグを用いて前記チェインの値を抽出する、
請求項２に記載の情報処理システム。
【請求項５】
送信データに係るタグを、共通鍵を用いて生成するタグ生成手段と、
一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成するチェイン生成手段と、
前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する合成手段と、
前記送信データ、及び、当該送信データの認証情報を、前記共通鍵を用いて生成した受信にデータに係るタグと当該受信データの認証情報とを用いて抽出した前記チェインの値に前記一方向性関数を適用して、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかどうかを検証する、他の情報処理装置に送信する送信手段と、
を備えた情報処理装置。
【請求項６】
共通鍵を用いて生成した、送信データに係るタグと、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられたチェインにおける、送信データの送信順序に対応する前記チェインの値と、を合成して、当該送信データの認証情報を生成する、他の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信する受信手段と、
前記受信データに係るタグを、前記共通鍵を用いて生成するタグ生成手段と、
前記受信データの認証情報から当該受信データに係るタグを用いて、前記チェインの値を抽出する分離手段と、
前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う検証手段と、
を備えた情報処理装置。
【請求項７】
第１の情報処理装置において、
送信データに係るタグを、共通鍵を用いて生成し、
一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成し、
前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成し、
前記送信データ、及び、当該送信データの認証情報を、第２の情報処理装置に送信し、
前記第２の情報処理装置において、
前記第１の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信し、
前記受信データに係るタグを、前記共通鍵を用いて生成し、
前記受信データの認証情報から当該受信データに係るタグを用いて前記チェインの値を抽出し、
前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う、
情報処理方法。
【請求項８】
コンピュータに、
送信データに係るタグを、共通鍵を用いて生成し、
一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成し、
前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成し、
前記送信データ、及び、当該送信データの認証情報を、前記共通鍵を用いて生成した受信にデータに係るタグと当該受信データの認証情報とを用いて抽出した前記チェインの値に前記一方向性関数を適用して、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかどうかを検証する、他の情報処理装置に送信する、
処理を実行させるプログラムを格納する、コンピュータが読み取り可能な記録媒体。
【請求項９】
コンピュータに、
共通鍵を用いて生成した、送信データに係るタグと、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられたチェインにおける、送信データの送信順序に対応する前記チェインの値と、を合成して、当該送信データの認証情報を生成する、他の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信し、
前記受信データに係るタグを、前記共通鍵を用いて生成し、
前記受信データの認証情報から当該受信データに係るタグを用いて、前記チェインの値を抽出し、
前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う、
処理を実行させるプログラムを格納する、コンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム、情報処理装置、情報処理方法、及び、記録媒体に関し、特に、メッセージ認証を行う情報処理システム、情報処理装置、情報処理方法、及び、記録媒体に関する。
【背景技術】
【０００２】
ブロードキャスト通信は、サーバ（送信装置）からネットワーク上の複数のノード（受信装置）への同報通信である。サーバから複数のノードへ同一内容を送信する場合には、ブロードキャスト通信を用いることにより、サーバ、ノード間の１対１の通信を繰り返す場合と比較して、通信効率が大きく改善される。このため、ブロードキャスト通信は、テレビ放送やラジオ放送だけではなく、インターネットやセンサネットワークなど、特に、無線通信において有用である。近年、サイバー攻撃の高まりとともに、ブロードキャスト通信においても情報セキュリティの対策が求められており、各ノードが受信したデータがサーバから送信されたデータであることを検証するデータ認証が重要となっている。【０００３】
一般に、ノードは攻撃者が直接アクセス可能なところに設置されることが多い。また、セキュリティ対策は性能低下やコスト増加を伴うことから、ノードにおけるセキュリティ対策は十分でないことが多い。このため、ノードからの秘密情報の漏洩の可能性は、サーバよりも高い。ブロードキャスト通信においては、このような状況を考慮したデータ認証方式が必要である。【０００４】
暗号技術を用いたデータの認証は、大きく、公開鍵暗号を用いたデジタル署名と、共通鍵暗号を用いたメッセージ認証と、の二種類に分類される。【０００５】
デジタル署名では、サーバは署名生成用の秘密鍵を保持し、ノードは署名検証用の公開鍵を保持する。公開鍵暗号の性質から、公開鍵から秘密鍵を推定することは困難であり、攻撃者がノードを攻撃しても署名生成に必要な秘密鍵を得ることはできない。したがって、ブロードキャストデータを改ざんすることは困難である。しかしながら、公開鍵暗号を用いたデジタル署名は、計算量、及び、通信量（署名長）が、共通鍵暗号を用いるメッセージ認証と比較して非常に大きいという問題がある。このため、センサ等の小型ノードにより構成されるネットワークでは、複雑度が低い、メッセージ認証を用いることが望ましい。【０００６】
図１０は、一般的なメッセージ認証の仕組みを示す図である。【０００７】
メッセージ認証では、サーバとノードとが秘密鍵を事前に共有する。サーバは、暗号処理によって、送信データＤとカウンタ値ｎからタグＴを生成し、データＤとともに送信する。カウンタ値ｎは再送攻撃を防ぐために用いられ、パケット等、認証処理が行われる対象毎にインクリメントされる。ノードは、受信したカウンタ値を保持しており、受信したカウンタ値ｎ’が現在保持しているカウンタ値から適切に更新されている場合、受信したデータが、再送攻撃により送信されたデータではないと判定する。この判定をパスすれば、ノードはサーバと同様に、暗号処理によって、受信したデータＤ’とカウンタ値ｎ’からタグを生成する。生成したタグが受信したタグＴ’と一致すれば、ノードは、受信したデータＤ’が、サーバからの正しいデータ（Ｄ’＝Ｄ）であると判定する。【０００８】
メッセージ認証処理としては、ブロック暗号を用いる方式であれば、非特許文献１に開示されているような、ＣＢＣ−ＭＡＣ（Cipher Block Chaining MAC algorithm）に基づくＣＭＡＣ（Cipher Block Chaining MAC algorithm）が用いられることが多い。また、暗号学的なハッシュ関数を用いる方式であれば、非特許文献２に開示されているような、ＨＭＡＣ（Keyed-Hash Message Authentication Code）が利用されることが多い。【０００９】
ブロードキャスト通信におけるメッセージ認証（以下、ブロードキャスト認証と呼ぶ）は、例えば、サーバと全てのノードとが秘密鍵を共有することで実現できる。このとき、一つのノードから秘密鍵が漏洩すると、ブロードキャストデータに対する改ざんが非常に容易に可能となり、全てのノードが影響を受ける。【００１０】
共通鍵暗号を用いたブロードキャスト認証の安全性を高める一つの方法として、複数の秘密鍵を用いたメッセージ認証がある。サーバは、秘密鍵の集合Ｌを保持し、ノードｕは、集合Ｌの部分集合Ｌ（ｕ）を保持する。サーバは、ブロードキャストするデータに対して、集合Ｌの全ての秘密鍵を用いてタグを生成し、データとともに送信する。ノードｕは、受信データから部分集合Ｌ（ｕ）の全ての秘密鍵を用いてタグを生成する。ノードｕは、生成したタグと受信したタグに含まれる対応するタグとが全て一致すれば、受信データがサーバから送信されたデータであると判定する。【００１１】
また、共通鍵暗号を用いたブロードキャスト認証の安全性を高める他の方法として、非特許文献３に開示されている、ＴＥＳＬＡ（Timed Efficient loSs-toLerant Authentication）がある。【００１２】
ＴＥＳＬＡでは、サーバは、メッセージ認証の秘密鍵を一方向性チェインを用いて生成する。サーバは、ランダムな秘密鍵Ｋ［ｎ］、及び、一方向性関数ｆを用いて、数１式により、秘密鍵Ｋ［ｎ−１］、…、Ｋ［０］を算出する。【００１３】
【数１】
2016067565.tif 000003
【００１４】
ここで、Ｎはチェインの長さである。チェインの長さは、サーバからノードへの秘密鍵Ｋ［０］の一度の設定に対して、実行可能なメッセージ認証の回数を決めるパラメータである。初期設定において、サーバは、この秘密鍵のチェインを生成して保持するとともに、ノードに秘密鍵Ｋ［０］を設定する。秘密鍵Ｋ［０］の設定には、サーバと各ノードの１対１の通信や、通常のデジタル署名が用いられる。デジタル署名が用いられる場合、ノードにおいて受信した秘密鍵Ｋ［０］が、サーバから送信された秘密鍵Ｋ［０］であることが検証される。【００１５】
ＴＥＳＬＡでは、サーバは、データＤ［１］、…、Ｄ［ｎ］をブロードキャストするときに、それぞれ、秘密鍵Ｋ［１］、…、Ｋ［ｎ］を用いてメッセージ認証のタグを生成し、送信する。データＤ［ｉ］がタイムスロット内の送信データ全体を表す場合、サーバは、データＤ［ｉ］の中の各送信データに対して、秘密鍵Ｋ［ｉ］を用いてタグを生成する。【００１６】
サーバは、データＤ［ｉ］を送信後一定時間が経ってから、秘密鍵Ｋ［ｉ］を送信する。ノードは、秘密鍵Ｋ［ｉ’］（ｉ’＜ｉ）を保持している。ノードは、秘密鍵Ｋ［ｉ］を受信後に、秘密鍵Ｋ［ｉ］に対して一方向性関数ｆを（ｉ−ｉ’）回適用した値と保持されている秘密鍵Ｋ［ｉ’］との一致を検証することで、秘密鍵Ｋ［ｉ］がサーバから送信された正しい秘密鍵Ｋ［ｉ］であることを確認する。ノードは、秘密鍵Ｋ［ｉ］の検証後にデータＤ［ｉ］の認証を行う。また、ノードは、秘密鍵Ｋ［ｉ］を保持することで、秘密鍵Ｋ［ｉ＋１］の受信に備える。【００１７】
ＴＥＳＬＡでは、データとメッセージ認証のタグの送信に対して、秘密鍵の開示を遅らせることにより、ノードが、受信データが正しい秘密鍵を知っているサーバからのデータであることを確認できる。また、サーバがデータＤ［ｉ］を送信する時点で、ノードは秘密鍵Ｋ［ｉ］を保持していない。このため、ノードを攻撃しても攻撃者はこの時点で秘密鍵Ｋ［ｉ］を入手できず、データＤ［ｉ］以外のデータに対するタグＴ［ｉ］を生成することは困難である。また、一般的な１対１通信のメッセージ認証と比較して、通信量や計算量の増加量は比較的小さく、効率が良い。【００１８】
なお、関連技術として、特許文献１には、公開鍵暗号を用いたデジタル署名方式において、一方向性関数を用いる技術が開示されている。また、特許文献２には、一方向関数により生成された認証情報を用いて、装置間通信における認証を行う技術が開示されている。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特開２００３−３１８８８４号公報
【特許文献２】特開２０１０−２５２２７５号公報
【非特許文献】
【００２０】
【非特許文献１】Morris Dworkin、「Recommendation for Block Cipher Modes of Operation: The CMAC mode for Authentication」、[online]、2005年5月、NIST Special Publication 800-38B、National Institute of Standards and Technology、2014年10月10日検索]、インターネット<http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf>
【非特許文献２】「The Keyed-Hash Message Authentication Code (HMAC) 」、[online]、2008年7月、FIPS PUB 198-1 (FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION)、Information Technology Laboratory National Institute of Standards and Technology、[平成2014年10月10日検索]、インターネット<http://csrc.nist.gov/publications/fips/fips198-1/FIPS-198-1_final.pdf>
【非特許文献３】Adrian Perring, Ran Canetti, J.D. Tygar, and Dawn Song、「Efficient Authentication and Signing for Multicast Streams over lossy Channels」、Proceeding of the 2000 IEEE Symposium on Security and Privacy、2005年5月、p.56-73
【発明の概要】
【発明が解決しようとする課題】
【００２１】
上述のブロードキャスト認証の安全性を高める方法の内、複数の秘密鍵を用いたメッセージ認証では、サーバは、秘密鍵の集合Ｌの大きさに比例したタグを送信する必要がある。大規模なネットワークで安全性を高めるためには、秘密鍵の集合Ｌを大きくする必要があるため、送信するタグの長さが長くなる。このため、メッセージ認証の利点である、認証情報の通信オーバーヘッド削減の効果が小さい。【００２２】
一方、ＴＥＳＬＡを用いたメッセージ認証では、ノードがデータＤ［ｉ］、タグＴ［ｉ］を受信前にサーバから秘密鍵Ｋ［ｉ］が開示されてしまうと、攻撃者は、偽データをそのノードに受信させることができる。すなわち、攻撃者は、秘密鍵Ｋ［ｉ］を入手しているため、任意のデータに対して秘密鍵Ｋ［ｉ］でタグを生成して送信し、その後に秘密鍵Ｋ［ｉ］を開示することで、偽データを受信させることができる。したがって、サーバは、全てのノードがデータＤ［ｉ］とタグＴ［ｉ］を受信した後で秘密鍵Ｋ［ｉ］を受信できるように、十分な余裕を持って秘密鍵Ｋ［ｉ］を送信する必要がある。このため、ノードにおけるデータ受信から認証までの間で大きな遅延が発生する。【００２３】
本発明の目的は、上述の課題を解決し、認証までの遅延や通信量、計算量を抑え、かつ、安全性の高いブロードキャスト認証ができる、情報処理システム、情報処理装置、情報処理方法、及び、記録媒体を提供することである。
【課題を解決するための手段】
【００２４】
本発明の一態様における情報処理システムは、送信データに係るタグを、共通鍵を用いて生成する第１のタグ生成手段と、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成するチェイン生成手段と、前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する合成手段と、前記送信データ、及び、当該送信データの認証情報を、第２の情報処理装置に送信する送信手段と、を含む、第１の情報処理装置と、前記第１の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信する受信手段と、前記受信データに係るタグを、前記共通鍵を用いて生成する第２のタグ生成手段と、前記受信データの認証情報から当該受信データに係るタグを用いて前記チェインの値を抽出する分離手段と、前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う検証手段と、を含む、前記第２の情報処理装置と、を備える。【００２５】
本発明の一態様における第１の情報処理装置は、送信データに係るタグを、共通鍵を用いて生成するタグ生成手段と、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成するチェイン生成手段と、前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する合成手段と、前記送信データ、及び、当該送信データの認証情報を、前記共通鍵を用いて生成した受信にデータに係るタグと当該受信データの認証情報とを用いて抽出した前記チェインの値に前記一方向性関数を適用して、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかどうかを検証する、他の情報処理装置に送信する送信手段と、を備える。【００２６】
本発明の一態様における第２の情報処理装置は、共通鍵を用いて生成した、送信データに係るタグと、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられたチェインにおける、送信データの送信順序に対応する前記チェインの値と、を合成して、当該送信データの認証情報を生成する、他の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信する受信手段と、前記受信データに係るタグを、前記共通鍵を用いて生成するタグ生成手段と、前記受信データの認証情報から当該受信データに係るタグを用いて、前記チェインの値を抽出する分離手段と、前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う検証手段と、を備える。【００２７】
本発明の一態様における情報処理方法は、第１の情報処理装置において、送信データに係るタグを、共通鍵を用いて生成し、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成し、前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成し、前記送信データ、及び、当該送信データの認証情報を、第２の情報処理装置に送信し、前記第２の情報処理装置において、前記第１の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信し、前記受信データに係るタグを、前記共通鍵を用いて生成し、前記受信データの認証情報から当該受信データに係るタグを用いて前記チェインの値を抽出し、前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う。【００２８】
本発明の一態様におけるコンピュータが読み取り可能な第１の記録媒体は、コンピュータに、送信データに係るタグを、共通鍵を用いて生成し、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成し、前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成し、前記送信データ、及び、当該送信データの認証情報を、前記共通鍵を用いて生成した受信にデータに係るタグと当該受信データの認証情報とを用いて抽出した前記チェインの値に前記一方向性関数を適用して、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかどうかを検証する、他の情報処理装置に送信する、処理を実行させる処理を実行させるプログラムを格納する。【００２９】
本発明の一態様におけるコンピュータが読み取り可能な第２の記録媒体は、共通鍵を用いて生成した、送信データに係るタグと、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられたチェインにおける、送信データの送信順序に対応する前記チェインの値と、を合成して、当該送信データの認証情報を生成する、他の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信し、前記受信データに係るタグを、前記共通鍵を用いて生成し、前記受信データの認証情報から当該受信データに係るタグを用いて、前記チェインの値を抽出し、前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う、処理を実行させるプログラムを格納する。
【発明の効果】
【００３０】
本発明の効果は、認証までの遅延や通信量、計算量を抑え、かつ、安全性の高いブロードキャスト認証を実行できることである。
【図面の簡単な説明】
【００３１】
【図１】本発明の第１の実施の形態の特徴的な構成を示すブロック図である。
【図２】本発明の第１実施の形態における、ブロードキャスト認証システム１の構成を示すブロック図である。
【図３】本発明の第１の実施の形態における、チェイン生成部１５０の構成を示すブロック図である。
【図４】本発明の第１の実施の形態における、検証部２６０の構成を示すブロック図である。
【図５】本発明の第１の実施の形態における、コンピュータにより実現されたサーバ１００、及び、ノード２００の構成を示すブロック図である。
【図６】本発明の第１の実施の形態における、ブロードキャスト認証システム１の動作を示すフローチャートである。
【図７】本発明の第１の実施の形態のサーバ１００における、事前処理（ステップＳ１２）の詳細を示すフローチャートである。
【図８】本発明の第１の実施の形態のサーバ１００における、認証情報生成処理（ステップＳ１３）の詳細を示すフローチャートである。
【図９】本発明の第１の実施の形態のノード２００における、認証情報検証処理（ステップＳ２３）の詳細を示すフローチャートである。
【図１０】一般的なメッセージ認証の仕組みを示す図である。
【発明を実施するための形態】
【００３２】
本発明を実施するための形態について図面を参照して詳細に説明する。なお、各図面、及び、明細書記載の各実施形態において、同様の構成要素には同一の符号を付与し、説明を適宜省略する。また、図面中の矢印の方向は一例を示すものであり、本発明の実施形態を限定するものではない。
【００３３】
（第１の実施の形態）
本発明の第１の実施の形態について説明する。
【００３４】
はじめに、本発明の第１の実施の形態の構成を説明する。
【００３５】
図２は、本発明の第１実施の形態における、ブロードキャスト認証システム１の構成を示すブロック図である。
【００３６】
図２を参照すると、ブロードキャスト認証システム１は、サーバ１００、及び、１以上のノード２００を含む。サーバ１００とノード２００とは、ネットワーク等により、通信可能に接続される。サーバ１００は、同じデータ（または、メッセージ）を、通信可能に接続された全ノード２００に同報（ブロードキャスト）する。各ノード２００は、サーバ１００により送信されたデータを受信する。なお、ブロードキャスト認証システム１は、本発明の情報処理システムの一実施形態である。また、サーバ１００、及び、ノード２００は、それぞれ、本発明の第１、及び、第２の情報処理装置の一実施形態である。
【００３７】
サーバ１００は、データ送信部１１０（または、単に、送信部）、及び、認証情報生成部１２０を含む。
【００３８】
データ送信部１１０は、送信データの送信順序を示すカウンタ値、当該送信データ、及び、当該送信データに係る認証情報を、ノード２００に送信する。認証情報生成部１２０は、認証情報を生成する。
【００３９】
認証情報生成部１２０は、タグ生成部１３０（または、第１のタグ生成部）、共通鍵記憶部１４０、チェイン生成部１５０、及び、合成部１６０を含む。
【００４０】
タグ生成部１３０は、図１０のタグ生成部と同様に、送信データに係る、メッセージ認証のためのタグを生成する。タグ生成部１３０は、送信データに係るカウンタ値と送信データを入力として、ノード２００との間で共有している秘密鍵（共通鍵）を用いてタグを生成する。
【００４１】
共通鍵記憶部１４０は、ノード２００との間で共有する秘密鍵を記憶する。
【００４２】
チェイン生成部１５０は、一方向性チェイン（または、単にチェイン）を生成する。図３は、本発明の第１の実施の形態における、チェイン生成部１５０の構成を示すブロック図である。
【００４３】
チェイン生成部１５０は、チェイン算出部１５１、チェイン記憶部１５２、及び、チェイン出力部１５３を含む。
【００４４】
チェイン算出部１５１は、事前処理において、一方向性関数を用いて、一方向性チェインを算出する。チェイン記憶部１５２は、チェイン算出部１５１により算出された一方向性チェインを記憶する。チェイン出力部１５３は、認証情報生成処理において、一方向性チェインから、送信データの送信順序に対応するチェイン値を出力する。
【００４５】
合成部１６０は、送信データに係るタグと送信データの送信順序に対応するチェイン値とを合成することにより、認証情報を生成する。
【００４６】
ノード２００は、データ受信部２１０（または、単に、受信部）、及び、認証情報検証部２２０を含む。
【００４７】
データ受信部２１０は、受信データの送信順序を示すカウンタ値、当該受信データ、及び、当該受信データに係る認証情報を受信する。認証情報検証部２２０は認証情報を用いて、受信データを認証する。
【００４８】
認証情報検証部２２０は、タグ生成部２３０（または、第２のタグ生成部）、共通鍵記憶部２４０、分離部２５０、及び、検証部２６０を含む。
【００４９】
タグ生成部２３０は、タグ生成部１３０と同様に、受信データに係る、メッセージ認証のためのタグを生成する。タグ生成部２３０は、受信したカウンタ値と受信データを入力として、サーバ１００との間で共有している秘密鍵（共通鍵）を用いてタグを生成する。
【００５０】
共通鍵記憶部２４０は、サーバ１００との間で共有する秘密鍵を記憶する。
【００５１】
分離部２５０は、受信した認証情報から、受信データに係るタグを用いて、チェイン値を抽出（分離）する。
【００５２】
検証部２６０は、認証情報から抽出されたチェイン値を用いて、受信データを認証する。図４は、本発明の第１の実施の形態における、検証部２６０の構成を示すブロック図である。
【００５３】
検証部２６０は、前回値記憶部２６１、及び、比較部２６２を含む。
【００５４】
前回値記憶部２６１は、前回（過去）の受信データに係るカウンタ値、及び、チェイン値を記憶する。
【００５５】
比較部２６２は、一方向関数と、前回の受信データに係るカウンタ値、及び、チェイン値と、を用いて、新たな受信データに係るカウンタ値、及び、認証情報から抽出されたチェイン値が正しいかどうかを検証する。
【００５６】
なお、サーバ１００、及び、ノード２００は、それぞれ、ＣＰＵ（Central Processing Unit）とプログラムを記憶した記憶媒体を含み、プログラムに基づく制御によって動作するコンピュータであってもよい。
【００５７】
図５は、本発明の第１の実施の形態における、コンピュータにより実現されたサーバ１００、及び、ノード２００の構成を示すブロック図である。
【００５８】
サーバ１００は、ＣＰＵ１０１、ハードディスクやメモリ等の記憶手段（記憶媒体）１０２、他の装置等と通信を行う通信手段１０３、キーボード等の入力手段１０４、及び、ディスプレイ等の出力手段１０５を含む。ＣＰＵ１０１は、データ送信部１１０、タグ生成部１３０、チェイン算出部１５１、チェイン出力部１５３、及び、合成部１６０の機能を実現するためのコンピュータプログラムを実行する。記憶手段１０２は、共通鍵記憶部１４０、及び、チェイン記憶部１５２のデータを記憶する。通信手段１０３は、ノード２００へ、データ等を送信（ブロードキャスト）する。入力手段１０４は、ユーザ等から、データ送信の指示等の入力を受け付ける。出力手段１０５は、ユーザ等へ、データ送信の実行結果等を出力する。
【００５９】
なお、サーバ１００の各構成要素は、独立した論理回路でもよい。
【００６０】
ノード２００は、同様に、ＣＰＵ２０１、記憶手段２０２、通信手段２０３、入力手段２０４、及び、出力手段２０５を含む。ＣＰＵ２０１は、データ受信部２１０、タグ生成部２３０、分離部２５０、及び、比較部２６２の機能を実現するためのコンピュータプログラムを実行する。記憶手段２０２は、共通鍵記憶部２４０、及び、前回値記憶部２６１のデータを記憶する。通信手段２０３は、サーバ１００から、データ等を受信する。入力手段２０４は、ユーザ等から、データ受信の実行指示等の入力を受け付ける。出力手段２０５は、ユーザ等へ、受信データの検証結果を含む、データ受信の実行結果等を出力する。
【００６１】
なお、ノード２００の各構成要素は、独立した論理回路でもよい。
【００６２】
次に、本発明の第１の実施の形態の動作について説明する。
【００６３】
図６は、本発明の第１の実施の形態における、ブロードキャスト認証システム１の動作を示すフローチャートである。
【００６４】
はじめに、サーバ１００の動作を説明する。
【００６５】
サーバ１００のデータ送信部１１０は、カウンタ値ｎ（ｎは１以上の整数）に１を設定する（ステップＳ１１）。
【００６６】
データ送信部１１０は、認証情報生成部１２０に、事前処理の実行を指示する。認証情報生成部１２０は、事前処理を実行する（ステップＳ１２）。
【００６７】
図７は、本発明の第１の実施の形態のサーバ１００における、事前処理（ステップＳ１２）の詳細を示すフローチャートである。
【００６８】
チェイン生成部１５０のチェイン算出部１５１は、一方向性関数を用いて、一方向性チェインを算出する（ステップＳ１２１）。チェイン算出部１５１は、算出した一方向性チェインを、チェイン記憶部１５２に保存する。ここで、一方向性関数ｆ（ｘ）は、ハッシュ関数等、ｆ（ｘ）から逆像ｘを求めることが非常に困難という性質を有する関数である。一方向性チェインは、ある値に一方向性関数を繰り返し適用することにより得られる値（チェイン値）の系列である。チェイン算出部１５１は、数２式により、一方向性チェインにおけるチェイン値を算出する。
【００６９】
【数２】
2016067565.tif 000004
【００７０】
ここで、ｈ［ｉ］はチェイン値、Ｎは一方向性チェインの更新間隔（事前処理の間隔）を決めるパラメータ（チェイン長）である。初期値ｈ［Ｎ］には、例えば、事前処理ごとに決定される乱数が用いられる。得られた一方向性チェインは、数３式のように表される。
【００７１】
【数３】
2016067565.tif 000005
【００７２】
なお、チェイン記憶部１５２は、数３におけるチェイン値の全てを記憶する必要はなく、所定の間隔で部分的に（間引いて）記憶してもよい。この場合、チェイン算出部１５１が、必要に応じて、記憶していないチェイン値を、数２式を用いて生成する。
【００７３】
チェイン算出部１５１は、Ｎ番目に算出されたチェイン値ｈ［０］を、全ノード２００に送信する（ステップＳ１２２）。チェイン値ｈ［０］の送信における改ざん検出には、サーバ１００と各ノード２００の１対１の安全な通信や、通常のデジタル署名が用いられる。上述のパラメータＮが十分に大きければ、事前処理の頻度は小さくなり、これに伴うオーバーヘッドも十分に小さくすることができる。
【００７４】
次に、データ送信部１１０は、認証情報生成部１２０に、カウンタ値ｎ、及び、ｎ番目の送信データＤ［ｎ］を入力し、認証情報生成処理の実行を指示する。認証情報生成部１２０は、認証情報生成処理を実行する（ステップＳ１３）。
【００７５】
図８は、本発明の第１の実施の形態のサーバ１００における、認証情報生成処理（ステップＳ１３）の詳細を示すフローチャートである。
【００７６】
認証情報生成部１２０のタグ生成部１３０はカウンタ値ｎ、及び、送信データＤ［ｎ］から、メッセージ認証のためのタグＴ［ｎ］を生成する（ステップＳ１３１）。ここで、タグ生成部１３０は、共通鍵記憶部１４０に記憶されている秘密鍵を用いて、タグＴ［ｎ］を生成する。
【００７７】
チェイン生成部１５０のチェイン出力部１５３は、チェイン記憶部１５２に記憶されている一方向性チェインから、送信データＤ［ｎ］の送信順序（カウンタ値ｎ）に対応するチェイン値ｈ［ｎ］を取得し、出力する（ステップＳ１３２）。ここで、送信データとチェイン値とは、各送信データの送信順序と一方向性チェインにおけるチェイン値の生成順序が逆順になるように対応づけられる。すなわち、チェイン出力部１５３は、順番に送信される送信データＤ［１］、Ｄ［２］、…、Ｄ［Ｎ］に対して、それぞれ、チェイン値ｈ［１］、ｈ［２］、…、ｈ［Ｎ］を出力する。
【００７８】
合成部１６０は、タグＴ［ｎ］とチェイン値ｈ［ｎ］とを合成し、認証情報Ａ［ｎ］を生成する（ステップＳ１３３）。合成部１６０は、生成した認証情報Ａ［ｎ］を、データ送信部１１０へ出力する。ここで、合成部１６０は、例えば、タグＴ［ｎ］とチェイン値ｈ［ｎ］との排他的論理和によって、認証情報Ａ［ｎ］を生成する。合成部１６０による合成処理は、数４式のように表される。
【００７９】
【数４】
2016067565.tif 000006
【００８０】
ここで、”＋”は、排他的論理和等の合成処理を示す。
【００８１】
次に、データ送信部１１０は、カウンタ値ｎ、送信データＤ［ｎ］、及び、認証情報Ａ［ｎ］を、全てのノード２００に送信（ブロードキャスト）する（ステップＳ１４）。
【００８２】
カウンタ値ｎがチェイン長Ｎより小さい場合（ステップＳ１５／Ｙ）、データ送信部１１０は、カウンタ値に１を加算し（ステップＳ１６）、ステップＳ１３からの処理を繰り返す。
【００８３】
一方、カウンタ値ｎがチェイン長Ｎと等しい場合（ステップＳ１５／Ｎ）、ステップＳ１１からの処理が繰り返される。これにより、データがＮ回送信される毎に、事前処理が行われる。
【００８４】
なお、事前処理において、メッセージ認証の秘密鍵の更新が、併せて実行されてもよい。
【００８５】
次に、ノード２００の動作を説明する。
【００８６】
ノード２００が、サーバ１００から、事前処理により生成されたチェイン値ｈ［０］を受信すると、検証部２６０は、前回値記憶部２６１に、カウンタ値ｍ＝０、及び、受信したチェイン値ｈ［０］を保存する（ステップＳ２１）。
【００８７】
次に、データ受信部２１０は、サーバ１００から、カウンタ値ｎ’、受信データＤ’［ｎ’］、及び、認証情報Ａ’［ｎ’］を受信する（ステップＳ２２）。
【００８８】
データ受信部２１０は、認証情報検証部２２０に、カウンタ値ｎ’、受信データＤ’［ｎ’］、及び、認証情報Ａ’［ｎ’］を入力し、認証情報検証処理の実行を指示する。認証情報検証部２２０は、認証情報検証処理を実行する（ステップＳ２３）。
【００８９】
図９は、本発明の第１の実施の形態のノード２００における、認証情報検証処理（ステップＳ２３）の詳細を示すフローチャートである。
【００９０】
検証部２６０の比較部２６２は、カウンタ値ｎ’が前回値記憶部２６１に保存されているカウンタ値ｍ以下か、或いは、チェイン長Ｎより大きいかを判定する（ステップＳ２３１）。カウンタ値ｎ’がｍ以下、或いは、チェイン長Ｎより大きい場合（ステップＳ２３１／Ｙ）、比較部２６２は、「認証失敗」を出力する（ステップＳ２３８）。
【００９１】
カウンタ値ｎ’がカウンタ値ｍより大きく、かつ、チェイン長Ｎ以下の場合（ステップＳ２３１／Ｎ）、タグ生成部２３０は、カウンタ値ｎ’、及び、受信データＤ’［ｎ’］から、メッセージ認証のためのタグＴ’［ｎ’］を生成する（ステップＳ２３２）。ここで、タグ生成部２３０は、共通鍵記憶部２４０に記憶されている秘密鍵を用いて、タグＴ’［ｎ’］を生成する。
【００９２】
分離部２５０は、認証情報Ａ’［ｎ’］から、タグＴ’［ｎ’］を用いて、チェイン値ｈ’［ｎ’］を抽出（分離）する（ステップＳ２３３）。ここで、合成部１６０が、例えば、排他的論理和によって認証情報を生成する場合、分離部２５０も、排他的論理和によってチェイン値ｈ’［ｎ’］を抽出する。分離部２５０による分離処理は、数５式のように表される。
【００９３】
【数５】
2016067565.tif 000007
【００９４】
検証部２６０の比較部２６２は、チェイン値ｈ’［ｎ’］に対して一方向性関数を適用し、カウンタ値ｍに対するチェイン値ｈ’’［ｍ］を算出する（ステップＳ２３４）。比較部２６２は、数６式により、チェイン値ｈ’’［ｍ］を算出する。
【００９５】
【数６】
2016067565.tif 000008
【００９６】
ここで、ｆ＾（ｎ’−ｍ）（ｈ’［ｎ’］）は、チェイン値ｈ’［ｎ’］に、一方向性関数ｆ（ｘ）を（ｎ’−ｍ）回適用することを示す。
【００９７】
比較部２６２は、算出したチェイン値ｈ’’［ｍ］が、前回値記憶部２６１に記憶されているチェイン値ｈ［ｍ］と等しいかどうかを判定する（ステップＳ２３５）。チェイン値ｈ’’［ｍ］がチェイン値ｈ［ｍ］と等しい場合（ステップＳ２３５／Ｙ）、比較部２６２は、前回値記憶部２６１に記憶されているカウンタ値ｍ、チェイン値ｈ［ｍ］を、カウンタ値ｎ’、チェイン値ｈ’［ｎ’］で更新する（ステップＳ２３６）。そして、比較部２６２は、検証結果として、カウンタ値ｎ’、及び、受信データＤ’［ｎ’］が、サーバ１００より送信された正しいデータであることを示す「認証成功」を出力する（ステップＳ２３７）。
【００９８】
一方、チェイン値ｈ’’［ｍ］がチェイン値ｈ［ｍ］と異なる場合（ステップＳ２３５／Ｎ）、比較部２６２は、検証結果として、「認証失敗」を出力する（ステップＳ２３８）。
【００９９】
なお、上述のステップＳ２３１で、カウンタ値ｎ’がチェイン長Ｎ以下でも、（ｎ’−ｍ）が大きい場合は、数６式における一方向性関数の実行回数が大きくなる。これを避けるため、ステップＳ２３１において、（ｎ’−ｍ）が所定値より大きい場合、「認証失敗」を出力してもよい。
【０１００】
以降、ステップＳ２２からの処理が繰り返し実行される。
【０１０１】
以上により、本発明の第１の実施の形態の動作が完了する。
【０１０２】
なお、本発明の第１の実施の形態では、ブロードキャスト通信を例に、動作を説明した。しかしながら、これに限らず、本発明の第１の実施の形態は、サーバ１００から通信可能に接続され接続されたノード２００の内の一部のノード２００のグループへの同報である、マルチキャスト通信にも適用できる。
【０１０３】
この場合、サーバ１００のチェイン生成部１５０は、一方向性チェインを、マルチキャストを行うグループ（マルチキャストグループ）毎に生成し、当該一方向性チェインのチェイン値ｈ［０］を、当該マルチキャストグループに属するノード２００に送信する。サーバ１００からの送信回数を表すカウンタも、マルチキャストグループ毎に設定される。合成部１６０は、マルチキャストグループに対応するチェイン値と送信データに係るタグとを合成して、送信データの認証情報を生成する。
【０１０４】
また、タグ生成部１３０、２３０におけるタグ生成には、非特許文献１に開示されているＣＭＡＣや、非特許文献２に開示されているＨＭＡＣ等を適用してもよい。
【０１０５】
また、チェイン生成部１５０や検証部２６０における一方向性関数には、非特許文献２で用いられているＳＨＡ（Secure Hash Algorithm）−１やＳＨＡ−２５６等の暗号学的なハッシュ関数を適用してもよい。一方向性チェインのチェイン値は、メッセージ認証のタグ長と同一となることが望ましいため、必要に応じてこれらのハッシュ関数の出力をタグ長で打ち切って得られる値が用いられる。メッセージ認証のタグの典型的な長さは、６４から１２８ビットである。
【０１０６】
また、一方向性関数により生成される一方向性チェインに、ランダムなＩＤ（Identifier）を割り当てることにより、チェイン間の独立性を高めてもよい。この場合、チェイン生成部１５０は、例えば、数７式のような一方向関数を用いて、一方向性チェインにおけるチェイン値を算出する。
【０１０７】
【数７】
2016067565.tif 000009
【０１０８】
ここで、Ｈ（）はハッシュ関数、ＲはランダムなＩＤである。また、ｔｒｕｎｃ（）は、上述のように、出力をメッセージ認証のタグ長で打ち切ることを示し、｜｜は、ビット列の連結を表す。Ｒは、ｈ［Ｎ］と同様に、サーバ１００の事前処理ごとに決定される乱数であり、ｈ［０］とともにノード２００に設定される。これにより、攻撃者が一方向性チェインを事前に生成して推測を行うような攻撃への耐性を向上できる。
【０１０９】
また、チェイン生成部１５０は、数７式におけるハッシュ関数において、数８式のようにｉも含めた値に対するハッシュ値を算出することにより、当該攻撃への耐性をさらに向上できる。
【０１１０】
【数８】
2016067565.tif 000010
【０１１１】
また、チェイン長Ｎに、メッセージ認証の秘密鍵の更新間隔内におけるデータの送信回数より大きい値を設定し、秘密鍵の更新と合わせて、事前処理により、次の一方向性チェインを生成してもよい。例えば、データの送信回数が高々１時間に１回、鍵更新間隔が1か月に１回の場合、秘密鍵の更新間隔内におけるデータの送信回数は高々８００程度である。この場合、マージンを考慮して、チェイン長Ｎには１０００から２０００程度が設定される。
【０１１２】
また、チェイン長Ｎを大きくすることは、サーバ１００の事前処理、及び、一方向性チェインを記憶するためのストレージ量に影響する。そのため、上述のように、チェイン記憶部１５２が、一方向性チェインにおけるチェイン値を間引いて記憶することで、ストレージ量とデータ送信時にチェイン値を算出するために必要な計算量や遅延とのトレードオフを図ることができる。
【０１１３】
典型的には、チェイン記憶部１５２が、Ｎ＾（１／２）の間隔でチェイン値ｈ［ｉ］を記憶し、チェイン算出部１５１が、高々Ｎ＾（１／２）回の一方向性関数ｆの処理で、ｈ［ｎ］を算出する。チェイン記憶部１５２は、例えば、Ｎ＝１０，０００であれば、事前処理において、チェイン値ｈ［０］、ｈ［１００］、ｈ［２００］、…、ｈ［９９００］、及び、ｈ［１００００］を記憶する。ここで、例えば、ｈ［１０１］を算出する場合には、チェイン算出部１５１が、ｈ［２００］に、一方向性関数ｆを９９回適用する。さらに、チェイン記憶部１５２が、この過程で算出されたｈ［ｉ］の内のいくつか記憶することで、１０１≦ｎ＜２００に対してｈ［ｎ］を算出するための計算量を抑えることができる。
【０１１４】
次に、本発明の第１の実施の形態の特徴的な構成を説明する。図１は、本発明の第１の実施の形態の特徴的な構成を示すブロック図である。
【０１１５】
図１を参照すると、ブロードキャスト認証システム１（情報処理システム）は、サーバ１００（第１の情報処理装置）、及び、ノード２００（第２の情報処理装置）を含む。
【０１１６】
サーバ１００は、タグ生成部１３０（第１のタグ生成部）、チェイン生成部１５０、合成部１６０、及び、データ送信部１１０（送信部）を含む。ここで、タグ生成部１３０は、送信データに係るタグを、共通鍵を用いて生成する。チェイン生成部１５０は、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成する。合成部１６０は、送信データの送信順序に対応するチェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する。データ送信部１１０は、送信データ、及び、当該送信データの認証情報を、ノード２００に送信する。
【０１１７】
ノード２００は、データ受信部２１０（受信部）、タグ生成部２３０（第２のタグ生成部）、分離部２５０、及び、検証部２６０を含む。ここで、データ受信部２１０は、サーバ１００から、受信データ、及び、当該受信データの認証情報を受信する。タグ生成部２３０は、受信データに係るタグを、共通鍵を用いて生成する。分離部２５０は、受信データの認証情報から当該受信データに係るタグを用いてチェインの値を抽出する。検証部２６０は、受信データの認証情報から抽出されたチェインの値に一方向性関数を適用することにより、過去に受信したデータの送信順序に対応するチェインの値が生成されるかを検証することにより、当該受信データの認証を行う。
【０１１８】
次に、本発明の第１の実施の形態の効果を説明する。
【０１１９】
本発明の第１の実施の形態の効果は、認証までの遅延や通信量、計算量を抑え、かつ、安全性の高いブロードキャスト認証を実行できることである。その理由は、以下の通りである。
【０１２０】
すなわち、サーバ１００は、共通鍵を用いて生成した、送信データに係るタグと、一方向性関数を用いて生成されたチェインにおける、送信順序に対応するチェイン値と、を合成して、送信データの認証情報を生成する。ノード２００は、共通鍵を用いて生成した、受信データに係るタグと、受信データの認証情報と、を用いて抽出したチェイン値に一方向性関数を適用して、過去に受信したデータの送信順序に対応するチェイン値が生成されるかどうかを検証する。
【０１２１】
このように、本発明の第１の実施の形態では、サーバ１００とノード２００とが、秘密鍵（共通鍵）を事前に共有し、データと認証情報とを同時に送受信する。このため、ＴＥＳＬＡと異なり、データ受信から受信データの認証までの遅延が発生しない。
【０１２２】
また、本発明の第１の実施の形態では、データと同時に送受信される認証情報の大きさは、共通鍵を用いて生成されるタグと同じにできる。このため、一般的な１対１通信のメッセージ認証と比較して、通信量は変わらない。
【０１２３】
また、本発明の第１の実施の形態では、攻撃者が秘密鍵を入手したとしても、攻撃者はサーバ１００から送信されたデータ、及び、認証情報からチェイン値を推定しない限り、データ、及び、認証情報の偽造ができない。また、攻撃者が、偽造データを受信させることが可能なノード２００は、サーバ１００からの正しいデータを受信前のノード２００に限定される。無線ＬＡＮ（Local Area Network）のようなワンホップのブロードキャストでは、攻撃者がサーバ１００からデータを取得してから偽造データを送信するまでに、ほとんどのノード２００で、サーバ１００からの正しいデータの受信を完了していると期待できる。したがって、本発明の第１の実施の形態により、攻撃者による攻撃機会を大きく制限できるため、安全性が向上する。
【０１２４】
（第２の実施の形態）
次に、本発明の第２の実施の形態について説明する。
【０１２５】
本発明の第２の実施の形態では、さらに、複数の秘密鍵を用いる。
【０１２６】
ここでは、各々がｗ個（ｗは１以上の整数）の秘密鍵を含むｖ個（ｖは１以上の整数）の秘密鍵集合Ｌ［ｉ］（ｉ＝１、２、…、ｖ）を用いる。また、異なる秘密鍵集合Ｌ［ｉ］間に、共通元（共通な秘密鍵）は無いと仮定する。この場合、全秘密鍵集合をＬ＝Ｌ［１］∪Ｌ［２］∪…∪Ｌ［ｖ］と定義すると、全秘密鍵集合Ｌの秘密鍵の数はｖｗである。
【０１２７】
本発明の第２の実施の形態では、サーバ１００の共通鍵記憶部１４０は、全秘密鍵集合Ｌを記憶する。各ノード２００の共通鍵記憶部２４０は、各秘密鍵集合Ｌ［ｉ］から一つずつ割り当てられたｖ個の秘密鍵を記憶する。
【０１２８】
サーバ１００のタグ生成部１３０は、送信データＤ［ｎ］に対して、各秘密鍵集合Ｌ［ｉ］に含まれる全ての秘密鍵を用いて、各々がｗ個のタグ（ｗ個の秘密鍵に対応）を含むｖ個のタグ集合Ｔ[n]［ｉ］（ｉ＝１、２、…、ｖ）を生成する。そして、タグ生成部１３０は、各タグを、本来のタグ長ｑに対して、ｑ／ｖの長さで打ち切る。この場合、全タグ集合のタグのトータルの長さはｑｗである。
【０１２９】
合成部１６０は、チェイン生成部１５０から出力された一方向性チェイン値ｈ［ｎ］（長さｑ）を、長さｑ／ｖの、ｖ個のｈ［ｎ］［ｉ］（ｉ＝１、２、…、ｖ）に分割する。合成部１６０は、各ｉについて、タグ集合Ｔ[n]［ｉ］に含まれるｗ個のタグとｈ［ｎ］［ｉ］とを合成することにより、各々がｗ個の認証情報（ｗ個の秘密鍵に対応）を含むｖ個の認証情報集合Ａ［ｎ］［ｉ］（ｉ＝１、２、…、ｖ）を生成する。この場合、認証情報のトータルの長さもｑｗである。
【０１３０】
サーバ１００は、カウンタ値ｎ、データＤ［ｎ］、ｖ個の認証情報集合Ａ［ｎ］［ｉ］を送信する。
【０１３１】
ノード２００は、カウンタ値ｎ’、データＤ’［ｎ’］、ｖ個の認証情報集合Ａ’［ｎ’］［ｉ］を受信する。
【０１３２】
各ノード２００のタグ生成部２３０は、当該ノード２００に割り当てられたｖ個の秘密鍵を用いて、受信データＤ’［ｎ’］に対して、ｖ個のタグを生成する。
【０１３３】
分離部２５０は、ｖ個の認証情報集合Ａ’［ｎ’］［ｉ］の各々に含まれる、当該ノード２００に割り当てられた秘密鍵に対応する認証情報から、生成したタグを用いて、ｖ個のｈ’［ｎ’］［ｉ］を抽出する。そして、分離部２５０は、ｖ個のｈ’［ｎ’］［ｉ］からチェイン値ｈ’［ｎ’］を生成する。
【０１３４】
検証部２６０は、生成したチェイン値ｈ’［ｎ’］を一方向性関数を用いて検証することにより、受信データＤ’［ｎ’］の認証を行う。
【０１３５】
本発明の第２の実施の形態では、ｗのｖ乗台までのノード２００に対して、異なるノード２００間で、秘密鍵の全てが一致することはないように、秘密鍵を割り当てることができる。この場合、あるノード２００が攻撃され、当該ノード２００から秘密鍵が漏洩しても、他のノード２００が受理する認証情報を生成することは困難である。
【０１３６】
また、複数のノード２００から秘密鍵が漏洩した場合、攻撃者は、一部のノード２００が持つ秘密鍵の全て得ることができる。しかしながら、攻撃者が偽造データを受信させることが可能なノード２００は、当該一部のノード２００の中で、サーバ１００からの正しいデータを受信前のノード２００に限定され、安全性はさらに向上する。
【０１３７】
次に、本発明の第２の実施の形態の効果を説明する。
【０１３８】
本発明の第２の実施の形態の効果は、本発明の第１の実施の形態に比べて、さらに安全性を向上できることである。その理由は、サーバ１００が複数の秘密鍵を用いて、複数の認証情報を生成し、ノード２００が複数の秘密鍵の内の当該ノード２００に割り当てられた秘密鍵を用いて、当該割り当てられた秘密鍵に対応する認証情報からチェイン値を抽出するためである。
【０１３９】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１４０】
この出願は、２０１４年１０月２９日に出願された日本出願特願２０１４−２１９８３９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１４１】
本発明は、無線ＬＡＮ、 センサネットワーク、インターネット通信などにおける、ブロードキャスト認証に適用することができる。
【符号の説明】
【０１４２】
１    ブロードキャスト認証システム
１００    サーバ
１０１    ＣＰＵ
１０２    記憶手段
１０３    通信手段
１０４    入力手段
１０５    出力手段
１１０    データ送信部
１２０    認証情報生成部
１３０    タグ生成部
１４０    共通鍵記憶部
１５０    チェイン生成部
１５１    チェイン算出部
１５２    チェイン記憶部
１５３    チェイン出力部
１６０    合成部
２００    ノード
２０１    ＣＰＵ
２０２    記憶手段
２０３    通信手段
２０４    入力手段
２０５    出力手段
２１０    データ受信部
２２０    認証情報検証部
２３０    タグ生成部
２４０    共通鍵記憶部
２５０    分離部
２６０    検証部
２６１    前回値記憶部
２６２    比較部
【図１】
2016067565.tif 000011
【図２】
2016067565.tif 000012
【図３】
2016067565.tif 000013
【図４】
2016067565.tif 000014
【図５】
2016067565.tif 000015
【図６】
2016067565.tif 000016
【図７】
2016067565.tif 000017
【図８】
2016067565.tif 000018
【図９】
2016067565.tif 000019
【図１０】
2016067565.tif 000020
【手続補正書】
【提出日】平成29年4月20日(2017.4.20)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
送信データに係るタグを、共通鍵を用いて生成する第１のタグ生成手段と、
一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成するチェイン生成手段と、
前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する合成手段と、
前記送信データ、及び、当該送信データの認証情報を、第２の情報処理装置に送信する送信手段と、
を含む、第１の情報処理装置と、
前記第１の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信する受信手段と、
前記受信データに係るタグを、前記共通鍵を用いて生成する第２のタグ生成手段と、
前記受信データの認証情報から当該受信データに係るタグを用いて前記チェインの値を抽出する分離手段と、
前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う検証手段と、
を含む、前記第２の情報処理装置と、
を備えた情報処理システム。
【請求項２】
複数の前記第２の情報処理装置を備え、
前記送信手段は、前記複数の前記第２の情報処理装置に、前記送信データ、及び、当該送信データの認証情報を送信する、
請求項１に記載の情報処理システム。
【請求項３】
前記チェイン生成手段は、前記複数の第２の情報処理装置の内の１以上の第２の情報処理装置を含むグループ毎に前記チェインを生成し、
前記合成手段は、前記送信データの受信対象のグループに対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する、
請求項２に記載の情報処理システム。
【請求項４】
前記第１のタグ生成手段は、複数の共通鍵を用いて、前記送信データに係る複数のタグを、それぞれ生成し、
前記合成手段は、前記送信データの送信順序に対応する前記チェインの値と前記複数のタグとを合成して、当該送信データの複数の認証情報を、それぞれ生成し、
前記送信手段は、前記送信データ、及び、当該送信データの複数の認証情報を送信し、
前記複数の前記第２の情報処理装置には、前記複数の共通鍵の内の、互いに異なる共通鍵が割り当てられ、
前記受信手段は、前記受信データ、及び、当該受信データの複数の認証情報を受信し、
前記第２のタグ生成手段は、前記第２の情報処理装置に割り当てられた共通鍵を用いて、前記受信データに係るタグを生成し、
前記分離手段は、前記受信データの複数の認証情報の内の、前記第２の情報処理装置に割り当てられた共通鍵に対応する認証情報から当該受信データに係るタグを用いて前記チェインの値を抽出する、
請求項２に記載の情報処理システム。
【請求項５】
送信データに係るタグを、共通鍵を用いて生成するタグ生成手段と、
一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成するチェイン生成手段と、
前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成する合成手段と、
前記送信データ、及び、当該送信データの認証情報を、前記共通鍵を用いて生成した受信にデータに係るタグと当該受信データの認証情報とを用いて抽出した前記チェインの値に前記一方向性関数を適用して、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかどうかを検証する、他の情報処理装置に送信する送信手段と、
を備えた情報処理装置。
【請求項６】
共通鍵を用いて生成した、送信データに係るタグと、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられたチェインにおける、送信データの送信順序に対応する前記チェインの値と、を合成して、当該送信データの認証情報を生成する、他の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信する受信手段と、
前記受信データに係るタグを、前記共通鍵を用いて生成するタグ生成手段と、
前記受信データの認証情報から当該受信データに係るタグを用いて、前記チェインの値を抽出する分離手段と、
前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う検証手段と、
を備えた情報処理装置。
【請求項７】
第１の情報処理装置において、
送信データに係るタグを、共通鍵を用いて生成し、
一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成し、
前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成し、
前記送信データ、及び、当該送信データの認証情報を、第２の情報処理装置に送信し、
前記第２の情報処理装置において、
前記第１の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信し、
前記受信データに係るタグを、前記共通鍵を用いて生成し、
前記受信データの認証情報から当該受信データに係るタグを用いて前記チェインの値を抽出し、
前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う、
情報処理方法。
【請求項８】
コンピュータに、
送信データに係るタグを、共通鍵を用いて生成し、
一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられた、チェインを生成し、
前記送信データの送信順序に対応する前記チェインの値と当該送信データに係るタグとを合成して、当該送信データの認証情報を生成し、
前記送信データ、及び、当該送信データの認証情報を、前記共通鍵を用いて生成した受信にデータに係るタグと当該受信データの認証情報とを用いて抽出した前記チェインの値に前記一方向性関数を適用して、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかどうかを検証する、他の情報処理装置に送信する、
処理を実行させるプログラム。
【請求項９】
コンピュータに、
共通鍵を用いて生成した、送信データに係るタグと、一の値に一方向性関数を繰り返し適用することにより順番に生成される値の系列であって、各値の生成順序がデータの送信順序と逆に対応づけられたチェインにおける、送信データの送信順序に対応する前記チェインの値と、を合成して、当該送信データの認証情報を生成する、他の情報処理装置から、受信データ、及び、当該受信データの認証情報を受信し、
前記受信データに係るタグを、前記共通鍵を用いて生成し、
前記受信データの認証情報から当該受信データに係るタグを用いて、前記チェインの値を抽出し、
前記受信データの認証情報から抽出された前記チェインの値に前記一方向性関数を適用することにより、過去に受信したデータの送信順序に対応する前記チェインの値が生成されるかを検証することにより、当該受信データの認証を行う、
処理を実行させるプログラム。
【国際調査報告】
2016067565.tif 000021
2016067565.tif 000022