"再暗号化装置と能力提供装置とを有し、G,Hが有限可換群、fが第一暗号化方式に則って平文mを第一暗号化鍵y1で暗号化して得られた群Hの元である第一暗号文C1が与えられたとき、当該第一暗号文C1を、第二暗号化方式に則って前記平文mを第二暗号化鍵y2で暗号化して得られる群Gの元である第二暗号文fC1=C2に変換するための関数、a,bが互いに素である自然数、第二暗号化方式に則って当該平文を前記第二暗号化鍵y2で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類、X1,X2が群Gに値を持つ確率変数、x1が確率変数X1の実現値、x2が確率変数X2の実現値であり、前記再暗号化装置が、前記第一暗号文C1に対応する群Hの元である第一入力情報τ1及び第二入力情報τ2を出力する入力情報提供部を含み、前記能力提供装置が、前記第一入力情報τ1を用い、或る確率より大きな確率でfτ1を正しく計算し、得られた演算結果を第一出力情報z1とする第一出力情報生成部と、前記第二入力情報τ2を用い、或る確率より大きな確率でfτ2を正しく計算し、得られた演算結果を第二出力情報z2とする第二出力情報生成部と、を含み、前記再暗号化装置が、さらに前記第一出力情報z1から演算結果u=fC1bx1を生成する第一計算部と、前記第二出力情報z2から演算結果v=fC1ax2を生成する第二計算部と、前記演算結果uに対する値uaと前記演算結果vに対する値vbとが互いに同一の暗号文の類に属する場合に、a’ab’b=1を満たす整数a’,b’についての値ub’va’を出力する最終出力部と、を含む、再暗号化システム。請求項1の再暗号化システムであって、前記再暗号化装置が、前記自然数a,bの少なくとも一方を選択する自然数選択部を含み、前記第一入力情報τ1が、前記自然数bにさらに対応し、前記第二入力情報τ2が、前記自然数aにさらに対応する、再暗号化システム。請求項1又は2の再暗号化システムにおいて、前記入力情報提供部が、前記第一暗号文C1との関係をかく乱させた情報を前記第一入力情報τ1及び前記第二入力情報τ2とする、再暗号化システム。請求項1から3の何れかのの再暗号化システムにおいて、前記関数fが準同型関数である、再暗号化システム。請求項1から4の何れかの再暗号化システムであって、前記関数fが準同型関数であり、前記入力情報提供部が、群Hの任意の元hr1を生成する第一乱数生成部と、前記第一暗号化方式に則って前記元hr1を前記第一暗号化鍵y1で暗号化して得られた群Hの元C1’に対応するC1bC1’を前記第一入力情報τ1として得る第一入力情報計算部と、群Hの任意の元hr2を生成する第二乱数生成部と、前記第一暗号化方式に則って前記元hr2を前記第一暗号化鍵y1で暗号化して得られた群Hの元C1に対応するC1aC1を前記第二入力情報τ2として得る第二入力情報計算部と、前記第一出力情報計算部は、前記第一入力情報C1bC1’を用い、或る確率より大きな確率でfC1bC1’を正しく計算し、得られた計算結果を前記第一出力情報z1とし、前記第二出力情報計算部は、前記第二入力情報C1aC1を用い、或る確率より大きな確率でfC1aC1を正しく計算し、得られた計算結果を第二出力情報z2とし、前記第一計算部は、前記第二暗号化方式に則って前記元hr1を前記第二暗号化鍵y2で暗号化して得られた群Hの元C2’に対応するz1C2’-1を前記uとし、前記第二計算部は、前記第二暗号化方式に則って前記元hr2を前記第二暗号化鍵y2で暗号化して得られた群Hの元C2に対応するz2C2-1を前記vとする、再暗号化システム。請求項1から5の何れかの再暗号化システムにおいて、前記関数fが準同型関数、群Gが群G1,G2の直積G1×G2、μg1が群G1の生成元、μg2が群G2の生成元、s2が前記第二暗号化鍵y2に対応する復号鍵、前記第二暗号化鍵y2がμg2s2、rが整数の乱数、前記第二暗号文C2がμg1r,my2r、前記値uaがc1u,c2u∈G1×G2、前記値vbがc1v,c2v∈G1×G2、eα,βがα,β∈G1×G2に対して有限可換群GTの元を与える双線形写像であり、前記最終出力部は、関係eμg1,c2u/ec1u,y2=eμg1,c2v/ec1v,y2を満たす場合に前記値ub’va’を出力する、再暗号化システム。請求項6の再暗号化システムであって、Nが素数ωと素数ιの合成数、前記群G1,G2がそれぞれ前記合成数Nを法とした剰余環上で定義された第一楕円曲線上の点からなる部分群、G1ω,G2ωが前記素数ωを法とした剰余体上で定義された第二楕円曲線上の点からなる部分群、G1ι,G2ιが前記素数ιを法とした剰余体上で定義された第三楕円曲線上の点からなる部分群、eωαω,βωがαω,βω∈G1ω×G2ωに対して有限可換群GTωの元を与える第二双線形写像、eιαι,βιがαι,βι∈G1ι×G2ιに対して有限可換群GTιの元を与える第三双線形写像、HMが前記第一楕円曲線上の点を前記第二楕円曲線上の点と前記第三楕円曲線上の点とに写す同型写像、HM-1が前記同型写像HMの逆像であり、前記再暗号化装置は、前記同型写像HMを用いて前記第一楕円曲線上の点αを前記第二楕円曲線上の点θωαと前記第三楕円曲線上の点θιαとに写し、前記同型写像HMを用いて前記第一楕円曲線上の点βを前記第二楕円曲線上の点θωβと前記第三楕円曲線上の点θιβとに写し、eωθωα,θωβ及びeιθια,θιβを求め、eωθωα,θωβ及びeιθια,θιβに対する前記逆像HM-1をeα,βとして求め、前記関係を満たすか否かを判定する判定部をさらに含む、再暗号化システム。請求項1から4の何れかの再暗号化システムにおいて、前記関数fが準同型関数、μhが群Hの生成元、KHが群Hの位数、ν=fμhであり、前記入力情報提供部は、0以上の自然数の乱数r1を生成する第一乱数生成部と、前記第一入力情報τ1としてμhr1C1bを計算する第一入力情報計算部と、0以上の自然数の乱数r2を生成する第二乱数生成部と、前記第二入力情報τ2としてμhr2C1aを計算する第二入力情報計算部と、を含み、前記第一出力情報計算部が、前記第一入力情報μhr1C1bを用い、或る確率より大きな確率でfμhr1C1bを正しく計算し、得られた計算結果を前記第一出力情報z1とし、前記第二出力情報計算部は、前記第二入力情報μhr2C1aを用い、或る確率より大きな確率でfμhr2C1aを正しく計算し、得られた計算結果を第二出力情報z2とし、前記第一計算部は、z1ν-r1を計算してその計算結果を前記uとし、前記第二計算部は、z2ν-r2を計算してその計算結果を前記vとする、再暗号化システム。請求項8の再暗号化システムにおいて、前記第一乱数生成部が、b≠1のときに前記乱数r1を生成し、前記第一入力情報計算部が、b≠1のときに前記第一入力情報τ1として前記μhr1C1bを計算し、前記第一出力情報計算部が、b≠1のときに前記第一入力情報μhr1C1bを用いて得られた前記計算結果を前記第一出力情報z1とし、前記第一計算部が、b≠1のときにz1ν-r1を計算してその計算結果を前記uとし、前記第二乱数生成部が、a≠1のときに前記乱数r2を生成し、前記第二入力情報計算部が、a≠1のときに前記第二入力情報τ2としてμhr2C1aを計算し、前記第二出力情報計算部が、a≠1のときに前記第二入力情報μhr2C1aを用いて得られた前記計算結果を第二出力情報z2とし、前記第二計算部が、a≠1のときにz2ν-r2を計算してその計算結果を前記vとし、前記入力情報提供部が、0以上の自然数の乱数r3を生成する第三乱数生成部と、b=1のときにC1r3を前記第一入力情報τ1とし、a=1のときにC1r3を前記第二入力情報τ2とする第三入力情報計算部と、を含み、前記能力提供装置が、前記C1r3を用い、或る確率より大きな確率でfC1r3を正しく計算し、得られた計算結果を第三出力情報z3とする第三出力情報計算部を含み、前記再暗号化装置が、b=1のときにz31/r3を前記uとし、a=1のときにz31/r3を前記vとする第三計算部を含む、再暗号化システム。請求項1から9の何れかの再暗号化システムにおいて、前記演算結果uのfC1bに対する誤差の確率分布が前記自然数bに依存しない、並びに/若しくは、前記演算結果vのfC1aに対する誤差の確率分布が前記自然数aに依存しない、又は、前記演算結果uのfC1bに対する誤差の確率分布と区別することができない前記自然数bに依存しない確率分布が存在する、並びに/若しくは、前記演算結果vのfC1aに対する誤差の確率分布と区別することができない前記自然数aに依存しない確率分布が存在する、再暗号化システム。請求項1から10の何れかの再暗号化システムにおいて、前記自然数a又は前記自然数bが定数である、再暗号化システム。G,Hが有限可換群、fが第一暗号化方式に則って平文mを第一暗号化鍵y1で暗号化して得られた群Hの元である第一暗号文C1が与えられたとき、当該第一暗号文C1を、第二暗号化方式に則って前記平文mを第二暗号化鍵y2で暗号化して得られる群Gの元である第二暗号文fC1=C2に変換するための関数、前記第二暗号化方式に則って当該平文を前記第二暗号化鍵y2で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類、X1,X2が群Gに値を持つ確率変数、x1が確率変数X1の実現値、x2が確率変数X2の実現値、a,bが互いに素である自然数であり、演算結果u=fC1bx1を生成する第一計算部と、演算結果v=fC1ax2を生成する第二計算部と、前記演算結果uに対する値uaと前記演算結果vに対する値vbとが互いに同一の暗号文の類に属する場合に、a’ab’b=1を満たす整数a’,b’についての値ub’va’を出力する最終出力部と、を有する再暗号化装置。請求項1から11の何れかの再暗号化システムが有する能力提供装置。G,Hが有限可換群、fが第一暗号化方式に則って平文mを第一暗号化鍵y1で暗号化して得られた群Hの元である第一暗号文C1が与えられたとき、当該第一暗号文C1を、第二暗号化方式に則って前記平文mを第二暗号化鍵y2で暗号化して得られる群Gの元である第二暗号文fC1=C2に変換するための関数、前記第二暗号化方式に則って当該平文を前記第二暗号化鍵y2で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類、X1,X2が群Gに値を持つ確率変数、x1が確率変数X1の実現値、x2が確率変数X2の実現値、a,bが互いに素である自然数であり、再暗号化装置で、前記第一暗号文C1に対応する群Hの元である第一入力情報τ1及び第二入力情報τ2を出力する入力情報提供ステップと、能力提供装置で、前記第一入力情報τ1を用い、或る確率より大きな確率でfτ1を正しく計算し、得られた演算結果を第一出力情報z1とする第一出力情報生成ステップと、前記能力提供装置で、前記第二入力情報τ2を用い、或る確率より大きな確率でfτ2を正しく計算し、得られた演算結果を第二出力情報z2とする第二出力情報生成ステップと、前記再暗号化装置で、前記第一出力情報z1から演算結果u=fC1bx1を生成する第一計算ステップと、前記再暗号化装置で、前記第二出力情報z2から演算結果v=fC1ax2を生成する第二計算ステップと、前記再暗号化装置で、前記演算結果uに対する値uaと前記演算結果vに対する値vbとが互いに同一の暗号文の類に属する場合に、a’ab’b=1を満たす整数a’,b’についての値ub’va’を出力する最終出力ステップと、を有する再暗号化方法。G,Hが有限可換群、fが第一暗号化方式に則って平文mを第一暗号化鍵y1で暗号化して得られた群Hの元である第一暗号文C1が与えられたとき、当該第一暗号文C1を、第二暗号化方式に則って前記平文mを第二暗号化鍵y2で暗号化して得られる群Gの元である第二暗号文fC1=C2に変換するための関数、前記第二暗号化方式に則って当該平文を前記第二暗号化鍵y2で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類、X1,X2が群Gに値を持つ確率変数、x1が確率変数X1の実現値、x2が確率変数X2の実現値、a,bが互いに素である自然数であり、第一計算部で、演算結果u=fC1bx1を生成する第一計算ステップと、第二計算部で、演算結果v=fC1ax2を生成する第二計算ステップと、最終出力部で、前記演算結果uに対する値uaと前記演算結果vに対する値vbとが互いに同一の暗号文の類に属する場合に、a’ab’b=1を満たす整数a’,b’についての値ub’va’を出力する最終出力ステップと、を有する再暗号化方法。請求項14の再暗号化方法の第一出力情報生成ステップと第二出力情報生成ステップとを有する能力提供方法。コンピュータに請求項15の再暗号化方法の各ステップを実行させるためのプログラム。コンピュータに請求項16の能力提供方法の各ステップを実行させるためのプログラム。しかしながら、第一装置が再暗号化装置に第一復号鍵を提供する方法では、第一復号鍵を第一装置の外部に取り出さなければならず、安全上の問題がある。一方、再暗号化装置が第一暗号文を第一装置に提供し、第一装置が第一復号鍵を用いて第一暗号文を再暗号化する方法では、再暗号化装置が第一装置の再暗号化処理の正当性を検証できない。本発明はこのような点に鑑みてなされたものであり、復号鍵を提供することなく暗号文を別の暗号化鍵で再暗号化する能力を提供する技術を提供することを目的とする。本発明では、G,Hを有限可換群として、第一暗号化方式に則って平文mを第一暗号化鍵y1で暗号化して得られた群Hの元である第一暗号文C1が与えられたとき、当該第一暗号文C1を、第二暗号化方式に則って前記平文mを第二暗号化鍵y2で暗号化して得られる群Gの元である第二暗号文fC1=C2に変換するための関数をfとする。a,bが互いに素である自然数、X1,X2が群Gに値を持つ確率変数、x1が確率変数X1の実現値、x2が確率変数X2の実現値であるとする。さらに、第二暗号化方式に則って平文を第二暗号化鍵y2で暗号化して得られる可能性がある暗号文を要素とする集合を、当該暗号文が属する暗号文の類と呼ぶことにする。再暗号化装置は、第一暗号文C1に対応する群Hの元である第一入力情報τ1及び第二入力情報τ2を出力する。能力提供装置は、第一入力情報τ1を用い、或る確率より大きな確率でfτ1を正しく計算し、得られた演算結果を第一出力情報z1し、第二入力情報τ2を用い、或る確率より大きな確率でfτ2を正しく計算し、得られた演算結果を第二出力情報z2とする。再暗号化装置は、第一出力情報z1から演算結果u=fC1bx1を生成し、第二出力情報z2から演算結果v=fC1ax2を生成し、演算結果uに対する値uaと演算結果vに対する値vbとが互いに同一の暗号文の類に属する場合に、a’ab’b=1を満たす整数a’,b’についての値ub’va’を出力する。本発明では、能力提供装置が復号鍵を提供することなく、第一出力情報z1及び第二出力情報z2を再暗号化装置に提供し、再暗号化装置がub’va’を出力する。ub’va’は高い確率で第二暗号文fC1となる。このように本発明では、能力提供装置が復号鍵を提供することなく暗号文を別の暗号化鍵で再暗号化する能力を再暗号化装置に提供できる。以下、図面を参照して本発明の実施形態を説明する。[第一実施形態]まず、本発明の第一実施形態を説明する。<構成>図1に例示するように、第一実施形態の再暗号化システム1は、例えば、暗号化装置10と再暗号化装置11と能力提供装置12と再暗号文取得装置13とを有する。各装置は情報のやり取りが可能なように構成される。例えば、各装置は伝送線やネットワークや可搬型記録媒体などを経由した情報のやり取りが可能とされている。本形態では、暗号化装置10が、第一暗号化方式に則って平文mを第一暗号化鍵y1で暗号化した第一暗号文C1を出力する。第一暗号文C1を取得した再暗号化装置11は、第一暗号文C1を第二暗号文C2に再暗号化する能力の提供を、能力提供装置12に依頼する。本形態の能力提供装置12はこの能力を再暗号化装置11に提供し、再暗号化装置11は提供された能力を用いて第一暗号文C1を第二暗号文C2に再暗号化する。再暗号化装置11は第二暗号文C2を再暗号文取得装置13に提供し、再暗号文取得装置13は第二暗号文C2を復号して復号結果m’を得る。また、再暗号文取得装置13が第一暗号文C1を取得し、当該第一暗号文C1を第二暗号文C2に再暗号化する能力の提供を、再暗号化装置11及び/又は能力提供装置12に対して依頼してもよい。この場合、この能力が再暗号文取得装置13に提供され、再暗号文取得装置13は提供された能力を用いて第一暗号文C1を第二暗号文C2に再暗号化する。図2に例示するように、第一実施形態の再暗号化装置11は、例えば、自然数記憶部1101と自然数選択部1102と整数計算部1103と入力情報提供部1104と第一計算部1105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部1108と第二べき乗計算部1109と第二リスト記憶部1110と判定部1111と最終出力部1112と制御部1113とを有する。再暗号化装置11は、制御部1113の制御のもとで各処理を実行する。再暗号化装置11の例は、特別なプログラムが読み込まれたCPUcentralprocessingunitやRAMrandom-accessmemoryを備えた公知又は専用のコンピュータや、サーバ装置やゲートウェイ装置やカードリーダライタ装置や携帯電話などの計算機能と記憶機能とを備えた機器などである。図3に例示するように、第一実施形態の能力提供装置12は、例えば、第一出力情報計算部1201と第二出力情報計算部1202と鍵記憶部1204と制御部1205とを有する。能力提供装置12は、制御部1205の制御のもとで各処理を実行する。能力提供装置12の例は、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータや、携帯電話などの計算機能と記憶機能とを備えた機器や、ICカードやICチップなどの耐タンパ性モジュールなどである。図4に例示するように、第一実施形態の再暗号文取得装置13は、例えば、再暗号化装置1311と復号部1312と制御部1313と鍵記憶部1314とを有する。再暗号化装置1311の構成は図2の再暗号化装置11と同じである。再暗号文取得装置13は、制御部1313の制御のもとで各処理を実行する。再暗号文取得装置13の例は、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータや、携帯電話などの計算機能と記憶機能とを備えた機器などである。詳細構成は省略するが、第一実施形態の暗号化装置10は、第一暗号化方式に則って平文mを第一暗号化鍵y1で暗号化する能力を持つ装置である。暗号化装置10の例は、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータや、携帯電話などの計算機能と記憶機能とを備えた機器などである。<処理の前提>G,Hが有限可換群例えば巡回群であり、X1,X2が群Gに値を持つ確率変数であり、x1が確率変数X1の実現値であり、x2が確率変数X2の実現値であり、fが与えられた群Hの元である第一暗号文C1を群Gの元である第二暗号文fC1=C2に変換するための関数であるとする。ここで第一暗号文C1は第一暗号化方式に則って平文mを第一暗号化鍵y1で暗号化して得られた暗号文であり、第二暗号文C2は第二暗号化方式に則って平文mを第二暗号化鍵y2で暗号化して得られる暗号文である。第一暗号化方式や第二暗号化方式は、公開鍵暗号方式であってもよいし、共通鍵暗号方式であってもよい。また、第一暗号化方式や第二暗号化方式は、確率暗号方式であってもよいし、確定暗号方式であってもよい。さらに、第一暗号化方式と第二暗号化方式とが同一の暗号化方式であってもよいし、これらが異なる暗号化方式であってもよい。第一暗号化方式や第二暗号化方式の例は、準同型関数を暗号化関数及び復号関数とする暗号化方式である。そのような例は、ElGamal暗号方式参考文献1:TaherElgamalAPublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithmsIEEETransactionsonInformationTheoryvIT31n41985pp469472orCRYPTO84pp1018SpringerVerlagや、RSA暗号方式参考文献2:RLRivestAShamirandLAdelmanAMethodforObtainingDigitalSignatureandPublickeyCryptsystemsMITLaboratoryforComputerScienceThechnicalMemoLCSTM82April41977などである。また、G=Hであってもよいし、G≠Hであってもよい。また、以下では群G,H上の演算を乗法的に表現する。第一暗号化鍵y1には第一復号鍵s1が対応し、第二暗号化鍵y2には第二復号鍵s2が対応する。第一暗号化方式が公開鍵暗号方式である場合、第一暗号化鍵y1は公開鍵であり、第一復号鍵s1は秘密鍵である。一方、第一暗号化方式が共通鍵暗号方式である場合、第一暗号化鍵y1及び第一復号鍵s1は共通鍵である。第二暗号化方式が公開鍵暗号方式である場合、第二暗号化鍵y2は公開鍵であり、第二復号鍵s2は秘密鍵である。一方、第二暗号化方式が共通鍵暗号方式である場合、第二暗号化鍵y2及び第二復号鍵s2は共通鍵である。また、第二暗号化方式に則って平文を第二暗号化鍵y2で暗号化して得られる暗号文C2について、C2と同一の平文と同一の暗号化鍵を用いて第二暗号化方式によって得られる可能性がある暗号文の集合を当該暗号文C2が属する暗号文の類と呼ぶ。例えば、第二暗号化方式がElGamal暗号方式のような確率暗号方式である場合、同一の平文と暗号化鍵との組に対して複数の暗号文が対応するため、任意の暗号文Cについて、Cが属する暗号文の類には複数の要素が属する。一方、例えば、第二暗号化方式がRSA暗号方式のような確定暗号方式である場合、同一の平文と暗号化鍵との組に対して暗号文が一義的に定まるため、同一の暗号文の類には一つの要素のみが属する。同一の暗号文の類に一つの要素のみが属する場合、二つの値が同一の暗号文の類に属することと当該二つの値が等しいこととが等価となる。すなわち、第二暗号化方式が確定暗号方式である場合、二つの値が同一の暗号文の類に属するかの判定は当該二つの値が等しいかを判定することで行うことができる。また、再暗号化装置11図2の自然数記憶部1101に、互いに素である2つの自然数a,bの組a,bが複数種類記憶されているものとする。Iを群Gの位数未満の2つの自然数の組で互いに素なものの集合とすると、自然数記憶部1101にはIの部分集合Sに対応する自然数a,bの組a,bが記憶されていると考えることができる。a,bは互いに素な自然数であり、自然数とは0以上の整数を表す。また、第一暗号化鍵y1が暗号化装置10の鍵記憶部図示せずに格納され、第一復号鍵s1及び第二暗号化鍵y2が能力提供装置12図3の鍵記憶部1204に格納され、第二復号鍵s2が再暗号文取得装置13図4の鍵記憶部1314に格納されているものとする。<処理>まず、暗号化装置10が、鍵記憶部図示せずから読み出した第一暗号化鍵y1を用い、入力された平文mを第一暗号化方式に則って暗号化して第一暗号文C1∈Hを生成し、当該第一暗号文C1を出力する。第一暗号文C1は再暗号化装置11図2の入力情報提供部1104に入力される。第一暗号文C1が入力された再暗号化装置11の自然数選択部1102は、図7に例示するように、自然数記憶部1101に記憶された複数の自然数の組a,bから1つの自然数の組a,bをランダムに読み込む。読み込まれた自然数の組a,b少なくとも一部の情報は、整数計算部1103、入力情報提供部1104、第一べき乗計算部1106及び第二べき乗計算部1109に送られるステップS1100。整数計算部1103は、送られた自然数の組a,bを用いて、a’ab’b=1の関係を満たす整数a’,b’を計算する。自然数a,bは互いに素であるため、a’ab’b=1の関係を満たす整数a’,b’は必ず存在して、その計算方法もよく知られている。たとえば拡張互除法などのよく知られたアルゴリズムによって整数a’,b’が計算され、自然数の組a’,b’の情報は、最終出力部1112に送られるステップS1101。制御部1113は、t=1とするステップS1102。入力情報提供部1104は、入力された第一暗号文C1にそれぞれ対応する群Hの元である第一入力情報τ1及び第二入力情報τ2を生成して出力する。好ましくは、第一入力情報τ1及び第二入力情報τ2はそれぞれ第一暗号文C1との関係をかく乱させた情報である。これにより、再暗号化装置11は、第一暗号文C1を能力提供装置12に対して隠蔽できる。また、好ましくは、本形態の第一入力情報τ1は自然数選択部1102で選択された自然数bにさらに対応し、第二入力情報τ2は自然数選択部1102で選択された自然数aにさらに対応する。これにより、能力提供装置12から提供された再暗号化能力を再暗号化装置11が高い精度で評価することができるステップS1103。図8に例示するように、第一入力情報τ1は能力提供装置12図3の第一出力情報計算部1201に入力され、第二入力情報τ2は第二出力情報計算部1202に入力されるステップS1200。第一出力情報計算部1201は、第一入力情報τ1と鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2とを用い、或る確率より大きな確率でfτ1を正しく計算し、得られた計算結果を第一出力情報z1とするステップS1201。第二出力情報計算部1202は、第二入力情報τ2と鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2を用い、或る確率より大きな確率でfτ2を正しく計算し、得られた演算結果を第二出力情報z2とするステップS1202。なお、関数fの例は、第一暗号化方式に則って第一復号鍵s1で暗号文を復号して得られる値を、第二暗号化方式に則って第二暗号化鍵y2で暗号化するための準同型関数である。また、或る確率は100未満の確率である。或る確率の例は無視することができない確率であり、無視することができない確率の例は、セキュリティパラメータkについての広義単調増加関数である多項式を多項式ψkとした場合の1/ψk以上の確率である。すなわち、第一出力情報計算部1201や第二出力情報計算部1202は、意図的又は意図的ではない誤差を含んだ計算結果を出力し得る。言い換えると、第一出力情報計算部1201での計算結果がfτ1の場合もあればfτ1でない場合もあり、第二出力情報計算部1202での計算結果がfτ2の場合もあればfτ2でない場合もある。第一出力情報計算部1201は第一出力情報z1を出力し、第二出力情報計算部1202は第二出力情報z2を出力するステップS1203。図7に戻り、第一出力情報z1は再暗号化装置11図2の第一計算部1105に入力され、第二出力情報z2は第二計算部1108に入力される。これらの第一出力情報z1及び第二出力情報z2が、能力提供装置12から再暗号化装置11に与えられた再暗号化能力に相当するステップS1104。第一計算部1105は、第一出力情報z1から演算結果u=fC1bx1を生成する。ここで、fC1bx1を生成計算するとは、fC1bx1と定義される式の値を計算することである。式fC1bx1の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。演算結果uは第一べき乗計算部1106に送られるステップS1105。第一べき乗計算部1106はu’=uaを計算する。計算結果uとその計算結果に基づいて計算されたu’との組u,u’は、第一リスト記憶部1107に記憶されるステップS1106。判定部1111は、第一リスト記憶部1107に記憶された組u,u’及び第二リスト記憶部1110に記憶された組v,v’の中で、u’とv’とが互いに同一の暗号文の類に属するものがあるかを判定する。言い換えると、判定部1111は、同一の平文に対する暗号文の類に属するu’とv’との組があるか判定する。例えば、第二暗号化方式が確定暗号方式の場合、判定部1111は、u’=v’であるかを判定するステップS1107。もし、第二リスト記憶部1110に組v,v’が記憶されていない場合には、このステップS1107の処理を行わずに、次のステップS1108の処理を行う。同一の平文に対する暗号文の類に属するu’とv’との組があった場合には、ステップS1114に進む。同一の平文に対する暗号文の類に属するu’とv’との組がなかった場合には、ステップS1108に進む。ステップS1108では、第二計算部1108が、第二出力情報z2から演算結果v=fC1ax2を生成する。演算結果vは第二べき乗計算部1109に送られるステップS1108。第二べき乗計算部1109はv’=vbを計算する。計算結果vとその計算結果に基づいて計算されたv’との組v,v’は、第二リスト記憶部1110に記憶されるステップS1109。判定部1111は、第一リスト記憶部1107に記憶された組u,u’及び第二リスト記憶部1110に記憶された組v,v’の中で、u’とv’とが互いに同一の平文に対する暗号文の類に属するものがあるかを判定する。例えば、第二暗号化方式が確定暗号方式の場合、判定部1111は、u’=v’であるかを判定するステップS1110。同一の平文に対する暗号文の類に属するu’とv’との組があった場合には、ステップS1114に進む。同一の平文に対する暗号文の類に属するu’とv’との組がなかった場合には、ステップS1111に進む。ステップS1111では、制御部1113がt=Tであるか判定するステップS1111。Tは予め定められた自然数である。t=Tであれば、最終出力部1112が、計算をすることができなかった旨の情報、例えば記号⊥を出力してステップS1113、処理を終える。t=Tでない場合には、制御部1113は、tを1だけインクリメント、すなわちt=t1t1を新たなtとしてステップS1112、ステップS1103に戻る。計算をすることができなかった旨の情報この例では記号⊥は、能力提供装置12が正しく計算を行う信頼性がTで定められる基準を下回るということを意味する。言い換えれば、T回の繰り返しで正しい演算を行うことができなかったということを意味する。ステップS1114では、最終出力部1112が、同一の平文に対する暗号文の類に属すると判定されたu’とv’との組に対応するu及びvを用いてub’va’を計算して、出力するステップS1114。このように計算されたub’va’は、高い確率で第二暗号文fC1=C2∈Gとなる高い確率でub’va’=fC1となる理由については後述する。よって、上述した処理を複数回繰り返し、ステップS1114で得られた値のうち最も頻度の高い値を第2暗号文C2とすればよい。また、後述するように、設定によっては圧倒的な確率でub’va’=fC1となる。その場合にはステップS1114で得られた値をそのまま第2暗号文C2としてよい。第二暗号文Cy2,mは、再暗号文取得装置13図4の復号部1312に入力される。復号部1312は、鍵記憶部1314から読み出した第二復号鍵s2を用いて第二暗号文C2を復号し、それによって得られる復号結果m’を出力する。また、再暗号文取得装置13が再暗号化装置11から与えられた第二暗号文を信頼できない場合も想定し得る。例えば、再暗号化装置11の処理自体が不正であった場合や、再暗号化装置11から出力された第二暗号文が改ざんされる可能性がある場合などである。このような場合には、再暗号文取得装置13がローカルに含む再暗号化装置1311に第一暗号文C1が入力され、再暗号化装置1311と能力提供装置12との間で、前述の図7及び図8に記載された処理が実行されてもよい。この処理は例えば再暗号化装置11が再暗号化装置1311に置換された処理となる。或いは、この処理の際、上述した能力提供装置12の処理の少なくとも一部が再暗号化装置11によって実行されてもよい。また再暗号化装置1311は、再暗号化装置11及び能力提供装置12がそれぞれどのような処理を行っているかを知る必要はない。少なくとも、再暗号化装置11及び能力提供装置12からなるシステムとして図8に記載された処理が実行されればよい。このようにして得られた第二暗号文C2は復号部1312に入力され、同様に第二復号鍵s2を用いて復号される。これにより、たとえ第一暗号文C1が確率暗号であったとしても、第一暗号文C1と第二暗号文C2とが同一の平文mに対応することを確認できる。同様に、第一暗号文C1が確定暗号である場合にも、第一暗号文C1と第二暗号文C2とが同一の平文mに対応することを確認できる。≪高い確率でub’va’=fC1となる理由について≫Xを群Gに値を持つ確率変数とする。w∈Gについて、要求を受けるたびに確率変数Xに従った標本x’に対応するwx’を返すものを、wについて誤差Xを持つ標本器samplerと呼ぶ。w∈Gについて、自然数aが与えられるたびに確率変数Xに従った標本x’に対応するwax’を返すものを、wについて誤差Xを持つ乱数化可能標本器randomizablesamplerと呼ぶ。乱数化可能標本器はa=1として用いられれば標本器として機能する。本実施形態の入力情報提供部1104と第一出力情報計算部1201と第一計算部1105との組み合わせが、fC1について誤差X1を持つ乱数化可能標本器第一乱数化可能標本器と呼ぶであり、入力情報提供部1104と第二出力情報計算部1202と第二計算部1108との組み合わせが、fC1について誤差X2を持つ乱数化可能標本器第二乱数化可能標本器と呼ぶである。u’とv’とが互いに同一の平文に対する暗号文の類に属するのは、第一乱数化可能標本器がu=fC1bを正しく計算しており、第二乱数化可能標本器がv=fC1aを正しく計算しているx1及びx2が群Gの単位元egである可能性が高いことを発明者は見出した。説明の簡略化の観点から、この証明は第五実施形態で行う。第一乱数化可能標本器がu=fC1bを正しく計算しており、第二乱数化可能標本器がv=fC1aを正しく計算しているときx1及びx2が群Gの単位元egであるとき、ub’=fC1bx1b’=fC1begb’=fC1bb’となり、va’=fC1ax2a’=fC1aega’=fC1aa’となる。そのため、第二暗号化方式が確定暗号方式なのであればub’va’=fC1bb’aa’=fC1となる。一方、第二暗号化方式が確率暗号方式であったとしてもfC1が準同型関数なのであれば、ub’va’=fC1bb’aa’=fC1となる。また、q1,q2∈Iについて、i=1,2の各々について関数πiをπiq1,q2=qiで定義する。さらに、L=min♯π1S,♯π2Sとする。♯は、集合の位数である。群Gが巡回群や位数の計算が困難な群であるときには、再暗号化装置11が⊥以外を出力するときの出力がfC1ではない確率は、無視できる程度の誤差の範囲で高々T2L/♯S程度と期待することができる。もしL/♯Sが無視できる量でTが多項式オーダー程度の量であれば、再暗号化装置11は圧倒的な確率で正しいfC1を出力する。L/♯Sが無視できる量になるようなSの例には、例えばS={1,d|d∈[2,|G|-1]}がある。[第二実施形態]第二実施形態の再暗号化システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した例である。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。以下の説明において、同一の参照番号が付された部分は同一の機能を持つものとし、同一の参照番号が付されたステップは同一の処理を表すものとする。<構成>図1に例示するように、第二実施形態の再暗号化システム2は、再暗号化装置11が再暗号化装置21に置換され、能力提供装置12が能力提供装置22に置換され、再暗号文取得装置13が再暗号文取得装置23に置換されたものである。図2に例示するように、第二実施形態の再暗号化装置21は、例えば、自然数記憶部1101と自然数選択部1102と整数計算部1103と入力情報提供部2104と第一計算部2105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部2108と第二べき乗計算部1109と第二リスト記憶部1110と判定部1111と最終出力部1112と制御部1113とを有する。図5に例示するように、本形態の入力情報提供部2104は、例えば、第一乱数生成部2104aと第一入力情報計算部2104bと第二乱数生成部2104cと第二入力情報計算部2104dとを有する。図3に例示するように、第二実施形態の能力提供装置22は、例えば、第一出力情報計算部2201と第二出力情報計算部2202と鍵記憶部1204と制御部1205とを有する。図4に例示するように、第二実施形態の再暗号文取得装置23は、例えば、再暗号化装置2321と復号部1312と制御部1313と鍵記憶部1314とを有する。再暗号化装置2321の構成及び処理は図2の再暗号化装置21と同じである。<処理の前提>第二実施形態では、関数fを準同型関数とし、群Hの生成元をμh、群Hの位数をKH、ν=fμhとする。その他の前提は、再暗号化装置11が再暗号化装置21に置換され、能力提供装置12が能力提供装置22に置換され、再暗号文取得装置13が再暗号文取得装置23に置換されている以外、第一実施形態と同一である。<処理>図7及び図8に例示するように、第二実施形態の処理は第一実施形態のステップS1103~S1105,S1108,S1200~S1203が、それぞれ、ステップS2103~S2105,S2108,S2200~S2203に置換されたものである。以下ではステップS2103~S2105,S2108,S2200~S2203の処理のみを説明する。《ステップS2103の処理》再暗号化装置21図2の入力情報提供部2104は、入力された第一暗号文C1にそれぞれ対応する第一入力情報τ1及び第二入力情報τ2を生成して出力する図7/ステップS2103。以下、図9を用いて本形態のステップS2103の処理を説明する。第一乱数生成部2104a図5は、0以上KH未満の自然数の一様乱数r1を生成する。生成された乱数r1は、第一入力情報計算部2104b及び第一計算部2105に送られるステップS2103a。第一入力情報計算部2104bは、入力された乱数r1と第一暗号文C1と自然数bとを用いて第一入力情報τ1=μhr1C1bを計算するステップS2103b。ここで、μhの右肩のr1は、r1のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。第二乱数生成部2104cは、0以上KH未満の自然数の一様乱数r2を生成する。生成された乱数r2は、第二入力情報計算部2104d及び第二計算部2108に送られるステップS2103c。第二入力情報計算部2104dは、入力された乱数r2と第一暗号文C1と自然数aとを用いて第二入力情報τ2=μhr2C1aを計算するステップS2103d。第一入力情報計算部2104b及び第二入力情報計算部2104dは、以上のように生成した第一入力情報τ1及び第二入力情報τ2を出力するステップS2103e。なお、本形態の第一入力情報τ1及び第二入力情報τ2は、それぞれ、乱数r1,r2によって第一暗号文C1との関係をかく乱させた情報である。これにより、再暗号化装置22は、第一暗号文C1を能力提供装置22に対して隠蔽できる。また、本形態の第一入力情報τ1は自然数選択部1102で選択された自然数bにさらに対応し、第二入力情報τ2は自然数選択部1102で選択された自然数aにさらに対応する。これにより、能力提供装置22から提供された再暗号化能力を再暗号化装置21が高い精度で評価することができる。《ステップS2200~S2203の処理》図8に例示するように、まず、第一入力情報τ1=μhr1C1bが能力提供装置22図3の第一出力情報計算部2201に入力され、第二入力情報τ2=μhr2C1aが第二出力情報計算部2202に入力されるステップS2200。第一出力情報計算部2201は、第一入力情報τ1=μhr1C1bと鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2とを用い、或る確率より大きな確率でfμhr1C1bを正しく計算し、得られた計算結果を第一出力情報z1とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部2201での計算結果がfμhr1C1bとなる場合もあれば、fμhr1C1bとならない場合もある。なお、関数fの例は、第一暗号化方式に則って第一復号鍵s1で暗号文を復号して得られる値を、第二暗号化方式に則って第二暗号化鍵y2で暗号化するための準同型関数である。このような関数fに対応する第一暗号化方式や第二暗号化方式の例はRSA暗号方式であるステップS2201。第二出力情報計算部2202は、第二入力情報τ2=μhr2C1aと鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2とを用い、或る確率より大きな確率でfμhr2C1aを正しく計算し、得られた計算結果を第二出力情報z2とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部2202での計算結果がfμhr2C1aとなる場合もあれば、fμhr2C1aとならない場合もあるステップS2202。第一出力情報計算部2201は第一出力情報z1を出力し、第二出力情報計算部2202は第二出力情報z2を出力するステップS2203。《ステップS2104及びS2105の処理》図7に戻り、第一出力情報z1は再暗号化装置21図2の第一計算部2105に入力され、第二出力情報z2は第二計算部2108に入力される。これらの第一出力情報z1及び第二出力情報z2が、能力提供装置22から再暗号化装置21に与えられた再暗号化能力に相当するステップS2104。第一計算部2105は、入力された乱数r1及び第一出力情報z1を用いてz1ν-r1を計算してその計算結果をuとする。計算結果uは、第一べき乗計算部1106に送られる。ここで、u=z1ν-r1=fC1bx1となる。すなわち、z1ν-r1は、fC1について誤差X1を持つ乱数化可能標本器の出力となる。その理由については後述するステップS2105。《ステップS2108の処理》第二計算部2108は、入力された乱数r2及び第二出力情報z2を用いてz2ν-r2を計算してその計算結果をvとする。計算結果vは、第二べき乗計算部1109に送られる。ここで、v=z2ν-r2=fC1ax2となる。すなわち、z2ν-r2は、fC1について誤差X2を持つ乱数化可能標本器の出力となる。その理由については後述するステップS2108。≪z1ν-r1,z2ν-r2がfC1についてそれぞれ誤差X1,X2を持つ乱数化可能標本器の出力となる理由について≫cを自然数、R及びR’を乱数として、能力提供装置22がμhRC1cを用いて行う計算の計算結果をBμhRC1cとする。すなわち、第一出力情報計算部2201や第二出力情報計算部2202が再暗号化装置21に返す計算結果をz=BμhRC1cとする。さらに、群Gに値を持つ確率変数XをX=BμhR’fμhR’-1と定義する。このとき、zν-R=BμhRC1cfμh-R=XfμhRC1cfμh-R=XfμhRfC1cfμh-R=fC1cXとなる。すなわち、zν-Rは、fC1について誤差Xを持つ乱数化可能標本器の出力となる。上記式展開において、X=BμhR’fμhR’-1=BμhRC1cfμhRC1c-1であり、BμhRC1c=XfμhRC1cであるという性質を用いている。この性質は、関数fが準同型関数であり、R及びR’が乱数であることに基づく。したがって、a,bが自然数、r1,r2が乱数であることを考慮すると、同様に、z1ν-r1,z2ν-r2がfC1についてそれぞれ誤差X1,X2を持つ乱数化可能標本器の出力となるのである。《その他》第一実施形態と同様、再暗号文取得装置23がローカルに含む再暗号化装置2321に第一暗号文C1が入力され、再暗号化装置2321と能力提供装置22との間で、前述の図7及び図8に記載された処理が実行されてもよい。この処理は例えば再暗号化装置21が再暗号化装置2321に置換された処理となる。或いは、この処理の際、上述した能力提供装置22の処理の少なくとも一部が再暗号化装置21によって実行されてもよい。また再暗号化装置2321は、再暗号化装置21及び能力提供装置22がそれぞれどのような処理を行っているかを知る必要はない。少なくとも、再暗号化装置21及び能力提供装置22からなるシステムとして図8に記載された処理が実行されればよい。[第三実施形態]第三実施形態は第二実施形態の変形例であり、a=1やb=1のときに前述した標本器によってu又はvの値を計算する。一般に乱数化可能標本器よりも標本器の計算量は小さい。a=1やb=1のときに乱数化可能標本器に代わり、標本器が計算を行うことで、再暗号化システムの計算量を小さくすることができる。以下、第一実施形態及び第二実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。<構成>図1に例示するように、第三実施形態の再暗号化システム3は、再暗号化装置21が再暗号化装置31に置換され、能力提供装置22が能力提供装置32に置換され、再暗号文取得装置23が再暗号文取得装置33に置換されたものである。図2に例示するように、第三実施形態の再暗号化装置31は、例えば、自然数記憶部1101と自然数選択部1102と整数計算部1103と入力情報提供部2104と第一計算部2105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部2108と第二べき乗計算部1109と第二リスト記憶部1110と判定部1111と最終出力部1112と制御部1113と第三計算部3109とを有する。図3に例示するように、第三実施形態の能力提供装置32は、例えば、第一出力情報計算部2201と第二出力情報計算部2202と鍵記憶部1204と制御部1205と第三出力情報計算部3203とを有する。図4に例示するように、第三実施形態の再暗号文取得装置33は、例えば、再暗号化装置3331と復号部1312と制御部1313と鍵記憶部1314とを有する。再暗号化装置3331の構成及び処理は図2の再暗号化装置31と同じである。<処理>次に本形態の処理を説明する。第二実施形態との相違点を説明する。図7及び図8に例示するように、第三実施形態の処理は第二実施形態のステップS2103~S2105,S2108,S2200~S2203が、それぞれ、ステップS3103~S3105,S3108,S2200~S2203及びS3205~S3209に置換されたものである。以下ではステップS3103~S3105,S3108,S2200~S2203及びS3205~S3209の処理を中心に説明する。《ステップS3103の処理》再暗号化装置31図2の入力情報提供部3104は、入力された第一暗号文C1にそれぞれ対応する第一入力情報τ1及び第二入力情報τ2を生成して出力する図7/ステップS3103。以下、図9を用いて本形態のステップS3103の処理を説明する。制御部1113図2は、自然数選択部1102で選択された自然数a,bに応じて入力情報提供部3104を制御する。制御部1113でbが1であるかが判定されステップS3103a、b≠1であると判定された場合、前述のステップS2103a及びS2103bの処理が実行され、ステップS3103gに進む。一方、ステップS3103aでb=1であると判定された場合、第三乱数生成部3104eが、0以上KH未満の自然数の乱数r3を生成する。生成された乱数r3は第三入力情報計算部3104f及び第三計算部3109に送られるステップS3103b。第三入力情報計算部3104fは、入力された乱数r3と第一暗号文C1とを用いてC1r3を計算し、これを第一入力情報τ1とするステップS3103c。その後、ステップS3103gに進む。ステップS3103gでは、制御部1113でaが1であるかが判定されステップS3103g、a≠1であると判定された場合、前述のステップS2103c及びステップS2103dの処理が実行される。一方、ステップS3103gでa=1であると判定された場合、第三乱数生成部3104eが、0以上KH未満の自然数の乱数r3を生成する。生成された乱数r3は第三入力情報計算部3104fに送られるステップS3103h。第三入力情報計算部3104fは、入力された乱数r3と第一暗号文C1とを用いてC1r3を計算し、これを第二入力情報τ2とするステップS3103i。第一入力情報計算部2104b、第二入力情報計算部2104d、第三入力情報計算部3104fは、以上のように生成した第一入力情報τ1及び第二入力情報τ2を対応する自然数a,bの情報とともに出力するステップS3103e。なお、本形態の第一入力情報τ1及び第二入力情報τ2は、それぞれ、乱数r1,r2,r3によって第一暗号文C1との関係をかく乱させた情報である。これにより、再暗号化装置31は、第一暗号文C1を能力提供装置32に対して隠蔽できる。《S2200~S2203及びS3205~S3209の処理》以下、図8を用いて本形態のS2200~S2203及びS3205~S3209の処理を説明する。制御部1205図3は、入力された自然数a,bに応じ、第一出力情報計算部2201、第二出力情報計算部2202、及び第三出力情報計算部3203を制御する。制御部1205の制御に基づき、b≠1の場合の第一入力情報τ1=μhr1C1bは能力提供装置32図3の第一出力情報計算部2201に入力され、a≠1の場合の第二入力情報τ2=μhr2C1aは第二出力情報計算部2202に入力される。また、b=1の場合の第一入力情報τ1=C1r3やa=1の場合の第二入力情報τ2=C1r3は第三出力情報計算部3203に入力されるステップS3200。制御部1113でbが1であるかが判定されステップS3205、b≠1であると判定された場合、前述のステップS2201の処理が実行される。その後、制御部1113でaが1であるかが判定されステップS3208、a≠1であると判定された場合、前述したステップS2202の処理が実行されてステップS3203に進む。一方、ステップS3208でa=1であると判定された場合、第三出力情報計算部3203は、第二入力情報τ2=C1r3と鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2とを用い、或る確率より大きな確率でfC1r3を正しく計算し、得られた計算結果を第三出力情報z3とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部3203での計算結果がfC1r3となる場合もあれば、fC1r3とならない場合もあるステップS3209。その後、ステップS3203に進む。また、ステップS3205でb=1であると判定された場合、第三出力情報計算部3203は、第二入力情報τ1=C1r3と鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2とを用い、或る確率より大きな確率でfC1r3を正しく計算し、得られた計算結果を第三出力情報z3とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部3203での計算結果がfC1r3となる場合もあれば、fC1r3とならない場合もあるステップS3206。その後、制御部1113でaが1であるかが判定されステップS3207、a=1であると判定された場合にはステップS3203に進み、a≠1であると判定された場合にはステップS2202に進む。ステップS3203では、第一出力情報z1を生成した第一出力情報計算部2201は第一出力情報z1を出力し、第二出力情報z2を生成した第二出力情報計算部2202は第二出力情報z2を出力し、第三出力情報z3を生成した第三出力情報計算部3202は第三出力情報z3を出力するステップS3203。《ステップS3104及びS3105の処理》図7に戻り、制御部1113の制御のもと、第一出力情報z1は再暗号化装置31図2の第一計算部2105に入力され、第二出力情報z2は第二計算部2108に入力され、第三出力情報z3は第三計算部3109に入力されるステップS3104。b≠1であれば、第一計算部2105が、前述のステップS2105の処理によってuを生成し、b=1であれば、第三計算部3109が、z31/r3を計算してその計算結果をuとする。計算結果uは第一べき乗計算部1106に送られる。ここで、b=1の場合、u=z31/r3=fC1x3となる。すなわち、z31/r3は、fC1について誤差X3を持つ標本器となる。その理由については後述するステップS3105。《ステップS3108の処理》a≠1であれば、第二計算部2108が、前述のステップS2108の処理によってvを生成し、a=1であれば、第三計算部3109が、z31/r3を計算してその計算結果をvとする。計算結果vは第二べき乗計算部1109に送られる。ここで、a=1の場合、v=z31/r3=fC1x3となる。すなわち、z31/r3は、fC1について誤差X3を持つ標本器となる。その理由については後述するステップS3108。なお、z31/r3の計算、すなわちz3のべき乗根の計算が困難な場合には、次のようにしてu及び/又はvを計算してもよい。第三計算部3109は、乱数r3とその乱数r3に基づいて計算されたz3の組を順次α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としてもよい。≪z31/r3がfC1について誤差X3を持つ標本器となる理由について≫Rを乱数として、能力提供装置32がC1Rを用いて行う計算の計算結果をBC1Rとする。すなわち、第一出力情報計算部2201や第二出力情報計算部2202や第三出力情報計算部3203が再暗号化装置31に返す計算結果をz=BC1Rとする。さらに、群Gに値を持つ確率変数XをX=BC1R1/RfC1-1と定義する。このとき、z1/R=BC1R1/R=XfC1=fC1Xとなる。すなわち、z1/Rは、fC1について誤差Xを持つ標本器となる。上記式展開において、X=BC1R1/RfC1R-1であり、BC1R1/R=XfC1Rであるという性質を用いている。この性質は、Rが乱数であることに基づく。したがって、r3が乱数であることを考慮すると、同様に、z1/RがfC1について誤差X3を持つ標本器となるのである。《その他》第一実施形態と同様、再暗号文取得装置33がローカルに含む再暗号化装置3331に第一暗号文C1が入力され、再暗号化装置3331と能力提供装置32との間で、前述の図7及び図8に記載された処理が実行されてもよい。この処理は例えば再暗号化装置31が再暗号化装置3331に置換された処理となる。或いは、この処理の際、上述した能力提供装置32の処理の少なくとも一部が再暗号化装置31によって実行されてもよい。また再暗号化装置3331は、再暗号化装置31及び能力提供装置32がそれぞれどのような処理を行っているかを知る必要はない。少なくとも、再暗号化装置31及び能力提供装置32からなるシステムとして図8に記載された処理が実行されればよい。[第四実施形態]第四実施形態の再暗号化システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した他の例である。具体的には、第二暗号化方式がElGamal暗号方式であり、関数fが準同型関数である例を示す。なお、第一暗号化方式には特に限定はなく、第一暗号化方式はElGamal暗号方式のような確率暗号方式であってもよいし、RSA暗号方式のような確定暗号方式であってもよい。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。図1に例示するように、第四実施形態の再暗号化システム4は、再暗号化装置11が再暗号化装置41に置換され、能力提供装置12が能力提供装置42に置換され、再暗号文取得装置13が再暗号文取得装置43に置換されたものである。図2に例示するように、第四実施形態の再暗号化装置41は、例えば、自然数記憶部1101と自然数選択部1102と整数計算部1103と入力情報提供部4104と第一計算部4105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部4108と第二べき乗計算部1109と第二リスト記憶部1110と判定部4111と最終出力部1112と制御部1113とを有する。図6に例示するように、本形態の入力情報提供部4104は、例えば、第一乱数生成部4104aと第一入力情報計算部4104bと第二乱数生成部4104cと第二入力情報計算部4104dと鍵記憶部4104eとを有する。図3に例示するように、第四実施形態の能力提供装置42は、例えば、第一出力情報計算部4201と第二出力情報計算部4202と鍵記憶部1204と制御部1205とを有する。<処理の前提>第四実施形態では、群Gが巡回群G1,G2の直積G1×G2、μg1が群G1の生成元、μg2が群G2の生成元、第二暗号化鍵y2がμg2s2、第二暗号文C2がμg1r,my2r∈G1×G2、rが整数の乱数、値uaがc1u,c2u∈G1×G2、値vbがc1v,c2v∈G1×G2である。G1=G2であってもよいし、G1≠G2であってもよい。また、前述のように第一暗号化方式には限定はないが、例えば第一暗号化方式がElGamal暗号方式である場合には、群Hが巡回群H1,H2の直積H1×H2、r’が整数の乱数、μh1が群H1の生成元、μh2が群H2の生成元、第一暗号化鍵y1がμh2s1、第一暗号文C1がμh1r’,my1r’∈H1×H2となる。H1=H2であってもよいし、H1≠H2であってもよい。なお、Α=α1,α2∈G1×G2,Β=β1,β2∈G1×G2,及びεが自然数である場合、Αεはα1ε,α2εを表し、Α-εはα1-ε,α2-εを表し、ΑΒはα1β1,α2β2を表す。同様に、εが自然数、Α=α1,α2∈H1×H2,Β=β1,β2∈H1×H2である場合、Αεはα1ε,α2εを表し、Α-εはα1-ε,α2-εを表し、ΑΒはα1β1,α2β2を表す。また、eα,βをα,β∈G1×G2に対して巡回群GTの元を与える双線形写像とする。双線形写像の例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数やアルゴリズムである参考文献3:AlfredJMenezes,ELLIPTICCURVEPUBLICKEYCRYPTOSYSTEMS,KLUWERACADEMICPUBLISHERS,ISBN0792393686,pp6181や、参考文献4:RFC5091IdentityBasedCryptographyStandard1SupersingularCurveImplementationsoftheBFandBB1Cryptosystems等参照。また、第一暗号化鍵y1及び第二暗号化鍵y2が、再暗号化装置11の入力情報提供部4104が含む鍵記憶部4104eに格納されているものとする。<処理>図7及び図8に例示するように、第四実施形態の処理は第一実施形態のステップS1103~S1105,S1107,S1108,S1110,S1200~S1203が、それぞれ、ステップS4103~S4105,S4107,S4108,S4110,S4200~S4203に置換されたものである。以下ではステップS4103~S4105,S4107,S4108,S4110,S4200~S4203の処理のみを説明する。《ステップS4103の処理》再暗号化装置41図2の入力情報提供部4104は、入力された第一暗号文C1に対応する第一入力情報τ1及び第二入力情報τ2を生成して出力する図7/ステップS4103。以下、図10を用いて本形態のステップS4103の処理を説明する。第一乱数生成部4104a図6は、群Hの任意の元hr1∈Hを生成する。本形態では群Hからランダムかつ一様に元hr1が選択される一様乱数。生成された元hr1は、第一入力情報計算部4104b、及び第一計算部4105に送られるステップS4103a。第一入力情報計算部4104bは、自然数選択部1102で選択された自然数b、第一暗号文C1、元hr1、及び鍵記憶部4104eから抽出した第一暗号化鍵y1を用い、第一暗号化方式によって第一暗号化鍵y1を用いて元hr1を暗号化したある暗号文C1’についてC1bC1’を計算し、C1bC1’を第一入力情報τ1とするステップS4103b。第二乱数生成部4104cは、群Hの任意の元hr2∈Hを生成する。本形態では群Hからランダムかつ一様に元hr2が選択される一様乱数。生成された元hr2は、第二入力情報計算部4104d、及び第二計算部4108に送られるステップS4103c。第二入力情報計算部4104bは、自然数選択部1102で選択された自然数a、第一暗号文C1、元hr2、及び鍵記憶部4104eから抽出した第一暗号化鍵y1を用い、第一暗号化方式によって第一暗号化情報y1を用いて元hr2を暗号化したある暗号文C1について、C1aC1を計算し、C1aC1を第二入力情報τ2とするステップS4103d。第一入力情報計算部4104bは、以上のように生成した第一入力情報τ1=C1bC1’を出力する。第二入力情報計算部4104dは、以上のように生成した第二入力情報τ2=C1aC1を出力するステップS4103e。《ステップS4200~S4203の処理》図8に例示するように、まず、第一入力情報τ1=C1bC1’が能力提供装置42図3の第一出力情報計算部4201に入力され、第二入力情報τ2=C1aC2が第二出力情報計算部4202に入力されるステップS4200。第一出力情報計算部4201は、第一入力情報τ1=C1bC1’と鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2とを用い、或る確率より大きな確率でfC1bC1’を正しく計算し、計算結果を第一出力情報z1とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部4201での計算結果がfC1bC1’となる場合もあれば、fC1bC1’とならない場合もあるステップS4201。なお、本形態の関数fは、第一暗号化方式に則って第一復号鍵s1で暗号文を復号して得られる値をElGamal暗号方式に則って第二暗号化鍵y2で暗号化するための準同型関数である。例えば、第一暗号化方式も第二暗号化方式もElGamal暗号方式で或る場合、関数fは、ElGamal暗号方式に則って第一復号鍵s1で暗号文を復号して得られる値を、ElGamal暗号方式に則って第二暗号化鍵y2で暗号化するための準同型関数である。第二出力情報計算部4202は、第二入力情報τ2=C1aC1と鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2とを用い、或る確率より大きな確率でfC1aC1を正しく計算可能であり、得られた計算結果を第二出力情報z2とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部4202での計算結果がfC1aC1となる場合もあれば、fC1aC1とならない場合もあるステップS4202。第一出力情報計算部4201は第一出力情報z1を出力し、第二出力情報計算部4202は第二出力情報z2を出力するステップS4203。《ステップS4104及びS4105の処理》図7に戻り、第一出力情報z1は再暗号化装置41図2の第一計算部4105に入力され、第二出力情報z2は第二計算部4108に入力されるステップS4104。第一計算部4105は、入力された第一出力情報z1、元hr1、及び鍵記憶部4104e図6から読み出した第二暗号化鍵y2を用い、第二暗号化方式によって第二暗号化鍵y2を用いて元hr1を暗号化したある暗号文C2’について、z1C2’-1を計算してその計算結果をuとするステップS4105。計算結果uは、第一べき乗計算部1106に送られる。ここで、u=z1C2’-1=fC1bx1となる。すなわち、z1C2’-1は、fC1について誤差X1を持つ乱数化可能標本器の出力となる。その理由については後述する。《ステップS4108の処理》第二計算部4108は、入力された第二出力情報z2、元hr2、及び鍵記憶部4104e図6から読み出した第二暗号化鍵y2を用い、第二暗号化方式によって第二暗号化鍵y2を用いて元hr2を暗号化したある暗号文C2について、z2C2-1を計算してその計算結果をvとする。計算結果vは、第二べき乗計算部1109に送られる。ここで、v=z2C2-1=fC1ax2となる。すなわち、z2C2-1は、fC1について誤差X2を持つ乱数化可能標本器の出力となる。その理由については後述する。《ステップS4107の処理》判定部4111は、第一リスト記憶部1107に記憶された組u,u’及び第二リスト記憶部1110に記憶された組v,v’の中で、u’とv’とが互いに同一の平文に対する暗号文の類に属するものがあるかを判定する。本形態の判定部4111は、u’=c1u,c2u及びv’=c1v,c2vに対して、関係eμg1,c2u/ec1u,y2=eμg1,c2v/ec1v,y2を満たすものがあるかを判定するステップS4107。u’とv’がこの関係を満たすかを判定することで、u’とv’とが互いに同一の平文に対する暗号文の類に属することを判定できる理由については後述する。もし、第二リスト記憶部1110に組v,v’が記憶されていない場合には、このステップS4107の処理を行わずに、次のステップS1108の処理を行う。同一の平文に対する暗号文の類に属するu’とv’との組があった場合上記の関係を満たすu’とv’との組があった場合には、ステップS1114に進む。同一の平文に対する暗号文の類に属するu’とv’との組がなかった場合には、ステップS4108に進む。《ステップS4110の処理》判定部4111は、第一リスト記憶部1107に記憶された組u,u’及び第二リスト記憶部4110に記憶された組v,v’の中で、u’とv’とが互いに同一の平文に対する暗号文の類に属するものがあるかを判定する。本形態の判定部4111は、u’=c1u,c2u及びv’=c1v,c2vに対して、関係eμg1,c2u/ec1u,y2=eμg1,c2v/ec1v,y2を満たすものがあるかを判定するステップS4110。同一の平文に対する暗号文の類に属するu’とv’との組があった場合には、ステップS1114に進む。同一の平文に対する暗号文の類に属するu’とv’との組がなかった場合には、ステップS1111に進む。なお、特殊な群G1,G2や双線形写像eを用いた場合、ステップS4107及びS4110の処理を再暗号化装置41に実行させることができる者を制限できる。この詳細については後述する。《z1C2’-1,z2C2-1がfC1についてそれぞれ誤差X1,X2を持つ乱数化可能標本器の出力となる理由について》任意の元hr1を固定して考えると、第二暗号文Cy2,m=μg1r,my2rにおける乱数rを確率空間とする確率分布について、以下の関係が成り立つ。ただし、Ds1,C1は、第一暗号化方式に則って第一暗号文C1を第一復号鍵s1で復号するための関数を表す。また、hr2’=Ds1,C1ahr2とする。rを乱数として、あるr2が存在してfC1aC1C2-1=μg1r,Ds1,C1ahr2y2rμg1r2,hr2y2r2-1となるから、fC1aC1C2-1=μg1r-r2,Ds1,C1ay2r-r2となる。したがって、確率分布fC1aC1C2-1は確率分布fC1aと等しい。したがって、C1を確率変数とみなして、群Gに値を持つ確率変数X2=z2fC1aC1-1を考えると、z2C2-1=z2fC1aC1-1fC1aC1C2-1であるから、この確率分布はx2∈X2についてx2fC1aの確率分布と等しい。同様に、z1C2’-1の確率分布はx1∈X1についてfC1bx1の確率分布と等しい。C1を確率変数とみなすとき、C1aC1の分布はC1の分布と等しいから、確率変数X2の確率分布はaに依存しない。同様に、確率変数X1の確率分布はbに依存しない。したがって、z1C2’-1,z2C2-1はfC1についてそれぞれ誤差X1,X2を持つ乱数化可能標本器の出力となる。《関係eμg1,c2u/ec1u,y2=eμg1,c2v/ec1v,y2を満たすかを判定することで、u’とv’とが互いに同一の平文に対する暗号文の類に属することを判定できる理由》u’とv’とが互いに同一の平文mに対する暗号文の類に属すると仮定する。この場合には第一乱数化可能標本器がu=fC1bを正しく計算しており、第二乱数化可能標本器がv=fC1aを正しく計算しているx1及びx2が群Gの単位元egである可能性が高い。よって、u’=μg1r’’,my2r’’かつv’=μg1r’’’,my2r’’’である可能性が高い。ただし、r’’及びr’’’は、ElGamal暗号方式の乱数成分と自然数選択部1102で選択された自然数の組とによって定まる値である。その場合、双線形写像eの性質から、u’=c1u,c2uに対してeμg1,c2u/ec1u,y2=eμg1,my2r’’/eμg1r’’,y2=eμg1,my2r’’/eμg1,y2r’’=eμg1,meμg1,y2/eμg1,y2=eμg1,mを満たす可能性が高い。また、v’=c1v,c2vに対してeμg1,c2v/ec1v,y2=eμg1,my2r’’’/eμg1r’’’,y2=eμg1,my2r’’’/eμg1,y2r’’’=eμg1,meμg1,y2/eμg1,y2=eμg1,mを満たす可能性が高い。よって、u’とv’とが互いに同一の平文mに対する暗号文の類に属する場合、関係eμg1,c2u/ec1u,y2=eμg1,c2v/ec1v,y2を満たす可能性が高い。次に、u’とv’とが互いに異なる平文に対する暗号文の類に属すると仮定する。すなわち、u’が平文muに対する暗号文の類に属し、v’が平文mvmv≠muに対する暗号文の類に属すると仮定する。すると、u’=μg1r’’,muy2r’’x1かつv’=μg1r’’’,mvy2r’’’x2となる。そのため、u’=c1u,c2uに対してeμg1,c2u/ec1u,y2=eμg1,mux1を満たし、v’=c1v,c2vに対してeμg1,c2v/ec1v,y2=eμg1,mvx2を満たす。よって、u’とv’とが互いに異なる平文に対する暗号文の類に属する場合、関係eμg1,c2u/ec1u,y2≠eμg1,c2v/ec1v,y2となる可能性が高い。《特殊な群G1,G2や双線形写像e》群G1,G2や双線形写像eの構成を以下のように限定した場合、ステップS4107及びS4110の処理を再暗号化装置41に実行させることができる者を制限することができる。以下にその詳細を述べる。この特殊な例では、Nが素数ωと素数ιの合成数、群G1,G2がそれぞれ合成数Nを法とした剰余環Z/NZ上で定義された第一楕円曲線上の点からなる部分群、G1ω,G2ωが素数ωを法とした剰余体Z/ωZ上で定義された第二楕円曲線上の点からなる部分群、G1ι,G2ιが素数ιを法とした剰余体Z/ιZ上で定義された第三楕円曲線上の点からなる部分群、eα,βがα,β∈G1×G2に対して巡回群GTの元を与える双線形写像、eωαω,βωがαω,βω∈G1ω×G2ωに対して巡回群GTωの元を与える第二双線形写像、eιαι,βιがαι,βι∈G1ι×G2ιに対して巡回群GTιの元を与える第三双線形写像、HMが第一楕円曲線上の点を第二楕円曲線上の点と第三楕円曲線上の点とに写す同型写像、HM-1が同型写像HMの逆像である。この例の場合、双線形写像eα,βは剰余環Z/NZ上で定義された第一楕円曲線上で定義される。しかしながら、剰余環上で定義された楕円曲線上で定義された双線形写像eα,βを多項式時間で計算する方法は知られておらず、多項式時間で計算可能な剰余環上で定義された楕円曲線上で定義された双線形写像eα,βの構成方法も知られていない参考文献5:AlexanderWDentandStevenDGalbraithHiddenPairingsandTrapdoorDDHGroupsANTS2006LNCS4076pp4364512006。このような設定の場合、判定部4111は、双線形写像eを剰余環Z/NZ上で直接計算して関係eμg1,c2u/ec1u,y2=eμg1,c2v/ec1v,y2を満たすか否かを判定することができない。一方、剰余体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に基づき、合成数NN=ωιを法とした剰余環Z/NZから剰余体Z/ωZと剰余体Z/ιZとの直積に写す同型写像が存在すること、及び剰余体Z/ωZと剰余体Z/ιZとの直積から剰余環Z/NZに写す同型写像が存在することがよく知られている参考文献10:ヨハネスブーフマン,暗号理論入門,シュプリンガーフェアラーク東京,ISBN104431708669ISBN13,pp5256。すなわち、第一楕円曲線上の点を第二楕円曲線上の点と第三楕円曲線上の点とに写す同型写像HM、及びその逆像HM-1が存在する。一例を挙げると、剰余環Z/NZの元κmodNを剰余体Z/ωZの元κmodωと剰余体Z/ιZの元κmodιとに写す同型写像をHMとし、剰余体Z/ωZの元κωmodωと剰余体Z/ιZの元κιmodιとを剰余環Z/NZの元κωιι’κιωω’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/NZ上で定義された第一楕円曲線上の双線形写像eα,βを計算することができる。ステップA判定部4111は、同型写像HMを用い、剰余環Z/NZ上で定義された第一楕円曲線上の点α∈G1を、剰余体Z/ωZ上で定義された第二楕円曲線上の点θωα∈G1ωと剰余体Z/ιZ上で定義された第三楕円曲線上の点θια∈G1ιとに写す。ステップB判定部4111は、同型写像HMを用い、剰余環Z/NZ上で定義された第一楕円曲線上の点β∈G2を、剰余体Z/ωZ上で定義された第二楕円曲線上の点θωβ∈G2ωと剰余体Z/ιZ上で定義された第三楕円曲線上の点θιβ∈G2ιとに写す。ステップC判定部4111は、第二楕円曲線及び第三楕円曲線でのeωθωα,θωβ及びeιθια,θιβを求める。ステップD判定部4111は、得られた演算結果eωθωα,θωβ及びeιθια,θιβに逆像HM-1を作用させた値をeα,βとする。よって素数ωと素数ιとの値が与えられるのであれば、判定部4111は、ステップA~Dに従ってeμg1,c2u,ec1u,y2,eμg1,c2v,ec1v,y2を計算し、関係eμg1,c2u/ec1u,y2=eμg1,c2v/ec1v,y2を満たすか否かを判定することができる。一方、大きな合成数Nの素因数分解を多項式時間で行う方法は知られていない。よって、この設定の場合、素数ω及び素数ιの少なくとも一方が与えられていない判定部4111は、関係eμg1,c2u/ec1u,y2=eμg1,c2v/ec1v,y2を満たすか否かを判定することができない。以上のような特殊な群G1,G2や双線形写像eを用いた場合、ステップS4107及びS4110の処理を再暗号化装置41に実行させることができる者を素数ω及び素数ιの少なくとも一方を知る者に制限することができる。《その他》第一実施形態と同様、再暗号文取得装置43がローカルに含む再暗号化装置4341に第一暗号文C1が入力され、再暗号化装置4341と能力提供装置42との間で、前述の図7及び図8に記載された処理が実行されてもよい。この処理は例えば再暗号化装置41が再暗号化装置4341に置換された処理となる。或いは、この処理の際、上述した能力提供装置42の処理の少なくとも一部が再暗号化装置41によって実行されてもよい。また再暗号化装置4341は、再暗号化装置41及び能力提供装置42がそれぞれどのような処理を行っているかを知る必要はない。少なくとも、再暗号化装置41及び能力提供装置42からなるシステムとして図8に記載された処理が実行されればよい。[第五実施形態]上述の各実施形態では、再暗号化装置の自然数記憶部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’を用いることなく、fC1=ub’va’をfC1=v又はfC1=uとして得ることができる。第五実施形態は、そのような変形の一例であり、bが1に固定され、第二乱数化可能標本器が標本器に置換された形態である。以下では、第一実施形態との相違点を中心に説明する。また、第一乱数化可能標本器や標本器の具体例は、第二実施形態から第四実施形態で説明したのと同様であるため、説明を省略する。<構成>図1に例示するように、第五実施形態の再暗号化システム5は、第一実施形態の再暗号化装置11が再暗号化装置51に置換され、能力提供装置12が能力提供装置52に置換され、再暗号文取得装置13が再暗号文取得装置53に置換されたものである。図11に例示するように、第五実施形態の再暗号化装置51は、例えば、自然数記憶部5101と自然数選択部5102と入力情報提供部5104と第一計算部5105と第一べき乗計算部1106と第一リスト記憶部1107と第二計算部5108と第二リスト記憶部5110と判定部5111と最終出力部1112と制御部1113とを有する。図3に例示するように、第五実施形態の能力提供装置52は、例えば、第一出力情報計算部5201と第二出力情報計算部5202と鍵記憶部1204と制御部1205とを有する。図4に例示するように、第二実施形態の再暗号文取得装置53は、例えば、再暗号化装置5351と復号部1312と制御部1313と鍵記憶部1314とを有する。再暗号化装置5351の構成及び処理は図11の再暗号化装置51と同じである。<処理の前提>再暗号化装置51の自然数記憶部5101には自然数bが記憶されておらず、自然数aのみが複数種類記憶されている。その他の前提は、上述の第一実施形態から第四実施形態の何れかと同様である。<処理>図12に例示するように、まず、再暗号化装置51図11の自然数選択部5102が、自然数記憶部5101に記憶された複数の自然数aから1つの自然数aをランダムに読み込む。読み込まれた自然数aの情報は、入力情報提供部5104及び第一べき乗計算部1106に送られるステップS5100。制御部1113は、t=1とするステップS1102。入力情報提供部5104は、入力された第一暗号文C1にそれぞれ対応する第一入力情報τ1及び第二入力情報τ2を生成して出力する。好ましくは、第一入力情報τ1及び第二入力情報τ2はそれぞれ第一暗号文C1との関係をかく乱させた情報である。これにより、再暗号化装置51は、第一暗号文C1を能力提供装置52に対して隠蔽できる。また、好ましくは、本形態の第二入力情報τ2は自然数選択部5102で選択された自然数aにさらに対応する。これにより、能力提供装置52から提供された再暗号化能力を再暗号化装置51が高い精度で評価することが可能となるステップS5103。第一入力情報τ1及び第二入力情報τ2の組みの具体例は、第二実施形態から第四実施形態の何れかのb=1とした第一入力情報τ1及び第二入力情報τ2の組みである。図8に例示するように、第一入力情報τ1は能力提供装置52図3の第一出力情報計算部5201に入力され、第二入力情報τ2は第二出力情報計算部5202に入力されるステップS5200。第一出力情報計算部5201は、第一入力情報τ1と鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2とを用い、或る確率より大きな確率でfτ1を正しく計算し、得られた計算結果を第一出力情報z1とするステップS5201。第二出力情報計算部5202は、第二入力情報τ2と鍵記憶部1204に格納された第一復号鍵s1及び第二暗号化鍵y2を用い、或る確率より大きな確率でfτ2を正しく計算し、得られた演算結果を第二出力情報z2とするステップS5202。すなわち、第一出力情報計算部5201や第二出力情報計算部5202は、意図的又は意図的ではない誤差を含んだ計算結果を出力し得る。言い換えると、第一出力情報計算部5201での計算結果がfτ1の場合もあればfτ1でない場合もあり、第二出力情報計算部5202での計算結果がfτ2の場合もあればfτ2でない場合もある。第一出力情報z1及び第二出力情報z2の組の具体例は、第二実施形態から第四実施形態の何れかのb=1とした第一出力情報z1及び第二出力情報z2の組である。第一出力情報計算部5201は第一出力情報z1を出力し、第二出力情報計算部5202は第二出力情報z2を出力するステップS5203。図12に戻り、第一出力情報z1は再暗号化装置51図11の第一計算部5105に入力され、第二出力情報z2は第二計算部5108に入力される。これらの第一出力情報z1及び第二出力情報z2が、能力提供装置52から再暗号化装置51に与えられた再暗号化能力に相当するステップS5104。第一計算部5105は、第一出力情報z1から演算結果u=fC1x1を生成する。演算結果uの具体例は、第二実施形態から第四実施形態の何れかのb=1とした演算結果uである。演算結果uは第一べき乗計算部1106に送られるステップS5105。第一べき乗計算部1106はu’=uaを計算する。計算結果uとその計算結果に基づいて計算されたu’との組u,u’は、第一リスト記憶部1107に記憶されるステップS1106。第二計算部5108は、第二出力情報z2から演算結果v=fC1ax2を生成する。演算結果vの具体例は、第二実施形態から第四実施形態の何れかの演算結果vである。演算結果vは第二リスト記憶部5110に記憶されるステップS5108。判定部5111は、第一実施形態から第四実施形態の何れかと同様に、第一リスト記憶部1107に記憶された組u,u’及び第二リスト記憶部5110に記憶されたvの中で、u’とvとが互いに同一の平文に対する暗号文の類に属するものがあるかを判定するステップS5110。同一の平文に対する暗号文の類に属するu’とvとの組があった場合には、ステップS5114に進む。同一の平文に対する暗号文の類に属するu’とvとの組がなかった場合には、ステップS1111に進む。ステップS1111では、制御部1113がt=Tであるか判定するステップS1111。Tは予め定められた自然数である。t=Tであれば、最終出力部1113が、計算をすることができなかった旨の情報、例えば記号⊥を出力してステップS1113、処理を終える。t=Tでない場合には、制御部1113は、tを1だけインクリメント、すなわちt=t1としてステップS1112、ステップS5103に戻る。ステップS5114では、最終出力部1112が、同一の平文に対する暗号文の類に属すると判定されたu’とvとの組が含むu’に対応するuを出力するステップS5114。このように得られたuは、第一実施形態から第四実施形態でb=1とした場合のub’va’に相当する。すなわち、このように得られたuは高い確率でfC1となる。よって、上述した処理を複数回繰り返し、ステップS5114で得られた値のうち最も頻度の高い値を第2暗号文C2とすればよい。また、後述するように、設定によっては圧倒的な確率でu=fC1となる。その場合にはステップS5114で得られた値をそのまま第2暗号文C2としてよい。≪fC1が得られる理由について≫次に、本形態の再暗号化装置51で復号結果fC1が得られる理由を説明する。まず、説明に必要な事項を定義する。ブラックボックス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=fxを出力する確率が、誤った値j≠fxを出力する確率よりも十分大きい場合を想定する。すなわち、Pr[j=fx|j=CFx,j≠⊥]>Pr[j≠fx|j=CFx,j≠⊥]Δ...2を満たす場合を想定する。なお、Δは或る正の値0<Δ<1である。このような場合、自己訂正器CFxはオールモスト自己訂正器であるという。例えば、或る正の値Δ’0<Δ’<1に対してPr[j=fx|j=CFx]>1/3Δ’Pr[j=⊥|j=CFx]<1/3Pr[j≠fxかつj≠⊥|j=CFx]<1/3を満たす場合、自己訂正器CFxはオールモスト自己訂正器である。Δ’の例はΔ’=1/12や1/3である。ローバスト自己訂正器robustself-corrector:自己訂正器CFxが、x∈Hを入力とし、δ-reliableのfτのブラックボックスFτを用い、正しい値j=fx又はj=⊥を出力する確率が圧倒的である場合を想定する。すなわち、無視することができる誤差ξ0≦ξ<1に対してPr[j=fxまたは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に値を持つ確率変数X1,X2の各実現値α∈X1α≠eg,β∈X2、及びa∈Ωについて、αa=βとなる確率Pr[αa=βかつα≠eg|a∈UΩ,α∈X1,β∈X2]...4について、あらゆる可能なX1,X2に関する上限値を、組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でα≠egであるものについて、集合Ωα={aα|a∈Ω}の要素数|Ωα|が2kを超える場合、組G,Ωによって定義される演算は擬似自由な作用といえる。なお、aαは、aとαに所定の演算を作用させた結果を表す。このような具体例は数多く存在する。例えば、群Gが素数pを法とする剰余群Z/pZであり、素数pが2kのオーダーであり、集合Ω={0,...,p-2}であり、aαがαa∈Z/pZであり、α≠egである場合、Ωα={αa|a=0,...,p-2}={eg,α1,...,αp-2}となり、|Ωα|=p-1である。素数pが2kのオーダーであるため、ある定数Cが存在して、kが十分大きければ|Ωα|>C2kを満たす。ここで式4の確率はC-12-k未満であり、このような組G,Ωによって定義される演算は擬似自由な作用である。信頼性δγδγ-reliableの乱数化可能標本器:自然数aが与えられるたびに、δ-reliableのfτのブラックボックスFτを用い、w∈Gについて、確率変数Xに従った標本x’に対応するwax’を返す乱数化可能標本器であって、wax’=waである確率がδγよりも大きいγは正定数、すなわち、Pr[wax’=wa]>δγ...6を満たすものを、信頼性δγの乱数化可能標本器という。本形態の入力情報提供部5104と第二出力情報計算部5202と第二計算部5108との組は、w=fxについて、信頼性δγの乱数化可能標本器である。次に、これらの定義を用い、本形態の再暗号化装置51でfC1が得られる理由を説明する。本形態のステップS5110では同一の平文に対する暗号文の類に属するu’とvとの組があるか、すなわち、同一の平文に対する暗号文の類に属するuaとvとの組があるかを判定している。本形態の入力情報提供部5104と第二出力情報計算部5202と第二計算部5108との組は信頼性δγの乱数化可能標本器であるため式6、Tをk、δ、γから定まる一定値よりも大きい値とすれば、漸近的に大きい確率でuaとvとが同一の平文に対する暗号文の類に属することになるステップS5110でyesとなる場合が生じる。たとえば、T≧4/δγとすれば、uaとvとが同一の平文に対する暗号文の類に属するステップS5110でyesとなる確率は1/2よりも大きいことがMarkovの不等式によってわかる。また、本形態ではu=fC1x1及びv=fC1ax2なのであるから、uaとvとが同一の平文に対する暗号文の類に属する場合にはDs2,fC1x1=Ds2,fC1x21/aが成立する。ただし、Ds2,υは第二暗号化方式に則ってυ∈Gを第二復号鍵s2で復号するための関数を表す。この場合、第2暗号化方式が確定暗号方式なのであればx1a=x2が成立する。また、第2暗号化方式が確率暗号方式であったとしてもfC1が準同型関数なのであればx1a=x2が成立する。x1a=x2が成立する場合には、x1=x2=egである場合とx1≠egである場合とがある。x1=x2=egである場合には、u=fC1となるのであるから、ステップS5114で出力されるuは正しいfC1となる。一方、x1≠egである場合には、u≠fC1となるのであるから、ステップS5114で出力されるuは正しいfC1ではない。群Gと自然数aが属する集合Ωとの組G,Ωによって定義される演算が擬似自由な作用であるか、疑似自由指標PG,ΩについてT2PG,Ωが漸近的に小さい場合、x1a=x2の場合にx1≠egである確率式4は漸近的に小さい。したがって、x1a=x2の場合にx1=egである確率は漸近的に大きい。よって、組G,Ωによって定義される演算が擬似自由な作用であるか、T2PG,Ωが漸近的に小さい場合、uaとvとが同一の平文に対する暗号文の類に属する場合に誤ったfC1が出力される確率は、uaとvとが同一の平文に対する暗号文の類に属する場合に正しいfC1が出力される確率よりも十分小さい。この場合の再暗号化装置51はオールモスト自己訂正器であるといえる式2参照。そのため、前述のように、再暗号化装置51からローバスト自己訂正器を構成することが可能であり、圧倒的な確率で正しいfC1を得ることができる。G,Ωで定義される演算が疑似自由な作用である場合には、uaとvとが同一の平文に対する暗号文の類に属する場合に誤ったfC1が出力される確率も無視できる。この場合の再暗号化装置51は、圧倒的な確率で正しいfC1または⊥を出力する。なお、任意の定数ρに対してk0が定まり、このk0に対してk0<k’を満たす任意のk’に対する関数値ηk’がρ未満となる場合ηk’が漸近的に小さいという。k’の例はセキュリティパラメータkである。また、任意の定数ρに対してk0が定まり、このk0に対してk0<k’を満たす任意のk’に対する関数値1-ηk’がρ未満となる場合ηk’が漸近的に大きいという。また、aをa/bに置換すれば分かるように、上述の証明は第一実施形態で述べたu’とv’とが互いに同一の平文に対する暗号文の類に属するのは、第一乱数化可能標本器がu=fC1bを正しく計算しており、第二乱数化可能標本器がv=fC1aを正しく計算しているx1及びx2が群Gの単位元egである可能性が高いことの証明ともなる。《信頼性δγの乱数化可能標本器と安全性について》以下のような攻撃を想定する。ブラックボックスFτ又はその部分が意図的に不正なzを出力する、又は、ブラックボックスFτから出力された値が不正なzに改ざんされる。不正なzに対応するwax’が乱数化可能標本器から出力される。不正なzに対応するwax’は、自己訂正器CFC1にuaとvとが同一の平文に対する暗号文の類に属すると判定させるステップS5110でyesなるにもかかわらず、自己訂正器CFC1が誤った値を出力する確率を増加させる。このような攻撃は、与えられた自然数aに対して乱数化可能標本器から出力されたwax’の誤差の確率分布Da=wax’w-aが自然数aに依存する場合に可能となる。例えば、第二計算部5108から出力されるvがfC1ax1aとなるような不正が行われた場合、x1の値にかかわらず、必ずua=vが成立してuaとvとが同一の平文に対する暗号文の類に属すると判定されることになる。よって、与えられた自然数aに対して乱数化可能標本器から出力されたwax’の誤差の確率分布Da=wax’w-aが当該自然数aに依存しないことが望ましい。あるいは、集合Ωのいかなる元a∈∀Ωについても、wax’の誤差の確率分布Da=wax’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を使用する第一実施形態から第四実施形態についても同様である。《その他》第一実施形態から第四実施形態と同様、再暗号文取得装置53がローカルに含む再暗号化装置5351に第一暗号文C1が入力され、再暗号化装置5351と能力提供装置52との間で、前述の図8及び図12に記載された処理が実行されてもよい。この処理は例えば再暗号化装置51が再暗号化装置5351に置換された処理となる。或いは、この処理の際、上述した能力提供装置52の処理の少なくとも一部が再暗号化装置51によって実行されてもよい。また再暗号化装置5351は、再暗号化装置51及び能力提供装置52がそれぞれどのような処理を行っているかを知る必要はない。少なくとも、再暗号化装置51及び能力提供装置52からなるシステムとして図8に記載された処理が実行されればよい。[変形例等]確率変数X1、X2及びX3は、同じでも異なっていてもよい。第一乱数生成部、第二乱数生成部、第三乱数生成部のそれぞれは、一様乱数を生成することにより、再暗号化システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部、第二乱数生成部、第三乱数生成部の少なくとも一部が、一様乱数ではない乱数を生成してもよい。また、演算効率上からは、上述の各実施形態のように、選択される自然数の乱数は0以上KH未満の自然数であることが望ましいが、それの代わりにKH以上の自然数の乱数が選択されてもよい。再暗号化装置が同一のa,bに対応する第一入力情報τ1及び第二入力情報τ2を能力提供装置に提供するたびに、能力提供装置の処理が複数回実行させてもよい。これにより、再暗号化装置が第一入力情報τ1及び第二入力情報τ2を能力提供装置に一回提供するたびに、再暗号化装置は第一出力情報z1や第二出力情報z2や第三出力情報z3を複数個得ることができる。これにより、再暗号化装置と能力提供装置との間のやり取り回数や通信量を減らすことができる。また、再暗号化装置が複数種類の第一入力情報τ1及び第二入力情報τ2を能力提供装置にまとめて提供し、対応する第一出力情報z1や第二出力情報z2や第三出力情報z3を複数個まとめて取得してもよい。これにより、再暗号化装置と能力提供装置との間のやり取り回数を減らすことができる。再暗号化装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、能力提供装置や再暗号文取得装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。また、各実施形態の第一計算部や第二計算部において得られたuやvが群Gの元であるかを確認し、群Gの元であった場合には上述した処理を続行し、u又はvが群Gの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号⊥が出力されてもよい。その他、本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。"