【課題】１回の代理計算でｆ（ｘ_１，ｘ_２）を計算することができる。
【解決手段】Ｈ_１，Ｈ_２及びＧを巡回群、ｈ_１，ｈ_２及びｇをそれぞれＨ_１，Ｈ_２及びＧの生成元、ｆ（ｘ_１，ｘ_２）を群Ｈ_１の元ｘ_１及び群Ｈ_２の元ｘ_２の組を群Ｇへ写す双準同型写像、Ｅ_１及びＥ_２を群Ｇに値を持つ確率変数、ｅ_１及びｅ_２をそれぞれ確率変数Ｅ_１及びＥ_２の実現値、ａを０以上の整数として、元ｘ_１及び元ｘ_２に対応する第一入力情報τ_１を生成する。元ｘ_１及び元ｘ_２に対応する第二入力情報τ_２を生成する。第一入力情報τ_１を用いて、ｆ（ｘ_１，ｘ_２）^ａｅ_１を計算可能であり、その計算結果をｕとする。第二入力情報τ_２を用いて、ｆ（ｘ_１，ｘ_２）ｅ_２を計算可能であり、その計算結果をｖとする。計算結果ｕ及びｖがｕ＝ｖ^ａを満たす場合に、そのｖを出力する。

【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータによる計算技術に関する。特に、他の計算機に行わせた計算結果を用いて計算を行う技術に関する。
【背景技術】
【０００２】
非特許文献１に、関数ｆを群Ｈ_１及び群Ｈ_２の元を群Ｇに写す双準同型写像として、乱数化可能標本器を用いて、２つの入力ｘ_１，ｘ_２に対するｆ（ｘ_１，ｘ_２）を計算する技術が発明者により提案されている。以下、この技術を簡単に説明する。
【０００３】
群Ｈ_１の生成元をｈ_１，群Ｈ_２の生成元をｈ_２とする。この技術では、まず、ｆ（ｘ_１，ｈ_１）についての乱数化可能標本器を用いた第一の代理計算により、ｆ（ｘ_１，ｈ_１）を計算する。次に、ｆ（ｘ_１，ｘ_２）についての乱数化可能標本器及びその計算結果ｆ（ｘ_１，ｈ_１）を用いた第二の代理計算により、ｆ（ｘ_１，ｘ_２）を計算する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】山本剛，小林鉄太郎，「準同型写像に対する自己訂正について」，ＳＣＩＳ ２０１０，ｐ．５−６
【発明の概要】
【発明が解決しようとする課題】
【０００５】
背景技術の欄に記載した技術では、ｆ（ｘ_１，ｘ_２）を計算するために、２回の代理計算を行う必要があった。
【０００６】
この発明は、１回の代理計算でｆ（ｘ_１，ｘ_２）を計算する技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
この発明の１つの観点による代理計算システムでは、Ｈ_１，Ｈ_２及びＧを巡回群、ｈ_１，ｈ_２及びｇをそれぞれＨ_１，Ｈ_２及びＧの生成元、ｆ（ｘ_１，ｘ_２）を群Ｈ_１の元ｘ_１及び群Ｈ_２の元ｘ_２の組を群Ｇへ写す双準同型写像、Ｋ_Ｈ１及びＫ_Ｈ２をそれぞれＨ_１及びＨ_２の位数、ｈ_１及びｈ_２をそれぞれＨ_１及びＨ_２の生成元、Ｅ_１及びＥ_２を群Ｇに値を持つ確率変数、ｅ_１及びｅ_２をそれぞれ確率変数Ｅ_１及びＥ_２の実現値、ａを０以上の整数として、元ｘ_１及び元ｘ_２に対応する第一入力情報τ_１を生成する第一入力情報生成部と、元ｘ_１及び元ｘ_２に対応する第二入力情報τ_２を生成する第二入力情報生成部と、第一入力情報τ_１を用いて、ｆ（ｘ_１，ｘ_２）^ａｅ_１を計算可能であり、その計算結果をｕとする乱数化可能標本器と、第二入力情報τ_２を用いて、ｆ（ｘ_１，ｘ_２）ｅ_２を計算可能であり、その計算結果をｖとする標本器と、計算結果ｕ及びｖがｕ＝ｖ^ａを満たす場合に、そのｖを出力する最終出力部と、を含む。
【発明の効果】
【０００８】
１回の代理計算でｆ（ｘ_１，ｘ_２）を計算することができる。
【図面の簡単な説明】
【０００９】
【図１】代理計算システムの構成を説明するためのブロック図。
【図２】依頼装置及び計算装置の構成を説明するためのブロック図。
【図３】第一入力情報生成部の構成を説明するためのブロック図。
【図４】第二入力情報生成部の構成を説明するためのブロック図。
【図５】代理計算方法の処理を説明するためのフローチャート。
【図６】ステップＳ１の処理を説明するためのフローチャート。
【図７】ステップＳ２の処理を説明するためのフローチャート。
【図８】ステップＳ３の処理を説明するためのフローチャート。
【図９】ステップＳ４の処理を説明するためのフローチャート。
【図１０】乱数化可能標本器の変形例の構成を説明するためのブロック図。
【図１１】第一入力情報生成部の変形例の構成を説明するためのブロック図。
【図１２】ステップＳ１の変形例の構成を説明するためのフローチャート。
【図１３】ステップＳ２の変形例の構成を説明するためのフローチャート。
【発明を実施するための形態】
【００１０】
以下、図面を参照してこの発明の一実施形態を説明する。
【００１１】
代理計算システムは、図１に示すように、依頼装置１及び計算装置２を例えば含む。
【００１２】
依頼装置１は、図２に示すように、第一入力情報生成部１１、第二入力情報生成部１２、制御部１３、第一記憶部１４、第一計算部１５、第二計算部１６、判定部１７、第二記憶部１８、最終出力部１９を例えば含む。
【００１３】
計算装置２は、図２に示すように、第一出力情報生成部２１、第二出力情報生成部２２、第三出力情報生成部２３を例えば含む。
【００１４】
まず、記号の定義を行う。Ｈ_１，Ｈ_２及びＧを巡回群、ｈ_１，ｈ_２及びｇをそれぞれＨ_１，Ｈ_２及びＧの生成元、ｆ（ｘ_１，ｘ_２）を群Ｈ_１の元ｘ_１及び群Ｈ_２の元ｘ_２の組を群Ｇへ写す双準同型写像、Ｋ_Ｈ１及びＫ_Ｈ２をそれぞれＨ_１及びＨ_２の位数、ｈ_１，ｈ_２及びｇをそれぞれＨ_１，Ｈ_２及びＧの生成元、Ｅ_１及びＥ_２を群Ｇに値を持つ確率変数、ｅ_１及びｅ_２をそれぞれ確率変数Ｅ_１及びＥ_２の実現値、ａを０以上の整数とする。ａは、例えば０以上の整数からランダムに選ばれた数である。ここで、確率変数Ｅ_１の分布は、ａに依存しないとする。
【００１５】
双準同型写像とは、２つの入力のそれぞれに対して準同型である写像を意味する。この例では、写像ｆ（ｘ_１，ｘ_２）は、群Ｈ_１の元ｘ_１に対して準同型であり、かつ、群Ｈ_２の元ｘ_２に対して準同型である。
【００１６】
依頼装置１及び計算装置２は協同して、ある入力（ｘ_１，ｘ_２）に対応するｆ（ｘ_１，ｘ_２）の値を計算するか、計算をすることができなかった旨の情報を出力する。
【００１７】
制御部１３は、ｔを１とする（ステップＳ０、図５）。
【００１８】
第一入力情報生成部１１は、元ｘ_１及び元ｘ_２に対応する第一入力情報τ_１を生成する（ステップＳ１）。生成された第一入力情報τ_１は、計算装置２に送信される。この例では、第一入力情報τ_１は、図６に例示するステップＳ１１からステップＳ１６により生成されるｘ_１^ｒ１、ｘ_２^ａｈ_２^ｒ２ｒ４、ｘ_１^−ｒ２ｈ_１^ｒ３及びｈ_２^ｒ４である。
【００１９】
第一乱数生成部１１１は、０以上Ｋ_Ｈ１未満の一様乱数ｒ_１，ｒ_３を生成する（ステップＳ１１）。生成された乱数ｒ_１は第一入力計算部１１３に送信され、生成された乱数ｒ_３は第三入力計算部１１５に送信される。
【００２０】
第二乱数生成部１１２は、０以上Ｋ_Ｈ２未満の一様乱数ｒ_２，ｒ_４を生成する（ステップＳ１２）。生成された乱数ｒ_２は第二入力計算部１１４及び第三入力計算部１１５に送信され、生成された乱数ｒ_４は第二入力計算部１１４及び第四入力計算部１１６に送信される。
【００２１】
第一入力計算部１１３は、生成された乱数ｒ_１及び元ｘ_１を用いて、ｘ_１^ｒ１を計算する（ステップＳ１３）。ｘ_１の右肩のｒ１は、ｒ_１のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、α^βγと表記した場合には、そのβγはβ_γ、すなわちβの下付きγを意味する。
【００２２】
第二入力計算部１１４は、生成された乱数ｒ_２，ｒ_４、元ｘ_２及び生成元ｈ_２を用いて、ｘ_２^ａｈ_２^ｒ２ｒ４を計算する（ステップＳ１４）。
【００２３】
第三入力計算部１１５は、生成された乱数ｒ_２，ｒ_３、元ｘ_１及び生成元ｈ_１を用いて、ｘ_１^−ｒ２ｈ_１^ｒ３を計算する（ステップＳ１５）。
【００２４】
第四入力計算部１１６は、生成された乱数ｒ_４及び生成元ｈ_２を用いて、ｈ_２^ｒ４を計算する（ステップＳ１６）。
【００２５】
このように、乱数ｒ_１，ｒ_２，ｒ_３及びｒ_４を用いて入力ｘ_１及びｘ_２を撹乱した情報を第一入力情報τ_１として計算装置２に送信することにより、入力ｘ_１及びｘ_２を計算装置２及び依頼装置１以外の装置に対して秘密にすることができる。
【００２６】
乱数化可能標本器３は、第一入力情報τ_１を用いて、ｆ（ｘ_１，ｘ_２）^ａｅ_１を計算可能であり、その計算結果をｕとする（ステップＳ２）。計算結果ｕは、第一記憶部１４に記憶される。この例では、図７に例示するステップＳ２１からステップＳ２３により計算結果ｕが生成される。
【００２７】
第一出力情報生成部２１は、第一入力情報τ_１のｘ_１^ｒ１及びｘ_２^ａｈ_２^ｒ２ｒ４を用いて、ある確率より大きな確率でｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）を正しく計算し、得られた計算結果を第一出力情報ｚ_１とする（ステップＳ２１）。第一出力情報ｚ_１は、依頼装置１に送信される。
【００２８】
群Ｈ_１の元ｙ_１，群Ｈ_２の元ｙ_２を入力したときにある確率δより大きな確率でｆ（ｙ_１，ｙ_２）を正しく計算する関数をブラックボックス関数Ｆとする。第一出力情報生成部２１は、例えばブラックボックス関数Ｆにｘ_１^ｒ１及びｘ_２^ａｈ_２^ｒ２ｒ４を入力することにより得た出力値Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）を第一出力情報ｚ_１とする。すなわち、第一出力情報ｚ_１＝Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）とする。
【００２９】
第二出力情報生成部２２は、第一入力情報τ_１のｘ_１^−ｒ２ｈ_１^ｒ３及びｈ_２^ｒ４を用いて、ある確率より大きな確率でｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）を正しく計算し、得られた計算結果を第二出力情報ｚ_２とする（ステップＳ２２）。第二出力情報ｚ_２は、依頼装置１に送信される。第二出力情報生成部２２は、例えばブラックボックス関数Ｆにｘ_１^−ｒ２ｈ_１^ｒ３及びｈ_２^ｒ４を入力することにより得た出力値Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）を第二出力情報ｚ_２とする。すなわち、第二出力情報ｚ_２＝Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）とする。
【００３０】
「ある確率」は１００％未満の確率である。「ある確率」の例は無視することができない確率であり、「無視することができない確率」の例は、セキュリティパラメータｋについての広義単調増加関数である多項式を多項式ψ（ｋ）とした場合の１／ψ（ｋ）以上の確率である。すなわち、第一出力情報生成部２１や第二出力情報生成部２２は、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報生成部２１での計算結果がｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）の場合もあればｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）でない場合もあり、第二出力情報生成部２２での計算結果がｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）の場合もあればｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）でない場合もある。
【００３１】
第一計算部１５は、第一出力情報ｚ_１及び第二出力情報ｚ_２を用いて、ｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}を計算してその計算結果を上記ｕとする（ステップＳ２３）。
【００３２】
第二入力情報生成部１２は、元ｘ_１及び元ｘ_２に対応する第二入力情報τ_２を生成する（ステップＳ３）。生成された第二入力情報τ_２は、計算装置２に送信される。この例では、第二入力情報τ_２は、図８に例示するステップＳ３１からステップＳ３４により生成されるｘ_１^ｒ５、ｘ_２^ｒ６である。
【００３３】
第三乱数生成部１２１は、０以上Ｋ_Ｈ１未満の一様乱数ｒ_５を生成する（ステップＳ３１）生成された乱数ｒ_５は、第五入力計算部１２３に送信される
第四乱数生成部１２２は、０以上Ｋ_Ｈ２未満の乱数ｒ_６を生成する（ステップＳ３２）。生成された乱数ｒ_６は、第六入力計算部１２４に送信される。
【００３４】
第五入力計算部１２３は、元ｘ_１及び乱数ｒ_５を用いて、ｘ_１^ｒ５を計算する（ステップＳ３３）。
【００３５】
第六入力計算部１２４は、元ｘ_２及び乱数ｒ_６を用いて、ｘ_２^ｒ６を計算する（ステップＳ３４）。
【００３６】
このように、乱数ｒ_５及びｒ_６を用いて、入力ｘ_１及びｘ_２を撹乱した情報を第二入力情報τ_２として計算装置２に送信することにより、入力ｘ_１及びｘ_２を計算装置２及び依頼装置１以外の装置に対して秘密にすることができる。
【００３７】
標本器４は、第二入力情報τ_２を用いて、ｆ（ｘ_１，ｘ_２）ｅ_２を計算可能であり、その計算結果をｖとする（ステップＳ４）。計算結果ｖは、第二記憶部１８に記憶される。
【００３８】
この例では、図９に例示するステップＳ４１及びステップＳ４２において、計算装置２に設けられた第三出力情報生成部２３と、依頼装置１に設けられた第二計算部１６とが計算結果ｖを生成する。
【００３９】
第三出力情報生成部２３は、第二入力情報τ_２を用いて、ある確率より大きな確率でｆ（ｘ_１^ｒ５，ｘ_２^ｒ６）を正しく計算し、得られた計算結果を第三出力情報ｚ_３とする（ステップＳ４１）。第三出力情報ｚ_３は、依頼装置１に送信される。例えば、ブラックボックス関数Ｆにｘ_１^ｒ５及びｘ_２^ｒ６を入力することにより得た出力値Ｆ（ｘ_１^ｒ５，ｘ_２^ｒ６）を第三出力情報ｚ_３とする。すなわち、第三出力情報ｚ_３＝Ｆ（ｘ_１^ｒ５，ｘ_２^ｒ６）である。
【００４０】
第二計算部１６は、第三出力情報ｚ_３及び乱数ｒ_５及びｒ_６を用いて、ｚ_３^{１／ｒ５ｒ６}を計算してその計算結果をｖとする（ステップＳ４２）。なお、ｚ_３^{１／ｒ５ｒ６}は、ｚ_３^{１／（ｒ５ｒ６）}である。
【００４１】
判定部１７は、第一記憶部１４に記憶された計算結果ｕ及び第二記憶部１８に記憶された計算結果ｖの中で、ｕ＝ｖ^ａとなるものがあるか判定する（ステップＳ５）。第一記憶部１４に記憶された複数の計算結果ｕから選択された１つの計算結果ｕと、第二記憶部１８から選択された１つの計算結果ｖとから構成される計算結果の組は、第一記憶部１４に記憶された計算結果ｕの数Ｕ個と第二記憶部１８に記憶された計算結果ｖの数Ｖ個とを乗算した数Ｕ×Ｖ個存在する。判定部１７は、Ｕ×Ｖ個の計算結果の組のそれぞれについて、その計算結果の組を構成する計算結果ｕと計算結果ｖとが、ｕ＝ｖ^ａという関係を満たすか判定する。
【００４２】
なお、判定部１７は、前回のステップＳ５において判定を行った計算結果の組については、その判定を省略してもよい。換言すれば、判定部１７は、例えば新たに追加された計算結果ｕ又は計算結果ｖから少なくとも一方が構成される計算結果の組についてのみ判定を行ってもよい。既に判定を行った計算結果の組についての判定を省略することにより、処理を高速に行うことができ、必要なハードウェア資源の量を小さくすることができる。
【００４３】
最終出力部１９は、判定部１７においてｕ＝ｖ^ａとなるものがあると判定された場合には、このｕ＝ｖ^ａという関係を満たすｖを出力する（ステップＳ６）。このｕ＝ｖ^ａという関係を満たすｖが、高い確率でｆ（ｘ_１，ｘ_２）の値と一致する。その理由については、後述する。
【００４４】
制御部１３は、ｔ＝Ｔであるか判定する（ステップＳ７）。Ｔは予め定められた正の整数である。ｔ＝Ｔであれば、制御部１３は、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ８）、処理を終える。ｔ＝Ｔでない場合には、制御部１３は、ｔを１だけインクリメント、すなわちｔにｔ＋１を代入して（ステップＳ９）、ステップＳ１に戻る。
【００４５】
≪高い確率でｕ＝ｖ^ａという関係を満たすｖがｆ（ｘ_１，ｘ_２）となる理由について≫
Ｘを群Ｇに値を持つ確率変数とする。ｗ∈Ｇについて、要求を受けるたびに確率変数Ｘに従った標本ｘ’に対応するｗｘ’を返すものを、ｗについて誤差Ｘを持つ標本器（ｓａｍｐｌｅｒ）と呼ぶ。
【００４６】
与えられた自然数ａに確率変数Ｘの分布が依存せず、ｗ∈Ｇについて、要求を受けるたびに確率変数Ｘに従った標本ｘ’に対応するｗ^ａｘ’を返すものを、ｗについて誤差Ｘを持つ乱数化可能標本器（ｒａｎｄｏｍｉｚａｂｌｅ ｓａｍｐｌｅｒ）と呼ぶ。乱数化可能標本器はａ＝１として用いられれば標本器として機能する。
【００４７】
上記の実施形態においては、乱数化可能標本器３がｆ（ｘ_１，ｘ_２）についての誤差Ｅ_１を持つ乱数化可能標本器であり、標本器４がｆ（ｘ_１，ｘ_２）についての誤差Ｅ_２を持つ標本器である。
【００４８】
乱数化可能標本器３により計算されるｕ＝ｆ（ｘ_１，ｘ_２）^ａｅ_１、及び、標本器４により計算されるｖ＝ｆ（ｘ_１，ｘ_２）ｅ_２が、ｕ＝ｖ^ａという関係を満たす場合、ｅ_１及びｅ_２が群Ｇの単位元ｅ_ｇである可能性が非常に高いことを発明者は見出した。ここでは、その証明を省略する。ｅ_２が群Ｇの単位元ｅ_ｇであるとき、ｖ＝ｆ（ｘ_１，ｘ_２）ｅ_２＝ｆ（ｘ_１，ｘ_２）ｅ_ｇ＝ｆ（ｘ_１，ｘ_２）となる。
【００４９】
入力ｘ_１，ｘ_２に対してブラックボックス関数Ｆを用いて計算を行う、ｗ＝ｆ（ｘ_１，ｘ_２）についての標本器をΣ’^Ｆ（ｘ_１，ｘ_２）と表記する。また、入力ｘ_１，ｘ_２及び与えられた自然数ａに対してブラックボックス関数Ｆを用いて計算を行う、ｗ＝ｆ（ｘ_１，ｘ_２）についての乱数化可能標本器をΣ^Ｆ（ｘ_１，ｘ_２，ａ）と表記する。
【００５０】
確率変数Ｅ_１＝Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^{−１／ｒ１}Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）^−１とすると、第一計算部１５により計算されるｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}は、ｆ（ｘ_１，ｘ_２）についての誤差Ｅ_１を持つ乱数化可能標本器Σ^Ｆ（ｘ_１，ｘ_２，ａ）となる。すなわち、Σ^Ｆ（ｘ_１，ｘ_２，ａ）＝ｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}＝ｆ（ｘ_１，ｘ_２）^ａＥ_１となる。換言すれば、Ｅ_１＝ｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}ｆ（ｘ_１，ｘ_２）^−ａとなる。
【００５１】
定義より、ｚ_１＝Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）、ｚ_２＝Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）であり、これらをＥ_１＝ｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}ｆ（ｘ_１，ｘ_２）^−ａに代入すると以下のように式展開でき、Ｅ_１＝Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^{−１／ｒ１}Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）^−１であることがわかる。また、関数ｆ及びブラックボックス関数Ｆの入力の１つであるｘ_２^ａｈ_２^ｒ２ｒ４は乱数ｒ_２及びｒ_４により撹乱されておりａに依存しない。このため、確率変数Ｅ_１もａに依存しない。
【００５２】
Ｅ_１＝ｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}ｆ（ｘ_１，ｘ_２）^−ａ
＝Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）ｆ（ｘ_１，ｘ_２）^−ａｙ^{−ｒ３ｒ４}
＝Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）ｆ（ｘ_１，ｘ_２）^−ａｙ^{−ｒ３ｒ４}ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^{−１／ｒ１}ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）^−１ …（１）
Ａ＝ｆ（ｘ_１，ｘ_２）^−ａｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４），Ｂ＝Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^{−１／ｒ１}，Ｃ＝Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）^−１とすると、上記（１）式＝ＡＢＣｙ^{−ｒ３ｒ４}と書ける。
【００５３】
ここで、関数ｆの準同型性により、Ａ＝ｆ（ｘ_１，ｘ_２）^−ａｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）＝ｆ（ｘ_１，ｘ_２）^−ａｆ（ｘ_１，ｘ_２）^ａｆ（ｘ_１，ｈ_２）^ｒ２ｒ４ｆ（ｘ_１，ｈ_２）^{−ｒ２ｒ４}ｆ（ｈ_１，ｈ_２）^ｒ３ｒ４＝ｙ^ｒ３ｒ４である。
【００５４】
このため、上記（１）式＝ＡＢＣｙ^{−ｒ３ｒ４}＝ｙ^ｒ３ｒ４ＢＣｙ^{−ｒ３ｒ４}＝ＢＣである。よって、Ｅ_１＝ｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}ｆ（ｘ_１，ｘ_２）^−ａ＝ＢＣ＝Ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^１／ｒ１ｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）^{−１／ｒ１}Ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）ｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）^−１となるのである。換言すれば、ｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}＝ｆ（ｘ_１，ｘ_２）^ａＥ_１である。
【００５５】
また、確率変数Ｅ_２＝Ｆ（ｘ_１^ｒ５，ｘ_２^ｒ６）^{１／ｒ５ｒ６}ｆ（ｘ_１，ｘ_２）^−１とすると、第二計算部１６により計算されるｚ_３^{１／ｒ５ｒ６}は、ｆ（ｘ_１，ｘ_２）についての誤差Ｅ_２を持つ標本器Σ’^Ｆ（ｘ_１，ｘ_２）となる。すなわち、Σ’^Ｆ（ｘ_１，ｘ_２）＝ｚ_３^{１／ｒ５ｒ６}＝ｆ（ｘ_１，ｘ_２）Ｅ_２となる。
【００５６】
［変形例等］
図１０に例示するように、乱数化可能標本器３を構成してもよい。図１０の乱数化可能標本器３は、第一計算部１５、第一出力情報生成部２１、第二出力情報生成部２２、第四出力情報生成部２４を備える。第一計算部１５は、依頼装置１に設けられ、３つの出力情報ｚ_１，ｚ_２，ｚ_４からｕを計算する。第一出力情報生成部２１、第二出力情報生成部２２、第四出力情報生成部２４は、計算装置２に設けられる。
【００５７】
この場合の第一入力情報生成部１１は、図１１に示すように、乱数生成部１１９、第一入力計算部１１３、第二入力計算部１１４、第三入力計算部１１５、第四入力計算部１１６、第五入力計算部１１７、第六入力計算部１１８を例えば備える。
【００５８】
乱数生成部１１９は、乱数ｓ_１，ｓ_２，ｓ_３，ｓ_４，ｓ_５，ｓ_６を生成する（ステップＳ１１、図１２）。乱数ｓ_１，ｓ_２，ｓ_３，ｓ_４，ｓ_５，ｓ_６は、例えば０以上所定の数以下の一様乱数である。ここで、所定の数は、例えばｎ（ｋ）を群Ｈ_１又は群Ｈ_２を表現するビット長として、２^{ｎ（ｋ）＋ｋ}である。乱数ｓ_１，ｓ_２は、第一入力計算部１１３に送信される。乱数ｓ_３，ｓ_４は、第二入力計算部１１４に送信される。乱数ｓ_１は、第三入力計算部１１５に送信される。乱数ｓ_２，ｓ_５は、第四入力計算部１１６に送信される。乱数ｓ_４，ｓ_６は、第五入力計算部１１７に送信される。乱数ｓ_３は、第六入力計算部１１８に送信される。
【００５９】
第一入力計算部１１３は、ｘ_１ｈ_１^ｓ１ｓ２を計算する（ステップＳ１３）。
【００６０】
第二入力計算部１１４は、ｘ_２^ａｈ_２^ｓ３ｓ４を計算する（ステップＳ１４）。
【００６１】
第三入力計算部１１５は、ｈ_１^ｓ１を計算する（ステップＳ１５）。
【００６２】
第四入力計算部１１６は、ｘ_２^−ａｓ２ｈ_２^ｓ５を計算する（ステップＳ１６）。
【００６３】
第五入力計算部１１７は、ｘ_１^−ｓ４ｈ_１^ｓ６を計算する（ステップＳ１７）。
【００６４】
第六入力計算部１１８は、ｈ_２^ｓ３を計算する（ステップＳ１８）。
【００６５】
この変形例では、これらの計算されたｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４，ｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５，ｘ_１^−ｓ４ｈ_１^ｓ６，ｈ_２^ｓ３が、第一入力情報τ_１となる。第一入力情報τ_１は、計算装置２に送信される。
【００６６】
第一出力情報生成部２１は、第一入力情報τ_１のｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４を用いて、ある確率より大きな確率でｆ（ｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４）を正しく計算し、得られた計算結果を第一出力情報ｚ_１とする（ステップＳ２１、図１３）。第一出力情報ｚ_１は、依頼装置１に送信される。第一出力情報生成部２１は、例えばブラックボックス関数Ｆにｘ_１ｈ_１^ｓ１ｓ２及びｘ_２^ａｈ_２^ｓ３ｓ４を入力することにより得た出力値Ｆ（ｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４）を第一出力情報ｚ_１とする。すなわち、第一出力情報ｚ_１＝Ｆ（ｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４）とする。
【００６７】
第二出力情報生成部２２は、第一入力情報τ_１のｈ_１^ｓ１及びｘ_２^−ａｓ２ｈ_２^ｓ５を用いて、ある確率より大きな確率でｆ（ｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５）を正しく計算し、得られた計算結果を第二出力情報ｚ_２とする（ステップＳ２２）。第二出力情報ｚ_２は、依頼装置１に送信される。第二出力情報生成部２２は、例えばブラックボックス関数Ｆにｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５を入力することにより得た出力値Ｆ（ｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５）を第二出力情報ｚ_２とする。すなわち、第二出力情報ｚ_２＝Ｆ（ｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５）とする。
【００６８】
第四出力情報生成部２４は、第一入力情報τ_１のｘ_１^−ｓ４ｈ_１^ｓ６及びｈ_２^ｓ３を用いて、ある確率より大きな確率でｆ（ｘ_１^−ｓ４ｈ_１^ｓ６，ｈ_２^ｓ３）を正しく計算し、得られた計算結果を第四出力情報ｚ_４とする（ステップＳ２４）。第四出力情報ｚ_４は、依頼装置１に送信される。第四出力情報生成部２４は、例えばブラックボックス関数Ｆにｘ_１^−ｓ４ｈ_１^ｓ６，ｈ_２^ｓ３を入力することにより得た出力値Ｆ（ｘ_１^−ｓ４ｈ_１^ｓ６，ｈ_２^ｓ３）を第四出力情報ｚ_４とする。すなわち、第四出力情報ｚ_４＝Ｆ（ｘ_１^−ｓ４ｈ_１^ｓ６，ｈ_２^ｓ３）とする。
【００６９】
第一計算部１５は、第一出力情報ｚ_１、第二出力情報ｚ_２及び第四出力情報ｚ_４を用いて、ｚ_１ｚ_２ｚ_４ｙ^{−ｓ１ｓ２ｓ３ｓ４−ｓ１ｓ５−ｓ３ｓ６}を計算してその計算結果をｕとする（ステップＳ２３）。その他の処理は、上記実施形態と同じである。
【００７０】
このように、ｕを計算することにより、上記実施形態の第一計算部１５が行っていた逆元の計算が不必要となり、演算をより効率的に行うことができる。このばあい、Ｅ_１＝Ｆ（ｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４）ｆ（ｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４）^−１Ｆ（ｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５）ｆ（ｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５）^−１Ｆ（ｘ_１^−ｓ４ｈ_１^ｓ６，ｈ_２^ｓ３）ｆ（ｘ_１^−ｓ４ｈ_１^ｓ６，ｈ_２^ｓ３）^−１である。ｓ_１，ｓ_２，ｓ_３，ｓ_４，ｓ_５，ｓ_６は乱数であるから、Ｅ_１はａに依存しない確率変数である。
【００７１】
確率変数Ｅ_１，Ｅ_２は、同じでも異なっていてもよい。したがって、標本器４は、乱数化可能標本器３またはその変形例に示した乱数化可能標本器で、ａを１で置き換えたもので代替することができる。
第一乱数生成部１１１、第二乱数生成部１１２、第三乱数生成部１２１、第四乱数生成部１２２、乱数生成部１１９は、一様乱数を生成することにより、代理計算システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部１１１、第二乱数生成部１１２、第三乱数生成部１２１、第四乱数生成部１２２、乱数生成部１１９は、一様乱数ではない乱数を生成してもよい。
【００７２】
また、第一乱数生成部１１１、第二乱数生成部１１２、第三乱数生成部１２１、第四乱数生成部１２２は、０以上所定の数以下の乱数を生成してもよい。ここで、例えばｎ（ｋ）を群Ｈ_１又は群Ｈ_２を表現するビット長として、所定の数は２^{ｎ（ｋ）＋ｋ}である。
【００７３】
また、依頼装置１が複数の第一入力情報及び第二入力情報を計算装置２にまとめて提供し、対応する計算結果を複数個まとめて取得してもよい。これにより、依頼装置１と計算装置２との間のやり取り回数を減らすことができる。
【００７４】
上記の実施形態では、例えばｘ_１^ｒ１、ｘ_２^ａｈ_２^ｒ２ｒ４、ｘ_１^−ｒ２ｈ_１^ｒ３及びｈ_２^ｒ４を第一入力情報τ_１としたが、第一入力情報τ_１は乱数化可能標本器３がその第一入力情報τ_１に基づいてｆ（ｘ_１，ｘ_２）^ａｅ_１を計算可能することができればどのような情報でもよい。例えば、ｘ_１及びｘ_２自体や、ｘ_１及びｘ_２に関する情報や、（ｘ_１，ｘ_２，ｒ_１，ｒ_２，ｒ_３，ｒ_４）の組を第一入力情報τ_１としてもよい。
【００７５】
同様に、上記の実施形態では、ｘ_１^ｒ５及びｘ_２^ｒ６を上記第二入力情報τ_２としたが、第二入力情報τ_２は乱数化可能標本器３がその第二入力情報τ_２に基づいてｆ（ｘ_１，ｘ_２）ｅ_２を計算可能することができればどのような情報でもよい。例えば、ｘ_１及びｘ_２自体や、ｘ_１及びｘ_２に関する情報や、（ｘ_１，ｘ_２，ｒ_５，ｒ_６）の組を第二入力情報τ_２としてもよい。
【００７６】
乱数化可能標本器３を構成する第一計算部１５、第一出力情報生成部２１及び第二出力情報生成部２２の少なくとも１つの部が計算装置２に備えられていれば、乱数化可能標本器３を構成する他の部は依頼装置１及び計算装置２の何れに備えられていてもよい。例えば、第一計算部１５、第一出力情報生成部２１及び第二出力情報生成部２２のすべてが計算装置２に備えられていてもよい。
【００７７】
同様に、標本器４を構成する第二計算部１６及び第三出力情報生成部２３の少なくとも１つの部が計算装置２に備えられていれば、標本器４を構成する他の部は依頼装置１及び計算装置２の何れに備えられていてもよい。例えば、第二計算部１６及び第三出力情報生成部２３のすべてが計算装置２に備えられていてもよい。
【００７８】
依頼装置１及び計算装置２の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【００７９】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。例えば、図５に破線で示すように、ステップＳ２とステップＳ３の間に、ステップＳ５の処理を行ってもよい。
【００８０】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００８１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８２】
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００８３】
１ 依頼装置
１１ 第一入力情報生成部
１１１ 第一乱数生成部
１１２ 第二乱数生成部
１１３ 第一入力計算部
１１４ 第二入力計算部
１１５ 第三入力計算部
１１６ 第四入力計算部
１１７ 第五入力計算部
１１８ 第六入力計算部
１１９ 乱数生成部１１９
１２ 第二入力情報生成部
１２１ 第三乱数生成部
１２２ 第四乱数生成部
１２３ 第五入力計算部
１２４ 第六入力計算部
１３ 制御部
１４ 第一記憶部
１５ 第一計算部
１６ 第二計算部
１７ 判定部
１８ 第二記憶部
１９ 最終出力部
２ 計算装置
２１ 第一出力情報生成部
２２ 第二出力情報生成部
２３ 第三出力情報生成部
２４ 第四出力情報生成部
３ 乱数化可能標本器
４ 標本器

【特許請求の範囲】
【請求項１】
Ｈ_１，Ｈ_２及びＧを巡回群、ｈ_１，ｈ_２及びｇをそれぞれＨ_１，Ｈ_２及びＧの生成元、ｆ（ｘ_１，ｘ_２）を群Ｈ_１の元ｘ_１及び群Ｈ_２の元ｘ_２の組を群Ｇへ写す双準同型写像、Ｅ_１及びＥ_２を群Ｇに値を持つ確率変数、ｅ_１及びｅ_２をそれぞれ確率変数Ｅ_１及びＥ_２の実現値、ａを０以上の整数として、
上記元ｘ_１及び元ｘ_２に対応する第一入力情報τ_１を生成する第一入力情報生成部と、
上記元ｘ_１及び元ｘ_２に対応する第二入力情報τ_２を生成する第二入力情報生成部と、
上記第一入力情報τ_１を用いて、ｆ（ｘ_１，ｘ_２）^ａｅ_１を計算可能であり、その計算結果をｕとする乱数化可能標本器と、
上記第二入力情報τ_２を用いて、ｆ（ｘ_１，ｘ_２）ｅ_２を計算可能であり、その計算結果をｖとする標本器と、
上記計算結果ｕ及びｖがｕ＝ｖ^ａを満たす場合に、そのｖを出力する最終出力部と、
を含む代理計算システム。
【請求項２】
請求項１の代理計算システムにおいて、
ｈ_１及びｈ_２をそれぞれＨ_１及びＨ_２の生成元として、
上記第一入力情報生成部は、０以上所定の数以下の乱数ｒ_１，ｒ_３を生成する第一乱数生成部と、０以上所定の数以下の乱数ｒ_２，ｒ_４を生成する第二乱数生成部と、ｘ_１^ｒ１を計算する第一入力計算部と、ｘ_２^ａｈ_２^ｒ２ｒ４を計算する第二入力計算部と、ｘ_１^−ｒ２ｈ_１^ｒ３を計算する第三入力計算部と、ｈ_２^ｒ４を計算する第四入力計算部と、を含み、これらの計算されたｘ_１^ｒ１、ｘ_２^ａｈ_２^ｒ２ｒ４、ｘ_１^−ｒ２ｈ_１^ｒ３及びｈ_２^ｒ４を上記第一入力情報τ_１とし、
ｙ＝ｆ（ｈ_１，ｈ_２）として、上記乱数化可能標本器は、上記第一入力情報τ_１のｘ_１^ｒ１及びｘ_２^ａｈ_２^ｒ２ｒ４を用いて、ある確率より大きな確率でｆ（ｘ_１^ｒ１，ｘ_２^ａｈ_２^ｒ２ｒ４）を正しく計算し、得られた計算結果を第一出力情報ｚ_１とする第一出力情報生成部と、上記第一入力情報τ_１のｘ_１^−ｒ２ｈ_１^ｒ３、ｈ_２^ｒ４を用いて、ある確率より大きな確率でｆ（ｘ_１^−ｒ２ｈ_１^ｒ３，ｈ_２^ｒ４）を正しく計算し、得られた計算結果を第二出力情報ｚ_２とする第二出力情報生成部と、ｚ_１^１／ｒ１ｚ_２ｙ^{−ｒ３ｒ４}を計算してその計算結果を上記ｕとする第一計算部と、を含み、
上記第二入力情報生成部は、０以上所定の数以下の乱数ｒ_５を生成する第三乱数生成部と、０以上所定の数以下の乱数ｒ_６を生成する第四乱数生成部と、ｘ_１^ｒ５を計算する第五入力計算部と、ｘ_２^ｒ６を計算する第六入力計算部と、を含み、これらの計算されたｘ_１^ｒ５、ｘ_２^ｒ６を上記第二入力情報τ_２とし、
上記標本器は、上記第二入力情報τ_２を用いて、ある確率より大きな確率でｆ（ｘ_１^ｒ５，ｘ_２^ｒ６）を正しく計算し、得られた計算結果を第三出力情報ｚ_３とする第三出力情報生成部と、ｚ_３^{１／ｒ５ｒ６}を計算してその計算結果を上記ｖとする第二計算部と、を含む、
代理計算システム。
【請求項３】
Ｈ_１，Ｈ_２及びＧを巡回群、ｈ_１，ｈ_２及びｇをそれぞれＨ_１，Ｈ_２及びＧの生成元、ｆ（ｘ_１，ｘ_２）を群Ｈ_１の元ｘ_１及び群Ｈ_２の元ｘ_２の組を群Ｇへ写す双準同型写像、Ｅ_１及びＥ_２を群Ｇに値を持つ確率変数、ｅ_１及びｅ_２をそれぞれ確率変数Ｅ_１及びＥ_２の実現値、ａを０以上の整数として、
上記元ｘ_１及び元ｘ_２に対応する第一入力情報τ_１を生成する第一入力情報生成部と、
上記元ｘ_１及び元ｘ_２に対応する第二入力情報τ_２を生成する第二入力情報生成部と、
上記第一入力情報τ_１を用いてｆ（ｘ_１，ｘ_２）^ａｅ_１を計算可能な乱数化可能標本器による計算結果ｕと、上記第二入力情報τ_２を用いてｆ（ｘ_１，ｘ_２）ｅ_２を計算可能な標本器による計算結果ｖとが、ｕ＝ｖ^ａを満たす場合に、そのｖを出力する最終出力部と、
を含む依頼装置。
【請求項４】
Ｈ_１，Ｈ_２及びＧを巡回群、ｈ_１，ｈ_２及びｇをそれぞれＨ_１，Ｈ_２及びＧの生成元、ｆ（ｘ_１，ｘ_２）を群Ｈ_１の元ｘ_１及び群Ｈ_２の元ｘ_２の組を群Ｇへ写す双準同型写像、Ｅ_１及びＥ_２を群Ｇに値を持つ確率変数、ｅ_１及びｅ_２をそれぞれ確率変数Ｅ_１及びＥ_２の実現値、ａを０以上の整数として、
上記元ｘ_１及び元ｘ_２に対応する第一入力情報τ_１を用いて、ｆ（ｘ_１，ｘ_２）^ａｅ_１を計算可能であり、その計算結果をｕとする乱数化可能標本器と、
上記元ｘ_１及び元ｘ_２に対応する第二入力情報τ_２を用いて、ｆ（ｘ_１，ｘ_２）ｅ_２を計算可能であり、その計算結果をｖとする標本器と、
を含む計算装置。
【請求項５】
Ｈ_１，Ｈ_２及びＧを巡回群、ｈ_１，ｈ_２及びｇをそれぞれＨ_１，Ｈ_２及びＧの生成元、ｆ（ｘ_１，ｘ_２）を群Ｈ_１の元ｘ_１及び群Ｈ_２の元ｘ_２の組を群Ｇへ写す双準同型写像、Ｅ_１及びＥ_２を群Ｇに値を持つ確率変数、ｅ_１及びｅ_２をそれぞれ確率変数Ｅ_１及びＥ_２の実現値、ａを０以上の整数として、
第一入力情報生成部が、上記元ｘ_１及び元ｘ_２に対応する第一入力情報τ_１を生成する第一入力情報生成ステップと、
第二入力情報生成部が、上記元ｘ_１及び元ｘ_２に対応する第二入力情報τ_２を生成する第二入力情報生成ステップと、
乱数化可能標本器が、上記第一入力情報τ_１を用いて、ｆ（ｘ_１，ｘ_２）^ａｅ_１を計算可能であり、その計算結果をｕとするステップと、
標本器が、上記第二入力情報τ_２を用いて、ｆ（ｘ_１，ｘ_２）ｅ_２を計算可能であり、その計算結果をｖとするステップと、
最終出力部が、上記計算結果ｕ及びｖがｕ＝ｖ^ａを満たす場合に、そのｖを出力する最終出力ステップと、
を含む代理計算方法。
【請求項６】
請求項１の代理計算システムにおいて、
ｈ_１及びｈ_２をそれぞれＨ_１及びＨ_２の生成元として、
上記第一入力情報生成部は、０以上所定の数以下の乱数ｓ_１，ｓ_２，ｓ_３，ｓ_４，ｓ_５，ｓ_６を生成する乱数生成部と、ｘ_１ｈ_１^ｓ１ｓ２を計算する第一入力計算部と、ｘ_２^ａｈ_２^ｓ３ｓ４を計算する第二入力計算部と、ｈ_１^ｓ１を計算する第三入力計算部と、ｘ_２^−ａｓ２ｈ_２^ｓ５を計算する第四入力計算部と、ｘ_１^−ｓ４ｈ_１^ｓ６を計算する第五入力計算部と、ｈ_２^ｓ３を計算する第六入力計算部と、を含み、これらの計算されたｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４，ｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５，ｘ_１^−ｓ４ｈ_１^ｓ６及びｈ_２^ｓ３を上記第一入力情報τ_１とし、
ｙ＝ｆ（ｈ_１，ｈ_２）として、上記乱数化可能標本器は、上記第一入力情報τ_１のｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４を用いて、ある確率より大きな確率でｆ（ｘ_１ｈ_１^ｓ１ｓ２，ｘ_２^ａｈ_２^ｓ３ｓ４）を正しく計算し、得られた計算結果を第一出力情報ｚ_１とする第一出力情報生成部と、上記第一入力情報τ_１のｈ_１^ｓ１及びｘ_２^−ａｓ２ｈ_２^ｓ５を用いて、ある確率より大きな確率でｆ（ｈ_１^ｓ１，ｘ_２^−ａｓ２ｈ_２^ｓ５）を正しく計算し、得られた計算結果を第二出力情報ｚ_２とする第二出力情報生成部と、上記第一入力情報τ_１のｘ_１^−ｓ４ｈ_１^ｓ６及びｈ_２^ｓ３を用いて、ある確率より大きな確率でｆ（ｘ_１^−ｓ４ｈ_１^ｓ６，ｈ_２^ｓ３）を正しく計算し、得られた計算結果を第四出力情報ｚ_４とする第四出力情報生成部と、ｚ_１ｚ_２ｚ_４ｙ^{−ｓ１ｓ２ｓ３ｓ４−ｓ１ｓ５−ｓ３ｓ６}を計算してその計算結果を上記ｕとする第一計算部と、を含み、
上記第二入力情報生成部は、０以上所定の数以下の乱数ｒ_５を生成する第三乱数生成部と、０以上所定の数以下の乱数ｒ_６を生成する第四乱数生成部と、ｘ_１^ｒ５を計算する第五入力計算部と、ｘ_２^ｒ６を計算する第六入力計算部と、を含み、これらの計算されたｘ_１^ｒ５、ｘ_２^ｒ６を上記第二入力情報τ_２とし、
上記標本器は、上記第二入力情報τ_２を用いて、ある確率より大きな確率でｆ（ｘ_１^ｒ５，ｘ_２^ｒ６）を正しく計算し、得られた計算結果を第三出力情報ｚ_３とする第三出力情報生成部と、ｚ_３^{１／ｒ５ｒ６}を計算してその計算結果を上記ｖとする第二計算部と、を含む、
代理計算システム。
【請求項７】
請求項３の依頼装置の各部としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項４の計算装置の各部としてコンピュータを機能させるためのプログラム。

【図１】

【図２】

【図３】

【図４】

【図５】

【図６】

【図７】

【図８】

【図９】

【図１０】

【図１１】

【図１２】

【図１３】

【公開番号】特開２０１２−１４５８９１（Ｐ２０１２−１４５８９１Ａ）
【公開日】平成２４年８月２日（２０１２．８．２）
【国際特許分類】
【出願番号】特願２０１１−６１６５（Ｐ２０１１−６１６５）
【出願日】平成２３年１月１４日（２０１１．１．１４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】