JP5355263B2 - 鍵共有装置、鍵共有方法及びプログラム - Google Patents

Description

本発明は、情報セキュリティ技術の応用に関し、特に、装置間で鍵を共有する鍵交換技術に関する。

装置間で鍵を共有する鍵交換方式の従来技術の一つに以下の方式がある（例えば、非特許文献１参照）。

［公開パラメータ］
ＧをＬビット（Ｌ≧１）の位数ｑ（ｑは素数）の巡回群、ｇをＧの生成元とする。Ｈ：｛０，１｝^＊→｛０，１｝^Ｌを任意長のビット列をＬビットのビット列に写すハッシュ関数とする。また、ＩＤ（ａｌｇｏ）を、共有した鍵Ｋの使いかた（認証鍵、暗号化鍵など）を記述するアルゴリズム識別子とする。

［鍵交換］
識別子ＩＤ（１）と秘密鍵ａ（１）∈Ｚ_ｑと公開鍵Ａ（１）＝ｇ^ａ（１）∈Ｇをもつ装置ＰＡ（１）と、識別子ＩＤ（２）と秘密鍵ａ（２）∈Ｚ_ｑと公開鍵Ａ（２）＝ｇ^ａ（２）∈Ｇをもつ装置ＰＡ（２）とは、以下のようにして鍵Ｋを共有する。

１．装置ＰＡ（１）は、乱数ｒ（１）∈Ｚ_ｑを生成し、識別子ＩＤ（１）とＸ（１）＝ｇ^ｒ（１）∈Ｇを装置ＰＡ（２）に送る。

２．装置ＰＡ（２）は、乱数ｒ（２）∈Ｚ_ｑを生成し、識別子ＩＤ（２）とＸ（２）＝ｇ^ｒ（２）∈ＧをＰＡ（１）に送る。

３．装置ＰＡ（１）は、φ（１）＝Ｘ（２）^ｒ（１）∈Ｇとφ（２）＝Ａ（２）^ａ（１）∈Ｇを計算し、鍵Ｋ＝Ｈ（φ（１），φ（２），ＩＤ（１），ＩＤ（２），ＩＤ（ａｌｇｏ））を計算する。

４．装置ＰＡ（２）は、φ（１）＝Ｘ（１）^ｒ（２）∈Ｇとφ（２）＝Ａ（１）^ａ（２）∈Ｇを計算し、鍵Ｋ＝Ｈ（φ（１），φ（２），ＩＤ（１），ＩＤ（２），ＩＤ（ａｌｇｏ））を計算する。

ここで、巡回群Ｇでの演算は可換であるため、装置ＰＡ（１），ＰＡ（２）で生成されるφ（１），φ（２）は、いずれも、
φ(1)=g^r(1)・r(2)∈G …(1)
φ(2)=g^a(1)・a(2)∈G …(2)
となり、装置ＰＡ（１），ＰＡ（２）で同一の鍵Ｋが共有される。

Elaine Barker, Don Johnson, and Miles Smid, "NIST Special Publication 800-56A: Recommendation for Pair-WiseKey Establishment Schemes Using Discrete Logarithm Cryptography", Section 6.1.1.2

しかし、非特許文献１の方式は、ＫＣＩ攻撃(Key-Compromise Impersonation attack) に弱いという問題がある。

攻撃者Ｍは以下のようにＫＣＩ攻撃を行うことができる。

０．攻撃者Ｍは、装置ＰＡ（１）の秘密鍵ａ（１）∈Ｚ_ｑを得る。

１．装置ＰＡ（１）は、乱数ｒ（１）∈Ｚ_ｑを生成し、識別子ＩＤ（１）とＸ（１）＝ｇ^ｒ（１）∈Ｇを装置ＰＡ（２）に送る。

２．攻撃者Ｍは、乱数ｒ（２）∈Ｚ_ｑを生成し、識別子ＩＤ（２）とＸ（２）＝ｇ^ｒ（２）∈ＧをＰＡ（１）に送る。

３．装置ＰＡ（１）は、φ（１）＝Ｘ（２）^ｒ（１）∈Ｇとφ（２）＝Ａ（２）^ａ（１）∈Ｇを計算し、鍵Ｋ＝Ｈ（φ（１），φ（２），ＩＤ（１），ＩＤ（２），ＩＤ（ａｌｇｏ））を計算する。

４．攻撃者Ｍは、φ（１）＝Ｘ（１）^ｒ（２）∈Ｇとφ（２）＝Ａ（２）^ａ（１）∈Ｇを計算し、鍵Ｋ＝Ｈ（φ（１），φ（２），ＩＤ（１），ＩＤ（２），ＩＤ（ａｌｇｏ））を計算する。

以上のように、装置ＰＡ（１）の秘密鍵ａ（１）∈Ｚ_ｑを得た攻撃者Ｍは、装置ＰＡ（２）の秘密鍵ａ（２）∈Ｚ_ｑを知らないにもかかわらず、装置ＰＡ（２）に成り済まして装置ＰＡ（１）と鍵Ｋを共有できる。

本発明はこのような点に鑑みてなされたものであり、ＫＣＩ攻撃に強い鍵共有技術を提供することを目的とする。

本発明では、他の装置と鍵を共有する鍵共有装置は、少なくとも、整数の秘密値ａ（ｉ）又は巡回群Ｇの元Ｚ（ｉ）＝ｇ^{ａ（ｉ）・ＭＳＫ}∈Ｇと、他の装置に対応する巡回群Ｇの元である公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇとを記憶する。なお、ｉ，ｊ∈｛１，．．．，Ｐ｝、ｊ≠ｉであり、Ｐは２以上の整数定数、ｇはｇ^ｍによって巡回群Ｇのすべての元を表現できる生成元であり、ＭＳＫ，ｍ及びａ（ｊ）は整数である。この鍵共有装置は、以下の処理を実行する。

まず、鍵共有装置は、整数の任意値ｒ（ｉ）を生成し、第１任意元Ｘ（ｉ）＝ｇ^ｒ（ｉ）∈Ｇを生成し、第１任意元Ｘ（ｉ）を出力する。この第１任意元Ｘ（ｉ）は他の装置に入力される。

また、鍵共有装置には、他の装置から出力された第２任意元Ｘ（ｊ）＝ｇ^ｒ（ｊ）∈Ｇが入力される。なお、ｒ（ｊ）は整数である。

鍵共有装置は、少なくとも、秘密値ａ（ｉ）又は元Ｚ（ｉ）＝ｇ^{ａ（ｉ）・ＭＳＫ}∈Ｇと、公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇと、任意値ｒ（ｉ）と、第２任意元Ｘ（ｊ）＝ｇ^ｒ（ｊ）∈Ｇとを用い、巡回群Ｇの元ｇ^Ｗ（ｕ）∈Ｇを共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群Ｇ_Ｔの元に写像する関数ｅを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔを共有元σ（ｕ）として生成する。なお、Ｗ（ｕ）は、整数ｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積であり、整数ｗ（ｕ，ｐ）は、ａ（ｐ）とｒ（ｐ）とを含む複数の整数の線形和であり、ｐ∈｛１，．．．，Ｐ｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数であり、ｇ_Ｔはｇ_Ｔ ^ｍによって巡回群Ｇ_Ｔのすべての元を表現できる生成元である。

そして、鍵共有装置は、少なくとも共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力する。

ここで、Ｗ（ｕ）は、整数ｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積であり、整数ｗ（ｕ，ｐ）は、ａ（ｐ）とｒ（ｐ）（ｐ∈｛１，．．．，Ｐ｝）とを含む複数の整数の線形和である。この場合、鍵共有装置は、自ら生成した任意値ｒ（ｉ）と、それに対応する秘密値ａ（ｉ）又は元Ｚ（ｉ）＝ｇ^{ａ（ｉ）・ＭＳＫ}∈Ｇと、の両方を知らなければ共有元σ（ｕ）を生成できない。そのため、他の装置の整数ａ（ｊ）を知った攻撃者が、任意値ｒ（ｉ）を生成して鍵共有装置に成り済まそうとしても、攻撃者は任意値ｒ（ｉ）に対応する秘密値ａ（ｉ）を知らないため、正しいσ（ｕ）を生成できない。よって、ＫＣＩ攻撃は成功しない。

以上のように、本発明の鍵共有技術はＫＣＩ攻撃に強い。

図１（Ａ）は、本形態の鍵共有システムの全体構成を例示するための図である。図１(Ｂ)は、本形態の鍵共有装置の基本構成を説明するための図である。 図２は、第１実施形態の鍵共有システムの構成を説明するためのブロック図である。 図３（Ａ）は、共有元生成部の構成を説明するためのブロック図である。図３（Ｂ）は、共有元生成部の構成を説明するためのブロック図である。 図４（Ａ）は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。図４（Ｂ）は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。 図５は、第２実施形態の鍵共有システムの構成を説明するためのブロック図である。 図６は、第２実施形態の鍵共有システムの構成を説明するためのブロック図である。 図７は、第２実施形態の鍵共有システムの構成を説明するためのブロック図である。 図８（Ａ）は、共有元生成部の構成を説明するためのブロック図である。図８（Ｂ）は、共有元生成部の構成を説明するためのブロック図である。 図９は、共有元生成部の構成を説明するためのブロック図である。 図１０（Ａ）は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。図１０（Ｂ）は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。 図１１は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。 図１２は、第３実施形態の鍵共有システムの構成を説明するためのブロック図である。 図１３は、第３実施形態の鍵共有システムの構成を説明するためのブロック図である。 図１４（Ａ）は、共有元生成部の構成を説明するためのブロック図である。図１４（Ｂ）は、共有元生成部の構成を説明するためのブロック図である。 図１５（Ａ）は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。図１５（Ｂ）は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。

以下、図面を参照して本発明の実施形態を説明する。

〔概要〕
まず、本形態の概要を説明する。

図１（Ａ）は、本形態の鍵共有システム１の全体構成を例示するための図であり、図１(Ｂ)は、本形態の鍵共有装置の基本構成を説明するための図である。

図１（Ａ）に例示するように、本形態の鍵共有システム１は、複数の鍵共有装置１０−ｐ（ｐ∈｛１，．．．，Ｐ｝、Ｐは２以上の整数定数）を有し、例えば、ネットワーク２０を通じて情報のやり取りが可能に構成されている。なお、複数の鍵共有装置１０−ｐ間での情報のやり取りはネットワーク経由で行われるものに限定されず、例えば、ＵＳＢメモリなどの可搬型の記録媒体への情報の読み書きによって行われてもよい。

鍵共有装置１０−ｉの記憶部１１−ｉ（図１（Ｂ））には、少なくとも、整数の秘密値ａ（ｉ）又は巡回群Ｇの元Ｚ（ｉ）＝ｇ^{ａ（ｉ）・ＭＳＫ}∈Ｇと、他の鍵共有装置１０−ｊに対応する巡回群Ｇの元である公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇと、が格納される。なお、ｉ，ｊ∈｛１，．．．，Ｐ｝、ｊ≠ｉ、ｇはｇ^ｍによって巡回群Ｇのすべての元を表現できる生成元、ＭＳＫ，ｍ及びａ（ｊ）は整数である。

鍵共有装置１０−ｉが他の鍵共有装置１０−ｊと鍵を共有する場合、まず、鍵共有装置１０−ｉの任意値生成部１２−ｉ（図１（Ｂ））が整数の任意値ｒ（ｉ）を生成し、任意値ｒ（ｉ）を出力する。次に、任意元生成部１３−ｉが任意値ｒ（ｉ）を入力として、第１任意元Ｘ（ｉ）＝ｇ^ｒ（ｉ）∈Ｇを生成し、第１任意元Ｘ（ｉ）＝ｇ^ｒ（ｉ）∈Ｇを出力する。出力部１４−ｉは、第１任意元Ｘ（ｉ）＝ｇ^ｒ（ｉ）∈Ｇを入力として、当該第１任意元Ｘ（ｉ）＝ｇ^ｒ（ｉ）∈Ｇを出力する。第１任意元Ｘ（ｉ）＝ｇ^ｒ（ｉ）∈Ｇは、他の鍵共有装置１０−ｊに入力される。

また、鍵共有装置１０−ｉの入力部１５−ｉには、他の鍵共有装置１０−ｊから出力された第２任意元Ｘ（ｊ）＝ｇ^ｒ（ｊ）∈Ｇが入力される。なお、ｒ（ｊ）は整数である。共有元生成部１６−ｉは、少なくとも、秘密値ａ（ｉ）又は元Ｚ（ｉ）＝ｇ^{ａ（ｉ）・ＭＳＫ}∈Ｇと、公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇと、任意値ｒ（ｉ）と、第２任意元Ｘ（ｊ）＝ｇ^ｒ（ｊ）∈Ｇと入力とし、巡回群Ｇの元ｇ^Ｗ（ｕ）∈Ｇを共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群Ｇ_Ｔの元に写像する関数ｅを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔを共有元σ（ｕ）として生成する。なお、Ｗ（ｕ）は、整数ｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積であり、整数ｗ（ｕ，ｐ）は、ａ（ｐ）とｒ（ｐ）とを含む複数の整数の線形和であり、ｐ∈｛１，．．．，Ｐ｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数であり、ｇ_Ｔはｇ_Ｔ ^ｍによって巡回群Ｇ_Ｔのすべての元を表現できる生成元である。共有元生成部１６−ｉは、生成した共有元σ（ｕ）を出力する。

鍵生成部１７−ｉは、共有元σ（ｕ）を入力として、少なくとも共有元σ（ｕ）に基づいて値が定まる鍵Ｋ（少なくとも共有元σ（ｕ）に値が依存する鍵Ｋ）を生成し、当該鍵Ｋを出力する。

鍵共有装置１０−ｉは、自ら生成した任意値ｒ（ｉ）と、それに対応する秘密値ａ（ｉ）又は元Ｚ（ｉ）＝ｇ^{ａ（ｉ）・ＭＳＫ}∈Ｇと、の両方を知らなければ共有元σ（ｕ）を生成できない。そのため、鍵共有装置１０−ｊの整数ａ（ｊ）を知った攻撃者が、任意値ｒ（ｉ）を生成して鍵共有装置１０−ｉに成り済まそうとしても、攻撃者は任意値ｒ（ｉ）に対応する秘密値ａ（ｉ）を知らないため、正しいσ（ｕ）を生成できない。よって、ＫＣＩ攻撃は成功しない。

また、少なくとも一部の整数ｗ（ｕ，ｐ）が、少なくとも一方が整数ｄ（ｐ）によって重み付けされたａ（ｐ）とｒ（ｐ）とを含む複数の整数の線形和であり、整数ｄ（ｐ）が、第１任意元Ｘ（ｉ）及び／又は第２任意元Ｘ（ｊ）に応じて値が定まる整数であってもよい。例えば、整数ｄ（ｐ）が、第１任意元Ｘ（ｉ）に応じて値が定まる整数であった場合、整数ｄ（ｐ）の値は、第１任意元Ｘ（ｉ）が定まるまで特定できないため、鍵共有装置１０−ｉ又はそれに成り済ました攻撃者は、鍵共有相手である鍵共有装置１０−ｊによる共有元σ（ｕ）の生成時にキャンセルされてしまうような第１任意元Ｘ（ｉ）を、意図的に生成できない。また、例えば、整数ｄ（ｐ）が、第２任意元Ｘ（ｊ）に応じて値が定まる整数であった場合、整数ｄ（ｐ）の値は、第２任意元Ｘ（ｊ）が定まるまで特定できないため、鍵共有装置１０−ｊ又はそれに成り済ました攻撃者は、鍵共有相手である鍵共有装置１０−ｉによる共有元σ（ｕ）の生成時にキャンセルされてしまうような第２任意元Ｘ（ｊ）を意図的に生成できない。以上により、安全性がより向上する。

また、共有元生成部１６−ｉが、複数種類の共有元σ（１），．．．σ（Ｕ）（Ｕ≧２）を生成し、鍵生成部１７−ｉが、複数種類の共有元σ（１），．．．σ（Ｕ）に基づいて値が定まる鍵Ｋを生成してもよい。この場合、より安全性が向上する。

〔第１実施形態〕
次に、本発明の第１実施形態を説明する。第１実施形態では、Ｐ＝２であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）であり、ｗ（ｕ，ｐ）がａ（ｐ）とｒ（ｐ）との線形和である。また、第１鍵共有装置の記憶部が、少なくとも、秘密値ａ（ｉ）と公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇとを格納し、第１鍵共有装置の共有元生成部が、少なくとも、秘密値ａ（ｉ）と、公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇと、任意値ｒ（ｉ）と、第２任意元Ｘ（ｊ）＝ｇ^ｒ（ｊ）∈Ｇとを用い、巡回群Ｇの元ｇ^Ｗ（ｕ）∈Ｇを共有元σ（ｕ）として生成する。また、第２鍵共有装置の記憶部が、少なくとも、秘密値ａ（ｊ）と公開値Ａ（ｉ）＝ｇ^ａ（ｉ）∈Ｇとを格納し、第２鍵共有装置の共有元生成部が、少なくとも、秘密値ａ（ｊ）と、公開値Ａ（ｉ）＝ｇ^ａ（ｉ）∈Ｇと、任意値ｒ（ｊ）と、第１任意元Ｘ（ｉ）＝ｇ^ｒ（ｉ）∈Ｇとを用い、巡回群Ｇの元ｇ^Ｗ（ｕ）∈Ｇを共有元σ（ｕ）として生成する。

＜構成＞
図２は、第１実施形態の鍵共有システム１００の構成を説明するためのブロック図である。なお、図２では、鍵共有装置間で情報をやり取りするための手段であるネットワークや可搬型の記録媒体の記載は省略してある（他の図でも同様）。

図２に例示するように、第１実施形態の鍵共有システム１００は、鍵共有装置１１０−１（第１鍵共有装置）と鍵共有装置１１０−２（第２鍵共有装置）とを有する。

鍵共有装置１１０−１は、記憶部１１１−１と、任意値生成部１１２−１と、任意元生成部１１３−１と、出力部１１４−１と、入力部１１５−１と、共有元生成部１１６−１と、鍵生成部１１７−１と、一時メモリ１１８−１と、制御部１１９−１とを有する。図３（Ａ）は、共有元生成部１１６−１の構成を説明するためのブロック図である。図３（Ａ）に例示するように、共有元生成部１１６−１は、ハッシュ演算部１１６ｂ−１，１１６ｃ−１と、共有元演算部１１６ａ−ｕ−１（ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数）とを有する。

図２に例示するように、鍵共有装置１１０−２は、記憶部１１１−２と、任意値生成部１１２−２と、任意元生成部１１３−２と、出力部１１４−２と、入力部１１５−２と、共有元生成部１１６−２と、鍵生成部１１７−２と、一時メモリ１１８−２と、制御部１１９−２とを有する。図３（Ｂ）は、共有元生成部１１６−２の構成を説明するためのブロック図である。図３（Ｂ）に例示するように、共有元生成部１１６−２は、ハッシュ演算部１１６ｂ−２，１１６ｃ−２と、共有元演算部１１６ａ−ｕ−２（ｕ∈｛１，．．．，Ｕ｝）とを有する。

なお、鍵共有装置１１０−１，２は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read-Only Memoryなどを備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。すなわち、任意値生成部１１２−１，２、任意元生成部１１３−１，２、共有元生成部１１６−１，２、鍵生成部１１７−１，２及び制御部１１９−１，２は、例えば、ＣＰＵが所定のプログラムを実行することで構成される処理部である。また、任意値生成部１１２−１，２を公知の乱数生成用ＩＣ(integrated Circuit)で構成するなど、処理部の少なくとも一部を集積回路で構成してもよい。また、記憶部１１１−１，２及び一時メモリ１１８−１，２は、例えば、ＲＡＭ、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。また、出力部１１４−１，２及び入力部１１５−１，２は、例えば、モデム、ＬＡＮ（Local Area Network）カード等の通信装置や、記録媒体に情報を読み書きするリーダライタなどである。

また、鍵共有装置１１０−１，２は、それぞれ、制御部１１９−１，２の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時メモリ１１８−１，２又は記憶部１１１−１，２に格納される。一時メモリ１１８−１，２又は記憶部１１１−１，２に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。

＜公開パラメータ＞
第１実施形態では、以下を公開パラメータとする。

Ｇ：Ｌビット（Ｌ≧１）の位数ｑ（ｑは素数）の巡回群。巡回群Ｇでの演算は可換である。巡回群Ｇの具体例は、ｑを法とした剰余類の乗法群や、楕円曲線上の点からなる部分群などである。

ｇ：巡回群Ｇの生成元。ｇ^ｍ（ｍは整数）によって巡回群Ｇのすべての元を表現できる。なお、ｇ^α∈Ｇは、生成元ｇに対し、巡回群Ｇ上で定義された演算をα回（αは整数）実行することを意味する。例えば、巡回群Ｇがｐを法とした剰余類の乗法群の場合、巡回群Ｇ上で定義された演算はｐを法とした剰余乗算であり、ｇ^α∈Ｇはｇ^α ｍｏｄ ｐとなる。また、巡回群Ｇが楕円曲線上の部分群である場合、巡回群Ｇ上で定義された演算は楕円曲線上の楕円加算であり、ｇ^α∈Ｇは楕円曲線上の点である生成元ｇに対する楕円曲線上でのα倍演算となる。

Ｆ：Ｇ→［０，ｑ^１／２］。巡回群Ｇの元を０以上ｑ^１／２以下の整数に写すハッシュ関数。

Ｈ：｛０，１｝^＊→｛０，１｝^Ｌ。任意長のビット列をＬビットのビット列に写すハッシュ関数。

ＩＤ（ｐｒｏｔ）：鍵交換方式の名称の識別子。

＜事前処理＞
鍵共有処理の事前処理として以下の処理が実行される。

鍵共有装置１１０−１の記憶部１１１−１に、鍵共有装置１１０−１の秘密値（秘密鍵）ａ（１）∈Ｚ_ｑと、鍵共有装置１１０−１に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（１）＝ｇ^ａ（１）∈Ｇと、鍵共有装置１１０−２に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（２）＝ｇ^ａ（２）∈Ｇと、鍵共有装置１１０−１の識別子ＩＤ（１）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。また、鍵共有装置１１０−２の記憶部１１１−２に、鍵共有装置１１０−２の秘密値（秘密鍵）ａ（２）∈Ｚ_ｑと、鍵共有装置１１０−１に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（１）＝ｇ^ａ（１）∈Ｇと、鍵共有装置１１０−２に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（２）＝ｇ^ａ（２）∈Ｇと、鍵共有装置１１０−２の識別子ＩＤ（２）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。なお、Ｚ_ｑは、法ｑについての整数の剰余環を意味し、その一例は０以上ｑ−１以下の整数から構成される有限集合である。また、識別子ＩＤ（１），ＩＤ（２）は、例えば、メールアドレス、電話番号などである。

＜鍵共有処理＞
図４（Ａ）は、鍵共有装置１１０−１の鍵共有処理を説明するためのフローチャートであり、図４（Ｂ）は、鍵共有装置１１０−２の鍵共有処理を説明するためのフローチャートである。

鍵共有装置１１０−１（図２）の任意値生成部１１２−１は、任意値ｒ（１）∈Ｚ_ｑを生成して出力する（図４（Ａ）／ステップＳ１１２−１）。なお、任意値ｒ（１）∈Ｚ_ｑは、例えば、公知の擬似乱数生成アルゴリズムを用いて生成された擬似乱数や、予め定められた順序でＺ_ｑから選択された値である。任意元生成部１１３−１には、任意値ｒ（１）∈Ｚ_ｑが入力され、任意元生成部１１３−１は、任意値ｒ（１）を用い、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇを生成して出力する（ステップＳ１１３−１）。任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと記憶部１１１−１から読み出された識別子ＩＤ（１）とが出力部１１４−１に入力され、出力部１１４−１は、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと識別子ＩＤ（１）とを出力（ネットワークへの送信や可搬型記録媒体への格納など）する（ステップＳ１１４−１）。任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと識別子ＩＤ（１）とは、鍵共有装置１１０−２に送られる。

一方、鍵共有装置１１０−２（図２）の任意値生成部１１２−２は、任意値ｒ（２）∈Ｚ_ｑを生成して出力する（図４（Ｂ）／ステップＳ１１２−２）。なお、任意値ｒ（２）∈Ｚ_ｑは、例えば、公知の擬似乱数生成アルゴリズムを用いて生成された擬似乱数や、予め定められた順序でＺ_ｑから選択された値である。任意元生成部１１３−２には、任意値ｒ（２）∈Ｚ_ｑが入力され、任意元生成部１１３−２は、任意値ｒ（２）を用い、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇを生成して出力する（ステップＳ１１３−２）。任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと記憶部１１１−２から読み出された識別子ＩＤ（２）とが出力部１１４−２に入力され、出力部１１４−２は、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと識別子ＩＤ（２）とを出力（ネットワークへの送信や可搬型記録媒体への格納など）する（ステップＳ１１４−２）。任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと識別子ＩＤ（２）とは、鍵共有装置１１０−１に送られる。

鍵共有装置１１０−１の入力部１１５−１には、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと識別子ＩＤ（２）とが入力される（図４（Ａ）／ステップＳ１１５−１）。任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇは共有元生成部１１６−１に送られ、識別子ＩＤ（２）は記憶部１１１−１に格納される。

共有元生成部１１６−１には、入力部１１５−１から送られた任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、記憶部１１１−１から読み出された秘密値ａ（１）及び公開値Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値生成部１１２−１で生成（ステップＳ１１２−１）された任意値ｒ（１）∈Ｚ_ｑと、任意元生成部１１３−１で生成（ステップＳ１１３−１）された任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇとが入力される。共有元生成部１１６−１は、これらを用い、巡回群Ｇの元ｇ^Ｗ（ｕ）∈Ｇ（ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数）を共有元σ（ｕ）として生成して出力する（ステップＳ１１６−１）。本形態では、
W(u)=w(u,1)・w(u,2)∈Z_q …(3)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Z_q …(4)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Z_q …(5)
を満たすｇ^Ｗ（ｕ）∈Ｇが、共有元σ（ｕ）として生成される。ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚ_ｑはｕごとに定まる定数又は変数である。ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚ_ｑ及びＵの設定は任意でよいが、すべてのｕについてｓ（ｕ，１）とｔ（ｕ，１）とや、ｓ（ｕ，２）とｔ（ｕ，２）とが、必ず０となる設定は好ましくない。以下に、ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚ_ｑ及びＵの設定例と、そのときのステップＳ１１６−１の処理とを例示する。

［ステップＳ１１６−１の例］
本形態では、
Ｕ=2 …(6)
s(1,1)=1, t(1,1)=1, s(1,2)=1, t(1,2)=d(2) …(7)
s(2,1)=1, t(2,1)=d(1), s(2,2)=1, t(2,2)=1 …(8)
としたステップＳ１１６−１の処理を例示する。すなわち、
σ(1)=g^{(r(1)+a(1))(r(2)+a(2)・ｄ(2))} …(9)
σ(2)=g^{(r(1)+a(1)・d(1))(r(2)+a(2))} …(10)
とした場合の例を示す。

この場合のステップＳ１１６−１では、ハッシュ演算部１１６ｂ−１（図３（Ａ））が、任意元Ｘ（１）を入力として、ハッシュ値（第１任意元Ｘ（ｉ）に応じて値が定まる整数）
d(1)=F(X(1)) …(11)
を生成して出力する。また、ハッシュ演算部１１６ｃ−１が、任意元Ｘ（２）を入力として、ハッシュ値（第２任意元Ｘ（ｊ）に応じて値が定まる整数）
d(2)=F(X(2)) …(12)
を生成して出力する。

共有元演算部１１６ａ−１−１（図３（Ａ））は、ハッシュ値ｄ（２）と、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、秘密値ａ（１）と、公開値Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(1)=(X(2)・A(2)^ｄ(2))^r(1)+a(1)∈G …(13)
=(g^r(2)・g^{a(2)・ｄ(2)})^r(1)+a(1)
=g^{(r(1)+a(1))(r(2)+a(2)・ｄ(2))}
を生成して出力する。共有元演算部１１６ａ−２−１は、ハッシュ値ｄ（１）と、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、秘密値ａ（１）と、公開値Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(2)=(X(2)・A(2))^{r(1)+a(1)・d(1)}∈G …(14)
=(g^r(2)・g^a(2))^{r(1)+a(1)・d(1)}
=g^{(r(1)+a(1)・d(1))(r(2)+a(2))}
を生成して出力する（［ステップＳ１１６−１の例］の説明終わり）。

鍵生成部１１７−１（図２）は、少なくとも、共有元生成部１１６−１から出力された共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成して出力する（図４（Ａ）／ステップＳ１１７−１）。本形態の例では、鍵生成部１１７−１に、共有元生成部１１６−１で生成された共有元σ（ｕ）と、任意元生成部１１３−１で生成された任意元Ｘ（１）（ステップＳ１１３−１）と、入力部１１５−１に入力された任意元Ｘ（２）（ステップＳ１１５−１）と、記憶部１１１−１から読み出した公開値Ａ（１），Ａ（２）、識別子ＩＤ（１），ＩＤ（２），ＩＤ（ｐｒｏｔ）とが入力される。鍵生成部１１７−１は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot)) …(14')
として生成し、生成した鍵Ｋを出力する。

一方、鍵共有装置１１０−２の入力部１１５−２には、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと識別子ＩＤ（１）とが入力される（図４（Ｂ）／ステップＳ１１５−２）。任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇは共有元生成部１１６−２に送られ、識別子ＩＤ（１）は記憶部１１１−２に格納される。

共有元生成部１１６−２には、入力部１１５−２から送られた任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと、記憶部１１１−２から読み出された秘密値ａ（２）及び公開値Ａ（１）＝ｇ^ａ（１）∈Ｇと、任意値生成部１１２−２で生成（図４（Ｂ）／ステップＳ１１２−２）された任意値ｒ（２）∈Ｚ_ｑと、任意元生成部１１３−２で生成（ステップＳ１１３−２）された任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇが入力される。共有元生成部１１６−２は、これらを用い、巡回群Ｇの元ｇ^Ｗ（ｕ）∈Ｇ（ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数）を共有元σ（ｕ）として生成して出力する（ステップＳ１１６−２）。本形態では、鍵共有装置１１０−１と同じ、前述の式(3)〜(5)を満たすｇ^Ｗ（ｕ）∈Ｇが、共有元σ（ｕ）として生成される。以下に、ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚ_ｑ及びＵの設定例と、そのときのステップＳ１１６−２の処理とを例示する。

［ステップＳ１１６−２の例］
本形態では、鍵共有装置１１０−１と同じ、前述の式(6)〜(10)を満たす共有元σ（ｕ）を生成する。

この場合のステップＳ１１６−２では、ハッシュ演算部１１６ｂ−２（図３（Ｂ））が、任意元Ｘ（１）を入力として、ハッシュ値（第１任意元Ｘ（ｉ）に応じて値が定まる整数）
d(1)=F(X(1)) …(15)
を生成して出力する。また、ハッシュ演算部１１６ｃ−２が、任意元Ｘ（２）を入力として、ハッシュ値（第２任意元Ｘ（ｊ）に応じて値が定まる整数）
d(2)=F(X(2)) …(16)
を生成して出力する。

共有元演算部１１６ａ−１−２（図３（Ｂ））は、ハッシュ値ｄ（２）と、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと、秘密値ａ（２）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(1)=(X(1)・A(1))^{r(2)+a(2)・ｄ(2)}∈G …(17)
=(ｇ^ｒ（１）・ｇ^ａ（１）)^{r(2)+a(2)・ｄ(2)}
=g^{(r(1)+a(1))(r(2)+a(2)・ｄ(2))}
を生成して出力する。また、共有元演算部１１６ａ−２−２は、ハッシュ値ｄ（１）と、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと、秘密値ａ（２）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(2)=(X(1)・A(1)^ｄ(1))^r(2)+a(2)∈G …(18)
=(g^r(1)・g^{a(1)・ｄ(1)})^r(2)+a(2)
=g^{(r(1)+a(1)・d(1))(r(2)+a(2))}
を生成して出力する（［ステップＳ１１６−２の例］の説明終わり）。

鍵生成部１１７−２（図２）は、少なくとも、共有元生成部１１６−２から出力された共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成して出力する（ステップ図４（Ｂ）／Ｓ１１７−２）。本形態の例では、鍵生成部１１７−２に、共有元生成部１１６−２で生成された共有元σ（ｕ）と、任意元生成部１１３−２で生成された任意元Ｘ（２）（ステップＳ１１３−２）と、入力部１１５−２に入力された任意元Ｘ（１）（ステップＳ１１５−２）と、記憶部２１１−２から読み出した公開値Ａ（１），Ａ（２）、識別子ＩＤ（１），ＩＤ（２），ＩＤ（ｐｒｏｔ）とが入力される。鍵生成部１１７−２は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot)) …(19)
として生成し、生成した鍵Ｋを出力する。

＜本形態の特徴＞
式(13)(14)(17)(18)の変形結果を見ればわかるように、鍵共有装置１１６−１，２でそれぞれ生成される共有元σ（１）は同一となり、かつ、鍵共有装置１１６−１，２でそれぞれ生成される共有元σ（２）は同一となる。そして、式(14')(19)を比べれば分かるように、鍵共有装置１１６−１，２でそれぞれ生成される鍵Ｋは同一となる。

ここで、鍵共有装置１１６−１が式(13)(14)の共有元σ（１），σ（２）を計算できるのは、鍵共有装置１１６−１が自らの秘密値ａ（１）と任意値ｒ（１）とを知っているからである。鍵共有装置１１６−２の秘密値ａ（２）を知っている攻撃者は、鍵共有装置１１６−１に成り済まして任意値ｒ（１）や任意元Ｘ（１）を生成することはできても、秘密値ａ（１）を知らないため、式(13)(14)の共有元σ（１），σ（２）を計算できない。

また、鍵共有装置１１６−２が式(17)(18)の共有元σ（１），σ（２）を計算できるのは、鍵共有装置１１６−２が自らの秘密値ａ（２）と任意値ｒ（２）とを知っているからである。鍵共有装置１１６−１の秘密値ａ（１）を知っている攻撃者は、鍵共有装置１１６−２に成り済まして任意値ｒ（２）や任意元Ｘ（２）を生成することはできても、秘密値ａ（２）を知らないため、式(17)(18)の共有元σ（１），σ（２）を計算できない。よって、本形態の方式に対して攻撃者がＫＣＩ攻撃を行うことは困難である。

また、本形態では、式(11)(12)(15)(16)によって、任意元Ｘ（１）又は任意元Ｘ（２）に応じて値が定まる整数ｄ（１），ｄ（２）を生成し、これらを用いて式(13)(14)(17)(18)のように共有元σ（１），σ（２）を生成した。そのため、本形態では、高い安全性を確保できる。

すなわち、整数ｄ（１）は任意元Ｘ（１）に応じて値が定まる整数であるため、整数ｄ（１）の値は、任意元Ｘ（１）が定まるまで特定できない。そのため、鍵共有装置１１０−１又はそれに成り済ました攻撃者は、鍵共有装置１１０−２による共有元σ（ｕ）の生成時にキャンセルされてしまうような任意元Ｘ（１）を、意図的に生成できない。例えば、整数ｄ（１）＝１に固定されている場合に、鍵共有装置１１０−１又はそれに成り済ました攻撃者が任意元としてＸ（１）＝１／Ａ（１）を鍵共有装置１１０−２に送った場合、鍵共有装置１１０−２によって生成される共有元σ（１），σ（２）はいずれも１∈Ｇとなってしまう。これに対し、任意元Ｘ（１）に応じて値が定まる整数ｄ（１）を用いた場合には、このような攻撃はできない。なお、任意元Ｘ（１）が得られるまで整数ｄ（１）の値を推測することが困難である場合には、より高い安全性を確保できる。同様に、整数ｄ（２）は任意元Ｘ（２）に応じて値が定まる整数であるため、整数ｄ（２）の値は、任意元Ｘ（２）が定まるまで特定できない。そのため、鍵共有装置１１０−２又はそれに成り済ました攻撃者は、鍵共有装置１１０−１による共有元σ（ｕ）の生成時にキャンセルされてしまうような任意元Ｘ（２）を、意図的に生成できない。任意元Ｘ（２）が得られるまで整数ｄ（２）の値を推測することが困難である場合には、より高い安全性を確保できる。

また、本形態では、複数の共有元σ（１），σ（２）を生成することとしたため、高い安全性を確保できる。

〔第１実施形態の変形例１〕
第１実施形態の変形例１は、ステップＳ１１６−１，２の共有元σ（ｕ）の生成処理の変形例である。第１実施形態の変形例１では、式(7)〜(10)の代わりに、
s(1,1)=1, t(1,1)=1, s(1,2)=1, t(1,2)=1 …(19')
s(2,1)=1, t(2,1)=d(1), s(2,2)=1, t(2,2)=d(2) …(20)
とする。すなわち、
σ(1)=g^{(r(1)+a(1))(r(2)+a(2))} …(21)
σ(2)=g^{(r(1)+a(1)・d(1))(r(2)+a(2)・ｄ(2))} …(22)
を満たす共有元σ（ｕ）を生成する。

この場合、共有元演算部１１６ａ−１−１，１１６ａ−２−１（図３（Ａ））が、式(13)(14)の代わりに、共有元
σ(1)=(X(2)・A(2))^r(1)+a(1)∈G …(23)
=g^{(r(1)+a(1))(r(2)+a(2))}
σ(2)=(X(2)・A(2)^d(2))^{r(1)+a(1)・d(1)}∈G …(24)
=g^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))}
を生成して出力する。

また、共有元演算部１１６ａ−１−２，１１６ａ−２−２（図３（Ｂ））が、式(17)(18)の代わりに、共有元
σ(1)=(X(1)・A(1))^r(2)+a(2)∈G …(25)
=g^{(r(1)+a(1))(r(2)+a(2))}
σ(2)=(X(1)・A(1)^ｄ(1))^{r(2)+a(2)・ｄ(2)}∈G …(26)
=g^{(r(1)+a(1)・d(1))(r(2)+a(2)・ｄ(2))}
を生成して出力する。その他は第１実施形態と同様である。

その他、Ｕ＝１として、式(7)〜(10)の代わりに、
s(1,1)=1, t(1,1)=d(1), s(1,2)=1, t(1,2)=d(2)
、すなわち、
σ(1)=g^{(r(1)+a(1)・d(1))(r(2)+a(2)・ｄ(2))}
を満たす共有元σ（ｕ）を生成する構成でもよい。その他、Ｕ≧３の構成、ハッシュ値ｄ（１）又はｄ（２）の一方のみを用いて共有元σ（ｕ）を生成する構成、任意元Ｘ（１）と任意元Ｘ（２）の両方に依存するハッシュ値ｄ（３）を用いて共有元σ（ｕ）を生成する構成、ハッシュ値ｄ（１），ｄ（２）を用いずに共有元σ（ｕ）を生成する構成なども可能である。また、ｄ（ｐ）は、ハッシュ値に限定されず、任意元Ｘ（１）及び／又は任意元Ｘ（２）に応じて値が定まる整数であればよい。例えば、任意元Ｘ（１）や任意元Ｘ（２）の一部のビットをｄ（ｐ）としてもよいし、任意元Ｘ（１）と任意元Ｘ（２）とのビット結合値の一部をｄ（ｐ）としてもよい。また、
ｒ（ｉ）＝Ｆ’（ｒ’（ｉ），ａ（ｉ））
としてもよい。なお、Ｆ’は、ハッシュ関数Ｆ’：｛０，１｝^*→Ｚ_ｑであり、ｒ’（ｉ）は乱数である。ｒ（ｊ）についても同様な変形を行ってもよい。これによってＵ＝１の場合でも高い安全性を確保できる。その他、本発明の趣旨を遺脱しない範囲で共有元σ（ｕ）の生成方法を変形可能である。

〔第１実施形態の変形例２〕
第１実施形態の変形例２は、ステップＳ１１７−１，２の鍵生成処理の変形例である。すなわち、第１実施形態では、式(14')(19)によって鍵Ｋを生成したが、鍵Ｋは共有元σ（ｕ）に基づいて値が定まればよい。例えば、式(14')(19)のハッシュ関数Ｈへの入力値となるσ（ｕ），Ｘ（１），Ｘ（２），Ａ（１），Ａ（２），ＩＤ（１），ＩＤ（２），ＩＤ（ｐｒｏｔ）のビット結合の順序には制限はない。また、Ｘ（１），Ｘ（２），Ａ（１），Ａ（２），ＩＤ（１），ＩＤ（２），ＩＤ（ｐｒｏｔ）の少なくとも一部が省略されてもよく、アルゴリズム識別子ＩＤ（algo）、セッション識別子ＩＤ（sess）などの他の情報がビット結合対象に加えられてもよい。例えば、
K=H(σ(1), σ(2), X(1), X(2), A(1), A(2), ID(1), ID(2))
K=H(σ(1), σ(2))
K=H(σ(1), σ(2), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot), ID(algo))
K=H(σ(1), σ(2) , X(1), X(2), ID(sess))
などを共有する鍵としてもよい。また、例えば、鍵Ｋの生成に識別子ＩＤ（１），ＩＤ（２）を用いない場合、ステップＳ１１４−１，２で鍵共有装置１１０−１，２が識別子ＩＤ（１），ＩＤ（２）を出力せず、ステップＳ１１５−１，２で鍵共有装置１１０−１，２に識別子ＩＤ（１），ＩＤ（２）が入力されなくてもよい。また、ハッシュ関数Ｈの代わりに他の関数が用いられてもよいし、ハッシュ関数を用いずに、共有元σ（ｕ）を含む値のビット結合値をそのまま鍵Ｋとしてもよい。ただし、ステップＳ１１７−１，２の鍵生成のための演算は同一でなければならない。

〔第２実施形態〕
次に、本発明の第２実施形態を説明する。第２実施形態では、Ｐ＝３、ｉ＝１、ｊ∈｛２，３｝であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）・ｗ（ｕ，３）であり、ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）との線形和である。第２実施形態では、３つの鍵共有装置で鍵の共有を行う。鍵共有装置の記憶部が、少なくとも、秘密値ａ（ｉ）とＡ（ｊ）＝ｇ^ａ（ｊ）∈Ｇとを格納し、鍵共有装置の共有元生成部が、少なくとも、秘密値ａ（ｉ）と、２つの公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇと、任意値ｒ（ｉ）と、２つの第２任意元Ｘ（ｊ）＝ｇ^ｒ（ｊ）∈Ｇと、巡回群Ｇの２つの元を巡回群Ｇ_Ｔの１つの元に写像する双線形関数である関数ｅとを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）＝ｅ（ｇ，ｇ）^Ｗ（ｕ）∈Ｇ_Ｔを共有元σ（ｕ）として生成する。

＜構成＞
図５〜７は、第２実施形態の鍵共有システム２００の構成を説明するためのブロック図である。なお、第１実施形態と共通する部分については、第１実施形態と同じ符号を用いて説明を簡略化する。

図５に例示するように、第２実施形態の鍵共有システム２００は、鍵共有装置２１０−１（第１鍵共有装置）と鍵共有装置２１０−２（第２鍵共有装置）と鍵共有装置２１０−３（第３鍵共有装置）とを有する。

図６に例示するように、鍵共有装置２１０−１は、記憶部２１１−１と、任意値生成部１１２−１と、任意元生成部１１３−１と、出力部２１４−１と、入力部２１５−１と、共有元生成部２１６−１と、鍵生成部２１７−１と、一時メモリ１１８−１と、制御部１１９−１とを有する。図８（Ａ）は、共有元生成部２１６−１の構成を説明するためのブロック図である。図８（Ａ）に例示するように、共有元生成部２１６−１は、ハッシュ演算部１１６ｂ−１，１１６ｃ−１，２１６ｄ−１と、共有元演算部２１６ａ−ｕ−１（ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数）とを有する。

鍵共有装置２１０−２は、記憶部２１１−２と、任意値生成部１１２−２と、任意元生成部１１３−２と、出力部２１４−２と、入力部２１５−２と、共有元生成部２１６−２と、鍵生成部２１７−２と、一時メモリ１１８−２と、制御部１１９−２とを有する。図８（Ｂ）は、共有元生成部２１６−２の構成を説明するためのブロック図である。図８（Ｂ）に例示するように、共有元生成部２１６−２は、ハッシュ演算部１１６ｂ−２，１１６ｃ−２，２１６ｄ−２と、共有元演算部２１６ａ−ｕ−２（ｕ∈｛１，．．．，Ｕ｝）とを有する。

図７に例示するように、鍵共有装置２１０−３は、記憶部２１１−３と、任意値生成部２１２−３と、任意元生成部２１３−３と、出力部２１４−３と、入力部２１５−３と、共有元生成部２１６−３と、鍵生成部２１７−３と、一時メモリ２１８−３と、制御部２１９−３とを有する。図９は、共有元生成部２１６−３の構成を説明するためのブロック図である。図９に例示するように、共有元生成部２１６−３は、ハッシュ演算部２１６ｂ−３，２１６ｃ−３，２１６ｄ−３と、共有元演算部２１６ａ−ｕ−３（ｕ∈｛１，．．．，Ｕ｝）とを有する。

なお、第１実施形態と同様、鍵共有装置２１０−１，２，３は、例えば、公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、鍵共有装置２１０−１，２，３は、それぞれ、制御部１１９−１，２、制御部２１９−３の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時メモリ１１８−１，２、一時メモリ２１８−３又は記憶部１１１−１，２、記憶部２１１−３に格納される。一時メモリ１１８−１，２、一時メモリ２１８−３又は記憶部１１１−１，２、記憶部２１１−３に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。

＜公開パラメータ＞
第２実施形態では、以下を公開パラメータとする。

Ｇ：Ｌビットの位数ｑ（ｑは素数）の巡回群。

Ｇ_Ｔ：Ｌビットの位数ｑの巡回群。

ｇ：巡回群Ｇの生成元。

ｇ_Ｔ：巡回群Ｇ_Ｔの生成元。ｇ_Ｔ ^ｍ（ｍは整数）によって巡回群Ｇ_Ｔのすべての元を表現できる。ｇ_Ｔ＝ｅ（ｇ，ｇ）。

ｅ：ｅ（α，β）→γ（α，β∈Ｇ，γ∈Ｇ_Ｔ）。巡回群Ｇの２つの元を巡回群Ｇ_Ｔの１つの元に写像する双線形関数。双線形関数ｅは、以下の性質を満たす。

［双線形性］すべてのα，β∈Ｇ及びν，κ∈Z_qについて以下の関係を満たす。

e(α^ν,β^κ)=e(α,β)^ν・κ …(27)
［非退化性］すべてのα，β∈Ｇを巡回群Ｇ_Ｔの単位元に写す関数ではない。

［計算可能性］あらゆるα，β∈Ｇについてe(α,β)を効率的に計算するアルゴリズムが存在する。

なお、双線形関数ｅの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である（例えば、「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）。

Ｆ：Ｇ→［０，ｑ^１／２］。巡回群Ｇの元を０以上ｑ^１／２以下の整数に写すハッシュ関数。

Ｈ：｛０，１｝^＊→｛０，１｝^Ｌ。任意長のビット列をＬビットのビット列に写すハッシュ関数。

ＩＤ（ｐｒｏｔ）：鍵交換方式の名称の識別子。

＜事前処理＞
鍵共有処理の事前処理として以下の処理が実行される。

鍵共有装置２１０−１の記憶部２１１−１に、鍵共有装置２１０−１の秘密値（秘密鍵）ａ（１）∈Ｚ_ｑと、鍵共有装置２１０−１に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（１）＝ｇ^ａ（１）∈Ｇと、鍵共有装置２１０−２に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（２）＝ｇ^ａ（２）∈Ｇと、鍵共有装置２１０−３に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（３）＝ｇ^ａ（３）∈Ｇと、鍵共有装置２１０−１の識別子ＩＤ（１）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。鍵共有装置２１０−２の記憶部２１１−２に、鍵共有装置２１０−２の秘密値（秘密鍵）ａ（２）∈Ｚ_ｑと、鍵共有装置２１０−１に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（１）＝ｇ^ａ（１）∈Ｇと、鍵共有装置２１０−２に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（２）＝ｇ^ａ（２）∈Ｇと、鍵共有装置２１０−３に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（３）＝ｇ^ａ（３）∈Ｇと、鍵共有装置２１０−２の識別子ＩＤ（２）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。鍵共有装置２１０−３の記憶部２１１−３に、鍵共有装置２１０−３の秘密値（秘密鍵）ａ（３）∈Ｚ_ｑと、鍵共有装置２１０−１に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（１）＝ｇ^ａ（１）∈Ｇと、鍵共有装置２１０−２に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（２）＝ｇ^ａ（２）∈Ｇと、鍵共有装置２１０−３に対応する巡回群Ｇの元である公開値（公開鍵）Ａ（３）＝ｇ^ａ（３）∈Ｇと、鍵共有装置２１０−２の識別子ＩＤ（２）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。

＜鍵共有処理＞
図１０（Ａ）は、鍵共有装置２１０−１の鍵共有処理を説明するためのフローチャートであり、図１０（Ｂ）は、鍵共有装置２１０−２の鍵共有処理を説明するためのフローチャートである。また、図１１は、鍵共有装置２１０−３の鍵共有処理を説明するためのフローチャートである。

まず、鍵共有装置２１０−１（図６）は、第１実施形態のステップＳ１１２−１,Ｓ１１３−１の処理を実行する。これによって得られた任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと、記憶部１１１−１から読み出された識別子ＩＤ（１）とが出力部２１４−１に入力され、出力部２１４−１は、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと識別子ＩＤ（１）とを出力（ネットワークへの送信や可搬型記録媒体への格納など）する（図１０（Ａ）／ステップＳ２１４−１）。任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと識別子ＩＤ（１）とは、鍵共有装置２１０−２，２１０−３に送られる。

また、鍵共有装置２１０−２（図６）は、第１実施形態のステップＳ１１２−２,Ｓ１１３−２の処理を実行する。これによって得られた任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、記憶部１１１−２から読み出された識別子ＩＤ（２）とが出力部２１４−２に入力され、出力部２１４−２は、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと識別子ＩＤ（２）とを出力（ネットワークへの送信や可搬型記録媒体への格納など）する（図１０（Ｂ）／ステップＳ２１４−２）。任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと識別子ＩＤ（２）とは、鍵共有装置２１０−１，２１０−３に送られる。

鍵共有装置２１０−３（図７）の任意値生成部２１２−２は、任意値ｒ（３）∈Ｚ_ｑを生成して出力する（図１１／ステップＳ２１２−３）。なお、任意値ｒ（３）∈Ｚ_ｑは、例えば、公知の擬似乱数生成アルゴリズムを用いて生成された擬似乱数や、予め定められた順序でＺ_ｑから選択された値である。任意元生成部２１３−３には、任意値ｒ（３）∈Ｚ_ｑが入力され、任意元生成部２１３−３は、任意値ｒ（３）を用い、任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇを生成して出力する（ステップＳ２１３−３）。任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇと記憶部２１１−３から読み出された識別子ＩＤ（３）とが出力部２１４−３に入力され、出力部２１４−３は、任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇと識別子ＩＤ（３）とを出力（ネットワークへの送信や可搬型記録媒体への格納など）する（ステップＳ２１４−３）。任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇと識別子ＩＤ（３）とは、鍵共有装置２１０−１，２１０−２に送られる。

鍵共有装置２１０−１（図６）の入力部２１５−１には、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと識別子ＩＤ（２）とが入力され（図１０（Ａ）／ステップＳ１１５−１）、任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇと識別子ＩＤ（３）とが入力される（ステップＳ２１５−１）。任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇは共有元生成部２１６−１に送られ、識別子ＩＤ（２），ＩＤ（３）は記憶部２１１−１に格納される。

共有元生成部２１６−１には、入力部２１５−１から送られた任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、記憶部２１１−１から読み出された秘密値ａ（１）及び公開値Ａ（２）＝ｇ^ａ（２）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値生成部１１２−１で生成（ステップＳ１１２−１）された任意値ｒ（１）∈Ｚ_ｑと、任意元生成部１１３−１で生成（ステップＳ１１３−１）された任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇが入力される。共有元生成部２１６−１は、これらと巡回群Ｇの元を巡回群Ｇ_Ｔの元に写像する前述の関数ｅを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔ（ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数）を共有元σ（ｕ）として生成して出力する（ステップＳ２１６−１）。本形態では、
W(u)=w(u,1)・w(u,2)・w(u,3)∈Z_q …(28)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Z_q …(29)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Z_q …(30)
w(u,3)=(r(3)・s(u,3)+a(3)・t(u,3))∈Z_q …(31)
を満たすｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔが、共有元σ（ｕ）として生成される。ｓ（ｕ，１），ｓ（ｕ，２），ｓ（ｕ，３），ｔ（ｕ，１），ｔ（ｕ，２），ｔ（ｕ，３）∈Ｚ_ｑはｕごとに定まる定数又は変数である。ｓ（ｕ，１），ｓ（ｕ，２），ｓ（ｕ，３），ｔ（ｕ，１），ｔ（ｕ，２），ｔ（ｕ，３）∈Ｚ_ｑ及びＵの設定は任意でよいが、すべてのｕについて、ｓ（ｕ，１）とｔ（ｕ，１）とや、ｓ（ｕ，２）とｔ（ｕ，２）とや、ｓ（ｕ，３）とｔ（ｕ，３）とが、必ず０となる設定は好ましくない。以下に、ｓ（ｕ，１），ｓ（ｕ，２），ｓ（ｕ，３），ｔ（ｕ，１），ｔ（ｕ，２），ｔ（ｕ，３）∈Ｚ_ｑ及びＵの設定例と、そのときのステップＳ２１６−１の処理とを例示する。

［ステップＳ２１６−１の例］
本形態では、
Ｕ=４ …(32)
s(1,1)=1, t(1,1)=d(1), s(1,2)=1, t(1,2)=1, s(1,3)=1, t(1,3)=1 …(33)
s(2,1)=1, t(2,1)=1, s(2,2)=1, t(2,2)=d(2), s(2,3)=1, t(2,3)=1 …(34)
s(3,1)=1, t(3,1)=1, s(3,2)=1, t(3,2)=1, s(3,3)=1, t(3,3)=d(3) …(35)
s(4,1)=1, t(4,1)=d(1), s(4,2)=1, t(4,2)=d(2), s(4,3)=1, t(4,3)=d(3) …(36)
としたステップＳ２１６−１の処理を例示する。すなわち、
σ(1)=g^{(r(1)+a(1)・ｄ(1))(r(2)+a(2))(r(3)+a(3))} …(37)
σ(2)=g^{(r(1)+a(1))(r(2)+a(2)・ｄ(2))(r(3)+a(3))} …(38)
σ(3)=g^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・ｄ(3))} …(39)
σ(4)=g^{(r(1)+a(1)・ｄ(1))(r(2)+a(2)・ｄ(2))(r(3)+a(3)・ｄ(3))} …(40)
とした場合の例を示す。

この場合のステップＳ２１６−１では、ハッシュ演算部１１６ｂ−１，１１６ｃ−１（図８（Ａ））が、第１実施形態と同様に、ハッシュ値
d(1)=F(X(1)) …(41)
d(2)=F(X(2)) …(42)
を生成して出力する。また、ハッシュ演算部２１６ｄ−１が、任意元Ｘ（３）を入力として、ハッシュ値（第２任意元Ｘ（ｊ）に応じて値が定まる整数）
d(3)=F(X(3)) …(43)
を生成して出力する。

共有元演算部２１６ａ−１−１（図８（Ａ））は、ハッシュ値ｄ（１）と、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、秘密値ａ（１）と、公開値Ａ（２）＝ｇ^ａ（２）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(1)=e(X(2)・A(2),X(3)・A(3))^{r(1)+a(1)・d(1)}∈G …(44)
=e(g^r(2)・g^a(2),g^r(3)・g^a(3))^{r(1)+a(1)・d(1)}
=e(g,g)^{(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3))} （式(27)より）
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3))} （g_T=e(g,g)より）
を生成して出力する。

共有元演算部２１６ａ−２−１は、ハッシュ値ｄ（２）と、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、秘密値ａ（１）と、公開値Ａ（２）＝ｇ^ａ（２）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(2)=e(X(2)・A(2)^d(2),X(3)・A(3))^r(1)+a(1)∈G …(45)
=e(g^r(2)・g^a(2)・d(2),g^r(3)・g^a(3))^r(1)+a(1)
=e(g,g)^{(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3))} （式(27)より）
=g_T ^{(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3))} （g_T=e(g,g)より）
を生成して出力する。

共有元演算部２１６ａ−３−１は、ハッシュ値ｄ（３）と、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、秘密値ａ（１）と、公開値Ａ（２）＝ｇ^ａ（２）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(3)=e(X(2)・A(2),X(3)・A(3)^d(3))^r(1)+a(1)∈G …(46)
=e(g^r(2)・g^a(2),g^r(3)・g^a(3)・d(3))^r(1)+a(1)
=e(g,g)^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3))} （式(27)より）
=g_T ^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3))} （g_T=e(g,g)より）
を生成して出力する。

共有元演算部２１６ａ−４−１は、ハッシュ値ｄ（１），ｄ（２），ｄ（３）と、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、秘密値ａ（１）と、公開値Ａ（２）＝ｇ^ａ（２）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(4)=e(X(2)・A(2)^d(2),X(3)・A(3)^d(3))^{r(1)+a(1)・d(1)}∈G …(47)
=e(g^r(2)・g^a(2)・d(2),g^r(3)・g^a(3)・d(3))^{r(1)+a(1)・d(1)}
=e(g,g)^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))} （式(27)より）
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))} （g_T=e(g,g)より）
を生成して出力する（［ステップＳ２１６−１の例］の説明終わり）。

鍵生成部２１７−１（図６）は、少なくとも、共有元生成部２１６−１から出力された共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成して出力する（ステップ図１０（Ａ）／Ｓ２１７−１）。本形態の例では、鍵生成部２１７−１に、共有元生成部２１６−１で生成された共有元σ（ｕ）と、任意元生成部１１３−１で生成された任意元Ｘ（１）（ステップＳ１１３−１）と、入力部２１５−１に入力された任意元Ｘ（２），Ｘ（３）（ステップＳ１１５−１，Ｓ２１５−１）と、記憶部２１１−１から読み出した公開値Ａ（１），Ａ（２），Ａ（３）、識別子ＩＤ（１），ＩＤ（２），ＩＤ（３），ＩＤ（ｐｒｏｔ）とが入力される。鍵生成部２１７−１は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), σ(4), X(1), X(2), X(3), A(1), A(2), A(3), ID(1), ID(2), ID(3), ID(prot)) …(48)
として生成し、生成した鍵Ｋを出力する。

鍵共有装置２１０−２（図６）の入力部２１５−２には、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと識別子ＩＤ（１）とが入力され（図１０（Ｂ）／ステップＳ１１５−２）、任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇと識別子ＩＤ（３）とが入力される（ステップＳ２１５−２）。任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇと任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇは共有元生成部２１６−２に送られ、識別子ＩＤ（１），ＩＤ（３）は記憶部２１１−２に格納される。

共有元生成部２１６−２には、入力部２１５−２から送られた任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、記憶部２１１−２から読み出された秘密値ａ（２）及び公開値Ａ（１）＝ｇ^ａ（２）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値生成部１１２−２で生成（ステップＳ１１２−２）された任意値ｒ（２）∈Ｚ_ｑと任意元生成部１１３−１で生成（ステップＳ１１３−２）された任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇが入力される。共有元生成部２１６−２は、これらと巡回群Ｇの元を巡回群Ｇ_Ｔの元に写像する前述の関数ｅを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔ（ｕ∈｛１，．．．，Ｕ｝）を共有元σ（ｕ）として生成して出力する（ステップＳ２１６−２）。本形態では、式(28)〜(31)を満たすｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔが、共有元σ（ｕ）として生成される。以下に、ｓ（ｕ，１），ｓ（ｕ，２），ｓ（ｕ，３），ｔ（ｕ，１），ｔ（ｕ，２），ｔ（ｕ，３）∈Ｚ_ｑ及びＵの設定例と、そのときのステップＳ２１６−２の処理とを例示する。

［ステップＳ２１６−２の例］
本形態では、前述の式(32)〜(40)を満たす共有元σ（ｕ）を生成する。

この場合のステップＳ２１６−２では、ハッシュ演算部１１６ｂ−２，１１６ｃ−２，２１６ｄ−２（図８（Ｂ））が、ハッシュ演算部１１６ｂ−１，１１６ｃ−１，２１６ｄ−１と同様に、ハッシュ値
d(1)=F(X(1)) …(49)
d(2)=F(X(2)) …(50)
d(3)=F(X(3)) …(51)
を生成して出力する。

共有元演算部２１６ａ−１−１（図８（Ｂ））は、ハッシュ値ｄ（１）と、任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、秘密値ａ（２）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(1)=e(X(3)・A(3),X(1)・A(1)^d(1))^r(2)+a(2)∈G …(52)
=e(g^r(3)・g^a(3),g^r(1)・g^a(1)・d(1))^r(2)+a(2)
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3))}
を生成して出力する。

共有元演算部２１６ａ−２−２は、ハッシュ値ｄ（２）と、任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、秘密値ａ（２）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(2)=e(X(3)・A(3),X(1)・A(1))^{r(2)+a(2)・d(2)}∈G …(53)
=e(g^r(3)・g^a(3),g^r(1)・g^a(1))^{r(2)+a(2)・d(2)}
=g_T ^{(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3))}
を生成して出力する。

共有元演算部２１６ａ−３−２は、ハッシュ値ｄ（３）と、任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、秘密値ａ（２）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(3)=e(X(3)・A(3)^d(3),X(1)・A(1))^r(2)+a(2)∈G …(54)
=e(g^r(3)・g^a(3)・d(3),g^r(1)・g^a(1))^r(2)+a(2)
=g_T ^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3))}
を生成して出力する。

共有元演算部２１６ａ−４−２は、ハッシュ値ｄ（１），ｄ（２），ｄ（３）と、任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇ，Ｘ（３）＝ｇ^ｒ（３）∈Ｇと、秘密値ａ（２）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇ，Ａ（３）＝ｇ^ａ（３）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(4)=e(X(3)・A(3)^d(3),X(1)・A(1)^d(1))^{r(2)+a(2)・d(2)}∈G …(55)
=e(g^r(3)・g^a(3)・d(3),g^r(1)・g^a(1)・d(1))^{r(2)+a(2)・d(2)}
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))}
を生成して出力する（［ステップＳ２１６−２の例］の説明終わり）。

鍵生成部２１７−２（図６）は、少なくとも、共有元生成部２１６−２から出力された共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成して出力する（ステップ図１０（Ｂ）／Ｓ２１７−２）。本形態の例では、鍵生成部２１７−２に、共有元生成部２１６−２で生成された共有元σ（ｕ）と、任意元生成部１１３−２で生成された任意元Ｘ（２）（ステップＳ１１３−２）と、入力部２１５−２に入力された任意元Ｘ（１），Ｘ（３）（ステップＳ１１５−２，Ｓ２１５−２）と、記憶部２１１−２から読み出した公開値Ａ（１），Ａ（２），Ａ（３）、識別子ＩＤ（１），ＩＤ（２），ＩＤ（３），ＩＤ（ｐｒｏｔ）とが入力される。鍵生成部２１７−２は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), σ(4), X(1), X(2), X(3), A(1), A(2), A(3), ID(1), ID(2), ID(3), ID(prot)) …(56)
として生成し、生成した鍵Ｋを出力する。

鍵共有装置２１０−２（図７）の入力部２１５−３には、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと識別子ＩＤ（１）とが入力され（図１１／ステップＳ２１５ａ−３）、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと識別子ＩＤ（２）とが入力される（ステップＳ２１５ｂ−３）。任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇと任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇは共有元生成部２１６−３に送られ、識別子ＩＤ（１），ＩＤ（２）は記憶部２１１−３に格納される。

共有元生成部２１６−３には、入力部２１５−３から送られた任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇ，Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、記憶部２１１−３から読み出された秘密値ａ（３）及び公開値Ａ（１）＝ｇ^ａ（２）∈Ｇ，Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値生成部２１２−３で生成（ステップＳ２１２−３）された任意値ｒ（３）∈Ｚ_ｑと、任意元生成部２１３−３で生成（ステップＳ２１３−３）された任意元Ｘ（３）＝ｇ^ｒ（３）∈Ｇが入力される。共有元生成部２１６−３は、これらと巡回群Ｇの元を巡回群Ｇ_Ｔの元に写像する前述の関数ｅを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔ（ｕ∈｛１，．．．，Ｕ｝）を共有元σ（ｕ）として生成して出力する（ステップＳ２１６−３）。本形態では、式(28)〜(31)を満たすｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔが、共有元σ（ｕ）として生成される。以下に、ｓ（ｕ，１），ｓ（ｕ，２），ｓ（ｕ，３），ｔ（ｕ，１），ｔ（ｕ，２），ｔ（ｕ，３）∈Ｚ_ｑ及びＵの設定例と、そのときのステップＳ２１６−３の処理とを例示する。

［ステップＳ２１６−３の例］
本形態では、前述の式(32)〜(40)を満たす共有元σ（ｕ）を生成する。

この場合のステップＳ２１６−３では、ハッシュ演算部２１６ｂ−３，２１６ｃ−３，２１６ｄ−３（図９）が、ハッシュ演算部１１６ｂ−１，１１６ｃ−１，２１６ｄ−１と同様に、ハッシュ値
d(1)=F(X(1)) …(57)
d(2)=F(X(2)) …(58)
d(3)=F(X(3)) …(59)
を生成して出力する。

共有元演算部２１６ａ−１−３（図９）は、ハッシュ値ｄ（１）と、任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇ，Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、秘密値ａ（３）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇ，Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値ｒ（３）∈Ｚ_ｑとを入力とし、共有元
σ(1)=e(X(1)・A(1)^d(1),X(2)・A(2))^r(3)+a(3)∈G …(60)
=e(g^r(1)・g^a(1)・d(1),g^r(2)・g^a(2))^r(3)+a(3)
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3))}
を生成して出力する。

共有元演算部２１６ａ−２−３は、ハッシュ値ｄ（２）と、任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇ，Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、秘密値ａ（３）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇ，Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値ｒ（３）∈Ｚ_ｑとを入力とし、共有元
σ(2)=e(X(1)・A(1),X(2)・A(2)^d(2))^r(3)+a(3)∈G …(61)
=e(g^r(1)・g^a(1),g^r(2)・g^a(2)・d(2))^r(3)+a(3)
=g_T ^{(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3))}
を生成して出力する。

共有元演算部２１６ａ−３−３は、ハッシュ値ｄ（３）と、任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇ，Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、秘密値ａ（３）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇ，Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値ｒ（３）∈Ｚ_ｑとを入力とし、共有元
σ(3)=e(X(1)・A(1),X(2)・A(2))^{r(3)+a(3)・d(3)}∈G …(62)
=e(g^r(1)・g^a(1),g^r(2)・g^a(2))^{r(3)+a(3)・d(3)}
=g_T ^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3))}
を生成して出力する。

共有元演算部２１６ａ−４−３は、ハッシュ値ｄ（１），ｄ（２），ｄ（３）と、任意元Ｘ（１）＝ｇ^ｒ（２）∈Ｇ，Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、秘密値ａ（３）と、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇ，Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値ｒ（３）∈Ｚ_ｑとを入力とし、共有元
σ(4)=e(X(1)・A(1)^d(1),X(2)・A(2)^d(2))^{r(3)+a(3)・d(3)}∈G …(63)
=e(g^r(1)・g^a(1)・d(1),g^r(2)・g^a(2)・d(2))^{r(3)+a(3)・d(3)}
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))}
を生成して出力する（［ステップＳ２１６−３の例］の説明終わり）。

鍵生成部２１７−３（図７）は、少なくとも、共有元生成部２１６−３から出力された共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成して出力する（ステップ図１１／Ｓ２１７−３）。

本形態の例では、鍵生成部２１７−３に、共有元生成部２１６−３で生成された共有元σ（ｕ）と、任意元生成部２１３−３で生成された任意元Ｘ（３）（ステップＳ２１３−３）と、入力部２１５−３に入力された任意元Ｘ（１），Ｘ（２）（ステップＳ２１５ａ−３，Ｓ２１５ｂ−３）と、記憶部２１１−３から読み出した公開値Ａ（１），Ａ（２），Ａ（３）、識別子ＩＤ（１），ＩＤ（２），ＩＤ（３），ＩＤ（ｐｒｏｔ）とが入力される。鍵生成部２１７−３は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), σ(4), X(1), X(2), X(3), A(1), A(2), A(3), ID(1), ID(2), ID(3), ID(prot)) …(64)
として生成し、生成した鍵Ｋを出力する。

＜本形態の特徴＞
式(44)〜(47)(52)〜(55)(60)〜(63)の変形結果を見ればわかるように、鍵共有装置２１６−１，２，３でそれぞれ生成される共有元σ（１）は同一となり、鍵共有装置２１６−１，２，３でそれぞれ生成される共有元σ（２）は同一となり、鍵共有装置２１６−１，２，３でそれぞれ生成される共有元σ（３）は同一となり、鍵共有装置２１６−１，２，３でそれぞれ生成される共有元σ（４）は同一となる。そして、式(48)(56)(64)を比べれば分かるように、鍵共有装置２１６−１，２，３でそれぞれ生成される鍵Ｋは同一となる。

ここで、鍵共有装置２１６−１が、それぞれ式(44)〜(47)の共有元σ（１），σ（２），σ（３），σ（４）を計算できるのは、鍵共有装置２１６−１が自らの秘密値ａ（１）と任意値ｒ（１）とを知っているからである。鍵共有装置２１６−２の秘密値ａ（２）を知っている攻撃者は、鍵共有装置２１６−１に成り済まして任意値ｒ（１）や任意元Ｘ（１）を生成することはできても、秘密値ａ（１）を知らないため、式(44)〜(47)の共有元σ（１），σ（２），σ（３），σ（４）を計算できない。同様なことは、鍵共有装置２１６−２，３についてもいえる。よって、本形態の方式に対して攻撃者がＫＣＩ攻撃を行うことは困難である。

また、本形態では、任意元Ｘ（１），Ｘ（２），Ｘ（３）に応じて値が定まる整数ｄ（１），ｄ（２），ｄ（３）を生成し、これらを用いて共有元σ（１），σ（２），σ（３），σ（４）を生成した。そのため、本形態では、高い安全性を確保できる。

また、本形態では、複数の共有元σ（１），σ（２），σ（３），σ（４）を生成することとしたため、高い安全性を確保できる。

〔第２実施形態の変形例１〕
第２実施形態の変形例１は、ステップＳ２１６−１，２，３の共有元σ（ｕ）の生成処理の変形例である。第２実施形態の変形例１では、式(33)〜(40)の代わりに、
s(1,1)=1, t(1,1)=1, s(1,2)=1, t(1,2)=d(2), s(1,3)=1, t(1,3)=d(3) …(64')
s(2,1)=1, t(2,1)=d(1), s(2,2)=1, t(2,2)=1, s(2,3)=1, t(2,3)=d(3) …(65)
s(3,1)=1, t(3,1)=d(1), s(3,2)=1, t(3,2)=d(2), s(3,3)=1, t(3,3)=1 …(66)
s(4,1)=1, t(4,1)=1, s(4,2)=1, t(4,2)=1, s(4,3)=1, t(4,3)=1 …(67)
、すなわち、
σ(1)=g_T ^{(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))} …(68)
σ(2)=g_T ^{(r(1)+a(1)・ｄ(1))(r(2)+a(2))(r(3)+a(3)・d(3))} …(69)
σ(3)=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3))} …(70)
σ(4)=g_T ^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3))} …(71)
を満たす共有元σ（ｕ）を生成する。

この場合、共有元演算部２１６ａ−１−１〜２１６ａ−４−１（図８（Ａ））は、式(44)〜(47)の代わりに、共有元
σ(1)=e(X(2)・A(2)^d(2),X(3)・A(3)^d(3))^r(1)+a(1)∈G …(72)
=g_T ^{(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))}
σ(2)=e(X(2)・A(2),X(3)・A(3)^d(3))^{r(1)+a(1)・d(1)}∈G …(73)
=g_T ^{(r(1)+a(1)・ｄ(1))(r(2)+a(2))(r(3)+a(3)・d(3))}
σ(3)=e(X(2)・A(2)^d(2),X(3)・A(3))^{r(1)+a(1)・d(1)}∈G …(74)
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3))}
σ(4)=e(X(2)・A(2),X(3)・A(3))^r(1)+a(1)∈G …(75)
=g_T ^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3))}
を生成して出力する。

また、共有元演算部２１６ａ−１−２〜２１６ａ−４−２（図８（Ｂ））が、式(52)〜(55)の代わりに、共有元
σ(1)=e(X(3)・A(3)^d(3),X(1)・A(1))^{r(2)+a(2)・d(2)}∈G …(76)
=g_T ^{(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))}
σ(2)=e_T(X(3)・A(3)^d(3),X(1)・A(1)^d(1))^r(2)+a(2)∈G …(77)
=g_T ^{(r(1)+a(1)・ｄ(1))(r(2)+a(2))(r(3)+a(3)・d(3))}
σ(3)=e(X(3)・A(3),X(1)・A(1)^・d(1))^{r(2)+a(2)・d(2)}∈G …(78)
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3))}
σ(4)=e(X(3)・A(3),X(1)・A(1))^r(2)+a(2)∈G …(79)
=g_T ^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3))}
を生成して出力する。

また、共有元演算部２１６ａ−１−３〜２１６ａ−４−３（図９）が、式(60)〜(63)の代わりに、共有元
σ(1)=e(X(1)・A(1),X(2)・A(2)^d(2))^{r(3)+a(3)・d(3)}∈G …(80)
=g_T ^{(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))}
σ(2)=e(X(1)・A(1)^d(1),X(2)・A(2))^{r(3)+a(3)・d(3)}∈G …(81)
=g_T ^{(r(1)+a(1)・ｄ(1))(r(2)+a(2))(r(3)+a(3)・d(3))}
σ(3)=e(X(1)・A(1)^・d(1),X(2)・A(2)^d(2))^r(3)+a(3)∈G …(82)
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3))}
σ(4)=e(X(1)・A(1),X(2)・A(2))^r(3)+a(3)∈G …(83)
=g_T ^{(r(1)+a(1))(r(2)+a(2))(r(3)+a(3))}
を生成して出力する。

また、例えば、Ｕ＝１として、式(33)〜(40)の代わりに、
σ(1)=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))}
としてもよい。その他、Ｕ＝２，３やＵ≧５の構成、ハッシュ値ｄ（１）〜ｄ（３）の一部のみを用いて共有元σ（ｕ）を生成する構成、複数の任意元Ｘ（１），Ｘ（２），Ｘ（３）に依存するハッシュ値を用いて共有元σ（ｕ）を生成する構成、ハッシュ値ｄ（１）〜ｄ（３）を用いずに共有元σ（ｕ）を生成する構成なども可能である。また、ｄ（ｐ）は、ハッシュ値に限定されず、任意元Ｘ（１）及び／又は任意元Ｘ（２）及び／又は任意元Ｘ（３）に応じて値が定まる整数であればよい。例えば、任意元Ｘ（１）や任意元Ｘ（２）や任意元Ｘ（３）の一部のビットをｄ（ｐ）としてもよいし、これらの任意元の一部をビット結合したビット列の一部をｄ（ｐ）としてもよい。また、
ｒ（ｉ）＝Ｆ’（ｒ’（ｉ），ａ（ｉ））
としてもよい。なお、Ｆ’は、ハッシュ関数Ｆ’：｛０，１｝^*→Ｚ_ｑであり、ｒ’（ｉ）は乱数である。ｒ（ｊ）についても同様な変形を行ってもよい。これによってＵ＝１の場合でも高い安全性を確保できる。その他、本発明の趣旨を遺脱しない範囲で共有元σ（ｕ）の生成方法を変形可能である。

〔第２実施形態の変形例２〕
第１実施形態の変形例２と同様、第２実施形態でも、鍵Ｋは共有元σ（ｕ）に基づいて値が定まればよく、第１実施形態の変形例２で述べたように鍵Ｋの生成方法を変形してもよい。

〔第３実施形態〕
次に、本発明の第３実施形態を説明する。第３実施形態では、ＩＤベース暗号方式を応用した形態であり、Ｐ＝２であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）・ＭＳＫであり、ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）との線形和である。第１鍵共有装置の記憶部が、少なくとも、元Ｚ（ｉ）＝ｇ^{ａ（ｉ）・ＭＳＫ}∈Ｇと、公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇと、巡回群Ｇの元ＭＰＫ＝ｇ^ＭＳＫ∈Ｇとを格納し、第１鍵共有装置の共有元生成部が、少なくとも、元Ｚ（ｉ）＝ｇ^{ａ（ｉ）・ＭＳＫ}∈Ｇと、公開値Ａ（ｊ）＝ｇ^ａ（ｊ）∈Ｇと、任意値ｒ（ｉ）と、任意元Ｘ（ｊ）＝ｇ^ｒ（ｊ）∈Ｇと、ＭＰＫ＝ｇ^ＭＳＫ∈Ｇと、巡回群Ｇの２つの元を巡回群Ｇ_Ｔの１つの元に写像する双線形関数である関数ｅとを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）＝ｅ（ｇ，ｇ）^Ｗ（ｕ）∈Ｇ_Ｔを共有元σ（ｕ）として生成する。また、第２鍵共有装置の記憶部が、少なくとも、元Ｚ（ｊ）＝ｇ^{ａ（ｊ）・ＭＳＫ}∈Ｇと、公開値Ａ（ｉ）＝ｇ^ａ（ｉ）∈Ｇと、巡回群Ｇの元ＭＰＫ＝ｇ^ＭＳＫ∈Ｇとを格納し、第２鍵共有装置の共有元生成部が、少なくとも、元Ｚ（ｊ）＝ｇ^{ａ（ｊ）・ＭＳＫ}∈Ｇと、公開値Ａ（ｉ）＝ｇ^ａ（ｉ）∈Ｇと、任意値ｒ（ｊ）と、任意元Ｘ（ｉ）＝ｇ^ｒ（ｉ）∈Ｇと、ＭＰＫ＝ｇ^ＭＳＫ∈Ｇと、巡回群Ｇの２つの元を巡回群Ｇ_Ｔの１つの元に写像する双線形関数である関数ｅとを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）＝ｅ（ｇ，ｇ）^Ｗ（ｕ）∈Ｇ_Ｔを共有元σ（ｕ）として生成する。

＜構成＞
図１２，１３は、第３実施形態の鍵共有システム３００の構成を説明するためのブロック図である。なお、第１実施形態と共通する部分については、第１実施形態と同じ符号を用いて説明を簡略化する。

図１２に例示するように、第３実施形態の鍵共有システム３００は、鍵共有装置３１０−１（第１鍵共有装置）と鍵共有装置３１０−２（第２鍵共有装置）とを有する。鍵共有装置３１０−１及び鍵共有装置３１０−２は、鍵生成装置３３０との情報のやり取りが可能に構成される。なお、この情報のやり取りは、ネットワーク経由で行われるものに限定されず、例えば、ＵＳＢメモリなどの可搬型の記録媒体への情報の読み書きによって行われてもよい。

図１３に例示するように、鍵共有装置３１０−１は、記憶部１１１−１と、任意値生成部１１２−１と、任意元生成部１１３−１と、出力部１１４−１と、入力部１１５−１と、共有元生成部３１６−１と、鍵生成部３１７−１と、一時メモリ１１８−１と、制御部１１９−１とを有する。図１４（Ａ）は、共有元生成部３１６−１の構成を説明するためのブロック図である。図１４（Ａ）に例示するように、共有元生成部３１６−１は、ハッシュ演算部１１６ｂ−１，１１６ｃ−１と、共有元演算部３１６ａ−ｕ−１（ｕ∈｛１，．．．，Ｕ｝），３１６ｂ−１とを有する。

図１３に例示するように、鍵共有装置３１０−２は、記憶部１１１−２と、任意値生成部１１２−２と、任意元生成部１１３−２と、出力部１１４−２と、入力部１１５−２と、共有元生成部３１６−２と、鍵生成部３１７−２と、一時メモリ１１８−２と、制御部１１９−２とを有する。図１４（Ｂ）は、共有元生成部３１６−２の構成を説明するためのブロック図である。図１４（Ｂ）に例示するように、共有元生成部３１６−２は、ハッシュ演算部１１６ｂ−２，１１６ｃ−２と、共有元演算部３１６ａ−ｕ−２（ｕ∈｛１，．．．，Ｕ｝），３１６ｂ−２とを有する。

なお、第１実施形態と同様、鍵共有装置３１０−１，２は、例えば、公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、鍵共有装置３１０−１，２は、それぞれ、制御部１１９−１，２の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時メモリ１１８−１，２又は記憶部１１１−１，２に格納される。一時メモリ１１８−１，２又は記憶部１１１−１，２に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。

＜公開パラメータ＞
第３実施形態では、以下を公開パラメータとする。

Ｇ：Ｌビットの位数ｑ（ｑは素数）の巡回群。

Ｇ_Ｔ：Ｌビットの位数ｑの巡回群。

ｇ：巡回群Ｇの生成元。

ｇ_Ｔ：巡回群Ｇ_Ｔの生成元。

ｅ：ｅ（α，β）→γ（α，β∈Ｇ，γ∈Ｇ_Ｔ）。巡回群Ｇの２つの元を巡回群Ｇ_Ｔの１つの元に写像する双線形関数。

Ｆ：Ｇ→［０，ｑ^１／２］。巡回群Ｇの元を０以上ｑ^１／２以下の整数に写すハッシュ関数。

Ｈ：｛０，１｝^＊→｛０，１｝^Ｌ。任意長のビット列をＬビットのビット列に写すハッシュ関数。

Ｙ：｛０，１｝^＊→Ｇ。任意長のビット列を巡回群Ｇに写すハッシュ関数。

ＩＤ（ｐｒｏｔ）：鍵交換方式の名称の識別子。

ＭＰＫ：ＩＤベース暗号方式のマスタ公開鍵。なお、ＭＰＫ＝ｇ^ＭＳＫ∈Ｇ（ＭＳＫ∈Ｚ_ｑはＩＤベース暗号方式のマスタ秘密鍵）を満たす。

＜事前処理＞
鍵生成装置３３０の記憶部にはマスタ秘密鍵ＭＳＫ∈Ｚ_ｑが安全に格納されている。鍵生成装置３３０は、鍵共有装置３１０−１の識別子ＩＤ（１）を用い、鍵共有装置３１０−１の秘密鍵
Z(1)=Y(ID(1))^MSK∈G …(84)
を生成する。ここで、
A(1)=Y(ID(1))=g^a(1)∈G …(85)
とおくと、式(84)は、
Z(1)=g^a(1)・MSK∈G …(86)
となる。秘密鍵Z(1)は、鍵共有装置３１０−１に送られ、その記憶部３１１−１に安全に格納される。

また、鍵生成装置３３０は、鍵共有装置３１０−２の識別子ＩＤ（２）を用い、鍵共有装置３１０−２の秘密鍵
Z(2)=Y(ID(2))^MSK∈G …(87)
を生成する。ここで、
A(2)=Y(ID(2))=g^a(2)∈G …(88)
とおくと、式(87)は、
Z(2)=g^a(2)・MSK∈G …(89)
となる。秘密鍵Z(2)は、鍵共有装置３１０−２に送られ、その記憶部３１１−２に安全に格納される。

また、鍵共有装置２１０−１の記憶部２１１−１に、マスタ公開鍵ＭＰＫ＝ｇ^ＭＳＫ∈Ｇと、鍵共有装置２１０−１に対応する巡回群Ｇの元である公開値Ａ（１）＝Ｙ（ＩＤ（１））＝ｇ^ａ（１）∈Ｇと、鍵共有装置２１０−２に対応する巡回群Ｇの元である公開値Ａ（２）＝Ｙ（ＩＤ（２））＝ｇ^ａ（２）∈Ｇと、鍵共有装置２１０−１の識別子ＩＤ（１）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。鍵共有装置２１０−２の記憶部２１１−２に、マスタ公開鍵ＭＰＫ＝ｇ^ＭＳＫ∈Ｇと、鍵共有装置２１０−１に対応する巡回群Ｇの元である公開値Ａ（１）＝Ｙ（ＩＤ（１））＝ｇ^ａ（１）∈Ｇと、鍵共有装置２１０−２に対応する巡回群Ｇの元である公開値Ａ（２）＝Ｙ（ＩＤ（２））＝ｇ^ａ（２）∈Ｇと、鍵共有装置２１０−２の識別子ＩＤ（２）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。

＜鍵共有処理＞
図１５（Ａ）は、鍵共有装置３１０−１の鍵共有処理を説明するためのフローチャートであり、図１５（Ｂ）は、鍵共有装置３１０−２の鍵共有処理を説明するためのフローチャートである。

図１５（Ａ）に示すように、鍵共有装置３１０−１（図１３）は、第１実施形態のステップＳ１１２−１〜Ｓ１１５−１の処理を実行する。

共有装置３１０−１の共有元生成部３１６−１には、入力部１１５−１に入力された任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、記憶部２１１−１から読み出された秘密鍵Ｚ（１）＝ｇ^{ａ（１）・ＭＳＫ}∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇ^ＭＳＫ∈Ｇ及び公開値Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値生成部１１２−１で生成（ステップＳ１１２−１）された任意値ｒ（１）∈Ｚ_ｑとが入力される。共有元生成部３１６−１は、これらと巡回群Ｇの元を巡回群Ｇ_Ｔの元に写像する前述の関数ｅを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔ（ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数）を共有元σ（ｕ）として生成して出力する（ステップＳ３１６ａ−１）。本形態では
W(u)=w(u,1)・w(u,2)・MSK∈Z_q …(90)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Z_q …(91)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Z_q …(92)
を満たすｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔが、共有元σ（ｕ）として生成される。ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚ_ｑはｕごとに定まる定数又は変数であり、第１実施形態と同様に設定すればよい。

以下に、ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚ_ｑ及びＵの設定例と、そのときのステップＳ３１６ａ−１の処理とを例示する。

［ステップＳ３１６ａ−１の例］
本形態では、まず、第１実施形態の式(6)〜(10)を満たす共有元σ（ｕ）を生成する。この場合、まず、第１実施形態と同様に、ハッシュ演算部１１６ｂ−１，１１６ｃ−１（図１４（Ａ））が、式(11)(12)のハッシュ値ｄ（１），ｄ（２）を生成して出力する。

共有元演算部３１６ａ−１−１（図１４（Ａ））は、ハッシュ値ｄ（２）と、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、秘密鍵Ｚ（１）＝ｇ^{ａ（１）・ＭＳＫ}∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇ^ＭＳＫ∈Ｇと、公開値Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(1)=e(MPK^r(1)・Z(1),X(2)・A(2)^d(2))∈G_T …(93)
=e(g^MSK・r(1)・g^a(1)・MSK, g^r(2)・g^a(2)・d(2))（MPK=g^MSK∈Gより）
=e(g,g)^{(r(1)+a(1))(r(2)+a(2)・d(2))MSK}（式(27)より）
=g_T ^{(r(1)+a(1))(r(2)+a(2)・ｄ(2))MSK} （g_T=e(g,g)より）
を生成して出力する。共有元演算部３１６ａ−２−１は、ハッシュ値ｄ（１）と、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、秘密鍵Ｚ（１）＝ｇ^{ａ（１）・ＭＳＫ}∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇ^ＭＳＫ∈Ｇと、公開値Ａ（２）＝ｇ^ａ（２）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(2)=e(MPK^r(1)・Z(1)^d(1), X(2)・A(2))∈G_T …(94)
=e(g^MSK・r(1)・g^{a(1)・MSK・d(1)}, g^r(2)・g^a(2))（MPK=g^MSK∈Gより）
=e(g,g)^{(r(1)+a(1)・d(1))(r(2)+a(2))MSK}（式(27)より）
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2))MSK}（g_T=e(g,g)より）
を生成して出力する（［ステップＳ３１６ａ−１の例］の説明終わり）。

また、共有元生成部３１６−１の共有元演算部３１６ｂ−１が、任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇと、任意値ｒ（１）∈Ｚ_ｑとを入力とし、共有元
σ(3)=X(2)^r(1)∈G …(95)
=g^r(2)・r(1)
を生成する（ステップＳ３１６ｂ−１）。なお、本形態はＵ＝２の例である。

鍵生成部３１７−１（図１３）は、少なくとも、共有元生成部３１６−１から出力された共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成して出力する（ステップ図１５（Ａ）／Ｓ２１７−１）。本形態の例では、鍵生成部３１７−１に、共有元生成部３１６−１で生成された共有元σ（１）, σ（２）, σ（３）と、任意元生成部１１３−１で生成された任意元Ｘ（１）（ステップＳ１１３−１）と、入力部１１５−１に入力された任意元Ｘ（２）（ステップＳ１１５−１）と、記憶部３１１−１から読み出した公開値Ａ（１），Ａ（２）、識別子ＩＤ（１），ＩＤ（２），ＩＤ（ｐｒｏｔ）とが入力される。鍵生成部３１７−１は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot))…(96)
として生成し、生成した鍵Ｋを出力する。

一方、図１５（Ｂ）に示すように、鍵共有装置３１０−２は、第１実施形態のステップＳ１１２−２〜Ｓ１１５−２の処理を実行する。

共有装置３１０−２の共有元生成部３１６−２には、入力部１１５−２に入力された任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと、記憶部２１１−２から読み出された秘密鍵Ｚ（２）＝ｇ^{ａ（２）・ＭＳＫ}∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇ^ＭＳＫ∈Ｇ及び公開値Ａ（１）＝ｇ^ａ（１）∈Ｇと、任意値生成部１１２−２で生成（ステップＳ１１２−２）された任意値ｒ（２）∈Ｚ_ｑとが入力される。共有元生成部３１６−２は、これらと巡回群Ｇの元を巡回群Ｇ_Ｔの元に写像する前述の関数ｅを用い、巡回群Ｇ_Ｔの元ｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔ（ｕ∈｛１，．．．，Ｕ｝）を共有元σ（ｕ）として生成して出力する（ステップＳ３１６ａ−２）。本形態では、式(90)〜(92)を満たすｇ_Ｔ ^Ｗ（ｕ）∈Ｇ_Ｔが、共有元σ（ｕ）として生成される。

以下に、ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚ_ｑ及びＵの設定例と、そのときのステップＳ３１６−２の処理とを例示する。

［ステップＳ３１６ａ−２の例］
本形態では、まず、第１実施形態の式(6)〜(10)を満たす共有元σ（ｕ）を生成する。この場合、まず、第１実施形態と同様に、ハッシュ演算部１１６ｂ−２，１１６ｃ−２（図１４（Ｂ））が、式(15)(16)のハッシュ値ｄ（１），ｄ（２）を生成して出力する。

共有元演算部３１６ａ−１−２（図１４（Ｂ））は、ハッシュ値ｄ（２）と、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと、秘密鍵Ｚ（２）＝ｇ^{ａ（２）・ＭＳＫ}∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇ^ＭＳＫ∈Ｇと、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(1)=e(X(1)・A(1),MPK^r(2)・Z(2)^d(2))∈G_T …(97)
=e(g^r(1)・g^a(1),g ^MSK・r(2)・g^{a(2)・MSK・d(2)})（MPK=g^MSK∈Gより）
=e(g,g)^{(r(1)+a(1))(r(2)+a(2)・d(2))MSK}（式(27)より）
=g_T ^{(r(1)+a(1))(r(2)+a(2)・ｄ(2))MSK} （g_T=e(g,g)より）
を生成して出力する。共有元演算部３１６ａ−２−２は、ハッシュ値ｄ（１）と、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと、秘密鍵Ｚ（２）＝ｇ^{ａ（２）・ＭＳＫ}∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇ^ＭＳＫ∈Ｇと、公開値Ａ（１）＝ｇ^ａ（１）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(2)=e(X(1)・A(1)^d(1),MPK^r(2)・Z(2))∈G_T …(98)
=e(g^r(1)・g^a(1)・d(1),g^MSK・r(2)・g^a(2)・MSK)（MPK=g^MSK∈Gより）
=e(g,g)^{(r(1)+a(1)・d(1))(r(2)+a(2))MSK}（式(27)より）
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2))MSK}（g_T=e(g,g)より）
を生成して出力する（［ステップＳ３１６ａ−２の例］の説明終わり）。

また、共有元生成部３１６−２の共有元演算部３１６ｂ−２が、任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇと、任意値ｒ（２）∈Ｚ_ｑとを入力とし、共有元
σ(3)=X(1)^r(2)∈G …(99)
=g^r(1)・r(2)
を生成する（ステップＳ３１６ｂ−２）。なお、本形態はＵ＝２の例である。

鍵生成部３１７−２（図１３）は、少なくとも、共有元生成部３１６−２から出力された共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成して出力する（ステップ図１５（Ｂ）／Ｓ２１７−２）。本形態の例では、鍵生成部３１７−２に、共有元生成部３１６−２で生成された共有元σ（１）, σ（２）, σ（３）と、任意元生成部１１３−２で生成された任意元Ｘ（２）（ステップＳ１１３−２）と、入力部１１５−２に入力された任意元Ｘ（１）（ステップＳ１１５−２）と、記憶部３１１−２から読み出した公開値Ａ（１），Ａ（２）、識別子ＩＤ（１），ＩＤ（２），ＩＤ（ｐｒｏｔ）とが入力される。鍵生成部３１７−２は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot))…(100)
として生成し、生成した鍵Ｋを出力する。

＜本形態の特徴＞
式(93)〜(95)(97)〜(99)の変形結果を見ればわかるように、鍵共有装置３１６−１，２でそれぞれ生成される共有元σ（１）は同一となり、鍵共有装置３１６−１，２でそれぞれ生成される共有元σ（２）は同一となり、鍵共有装置３１６−１，２でそれぞれ生成される共有元σ（３）は同一となる。そして、式(96)(100)を比べれば分かるように、鍵共有装置３１６−１，２でそれぞれ生成される鍵Ｋは同一となる。

ここで、鍵共有装置３１６−１が、それぞれ式(93)(94)の共有元σ（１），σ（２）を計算できるのは、鍵共有装置３１６−１が自らの秘密鍵Ｚ（１）と任意値ｒ（１）とを知っているからである。鍵共有装置３１６−２の秘密鍵Ｚ（２）を知っている攻撃者は、鍵共有装置３１６−１に成り済まして任意値ｒ（１）や任意元Ｘ（１）を生成することはできても、秘密鍵Ｚ（１）を知らないため、式(93)(94)の共有元σ（１），σ（２）を計算できない。同様なことは、鍵共有装置２１６−２についてもいえる。よって、本形態の方式に対して攻撃者がＫＣＩ攻撃を行うことは困難である。

また、本形態では、任意元Ｘ（１），Ｘ（２）に応じて値が定まる整数ｄ（１），ｄ（２）を生成し、これらを用いて共有元σ（１），σ（２）を生成した。そのため、本形態では、高い安全性を確保できる。

また、本形態では、複数の共有元σ（１），σ（２）を生成することとしたため、高い安全性を確保できる。

〔第３実施形態の変形例１〕
第３実施形態の変形例１は、ステップＳ３１６ａ−１，２、Ｓ３１６ｂ−１，２の共有元σ（ｕ）の生成処理の変形例である。第３実施形態の変形例１では、式(7)〜(10)の代わりに、式(19')〜(22)を満たす共有元σ（ｕ）を生成し、共有元σ（３）は生成しない。

この場合、共有元演算部３１６ａ−１−１，３１６ａ−２−１（図１４（Ａ））が、式(93)(94)の代わりに、共有元
σ(1)=e(MPK^r(1)・Z(1),X(2)・A(2))∈G_T …(101)
=g_T ^{(r(1)+a(1))(r(2)+a(2))MSK}
σ(2)=e(MPK^r(1)・Z(1)^d(1), X(2)・A(2)^d(1))∈G_T …(102)
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK}
を生成して出力する。

また、共有元演算部３１６ａ−１−２，３１６ａ−２−２（図１４（Ｂ））が、式(98)(98)の代わりに、共有元
σ(1)=e(X(1)・A(1),MPK^r(2)・Z(2))∈G_T …(103)
=g_T ^{(r(1)+a(1))(r(2)+a(2))MSK}
σ(2)=e(X(1)・A(1)^d(1),MPK^r(2)・Z(2)^d(2))∈G_T …(104)
=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK}
を生成して出力する。また、この変形例では、共有元σ（３）は生成されない。その他は第３実施形態と同様である。

その他、例えば、Ｕ＝１として共有元
σ(1)=g_T ^{(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK}
を生成してもよい。また、例えば、第１実施形態の変形例１で説明したようなｓ（１，１），ｔ（１，１），ｓ（１，２），ｔ（１，２），ｓ（２，１），ｔ（２，１），ｓ（２，２），ｔ（２，２）やＵやｄ（ｐ）に関する変形を行ってもよい。また、
ｒ（ｉ）＝Ｆ’（ｒ’（ｉ），ａ（ｉ））
としてもよい。なお、Ｆ’は、ハッシュ関数Ｆ’：｛０，１｝^*→Ｚ_ｑであり、ｒ’（ｉ）は乱数である。ｒ（ｊ）についても同様な変形を行ってもよい。これによってＵ＝１の場合でも高い安全性を確保できる。その他、本発明の趣旨を遺脱しない範囲で共有元σ（ｕ）の生成方法を変形可能である。

〔第３実施形態の変形例２〕
第１実施形態の変形例２と同様、第３実施形態でも、鍵Ｋは共有元σ（ｕ）に基づいて値が定まればよく、第１実施形態の変形例２で述べたように鍵Ｋの生成方法を変形してもよい。

〔その他の変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各実施形態では、位数ｑを素数としたが、位数ｑが素数でなく合成数であってもよい。また、上述の各実施形態では、任意値ｒ（ｉ），ｒ（ｊ）等を法ｑについての整数の剰余環Ｚ_ｑの元としたが、各実施形態で法ｑについての整数の剰余環Ｚ_ｑの元として扱った各値が整数集合の元であってもよい。

また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。

また、各形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

本発明の利用分野としては、例えば、共通鍵暗号における共通鍵の共有、共通鍵暗号を用いた認証処理における共通鍵の共有などがある。

１，１００〜３００ 鍵共有システム
１０−１０〜Ｐ，１１０−１１０〜Ｐ，２１０−２１０〜Ｐ，３１０−３１０〜Ｐ 鍵共有装置

Claims (9)

1. 他の装置と鍵を共有する鍵共有装置であって、
   前記他の装置の公開値が巡回群Ｇの元であるＡ（２）＝ｇ^ａ（２）∈Ｇであり、ｇは巡回群Ｇの生成元であり、ＭＳＫ及びａ（２）は整数又は位数ｑのＺ _ｑ の元であり、
   整数又はＺ _ｑ の元である任意値ｒ（１）を生成する任意値生成部と、
   前記任意値ｒ（１）を用い、第１任意元Ｘ（１）＝ｇ^ｒ（１）∈Ｇを生成する任意元生成部と、
   前記第１任意元Ｘ（１）を出力する出力部と、
   第２任意元Ｘ（２）＝ｇ^ｒ（２）∈Ｇ〔ｒ（２）は整数又はＺ _ｑ の元〕が入力される入力部と、
   少なくとも、巡回群Ｇの元Ｚ（１）＝ｇ^{ａ（１）・ＭＳＫ}∈Ｇと、前記公開値Ａ（２）と、前記任意値ｒ（１）と、前記第２任意元Ｘ（２）と、巡回群Ｇの元ＭＰＫ＝ｇ ^ＭＳＫ ∈Ｇと、前記巡回群Ｇの２つの元を巡回群Ｇ _Ｔ の元に写像する双線形関数ｅとを用い、巡回群Ｇの元ｇ _Ｔ ^Ｗ（ｕ） ＝ｅ（ｇ，ｇ） ^Ｗ（ｕ） ∈Ｇ _Ｔ 〔ａ（１）は整数又はＺ _ｑ の元であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）・ＭＳＫであり、ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）との線形和、ｐ∈｛１，２｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数、ｇ_Ｔ は巡回群Ｇ_Ｔ の生成元〕を共有元σ（ｕ）として生成する共有元生成部と、
   少なくとも前記共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力する鍵生成部と、
   を有する鍵共有装置。
2. 請求項１の鍵共有装置であって、
   Ｕ≧２であり、
   前記共有元生成部は、複数種類の前記共有元σ（１），．．．σ（Ｕ）を生成する、
   ことを特徴とする鍵共有装置。
3. 他の装置と鍵を共有する鍵共有装置であって、
   前記他の装置の公開値が巡回群Ｇの元であるＡ（ｊ）＝ｇ ^ａ（ｊ） ∈Ｇであり、ｉ，ｊ∈｛１，．．．，Ｐ｝、ｊ≠ｉ、Ｐは２以上の整数定数、ｇは巡回群Ｇの生成元であり、ＭＳＫ及びａ（ｊ）は整数又は位数ｑのＺ _ｑ の元であり、
   整数又はＺ _ｑ の元である任意値ｒ（ｉ）を生成する任意値生成部と、
   前記任意値ｒ（ｉ）を用い、第１任意元Ｘ（ｉ）＝ｇ ^ｒ（ｉ） ∈Ｇを生成する任意元生成部と、
   前記第１任意元Ｘ（ｉ）を出力する出力部と、
   第２任意元Ｘ（ｊ）＝ｇ ^ｒ（ｊ） ∈Ｇ〔ｒ（ｊ）は整数又はＺ _ｑ の元〕が入力される入力部と、
   少なくとも、整数若しくはＺ _ｑ の元である秘密値ａ（ｉ）又は巡回群Ｇの元Ｚ（ｉ）＝ｇ ^{ａ（ｉ）・ＭＳＫ} ∈Ｇと、前記公開値Ａ（ｊ）と、前記任意値ｒ（ｉ）と、前記第２任意元Ｘ（ｊ）とを用い、巡回群Ｇの元ｇ ^Ｗ（ｕ） ∈Ｇ〔Ｗ（ｕ）はｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積、前記ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）とを含む複数の整数又はＺ _ｑ の元の線形和、ｐ∈｛１，．．．，Ｐ｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数〕を共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群Ｇ _Ｔ の元に写像する関数ｅを用い、巡回群Ｇ _Ｔ の元ｇ _Ｔ ^Ｗ（ｕ） ∈Ｇ _Ｔ 〔ｇ _Ｔ は巡回群Ｇ _Ｔ の生成元〕を共有元σ（ｕ）として生成する共有元生成部と、
   少なくとも前記共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力する鍵生成部と、を有し、
   ｒ（ｉ）＝Ｆ’（ｒ’（ｉ），ａ（ｉ））、ｒ（ｊ）＝Ｆ”（ｒ’（ｊ），ａ（ｊ））であり、Ｆ’およびＦ”がハッシュ関数であり、ｒ’（ｉ）およびｒ’（ｊ）が乱数である、鍵共有装置。
4. 他の装置と鍵を共有する鍵共有装置であって、
   前記他の装置の公開値が巡回群Ｇの元であるＡ（ｊ）＝ｇ ^ａ（ｊ） ∈Ｇであり、ｉ，ｊ∈｛１，．．．，Ｐ｝、ｊ≠ｉ、Ｐは２以上の整数定数、ｇは巡回群Ｇの生成元であり、ＭＳＫ及びａ（ｊ）は整数又は位数ｑのＺ _ｑ の元であり、
   整数又はＺ _ｑ の元である任意値ｒ（ｉ）を生成する任意値生成部と、
   前記任意値ｒ（ｉ）を用い、第１任意元Ｘ（ｉ）＝ｇ ^ｒ（ｉ） ∈Ｇを生成する任意元生成部と、
   前記第１任意元Ｘ（ｉ）を出力する出力部と、
   第２任意元Ｘ（ｊ）＝ｇ ^ｒ（ｊ） ∈Ｇ〔ｒ（ｊ）は整数又はＺ _ｑ の元〕が入力される入力部と、
   少なくとも、整数若しくはＺ _ｑ の元である秘密値ａ（ｉ）又は巡回群Ｇの元Ｚ（ｉ）＝ｇ ^{ａ（ｉ）・ＭＳＫ} ∈Ｇと、前記公開値Ａ（ｊ）と、前記任意値ｒ（ｉ）と、前記第２任意元Ｘ（ｊ）とを用い、巡回群Ｇの元ｇ ^Ｗ（ｕ） ∈Ｇ〔Ｗ（ｕ）はｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積、前記ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）とを含む複数の整数又はＺ _ｑ の元の線形和、ｐ∈｛１，．．．，Ｐ｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは３以上の整数定数〕を共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群Ｇ _Ｔ の元に写像する関数ｅを用い、巡回群Ｇ _Ｔ の元ｇ _Ｔ ^Ｗ（ｕ） ∈Ｇ _Ｔ 〔ｇ _Ｔ は巡回群Ｇ _Ｔ の生成元〕を共有元σ（ｕ）として生成する共有元生成部と、
   少なくとも複数種類の前記共有元σ（１），．．．σ（Ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力する鍵生成部と、
   を有する鍵共有装置。
5. 他の装置と鍵を共有する鍵共有装置の鍵共有方法であって、
   前記他の装置の公開値が巡回群Ｇの元であるＡ（２）＝ｇ ^ａ（２） ∈Ｇであり、ｇは巡回群Ｇの生成元であり、ＭＳＫ及びａ（２）は整数又は位数ｑのＺ _ｑ の元であり、
   任意値生成部で、整数又はＺ _ｑ の元である任意値ｒ（１）を生成する任意値生成ステップと、
   任意元生成部で、前記任意値ｒ（１）を用い、第１任意元Ｘ（１）＝ｇ ^ｒ（１） ∈Ｇを生成する任意元生成ステップと、
   出力部から前記第１任意元Ｘ（１）を出力する出力ステップと、
   第２任意元Ｘ（２）＝ｇ ^ｒ（２） ∈Ｇ〔ｒ（２）は整数又はＺ _ｑ の元〕が入力部に入力される入力ステップと、
   共有元生成部で、少なくとも、巡回群Ｇの元Ｚ（１）＝ｇ ^{ａ（１）・ＭＳＫ} ∈Ｇと、前記公開値Ａ（２）と、前記任意値ｒ（１）と、前記第２任意元Ｘ（２）と、巡回群Ｇの元ＭＰＫ＝ｇ ^ＭＳＫ ∈Ｇと、前記巡回群Ｇの２つの元を巡回群Ｇ _Ｔ の元に写像する双線形関数ｅとを用い、巡回群Ｇの元ｇ _Ｔ ^Ｗ（ｕ） ＝ｅ（ｇ，ｇ） ^Ｗ（ｕ） ∈Ｇ _Ｔ 〔ａ（１）は整数又はＺ _ｑ の元であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）・ＭＳＫであり、ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）との線形和、ｐ∈｛１，２｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数、ｇ _Ｔ は巡回群Ｇ _Ｔ の生成元〕を共有元σ（ｕ）として生成する共有元生成ステップと、
   鍵生成部で、少なくとも前記共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力する鍵生成ステップと、
   を有する鍵共有方法。
6. 請求項５の鍵共有方法であって、
   Ｕ≧２であり、
   前記共有元生成ステップは、複数種類の前記共有元σ（１），．．．σ（Ｕ）を生成するステップである、
   ことを特徴とする鍵共有方法。
7. 他の装置と鍵を共有する鍵共有装置の鍵共有方法であって、
   前記他の装置の公開値が巡回群Ｇの元であるＡ（ｊ）＝ｇ ^ａ（ｊ） ∈Ｇであり、ｉ，ｊ∈｛１，．．．，Ｐ｝、ｊ≠ｉ、Ｐは２以上の整数定数、ｇは巡回群Ｇの生成元であり、ＭＳＫ及びａ（ｊ）は整数又は位数ｑのＺ _ｑ の元であり、
   任意値生成部で、整数又はＺ _ｑ の元である任意値ｒ（ｉ）を生成する任意値生成ステップと、
   任意元生成部で、前記任意値ｒ（ｉ）を用い、第１任意元Ｘ（ｉ）＝ｇ ^ｒ（ｉ） ∈Ｇを生成する任意元生成ステップと、
   出力部から前記第１任意元Ｘ（ｉ）を出力する出力ステップと、
   第２任意元Ｘ（ｊ）＝ｇ ^ｒ（ｊ） ∈Ｇ〔ｒ（ｊ）は整数又はＺ _ｑ の元〕が入力部に入力される入力ステップと、
   共有元生成部で、少なくとも、整数若しくはＺ _ｑ の元である秘密値ａ（ｉ）又は巡回群Ｇの元Ｚ（ｉ）＝ｇ ^{ａ（ｉ）・ＭＳＫ} ∈Ｇと、前記公開値Ａ（ｊ）と、前記任意値ｒ（ｉ）と、前記第２任意元Ｘ（ｊ）とを用い、巡回群Ｇの元ｇ ^Ｗ（ｕ） ∈Ｇ〔Ｗ（ｕ）はｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積、前記ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）とを含む複数の整数又はＺ _ｑ の元の線形和、ｐ∈｛１，．．．，Ｐ｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数〕を共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群Ｇ _Ｔ の元に写像する関数ｅを用い、巡回群Ｇ _Ｔ の元ｇ _Ｔ ^Ｗ（ｕ） ∈Ｇ _Ｔ 〔ｇ _Ｔ は巡回群Ｇ _Ｔ の生成元〕を共有元σ（ｕ）として生成する共有元生成ステップと、
   鍵生成部で、少なくとも前記共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力する鍵生成ステップと、を有し、
   ｒ（ｉ）＝Ｆ’（ｒ’（ｉ），ａ（ｉ））、ｒ（ｊ）＝Ｆ”（ｒ’（ｊ），ａ（ｊ））であり、Ｆ’およびＦ”がハッシュ関数であり、ｒ’（ｉ）およびｒ’（ｊ）が乱数である、鍵共有方法。
8. 他の装置と鍵を共有する鍵共有装置の鍵共有方法であって、
   前記他の装置の公開値が巡回群Ｇの元であるＡ（ｊ）＝ｇ ^ａ（ｊ） ∈Ｇであり、ｉ，ｊ∈｛１，．．．，Ｐ｝、ｊ≠ｉ、Ｐは２以上の整数定数、ｇは巡回群Ｇの生成元であり、ＭＳＫ及びａ（ｊ）は整数又は位数ｑのＺ _ｑ の元であり、
   任意値生成部で、整数又はＺ _ｑ の元である任意値ｒ（ｉ）を生成する任意値生成ステップと、
   任意元生成部で、前記任意値ｒ（ｉ）を用い、第１任意元Ｘ（ｉ）＝ｇ ^ｒ（ｉ） ∈Ｇを生成する任意元生成ステップと、
   出力部から前記第１任意元Ｘ（ｉ）を出力する出力ステップと、
   第２任意元Ｘ（ｊ）＝ｇ ^ｒ（ｊ） ∈Ｇ〔ｒ（ｊ）は整数又はＺ _ｑ の元〕が入力部に入力される入力ステップと、
   共有元生成部で、少なくとも、整数若しくはＺ _ｑ の元である秘密値ａ（ｉ）又は巡回群Ｇの元Ｚ（ｉ）＝ｇ ^{ａ（ｉ）・ＭＳＫ} ∈Ｇと、前記公開値Ａ（ｊ）と、前記任意値ｒ（ｉ）と、前記第２任意元Ｘ（ｊ）とを用い、巡回群Ｇの元ｇ ^Ｗ（ｕ） ∈Ｇ〔Ｗ（ｕ）はｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積、前記ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）とを含む複数の整数又はＺ _ｑ の元の線形和、ｐ∈｛１，．．．，Ｐ｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは３以上の整数定数〕を共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群Ｇ _Ｔ の元に写像する関数ｅを用い、巡回群Ｇ _Ｔ の元ｇ _Ｔ ^Ｗ（ｕ） ∈Ｇ _Ｔ 〔ｇ _Ｔ は巡回群Ｇ _Ｔ の生成元〕を共有元σ（ｕ）として生成する共有元生成ステップと、
   鍵生成部で、少なくとも複数種類の前記共有元σ（１），．．．σ（Ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力する鍵生成ステップと、
   を有する鍵共有方法。
9. 請求項１から４の何れかの鍵共有装置としてコンピュータを機能させるためのプログラム。

Images