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