(57)【特許請求の範囲】
【請求項１】
関数暗号方式に則って第１シード値を暗号化し、有効時間区間に属する時間に対応する情報を含む情報に対応する秘密鍵で復号可能な暗号文を得、前記暗号文と共有情報とを出力する第１配送処理部と、
前記共有情報が秘匿化された秘匿化共有情報が入力され、前記秘匿化共有情報と管理秘密値とに応じた第２シード値の秘匿化情報を得、前記第２シード値の秘匿化情報を出力する第２配送処理部と、
を有する鍵配送管理装置。
【請求項２】
請求項１の鍵配送管理装置であって、
前記共有情報と新たな管理秘密値とに応じた新たな共有情報を得、前記新たな共有情報と前記秘匿化共有情報とを出力する第３配送処理部と、
前記新たな共有情報が秘匿化された新たな秘匿化共有情報が入力され、前記新たな秘匿化共有情報と前記新たな管理秘密値とに応じた新たな第２シード値の秘匿化情報を得、前記新たな第２シード値の秘匿化情報を出力する第４配送処理部を有する、鍵配送管理装置。
【請求項３】
請求項１の鍵配送管理装置であって、
前記秘匿化共有情報と新たな管理秘密値とに応じた新たな第２シード値の秘匿化情報を得、前記新たな第２シード値の秘匿化情報を出力する第５配送処理部を有する、鍵配送管理装置。
【請求項４】
請求個１から３の何れかの鍵配送管理装置であって、
前記関数暗号方式に則って新たな第１シード値を暗号化し、新たな有効時間区間に属する時間に対応する情報を含む情報に対応する新たな秘密鍵で復号可能な新たな暗号文を得、前記新たな暗号文を出力する第６配送処理部を有する、鍵配送管理装置。
【請求項５】
暗号文が入力され、有効時間区間に属する時間に対応する情報を含む情報に対応する秘密鍵を用い、関数暗号方式に則って前記暗号文を復号して第１シード値を得る第１処理部と、
共有情報が入力され、前記共有情報と端末秘密値の逆元とに応じた秘匿化共有情報を得、前記秘匿化共有情報を出力する第２処理部と、
第２シード値の秘匿化情報が入力され、前記第２シード値の秘匿化情報と前記端末秘密値とに応じた第２シード値を得る第３処理部と、
前記第１シード値を含む情報と前記第２シード値を含む情報とに対応する共通鍵を得る第４処理部と、
を有する端末装置。
【請求項６】
請求項５の端末装置であって、
前記共通鍵は、前記第１シード値に関する情報および前記第２シード値に関する情報が隠蔽された情報である、端末装置。
【請求項７】
請求項５または６の端末装置であって、
新たな第２シード値の秘匿化情報が入力され、前記新たな第２シード値の秘匿化情報と前記端末秘密値とに応じた新たな第２シード値を得る第５処理部を有する端末装置。
【請求項８】
暗号文が入力され、有効時間区間に属する時間に対応する情報を含む情報に対応する秘密鍵を用い、関数暗号方式に則って前記暗号文を復号して第１シード値を得る第１処理部と、
秘匿化共有情報が入力され、前記秘匿化共有情報と端末秘密値とに応じた新たな秘匿化共有情報を得、前記新たな秘匿化共有情報を出力する第６処理部と、
新たな共有情報が入力され、前記新たな共有情報と前記端末秘密値とに応じた新たな第２シード値を得る第７処理部と、
前記第１シード値を含む情報と前記第２シード値を含む情報とに対応する共通鍵を得る第４処理部と、
を有する端末装置。
【請求項９】
鍵配送管理装置と複数の端末装置とを有する鍵配送システムであって、
前記鍵配送管理装置は、
関数暗号方式に則って第１シード値を暗号化し、有効時間区間に属する時間に対応する情報を含む情報に対応する秘密鍵で復号可能な暗号文を得、前記暗号文と共有情報とを前記端末装置に出力する第１配送処理部を含み、
前記端末装置は、
前記暗号文が入力され、前記秘密鍵を用い、前記関数暗号方式に則って前記暗号文を復号して第１シード値を得る第１処理部と、
前記共有情報が入力され、前記共有情報と端末秘密値の逆元とに応じた秘匿化共有情報を得、前記秘匿化共有情報を出力する第２処理部と、を含み、
前記鍵配送管理装置は、
前記秘匿化共有情報が入力され、前記秘匿化共有情報と管理秘密値とに応じた第２シード値の秘匿化情報を得、前記第２シード値の秘匿化情報を出力する第２配送処理部を含み、
前記端末装置は、
前記第２シード値の秘匿化情報が入力され、前記第２シード値の秘匿化情報と前記端末秘密値とに応じた第２シード値を得る第３処理部と、
前記第１シード値を含む情報と前記第２シード値を含む情報とに対応する共通鍵を得る第４処理部とを含む、鍵配送システム。
【請求項１０】
請求項１から４の何れかの鍵配送管理装置または請求項５から８の何れかの端末装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に、共通鍵を共有する鍵配送方式に関する。
【背景技術】
【０００２】
従来の動的鍵配送方式の一つにＳＴＷ方式がある（例えば、非特許文献１参照）。ＳＴＷ方式では、ユーザ集合に属する端末装置がピア・ツー・ピアで通信を行い、これらの端末装置が共通のセッション鍵（共通鍵）を共有する。既存のユーザ集合に新たな端末装置を追加した場合や、既存のユーザ集合から端末装置を削除した場合には、更新後のユーザ集合に応じた新たな共通鍵が生成される。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Michael Steiner, Gene Tsudik, Michael Waidner, “Diffie-Hellman Key Distribution Extended to Group Communication,” ACM Conference on Computer and Communications Security 1996, 31-37.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の既存技術では、通信路の盗聴のみを行う攻撃者に対しては、共通鍵の情報が漏れないが、通信路上で改ざんを行うような攻撃者に対しては成りすましを防げない。また、鍵配送時に一部の端末装置がブロードキャストを行う必要があり、端末装置数が増大するとそれらの端末装置の計算・通信コストが増大するという問題がある。
【０００５】
本発明の課題は、通信路上での成り済ましに対する安全性が高く、端末装置の計算・通信コストが小さな鍵配送技術を提供することである。
【課題を解決するための手段】
【０００６】
鍵配送管理装置は、関数暗号方式に則って第１シード値を暗号化し、有効時間区間に属する時間に対応する情報を含む情報に対応する秘密鍵で復号可能な暗号文を得、暗号文と共有情報とを端末装置に出力する。端末装置は、前記有効時間区間に属する時間に対応する情報を含む情報に対応する秘密鍵を用い、前記関数暗号方式に則って前記暗号文を復号して第１シード値を得、前記共有情報と端末秘密値の逆元とに応じた秘匿化共有情報を得て出力する。鍵配送管理装置は、前記秘匿化共有情報と管理秘密値とに応じた第２シード値の秘匿化情報を得て出力する。端末装置は、前記第２シード値の秘匿化情報と前記端末秘密値とに応じた第２シード値を得、前記第１シード値を含む情報と前記第２シード値を含む情報とに対応する共通鍵を得る。
【発明の効果】
【０００７】
以上より、通信路上での成り済ましに対する安全性が高く、端末装置の計算・通信コストが小さな鍵配送が可能となる。
【図面の簡単な説明】
【０００８】
【図１】図１は、実施形態の鍵配送システムの機能構成を例示したブロック図である。
【図２】図２Ａは、第１実施形態の鍵配送管理装置の機能構成を例示したブロック図であり、図２Ｂは、第１実施形態の端末装置の機能構成を例示したブロック図である。
【図３】図３は、第１実施形態の鍵配送処理を例示するためのシーケンス図である。
【図４】図４は、第１実施形態のユーザ追加処理を例示するためのシーケンス図である。
【図５】図５Ａは、第１実施形態の有効時間区間の更新処理を例示するためのシーケンス図であり、図５Ｂは、第１実施形態のユーザ削除処理を例示するためのシーケンス図である。
【図６】図６は、第２実施形態の鍵配送管理装置の機能構成を例示したブロック図である。
【図７】図７は、第２実施形態の端末装置の機能構成を例示したブロック図である。
【図８】図８は、第２実施形態の秘密鍵配送処理を例示するためのシーケンス図である。
【図９】図９は、第２実施形態の鍵配送処理を例示するためのシーケンス図である。
【図１０】図１０は、第２実施形態の鍵配送処理を例示するためのシーケンス図である。
【図１１】図１１は、第２実施形態の鍵配送処理を例示するためのシーケンス図である。
【図１２】図１２は、第２実施形態の端末追加処理を例示するためのシーケンス図である。
【図１３】図１３は、第２実施形態の端末追加処理を例示するためのシーケンス図である。
【図１４】図１４は、第２実施形態の端末追加処理を例示するためのシーケンス図である。
【図１５】図１５は、第２実施形態の端末削除処理を例示するためのシーケンス図である。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施形態を説明する。
［第１実施形態］
まず、本発明の第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の鍵配送システム１は、端末装置１２−１〜１２−Ｎと鍵配送管理装置１１とを有する。ただし、Ｎは３以上の整数である。端末装置１２−１〜１２−Ｎと鍵配送管理装置１１とはインターネット等の安全ではない通信路を通じて通信可能に構成されている。
【００１０】
図２Ａに例示するように、本形態の鍵配送管理装置１１は、制御部１１０と配送処理部１１１，１１２と通信部１１８と記憶部１１９とを有する。図２Ｂに例示するように、本形態の端末装置１２−ｈは、制御部１２０−ｈと処理部１２１−ｈ〜１２４−ｈと通信部１２８−ｈと記憶部１２９−ｈとを有する。ただし、ｈ∈［１，Ｎ］である。［１，Ｎ］は１以上Ｎ以下の整数からなる集合｛１，・・・，Ｎ｝を表す。各装置は、例えば、通信装置、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。また、各装置は自らが備える制御部１１０，１２０−ｈの制御に基づいて各処理を実行する。各装置の各処理で得られたデータは、逐一、それぞれが備える記憶部１１９，１２９−ｈに格納され、必要に応じて読み出されて使用される。
【００１１】
＜鍵配送処理＞
以下、端末装置１２−１〜１２−Ｎからなる集合の部分集合（ユーザ集合）である端末装置１２−σ（１）〜１２−σ（ｎ）がセッションを立ち上げ、共通鍵を共有する処理を説明する。ただし、ｎは２以上Ｎ以下の整数であり、｛σ（１），・・・，σ（ｎ）｝⊂｛１，・・・，Ｎ｝であるとする。以降、記述を簡単にするために、一般性を失うことなく（σ（１），・・・，σ（ｎ））＝（１，・・・，ｎ）と仮定することにする。
【００１２】
図３に例示するように、まず鍵配送管理装置１１（図２Ａ）の配送処理部１１１が、関数暗号方式に則り、端末装置１２−ｉの識別情報Ｕｉと有効時間区間（タイムフレーム）ＴＦに属する時間ｔｉｍｅ∈ＴＦに対応する情報を含む情報Ｖ（Ｕｉ，ｔｉｍｅ）に対応する秘密鍵ｕｓｋｉを生成し、各秘密鍵ｕｓｋｉを端末装置１２−ｉに安全に配送する。ただし、ｉ∈［１，ｎ］である。「有効時間区間」は、所定の時間区間であり、所定の契機で更新される。秘密鍵ｕｓｋｉは、端末装置１２−ｉの公開鍵で暗号化されてから配送されてもよいし、安全な通信路を通じて配送されてもよいし、可搬型記録媒体に格納されて配送されてもよい。秘密鍵ｕｓｋｉは端末装置１２−ｉ（図２Ｂ）で復号等によって取得され、記憶部１２９−ｉに安全に格納される。
【００１３】
「関数暗号方式」とは、「属性情報」と呼ばれる情報と「アクセス構造（または述語情報）」と呼ばれる情報との組み合わせが所定の論理式の真理値を「真」にする関係にある場合に暗号文が復号される方式である。関数暗号方式では、「属性情報」と「アクセス構造（または述語情報）」との一方の情報が秘密鍵に埋め込まれ、他方の情報が暗号文に埋め込まれる。秘密鍵に埋め込まれた「属性情報」または「アクセス構造（または述語情報）」と暗号文に埋め込まれた「アクセス構造（または述語情報）」または「属性情報」が上述の論理式の真理値を「真」にする関係にある場合、当該秘密鍵と暗号文とから復号結果が得られる。「関数暗号方式」は「関数型暗号方式」や「述語暗号方式」と呼ばれることもあり、例えば、参考文献１「T. Okamoto, K. Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption," Advances in Cryptology - CRYPTO 2010, Lecture Notes in Computer Science, 2010, Volume 6223/2010, 191-208」、参考文献２（J. Katz, A. Sahai, and B. Waters., "Predicate encryption supporting disjunctions, polynomial equations, and inner products," In EUROCRYPT, pp. 146-162, 2008.）、参考文献３（T. Okamoto and K. Takashima., "Hierarchical predicate encryption for inner-products," In ASIACRYPT, pp. 214-231, 2009.）等に具体的な方式が開示されている。ただし、本形態で使用可能な関数暗号方式はこれらの方式に限定されない。「情報Ｖ（Ｕｉ，ｔｉｍｅ）」は、識別情報Ｕｉと時間ｔｉｍｅ∈ｔｉｍｅに対応する情報からなる情報であってもよいし、識別情報Ｕｉと時間ｔｉｍｅ∈ｔｉｍｅに対応する情報とその他の情報（公開パラメータやセッションＩＤ等）とからなる情報であってもよい。本形態では「情報Ｖ（Ｕｉ，ｔｉｍｅ）」が「属性情報」である例を示す。「属性情報」や「アクセス構造（または述語情報）」の実装方法に限定はないが、例えば、「属性情報」や「述語情報」はベクトルまたはベクトルの集合として実装でき、「アクセス構造」は行列とその各行に対応するラベルとからなるラベル付き行列と写像（例えば、ベクトルを写す写像）とによって実装できる。例えば、「α１がη１である」という命題１と「α２がη２である」という命題２との論理和（α１＝η１）∨（α２＝η２）は（α１−η１）・（α２−η２）という多項式で表現できる。論理和（α１＝η１）∨（α２＝η２）が真である場合、（α１−η１）・（α２−η２）＝０となり、論理和（α１＝η１）∨（α２＝η２）が偽である場合、（α１−η１）・（α２−η２）≠０となる。すなわち、論理和（α１＝η１）∨（α２＝η２）が真であることと、（α１−η１）・（α２−η２）＝０となることとは等価である。また、「α１がη１である」という命題１と「α２がη２である」という命題２との論理積（α１＝η１）∧（α２＝η２）はι１・（α１−η１）＋ι２・（α２−η２）という多項式で表現できる。ただし、ι１及びι２は乱数である。論理積（α１＝η１）∧（α２＝η２）が真である場合、ι１・（α１−η１）＋ι２・（α２−η２）＝０になり、論理積（α１＝η１）∧（α２＝η２）が偽である場合、ι１・（ｘ１−η１）＋ι２・（α２−η２）≠０となる。すなわち、論理積（α１＝η１）∧（α２＝η２）が真であることと、ι１・（α１−η１）＋ι２・（α２−η２）＝０となることとは等価である。このように、論理式は多項式によって表現することができる。また、論理式を表現する多項式は２つのベクトルの内積で表現できる。すなわち、論理式を表現する多項式は、各項の不定元成分と１とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。そのため、ベクトルまたはベクトルの集合を用いて「属性情報」や「述語情報」を実装でき、論理式の真理値が真であることを内積が０であることに置き換えることができる。同様にこのようなベクトル集合に対応する写像とラベル付き行列と用いて「アクセス構造」を実装できる。なお、ｔｉｍｅ∈ＴＦは、例えば、ＴＦ＝｛ｔｍｉｎ，・・・，ｔｍａｘ｝とすれば、（ｔｉｍｅ＝ｔｍｉｎ）∨・・・∨（ｔｉｍｅ＝ｔｍａｘ）のような論理和で表現できる（ステップＳ１０１）。
【００１４】
次に、鍵配送管理装置１１および端末装置１２−１〜１２−ｎが協力して共有情報Ｃを生成する。この際、各端末装置１２−ｉの端末秘密値ｘｉが用いられる。例えば、Ｇを位数ｐの乗法巡回群とし、ｇ∈Ｇを群Ｇの生成元とし、ｘｉ∈Ｚｐとし、鍵配送管理装置１１および端末装置１２−１〜１２−ｎが協力してＣ：＝ｇｘ１・ｘ２・...・ｘｎを生成する。ただし、「α：＝β」はαがβを表すこと（αをβと定義すること）を意味する。上付き添え字の「ｘｉ」は「ｘｉ」を表す。集合Ｘ＝｛ｘ１，・・・，ｘｎ｝についてｇｘ１・ｘ２・...・ｘｎをｇΠＸと表記する。Ｘが空集合の場合にはΠＸ＝１となる。共有情報Ｃは、鍵配送管理装置１１（図２Ａ）の記憶部１１９に格納され、共有情報Ｃの生成に用いられた端末秘密値ｘｉは各端末装置１２−ｉ（図２Ｂ）の記憶部１２９−ｉに安全に格納される（ステップＳ１０２）。
【００１５】
鍵配送管理装置１１（図２Ａ）の配送処理部１１１は、第１シード値Ｋ１を生成し、関数暗号方式に則って第１シード値Ｋ１を暗号化し、端末装置１２−ｉの識別情報Ｕｉと有効時間区間ＴＦに属する時間に対応する情報を含む情報に対応する秘密鍵ｕｓｋｉで復号可能な暗号文ＣＴ’ｉを生成し、暗号文ＣＴ’ｉ（ただし、ｉ∈［１，ｎ］）と共有情報Ｃとを出力する。この暗号文ＣＴ’ｉは、秘密鍵ｕｓｋｉに対応する識別情報Ｕｉおよび時間ｔｉｍｅが論理式Ｐｉ：＝（ＩＤ＝Ｕｉ）∧（ｔｉｍｅ∈ＴＦ）を真にする場合に、当該秘密鍵ｕｓｋｉを用いて復号可能となる暗号文である。なお、第１シード値Ｋ１は記憶部１１９に格納される（ステップＳ１０３）。
【００１６】
暗号文ＣＴ’ｉと共有情報Ｃは通信部１１８に送られ、通信部１１８はこれらを端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）に送信する（ステップＳ１０４）。暗号文ＣＴ’ｉと共有情報Ｃは、各端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）の通信部１２８−ｉに入力され、記憶部１２９−ｉに格納される。各処理部１２１−ｉは、記憶部１２９−ｉから秘密鍵ｕｓｋｉと暗号文ＣＴ’ｉとを読み込み、入力された秘密鍵ｕｓｋｉを用い、関数暗号方式に則って、入力された暗号文ＣＴ’ｉを復号して第１シード値Ｋ１を生成し、第１シード値Ｋ１を記憶部１２９−ｉに格納する（ステップＳ１０５）。
【００１７】
各端末装置１２−ｉの処理部１２２−ｉは、記憶部１２９−ｉから共有情報Ｃと端末秘密値ｘｉを読み込み、入力された共有情報Ｃと端末秘密値ｘｉの逆元１／ｘｉとに応じた秘匿化共有情報ＳＣｉを生成し、秘匿化共有情報ＳＣｉを出力する。例えば、処理部１２２−ｉは、ＳＣｉ：＝Ｃ１／ｘｉを生成する（ステップＳ１０６）。秘匿化共有情報ＳＣｉは、通信部１２８−ｉに送られ、信部１２８−ｉは秘匿化共有情報ＳＣｉを鍵配送管理装置１１に送信する（ステップＳ１０７）。
【００１８】
秘匿化共有情報ＳＣｉ（ただし、ｉ∈［１，ｎ］）は、鍵配送管理装置１１（図２Ａ）の通信部１１８に入力され、記憶部１１９に格納される。配送処理部１１２は、管理秘密値ｘｓを生成して記憶部１１９に格納する（ステップＳ１０８）。配送処理部１１２は、記憶部１１９から秘匿化共有情報ＳＣｉ（共有情報Ｃが秘匿化された秘匿化共有情報ＳＣｉ）と管理秘密値ｘｓを読み込み、入力された秘匿化共有情報ＳＣｉと管理秘密値ｘｓとに応じた第２シード値の秘匿化情報ＳＫ２，ｉを生成し、第２シード値の秘匿化情報ＳＫ２，ｉを出力する。例えば、ｘｓ∈Ｚｐとし、配送処理部１１２は、ＳＫ２，ｉ：＝ＳＣｉｘｓ＝Ｃ（１／ｘｉ）・ｘｓを生成する。ただし、上付き添え字の「ｘｓ」は「ｘｓ」を表す。第２シード値の秘匿化情報ＳＫ２，ｉは通信部１１８に送られ、通信部１１８は第２シード値の秘匿化情報ＳＫ２，ｉ（ただし、ｉ∈［１，ｎ］）を端末装置１２−ｉに送信する（ステップＳ１０９）。
【００１９】
第２シード値の秘匿化情報ＳＫ２，ｉ（ただし、ｉ∈［１，ｎ］）は、端末装置１２−ｉ（図２Ｂ）の通信部１２８−ｉに入力され、記憶部１２９−ｉに格納される。各処理部１２３−ｉ（ただし、ｉ∈［１，ｎ］）は、記憶部１２９−ｉから第２シード値の秘匿化情報ＳＫ２，ｉと端末秘密値ｘｉとを読み込み、入力された第２シード値の秘匿化情報ＳＫ２，ｉと端末秘密値ｘｉとに応じた第２シード値Ｋ２を生成して出力する。例えば、処理部１２３−ｉは、Ｋ２：＝ＳＫ２，ｉｘｉ＝Ｃ（１／ｘｉ）・ｘｓ・ｘｉ＝Ｃｘｓを生成する。第２シード値Ｋ２は記憶部１２９−ｉに格納される（ステップＳ１０９）。
【００２０】
各処理部１２４−ｉ（ただし、ｉ∈［１，ｎ］）は、記憶部１２９−ｉから第１シード値Ｋ１および第２シード値Ｋ２を読み込み、第１シード値Ｋ１を含む情報と第２シード値Ｋ２を含む情報とに対応する共通鍵Ｋを得て出力する。これにより、端末装置１２−１〜１２−ｎで共通鍵Ｋを共有できる。なお、第１シード値Ｋ１を含む情報は、第１シード値Ｋ１のみからなる情報であってもよいし、第１シード値Ｋ１とその他の情報（公開パラメータやセッションＩＤ等）とからなる情報であってもよい。同様に、第２シード値Ｋ２を含む情報は、第２シード値Ｋ２のみからなる情報であってもよいし、第２シード値Ｋ２とその他の情報（公開パラメータやセッションＩＤ等）とからなる情報であってもよい。また共通鍵Ｋは、第１シード値Ｋ１を含む情報と第２シード値Ｋ２を含む情報とから一義的に決まる。安全性の観点から、共通鍵Ｋは、第１シード値Ｋ１に関する情報および第２シード値Ｋ２に関する情報が隠蔽された情報であることが望ましい。言い換えると、共通鍵Ｋから第１シード値Ｋ１に関する情報も第２シード値Ｋ２に関する情報も漏洩しないことが望ましい。これにより、攻撃者に共通鍵Ｋが漏洩した場合であっても、第１シード値Ｋ１または第２シード値Ｋ２の一方を更新し、それらに応じた共通鍵Ｋに更新するだけで、当該攻撃者からの攻撃を防ぐことができる（ステップＳ１１０）。
【００２１】
＜端末装置追加処理＞
端末装置１２−１〜１２−ｎからなるユーザ集合に新たな端末装置１２−（ｎ＋１）を追加し、共通鍵Ｋを更新する処理を説明する。一般性を失うことなく、新たな端末装置を端末装置１２−（ｎ＋１）とすることができる。
【００２２】
図４に例示するように、まず、鍵配送管理装置１１（図２Ａ）の配送処理部１１１が、関数暗号方式に則り、端末装置１２−（ｎ＋１）の識別情報Ｕｎ＋１と有効時間区間ＴＦに属する時間ｔｉｍｅ∈ＴＦに対応する情報を含む情報Ｖ（ｎ＋１，ｔｉｍｅ）に対応する秘密鍵ｕｓｋｎ＋１を生成し、秘密鍵ｕｓｋｎ＋１を端末装置１２−（ｎ＋１）に安全に配送する。秘密鍵ｕｓｋｎ＋１は端末装置１２−（ｎ＋１）（図２Ｂ）の記憶部１２９−（ｎ＋１）に安全に格納される（ステップＳ１１１）。
【００２３】
次に配送処理部１１１は、記憶部１１９から第１シード値Ｋ１を読み込み、関数暗号方式に則って第１シード値Ｋ１を暗号化し、端末装置１２−（ｎ＋１）の識別情報Ｕｎ＋１と有効時間区間ＴＦに属する時間に対応する情報を含む情報に対応する秘密鍵ｕｓｋｎ＋１で復号可能な暗号文ＣＴ’ｎ＋１を生成し、記憶部１１９に格納する。暗号文ＣＴ’ｎ＋１は、秘密鍵ｕｓｋｎ＋１に対応する識別情報Ｕｎ＋１および時間ｔｉｍｅが論理式Ｐｎ＋１＝（ＩＤ＝Ｕｎ＋１）∧（ｔｉｍｅ∈ＴＦ）を真にする場合に、当該秘密鍵ｕｓｋｎ＋１を用いて復号可能となる暗号文である（ステップＳ１１３）。
【００２４】
配送処理部１１２は、新たな管理秘密値ｘ’ｓを生成し、記憶部１１９に格納する。配送処理部１１２は、記憶部１１９から共有情報Ｃと新たな管理秘密値ｘ’ｓとを読み込み、入力された共有情報Ｃと新たな管理秘密値ｘ’ｓとに応じた新たな共有情報Ｃ’を生成し、記憶部１１９に格納する。例えば、ｘ’ｓ∈Ｚｐとし、配送処理部１１２は、Ｃ’：＝Ｃｘ’ｓを生成する。ただし、上付き添え字の「ｘ’ｓ」は「ｘ’ｓ」を表す（ステップＳ１１４）。
【００２５】
暗号文ＣＴ’ｎ＋１、新たな共有情報Ｃ’、および秘匿化共有情報ＳＣｉ（ただし、ｉ∈［１，ｎ］）が記憶部１１９から読み出されて通信部１１８に送られる。通信部１１８は、これらを端末装置１２−（ｎ＋１）に送信する（ステップＳ１１５）。
【００２６】
暗号文ＣＴ’ｎ＋１、新たな共有情報Ｃ’、および秘匿化共有情報ＳＣｉ（ただし、ｉ∈［１，ｎ］）は、端末装置１２−（ｎ＋１）（図２Ｂ）の通信部１２８−（ｎ＋１）に入力され、記憶部１２９−（ｎ＋１）に格納される。処理部１２１−（ｎ＋１）は、記憶部１２９−（ｎ＋１）から暗号文ＣＴ’ｎ＋１と秘密鍵ｕｓｋｎ＋１とを読み込み、入力された秘密鍵ｕｓｋｎ＋１を用い、関数暗号方式に則って、入力された暗号文ＣＴ’ｎ＋１を復号して第１シード値Ｋ１を生成して出力する。第１シード値Ｋ１は記憶部１２９−（ｎ＋１）に格納される（ステップＳ１１６）。
【００２７】
処理部１２２−（ｎ＋１）は、端末秘密値ｘｎ＋１を生成して記憶部１２９−（ｎ＋１）に格納する。処理部１２２−（ｎ＋１）は、記憶部１２９−（ｎ＋１）から秘匿化共有情報ＳＣｉ（ただし、ｉ∈［１，ｎ］）と端末秘密値ｘｎ＋１とを読み込み、入力された秘匿化共有情報ＳＣｉと端末秘密値ｘｎ＋１とに応じた新たな秘匿化共有情報ＳＣ’ｉ（ただし、ｉ∈［１，ｎ］）を生成して記憶部１２９−（ｎ＋１）に格納する。例えば、ｘｎ＋１∈Ｚｐとし、処理部１２２−（ｎ＋１）は、ＳＣ’ｉ：＝ＳＣｉｘｎ＋１＝Ｃ（１／ｘｉ）・ｘｎ＋１を生成する。ただし、上付き添え字の「ｘｎ＋１」は「ｘｎ＋１」を表す。新たな秘匿化共有情報ＳＣ’ｉは記憶部１２９−（ｎ＋１）から読み出されて通信部１２８−（ｎ＋１）に送られ、通信部１２８−（ｎ＋１）は、新たな秘匿化共有情報ＳＣ’ｉ（ただし、ｉ∈［１，ｎ］）を鍵配送管理装置１１に送信する（ステップＳ１１８）。
【００２８】
処理部１２３−（ｎ＋１）は、記憶部１２９−（ｎ＋１）から新たな共有情報Ｃ’と端末秘密値ｘｎ＋１とを読み込み、入力された新たな共有情報Ｃ’と端末秘密値ｘｎ＋１とに応じた新たな第２シード値Ｋ’２を生成して出力する。例えば、処理部１２３−（ｎ＋１）は、Ｋ’２：＝Ｃ’ｘｎ＋１＝Ｃｘ’ｓ・ｘｎ＋１を生成する。ただし、上付き添え字の「ｘ’ｓ・ｘｎ＋１」は「ｘ’ｓ・ｘｎ＋１」を表す。新たな第２シード値Ｋ’２は記憶部１２９−（ｎ＋１）に格納される（ステップＳ１１９）。
【００２９】
新たな秘匿化共有情報ＳＣ’ｉ（ただし、ｉ∈［１，ｎ］）は、鍵配送管理装置１１（図２Ａ）の通信部１１８に入力され、記憶部１１９に格納される。配送処理部１１２は、記憶部１１９から新たな秘匿化共有情報ＳＣ’ｉと新たな管理秘密値ｘ’ｓとを読み込み、入力された新たな秘匿化共有情報ＳＣ’ｉと新たな管理秘密値ｘ’ｓとに応じた新たな第２シード値の秘匿化情報ＳＫ’２，ｉ（ただし、ｉ∈［１，ｎ］）を生成し、記憶部１１９に格納する。例えば、配送処理部１１２は、ＳＫ’２，ｉ：＝ＳＣ’ｉｘ’ｓ＝Ｃ（１／ｘｉ）・ｘｎ＋１・ｘ’ｓを生成する。新たな第２シード値の秘匿化情報ＳＫ’２，ｉが記憶部１１９から読み出されて通信部１１８に送られる。通信部１１８は、新たな第２シード値の秘匿化情報ＳＫ’２，ｉを端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）に送信する（ステップＳ１２０）。
【００３０】
新たな第２シード値の秘匿化情報ＳＫ’２，ｉは、端末装置１２−ｉ（図２Ｂ）の通信部１２８−ｉに入力され、記憶部１２９−ｉに格納される。処理部１２３−ｉは、記憶部１２９−ｉから、新たな第２シード値の秘匿化情報ＳＫ’２，ｉと端末秘密値ｘｉとを読み込み、入力された新たな第２シード値の秘匿化情報ＳＫ’２，ｉと端末秘密値ｘｉとに応じた新たな第２シード値Ｋ’２を生成して記憶部１２９−ｉに格納する。例えば、処理部１２３−ｉは、Ｋ’２：＝ＳＫ’２，ｉｘｉ＝Ｃｘ’ｓ・ｘｎ＋１を生成する。新たな第２シード値Ｋ’２は記憶部１２９−（ｎ＋１）に格納される（ステップＳ１２１）。
【００３１】
端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）の処理部１２４−ｉは、記憶部１２９−ｉから第１シード値Ｋ１および新たな第２シード値Ｋ’２を読み込み、Ｋ１を含む情報とＫ’２を含む情報とに対応する共通鍵Ｋ’を生成して出力する。同様に、端末装置１２−（ｎ＋１）の１２４−（ｎ＋１）は、記憶部１２９−（ｎ＋１）から第１シード値Ｋ１および新たな第２シード値Ｋ’２を読み込み、Ｋ２：＝Ｋ’２とし、Ｋ１を含む情報とＫ２を含む情報とに対応する共通鍵Ｋ’を生成して出力する（ステップＳ１２２）。
【００３２】
＜有効期間更新処理＞
端末装置１２−１〜１２−ｎからなるユーザ集合で共通鍵Ｋを共有した後、有効時間区間を更新する処理を説明する。
【００３３】
図５Ａに例示するように、まず鍵配送管理装置１１（図２Ａ）の配送処理部１１１が、関数暗号方式に則り、端末装置１２−ｉの識別情報Ｕｉと新たな有効時間区間ＴＦ’に属する時間ｔｉｍｅ’∈ＴＦ’に対応する情報を含む情報Ｖ（ｉ，ｔｉｍｅ’）に対応する秘密鍵ｕｓｋ’ｉを生成し、各秘密鍵ｕｓｋ’ｉを端末装置１２−ｉに安全に配送する。秘密鍵ｕｓｋ’ｉは端末装置１２−ｉ（図２Ｂ）の記憶部１２９−ｉに安全に格納される（ステップＳ１３０）。
【００３４】
鍵配送管理装置１１（図２Ａ）の配送処理部１１１は、新たな第１シード値Ｋ’１を生成し、関数暗号方式に則って新たな第１シード値Ｋ’１を暗号化し、端末装置１２−ｉの識別情報Ｕｉと新たな有効時間区間ＴＦ’に属する時間に対応する情報を含む情報に対応する秘密鍵ｕｓｋ’ｉで復号可能な新たな暗号文ＣＴ”ｉを生成し、新たな暗号文ＣＴ”ｉ（ただし、ｉ∈［１，ｎ］）を出力する。この暗号文ＣＴ”ｉは、秘密鍵ｕｓｋ’ｉに対応する識別情報Ｕｉおよび時間ｔｉｍｅ’が論理式Ｐｉ：＝（ＩＤ＝Ｕｉ）∧（ｔｉｍｅ’∈ＴＦ’）を真にする場合に、当該秘密鍵ｕｓｋ’ｉを用いて復号可能となる暗号文である（ステップＳ１３１）。
【００３５】
暗号文ＣＴ”ｉは通信部１１８に送られ、通信部１１８はこれらを端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）に送信する（ステップＳ１３２）。暗号文ＣＴ”ｉは、各端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）の通信部１２８−ｉに入力され、記憶部１２９−ｉに格納される。各処理部１２１−ｉは、記憶部１２９−ｉから秘密鍵ｕｓｋ’ｉと暗号文ＣＴ”ｉを読み込み、入力された秘密鍵ｕｓｋ’ｉを用い、関数暗号方式に則って、入力された暗号文ＣＴ”ｉを復号して新たな第１シード値Ｋ’１を生成し、新たな第１シード値Ｋ’１を記憶部１２９−ｉに格納する（ステップＳ１３３）。
【００３６】
端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）の処理部１２４−ｉは、記憶部１２９−ｉから新たな第１シード値Ｋ’１および第２シード値Ｋ２を読み込み、Ｋ１：＝Ｋ’１とし、Ｋ１を含む情報とＫ２を含む情報とに対応する共通鍵Ｋ”を生成して出力する（ステップＳ１３４）。
【００３７】
＜端末装置削除処理＞
共通鍵Ｋを共有した端末装置１２−１〜１２−ｎからなるユーザ集合から端末装置１２−ｊを削除し、端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）で新たな共通鍵を共有する処理を説明する。ｉ∈［１，ｎ］＼ｊは、集合［１，ｎ］からｊを除いた補集合を表す。
【００３８】
図５Ｂに例示するように、まず配送処理部１１２は、新たな管理秘密値ｘ”ｓを生成して記憶部１１９に格納する（ステップＳ１３５）。配送処理部１１２は、記憶部１１９から秘匿化共有情報ＳＣｉ（共有情報Ｃが秘匿化された秘匿化共有情報ＳＣｉ）と新たな管理秘密値ｘ”ｓとを読み込み、入力された秘匿化共有情報ＳＣｉと新たな管理秘密値ｘ”ｓとに応じた新たな第２シード値の秘匿化情報ＳＫ”２，ｉを生成し、新たな第２シード値の秘匿化情報ＳＫ”２，ｉを出力する（ただし、ｉ∈［１，ｎ］＼ｊ）。例えば、ｘ”ｓ∈Ｚｐとし、配送処理部１１２は、ＳＫ”２，ｉ：＝ＳＣｉｘ”ｓ＝Ｃ（１／ｘｉ）・ｘ”ｓを生成する。新たな第２シード値の秘匿化情報ＳＫ”２，ｉは通信部１１８に送られ、通信部１１８は新たな第２シード値の秘匿化情報ＳＫ”２，ｉを端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）に送信する（ステップＳ１３６）。
【００３９】
新たな第２シード値の秘匿化情報ＳＫ”２，ｉは、端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）（図２Ｂ）の通信部１２８−ｉに入力され、記憶部１２９−ｉに格納される。各処理部１２３−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）は、記憶部１２９−ｉから新たな第２シード値の秘匿化情報ＳＫ”２，ｉと端末秘密値ｘｉとを読み込み、入力された新たな第２シード値の秘匿化情報ＳＫ”２，ｉと端末秘密値ｘｉとに応じた新たな第２シード値Ｋ”２を生成して出力する。例えば、処理部１２３−ｉは、Ｋ”２：＝ＳＫ”２，ｉｘｉ＝Ｃ（１／ｘｉ）・ｘ”ｓ・ｘｉ＝Ｃｘ”ｓを生成する。第２シード値Ｋ”２は記憶部１２９−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）に格納される（ステップＳ１３７）。
【００４０】
端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）の処理部１２４−ｉは、記憶部１２９−ｉから第１シード値Ｋ１および新たな第２シード値Ｋ”２を読み込み、Ｋ２：＝Ｋ”２とし、Ｋ１を含む情報とＫ２を含む情報とに対応する共通鍵Ｋ”’を生成して出力する（ステップＳ１３８）。
【００４１】
＜本形態の特徴＞
本形態の鍵配送処理では、鍵配送管理装置１１が、関数暗号方式に則って、端末装置１２−ｉの識別情報Ｕｉと有効時間区間ＴＦに属する時間ｔｉｍｅ∈ＴＦに対応する情報を含む情報Ｖ（Ｕｉ，ｔｉｍｅ）に対応する秘密鍵ｕｓｋｉで復号可能なように第１シード値Ｋ１を暗号化し、それによって得られた暗号文ＣＴ’ｉを各端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）に送信する。各端末装置１２−ｉは、安全に格納しておいた秘密鍵ｕｓｋｉを用いて暗号文ＣＴ’ｉを復号して第１シード値Ｋ１を得る。秘密鍵ｕｓｋｉを知らない通信路上の攻撃者は暗号文ＣＴ’ｉを復号できないため第１シード値Ｋ１を得ることができない。これにより、通信路上の成り済ましによる共通鍵Ｋの改ざんを防止できる。また、秘密鍵ｕｓｋｉは有効時間区間ＴＦに属する時間ｔｉｍｅだけではなく、各端末装置１２−ｉの識別情報Ｕｉにも対応するため、他の端末装置に成り済ますことも防止できる。他の端末装置の成り済ましの問題がないのであれば、秘密鍵ｕｓｋｉが有効時間区間ＴＦに属する時間ｔｉｍｅに対応し、識別情報Ｕｉに対応しないものであってもよい。
【００４２】
また、秘密鍵ｕｓｋｉは有効時間区間ＴＦに属する時間で生成された暗号文ＣＴ’ｉのみを復号でき、有効時間区間ＴＦ以外の時間で生成された暗号文を復号できない。そのため、端末装置１２−ｉの紛失等によって秘密鍵ｕｓｋｉが漏洩した場合であっても、有効時間区間を更新することで秘密鍵を無効化できる。
【００４３】
さらに、本形態では鍵配送管理装置１１が端末装置１２−ｉ（ただし、ｉ∈［１，ｎ］）の間の通信を中継する。各端末装置１２−ｉはユニキャストによって鍵配送管理装置１１にデータを送信し、端末装置１２−ｉ同士は直接通信を行わない。ブロードキャストのように計算・通信コストが端末装置数に依存する処理は、鍵配送管理装置１１のみによって行われる。これにより、端末装置数によらず、各端末装置１２−ｉの計算・通信コストを一定にできる。
【００４４】
本形態の共通鍵Ｋは、第１シード値Ｋ１を含む情報と第２シード値Ｋ２を含む情報とに対応する。ここで、第１シード値Ｋ１の配信には比較的計算コストが大きな関数暗号方式を利用する必要があるが、第２シード値Ｋ２の配信には関数暗号方式を用いる必要がない。そのため、有効時間区間ＴＦ内であれば、関数暗号方式を利用することなく共通鍵Ｋを更新できる。例えば、有効時間区間ＴＦ内であれば、関数暗号方式を利用することなく、端末装置追加処理や端末装置削除処理を実行して共通鍵Ｋを更新できる。これにより、できるだけ小さな計算コストで、端末装置追加処理で新たに追加された端末装置が追加前に共有されていた共有鍵を取得することを防止したり、端末装置削除処理で削除された端末装置が取得できない共通鍵へ更新をしたりすることができる。
【００４５】
なお、秘密鍵を格納するデバイスとして例えば参考文献４（Java Card API and Export File for Card Specification v2.2.1 (org. global platform) v1.6, http://www.safenet-inc.jp/data-encryption/hardware-security-modules-hsms/luna-hsms-key-management/luna-sa-network-hsm/）に開示された装置が利用可能である。
【００４６】
その他、鍵配送管理装置１１と端末装置１２−ｈ（ただし、ｈ∈［１，Ｎ］）との通信時に、送信側の装置が一般的な存在的偽造不可能性を満たす電子署名を生成して送信情報に添付し、受信側の装置が電子署名の検証を行い、検証に成功した場合にのみ処理を継続してもよい。これにより、通信路上での改ざんに対する耐性が向上する。存在的偽造不可能性を満たす電子署名は、例えば、参考文献５（Mihir Bellare, Phillip Rogaway: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. ACM Conference on Computer and Communications Security 1993: 62-73）に開示されている。
【００４７】
［第２実施形態］
次に、本発明の第２実施形態を説明する。なお、第１実施形態と共通する事項については第１実施形態と同じ参照記号を用い、説明を省略する。
＜準備＞
ある集合Ｓｅｔについて、Ｓｅｔから要素ωをランダムに選ぶことをω∈ＲＳｅｔと表記する。あるアルゴリズムＡＬＧについて、入力ｘと乱数ｒ（確定的アルゴリズムの場合は、乱数は空）に対してＡＬＧがｙを出力することをｙ←ＡＬＧ（ｘ；ｒ）またはＡＬＧ（ｘ；ｒ）→ｙと表記する。「｜Φ｜」は値Φのビット長を表す。集合Ｘ＝｛ｘ１，・・・，ｘｎ｝についてｇｘ１・ｘ２・...・ｘｎをｇΠＸと表記する。Ｘが空集合の場合にはΠＸ＝１となる。ただし、Ｇを位数ｐの乗法巡回群とし、ｇ∈Ｇを群Ｇの生成元とする。
【００４８】
Ｆ＝｛Ｆκ：Ｄｏｍκ×ＦＳκ→Ｒｎｇκ｝κを、セキュリティパラメータκ上で定められた定義域｛Ｄｏｍκ｝κ、鍵空間｛ＦＳκ｝κ、値域｛Ｒｎｇκ｝κを持つ関数族とする。この時、もし多項式時間の識別者Ｄに対して、Ｆκと真性ランダム関数ＲＦκ：Ｄｏｍκ→Ｒｎｇκが見分けられなければ、Ｆ＝｛Ｆκ｝κを擬似ランダム関数族と呼ぶ。
【００４９】
公開鍵暗号アルゴリズムを（ＥＧｅｎ，Ｅｎｃ，Ｄｅｃ）とする。鍵生成アルゴリズムＥＧｅｎはκを入力とし、暗号化鍵ｅｋと復号鍵ｄｋを出力する。暗号化アルゴリズムＥｎｃは暗号化鍵ｅｋと平文ｍを入力とし、暗号文ＣＴを出力する。復号アルゴリズムＤｅｃは復号鍵ｄｋと暗号文ＣＴを入力とし、平文ｍを出力する。
【００５０】
電子署名アルゴリズムを（ＳＧｅｎ，Ｓｉｇｎ，Ｖｅｒ）とする。鍵生成アルゴリズムＳＧｅｎはκを入力とし、検証鍵ｖｋと署名鍵ｓｋを出力する。署名生成アルゴリズムＳｉｇｎは署名鍵ｓｋと文書Ｍを入力とし、署名σを出力する。署名検証アルゴリズムＶｅｒは検証鍵ｖｋ、文書Ｍと署名σを入力とし、検証結果（検証成功／検証失敗）を出力する。
【００５１】
関数暗号アルゴリズムを（Ｓｅｔｕｐ，Ｄｅｒ，ＦＥｎｃ，ＦＤｅｃ）とする。セットアップアルゴリズムＳｅｔｕｐはκを入力とし、マスタ秘密鍵ｍｓｋと公開パラメータＰａｒａｍｓを出力する。鍵導出アルゴリズムＤｅｒは公開パラメータＰａｒａｍｓ、マスタ秘密鍵ｍｓｋと属性情報Ｖを入力とし、秘密鍵ｕｓｋを出力する。暗号化アルゴリズムＦＥｎｃは公開パラメータＰａｒａｍｓ、論理式Ｐに対応するアクセス構造と平文ｍを入力とし、暗号文ＣＴを出力する。復号アルゴリズムＦＤｅｃはユーザ秘密鍵ｕｓｋと暗号文ＣＴを入力とし、属性情報Ｖが論理式Ｐを真にする（論理式Ｐに対応するアクセス構造が属性情報を受け入れる）ならば平文ｍを出力する。
【００５２】
関数ｔＰＲＦ：｛０,１｝κ×ＦＳκ×｛０,１｝κ×ＦＳκ→Ｚｐを「ねじれ擬似ランダム関数（例えば「Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa, Kazuki Yoneyama: Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices. IACR Cryptology ePrint Archive 2012: 211 (2012)，http://eprint.iacr.org/2012/211」等参照）と呼び、擬似ランダム関数Ｆκを用いてｔＰＲＦ（ａ，ｂ，ａ’，ｂ’）：＝Ｆκ（ａ，b）（＋）Ｆκ（ａ’，ｂ’）と定義する。ただし、ａ，ａ’∈｛０,１｝κであり、ｂ’，ｂ’∈ＦＳκである。｛０，１｝κはκビット列を表し、「α（＋）β」はαとβとの排他的論理和を表す。
【００５３】
＜構成＞
図１に例示するように、本形態の鍵配送システム２は、端末装置２２−１〜２２−Ｎと鍵配送管理装置２１とを有する。ただし、Ｎは３以上の整数である。端末装置２２−１〜２２−Ｎと鍵配送管理装置２１とはインターネット等の安全ではない通信路を通じて通信可能に構成されている。
【００５４】
図６に例示するように、本形態の鍵配送管理装置２１は、制御部２１０と秘密鍵生成部２１０１と秘密鍵暗号化部２１０２と署名生成部２１０３と署名検証部２１０４と第１シード値生成部２１１１（第１，６配送処理部）と第１シード値暗号化部２１１２（第１，６配送処理部）と管理秘密値生成部２１２１（第２〜５配送処理部）と第２シード値秘匿化情報生成部２１２２（第２〜５配送処理部）と通信部２１８と記憶部２１９とを有する。
【００５５】
図７に例示するように、本形態の端末装置２２−ｈは、制御部２２０−ｈと秘密鍵復号部２２０１−ｈと端末秘密値生成部２２０２−ｈと公開情報生成部２２０３−ｈと署名生成部２２０４−ｈと署名検証部２２０５−ｈと第１シード値復号部２２１−ｈ（第１処理部）と秘匿化共有情報生成部２２２−ｈ（第２，６処理部）と第２シード値生成部２２３−ｈ（第３，５，７処理部）と共通鍵生成部２２４−ｈ（第４処理部）と通信部２２８−ｈと記憶部２２９−ｈとを有する。ただし、ｈ∈［１，Ｎ］である。
【００５６】
各装置は、例えば、上述のようなコンピュータが所定のプログラムを実行することで構成される装置であってもよいし、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、各装置は自らが備える制御部２１０，２２０−ｈの制御に基づいて各処理を実行する。各装置の各処理で得られたデータは、逐一、それぞれが備える記憶部２１９，２２９−ｈに格納され、必要に応じて読み出されて使用される。
【００５７】
＜システムセットアップ＞
鍵配送管理装置２１（図６）の制御部２１０は、関数暗号のセットアップアルゴリズムＳｅｔｕｐにより、公開パラメータＰａｒａｍｓとマスタ秘密鍵ｍｓｋを生成する。また制御部２１０は、公開鍵暗号の鍵生成アルゴリズムＥＧｅｎにより、暗号化鍵ｅｋｓと復号鍵ｄｋｓを生成し、電子署名の鍵生成アルゴリズムＳＧｅｎにより、検証鍵ｖｋｓと署名鍵ｓｋｓを生成する。各端末装置２２−ｈ（図７）の制御部２２０−ｈは、公開鍵暗号の鍵生成アルゴリズムＥＧｅｎにより、暗号化鍵ｅｋｈと復号鍵ｄｋｈを生成し、電子署名の鍵生成アルゴリズムＳＧｅｎにより、検証鍵ｖｋｈと署名鍵ｓｋｈを生成する。また制御部２２０−ｈは、秘密ストリング（ｓｔｈ，ｓｔ’ｈ）をそれぞれｓｔｈ∈ＦＳκ、ｓｔ’ｈ∈｛０，１｝κとして生成する。また、鍵配送管理装置２１の識別情報Ｓおよび各端末装置２２−ｈの識別情報Ｕｈが設定される。
【００５８】
Ｓ、Ｕ１，・・・，ＵＮ、Ｐａｒａｍｓは、鍵配送管理装置２１の記憶部２１９および各端末装置２２−ｈの記憶部２２９−ｈ（ただし、ｈ∈［１，Ｎ］）に格納される。鍵配送管理装置２１の記憶部２１９には、さらにｍｓｋ、ｓｋｓ、ｅｋ１，・・・，ｅｋＮ、ｖｋ１，・・・，ｖｋＮが格納される。各端末装置２２−ｈの記憶部２２９−ｈには、さらにｄｋｈ、ｓｋｈ、ｓｔｈ、ｓｔ’ｈ、ｅｋｓ、ｖｋｓが格納される。
【００５９】
＜鍵配送処理＞
以下、端末装置２２−１〜２２−Ｎからなる集合の部分集合（ユーザ集合）である端末装置２２−σ（１）〜２２−σ（ｎ）がセッションを立ち上げ、共通鍵を共有する処理を説明する。ただし、ｎは２以上Ｎ以下の整数であり、｛σ（１），・・・，σ（ｎ）｝⊂｛１，・・・，Ｎ｝であるとする。以降、記述を簡単にするために、一般性を失うことなく（σ（１），・・・，σ（ｎ））＝（１，・・・，ｎ）と仮定することにする。セッションには、固有のセッション識別情報ｓｉｄが付され、ｓｉｄは鍵配送管理装置２１の記憶部２１９および各端末装置２２−ｉの記憶部２２９−ｉ（ただし、ｉ∈［１，ｎ］）に格納される。セッション識別情報ｓｉｄは例えば、鍵配送管理装置２１によって付される。
【００６０】
≪関数暗号方式に則った秘密鍵の配送≫
そのセッションが有効時間区間（タイムフレーム）ＴＦにおける最初のセッションであった場合、関数暗号方式に則った秘密鍵の配送が行われる。この場合、図８に例示するように、まず鍵配送管理装置２１（図６）の秘密鍵生成部２１０１が、記憶部２１９からＰａｒａｍｓ、ｍｓｋを読み込み、関数暗号方式に則り、端末装置２２−ｉの識別情報Ｕｉと有効時間区間ＴＦに属する時間ｔｉｍｅ∈ＴＦに対応する情報を含む属性情報Ｖｉ：＝Ｖ（Ｕｉ，ｔｉｍｅ）に対応する秘密鍵ｕｓｋｉ：＝Ｄｅｒ（Ｐａｒａｍｓ，ｍｓｋ，Ｖｉ）（ただし、ｉ∈［１，ｎ］）を生成して出力する。秘密鍵ｕｓｋｉは記憶部２１９に格納される（ステップＳ２０１１）。秘密鍵暗号化部２１０２は、記憶部２１９から秘密鍵ｕｓｋｉおよび暗号化鍵ｅｋｉを読み込み、暗号化鍵ｅｋｉを用いて秘密鍵ｕｓｋｉを暗号化し、暗号文ＣＴｉ←Ｅｎｃｅｋｉ（ｕｓｋｉ）を生成して出力する。ただし、下付き添え字の「ｅｋｉ」は「ｅｋｉ」を表す（ステップＳ２０１２）。暗号文ＣＴｉ（ただし、ｉ∈［１，ｎ］）は通信部２１８に送られ、通信部２１８は暗号文ＣＴｉを端末装置２２−ｉに送信する。各暗号文ＣＴｉは端末装置２２−ｉ（図７）の通信部２２８−ｉに入力され、記憶部２２９−ｉに格納される（ステップＳ２０１３）。秘密鍵復号部２２０１−ｉは、記憶部２２９−ｉから復号鍵ｄｋｉおよび暗号文ＣＴｉを読み込み、復号鍵ｄｋｉを用いて暗号文ＣＴｉを復号して秘密鍵ｕｓｋｉ←Ｄｅｃｄｋｉ（ＣＴｉ）を生成して出力する。ただし、下付き添え字の「ｄｋｉ」は「ｄｋｉ」を表す。秘密鍵ｕｓｋｉは、端末装置２２−ｉの記憶部２２９−ｉに安全に格納される（ステップＳ２０１４）。なお、セッションが有効時間区間ＴＦにおける最初のセッションでない場合には、ステップＳ２０１１からＳ２０１４の処理が省略されてもよい。
【００６１】
≪共有情報の生成≫
次に、鍵配送管理装置２１および端末装置２２−１〜２２−ｎが協力して共有情報Ｃ＝ｇΠ｛ｘｉ｜ｉ∈［１，ｎ］｝を生成する。図９に例示するように、まず端末装置２２−１（図７）の端末秘密値生成部２２０２−１は、記憶部２２９−１からｓｔ１とｓｔ’１を読み込み、ｒ１∈Ｒ｛０，１｝κとｒ’１∈ＲＦＳκを生成し、端末秘密値ｘ１←ｔＰＲＦ（ｒ１，ｓｔ１，ｓｔ’１，ｒ’１）を生成して出力する。端末秘密値ｘ１は記憶部２２９−１に格納される（ステップＳ２０２２−１）。
【００６２】
公開情報生成部２２０３−１は、記憶部２２９−１から端末秘密値ｘ１を読み込んでｇｘ１∈Ｇを生成する。署名生成部２２０３−１は、記憶部２２９−１から署名鍵ｓｋ１および識別情報Ｓ，Ｕ１，・・・，Ｕｎを読み込み、署名σ１←Ｓｉｇｓｋ１（Ｕ１，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇ，ｇｘ１）を生成する。（Ｕ１，ｇｘ１，σ１）は通信部２２８−１に送られ、通信部２２８−１は（Ｕ１，ｇｘ１，σ１）を鍵配送管理装置２１に送信する（ステップＳ２０２３−１）。
【００６３】
その後、ｗ∈［１，ｎ−１］について、鍵配送管理装置２１と端末装置２２−ｉとの間で次のように通信を行う。ただし、ｗ∈［１，ｎ−１］の範囲では、実行する順序が前後してもかまわない。
端末装置２２−ｉから送信された（Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ］｝，σｉ）は、鍵配送管理装置２１（図６）の通信部２１８に入力され、記憶部２１９に格納される。署名検証部２１０４は、記憶部２１９から検証鍵ｖｋｉおよび署名σｉを読み込み、検証鍵ｖｋｉを用い、署名σｉをＶｅｒｖｋｉ（（Ｕｉ，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ−１］｝，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ］｝），σｉ）として検証する。ただし、ｉ＝１でのｇΠ｛ｘｋ｜ｋ∈［１，ｉ−１］｝は公開情報ｇΠ｛ｘｋ｜ｋ∈［１，０］｝：＝ｇであり、ｉ∈［２，ｎ−１］でのｇΠ｛ｘｋ｜ｋ∈［１，ｉ−１］｝は既に端末装置２２−（ｉ−１）から受け取っているものとする（ステップＳ２０２４−ｉ）。ここで、署名σｉが正当でない（検証失敗）と判断された場合、セッションを終了する。一方、署名σｉが正当である（検証成功）と判断された場合、（Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ］｝）が通信部２１８に送られ、通信部２１８は（Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ］｝）を端末装置２２−（ｉ＋１）に送信する（ステップＳ２０２１−（ｉ＋１））。（Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ］｝）は、端末装置２２−（ｉ＋１）（図７）の通信部２２８−（ｉ＋１）に入力され、記憶部２２９−（ｉ＋１）に格納される。端末装置２２−（ｉ＋１）の端末秘密値生成部２２０２−（ｉ＋１）は、記憶部２２９−（ｉ＋１）からｓｔｉ＋１とｓｔ’ｉ＋１を読み込み、ｒｉ＋１∈Ｒ｛０，１｝κとｒ’ｉ＋１∈ＲＦＳκを生成し、端末秘密値ｘｉ＋１←ｔＰＲＦ（ｒｉ＋１，ｓｔｉ＋１，ｓｔ’ｉ＋１，ｒ’ｉ＋１）を生成して出力する。端末秘密値ｘｉ＋１は記憶部２２９−（ｉ＋１）に格納される（ステップＳ２０２２−（ｉ＋１））。公開情報生成部２２０３−（ｉ＋１）は、記憶部２２９−（ｉ＋１）から端末秘密値ｘｉ＋１およびｇΠ｛ｘｋ｜ｋ∈［１，ｉ］｝を読み込み、ｇΠ｛ｘｋ｜ｋ∈［１，ｉ＋１］｝：＝ｇΠ｛ｘｋ｜ｋ∈［１，ｉ］｝・ｘｉ＋１∈Ｇを生成する。ｇΠ｛ｘｋ｜ｋ∈［１，ｉ＋１］｝は記憶部２２９−（ｉ＋１）に格納される。署名生成部２２０４−（ｉ＋１）は、記憶部２２９−（ｉ＋１）から署名鍵ｓｋｉ＋１および識別情報Ｓ，Ｕ１，・・・，Ｕｎを読み込み、署名σｉ＋１←Ｓｉｇｓｋｉ＋１（Ｕｉ＋１，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ］｝，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ＋１］｝）を生成する。ただし、下付き添え字の「ｓｋｉ＋１」は「ｓｋｉ＋１」を表す。（Ｕｉ＋１，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ＋１］｝，σｉ＋１）は通信部２２８−（ｉ＋１）に送られ、通信部２２８−（ｉ＋１）は（Ｕｉ＋１，ｇΠ｛ｘｋ｜ｋ∈［１，ｉ＋１］｝，σｉ＋１）を鍵配送管理装置２１に送信する（ステップＳ２０２３−（ｉ＋１））。
【００６４】
上記の処理の結果、最後のステップＳ２０２３−ｎでは、共有情報Ｃ＝ｇΠ｛ｘｉ｜ｉ∈［１，ｎ］｝＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝を含む（Ｕｎ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝，σｎ）が鍵配送管理装置２１に送信される。（Ｕｎ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝，σｎ）は、鍵配送管理装置２１（図６）の通信部２１８に入力され、記憶部２１９に格納される。署名検証部２１０４は、記憶部２１９から検証鍵ｖｋｎ、識別情報Ｕ１，・・・，Ｕｎ，Ｓ、および署名σｎを読み込み、検証鍵ｖｋｎを用い、署名σｎをＶｅｒｖｋｉ（（Ｕｎ，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ−１］｝，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝），σｉ）として検証する（ステップＳ２０２４−ｎ）。ここで、署名σｎが正当でないと判断された場合、セッションを終了する。一方、署名σｎが正当であると判断された場合、シード値の共有処理に移る。
【００６５】
≪シード値の共有処理≫
図１０に例示するように、シード値の共有処理では、まず鍵配送管理装置２１（図６）の第１シード値生成部２１１１が第１シード値Ｋ１∈ＲＦＳκを生成し、記憶部２１９に格納する（ステップＳ２０３１）。次に、第１シード値暗号化部２１１２が記憶部２１９からＰａｒａｍｓおよび第１シード値Ｋ１を読み込み、関数暗号方式に則って第１シード値Ｋ１を暗号化し、端末装置２２−ｉの識別情報Ｕｉと有効時間区間ＴＦに属する時間ｔｉｍｅに対応する情報を含む属性情報Ｐｉ：＝（ＩＤ＝Ｕｉ）∧（ｔｉｍｅ∈ＴＦ）に対応する秘密鍵で復号可能な暗号文ＣＴ’ｉ←ＦＥｎｃ（Ｐａｒａｍｓ，Ｐｉ，Ｋ１）を生成して記憶部２１９に格納する（ステップＳ２０３２）。署名生成部２１０３は、記憶部２１９から署名鍵ｓｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ、共有情報Ｃ＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝、暗号文ＣＴ’ｗを読み込み、ｗ∈［１，ｎ−１］について署名σｓｗ←Ｓｉｇｓｋｓ（Ｓ，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝，ＣＴ’ｗ）を生成する。また、ｎについて署名σｓｎ←Ｓｉｇｓｋｓ（Ｓ，（Ｕ１，・・・，Ｕｎ），Ｓ，ＣＴ’ｎ）を生成する。ｗ∈［１，ｎ−１］について（Ｕｗ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝，ＣＴ’ｗ，σｓｗ）が通信部２１８に送られ、通信部２１８は（Ｕｗ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝，ＣＴ’ｗ，σｓｗ）を端末装置２２−ｗに送信する。（Ｕｗ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝，ＣＴ’ｗ，σｓｗ）は端末装置２２−ｗの通信部２２８−ｗに入力され、記憶部２２９−ｗに格納される。ｎについて（Ｕｎ，ＣＴ’ｎ，σｓｎ）が通信部２１８に送られ、通信部２１８は（Ｕｎ，ＣＴ’ｎ，σｓｎ）を端末装置２２−ｎに送信する。（Ｕｎ，ＣＴ’ｎ，σｓｎ）は端末装置２２−ｎの通信部２２８−ｎに入力され、記憶部２２９−ｎに格納される。なお、記憶部２２９−ｎには、前述のステップＳ２０２３−ｎの過程で既にｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝が格納されている（ステップＳ２０３１）。
【００６６】
端末装置２２−ｗ（ただし、ｗ∈［１，ｎ−１］）の署名検証部２２０５−ｗは、記憶部２２９−ｗから検証鍵ｖｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ、共有情報Ｃ＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝、暗号文ＣＴ’ｗ、および署名σｓｗを読み込み、検証鍵ｖｋｓを用い、署名σｓｗをＶｅｒｖｋｓ（（Ｓ，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝，ＣＴ’ｗ），σｓｗ）として検証する（ステップＳ２０５１−ｗ）。ここで、署名σｓｗが正当でないと判断された場合、セッションを終了する。一方、署名σｓｗが正当であると判断された場合、ステップＳ２０５２−ｗの処理に進む。端末装置２２−ｎの署名検証部２２０５−ｎは、記憶部から検証鍵ｖｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ、暗号文ＣＴ’ｎを読み込み、検証鍵ｖｋｓを用い、署名σｓｉをＶｅｒｖｋｓ（（Ｓ，（Ｕ１，・・・，Ｕｎ），Ｓ，ＣＴ’ｎ），σｓｎ）として検証する（ステップＳ２０５１−ｎ）。ここで、署名σｓｎが正当でないと判断された場合、セッションを終了する。一方、署名σｓｎが正当であると判断された場合、ステップＳ２０５２−ｎの処理に進む。
【００６７】
ステップＳ２０５２−ｉ（ただし、ｉ∈［１，ｎ］）では、端末装置２２−ｉ（図７）の第１シード値復号部２２１−ｉが、記憶部２２９−ｉから秘密鍵ｕｓｋｉおよび暗号文ＣＴ’ｉを読み込み、秘密鍵ｕｓｋｉを用い、関数暗号方式に則って暗号文ＣＴ’ｉをＫ１←ＦＤｅｃｕｓｋｉ（ＣＴ’ｉ，Ｐｉ）として復号して第１シード値Ｋ１を生成して出力する。第１シード値Ｋ１は記憶部２２９−ｉに格納される（ステップＳ２０５２−ｉ）。
【００６８】
次に、秘匿化共有情報生成部２２２−ｉ（ただし、ｉ∈［１，ｎ］）は、記憶部２２９−ｉから共有情報Ｃ＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝および端末秘密値ｘｉを読み込み、共有情報Ｃと端末秘密値の逆元１／ｘｉとに応じた秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝：＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝／ｘｉを生成して出力する。秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝は記憶部２２９−ｉに格納される（ステップＳ２０６−ｉ）。
【００６９】
署名生成部２２０４−ｉは、記憶部２２９−ｉから、署名鍵ｓｋｉ、識別情報Ｓ，Ｕ１，・・・，Ｕｎ、秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝を読み込み、署名σ’ｉ←Ｓｉｇｓｋｉ（Ｕｉ，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝）を生成する。（Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝，σ’ｉ）は通信部２２８−ｉに送られ、通信部２２８−ｉは（Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝，σ’ｉ）を鍵配送管理装置２１に送信する（ステップＳ２０７−ｉ）。
【００７０】
図１１に例示するように、各端末装置２２−ｉ（ただし、ｉ∈［１，ｎ］）から送信された（Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝，σ’ｉ）は、鍵配送管理装置２１の通信部２１８に入力され、記憶部２１９に格納される。署名検証部２１０４は、記憶部２１９から検証鍵ｖｋｉ、識別情報Ｕ１，・・・，Ｕｎ，Ｓ、秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝、および署名σ’ｉを読み込み、検証鍵ｖｋｉを用い、署名σ’ｉをＶｅｒｖｋｉ（（Ｕｉ，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝），σ’ｉ）として検証する（ステップＳ２０８１）。ここで、何れかの署名σ’ｉが正当でないと判断された場合、セッションを終了する。一方、すべての署名σ’ｉが正当であると判断された場合、管理秘密値生成部２１２１が管理秘密値ｘｓ∈ＲＺｐを生成して記憶部２１９に格納する（ステップＳ２０８２）。第２シード値秘匿化共有情報部２１２２は、記憶部２１９から秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝および管理秘密値ｘｓを読み込み、秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝と管理秘密値ｘｓとに応じた第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓ（ただし、ｉ∈［１，ｎ］）を生成する。第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓは記憶部２１９に格納される（ステップＳ２０９１）。署名生成部２１０３は、記憶部２１９から署名鍵ｓｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ、および第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓを読み込み、ｉ∈［１，ｎ］について署名σ’ｓｉ←Ｓｉｇｓｋｓ（Ｓ，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓ）を生成する。(Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓ，σ’ｓｉ)は通信部２１８に送られ、通信部２１８は、(Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓ，σ’ｓｉ)を端末装置２２−ｉに送信する。(Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓ，σ’ｓｉ)は、端末装置２２−ｉ（図７）の通信部２２８−ｉに入力され、記憶部２２９−ｉに格納される（ステップＳ２０９２）。
【００７１】
端末装置２２−ｉ（ただし、ｉ∈［１，ｎ］）の署名検証部２２０５−ｉは、記憶部２２９−ｉから検証鍵ｖｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ、ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓ、および署名σ’ｓｉを読み込み、検証鍵ｖｋｓを用い、署名σ’ｓｉをＶｅｒｖｋｓ（（Ｓ，（Ｕ１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓ），σ’ｓｉ）として検証する（ステップＳ２１０１−ｉ）。ここで、署名σ’ｓｉが正当でないと判断された場合、セッションを終了する。一方、署名σ’ｓｉが正当であると判断された場合、第２シード値生成部２２３−ｉが、記憶部２２９−ｉから第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓおよび端末秘密値ｘｉを読み込み、第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓと端末秘密値ｘｉとに応じた第２シード値Ｋ２：＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｓ・ｘｉ＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘｓを生成して出力する。第２シード値Ｋ２は記憶部２２９−ｉに格納される（ステップＳ２１０２−ｉ）。
【００７２】
共通鍵生成部２２４−ｉ（ただし、ｉ∈［１，ｎ］）は、記憶部２２９−ｉから、セッション識別情報ｓｉｄ、第１シード値Ｋ１、および第２シード値Ｋ２を読み込み、擬似ランダム関数Ｆκを用い、第１シード値Ｋ１を含む情報と第２シード値Ｋ２を含む情報とに対応する共通鍵Ｋ＝Ｆκ（ｓｉｄ，Ｋ１）（＋）Ｆκ（ｓｉｄ，Ｋ２）を生成して出力する。このように生成された共通鍵Ｋは、第１シード値Ｋ１に関する情報および第２シード値Ｋ２に関する情報が隠蔽された情報となる（ステップＳ２１１）。
【００７３】
＜端末装置追加処理＞
端末装置２２−１〜２２−ｎにより既に確立されたセッションに、新たな端末装置２２−（ｎ＋１）を追加し、共通鍵Ｋを更新する処理を説明する。本形態でも、一般性を失うことなく、新たな端末装置を端末装置２２−（ｎ＋１）とすることができる。
【００７４】
上述した確立されたセッションでの有効時間区間が終了し、端末装置２２−１〜２２−ｎにとって新たな有効時間区間ＴＦでセッションを行うことになる場合、前述した関数暗号方式に則った秘密鍵ｕｓｋｉ（ただし、ｉ∈［１，ｎ］）の配送が行われる（図８：ステップＳ２０１１〜Ｓ２０１４）。この処理は既に説明したため、ここでの説明を省略する。
【００７５】
同様に、新たな端末装置２２−（ｎ＋１）にとって新たな有効時間区間ＴＦでセッションを行うことになる場合、端末装置２２−（ｎ＋１）に対し、関数暗号方式に則った秘密鍵の配送ｕｓｋｎ＋１が行われる。この場合、図１２に例示するように、まず鍵配送管理装置２１（図６）の秘密鍵生成部２１０１が、記憶部２１９からＰａｒａｍｓ、ｍｓｋを読み込み、関数暗号方式に則り、端末装置２２−ｉの識別情報Ｕｎ＋１と有効時間区間ＴＦに属する時間ｔｉｍｅ∈ＴＦに対応する情報を含む属性情報Ｖｉ：＝Ｖ（Ｕｎ＋１，ｔｉｍｅ）に対応する秘密鍵ｕｓｋｎ＋１：＝Ｄｅｒ（Ｐａｒａｍｓ，ｍｓｋ，Ｖｎ＋１）を生成して出力する。秘密鍵ｕｓｋｎ＋１は記憶部２１９に格納される（ステップＳ２０１５）。秘密鍵暗号化部２１０２は、記憶部２１９から秘密鍵ｕｓｋｎ＋１および暗号化鍵ｅｋｎ＋１を読み込み、暗号化鍵ｅｋｎ＋１を用いて秘密鍵ｕｓｋｎ＋１を暗号化し、暗号文ＣＴｎ＋１←Ｅｎｃｅｋｎ＋１（ｕｓｋｎ＋１）を生成して出力する。ただし、下付き添え字の「ｅｋｎ＋１」は「ｅｋｎ＋１」を表す（ステップＳ２０１６）。暗号文ＣＴｎ＋１は通信部２１８に送られ、通信部２１８は暗号文ＣＴｎ＋１を端末装置２２−（ｎ＋１）に送信する。暗号文ＣＴｎ＋１は端末装置２２−（ｎ＋１）（図７）の通信部２２８−（ｎ＋１）に入力され、記憶部２２９−（ｎ＋１）に格納される（ステップＳ２０１７）。秘密鍵復号部２２０１−（ｎ＋１）は、記憶部２２９−（ｎ＋１）から復号鍵ｄｋｎ＋１および暗号文ＣＴｎ＋１を読み込み、復号鍵ｄｋｎ＋１を用いて暗号文ＣＴｎ＋１を復号して秘密鍵ｕｓｋｎ＋１←Ｄｅｃｄｋｎ＋１（ＣＴｎ＋１）を生成して出力する。ただし、下付き添え字の「ｄｋｉ＋１」は「ｄｋｎ＋１」を表す。秘密鍵ｕｓｋｎ＋１は、端末装置２２−（ｎ＋１）の記憶部２２９−（ｎ＋１）に安全に格納される（ステップＳ２０１８）。なお、端末装置２２−（ｎ＋１）にとって新たな有効時間区間ＴＦでセッションを行うことにならない場合には、ステップＳ２０１５からＳ２０１７の処理が省略されてもよい。
【００７６】
新たな有効時間区間ＴＦでセッションを行うことになる場合、鍵配送管理装置２１（図６）の第１シード値生成部２１１１が新たな第１シード値Ｋ’１∈ＲＦＳκを生成し、Ｋ１：＝Ｋ’１として記憶部２１９に格納し（ステップＳ２０１６）、ステップＳ２１３３に進む。そうでない場合、ステップＳ２０１６を行うことなく、ステップＳ２１３３に進む。
【００７７】
ステップＳ２１３３では、第１シード値暗号化部２１１２が記憶部２１９からＰａｒａｍｓおよび第１シード値Ｋ１を読み込み、関数暗号方式に則って第１シード値Ｋ１を暗号化し、端末装置の識別情報Ｕｎ＋１と有効時間区間ＴＦに属する時間ｔｉｍｅに対応する情報を含む属性情報Ｐｎ＋１：＝（ＩＤ＝Ｕｎ＋１）∧（ｔｉｍｅ∈ＴＦ）に対応する秘密鍵で復号可能な暗号文ＣＴ’ｎ＋１←ＦＥｎｃ（Ｐａｒａｍｓ，Ｐｎ＋１，Ｋ１）を生成して記憶部２１９に格納する（ステップＳ２１３３）。管理秘密値生成部２１２１が新たな管理秘密値ｘ’ｓ∈ＲＺｐを生成して記憶部２１９に格納する（ステップＳ２１４１）。第２シード値秘匿化共有情報部２１２２は、記憶部２１９から共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝および新たな管理秘密値ｘ’ｓを読み込み、共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝と新たな管理秘密値ｘ’ｓとに応じた新たな共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓを生成して出力する。新たな共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓは記憶部２１１に格納される（ステップＳ２１４２）。署名生成部２１０３は、記憶部２１９から、署名鍵ｓｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ＋１、新たな共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓ、秘匿化共有情報｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］、および暗号文ＣＴ’ｎ＋１を読み込み、署名σｓｎ＋１←Ｓｉｇｓｋｓ（Ｓ，（Ｕ１，・・・，Ｕｎ＋１），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓ，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］，ＣＴ’ｎ＋１）を生成する。(Ｕｎ＋１，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓ，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］，ＣＴ’ｎ＋１，σｓｎ＋１)は通信部２１８に送られ、通信部２１８は、(Ｕｎ＋１，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓ，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］，ＣＴ’ｎ＋１，σｓｎ＋１)を端末装置２２−（ｎ＋１）に送信する。(Ｕｎ＋１，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓ，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］，ＣＴ’ｎ＋１，σｓｎ＋１)は、端末装置２２−（ｎ＋１）（図７）の通信部２２８−（ｎ＋１）に入力され、記憶部２２９−（ｎ＋１）に格納される（ステップＳ２１５）。
【００７８】
端末装置２２−（ｎ＋１）の署名検証部２２０５−（ｎ＋１）は、記憶部２２９−（ｎ＋１）から検証鍵ｖｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ＋１、ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓ，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］、暗号文ＣＴ’ｎ＋１、および署名σｓｎ＋１を読み込み、検証鍵ｖｋｓを用い、署名σｓｎ＋１をＶｅｒｖｋｓ（（Ｓ，（Ｕ１，・・・，Ｕｎ＋１），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓ，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］，ＣＴ’ｎ＋１），σｓｎ＋１）として検証する（ステップＳ２１６１）。ここで、署名σｓｎ＋１が正当でないと判断された場合、セッションを終了する。一方、署名σｓｎ＋１が正当であると判断された場合、端末装置２２−ｉ（図７）の第１シード値復号部２２１−（ｎ＋１）が、記憶部２２９−（ｎ＋１）から秘密鍵ｕｓｋｎ＋１および暗号文ＣＴ’ｎ＋１を読み込み、秘密鍵ｕｓｋｎ＋１を用い、関数暗号方式に則って暗号文ＣＴ’ｎ＋１をＫ１←ＦＤｅｃｕｓｋｎ＋１（ＣＴ’ｎ＋１，Ｐｎ＋１）として復号して第１シード値Ｋ１を生成して出力する。第１シード値Ｋ１は記憶部２２９−（ｎ＋１）に格納される（ステップ２１６２）。
【００７９】
端末秘密値生成部２２０２−（ｎ＋１）は、記憶部２２９−（ｎ＋１）からｓｔｎ＋１とｓｔ’ｎ＋１を読み込み、ｒｎ＋１∈Ｒ｛０，１｝κとｒ’ｎ＋１∈ＲＦＳκを生成し、端末秘密値ｘｎ＋１←ｔＰＲＦ（ｒｎ＋１，ｓｔｎ＋１，ｓｔ’ｎ＋１，ｒ’ｎ＋１）を生成して出力する。端末秘密値ｘｎ＋１は記憶部２２９−（ｎ＋１）に格納される（ステップＳ２１７１）。秘匿化共有情報生成部２２２−（ｎ＋１）は、記憶部２２９−（ｎ＋１）から秘匿化共有情報｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］と端末秘密値ｘｎ＋１とを読み込み、ｉ∈［１，ｎ］について、秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝と端末秘密値ｘｎ＋１とに応じた新たな秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝：＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘｎ＋１を生成して出力する。新たな秘匿化共有情報｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］は記憶部２２−（ｎ＋１）に格納される（ステップＳ２１７２）。
【００８０】
署名生成部２２０４−（ｎ＋１）は、記憶部２２９−（ｎ＋１）から、署名鍵ｓｋｎ＋１、識別情報Ｓ，Ｕ１，・・・，Ｕｎ＋１、新たな秘匿化共有情報｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］を読み込み、署名σｎ＋１←Ｓｉｇｓｋｎ＋１（Ｕｎ＋１，（Ｕ１，・・・，Ｕｎ＋１），Ｓ，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］）を生成する。（Ｕｎ＋１，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］，σｎ＋１）は通信部２２８−（ｎ＋１）に送られ、通信部２２８−（ｎ＋１）は（Ｕｎ＋１，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］，σｎ＋１）を鍵配送管理装置２１に送信する（ステップＳ２１８）。
【００８１】
第２シード値生成部２２３−（ｎ＋１）は、記憶部２２９−（ｎ＋１）から新たな共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓおよび端末秘密値ｘｎ＋１を読み込み、新たな共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓと端末秘密値ｘｎ＋１とに応じた新たな第２シード値Ｋ’２：＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ’ｓ・ｘｎ＋１＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］｝・ｘ’ｓを生成して出力する。新たな第２シード値Ｋ’２は記憶部２２９−（ｎ＋１）に格納される（ステップＳ２１９）。共通鍵生成部２２４−（ｎ＋１）は、記憶部２２９−（ｎ＋１）から、セッション識別情報ｓｉｄ、第１シード値Ｋ１、および新たな第２シード値Ｋ’２を読み込み、擬似ランダム関数Ｆκを用い、第１シード値Ｋ１を含む情報と新たな第２シード値Ｋ’２を含む情報とに対応する共通鍵Ｋ’＝Ｆκ（ｓｉｄ，Ｋ１）（＋）Ｆκ（ｓｉｄ，Ｋ’２）を生成して出力する（ステップＳ２２２−（ｎ＋１））。
【００８２】
図１４に例示するように、端末装置２２−（ｎ＋１）から送信された（Ｕｎ＋１，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］，σｎ＋１）は、鍵配送管理装置２１の通信部２１８に入力され、記憶部２１９に格納される。署名検証部２１０４は、記憶部２１９から検証鍵ｖｋｎ＋１、識別情報Ｕ１，・・・，Ｕｎ＋１，Ｓ、新たな秘匿化共有情報｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］、および署名σｎ＋１を読み込み、検証鍵ｖｋｎ＋１を用い、署名σｎ＋１をＶｅｒｖｋｎ＋１（（Ｕｎ＋１，（Ｕ１，・・・，Ｕｎ＋１），Ｓ，｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］），σｎ＋１）として検証する（ステップＳ２２０１）。ここで、署名σｎ＋１が正当でないと判断された場合、セッションを終了する。一方、署名σｎ＋１が正当であると判断された場合、制御部２１０がステップＳ２１３２で第１シード値Ｋ１が更新されたかを判定する。ここで、第１シード値Ｋ１が更新されていた場合、第１シード値暗号化部２１１２が記憶部２１９からＰａｒａｍｓおよび第１シード値Ｋ１を読み込み、関数暗号方式に則って第１シード値Ｋ１を暗号化し、ｉ∈［１，ｎ］について、端末装置の識別情報Ｕｉと有効時間区間ＴＦに属する時間ｔｉｍｅに対応する情報を含む属性情報Ｐｉ：＝（ＩＤ＝Ｕｉ）∧（ｔｉｍｅ∈ＴＦ）に対応する秘密鍵で復号可能な暗号文ＣＴ’ｉ←ＦＥｎｃ（Ｐａｒａｍｓ，Ｐｉ，Ｋ１）を生成して記憶部２１９に格納し（ステップＳ２２０３）、ステップＳ２２０５に進む。一方、第１シード値Ｋ１が更新されていない場合、第１シード値暗号化部２１１２はＣＴ’ｉ：＝｛｝（空）として記憶部２１９に格納し（ステップＳ２２０４）、ステップＳ２２０５に進む。
【００８３】
ステップＳ２２０５では、第２シード値秘匿化共有情報部２１２２は、記憶部２１９から新たな秘匿化共有情報新たな秘匿化共有情報｛ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝｝ｉ∈［１，ｎ］および新たな管理秘密値ｘ’ｓを読み込み、ｉ∈［１，ｎ］について、新たな秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝と新たな管理秘密値ｘ’ｓとに応じた新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓを生成して出力する。新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓは記憶部２１１に格納される（ステップＳ２２０５）。
【００８４】
署名生成部２１０３は、記憶部２１９から、署名鍵ｓｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ＋１、新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓ、および暗号文ＣＴ’ｉを読み込み、署名σ”ｓｉ←Ｓｉｇｓｋｓ（Ｓ，（Ｕ１，・・・，Ｕｎ＋１），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓ，ＣＴ’ｉ）を生成する（ただし、ｉ∈［１，ｎ］）。(Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓ，ＣＴ’ｉ，σ”ｓｉ)は通信部２１８に送られ、通信部２１８は、(Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓ，ＣＴ’ｉ，σ”ｓｉ)を端末装置２２−ｉに送信する。(Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓ，ＣＴ’ｉ，σ”ｓｉ)は、端末装置２２−ｉ（図７）の通信部２２８−ｉに入力され、記憶部２２９−ｉ（ただし、ｉ∈［１，ｎ］）に格納される（ステップＳ２２０６）。
【００８５】
端末装置２２−ｉ（ただし、ｉ∈［１，ｎ］）の署名検証部２２０５−ｉは、記憶部２２９−ｉから検証鍵ｖｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｎ＋１、新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓ、暗号文ＣＴ’ｉ、および署名σ”ｓｉを読み込み、検証鍵ｖｋｓを用い、署名σ”ｓｉをＶｅｒｖｋｓ（（Ｓ，（Ｕ１，・・・，Ｕｎ＋１），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓ，ＣＴ’ｉ），σ”ｓｉ）として検証する（ステップＳ２２１１−ｉ）。ここで、署名σ”ｓｉが正当でないと判断された場合、セッションを終了する。一方、署名σ”ｓｉが正当であると判断された場合、制御部２２０−ｉは記憶部２２９−ｉから暗号文ＣＴ’ｉを読み込み、ＣＴ’ｉ＝｛｝であるかを判定する（ステップＳ２２１２−ｉ）。ここで、ＣＴ’ｉ＝｛｝でなければ、第１シード値復号部２２１−ｉが、記憶部２２９−ｉから秘密鍵ｕｓｋｉおよび暗号文ＣＴ’ｉを読み込み、秘密鍵ｕｓｋｉを用い、関数暗号方式に則って暗号文ＣＴ’ｉをＫ１←ＦＤｅｃｕｓｋｉ（ＣＴ’ｉ，Ｐｉ）として復号して第１シード値Ｋ１を生成して出力する。第１シード値Ｋ１は記憶部２２９−ｉに格納され（ステップＳ２２１３−ｉ）、ステップＳ２２１４−ｉに進む。一方、ＣＴ’ｉ＝｛｝であればステップＳ２２１３−ｉを実行することなく、ステップＳ２２１４−ｉに進む。
【００８６】
ステップＳ２２１４−ｉ（ただし、ｉ∈［１，ｎ］）では、第２シード値生成部２２３−ｉが、記憶部２２９−ｉから新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓおよび端末秘密値ｘｉを読み込み、新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓと端末秘密値ｘｉとに応じた新たな第２シード値Ｋ’２：＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］∧ｋ≠ｉ｝・ｘ’ｓ・ｘｉ＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ＋１］｝・ｘ’ｓを生成して出力する。新たな第２シード値Ｋ’２は記憶部２２９−ｉに格納される（ステップＳ２２１４−ｉ）。
【００８７】
共通鍵生成部２２４−ｉ（ただし、ｉ∈［１，ｎ］）は、記憶部２２９−ｉから、セッション識別情報ｓｉｄ、第１シード値Ｋ１、および新たな第２シード値Ｋ’２を読み込み、擬似ランダム関数Ｆκを用い、第１シード値Ｋ１を含む情報と新たな第２シード値Ｋ’２を含む情報とに対応する共通鍵Ｋ＝Ｆκ（ｓｉｄ，Ｋ１）（＋）Ｆκ（ｓｉｄ，Ｋ’２）を生成して出力する（ステップＳ２２２−ｉ）。
【００８８】
＜端末装置削除処理＞
既にセッションが確立された端末装置２２−１〜２２−ｎから任意の端末装置２２−ｊを除き、端末装置２２−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）で新たな共通鍵を共有する処理を説明する
【００８９】
図１５に例示するように、管理秘密値生成部２１２１が新たな管理秘密値ｘ”ｓ∈ＲＺｐを生成して記憶部２１９に格納する（ステップＳ２３５）。第２シード値秘匿化情報生成部２１２２は、記憶部２１９から秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝および新たな管理秘密値ｘ”ｓを読み込み、秘匿化共有情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝と新たな管理秘密値ｘ”ｓとに応じた新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓ（ただし、ｉ∈［１，ｎ］＼ｊ）を生成して出力する。新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓは記憶部２１１に格納される（ステップＳ２３６１）。
【００９０】
署名生成部２１０３は、記憶部２１９から、署名鍵ｓｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｊ−１，Ｕｊ＋１，・・・，Ｕｎ、新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓを読み込み、署名σ’”ｓｉ←Ｓｉｇｓｋｓ（Ｓ，（Ｕ１，・・・，Ｕｊ−１，Ｕｊ＋１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓ）（ただし、ｉ∈［１，ｎ］＼ｊ）を生成する。(Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓ，σ’”ｓｉ)は通信部２１８に送られ、通信部２１８は、((Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓ，σ’”ｓｉ)を端末装置２２−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）に送信する。(Ｕｉ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓ，σ’”ｓｉ)は、端末装置２２−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）の通信部２２８−ｉに入力され、記憶部２２９−ｉに格納される（ステップＳ２３６２）。
【００９１】
端末装置２２−ｉ（ただし、ｉ∈［１，ｎ］＼ｊ）の署名検証部２２０５−ｉは、記憶部２２９−ｉから検証鍵ｖｋｓ、識別情報Ｓ、Ｕ１，・・・，Ｕｊ−１，Ｕｊ＋１，・・・，Ｕｎ、新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓ、および署名σ’”ｓｉを読み込み、検証鍵ｖｋｓを用い、署名σ’”ｓｉをＶｅｒｖｋｓ（（Ｓ，（Ｕ１，・・・，Ｕｊ−１，Ｕｊ＋１，・・・，Ｕｎ），Ｓ，ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓ），σ’”ｓｉ）として検証する（ステップＳ２３７１−ｉ）。ここで、署名σ’”ｓｉが正当でないと判断された場合、セッションを終了する。一方、σ’”ｓｉが正当であると判断された場合、第２シード値生成部２２３−ｉが、記憶部２２９−ｉから新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓおよび端末秘密値ｘｉを読み込み、新たな第２シード値の秘匿化情報ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓと端末秘密値ｘｉとに応じた新たな第２シード値Ｋ”２：＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］∧ｋ≠ｉ｝・ｘ”ｓ・ｘｉ＝ｇΠ｛ｘｋ｜ｋ∈［１，ｎ］｝・ｘ”ｓを生成して出力する。新たな第２シード値Ｋ”２は記憶部２２９−ｉに格納される（ステップＳ２３７２−ｉ）。共通鍵生成部２２４−ｉは、記憶部２２９−ｉから、セッション識別情報ｓｉｄ、第１シード値Ｋ１、および新たな第２シード値Ｋ”２を読み込み、擬似ランダム関数Ｆκを用い、第１シード値Ｋ１を含む情報と新たな第２シード値Ｋ”２を含む情報とに対応する共通鍵Ｋ”＝Ｆκ（ｓｉｄ，Ｋ１）（＋）Ｆκ（ｓｉｄ，Ｋ”２）を生成して出力する（ステップＳ２３８）。
【００９２】
［関数暗号方式の一例］
以下に関数暗号方式の一例を示す。本発明はこの方式に限定されない。また、［関数暗号方式の一例］の説明で使用する記号は上述で使用した記号と独立したものである。
【００９３】
＜記号の定義＞
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
∧：∧は論理積（ＡＮＤ）を表す論理記号である。
∨：∨は論理和（ＯＲ）を表す論理記号である。
¬：¬は否定（ＮＯＴ）を表す論理記号である。
命題変数：命題変数は命題の「真」,「偽」（"false","true"）を要素とする集合｛真，偽｝上の変数である。すなわち、命題変数の定義域は「真」,「偽」を要素とする集合である。命題変数及び命題変数の否定を総称してリテラル（literal）と呼ぶ。
【００９４】
Ｚ：Ｚは整数集合を表す。
sec：secはセキュリティパラメータ（sec∈Z, sec>0）を表す。
0*：0*は*個の0からなる列を表す。
1*：1*は*個の１からなる列を表す。
Fq：Fqは位数qの有限体を表す。位数qは１以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。
0F：0Fは有限体Fqの加法単位元を表す。
1F：1Fは有限体Fqの乗法単位元を表す。
δ(i,j)：δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0Fを満たす。
【００９５】
E：Eは有限体Fq上で定義された楕円曲線を表す。
G1, G2,GT：G1, G2, GTは位数qの巡回群を表す。本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。
【００９６】
Ψ：Ψは1以上の整数を表す。
ψ：ψは0以上Ψ以下の整数ψ=0,...,Ψを表す。
λ：λは1以上Ψ以下の整数λ=1,...,Ψを表す。
n(ψ)：n(ψ)は1以上の整数を表す。
ζ(ψ)：ζ(ψ)は0以上の整数を表す。
【００９７】
G1n(ψ)+ζ(ψ)：G1n(ψ)+ζ(ψ)はn(ψ)+ζ(ψ)個の巡回群G1の直積を表す。
G2n(ψ)+ζ(ψ)：G2n(ψ)+ζ(ψ)はn(ψ)+ζ(ψ)個の巡回群G2の直積を表す。
g1, g2,gT：g1, g2, gTは巡回群G, G1, G2, GTの生成元を表す。
V(ψ)：V(ψ)はn(ψ)+ζ(ψ)個の巡回群G1の直積からなるn(ψ)+ζ(ψ)次元のベクトル空間を表す。
V*(ψ)：V*(ψ)はn(ψ)+ζ(ψ)個の巡回群G2の直積からなるn(ψ)+ζ(ψ)次元のベクトル空間を表す。
Σν＝ν１ ν２ κ（ν）：Σν＝ν１ ν２κ（ν）は以下を意味する。
【数１】
0006259402.tif 000002
Πν＝ν１ ν２ κ（ν）：Πν＝ν１ ν２κ（ν）は以下を意味する。
【数２】
0006259402.tif 000003
【００９８】
eψ：eψは直積G1n(ψ)+ζ(ψ)と直積G2n(ψ)+ζ(ψ)との直積G1n(ψ)+ζ(ψ)×G2n(ψ)+ζ(ψ)を巡回群GTに写す非退化な双線形写像（bilinear map）を表す。双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力とし、巡回群GTの１個の元を出力する。
eψ：G1n(ψ)+ζ(ψ)×G2n(ψ)+ζ(ψ)→GT          …(1)
【００９９】
双線形写像eψは以下の性質を満たす。
［双線形性］双線形写像eψは、すべてのΓ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)及びν，κ∈Fqについて以下の関係を満たす。
eψ(ν・Γ1,κ・Γ2)=eψ(Γ1,Γ2)ν・κ          …(2)
［非退化性］双線形写像eψは、すべてのΓ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆる
Γ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)          …(3)
についてeψ(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【０１００】
本形態では、以下のような、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を用いて双線形写像eψを構成する。
Pair:G1×G2→GT          …(4)
本形態の双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ (β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1,...,γn(ψ)+ζ(ψ))と、巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1*,...,γn(ψ)+ζ(ψ)*)との入力に対し、巡回群GTの１個の元を出力する。
eψ：Πβ=1n(ψ)+ζ(ψ)Pair(γβ, γβ*)          …(5)
【０１０１】
双線形写像Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する。双線形写像Pairは、以下の性質を満たす。
［双線形性］双線形写像Pairは、すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(6)
［非退化性］双線形写像Pairは、すべての
Ω1∈G1，Ω2∈G2          …(7)
を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてPair(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
【０１０２】
ai(ψ)(i=1,...,n(ψ)+ζ(ψ))：ai(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。基底ベクトルai(ψ)の一例は、κ1・g1∈G1をi次元目の要素とし、残りのn(ψ)+ζ(ψ)-1個の要素を巡回群G1の単位元（加法的に「0」と表現）とするn(ψ)+ζ(ψ)次元の基底ベクトルである。この場合、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1(ψ)=(κ1・g1,0,0,...,0)
a2(ψ)=(0,κ1・g1,0,...,0)          …(8)
...
an(ψ)+ζ(ψ)(ψ)=(0,0,0,...,κ1・g1)
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルai(ψ)は直交基底であり、巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)は前述のベクトル空間V(ψ)を張る。
【０１０３】
ai*(ψ)(i=1,...,n(ψ)+ζ(ψ))：ai*(ψ)は巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。基底ベクトルai*(ψ)の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn(ψ)+ζ(ψ)-1個の要素を巡回群G2の単位元（加法的に「0」と表現）とするn(ψ)+ζ(ψ)次元の基底ベクトルである。この場合、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1*(ψ)=(κ2・g2,0,0,...,0)
a2*(ψ)=(0,κ2・g2,0,...,0)          …(9)
...
an(ψ)+ζ(ψ)*(ψ)=(0,0,0,...,κ2・g2)
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*(ψ)は直交基底であり、巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルai*(ψ)は前述のベクトル空間V*(ψ)を張る。
【０１０４】
なお、基底ベクトルai(ψ)と基底ベクトルai*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について以下の関係を満たす。
eψ(ai(ψ), aj*(ψ))=gTτ・δ(i,j)           …(10)
すなわち、i=jの場合には、式(5)(6)の関係から、以下の関係が満たされる。
eψ(ai(ψ), aj*(ψ))=Pair(g1, g2)κ1・κ2=gTτ
上付き添え字κ1，κ2はそれぞれκ1，κ2を表す。一方、i≠jの場合には、eψ(ai(ψ), aj*(ψ))=Πi=1n(ψ)+ζ(ψ) Pair(ai(ψ), aj*(ψ))の右辺は、Pair(κ1・g1,κ2・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(6)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、以下の関係が満たされる。
eψ(ai(ψ), aj*(ψ))=eψ(g1, g2)0=gT0
【０１０５】
特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、以下の関係が満たされる。
e(ai(ψ), aj*(ψ))=gTδ(i,j)           …(11)
gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。
【０１０６】
A(ψ)：A(ψ)は、基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(8)によって表現される場合、行列A(ψ)は以下のようになる。
【数３】
0006259402.tif 000004
【０１０７】
A*(ψ)：A*(ψ)は、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(9)によって表現される場合、行列A*(ψ)は以下のようになる。
【数４】
0006259402.tif 000005
【０１０８】
X(ψ)：X(ψ)は有限体Fqの元を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。行列X(ψ)は基底ベクトルai(ψ)の座標変換に用いられる。行列X(ψ)のi行j列(i=1,...,n(ψ)+ζ(ψ),j=1,...,n(ψ)+ζ(ψ))の要素をχi,j(ψ)∈Fqとすると、行列X(ψ)は以下のようになる。
【数５】
0006259402.tif 000006
なお、行列X(ψ)の各要素χi,j(ψ)を変換係数と呼ぶ。
【０１０９】
X*(ψ)：X*(ψ)はX*(ψ)=τ'・(X(ψ)-1)Tの関係を満たす行列である。ただし、τ'∈Fqは有限体Fqに属する任意の定数であり、例えば、τ'=1Fである。X*(ψ)は基底ベクトルai*(ψ)の座標変換に用いられる。行列X*(ψ)のi行j列の要素をχi,j*(ψ)∈Fqとすると、行列Ｘ*(ψ)は以下のようになる。
【数６】
0006259402.tif 000007
なお、行列Ｘ*(ψ)の各要素χi,j*(ψ)を変換係数と呼ぶ。
【０１１０】
この場合、n(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の単位行列をI(ψ)とするとX(ψ)・(X*(ψ))T=τ'・I(ψ)を満たす。すなわち、単位行列を以下のように定義する。
【数７】
0006259402.tif 000008
これについて以下が満たされる。
【数８】
0006259402.tif 000009
【０１１１】
ここで、n(ψ)+ζ(ψ)次元ベクトルを以下のように定義する。
χi→(ψ)=(χi,1(ψ),...,χi,n(ψ)+ζ(ψ)(ψ))          …(18)
χj→*(ψ)=(χj,1*(ψ),...,χj,n(ψ)+ζ(ψ)*(ψ))           …(19)
すると、式(17)の関係から、n(ψ)+ζ(ψ)次元ベクトルχi→(ψ)とχj→*(ψ)との内積は、以下のようになる。
χi→(ψ)・χj→*(ψ)=τ'・δ(i,j)          …(20)
【０１１２】
bi(ψ)：bi(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi(ψ)は行列X(ψ)を用いて基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi(ψ)は、以下の演算によって得られる。
bi(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j(ψ)・aj(ψ)          …(21)
例えば、基底ベクトルaj(ψ)(j=1,...,n(ψ)+ζ(ψ))が式(8)によって表現される場合、基底ベクトルbi(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi(ψ)=(χi,1(ψ)・κ1・g1,χi,2(ψ)・κ1・g1,
...,χi,n(ψ)+ζ(ψ)(ψ)・κ1・g1)          …(22)
巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ)は前述のベクトル空間V(ψ)を張る。
【０１１３】
bi*(ψ)：bi*(ψ)は巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi*(ψ)は行列X*(ψ)を用いて基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi*(ψ)は、以下の演算によって得られる。
bi*(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j*(ψ)・aj*(ψ)          …(23)
例えば、基底ベクトルaj*(ψ) (j=1,...,n(ψ)+ζ(ψ))が式(9)によって表現される場合、基底ベクトルbi*(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi*(ψ)=(χi,1*(ψ)・κ2・g2 ,χi,2*(ψ)・κ2・g2,
...,χi,n(ψ)+ζ(ψ)*(ψ)・κ2・g2)        …(24)
巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)は前述のベクトル空間V*(ψ)を張る。
【０１１４】
なお、基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について以下の関係を満たす。
eψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)          …(25)
すなわち、式(5)(20)(22)(24)の関係から、以下の関係が満たされる。
【数９】
0006259402.tif 000010
特にτ=κ1・κ2=1F（例えば、κ1=κ2=1F）及びτ'=1Fである場合、以下の関係が満たされる。
eψ(bi(ψ), bj*(ψ))=gTδ(i,j)          …(26)
基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、双対ペアリングベクトル空間（ベクトル空間V(ψ)とベクトル空間V*(ψ)）の双対正規直交基底である。
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルai(ψ)及びai*(ψ)や、式(21)(23)で例示したもの以外の基底ベクトルbi(ψ)及びbi*(ψ)を用いてもよい。
【０１１５】
B(ψ)：B(ψ)は基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列である。B(ψ)=X(ψ)・A(ψ)を満たす。例えば、基底ベクトルbi(ψ)が式(22)によって表現される場合、行列B(ψ)は以下のように表される。
【数１０】
0006259402.tif 000011
【０１１６】
B*(ψ)：B*(ψ)は基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。B*(ψ)=X*(ψ)・A*(ψ)を満たす。例えば、基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(24)によって表現される場合、行列B*(ψ)は以下のように表される。
【数１１】
0006259402.tif 000012
【０１１７】
v(λ)→：v(λ)→は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
v(λ)→=(v1(λ),...,vn(λ)(λ))∈Fqn(λ)          …(29)
vμ(λ)：vμ(λ)はn(λ)次元ベクトルv(λ)→のμ(μ=1,...,n(λ))番目の要素を表す。
w(λ)→：w(λ)→は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
w(λ)→=(w1(λ),...,wn(λ)(λ))∈Fqn(λ)          …(30)
wμ(λ)：wμ(λ)はn(λ)次元ベクトルw(λ)→のμ(μ=1,...,n(λ))番目の要素を表す。
【０１１８】
Enc：Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。
EncK(M)：EncK(M)は、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。
Dec：Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。
DecK(C)：DecK(C)は、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。
【０１１９】
＜関数暗号方式の基本的な構成＞
次に、関数暗号方式の基本的な構成について例示する。ここで例示する関数暗号方式では秘密情報に応じた値が所定の論理式に応じた態様で階層的に秘密分散される。所定の論理式は、第１情報と第２情報との組み合わせによって真理値が定まる命題変数を含み、必要に応じてさらに論理記号∧，∨，¬の何れか又はすべてを含む。各命題変数の真理値が特定されることで定まる当該所定の論理式の真理値が「真」となる場合に秘密情報に応じた値が復元され、それに基づいて暗号文が復号される。
【０１２０】
＜論理式と階層的な秘密分散との関係＞
上述した所定の論理式と階層的な秘密分散との関係を説明する。
秘密分散とは、しきい値Kt(Kt≧1)個以上のシェア情報が得られた場合にのみ秘密情報が復元されるように、秘密情報をN(N≧2)個のシェア情報に分散することである。Kt=Nを満たす秘密分散の方式（SSS: Secret Sharing Scheme）をN-out-of-N分散方式（或いは「N-out-of-Nしきい値分散方式」）といい、Kt＜Nを満たす秘密分散の方式をKt-out-of-N分散方式（或いは「Kt-out-of-Nしきい値分散方式」）という。
【０１２１】
N-out-of-N分散方式では、すべてのシェア情報share(1),...,share(N)が与えられれば秘密情報SEを復元できるが、任意のN-1個のシェア情報share(φ1),...,share(φN-1)が与えられても秘密情報SEの情報はまったく得られない。以下に、N-out-of-N分散方式の一例を示す。
・SH1,...,SHN-1をランダムに選択する。
・SHN=SE-(SH1+...+SHN-1)の計算を行う。
・SH1,...,SHNを各シェア情報share(1),...,share(N)とする。
・すべてのシェア情報share(1),...,share(N)が与えられれば、以下の復元処理によって秘密情報SEの復元が可能である。
SE=share(1)+...+share(N)          …(31)
【０１２２】
Kt-out-of-N分散方式では、任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)が与えられれば秘密情報SEを復元できるが、任意のKt-1個のシェア情報share(φ1),...,share(φKt-1)が与えられても秘密情報SEの情報はまったく得られない。添え字のKtはKtを表す。以下にKt-out-of-N分散方式の一例を示す。
・f(0)=SEを満たすKt-1次の多項式f(x)=ξ0+ξ1・x+ξ2・x2+...+ξKt-1・xKt-1をランダムに選ぶ。すなわち、ξ0=SEとし、ξ1,..., ξKt-1をランダムに選ぶ。シェア情報をshare(ρ)=(ρ, f(ρ))（ρ=1,...,N）とする。(ρ, f(ρ))からのρ及びf(ρ)の抽出が可能であり、(ρ, f(ρ))の例はρとf(ρ)とのビット結合値である。
・任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)（(φ1,...,φKt)⊂(1,...,N)）が得られた場合、例えば、ラグランジェ(Lagrange)の補間公式を用い、以下のような復元処理によって秘密情報SEの復元が可能である。
SE=f(0)=LA1・f(φ1)+...+ LAKt・f(φKt)          …(32)
【数１２】
0006259402.tif 000013
は先頭からρ番目の被演算子〔分母の要素(φρ-φρ)、分子の要素(x-φρ)〕が存在しないことを意味する。すなわち、式(33)の分母は、以下のように表される。
(φρ-φ1)・...・(φρ-φρ-1)・(φρ-φρ+1)・...・(φρ-φKt)
式(33)の分子は、以下のように表される。
(x-φ1)・...・(x-φρ-1)・(x-φρ+1)・...・(x-φKt)
【０１２３】
上述した各秘密分散を拡張し、秘密情報SEに応じた値をシェア情報shareに応じた値に秘密分散することもできる。秘密情報SEに応じた値とは秘密情報SEそのものや秘密情報SEの関数値であり、シェア情報shareに応じた値とはシェア情報shareそのものやシェア情報の関数値である。例えば、有限体Fqの元である秘密情報SE∈Fqに応じた巡回群GTの元gTSE∈GTを秘密情報SEの各シェア情報share(1),share(2)に応じた巡回群GTの元gTshare(1),gTshare(2)∈GTに秘密分散することもできる。上述した秘密情報SEはシェア情報shareの線形結合となる（式(31)(32)）。秘密情報SEがシェア情報shareの線形結合となる秘密分散方式を線形秘密分散方式と呼ぶ。
【０１２４】
上述した所定の論理式は、秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。すなわち、ド・モルガンの法則により、上述した所定の論理式はリテラルからなる論理式、又は、論理記号∧，∨の少なくとも一部とリテラルとからなる論理式（これらを「標準形論理式」と呼ぶことにする）によって表現でき、この標準形論理式は秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。
【０１２５】
標準形論理式を表現する木構造データは複数のノードを含み、少なくとも一部のノードは１個以上の子ノードの親ノードとされ、親ノードの１つはルートノードとされ、子ノードの少なくとも一部は葉ノードとされる。ルートノードの親ノードや、葉ノードの子ノードは存在しない。ルートノードには秘密情報に応じた値が対応し、各親ノードの子ノードには当該親ノードに対応する値を秘密分散したシェア情報に応じた値が対応する。各ノードでの秘密分散形態（秘密分散方式やしきい値）は標準形論理式に応じて定まる。また、各葉ノードには標準形論理式を構成する各リテラルが対応し、当該各リテラルの真理値は第１情報と第２情報との組み合わせによって定まる。
【０１２６】
ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られないものとする。また、上述した秘密分散の性質により、親ノードに対応するシェア情報に応じた値（その親ノードがルートノードであれば秘密情報に応じた値）は、その子ノードに対応するシェア情報に応じた値が当該親ノードに対応するしきい値以上の個数だけ得られた場合にのみ復元される。そのため、どの葉ノードに対応するリテラルの真理値が真になったのかと木構造データの構成（各ノードでの秘密分散の形態を含む）とに応じ、最終的にルートノードに対応する秘密情報に応じた値が復元できるか否かが定まる。そして、各葉ノードに対応する各リテラルの真理値が標準形論理式の真理値を真にする場合にのみ最終的にルートノードに対応する秘密情報に応じた値が復元できるように木構造データが構成されている場合、このような木構造データは標準形論理式を表現する。このような標準形論理式を表現する木構造データは容易に設定できる。
【０１２７】
＜アクセス構造＞
上述のように秘密情報を階層的に秘密分散して得られる木構造データによって所定の論理式を表現した場合、第１情報と第２情報との組み合わせに対して得られる葉ノードでのシェア情報に応じた値から秘密情報に応じた値を復元できるか否かによって、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となるか「偽」となるかを判定できる。以下、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となる場合に第１情報と第２情報との組み合わせを受け入れ、「偽」となる場合に第１情報と第２情報との組み合わせを拒絶する仕組みをアクセス構造と呼ぶ。
【０１２８】
上述のように所定の論理式を表現した木構造データの葉ノードの総数をΨとし、各葉ノードに対応する識別子をλ=1,...,Ψとする。各葉ノードに対応するn(λ)次元ベクトルv(λ)→の集合{v(λ)→}λ=1,...,Ψを第１情報とし、n(λ)次元ベクトルw(λ)→の集合{w(λ)→}λ=1,...,Ψを第２情報とする。また、上述した木構造データをラベル付き行列LMT(MT,LAB)として実装する。
【０１２９】
ラベル付き行列LMT(MT,LAB)は、以下のΨ行COL列（COL≧1）の行列MTと、行列MTの各行λ=1,...,Ψに対応付けられたラベルLAB(λ)とを含む。
【数１３】
0006259402.tif 000014
【０１３０】
行列MTの各要素mtλ,col（col=1,...,COL）は次の２つの要件を満たす。第１に、上述のように所定の論理式を表現した木構造データのルートノードに秘密情報SE∈Fqに応じた値が対応する場合、予め定められた有限体Fqの元を要素とするCOL次元ベクトルGV→と秘密情報SEに応じた有限体Fqの元を要素とするCOL次元ベクトルCV→との間に以下の関係が成立する。
GV→=(gv1,...,gvCOL)∈FqCOL          …(35)
CV→=(cv1,...,cvCOL)∈FqCOL          …(36)
SE=GV→・(CV→)T          …(37)
【０１３１】
以下にCOL次元ベクトルGV→の具体例を示す。
GV→=(1F,...,1F)∈FqCOL          …(38)
ただし、GV→=(1F,0F,...,0F)∈FqCOLなどのその他のCOL次元ベクトルがGV→であってもよい。第２に、識別子λに対応する葉ノードにシェア情報share(λ)∈Fqに応じた値が対応する場合、以下の関係が成立する。
(share(1),...,share(Ψ))T=MT・(CV→)T          …(39)
【０１３２】
上述のように所定の論理式を表現した木構造データが定まれば、これら２つの要件を満たす行列MTを選択することは容易である。また、秘密情報SEやシェア情報share(λ)が変数であったとしても、これら２つの要件を満たす行列MTを選択することは容易である。すなわち、行列MTを定めた後で秘密情報SEやシェア情報share(λ)の値が定められてもよい。
【０１３３】
また、行列MTの各行λ=1,...,Ψに対応付けられたラベルLAB(λ)は、識別子λに対応する葉ノードに対応するリテラル（PRO(λ)又は¬PRO(λ)）に対応する。ここで、命題変数PRO(λ)の真理値が「真」であることと第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}が含むv(λ)→と第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}が含むw(λ)→との内積v(λ)→・w(λ)→が０となることとが等価であると扱い、命題変数PRO(λ)の真理値が「偽」であることと内積v(λ)→・w(λ)→が０とならないこととが等価であると扱う。PRO(λ)に対応するラベルLAB(λ)がv(λ)→を表し、¬PRO(λ)に対応するラベルLAB(λ)が¬v(λ)→を表すものとする。なお、¬v(λ)→はv(λ)→の否定を表す論理式であり、¬v(λ)→からv(λ)→の特定が可能である。また、LAB(λ)がv(λ)→を表すことを「LAB(λ)=v(λ)→」と表記し、LAB(λ)が¬v(λ)→を表すことを「LAB(λ)=¬v(λ)→」と表記する。また、LAB(λ)（λ=1,...,Ψ）の集合{LAB(λ)}λ=1,...,ΨをLABと表記する。
【０１３４】
さらに、Ψ次元ベクトルが以下のように定義される。
TFV→=(tfv(1),...,tfv(Ψ))          …(40)
要素tfv(λ)は、内積v(λ)→・w(λ)→が０のときにtfv(λ)=１となり、０以外のときにtfv(λ)=0となる。
tfv(λ)=1  （PRO(λ)が真）    if  v(λ)→・w(λ)→=0        …(41)
tfv(λ)=0  （PRO(λ)が偽）    if  v(λ)→・w(λ)→≠0        …(42)
さらに、以下の論理式の真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。
{(LAB(λ)=v(λ)→)∧(tfv(λ)=1)}∨{(LAB(λ)=¬v(λ)→)∧(tfv(λ)=0)}  …(43)
すなわち、識別子λに対応する葉ノードに対応するリテラルの真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。すると、行列MTが含む行ベクトルのうちLIT(λ)=1となる行ベクトルmtλ→=(mtλ,1,...,mtλ,COL)のみからなる部分行列MTTFVは以下のように表記できる。
MTTFV=(MT)LIT(λ)=1          …(44)
【０１３５】
上述した秘密分散方式が線形秘密分散方式である場合、識別子λに対応するシェア情報share(λ)に応じた値から秘密情報SEに応じた値が復元できることと、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属することとは等価である。すなわち、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属するか否かを判定することで、識別子λに対応するシェア情報share(λ)に応じた値から秘密情報SEに応じた値が復元できるか否かが判定できる。行ベクトルmtλ→で張られるベクトル空間とは、行ベクトルmtλ→の線形結合で表すことができるベクトル空間を意味する。
【０１３６】
ここで、上述の部分行列MTTFVの各行ベクトルmtλ→で張られるベクトル空間span<MTTFV>にCOL次元ベクトルGV→が属する場合に第１情報と第２情報との組み合わせが受け入れられ、そうでない場合に第１情報と第２情報との組み合わせが拒絶されることにする。これにより、上述のアクセス構造が具体化される。なお、上述したようにラベル付き行列LMT(MT,LAB)が第１情報に対応する場合、アクセス構造が第１情報と第２情報との組み合わせを受け入れることを「アクセス構造が第２情報を受け入れる」といい、アクセス構造が第１情報と第２情報との組み合わせを受け入れないことを「アクセス構造が第２情報を拒絶する」という。
受け入れ  if  GV→∈span<MTTFV>
拒絶      if  ¬(GV→∈span<MTTFV>)
【０１３７】
また、GV→∈span<MTTFV>の場合、以下を満たす係数const(μ)が存在し、このような係数const(μ)は行列MTのサイズのオーダーの多項式時間で求めることができる。
SE=Σμ∈SETconst(μ)・share(μ)          …(45)
{const(μ)∈Fq|μ∈SET},SET⊆{1,...,λ|LIT(λ)=1}
【０１３８】
＜アクセス構造を用いた関数暗号方式の基本方式＞
以下では、アクセス構造を用いた関数暗号方式によって鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本方式を例示する。この基本方式はSetup(1sec，(Ψ;n(1),...,n(Ψ)))，GenKey(PK,MSK,LMT(MT,LAB))，Enc(PK,M,{λ,v(λ)→|λ=1,...,Ψ})(v1(λ)=1F)，Dec(PK,SKS,C)を含む。また、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の1番目の要素w1(λ)が1Fとされる。
【０１３９】
［Setup(1sec，(Ψ;n(1),...,n(Ψ)))：セットアップ］
−入力：1sec，(Ψ;n(1),...,n(Ψ))
−出力：マスタ秘密鍵MSK，公開パラメータPK
【０１４０】
Setupでは各ψ=0,...,Ψについて以下の処理が実行される。
(Setup-1) 1secを入力としてセキュリティパラメータsecでの位数q、楕円曲線E、巡回群G1, G2, GT、双線形写像eψ(ψ=0,...,Ψ)が生成される（param=(q, E, G1, G2, GT, eψ)）。
(Setup-2) τ'∈Fqが選択され、X*(ψ)=τ'・(X(ψ)-1)Tを満たす行列X(ψ)，X*(ψ)が選択される。
(Setup-3) 基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(21)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B(ψ)が生成される。
【０１４１】
(Setup-4) 基底ベクトルai*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(23)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B*(ψ)が生成される。
(Setup-5) B*(ψ)＾の集合{B*(ψ)＾}ψ=0,...,Ψをマスタ秘密鍵MSK={B*(ψ)＾}ψ=0,...,Ψとする。B(ψ)＾の集合{B(ψ)＾}ψ=0,...,Ψと1secとparamとを公開パラメータPKとする。ただし、B*(ψ)＾は行列B*(ψ)又はその部分行列であり、B(ψ)＾は行列B(ψ)又はその部分行列である。集合{B*(ψ)＾}ψ=0,...,Ψは、少なくとも、b1*(0),b1*(λ) …,bn(λ)*(λ)（λ=1,...,Ψ）を含む。集合{B(ψ)＾}ψ=0,...,Ψは、少なくとも、b1(0),b1(λ),…,bn(λ)(λ)（λ=1,...,Ψ）を含む。以下に一例を示す。
【０１４２】
・n(0)+ζ(0)≧5, ζ(λ)=3・n(λ)
・B(0)＾=(b1(0) b3(0) b5(0))T
・B(λ)＾=(b1(λ) … bn(λ)(λ) b3・n(λ)+1(λ) … b4・n(λ)(λ))T（λ=1,...,Ψ）
・B*(0)＾=(b1*(0) b3*(0) b4*(0))T
・B*(λ)＾=(b1*(λ) … bn(λ)*(λ) b2・n(λ)+1*(λ) … b3・n(λ)*(λ))T（λ=1,...,Ψ）
【０１４３】
［GenKey(PK,MSK,LMT(MT,LAB))：秘密鍵生成］
−入力：公開パラメータPK，マスタ秘密鍵MSK，第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}に対応するラベル付き行列LMT(MT,LAB)
−出力：秘密鍵SKS
【０１４４】
(GenKey-1) 式(35)-(39)を満たす秘密情報SEに対して以下の処理が実行される。
D*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0)          …(46)
ただし、Iは2以上n(0)+ζ(0)以下の定数である。coefι(0)∈Fqは定数又は乱数である。「乱数」とは真性乱数や擬似乱数を意味する。以下にD*(0)の一例を示す。なお、式(47)のcoef4(0)は乱数である。
D*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0)          …(47)
(GenKey-2) 式(35)-(39)を満たすshare(λ)(λ=1,...,Ψ)に対して以下の処理が実行される。
LAB(λ)=v(λ)→となるλに対して、以下のD*(λ)が生成される。
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)          …(48)
LAB(λ)=¬v(λ)→となるλに対して、以下のD*(λ)が生成される。
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)          …(49)
ただしcoef(λ),coefι(λ)∈Fqは定数又は乱数である。以下に一例を示す。
【０１４５】
LAB(λ)=v(λ)→となるλに対して、例えば以下のD*(λ)が生成される。
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)          …(50)
LAB(λ)=¬v(λ)→となるλに対して、例えば以下のD*(λ)が生成される。
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)          …(51)
なお、式(50)(51)のcoef(λ)及びcoefι(λ)は乱数である。
(GenKey-3) 以下の秘密鍵が生成される。
SKS=(LMT(MT,LAB),D*(0),D*(1),...,D(Ψ))          …(52)
【０１４６】
［Enc(PK,M,VSET2)：暗号化］
−入力：公開パラメータPK，平文M，第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}(w1(λ)=1F)
−出力：暗号文C
【０１４７】
(Enc-1) 以下の処理によって共通鍵Kの暗号文C(ψ)(ψ=0,...,Ψ)が生成される。
C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0)          …(53)
C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)  …(54)
ただし、υ,υι(ψ)∈Fq(ψ=0,...,Ψ)は定数又は乱数であり、以下の関係が満たされる。
(coef2(0),...,coefI(0))・(υ2(0),...,υI(0))=υ'      …(55)
coefι(λ)・υι(λ)=0F (ι=n(λ)+1,...,n(λ)+ζ(λ))  …(56)
υ'の例はυ2(0),...,υI(0)の何れか１個である。例えば、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)が乱数であり、ζ(λ)=3・n(λ)、I=5であり、以下の関係が満たされる。
(υ2(0),...,υI(0))=(0F,υ3(0),0F,υ5(0))
υ'=υ3(0)
(υn(λ)+1(λ),...,υ3・n(λ)(λ))=(0F,...,0F)
(Enc-2) 共通鍵
K=gTτ・τ'・υ'∈GT          …(57)
が生成される。例えば、τ=τ'=1Fの場合、以下の関係が満たされる。
K=gTυ'∈GT          …(58)
(Enc-3) 共通鍵Kを用いて平文Mの暗号文C(Ψ+1)が生成される。
C(Ψ+1)=EncK(M)          …(59)
【０１４８】
共通鍵暗号方式Encは、例えば共通鍵Kを用いて暗号化可能に構成されたカメリア（Camellia）（登録商標）やAESや共通鍵と平文との排他的論理和などでよいが、その他の簡単な例として以下のようにEncK(M)を生成してもよい。ただし、式(60)の例ではM∈GTとされる。
C(Ψ+1)=gTυ'・M          …(60)
(Enc-4) 以下の暗号文が生成される。
C=(VSET2,C(0),{C(λ)}(λ,w(λ)→)∈VSET2,C(Ψ+1))          …(61)
ただし、下付き添え字の「w(λ)→」は「w(λ)→」を表す。
【０１４９】
［Dec(PK,SKS,C)：復号］
−入力：公開パラメータPK，秘密鍵SKS，暗号文C
−出力：平文M'
【０１５０】
(Dec-1) λ=1,...,Ψについて、秘密鍵SKSが含むラベル付き行列LMT(MT,LAB)の各ラベルLAB(λ)であるn(λ)次元ベクトルv(λ)→と暗号文CのVSET2が含むn(λ)次元ベクトルw(λ)→との内積v(λ)→・w(λ)→が0となるか否かが判定され、これとLMT(MT,LAB)の各ラベルLAB(λ)とによってGV→∈span<MTTFV>であるか否かが判定される（式(40)-(45)）。GV→∈span<MTTFV>でなければ暗号文Cが拒絶され、GV→∈span<MTTFV>であれば暗号文Cが受け入れられる。
(Dec-2) 暗号文Cが受け入れられると、SET⊆{1,...,λ|LIT(λ)=1}と式(45)を満たす係数const(μ)(μ∈SET)とが計算される。
(Dec-3) 以下の共通鍵が生成される。
【数１４】
0006259402.tif 000015
式(6)(25)(55)より、以下の関係が満たされる。
【数１５】
0006259402.tif 000016
【０１５１】
式(6)(25)(41)(48)(54)(56)及びw1(λ)=1Fより、以下の関係が満たされる。
【数１６】
0006259402.tif 000017
【０１５２】
式(6)(25)(42)(49)(54)(56)より以下の関係がみたされる。
【数１７】
0006259402.tif 000018
を満たす。
【０１５３】
式(45)(63)-(65)より以下の関係が満たされる。
【数１８】
0006259402.tif 000019
例えば、τ=τ'=1Fの場合、以下の関係が満たされる。
K=gTυ'∈GT          …(67)
【０１５４】
(Dec-4) 共通鍵Kを用い、以下のように平文M'が生成される。
M'=DecK(C(Ψ+1))=DecK(C(Ψ+1))          …(68)
例えば、式(60)に例示した共通鍵暗号方式の場合、以下のように平文M'が生成される。
M'=C(Ψ+1)/K          …(69)
【０１５５】
なお、gTをGTの生成元とする代わりにgTτやgTτ'やgTτ・τ'をGTの生成元と扱ってもよい。秘密鍵SKSのλと暗号文のλとを対応関係を特定する写像を用いてC(λ)とD*(λ)との組み合わせを特定し、［Dec(PK,SKS,C)：復号］の処理が実行されてもよい。第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の1番目の要素w1(λ)が1Fとされるだけではなく、第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}のn(λ)番目の要素vn(λ)(λ)が1Fとされてもよい。要素w1(λ)が1Fでない場合にはw(λ)→の代わりにw(λ)→/w1(λ)を用いてもよく、要素vn(λ)(λ)が1Fでない場合にはv(λ)→の代わりにv(λ)→/vn(λ)(λ)を用いてもよい。第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}の代わりに第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}が用いられ、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の代わりに第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}が用いられてもよい。この場合には第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}の1番目の要素v1(λ)が1Fとされる。
【０１５６】
［その他の変形例等］
なお、本発明は上述の実施形態に限定されるものではない。例えば、上記の実施形態の秘密鍵ｕｓｋｉは、端末装置１２，２２−ｉの識別情報Ｕｉと有効時間区間ＴＦに属する時間ｔｉｍｅ∈ＴＦに対応する情報を含む情報に対応するものであった。しかしながら、秘密鍵ｕｓｋｉが識別情報Ｕｉに対応せず、有効時間区間ＴＦに属する時間ｔｉｍｅ∈ＴＦに対応する情報を含む情報に対応するものであってもよい。また、共有情報Ｃが予め生成されていてもよいし、共有情報Ｃが定数であってもよい。さらに共有情報Ｃは第２実施形態で例示したものには限定されない。例えば、公知の鍵配送方式で鍵配送がなされる端末装置間で共有されるその他の情報を共有情報Ｃとしてもよい。また、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１５７】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１５８】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１５９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１６０】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０１６１】
１，２  鍵配送システム
１１，２１  鍵配送管理装置
１２−ｋ，２２−ｋ  端末装置
【図１】
0006259402.tif 000020
【図２】
0006259402.tif 000021
【図３】
0006259402.tif 000022
【図４】
0006259402.tif 000023
【図５】
0006259402.tif 000024
【図６】
0006259402.tif 000025
【図７】
0006259402.tif 000026
【図８】
0006259402.tif 000027
【図９】
0006259402.tif 000028
【図１０】
0006259402.tif 000029
【図１１】
0006259402.tif 000030
【図１２】
0006259402.tif 000031
【図１３】
0006259402.tif 000032
【図１４】
0006259402.tif 000033
【図１５】
0006259402.tif 000034