(57)【要約】安全性が高く高速なグループ鍵の更新方法を提供する方法である。情報の復号に用いる暗号化されたグループ鍵を復号するための復号処理の一部が、このグループ鍵の配布前に、加入者端末において実行されるステップと、グループ鍵とこのグループ鍵の復号処理の残りの一部を実行するための端末装置ごとに個別の復号情報とが、加入者端末に配布されるステップと、配布された復号情報と事前に実行された復号処理の一部の結果とを用いたグループ鍵の復号処理が、加入者端末において実行されるステップとを含む。
2003094422.tif 000002
【特許請求の範囲】
【請求項１】
暗号化された情報を復号するための鍵を配布する鍵配布サーバと、当該情報を使用する所定台数の加入者端末とを備えた暗号通信システムにおいて、
前記鍵配布サーバは、前記情報の復号に用いる暗号化された第１のグループ鍵と、当該第１のグループ鍵の復号処理を実行するための前記加入者端末ごとに個別の復号情報と、グループ鍵の更新後に更新された第２のグループ鍵の復号処理の一部を実行するための前記加入者端末ごとに個別の鍵更新情報とを前記加入者端末に配布し、
前記加入者端末は、予め取得した前記第１のグループ鍵を復号するための前記鍵更新情報に基づく処理結果と前記鍵配布サーバから配布された前記復号情報とを用いて前記鍵配布サーバから配布された前記第１のグループ鍵を復号することを特徴とする暗号通信システム。
【請求項２】
前記加入者端末は、前記鍵更新情報を用いた前記グループ鍵の復号処理の一部を、当該グループ鍵の配布前に実行することを特徴とする請求項１に記載の暗号通信システム。
【請求項３】
前記鍵配布サーバは、前記第１のグループ鍵を復号するための鍵更新情報を、当該第１のグループ鍵に更新される前の第３のグループ鍵と共に前記加入者端末に配布することを特徴とする請求項１に記載の暗号通信システム。
【請求項４】
前記鍵配布サーバは、前記グループ鍵を更新した場合に、前記加入者端末のうち排除対象端末を設定し、当該排除対象端末以外の加入者端末が更新された当該グループ鍵を復号可能な前記復号情報を、更新された当該グループ鍵と共に前記加入者端末に配布することを特徴とする請求項１に記載の暗号通信システム。
【請求項５】
暗号化された情報を復号するための鍵を配布する鍵配布サーバにおいて、
前記情報の復号に用いる第１のグループ鍵を生成し暗号化する手段と、
前記第１のグループ鍵の復号処理を実行するための加入者端末ごとに個別の復号情報を生成する手段と、
グループ鍵の更新後に更新された第２のグループ鍵の復号処理の一部を実行するための前記加入者端末ごとに個別の鍵更新情報を生成する手段と、
前記第１のグループ鍵と前記復号情報と前記鍵更新情報とを前記加入者端末に配布する手段と
を備えることを特徴とする鍵配布サーバ。
【請求項６】
前記復号情報を生成する手段は、前記加入者端末のうち排除対象端末を設定し、当該排除対象端末以外の加入者端末が当該グループ鍵を復号可能な前記復号情報を生成することを特徴とする請求項５に記載の鍵配布サーバ。
【請求項７】
暗号化された情報を復号するための暗号化されたグループ鍵と当該グループ鍵を復号するための復号情報とを所定の鍵配布サーバから取得する手段と、
前記グループ鍵の復号処理の一部を当該グループ鍵の配布前に実行する手段と、
前記グループ鍵の復号処理の一部に基づく処理結果と前記鍵配布サーバから取得した前記復号情報とを用いて前記グループ鍵を復号する手段と
を備えることを特徴とする端末装置。
【請求項８】
コンピュータを制御して、暗号化された情報を復号するための鍵を配布するプログラムであって、
前記情報の復号に用いる第１のグループ鍵を生成し暗号化する機能と、
前記第１のグループ鍵の復号処理を実行するための加入者端末ごとに個別の復号情報を生成する機能と、
グループ鍵の更新後に更新された第２のグループ鍵の復号処理の一部を実行するための前記加入者端末ごとに個別の鍵更新情報を生成する機能と、
所定の通信手段を介して前記第１のグループ鍵と前記復号情報と前記鍵更新情報とを前記加入者端末に配布する機能と
を前記コンピュータに実現させることを特徴とするプログラム。
【請求項９】
前記復号情報を生成する機能は、前記加入者端末のうち排除対象端末を設定し、当該排除対象端末以外の加入者端末が当該グループ鍵を復号可能な前記復号情報を生成することを特徴とする請求項８に記載のプログラム。
【請求項１０】
コンピュータを制御して、所定の機能を実現するプログラムであって、
所定の通信手段を介して、暗号化された情報を復号するための暗号化されたグループ鍵と当該グループ鍵を復号するための復号情報とを所定の鍵配布サーバから取得する機能と、
前記グループ鍵の復号処理の一部を当該グループ鍵の配布前に実行する機能と、
前記グループ鍵の復号処理の一部に基づく処理結果と前記鍵配布サーバから取得した前記復号情報とを用いて前記グループ鍵を復号する機能と
を前記コンピュータに実現させることを特徴とするプログラム。
【請求項１１】
コンピュータを制御して暗号化された情報を復号するための鍵を配布するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
前記プログラムは、
前記情報の復号に用いる第１のグループ鍵を生成し暗号化する機能と、
前記第１のグループ鍵の復号処理を実行するための加入者端末ごとに個別の復号情報を生成する機能と、
グループ鍵の更新後に更新された第２のグループ鍵の復号処理の一部を実行するための前記加入者端末ごとに個別の鍵更新情報を生成する機能と、
所定の通信手段を介して前記第１のグループ鍵と前記復号情報と前記鍵更新情報とを前記加入者端末に配布する機能と
を前記コンピュータに実現させることを特徴とする記録媒体。
【請求項１２】
コンピュータを制御して所定の機能を実現するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
前記プログラムは、
所定の通信手段を介して、暗号化された情報を復号するための暗号化されたグループ鍵と当該グループ鍵を復号するための復号情報とを所定の鍵配布サーバから取得する機能と、
前記グループ鍵の復号処理の一部を当該グループ鍵の配布前に実行する機能と、
前記グループ鍵の復号処理の一部に基づく処理結果と前記鍵配布サーバから取得した前記復号情報とを用いて前記グループ鍵を復号する機能と
を前記コンピュータに実現させることを特徴とする記録媒体。
【請求項１３】
暗号化された情報を復号するための鍵を、当該情報を使用する所定台数の端末で共有する鍵共有方法において、
前記情報の復号に用いる暗号化されたグループ鍵を復号するための復号処理の一部が、当該グループ鍵の配布前に、前記端末において実行されるステップと、
前記グループ鍵と、当該グループ鍵の復号処理の残りの一部を実行するための前記端末ごとに個別の復号情報とが、当該端末に配布されるステップと、
配布された前記復号情報と事前に実行された前記復号処理の一部の結果とを用いた前記グループ鍵の復号処理が、前記端末において実行されるステップと
を含むことを特徴とする鍵共有方法。
【請求項１４】
前記グループ鍵の配布前に前記復号処理の一部を実行するための情報が、更新前の前記グループ鍵と共に前記端末に配布されることを特徴とする請求項１３に記載の鍵共有方法。
【発明の詳細な説明】
技術分野
本発明は、暗号化された情報を復号するための鍵を加入者端末に配布する技術に関し、特に鍵の更新を安全かつ高速に行う技術に関する。
背景技術
予め決められたグループに対して情報を提供するようなシステムを構築する際に、グループ加入者だけに鍵（グループ鍵）を配布して、その鍵を用いた暗号通信を行う場面が多く登場する。例えば、携帯電話に対するコンテンツ配信、ＤＶＤの復号再生器、ＣＤＲＯＭによるソフトウェア配信、警察無線、Ｐ２Ｐサービスにおけるグループ内通信など、広い応用分野がある。
このようなシステムにおいて、一部の端末装置（復号器）が盗難等により紛失された場合、グループ加入者以外にグループ鍵が漏洩してしまうおそれがある。このため、古いグループ鍵を更新して、一刻も早く新しいグループ鍵を共有しなければならない。
この鍵更新技術は、一度作られたインフラを長期間利用するようなシステムにおいて、極めて重要な意味を持つ。
複数の加入者端末から構成されるこの種のシステム（以下、放送型暗号通信システム）において、任意に決定した単数または複数の加入者端末を除く全加入者端末に対してメッセージを配布することを考える。ここで、ある加入者端末をグループから除くことを「排除する」、その加入者端末を「排除対象端末」と呼ぶ。一般に、排除対象端末を排除するには、排除対象端末以外の個々の加入者端末に新たなグループ鍵を配送する必要がある。そのため、グループの規模の拡大に伴い、通信量や全加入者端末間で新しいグループ鍵の共有が完了するまでの遅延が増加する。
従来、上述したグループ鍵の更新の際における遅延を減少させるため、種々の方法が検討されている。この種の従来技術としては、例えば特開２０００−１９６５８１号公報に開示された技術がある（従来技術１）。
同公報に開示された従来技術１は、排除対象端末が決定後の通信量や遅延がグループ加入者総数ｎに比例しない手法が用いられている。この手法では、排除対象端末の最大数をｋであるとすると、各加入者端末がグループ鍵を計算するために、ｋに比例した冪剰余演算が必要になる。したがって、ｋがｎに比べて非常に小さいならば（ｋ＜＜ｎ）、一般的なグループ鍵配送法よりも大幅な効率化が実現できる。例えば、１００００台の加入者端末を持つシステム（ｎ＝１００００）で、排除対象端末を１００（ｋ＝１００）とすると、一般的なグループ鍵配送法では１００００回に比例した処理が必要だったのに対し、同公報に記載された従来技術１によれば１００回に比例した処理で実現することが可能である。
しかし、加入者端末数が数百万台に上るようなシステム（例えば携帯電話などのモバイル端末を対象としたシステム）等では、グループの大きさにあわせて、排除対象端末の最大数ｋも大きく取る必要がある（例えば数千〜数万）。このため、計算能力が低い端末などでは、復号処理に要するｋに比例した計算負荷が無視できない。したがって、ｋに比例しない、可能ならば定数回の復号処理によりグループ鍵配送が望まれる。
この問題を解決すべくなされた従来技術として、特開２００１−２０３６８２号公報がある（従来技術２）。
同公報に開示された従来技術２は、加入者端末数ｎ、及び排除対象端末の最大数ｋに依存せず、２回の冪剰余演算のみで復号処理を実現する。したがって、非常に多くの加入者端末を持つシステムにおいても、高速にグループ鍵の配送を完了することができる。
放送型暗号通信システムにおいて、プロトコル中のメンバーを次のように定義する。
鍵配布サーバ：セットアップ時に、システムパラメータを決定し、各加入者端末に対して個人鍵を配布する信頼機関。グループ鍵配送時には、どの加入者端末を排除するかを決定した上で、グループ鍵をブロードキャストにより配送する。鍵配布サーバをＳと表す。
加入者端末：鍵配布サーバからのブロードキャストを受信する端末。加入者端末ｉは、セットアップ時に鍵配布サーバから個人鍵ｓｉを受け取る。加入者端末の集合をΦ＝｛１，・・・，ｎ｝とする（ｎ＝｜Φ｜は加入者端末の総数）。
排除された加入者端末：鍵配布サーバにより排除された加入者端末。Ｉ回目のグループ鍵配送において排除されるｄ（＜ｋ）個の加入者端末の集合をΛＩ（⊂Φ）とする。一度排除された加入者端末は、それ以降のラウンドでグループ鍵を復号することはできないため、複数のラウンドで重複して排除されることはない。すなわち、ΛＩ∩ΛＩ’＝｛０｝（Ｉ≠Ｉ’）を満たす。また、排除された加入者端末の総数は、ラウンド全体を通じてｋを超えないものとする（即ち、｜ＵΛＩ｜≦ｋ）。
有効な加入者端末：排除されていない加入者端末。Ｉ回目のグループ鍵配送において有効な加入者端末の集合をΩＩ（＝Φ＼ＵＩｊ＝１Λｊ）とする。
以上のように定義された放送型暗号システムでは、Ｉラウンドにおいて、加入者端末全体Φのうち、有効な加入者端末ΩＩに対してＵＩが配送される。ＵＩを用いてメッセージを暗号化することで、グループΩＩ内における放送型暗号通信が可能になる。すなわち、
１．Ω０＝Φとする。鍵配布サーバは、各加入者ｉ∈Φに対して、グループ鍵Ｕ０及び個人鍵ｋｅｙｉをＰｏｉｎｔ−ｔｏ−Ｐｏｉｎｔの鍵配送プロトコルで配送する。
２．Ｉ≧１に対して、以下の処理を繰り返す（この処理の１回の繰り返しを、以後「Ｉラウンド」と呼ぶ）。
（ａ）鍵配布サーバがΛＩ⊂ΩＩ−１を決定する。
（ｂ）ｋ≧ΣＩｊ＝１｜Λｊ｜であれば、Φ：＝ΩＩ−１、Ｕ０：＝ＵＩ−１として１．へ戻る。
（ｃ）鍵配布サーバがΩＩに対してＵＩを計算するためのヘッダＨＩを配送する。
（ｄ）ｖ∈ΩＩは、ＨＩ及びｋｅｙｖを用いてＵＩを計算する。
（ｅ）鍵配布サーバ及びΩＩは、ＵＩを用いて放送型暗号通信を行う。
また、これ以降の説明では、次のパラメータを用いる。ｐ、ｑはｑ｜ｐ−１を満たす大きな素数であり、ｇは有限体Ｚｐ上の位数ｑの元とする。ｐ、ｑのサイズは、ｇを生成元として構成される群ＧＦ（ｑ）上での離散対数問題が計算量的に困難であるように設定するものとする。また、これ以降の説明において、特に記述のない場合、演算は、全てｍｏｄ  ｐ上で行われるものとする。なお、詳述はしないが、位数ｐの素体の上での構成法以外にも、離散対数問題が計算量的に困難となるような任意の群ＧＦ（ｑ）上で定義することができる。例えば、（１）位数ｐの素体上での乗法演算を、任意の有限体上の楕円曲線などの曲線上の加法演算に対応させることにより構成される群、（２）素数ｐに代えて素数ｐ’の冪乗数とし、素数ｐ’を法とする剰余演算に代えてＧＦ（ｐ’）の拡大体上での演算を行なうことにより構成される群、などがある。
Ｅ（ｋｅｙ，ｍｅｓｓａｇｅ）は、鍵（ｋｅｙ）を用いた対称鍵暗号によるメッセージ（ｍｅｓｓａｇｅ）の暗号化を示す。ｎは加入者端末の総数、ｋ（＜ｎ）は排除対象端末の最大数である。
以上の前提の下で、放送型暗号通信システムは、以下のような安全性・効率上の４つの要件を満たすことが要求される。
１．有効な加入者端末ｖ∈ΩＩは、単独でグループ鍵ＵＩを（多項式時間で）復号できる。
２．排除されたｋ個の加入者端末の持つ個人鍵を用いても、排除されたラウンド以降のグループ鍵を（確率的多項式時間で）復号することができない。
３．グループ鍵を配送するためのヘッダの長さや各加入者端末が持つ個人鍵のサイズが加入者端末の総数に依存しない。
４．グループ鍵を計算するためのヘッダを受け取ってから、グループ鍵の復号を完了するまで（復号処理）に要する冪剰余演算の回数がｎ、ｋに依存しない。
上記要件１は、加入者端末が単独で効率的に復号できるための要件である。放送型暗号通信において、加入者端末が復号時に他の端末と通信する必要がないときには、ネットワークに対して余計なトラフィックを発生させないために重要である。
要件２は、排除された加入者端末が結託してもセッション鍵を復号できないために必要である。
要件３は、非常に多くの加入者端末を持つ場合に処理が大きくなること防ぐために必要である。
要件４は、大規模なグループにおいてｋも大きく設定する必要がある場合に、ｎやｋに依存しない処理量でグループ鍵を復号するための要件である。
いわゆるＳｐａｒｅ  Ｓｈａｄｏｗ  Ａｔｔａｃｋ及びｒ  ｐｕｂｌｉｓｈ  ａｔｔａｃｋは、要件２に包含される。Ｓｅｃｒｅｔ  Ｐｕｂｌｉｓｈ  Ａｔｔａｃｋは閾値型のプロトコルでは本質的に対応することはできない。ただし、秘密を公開してしまう攻撃者をｗ人としたとき、不正者の結託がｋ−ｗ人以下であれば安全性が維持されることから、不正に加担する加入者端末が併せてｋ以下という条件でプロトコルの安全性を評価することで、要件２と同じ枠組みで安全性を議論することは可能である。
上述した従来技術１は、上記の要件１、２、３を満足する。配布される暗号文の長さが定数時間のＯ（ｋ）であり、かつ個人鍵のサイズがＯ（１）であり、極めて効率が良い。しかし、グループ鍵の復号処理に要する冪剰余演算の回数はＯ（ｋ）であり、またそれを事前計算に移行させることもできないため、要件４を満たさない。
従来技術２は、要件４の必要性に着目し、これを満足する手法を提示している。だが、以下に示す分析により、従来技術２は安全性上最も重要である要件２を満たしていない。すなわち、有限回グループ鍵を配送されると、排除されていない加入者端末はシステム全体の秘密情報を求めることが可能であり、それ以後の排除を無効にすることが可能である（例えばｋ≧５の場合、３回のグループ鍵配送で攻撃可能である）。
以下に、従来技術２が要件２を満足しないことを示す。まず、従来技術２による放送型暗号通信の手法を説明する。
１．セットアップ
鍵配布サーバは、排除対象端末の最大数ｋを設定し、次の数１式に示すＺｑ上のｋ次多項式
2003094422.tif 000003
をランダムに選択する。Ｆ（０）＝Ｓ、Ｇ（０）＝Ｔ（ｍｏｄ  ｑ）は、鍵配布サーバだけが知る秘密鍵である。鍵配布サーバは、ｋｅｙｉ＝（ｓｉ，ｆｉ）＝（Ｆ（ｉ），ｇＧ（ｉ）／Ｆ（ｉ））（ｉ＝１，・・・，ｎ）を各加入者端末ｉに秘密通信路を用いて配布する。また、鍵配布サーバは、Ｕ０∈ＧＦ（ｑ）をランダムに選択しブロードキャストする。
２．グループ鍵暗号化
Ｉ（≧１）ラウンドにおけるグループ鍵ＵＩを次のように配送する。ｒＩ∈Ｚｑをランダムに選び、ＸＩ＝ｇｒＩを求める。次にｄ個の排除される加入者端末の集合ΛＩを決定する。ｋ−ｄ個の整数をｎ＋ｋ（Ｒ−１）とｎ＋ｋＲの間から選び、それらからなる集合をΘＩとする。鍵配布サーバは、ＭＩ１，・・・，ＭＩｋを次の数２式にて求める。
2003094422.tif 000004
最後に、鍵配布サーバは、Ｅ（ＵＩ−１，ＢＩ）＝Ｅ（ＵＩ−１，ＸＩ｜｜［（ｊ，ＭＩｊ）｜ｊ∈ΛＩ∪ΘＩ］）を求め、ブロードキャストする。Ｉラウンドに共有されるグループ鍵はＵＩ＝ｇｒＩＳ＋Ｔである。
３．グループ鍵復号
Ｉラウンドの有効な加入者端末ｖ∈ΩＩは、ｖ∈ΩＩ−１であるから、ＵＩ−１をＩ−１ラウンドで得ている。加入者端末ｖは、受信した暗号文Ｅ（ＵＩ−１，ＢＩ）について、ＵＩ−１を用いてＢＩを復号する。次に、ＢＩの情報を用いて、グループ鍵ＵＩを次の数３式にて計算する。
2003094422.tif 000005
ここで、
2003094422.tif 000006
また、Ｌ（ｊ）はＬａｇｒａｎｇｅの多項式補間係数で、
2003094422.tif 000007
次に、上記従来技術２の手法が要件２を満たさないことを示す。具体的に、Ｒラウンドの有効な任意の加入者端末∀ｖ∈ΩＲが、鍵配布サーバだけが知るべき秘密情報Ｓ、Ｔを導出する方法を示す。ｖは１〜Ｒラウンドにおいて（ｊ，ＭＩｊ）（Ｉ＝１，・・・，Ｒ，ｊ＝１，・・・，ｋ）を得るが、これは次の数６式の関係を満たす。
2003094422.tif 000008
ここで、ｊは既知であるため、２ｋ＋２＋Ｒ個の変数ａ０，・・・，ａｋ、ｂ０，・・・，ｂｋ、ｒ１，・・・，ｒＲに対し、ｋＲ個の方程式を得ることができる。つまり、Ｒが次の数７式を満たす場合、鍵配布サーバが持つ全ての秘密鍵Ｓ（＝ａ０），Ｔ（＝ｂ１０）を導出することができてしまう。
2003094422.tif 000009
例えば、ｋ≧５であれば、３ラウンドには全ての有効な加入者端末が鍵配布サーバの秘密鍵（ＳやＴなど）を求められる。これにより、従来技術２が要件２を満たしていないことがわかる。
そこで本発明は、上述した４つの要件を全て満足し、安全性が高く高速なグループ鍵の更新方法を提供することを目的とする。
また本発明は、上記の目的に加えて、安全性が高く効率の良い放送型暗号通信を実現することを目的とする。
発明の開示
上記の目的を達成する本発明は、暗号化された情報を復号するための鍵を配布する鍵配布サーバと、当該情報を使用する所定台数の加入者端末とを備えた暗号通信システムとして実現される。この鍵配布サーバは、情報の復号に用いる暗号化された第１のグループ鍵と、この第１のグループ鍵の復号処理を実行するための加入者端末ごとに個別の復号情報と、グループ鍵の更新後に更新された第２のグループ鍵の復号処理の一部を実行するための加入者端末ごとに個別の鍵更新情報とを加入者端末に配布し、この加入者端末は、予め取得した第１のグループ鍵を復号するための鍵更新情報に基づく処理結果と鍵配布サーバから配布された復号情報とを用いて鍵配布サーバから配布された第１のグループ鍵を復号することを特徴とする。グループ鍵の復号処理を時間的に分散することにより、グループ鍵更新時の処理を軽減している。
ここで、加入者端末は、鍵更新情報を用いたグループ鍵の復号処理の一部を、このグループ鍵の配布前に実行する。グループ鍵を復号する処理の一部を加入者端末において事前に行っておくことにより、グループ鍵の更新において、安全性を損なうことなく、新しいグループ鍵が配布された後の処理に要する時間の短縮を実現している。
また好ましくは、鍵配布サーバは、第１のグループ鍵を復号するための鍵更新情報を、この第１のグループ鍵に更新される前の第３のグループ鍵と共に加入者端末に配布する。
さらに、鍵配布サーバは、グループ鍵を更新した場合に、加入者端末のうち排除対象端末を設定し、この排除対象端末以外の加入者端末が更新されたグループ鍵を復号可能となる復号情報を、更新されたグループ鍵と共に加入者端末に配布する。
また、上記の目的を達成する他の本発明は、暗号化された情報を復号するための鍵を配布する次のように構成された鍵配布サーバとして実現される。この鍵配布サーバは、情報の復号に用いる第１のグループ鍵を生成し暗号化する手段と、この第１のグループ鍵の復号処理を実行するための加入者端末ごとに個別の復号情報を生成する手段と、グループ鍵の更新後に更新された第２のグループ鍵の復号処理の一部を実行するための加入者端末ごとに個別の鍵更新情報を生成する手段と、第１のグループ鍵と復号情報と鍵更新情報とを加入者端末に配布する手段とを備えることを特徴とする。
また、上記の目的を達成するさらに他の本発明は、次のように構成された端末装置としても実現される。この端末装置は、暗号化された情報を復号するための暗号化されたグループ鍵とこのグループ鍵を復号するための復号情報とを所定の鍵配布サーバから取得する手段と、グループ鍵の復号処理の一部をこのグループ鍵の配布前に実行する手段と、このグループ鍵の復号処理の一部に基づく処理結果と鍵配布サーバから取得した復号情報とを用いてグループ鍵を復号する手段とを備えることを特徴とする。
さらに本発明は、コンピュータを制御して上記の鍵配布サーバや端末装置として機能させるプログラムとしても実現される。このプログラムは、磁気ディスクや光ディスク、半導体メモリその他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより、提供することができる。
また、本発明は、暗号化された情報を復号するための鍵を、この情報を使用する所定台数の端末で共有する、次のような鍵共有方法として実現される。すなわち、この鍵共有方法は、情報の復号に用いる暗号化されたグループ鍵を復号するための復号処理の一部が、このグループ鍵の配布前に、端末において実行されるステップと、グループ鍵とこのグループ鍵の復号処理の残りの一部を実行するための端末ごとに個別の復号情報とが、端末に配布されるステップと、配布された復号情報と事前に実行された復号処理の一部の結果とを用いたグループ鍵の復号処理が、端末において実行されるステップとを含むことを特徴とする。
発明を実施するための最良の態様
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
図１は、本実施の形態による放送型暗号通信システムの概略構成を説明する図である。
図１を参照すると、本実施の形態による放送型暗号通信システムは、暗号通信に用いられるグループ鍵を生成し配布する鍵配布サーバ１０と、鍵配布サーバ１０から配布されたグループ鍵を取得しこれを用いて暗号通信を行う加入者端末２０とを備える。
鍵配布サーバ１０は、ワークステーションやパーソナルコンピュータ、その他のネットワーク機能を備えたコンピュータ装置にて実現され、セットアップ時に、システムパラメータを決定し、各加入者端末２０に対して個人鍵を配布する。グループ鍵配送時には、どの加入者端末２０を排除するかを決定した上で、グループ鍵を暗号化し、ブロードキャストにより配送する。個人鍵やグループ鍵の生成、配送等の処理は、例えばプログラム制御されたＣＰＵの機能として実現される。
加入者端末２０は、ワークステーションやパーソナルコンピュータ、携帯電話、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、その他のネットワーク機能を備えた情報端末機器にて実現され、鍵配布サーバ１０からのブロードキャストを受信する。加入者端末ｉ（ｉ番目の加入者端末２０）は、セットアップ時に鍵配布サーバ１０から個人鍵ｓｉを受け取る。そして、この個人鍵ｓｉを用いて暗号化されているグループ鍵を復号し、さらにこのグループ鍵を用いて所定のメッセージを復号して使用する。これらの処理は、例えば、プログラム制御されたプロセッサにて実現される。加入者端末２０の集合をΦ＝｛１，・・・，ｎ｝とする（ｎ＝｜Φ｜は加入者端末２０の総数）。
加入者端末２０は、全体で、鍵配布サーバ１０から配布されたグループ鍵を用いて暗号通信を行うグループΦを構成する。このグループを構成する個々の加入者端末２０は、初期的には全て暗号通信に参加できる「有効な加入者端末」であるが、何らかの理由により「排除された加入者端末」となった後は、暗号通信には参加できない。すなわち、個人鍵を用いてグループ鍵を復元することができない。
本実施の形態における通信形態は、鍵配布サーバ１０あるいは所定のサーバと加入者端末２０との間で情報がやりとりされるクライアント／サーバ型のシステムであっても良いし、加入者端末２０相互間で情報をやりとりするピア・ツー・ピア（Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ）型のシステムであっても良い。すなわち、加入者端末２０で使用されるメッセージ（コンテンツ）の提供者は、鍵配布サーバ１０とは別個に存在しても良い。
放送型暗号通信システムにおけるグループ鍵を用いた暗号通信は、グループ鍵のセットアップ、グループ鍵を用いた情報の暗号化、グループ鍵を用いた情報の復号、及び鍵更新の４つのフェーズを含む。
図２は、本実施の形態による暗号通信の処理の流れを説明するフローチャートである。
本実施の形態では、暗号化されたグループ鍵の復号処理の中で排除対象端末の最大数ｋに依存する計算部分を事前計算（鍵更新処理）に切り分ける。これにより、証明可能な安全性を保ちつつ、鍵更新処理を除く部分のグループ鍵の復号処理を２回の冪剰余演算で高速に実行可能としている。以下、本実施の形態による暗号通信におけるプロトコルの構成法を説明する。なお、以下の説明において、受信者とは、加入者端末２０のユーザであり、加入者自身である。
１．セットアップ
Ｚｑ上のランダムなｋ次一変数多項式
2003094422.tif 000010
を選択する。Ｆ（０）＝Ｓ、Ｇ１（０）＝Ｔ１を鍵配布サーバ１０の秘密鍵とする。鍵配布サーバ１０は、ｋｅｙｉ＝（ｓｉ，ｆ１１）＝（Ｆ（ｉ），ｇＧ１（ｉ）／Ｆ（ｉ））を第１ラウンドの受信者ｉの復号鍵として、各加入者端末ｉ∈｛１，・・・，ｎ｝に秘密に配布する。グループ鍵Ｕ０∈ＧＦ（ｑ）は、全ての加入者端末２０に対して配布される（ステップ２０１）。
２．Ｉラウンドにおけるグループ鍵暗号化
鍵配布サーバ１０は、ｒＩ∈Ｚｑをランダムに選択し、ＸＩ：＝ｇｒＩを求める。次に、ｄ個の排除される加入者端末２０の集合ΛＩを決定する（ステップ２０２）。ｋ−ｄ個の整数をｎ＋ｋ（Ｒ−１）とｎ＋ｋＲの間から選び、それらからなる集合をΘＩとする。鍵配布サーバ１０はＭＩ１，・・・，ＭＩｋを次の数９式にて求める。
2003094422.tif 000011
また、有効な加入者端末２０であるΩＩ（以下、加入者端末ΩＩ）がＩラウンドの配送鍵ＵＩを計算するために必要なヘッダ情報ＨＩを、次の数１０式にて計算する（ステップ２０３）。
2003094422.tif 000012
ここで、Ｉラウンドにおいて有効な加入者端末ΩＩにて共有されるグループ鍵は、ＵＩ＝ｇｒＳ＋ＴＩである。
次に、Ｉ＋１ラウンドにグループ鍵を配送するための（すなわち、加入者端末２０がＩ＋１ラウンドのグループ鍵の復号処理における鍵更新処理で用いる）鍵更新情報を生成する。鍵配布サーバ１０は、ｂＩ＋１，ｊ∈Ｚｑ（ｊ＝０，・・・，ｋ）をランダムに選択し、（ｕＩ０，・・・，ｕＩｋ）＝（ｇｂＩ＋１，０，・・・，ｇｂＩ＋１，ｋ）を求め、次の数１１式によりＩラウンドのグループ鍵ＵＩで暗号化してＣＩを求める（ステップ２０４）。
2003094422.tif 000013
そして、鍵配布サーバ１０は、（ＨＩ，ＣＩ）を全ての加入者端末２０（すなわちΦ）に対してブロードキャストで配布する（ステップ２０５）。
３．Ｉラウンドにおけるグループ鍵復号
Ｉラウンドにおける復号可能な加入者端末２０である加入者端末ｖ（∈ΩＩ）は、次の数１２式により、Ｉラウンドの復号を行う（ステップ２０６）。
2003094422.tif 000014
すなわち、ここではＩ−１ラウンドで配布された情報に基づいて事前計算されたｆＩｖと、ステップ２０５で配布されたＨＩから解読されるＢＩとを用いてＩラウンドのグループ鍵ＵＩを復号している。
４．Ｉ＋１ラウンドへ向けての鍵更新処理（事前計算）
有効な各加入者端末ｖ∈ΩＩは、鍵配布サーバ１０から配布されたＣＩに含まれる鍵更新情報を用い、次の数１３式にて事前計算（すなわちＩ＋１ラウンドのグループ鍵の配布前の処理）である鍵更新処理を行う（ステップ２０７）。
2003094422.tif 000015
また、鍵配布サーバ１０は、Ｉ＋１ラウンドのグループ鍵の生成に先立って、次の数１４式の事前計算を実行する。
2003094422.tif 000016
これら加入者端末２０及び鍵配布サーバ１０による鍵更新処理（事前計算）は、Ｉラウンドのグループ鍵と共に配布された情報を用いて、Ｉ＋１ラウンドのグループ鍵が配布される前までに実行しておく。
以上のように構成される本実施の形態による放送型暗号通信システムが、上述した安全性・効率上の４つの要件を満たすかどうかを検討する。
まず、本実施の形態は、加入者端末２０間の通信を必要としていないことから、要件１を満たすことは明らかである。
また、本実施の形態において配布される暗号文の長さはＯ（ｋ）、個人鍵のサイズはＯ（１）であり、要件３も満たす。
さらに、本実施の形態における復号処理は２回の冪剰余演算で構成されており、要件４も満たしている。
次に、本実施の形態が残る要件２を満たすことを示す。
まず、要件２で述べられている「排除されたｋ個の加入者端末の持つ個人鍵を用いる」攻撃者をモデル化する。この攻撃者は、Ｒラウンドまでに排除されたメンバｋ人の復号鍵、及びＲラウンド以前に受け取った情報からＲラウンドのグループ鍵を多項式時間で求めるアルゴリズムＭ１としてモデル化できる。一般性を失わずに（ｋ個の）排除された加入者端末２０をｉ＝１，・・・，ｋとする。Ｍ１のインプットは、
〈ｇ，ｐ，ｑ，ｋ，Ｕ０，（ｓ１，．．．，ｓｋ），（ｆ１１，．．．，ｆ１ｋ），（Ｈ１，Ｃ１），．．．，（ＨＲ，ＣＲ）〉
である。
このようにモデル化すると、要件２は、ＤＤＨ問題（Ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ｐｒｏｂｌｅｍ）を用いて次のように言い換えることができる。
（命題）
「ＤＤＨ問題を解く多項式時間アルゴリズムが存在しない限り、Ｍ１は存在しない」
ＤＤＨ問題とは、ｇ，ｈ∈ＧＦ（ｑ），ａ，ｂ∈Ｚｑをランダムに選んだとき、ＧＦ（ｑ）上において、Ｄ＝〈ｇ，ｈ，ｇａ，ｈａ〉（この形を「Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎの組」と呼ぶ）とＲ＝〈ｇ，ｈ，ｇａ，ｈａ〉とを有意な確率を持って区別する判定問題である。ＤＤＨ問題を多項式時間で解くアルゴリズムは知られていない。すなわち、計算量的に困難であると仮定できる数学的な問題であり、上記の命題からＭ１は存在しない。したがって、本実施の形態は要件２を満足する。
以上のように、本実施の形態による放送型暗号通信システムのグループ鍵共有方法によれば、グループ鍵を更新するにあたって、証明可能な安全性を確保でき、かつグループ鍵の復号処理の一部を事前計算にて当該グループ鍵が配布される前に行うことにより、更新されたグループ鍵が配布された後の処理では加入者端末数ｎ、及び排除対象端末の最大数ｋに依存せず、２回の冪剰余演算のみで復号処理を実現できる。したがって、加入者端末２０の数が膨大であるネットワークシステムにおいて、特に有効である。
次に、本実施の形態による放送型暗号通信システムを種々のネットワークシステムに適用した場合の構成例を説明する。
〔ピア・ツー・ピアにおけるグループメンバー管理〕
ピア・ツー・ピア（Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ：Ｐ２Ｐ）型のネットワークシステムにおいて、グループ内通信を安全かつ高速に行うために、本実施の形態を用いることができる。すなわち、ネットワークシステムにおけるグループ内の全てのピア（Ｐｅｅｒ）が１つの鍵（グループ鍵）を共有し、放送型暗号通信を行う。
図３は、本実施の形態を適用したピア・ツー・ピア型ネットワークシステムの構成を示す図である。図３において、対象であるネットワークシステムのグループマネージャーが本実施の形態の鍵配布サーバ１０を構成し、グループ内の各ピア（Ｐｅｅｒ）が加入者端末２０を構成する。
このようなネットワークシステムでは、例えばｊｘｔａにおけるｌｅａｖｅなどによって所定のピア（Ｐｅｅｒ）がグループから離脱した場合、それ以降のグループ内通信を安全に行うためには、新たなグループ鍵を残りのピア（Ｐｅｅｒ）の間で迅速に再共有する必要がある。一方で、ピア・ツー・ピア型ネットワークでは様々な端末がピア（Ｐｅｅｒ）となり得るため、非常に計算能力の限られた端末であっても容易にグループ鍵を入手できなければならない。本実施の形態は、このようなピア・ツー・ピア型ネットワークシステムにおけるグループメンバー管理に容易に適用できる。
本実施の形態を適用することにより、グループ鍵の復号処理は、２回の冪剰余乗算で完了するため、大きな計算能力を必要としない。また、大規模なネットワークで適用した場合でも効率性を損なわずに高速にグループ鍵の更新を行い利用可能とすることができる。
〔リアルタイムコンテンツ配信システム〕
ゲーム機の高機能化に伴い、ゲーム機をピア（Ｐｅｅｒ）と見立ててピア・ツー・ピア型ネットワークを構成することにより、ユーザ間のインタラクションを容易にするようなオンラインゲームが出現している。すなわち、グループマネージャに相当するサーバがゲームコンテンツを各ゲーム機に提供し、各ゲーム機間でピア・ツー・ピア型の通信を行いながらゲームを進行する。
図４は、本実施の形態を適用したこの種のコンテンツ配信システムの構成を示す図である。図４において、ゲームコンテンツを配信するサーバが本実施の形態の鍵配布サーバ１０を構成し、各ゲーム機が加入者端末２０を構成する。
このような環境においては、グループ内での放送型暗号通信が頻繁に必要になることが予想されるが、その一方でグループからのメンバの離脱も頻繁に起こりえると考えられる。例えば、利用料金を滞納したユーザはグループへの接続を解除する必要がある。したがって、グループからメンバが離脱する際に要する、グループ鍵共有のための復号処理時間を短縮することは、アプリケーションの利用性を高める。
本実施の形態による放送型暗号通信は、高速な復号処理を実現し、大規模なネットワークに対応可能であるため、図４に示すシステムにおけるコンテンツの配信に適用することができる。すなわち、グループ鍵を高速に共有することができ、これにより暗号化されたコンテンツを受信と同時にリアルタイムで復号することが可能になる。また、時間を要する鍵更新処理は、コンテンツ受信後に当該コンテンツ実行時の余剰処理能力を用いて行うことができる。なお、ここではオンラインゲームを実行するためのコンテンツ配信を例として説明したが、ゲームの他にもリアルタイムで実行するような種々のコンテンツを配信する場合に、本実施の形態による放送型暗号通信を適用できることは言うまでもない。
〔携帯電話加入者へのデータ配信〕
近年、携帯電話の利用は人口の過半数をカバーするほどに拡大している。そこで、数百万の携帯電話加入者に対してグループ暗号化通信のサービスを行う場面を考える。例えば、グループを構成した端末に対して特定のサービスを提供する場合などがある。
図５は、本実施の形態を適用した携帯電話を対象とするサービス提供システムの構成を示す図である。図５において、サービスを提供するサーバが鍵配布サーバ１０を構成し、サービスの利用登録がなされている携帯電話が加入者端末２０を構成する。
このようなネットワークシステムでは、サービスの利用料金を滞納したり、端末の紛失や盗難があった場合に、特定の端末の持つグループへのアクセス権限を無効化する必要がある。本実施の形態は、本発明を適用することで、非力な携帯電話に対しても利用可能な放送型暗号通信を実現できる。
〔マルチメディアコンテンツ配信システム〕
近年、ＤＶＤを用いたマルチメディアコンテンツ配信システムが爆発的に普及している。
図６は、本実施の形態を適用したマルチメディアコンテンツ配信システムの構成を示す図である。図６において、マルチメディアコンテンツを提供するコンテンツプロバイダが本実施の形態の鍵配布サーバ１０を構成し、当該マルチメディアコンテンツの再生機が加入者端末２０を構成する。
このシステムにおいて、ＤＶＤメディアは暗号化されたデジタルコンテンツ（映画や音楽、ソフトウェアなど）が記憶された状態で配布される。暗号化されたコンテンツは再生機に搭載された再生復号器内に保管される復号鍵を用いて復号される。復号鍵は再生復号器のメーカーごとに異なり、再生復号器の安全なメモリエリアに格納されている。だが、クラッカーの解析やメーカーの不手際により、復号鍵が漏洩してしまう場面が起こり得る。この場合に、一部の復号鍵を使用不可能にする暗号化手法が必要となる。
本実施の形態を適用することにより、証明可能な安全性を確保して、一部の復号鍵を使用不可能にするための復号鍵の更新を行うことが可能となる。
〔警察無線機の紛失・盗難に対応する秘密放送システム〕
警察無線は、グループ内秘匿通信の代表例である。警察官の所持する無線機以外の無線受信機を用いても通信が傍受できないようにすることが必要となる。
図７は、本実施の形態を適用した秘密放送システムの構成を示す図である。図７において、秘密放送の放送局が鍵配布サーバ１０を構成し、各無線受信機が加入者端末２０を構成する。
上記のように、警察無線のような秘密放送では、警察官の所持する無線機以外の無線受信機では通信を傍受できないような工夫が必要であるが、警察官が無線機を紛失したり盗難されたりした場合、本実施の形態により、かかる無線機を加入者端末２０のグループ（Φ）から排除して新しいグループ鍵を共有することにより、紛失した無線機を利用不可能にすることができる。
発明の効果
以上説明したように、本発明によれば、安全性が高く高速なグループ鍵の更新方法を提供することができる。
また本発明によれば、安全性が高く効率の良い放送型暗号通信を実現することができる。
【図面の簡単な説明】
図１は本実施の形態による放送型暗号通信システムの概略構成を説明する図である。
図２は本実施の形態による暗号通信の処理の流れを説明するフローチャートである。
図３は本実施の形態を適用したピア・ツー・ピア型ネットワークシステムの構成を示す図である。
図４は本実施の形態を適用したリアルタイムコンテンツ配信システムの構成を示す図である。
図５は本実施の形態を適用した携帯電話を対象とするサービス提供システムの構成を示す図である。
図６は本実施の形態を適用したマルチメディアコンテンツ配信システムの構成を示す図である。
図７は本実施の形態を適用した秘密放送システムの構成を示す図である。
【図１】
2003094422.tif 000017
【図２】
2003094422.tif 000018
【図３】
2003094422.tif 000019
【図４】
2003094422.tif 000020
【図５】
2003094422.tif 000021
【図６】
2003094422.tif 000022
【図７】
2003094422.tif 000023
【国際調査報告】
2003094422.tif 000024
2003094422.tif 000025