"仲介装置とΦ個の情報提供装置φとを有し、φ=1,...,Φ、σφ=1,...,Φ、σφ≠φ、Φが2以上の整数、Gφ,Hφが有限可換群、fφが第一暗号化方式ENCφ,1に則って平文mφを第一暗号化鍵yφ,1で暗号化して得られた群Hφの元である第一暗号文Cφ,1が与えられたとき、当該第一暗号文Cφ,1を、第二暗号化方式ENCφ,2に則って前記平文mφを第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元である第二暗号文fφCφ,1=Cφ,2に変換するための関数、aφ,bφが互いに素である自然数、平文Mφを前記第二暗号化方式ENCφ,2に則って前記第二暗号化鍵yσφ,2で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類CLφMφ、Xφ,1,Xφ,2が群Gφに値を持つ確率変数、xφ,1が確率変数Xφ,1の実現値、xφ,2が確率変数Xφ,2の実現値であり、前記仲介装置が、前記情報提供装置φそれぞれの前記第一暗号文Cφ,1に対応する群Hφの元である第一入力情報τφ,1及び第二入力情報τφ,2を出力する入力情報提供部を含み、前記情報提供装置φのそれぞれが、前記第一入力情報τφ,1を用い、或る確率より大きな確率でfφτφ,1を正しく計算し、得られた演算結果を第一出力情報zφ,1とする第一出力情報生成部と、前記第二入力情報τφ,2を用い、或る確率より大きな確率でfφτφ,2を正しく計算し、得られた演算結果を第二出力情報zφ,2とする第二出力情報生成部と、を含み、前記仲介装置が、さらに前記第一出力情報zφ,1から演算結果uφ=fφCφ,1bφxφ,1を生成する第一計算部と、前記第二出力情報zφ,2から演算結果vφ=fφCφ,1aφxφ,2を生成する第二計算部と、前記演算結果uφに対する値uφaφと前記演算結果vφに対する値vφbφとが互いに同一の暗号文の類CLφMφに属する場合の前記演算結果uφ及び前記演算結果vφと、a’φaφb’φbφ=1を満たす整数a’φ,b’φとに対する、値uφb’φvφa’φを得る処理部と、すべてのφ=1,...,Φについて前記値uφb’φvφa’φが得られた後に、前記値uφb’φvφa’φφ=1,...,Φを出力する最終出力部とを含む、情報提供システム。請求項1の情報提供システムであって、前記仲介装置が、前記自然数aφ,bφの少なくとも一方を選択する自然数選択部を含み、前記第一入力情報τφ,1が前記自然数bφにさらに対応し、前記第二入力情報τφ,2が前記自然数aφにさらに対応する、情報提供システム。請求項1又は2の情報提供システムにおいて、前記入力情報提供部が、前記第一暗号文Cφ,1との関係をかく乱させた情報を前記第一入力情報τφ,1及び前記第二入力情報τφ,2とする、情報提供システム。請求項1から3の何れかの情報提供システムであって、前記関数fφが準同型関数であり、前記入力情報提供部が、群Hφの任意の元hrφ,1を生成する第一乱数生成部と、第一暗号化方式ENCφ,1に則って前記元hrφ,1を前記第一暗号化鍵yφ,1で暗号化して得られた群Hφの元Cφ,1’に対応するCφ,1bφCφ,1’を前記第一入力情報τ1として得る第一入力情報計算部と、群Hφの任意の元hrφ,2を生成する第二乱数生成部と、第一暗号化方式ENCφ,1に則って前記元hrφ,2を前記第一暗号化鍵yφ,1で暗号化して得られた群Hφの元Cφ,1に対応するCφ,1aφCφ,1を前記第二入力情報τ2として得る第二入力情報計算部と、前記第一出力情報計算部は、前記第一入力情報Cφ,1bφCφ,1’を用い、或る確率より大きな確率でfφCφ,1bφCφ,1’を正しく計算し、得られた計算結果を前記第一出力情報zφ,1とし、前記第二出力情報計算部は、前記第二入力情報Cφ,1aφCφ,1を用い、或る確率より大きな確率でfφCφ,1aφCφ,1を正しく計算し、得られた計算結果を第二出力情報zφ,2とし、前記第一計算部は、前記第二暗号化方式ENCφ,2に則って前記元hrφ,1を前記第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元Cφ,2’に対応するzφ,1Cφ,2’-1を前記uφとし、前記第二計算部は、前記第二暗号化方式ENCφ,2に則って前記元hrφ,2を前記第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元Cφ,2に対応するzφ,2Cφ,2-1を前記vφとする、情報提供システム。請求項1から4の何れかの情報提供システムにおいて、前記関数fφが準同型関数、群Gφが群Gφ,1,Gφ,2の直積Gφ,1×Gφ,2、μφ,g1が群Gφ,1の生成元、μφ,g2が群Gφ,2の生成元、sσφ,2が前記第二暗号化鍵yσφ,2に対応する復号鍵、前記第二暗号化鍵yσφ,2がμφ,g2sσφ,2、rφが整数の乱数、前記第二暗号文Cφ,2がμφ,g1rφ,mφyσφ,2rφ、前記値uφaφがcφ,1u,cφ,2u∈Gφ,1×Gφ,2、前記値vφbφがcφ,1v,cφ,2v∈Gφ,1×Gφ,2、eφα,βがα,β∈Gφ,1×Gφ,2に対して有限可換群Gφ,Tの元を与える双線形写像であり、前記処理部は、関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2を満たす場合の前記値uφb’φvφa’φを出力する、情報提供システム。請求項5の情報提供システムであって、Nφが素数ωφと素数ιφの合成数、前記群Gφ,1,Gφ,2がそれぞれ前記合成数Nφを法とした剰余環上で定義された第一楕円曲線Eφ,1上の点からなる部分群、Gφ,1ω,Gφ,2ωが前記素数ωφを法とした剰余体上で定義された第二楕円曲線Eφ,2上の点からなる部分群、Gφ,1ι,Gφ,2ιが前記素数ιφを法とした剰余体上で定義された第三楕円曲線Eφ,3上の点からなる部分群、eφ,ωαω,βωがαω,βω∈Gφ,1ω×Gφ,2ωに対して有限可換群Gφ,Tωの元を与える第二双線形写像、eφ,ιαι,βιがαι,βι∈Gφ,1ι×Gφ,2ιに対して有限可換群Gφ,Tιの元を与える第三双線形写像、HMφが前記第一楕円曲線Eφ,1上の点を前記第二楕円曲線Eφ,2上の点と前記第三楕円曲線Eφ,3上の点とに写す同型写像、HMφ-1が前記同型写像HMφの逆像であり、前記仲介装置は、前記同型写像HMφを用いて前記第一楕円曲線Eφ,1上の点αを前記第二楕円曲線Eφ,2上の点θωαと前記第三楕円曲線Eφ,3上の点θιαとに写し、前記同型写像HMφを用いて前記第一楕円曲線Eφ,1上の点βを前記第二楕円曲線Eφ,2上の点θωβと前記第三楕円曲線Eφ,3上の点θιβとに写し、eφ,ωθωα,θωβ及びeφ,ιθια,θιβを求め、eφ,ωθωα,θωβ及びeφ,ιθια,θιβに対する前記逆像HMφ-1をeφα,βとして求め、前記関係を満たすか否かを判定する判定部をさらに含む、情報提供システム。請求項1から3の何れかの情報提供システムにおいて、前記関数fφが準同型関数、μφ,hが群Hの生成元、Kφ,Hが群Hφの位数、νφ=fφμφ,hであり、前記入力情報提供部は、0以上の自然数の乱数rφ,1を生成する第一乱数生成部と、前記第一入力情報τφ,1としてμφ,hrφ,1Cφ,1bφを計算する第一入力情報計算部と、0以上の自然数の乱数rφ,2を生成する第二乱数生成部と、前記第二入力情報τφ,2としてμφ,hrφ,2Cφ,1aφを計算する第二入力情報計算部と、を含み、前記第一出力情報計算部は、前記第一入力情報μφ,hrφ,1Cφ,1bφを用い、或る確率より大きな確率でfφμφ,hrφ,1Cφ,1bφを正しく計算し、得られた計算結果を前記第一出力情報zφ,1とし、前記第二出力情報計算部は、前記第二入力情報μφ,hrφ,2Cφ,1aφを用い、或る確率より大きな確率でfφμφ,hrφ,2Cφ,1aφを正しく計算し、得られた計算結果を第二出力情報zφ,2とし、前記第一計算部は、zφ,1νφ-rφ,1を計算してその計算結果を前記uφとし、前記第二計算部は、zφ,2νφ-rφ,2を計算してその計算結果を前記vφとする、情報提供システム。請求項7の情報提供システムにおいて、前記第一乱数生成部は、bφ≠1のときに前記乱数rφ,1を生成し、前記第一入力情報計算部は、bφ≠1のときに前記第一入力情報τφ,1として前記μφ,hrφ,1Cφ,1bφを計算し、前記第一出力情報計算部は、bφ≠1のときに前記第一入力情報μφ,hrφ,1Cφ,1bφを用いて得られた前記計算結果を前記第一出力情報zφ,1とし、前記第一計算部が、bφ≠1のときにzφ,1νφ-rφ,1を計算してその計算結果を前記uφとし、前記第二乱数生成部が、aφ≠1のときに前記乱数rφ,2を生成し、前記第二入力情報計算部が、aφ≠1のときに前記第二入力情報τφ,2としてμφ,hrφ,2Cφ,1aφを計算し、前記第二出力情報計算部が、aφ≠1のときに前記第二入力情報μφ,hrφ,2Cφ,1aφを用いて得られた前記計算結果を第二出力情報zφ,2とし、前記第二計算部が、aφ≠1のときにzφ,2νφ-rφ,2を計算してその計算結果を前記vφとし、前記入力情報提供部が、0以上の自然数の乱数rφ,3を生成する第三乱数生成部と、bφ=1のときにCφ,1rφ,3を前記第一入力情報τφ,1とし、aφ=1のときにCφ,1rφ,3を前記第二入力情報τφ,2とする第三入力情報計算部と、を含み、前記情報提供装置が、前記Cφ,1rφ,3を用い、或る確率より大きな確率でfφCφ,1rφ,3を正しく計算し、得られた計算結果を第三出力情報zφ,3とする第三出力情報計算部を含み、前記仲介装置が、bφ=1のときにzφ,31/rφ,3を前記uφとし、aφ=1のときにzφ,31/rφ,3を前記vφとする第三計算部を含む、情報提供システム。請求項1から8の何れかの情報提供システムにおいて、前記演算結果uφのfφCφ,1bφに対する誤差の確率分布が前記自然数bφに依存しない、並びに/若しくは、前記演算結果vφのfφCφ,1aφに対する誤差の確率分布が前記自然数aφに依存しない、又は、前記演算結果uφのfφCφ,1bφに対する誤差の確率分布と区別することができない前記自然数bφに依存しない確率分布が存在する、並びに/若しくは、前記演算結果vφのfφCφ,1aφに対する誤差の確率分布と区別することができない前記自然数aφに依存しない確率分布が存在する、情報提供システム。φ=1,...,Φ、σφ=1,...,Φ、σφ≠φ、Φが2以上の整数、Gφ,Hφが有限可換群、fφが第一暗号化方式ENCφ,1に則って平文mφを第一暗号化鍵yφ,1で暗号化して得られた群Hφの元である第一暗号文Cφ,1が与えられたとき、当該第一暗号文Cφ,1を、第二暗号化方式ENCφ,2に則って前記平文mφを第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元である第二暗号文fφCφ,1=Cφ,2に変換するための関数、aφ,bφが互いに素である自然数、平文Mφを前記第二暗号化方式ENCφ,2に則って前記第二暗号化鍵yσφ,2で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類CLφMφ、Xφ,1,Xφ,2が群Gφに値を持つ確率変数、xφ,1が確率変数Xφ,1の実現値、xφ,2が確率変数Xφ,2の実現値であり、演算結果uφ=fφCφ,1bφxφ,1を生成する第一計算部と、演算結果vφ=fφCφ,1aφxφ,2を生成する第二計算部と、前記演算結果uφに対する値uφaφと前記演算結果vφに対する値vφbφとが互いに同一の暗号文の類CLφMφに属する場合の前記演算結果uφ及び前記演算結果vφと、a’φaφb’φbφ=1を満たす整数a’φ,b’φとに対する、値uφb’φvφa’φを得る処理部と、すべてのφ=1,...,Φについて前記値uφb’φvφa’φが得られた後に、前記値uφb’φvφa’φφ=1,...,Φを出力する最終出力部と、を有する仲介装置。請求項1から9の何れかの情報提供システムが有する情報提供装置。φ=1,...,Φ、σφ=1,...,Φ、σφ≠φ、Φは2以上の整数、Gφ,Hφが有限可換群、fφが第一暗号化方式ENCφ,1に則って平文mφを第一暗号化鍵yφ,1で暗号化して得られた群Hφの元である第一暗号文Cφ,1が与えられたとき、当該第一暗号文Cφ,1を、第二暗号化方式ENCφ,2に則って前記平文mφを第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元である第二暗号文fφCφ,1=Cφ,2に変換するための関数、aφ,bφが互いに素である自然数、平文Mφを前記第二暗号化方式ENCφ,2に則って前記第二暗号化鍵yσφ,2で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類CLφMφ、Xφ,1,Xφ,2が群Gφに値を持つ確率変数、xφ,1が確率変数Xφ,1の実現値、xφ,2が確率変数Xφ,2の実現値であり、仲介装置で、前記情報提供装置φそれぞれの前記第一暗号文Cφ,1に対応する群Hφの元である第一入力情報τφ,1及び第二入力情報τφ,2を出力する入力情報提供ステップと、情報提供装置φのそれぞれで、前記第一入力情報τφ,1を用い、或る確率より大きな確率でfφτφ,1を正しく計算し、得られた演算結果を第一出力情報zφ,1とする第一出力情報生成ステップと、前記情報提供装置φのそれぞれで、前記第二入力情報τφ,2を用い、或る確率より大きな確率でfφτφ,2を正しく計算し、得られた演算結果を第二出力情報zφ,2とする第二出力情報生成ステップと、前記仲介装置で、前記第一出力情報zφ,1から演算結果uφ=fφCφ,1bφxφ,1を生成する第一計算ステップと、前記仲介装置で、前記第二出力情報zφ,2から演算結果vφ=fφCφ,1aφxφ,2を生成する第二計算ステップと、前記仲介装置で、前記演算結果uφに対する値uφaφと前記演算結果vφに対する値vφbφとが互いに同一の暗号文の類CLφMφに属する場合の前記演算結果uφ及び前記演算結果vφと、a’φaφb’φbφ=1を満たす整数a’φ,b’φとに対する、値uφb’φvφa’φを得る処理ステップと、前記仲介装置で、すべてのφ=1,...,Φについて前記値uφb’φvφa’φが得られた後に、前記値uφb’φvφa’φφ=1,...,Φを出力する最終出力ステップと、を有する情報提供方法。φ=1,...,Φ、σφ=1,...,Φ、σφ≠φ、Φは2以上の整数、Gφ,Hφが有限可換群、fφが第一暗号化方式ENCφ,1に則って平文mφを第一暗号化鍵yφ,1で暗号化して得られた群Hφの元である第一暗号文Cφ,1が与えられたとき、当該第一暗号文Cφ,1を、第二暗号化方式ENCφ,2に則って前記平文mφを第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元である第二暗号文fφCφ,1=Cφ,2に変換するための関数、aφ,bφが互いに素である自然数、平文Mφを前記第二暗号化方式ENCφ,2に則って前記第二暗号化鍵yσφ,2で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類CLφMφ、Xφ,1,Xφ,2が群Gφに値を持つ確率変数、xφ,1が確率変数Xφ,1の実現値、xφ,2が確率変数Xφ,2の実現値であり、第一計算部で、演算結果uφ=fφCφ,1bφxφ,1を生成する第一計算ステップと、第二計算部で、演算結果vφ=fφCφ,1aφxφ,2を生成する第二計算ステップと、処理部で、前記演算結果uφに対する値uφaφと前記演算結果vφに対する値vφbφとが互いに同一の暗号文の類CLφMφに属する場合の前記演算結果uφ及び前記演算結果vφと、a’φaφb’φbφ=1を満たす整数a’φ,b’φとに対する、値uφb’φvφa’φを得る処理ステップと、最終出力部で、すべてのφ=1,...,Φについて前記値uφb’φvφa’φが得られた後に、前記値uφb’φvφa’φφ=1,...,Φを出力する最終出力ステップと、を有する仲介方法。請求項12の情報提供方法の第一出力情報生成ステップと第二出力情報生成ステップとを有する情報提供方法。請求項10の仲介装置としてコンピュータを機能させるためのプログラム。請求項11の情報提供装置としてコンピュータを機能させるためのプログラム。しかしながら、GradualReleaseofSecretの場合でも、情報を提供された情報提供装置が自らの情報を提供しない可能性があり、やはり先に情報を提供した情報提供装置が不利益を被る可能性がある。また、情報提供装置間が互いに暗号文を提供した場合であっても、一方の情報提供装置が不正な暗号文を他方の情報提供装置に提供し、当該他方の情報提供装置が不利益を被る可能性もある。このような問題は、暗号文を格納した二つの情報提供装置が当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する場合に限定されたものではなく、複数の情報提供装置が当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する場合に共通する問題である。本発明はこのような点に鑑みてなされたものであり、暗号文を格納した複数の情報提供装置が、当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する場合の持ち逃げ問題を抑制できる技術を提供することを目的とする。本発明では、φ=1,...,Φ、σφ=1,...,Φ、σφ≠φ、Φが2以上の整数、Gφ,Hφが有限可換群、fφが第一暗号化方式ENCφ,1に則って平文mφを第一暗号化鍵yφ,1で暗号化して得られた群Hφの元である第一暗号文Cφ,1が与えられたとき、当該第一暗号文Cφ,1を、第二暗号化方式ENCφ,2に則って平文mφを第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元である第二暗号文fφCφ,1=Cφ,2に変換するための関数、aφ,bφが互いに素である自然数、平文Mφを第二暗号化方式ENCφ,2に則って第二暗号化鍵yσφ,2で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類、Xφ,1,Xφ,2が群Gφに値を持つ確率変数、xφ,1が確率変数Xφ,1の実現値、xφ,2が確率変数Xφ,2の実現値であり、仲介装置とΦ個の情報提供装置φとが次の処理を行う。仲介装置で、情報提供装置φそれぞれの第一暗号文Cφ,1に対応する群Hφの元である第一入力情報τφ,1及び第二入力情報τφ,2を出力する。情報提供装置φのそれぞれで、第一入力情報τφ,1を用い、或る確率より大きな確率でfφτφ,1を正しく計算し、得られた演算結果を第一出力情報zφ,1とし、第二入力情報τφ,2を用い、或る確率より大きな確率でfφτφ,2を正しく計算し、得られた演算結果を第二出力情報zφ,2とする。仲介装置で、第一出力情報zφ,1から演算結果uφ=fφCφ,1bφxφ,1を生成し、第二出力情報zφ,2から演算結果vφ=fφCφ,1aφxφ,2を生成し、演算結果uφに対する値uφaφと演算結果vφに対する値vφbφとが互いに同一の暗号文の類CLφMφに属する場合の演算結果uφ及び演算結果vφと、a’φaφb’φbφ=1を満たす整数a’φ,b’φとに対する、値uφb’φvφa’φを得、すべてのφ=1,...,Φについて値uφb’φvφa’φが得られた後に、値uφb’φvφa’φφ=1,...,Φを出力する。仲介装置で得られた各値uφb’φvφa’φは、それぞれ高い確率で第二暗号化鍵yσφ,2に対応する復号鍵で復号可能な第二暗号文Cφ,2となる。そのため仲介装置は、すべての情報提供装置φφ=1,...,Φにそれぞれ対応する正しい第二暗号文Cφ,2を取得した後に、各第二暗号文Cφ,2を出力しているとみなせる。これにより、第二暗号文Cφ,2を提供すべき情報提供装置が正しい第二暗号文Cφ,2を提供することなく、他の情報提供装置から提供された第二暗号文を取得するといった持ち逃げ問題を抑制できる。すなわち本発明では、暗号文を格納した複数の情報提供装置が、当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する場合の持ち逃げ問題を抑制できる。以下、図面を参照して本発明の実施形態を説明する。[第一実施形態]まず、本発明の第一実施形態を説明する。本形態では、2個の情報提供装置が仲介装置を介し、これらが互いに暗号文の提供を行う例を説明する。すなわち、本発明はφ=1,...,Φ、σφ=1,...,Φ、σφ≠φ、Φが2以上の整数である場合に適用可能であるが、以下ではΦ=2、σ1=2、σ2=1の例を説明する。ただし、この例は本発明を限定するものではない。<構成>図1に例示するように、第一実施形態の情報提供システム1は、例えば、仲介装置11と2個の情報提供装置12-1,12-2とを有する。各装置は情報のやり取りが可能なように構成される。例えば、各装置は伝送線やネットワークや可搬型記録媒体などを経由した情報のやり取りが可能とされている。本形態では、情報提供装置12-1が、第一暗号化方式ENC1,1に則って平文m1を第一暗号化鍵y1,1で暗号化して得られた第一暗号文C1,1を、第二暗号化方式ENC1,2に則って平文m1を第二暗号化鍵y2,2で暗号化して得られる第二暗号文C1,2に再暗号化する能力を仲介装置11に与える。また、情報提供装置12-2が、第一暗号化方式ENC2,1に則って平文m2を第一暗号化鍵y2,1で暗号化した第一暗号文C2,1を、第二暗号化方式ENC2,2に則って平文m2を第二暗号化鍵y1,2で暗号化した第二暗号文C2,2に再暗号化する能力を仲介装置11に与える。仲介装置11は、提供された能力を用い、情報提供装置12-1の第一暗号文C1,1を第二暗号文C1,2に再暗号化し、情報提供装置12-2の第一暗号文C2,1を第二暗号文C2,2に再暗号化する。その後、仲介装置11は、第二暗号文C1,2を情報提供装置12-2に出力し、第二暗号文C2,2を情報提供装置12-1に出力する。情報提供装置12-1は、第二復号鍵s1,2を用いて第二暗号文C2,2を復号して平文m2を取得可能である。情報提供装置12-2は、第二復号鍵s1,1を用いて第二暗号文C1,2を復号して平文m1を取得可能である。図2に例示するように、第一実施形態の仲介装置11は、例えば、自然数記憶部1101と自然数選択部1102と整数計算部1103と入力情報提供部1104と第一計算部1105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部1108と第二べき乗計算部1109と第二リスト記憶部1110と判定部1111と処理部1112と最終出力部1113と制御部1114とを有する。仲介装置11は、制御部1114の制御のもとで各処理を実行する。仲介装置11の例は、特別なプログラムが読み込まれたCPUcentralprocessingunitやRAMrandom-accessmemoryを備えた公知又は専用のコンピュータや、サーバ装置やゲートウェイ装置やカードリーダライタ装置や携帯電話などの計算機能と記憶機能とを備えた機器などである。図3に例示するように、第一実施形態の情報提供装置12-φφ=1,2は、例えば、それぞれ、第一出力情報計算部1201-φと第二出力情報計算部1202-φと鍵記憶部1204-φと暗号文記憶部1205-φと出力部1206-φと復号部1207-φと制御部1208-φとを有する。情報提供装置12-φは、制御部1208-φの制御のもとで各処理を実行する。情報提供装置12-φの例は、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータや、携帯電話などの計算機能と記憶機能とを備えた機器や、ICカードやICチップなどの耐タンパ性モジュールなどである。<処理の前提>Gφ,Hφが巡回群などの有限可換群であり、Xφ,1,Xφ,2が群Gφに値を持つ確率変数であり、xφ,1が確率変数Xφ,1の実現値であり、xφ,2が確率変数Xφ,2の実現値であり、fφが群Hφの元である第一暗号文Cφ,1を群Gφの元である第二暗号文fφCφ,1=Cφ,2に変換するための関数であるとする。ここで、第一暗号文Cφ,1は第一暗号化方式ENCφ,1に則って平文mφを第一暗号化鍵yφ,1で暗号化して得られた暗号文であり、第二暗号文Cφ,2は第二暗号化方式ENCφ,2に則って平文mφを第二暗号化鍵yσφ,2で暗号化して得られる暗号文である。第一暗号化方式ENCφ,1や第二暗号化方式ENCφ,2は、公開鍵暗号方式であってもよいし、共通鍵暗号方式であってもよい。また、第一暗号化方式ENCφ,1や第二暗号化方式ENCφ,2は、確率暗号方式であってもよいし、確定暗号方式であってもよい。第一暗号化方式ENCφ,1と第二暗号化方式ENCφ,2とが同一の暗号化方式であってもよいし、これらが異なる暗号化方式であってもよい。また、すべての第一暗号化方式ENCφ,1φ=1,...,Φが互いに同一の暗号化方式であってもよいし、少なくとも一部のφ’≠φに対する第一暗号化方式ENCφ’,1が他の第一暗号化方式ENCφ,1と相違してもよい。また、すべての第二暗号化方式ENCφ,2φ=1,...,Φが互いに同一の暗号化方式であってもよいし、少なくとも一部のφ’≠φに対する第二暗号化方式ENCφ’,2が他の第二暗号化方式ENCφ,2と相違してもよい。第一暗号化方式ENCφ,1や第二暗号化方式ENCφ,2の例は、準同型関数を暗号化関数及び復号関数とする暗号化方式である。そのような例は、ElGamal暗号方式参考文献1:TaherElgamalAPublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithmsIEEETransactionsonInformationTheoryvIT31n41985pp469472orCRYPTO84pp1018SpringerVerlagや、RSA暗号方式参考文献2:RLRivestAShamirandLAdelmanAMethodforObtainingDigitalSignatureandPublickeyCryptsystemsMITLaboratoryforComputerScienceThechnicalMemoLCSTM82April41977などの公開鍵暗号方式などである。また、Gφ=Hφであってもよいし、Gφ≠Hφであってもよい。すべての群Gφφ=1,...,Φが互いに同一であってもよいし、少なくとも一部のφ’≠φに対する群Gφ’が他の群Gφと相違してもよい。また、すべての群Hφφ=1,...,Φが互いに同一であってもよいし、少なくとも一部のφ’≠φに対する群Hφ’が他の群Hφと相違してもよい。また、以下では群Gφ,Hφ上の演算を乗法的に表現する。第一暗号化鍵yφ,1には第一復号鍵sφ,1が対応し、第二暗号化鍵yσφ,2には第二復号鍵sσφ,2が対応する。第一暗号化方式ENCφ,1が公開鍵暗号方式である場合、第一暗号化鍵yφ,1は公開鍵であり、第一復号鍵sφ,1は秘密鍵である。一方、第一暗号化方式ENCφ,1が共通鍵暗号方式である場合、第一暗号化鍵yφ,1及び第一復号鍵は共通鍵である。第二暗号化方式ENCφ,2が公開鍵暗号方式である場合、第二暗号化鍵yσφ,2は公開鍵であり、第二復号鍵sσφ,2は秘密鍵である。一方、第二暗号化方式ENCφ,2が共通鍵暗号方式である場合、第二暗号化鍵yσφ,2及び第二復号鍵sσφ,2は共通鍵である。yφ,1=yφ,2であってもよいし、yφ,1≠yφ,2であってもよい。sφ,1=sφ,2であってもよいし、sφ,1≠sφ,2であってもよい。また、平文Mφを第二暗号化方式ENCφ,2に則って第二暗号化鍵yσφ,2で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類CLφMφと呼ぶ。ここでaφ,bφは互いに素な自然数であり、自然数とは0以上の整数を表す。CLφMφとCLφ’Mφ’φ’≠φとは互いに異なる類である。同一の暗号文の類CLφMφには、同一の平文Mφを第二暗号化鍵yσφ,2でそれぞれ暗号化して得られる可能性がある各暗号文が属する。例えば、第二暗号化方式ENCφ,2がElGamal暗号方式のような確率暗号方式である場合、同一の平文Mφと暗号化鍵yσφ,2との組に対して複数の暗号文Cφ,2が対応するため、同一の暗号文の類CLφMφにはaφ,bφの組みごとに複数の要素が属する。一方、例えば、第二暗号化方式ENCφ,2がRSA暗号方式のような確定暗号方式である場合、同一の平文Mφと暗号化鍵yσφ,2との組に対して暗号文Cφ,2が一義的に定まるため、同一の暗号文の類CLφMφにはaφ,bφの組みごとに一つの要素のみが属する。aφ,bφの組みごとに同一の暗号文の類CLφMφに一つの要素のみが属する場合、二つの値が同一の暗号文の類CLφMφに属することと当該二つの値が等しいこととが等価となる。すなわち、第二暗号化方式が確定暗号方式である場合、二つの値が同一の暗号文の類CLφMφに属するかの判定は当該二つの値が等しいかを判定することで行うことができる。また、仲介装置11図2の自然数記憶部1101に、互いに素である2つの自然数aφ,bφの組aφ,bφが複数種類記憶されているものとする。Iφを群Gφの位数未満の2つの自然数の組で互いに素なものの集合とすると、自然数記憶部1101にはIφの部分集合Sφに対応する自然数aφ,bφの組aφ,bφが記憶されていると考えることができる。また、第一復号鍵sφ,1、第二復号鍵sφ,2、及び第二暗号化鍵yσφ,2が情報提供装置12-φ図3の鍵記憶部1204-φに格納され、第一暗号文Cφ,1∈Hφが情報提供装置12-φの暗号文記憶部1205-φに格納されているものとする。<処理>図6に例示するように、まず、仲介装置11図2の制御部1114がφ=1とするステップS111。次に、仲介装置11は情報提供装置12-φとの間でφについての自己訂正処理を実行するステップS112。以下にφについての自己訂正処理を説明する。[φについての自己訂正処理]まず、情報提供装置12-φ図3の出力部1206-φが、暗号文記憶部1205-φから読み出された第一暗号文Cφ,1を出力する。第一暗号文Cφ,1は仲介装置11図2の入力情報提供部1104に入力される。第一暗号文Cφ,1は、例えば、情報提供装置12-σφによって選択されたものである。また、この処理は複数の第一暗号文Cφ,1について実行されてもよいし、既に第一暗号文Cφ,1が入力情報提供部1104に入力されている場合にはこの処理が省略されてもよい。図7に例示するように、第一暗号文Cφ,1が入力情報提供部1104に入力された仲介装置11の自然数選択部1102は、自然数記憶部1101に記憶された複数の自然数の組aφ,bφから1つの自然数の組aφ,bφをランダムに読み込む。読み込まれた自然数の組aφ,bφ少なくとも一部の情報は、整数計算部1103、入力情報提供部1104、第一べき乗計算部1106及び第二べき乗計算部1109に送られるステップS1100。整数計算部1103は、送られた自然数の組aφ,bφを用いて、a’φaφb’φbφ=1の関係を満たす整数a’φ,b’φを計算する。自然数aφ,bφは互いに素であるため、a’φaφb’φbφ=1の関係を満たす整数a’φ,b’φをEuclidの互除法などの公知のアルゴリズムによって計算することができる。自然数の組a’φ,b’φの情報は、処理部1112に送られるステップS1101。制御部1114は、t=1とするステップS1102。入力情報提供部1104は、入力された第一暗号文Cφ,1にそれぞれ対応する群Hφの元である第一入力情報τφ,1及び第二入力情報τφ,2を生成して出力する。好ましくは、第一入力情報τφ,1及び第二入力情報τφ,2はそれぞれ第一暗号文Cφ,1との関係をかく乱させた情報である。これにより、仲介装置11は、第一暗号文Cφ,1を情報提供装置12-φに対して隠蔽できる。例えば、情報提供装置12-φが複数種類の第一暗号文Cφ,1を出力していた場合、仲介装置11は、どの第一暗号文Cφ,1に関する処理を行っているのかを情報提供装置12-φに対して隠蔽できる。また、好ましくは、本形態の第一入力情報τφ,1は自然数選択部1102で選択された自然数bφにさらに対応し、第二入力情報τφ,2は自然数選択部1102で選択された自然数aφにさらに対応する。これにより、情報提供装置12-φから提供された再暗号化能力を仲介装置11が高い精度で評価することができるステップS1103。図8に例示するように、第一入力情報τφ,1は情報提供装置12-φ図3の第一出力情報計算部1201-φに入力され、第二入力情報τφ,2は第二出力情報計算部1202-φに入力されるステップS1200。第一出力情報計算部1201-φは、第一入力情報τφ,1と鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2とを用い、或る確率より大きな確率でfφτφ,1を正しく計算し、得られた計算結果を第一出力情報zφ,1とするステップS1201。第二出力情報計算部1202-φは、第二入力情報τφ,2と鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2を用い、或る確率より大きな確率でfφτφ,2を正しく計算し、得られた演算結果を第二出力情報zφ,2とするステップS1202。なお、関数fφの例は、第一暗号化方式ENCφ,1に則って第一復号鍵sφ,1で暗号文を復号して得られる値を、第二暗号化方式ENCφ,2に則って第二暗号化鍵yσφ,2で暗号化するための準同型関数である。また、或る確率は100未満の確率である。或る確率の例は無視することができない確率であり、無視することができない確率の例は、セキュリティパラメータkについての広義単調増加関数である多項式を多項式ψkとした場合の1/ψk以上の確率である。すなわち、第一出力情報計算部1201-φや第二出力情報計算部1202-φは、意図的又は意図的ではない誤差を含んだ計算結果を出力し得る。言い換えると、第一出力情報計算部1201-φでの計算結果がfφτφ,1の場合もあればfφτφ,1でない場合もあり、第二出力情報計算部1202-φでの計算結果がfφτφ,2の場合もあればfφτφ,2でない場合もある。第一出力情報計算部1201-φは第一出力情報zφ,1を出力し、第二出力情報計算部1202-φは第二出力情報zφ,2を出力するステップS1203。図7に戻り、第一出力情報zφ,1は仲介装置11図2の第一計算部1105に入力され、第二出力情報zφ,2は第二計算部1108に入力される。これらの第一出力情報zφ,1及び第二出力情報zφ,2が、情報提供装置12-φから仲介装置11に与えられた再暗号化能力に相当するステップS1104。第一計算部1105は、第一出力情報zφ,1から演算結果uφ=fφCφ,1bφxφ,1を生成する。ここで、fφCφ,1bφxφ,1を生成計算するとは、fφCφ,1bφxφ,1と定義される式の値を計算することである。式fφCφ,1bφxφ,1の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。演算結果uφは第一べき乗計算部1106に送られるステップS1105。第一べき乗計算部1106はuφ’=uφaφを計算する。計算結果uφとその計算結果に基づいて計算されたuφ’との組uφ,uφ’は、第一リスト記憶部1107に記憶されるステップS1106。判定部1111は、第一リスト記憶部1107に記憶された組uφ,uφ’及び第二リスト記憶部1110に記憶された組vφ,vφ’の中で、uφ’とvφ’とが互いに同一の暗号文の類CLφMφに属するものがあるかを判定する。必ずしもMφを計算できる必要はなく、またMφ=mφであることまでは判定できなくてもよい以下同様。言い換えると、判定部1111は、同一の暗号文の類CLφMφに属するuφ’とvφ’との組があるか判定する。例えば、第二暗号化方式ENCφ,2が確定暗号方式の場合、判定部1111は、uφ’=vφ’であるかを判定するステップS1107。もし、第二リスト記憶部1110に組vφ,vφ’が記憶されていない場合には、このステップS1107の処理を行わずに、次のステップS1108の処理を行う。同一の暗号文の類CLφMφに属するuφ’とvφ’との組があった場合には、ステップS1114に進む。同一の暗号文の類CLφMφに属するuφ’とvφ’との組がなかった場合には、ステップS1108に進む。ステップS1108では、第二計算部1108が、第二出力情報zφ,2から演算結果vφ=fφCφ,1aφxφ,2を生成する。演算結果vφは第二べき乗計算部1109に送られるステップS1108。第二べき乗計算部1109はvφ’=vφbφを計算する。計算結果vφとその計算結果に基づいて計算されたvφ’との組vφ,vφ’は、第二リスト記憶部1110に記憶されるステップS1109。判定部1111は、第一リスト記憶部1107に記憶された組uφ,uφ’及び第二リスト記憶部1110に記憶された組vφ,vφ’の中で、uφ’とvφ’とが互いに同一の暗号文の類CLφMφに属するものがあるかを判定する。例えば、第二暗号化方式ENCφ,2が確定暗号方式の場合、判定部1111は、uφ’=vφ’であるかを判定するステップS1110。同一の暗号文の類CLφMφに属するuφ’とvφ’との組があった場合には、ステップS1114に進む。同一の暗号文の類CLφMφに属するuφ’とvφ’との組がなかった場合には、ステップS1111に進む。ステップS1111では、制御部1114がt=Tであるか判定するステップS1111。Tは予め定められた自然数である。Tはすべてのφについて同一値であってもよいし、φについての自己訂正処理でのTの値と、φ’σ’≠σ,σ’=1,...,Φについての自己訂正処理でのTの値が相違する場合があってもよい。t=Tであれば、処理部1112が、計算をすることができなかった旨の情報、例えば記号⊥を出力してステップS1113、処理を終える。t=Tでない場合には、制御部1114は、tを1だけインクリメント、すなわちt=t1t1を新たなtとしてステップS1112、ステップS1103に戻る。計算をすることができなかった旨の情報この例では記号⊥は、情報提供装置12-φが正しく計算を行う信頼性がTで定められる基準を下回るということを意味する。言い換えれば、T回の繰り返しで正しい演算を行うことができなかったということを意味する。ステップS1114では、処理部1112が、同一の暗号文の類CLφMφに属すると判定されたuφ’とvφ’との組に対応するuφ及びvφを用いてuφb’φvφa’φを計算して、出力して処理を終えるステップS1114。このように計算されたuφb’φvφa’φは、高い確率で第二暗号文fφCφ,1=Cφ,2∈Gφとなる高い確率でuφb’φvφa’φ=fφCφ,1となる理由については後述する。よって、少なくともφについての自己訂正処理を複数回繰り返し、ステップS1114で得られた値のうち最も頻度の高いuφb’φvφa’φを選択すれば、選択されたuφb’φvφa’φが第2暗号文Cφ,2であることの信頼度確率などは所定値以上となる。たとえば、セキュリティパラメータをkとするとき、k回の自己訂正処理を繰り返せば、無視できる確率をのぞいて正しい計算を行うことができる。また、後述するように、設定によっては圧倒的な確率でuφb’φvφa’φ=fφCφ,1となる。その場合にはステップS1114で得られたuφb’φvφa’φが第2暗号文Cφ,2であることの信頼度は必ず所定値以上となる[φについての自己訂正処理]についての説明終わり。図6に戻り、仲介装置11図2の処理部1112は、φについての自己訂正処理で得られたuφb’φvφa’φが第2暗号文Cφ,2であることの信頼度が所定値以上であるかを判定するステップS113。ここで得られたuφb’φvφa’φが第2暗号文Cφ,2であることの信頼度が所定値以上でなかったと判定された場合、φを更新することなくステップS112に戻ってステップS112の処理が再び実行される。例えば、ステップS1113で計算をすることができなかった旨の情報が出力された場合には、信頼度が所定値以上でなかったと判定される。また、ステップS1114でuφb’φvφa’φが得られたとしても、φについての自己訂正処理を複数回繰り繰り返さなくてはuφb’φvφa’φの信頼度を評価できない場合には、信頼度を評価できる所定の回数だけφについての自己訂正処理が繰り返されるまで、信頼度が所定値以上でなかったと判定される。一方、得られたuφb’φvφa’φが第2暗号文Cφ,2であることの信頼度が所定値以上であったと判定された場合、処理部1112は、信頼度が所定値以上のuφb’φvφa’φを出力し、それが最終出力部1113に入力される。例えば、ステップS1114でuφb’φvφa’φが得られた場合にその信頼度が必ず所定値以上となる設定の場合には、ステップS1114でuφb’φvφa’φが最終出力部1113に入力される。また、φについての自己訂正処理を複数回繰り繰り返さなくてはuφb’φvφa’φの信頼度を評価できない場合であって、かつ、信頼度を評価できる所定の回数だけφについての自己訂正処理が繰り返された場合には、それらの自己訂正処理で得られたuφb’φvφa’φのうち最も頻度の高いものが最終出力部1113に入力される。最終出力部1113に入力されたuφb’φvφa’φは図示していない最終出力部1113内の記憶部に格納され、ステップS114に進む。ステップS114では、制御部1114がφ=Φであるかを判定するステップS114。ここでφ=Φでなければ、制御部1114はφを1だけインクリメント、すなわちφ=φ1φ1を新たなφとしてステップS115、ステップS112に戻って[φについての自己訂正処理]が実行される。一方、φ=Φであれば、最終出力部1113は、最終出力部1113内の記憶部図示せずに格納されたすべての値uφb’φvφa’φφ=1,...,Φを出力する。すなわち、最終出力部1113は、上述のようにすべてのφ=1,...,Φについて値uφb’φvφa’φが計算された後に、各uφb’φvφa’φφ=1,...,Φを出力する。これにより、情報提供装置12-1及び12-2による持ち逃げ問題を抑制できる。また、仲介装置11が第一復号鍵sφ,1や第二復号鍵sφ,2を利用可能でない場合、仲介装置11に平文mφの情報が知られることはないステップS116。各uφb’φvφa’φは、それぞれ第2暗号文Cφ,2として情報提供装置12-σφに入力される。本形態では、uσφb’σφvσφa’σφが第二暗号文Cσφ,2として情報提供装置12-φ図3の復号部1207-φに入力される。復号部1207-φは、鍵記憶部1204-φから第二復号鍵sφ,2を読み出し、それを用いて第2暗号文Cσφ,2を復号し、得られた復号結果を出力する。≪高い確率でuφb’φvφa’φ=fφCφ,1となる理由について≫Xφを群Gφに値を持つ確率変数とする。wφ∈Gφについて、要求を受けるたびに確率変数Xφに従った標本xφ’に対応するwφxφ’を返すものを、wφについて誤差Xφを持つ標本器samplerと呼ぶ。wφ∈Gφについて、自然数aφが与えられるたびに確率変数Xφに従った標本xφ’に対応するwφaφxφ’を返すものを、wφについて誤差Xφを持つ乱数化可能標本器randomizablesamplerと呼ぶ。乱数化可能標本器はaφ=1として用いられれば標本器として機能する。本実施形態の入力情報提供部1104と第一出力情報計算部1201-φと第一計算部1105との組み合わせが、fφCφ,1について誤差Xφ,1を持つ乱数化可能標本器第一乱数化可能標本器と呼ぶであり、入力情報提供部1104と第二出力情報計算部1202-φと第二計算部1108との組み合わせが、fφCφ,1について誤差Xφ,2を持つ乱数化可能標本器第二乱数化可能標本器と呼ぶである。uφ’とvφ’とが互いに同一の暗号文の類CLφMφに属するのは、第一乱数化可能標本器がuφ=fφCφ,1bφを正しく計算しており、第二乱数化可能標本器がvφ=fφCφ,1aφを正しく計算しているxφ,1及びxφ,2が群Gφの単位元eφ,gである可能性が高いことを発明者は見出した。説明の簡略化の観点から、この証明は第五実施形態で行う。第一乱数化可能標本器がuφ=fφCφ,1bφを正しく計算しており、第二乱数化可能標本器がvφ=fφCφ,1aφを正しく計算しているときxφ,1及びxφ,2が群Gφの単位元eφ,gであるとき、uφb’φ=fφCφ,1bφxφ,1b’φ=fφCφ,1bφeφ,gb’φ=fφCφ,1bφb’φとなり、vφa’φ=fφCφ,1aφxφ,2a’φ=fφCφ,1aφeφ,ga’φ=fφCφ,1aφa’φとなる。そのため、第二暗号化方式が確定暗号方式なのであればuφb’φvφa’φ=fφCφ,1bφb’φaφa’φ=fφCφ,1となる。一方、第二暗号化方式が確率暗号方式であったとしてもfφCφ,1が準同型関数なのであれば、uφb’φvφa’φ=fφCφ,1bφb’φaφa’φ=fφCφ,1となる。また、q1,q2∈Iについて、i=1,2の各々について関数πiをπiq1,q2=qiで定義する。さらに、L=min♯π1S,♯π2Sとする。♯は、集合の位数である。群Gφが巡回群などの有限可換群や位数の計算が困難な群であるときには、仲介装置11が⊥以外を出力するときの出力がfφCφ,1ではない確率は、無視できる程度の誤差の範囲で高々T2L/♯S程度と期待することができる。もしL/♯Sが無視できる量でTが多項式オーダー程度の量であれば、仲介装置11は圧倒的な確率で正しいfφCφ,1を出力する。L/♯Sが無視できる量になるようなSの例には、例えばS={1,d|d∈[2,|Gφ|-1]}がある。[第二実施形態]第二実施形態の情報提供システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した例である。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。以下の説明において、同一の参照番号が付された部分は同一の機能を持つものとし、同一の参照番号が付されたステップは同一の処理を表すものとする。<構成>図1に例示するように、第二実施形態の情報提供システム2は、仲介装置11が仲介装置21に置換され、情報提供装置12-φが情報提供装置22-φに置換されたものである。図2に例示するように、第二実施形態の仲介装置21は、例えば、自然数記憶部1101と自然数選択部1102と整数計算部1103と入力情報提供部2104と第一計算部2105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部2108と第二べき乗計算部1109と第二リスト記憶部1110と判定部1111と処理部1112と最終出力部1113と制御部1114とを有する。図4に例示するように、本形態の入力情報提供部2104は、例えば、第一乱数生成部2104aと第一入力情報計算部2104bと第二乱数生成部2104cと第二入力情報計算部2104dとを有する。図3に例示するように、第二実施形態の情報提供装置22-φφ=1,2は、例えば、それぞれ、第一出力情報計算部2201-φと第二出力情報計算部2202-φと鍵記憶部1204-φと暗号文記憶部1205-φと出力部1206-φと復号部1207-φと制御部1208-φとを有する。<処理の前提>第二実施形態では、関数fφを準同型関数とし、群Hφの生成元をμφ,h、群Hφの位数をKφ,H、νφ=fφμφ,hとする。その他の前提は、仲介装置11が仲介装置21に置換され、情報提供装置12-φが情報提供装置22-φに置換されている以外、第一実施形態と同一である。<処理>図6~図8に例示するように、第二実施形態の処理は第一実施形態のステップS113のステップS1103~S1105,S1108,S1200~S1203が、それぞれ、ステップS213のステップS2103~S2105,S2108,S2200~S2203に置換されたものである。以下ではステップS213のステップS2103~S2105,S2108,S2200~S2203の処理のみを説明する。《ステップS2103の処理》仲介装置21図2の入力情報提供部2104は、入力された第一暗号文Cφ,1にそれぞれ対応する第一入力情報τφ,1及び第二入力情報τφ,2を生成して出力する図7/ステップS2103。以下、図9を用いて本形態のステップS2103の処理を説明する。第一乱数生成部2104a図4は、0以上Kφ,H未満の自然数の一様乱数rφ,1を生成する。生成された乱数rφ,1は、第一入力情報計算部2104b及び第一計算部2105に送られるステップS2103a。第一入力情報計算部2104bは、入力された乱数rφ,1と第一暗号文Cφ,1と自然数bφとを用いて第一入力情報τφ,1=μφ,hrφ,1Cφ,1bφを計算するステップS2103b。第二乱数生成部2104cは、0以上Kφ,H未満の自然数の一様乱数rφ,2を生成する。生成された乱数rφ,2は、第二入力情報計算部2104d及び第二計算部2108に送られるステップS2103c。第二入力情報計算部2104dは、入力された乱数rφ,2と第一暗号文Cφ,1と自然数aφとを用いて第二入力情報τφ,2=μφ,hrφ,2Cφ,1aφを計算するステップS2103d。第一入力情報計算部2104b及び第二入力情報計算部2104dは、以上のように生成した第一入力情報τφ,1及び第二入力情報τφ,2を出力するステップS2103e。なお、本形態の第一入力情報τφ,1及び第二入力情報τφ,2は、それぞれ、乱数rφ,1,rφ,2によって第一暗号文Cφ,1との関係をかく乱させた情報である。これにより、仲介装置22は、第一暗号文Cφ,1を情報提供装置22-φに対して隠蔽できる。また、本形態の第一入力情報τφ,1は自然数選択部1102で選択された自然数bφにさらに対応し、第二入力情報τφ,2は自然数選択部1102で選択された自然数aφにさらに対応する。これにより、情報提供装置22-φから提供された再暗号化能力を仲介装置21が高い精度で評価することができる。《ステップS2200~S2203の処理》図8に例示するように、まず、第一入力情報τφ,1=μφ,hrφ,1Cφ,1bφが情報提供装置22-φ図3の第一出力情報計算部2201-φに入力され、第二入力情報τφ,2=μφ,hrφ,2Cφ,1aφが第二出力情報計算部2202-φに入力されるステップS2200。第一出力情報計算部2201-φは、第一入力情報τφ,1=μφ,hrφ,1Cφ,1bφと鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2とを用い、或る確率より大きな確率でfφμφ,hrφ,1Cφ,1bφを正しく計算し、得られた計算結果を第一出力情報zφ,1とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部2201-φでの計算結果がfφμφ,hrφ,1Cφ,1bφとなる場合もあれば、fφμφ,hrφ,1Cφ,1bφとならない場合もある。なお、関数fφの例は、第一暗号化方式ENCφ,1に則って第一復号鍵sφ,1で暗号文を復号して得られる値を、第二暗号化方式ENCφ,2に則って第二暗号化鍵yσφ,2で暗号化するための準同型関数である。このような関数fφに対応する第一暗号化方式ENCφ,1や第二暗号化方式ENCφ,2の例はRSA暗号方式であるステップS2201。第二出力情報計算部2202-φは、第二入力情報τφ,2=μφ,hrφ,2Cφ,1aφと鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2とを用い、或る確率より大きな確率でfφμφ,hrφ,2Cφ,1aφを正しく計算し、得られた計算結果を第二出力情報zφ,2とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部2202-φでの計算結果がfφμφ,hrφ,2Cφ,1aφとなる場合もあれば、fφμφ,hrφ,2Cφ,1aφとならない場合もあるステップS2202。第一出力情報計算部2201-φは第一出力情報zφ,1を出力し、第二出力情報計算部2202-φは第二出力情報zφ,2を出力するステップS2203。《ステップS2104及びS2105の処理》図7に戻り、第一出力情報zφ,1は仲介装置21図2の第一計算部2105に入力され、第二出力情報zφ,2は第二計算部2108に入力される。これらの第一出力情報zφ,1及び第二出力情報zφ,2が、情報提供装置22-φから仲介装置21に与えられた再暗号化能力に相当するステップS2104。第一計算部2105は、入力された乱数rφ,1及び第一出力情報zφ,1を用いてzφ,1νφ-rφ,1を計算してその計算結果をuφとする。計算結果uφは、第一べき乗計算部1106に送られる。ここで、uφ=zφ,1νφ-rφ,1=fφCφ,1bφxφ,1となる。すなわち、zφ,1νφ-rφ,1は、fφCφ,1について誤差Xφ,1を持つ乱数化可能標本器の出力となる。その理由については後述するステップS2105。《ステップS2108の処理》第二計算部2108は、入力された乱数rφ,2及び第二出力情報zφ,2を用いてzφ,2νφ-rφ,2を計算してその計算結果をvφとする。計算結果vφは、第二べき乗計算部1109に送られる。ここで、vφ=zφ,2νφ-rφ,2=fφCφ,1aφxφ,2となる。すなわち、zφ,2νφ-rφ,2は、fφCφ,1について誤差Xφ,2を持つ乱数化可能標本器の出力となる。その理由については後述するステップS2108。≪zφ,1νφ-rφ,1,zφ,2νφ-rφ,2がfφCφ,1についてそれぞれ誤差Xφ,1,Xφ,2を持つ乱数化可能標本器の出力となる理由について≫cを自然数、R及びR’を乱数として、情報提供装置22-φがμφ,hRCφ,1cを用いて行う計算の計算結果をBμφ,hRCφ,1cとする。すなわち、第一出力情報計算部2201-φや第二出力情報計算部2202-φが仲介装置21に返す計算結果をzφ=Bμφ,hRCφ,1cとする。さらに、群Gφに値を持つ確率変数XφをXφ=Bμφ,hR’fφμφ,hR’-1と定義する。このとき、zφνφ-R=Bμφ,hRCφ,1cfμφ,h-R=Xφfφμφ,hRCφ,1cfφμφ,h-R=Xφfφμφ,hRfφCφ,1cfφμφ,h-R=fφCφ,1cXφとなる。すなわち、zφνφ-Rは、fφCφ,1について誤差Xφを持つ乱数化可能標本器の出力となる。上記式展開において、Xφ=Bμφ,hR’fφμφ,hR’-1=Bμφ,hRCφ,1cfφμφ,hRCφ,1c-1であり、Bμφ,hRCφ,1c=Xφfφμφ,hRCφ,1cであるという性質を用いている。この性質は、関数fφが準同型関数であり、R及びR’が乱数であることに基づく。したがって、aφ,bφが自然数、rφ,1,rφ,2が乱数であることを考慮すると、同様に、zφ,1ν-rφ,1,zφ,2ν-rφ,2がfφCφ,1についてそれぞれ誤差Xφ,1,Xφ,2を持つ乱数化可能標本器の出力となるのである。[第三実施形態]第三実施形態は第二実施形態の変形例であり、aφ=1やbφ=1のときに前述した標本器によってuφ又はvφの値を計算する。一般に乱数化可能標本器よりも標本器の計算量は小さい。aφ=1やbφ=1のときに乱数化可能標本器に代わり、標本器が計算を行うことで、情報提供システムの計算量を小さくすることができる。以下、第一実施形態及び第二実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。<構成>図1に例示するように、第三実施形態の情報提供システム3は、仲介装置21が仲介装置31に置換され、情報提供装置22-φが情報提供装置32-φに置換されたものである。図2に例示するように、第三実施形態の仲介装置31は、例えば、自然数記憶部1101と自然数選択部1102と整数計算部1103と入力情報提供部2104と第一計算部2105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部2108と第二べき乗計算部1109と第二リスト記憶部1110と判定部1111と処理部1112と最終出力部1113と制御部1114と第三計算部3109とを有する。図3に例示するように、第三実施形態の情報提供装置32-φは、例えば、第一出力情報計算部2201-φと第二出力情報計算部2202-φと鍵記憶部1204-φと暗号文記憶部1205-φと出力部1206-φと復号部1207-φと制御部1208-φと第三出力情報計算部3203-φとを有する。<処理>次に本形態の処理を説明する。第二実施形態との相違点を説明する。図6~図8に例示するように、第三実施形態の処理は第二実施形態のステップS213のステップS2103~S2105,S2108,S2200~S2203が、それぞれ、ステップS313のステップS3103~S3105,S3108,S2200~S2203及びS3205~S3209に置換されたものである。以下ではステップS313のステップS3103~S3105,S3108,S2200~S2203及びS3205~S3209の処理を中心に説明する。《ステップS3103の処理》仲介装置31図2の入力情報提供部3104は、入力された第一暗号文Cφ,1にそれぞれ対応する第一入力情報τφ,1及び第二入力情報τφ,2を生成して出力する図7/ステップS3103。以下、図9を用いて本形態のステップS3103の処理を説明する。制御部1114図2は、自然数選択部1102で選択された自然数aφ,bφに応じて入力情報提供部3104を制御する。制御部1114でbφが1であるかが判定されステップS3103a、bφ≠1であると判定された場合、前述のステップS2103a及びS2103bの処理が実行され、ステップS3103gに進む。一方、ステップS3103aでbφ=1であると判定された場合、第三乱数生成部3104eが、0以上Kφ,H未満の自然数の乱数rφ,3を生成する。生成された乱数rφ,3は第三入力情報計算部3104f及び第三計算部3109に送られるステップS3103b。第三入力情報計算部3104fは、入力された乱数rφ,3と第一暗号文Cφ,1とを用いてCφ,1rφ,3を計算し、これを第一入力情報τφ,1とするステップS3103c。その後、ステップS3103gに進む。ステップS3103gでは、制御部1114でaφが1であるかが判定されステップS3103g、aφ≠1であると判定された場合、前述のステップS2103c及びステップS2103dの処理が実行される。一方、ステップS3103gでaφ=1であると判定された場合、第三乱数生成部3104eが、0以上Kφ,H未満の自然数の乱数rφ,3を生成する。生成された乱数rφ,3は第三入力情報計算部3104fに送られるステップS3103h。第三入力情報計算部3104fは、入力された乱数rφ,3と第一暗号文Cφ,1とを用いてCφ,1rφ,3を計算し、これを第二入力情報τφ,2とするステップS3103i。第一入力情報計算部2104b、第二入力情報計算部2104d、第三入力情報計算部3104fは、以上のように生成した第一入力情報τφ,1及び第二入力情報τφ,2を対応する自然数aφ,bφの情報とともに出力するステップS3103e。なお、本形態の第一入力情報τφ,1及び第二入力情報τφ,2は、それぞれ、乱数rφ,1,rφ,2,rφ,3によって第一暗号文Cφ,1との関係をかく乱させた情報である。これにより、仲介装置31は、第一暗号文Cφ,1を情報提供装置32-φに対して隠蔽できる。《S2200~S2203及びS3205~S3209の処理》以下、図8を用いて本形態のS2200~S2203及びS3205~S3209の処理を説明する。制御部1208-φ図3は、入力された自然数aφ,bφに応じ、第一出力情報計算部2201-φ、第二出力情報計算部2202-φ、及び第三出力情報計算部3203-φを制御する。制御部1208-φの制御に基づき、bφ≠1の場合の第一入力情報τφ,1=μφ,hrφ,1Cφ,1bφは情報提供装置32-φ図3の第一出力情報計算部2201-φに入力され、aφ≠1の場合の第二入力情報τφ,2=μφ,hrφ,2Cφ,1aφは第二出力情報計算部2202-φに入力される。また、bφ=1の場合の第一入力情報τφ,1=Cφ,1rφ,3やaφ=1の場合の第二入力情報τφ,2=Cφ,1rφ,3は第三出力情報計算部3203-φに入力されるステップS3200。制御部1114でbφが1であるかが判定されステップS3205、bφ≠1であると判定された場合、前述のステップS2201の処理が実行される。その後、制御部1114でaφが1であるかが判定されステップS3208、aφ≠1であると判定された場合、前述したステップS2202の処理が実行されてステップS3203に進む。一方、ステップS3208でaφ=1であると判定された場合、第三出力情報計算部3203-φは、第二入力情報τφ,2=Cφ,1rφ,3と鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2とを用い、或る確率より大きな確率でfφCφ,1rφ,3を正しく計算し、得られた計算結果を第三出力情報zφ,3とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部3203-φでの計算結果がfφCφ,1rφ,3となる場合もあれば、fφCφ,1rφ,3とならない場合もあるステップS3209。その後、ステップS3203に進む。また、ステップS3205でbφ=1であると判定された場合、第三出力情報計算部3203-φは、第二入力情報τφ,1=Cφ,1rφ,3と鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2とを用い、或る確率より大きな確率でfφCφ,1rφ,3を正しく計算し、得られた計算結果を第三出力情報zφ,3とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部3203-φでの計算結果がfφCφ,1rφ,3となる場合もあれば、fφCφ,1rφ,3とならない場合もあるステップS3206。その後、制御部1114でaφが1であるかが判定されステップS3207、aφ=1であると判定された場合にはステップS3203に進み、aφ≠1であると判定された場合にはステップS2202に進む。ステップS3203では、第一出力情報zφ,1を生成した第一出力情報計算部2201-φは第一出力情報zφ,1を出力し、第二出力情報zφ,2を生成した第二出力情報計算部2202-φは第二出力情報zφ,2を出力し、第三出力情報zφ,3を生成した第三出力情報計算部3202は第三出力情報zφ,3を出力するステップS3203。《ステップS3104及びS3105の処理》図7に戻り、制御部1114の制御のもと、第一出力情報zφ,1は仲介装置31図2の第一計算部2105に入力され、第二出力情報zφ,2は第二計算部2108に入力され、第三出力情報zφ,3は第三計算部3109に入力されるステップS3104。bφ≠1であれば、第一計算部2105が、前述のステップS2105の処理によってuφを生成し、bφ=1であれば、第三計算部3109が、zφ,31/rφ,3を計算してその計算結果をuφとする。計算結果uφは第一べき乗計算部1106に送られる。ここで、bφ=1の場合、uφ=zφ,31/rφ,3=fφCφ,1xφ,3となる。すなわち、zφ,31/rφ,3は、fφCφ,1について誤差Xφ,3を持つ標本器となる。その理由については後述するステップS3105。《ステップS3108の処理》aφ≠1であれば、第二計算部2108が、前述のステップS2108の処理によってvφを生成し、aφ=1であれば、第三計算部3109が、zφ,31/rφ,3を計算してその計算結果をvφとする。計算結果vφは第二べき乗計算部1109に送られる。ここで、aφ=1の場合、vφ=zφ,31/rφ,3=fφCφ,1xφ,3となる。すなわち、zφ,31/rφ,3は、fφCφ,1について誤差Xφ,3を持つ標本器となる。その理由については後述するステップS3108。なお、zφ,31/rφ,3の計算、すなわちzφ,3のべき乗根の計算が困難な場合には、次のようにしてuφ及び/又はvφを計算してもよい。第三計算部3109は、乱数rφ,3とその乱数rφ,3に基づいて計算されたzφ,3の組を順次α1,β1,α2,β2,...,αm,βm,...として図示していない記憶部に記憶する。mは自然数である。第三計算部3109は、α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φとしてもよい。≪zφ,31/rφ,3がfφCφ,1について誤差Xφ,3を持つ標本器となる理由について≫Rを乱数として、情報提供装置32-φがCφ,1Rを用いて行う計算の計算結果をBCφ,1Rとする。すなわち、第一出力情報計算部2201-φや第二出力情報計算部2202-φや第三出力情報計算部3203-φが仲介装置31に返す計算結果をzφ=BCφ,1Rとする。さらに、群Gφに値を持つ確率変数XφをXφ=BCφ,1R1/RfφCφ,1-1と定義する。このとき、zφ1/R=BCφ,1R1/R=XφfφCφ,1=fφCφ,1Xφとなる。すなわち、zφ1/Rは、fφCφ,1について誤差Xφを持つ標本器となる。上記式展開において、Xφ=BCφ,1R1/RfφCφ,1R-1であり、BCφ,1R1/R=XφfφCφ,1Rであるという性質を用いている。この性質は、Rが乱数であることに基づく。したがって、rφ,3が乱数であることを考慮すると、同様に、zφ1/RがfφCφ,1について誤差Xφ,3を持つ標本器となるのである。[第四実施形態]第四実施形態の情報提供システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した他の例である。具体的には、第二暗号化方式ENCφ,2がElGamal暗号方式であり、関数fφが準同型関数である例を示す。なお、第一暗号化方式ENCφ,1には特に限定はなく、第一暗号化方式ENCφ,1はElGamal暗号方式のような確率暗号方式であってもよいし、RSA暗号方式のような確定暗号方式であってもよい。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。図1に例示するように、第四実施形態の情報提供システム4は、仲介装置11が仲介装置41に置換され、情報提供装置12-φが情報提供装置42-φに置換されたものである。図2に例示するように、第四実施形態の仲介装置41は、例えば、自然数記憶部1101と自然数選択部1102と整数計算部1103と入力情報提供部4104と第一計算部4105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部4108と第二べき乗計算部1109と第二リスト記憶部1110と判定部4111と処理部1112と最終出力部1113と制御部1114とを有する。図5に例示するように、本形態の入力情報提供部4104は、例えば、第一乱数生成部4104aと第一入力情報計算部4104bと第二乱数生成部4104cと第二入力情報計算部4104dと鍵記憶部4104eとを有する。図3に例示するように、第四実施形態の情報提供装置42-φは、例えば、第一出力情報計算部4201-φと第二出力情報計算部4202-φと鍵記憶部1204-φと暗号文記憶部1205-φと出力部1206-φと復号部1207-φと制御部1208-φとを有する。<処理の前提>第四実施形態では、群Gφが巡回群などの有限可換群Gφ,1,Gφ,2の直積Gφ,1×Gφ,2、μφ,g1が群Gφ,1の生成元、μφ,g2が群Gφ,2の生成元、第二暗号化鍵yσφ,2がμφ,g2sσφ,2、第二暗号文Cφ,2がμφ,g1rφ,mφyσφ,2rφ∈Gφ,1×Gφ,2、rφが整数の乱数、値uφaφがcφ,1u,cφ,2u∈Gφ,1×Gφ,2、値vφbφがcφ,1v,cφ,2v∈Gφ,1×Gφ,2である。Gφ,1=Gφ,2であってもよいし、Gφ,1≠Gφ,2であってもよい。また、前述のように第一暗号化方式ENCφ,1には限定はないが、例えば第一暗号化方式ENCφ,1がElGamal暗号方式である場合には、群Hφが巡回群などの有限可換群Hφ,1,Hφ,2の直積Hφ,1×Hφ,2、r’φが整数の乱数、μφ,h1が群Hφ,1の生成元、μφ,h2が群Hφ,2の生成元、第一暗号化鍵yφ,1がμφ,h2sφ,1、第一暗号文Cφ,1がμφ,h1r’φ,mφyφ,1r’φ∈Hφ,1×Hφ,2となる。Hφ,1=Hφ,2であってもよいし、Hφ,1≠Hφ,2であってもよい。なお、Α=α1,α2∈Gφ,1×Gφ,2,Β=β1,β2∈Gφ,1×Gφ,2,及びεが自然数である場合、Αεはα1ε,α2εを表し、Α-εはα1-ε,α2-εを表し、ΑΒはα1β1,α2β2を表す。同様に、εが自然数、Α=α1,α2∈Hφ,1×Hφ,2,Β=β1,β2∈Hφ,1×Hφ,2である場合、Αεはα1ε,α2εを表し、Α-εはα1-ε,α2-εを表し、ΑΒはα1β1,α2β2を表す。また、eφα,βをα,β∈Gφ,1×Gφ,2に対して巡回群などの有限可換群Gφ,Tの元を与える双線形写像とする。双線形写像の例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数やアルゴリズムである参考文献3:AlfredJMenezes,ELLIPTICCURVEPUBLICKEYCRYPTOSYSTEMS,KLUWERACADEMICPUBLISHERS,ISBN0792393686,pp6181や、参考文献4:RFC5091IdentityBasedCryptographyStandard1SupersingularCurveImplementationsoftheBFandBB1Cryptosystems等参照。また、第一暗号化鍵yφ,1及び第二暗号化鍵yσφ,2が、仲介装置11の入力情報提供部4104が含む鍵記憶部4104eに格納されているものとする。<処理>図6~図8に例示するように、第四実施形態の処理は第一実施形態のステップS113のステップS1103~S1105,S1107,S1108,S1110,S1200~S1203が、それぞれ、ステップS413のステップS4103~S4105,S4107,S4108,S4110,S4200~S4203に置換されたものである。以下ではステップS413のステップS4103~S4105,S4107,S4108,S4110,S4200~S4203の処理のみを説明する。《ステップS4103の処理》仲介装置41図2の入力情報提供部4104は、入力された第一暗号文Cφ,1に対応する第一入力情報τφ,1及び第二入力情報τφ,2を生成して出力する図7/ステップS4103。以下、図10を用いて本形態のステップS4103の処理を説明する。第一乱数生成部4104a図5は、群Hφの任意の元hrφ,1∈Hφを生成する。本形態では群Hφからランダムかつ一様に元hrφ,1が選択される一様乱数。生成された元hrφ,1は、第一入力情報計算部4104b、及び第一計算部4105に送られるステップS4103a。第一入力情報計算部4104bは、自然数選択部1102で選択された自然数bφ、第一暗号文Cφ,1、元hrφ,1、及び鍵記憶部4104eから抽出した第一暗号化鍵yφ,1を用い、第一入力情報τφ,1としてCφ,1bφCφ,1’を計算するステップS4103b。なお、Cφ,1’は、第一暗号化方式ENCφ,1に則って元hrφ,1を第一暗号化鍵yφ,1で暗号化して得られた群Hφの元である。第二乱数生成部4104cは、群Hφの任意の元hrφ,2∈Hφを生成する。本形態では群Hφからランダムかつ一様に元hrφ,2が選択される一様乱数。生成された元hrφ,2は、第二入力情報計算部4104d、及び第二計算部4108に送られるステップS4103c。第二入力情報計算部4104bは、自然数選択部1102で選択された自然数aφ、第一暗号文Cφ,1、元hrφ,2、及び鍵記憶部4104eから抽出した第一暗号化鍵yφ,1を用い、第二入力情報τφ,2としてCφ,1aφCφ,1を計算するステップS4103d。なお、Cφ,1は、第一暗号化方式ENCφ,1に則って元hrφ,2を第一暗号化鍵yφ,1で暗号化して得られた群Hφの元である。第一入力情報計算部4104bは、以上のように生成した第一入力情報τφ,1=Cφ,1bφCφ,1’を出力する。第二入力情報計算部4104dは、以上のように生成した第二入力情報τφ,2=Cφ,1aφCφ,1を出力するステップS4103e。《ステップS4200~S4203の処理》図8に例示するように、まず、第一入力情報τφ,1=Cφ,1bφCφ,1’が情報提供装置42-φ図3の第一出力情報計算部4201-φに入力され、第二入力情報τφ,2=Cφ,1aφCφ,1が第二出力情報計算部4202-φに入力されるステップS4200。第一出力情報計算部4201-φは、第一入力情報τφ,1=Cφ,1bφCφ,1’と鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2とを用い、或る確率より大きな確率でfφCφ,1bφCφ,1’を正しく計算し、計算結果を第一出力情報zφ,1とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部4201-φでの計算結果がfφCφ,1bφCφ,1’となる場合もあれば、fφCφ,1bφCφ,1’とならない場合もあるステップS4201。なお、本形態の関数fφは、第一暗号化方式ENCφ,1に則って第一復号鍵sφ,1で暗号文を復号して得られる値をElGamal暗号方式に則って第二暗号化鍵yσφ,2で暗号化するための準同型関数である。例えば、第一暗号化方式ENCφ,1も第二暗号化方式ENCφ,2もElGamal暗号方式で或る場合、関数fφは、ElGamal暗号方式に則って第一復号鍵sφ,1で暗号文を復号して得られる値を、ElGamal暗号方式に則って第二暗号化鍵yσφ,2で暗号化するための準同型関数である。第二出力情報計算部4202-φは、第二入力情報τφ,2=Cφ,1aφCφ,1と鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2とを用い、或る確率より大きな確率でfφCφ,1aφCφ,1を正しく計算可能であり、得られた計算結果を第二出力情報zφ,2とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部4202-φでの計算結果がfφCφ,1aφCφ,1となる場合もあれば、fφCφ,1aφCφ,1とならない場合もあるステップS4202。第一出力情報計算部4201-φは第一出力情報zφ,1を出力し、第二出力情報計算部4202-φは第二出力情報zφ,2を出力するステップS4203。《ステップS4104及びS4105の処理》図7に戻り、第一出力情報zφ,1は仲介装置41図2の第一計算部4105に入力され、第二出力情報zφ,2は第二計算部4108に入力されるステップS4104。第一計算部4105は、入力された第一出力情報zφ,1、元hrφ,1、及び鍵記憶部4104e図5から読み出した第二暗号化鍵yσφ,2を用い、zφ,1Cφ,2’-1を計算してその計算結果をuφとするステップS4105。なお、Cφ,2’は、第二暗号化方式ENCφ,2に則って元hrφ,1を第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元である。計算結果uφは、第一べき乗計算部1106に送られる。ここで、uφ=zφ,1Cφ,2’-1=fφCφ,1bφxφ,1となる。すなわち、zφ,1Cφ,2’-1は、fφCφ,1について誤差Xφ,1を持つ乱数化可能標本器の出力となる。その理由については後述する。《ステップS4108の処理》第二計算部4108は、入力された第二出力情報zφ,2、元hrφ,2、及び鍵記憶部4104e図5から読み出した第二暗号化鍵yσφ,2を用い、zφ,2Cφ,2-1を計算してその計算結果をvφとする。なお、Cφ,2は、第二暗号化方式ENCφ,2に則って元hrφ,2を第二暗号化鍵yσφ,2で暗号化して得られる群Gφの元である。計算結果vφは、第二べき乗計算部1109に送られる。ここで、vφ=zφ,2Cφ,2-1=fφCφ,1aφxφ,2となる。すなわち、zφ,2Cφ,2-1は、fφCφ,1について誤差Xφ,2を持つ乱数化可能標本器の出力となる。その理由については後述する。《ステップS4107の処理》判定部4111は、第一リスト記憶部1107に記憶された組uφ,uφ’及び第二リスト記憶部1110に記憶された組vφ,vφ’の中で、uφ’とvφ’とが互いに同一の暗号文の類CLφMφに属するものがあるかを判定する。本形態の判定部4111は、uφ’=cφ,1u,cφ,2u及びvφ’=cφ,1v,cφ,2vに対して、関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2を満たすものがあるかを判定するステップS4107。uφ’とvφ’がこの関係を満たすかを判定することで、uφ’とvφ’とが互いに同一の暗号文の類CLφMφに属することを判定できる理由については後述する。もし、第二リスト記憶部1110に組vφ,vφ’が記憶されていない場合には、このステップS4107の処理を行わずに、次のステップS1108の処理を行う。同一の暗号文の類CLφMφに属するuφ’とvφ’との組があった場合上記の関係を満たすuφ’とvφ’との組があった場合には、ステップS1114に進む。同一の暗号文の類CLφMφに属するuφ’とvφ’との組がなかった場合には、ステップS4108に進む。《ステップS4110の処理》判定部4111は、第一リスト記憶部1107に記憶された組uφ,uφ’及び第二リスト記憶部4110に記憶された組vφ,vφ’の中で、uφ’とvφ’とが互いに同一の暗号文の類CLφMφに属するものがあるかを判定する。本形態の判定部4111は、uφ’=cφ,1u,cφ,2u及びvφ’=cφ,1v,cφ,2vに対して、関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2を満たすものがあるかを判定するステップS4110。同一の暗号文の類CLφMφに属するuφ’とvφ’との組があった場合には、ステップS1114に進む。同一の暗号文の類CLφMφに属するuφ’とvφ’との組がなかった場合には、ステップS1111に進む。なお、特殊な群Gφ,1,Gφ,2や双線形写像eφを用いた場合、ステップS4107及びS4110の処理を仲介装置41に実行させることができる者を制限できる。この詳細については後述する。《zφ,1Cφ,2’-1,zφ,2Cφ,2-1がfφCφ,1についてそれぞれ誤差Xφ,1,Xφ,2を持つ乱数化可能標本器の出力となる理由について》任意の元hrφ,1を固定して考えると、第二暗号文Cφ,2=μφ,g1rφ,mφyσφ,2rφにおける乱数rφを確率空間とする確率分布について、以下の関係が成り立つ。ただし、Dφ,1sφ,1,xφは、第一暗号化方式ENCφ,1に則って第一暗号文xφを第一復号鍵sφ,1で復号するための関数を表す。rを乱数として、あるr2が存在してfφxφaφCφ,1Cφ,2-1=μφ,g1rφ,Dφ,1sφ,1,xφaφhrφ,2yσφ,2rφ×μφ,g1r2,hrφ,2yσφ,2r2-1となるから、fφxφaφCφ,1Cφ,2-1=μφ,g1rφ-r2,Dφ,1sφ,1,xφaφyσφ,2r-r2となる。したがって、確率分布fφxφaφCφ,1Cφ,2-1は確率分布fxφaと等しい。Cφ,1を確率変数とみなして、群Gφに値を持つ確率変数Xφ,2=zφ,2fφxφaφCφ,1-1を考えると、zφ,2Cφ,2-1=zφ,2fφxφaφCφ,1-1fφxφaφCφ,1Cφ,2-1であるから、この確率分布はxφ,2∈Xφ,2についてxφ,2fφxφaφの確率分布と等しい。同様に、zφ,1Cφ,2’-1の確率分布はxφ,1∈Xφ,1についてfφxφbφxφ,1の確率分布と等しい。Cφ,1を確率変数とみなすとき、xφaφCφ,1の分布はCφ,1の分布と等しいから、確率変数Xφ,2の確率分布はaφに依存しない。同様に、確率変数Xφ,1の確率分布はbφに依存しない。したがって、zφ,1Cφ,2’-1,zφ,2Cφ,2-1はfφCφ,1についてそれぞれ誤差Xφ,1,Xφ,2を持つ乱数化可能標本器の出力となる。《関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2を満たすかを判定することで、uφ’とvφ’とが互いに同一の暗号文の類CLφMφに属することを判定できる理由》uφ’とvφ’とが互いに平文Mφ=mφに対応する同一の暗号文の類CLφMφに属すると仮定する。この場合には第一乱数化可能標本器がuφ=fφCφ,1bφを正しく計算しており、第二乱数化可能標本器がvφ=fφCφ,1aφを正しく計算しているxφ,1及びxφ,2が群Gφの単位元eφ,gである可能性が高い。よって、uφ’=μφ,g1r’’φ,mφyσφ,2r’’φかつvφ’=μφ,g1r’’’φ,mφyσφ,2r’’’φである可能性が高い。ただし、r’’φ及びr’’’φは、ElGamal暗号方式の乱数成分と自然数選択部1102で選択された自然数の組とによって定まる値である。その場合、双線形写像eφの性質から、uφ’=cφ,1u,cφ,2uに対してeφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,mφyσφ,2r’’φ/eφμφg1r’’φ,yσφ,2=eφμφ,g1,mφyσφ,2r’’φ/eφμφ,g1,yσφ,2r’’φ=eφμφ,g1,mφeφμφ,g1,yσφ,2/eφμφ,g1,yσφ,2=eφμφ,g1,mφを満たす可能性が高い。また、vφ’=cφ,1v,cφ,2vに対してeφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2=eφμφ,g1,mφyσφ,2r’’’φ/eφμφ,g1r’’’φ,yσφ,2=eφμφ,g1,mφyσφ,2r’’’φ/eφμφ,g1,yσφ,2r’’’φ=eφμφ,g1,mφeφμφ,g1,yσφ,2/eφμφ,g1,yσφ,2=eφμφ,g1,mφを満たす可能性が高い。よって、uφ’とvφ’とが互いに同一の暗号文の類CLφMφに属する場合、関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2を満たす可能性が高い。次に、uφ’とvφ’とが互いに異なる暗号文の類に属すると仮定する。すなわち、uφ’が平文mφ,uに対応する暗号文の類CLφmφ,uに属し、vφ’が平文mφ,vmφ,v≠mφ,uに対応する暗号文の類CLφmφ,vに属すると仮定する。すると、uφ’=μφ,g1r’’φ,mφ,uyσφ,2r’’φxφ,1かつvφ’=μφ,g1r’’’φ,mφ,vyσφ,2r’’’φxφ,2となる。そのため、uφ’=cφ,1u,cφ,2uに対してeφ,μφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,mφ,uxφ,1を満たし、vφ’=cφ,1v,cφ,2vに対してeφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2=eφμφ,g1,mφ,vxφ,2を満たす。よって、uφ’とvφ’とが互いに異なる暗号文の類に属する場合、関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2≠eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2となる可能性が高い。《特殊な群Gφ,1,Gφ,2や双線形写像eφ》群Gφ,1,Gφ,2や双線形写像eφの構成を以下のように限定した場合、ステップS4107及びS4110の処理を仲介装置41に実行させることができる者を制限することができる。以下にその詳細を述べる。この特殊な例では、Nφが素数ωφと素数ιφの合成数、群Gφ,1,Gφ,2がそれぞれ合成数Nφを法とした剰余環Z/NφZ上で定義された第一楕円曲線Eφ,1上の点からなる部分群、Gφ,1ω,Gφ,2ωが素数ωφを法とした剰余体Z/ωφZ上で定義された第二楕円曲線Eφ,2上の点からなる部分群、Gφ,1ι,Gφ,2ιが素数ιφを法とした剰余体Z/ιφZ上で定義された第三楕円曲線Eφ,3上の点からなる部分群、eφα,βがα,β∈Gφ,1×Gφ,2に対して巡回群などの有限可換群Gφ,Tの元を与える双線形写像、eφ,ωαω,βωがαω,βω∈Gφ,1ω×Gφ,2ωに対して巡回群などの有限可換群Gφ,Tωの元を与える第二双線形写像、eφ,ιαι,βιがαι,βι∈Gφ,1ι×Gφ,2ιに対して巡回群などの有限可換群Gφ,Tιの元を与える第三双線形写像、HMφが第一楕円曲線Eφ,1上の点を第二楕円曲線Eφ,2上の点と第三楕円曲線Eφ,3上の点とに写す同型写像、HMφ-1が同型写像HMφの逆像である。この例の場合、双線形写像eφα,βは剰余環Z/NφZ上で定義された第一楕円曲線Eφ,1上で定義される。しかしながら、剰余環上で定義された楕円曲線上で定義された双線形写像eφα,βを多項式時間で計算する方法は知られておらず、多項式時間で計算可能な剰余環上で定義された楕円曲線上で定義された双線形写像eφα,βの構成方法も知られていない参考文献5:AlexanderWDentandStevenDGalbraithHiddenPairingsandTrapdoorDDHGroupsANTS2006LNCS4076pp4364512006。このような設定の場合、判定部4111は、双線形写像eφを剰余環Z/NφZ上で直接計算して関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2を満たすか否かを判定することができない。一方、剰余体Z/ωφZ,Z/ιφZ上で定義された楕円曲線上で定義されたeφ,ωαω,βωやeφ,ιαι,βιとしては、多項式時間で計算可能なWeilペアリングやTateペアリングなどが存在する参考文献3,4等参照。また、このようなeφ,ωαω,βωやeφ,ιαι,βιを多項式時間で行うアルゴリズムとしてMillerのアルゴリズム参考文献6:VSMillerShortProgramsforfunctionsonCurves1986,インターネット<httpcryptostanfordedumillermillerpdf>などがよく知られている。さらに、このようなeφ,ωαω,βωやeφ,ιαι,βιを効率的に行うための楕円曲線や巡回群などの有限可換群の構成方法もよく知られている例えば、参考文献4、参考文献7:AMiyajiMNakabayashiSTakanoNewexplicitconditionsofellipticcurveTracesforFRReductionIEICETransFundamentalsvolE84Ano05pp12341243May2001、参考文献8:PSLMBarretoBLynnMScottConstructingellipticcurveswithprescribedembeddingdegreesProcSCN2002LNCS2576pp257267SpringerVerlag2003、参考文献9:RDupontAEngeFMorainBuildingcurveswitharbitrarysmallMOVdegreeoverfiniteprimefieldshttpeprintiacrorg2002094等参照。また、中国人の剰余定理Chineseremaindertheoremに基づき、合成数NφNφ=ωφιφを法とした剰余環Z/NφZから剰余体Z/ωφZと剰余体Z/ιφZとの直積に写す同型写像が存在すること、及び剰余体Z/ωφZと剰余体Z/ιφZとの直積から剰余環Z/NφZに写す同型写像が存在することがよく知られている参考文献10:ヨハネスブーフマン,暗号理論入門,シュプリンガーフェアラーク東京,ISBN104431708669ISBN13,pp5256。すなわち、第一楕円曲線Eφ,1上の点を第二楕円曲線Eφ,2上の点と第三楕円曲線Eφ,3上の点とに写す同型写像HMφ、及びその逆像HMφ-1が存在する。一例を挙げると、剰余環Z/NφZの元κmodNφを剰余体Z/ωφZの元κmodωφと剰余体Z/ιφZの元κmodιφとに写す同型写像をHMφとし、剰余体Z/ωφZの元κωmodωφと剰余体Z/ιφZの元κιmodιφとを剰余環Z/NφZの元κωιφιφ’κιωφωφ’modNφに写す写像をHMφ-1とすることができる。ただし、ωφ’及びιφ’はωφωφ’ιφιφ’=1を満たす自然数である。このようなωφ’,ιφ’は拡張ユークリッドの互除法を用いて容易に生成できる。ωφωφ’ιφιφ’=1の関係から、κωιφιφ’κιωφωφ’modNにHMφを作用させるとκωιφιφ’κιωφωφ’modωφ=κωιφιφ’modωφ=κω1-ωφωφ’modωφ=κωmodωφ∈Z/ωφZκωιφιφ’κιωφωφ’modιφ=κιωφωφ’modιφ=κι1-ιφιφ’modιφ=κιmodιφ∈Z/ιφZとなり、この一例での写像はHMφとHMφ-1との関係にあることが分かる。そのため、合成数Nφを素因数分解した値、すなわち素数ωφと素数ιφとの値が与えられるのであれば、判定部4111は、以下のステップA~Dの処理によって、剰余環Z/NφZ上で定義された第一楕円曲線Eφ,1上の双線形写像eφα,βを計算することができる。ステップA判定部4111は、同型写像HMφを用い、剰余環Z/NφZ上で定義された第一楕円曲線Eφ,1上の点α∈Gφ,1を、剰余体Z/ωφZ上で定義された第二楕円曲線Eφ,2上の点θωα∈Gφ,1ωと剰余体Z/ιφZ上で定義された第三楕円曲線Eφ,3上の点θια∈Gφ,1ιとに写す。ステップB判定部4111は、同型写像HMφを用い、剰余環Z/NφZ上で定義された第一楕円曲線Eφ,1上の点β∈Gφ,2を、剰余体Z/ωφZ上で定義された第二楕円曲線Eφ,2上の点θωβ∈Gφ,2ωと剰余体Z/ιφZ上で定義された第三楕円曲線Eφ,3上の点θιβ∈Gφ,2ιとに写す。ステップC判定部4111は、第二楕円曲線Eφ,2及び第三楕円曲線Eφ,3でのeφ,ωθωα,θωβ及びeφ,ιθια,θιβを求める。ステップD判定部4111は、得られた演算結果eφ,ωθωα,θωβ及びeφ,ιθια,θιβに逆像HMφ-1を作用させた値をeφα,βとする。よって素数ωφと素数ιφとの値が与えられるのであれば、判定部4111は、ステップA~Dに従ってeφμφ,g1,cφ,2u,eφcφ,1u,yσφ,2,eφμφ,g1,cφ,2v,eφcφ,1v,yσφ,2を計算し、関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2を満たすか否かを判定することができる。一方、大きな合成数Nφの素因数分解を多項式時間で行う方法は知られていない。よって、この設定の場合、素数ωφ及び素数ιφの少なくとも一方が与えられていない判定部4111は、関係eφμφ,g1,cφ,2u/eφcφ,1u,yσφ,2=eφμφ,g1,cφ,2v/eφcφ,1v,yσφ,2を満たすか否かを判定することができない。以上のような特殊な群Gφ,1,Gφ,2や双線形写像eφを用いた場合、ステップS4107及びS4110の処理を仲介装置41に実行させることができる者を素数ωφ及び素数ιφの少なくとも一方を知る者に制限することができる。[第五実施形態]上述の各実施形態では、仲介装置の自然数記憶部1101に、互いに素である2つの自然数aφ,bφの組aφ,bφが複数種類記憶され、これらの組aφ,bφを用いて各処理が実行されることとした。しかしながら、aφ,bφの一方が定数であってもよい。例えば、aφが1に固定されていてもよいし、bφが1に固定されていてもよい。言い換えると、第一乱数化可能標本器又は第二乱数化可能標本器の一方が標本器に置換されていてもよい。aφ,bφの一方が定数である場合、定数とされたaφ又はbφを選択する処理が不要となり、各処理部は定数とされたaφ又はbφが入力されることなく、それを定数として扱って計算を行うことができる。また、定数とされたaφ又はbφが1である場合には、a’φやb’φを用いることなく、fφCφ,1=uφb’φvφa’φをfφCφ,1=vφ又はfφCφ,1=uφとして得ることができる。第五実施形態は、そのような変形の一例であり、bφが1に固定され、第二乱数化可能標本器が標本器に置換された形態である。以下では、第一実施形態との相違点を中心に説明する。また、第一乱数化可能標本器や標本器の具体例は、第二実施形態から第四実施形態で説明したのと同様であるため、説明を省略する。<構成>図1に例示するように、第五実施形態の情報提供システム5は、第一実施形態の仲介装置11が仲介装置51に置換され、情報提供装置12-φが情報提供装置52-φに置換されたものである。図11に例示するように、第五実施形態の仲介装置51は、例えば、自然数記憶部5101と自然数選択部5102と入力情報提供部5104と第一計算部5105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部5108と第二リスト記憶部5110と判定部5111と処理部1112と最終出力部1113と制御部1114とを有する。図3に例示するように、第五実施形態の情報提供装置52-φは、例えば、第一出力情報計算部5201-φと第二出力情報計算部5202-φと鍵記憶部1204-φと暗号文記憶部1205-φと出力部1206-φと復号部1207-φと制御部1208-φとを有する。<処理の前提>仲介装置51の自然数記憶部5101には自然数bφが記憶されておらず、自然数aφのみが複数種類記憶されている。その他の前提は、上述の第一実施形態から第四実施形態の何れかと同様である。<処理>図12に例示するように、まず、仲介装置51図11の自然数選択部5102が、自然数記憶部5101に記憶された複数の自然数aφから1つの自然数aφをランダムに読み込む。読み込まれた自然数aφの情報は、入力情報提供部5104及び第一べき乗計算部1106に送られるステップS5100。制御部1114は、t=1とするステップS1102。入力情報提供部5104は、入力された第一暗号文Cφ,1にそれぞれ対応する第一入力情報τφ,1及び第二入力情報τφ,2を生成して出力する。好ましくは、第一入力情報τφ,1及び第二入力情報τφ,2はそれぞれ第一暗号文Cφ,1との関係をかく乱させた情報である。これにより、仲介装置51は、第一暗号文Cφ,1を情報提供装置52-φに対して隠蔽できる。また、好ましくは、本形態の第二入力情報τφ,2は自然数選択部5102で選択された自然数aφにさらに対応する。これにより、情報提供装置52-φから提供された再暗号化能力を仲介装置51が高い精度で評価することが可能となるステップS5103。第一入力情報τφ,1及び第二入力情報τφ,2の組みの具体例は、第二実施形態から第四実施形態の何れかのbφ=1とした第一入力情報τφ,1及び第二入力情報τφ,2の組みである。図8に例示するように、第一入力情報τφ,1は情報提供装置52-φ図3の第一出力情報計算部5201-φに入力され、第二入力情報τφ,2は第二出力情報計算部5202-φに入力されるステップS5200。第一出力情報計算部5201-φは、第一入力情報τφ,1と鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2とを用い、或る確率より大きな確率でfφτφ,1を正しく計算し、得られた計算結果を第一出力情報zφ,1とするステップS5201。第二出力情報計算部5202-φは、第二入力情報τφ,2と鍵記憶部1204-φに格納された第一復号鍵sφ,1及び第二暗号化鍵yσφ,2を用い、或る確率より大きな確率でfφτφ,2を正しく計算し、得られた演算結果を第二出力情報zφ,2とするステップS5202。すなわち、第一出力情報計算部5201-φや第二出力情報計算部5202-φは、意図的又は意図的ではない誤差を含んだ計算結果を出力し得る。言い換えると、第一出力情報計算部5201-φでの計算結果がfφτφ,1の場合もあればfφτφ,1でない場合もあり、第二出力情報計算部5202-φでの計算結果がfφτφ,2の場合もあればfφτφ,2でない場合もある。第一出力情報zφ,1及び第二出力情報zφ,2の組の具体例は、第二実施形態から第四実施形態の何れかのbφ=1とした第一出力情報zφ,1及び第二出力情報zφ,2の組である。第一出力情報計算部5201-φは第一出力情報zφ,1を出力し、第二出力情報計算部5202-φは第二出力情報zφ,2を出力するステップS5203。図12に戻り、第一出力情報zφ,1は仲介装置51図11の第一計算部5105に入力され、第二出力情報zφ,2は第二計算部5108に入力される。これらの第一出力情報zφ,1及び第二出力情報zφ,2が、情報提供装置52-φから仲介装置51に与えられた再暗号化能力に相当するステップS5104。第一計算部5105は、第一出力情報zφ,1から演算結果uφ=fφCφ,1xφ,1を生成する。演算結果uφの具体例は、第二実施形態から第四実施形態の何れかのbφ=1とした演算結果uφである。演算結果uφは第一べき乗計算部1106に送られるステップS5105。第一べき乗計算部1106はuφ’=uφaφを計算する。計算結果uφとその計算結果に基づいて計算されたuφ’との組uφ,uφ’は、第一リスト記憶部1107に記憶されるステップS1106。第二計算部5108は、第二出力情報zφ,2から演算結果vφ=fφCφ,1aφxφ,2を生成する。演算結果vφの具体例は、第二実施形態から第四実施形態の何れかの演算結果vφである。演算結果vφは第二リスト記憶部5110に記憶されるステップS5108。判定部5111は、第一実施形態から第四実施形態の何れかと同様に、第一リスト記憶部1107に記憶された組uφ,uφ’及び第二リスト記憶部5110に記憶されたvφの中で、uφ’とvφとが互いに同一の暗号文の類CLφMφに属するものがあるかを判定するステップS5110。同一の暗号文の類CLφMφに属するuφ’とvφとの組があった場合には、ステップS5114に進む。同一の暗号文の類CLφMφに属するuφ’とvφとの組がなかった場合には、ステップS1111に進む。ステップS1111では、制御部1114がt=Tであるか判定するステップS1111。Tは予め定められた自然数である。t=Tであれば、処理部1112が、計算をすることができなかった旨の情報、例えば記号⊥を出力してステップS1113、処理を終える。t=Tでない場合には、制御部1114は、tを1だけインクリメント、すなわちt=t1としてステップS1112、ステップS5103に戻る。ステップS5114では、処理部1112が、同一の暗号文の類CLφMφに属すると判定されたuφ’とvφとの組が含むuφ’に対応するuφを出力するステップS5114。このように得られたuφは、第一実施形態から第四実施形態でbφ=1とした場合のuφb’φvφa’φに相当する。すなわち、このように得られたuφは高い確率でfφCφ,1となる。よって、少なくともφについての自己訂正処理を複数回繰り返し、ステップS5114で得られた値のうち最も頻度の高い値uφを選択すれば、選択されたuφが第2暗号文Cφ,2であることの信頼度は所定値以上となる。また、後述するように、設定によっては圧倒的な確率でuφ=fφCφ,1となる。その場合にはステップS5114で得られた値uφが第2暗号文Cφ,2であることの信頼度は必ず所定値以上となる。≪fφCφ,1が得られる理由について≫次に、本形態の仲介装置51で復号結果fφCφ,1が得られる理由を説明する。まず、説明に必要な事項を定義する。ブラックボックスblack-box:fφτφのブラックボックスFφτφとは、τφ∈Hφを入力としてzφ∈Gφを出力する処理部を意味する。本形態では、第一出力情報計算部5201-φ及び第二出力情報計算部5202-φが、それぞれ関数fφτφのブラックボックスFφτφに相当する。群Hφから任意に選択された元τφ∈UHφ及びzφ=Fφτφに対してzφ=fφτφを満たす確率がδ0<δ≦1よりも大きい場合、すなわち、Pr[zφ=fφτφ|τφ∈UHφ,zφ=Fφτφ]>δ...1を満たすfφτφのブラックボックスFφτφのことを、信頼性δδ-reliableのfφτφのブラックボックスFφτφという。なお、δは正の値であり、前述した或る確率に相当する。自己訂正器self-corrector:自己訂正器CFxφとは、xφ∈Hφを入力とし、fφτφのブラックボックスFφτφを用いて計算を行い、j∈G∪⊥を出力する処理部を意味する。本形態では、仲介装置51が自己訂正器CFxφに相当する。オールモスト自己訂正器almostself-corrector:自己訂正器CFxφが、xφ∈Hφを入力とし、δ-reliableのfφτφのブラックボックスFφτφを用い、正しい値j=fφxφを出力する確率が、誤った値j≠fφxφを出力する確率よりも十分大きい場合を想定する。すなわち、Pr[j=fφxφ|j=CFxφ,j≠⊥]>Pr[j≠fφxφ|j=CFxφ,j≠⊥]Δ...2を満たす場合を想定する。なお、Δは或る正の値0<Δ<1である。このような場合、自己訂正器CFxφはオールモスト自己訂正器であるという。例えば、或る正の値Δ’0<Δ’<1に対してPr[j=fφxφ|j=CFxφ]>1/3Δ’Pr[j=⊥|j=CFxφ]<1/3Pr[j≠fφxφかつj≠⊥|j=CFxφ]<1/3を満たす場合、自己訂正器CFxφはオールモスト自己訂正器である。Δ’の例はΔ’=1/12や1/3である。ローバスト自己訂正器robustself-corrector:自己訂正器CFxφが、xφ∈Hを入力とし、δ-reliableのfφτφのブラックボックスFφτφを用い、正しい値j=fφxφ又はj=⊥を出力する確率が圧倒的である場合を想定する。すなわち、無視することができる誤差ξ0≦ξ<1に対してPr[j=fφxφまたはj=⊥|j=CFxφ]>1-ξ...3を満たす場合を想定する。このような場合、自己訂正器CFxφはローバスト自己訂正器であるという。なお、無視することができる誤差ξの例は、セキュリティパラメータkの関数値ξkである。関数値ξkの例は、任意の多項式pkについて、十分大きいkに対して{ξkpk}が0に収束するものである。関数値ξkの具体例は、ξk=2-kやξk=2-√kなどである。また、オールモスト自己訂正器からローバスト自己訂正器を構成することができる。すなわち、同一のxに対してオールモスト自己訂正器を複数回実行させ、⊥を除いて最も頻度が高い出力値をjとすることで、ローバスト自己訂正器を構成できる。例えば、同一のxに対してオールモスト自己訂正器をOlog1/ξ回実行させ、最も頻度が高い出力値をjとすることで、ローバスト自己訂正器を構成できる。なお、Oはオー記法を表す。擬似自由pseudo-freeな作用:群Gφ、自然数の集合Ωφ={0,...,Mφ}Mφは1以上の自然数、群Gφに値を持つ確率変数Xφ,1,Xφ,2の各実現値αφ∈Xφ,1αφ≠eφ,g,βφ∈Xφ,2、及びaφ∈Ωφについて、αφaφ=βφとなる確率Pr[αφaφ=βφかつαφ≠eφ,g|aφ∈UΩ,αφ∈Xφ,1,βφ∈Xφ,2]...4について、あらゆる可能なXφ,1,Xφ,2に関する上限値を、組Gφ,Ωφの疑似自由指標とよび、これをPGφ,Ωφと表すことにする。ある無視することができる関数ζkが存在して、PGφ,Ωφ<ζk...5である場合、組Gφ,Ωφによって定義される演算は擬似自由な作用であるという。なお、αφaφは、群Gφで定義された演算をαφに対してaφ回作用させることを意味する。また、無視することができる関数ζkの例は、任意の多項式pkについて、十分大きいkに対して{ζkpk}が0に収束するものである。関数ζkの具体例は、ζk=2-kやζk=2-√kなどである。例えば、セキュリティパラメータkとに対し、式4の確率がO2-k未満である場合、組Gφ,Ωφによって定義される演算は擬似自由な作用である。また、例えば、任意のαφ∈Gφでαφ≠eφ,gであるものについて、集合Ωφαφ={aφαφ|aφ∈Ωφ}の要素数|Ωφαφ|が2kを超える場合、組Gφ,Ωφによって定義される演算は擬似自由な作用といえる。なお、aφαφは、aφとαφに所定の演算を作用させた結果を表す。このような具体例は数多く存在する。例えば、群Gφが素数pを法とする剰余群Z/pZであり、素数pが2kのオーダーであり、集合Ωφ={0,...,p-2}であり、aφαφがαφaφ∈Z/pZであり、αφ≠eφ,gである場合、Ωφαφ={αφaφ|aφ=0,...,p-2}={eφ,g,αφ1,...,αφp-2}となり、|Ωφαφ|=p-1である。素数pが2kのオーダーであるため、ある定数Cが存在して、kが十分大きければ|Ωφαφ|>C2kを満たす。ここで式4の確率はC-12-k未満であり、このような組Gφ,Ωφによって定義される演算は擬似自由な作用である。信頼性δγδγ-reliableの乱数化可能標本器:自然数aφが与えられるたびに、δ-reliableのfφτφのブラックボックスFφτφを用い、wφ∈Gφについて、確率変数Xφに従った標本xφ’に対応するwφaφxφ’を返す乱数化可能標本器であって、wφaφxφ’=wφaφである確率がδγよりも大きいγは正定数、すなわち、Pr[wφaφxφ’=wφaφ]>δγ...6を満たすものを、信頼性δγの乱数化可能標本器という。本形態の入力情報提供部5104と第二出力情報計算部5202-φと第二計算部5108との組は、wφ=fφxφについて、信頼性δγの乱数化可能標本器である。次に、これらの定義を用い、本形態の仲介装置51でfφCφ,1が得られる理由を説明する。本形態のステップS5110では同一の暗号文の類CLφMφに属するuφ’とvφとの組があるか、すなわち、同一の暗号文の類CLφMφに属するuφaφとvφとの組があるかを判定している。本形態の入力情報提供部5104と第二出力情報計算部5202-φと第二計算部5108との組は信頼性δγの乱数化可能標本器であるため式6、Tをk、δ、γから定まる一定値よりも大きい値とすれば、漸近的に大きい確率でuφaφとvφとが同一の暗号文の類CLφMφに属することになるステップS5110でyesとなる場合が生じる。たとえば、T≧4/δγとすれば、uφaφとvφとが同一の暗号文の類CLφMφに属するステップS5110でyesとなる確率は1/2よりも大きいことがMarkovの不等式によってわかる。また、本形態ではuφ=fφCφ,1xφ,1及びvφ=fφCφ,1aφxφ,2なのであるから、uφaφとvφとが同一の暗号文の類CLφMφに属する場合にはDφ,2sσφ,2,fφCφ,1xφ,1=Dφ,2sσφ,2,fφCφ,1xφ,21/aφが成立する。ただし、Dφ,2sσφ,2,υは第二暗号化方式ENCφ,2に則ってυ∈Gφを第二復号鍵sσφ,2で復号するための関数を表す。この場合、第2暗号化方式ENCφ,2が確定暗号方式なのであればxφ,1aφ=xφ,2が成立する。また、第2暗号化方式ENCφ,2が確率暗号方式であったとしてもfφCφ,1が準同型関数なのであればxφ,1aφ=xφ,2が成立する。xφ,1aφ=xφ,2が成立する場合には、xφ,1=xφ,2=eφ,gである場合とxφ,1≠eφ,gである場合とがある。xφ,1=xφ,2=eφ,gである場合には、uφ=fφCφ,1となるのであるから、ステップS5114で出力されるuφは正しいfφCφ,1となる。一方、xφ,1≠eφ,gである場合には、uφ≠fφCφ,1となるのであるから、ステップS5114で出力されるuφは正しいfφCφ,1ではない。群Gφと自然数aφが属する集合Ωφとの組Gφ,Ωφによって定義される演算が擬似自由な作用であるか、疑似自由指標PGφ,ΩφについてT2PGφ,Ωφが漸近的に小さい場合、xφ,1aφ=xφ,2の場合にxφ,1≠eφ,gである確率式4は漸近的に小さい。したがって、xφ,1aφ=xφ,2の場合にxφ,1=eφ,gである確率は漸近的に大きい。よって、組Gφ,Ωφによって定義される演算が擬似自由な作用であるか、T2PGφ,Ωφが漸近的に小さい場合、uφaφとvφとが同一の暗号文の類CLφMφに属する場合に誤ったfφCφ,1が出力される確率は、uφaφとvφとが同一の暗号文の類CLφMφに属する場合に正しいfφCφ,1が出力される確率よりも十分小さい。この場合の仲介装置51はオールモスト自己訂正器であるといえる式2参照。そのため、前述のように、仲介装置51からローバスト自己訂正器を構成することが可能であり、圧倒的な確率で正しいfφCφ,1を得ることができる。Gφ,Ωφで定義される演算が疑似自由な作用である場合には、uφaφとvφとが同一の暗号文の類CLφMφに属する場合に誤ったfφCφ,1が出力される確率も無視できる。この場合の仲介装置51は、圧倒的な確率で正しいfφCφ,1または⊥を出力する。なお、任意の定数ρに対してk0が定まり、このk0に対してk0<k’を満たす任意のk’に対する関数値ηk’がρ未満となる場合ηk’が漸近的に小さいという。k’の例はセキュリティパラメータkである。また、任意の定数ρに対してk0が定まり、このk0に対してk0<k’を満たす任意のk’に対する関数値1-ηk’がρ未満となる場合ηk’が漸近的に大きいという。また、aφをaφ/bφに置換すれば分かるように、上述の証明は第一実施形態で述べたuφ’とvφ’とが互いに同一の暗号文の類CLφMφに属するのは、第一乱数化可能標本器がuφ=fφCφ,1bφを正しく計算しており、第二乱数化可能標本器がvφ=fφCφ,1aφを正しく計算しているxφ,1及びxφ,2が群Gφの単位元eφ,gである可能性が高いことの証明ともなる。《信頼性δγの乱数化可能標本器と安全性について》以下のような攻撃を想定する。ブラックボックスFφτφ又はその部分が意図的に不正なzφを出力する、又は、ブラックボックスFφτφから出力された値が不正なzφに改ざんされる。不正なzφに対応するwφaφxφ’が乱数化可能標本器から出力される。不正なzφに対応するwφaφxφ’は、自己訂正器CFCφ,1にuφaφとvφとが同一の暗号文の類CLφMφに属すると判定させるステップS5110でyesなるにもかかわらず、自己訂正器CFCφ,1が誤った値を出力する確率を増加させる。このような攻撃は、与えられた自然数aφに対して乱数化可能標本器から出力されたwφaφxφ’の誤差の確率分布Da=wφaφxφ’wφ-aφが自然数aφに依存する場合に可能となる。例えば、第二計算部5108から出力されるvφがfφCφ,1aφxφ,1aφとなるような不正が行われた場合、xφ,1の値にかかわらず、必ずuφaφ=vφが成立してuφaφとvφとが同一の暗号文の類CLφMφに属すると判定されることになる。よって、与えられた自然数aφに対して乱数化可能標本器から出力されたwφaφxφ’の誤差の確率分布Da=wφaφxφ’wφ-aφが当該自然数aφに依存しないことが望ましい。あるいは、集合Ωφのいかなる元aφ∈∀Ωφについても、wφaφxφ’の誤差の確率分布Da=wφaφxφ’wφ-aφと区別することができない群Gφに値を持つ確率分布Dが存在する確率分布Daと確率分布Dとが統計的に近似するstatistically-close乱数化可能標本器であることが望ましい。なお、確率分布Dは自然数aφに依存しない。また、確率分布Daと確率分布Dとを区別することができないとは、多項式時間アルゴリズムによって確率分布Daと確率分布Dとを区別することができないことを意味し、例えば、無視することができるζ0≦ζ<1に対してΣg∈G|Pr[g∈D]-Pr[g∈Da]|<ζ...7を満たすならば、多項式時間アルゴリズムによって確率分布Daと確率分布Dとを区別することができない。無視することができるζの例は、セキュリティパラメータkの関数値ζkである。関数値ζkの例は、任意の多項式pkについて、十分大きなkに対して{ζkpk}が0に収束するものである。関数値ζkの具体例は、ζk=2-kやζk=2-√kなどである。また、これらの点は自然数aφ及びbφを使用する第一実施形態から第四実施形態についても同様である。[変形例等]上記の各実施形態ではΦ=2、σ1=2、σ2=1の場合を例示したが、その他のΦ,σφについて本発明が実施されてもよい。図13では、Φ=3の場合の情報提供システム6を例示している。図13の例の場合、例えば、Φ=3、σ1=2、σ2=3、σ3=1として上記の各実施形態の処理を実行すればよい。その他、Φ=4の場合には、例えば、σ1=2、σ2=3、σ3=4、σ4=1としたり、σ1=2、σ2=1、σ3=4、σ4=3としたりしてもよい。確率変数Xφ,1、Xφ,2及びXφ,3は、同じでも異なっていてもよい。第一乱数生成部、第二乱数生成部、第三乱数生成部のそれぞれは、一様乱数を生成することにより、情報提供システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部、第二乱数生成部、第三乱数生成部の少なくとも一部が、一様乱数ではない乱数を生成してもよい。また、演算効率上からは、上述の各実施形態のように、選択される自然数の乱数は0以上Kφ,H未満の自然数であることが望ましいが、その代わりにKφ,H以上の自然数の乱数が選択されてもよい。仲介装置が同一のaφ,bφに対応する第一入力情報τφ,1及び第二入力情報τφ,2を情報提供装置に提供するたびに、情報提供装置の処理が複数回実行させてもよい。これにより、仲介装置が第一入力情報τφ,1及び第二入力情報τφ,2を情報提供装置に一回提供するたびに、仲介装置は第一出力情報zφ,1や第二出力情報zφ,2や第三出力情報zφ,3を複数個得ることができる。これにより、仲介装置と情報提供装置との間のやり取り回数や通信量を減らすことができる。また、仲介装置が複数種類の第一入力情報τφ,1及び第二入力情報τφ,2を情報提供装置にまとめて提供し、対応する第一出力情報zφ,1や第二出力情報zφ,2や第三出力情報zφ,3を複数個まとめて取得してもよい。これにより、仲介装置と情報提供装置との間のやり取り回数を減らすことができる。仲介装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、情報提供装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。また、各実施形態の第一計算部や第二計算部において得られたuφやvφが群Gφの元であるかを確認し、群Gφの元であった場合には上述した処理を続行し、uφ又はvφが群Gφの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号⊥が出力されてもよい。その他、本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。"