WO2011086992A1 - 代理計算システム、方法、依頼装置、プログラム及びその記録媒体 - Google Patents

Abstract

　正しい計算を行う確率が低い計算装置を用いて関数ｆ（ｘ）の計算をする。Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ_１，Ｘ_２を群Ｇに値を持つ確率変数、確率変数Ｘ_１の実現値をｘ_１、確率変数Ｘ_２の実現値をｘ_２として、整数計算部が、互いに素である２つの自然数ａ，ｂを用いて、ａ'ａ＋ｂ'ｂ＝１の関係を満たす整数ａ'，ｂ'を計算する。第一乱数化可能標本器は、ｆ（ｘ）^ｂｘ_１を計算可能であり、その計算結果をｕとする。第一べき乗計算部は、ｕ'＝ｕ^ａを計算する。第二乱数化可能標本器は、ｆ（ｘ）^ａｘ_２を計算可能であり、その計算結果をｖとする。第二べき乗計算部は、ｖ'＝ｖ^ｂを計算する。判定部は、ｕ'＝ｖ'であるか判定する。最終計算部は、ｕ'＝ｖ'であると判定された場合には、ｕ^ｂ'ｖ^ａ'を計算する。

Description

代理計算システム、方法、依頼装置、プログラム及びその記録媒体

　この発明は、コンピュータによる計算技術に関する。特に、他の計算機に行わせた計算結果を用いて計算を行う技術に関する。

　正しい計算をするとは限らない計算装置に依頼した計算の結果を用いて依頼装置が関数ｆの計算を行う技術が、非特許文献１に記載されている。非特許文献１に記載された自己訂正器は、計算装置に計算を複数回依頼しその計算結果の多数決を採ることで関数ｆの計算を行う（例えば、非特許文献１参照。）。

M. Blum, M. Luby, and R. Rubinfeld, "Self-Testing/Correcting with Applications to Numerical Problems"， STOC 1990, pp. 73-83.

　しかしながら、非特許文献１の自己訂正器が正常に動作するためには、計算装置は一定以上の確率で正しい計算をする必要があり、正しい計算を行う確率が低い計算装置を用いて関数ｆの計算をする技術は知られていないという課題がある。

　この発明の第一の態様である代理計算システムは、Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ_１，Ｘ_２を群Ｇに値を持つ確率変数、確率変数Ｘ_１の実現値をｘ_１、確率変数Ｘ_２の実現値をｘ_２として、互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する整数計算部と、ｆ（ｘ）^ｂｘ_１を計算可能であり、その計算結果をｕとする第一乱数化可能標本器と、ｕ’＝ｕ^ａを計算する第一べき乗計算部と、ｆ（ｘ）^ａｘ_２を計算可能であり、その計算結果をｖとする第二乱数化可能標本器と、ｖ’＝ｖ^ｂを計算する第二べき乗計算部と、ｕ’＝ｖ’であるか判定する判定部と、ｕ’＝ｖ’であると判定された場合には、ｕ^ｂ’ｖ^ａ’を計算する最終計算部とを含む。

　この発明の第二の態様である代理計算システムは、Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双同型準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、Ｋ_Ｇを群Ｇの位数とし、Ｋ_Ｈを群Ｈの位数とし、μ_ｇを群Ｇの生成元とし、μ_ｈを群Ｈの生成元とし、ν＝θ（μ_ｇ，μ_ｇ）とし、ｋを自然数のセキュリティパラメータとし、Ｋ＝２^ｋとして、依頼装置は、０以上Ｋ_Ｇ未満の整数の乱数ｒ_１を生成する第一乱数生成部と、０以上Ｋ_Ｈ未満の整数の乱数ｒ_２を生成する第二乱数生成部と、第一入力情報ｇ_１＝μ_ｇ ^ｒ１ｇを計算する第一入力情報計算部と、第二入力情報ｈ_１＝μ_ｈ ^ｒ２を計算する第二入力情報計算部と、計算装置から受信したｚ_１∈Ｆを用いて、ｚ_１ν^{－ｒ１ｒ２}を計算する第一リスト情報計算部と、乱数ｒ_２と計算されたｚ_１ν^{－ｒ１ｒ２}とから構成される情報の組（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）が記憶される第一リスト記憶部と、０以上Ｋ未満の整数の一様乱数であるｄ_１を生成する第三乱数生成部と、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_４を生成する第四乱数生成部と、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_５を生成する第五乱数生成部と、第三入力情報ｇ_２＝μ_ｇ ^ｒ４ｇ^ｄ１を計算する第三入力情報計算部と、第四入力情報ｈ_２＝μ_ｈ ^ｒ５を計算する第四入力情報計算部と、計算装置から受信したｚ_２∈Ｆを用いて、ｚ_２ν^{－ｒ４ｒ５}を計算する第二リスト情報計算部と、ｄ_１とｒ_５と計算されたｚ_２ν^{－ｒ４ｒ５}とから構成される情報の組（ｄ_１，ｒ_５，ｚ_２ν^{－ｒ４ｒ５}）が記憶される第二リスト記憶部と、第一リスト記憶部から読み込んだ情報の組の第一成分をｓ_１とし、第二成分をｗ_１とし、第二リスト記憶部から読み込んだ情報の組の第一成分をｔ_２とし、第二成分をｓ_２とし、第三成分をｗ_２として、これらの情報の組が（ｗ_１）＾（ｔ_２ｓ_２ｓ_１ ^－１）＝ｗ_２の関係を満たすかを判定し、その関係を満たす場合には、ｓ_１をσに代入し、ｗ_１をν’に代入する第一判定部と、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_６を生成する第六乱数生成部と、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_７を生成する第七乱数生成部と、第五入力情報ｇ_３＝ｇ^ｒ６を計算する第五入力情報計算部と、第六入力情報ｈ_３＝μ_ｈ ^ｒ７σｈを計算する第六入力情報計算部と、計算装置から受信したｚ_３∈Ｆを用いて、ｚ_３ν’^{－ｒ６ｒ７}を計算する第三リスト情報計算部と、ｒ_６と計算されたｚ_３ν’^{－ｒ６ｒ７}とから構成される情報の組（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）が記憶される第三リスト記憶部と、０以上Ｋ未満の整数の一様乱数であるｄ_２を生成する第八乱数生成部と、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_９を生成する第九乱数生成部と、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_１０を生成する第十乱数生成部と、第七入力情報ｇ_４＝μ_ｇ ^ｒ９を計算する第七入力情報計算部と、第八入力情報ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２を計算する第八入力情報計算部と、計算装置から受信したｚ_４∈Ｆを用いて、ｚ_４ν’^{－ｒ９ｒ１０}を計算する第四リスト情報計算部と、ｄ_２とｒ_９と計算されたｚ_４ν’^{－ｒ９ｒ１０}とから構成される情報の組（ｄ_２，ｒ_９，ｚ_４ν’^{－ｒ９ｒ１０}）が記憶される第四リスト記憶部と、第三リスト記憶部から読み込んだ情報の組の第一成分をｓ_３とし、第二成分をｗ_３とし、第四リスト記憶部から読み込んだ情報の組の第一成分をｔ_４とし、第二成分をｓ_４とし、第三成分をｗ_４として、これらの情報の組が（ｗ_３）＾（ｔ_４ｓ_４ｓ_３ ^－１）＝ｗ_４の関係を満たすかを判定し、その関係を満たす場合には、（ｗ_３）＾（ｓ_３ ^－１）を出力する第二判定部と、を含む。計算装置は、依頼装置から受信したｇ_１及びｈ_１を用いてθ（ｇ_１，ｈ_１）を計算可能であり、その計算結果をｚ_１として出力する第一出力情報計算部と、依頼装置から受信したｇ_２及びｈ_２を用いてθ（ｇ_２，ｈ_２）を計算可能であり、その計算結果をｚ_２として出力する第二出力情報計算部と、依頼装置から受信したｇ_３及びｈ_３を用いてθ（ｇ_３，ｈ_３）を計算可能であり、その計算結果をｚ_３として出力する第三出力情報計算部と、依頼装置から受信したｇ_４及びｈ_４を用いてθ（ｇ_４，ｈ_４）を計算可能であり、その計算結果をｚ_４として出力する第四出力情報計算部とを含む。

　正しい計算を行う確率が低い計算装置を用いて関数ｆの計算をすることができる。

第一実施形態から第三実施形態の代理計算システムの例の機能ブロック図。 第一実施形態から第三実施形態の依頼装置及び計算装置の例の機能ブロック図。 第一実施形態から第三実施形態の標本器の例の機能ブロック図。 第一実施形態から第三実施形態の第一乱数化可能標本器及び第二乱数化可能標本器の例の機能ブロック図。 第一実施形態から第三実施形態の第一乱数化可能標本器及び第二乱数化可能標本器の他の例の機能ブロック図。 第一実施形態から第三実施形態の代理計算方法の例の流れ図。 ステップＳ３の例を示す流れ図。 ステップＳ６の例を示す流れ図。 ステップＳ３の他の例を示す流れ図。 ステップＳ６の他の例を示す流れ図。 第四実施形態から第十実施形態の代理計算システムの例の機能ブロック図。 第四実施形態から第十実施形態の依頼装置の例の機能ブロック図。 第四実施形態から第十実施形態の依頼装置の例の機能ブロック図。 第四実施形態から第十実施形態の計算装置の例の機能ブロック図。 第四実施形態から第十実施形態の代理計算方法の例の流れ図。 第四実施形態から第十実施形態の代理計算方法の例の流れ図。 代理計算システムの変形例の機能ブロック図。

　以下、この発明による代理計算システム、代理計算方法の実施形態を詳細に説明する。
　第一実施形態から第二実施形態は、依頼装置１が計算装置２に依頼した計算の結果を用いてｆ（ｘ）を計算するものである。

［第一実施形態］
　第一実施形態の代理計算システムは、図１に例示するように依頼装置１及び計算装置２を含み、依頼装置１が計算装置２に依頼した計算の結果を用いてｆ（ｘ）を計算する。

　依頼装置１は、図２に示すように、自然数記憶部１１、整数計算部１２、第一べき乗計算部１３、第一リスト記憶部１４、判定部１５、第二べき乗計算部１６、第二リスト記憶部１７、制御部１８及び最終計算部１９を例えば含む。計算装置２は、第一乱数化可能標本器２１及び第二乱数化可能標本器２２を例えば含む。第一実施形態においては、第一乱数化可能標本器２１及び第二乱数化可能標本器２２が計算装置２に対応する。

　Ｇ，Ｈを巡回群、関数ｆ：Ｈ→Ｇを群Ｈの元ｘを群Ｇへ写す関数、群Ｇ，Ｈの生成元をそれぞれμ_ｇ，μ_ｈ、Ｘ_１，Ｘ_２を群Ｇに値を持つ確率変数、確率変数Ｘ_１の実現値をｘ_１、確率変数Ｘ_２の実現値をｘ_２とする。

　自然数記憶部１１には、互いに素である２つの自然数ａ，ｂの組（ａ，ｂ）が複数記憶されているものとする。Ｉを群Ｇの位数未満の２つの自然数の組で互いに素なものの集合とすると、自然数記憶部１１にはＩの部分集合Ｓに対応する自然数ａ，ｂの組（ａ，ｂ）が記憶されていると考えることができる。

　整数計算部１２は、自然数記憶部１１に記憶された複数の自然数の組（ａ，ｂ）から、１つの自然数の組（ａ，ｂ）をランダムに読み込み、その読み込んだ自然数の組（ａ，ｂ）を用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する（ステップＳ１）。自然数ａ，ｂは互いに素であるため、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’は必ず存在する。自然数の組（ａ，ｂ）についての情報は、第一べき乗計算部１３、第二べき乗計算部１６、第一乱数化可能標本器２１及び第二乱数化可能標本器２２に送られる。自然数の組（ａ’，ｂ’）についての情報は、最終計算部１９に送られる。

　制御部１８は、ｔ＝１とする（ステップＳ２）。
　第一乱数化可能標本器２１は、ｆ（ｘ）^ｂｘ_１を計算可能であり、ｘ及びｂを用いて計算を行い、その計算結果をｕとする（ステップＳ３）。計算結果ｕは、第一べき乗計算部１３に送られる。

　この出願において、計算可能とは、無視することができない確率以上の確率で計算することができることを意味する。無視することができない確率とは、セキュリティパラメータｋについての広義単調関数である多項式を多項式Ｆ（ｋ）として、１／Ｆ（ｋ）以上の確率である。

　ここで、ｆ（ｘ）^ｂｘ_１を計算するとは、ｆ（ｘ）^ｂｘ_１と定義される式の値を計算することである。式ｆ（ｘ）^ｂｘ_１の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。

　第一べき乗計算部１３は、ｕ’＝ｕ^ａを計算する（ステップＳ４）。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部１４に記憶される。

　判定部１５は、第一リスト記憶部１４に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１７に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ５）。もし、第二リスト記憶部１７に組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ５の処理を行わずに、次のステップＳ６の処理を行う。ｕ’＝ｖ’となるものがあった場合には、ステップ１２に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ６に進む。

　第二乱数化可能標本器２２は、ｆ（ｘ）^ａｘ_２を計算可能であり、ｘ及びａを用いて計算を行い、その計算結果をｖとする（ステップＳ６）。計算結果ｖは、第二べき乗計算部１６に送られる。

　第二べき乗計算部１６は、ｖ’＝ｖ^ｂを計算する（ステップＳ７）。計算結果ｖとその計算結果に基づいて計算されたｖ’との組（ｖ，ｖ’）は、第二リスト記憶部１７に記憶される。

　判定部１５は、第一リスト記憶部１４に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１７に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ８）。ｕ’＝ｖ’となるものがあった場合には、ステップ１２に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ９に進む。

　制御部１８は、ｔ＝Ｔであるか判定する（ステップＳ９）。Ｔは予め定められた自然数である。ｔ＝Ｔであれば、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１）、処理を終える。ｔ＝Ｔでない場合には、制御部１８は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ１０）、ステップＳ３に戻る。

　計算をすることができなかった旨の情報（この例では記号「⊥」）は、計算装置２が正しく計算を行う信頼性がＴで定められる基準を下回るということを意味する。言い換えれば、Ｔ回の繰り返しで正しい演算を行うことができなかったということを意味する。

　最終計算部１９は、ｕ’＝ｖ’であると判定された場合には、そのｕ’及びｖ’に対応するｕ及びｖを用いてｕ^ｂ’ｖ^ａ’を計算して、出力する（ステップＳ１２）。計算されたｕ^ｂ’ｖ^ａ’＝ｆ（ｘ）となる。ｕ^ｂ’ｖ^ａ’＝ｆ（ｘ）となる理由については、後述する。

　≪ｕ^ｂ’ｖ^ａ’＝ｆ（ｘ）となる理由について≫
　Ｘを群Ｇに値を持つ確率変数とする。ｗ∈Ｇについて、ある計算装置で要求を受けるたびに確率変数Ｒに従って標本ｘ’を抽出しｗｘ’を返信するものを、ｗについて誤差Ｘを持つ標本器（ｓａｍｐｌｅｒ）と呼ぶ。

　ｗ∈Ｇについて、ある計算装置で自然数ａの入力を受けるたびに確率変数Ｘに従って標本ｘ’を抽出しｗ^ａｘ’を返信するものを、ｗについて誤差Ｘを持つ乱数化可能標本器（ｒａｎｄｏｍｉｚａｂｌｅ　ｓａｍｐｌｅｒ）と呼ぶ。乱数化可能標本器はａ＝１として用いられれば標本器として機能する。

　上記実施形態の代理計算システムは、ｘを入力としてｆ（ｘ）を出力する代理計算システムを構成するに当たり、ｆ（ｘ）について誤差Ｘ_１を持つ第一乱数化可能標本器２１、ｆ（ｘ）について誤差Ｘ_２を持つ第二乱数化可能標本器２２を用いている。

　ｕ’＝ｖ’が成立するのは、すなわちｕ^ａ＝ｖ^ｂが成立するのは、第一乱数化可能標本器２１がｕ＝ｆ（ｘ）^ｂｘ_１を正しく計算しており、第二乱数化可能標本器２２がｖ＝ｆ（ｘ）^ａｘ_２を正しく計算しており、さらにｘ_１及びｘ_２が群Ｇの単位元ｅ_ｇである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。

　第一乱数化可能標本器２１がｕ＝ｆ（ｘ）^ｂｘ_１を正しく計算しており、第二乱数化可能標本器２２がｖ＝ｆ（ｘ）^ａｘ_２を正しく計算しており、ｘ_１及びｘ_２が群Ｇの単位元ｅ_ｇであるとき、ｕ^ｂ’ｖ^ａ’＝（ｆ（ｘ）^ｂｘ_１）^ｂ’（ｆ（ｘ）^ａｘ_２）^ａ’＝（ｆ（ｘ）^ｂｅ_ｇ）^ｂ’（ｆ（ｘ）^ａｅ_ｇ）^ａ’＝ｆ（ｘ）^ｂｂ’ｅ_ｇ ^ｂ’ｆ（ｘ）^ａａ’ｅ_ｇ ^ａ’＝ｆ（ｘ）^{（ｂｂ’＋ａａ’）}＝ｆ（ｘ）となる。

　（ｑ_１，ｑ_２）∈Ｉについて、ｉ＝１，２の各々について関数π_ｉをπ_ｉ（ｑ_１，ｑ_２）＝ｑ_ｉで定義する。また、Ｌ＝ｍｉｎ（♯π_１（Ｓ），♯π_２（Ｓ））とする。♯・は、集合・の位数である。群Ｇが巡回群や位数の計算が困難な群であるときには、上記代理計算システムが「⊥」以外を出力するときの出力がｆ（ｘ）ではない確率は、無視できる程度の誤差の範囲で高々Ｔ^２Ｌ／♯Ｓ程度と期待することができる。もしＬ／♯Ｓが無視できる量でＴが多項式オーダー程度の量であれば、上記代理計算システムは圧倒的な確率でｆ（ｘ）を出力する。
　Ｌ／♯Ｓが無視できる量になるようなＳの例には、例えばＳ＝｛（１，ｄ）｜ｄ∈［２，｜Ｇ｜－１］｝がある。

　なお、図２に破線で示すように、計算装置２に標本器２３を設けてもよい。標本器２３は、Ｘ_３を群Ｇに値を持つ確率変数、確率変数Ｘ_３の実現値をｘ_３として、ｆ（ｘ）ｘ_３を計算可能であり、ａ＝１あれば第二乱数化可能標本器２２に代わりその計算結果を上記ｖとし、ｂ＝１であれば第一乱数化可能標本器２１に代わりその計算結果を上記ｕとする。

　一般に乱数化可能標本器よりも標本器の計算量は小さい。ａ＝１，ｂ＝１のときに第一乱数化可能標本器２１、第二乱数化可能標本器２２に代わり、標本器２３が計算を行うことで、計算装置２の計算量を小さくすることができる。

［第二実施形態］
　第二実施形態の代理計算システムは、第一乱数化可能標本器２１及び第二乱数化可能標本器２２の一例、言い換えればステップＳ３及びステップＳ６の一例を具体化したものである。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。

　第二実施形態の第一乱数化可能標本器２１は、図３に示すように、第一乱数生成部１１０、第一入力情報計算部１１１、第一出力情報計算部２４及び第一計算部１１２を例えば含む。また、第二実施形態の第二乱数化可能標本器２２は、図３に示すように、第二乱数生成部１１３、第二入力情報計算部１１４、第二出力情報計算部２５及び第二計算部１１５を例えば含む。

　第二実施形態においては、第一乱数生成部１１０、第一入力情報計算部１１１、第一計算部１１２、第二乱数生成部１１３、第二入力情報計算部１１４及び第二計算部１１５は、依頼装置１に含まれる。また、第一出力情報計算部２４及び第二出力情報計算部２５は、計算装置２に含まれる。第二実施形態においては、第一出力情報計算部２４及び第二出力情報計算部２５が計算装置２に対応する。

　第二実施形態の関数ｆは準同型写像であるとする。また、群Ｈの生成元をμ_ｈ、群Ｈの位数をＫ_Ｈ、ν＝ｆ（μ_ｈ）とする。

　ステップＳ３は、図７に例示するステップＳ３１からステップＳ３４で構成される。

　第一乱数生成部１１０は、０以上Ｋ_Ｈ未満の整数の一様乱数ｒ_１を生成する（ステップＳ３１）。生成された乱数ｒ_１は、第一入力情報計算部１１１に送られる。
　第一入力情報計算部１１１は、第一入力情報μ_ｈ ^ｒ１ｘ^ｂを計算する（ステップＳ３２）。計算された第一入力情報μ_ｈ ^ｒ１ｘ^ｂは、第一出力情報計算部２４に送られる。
　第一出力情報計算部２４は、第一入力情報μ_ｈ ^ｒ１ｘ^ｂを用いて計算を行い、その計算結果を第一出力情報ｚ_１とする（ステップＳ３３）。計算された第一出力情報ｚ_１は、第一計算部１１２に送られる。
　第一出力情報計算部２４は、ｆ（μ_ｈ ^ｒ１ｘ^ｂ）を計算可能である。第一出力情報計算部２４による計算の結果がｆ（μ_ｈ ^ｒ１ｘ^ｂ）であることもあれば、ｆ（μ_ｈ ^ｒ１ｘ^ｂ）でないこともある。

　ここで、μ_ｈの右肩のｒ１は、ｒ_１のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、α^βγと表記した場合には、そのβγはβ_γ、すなわちβの下付きγを意味する。
　第一計算部１１２は、ｚ_１ν^－ｒ１を計算してその計算結果をｕとする（ステップＳ３４）。計算結果ｕは、第一べき乗計算部１３に送られる。ここで、ｕ＝ｚ_１ν^－ｒ１＝ｆ（ｘ）^ｂｘ_１となる。すなわち、ｚ_１ν^－ｒ１は、ｆ（ｘ）について誤差Ｘ_１を持つ乱数化可能標本器となる。その理由については後述する。

　ステップＳ６は、図８に例示するステップＳ６１からステップＳ６４で構成される。

　第二乱数生成部１１３は、０以上Ｋ_Ｈ未満の整数の一様乱数ｒ_２を生成する（ステップＳ６１）。生成された乱数ｒ_２は、第二入力情報計算部１１４に送られる。
　第二入力情報計算部１１４は、第二入力情報μ_ｈ ^ｒ２ｘ^ａを計算する（ステップＳ６２）。計算された第二入力情報μ_ｈ ^ｒ２ｘ^ａは、第二出力情報計算部２５に送られる。
　第二出力情報計算部２５は、第二入力情報μ_ｈ ^ｒ２ｘ^ａを用いて計算を行い、その計算結果を第二出力情報ｚ_２とする（ステップＳ６３）。計算された第二出力情報ｚ_２は、第二計算部１１５に送られる。

　第二出力情報計算部２５は、ｆ（μ_ｈ ^ｒ２ｘ^ａ）を計算可能である。第二出力情報計算部２５による計算の結果がｆ（μ_ｈ ^ｒ２ｘ^ａ）であることもあれば、ｆ（μ_ｈ ^ｒ２ｘ^ａ）でないこともある。
　第二計算部１１５は、ｚ_２ν^－ｒ２を計算してその計算結果をｖとする（ステップＳ６４）。計算結果ｖは、第二べき乗計算部１６に送られる。ここで、ｖ＝ｚ_２ν^－ｒ２＝ｆ（ｘ）^ａｘ_２となる。すなわち、ｚ_２ν^－ｒ２は、ｆ（ｘ）について誤差Ｘ_２を持つ乱数化可能標本器となる。その理由については後述する。

　第二実施形態においても、ａ＝１，ｂ＝１のときは、第一乱数化可能標本器２１又は第二乱数化可能標本器２２に代わり、標本器２３がｕ又はｖの値を計算することにより、計算量を削減してもよい。

　第二実施形態の標本器２３は、図４に示すように、第三乱数生成部１１６、第三入力情報計算部１１７、第三出力情報計算部２６、第三計算部１１８を例えば含む。第三乱数生成部１１６、第三入力情報計算部１１７及び第三計算部１１８は依頼装置１に含まれる。第三出力情報計算部２６は計算装置２に含まれる。

　ａ＝１，ｂ＝１であれば、第一乱数化可能標本器２１、第二乱数化可能標本器２２に代わり標本器２３の各部は以下の処理を行う。
　第三乱数生成部１１６は、０以上Ｋ_Ｈ未満の整数の乱数ｒ_３を生成する。生成された乱数ｒ_３は第三入力情報計算部１１７に送られる。
　第三入力情報計算部１１７は、第三入力情報ｘ^ｒ３を計算する。計算された第三入力情報ｘ^ｒ３は、第三出力情報計算部２６に送られる。

　第三出力情報計算部２６は、第三入力情報ｘ^ｒ３を用いて計算を行い、その計算結果を第三出力情報ｚ_３とする。計算された第三出力情報ｚ_３は、第三計算部１１８に送られる。
　第三出力情報計算部２６は、ｆ（ｘ^ｒ３）を計算可能である。第三出力情報計算部２６による計算の結果がｆ（ｘ^ｒ３）であることもあれば、ｆ（ｘ^ｒ３）でないこともある。

　第三計算部１１８は、ｚ_３ ^１／ｒ３を計算してその計算結果を、ａ＝１であればｖとし、ｂ＝１であればｕとする。計算結果ｖは第二べき乗計算部１６に送られる。計算結果ｕは第一べき乗計算部１３に送られる。ここで、ｕ＝ｖ＝ｚ_３ ^１／ｒ３＝ｆ（ｘ）ｘ_３となる。すなわち、ｚ_３ ^１／ｒ３は、ｆ（ｘ）について誤差Ｘ_３を持つ標本器となる。ｚ_３ ^１／ｒ３は、ｆ（ｘ）について誤差Ｘ_３を持つ標本器となる。その理由については後述する。

　ｚ_３ ^１／ｒ３の計算、すなわちｚ_３のべき乗根の計算が困難な場合には、次のようにしてｕ及び／又はｖを計算してもよい。第三計算部１１８は、乱数ｒ_３とその乱数ｒ_３に基づいて計算されたｚ_３の組を順次（α_１，β_１），（α_２，β_２），…，（α_ｍ，β_ｍ），…として図示していない記憶部に記憶する。ｍは自然数である。第三計算部１１８は、α_１，α_２，…，α_ｍの最小公倍数が１になれば、γ_１，γ_２，…，γ_ｍを整数としてγ_１α_１＋γ_２α_２＋…＋γ_ｍα_ｍ＝１となるγ_１，γ_２，…，γ_ｍを計算して、そのγ，γ_２，…，γ_ｍを用いてΠ_ｉ＝１ ^ｍβ_ｉ ^γｉ＝β_１ ^γ１β_２ ^γ２…β_ｍ ^γｍを計算して、その計算結果をｕ及び／又はｖとしてもよい。

　このように、乱数ｒ_１，ｒ_２，ｒ_３を用いてｘを撹乱した情報を計算装置２に送ることにより、関数ｆの値の計算の対象となるｘ∈Ｈを依頼装置１と計算装置２との間の通信を傍受する第三者、及び、計算装置２に対して秘匿化することができる。

　≪ｚ_１ν^－ｒ１，ｚ_２ν^－ｒ２がｆ（ｘ）についてそれぞれ誤差Ｘ_１，Ｘ_２を持つ乱数化可能標本器となる理由について≫
　ｃを自然数、Ｒ及びＲ’を乱数として、計算装置２がμ_ｈ ^Ｒｘ^ｃを用いて行う計算の計算結果をＢ（μ_ｈ ^Ｒｘ^ｃ）（すなわち、計算装置２が依頼装置１に返す計算結果をｚとすると、ｚ＝Ｂ（μ_ｈ ^Ｒｘ^ｃ）である。）とし、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（μ_ｈ ^Ｒ’）ｆ（μ_ｈ ^Ｒ’）^－１と定義する。

　このとき、ｚν^－Ｒ＝Ｂ（μ_ｈ ^Ｒｘ^ｃ）ｆ（μ_ｈ）^－Ｒ＝Ｘｆ（μ_ｈ ^Ｒｘ^ｃ）ｆ（μ_ｈ）^－Ｒ＝Ｘｆ（μ_ｈ）^Ｒｆ（ｘ）^ｃｆ（μ_ｈ）^－Ｒ＝ｆ（ｘ）^ｃＸとなる。すなわち、ｚν^－Ｒは、ｆ（ｘ）について誤差Ｘを持つ乱数化可能標本器となる。

　上記式展開において、Ｘ＝Ｂ（μ_ｈ ^Ｒ’）ｆ（μ_ｈ ^Ｒ’）^－１＝Ｂ（μ_ｈ ^Ｒｘ^ｃ）ｆ（μ_ｈ ^Ｒｘ^ｃ）^－１であり、Ｂ（μ_ｈ ^Ｒｘ^ｃ）＝Ｘｆ（μ_ｈ ^Ｒｘ^ｃ）であるという性質を用いている。この性質は、関数ｆが準同型写像であり、Ｒ及びＲ’が乱数であることに基づく。

　したがって、ａ，ｂが自然数、ｒ_１，ｒ_２が乱数であることを考慮すると、同様に、ｚ_１ν^－ｒ１，ｚ_２ν^－ｒ２がｆ（ｘ）についてそれぞれ誤差Ｘ_１，Ｘ_２を持つ乱数化可能標本器となるのである。

　≪ｚ_３ ^１／ｒ３がｆ（ｘ）について誤差Ｘ_３を持つ標本器となる理由について≫
　Ｒ及びＲ’を乱数として、計算装置２がｘ^Ｒを用いて行う計算の計算結果をＢ（ｘ^Ｒ）（すなわち、計算装置２が依頼装置１に返す計算結果をｚとすると、ｚ＝Ｂ（ｘ^Ｒ）である。）とし、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（ｘ^Ｒ）^１／Ｒｆ（ｘ）^－１と定義する。
このとき、ｚ^１／Ｒ＝Ｂ（ｘ^Ｒ）^１／Ｒ＝Ｘｆ（ｘ）＝ｆ（ｘ）Ｘとなる。すなわち、ｚ^１／Ｒは、ｆ（ｘ）について誤差Ｘを持つ標本器となる。

　上記式展開において、Ｘ＝Ｂ（ｘ^Ｒ）^１／Ｒｆ（ｘ^Ｒ）^－１であり、Ｂ（ｘ^Ｒ）^１／Ｒ＝Ｘｆ（ｘ^Ｒ）であるという性質を用いている。この性質は、Ｒ及びＲ’が乱数であることに基づく。
　したがって、ｒ_３が乱数であることを考慮すると、ｚ^１／Ｒがｆ（ｘ）について誤差Ｘ_３を持つ乱数化可能標本器となるのである。

［第三実施形態］
　第三実施形態の代理計算システムは、第一乱数化可能標本器２１及び第二乱数化可能標本器２２の他の例、言い換えればステップＳ３及びステップＳ６の他の例を具体化したものである。具体的には、Ｈ＝Ｇ×Ｇで、関数ｆがＥｌＧａｍａｌ暗号の復号関数、すなわち秘密鍵ｓ及び暗号文（ｃ_１，ｃ_２）に対してｆ（ｃ_１，ｃ_２）＝ｃ_１ｃ_２ ^－ｓである場合の第一乱数化可能標本器２１及び第二乱数化可能標本器２２の例を具体化したものである。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。

　第三実施形態の第一乱数化可能標本器２１は、図５に示すように、第四乱数生成部１１９、第五乱数生成部１２０、第四入力情報計算部１２１、第五入力情報計算部１２２、第四出力情報計算部２７及び第四計算部１２３を例えば含む。第二乱数化可能標本器２２は、図５に示すように、第六乱数生成部１２４、第七乱数生成部１２５、第六入力情報計算部１２６、第七入力情報計算部１２７、第五出力情報計算部２８及び第五計算部１２８を例えば含む。

　第四乱数生成部１１９、第五乱数生成部１２０、第四入力情報計算部１２１、第五入力情報計算部１２２、第四計算部１２３、第六乱数生成部１２４、第七乱数生成部１２５、第六入力情報計算部１２６、第七入力情報計算部１２７、第五出力情報計算部２８及び第五計算部１２８は、依頼装置１に含まれる。第四出力情報計算部２７及び第五出力情報計算部２８は計算装置２に含まれる。第三実施形態では、第四出力情報計算部２７及び第五出力情報計算部２８が計算装置２に対応する。

　第三実施形態では、ｘ＝（ｃ_１，ｃ_２）であり、ｆ（ｃ_１，ｃ_２）は直積群Ｇ×ＧからＧへの準同型写像であり、群Ｇの生成元をμ_ｇとし、群Ｇの位数をＫ_Ｇとし、同じ秘密鍵ｓに対する暗号文（Ｖ，Ｗ）∈Ｈとその暗号文を復号した復号文ｆ（Ｖ，Ｗ）＝Ｙ∈Ｇとを依頼装置１と計算装置２は事前に知っているとする。

　第三実施形態のステップＳ３は、図９に例示するステップＳ３１’からステップＳ３６’で構成される。

　第四乱数生成部１１９は、０以上Ｋ_Ｇ未満の整数の一様乱数ｒ_４を生成する（ステップＳ３１’）。生成された乱数ｒ_４は、第四入力情報計算部１２１、第五入力情報計算部１２２及び第四計算部１２３に送られる。
　第五乱数生成部１２０は、０以上Ｋ_Ｇ未満の整数の一様乱数ｒ_５を生成する（ステップＳ３２’）。生成された乱数ｒ_５は、第四入力情報計算部１２１及び第四計算部１２３に送られる。

　第四入力情報計算部１２１は、第四入力情報ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５を計算する（ステップＳ３３’）。計算された第四入力情報ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５は、第四出力情報計算部２７に送られる。
　第五入力情報計算部１２２は、第五入力情報ｃ_２ ^ｂＷ^ｒ４を計算する（ステップＳ３４’）。計算された第五入力情報ｃ_２ ^ｂＷ^ｒ４は、第四出力情報計算部２７に送られる。

　第四出力情報計算部２７は、第四入力情報ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５及び第五入力情報ｃ_２ ^ｂＷ^ｒ４を用いて計算を行い、その計算結果を第四出力情報ｚ_４とする（ステップＳ３５’）。
　第四出力情報計算部２７は、ｆ（ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５，ｃ_２ ^ｂＷ^ｒ４）を計算可能である。第四出力情報計算部２７による計算の結果がｆ（ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５，ｃ_２ ^ｂＷ^ｒ４）であることもあれば、ｆ（ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５，ｃ_２ ^ｂＷ^ｒ４）でないこともある。

　第四計算部１２３は、ｚ_４Ｙ^－ｒ４μ_ｇ ^－ｒ５を計算してその計算結果をｕとする（ステップＳ３６’）。計算結果ｕは、第一べき乗計算部１３に送られる。ここで、ｕ＝ｚ_４Ｙ^－ｒ４μ_ｇ ^－ｒ５＝ｆ（ｃ_１，ｃ_２）^ｂｘ_１となる。すなわち、ｚ_４Ｙ^－ｒ４μ_ｇ ^－ｒ５は、ｆ（ｃ_１，ｃ_２）について誤差Ｘ_１を持つ乱数化可能標本器となる。その理由については後述する。

　第三実施形態のステップＳ６は、図１０に例示するステップＳ６１’からステップＳ６６’で構成される。

　第六乱数生成部１２４は、０以上Ｋ_Ｇ未満の整数の一様乱数ｒ_６を生成する（ステップＳ６１’）。生成された乱数ｒ_６は、第六入力情報計算部１２６、第七入力情報計算部１２７及び第五計算部１２８に送られる。
　第七乱数生成部１２５は、０以上Ｋ_Ｇ未満の整数の一様乱数ｒ_７を生成する（ステップＳ６２’）。生成された乱数ｒ_７は、第六入力情報計算部１２６及び第五計算部１２８に送られる。

　第六入力情報計算部１２６は、第六入力情報ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７を計算する（ステップＳ６３’）。計算された第六入力情報ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７は、第五出力情報計算部２８に送られる。
　第七入力情報計算部１２７は、第七入力情報ｃ_２ ^ａＷ^ｒ６を計算する（ステップＳ６４’）。計算された第七入力情報ｃ_２ ^ａＷ^ｒ６は、第五出力情報計算部２８に送られる。

　第五出力情報計算部２８は、上記第六入力情報ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７及び上記第七入力情報ｃ_２ ^ａＷ^ｒ６を用いて計算を行い、その計算結果を第五出力情報ｚ_５とする（ステップＳ６５’）。計算された第五出力情報ｚ_５は、第五計算部１２８に送られる。
　第五出力情報計算部２８は、ｆ（ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７，ｃ_２ ^ａＷ^ｒ６）を計算可能である。第五出力情報計算部２８による計算の結果がｆ（ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７，ｃ_２ ^ａＷ^ｒ６）であることもあれば、ｆ（ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７，ｃ_２ ^ａＷ^ｒ６）でないこともある。

　第五計算部１２８は、ｚ_５Ｙ^－ｒ６μ_ｇ ^－ｒ７を計算してその計算結果をｖとする（ステップＳ６６’）。計算結果ｖは、第二べき乗計算部１６に送られる。ここで、ｖ＝ｚ_５Ｙ^－ｒ６μ_ｇ ^－ｒ７＝ｆ（ｃ_１，ｃ_２）^ａｘ_２となる。すなわち、ｚ_５Ｙ^－ｒ６μ_ｇ ^－ｒ７は、ｆ（ｃ_１，ｃ_２）について誤差Ｘ_２を持つ乱数化可能標本器となる。その理由については後述する。

　≪ｚ_４Ｙ^－ｒ４μ_ｇ ^－ｒ５，ｚ_５Ｙ^－ｒ６μ_ｇ ^－ｒ７がｆ（ｃ_１，ｃ_２）についてそれぞれ誤差Ｘ_１，Ｘ_２を持つ乱数化可能標本器となる理由について≫
　ｃを自然数、Ｒ_１、Ｒ_２、Ｒ_１’及びＲ_２’を乱数として、計算装置２がｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２及びｃ_２ ^ｃＷ^Ｒ１を用いて行う計算の計算結果をＢ（ｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２，ｃ_２ ^ｃＷ^Ｒ１）（すなわち、計算装置２が依頼装置１に返す計算結果をｚとすると、ｚ＝Ｂ（ｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２，ｃ_２ ^ｃＷ^Ｒ１）である。）とし、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（Ｖ^Ｒ１’μ_ｇ ^Ｒ２’，Ｗ^Ｒ１’）ｆ（Ｖ^Ｒ１’μ_ｇ ^Ｒ２’，Ｗ^Ｒ１’）^－１と定義する。

　このとき、ｚＹ^－Ｒ１μ_ｇ ^－Ｒ２＝Ｂ（ｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２，ｃ_２ ^ｃＷ^Ｒ１）Ｙ^－Ｒ１μ_ｇ ^－Ｒ２＝Ｘｆ（ｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２，ｃ_２ ^ｃＷ^Ｒ１）Ｙ^－Ｒ１μ_ｇ ^－Ｒ２＝Ｘｆ（ｃ_１，ｃ_２）^ｃｆ（Ｖ，Ｗ）^Ｒ１ｆ（μ_ｇ，ｅ_ｇ）^Ｒ２Ｙ^－Ｒ１μ_ｇ ^－Ｒ２＝Ｘｆ（ｃ_１，ｃ_２）^ｃＹ^Ｒ１μ_ｇ ^Ｒ２Ｙ^－Ｒ１μ_ｇ ^－Ｒ２＝ｆ（ｃ_１，ｃ_２）^ｃＸとなる。すなわち、ｚＹ^－Ｒ１μ_ｇ ^－Ｒ２は、ｆ（ｘ）について誤差Ｘを持つ乱数化可能標本器となる。なお、ｅ_ｇは、群Ｇの単位元である。

　上記式展開において、Ｘ＝Ｂ（Ｖ^Ｒ１’μ_ｇ ^Ｒ２’，Ｗ^Ｒ１’）ｆ（Ｖ^Ｒ１’μ_ｇ ^Ｒ２’，Ｗ^Ｒ１’）^－１＝Ｂ（ｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２，ｃ_２ ^ｃＷ^Ｒ１）ｆ（ｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２，ｃ_２ ^ｃＷ^Ｒ１）であり、Ｂ（ｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２，ｃ_２ ^ｃＷ^Ｒ１）＝Ｘｆ（ｃ_１ ^ｃＶ^Ｒ１μ_ｇ ^Ｒ２，ｃ_２ ^ｃＷ^Ｒ１）であるという性質を用いている。この性質は、Ｒ_１、Ｒ_２、Ｒ_１’及びＲ_２’が乱数であることに基づく。

　したがって、ａ，ｂが自然数、ｒ_４，ｒ_５，ｒ_６及びｒ_７が乱数であることを考慮すると、同様に、ｚ_４Ｙ^－ｒ４μ_ｇ ^－ｒ５，ｚ_５Ｙ^－ｒ６μ_ｇ ^－ｒ７がｆ（ｃ_１，ｃ_２）についてそれぞれ誤差Ｘ_１，Ｘ_２を持つ乱数化可能標本器となるのである。

［第一実施形態から第三実施形態の変形例等］
　確率変数Ｘ_１、Ｘ_２及びＸ_３は、同じでも異なっていてもよい。
　第一乱数生成部１１０、第二乱数生成部１１３、第三乱数生成部１１６、第四乱数生成部１１９、第五乱数生成部１２０、第六乱数生成部１２４及び第七乱数生成部１２５のそれぞれは、一様乱数を生成することにより、代理計算システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部１１０、第二乱数生成部１１３、第三乱数生成部１１６、第四乱数生成部１１９、第五乱数生成部１２０、第六乱数生成部１２４及び第七乱数生成部１２５のそれぞれは、一様乱数ではない乱数を生成してもよい。

　上記の例では、第一乱数化可能標本器２１、第二乱数化可能標本器２２を一回づつ呼び出しているが、依頼装置１と計算装置２との間の通信回数を減らすために、同一のａ，ｂに対して第一乱数化可能標本器２１、第二乱数化可能標本器２２を複数回呼び出して、依頼装置１が一回の通信で複数のｕ，ｖを取得できるようにしてもよい。

　第一乱数化可能標本器２１、第二乱数化可能標本器２２及び標本器２３の各部は、依頼装置１に配置してもよいし、計算装置２に配置してもよい。すなわち、第一実施形態のように各部のすべてを計算装置２に配置してもよいし、例えば第二実施形態及び第三実施形態のように依頼装置１及び計算装置２に分けて配置してもよい。

　依頼装置１の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、計算装置２の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。

　依頼装置１及び計算装置２のそれぞれはコンピュータによって実現することができる。この場合、この装置が有すべき各機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これ装置における各処理機能が、コンピュータ上で実現される。

　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

　［第四実施形態］
　第四実施形態から第十実施形態は、依頼装置１’が計算装置２’に依頼した計算の結果を用いてθ（ｇ，ｈ）を計算するものである。

　第四実施形態の代理計算システムは、図１１に例示するように依頼装置１’及び計算装置２’を含み、依頼装置１’が計算装置２’に依頼した計算の結果を用いて双準同型写像θ（ｇ，ｈ）を計算する。

　ここで、Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、Ｋ_Ｇを群Ｇの位数とし、Ｋ_Ｈを群Ｈの位数とし、μ_ｇを群Ｇの生成元とし、μ_ｈを群Ｈの生成元とし、ν＝θ（μ_ｇ，μ_ｇ）とし、ｋを１以上の整数のセキュリティパラメータとし、Ｋ＝２^ｋとする。

　双準同型写像とは、２つの入力のそれぞれに対して準同型である写像を意味する。この例では、写像θ（ｇ，ｈ）は、群Ｇの元ｇに対して準同型であり、かつ、群Ｈの元ｈに対して準同型である。

　依頼装置１’と計算装置２’との間には通信路が確立されており、依頼装置１’及び計算装置２’は双方向に通信可能である。この通信路は秘密に保たれている必要はなく、第三者がこの通信路を流れる情報を傍受することができてもよい。

　依頼装置１’は信頼できない計算装置２’に乱数によって撹乱した情報を送信し、計算装置２’はその撹乱された情報を用いて一定のアルゴリズムに従って計算を行い、その計算結果を依頼装置１’に返信する。この計算装置２’への情報の送受信を繰り返すことにより、依頼装置１’は最終的にθ（ｇ，ｈ）を計算する。

　依頼装置１’は、まずステップＳ１１’からステップＳ１２５’（図１５）の処理によりθ（ｇ，μ_ｈ）と同等の情報（σ，ν’）を計算し、そのθ（ｇ，μ_ｈ）と同等の情報（σ，ν’）を用いてステップＳ２１’からステップS２２５’の処理によりθ（ｇ，μ）を計算する。

　依頼装置１’は、図１２及び図１３に例示する、第一乱数生成部１１’、第二乱数生成部１２’、第一入力情報計算部１３’、第二入力情報計算部１４’、第一リスト情報計算部１５’、第一リスト記憶部１６’、受信部１７’、送信部１８’、第四乱数生成部２１’、第五乱数生成部２２’、第三入力情報計算部２３’、第四入力情報計算部２４’、第二リスト情報計算部２５’、第二リスト記憶部２６’、第三乱数生成部２７’、第一判定部２８’、第六乱数生成部３１’、第七乱数生成部３２’、第五入力情報計算部３３’、第六入力情報計算部３４’、第三リスト情報計算部３５’、第三リスト記憶部３６’、第九乱数生成部４１’、第十乱数生成部４２’、第七入力情報計算部４３’、第八入力情報計算部４４’、第四リスト情報計算部４５’、第四リスト計算部４６’、第八乱数生成部４７’及び第二判定部４８’を例えば含む。

　計算装置２’は、図１４に例示するように、受信部５１’、送信部５２’、第一出力情報計算部５３’、第二出力情報計算部５４’、第三出力情報計算部５５’及び第四出力情報計算部５６’を例えば含む。

　＜ステップＳ１１’（図１５）＞
　第一乱数生成部１１’は、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_１を生成する（ステップＳ１１’）。生成された乱数ｒ_１は、第一入力情報計算部１３’及び第一リスト情報計算部１５’に送られる。

　＜ステップＳ１２’＞
　第二乱数生成部１２’は、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_２を生成する（ステップＳ１２’）。生成された乱数ｒ_２は、第二入力情報計算部１４’、第一リスト情報計算部１５’及び第一リスト記憶部１６’に送られる。

　＜ステップＳ１３’＞
　第一入力情報計算部１３’は、第一入力情報ｇ_１＝μ_ｇ ^ｒ１ｇを計算する（ステップＳ１３’）。計算されたｇ_１は送信部１８’に送られる。
　ここで、μ_ｇの右肩のｒ１は、ｒ_１のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、α^βγと表記した場合には、そのβγはβ_γ、すなわちβの下付きγを意味する。

　また、ｇ_１＝μ_ｇ ^ｒ１ｇを計算するとは、μ_ｇ ^ｒ１ｇという式で定義されるｇ_１の値を計算することである。式μ_ｇ ^ｒ１ｇの値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。

　＜ステップＳ１４’＞
　第二入力情報計算部１４’は、第二入力情報ｈ_１＝μ_ｈ ^ｒ２を計算する（ステップＳ１４’）。計算されたｈ_１は送信部１８’に送られる。

　＜ステップＳ１５’＞
　送信部１８’は、第一入力情報ｇ_１及び第二入力情報ｈ_１を計算装置２’に送信する（ステップＳ１５’）。

　＜ステップＳ１６’＞
　計算装置２’の受信部５１’（図１４）は、第一入力情報ｇ_１及び第二入力情報ｈ_１を受信する（ステップＳ１６’）。

　＜ステップＳ１７’＞
　第一出力情報計算部５３’は、第一入力情報ｇ_１及び第二入力情報ｈ_１を用いて計算を行い、その計算結果を第一出力情報ｚ_１とする（ステップＳ１７’）。ｚ_１は、送信部５２’に送られる。

　第一出力情報計算部５３’は、θ（ｇ_１，ｈ_１）を計算可能である。第一出力情報計算部５３’による計算の結果がθ（ｇ_１，ｈ_１）であることもあれば、θ（ｇ_１，ｈ_１）でないこともある。

　この出願において、計算可能とは、無視することができない確率で計算することができることを意味する。無視することができない確率とは、セキュリティパラメータｋについての広義単調増加関数である多項式を多項式ｆ（ｋ）として、１／ｆ（ｋ）以上の確率である。

　＜ステップＳ１８’＞
　送信部５２’は、第一出力情報ｚ_１を依頼装置１’に送信する（ステップＳ１８’）。

　＜ステップＳ１９’＞
　依頼装置１’の受信部１７’（図１２）は、第一出力情報ｚ_１を受信する（ステップＳ１９’）。受信した第一出力情報ｚ_１は、第一リスト情報計算部１５’に送られる。ここでは、第一出力情報ｚ_１は群Ｆの元であるとする。

　＜ステップＳ１１０’＞
　第一リスト情報計算部１５’は、乱数ｒ_１、乱数ｒ_２及び第一出力情報ｚ_１を用いて、ｚ_１ν^{－ｒ１ｒ２}を計算する（ステップＳ１１０’）。計算されたｚ_１ν^{－ｒ１ｒ２}は、第一リスト記憶部１６’に送られる。

　＜ステップＳ１１１’＞
　乱数ｒ_２と、ｚ_１ν^{－ｒ１ｒ２}とから構成される情報の組（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）がリストＬ_１に追加される。この例では、第一リスト記憶部１６’に、情報の組（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）が記憶される（ステップＳ１１１’）。

　＜ステップＳ１１２’＞
　第三乱数生成部２７’は、０以上Ｋ未満の整数の一様乱数であるｄ_１を生成する（ステップＳ１１２’）。生成された乱数ｄ_１は、第三入力情報計算部２３’及び第二リスト記憶部２６’に送られる。

　＜ステップＳ１１３’＞
　第四乱数生成部２１’は、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_４を生成する（ステップＳ１１３’）。生成された乱数ｒ_４は、第三入力情報計算部２３’及び第二リスト情報計算部２５’に送られる。

　＜ステップＳ１１４’＞
　第五乱数生成部２２’は、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_５を生成する（ステップＳ１１４’）。生成された乱数ｒ_５は、第四入力情報計算部２４’、第二リスト情報計算部２５’及び第二リスト記憶部２６’に送られる。

　＜ステップＳ１１５’＞
　第三入力情報計算部２３’は、第三入力情報ｇ_２＝μ_ｇ ^ｒ４ｇ^ｄ１を計算する（ステップＳ１１５’）。計算された第三入力情報ｇ_２は、送信部１８’に送られる。

　＜ステップＳ１１６’＞
　第四入力情報計算部２４’は、第四入力情報ｈ_２＝μ_ｈ ^ｒ５を計算する（ステップＳ１１６’）。計算された第四入力情報ｈ_２は、送信部１８’に送られる。

　＜ステップＳ１１７’＞
　送信部１８’は、第三入力情報ｇ_２及び第四入力情報ｈ_２を計算装置２’に送信する（ステップＳ１１７’）。

　＜ステップＳ１１８’＞
　計算装置２’の受信部５１’（図１４）は、第三入力情報ｇ_２及び第四入力情報ｈ_２を受信する（ステップＳ１１８’）。

　＜ステップＳ１１９’＞
　第二出力情報計算部５４’は、第三入力情報ｇ_２及び第三入力情報ｈ_２を用いて計算を行い、その計算結果を第二出力情報ｚ_２とする（ステップＳ１１９’）。ｚ_２は、送信部５２’に送られる。
　第二出力情報計算部５４’は、θ（ｇ_２，ｈ_２）を計算可能である。第二出力情報計算部５４’による計算の結果がθ（ｇ_２，ｈ_２）であることもあれば、θ（ｇ_２，ｈ_２）でないこともある。

　＜ステップＳ１２０’＞
　送信部５２’は、第二出力情報ｚ_２を依頼装置１’に送信する（ステップＳ１２０’）。

　＜ステップＳ１２１’＞
　依頼装置１’の受信部１７’（図１２）は、第二出力情報ｚ_２を受信する（ステップＳ１２１’）。受信した第二出力情報ｚ_２は、第二リスト情報計算部２５’に送られる。ここでは、第二出力情報ｚ_２は群Ｆの元であるとする。

　＜ステップＳ１２２’＞
　第二リスト情報計算部２５’は、乱数ｒ_４、乱数ｒ_５及び第二出力情報ｚ_２を用いて、ｚ_２ν^{－ｒ４ｒ５}を計算する（ステップＳ１２２’）。計算されたｚ_２ν^{－ｒ４ｒ５}は、第二リスト記憶部２６’に送られる。

　＜ステップＳ１２３’＞
　乱数ｄ_１と、乱数ｒ_５と、ｚ_２ν^{－ｒ４ｒ５}とから構成される情報の組（ｄ_１，ｒ_５，ｚ_２ν^{－ｒ４ｒ５}）が、リストＬ_２に追加される。この例では、第二リスト記憶部２６’には、情報の組（ｄ_１，ｒ_５，ｚ_２ν^{－ｒ４ｒ５}）が記憶される（ステップＳ１２３’）。　

　＜ステップＳ１２４’＞
　第一判定部２８’は、第一リスト記憶部１６’から読み込んだ情報の組の第一成分をｓ_１とし、第二成分をｗ_１とし、第二リスト記憶部２６’から読み込んだ情報の組の第一成分をｔ_２とし、第二成分をｓ_２とし、第三成分をｗ_２として、これらの情報の組が（ｗ_１）＾（ｔ_２ｓ_２ｓ_１ ^－１）＝ｗ_２の関係を満たすかを判定する（ステップＳ１２４’）。

　第一判定部２８’は、第一リスト記憶部１６’及び第二リスト記憶部２６’に複数の情報の組が記憶されている場合には、第一リスト記憶部１６’に記憶された情報の組（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）と、第二リスト記憶部２６’に記憶された情報の組（ｄ_１，ｒ_５，ｚ_２ν^{－ｒ４ｒ５}）とから構成されるすべての情報のペアについて、上記関係を満たすかどうかを判定する。もちろん、既に上記関係を満たすかどうかを判定した情報のペアについては、その判定処理を省いてもよい。

　＜ステップＳ１２５’＞
　第一判定部２８’は、上記の関係を満たす場合には、ｓ_１をσに代入し、ｗ_１をν’に代入する（ステップＳ１２５’）。ここで、ν’^１／σ＝ｗ_１ ^１／σ＝θ（ｇ，μ_ｈ）となる。ν’^１／σ＝θ（ｇ，μ_ｈ）となる理由については後述する。
　上記の関係を満たさない場合には、ステップＳ１１’に戻る。

　＜ステップＳ２１’（図１６）＞
　第六乱数生成部３１’は、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_６を生成する（ステップＳ２１’）。生成された乱数ｒ_６は、第五入力情報計算部３３’、第三リスト情報計算部３５’及び第三リスト記憶部３６’に送られる。

　＜ステップＳ２２’＞
　第七乱数生成部３２’は、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_７を生成する（ステップＳ２２’）。生成された乱数ｒ_７は、第六入力情報計算部３４’及び第三リスト情報計算部３５’に送られる。

　＜ステップＳ２３’＞
　第五入力情報計算部３３’は、第五入力情報ｇ_３＝μ_ｇ ^ｒ６を計算する（ステップＳ２３’）。計算されたｇ_３は送信部１８’に送られる。

　＜ステップＳ２４’＞
　第六入力情報計算部３４’は、第六入力情報ｈ_３＝μ_ｈ ^ｒ７σｈを計算する（ステップＳ２４’）。計算されたｈ_３は送信部１８’に送られる。

　＜ステップＳ２５’＞
　送信部１８’は、第五入力情報ｇ_３及び第六入力情報ｈ_３を計算装置２’に送信する（ステップＳ２５’）。

　＜ステップＳ２６’＞
　計算装置２’の受信部５１’（図１４）は、第五入力情報ｇ_３及び第六入力情報ｈ_３を受信する（ステップＳ２６’）。

　＜ステップＳ２７’＞
　第三出力情報計算部５５’は、第五入力情報ｇ_３及び第六入力情報ｈ_３を用いて計算を行い、その計算結果を第三出力情報ｚ_３とする（ステップＳ２７’）。ｚ_３は、送信部５２’に送られる。
　第三出力情報計算部５５’は、θ（ｇ_３，ｈ_３）を計算可能である。第三出力情報計算部５５’による計算の結果がθ（ｇ_３，ｈ_３）であることもあれば、θ（ｇ_３，ｈ_３）でないこともある。

　＜ステップＳ２８’＞
　送信部５２’は、第三出力情報ｚ_３を依頼装置１’に送信する（ステップＳ２８’）。

　＜ステップＳ２９’＞
　依頼装置１’の受信部１７’（図１３）は、第三出力情報ｚ_３を受信する（ステップＳ２９’）。受信した第三出力情報ｚ_３は、第三リスト情報計算部３５’に送られる。ここでは、第３出力情報ｚ_３は群Ｆの元であるとする。

　＜ステップＳ２１０’＞
　第三リスト情報計算部３５’は、乱数ｒ_６、乱数ｒ_７及び第三出力情報ｚ_３を用いて、ｚ_３ν’^{－ｒ６ｒ７}を計算する（ステップＳ２１０’）。計算されたｚ_３ν^{－ｒ６ｒ７}は、第三リスト記憶部３６’に送られる。

　＜ステップＳ２１１’＞
　乱数ｒ_６と、ｚ_３ν’^{－ｒ６ｒ７}とから構成される情報の組（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）がリストＬ_３に追加される。この例では、第三リスト記憶部３６’に、情報の組（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）が記憶される（ステップＳ２１１’）。

　＜ステップＳ２１２’＞
　第八乱数生成部４７’は、０以上Ｋ未満の整数の一様乱数であるｄ_２を生成する（ステップＳ２１２’）。生成された乱数ｄ_２は、第八入力情報計算部４４及び第四リスト記憶部４６’に送られる。

　＜ステップＳ２１３’＞
　第九乱数生成部４１’は、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_９を生成する（ステップＳ２１３’）。生成された乱数ｒ_９は、第七入力情報計算部４３’、第四リスト情報計算部４５’及び第四リスト記憶部４６’に送られる。

　＜ステップＳ２１４’＞
　第十乱数生成部４２’は、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_１０を生成する（ステップＳ２１４’）。生成された乱数ｒ_１０は、第八入力情報計算部４４’、第四リスト情報計算部４５’及び第四リスト記憶部４６’に送られる。

　＜ステップＳ２１５’＞
　第七入力情報計算部４３’は、第七入力情報ｇ_４＝ｇ^ｒ９を計算する（ステップＳ２１５’）。計算された第七入力情報ｇ_４は、送信部１８’に送られる。

　＜ステップＳ２１６’＞
　第八入力情報計算部４４’は、第八入力情報ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２を計算する（ステップＳ２１６’）。計算された第八入力情報ｈ_４は、送信部１８’に送られる。

　＜ステップＳ２１７’＞
　送信部１８’は、第七入力情報ｇ_４及び第八入力情報ｈ_４を計算装置２’に送信する（ステップＳ２１７’）。

　＜ステップＳ２１８’＞
　計算装置２’の受信部５１’（図１４）は、第七入力情報ｇ_４及び第八入力情報ｈ_４を受信する（ステップＳ２１８’）。

　＜ステップＳ２１９’＞
　第四出力情報計算部５６’は、第七入力情報ｇ_４及び第八入力情報ｈ_４を用いて計算を行い、その計算結果を第四出力情報ｚ_４とする（ステップＳ２１９’）。ｚ_４は、送信部５２’に送られる。
　第四出力情報計算部５６’は、θ（ｇ_４，ｈ_４）を計算可能である。第四出力情報計算部５６’による計算の結果がθ（ｇ_４，ｈ_４）であることもあれば、θ（ｇ_４，ｈ_４）でないこともある。

　＜ステップＳ２２０’＞
　送信部５２’は、第四出力情報ｚ_４を依頼装置１’に送信する（ステップＳ２２０’）。

　＜ステップＳ２２１’＞
　依頼装置１’の受信部１７’（図１２）は、第四出力情報ｚ_４を受信する（ステップＳ２２１）。受信した第四出力情報ｚ_４は、第四リスト情報計算部４５’に送られる。ここでは、第四出力情報ｚ_４は群Ｆの元であるとする。

　＜ステップＳ２２２’＞
　第四リスト情報計算部４５’は、乱数ｒ_９、乱数ｒ_１０及び第四出力情報ｚ_４を用いて、ｚ_４ν’^{－ｒ９ｒ１０}を計算する（ステップＳ２２２’）。計算されたｚ_４ν’^{－ｒ９ｒ１０}は、第四リスト記憶部４６’に送られる。

　＜ステップＳ２２３’＞
　乱数ｄ_２と、乱数ｒ_９と、ｚ_４ν^{－ｒ９ｒ１０}とから構成される情報の組（ｄ_２，ｒ_９，ｚ_４ν’^{－ｒ９ｒ１０}）が、リストＬ_４に追加される。この例では、第四リスト記憶部４６’に、情報の組（ｄ_２，ｒ_９，ｚ_４ν^{－ｒ９ｒ１０}）が記憶される（ステップＳ２２３’）。

　＜ステップＳ２２４’＞
　第二判定部４８’は、第三リスト記憶部３６’から読み込んだ情報の組の第一成分をｓ_３とし、第二成分をｗ_３とし、第四リスト記憶部４６’から読み込んだ情報の組の第一成分をｔ_４とし、第二成分をｓ_４とし、第三成分をｗ_４として、これらの情報の組が（ｗ_３）＾（ｔ_４ｓ_４ｓ_３ ^－１）＝ｗ_４の関係を満たすかを判定する（ステップＳ２２４’）。

　第二判定部４８’は、第三リスト記憶部３６’及び第四リスト記憶部４６’に複数の情報の組が記憶されている場合には、第三リスト記憶部３６’に記憶された情報の組（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）と、第四リスト記憶部４６’に記憶された情報の組（ｄ_２，ｒ_９，ｚ_４ν’^{－ｒ９ｒ１０}）とから構成されるすべての情報のペアについて、上記関係を満たすかどうかを判定する。もちろん、既に上記関係を満たすかどうかを判定した情報のペアについては、その判定処理を省いてもよい。

　＜ステップＳ２２５’＞
　第二判定部４８’は、上記の関係を満たす場合には、（ｗ_３）＾（ｓ_３ ^－１）を出力する（ステップＳ２２５’）。ここで、（ｗ_３）＾（ｓ_３ ^－１）＝θ（ｇ，ｈ）となる。（ｗ_３）＾（ｓ_３ ^－１）＝θ（ｇ，ｈ）となる理由については後述する。
　上記の関係を満たさない場合には、ステップＳ２１’に戻る。

　（ｗ_３）＾（ｓ_３ ^－１）の計算、すなわちｗ_３のべき乗根の計算が困難な場合には、次のようにしてθ（ｇ，ｈ）を容易に計算することができる。第二判定部４８’は、ステップＳ２１’からステップＳ２２４’の処理を繰り返して（ｗ_３）＾（ｔ_４ｓ_４ｓ_３ ^－１）＝ｗ_４の関係を満たすｗ_３とｓ_３との組（ｗ_３，ｓ_３）を順次（α_１，Ｓ_１），（α_２，Ｓ_２），…，（α_ｍ，Ｓ_ｍ），…として記憶部４１０’に記憶する。ｍは自然数である。第二判定部４８’は、Ｓ_１と互いに素となるＳ_ｍが見つかれば、Ｌ_１とＬ_２とを整数としてＬ_１Ｓ_１＋Ｌ_２Ｓ_ｍ＝１となるＬ_１及びＬ_２を計算して、そのＬ_１及びＬ_２を用いてα_１ ^Ｌ１α_ｍ ^Ｌ２を計算する。α_１ ^Ｌ１α_ｍ ^Ｌ２＝θ（ｇ，ｈ）^{（Ｌ１Ｓ１＋Ｌ２Ｓ２）}＝θ（ｇ，ｈ）となる。また、第二判定部４８’は、Ｓ_１，Ｓ_２，…，Ｓ_ｍの最小公倍数が１になれば、Ｌ_１，Ｌ_２，…，Ｌ_ｍを整数としてＬ_１Ｓ_１＋Ｌ_２Ｓ_２＋…＋Ｌ_ｍＳ_ｍ＝１となるＬ_１，Ｌ_２，…，Ｌ_ｍを計算して、そのＬ_１，Ｌ_２，…，Ｌ_ｍを用いてα_１ ^Ｌ１α_２ ^Ｌ２…α_ｍ ^Ｌｍを計算してもよい。α_１ ^Ｌ１α_２ ^Ｌ２…α_ｍ ^Ｌｍ＝θ（ｇ，ｈ）^{（Ｌ１Ｓ１＋Ｌ２Ｓ２＋…＋ＬｍＳｍ）}＝θ（ｇ，ｈ）となる。

　依頼装置１’と計算装置２’との間の通信を傍受することができる攻撃者Ｍがいるとしても、依頼装置１’及び計算装置２’との間で通信される情報を、依頼装置１’のみが知る乱数（例えば、ｒ_１，ｒ_２）で撹乱することにより、攻撃者Ｍから秘匿することができる。

　また、依頼装置１’及び計算装置２’との間で通信される情報は依頼装置１’のみが知るｒ_１，ｒ_２等の乱数で撹乱されているため、計算装置２’は、依頼装置１’が最終的に計算しようとするθ（ｇ，ｈ）はもちろんのこと、その入力であるｇ及びｈをも知ることはできない。

　したがって、計算装置２’は信頼することができる計算機である必要はなく、双準同型写像を計算するためのシステムの構成要件を緩和することができる。また、信頼することができる計算機は一般に高価であり運用に費用を要するが、計算装置２’が信頼することができる計算機である必要ないため、双準同型写像を計算するためのシステムの構築及び運用のコストを削減することができる。

　≪ν’^１／σ＝θ（ｇ，μ_ｈ）となる理由について≫
　まず、ｒａｎｄｏｍｉｚａｂｌｅ　ｓａｍｐｌｅｒと呼ばれる確率変数Ｓ_Ｘ（ｄ）について説明する。ｗ∈Ｆに関する誤差Ｘのｒａｎｄｏｍｉｚａｂｌｅ　ｓａｍｐｌｅｒである確率変数Ｓ_Ｘ（ｄ）は、Ｓ_Ｘ（ｄ）＝ｗ^ｄＸである。ｄは自然数である。

　ここで、Ｒ_１，Ｒ_２，Ｒ_１’及びＲ_２’を乱数として、計算装置がｇ^ｄμ_ｇ ^Ｒ１及びμ_ｈ ^Ｒ２を用いて行う計算の計算結果をＢ（ｇ^ｄμ_ｇ ^Ｒ１，μ_ｈ ^Ｒ２）（計算装置が依頼装置に返す計算結果をｚとすると、ｚ＝Ｂ（ｇ^ｄμ_ｇ ^Ｒ１，μ_ｈ ^Ｒ２）である。）とし、群Ｆに値を持つ確率変数ＸをＸ＝Ｂ（μ_ｇ ^Ｒ’１，μ_ｈ ^Ｒ’２）^{１／Ｒ’２}θ（μ_ｇ ^Ｒ’１，μ_ｈ）^－１と定義すると、Ｓ_Ｘ（ｄ）＝ｚ^{（１／Ｒ２）}ν^－Ｒ１は、θ（ｇ，μ_ｈ）に関する誤差Ｘのｒａｎｄｏｍｉｚａｂｌｅ　ｓａｍｐｌｅｒとなる。

　Ｓ_Ｘ（ｄ）＝ｚ^{（１／Ｒ２）}ν^－Ｒ１＝Ｂ（ｇ^ｄμ_ｇ ^Ｒ１，μ_ｈ ^Ｒ２）^１／Ｒ２θ（μ_ｇ，μ_ｈ）^－Ｒ１＝Ｘθ（ｇ^ｄμ_ｇ ^Ｒ１，μ_ｈ）θ（μ_ｇ ^Ｒ１，μ_ｈ）^－１＝Ｘθ（ｇ^ｄ，μ_ｈ）θ（μ_ｇ ^Ｒ１，μ_ｈ）θ（μ_ｇ ^Ｒ１，μ_ｈ）^－１＝θ（ｇ，μ_ｈ）^ｄＸであるためである。

　上記式展開において、Ｘ＝Ｂ（μ_ｇ ^Ｒ’１，μ_ｈ ^Ｒ’２）^{１／Ｒ’２}θ（μ_ｇ ^Ｒ’１，μ_ｈ）^－１＝Ｂ（ｇ^ｄμ_ｇ ^Ｒ１，μ_ｈ ^Ｒ２）^１／Ｒ２θ（ｇ^ｄμ_ｇ ^Ｒ１，μ_ｈ）^－１であり、Ｂ（ｇ^ｄμ_ｇ ^Ｒ１，μ_ｈ ^Ｒ２）^１／Ｒ２＝Ｘθ（ｇ^ｄμ_ｇ ^Ｒ１，μ_ｈ）であるという性質を用いている。この性質は、Ｒ_１，Ｒ_２，Ｒ_１’及びＲ_２’が乱数であることに基づく。

　ここで、Ｓ_Ｘ（１）の実現値をθ（ｇ，μ_ｈ）^１ｘ_１と表記し、Ｓ_Ｘ（ｄ）の実現値をθ（ｇ，μ_ｈ）^ｄｘ_２と表記するとして、Ｓ_Ｘ（１）の実現値のｄ乗＝Ｓ_Ｘ（ｄ）の実現値、すなわち（θ（ｇ，μ_ｈ）^１ｘ_１）^ｄ＝θ（ｇ，μ_ｈ）^ｄｘ_２となるのは、ｘ_１及びｘ_２が群Ｆの単位元ｅ_ｆのときである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。ｘ_１が群Ｆの単位元ｅ_ｆのとき、Ｓ_Ｘ（１）の実現値＝θ（ｇ，μ_ｈ）^１ｘ_１＝θ（ｇ，μ_ｈ）となる。

　上記実施形態の代理計算システムは、このｒａｎｄｏｍｉｚａｂｌｅ　ｓａｍｐｌｅｒの性質を用いている。

　ステップＳ１１’からステップＳ１１１’の処理がＳ_Ｘ（１）の実現値θ（ｇ，μ_ｈ）^１ｘ_１の計算に対応している。実際には、Ｓ_Ｘ（１）の実現値自体は計算していないが、同処理により得られる（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）を用いて、ｚ_１ν^{－ｒ１ｒ２}を１／ｒ_２乗すると、（ｚ_１ν^{－ｒ１ｒ２}）^１／ｒ２＝ｚ_１ ^１／ｒ２ν^－ｒ１となり、Ｓ_Ｘ（１）の実現値θ（ｇ，μ_ｈ）^１ｘ_１となる。同様に、ステップＳ１１２’からステップＳ１２３’の処理がＳ_Ｘ（ｄ_１）の実現値θ（ｇ，μ_ｈ）^ｄ１ｘ_２の計算に対応している。

　また、ステップＳ１２４’の処理が、Ｓ_Ｘ（１）の実現値のｄ_１乗＝Ｓ_Ｘ（ｄ_１）、すなわち（θ（ｇ，μ_ｈ）^１ｘ_１）^ｄ１＝θ（ｇ，μ_ｈ）^ｄ１ｘ_２であるかどうかの判定に対応している。ステップＳ１２４で用いる判定条件（ｗ_１）＾（ｔ_２ｓ_２ｓ_１ ^－１）は、（ｗ_１）＾（ｔ_２ｓ_２ｓ_１ ^－１）＝ｗ_２⇔（ｗ_１ ^１／ｓ１）^ｔ２＝ｗ_２ ^１／ｓ２⇔（ｚ_１ ^１／ｒ２ν^－ｒ１）^ｄ１＝ｚ_２ ^１／ｒ５ν^－ｒ４⇔（θ（ｇ，μ_ｈ）^１ｘ_１）^ｄ１＝θ（ｇ，μ_ｈ）^ｄ１ｘ_２⇔Ｓ_Ｘ（１）の実現値のｄ_１乗＝Ｓ_Ｘ（ｄ_１）の実現値であるためである。ここで、定義よりｓ_１＝ｒ_２、ｗ_１＝ｚ_１ν^{－ｒ１ｒ２}、ｔ_２＝ｄ_１、ｓ_２＝ｒ_５、ｗ_２＝ｚ_２ν^{－ｒ４ｒ５}である。

　さらに、ステップＳ１２５’におけるσ及びν’が、θ（ｇ，μ_ｈ）に対応している。上記したようにＳ_Ｘ（１）の実現値のｄ_１乗＝Ｓ_Ｘ（ｄ_１）の実現値のとき、ν’^１／σ＝ｗ_１ ^１／ｓ１＝ｚ_１ ^１／ｒ２ν^－ｒ１＝θ（ｇ，μ_ｈ）^１ｘ_１＝θ（ｇ，μ_ｈ）であるためである。

　≪（ｗ_３）＾（ｓ_３ ^－１）＝θ（ｇ，ｈ）となる理由について≫
　Ｒ_１，Ｒ_２，Ｒ_１’及びＲ_２’を乱数として、計算装置がｇ^Ｒ１及びｈ^ｄμ_ｈ ^Ｒ２を用いて行う計算の計算結果をＢ（ｇ^Ｒ１，ｈ^ｄμ_ｈ ^Ｒ２）（計算装置が依頼装置に返す計算結果をｚとすると、ｚ＝Ｂ（ｇ^Ｒ１，ｈ^ｄμ_ｈ ^Ｒ２）である。）とし、群Ｆに値を持つ確率変数ＸをＸ＝Ｂ（ｇ^Ｒ’１，μ_ｈ ^Ｒ’２）^{１／Ｒ’１}θ（ｇ，μ_ｈ ^Ｒ’２）^－１と定義すると、Ｓ_Ｘ（ｄ）＝ｚ^{（１／Ｒ１）}ν’^－Ｒ２は、θ（ｇ，ｈ）に関する誤差Ｘのｒａｎｄｏｍｉｚａｂｌｅ　ｓａｍｐｌｅｒとなる。

　Ｓ_Ｘ（ｄ）＝ｚ^{（１／Ｒ１）}ν’^－Ｒ２＝Ｂ（ｇ^Ｒ１，ｈ^ｄμ_ｈ ^Ｒ２）^１／Ｒ１θ（ｇ，μ_ｈ）^－Ｒ２＝Ｘθ（ｇ，ｈ^ｄμ_ｈ ^Ｒ２）θ（ｇ，μ_ｈ ^Ｒ２）^－１＝Ｘθ（ｇ，ｈ^ｄ）θ（ｇ，μ_ｈ ^Ｒ２）θ（ｇ，μ_ｈ ^Ｒ２）^－１＝θ（ｇ，ｈ）^ｄＸであるためである。

　上記式展開において、Ｘ＝Ｂ（ｇ^Ｒ’１，μ_ｈ ^Ｒ’２）^{１／Ｒ’１}θ（ｇ，μ_ｈ ^Ｒ’２）^－１＝Ｂ（ｇ^Ｒ１，μ_ｈ ^Ｒ２）^１／Ｒ１θ（ｇ，ｈ^ｄμ_ｈ ^Ｒ２）^－１であり、Ｂ（ｇ^Ｒ１，ｈ^ｄμ_ｈ ^Ｒ２）^１／Ｒ１＝Ｘθ（ｇ，ｈ^ｄμ_ｈ ^Ｒ２）であるという性質を用いている。この性質は、Ｒ_１，Ｒ_２，Ｒ_１’及びＲ_２’が乱数であることに基づく。

　ここで、Ｓ_Ｘ（１）の実現値をＳ_Ｘ（１）＝θ（ｇ，ｈ）^１ｘ_１と表記し、Ｓ_Ｘ（ｄ）の実現値をＳ_Ｘ（ｄ）＝θ（ｇ，ｈ）^ｄｘ_２と表記するとして、Ｓ_Ｘ（１）の実現値のｄ乗＝Ｓ_Ｘ（ｄ）、すなわち（θ（ｇ，ｈ）^１ｘ_１）^ｄ＝θ（ｇ，ｈ）^ｄｘ_２となるのは、ｘ_１及びｘ_２が群Ｆの単位元ｅ_ｆのときである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。ｘ_１が群Ｆの単位元ｅ_ｆのとき、Ｓ_Ｘ（１）の実現値＝θ（ｇ，ｈ）^１ｘ_１＝θ（ｇ，ｈ）となる。

　上記実施形態の代理計算システムは、このｒａｎｄｏｍｉｚａｂｌｅ　ｓａｍｐｌｅｒの性質を用いている。

　ステップＳ２１’からステップＳ２１１’の処理がＳ_Ｘ（１）の実現値θ（ｇ，ｈ）^１ｘ_１の計算に対応している。実際には、Ｓ_Ｘ（１）の実現値自体は計算していないが、同処理により得られる（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）を用いて、ｚ_３ν’^{－ｒ６ｒ７}を１／ｒ_６乗すると、（ｚ_３ν’^{－ｒ６ｒ７}）^１／ｒ６＝ｚ_３ ^１／ｒ６ν’^－ｒ７となり、Ｓ_Ｘ（１）の実現値θ（ｇ，ｈ）^１ｘ_１となる。同様に、ステップＳ２１２’からステップＳ２２３’の処理がＳ_Ｘ（ｄ_２）の実現値θ（ｇ，ｈ）^ｄ２ｘ_２の計算に対応している。

　また、ステップＳ２２４’の処理が、Ｓ_Ｘ（１）の実現値のｄ_２乗＝Ｓ_Ｘ（ｄ_２）の実現値、すなわち（θ（ｇ，ｈ）^１ｘ_１）^ｄ２＝θ（ｇ，ｈ）^ｄ２ｘ_２であるかどうかの判定に対応している。ステップＳ２２４’で用いる判定条件（ｗ_３）＾（ｔ_４ｓ_４ｓ_３ ^－１）＝ｗ_４は、（ｗ_３）＾（ｔ_４ｓ_４ｓ_３ ^－１）＝ｗ_４⇔（ｗ_３ ^１／ｓ３）^ｔ４＝ｗ_４ ^１／ｓ４⇔（ｚ_３ ^１／ｒ６ν’^－ｒ７）^ｄ２＝ｚ_４ ^１／ｒ９ν’^－ｒ１０⇔（θ（ｇ，ｈ）^１ｘ_１）^ｄ２＝θ（ｇ，ｈ）^ｄ２ｘ_２⇔Ｓ_Ｘ（１）の実現値のｄ_２乗＝Ｓ_Ｘ（ｄ_２）の実現値であるためである。ここで、定義よりｓ_３＝ｒ_６、ｗ_３＝ｚ_３ν’^{－ｒ６ｒ７}、ｔ_４＝ｄ_２、ｓ_４＝ｒ_９、ｗ_４＝ｚ_４ν’^{－ｒ９ｒ１０}である。

　さらに、ステップＳ２２５’における（ｗ_３）＾（ｓ_３ ^－１）が、θ（ｇ，ｈ）に対応している。上記したようにＳ_Ｘ（１）の実現値のｄ_２乗＝Ｓ_Ｘ（ｄ_２）の実現値のとき、（ｗ_３）＾（ｓ_３ ^－１）＝（ｚ_３ν’^{－ｒ６ｒ７}）＾（ｒ_６ ^－１）＝ｚ_３ ^１／ｒ６ν’^－ｒ７＝θ（ｇ，ｈ）^１ｘ_１＝θ（ｇ，ｈ）であるためである。

　［第五実施形態］
　第五実施形態の代理計算システムは、ステップＳ１３’、ステップＳ１１０’及びステップＳ１１１’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。

　第一入力情報計算部１３’は、ｇ_１＝μ_ｇ ^ｒ１ｇではなく、ｇ_１＝ｇ^ｒ１で定義される第一入力情報を計算する（ステップＳ１３’）。
　第一リスト情報計算部１５’は、ｚ_１ν^{－ｒ１ｒ２}ではなく、乱数ｒ_１及び乱数ｒ_２を用いてｒ_１ｒ_２を計算して、その計算結果を第一リスト記憶部１６’に送る（ステップＳ１１０’）。
　第一リスト記憶部１６’には、情報の組（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）ではなく、計算されたｒ_１ｒ_２と計算装置２’から受信したｚ_１∈Ｆとから構成される情報の組（ｒ_１ｒ_２，ｚ_１）が記憶される（ステップＳ１１１’）。

　第四実施形態のステップＳ１１０’では、ｚ_１ν^{－ｒ１ｒ２}という群Ｆのべき演算を行う必要があったが、第五実施形態のステップＳ１１０’ではｒ_１ｒ_２の計算を行っておりべき演算の回数が１回減っている。このように、べき演算の回数を減らすことにより演算の効率性を増すことができる。また、群Ｇ、群Ｈにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。

　［第六実施形態］
　第六実施形態の代理計算システムは、ステップＳ２４’、ステップＳ２１０’及びステップＳ２１１’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。

　第六入力情報計算部３４’は、ｈ_３＝μ_ｈ ^ｒ７σｈではなく、ｈ_３＝ｈ^ｒ７で定義される第六入力情報ｈ_３を計算する（ステップＳ２４’）。
　第三リスト情報計算部３５’は、ｚ_３ν’^{－ｒ６ｒ７}ではなく、乱数ｒ_６及び乱数ｒ_７を用いてｒ_６ｒ_７を計算する（ステップＳ２１０’）。
　第三リスト記憶部３６’には、情報の組（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）ではなく、計算されたｒ_６ｒ_７と計算装置２’から受信したｚ_３∈Ｆとから構成される情報の組（ｒ_６ｒ_７，ｚ_３）が記憶される（ステップＳ２１１’）。

　第四実施形態のステップＳ２１０’では、ｚ_３ν’^{－ｒ６ｒ７}という群Ｆのべき演算を行う必要があったが、第六実施形態のステップＳ２１０’ではｒ_６ｒ_７の計算を行っておりべき演算の回数が１回減っている。このように、べき演算の回数を減らすことにより演算の効率性を増すことができる。

　群Ｇ、群Ｈにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。

　［第七実施形態］
　第七実施形態の代理計算システムは、ステップＳ１２５’及びステップＳ２１４’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。
第一判定部２８’は、上記の関係を満たす場合には、ｔ_１ｓ_２をσに代入し、ｗ_２をν’に代入する（ステップＳ１２５’）。
第十乱数生成部４２’は、乱数ｒ_９を用いて－ｒ_９ ^－１を計算してｒ_１０とする（ステップＳ２１４’）。

　このように、ν’の定義を変更して、σを計算装置２’にとって推測が困難な乱数とすることにより安全性が増す。また、乱数ｒ_９を用いて乱数ｒ_１０を計算することにより、乱数を生成する回数を減らすことができる。乱数ｒ_１０が乱数ｒ_９により定まるため第八入力情報ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２の乱雑性が低下し安全性が損なわれるとも思われるが、第八入力情報ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２は乱数ｒ_１０だけでなく更にσにより撹乱されているため安全性は損なわれない。

　なお、第七実施形態においては更にステップＳ２２’及びステップＳ２１１’を以下のように変更してもよい。

　第七乱数生成部３２’は、乱数ｒ_６を用いて－ｒ_６ ^－１を計算してｒ_７とする（ステップＳ２２’）。
　第三リスト記憶部３６’には、１と上記計算されたｚ_３ν’^{－ｒ６ｒ７}とから構成される情報の組（１，ｚ_３ν’^{－ｒ６ｒ７}）が記憶される（ステップＳ２１１’）。

　このように、乱数ｒ_６を用いて乱数ｒ_７を計算することにより乱数を生成する回数を減らすことができる。
群Ｇ、群Ｈにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。

　［第八実施形態］
　第八実施形態の代理計算システムは、ステップＳ１１３’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。

　まず、ステップＳ１１３’に先立ち、第五乱数生成部２２’は乱数ｒ_５を生成する（ステップＳ１１４’）。
　第四乱数生成部２１’は、乱数ｒ_５を用いて－ｒ_５ ^－１を計算してｒ_４とする（ステップＳ１１３’）。
　このように、乱数ｒ_５を用いて乱数ｒ_４を計算することにより乱数を生成する回数を減らすことができる。

　群Ｈの任意の元ｈについて、ｇ∈Ｇでθ（ｇ，ｈ）＝νとなるものを計算することが困難ならば、第四実施形態と比較して安全性は低下しない。

　［第九実施形態］
　第九実施形態の代理計算システムは、依頼装置１’が図１２に破線で示された事前計算部２９’を更に含み、ステップＳ１１５’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。

　事前計算部２９’は、第三乱数生成部２７’が生成したｄ_１を用いてｇ^ｄ１を計算する。この処理は、ステップＳ１１２’の後、ステップＳ１１５’の前に行う。
　第三入力情報計算部２３’は、事前計算されたｇ^ｄ１を用いて、ｇ_２＝μ_ｇ ^ｒ４ｇ^ｄ１の計算を行う（ステップＳ１１５’）。

　ステップＳ１１４’で、判定条件を満たさない場合にはステップＳ１１’からステップＳ１２３’の処理が繰り返されるが、この繰り返しの処理においては、事前計算されたｇ^ｄ１を再利用する。すなわち、第三乱数生成部２７’は乱数ｄ_１を生成せず、第三入力情報計算部２３’は事前計算されたｇ^ｄ１を用いて、ｇ_２＝μ_ｇ ^ｒ４ｇ^ｄ１の計算を行う。これにより、乱数ｄ_１を生成する回数を減らすことができ、ｇ_２＝μ_ｇ ^ｒ４ｇ^ｄ１の計算を速く行うことができる。

　［第十実施形態］
　第十実施形態の代理計算システムは、依頼装置１’が図１３に破線で示された事前計算部４９’を更に含み、ステップＳ２１６’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。

　事前計算部４９’は、第八乱数生成部４７’が生成したｄ_２を用いてｈ^ｄ２を計算する。この処理は、ステップＳ２１２’の後、ステップＳ２１６’の前に行う。
　第八入力情報計算部４４’は、事前計算されたｈ^ｄ２を用いて、第八入力情報ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２の計算を行う（ステップＳ１１６’）。

　ステップＳ２１４’で、判定条件を満たさない場合にはステップＳ２１’からステップＳ２２３’の処理が繰り返されるが、この繰り返しの処理においては、事前計算されたｈ^ｄ２を再利用する。すなわち、第八乱数生成部４７’は乱数ｄ_２を生成せず、第八入力情報計算部４４’は事前計算されたｈ^ｄ２を用いて、ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２の計算を行う。これにより、乱数ｄ_２を生成する回数を減らすことができ、ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２の計算を速く行うことができる。

　［第四実施形態から第十実施形態の変形例等］
　第一乱数生成部１１’、第二乱数生成部１２’、第三乱数生成部２７’、第四乱数生成部２１’、第五乱数生成部２２’、第六乱数生成部３１’、第七乱数生成部３２’、第八乱数生成部４７’、第九乱数生成部４１’及び第十乱数生成部４２’のそれぞれは、一様乱数を生成することにより、代理計算システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部１１’、第二乱数生成部１２’、第三乱数生成部２７’、第四乱数生成部２１’、第五乱数生成部２２’、第六乱数生成部３１’、第七乱数生成部３２’、第八乱数生成部４７’、第九乱数生成部４１’及び第十乱数生成部４２’のそれぞれは、一様乱数ではない乱数を生成してもよい。

　リストＬ_１、リストＬ_２に情報の組が追加される毎に、第一判定部２８’の処理を行ってもよい。例えば、第二リスト記憶部２６’に情報の組（ｄ_１，ｒ_５，ｚ_２ν^{－ｒ４ｒ５}）が記憶されている場合には、ステップＳ１１１’の後に、ステップＳ１２４’の処理を行っても良い。同様に、リストＬ_３、リストＬ_４に情報の組が追加される毎に、第二判定部４８’の処理を行ってもよい。

　第四実施形態から第十実施形態は互いに組み合わせることができる。

　依頼装置１’の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、計算装置２’の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。

　依頼装置１’及び計算装置２’のそれぞれはコンピュータによって実現することができる。この場合、この装置が有すべき各機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これ装置における各処理機能が、コンピュータ上で実現される。

　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

　なお、第一実施形態から第三実施形態と、第四実施形態から第十実施形態とを組み合わせてもよい。例えば、図１７に例示するように、第一実施形態から第三実施形態の計算装置２が第四実施形態から第十実施形態の依頼装置１’を備えており、この依頼装置１’を含む計算装置２が、第四実施形態から第十実施形態で説明したのと同様にして計算装置２’を用いて、関数ｆの計算を行ってもよい。

　具体的には、計算装置２は計算する必要がある関数ｆ（ｘ）を計算するために、対応する写像θ（ｇ，ｈ）の値を、計算装置２’を用いて計算する。関数ｆ（ｘ）に対応する写像θ（ｇ，ｈ）とは、与えられた関数ｆ及びｘに対して、関数ｆ（ｘ）と値が同じ値を出力する写像θ（ｇ，ｈ）である。ある元ｈ∈Ｈに関して、ｆ（ｘ）＝θ（ｘ，ｈ）という関係がある場合には、ｆ（ｘ）に対応する写像θがθ（ｘ，ｈ）となる。

　例えば、参考文献１に記載されたＢｏｎｅｈ－Ｆｒａｎｋｌｉｎ方式のＩＤベース暗号において、ある一定のＩＤに関する復号関数をｆとする。この方式のＩＤベース暗号では、楕円曲線の点がなす有限群Ｇ，Ｈと、ペアリングτ：Ｇ×Ｈ→Ｆを用いて構成される。ＱをＧの元とする。ＩＤベース暗号の鍵発行センタの秘密鍵をｓとして、公開鍵をＰ＝ｓＱとする。ＩＤベース暗号のパブリックパラメータは、群Ｇ，Ｈの記述と、ペアリングτの記述、Ｑ及びＰである。

　〔参考文献１〕Dan Boneh, Matt Franklin, “Identity-Based Encryption from the Weil Pairing”, CRYPTO 2001, LNCS 2139, pp.213-229, 2001.
　鍵の発行は以下のようにして行われる。鍵発行センタは、ＩＤに対応して定まるＨの元Ｑ_ＩＤについて、Ｐ_ＩＤ＝ｓＱ_ＩＤを計算してＩＤの保持者に対して通知する。Ｐ_ＩＤはＩＤの保持者の秘密鍵である。このとき、復号関数ｆ：Ｇ→Ｆは、ｆ（ｘ）＝τ（ｘ，Ｐ_ＩＤ）で定義される。

　暗号文の作成、暗号文の復号は以下のようにして行われる。平文ｍをあるＩＤについて暗号化するためには、乱数ｒを生成して（Ｑ^ｒ，ｍ（＋）Ｈ（τ（Ｐ^ｒ，Ｑ_ＩＤ）））を計算し、これを暗号文（Ｃ_１，Ｃ_２）とする。復号するためには、暗号文（Ｃ_１，Ｃ_２）に対して、Ｃ_２（＋）Ｈ（ｆ（Ｃ_１））を計算することで平文が得られる。ただし、ここでＨはハッシュ関数、（＋）は排他的論理和である。

　このようなＢｏｎｅｈ－Ｆｒａｎｋｌｉｎ方式のＩＤベース暗号において、関数ｆ（ｘ）に対応する写像θは例えばペアリングτを用いて定義される。すなわち、ｆ（ｘ）＝τ（ｘ，Ｐ_ＩＤ）である。

　計算装置２がＩＣカードや携帯電話であり、秘密情報の抽出が困難であるが、計算能力が限定されている場合に、このように依頼装置及び計算装置を多重にして組み合わせることが有益である。

　この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。

Claims (19)

1. 　Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ_１，Ｘ_２を群Ｇに値を持つ確率変数、確率変数Ｘ_１の実現値をｘ_１、確率変数Ｘ_２の実現値をｘ_２として、
   　互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する整数計算部と、
   　ｆ（ｘ）^ｂｘ_１を計算可能であり、その計算結果をｕとする第一乱数化可能標本器と、
   　ｕ’＝ｕ^ａを計算する第一べき乗計算部と、
   　ｆ（ｘ）^ａｘ_２を計算可能であり、その計算結果をｖとする第二乱数化可能標本器と、
   　ｖ’＝ｖ^ｂを計算する第二べき乗計算部と、
   　ｕ’＝ｖ’であるか判定する判定部と、
   　ｕ’＝ｖ’であると判定された場合には、ｕ^ｂ’ｖ^ａ’を計算する最終計算部と、
   　を含む代理計算システム。
2. 　請求項１の代理計算システムにおいて、
   　Ｘ_３を群Ｇに値を持つ確率変数、確率変数Ｘ_３の実現値をｘ_３として、ｆ（ｘ）ｘ_３を計算可能であり、ａ＝１あれば上記第二乱数化可能標本器に代わりその計算結果を上記ｖとし、ｂ＝１であれば上記第一乱数化可能標本器に代わりその計算結果を上記ｕとする標本器を更に含む、
   　代理計算システム。
3. 　請求項１の代理計算システムにおいて、
   　上記ｆを準同型写像、群Ｈの生成元をμ_ｈ、群Ｈの位数をＫ_Ｈ、ν＝ｆ（μ_ｈ）として、
   　上記第一乱数化可能標本器は、０以上Ｋ_Ｈ未満の整数の乱数ｒ_１を生成する第一乱数生成部と、第一入力情報μ_ｈ ^ｒ１ｘ^ｂを計算する第一入力情報計算部と、上記第一入力情報μ_ｈ ^ｒ１ｘ^ｂを用いてｆ（μ_ｈ ^ｒ１ｘ^ｂ）を計算可能でありその計算結果を第一出力情報ｚ_１とする第一出力情報計算部と、ｚ_１ν^－ｒ１を計算してその計算結果を上記ｕとする第一計算部とを含み、
   　上記第二乱数化可能標本器は、０以上Ｋ_Ｈ未満の整数の乱数ｒ_２を生成する第二乱数生成部と、第二入力情報μ_ｈ ^ｒ２ｘ^ａを計算する第二入力情報計算部と、上記第二入力情報μ_ｈ ^ｒ２ｘ^ａを用いてｆ（μ_ｈ ^ｒ２ｘ^ａ）を計算可能でありその計算結果を第二出力情報ｚ_２とする第二出力情報計算部と、ｚ_２ν^－ｒ２を計算してその計算結果を上記ｖとする第二計算部とを含む、
   　代理計算システム。
4. 　請求項３の代理計算システムにおいて、
   　０以上Ｋ_Ｈ未満の整数の乱数ｒ_３を生成する第三乱数生成部と、第三入力情報ｘ^ｒ３を計算する第三入力情報計算部と、上記第三入力情報ｘ^ｒ３を用いてｆ（ｘ^ｒ３）を計算可能でありその計算結果を第三出力情報ｚ_３とする第三出力情報計算部と、ｚ_３ ^１／ｒ３を計算してａ＝１あれば上記第二乱数化可能標本器に代わりその計算結果を上記ｖとしｂ＝１であれば上記第一乱数化可能標本器に代わりその計算結果を上記ｕとする第三計算部とを含む標本器を更に含む、
   　代理計算システム。
5. 　請求項１の代理計算システムにおいて、
   　群Ｈ＝Ｇ×Ｇ、上記ｆを準同型写像、群Ｇの生成元をμ_ｇ、群Ｇの位数をＫ_Ｇ、ｘ＝（ｃ_１，ｃ_２），（Ｖ，Ｗ）を群Ｈの元、ｆ（Ｖ，Ｗ）＝Ｙとして、
   　上記第一乱数化可能標本器は、０以上Ｋ_Ｇ未満の整数の乱数ｒ_４を生成する第四乱数生成部と、０以上Ｋ_Ｇ未満の整数の乱数ｒ_５を生成する第五乱数生成部と、第四入力情報ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５を計算する第四入力情報計算部と、第五入力情報ｃ_２ ^ｂＷ^ｒ４を計算する第五入力情報計算部と、上記第四入力情報ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５及び上記第五入力情報ｃ_２ ^ｂＷ^ｒ４を用いてｆ（ｃ_１ ^ｂＶ^ｒ４μ_ｇ ^ｒ５，ｃ_２ ^ｂＷ^ｒ４）を計算可能でありその計算結果を第四出力情報ｚ_４とする第四出力情報計算部と、ｚ_４Ｙ^－ｒ４μ_ｇ ^－ｒ５を計算してその計算結果を上記ｕとする第四計算部とを含み、
   　上記第二乱数化可能標本器は、０以上Ｋ_Ｇ未満の整数の乱数ｒ_６を生成する第六乱数生成部と、０以上Ｋ_Ｇ未満の整数の乱数ｒ_７を生成する第七乱数生成部と、第六入力情報ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７を計算する第六入力情報計算部と、第七入力情報ｃ_２ ^ａＷ^ｒ６を計算する第七入力情報計算部と、上記第六入力情報ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７及び上記第七入力情報ｃ_２ ^ａＷ^ｒ６を用いてｆ（ｃ_１ ^ａＶ^ｒ６μ_ｇ ^ｒ７，ｃ_２ ^ａＷ^ｒ６）を計算可能でありその計算結果を第五出力情報ｚ_５とする第五出力情報計算部と、ｚ_５Ｙ^－ｒ６μ_ｇ ^－ｒ７を計算してその計算結果を上記ｖとする第五計算部とを含む、
   　代理計算システム。
6. 　Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ_１，Ｘ_２を群Ｇに値を持つ確率変数、確率変数Ｘ_１の実現値をｘ_１、確率変数Ｘ_２の実現値をｘ_２として、
   　整数計算部が、互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する整数計算ステップと、
   　第一乱数化可能標本器が、ｆ（ｘ）^ｂｘ_１を計算可能であり、その計算結果をｕとする第一乱数化可能標本抽出ステップと、
   　第一べき乗計算部が、ｕ’＝ｕ^ａを計算する第一べき乗計算ステップと、
   　第二乱数化可能標本器が、ｆ（ｘ）^ａｘ_２を計算可能であり、その計算結果をｖとする第二乱数化可能標本抽出ステップと、
   　第二べき乗計算部が、ｖ’＝ｖ^ｂを計算する第二べき乗計算ステップと、
   　判定部が、ｕ’＝ｖ’であるか判定する判定ステップと、
   　最終計算部が、ｕ’＝ｖ’であると判定された場合には、ｕ^ｂ’ｖ^ａ’を計算する最終計算ステップと、
   　を含む代理計算方法。
7. 　Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ_１，Ｘ_２を群Ｇに値を持つ確率変数、確率変数Ｘ_１の実現値をｘ_１、確率変数Ｘ_２の実現値をｘ_２として、
   　互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する整数計算部と、
   　ｆ（ｘ）^ｂｘ_１を計算可能な第一乱数化可能標本器による計算結果ｕを用いてｕ’＝ｕ^ａを計算する第一べき乗計算部と、
   　ｆ（ｘ）^ａｘ_２を計算可能な第二乱数化可能標本器による計算結果ｖを用いてｖ’＝ｖ^ｂを計算する第二べき乗計算部と、
   　ｕ’＝ｖ’であるか判定する判定部と、
   　ｕ’＝ｖ’であると判定された場合には、ｕ^ｂ’ｖ^ａ’を計算する最終計算部と、
   　を含む依頼装置。
8. 　依頼装置が計算装置に依頼した計算の結果を用いてθ（ｇ，ｈ）を計算する代理計算システムにおいて、
   　Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、Ｋ_Ｇを群Ｇの位数とし、Ｋ_Ｈを群Ｈの位数とし、μ_ｇを群Ｇの生成元とし、μ_ｈを群Ｈの生成元とし、ν＝θ（μ_ｇ，μ_ｇ）とし、ｋを自然数のセキュリティパラメータとし、Ｋ＝２^ｋとして、
   　上記依頼装置は、
   　０以上Ｋ_Ｇ未満の整数の乱数ｒ_１を生成する第一乱数生成部と、
   　０以上Ｋ_Ｈ未満の整数の乱数ｒ_２を生成する第二乱数生成部と、
   　第一入力情報ｇ_１＝μ_ｇ ^ｒ１ｇを計算する第一入力情報計算部と、
   　第二入力情報ｈ_１＝μ_ｈ ^ｒ２を計算する第二入力情報計算部と、
   　上記計算装置から受信したｚ_１∈Ｆを用いて、ｚ_１ν^{－ｒ１ｒ２}を計算する第一リスト情報計算部と、
   　上記乱数ｒ_２と上記計算されたｚ_１ν^{－ｒ１ｒ２}とから構成される情報の組（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）が記憶される第一リスト記憶部と、
   　０以上Ｋ未満の整数の一様乱数であるｄ_１を生成する第三乱数生成部と、
   　０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_４を生成する第四乱数生成部と、
   　０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_５を生成する第五乱数生成部と、
   　第三入力情報ｇ_２＝μ_ｇ ^ｒ４ｇ^ｄ１を計算する第三入力情報計算部と、
   　第四入力情報ｈ_２＝μ_ｈ ^ｒ５を計算する第四入力情報計算部と、
   　上記計算装置から受信したｚ_２∈Ｆを用いて、ｚ_２ν^{－ｒ４ｒ５}を計算する第二リスト情報計算部と、
   　上記ｄ_１と上記ｒ_５と上記計算されたｚ_２ν^{－ｒ４ｒ５}とから構成される情報の組（ｄ_１，ｒ_５，ｚ_２ν^{－ｒ４ｒ５}）が記憶される第二リスト記憶部と、
   　上記第一リスト記憶部から読み込んだ情報の組の第一成分をｓ_１とし、第二成分をｗ_１とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をｔ_２とし、第二成分をｓ_２とし、第三成分をｗ_２として、これらの情報の組が（ｗ_１）＾（ｔ_２ｓ_２ｓ_１ ^－１）＝ｗ_２の関係を満たすかを判定し、その関係を満たす場合には、ｓ_１をσに代入し、ｗ_１をν’に代入する第一判定部と、
   　０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_６を生成する第六乱数生成部と、
   　０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_７を生成する第七乱数生成部と、
   　第五入力情報ｇ_３＝ｇ^ｒ６を計算する第五入力情報計算部と、
   　第六入力情報ｈ_３＝μ_ｈ ^ｒ７σｈを計算する第六入力情報計算部と、
   　上記計算装置から受信したｚ_３∈Ｆを用いて、ｚ_３ν’^{－ｒ６ｒ７}を計算する第三リスト情報計算部と、
   　上記ｒ_６と上記計算されたｚ_３ν’^{－ｒ６ｒ７}とから構成される情報の組（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）が記憶される第三リスト記憶部と、
   　０以上Ｋ未満の整数の一様乱数であるｄ_２を生成する第八乱数生成部と、
   　０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_９を生成する第九乱数生成部と、
   　０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_１０を生成する第十乱数生成部と、
   　第七入力情報ｇ_４＝μ_ｇ ^ｒ９を計算する第七入力情報計算部と、
   　第八入力情報ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２を計算する第八入力情報計算部と、
   　上記計算装置から受信したｚ_４∈Ｆを用いて、ｚ_４ν’^{－ｒ９ｒ１０}を計算する第四リスト情報計算部と、
   　上記ｄ_２と上記ｒ_９と上記計算されたｚ_４ν’^{－ｒ９ｒ１０}とから構成される情報の組（ｄ_２，ｒ_９，ｚ_４ν’^{－ｒ９ｒ１０}）が記憶される第四リスト記憶部と、
   　上記第三リスト記憶部から読み込んだ情報の組の第一成分をｓ_３とし、第二成分をｗ_３とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をｔ_４とし、第二成分をｓ_４とし、第三成分をｗ_４として、これらの情報の組が（ｗ_３）＾（ｔ_４ｓ_４ｓ_３ ^－１）＝ｗ_４の関係を満たすかを判定し、その関係を満たす場合には、（ｗ_３）＾（ｓ_３ ^－１）を出力する第二判定部と、
   　を含み、
   　上記計算装置は、
   　上記依頼装置から受信したｇ_１及びｈ_１を用いてθ（ｇ_１，ｈ_１）を計算可能であり、その計算結果を上記ｚ_１として出力する第一出力情報計算部と、
   　上記依頼装置から受信したｇ_２及びｈ_２を用いてθ（ｇ_２，ｈ_２）を計算可能であり、その計算結果を上記ｚ_２として出力する第二出力情報計算部と、
   　上記依頼装置から受信したｇ_３及びｈ_３を用いてθ（ｇ_３，ｈ_３）を計算可能であり、その計算結果を上記ｚ_３として出力する第三出力情報計算部と、
   　上記依頼装置から受信したｇ_４及びｈ_４を用いてθ（ｇ_４，ｈ_４）を計算可能であり、その計算結果を上記ｚ_４として出力する第四出力情報計算部と、
   を含む、
   　代理計算システム。
9. 　請求項８の代理計算システムにおいて、
   　上記第一入力情報計算部は、第一入力情報ｇ_１＝ｇ^ｒ１を計算し、
   　上記第一リスト情報計算部は、上記ｒ_１及び上記ｒ_２を用いてｒ_１ｒ_２を計算し、
   　上記第一リスト記憶部には、上記計算されたｒ_１ｒ_２と上記計算装置から受信したｚ_１∈Ｆとから構成される情報の組（ｒ_１ｒ_２，ｚ_１）が記憶される、
   　ことを特徴とする代理計算システム。
10. 　請求項８又は９に記載の代理計算システムにおいて、
    　上記第六入力情報計算部は、第六入力情報ｈ_３＝ｈ^ｒ７を計算し、
    　上記第三リスト情報計算部は、上記ｒ_６及び上記ｒ_７を用いてｒ_６ｒ_７を計算し、
    　上記第三リスト記憶部には、上記計算されたｒ_６ｒ_７と上記計算装置から受信したｚ_３∈Ｆとから構成される情報の組（ｒ_６ｒ_７，ｚ_３）が記憶される、
    　ことを特徴とする代理計算システム。
11. 　請求項８から１０の何れかに記載の代理計算システムにおいて、
    　上記第一判定部は、上記の関係を満たす場合には、ｔ_１ｓ_２をσに代入し、ｗ_２をν’に代入し、
    　上記第十乱数生成部は、上記ｒ_９を用いて－ｒ_９ ^－１を計算してｒ_１０とする、
    　ことを特徴とする代理計算システム。
12. 　請求項１１に記載の代理計算システムにおいて、
    　上記第七乱数生成部は、上記ｒ_６を用いて－ｒ_６ ^－１を計算してｒ_７とし、
    　上記第三リスト記憶部には、１と上記計算されたｚ_３ν’^{－ｒ６ｒ７}とから構成される情報の組（１，ｚ_３ν’^{－ｒ６ｒ７}）が記憶される、
    　ことを特徴とする代理計算システム。
13. 　請求項８から１２の何れかに記載の代理計算システムにおいて、
    　上記第四乱数生成部は、上記ｒ_５を用いて－ｒ_５ ^－１を計算してｒ_４とする、
    　ことを特徴とする代理計算システム。
14. 　請求項８から１３の何れかに記載の代理計算システムにおいて、
    　上記ｄ_１を用いてｇ^ｄ１を計算する事前計算部を更に含み、
    　上記第三入力情報計算部は、上記事前計算されたｇ^ｄ１を用いて、上記ｇ_２の計算を行う、　ことを特徴とする代理計算システム。
15. 　請求項８から１４の何れかに記載の代理計算システムにおいて、
    　上記ｄ_２を用いてｈ^ｄ２を計算する事前計算部を更に含み、
    　上記第八入力情報計算部は、上記事前計算されたｈ^ｄ２を用いて、上記ｈ_４の計算を行う、
    　ことを特徴とする代理計算システム。
16. 　依頼装置が計算装置に依頼した計算の結果を用いてθ（ｇ，ｈ）を計算する代理計算方法において、
    　Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、Ｋ_Ｇを群Ｇの位数とし、Ｋ_Ｈを群Ｈの位数とし、μ_ｇを群Ｇの生成元とし、μ_ｈを群Ｈの生成元とし、ν＝θ（μ_ｇ，μ_ｇ）とし、ｋを整数のセキュリティパラメータとし、Ｋ＝２^ｋとして、
    　上記依頼装置の第一乱数生成部が、０以上Ｋ_Ｇ未満の整数の乱数ｒ_１を生成する第一乱数生成ステップと、
    　上記依頼装置の第二乱数生成部が、０以上Ｋ_Ｈ未満の整数の乱数ｒ_２を生成する第二乱数生成ステップと、
    　上記依頼装置の第一入力情報計算部が、第一入力情報ｇ_１＝μ_ｇ ^ｒ１ｇを計算する第一入力情報計算ステップと、
    　上記依頼装置の第二入力情報計算部が、第二入力情報ｈ_１＝μ_ｈ ^ｒ２を計算する第二入力情報計算ステップと、
    　上記計算装置の第一出力情報計算部が、上記依頼装置から受信したｇ_１及びｈ_１を用いてθ（ｇ_１，ｈ_１）を計算可能であり、その計算結果を上記ｚ_１として出力する第一出力情報計算ステップと、
    　上記依頼装置の第一リスト情報計算部が、上記計算装置から受信したｚ_１∈Ｆを用いて、ｚ_１ν^{－ｒ１ｒ２}を計算する第一リスト情報計算ステップと、
    　上記依頼装置の第一リスト記憶部に、上記乱数ｒ_２と上記計算されたｚ_１ν^{－ｒ１ｒ２}とから構成される情報の組（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）が記憶されるステップと、
    　上記依頼装置の第三乱数生成部が、０以上Ｋ未満の整数の一様乱数であるｄ_１を生成する第三乱数生成ステップと、
    　上記依頼装置の第四乱数生成部が、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_４を生成する第四乱数生成ステップと、
    　上記依頼装置の第五乱数生成部が、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_５を生成する第五乱数生成ステップと、
    　上記依頼装置の第三入力情報計算部が、第三入力情報ｇ_２＝μ_ｇ ^ｒ４ｇ^ｄ１を計算する第三入力情報計算ステップと、
    　上記依頼装置の第四入力情報計算部が、第四入力情報ｈ_２＝μ_ｈ ^ｒ５を計算する第四入力情報計算ステップと、
    　上記計算装置の第二出力情報計算部が、上記依頼装置から受信したｇ_２及びｈ_２を用いてθ（ｇ_２，ｈ_２）を計算可能であり、その計算結果を上記ｚ_２として出力する第二出力情報計算ステップと、
    　上記依頼装置の第二リスト情報計算部が、上記計算装置から受信したｚ_２∈Ｆを用いて、ｚ_２ν^{－ｒ４ｒ５}を計算する第二リスト情報計算ステップと、
    　上記依頼装置の第二リスト記憶部に、上記ｄ_１と上記ｒ_５と上記計算されたｚ_２ν^{－ｒ４ｒ５}とから構成される情報の組（ｄ_１，ｒ_５，ｚ_２ν^{－ｒ４ｒ５}）が記憶されるステップと、
    　上記依頼装置の第一判定部が、上記第一リスト記憶部から読み込んだ情報の組の第一成分をｓ_１とし、第二成分をｗ_１とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をｔ_２とし、第二成分をｓ_２とし、第三成分をｗ_２として、これらの情報の組が（ｗ_１）＾（ｔ_２ｓ_２ｓ_１ ^－１）＝ｗ_２の関係を満たすかを判定し、その関係を満たす場合には、ｓ_１をσに代入し、ｗ_１をν’に代入する第一判定ステップと、
    　上記依頼装置の第六乱数生成部が、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_６を生成する第六乱数生成ステップと、
    　上記依頼装置の第七乱数生成部が、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_７を生成する第七乱数生成ステップと、
    　上記依頼装置の第五入力情報計算部が、第五入力情報ｇ_３＝ｇ^ｒ６を計算する第五入力情報計算ステップと、
    　上記依頼装置の第六入力情報計算部が、第六入力情報ｈ_３＝μ_ｈ ^ｒ７σｈを計算する第六入力情報計算ステップと、
    　上記計算装置の第三出力情報計算部が、上記依頼装置から受信したｇ_３及びｈ_３を用いてθ（ｇ_３，ｈ_３）を計算可能であり、その計算結果を上記ｚ_３として出力する第三出力情報計算ステップと、
    　上記依頼装置の第三リスト情報計算部が、上記計算装置から受信したｚ_３∈Ｆを用いて、ｚ_３ν’^{－ｒ６ｒ７}を計算する第三リスト情報計算ステップと、
    　上記依頼装置の第三リスト記憶部に、上記ｒ_６と上記計算されたｚ_３ν’^{－ｒ６ｒ７}とから構成される情報の組（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）が記憶されるステップと、
    　上記依頼装置の第八乱数生成部が、０以上Ｋ未満の整数の一様乱数であるｄ_２を生成する第八乱数生成ステップと、
    　上記依頼装置の第九乱数生成部が、０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_９を生成する第九乱数生成ステップと、
    　上記依頼装置の第十乱数生成部が、０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_１０を生成する第十乱数生成ステップと、
    　上記依頼装置の第七入力情報計算部が、第七入力情報ｇ_４＝μ_ｇ ^ｒ９を計算する第七入力情報計算ステップと、
    　上記依頼装置の第八入力情報計算部が、第八入力情報ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２を計算する第八入力情報計算ステップと、
    　上記計算装置の第四出力情報計算部が、上記依頼装置から受信したｇ_４及びｈ_４を用いてθ（ｇ_４，ｈ_４）を計算可能であり、その計算結果を上記ｚ_４として出力する第四出力情報計算ステップと、
    　上記依頼装置の第四リスト情報計算部が、上記計算装置から受信したｚ_４∈Ｆを用いて、ｚ_４ν’^{－ｒ９ｒ１０}を計算する第四リスト情報計算ステップと、
    　上記依頼装置の第四リスト記憶部に、上記ｄ_２と上記ｒ_９と上記計算されたｚ_４ν’^{－ｒ９ｒ１０}とから構成される情報の組（ｄ_２，ｒ_９，ｚ_４ν’^{－ｒ９ｒ１０}）が記憶されるステップと、
    　上記依頼装置の第二判定部が、上記第三リスト記憶部から読み込んだ情報の組の第一成分をｓ_３とし、第二成分をｗ_３とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をｔ_４とし、第二成分をｓ_４とし、第三成分をｗ_４として、これらの情報の組が（ｗ_３）＾（ｔ_４ｓ_４ｓ_３ ^－１）＝ｗ_４の関係を満たすかを判定し、その関係を満たす場合には、（ｗ_３）＾（ｓ_３ ^－１）を出力する第二判定ステップと、
    　を含む代理計算方法。
17. 　依頼装置が計算装置に依頼した計算の結果を用いてθ（ｇ，ｈ）を計算する代理計算システムの依頼装置において、
    　Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、Ｋ_Ｇを群Ｇの位数とし、Ｋ_Ｈを群Ｈの位数とし、μ_ｇを群Ｇの生成元とし、μ_ｈを群Ｈの生成元とし、ν＝θ（μ_ｇ，μ_ｇ）とし、ｋを自然数のセキュリティパラメータとし、Ｋ＝２^ｋとして、
    　０以上Ｋ_Ｇ未満の整数の乱数ｒ_１を生成する第一乱数生成部と、
    　０以上Ｋ_Ｈ未満の整数の乱数ｒ_２を生成する第二乱数生成部と、
    第一入力情報ｇ_１＝μ_ｇ ^ｒ１ｇを計算する第一入力情報計算部と、
    　第二入力情報ｈ_１＝μ_ｈ ^ｒ２を計算する第二入力情報計算部と、
    　上記計算装置から受信したｚ_１∈Ｆを用いて、ｚ_１ν^{－ｒ１ｒ２}を計算する第一リスト情報計算部と、
    　上記乱数ｒ_２と上記計算されたｚ_１ν^{－ｒ１ｒ２}とから構成される情報の組（ｒ_２，ｚ_１ν^{－ｒ１ｒ２}）が記憶される第一リスト記憶部と、
    　０以上Ｋ未満の整数の一様乱数であるｄ_１を生成する第三乱数生成部と、
    　０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_４を生成する第四乱数生成部と、
    　０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_５を生成する第五乱数生成部と、
    　第三入力情報ｇ_２＝μ_ｇ ^ｒ４ｇ^ｄ１を計算する第三入力情報計算部と、
    　第四入力情報ｈ_２＝μ_ｈ ^ｒ５を計算する第四入力情報計算部と、
    　上記計算装置から受信したｚ_２∈Ｆを用いて、ｚ_２ν^{－ｒ４ｒ５}を計算する第二リスト情報計算部と、
    　上記ｄ_１と上記ｒ_５と上記計算されたｚ_２ν^{－ｒ４ｒ５}とから構成される情報の組（ｄ_１，ｒ_５，ｚ_２ν^{－ｒ４ｒ５}）が記憶される第二リスト記憶部と、
    　上記第一リスト記憶部から読み込んだ情報の組の第一成分をｓ_１とし、第二成分をｗ_１とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をｔ_２とし、第二成分をｓ_２とし、第三成分をｗ_２として、これらの情報の組が（ｗ_１）＾（ｔ_２ｓ_２ｓ_１ ^－１）＝ｗ_２の関係を満たすかを判定し、その関係を満たす場合には、ｓ_１をσに代入し、ｗ_１をν’に代入する第一判定部と、
    　０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_６を生成する第六乱数生成部と、
    　０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_７を生成する第七乱数生成部と、
    　第五入力情報ｇ_３＝ｇ^ｒ６を計算する第五入力情報計算部と、
    　第六入力情報ｈ_３＝μ_ｈ ^ｒ７σｈを計算する第六入力情報計算部と、
    　上記計算装置から受信したｚ_３∈Ｆを用いて、ｚ_３ν’^{－ｒ６ｒ７}を計算する第三リスト情報計算部と、
    　上記ｒ_６と上記計算されたｚ_３ν’^{－ｒ６ｒ７}とから構成される情報の組（ｒ_６，ｚ_３ν’^{－ｒ６ｒ７}）が記憶される第三リスト記憶部と、
    　０以上Ｋ未満の整数の一様乱数であるｄ_２を生成する第八乱数生成部と、
    　０以上Ｋ_Ｇ未満の整数の一様乱数であるｒ_９を生成する第九乱数生成部と、
    　０以上Ｋ_Ｈ未満の整数の一様乱数であるｒ_１０を生成する第十乱数生成部と、
    　第七入力情報ｇ_４＝μ_ｇ ^ｒ９を計算する第七入力情報計算部と、
    　第八入力情報ｈ_４＝μ_ｈ ^ｒ１０σｈ^ｄ２を計算する第八入力情報計算部と、
    　上記計算装置から受信したｚ_４∈Ｆを用いて、ｚ_４ν’^{－ｒ９ｒ１０}を計算する第四リスト情報計算部と、
    　上記ｄ_２と上記ｒ_９と上記計算されたｚ_４ν’^{－ｒ９ｒ１０}とから構成される情報の組（ｄ_２，ｒ_９，ｚ_４ν’^{－ｒ９ｒ１０}）が記憶される第四リスト記憶部と、
    　上記第三リスト記憶部から読み込んだ情報の組の第一成分をｓ_３とし、第二成分をｗ_３とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をｔ_４とし、第二成分をｓ_４とし、第三成分をｗ_４として、これらの情報の組が（ｗ_３）＾（ｔ_４ｓ_４ｓ_３ ^－１）＝ｗ_４の関係を満たすかを判定し、その関係を満たす場合には、（ｗ_３）＾（ｓ_３ ^－１）を出力する第二判定部と、
    　を含む依頼装置。
18. 　請求項７又は請求項１７の依頼装置の各部としてコンピュータを機能させるためのプログラム。
19. 　請求項１８の依頼装置プログラムが記録されたコンピュータ読み取り可能な記録媒体。
     

Images