"nを正の整数とし、1≦i≦nとし、Hi01→Zpをハッシュ関数とし、dieiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1a2∈Zpを情報共有装置UAの長期秘密鍵とし、A1ga1A2ga2を情報共有装置UAの長期公開鍵とし、b1b2∈Zpを情報共有装置UBの長期秘密鍵とし、B1gb1B2gb2を情報共有装置UBの長期公開鍵として、短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をXgxを計算する短期公開鍵生成部と、上記短期公開鍵Xを情報共有装置UBに送信する送信部と、短期公開鍵Yを上記情報共有装置UBから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1xdia1、σi1’xdia1、σi2xdia2、σi2’xdia2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をYgyを計算する短期公開鍵生成部と、上記短期公開鍵Yを情報共有装置UAに送信する送信部と、短期公開鍵Xを上記情報共有装置UAから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1yeib1、σi1’yeib2、σi2yeib1、σi2’yeib2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む情報共有システム。nを正の整数とし、1≦i≦nとし、Hi01→Zpをハッシュ関数とし、di1di2ei1ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置UAの長期秘密鍵とし、Agaを情報共有装置UAの長期公開鍵とし、b∈Zpを情報共有装置UBの長期秘密鍵とし、Bgaを情報共有装置UBの長期公開鍵として、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX1gx1X2gx2を計算する短期公開鍵生成部と、上記短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1x1di1a、σi1’x1di1a、σi2x2di2a、σi2’x2di2aを計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY1gy1Y2gy2を計算する短期公開鍵生成部と、上記短期公開鍵Y1Y2を情報共有装置UAに送信する送信部と、短期公開鍵X1X2を上記情報共有装置UAから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1y1ei1b、σi1’y2ei2b、σi2y1ei1b、σi2’y2ei2bを計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む情報共有システム。H01→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1a2∈Zpを情報共有装置UAの長期秘密鍵とし、A1ga1A2ga2を情報共有装置UAの長期公開鍵とし、b1b2∈Zpを情報共有装置UBの長期秘密鍵とし、B1gb1B2gb2を情報共有装置UBの長期公開鍵とし、UAを情報共有装置UAに対応する所定の値とし、UBを情報共有装置UBに対応する所定の値として、短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、x1Hx2Hを計算するハッシュ値計算部と、短期公開鍵X1gx1X2gx2を計算する短期公開鍵生成部と、上記短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信部と、σ1Y1a1、σ1’Y1a2、σ2Y2a1、σ2’Y2a2、σ3B1x1、σ3’B1x2、σ4B2x1、σ4’B2x2、σ5Y1x1、σ5’Y2x1、σ6Y1x2、σ6’Y2x2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、y1Hy2Hを計算するハッシュ値計算部と、短期公開鍵Y1gy1Y2gy2を計算する短期公開鍵生成部と、上記短期公開鍵Y1Y2を情報共有装置UAに送信する送信部と、短期公開鍵X1X2を上記情報共有装置UAから受信する受信部と、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1A1y1、σ1’A2y1、σ2A1y2、σ2’A2y2、σ3X1b1、σ3’X2b1、σ4X1b2、σ4’X2b2、σ5X1y1、σ5’X1y2、σ6X2y1、σ6’X2y2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む情報共有システム。H01→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置UAの長期秘密鍵とし、Agaを情報共有装置UAの長期公開鍵とし、b∈Zpを情報共有装置UBの長期秘密鍵とし、Bgbを情報共有装置UBの長期公開鍵とし、UAを情報共有装置UAに対応する所定の値とし、UBを情報共有装置UBに対応する所定の値として、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、x1H、x2Hを計算するハッシュ値計算部と、短期公開鍵X1gx1X2gx2を計算する短期公開鍵生成部と、上記短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信部と、σ1Y1a、σ1’Y2a、σ2Bx1、σ2’Bx2、σ3Y1x1、σ3’Y1x2、σ4Y2x1、σ4’Y2x2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成部と、y1H、y2Hを計算するハッシュ値計算部と、短期公開鍵Y1gy1Y2gy2を計算する短期公開鍵生成部と、上記短期公開鍵Y1Y2を情報共有装置UAに送信する送信部と、短期公開鍵X1X2を上記情報共有装置UAから受信する受信部と、σ1Ay1、σ1’Ay2、σ2X1b、σ2’X2b、σ3X1y1、σ3’X2y1、σ4X1y2、σ4’X2y2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む情報共有システム。請求項1の情報共有システムにおいて、UAを上記情報共有装置UAに対応する所定の値とし、UBを上記情報共有装置UBに対応する所定の値として、上記diHiであり、上記eiHiである、情報共有システム。請求項2の情報共有システムにおいて、UAを上記情報共有装置UAに対応する所定の値とし、UBを上記情報共有装置UBに対応する所定の値として、上記di1Hiであり、上記di2Hiであり、上記ei1Hiであり、上記ei2Hiである、情報共有システム。請求項1から6の情報共有システムにおいて、上記関数Fは、ハッシュ関数H’01→01である、情報共有システム。nを正の整数とし、1≦i≦nとし、Hi01→Zpをハッシュ関数とし、dieiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1a2∈Zpを情報共有装置UAの長期秘密鍵とし、A1ga1A2ga2を情報共有装置UAの長期公開鍵とし、b1b2∈Zpを情報共有装置UBの長期秘密鍵とし、B1gb1B2gb2を情報共有装置UBの長期公開鍵として、情報共有装置UAの短期秘密鍵生成部が、短期秘密鍵x∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UAの短期公開鍵生成部が、短期公開鍵をXgxを計算する短期公開鍵生成ステップと、情報共有装置UAの送信部が、上記短期公開鍵Xを情報共有装置UBに送信する送信ステップと、情報共有装置UAの受信部が、短期公開鍵Yを上記情報共有装置UBから受信する受信ステップと、情報共有装置UAの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1xdia1、σi1’xdia1、σi2xdia2、σi2’xdia2を計算する共有秘密情報計算ステップと、情報共有装置UAの共有情報生成部が、Fを計算する共有情報生成ステップと、情報共有装置UBの短期秘密鍵生成部が、短期秘密鍵y∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UBの短期公開鍵生成部が、短期公開鍵をYgyを計算する短期公開鍵生成ステップと、情報共有装置UBの送信部が、上記短期公開鍵Yを情報共有装置UAに送信する送信ステップと、情報共有装置UBの受信部が、短期公開鍵Xを上記情報共有装置UAから受信する受信ステップと、情報共有装置UBの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1yeib1、σi1’yeib2、σi2yeib1、σi2’yeib2を計算する共有秘密情報計算ステップと、情報共有装置UBの共有情報生成部が、Fを計算する共有情報生成ステップと、を含む情報共有方法。nを正の整数とし、1≦i≦nとし、Hi01→Zpをハッシュ関数とし、di1di2ei1ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置UAの長期秘密鍵とし、Agaを情報共有装置UAの長期公開鍵とし、b∈Zpを情報共有装置UBの長期秘密鍵とし、Bgaを情報共有装置UBの長期公開鍵として、情報共有装置UAの短期秘密鍵生成部が、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UAの短期公開鍵生成部が、短期公開鍵をX1gx1X2gx2を計算する短期公開鍵生成ステップと、情報共有装置UAの送信部が、上記短期公開鍵X1X2を情報共有装置UBに送信する送信ステップと、情報共有装置UAの受信部が、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信ステップと、情報共有装置UAの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1x1di1a、σi1’x1di1a、σi2x2di2a、σi2’x2di2aを計算する共有秘密情報計算ステップと、情報共有装置UAの共有情報生成部が、Fを計算する共有情報生成ステップと、情報共有装置UBの短期秘密鍵生成部が、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UBの短期公開鍵生成部が、短期公開鍵をY1gy1Y2gy2を計算する短期公開鍵生成ステップと、情報共有装置UBの送信部が、上記短期公開鍵Y1Y2を情報共有装置UAに送信する送信ステップと、情報共有装置UBの受信部が、短期公開鍵X1X2を上記情報共有装置UAから受信する受信ステップと、情報共有装置UBの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1y1ei1b、σi1’y2ei2b、σi2y1ei1b、σi2’y2ei2bを計算する共有秘密情報計算ステップと、情報共有装置UBの共有情報生成部が、Fを計算する共有情報生成ステップと、を含む情報共有方法。H01→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1a2∈Zpを情報共有装置UAの長期秘密鍵とし、A1ga1A2ga2を情報共有装置UAの長期公開鍵とし、b1b2∈Zpを情報共有装置UBの長期秘密鍵とし、B1gb1B2gb2を情報共有装置UBの長期公開鍵とし、UAを情報共有装置UAに対応する所定の値とし、UBを情報共有装置UBに対応する所定の値として、情報共有装置UAの短期秘密鍵生成部が、短期秘密鍵x∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UAのハッシュ値計算部が、x1Hx2Hを計算するハッシュ値計算ステップと、情報共有装置UAの短期公開鍵生成部が、短期公開鍵X1gx1X2gx2を計算する短期公開鍵生成ステップと、情報共有装置UAの送信部が、上記短期公開鍵X1X2を情報共有装置UBに送信する送信ステップと、情報共有装置UAの受信部が、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信ステップと、情報共有装置UAの共有秘密情報計算部が、σ1Y1a1、σ1’Y1a2、σ2Y2a1、σ2’Y2a2、σ3B1x1、σ3’B1x2、σ4B2x1、σ4’B2x2、σ5Y1x1、σ5’Y2x1、σ6Y1x2、σ6’Y2x2を計算する共有秘密情報計算ステップと、情報共有装置UAの共有情報生成部が、Fを計算する共有情報生成ステップと、情報共有装置UBの短期秘密鍵生成部が、短期秘密鍵y∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UBのハッシュ値計算部が、y1Hy2Hを計算するハッシュ値計算ステップと、情報共有装置UBの短期公開鍵生成部が、短期公開鍵Y1gy1Y2gy2を計算する短期公開鍵生成ステップと、情報共有装置UBの送信部が、上記短期公開鍵Y1Y2を情報共有装置UAに送信する送信ステップと、情報共有装置UBの受信部が、短期公開鍵X1X2を上記情報共有装置UAから受信する受信ステップと、情報共有装置UBの共有秘密情報計算部が、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1A1y1、σ1’A2y1、σ2A1y2、σ2’A2y2、σ3X1b1、σ3’X2b1、σ4X1b2、σ4’X2b2、σ5X1y1、σ5’X1y2、σ6X2y1、σ6’X2y2を計算する共有秘密情報計算ステップと、情報共有装置UBの共有情報生成部が、Fを計算する共有情報生成ステップと、を含む情報共有方法。H01→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置UAの長期秘密鍵とし、Agaを情報共有装置UAの長期公開鍵とし、b∈Zpを情報共有装置UBの長期秘密鍵とし、Bgbを情報共有装置UBの長期公開鍵とし、UAを情報共有装置UAに対応する所定の値とし、UBを情報共有装置UBに対応する所定の値として、情報共有装置UAの短期秘密鍵生成部が、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UAのハッシュ値計算部が、x1H、x2Hを計算するハッシュ値計算ステップと、情報共有装置UAの短期公開鍵生成部が、短期公開鍵X1gx1X2gx2を計算する短期公開鍵生成ステップと、情報共有装置UAの送信部が、上記短期公開鍵X1X2を情報共有装置UBに送信する送信ステップと、情報共有装置UAの受信部が、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信ステップと、情報共有装置UAの共有秘密情報計算部が、σ1Y1a、σ1’Y2a、σ2Bx1、σ2’Bx2、σ3Y1x1、σ3’Y1x2、σ4Y2x1、σ4’Y2x2を計算する共有秘密情報計算ステップと、情報共有装置UAの共有情報生成部が、Fを計算する共有情報生成ステップと、情報共有装置UBの短期秘密鍵生成部が、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UBのハッシュ値計算部が、y1H、y2Hを計算するハッシュ値計算ステップと、情報共有装置UBの短期公開鍵生成部が、短期公開鍵Y1gy1Y2gy2を計算する短期公開鍵生成ステップと、情報共有装置UBの送信部が、上記短期公開鍵Y1Y2を情報共有装置UAに送信する送信ステップと、情報共有装置UBの受信部が、短期公開鍵X1X2を上記情報共有装置UAから受信する受信ステップと、情報共有装置UBの共有秘密情報計算部が、σ1Ay1、σ1’Ay2、σ2X1b、σ2’X2b、σ3X1y1、σ3’X2y1、σ4X1y2、σ4’X2y2を計算する共有秘密情報計算ステップと、情報共有装置UBの共有情報生成部が、Fを計算する共有情報生成ステップと、を含む情報共有方法。nを正の整数とし、1≦i≦nとし、Hi01→Zpをハッシュ関数とし、dieiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1a2∈Zpを情報共有装置UAの長期秘密鍵とし、A1ga1A2ga2を情報共有装置UAの長期公開鍵とし、b1b2∈Zpを情報共有装置UBの長期秘密鍵とし、B1gb1B2gb2を情報共有装置UBの長期公開鍵として、短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をXgxを計算する短期公開鍵生成部と、上記短期公開鍵Xを情報共有装置UBに送信する送信部と、短期公開鍵Yを上記情報共有装置UBから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1xdia1、σi1’xdia1、σi2xdia2、σi2’xdia2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAである情報共有装置。nを正の整数とし、1≦i≦nとし、Hi01→Zpをハッシュ関数とし、di1di2ei1ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置UAの長期秘密鍵とし、Agaを情報共有装置UAの長期公開鍵とし、b∈Zpを情報共有装置UBの長期秘密鍵とし、Bgaを情報共有装置UBの長期公開鍵として、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX1gx1X2gx2を計算する短期公開鍵生成部と、上記短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1x1di1a、σi1’x1di1a、σi2x2di2a、σi2’x2di2aを計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAである情報共有装置。H01→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1a2∈Zpを情報共有装置UAの長期秘密鍵とし、A1ga1A2ga2を情報共有装置UAの長期公開鍵とし、b1b2∈Zpを情報共有装置UBの長期秘密鍵とし、B1gb1B2gb2を情報共有装置UBの長期公開鍵とし、UAを情報共有装置UAに対応する所定の値とし、UBを情報共有装置UBに対応する所定の値として、短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、x1Hx2Hを計算するハッシュ値計算部と、短期公開鍵X1gx1X2gx2を計算する短期公開鍵生成部と、上記短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信部と、σ1Y1a1、σ1’Y1a2、σ2Y2a1、σ2’Y2a2、σ3B1x1、σ3’B1x2、σ4B2x1、σ4’B2x2、σ5Y1x1、σ5’Y2x1、σ6Y1x2、σ6’Y2x2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAである情報共有装置。。H01→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置UAの長期秘密鍵とし、Agaを情報共有装置UAの長期公開鍵とし、b∈Zpを情報共有装置UBの長期秘密鍵とし、Bgbを情報共有装置UBの長期公開鍵とし、UAを情報共有装置UAに対応する所定の値とし、UBを情報共有装置UBに対応する所定の値として、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、x1H、x2Hを計算するハッシュ値計算部と、短期公開鍵X1gx1X2gx2を計算する短期公開鍵生成部と、上記短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を上記情報共有装置UBから受信する受信部と、σ1Y1a、σ1’Y2a、σ2Bx1、σ2’Bx2、σ3Y1x1、σ3’Y1x2、σ4Y2x1、σ4’Y2x2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAである情報共有装置。請求項12から15の何れかに記載の情報共有装置の各部としてコンピュータを機能させるためのプログラム。背景技術に記載した技術では、安全性を保証するためにいわゆるギャップ問題の難しさを仮定する必要がある。ギャップ問題とは、探索問題を解くために判定オラクルの利用を許した問題のことであり、一般にいわゆる探索問題よりも解きやすい問題となる。よって、ギャップ問題の難しさを仮定するよりも、探索問題の難しさを仮定した方が仮定を弱めることができるので望ましい。この発明の課題は、探索問題の難しさを仮定することにより安全性が保証される情報共有システム、方法、装置及びプログラムを提供することである。この発明の一態様による情報共有システムは、nを正の整数とし、1≦i≦nとし、Hi01→Zpをハッシュ関数とし、dieiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1a2∈Zpを情報共有装置UAの長期秘密鍵とし、A1ga1A2ga2を情報共有装置UAの長期公開鍵とし、b1b2∈Zpを情報共有装置UBの長期秘密鍵とし、B1gb1B2gb2を情報共有装置UBの長期公開鍵として、短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をXgxを計算する短期公開鍵生成部と、短期公開鍵Xを情報共有装置UBに送信する送信部と、短期公開鍵Yを情報共有装置UBから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1xdia1、σi1’xdia1、σi2xdia2、σi2’xdia2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をYgyを計算する短期公開鍵生成部と、短期公開鍵Yを情報共有装置UAに送信する送信部と、短期公開鍵Xを情報共有装置UAから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1yeib1、σi1’yeib2、σi2yeib1、σi2’yeib2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む。この発明の一態様による情報共有システムは、nを正の整数とし、1≦i≦nとし、Hi01→Zpをハッシュ関数とし、di1di2ei1ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置UAの長期秘密鍵とし、Agaを情報共有装置UAの長期公開鍵とし、b∈Zpを情報共有装置UBの長期秘密鍵とし、Bgaを情報共有装置UBの長期公開鍵として、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX1gx1X2gx2を計算する短期公開鍵生成部と、短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を情報共有装置UBから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1x1di1a、σi1’x1di1a、σi2x2di2a、σi2’x2di2aを計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY1gy1Y2gy2を計算する短期公開鍵生成部と、短期公開鍵Y1Y2を情報共有装置UAに送信する送信部と、短期公開鍵X1X2を情報共有装置UAから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1y1ei1b、σi1’y2ei2b、σi2y1ei1b、σi2’y2ei2bを計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む。この発明の一態様による情報共有システムは、H01→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1a2∈Zpを情報共有装置UAの長期秘密鍵とし、A1ga1A2ga2を情報共有装置UAの長期公開鍵とし、b1b2∈Zpを情報共有装置UBの長期秘密鍵とし、B1gb1B2gb2を情報共有装置UBの長期公開鍵とし、UAを情報共有装置UAに対応する所定の値とし、UBは情報共有装置UBに対応する所定の値とし、UAを情報共有装置UAに対応する所定の値とし、UBを情報共有装置UBに対応する所定の値として、短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、x1Hx2Hを計算するハッシュ値計算部と、短期公開鍵X1gx1X2gx2を計算する短期公開鍵生成部と、短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を情報共有装置UBから受信する受信部と、σ1Y1a1、σ1’Y1a2、σ2Y2a1、σ2’Y2a2、σ3B1x1、σ3’B1x2、σ4B2x1、σ4’B2x2、σ5Y1x1、σ5’Y2x1、σ6Y1x2、σ6’Y2x2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、y1Hy2Hを計算するハッシュ値計算部と、短期公開鍵Y1gy1Y2gy2を計算する短期公開鍵生成部と、短期公開鍵Y1Y2を情報共有装置UAに送信する送信部と、短期公開鍵X1X2を情報共有装置UAから受信する受信部と、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1A1y1、σ1’A2y1、σ2A1y2、σ2’A2y2、σ3X1b1、σ3’X2b1、σ4X1b2、σ4’X2b2、σ5X1y1、σ5’X1y2、σ6X2y1、σ6’X2y2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む。この発明の一態様による情報共有システムは、H01→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置UAの長期秘密鍵とし、Agaを情報共有装置UAの長期公開鍵とし、b∈Zpを情報共有装置UBの長期秘密鍵とし、Bgbを情報共有装置UBの長期公開鍵とし、UAを情報共有装置UAに対応する所定の値とし、UBを情報共有装置UBに対応する所定の値として、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、x1H、x2Hを計算するハッシュ値計算部と、短期公開鍵X1gx1X2gx2を計算する短期公開鍵生成部と、短期公開鍵X1X2を情報共有装置UBに送信する送信部と、短期公開鍵Y1Y2を情報共有装置UBから受信する受信部と、σ1Y1a、σ1’Y2a、σ2Bx1、σ2’Bx2、σ3Y1x1、σ3’Y1x2、σ4Y2x1、σ4’Y2x2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成部と、y1H、y2Hを計算するハッシュ値計算部と、短期公開鍵Y1gy1Y2gy2を計算する短期公開鍵生成部と、短期公開鍵Y1Y2を情報共有装置UAに送信する送信部と、短期公開鍵X1X2を情報共有装置UAから受信する受信部と、σ1Ay1、σ1’Ay2、σ2X1b、σ2’X2b、σ3X1y1、σ3’X2y1、σ4X1y2、σ4’X2y2を計算する共有秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む。探索問題の難しさを仮定して安全性を保証することができる。以下、図面を参照してこの発明の一実施形態を説明する。[第一実施形態]まず、第一実施形態のアルゴリズムである長期鍵二重化HMQVについて説明する。長期鍵二重化HMQV長期鍵二重化HMQVは、次のような方式である。長期鍵二重化HMQVの概要を図7に示す。<公開パラメータ>Gをkbitの素数位数pの巡回群、gをGの生成元、Hi01→Zp及びH’01→01kをハッシュ関数とする。kは、セキュリティパラメータであり正の整数である。また、1≦i≦nでありnは正の整数である。<鍵生成>鍵生成者は、ユーザUAに対して、長期秘密鍵a1a2∈Zpを計算し、長期公開鍵A1ga1A2ga2を公開する。ga1の右肩のa1はa1を意味する。このように、この明細書、特許請求の範囲及び図面において、ある文字の上付きの文字及び数字の一部がその上付きの中で更に上付き又は下付きである場合がある点に留意する。同様に、ある文字の下付きの文字及び数字の一部がその下付きの中で更に上付き又は下付きである場合がある点に留意する。鍵生成者は、同様にユーザUBに対して、長期秘密鍵b1b2∈Zpを計算し、長期公開鍵B1gb1B2gb2を公開する。<鍵交換>長期秘密鍵a1a2をもつユーザUAと、長期秘密鍵b1b2をもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。1.ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、短期公開鍵をXgxとし、ユーザUBに送る。2.ユーザUBは、Xを受信し、短期秘密鍵y∈Zpをランダムに選び、短期公開鍵をYgyとし、ユーザUAに送る。ユーザUBは、1≦i≦nについて、diHi、eiHi、σi1yeib1、σi1’yeib2、σi2yeib1、σi2’yeib2を計算し、共有情報KH’を得る。ただし、nは正の整数。diとeiは、diHi、eiHi以外の事前に定められた定数であっても良い。3.ユーザUAは、Yを受信し、1≦i≦nについて、diHi、eiHi、σi1xdia1、σi1’xdia1、σi2xdia2、σi2’xdia2を計算し、共有情報KH’を得る。diとeiは、diHi、eiHi以外の事前に定められた定数であっても良い。共有秘密情報は両方のユーザが計算したσi1gσi1’gσi2gσi2’gから得られるので、両者で計算した共有情報Kは一致する。次に、上記長期鍵二重化HMQVの欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図1に例示するように、情報共有装置UA及び情報共有装置UBから構成される。情報共有装置UAが長期鍵二重化HMQVの欄で説明したユーザUAに対応し、情報共有装置UBが長期鍵二重化HMQVの欄で説明したユーザUBに対応する。情報共有装置UAは図4に例示した処理を行い、情報共有装置UBは図5に例示した処理を行う。情報共有装置UAは、図2に示すように、記憶部10、短期秘密鍵生成部11、短期公開鍵生成部12、送信部13、受信部14、共有秘密情報生成部15、共有情報生成部16を例えば含む。情報共有装置UBは、図3に示すように、記憶部20、短期秘密鍵生成部21、短期公開鍵生成部22、送信部23、受信部24、共有秘密情報生成部25、共有情報生成部26を例えば含む。情報共有の前に、ハッシュ関数Hi、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部10及び記憶部20に記憶されているものとする。また、情報共有の前に、情報共有装置UAには、長期秘密鍵a1a2及び長期公開鍵A1A2が予め定められ、必要に応じて記憶部10に記憶されているものとする。同様に、情報共有の前に、情報共有装置UBには、長期秘密鍵b1b2及び長期公開鍵B1B2が予め定められ、必要に応じて記憶部10に記憶されているものとする。長期秘密鍵a1a2b1b2及び長期公開鍵A1A2B1B2の計算は、鍵生成装置3図1により行われる。これらの記憶部10及び20に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。情報共有装置UAの短期秘密鍵生成部11図2は、短期秘密鍵x∈Zpを生成するステップA1。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵xとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵xは、短期公開鍵生成部12に送信される。情報共有装置UAの短期公開鍵生成部12は、短期秘密鍵xを用いて短期公開鍵Xgxを計算するステップA2。短期公開鍵Xは、共有秘密情報生成部15及び送信部13に送信される。情報共有装置UAの送信部13は、短期公開鍵Xを情報共有装置UBに送信するステップA3。情報共有装置UBの短期秘密鍵生成部21図3は、短期秘密鍵y∈Zpを生成するステップB1。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵yとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、短期公開鍵生成部22に送信される。情報共有装置UBの短期公開鍵生成部22は、短期秘密鍵yを用いて短期公開鍵Ygyを計算するステップB2。短期公開鍵Yは、共有秘密情報生成部25及び送信部23に送信される。情報共有装置UBの送信部23は、短期公開鍵Yを情報共有装置UAに送信するステップB4。情報共有装置UBの受信部24は、短期公開鍵Xを情報共有装置UAから受信するステップB5。情報共有装置UBの共有秘密情報生成部25は、1≦i≦nのそれぞれのiについての共有秘密情報σi1yeib1、σi1’yeib2、σi2yeib1、σi2’yeib2を計算するステップB6。すなわち、計4n個の共有秘密情報σ11,σ11’σ21,σ21’...σ1n,σ1n’σ2n,σ2n’を計算する。計算された共有秘密情報は、共有情報生成部26に送信される。ここで、di及びeiは、所定の定数である。例えば、diHieiHiである。第一実施形態の情報共有装置UBは、補助情報diHi、eiHiを計算する補助情報生成部28を有していても良い。情報共有装置UBの共有情報生成部26は、H’を計算して、その計算結果を共有情報KとするステップB7。この共有情報Kは、例えば認証鍵として用いられる。情報共有装置UAの受信部14図2は、短期公開鍵Yを情報共有装置UBから受信するステップA4。情報共有装置UAの共有秘密情報生成部15は、1≦i≦nのそれぞれのiについてのσi1xdia1、σi1’xdia1、σi2xdia2、σi2’xdia2を計算するステップA5。すなわち、計4n個の共有秘密情報σ11,σ11’σ21,σ21’...σ1n,σ1n’σ2n,σ2n’を計算する。計算された共有秘密情報は、共有情報生成部16に送信される。ここで、di及びeiは、所定の定数である。例えば、diHieiHiである。第一実施形態の情報共有装置UAは、補助情報diHi、eiHiを計算する補助情報生成部18を有していても良い。情報共有装置UAの共有情報生成部16は、H’を計算して、その計算結果を共有情報KとするステップA6。この共有情報Kは、例えば認証鍵として用いられる。このようにして、情報共有が行われる。[第二実施形態]まず、第二実施形態のアルゴリズムである長期鍵二重化HMQVについて説明する。短期鍵二重化HMQV短期鍵二重化HMQVは、次のような方式である。短期鍵二重化HMQVの概要を図8に示す。<公開パラメータ>Gをkbitの素数位数pの巡回群、gをGの生成元、Hi01→Zp及びH’01→01kをハッシュ関数とする。kは、セキュリティパラメータであり正の整数である。また、1≦i≦nでありnは正の整数である。<鍵生成>鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵Agaを公開する。<鍵交換>長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。1.ユーザUAは、短期秘密鍵x1x2∈Zpをランダムに選び、短期公開鍵をX1gx1X2gx2とし、ユーザUBに送る。2.ユーザUBは、X1X2を受信し、短期秘密鍵y1y2∈Zpをランダムに選び、短期公開鍵をY1gy1Y2gy2とし、ユーザUAに送る。ユーザUBは、1≦i≦nについて、di1Hi、di2Hi、ei1Hi、ei2Hi、σi1y1ei1b、σi1’y2ei2b、σi2y1ei1b、σi2’y2ei2bを計算し、共有情報KH’を得る。ただし、nは正の整数。di1di2ei1ei2は、di1Hi、di2Hi、ei1Hi、ei2Hi以外の事前に定められた定数であっても良い。3.ユーザUAは、Y1Y2を受信し、1≦i≦nについて、di1Hi、di2Hi、ei1Hi、ei2Hi、σi1x1di1a、σi1’x1di1a、σi2x2di2a、σi2’x2di2aを計算し、共有鍵KH’を得る。ただし、nは正の整数。di1di2ei1ei2は、di1Hi、di2Hi、ei1Hi、ei2Hi以外の事前に定められた定数であっても良い。共有秘密情報は両方のユーザが計算したσi1gσi1’gσi2gσi2’gから得られるので、両者で計算した共有情報Kは一致する。次に、上記短期鍵二重化HMQVの欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図1に例示するように、情報共有装置UA及び情報共有装置UBから構成される。情報共有装置UAが短期鍵二重化HMQVの欄で説明したユーザUAに対応し、情報共有装置UBが短期鍵二重化HMQVの欄で説明したユーザUBに対応する。情報共有装置UAは図4に例示した処理を行い、情報共有装置UBは図5に例示した処理を行う。情報共有装置UAは、図2に示すように、記憶部10、短期秘密鍵生成部11、短期公開鍵生成部12、送信部13、受信部14、共有秘密情報生成部15、共有情報生成部16を例えば含む。情報共有装置UBは、図3に示すように、記憶部20、短期秘密鍵生成部21、短期公開鍵生成部22、送信部23、受信部24、共有秘密情報生成部25、共有情報生成部26を例えば含む。情報共有の前に、ハッシュ関数Hi、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部10及び記憶部20に記憶されているものとする。また、情報共有の前に、情報共有装置UAには、長期秘密鍵a及び長期公開鍵Aが予め定められ、必要に応じて記憶部10に記憶されているものとする。同様に、情報共有の前に、情報共有装置UBには、長期秘密鍵b及び長期公開鍵Bが予め定められ、必要に応じて記憶部10に記憶されているものとする。長期秘密鍵ab及び長期公開鍵ABの計算は、鍵生成装置3図1により行われる。これらの記憶部10及び20に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。情報共有装置UAの短期秘密鍵生成部11図2は、短期秘密鍵x1x2∈Zpを生成するステップA1。例えば、Zpの中から一様ランダムに2つの元を選びそれぞれ短期秘密鍵x1x2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵x1x2は、短期公開鍵生成部12に送信される。情報共有装置UAの短期公開鍵生成部12は、短期秘密鍵x1x2を用いて短期公開鍵X1gx1X2gx2を計算するステップA2。短期公開鍵X1X2は、共有秘密情報生成部15及び送信部13に送信される。情報共有装置UAの送信部13は、短期公開鍵X1X2を情報共有装置UBに送信するステップA3。情報共有装置UBの短期秘密鍵生成部21図3は、短期秘密鍵y1y2∈Zpを生成するステップB1。例えば、Zpの中から一様ランダムに2つの元を選びそれぞれ短期秘密鍵y1y2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、短期公開鍵生成部22に送信される。情報共有装置UBの短期公開鍵生成部22は、短期秘密鍵y1y2を用いて短期公開鍵Y1gy1Y2gy2を計算するステップB2。短期公開鍵Y1gy1Y2gy2は、共有秘密情報生成部25及び送信部23に送信される。情報共有装置UBの送信部23は、短期公開鍵Y1Y2を情報共有装置UAに送信するステップB4。情報共有装置UBの受信部24は、短期公開鍵X1X2を情報共有装置UAから受信するステップB5。情報共有装置UBの共有秘密情報生成部25は、1≦i≦nのそれぞれのiについての共有秘密情報σi1y1ei1b、σi1’y2ei2b、σi2y1ei1b、σi2’y2ei2bを計算するステップB6。すなわち、計4n個の共有秘密情報σ11,σ11’σ21,σ21’...σ1n,σ1n’σ2n,σ2n’を計算する。計算された共有秘密情報は、共有情報生成部26に送信される。ここで、di1di2ei1ei2は、所定の定数である。例えば、di1Hi、di2Hi、ei1Hi、ei2Hiである。第二実施形態の情報共有装置UBは、補助情報diHi、eiHiを計算する補助情報生成部28を有していても良い。情報共有装置UBの共有情報生成部26は、H’を計算して、その計算結果を共有情報KとするステップB7。この共有情報Kは、例えば認証鍵として用いられる。情報共有装置UAの受信部14図2は、短期公開鍵Yを情報共有装置UBから受信するステップA4。情報共有装置UAの共有秘密情報生成部15は、1≦i≦nのそれぞれのiについてのσi1x1di1a、σi1’x1di1a、σi2x2di2a、σi2’x2di2aを計算するステップA5。すなわち、計4n個の共有秘密情報σ11,σ11’σ21,σ21’...σ1n,σ1n’σ2n,σ2n’を計算する。計算された共有秘密情報は、共有情報生成部16に送信される。ここで、di1di2ei1ei2は、所定の定数である。例えば、di1Hi、di2Hi、ei1Hi、ei2Hiである。第二実施形態の情報共有装置UAは、補助情報di1Hi、di2Hi、ei1Hi、ei2Hiを計算する補助情報生成部18を有していても良い。情報共有装置UAの共有情報生成部16は、H’を計算して、その計算結果を共有情報KとするステップA6。この共有情報Kは、例えば認証鍵として用いられる。このようにして、情報共有が行われる。[第三実施形態]まず、第三実施形態のアルゴリズムである長期鍵二重化NAXOSについて説明する。長期鍵二重化NAXOS長期鍵二重化NAXOSは、次のような方式である。長期鍵二重化NAXOSの概要を図9に示す。<公開パラメータ>Gをkbitの素数位数pの巡回群、gをGの生成元、H01→Zp及びH’01→01kをハッシュ関数とする。<鍵生成>鍵生成者は、ユーザUAに対して、長期秘密鍵a1a2∈Zpを計算し、長期公開鍵A1ga1A2ga2を公開する。鍵生成者は、同様にユーザUBに対して、長期秘密鍵b1b2∈Zpを計算し、長期公開鍵B1gb1B2gb2を公開する。<鍵交換>長期秘密鍵a1a2をもつユーザUAと、長期秘密鍵b1b2をもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。1.ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、x1Hx2Hを計算し、短期公開鍵をX1gx1X2gx2とし、ユーザUBに送る。2.ユーザUBは、X1X2を受信し、短期秘密鍵y∈Zpをランダムに選び、y1Hy2Hを計算し、短期公開鍵をY1gy1Y2gy2とし、ユーザUAに送る。ユーザUBは、σ1A1y1、σ1’A2y1、σ2A1y2、σ2’A2y2、σ3X1b1、σ3’X2b1、σ4X1b2、σ4’X2b2、σ5X1y1、σ5’X1y2、σ6X2y1、σ6’X2y2を計算し、KH’を得る。UAは、ユーザUA情報共有装置UAに対応する所定の値である。同様に、UBは、ユーザUB情報共有装置UBに対応する所定の値である。3.ユーザUAは、Yを受信し、σ1Y1a1、σ1’Y1a2、σ2Y2a1、σ2’Y2a2、σ3B1x1、σ3’B1x2、σ4B2x1、σ4’B2x2、σ5Y1x1、σ5’Y2x1、σ6Y1x2、σ6’Y2x2を計算し、共有情報KH’を得る。共有秘密情報は両方のユーザが計算したσ1gy1a1σ1’gy1a2σ2gy2a1σ2’gy2a2σ3gx1b1σ3’gx1b2σ4gx2b1σ4’gx2b2σ5gx1y1σ5’gx1y2σ6gx2y1σ6’gx2y2から得られるので、両者で計算した共有鍵Kは一致する。次に、上記長期鍵二重化NAXOSの欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図1に例示するように、情報共有装置UA及び情報共有装置UBから構成される。情報共有装置UAが長期鍵二重化NAXOSの欄で説明したユーザUAに対応し、情報共有装置UBが長期鍵二重化NAXOSの欄で説明したユーザUBに対応する。情報共有装置UAは図4に例示した処理を行い、情報共有装置UBは図5に例示した処理を行う。情報共有装置UAは、図2に示すように、記憶部10、短期秘密鍵生成部11、短期公開鍵生成部12、送信部13、受信部14、共有秘密情報生成部15、共有情報生成部16、破線で示したハッシュ値計算部17を例えば含む。情報共有装置UBは、図3に示すように、記憶部20、短期秘密鍵生成部21、短期公開鍵生成部22、送信部23、受信部24、共有秘密情報生成部25、共有情報生成部26、破線で示したハッシュ値計算部27を例えば含む。情報共有の前に、ハッシュ関数H、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部10及び記憶部20に記憶されているものとする。また、情報共有の前に、情報共有装置UAには、長期秘密鍵a1a2及び長期公開鍵A1A2が予め定められ、必要に応じて記憶部10に記憶されているものとする。同様に、情報共有の前に、情報共有装置UBには、長期秘密鍵b1b2及び長期公開鍵B1B2が予め定められ、必要に応じて記憶部10に記憶されているものとする。長期秘密鍵a1a2b1b2及び長期公開鍵A1A2B1B2の計算は、鍵生成装置3図1により行われる。これらの記憶部10及び20に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。情報共有装置UAの短期秘密鍵生成部11図2は、短期秘密鍵x∈Zpを生成するステップA1。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵xとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵xは、ハッシュ値計算部17に送信される。情報共有装置UAのハッシュ値計算部17は、x1Hx2Hを計算するステップA7。計算されたハッシュ値x1x2は、短期公開鍵生成部12及び共有秘密情報生成部15に送信される。情報共有装置UAの短期公開鍵生成部12は、計算されたハッシュ値x1x2をそれぞれ用いて短期公開鍵X1gx1X2gx2を計算するステップA2。短期公開鍵X1X2は、共有秘密情報生成部15及び送信部13に送信される。情報共有装置UAの送信部13は、短期公開鍵X1X2を情報共有装置UBに送信するステップA3。情報共有装置UBの短期秘密鍵生成部21図3は、短期秘密鍵y∈Zpを生成するステップB1。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵yとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、ハッシュ値計算部27に送信される。情報共有装置UBのハッシュ値計算部27は、y1Hy2Hを計算する。計算されたハッシュ値y1y2は、短期公開鍵生成部22及び共有秘密情報生成部25に送信される。情報共有装置UBの短期公開鍵生成部22は、ハッシュ値y1y2をそれぞれ用いて短期公開鍵Y1gy1Y2gy2を計算するステップB7。短期公開鍵Y1Y2は、共有秘密情報生成部25及び送信部23に送信される。情報共有装置UBの送信部23は、短期公開鍵Y1Y2を情報共有装置UAに送信するステップB4。情報共有装置UBの受信部24は、短期公開鍵X1X2を情報共有装置UAから受信するステップB5。情報共有装置UBの共有秘密情報生成部25は、12個の共有秘密情報σ1A1y1、σ1’A2y1、σ2A1y2、σ2’A2y2、σ3X1b1、σ3’X2b1、σ4X1b2、σ4’X2b2、σ5X1y1、σ5’X1y2、σ6X2y1、σ6’X2y2を計算するステップB6。計算された共有秘密情報は、共有情報生成部26に送信される。情報共有装置UBの共有情報生成部26は、H’を計算して、その計算結果を共有情報KとするステップB7。この共有情報Kは、例えば認証鍵として用いられる。情報共有装置UAの受信部14図2は、短期公開鍵Y1Y2を情報共有装置UBから受信するステップA4。情報共有装置UAの共有秘密情報生成部15は、σ1Y1a1、σ1’Y1a2、σ2Y2a1、σ2’Y2a2、σ3B1x1、σ3’B1x2、σ4B2x1、σ4’B2x2、σ5Y1x1、σ5’Y2x1、σ6Y1x2、σ6’Y2x2を計算するステップA5。計算された共有秘密情報は、共有情報生成部16に送信される。情報共有装置UAの共有情報生成部16は、H’を計算して、その計算結果を共有情報KとするステップA6。この共有情報Kは、例えば認証鍵として用いられる。このようにして、情報共有が行われる。[第四実施形態]まず、第四実施形態のアルゴリズムである短期鍵二重化NAXOSについて説明する。短期鍵二重化NAXOS短期鍵二重化NAXOSは、次のような方式である。短期鍵二重化NAXOSの概要を図10に示す。<公開パラメータ>Gをkbitの素数位数pの巡回群、gをGの生成元、H01→Zp及びH’01→01kをハッシュ関数とする。<鍵生成>鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵Agaを公開する。同様に、鍵生成者は、ユーザUBに対して、長期秘密鍵b∈Zpを計算し、長期公開鍵Bgbを公開する。<鍵交換>長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。1.ユーザUAは、短期秘密鍵x1x2∈Zpをランダムに選び、x1H、x2Hを計算し、短期公開鍵をX1gx1X2gx2とし、ユーザUBに送る。2.ユーザUBは、X1X2を受信し、短期秘密鍵y1y2∈Zpをランダムに選び、y1H、y2Hを計算し、短期公開鍵をY1gy1Y2gy2とし、ユーザUAに送る。ユーザUBは、σ1Ay1、σ1’Ay2、σ2X1b、σ2’X2b、σ3X1y1、σ3’X2y1、σ4X1y2、σ4’X2y2を計算し、共有情報KH’を得る。UAは、ユーザUA情報共有装置UAに対応する所定の値である。同様に、UBは、ユーザUB情報共有装置UBに対応する所定の値である。3.ユーザUAは、Y1Y2を受信し、σ1Y1a、σ1’Y2a、σ2Bx1、σ2’Bx2、σ3Y1x1、σ3’Y1x2、σ4Y2x1、σ4’Y2x2を計算し、共有情報KH′を得る。共有秘密情報は両方のユーザが計算したσ1gy1aσ1’gy2aσ2gx1bσ2’gx2bσ3gx1y1σ3’gx2y1σ4gx1y2σ4’gx2y2から得られるので、両者で計算した共有情報Kは一致する。次に、上記短期鍵二重化NAXOSの欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図1に例示するように、情報共有装置UA及び情報共有装置UBから構成される。情報共有装置UAが短期鍵二重化NAXOSの欄で説明したユーザUAに対応し、情報共有装置UBが短期鍵二重化NAXOSの欄で説明したユーザUBに対応する。情報共有装置UAは図4に例示した処理を行い、情報共有装置UBは図5に例示した処理を行う。情報共有装置UAは、図2に示すように、記憶部10、短期秘密鍵生成部11、短期公開鍵生成部12、送信部13、受信部14、共有秘密情報生成部15、共有情報生成部16、破線で示したハッシュ値計算部17を例えば含む。情報共有装置UBは、図3に示すように、記憶部20、短期秘密鍵生成部21、短期公開鍵生成部22、送信部23、受信部24、共有秘密情報生成部25、共有情報生成部26、破線で示したハッシュ値計算部27を例えば含む。情報共有の前に、ハッシュ関数H、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部10及び記憶部20に記憶されているものとする。また、情報共有の前に、情報共有装置UAには、長期秘密鍵a及び長期公開鍵Aが予め定められ、必要に応じて記憶部10に記憶されているものとする。同様に、情報共有の前に、情報共有装置UBには、長期秘密鍵b及び長期公開鍵Bが予め定められ、必要に応じて記憶部10に記憶されているものとする。長期秘密鍵ab及び長期公開鍵ABの計算は、鍵生成装置3図1により行われる。これらの記憶部10及び20に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。情報共有装置UAの短期秘密鍵生成部11図2は、短期秘密鍵x1x2∈Zpを生成するステップA1。例えば、Zpの中から一様ランダムに2つの元を選びそれぞれ短期秘密鍵x1x2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵x1x2は、ハッシュ値計算部17に送信される。情報共有装置UAのハッシュ値計算部17は、x1Hx2Hを計算するステップA7。計算されたハッシュ値x1x2は、短期公開鍵生成部12及び共有秘密情報生成部15に送信される。情報共有装置UAの短期公開鍵生成部12は、計算されたハッシュ値x1x2をそれぞれ用いて短期公開鍵X1gx1X2gx2を計算するステップA2。短期公開鍵X1X2は、共有秘密情報生成部15及び送信部13に送信される。情報共有装置UAの送信部13は、短期公開鍵X1X2を情報共有装置UBに送信するステップA3。情報共有装置UBの短期秘密鍵生成部21図3は、短期秘密鍵y1y2∈Zpを生成するステップB1。例えば、Zpの中から一様ランダムに2つの元を選び短期秘密鍵y1y2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵y1y2は、ハッシュ値計算部27に送信される。情報共有装置UBのハッシュ値計算部27は、y1Hy2Hを計算する。計算されたハッシュ値y1y2は、短期公開鍵生成部22及び共有秘密情報生成部25に送信される。情報共有装置UBの短期公開鍵生成部22は、ハッシュ値y1y2をそれぞれ用いて短期公開鍵Y1gy1Y2gy2を計算するステップB7。短期公開鍵Y1Y2は、共有秘密情報生成部25及び送信部23に送信される。情報共有装置UBの送信部23は、短期公開鍵Y1Y2を情報共有装置UAに送信するステップB4。情報共有装置UBの受信部24は、短期公開鍵X1X2を情報共有装置UAから受信するステップB5。情報共有装置UBの共有秘密情報生成部25は、計8個の共有秘密情報σ1Ay1、σ1’Ay2、σ2X1b、σ2’X2b、σ3X1y1、σ3’X2y1、σ4X1y2、σ4’X2y2を計算するステップB6。計算された共有秘密情報は、共有情報生成部26に送信される。情報共有装置UBの共有情報生成部26は、H’を計算して、その計算結果を共有情報KとするステップB7。この共有情報Kは、例えば認証鍵として用いられる。情報共有装置UAの受信部14図2は、短期公開鍵Y1Y2を情報共有装置UBから受信するステップA4。情報共有装置UAの共有秘密情報生成部15は、σ1Y1a1、σ1’Y1a2、σ2Y2a1、σ2’Y2a2、σ3B1x1、σ3’B1x2、σ4B2x1、σ4’B2x2、σ5Y1x1、σ5’Y2x1、σ6Y1x2、σ6’Y2x2を計算するステップA5。計算された共有秘密情報は、共有情報生成部16に送信される。情報共有装置UAの共有情報生成部16は、H’を計算して、その計算結果を共有情報KとするステップA6。この共有情報Kは、例えば認証鍵として用いられる。このようにして、情報共有が行われる。[変形例等]情報共有装置UAの各部間のデータのやり取りは直接行われてもよいし、記憶部10を介して行われてもよい。同様に、情報共有装置UBの各部間のデータのやり取りは直接行われてもよいし、記憶部20を介して行われてもよい。上記の例では、共有情報生成部16及び共有情報生成部26は、ハッシュ関数H’を用いたが、任意の予め定められた関数Fを用いて共有情報を求めてもよい。すなわち、第一実施形態及び第二実施形態においてはFを計算してその計算結果を共有情報kとしても良いし、第三実施形態においてはFを計算してその計算結果を共有情報kとしても良いし、第四実施形態においては、Fを計算してその計算結果を共有情報kとしても良い。その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。[安全性の証明]このように、長期秘密鍵又は短期秘密鍵を二重化し、共有情報を計算するための共有秘密情報であって長期秘密鍵又は短期秘密鍵に由来する共有秘密情報を短期秘密鍵ごとに計算する。これにより、ギャップ問題の難しさを仮定することなく探索問題の難しさをのみを仮定することで安全性を証明することができる。以下、その安全性の証明の概要を説明する。まず、探索問題探索DiffieHellman問題及びギャップ問題ギャップDiffieHellman問題の定義を説明する。探索DiffieHellman問題:κをセキュリティパラメータとし、pをκビット素数とする。Gをgを生成元とする位数pの巡回群とする。DiffieHellman関数CDHG2→GをCDHguvとして定義し、判定DiffieHellman述語オラクルDDHG3→01をを入力としuvwmodpが成り立つとき1を出力し、そうでなければ0を出力する関数として定義する。解答者Sは、一様ランダムに選ばれたUguVgv∈Gと判定DiffieHellman述語オラクルDDHへのアクセスを入力され、CDHの出力を試みる。解答者Sのアドバンテージを次のように定義する。ADVGDHPrUV∈GSDDHCDHADVGDHが無視できない確率であるとき、解答者SはギャップDiffieHellman問題を解いたという。ギャップ問題は上記のように判定オラクルのヒント付きの探索問題とみなせるので、ギャップ問題の方が真に易しい。鍵交換方式情報共有方式の安全性証明を行う際は、ギャップ問題、もしくは探索問題を解くことが難しいことを仮定すると、情報共有方式への攻撃者が存在しないことを示す必要がある。これは、対偶を取ることにより、情報共有方式への攻撃者が存在すると仮定すると、問題を解く解答者を構成できることを示すことと同値である。従って、安全性証明では実際に攻撃者から解答者を構成する必要がある。そのためには解答者は攻撃者を実際の攻撃環境と見分けがつかないように動作させなければならない。HMQVでは、攻撃者が出力したσに対してσyebを解答者が検証し、結果に応じて動作を変えねばならない。しかし、解答者はyとbを知ることができないので、自分で上記の検証を行うことができない。よって、判定オラクルにを聞き、検証式が成り立つかどうかの答えをもらうことによって証明を行う。このためギャップ問題の難しさを仮定する必要がある。一方、第一実施形態の長期鍵二重化HMQVでは、任意のsとrについて、解答者は証明中でa2sra1と設定することでσ1yeb1、σ1’yeb2、σ2yeb1、σ2’yeb2の検証をyとb1b2を知ること無しに行うことができる。具体的には、σ1rσ2sの真理値がσ1yeb1∧σ2yeb1の真理値と一致することを利用して検証を行う。このテクニックは落とし戸試験と呼ばれる。σ1rσ2sは解答者の持つ情報のみで検証できるため、判定オラクルは不要であり、ギャップ問題の難しさを仮定する必要が無くなる。同様に、σ1’rσ2’sの落とし戸試験を行うことで、σ1’yeb2∧σ2’yeb2の検証を行うことができる。第二実施形態の短期鍵二重化HMQVでも同様に、シミュレータは証明中でx2srx1と設定し、σ1rσ2sとσ1’rσ2’sの落とし戸試験を行うことによって、判定オラクル無しでσ1y1e1b、σ1’y2e2b、σ2y1e1b、σ2’y2e2bの検証を行うことができる。第三実施形態の長期鍵二重化NAXOSでも同様に、シミュレータは証明中でa2sra1、およびx2s’r’x1と設定し、σ1rσ1’Y1s、σ2rσ2’Y2s、σ5r’σ5’Y1s′、σ6r’σ6’Y2s’の落とし戸試験を行うことによって、判定オラクル無しでσ1Y1a1、σ1’Y1a2、σ2Y2a1、σ2’Y2a2、σ5Y1x1、σ5’Y1x2、σ6Y2x1、σ6’Y2x2の検証を行うことができる。第四実施形態の短期鍵二重化NAXOSでも同様に、シミュレータは証明中でx2srx1と設定し、σ1rσ1’As、σ2rσ2’Bs、σ3rσ3’Y1s、σ4rσ4’Y2sの落とし戸試験を行うことによって、判定オラクル無しでσ1Ay1、σ1’Ay2、σ2Bx1、σ2’Bx2、σ3Y1x1、σ3’Y1x2、σ4Y2x1、σ4’Y2x2の検証を行うことができる。"