(57)【要約】【課題】計算装置と鍵管理装置との間の信頼関係が確保できない環境であっても、計算装置を正しく動作させる。【解決手段】計算装置が、元Ｅに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を得、鍵を保持する鍵管理装置が、第一入力情報τ１を用いてｆ（τ１）を正しく計算可能であり、その計算結果を第一出力情報ｚ１とし、第二入力情報τ２を用いてｆ（τ２）を正しく計算可能であり、その計算結果を第二出力情報ｚ２とする。計算装置は、第一出力情報ｚ１から計算結果ｕ＝ｆ（Ｅ）ｂｘ１を得、第二出力情報ｚ２から計算結果ｖ＝ｆ（Ｅ）ａｘ２を得、計算結果ｕ及びｖがｕａ＝ｖｂを満たす場合にａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕｂ’ｖａ’を得、ｕａ＝ｖｂを満たさない場合に処理を終了する。【選択図】図３
2014137562.tif 000002
【特許請求の範囲】
【請求項１】
計算装置と鍵を保持する鍵管理装置とを有し、
Ｇ，Ｈが群、ｆ（Ｅ）が前記鍵と前記群Ｈの元Ｅとに対応する前記群Ｇの元を得る準同型関数、Ｘ1，Ｘ2が前記群Ｇに値を持つ確率変数、ｘ1が確率変数Ｘ1の実現値、ｘ2が確率変数Ｘ2の実現値、ａ，ｂが互いに素である自然数であり、
前記計算装置が、
前記元Ｅに対応する、前記群Ｈの元である第一入力情報τ1及び第二入力情報τ2を得る入力情報提供部を含み、
前記鍵管理装置が、
前記第一入力情報τ1を用いてｆ（τ1）を正しく計算可能であり、得られた計算結果を第一出力情報ｚ1とする第一出力情報計算部と、
前記第二入力情報τ2を用いてｆ（τ2）を正しく計算可能であり、得られた計算結果を第二出力情報ｚ2とする第二出力情報計算部と、を含み、
前記計算装置が、さらに
前記第一出力情報ｚ1から計算結果ｕ＝ｆ（Ｅ）bｘ1を得る第一計算部と、
前記第二出力情報ｚ2から計算結果ｖ＝ｆ（Ｅ）aｘ2を得る第二計算部と、
前記計算結果ｕ及びｖがｕa＝ｖｂを満たす場合にａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕb’ｖa’を得、ｕa＝ｖｂを満たさない場合に前記計算装置の処理を終了させる計算制御部と、を含む計算システム。
【請求項２】
請求項１の計算システムであって、
前記群Ｈが前記群Ｇの直積群Ｇ×Ｇ、前記群Ｇが可換群、前記元Ｅが暗号文（ｃ1，ｃ2）∈Ｈであり、ｆ（Ｅ）が前記鍵を用いて前記暗号文（ｃ1，ｃ2）を復号するための復号関数ｆ（ｃ1，ｃ2）である、計算システム。
【請求項３】
請求項２の計算システムであって、
前記第一入力情報がτ1＝（ｃ1bＲ1ｙｒ1，ｃ2bｇｒ1）、前記第二入力情報がτ2＝（ｃ1aＲ2ｙｒ2，ｃ2aｇｒ2）、Ｒ1，Ｒ2がランダムに選択された前記群Ｇの元、ｒ１，ｒ２がランダムに選択された自然数、ｕ＝ｚ１Ｒ１−１、ｖ＝ｚ２Ｒ２−１である、計算システム。
【請求項４】
請求項１の計算システムであって、
前記群Ｈが前記群Ｇ、ｇが前記群Ｇの生成元、前記鍵が前記計算装置の秘密鍵ｓ、ｔが他の計算装置の秘密鍵、Ｂが前記他の計算装置の公開鍵ｇt、Ａ＾が前記計算装置に対応する公開情報、Ｂ＾が前記他の計算装置に対応する公開情報、ｆ（Ｅ）が前記群Ｇの元Ｅから元Ｅｓを得る関数であり、
前記計算装置が、さらに
乱数ｘについての前記群Ｇの元Ｘ＝ｇｘを得る第三計算部と、
前記公開情報Ｂ＾と前記元Ｘとに対応する値ｄを得る第四計算部と、
前記公開情報Ａ＾と前記他の計算装置で得られた前記群Ｇの元Ｙとに対応する値ｅを得る第五計算部と、
前記群Ｇの元Ｅ＝ＹＢｅを得る第六計算部と、
Ｅｘ（ｕb’ｖa’）ｄに対応する共通鍵Ｋを得る共通鍵生成部と、
を含む計算システム。
【請求項５】
請求項１の計算システムであって、
乱数ｘを生成する乱数装置をさらに有し、
前記群Ｈが前記群Ｇ、ｇが前記群Ｇの生成元、前記鍵が前記計算装置の秘密鍵ｓ、Ｂが前記他の計算装置の公開鍵ｇt、Ａ＾が前記計算装置に対応する公開情報、Ｂ＾が前記他の計算装置に対応する公開情報、ｆ（Ｅ）が前記群Ｇの元Ｅから元Ｅｓを得る関数、ｆ’（Ｅ）が前記群Ｇの元Ｅから元Ｅｘを得る準同型関数、Ｘ3，Ｘ4が前記群Ｇに値を持つ確率変数、ｘ3が確率変数Ｘ3の実現値、ｘ4が確率変数Ｘ4の実現値、ｉ，ｊが互いに素である自然数であり、
前記計算装置が、さらに
前記公開情報Ｂ＾と元Ｘ＝ｇｘとに対応する値ｄを得る第四計算部と、
前記公開情報Ａ＾と前記他の計算装置で得られた前記群Ｇの元Ｙとに対応する値ｅを得る第五計算部と、
前記群Ｇの元Ｅ＝ＹＢｅを得る第六計算部と、を含み、
前記乱数装置が、
前記元Ｅに対応する前記群Ｇの元である第三入力情報τ3を用いてｆ’（τ3）を正しく計算可能であり、得られた計算結果を第三出力情報ｚ3とする第三出力情報計算部と、
前記元Ｅに対応する前記群Ｇの元である第四入力情報τ4を用いてを用いてｆ’（τ4）を正しく計算可能であり、得られた計算結果を第四出力情報ｚ4とする第四出力情報計算部と、を含み、
前記計算装置が、さらに
前記第三出力情報ｚ3から計算結果μ＝ｆ’（Ｅ）ｊｘ3を得る第七計算部と、
前記第四出力情報ｚ4から計算結果ω＝ｆ’（Ｅ）ｉｘ4を得る第八計算部と、
前記計算結果μ及びωがμｉ＝ωｊを満たす場合にｉ’ｉ＋ｊ’ｊ＝１を満たす整数ｉ’，ｊ’についてのμｊ’ωｉ’を得る第九計算部と、
（μｊ’ωｉ’）（ｕb’ｖa’）ｄに対応する共通鍵Ｋを得る共通鍵生成部と、
を含む計算システム。
【請求項６】
請求項５の計算システムであって、
μｉ＝ωｊを満たさない場合、前記計算装置は、新たな第三出力情報ｚ3及び第四出力情報ｚ4を得ることなく処理を終了する、計算システム。
【請求項７】
請求項１から６の何れかの計算システムであって、
ｕa＝ｖｂを満たさない場合、前記計算装置は、新たな第一出力情報ｚ1及び第二出力情報ｚ2を得ることなく処理を終了する、計算システム。
【請求項８】
Ｇ，Ｈが群、ｆ（Ｅ）が鍵と前記群Ｈの元Ｅとに対応する前記群Ｇの元を得る準同型関数、Ｘ1，Ｘ2が前記群Ｇに値を持つ確率変数、ｘ1が確率変数Ｘ1の実現値、ｘ2が確率変数Ｘ2の実現値、ａ，ｂが互いに素である自然数であり、
計算結果ｕ＝ｆ（Ｅ）bｘ1を得る第一計算部と、
計算結果ｖ＝ｆ（Ｅ）aｘ2を得る第二計算部と、
前記計算結果ｕ及びｖがｕa＝ｖｂを満たす場合にａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕb’ｖa’を得、ｕa＝ｖｂを満たさない場合に処理を終了させる計算制御部と、を有する計算装置。
【請求項９】
請求項８の計算装置であって、
前記群Ｈが前記群Ｇの直積群Ｇ×Ｇ、前記群Ｇが可換群、前記元Ｅが暗号文（ｃ1，ｃ2）∈Ｈであり、ｆ（Ｅ）が前記鍵を用いて前記暗号文（ｃ1，ｃ2）を復号するための復号関数ｆ（ｃ1，ｃ2）である、計算装置。
【請求項１０】
請求項８の計算装置であって、
前記群Ｈが前記群Ｇ、ｇが前記群Ｇの生成元、前記鍵が前記計算装置の秘密鍵ｓ、ｔが他の計算装置の秘密鍵、Ｂが前記他の計算装置の公開鍵ｇt、Ａ＾が前記計算装置に対応する公開情報、Ｂ＾が前記他の計算装置に対応する公開情報、ｆ（Ｅ）が前記群Ｇの元Ｅから元Ｅｓを得る関数であり、
乱数ｘについての前記群Ｇの元Ｘ＝ｇｘを得る第三計算部と、
前記公開情報Ｂ＾と前記元Ｘとに対応する値ｄを得る第四計算部と、
前記公開情報Ａ＾と前記他の計算装置で得られた前記群Ｇの元Ｙとに対応する値ｅを得る第五計算部と、
前記群Ｇの元Ｅ＝ＹＢｅを得る第六計算部と、
Ｅｘ（ｕb’ｖa’）ｄに対応する共通鍵Ｋを得る共通鍵生成部と、
をさらに有する計算装置。
【請求項１１】
請求項８の計算装置であって、
前記群Ｈが前記群Ｇ、ｇが前記群Ｇの生成元、前記鍵が前記計算装置の秘密鍵ｓ、ｔが他の計算装置の秘密鍵、Ｂが前記他の計算装置の公開鍵ｇt、Ａ＾が前記計算装置に対応する公開情報、Ｂ＾が前記他の計算装置に対応する公開情報、ｘが乱数、ｆ（Ｅ）が前記群Ｇの元Ｅから元Ｅｓを得る関数、ｆ’（Ｅ）が前記群Ｇの元Ｅから元Ｅｘを得る準同型関数、Ｘ3，Ｘ4が前記群Ｇに値を持つ確率変数、ｘ3が確率変数Ｘ3の実現値、ｘ4が確率変数Ｘ4の実現値、ｉ，ｊが互いに素である自然数であり、
前記公開情報Ｂ＾と元Ｘ＝ｇｘとに対応する値ｄを得る第四計算部と、
前記公開情報Ａ＾と前記他の計算装置で得られた前記群Ｇの元Ｙとに対応する値ｅを得る第五計算部と、
前記群Ｇの元Ｅ＝ＹＢｅを得る第六計算部と、
計算結果μ＝ｆ’（Ｅ）ｊｘ3を得る第七計算部と、
計算結果ω＝ｆ’（Ｅ）ｉｘ4を得る第八計算部と、
前記計算結果μ及びωがμｉ＝ωｊを満たす場合にｉ’ｉ＋ｊ’ｊ＝１を満たす整数ｉ’，ｊ’についてのμｊ’ωｉ’を得る第九計算部と、
（μｊ’ωｉ’）（ｕb’ｖa’）ｄに対応する共通鍵Ｋを得る共通鍵生成部と、
をさらに有する計算装置。
【請求項１２】
請求項７から１１の何れかの計算装置の各部としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関し、特に鍵管理技術に関する。
【背景技術】
【０００２】
公開鍵暗号技術を用いた暗号、鍵共有、認証方式が広く知られている。例えばＥｌＧａｍａｌ暗号（例えば、非特許文献１参照）、ＲＳＡ暗号、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有、Ｍｅｎｅｚｅｓ−Ｑｕ−Ｖａｎｓｔｏｎｅ（ＭＱＶ）鍵共有、ＨａｓｈｅｄＭＱＶ（ＨＭＱＶ）鍵共有（例えば、非特許文献２参照）などの方式がある。また、鍵共有を用いれば認証が可能である。
【０００３】
これらの方式で暗号や認証を利用しようとするとき、各利用者は秘密鍵を安全に保持する必要がある。特に、コンピュータの内部に秘密鍵を保持するときには、コンピュータの上で動作するアプリケーションプログラムや、オペレーティングシステム内部のプログラム（デバイスドライバなど）に不正プログラムが混入されて、秘密鍵を不正に読み取られるリスクがある問題があった。そのため、従来技術ではコンピュータのオペレーティングシステムよりも下位のレイヤにおいて鍵を管理するための仕組みを設ける場合がある。例えばＴＰＭと呼ばれる技術では、専用の半導体チップをコンピュータのハードウエアに内蔵させて、その内部に鍵を保持することで、ソフトウエアによる鍵の不正読み取りを防止している。
【０００４】
また、プロセッサによっては複数の動作モードを持ち、オペレーティングシステムを動作させるためのモードと、鍵を操作して暗号や認証の処理を行うモードを分けることができる場合がある。オペレーティングシステムの下位レイヤで動作するＢＩＯＳ等のプログラムからこのような複数のモードを使い分けることで、オペレーティングシステム上のプログラムが鍵を不正に読み取ることを防止することができる。
【０００５】
これらの従来技術は、オペレーティングシステムと、鍵管理システムの両方の機能を備えて、オペレーティングシステムから鍵管理システムを用いて暗号や認証のための計算が可能な仕組みといえる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Taher ElGamal, A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory, v. IT-31, n. 4, 1985, pp. 469-472 or CRYPTO 84, pp. 10-18, Springer-Verlag.
【非特許文献２】Krawczyk H., “HMQV: A high-performance secure Diffie-Hellman protocol,” Advances in Cryptology-CRYPTO 2005, LNCS, vol.3621, pp. 546-566, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術には、オペレーティングシステムと鍵管理システムの間の相互の信頼関係を確保することが難しい場合、第三のシステムが鍵管理システムを詐称して、オペレーティングシステムの動作を誤らせることができてしまうという課題がある。例えば、鍵管理システムがシステムの下位レイヤで動作し、その直上ではハードウエア仮想化ソフトウエアが動作し、オペレーティングシステムは仮想ハードウエアの上で動作するようなシステムが考えられる。このとき、ハードウエア仮想化ソフトウエアが鍵管理システムとオペレーティングシステムの間のやりとりに介入し、オペレーティングシステムの動作を誤らせることが考えられる。
【０００８】
本発明はこのような点に鑑み、オペレーティングシステムなどの計算装置と鍵管理システムなどの鍵管理装置との間の信頼関係が確保できない環境であっても、計算装置を正しく動作させることができる技術を提供する。
【課題を解決するための手段】
【０００９】
計算装置が、元Ｅに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を得、鍵を保持する鍵管理装置が、第一入力情報τ１を用いてｆ（τ１）を正しく計算可能であり、その計算結果を第一出力情報ｚ１とし、第二入力情報τ２を用いてｆ（τ２）を正しく計算可能であり、その計算結果を第二出力情報ｚ２とする。計算装置は、第一出力情報ｚ１から計算結果ｕ＝ｆ（Ｅ）ｂｘ１を得、第二出力情報ｚ２から計算結果ｖ＝ｆ（Ｅ）ａｘ２を得、計算結果ｕ及びｖがｕａ＝ｖｂを満たす場合にａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕｂ’ｖａ’を得、ｕａ＝ｖｂを満たさない場合に処理を終了する。ただし、Ｇ，Ｈが群、ｆ（Ｅ）が鍵と群Ｈの元Ｅとに対応する群Ｇの元を得る準同型関数、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素である自然数である。
【発明の効果】
【００１０】
本発明では、上述のような自己訂正技術を用いるため、計算装置と鍵管理装置との間の信頼関係が確保できない環境であっても、計算装置を正しく動作させることができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、実施形態の計算システムを例示するためのブロック図である。
【図２】図２Ａは、第一実施形態の計算装置を例示するためのブロック図である。図２Ｂは、第一、二実施形態の鍵管理装置を例示するためのブロック図である。
【図３】図３は、第一、二実施形態の自己訂正部を例示するためのブロック図である。
【図４】図４は、第一、二実施形態の自己訂正処理を例示するためのフロー図である。
【図５】図５は、第一、二実施形態の鍵管理装置の処理を例示するためのフロー図である。
【図６】図６は、第二実施形態の計算装置を例示するためのブロック図である。
【図７】図７は、第二実施形態の計算装置を例示するためのブロック図である。
【図８】図８は、第二実施形態の鍵管理装置を例示するためのブロック図である。
【図９】図９Ａ及び図９Ｂは、第二実施形態の計算装置の処理を例示するためのフロー図である。
【図１０】図１０は、第三実施形態の計算装置を例示するためのブロック図である。
【図１１】図１１は、第三実施形態の計算装置を例示するためのブロック図である
【図１２】図１２Ａは、第三実施形態の鍵管理装置を例示するためのブロック図である。図１２Ｂは、第三実施形態の乱数装置を例示するためのブロック図である。
【図１３】図１３は、第三実施形態の自己訂正部を例示するためのブロック図である。
【図１４】図１４Ａ及び図１４Ｂは、第三実施形態の計算装置の処理を例示するためのフロー図である。
【図１５】図１５は、第三実施形態の自己訂正処理を例示するためのフロー図である。
【図１６】図１６は、第三実施形態の鍵管理装置の処理を例示するためのフロー図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施形態を説明する。
各実施形態では、オペレーティングシステムなどの計算装置で暗号技術を用いた計算を行う際に、鍵を保持する鍵管理装置での計算結果を直接用いるのではなく、自己訂正技術を用いて鍵管理装置を呼び出して計算を行い、鍵を用いた計算の正しさが確保できないときに処理を終了する。すなわち、計算装置が元Ｅに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を得て出力し、鍵管理装置が、第一入力情報τ１を用いてｆ（τ１）を正しく計算可能であり、その計算結果を第一出力情報ｚ１とし、第二入力情報τ２を用いてｆ（τ２）を正しく計算可能であり、その計算結果を第二出力情報ｚ２とする。計算装置は、第一出力情報ｚ１から計算結果ｕ＝ｆ（Ｅ）ｂｘ１を得、第二出力情報ｚ２から計算結果ｖ＝ｆ（Ｅ）ａｘ２を得、計算結果ｕ及びｖがｕａ＝ｖｂを満たす場合にａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕｂ’ｖａ’を得、ｕａ＝ｖｂを満たさない場合に処理を終了する。ただし、Ｇ，Ｈが群（例えば、可換群）、ｆ（Ｅ）が鍵と群Ｈの元Ｅとに対応する群Ｇの元を得る準同型関数、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素である自然数である。以上より、計算装置と鍵管理装置との間の信頼関係が確保できない環境であっても、鍵を用いた計算の正しさが担保され、計算装置を正しく動作させることができる。
【００１３】
［第一実施形態］
本発明の第一実施形態を説明する。
本形態では、群Ｇを可換群（例えば巡回群）、群Ｈを群Ｇの直積群Ｇ×Ｇ、ｇ∈Ｇを群Ｇの元（例えば生成元）とし、群Ｇ上のＥｌＧａｍａｌ暗号を考える（例えば、非特許文献１等参照）。群ＧはＥｌＧａｍａｌ暗号が安全であるように選ばれる。ＥｌＧａｍａｌ暗号は、ランダムに選ばれた秘密鍵ｓについて公開鍵をｙ＝ｇ−ｓとする暗号方式であり、平文ｍ∈Ｇの暗号文は（ｃ１，ｃ２）＝（ｍｙｒ，ｇｒ）∈Ｈで与えられる。ｒは暗号化の過程で決められる乱数である。暗号文（ｃ１，ｃ２）を復号するためにはｃ１ｃ２ｓを計算すればよい。本形態では、計算装置が自己訂正技術を用い、秘密鍵ｓを保持する鍵管理装置を呼び出し、暗号文（ｃ１，ｃ２）の復号を行う。本形態のｆ（Ｅ）は、秘密鍵ｓを用いて暗号文Ｅ＝（ｃ１，ｃ２）を復号するための復号関数ｆ（ｃ１，ｃ２）＝ｃ１ｃ２ｓである。
【００１４】
＜構成＞
図１に例示するように、本形態の計算システム１は、秘密鍵ｓを保持していない計算装置１１と秘密鍵ｓを保持する鍵管理装置１２とを有し、計算装置１１と鍵管理装置１２とは互いに情報のやり取りが可能なように構成される。
【００１５】
図２Ａに例示するように、計算装置１１は入力部１１１と制御部１１３と自己訂正部１１４とを有する。図３に例示するように、自己訂正部１１４は、自然数選択部１１４ｂと入力情報提供部１１４ｃと整数計算部１１４ｄと計算部１１４ｅ，１１４ｇとべき乗計算部１１４ｆ，１１４ｈとリスト記憶部１１４ｉ，１１４ｊと判定部１１４ｋと計算制御部１１４ｍとを有する。計算装置１１は制御部１１３の制御のもとで各処理を実行する。各部から出力されたデータは必要に応じて図示していない一時メモリに格納され、必要に応じて読み出されて別の処理に用いられる。計算装置１１の例は、カードリーダライタ装置や携帯電話などの計算機能と記憶機能とを備えた機器や、オペレーションプログラムやアプリケーションプログラム等のプログラムが読み込まれたＣＰＵ（ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）やＲＡＭ（ｒａｎｄｏｍ−ａｃｃｅｓｓ  ｍｅｍｏｒｙ）を備えた汎用又は専用のコンピュータなどである。
【００１６】
図２Ｂに例示するように、鍵管理装置１２は秘密鍵ｓを安全に格納する鍵記憶部１２１と制御部１２２と出力情報計算部１２３，１２４を有する。鍵管理装置１２は制御部１２２の制御のもとで各処理を実行する。各部から出力されたデータは必要に応じて図示していない一時メモリに格納され、必要に応じて読み出されて別の処理に用いられる。鍵管理装置１２の例は、半導体チップ等のハードウェアや所定のプログラムが読み込まれた汎用又は専用のコンピュータなどである。
【００１７】
＜処理＞
次に本形態の処理を説明する。処理の前提として、リスト記憶部１１４ａ，１１４ｊは初期化されており、鍵管理装置１２の鍵記憶部１２１には秘密鍵ｓが安全に格納されているものとする。
【００１８】
本形態では、計算装置１１（図２Ａ）の入力部１１１に平文ｍ∈Ｇの暗号文Ｅ＝（ｃ1，ｃ2）∈Ｈが入力され、自己訂正部１１４（図３）の入力情報提供部１１４ｃに送られる。自己訂正部１１４は、図４の自己訂正技術を用いて鍵管理装置１２を呼び出して暗号文Ｅを復号する（自己訂正処理）。まず自然数選択部１１４ｂが、群Ｇの位数未満の自然数ａをランダムに選択し、１または素数からなる固定値ｂとあわせて（ａ，ｂ）を出力する。「自然数」とは０以上の整数を意味する。ａとｂは互いに素である。自然数の組（ａ，ｂ）の少なくとも一部の情報は、整数計算部１１４ｄ、入力情報提供部１１４ｃ、及びべき乗計算部１１４ｆ，１１４ｈに送られる（ステップＳ１１００）。
【００１９】
整数計算部１１４ｄは、送られた自然数の組（ａ，ｂ）を用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する。自然数ａ，ｂは互いに素であるため、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’は必ず存在する。整数ａ’，ｂ’は拡張ユークリッドの互除法等の公知のアルゴリズムを用いて容易に生成できる。整数の組（ａ’，ｂ’）の情報は、計算制御部１１４ｍに送られる（ステップＳ１１０１）。
【００２０】
制御部１１３はｔ１＝１とする（ステップＳ１１０２）。入力情報提供部１１４ｃは、入力された暗号文Ｅにそれぞれ対応する群Ｈの元である第一入力情報τ1及び第二入力情報τ2を生成して出力する。第一入力情報τ1及び第二入力情報τ2は、例えば、それぞれ暗号文Ｅとの関係をかく乱させた情報である。これにより、計算装置１１は、暗号文Ｅを外部に対して隠蔽できる。例えば、第一入力情報τ1は自然数選択部１１４ｂで選択された自然数ｂにさらに対応し、第二入力情報τ2は自然数選択部１１４ｂで選択された自然数ａにさらに対応する。これにより、鍵管理装置１２から提供された情報を高い精度で評価できる。例えば、入力情報提供部１１４ｃは、第一入力情報τ１＝（ｃ１ｂ，ｃ２ｂ）（Ｒ１ｙｒ１，ｇｒ１）＝（ｃ１ｂＲ１ｙｒ１，ｃ２ｂｇｒ１）∈Ｈ、及び第二入力情報τ２＝（ｃ１ａ，ｃ２ａ）（Ｒ２ｙｒ２，ｇｒ２）＝（ｃ１ａＲ２ｙｒ２，ｃ２ａｇｒ２）∈Ｈを得て出力する。ただし、元Ｒ１，Ｒ２∈Ｇ及び自然数ｒ１，ｒ２は、第一入力情報τ１及び第二入力情報τ２の生成過程で一様ランダムに選択される（ステップＳ１１０３）。
【００２１】
図５に例示するように、第一入力情報τ1が鍵管理装置１２（図２Ｂ）の出力情報計算部１２３に入力され、第二入力情報τ2が出力情報計算部１２４に入力される（ステップＳ１２０１）。
【００２２】
出力情報計算部１２３は、第一入力情報τ１と鍵記憶部１２１に格納された秘密鍵ｓとを用いてｆ（τ１）を正しく計算可能であり、得られた計算結果を第一出力情報ｚ１とする。言い換えると、出力情報計算部１２３は、第一入力情報τ１と鍵記憶部１２１に格納された秘密鍵ｓとを用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする（ステップＳ１２０２）。また、出力情報計算部１２４は、第二入力情報τ２と鍵記憶部１２１に格納された秘密鍵ｓとを用いてｆ（τ２）を正しく計算可能であり、得られた計算結果を第二出力情報ｚ２とする。言い換えると、出力情報計算部１２４は、第二入力情報τ２と鍵記憶部１２１に格納された秘密鍵ｓとを用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた計算結果を第二出力情報ｚ２とする（ステップＳ１２０３）。なお、「或る確率」は０％以上１００％未満の確率である。「或る確率」の例は無視することができない確率であり、「無視することができない確率」の例は、セキュリティパラメータｋについての広義単調増加関数である多項式を多項式ψ（ｋ）とした場合の１／ψ（ｋ）以上の確率である。すなわち、出力情報計算部１２３，１２４は、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、出力情報計算部１２３での計算結果がｆ（τ１）の場合もあればｆ（τ１）でない場合もあり、出力情報計算部１２４での計算結果がｆ（τ２）の場合もあればｆ（τ２）でない場合もある。出力情報計算部１２３は第一出力情報ｚ１を出力し、出力情報計算部１２４は第二出力情報ｚ２を出力する（ステップＳ１２０４）。
【００２３】
図４に戻り、第一出力情報ｚ1は自己訂正部１１４（図３）の計算部１１４ｅに入力され、第二出力情報ｚ2は計算部１１４ｇに入力される（ステップＳ１１０４）。
【００２４】
計算部１１４ｅは、第一出力情報ｚ１から計算結果ｕ＝ｆ（ｘ）ｂｘ１を生成する。ここで、ｆ（ｘ）ｂｘ１を生成（計算）するとは、ｆ（ｘ）ｂｘ１と定義される式の値を計算することである。式ｆ（ｘ）ｂｘ１の値を最終的に計算することができれば途中の計算方法は問わない。これは他の式の計算についても同様である。例えば、第一入力情報がτ１＝（ｃ１ｂＲ１ｙｒ１，ｃ２ｂｇｒ１）であった場合、計算部１１４ｅはｕ＝ｚ１Ｒ１−１を生成する。ただし、Ｒ１−１はＲ１の逆元である。計算結果ｕはべき乗計算部１１４ｆに送られる（ステップＳ１１０５）。べき乗計算部１１４ｆはｕ’＝ｕａを計算する。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、リスト記憶部１１４ｉに記憶される（ステップＳ１１０６）。
【００２５】
判定部１１４ｋは、リスト記憶部１１４ｉに記憶された組（ｕ，ｕ’）及びリスト記憶部１１４ｊに記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ１１０７）。もし、リスト記憶部１１４ｊに組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ１１０７の処理を行わずに、次のステップＳ１１０８の処理を行う。ｕ’＝ｖ’となるものがあった場合には、ステップＳ１１１４に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ１１０８に進む。
【００２６】
ステップＳ１１０８では、計算部１１４ｇが第二出力情報ｚ２から計算結果ｖ＝ｆ（ｘ）ａｘ２を生成する。例えば、第二入力情報がτ２＝（ｃ１ａＲ２ｙｒ２，ｃ２ａｇｒ２）であった場合、計算部１１４ｅはｖ＝ｚ２Ｒ２−１を生成する。計算結果ｖはべき乗計算部１１４ｈに送られる（ステップＳ１１０８）。べき乗計算部１１４ｈはｖ’＝ｖｂを計算する。計算結果ｖとその計算結果に基づいて計算されたｖ’との組（ｖ，ｖ’）は、リスト記憶部１１４ｊに記憶される（ステップＳ１１０９）。
【００２７】
判定部１１４ｋは、リスト記憶部１１４ｉに記憶された組（ｕ，ｕ’）及びリスト記憶部１１４ｊに記憶された組（ｖ，ｖ’）についてｕ’＝ｖ’となるか判定する（ステップＳ１１１０）。ｕ’＝ｖ’となるものがあった場合には、ステップＳ１１１４に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ１１１１に進む。
【００２８】
ステップＳ１１１１では、制御部１１３がｔ１＝Ｔ１ｍａｘであるか判定する（ステップＳ１１１１）。Ｔ１ｍａｘはｚ１，ｚ２の誤りに対する許容度を定めるパラメータであり、１以上の所定の自然数である。ｔ１＝Ｔ１ｍａｘであれば、計算制御部１１４ｍは、計算をすることができなかった旨の情報（エラー情報）、例えば記号「⊥」を出力して（ステップＳ１１１３）、計算装置１１の処理を終了させる。一方、ｔ１＝Ｔ１ｍａｘでない場合には、制御部１１３は、ｔ１を１だけインクリメント、すなわちｔ１＝ｔ１＋１として（ステップＳ１１１２）、ステップＳ１１０３に戻る。
【００２９】
計算をすることができなかった旨の情報（この例では記号「⊥」）は、鍵管理装置１２が正しく計算を行う信頼性がＴ１ｍａｘで定められる基準を下回るということを意味する。言い換えれば、Ｔ１ｍａｘ回の繰り返しで正しい演算を行うことができなかったということを意味する。Ｔ１ｍａｘの値が小さいほど信頼性の基準が高い。例えばＴ１ｍａｘ＝１の場合、計算装置１１は新たな第一出力情報ｚ１及び第二出力情報ｚ２を得ることなく処理を終了する。
【００３０】
ステップＳ１１１４では、計算制御部１１４ｍが、ｕ’＝ｖ’であると判定されたｕ’及びｖ’に対応するｕ及びｖを用いてｕｂ’ｖａ’を計算して、出力する（ステップＳ１１１４）。このように計算されたｕｂ’ｖａ’は、一般的な用途では考慮する必要がない非常にまれな例外を除いて、暗号文Ｅ＝（ｃ１，ｃ２）を秘密鍵ｓで復号して得られる復号結果ｆ（Ｅ）＝ｆ（ｃ１，ｃ２）＝ｃ１ｃ２ｓとなる（例えば、国際公開第ＷＯ／２０１２／１２１１５２号や第ＷＯ／２０１２／０５７１３４号参照）。
【００３１】
以上のように本形態の計算装置１１は、一般的な用途では考慮する必要がない非常にまれな例外を除いて、正しい復号結果を出力するか、あるいは明示的なエラーを検出する。すなわち、自己訂正部１１４に入力されるｚ１，ｚ２がどのようなものであっても、計算装置１１が誤った復号結果を出力することがないと考えてよい。
【００３２】
［第二実施形態］
本発明の第二実施形態を説明する。以降では、すでに説明した事項と共通するものについては、これまでの説明で用いた参照番号を引用し、詳細な説明を省略する。
本形態では、群Ｇを可換群、群Ｈを群Ｇ、ｇ∈Ｇを群Ｇの元（例えば生成元）、ｑを群Ｇの位数｜Ｇ｜、ｓを第一計算装置の秘密鍵、ｔを第二計算装置の秘密鍵、Ａを第一計算装置の公開鍵ｇｓ、Ｂを第二計算装置の公開鍵ｇｔ、Ａ＾を第一計算装置に対応する公開情報、Ｂ＾を第二計算装置に対応する公開情報、Ｈａｓｈ１，Ｈａｓｈ２，Ｈａｓｈ３を暗号学的なハッシュ関数とし、第一計算装置と第二計算装置とでのＨＭＱＶ鍵共有を考える（例えば、非特許文献２参照）。公開情報Ａ＾は第一計算装置の識別子であり、例えば、Ａ＾＝Ａである。公開情報Ｂ＾は第二計算装置の識別子であり、例えば、Ｂ＾＝Ｂである。ハッシュ関数Ｈａｓｈ１，Ｈａｓｈ２，Ｈａｓｈ３は、例えばＳＨＡ−１やＳＨＡ−２等である。Ｈａｓｈ１，Ｈａｓｈ２，Ｈａｓｈ３は互いに同一であってもよいし、同一でなくてもよい。Ｈａｓｈ１及びＨａｓｈ２のハッシュ値は０以上ｑ未満の自然数である。ＨＭＱＶ鍵共有では、以下のように第一計算装置と第二計算装置とで共通鍵Ｋを共有する。
１．第一計算装置が、０以上ｑ未満の自然数である乱数ｘを生成し、Ｘ＝ｇｘを第二計算装置に送る。
２．第二計算装置が、０以上ｑ未満の自然数である乱数ｙを生成し、Ｙ＝ｇｙを第一計算装置に送る。
３．第一計算装置が、ｄ＝Ｈａｓｈ１（Ｘ，Ｂ＾）、ｅ＝Ｈａｓｈ２（Ｙ，Ａ＾）、σＡ＝（ＹＢｅ）ｘ＋ｓｄ、Ｋ＝Ｈａｓｈ３（σＡ）を計算する。
４．第二計算装置が、ｄ＝Ｈａｓｈ１（Ｘ，Ｂ＾）、ｅ＝Ｈａｓｈ２（Ｙ，Ａ＾）、σＢ＝（ＸＡｄ）ｙ＋ｔｅ、Ｋ＝Ｈａｓｈ３（σＢ）を計算する。
【００３３】
本形態では、各計算装置が自己訂正技術を用い、各秘密鍵ｓやｔを保持する鍵管理装置を呼び出し、（ＹＢｅ）ｓや（ＸＡｄ）ｔを計算する。本形態のｆ（Ｅ）は群Ｇの元Ｅから元Ｅｓを得る準同型関数である。
【００３４】
＜構成＞
図１に例示するように、本形態の計算システム２は、秘密鍵ｓを保持していない計算装置２１と、秘密鍵ｓを保持する鍵管理装置２２と、秘密鍵ｔを保持していない計算装置２３と、秘密鍵ｔを保持する鍵管理装置２４とを有する。計算装置２１と鍵管理装置２２とが互いに情報のやり取りが可能なように構成され、計算装置２３と鍵管理装置２４とが互いに情報のやり取りが可能なように構成され、計算装置２１と計算装置２３とが互いに情報のやり取りが可能なように構成されている。
【００３５】
図６に例示するように、計算装置２１は、出力部２１１と入力部２１２と制御部２１３と自己訂正部２１４と計算部２１５〜２１１０と共通鍵生成部２１１１とを有する。図３に例示するように、自己訂正部２１４は、自然数選択部１１４ｂと入力情報提供部２１４ｃと整数計算部１１４ｄと計算部２１４ｅ，２１４ｇとべき乗計算部１１４ｆ，１１４ｈとリスト記憶部１１４ｉ，１１４ｊと判定部１１４ｋと計算制御部１１４ｍとを有する。図７に例示するように、計算装置２３は、出力部２３１と入力部２３２と制御部２３３と自己訂正部２３４と計算部２３５〜２３１０と共通鍵生成部２３１１とを有する。自己訂正部２３４は、自己訂正部２１４と同様に構成される。計算装置２１，２３は、それぞれ制御部２１３，２３３の制御のもとで各処理を実行する。各部から出力されたデータは必要に応じて図示していない一時メモリに格納され、必要に応じて読み出されて別の処理に用いられる。計算装置２１，２３の例は、計算機能と記憶機能とを備えた機器やプログラムが読み込まれたＣＰＵやＲＡＭを備えた汎用又は専用のコンピュータなどである。
【００３６】
図２Ｂに例示するように、鍵管理装置２２は秘密鍵ｓを安全に格納する鍵記憶部１２１と制御部１２２と出力情報計算部２２３，２２４を有する。鍵管理装置２２は制御部１２２の制御のもとで各処理を実行する。図８に例示するように、鍵管理装置２４は秘密鍵ｔを安全に格納する鍵記憶部２４１と制御部２４２と出力情報計算部２４３，２４４を有する。鍵管理装置２２，２４は、それぞれ制御部１２２，２４２の制御のもとで各処理を実行する。各部から出力されたデータは必要に応じて図示していない一時メモリに格納され、必要に応じて読み出されて別の処理に用いられる。鍵管理装置２２，２４の例は、半導体チップ等のハードウェアや所定のプログラムが読み込まれた汎用又は専用のコンピュータなどである。
【００３７】
＜処理＞
本形態の処理を説明する。処理の前提として、計算装置２１，２３の記憶部２１５，２３５に計算装置２１の公開情報Ａ＾及び公開鍵Ａ並びに計算装置２３の公開情報Ｂ＾及び公開鍵Ｂが格納される。また、鍵管理装置２２の鍵記憶部１２１には秘密鍵ｓが安全に格納され、鍵管理装置２４の鍵記憶部２４１には秘密鍵ｔが安全に格納される。
【００３８】
図９Ａに例示するように、計算装置２１（図６）の計算部２１６が０以上ｑ未満の自然数である乱数ｘを生成し（ステップＳ２１０）、乱数ｘについての群Ｇの元Ｘ＝ｇｘを得て（ステップＳ２１１）、乱数ｘ及び元Ｘを出力する。元Ｘは出力部２１１に送られ、出力部２１１は元Ｘを計算装置２３に対して出力する（ステップＳ２１２）。
【００３９】
図９Ｂに例示するように、計算装置２３（図７）の計算部２３６が０以上ｑ未満の自然数である乱数ｙを生成し（ステップＳ２３０）、乱数ｙについての群Ｇの元Ｙ＝ｇｙを得て（ステップＳ２３１）、乱数ｙ及び元Ｙを出力する。元Ｙは出力部２３１に送られ、出力部２３１は元Ｙを計算装置２１に対して出力する（ステップＳ２３２）。
【００４０】
図９Ａに例示するように、計算装置２１（図６）の入力部２１２に元Ｙが入力される（ステップＳ２１３）。計算部２１７は、記憶部２１５から読み出した公開情報Ｂ＾と計算部２１６から出力された元Ｘとを入力とし、公開情報Ｂ＾と元Ｘとに対応するハッシュ値ｄ＝Ｈａｓｈ１（Ｘ，Ｂ＾）を得て出力する。Ｈａｓｈ１（Ｘ，Ｂ＾）は、Ｂ＾とＸとに対応する入力値にハッシュ関数Ｈａｓｈ１を作用させたハッシュ値を意味する。Ｂ＾とＸとに対応する入力値の例は、Ｂ＾を表すビット列ｂｉｔ（Ｂ＾）とＸを表すビット列ｂｉｔ（Ｘ）とのビット結合値ｂｉｔ（Ｘ）｜ｂｉｔ（Ｂ＾）である（ステップＳ２１４）。計算部２１８は、記憶部２１５から読み出した公開情報Ａ＾と入力部２１２から送られた元Ｙとを入力とし、公開情報Ａ＾と元Ｙとに対応するハッシュ値ｅ＝Ｈａｓｈ２（Ｙ，Ａ＾）を得て出力する（ステップＳ２１５）。計算部２１９は、入力部２１２から送られた元Ｙと記憶部２１５から読み出した公開鍵Ｂと計算部２１８から出力されたハッシュ値ｅを入力とし、群Ｇの元Ｅ＝ＹＢｅを得て出力する。自己訂正部２１４は、元Ｅを入力とし、図４の自己訂正技術を用いて鍵管理装置２２を呼び出し、群Ｇの元Ｆ＝Ｅｓ＝ｕｂ’ｖａ’を得て出力するか、又は計算をすることができなかった旨の情報を出力する（自己訂正処理／ステップＳ２１７）。この処理の詳細は後述する。元Ｆが得られた場合、計算部２１１０は、上述の元Ｅ，Ｆ，乱数ｘ，ハッシュ値ｄを入力とし、σＡ＝ＥｘＦｄを得て出力する（ステップＳ２１８）。共通鍵生成部２１１１は、共通鍵Ｋ＝Ｈａｓｈ３（σＡ）（Ｅｘ（ｕｂ’ｖａ’）ｄに対応する共通鍵Ｋ）を得て出力する（ステップＳ２１９）。
【００４１】
図９Ｂに例示するように、計算装置２３（図７）の入力部２３２に元Ｘが入力される（ステップＳ２３３）。計算部２３８は、記憶部２３５から読み出した公開情報Ｂ＾と入力部２３２から送られた元Ｘとを入力とし、公開情報Ｂ＾と元Ｘとに対応するハッシュ値ｄ＝Ｈａｓｈ１（Ｘ，Ｂ＾）を得て出力する（ステップＳ２３４）。計算部２３７は、記憶部２３５から読み出した公開情報Ａ＾と計算部２３６から出力された元Ｙとを入力とし、公開情報Ａ＾と元Ｙとに対応するハッシュ値ｅ＝Ｈａｓｈ２（Ｙ，Ａ＾）を得て出力する（ステップＳ２３５）。計算部２３９は、入力部２３２から送られた元Ｘと記憶部２３５から読み出した公開鍵Ａと計算部２３８から出力されたハッシュ値ｄを入力とし、群Ｇの元Ｅ’＝ＸＡｄを得て出力する。自己訂正部２３４は、元Ｅ’を入力とし、自己訂正技術を用いて鍵管理装置２４を呼び出し、群Ｇの元Ｆ’＝Ｅ’ｔを得て出力するか、又は計算をすることができなかった旨の情報を出力する（ステップＳ２３７）。この処理の詳細は後述する。元Ｆ’が得られた場合、計算部２３１０は、上述の元Ｅ’，Ｆ’，乱数ｙ，ハッシュ値ｅを入力とし、σＢ＝Ｅ’ｙＦ’ｅを得て出力する（ステップＳ２３８）。共通鍵生成部２３１１は、Ｋ＝Ｈａｓｈ３（σＢ）を得て出力する（ステップＳ２３９）。
【００４２】
《ステップＳ２１７の詳細》
ステップＳ２１７の詳細を説明する。
図４に例示するように、まず自然数選択部１１４ｂ及び整数計算部１１４ｄが、第一実施形態で説明したステップＳ１１００及びＳ１１０１の処理を実行し、制御部２１３が第一実施形態で説明したステップＳ１１０２の処理を実行する。
【００４３】
次に入力情報提供部２１４ｃは、入力された元Ｅにそれぞれ対応する群Ｈの元である第一入力情報τ1及び第二入力情報τ2を生成して出力する。第一入力情報τ1及び第二入力情報τ2は、例えば、それぞれ元Ｅとの関係をかく乱させた情報である。第一入力情報τ1は、例えば自然数選択部１１４ｂで選択された自然数ｂにさらに対応し、第二入力情報τ2は、例えば自然数選択部１１４ｂで選択された自然数ａにさらに対応する。例えば、入力情報提供部２１４ｃは、第一入力情報τ１＝Ｅｂｇｒ３及び第二入力情報τ２＝Ｅａｇｒ４を得て出力する。ただし、ｒ３，ｒ４は、第一入力情報τ１及び第二入力情報τ２の生成過程で一様ランダムに選択される０以上ｑ未満の自然数である（ステップＳ２１０３）。
【００４４】
図５に例示するように、第一入力情報τ1が鍵管理装置２２（図２Ｂ）の出力情報計算部２２３に入力され、第二入力情報τ2が出力情報計算部２２４に入力される（ステップＳ２２０１）。
【００４５】
出力情報計算部２２３は、第一入力情報τ１と鍵記憶部１２１に格納された秘密鍵ｓとを用いてｆ（τ１）を正しく計算可能であり、得られた計算結果を第一出力情報ｚ１とする。言い換えると、出力情報計算部２２３は、第一入力情報τ１と鍵記憶部１２１に格納された秘密鍵ｓとを用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする（ステップＳ２２０２）。出力情報計算部２２４は、第二入力情報τ２と鍵記憶部１２１に格納された秘密鍵ｓとを用いてｆ（τ２）を正しく計算可能であり、得られた計算結果を第二出力情報ｚ２とする。言い換えると、出力情報計算部２２４は、第二入力情報τ２と鍵記憶部１２１に格納された秘密鍵ｓとを用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた計算結果を第二出力情報ｚ２とする（ステップＳ２２０３）。出力情報計算部２２３での計算結果がｆ（τ１）の場合もあればｆ（τ１）でない場合もあり、出力情報計算部２２４での計算結果がｆ（τ２）の場合もあればｆ（τ２）でない場合もある。出力情報計算部２２３は第一出力情報ｚ１を出力し、出力情報計算部２２４は第二出力情報ｚ２を出力する（ステップＳ２２０４）。
【００４６】
図４に戻り、第一出力情報ｚ1は自己訂正部２１４（図３）の計算部２１４ｅに入力され、第二出力情報ｚ2は計算部２１４ｇに入力される（ステップＳ２１０４）。
【００４７】
計算部２１４ｅは、第一出力情報ｚ１から計算結果ｕ＝ｆ（ｘ）ｂｘ１を生成する。例えば、第一入力情報がτ１＝Ｅｂｇｒ３であった場合、計算部２１４ｅはｕ＝ｚ１Ａ−ｒ３を生成する。計算結果ｕはべき乗計算部１１４ｆに送られる（ステップＳ２１０５）。その後、べき乗計算部１１４ｆと判定部１１４ｋが、第一実施形態で説明したステップＳ１１０６とＳ１１０７とを実行する。ステップＳ１１０７でｕ’＝ｖ’となるものがあった場合には、ステップＳ１１１４の処理を実行する。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ２１０８に進む。
【００４８】
ステップＳ２１０８では、計算部１１４ｇが第二出力情報ｚ２から計算結果ｖ＝ｆ（ｘ）ａｘ２を生成する。例えば、第二入力情報がτ２＝Ｅａｇｒ４であった場合、計算部１１４ｅはｖ＝ｚ２Ａ−ｒ４を生成する。計算結果ｖはべき乗計算部１１４ｈに送られる（ステップＳ２１０８）。その後、べき乗計算部１１４ｈと判定部１１４ｋが、第一実施形態で説明したステップＳ１１０９とＳ１１１０とを実行する。ステップＳ１１１０でｕ’＝ｖ’となるものがあった場合には、ステップＳ１１１４の処理を実行する。ステップＳ１１１４で得られるｕｂ’ｖａ’は、一般的な用途では考慮する必要がない非常にまれな例外を除いて、Ｆ＝Ｅｓとなる。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ１１１１の処理を実行する。ステップＳ１１１１でｔ１＝Ｔ１ｍａｘであれば、計算制御部１１４ｍは、計算をすることができなかった旨の情報（エラー情報）、例えば記号「⊥」を出力して（ステップＳ１１１３）、計算装置１１の処理を終了させる。一方、ｔ１＝Ｔ１ｍａｘでない場合には、制御部１１３は、ｔ１を１だけインクリメント、すなわちｔ１＝ｔ１＋１として（ステップＳ１１１２）、ステップＳ２１０３に戻る。
【００４９】
《ステップＳ２３７の詳細》
ステップＳ２３７では、計算装置２３の制御部２３３と自己訂正部２３４と、鍵管理装置２４の出力情報計算部２４３，２４４とが、ステップＳ２１７の処理における、元Ｅを元Ｅ’に置換し、元Ｆを元Ｆ’に置換し、鍵記憶部１２１に格納された秘密鍵ｓを鍵記憶部２４１に格納された秘密鍵ｔに置換し、群Ｇの元Ｅから元Ｅｓを得る準同型関数ｆ（Ｅ）を群Ｇの元Ｅ’から元Ｅ’ｔを得る準同型関数に置換した処理を実行する。
【００５０】
［第三実施形態］
本発明の第三実施形態を説明する。
本形態は第二実施形態の変形例である。本形態でも、群Ｇを可換群、群Ｈを群Ｇ、ｇ∈Ｇを群Ｇの元（例えば生成元）、ｑを群Ｇの位数｜Ｇ｜、ｓを第一計算装置の秘密鍵、ｔを第二計算装置の秘密鍵、Ａを第一計算装置の公開鍵ｇｓ、Ｂを第二計算装置の公開鍵ｇｔ、Ａ＾を第一計算装置に対応する公開情報、Ｂ＾を第二計算装置に対応する公開情報、Ｈａｓｈ１，Ｈａｓｈ２，Ｈａｓｈ３を暗号学的なハッシュ関数としたＨＭＱＶ鍵共有を行い。ただし、本形態では、各計算装置が自己訂正技術を用い、各秘密鍵ｓやｔを保持する鍵管理装置を呼び出し、（ＹＢｅ）ｓや（ＸＡｄ）ｔを計算し、さらに各乱数ｘやｙを生成する乱数装置を呼び出し、（ＹＢｅ）ｘや（ＸＡｄ）ｙを計算する。これにより、さらに高い安全性が確保できる。本形態では、ｆ（Ｅ）を群Ｇの元Ｅから元Ｅｓを得る準同型関数とし、ｆ’（Ｅ）を群Ｇの元Ｅから元Ｅｘを得る準同型関数とする。また、Ｘ３，Ｘ４を群Ｇに値を持つ確率変数、ｘ３を確率変数Ｘ３の実現値、ｘ４を確率変数Ｘ４の実現値、ｉ，ｊを互いに素な自然数とする。
【００５１】
＜構成＞
図１に例示するように、本形態の計算システム３は、秘密鍵ｓや乱数ｘを保持していない計算装置３１と、秘密鍵ｓを保持する鍵管理装置２２と、秘密鍵ｔや乱数ｙを保持していない計算装置３３と、秘密鍵ｔを保持する鍵管理装置２４と、乱数ｘを生成して保持する乱数装置３５と、乱数ｙを生成して保持する乱数装置３６とを有する。計算装置３１は鍵管理装置２２と乱数装置３５と情報のやり取りが可能なように構成され、計算装置３３は鍵管理装置２４と乱数装置３６と情報のやり取りが可能なように構成され、計算装置３１と計算装置３３とが互いに情報のやり取りが可能なように構成されている。
【００５２】
図１０に例示するように、計算装置３１は、出力部２１１と入力部３１２と制御部３１３と自己訂正部２１４，３１４と計算部２１５，２１７〜２１１０と共通鍵生成部２１１１とを有する。図１３に例示するように、自己訂正部３１４は、自然数選択部３１４ｂと入力情報提供部３１４ｃと整数計算部３１４ｄと計算部３１４ｅ，３１４ｇとべき乗計算部３１４ｆ，３１４ｈとリスト記憶部３１４ｉ，３１４ｊと判定部３１４ｋと計算制御部３１４ｍとを有する。図１１に例示するように、計算装置３３は、出力部２３１と入力部３３２と制御部３３３と自己訂正部２３４，３３４と計算部２３５，３３７〜２３１０と共通鍵生成部２３１１とを有する。自己訂正部３３４は、自己訂正部３１４と同様に構成される。計算装置３１，３３は、それぞれ制御部３１３，３３３の制御のもとで各処理を実行する。各部から出力されたデータは必要に応じて図示していない一時メモリに格納され、必要に応じて読み出されて別の処理に用いられる。計算装置３１，３３の例は、計算機能と記憶機能とを備えた機器やプログラムが読み込まれたＣＰＵやＲＡＭを備えた汎用又は専用のコンピュータなどである。
【００５３】
図１２Ａに例示するように、乱数装置３５は乱数記憶部３５１と制御部３５２と出力情報計算部３５３，３５４と乱数生成部３５５と計算部３５６とを有する。乱数装置３５は制御部３５２の制御のもとで各処理を実行する。図１２Ｂに例示するように、乱数装置３６は乱数記憶部３６１と制御部３６２と出力情報計算部３６３，３６４と乱数生成部３６５と計算部３６６とを有する。乱数装置３５，３６は、それぞれ制御部３５２，３６２の制御のもとで各処理を実行する。各部から出力されたデータは必要に応じて図示していない一時メモリに格納され、必要に応じて読み出されて別の処理に用いられる。乱数装置３５，３６の例は、半導体チップ等のハードウェアや所定のプログラムが読み込まれた汎用又は専用のコンピュータなどである。
【００５４】
＜処理＞
本形態の処理を説明する。処理の前提として、計算装置３１，３３の記憶部２１５，２３５に計算装置２１の公開情報Ａ＾及び公開鍵Ａ並びに計算装置２３の公開情報Ｂ＾及び公開鍵Ｂが格納される。またリスト記憶部３１４ａ，３１４ｊは初期化されている。
【００５５】
乱数装置３５（図１２Ａ）の乱数生成部３５５は、０以上ｑ未満の自然数である乱数ｘを生成する。乱数ｘは乱数記憶部３５１に格納されるとともに、計算部３５６に送られる。計算部３５６は、乱数ｘを入力として群Ｇの元Ｘ＝ｇｘを得て、元Ｘを計算装置３１に対して出力する。元Ｘは計算装置３１（図１０）の入力部３１２に入力され（ステップＳ３１１）、計算部２１７及び出力部２１１に送られる。その後、第二実施形態で説明したステップＳ２１２〜Ｓ２１７の処理が実行される。ステップＳ２１７で元Ｆが得られた場合、自己訂正部３１４は、元Ｅを入力とし、図１５の自己訂正技術を用いて乱数装置３５を呼び出し、群Ｇの元Ｄ＝Ｅｘ＝μｊ’ωｉ’を得て出力するか、又は計算をすることができなかった旨の情報を出力する（自己訂正処理／ステップＳ３１７）。この処理の詳細は後述する。元Ｄが得られた場合、計算部３１１０は、上述の元Ｄ，Ｆ，ハッシュ値ｄを入力とし、σＡ＝ＤＦｄを得て出力する（ステップＳ３１８）。共通鍵生成部２１１１は、共通鍵Ｋ＝Ｈａｓｈ3（σＡ）（（μｊ’ωｉ’）（ｕb’ｖa’）ｄに対応する共通鍵Ｋ）を得て出力する（ステップＳ２１９）。
【００５６】
乱数装置３６（図１２Ｂ）の乱数生成部３６５は、０以上ｑ未満の自然数である乱数ｙを生成する。乱数ｙは乱数記憶部３６１に格納されるとともに、計算部３６６に送られる。計算部３６６は、乱数ｙを入力として群Ｇの元Ｙ＝ｇｙを得て、元Ｙを計算装置３３に対して出力する。元Ｘは計算装置３３（図１１）の入力部３３２に入力され（ステップＳ３３１）、計算部２３７及び出力部２３１に送られる。その後、第二実施形態で説明したステップＳ２３２〜Ｓ２３７の処理が実行される。ステップＳ２３７で元Ｆ’が得られた場合、自己訂正部３３４は、元Ｅ’を入力とし、自己訂正技術を用いて乱数装置３６を呼び出し、群Ｇの元Ｄ’＝Ｅ’ｙを得て出力するか、又は計算をすることができなかった旨の情報を出力する（自己訂正処理／ステップＳ３３７）。この処理の詳細は後述する。元Ｄ’が得られた場合、計算部３３１０は、上述の元Ｄ’，Ｆ’，ハッシュ値ｅを入力とし、σＢ＝Ｄ’Ｆ’ｅを得て出力する（ステップＳ３３８）。共通鍵生成部２３１１は、共通鍵Ｋ＝Ｈａｓｈ３（σＢ）を得て出力する（ステップＳ２１９）。
【００５７】
《ステップＳ３１７の詳細》
ステップＳ３１７の詳細を説明する。
図１５に例示するように、まず自己訂正部３１４（図１３）の自然数選択部３１４ｂが、群Ｇの位数未満の自然数ｉをランダムに選択し、１または素数からなる固定値ｊとあわせて（ｉ，ｊ）を出力する。ｉとｊとは互いに素である。自然数の組（ｉ，ｊ）の少なくとも一部の情報は、整数計算部３１４ｄ、入力情報提供部３１４ｃ、及びべき乗計算部３１４ｆ，３１４ｈに送られる（ステップＳ３１００）。
【００５８】
整数計算部３１４ｄは、送られた自然数の組（ｉ，ｊ）を用いて、ｉ’ｉ＋ｊ’ｊ＝１の関係を満たす整数ｉ’，ｊ’を計算する。整数の組（ｉ’，ｊ’）の情報は、計算制御部３１４ｍに送られる（ステップＳ３１０１）。
【００５９】
制御部３１３はｔ２＝１とする（ステップＳ３１０２）。入力情報提供部３１４ｃは、入力された元Ｅにそれぞれ対応する群Ｈの元である第三入力情報τ３及び第四入力情報τ４を生成して出力する。第三入力情報τ３及び第四入力情報τ４は、例えば、それぞれ元Ｅとの関係をかく乱させた情報である。第三入力情報τ３は、例えば自然数選択部３１４ｂで選択された自然数ｊにさらに対応し、第四入力情報τ４は、例えば自然数選択部３１４ｂで選択された自然数ｉにさらに対応する。例えば、入力情報提供部３１４ｃは、第三入力情報τ３＝Ｅｊｇｒ５及び第四入力情報τ４＝Ｅｉｇｒ６を得て出力する。ただし、ｒ５，ｒ６は、第三入力情報τ３及び第四入力情報τ４の生成過程で一様ランダムに選択される０以上ｑ未満の自然数である（ステップＳ３１０３）。
【００６０】
図１６に例示するように、第三入力情報τ３が乱数装置３５（図２Ｂ）の出力情報計算部３５３に入力され、第四入力情報τ４が出力情報計算部３５４に入力される（ステップＳ３５０１）。
【００６１】
出力情報計算部３５３は、第三入力情報τ３と乱数記憶部３５１に格納された乱数ｘとを用いてｆ’（τ３）を正しく計算可能であり、得られた計算結果を第三出力情報ｚ３とする。言い換えると、出力情報計算部３５３は、第三入力情報τ３と乱数記憶部３５１に格納された乱数ｘとを用い、或る確率より大きな確率でｆ’（τ３）を正しく計算し、得られた計算結果を第三出力情報ｚ３とする（ステップＳ３５０２）。出力情報計算部３５４は、第四入力情報τ４と乱数記憶部３５１に格納された乱数ｘとを用いてｆ’（τ４）を正しく計算可能であり、得られた計算結果を第四出力情報ｚ４とする。言い換えると、出力情報計算部３５４は、第四入力情報τ４と乱数記憶部３５１に格納された乱数ｘとを用い、或る確率より大きな確率でｆ’（τ４）を正しく計算し、得られた計算結果を第三出力情報ｚ４とする（ステップＳ３５０３）。出力情報計算部３５３での計算結果がｆ’（τ３）の場合もあればｆ’（τ３）でない場合もあり、出力情報計算部３５４での計算結果がｆ’（τ４）の場合もあればｆ’（τ４）でない場合もある。出力情報計算部３５３は第三出力情報ｚ３を出力し、出力情報計算部３５４は第四出力情報ｚ４を出力する（ステップＳ３５０４）。
【００６２】
図１５に戻り、第三出力情報ｚ３は自己訂正部３１４（図１３）の計算部３１４ｅに入力され、第四出力情報ｚ４は計算部３１４ｇに入力される（ステップＳ３１０４）。
【００６３】
計算部３１４ｅは、第三出力情報ｚ３から計算結果μ＝ｆ’（ｘ）ｊｘ３を生成する。例えば、第三入力情報がτ３＝Ｅｊｇｒ５であった場合、計算部３１４ｅはμ＝ｚ３Ｘ−ｒ５を生成する。計算結果μはべき乗計算部３１４ｆに送られる（ステップＳ３１０５）。べき乗計算部３１４ｆはμ’＝μａを計算する。計算結果μとその計算結果に基づいて計算されたμ’との組（μ，μ’）は、リスト記憶部３１４ｉに記憶される（ステップＳ３１０６）。
【００６４】
判定部３１４ｋは、リスト記憶部３１４ｉに記憶された組（μ，μ’）及びリスト記憶部３１４ｊに記憶された組（ω，ω’）の中で、μ’＝ω’となるものがあるか判定する（ステップＳ３１０７）。もし、リスト記憶部３１４ｊに組（ω，ω’）が記憶されていない場合には、このステップＳ３１０７の処理を行わずに、次のステップＳ３１０８の処理を行う。μ’＝ω’となるものがあった場合には、ステップＳ３１１４に進む。μ’＝ω’となるものがなかった場合には、ステップＳ３１０８に進む。
【００６５】
ステップＳ３１０８では、計算部３１４ｇが第四出力情報ｚ４から計算結果ω＝ｆ’（ｘ）ｉｘ４を生成する。例えば、第四入力情報がτ４＝Ｅｉｇｒ６であった場合、計算部３１４ｅはω＝ｚ４Ｘ−ｒ６を生成する。計算結果ωはべき乗計算部３１４ｈに送られる（ステップＳ３１０８）。べき乗計算部３１４ｈはω’＝ωｊを計算する。計算結果ωとその計算結果に基づいて計算されたω’との組（ω，ω’）は、リスト記憶部３１４ｊに記憶される（ステップＳ３１０９）。
【００６６】
判定部３１４ｋは、リスト記憶部３１４ｉに記憶された組（μ，μ’）及びリスト記憶部３１４ｊに記憶された組（ω，ω’）についてμ’＝ω’となるか判定する（ステップＳ３１１０）。μ’＝ω’となるものがあった場合には、ステップＳ３１１４に進む。μ’＝ω’となるものがなかった場合には、ステップＳ３１１１に進む。
【００６７】
ステップＳ３１１１では、制御部３１３がｔ２＝Ｔ２ｍａｘであるか判定する（ステップＳ３１１１）。Ｔ２ｍａｘはｚ３，ｚ４の誤りに対する許容度を定めるパラメータであり、１以上の所定の自然数である。ｔ２＝Ｔ２ｍａｘであれば、計算制御部３１４ｍは、計算をすることができなかった旨の情報（エラー情報）、例えば記号「⊥」を出力して（ステップＳ３１１３）、計算装置３１の処理を終了させる。一方、ｔ２＝Ｔ２ｍａｘでない場合には、制御部３１３は、ｔ２を１だけインクリメント、すなわちｔ２＝ｔ２＋１として（ステップＳ３１１２）、ステップＳ３１０３に戻る。
【００６８】
計算をすることができなかった旨の情報（この例では記号「⊥」）は、乱数装置３５が正しく計算を行う信頼性がＴ２ｍａｘで定められる基準を下回るということを意味する。言い換えれば、Ｔ２ｍａｘ回の繰り返しで正しい演算を行うことができなかったということを意味する。Ｔ２ｍａｘの値が小さいほど信頼性の基準が高い。例えばＴ２ｍａｘ＝１の場合、計算装置３１は新たな第三出力情報ｚ３及び第四出力情報ｚ４を得ることなく処理を終了する。
【００６９】
ステップＳ３１１４では、計算制御部３１４ｍが、μ’＝ω’であると判定されたμ’及びω’に対応するμ及びωを用いてμｊ’ωｉ’を計算して、出力する（ステップＳ３１１４）。このように得られるμｊ’ωｉ’は、一般的な用途では考慮する必要がない非常にまれな例外を除いて、Ｄ＝Ｅｘとなる。
【００７０】
《ステップＳ３３７の詳細》
ステップＳ３３７では、計算装置３３の制御部３３３と自己訂正部３３４と、乱数装置３６の出力情報計算部３６３，３６４とが、ステップＳ３１７の処理における、元Ｅを元Ｅ’に置換し、元Ｄを元Ｄ’に置換し、乱数記憶部３５１に格納された乱数ｘを乱数記憶部３６１に格納された乱数ｙに置換し、群Ｇの元Ｅから元Ｅｘを得る準同型関数ｆ’（Ｅ）を群Ｇの元Ｅ’から元Ｅ’ｙを得る準同型関数に置換した処理を実行する。
【００７１】
＜その他の変形例等＞
本発明は上述の実施の形態に限定されるものではない。例えば、ｂ，ｂ’，ａ’がｂ＝ｂ’＝１，ａ’＝０に固定されていてもよい。この場合、図３の整数計算部１１４ｄ，べき乗計算部１１４ｈ、及び図４のステップＳ１１０１，Ｓ１１０９は不要となる。同様に、ｊ，ｊ’，ｉ’がｊ＝ｊ’＝１，ｉ’＝０に固定されていてもよい。この場合、図１３の整数計算部３１４ｄ，べき乗計算部３１４ｈ、及び図１５のステップＳ３１０１，Ｓ３１０９は不要となる。Ｔ１ｍａｘ＝１の場合には、ステップＳ１１１１，Ｓ１１１２は不要となり、Ｔ２ｍａｘ＝１の場合には、ステップＳ３１１１，Ｓ３１１２は不要となる。
【００７２】
「自然数」が０を含まないものとしてもよい。また、０以上ｑ未満の自然数に代えてｑを法とした剰余群Ｚｑの元が用いられてもよい。
【００７３】
計算装置２３，３３が、自己訂正技術を用いることなく、Ｆ’＝Ｅ’ｔやＤ’＝Ｅ’ｙを計算してもよい。
【００７４】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７５】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００７６】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００７８】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００７９】
計算システム  １,２,３
計算装置  １１,１２,１３
鍵管理装置  １２,２２,２４
乱数装置  ３５,３６
【図１】
2014137562.tif 000003
【図２】
2014137562.tif 000004
【図３】
2014137562.tif 000005
【図４】
2014137562.tif 000006
【図５】
2014137562.tif 000007
【図６】
2014137562.tif 000008
【図７】
2014137562.tif 000009
【図８】
2014137562.tif 000010
【図９】
2014137562.tif 000011
【図１０】
2014137562.tif 000012
【図１１】
2014137562.tif 000013
【図１２】
2014137562.tif 000014
【図１３】
2014137562.tif 000015
【図１４】
2014137562.tif 000016
【図１５】
2014137562.tif 000017
【図１６】
2014137562.tif 000018