(57)【要約】【課題】鍵共有プロトコルにおいて送受信される情報と公開鍵（対話鍵）の関係を検証できるようにして、対話鍵に対応する非対称秘密鍵をいつ誰が共有したかが分かるようにする。【解決手段】複数のユーザ端末（ＡｌｉｃｅとＢｏｂ）があり、鍵共有プロトコルＺにより非対称共通鍵ＣＫを秘密に共有する。オブザーバであるセンタ（Ｃｈａｒｌｅｙ）は、傍受した端末間の通信（対話文ＩＭ）から、秘密に共有された非対称共通鍵ＣＫに対応するグループ公開鍵（対話鍵ＩＫ）を、アルゴリズムαにより計算する。非対称共通鍵ＣＫが秘密に共有された時点では、対話鍵ＩＫも既に計算可能となっており、リアルタイム性が保証される。鍵共有プロトコルＺにおいて送受信される情報と公開鍵（対話鍵）の関係が、センタで検証でき、対話鍵ＩＫに対応する非対称共通鍵ＣＫをいつ誰が秘密に共有したかが分かる。【選択図】      図１
2004282575.tif 000002
【特許請求の範囲】
【請求項１】
非対称共通鍵（公開鍵方式のグループ秘密鍵）を計算可能な鍵交換手段を持つ複数の端末と、センタとからなる鍵交換システムにおいて、前記センタは、前記端末間の通信を傍受可能な傍受手段と、傍受した前記通信から前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する手段とを備えたことを特徴とする鍵交換システム。
【請求項２】
ｐを素数とし、ｑを（ｐ−１）の素因数とし、ｇを位数がｑであるＧＦ（ｑ）の元とし、前記ｐ，ｑ，ｇを固定のパラメータとして全エンティティに予め共有させておき、ｉ（１≦ｉ≦ｎ；ｎは２以上の整数）をユーザｉのＩＤとし、Ｘｉをユーザｉの非対称秘密鍵とし、ＹｉをユーザｉのＸｉに対する公開鍵とし、Ｐ＿ＥＮＣ（ｙ，ｍ）を、公開鍵ｙにより、公開鍵ｙに対応する非対称秘密鍵で復号できる暗号文に平文ｍを公開鍵方式で暗号化する関数とし、Ｃ＿ＥＮＣ（Ｋ，ｍ）を、対称秘密鍵Ｋにより復号できる暗号文に平文ｍを対称秘密鍵Ｋにより対称秘密鍵方式で暗号化する関数とし、Ｌ（Ψ，ｗ）を、集合Ψと整数ｗに関して
Ｌ（Ψ，ｗ）＝Πｔ∈Ψ＼｛ｗ｝  ｔ／（ｔ−ｗ）  ｍｏｄｑ
と定義されるラグランジェ補間係数とし、非対称共通鍵の交換が可能なｎ台の端末間の通信をセンタで傍受して前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵共有方法において、
Ｓｔｅｐ１で、各ユーザｉ（ｉ＝１・・・ｎ）は、
ａ）乱数Ｒｉ（∈Ｚｑ）を生成し、
ｂ）Ｚｑ上の任意のｎ次多項式ｆｉ（ｗ）
ｆｉ（ｗ）＝ｆｉ，０＊ｗ０＋ｆｉ，１＊ｗ１＋・＋ｆｉ，ｎ＊ｗｎ
を生成し、ｆｉ，０＝Ｒｉとし、
ｃ）非対称共通鍵の元データ
ＣＫｉ，ｊ＝ｆｉ（ｊ）  （ｊ＝１・・・・・・２ｎ）
を計算し、２つの分散値ＣＫｉ，２ｉ−１とＣＫｉ，２ｉを保持し、
ｄ）ユーザｉ自身以外の全てのユーザｖ（ｖ≠ｉ）に対して、暗号文
ＥＮＣｉ，ｖ＝Ｐ＿ＥＮＣ（Ｙｖ，ｉ‖ＣＫｉ，２ｖ−１‖ＣＫｉ，２ｖ）
を計算し、ユーザｖに送信し、
Ｓｔｅｐ２で、各ユーザｉ（ｉ＝１・・・ｎ）は、
ａ）ユーザｉ自身以外の全てのユーザｖ（ｖ≠ｉ）のＥＮＣｖ，ｉを受信し、
ｂ）暗号文ＥＮＣｖ，ｉを非対称秘密鍵Ｘｉで復号し、ＣＫｖ，２ｉ−１‖ＣＫｖ，２ｉを得て、
ｃ）非対称共通鍵の元データ
ＣＫ２ｉ−１＝Σｖ＝１ｎ  ＣＫｖ，２ｉ−１  ｍｏｄｑ
ＣＫ２ｉ＝Σｖ＝１ｎ  ＣＫｖ，２ｉ  ｍｏｄｑ
を計算し、
ｄ）対話鍵の元データ
ＩＫｉ＝ｇ＾（ＣＫ２ｉ−１）  ｍｏｄｐ
を計算し、
ｅ）ＩＫｉ，ＣＫ２ｉをユーザｉ自身以外の全てのユーザｖ（ｖ≠ｉ）に送信し、
Ｓｔｅｐ３で、各ユーザｉ（ｉ＝１・・・ｎ）は、
ａ）ユーザｉ自身の保持する分散値の番号と受信した分散値の番号の集合を
φ＝｛２ｉ−１，２，４，・・・，２ｎ｝
として、非対称共通鍵
ＣＫ＝Σｈ∈φ  （ＣＫｈ＊Ｌ（φ，ｈ））  ｍｏｄｑ
＝Σｉ＝１ｎ  Ｒｉ  ｍｏｄｑ
を計算し、
前記センターは、
ａ）各ユーザのＩＫｉ，ＣＫ２ｉを受信し、
ｂ）分散値の番号の集合Δを
Δ＝｛１，２，３，・・・，２ｎ｝
として、対話鍵
ＩＫ＝Πｉ＝１ｎ  ｛ＩＫｉ＾（Ｌ（Δ，２ｉ−１））＊ｇ＾（ＣＫ２ｉ＊Ｌ（Δ，２ｉ））｝  ｍｏｄｐ
＝ｇ＾（ＣＫ）  ｍｏｄｐ
を計算することを特徴とする対話鍵共有方法。
【請求項３】
ｐを素数とし、ｑを（ｐ−１）の素因数とし、ｇを位数がｑであるＧＦ（ｑ）の元とし、前記ｐ，ｑ，ｇを固定のパラメータとして全エンティティに予め共有させておき、ｉ（１≦ｉ≦ｎ；ｎは２以上の整数）をユーザｉのＩＤとし、Ｘｉをユーザｉの非対称秘密鍵とし、ＹｉをユーザｉのＸｉに対する公開鍵とし、Ｐ＿ＥＮＣ（ｙ，ｍ）を、公開鍵ｙにより、公開鍵ｙに対応する非対称秘密鍵で復号できる暗号文に平文ｍを公開鍵方式で暗号化する関数とし、Ｃ＿ＥＮＣ（Ｋ，ｍ）を、対称秘密鍵Ｋにより復号できる暗号文に平文ｍを対称秘密鍵Ｋにより対称秘密鍵方式で暗号化する関数とし、Ｌ（Ψ，ｗ）を、集合Ψと整数ｗに関して
Ｌ（Ψ，ｗ）＝Πｔ∈Ψ＼｛ｗ｝  ｔ／（ｔ−ｗ）  ｍｏｄｑ
と定義されるラグランジェ補間係数とし、非対称共通鍵の交換が可能なｎ台の端末間の通信をセンタで傍受して前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵共有方法において、
Ｓｔｅｐ１で、各ユーザｉ（ｉ＝１・・・ｎ）は、
ａ）乱数Ｒｉ（∈Ｚｑ）を生成し、
ｂ）Ｚｑ上の任意のｎ次多項式ｆｉ（ｗ）
ｆｉ（ｗ）＝ｆｉ，０＊ｗ０＋ｆｉ，１＊ｗ１＋・＋ｆｉ，ｎ＊ｗｎ
を生成し、ｆｉ，０＝Ｒｉとし、
ｃ）検証値
Ｆｉ＝｛Ｆｉ，ｋ＝ｇ＾（ｆｉ，ｋ）｜ｋ＝０，１・・，ｎ｝
を計算して全ユーザに送信し、
ｄ）非対称共通鍵の元データ
ＣＫｉ，ｊ＝ｆｉ（ｊ）  （ｊ＝１・・・・・・２ｎ）
を計算し、２つの分散値ＣＫｉ，２ｉ−１とＣＫｉ，２ｉを保持し、
ｅ）ユーザｉ自身以外の全てのユーザｖ（ｖ≠ｉ）に対して、暗号文
ＥＮＣｉ，ｖ＝Ｐ＿ＥＮＣ（Ｙｖ，ｉ‖ＣＫｉ，２ｖ−１‖ＣＫｉ，２ｖ）
を計算し、ユーザｖに送信し、
Ｓｔｅｐ２で、各ユーザｉ（ｉ＝１・・・ｎ）は、
ａ）ユーザｉ自身以外の全てのユーザｖ（ｖ≠ｉ）のＥＮＣｖ，ｉ，Ｆｖを受信し、
ｂ）暗号文ＥＮＣｖ，ｉを非対称秘密鍵Ｘｉで復号し、ＣＫｖ，２ｉ−１‖ＣＫｖ，２ｉを得て、
ｃ）非対称共通鍵の元データ
ＣＫ２ｉ−１＝Σｖ＝１ｎ  ＣＫｖ，２ｉ−１  ｍｏｄｑ
ＣＫ２ｉ＝Σｖ＝１ｎ  ＣＫｖ，２ｉ  ｍｏｄｑ
を計算し、
ｄ）対話鍵の元データ
ＩＫｉ＝ｇ＾（ＣＫ２ｉ−１）  ｍｏｄｐ
を計算し、
ｅ）ＩＫｉ，ＣＫ２ｉをユーザｉ自身以外の全てのユーザｖ（ｖ≠ｉ）に送信し、
Ｓｔｅｐ３で、各ユーザｉ（ｉ＝１・・・ｎ）は、
ａ）ユーザｉ自身の保持する分散値の番号と受信した分散値の番号の集合を
φ＝｛２ｉ−１，２，４，・・・，２ｎ｝
として、非対称共通鍵
ＣＫ＝Σｈ∈φ  （ＣＫｈ＊Ｌ（φ，ｈ））  ｍｏｄｑ
＝Σｉ＝１ｎ  Ｒｉ  ｍｏｄｑ
を計算し、
前記センターは、
ａ）各ユーザのＦｉ，ＩＫｉ，ＣＫ２ｉを受信し、ｉ＝１，・，ｎに対し、ＩＫｉとＣＫ２ｉを
ｇ＾（ＣＫｊ）＝Πｉ＝１ｎ  （Πｋ＝０ｎ  Ｆｉ，ｋ＾（ｊｋ））  ｍｏｄｐ
により検証し、検証失敗ならエラーであることを全ユーザに送信して終了し、検証成功なら、
ｂ）対話鍵
ＩＫ＝Πｉ＝１ｎ  ｛ＩＫｉ＾（Ｌ（Δ，２ｉ−１））＊ｇ＾（ＣＫ２ｉ＊Ｌ（Δ，２ｉ））｝  ｍｏｄｐ
＝ｇ＾（ＣＫ）  ｍｏｄｐ
を計算することを特徴とする対話鍵共有方法。
【請求項４】
ｐを素数とし、ｑを（ｐ−１）の素因数とし、ｇを位数がｑであるＧＦ（ｑ）の元とし、前記ｐ，ｑ，ｇを固定のパラメータとしてユーザＡとユーザＢとセンタに予め共有させておき、ＸＡをユーザＡの非対称秘密鍵とし、ＸＢをユーザＢの非対称秘密鍵とし、ＹＡをユーザＡのＸＡに対する公開鍵とし、ＹＢをユーザＢのＸＢに対する公開鍵とし、Ｐ＿ＥＮＣ（ｙ，ｍ）を、公開鍵ｙにより、公開鍵ｙに対応する非対称秘密鍵で復号できる暗号文に平文ｍを公開鍵方式で暗号化する関数とし、Ｃ＿ＥＮＣ（Ｋ，ｍ）を、対称秘密鍵Ｋにより復号できる暗号文に平文ｍを対称秘密鍵Ｋにより対称秘密鍵方式で暗号化する関数とし、Ｈを、ハッシュ関数とし、非対称共通鍵の交換が可能な２台の端末間の通信をセンタで傍受して前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵共有方法において、
Ｓｔｅｐ１でユーザＡは、
ａ）乱数ＲＡ（∈Ｚｑ）を生成し、
ｂ）対話鍵の元データ
ＩＫＡ＝ｇ＾（ＲＡ）  ｍｏｄｐ
を計算してユーザＢに送信し、
Ｓｔｅｐ２でユーザＢは、
ａ）乱数ＲＢ（∈Ｚｑ）を生成し、
ｂ）対話鍵の元データ
ＩＫＢ＝ｇ＾（ＲＢ）  ｍｏｄｐ
を計算してユーザＡに送信し、
Ｓｔｅｐ３でユーザＡは、
ａ）暗号文
ＥＮＣＡ，Ｂ＝Ｐ＿ＥＮＣ（ＹＢ，Ａ‖ＲＡ）
を計算してユーザＢに送信し、
Ｓｔｅｐ４でユーザＢは、
ａ）非対称秘密鍵ＸＢを使ってＥＮＣＡ，Ｂを復号し、乱数ＲＡを得て、
ｂ）暗号文
ＥＮＣＢ，Ａ＝Ｃ＿ＥＮＣ（Ｈ（ＲＡ），ＲＢ）
を計算してユーザＡに送信し、
ｃ）非対称共通鍵
ＣＫ＝ＲＢ＋ＲＡ  ｍｏｄｑ
を計算し、
Ｓｔｅｐ５でユーザＡは、
ａ）ハッシュ値Ｈ（ＲＡ）を使ってＥＮＣＢ，Ａを復号し、乱数ＲＢを得て、
ｂ）非対称共通鍵
ＣＫ＝ＲＡ＋ＲＢ  ｍｏｄｑ
を計算し、
Ｓｔｅｐ５でセンタは、
ａ）対話鍵
ＩＫ＝ＩＫＡ＊ＩＫＢ  ｍｏｄｐ
＝ｇ＾（ＲＡ＋ＲＢ）  ｍｏｄｐ
を計算することを特徴とする対話鍵共有方法。
【請求項５】
ｐを素数とし、ｑを（ｐ−１）の素因数とし、ｇを位数がｑであるＧＦ（ｑ）の元とし、前記ｐ，ｑ，ｇを固定のパラメータとしてユーザＡとユーザＢとセンタに予め共有させておき、ＸＡをユーザＡの非対称秘密鍵とし、ＸＢをユーザＢの非対称秘密鍵とし、ＹＡをユーザＡのＸＡに対する公開鍵とし、ＹＢをユーザＢのＸＢに対する公開鍵とし、Ｐ＿ＥＮＣ（ｙ，ｍ）を、公開鍵ｙにより、公開鍵ｙに対応する非対称秘密鍵で復号できる暗号文に平文ｍを公開鍵方式で暗号化する関数とし、Ｃ＿ＥＮＣ（Ｋ，ｍ）を、対称秘密鍵Ｋにより復号できる暗号文に平文ｍを対称秘密鍵Ｋにより対称秘密鍵方式で暗号化する関数とし、Ｈを、ハッシュ関数とし、非対称共通鍵の交換が可能な２台の端末間の通信をセンタで傍受して前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵共有方法において、
Ｓｔｅｐ１でユーザＡは、
ａ）乱数ＲＡ，ＤＡ  （∈Ｚｑ）を生成し、
ｂ）対話鍵の元データ
ＩＫＡ＝ｇ＾（ＲＡ）  ｍｏｄｐ
を計算し、
ｃ）チャレンジ
ＣＨＡＡ，Ｂ＝ｇ＾（ＤＡ）  ｍｏｄｐ
を計算し、
ｄ）ＩＫＡ，ＣＨＡＡ，ＢをユーザＢに送信し、
Ｓｔｅｐ２でユーザＢは、
ａ）乱数ＲＢ，ＤＢ（∈Ｚｑ）を生成し、
ｂ）対話鍵の元データ
ＩＫＢ＝ｇ＾（ＲＢ）  ｍｏｄｐ
を計算し、
ｃ）チャレンジ
ＣＨＡＢ，Ａ＝ｇ＾（ＤＢ）  ｍｏｄｐ
を計算し、
ｄ）レスポンス
ＲＥＳＢ，Ａ＝ＣＨＡＡ，Ｂ＾（ＲＢ）  ｍｏｄｐ
を計算し、
ｅ）ＩＫＢ，ＲＥＳＢ，Ａ，ＣＨＡＢ，ＡをユーザＡに送信し、
Ｓｔｅｐ３でユーザＡは、
ａ）レスポンス
ＲＥＳＡ，Ｂ＝ＣＨＡＢ，Ａ＾（ＲＡ）  ｍｏｄｐ
を計算し、
ｂ）暗号文
ＥＮＣＡ，Ｂ＝Ｐ＿ＥＮＣ（ＹＢ，Ａ‖ＲＡ）
を計算し、
ｃ）ＥＮＣＡ，Ｂ，ＤＡ，ＲＥＳＡ，ＢをユーザＢに送信し、
Ｓｔｅｐ４でユーザＢは、
ａ）非対称秘密鍵ＸＢでＥＮＣＡ，Ｂを復号し、乱数ＲＡを得て、
ｂ）暗号文
ＥＮＣＢ，Ａ＝Ｃ＿ＥＮＣ（Ｈ（ＲＡ），ＲＢ）
を計算し、
ｃ）ＥＮＣＢ，Ａ，ＤＢをユーザＡに送信し、
ｄ）非対称共通鍵
ＣＫ＝ＲＢ＋ＲＡ  ｍｏｄｑ
を計算し、
Ｓｔｅｐ５でユーザＡは、
ａ）ハッシュ値Ｈ（ＲＡ）を使ってＥＮＣＢ，Ａを復号し、乱数ＲＢを得て、
ｂ）非対称共通鍵
ＣＫ＝ＲＡ＋ＲＢ  ｍｏｄｑ
を計算し、
Ｓｔｅｐ５でセンタは、チャレンジの後に乱数（ＤＡ，ＤＢ）が公開された場合にのみ、
ａ）通信を傍受して得たデータに基づいて、
ＲＥＳＡ，  Ｂ≡ＩＫＡ＾（ＤＢ）  （ｍｏｄｐ）
ＲＥＳＢ，  Ａ≡ＩＫＢ＾（ＤＡ）  （ｍｏｄｐ）
が成立するか否かを検証し、成立しない場合はエラーであることをユーザＡとユーザＢに送信し、成立する場合は、
ｂ）対話鍵
ＩＫ＝ＩＫＡ＊ＩＫＢ  ｍｏｄｐ
＝ｇ＾（ＲＡ＋ＲＢ）  ｍｏｄｐ
を計算することを特徴とする対話鍵共有方法。
【請求項６】
Ｕを素数とし、ｅをＲＳＡの公開鍵とし、前記Ｕ，ｅをユーザＡとユーザＢとセンタに予め共有させておき、ＸＡをユーザＡの非対称秘密鍵とし、ＸＢをユーザＢの非対称秘密鍵とし、ＹＡをユーザＡのＸＡに対する公開鍵とし、ＹＢをユーザＢのＸＢに対する公開鍵とし、Ｐ＿ＥＮＣ（ｙ，ｍ）を、公開鍵ｙにより、公開鍵ｙに対応する非対称秘密鍵で復号できる暗号文に平文ｍを公開鍵方式で暗号化する関数とし、非対称共通鍵の交換が可能な２台の端末間の通信をセンタで傍受して前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵共有方法において、
Ｓｔｅｐ１でユーザＡは、
ａ）乱数ＲＡ  （１≦ＲＡ＜Ｕ）を生成し、
ｂ）暗号文
ＥＮＣＡ，Ｂ＝Ｐ＿ＥＮＣ（ＹＢ，ＲＡ）
を計算してユーザＢに送信し、
Ｓｔｅｐ２でユーザＢは、
ａ）非対称秘密鍵ＸＢを使ってＥＮＣＡ，Ｂを復号し、
ｂ）ＲＡ＊ＲＢ＞Ｕとなるように、乱数ＲＢ  （１≦ＲＢｏｂ＜Ｕ）を生成し、
ｃ）（ＱＢｏｂ−１）と公開鍵ｅが互いに素になり、ＱＢｏｂ＊ＲＢｏｂ＞Ｕとなるように、素数ＱＢｏｂを生成し、
ｄ）対話鍵の元データ
ＩＫＢｏｂ＝ＱＢｏｂ＊ＲＢｏｂ  ｍｏｄＵ
を計算し、
ｅ）乱数の積
ＲＡ，Ｂ＝ＲＡ＊ＲＢ  ｍｏｄＵ
を計算して、ＩＫＢｏｂと共にユーザＡに送信し、
Ｓｔｅｐ３でユーザＡは、
ａ）（ＰＡ−１）と公開鍵ｅが互いに素になり、ＲＡ＊ＰＡ＞Ｕとなるように、素数ＰＡを生成し、
ｂ）対話鍵の元データ
ＩＫＡ＝ＲＡ＊ＰＡ  ｍｏｄＵ
を計算してユーザＢに送信し、
ｃ）ユーザＢの乱数
ＱＢ＝（ＲＡ＊ＩＫＢ）／ＲＡ，Ｂ  ｍｏｄＵ
を計算して得て、
ｄ）方程式
ｄ＊ｅ≡１  （ｍｏｄ  ＬＣＭ（ＰＡ−１，ＱＢ−１））
を満たす非対称秘密鍵ｄを求め、
Ｓｔｅｐ４でユーザＢは、
ａ）ユーザＡの素数
ＰＡ＝ＩＫＡ／ＲＡ  ｍｏｄＵ
を計算して得て、
ｂ）方程式
ｄ＊ｅ≡１  （ｍｏｄ  ＬＣＭ（ＰＡ−１，ＱＢ−１））
を満たす非対称秘密鍵ｄを求め、
Ｓｔｅｐ４でセンタは、
ａ）対話鍵
ＩＫ＝（ＩＫＡ＊ＩＫＢ）／ＲＡ，Ｂ  ｍｏｄＵ
を計算することを特徴とする対話鍵共有方法。
【請求項７】
公開鍵暗号Ｐ＿ＥＮＣ（・）としてＥｌ  Ｇａｍａｌ暗号を使用する場合において、Ｆｉ，０をＥｌ  Ｇａｍａｌ暗号における乱数のベキ乗剰余値の代わりに用いることを特徴とする請求項３に記載の対話鍵共有方法。
【請求項８】
非対称共通鍵を計算可能な鍵交換手段を持つ複数の端末と、前記端末間の通信を傍受可能な傍受手段および傍受した前記通信から前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する手段とを有するセンタとからなる鍵交換システムでの通話内容証明方法において、前記センタは、対話文と通話内容を安全に記録し、かつ要求に応じて公開し、通話内容登録に参加する全ユーザがセンタに観察を依頼し、各ユーザｉは、対話文ＩＭｉを他の全ユーザに送信して非対称共通鍵ＣＫを共有し、各ユーザｉは、通話文ＰＴｉから指紋ＦＰｉ（＝Ｈ（ＰＴｉ））を生成し、通話文ＰＴｉを非対称共通鍵ＣＫか対話鍵ＩＫで暗号化して暗号文ＣＴｉを生成し、非対称秘密鍵Ｘｉと非対称共通鍵ＣＫを用いて、それぞれＦＰｉ‖Ｈ（ＣＴｉ）に対する署名ＳＭｉＩ，ＳＭｉＩＩを生成し、生成した暗号文ＣＴｉ，署名ＳＭｉＩ，ＳＭｉＩＩ，指紋ＦＰｉを他の全ユーザに送信し、各ユーザは、暗号文ＣＴｉから通話文ＰＴｉを得て、Ｈ（ＰＴｉ）＝ＦＰｉを確認してから署名を検証し、センタは、全ユーザのＩＭｉ，ＣＴｉ，ＦＰｉ，ＳＭｉＩ，ＳＭｉＩＩを保存し、検証者は、ユーザｉに通話内容証明を要求し、ユーザｉは、センタに通話内容証明を依頼し、全ユーザは、ＰＴｉを公開し、センタは、全ユーザのＩＭｉ，ＣＴｉ，ＦＰｉ，ＳＭｉＩ，ＳＭｉＩＩを公開し、検証者は、全ユーザの対話文ＩＭｉから対話鍵ＩＫを生成し、通話文ＰＴｉから指紋ＦＰｉを生成し、暗号文ＣＴｉからＨ（ＣＴｉ）を計算して、対話鍵ＩＫと全ユーザの公開鍵Ｙｉを用いて、署名ＳＭｉＩ，ＳＭｉＩＩを検証し、検証成功ならば通話文ＰＴｉを受理することを特徴とする対話鍵による通話内容証明方法。
【請求項９】
非対称共通鍵を計算可能な鍵交換手段を持つ複数の端末と、前記端末間の通信を傍受可能な傍受手段および傍受した前記通信から前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する手段とを有するセンタとからなる鍵交換システムでの通話内容証明方法において、前記センタは、対話文と通話内容を安全に記録し、かつ要求に応じて公開し、通話内容登録に参加する全ユーザがセンタに観察を依頼し、各ユーザｉは、対話文ＩＭｉを他の全ユーザに送信して非対称共通鍵ＣＫを共有し、各ユーザｉは、通話文ＰＴｉを対話鍵ＩＫで暗号化してＣＴｉを生成し、非対称秘密鍵Ｘｉと非対称共通鍵ＣＫを用いて、それぞれＨ（ＣＴｉ）に対する署名ＳＭｉＩ，ＳＭｉＩＩを生成し、生成した暗号文ＣＴｉ，署名ＳＭｉＩ，ＳＭｉＩＩを他の全ユーザに送信し、センタは、全ユーザのＩＭｉ，ＣＴｉ，ＳＭｉＩ，ＳＭｉＩＩを保存し、検証者は、ユーザｉに通話内容証明を要求し、ユーザｉは、センタに通話内容証明を依頼し、全ユーザは、通話文ＰＴｉを公開し、センタは、全ユーザのＩＭｉ，ＣＴｉ，ＳＭｉＩ，ＳＭｉＩＩを公開し、全ユーザの対話文ＩＭｉから対話鍵ＩＫを生成し、対話鍵ＩＫを用いて通話文ＰＴｉから暗号文ＣＴｉを計算し、暗号文ＣＴｉからＨ（ＣＴｉ）を計算して、対話鍵ＩＫと全ユーザのＹｉを用いて、署名ＳＭｉＩ，ＳＭｉＩＩを検証し、検証者は、検証成功ならば通話文ＰＴｉを受理することを特徴とする対話鍵による通話内容証明方法。
【請求項１０】
非対称共通鍵を計算可能な鍵交換手段を持つ複数の端末と、前記端末間の通信を傍受可能な傍受手段および傍受した前記通信から前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する手段とを有するセンタとからなる鍵交換システムでの通話内容証明方法において、前記センタは、対話文と通話内容を安全に記録し、かつ要求に応じて公開し、通話内容登録に参加する全ユーザがセンタに観察を依頼し、各ユーザｉは、対話文ＩＭｉを他の全ユーザに送信して非対称共通鍵ＣＫを共有し、各ユーザｉは、非対称秘密鍵Ｘｉと非対称共通鍵ＣＫを用いて、それぞれＨ（ＰＴｉ）に対する署名ＳＭｉＩ，ＳＭｉＩＩを生成し、通話文ＰＴｉ，署名ＳＭｉＩ，ＳＭｉＩＩを他の全ユーザに送信し、センタは、全ユーザのＩＭｉ，ＰＴｉ，ＳＭｉＩ，ＳＭｉＩＩを保存し、検証者は、ユーザｉに通話内容証明を要求し、ユーザｉは、センタに通話内容証明を依頼し、全ユーザは、通話文ＰＴｉを公開し、センタは、全ユーザのＩＭｉ，ＰＴｉ，ＳＭｉＩ，ＳＭｉＩＩを公開し、通話文ＰＴｉからＨ（ＰＴｉ）を計算して、全ユーザの対話文ＩＭｉから対話鍵ＩＫを生成し、対話鍵ＩＫと全ユーザの公開鍵Ｙｉを用いて、署名ＳＭｉＩ，ＳＭｉＩＩを検証し、検証者は、検証成功ならば通話文ＰＴｉを受理することを特徴とする対話鍵による通話内容証明方法。
【請求項１１】
前記センタと検証者が一体であることを特徴とする請求項８〜１０のいずれかに記載の対話鍵による通話内容証明方法。
【請求項１２】
ユーザｊは、受信した情報の署名が正しく、かつＰＴの内容を受理したら、ユーザ≡の送信した情報（例えばＦＰ，ＣＴ，ＰＴ）に対して自身の非対称秘密鍵Ｘｊを用いた署名ＳＭｊＩＩＩを作成して送信者に送り返し、センタは、署名ＳＭｊＩＩＩを保管し、要求時に他のメッセージと一緒に公開することを特徴とする請求項８〜１０のいずれかに記載の対話鍵による通話内容証明方法。
【請求項１３】
ｐを素数とし、ｑを（ｐ−１）の素因数とし、ｇを位数がｑであるＧＦ（ｑ）の元とし、ｐ，ｑ，ｇを固定のパラメータとして、ユーザ１〜ユーザｎ（ｎ≧３）とセンタに予め共有させておき、Ｘｉをユーザｉの非対称秘密鍵とし、ＹｉをユーザｉのＸｉに対する公開鍵とし、Ｐ＿ＥＮＣ（ｙ，ｍ）を、公開鍵ｙにより、公開鍵ｙに対応する非対称秘密鍵で復号できる暗号文に平文ｍを公開鍵方式で暗号化する関数とし、Ｃ＿ＥＮＣ（Ｋ，ｍ）を、対称秘密鍵Ｋにより復号できる暗号文に平文ｍを対称秘密鍵Ｋにより対称秘密鍵方式で暗号化する関数とし、Ｈをハッシュ関数とし、λを全ユーザＩＤの集合｛１，２，・・・，ｎ｝とし、εｉをユーザＩＤの集合｛２，・・・，ｉ｝とし、δｉをユーザＩＤの集合｛１，ｉ＋２，・・・，ｎ｝（＝λ−εｉ＋１）とし、非対称共通鍵の交換が可能なｎ台の端末間の通信をセンタで傍受して前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵共有方法において、
ＳｔｅｐＳ１：ユーザ１は、乱数Ｒ１（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ１＝ｇ＾（Ｒ１）  ｍｏｄｐ
を計算してユーザ２に送信し、
ＳｔｅｐＲ１：ユーザ２は、乱数Ｒ２（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ２＝ｇ＾（Ｒ２）  ｍｏｄｐ
を計算し、暗号文
ＥＮＣ２，３＝Ｐ＿ＥＮＣ（Ｙ３，２‖Ｒ２）
を計算してユーザ３に送信し、
ユーザｉ（３≦ｉ≦ｎ−１）は、乱数Ｒｉ（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫｉ＝ｇ＾（Ｒｉ）  ｍｏｄｐ
を計算し、暗号文
ＥＮＣｉ−１，ｉ＝Ｐ＿ＥＮＣ（Ｙｉ，ｉ−１‖Σｊ∈εｉ−１Ｒｊ）
を、非対称秘密鍵Ｘｉを使って復号してΣｊ∈εｉ−１Ｒｊを得て、暗号文
ＥＮＣｉ，ｉ＋１＝Ｐ＿ＥＮＣ（Ｙｉ＋１，ｉ‖Σｊ∈εｉＲｊ）
を計算してユーザｉ＋１に送信し、
ＳｔｅｐＴ１：ユーザｎは、乱数Ｒｎ（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫｎ＝ｇ＾（Ｒｎ）  ｍｏｄｐ
を計算し、暗号文
ＥＮＣｎ−１，ｎ＝Ｐ＿ＥＮＣ（Ｙｎ，ｎ−１‖Σｊ∈εｎ−１Ｒｊ）
を、非対称秘密鍵Ｘｎを使って復号してΣｊ∈εｎ−１Ｒｊを得て、暗号文
ＥＮＣｎ，１＝Ｐ＿ＥＮＣ（Ｙ１，ｎ‖Σｊ∈εｎＲｊ）
を計算してユーザ１に送信し、
ＳｔｅｐＳ２：ユーザ１は、暗号文
ＥＮＣｎ，１＝Ｐ＿ＥＮＣ（Ｙ１，ｎ‖Σｊ∈εｎＲｊ）
を、非対称秘密鍵Ｘ１を使って復号してΣｊ∈εｎＲｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算し、暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Σｊ∈δ１Ｒｊ）
を計算してユーザ２に送信し、
ＳｔｅｐＲ２：ユーザ２は、暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Σｊ∈δ１Ｒｊ）
を、非対称秘密鍵Ｘ２を使って復号してΣｊ∈δ１Ｒｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算し、暗号文
ＥＮＣ２，３＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２），Σｊ∈δ２Ｒｊ）
を計算してユーザ３に送信し、ｎ≧４のとき、
ユーザｉ（３≦ｉ≦ｎ−１）は、暗号文
ＥＮＣｉ−１，ｉ＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｉ−１Ｒｊ），Σｊ∈δｉ−１Ｒｊ）
を、ハッシュ値Ｈ（Σｊ∈εｉ−１Ｒｊ）を使って復号してΣｊ∈δｉ−１Ｒｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算し、暗号文
ＥＮＣｉ，ｉ＋１＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｉＲｊ），Σｊ∈δｉＲｊ）
を計算してユーザｉ＋１に送信し、
ＳｔｅｐＴ２：ユーザｎは、暗号文
ＥＮＣｎ−１，ｎ＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｎ−１Ｒｊ），Σｊ∈δｎ−１Ｒｊ）
を、ハッシュ値Ｈ（Σｊ∈εｎ−１Ｒｊ）を使って復号してΣｊ∈δｎ−１Ｒｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算し、
ＳｔｅｐＣ１：センタは、対話鍵
ＩＫ＝ＩＫ１＊ＩＫ２＊・・・＊ＩＫｎ  ｍｏｄｐ
＝ｇ＾（Ｒ１＋Ｒ２＋・・・＋Ｒｎ）  ｍｏｄｐ
を計算することを特徴とする対話鍵共有方法。
【請求項１４】
ｐを素数とし、ｑを（ｐ−１）の素因数とし、ｇを位数がｑであるＧＦ（ｑ）の元とし、ｐ，ｑ，ｇを固定のパラメータとして、ユーザ１〜ユーザｎ（ｎ≧３）とセンタに予め共有させておき、Ｘｉをユーザｉの非対称秘密鍵とし、ＹｉをユーザｉのＸｉに対する公開鍵とし、Ｐ＿ＥＮＣ（ｙ，ｍ）を、公開鍵ｙにより、公開鍵ｙに対応する非対称秘密鍵で復号できる暗号文に平文ｍを公開鍵方式で暗号化する関数とし、Ｃ＿ＥＮＣ（Ｋ，ｍ）を、対称秘密鍵Ｋにより復号できる暗号文に平文ｍを対称秘密鍵Ｋにより対称秘密鍵方式で暗号化する関数とし、Ｈを、ハッシュ関数とし、λを全ユーザＩＤの集合｛１，２，・・・，ｎ｝とし、εｉをユーザＩＤの集合｛２，・・・，ｉ｝とし、δｉをユーザＩＤの集合｛１，ｉ＋２，・・・，ｎ｝（＝λ−εｉ＋１）とし、非対称共通鍵の交換が可能なｎ台の端末間の通信をセンタで傍受して前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵共有方法において、
ＳｔｅｐＳ１：ユーザ１は、乱数Ｒ１，Ｄ１（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ１＝ｇ＾（Ｒ１）  ｍｏｄｐ
を計算し、チャレンジ
ＣＨＡ１＝ｇ＾（Ｄ１）  ｍｏｄｐ
を計算して、ＩＫ１とＣＨＡ１をユーザ２に送信し、
ＳｔｅｐＲ１：ユーザｉ（３≦ｉ≦ｎ−１）は、乱数Ｒｉ（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫｉ＝ｇ＾（Ｒｉ）  ｍｏｄｐ
を計算し、レスポンス
ＲＥＳｉ＝ＣＨＡ１＾（Ｒｉ）  ｍｏｄｐ
を計算し、ＩＫｉとＲＥＳｉとＣＨＡ１をユーザｉ＋１に送信し、
ＳｔｅｐＴ１：ユーザｎは、乱数Ｒｎ，Ｄｎ（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫｎ＝ｇ＾（Ｒｎ）  ｍｏｄｐ
を計算し、チャレンジ
ＣＨＡｎ＝ｇ＾（Ｄｎ）  ｍｏｄｐ
を計算し、レスポンス
ＲＥＳｎ＝ＣＨＡ１＾（Ｒｎ）  ｍｏｄｐ
を計算して、ＩＫｎとＲＥＳｎとＣＨＡｎをユーザ１に送信し、
ＳｔｅｐＳ２：ユーザ１は、レスポンス
ＲＥＳ１＝ＣＨＡｎ＾（Ｒ１）  ｍｏｄｐ
を計算して、ＲＥＳ１とＤ１をユーザ２に送信し、
ＳｔｅｐＲ２：ユーザ２は、暗号文
ＥＮＣ２，３＝Ｐ＿ＥＮＣ（Ｙ３，２‖Ｒ２）
を計算してユーザ３に送信し、ｎ≧４のとき、
ユーザｉ（３≦ｉ≦ｎ−１）は、暗号文
ＥＮＣｉ−１，ｉ＝Ｐ＿ＥＮＣ（Ｙｉ，ｉ−１‖Σｊ∈εｉ−１Ｒｊ）
を、非対称秘密鍵Ｘｉを使って復号してΣｊ∈εｉ−１Ｒｊを得て、暗号文
ＥＮＣｉ，ｉ＋１＝Ｐ＿ＥＮＣ（Ｙｉ＋１，ｉ‖Σｊ∈εｉＲｊ）
を計算してユーザｉ＋１に送信し、
ＳｔｅｐＴ２：ユーザｎは、暗号文
ＥＮＣｎ−１，ｎ＝Ｐ＿ＥＮＣ（Ｙｎ，ｎ−１‖Σｊ∈εｎ−１Ｒｊ）
を、非対称秘密鍵Ｘｎを使って復号してΣｊ∈εｎ−１Ｒｊを得て、暗号文
ＥＮＣｎ，１＝Ｐ＿ＥＮＣ（Ｙ１，ｎ‖Σｊ∈εｎＲｊ）
を計算して、ＥＮＣｎ，１とＤｎをユーザ１に送信し、
ＳｔｅｐＳ３：ユーザ１は、暗号文
ＥＮＣｎ，１＝Ｐ＿ＥＮＣ（Ｙ１，ｎ‖Σｊ∈εｎＲｊ）
を、非対称秘密鍵Ｘ１を使って復号してΣｊ∈εｎＲｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算し、暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Σｊ∈δ１Ｒｊ）
を計算してユーザ２に送信し、
ＳｔｅｐＲ３：ユーザ２は、暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Σｊ∈δ１Ｒｊ）
を、非対称秘密鍵Ｘ２を使って復号してΣｊ∈δ１Ｒｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算し、暗号文
ＥＮＣ２，３＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２），Σｊ∈δ２Ｒｊ）
を計算してユーザ３に送信し、
ユーザｉ（３≦ｉ≦ｎ−１）は、暗号文
ＥＮＣｉ−１，ｉ＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｉ−１Ｒｊ），Σｊ∈δｉ−１Ｒｊ）
を、ハッシュ値Ｈ（Σｊ∈εｉ−１Ｒｊ）を使って復号してΣｊ∈δｉ−１Ｒｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算し、暗号文
ＥＮＣｉ，ｉ＋１＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｉＲｊ），Σｊ∈δｉＲｊ）
を計算してユーザｉ＋１に送信し、
ＳｔｅｐＴ３：ユーザｎは、暗号文
ＥＮＣｎ−１，ｎ＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｎ−１Ｒｊ），Σｊ∈δｎ−１Ｒｊ）
を、ハッシュ値Ｈ（Σｊ∈εｎ−１Ｒｊ）を使って復号してΣｊ∈δｎ−１Ｒｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算し、
ＳｔｅｐＣ１：前記センターは、各ユーザのＲＥＳｉとＤ１とＤｎを受信し、ＲＥＳ２，…，ＲＥＳｎ，Ｄ１，ＲＥＳ１，Ｄｎの順に公開されていることを検証し、検証失敗ならエラーであることを全ユーザに送信して終了し、検証成功なら、
ＳｔｅｐＣ２：前記センターは、
Πｉ∈ε１ＲＥＳｉ≡（Πｉ∈ε１ＩＫｉ）＾（Ｄ１）  （ｍｏｄｐ）
ＲＥＳ１≡ＩＫ１＾（Ｄｎ）  （ｍｏｄｐ）
を検証し、検証失敗ならエラーであることを全ユーザに送信して終了し、検証成功なら、
ＳｔｅｐＣ３：前記センターは、対話鍵
ＩＫ＝Πｉ∈λ  ＩＫｉ  ｍｏｄｐ
を計算することを特徴とする対話鍵共有方法。
【請求項１５】
対話鍵の元データＩＫ１〜ＩＫｎを事前に計算しておくことを特徴とする請求項１３記載の対話鍵共有方法。
【請求項１６】
対話鍵の元データＩＫ１〜ＩＫｎとチャレンジＣＨＡ１とＣＨＡｎを事前に計算しておくことを特徴とする請求項１４記載の対話鍵共有方法。
【請求項１７】
ＳｔｅｐＣ２におけるレスポンスの計算を、
ＲＥＳ１≡ＩＫ１＾（Ｄｎ）  （ｍｏｄｐ）
ＲＥＳ２≡ＩＫ２＾（Ｄ１）  （ｍｏｄｐ），・・・，
ＲＥＳｎ≡ＩＫｎ＾（Ｄ１）  （ｍｏｄｐ）
と個別に行うことを特徴とする請求項１４記載の対話鍵共有方法。
【請求項１８】
Ｓｔｅｐ１で、各ユーザｉ（ｉ＝１・・・ｎ）は、
ａ）乱数Ｒｉ（∈Ｚｑ）を生成し、
ｂ）Ｚｑ上の任意のｎ次多項式ｆｉ（ｗ）
ｆｉ（ｗ）＝ｆｉ，０＊ｗ０＋ｆｉ，１＊ｗ１＋・＋ｆｉ，ｎ＊ｗｎ
を生成し、ｆｉ，０＝Ｒｉとし、
ｃ）検証値
Ｆｉ＝｛Ｆｉ，ｋ＝ｇ＾（ｆｉ，ｋ）｜ｋ＝０，１・・，ｎ｝
を事前に計算しておくことを特徴とする請求項３記載の対話鍵共有方法。
【請求項１９】
前記各端末は、非対称共通鍵ＣＫを計算した後に、検証式
Πｉ＝１ｎＩＫｉ≡ｇ＾（ＣＫ）  （ｍｏｄｐ）
を検証し、不成立なら前記センタに通知することを特徴とする請求項１４記載の対話鍵共有方法。
【請求項２０】
全ての送信メッセージに対して送信者のディジタル署名を付加し、受信者は前記署名の検証に成功した場合のみメッセージを受信することを特徴とする請求項２〜６、１４のいずれかに記載の対話鍵共有方法。
【請求項２１】
公開鍵方式の暗号関数Ｐ＿ＥＮＣ（・）としてＥｌ  Ｇａｍａｌ暗号の暗号関数を使用する場合において、ＩＫＡ，ＩＫＢまたはＩＫｉ（１≦ｉ≦ｎ）をＥｌ  Ｇａｍａｌ暗号における乱数のベキ乗剰余値の代わりに用いることを特徴とする請求項４、５、１４のいずれかに記載の対話鍵共有方法。
【請求項２２】
対称秘密鍵方式の暗号関数Ｃ＿ＥＮＣ（・）の代わりに公開鍵方式の暗号関数Ｐ＿ＥＮＣ（・）を用いることを特徴とする請求項４、５、１４のいずれかにに記載の対話鍵共有方法。
【請求項２３】
センタが対話鍵を計算後に、対話鍵に対する公開鍵証明書を発行することを特徴とする請求項２〜５、１４のいずれかに記載の対話鍵共有方法。
【請求項２４】
前記対話鍵に対する公開鍵証明書を対話鍵で暗号化して、対話鍵を共有したユーザに送信することを特徴とする請求項２３に記載の対話鍵共有方法。
【請求項２５】
前記ユーザを、携帯電話システムにおける携帯電話とし、前記センタを、携帯電話システムの通信キャリアのゲートウェイまたは基地局とすることを特徴とする請求項２〜２４のいずれかに記載の対話鍵共有方法。
【請求項２６】
前記ユーザを、ＰＣ／ＰＤＡ等のインターネット接続機能を有する端末とし、前記センタを、ウェブサーバまたはプロキシサーバまたはルータとすることを特徴とする請求項２〜２４のいずれかに記載の対話鍵共有方法。
【請求項２７】
前記ユーザを、ＰＣ／ＰＤＡ等のローカル通信機能を有する端末とし、前記センタを、特定の端末またはＬＡＮサーバとすることを特徴とする請求項２〜２４のいずれかに記載の対話鍵共有方法。
【請求項２８】
前記センタは複数あり、前記ユーザは、複数のセンタを経由して通信することを特徴とする請求項２〜２４のいずれかに記載の対話鍵共有方法。
【請求項２９】
有限体上の演算を楕円曲線上の演算に対応させて計算することを特徴とする請求項２〜８、１３、１４のいずれかに記載の対話鍵共有方法。
【請求項３０】
ユーザもセンタと同じ検証を実施することを特徴とする請求項３、５、１４のいずれかに記載の対話鍵共有方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、対話鍵とその生成法に関し、特に、鍵共有プロトコルにおいて、いつ誰が秘密鍵を共有したかが分かるようにした、秘密鍵に対応する公開鍵である対話鍵とその生成法に関する。
【０００２】
【従来の技術】
従来の鍵共有方式における共通鍵の共有方法を説明する。ＡｌｉｃｅとＢｏｂ間で共通鍵を共有する方法として、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ法と、その数多くのバリエーションや、これらを３つ以上のエンティティ間に拡張した方式（例えば［ＢＤ９４］）が知られている。共有された共通鍵は、多くの場合、共通鍵暗号やＭＡＣ（メッセージ認証子）に使用される。また、Ｓｅｒｖｅｒ−Ｃｌｉｅｎｔ間のセキュアセッションを提供するＳＳＬ３．０［ＳＳＬ］／ＴＬＳ１．０［ＴＬＳ］（鍵共有方式がＲＳＡの場合）のように、共通鍵の元となる値をＲＳＡで暗号化配送する方法も知られており、ここでも共有された共通鍵は、共通鍵暗号とＭＡＣに使用される。
【０００３】
これらの方式において、共有した共通鍵を公開鍵暗号の秘密鍵として使用するためには、共通鍵を保持するＡｌｉｃｅとＢｏｂが、事前に取り決めた共通鍵から公開鍵を生成する手順により計算して公開し、検証者が全ての公開鍵が等しいことを検証すればよい。以降、この方式をＳｉｍｐｌｅ  Ｍｅｔｈｏｄと呼ぶ。
【０００４】
公開鍵と秘密鍵の共有方法について説明する。ＲＳＡの公開鍵と秘密鍵をＡｌｉｃｅとＢｏｂ間で共有する方式［ＰＳ９８，Ｇ９９］、または３つ以上のエンティティ間で共有する方式［ＢＦ９７］が知られている。これらの方式では、プロトコルに参加する全エンティティが公開鍵を計算できるが、秘密鍵については、各エンティティはその分散値のみを計算できるという特徴を持つ。
【０００５】
しかしながら、［ＰＳ９８，Ｇ９９］では、プロトコルに参加するエンティティのみが自身の秘密鍵を用いて公開鍵を計算できる。また、［ＢＦ９７］では、プロトコルに参加するエンティティとして、Ｈｅｌｐｅｒと呼ばれる秘密鍵の分散値を得られないエンティティを仮定しており、Ｈｅｌｐｅｒのみが公開鍵を計算できる。結局、これらの方式においては、プロトコルに参加するエンティティしか公開鍵を計算できない。したがって、検証者が公開鍵を得るためには、Ｓｉｍｐｌｅ  Ｍｅｔｈｏｄと同様に、プロトコルに参加するエンティティが公開鍵を計算後に公開する必要がある。
【０００６】
Ｓｉｍｐｌｅ  Ｍｅｔｈｏｄについて説明する。簡単化のためユーザ数を２として、複数ユーザ間で共通鍵を共有し、各ユーザが共通鍵から計算した公開鍵を検証者に公開する例を示す。ＡｌｉｃｅとＢｏｂは、それぞれ公開鍵ＹＡｌｉｃｅとＹＢｏｂ、秘密鍵ＸＡｌｉｃｅとＸＢｏｂを保持しており、検証者はＹＡｌｉｃｅとＹＢｏｂを知っているものとする。また、ＡｌｉｃｅとＢｏｂは共通鍵から公開鍵を計算する手順を事前に共有している。
【０００７】
ＡｌｉｃｅとＢｏｂの処理は以下の通りである。
Ｓｔｅｐ１：既存の鍵共有方式（例えばＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ）を用いて、共通鍵ＣＫを共有する。
Ｓｔｅｐ２：Ａｌｉｃｅは、共通鍵ＣＫを公開鍵暗号の秘密鍵とする公開鍵ＰＫＡｌｉｃｅ（ＢｏｂはＰＫＢｏｂ）を計算する。
Ｓｔｅｐ３：Ａｌｉｃｅは、ＰＫＡｌｉｃｅ（ＢｏｂはＰＫＢｏｂ）に対して、ＸＡｌｉｃｅ（ＢｏｂはＸＢｏｂ）を用いて、ディジタル署名ＳＩＧＡｌｉｃｅ（ＢｏｂはＳＩＧＢｏｂ）を計算する。
Ｓｔｅｐ４：Ａｌｉｃｅは、ＰＫＡｌｉｃｅ（ＢｏｂはＰＫＢｏｂ）とＳＩＧＡｌｉｃｅ（ＢｏｂはＳＩＧＢｏｂ）を、検証者に公開する。
【０００８】
検証者の処理は、以下の通りである。
Ｓｔｅｐ５：署名ＳＩＧＡｌｉｃｅとＳＩＧＢｏｂを検証する。成功ならＳｔｅｐ６へ，失敗なら終了する。
Ｓｔｅｐ６：ＰＫＡｌｉｃｅ＝ＰＫＢｏｂなら受理し、不成立なら終了する。
【０００９】
通話内容証明について説明する。通話内容証明とは、ある複数のエンティティ間で行われた通話の内容を、通話後に第三者に証明するサービスである。従来の通話内容証明に利用可能なサービスとして、電子公証やタイムスタンプがある。タイムスタンプは、ある時点にコンテンツが存在していたことを証明する技術である。これらのサービスを通話内容証明に利用するためには、主にそれぞれのＡｕｔｈｏｒｉｔｙに通話内容を送信して、各Ａｕｔｈｏｒｉｔｙのディジタル署名を発行してもらい、サービスの利用者は、そのディジタル署名を検証者に公開することで通話内容を証明する。図７に、従来の通話内容証明方法の一例の手順を示す。
【００１０】
【非特許文献１】
［ＢＦ９７］Ｄ．  Ｂｏｎｅｈ，  Ｍ．  Ｆｒａｎｋｌｉｎ，  ”Ｅｆｆｉｃｉｅｎｔ  Ｇｅｎｅｒａｔｉｏｎ  ｏｆ  Ｓｈａｒｅｄ  ＲＳＡ  Ｋｅｙｓ，”  Ａｄｖａｎｃｅｄ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ  ’９７，  ｐｐ．  ４２５−４３９，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９７．
【非特許文献２】
［ＢＤ９４］Ｍ．  Ｂｕｒｍｅｓｔｅｒ，  Ｙ．  Ｄｅｓｍｅｄｔ，  ”Ａ  Ｓｅｃｕｒｅ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｃｏｎｆｅｒｅｎｃｅ  Ｋｅｙ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｓｙｓｔｅｍ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＥＵＲＯＣＲＹＰＴ’９４，  ｐｐ．２７５−  ２８５，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９４．
【非特許文献３】
［ＤＦ８９］Ｙ．  Ｄｅｓｍｅｄｔ，  Ｙ．  Ｆｒａｎｋｅｌ，  ”Ｔｈｒｅｓｈｏｌｄ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｃｒｙｐｔｏ’８９，  ＬＮＣＳ４３５，  ｐｐ．３０７−３１５，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９８９．
【非特許文献４】
［ＴＬＳ］Ｔ．  Ｄｉｅｒｋｓ，  Ｃ．  Ａｌｌｅｎ，  ”Ｔｈｅ  ＴＬＳ  Ｐｒｏｔｏｃｏｌ  Ｖｅｒｓｉｏｎ  １．０，”  Ｒｅｑｕｅｓｔ  ｆｏｒ  Ｃｏｍｍｅｎｔｓ：  ２２４６，  １９９９．
【非特許文献５】
［ＳＳＬ］Ａ．  Ｆｒｅｉｅｒ，  Ｐ．  Ｋａｒｌｔｏｎ，  ａｎｄ  Ｐ．  Ｋｏｃｈｅｒ，  ”Ｔｈｅ  ＳＳＬ  Ｐｒｏｔｏｃｏｌ  Ｖｅｒｓｉｏｎ  ３．０，”  Ｔｒａｎｓｐｏｒｔ  Ｌａｙｅｒ  Ｓｅｃｕｒｉｔｙ  Ｗｏｒｋｉｎｇ  Ｇｒｏｕｐ，  ＩＮＴＥＲＮＥＴ−ＤＲＡＦＴ，  １９９６．
【非特許文献６】
［Ｇ９９］Ｎ．  Ｇｉｌｂｏａ，  ”Ｔｗｏ  Ｐａｒｔｙ  ＲＳＡ  Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ，”  Ａｄｖａｎｃｅｄ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ’９９，  ｐｐ．  １１６−１２９，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９９．
【非特許文献７】
［Ｐ９１］Ｔ．  Ｐｅｄｅｒｓｏｎ，  ”Ａ  Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍ  ｗｉｔｈｏｕｔ  ａ  Ｔｒｕｓｔｅｄ  Ｐａｒｔｙ，”  Ａｄｖａｎｃｅｄ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＥＵＲＯ  ・・・・・’・・，  ｐｐ．  ５２２−５２６，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９１．
【非特許文献８】
［ＰＳ９８］Ｇ．  Ｐｏｕｐａｒｄ，  Ｊ．  Ｓｔｅｒｎ，  ”Ｇｅｎｅｒａｔｉｏｎ  ｏｆ  Ｓｈａｒｅｄ  ＲＳＡ  Ｋｅｙｓ  ｂｙ  Ｔｗｏ  Ｐａｒｔｉｅｓ，”  Ａｄｖａｎｃｅｄ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−  ・・・・・・・・・’・・，  ｐｐ．１１−２４，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９８．
【非特許文献９】
［Ｓ７９］Ａ．Ｓｈａｍｉｒ，  ”Ｈｏｗ  ｔｏ  ｓｈａｒｅ  ａ  ｓｅｃｒｅｔ”，  Ｃｏｍｍ．  Ａｓｓｏｃ．  Ｃｏｍｐｕｔ．Ｍａｃｈ．，  ｖｏｌ．２２，  ｎｏ．１１，  ｐｐ．６１２−３，  １９７９．
【００１１】
【発明が解決しようとする課題】
しかし、従来のＳｉｍｐｌｅ  Ｍｅｔｈｏｄでは、検証者は、公開鍵の署名と等しいことの検証しか行えないため、以下のような問題がある。
（１）検証者は、公開された公開鍵がいつ誰により共有された共通鍵に対応するか分からない。
（２）検証者は、公開鍵を公開しないユーザがいる場合に、公開鍵を受理できない。
【００１２】
また、従来の通話内容証明の方法には、大きく２つの問題がある。１つは、通話時刻と署名発行時刻が等しくないため、リアルタイム性に欠けるという問題である。２つ目は、Ａｕｔｈｏｒｉｔｙが受信した通話内容が、そもそも通話内容であることが保証されないという問題である。仮に、通話内容Ｍ（例えば契約書）に対して、ＡｌｉｃｅとＢｏｂの署名が発行されていても、ＡｌｉｃｅとＢｏｂが通話者であるとは限らない。なぜならば、先に署名したエンティティ（Ａｌｉｃｅ）は、後に署名するエンティティが誰であるか分からないため、通話者の署名であるとは保証できない。
【００１３】
例えば、Ａｕｔｈｏｒｉｔｙが受け取った通話内容として、
Ａｌｉｃｅが想定する通話内容：ＳＩＧ（ＳＥＣＲＥＴＡｌｉｃｅ，Ｍ）‖ＳＩＧ（ＳＥＣＲＥＴＢｏｂ，Ｍ）‖Ｍ
Ａｌｉｃｅが想定外の通話内容：ＳＩＧ（ＳＥＣＲＥＴＡｌｉｃｅ，Ｍ）‖ＳＩＧ（ＳＥＣＲＥＴＣｈａｒｌｅｙ，Ｍ）‖Ｍ
のどちらもありうる。
【００１４】
これを解決するために、通話内容にＡｌｉｃｅとＢｏｂの名を記載することもできるが、事前に通話内容やその署名を用意できない、検証者やＡｕｔｈｏｒｉｔｙがいちいちそれを確認する手間がかかる、通話内容が暗号化されていればそれもできない、といった問題がある。
【００１５】
これらを解決する次の方法が存在する。
▲１▼電話機等に、電話の通信ログを取るハードウエアを内蔵させて、通話データにタイムスタンプを付与するシステムがある。電話による商取引などの際、協定世界時（ＵＴＣ）に同期したタイムスタンプを通話データに付与できる音声記録公証システムである。時刻認証サービスを時刻認証局とし、タイムスタンプ局とボイス・ロギング・システムを組み合わせる。第三者機関による時刻認証を利用することで、通話内容の信頼性を確保できる。しかし、リアルタイム性が無いし、記録が通話内容であることの保証が、ログを取るハードウエアの信頼性に依存するという問題がある。
▲２▼ＡｌｉｃｅとＢｏｂしか持たない秘密鍵ＳＥＣＲＥＴＡｌｉｃｅＢｏｂにより作成した、通話内容に対する署名を発行し、検証者は、その秘密鍵に対応した公開鍵により通話内容を検証する。しかし、ＳＩＧ（ＳＥＣＲＥＴＡｌｉｃｅＢｏｂ，Ｍ）‖ＳＩＧ（ＳＥＣＲＥＴＡｌｉｃｅ，Ｍ）‖ＳＩＧ（ＳＥＣＲＥＴＢｏｂ，Ｍ）‖Ｍからは、ＡｌｉｃｅとＢｏｂ以外にも同じ秘密鍵を持つエンティティがいることが否定できないし、リアルタイム性も保証されない。
【００１６】
また、ユーザ数が２人の場合のみを想定しているＤＨ型対話鍵生成法を単純に３人以上に拡張した場合、各ユーザの演算量と通信量がそれぞれ人数に依存して増加し、効率が大きく低下するという問題がある。
【００１７】
本発明は、上記従来の問題を解決して、鍵共有プロトコルにおいて送受信される情報と公開鍵（対話鍵）の関係を検証できるようにして、対話鍵に対応する秘密鍵をいつ誰が共有したかが分かるようにすることを目的とする。また、ＤＨ型対話鍵生成法を、効率を低下させることなくユーザ数を３人以上に拡張することを目的とする。すなわち、検証者は、鍵共有プロトコルにおいてユーザ間で送受信される情報から、当該鍵共有プロトコルにより共有される秘密鍵に対応する公開鍵（対話鍵）を計算できるようにし、秘密鍵を共有可能な時点では公開鍵（対話鍵）も既に計算可能となっているようにして、リアルタイム性も保証されるようにする。なお、タイムスタンプは、ある時点にコンテンツが存在していたことを証明する技術であるのに対して、対話鍵は、ある時点以前に対話鍵に対応する共通鍵が存在しないことを証明する技術である。
【００１８】
【課題を解決するための手段】
上記の課題を解決するために、本発明では、非対称共通鍵を計算可能な鍵交換手段を持つ複数の端末と、センタとからなる鍵交換システムのセンタに、端末間の通信を傍受可能な傍受手段と、傍受した通信から非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する手段とを備えた構成とした。
【００１９】
このように構成したことにより、鍵共有プロトコルにおいて送受信される情報と公開鍵（対話鍵）の関係が検証でき、対話鍵に対応する非対称秘密鍵をいつ誰が共有したかが分かる。また、ユーザが３人以上の場合には、リング型の通信経路を採用して、各ユーザの通信先を限定することにより、演算量と通信量を削減することができる。
【００２０】
【発明の実施の形態】
以下、本発明の実施の形態について、図１〜図６を参照しながら詳細に説明する。
【００２１】
（第１の実施の形態）
本発明の第１の実施の形態は、複数のユーザ端末の間で、秘密分散法を利用した鍵共有プロトコルにより非対称共通鍵を秘密に共有し、センタは、傍受した端末間の通信から、秘密に共有された非対称共通鍵に対応するグループ公開鍵（対話鍵）を計算する、Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍ（ＴＣ）型の対話鍵共有システムである。
【００２２】
図１は、本発明の第１の実施の形態における対話鍵共有システムの概念図である。図１において、ユーザ１（Ａｌｉｃｅ）とユーザ２（Ｂｏｂ）は、証明を必要とする通話を行なう当事者である。オブザーバ３（Ｃｈａｒｌｅｙ）は、通信を傍受して、通話内容に関して証明を行なうセンタである。対話文４は、ユーザの間で通信される鍵共有のためのデータである。共通鍵５は、ユーザにより秘密に共有される暗号鍵である。対話鍵６は、共通鍵５に対応する公開鍵であり、対話文４と公開情報からだれでも生成できる。
【００２３】
図２は、本発明の第１の実施の形態における対話鍵共有システムの構成図である。図２において、鍵交換手段７は、非対称共通鍵を、対話文から計算する手段である。傍受手段８は、端末間の通信を傍受する手段である。対話鍵計算手段９は、対話文から対話鍵を計算する手段である。図３は、対話鍵共有システムの動作手順を示す流れ図である。
【００２４】
本発明の第１の実施の形態における対話鍵共有システムの動作原理と動作手順を説明する。最初に、図１を参照しながら、“対話鍵”の概念を説明する。通信を行なう複数エンティティ、例えばＡｌｉｃｅ（ユーザ１）とＢｏｂ（ユーザ２）がある。この例では２つであるが、３つ以上でもよい。ＡｌｉｃｅとＢｏｂの間で、ある鍵共有プロトコルＺを実行し、共通鍵ＣＫを共有する。この共通鍵ＣＫは、公開鍵方式（非対称鍵方式）のグループ秘密鍵である。ＡｌｉｃｅとＢｏｂの間の通信を観察（傍受）することにより、鍵共有を行わないで対話鍵ＩＫを生成するエンティティ（オブザーバ３（Ｃｈａｒｌｅｙ））がある。“対話鍵”とは、この共通鍵ＣＫを非対称秘密鍵とするグループ公開鍵である。対話鍵は、鍵共有プロトコルＺにおいてＡｌｉｃｅとＢｏｂ間で送受信される公開の対話文ＩＭから、アルゴリズムαにより計算できなければならない。
【００２５】
“対話鍵”の最大の特徴は、いつ誰によって共有された非対称共通鍵に対応する公開鍵であるのかを、Ｃｈａｒｌｅｙ自身が判断できる点にある。例えば、ＡｌｉｃｅとＢｏｂを、携帯電話やＰＣを持つユーザとし、Ｃｈａｒｌｅｙを、通信キャリアのＧＷやＩＳＰとする。このとき、対話鍵のアプリケーションとして、通話内容証明と公開鍵証明書の発行が考えられる。前者（通話内容証明）は、ＡｌｉｃｅとＢｏｂが非対称共通鍵を使用して、暗号化・署名した通話（例えば契約に関する通話）を行い、Ｃｈａｒｌｅｙはその通話を記録しておき、検証者の要求に応じて、対話鍵を用いて通話内容を証明するサービスである。後者（公開鍵証明書の発行）は、Ｃｈａｒｌｅｙが対話鍵に対する公開鍵証明書を発行するサービスである。いずれも、通話内容や証明書の検証者が、いつ誰が共有した対話鍵か判断できることが利点となる。
【００２６】
用語を以下のように定義する。
（１）ユーザ：非対称共通鍵の共有を行うユーザである。ユーザ同士の結託によるオブザーバへの攻撃は想定しない。ユーザ数が２の場合はＡｌｉｃｅとＢｏｂと呼ぶ。
（２）オブザーバ：ユーザ間の対話を観察できる第三者であり、対話文ＩＭから対話鍵ＩＫを計算する多項式時間アルゴリズムαと、対話文ＩＭと対話鍵ＩＫの関係を検証する多項式アルゴリズムβを持つ。オブザーバ数が１の場合はＣｈａｒｌｅｙと呼ぶ。
（３）非対称共通鍵（ＣＫ）：ある時点において、複数のユーザが鍵共有プロトコルにより秘密に共有した非対称共通鍵である。公開鍵方式（非対称鍵方式）でない秘密鍵方式（対称鍵方式）の共通鍵（対称秘密鍵）と区別するために、非対称共通鍵とよぶことにする。公開鍵方式の個別の秘密鍵を、非対称秘密鍵とよぶ。
（４）対話：非対称共通鍵ＣＫの共有のため行われるユーザ間の平文の交換である。この平文を対話文（ＩＭ）と呼ぶ。
（５）対話鍵（ＩＫ）：全ユーザをメンバとするグループの公開鍵であり、入力を対話文ＩＭ、出力を対話鍵ＩＫとする多項式時間アルゴリズムαにより計算される。ここで、対話鍵ＩＫは、対話文ＩＭにより共有された非対称共通鍵ＣＫを非対称秘密鍵とする公開鍵である。
（６）検証者：通話者（ユーザ）とオブザーバ以外の第三者であり、通話内容の検証を求める者である。
【００２７】
以下に、本発明が満たすべき条件を示す。一般の鍵共有方式で要求される条件は省略するが、本発明においても満たす必要がある。
（１）生成可能性：対話文ＩＭから対話鍵ＩＫを計算する多項式時間アルゴリズムαが存在する。
（２）検証可能性：対話文ＩＭと対話鍵ＩＫの関係を検証する多項式時間アルゴリズムβが存在する。
（３）耐性：全ユーザが非対称共通鍵ＣＫを計算できる時点では、必ずオブザーバも対話鍵ＩＫを計算できる。
（４）守秘性：オブザーバが対話文ＩＭから非対称共通鍵ＣＫを得られない。
【００２８】
以下に、本発明に用いる記号を定義し、簡単に説明する。
（１）ｐ：大きな素数である。大きな素数とは、例えば、１０２４ｂｉｔ程度の素数であり、離散対数問題が事実上解けない大きさの素数である。
（２）ｑ：（ｐ−１）を割り切る大きな素数である。例えば、１６０ｂｉｔ程度の素数である。
（３）ｇ：Ｚ＊ｐでの位数がｑとなる元である。すなわち、Ｚ＊ｐ上の乗法群で、ｇｑ＝１  ｍｏｄｐであり、０＜ｒ＜ｑであるｒでは、ｇｒ≠１  ｍｏｄｐである。Ｚ＊ｐは、０以上ｐ未満かつｐと互いに素な整数の集合である。Ｚｑは、０以上ｑ未満の整数の集合である。ｐが素数の場合は、Ｚ＊ｐはＺｐ−｛０｝である。ｐ，ｑ，ｇは固定のパラメータであり、全エンティティが予め共有しているものとする。この例では、簡単化のために、離散対数問題型の暗号方式を用いるが、楕円曲線暗号を用いてもよい。
（４）Ｈ：ハッシュ関数である。
（５）Ｘｉ：ユーザｉの非対称秘密鍵である。
（６）Ｙｉ：ユーザｉの非対称秘密鍵Ｘｉに対する公開鍵である。ここでは、簡単化のために、同じ鍵ペアを公開鍵暗号およびディジタル署名に使用するが、実際には別々の鍵ペアを使用することが望ましい。
（７）ｉ：Ｘｉを秘密に保持するユーザのＩＤであり、（１≦ｉ≦ｎ）の整数である。整数ｉをＩＤとするユーザを、ユーザｉまたはＵｓｅｒ  ｉとよぶ。
（８）Ｐ＿ＥＮＣ（ｙ，ｍ）：公開鍵ｙにより平文ｍを公開鍵方式で暗号化する関数である。公開鍵ｙに対応する非対称秘密鍵で復号できる。
（９）Ｃ＿ＥＮＣ（Ｋ，ｍ）：対称秘密鍵Ｋにより平文ｍを対称秘密鍵方式で暗号化する関数である。対称秘密鍵Ｋにより復号できる。
（１０）ＭＡＣ（Ｋ，ｍ）：対称秘密鍵Ｋにより平文ｍに対するＭＡＣ（メッセージ認証子）を生成する関数である。対称秘密鍵Ｋによりｍに対する改ざんの有無を検証できる。
（１１）ＳＩＧ（ｘ，ｍ）：非対称秘密鍵ｘにより平文ｍに署名する関数である。非対称秘密鍵ｘに対応する公開鍵により署名の検証ができる。ここでは、例として添付型の署名方式を想定している。
（１２）Ｌ（Ψ，ｗ）：ラグランジェ補間係数（Ψ：集合，ｗ：整数）であり、
Ｌ（Ψ，ｗ）＝Πｔ∈Ψ＼｛ｗ｝  ｔ／（ｔ−ｗ）  ｍｏｄｑ
で定義される。Ψ＼｛ｗ｝は、集合Ψから集合｛ｗ｝を除いた集合である。
【００２９】
次に、Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍ（ＴＣ）型の対話鍵生成方法の概要を説明する。ユーザの総数をｎ（２≦ｎ≦ｑ−１）とする。秘密分散法における分散値から秘密値を復元できる閾値を（ｎ＋１）とする。すなわち、（ｎ＋１）個以上の分散値があれば、秘密値を復元できる。分散値の総数を２ｎ（分散値の番号の集合をΔとする）とする。このようなｔｈｒｅｓｈｏｌｄ  ｃｒｙｐｔｏｓｙｓｔｅｍを用いることにより、対話鍵を生成可能な鍵共有法を構成できる。秘密分散法の詳細は、［ＤＦ８９］や［Ｐ９１］を参照。
【００３０】
各ユーザｉは、以下の処理を実施する。
Ｓｔｅｐ１：秘密分散法により、閾値を（ｎ＋１）とする非対称共通鍵ＣＫ（∈Ｚｑ）の分散値ＣＫ２ｉ−１，ＣＫ２ｉ（∈Ｚｑ）を生成する。
Ｓｔｅｐ２：ＩＫｉ（＝ｇ＾（ＣＫ２ｉ−１）  ｍｏｄｐ）、ＣＫ２ｉ、検証値Ｆｉ（分散値の生成に用いた多項式の係数を指数とし、ｇを底とし、ｐを法としたベキ乗剰余値）を計算する。
Ｓｔｅｐ３：ＩＫｉ，ＣＫ２ｉ，Ｆｉを公開する。
Ｓｔｅｐ４：合計（ｎ＋１）個の分散値（公開されたｎ個と自身の１個）から非対称共通鍵ＣＫを復元する。
【００３１】
Ｃｈａｒｌｅｙは、以下の処理を実施する。
Ｓｔｅｐ５：全ＩＫｉ，ＣＫ２ｉをＦｉで検証し、成功ならばＳｔｅｐ６へ、失敗ならばＥｒｒｏｒを公開する。
Ｓｔｅｐ６：ＩＫ＝Πｉ＝１ｎ  （ＩＫｉＬ（Δ，  ２ｉ−１）＊ｇ＾（ＣＫ２ｉ＊Ｌ（Δ，２ｉ）））  ｍｏｄｐを計算する。この結果は、ＩＫ＝ｇＣＫ  ｍｏｄｐとなる。
【００３２】
Ｃｈａｒｌｅｙは、ＩＫｉとｇ＾（ＣＫ２ｉ）を合わせて、（ｎ＋１）以上の分散値を集められるために、ＩＫを計算できる。しかし、ＣＫ２ｉをｎ以下しか集められないために、ＣＫを復元できない。
【００３３】
Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍ（ＴＣ）型の対話鍵生成方法を詳しく説明する。
（１）ユーザｉの処理
（Ｓｔｅｐ１）
ａ）乱数Ｒｉ（∈Ｚｑ）を生成する。
ｂ）Ｚｑ上の任意のｎ次多項式ｆｉ  （ｗ）を生成する。
ｃ）ｆｉ，０＝Ｒｉとして、
ｆｉ（ｗ）＝ｆｉ，０＊ｗ０＋ｆｉ，１＊ｗ１＋・＋ｆｉ，ｎ＊ｗｎ
を計算する。
ｄ）Ｆｉ＝｛Ｆｉ，ｋ＝ｇ＾（ｆｉ，ｋ）｜ｋ＝０，１・・，ｎ｝を計算する。
ｅ）ＣＫｉ，ｊ＝ｆｉ（ｊ）  （ｊ＝１・・・・・・２ｎ）を計算する。ユーザｉは、２つの分散値を保持する。このとき、ｉに対応するｊは、（２ｉ−１）と（２ｉ）となる。
ｆ）自身以外の全てのユーザｖ（ｖ≠ｉ）に対して、
ＥＮＣｉ，ｖ＝Ｐ＿ＥＮＣ（Ｙｖ，ｉ‖ＣＫｉ，２ｖ−１‖ＣＫｉ，２ｖ）
を計算する。
ｇ）ＥＮＣｉ，ｖに対する署名ＳＩＧ（Ｘｉ，ｉ‖ＥＮＣｉ，ｖ）を計算し、ＥＮＣｉ，ｖと共にユーザｖに送信する。
ｈ）Ｆｉに対する署名ＳＩＧ（Ｘｉ，ｉ‖Ｆｉ）を計算し、Ｆｉと共に全ユーザに送信する。ここで、‖は連接を意味する。
【００３４】
（Ｓｔｅｐ２）
ａ）全ユーザｖ（ｖ≠ｉ）のＥＮＣｖ，ｉ，ＳＩＧ（Ｘｖ，ｖ‖ＥＮＣｖ，ｉ），Ｆｖ，ＳＩＧ（Ｘｖ，ｖ‖Ｆｖ）を受信する。
ｂ）ＹｖでＳＩＧ（Ｘｖ，ｖ‖ＥＮＣｖ，ｉ）を検証し、成功すれば、ＥＮＣｖ，ｉをＸｉで復号し、ＣＫｖ，２ｉ−１‖ＣＫｖ，２ｉを得る。正しくなければ、Ｅｒｒｏｒを全ユーザに送信する。
ｃ）ＣＫ２ｉ−１＝Σｖ＝１ｎ  ＣＫｖ，２ｉ−１  ｍｏｄｑを計算する。
ｄ）ＣＫ２ｉ＝Σｖ＝１ｎ  ＣＫｖ，２ｉ  ｍｏｄｑを計算する。
ｅ）ＩＫｉ＝ｇ＾（ＣＫ２ｉ−１）  ｍｏｄｐを計算する。
ｆ）ＩＫｉ，ＣＫ２ｉに対する署名ＳＩＧ（Ｘｉ，ｉ‖ＩＫｉ‖ＣＫ２ｉ）を計算し、ＩＫｉ，ＣＫ２ｉと共に全ユーザに送信する。
【００３５】
（Ｓｔｅｐ３）
ａ）自身の分散値と受信した分散値の番号の集合をφとしたとき、
ＣＫ＝Σｈ∈φ  （ＣＫｈ＊Ｌ（φ，ｈ））  ｍｏｄｑ
を計算する。この結果、ＣＫ＝Σｉ＝１ｎ  Ｒｉ  ｍｏｄｑとなる。
【００３６】
（２）Ｃｈａｒｌｅｙの処理
（Ｓｔｅｐ１）
ａ）ｉ＝１，・，ｎに対し、ＹｉでＳＩＧ（Ｘｉ，ｉ‖Ｆｉ）とＳＩＧ（Ｘｉ，ｉ‖ＩＫｉ‖ＣＫ２ｉ）を検証し、検証成功ならｂ）へ進む。検証失敗なら、Ｅｒｒｏｒを全ユーザに送信して終了する。
ｂ）ｉ＝１，・，ｎに対し、ＩＫｉとＣＫ２ｉを式（１）により検証し、検証成功ならｃ）へ進む。
ｇ＾（ＣＫｊ）＝Πｉ＝１ｎ  （Πｋ＝０ｎ  Ｆｉ，ｋ＾（ｊｋ））  ｍｏｄｐ  ・・・・・  （１）
Πｋ＝０ｎ  Ｆｉ，ｋ＾（ｊｋ）  ｍｏｄｐ＝Πｋ＝０ｎ  （ｇ＾（ｆｉ，ｋ））＾（ｊｋ）  ｍｏｄｐ
＝Πｋ＝０ｎ  ｇ＾（ｆｉ，ｋ＊ｊｋ）  ｍｏｄｐ
＝ｇ＾（Σｋ＝０ｎ  ｆｉ，ｋ＊ｊｋ）  ｍｏｄｐ
＝ｇ＾（ｆｉ（ｊ））  ｍｏｄｐ
＝ｇ＾（ＣＫｉ，ｊ）  ｍｏｄｐ
Πｉ＝１ｎ  （ｇ＾（ＣＫｉ，ｊ））  ｍｏｄｐ
＝ｇ＾（Σｉ＝１ｎ  ＣＫｉ，ｊ）  ｍｏｄｐ
＝ｇ＾（ＣＫｊ）  ｍｏｄｐ
検証失敗ならＥｒｒｏｒを全ユーザに送信して終了する。
ｃ）対話鍵
ＩＫ＝Πｉ＝１ｎ  （ＩＫｉＬ（Δ，２ｉ−１）＊ｇ＾（ＣＫ２ｉ＊Ｌ（Δ，２ｉ））  ｍｏｄｑ
を計算する。式（１）による検証およびＩＫの生成は各ユーザも可能だが、この例では、Ｃｈａｒｌｅｙが一括して行う。
【００３７】
次に、図２を参照しながら、対話鍵共有システムの構成と機能の概略を説明する。通信端末などであるユーザ１（Ａｌｉｃｅ）とユーザ２（Ｂｏｂ）は、鍵交換手段７を備えている。鍵交換手段７は、公開鍵方式のグループ秘密鍵である非対称共通鍵を、対話文４から計算できる。センタであるオブザーバ３（Ｃｈａｒｌｅｙ）は、端末間の通信を傍受できる傍受手段８と、傍受した通信の対話文４から、非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵計算手段９とを備えている。
【００３８】
鍵交換手段７は、送受信手段と、乱数発生手段と、演算手段と、記憶手段などを備えている。鍵交換手段７の基本的な機能は、従来の暗号通信システムにおける鍵交換手段と同様であり、詳しい説明は省略する。傍受手段８は、通常の受信手段と同様であり、従来のものと変わりはない。対話鍵計算手段９は、本発明特有のアルゴリズムにより、対話文４から対話鍵を計算する手段である。対話鍵の計算方法は前述のとおりである。
【００３９】
次に、図３を参照しながら、ｎ＝２（閾値３、分散値数４）の場合の対話鍵共有方法の具体例を説明する。ユーザ１をＡｌｉｃｅとし、ユーザ２をＢｏｂとする。ここでは、分かり易くするために、ユーザＩＤの１をＡｌｉｃｅと書き、Ｘ１をＸＡｌｉｃｅと表記する。その他も同様である。
【００４０】
Ａｌｉｃｅ（ｉ＝１）は、Ｓｔｅｐ１で、
ａ）乱数ＲＡｌｉｃｅ（∈Ｚｑ）を生成する。
ｂ）定数項ｆＡｌｉｃｅ，０を乱数ＲＡｌｉｃｅとするＺｑ上の任意の２次多項式ｆＡｌｉｃｅ（ｗ）を生成する。
ｆＡｌｉｃｅ（ｗ）＝ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊ｗ１＋ｆＡｌｉｃｅ，２＊ｗ２
ｃ）検証値の集合ＦＡｌｉｃｅを生成する。
ＦＡｌｉｃｅ＝｛ＦＡｌｉｃｅ，ｋ＝ｇ＾（ｆＡｌｉｃｅ，ｋ）  ｍｏｄｐ｜ｋ＝０，１，２｝
これは集合であるが、実際には、各要素を連接した数として表すので、以下、表記上は数として扱う。
ｄ）分散値の元データを生成する。
ＣＫＡｌｉｃｅ，ｊ＝ｆＡｌｉｃｅ（ｊ）  （ｊ＝１，…，４）
すなわち、
ＣＫＡｌｉｃｅ，１＝ｆＡｌｉｃｅ（１）＝ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊１＋ｆＡｌｉｃｅ，２＊１２
ＣＫＡｌｉｃｅ，２＝ｆＡｌｉｃｅ（２）＝ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊２＋ｆＡｌｉｃｅ，２＊２２
ＣＫＡｌｉｃｅ，３＝ｆＡｌｉｃｅ（３）＝ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊３＋ｆＡｌｉｃｅ，２＊３２
ＣＫＡｌｉｃｅ，４＝ｆＡｌｉｃｅ（４）＝ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊４＋ｆＡｌｉｃｅ，２＊４２
ｅ）分散値の元データを暗号化する。
ＥＮＣＡｌｉｃｅ，Ｂｏｂ＝Ｐ＿ＥＮＣ（ＹＢｏｂ，ＣＫＡｌｉｃｅ，３‖ＣＫＡｌｉｃｅ，４）
ｆ）署名ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＦＡｌｉｃｅ‖ＥＮＣＡｌｉｃｅ，Ｂｏｂ）を計算する。
ｇ）各データを連接して、
Ａｌｉｃｅ‖ＦＡｌｉｃｅ‖ＥＮＣＡｌｉｃｅ，Ｂｏｂ‖ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＦＡｌｉｃｅ‖ＥＮＣＡｌｉｃｅ，Ｂｏｂ）
として、Ｂｏｂに送信する。
【００４１】
Ｓｔｅｐ２で、
ａ）Ｂｏｂからデータを受信し、ＹＢｏｂでＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＦＢｏｂ‖ＥＮＣＢｏｂ）を検証し、成功ならＥＮＣＢｏｂ，ＡｌｉｃｅをＸＡｌｉｃｅで復号し、ＣＫＢｏｂ，１とＣＫＢｏｂ，２を得る。
ｂ）分散値を計算する。
【００４２】
ＣＫｊ＝ＣＫＡｌｉｃｅ，ｊ＋ＣＫＢｏｂ，ｊ  ｍｏｄｑ  （ｊ＝１，２）
すなわち、
ＣＫ１＝ＣＫＡｌｉｃｅ，１＋ＣＫＢｏｂ，１  ｍｏｄｑ
ＣＫ２＝ＣＫＡｌｉｃｅ，２＋ＣＫＢｏｂ，２  ｍｏｄｑ
ｃ）対話鍵の元データを計算する。
ＩＫＡｌｉｃｅ＝ｇ＾（ＣＫ１）  ｍｏｄｐ
ｄ）署名ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＩＫＡｌｉｃｅ‖ＣＫ２）を生成する。
ｅ）各データを連接して、
Ａｌｉｃｅ‖ＩＫＡｌｉｃｅ‖ＣＫ２‖ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＩＫＡｌｉｃｅ‖ＣＫ２）
として、Ｂｏｂに送信する。
【００４３】
Ｓｔｅｐ３で、
ａ）Ｂｏｂからデータを受信し、ＹＢｏｂでＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＩＫＢｏｂ‖ＣＫ４）を検証し、成功なら非対称共通鍵を計算する。
ＣＫ＝ＣＫ１＊Ｌ（Δ＼｛３｝，１）
＋ＣＫ２＊Ｌ（Δ＼｛３｝，２）
＋ＣＫ４＊Ｌ（Δ＼｛３｝，４）  ｍｏｄｑ
＝（ＣＫＡｌｉｃｅ，１＋ＣＫＢｏｂ，１  ｍｏｄｑ）＊（２／（２−１））（４／（４−１））
＋（ＣＫＡｌｉｃｅ，２＋ＣＫＢｏｂ，２  ｍｏｄｑ）＊（１／（１−２））（４／（４−２））
＋（ＣＫＡｌｉｃｅ，４＋ＣＫＢｏｂ，４  ｍｏｄｑ）＊（１／（１−４））（２／（２−４））  ｍｏｄｑ
＝｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊１＋ｆＡｌｉｃｅ，２＊１２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊１＋ｆＢｏｂ，２＊１２）｝＊（８／３）
＋｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊２＋ｆＡｌｉｃｅ，２＊２２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊２＋ｆＢｏｂ，２＊２２）｝＊（−２）
＋｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊４＋ｆＡｌｉｃｅ，２＊４２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊４＋ｆＢｏｂ，２＊４２）｝＊（１／３）
＝（ＲＡｌｉｃｅ＋ＲＢｏｂ）＊（（８／３）−２＋（１／３））
＋（ｆＡｌｉｃｅ，１＋ｆＢｏｂ，１）＊（（８／３）−４＋（４／３））
＋（ｆＡｌｉｃｅ，２＋ｆＢｏｂ，２）＊（（８／３）−８＋（１６／３））
＝ＲＡｌｉｃｅ＋ＲＢｏｂ  ｍｏｄｑ
この計算は、ＧＦ（ｑ）上の演算である。
【００４４】
Ｂｏｂの手順を説明する。ここでは、分かり易くするために、ユーザＩＤの２をＢｏｂと書き、Ｘ２をＸＢｏｂと表記する。その他も同様である。Ｂｏｂ（ｉ＝２）は、Ｓｔｅｐ１で、
ａ）１６０ｂｉｔ程度の乱数ＲＢｏｂ（∈Ｚｑ）を生成する。
ｂ）定数項を乱数ＲＢｏｂとするＺｑ上の任意の２次多項式ｆＢｏｂ（ｗ）を生成する。
ｆＢｏｂ（ｗ）＝ｆＢｏｂ，０＋ｆＢｏｂ，１＊ｗ１＋ｆＢｏｂ，２＊ｗ２
ｃ）検証値の集合ＦＢｏｂを生成する。
ＦＢｏｂ＝｛ＦＢｏｂ，ｋ＝ｇ＾（ｆＢｏｂ，ｋ）｜ｋ＝０，１，２｝
実際には、各要素を連接した数として表す。
ｄ）分散値の元データを生成する。
ＣＫＢｏｂ，ｊ＝ｆＢｏｂ（ｊ）  ｆｏｒ  ｊ＝１，…，４
ｅ）分散値の元データを暗号化する。
ＥＮＣＢｏｂ，Ａｌｉｃｅ＝Ｐ＿ＥＮＣ（ＹＡｌｉｃｅ，ＣＫＢｏｂ，１‖ＣＫＢｏｂ，２）
ｆ）署名ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＦＢｏｂ‖ＥＮＣＢｏｂ，Ａｌｉｃｅ）を計算する。
ｇ）各データを連接して、
Ｂｏｂ‖ＦＢｏｂ‖ＥＮＣＢｏｂ，Ａｌｉｃｅ‖ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＦＢｏｂ‖ＥＮＣＢｏｂ，Ａｌｉｃｅ）
として、Ｂｏｂに送信する。
【００４５】
Ｓｔｅｐ２で、
ａ）Ａｌｉｃｅからデータを受信し、ＹＡｌｉｃｅでＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＦＡｌｉｃｅ‖ＥＮＣＡｌｉｃｅ，Ｂｏｂ）を検証し、成功ならＥＮＣＡｌｉｃｅ，ＢｏｂをＸＢｏｂで復号し、ＣＫＡｌｉｃｅ，３とＣＫＡｌｉｃｅ，４を得る。
ｂ）分散値を計算する。
ＣＫｊ＝ＣＫＡｌｉｃｅ，ｊ＋ＣＫＢｏｂ，ｊ  ｍｏｄｑ  （ｊ＝３，４）
ｃ）対話鍵の元データを計算する。
ＩＫＢｏｂ＝ｇ＾（ＣＫ３）  ｍｏｄｐ
ｄ）署名ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＩＫＢｏｂ‖ＣＫ４）を生成する。
ｅ）各データを連接して、
Ｂｏｂ‖ＩＫＢｏｂ‖ＣＫ４‖ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＩＫＢｏｂ‖ＣＫ４）
として、Ｂｏｂに送信する。
【００４６】
Ｓｔｅｐ３で、
ａ）Ａｌｉｃｅからデータを受信し、ＹＡｌｉｃｅでＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＩＫＡｌｉｃｅ‖ＣＫ２）を検証し、成功なら非対称共通鍵を計算する。
ＣＫ＝ＣＫ２＊Ｌ（Δ＼｛１｝，２）
＋ＣＫ３＊Ｌ（Δ＼｛１｝，３）
＋ＣＫ４＊Ｌ（Δ＼｛１｝，４）  ｍｏｄｑ
＝（ＣＫＡｌｉｃｅ，２＋ＣＫＢｏｂ，２  ｍｏｄｑ）＊（３／（３−２））（４／（４−２））
＋（ＣＫＡｌｉｃｅ，３＋ＣＫＢｏｂ，３  ｍｏｄｑ）＊（２／（２−３））（４／（４−３））
＋（ＣＫＡｌｉｃｅ，４＋ＣＫＢｏｂ，４  ｍｏｄｑ）＊（２／（２−４））（３／（３−４））  ｍｏｄｑ
＝｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊２＋ｆＡｌｉｃｅ，２＊２２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊２＋ｆＢｏｂ，２＊２２）｝＊６
＋｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊３＋ｆＡｌｉｃｅ，２＊３２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊３＋ｆＢｏｂ，２＊３２）｝＊（−８）
＋｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊４＋ｆＡｌｉｃｅ，２＊４２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊４＋ｆＢｏｂ，２＊４２）｝＊３
＝（ＲＡｌｉｃｅ＋ＲＢｏｂ）＊（６−８＋３）
＋（ｆＡｌｉｃｅ，１＋ｆＢｏｂ，１）＊（１２−２４＋１２）
＋（ｆＡｌｉｃｅ，２＋ｆＢｏｂ，２）＊（２４−７２＋４８）
＝ＲＡｌｉｃｅ＋ＲＢｏｂ  ｍｏｄｑ
この計算は、ＧＦ（ｑ）上の演算である。
【００４７】
Ｃｈａｒｌｅｙは、Ｓｔｅｐ３で、
ａ）ＹＡｌｉｃｅを用いて、
ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＦＡｌｉｃｅ‖ＥＮＣＡｌｉｃｅ）と
ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＩＫＡｌｉｃｅ‖ＣＫ２）を検証し、
ＹＢｏｂを用いて、
ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＦＢｏｂ‖ＥＮＣＢｏｂ）と
ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＩＫＢｏｂ‖ＣＫ４）を検証し、
成功ならｂ）の処理を行う。
ｂ）ＦＡｌｉｃｅとＦＢｏｂを用いて、ＩＫＡ，ＣＫ２とＩＫＢ，ＣＫ４を検証し、成功ならｃ）の処理を行う。
【００４８】
ｃ）対話鍵を計算する。
ＩＫ＝ＩＫＡｌｉｃｅ＾（Ｌ（Δ，１））＊ｇ＾（ＣＫ２＊Ｌ（Δ，２））
＊ＩＫＢｏｂ＾（Ｌ（Δ，３））＊ｇ＾（ＣＫ４＊Ｌ（Δ，４））  ｍｏｄｐ
＝ｇ＾（ＣＫ１＊（２／（２−１））（３／（３−１））（４／（４−１）））
＊ｇ＾（ＣＫ２＊（１／（１−２））（３／（３−２））（４／（４−２）））
＊ｇ＾（ＣＫ３＊（１／（１−３））（２／（２−３））（４／（４−３）））
＊ｇ＾（ＣＫ４＊（１／（１−４））（２／（２−４））（３／（３−４）））  ｍｏｄｐ
＝ｇ＾（ＣＫ１＊４＋ＣＫ２＊（−６）＋ＣＫ３＊４＋ＣＫ４＊（−１））  ｍｏｄｐ
＝ｇＣＫ  ｍｏｄｐ
（ＣＫ１＊４＋ＣＫ２＊（−６）＋ＣＫ３＊４＋ＣＫ４＊（−１））
＝（ＣＫＡｌｉｃｅ，１＋ＣＫＢｏｂ，１）＊４＋（ＣＫＡｌｉｃｅ，２＋ＣＫＢｏｂ，２）＊（−６）
＋（ＣＫＡｌｉｃｅ，３＋ＣＫＢｏｂ，３）＊４＋（ＣＫＡｌｉｃｅ，４＋ＣＫＢｏｂ，４）＊（−１）
＝｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊１＋ｆＡｌｉｃｅ，２＊１２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊１＋ｆＢｏｂ，２＊１２）｝＊４
＋｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊２＋ｆＡｌｉｃｅ，２＊２２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊２＋ｆＢｏｂ，２＊２２）｝＊（−６）
＋｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊３＋ｆＡｌｉｃｅ，２＊３２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊３＋ｆＢｏｂ，２＊３２）｝＊４
＋｛（ＲＡｌｉｃｅ＋ｆＡｌｉｃｅ，１＊４＋ｆＡｌｉｃｅ，２＊４２）
＋（ＲＢｏｂ＋ｆＢｏｂ，１＊４＋ｆＢｏｂ，２＊４２）｝＊（−１）
＝（ＲＡｌｉｃｅ＋ＲＢｏｂ）＊（４−６＋４−１）
＋（ｆＡｌｉｃｅ，１＋ｆＢｏｂ，１）＊（４−１２＋１２−４）
＋（ｆＡｌｉｃｅ，２＋ｆＢｏｂ，２）＊（４−２４＋３６−１６）
＝（ＲＡｌｉｃｅ＋ＲＢｏｂ）
＝ＣＫ
【００４９】
安全性について説明する。ＴＣ型方式の対話文は、非対称共通鍵ＣＫの分散値と、それを指数とするベキ乗剰余値から成る。非対称共通鍵ＣＫの分散値は、（閾値ｎ＋１、分散値数２ｎ）のＳｈａｍｉｒ  ｓｅｃｒｅｔ  ｓｈａｒｉｎｇ  ｓｃｈｅｍｅ［Ｓ７９］になっており、公開される分散値の数がｎ個であるため、情報量的にＣｈａｒｌｅｙが非対称共通鍵ＣＫを復元することはできない。また、ベキ乗剰余値の指数を求めることは、離散対数問題に帰着するため、ＩＫｉから分散値を求めること、およびＦｉから分散値の生成に用いる係数を求めることは、計算量的に困難である。
【００５０】
上記のように、本発明の第１の実施の形態では、対話鍵共有システムを、複数のユーザ端末の間で、秘密分散法を利用した鍵共有プロトコルにより非対称共通鍵を秘密に共有し、センタは、傍受した端末間の通信から、秘密に共有された非対称共通鍵に対応するグループ公開鍵（対話鍵）を計算する、Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍ（ＴＣ）型としたので、閾値暗号ベースで、対話鍵共有システムを実現できる。
【００５１】
（第２の実施の形態）
本発明の第２の実施の形態は、２つのユーザ端末の間で、ＤＨ法を利用した鍵共有プロトコルにより非対称共通鍵を秘密に共有し、センタは、傍受した端末間の通信から、秘密に共有された非対称共通鍵に対応するグループ公開鍵（対話鍵）を計算する、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＨ）型の対話鍵共有システムである。
【００５２】
図４は、本発明の第２の実施の形態における対話鍵共有システムの動作手順を示す流れ図である。第２の実施の形態における対話鍵共有システムの基本的な構成は、図２に示した第１の実施の形態と同様である。
【００５３】
本発明の第２の実施の形態における対話鍵共有システムの動作原理と動作手順を説明する。最初に、鍵共有法および対話鍵生成法の概略を説明する。ＤＨ型の対話鍵共有方式は、公開鍵暗号を用いた簡素なＡｌｉｃｅとＢｏｂ間の鍵共有法およびＣｈａｒｌｅｙの対話鍵生成法と、ＤＨ問題を利用した対話文ＩＭと対話鍵ＩＫの検証法から成る。
【００５４】
Ａｌｉｃｅの秘密の乱数をＲＡｌｉｃｅ（∈Ｚｑ）として、対話鍵元データＩＫＡｌｉｃｅ（＝ｇ＾（ＲＡｌｉｃｅ）  ｍｏｄｐ）を公開すると共に、乱数ＲＡｌｉｃｅをＢｏｂの公開鍵ＹＢｏｂで暗号化してＢｏｂに送信する。ＢｏｂもＡｌｉｃｅと同様に、対話鍵元データＩＫＢｏｂを公開し、乱数ＲＢｏｂをＡｌｉｃｅの公開鍵で暗号化して送信する。
【００５５】
ＡｌｉｃｅとＢｏｂは、非対称共通鍵ＣＫ（＝ＲＡｌｉｃｅ＋ＲＢｏｂ  ｍｏｄｑ）を計算する。Ｃｈａｒｌｅｙは、対話鍵
ＩＫ＝ＩＫＡｌｉｃｅ＊ＩＫＢｏｂ  ｍｏｄｐ
＝ｇ＾（ＲＡｌｉｃｅ＋ＲＢｏｂ）  ｍｏｄｐ
を計算することで、非対称共通鍵ＣＫに対応する対話鍵ＩＫを得る。
【００５６】
対話文ＩＭと対話鍵元データＩＫＡｌｉｃｅの検証法を説明する。対話文ＩＭと対話鍵元データＩＫＡｌｉｃｅ，ＩＫＢｏｂの検証法の目的は、対話鍵元データＩＫＡｌｉｃｅ，ＩＫＢｏｂに対応する乱数ＲＡｌｉｃｅ，ＲＢｏｂを、それぞれＡｌｉｃｅとＢｏｂが保持することを、乱数ＲＡｌｉｃｅ，ＲＢｏｂを知ることなく検証することである。Ｂｏｂは、チャレンジとして、乱数ＤＢｏｂ（∈Ｚｑ）を指数とするベキ乗剰余値ＣＨＡＢｏｂ，Ａｌｉｃｅ（＝ｇ＾（ＤＢｏｂ）  ｍｏｄｐ）をＡｌｉｃｅに送信する。Ａｌｉｃｅは、レスポンスとして、チャレンジＣＨＡＢｏｂ，Ａｌｉｃｅに乱数ＲＡｌｉｃｅをベキ乗した剰余ＲＥＳＡｌｉｃｅ，ｂｏｂ（＝（ｇ＾（ＤＢｏｂ））＾（ＲＡｌｉｃｅ）  ｍｏｄｐ）をＢｏｂに送信する。Ｂｏｂは、レスポンスＲＥＳＡｌｉｃｅ，Ｂｏｂを受信後に、乱数ＤＢｏｂを公開する。
【００５７】
Ｃｈａｒｌｅｙは、ＲＥＳＡｌｉｃｅ，Ｂｏｂ，ＤＢｏｂの順に公開された場合のみ、
ＲＥＳＡｌｉｃｅ，Ｂｏｂ≡ＩＫＡｌｉｃｅ＾（ＤＢｏｂ）  （ｍｏｄｐ）
を検証する。成功なら、Ａｌｉｃｅが対話鍵元データＩＫＡｌｉｃｅに対応する乱数ＲＡｌｉｃｅを持つと承認する。乱数ＤＢｏｂの公開前に、乱数ＲＡｌｉｃｅを知らずに、対話鍵元データＩＫＡｌｉｃｅ（＝ｇ＾（ＲＡｌｉｃｅ）  ｍｏｄｐ）とチャレンジＣＨＡＢｏｂ，Ａｌｉｃｅ（＝ｇ＾（ＤＢｏｂ）  ｍｏｄｐ）からレスポンスＲＥＳＡｌｉｃｅ，ｂｏｂ（＝（ｇ＾（ＤＢｏｂ））＾（ＲＡｌｉｃｅ）  ｍｏｄｐ）を計算することは、ＤＨ問題に帰着できる。したがって、Ｃｈａｒｌｅｙは乱数ＲＡｌｉｃｅを知ることなく、Ａｌｉｃｅが乱数ＲＡｌｉｃｅを保持していることを検証できる。
【００５８】
次に、図４を参照しながら、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＨ）型対話鍵共有システムの動作手順を、対話鍵生成法と対話文と対話鍵検証法を組み合わせた形で、詳しく説明する。なお、式（２）と（３）の検証と対話鍵の生成は、各ユーザも可能であるが、この例では、Ｃｈａｒｌｅｙが一括して行う。
【００５９】
Ａｌｉｃｅは、Ｓｔｅｐ１で、
ａ）乱数ＲＡｌｉｃｅ，ＤＡｌｉｃｅ（∈Ｚｑ）を生成する。
ｂ）対話鍵の元データ
ＩＫＡｌｉｃｅ＝ｇ＾（ＲＡｌｉｃｅ）  ｍｏｄｐ
を計算する。
ｃ）チャレンジ
ＣＨＡＡｌｉｃｅ，Ｂｏｂ＝ｇ＾（ＤＡｌｉｃｅ）  ｍｏｄｐ
を計算する。
ｄ）署名ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＩＫＡｌｉｃｅ‖ＣＨＡＡｌｉｃｅ，Ｂｏｂ）を計算し、ＩＫＡｌｉｃｅ，ＣＨＡＡｌｉｃｅ，Ｂｏｂと共にＢｏｂに送信する。
【００６０】
Ｂｏｂは、Ｓｔｅｐ２で、
ａ）Ａｌｉｃｅの公開鍵ＹＡｌｉｃｅで、署名ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＩＫＡｌｉｃｅ‖ＣＨＡＡｌｉｃｅ，  Ｂｏｂ）を検証し、失敗なら終了し、成功なら、乱数ＲＢｏｂ，ＤＢｏｂ（∈Ｚｑ）を生成する。
ｂ）対話鍵の元データ
ＩＫＢｏｂ＝ｇ＾（ＲＢｏｂ）  ｍｏｄｐ
を計算する。
ｃ）チャレンジ
ＣＨＡＢｏｂ，Ａｌｉｃｅ＝ｇ＾（ＤＢｏｂ）  ｍｏｄｐ
を計算する。
ｄ）レスポンス
ＲＥＳＢｏｂ，Ａｌｉｃｅ＝ＣＨＡＡｌｉｃｅ，Ｂｏｂ＾（ＲＢｏｂ）  ｍｏｄｐ
を計算する。
ｅ）署名ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＩＫＢｏｂ‖ＣＨＡＢｏｂ，Ａｌｉｃｅ‖ＲＥＳＢｏｂ，Ａｌｉｃｅ）を計算し、ＩＫＢｏｂ，ＣＨＡＢｏｂ，Ａｌｉｃｅ，ＲＥＳＢｏｂ，Ａｌｉｃｅと共にＡｌｉｃｅに送信する。
【００６１】
Ａｌｉｃｅは、Ｓｔｅｐ３で、
ａ）Ｂｏｂの公開鍵ＹＢｏｂを使って、署名ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＲＥＳＢｏｂ，Ａｌｉｃｅ‖ＣＨＡＢｏｂ，Ａｌｉｃｅ‖ＩＫＢｏｂ）を検証し、失敗なら終了し、成功なら、レスポンス
ＲＥＳＡｌｉｃｅ，Ｂｏｂ＝ＣＨＡＢｏｂ，Ａｌｉｃｅ＾（ＲＡｌｉｃｅ）  ｍｏｄｐ
を計算する。
ｂ）暗号文
ＥＮＣＡｌｉｃｅ，Ｂｏｂ＝Ｐ＿ＥＮＣ（ＹＢｏｂ，Ａｌｉｃｅ‖ＲＡｌｉｃｅ）
を計算する。
ｃ）署名ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＥＮＣＡｌｉｃｅ，Ｂｏｂ‖ＤＡｌｉｃｅ‖ＲＥＳＡｌｉｃｅ，Ｂｏｂ）を計算し、ＥＮＣＡｌｉｃｅ，Ｂｏｂ，ＤＡｌｉｃｅ，ＲＥＳＡｌｉｃｅ，Ｂｏｂと共にＢｏｂに送信する。
【００６２】
Ｂｏｂは、Ｓｔｅｐ４で、
ａ）Ａｌｉｃｅの公開鍵ＹＡｌｉｃｅを使って、署名ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＥＮＣＡｌｉｃｅ，Ｂｏｂ‖ＤＡｌｉｃｅ‖ＲＥＳＡｌｉｃｅ，Ｂｏｂ）を検証し、成功なら、ＸＢｏｂでＥＮＣＡｌｉｃｅ，Ｂｏｂを復号し、ＲＡｌｉｃｅを得る。
ｂ）暗号文
ＥＮＣＢｏｂ，Ａｌｉｃｅ＝Ｃ＿ＥＮＣ（Ｈ（ＲＡｌｉｃｅ），ＲＢｏｂ）
を計算する。
ｃ）署名ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＥＮＣＢｏｂ，Ａｌｉｃｅ‖ＤＢｏｂ）を計算し、ＥＮＣＢｏｂ，Ａｌｉｃｅ，ＤＢｏｂと共にＡｌｉｃｅに送信する。
ｄ）非対称共通鍵
ＣＫ＝ＲＢｏｂ＋ＲＡｌｉｃｅ  ｍｏｄｑ
を計算する。
【００６３】
Ａｌｉｃｅは、Ｓｔｅｐ５で、
ａ）ＹＢｏｂを使って、ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＥＮＣＢｏｂ，Ａｌｉｃｅ‖ＤＢｏｂ）を検証し、成功なら、Ｈ（ＲＡｌｉｃｅ）でＥＮＣＢｏｂ，Ａｌｉｃｅを復号し、ＲＢｏｂを得る。
ｂ）非対称共通鍵
ＣＫ＝ＲＡｌｉｃｅ＋ＲＢｏｂ  ｍｏｄｑ
を計算する。
【００６４】
Ｃｈａｒｌｅｙは、Ｓｔｅｐ５で、
ａ）ＹＡｌｉｃｅを使って、
ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＩＫＡｌｉｃｅ‖ＣＨＡＡｌｉｃｅ，Ｂｏｂ）と
ＳＩＧ（ＸＡｌｉｃｅ，Ａｌｉｃｅ‖ＥＮＣＡｌｉｃｅ，Ｂｏｂ‖ＤＡｌｉｃｅ‖ＲＥＳＡｌｉｃｅ，Ｂｏｂ）を検証し、
ＹＢｏｂを使って、
ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＩＫＢｏｂ‖ＣＨＡＢｏｂ，Ａｌｉｃｅ‖ＲＥＳＢｏｂ，Ａｌｉｃｅ）と
ＳＩＧ（ＸＢｏｂ，Ｂｏｂ‖ＥＮＣＢｏｂ，Ａｌｉｃｅ‖ＤＢｏｂ）を検証し、
検証成功ならｂ）を実行し、検証失敗ならＥｒｒｏｒをＡｌｉｃｅとＢｏｂに送信する。
ｂ）式
ＲＥＳＡｌｉｃｅ，Ｂｏｂ≡ＩＫＡｌｉｃｅ＾（ＤＢｏｂ）  （ｍｏｄｐ）  ・・・・・  （２）
ＲＥＳＢｏｂ，Ａｌｉｃｅ≡ＩＫＢｏｂ＾（ＤＡｌｉｃｅ）  （ｍｏｄｐ）  ・・・・・  （３）
を検証し、成立ならｃ）を実行し、非成立ならＥｒｒｏｒをＡｌｉｃｅとＢｏｂに送信する。すなわち、成立なら、
ＲＥＳＡｌｉｃｅ，Ｂｏｂ＝ＣＨＡＢｏｂ，Ａｌｉｃｅ＾（ＲＡｌｉｃｅ）  ｍｏｄｐ
＝（ｇ＾（ＤＢｏｂ））＾（ＲＡｌｉｃｅ）  ｍｏｄｐ
＝ｇ＾（ＤＢｏｂ＊ＲＡｌｉｃｅ）  ｍｏｄｐ
ＩＫＡｌｉｃｅ＾（ＤＢｏｂ）  ｍｏｄｐ
＝（ｇ＾（ＲＡｌｉｃｅ））＾（ＤＢｏｂ）  ｍｏｄｐ
＝ｇ＾（ＤＢｏｂ＊ＲＡｌｉｃｅ）  ｍｏｄｐ
となり、同様に、
ＲＥＳＢｏｂ，Ａｌｉｃｅ＝ＣＨＡＡｌｉｃｅ，Ｂｏｂ＾（ＲＢｏｂ）  ｍｏｄｐ
＝（ｇ＾（ＤＡｌｉｃｅ））＾（ＲＢｏｂ）  ｍｏｄｐ
＝ｇ＾（ＤＡｌｉｃｅ＊ＲＢｏｂ）  ｍｏｄｐ
ＩＫＢｏｂ＾（ＤＡｌｉｃｅ）  ｍｏｄｐ
＝（ｇ＾（ＲＢｏｂ））＾（ＤＡｌｉｃｅ）  ｍｏｄｐ
＝ｇ＾（ＤＡｌｉｃｅ＊ＲＢｏｂ）  ｍｏｄｐ
となる。
ｃ）対話鍵を計算する。
ＩＫ＝ＩＫＡｌｉｃｅ＊ＩＫＢｏｂ  ｍｏｄｐ
＝ｇ＾（ＲＡｌｉｃｅ）＊ｇ＾（ＲＢｏｂ）  ｍｏｄｐ
＝ｇ＾（ＲＡｌｉｃｅ＋ＲＢｏｂ）  ｍｏｄｐ
【００６５】
安全性について説明する。使用する暗号方式が安全であり、かつ離散対数問題が計算量的に困難であれば、公開される暗号文ＥＮＣｉおよびベキ乗剰余値ＩＫｉからＣｈａｒｌｅｙがＲｉを入手することは明らかに困難である。
【００６６】
上記のように、本発明の第２の実施の形態では、対話鍵共有システムを、２つのユーザ端末の間で、ＤＨ法を利用した鍵共有プロトコルにより秘密に非対称共通鍵を共有し、センタは、傍受した端末間の通信から、秘密に共有された非対称共通鍵に対応するグループ公開鍵（対話鍵）を計算する、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＨ）型としたので、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有法をベースにして、対話鍵共有システムを実現できる。
【００６７】
（第３の実施の形態）
本発明の第３の実施の形態は、２つのユーザ端末の間で、ＲＳＡ法を利用した鍵共有プロトコルにより秘密に非対称共通鍵を共有し、センタは、傍受した端末間の通信から、秘密に共有された非対称共通鍵に対応するグループ公開鍵（対話鍵）を計算する、ＲＳＡ型の対話鍵共有システムである。
【００６８】
本発明の第３の実施の形態における対話鍵共有システムの動作原理と動作手順を説明する。第３の実施の形態における対話鍵共有システムの基本的な構成は、図２に示した第１の実施の形態と同様である。ＲＳＡ暗号の原理を基本とする点が異なる。
【００６９】
Ｕを、１０２４ｂｉｔ程度の素数とする。ｅを、ＲＳＡの公開鍵であり、１６ビット程度の数とする。例えば、ｅ＝（２１６＋１）（フェルマーの素数）とする。Ｕとｅは、全エンティティ（ユーザＡとユーザＢとセンタ）が共有している。説明を分かりやすくするために、ユーザＡをＡｌｉｃｅとし、ユーザＢをＢｏｂとし、センタをＣｈａｒｌｅｙとする。
【００７０】
Ａｌｉｃｅは、Ｓｔｅｐ１で、
ａ）１０２４ｂｉｔ程度の乱数ＲＡｌｉｃｅ（１≦ＲＡｌｉｃｅ＜Ｕ）を生成する。
ｂ）暗号文
ＥＮＣＡｌｉｃｅ，Ｂｏｂ＝Ｐ＿ＥＮＣ（ＹＢｏｂ，ＲＡｌｉｃｅ）
を計算し、Ｂｏｂに送信する。
【００７１】
Ｂｏｂは、Ｓｔｅｐ２で、
ａ）非対称秘密鍵ＸＢｏｂを使って、暗号文ＥＮＣＡｌｉｃｅ，Ｂｏｂを復号する。
ｂ）１０２４ｂｉｔ程度の乱数ＲＢｏｂ（１≦ＲＢｏｂ＜Ｕ）を生成する。ＲＡｌｉｃｅ＊ＲＢｏｂ＞Ｕとなるようにする。
ｃ）５１２ｂｉｔ程度の素数ＱＢｏｂを生成する。ｅが素数でない場合は、（ＱＢｏｂ−１）がｅと互いに素になるようにする。さらに、ＱＢｏｂ＊ＲＢｏｂ＞Ｕとなるようにする。
ｄ）対話鍵の元データ
ＩＫＢｏｂ＝ＱＢｏｂ＊ＲＢｏｂ  ｍｏｄＵ
を計算する。
ｅ）乱数の積
ＲＡｌｉｃｅ，Ｂｏｂ＝ＲＡｌｉｃｅ＊ＲＢｏｂ  ｍｏｄＵ
を計算し、ＩＫＢｏｂと共にＡｌｉｃｅに送信する。
【００７２】
Ａｌｉｃｅは、Ｓｔｅｐ３で、
ａ）５１２ｂｉｔ程度の素数ＰＡｌｉｃｅを生成する。ｅが素数でない場合は、（ＰＡｌｉｃｅ−１）がｅと互いに素になるようにする。ＲＡｌｉｃｅ＊ＰＡｌｉｃｅ＞Ｕとなるようにする。
ｂ）対話鍵の元データ
ＩＫＡｌｉｃｅ＝ＲＡｌｉｃｅ＊ＰＡｌｉｃｅ  ｍｏｄＵ
を計算し、Ｂｏｂに送信する。
ｃ）ＱＢｏｂ＝（ＲＡｌｉｃｅ＊ＩＫＢｏｂ）／ＲＡｌｉｃｅ，Ｂｏｂ  ｍｏｄＵを計算する。
ｄ）次式を満たす非対称秘密鍵ｄを計算する。
ｄ＊ｅ≡１  （ｍｏｄ  ＬＣＭ（ＰＡｌｉｃｅ−１，ＱＢｏｂ−１））
【００７３】
Ｂｏｂは、Ｓｔｅｐ４で、
ａ）ＰＡｌｉｃｅ＝ＩＫＡｌｉｃｅ／ＲＡｌｉｃｅ  ｍｏｄＵを計算する。
ｂ）次式を満たす非対称秘密鍵ｄを計算する。
ｄ＊ｅ≡１  （ｍｏｄ  ＬＣＭ（ＰＡｌｉｃｅ−１，ＱＢｏｂ−１））
これで非対称秘密鍵ｄが共有された。
【００７４】
Ｃｈａｒｌｅｙは、Ｓｔｅｐ４で、
ａ）対話鍵の法
ＩＫ＝（ＩＫＡｌｉｃｅ＊ＩＫＢｏｂ）／ＲＡｌｉｃｅＢｏｂ  ｍｏｄＵ
＝（ＲＡｌｉｃｅ＊ＰＡｌｉｃｅ＊ＱＢｏｂ＊ＲＢｏｂ）／（ＲＡｌｉｃｅ＊ＲＢｏｂ）  ｍｏｄＵ
＝（ＰＡｌｉｃｅ＊ＱＢｏｂ）  ｍｏｄＵ
を計算する。
【００７５】
非対称秘密鍵ｄに対応する公開鍵（対話鍵）は、ベキ指数ｅであり、法はＩＫである。ベキ指数ｅを１６ビット程度の素数とすれば、秘密の素数ＰＡｌｉｃｅ，ＱＢｏｂが何であっても、ＬＣＭ（ＰＡｌｉｃｅ−１，ＱＢｏｂ−１）より小さく、かつそれと互いに素になるので、ＲＳＡ公開鍵の条件を満たす。ベキ指数ｅが素数でない場合は、秘密の素数ＰＡｌｉｃｅ，ＱＢｏｂを、（ＰＡｌｉｃｅ−１），（ＱＢｏｂ−１）がベキ指数ｅと互いに素になるように決めればよい。
【００７６】
上記のように、本発明の第３の実施の形態では、対話鍵共有システムを、２つのユーザ端末の間で、ＲＳＡ法を利用した鍵共有プロトコルにより秘密に非対称共通鍵を共有し、センタは、傍受した端末間の通信から、秘密に共有された非対称共通鍵に対応するグループ公開鍵（対話鍵）を計算するＲＳＡ型としたので、ＲＳＡ暗号をベースにして対話鍵共有システムを実現できる。
【００７７】
（第４の実施の形態）
本発明の第４の実施の形態は、複数のユーザ端末の間で、鍵共有プロトコルにより秘密に非対称共通鍵を共有し、センタは、傍受した端末間の通信から、秘密に共有された非対称共通鍵に対応するグループ公開鍵（対話鍵）を計算し、非対称共通鍵による署名を対話鍵で検証する通話内容証明システムである。
【００７８】
図５は、本発明の第４の実施の形態における通話内容証明システムの構成図である。図５において、検証者１０は、ユーザに、通話内容の検証を求める者である。対話文保存手段１１は、ユーザ間の対話文を保存する手段である。署名検証手段１２は、対話鍵でユーザの署名を検証する手段である。その他の基本的な構成は、図２に示した第１の実施の形態と同様である。
【００７９】
上記のように構成された本発明の第４の実施の形態における通話内容証明システムの動作手順を説明する。最初に、対話鍵のアプリケーションについて説明する。対話鍵が有効なアプリケーションとして、通話内容（契約等）証明を考える。通話内容証明とは、ここでは複数ユーザ間の通話内容に対して署名を付加することにより、第三者による通話内容の確認を可能とするアプリケーションのことである。
【００８０】
一般に、従来の通話内容証明では、Ｔｒｕｓｔｅｄ  Ａｕｔｈｏｒｉｔｙまたは各通話者の署名を付加する。したがって、通話内容に複数の署名が付加される可能性があり、最初の署名者は、後から誰が署名するか分からない。そのため、この通話内容証明は、契約等に必ずしも適しているとは言えない。これを解決するために、通話者全員が共有した非対称秘密鍵により署名を付加することが、一応考えられる。しかし、従来のＳｉｍｐｌｅ  Ｍｅｔｈｏｄで署名検証者が得られる公開鍵は、対話鍵と異なり、いつ誰が共有した鍵か分からないため、この様な用途には使えない。
【００８１】
本発明では、対話鍵を使い、さらに、「Ｃｈａｒｌｅｙは対話文と通話内容を安全に記録し、かつ要求に応じて公開する」という条件を追加する。｛Ａｌｉｃｅ  ａｎｄ  Ｂｏｂ，Ｃｈａｒｌｅｙ｝の組は、｛携帯電話，通信キャリアのＧＷ｝、｛ＰＣ，ＩＳＰのＳｅｒｖｅｒ  ｏｒ  Ｐｒｏｘｙ｝を想定する。対話鍵によるＡｌｉｃｅ−Ｂｏｂ間の通話内容証明例を示す。
【００８２】
図５（ａ）を参照しながら、例１の通話内容の登録手順を説明する。
１．ＡｌｉｃｅとＢｏｂは、Ｃｈａｒｌｅｙに観察を依頼する。
２．ＡｌｉｃｅとＢｏｂは、対話文ＩＭＡｌｉｃｅとＩＭＢｏｂを交換し、非対称共通鍵ＣＫを共有する。
３．Ａｌｉｃｅは、以下のように生成した暗号文ＣＴＡｌｉｃｅ、署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ、指紋ＦＰＡｌｉｃｅをＢｏｂに送信する。
３−１．通話文ＰＴＡｌｉｃｅから指紋ＦＰＡｌｉｃｅ（＝Ｈ（ＰＴＡｌｉｃｅ））を生成する。
３−２．通話文ＰＴＡｌｉｃｅを、非対称共通鍵ＣＫか対話鍵ＩＫで暗号化して、暗号文ＣＴＡｌｉｃｅを生成する。
３−３．非対称秘密鍵ＸＡｌｉｃｅと非対称共通鍵ＣＫを用いて、それぞれＦＰＡｌｉｃｅ‖Ｈ（ＣＴＡｌｉｃｅ）に対する署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩを生成する。
４．Ｂｏｂは、Ａｌｉｃｅと同様に生成した暗号文ＣＴＢｏｂ、署名ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩ、指紋ＦＰＢｏｂを、Ａｌｉｃｅに送信する。
５．受信者（Ａｌｉｃｅ）は、暗号文ＣＴＢｏｂから通話文ＰＴＢｏｂを得て、Ｈ（ＰＴＢｏｂ）＝ＦＰを確認してから、署名ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩを検証する。受信者（Ｂｏｂ）は、暗号文ＣＴＡｌｉｃｅから通話文ＰＴＡｌｉｃｅを得て、Ｈ（ＰＴＡｌｉｃｅ）＝ＦＰＡｌｉｃｅを確認してから、署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩを検証する。
６．Ｃｈａｒｌｅｙは、ＩＭＡｌｉｃｅ，ＩＭＢｏｂ，ＣＴＡｌｉｃｅ，ＣＴＢｏｂ，ＦＰＡｌｉｃｅ，ＦＰＢｏｂ，ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＡｌｉｃｅＩＩを保存する。
【００８３】
図５（ａ）を参照しながら、例１の通話内容検証の手順を説明する。
１．検証者は、Ａｌｉｃｅ又はＢｏｂに通話内容証明を要求する。
２．Ａｌｉｃｅ又はＢｏｂは、Ｃｈａｒｌｅｙに通話内容証明を依頼する。
３．Ａｌｉｃｅ又はＢｏｂは、通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂを公開する。
４．Ｃｈａｒｌｅｙは、ＩＭＡｌｉｃｅ，ＩＭＢｏｂ，ＣＴＡｌｉｃｅ，ＣＴＢｏｂ，ＦＰＡｌｉｃｅ，ＦＰＢｏｂ，ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＡｌｉｃｅＩＩを公開する。
５．検証者は、対話文ＩＭＡｌｉｃｅ，ＩＭＢｏｂから対話鍵ＩＫを生成し、通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂから指紋ＦＰＡｌｉｃｅ，ＦＰＢｏｂを生成する。
６．検証者は、ＦＰＡｌｉｃｅ，ＦＰＢｏｂ，ＣＴＡｌｉｃｅ，ＣＴＢｏｂ，ＩＫ，ＹＡｌｉｃｅ，ＹＢｏｂを用いて、署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩを検証し、検証成功ならば、通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂを受理する。
【００８４】
図５（ｂ）を参照しながら、例２の通話内容の登録手順を説明する。例１とは、暗号文ＣＴと、Ｈ（ＰＴ）に対する署名を送信する点が異なる。
１．ＡｌｉｃｅとＢｏｂは、Ｃｈａｒｌｅｙに観察を依頼する。
２．ＡｌｉｃｅとＢｏｂは、対話文ＩＭＡｌｉｃｅとＩＭＢｏｂを交換し、非対称共通鍵ＣＫを共有する。
３．Ａｌｉｃｅは、以下のように生成した暗号文ＣＴＡｌｉｃｅと署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩを、Ｂｏｂに送信する。
３−１．通話文ＰＴＡｌｉｃｅから、Ｈ（ＰＴＡｌｉｃｅ）を生成する。
３−２．通話文ＰＴＡｌｉｃｅを対話鍵ＩＫで暗号化して暗号文ＣＴＡｌｉｃｅを生成する。
３−３．秘密鍵ＸＡｌｉｃｅと非対称共通鍵ＣＫを用いて、それぞれＨ（ＰＴＡｌｉｃｅ）に対する署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩを生成する。
４．Ｂｏｂは、Ａｌｉｃｅと同様に生成した暗号文ＣＴＢｏｂと署名ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩを、Ａｌｉｃｅに送信する。
６．Ｃｈａｒｌｅｙは、ＩＭＡｌｉｃｅ，ＩＭＢｏｂ，ＣＴＡｌｉｃｅ，ＣＴＢｏｂ，ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩを保存する。
【００８５】
図５（ｂ）を参照しながら、例２の通話内容検証の手順を説明する。例１とは、Ｃｈａｒｌｅｙが、公開された通話文ＰＴから暗号文ＣＴを計算し、暗号文ＣＴからＨ（ＣＴ）を計算して、署名を検証する点が異なる。
１．検証者は、Ａｌｉｃｅ又はＢｏｂに通話内容証明を要求する。
２．Ａｌｉｃｅ又はＢｏｂは、Ｃｈａｒｌｅｙに通話内容証明を依頼する。
３．Ａｌｉｃｅ又はＢｏｂは、通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂを公開する。
４．Ｃｈａｒｌｅｙは、ＩＭＡｌｉｃｅ，ＩＭＢｏｂ，ＣＴＡｌｉｃｅ，ＣＴＢｏｂ，ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩを公開する。
５．Ｃｈａｒｌｅｙは、通話文ＩＭＡｌｉｃｅ，ＩＭＢｏｂから対話鍵ＩＫを生成する。
６．Ｃｈａｒｌｅｙは、公開された通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂから暗号文ＣＴＡｌｉｃｅ，ＣＴＢｏｂを計算し、暗号文ＣＴＡｌｉｃｅ，ＣＴＢｏｂからＨ（ＣＴＡｌｉｃｅ），Ｈ（ＣＴＢｏｂ）を計算して、対話鍵ＩＫと公開鍵ＹＡｌｉｃｅ，ＹＢｏｂを用いて、署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩを検証する。
７．検証成功ならば、検証者は、通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂを受理する。
【００８６】
図５（ｂ）を参照しながら、例３の通話内容の登録手順を説明する。例１とは、通話文ＰＴとＨ（ＰＴ）に対する署名を送信する点が異なる。
１．ＡｌｉｃｅとＢｏｂは、Ｃｈａｒｌｅｙに観察を依頼する。
２．ＡｌｉｃｅとＢｏｂは、対話文ＩＭＡｌｉｃｅとＩＭＢｏｂを交換し、非対称共通鍵ＣＫを共有する。
３．Ａｌｉｃｅは、以下のように生成した暗号文ＣＴＡｌｉｃｅと署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩを、Ｂｏｂに送信する。
３−２．通話文ＰＴＡｌｉｃｅを非対称共通鍵ＣＫか対話鍵ＩＫで暗号化して暗号文ＣＴＡｌｉｃｅを生成する。
３−３．非対称秘密鍵ＸＡｌｉｃｅと非対称共通鍵ＣＫを用いて、それぞれＨ（ＰＴＡｌｉｃｅ）に対する署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩを生成する。
４．Ｂｏｂは、Ａｌｉｃｅと同様に生成した暗号文ＣＴＢｏｂと署名ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩを、Ａｌｉｃｅに送信する。
５．受信者（ＡｌｉｃｅまたはＢｏｂ）は、暗号文ＣＴから通話文ＰＴを得て、Ｈ（ＰＴ）を生成してから、署名を検証する。
６．Ｃｈａｒｌｅｙは、ＩＭＡｌｉｃｅ，ＩＭＢｏｂ，ＣＴＡｌｉｃｅ，ＣＴＢｏｂ，ＦＰＡｌｉｃｅ，ＦＰＢｏｂ，ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＡｌｉｃｅＩＩを保存する。
【００８７】
図５（ｂ）を参照しながら、例３の通話内容検証の手順を説明する。例１とは、Ｃｈａｒｌｅｙが、通話文ＰＴからＨ（ＰＴ）を計算して署名を検証する点が異なる。
１．検証者は、Ａｌｉｃｅ又はＢｏｂに通話内容証明を要求する。
２．Ａｌｉｃｅ又はＢｏｂは、Ｃｈａｒｌｅｙに通話内容証明を依頼する。
３．Ａｌｉｃｅ又はＢｏｂは、通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂを公開する。
４．Ｃｈａｒｌｅｙは、ＩＭＡｌｉｃｅ，ＩＭＢｏｂ，ＣＴＡｌｉｃｅ，ＣＴＢｏｂ，ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＡｌｉｃｅＩＩを公開する。
５．Ｃｈａｒｌｅｙは、対話文ＩＭＡｌｉｃｅ，ＩＭＢｏｂから対話鍵ＩＫを生成する。
６．Ｃｈａｒｌｅｙは、通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂからＨ（ＰＴＡｌｉｃｅ），Ｈ（ＰＴＢｏｂ）を計算し、対話鍵ＩＫと公開鍵ＹＡｌｉｃｅ，ＹＢｏｂを用いて、署名ＳＭＡｌｉｃｅＩ，ＳＭＡｌｉｃｅＩＩ，ＳＭＢｏｂＩ，ＳＭＢｏｂＩＩを検証する。
７．検証成功ならば、検証者は、通話文ＰＴＡｌｉｃｅ，ＰＴＢｏｂを受理する。
【００８８】
例４は、受信者の署名を付加する方法である。例１から例３において、ＡｌｉｃｅまたはＢｏｂの送信した情報（例えばＦＰ，ＣＴ，ＰＴ）に対して、自身の非対称秘密鍵Ｘを用いた署名を作成して送信者に送り返す。
【００８９】
センタ（オブザーバＣｈａｒｌｅｙ）がＣｅｒｔｉｆｉｃａｔｅ  Ａｕｔｈｏｒｉｔｙの場合は、対話鍵に対する公開鍵証明書を発行するアプリケーションにも利用できる。センタ（オブザーバＣｈａｒｌｅｙ）が証明者としてだけではなく、検証者であってもよいので、センタと検証者を一体としてもよい。
【００９０】
上記のように、本発明の第４の実施の形態では、通話内容証明システムを、複数のユーザ端末の間で、鍵共有プロトコルにより秘密に非対称共通鍵を共有し、センタは、傍受した端末間の通信から、秘密に共有された非対称共通鍵に対応するグループ公開鍵（対話鍵）を計算し、非対称共通鍵による署名を対話鍵で検証する構成としたので、いつ誰が署名した通話内容であるか証明することができる。
【００９１】
（第５の実施の形態）
本発明の第５の実施の形態は、リング型通信路で結ばれた３人以上のユーザでＤＨ型対話鍵生成法を用いる通話内容証明システムである。
【００９２】
図６は、本発明の第５の実施の形態における対話鍵共有システムの動作手順を示す流れ図である。ユーザ数が５の場合の例を示してある。第５の実施の形態における対話鍵共有システムの基本的な構成は、図２に示した第１の実施の形態と同様であるが、３人以上のユーザがリング型通信路で結ばれている点が異なる。図６では、細部を省略してあるので、一部説明と異なる部分がある。
【００９３】
上記のように構成された本発明の第５の実施の形態における通話内容証明システムの動作手順を説明する。リング型通信路を想定するため、ｎ（ｎ≧３）人のユーザを次の三種類に分類する。
Ｓｔａｒｔｅｒ：通信を開始するユーザであり、ユーザＩＤを１とする。
Ｒｅｌａｙ：通信を中継するユーザであり、ユーザＩＤを２，…，ｎ−１とする。
Ｔｅｒｍｉｎａｔｏｒ：通信を終了するユーザであり、ユーザＩＤをｎとする。
【００９４】
λを全ユーザＩＤの集合とする。すなわち、
λ＝｛１，２，・・・，ｎ｝
εｉをユーザ２，…，ｉのＩＤの集合とする。すなわち、
εｉ＝｛２，・・・，ｉ｝
δｉをユーザ１，ｉ＋２，…，ｎのユーザＩＤの集合とする。すなわち、
δｉ＝λ−εｉ＋１＝｛１，ｉ＋２，・・・，ｎ｝
【００９５】
図６を参照しながら、ｎ＝５の例を説明する。
ＳｔｅｐＳ１でユーザ１は、乱数Ｒ１とＤ１（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ１＝ｇ＾（Ｒ１）  ｍｏｄｐ
と、チャレンジ
ＣＨＡ１＝ｇ＾（Ｄ１）  ｍｏｄｐ
を計算してユーザ２に送信する。
【００９６】
ＳｔｅｐＲ１１でユーザ２は、乱数Ｒ２（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ２＝ｇ＾（Ｒ２）  ｍｏｄｐ
を計算し、レスポンス
ＲＥＳ２＝ＣＨＡ１＾（Ｒ２）  ｍｏｄｐ
を計算して、ＩＫ２とＲＥＳ２とＣＨＡ１を、ユーザ３に送信する。
ＳｔｅｐＲ２１でユーザ３は、乱数Ｒ３（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ３＝ｇ＾（Ｒ３）  ｍｏｄｐ
を計算し、レスポンス
ＲＥＳ３＝ＣＨＡ１＾（Ｒ３）  ｍｏｄｐ
を計算して、ＩＫ３とＲＥＳ３とＣＨＡ１を、ユーザ４に送信する。
ＳｔｅｐＲ３１でユーザ４は、乱数Ｒ４（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ４＝ｇ＾（Ｒ４）  ｍｏｄｐ
を計算し、レスポンス
ＲＥＳ４＝ＣＨＡ１＾（Ｒ４）  ｍｏｄｐ
を計算して、ＩＫ４とＲＥＳ４とＣＨＡ１を、ユーザ５に送信する。
【００９７】
ＳｔｅｐＴ１でユーザ５は、乱数Ｒ５とＤ５（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ５＝ｇ＾（Ｒ５）  ｍｏｄｐ
を計算し、チャレンジ
ＣＨＡ５＝ｇ＾（Ｄ５）  ｍｏｄｐ
を計算し、レスポンス
ＲＥＳ５＝ＣＨＡ１＾（Ｒ５）  ｍｏｄｐ
を計算して、ＩＫ５とＣＨＡ５とＲＥＳ５を、ユーザ１に送信する。
【００９８】
ＳｔｅｐＳ２でユーザ１は、レスポンス
ＲＥＳ１＝ＣＨＡ５＾（Ｒ１）  ｍｏｄｐ
を計算して、ＲＥＳ１とＤ１を、ユーザ２に送信する。
【００９９】
ＳｔｅｐＲ１２でユーザ２は、暗号文
ＥＮＣ２，３＝Ｐ＿ＥＮＣ（Ｙ３，２‖Ｒ２）
を計算して、ユーザ３に送信する。
ＳｔｅｐＲ２２でユーザ３は、暗号文
ＥＮＣ２，３＝Ｐ＿ＥＮＣ（Ｙ３，２‖Ｒ２）
を、非対称秘密鍵Ｘ３を使って復号してＲ２を得るので、ユーザ３は（Ｒ２，Ｒ３）を保持することになる。暗号文
ＥＮＣ３，４＝Ｐ＿ＥＮＣ（Ｙ４，３‖Ｒ２＋Ｒ３  ｍｏｄｑ）
を計算して、ユーザ４に送信する。
ＳｔｅｐＲ３２でユーザ４は、暗号文
ＥＮＣ３，４＝Ｐ＿ＥＮＣ（Ｙ４，３‖Ｒ２＋Ｒ３  ｍｏｄｑ）
を、非対称秘密鍵Ｘ４を使って復号してＲ２＋Ｒ３を得るので、ユーザ４は（Ｒ２＋Ｒ３，Ｒ４）を保持することになる。暗号文
ＥＮＣ４，５＝Ｐ＿ＥＮＣ（Ｙ５，４‖Ｒ２＋Ｒ３＋Ｒ４  ｍｏｄｑ）
を計算して、ユーザ５に送信する。
【０１００】
ＳｔｅｐＴ２でユーザ５は、暗号文
ＥＮＣ４，５＝Ｐ＿ＥＮＣ（Ｙ５，４‖Ｒ２＋Ｒ３＋Ｒ４  ｍｏｄｑ）
を、非対称秘密鍵Ｘ５を使って復号してＲ２＋Ｒ３＋Ｒ４を得るので、ユーザ５は（Ｒ２＋Ｒ３＋Ｒ４，Ｒ５）を保持することになる。暗号文
ＥＮＣ５，１＝Ｐ＿ＥＮＣ（Ｙ１，５‖Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ）
を計算して、乱数Ｄ５とともに、ユーザ１に送信する。
【０１０１】
ＳｔｅｐＳ３でユーザ１は、暗号文
ＥＮＣ５，１＝Ｐ＿ＥＮＣ（Ｙ１，５‖Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ）
を、非対称秘密鍵Ｘ１を使って復号してＲ２＋Ｒ３＋Ｒ４＋Ｒ５を得るので、ユーザ１は（Ｒ１，Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５）を保持することになる。非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ
を計算する。暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Ｒ１＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ）
を計算して、ユーザ２に送信する。
【０１０２】
ＳｔｅｐＲ１３でユーザ２は、暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Ｒ１＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ）
を、非対称秘密鍵Ｘ２を使って復号してＲ１＋Ｒ３＋Ｒ４＋Ｒ５を得るので、ユーザ２は（Ｒ１＋Ｒ３＋Ｒ４＋Ｒ５，Ｒ２）を保持することになる。非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ
を計算する。暗号文
ＥＮＣ２，３＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２），Ｒ１＋Ｒ４＋Ｒ５  ｍｏｄｑ）
を計算してユーザ３に送信する。
ＳｔｅｐＲ２３でユーザ３は、暗号文
ＥＮＣ２，３＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２），Ｒ１＋Ｒ４＋Ｒ５  ｍｏｄｑ）
を、ハッシュ値Ｈ（Ｒｉ−１）を使って復号してＲ１＋Ｒ４＋Ｒ５を得るので、ユーザ３は（Ｒ１＋Ｒ４＋Ｒ５，Ｒ２，Ｒ３）を保持することになる。非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ
を計算する。暗号文
ＥＮＣ３，４＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２＋Ｒ３），Ｒ１＋Ｒ５  ｍｏｄｑ）
を計算してユーザ４に送信する。
ＳｔｅｐＲ３３でユーザ４は、暗号文
ＥＮＣ３，４＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２＋Ｒ３  ｍｏｄｑ），Ｒ１＋Ｒ５  ｍｏｄｑ）
を、ハッシュ値Ｈ（Ｒ２＋Ｒ３  ｍｏｄｑ）を使って復号してＲ１＋Ｒ５を得るので、ユーザ４は（Ｒ１＋Ｒ５，Ｒ２＋Ｒ３，Ｒ４）を保持することになる。非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ
を計算する。暗号文
ＥＮＣ４，５＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２＋Ｒ３＋Ｒ４  ｍｏｄｑ），Ｒ１  ｍｏｄｑ）
を計算してユーザ５に送信する。
【０１０３】
ＳｔｅｐＴ３でユーザ５は、暗号文
ＥＮＣ４，５＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２＋Ｒ３＋Ｒ４  ｍｏｄｑ），Ｒ１  ｍｏｄｑ）
を、ハッシュ値Ｈ（Ｒ２＋Ｒ３＋Ｒ４  ｍｏｄｑ）を使って復号してＲ１を得るので、ユーザ５は（Ｒ１，Ｒ２＋Ｒ３＋Ｒ４，Ｒ５）を保持することになる。非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５  ｍｏｄｑ
を計算する。
【０１０４】
ＳｔｅｐＯ１でセンタは、ＲＥＳ２，・・・，ＲＥＳ５が公開されてから、Ｄ１，ＲＥＳ１が公開され、その後Ｄ５が公開されたことを確認する。ＳｔｅｐＯ２でセンタは、
ＲＥＳ２＊ＲＥＳ３＊ＲＥＳ４＊ＲＥＳ５≡（ＩＫ２＊ＩＫ３＊ＩＫ４＊ＩＫ５）＾（Ｄ１）（ｍｏｄｐ）
ＲＥＳ１≡ＩＫ１＾（Ｄ５）（ｍｏｄｐ）
を確認する。ＳｔｅｐＯ３でセンタは、すべての確認ができたら、対話鍵
ＩＫ＝ＩＫ１＊ＩＫ２＊ＩＫ３＊ＩＫ４＊ＩＫ５  ｍｏｄｐ
＝ｇ＾（Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４＋Ｒ５）  ｍｏｄｐ
を計算する。
【０１０５】
ユーザがｎ人で、検証なしの場合を説明する。ｐを素数とし、ｑを（ｐ−１）の素因数とし、ｇを位数がｑであるＧＦ（ｑ）の元とする。ｐ，ｑ，ｇを固定のパラメータとして、ユーザ１〜ユーザｎ（ｎ≧３）とセンタに予め共有させておく。Ｘｉをユーザｉの非対称秘密鍵とする。ＹｉをユーザｉのＸｉに対する公開鍵とする。Ｐ＿ＥＮＣ（ｙ，ｍ）を、公開鍵ｙにより、公開鍵ｙに対応する非対称秘密鍵で復号できる暗号文に平文ｍを公開鍵方式で暗号化する関数とする。Ｃ＿ＥＮＣ（Ｋ，ｍ）を、対称秘密鍵Ｋにより復号できる暗号文に平文ｍを対称秘密鍵Ｋにより対称秘密鍵方式で暗号化する関数とする。Ｈを、ハッシュ関数とする。非対称共通鍵の交換が可能なｎ台の端末間の通信をセンタで傍受して前記非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する対話鍵共有方法である。
【０１０６】
ＳｔｅｐＳ１でユーザ１は、乱数Ｒ１（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ１＝ｇ＾（Ｒ１）  ｍｏｄｐ
を計算してユーザ２に送信する。
【０１０７】
ＳｔｅｐＲ１でユーザ２は、乱数Ｒ２（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫ２＝ｇ＾（Ｒ２）  ｍｏｄｐ
を計算し、暗号文
ＥＮＣ２，３＝Ｐ＿ＥＮＣ（Ｙ３，２‖Ｒ２）
を計算して、ＩＫ２とＥＮＣ２，３を、ユーザ３に送信する。
ｎ≧４のとき、ユーザｉ（３≦ｉ≦ｎ−１）は、乱数Ｒｉ（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫｉ＝ｇ＾（Ｒｉ）  ｍｏｄｐ
を計算し、暗号文
ＥＮＣｉ−１，ｉ＝Ｐ＿ＥＮＣ（Ｙｉ，ｉ−１‖Σｊ∈εｉ−１Ｒｊ）
を、非対称秘密鍵Ｘｉを使って復号してΣｊ∈εｉ−１Ｒｊを得て、暗号文
ＥＮＣｉ，ｉ＋１＝Ｐ＿ＥＮＣ（Ｙｉ＋１，ｉ‖Σｊ∈εｉＲｊ）
を計算して、ＩＫｉとＥＮＣｉ，ｉ＋１を、ユーザｉ＋１に送信する。以下、ユーザｉ＋１〜ユーザｎ−１まで、順次同様な処理を行う。
【０１０８】
ＳｔｅｐＴ１でユーザｎは、乱数Ｒｎ（∈Ｚｑ）を生成し、対話鍵の元データ
ＩＫｎ＝ｇ＾（Ｒｎ）  ｍｏｄｐ
を計算し、暗号文
ＥＮＣｎ−１，ｎ＝Ｐ＿ＥＮＣ（Ｙｎ，ｎ−１‖Σｊ∈εｎ−１Ｒｊ）
を、非対称秘密鍵Ｘｎを使って復号してΣｊ∈εｎ−１Ｒｊを得て、暗号文
ＥＮＣｎ，１＝Ｐ＿ＥＮＣ（Ｙ１，ｎ‖Σｊ∈εｎＲｊ）
を計算して、ＩＫｎとＥＮＣｎ，１を、ユーザ１に送信する。
【０１０９】
ＳｔｅｐＳ２でユーザ１は、暗号文
ＥＮＣｎ，１＝Ｐ＿ＥＮＣ（Ｙ１，ｎ‖Σｊ∈εｎＲｊ）
を、非対称秘密鍵Ｘ１を使って復号してΣｊ∈εｎＲｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算する。暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Σｊ∈δ１Ｒｊ）
を計算してユーザ２に送信する。
【０１１０】
ＳｔｅｐＲ２でユーザ２は、暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Σｊ∈δ１Ｒｊ）
を、非対称秘密鍵Ｘ２を使って復号してΣｊ∈δ１Ｒｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算する。暗号文
ＥＮＣ２，３＝Ｃ＿ＥＮＣ（Ｈ（Ｒ２），Σｊ∈δ２Ｒｊ）
を計算してユーザ３に送信する。
ｎ≧４のとき、ユーザｉ（３≦ｉ≦ｎ−１）は、暗号文
ＥＮＣｉ−１，ｉ＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｉ−１Ｒｊ），Σｊ∈δｉ−１Ｒｊ）
を、ハッシュ値Ｈ（Σｊ∈εｉ−１Ｒｊ）を使って復号してΣｊ∈δｉ−１Ｒｊを得て、非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算する。暗号文
ＥＮＣｉ，ｉ＋１＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｉＲｊ），Σｊ∈δｉＲｊ）
を計算してユーザｉ＋１に送信する。以下、ユーザｉ＋１〜ユーザｎ−１まで、順次同様な処理を行う。
【０１１１】
ＳｔｅｐＴ２でユーザｎは、暗号文
ＥＮＣｎ−１，ｎ＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｎ−１Ｒｊ），Σｊ∈δｎ−１Ｒｊ）
を、ハッシュ値Ｈ（Σｊ∈εｎ−１Ｒｊ）を使って復号してΣｊ∈δｎ−１Ｒｊを得る。非対称共通鍵
ＣＫ＝Ｒ１＋Ｒ２＋・・・＋Ｒｎ  ｍｏｄｑ
を計算する。
【０１１２】
ＳｔｅｐＣ１でセンタは、対話鍵
ＩＫ＝ＩＫ１＊ＩＫ２＊・・・＊ＩＫｎ  ｍｏｄｐ
＝ｇ＾（Ｒ１＋Ｒ２＋・・・＋Ｒｎ）  ｍｏｄｐ
を計算する。
【０１１３】
ユーザがｎ人で、検証ありの場合を説明する。以下の各Ｓｔｅｐは、Ｓ１→Ｒ１（ｎ−２ステップ）→Ｔ１→Ｓ２→Ｒ２（ｎ−２ステップ）→Ｔ２→Ｓ３→Ｒ３（ｎ−２ステップ）の順に進むものとする。
【０１１４】
Ｓｔａｒｔｅｒ（ユーザ１）は、
Ｓｔｅｐ  Ｓ１で、乱数Ｒ１，Ｄ１∈Ｚｑを生成する。対話鍵の元データ
ＩＫ１＝ｇ＾（Ｒ１）  ｍｏｄ  ｐ
と、チャレンジ
ＣＨＡ１＝ｇ＾（Ｄ１）  ｍｏｄ  ｐ
を計算し、ユーザ２に、ＩＫ１とＣＨＡ１を送信する。ＩＫ１とＣＨＡ１は事前計算が可能である。
【０１１５】
Ｓｔｅｐ  Ｓ２で、レスポンス
ＲＥＳ１＝ＣＨＡｎ＾（Ｒ１）  ｍｏｄｐ
を計算し、ユーザ２に、Ｄ１とＲＥＳ１を送信する。
【０１１６】
Ｓｔｅｐ  Ｓ３で、暗号文
ＥＮＣｎ，１＝Ｐ＿ＥＮＣ（Ｙ１，ｎ‖Σｉ∈εｎＲｉ  ｍｏｄｑ）
を、非対称秘密鍵Ｘ１を使って復号してΣｉ∈εｎＲｉを得る。暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Σｉ∈δ１Ｒｉ  ｍｏｄｑ）
を計算し、ユーザ２に送信する。
【０１１７】
Ｒｅｌａｙ（ユーザｉ、２≦ｉ≦ｎ−１）は、
ＳｔｅｐＲ１で、乱数Ｒｉ∈Ｚｑを生成し、対話鍵の元データ
ＩＫｉ＝ｇ＾（Ｒ１）  ｍｏｄｐ
と、レスポンス
ＲＥＳｉ＝ＣＨＡ１＾（Ｒｉ）  ｍｏｄｐ
を計算し、ユーザｉ＋１に、ＩＫｉとＲＥＳｉとＣＨＡ１を送信する。ＩＫｉは事前計算が可能である。ユーザ２〜ユーザｎ−１まで、順次この処理を行う。
【０１１８】
ＳｔｅｐＲ２で、ｎ≧４のとき、ユーザｉ（３〜ｎ−１）は、暗号文
ＥＮＣｉ−１，ｉ＝Ｐ＿ＥＮＣ（Ｙｉ，ｉ−１‖Σｊ∈εｉ−１Ｒｊ  ｍｏｄｑ）
を、非対称秘密鍵Ｘｉを使って復号してΣｊ∈εｉ−１Ｒｊを得る。
ユーザｉ（２〜ｎ−１）は、暗号文
ＥＮＣｉ，ｉ＋１＝Ｐ＿ＥＮＣ（Ｙｉ＋１，ｉ‖Σｊ∈εｉＲｊ  ｍｏｄｑ）
を計算し、ユーザｉ＋１に送信する。ユーザ２〜ユーザｎ−１まで、順次この処理を行う。
【０１１９】
ＳｔｅｐＲ３で、ユーザ２は、暗号文
ＥＮＣ１，２＝Ｐ＿ＥＮＣ（Ｙ２，１‖Σｉ∈δ１Ｒｉ  ｍｏｄｑ）
を、非対称秘密鍵Ｘ２を使って復号してΣｉ∈δ１Ｒｉを得る。
ｎ≧４のとき、ユーザｉ（３〜ｎ−１）は、暗号文
ＥＮＣｉ−１，ｉ＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｉ−１Ｒｊ  ｍｏｄｑ），Σｊ∈δｉ−１  Ｒｊ  ｍｏｄｑ）
を、ハッシュ値Ｈ（Σｊ∈εｉ−１Ｒｊ  ｍｏｄｑ）を使って復号してΣｊ∈δｉ−１  Ｒｊを得る。
ユーザｉ（２〜ｎ−１）は、暗号文
ＥＮＣｉ，ｉ＋１＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｉＲｊ  ｍｏｄｑ），Σｊ∈δｉ  Ｒｊ  ｍｏｄｑ）
を計算し、ユーザｉ＋１に送信する。ユーザ２〜ユーザｎ−１まで、順次この処理を行う。
【０１２０】
Ｔａｒｍｉｎａｔｏｒ（ユーザｎ）は、
ＳｔｅｐＴ１で、乱数Ｒｎ，Ｄｎ∈Ｚｑを生成する。対話鍵の元データ
ＩＫｎ＝ｇ＾（Ｒｎ）  ｍｏｄｐ
と、チャレンジ
ＣＨＡｎ＝ｇ＾（Ｄｎ）  ｍｏｄｐ
と、レスポンス
ＲＥＳｎ＝ＣＨＡ１＾（Ｒｎ）  ｍｏｄｐ
を計算する。ＩＫｎとＣＨＡｎは事前計算が可能である。ユーザ１に、ＩＫｎとＲＥＳｎとＣＨＡｎを送信する。
【０１２１】
ＳｔｅｐＴ２で、暗号文
ＥＮＣｎ−１，ｎ＝Ｃ＿ＥＮＣ（Ｈ（Σｊ∈εｎ−１Ｒｊ  ｍｏｄｑ），Σｊ∈δｎ−１  Ｒｊ  ｍｏｄｑ）
を、ハッシュ値Ｈ（Σｊ∈εｎ−１Ｒｊ  ｍｏｄｑ）を使って復号してΣｊ∈δｎ−１  Ｒｊを得る。暗号文
ＥＮＣｎ，１＝Ｐ＿ＥＮＣ（Ｙ１，ｎ‖Σｉ∈εｎＲｉ  ｍｏｄｑ）
を計算し、Ｄｎと共にユーザ１に送信する。
【０１２２】
Ｏｂｓｅｒｖｅｒ（センタ）は、Ｓｔｅｐ  Ｏ１で、（ＲＥＳ２，…，ＲＥＳｎ）→（Ｄ１，ＲＥＳ１）→Ｄｎの順に公開されていることを確認する。Ｓｔｅｐ  Ｏ２で、
Πｉ∈εｎＲＥＳｉ≡（Πｉ∈εｎＩＫｉ）＾（Ｄ１）  （ｍｏｄｐ）
ＲＥＳ１≡ＩＫ１＾（Ｄｎ）  （ｍｏｄｐ）
を確認する。
Ｓｔｅｐ  Ｏ３で、Ｓｔｅｐ  Ｏ１とＳｔｅｐ  Ｏ２での確認がＯＫならば、
ＩＫ＝Πｉ∈λ  ＩＫｉ  ｍｏｄｐ
を計算する。
【０１２３】
各端末は、非対称共通鍵ＣＫを計算した後に、検証式
Πｉ＝１ｎＩＫｉ≡ｇ＾（ＣＫ）  （ｍｏｄｐ）
を検証し、不成立ならセンタに通知する。これは、実際に共有された非対称共通鍵ＣＫと、センタが受け入れた対話鍵ＩＫの対応が正しいことを確認するために必要となる。
【０１２４】
全ての送信メッセージに対して送信者のディジタル署名を付加し、受信者は署名の検証に成功した場合のみメッセージを受信するようにできる。センタが対話鍵を計算後に、対話鍵に対する公開鍵証明書を発行することができる。対話鍵に対する公開鍵証明書を対話鍵で暗号化して、対話鍵を共有したユーザに送信することができる。ユーザもセンタと同じ検証を実施することができる。
【０１２５】
公開鍵方式の暗号関数Ｐ＿ＥＮＣ（・）としてＥｌ  Ｇａｍａｌ暗号の暗号関数を使用する場合において、ＩＫｉ（１≦ｉ≦ｎ）をＥｌ  Ｇａｍａｌ暗号における乱数のベキ乗剰余値の代わりに用いることができる。対称秘密鍵方式の暗号関数Ｃ＿ＥＮＣ（・）の代わりに公開鍵方式の暗号関数Ｐ＿ＥＮＣ（・）を用いることができる。有限体上の演算を楕円曲線上の演算に対応させて計算することができる。
【０１２６】
ユーザを、携帯電話システムにおける携帯電話とし、センタを、携帯電話システムの通信キャリアのゲートウェイまたは基地局とすることができる。ユーザを、ＰＣ／ＰＤＡ等のインターネット接続機能を有する端末とし、センタを、ウェブサーバまたはプロキシサーバまたはルータとすることができる。ユーザを、ＰＣ／ＰＤＡ等のローカル通信機能を有する端末とし、センタを、特定の端末またはＬＡＮサーバとすることができる。センタが複数ある場合は、ユーザは、複数のセンタを経由して通信することができる。
【０１２７】
上記のように、本発明の第５の実施の形態では、通話内容証明システムを、リング型通信路で結ばれた３人以上のユーザでＤＨ型対話鍵生成法を用いる構成としたので、効率を低下させることなくユーザ数を３人以上に拡張することができる。
【０１２８】
【発明の効果】
以上の説明から明らかなように、本発明では、非対称共通鍵を計算可能な鍵交換手段を持つ複数の端末と、センタとからなる鍵交換システムのセンタに、端末間の通信を傍受可能な傍受手段と、傍受した通信から非対称共通鍵を非対称秘密鍵とするグループ公開鍵である対話鍵を計算する手段とを備えた構成としたので、鍵共有プロトコルにおいて送受信される情報と公開鍵（対話鍵）の関係が検証でき、対話鍵に対応する非対称共通鍵をいつ誰が秘密に共有したかが分かるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態における対話鍵共有システムの概念図、
【図２】本発明の第１の実施の形態における対話鍵共有システムの構成図、
【図３】本発明の第１の実施の形態における対話鍵共有システムの動作手順を示す流れ図、
【図４】本発明の第２の実施の形態における対話鍵共有システムの動作手順を示す流れ図、
【図５】本発明の第４の実施の形態における対話鍵共有システムの構成図、
【図６】本発明の第５の実施の形態における対話鍵共有システムの動作手順を示す流れ図、
【図７】従来の通話内容証明の手順を示す流れ図である。
【符号の説明】
１  ユーザ（Ａｌｉｃｅ）
２  ユーザ（Ｂｏｂ）
３  オブザーバ（Ｃｈａｒｌｅｙ）
４  対話文
５  非対称共通鍵
６  対話鍵
７  鍵交換手段
８  傍受手段
９  対話鍵計算手段
１０  検証者
１１  対話文保存手段
１２  署名検証手段
【図１】
2004282575.tif 000003
【図２】
2004282575.tif 000004
【図３】
2004282575.tif 000005
【図４】
2004282575.tif 000006
【図５】
2004282575.tif 000007
【図６】
2004282575.tif 000008
【図７】
2004282575.tif 000009