"G,Hを巡回群、fを群Hの元xを群Gへ写す関数、X1,X2を群Gに値を持つ確率変数、確率変数X1の実現値をx1、確率変数X2の実現値をx2として、互いに素である2つの自然数a,bを用いて、a’ab’b=1の関係を満たす整数a’,b’を計算する整数計算部と、fxbx1を計算可能であり、その計算結果をuとする第一乱数化可能標本器と、u’=uaを計算する第一べき乗計算部と、fxax2を計算可能であり、その計算結果をvとする第二乱数化可能標本器と、v’=vbを計算する第二べき乗計算部と、u’=v’であるか判定する判定部と、u’=v’であると判定された場合には、ub’va’を計算する最終計算部と、を含む代理計算システム。請求項1の代理計算システムにおいて、X3を群Gに値を持つ確率変数、確率変数X3の実現値をx3として、fxx3を計算可能であり、a=1あれば上記第二乱数化可能標本器に代わりその計算結果を上記vとし、b=1であれば上記第一乱数化可能標本器に代わりその計算結果を上記uとする標本器を更に含む、代理計算システム。請求項1の代理計算システムにおいて、上記fを準同型写像、群Hの生成元をμh、群Hの位数をKH、ν=fμhとして、上記第一乱数化可能標本器は、0以上KH未満の整数の乱数r1を生成する第一乱数生成部と、第一入力情報μhr1xbを計算する第一入力情報計算部と、上記第一入力情報μhr1xbを用いてfμhr1xbを計算可能でありその計算結果を第一出力情報z1とする第一出力情報計算部と、z1ν-r1を計算してその計算結果を上記uとする第一計算部とを含み、上記第二乱数化可能標本器は、0以上KH未満の整数の乱数r2を生成する第二乱数生成部と、第二入力情報μhr2xaを計算する第二入力情報計算部と、上記第二入力情報μhr2xaを用いてfμhr2xaを計算可能でありその計算結果を第二出力情報z2とする第二出力情報計算部と、z2ν-r2を計算してその計算結果を上記vとする第二計算部とを含む、代理計算システム。請求項3の代理計算システムにおいて、0以上KH未満の整数の乱数r3を生成する第三乱数生成部と、第三入力情報xr3を計算する第三入力情報計算部と、上記第三入力情報xr3を用いてfxr3を計算可能でありその計算結果を第三出力情報z3とする第三出力情報計算部と、z31/r3を計算してa=1あれば上記第二乱数化可能標本器に代わりその計算結果を上記vとしb=1であれば上記第一乱数化可能標本器に代わりその計算結果を上記uとする第三計算部とを含む標本器を更に含む、代理計算システム。請求項1の代理計算システムにおいて、群H=G×G、上記fを準同型写像、群Gの生成元をμg、群Gの位数をKG、x=c1,c2,V,Wを群Hの元、fV,W=Yとして、上記第一乱数化可能標本器は、0以上KG未満の整数の乱数r4を生成する第四乱数生成部と、0以上KG未満の整数の乱数r5を生成する第五乱数生成部と、第四入力情報c1bVr4μgr5を計算する第四入力情報計算部と、第五入力情報c2bWr4を計算する第五入力情報計算部と、上記第四入力情報c1bVr4μgr5及び上記第五入力情報c2bWr4を用いてfc1bVr4μgr5,c2bWr4を計算可能でありその計算結果を第四出力情報z4とする第四出力情報計算部と、z4Y-r4μg-r5を計算してその計算結果を上記uとする第四計算部とを含み、上記第二乱数化可能標本器は、0以上KG未満の整数の乱数r6を生成する第六乱数生成部と、0以上KG未満の整数の乱数r7を生成する第七乱数生成部と、第六入力情報c1aVr6μgr7を計算する第六入力情報計算部と、第七入力情報c2aWr6を計算する第七入力情報計算部と、上記第六入力情報c1aVr6μgr7及び上記第七入力情報c2aWr6を用いてfc1aVr6μgr7,c2aWr6を計算可能でありその計算結果を第五出力情報z5とする第五出力情報計算部と、z5Y-r6μg-r7を計算してその計算結果を上記vとする第五計算部とを含む、代理計算システム。G,Hを巡回群、fを群Hの元xを群Gへ写す関数、X1,X2を群Gに値を持つ確率変数、確率変数X1の実現値をx1、確率変数X2の実現値をx2として、整数計算部が、互いに素である2つの自然数a,bを用いて、a’ab’b=1の関係を満たす整数a’,b’を計算する整数計算ステップと、第一乱数化可能標本器が、fxbx1を計算可能であり、その計算結果をuとする第一乱数化可能標本抽出ステップと、第一べき乗計算部が、u’=uaを計算する第一べき乗計算ステップと、第二乱数化可能標本器が、fxax2を計算可能であり、その計算結果をvとする第二乱数化可能標本抽出ステップと、第二べき乗計算部が、v’=vbを計算する第二べき乗計算ステップと、判定部が、u’=v’であるか判定する判定ステップと、最終計算部が、u’=v’であると判定された場合には、ub’va’を計算する最終計算ステップと、を含む代理計算方法。G,Hを巡回群、fを群Hの元xを群Gへ写す関数、X1,X2を群Gに値を持つ確率変数、確率変数X1の実現値をx1、確率変数X2の実現値をx2として、互いに素である2つの自然数a,bを用いて、a’ab’b=1の関係を満たす整数a’,b’を計算する整数計算部と、fxbx1を計算可能な第一乱数化可能標本器による計算結果uを用いてu’=uaを計算する第一べき乗計算部と、fxax2を計算可能な第二乱数化可能標本器による計算結果vを用いてv’=vbを計算する第二べき乗計算部と、u’=v’であるか判定する判定部と、u’=v’であると判定された場合には、ub’va’を計算する最終計算部と、を含む依頼装置。依頼装置が計算装置に依頼した計算の結果を用いてθg,hを計算する代理計算システムにおいて、G、H及びFを巡回群とし、写像θ:G×H→Fを双準同型写像とし、gを群Gの元とし、hを群Hの元とし、KGを群Gの位数とし、KHを群Hの位数とし、μgを群Gの生成元とし、μhを群Hの生成元とし、ν=θμg,μgとし、kを自然数のセキュリティパラメータとし、K=2kとして、上記依頼装置は、0以上KG未満の整数の乱数r1を生成する第一乱数生成部と、0以上KH未満の整数の乱数r2を生成する第二乱数生成部と、第一入力情報g1=μgr1gを計算する第一入力情報計算部と、第二入力情報h1=μhr2を計算する第二入力情報計算部と、上記計算装置から受信したz1∈Fを用いて、z1ν-r1r2を計算する第一リスト情報計算部と、上記乱数r2と上記計算されたz1ν-r1r2とから構成される情報の組r2,z1ν-r1r2が記憶される第一リスト記憶部と、0以上K未満の整数の一様乱数であるd1を生成する第三乱数生成部と、0以上KG未満の整数の一様乱数であるr4を生成する第四乱数生成部と、0以上KH未満の整数の一様乱数であるr5を生成する第五乱数生成部と、第三入力情報g2=μgr4gd1を計算する第三入力情報計算部と、第四入力情報h2=μhr5を計算する第四入力情報計算部と、上記計算装置から受信したz2∈Fを用いて、z2ν-r4r5を計算する第二リスト情報計算部と、上記d1と上記r5と上記計算されたz2ν-r4r5とから構成される情報の組d1,r5,z2ν-r4r5が記憶される第二リスト記憶部と、上記第一リスト記憶部から読み込んだ情報の組の第一成分をs1とし、第二成分をw1とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をt2とし、第二成分をs2とし、第三成分をw2として、これらの情報の組がw1^t2s2s1-1=w2の関係を満たすかを判定し、その関係を満たす場合には、s1をσに代入し、w1をν’に代入する第一判定部と、0以上KG未満の整数の一様乱数であるr6を生成する第六乱数生成部と、0以上KH未満の整数の一様乱数であるr7を生成する第七乱数生成部と、第五入力情報g3=gr6を計算する第五入力情報計算部と、第六入力情報h3=μhr7σhを計算する第六入力情報計算部と、上記計算装置から受信したz3∈Fを用いて、z3ν’-r6r7を計算する第三リスト情報計算部と、上記r6と上記計算されたz3ν’-r6r7とから構成される情報の組r6,z3ν’-r6r7が記憶される第三リスト記憶部と、0以上K未満の整数の一様乱数であるd2を生成する第八乱数生成部と、0以上KG未満の整数の一様乱数であるr9を生成する第九乱数生成部と、0以上KH未満の整数の一様乱数であるr10を生成する第十乱数生成部と、第七入力情報g4=μgr9を計算する第七入力情報計算部と、第八入力情報h4=μhr10σhd2を計算する第八入力情報計算部と、上記計算装置から受信したz4∈Fを用いて、z4ν’-r9r10を計算する第四リスト情報計算部と、上記d2と上記r9と上記計算されたz4ν’-r9r10とから構成される情報の組d2,r9,z4ν’-r9r10が記憶される第四リスト記憶部と、上記第三リスト記憶部から読み込んだ情報の組の第一成分をs3とし、第二成分をw3とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をt4とし、第二成分をs4とし、第三成分をw4として、これらの情報の組がw3^t4s4s3-1=w4の関係を満たすかを判定し、その関係を満たす場合には、w3^s3-1を出力する第二判定部と、を含み、上記計算装置は、上記依頼装置から受信したg1及びh1を用いてθg1,h1を計算可能であり、その計算結果を上記z1として出力する第一出力情報計算部と、上記依頼装置から受信したg2及びh2を用いてθg2,h2を計算可能であり、その計算結果を上記z2として出力する第二出力情報計算部と、上記依頼装置から受信したg3及びh3を用いてθg3,h3を計算可能であり、その計算結果を上記z3として出力する第三出力情報計算部と、上記依頼装置から受信したg4及びh4を用いてθg4,h4を計算可能であり、その計算結果を上記z4として出力する第四出力情報計算部と、を含む、代理計算システム。請求項8の代理計算システムにおいて、上記第一入力情報計算部は、第一入力情報g1=gr1を計算し、上記第一リスト情報計算部は、上記r1及び上記r2を用いてr1r2を計算し、上記第一リスト記憶部には、上記計算されたr1r2と上記計算装置から受信したz1∈Fとから構成される情報の組r1r2,z1が記憶される、ことを特徴とする代理計算システム。請求項8又は9に記載の代理計算システムにおいて、上記第六入力情報計算部は、第六入力情報h3=hr7を計算し、上記第三リスト情報計算部は、上記r6及び上記r7を用いてr6r7を計算し、上記第三リスト記憶部には、上記計算されたr6r7と上記計算装置から受信したz3∈Fとから構成される情報の組r6r7,z3が記憶される、ことを特徴とする代理計算システム。請求項8から10の何れかに記載の代理計算システムにおいて、上記第一判定部は、上記の関係を満たす場合には、t1s2をσに代入し、w2をν’に代入し、上記第十乱数生成部は、上記r9を用いて-r9-1を計算してr10とする、ことを特徴とする代理計算システム。請求項11に記載の代理計算システムにおいて、上記第七乱数生成部は、上記r6を用いて-r6-1を計算してr7とし、上記第三リスト記憶部には、1と上記計算されたz3ν’-r6r7とから構成される情報の組1,z3ν’-r6r7が記憶される、ことを特徴とする代理計算システム。請求項8から12の何れかに記載の代理計算システムにおいて、上記第四乱数生成部は、上記r5を用いて-r5-1を計算してr4とする、ことを特徴とする代理計算システム。請求項8から13の何れかに記載の代理計算システムにおいて、上記d1を用いてgd1を計算する事前計算部を更に含み、上記第三入力情報計算部は、上記事前計算されたgd1を用いて、上記g2の計算を行う、ことを特徴とする代理計算システム。請求項8から14の何れかに記載の代理計算システムにおいて、上記d2を用いてhd2を計算する事前計算部を更に含み、上記第八入力情報計算部は、上記事前計算されたhd2を用いて、上記h4の計算を行う、ことを特徴とする代理計算システム。依頼装置が計算装置に依頼した計算の結果を用いてθg,hを計算する代理計算方法において、G、H及びFを巡回群とし、写像θ:G×H→Fを双準同型写像とし、gを群Gの元とし、hを群Hの元とし、KGを群Gの位数とし、KHを群Hの位数とし、μgを群Gの生成元とし、μhを群Hの生成元とし、ν=θμg,μgとし、kを整数のセキュリティパラメータとし、K=2kとして、上記依頼装置の第一乱数生成部が、0以上KG未満の整数の乱数r1を生成する第一乱数生成ステップと、上記依頼装置の第二乱数生成部が、0以上KH未満の整数の乱数r2を生成する第二乱数生成ステップと、上記依頼装置の第一入力情報計算部が、第一入力情報g1=μgr1gを計算する第一入力情報計算ステップと、上記依頼装置の第二入力情報計算部が、第二入力情報h1=μhr2を計算する第二入力情報計算ステップと、上記計算装置の第一出力情報計算部が、上記依頼装置から受信したg1及びh1を用いてθg1,h1を計算可能であり、その計算結果を上記z1として出力する第一出力情報計算ステップと、上記依頼装置の第一リスト情報計算部が、上記計算装置から受信したz1∈Fを用いて、z1ν-r1r2を計算する第一リスト情報計算ステップと、上記依頼装置の第一リスト記憶部に、上記乱数r2と上記計算されたz1ν-r1r2とから構成される情報の組r2,z1ν-r1r2が記憶されるステップと、上記依頼装置の第三乱数生成部が、0以上K未満の整数の一様乱数であるd1を生成する第三乱数生成ステップと、上記依頼装置の第四乱数生成部が、0以上KG未満の整数の一様乱数であるr4を生成する第四乱数生成ステップと、上記依頼装置の第五乱数生成部が、0以上KH未満の整数の一様乱数であるr5を生成する第五乱数生成ステップと、上記依頼装置の第三入力情報計算部が、第三入力情報g2=μgr4gd1を計算する第三入力情報計算ステップと、上記依頼装置の第四入力情報計算部が、第四入力情報h2=μhr5を計算する第四入力情報計算ステップと、上記計算装置の第二出力情報計算部が、上記依頼装置から受信したg2及びh2を用いてθg2,h2を計算可能であり、その計算結果を上記z2として出力する第二出力情報計算ステップと、上記依頼装置の第二リスト情報計算部が、上記計算装置から受信したz2∈Fを用いて、z2ν-r4r5を計算する第二リスト情報計算ステップと、上記依頼装置の第二リスト記憶部に、上記d1と上記r5と上記計算されたz2ν-r4r5とから構成される情報の組d1,r5,z2ν-r4r5が記憶されるステップと、上記依頼装置の第一判定部が、上記第一リスト記憶部から読み込んだ情報の組の第一成分をs1とし、第二成分をw1とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をt2とし、第二成分をs2とし、第三成分をw2として、これらの情報の組がw1^t2s2s1-1=w2の関係を満たすかを判定し、その関係を満たす場合には、s1をσに代入し、w1をν’に代入する第一判定ステップと、上記依頼装置の第六乱数生成部が、0以上KG未満の整数の一様乱数であるr6を生成する第六乱数生成ステップと、上記依頼装置の第七乱数生成部が、0以上KH未満の整数の一様乱数であるr7を生成する第七乱数生成ステップと、上記依頼装置の第五入力情報計算部が、第五入力情報g3=gr6を計算する第五入力情報計算ステップと、上記依頼装置の第六入力情報計算部が、第六入力情報h3=μhr7σhを計算する第六入力情報計算ステップと、上記計算装置の第三出力情報計算部が、上記依頼装置から受信したg3及びh3を用いてθg3,h3を計算可能であり、その計算結果を上記z3として出力する第三出力情報計算ステップと、上記依頼装置の第三リスト情報計算部が、上記計算装置から受信したz3∈Fを用いて、z3ν’-r6r7を計算する第三リスト情報計算ステップと、上記依頼装置の第三リスト記憶部に、上記r6と上記計算されたz3ν’-r6r7とから構成される情報の組r6,z3ν’-r6r7が記憶されるステップと、上記依頼装置の第八乱数生成部が、0以上K未満の整数の一様乱数であるd2を生成する第八乱数生成ステップと、上記依頼装置の第九乱数生成部が、0以上KG未満の整数の一様乱数であるr9を生成する第九乱数生成ステップと、上記依頼装置の第十乱数生成部が、0以上KH未満の整数の一様乱数であるr10を生成する第十乱数生成ステップと、上記依頼装置の第七入力情報計算部が、第七入力情報g4=μgr9を計算する第七入力情報計算ステップと、上記依頼装置の第八入力情報計算部が、第八入力情報h4=μhr10σhd2を計算する第八入力情報計算ステップと、上記計算装置の第四出力情報計算部が、上記依頼装置から受信したg4及びh4を用いてθg4,h4を計算可能であり、その計算結果を上記z4として出力する第四出力情報計算ステップと、上記依頼装置の第四リスト情報計算部が、上記計算装置から受信したz4∈Fを用いて、z4ν’-r9r10を計算する第四リスト情報計算ステップと、上記依頼装置の第四リスト記憶部に、上記d2と上記r9と上記計算されたz4ν’-r9r10とから構成される情報の組d2,r9,z4ν’-r9r10が記憶されるステップと、上記依頼装置の第二判定部が、上記第三リスト記憶部から読み込んだ情報の組の第一成分をs3とし、第二成分をw3とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をt4とし、第二成分をs4とし、第三成分をw4として、これらの情報の組がw3^t4s4s3-1=w4の関係を満たすかを判定し、その関係を満たす場合には、w3^s3-1を出力する第二判定ステップと、を含む代理計算方法。依頼装置が計算装置に依頼した計算の結果を用いてθg,hを計算する代理計算システムの依頼装置において、G、H及びFを巡回群とし、写像θ:G×H→Fを双準同型写像とし、gを群Gの元とし、hを群Hの元とし、KGを群Gの位数とし、KHを群Hの位数とし、μgを群Gの生成元とし、μhを群Hの生成元とし、ν=θμg,μgとし、kを自然数のセキュリティパラメータとし、K=2kとして、0以上KG未満の整数の乱数r1を生成する第一乱数生成部と、0以上KH未満の整数の乱数r2を生成する第二乱数生成部と、第一入力情報g1=μgr1gを計算する第一入力情報計算部と、第二入力情報h1=μhr2を計算する第二入力情報計算部と、上記計算装置から受信したz1∈Fを用いて、z1ν-r1r2を計算する第一リスト情報計算部と、上記乱数r2と上記計算されたz1ν-r1r2とから構成される情報の組r2,z1ν-r1r2が記憶される第一リスト記憶部と、0以上K未満の整数の一様乱数であるd1を生成する第三乱数生成部と、0以上KG未満の整数の一様乱数であるr4を生成する第四乱数生成部と、0以上KH未満の整数の一様乱数であるr5を生成する第五乱数生成部と、第三入力情報g2=μgr4gd1を計算する第三入力情報計算部と、第四入力情報h2=μhr5を計算する第四入力情報計算部と、上記計算装置から受信したz2∈Fを用いて、z2ν-r4r5を計算する第二リスト情報計算部と、上記d1と上記r5と上記計算されたz2ν-r4r5とから構成される情報の組d1,r5,z2ν-r4r5が記憶される第二リスト記憶部と、上記第一リスト記憶部から読み込んだ情報の組の第一成分をs1とし、第二成分をw1とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をt2とし、第二成分をs2とし、第三成分をw2として、これらの情報の組がw1^t2s2s1-1=w2の関係を満たすかを判定し、その関係を満たす場合には、s1をσに代入し、w1をν’に代入する第一判定部と、0以上KG未満の整数の一様乱数であるr6を生成する第六乱数生成部と、0以上KH未満の整数の一様乱数であるr7を生成する第七乱数生成部と、第五入力情報g3=gr6を計算する第五入力情報計算部と、第六入力情報h3=μhr7σhを計算する第六入力情報計算部と、上記計算装置から受信したz3∈Fを用いて、z3ν’-r6r7を計算する第三リスト情報計算部と、上記r6と上記計算されたz3ν’-r6r7とから構成される情報の組r6,z3ν’-r6r7が記憶される第三リスト記憶部と、0以上K未満の整数の一様乱数であるd2を生成する第八乱数生成部と、0以上KG未満の整数の一様乱数であるr9を生成する第九乱数生成部と、0以上KH未満の整数の一様乱数であるr10を生成する第十乱数生成部と、第七入力情報g4=μgr9を計算する第七入力情報計算部と、第八入力情報h4=μhr10σhd2を計算する第八入力情報計算部と、上記計算装置から受信したz4∈Fを用いて、z4ν’-r9r10を計算する第四リスト情報計算部と、上記d2と上記r9と上記計算されたz4ν’-r9r10とから構成される情報の組d2,r9,z4ν’-r9r10が記憶される第四リスト記憶部と、上記第三リスト記憶部から読み込んだ情報の組の第一成分をs3とし、第二成分をw3とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をt4とし、第二成分をs4とし、第三成分をw4として、これらの情報の組がw3^t4s4s3-1=w4の関係を満たすかを判定し、その関係を満たす場合には、w3^s3-1を出力する第二判定部と、を含む依頼装置。請求項7又は請求項17の依頼装置の各部としてコンピュータを機能させるためのプログラム。請求項18の依頼装置プログラムが記録されたコンピュータ読み取り可能な記録媒体。しかしながら、非特許文献1の自己訂正器が正常に動作するためには、計算装置は一定以上の確率で正しい計算をする必要があり、正しい計算を行う確率が低い計算装置を用いて関数fの計算をする技術は知られていないという課題がある。この発明の第一の態様である代理計算システムは、G,Hを巡回群、fを群Hの元xを群Gへ写す関数、X1,X2を群Gに値を持つ確率変数、確率変数X1の実現値をx1、確率変数X2の実現値をx2として、互いに素である2つの自然数a,bを用いて、a’ab’b=1の関係を満たす整数a’,b’を計算する整数計算部と、fxbx1を計算可能であり、その計算結果をuとする第一乱数化可能標本器と、u’=uaを計算する第一べき乗計算部と、fxax2を計算可能であり、その計算結果をvとする第二乱数化可能標本器と、v’=vbを計算する第二べき乗計算部と、u’=v’であるか判定する判定部と、u’=v’であると判定された場合には、ub’va’を計算する最終計算部とを含む。この発明の第二の態様である代理計算システムは、G、H及びFを巡回群とし、写像θ:G×H→Fを双同型準同型写像とし、gを群Gの元とし、hを群Hの元とし、KGを群Gの位数とし、KHを群Hの位数とし、μgを群Gの生成元とし、μhを群Hの生成元とし、ν=θμg,μgとし、kを自然数のセキュリティパラメータとし、K=2kとして、依頼装置は、0以上KG未満の整数の乱数r1を生成する第一乱数生成部と、0以上KH未満の整数の乱数r2を生成する第二乱数生成部と、第一入力情報g1=μgr1gを計算する第一入力情報計算部と、第二入力情報h1=μhr2を計算する第二入力情報計算部と、計算装置から受信したz1∈Fを用いて、z1ν-r1r2を計算する第一リスト情報計算部と、乱数r2と計算されたz1ν-r1r2とから構成される情報の組r2,z1ν-r1r2が記憶される第一リスト記憶部と、0以上K未満の整数の一様乱数であるd1を生成する第三乱数生成部と、0以上KG未満の整数の一様乱数であるr4を生成する第四乱数生成部と、0以上KH未満の整数の一様乱数であるr5を生成する第五乱数生成部と、第三入力情報g2=μgr4gd1を計算する第三入力情報計算部と、第四入力情報h2=μhr5を計算する第四入力情報計算部と、計算装置から受信したz2∈Fを用いて、z2ν-r4r5を計算する第二リスト情報計算部と、d1とr5と計算されたz2ν-r4r5とから構成される情報の組d1,r5,z2ν-r4r5が記憶される第二リスト記憶部と、第一リスト記憶部から読み込んだ情報の組の第一成分をs1とし、第二成分をw1とし、第二リスト記憶部から読み込んだ情報の組の第一成分をt2とし、第二成分をs2とし、第三成分をw2として、これらの情報の組がw1^t2s2s1-1=w2の関係を満たすかを判定し、その関係を満たす場合には、s1をσに代入し、w1をν’に代入する第一判定部と、0以上KG未満の整数の一様乱数であるr6を生成する第六乱数生成部と、0以上KH未満の整数の一様乱数であるr7を生成する第七乱数生成部と、第五入力情報g3=gr6を計算する第五入力情報計算部と、第六入力情報h3=μhr7σhを計算する第六入力情報計算部と、計算装置から受信したz3∈Fを用いて、z3ν’-r6r7を計算する第三リスト情報計算部と、r6と計算されたz3ν’-r6r7とから構成される情報の組r6,z3ν’-r6r7が記憶される第三リスト記憶部と、0以上K未満の整数の一様乱数であるd2を生成する第八乱数生成部と、0以上KG未満の整数の一様乱数であるr9を生成する第九乱数生成部と、0以上KH未満の整数の一様乱数であるr10を生成する第十乱数生成部と、第七入力情報g4=μgr9を計算する第七入力情報計算部と、第八入力情報h4=μhr10σhd2を計算する第八入力情報計算部と、計算装置から受信したz4∈Fを用いて、z4ν’-r9r10を計算する第四リスト情報計算部と、d2とr9と計算されたz4ν’-r9r10とから構成される情報の組d2,r9,z4ν’-r9r10が記憶される第四リスト記憶部と、第三リスト記憶部から読み込んだ情報の組の第一成分をs3とし、第二成分をw3とし、第四リスト記憶部から読み込んだ情報の組の第一成分をt4とし、第二成分をs4とし、第三成分をw4として、これらの情報の組がw3^t4s4s3-1=w4の関係を満たすかを判定し、その関係を満たす場合には、w3^s3-1を出力する第二判定部と、を含む。計算装置は、依頼装置から受信したg1及びh1を用いてθg1,h1を計算可能であり、その計算結果をz1として出力する第一出力情報計算部と、依頼装置から受信したg2及びh2を用いてθg2,h2を計算可能であり、その計算結果をz2として出力する第二出力情報計算部と、依頼装置から受信したg3及びh3を用いてθg3,h3を計算可能であり、その計算結果をz3として出力する第三出力情報計算部と、依頼装置から受信したg4及びh4を用いてθg4,h4を計算可能であり、その計算結果をz4として出力する第四出力情報計算部とを含む。正しい計算を行う確率が低い計算装置を用いて関数fの計算をすることができる。以下、この発明による代理計算システム、代理計算方法の実施形態を詳細に説明する。第一実施形態から第二実施形態は、依頼装置1が計算装置2に依頼した計算の結果を用いてfxを計算するものである。[第一実施形態]第一実施形態の代理計算システムは、図1に例示するように依頼装置1及び計算装置2を含み、依頼装置1が計算装置2に依頼した計算の結果を用いてfxを計算する。依頼装置1は、図2に示すように、自然数記憶部11、整数計算部12、第一べき乗計算部13、第一リスト記憶部14、判定部15、第二べき乗計算部16、第二リスト記憶部17、制御部18及び最終計算部19を例えば含む。計算装置2は、第一乱数化可能標本器21及び第二乱数化可能標本器22を例えば含む。第一実施形態においては、第一乱数化可能標本器21及び第二乱数化可能標本器22が計算装置2に対応する。G,Hを巡回群、関数f:H→Gを群Hの元xを群Gへ写す関数、群G,Hの生成元をそれぞれμg,μh、X1,X2を群Gに値を持つ確率変数、確率変数X1の実現値をx1、確率変数X2の実現値をx2とする。自然数記憶部11には、互いに素である2つの自然数a,bの組a,bが複数記憶されているものとする。Iを群Gの位数未満の2つの自然数の組で互いに素なものの集合とすると、自然数記憶部11にはIの部分集合Sに対応する自然数a,bの組a,bが記憶されていると考えることができる。整数計算部12は、自然数記憶部11に記憶された複数の自然数の組a,bから、1つの自然数の組a,bをランダムに読み込み、その読み込んだ自然数の組a,bを用いて、a’ab’b=1の関係を満たす整数a’,b’を計算するステップS1。自然数a,bは互いに素であるため、a’ab’b=1の関係を満たす整数a’,b’は必ず存在する。自然数の組a,bについての情報は、第一べき乗計算部13、第二べき乗計算部16、第一乱数化可能標本器21及び第二乱数化可能標本器22に送られる。自然数の組a’,b’についての情報は、最終計算部19に送られる。制御部18は、t=1とするステップS2。第一乱数化可能標本器21は、fxbx1を計算可能であり、x及びbを用いて計算を行い、その計算結果をuとするステップS3。計算結果uは、第一べき乗計算部13に送られる。この出願において、計算可能とは、無視することができない確率以上の確率で計算することができることを意味する。無視することができない確率とは、セキュリティパラメータkについての広義単調関数である多項式を多項式Fkとして、1/Fk以上の確率である。ここで、fxbx1を計算するとは、fxbx1と定義される式の値を計算することである。式fxbx1の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。第一べき乗計算部13は、u’=uaを計算するステップS4。計算結果uとその計算結果に基づいて計算されたu’との組u,u’は、第一リスト記憶部14に記憶される。判定部15は、第一リスト記憶部14に記憶された組u,u’及び第二リスト記憶部17に記憶された組v,v’の中で、u’=v’となるものがあるか判定するステップS5。もし、第二リスト記憶部17に組v,v’が記憶されていない場合には、このステップS5の処理を行わずに、次のステップS6の処理を行う。u’=v’となるものがあった場合には、ステップ12に進む。u’=v’となるものがなかった場合には、ステップS6に進む。第二乱数化可能標本器22は、fxax2を計算可能であり、x及びaを用いて計算を行い、その計算結果をvとするステップS6。計算結果vは、第二べき乗計算部16に送られる。第二べき乗計算部16は、v’=vbを計算するステップS7。計算結果vとその計算結果に基づいて計算されたv’との組v,v’は、第二リスト記憶部17に記憶される。判定部15は、第一リスト記憶部14に記憶された組u,u’及び第二リスト記憶部17に記憶された組v,v’の中で、u’=v’となるものがあるか判定するステップS8。u’=v’となるものがあった場合には、ステップ12に進む。u’=v’となるものがなかった場合には、ステップS9に進む。制御部18は、t=Tであるか判定するステップS9。Tは予め定められた自然数である。t=Tであれば、計算をすることができなかった旨の情報、例えば記号⊥を出力してステップS11、処理を終える。t=Tでない場合には、制御部18は、tを1だけインクリメント、すなわちt=t1としてステップS10、ステップS3に戻る。計算をすることができなかった旨の情報この例では記号⊥は、計算装置2が正しく計算を行う信頼性がTで定められる基準を下回るということを意味する。言い換えれば、T回の繰り返しで正しい演算を行うことができなかったということを意味する。最終計算部19は、u’=v’であると判定された場合には、そのu’及びv’に対応するu及びvを用いてub’va’を計算して、出力するステップS12。計算されたub’va’=fxとなる。ub’va’=fxとなる理由については、後述する。≪ub’va’=fxとなる理由について≫Xを群Gに値を持つ確率変数とする。w∈Gについて、ある計算装置で要求を受けるたびに確率変数Rに従って標本x’を抽出しwx’を返信するものを、wについて誤差Xを持つ標本器samplerと呼ぶ。w∈Gについて、ある計算装置で自然数aの入力を受けるたびに確率変数Xに従って標本x’を抽出しwax’を返信するものを、wについて誤差Xを持つ乱数化可能標本器randomizablesamplerと呼ぶ。乱数化可能標本器はa=1として用いられれば標本器として機能する。上記実施形態の代理計算システムは、xを入力としてfxを出力する代理計算システムを構成するに当たり、fxについて誤差X1を持つ第一乱数化可能標本器21、fxについて誤差X2を持つ第二乱数化可能標本器22を用いている。u’=v’が成立するのは、すなわちua=vbが成立するのは、第一乱数化可能標本器21がu=fxbx1を正しく計算しており、第二乱数化可能標本器22がv=fxax2を正しく計算しており、さらにx1及びx2が群Gの単位元egである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。第一乱数化可能標本器21がu=fxbx1を正しく計算しており、第二乱数化可能標本器22がv=fxax2を正しく計算しており、x1及びx2が群Gの単位元egであるとき、ub’va’=fxbx1b’fxax2a’=fxbegb’fxaega’=fxbb’egb’fxaa’ega’=fxbb’aa’=fxとなる。q1,q2∈Iについて、i=1,2の各々について関数πiをπiq1,q2=qiで定義する。また、L=min♯π1S,♯π2Sとする。♯は、集合の位数である。群Gが巡回群や位数の計算が困難な群であるときには、上記代理計算システムが⊥以外を出力するときの出力がfxではない確率は、無視できる程度の誤差の範囲で高々T2L/♯S程度と期待することができる。もしL/♯Sが無視できる量でTが多項式オーダー程度の量であれば、上記代理計算システムは圧倒的な確率でfxを出力する。L/♯Sが無視できる量になるようなSの例には、例えばS={1,d|d∈[2,|G|-1]}がある。なお、図2に破線で示すように、計算装置2に標本器23を設けてもよい。標本器23は、X3を群Gに値を持つ確率変数、確率変数X3の実現値をx3として、fxx3を計算可能であり、a=1あれば第二乱数化可能標本器22に代わりその計算結果を上記vとし、b=1であれば第一乱数化可能標本器21に代わりその計算結果を上記uとする。一般に乱数化可能標本器よりも標本器の計算量は小さい。a=1,b=1のときに第一乱数化可能標本器21、第二乱数化可能標本器22に代わり、標本器23が計算を行うことで、計算装置2の計算量を小さくすることができる。[第二実施形態]第二実施形態の代理計算システムは、第一乱数化可能標本器21及び第二乱数化可能標本器22の一例、言い換えればステップS3及びステップS6の一例を具体化したものである。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。第二実施形態の第一乱数化可能標本器21は、図3に示すように、第一乱数生成部110、第一入力情報計算部111、第一出力情報計算部24及び第一計算部112を例えば含む。また、第二実施形態の第二乱数化可能標本器22は、図3に示すように、第二乱数生成部113、第二入力情報計算部114、第二出力情報計算部25及び第二計算部115を例えば含む。第二実施形態においては、第一乱数生成部110、第一入力情報計算部111、第一計算部112、第二乱数生成部113、第二入力情報計算部114及び第二計算部115は、依頼装置1に含まれる。また、第一出力情報計算部24及び第二出力情報計算部25は、計算装置2に含まれる。第二実施形態においては、第一出力情報計算部24及び第二出力情報計算部25が計算装置2に対応する。第二実施形態の関数fは準同型写像であるとする。また、群Hの生成元をμh、群Hの位数をKH、ν=fμhとする。ステップS3は、図7に例示するステップS31からステップS34で構成される。第一乱数生成部110は、0以上KH未満の整数の一様乱数r1を生成するステップS31。生成された乱数r1は、第一入力情報計算部111に送られる。第一入力情報計算部111は、第一入力情報μhr1xbを計算するステップS32。計算された第一入力情報μhr1xbは、第一出力情報計算部24に送られる。第一出力情報計算部24は、第一入力情報μhr1xbを用いて計算を行い、その計算結果を第一出力情報z1とするステップS33。計算された第一出力情報z1は、第一計算部112に送られる。第一出力情報計算部24は、fμhr1xbを計算可能である。第一出力情報計算部24による計算の結果がfμhr1xbであることもあれば、fμhr1xbでないこともある。ここで、μhの右肩のr1は、r1のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。第一計算部112は、z1ν-r1を計算してその計算結果をuとするステップS34。計算結果uは、第一べき乗計算部13に送られる。ここで、u=z1ν-r1=fxbx1となる。すなわち、z1ν-r1は、fxについて誤差X1を持つ乱数化可能標本器となる。その理由については後述する。ステップS6は、図8に例示するステップS61からステップS64で構成される。第二乱数生成部113は、0以上KH未満の整数の一様乱数r2を生成するステップS61。生成された乱数r2は、第二入力情報計算部114に送られる。第二入力情報計算部114は、第二入力情報μhr2xaを計算するステップS62。計算された第二入力情報μhr2xaは、第二出力情報計算部25に送られる。第二出力情報計算部25は、第二入力情報μhr2xaを用いて計算を行い、その計算結果を第二出力情報z2とするステップS63。計算された第二出力情報z2は、第二計算部115に送られる。第二出力情報計算部25は、fμhr2xaを計算可能である。第二出力情報計算部25による計算の結果がfμhr2xaであることもあれば、fμhr2xaでないこともある。第二計算部115は、z2ν-r2を計算してその計算結果をvとするステップS64。計算結果vは、第二べき乗計算部16に送られる。ここで、v=z2ν-r2=fxax2となる。すなわち、z2ν-r2は、fxについて誤差X2を持つ乱数化可能標本器となる。その理由については後述する。第二実施形態においても、a=1,b=1のときは、第一乱数化可能標本器21又は第二乱数化可能標本器22に代わり、標本器23がu又はvの値を計算することにより、計算量を削減してもよい。第二実施形態の標本器23は、図4に示すように、第三乱数生成部116、第三入力情報計算部117、第三出力情報計算部26、第三計算部118を例えば含む。第三乱数生成部116、第三入力情報計算部117及び第三計算部118は依頼装置1に含まれる。第三出力情報計算部26は計算装置2に含まれる。a=1,b=1であれば、第一乱数化可能標本器21、第二乱数化可能標本器22に代わり標本器23の各部は以下の処理を行う。第三乱数生成部116は、0以上KH未満の整数の乱数r3を生成する。生成された乱数r3は第三入力情報計算部117に送られる。第三入力情報計算部117は、第三入力情報xr3を計算する。計算された第三入力情報xr3は、第三出力情報計算部26に送られる。第三出力情報計算部26は、第三入力情報xr3を用いて計算を行い、その計算結果を第三出力情報z3とする。計算された第三出力情報z3は、第三計算部118に送られる。第三出力情報計算部26は、fxr3を計算可能である。第三出力情報計算部26による計算の結果がfxr3であることもあれば、fxr3でないこともある。第三計算部118は、z31/r3を計算してその計算結果を、a=1であればvとし、b=1であればuとする。計算結果vは第二べき乗計算部16に送られる。計算結果uは第一べき乗計算部13に送られる。ここで、u=v=z31/r3=fxx3となる。すなわち、z31/r3は、fxについて誤差X3を持つ標本器となる。z31/r3は、fxについて誤差X3を持つ標本器となる。その理由については後述する。z31/r3の計算、すなわちz3のべき乗根の計算が困難な場合には、次のようにしてu及び/又はvを計算してもよい。第三計算部118は、乱数r3とその乱数r3に基づいて計算されたz3の組を順次α1,β1,α2,β2,...,αm,βm,...として図示していない記憶部に記憶する。mは自然数である。第三計算部118は、α1,α2,...,αmの最小公倍数が1になれば、γ1,γ2,...,γmを整数としてγ1α1γ2α2...γmαm=1となるγ1,γ2,...,γmを計算して、そのγ,γ2,...,γmを用いてΠi=1mβiγi=β1γ1β2γ2...βmγmを計算して、その計算結果をu及び/又はvとしてもよい。このように、乱数r1,r2,r3を用いてxを撹乱した情報を計算装置2に送ることにより、関数fの値の計算の対象となるx∈Hを依頼装置1と計算装置2との間の通信を傍受する第三者、及び、計算装置2に対して秘匿化することができる。≪z1ν-r1,z2ν-r2がfxについてそれぞれ誤差X1,X2を持つ乱数化可能標本器となる理由について≫cを自然数、R及びR’を乱数として、計算装置2がμhRxcを用いて行う計算の計算結果をBμhRxcすなわち、計算装置2が依頼装置1に返す計算結果をzとすると、z=BμhRxcである。とし、群Gに値を持つ確率変数XをX=BμhR’fμhR’-1と定義する。このとき、zν-R=BμhRxcfμh-R=XfμhRxcfμh-R=XfμhRfxcfμh-R=fxcXとなる。すなわち、zν-Rは、fxについて誤差Xを持つ乱数化可能標本器となる。上記式展開において、X=BμhR’fμhR’-1=BμhRxcfμhRxc-1であり、BμhRxc=XfμhRxcであるという性質を用いている。この性質は、関数fが準同型写像であり、R及びR’が乱数であることに基づく。したがって、a,bが自然数、r1,r2が乱数であることを考慮すると、同様に、z1ν-r1,z2ν-r2がfxについてそれぞれ誤差X1,X2を持つ乱数化可能標本器となるのである。≪z31/r3がfxについて誤差X3を持つ標本器となる理由について≫R及びR’を乱数として、計算装置2がxRを用いて行う計算の計算結果をBxRすなわち、計算装置2が依頼装置1に返す計算結果をzとすると、z=BxRである。とし、群Gに値を持つ確率変数XをX=BxR1/Rfx-1と定義する。このとき、z1/R=BxR1/R=Xfx=fxXとなる。すなわち、z1/Rは、fxについて誤差Xを持つ標本器となる。上記式展開において、X=BxR1/RfxR-1であり、BxR1/R=XfxRであるという性質を用いている。この性質は、R及びR’が乱数であることに基づく。したがって、r3が乱数であることを考慮すると、z1/Rがfxについて誤差X3を持つ乱数化可能標本器となるのである。[第三実施形態]第三実施形態の代理計算システムは、第一乱数化可能標本器21及び第二乱数化可能標本器22の他の例、言い換えればステップS3及びステップS6の他の例を具体化したものである。具体的には、H=G×Gで、関数fがElGamal暗号の復号関数、すなわち秘密鍵s及び暗号文c1,c2に対してfc1,c2=c1c2-sである場合の第一乱数化可能標本器21及び第二乱数化可能標本器22の例を具体化したものである。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。第三実施形態の第一乱数化可能標本器21は、図5に示すように、第四乱数生成部119、第五乱数生成部120、第四入力情報計算部121、第五入力情報計算部122、第四出力情報計算部27及び第四計算部123を例えば含む。第二乱数化可能標本器22は、図5に示すように、第六乱数生成部124、第七乱数生成部125、第六入力情報計算部126、第七入力情報計算部127、第五出力情報計算部28及び第五計算部128を例えば含む。第四乱数生成部119、第五乱数生成部120、第四入力情報計算部121、第五入力情報計算部122、第四計算部123、第六乱数生成部124、第七乱数生成部125、第六入力情報計算部126、第七入力情報計算部127、第五出力情報計算部28及び第五計算部128は、依頼装置1に含まれる。第四出力情報計算部27及び第五出力情報計算部28は計算装置2に含まれる。第三実施形態では、第四出力情報計算部27及び第五出力情報計算部28が計算装置2に対応する。第三実施形態では、x=c1,c2であり、fc1,c2は直積群G×GからGへの準同型写像であり、群Gの生成元をμgとし、群Gの位数をKGとし、同じ秘密鍵sに対する暗号文V,W∈Hとその暗号文を復号した復号文fV,W=Y∈Gとを依頼装置1と計算装置2は事前に知っているとする。第三実施形態のステップS3は、図9に例示するステップS31’からステップS36’で構成される。第四乱数生成部119は、0以上KG未満の整数の一様乱数r4を生成するステップS31’。生成された乱数r4は、第四入力情報計算部121、第五入力情報計算部122及び第四計算部123に送られる。第五乱数生成部120は、0以上KG未満の整数の一様乱数r5を生成するステップS32’。生成された乱数r5は、第四入力情報計算部121及び第四計算部123に送られる。第四入力情報計算部121は、第四入力情報c1bVr4μgr5を計算するステップS33’。計算された第四入力情報c1bVr4μgr5は、第四出力情報計算部27に送られる。第五入力情報計算部122は、第五入力情報c2bWr4を計算するステップS34’。計算された第五入力情報c2bWr4は、第四出力情報計算部27に送られる。第四出力情報計算部27は、第四入力情報c1bVr4μgr5及び第五入力情報c2bWr4を用いて計算を行い、その計算結果を第四出力情報z4とするステップS35’。第四出力情報計算部27は、fc1bVr4μgr5,c2bWr4を計算可能である。第四出力情報計算部27による計算の結果がfc1bVr4μgr5,c2bWr4であることもあれば、fc1bVr4μgr5,c2bWr4でないこともある。第四計算部123は、z4Y-r4μg-r5を計算してその計算結果をuとするステップS36’。計算結果uは、第一べき乗計算部13に送られる。ここで、u=z4Y-r4μg-r5=fc1,c2bx1となる。すなわち、z4Y-r4μg-r5は、fc1,c2について誤差X1を持つ乱数化可能標本器となる。その理由については後述する。第三実施形態のステップS6は、図10に例示するステップS61’からステップS66’で構成される。第六乱数生成部124は、0以上KG未満の整数の一様乱数r6を生成するステップS61’。生成された乱数r6は、第六入力情報計算部126、第七入力情報計算部127及び第五計算部128に送られる。第七乱数生成部125は、0以上KG未満の整数の一様乱数r7を生成するステップS62’。生成された乱数r7は、第六入力情報計算部126及び第五計算部128に送られる。第六入力情報計算部126は、第六入力情報c1aVr6μgr7を計算するステップS63’。計算された第六入力情報c1aVr6μgr7は、第五出力情報計算部28に送られる。第七入力情報計算部127は、第七入力情報c2aWr6を計算するステップS64’。計算された第七入力情報c2aWr6は、第五出力情報計算部28に送られる。第五出力情報計算部28は、上記第六入力情報c1aVr6μgr7及び上記第七入力情報c2aWr6を用いて計算を行い、その計算結果を第五出力情報z5とするステップS65’。計算された第五出力情報z5は、第五計算部128に送られる。第五出力情報計算部28は、fc1aVr6μgr7,c2aWr6を計算可能である。第五出力情報計算部28による計算の結果がfc1aVr6μgr7,c2aWr6であることもあれば、fc1aVr6μgr7,c2aWr6でないこともある。第五計算部128は、z5Y-r6μg-r7を計算してその計算結果をvとするステップS66’。計算結果vは、第二べき乗計算部16に送られる。ここで、v=z5Y-r6μg-r7=fc1,c2ax2となる。すなわち、z5Y-r6μg-r7は、fc1,c2について誤差X2を持つ乱数化可能標本器となる。その理由については後述する。≪z4Y-r4μg-r5,z5Y-r6μg-r7がfc1,c2についてそれぞれ誤差X1,X2を持つ乱数化可能標本器となる理由について≫cを自然数、R1、R2、R1’及びR2’を乱数として、計算装置2がc1cVR1μgR2及びc2cWR1を用いて行う計算の計算結果をBc1cVR1μgR2,c2cWR1すなわち、計算装置2が依頼装置1に返す計算結果をzとすると、z=Bc1cVR1μgR2,c2cWR1である。とし、群Gに値を持つ確率変数XをX=BVR1’μgR2’,WR1’fVR1’μgR2’,WR1’-1と定義する。このとき、zY-R1μg-R2=Bc1cVR1μgR2,c2cWR1Y-R1μg-R2=Xfc1cVR1μgR2,c2cWR1Y-R1μg-R2=Xfc1,c2cfV,WR1fμg,egR2Y-R1μg-R2=Xfc1,c2cYR1μgR2Y-R1μg-R2=fc1,c2cXとなる。すなわち、zY-R1μg-R2は、fxについて誤差Xを持つ乱数化可能標本器となる。なお、egは、群Gの単位元である。上記式展開において、X=BVR1’μgR2’,WR1’fVR1’μgR2’,WR1’-1=Bc1cVR1μgR2,c2cWR1fc1cVR1μgR2,c2cWR1であり、Bc1cVR1μgR2,c2cWR1=Xfc1cVR1μgR2,c2cWR1であるという性質を用いている。この性質は、R1、R2、R1’及びR2’が乱数であることに基づく。したがって、a,bが自然数、r4,r5,r6及びr7が乱数であることを考慮すると、同様に、z4Y-r4μg-r5,z5Y-r6μg-r7がfc1,c2についてそれぞれ誤差X1,X2を持つ乱数化可能標本器となるのである。[第一実施形態から第三実施形態の変形例等]確率変数X1、X2及びX3は、同じでも異なっていてもよい。第一乱数生成部110、第二乱数生成部113、第三乱数生成部116、第四乱数生成部119、第五乱数生成部120、第六乱数生成部124及び第七乱数生成部125のそれぞれは、一様乱数を生成することにより、代理計算システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部110、第二乱数生成部113、第三乱数生成部116、第四乱数生成部119、第五乱数生成部120、第六乱数生成部124及び第七乱数生成部125のそれぞれは、一様乱数ではない乱数を生成してもよい。上記の例では、第一乱数化可能標本器21、第二乱数化可能標本器22を一回づつ呼び出しているが、依頼装置1と計算装置2との間の通信回数を減らすために、同一のa,bに対して第一乱数化可能標本器21、第二乱数化可能標本器22を複数回呼び出して、依頼装置1が一回の通信で複数のu,vを取得できるようにしてもよい。第一乱数化可能標本器21、第二乱数化可能標本器22及び標本器23の各部は、依頼装置1に配置してもよいし、計算装置2に配置してもよい。すなわち、第一実施形態のように各部のすべてを計算装置2に配置してもよいし、例えば第二実施形態及び第三実施形態のように依頼装置1及び計算装置2に分けて配置してもよい。依頼装置1の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、計算装置2の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。依頼装置1及び計算装置2のそれぞれはコンピュータによって実現することができる。この場合、この装置が有すべき各機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これ装置における各処理機能が、コンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。[第四実施形態]第四実施形態から第十実施形態は、依頼装置1’が計算装置2’に依頼した計算の結果を用いてθg,hを計算するものである。第四実施形態の代理計算システムは、図11に例示するように依頼装置1’及び計算装置2’を含み、依頼装置1’が計算装置2’に依頼した計算の結果を用いて双準同型写像θg,hを計算する。ここで、G、H及びFを巡回群とし、写像θ:G×H→Fを双準同型写像とし、gを群Gの元とし、hを群Hの元とし、KGを群Gの位数とし、KHを群Hの位数とし、μgを群Gの生成元とし、μhを群Hの生成元とし、ν=θμg,μgとし、kを1以上の整数のセキュリティパラメータとし、K=2kとする。双準同型写像とは、2つの入力のそれぞれに対して準同型である写像を意味する。この例では、写像θg,hは、群Gの元gに対して準同型であり、かつ、群Hの元hに対して準同型である。依頼装置1’と計算装置2’との間には通信路が確立されており、依頼装置1’及び計算装置2’は双方向に通信可能である。この通信路は秘密に保たれている必要はなく、第三者がこの通信路を流れる情報を傍受することができてもよい。依頼装置1’は信頼できない計算装置2’に乱数によって撹乱した情報を送信し、計算装置2’はその撹乱された情報を用いて一定のアルゴリズムに従って計算を行い、その計算結果を依頼装置1’に返信する。この計算装置2’への情報の送受信を繰り返すことにより、依頼装置1’は最終的にθg,hを計算する。依頼装置1’は、まずステップS11’からステップS125’図15の処理によりθg,μhと同等の情報σ,ν’を計算し、そのθg,μhと同等の情報σ,ν’を用いてステップS21’からステップS225’の処理によりθg,μを計算する。依頼装置1’は、図12及び図13に例示する、第一乱数生成部11’、第二乱数生成部12’、第一入力情報計算部13’、第二入力情報計算部14’、第一リスト情報計算部15’、第一リスト記憶部16’、受信部17’、送信部18’、第四乱数生成部21’、第五乱数生成部22’、第三入力情報計算部23’、第四入力情報計算部24’、第二リスト情報計算部25’、第二リスト記憶部26’、第三乱数生成部27’、第一判定部28’、第六乱数生成部31’、第七乱数生成部32’、第五入力情報計算部33’、第六入力情報計算部34’、第三リスト情報計算部35’、第三リスト記憶部36’、第九乱数生成部41’、第十乱数生成部42’、第七入力情報計算部43’、第八入力情報計算部44’、第四リスト情報計算部45’、第四リスト計算部46’、第八乱数生成部47’及び第二判定部48’を例えば含む。計算装置2’は、図14に例示するように、受信部51’、送信部52’、第一出力情報計算部53’、第二出力情報計算部54’、第三出力情報計算部55’及び第四出力情報計算部56’を例えば含む。<ステップS11’図15>第一乱数生成部11’は、0以上KG未満の整数の一様乱数であるr1を生成するステップS11’。生成された乱数r1は、第一入力情報計算部13’及び第一リスト情報計算部15’に送られる。<ステップS12’>第二乱数生成部12’は、0以上KH未満の整数の一様乱数であるr2を生成するステップS12’。生成された乱数r2は、第二入力情報計算部14’、第一リスト情報計算部15’及び第一リスト記憶部16’に送られる。<ステップS13’>第一入力情報計算部13’は、第一入力情報g1=μgr1gを計算するステップS13’。計算されたg1は送信部18’に送られる。ここで、μgの右肩のr1は、r1のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。また、g1=μgr1gを計算するとは、μgr1gという式で定義されるg1の値を計算することである。式μgr1gの値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。<ステップS14’>第二入力情報計算部14’は、第二入力情報h1=μhr2を計算するステップS14’。計算されたh1は送信部18’に送られる。<ステップS15’>送信部18’は、第一入力情報g1及び第二入力情報h1を計算装置2’に送信するステップS15’。<ステップS16’>計算装置2’の受信部51’図14は、第一入力情報g1及び第二入力情報h1を受信するステップS16’。<ステップS17’>第一出力情報計算部53’は、第一入力情報g1及び第二入力情報h1を用いて計算を行い、その計算結果を第一出力情報z1とするステップS17’。z1は、送信部52’に送られる。第一出力情報計算部53’は、θg1,h1を計算可能である。第一出力情報計算部53’による計算の結果がθg1,h1であることもあれば、θg1,h1でないこともある。この出願において、計算可能とは、無視することができない確率で計算することができることを意味する。無視することができない確率とは、セキュリティパラメータkについての広義単調増加関数である多項式を多項式fkとして、1/fk以上の確率である。<ステップS18’>送信部52’は、第一出力情報z1を依頼装置1’に送信するステップS18’。<ステップS19’>依頼装置1’の受信部17’図12は、第一出力情報z1を受信するステップS19’。受信した第一出力情報z1は、第一リスト情報計算部15’に送られる。ここでは、第一出力情報z1は群Fの元であるとする。<ステップS110’>第一リスト情報計算部15’は、乱数r1、乱数r2及び第一出力情報z1を用いて、z1ν-r1r2を計算するステップS110’。計算されたz1ν-r1r2は、第一リスト記憶部16’に送られる。<ステップS111’>乱数r2と、z1ν-r1r2とから構成される情報の組r2,z1ν-r1r2がリストL1に追加される。この例では、第一リスト記憶部16’に、情報の組r2,z1ν-r1r2が記憶されるステップS111’。<ステップS112’>第三乱数生成部27’は、0以上K未満の整数の一様乱数であるd1を生成するステップS112’。生成された乱数d1は、第三入力情報計算部23’及び第二リスト記憶部26’に送られる。<ステップS113’>第四乱数生成部21’は、0以上KG未満の整数の一様乱数であるr4を生成するステップS113’。生成された乱数r4は、第三入力情報計算部23’及び第二リスト情報計算部25’に送られる。<ステップS114’>第五乱数生成部22’は、0以上KH未満の整数の一様乱数であるr5を生成するステップS114’。生成された乱数r5は、第四入力情報計算部24’、第二リスト情報計算部25’及び第二リスト記憶部26’に送られる。<ステップS115’>第三入力情報計算部23’は、第三入力情報g2=μgr4gd1を計算するステップS115’。計算された第三入力情報g2は、送信部18’に送られる。<ステップS116’>第四入力情報計算部24’は、第四入力情報h2=μhr5を計算するステップS116’。計算された第四入力情報h2は、送信部18’に送られる。<ステップS117’>送信部18’は、第三入力情報g2及び第四入力情報h2を計算装置2’に送信するステップS117’。<ステップS118’>計算装置2’の受信部51’図14は、第三入力情報g2及び第四入力情報h2を受信するステップS118’。<ステップS119’>第二出力情報計算部54’は、第三入力情報g2及び第三入力情報h2を用いて計算を行い、その計算結果を第二出力情報z2とするステップS119’。z2は、送信部52’に送られる。第二出力情報計算部54’は、θg2,h2を計算可能である。第二出力情報計算部54’による計算の結果がθg2,h2であることもあれば、θg2,h2でないこともある。<ステップS120’>送信部52’は、第二出力情報z2を依頼装置1’に送信するステップS120’。<ステップS121’>依頼装置1’の受信部17’図12は、第二出力情報z2を受信するステップS121’。受信した第二出力情報z2は、第二リスト情報計算部25’に送られる。ここでは、第二出力情報z2は群Fの元であるとする。<ステップS122’>第二リスト情報計算部25’は、乱数r4、乱数r5及び第二出力情報z2を用いて、z2ν-r4r5を計算するステップS122’。計算されたz2ν-r4r5は、第二リスト記憶部26’に送られる。<ステップS123’>乱数d1と、乱数r5と、z2ν-r4r5とから構成される情報の組d1,r5,z2ν-r4r5が、リストL2に追加される。この例では、第二リスト記憶部26’には、情報の組d1,r5,z2ν-r4r5が記憶されるステップS123’。<ステップS124’>第一判定部28’は、第一リスト記憶部16’から読み込んだ情報の組の第一成分をs1とし、第二成分をw1とし、第二リスト記憶部26’から読み込んだ情報の組の第一成分をt2とし、第二成分をs2とし、第三成分をw2として、これらの情報の組がw1^t2s2s1-1=w2の関係を満たすかを判定するステップS124’。第一判定部28’は、第一リスト記憶部16’及び第二リスト記憶部26’に複数の情報の組が記憶されている場合には、第一リスト記憶部16’に記憶された情報の組r2,z1ν-r1r2と、第二リスト記憶部26’に記憶された情報の組d1,r5,z2ν-r4r5とから構成されるすべての情報のペアについて、上記関係を満たすかどうかを判定する。もちろん、既に上記関係を満たすかどうかを判定した情報のペアについては、その判定処理を省いてもよい。<ステップS125’>第一判定部28’は、上記の関係を満たす場合には、s1をσに代入し、w1をν’に代入するステップS125’。ここで、ν’1/σ=w11/σ=θg,μhとなる。ν’1/σ=θg,μhとなる理由については後述する。上記の関係を満たさない場合には、ステップS11’に戻る。<ステップS21’図16>第六乱数生成部31’は、0以上KG未満の整数の一様乱数であるr6を生成するステップS21’。生成された乱数r6は、第五入力情報計算部33’、第三リスト情報計算部35’及び第三リスト記憶部36’に送られる。<ステップS22’>第七乱数生成部32’は、0以上KH未満の整数の一様乱数であるr7を生成するステップS22’。生成された乱数r7は、第六入力情報計算部34’及び第三リスト情報計算部35’に送られる。<ステップS23’>第五入力情報計算部33’は、第五入力情報g3=μgr6を計算するステップS23’。計算されたg3は送信部18’に送られる。<ステップS24’>第六入力情報計算部34’は、第六入力情報h3=μhr7σhを計算するステップS24’。計算されたh3は送信部18’に送られる。<ステップS25’>送信部18’は、第五入力情報g3及び第六入力情報h3を計算装置2’に送信するステップS25’。<ステップS26’>計算装置2’の受信部51’図14は、第五入力情報g3及び第六入力情報h3を受信するステップS26’。<ステップS27’>第三出力情報計算部55’は、第五入力情報g3及び第六入力情報h3を用いて計算を行い、その計算結果を第三出力情報z3とするステップS27’。z3は、送信部52’に送られる。第三出力情報計算部55’は、θg3,h3を計算可能である。第三出力情報計算部55’による計算の結果がθg3,h3であることもあれば、θg3,h3でないこともある。<ステップS28’>送信部52’は、第三出力情報z3を依頼装置1’に送信するステップS28’。<ステップS29’>依頼装置1’の受信部17’図13は、第三出力情報z3を受信するステップS29’。受信した第三出力情報z3は、第三リスト情報計算部35’に送られる。ここでは、第3出力情報z3は群Fの元であるとする。<ステップS210’>第三リスト情報計算部35’は、乱数r6、乱数r7及び第三出力情報z3を用いて、z3ν’-r6r7を計算するステップS210’。計算されたz3ν-r6r7は、第三リスト記憶部36’に送られる。<ステップS211’>乱数r6と、z3ν’-r6r7とから構成される情報の組r6,z3ν’-r6r7がリストL3に追加される。この例では、第三リスト記憶部36’に、情報の組r6,z3ν’-r6r7が記憶されるステップS211’。<ステップS212’>第八乱数生成部47’は、0以上K未満の整数の一様乱数であるd2を生成するステップS212’。生成された乱数d2は、第八入力情報計算部44及び第四リスト記憶部46’に送られる。<ステップS213’>第九乱数生成部41’は、0以上KG未満の整数の一様乱数であるr9を生成するステップS213’。生成された乱数r9は、第七入力情報計算部43’、第四リスト情報計算部45’及び第四リスト記憶部46’に送られる。<ステップS214’>第十乱数生成部42’は、0以上KH未満の整数の一様乱数であるr10を生成するステップS214’。生成された乱数r10は、第八入力情報計算部44’、第四リスト情報計算部45’及び第四リスト記憶部46’に送られる。<ステップS215’>第七入力情報計算部43’は、第七入力情報g4=gr9を計算するステップS215’。計算された第七入力情報g4は、送信部18’に送られる。<ステップS216’>第八入力情報計算部44’は、第八入力情報h4=μhr10σhd2を計算するステップS216’。計算された第八入力情報h4は、送信部18’に送られる。<ステップS217’>送信部18’は、第七入力情報g4及び第八入力情報h4を計算装置2’に送信するステップS217’。<ステップS218’>計算装置2’の受信部51’図14は、第七入力情報g4及び第八入力情報h4を受信するステップS218’。<ステップS219’>第四出力情報計算部56’は、第七入力情報g4及び第八入力情報h4を用いて計算を行い、その計算結果を第四出力情報z4とするステップS219’。z4は、送信部52’に送られる。第四出力情報計算部56’は、θg4,h4を計算可能である。第四出力情報計算部56’による計算の結果がθg4,h4であることもあれば、θg4,h4でないこともある。<ステップS220’>送信部52’は、第四出力情報z4を依頼装置1’に送信するステップS220’。<ステップS221’>依頼装置1’の受信部17’図12は、第四出力情報z4を受信するステップS221。受信した第四出力情報z4は、第四リスト情報計算部45’に送られる。ここでは、第四出力情報z4は群Fの元であるとする。<ステップS222’>第四リスト情報計算部45’は、乱数r9、乱数r10及び第四出力情報z4を用いて、z4ν’-r9r10を計算するステップS222’。計算されたz4ν’-r9r10は、第四リスト記憶部46’に送られる。<ステップS223’>乱数d2と、乱数r9と、z4ν-r9r10とから構成される情報の組d2,r9,z4ν’-r9r10が、リストL4に追加される。この例では、第四リスト記憶部46’に、情報の組d2,r9,z4ν-r9r10が記憶されるステップS223’。<ステップS224’>第二判定部48’は、第三リスト記憶部36’から読み込んだ情報の組の第一成分をs3とし、第二成分をw3とし、第四リスト記憶部46’から読み込んだ情報の組の第一成分をt4とし、第二成分をs4とし、第三成分をw4として、これらの情報の組がw3^t4s4s3-1=w4の関係を満たすかを判定するステップS224’。第二判定部48’は、第三リスト記憶部36’及び第四リスト記憶部46’に複数の情報の組が記憶されている場合には、第三リスト記憶部36’に記憶された情報の組r6,z3ν’-r6r7と、第四リスト記憶部46’に記憶された情報の組d2,r9,z4ν’-r9r10とから構成されるすべての情報のペアについて、上記関係を満たすかどうかを判定する。もちろん、既に上記関係を満たすかどうかを判定した情報のペアについては、その判定処理を省いてもよい。<ステップS225’>第二判定部48’は、上記の関係を満たす場合には、w3^s3-1を出力するステップS225’。ここで、w3^s3-1=θg,hとなる。w3^s3-1=θg,hとなる理由については後述する。上記の関係を満たさない場合には、ステップS21’に戻る。w3^s3-1の計算、すなわちw3のべき乗根の計算が困難な場合には、次のようにしてθg,hを容易に計算することができる。第二判定部48’は、ステップS21’からステップS224’の処理を繰り返してw3^t4s4s3-1=w4の関係を満たすw3とs3との組w3,s3を順次α1,S1,α2,S2,...,αm,Sm,...として記憶部410’に記憶する。mは自然数である。第二判定部48’は、S1と互いに素となるSmが見つかれば、L1とL2とを整数としてL1S1L2Sm=1となるL1及びL2を計算して、そのL1及びL2を用いてα1L1αmL2を計算する。α1L1αmL2=θg,hL1S1L2S2=θg,hとなる。また、第二判定部48’は、S1,S2,...,Smの最小公倍数が1になれば、L1,L2,...,Lmを整数としてL1S1L2S2...LmSm=1となるL1,L2,...,Lmを計算して、そのL1,L2,...,Lmを用いてα1L1α2L2...αmLmを計算してもよい。α1L1α2L2...αmLm=θg,hL1S1L2S2...LmSm=θg,hとなる。依頼装置1’と計算装置2’との間の通信を傍受することができる攻撃者Mがいるとしても、依頼装置1’及び計算装置2’との間で通信される情報を、依頼装置1’のみが知る乱数例えば、r1,r2で撹乱することにより、攻撃者Mから秘匿することができる。また、依頼装置1’及び計算装置2’との間で通信される情報は依頼装置1’のみが知るr1,r2等の乱数で撹乱されているため、計算装置2’は、依頼装置1’が最終的に計算しようとするθg,hはもちろんのこと、その入力であるg及びhをも知ることはできない。したがって、計算装置2’は信頼することができる計算機である必要はなく、双準同型写像を計算するためのシステムの構成要件を緩和することができる。また、信頼することができる計算機は一般に高価であり運用に費用を要するが、計算装置2’が信頼することができる計算機である必要ないため、双準同型写像を計算するためのシステムの構築及び運用のコストを削減することができる。≪ν’1/σ=θg,μhとなる理由について≫まず、randomizablesamplerと呼ばれる確率変数SXdについて説明する。w∈Fに関する誤差Xのrandomizablesamplerである確率変数SXdは、SXd=wdXである。dは自然数である。ここで、R1,R2,R1’及びR2’を乱数として、計算装置がgdμgR1及びμhR2を用いて行う計算の計算結果をBgdμgR1,μhR2計算装置が依頼装置に返す計算結果をzとすると、z=BgdμgR1,μhR2である。とし、群Fに値を持つ確率変数XをX=BμgR’1,μhR’21/R’2θμgR’1,μh-1と定義すると、SXd=z1/R2ν-R1は、θg,μhに関する誤差Xのrandomizablesamplerとなる。SXd=z1/R2ν-R1=BgdμgR1,μhR21/R2θμg,μh-R1=XθgdμgR1,μhθμgR1,μh-1=Xθgd,μhθμgR1,μhθμgR1,μh-1=θg,μhdXであるためである。上記式展開において、X=BμgR’1,μhR’21/R’2θμgR’1,μh-1=BgdμgR1,μhR21/R2θgdμgR1,μh-1であり、BgdμgR1,μhR21/R2=XθgdμgR1,μhであるという性質を用いている。この性質は、R1,R2,R1’及びR2’が乱数であることに基づく。ここで、SX1の実現値をθg,μh1x1と表記し、SXdの実現値をθg,μhdx2と表記するとして、SX1の実現値のd乗=SXdの実現値、すなわちθg,μh1x1d=θg,μhdx2となるのは、x1及びx2が群Fの単位元efのときである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。x1が群Fの単位元efのとき、SX1の実現値=θg,μh1x1=θg,μhとなる。上記実施形態の代理計算システムは、このrandomizablesamplerの性質を用いている。ステップS11’からステップS111’の処理がSX1の実現値θg,μh1x1の計算に対応している。実際には、SX1の実現値自体は計算していないが、同処理により得られるr2,z1ν-r1r2を用いて、z1ν-r1r2を1/r2乗すると、z1ν-r1r21/r2=z11/r2ν-r1となり、SX1の実現値θg,μh1x1となる。同様に、ステップS112’からステップS123’の処理がSXd1の実現値θg,μhd1x2の計算に対応している。また、ステップS124’の処理が、SX1の実現値のd1乗=SXd1、すなわちθg,μh1x1d1=θg,μhd1x2であるかどうかの判定に対応している。ステップS124で用いる判定条件w1^t2s2s1-1は、w1^t2s2s1-1=w2⇔w11/s1t2=w21/s2⇔z11/r2ν-r1d1=z21/r5ν-r4⇔θg,μh1x1d1=θg,μhd1x2⇔SX1の実現値のd1乗=SXd1の実現値であるためである。ここで、定義よりs1=r2、w1=z1ν-r1r2、t2=d1、s2=r5、w2=z2ν-r4r5である。さらに、ステップS125’におけるσ及びν’が、θg,μhに対応している。上記したようにSX1の実現値のd1乗=SXd1の実現値のとき、ν’1/σ=w11/s1=z11/r2ν-r1=θg,μh1x1=θg,μhであるためである。≪w3^s3-1=θg,hとなる理由について≫R1,R2,R1’及びR2’を乱数として、計算装置がgR1及びhdμhR2を用いて行う計算の計算結果をBgR1,hdμhR2計算装置が依頼装置に返す計算結果をzとすると、z=BgR1,hdμhR2である。とし、群Fに値を持つ確率変数XをX=BgR’1,μhR’21/R’1θg,μhR’2-1と定義すると、SXd=z1/R1ν’-R2は、θg,hに関する誤差Xのrandomizablesamplerとなる。SXd=z1/R1ν’-R2=BgR1,hdμhR21/R1θg,μh-R2=Xθg,hdμhR2θg,μhR2-1=Xθg,hdθg,μhR2θg,μhR2-1=θg,hdXであるためである。上記式展開において、X=BgR’1,μhR’21/R’1θg,μhR’2-1=BgR1,μhR21/R1θg,hdμhR2-1であり、BgR1,hdμhR21/R1=Xθg,hdμhR2であるという性質を用いている。この性質は、R1,R2,R1’及びR2’が乱数であることに基づく。ここで、SX1の実現値をSX1=θg,h1x1と表記し、SXdの実現値をSXd=θg,hdx2と表記するとして、SX1の実現値のd乗=SXd、すなわちθg,h1x1d=θg,hdx2となるのは、x1及びx2が群Fの単位元efのときである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。x1が群Fの単位元efのとき、SX1の実現値=θg,h1x1=θg,hとなる。上記実施形態の代理計算システムは、このrandomizablesamplerの性質を用いている。ステップS21’からステップS211’の処理がSX1の実現値θg,h1x1の計算に対応している。実際には、SX1の実現値自体は計算していないが、同処理により得られるr6,z3ν’-r6r7を用いて、z3ν’-r6r7を1/r6乗すると、z3ν’-r6r71/r6=z31/r6ν’-r7となり、SX1の実現値θg,h1x1となる。同様に、ステップS212’からステップS223’の処理がSXd2の実現値θg,hd2x2の計算に対応している。また、ステップS224’の処理が、SX1の実現値のd2乗=SXd2の実現値、すなわちθg,h1x1d2=θg,hd2x2であるかどうかの判定に対応している。ステップS224’で用いる判定条件w3^t4s4s3-1=w4は、w3^t4s4s3-1=w4⇔w31/s3t4=w41/s4⇔z31/r6ν’-r7d2=z41/r9ν’-r10⇔θg,h1x1d2=θg,hd2x2⇔SX1の実現値のd2乗=SXd2の実現値であるためである。ここで、定義よりs3=r6、w3=z3ν’-r6r7、t4=d2、s4=r9、w4=z4ν’-r9r10である。さらに、ステップS225’におけるw3^s3-1が、θg,hに対応している。上記したようにSX1の実現値のd2乗=SXd2の実現値のとき、w3^s3-1=z3ν’-r6r7^r6-1=z31/r6ν’-r7=θg,h1x1=θg,hであるためである。[第五実施形態]第五実施形態の代理計算システムは、ステップS13’、ステップS110’及びステップS111’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。第一入力情報計算部13’は、g1=μgr1gではなく、g1=gr1で定義される第一入力情報を計算するステップS13’。第一リスト情報計算部15’は、z1ν-r1r2ではなく、乱数r1及び乱数r2を用いてr1r2を計算して、その計算結果を第一リスト記憶部16’に送るステップS110’。第一リスト記憶部16’には、情報の組r2,z1ν-r1r2ではなく、計算されたr1r2と計算装置2’から受信したz1∈Fとから構成される情報の組r1r2,z1が記憶されるステップS111’。第四実施形態のステップS110’では、z1ν-r1r2という群Fのべき演算を行う必要があったが、第五実施形態のステップS110’ではr1r2の計算を行っておりべき演算の回数が1回減っている。このように、べき演算の回数を減らすことにより演算の効率性を増すことができる。また、群G、群Hにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。[第六実施形態]第六実施形態の代理計算システムは、ステップS24’、ステップS210’及びステップS211’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。第六入力情報計算部34’は、h3=μhr7σhではなく、h3=hr7で定義される第六入力情報h3を計算するステップS24’。第三リスト情報計算部35’は、z3ν’-r6r7ではなく、乱数r6及び乱数r7を用いてr6r7を計算するステップS210’。第三リスト記憶部36’には、情報の組r6,z3ν’-r6r7ではなく、計算されたr6r7と計算装置2’から受信したz3∈Fとから構成される情報の組r6r7,z3が記憶されるステップS211’。第四実施形態のステップS210’では、z3ν’-r6r7という群Fのべき演算を行う必要があったが、第六実施形態のステップS210’ではr6r7の計算を行っておりべき演算の回数が1回減っている。このように、べき演算の回数を減らすことにより演算の効率性を増すことができる。群G、群Hにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。[第七実施形態]第七実施形態の代理計算システムは、ステップS125’及びステップS214’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。第一判定部28’は、上記の関係を満たす場合には、t1s2をσに代入し、w2をν’に代入するステップS125’。第十乱数生成部42’は、乱数r9を用いて-r9-1を計算してr10とするステップS214’。このように、ν’の定義を変更して、σを計算装置2’にとって推測が困難な乱数とすることにより安全性が増す。また、乱数r9を用いて乱数r10を計算することにより、乱数を生成する回数を減らすことができる。乱数r10が乱数r9により定まるため第八入力情報h4=μhr10σhd2の乱雑性が低下し安全性が損なわれるとも思われるが、第八入力情報h4=μhr10σhd2は乱数r10だけでなく更にσにより撹乱されているため安全性は損なわれない。なお、第七実施形態においては更にステップS22’及びステップS211’を以下のように変更してもよい。第七乱数生成部32’は、乱数r6を用いて-r6-1を計算してr7とするステップS22’。第三リスト記憶部36’には、1と上記計算されたz3ν’-r6r7とから構成される情報の組1,z3ν’-r6r7が記憶されるステップS211’。このように、乱数r6を用いて乱数r7を計算することにより乱数を生成する回数を減らすことができる。群G、群Hにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。[第八実施形態]第八実施形態の代理計算システムは、ステップS113’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。まず、ステップS113’に先立ち、第五乱数生成部22’は乱数r5を生成するステップS114’。第四乱数生成部21’は、乱数r5を用いて-r5-1を計算してr4とするステップS113’。このように、乱数r5を用いて乱数r4を計算することにより乱数を生成する回数を減らすことができる。群Hの任意の元hについて、g∈Gでθg,h=νとなるものを計算することが困難ならば、第四実施形態と比較して安全性は低下しない。[第九実施形態]第九実施形態の代理計算システムは、依頼装置1’が図12に破線で示された事前計算部29’を更に含み、ステップS115’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。事前計算部29’は、第三乱数生成部27’が生成したd1を用いてgd1を計算する。この処理は、ステップS112’の後、ステップS115’の前に行う。第三入力情報計算部23’は、事前計算されたgd1を用いて、g2=μgr4gd1の計算を行うステップS115’。ステップS114’で、判定条件を満たさない場合にはステップS11’からステップS123’の処理が繰り返されるが、この繰り返しの処理においては、事前計算されたgd1を再利用する。すなわち、第三乱数生成部27’は乱数d1を生成せず、第三入力情報計算部23’は事前計算されたgd1を用いて、g2=μgr4gd1の計算を行う。これにより、乱数d1を生成する回数を減らすことができ、g2=μgr4gd1の計算を速く行うことができる。[第十実施形態]第十実施形態の代理計算システムは、依頼装置1’が図13に破線で示された事前計算部49’を更に含み、ステップS216’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。事前計算部49’は、第八乱数生成部47’が生成したd2を用いてhd2を計算する。この処理は、ステップS212’の後、ステップS216’の前に行う。第八入力情報計算部44’は、事前計算されたhd2を用いて、第八入力情報h4=μhr10σhd2の計算を行うステップS116’。ステップS214’で、判定条件を満たさない場合にはステップS21’からステップS223’の処理が繰り返されるが、この繰り返しの処理においては、事前計算されたhd2を再利用する。すなわち、第八乱数生成部47’は乱数d2を生成せず、第八入力情報計算部44’は事前計算されたhd2を用いて、h4=μhr10σhd2の計算を行う。これにより、乱数d2を生成する回数を減らすことができ、h4=μhr10σhd2の計算を速く行うことができる。[第四実施形態から第十実施形態の変形例等]第一乱数生成部11’、第二乱数生成部12’、第三乱数生成部27’、第四乱数生成部21’、第五乱数生成部22’、第六乱数生成部31’、第七乱数生成部32’、第八乱数生成部47’、第九乱数生成部41’及び第十乱数生成部42’のそれぞれは、一様乱数を生成することにより、代理計算システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部11’、第二乱数生成部12’、第三乱数生成部27’、第四乱数生成部21’、第五乱数生成部22’、第六乱数生成部31’、第七乱数生成部32’、第八乱数生成部47’、第九乱数生成部41’及び第十乱数生成部42’のそれぞれは、一様乱数ではない乱数を生成してもよい。リストL1、リストL2に情報の組が追加される毎に、第一判定部28’の処理を行ってもよい。例えば、第二リスト記憶部26’に情報の組d1,r5,z2ν-r4r5が記憶されている場合には、ステップS111’の後に、ステップS124’の処理を行っても良い。同様に、リストL3、リストL4に情報の組が追加される毎に、第二判定部48’の処理を行ってもよい。第四実施形態から第十実施形態は互いに組み合わせることができる。依頼装置1’の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、計算装置2’の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。依頼装置1’及び計算装置2’のそれぞれはコンピュータによって実現することができる。この場合、この装置が有すべき各機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これ装置における各処理機能が、コンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。なお、第一実施形態から第三実施形態と、第四実施形態から第十実施形態とを組み合わせてもよい。例えば、図17に例示するように、第一実施形態から第三実施形態の計算装置2が第四実施形態から第十実施形態の依頼装置1’を備えており、この依頼装置1’を含む計算装置2が、第四実施形態から第十実施形態で説明したのと同様にして計算装置2’を用いて、関数fの計算を行ってもよい。具体的には、計算装置2は計算する必要がある関数fxを計算するために、対応する写像θg,hの値を、計算装置2’を用いて計算する。関数fxに対応する写像θg,hとは、与えられた関数f及びxに対して、関数fxと値が同じ値を出力する写像θg,hである。ある元h∈Hに関して、fx=θx,hという関係がある場合には、fxに対応する写像θがθx,hとなる。例えば、参考文献1に記載されたBoneh-Franklin方式のIDベース暗号において、ある一定のIDに関する復号関数をfとする。この方式のIDベース暗号では、楕円曲線の点がなす有限群G,Hと、ペアリングτ:G×H→Fを用いて構成される。QをGの元とする。IDベース暗号の鍵発行センタの秘密鍵をsとして、公開鍵をP=sQとする。IDベース暗号のパブリックパラメータは、群G,Hの記述と、ペアリングτの記述、Q及びPである。参考文献1DanBonehMattFranklinIdentityBasedEncryptionfromtheWeilPairingCRYPTO2001LNCS2139pp2132292001鍵の発行は以下のようにして行われる。鍵発行センタは、IDに対応して定まるHの元QIDについて、PID=sQIDを計算してIDの保持者に対して通知する。PIDはIDの保持者の秘密鍵である。このとき、復号関数f:G→Fは、fx=τx,PIDで定義される。暗号文の作成、暗号文の復号は以下のようにして行われる。平文mをあるIDについて暗号化するためには、乱数rを生成してQr,mHτPr,QIDを計算し、これを暗号文C1,C2とする。復号するためには、暗号文C1,C2に対して、C2HfC1を計算することで平文が得られる。ただし、ここでHはハッシュ関数、は排他的論理和である。このようなBoneh-Franklin方式のIDベース暗号において、関数fxに対応する写像θは例えばペアリングτを用いて定義される。すなわち、fx=τx,PIDである。計算装置2がICカードや携帯電話であり、秘密情報の抽出が困難であるが、計算能力が限定されている場合に、このように依頼装置及び計算装置を多重にして組み合わせることが有益である。この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。"