(57)【要約】【課題】木構造に従ってグループ分けされた複数の端末装置に対し、同じ木構造で管理される暗号鍵を配布する方式において、いずれかの端末装置の暗号鍵が何らかの理由で失効した場合でも、その端末装置と同じグループに属していた各端末装置と安全に効率よく通信する。【解決手段】２分木の木構造の各末端ノードにＡ１〜Ａ８の端末装置３００を対応させる。例えばＡ６が失効した場合、特定グループ情報生成部４０２はＡ６に対応する末端ノードと当該末端ノードの祖先ノードとを上記木構造から除外することにより形成される部分木ごとに、同じ部分木に含まれる末端ノードに対応する端末装置３００を有効端末として特定する。グループ別情報送信部４０３は、当該有効端末からなる端末装置３００のグループ（Ａ１〜Ａ４／Ａ５／Ａ７，Ａ８の３グループ）ごとに共通の暗号鍵を用いて生成した暗号文を端末装置３００へ一括送信する。【選択図】図１
2010193226.tif 000002
【特許請求の範囲】
【請求項１】
割り当てられている暗号鍵を用いて暗号通信を行う端末装置と通信する通信装置であって、
親子関係をもつ複数ノードからなる木構造の末端ノードに、端末装置に割り当てられている個別の暗号鍵を対応付け、末端ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納するとともに、記憶装置に格納された鍵情報で個別の暗号鍵が対応付けられた末端ノードに、当該暗号鍵が割り当てられている端末装置を対応付け、末端ノードと端末装置との対応関係を示す端末情報を記憶装置に格納する情報格納部と、
割り当てられている暗号鍵が失効した端末装置がある場合、前記情報格納部により格納された端末情報に基づいて、当該端末装置に対応する末端ノードと当該末端ノードの祖先ノードとを前記木構造から除外することにより形成される部分木ごとに、同じ部分木に含まれる末端ノードに対応する端末装置を有効端末として特定し、当該有効端末からなる端末装置のグループを示す特定グループ情報を処理装置により生成し、生成した特定グループ情報を記憶装置に格納する特定グループ情報生成部と、
前記特定グループ情報生成部により格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成し、生成したグループ別情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信したグループ別情報を利用させるグループ別情報送信部とを備えることを特徴とする通信装置。
【請求項２】
前記情報格納部は、さらに、前記木構造の末端ノード以外のノードに、記憶装置に格納された端末情報で当該ノードの子孫ノードにあたる末端ノードに対応付けられた端末装置からなる端末装置のグループを対応付け、ノードと端末装置のグループとの対応関係を示す端末グループ情報を記憶装置に格納するとともに、鍵情報として、さらに、前記木構造の末端ノード以外のノードに、記憶装置に格納された端末グループ情報で当該ノードに対応付けられたグループに属する端末装置に割り当てられている共通の暗号鍵を対応付け、ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納し、
前記グループ別情報送信部は、前記情報格納部により格納された鍵情報と端末グループ情報とに基づいて、前記特定グループ情報生成部により格納された特定グループ情報で示されたグループごとに、当該グループに対応するノードを有効ノードとして特定し、当該有効ノードに対応する暗号鍵を用いて暗号文をグループ別情報として処理装置により生成し、生成した暗号文を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信した暗号文を復号させることを特徴とする請求項１に記載の通信装置。
【請求項３】
前記グループ別情報送信部は、前記特定グループ情報生成部により格納された特定グループ情報で示されたグループごとに、暗号鍵を更新するための鍵更新情報をグループ別情報として処理装置により生成し、生成した鍵更新情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信した鍵更新情報により当該端末装置に割り当てられている暗号鍵を更新させることを特徴とする請求項１に記載の通信装置。
【請求項４】
前記情報格納部は、鍵情報として、さらに、前記木構造のルートノード以外かつ末端ノード以外のノードに、当該ノードの子ノードに対応する暗号鍵を生成するために用いられる暗号鍵を対応付け、ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納するとともに、さらに、前記木構造の末端ノード以外のノードに、記憶装置に格納された端末情報で当該ノードの子孫ノードにあたる末端ノードに対応付けられた端末装置からなる端末装置のグループを対応付け、ノードと端末装置のグループとの対応関係を示す端末グループ情報を記憶装置に格納し、
前記グループ別情報送信部は、前記情報格納部により格納された鍵情報と端末グループ情報とに基づいて、前記特定グループ情報生成部により格納された特定グループ情報で示されたグループごとに、当該グループに対応するノードを有効ノードとして特定し、当該有効ノードの親ノードに対応する暗号鍵を更新し、当該暗号鍵の更新前後の差分情報を鍵更新情報として処理装置により生成し、生成した差分情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信した差分情報により当該端末装置に割り当てられている暗号鍵を更新させることを特徴とする請求項３に記載の通信装置。
【請求項５】
端末装置に割り当てられている暗号鍵は、階層型ＩＤ（Ｉｄｅｎｔｉｔｙ）ベース暗号方式にて前記木構造のノードに割り当てられる識別子と秘密情報とを基に生成される秘密鍵であり、
前記グループ別情報送信部は、前記情報格納部により格納された鍵情報と端末グループ情報とに基づいて、前記特定グループ情報生成部により格納された特定グループ情報で示されたグループごとに、当該グループに対応するノードを有効ノードとして特定し、ルートノードから当該有効ノードの親ノードまでの各ノードに割り当てられた識別子と秘密情報とのいずれかを更新することにより、各ノードに対応する秘密鍵を更新し、当該有効ノードの親ノードに対応する秘密鍵の更新前後の差分情報を鍵更新情報として処理装置により生成することを特徴とする請求項４に記載の通信装置。
【請求項６】
割り当てられている暗号鍵を用いて暗号通信を行う端末装置と通信するために、個別の暗号鍵を保持する通信装置であって、
親子関係をもつ複数ノードからなる木構造のノードに、端末装置に割り当てられている個別の暗号鍵及び前記通信装置が保持する個別の暗号鍵を対応付け、ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納するとともに、記憶装置に格納された鍵情報で個別の暗号鍵が対応付けられたノードに、当該暗号鍵が割り当てられている端末装置及び当該暗号鍵を保持する前記通信装置を対応付け、ノードと端末装置及び前記通信装置との対応関係を示す端末情報を記憶装置に格納する情報格納部と、
割り当てられている暗号鍵が失効した端末装置がある場合、当該端末装置を失効端末とし、前記情報格納部により格納された端末情報に基づいて、前記失効端末が前記通信装置に対応するノードの子ノードに対応する子端末と子ノード以外の子孫ノードに対応する子孫端末と子孫ノードに対応しない端末装置とのいずれであるかを処理装置により判定し、前記失効端末が子端末であると判定した場合、前記失効端末以外の子端末それぞれを１つの端末装置のグループとして示す特定グループ情報を処理装置により生成し、前記失効端末が子孫端末であると判定した場合、子端末のうち、前記失効端末に対応するノードの祖先ノードに対応する子端末を１つの端末装置のグループとして示すとともに他の子端末と当該他の子端末に対応するノードの子孫ノードに対応する端末装置とをまとめて１つの端末装置のグループとして示す特定グループ情報を処理装置により生成し、生成した特定グループ情報を記憶装置に格納する特定グループ情報生成部と、
前記特定グループ情報生成部により格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成し、生成したグループ別情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信したグループ別情報を利用させるグループ別情報送信部とを備えることを特徴とする通信装置。
【請求項７】
前記グループ別情報送信部は、前記特定グループ情報生成部により格納された特定グループ情報で示されたグループごとに、暗号鍵を更新するための鍵更新情報をグループ別情報として処理装置により生成し、生成した鍵更新情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信した鍵更新情報により当該端末装置に割り当てられている暗号鍵を更新させることを特徴とする請求項６に記載の通信装置。
【請求項８】
前記通信装置は、他の端末装置と通信する端末装置であることを特徴とする請求項１から７までのいずれかに記載の通信装置。
【請求項９】
割り当てられている暗号鍵を用いて暗号通信を行う端末装置と通信する通信方法であって、
記憶装置が、親子関係をもつ複数ノードからなる木構造の末端ノードに、端末装置に割り当てられている個別の暗号鍵を対応付け、末端ノードと暗号鍵との対応関係を示す鍵情報を格納し、
記憶装置が、前記格納された鍵情報で個別の暗号鍵が対応付けられた末端ノードに、当該暗号鍵が割り当てられている端末装置を対応付け、末端ノードと端末装置との対応関係を示す端末情報を格納し、
処理装置が、割り当てられている暗号鍵が失効した端末装置がある場合、前記格納された端末情報に基づいて、当該端末装置に対応する末端ノードと当該末端ノードの祖先ノードとを前記木構造から除外することにより形成される部分木ごとに、同じ部分木に含まれる末端ノードに対応する端末装置を有効端末として特定し、当該有効端末からなる端末装置のグループを示す特定グループ情報を生成し、
記憶装置が、前記生成された特定グループ情報を格納し、
処理装置が、前記格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として生成し、生成したグループ別情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信したグループ別情報を利用させることを特徴とする通信方法。
【請求項１０】
割り当てられている暗号鍵を用いて暗号通信を行う端末装置と、個別の暗号鍵を保持する通信装置により通信する通信方法であって、
記憶装置が、親子関係をもつ複数ノードからなる木構造のノードに、端末装置に割り当てられている個別の暗号鍵及び前記通信装置が保持する個別の暗号鍵を対応付け、ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納し、
記憶装置が、前記格納された鍵情報で個別の暗号鍵が対応付けられたノードに、当該暗号鍵が割り当てられている端末装置及び当該暗号鍵を保持する前記通信装置を対応付け、ノードと端末装置及び前記通信装置との対応関係を示す端末情報を記憶装置に格納し、
処理装置が、割り当てられている暗号鍵が失効した端末装置がある場合、当該端末装置を失効端末とし、前記格納された端末情報に基づいて、前記失効端末が前記通信装置に対応するノードの子ノードに対応する子端末と子ノード以外の子孫ノードに対応する子孫端末と子孫ノードに対応しない端末装置とのいずれであるかを処理装置により判定し、前記失効端末が子端末であると判定した場合、前記失効端末以外の子端末それぞれを１つの端末装置のグループとして示す特定グループ情報を処理装置により生成し、前記失効端末が子孫端末であると判定した場合、子端末のうち、前記失効端末に対応するノードの祖先ノードに対応する子端末を１つの端末装置のグループとして示すとともに他の子端末と当該他の子端末に対応するノードの子孫ノードに対応する端末装置とをまとめて１つの端末装置のグループとして示す特定グループ情報を処理装置により生成し、
記憶装置が、前記生成された特定グループ情報を記憶装置に格納し、
処理装置が、前記格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成し、生成したグループ別情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信したグループ別情報を利用させることを特徴とする通信方法。
【請求項１１】
割り当てられている暗号鍵を用いて暗号通信を行う端末装置と通信する通信プログラムであって、
親子関係をもつ複数ノードからなる木構造の末端ノードに、端末装置に割り当てられている個別の暗号鍵を対応付け、末端ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納するとともに、記憶装置に格納された鍵情報で個別の暗号鍵が対応付けられた末端ノードに、当該暗号鍵が割り当てられている端末装置を対応付け、末端ノードと端末装置との対応関係を示す端末情報を記憶装置に格納する情報格納処理と、
割り当てられている暗号鍵が失効した端末装置がある場合、前記情報格納処理により格納された端末情報に基づいて、当該端末装置に対応する末端ノードと当該末端ノードの祖先ノードとを前記木構造から除外することにより形成される部分木ごとに、同じ部分木に含まれる末端ノードに対応する端末装置を有効端末として特定し、当該有効端末からなる端末装置のグループを示す特定グループ情報を処理装置により生成し、生成した特定グループ情報を記憶装置に格納する特定グループ情報生成処理と、
前記特定グループ情報生成処理により格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成し、生成したグループ別情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信したグループ別情報を利用させるグループ別情報送信処理とをコンピュータに実行させることを特徴とする通信プログラム。
【請求項１２】
割り当てられている暗号鍵を用いて暗号通信を行う端末装置と通信するために、個別の暗号鍵を保持する通信プログラムであって、
親子関係をもつ複数ノードからなる木構造のノードに、端末装置に割り当てられている個別の暗号鍵及び前記通信装置が保持する個別の暗号鍵を対応付け、ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納するとともに、記憶装置に格納された鍵情報で個別の暗号鍵が対応付けられたノードに、当該暗号鍵が割り当てられている端末装置及び当該暗号鍵を保持する前記通信装置を対応付け、ノードと端末装置及び前記通信装置との対応関係を示す端末情報を記憶装置に格納する情報格納処理と、
割り当てられている暗号鍵が失効した端末装置がある場合、当該端末装置を失効端末とし、前記情報格納処理により格納された端末情報に基づいて、前記失効端末が前記通信装置に対応するノードの子ノードに対応する子端末と子ノード以外の子孫ノードに対応する子孫端末と子孫ノードに対応しない端末装置とのいずれであるかを処理装置により判定し、前記失効端末が子端末であると判定した場合、前記失効端末以外の子端末それぞれを１つの端末装置のグループとして示す特定グループ情報を処理装置により生成し、前記失効端末が子孫端末であると判定した場合、子端末のうち、前記失効端末に対応するノードの祖先ノードに対応する子端末を１つの端末装置のグループとして示すとともに他の子端末と当該他の子端末に対応するノードの子孫ノードに対応する端末装置とをまとめて１つの端末装置のグループとして示す特定グループ情報を処理装置により生成し、生成した特定グループ情報を記憶装置に格納する特定グループ情報生成処理と、
前記特定グループ情報生成処理により格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成し、生成したグループ別情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信したグループ別情報を利用させるグループ別情報送信処理とをコンピュータに実行させることを特徴とする通信プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信装置及び通信方法及び通信プログラムに関するものである。本発明は、特に、通信装置を利用した鍵更新方法及び鍵配布方法、通信装置となる鍵管理装置及び端末装置、通信装置を備える暗号システムに関するものである。
【背景技術】
【０００２】
多数の端末装置が接続されているネットワーク内において、特定の目的や条件の下で決定される複数の端末装置からなる集合をグループと呼ぶ。特定のグループに属する端末装置のみが復号可能な暗号文を作成するための鍵をグループ鍵と呼ぶ。グループ鍵の単純な例は、全ての端末装置に同じ鍵をもたせることであるが、この場合にある１つの端末装置から何らかの原因でグループ鍵が漏洩してしまったら、ネットワーク全体の安全性が損なわれてしまう。逆に、全ての部分集合に対して異なる鍵を作成した場合では、ネットワーク全体で鍵の数が端末装置台数の指数乗となり、鍵を管理する面から見て効率が悪い。
【０００３】
この課題に対して、グループ鍵を安全で効率よく管理する方法の１つに木構造鍵管理方式がある。木構造に基づき鍵更新を行う鍵管理方式として、ＬＫＨ（Ｌｏｇｉｃａｌ・Ｋｅｙ・Ｈｉｅｒａｒｃｈｙ）がある（例えば、非特許文献１参照）。ＬＫＨでは、以下のようにして共有鍵の木構造を構成する。まず、ネットワーク全体の共有鍵を管理する鍵管理装置を仮定し、鍵管理装置が予め多数の共有鍵を用意しておく。次に、その中から定数個（例えば３つ）ずつの鍵を選択し、それらを一方向性ハッシュ関数へ入力し、１つずつの鍵を得る。次に、得られた鍵の中から３つずつの鍵を選択し、一方向性ハッシュ関数へ入力し、１つずつの鍵を得る。この動作を、最終的に１つの鍵が出力されるまで繰り返す。ここまで繰り返すと、最終的に出力された鍵を根頂点（親のない頂点）、予め用意した多数の鍵を葉頂点（子のない頂点）とする木構造が形成される。各端末装置には、葉頂点を１つずつ割り当て、葉頂点から根頂点までの各共有鍵を埋め込むことで、同じ共有鍵をもつ端末装置同士が暗号化通信を行うことができる。
【０００４】
しかし、木構造の各頂点に共有鍵が割り当てられている方式では、各端末装置に１種類あるいは複数種類の共有鍵を埋め込まれているが、まったく同じ共有鍵をもたない限り暗号化通信ができないという課題がある。例えば、特定のグループに属する端末装置に対して暗号文を一斉送信する場合、送信者も同グループのグループ鍵をもっていなければならない。また、共有鍵を用いたグループ鍵では、同じ共有鍵をもつ端末装置ならば誰でも暗号文を復号できるので、送信者がグループの中のある特定の１つの端末装置に対して暗号文を送信することができないという課題がある。
【０００５】
前者の課題を回避するためには、別途公開鍵暗号系を利用する方法があるが、この場合は、別途暗号装置や公開鍵／秘密鍵を用意しなければならない。また、後者の課題を回避するためには、グループ鍵とは別に、任意の２端末装置間のみでの暗号化のための共有鍵を保持する方法があるが、この場合は、事前に送信者と受信者に対して共有鍵を埋め込んでおかなければならない。そのため、送信者と受信者の関係がネットワーク施工時まで想定できない環境では、全ての２者の組み合わせに対して共有鍵を用意しなければならない。端末装置数をｎとすると、共有鍵数はｎ（ｎ−１）／２個となってしまい、例えば端末装置数が１００台のときは、共有鍵数は４９５０個の鍵が必要となり、端末装置数に比べて非常に多くの共有鍵を管理しなければならないという課題がある。
【０００６】
一方、公開鍵暗号系に基づく木構造鍵管理方式も存在するが、これらの多くはグループ鍵の利用を目的としているわけではなく、専ら移動通信における基地局からの公開鍵／秘密鍵ペアの配布にかかるコスト削減のために用いられている。その１つとして、階層型ＩＤベース暗号（Ｈｉｅｒａｒｃｈｉｃａｌ・Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ・Ｃｒｙｐｔｏｇｒａｐｈｙ，ＨＩＢＥ）がある（例えば、非特許文献２参照）。ＩＤベース暗号（Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ・Ｃｒｙｐｔｏｇｒａｐｈｙ，ＩＢＥ）は、任意の文字列（例えばメールアドレス等、以降ＩＤと呼ぶ）等を公開鍵とする暗号技術である。階層型ＩＤベース暗号において、暗号化通信に用いる鍵漏洩に対する対策として、端末装置が保持する鍵の更新がある（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００５−１９８１８９号公報
【非特許文献】
【０００８】
【非特許文献１】Ｃ．  Ｋ．  Ｗｏｎｇ，  Ｍ．  Ｇｏｕｄａ，  ａｎｄ  Ｓ．  Ｓ．  Ｌａｍ，  “Ｓｅｃｕｒｅ  Ｇｒｏｕｐ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｕｓｉｎｇ  Ｋｅｙ  Ｇｒａｐｈｓ，”  Ｐｒｏｃ．  ｏｆ  ＳＩＧＣＯＭＭ’９８，  ｐｐ．６８−７９，  ＡＣＭ，  １９９８
【非特許文献２】Ｃ．  Ｇｅｎｔｒｙ  ａｎｄ  Ａ．  Ｓｉｌｖｅｒｂｅｒｇ，  “Ｈｉｅｒａｒｃｈｉｃａｌ  ＩＤ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ，”  Ｐｒｏｃ．  ｏｆ  ＡＳＩＡＣＲＹＰＴ’０２，  ＬＮＣＳ２５０１，  ｐｐ．５４８−５６６，  Ｓｐｒｉｎｇｅｒ，  ２００２
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献２では、公開鍵／秘密鍵ペアをもつ者は個人であり、グループに対して暗号文を送信する方法は記載されていない。また、特定のグループに対して同じ鍵を格納させた場合、鍵の更新方法がないという課題があるが、この課題に対して、対策が示されていない。特許文献１では、鍵更新に各端末装置が保持する鍵更新鍵を用いており、ある端末装置が盗難され、端末装置内に格納されている全ての情報が漏洩した場合には、鍵更新を行っても、失効した端末も鍵を更新できてしまうという課題がある。
【００１０】
従来の技術（特許文献１及び非特許文献２）は、公開鍵暗号系の木構造において、鍵を管理する装置が各頂点に対応するグループに対して暗号化通信を行うためのものである。公開鍵暗号系の特徴から、公開情報は誰でも取得することができるので、各端末装置は他の全端末装置に対して暗号文を送信することが可能である。しかし、特定の端末装置が失効した場合、ある別の端末装置が、失効した端末装置を含むグループに対して暗号文を送信してしまうと、失効したはずの端末装置も暗号文を復号できてしまう。失効した端末装置以外の同じグループに属する各端末装置に暗号文を個別に送信する方法もあるが、これは効率的ではない。また、失効した端末装置を除く全端末装置を１箇所に集め、安全な方法で鍵を埋め込み直す方法もあるが、これは現実的ではない。そのため、失効した端末装置以外の同じグループに属する各端末装置に対して暗号文を送信する効率のよい方法が必要となるが、この課題に対して、従来の技術は対策手法を示していなかった。
【００１１】
本発明は、例えば、木構造に従ってグループ分けされた複数の端末装置に対し、同じ木構造で管理される暗号鍵を配布する方式において、いずれかの端末装置の暗号鍵が何らかの理由で失効した場合でも、その端末装置と同じグループに属していた各端末装置と安全に効率よく通信することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の一の態様に係る通信装置は、
割り当てられている暗号鍵を用いて暗号通信を行う端末装置と通信する通信装置であって、
親子関係をもつ複数ノードからなる木構造の末端ノードに、端末装置に割り当てられている個別の暗号鍵を対応付け、末端ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納するとともに、記憶装置に格納された鍵情報で個別の暗号鍵が対応付けられた末端ノードに、当該暗号鍵が割り当てられている端末装置を対応付け、末端ノードと端末装置との対応関係を示す端末情報を記憶装置に格納する情報格納部と、
割り当てられている暗号鍵が失効した端末装置がある場合、前記情報格納部により格納された端末情報に基づいて、当該端末装置に対応する末端ノードと当該末端ノードの祖先ノードとを前記木構造から除外することにより形成される部分木ごとに、同じ部分木に含まれる末端ノードに対応する端末装置を有効端末として特定し、当該有効端末からなる端末装置のグループを示す特定グループ情報を処理装置により生成し、生成した特定グループ情報を記憶装置に格納する特定グループ情報生成部と、
前記特定グループ情報生成部により格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成し、生成したグループ別情報を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信したグループ別情報を利用させるグループ別情報送信部とを備えることを特徴とする。
【発明の効果】
【００１３】
本発明の一の態様によれば、例えば、木構造に従ってグループ分けされた複数の端末装置に対し、同じ木構造で管理される暗号鍵を配布する方式において、いずれかの端末装置の暗号鍵が何らかの理由で失効した場合でも、特定グループ情報生成部が、当該端末装置に対応する末端ノードと当該末端ノードの祖先ノードとを上記木構造から除外することにより形成される部分木ごとに、同じ部分木に含まれる末端ノードに対応する端末装置を有効端末として特定し、当該有効端末からなる端末装置のグループを示す特定グループ情報を生成し、グループ別情報送信部が、上記特定グループ情報生成部により生成された特定グループ情報で示されたグループごとに、グループ別情報を同じグループに属する端末装置へ送信するため、暗号鍵が失効した端末装置と同じグループに属していた各端末装置と安全に効率よく通信することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】実施の形態１に係る暗号システムの構成を示すブロック図である。
【図２】実施の形態１に係る木構造の一例を示す図である。
【図３】実施の形態１に係る鍵管理装置、端末装置のハードウェア構成の一例を示す図である。
【図４】実施の形態１に係る端末装置の動作を示すフローチャートである。
【図５】実施の形態１に係る端末装置の動作を示すフローチャートである。
【図６】実施の形態１に係る端末装置の動作を示すフローチャートである。
【図７】実施の形態１に係る木構造の一例を示す図である。
【図８】実施の形態２に係る暗号システムの構成を示すブロック図である。
【図９】実施の形態２に係る鍵管理装置の動作を示すフローチャートである。
【図１０】実施の形態２に係る木構造の一例を示す図である。
【図１１】実施の形態３に係る木構造の一例を示す図である。
【図１２】実施の形態４に係る木構造の一例を示す図である。
【図１３】実施の形態４に係る木構造の一例を示す図である。
【図１４】実施の形態５に係る暗号システムの構成を示すブロック図である。
【図１５】実施の形態５に係る木構造の一例を示す図である。
【図１６】実施の形態５に係る鍵管理装置の動作を示すフローチャートである。
【図１７】実施の形態５に係る木構造の一例を示す図である。
【図１８】実施の形態５に係る端末装置の動作を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、図を用いて説明する。
【００１６】
実施の形態１．
図１は、本実施の形態に係る暗号システム１００の構成を示すブロック図である。
【００１７】
図１において、暗号システム１００は、鍵管理装置２００、Ａ１〜Ａ８の８台の端末装置３００を備える。鍵管理装置２００及び各端末装置３００は、無線ネットワーク１０１（ネットワークの一例）で接続され、メッセージの送受信を行うものである。鍵管理装置２００は、端末装置３００の暗号鍵及び端末装置３００のグループの暗号鍵を生成し、生成した暗号鍵を端末装置３００に割り当てるとともに、割り当てた暗号鍵を管理し、必要に応じて更新する。端末装置３００は、鍵管理装置２００により割り当てられた自己の暗号鍵及び自己が属するグループの暗号鍵を用いて暗号通信を行う。
【００１８】
本実施の形態において、端末装置３００の暗号鍵、端末装置３００のグループの暗号鍵は、図２に示すような木構造によって管理される階層型ＩＤ（Ｉｄｅｎｔｉｔｙ）ベース暗号方式の暗号鍵（公開鍵、公開情報、秘密鍵の組み合わせ）である。端末装置３００、端末装置３００のグループも、同じ木構造によって管理される。木構造は、親子関係をもつ複数ノードからなり、ノードとして、１つのルートノードのほか、ルートノードの子孫ノード（子ノード、孫ノード、曾孫ノード等）を複数含むものである。ルートノードの子孫ノードのうち、それ自身が子孫ノードをもたないノードが末端ノードである。端末装置３００及びその端末装置３００に個別に割り当てられる暗号鍵は、末端ノードに１対１で対応付けて管理される。端末装置３００のグループ及びそのグループに属する端末装置３００に共通に割り当てられる暗号鍵は、末端ノード以外のノードに１対１で対応付けて管理される。
【００１９】
鍵管理装置２００は、端末情報格納部２０１、グループ情報格納部２０２、秘密情報格納部２０３、公開情報格納部２０４、秘密鍵格納部２０５、暗号化計算部２０６、復号計算部２０７を備える。また、図示していないが、鍵管理装置２００は、処理装置、記憶装置、入力装置、出力装置等のハードウェアを備える。ハードウェアは鍵管理装置２００の各部によって利用される。例えば、処理装置は、鍵管理装置２００の各部でデータや情報の演算、加工、読み取り、書き込み等を行うために利用される。記憶装置は、そのデータや情報を記憶するために利用される。また、入力装置は、そのデータや情報を入力するために、出力装置は、そのデータや情報を出力するために利用される。
【００２０】
端末情報格納部２０１は、全端末装置３００（Ａ１〜Ａ８）のＩＤと上記木構造の末端ノードとの対応関係を示す端末情報を記憶装置に保管する。本実施の形態では、一般的なＩＤベース暗号方式と同様に、端末装置３００のＩＤを端末装置３００の公開鍵として用いる（他に公開パラメータが必要なＩＤベース暗号方式を採用する場合にはその公開パラメータも含めて公開鍵とする）。そのため、端末情報格納部２０１は、端末装置３００のＩＤを、当該端末装置３００に対応する末端ノードの公開鍵として記憶装置に格納することになる。
【００２１】
グループ情報格納部２０２は、端末装置３００のグループのＩＤと上記木構造のノードとの対応関係を示すグループ情報を記憶装置に保管する。本実施の形態では、端末装置３００のＩＤの場合と同様に、端末装置３００のグループのＩＤを端末装置３００のグループの公開鍵として用いる。そのため、グループ情報格納部２０２は、端末装置３００のグループのＩＤを、当該グループに対応するノードの公開鍵として記憶装置に格納することになる。グループ情報格納部２０２は、さらに、失効等によりグループを脱退した端末装置３００の情報を失効情報として記憶装置に保管する。
【００２２】
端末装置３００のＩＤは、例えばａａａ＠ｂｂｂ．ｃｃｃ．ｄｄｄといった形式（メールアドレス等と同様）で表される。この例では、端末装置３００のグループのＩＤは、ｂｂｂ．ｃｃｃ．ｄｄｄやｃｃｃ．ｄｄｄやｄｄｄとなる。前述したように、これらのＩＤは、上記木構造の各ノードに割り当てられ、公開鍵として用いられる。図２では、ルートノードの公開鍵をＰ０、その子ノードの公開鍵をＰ１，Ｐ２、その子ノード（ルートノードの孫ノード）の公開鍵をＰ３〜Ｐ６、その子ノード（末端ノード）の公開鍵をＰ７〜Ｐ１４と表している。
【００２３】
秘密情報格納部２０３は、鍵を生成するための基となる秘密情報（マスタ鍵）を記憶装置に保管する。秘密情報は、鍵管理装置２００しか知ることのできない情報であり、上記木構造のノードごとに生成される任意のデータ（例えば、乱数）である。図２では、ルートノードの秘密情報をｓ０、その子ノードの秘密情報をｓ１，ｓ２、その子ノード（ルートノードの孫ノード）の秘密情報をｓ３〜ｓ６と表している。なお、子ノードがないノード、即ち、末端ノードには、秘密情報は不要である。
【００２４】
公開情報格納部２０４は、秘密情報格納部２０３により格納された秘密情報とグループ情報格納部２０２により格納されたルートノードの公開鍵を入力として公開情報を処理装置により生成し、記憶装置に保管する。公開情報は、誰もが知ることのできる情報であり、上記木構造のノードごとに生成されるものである。図２では、ルートノードの公開情報をＱ０、その子ノードの公開情報をＱ１，Ｑ２、その子ノード（ルートノードの孫ノード）の公開情報をＱ３〜Ｑ６と表している。なお、子ノードがないノード、即ち、末端ノードには、公開情報は不要である。以下、図２の例を用いて、公開情報格納部２０４の動作について具体的に説明する。
【００２５】
公開情報格納部２０４は、ルートノードの秘密情報（全体の秘密情報）ｓ０とルートノードの公開鍵（全体の公開鍵）Ｐ０とを乗算して、ルートノードの公開情報（全体の公開情報）Ｑ０＝ｓ０Ｐ０を求める。また、公開情報格納部２０４は、ルートノードの子ノードの秘密情報ｓ１（あるいはｓ２）とルートノードの公開鍵Ｐ０とを乗算して、ルートノードの子ノードの公開情報Ｑ１＝ｓ１Ｐ０（あるいはＱ２）を求める。同様に、公開情報格納部２０４は、ルートノードの孫ノードの秘密情報ｓ３（あるいはｓ４〜ｓ６）とルートノードの公開鍵Ｐ０とを乗算して、ルートノードの孫ノードの公開情報Ｑ３＝ｓ３Ｐ０（あるいはＱ４〜Ｑ６）を求める。公開情報格納部２０４は、求めた公開情報Ｑ０〜Ｑ６を記憶装置に格納する。
【００２６】
秘密鍵格納部２０５は、秘密情報格納部２０３により格納された秘密情報と端末情報格納部２０１及びグループ情報格納部２０２により格納された公開鍵を入力として新たな秘密鍵を処理装置により生成し、記憶装置に保管する。秘密鍵は、特定の端末装置３００あるいは鍵管理装置２００しか知ることのできない鍵であり、上記木構造のノードごとに生成されるものである。図２では、ルートノードの子ノードの秘密鍵をｔ１，ｔ２、その子ノード（ルートノードの孫ノード）の秘密鍵をｔ３〜ｔ６、その子ノード（末端ノード）の秘密鍵をｔ７〜ｔ１４と表している。なお、ここでは、ルートノードの秘密鍵は生成されない例を用いているが、ルートノードの秘密鍵が生成されてもよい。以下、図２の例を用いて、秘密鍵格納部２０５の動作について具体的に説明する。
【００２７】
まず、秘密鍵格納部２０５は、ルートノードの秘密情報（全体の秘密情報）ｓ０とルートノードの子ノードの公開鍵Ｐ１（あるいはＰ２）とを乗算して、ルートノードの子ノードの秘密鍵ｔ１＝ｓ０Ｐ１（あるいはｔ２）を求める。次に、秘密鍵格納部２０５は、ルートノードの子ノードの秘密情報ｓ１（あるいはｓ２）とその子ノード（ルートノードの孫ノード）の公開鍵Ｐ３（あるいはＰ４〜Ｐ６）とを乗算し、さらに、当該乗算結果とルートノードの子ノードの秘密鍵ｔ１（あるいはｔ２）とを加算して、その子ノード（ルートノードの孫ノード）の秘密鍵ｔ３＝ｔ１＋ｓ１Ｐ３＝ｓ０Ｐ１＋ｓ１Ｐ３（あるいはｔ４〜ｔ６）を求める。最後に、秘密鍵格納部２０５は、末端ノードの親ノード（ルートノードの孫ノード）の秘密情報ｓ３（あるいはｓ４〜ｓ６）とその末端ノードの公開鍵Ｐ７（あるいはＰ８〜Ｐ１４）とを乗算し、さらに、当該乗算結果と末端ノードの親ノードの秘密鍵ｔ３（あるいはｔ４〜ｔ６）とを加算して、その末端ノードの秘密鍵ｔ７＝ｔ３＋ｓ３Ｐ７＝ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ７（あるいはｔ８〜ｔ１４）を求める。秘密鍵格納部２０５は、求めた秘密鍵ｔ１〜ｔ１４を記憶装置に格納する。
【００２８】
暗号化計算部２０６は、暗号化したいメッセージ（鍵情報や文書等）と端末情報格納部２０１及びグループ情報格納部２０２により格納された公開鍵と公開情報格納部２０４により格納されたルートノードの公開情報とを入力として暗号文を処理装置により作成する。具体的には、暗号化計算部２０６は、ある端末装置３００の秘密鍵で復号可能な暗号文を作成する場合、端末情報格納部２０１により格納された、当該端末装置３００に対応する末端ノードの公開鍵と、グループ情報格納部２０２により格納された、当該末端ノードの祖先ノードにあたる全てのノード（即ち、当該末端ノードの親ノードからルートノードまでの全ての祖先ノード）の公開鍵と、公開情報格納部２０４により格納されたルートノードの公開情報とを用いて、メッセージを暗号化する。また、暗号化計算部２０６は、あるグループの秘密鍵で復号可能な暗号文を作成する場合、グループ情報格納部２０２により格納された、当該グループに対応するノードの公開鍵と、当該ノードの祖先ノードにあたる全てのノードの公開鍵と、公開情報格納部２０４により格納されたルートノードの公開情報とを用いて、メッセージを暗号化する。
【００２９】
図２の例において、Ａ５の端末装置３００（ＩＤタプルは｛Ｐ０，Ｐ２，Ｐ５，Ｐ１１｝）に対してメッセージＭを送るとき、暗号化計算部２０６は、次式（１）のようにして暗号文Ｃを作成する。
【数１】
2010193226.tif 000003
・まず、暗号化計算部２０６は、メッセージごとに異なる乱数ｒを選択し（適当に選び）、Ｐ０，Ｐ５，Ｐ１１のそれぞれと乱数ｒを掛けて、ｒＰ０，ｒＰ５，ｒＰ１１をそれぞれ別々に計算する。
・次に、暗号化計算部２０６は、ペアリング写像＾ｅを用いて＾ｅ（ｓ０Ｐ０，Ｐ２）ｒを計算し、それを乗算が定義された一方向性ハッシュ関数Ｈ２に入力して、Ｈ２（＾ｅ（ｓ０Ｐ０，Ｐ２）ｒ）を演算し、さらに平文Ｍとの排他的論理和（＋）をとって、Ｍ＋Ｈ２（＾ｅ（ｓ０Ｐ０，Ｐ２）ｒ）を計算する。
・最後に、暗号化計算部２０６は、ｒＰ０，ｒＰ５，ｒＰ１１，Ｍ＋Ｈ２（＾ｅ（ｓ０Ｐ０，Ｐ２）ｒ）の連接（単に並べるだけである）の演算結果をＣとする。
【００３０】
復号計算部２０７は、暗号文と秘密鍵格納部２０５により格納された秘密鍵と公開情報格納部２０４により格納された公開情報とを入力として元のメッセージを処理装置により出力する。具体的には、復号計算部２０７は、ある端末装置３００の公開鍵で暗号化された暗号文を復号する場合、秘密鍵格納部２０５により格納された、当該端末装置３００に対応する末端ノードの秘密鍵と、公開情報格納部２０４により格納された、当該末端ノードの祖先ノードにあたる全てのノード（即ち、当該末端ノードの親ノードからルートノードまでの全ての祖先ノード）の公開情報とを用いて、メッセージを復元する。また、復号計算部２０７は、あるグループの公開鍵で暗号化された暗号文を復号する場合、秘密鍵格納部２０５により格納された、当該グループに対応するノードの秘密鍵と、公開情報格納部２０４により格納された、当該ノードの祖先ノードにあたる全てのノード（即ち、当該ノードの親ノードからルートノードまでの全ての祖先ノード）の公開情報とを用いて、メッセージを復元する。
【００３１】
図２の例において、上記の暗号文Ｃを復号する際、復号計算部２０７（Ａ５の端末装置３００でも同様）は、次式（２）の計算を行う。
【数２】
2010193226.tif 000004
・まず、復号計算部２０７は、暗号文ＣからｒＰ０，ｒＰ５，ｒＰ１１，Ｍ＋Ｈ２（＾ｅ（ｓ０Ｐ０，Ｐ２）ｒ）をそれぞれ取り出す（これらは単に並んでいるだけなので、特別な演算なく取り出すことが可能）。
・次に、復号計算部２０７は、暗号文Ｃから取り出したｒＰ０とＡ５の秘密鍵ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１１をペアリング写像＾ｅへの入力とし、＾ｅ（ｒＰ０，ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１１）を計算する。
・また、復号計算部２０７は、公開情報であるＱ２＝ｓ２Ｐ０，Ｑ３＝ｓ３Ｐ０と、暗号文Ｃから取り出したｒＰ５，ｒＰ１１から、それぞれ＾ｅ（Ｑ２，ｒＰ５），＾ｅ（Ｑ３，ｒＰ１１）を計算し、さらにそれらを掛け算して＾ｅ（Ｑ２，ｒＰ５）×＾ｅ（Ｑ３，ｒＰ１１）を計算する。
・復号計算部２０７は、＾ｅ（ｒＰ０，ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１１）を＾ｅ（Ｑ２，ｒＰ５）×＾ｅ（Ｑ３，ｒＰ１１）で割ったものを一方向性ハッシュ関数Ｈ２に入力して、次式（３）を得る。
【数３】
2010193226.tif 000005
・復号計算部２０７は、式（３）と、暗号文Ｃから取り出したＭ＋Ｈ２（＾ｅ（ｓ０Ｐ０，Ｐ２）ｒ）との排他的論理和をとって、メッセージＭを復元する。
【００３２】
端末装置３００（便宜上、Ａ１のみの構成を図示している）は、秘密鍵格納部３０１、公開情報格納部３０２、端末情報格納部３０３、グループ情報格納部３０４、暗号化計算部３０５、復号計算部３０６、グループ情報更新部３０７、グループ鍵検索部３０８、失効端末感知部３０９、失効情報放送部３１０を備える。また、図示していないが、端末装置３００は、処理装置、記憶装置、入力装置、出力装置等のハードウェアを備える。ハードウェアは端末装置３００の各部によって利用される。例えば、処理装置は、端末装置３００の各部でデータや情報の演算、加工、読み取り、書き込み等を行うために利用される。記憶装置は、そのデータや情報を記憶するために利用される。また、入力装置は、そのデータや情報を入力するために、出力装置は、そのデータや情報を出力するために利用される。
【００３３】
秘密鍵格納部３０１は、端末装置３００が暗号文の復号のために鍵管理装置２００より割り当てられた秘密鍵を記憶装置に保管する。なお、秘密鍵は、鍵管理装置２００の秘密鍵格納部２０５により最初に生成された後、予め安全な方法で、割り当て先の端末装置３００の秘密鍵格納部３０１に提供されるものとする。
【００３４】
このように、端末装置３００は、鍵管理装置２００と異なり、秘密鍵については、秘密鍵格納部３０１により格納されている自身に割り当てられた秘密鍵のみを知っている。
【００３５】
公開情報格納部３０２は、鍵管理装置２００より公開された公開情報を記憶装置に保管する。なお、公開情報は、鍵管理装置２００の公開情報格納部２０４により生成された後、公開され、予め端末装置３００の公開情報格納部３０２に提供されるものとする。
【００３６】
端末情報格納部３０３は、全端末装置３００（Ａ１〜Ａ８）のＩＤと上記木構造の末端ノードとの対応関係を示す端末情報を記憶装置に保管する。端末情報格納部３０３は、鍵管理装置２００の端末情報格納部２０１と同様に、端末装置３００のＩＤを、当該端末装置３００に対応する末端ノードの公開鍵として記憶装置に格納することになる。
【００３７】
グループ情報格納部３０４は、各グループを識別できる情報とそれらの親子関係に関する情報をグループ情報として記憶装置に格納する。即ち、グループ情報格納部３０４は、端末装置３００のグループのＩＤと上記木構造のノードとの対応関係を示すグループ情報を記憶装置に保管する。グループ情報格納部３０４は、鍵管理装置２００のグループ情報格納部２０２と同様に、端末装置３００のグループのＩＤを、当該グループに対応するノードの公開鍵として記憶装置に格納することになる。グループ情報格納部３０４は、さらに、失効等によりグループを脱退した端末装置３００の情報を失効情報として記憶装置に保管する。
【００３８】
このように、端末装置は、グループ情報格納部３０４によりグループの階層構造に関する情報を格納するが、この情報については、グループの階層構造の関係さえわかっていればよく、どのような情報を格納するかは任意である。例えば、各グループのグループＩＤや、各グループの階層構造を示す符号が割り当てられている場合にはその符号等でもよい。
【００３９】
暗号化計算部３０５は、鍵管理装置２００の暗号化計算部２０６と同様に、暗号化したいメッセージと端末情報格納部３０３及びグループ情報格納部３０４により格納された公開鍵と公開情報格納部３０２により格納されたルートノードの公開情報とを入力として暗号文を処理装置により作成する。具体的には、暗号化計算部３０５は、他の端末装置３００に送信する（他の端末装置３００の秘密鍵で復号可能な）暗号文を作成する場合、端末情報格納部３０３により格納された、当該他の端末装置３００に対応する末端ノードの公開鍵と、グループ情報格納部３０４により格納された、当該末端ノードの祖先ノードにあたる全てのノード（即ち、当該末端ノードの親ノードからルートノードまでの全ての祖先ノード）の公開鍵と、公開情報格納部３０２により格納されたルートノードの公開情報とを用いて、メッセージを暗号化する。また、暗号化計算部３０５は、あるグループに属する端末装置３００に一括送信する（あるグループの秘密鍵で復号可能な）暗号文を作成する場合、グループ情報格納部３０４により格納された、当該グループに対応するノードの公開鍵と、当該ノードの祖先ノードにあたる全てのノードの公開鍵と、公開情報格納部３０２により格納されたルートノードの公開情報とを用いて、メッセージを暗号化する。
【００４０】
図２の例において、暗号化計算部３０５が暗号文Ｃを作成する処理については、前述した鍵管理装置２００の暗号化計算部２０６の例と同様である。
【００４１】
復号計算部３０６は、鍵管理装置２００の復号計算部２０７と同様に、暗号文と秘密鍵格納部３０１により格納された秘密鍵と公開情報格納部３０２により格納された公開情報とを入力として元のメッセージを処理装置により出力する。具体的には、復号計算部３０６は、自己の公開鍵で暗号化された暗号文を復号する場合、秘密鍵格納部３０１により格納された秘密鍵と、公開情報格納部３０２により格納された、自己に対応する末端ノードの祖先ノードにあたる全てのノード（即ち、当該末端ノードの親ノードからルートノードまでの全ての祖先ノード）の公開情報とを用いて、メッセージを復元する。また、復号計算部３０６は、自己の属するグループの公開鍵で暗号化された暗号文を復号する場合、秘密鍵格納部３０１により格納された秘密鍵と、公開情報格納部３０２により格納された、当該グループに対応するノードの祖先ノードにあたる全てのノード（即ち、当該ノードの親ノードからルートノードまでの全ての祖先ノード）の公開情報とを用いて、メッセージを復元する。
【００４２】
図２の例において、復号計算部３０６が暗号文Ｃを復号する処理については、前述した鍵管理装置２００の復号計算部２０７の例と同様である。
【００４３】
グループ情報更新部３０７は、特定の端末装置３００の失効（当該端末装置３００の暗号鍵の失効）に伴い、グループ情報格納部３０４により格納された失効情報を更新する。
【００４４】
グループ鍵検索部３０８は、特定のグループに対してメッセージを暗号化して送信する際、グループ情報更新部３０７により格納された失効情報に記録されている端末装置３００を除く同グループ内の各端末装置３００が復号できる暗号文を作成するための全公開鍵を検索する。
【００４５】
失効端末感知部３０９は、無線ネットワーク１０１内におけるある端末装置３００が何らかの理由で失効したとき、失効したことを感知し（当該端末装置３００あるいは他の装置から通知を受けたり、自ら当該端末装置３００に定期的に失効していないか確認するメッセージを送ったりする等により感知する）、失効した端末装置３００のＩＤを得る。
【００４６】
失効情報放送部３１０は、失効端末感知部３０９が失効した端末装置３００を感知したとき、その端末装置３００のＩＤを無線ネットワーク１０１内に（即ち、全端末装置３００及び鍵管理装置２００に対して）ブロードキャストする。
【００４７】
なお、本実施の形態では、鍵管理装置２００や各端末装置３００は無線ネットワーク１０１を介して接続されているが、それ以外にも、例えば端末装置３００同士が直列に繋がったマルチホップ型ネットワーク等を介して接続されていてもよい。また、端末装置３００の台数は任意であり、ネットワークトポロジは図示したものに限らない。さらに、鍵管理装置２００が各端末装置３００にＩＤ等の公開鍵や公開情報や秘密鍵等を事前に格納させた場合、鍵管理装置２００は無線ネットワーク１０１と接続されていなくともよい。また、鍵管理装置２００が無線ネットワーク１０１と接続されており、端末装置３００の失効状態を監視する場合には、鍵管理装置２００も、端末装置３００のグループ情報更新部３０７、グループ鍵検索部３０８、失効端末感知部３０９、失効情報放送部３１０と同様の構成要素をもつものとする。
【００４８】
本実施の形態において、端末装置３００は、情報格納部４０１と特定グループ情報生成部４０２とグループ別情報送信部４０３とを備える通信装置の一例である。秘密鍵格納部３０１、公開情報格納部３０２、端末情報格納部３０３、グループ情報格納部３０４は、情報格納部４０１を構成している。グループ情報更新部３０７、グループ鍵検索部３０８、失効端末感知部３０９は、特定グループ情報生成部４０２を構成している。暗号化計算部３０５は、グループ別情報送信部４０３を構成している。
【００４９】
鍵管理装置２００の端末情報格納部２０１、グループ情報格納部２０２、秘密情報格納部２０３、公開情報格納部２０４、秘密鍵格納部２０５により格納される情報、あるいは、端末装置３００の秘密鍵格納部３０１、公開情報格納部３０２、端末情報格納部３０３、グループ情報格納部３０４により格納される情報は、例えば図２のように模式的に表すことができる。前述したように、図２では、鍵が木構造の形に階層的に配置されている。各頂点（ノード）に割り当てられている公開鍵はＩＤ等、任意のデータに設定できるが、秘密情報は特定の方法（例えば非特許文献１と同様の方法等）で算出する。公開情報、秘密鍵は、公開鍵及び秘密情報を基に計算される。鍵管理装置２００は、一番上の根頂点（ルートノード）から一番下の葉頂点（末端ノード）まで計算した後、各葉頂点に割り当てられた公開情報、秘密鍵等を各端末装置３００に格納する。さらに、どの暗号鍵（公開鍵、秘密情報、公開情報、秘密鍵）をどの頂点に割り当てたかを記憶装置に格納する。
【００５０】
暗号鍵の端末装置３００への割り当て方により、末端ノードに対応する暗号鍵の場合、特定の暗号鍵（公開鍵等）で暗号化された暗号文は、その暗号鍵に対応する暗号鍵（秘密鍵等）を保持する端末装置３００（及び鍵の木構造全体を管理する鍵管理装置２００）のみが復号可能となる。また、末端ノード以外のノードに対応する暗号鍵の場合、特定の暗号鍵（公開鍵等）で暗号化された暗号文は、そのノード以下の（子孫ノードにあたる）末端ノードに対応付けられた暗号鍵（秘密鍵等）を保持する各端末装置３００（及び鍵の木構造全体を管理する鍵管理装置２００）のみが復号可能となる。
【００５１】
例えば、公開鍵Ｐ０，Ｐ２，Ｐ５，Ｐ１１及び公開情報Ｑ０を暗号鍵として作成された暗号文は、秘密鍵ｔ１１＝ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１１を保持するＡ５（及び鍵管理装置２００）のみが復号できる。また、例えば、公開鍵Ｐ０，Ｐ２，Ｐ５及び公開情報Ｑ０を暗号鍵として作成された暗号文は、秘密鍵ｔ１１を保持するＡ５、秘密鍵ｔ１２＝ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１２を保持するＡ６（及び鍵管理装置２００）のみが復号できる。また、例えば、公開鍵Ｐ０，Ｐ１及び公開情報Ｑ０を暗号鍵として作成された暗号文は、秘密鍵ｔ７＝ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ７を保持するＡ１、秘密鍵ｔ８＝ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ８を保持するＡ２、秘密鍵ｔ９＝ｓ０Ｐ１＋ｓ１Ｐ４＋ｓ４Ｐ９を保持するＡ３、秘密鍵ｔ１０＝ｓ０Ｐ１＋ｓ１Ｐ４＋ｓ４Ｐ１０を保持するＡ４（及び鍵管理装置２００）のみが復号できる。
【００５２】
例えば、Ａ５〜Ａ８を１つのグループとみなした場合、公開鍵Ｐ０，Ｐ２及び公開情報Ｑ０を暗号鍵として作成された暗号文は、このグループに属する端末装置３００のみが復号可能であるので、当該暗号鍵はＡ５〜Ａ８のグループ鍵と呼ぶことができる。各端末装置３００を１台の端末装置３００からなるグループとみなすことも可能である。
【００５３】
なお、図２に示した木構造は高さが３の２分木であるが、他の木構造を用いてもよい。例えば、それぞれのノードから派生する枝の数は２でなくともよいし、派生する枝の数はそれぞれのノードで異なっていてもよいし、高さは３でなくともよい。つまり、鍵の木構造は２分木でなくともよいし、高さが３でなくともよく、任意のグループ構成が可能である。
【００５４】
本実施の形態では、階層型ＩＤベース暗号方式の暗号鍵を用いることとしているが、他の公開鍵暗号方式の暗号鍵（公開鍵／秘密鍵のペア）を用いてもよいし、共通鍵暗号方式の暗号鍵（共通鍵）を用いてもよい。前者の場合、図２の例において、ルートノードから末端ノードまでの各ノードに公開鍵Ｐ０〜Ｐ１４及びそれぞれの公開鍵とペアになる秘密鍵ｔ０〜ｔ１４が割り当てられる（秘密情報ｓ０〜ｓ６、公開情報Ｑ０〜６は不要である）。例えば、公開鍵Ｐ１１で作成された暗号文は、秘密鍵ｔ１１を保持するＡ５のみが復号できる。また、例えば、公開鍵Ｐ５で作成された暗号文は、秘密鍵ｔ５を保持するＡ５，Ａ６のみが復号できる（Ａ５，Ａ６は秘密鍵ｔ５を共有する）。また、例えば、公開鍵Ｐ１で作成された暗号文は、秘密鍵ｔ１を保持するＡ１〜Ａ４のみが復号できる（Ａ１〜Ａ４は秘密鍵ｔ１を共有する）。共通鍵暗号方式の暗号鍵を用いる場合については、説明を省略するが、同様に、各端末装置３００が自己の共通鍵とグループ鍵を保持する。
【００５５】
図３は、鍵管理装置２００、端末装置３００のハードウェア構成の一例を示す図である。
【００５６】
図３において、鍵管理装置２００、端末装置３００は、コンピュータであり、ＬＣＤ９０１（Ｌｉｑｕｉｄ・Ｃｒｙｓｔａｌ・Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤＤ９０５（Ｃｏｍｐａｃｔ・Ｄｉｓｃ・Ｄｒｉｖｅ）、プリンタ９０６といったハードウェアデバイスを備えている。これらのハードウェアデバイスはケーブルや信号線で接続されている。ＬＣＤ９０１の代わりに、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）、あるいは、その他の表示装置が用いられてもよい。マウス９０３の代わりに、タッチパネル、タッチパッド、トラックボール、ペンタブレット、あるいは、その他のポインティングデバイスが用いられてもよい。
【００５７】
鍵管理装置２００、端末装置３００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）を備えている。ＣＰＵ９１１は、処理装置の一例である。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、ＲＡＭ９１４（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、通信ボード９１５、ＬＣＤ９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ９０６、ＨＤＤ９２０（Ｈａｒｄ・Ｄｉｓｋ・Ｄｒｉｖｅ）と接続され、これらのハードウェアデバイスを制御する。ＨＤＤ９２０の代わりに、フラッシュメモリ、光ディスク装置、メモリカードリーダライタ又はその他の記憶媒体が用いられてもよい。
【００５８】
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、ＨＤＤ９２０は、不揮発性メモリの一例である。これらは、記憶装置の一例である。通信ボード９１５、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５は、入力装置の一例である。また、通信ボード９１５、ＬＣＤ９０１、プリンタ９０６は、出力装置の一例である。
【００５９】
通信ボード９１５は、ＬＡＮ（Ｌｏｃａｌ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）等に接続されている。通信ボード９１５は、ＬＡＮに限らず、ＩＰ−ＶＰＮ（Ｉｎｔｅｒｎｅｔ・Ｐｒｏｔｏｃｏｌ・Ｖｉｒｔｕａｌ・Ｐｒｉｖａｔｅ・Ｎｅｔｗｏｒｋ）、広域ＬＡＮ、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ・Ｔｒａｎｓｆｅｒ・Ｍｏｄｅ）ネットワークといったＷＡＮ（Ｗｉｄｅ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）、あるいは、インターネットに接続されていても構わない。ＬＡＮ、ＷＡＮ、インターネットは、ネットワークの一例である。
【００６０】
ＨＤＤ９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。プログラム群９２３には、本実施の形態の説明において「〜部」として説明する機能を実行するプログラムが含まれている。プログラムは、ＣＰＵ９１１により読み出され実行される。ファイル群９２４には、本実施の形態の説明において、「〜データ」、「〜情報」、「〜ＩＤ（識別子）」、「〜フラグ」、「〜結果」として説明するデータや情報や信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」や「〜テーブル」の各項目として含まれている。「〜ファイル」や「〜データベース」や「〜テーブル」は、ＲＡＭ９１４やＨＤＤ９２０等の記憶媒体に記憶される。ＲＡＭ９１４やＨＤＤ９２０等の記憶媒体に記憶されたデータや情報や信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理（動作）に用いられる。抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理中、データや情報や信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００６１】
本実施の形態の説明において用いるブロック図やフローチャートの矢印の部分は主としてデータや信号の入出力を示す。データや信号は、ＲＡＭ９１４等のメモリ、ＦＤＤ９０４のフレキシブルディスク（ＦＤ）、ＣＤＤ９０５のコンパクトディスク（ＣＤ）、ＨＤＤ９２０の磁気ディスク、光ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）、あるいは、その他の記録媒体に記録される。また、データや信号は、バス９１２、信号線、ケーブル、あるいは、その他の伝送媒体により伝送される。
【００６２】
本実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜工程」、「〜手順」、「〜処理」であってもよい。即ち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアのみ、あるいは、素子、デバイス、基板、配線といったハードウェアのみで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアとハードウェアとの組み合わせ、あるいは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実現されていても構わない。ファームウェアとソフトウェアは、プログラムとして、フレキシブルディスク、コンパクトディスク、磁気ディスク、光ディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。即ち、プログラムは、本実施の形態の説明で述べる「〜部」としてコンピュータを機能させるものである。あるいは、プログラムは、本実施の形態の説明で述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００６３】
次に、暗号システム１００の動作について説明する。
【００６４】
図４は、無線ネットワーク１０１内において他の端末装置３００が失効したときの端末装置３００の動作を示すフローチャートである。
【００６５】
図４において、まず、ステップＳＴ１０１で、失効端末感知部３０９は、近隣の端末装置３００が失効したことを感知する。例えば、各端末装置３００が１分間に１回、定期的にセンシング情報を集計端末（特定の端末装置３００を集計端末とする）に発信するような運用例の場合、そのセンシング情報が途絶えたときに失効したことがわかる。その他にも、端末装置３００の失効そのものに関する技術として公知の方法を用いることができる。ステップＳＴ１０２で、失効情報放送部３１０は、任意の方法を用いて失効を感知した失効端末感知部３０９から、失効した端末装置３００のＩＤを受け取り、受け取ったＩＤを全端末装置３００及び鍵管理装置２００に対してブロードキャストする。この方法により、少なくとも１つの端末装置３００は、無線ネットワーク１０１内において、他の端末装置３００が失効したことを感知し、全端末装置３００及び鍵管理装置２００は、失効した端末装置３００のＩＤを知ることが可能となる。
【００６６】
図５は、失効した端末装置３００に関する通知を受け取った端末装置３００の動作を示すフローチャートである。
【００６７】
図５において、まず、ステップＳＴ１０３で、グループ情報更新部３０７は、失効した端末装置３００のＩＤを他の端末装置３００の失効情報放送部３１０から無線ネットワーク１０１を介して受信する。次に、ステップＳＴ１０４で、グループ情報更新部３０７は、受信した端末装置３００のＩＤをグループ情報格納部３０４により格納された失効情報に書き込む。そして、ステップＳＴ１０５で、グループ情報更新部３０７は、失効情報にＩＤを書き込んだ端末装置３００（失効した端末装置３００）が属するグループをグループ情報格納部３０４により格納されたグループ情報から特定し、特定したグループのＩＤを失効情報に書き込む。グループ情報更新部３０７は、ステップＳＴ１０３〜ＳＴ１０５の動作を、失効した端末装置３００のＩＤを受け取ったら随時行う。
【００６８】
図６は、特定のグループに対して暗号化マルチキャストを行う端末装置３００の動作を示すフローチャートである。
【００６９】
図６において、まず、ステップＳＴ１０６で、グループ鍵検索部３０８は、これから暗号文を送信する相手先グループのＩＤの入力を入力装置により受け付ける。次に、ステップＳＴ１０７で、グループ鍵検索部３０８は、入力されたＩＤとグループ情報格納部３０４により格納された失効情報を照らし合わせ、指定されたグループの中に失効した端末装置３００が存在するかどうか（指定されたグループが、失効した端末装置３００が属するグループかどうか）を処理装置により判定する。
【００７０】
指定されたグループの中に失効した端末装置３００が存在する場合、ステップＳＴ１０８で、グループ鍵検索部３０８は、端末情報格納部３０３により格納された端末情報とグループ情報格納部３０４により格納されたグループ情報とに基づき、前述した木構造にて、指定されたグループに相当する部分木（指定されたグループに対応するノード及びその子孫ノード全てを含む部分木）のうち、失効した端末装置３００に対応する末端ノードと当該端末装置３００が属するグループに対応するノードを除いて残っている部分木を特定し、特定した部分木の各根元にあるノードに対応する暗号鍵（端末情報格納部３０３及びグループ情報格納部３０４により格納された公開鍵）を全て選択する。
【００７１】
一方、指定されたグループの中に失効した端末装置３００が存在しない場合には、ステップＳＴ１０９で、グループ鍵検索部３０８は、指定されたグループに属する端末装置３００のみが復号可能となるグループ鍵１つ（指定されたグループに相当する部分木の根元にあるノードに対応する暗号鍵として、グループ情報格納部３０４により格納された公開鍵）を選択する。
【００７２】
ステップＳＴ１１０で、グループ鍵検索部３０８は、ステップＳＴ１０８又はＳＴ１０９で選択した暗号鍵を出力する。ステップＳＴ１１１で、暗号化計算部３０５は、グループ鍵検索部３０８から出力された１つ又は複数の暗号鍵（端末情報格納部３０３及びグループ情報格納部３０４により格納された公開鍵と公開情報格納部３０２により格納されたルートノードの公開情報）を用いて、送信したいメッセージを暗号化して暗号文を作成し、無線ネットワーク１０１を介してユニキャスト又はマルチキャストで他の端末装置３００へ送信する。
【００７３】
なお、図示していないが、暗号文を受け取った他の端末装置３００では、復号計算部３０６が、秘密鍵格納部３０１により格納された秘密鍵と公開情報格納部３０２により格納された公開情報とを用いて、元のメッセージを得る。
【００７４】
ここで、図２の例において、Ａ６が失効している場合のＡ１の動作について説明する。以下では、一例として、Ａ１がＡ５〜Ａ８に対してメッセージを送信する場合を想定する。
【００７５】
Ａ１がＡ５〜Ａ８に対してメッセージを送信する際に、最も効率よく暗号通信を行うためには、Ａ５〜Ａ８が属するグループに割り当てられた暗号鍵でメッセージを暗号化して、暗号文をマルチキャスト送信するのが望ましい。しかし、ここではＡ６が失効しているため、Ａ６が復号できない暗号文をＡ５，Ａ７，Ａ８へ送信する必要がある。
【００７６】
ステップＳＴ１０６で、Ａ５〜Ａ８が属するグループが指定されると、ステップＳＴ１０７で、Ａ１のグループ鍵検索部３０８は、グループ情報格納部３０４により格納された失効情報を参照して、指定されたグループの中に失効したＡ６が存在することを確認する。そのため、ステップＳＴ１０８で、グループ鍵検索部３０８は、端末情報格納部３０３により格納された端末情報とグループ情報格納部３０４により格納されたグループ情報とに基づき、図７に示すように、指定されたグループに相当する部分木Ｂ１のうち、失効したＡ６に対応する末端ノードとＡ６が属するグループに対応するノードを除いて残っている部分木Ｂ２，Ｂ３を特定する。そして、グループ鍵検索部３０８は、特定した部分木Ｂ２の根元にあるノード（この場合は末端ノード）に対応する暗号鍵、即ち、公開鍵Ｐ０，Ｐ２，Ｐ５，Ｐ１１を選択する。また、グループ鍵検索部３０８は、特定した部分木Ｂ３の根元にあるノードに対応する暗号鍵、即ち、公開鍵Ｐ０，Ｐ２，Ｐ６を選択する。
【００７７】
ステップＳＴ１１０で、グループ鍵検索部３０８は、ステップＳＴ１０８で選択した公開鍵Ｐ０，Ｐ２，Ｐ５，Ｐ１１の組み合わせ、及び、公開鍵Ｐ０，Ｐ２，Ｐ６の組み合わせを出力する。ステップＳＴ１１１で、Ａ１の暗号化計算部３０５は、グループ鍵検索部３０８から出力された公開鍵Ｐ０，Ｐ２，Ｐ５，Ｐ１１及び公開情報Ｑ０を用いて暗号文を作成し、無線ネットワーク１０１を介してユニキャストでＡ５へ送信する。また、暗号化計算部３０５は、グループ鍵検索部３０８から出力された公開鍵Ｐ０，Ｐ２，Ｐ６及び公開情報Ｑ０を用いて暗号文を作成し、無線ネットワーク１０１を介してマルチキャストでＡ７，Ａ８へ送信する。
【００７８】
このように、グループ鍵検索部３０８は、Ａ５〜Ａ８のグループが指定されると、失効情報を参照して、適切なグループ鍵の検索を行う。上記の例では、Ａ６が失効しているので、指定されたグループの中に失効した端末装置３００が存在するかどうかの答えは真である。よって、その端末装置３００、即ち、Ａ６を除くＡ５，Ａ７，Ａ８のみが復号可能な暗号文を作成するための鍵、具体的には公開鍵Ｐ０，Ｐ２，Ｐ５，Ｐ１１の組み合わせ、及び、公開鍵Ｐ０，Ｐ２，Ｐ６の組み合わせを選択し、出力する。出力された公開鍵は暗号化したいメッセージとともに暗号化計算部３０５に入力され、暗号文が作成される。この例では、公開鍵Ｐ０，Ｐ２，Ｐ５，Ｐ１１及び公開情報Ｑ０で暗号化されたＡ５のみが復号可能な暗号文と、公開鍵Ｐ０，Ｐ２，Ｐ６及び公開情報Ｑ０で暗号化されたＡ７，Ａ８のみが復号可能な暗号文の２種類が出力される。
【００７９】
ここで、別の例として、Ａ８がＡ１〜Ａ４に対してメッセージを送信する場合を考える。この場合、Ａ８のグループ鍵検索部３０８には、Ａ１〜Ａ４が属するグループのＩＤが入力される。そのグループ内に失効した端末装置３００はないので、グループ鍵検索部３０８から出力されるグループ鍵は公開鍵Ｐ０，Ｐ１のみとなる。出力された公開鍵は暗号化したいメッセージとともに暗号化計算部３０５に入力され、暗号文が作成される。この例では、Ａ１〜Ａ４の全てかつそれらの端末装置３００のみが復号可能な暗号文が出力される。
【００８０】
なお、上記の例ではＡ６が失効している場合を想定していたが、他の端末装置３００が失効していても同様の手順によりグループ内の失効した端末装置３００以外の端末装置３００のみが復号可能な暗号文を作成できる。さらに、複数の端末装置３００が失効していても同様の手順によりグループ内の失効した端末装置３００以外の端末装置３００のみが復号可能な暗号文を作成できる。
【００８１】
以上のように、本実施の形態では、通信装置の一例である端末装置３００において、情報格納部４０１は、木構造の末端ノードに、端末装置３００に割り当てられている個別の暗号鍵（公開鍵や公開情報）を対応付け、末端ノードと暗号鍵との対応関係を示す鍵情報（例えば、図２に示したような情報）を記憶装置に格納する。また、情報格納部４０１は、記憶装置に格納された鍵情報で個別の暗号鍵が対応付けられた末端ノードに、当該暗号鍵が割り当てられている端末装置３００を対応付け、末端ノードと端末装置３００との対応関係を示す端末情報（例えば、図２に示したような情報）を記憶装置に格納する。情報格納部４０１は、さらに、上記木構造の末端ノード以外のノードに、記憶装置に格納された端末情報で当該ノードの子孫ノードにあたる末端ノードに対応付けられた端末装置３００からなる端末装置３００のグループを対応付け、ノードと端末装置３００のグループとの対応関係を示す端末グループ情報（前述したグループ情報）（例えば、図２に示したような情報）を記憶装置に格納する。そして、情報格納部４０１は、鍵情報として、さらに、上記木構造の末端ノード以外のノードに、記憶装置に格納された端末グループ情報で当該ノードに対応付けられたグループに属する端末装置３００に割り当てられている共通の暗号鍵（公開鍵や公開情報）を対応付け、ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納する。
【００８２】
特定グループ情報生成部４０２は、割り当てられている暗号鍵が失効した端末装置３００がある場合、情報格納部４０１により格納された端末情報に基づいて、当該端末装置３００に対応する末端ノードと当該末端ノードの祖先ノードとを上記木構造から除外することにより形成される部分木ごとに、同じ部分木に含まれる末端ノードに対応する端末装置３００を有効端末として特定する。そして、特定グループ情報生成部４０２は、当該有効端末からなる端末装置３００のグループを示す特定グループ情報（例えば、図７に示したような情報）を処理装置により生成し、生成した特定グループ情報を記憶装置に格納する。
【００８３】
グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成する。そして、グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、生成したグループ別情報を同じグループに属する端末装置３００へ送信し、当該端末装置３００に対して、送信したグループ別情報を利用させる。本実施の形態では、グループ別情報送信部４０３は、情報格納部４０１により格納された鍵情報と端末グループ情報とに基づいて、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、当該グループに対応するノードを有効ノードとして特定し、当該有効ノードに対応する暗号鍵を用いて暗号文をグループ別情報として処理装置により生成する。そして、グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、生成した暗号文を同じグループに属する端末装置へ送信し、当該端末装置に対して、送信した暗号文を復号させる。
【００８４】
本実施の形態によれば、木構造に従ってグループ分けされた複数の端末装置３００（例えばＡ１〜Ａ８）に対し、同じ木構造で管理される暗号鍵を配布する方式において、いずれかの端末装置３００（例えばＡ６）の暗号鍵が何らかの理由で失効した場合でも、その端末装置３００と同じグループに属していた各端末装置３００（例えばＡ５，Ａ７，Ａ８）と安全に効率よく通信することができる。
【００８５】
以上述べたように、本実施の形態では、端末装置３００が、メッセージを送信するグループ内に失効した端末装置３００が存在していても、グループ内の失効した端末装置３００以外の端末装置３００全てかつそれらのみが復号可能な暗号文を効率よく作成することができる。つまり、端末装置３００が、いくつかの他の端末装置３００が何らかの理由で失効した場合でも、失効した端末装置３００を除く同じグループに属する端末装置３００に対して効率よく暗号化通信を行うことができる。
【００８６】
実施の形態２．
本実施の形態について、主に実施の形態１との差異を説明する。
【００８７】
図８は、本実施の形態に係る暗号システム１００の構成を示すブロック図である。
【００８８】
図８において、暗号システム１００は、実施の形態１と同様に、鍵管理装置２００、Ａ１〜Ａ８の８台の端末装置３００を備える。
【００８９】
本実施の形態において、端末装置３００の暗号鍵、端末装置３００のグループの暗号鍵は、実施の形態１と同様に、図２に示すような木構造によって管理される階層型ＩＤベース暗号方式の暗号鍵（公開鍵、公開情報、秘密鍵の組み合わせ）である。端末装置３００、端末装置３００のグループも、同じ木構造によって管理される。
【００９０】
鍵管理装置２００は、実施の形態１と同様の構成要素のほか、さらに、鍵更新情報作成部２０８、鍵更新パケット作成部２０９を備える。
【００９１】
鍵更新情報作成部２０８は、ある端末装置３００が失効した場合、秘密情報格納部２０３により格納された秘密情報を更新し、公開情報格納部２０４及び秘密鍵格納部２０５に公開情報及び秘密鍵を更新させるとともに、秘密鍵格納部２０５により格納された更新前の秘密鍵と更新後の秘密鍵との差分を鍵更新情報として出力する。
【００９２】
鍵更新パケット作成部２０９は、鍵更新情報作成部２０８により出力された鍵更新情報を（望ましくは、所定の方法により暗号化した上で）１つの送信パケット（通信データの一例）に加工し、失効した端末装置３００以外の端末装置３００へ送信する。
【００９３】
実施の形態１と異なり、本実施の形態において、鍵管理装置２００は、情報格納部４０１と特定グループ情報生成部４０２とグループ別情報送信部４０３とを備える通信装置の一例である。端末情報格納部２０１、グループ情報格納部２０２、秘密情報格納部２０３、公開情報格納部２０４、秘密鍵格納部２０５は、情報格納部４０１を構成している。鍵更新情報作成部２０８は、特定グループ情報生成部４０２を構成している。暗号化計算部２０６、鍵更新パケット作成部２０９は、グループ別情報送信部４０３を構成している。
【００９４】
端末装置３００（便宜上、Ａ１のみの構成を図示している）は、実施の形態１と同様の構成要素のほか、さらに、秘密鍵更新部３１１を備える。
【００９５】
秘密鍵更新部３１１は、鍵管理装置２００の鍵更新パケット作成部２０９により送信されたパケットに含まれる鍵更新情報に基づいて秘密鍵格納部３０１により格納された秘密鍵を更新する。
【００９６】
次に、暗号システム１００の動作について説明する。
【００９７】
無線ネットワーク１０１内において他の端末装置３００が失効したときの端末装置３００の動作については、図４に示した実施の形態１のものと同様である。
【００９８】
図９は、失効した端末装置３００に関する通知を受け取った鍵管理装置２００の動作を示すフローチャートである。
【００９９】
図９において、まず、ステップＳＴ２０１で、グループ情報格納部２０２は、失効した端末装置３００のＩＤを他の端末装置３００の失効情報放送部３１０から無線ネットワーク１０１を介して受信する。次に、ステップＳＴ２０２で、グループ情報格納部２０２は、受信した端末装置３００のＩＤを失効情報に書き込む。そして、ステップＳＴ２０３で、グループ情報格納部２０２は、失効情報にＩＤを書き込んだ端末装置３００（失効した端末装置３００）が属するグループをグループ情報から特定し、特定したグループのＩＤを失効情報に書き込む。
【０１００】
ステップＳＴ２０４で、鍵更新情報作成部２０８は、グループ情報格納部２０２により格納された失効情報を参照して、失効した端末装置３００が属するグループに対応するノード（即ち、失効した端末装置３００に対応する末端ノードの親ノードからルートノードまでの全ての祖先ノード）を特定する。そして、鍵更新情報作成部２０８は、秘密情報格納部２０３により格納された秘密情報のうち、特定したノードの各々に対応する秘密情報を更新する。ステップＳＴ２０５で、鍵更新情報作成部２０８は、公開情報格納部２０４に対し、秘密情報格納部２０３により格納された更新後の秘密情報とグループ情報格納部２０２により格納されたルートノードの公開鍵を入力として公開情報を更新させる。また、鍵更新情報作成部２０８は、秘密鍵格納部２０５に対し、秘密情報格納部２０３により格納された更新後の秘密情報と端末情報格納部２０１及びグループ情報格納部２０２により格納された公開鍵を入力として秘密鍵を更新させる。このとき、秘密鍵格納部２０５は、更新後の秘密鍵とともに更新前の秘密鍵を一時的に記憶装置に格納しておく。なお、公開鍵は変更する必要がない。
【０１０１】
ステップＳＴ２０６で、鍵更新情報作成部２０８は、各端末装置３００に配送する鍵更新情報を作成する。具体的には、鍵更新情報作成部２０８は、端末情報格納部３０３により格納された端末情報とグループ情報格納部３０４により格納されたグループ情報とに基づき、前述した木構造のうち、失効した端末装置３００に対応する末端ノードと当該端末装置３００が属するグループに対応するノードを除いて残っている部分木を特定する。そして、鍵更新情報作成部２０８は、特定した部分木ごとに、部分木に含まれる１つ又は複数の末端ノードのそれぞれに対応する端末装置３００を特定し、秘密鍵格納部２０５により格納された更新前の秘密鍵と更新後の秘密鍵のうち、特定した端末装置３００のいずれか１つの更新前の秘密鍵と更新後の秘密鍵（どの端末装置３００の秘密鍵を選んでも差分は同じである）を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵と更新後の秘密鍵との差分を計算し、鍵更新情報として出力する。なお、秘密鍵格納部２０５は更新前の秘密鍵をいつまでも保持しておく必要はなく、鍵更新情報が作成された時点で消去して構わない。
【０１０２】
ステップＳＴ２０７で、暗号化計算部２０６は、鍵更新情報作成部２０８から出力された鍵更新情報と鍵更新情報の各配送先に対応する公開鍵とルートノードの更新前の公開情報とを入力として、配送先ごとの暗号文を作成する。ステップＳＴ２０８で、鍵更新パケット作成部２０９は、暗号化計算部２０６により作成された暗号文を、任意の方法を用いて１つのブロードキャストメッセージにまとめて出力する。
【０１０３】
なお、図示していないが、上記ブロードキャストメッセージを受信した端末装置３００では、復号計算部３０６が、秘密鍵格納部３０１により格納された更新前の秘密鍵と公開情報格納部３０２により格納された更新前の公開情報とを用いて、鍵更新情報を得る。そして、秘密鍵更新部３１１は、復号計算部３０６により得られた鍵更新情報を、秘密鍵格納部３０１により格納された更新前の秘密鍵に加算して当該秘密鍵を更新する。
【０１０４】
ここで、図２の例において、Ａ６が失効した場合の鍵管理装置２００の動作について説明する。
【０１０５】
ステップＳＴ２０４で、鍵更新情報作成部２０８は、グループ情報格納部２０２により格納された失効情報を参照して、図１０に示すように、失効したＡ６が属するグループに対応するノードを全て特定する。ここでは、Ａ５，Ａ６からなるグループに対応するノード、Ａ５〜Ａ８からなるグループに対応するノード、ルートノードが特定されることになる。鍵更新情報作成部２０８は、秘密情報格納部２０３により格納された秘密情報のうち、特定したノードの各々に対応する秘密情報ｓ０，ｓ２，ｓ５を秘密情報ｓ０’，ｓ２’，ｓ５’に更新する。ステップＳＴ２０５で、鍵更新情報作成部２０８は、公開情報格納部２０４に対し、秘密情報格納部２０３により格納された更新後の秘密情報ｓ０’，ｓ２’，ｓ５’とグループ情報格納部２０２により格納されたルートノードの公開鍵Ｐ０を入力として公開情報Ｑ０，Ｑ２，Ｑ５を公開情報Ｑ０’＝ｓ０’Ｐ０、Ｑ２’＝ｓ２’Ｐ０、Ｑ５’＝ｓ５’Ｐ０に更新させる。また、鍵更新情報作成部２０８は、秘密鍵格納部２０５に対し、秘密情報格納部２０３により格納された更新後の秘密情報ｓ０’，ｓ２’，ｓ５’と端末情報格納部２０１及びグループ情報格納部２０２により格納された公開鍵Ｐ０〜Ｐ１４を入力として秘密鍵ｔ１〜ｔ１４を秘密鍵ｔ１’〜ｔ１４’に更新させる。このとき、秘密鍵格納部２０５は、更新後の秘密鍵ｔ１’〜ｔ１４’とともに更新前の秘密鍵ｔ１〜ｔ１４を一時的に記憶装置に格納しておく。
【０１０６】
ステップＳＴ２０６で、鍵更新情報作成部２０８は、端末情報格納部３０３により格納された端末情報とグループ情報格納部３０４により格納されたグループ情報とに基づき、図１０に示すように、木構造のうち、失効したＡ６とＡ６が属するグループに対応するノードを除いて残っている部分木Ｂ１〜Ｂ３を特定する。そして、鍵更新情報作成部２０８は、部分木Ｂ１については、部分木Ｂ１に含まれる末端ノードに対応するＡ１〜Ａ４を特定し、Ａ１〜Ａ４のいずれか１つ（例えば、Ａ１）の更新前の秘密鍵ｔ７＝ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ７と更新後の秘密鍵ｔ７’＝ｓ０’Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ７を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵ｔ７と更新後の秘密鍵ｔ７’との差分ｄ１＝ｔ７−ｔ７’＝ｓ０’Ｐ１−ｓ０Ｐ１を計算し、鍵更新情報として出力する（Ａ２〜Ａ４の更新前の秘密鍵ｔ８〜ｔ１０と更新後の秘密鍵ｔ８’〜ｔ１０’との差分もｄ１＝ｓ０’Ｐ１−ｓ０Ｐ１になる）。同様に、鍵更新情報作成部２０８は、部分木Ｂ２については、部分木Ｂ２に含まれる末端ノードに対応するＡ５を特定し、Ａ５の更新前の秘密鍵ｔ１１＝ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１１と更新後の秘密鍵ｔ１１’＝ｓ０’Ｐ２＋ｓ２’Ｐ５＋ｓ５’Ｐ１１を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵ｔ１１と更新後の秘密鍵ｔ１１’との差分ｄ２＝ｔ１１−ｔ１１’＝（ｓ０’Ｐ２＋ｓ２’Ｐ５＋ｓ５’Ｐ１１）−（ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１１）を計算し、鍵更新情報として出力する。同様に、鍵更新情報作成部２０８は、部分木Ｂ３については、部分木Ｂ３に含まれる末端ノードに対応するＡ７，Ａ８を特定し、Ａ７，Ａ８のいずれか１つ（例えば、Ａ７）の更新前の秘密鍵ｔ１３＝ｓ０Ｐ２＋ｓ２Ｐ６＋ｓ６Ｐ１３と更新後の秘密鍵ｔ１３’＝ｓ０’Ｐ２＋ｓ２’Ｐ６＋ｓ６Ｐ１３を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵ｔ１３と更新後の秘密鍵ｔ１３’との差分ｄ３＝ｔ１３−ｔ１３’＝（ｓ０’Ｐ２＋ｓ２’Ｐ６）−（ｓ０Ｐ２＋ｓ２Ｐ６）を計算し、鍵更新情報として出力する（Ａ８の更新前の秘密鍵ｔ１４と更新後の秘密鍵ｔ１４’との差分もｄ３＝（ｓ０’Ｐ２＋ｓ２’Ｐ６）−（ｓ０Ｐ２＋ｓ２Ｐ６）になる）。
【０１０７】
ステップＳＴ２０７で、暗号化計算部２０６は、鍵更新情報作成部２０８から出力された鍵更新情報ｄ１〜ｄ３を暗号化し、それぞれに対応する３つの暗号文を作成する。ステップＳＴ２０８で、鍵更新パケット作成部２０９は、暗号化計算部２０６により作成された３つの暗号文を、任意の方法を用いて１つのブロードキャストメッセージにまとめて無線ネットワーク１０１に送信する。
【０１０８】
Ａ１〜Ａ４では、秘密鍵更新部３１１が、上記ブロードキャストメッセージに含まれる鍵更新情報ｄ１を、秘密鍵格納部３０１により格納された更新前の秘密鍵ｔ７〜ｔ１０に加算することで、更新後の秘密鍵ｔ７’〜ｔ１０’を得る。同様に、Ａ５では、秘密鍵更新部３１１が、上記ブロードキャストメッセージに含まれる鍵更新情報ｄ２を、秘密鍵格納部３０１により格納された更新前の秘密鍵ｔ１１に加算することで、更新後の秘密鍵ｔ１１’を得る。同様に、Ａ７，Ａ８では、秘密鍵更新部３１１が、上記ブロードキャストメッセージに含まれる鍵更新情報ｄ３を、秘密鍵格納部３０１により格納された更新前の秘密鍵ｔ１３，ｔ１４に加算することで、更新後の秘密鍵ｔ１３’，ｔ１４’を得る。
【０１０９】
このように、Ａ６が失効したことを知らせるメッセージを鍵管理装置２００が受信したとき、鍵更新情報作成部２０８は、木構造の各ノードに対応する秘密鍵を更新する。そして、鍵更新情報作成部２０８は、Ａ１〜Ａ４に対して同一の鍵更新情報ｄ１を、更新前の秘密鍵ｔ７及び更新前の秘密鍵ｔ７’から作成する。同様に、鍵更新情報作成部２０８は、Ａ５に対する鍵更新情報ｄ２を、更新前の秘密鍵ｔ１１及び更新後の秘密鍵ｔ１１’から作成する。なお、Ａ５については、失効したＡ６を避けたグループが存在しないので、鍵更新情報ｄ２の代わりに秘密鍵ｔ１１’そのものを送信してもよい。つまり、複数の端末装置３００に対して同一の鍵更新情報を安全に暗号化送信できるときは鍵更新情報を、単一の端末装置３００にしか暗号化通信ができない場合には暗号鍵そのものを出力するようにしてもよい。鍵更新情報作成部２０８は、Ａ７，Ａ８に対して同一の鍵更新情報ｄ３を、更新前の秘密鍵ｔ１３及び更新前の秘密鍵ｔ１３’から作成する。
【０１１０】
Ａ１〜Ａ４は、鍵管理装置２００によって送信されたブロードキャストメッセージを受け取った後、復号計算部３０６にて、そのメッセージから任意の方法で自身の鍵更新情報ｄ１を暗号化した暗号文を検索し、復号してｄ１を取り出す。そして、自身が保持する秘密鍵ｔ７〜ｔ１０とｄ１とを秘密鍵更新部３１１に入力し、新しい秘密鍵ｔ７’〜ｔ１０’を出力する。Ａ５，Ａ７，Ａ８も同様にして新しい秘密鍵ｔ１１’，ｔ１３’，ｔ１４’を取得する。ここで、失効したＡ６は、どの暗号文も復号できないため、秘密鍵を更新できないことに注意されたい。
【０１１１】
以上のように、本実施の形態では、通信装置の一例である鍵管理装置２００において、情報格納部４０１は、木構造の末端ノードに、端末装置３００に割り当てられている個別の暗号鍵（秘密鍵）を対応付け、末端ノードと暗号鍵との対応関係を示す鍵情報（例えば、図２に示したような情報）を記憶装置に格納する。また、情報格納部４０１は、記憶装置に格納された鍵情報で個別の暗号鍵が対応付けられた末端ノードに、当該暗号鍵が割り当てられている端末装置３００を対応付け、末端ノードと端末装置３００との対応関係を示す端末情報（例えば、図２に示したような情報）を記憶装置に格納する。情報格納部４０１は、鍵情報として、さらに、上記木構造のルートノード以外かつ末端ノード以外のノードに、当該ノードの子ノードに対応する暗号鍵を生成するために用いられる暗号鍵（秘密鍵）を対応付け、ノードと暗号鍵との対応関係を示す鍵情報を記憶装置に格納する。情報格納部４０１は、さらに、上記木構造の末端ノード以外のノードに、記憶装置に格納された端末情報で当該ノードの子孫ノードにあたる末端ノードに対応付けられた端末装置３００からなる端末装置３００のグループを対応付け、ノードと端末装置のグループとの対応関係を示す端末グループ情報（前述したグループ情報）（例えば、図２に示したような情報）を記憶装置に格納する。
【０１１２】
特定グループ情報生成部４０２は、割り当てられている暗号鍵が失効した端末装置３００がある場合、情報格納部４０１により格納された端末情報に基づいて、当該端末装置３００に対応する末端ノードと当該末端ノードの祖先ノードとを上記木構造から除外することにより形成される部分木ごとに、同じ部分木に含まれる末端ノードに対応する端末装置３００を有効端末として特定する。そして、特定グループ情報生成部４０２は、当該有効端末からなる端末装置３００のグループを示す特定グループ情報（例えば、図１０に示したような情報）を処理装置により生成し、生成した特定グループ情報を記憶装置に格納する。
【０１１３】
グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成する。そして、グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、生成したグループ別情報を同じグループに属する端末装置３００へ送信し、当該端末装置３００に対して、送信したグループ別情報を利用させる。本実施の形態では、グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、暗号鍵を更新するための鍵更新情報をグループ別情報として処理装置により生成する。そして、グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、生成した鍵更新情報を同じグループに属する端末装置３００へ送信し、当該端末装置３００に対して、送信した鍵更新情報により当該端末装置３００に割り当てられている暗号鍵を更新させる。具体的には、グループ別情報送信部４０３は、情報格納部４０１により格納された鍵情報と端末グループ情報とに基づいて、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、当該グループに対応するノードを有効ノードとして特定し、当該有効ノードの親ノードに対応する暗号鍵を更新し、当該暗号鍵の更新前後の差分情報を鍵更新情報として処理装置により生成する。そして、グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、生成した差分情報を同じグループに属する端末装置３００へ送信し、当該端末装置３００に対して、送信した差分情報により当該端末装置３００に割り当てられている暗号鍵を更新させる。
【０１１４】
また、本実施の形態では、端末装置３００に割り当てられている暗号鍵は、階層型ＩＤベース暗号方式にて上記木構造のノードに割り当てられる識別子（ＩＤ）と秘密情報とを基に生成される秘密鍵である。そして、グループ別情報送信部４０３は、情報格納部４０１により格納された鍵情報と端末グループ情報とに基づいて、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、当該グループに対応するノードを有効ノードとして特定し、ルートノードから当該有効ノードの親ノードまでの各ノードに割り当てられた秘密情報を更新することにより、各ノードに対応する秘密鍵を更新し、当該有効ノードの親ノードに対応する秘密鍵の更新前後の差分情報を鍵更新情報として処理装置により生成する。
【０１１５】
本実施の形態によれば、木構造に従ってグループ分けされた複数の端末装置３００（例えばＡ１〜Ａ８）に対し、同じ木構造で管理される暗号鍵を配布する方式において、いずれかの端末装置３００（例えばＡ６）の暗号鍵が何らかの理由で失効した場合でも、その端末装置３００と同じグループに属していた各端末装置３００（例えばＡ５，Ａ７，Ａ８）と安全に効率よく通信することができる。
【０１１６】
以上述べたように、本実施の形態では、暗号システム１００が、ある特定の端末装置３００に格納された秘密鍵を除き、全端末装置３００に格納された秘密鍵を効率よく更新することができる。鍵管理装置２００は、失効した端末装置３００以外の全端末装置３００に格納された秘密鍵を効率よく更新するための情報を暗号化し、効率よく配送することができる。そのために、鍵管理装置２００は、失効した端末装置３００以外の全端末装置３００に格納された秘密鍵を更新するための効率のよい情報を計算する鍵更新情報作成部２０８を備える。また、鍵管理装置２００は、失効した端末装置３００以外の全端末装置３００に格納された秘密鍵を更新するための情報を効率よく暗号化して配送する鍵更新パケット作成部２０９を備える。端末装置３００は、効率よく格納された秘密鍵を更新することができる。
【０１１７】
本実施の形態によれば、各端末装置３００に対して更新した秘密鍵を暗号化してユニキャストした場合に比べて、暗号文の種類が格段に減る（例えば、８台の端末装置３００がある場合に、１台の端末装置３００が失効したときの暗号文は３種類となり、１０２４台の端末装置３００がある場合に、１台の端末装置３００が失効したときの暗号文は１０種類となる）。また、メッセージを１つにまとめることで、ある端末装置３００を介して別の端末装置３００にメッセージを転送する可能性がある無線ネットワーク１０１において、どの端末装置３００も１つのメッセージから鍵更新情報を取り出すことが可能となり、通信の効率化が図れる（暗号文を別々に送信すると、端末装置３００にとって意味のない（復号できない）メッセージも受け取って転送しなければならない場合が発生する）。
【０１１８】
実施の形態３．
本実施の形態について、主に実施の形態２との差異を説明する。
【０１１９】
実施の形態２では、端末装置３００が失効した場合、鍵管理装置２００は、失効した端末装置３００が属するグループに対応するノードの秘密情報を更新し、それによって全ての端末装置３００の秘密鍵を更新する。これに対し、本実施の形態では、端末装置３００が失効した場合、鍵管理装置２００は、失効した端末装置３００が属するグループに対応するノードの公開鍵（グループのＩＤ）を更新し（秘密情報は更新しなくてよい）、それによって全ての端末装置３００の秘密鍵を更新する。
【０１２０】
以下、本実施の形態に係る暗号システム１００の動作について説明する。
【０１２１】
無線ネットワーク１０１内において他の端末装置３００が失効したときの端末装置３００の動作については、図４に示した実施の形態１のものと同様である。
【０１２２】
以下では、図９を用いて、失効した端末装置３００に関する通知を受け取った鍵管理装置２００の動作を説明する。
【０１２３】
ステップＳＴ２０１〜ＳＴ２０３については、実施の形態２と同様である。
【０１２４】
ステップＳＴ２０４で、鍵更新情報作成部２０８は、グループ情報格納部２０２により格納された失効情報を参照して、失効した端末装置３００が属するグループに対応するノード（即ち、失効した端末装置３００に対応する末端ノードの親ノードからルートノードの子ノードまでの全ての祖先ノード）を特定する（ルートノードの公開鍵は秘密鍵の生成には用いられないため、ルートノードは対象に含めなくてよい）。そして、鍵更新情報作成部２０８は、グループ情報格納部３０４により格納された公開鍵のうち、特定したノードの各々に対応する公開鍵を更新する。ステップＳＴ２０５で、鍵更新情報作成部２０８は、秘密鍵格納部２０５に対し、秘密情報格納部２０３により格納された秘密情報と端末情報格納部２０１により格納された公開鍵及びグループ情報格納部２０２により格納された更新後の公開鍵を入力として秘密鍵を更新させる。このとき、秘密鍵格納部２０５は、更新後の秘密鍵とともに更新前の秘密鍵を一時的に記憶装置に格納しておく。なお、秘密情報、公開情報は変更する必要がない。
【０１２５】
ステップＳＴ２０６，ＳＴ２０７については、実施の形態２と同様である。
【０１２６】
ここで、図２の例において、Ａ６が失効した場合の鍵管理装置２００の動作について説明する。
【０１２７】
ステップＳＴ２０４で、鍵更新情報作成部２０８は、グループ情報格納部２０２により格納された失効情報を参照して、図１１に示すように、失効したＡ６が属するグループに対応するノードを全て特定する。ここでは、Ａ５，Ａ６からなるグループに対応するノード、Ａ５〜Ａ８からなるグループに対応するノードが特定されることになる。なお、前述したように、ルートノードの公開鍵は秘密鍵の生成には用いられないため、ルートノードは対象外となる。鍵更新情報作成部２０８は、グループ情報格納部３０４により格納された公開鍵のうち、特定したノードの各々に対応する公開鍵Ｐ２，Ｐ５を公開鍵Ｐ２’，Ｐ５’に更新する。ステップＳＴ２０５で、鍵更新情報作成部２０８は、秘密鍵格納部２０５に対し、秘密情報格納部２０３により格納された秘密情報と端末情報格納部２０１及びグループ情報格納部２０２により格納された公開鍵（更新前の公開鍵と更新後の公開鍵とを用いて差分更新を行ってもよい）を入力として秘密鍵ｔ２，ｔ５，ｔ６，ｔ１１，ｔ１３，ｔ１４を秘密鍵ｔ２’，ｔ５’，ｔ６’，ｔ１１’，ｔ１３’，ｔ１４’に更新させる。このとき、秘密鍵格納部２０５は、更新後の秘密鍵ｔ２’，ｔ５’，ｔ６’，ｔ１１’，ｔ１３’，ｔ１４’とともに更新前の秘密鍵ｔ２，ｔ５，ｔ６，ｔ１１，ｔ１３，ｔ１４を一時的に記憶装置に格納しておく。
【０１２８】
ステップＳＴ２０６で、鍵更新情報作成部２０８は、端末情報格納部３０３により格納された端末情報とグループ情報格納部３０４により格納されたグループ情報とに基づき、図１１に示すように、木構造のうち、失効したＡ６とＡ６が属するグループに対応するノードを除いて残っている部分木Ｂ１，Ｂ２を特定する。そして、鍵更新情報作成部２０８は、部分木Ｂ１については、部分木Ｂ１に含まれる末端ノードに対応するＡ５を特定し、Ａ５の更新前の秘密鍵ｔ１１＝ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１１と更新後の秘密鍵ｔ１１’＝ｓ０Ｐ２’＋ｓ２Ｐ５’＋ｓ５Ｐ１１を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵ｔ１１と更新後の秘密鍵ｔ１１’との差分ｄ２＝ｔ１１−ｔ１１’＝（ｓ０Ｐ２’＋ｓ２Ｐ５’）−（ｓ０Ｐ２＋ｓ２Ｐ５）を計算し、鍵更新情報として出力する。同様に、鍵更新情報作成部２０８は、部分木Ｂ２については、部分木Ｂ２に含まれる末端ノードに対応するＡ７，Ａ８を特定し、Ａ７，Ａ８のいずれか１つ（例えば、Ａ７）の更新前の秘密鍵ｔ１３＝ｓ０Ｐ２＋ｓ２Ｐ６＋ｓ６Ｐ１３と更新後の秘密鍵ｔ１３’＝ｓ０Ｐ２’＋ｓ２Ｐ６＋ｓ６Ｐ１３を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵ｔ１３と更新後の秘密鍵ｔ１３’との差分ｄ３＝ｔ１３−ｔ１３’＝ｓ０Ｐ２’−ｓ０Ｐ２を計算し、鍵更新情報として出力する（Ａ８の更新前の秘密鍵ｔ１４と更新後の秘密鍵ｔ１４’との差分もｄ３＝ｓ０Ｐ２’−ｓ０Ｐ２になる）。
【０１２９】
ステップＳＴ２０７で、暗号化計算部２０６は、鍵更新情報作成部２０８から出力された鍵更新情報ｄ１，ｄ２を暗号化し、それぞれに対応する２つの暗号文を作成する。ステップＳＴ２０８で、鍵更新パケット作成部２０９は、暗号化計算部２０６により作成された３つの暗号文を、任意の方法を用いて１つのブロードキャストメッセージにまとめて無線ネットワーク１０１に送信する。
【０１３０】
以上のように、本実施の形態では、通信装置の一例である鍵管理装置２００において、グループ別情報送信部４０３は、情報格納部４０１により格納された鍵情報と端末グループ情報とに基づいて、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、当該グループに対応するノードを有効ノードとして特定し、ルートノードから当該有効ノードの親ノードまでの各ノードに割り当てられた識別子を更新することにより、各ノードに対応する秘密鍵を更新し、当該有効ノードの親ノードに対応する秘密鍵の更新前後の差分情報を鍵更新情報として処理装置により生成する。
【０１３１】
本実施の形態によれば、実施の形態２と同様に、木構造に従ってグループ分けされた複数の端末装置３００（例えばＡ１〜Ａ８）に対し、同じ木構造で管理される暗号鍵を配布する方式において、いずれかの端末装置３００（例えばＡ６）の暗号鍵が何らかの理由で失効した場合でも、その端末装置３００と同じグループに属していた各端末装置３００（例えばＡ５，Ａ７，Ａ８）と安全に効率よく通信することができる。
【０１３２】
実施の形態４．
本実施の形態について、主に実施の形態３との差異を説明する。
【０１３３】
実施の形態３では、鍵管理装置２００の秘密鍵格納部２０５は、ルートノードの秘密鍵を生成しないが、本実施の形態では、ルートノードの秘密鍵も生成するものとする。そのため、本実施の形態では、ルートノードの秘密鍵の基となる秘密情報と公開鍵が別途必要となる。
【０１３４】
図２の例を本実施の形態に合わせて変更したものを図１２に示す。以下、図１２の例を用いて、鍵管理装置２００の公開情報格納部２０４及び秘密鍵格納部２０５の動作について具体的に説明する。
【０１３５】
公開情報格納部２０４は、全体の秘密情報ｓｉと全体の公開鍵Ｐｉとを乗算して、全体の公開情報Ｑｉ＝ｓｉＰｉを求めるとともに、ルートノードの秘密情報ｓ０と全体の公開鍵Ｐｉとを乗算して、ルートノードの公開情報Ｑ０＝ｓ０Ｐｉを求める。また、公開情報格納部２０４は、ルートノードの子ノードの秘密情報ｓ１（あるいはｓ２）と全体の公開鍵Ｐｉとを乗算して、ルートノードの子ノードの公開情報Ｑ１＝ｓ１Ｐｉ（あるいはＱ２）を求める。同様に、公開情報格納部２０４は、ルートノードの孫ノードの秘密情報ｓ３（あるいはｓ４〜ｓ６）と全体の公開鍵Ｐｉとを乗算して、ルートノードの孫ノードの公開情報Ｑ３＝ｓ３Ｐｉ（あるいはＱ４〜Ｑ６）を求める。公開情報格納部２０４は、求めた公開情報Ｑｉ，Ｑ０〜Ｑ６を記憶装置に格納する。
【０１３６】
秘密鍵格納部２０５は、全体の秘密情報ｓｉとルートノードの公開鍵Ｐ０とを乗算して、ルートノードの秘密鍵ｔ０＝ｓｉＰ０を求める。次に、秘密鍵格納部２０５は、ルートノードの秘密情報ｓ０とルートノードの子ノードの公開鍵Ｐ１（あるいはＰ２）とを乗算し、さらに、当該乗算結果とルートノードの秘密鍵ｔ０とを加算して、ルートノードの子ノードの秘密鍵ｔ１＝ｔ０＋ｓ０Ｐ１＝ｓｉＰ０＋ｓ０Ｐ１（あるいはｔ２）を求める。同様に、秘密鍵格納部２０５は、ルートノードの子ノードの秘密情報ｓ１（あるいはｓ２）とその子ノード（ルートノードの孫ノード）の公開鍵Ｐ３（あるいはＰ４〜Ｐ６）とを乗算し、さらに、当該乗算結果とルートノードの子ノードの秘密鍵ｔ１（あるいはｔ２）とを加算して、その子ノード（ルートノードの孫ノード）の秘密鍵ｔ３＝ｔ１＋ｓ１Ｐ３＝ｓｉＰ０＋ｓ０Ｐ１＋ｓ１Ｐ３（あるいはｔ４〜ｔ６）を求める。最後に、秘密鍵格納部２０５は、末端ノードの親ノード（ルートノードの孫ノード）の秘密情報ｓ３（あるいはｓ４〜ｓ６）とその末端ノードの公開鍵Ｐ７（あるいはＰ８〜Ｐ１４）とを乗算し、さらに、当該乗算結果と末端ノードの親ノードの秘密鍵ｔ３（あるいはｔ４〜ｔ６）とを加算して、その末端ノードの秘密鍵ｔ７＝ｔ３＋ｓ３Ｐ７＝ｓｉＰ０＋ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ７（あるいはｔ８〜ｔ１４）を求める。秘密鍵格納部２０５は、求めた秘密鍵ｔ０〜ｔ１４を記憶装置に格納する。
【０１３７】
ここで、図１２の例において、Ａ６が失効した場合の鍵管理装置２００の動作について説明する。
【０１３８】
図９のステップＳＴ２０４で、鍵更新情報作成部２０８は、グループ情報格納部２０２により格納された失効情報を参照して、図１３に示すように、失効したＡ６が属するグループに対応するノードを全て特定する。ここでは、Ａ５，Ａ６からなるグループに対応するノード、Ａ５〜Ａ８からなるグループに対応するノード、Ａ１〜Ａ８からなるグループに対応するルートノードが特定されることになる。鍵更新情報作成部２０８は、グループ情報格納部３０４により格納された公開鍵のうち、特定したノードの各々に対応する公開鍵Ｐ０，Ｐ２，Ｐ５を公開鍵Ｐ０’，Ｐ２’，Ｐ５’に更新する。ステップＳＴ２０５で、鍵更新情報作成部２０８は、秘密鍵格納部２０５に対し、秘密情報格納部２０３により格納された秘密情報と端末情報格納部２０１及びグループ情報格納部２０２により格納された公開鍵（更新前の公開鍵と更新後の公開鍵とを用いて差分更新を行ってもよい）を入力として秘密鍵ｔ０〜ｔ１４を秘密鍵ｔ０’〜ｔ１４’に更新させる。このとき、秘密鍵格納部２０５は、更新後の秘密鍵ｔ０’〜ｔ１４’とともに更新前の秘密鍵ｔ０〜ｔ１４を一時的に記憶装置に格納しておく。
【０１３９】
ステップＳＴ２０６で、鍵更新情報作成部２０８は、端末情報格納部３０３により格納された端末情報とグループ情報格納部３０４により格納されたグループ情報とに基づき、図１３に示すように、木構造のうち、失効したＡ６とＡ６が属するグループに対応するノードを除いて残っている部分木Ｂ１〜Ｂ３を特定する。そして、鍵更新情報作成部２０８は、部分木Ｂ１については、部分木Ｂ１に含まれる末端ノードに対応するＡ１〜Ａ４を特定し、Ａ１〜Ａ４のいずれか１つ（例えば、Ａ１）の更新前の秘密鍵ｔ７＝ｓｉＰ０＋ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ７と更新後の秘密鍵ｔ７’＝ｓｉＰ０’＋ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ７を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵ｔ７と更新後の秘密鍵ｔ７’との差分ｄ１＝ｔ７−ｔ７’＝ｓｉＰ０’−ｓｉＰ０を計算し、鍵更新情報として出力する（Ａ２〜Ａ４の更新前の秘密鍵ｔ８〜ｔ１０と更新後の秘密鍵ｔ８’〜ｔ１０’との差分もｄ１＝ｓｉＰ０’−ｓｉＰ０になる）。同様に、鍵更新情報作成部２０８は、部分木Ｂ２については、部分木Ｂ２に含まれる末端ノードに対応するＡ５を特定し、Ａ５の更新前の秘密鍵ｔ１１＝ｓｉＰ０＋ｓ０Ｐ２＋ｓ２Ｐ５＋ｓ５Ｐ１１と更新後の秘密鍵ｔ１１’＝ｓｉＰ０’＋ｓ０Ｐ２’＋ｓ２Ｐ５’＋ｓ５Ｐ１１を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵ｔ１１と更新後の秘密鍵ｔ１１’との差分ｄ２＝ｔ１１−ｔ１１’＝（ｓｉＰ０’＋ｓ０Ｐ２’＋ｓ２Ｐ５’）−（ｓｉＰ０＋ｓ０Ｐ２＋ｓ２Ｐ５）を計算し、鍵更新情報として出力する。同様に、鍵更新情報作成部２０８は、部分木Ｂ３については、部分木Ｂ３に含まれる末端ノードに対応するＡ７，Ａ８を特定し、Ａ７，Ａ８のいずれか１つ（例えば、Ａ７）の更新前の秘密鍵ｔ１３＝ｓｉＰ０＋ｓ０Ｐ２＋ｓ２Ｐ６＋ｓ６Ｐ１３と更新後の秘密鍵ｔ１３’＝ｓｉＰ０’＋ｓ０Ｐ２’＋ｓ２Ｐ６＋ｓ６Ｐ１３を記憶装置から読み出す。鍵更新情報作成部２０８は、読み出した更新前の秘密鍵ｔ１３と更新後の秘密鍵ｔ１３’との差分ｄ３＝ｔ１３−ｔ１３’＝（ｓｉＰ０’＋ｓ０Ｐ２’）−（ｓｉＰ０＋ｓ０Ｐ２）を計算し、鍵更新情報として出力する（Ａ８の更新前の秘密鍵ｔ１４と更新後の秘密鍵ｔ１４’との差分もｄ３＝（ｓｉＰ０’＋ｓ０Ｐ２’）−（ｓｉＰ０＋ｓ０Ｐ２）になる）。
【０１４０】
ステップＳＴ２０７で、暗号化計算部２０６は、鍵更新情報作成部２０８から出力された鍵更新情報ｄ１〜ｄ３を暗号化し、それぞれに対応する３つの暗号文を作成する。ステップＳＴ２０８で、鍵更新パケット作成部２０９は、暗号化計算部２０６により作成された３つの暗号文を、任意の方法を用いて１つのブロードキャストメッセージにまとめて無線ネットワーク１０１に送信する。
【０１４１】
本実施の形態では、端末装置３００が失効した場合、鍵管理装置２００は、実施の形態３と同様に、失効した端末装置３００が属するグループに対応するノードの公開鍵（グループのＩＤ）を更新し、それによって全ての端末装置３００の秘密鍵を更新するが、実施の形態２と同様に、失効した端末装置３００が属するグループに対応するノードの秘密情報を更新し、それによって全ての端末装置３００の秘密鍵を更新してもよい。
【０１４２】
本実施の形態によれば、実施の形態３と同様に、木構造に従ってグループ分けされた複数の端末装置３００（例えばＡ１〜Ａ８）に対し、同じ木構造で管理される暗号鍵を配布する方式において、いずれかの端末装置３００（例えばＡ６）の暗号鍵が何らかの理由で失効した場合でも、その端末装置３００と同じグループに属していた各端末装置３００（例えばＡ５，Ａ７，Ａ８）と安全に効率よく通信することができる。
【０１４３】
実施の形態５．
本実施の形態について、主に実施の形態４との差異を説明する。
【０１４４】
本実施の形態では、端末装置３００のグループのＩＤ（公開鍵）は、バージョン情報（例えば、１以上の整数）であるとする。ある端末装置３００が失効した場合、その端末装置３００が属するグループのＩＤは更新される（例えば、現在のバージョンが１であったとき、更新されたバージョンを２とする）。なお、実施の形態４と同様にグループのＩＤが変えられるものであれば、グループのＩＤはバージョン情報でなくともよい。
【０１４５】
実施の形態４では、木構造の末端ノード以外のノードには、端末装置３００のグループを対応付けているが、本実施の形態では、木構造の末端ノード以外のノードにも、個別の端末装置３００を対応付ける。全てのノードに端末装置３００を対応付けても構わないが、ここでは、ルートノードには、鍵管理装置２００を対応付けるものとする。各端末装置３００及び鍵管理装置２００には、それぞれに対応するノードの暗号鍵が割り当てられ、各端末装置３００及び鍵管理装置２００は、割り当てられた暗号鍵を保持する。言い換えると、本実施の形態では、木構造の各ノードに、各端末装置３００及び鍵管理装置２００の個別の暗号鍵が対応付けられる。本実施の形態では、木構造の各ノードに、さらに、グループ鍵も対応付けられる。各端末装置３００及び鍵管理装置２００は、自己が属するグループのグループ鍵を全て保持する。
【０１４６】
図１４は、本実施の形態に係る暗号システム１００の構成を示すブロック図である。
【０１４７】
図１４において、暗号システム１００は、鍵管理装置２００、Ａ１〜Ａ１４の１４台の端末装置３００（便宜上、Ａ１のみを図示している）を備える。
【０１４８】
鍵管理装置２００は、実施の形態４と同様の構成要素のほか、さらに、サブグループ判定部２１０を備える。
【０１４９】
サブグループ判定部２１０は、自身の対応するノード（即ち、ルートノード）の子ノードに対応するグループのＩＤと特定の端末装置３００（例えば、失効した端末装置３００）のＩＤとを入力とし、当該グループに当該端末装置３００が属するか、即ち、入力されたグループのＩＤに対応するノードが、入力された端末装置３００のＩＤに対応するノードを子孫にもつかどうかを処理装置により判定する。
【０１５０】
端末装置３００（便宜上、Ａ１のみの構成を図示している）は、実施の形態４と同様の構成要素のほか、さらに、サブグループ判定部３１２、パケット処理判定部３１３、失効端末親子判定部３１４を備える。
【０１５１】
サブグループ判定部３１２は、自身の対応するノードの子ノードに対応するグループのＩＤと特定の端末装置３００（例えば、失効した端末装置３００）のＩＤとを入力とし、当該グループに当該端末装置３００が属するか、即ち、入力されたグループのＩＤに対応するノードが、入力された端末装置３００のＩＤに対応するノードを子孫にもつかどうかを処理装置により判定する。
【０１５２】
パケット処理判定部３１３は、特定の端末装置３００のＩＤが含まれるパケットを受信し、受信したパケットの送信者が自身の対応するノードの親ノードに対応し、かつ、パケットに付与された端末装置３００のＩＤが自身の対応するノードの子孫ノードに対応するかどうかを処理装置により判定する。
【０１５３】
失効端末親子判定部３１４は、特定の端末装置３００のＩＤを入力とし、その端末装置３００が自身の対応するノードの子ノードに対応するかどうかを処理装置により判定する。
【０１５４】
図１２の例を本実施の形態に合わせて変更したものを図１５に示す。この例では、各端末装置３００は、自己が対応するノードの子ノードの公開情報、個別の秘密鍵、グループ鍵を生成するものとする。よって、鍵管理装置２００は、全体の公開情報のほかは、ルートノードの公開情報、秘密鍵、グループ鍵、ルートノードの子ノードの公開情報、個別の秘密鍵、グループ鍵のみを生成する。このとき、全体の公開鍵、全体の秘密情報、各ノードの秘密情報、各ノードの公開情報は、個別の暗号鍵及びグループ鍵の両方について利用される。なお、実施の形態４等と同様に、鍵管理装置２００が全ノードの公開情報、秘密鍵、グループ鍵を生成してもよい。以下、図１５の例を用いて、鍵管理装置２００の公開情報格納部２０４及び秘密鍵格納部２０５の動作について具体的に説明する。また、端末装置３００の秘密鍵格納部３０１及び公開情報格納部３０２の動作について具体的に説明する。
【０１５５】
鍵管理装置２００の公開情報格納部２０４は、実施の形態４と同様に、公開情報Ｑｉ，Ｑ０を求めて記憶装置に格納する。
【０１５６】
鍵管理装置２００の秘密鍵格納部２０５は、実施の形態４と同様に、鍵管理装置２００の個別の秘密鍵ｔ０を求めて記憶装置に格納する。また、秘密鍵格納部２０５は、ルートノードの秘密情報ｓ０とルートノードに対応するグループのバージョン情報である公開鍵Ｐｇ０とを乗算し、さらに、当該乗算結果とルートノードの秘密鍵ｔ０とを加算して、ルートノードに対応するグループの秘密鍵ｔｇ０＝ｔ０＋ｓ０Ｐｇ０＝ｓｉＰ０＋ｓ０Ｐｇ０を求めて記憶装置に格納する。
【０１５７】
例えば、Ａ１の公開情報格納部３０２は、鍵管理装置２００の公開情報格納部２０４と同様に、自己に対応するノードの秘密情報ｓ１と全体の公開鍵Ｐｉとを乗算して、自己に対応するノードの公開情報Ｑ１＝ｓ１Ｐｉを求めて記憶装置に格納する。同様に、Ａ１の子端末であるＡ３の公開情報格納部３０２は、自己に対応するノードの秘密情報ｓ３と全体の公開鍵Ｐｉとを乗算して、自己に対応するノードの公開情報Ｑ３＝ｓ３Ｐｉを求めて記憶装置に格納する。
【０１５８】
また、例えば、Ａ１の秘密鍵格納部３０１は、鍵管理装置２００の秘密鍵格納部２０５と同様に、自己に対応するノードの親ノードであるルートノードの秘密情報ｓ０と自己に対応するノードの公開鍵Ｐ１とを乗算し、さらに、当該乗算結果とルートノードの秘密鍵ｔ０とを加算して、自己に対応するノードの秘密鍵ｔ１＝ｔ０＋ｓ０Ｐ１＝ｓｉＰ０＋ｓ０Ｐ１を求めて記憶装置に格納する。また、Ａ１の秘密鍵格納部３０１は、自己に対応するノードの秘密情報ｓ１と当該ノードに対応するグループのバージョン情報である公開鍵Ｐｇ１とを乗算し、さらに、当該乗算結果と当該ノードの秘密鍵ｔ１とを加算して、当該ノードに対応するグループの秘密鍵ｔｇ１＝ｔ１＋ｓ１Ｐｇ１＝ｓｉＰ０＋ｓ０Ｐ１＋ｓ１Ｐｇ１を求めて記憶装置に格納する。同様に、Ａ１の子端末であるＡ３の秘密鍵格納部３０１は、自己に対応するノードの親ノードの秘密情報ｓ１と自己に対応するノードの公開鍵Ｐ３とを乗算し、さらに、当該乗算結果と親ノードの秘密鍵ｔ１とを加算して、自己に対応するノードの秘密鍵ｔ３＝ｔ１＋ｓ１Ｐ３＝ｓｉＰ０＋ｓ０Ｐ１＋ｓ１Ｐ３を求めて記憶装置に格納する。また、Ａ３の秘密鍵格納部３０１は、自己に対応するノードの秘密情報ｓ３と当該ノードに対応するグループのバージョン情報である公開鍵Ｐｇ３とを乗算し、さらに、当該乗算結果と当該ノードの秘密鍵ｔ３とを加算して、当該ノードに対応するグループの秘密鍵ｔｇ３＝ｔ３＋ｓ３Ｐｇ３＝ｓｉＰ０＋ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐｇ３を求めて記憶装置に格納する。同様に、Ａ３の子端末であるＡ７の秘密鍵格納部３０１は、自己に対応するノードの親ノードの秘密情報ｓ３と自己に対応するノードの公開鍵Ｐ７とを乗算し、さらに、当該乗算結果と親ノードの秘密鍵ｔ３とを加算して、自己に対応するノードの秘密鍵ｔ７＝ｔ３＋ｓ３Ｐ７＝ｓｉＰ０＋ｓ０Ｐ１＋ｓ１Ｐ３＋ｓ３Ｐ７を求めて記憶装置に格納する。
【０１５９】
この例では、グループ鍵である秘密鍵ｔｇ０は、安全な方法により予め鍵管理装置２００からＡ１〜Ａ１４に配布されている。同様に、秘密鍵ｔｇ１は、予めＡ１からＡ３，Ａ４，Ａ７，Ａ〜１０に、秘密鍵ｔｇ２は、予めＡ２からＡ５，Ａ６，Ａ１１〜Ａ１４に配布されている。同様に、秘密鍵ｔｇ３は、予めＡ７，Ａ８に、秘密鍵ｔｇ４は、予めＡ９，Ａ１０に、秘密鍵ｔｇ５は、予めＡ１１，Ａ１２に、秘密鍵ｔｇ６は、予めＡ１３，Ａ１４に配布されている。
【０１６０】
次に、暗号システム１００の動作について説明する。
【０１６１】
無線ネットワーク１０１内において他の端末装置３００が失効したときの端末装置３００の動作については、図４に示した実施の形態１のものと同様である。
【０１６２】
図１６は、失効した端末装置３００に関する通知を受け取った鍵管理装置２００の動作を示すフローチャートである。
【０１６３】
図１６において、まず、ステップＳＴ３０１で、グループ情報格納部２０２は、鍵管理装置２００が管理しているグループ、即ち、ルートノードに対応するグループのバージョン情報を更新する。例えば、現在のバージョンが１であったとき、更新されたバージョンを２とする。
【０１６４】
次に、ステップＳＴ３０２で、鍵更新情報作成部２０８は、秘密鍵格納部２０５に対し、秘密情報格納部２０３により格納された秘密情報と端末情報格納部２０１により格納されたＩＤ（公開鍵）とグループ情報格納部２０２により格納された更新後のバージョン情報を入力としてルートノードのグループ鍵（秘密鍵）を更新させる。そして、鍵更新情報作成部２０８は、秘密鍵格納部２０５により格納された更新後のグループ鍵とグループ情報格納部２０２により格納された更新後のバージョン情報とを含む鍵更新情報（少なくともグループ鍵を更新するための情報であればよい）を生成する。
【０１６５】
次に、ステップＳＴ３０３で、サブグループ判定部３１２は、失効した端末装置３００のＩＤ（複数あってもよい）の入力を受け付ける。そして、サブグループ判定部３１２は、入力されたＩＤを基に、自己の対応するノード（即ち、ルートノード）の子ノード全てについて、失効した端末装置３００がそれぞれの子ノードに対応するグループに属するかどうかを判定する。以下では、自己の対応するノードの子ノードに対応するグループを自己のサブグループといい、自己の対応するノードの子ノードに対応する端末装置３００をサブグループ管理者という。
【０１６６】
ステップＳＴ３０４で、暗号化計算部２０６は、失効した端末装置３００を含むサブグループのサブグループ管理者に対しては、ステップＳＴ３０２で生成された鍵更新情報をサブグループ管理者のＩＤ（公開鍵）で暗号化して暗号文を作成する。一方、ステップ暗号化計算部２０６は、失効した端末装置３００を含まないサブグループに対しては、ステップＳＴ３０２で生成された鍵更新情報をサブグループのＩＤ（公開鍵）で暗号化して暗号文を作成する。このとき、失効した端末装置３００を含まないサブグループの数だけ暗号文が作成される。
【０１６７】
次に、ステップＳＴ３０５で、鍵更新パケット作成部２０９は、暗号化計算部２０６により作成された暗号文に、失効した端末装置３００のＩＤを付加してパケットを生成する。このとき、鍵更新パケット作成部２０９は、暗号文のうち、失効した端末装置３００を含むサブグループのサブグループ管理者のＩＤで暗号化された暗号文を含むパケットの送り先は、当該サブグループのサブグループ管理者である端末装置３００とする。一方、鍵更新パケット作成部２０９は、暗号文のうち、失効した端末装置３００を含まないサブグループのＩＤで暗号化された暗号文を含むパケットの送り先は、当該サブグループに属する端末装置３００全てとする。鍵更新パケット作成部２０９は、生成したパケットを、無線ネットワーク１０１を介して送信する。
【０１６８】
ここで、図１５の例において、Ａ１２が失効した場合の鍵管理装置２００の動作について説明する。
【０１６９】
ステップＳＴ３０１で、グループ情報格納部２０２は、図１７に示すように、ルートノードのグループのバージョン情報Ｐｇ０をＰｇ０’に更新する。ステップＳＴ３０２で、鍵更新情報作成部２０８は、秘密鍵格納部２０５に対し、ルートノードのグループ鍵ｔｇ０をｔｇ０’＝ｓｉＰ０＋ｓ０Ｐｇ０’に更新させる。そして、鍵更新情報作成部２０８は、更新後のグループ鍵ｔｇ０’と更新後のバージョン情報Ｐｇ０’とを含む鍵更新情報を生成する。
【０１７０】
ステップＳＴ３０３で、サブグループ判定部３１２は、Ａ１をサブグループ管理者とするサブグループとＡ２をサブグループ管理者とするサブグループとについて、失効したＡ１２が属するサブグループかどうかを判定する。ステップＳＴ３０４で、暗号化計算部２０６は、失効したＡ１２を含むサブグループのサブグループ管理者であるＡ２に対しては、ステップＳＴ３０２で生成された鍵更新情報をＡ２のＩＤである公開鍵Ｐ２（及び全体の公開情報Ｑｉ、全体の公開鍵Ｐｉ、ルートノードの公開鍵Ｐ０）で暗号化して暗号文を作成する。一方、暗号化計算部２０６は、失効したＡ１２を含まないサブグループ（Ａ１，Ａ３，Ａ４，Ａ７〜Ａ１０からなるサブグループ）に対しては、ステップＳＴ３０２で生成された鍵更新情報をサブグループのＩＤである公開鍵Ｐｇ１（及び全体の公開情報Ｑｉ、ルートノードの公開鍵Ｐ０）で暗号化して暗号文を作成する。
【０１７１】
ステップＳＴ３０５で、鍵更新パケット作成部２０９は、公開鍵Ｐ２で暗号化された暗号文を含み、失効したＡ１２のＩＤである公開鍵Ｐ１２を付加したパケットを生成し、その送り先をＡ２に設定してパケットをユニキャストで送信する。また、鍵更新パケット作成部２０９は、公開鍵Ｐｇ１で暗号化された暗号文を含み、失効したＡ１２のＩＤである公開鍵Ｐ１２を付加したパケットを生成し、その送り先をＡ１，Ａ３，Ａ４，Ａ７〜Ａ１０からなるサブグループに設定してパケットをマルチキャストで送信する。
【０１７２】
図１８は、自己を宛先とするパケットを受信した端末装置３００の動作を示すフローチャートである。
【０１７３】
図１８において、まず、ステップＳＴ３０６で、パケット処理判定部３１３は、パケットを受信する。復号計算部３０６は、パケット処理判定部３１３により受信されたパケットから、自己のＩＤ（公開鍵）で暗号化された暗号文を取り出して復号し、鍵更新情報を得る。秘密鍵更新部３１１は、復号計算部３０６により得られた鍵更新情報に基づいて、秘密鍵格納部３０１により格納されているグループ鍵を更新する。具体的には、秘密鍵更新部３１１は、秘密鍵格納部３０１により格納されているグループ鍵（自己の対応するノードの親ノードに対応するグループの秘密鍵）を、復号計算部３０６により得られた鍵更新情報に含まれるグループ鍵で、上書きする。グループ情報格納部３０４は、現在格納されているグループのバージョン情報（自己の対応するノードの親ノードに対応するグループの公開鍵）を、復号計算部３０６により得られた鍵更新情報に含まれるバージョン情報で更新する。
【０１７４】
次に、ステップＳＴ３０７で、パケット処理判定部３１３は、受信したパケットの送信者が自身の対応するノードの親ノードに対応し、かつ、パケットに付与された端末装置３００（失効した端末装置３００）のＩＤが自身の管理するグループ（自己の対応するノードに対応するグループ）に属する端末装置３００のＩＤかどうかを判定する。
【０１７５】
パケット送信者が親ノードに対応するものでない場合、あるいは、失効した端末装置３００が自身の管理するグループに属していない場合には、何もせず終了する。自身が管理者でない、即ち、自身の対応するノードが末端ノードである（子ノードがない）場合も、上記条件には当てはまらないので何もせず終了することになる。
【０１７６】
一方、パケット送信者が親ノードに対応し、かつ、失効した端末装置３００が自身の管理するグループに属する場合には、ステップＳＴ３０８で、グループ情報格納部３０４は、自身が管理するグループのバージョン情報を更新する。そして、ステップＳＴ３０９で、秘密鍵格納部３０１は、ステップＳＴ３０８で更新されたバージョン情報を用いて、グループの秘密鍵を更新する。
【０１７７】
ステップＳＴ３１０で、失効端末親子判定部３１４は、失効した端末装置３００のＩＤを入力とし、その端末装置３００が自身の対応するノードの子ノードに対応するかどうか（失効した端末装置３００が直接の子であるかどうか）を判定する。
【０１７８】
失効した端末装置３００が直接の子であった場合、ステップＳＴ３１１で、暗号化計算部３０５は、パケット送信者から送られてきた鍵更新情報に含まれる更新後のグループ鍵及びバージョン情報、秘密鍵格納部３０１により更新されたグループの秘密鍵、グループ情報格納部３０４により更新されたグループのバージョン情報をまとめて鍵更新情報とし、この鍵更新情報を、失効した端末装置３００以外の各端末装置３００（自己が管理するグループに属する各端末装置３００）のＩＤで暗号化して各端末装置３００向けの暗号文を作成する。
【０１７９】
一方、失効した端末装置３００が直接の子でない場合、ステップＳＴ３１２で、サブグループ判定部３１２は、失効した端末装置３００のＩＤ（複数あってもよい）の入力を受け付け、入力されたＩＤを基に、自己の対応するノードの子ノード全てについて、失効した端末装置３００がそれぞれの子ノードに対応するグループ、即ち、サブグループに属するかどうかを判定する。
【０１８０】
ステップＳＴ３１３で、暗号化計算部３０５は、失効した端末装置３００を含むサブグループのサブグループ管理者に対しては、パケット送信者から送られてきた鍵更新情報に含まれる更新後のグループ鍵及びバージョン情報、秘密鍵格納部３０１により更新されたグループの秘密鍵、グループ情報格納部３０４により更新されたグループのバージョン情報をまとめて鍵更新情報とし、この鍵更新情報を、失効した端末装置３００を含むサブグループのサブグループ管理者のＩＤで暗号化して当該サブグループ管理者向けの暗号文を作成する。一方、暗号化計算部３０５は、失効した端末装置３００を含まないサブグループに対しては、同様の鍵更新情報を、当該サブグループのＩＤ（公開鍵）で暗号化して暗号文を作成する。このとき、失効した端末装置３００を含まないサブグループの数だけ暗号文が作成される。
【０１８１】
次に、ステップＳＴ３１４で、暗号化計算部３０５は、ステップＳＴ３１３で作成した暗号文に、失効した端末装置３００のＩＤを付加してパケットを生成する。このとき、暗号化計算部３０５は、暗号文のうち、失効した端末装置３００を含むサブグループのサブグループ管理者のＩＤで暗号化された暗号文を含むパケットの送り先は、当該サブグループのサブグループ管理者である端末装置３００とする。一方、暗号化計算部３０５は、暗号文のうち、失効した端末装置３００を含まないサブグループのＩＤで暗号化された暗号文を含むパケットの送り先は、当該サブグループに属する端末装置３００全てとする。暗号化計算部３０５は、生成したパケットを、無線ネットワーク１０１を介して送信する。また、ステップＳＴ３１１で暗号文を作成した場合には、暗号化計算部３０５は、その暗号文に、失効した端末装置３００のＩＤを付加してパケットを生成し、生成したパケットを自己が管理するグループに属する各端末装置３００へ送信する。
【０１８２】
ここで、図１５の例において、Ａ１２が失効した場合のＡ２の動作について説明する。
【０１８３】
ステップＳＴ３０６で、Ａ２のパケット処理判定部３１３は、鍵管理装置２００からパケットを受信する。復号計算部３０６は、パケット処理判定部３１３により受信されたパケットから、自己のＩＤである公開鍵Ｐ２（及び全体の公開情報Ｑｉ、全体の公開鍵Ｐｉ、ルートノードの公開鍵Ｐ０）で暗号化された暗号文を取り出して復号し、鍵更新情報を得る。秘密鍵更新部３１１は、図１７に示すように、秘密鍵格納部３０１により格納されているグループ鍵ｔｇ０を、復号計算部３０６により得られた鍵更新情報に含まれるグループ鍵ｔｇ０’で、上書きする。グループ情報格納部３０４は、現在格納されているグループのバージョン情報Ｐｇ０を、復号計算部３０６により得られた鍵更新情報に含まれるバージョン情報Ｐｇ０’で更新する。
【０１８４】
次に、ステップＳＴ３０７で、パケット処理判定部３１３は、受信したパケットの送信者が自身の対応するノードの親ノードに対応する鍵管理装置２００であり、かつ、パケットに付与された公開鍵Ｐ１２から失効した端末装置３００が自身の管理するグループに属するＡ１２であると判定する。そのため、ステップＳＴ３０８で、グループ情報格納部３０４は、自身が管理するグループのバージョン情報Ｐｇ２をバージョン情報Ｐｇ２’に更新する。そして、ステップＳＴ３０９で、秘密鍵格納部３０１は、ステップＳＴ３０８で更新されたバージョン情報Ｐｇ２’を用いて、グループの秘密鍵ｔｇ２を秘密鍵ｔｇ２’＝ｓｉＰ０＋ｓ０Ｐ２＋ｓ２Ｐｇ２’に更新する。
【０１８５】
ステップＳＴ３１０で、失効端末親子判定部３１４は、失効したＡ１２が直接の子ではないと判定する。そのため、ステップＳＴ３１２で、サブグループ判定部３１２は、自己の対応するノードの子ノード全てについて、失効したＡ１２がそれぞれの子ノードに対応するサブグループに属するかどうかを判定する。
【０１８６】
ステップＳＴ３１３で、暗号化計算部３０５は、失効したＡ１２を含むサブグループのサブグループ管理者であるＡ５に対しては、パケット送信者である鍵管理装置２００から送られてきた鍵更新情報に含まれる更新後のグループ鍵ｔｇ０’及び更新後のバージョン情報Ｐｇ０’、秘密鍵格納部３０１により更新されたグループの秘密鍵ｔｇ２’、グループ情報格納部３０４により更新されたグループのバージョン情報Ｐｇ２’をまとめて鍵更新情報とし、この鍵更新情報を、Ａ５のＩＤである公開鍵Ｐ５（及び全体の公開情報Ｑｉ、全体の公開鍵Ｐｉ、Ａ５が対応するノードの祖先ノードの公開鍵Ｐ０，Ｐ２）で暗号化してＡ５向けの暗号文を作成する。一方、暗号化計算部３０５は、失効した端末装置３００を含まないサブグループ（Ａ６，Ａ１３，Ａ１４からなるサブグループ）に対しては、同様の鍵更新情報を、当該サブグループのＩＤである公開鍵Ｐｇ６（及び全体の公開情報Ｑｉ、全体の公開鍵Ｐｉ、Ａ６が対応するノードの祖先ノードの公開鍵Ｐ０，Ｐ２）で暗号化して暗号文を作成する。
【０１８７】
ステップＳＴ３１４で、暗号化計算部３０５は、公開鍵Ｐ５で暗号化された暗号文を含み、失効したＡ１２のＩＤである公開鍵Ｐ１２を付加したパケットを生成し、その送り先をＡ５に設定してパケットをユニキャストで送信する。また、暗号化計算部３０５は、公開鍵Ｐｇ６で暗号化された暗号文を含み、失効したＡ１２のＩＤである公開鍵Ｐ１２を付加したパケットを生成し、その送り先をＡ６，Ａ１３，Ａ１４からなるサブグループに設定してパケットをマルチキャストで送信する。
【０１８８】
以上のように、本実施の形態では、通信装置の一例である端末装置３００（又は鍵管理装置２００）において、情報格納部４０１は、木構造のノードに、他の端末装置３００に割り当てられている個別の暗号鍵（秘密鍵）及び自己が保持する個別の暗号鍵を対応付け、ノードと暗号鍵との対応関係を示す鍵情報（例えば、図１５に示したような情報）を記憶装置に格納する。また、情報格納部４０１は、記憶装置に格納された鍵情報で個別の暗号鍵が対応付けられたノードに、当該暗号鍵が割り当てられている他の端末装置３００及び当該暗号鍵を保持する自己を対応付け、ノードと他の端末装置３００及び自己との対応関係を示す端末情報（例えば、図１５に示したような情報）を記憶装置に格納する。
【０１８９】
特定グループ情報生成部４０２は、割り当てられている暗号鍵が失効した端末装置３００がある場合、当該端末装置３００を失効端末とし、情報格納部４０１により格納された端末情報に基づいて、上記失効端末が自己に対応するノードの子ノードに対応する子端末と子ノード以外の子孫ノードに対応する子孫端末と子孫ノードに対応しない端末装置３００とのいずれであるかを処理装置により判定する。特定グループ情報生成部４０２は、上記失効端末が子端末であると判定した場合、上記失効端末以外の子端末それぞれ（１台の場合はその子端末のみ）を１つの端末装置３００のグループとして示す特定グループ情報を処理装置により生成する。一方、特定グループ情報生成部４０２は、上記失効端末が子孫端末であると判定した場合、子端末のうち、上記失効端末に対応するノードの祖先ノードに対応する子端末を１つの端末装置３００のグループとして示すとともに他の子端末と当該他の子端末に対応するノードの子孫ノードに対応する端末装置３００とをまとめて１つの端末装置３００のグループとして示す特定グループ情報を処理装置により生成する。そして、特定グループ情報生成部４０２は、生成した特定グループ情報を記憶装置に格納する。
【０１９０】
グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、所定の情報をグループ別情報として処理装置により生成する。そして、グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、生成したグループ別情報を同じグループに属する端末装置３００へ送信し、当該端末装置３００に対して、送信したグループ別情報を利用させる。本実施の形態では、グループ別情報送信部４０３は、実施の形態２〜４と同様に、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、暗号鍵を更新するための鍵更新情報をグループ別情報として処理装置により生成する。そして、グループ別情報送信部４０３は、特定グループ情報生成部４０２により格納された特定グループ情報で示されたグループごとに、生成した鍵更新情報を同じグループに属する端末装置３００へ送信し、当該端末装置３００に対して、送信した鍵更新情報により当該端末装置３００に割り当てられている暗号鍵を更新させる。
【０１９１】
本実施の形態によれば、実施の形態２〜４と同様に、木構造に従ってグループ分けされた複数の端末装置３００（例えばＡ１〜Ａ８）に対し、同じ木構造で管理される暗号鍵を配布する方式において、いずれかの端末装置３００（例えばＡ６）の暗号鍵が何らかの理由で失効した場合でも、その端末装置３００と同じグループに属していた各端末装置３００（例えばＡ５，Ａ７，Ａ８）と安全に効率よく通信することができる。
【０１９２】
以上述べたように、本実施の形態では、暗号システム１００が、ある特定の端末装置３００に格納された秘密鍵を除き、全端末装置３００に格納された秘密鍵を効率よく更新することができる。
【０１９３】
本実施の形態によれば、階層の上位に位置する端末装置３００ほど鍵が少ないため、管理がしやすい。また、各端末装置３００に対して更新した秘密鍵を暗号化してユニキャストした場合に比べて、暗号文の種類が格段に減る。
【０１９４】
以上、本発明の実施の形態について説明したが、これらのうち、２つ以上の実施の形態を組み合わせて実施しても構わない。あるいは、これらのうち、１つの実施の形態を部分的に実施しても構わない。あるいは、これらのうち、２つ以上の実施の形態を部分的に組み合わせて実施しても構わない。
【符号の説明】
【０１９５】
１００  暗号システム、１０１  無線ネットワーク、２００  鍵管理装置、２０１  端末情報格納部、２０２  グループ情報格納部、２０３  秘密情報格納部、２０４  公開情報格納部、２０５  秘密鍵格納部、２０６  暗号化計算部、２０７  復号計算部、２０８  鍵更新情報作成部、２０９  鍵更新パケット作成部、２１０  サブグループ判定部、３００  端末装置、３０１  秘密鍵格納部、３０２  公開情報格納部、３０３  端末情報格納部、３０４  グループ情報格納部、３０５  暗号化計算部、３０６  復号計算部、３０７  グループ情報更新部、３０８  グループ鍵検索部、３０９  失効端末感知部、３１０  失効情報放送部、３１１  秘密鍵更新部、３１２  サブグループ判定部、３１３  パケット処理判定部、３１４  失効端末親子判定部、４０１  情報格納部、４０２  特定グループ情報生成部、４０３  グループ別情報送信部、９０１  ＬＣＤ、９０２  キーボード、９０３  マウス、９０４  ＦＤＤ、９０５  ＣＤＤ、９０６  プリンタ、９１１  ＣＰＵ、９１２  バス、９１３  ＲＯＭ、９１４  ＲＡＭ、９１５  通信ボード、９２０  ＨＤＤ、９２１  オペレーティングシステム、９２２  ウィンドウシステム、９２３  プログラム群、９２４  ファイル群。
【図１】
2010193226.tif 000006
【図２】
2010193226.tif 000007
【図３】
2010193226.tif 000008
【図４】
2010193226.tif 000009
【図５】
2010193226.tif 000010
【図６】
2010193226.tif 000011
【図７】
2010193226.tif 000012
【図８】
2010193226.tif 000013
【図９】
2010193226.tif 000014
【図１０】
2010193226.tif 000015
【図１１】
2010193226.tif 000016
【図１２】
2010193226.tif 000017
【図１３】
2010193226.tif 000018
【図１４】
2010193226.tif 000019
【図１５】
2010193226.tif 000020
【図１６】
2010193226.tif 000021
【図１７】
2010193226.tif 000022
【図１８】
2010193226.tif 000023