鍵共有方法、第１装置、第２装置、及び、それらのプログラム
【課題】効率が良く、標準モデルで安全性が保証される鍵共有技術を提供する。
【解決手段】第１装置がx={ F1(rx)(a1, a2, a3, a4)+F2(a1, a2, a3, a4)(rx) } mod pを用い、X1=g1x及びX2=g2xを求めて第２装置に送信する。第２装置はy={ F1(ry)(b1, b2, b3, b4)+F2(b1, b2, b3, b4)(ry) } mod pを用い、Y1=g1y及びY2=g2yを求めて第１装置に送信する。第２装置はc=H1(A, Y1, Y2)，d=H2(B, X1, X2)、σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・yを求め、鍵K=Fσ(A, B, X1, X2, Y1, Y2)を算出する。第１装置は、c=H1(A, Y1, Y2)，d=H2(B, X1, X2)、σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・xを求め、鍵K=Fσ(A, B, X1, X2, Y1, Y2)を算出する。
【解決手段】第１装置がx={ F1(rx)(a1, a2, a3, a4)+F2(a1, a2, a3, a4)(rx) } mod pを用い、X1=g1x及びX2=g2xを求めて第２装置に送信する。第２装置はy={ F1(ry)(b1, b2, b3, b4)+F2(b1, b2, b3, b4)(ry) } mod pを用い、Y1=g1y及びY2=g2yを求めて第１装置に送信する。第２装置はc=H1(A, Y1, Y2)，d=H2(B, X1, X2)、σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・yを求め、鍵K=Fσ(A, B, X1, X2, Y1, Y2)を算出する。第１装置は、c=H1(A, Y1, Y2)，d=H2(B, X1, X2)、σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・xを求め、鍵K=Fσ(A, B, X1, X2, Y1, Y2)を算出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に鍵共有技術に関する。
【背景技術】
【０００２】
従来、安全性が保証されていないネットワークを使って鍵を安全に共有するための鍵共有方式が数多く提案されているが、その中で最も安全な方式として、公開鍵インフラストラクチャ（PKI）に基づく方式がある。この方式の代表的な方式として、MQX, HMQV, NAXOS, CMQVなどの方式があり、MQVなどはIEEEなどで標準化されている（例えば、非特許文献１〜４参照）。
【非特許文献１】Law, L., Menezes, A., Qu, M., Solinas, J. and Vanstone, “An Efficient Protocol for Authenticated Key Agreement,” Designs, Codes and Cryptography 28, pp. 119-134 (2003)
【非特許文献２】Krawczk, H., “HMQV: A High-Performance Secure Diffie-Hellman Protocol”, [online],received 13 Jun 2005, last revised 5 Jul 2005, Advances in Cryptography, CRYPTO 2005, LNCS 3621 (2005), [２００７年１１月１６日検索], インターネット＜http://eprint.iacr.org/2005/176＞
【非特許文献３】LaMacchia, B., Lauter, K. and Mityagin, A., “Stronger Security of Authenticated Key Exchange”, [online], received 23 Feb 2006, last revised 31 Mar 2006, Cryptology ePrint Archive, Report 2006/073, [２００７年１１月１６日検索], インターネット＜http://eprint.iacr.org/2006/073＞
【非特許文献４】Ustaoglu, B., “Obtaining a secure and efficient key agreement protocol from (H)MQV and NAXOS”, [online], received 28 Mar 2007, last revised 16 May 2007, Cryptology ePrint Archive, Report 2007/123, [２００７年１１月１６日検索], インターネット＜http://eprint.iacr.org/2007/123＞
【発明の開示】
【発明が解決しようとする課題】
【０００３】
非特許文献１〜４の方式は、通信量や計算量の点で、大変効率がよく実用性に優れている。しかしながら、MQV方式の安全性は証明されておらず、その他の方式の安全性はランダムオラクルモデルという仮想的なモデル（ハッシュ関数を極度に理想化したモデル）でのみ保証されており、現実的なモデル（標準モデル：ハッシュ関数を具体的な関数に固定したモデル）では安全性の保証はない。
本発明は、このような点に鑑みてなされたものであり、従来の最も実用的な方式と同等の効率を持ち、なおかつ標準モデルで安全性が保証される鍵共有技術を提供することを目的とする。
【課題を解決するための手段】
【０００４】
本発明では上記課題を解決するために、整数a1, a2, a3, a4を第１装置の秘密鍵として第１装置の記憶部に格納し、g1, g2を有限群Gの元g1, g2∈Gとした場合における、有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈Gを第１装置の公開鍵として第１装置の記憶部に格納し、整数b1, b2, b3, b4を第２装置の秘密鍵として第２装置の記憶部に格納し、有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈Gを第２装置の公開鍵として第２装置の記憶部に格納し、第１装置の公開鍵A1, A2を第２装置の記憶部に格納し、第２装置の公開鍵B1, B2を第１装置の記憶部に格納する。
【０００５】
また、第１装置が、ランダム値rxを選択し、第１装置の秘密鍵a1, a2, a3, a4の少なくとも一部によって定まる値を入力とし、ランダム値rxをシードとした擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と、ランダム値rxを入力とし、第１装置の秘密鍵a1, a2, a3, a4の少なくとも一部によって定まる値をシードとした擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値と、によって定まる整数xを算出する。さらに、第１装置が、有限群G上での演算X1=g1x∈Gを行い、演算X2=g2x∈Gを行い、少なくとも演算結果X1, X2を第２装置に送信する。
【０００６】
第２装置は、少なくとも演算結果X1, X2を第２装置の記憶部に格納し、ランダム値ryを選択し、第２装置の秘密鍵b1, b2, b3, b4の少なくとも一部によって定まる値を入力とし、ランダム値ryをシードとした擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と、ランダム値ryを入力とし、第２装置の秘密鍵b1, b2, b3, b4の少なくとも一部によって定まる値をシードとした擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値と、によって定まる整数yを算出し、有限群G上での演算Y1=g1y∈Gを行い、演算Y2=g2y∈Gを行い、少なくとも演算結果Y1, Y2を第１装置に送信する。
【０００７】
また、第２装置が、少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値とし、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させてその演算結果cを求め、少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させてその演算結果dを求める。そして、第２装置が、有限群G上での演算σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・y∈Gを行い、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとする。
【０００８】
また、第１装置が、少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値とし、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させてその演算結果cを求め、第１装置が、少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値とし、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させてその演算結果dを求める。そして、第１装置が、有限群G上での演算σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x∈Gを行い、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとする。
【発明の効果】
【０００９】
本発明では、従来の最も実用的な方式と同等の効率を持ち、なおかつ標準モデルで安全性が保証される鍵共有が可能となる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔準備〕
まず、用語の説明を行う。
＜有限群＞
以下の各実施形態では、離散対数問題が難しい有限群Gを用い、その位数をpとする。なお、離散対数問題が難しいとは、離散対数問題を多項式時間で解くことが困難であることを意味する。また、このような有限群Gの実現例としては、例えば、楕円曲線暗号に用いられる楕円曲線上の有理点のなす群や、エルガマル暗号等に用いられる有限体の乗法群などを用いることができる（例えば、『岡本龍明，山本博資著、「現代暗号」、産業図書出版、ISBN4-7828-5353-X（参考文献１）』等参照）。なお、有限群Gとして楕円曲線上の有理点のなす群を用いる場合、その元は楕円曲線上の点であり、有限体の乗法群を用いる場合、その元は整数である。また、楕円曲線上の有理点のなす群をコンピュータ上で実現するための具体的方法には様々なものが存在し、実際、楕円曲線上の有理点のなす群で構成され、コンピュータ上で実装可能な様々な楕円曲線暗号方式が存在する（例えば、参考文献１や『イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、鈴木治郎＝訳、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0（参考文献２）』等参照）。
【００１１】
また、有限群G上の演算とは、有限群Gで定義された演算を意味する。例えば、有限群Gが楕円曲線上の有理点のなす群である場合、楕円曲線上の楕円加算や楕円スカラー倍算やそれらの組み合わせが「有限群G上の演算」に相当する。この場合、αβ∈Gは、楕円曲線上の点αを楕円スカラー倍（β倍）する演算を意味し、α・β∈Gは、楕円曲線上の点αと点βとの楕円加算を意味する。また、楕円スカラー倍演算をコンピュータ上で実行する具体的な方法としては、二進展開法、移動窓法等の公知の演算方法を例示できる（例えば、参考文献２等参照）。また、例えば、有限群Ｇが有限体の乗法群であった場合、ｑ（ただし、ｇは２以上の整数、q=2p+1）を法としたべき乗演算や積演算が「有限群G上の演算」に相当する。この場合、αβ∈Gは、αβmod qの演算を意味し、α・β∈Gは、(α・β) mod qの演算を意味する。
【００１２】
＜目的衝突困難なハッシュ関数＞
目的衝突困難（TCR: Target Collision Resistant）なハッシュ関数とは、異なる入力値に対する出力値が互いに同一となる確率が無視できるほど小さいハッシュ関数を意味する。本形態の目的衝突困難なハッシュ関数は、以下のように定義される。
まず、集合Domkと集合Rngk（kは自然数のセキュリティパラメータ）との間を対応付けるハッシュ関数Hを想定する。また、このようなハッシュ関数Hの各セキュリティパラメータkに対する鍵空間が、KHkで示されるビット列による確率空間であるとする。さらに、入力１ｋ（kビットデータ）に対する出力値の分布がKHkと等しくなる確率的多項式時間アルゴリズムが存在するものとする。また、セキュリティパラメータkと、KHkからその分布に従って任意に選択したh（h ←R KHk）と、集合Domkからその分布に従って任意に選択した集合D（D ←RDomk）と、集合Rngkからその分布に従って任意に選択した集合Rと（R ←R Rngk）のインデックスが付されたこのようなハッシュ関数Hhk,D,Rが、集合Dの要素を集合Rの要素にマッピングする関数であるものとする。なお、「α ←R β」は、集合βからその分布に従って任意に選択した集合αを意味する。さらに、１ｋ，h及び集合Dの要素ρの入力に対して関数値Hhk,D,R(ρ)を出力する決定論多項式アルゴリズムが存在するものとする。
【００１３】
そして、確率的多項式時間マシーンAを想定し、全てのキュリティパラメータkに対するハッシュ関数Hhk,D,Rの優位性を以下のように定義する。なお、Pr[・]は事象・の確率を示し、ρ*は集合Dから一様に選択された値（ρ*←U D）を示す。また、「α←β」はβをαとして設定することを意味する。
AdvTCRH,A(k)←Pr[ρ∈D∧ρ≠ρ*∧Hhk,D,R(ρ)=Hhk,D,R(ρ*)|ρ ←R A(1k,ρ*,h,D,R)] …(1)
ここで、どのような確率的多項式時間マシーンAに対しても優位性AdvTCRH,A(k)がセキュリティパラメータkにおいて無視できる程度に小さい場合、ハッシュ関数Hを目的衝突困難なハッシュ関数と呼ぶ。なお、このような目的衝突困難なハッシュ関数は、SHA-1などの実用的なハッシュ関数を用いて容易に構成できる。
【００１４】
＜擬似ランダム関数＞
擬似ランダム関数（Pseudo-Random Function）とは、入力値に対する出力値が真のランダム値と識別困難である関数を意味する。本形態の擬似ランダム関数は、以下のように定義される。
まず、シードSeedkと集合Domkと集合Rngkとの間を関連付ける関数Fを想定する。ここで、シードSeedkはランダムな値である。さらに、セキュリティパラメータkと、Seedkからその分布に従って任意に選択した集合Σ（Σ ←R Seedk）と、集合Σから一様に選択したσ（σ ←U Σ）と、集合Domkからその分布に従って任意に選択した集合D（D ←R Domk）と、集合Rngkからその分布に従って任意に選択した集合Rと（R ←RRngk）のインデックスが付されたこのような関数Fσk,Σ,D,Rが、集合Dの要素を集合Rにマッピングする関数であるものとする。
【００１５】
そして、オラクルOにアクセス可能な確率的多項式時間マシーンAOを想定し、全てのキュリティパラメータkに対する関数Fσk,Σ,D,Rの優位性を以下のように定義する。なお、Fは関数Fσk,Σ,D,Rであり、RFはDをFに写す真のランダム関数である。また、「A(α)→β」は、Aが入力αに対してβ∈{0, 1}を出力することを意味する。
AdvPRFF,A(k)←｜Pr[AF(1k,D,R)→1] - Pr[ARF(1k,D,R)→1]| …(2)
ここで、どのような確率的多項式時間マシーンAに対しても優位性AdvPRFF,A(k)がセキュリティパラメータkにおいて無視できる程度に小さい場合、関数Fを擬似ランダム関数と呼ぶ。なお、このような目擬似ランダム関数は、SHA-1などの実用的なハッシュ関数を用いて容易に構成できる。
【００１６】
〔第１実施形態〕
次に、本発明の第１実施形態について説明する。
＜全体構成＞
図１（ａ）は、第１実施形態の鍵共有システム１の構成を例示した図である。
図１（ａ）に例示するように、本形態の鍵共有システム１は、鍵を共有する第１装置１０と第２装置とを有し、それらはインターネット等の安全ではないネットワーク３０を通じて通信可能に接続されている。なお、第１装置１０と第２装置２０との間の通信はネットワーク３０を通じて行われるが、以下ではその旨を省略して説明する。
【００１７】
＜ハードウェア構成＞
図１（ｂ）は、第１装置１０のハードウェア構成を例示したブロック図である。
図１（ｂ）に例示するように、この例の第１装置１０は、ＣＰＵ（Central Processing Unit）１０ａ、入力部１０ｂ、出力部１０ｃ、補助記憶装置１０ｄ、ＲＡＭ（Random Access Memory）１０ｆ、ＲＯＭ（Read Only Memory）１０ｅ及びバス１０ｇを有している。
【００１８】
ＣＰＵ１０ａは、読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１０ｂは、データが入力される入力ポート、キーボード、マウス等であり、出力部１０ｃは、データを出力する出力ポート、ディスプレイ等である。補助記憶装置１０ｄは、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、ＲＡＭ１０ｆは、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等である。また、バス１０ｇは、ＣＰＵ１０ａ、入力部１０ｂ、出力部１０ｃ、補助記憶装置１０ｄ、ＲＡＭ１０ｆ及びＲＯＭ１０ｅを通信可能に接続している。
なお、第２装置２０のハードウェア構成は、第１装置１０のそれと同様であるため説明を省略する。
【００１９】
＜ハードウェアとソフトウェアとの協働＞
図２は、第１実施形態の第１装置１０の機能構成を例示したブロック図である。また、図３は、第２実施形態の第２装置２０の機能構成を例示したブロック図である。なお、図２及び図３における矢印はデータの流れを示すが、制御部１３ａ，２３ａに出入りするデータの流れに対応する矢印は省略してある。
【００２０】
第１実施形態の第１装置１０及び第２装置２０は、それぞれ、上述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵが実行することによって構築される。
図２に例示するように、本形態の第１装置１０は、記憶部１１と、送信部１２ａと、受信部１２ｂと、制御部１３ａと、ランダム値選択部１３ｂと、擬似ランダム関数演算部１３ｃと、第１暗号化部１３ｄと、第２暗号化部１３ｅと、第１関数演算部１３ｆと、第２関数演算部１３ｇと、シード演算部１３ｈと、鍵演算部１３ｉとを有する。なお、記憶部１１は、例えば、キャッシュメモリ、レジスタ、ＲＡＭ、若しくは補助記憶装置、又はそれらを結合した記憶領域である。また、送信部１２ａ及び受信部１２ｂは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード、モデム等の通信装置である。さらに、制御部１３ａ、ランダム値選択部１３ｂ、擬似ランダム関数演算部１３ｃ、第１暗号化部１３ｄ、第２暗号化部１３ｅ、第１関数演算部１３ｆ、第２関数演算部１３ｇ、シード演算部１３ｈ及び鍵演算部１３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。
【００２１】
図３に例示するように、本形態の第２装置２０は、記憶部２１と、送信部２２ａと、受信部２２ｂと、制御部２３ａと、ランダム値選択部２３ｂと、擬似ランダム関数演算部２３ｃと、第１暗号化部２３ｄと、第２暗号化部２３ｅと、第１関数演算部２３ｆと、第２関数演算部２３ｇと、シード演算部２３ｈと、鍵演算部２３ｉとを有する。なお、記憶部２１、例えば、キャッシュメモリ、レジスタ、ＲＡＭ、若しくは補助記憶装置、又はそれらを結合した記憶領域である。また、送信部２２ａ及び受信部２２ｂは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード、モデム等の通信装置である。さらに、制御部２３ａ、ランダム値選択部２３ｂ、擬似ランダム関数演算部２３ｃ、第１暗号化部２３ｄ、第２暗号化部２３ｅ、第１関数演算部２３ｆ、第２関数演算部２３ｇ、シード演算部２３ｈ及び鍵演算部２３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。
また、第１装置１０，第２装置２０は、それぞれ、制御部１３ａ，２３ａの制御の下、各処理を実行する。
【００２２】
＜鍵共有処理＞
次に、本形態の鍵共有処理について説明する。
図４及び図５は、本形態の鍵共有処理を説明するためのシーケンス図である。以下、これらの図を用いて本形態の鍵共有処理を説明する。
前処理として、第１装置１０と第２装置２０との共通パラメータとして、有限群Gの元g1, g2∈Gと有限群Gの位数pとが、第１装置１０の記憶部１１と第２装置の記憶部１２とに格納される。
【００２３】
そしてまず、第１装置１０の秘密鍵として(a1, a2, a3, a4)∈{0,1,...,p-1}4が設定され、これらが第１装置１０の記憶部１１に格納される（第１装置秘密鍵格納過程／ステップＳ１）。なお、演算の効率面からは、秘密鍵を(a1, a2, a3, a4)∈{0,1,...,p-1}4のように設定するのが好ましいが、任意の４つの整数(a1, a2, a3, a4)を第１装置１０の秘密鍵としてもよい。
また、第１装置１０の公開鍵として有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈Gが設定され、これらが第１装置１０の記憶部１１に格納される（第１公開鍵格納過程／ステップＳ２）。なお、本形態では、第１装置１０の公開鍵A1, A2を含むid情報Aが記憶部１１に格納される。
【００２４】
同様に、第２装置２０の秘密鍵として(b1, b2, b3, b4)∈{0,1,...,p-1}4が設定され、これらが第２装置２０の記憶部2１に格納される（第２装置秘密鍵格納過程／ステップＳ３）。なお、演算の効率面からは、秘密鍵を(b1, b2, b3, b4)∈{0,1,...,p-1}4のように設定するのが好ましいが、任意の４つの整数(b1, b2, b3, b4)を第２装置２０の秘密鍵としてもよい。
また、第２装置２０の公開鍵として有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈Gが設定され、これらが第２装置２０の記憶部２１に格納される（第２公開鍵格納過程／ステップＳ４）。なお、本形態では、第２装置２０の公開鍵B1, B2を含むid情報Bが記憶部２１に格納される。
【００２５】
さらに、第１装置１０の送信部１２ａに第１装置１０の公開鍵A1, A2が送られ、送信部１２ａは、これらを第２装置２０に送信する（ステップＳ５）。送信された公開鍵A1, A2は、第２装置２０の受信部２２ｂで受信され、第２装置２０の記憶部２１に格納される（第３公開鍵格納過程／ステップＳ６）。なお、本形態では、第１装置１０の公開鍵A1, A2を含むid情報Aが第２装置２０に送信され、記憶部２１に格納される。また、第２装置２０の送信部２２に第２装置２０の公開鍵B1, B2が送られ、送信部２２は、これらを第１装置１０に送信する（ステップＳ７）。送信された公開鍵B1, B2は、第１装置１０の受信部１２ｂで受信され、第１装置１０の記憶部１１に格納される（第４公開鍵格納過程／ステップＳ８）。なお、本形態では、第２装置２０の公開鍵B1, B2を含むid情報Bが第１装置１０に送信され、記憶部１１に格納される。
次に、第１装置１０のランダム値選択部１３ｂが、kビット列のランダム値rxを選択し、当該ランダム値rxを第１装置１０の記憶部１１に格納する（第１装置シード選択過程／ステップＳ９）。
【００２６】
次に、第１装置１０の擬似ランダム関数演算部１３ｃが、第１装置１０の記憶部１１から第１装置１０の秘密鍵(a1, a2, a3, a4)とランダム値rxと位数pとを読み込み、読み込んだ第１装置１０の秘密鍵(a1, a2, a3, a4)によって定まる値を入力とし、ランダム値rxをシードとした擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と、ランダム値rxを入力とし、読み込んだ第１装置１０の秘密鍵(a1, a2, a3, a4)によって定まる値をシードとした擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値と、によって定まる整数xを算出し、当該整数xを第１装置１０の記憶部１１に格納する（第１装置擬似ランダム関数演算過程／ステップＳ１０）。本形態では、
x={F1(rx)(a1, a2, a3, a4) + F2(a1, a2, a3, a4)(rx)} mod p …(3)
によって整数x∈{0,1,...,p-1}が算出・格納される。なお、「読み込んだ第１装置１０の秘密鍵によって定まる値」としては、例えば、読み込んだ第１装置１０の秘密鍵のビット結合値等を例示できる。
【００２７】
次に、第１装置１０の第１暗号化部１３ｄが、第１装置１０の記憶部１１から整数xと有限群Gの元g1とを読み込み、有限群G上での演算
X1=g1x∈G …(4)
を行い、当該演算結果X1を第１装置１０の記憶部１１に格納する（第１装置第１暗号化過程／ステップＳ１１）。また、第１装置１０の第２暗号化部１３ｅが、第１装置１０の記憶部１１から整数xと有限群Gの元g2とを読み込み、有限群G上での演算
X2=g2x∈G …(5)
を行い、当該演算結果X2を第１装置１０の記憶部１１に格納する（第１装置第２暗号化過程／ステップＳ１２）。
【００２８】
次に、第１装置１０の記憶部１１から送信部１２ａに、第１装置１０の公開鍵A1, A2を含むid情報Aと、第２装置２０の公開鍵B1, B2を含むid情報Bと、演算結果X1, X2とが送られ、送信部１２ａが、これらを第２装置２０に送信する（第１演算結果送信過程／ステップＳ１３）。送信されたid情報A, Bと演算結果X1, X2とは、第２装置の受信部２２ｂで受信され、記憶部２１に格納される（第１演算結果格納過程及び第３公開鍵格納過程／ステップＳ１４）。
次に、第２装置２０のランダム値選択部２３ｂが、kビット列のランダム値ryを選択し、当該ランダム値ryを第２装置２０の記憶部２１に格納する（第２装置シード選択過程／ステップＳ１５）。
【００２９】
次に、第２装置２０の擬似ランダム関数演算部２３ｃが、第２装置２０の記憶部２１から第２装置２０の秘密鍵(b1, b2, b3, b4)とランダム値ryと位数pとを読み込み、読み込んだ第２装置２０の秘密鍵(b1, b2, b3, b4)によって定まる値を入力とし、ランダム値ryをシードとした擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と、ランダム値ryを入力とし、読み込んだ第２装置２０の秘密鍵(b1, b2, b3, b4)によって定まる値をシードとした擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値と、によって定まる整数yを算出し、当該整数yを第２装置２０の記憶部２１に格納する（第２装置擬似ランダム関数演算過程／ステップＳ１６）。本形態では、
x={F1(ry)(b1, b2, b3, b4) + F2(b1, b2, b3, b4)(ry)} mod p …(6)
によって整数x∈{0,1,...,p-1}が算出・格納される。なお、「読み込んだ第２装置２０の秘密鍵によって定まる値」としては、例えば、読み込んだ第２装置２０の秘密鍵のビット結合値等を例示できる。
【００３０】
次に、第２装置２０の第１暗号化部２３ｄが、第２装置２０の記憶部２１から整数yと有限群Gの元g1とを読み込み、有限群G上での演算
Y1=g1y∈G …(7)
を行い、当該演算結果Y1を第２装置２０の記憶部２１に格納する（第２装置第１暗号化過程／ステップＳ１７）。
また、第２装置２０の第２暗号化部２３ｅが、第２装置２０の記憶部２１から整数yと有限群Gの元g2とを読み込み、有限群G上での演算
Y2=g2y∈G …(8)
を行い、当該演算結果Y2を第２装置２０の記憶部２１に格納する（第２装置第２暗号化過程／ステップＳ１８）。
【００３１】
次に、第２装置２０の記憶部２１から送信部２２ａに、第１装置１０の公開鍵A1, A2を含むid情報Aと、第２装置２０の公開鍵B1, B2を含むid情報Bと、演算結果X1, X2, Y1, Y2とが送られ、送信部２２ａが、これらを第１装置１０に送信する（第２演算結果送信過程／ステップＳ１９）。送信されたid情報A, Bと演算結果X1, X2, Y1, Y2と（sid=A, B, X1, X2, Y1, Y2）は、第１装置の受信部１２ｂで受信され、記憶部１１に格納される（第１演算結果格納過程／ステップＳ２０）。
【００３２】
その後、第２装置２０の第１関数演算部２３ｆが、第２装置２０の記憶部２１から演算結果Y1, Y2とid情報AとをH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果
c=H1(A, Y1, Y2) …(9)
を第２装置２０の記憶部２１に格納する（第２装置第１関数演算過程／ステップＳ２１）。また、「H1関数入力値によって定まる値」の例としては、例えば、有限群Gが有限体の乗法群の場合には、A, Y1, Y2のビット結合値やそれらの排他的論理和等を例示できる。また、例えば、有限群Gが楕円曲線上の有理点のなす群である場合には、楕円曲線上の点A, Y1, Y2の各座標値（ｘ座標値とｙ座標値）のビット結合値や、各ｘ座標値若しくはｙ座標値のビット結合値や、それらの排他的論理和等を、「H1関数入力値によって定まる値」として用いることができる。
【００３３】
また、第２装置２０の第２関数演算部２３ｇが、第２装置２０の記憶部２１から演算結果X1, X2とid情報BとをH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果
d=H2(B, X1, X2) …(10)
を第２装置２０の記憶部２１に格納する（第２装置第２関数演算過程／ステップＳ２２）。なお、「H2関数入力値によって定まる値」の具体例としては、例えば、「H1関数入力値によって定まる値」の具体例と同様なものを挙げることができる。また、目的衝突困難なハッシュ関数H1と目的衝突困難なハッシュ関数H2とは同一の関数であってもよいし、異なる関数であってもよい。
【００３４】
次に、第２装置２０のシード演算部２３ｈが、第２装置２０の記憶部２１から演算結果X1, X2, c, dと公開鍵A1, A2と秘密鍵b1, b2, b3, b4と整数yとを読み込み、有限群G上での演算
σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・y∈G …(11)
を行い、当該演算結果σを第２装置２０の記憶部２１に格納する（第２装置シード演算過程／ステップＳ２３）。
【００３５】
さらに、第２装置２０の鍵演算部２３ｉが、第２装置２０の記憶部２１から演算結果σとid情報A, Bと演算結果X1, X2, Y1, Y2を読み込み、当該演算結果σをシードとし、id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値を入力とした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵
K=Fσ(A, B, X1, X2, Y1, Y2) …(12)
として第２装置の記憶部に格納する（第２装置鍵演算過程／ステップＳ２４）。なお、「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」の例としては、例えば、有限群Gが有限体の乗法群の場合には、A, B, X1, X2, Y1, Y2のビット結合値やそれらの排他的論理和等を例示できる。また、例えば、有限群Gが楕円曲線上の有理点のなす群である場合には、楕円曲線上の点A, B, X1, X2, Y1, Y2の各座標値（ｘ座標値とｙ座標値）のビット結合値や、各ｘ座標値若しくはｙ座標値のビット結合値や、それらの排他的論理和等を、「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」として用いることができる。また、演算結果σをシードとし、id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値を入力とした擬似ランダム関数Fσの関数値とは、例えば、演算結果σと「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」とを擬似ランダム関数Fσの入力とし、出力された関数値を意味し、より具体的には、例えば、演算結果σと「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」とのビット結合値に対して擬似ランダム関数Fσを作用させた演算結果を意味する。
【００３６】
一方、ステップＳ２０でid情報A, Bと演算結果X1, X2, Y1, Y2とを受信し、記憶部１１に格納した第１装置１０は、その第１関数演算部１３ｆにおいて、第１装置１０の記憶部１１から演算結果Y1, Y2とid情報AとをH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果
c=H1(A, Y1, Y2) …(13)
を第１装置１０の記憶部１１に格納する（第１装置第１関数演算過程／ステップＳ２５）。
【００３７】
また、当該第１装置１０の第２関数演算部１３ｇが、第１装置１０の記憶部１１から演算結果X1, X2とid情報BとをH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果
d=H2(B, X1, X2) …(14)
を第１装置１０の記憶部１１に格納する（第１装置第２関数演算過程／ステップＳ２６）。
【００３８】
さらに、第１装置１０のシード演算部１３ｈが、第１装置１０の記憶部１１から演算結果Y1, Y2, c, dと公開鍵B1, B2と秘密鍵a1, a2, a3, a4と整数xとを読み込み、有限群G上での演算
σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x∈G …(15)
を行い、当該演算結果σを第１装置１０の記憶部１１に格納する（第１装置シード演算過程／ステップＳ２７）。
【００３９】
さらに、第１装置１０の鍵演算部１３ｉが、第１装置１０の記憶部１１から演算結果σとid情報A, Bと演算結果X1, X2, Y1, Y2を読み込み、当該演算結果σをシードとし、id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値を入力とした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵
K=Fσ(A, B, X1, X2, Y1, Y2) …(16)
として第１装置の記憶部に格納する（第１装置鍵演算過程／ステップＳ２８）。
以上の処理により、第１装置１０と第２装置２０とで鍵Kが共有される。
【００４０】
＜第１装置１０と第２装置２０とで鍵Kが共有される理由＞
上述の手順が正しく実行されれば以下を満たし、第１装置１０で算出されるシードσ（式(11)）と第２装置２０で算出されるシードσ（式(15)）とが等しくなり、擬似ランダム関数Fσの関数値である鍵K（式(12)(16)）も等しくなる。
σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x（式(15)）
=g1y・(a1+c・a3+x)・g2y・(a2+c・a4+x)・(g1b1・g2b2)x・(g1b3・g2b4)d・x（式(7)(8), B1,B2の定義）
=(g1a1・g2a2)y・(g1a3・g2a4)c・y・(g1・g2)x・y・g1x(b1+d・b3)・g2x(b2+d・b4)
=A1y・A2 c・y・X1y・X2y・X1(b1+d・b3)・X2(b2+d・b4)（式(4)(5), A1,A2の定義）
= A1y・A2 c・y・X1(b1+d・b3+y)・X2(b2+d・b4+y)
=式(11)
【００４１】
＜本形態の効果＞
本形態の鍵共有方式において、第１装置１０及び第２装置２０の計算量は、それぞれ、有限群G上での指数演算３回に相当する。また、第１装置１０及び第２装置２０の送信情報量（id情報以外）は、有限群Gの２要素のサイズに相当する。また、この方式の安全性は、標準モデルで安全であることが示される。
【００４２】
従来の方式の中で最も効率の良い鍵共有方式であるMQV方式の場合、それぞれの利用者の計算量は、有限群G上の指数演算２回に相当する。また、それぞれの利用者の送信情報量（id情報以外）は、有限群Gの１要素のサイズに相当する。しかし、MQV方式の安全性は証明されておらず、それをほぼ同等な性能を持つHMQVやCMQV方式では、ランダムオラクルモデルで安全であることが示されるが、標準モデルでは示されない。
以上より、本形態の方式が、従来の方式とほぼ同等の効率でありながら、安全性ではそれらの方式よりも優れていることが分かる。
【００４３】
＜本形態の方式の安全性＞
K*を目的のセッションで共有される鍵とし、R*←U {0,1}|K*|とし、b* ←U {0,1}とする。攻撃者Mによるテスト要求に対する応答として、b*=0であればK*が攻撃者Mに与えられ、そうでなければR*が攻撃者Mに与えられる。そして、最終的に攻撃者Mはb∈{0,1}を出力する。これについて以下を定義する。
AdvAKEM(k) ← |Pr(b=b*)‐1/2| …(17)
ここで、以下の条件が満たされる場合、その鍵共有プロトコルは安全（eCK安全）であるといえる。
【００４４】
（条件１）第１装置−第２装置間でマッチングセッションが完全になされるのであれば、それによって両装置間で同じ鍵が算出される（又は両装置でエラー出力がなされる）。
（条件２）どのような確率的多項式時間攻撃者Mに対しても、AdvAKEM(k)がセキュリティパラメータkにおいて無視できる。
ここで、本形態の方式が上述の（条件１）を満たすことは明らかである。また、本形態の方式では、有限群GにおいてDDH仮定が保たれ、H1, H2が目的衝突困難ハッシュ関数であり、F, F1, F2が擬似ランダム関数であることから（条件２）を満たすことも証明できる。よって、本形態の方式は安全であるといえる。
【００４５】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。
例えば、本形態では、ステップＳ１０において{F1(rx)(a1, a2, a3, a4)+F2(a1, a2, a3, a4)(rx)} mod pを整数xとし、ステップＳ１６において{F1(ry)(b1, b2, b3, b4)+F2(b1, b2, b3, b4)(ry)} mod pを整数yとした。しかし、ステップＳ１０においてF1(rx)(a1, a2, a3, a4)+F2(a1, a2, a3, a4)(rx)を整数xとし、ステップＳ１６においてF1(ry)(b1, b2, b3, b4)+F2(b1, b2, b3, b4)(ry)を整数yとしてもよい。さらに、ステップＳ１０においてF1(rx)(a1, a2, a3, a4)とF2(a1, a2, a3, a4)(rx)との他の演算によって定まる値を整数xとし、ステップＳ１６においてF1(ry)(b1, b2, b3, b4)とF2(b1, b2, b3, b4)(ry)との他の演算によって定まる値を整数yとしてもよい。また、ステップＳ１０において秘密鍵a1, a2, a3, a4の一部とランダム値rxとを用いて整数xを生成し、ステップＳ１６において秘密鍵b1, b2, b3, b4の一部とランダム値ryとを用いて整数yを生成してもよい。
【００４６】
また、本形態では、ステップＳ２１，Ｓ２５において、演算結果Y1, Y2とid情報AとをH1関数入力値としたが、演算結果Y1, Y2と第１装置１０の公開鍵A1，A2とを含むその他の情報をH1関数入力値としてもよい。また、演算結果Y1, Y2の一方と公開鍵A1，A2とをH1関数入力値としてもよいし、演算結果Y1, Y2の一方と公開鍵A1，A2の一方とをH1関数入力値としてもよいし、演算結果Y1, Y2の一方とその他の情報とをH1関数入力値としてもよい。
また、本形態では、ステップＳ２２，Ｓ２６において、演算結果X1, X2とid情報AとをH2関数入力値としたが、演算結果X1, X2と第２装置２０の公開鍵B1，B2とを含むその他の情報をH2関数入力値としてもよい。また、演算結果X1, X2の一方と公開鍵B1，B2とをH2関数入力値としてもよいし、演算結果X1, X2の一方と公開鍵B1，B2の一方とをH2関数入力値としてもよいし、演算結果X1, X2の一方とその他の情報とをH2関数入力値としてもよい。
【００４７】
また、本形態では、ステップＳ２４，Ｓ２８において、演算結果σをシードとし、id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値を入力とした擬似ランダム関数Fσの関数値K=Fσ(A, B, X1, X2, Y1, Y2)を鍵Kとした。しかし、「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」の代わりに他の情報を用いることとしてもよい。例えば、「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」の代わりに、「A1, A2, B1, B2, X1, X2, Y1, Y2によって定まる値」や「A1, B1, X1, X2, Y1, Y2によって定まる値」や「X1, X2, Y1, Y2によって定まる値」や「X1, X2, Y1, Y2の一部によって定まる値」やnull値等を用いてもよい。
【００４８】
また、ステップＳ１〜Ｓ８の各処理は、それらの情報が必要となるまでのその他の時点で実行されてもよい。また、ステップＳ５，Ｓ６を行わないこととしてもよい。その他、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００４９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００５０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００５３】
本発明の産業上の利用分野としては、例えば、共通鍵を共有して共通鍵暗号通信を行う暗号通信分野を例示できる。
【図面の簡単な説明】
【００５４】
【図１】図１（ａ）は、第１実施形態の鍵共有システムの構成を例示した図である。図１（ｂ）は、第１装置のハードウェア構成を例示したブロック図である。
【図２】図２は、第１実施形態の第１装置の機能構成を例示したブロック図である。
【図３】図３は、第２実施形態の第２装置の機能構成を例示したブロック図である。
【図４】図４は、本形態の鍵共有処理を説明するためのシーケンス図である。
【図５】図５は、本形態の鍵共有処理を説明するためのシーケンス図である。
【符号の説明】
【００５５】
１０ 第１装置
２０ 第２装置
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に鍵共有技術に関する。
【背景技術】
【０００２】
従来、安全性が保証されていないネットワークを使って鍵を安全に共有するための鍵共有方式が数多く提案されているが、その中で最も安全な方式として、公開鍵インフラストラクチャ（PKI）に基づく方式がある。この方式の代表的な方式として、MQX, HMQV, NAXOS, CMQVなどの方式があり、MQVなどはIEEEなどで標準化されている（例えば、非特許文献１〜４参照）。
【非特許文献１】Law, L., Menezes, A., Qu, M., Solinas, J. and Vanstone, “An Efficient Protocol for Authenticated Key Agreement,” Designs, Codes and Cryptography 28, pp. 119-134 (2003)
【非特許文献２】Krawczk, H., “HMQV: A High-Performance Secure Diffie-Hellman Protocol”, [online],received 13 Jun 2005, last revised 5 Jul 2005, Advances in Cryptography, CRYPTO 2005, LNCS 3621 (2005), [２００７年１１月１６日検索], インターネット＜http://eprint.iacr.org/2005/176＞
【非特許文献３】LaMacchia, B., Lauter, K. and Mityagin, A., “Stronger Security of Authenticated Key Exchange”, [online], received 23 Feb 2006, last revised 31 Mar 2006, Cryptology ePrint Archive, Report 2006/073, [２００７年１１月１６日検索], インターネット＜http://eprint.iacr.org/2006/073＞
【非特許文献４】Ustaoglu, B., “Obtaining a secure and efficient key agreement protocol from (H)MQV and NAXOS”, [online], received 28 Mar 2007, last revised 16 May 2007, Cryptology ePrint Archive, Report 2007/123, [２００７年１１月１６日検索], インターネット＜http://eprint.iacr.org/2007/123＞
【発明の開示】
【発明が解決しようとする課題】
【０００３】
非特許文献１〜４の方式は、通信量や計算量の点で、大変効率がよく実用性に優れている。しかしながら、MQV方式の安全性は証明されておらず、その他の方式の安全性はランダムオラクルモデルという仮想的なモデル（ハッシュ関数を極度に理想化したモデル）でのみ保証されており、現実的なモデル（標準モデル：ハッシュ関数を具体的な関数に固定したモデル）では安全性の保証はない。
本発明は、このような点に鑑みてなされたものであり、従来の最も実用的な方式と同等の効率を持ち、なおかつ標準モデルで安全性が保証される鍵共有技術を提供することを目的とする。
【課題を解決するための手段】
【０００４】
本発明では上記課題を解決するために、整数a1, a2, a3, a4を第１装置の秘密鍵として第１装置の記憶部に格納し、g1, g2を有限群Gの元g1, g2∈Gとした場合における、有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈Gを第１装置の公開鍵として第１装置の記憶部に格納し、整数b1, b2, b3, b4を第２装置の秘密鍵として第２装置の記憶部に格納し、有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈Gを第２装置の公開鍵として第２装置の記憶部に格納し、第１装置の公開鍵A1, A2を第２装置の記憶部に格納し、第２装置の公開鍵B1, B2を第１装置の記憶部に格納する。
【０００５】
また、第１装置が、ランダム値rxを選択し、第１装置の秘密鍵a1, a2, a3, a4の少なくとも一部によって定まる値を入力とし、ランダム値rxをシードとした擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と、ランダム値rxを入力とし、第１装置の秘密鍵a1, a2, a3, a4の少なくとも一部によって定まる値をシードとした擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値と、によって定まる整数xを算出する。さらに、第１装置が、有限群G上での演算X1=g1x∈Gを行い、演算X2=g2x∈Gを行い、少なくとも演算結果X1, X2を第２装置に送信する。
【０００６】
第２装置は、少なくとも演算結果X1, X2を第２装置の記憶部に格納し、ランダム値ryを選択し、第２装置の秘密鍵b1, b2, b3, b4の少なくとも一部によって定まる値を入力とし、ランダム値ryをシードとした擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と、ランダム値ryを入力とし、第２装置の秘密鍵b1, b2, b3, b4の少なくとも一部によって定まる値をシードとした擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値と、によって定まる整数yを算出し、有限群G上での演算Y1=g1y∈Gを行い、演算Y2=g2y∈Gを行い、少なくとも演算結果Y1, Y2を第１装置に送信する。
【０００７】
また、第２装置が、少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値とし、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させてその演算結果cを求め、少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させてその演算結果dを求める。そして、第２装置が、有限群G上での演算σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・y∈Gを行い、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとする。
【０００８】
また、第１装置が、少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値とし、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させてその演算結果cを求め、第１装置が、少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値とし、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させてその演算結果dを求める。そして、第１装置が、有限群G上での演算σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x∈Gを行い、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとする。
【発明の効果】
【０００９】
本発明では、従来の最も実用的な方式と同等の効率を持ち、なおかつ標準モデルで安全性が保証される鍵共有が可能となる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔準備〕
まず、用語の説明を行う。
＜有限群＞
以下の各実施形態では、離散対数問題が難しい有限群Gを用い、その位数をpとする。なお、離散対数問題が難しいとは、離散対数問題を多項式時間で解くことが困難であることを意味する。また、このような有限群Gの実現例としては、例えば、楕円曲線暗号に用いられる楕円曲線上の有理点のなす群や、エルガマル暗号等に用いられる有限体の乗法群などを用いることができる（例えば、『岡本龍明，山本博資著、「現代暗号」、産業図書出版、ISBN4-7828-5353-X（参考文献１）』等参照）。なお、有限群Gとして楕円曲線上の有理点のなす群を用いる場合、その元は楕円曲線上の点であり、有限体の乗法群を用いる場合、その元は整数である。また、楕円曲線上の有理点のなす群をコンピュータ上で実現するための具体的方法には様々なものが存在し、実際、楕円曲線上の有理点のなす群で構成され、コンピュータ上で実装可能な様々な楕円曲線暗号方式が存在する（例えば、参考文献１や『イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、鈴木治郎＝訳、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0（参考文献２）』等参照）。
【００１１】
また、有限群G上の演算とは、有限群Gで定義された演算を意味する。例えば、有限群Gが楕円曲線上の有理点のなす群である場合、楕円曲線上の楕円加算や楕円スカラー倍算やそれらの組み合わせが「有限群G上の演算」に相当する。この場合、αβ∈Gは、楕円曲線上の点αを楕円スカラー倍（β倍）する演算を意味し、α・β∈Gは、楕円曲線上の点αと点βとの楕円加算を意味する。また、楕円スカラー倍演算をコンピュータ上で実行する具体的な方法としては、二進展開法、移動窓法等の公知の演算方法を例示できる（例えば、参考文献２等参照）。また、例えば、有限群Ｇが有限体の乗法群であった場合、ｑ（ただし、ｇは２以上の整数、q=2p+1）を法としたべき乗演算や積演算が「有限群G上の演算」に相当する。この場合、αβ∈Gは、αβmod qの演算を意味し、α・β∈Gは、(α・β) mod qの演算を意味する。
【００１２】
＜目的衝突困難なハッシュ関数＞
目的衝突困難（TCR: Target Collision Resistant）なハッシュ関数とは、異なる入力値に対する出力値が互いに同一となる確率が無視できるほど小さいハッシュ関数を意味する。本形態の目的衝突困難なハッシュ関数は、以下のように定義される。
まず、集合Domkと集合Rngk（kは自然数のセキュリティパラメータ）との間を対応付けるハッシュ関数Hを想定する。また、このようなハッシュ関数Hの各セキュリティパラメータkに対する鍵空間が、KHkで示されるビット列による確率空間であるとする。さらに、入力１ｋ（kビットデータ）に対する出力値の分布がKHkと等しくなる確率的多項式時間アルゴリズムが存在するものとする。また、セキュリティパラメータkと、KHkからその分布に従って任意に選択したh（h ←R KHk）と、集合Domkからその分布に従って任意に選択した集合D（D ←RDomk）と、集合Rngkからその分布に従って任意に選択した集合Rと（R ←R Rngk）のインデックスが付されたこのようなハッシュ関数Hhk,D,Rが、集合Dの要素を集合Rの要素にマッピングする関数であるものとする。なお、「α ←R β」は、集合βからその分布に従って任意に選択した集合αを意味する。さらに、１ｋ，h及び集合Dの要素ρの入力に対して関数値Hhk,D,R(ρ)を出力する決定論多項式アルゴリズムが存在するものとする。
【００１３】
そして、確率的多項式時間マシーンAを想定し、全てのキュリティパラメータkに対するハッシュ関数Hhk,D,Rの優位性を以下のように定義する。なお、Pr[・]は事象・の確率を示し、ρ*は集合Dから一様に選択された値（ρ*←U D）を示す。また、「α←β」はβをαとして設定することを意味する。
AdvTCRH,A(k)←Pr[ρ∈D∧ρ≠ρ*∧Hhk,D,R(ρ)=Hhk,D,R(ρ*)|ρ ←R A(1k,ρ*,h,D,R)] …(1)
ここで、どのような確率的多項式時間マシーンAに対しても優位性AdvTCRH,A(k)がセキュリティパラメータkにおいて無視できる程度に小さい場合、ハッシュ関数Hを目的衝突困難なハッシュ関数と呼ぶ。なお、このような目的衝突困難なハッシュ関数は、SHA-1などの実用的なハッシュ関数を用いて容易に構成できる。
【００１４】
＜擬似ランダム関数＞
擬似ランダム関数（Pseudo-Random Function）とは、入力値に対する出力値が真のランダム値と識別困難である関数を意味する。本形態の擬似ランダム関数は、以下のように定義される。
まず、シードSeedkと集合Domkと集合Rngkとの間を関連付ける関数Fを想定する。ここで、シードSeedkはランダムな値である。さらに、セキュリティパラメータkと、Seedkからその分布に従って任意に選択した集合Σ（Σ ←R Seedk）と、集合Σから一様に選択したσ（σ ←U Σ）と、集合Domkからその分布に従って任意に選択した集合D（D ←R Domk）と、集合Rngkからその分布に従って任意に選択した集合Rと（R ←RRngk）のインデックスが付されたこのような関数Fσk,Σ,D,Rが、集合Dの要素を集合Rにマッピングする関数であるものとする。
【００１５】
そして、オラクルOにアクセス可能な確率的多項式時間マシーンAOを想定し、全てのキュリティパラメータkに対する関数Fσk,Σ,D,Rの優位性を以下のように定義する。なお、Fは関数Fσk,Σ,D,Rであり、RFはDをFに写す真のランダム関数である。また、「A(α)→β」は、Aが入力αに対してβ∈{0, 1}を出力することを意味する。
AdvPRFF,A(k)←｜Pr[AF(1k,D,R)→1] - Pr[ARF(1k,D,R)→1]| …(2)
ここで、どのような確率的多項式時間マシーンAに対しても優位性AdvPRFF,A(k)がセキュリティパラメータkにおいて無視できる程度に小さい場合、関数Fを擬似ランダム関数と呼ぶ。なお、このような目擬似ランダム関数は、SHA-1などの実用的なハッシュ関数を用いて容易に構成できる。
【００１６】
〔第１実施形態〕
次に、本発明の第１実施形態について説明する。
＜全体構成＞
図１（ａ）は、第１実施形態の鍵共有システム１の構成を例示した図である。
図１（ａ）に例示するように、本形態の鍵共有システム１は、鍵を共有する第１装置１０と第２装置とを有し、それらはインターネット等の安全ではないネットワーク３０を通じて通信可能に接続されている。なお、第１装置１０と第２装置２０との間の通信はネットワーク３０を通じて行われるが、以下ではその旨を省略して説明する。
【００１７】
＜ハードウェア構成＞
図１（ｂ）は、第１装置１０のハードウェア構成を例示したブロック図である。
図１（ｂ）に例示するように、この例の第１装置１０は、ＣＰＵ（Central Processing Unit）１０ａ、入力部１０ｂ、出力部１０ｃ、補助記憶装置１０ｄ、ＲＡＭ（Random Access Memory）１０ｆ、ＲＯＭ（Read Only Memory）１０ｅ及びバス１０ｇを有している。
【００１８】
ＣＰＵ１０ａは、読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１０ｂは、データが入力される入力ポート、キーボード、マウス等であり、出力部１０ｃは、データを出力する出力ポート、ディスプレイ等である。補助記憶装置１０ｄは、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、ＲＡＭ１０ｆは、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等である。また、バス１０ｇは、ＣＰＵ１０ａ、入力部１０ｂ、出力部１０ｃ、補助記憶装置１０ｄ、ＲＡＭ１０ｆ及びＲＯＭ１０ｅを通信可能に接続している。
なお、第２装置２０のハードウェア構成は、第１装置１０のそれと同様であるため説明を省略する。
【００１９】
＜ハードウェアとソフトウェアとの協働＞
図２は、第１実施形態の第１装置１０の機能構成を例示したブロック図である。また、図３は、第２実施形態の第２装置２０の機能構成を例示したブロック図である。なお、図２及び図３における矢印はデータの流れを示すが、制御部１３ａ，２３ａに出入りするデータの流れに対応する矢印は省略してある。
【００２０】
第１実施形態の第１装置１０及び第２装置２０は、それぞれ、上述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵが実行することによって構築される。
図２に例示するように、本形態の第１装置１０は、記憶部１１と、送信部１２ａと、受信部１２ｂと、制御部１３ａと、ランダム値選択部１３ｂと、擬似ランダム関数演算部１３ｃと、第１暗号化部１３ｄと、第２暗号化部１３ｅと、第１関数演算部１３ｆと、第２関数演算部１３ｇと、シード演算部１３ｈと、鍵演算部１３ｉとを有する。なお、記憶部１１は、例えば、キャッシュメモリ、レジスタ、ＲＡＭ、若しくは補助記憶装置、又はそれらを結合した記憶領域である。また、送信部１２ａ及び受信部１２ｂは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード、モデム等の通信装置である。さらに、制御部１３ａ、ランダム値選択部１３ｂ、擬似ランダム関数演算部１３ｃ、第１暗号化部１３ｄ、第２暗号化部１３ｅ、第１関数演算部１３ｆ、第２関数演算部１３ｇ、シード演算部１３ｈ及び鍵演算部１３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。
【００２１】
図３に例示するように、本形態の第２装置２０は、記憶部２１と、送信部２２ａと、受信部２２ｂと、制御部２３ａと、ランダム値選択部２３ｂと、擬似ランダム関数演算部２３ｃと、第１暗号化部２３ｄと、第２暗号化部２３ｅと、第１関数演算部２３ｆと、第２関数演算部２３ｇと、シード演算部２３ｈと、鍵演算部２３ｉとを有する。なお、記憶部２１、例えば、キャッシュメモリ、レジスタ、ＲＡＭ、若しくは補助記憶装置、又はそれらを結合した記憶領域である。また、送信部２２ａ及び受信部２２ｂは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード、モデム等の通信装置である。さらに、制御部２３ａ、ランダム値選択部２３ｂ、擬似ランダム関数演算部２３ｃ、第１暗号化部２３ｄ、第２暗号化部２３ｅ、第１関数演算部２３ｆ、第２関数演算部２３ｇ、シード演算部２３ｈ及び鍵演算部２３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。
また、第１装置１０，第２装置２０は、それぞれ、制御部１３ａ，２３ａの制御の下、各処理を実行する。
【００２２】
＜鍵共有処理＞
次に、本形態の鍵共有処理について説明する。
図４及び図５は、本形態の鍵共有処理を説明するためのシーケンス図である。以下、これらの図を用いて本形態の鍵共有処理を説明する。
前処理として、第１装置１０と第２装置２０との共通パラメータとして、有限群Gの元g1, g2∈Gと有限群Gの位数pとが、第１装置１０の記憶部１１と第２装置の記憶部１２とに格納される。
【００２３】
そしてまず、第１装置１０の秘密鍵として(a1, a2, a3, a4)∈{0,1,...,p-1}4が設定され、これらが第１装置１０の記憶部１１に格納される（第１装置秘密鍵格納過程／ステップＳ１）。なお、演算の効率面からは、秘密鍵を(a1, a2, a3, a4)∈{0,1,...,p-1}4のように設定するのが好ましいが、任意の４つの整数(a1, a2, a3, a4)を第１装置１０の秘密鍵としてもよい。
また、第１装置１０の公開鍵として有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈Gが設定され、これらが第１装置１０の記憶部１１に格納される（第１公開鍵格納過程／ステップＳ２）。なお、本形態では、第１装置１０の公開鍵A1, A2を含むid情報Aが記憶部１１に格納される。
【００２４】
同様に、第２装置２０の秘密鍵として(b1, b2, b3, b4)∈{0,1,...,p-1}4が設定され、これらが第２装置２０の記憶部2１に格納される（第２装置秘密鍵格納過程／ステップＳ３）。なお、演算の効率面からは、秘密鍵を(b1, b2, b3, b4)∈{0,1,...,p-1}4のように設定するのが好ましいが、任意の４つの整数(b1, b2, b3, b4)を第２装置２０の秘密鍵としてもよい。
また、第２装置２０の公開鍵として有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈Gが設定され、これらが第２装置２０の記憶部２１に格納される（第２公開鍵格納過程／ステップＳ４）。なお、本形態では、第２装置２０の公開鍵B1, B2を含むid情報Bが記憶部２１に格納される。
【００２５】
さらに、第１装置１０の送信部１２ａに第１装置１０の公開鍵A1, A2が送られ、送信部１２ａは、これらを第２装置２０に送信する（ステップＳ５）。送信された公開鍵A1, A2は、第２装置２０の受信部２２ｂで受信され、第２装置２０の記憶部２１に格納される（第３公開鍵格納過程／ステップＳ６）。なお、本形態では、第１装置１０の公開鍵A1, A2を含むid情報Aが第２装置２０に送信され、記憶部２１に格納される。また、第２装置２０の送信部２２に第２装置２０の公開鍵B1, B2が送られ、送信部２２は、これらを第１装置１０に送信する（ステップＳ７）。送信された公開鍵B1, B2は、第１装置１０の受信部１２ｂで受信され、第１装置１０の記憶部１１に格納される（第４公開鍵格納過程／ステップＳ８）。なお、本形態では、第２装置２０の公開鍵B1, B2を含むid情報Bが第１装置１０に送信され、記憶部１１に格納される。
次に、第１装置１０のランダム値選択部１３ｂが、kビット列のランダム値rxを選択し、当該ランダム値rxを第１装置１０の記憶部１１に格納する（第１装置シード選択過程／ステップＳ９）。
【００２６】
次に、第１装置１０の擬似ランダム関数演算部１３ｃが、第１装置１０の記憶部１１から第１装置１０の秘密鍵(a1, a2, a3, a4)とランダム値rxと位数pとを読み込み、読み込んだ第１装置１０の秘密鍵(a1, a2, a3, a4)によって定まる値を入力とし、ランダム値rxをシードとした擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と、ランダム値rxを入力とし、読み込んだ第１装置１０の秘密鍵(a1, a2, a3, a4)によって定まる値をシードとした擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値と、によって定まる整数xを算出し、当該整数xを第１装置１０の記憶部１１に格納する（第１装置擬似ランダム関数演算過程／ステップＳ１０）。本形態では、
x={F1(rx)(a1, a2, a3, a4) + F2(a1, a2, a3, a4)(rx)} mod p …(3)
によって整数x∈{0,1,...,p-1}が算出・格納される。なお、「読み込んだ第１装置１０の秘密鍵によって定まる値」としては、例えば、読み込んだ第１装置１０の秘密鍵のビット結合値等を例示できる。
【００２７】
次に、第１装置１０の第１暗号化部１３ｄが、第１装置１０の記憶部１１から整数xと有限群Gの元g1とを読み込み、有限群G上での演算
X1=g1x∈G …(4)
を行い、当該演算結果X1を第１装置１０の記憶部１１に格納する（第１装置第１暗号化過程／ステップＳ１１）。また、第１装置１０の第２暗号化部１３ｅが、第１装置１０の記憶部１１から整数xと有限群Gの元g2とを読み込み、有限群G上での演算
X2=g2x∈G …(5)
を行い、当該演算結果X2を第１装置１０の記憶部１１に格納する（第１装置第２暗号化過程／ステップＳ１２）。
【００２８】
次に、第１装置１０の記憶部１１から送信部１２ａに、第１装置１０の公開鍵A1, A2を含むid情報Aと、第２装置２０の公開鍵B1, B2を含むid情報Bと、演算結果X1, X2とが送られ、送信部１２ａが、これらを第２装置２０に送信する（第１演算結果送信過程／ステップＳ１３）。送信されたid情報A, Bと演算結果X1, X2とは、第２装置の受信部２２ｂで受信され、記憶部２１に格納される（第１演算結果格納過程及び第３公開鍵格納過程／ステップＳ１４）。
次に、第２装置２０のランダム値選択部２３ｂが、kビット列のランダム値ryを選択し、当該ランダム値ryを第２装置２０の記憶部２１に格納する（第２装置シード選択過程／ステップＳ１５）。
【００２９】
次に、第２装置２０の擬似ランダム関数演算部２３ｃが、第２装置２０の記憶部２１から第２装置２０の秘密鍵(b1, b2, b3, b4)とランダム値ryと位数pとを読み込み、読み込んだ第２装置２０の秘密鍵(b1, b2, b3, b4)によって定まる値を入力とし、ランダム値ryをシードとした擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と、ランダム値ryを入力とし、読み込んだ第２装置２０の秘密鍵(b1, b2, b3, b4)によって定まる値をシードとした擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値と、によって定まる整数yを算出し、当該整数yを第２装置２０の記憶部２１に格納する（第２装置擬似ランダム関数演算過程／ステップＳ１６）。本形態では、
x={F1(ry)(b1, b2, b3, b4) + F2(b1, b2, b3, b4)(ry)} mod p …(6)
によって整数x∈{0,1,...,p-1}が算出・格納される。なお、「読み込んだ第２装置２０の秘密鍵によって定まる値」としては、例えば、読み込んだ第２装置２０の秘密鍵のビット結合値等を例示できる。
【００３０】
次に、第２装置２０の第１暗号化部２３ｄが、第２装置２０の記憶部２１から整数yと有限群Gの元g1とを読み込み、有限群G上での演算
Y1=g1y∈G …(7)
を行い、当該演算結果Y1を第２装置２０の記憶部２１に格納する（第２装置第１暗号化過程／ステップＳ１７）。
また、第２装置２０の第２暗号化部２３ｅが、第２装置２０の記憶部２１から整数yと有限群Gの元g2とを読み込み、有限群G上での演算
Y2=g2y∈G …(8)
を行い、当該演算結果Y2を第２装置２０の記憶部２１に格納する（第２装置第２暗号化過程／ステップＳ１８）。
【００３１】
次に、第２装置２０の記憶部２１から送信部２２ａに、第１装置１０の公開鍵A1, A2を含むid情報Aと、第２装置２０の公開鍵B1, B2を含むid情報Bと、演算結果X1, X2, Y1, Y2とが送られ、送信部２２ａが、これらを第１装置１０に送信する（第２演算結果送信過程／ステップＳ１９）。送信されたid情報A, Bと演算結果X1, X2, Y1, Y2と（sid=A, B, X1, X2, Y1, Y2）は、第１装置の受信部１２ｂで受信され、記憶部１１に格納される（第１演算結果格納過程／ステップＳ２０）。
【００３２】
その後、第２装置２０の第１関数演算部２３ｆが、第２装置２０の記憶部２１から演算結果Y1, Y2とid情報AとをH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果
c=H1(A, Y1, Y2) …(9)
を第２装置２０の記憶部２１に格納する（第２装置第１関数演算過程／ステップＳ２１）。また、「H1関数入力値によって定まる値」の例としては、例えば、有限群Gが有限体の乗法群の場合には、A, Y1, Y2のビット結合値やそれらの排他的論理和等を例示できる。また、例えば、有限群Gが楕円曲線上の有理点のなす群である場合には、楕円曲線上の点A, Y1, Y2の各座標値（ｘ座標値とｙ座標値）のビット結合値や、各ｘ座標値若しくはｙ座標値のビット結合値や、それらの排他的論理和等を、「H1関数入力値によって定まる値」として用いることができる。
【００３３】
また、第２装置２０の第２関数演算部２３ｇが、第２装置２０の記憶部２１から演算結果X1, X2とid情報BとをH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果
d=H2(B, X1, X2) …(10)
を第２装置２０の記憶部２１に格納する（第２装置第２関数演算過程／ステップＳ２２）。なお、「H2関数入力値によって定まる値」の具体例としては、例えば、「H1関数入力値によって定まる値」の具体例と同様なものを挙げることができる。また、目的衝突困難なハッシュ関数H1と目的衝突困難なハッシュ関数H2とは同一の関数であってもよいし、異なる関数であってもよい。
【００３４】
次に、第２装置２０のシード演算部２３ｈが、第２装置２０の記憶部２１から演算結果X1, X2, c, dと公開鍵A1, A2と秘密鍵b1, b2, b3, b4と整数yとを読み込み、有限群G上での演算
σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・y∈G …(11)
を行い、当該演算結果σを第２装置２０の記憶部２１に格納する（第２装置シード演算過程／ステップＳ２３）。
【００３５】
さらに、第２装置２０の鍵演算部２３ｉが、第２装置２０の記憶部２１から演算結果σとid情報A, Bと演算結果X1, X2, Y1, Y2を読み込み、当該演算結果σをシードとし、id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値を入力とした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵
K=Fσ(A, B, X1, X2, Y1, Y2) …(12)
として第２装置の記憶部に格納する（第２装置鍵演算過程／ステップＳ２４）。なお、「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」の例としては、例えば、有限群Gが有限体の乗法群の場合には、A, B, X1, X2, Y1, Y2のビット結合値やそれらの排他的論理和等を例示できる。また、例えば、有限群Gが楕円曲線上の有理点のなす群である場合には、楕円曲線上の点A, B, X1, X2, Y1, Y2の各座標値（ｘ座標値とｙ座標値）のビット結合値や、各ｘ座標値若しくはｙ座標値のビット結合値や、それらの排他的論理和等を、「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」として用いることができる。また、演算結果σをシードとし、id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値を入力とした擬似ランダム関数Fσの関数値とは、例えば、演算結果σと「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」とを擬似ランダム関数Fσの入力とし、出力された関数値を意味し、より具体的には、例えば、演算結果σと「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」とのビット結合値に対して擬似ランダム関数Fσを作用させた演算結果を意味する。
【００３６】
一方、ステップＳ２０でid情報A, Bと演算結果X1, X2, Y1, Y2とを受信し、記憶部１１に格納した第１装置１０は、その第１関数演算部１３ｆにおいて、第１装置１０の記憶部１１から演算結果Y1, Y2とid情報AとをH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果
c=H1(A, Y1, Y2) …(13)
を第１装置１０の記憶部１１に格納する（第１装置第１関数演算過程／ステップＳ２５）。
【００３７】
また、当該第１装置１０の第２関数演算部１３ｇが、第１装置１０の記憶部１１から演算結果X1, X2とid情報BとをH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果
d=H2(B, X1, X2) …(14)
を第１装置１０の記憶部１１に格納する（第１装置第２関数演算過程／ステップＳ２６）。
【００３８】
さらに、第１装置１０のシード演算部１３ｈが、第１装置１０の記憶部１１から演算結果Y1, Y2, c, dと公開鍵B1, B2と秘密鍵a1, a2, a3, a4と整数xとを読み込み、有限群G上での演算
σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x∈G …(15)
を行い、当該演算結果σを第１装置１０の記憶部１１に格納する（第１装置シード演算過程／ステップＳ２７）。
【００３９】
さらに、第１装置１０の鍵演算部１３ｉが、第１装置１０の記憶部１１から演算結果σとid情報A, Bと演算結果X1, X2, Y1, Y2を読み込み、当該演算結果σをシードとし、id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値を入力とした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵
K=Fσ(A, B, X1, X2, Y1, Y2) …(16)
として第１装置の記憶部に格納する（第１装置鍵演算過程／ステップＳ２８）。
以上の処理により、第１装置１０と第２装置２０とで鍵Kが共有される。
【００４０】
＜第１装置１０と第２装置２０とで鍵Kが共有される理由＞
上述の手順が正しく実行されれば以下を満たし、第１装置１０で算出されるシードσ（式(11)）と第２装置２０で算出されるシードσ（式(15)）とが等しくなり、擬似ランダム関数Fσの関数値である鍵K（式(12)(16)）も等しくなる。
σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x（式(15)）
=g1y・(a1+c・a3+x)・g2y・(a2+c・a4+x)・(g1b1・g2b2)x・(g1b3・g2b4)d・x（式(7)(8), B1,B2の定義）
=(g1a1・g2a2)y・(g1a3・g2a4)c・y・(g1・g2)x・y・g1x(b1+d・b3)・g2x(b2+d・b4)
=A1y・A2 c・y・X1y・X2y・X1(b1+d・b3)・X2(b2+d・b4)（式(4)(5), A1,A2の定義）
= A1y・A2 c・y・X1(b1+d・b3+y)・X2(b2+d・b4+y)
=式(11)
【００４１】
＜本形態の効果＞
本形態の鍵共有方式において、第１装置１０及び第２装置２０の計算量は、それぞれ、有限群G上での指数演算３回に相当する。また、第１装置１０及び第２装置２０の送信情報量（id情報以外）は、有限群Gの２要素のサイズに相当する。また、この方式の安全性は、標準モデルで安全であることが示される。
【００４２】
従来の方式の中で最も効率の良い鍵共有方式であるMQV方式の場合、それぞれの利用者の計算量は、有限群G上の指数演算２回に相当する。また、それぞれの利用者の送信情報量（id情報以外）は、有限群Gの１要素のサイズに相当する。しかし、MQV方式の安全性は証明されておらず、それをほぼ同等な性能を持つHMQVやCMQV方式では、ランダムオラクルモデルで安全であることが示されるが、標準モデルでは示されない。
以上より、本形態の方式が、従来の方式とほぼ同等の効率でありながら、安全性ではそれらの方式よりも優れていることが分かる。
【００４３】
＜本形態の方式の安全性＞
K*を目的のセッションで共有される鍵とし、R*←U {0,1}|K*|とし、b* ←U {0,1}とする。攻撃者Mによるテスト要求に対する応答として、b*=0であればK*が攻撃者Mに与えられ、そうでなければR*が攻撃者Mに与えられる。そして、最終的に攻撃者Mはb∈{0,1}を出力する。これについて以下を定義する。
AdvAKEM(k) ← |Pr(b=b*)‐1/2| …(17)
ここで、以下の条件が満たされる場合、その鍵共有プロトコルは安全（eCK安全）であるといえる。
【００４４】
（条件１）第１装置−第２装置間でマッチングセッションが完全になされるのであれば、それによって両装置間で同じ鍵が算出される（又は両装置でエラー出力がなされる）。
（条件２）どのような確率的多項式時間攻撃者Mに対しても、AdvAKEM(k)がセキュリティパラメータkにおいて無視できる。
ここで、本形態の方式が上述の（条件１）を満たすことは明らかである。また、本形態の方式では、有限群GにおいてDDH仮定が保たれ、H1, H2が目的衝突困難ハッシュ関数であり、F, F1, F2が擬似ランダム関数であることから（条件２）を満たすことも証明できる。よって、本形態の方式は安全であるといえる。
【００４５】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。
例えば、本形態では、ステップＳ１０において{F1(rx)(a1, a2, a3, a4)+F2(a1, a2, a3, a4)(rx)} mod pを整数xとし、ステップＳ１６において{F1(ry)(b1, b2, b3, b4)+F2(b1, b2, b3, b4)(ry)} mod pを整数yとした。しかし、ステップＳ１０においてF1(rx)(a1, a2, a3, a4)+F2(a1, a2, a3, a4)(rx)を整数xとし、ステップＳ１６においてF1(ry)(b1, b2, b3, b4)+F2(b1, b2, b3, b4)(ry)を整数yとしてもよい。さらに、ステップＳ１０においてF1(rx)(a1, a2, a3, a4)とF2(a1, a2, a3, a4)(rx)との他の演算によって定まる値を整数xとし、ステップＳ１６においてF1(ry)(b1, b2, b3, b4)とF2(b1, b2, b3, b4)(ry)との他の演算によって定まる値を整数yとしてもよい。また、ステップＳ１０において秘密鍵a1, a2, a3, a4の一部とランダム値rxとを用いて整数xを生成し、ステップＳ１６において秘密鍵b1, b2, b3, b4の一部とランダム値ryとを用いて整数yを生成してもよい。
【００４６】
また、本形態では、ステップＳ２１，Ｓ２５において、演算結果Y1, Y2とid情報AとをH1関数入力値としたが、演算結果Y1, Y2と第１装置１０の公開鍵A1，A2とを含むその他の情報をH1関数入力値としてもよい。また、演算結果Y1, Y2の一方と公開鍵A1，A2とをH1関数入力値としてもよいし、演算結果Y1, Y2の一方と公開鍵A1，A2の一方とをH1関数入力値としてもよいし、演算結果Y1, Y2の一方とその他の情報とをH1関数入力値としてもよい。
また、本形態では、ステップＳ２２，Ｓ２６において、演算結果X1, X2とid情報AとをH2関数入力値としたが、演算結果X1, X2と第２装置２０の公開鍵B1，B2とを含むその他の情報をH2関数入力値としてもよい。また、演算結果X1, X2の一方と公開鍵B1，B2とをH2関数入力値としてもよいし、演算結果X1, X2の一方と公開鍵B1，B2の一方とをH2関数入力値としてもよいし、演算結果X1, X2の一方とその他の情報とをH2関数入力値としてもよい。
【００４７】
また、本形態では、ステップＳ２４，Ｓ２８において、演算結果σをシードとし、id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値を入力とした擬似ランダム関数Fσの関数値K=Fσ(A, B, X1, X2, Y1, Y2)を鍵Kとした。しかし、「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」の代わりに他の情報を用いることとしてもよい。例えば、「id情報A, Bと演算結果X1, X2, Y1, Y2とによって定まる値」の代わりに、「A1, A2, B1, B2, X1, X2, Y1, Y2によって定まる値」や「A1, B1, X1, X2, Y1, Y2によって定まる値」や「X1, X2, Y1, Y2によって定まる値」や「X1, X2, Y1, Y2の一部によって定まる値」やnull値等を用いてもよい。
【００４８】
また、ステップＳ１〜Ｓ８の各処理は、それらの情報が必要となるまでのその他の時点で実行されてもよい。また、ステップＳ５，Ｓ６を行わないこととしてもよい。その他、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００４９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００５０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００５３】
本発明の産業上の利用分野としては、例えば、共通鍵を共有して共通鍵暗号通信を行う暗号通信分野を例示できる。
【図面の簡単な説明】
【００５４】
【図１】図１（ａ）は、第１実施形態の鍵共有システムの構成を例示した図である。図１（ｂ）は、第１装置のハードウェア構成を例示したブロック図である。
【図２】図２は、第１実施形態の第１装置の機能構成を例示したブロック図である。
【図３】図３は、第２実施形態の第２装置の機能構成を例示したブロック図である。
【図４】図４は、本形態の鍵共有処理を説明するためのシーケンス図である。
【図５】図５は、本形態の鍵共有処理を説明するためのシーケンス図である。
【符号の説明】
【００５５】
１０ 第１装置
２０ 第２装置
【特許請求の範囲】
【請求項１】
第１装置と第２装置とで鍵を共有するための鍵共有方法であって、
整数a1, a2, a3, a4を第１装置の秘密鍵として第１装置の記憶部に格納する第１装置秘密鍵格納過程と、
g1, g2を有限群Gの元g1, g2∈Gとした場合における、有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈Gを第１装置の公開鍵として上記第１装置の記憶部に格納する第１公開鍵格納過程と、
整数b1, b2, b3, b4を第２装置の秘密鍵として第２装置の記憶部に格納する第２装置秘密鍵格納過程と、
有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈Gを第２装置の公開鍵として上記第２装置の記憶部に格納する第２公開鍵格納過程と、
上記第１装置の公開鍵A1, A2を上記第２装置の記憶部に格納する第３公開鍵格納過程と、
上記第２装置の公開鍵B1, B2を上記第１装置の記憶部に格納する第４公開鍵格納過程と、
第１装置のランダム値選択部が、ランダム値rxを選択し、当該ランダム値rxを上記第１装置の記憶部に格納する第１装置シード選択過程と、
第１装置の擬似ランダム関数演算部が、上記第１装置の記憶部から第１装置の秘密鍵a1, a2, a3, a4の少なくとも一部とランダム値rxとを読み込み、読み込んだ第１装置の秘密鍵によって定まる値を入力とし、ランダム値rxをシードとした擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と、ランダム値rxを入力とし、読み込んだ第１装置の秘密鍵によって定まる値をシードとした擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値と、によって定まる整数xを算出し、当該整数xを上記第１装置の記憶部に格納する第１装置擬似ランダム関数演算過程と、
第１装置の第１暗号化部が、上記第１装置の記憶部から整数xを読み込み、有限群G上での演算X1=g1x∈Gを行い、当該演算結果X1を上記第１装置の記憶部に格納する第１装置第１暗号化過程と、
第１装置の第２暗号化部が、上記第１装置の記憶部から整数xを読み込み、有限群G上での演算X2=g2x∈Gを行い、当該演算結果X2を上記第１装置の記憶部に格納する第１装置第２暗号化過程と、
第１装置の送信部が、少なくとも上記演算結果X1, X2を第２装置に送信する第１演算結果送信過程と、
少なくとも上記演算結果X1, X2を上記第２装置の記憶部に格納する第１演算結果格納過程と、
第２装置のランダム値選択部が、ランダム値ryを選択し、当該ランダム値ryを上記第２装置の記憶部に格納する第２装置シード選択過程と、
第２装置の擬似ランダム関数演算部が、上記第２装置の記憶部から第２装置の秘密鍵b1, b2, b3, b4の少なくとも一部とランダム値ryとを読み込み、読み込んだ第２装置の秘密鍵によって定まる値を入力とし、ランダム値ryをシードとした擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と、ランダム値ryを入力とし、読み込んだ第２装置の秘密鍵によって定まる値をシードとした擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値と、によって定まる整数yを算出し、当該整数yを上記第２装置の記憶部に格納する第２装置擬似ランダム関数演算過程と、
第２装置の第１暗号化部が、上記第２装置の記憶部から整数yを読み込み、有限群G上での演算Y1=g1y∈Gを行い、当該演算結果Y1を上記第２装置の記憶部に格納する第２装置第１暗号化過程と、
第２装置の第２暗号化部が、上記第２装置の記憶部から整数yを読み込み、有限群G上での演算Y2=g2y∈Gを行い、当該演算結果Y2を上記第２装置の記憶部に格納する第２装置第２暗号化過程と、
第２装置の送信部が、少なくとも上記演算結果Y1, Y2を第１装置に送信する第２演算結果送信過程と、
第２装置の第１関数演算部が、上記第２装置の記憶部から少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果cを上記第２装置の記憶部に格納する第２装置第１関数演算過程と、
第２装置の第２関数演算部が、上記第２装置の記憶部から少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果dを上記第２装置の記憶部に格納する第２装置第２関数演算過程と、
第２装置のシード演算部が、上記第２装置の記憶部から演算結果X1, X2, c, dと公開鍵A1, A2と秘密鍵b1, b2, b3, b4と整数yとを読み込み、有限群G上での演算σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・y∈Gを行い、当該演算結果σを上記第２装置の記憶部に格納する第２装置シード演算過程と、
第２装置の鍵演算部が、上記第２装置の記憶部から少なくとも演算結果σを読み込み、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとして上記第２装置の記憶部に格納する第２装置鍵演算過程と、
第１装置の第１関数演算部が、上記第１装置の記憶部から少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果cを上記第１装置の記憶部に格納する第１装置第１関数演算過程と、
第１装置の第２関数演算部が、上記第１装置の記憶部から少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果dを上記第１装置の記憶部に格納する第１装置第２関数演算過程と、
第１装置のシード演算部が、上記第１装置の記憶部から演算結果Y1, Y2, c, dと公開鍵B1, B2と秘密鍵a1, a2, a3, a4と整数xとを読み込み、有限群G上での演算σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x∈Gを行い、当該演算結果σを上記第１装置の記憶部に格納する第１装置シード演算過程と、
第１装置の鍵演算部が、上記第１装置の記憶部から少なくとも演算結果σを読み込み、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとして上記第１装置の記憶部に格納する第１装置鍵演算過程と、
を有することを特徴とする鍵共有方法。
【請求項２】
請求項１に記載の鍵共有方法であって、
上記第１装置擬似ランダム関数演算過程は、
第１装置の擬似ランダム関数演算部が、上記第１装置の記憶部からすべての秘密鍵a1, a2, a3, a4を読み込み、擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値との和に対する有限群Gの位数pを法とした剰余演算を行い、その演算結果{F1(rx)(a1, a2, a3, a4)+F2(a1, a2, a3, a4)(rx)} mod pを上記整数xとして算出する過程であり、
上記第２装置擬似ランダム関数演算過程は、
第２装置の擬似ランダム関数演算部が、上記第２装置の記憶部からすべての秘密鍵b1, b2, b3, b4を読み込み、擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値との和に対する有限群Gの位数pを法とした剰余演算を行い、その演算結果{F1(ry)(b1, b2, b3, b4)+F2(b1, b2, b3, b4)(ry)} mod pを上記整数yとして算出する過程である、
ことを特徴とする鍵共有方法。
【請求項３】
請求項１又は２に記載の鍵共有方法であって、
上記H1関数入力値は、
演算結果Y1, Y2と第１装置の公開鍵A1，A2とを含み、
上記H2関数入力値は、
演算結果X1, X2と第２装置の公開鍵B1，B2とを含む、
ことを特徴とする鍵共有方法。
【請求項４】
請求項１から３のいずれかに記載の鍵共有方法であって、
上記第２装置鍵演算過程は、
上記第２装置の記憶部から少なくとも演算結果X1, X2, Y1, Y2の一部を擬似ランダム関数入力値として読み込み、当該擬似ランダム関数入力値によって定まる値を入力とし、上記演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとする過程であり、
上記第１装置鍵演算過程は、
上記第１装置の記憶部から少なくとも演算結果X1, X2, Y1, Y2の一部を擬似ランダム関数入力値として読み込み、当該擬似ランダム関数入力値によって定まる値を入力とし、上記演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとする過程である、
ことを特徴とする鍵共有方法。
【請求項５】
請求項４に記載の鍵共有方法であって、
上記擬似ランダム関数入力値は、
演算結果X1, X2, Y1, Y2と第１装置の公開鍵A1，A2と第２装置の公開鍵B1，B2とを含む、
ことを特徴とする鍵共有方法。
【請求項６】
第２装置と鍵を共有する第１装置であって、
整数a1, a2, a3, a4を第１装置の秘密鍵として格納し、有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈Gを第１装置の公開鍵として格納し、有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈G（整数b1, b2, b3, b4は第２装置の秘密鍵）を第２装置の公開鍵として格納する記憶部と、
ランダム値rxを選択し、当該ランダム値rxを上記記憶部に格納するランダム値選択部と、
上記記憶部から第１装置の秘密鍵a1, a2, a3, a4の少なくとも一部とランダム値rxとを読み込み、読み込んだ第１装置の秘密鍵によって定まる値を入力とし、ランダム値rxをシードとした擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と、ランダム値rxを入力とし、読み込んだ第１装置の秘密鍵によって定まる値をシードとした擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値と、によって定まる整数xを算出し、当該整数xを上記記憶部に格納する擬似ランダム関数演算部と、
上記記憶部から整数xを読み込み、有限群G上での演算X1=g1x∈Gを行い、当該演算結果X1を上記記憶部に格納する第１暗号化部と、
上記記憶部から整数xを読み込み、有限群G上での演算X2=g2x∈Gを行い、当該演算結果X2を上記記憶部に格納する第２暗号化部と、
少なくとも上記演算結果X1, X2を第２装置に送信する送信部と、
第２装置から送信された演算結果Y1, Y2を受信して上記記憶部に格納する受信部と、
上記記憶部から少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果cを上記記憶部に格納する第１関数演算部と、
上記記憶部から少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果dを上記記憶部に格納する第２関数演算部と、
上記記憶部から演算結果Y1, Y2, c, dと公開鍵B1, B2と秘密鍵a1, a2, a3, a4と整数xとを読み込み、有限群G上での演算σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x∈Gを行い、当該演算結果σを上記記憶部に格納するシード演算部と、
上記記憶部から少なくとも演算結果σを読み込み、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとして上記記憶部に格納する鍵演算部と、
を有することを特徴とする第１装置。
【請求項７】
第１装置と鍵を共有する第２装置であって、
整数b1, b2, b3, b4を第２装置の秘密鍵として格納し、有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈Gを第２装置の公開鍵として格納し、有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈G（整数a1, a2, a3, a4は第１装置の秘密鍵）を第１装置の公開鍵として格納する記憶部と、
第１装置から送信された演算結果X1, X2を受信して上記記憶部に格納する受信部と、
ランダム値ryを選択し、当該ランダム値ryを上記記憶部に格納するランダム値選択部と、
上記記憶部から第２装置の秘密鍵b1, b2, b3, b4の少なくとも一部とランダム値ryとを読み込み、読み込んだ第２装置の秘密鍵によって定まる値を入力とし、ランダム値ryをシードとした擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と、ランダム値ryを入力とし、読み込んだ第２装置の秘密鍵によって定まる値をシードとした擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値と、によって定まる整数yを算出し、当該整数yを上記記憶部に格納する擬似ランダム関数演算部と、
上記記憶部から整数yを読み込み、有限群G上での演算Y1=g1y∈Gを行い、当該演算結果Y1を上記記憶部に格納する第１暗号化部と、
上記記憶部から整数yを読み込み、有限群G上での演算Y2=g2y∈Gを行い、当該演算結果Y2を上記記憶部に格納する第２暗号化部と、
少なくとも上記演算結果Y1, Y2を第１装置に送信する送信部と、
上記記憶部から少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果cを上記記憶部に格納する第１関数演算部と、
上記記憶部から少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果dを上記記憶部に格納する第２関数演算部と、
上記記憶部から演算結果X1, X2, c, dと公開鍵A1, A2と秘密鍵b1, b2, b3, b4と整数yとを読み込み、有限群G上での演算σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・y∈Gを行い、当該演算結果σを上記記憶部に格納するシード演算部と、
記憶部から少なくとも演算結果σを読み込み、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとして記憶部に格納する鍵演算部と、
を有することを特徴とする第２装置。
【請求項８】
請求項６に記載の第１装置としてコンピュータを機能させるためのプログラム。
【請求項９】
請求項７に記載の第２装置としてコンピュータを機能させるためのプログラム。
【請求項１】
第１装置と第２装置とで鍵を共有するための鍵共有方法であって、
整数a1, a2, a3, a4を第１装置の秘密鍵として第１装置の記憶部に格納する第１装置秘密鍵格納過程と、
g1, g2を有限群Gの元g1, g2∈Gとした場合における、有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈Gを第１装置の公開鍵として上記第１装置の記憶部に格納する第１公開鍵格納過程と、
整数b1, b2, b3, b4を第２装置の秘密鍵として第２装置の記憶部に格納する第２装置秘密鍵格納過程と、
有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈Gを第２装置の公開鍵として上記第２装置の記憶部に格納する第２公開鍵格納過程と、
上記第１装置の公開鍵A1, A2を上記第２装置の記憶部に格納する第３公開鍵格納過程と、
上記第２装置の公開鍵B1, B2を上記第１装置の記憶部に格納する第４公開鍵格納過程と、
第１装置のランダム値選択部が、ランダム値rxを選択し、当該ランダム値rxを上記第１装置の記憶部に格納する第１装置シード選択過程と、
第１装置の擬似ランダム関数演算部が、上記第１装置の記憶部から第１装置の秘密鍵a1, a2, a3, a4の少なくとも一部とランダム値rxとを読み込み、読み込んだ第１装置の秘密鍵によって定まる値を入力とし、ランダム値rxをシードとした擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と、ランダム値rxを入力とし、読み込んだ第１装置の秘密鍵によって定まる値をシードとした擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値と、によって定まる整数xを算出し、当該整数xを上記第１装置の記憶部に格納する第１装置擬似ランダム関数演算過程と、
第１装置の第１暗号化部が、上記第１装置の記憶部から整数xを読み込み、有限群G上での演算X1=g1x∈Gを行い、当該演算結果X1を上記第１装置の記憶部に格納する第１装置第１暗号化過程と、
第１装置の第２暗号化部が、上記第１装置の記憶部から整数xを読み込み、有限群G上での演算X2=g2x∈Gを行い、当該演算結果X2を上記第１装置の記憶部に格納する第１装置第２暗号化過程と、
第１装置の送信部が、少なくとも上記演算結果X1, X2を第２装置に送信する第１演算結果送信過程と、
少なくとも上記演算結果X1, X2を上記第２装置の記憶部に格納する第１演算結果格納過程と、
第２装置のランダム値選択部が、ランダム値ryを選択し、当該ランダム値ryを上記第２装置の記憶部に格納する第２装置シード選択過程と、
第２装置の擬似ランダム関数演算部が、上記第２装置の記憶部から第２装置の秘密鍵b1, b2, b3, b4の少なくとも一部とランダム値ryとを読み込み、読み込んだ第２装置の秘密鍵によって定まる値を入力とし、ランダム値ryをシードとした擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と、ランダム値ryを入力とし、読み込んだ第２装置の秘密鍵によって定まる値をシードとした擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値と、によって定まる整数yを算出し、当該整数yを上記第２装置の記憶部に格納する第２装置擬似ランダム関数演算過程と、
第２装置の第１暗号化部が、上記第２装置の記憶部から整数yを読み込み、有限群G上での演算Y1=g1y∈Gを行い、当該演算結果Y1を上記第２装置の記憶部に格納する第２装置第１暗号化過程と、
第２装置の第２暗号化部が、上記第２装置の記憶部から整数yを読み込み、有限群G上での演算Y2=g2y∈Gを行い、当該演算結果Y2を上記第２装置の記憶部に格納する第２装置第２暗号化過程と、
第２装置の送信部が、少なくとも上記演算結果Y1, Y2を第１装置に送信する第２演算結果送信過程と、
第２装置の第１関数演算部が、上記第２装置の記憶部から少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果cを上記第２装置の記憶部に格納する第２装置第１関数演算過程と、
第２装置の第２関数演算部が、上記第２装置の記憶部から少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果dを上記第２装置の記憶部に格納する第２装置第２関数演算過程と、
第２装置のシード演算部が、上記第２装置の記憶部から演算結果X1, X2, c, dと公開鍵A1, A2と秘密鍵b1, b2, b3, b4と整数yとを読み込み、有限群G上での演算σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・y∈Gを行い、当該演算結果σを上記第２装置の記憶部に格納する第２装置シード演算過程と、
第２装置の鍵演算部が、上記第２装置の記憶部から少なくとも演算結果σを読み込み、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとして上記第２装置の記憶部に格納する第２装置鍵演算過程と、
第１装置の第１関数演算部が、上記第１装置の記憶部から少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果cを上記第１装置の記憶部に格納する第１装置第１関数演算過程と、
第１装置の第２関数演算部が、上記第１装置の記憶部から少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果dを上記第１装置の記憶部に格納する第１装置第２関数演算過程と、
第１装置のシード演算部が、上記第１装置の記憶部から演算結果Y1, Y2, c, dと公開鍵B1, B2と秘密鍵a1, a2, a3, a4と整数xとを読み込み、有限群G上での演算σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x∈Gを行い、当該演算結果σを上記第１装置の記憶部に格納する第１装置シード演算過程と、
第１装置の鍵演算部が、上記第１装置の記憶部から少なくとも演算結果σを読み込み、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとして上記第１装置の記憶部に格納する第１装置鍵演算過程と、
を有することを特徴とする鍵共有方法。
【請求項２】
請求項１に記載の鍵共有方法であって、
上記第１装置擬似ランダム関数演算過程は、
第１装置の擬似ランダム関数演算部が、上記第１装置の記憶部からすべての秘密鍵a1, a2, a3, a4を読み込み、擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値との和に対する有限群Gの位数pを法とした剰余演算を行い、その演算結果{F1(rx)(a1, a2, a3, a4)+F2(a1, a2, a3, a4)(rx)} mod pを上記整数xとして算出する過程であり、
上記第２装置擬似ランダム関数演算過程は、
第２装置の擬似ランダム関数演算部が、上記第２装置の記憶部からすべての秘密鍵b1, b2, b3, b4を読み込み、擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値との和に対する有限群Gの位数pを法とした剰余演算を行い、その演算結果{F1(ry)(b1, b2, b3, b4)+F2(b1, b2, b3, b4)(ry)} mod pを上記整数yとして算出する過程である、
ことを特徴とする鍵共有方法。
【請求項３】
請求項１又は２に記載の鍵共有方法であって、
上記H1関数入力値は、
演算結果Y1, Y2と第１装置の公開鍵A1，A2とを含み、
上記H2関数入力値は、
演算結果X1, X2と第２装置の公開鍵B1，B2とを含む、
ことを特徴とする鍵共有方法。
【請求項４】
請求項１から３のいずれかに記載の鍵共有方法であって、
上記第２装置鍵演算過程は、
上記第２装置の記憶部から少なくとも演算結果X1, X2, Y1, Y2の一部を擬似ランダム関数入力値として読み込み、当該擬似ランダム関数入力値によって定まる値を入力とし、上記演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとする過程であり、
上記第１装置鍵演算過程は、
上記第１装置の記憶部から少なくとも演算結果X1, X2, Y1, Y2の一部を擬似ランダム関数入力値として読み込み、当該擬似ランダム関数入力値によって定まる値を入力とし、上記演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとする過程である、
ことを特徴とする鍵共有方法。
【請求項５】
請求項４に記載の鍵共有方法であって、
上記擬似ランダム関数入力値は、
演算結果X1, X2, Y1, Y2と第１装置の公開鍵A1，A2と第２装置の公開鍵B1，B2とを含む、
ことを特徴とする鍵共有方法。
【請求項６】
第２装置と鍵を共有する第１装置であって、
整数a1, a2, a3, a4を第１装置の秘密鍵として格納し、有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈Gを第１装置の公開鍵として格納し、有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈G（整数b1, b2, b3, b4は第２装置の秘密鍵）を第２装置の公開鍵として格納する記憶部と、
ランダム値rxを選択し、当該ランダム値rxを上記記憶部に格納するランダム値選択部と、
上記記憶部から第１装置の秘密鍵a1, a2, a3, a4の少なくとも一部とランダム値rxとを読み込み、読み込んだ第１装置の秘密鍵によって定まる値を入力とし、ランダム値rxをシードとした擬似ランダム関数F1(rx)(a1, a2, a3, a4)の関数値と、ランダム値rxを入力とし、読み込んだ第１装置の秘密鍵によって定まる値をシードとした擬似ランダム関数F2(a1, a2, a3, a4)(rx)の関数値と、によって定まる整数xを算出し、当該整数xを上記記憶部に格納する擬似ランダム関数演算部と、
上記記憶部から整数xを読み込み、有限群G上での演算X1=g1x∈Gを行い、当該演算結果X1を上記記憶部に格納する第１暗号化部と、
上記記憶部から整数xを読み込み、有限群G上での演算X2=g2x∈Gを行い、当該演算結果X2を上記記憶部に格納する第２暗号化部と、
少なくとも上記演算結果X1, X2を第２装置に送信する送信部と、
第２装置から送信された演算結果Y1, Y2を受信して上記記憶部に格納する受信部と、
上記記憶部から少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果cを上記記憶部に格納する第１関数演算部と、
上記記憶部から少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果dを上記記憶部に格納する第２関数演算部と、
上記記憶部から演算結果Y1, Y2, c, dと公開鍵B1, B2と秘密鍵a1, a2, a3, a4と整数xとを読み込み、有限群G上での演算σ=Y1(a1+c・a3+x)・Y2(a2+c・a4+x)・B1x・B2d・x∈Gを行い、当該演算結果σを上記記憶部に格納するシード演算部と、
上記記憶部から少なくとも演算結果σを読み込み、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとして上記記憶部に格納する鍵演算部と、
を有することを特徴とする第１装置。
【請求項７】
第１装置と鍵を共有する第２装置であって、
整数b1, b2, b3, b4を第２装置の秘密鍵として格納し、有限群G上での演算結果B1=g1b1・g2b2∈G，B2=g1b3・g2b4∈Gを第２装置の公開鍵として格納し、有限群G上での演算結果A1=g1a1・g2a2∈G，A2=g1a3・g2a4∈G（整数a1, a2, a3, a4は第１装置の秘密鍵）を第１装置の公開鍵として格納する記憶部と、
第１装置から送信された演算結果X1, X2を受信して上記記憶部に格納する受信部と、
ランダム値ryを選択し、当該ランダム値ryを上記記憶部に格納するランダム値選択部と、
上記記憶部から第２装置の秘密鍵b1, b2, b3, b4の少なくとも一部とランダム値ryとを読み込み、読み込んだ第２装置の秘密鍵によって定まる値を入力とし、ランダム値ryをシードとした擬似ランダム関数F1(ry)(b1, b2, b3, b4)の関数値と、ランダム値ryを入力とし、読み込んだ第２装置の秘密鍵によって定まる値をシードとした擬似ランダム関数F2(b1, b2, b3, b4)(ry)の関数値と、によって定まる整数yを算出し、当該整数yを上記記憶部に格納する擬似ランダム関数演算部と、
上記記憶部から整数yを読み込み、有限群G上での演算Y1=g1y∈Gを行い、当該演算結果Y1を上記記憶部に格納する第１暗号化部と、
上記記憶部から整数yを読み込み、有限群G上での演算Y2=g2y∈Gを行い、当該演算結果Y2を上記記憶部に格納する第２暗号化部と、
少なくとも上記演算結果Y1, Y2を第１装置に送信する送信部と、
上記記憶部から少なくとも演算結果Y1, Y2の一方を含む情報をH1関数入力値として読み込み、当該H1関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H1を作用させ、その演算結果cを上記記憶部に格納する第１関数演算部と、
上記記憶部から少なくとも演算結果X1, X2の一方を含む情報をH2関数入力値として読み込み、当該H2関数入力値によって定まる値に対し、値域を整数とする目的衝突困難なハッシュ関数H2を作用させ、その演算結果dを上記記憶部に格納する第２関数演算部と、
上記記憶部から演算結果X1, X2, c, dと公開鍵A1, A2と秘密鍵b1, b2, b3, b4と整数yとを読み込み、有限群G上での演算σ=X1(b1+d・b3+y)・X2(b2+d・b4+y)・A1y・A2c・y∈Gを行い、当該演算結果σを上記記憶部に格納するシード演算部と、
記憶部から少なくとも演算結果σを読み込み、当該演算結果σをシードとした擬似ランダム関数Fσの関数値を算出し、その関数値を鍵Kとして記憶部に格納する鍵演算部と、
を有することを特徴とする第２装置。
【請求項８】
請求項６に記載の第１装置としてコンピュータを機能させるためのプログラム。
【請求項９】
請求項７に記載の第２装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００９−１３０８７２（Ｐ２００９−１３０８７２Ａ）
【公開日】平成２１年６月１１日（２００９．６．１１）
【国際特許分類】
【出願番号】特願２００７−３０６７３８（Ｐ２００７−３０６７３８）
【出願日】平成１９年１１月２８日（２００７．１１．２８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２１年６月１１日（２００９．６．１１）
【国際特許分類】
【出願日】平成１９年１１月２８日（２００７．１１．２８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]