"第1情報共有装置と第2情報共有装置とが情報を共有する情報共有方法であって、前記第1情報共有装置で、任意値tを生成するステップと、前記第1情報共有装置で、前記任意値tと巡回群Gの生成元gとを用い、出力情報Tgt∈Gを生成するステップと、前記第1情報共有装置で、前記出力情報Tを出力するステップと、前記第2情報共有装置で、任意値yを生成するステップと、前記第2情報共有装置で、前記任意値yと前記生成元gとを用い、出力情報Ygy∈Gを生成するステップと、前記第2情報共有装置で、前記出力情報Yを出力するステップと、前記第1情報共有装置で、前記出力情報Yの入力を受け付けるステップと、前記第1情報共有装置で、前記第2情報共有装置の秘密情報bに対応する公開情報Bgb∈Gと、前記出力情報Yと、前記第1情報共有装置の秘密情報aと、前記任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成するステップと、前記第2情報共有装置で、前記出力情報Tの入力を受け付けるステップと、前記第2情報共有装置で、前記第1情報共有装置の秘密情報aに対応する公開情報Aga∈Gと、前記出力情報Tと、前記第2情報共有装置の秘密情報bと、前記任意値yとを用い、各演算式Wjj1Jがそれぞれ表す前記共有情報Ujj1Jを生成するステップと、を有し、前記演算式Vjj1J及び前記演算式Wjj1Jは、それぞれ、前記巡回群Gでの演算を表し、少なくとも一部のmn∈1Jrrrに対してgabrayrbtrtyを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である、ことを特徴とする情報共有方法。請求項1の情報共有方法であって、前記演算式Vjは、UjBrartYrart又はそれに変形可能な式であり、前記演算式Wjは、UjArbryTrbry又はそれに変形可能な式である、ことを特徴とする情報共有方法。第1情報共有装置と第2情報共有装置とが情報を共有する情報共有方法であって、前記第1情報共有装置で、任意値tを生成するステップと、前記第1情報共有装置で、前記任意値tと巡回群G1の生成元g1とを用い、出力情報Tg1t∈G1を生成するステップと、前記第1情報共有装置で、前記出力情報Tを出力するステップと、前記第2情報共有装置で、任意値yを生成するステップと、前記第2情報共有装置で、前記任意値yと前記生成元g2とを用い、出力情報Yg2y∈G2を生成するステップと、前記第2情報共有装置で、前記出力情報Yを出力するステップと、前記第1情報共有装置で、前記出力情報Yの入力を受け付けるステップと、前記第1情報共有装置で、前記第2情報共有装置の公開情報Bg2b∈G2と、前記出力情報Yと、秘密情報z及び前記第1情報共有装置の公開情報Ag1a∈G1に対応する前記第1情報共有装置の秘密情報CAz∈G1と、g1zである公開情報P1及び/又はg2zである公開情報P2と、前記任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成するステップと、前記第2情報共有装置で、前記出力情報Tの入力を受け付けるステップと、前記第2情報共有装置で、前記第1情報共有装置の公開情報Ag1a∈G1と、前記出力情報Tと、前記秘密情報z及び前記公開情報Bに対応する前記第2情報共有装置の秘密情報DBz∈G2と、前記公開情報P1及び/又は前記公開情報P2と、前記任意値yとを用い、各演算式Wjj1Jがそれぞれ表す前記共有情報Ujj1Jを生成するステップと、を有し、前記演算式Vjj1J及び前記演算式Wjj1Jは、それぞれ、前記巡回群G1の元と前記巡回群G2の元とから巡回群GTの元を得る双線形写像e:G1×G2→GTを含み、少なくとも一部のmn∈1Jrrrに対してgTzabrayrbtrty∈GTを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である、ことを特徴とする情報共有方法。請求項3の情報共有方法であって、前記演算式Vjは、UjeP1rtBeP1rtY又はそれに変形可能な式であり、かつ、前記演算式Wjは、UjeP2ryeP2ry又はそれに変形可能な式である、ことを特徴とする情報共有方法。請求項3又は4の情報共有方法であって、G1G2及びg1g2であり、前記第1情報共有装置で、Ytを共有情報UJ1として生成するステップと、前記第2情報共有装置で、Tyを前記共有情報UJ1として生成するステップと、を有する情報共有方法。請求項3又は4の情報共有方法であって、前記第1情報共有装置で、前記任意値tと前記生成元g2とを用い、出力情報T2g2t∈G2を生成するステップと、前記第1情報共有装置で、前記出力情報T2を出力するステップと、前記第2情報共有装置で、前記任意値yと前記生成元g1とを用い、出力情報Y1g1y∈G2を生成するステップと、前記第2情報共有装置で、前記出力情報Y1を出力するステップと、前記第1情報共有装置で、Y1tを共有情報1UJ1として生成するステップと、前記第1情報共有装置で、Ytを共有情報2UJ1として生成するステップと、前記第2情報共有装置で、Tyを共有情報1UJ1として生成するステップと、前記第2情報共有装置で、T2yを共有情報2UJ1として生成するステップと、を有する情報共有方法。請求項1から6の何れかの情報共有方法であって、少なくとも一部のmn∈1Jに対するベクトルrとベクトルrとが一次独立であり、かつ、少なくとも一部のmn∈1Jに対するベクトルrとベクトルrとが一次独立であり、かつ、aとtとの線形結合をLAjとし、bとyとの線形結合をLBjとした場合における、すべてのj1JについてrabrayrbtrtyLAjLBjを満たす、ことを特徴とする情報共有方法。請求項1から6の何れかの情報共有方法であって、少なくとも一部のmn∈1Jに対するベクトルrとベクトルrとが一次独立であり、かつ、少なくとも一部のmn∈1Jに対するベクトルrとベクトルrとが一次独立であり、かつ、u0av0bu1tv1yとし、u0とu1との線形結合をLAjιとし、v0とv1との線形結合をLBjιとした場合における、すべてのιについてruιv0ruιv1LAjιLBjιを満たし、かつ、u0とu1との線形結合をLAjθとし、v0とv1との線形結合をLBjθとした場合における、すべてのθについてru0vθru1vθLAjθLBjθを満たす、ことを特徴とする情報共有方法。請求項1から8の何れかの情報共有方法であって、前記第1情報共有装置で、前記第1情報共有装置で得られた前記共有情報Ujj1Jを含む情報を関数に入力して得られる鍵を生成するステップと、前記第2情報共有装置で、前記第2情報共有装置で得られた前記共有情報Ujj1Jを含む情報を前記関数に入力して得られる前記鍵を生成するステップと、を有する情報共有方法。他の装置と情報を共有する情報共有装置であって、任意値tを生成する任意値生成部と、前記任意値tと巡回群Gの生成元gとを用い、出力情報Tgt∈Gを生成する出力情報生成部と、前記出力情報Tを出力する出力部と、出力情報Yの入力を受け付ける入力部と、前記第2情報共有装置の秘密情報bに対応する公開情報Bgb∈Gと、前記出力情報Yと、秘密情報aと、前記任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する共有情報生成部と、を有し、前記演算式Vjj1Jは、それぞれ前記巡回群Gでの演算を表し、少なくとも一部のmn∈1Jrrrに対してgabrayrbtrtyを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である、ことを特徴とする情報共有装置。他の装置と情報を共有する情報共有装置であって、任意値tを生成する任意値生成部と、前記任意値tと巡回群G1の生成元g1とを用い、出力情報Tg1t∈G1を生成する出力情報生成部と、前記出力情報Tを出力する出力部と、前記出力情報Yの入力を受け付ける入力部と、前記第2情報共有装置の公開情報Bg2b∈G2と、前記出力情報Yと、秘密情報z及び前記第1情報共有装置の公開情報Ag1a∈G1に対応する前記第1情報共有装置の秘密情報CAz∈G1と、g1zである公開情報P1及び/又はg2zである公開情報P2と、前記任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する共有情報生成部と、を有し、前記演算式Vjj1Jは、それぞれ、前記巡回群G1の元と前記巡回群G2の元とから巡回群GTの元を得る双線形写像e:G1×G2→GTを含み、少なくとも一部のmn∈1Jrrrに対してgTzabrayrbtrty∈GTを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である、ことを特徴とする情報共有装置。第1情報共有装置と第2情報共有装置とを有し、前記第1情報共有装置は、任意値tを生成する第1任意値生成部と、前記任意値tと巡回群Gの生成元gとを用い、出力情報Tgt∈Gを生成する第1出力情報生成部と、前記出力情報Tを出力する第1出力部と、を有し、前記第2情報共有装置は、任意値yを生成する第2任意値生成部と、前記任意値yと前記生成元gとを用い、出力情報Ygy∈Gを生成する第2出力情報生成部と、前記出力情報Yを出力する第出力部と、を有し、前記第1情報共有装置は、さらに、前記出力情報Yの入力を受け付ける第1入力部と、前記第2情報共有装置の秘密情報bに対応する公開情報Bgb∈Gと、前記出力情報Yと、前記第1情報共有装置の秘密情報aと、前記任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する第1共有情報生成部と、を有し、前記第2情報共有装置は、さらに、前記出力情報Tの入力を受け付ける第2入力部と、前記第1情報共有装置の秘密情報aに対応する公開情報Aga∈Gと、前記出力情報Tと、前記第2情報共有装置の秘密情報bと、前記任意値yとを用い、各演算式Wjj1Jがそれぞれ表す前記共有情報Ujj1Jを生成する第2共有情報生成部と、を有し、前記演算式Vjj1J及び前記演算式Wjj1Jは、それぞれ、前記巡回群Gでの演算を表し、少なくとも一部のmn∈1Jrrrに対してgabrayrbtrtyを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である、ことを特徴とする情報共有システム。第1情報共有装置と第2情報共有装置とを有し、前記第1情報共有装置は、任意値tを生成する第1任意値生成部と、前記任意値tと巡回群G1の生成元g1とを用い、出力情報Tg1t∈G1を生成する第1出力情報生成部と、前記出力情報Tを出力する第1出力部と、を有し、前記第2情報共有装置は、任意値yを生成する第2任意値生成部と、前記任意値yと前記生成元g2とを用い、出力情報Yg2y∈G2を生成する第2出力情報生成部と、前記出力情報Yを出力する第2出力部と、を有し、前記第1情報共有装置は、さらに、前記出力情報Yの入力を受け付ける第1入力部と、前記第2情報共有装置の公開情報Bg2b∈G2と、前記出力情報Yと、秘密情報z及び前記第1情報共有装置の公開情報Ag1a∈G1に対応する前記第1情報共有装置の秘密情報CAz∈G1と、g1zである公開情報P1及び/又はg2zである公開情報P2と、前記任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する第1共有情報生成部と、を有し、前記第2情報共有装置は、さらに、前記出力情報Tの入力を受け付ける第2入力部と、前記第1情報共有装置の公開情報Ag1a∈G1と、前記出力情報Tと、前記秘密情報z及び前記公開情報Bに対応する前記第2情報共有装置の秘密情報DBz∈G2と、前記公開情報P1及び/又は前記公開情報P2と、前記任意値yとを用い、各演算式Wjj1Jがそれぞれ表す前記共有情報Ujj1Jを生成する第2共有情報生成部と、を有し、前記演算式Vjj1J及び前記演算式Wjj1Jは、それぞれ、前記巡回群G1の元と前記巡回群G2の元とから巡回群GTの元を得る双線形写像e:G1×G2→GTを含み、少なくとも一部のmn∈1Jrrrに対してgTzabrayrbtrty∈GTを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である、ことを特徴とする情報共有システム。請求項10又は11の情報共有装置としてコンピュータを機能させるためのプログラム。しかし、非特許文献1の方式は、共有情報U1及びU2を計算するために、演算量の大きなハッシュ関数Fを用いてdFとeFとを計算する必要がある。本発明はこのような点に鑑みてなされたものであり、高い安全性を確保しつつ、低い演算量で共有情報Ujj1Jを共有することが可能な技術を提供することを目的とする。本発明の第1態様では、第1情報共有装置で任意値tを生成し、任意値tと巡回群Gの生成元gとを用い、出力情報Tgt∈Gを生成して出力する。第2情報共有装置で任意値yを生成し、任意値yと生成元gとを用い、出力情報Ygy∈Gを生成して出力する。第1情報共有装置で、出力情報Yの入力を受け付け、第2情報共有装置の秘密情報bに対応する公開情報Bgb∈Gと、出力情報Yと、第1情報共有装置の秘密情報aと、任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する。第2情報共有装置で、出力情報Tの入力を受け付け、第1情報共有装置の秘密情報aに対応する公開情報Aga∈Gと、出力情報Tと、第2情報共有装置の秘密情報bと、任意値yとを用い、各演算式Wjj1Jがそれぞれ表す共有情報Ujj1Jを生成する。ここで演算式Vjj1J及び演算式Wjj1Jは、それぞれ、巡回群Gでの演算を表わす。少なくとも一部のmn∈1Jrrrに対してgabrayrbtrtyを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である。本発明の第2態様では、第1情報共有装置で、任意値tを生成し、任意値tと巡回群G1の生成元g1とを用い、出力情報Tg1t∈G1を生成して出力する。第2情報共有装置で、任意値yを生成し、任意値yと生成元g2とを用い、出力情報Yg2y∈G2を生成して出力する。第1情報共有装置で、出力情報Yの入力を受け付け、第2情報共有装置の公開情報Bg2b∈G2と、出力情報Yと、秘密情報z及び第1情報共有装置の公開情報Ag1a∈G1に対応する第1情報共有装置の秘密情報CAz∈G1と、g1zである公開情報P1及び/又はg2zである公開情報P2と、任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する。第2情報共有装置で、出力情報Tの入力を受け付け、第1情報共有装置の公開情報Ag1a∈G1と、出力情報Tと、秘密情報z及び公開情報Bに対応する第2情報共有装置の秘密情報DBz∈G2と、公開情報P1及び/又は公開情報P2と、任意値yとを用い、各演算式Wjj1Jがそれぞれ表す共有情報Ujj1Jを生成する。ここで演算式Vjj1J及び演算式Wjj1Jは、それぞれ、巡回群G1の元と巡回群G2の元とから巡回群GTの元を得る双線形写像e:G1×G2→GTを含む。少なくとも一部のmn∈1Jrrrに対してgTzabrayrbtrty∈GTを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である。本発明では、高い安全性を確保しつつ、低い演算量で共有情報Ujj1Jを共有することができる。図面を参照して本発明の実施形態を説明する。定義まず、本形態で使用する用語及び記号を定義する。Zq:Zqはqを法とする剰余環を表す。Zqの要素の一例は、qを法とする剰余類の完全代表系である。qを法とする剰余類の完全代表系の一例は0q1である。なお、qは正整数であり、qをビット表現した場合のビット長を例えばLLは正整数とする。安全性の面から位数qは素数であることが望ましい。また、位数qが素数でない場合には、位数qの最大因数のビット長がL以上であることが望ましい。素数であるか否かが不明な正整数をqとして用いてもよい。GG1G2GT:GG1G2GTは巡回群を表す。実施形態の巡回群GG1G2は、例えば、位数qの巡回群である。巡回群GG1G2としては、例えば、楕円曲線上の有理点のなす群や有限体の乗法群などを用いることができる。楕円曲線上の有理点のなす群をコンピュータ上で実現するための具体的方法には様々なものが存在し、実際、楕円曲線上の有理点のなす群で構成され、コンピュータ上で実装可能な様々な暗号方式が存在する。巡回群GTの具体例は、位数qの有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。楕円曲線上の有理点のなす群や有限体の乗法群などを巡回群GTとしてもよい。G1G2であってもよいし、G1≠G2であってもよい。gg1g2gT:gg1g2gTは巡回群GG1G2GTの生成元を表す。g1g2であってもよいし、g1≠g2であってもよい。巡回群Gで定義された演算:巡回群Gの元は巡回群Gで定義された演算について群をなす。例えば、巡回群Gが楕円曲線上の有理点のなす群である場合、巡回群Gで定義された演算は楕円曲線上での楕円加算などである。また、例えば、巡回群Gが有限体の乗法群である場合、巡回群Gでの演算は、qを法とした剰余乗算などである。なお、実施形態では、巡回群Gで定義された演算を乗法的に表現する。すなわち、α∈Zq及びβ∈Gに対するβα∈Gは、β∈Gに対して巡回群Gで定義された演算をα回施すことを意味し、β1β2∈Gに対するβ1β2∈Gは、β1β2∈G1とを被演算子として巡回群Gで定義された演算を行うことを意味する。例えば、巡回群Gが楕円曲線上の有理点のなす群である場合、βα∈Gは、楕円曲線上の点βを楕円曲線上でα倍する楕円スカラー倍演算を表し、β1β2∈Gは、楕円曲線上の点β1と点β2とを楕円曲線上で加算する楕円加算演算を表す。また、例えば、巡回群Gが有限体の乗法群である場合、βα∈Gは、βを整数とみなした場合のβαmodqの演算を表し、β1β2∈Gは、β1及びβ2を整数とみなした場合のβ1β2modqの演算を表す。巡回群Gでの演算:巡回群Gでの演算は巡回群Gで定義された演算を用いて巡回群G上で実行可能な演算を表す。例えば、巡回群Gが楕円曲線上の有理点のなす群である場合、巡回群Gでの演算は、楕円曲線上での楕円加算、楕円スカラー倍算、逆元演算、又は、それらの少なくとも一部の組み合わせた演算を表す。また、例えば、巡回群Gが有限体の乗法群である場合、巡回群Gでの演算は、qを法とした剰余乗算、べき乗剰余、逆元演算、又は、それらの少なくとも一部の組み合わせた演算を表す。巡回群G1G2GTについても同様である。H:Hは任意の値αをLビットのビット列に写すハッシュ関数を表す。任意の値αの例は任意長のビット列01や巡回群の元などである。また、Hは、α1αnに対して定まるハッシュ値を表す。例えば、α1αnのそれぞれがすべてビット列なのであれば、α1αnのビット結合α1αnをSHA1などの公知のハッシュ関数に入力して得られる値をH∈01Lとする。また、例えば、α1αnの少なくとも一部がビット列以外の値例えば巡回群Gの元なのであれば、α1αnの各要素をビット列に写像した値β1βnのビット結合β1βnのビット結合を、SHA1などの公知のハッシュ関数に入力して得られる値をH∈01Lとする。このようなハッシュ関数Hは、SHA1などの公知のハッシュ関数を用いて容易に構成できる。H1H2:H1は任意の値を巡回群G1に写すハッシュ関数を表し、H1∈G1はαに対して定まるハッシュ値を表す。H2は任意の値を巡回群G2に写すハッシュ関数を表し、H2∈G2はαに対して定まるハッシュ値を表す。αの例は任意長のビット列01である。このようなハッシュ関数H1H2は、SHA1などの公知のハッシュ関数を用いて容易に構成できる。pj:pjは、u0u1v0v1∈Zqを不定元とする剰余環Zq上で定義された多項式pj∈Zqu0u1v0v1である。実施形態では以下のように定義される。係数rrrr∈Zqは定数であってもよいし、短期公開鍵、公開鍵、ユーザID、公開パラメータなどに依存して値が決まるものであってもよい。e:eは巡回群G1の元と巡回群G2の元とから巡回群GTの元を得る双線形写像e:G1×G2→GTを表わす。双線形写像eは、以下の性質を満たす。[双線形性]すべてのΩ1∈G1,Ω2∈G2及びν,κ∈Zqについて以下の関係を満たす。eeνκ[非退化性]すべてのΩ1∈G1,Ω2∈G2を巡回群GTの単位元に写す写像ではない。[計算可能性]あらゆるΩ1∈G1,Ω2∈G2についてeを効率的に計算するアルゴリズムが存在する。双線形写像eの具体例は、WeilペアリングやTateペアリングなどのペアリング演算のための関数やアルゴリズムである。第1実施形態<原理>第1実施形態の原理を説明する。第1実施形態では、第1情報共有装置で任意値tを生成し、任意値tと巡回群Gの生成元gとを用い、出力情報Tgt∈Gを生成して出力する。第2情報共有装置で任意値yを生成し、任意値yと生成元gとを用い、出力情報Ygy∈Gを生成して出力する。第1情報共有装置で、出力情報Yの入力を受け付け、第2情報共有装置の秘密情報bに対応する公開情報Bgb∈Gと、出力情報Yと、第1情報共有装置の秘密情報aと、任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する。第2情報共有装置で、出力情報Tの入力を受け付け、第1情報共有装置の秘密情報aに対応する公開情報Aga∈Gと、出力情報Tと、第2情報共有装置の秘密情報bと、任意値yとを用い、各演算式Wjj1Jがそれぞれ表す共有情報Ujj1Jを生成する。本形態の演算式Vjj1J及び演算式Wjj1Jは、それぞれ、巡回群Gでの演算を表わす。少なくとも一部のmn∈1Jrrrに対してgabrayrbtrtyを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である。すなわち、δmrrrδnrrrを満たすのはδmδn0である場合に限られる。ここで、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である場合、攻撃者の装置ADVは、第2情報共有装置が共有情報Ujj1Jを計算する際に、それらのすべてについて第1情報共有装置の公開情報Aga∈Gの成分を打ち消すことになるTをTとして生成するとともに、第1情報共有装置が共有情報Ujj1Jを計算する際に、それらのすべてについて第2情報共有装置の公開情報Bgb∈Gの成分を打ち消すことになるYをYとして生成することができない。すなわち、攻撃者の装置ADVは、第1情報共有装置と第2情報共有装置との両方に成りすまして中間者攻撃を行うことができない。また、本形態では、共有情報Ujj1Jの計算のために演算量の大きなハッシュ関数Fを用いる必要はない。これにより、本形態では、高い安全性を確保しつつ、第1情報共有装置と第2情報共有装置とが低い演算量で共有情報を共有できる。また、第1情報共有装置が、共有情報Ujj1Jを含む情報を関数に入力して得られる鍵を生成し、第2情報共有装置が、共有情報Ujj1Jを含む情報を当該関数に入力して得られる鍵を生成することで、第1情報共有装置と第2情報共有装置とで同一の鍵を共有できる。本形態では、任意値tyに応じて鍵の値が異なるため、第1情報共有装置と第2情報共有装置との間で上記の処理を行うたびに共有される鍵Kが変化する。なお、関数の例は前述のハッシュ関数Hである。また好ましくは、少なくとも一部のmn∈1Jに対するベクトルrとベクトルrとが一次独立であり、かつ、少なくとも一部のmn∈1Jに対するベクトルrとベクトルrとが一次独立であり、かつ、aとtとの線形結合をLAjとし、bとyとの線形結合をLBjとした場合における、すべてのj1JについてrabrayrbtrtyLAjLBjを満たす条件1。これにより高い安全性を確保できる。また好ましくは、少なくとも一部のmn∈1Jに対するベクトルrとベクトルrとが一次独立であり、かつ、少なくとも一部のmn∈1Jに対するベクトルrとベクトルrとが一次独立であり、かつ、u0av0bu1tv1yとし、u0とu1との線形結合をLAjιとし、v0とv1との線形結合をLBjιとした場合における、すべてのιについてruιv0ruιv1LAjιLBjιを満たし、かつ、u0とu1との線形結合をLAjθとし、v0とv1との線形結合をLBjθとした場合における、すべてのθについてru0vθru1vθLAjθLBjθを満たす条件2。これにより高い安全性を確保できる。<構成>第1実施形態の構成を例示する。図1に例示するように、第1実施形態の情報共有システム1は、情報共有装置110と情報共有装置120とを有する。情報共有装置110は、記憶部111と入力部112と出力部113と制御部114と任意値生成部115と出力情報生成部116と共有情報生成部117と鍵生成部118とを有する。また、情報共有装置120は、記憶部121と入力部122と出力部123と制御部124と任意値生成部125と出力情報生成部126と共有情報生成部127と鍵生成部128とを有する。情報共有装置110,120は、CPU、RAM、ROMなどからなる公知又は専用のコンピュータと特別なプログラムとを有する特別な装置である。特別なプログラムはコンピュータのCPUに読み込まれ、CPUが特別なプログラムを実行することで、情報共有装置110,120が構築される。また、特別なプログラムだけではなく汎用ルーチンなどの汎用プログラムもCPUに読み込まれ、CPUが特別なプログラムと汎用プログラムとを実行することで情報共有装置110,120が構築されてもよい。記憶部111,121は、例えば、RAM、キャッシュメモリ、レジスタ、ハードディスク装置等の補助記憶装置、又は、それらの少なくとも一部を結合した記憶領域などである。入力部112,122及び出力部113,123は、例えば、特別なプログラムが読み込まれたCPUの制御のもと駆動する通信装置や入出力インタフェースなどである。制御部114,124、任意値生成部115,125、出力情報生成部116,126、共有情報生成部117,127、及び鍵生成部118,128は、例えば、特別なプログラムが読み込まれたCPUである。なお、制御部114,124、任意値生成部115,125、出力情報生成部116,126、共有情報生成部117,127、及び鍵生成部118,128などの処理部の少なくとも一部が集積回路などのハードウェアで構成されていてもよい。なお、情報共有装置110,120は、それぞれ、制御部114,124の制御のもと各処理を実行する。また、各演算過程で得られるデータは記憶部111,121に格納され、必要に応じて他の演算に用いられる。<処理>次に、第1実施形態の処理を例示する。[前処理]システム管理者などによって位数q、剰余環Zq、巡回群G、生成元g、ハッシュ関数H、第1情報共有装置110の秘密鍵秘密情報a∈Zq及び公開鍵公開情報Aga∈G、第2情報共有装置120の秘密鍵秘密情報b∈Zq及び公開鍵公開情報Bgb∈Gが定められる。秘密鍵a及び公開鍵ABは第1情報共有装置110の記憶部111に格納され、秘密鍵bは第2情報共有装置120の記憶部121に格納される。また、任意値生成部115,125は、剰余環Zqの元を生成するように構成され、出力情報生成部116,126は、生成元gを用いて巡回群G上の演算が可能なように構成され、共有情報生成部117,217は、巡回群G上の演算が可能なように構成され、鍵生成部118,128は、ハッシュ関数Hを用いたハッシュ演算が可能なように構成される。[鍵交換]次に、図2A及び図2Bを用い、第1実施形態の鍵交換処理を説明する。第1情報共有装置110図1の任意値生成部115がランダムな短期秘密鍵任意値tを以下の式のように生成し、生成した短期秘密鍵tを記憶部111に格納するステップS111。t∈Zq...例えば、任意値生成部115は、SHA1等の公知のハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて発生させた擬似乱数を用いて短期秘密鍵t∈Zqを生成する。第1情報共有装置110の出力情報生成部116は、記憶部111から短期秘密鍵tを読み出し、短期秘密鍵tと巡回群Gの生成元gとを用い、出力情報Tを以下の式のように生成し、生成した出力情報Tを記憶部111に格納するステップS112。Tgt∈G...記憶部111に格納された公開鍵AB及び出力情報Tは出力部112に送られ、出力部112はを出力するステップS113。出力されたは、ネットワークや可搬型記録媒体などを介して第2情報共有装置120に送られる。第2情報共有装置120の入力部122はの入力を受け付け、は記憶部121に格納されるステップS121。第2情報共有装置120の任意値生成部125がランダムな短期秘密鍵任意値yを以下の式のように生成し、生成した短期秘密鍵yを記憶部121に格納する。y∈Zq...例えば、任意値生成部125は、SHA1等の公知のハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて発生させた擬似乱数を用いて短期秘密鍵y∈Zqを生成するステップS122。第2情報共有装置120の出力情報生成部126は、記憶部121から短期秘密鍵yを読み出し、短期秘密鍵yと巡回群Gの生成元gとを用い、出力情報Yを以下の式のように生成し、生成した出力情報Yを記憶部121に格納するステップS123。Ygy∈G...記憶部121に格納された公開鍵AB、出力情報T及び出力情報Yは出力部123に送られ、出力部123はを出力するステップS124。出力されたは、ネットワークや可搬型記録媒体などを介して第1情報共有装置110に送られる。第1情報共有装置110の入力部112はの入力を受け付け、は記憶部111に格納されるステップS114。第1情報共有装置110の共有情報生成部117は、記憶部111から出力情報Yと公開鍵Bと秘密鍵aと短期秘密鍵tとを読み込む。共有情報生成部117は、これらを用いて各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する。共有情報Ujj1Jは、それぞれ、rrrrに対してgabrayrbtrtyを満たす。本形態の演算式Vjは巡回群Gでの演算を表し、少なくとも一部のmn∈1J又は式に変形可能な式である。UjBrartYrart...式に変形可能な式の例は以下の式などである。UjBrtraYrtra...UjBartrYartr...UjYrartBrart...少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である。好ましくは前述の条件1又は条件2を満たす。生成された共有情報Ujj1Jは記憶部111に格納されるステップS115。第1情報共有装置110の鍵生成部118が、記憶部111から共有情報Ujj1Jと公開鍵ABと出力情報TYとを読み込み、これらを含む情報をハッシュ関数Hに入力し、鍵KH...を生成し、生成した鍵Kを出力するステップS116。第2情報共有装置120の共有情報生成部127は、記憶部121から共有情報Ujj1Jと公開鍵ABと出力情報TYとを読み込む。共有情報生成部127は、これらを用いて各演算式Wjj1Jがそれぞれ表す共有情報Ujj1Jを生成する。共有情報Ujj1Jは、それぞれ、rrrrに対してgabrayrbtrtyを満たす。本形態の演算式Wjは巡回群Gでの演算を表し、少なくとも一部のmn∈1J又は式に変形可能な式である。UjArbryTrbry...式に変形可能な式の例は以下の式などである。UjAryrbTryrb...UjAbryrTbryr...UjTrbryArbry...少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である。好ましくは前述の条件1又は条件2を満たす。生成された共有情報Ujj1Jは記憶部121に格納されるステップS125。第2情報共有装置120の鍵生成部128は、記憶部121から共有情報Ujj1Jと公開鍵ABと出力情報TYとを読み込み、これらを含む情報をハッシュ関数Hに入力し、鍵KH...を生成し、生成した鍵Kを出力するステップS126。<本形態の特徴>巡回群Gは可換群であること、及び剰余環Zqが可換環であることから、式は以下のように変形できる。式などの式に変形可能な式も同様である。ただし、上付き添え字のpjはpjを表す。BrartYrartgbartyartgabrayrbtrtygpj同様に式は以下のように変形でき、式と等しいことが分かる。式などの式に変形可能な式も同様である。ArbryTrbrygabrytbrygabrayrbtrtygpjこのように第1情報共有装置110と第2情報共有装置120との間で共有情報Ujj1Jを共有でき、鍵Kも共有できる。短期秘密鍵tyに応じて鍵Kの値が異なるため、第1情報共有装置110と第2情報共有装置120との間で上記の処理を行うたびに共有される鍵Kが変化する。またベクトルrrrとベクトルrrrとが一次独立であるため、前述のように中間者攻撃を防止できる。さらにハッシュ関数を用いることなく第1情報共有装置110と第2情報共有装置120とが共有情報Ujを共有できる。よって本形態では、高い安全性を確保しつつ、第1情報共有装置110と第2情報共有装置120とが低い演算量で共有情報を共有できる。第2実施形態次に、本発明のおける第2実施形態を説明する。第2実施形態は双線形写像を用いる例である。以下では第1実施形態との相違点を中心に説明し、第1実施形態と共通する事項については説明を省略する。<原理>第2実施形態の原理を説明する。第2実施形態では、第1情報共有装置で、任意値tを生成し、任意値tと巡回群G1の生成元g1とを用い、出力情報Tg1t∈G1を生成して出力する。第2情報共有装置で、任意値yを生成し、任意値yと生成元g2とを用い、出力情報Yg2y∈G2を生成して出力する。第1情報共有装置で、出力情報Yの入力を受け付け、第2情報共有装置の公開情報Bg2b∈G2と、出力情報Yと、秘密情報z及び第1情報共有装置の公開情報Ag1a∈G1に対応する第1情報共有装置の秘密情報CAz∈G1と、g1zである公開情報P1及び/又はg2zである公開情報P2と、任意値tとを用い、各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する。第2情報共有装置で、出力情報Tの入力を受け付け、第1情報共有装置の公開情報Ag1a∈G1と、出力情報Tと、秘密情報z及び公開情報Bに対応する第2情報共有装置の秘密情報DBz∈G2と、公開情報P1及び/又は公開情報P2と、任意値yとを用い、各演算式Wjj1Jがそれぞれ表す共有情報Ujj1Jを生成する。本形態の演算式Vjj1J及び演算式Wjj1Jは、それぞれ、巡回群G1の元と巡回群G2の元とから巡回群GTの元を得る双線形写像e:G1×G2→GTを含む。少なくとも一部のmn∈1Jrrrに対してgTzabrayrbtrty∈GTを満たし、少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である。これにより本形態でも、高い安全性を確保しつつ、第1情報共有装置と第2情報共有装置とが低い演算量で共有情報を共有できる。また本形態でも前述の条件1又は条件2を満たすことが望ましい。これにより高い安全性を確保できる。また、第1情報共有装置が、共有情報Ujj1Jを含む情報を関数に入力して得られる鍵を生成し、第2情報共有装置が、共有情報Ujj1Jを含む情報を当該関数に入力して得られる鍵を生成することで、第1情報共有装置と第2情報共有装置とで同一の鍵を共有できる。本形態では、任意値tyに応じて鍵の値が異なるため、第1情報共有装置と第2情報共有装置との間で上記の処理を行うたびに共有される鍵Kが変化する。<構成>第2実施形態の構成を例示する。図3に例示するように、第2実施形態の情報共有システム2は、情報共有装置210と情報共有装置220とを有する。情報共有装置210は、記憶部211と入力部212と出力部213と制御部114と任意値生成部115と出力情報生成部216と共有情報生成部217と鍵生成部218とを有する。また、情報共有装置220は、記憶部221と入力部222と出力部223と制御部124と任意値生成部125と出力情報生成部226と共有情報生成部227と鍵生成部228とを有する。第1実施形態と同様、情報共有装置210,220は、CPU、RAM、ROMなどからなる公知又は専用のコンピュータと特別なプログラムとを有する特別な装置である。処理部の少なくとも一部が集積回路などのハードウェアで構成されていてもよい。なお、情報共有装置210,220は、それぞれ、制御部114,124の制御のもと各処理を実行する。また、各演算過程で得られるデータは記憶部211,221に格納され、必要に応じて他の演算に用いられる。<処理>次に、第2実施形態の処理を例示する。[前処理]位数q、剰余環Zq、巡回群G1G2GT、生成元g1g1gT、双線形写像e:G1×G2→GT、ハッシュ関数HH1H2、マスタ秘密鍵秘密情報z∈Zq、g1zであるマスタ公開鍵公開情報P1及び/又はg2zであるマスタ公開鍵公開情報P2が定められる。第1情報共有装置210を利用するユーザの識別子IDA例えばIDA∈01、及び第2情報共有装置220を利用するユーザの識別子IDB例えばIDB∈01が定められる。識別子IDAに対して鍵公開情報AH1∈G1が設定され、識別子IDBに対して鍵公開情報BH2∈G2が設定される。ABはab∈ZqについてAg1a∈G1及びBg2b∈G2を満たす。さらにマスタ秘密鍵zを用い、Aに対応する第1情報共有装置210の秘密鍵秘密情報CAz∈G1と、Bに対応する第2情報共有装置220の秘密鍵秘密情報DBz∈G2とが設定される。これらの処理はシステム管理者などによってなされる。第2実施形態ではG1G2、g1g2、H1H2、P1P2とする。第2情報共有装置220の鍵B、第1情報共有装置210の秘密鍵C、マスタ公開鍵P1、識別子IDAIDBは第1情報共有装置210の記憶部211に格納される。第1情報共有装置210の鍵A、第2情報共有装置220の秘密鍵D、マスタ公開鍵P2、識別子IDAIDBは第2情報共有装置220の記憶部221に格納される。出力情報生成部216,226は、それぞれ生成元g1g2を用いて巡回群G1G2上の演算が可能なように構成され、共有情報生成部217,217は、双線形写像eの演算や巡回群G1G2上の演算が可能なように構成される。[鍵交換]次に、図4A及び図4Bを用い、第2実施形態の鍵交換処理を説明する。第1情報共有装置210図3の任意値生成部115がランダムな短期秘密鍵任意値tを前述の式のように生成し、生成した短期秘密鍵tを記憶部211に格納するステップS111。第1情報共有装置210の出力情報生成部216は、記憶部211から短期秘密鍵tを読み出し、短期秘密鍵tと巡回群G1の生成元g1とを用い、出力情報Tを以下の式のように生成し、生成した出力情報Tを記憶部211に格納するステップS212。Tg1t∈G1...記憶部211に格納された識別子IDAIDB及び出力情報Tは出力部212に送られ、出力部212はを出力するステップS213。出力されたは、ネットワークや可搬型記録媒体などを介して第2情報共有装置220に送られる。第2情報共有装置220の入力部222はの入力を受け付け、は記憶部221に格納されるステップS221。第2情報共有装置220の任意値生成部125がランダムな短期秘密鍵任意値yを前述の式のように生成し、生成した短期秘密鍵yを記憶部221に格納するステップS122。第2情報共有装置220の出力情報生成部226は、記憶部221から短期秘密鍵yを読み出し、短期秘密鍵yと巡回群G2の生成元g2とを用い、出力情報Yを以下の式のように生成し、生成した出力情報Yを記憶部221に格納するステップS223。Yg2y∈G2...記憶部221に格納された識別子IDAIDB、出力情報T及び出力情報Yは出力部223に送られ、出力部223はを出力するステップS224。出力されたは、ネットワークや可搬型記録媒体などを介して第1情報共有装置210に送られる。第1情報共有装置210の入力部212はの入力を受け付け、は記憶部211に格納されるステップS214。第1情報共有装置210の共有情報生成部217は、記憶部211から第2情報共有装置220の鍵Bg2b∈G2と出力情報Yと第1情報共有装置210の秘密鍵Cとマスタ公開鍵P1と短期秘密鍵tを読み込む。共有情報生成部217は、これらを用いて各演算式Vjj1J、Jは2以上の整数がそれぞれ表す共有情報Ujj1Jを生成する。共有情報Ujj1Jは、それぞれ、rrrrに対してgTzabrayrbtrty∈GTを満たす。本形態の演算式Vjは、それぞれ双線形写像e:G1×G2→GTからなり、少なくとも一部のmn∈1J又は式に変形可能な式である。UjeP1rtBeP1rtY...式に変形可能な式の例は以下の式などである。UjeP1rtYeP1rtB...UjetCrBetCrY...UjetCrYetCrB...少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である。好ましくは前述の条件1又は条件2を満たす。生成された共有情報Ujj1Jは記憶部211に格納されるステップS215。第1情報共有装置210の共有情報生成部217は、記憶部211から出力情報Yと短期秘密鍵tを読み込む。共有情報生成部217は、共有情報UJ1を以下の式のように生成し、生成した共有情報UJ1を記憶部211に格納するステップS216。UJ1Yt∈G2...第1情報共有装置210の鍵生成部218が、記憶部211から共有情報Ujj1Jと共有情報UJ1と識別子IDAIDBと出力情報TYとを読み込み、これらを含む情報をハッシュ関数Hに入力し、鍵KH...を生成し、生成した鍵Kを出力するステップS217。第2情報共有装置220の共有情報生成部227は、記憶部221から第1情報共有装置210の鍵Ag1a∈G1と出力情報Tと第2情報共有装置220の秘密鍵DBz∈G2とマスタ公開鍵P2と短期秘密鍵yを読み込む。共有情報生成部227は、これらを用いて各演算式Wjj1Jがそれぞれ表す共有情報Ujj1Jを生成する。共有情報Ujj1Jは、それぞれ、rrrrに対してgTzabrayrbtrty∈GTを満たす。本形態の演算式Wjは、それぞれ双線形写像e:G1×G2→GTからなり、少なくとも一部のmn∈1J又は式に変形可能な式である。UjeP2ryeP2ry...式に変形可能な式の例は以下の式などである。UjeP2ryeP2ry...UjeyDreyDr...UjeyDreyDr...少なくとも一部のmn∈1Jrrrとベクトルrrrとが一次独立である。好ましくは前述の条件1又は条件2を満たす。生成された共有情報Ujj1Jは記憶部221に格納されるステップS225。第2情報共有装置220の共有情報生成部227は、記憶部221から出力情報Tと短期秘密鍵yを読み込む。共有情報生成部227は、共有情報UJ1を以下の式のように生成し、生成した共有情報UJ1を記憶部221に格納するステップS226。UJ1Ty∈G1...第2情報共有装置220の鍵生成部228が、記憶部221から共有情報Ujj1Jと共有情報UJ1と識別子IDAIDBと出力情報TYとを読み込み、これらを含む情報をハッシュ関数Hに入力し、鍵KH...を生成し、生成した鍵Kを出力するステップS227。<本形態の特徴>双線形写像eの双線形性、巡回群Gが可換群であること、及び剰余環Zqが可換環であることから、式は以下のように変形できる。式などの式に変形可能な式も同様である。ただし、上付き添え字のpjはpjを表す。eP1rtBeP1rtYeazrtzg2beazrtzg2ygTrabzrtbzgTrayzrtyzgTzabrayrbtrtygTzpj同様に式は以下のように変形でき、式と等しいことが分かる。式などの式に変形可能な式も同様である。eP2ryeP2ryebzryzebzryzgTabzryzgTtbzryzgTzabrayrbtrtygTzpj巡回群G1G2が可換群であること、剰余環Zqが可換環であること、及び本形態ではG1G2及びg1g2あることから、式は以下のように変形でき、式と等しいことが分かる。Ytg2ytg1tyTyこのように第1情報共有装置210と第2情報共有装置220との間で共有情報Ujj1JUJ1を共有でき、鍵Kも共有できる。短期秘密鍵tyに応じて鍵Kの値が異なるため、第1情報共有装置210と第2情報共有装置220との間で上記の処理を行うたびに共有される鍵Kが変化する。またベクトルrrrとベクトルrrrとが一次独立であるため、前述のように中間者攻撃を防止できる。さらにハッシュ関数を用いることなく第1情報共有装置210と第2情報共有装置220とが共有情報Ujを共有できる。よって本形態では、高い安全性を確保しつつ、第1情報共有装置210と第2情報共有装置220とが低い演算量で共有情報を共有できる。第2実施形態の変形例次に、本発明のおける第2実施形態の変形例を説明する。この変形例は、G1とG2が同一であるか否か、g1とg2が同一であるか否か、H1とH2が同一であるか否か、P1とP2が同一であるか否かにかかわらず、実行可能なものである。以下では第1,2実施形態との相違点を中心に説明し、第1,2実施形態と共通する事項については説明を省略する。<構成>第2実施形態の変形例の構成を例示する。図5に例示するように、第2実施形態の変形例の情報共有システム3は、情報共有装置310と情報共有装置320とを有する。情報共有装置310は、記憶部311と入力部312と出力部313と制御部114と任意値生成部115と出力情報生成部316と共有情報生成部317と鍵生成部318とを有する。また、情報共有装置320は、記憶部321と入力部322と出力部323と制御部124と任意値生成部125と出力情報生成部326と共有情報生成部327と鍵生成部328とを有する。第1実施形態と同様、情報共有装置310,320は、CPU、RAM、ROMなどからなる公知又は専用のコンピュータと特別なプログラムとを有する特別な装置である。処理部の少なくとも一部が集積回路などのハードウェアで構成されていてもよい。なお、情報共有装置310,320は、それぞれ、制御部114,124の制御のもと各処理を実行する。また、各演算過程で得られるデータは記憶部311,321に格納され、必要に応じて他の演算に用いられる。<処理>次に、第2実施形態の変形例の処理を例示する。[前処理]G1G2、g1g2、H1H2、P1P2であってもなくてもよいこと以外、第2実施形態と同様である。[鍵交換]次に、図6A及び図6Bを用い、第3実施形態の鍵交換処理を説明する。任意値生成部115及び出力情報生成部316が前述のステップS111及びS212の処理をそれぞれ実行する。さらに第1情報共有装置310図5の出力情報生成部316が、記憶部311から短期秘密鍵tを読み出し、短期秘密鍵tと巡回群G2の生成元g2とを用い、出力情報T2を以下の式のように生成し、生成した出力情報Tを記憶部311に格納するステップS312。T2g2t∈G2...記憶部311に格納された識別子IDAIDB及び出力情報TT2は出力部312に送られ、出力部312はを出力するステップS313。出力されたは、ネットワークや可搬型記録媒体などを介して第2情報共有装置320に送られる。第2情報共有装置320の入力部222はの入力を受け付け、は記憶部321に格納されるステップS321。任意値生成部125及び出力情報生成部326が前述のステップS121及びS223の処理をそれぞれ実行する。さらに第2情報共有装置320の出力情報生成部326が、記憶部321から短期秘密鍵yを読み出し、短期秘密鍵yと巡回群G1の生成元g1とを用い、出力情報Y1を以下の式のように生成し、生成した出力情報Y1を記憶部321に格納するステップS323。Y1g1y∈G1...記憶部321に格納された識別子IDAIDB、出力情報TT2及び出力情報Y1Yは出力部323に送られ、出力部323はを出力するステップS324。出力されたは、ネットワークや可搬型記録媒体などを介して第1情報共有装置310に送られる。第1情報共有装置310の入力部312はの入力を受け付け、は記憶部311に格納されるステップS314。共有情報生成部317が前述のステップS215の処理を実行する。さらに共有情報生成部317は記憶部311から出力情報Y1Yと短期秘密鍵tを読み込む。共有情報生成部317は、共有情報1UJ12UJ1を以下の式のように生成し、生成した共有情報1UJ12UJ1を記憶部311に格納するステップS316。1UJ1Y1t∈G1...2UJ1Yt∈G2...第1情報共有装置310の鍵生成部318が、記憶部311から共有情報Ujj1Jと共有情報1UJ12UJ1と識別子IDAIDBと出力情報TT2Y1Yとを読み込み、これらを含む情報をハッシュ関数Hに入力し、鍵KH...を生成し、生成した鍵Kを出力するステップS317。共有情報生成部327は前述のステップS225の処理を実行する。さらに共有情報生成部327は、記憶部321から出力情報TT2と短期秘密鍵yを読み込む。共有情報生成部327は、共有情報1UJ12UJ1を以下の式のように生成し、生成した共有情報1UJ12UJ1を記憶部321に格納するステップS326。1UJ1Ty∈G1...2UJ1T2y∈G2...第2情報共有装置320の鍵生成部328が、記憶部321から共有情報Ujj1Jと共有情報1UJ12UJ1と識別子IDAIDBと出力情報TT2Y1Yとを読み込み、これらを含む情報をハッシュ関数Hに入力し、鍵KH...を生成し、生成した鍵Kを出力するステップS327。<本形態の特徴>第2実施形態と同様、第1情報共有装置310で生成された共有情報Ujj1Jと第2情報共有装置320で生成された共有情報Ujj1Jとはそれぞれ等しくなる。巡回群G1G2が可換群であること、及び剰余環Zqが可換環であることから、式は以下のように変形でき、式と等しいことが分かる。Y1tg1ytg1tyTy∈G1同様に、式は以下のように変形でき、式と等しいことが分かる。Ytg2ytg2tyT2y∈G2このように第1情報共有装置310と第2情報共有装置320との間で共有情報Ujj1J1UJ12UJ1を共有でき、鍵Kも共有できる。短期秘密鍵tyに応じて鍵Kの値が異なるため、第1情報共有装置310と第2情報共有装置320との間で上記の処理を行うたびに共有される鍵Kが変化する。またベクトルrrrとベクトルrrrとが一次独立であるため、前述のように中間者攻撃を防止できる。さらにハッシュ関数を用いることなく第1情報共有装置310と第2情報共有装置320とが共有情報Ujを共有できる。よって本形態では、高い安全性を確保しつつ、第1情報共有装置310と第2情報共有装置320とが低い演算量で共有情報を共有できる。その他の変形例等なお、本発明は上述の実施の形態に限定されるものではない。例えば、第1実施形態ではKHの計算によって、第2実施形態ではKHの計算によって、その変形例ではKHの計算によってそれぞれ鍵Kを生成した。しかし、すべての共有情報Ujを含む情報γとし、KHの計算によって鍵を生成するのであれば、その他の情報をγとして鍵Kを生成してもよい。ただし、第1情報共有装置と第2情報共有装置とでのγは同一の構成とする。例えば第1実施形態において、KH、KH、KH、KH、KHなどによって鍵Kが生成されてもよい。Ψは公開パラメータやアルゴリズムIDなどの付加情報である。またγを構成するビット列の結合順序に限定はない。また、各実施形態では、ハッシュ関数Hの出力ビット数をLとしたが、ハッシュ関数の出力ビット数がL以外であってもよい。さらに、各実施形態ではHがハッシュ関数である場合を例示したが、Hが共通鍵暗号関数、入力値をビット列に変換してからビット結合する関数など、どの他の関数をHとして用いてもかまわない。また、各実施形態では、共有情報Ujを用いて鍵Kを生成することとしたが、鍵Kを生成することなく、共有情報Ujそのものが暗号化処理その他の処理に利用されてもよい。また、上記の第1実施形態では、秘密情報aが第1情報共有装置の秘密鍵そのものであり、秘密情報bが第2情報共有装置の秘密鍵そのものであるとした。しかし、秘密情報abが秘密鍵そのものでなく、第1情報共有装置の秘密鍵の関数値をaとし、第2情報共有装置の秘密鍵の関数値をbとしてもよい。秘密鍵の関数値の例は、秘密鍵と定数又は変数との加算値、秘密鍵のべき乗値、秘密鍵のべき乗値と定数又は変数との加算値、秘密鍵の逆元値、秘密鍵の逆元値と定数又は変数との加算値、秘密鍵のハッシュ値などである。なお、定数や変数は、正であってもよいし負であってもよい。また、各実施形態において剰余環Zqの要素として説明した値が体の要素であってもよいし、整数であってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。なお、当該プログラムは、上述した特別なプログラムであってもよいし、特別なプログラムと汎用プログラムとの結合であってもよい。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、各形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"