(57)【要約】【課題】ＫＣＩ攻撃に強い鍵共有方式を提供する。【解決手段】鍵共有装置１１０−１が、任意値ｒ（１）を生成し、Ｘ（１）＝ｇｒ（１）∈Ｇを生成する。Ｘ（１）は鍵共有装置１１０−２に入力される。鍵共有装置１１０−２が、任意値ｒ（２）を生成し、Ｘ（２）＝ｇｒ（２）∈Ｇを生成する。Ｘ（２）は鍵共有装置１１０−１に入力される。鍵共有装置１１０−１は、ａ（１）、Ａ（２）、ｒ（１）、Ｘ（２）とを用い、巡回群Ｇの元ｇＷ（ｕ）∈Ｇをσ（ｕ）として生成し、鍵共有装置１１０−２は、ａ（２）、Ａ（１）、ｒ（２）、Ｘ（１）とを用い、巡回群Ｇの元ｇＷ（ｕ）∈Ｇをσ（ｕ）として生成する。なお、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）の積であり、ｗ（ｕ，ｐ）は、ａ（ｐ）とｒ（ｐ）の線形和である。鍵共有装置１１０−１，２は、σ（ｕ）に基づいて値が定まる鍵Ｋを生成する。【選択図】図２
2011019042.tif 000002
【特許請求の範囲】
【請求項１】
他の装置と鍵を共有する鍵共有装置であって、
少なくとも、整数の秘密値ａ（ｉ）又は巡回群Ｇの元Ｚ（ｉ）＝ｇａ（ｉ）・ＭＳＫ∈Ｇと、前記他の装置に対応する巡回群Ｇの元である公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇ〔ｉ，ｊ∈｛１，．．．，Ｐ｝、ｊ≠ｉ、Ｐは２以上の整数定数、ｇはｇｍによって巡回群Ｇのすべての元を表現できる生成元、ＭＳＫ，ｍ及びａ（ｊ）は整数〕と、を格納する記憶部と、
整数の任意値ｒ（ｉ）を生成する任意値生成部と、
前記任意値ｒ（ｉ）を用い、第１任意元Ｘ（ｉ）＝ｇｒ（ｉ）∈Ｇを生成する任意元生成部と、
前記第１任意元Ｘ（ｉ）を出力する出力部と、
第２任意元Ｘ（ｊ）＝ｇｒ（ｊ）∈Ｇ〔ｒ（ｊ）は整数〕が入力される入力部と、
少なくとも、前記秘密値ａ（ｉ）又は前記元Ｚ（ｉ）＝ｇａ（ｉ）・ＭＳＫ∈Ｇと、前記公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇと、前記任意値ｒ（ｉ）と、前記第２任意元Ｘ（ｊ）＝ｇｒ（ｊ）∈Ｇとを用い、巡回群Ｇの元ｇＷ（ｕ）∈Ｇ〔Ｗ（ｕ）は整数ｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積、前記整数ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）とを含む複数の整数の線形和、ｐ∈｛１，．．．，Ｐ｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数〕を共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群ＧＴの元に写像する関数ｅを用い、巡回群ＧＴの元ｇＴＷ（ｕ）∈ＧＴ〔ｇＴはｇＴｍによって巡回群ＧＴのすべての元を表現できる生成元〕を共有元σ（ｕ）として生成する共有元生成部と、
少なくとも前記共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力する鍵生成部と、
を有する鍵共有装置。
【請求項２】
請求項１の鍵共有装置であって、
少なくとも一部の前記整数ｗ（ｕ，ｐ）は、少なくとも一方が整数ｄ（ｐ）によって重み付けされたａ（ｐ）とｒ（ｐ）とを含む複数の整数の線形和であり、
前記整数ｄ（ｐ）は、前記第１任意元Ｘ（ｉ）及び／又は前記第２任意元Ｘ（ｊ）に応じて値が定まる整数である、
ことを特徴とする鍵共有装置。
【請求項３】
請求項１又は２の鍵共有装置であって、
Ｕ≧２であり、
前記共有元生成部は、複数種類の前記共有元σ（１），．．．σ（Ｕ）を生成する、
ことを特徴とする鍵共有装置。
【請求項４】
請求項１から３の何れかの鍵共有装置であって、
Ｐ＝２であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）であり、ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）との線形和であり、
前記記憶部は、少なくとも、前記秘密値ａ（ｉ）と前記公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇとを格納し、
前記共有元生成部は、少なくとも、前記秘密値ａ（ｉ）と、前記公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇと、前記任意値ｒ（ｉ）と、前記第２任意元Ｘ（ｊ）＝ｇｒ（ｊ）∈Ｇとを用い、巡回群Ｇの元ｇＷ（ｕ）∈Ｇを前記共有元σ（ｕ）として生成する、
ことを特徴とする鍵共有装置。
【請求項５】
請求項１から３の何れかの鍵共有装置であって、
Ｐ＝３、ｉ＝１、ｊ∈｛２，３｝であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）・ｗ（ｕ，３）であり、ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）との線形和であり、前記関数ｅは、前記巡回群Ｇの２つの元を巡回群ＧＴの１つの元に写像する双線形関数であり、
前記記憶部は、少なくとも、前記秘密値ａ（ｉ）と前記公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇとを格納し、
前記共有元生成部は、少なくとも、前記秘密値ａ（ｉ）と、２つの前記公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇと、前記任意値ｒ（ｉ）と、２つの前記第２任意元Ｘ（ｊ）＝ｇｒ（ｊ）∈Ｇと、前記関数ｅとを用い、巡回群ＧＴの元ｇＴＷ（ｕ）＝ｅ（ｇ，ｇ）Ｗ（ｕ）∈ＧＴを前記共有元σ（ｕ）として生成する、
ことを特徴とする鍵共有装置。
【請求項６】
請求項１から３の何れかの鍵共有装置であって、
Ｐ＝２であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）・ＭＳＫであり、ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）との線形和であり、前記関数ｅは、前記巡回群Ｇの２つの元を巡回群ＧＴの１つの元に写像する双線形関数であり、
前記記憶部は、少なくとも、前記元Ｚ（ｉ）＝ｇａ（ｉ）・ＭＳＫ∈Ｇと、前記公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇと、巡回群Ｇの元ＭＰＫ＝ｇＭＳＫ∈Ｇと、を格納し、
前記共有元生成部は、少なくとも、前記元Ｚ（ｉ）＝ｇａ（ｉ）・ＭＳＫ∈Ｇと、前記公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇと、前記任意値ｒ（ｉ）と、前記第２任意元Ｘ（ｊ）＝ｇｒ（ｊ）∈Ｇと、前記元ＭＰＫ＝ｇＭＳＫ∈Ｇと、前記関数ｅとを用い、巡回群ＧＴの元ｇＴＷ（ｕ）＝ｅ（ｇ，ｇ）Ｗ（ｕ）∈ＧＴを前記共有元σ（ｕ）として生成する、
ことを特徴とする鍵共有装置。
【請求項７】
第１鍵共有装置と第２鍵共有装置とで鍵を共有する鍵共有システムであって、
前記第１鍵共有装置は、
少なくとも、整数の秘密値ａ（１）又は巡回群Ｇの元Ｚ（１）＝ｇａ（１）・ＭＳＫ∈Ｇと、前記第２鍵共有装置に対応する巡回群Ｇの元である公開値Ａ（２）＝ｇａ（２）∈Ｇ〔ｇはｇｍによって巡回群Ｇのすべての元を表現できる生成元、ＭＳＫ，ｍ及びａ（２）は整数〕と、を格納する第１記憶部と、
整数の任意値ｒ（１）を生成する第１任意値生成部と、
前記任意値ｒ（１）を用い、第１任意元Ｘ（１）＝ｇｒ（１）∈Ｇを生成する第１任意元生成部と、
前記第１任意元Ｘ（１）を出力する第１出力部と、
第２任意元Ｘ（２）＝ｇｒ（２）∈Ｇ〔ｒ（２）は整数〕が入力される第１入力部と、
少なくとも、前記秘密値ａ（１）又は前記元Ｚ（１）＝ｇａ（１）・ＭＳＫ∈Ｇと、前記公開値Ａ（２）＝ｇａ（２）∈Ｇと、前記任意値ｒ（１）と、前記第２任意元Ｘ（２）＝ｇｒ（２）∈Ｇとを用い、巡回群Ｇの元ｇＷ（ｕ）∈Ｇ〔Ｗ（ｕ）は整数ｗ（ｕ，１），ｗ（ｕ，２）を含む２個以上の整数の積、前記整数ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）とを含む複数の整数の線形和、ｐ∈｛１，２｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数〕を第１共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群ＧＴの元に写像する関数ｅを用い、巡回群ＧＴの元ｇＴＷ（ｕ）∈ＧＴ〔ｇＴはｇＴｍによって巡回群ＧＴのすべての元を表現できる生成元〕を第１共有元σ（ｕ）として生成する第１共有元生成部と、
少なくとも前記第１共有元σ（ｕ）に基づいて値が定まる第１鍵Ｋを生成し、当該第１鍵Ｋを出力する第１鍵生成部と、を含み、
前記第２鍵共有装置は、
少なくとも、整数の秘密値ａ（２）又は巡回群Ｇの元Ｚ（２）＝ｇａ（２）・ＭＳＫ∈Ｇと、前記第１鍵共有装置に対応する巡回群Ｇの元である公開値Ａ（１）＝ｇａ（１）∈Ｇと、を格納する第２記憶部と、
整数の任意値ｒ（２）を生成する第２任意値生成部と、
前記任意値ｒ（２）を用い、前記第２任意元Ｘ（２）＝ｇｒ（２）∈Ｇを生成する第２任意元生成部と、
前記第２任意元Ｘ（２）を出力する第２出力部と、
前記第１任意元Ｘ（１）＝ｇｒ（１）∈Ｇが入力される第２入力部と、
少なくとも、前記秘密値ａ（２）又は前記元Ｚ（２）＝ｇａ（２）・ＭＳＫ∈Ｇと、前記公開値Ａ（１）＝ｇａ（１）∈Ｇと、前記任意値ｒ（２）と、前記第２任意元Ｘ（１）＝ｇｒ（１）∈Ｇとを用い、巡回群Ｇの元ｇＷ（ｕ）∈Ｇを第２共有元σ（ｕ）として生成するか、又は、さらに前記関数ｅを用い、巡回群ＧＴの元ｇＴＷ（ｕ）∈ＧＴを第２共有元σ（ｕ）として生成する第２共有元生成部と、
少なくとも前記第２共有元σ（ｕ）に基づいて値が定まる第２鍵Ｋを生成し、当該第２鍵Ｋを出力する第２鍵生成部と、を含む、
ことを特徴とする鍵共有システム。
【請求項８】
第１鍵共有装置と第２鍵共有装置と第３鍵共有装置とで鍵を共有する鍵共有システムであって、
前記第１鍵共有装置は、
少なくとも、整数の秘密値ａ（１）と、前記第２鍵共有装置及び前記第３鍵共有装置にそれぞれ対応する巡回群Ｇの元である公開値Ａ（２）＝ｇａ（２），ｇａ（３）∈Ｇ〔ｇはｇｍによって巡回群Ｇのすべての元を表現できる生成元、ｍ，ａ（２）及びａ（３）は整数〕と、を格納する第１記憶部と、
整数の任意値ｒ（１）を生成する第１任意値生成部と、
前記任意値ｒ（１）を用い、第１任意元Ｘ（１）＝ｇｒ（１）∈Ｇを生成する第１任意元生成部と、
前記第１任意元Ｘ（１）を出力する第１出力部と、
第２任意元Ｘ（２）＝ｇｒ（２）∈Ｇ及び第３任意元Ｘ（３）＝ｇｒ（３）∈Ｇ〔ｒ（２）及びｒ（３）は整数〕が入力される第１入力部と、
少なくとも、前記秘密値ａ（１）と、前記公開値Ａ（２）＝ｇａ（２），Ａ（３）＝ｇａ（３）∈Ｇと、前記任意値ｒ（１）と、前記第２任意元Ｘ（２）＝ｇｒ（２）∈Ｇ及び前記第３任意元Ｘ（３）＝ｇｒ（３）∈Ｇと、巡回群Ｇの元を巡回群ＧＴの元に写像する関数ｅとを用い、巡回群ＧＴの元ｇＴＷ（ｕ）∈ＧＴ〔Ｗ（ｕ）は整数ｗ（ｕ，１），ｗ（ｕ，２），ｗ（ｕ，３）を含む３個以上の整数の積、前記整数ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）とを含む複数の整数の線形和、ｐ∈｛１，．．．，３｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数、ｇＴはｇＴｍによって巡回群ＧＴのすべての元を表現できる生成元〕を第１共有元σ（ｕ）として生成する第１共有元生成部と、
少なくとも前記第１共有元σ（ｕ）に基づいて値が定まる第１鍵Ｋを生成し、当該第１鍵Ｋを出力する第１鍵生成部と、を含み、
前記第２鍵共有装置は、
少なくとも、整数の秘密値ａ（２）と、前記第１鍵共有装置及び前記第３鍵共有装置にそれぞれ対応する巡回群Ｇの元である公開値Ａ（１）＝ｇａ（１），Ａ（３）＝ｇａ（３）∈Ｇと、を格納する第２記憶部と、
整数の任意値ｒ（２）を生成する第２任意値生成部と、
前記任意値ｒ（２）を用い、第２任意元Ｘ（２）＝ｇｒ（２）∈Ｇを生成する第２任意元生成部と、
前記第２任意元Ｘ（２）を出力する第２出力部と、
第１任意元Ｘ（１）＝ｇｒ（１）∈Ｇ及び第３任意元Ｘ（３）＝ｇｒ（３）∈Ｇが入力される第２入力部と、
少なくとも、前記秘密値ａ（２）と、前記公開値Ａ（１）＝ｇａ（１），Ａ（３）＝ｇａ（３）∈Ｇと、前記任意値ｒ（２）と、前記第１任意元Ｘ（１）＝ｇｒ（１）∈Ｇ及び前記第３任意元Ｘ（３）＝ｇｒ（３）∈Ｇと、前記関数ｅとを用い、巡回群ＧＴの元ｇＴＷ（ｕ）∈ＧＴを第２共有元σ（ｕ）として生成する第２共有元生成部と、
少なくとも前記第２共有元σ（ｕ）に基づいて値が定まる第２鍵Ｋを生成し、当該第２鍵Ｋを出力する第２鍵生成部と、を含み、
前記第３鍵共有装置は、
少なくとも、整数の秘密値ａ（３）と、前記第１鍵共有装置及び前記第２鍵共有装置にそれぞれ対応する巡回群Ｇの元である公開値Ａ（１）＝ｇａ（１），Ａ（２）＝ｇａ（２）∈Ｇと、を格納する第３記憶部と、
整数の任意値ｒ（３）を生成する第３任意値生成部と、
前記任意値ｒ（３）を用い、第３任意元Ｘ（３）＝ｇｒ（３）∈Ｇを生成する第３任意元生成部と、
前記第１任意元Ｘ（３）を出力する第３出力部と、
前記第１任意元Ｘ（１）＝ｇｒ（１）∈Ｇ及び前記第２任意元Ｘ（２）＝ｇｒ（２）∈Ｇが入力される第３入力部と、
少なくとも、前記秘密値ａ（３）と、前記公開値Ａ（１）＝ｇａ（１），Ａ（２）＝ｇａ（２）∈Ｇと、前記任意値ｒ（３）と、前記第１任意元Ｘ（１）＝ｇｒ（１）∈Ｇ及び前記第２任意元Ｘ（２）＝ｇｒ（２）∈Ｇと前記関数ｅとを用い、巡回群ＧＴの元ｇＴＷ（ｕ）∈ＧＴを第３共有元σ（ｕ）として生成する第３共有元生成部と、
少なくとも前記第３共有元σ（ｕ）に基づいて値が定まる第３鍵Ｋを生成し、当該第３鍵Ｋを出力する第３鍵生成部と、を含む、
ことを特徴とする鍵共有システム。
【請求項９】
記憶部と任意値生成部と任意元生成部と出力部と入力部と共有元生成部と鍵生成部とを有する鍵共有装置が他の装置と鍵を共有する鍵共有方法であって、
少なくとも、整数の秘密値ａ（ｉ）又は巡回群Ｇの元Ｚ（ｉ）＝ｇａ（ｉ）・ＭＳＫ∈Ｇと、前記他の装置に対応する巡回群Ｇの元である公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇ〔ｉ，ｊ∈｛１，．．．，Ｐ｝、ｊ≠ｉ、Ｐは２以上の整数定数、ｇはｇｍによって巡回群Ｇのすべての元を表現できる生成元、ＭＳＫ，ｍ及びａ（ｊ）は整数〕と、が前記記憶部に格納されており、
前記任意値生成部が、整数の任意値ｒ（ｉ）を生成するステップと、
前記任意元生成部が、前記任意値ｒ（ｉ）を用い、第１任意元Ｘ（ｉ）＝ｇｒ（ｉ）∈Ｇを生成するステップと、
前記出力部が、前記第１任意元Ｘ（ｉ）を出力するステップと、
前記入力部に、第２任意元Ｘ（ｊ）＝ｇｒ（ｊ）∈Ｇ〔ｒ（ｊ）は整数〕が入力されるステップと、
前記共有元生成部が、少なくとも、前記秘密値ａ（ｉ）又は前記元Ｚ（ｉ）＝ｇａ（ｉ）・ＭＳＫ∈Ｇと、前記公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇと、前記任意値ｒ（ｉ）と、前記第２任意元Ｘ（ｊ）＝ｇｒ（ｊ）∈Ｇとを用い、巡回群Ｇの元ｇＷ（ｕ）∈Ｇ〔Ｗ（ｕ）は整数ｗ（ｕ，１），．．．，ｗ（ｕ，Ｐ）を含むＰ個以上の整数の積、前記整数ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）とを含む複数の整数の線形和、ｐ∈｛１，．．．，Ｐ｝、ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数〕を共有元σ（ｕ）として生成するか、又は、さらに巡回群Ｇの元を巡回群ＧＴの元に写像する関数ｅを用い、巡回群ＧＴの元ｇＴＷ（ｕ）∈ＧＴ〔ｇＴはｇＴｍによって巡回群ＧＴのすべての元を表現できる生成元〕を共有元σ（ｕ）として生成するステップと、
前記鍵生成部が、少なくとも前記共有元σ（ｕ）に基づいて値が定まる鍵Ｋを生成し、当該鍵Ｋを出力するステップと、
を実行する鍵共有方法。
【請求項１０】
請求項１から７の何れかの鍵共有装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用に関し、特に、装置間で鍵を共有する鍵交換技術に関する。
【背景技術】
【０００２】
装置間で鍵を共有する鍵交換方式の従来技術の一つに以下の方式がある（例えば、非特許文献１参照）。
【０００３】
［公開パラメータ］
ＧをＬビット（Ｌ≧１）の位数ｑ（ｑは素数）の巡回群、ｇをＧの生成元とする。Ｈ：｛０，１｝＊→｛０，１｝Ｌを任意長のビット列をＬビットのビット列に写すハッシュ関数とする。また、ＩＤ（ａｌｇｏ）を、共有した鍵Ｋの使いかた（認証鍵、暗号化鍵など）を記述するアルゴリズム識別子とする。
【０００４】
［鍵交換］
識別子ＩＤ（１）と秘密鍵ａ（１）∈Ｚｑと公開鍵Ａ（１）＝ｇａ（１）∈Ｇをもつ装置ＰＡ（１）と、識別子ＩＤ（２）と秘密鍵ａ（２）∈Ｚｑと公開鍵Ａ（２）＝ｇａ（２）∈Ｇをもつ装置ＰＡ（２）とは、以下のようにして鍵Ｋを共有する。
【０００５】
１．装置ＰＡ（１）は、乱数ｒ（１）∈Ｚｑを生成し、識別子ＩＤ（１）とＸ（１）＝ｇｒ（１）∈Ｇを装置ＰＡ（２）に送る。
【０００６】
２．装置ＰＡ（２）は、乱数ｒ（２）∈Ｚｑを生成し、識別子ＩＤ（２）とＸ（２）＝ｇｒ（２）∈ＧをＰＡ（１）に送る。
【０００７】
３．装置ＰＡ（１）は、φ（１）＝Ｘ（２）ｒ（１）∈Ｇとφ（２）＝Ａ（２）ａ（１）∈Ｇを計算し、鍵Ｋ＝Ｈ（φ（１），φ（２），ＩＤ（１），ＩＤ（２），ＩＤ（ａｌｇｏ））を計算する。
【０００８】
４．装置ＰＡ（２）は、φ（１）＝Ｘ（１）ｒ（２）∈Ｇとφ（２）＝Ａ（１）ａ（２）∈Ｇを計算し、鍵Ｋ＝Ｈ（φ（１），φ（２），ＩＤ（１），ＩＤ（２），ＩＤ（ａｌｇｏ））を計算する。
【０００９】
ここで、巡回群Ｇでの演算は可換であるため、装置ＰＡ（１），ＰＡ（２）で生成されるφ（１），φ（２）は、いずれも、
φ(1)=gr(1)・r(2)∈G      …(1)
φ(2)=ga(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)∈Zq      …(3)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Zq      …(4)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Zq      …(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)
=(gr(2)・ga(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)
=(gr(2)・ga(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)
=(gr(1)・ga(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))
などを共有する鍵としてもよい。また、例えば、鍵Ｋの生成に識別子ＩＤ（１），ＩＤ（２）を用いない場合、ステップＳ１１４−１，２で鍵共有装置１１０−１，２が識別子ＩＤ（１），ＩＤ（２）を出力せず、ステップＳ１１５−１，２で鍵共有装置１１０−１，２に識別子ＩＤ（１），ＩＤ（２）が入力されなくてもよい。また、ハッシュ関数Ｈの代わりに他の関数が用いられてもよいし、ハッシュ関数を用いずに、共有元σ（ｕ）を含む値のビット結合値をそのまま鍵Ｋとしてもよい。ただし、ステップＳ１１７−１，２の鍵生成のための演算は同一でなければならない。
【００８０】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。第２実施形態では、Ｐ＝３、ｉ＝１、ｊ∈｛２，３｝であり、Ｗ（ｕ）＝ｗ（ｕ，１）・ｗ（ｕ，２）・ｗ（ｕ，３）であり、ｗ（ｕ，ｐ）はａ（ｐ）とｒ（ｐ）との線形和である。第２実施形態では、３つの鍵共有装置で鍵の共有を行う。鍵共有装置の記憶部が、少なくとも、秘密値ａ（ｉ）とＡ（ｊ）＝ｇａ（ｊ）∈Ｇとを格納し、鍵共有装置の共有元生成部が、少なくとも、秘密値ａ（ｉ）と、２つの公開値Ａ（ｊ）＝ｇａ（ｊ）∈Ｇと、任意値ｒ（ｉ）と、２つの第２任意元Ｘ（ｊ）＝ｇｒ（ｊ）∈Ｇと、巡回群Ｇの２つの元を巡回群ＧＴの１つの元に写像する双線形関数である関数ｅとを用い、巡回群ＧＴの元ｇＴＷ（ｕ）＝ｅ（ｇ，ｇ）Ｗ（ｕ）∈ＧＴを共有元σ（ｕ）として生成する。
【００８１】
＜構成＞
図５〜７は、第２実施形態の鍵共有システム２００の構成を説明するためのブロック図である。なお、第１実施形態と共通する部分については、第１実施形態と同じ符号を用いて説明を簡略化する。
【００８２】
図５に例示するように、第２実施形態の鍵共有システム２００は、鍵共有装置２１０−１（第１鍵共有装置）と鍵共有装置２１０−２（第２鍵共有装置）と鍵共有装置２１０−３（第３鍵共有装置）とを有する。
【００８３】
図６に例示するように、鍵共有装置２１０−１は、記憶部２１１−１と、任意値生成部１１２−１と、任意元生成部１１３−１と、出力部２１４−１と、入力部２１５−１と、共有元生成部２１６−１と、鍵生成部２１７−１と、一時メモリ１１８−１と、制御部１１９−１とを有する。図８（Ａ）は、共有元生成部２１６−１の構成を説明するためのブロック図である。図８（Ａ）に例示するように、共有元生成部２１６−１は、ハッシュ演算部１１６ｂ−１，１１６ｃ−１，２１６ｄ−１と、共有元演算部２１６ａ−ｕ−１（ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数）とを有する。
【００８４】
鍵共有装置２１０−２は、記憶部２１１−２と、任意値生成部１１２−２と、任意元生成部１１３−２と、出力部２１４−２と、入力部２１５−２と、共有元生成部２１６−２と、鍵生成部２１７−２と、一時メモリ１１８−２と、制御部１１９−２とを有する。図８（Ｂ）は、共有元生成部２１６−２の構成を説明するためのブロック図である。図８（Ｂ）に例示するように、共有元生成部２１６−２は、ハッシュ演算部１１６ｂ−２，１１６ｃ−２，２１６ｄ−２と、共有元演算部２１６ａ−ｕ−２（ｕ∈｛１，．．．，Ｕ｝）とを有する。
【００８５】
図７に例示するように、鍵共有装置２１０−３は、記憶部２１１−３と、任意値生成部２１２−３と、任意元生成部２１３−３と、出力部２１４−３と、入力部２１５−３と、共有元生成部２１６−３と、鍵生成部２１７−３と、一時メモリ２１８−３と、制御部２１９−３とを有する。図９は、共有元生成部２１６−３の構成を説明するためのブロック図である。図９に例示するように、共有元生成部２１６−３は、ハッシュ演算部２１６ｂ−３，２１６ｃ−３，２１６ｄ−３と、共有元演算部２１６ａ−ｕ−３（ｕ∈｛１，．．．，Ｕ｝）とを有する。
【００８６】
なお、第１実施形態と同様、鍵共有装置２１０−１，２，３は、例えば、公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、鍵共有装置２１０−１，２，３は、それぞれ、制御部１１９−１，２、制御部２１９−３の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時メモリ１１８−１，２、一時メモリ２１８−３又は記憶部１１１−１，２、記憶部２１１−３に格納される。一時メモリ１１８−１，２、一時メモリ２１８−３又は記憶部１１１−１，２、記憶部２１１−３に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【００８７】
＜公開パラメータ＞
第２実施形態では、以下を公開パラメータとする。
【００８８】
Ｇ：Ｌビットの位数ｑ（ｑは素数）の巡回群。
【００８９】
ＧＴ：Ｌビットの位数ｑの巡回群。
【００９０】
ｇ：巡回群Ｇの生成元。
【００９１】
ｇＴ：巡回群ＧＴの生成元。ｇＴｍ（ｍは整数）によって巡回群ＧＴのすべての元を表現できる。ｇＴ＝ｅ（ｇ，ｇ）。
【００９２】
ｅ：ｅ（α，β）→γ（α，β∈Ｇ，γ∈ＧＴ）。巡回群Ｇの２つの元を巡回群ＧＴの１つの元に写像する双線形関数。双線形関数ｅは、以下の性質を満たす。
【００９３】
［双線形性］すべてのα，β∈Ｇ及びν，κ∈Zqについて以下の関係を満たす。
【００９４】
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)∈Zq      …(28)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Zq    …(29)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Zq    …(30)
w(u,3)=(r(3)・s(u,3)+a(3)・t(u,3))∈Zq    …(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(gr(2)・ga(2),gr(3)・ga(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)より）
=gT(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3)) （gT=e(g,g)より）
を生成して出力する。
【０１１１】
共有元演算部２１６ａ−２−１は、ハッシュ値ｄ（２）と、任意元Ｘ（２）＝ｇｒ（２）∈Ｇ，Ｘ（３）＝ｇｒ（３）∈Ｇと、秘密値ａ（１）と、公開値Ａ（２）＝ｇａ（２）∈Ｇ，Ａ（３）＝ｇａ（３）∈Ｇと、任意値ｒ（１）∈Ｚｑとを入力とし、共有元
σ(2)=e(X(2)・A(2)d(2),X(3)・A(3))r(1)+a(1)∈G      …(45)
=e(gr(2)・ga(2)・d(2),gr(3)・ga(3))r(1)+a(1)
=e(g,g)(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)) （式(27)より）
=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)) （gT=e(g,g)より）
を生成して出力する。
【０１１２】
共有元演算部２１６ａ−３−１は、ハッシュ値ｄ（３）と、任意元Ｘ（２）＝ｇｒ（２）∈Ｇ，Ｘ（３）＝ｇｒ（３）∈Ｇと、秘密値ａ（１）と、公開値Ａ（２）＝ｇａ（２）∈Ｇ，Ａ（３）＝ｇａ（３）∈Ｇと、任意値ｒ（１）∈Ｚｑとを入力とし、共有元
σ(3)=e(X(2)・A(2),X(3)・A(3)d(3))r(1)+a(1)∈G      …(46)
=e(gr(2)・ga(2),gr(3)・ga(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)より）
=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3)) （gT=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(gr(2)・ga(2)・d(2),gr(3)・ga(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)より）
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3)) （gT=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(gr(3)・ga(3),gr(1)・ga(1)・d(1))r(2)+a(2)
=gT(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(gr(3)・ga(3),gr(1)・ga(1))r(2)+a(2)・d(2)
=gT(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(gr(3)・ga(3)・d(3),gr(1)・ga(1))r(2)+a(2)
=gT(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(gr(3)・ga(3)・d(3),gr(1)・ga(1)・d(1))r(2)+a(2)・d(2)
=gT(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(gr(1)・ga(1)・d(1),gr(2)・ga(2))r(3)+a(3)
=gT(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(gr(1)・ga(1),gr(2)・ga(2)・d(2))r(3)+a(3)
=gT(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(gr(1)・ga(1),gr(2)・ga(2))r(3)+a(3)・d(3)
=gT(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(gr(1)・ga(1)・d(1),gr(2)・ga(2)・d(2))r(3)+a(3)・d(3)
=gT(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)=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))      …(68)
σ(2)=gT(r(1)+a(1)・ｄ(1))(r(2)+a(2))(r(3)+a(3)・d(3))      …(69)
σ(3)=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3))      …(70)
σ(4)=gT(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)
=gT(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)
=gT(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)
=gT(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)
=gT(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)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))
σ(2)=eT(X(3)・A(3)d(3),X(1)・A(1)d(1))r(2)+a(2)∈G      …(77)
=gT(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)
=gT(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)
=gT(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)
=gT(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)
=gT(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)
=gT(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)
=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3))
を生成して出力する。
【０１４２】
また、例えば、Ｕ＝１として、式(33)〜(40)の代わりに、
σ(1)=gT(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))=ga(1)∈G      …(85)
とおくと、式(84)は、
Z(1)=ga(1)・MSK∈G      …(86)
となる。秘密鍵Z(1)は、鍵共有装置３１０−１に送られ、その記憶部３１１−１に安全に格納される。
【０１６２】
また、鍵生成装置３３０は、鍵共有装置３１０−２の識別子ＩＤ（２）を用い、鍵共有装置３１０−２の秘密鍵
Z(2)=Y(ID(2))MSK∈G      …(87)
を生成する。ここで、
A(2)=Y(ID(2))=ga(2)∈G      …(88)
とおくと、式(87)は、
Z(2)=ga(2)・MSK∈G      …(89)
となる。秘密鍵Z(2)は、鍵共有装置３１０−２に送られ、その記憶部３１１−２に安全に格納される。
【０１６３】
また、鍵共有装置２１０−１の記憶部２１１−１に、マスタ公開鍵ＭＰＫ＝ｇＭＳＫ∈Ｇと、鍵共有装置２１０−１に対応する巡回群Ｇの元である公開値Ａ（１）＝Ｙ（ＩＤ（１））＝ｇａ（１）∈Ｇと、鍵共有装置２１０−２に対応する巡回群Ｇの元である公開値Ａ（２）＝Ｙ（ＩＤ（２））＝ｇａ（２）∈Ｇと、鍵共有装置２１０−１の識別子ＩＤ（１）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。鍵共有装置２１０−２の記憶部２１１−２に、マスタ公開鍵ＭＰＫ＝ｇＭＳＫ∈Ｇと、鍵共有装置２１０−１に対応する巡回群Ｇの元である公開値Ａ（１）＝Ｙ（ＩＤ（１））＝ｇａ（１）∈Ｇと、鍵共有装置２１０−２に対応する巡回群Ｇの元である公開値Ａ（２）＝Ｙ（ＩＤ（２））＝ｇａ（２）∈Ｇと、鍵共有装置２１０−２の識別子ＩＤ（２）と、識別子ＩＤ（ｐｒｏｔ）とが格納される。
【０１６４】
＜鍵共有処理＞
図１５（Ａ）は、鍵共有装置３１０−１の鍵共有処理を説明するためのフローチャートであり、図１５（Ｂ）は、鍵共有装置３１０−２の鍵共有処理を説明するためのフローチャートである。
【０１６５】
図１５（Ａ）に示すように、鍵共有装置３１０−１（図１３）は、第１実施形態のステップＳ１１２−１〜Ｓ１１５−１の処理を実行する。
【０１６６】
共有装置３１０−１の共有元生成部３１６−１には、入力部１１５−１に入力された任意元Ｘ（２）＝ｇｒ（２）∈Ｇと、記憶部２１１−１から読み出された秘密鍵Ｚ（１）＝ｇａ（１）・ＭＳＫ∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇＭＳＫ∈Ｇ及び公開値Ａ（２）＝ｇａ（２）∈Ｇと、任意値生成部１１２−１で生成（ステップＳ１１２−１）された任意値ｒ（１）∈Ｚｑとが入力される。共有元生成部３１６−１は、これらと巡回群Ｇの元を巡回群ＧＴの元に写像する前述の関数ｅを用い、巡回群ＧＴの元ｇＴＷ（ｕ）∈ＧＴ（ｕ∈｛１，．．．，Ｕ｝、Ｕは１以上の整数定数）を共有元σ（ｕ）として生成して出力する（ステップＳ３１６ａ−１）。本形態では
W(u)=w(u,1)・w(u,2)・MSK∈Zq      …(90)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Zq    …(91)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Zq    …(92)
を満たすｇＴＷ（ｕ）∈ＧＴが、共有元σ（ｕ）として生成される。ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚｑはｕごとに定まる定数又は変数であり、第１実施形態と同様に設定すればよい。
【０１６７】
以下に、ｓ（ｕ，１），ｓ（ｕ，２），ｔ（ｕ，１），ｔ（ｕ，２）∈Ｚｑ及びＵの設定例と、そのときのステップＳ３１６ａ−１の処理とを例示する。
【０１６８】
［ステップＳ３１６ａ−１の例］
本形態では、まず、第１実施形態の式(6)〜(10)を満たす共有元σ（ｕ）を生成する。この場合、まず、第１実施形態と同様に、ハッシュ演算部１１６ｂ−１，１１６ｃ−１（図１４（Ａ））が、式(11)(12)のハッシュ値ｄ（１），ｄ（２）を生成して出力する。
【０１６９】
共有元演算部３１６ａ−１−１（図１４（Ａ））は、ハッシュ値ｄ（２）と、任意元Ｘ（２）＝ｇｒ（２）∈Ｇと、秘密鍵Ｚ（１）＝ｇａ（１）・ＭＳＫ∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇＭＳＫ∈Ｇと、公開値Ａ（２）＝ｇａ（２）∈Ｇと、任意値ｒ（１）∈Ｚｑとを入力とし、共有元
σ(1)=e(MPKr(1)・Z(1),X(2)・A(2)d(2))∈GT      …(93)
=e(gMSK・r(1)・ga(1)・MSK, gr(2)・ga(2)・d(2))（MPK=gMSK∈Gより）
=e(g,g)(r(1)+a(1))(r(2)+a(2)・d(2))MSK（式(27)より）
=gT(r(1)+a(1))(r(2)+a(2)・ｄ(2))MSK （gT=e(g,g)より）
を生成して出力する。共有元演算部３１６ａ−２−１は、ハッシュ値ｄ（１）と、任意元Ｘ（２）＝ｇｒ（２）∈Ｇと、秘密鍵Ｚ（１）＝ｇａ（１）・ＭＳＫ∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇＭＳＫ∈Ｇと、公開値Ａ（２）＝ｇａ（２）∈Ｇと、任意値ｒ（１）∈Ｚｑとを入力とし、共有元
σ(2)=e(MPKr(1)・Z(1)d(1), X(2)・A(2))∈GT      …(94)
=e(gMSK・r(1)・ga(1)・MSK・d(1), gr(2)・ga(2))（MPK=gMSK∈Gより）
=e(g,g)(r(1)+a(1)・d(1))(r(2)+a(2))MSK（式(27)より）
=gT(r(1)+a(1)・d(1))(r(2)+a(2))MSK（gT=e(g,g)より）
を生成して出力する（［ステップＳ３１６ａ−１の例］の説明終わり）。
【０１７０】
また、共有元生成部３１６−１の共有元演算部３１６ｂ−１が、任意元Ｘ（２）＝ｇｒ（２）∈Ｇと、任意値ｒ（１）∈Ｚｑとを入力とし、共有元
σ(3)=X(2)r(1)∈G      …(95)
=gr(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),MPKr(2)・Z(2)d(2))∈GT      …(97)
=e(gr(1)・ga(1),g MSK・r(2)・ga(2)・MSK・d(2))（MPK=gMSK∈Gより）
=e(g,g)(r(1)+a(1))(r(2)+a(2)・d(2))MSK（式(27)より）
=gT(r(1)+a(1))(r(2)+a(2)・ｄ(2))MSK （gT=e(g,g)より）
を生成して出力する。共有元演算部３１６ａ−２−２は、ハッシュ値ｄ（１）と、任意元Ｘ（１）＝ｇｒ（１）∈Ｇと、秘密鍵Ｚ（２）＝ｇａ（２）・ＭＳＫ∈Ｇ、マスタ公開鍵ＭＰＫ＝ｇＭＳＫ∈Ｇと、公開値Ａ（１）＝ｇａ（１）∈Ｇと、任意値ｒ（２）∈Ｚｑとを入力とし、共有元
σ(2)=e(X(1)・A(1)d(1),MPKr(2)・Z(2))∈GT      …(98)
=e(gr(1)・ga(1)・d(1),gMSK・r(2)・ga(2)・MSK)（MPK=gMSK∈Gより）
=e(g,g)(r(1)+a(1)・d(1))(r(2)+a(2))MSK（式(27)より）
=gT(r(1)+a(1)・d(1))(r(2)+a(2))MSK（gT=e(g,g)より）
を生成して出力する（［ステップＳ３１６ａ−２の例］の説明終わり）。
【０１７７】
また、共有元生成部３１６−２の共有元演算部３１６ｂ−２が、任意元Ｘ（１）＝ｇｒ（１）∈Ｇと、任意値ｒ（２）∈Ｚｑとを入力とし、共有元
σ(3)=X(1)r(2)∈G      …(99)
=gr(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(MPKr(1)・Z(1),X(2)・A(2))∈GT      …(101)
=gT(r(1)+a(1))(r(2)+a(2))MSK 
σ(2)=e(MPKr(1)・Z(1)d(1), X(2)・A(2)d(1))∈GT      …(102)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK
を生成して出力する。
【０１８５】
また、共有元演算部３１６ａ−１−２，３１６ａ−２−２（図１４（Ｂ））が、式(98)(98)の代わりに、共有元
σ(1)=e(X(1)・A(1),MPKr(2)・Z(2))∈GT      …(103)
=gT(r(1)+a(1))(r(2)+a(2))MSK
σ(2)=e(X(1)・A(1)d(1),MPKr(2)・Z(2)d(2))∈GT      …(104)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK
を生成して出力する。また、この変形例では、共有元σ（３）は生成されない。その他は第３実施形態と同様である。
【０１８６】
その他、例えば、Ｕ＝１として共有元
σ(1)=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK
を生成してもよい。また、例えば、第１実施形態の変形例１で説明したようなｓ（１，１），ｔ（１，１），ｓ（１，２），ｔ（１，２），ｓ（２，１），ｔ（２，１），ｓ（２，２），ｔ（２，２）やＵやｄ（ｐ）に関する変形を行ってもよい。また、
ｒ（ｉ）＝Ｆ’（ｒ’（ｉ），ａ（ｉ））
としてもよい。なお、Ｆ’は、ハッシュ関数Ｆ’：｛０，１｝*→Ｚｑであり、ｒ’（ｉ）は乱数である。ｒ（ｊ）についても同様な変形を行ってもよい。これによってＵ＝１の場合でも高い安全性を確保できる。その他、本発明の趣旨を遺脱しない範囲で共有元σ（ｕ）の生成方法を変形可能である。
【０１８７】
〔第３実施形態の変形例２〕
第１実施形態の変形例２と同様、第３実施形態でも、鍵Ｋは共有元σ（ｕ）に基づいて値が定まればよく、第１実施形態の変形例２で述べたように鍵Ｋの生成方法を変形してもよい。
【０１８８】
〔その他の変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各実施形態では、位数ｑを素数としたが、位数ｑが素数でなく合成数であってもよい。また、上述の各実施形態では、任意値ｒ（ｉ），ｒ（ｊ）等を法ｑについての整数の剰余環Ｚｑの元としたが、各実施形態で法ｑについての整数の剰余環Ｚｑの元として扱った各値が整数集合の元であってもよい。
【０１８９】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１９０】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１９１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１９２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１９３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１９４】
また、各形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１９５】
本発明の利用分野としては、例えば、共通鍵暗号における共通鍵の共有、共通鍵暗号を用いた認証処理における共通鍵の共有などがある。
【符号の説明】
【０１９６】
１，１００〜３００  鍵共有システム
１０−１０〜Ｐ，１１０−１１０〜Ｐ，２１０−２１０〜Ｐ，３１０−３１０〜Ｐ  鍵共有装置
【図１】
2011019042.tif 000003
【図２】
2011019042.tif 000004
【図３】
2011019042.tif 000005
【図４】
2011019042.tif 000006
【図５】
2011019042.tif 000007
【図６】
2011019042.tif 000008
【図７】
2011019042.tif 000009
【図８】
2011019042.tif 000010
【図９】
2011019042.tif 000011
【図１０】
2011019042.tif 000012
【図１１】
2011019042.tif 000013
【図１２】
2011019042.tif 000014
【図１３】
2011019042.tif 000015
【図１４】
2011019042.tif 000016
【図１５】
2011019042.tif 000017