(57)【特許請求の範囲】
【請求項１】
仲介装置とΦ個の情報提供装置φとを有し、
φ＝１，…，Φ、σ（φ）＝１，…，Φ、σ（φ）≠φ、Φが２以上の整数、Ｇφ，Ｈφが有限可換群、ｆφが第一暗号化方式ＥＮＣφ，１に則って平文ｍφを第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元である第一暗号文Ｃφ，１が与えられたとき、当該第一暗号文Ｃφ，１を、第二暗号化方式ＥＮＣφ，２に則って前記平文ｍφを第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元である第二暗号文ｆφ（Ｃφ，１）＝Ｃφ，２に変換するための関数、ａ（φ），ｂ（φ）が互いに素である自然数、平文Ｍφを前記第二暗号化方式ＥＮＣφ，２に則って前記第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類ＣＬφ（Ｍφ）、Ｘφ，１，Ｘφ，２が群Ｇφに値を持つ確率変数、ｘφ，１が確率変数Ｘφ，１の実現値、ｘφ，２が確率変数Ｘφ，２の実現値であり、
前記仲介装置が、
前記情報提供装置φそれぞれの前記第一暗号文Ｃφ，１に対応する群Ｈφの元である第一入力情報τφ，１及び第二入力情報τφ，２を出力する入力情報提供部を含み、
前記情報提供装置φのそれぞれが、
前記第一入力情報τφ，１を用い、或る確率より大きな確率でｆφ（τφ，１）を正しく計算し、得られた演算結果を第一出力情報ｚφ，１とする第一出力情報計算部と、
前記第二入力情報τφ，２を用い、或る確率より大きな確率でｆφ（τφ，２）を正しく計算し、得られた演算結果を第二出力情報ｚφ，２とする第二出力情報計算部と、を含み、
前記仲介装置が、さらに
前記第一出力情報ｚφ，１から演算結果ｕφ＝ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１を生成する第一計算部と、
前記第二出力情報ｚφ，２から演算結果ｖφ＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２を生成する第二計算部と、
前記演算結果ｕφに対する値ｕφａ（φ）と前記演算結果ｖφに対する値ｖφｂ（φ）とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属する場合の前記演算結果ｕφ及び前記演算結果ｖφと、ａ’（φ）ａ（φ）＋ｂ’（φ）ｂ（φ）＝１を満たす整数ａ’（φ），ｂ’（φ）とに対する、値ｕφｂ’（φ）ｖφａ’（φ）を得る処理部と、
すべてのφ＝１，…，Φについて前記値ｕφｂ’（φ）ｖφａ’（φ）が得られた後に、前記値ｕφｂ’（φ）ｖφａ’（φ）（φ＝１，…，Φ）を出力する最終出力部とを含む、
情報提供システム。
【請求項２】
請求項１の情報提供システムであって、
前記仲介装置が、前記自然数ａ（φ），ｂ（φ）の少なくとも一方を選択する自然数選択部を含み、
前記第一入力情報τφ，１が前記自然数ｂ（φ）にさらに対応し、前記第二入力情報τφ，２が前記自然数ａ（φ）にさらに対応する、
情報提供システム。
【請求項３】
請求項１又は２の情報提供システムにおいて、
前記入力情報提供部が、前記第一暗号文Ｃφ，１との関係をかく乱させた情報を前記第一入力情報τφ，１及び前記第二入力情報τφ，２とする、
情報提供システム。
【請求項４】
請求項１から３の何れかの情報提供システムであって、
前記関数ｆφが準同型関数であり、
前記入力情報提供部が、
群Ｈφの任意の元ｈｒφ，１を生成する第一乱数生成部と、
第一暗号化方式ＥＮＣφ，１に則って前記元ｈｒφ，１を前記第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元Ｃφ，１’に対応するＣφ，１ｂ（φ）Ｃφ，１’を前記第一入力情報τφ，１として得る第一入力情報計算部と、
群Ｈφの任意の元ｈｒφ，２を生成する第二乱数生成部と、
第一暗号化方式ＥＮＣφ，１に則って前記元ｈｒφ，２を前記第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元Ｃφ，１”に対応するＣφ，１ａ（φ）Ｃφ，１”を前記第二入力情報τφ，２として得る第二入力情報計算部と、を含み、
前記第一出力情報計算部は、前記第一入力情報Ｃφ，１ｂ（φ）Ｃφ，１’を用い、或る確率より大きな確率でｆφ（Ｃφ，１ｂ（φ）Ｃφ，１’）を正しく計算し、得られた計算結果を前記第一出力情報ｚφ，１とし、
前記第二出力情報計算部は、前記第二入力情報Ｃφ，１ａ（φ）Ｃφ，１”を用い、或る確率より大きな確率でｆφ（Ｃφ，１ａ（φ）Ｃφ，１”）を正しく計算し、得られた計算結果を第二出力情報ｚφ，２とし、
前記第一計算部は、前記第二暗号化方式ＥＮＣφ，２に則って前記元ｈｒφ，１を前記第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元Ｃφ，２’に対応するｚφ，１（Ｃφ，２’）−１を前記ｕφとし、
前記第二計算部は、前記第二暗号化方式ＥＮＣφ，２に則って前記元ｈｒφ，２を前記第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元Ｃφ，２”に対応するｚφ，２（Ｃφ，２”）−１を前記ｖφとする、
情報提供システム。
【請求項５】
請求項１から４の何れかの情報提供システムにおいて、
前記関数ｆφが準同型関数、群Ｇφが群Ｇφ，１，Ｇφ，２の直積Ｇφ，１×Ｇφ，２、μφ，ｇ１が群Ｇφ，１の生成元、μφ，ｇ２が群Ｇφ，２の生成元、ｓ（σ（φ），２）が前記第二暗号化鍵ｙ（σ（φ），２）に対応する復号鍵、前記第二暗号化鍵ｙ（σ（φ），２）がμφ，ｇ２ｓ（σ（φ），２）、ｒ（φ）が整数の乱数、前記第二暗号文Ｃφ，２が（μφ，ｇ１ｒ（φ），ｍφｙ（σ（φ），２）ｒ（φ））、前記値ｕφａ（φ）が（ｃφ，１ｕ，ｃφ，２ｕ）∈Ｇφ，１×Ｇφ，２、前記値ｖφｂ（φ）が（ｃφ，１ｖ，ｃφ，２ｖ）∈Ｇφ，１×Ｇφ，２、ｅφ（α，β）が（α，β）∈Ｇφ，１×Ｇφ，２に対して有限可換群Ｇφ，Ｔの元を与える双線形写像であり、
前記処理部は、関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を満たす場合の前記値ｕφｂ’（φ）ｖφａ’（φ）を出力する、
情報提供システム。
【請求項６】
請求項５の情報提供システムであって、
Ｎφが素数ωφと素数ιφの合成数、前記群Ｇφ，１，Ｇφ，２がそれぞれ前記合成数Ｎφを法とした剰余環上で定義された第一楕円曲線Ｅφ，１上の点からなる部分群、Ｇφ，１ω，Ｇφ，２ωが前記素数ωφを法とした剰余体上で定義された第二楕円曲線Ｅφ，２上の点からなる部分群、Ｇφ，１ι，Ｇφ，２ιが前記素数ιφを法とした剰余体上で定義された第三楕円曲線Ｅφ，３上の点からなる部分群、ｅφ，ω（αω，βω）が（αω，βω）∈Ｇφ，１ω×Ｇφ，２ωに対して有限可換群Ｇφ，Ｔωの元を与える第二双線形写像、ｅφ，ι（αι，βι）が（αι，βι）∈Ｇφ，１ι×Ｇφ，２ιに対して有限可換群Ｇφ，Ｔιの元を与える第三双線形写像、ＨＭφが前記第一楕円曲線Ｅφ，１上の点を前記第二楕円曲線Ｅφ，２上の点と前記第三楕円曲線Ｅφ，３上の点とに写す同型写像、ＨＭφ−１が前記同型写像ＨＭφの逆像であり、
前記仲介装置は、
前記同型写像ＨＭφを用いて前記第一楕円曲線Ｅφ，１上の点αを前記第二楕円曲線Ｅφ，２上の点θω（α）と前記第三楕円曲線Ｅφ，３上の点θι（α）とに写し、前記同型写像ＨＭφを用いて前記第一楕円曲線Ｅφ，１上の点βを前記第二楕円曲線Ｅφ，２上の点θω（β）と前記第三楕円曲線Ｅφ，３上の点θι（β）とに写し、ｅφ，ω（θω（α），θω（β））及びｅφ，ι（θι（α），θι（β））を求め、ｅφ，ω（θω（α），θω（β））及びｅφ，ι（θι（α），θι（β））に対する前記逆像ＨＭφ−１をｅφ（α，β）として求め、前記関係を満たすか否かを判定する判定部をさらに含む、
情報提供システム。
【請求項７】
請求項１から３の何れかの情報提供システムにおいて、
前記関数ｆφが準同型関数、μφ，ｈが群Ｈの生成元、Ｋφ，Ｈが群Ｈφの位数、νφ＝ｆφ（μφ，ｈ）であり、
前記入力情報提供部は、
０以上の自然数の乱数ｒ（φ，１）を生成する第一乱数生成部と、
前記第一入力情報τφ，１としてμφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ）を計算する第一入力情報計算部と、
０以上の自然数の乱数ｒ（φ，２）を生成する第二乱数生成部と、
前記第二入力情報τφ，２としてμφ，ｈｒ（φ，２）Ｃφ，１ａ（φ）を計算する第二入力情報計算部と、を含み、
前記第一出力情報計算部は、前記第一入力情報μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ）を用い、或る確率より大きな確率でｆφ（μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ））を正しく計算し、得られた計算結果を前記第一出力情報ｚφ，１とし、
前記第二出力情報計算部は、前記第二入力情報μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ）を用い、或る確率より大きな確率でｆφ（μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ））を正しく計算し、得られた計算結果を第二出力情報ｚφ，２とし、
前記第一計算部は、ｚφ，１νφ−ｒ（φ，１）を計算してその計算結果を前記ｕφとし、
前記第二計算部は、ｚφ，２νφ−ｒ（φ，２）を計算してその計算結果を前記ｖφとする、
情報提供システム。
【請求項８】
請求項７の情報提供システムにおいて、
前記第一乱数生成部は、ｂ（φ）≠１のときに前記乱数ｒ（φ，１）を生成し、
前記第一入力情報計算部は、ｂ（φ）≠１のときに前記第一入力情報τφ，１として前記μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ）を計算し、
前記第一出力情報計算部は、ｂ（φ）≠１のときに前記第一入力情報μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ）を用いて得られた前記計算結果を前記第一出力情報ｚφ，１とし、
前記第一計算部が、ｂ（φ）≠１のときにｚφ，１νφ−ｒ（φ，１）を計算してその計算結果を前記ｕφとし、
前記第二乱数生成部が、ａ（φ）≠１のときに前記乱数ｒ（φ，２）を生成し、
前記第二入力情報計算部が、ａ（φ）≠１のときに前記第二入力情報τφ，２としてμφ，ｈｒ（φ，２）Ｃφ，１ａ（φ）を計算し、
前記第二出力情報計算部が、ａ（φ）≠１のときに前記第二入力情報μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ）を用いて得られた前記計算結果を第二出力情報ｚφ，２とし、
前記第二計算部が、ａ（φ）≠１のときにｚφ，２νφ−ｒ（φ，２）を計算してその計算結果を前記ｖφとし、
前記入力情報提供部が、
０以上の自然数の乱数ｒ（φ，３）を生成する第三乱数生成部と、
ｂ（φ）＝１のときにＣφ，１ｒ（φ，３）を前記第一入力情報τφ，１とし、ａ（φ）＝１のときにＣφ，１ｒ（φ，３）を前記第二入力情報τφ，２とする第三入力情報計算部と、を含み、
前記情報提供装置が、
前記Ｃφ，１ｒ（φ，３）を用い、或る確率より大きな確率でｆφ（Ｃφ，１ｒ（φ，３））を正しく計算し、得られた計算結果を第三出力情報ｚφ，３とする第三出力情報計算部を含み、
前記仲介装置が、
ｂ（φ）＝１のときにｚφ，３１／ｒ（φ，３）を前記ｕφとし、ａ（φ）＝１のときにｚφ，３１／ｒ（φ，３）を前記ｖφとする第三計算部を含む、
情報提供システム。
【請求項９】
請求項１から８の何れかの情報提供システムにおいて、
前記演算結果ｕφのｆφ（Ｃφ，１）ｂ（φ）に対する誤差の確率分布が前記自然数ｂ（φ）に依存しない、並びに／若しくは、前記演算結果ｖφのｆφ（Ｃφ，１）ａ（φ）に対する誤差の確率分布が前記自然数ａ（φ）に依存しない、又は、前記演算結果ｕφのｆφ（Ｃφ，１）ｂ（φ）に対する誤差の確率分布と区別することができない前記自然数ｂ（φ）に依存しない確率分布が存在する、並びに／若しくは、前記演算結果ｖφのｆφ（Ｃφ，１）ａ（φ）に対する誤差の確率分布と区別することができない前記自然数ａ（φ）に依存しない確率分布が存在する、
情報提供システム。
【請求項１０】
φ＝１，…，Φ、σ（φ）＝１，…，Φ、σ（φ）≠φ、Φが２以上の整数、Ｇφ，Ｈφが有限可換群、ｆφが第一暗号化方式ＥＮＣφ，１に則って平文ｍφを第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元である第一暗号文Ｃφ，１が与えられたとき、当該第一暗号文Ｃφ，１を、第二暗号化方式ＥＮＣφ，２に則って前記平文ｍφを第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元である第二暗号文ｆφ（Ｃφ，１）＝Ｃφ，２に変換するための関数、ａ（φ），ｂ（φ）が互いに素である自然数、平文Ｍφを前記第二暗号化方式ＥＮＣφ，２に則って前記第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類ＣＬφ（Ｍφ）、Ｘφ，１，Ｘφ，２が群Ｇφに値を持つ確率変数、ｘφ，１が確率変数Ｘφ，１の実現値、ｘφ，２が確率変数Ｘφ，２の実現値であり、
演算結果ｕφ＝ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１を生成する第一計算部と、
演算結果ｖφ＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２を生成する第二計算部と、
前記演算結果ｕφに対する値ｕφａ（φ）と前記演算結果ｖφに対する値ｖφｂ（φ）とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属する場合の前記演算結果ｕφ及び前記演算結果ｖφと、ａ’（φ）ａ（φ）＋ｂ’（φ）ｂ（φ）＝１を満たす整数ａ’（φ），ｂ’（φ）とに対する、値ｕφｂ’（φ）ｖφａ’（φ）を得る処理部と、
すべてのφ＝１，…，Φについて前記値ｕφｂ’（φ）ｖφａ’（φ）が得られた後に、前記値ｕφｂ’（φ）ｖφａ’（φ）（φ＝１，…，Φ）を出力する最終出力部と、
を有する仲介装置。
【請求項１１】
φ＝１，…，Φ、σ（φ）＝１，…，Φ、σ（φ）≠φ、Φは２以上の整数、Ｇφ，Ｈφが有限可換群、ｆφが第一暗号化方式ＥＮＣφ，１に則って平文ｍφを第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元である第一暗号文Ｃφ，１が与えられたとき、当該第一暗号文Ｃφ，１を、第二暗号化方式ＥＮＣφ，２に則って前記平文ｍφを第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元である第二暗号文ｆφ（Ｃφ，１）＝Ｃφ，２に変換するための関数、ａ（φ），ｂ（φ）が互いに素である自然数、平文Ｍφを前記第二暗号化方式ＥＮＣφ，２に則って前記第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類ＣＬφ（Ｍφ）、Ｘφ，１，Ｘφ，２が群Ｇφに値を持つ確率変数、ｘφ，１が確率変数Ｘφ，１の実現値、ｘφ，２が確率変数Ｘφ，２の実現値であり、
仲介装置で、前記情報提供装置φそれぞれの前記第一暗号文Ｃφ，１に対応する群Ｈφの元である第一入力情報τφ，１及び第二入力情報τφ，２を出力する入力情報提供ステップと、
情報提供装置φのそれぞれで、前記第一入力情報τφ，１を用い、或る確率より大きな確率でｆφ（τφ，１）を正しく計算し、得られた演算結果を第一出力情報ｚφ，１とする第一出力情報計算ステップと、
前記情報提供装置φのそれぞれで、前記第二入力情報τφ，２を用い、或る確率より大きな確率でｆφ（τφ，２）を正しく計算し、得られた演算結果を第二出力情報ｚφ，２とする第二出力情報計算ステップと、
前記仲介装置で、前記第一出力情報ｚφ，１から演算結果ｕφ＝ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１を生成する第一計算ステップと、
前記仲介装置で、前記第二出力情報ｚφ，２から演算結果ｖφ＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２を生成する第二計算ステップと、
前記仲介装置で、前記演算結果ｕφに対する値ｕφａ（φ）と前記演算結果ｖφに対する値ｖφｂ（φ）とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属する場合の前記演算結果ｕφ及び前記演算結果ｖφと、ａ’（φ）ａ（φ）＋ｂ’（φ）ｂ（φ）＝１を満たす整数ａ’（φ），ｂ’（φ）とに対する、値ｕφｂ’（φ）ｖφａ’（φ）を得る処理ステップと、
前記仲介装置で、すべてのφ＝１，…，Φについて前記値ｕφｂ’（φ）ｖφａ’（φ）が得られた後に、前記値ｕφｂ’（φ）ｖφａ’（φ）（φ＝１，…，Φ）を出力する最終出力ステップと、
を有する情報提供方法。
【請求項１２】
φ＝１，…，Φ、σ（φ）＝１，…，Φ、σ（φ）≠φ、Φは２以上の整数、Ｇφ，Ｈφが有限可換群、ｆφが第一暗号化方式ＥＮＣφ，１に則って平文ｍφを第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元である第一暗号文Ｃφ，１が与えられたとき、当該第一暗号文Ｃφ，１を、第二暗号化方式ＥＮＣφ，２に則って前記平文ｍφを第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元である第二暗号文ｆφ（Ｃφ，１）＝Ｃφ，２に変換するための関数、ａ（φ），ｂ（φ）が互いに素である自然数、平文Ｍφを前記第二暗号化方式ＥＮＣφ，２に則って前記第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類ＣＬφ（Ｍφ）、Ｘφ，１，Ｘφ，２が群Ｇφに値を持つ確率変数、ｘφ，１が確率変数Ｘφ，１の実現値、ｘφ，２が確率変数Ｘφ，２の実現値であり、
第一計算部で、演算結果ｕφ＝ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１を生成する第一計算ステップと、
第二計算部で、演算結果ｖφ＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２を生成する第二計算ステップと、
処理部で、前記演算結果ｕφに対する値ｕφａ（φ）と前記演算結果ｖφに対する値ｖφｂ（φ）とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属する場合の前記演算結果ｕφ及び前記演算結果ｖφと、ａ’（φ）ａ（φ）＋ｂ’（φ）ｂ（φ）＝１を満たす整数ａ’（φ），ｂ’（φ）とに対する、値ｕφｂ’（φ）ｖφａ’（φ）を得る処理ステップと、
最終出力部で、すべてのφ＝１，…，Φについて前記値ｕφｂ’（φ）ｖφａ’（φ）が得られた後に、前記値ｕφｂ’（φ）ｖφａ’（φ）（φ＝１，…，Φ）を出力する最終出力ステップと、
を有する仲介方法。
【請求項１３】
請求項１０の仲介装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化された情報を提供する技術に関し、特に、複数の装置間で情報提供を行う技術に関する。
【背景技術】
【０００２】
暗号文を格納した複数の情報提供装置が、当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する状況を想定する。このような情報提供方法には様々なものが想定できる。しかしながら、互いを信頼できない情報提供装置間でこのような処理を公平に行うことは容易ではない。相手から暗号文の提供を受けた情報提供装置が自らは情報の提供を行わず、先に情報を提供した情報提供装置が不利益を被る可能性があるからである（持ち逃げ問題）。
【０００３】
持ち逃げ問題を抑制する手法として、同時交換プロトコルと呼ばれる手法が知られている（例えば、非特許文献１参照）。同時交換プロトコルの一つであるGradual Release of Secretでは、一方の情報提供装置が情報の一部を他方の情報提供装置に提供してから、当該他方の情報提供装置が情報の一部を当該一方の情報提供装置に提供するといった処理を繰り返す。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】I. Damgard (Ed.), "Signing Contracts and Paying Electronically," Lectures on Data Security, Lecture Notes in Computer Science 1561
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、Gradual Release of Secretの場合でも、情報を提供された情報提供装置が自らの情報を提供しない可能性があり、やはり先に情報を提供した情報提供装置が不利益を被る可能性がある。
【０００６】
また、情報提供装置間が互いに暗号文を提供した場合であっても、一方の情報提供装置が不正な暗号文を他方の情報提供装置に提供し、当該他方の情報提供装置が不利益を被る可能性もある。
【０００７】
このような問題は、暗号文を格納した二つの情報提供装置が当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する場合に限定されたものではなく、複数の情報提供装置が当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する場合に共通する問題である。
【０００８】
本発明はこのような点に鑑みてなされたものであり、暗号文を格納した複数の情報提供装置が、当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する場合の持ち逃げ問題を抑制できる技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明では、φ＝１，…，Φ、σ（φ）＝１，…，Φ、σ（φ）≠φ、Φが２以上の整数、Ｇφ，Ｈφが有限可換群、ｆφが第一暗号化方式ＥＮＣφ，１に則って平文ｍφを第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元である第一暗号文Ｃφ，１が与えられたとき、当該第一暗号文Ｃφ，１を、第二暗号化方式ＥＮＣφ，２に則って平文ｍφを第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元である第二暗号文ｆφ（Ｃφ，１）＝Ｃφ，２に変換するための関数、ａ（φ），ｂ（φ）が互いに素である自然数、平文Ｍφを第二暗号化方式ＥＮＣφ，２に則って第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる可能性がある暗号文を要素とする集合が、当該暗号文が属する暗号文の類、Ｘφ，１，Ｘφ，２が群Ｇφに値を持つ確率変数、ｘφ，１が確率変数Ｘφ，１の実現値、ｘφ，２が確率変数Ｘφ，２の実現値であり、仲介装置とΦ個の情報提供装置φとが次の処理を行う。
【００１０】
仲介装置で、情報提供装置φそれぞれの第一暗号文Ｃφ，１に対応する群Ｈφの元である第一入力情報τφ，１及び第二入力情報τφ，２を出力する。情報提供装置φのそれぞれで、第一入力情報τφ，１を用い、或る確率より大きな確率でｆφ（τφ，１）を正しく計算し、得られた演算結果を第一出力情報ｚφ，１とし、第二入力情報τφ，２を用い、或る確率より大きな確率でｆφ（τφ，２）を正しく計算し、得られた演算結果を第二出力情報ｚφ，２とする。仲介装置で、第一出力情報ｚφ，１から演算結果ｕφ＝ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１を生成し、第二出力情報ｚφ，２から演算結果ｖφ＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２を生成し、演算結果ｕφに対する値ｕφａ（φ）と演算結果ｖφに対する値ｖφｂ（φ）とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属する場合の演算結果ｕφ及び演算結果ｖφと、ａ’（φ）ａ（φ）＋ｂ’（φ）ｂ（φ）＝１を満たす整数ａ’（φ），ｂ’（φ）とに対する、値ｕφｂ’（φ）ｖφａ’（φ）を得、すべてのφ＝１，…，Φについて値ｕφｂ’（φ）ｖφａ’（φ）が得られた後に、値ｕφｂ’（φ）ｖφａ’（φ）（φ＝１，…，Φ）を出力する。
【発明の効果】
【００１１】
仲介装置で得られた各値ｕφｂ’（φ）ｖφａ’（φ）は、それぞれ高い確率で第二暗号化鍵ｙ（σ（φ），２）に対応する復号鍵で復号可能な第二暗号文Ｃφ，２となる。そのため仲介装置は、すべての情報提供装置φ（φ＝１，…，Φ）にそれぞれ対応する正しい第二暗号文Ｃφ，２を取得した後に、各第二暗号文Ｃφ，２を出力しているとみなせる。これにより、第二暗号文Ｃφ，２を提供すべき情報提供装置が正しい第二暗号文Ｃφ，２を提供することなく、他の情報提供装置から提供された第二暗号文を取得するといった持ち逃げ問題を抑制できる。すなわち本発明では、暗号文を格納した複数の情報提供装置が、当該暗号文を相手側の情報提供装置で復号可能な暗号文に再暗号化して提供する場合の持ち逃げ問題を抑制できる。
【図面の簡単な説明】
【００１２】
【図１】実施形態の情報提供システムの構成を説明するためのブロック図。
【図２】実施形態の仲介装置の構成を説明するためのブロック図。
【図３】実施形態の情報提供装置の構成を説明するためのブロック図。
【図４】実施形態の入力情報提供部の構成を説明するためのブロック図。
【図５】実施形態の入力情報提供部の構成を説明するためのブロック図。
【図６】実施形態の仲介装置の処理を説明するためのフローチャート。
【図７】実施形態の自己訂正処理を説明するためのフローチャート。
【図８】実施形態の情報提供装置の処理を説明するためのフローチャート。
【図９】ステップＳ２１０３（Ｓ３１０３）の処理を説明するためのフローチャート。
【図１０】ステップＳ４１０３の処理を説明するためのフローチャート。
【図１１】実施形態の仲介装置の構成を説明するためのブロック図。
【図１２】実施形態の仲介装置の処理を説明するためのフローチャート。
【図１３】実施形態の情報提供システムの構成を説明するためのブロック図。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施形態を説明する。
【００１４】
［第一実施形態］
まず、本発明の第一実施形態を説明する。本形態では、２個の情報提供装置が仲介装置を介し、これらが互いに暗号文の提供を行う例を説明する。すなわち、本発明はφ＝１，…，Φ、σ（φ）＝１，…，Φ、σ（φ）≠φ、Φが２以上の整数である場合に適用可能であるが、以下ではΦ＝２、σ（１）＝２、σ（２）＝１の例を説明する。ただし、この例は本発明を限定するものではない。
【００１５】
＜構成＞
図１に例示するように、第一実施形態の情報提供システム１は、例えば、仲介装置１１と２個の情報提供装置１２−１，１２−２とを有する。各装置は情報のやり取りが可能なように構成される。例えば、各装置は伝送線やネットワークや可搬型記録媒体などを経由した情報のやり取りが可能とされている。
【００１６】
本形態では、情報提供装置１２−１が、第一暗号化方式ＥＮＣ１，１に則って平文ｍ１を第一暗号化鍵ｙ（１，１）で暗号化して得られた第一暗号文Ｃ１，１を、第二暗号化方式ＥＮＣ１，２に則って平文ｍ１を第二暗号化鍵ｙ（２，２）で暗号化して得られる第二暗号文Ｃ１，２に再暗号化する能力を仲介装置１１に与える。また、情報提供装置１２−２が、第一暗号化方式ＥＮＣ２，１に則って平文ｍ２を第一暗号化鍵ｙ（２，１）で暗号化した第一暗号文Ｃ２，１を、第二暗号化方式ＥＮＣ２，２に則って平文ｍ２を第二暗号化鍵ｙ（１，２）で暗号化した第二暗号文Ｃ２，２に再暗号化する能力を仲介装置１１に与える。仲介装置１１は、提供された能力を用い、情報提供装置１２−１の第一暗号文Ｃ１，１を第二暗号文Ｃ１，２に再暗号化し、情報提供装置１２−２の第一暗号文Ｃ２，１を第二暗号文Ｃ２，２に再暗号化する。その後、仲介装置１１は、第二暗号文Ｃ１，２を情報提供装置１２−２に出力し、第二暗号文Ｃ２，２を情報提供装置１２−１に出力する。情報提供装置１２−１は、第二復号鍵ｓ（１，２）を用いて第二暗号文Ｃ２，２を復号して平文ｍ２を取得可能である。情報提供装置１２−２は、第二復号鍵ｓ（１，１）を用いて第二暗号文Ｃ１，２を復号して平文ｍ１を取得可能である。
【００１７】
図２に例示するように、第一実施形態の仲介装置１１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部１１０４と第一計算部１１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部１１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と処理部１１１２と最終出力部１１１３と制御部１１１４とを有する。仲介装置１１は、制御部１１１４の制御のもとで各処理を実行する。仲介装置１１の例は、特別なプログラムが読み込まれたＣＰＵ（ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）やＲＡＭ（ｒａｎｄｏｍ−ａｃｃｅｓｓ  ｍｅｍｏｒｙ）を備えた公知又は専用のコンピュータや、サーバ装置やゲートウェイ装置やカードリーダライタ装置や携帯電話などの計算機能と記憶機能とを備えた機器などである。
【００１８】
図３に例示するように、第一実施形態の情報提供装置１２−φ（φ＝１，２）は、例えば、それぞれ、第一出力情報計算部１２０１−φと第二出力情報計算部１２０２−φと鍵記憶部１２０４−φと暗号文記憶部１２０５−φと出力部１２０６−φと復号部１２０７−φと制御部１２０８−φとを有する。情報提供装置１２−φは、制御部１２０８−φの制御のもとで各処理を実行する。情報提供装置１２−φの例は、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータや、携帯電話などの計算機能と記憶機能とを備えた機器や、ＩＣカードやＩＣチップなどの耐タンパ性モジュールなどである。
【００１９】
＜処理の前提＞
Ｇφ，Ｈφが巡回群などの有限可換群であり、Ｘφ，１，Ｘφ，２が群Ｇφに値を持つ確率変数であり、ｘφ，１が確率変数Ｘφ，１の実現値であり、ｘφ，２が確率変数Ｘφ，２の実現値であり、ｆφが群Ｈφの元である第一暗号文Ｃφ，１を群Ｇφの元である第二暗号文ｆφ（Ｃφ，１）＝Ｃφ，２に変換するための関数であるとする。ここで、第一暗号文Ｃφ，１は第一暗号化方式ＥＮＣφ，１に則って平文ｍφを第一暗号化鍵ｙ（φ，１）で暗号化して得られた暗号文であり、第二暗号文Ｃφ，２は第二暗号化方式ＥＮＣφ，２に則って平文ｍφを第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる暗号文である。第一暗号化方式ＥＮＣφ，１や第二暗号化方式ＥＮＣφ，２は、公開鍵暗号方式であってもよいし、共通鍵暗号方式であってもよい。また、第一暗号化方式ＥＮＣφ，１や第二暗号化方式ＥＮＣφ，２は、確率暗号方式であってもよいし、確定暗号方式であってもよい。第一暗号化方式ＥＮＣφ，１と第二暗号化方式ＥＮＣφ，２とが同一の暗号化方式であってもよいし、これらが異なる暗号化方式であってもよい。また、すべての第一暗号化方式ＥＮＣφ，１（φ＝１，…，Φ）が互いに同一の暗号化方式であってもよいし、少なくとも一部のφ’≠φに対する第一暗号化方式ＥＮＣφ’，１が他の第一暗号化方式ＥＮＣφ，１と相違してもよい。また、すべての第二暗号化方式ＥＮＣφ，２（φ＝１，…，Φ）が互いに同一の暗号化方式であってもよいし、少なくとも一部のφ’≠φに対する第二暗号化方式ＥＮＣφ’，２が他の第二暗号化方式ＥＮＣφ，２と相違してもよい。第一暗号化方式ＥＮＣφ，１や第二暗号化方式ＥＮＣφ，２の例は、準同型関数を暗号化関数及び復号関数とする暗号化方式である。そのような例は、ＥｌＧａｍａｌ暗号方式（参考文献１：Taher Elgamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," IEEE Transactions on Information Theory, v. IT-31, n. 4, 1985, pp. 469-472 or CRYPTO 84, pp. 10-18, Springer-Verlag.）や、ＲＳＡ暗号方式（参考文献２：R.L.Rivest,A.Shamir,and L.Adelman, "A Method for Obtaining Digital Signature and Public-key Cryptsystems," MIT Laboratory for Computer Science, Thechnical Memo LCS/TM82, April 4,1977(Revised December 12,1977)）などの公開鍵暗号方式などである。また、Ｇφ＝Ｈφであってもよいし、Ｇφ≠Ｈφであってもよい。すべての群Ｇφ（φ＝１，…，Φ）が互いに同一であってもよいし、少なくとも一部のφ’≠φに対する群Ｇφ’が他の群Ｇφと相違してもよい。また、すべての群Ｈφ（φ＝１，…，Φ）が互いに同一であってもよいし、少なくとも一部のφ’≠φに対する群Ｈφ’が他の群Ｈφと相違してもよい。また、以下では群Ｇφ，Ｈφ上の演算を乗法的に表現する。
【００２０】
第一暗号化鍵ｙ（φ，１）には第一復号鍵ｓ（φ，１）が対応し、第二暗号化鍵ｙ（σ（φ），２）には第二復号鍵ｓ（σ（φ），２）が対応する。第一暗号化方式ＥＮＣφ，１が公開鍵暗号方式である場合、第一暗号化鍵ｙ（φ，１）は公開鍵であり、第一復号鍵ｓ（φ，１）は秘密鍵である。一方、第一暗号化方式ＥＮＣφ，１が共通鍵暗号方式である場合、第一暗号化鍵ｙ（φ，１）及び第一復号鍵は共通鍵である。第二暗号化方式ＥＮＣφ，２が公開鍵暗号方式である場合、第二暗号化鍵ｙ（σ（φ），２）は公開鍵であり、第二復号鍵ｓ（σ（φ），２）は秘密鍵である。一方、第二暗号化方式ＥＮＣφ，２が共通鍵暗号方式である場合、第二暗号化鍵ｙ（σ（φ），２）及び第二復号鍵ｓ（σ（φ），２）は共通鍵である。ｙ（φ，１）＝ｙ（φ，２）であってもよいし、ｙ（φ，１）≠ｙ（φ，２）であってもよい。ｓ（φ，１）＝ｓ（φ，２）であってもよいし、ｓ（φ，１）≠ｓ（φ，２）であってもよい。
【００２１】
また、平文Ｍφを第二暗号化方式ＥＮＣφ，２に則って第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる可能性がある暗号文を要素とする集合を「当該暗号文が属する暗号文の類ＣＬφ（Ｍφ）」と呼ぶ。ここでａ（φ），ｂ（φ）は互いに素な自然数であり、「自然数」とは０以上の整数を表す。ＣＬφ（Ｍφ）とＣＬφ’（Ｍφ’）（φ’≠φ）とは互いに異なる類である。同一の暗号文の類ＣＬφ（Ｍφ）には、同一の平文Ｍφを第二暗号化鍵ｙ（σ（φ），２）でそれぞれ暗号化して得られる可能性がある各暗号文が属する。例えば、第二暗号化方式ＥＮＣφ，２がＥｌＧａｍａｌ暗号方式のような確率暗号方式である場合、同一の平文Ｍφと暗号化鍵ｙ（σ（φ），２）との組に対して複数の暗号文Ｃφ，２が対応するため、同一の暗号文の類ＣＬφ（Ｍφ）にはａ（φ），ｂ（φ）の組みごとに複数の要素が属する。一方、例えば、第二暗号化方式ＥＮＣφ，２がＲＳＡ暗号方式のような確定暗号方式である場合、同一の平文Ｍφと暗号化鍵ｙ（σ（φ），２）との組に対して暗号文Ｃφ，２が一義的に定まるため、同一の暗号文の類ＣＬφ（Ｍφ）にはａ（φ），ｂ（φ）の組みごとに一つの要素のみが属する。ａ（φ），ｂ（φ）の組みごとに同一の暗号文の類ＣＬφ（Ｍφ）に一つの要素のみが属する場合、二つの値が同一の暗号文の類ＣＬφ（Ｍφ）に属することと当該二つの値が等しいこととが等価となる。すなわち、第二暗号化方式が確定暗号方式である場合、二つの値が同一の暗号文の類ＣＬφ（Ｍφ）に属するかの判定は当該二つの値が等しいかを判定することで行うことができる。
【００２２】
また、仲介装置１１（図２）の自然数記憶部１１０１に、互いに素である２つの自然数ａ（φ），ｂ（φ）の組（ａ（φ），ｂ（φ））が複数種類記憶されているものとする。Ｉφを群Ｇφの位数未満の２つの自然数の組で互いに素なものの集合とすると、自然数記憶部１１０１にはＩφの部分集合Ｓφに対応する自然数ａ（φ），ｂ（φ）の組（ａ（φ），ｂ（φ））が記憶されていると考えることができる。また、第一復号鍵ｓ（φ，１）、第二復号鍵ｓ（φ，２）、及び第二暗号化鍵ｙ（σ（φ），２）が情報提供装置１２−φ（図３）の鍵記憶部１２０４−φに格納され、第一暗号文Ｃφ，１∈Ｈφが情報提供装置１２−φの暗号文記憶部１２０５−φに格納されているものとする。
【００２３】
＜処理＞
図６に例示するように、まず、仲介装置１１（図２）の制御部１１１４がφ＝１とする（ステップＳ１１１）。
【００２４】
次に、仲介装置１１は情報提供装置１２−φとの間でφについての自己訂正処理を実行する（ステップＳ１１２）。以下にφについての自己訂正処理を説明する。
【００２５】
［φについての自己訂正処理］
まず、情報提供装置１２−φ（図３）の出力部１２０６−φが、暗号文記憶部１２０５−φから読み出された第一暗号文Ｃφ，１を出力する。第一暗号文Ｃφ，１は仲介装置１１（図２）の入力情報提供部１１０４に入力される。第一暗号文Ｃφ，１は、例えば、情報提供装置１２−σ（φ）によって選択されたものである。また、この処理は複数の第一暗号文Ｃφ，１について実行されてもよいし、既に第一暗号文Ｃφ，１が入力情報提供部１１０４に入力されている場合にはこの処理が省略されてもよい。
【００２６】
図７に例示するように、第一暗号文Ｃφ，１が入力情報提供部１１０４に入力された仲介装置１１の自然数選択部１１０２は、自然数記憶部１１０１に記憶された複数の自然数の組（ａ（φ），ｂ（φ））から１つの自然数の組（ａ（φ），ｂ（φ））をランダムに読み込む。読み込まれた自然数の組（ａ（φ），ｂ（φ））少なくとも一部の情報は、整数計算部１１０３、入力情報提供部１１０４、第一べき乗計算部１１０６及び第二べき乗計算部１１０９に送られる（ステップＳ１１００）。
【００２７】
整数計算部１１０３は、送られた自然数の組（ａ（φ），ｂ（φ））を用いて、ａ’（φ）ａ（φ）＋ｂ’（φ）ｂ（φ）＝１の関係を満たす整数ａ’（φ），ｂ’（φ）を計算する。自然数ａ（φ），ｂ（φ）は互いに素であるため、ａ’（φ）ａ（φ）＋ｂ’（φ）ｂ（φ）＝１の関係を満たす整数ａ’（φ），ｂ’（φ）をEuclidの互除法などの公知のアルゴリズムによって計算することができる。自然数の組（ａ’（φ），ｂ’（φ））の情報は、処理部１１１２に送られる（ステップＳ１１０１）。
【００２８】
制御部１１１４は、ｔ＝１とする（ステップＳ１１０２）。
【００２９】
入力情報提供部１１０４は、入力された第一暗号文Ｃφ，１にそれぞれ対応する群Ｈφの元である第一入力情報τφ，１及び第二入力情報τφ，２を生成して出力する。好ましくは、第一入力情報τφ，１及び第二入力情報τφ，２はそれぞれ第一暗号文Ｃφ，１との関係をかく乱させた情報である。これにより、仲介装置１１は、第一暗号文Ｃφ，１を情報提供装置１２−φに対して隠蔽できる。例えば、情報提供装置１２−φが複数種類の第一暗号文Ｃφ，１を出力していた場合、仲介装置１１は、どの第一暗号文Ｃφ，１に関する処理を行っているのかを情報提供装置１２−φに対して隠蔽できる。また、好ましくは、本形態の第一入力情報τφ，１は自然数選択部１１０２で選択された自然数ｂ（φ）にさらに対応し、第二入力情報τφ，２は自然数選択部１１０２で選択された自然数ａ（φ）にさらに対応する。これにより、情報提供装置１２−φから提供された再暗号化能力を仲介装置１１が高い精度で評価することができる（ステップＳ１１０３）。
【００３０】
図８に例示するように、第一入力情報τφ，１は情報提供装置１２−φ（図３）の第一出力情報計算部１２０１−φに入力され、第二入力情報τφ，２は第二出力情報計算部１２０２−φに入力される（ステップＳ１２００）。
【００３１】
第一出力情報計算部１２０１−φは、第一入力情報τφ，１と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）とを用い、或る確率より大きな確率でｆφ（τφ，１）を正しく計算し、得られた計算結果を第一出力情報ｚφ，１とする（ステップＳ１２０１）。第二出力情報計算部１２０２−φは、第二入力情報τφ，２と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）を用い、或る確率より大きな確率でｆφ（τφ，２）を正しく計算し、得られた演算結果を第二出力情報ｚφ，２とする（ステップＳ１２０２）。なお、関数ｆφの例は、第一暗号化方式ＥＮＣφ，１に則って第一復号鍵ｓ（φ，１）で暗号文を復号して得られる値を、第二暗号化方式ＥＮＣφ，２に則って第二暗号化鍵ｙ（σ（φ），２）で暗号化するための準同型関数である。また、「或る確率」は１００％未満の確率である。「或る確率」の例は無視することができない確率であり、「無視することができない確率」の例は、セキュリティパラメータｋについての広義単調増加関数である多項式を多項式ψ（ｋ）とした場合の１／ψ（ｋ）以上の確率である。すなわち、第一出力情報計算部１２０１−φや第二出力情報計算部１２０２−φは、意図的又は意図的ではない誤差を含んだ計算結果を出力し得る。言い換えると、第一出力情報計算部１２０１−φでの計算結果がｆφ（τφ，１）の場合もあればｆφ（τφ，１）でない場合もあり、第二出力情報計算部１２０２−φでの計算結果がｆφ（τφ，２）の場合もあればｆφ（τφ，２）でない場合もある。第一出力情報計算部１２０１−φは第一出力情報ｚφ，１を出力し、第二出力情報計算部１２０２−φは第二出力情報ｚφ，２を出力する（ステップＳ１２０３）。
【００３２】
図７に戻り、第一出力情報ｚφ，１は仲介装置１１（図２）の第一計算部１１０５に入力され、第二出力情報ｚφ，２は第二計算部１１０８に入力される。これらの第一出力情報ｚφ，１及び第二出力情報ｚφ，２が、情報提供装置１２−φから仲介装置１１に与えられた再暗号化能力に相当する（ステップＳ１１０４）。
【００３３】
第一計算部１１０５は、第一出力情報ｚφ，１から演算結果ｕφ＝ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１を生成する。ここで、ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１を生成（計算）するとは、ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１と定義される式の値を計算することである。式ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。演算結果ｕφは第一べき乗計算部１１０６に送られる（ステップＳ１１０５）。
【００３４】
第一べき乗計算部１１０６はｕφ’＝ｕφａ（φ）を計算する。計算結果ｕφとその計算結果に基づいて計算されたｕφ’との組（ｕφ，ｕφ’）は、第一リスト記憶部１１０７に記憶される（ステップＳ１１０６）。
【００３５】
判定部１１１１は、第一リスト記憶部１１０７に記憶された組（ｕφ，ｕφ’）及び第二リスト記憶部１１１０に記憶された組（ｖφ，ｖφ’）の中で、ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属するものがあるかを判定する。必ずしもＭφを計算できる必要はなく、またＭφ＝ｍφであることまでは判定できなくてもよい（以下同様）。言い換えると、判定部１１１１は、同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組があるか判定する。例えば、第二暗号化方式ＥＮＣφ，２が確定暗号方式の場合、判定部１１１１は、ｕφ’＝ｖφ’であるかを判定する（ステップＳ１１０７）。もし、第二リスト記憶部１１１０に組（ｖφ，ｖφ’）が記憶されていない場合には、このステップＳ１１０７の処理を行わずに、次のステップＳ１１０８の処理を行う。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組があった場合には、ステップＳ１１１４に進む。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組がなかった場合には、ステップＳ１１０８に進む。
【００３６】
ステップＳ１１０８では、第二計算部１１０８が、第二出力情報ｚφ，２から演算結果ｖφ＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２を生成する。演算結果ｖφは第二べき乗計算部１１０９に送られる（ステップＳ１１０８）。
【００３７】
第二べき乗計算部１１０９はｖφ’＝ｖφｂ（φ）を計算する。計算結果ｖφとその計算結果に基づいて計算されたｖφ’との組（ｖφ，ｖφ’）は、第二リスト記憶部１１１０に記憶される（ステップＳ１１０９）。
【００３８】
判定部１１１１は、第一リスト記憶部１１０７に記憶された組（ｕφ，ｕφ’）及び第二リスト記憶部１１１０に記憶された組（ｖφ，ｖφ’）の中で、ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属するものがあるかを判定する。例えば、第二暗号化方式ＥＮＣφ，２が確定暗号方式の場合、判定部１１１１は、ｕφ’＝ｖφ’であるかを判定する（ステップＳ１１１０）。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組があった場合には、ステップＳ１１１４に進む。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組がなかった場合には、ステップＳ１１１１に進む。
【００３９】
ステップＳ１１１１では、制御部１１１４がｔ＝Ｔであるか判定する（ステップＳ１１１１）。Ｔは予め定められた自然数である。Ｔはすべてのφについて同一値であってもよいし、φについての自己訂正処理でのＴの値と、φ’（σ’≠σ，σ’＝１，…，Φ）についての自己訂正処理でのＴの値が相違する場合があってもよい。ｔ＝Ｔであれば、処理部１１１２が、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１１３）、処理を終える。ｔ＝Ｔでない場合には、制御部１１１４は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１（ｔ＋１を新たなｔ）として（ステップＳ１１１２）、ステップＳ１１０３に戻る。
【００４０】
計算をすることができなかった旨の情報（この例では記号「⊥」）は、情報提供装置１２−φが正しく計算を行う信頼性がＴで定められる基準を下回るということを意味する。言い換えれば、Ｔ回の繰り返しで正しい演算を行うことができなかったということを意味する。
【００４１】
ステップＳ１１１４では、処理部１１１２が、同一の暗号文の類ＣＬφ（Ｍφ）に属すると判定されたｕφ’とｖφ’との組に対応するｕφ及びｖφを用いてｕφｂ’（φ）ｖφａ’（φ）を計算して、出力して処理を終える（ステップＳ１１１４）。このように計算されたｕφｂ’（φ）ｖφａ’（φ）は、高い確率で第二暗号文ｆφ（Ｃφ，１）＝Ｃφ，２∈Ｇφとなる（高い確率でｕφｂ’（φ）ｖφａ’（φ）＝ｆφ（Ｃφ，１）となる理由については後述する）。よって、少なくともφについての自己訂正処理を複数回繰り返し、ステップＳ１１１４で得られた値のうち最も頻度の高いｕφｂ’（φ）ｖφａ’（φ）を選択すれば、選択されたｕφｂ’（φ）ｖφａ’（φ）が第２暗号文Ｃφ，２であることの信頼度（確率など）は所定値以上となる。たとえば、セキュリティパラメータをｋとするとき、ｋ回の自己訂正処理を繰り返せば、無視できる確率をのぞいて正しい計算を行うことができる。また、後述するように、設定によっては圧倒的な確率でｕφｂ’（φ）ｖφａ’（φ）＝ｆφ（Ｃφ，１）となる。その場合にはステップＳ１１１４で得られたｕφｂ’（φ）ｖφａ’（φ）が第２暗号文Ｃφ，２であることの信頼度は必ず所定値以上となる（［φについての自己訂正処理］についての説明終わり）。
【００４２】
図６に戻り、仲介装置１１（図２）の処理部１１１２は、φについての自己訂正処理で得られたｕφｂ’（φ）ｖφａ’（φ）が第２暗号文Ｃφ，２であることの信頼度が所定値以上であるかを判定する（ステップＳ１１３）。
【００４３】
ここで得られたｕφｂ’（φ）ｖφａ’（φ）が第２暗号文Ｃφ，２であることの信頼度が所定値以上でなかったと判定された場合、φを更新することなくステップＳ１１２に戻ってステップＳ１１２の処理が再び実行される。例えば、ステップＳ１１１３で計算をすることができなかった旨の情報が出力された場合には、信頼度が所定値以上でなかったと判定される。また、ステップＳ１１１４でｕφｂ’（φ）ｖφａ’（φ）が得られたとしても、φについての自己訂正処理を複数回繰り繰り返さなくてはｕφｂ’（φ）ｖφａ’（φ）の信頼度を評価できない場合には、信頼度を評価できる所定の回数だけφについての自己訂正処理が繰り返されるまで、信頼度が所定値以上でなかったと判定される。
【００４４】
一方、得られたｕφｂ’（φ）ｖφａ’（φ）が第２暗号文Ｃφ，２であることの信頼度が所定値以上であったと判定された場合、処理部１１１２は、信頼度が所定値以上のｕφｂ’（φ）ｖφａ’（φ）を出力し、それが最終出力部１１１３に入力される。例えば、ステップＳ１１１４でｕφｂ’（φ）ｖφａ’（φ）が得られた場合にその信頼度が必ず所定値以上となる設定の場合には、ステップＳ１１１４でｕφｂ’（φ）ｖφａ’（φ）が最終出力部１１１３に入力される。また、φについての自己訂正処理を複数回繰り繰り返さなくてはｕφｂ’（φ）ｖφａ’（φ）の信頼度を評価できない場合であって、かつ、信頼度を評価できる所定の回数だけφについての自己訂正処理が繰り返された場合には、それらの自己訂正処理で得られたｕφｂ’（φ）ｖφａ’（φ）のうち最も頻度の高いものが最終出力部１１１３に入力される。最終出力部１１１３に入力されたｕφｂ’（φ）ｖφａ’（φ）は図示していない最終出力部１１１３内の記憶部に格納され、ステップＳ１１４に進む。
【００４５】
ステップＳ１１４では、制御部１１１４がφ＝Φであるかを判定する（ステップＳ１１４）。ここでφ＝Φでなければ、制御部１１１４はφを１だけインクリメント、すなわちφ＝φ＋１（φ＋１を新たなφ）として（ステップＳ１１５）、ステップＳ１１２に戻って［φについての自己訂正処理］が実行される。一方、φ＝Φであれば、最終出力部１１１３は、最終出力部１１１３内の記憶部（図示せず）に格納されたすべての値ｕφｂ’（φ）ｖφａ’（φ）（φ＝１，…，Φ）を出力する。すなわち、最終出力部１１１３は、上述のようにすべてのφ＝１，…，Φについて値ｕφｂ’（φ）ｖφａ’（φ）が計算された後に、各ｕφｂ’（φ）ｖφａ’（φ）（φ＝１，…，Φ）を出力する。これにより、情報提供装置１２−１及び１２−２による持ち逃げ問題を抑制できる。また、仲介装置１１が第一復号鍵ｓ（φ，１）や第二復号鍵ｓ（φ，２）を利用可能でない場合、仲介装置１１に平文ｍφの情報が知られることはない（ステップＳ１１６）。
【００４６】
各ｕφｂ’（φ）ｖφａ’（φ）は、それぞれ第２暗号文Ｃφ，２として情報提供装置１２−σ（φ）に入力される。本形態では、ｕσ（φ）ｂ’（σ（φ））ｖσ（φ）ａ’（σ（φ））が第二暗号文Ｃσ（φ），２として情報提供装置１２−φ（図３）の復号部１２０７−φに入力される。復号部１２０７−φは、鍵記憶部１２０４−φから第二復号鍵ｓ（φ，２）を読み出し、それを用いて第２暗号文Ｃσ（φ），２を復号し、得られた復号結果を出力する。
【００４７】
≪高い確率でｕφｂ’（φ）ｖφａ’（φ）＝ｆφ（Ｃφ，１）となる理由について≫
Ｘφを群Ｇφに値を持つ確率変数とする。ｗφ∈Ｇφについて、要求を受けるたびに確率変数Ｘφに従った標本ｘφ’に対応するｗφｘφ’を返すものを、ｗφについて誤差Ｘφを持つ標本器（ｓａｍｐｌｅｒ）と呼ぶ。
【００４８】
ｗφ∈Ｇφについて、自然数ａ（φ）が与えられるたびに確率変数Ｘφに従った標本ｘφ’に対応するｗφａ（φ）ｘφ’を返すものを、ｗφについて誤差Ｘφを持つ乱数化可能標本器（ｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒ）と呼ぶ。乱数化可能標本器はａ（φ）＝１として用いられれば標本器として機能する。
【００４９】
本実施形態の入力情報提供部１１０４と第一出力情報計算部１２０１−φと第一計算部１１０５との組み合わせが、ｆφ（Ｃφ，１）について誤差Ｘφ，１を持つ乱数化可能標本器（「第一乱数化可能標本器」と呼ぶ）であり、入力情報提供部１１０４と第二出力情報計算部１２０２−φと第二計算部１１０８との組み合わせが、ｆφ（Ｃφ，１）について誤差Ｘφ，２を持つ乱数化可能標本器（「第二乱数化可能標本器」と呼ぶ）である。
【００５０】
ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属するのは、第一乱数化可能標本器がｕφ＝ｆφ（Ｃφ，１）ｂ（φ）を正しく計算しており、第二乱数化可能標本器がｖφ＝ｆφ（Ｃφ，１）ａ（φ）を正しく計算している（ｘφ，１及びｘφ，２が群Ｇφの単位元ｅφ，ｇである）可能性が高いことを発明者は見出した。説明の簡略化の観点から、この証明は第五実施形態で行う。
【００５１】
第一乱数化可能標本器がｕφ＝ｆφ（Ｃφ，１）ｂ（φ）を正しく計算しており、第二乱数化可能標本器がｖφ＝ｆφ（Ｃφ，１）ａ（φ）を正しく計算しているとき（ｘφ，１及びｘφ，２が群Ｇφの単位元ｅφ，ｇであるとき）、ｕφｂ’（φ）＝（ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１）ｂ’（φ）＝（ｆφ（Ｃφ，１）ｂ（φ）ｅφ，ｇ）ｂ’（φ）＝ｆφ（Ｃφ，１）ｂ（φ）ｂ’（φ）となり、ｖφａ’（φ）＝（ｆφ（Ｃφ，１）ａ（φ）ｘφ，２）ａ’（φ）＝（ｆφ（Ｃφ，１）ａ（φ）ｅφ，ｇ）ａ’（φ）＝ｆφ（Ｃφ，１）ａ（φ）ａ’（φ）となる。そのため、第二暗号化方式が確定暗号方式なのであればｕφｂ’（φ）ｖφａ’（φ）＝ｆφ（Ｃφ，１）（ｂ（φ）ｂ’（φ）＋ａ（φ）ａ’（φ））＝ｆφ（Ｃφ，１）となる。一方、第二暗号化方式が確率暗号方式であったとしてもｆφ（Ｃφ，１）が準同型関数なのであれば、ｕφｂ’（φ）ｖφａ’（φ）＝ｆφ（Ｃφ，１（ｂ（φ）ｂ’（φ）＋ａ（φ）ａ’（φ）））＝ｆφ（Ｃφ，１）となる。
【００５２】
また、（ｑ１，ｑ２）∈Ｉについて、ｉ＝１，２の各々について関数πｉをπｉ（ｑ１，ｑ２）＝ｑｉで定義する。さらに、Ｌ＝ｍｉｎ（♯π１（Ｓ），♯π２（Ｓ））とする。♯・は、集合・の位数である。群Ｇφが巡回群などの有限可換群や位数の計算が困難な群であるときには、仲介装置１１が「⊥」以外を出力するときの出力がｆφ（Ｃφ，１）ではない確率は、無視できる程度の誤差の範囲で高々Ｔ２Ｌ／♯Ｓ程度と期待することができる。もしＬ／♯Ｓが無視できる量でＴが多項式オーダー程度の量であれば、仲介装置１１は圧倒的な確率で正しいｆφ（Ｃφ，１）を出力する。Ｌ／♯Ｓが無視できる量になるようなＳの例には、例えばＳ＝｛（１，ｄ）｜ｄ∈［２，｜Ｇφ｜−１］｝がある。
【００５３】
［第二実施形態］
第二実施形態の情報提供システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した例である。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。以下の説明において、同一の参照番号が付された部分は同一の機能を持つものとし、同一の参照番号が付されたステップは同一の処理を表すものとする。
【００５４】
＜構成＞
図１に例示するように、第二実施形態の情報提供システム２は、仲介装置１１が仲介装置２１に置換され、情報提供装置１２−φが情報提供装置２２−φに置換されたものである。
【００５５】
図２に例示するように、第二実施形態の仲介装置２１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部２１０４と第一計算部２１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部２１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と処理部１１１２と最終出力部１１１３と制御部１１１４とを有する。図４に例示するように、本形態の入力情報提供部２１０４は、例えば、第一乱数生成部２１０４ａと第一入力情報計算部２１０４ｂと第二乱数生成部２１０４ｃと第二入力情報計算部２１０４ｄとを有する。
【００５６】
図３に例示するように、第二実施形態の情報提供装置２２−φ（φ＝１，２）は、例えば、それぞれ、第一出力情報計算部２２０１−φと第二出力情報計算部２２０２−φと鍵記憶部１２０４−φと暗号文記憶部１２０５−φと出力部１２０６−φと復号部１２０７−φと制御部１２０８−φとを有する。
【００５７】
＜処理の前提＞
第二実施形態では、関数ｆφを準同型関数とし、群Ｈφの生成元をμφ，ｈ、群Ｈφの位数をＫφ，Ｈ、νφ＝ｆφ（μφ，ｈ）とする。その他の前提は、仲介装置１１が仲介装置２１に置換され、情報提供装置１２−φが情報提供装置２２−φに置換されている以外、第一実施形態と同一である。
【００５８】
＜処理＞
図６〜図８に例示するように、第二実施形態の処理は第一実施形態のステップＳ１１３のステップＳ１１０３〜Ｓ１１０５，Ｓ１１０８，Ｓ１２００〜Ｓ１２０３が、それぞれ、ステップＳ２１３のステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３に置換されたものである。以下ではステップＳ２１３のステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３の処理のみを説明する。
【００５９】
《ステップＳ２１０３の処理》
仲介装置２１（図２）の入力情報提供部２１０４は、入力された第一暗号文Ｃφ，１にそれぞれ対応する第一入力情報τφ，１及び第二入力情報τφ，２を生成して出力する（図７／ステップＳ２１０３）。以下、図９を用いて本形態のステップＳ２１０３の処理を説明する。
【００６０】
第一乱数生成部２１０４ａ（図４）は、０以上Ｋφ，Ｈ未満の自然数の一様乱数ｒ（φ，１）を生成する。生成された乱数ｒ（φ，１）は、第一入力情報計算部２１０４ｂ及び第一計算部２１０５に送られる（ステップＳ２１０３ａ）。第一入力情報計算部２１０４ｂは、入力された乱数ｒ（φ，１）と第一暗号文Ｃφ，１と自然数ｂ（φ）とを用いて第一入力情報τφ，１＝μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ）を計算する（ステップＳ２１０３ｂ）。
【００６１】
第二乱数生成部２１０４ｃは、０以上Ｋφ，Ｈ未満の自然数の一様乱数ｒ（φ，２）を生成する。生成された乱数ｒ（φ，２）は、第二入力情報計算部２１０４ｄ及び第二計算部２１０８に送られる（ステップＳ２１０３ｃ）。第二入力情報計算部２１０４ｄは、入力された乱数ｒ（φ，２）と第一暗号文Ｃφ，１と自然数ａ（φ）とを用いて第二入力情報τφ，２＝μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ）を計算する（ステップＳ２１０３ｄ）。
【００６２】
第一入力情報計算部２１０４ｂ及び第二入力情報計算部２１０４ｄは、以上のように生成した第一入力情報τφ，１及び第二入力情報τφ，２を出力する（ステップＳ２１０３ｅ）。なお、本形態の第一入力情報τφ，１及び第二入力情報τφ，２は、それぞれ、乱数ｒ（φ，１），ｒ（φ，２）によって第一暗号文Ｃφ，１との関係をかく乱させた情報である。これにより、仲介装置２２は、第一暗号文Ｃφ，１を情報提供装置２２−φに対して隠蔽できる。また、本形態の第一入力情報τφ，１は自然数選択部１１０２で選択された自然数ｂ（φ）にさらに対応し、第二入力情報τφ，２は自然数選択部１１０２で選択された自然数ａ（φ）にさらに対応する。これにより、情報提供装置２２−φから提供された再暗号化能力を仲介装置２１が高い精度で評価することができる。
【００６３】
《ステップＳ２２００〜Ｓ２２０３の処理》
図８に例示するように、まず、第一入力情報τφ，１＝μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ）が情報提供装置２２−φ（図３）の第一出力情報計算部２２０１−φに入力され、第二入力情報τφ，２＝μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ）が第二出力情報計算部２２０２−φに入力される（ステップＳ２２００）。
【００６４】
第一出力情報計算部２２０１−φは、第一入力情報τφ，１＝μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ）と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）とを用い、或る確率より大きな確率でｆφ（μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ））を正しく計算し、得られた計算結果を第一出力情報ｚφ，１とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部２２０１−φでの計算結果がｆφ（μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ））となる場合もあれば、ｆφ（μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ））とならない場合もある。なお、関数ｆφの例は、第一暗号化方式ＥＮＣφ，１に則って第一復号鍵ｓ（φ，１）で暗号文を復号して得られる値を、第二暗号化方式ＥＮＣφ，２に則って第二暗号化鍵ｙ（σ（φ），２）で暗号化するための準同型関数である。このような関数ｆφに対応する第一暗号化方式ＥＮＣφ，１や第二暗号化方式ＥＮＣφ，２の例はＲＳＡ暗号方式である（ステップＳ２２０１）。
【００６５】
第二出力情報計算部２２０２−φは、第二入力情報τφ，２＝μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ）と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）とを用い、或る確率より大きな確率でｆφ（μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ））を正しく計算し、得られた計算結果を第二出力情報ｚφ，２とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部２２０２−φでの計算結果がｆφ（μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ））となる場合もあれば、ｆφ（μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ））とならない場合もある（ステップＳ２２０２）。
【００６６】
第一出力情報計算部２２０１−φは第一出力情報ｚφ，１を出力し、第二出力情報計算部２２０２−φは第二出力情報ｚφ，２を出力する（ステップＳ２２０３）。
【００６７】
《ステップＳ２１０４及びＳ２１０５の処理》
図７に戻り、第一出力情報ｚφ，１は仲介装置２１（図２）の第一計算部２１０５に入力され、第二出力情報ｚφ，２は第二計算部２１０８に入力される。これらの第一出力情報ｚφ，１及び第二出力情報ｚφ，２が、情報提供装置２２−φから仲介装置２１に与えられた再暗号化能力に相当する（ステップＳ２１０４）。
【００６８】
第一計算部２１０５は、入力された乱数ｒ（φ，１）及び第一出力情報ｚφ，１を用いてｚφ，１νφ−ｒ（φ，１）を計算してその計算結果をｕφとする。計算結果ｕφは、第一べき乗計算部１１０６に送られる。ここで、ｕφ＝ｚφ，１νφ−ｒ（φ，１）＝ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１となる。すなわち、ｚφ，１νφ−ｒ（φ，１）は、ｆφ（Ｃφ，１）について誤差Ｘφ，１を持つ乱数化可能標本器の出力となる。その理由については後述する（ステップＳ２１０５）。
【００６９】
《ステップＳ２１０８の処理》
第二計算部２１０８は、入力された乱数ｒ（φ，２）及び第二出力情報ｚφ，２を用いてｚφ，２νφ−ｒ（φ，２）を計算してその計算結果をｖφとする。計算結果ｖφは、第二べき乗計算部１１０９に送られる。ここで、ｖφ＝ｚφ，２νφ−ｒ（φ，２）＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２となる。すなわち、ｚφ，２νφ−ｒ（φ，２）は、ｆφ（Ｃφ，１）について誤差Ｘφ，２を持つ乱数化可能標本器の出力となる。その理由については後述する（ステップＳ２１０８）。
【００７０】
≪ｚφ，１νφ−ｒ（φ，１），ｚφ，２νφ−ｒ（φ，２）がｆφ（Ｃφ，１）についてそれぞれ誤差Ｘφ，１，Ｘφ，２を持つ乱数化可能標本器の出力となる理由について≫
ｃを自然数、Ｒ及びＲ’を乱数として、情報提供装置２２−φがμφ，ｈＲＣφ，１ｃを用いて行う計算の計算結果をＢ（μφ，ｈＲＣφ，１ｃ）とする。すなわち、第一出力情報計算部２２０１−φや第二出力情報計算部２２０２−φが仲介装置２１に返す計算結果をｚφ＝Ｂ（μφ，ｈＲＣφ，１ｃ）とする。さらに、群Ｇφに値を持つ確率変数ＸφをＸφ＝Ｂ（μφ，ｈＲ’）ｆφ（μφ，ｈＲ’）−１と定義する。
【００７１】
このとき、ｚφνφ−Ｒ＝Ｂ（μφ，ｈＲＣφ，１ｃ）ｆ（μφ，ｈ）−Ｒ＝Ｘφｆφ（μφ，ｈＲＣφ，１ｃ）ｆφ（μφ，ｈ）−Ｒ＝Ｘφｆφ（μφ，ｈ）Ｒｆφ（Ｃφ，１）ｃｆφ（μφ，ｈ）−Ｒ＝ｆφ（Ｃφ，１）ｃＸφとなる。すなわち、ｚφνφ−Ｒは、ｆφ（Ｃφ，１）について誤差Ｘφを持つ乱数化可能標本器の出力となる。
【００７２】
上記式展開において、Ｘφ＝Ｂ（μφ，ｈＲ’）ｆφ（μφ，ｈＲ’）−１＝Ｂ（μφ，ｈＲＣφ，１ｃ）ｆφ（μφ，ｈＲＣφ，１ｃ）−１であり、Ｂ（μφ，ｈＲＣφ，１ｃ）＝Ｘφｆφ（μφ，ｈＲＣφ，１ｃ）であるという性質を用いている。この性質は、関数ｆφが準同型関数であり、Ｒ及びＲ’が乱数であることに基づく。
【００７３】
したがって、ａ（φ），ｂ（φ）が自然数、ｒ（φ，１），ｒ（φ，２）が乱数であることを考慮すると、同様に、ｚφ，１ν−ｒ（φ，１），ｚφ，２ν−ｒ（φ，２）がｆφ（Ｃφ，１）についてそれぞれ誤差Ｘφ，１，Ｘφ，２を持つ乱数化可能標本器の出力となるのである。
【００７４】
［第三実施形態］
第三実施形態は第二実施形態の変形例であり、ａ（φ）＝１やｂ（φ）＝１のときに前述した標本器によってｕφ又はｖφの値を計算する。一般に乱数化可能標本器よりも標本器の計算量は小さい。ａ（φ）＝１やｂ（φ）＝１のときに乱数化可能標本器に代わり、標本器が計算を行うことで、情報提供システムの計算量を小さくすることができる。以下、第一実施形態及び第二実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。
【００７５】
＜構成＞
図１に例示するように、第三実施形態の情報提供システム３は、仲介装置２１が仲介装置３１に置換され、情報提供装置２２−φが情報提供装置３２−φに置換されたものである。
【００７６】
図２に例示するように、第三実施形態の仲介装置３１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部２１０４と第一計算部２１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部２１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と処理部１１１２と最終出力部１１１３と制御部１１１４と第三計算部３１０９とを有する。
【００７７】
図３に例示するように、第三実施形態の情報提供装置３２−φは、例えば、第一出力情報計算部２２０１−φと第二出力情報計算部２２０２−φと鍵記憶部１２０４−φと暗号文記憶部１２０５−φと出力部１２０６−φと復号部１２０７−φと制御部１２０８−φと第三出力情報計算部３２０３−φとを有する。
【００７８】
＜処理＞
次に本形態の処理を説明する。第二実施形態との相違点を説明する。
【００７９】
図６〜図８に例示するように、第三実施形態の処理は第二実施形態のステップＳ２１３のステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３が、それぞれ、ステップＳ３１３のステップＳ３１０３〜Ｓ３１０５，Ｓ３１０８，Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９に置換されたものである。以下ではステップＳ３１３のステップＳ３１０３〜Ｓ３１０５，Ｓ３１０８，Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理を中心に説明する。
【００８０】
《ステップＳ３１０３の処理》
仲介装置３１（図２）の入力情報提供部３１０４は、入力された第一暗号文Ｃφ，１にそれぞれ対応する第一入力情報τφ，１及び第二入力情報τφ，２を生成して出力する（図７／ステップＳ３１０３）。
【００８１】
以下、図９を用いて本形態のステップＳ３１０３の処理を説明する。
【００８２】
制御部１１１４（図２）は、自然数選択部１１０２で選択された自然数（ａ（φ），ｂ（φ））に応じて入力情報提供部３１０４を制御する。
【００８３】
制御部１１１４でｂ（φ）が１であるかが判定され（ステップＳ３１０３ａ）、ｂ（φ）≠１であると判定された場合、前述のステップＳ２１０３ａ及びＳ２１０３ｂの処理が実行され、ステップＳ３１０３ｇに進む。
【００８４】
一方、ステップＳ３１０３ａでｂ（φ）＝１であると判定された場合、第三乱数生成部３１０４ｅが、０以上Ｋφ，Ｈ未満の自然数の乱数ｒ（φ，３）を生成する。生成された乱数ｒ（φ，３）は第三入力情報計算部３１０４ｆ及び第三計算部３１０９に送られる（ステップＳ３１０３ｂ）。第三入力情報計算部３１０４ｆは、入力された乱数ｒ（φ，３）と第一暗号文Ｃφ，１とを用いてＣφ，１ｒ（φ，３）を計算し、これを第一入力情報τφ，１とする（ステップＳ３１０３ｃ）。その後、ステップＳ３１０３ｇに進む。
【００８５】
ステップＳ３１０３ｇでは、制御部１１１４でａ（φ）が１であるかが判定され（ステップＳ３１０３ｇ）、ａ（φ）≠１であると判定された場合、前述のステップＳ２１０３ｃ及びステップＳ２１０３ｄの処理が実行される。
【００８６】
一方、ステップＳ３１０３ｇでａ（φ）＝１であると判定された場合、第三乱数生成部３１０４ｅが、０以上Ｋφ，Ｈ未満の自然数の乱数ｒ（φ，３）を生成する。生成された乱数ｒ（φ，３）は第三入力情報計算部３１０４ｆに送られる（ステップＳ３１０３ｈ）。第三入力情報計算部３１０４ｆは、入力された乱数ｒ（φ，３）と第一暗号文Ｃφ，１とを用いてＣφ，１ｒ（φ，３）を計算し、これを第二入力情報τφ，２とする（ステップＳ３１０３ｉ）。
【００８７】
第一入力情報計算部２１０４ｂ、第二入力情報計算部２１０４ｄ、第三入力情報計算部３１０４ｆは、以上のように生成した第一入力情報τφ，１及び第二入力情報τφ，２を対応する自然数（ａ（φ），ｂ（φ））の情報とともに出力する（ステップＳ３１０３ｅ）。なお、本形態の第一入力情報τφ，１及び第二入力情報τφ，２は、それぞれ、乱数ｒ（φ，１），ｒ（φ，２），ｒ（φ，３）によって第一暗号文Ｃφ，１との関係をかく乱させた情報である。これにより、仲介装置３１は、第一暗号文Ｃφ，１を情報提供装置３２−φに対して隠蔽できる。
【００８８】
《Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理》
以下、図８を用いて本形態のＳ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理を説明する。
【００８９】
制御部１２０８−φ（図３）は、入力された自然数（ａ（φ），ｂ（φ））に応じ、第一出力情報計算部２２０１−φ、第二出力情報計算部２２０２−φ、及び第三出力情報計算部３２０３−φを制御する。
【００９０】
制御部１２０８−φの制御に基づき、ｂ（φ）≠１の場合の第一入力情報τφ，１＝μφ，ｈｒ（φ，１）Ｃφ，１ｂ（φ）は情報提供装置３２−φ（図３）の第一出力情報計算部２２０１−φに入力され、ａ（φ）≠１の場合の第二入力情報τφ，２＝μφ，ｈｒ（φ，２）Ｃφ，１ａ（φ）は第二出力情報計算部２２０２−φに入力される。また、ｂ（φ）＝１の場合の第一入力情報τφ，１＝Ｃφ，１ｒ（φ，３）やａ（φ）＝１の場合の第二入力情報τφ，２＝Ｃφ，１ｒ（φ，３）は第三出力情報計算部３２０３−φに入力される（ステップＳ３２００）。
【００９１】
制御部１１１４でｂ（φ）が１であるかが判定され（ステップＳ３２０５）、ｂ（φ）≠１であると判定された場合、前述のステップＳ２２０１の処理が実行される。その後、制御部１１１４でａ（φ）が１であるかが判定され（ステップＳ３２０８）、ａ（φ）≠１であると判定された場合、前述したステップＳ２２０２の処理が実行されてステップＳ３２０３に進む。
【００９２】
一方、ステップＳ３２０８でａ（φ）＝１であると判定された場合、第三出力情報計算部３２０３−φは、第二入力情報τφ，２＝Ｃφ，１ｒ（φ，３）と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）とを用い、或る確率より大きな確率でｆφ（Ｃφ，１ｒ（φ，３））を正しく計算し、得られた計算結果を第三出力情報ｚφ，３とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部３２０３−φでの計算結果がｆφ（Ｃφ，１ｒ（φ，３））となる場合もあれば、ｆφ（Ｃφ，１ｒ（φ，３））とならない場合もある（ステップＳ３２０９）。その後、ステップＳ３２０３に進む。
【００９３】
また、ステップＳ３２０５でｂ（φ）＝１であると判定された場合、第三出力情報計算部３２０３−φは、第二入力情報τφ，１＝Ｃφ，１ｒ（φ，３）と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）とを用い、或る確率より大きな確率でｆφ（Ｃφ，１ｒ（φ，３））を正しく計算し、得られた計算結果を第三出力情報ｚφ，３とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部３２０３−φでの計算結果がｆφ（Ｃφ，１ｒ（φ，３））となる場合もあれば、ｆφ（Ｃφ，１ｒ（φ，３））とならない場合もある（ステップＳ３２０６）。
【００９４】
その後、制御部１１１４でａ（φ）が１であるかが判定され（ステップＳ３２０７）、ａ（φ）＝１であると判定された場合にはステップＳ３２０３に進み、ａ（φ）≠１であると判定された場合にはステップＳ２２０２に進む。
【００９５】
ステップＳ３２０３では、第一出力情報ｚφ，１を生成した第一出力情報計算部２２０１−φは第一出力情報ｚφ，１を出力し、第二出力情報ｚφ，２を生成した第二出力情報計算部２２０２−φは第二出力情報ｚφ，２を出力し、第三出力情報ｚφ，３を生成した第三出力情報計算部３２０２は第三出力情報ｚφ，３を出力する（ステップＳ３２０３）。
【００９６】
《ステップＳ３１０４及びＳ３１０５の処理》
図７に戻り、制御部１１１４の制御のもと、第一出力情報ｚφ，１は仲介装置３１（図２）の第一計算部２１０５に入力され、第二出力情報ｚφ，２は第二計算部２１０８に入力され、第三出力情報ｚφ，３は第三計算部３１０９に入力される（ステップＳ３１０４）。
【００９７】
ｂ（φ）≠１であれば、第一計算部２１０５が、前述のステップＳ２１０５の処理によってｕφを生成し、ｂ（φ）＝１であれば、第三計算部３１０９が、ｚφ，３１／ｒ（φ，３）を計算してその計算結果をｕφとする。計算結果ｕφは第一べき乗計算部１１０６に送られる。ここで、ｂ（φ）＝１の場合、ｕφ＝ｚφ，３１／ｒ（φ，３）＝ｆφ（Ｃφ，１）ｘφ，３となる。すなわち、ｚφ，３１／ｒ（φ，３）は、ｆφ（Ｃφ，１）について誤差Ｘφ，３を持つ標本器となる。その理由については後述する（ステップＳ３１０５）。
【００９８】
《ステップＳ３１０８の処理》
ａ（φ）≠１であれば、第二計算部２１０８が、前述のステップＳ２１０８の処理によってｖφを生成し、ａ（φ）＝１であれば、第三計算部３１０９が、ｚφ，３１／ｒ（φ，３）を計算してその計算結果をｖφとする。計算結果ｖφは第二べき乗計算部１１０９に送られる。ここで、ａ（φ）＝１の場合、ｖφ＝ｚφ，３１／ｒ（φ，３）＝ｆφ（Ｃφ，１）ｘφ，３となる。すなわち、ｚφ，３１／ｒ（φ，３）は、ｆφ（Ｃφ，１）について誤差Ｘφ，３を持つ標本器となる。その理由については後述する（ステップＳ３１０８）。
【００９９】
なお、ｚφ，３１／ｒ（φ，３）の計算、すなわちｚφ，３のべき乗根の計算が困難な場合には、次のようにしてｕφ及び／又はｖφを計算してもよい。第三計算部３１０９は、乱数ｒ（φ，３）とその乱数ｒ（φ，３）に基づいて計算されたｚφ，３の組を順次（α１，β１），（α２，β２），…，（αｍ，βｍ），…として図示していない記憶部に記憶する。ｍは自然数である。第三計算部３１０９は、α１，α２，…，αｍの最小公倍数が１になれば、γ１，γ２，…，γｍを整数としてγ１α１＋γ２α２＋…＋γｍαｍ＝１となるγ１，γ２，…，γｍを計算して、そのγ，γ２，…，γｍを用いてΠｉ＝１ｍβｉγｉ＝β１γ１β２γ２…βｍγｍを計算して、その計算結果をｕφ及び／又はｖφとしてもよい。
【０１００】
≪ｚφ，３１／ｒ（φ，３）がｆφ（Ｃφ，１）について誤差Ｘφ，３を持つ標本器となる理由について≫
Ｒを乱数として、情報提供装置３２−φがＣφ，１Ｒを用いて行う計算の計算結果をＢ（Ｃφ，１Ｒ）とする。すなわち、第一出力情報計算部２２０１−φや第二出力情報計算部２２０２−φや第三出力情報計算部３２０３−φが仲介装置３１に返す計算結果をｚφ＝Ｂ（Ｃφ，１Ｒ）とする。さらに、群Ｇφに値を持つ確率変数ＸφをＸφ＝Ｂ（Ｃφ，１Ｒ）１／Ｒｆφ（Ｃφ，１）−１と定義する。
【０１０１】
このとき、ｚφ１／Ｒ＝Ｂ（Ｃφ，１Ｒ）１／Ｒ＝Ｘφｆφ（Ｃφ，１）＝ｆφ（Ｃφ，１）Ｘφとなる。すなわち、ｚφ１／Ｒは、ｆφ（Ｃφ，１）について誤差Ｘφを持つ標本器となる。
【０１０２】
上記式展開において、Ｘφ＝Ｂ（Ｃφ，１Ｒ）１／Ｒｆφ（Ｃφ，１Ｒ）−１であり、Ｂ（Ｃφ，１Ｒ）１／Ｒ＝Ｘφｆφ（Ｃφ，１Ｒ）であるという性質を用いている。この性質は、Ｒが乱数であることに基づく。
【０１０３】
したがって、ｒ（φ，３）が乱数であることを考慮すると、同様に、ｚφ１／Ｒがｆφ（Ｃφ，１）について誤差Ｘφ，３を持つ標本器となるのである。
【０１０４】
［第四実施形態］
第四実施形態の情報提供システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した他の例である。具体的には、第二暗号化方式ＥＮＣφ，２がＥｌＧａｍａｌ暗号方式であり、関数ｆφが準同型関数である例を示す。なお、第一暗号化方式ＥＮＣφ，１には特に限定はなく、第一暗号化方式ＥＮＣφ，１はＥｌＧａｍａｌ暗号方式のような確率暗号方式であってもよいし、ＲＳＡ暗号方式のような確定暗号方式であってもよい。
【０１０５】
以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。
【０１０６】
図１に例示するように、第四実施形態の情報提供システム４は、仲介装置１１が仲介装置４１に置換され、情報提供装置１２−φが情報提供装置４２−φに置換されたものである。
【０１０７】
図２に例示するように、第四実施形態の仲介装置４１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部４１０４と第一計算部４１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部４１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部４１１１と処理部１１１２と最終出力部１１１３と制御部１１１４とを有する。図５に例示するように、本形態の入力情報提供部４１０４は、例えば、第一乱数生成部４１０４ａと第一入力情報計算部４１０４ｂと第二乱数生成部４１０４ｃと第二入力情報計算部４１０４ｄと鍵記憶部４１０４ｅとを有する。
【０１０８】
図３に例示するように、第四実施形態の情報提供装置４２−φは、例えば、第一出力情報計算部４２０１−φと第二出力情報計算部４２０２−φと鍵記憶部１２０４−φと暗号文記憶部１２０５−φと出力部１２０６−φと復号部１２０７−φと制御部１２０８−φとを有する。
【０１０９】
＜処理の前提＞
第四実施形態では、群Ｇφが巡回群などの有限可換群Ｇφ，１，Ｇφ，２の直積Ｇφ，１×Ｇφ，２、μφ，ｇ１が群Ｇφ，１の生成元、μφ，ｇ２が群Ｇφ，２の生成元、第二暗号化鍵ｙ（σ（φ），２）がμφ，ｇ２ｓ（σ（φ），２）、第二暗号文Ｃφ，２が（μφ，ｇ１ｒ（φ），ｍφｙ（σ（φ），２）ｒ（φ））∈Ｇφ，１×Ｇφ，２、ｒ（φ）が整数の乱数、値ｕφａ（φ）が（ｃφ，１ｕ，ｃφ，２ｕ）∈Ｇφ，１×Ｇφ，２、値ｖφｂ（φ）が（ｃφ，１ｖ，ｃφ，２ｖ）∈Ｇφ，１×Ｇφ，２である。Ｇφ，１＝Ｇφ，２であってもよいし、Ｇφ，１≠Ｇφ，２であってもよい。また、前述のように第一暗号化方式ＥＮＣφ，１には限定はないが、例えば第一暗号化方式ＥＮＣφ，１がＥｌＧａｍａｌ暗号方式である場合には、群Ｈφが巡回群などの有限可換群Ｈφ，１，Ｈφ，２の直積Ｈφ，１×Ｈφ，２、ｒ’（φ）が整数の乱数、μφ，ｈ１が群Ｈφ，１の生成元、μφ，ｈ２が群Ｈφ，２の生成元、第一暗号化鍵ｙ（φ，１）がμφ，ｈ２ｓ（φ，１）、第一暗号文Ｃφ，１が（μφ，ｈ１ｒ’（φ），ｍφｙ（φ，１）ｒ’（φ））∈Ｈφ，１×Ｈφ，２となる。Ｈφ，１＝Ｈφ，２であってもよいし、Ｈφ，１≠Ｈφ，２であってもよい。
【０１１０】
なお、Α＝（α１，α２）∈Ｇφ，１×Ｇφ，２，Β＝（β１，β２）∈Ｇφ，１×Ｇφ，２，及びεが自然数である場合、Αεは（α１ε，α２ε）を表し、Α−εは（α１−ε，α２−ε）を表し、ΑΒは（α１β１，α２β２）を表す。同様に、εが自然数、Α＝（α１，α２）∈Ｈφ，１×Ｈφ，２，Β＝（β１，β２）∈Ｈφ，１×Ｈφ，２である場合、Αεは（α１ε，α２ε）を表し、Α−εは（α１−ε，α２−ε）を表し、ΑΒは（α１β１，α２β２）を表す。また、ｅφ（α，β）を（α，β）∈Ｇφ，１×Ｇφ，２に対して巡回群などの有限可換群Ｇφ，Ｔの元を与える双線形写像とする。双線形写像の例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数やアルゴリズムである（参考文献３：Alfred. J. Menezes，"ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS，" KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81や、参考文献４：RFC 5091, "Identity-Based Cryptography Standard (IBCS) #1," Supersingular Curve Implementations of the BF and BB1 Cryptosystems等参照）。また、第一暗号化鍵ｙ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）が、仲介装置１１の入力情報提供部４１０４が含む鍵記憶部４１０４ｅに格納されているものとする。
【０１１１】
＜処理＞
図６〜図８に例示するように、第四実施形態の処理は第一実施形態のステップＳ１１３のステップＳ１１０３〜Ｓ１１０５，Ｓ１１０７，Ｓ１１０８，Ｓ１１１０，Ｓ１２００〜Ｓ１２０３が、それぞれ、ステップＳ４１３のステップＳ４１０３〜Ｓ４１０５，Ｓ４１０７，Ｓ４１０８，Ｓ４１１０，Ｓ４２００〜Ｓ４２０３に置換されたものである。以下ではステップＳ４１３のステップＳ４１０３〜Ｓ４１０５，Ｓ４１０７，Ｓ４１０８，Ｓ４１１０，Ｓ４２００〜Ｓ４２０３の処理のみを説明する。
【０１１２】
《ステップＳ４１０３の処理》
仲介装置４１（図２）の入力情報提供部４１０４は、入力された第一暗号文Ｃφ，１に対応する第一入力情報τφ，１及び第二入力情報τφ，２を生成して出力する（図７／ステップＳ４１０３）。以下、図１０を用いて本形態のステップＳ４１０３の処理を説明する。
【０１１３】
第一乱数生成部４１０４ａ（図５）は、群Ｈφの任意の元ｈｒφ，１∈Ｈφを生成する。本形態では群Ｈφからランダムかつ一様に元ｈｒφ，１が選択される（一様乱数）。生成された元ｈｒφ，１は、第一入力情報計算部４１０４ｂ、及び第一計算部４１０５に送られる（ステップＳ４１０３ａ）。
【０１１４】
第一入力情報計算部４１０４ｂは、自然数選択部１１０２で選択された自然数ｂ（φ）、第一暗号文Ｃφ，１、元ｈｒφ，１、及び鍵記憶部４１０４ｅから抽出した第一暗号化鍵ｙ（φ，１）を用い、第一入力情報τφ，１としてＣφ，１ｂ（φ）Ｃφ，１’を計算する（ステップＳ４１０３ｂ）。なお、Ｃφ，１’は、第一暗号化方式ＥＮＣφ，１に則って元ｈｒφ，１を第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元である。
【０１１５】
第二乱数生成部４１０４ｃは、群Ｈφの任意の元ｈｒφ，２∈Ｈφを生成する。本形態では群Ｈφからランダムかつ一様に元ｈｒφ，２が選択される（一様乱数）。生成された元ｈｒφ，２は、第二入力情報計算部４１０４ｄ、及び第二計算部４１０８に送られる（ステップＳ４１０３ｃ）。
【０１１６】
第二入力情報計算部４１０４ｂは、自然数選択部１１０２で選択された自然数ａ（φ）、第一暗号文Ｃφ，１、元ｈｒφ，２、及び鍵記憶部４１０４ｅから抽出した第一暗号化鍵ｙ（φ，１）を用い、第二入力情報τφ，２としてＣφ，１ａ（φ）Ｃφ，１”を計算する（ステップＳ４１０３ｄ）。なお、Ｃφ，１”は、第一暗号化方式ＥＮＣφ，１に則って元ｈｒφ，２を第一暗号化鍵ｙ（φ，１）で暗号化して得られた群Ｈφの元である。
【０１１７】
第一入力情報計算部４１０４ｂは、以上のように生成した第一入力情報τφ，１＝Ｃφ，１ｂ（φ）Ｃφ，１’を出力する。第二入力情報計算部４１０４ｄは、以上のように生成した第二入力情報τφ，２＝Ｃφ，１ａ（φ）Ｃφ，１”を出力する（ステップＳ４１０３ｅ）。
【０１１８】
《ステップＳ４２００〜Ｓ４２０３の処理》
図８に例示するように、まず、第一入力情報τφ，１＝Ｃφ，１ｂ（φ）Ｃφ，１’が情報提供装置４２−φ（図３）の第一出力情報計算部４２０１−φに入力され、第二入力情報τφ，２＝Ｃφ，１ａ（φ）Ｃφ，１”が第二出力情報計算部４２０２−φに入力される（ステップＳ４２００）。
【０１１９】
第一出力情報計算部４２０１−φは、第一入力情報τφ，１＝Ｃφ，１ｂ（φ）Ｃφ，１’と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）とを用い、或る確率より大きな確率でｆφ（Ｃφ，１ｂ（φ）Ｃφ，１’）を正しく計算し、計算結果を第一出力情報ｚφ，１とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部４２０１−φでの計算結果がｆφ（Ｃφ，１ｂ（φ）Ｃφ，１’）となる場合もあれば、ｆφ（Ｃφ，１ｂ（φ）Ｃφ，１’）とならない場合もある（ステップＳ４２０１）。
【０１２０】
なお、本形態の関数ｆφは、第一暗号化方式ＥＮＣφ，１に則って第一復号鍵ｓ（φ，１）で暗号文を復号して得られる値をＥｌＧａｍａｌ暗号方式に則って第二暗号化鍵ｙ（σ（φ），２）で暗号化するための準同型関数である。例えば、第一暗号化方式ＥＮＣφ，１も第二暗号化方式ＥＮＣφ，２もＥｌＧａｍａｌ暗号方式で或る場合、関数ｆφは、ＥｌＧａｍａｌ暗号方式に則って第一復号鍵ｓ（φ，１）で暗号文を復号して得られる値を、ＥｌＧａｍａｌ暗号方式に則って第二暗号化鍵ｙ（σ（φ），２）で暗号化するための準同型関数である。
【０１２１】
第二出力情報計算部４２０２−φは、第二入力情報τφ，２＝Ｃφ，１ａ（φ）Ｃφ，１”と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）とを用い、或る確率より大きな確率でｆφ（Ｃφ，１ａ（φ）Ｃφ，１”）を正しく計算可能であり、得られた計算結果を第二出力情報ｚφ，２とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部４２０２−φでの計算結果がｆφ（Ｃφ，１ａ（φ）Ｃφ，１”）となる場合もあれば、ｆφ（Ｃφ，１ａ（φ）Ｃφ，１”）とならない場合もある（ステップＳ４２０２）。
【０１２２】
第一出力情報計算部４２０１−φは第一出力情報ｚφ，１を出力し、第二出力情報計算部４２０２−φは第二出力情報ｚφ，２を出力する（ステップＳ４２０３）。
【０１２３】
《ステップＳ４１０４及びＳ４１０５の処理》
図７に戻り、第一出力情報ｚφ，１は仲介装置４１（図２）の第一計算部４１０５に入力され、第二出力情報ｚφ，２は第二計算部４１０８に入力される（ステップＳ４１０４）。
【０１２４】
第一計算部４１０５は、入力された第一出力情報ｚφ，１、元ｈｒφ，１、及び鍵記憶部４１０４ｅ（図５）から読み出した第二暗号化鍵ｙ（σ（φ），２）を用い、ｚφ，１（Ｃφ，２’）−１を計算してその計算結果をｕφとする（ステップＳ４１０５）。なお、Ｃφ，２’は、第二暗号化方式ＥＮＣφ，２に則って元ｈｒφ，１を第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元である。計算結果ｕφは、第一べき乗計算部１１０６に送られる。ここで、ｕφ＝ｚφ，１（Ｃφ，２’）−１＝ｆφ（Ｃφ，１）ｂ（φ）ｘφ，１となる。すなわち、ｚφ，１（Ｃφ，２’）−１は、ｆφ（Ｃφ，１）について誤差Ｘφ，１を持つ乱数化可能標本器の出力となる。その理由については後述する。
【０１２５】
《ステップＳ４１０８の処理》
第二計算部４１０８は、入力された第二出力情報ｚφ，２、元ｈｒφ，２、及び鍵記憶部４１０４ｅ（図５）から読み出した第二暗号化鍵ｙ（σ（φ），２）を用い、ｚφ，２（Ｃφ，２”）−１を計算してその計算結果をｖφとする。なお、Ｃφ，２”は、第二暗号化方式ＥＮＣφ，２に則って元ｈｒφ，２を第二暗号化鍵ｙ（σ（φ），２）で暗号化して得られる群Ｇφの元である。計算結果ｖφは、第二べき乗計算部１１０９に送られる。ここで、ｖφ＝ｚφ，２（Ｃφ，２”）−１＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２となる。すなわち、ｚφ，２（Ｃφ，２”）−１は、ｆφ（Ｃφ，１）について誤差Ｘφ，２を持つ乱数化可能標本器の出力となる。その理由については後述する。
【０１２６】
《ステップＳ４１０７の処理》
判定部４１１１は、第一リスト記憶部１１０７に記憶された組（ｕφ，ｕφ’）及び第二リスト記憶部１１１０に記憶された組（ｖφ，ｖφ’）の中で、ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属するものがあるかを判定する。本形態の判定部４１１１は、ｕφ’＝（ｃφ，１ｕ，ｃφ，２ｕ）及びｖφ’＝（ｃφ，１ｖ，ｃφ，２ｖ）に対して、関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を満たすものがあるかを判定する（ステップＳ４１０７）。ｕφ’とｖφ’がこの関係を満たすかを判定することで、ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属することを判定できる理由については後述する。
【０１２７】
もし、第二リスト記憶部１１１０に組（ｖφ，ｖφ’）が記憶されていない場合には、このステップＳ４１０７の処理を行わずに、次のステップＳ１１０８の処理を行う。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組があった場合（上記の関係を満たすｕφ’とｖφ’との組があった場合）には、ステップＳ１１１４に進む。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組がなかった場合には、ステップＳ４１０８に進む。
【０１２８】
《ステップＳ４１１０の処理》
判定部４１１１は、第一リスト記憶部１１０７に記憶された組（ｕφ，ｕφ’）及び第二リスト記憶部４１１０に記憶された組（ｖφ，ｖφ’）の中で、ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属するものがあるかを判定する。本形態の判定部４１１１は、ｕφ’＝（ｃφ，１ｕ，ｃφ，２ｕ）及びｖφ’＝（ｃφ，１ｖ，ｃφ，２ｖ）に対して、関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を満たすものがあるかを判定する（ステップＳ４１１０）。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組があった場合には、ステップＳ１１１４に進む。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφ’との組がなかった場合には、ステップＳ１１１１に進む。
【０１２９】
なお、特殊な群Ｇφ，１，Ｇφ，２や双線形写像ｅφを用いた場合、ステップＳ４１０７及びＳ４１１０の処理を仲介装置４１に実行させることができる者を制限できる。この詳細については後述する。
【０１３０】
《ｚφ，１（Ｃφ，２’）−１，ｚφ，２（Ｃφ，２”）−１がｆφ（Ｃφ，１）についてそれぞれ誤差Ｘφ，１，Ｘφ，２を持つ乱数化可能標本器の出力となる理由について》
任意の元ｈｒφ，１を固定して考えると、第二暗号文Ｃφ，２＝（μφ，ｇ１ｒ（φ），ｍφｙ（σ（φ），２）ｒ（φ））における乱数ｒ（φ）を確率空間とする確率分布について、以下の関係が成り立つ。ただし、Ｄφ，１（ｓ（φ，１），ｘφ）は、第一暗号化方式ＥＮＣφ，１に則って第一暗号文ｘφを第一復号鍵ｓ（φ，１）で復号するための関数を表す。ｒを乱数として、あるｒ２が存在して
ｆφ（ｘφａ（φ）Ｃφ，1”）（Ｃφ，２”）−１
＝（μφ，ｇ１ｒ（φ），Ｄφ，１（ｓ（φ，１），ｘφ）ａ（φ）ｈｒφ，２ｙ（σ（φ），２）ｒ（φ））
×（μφ，ｇ１ｒ２，ｈｒφ，２ｙ（σ（φ），２）ｒ２）−１
となるから、
ｆφ（ｘφａ（φ）Ｃφ，1”）（Ｃφ，２”）−１
＝（μφ，ｇ１ｒ（φ）−ｒ２，Ｄφ，１（ｓ（φ，１），ｘφ）ａ（φ）ｙ（σ（φ），２）ｒ−ｒ２）
となる。したがって、確率分布ｆφ（ｘφａ（φ）Ｃφ，1”）（Ｃφ，２”）−１は確率分布ｆ（ｘφ）ａと等しい。
【０１３１】
Ｃφ，1”を確率変数とみなして、群Ｇφに値を持つ確率変数Ｘφ，２＝ｚφ，２ｆφ（ｘφａ（φ）Ｃφ，1”）−１を考えると、
ｚφ，２（Ｃφ，２”）−１
＝ｚφ，２ｆφ（ｘφａ（φ）Ｃφ，1”）−１ｆφ（ｘφａ（φ）Ｃφ，1”）（Ｃφ，２”）−１
であるから、この確率分布はｘφ，２∈Ｘφ，２についてｘφ，２ｆφ（ｘφ）ａ（φ）の確率分布と等しい。同様に、ｚφ，１（Ｃφ，２’）−１の確率分布はｘφ，１∈Ｘφ，１についてｆφ（ｘφ）ｂ（φ）ｘφ，１の確率分布と等しい。
【０１３２】
Ｃφ，1”を確率変数とみなすとき、ｘφａ（φ）Ｃφ，1”の分布はＣφ，1”の分布と等しいから、確率変数Ｘφ，２の確率分布はa（φ）に依存しない。同様に、確率変数Ｘφ，１の確率分布はｂ（φ）に依存しない。したがって、ｚφ，１（Ｃφ，２’）−１，ｚφ，２（Ｃφ，２”）−１はｆφ（Ｃφ，１）についてそれぞれ誤差Ｘφ，１，Ｘφ，２を持つ乱数化可能標本器の出力となる。
【０１３３】
《関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を満たすかを判定することで、ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属することを判定できる理由》
ｕφ’とｖφ’とが互いに平文Ｍφ＝ｍφに対応する同一の暗号文の類ＣＬφ（Ｍφ）に属すると仮定する。この場合には第一乱数化可能標本器がｕφ＝ｆφ（Ｃφ，１）ｂ（φ）を正しく計算しており、第二乱数化可能標本器がｖφ＝ｆφ（Ｃφ，１）ａ（φ）を正しく計算している（ｘφ，１及びｘφ，２が群Ｇφの単位元ｅφ，ｇである）可能性が高い。よって、ｕφ’＝（μφ，ｇ１ｒ’’（φ），ｍφｙ（σ（φ），２）ｒ’’（φ））かつｖφ’＝（μφ，ｇ１ｒ’’’（φ），ｍφｙ（σ（φ），２）ｒ’’’（φ））である可能性が高い。ただし、ｒ’’（φ）及びｒ’’’（φ）は、ＥｌＧａｍａｌ暗号方式の乱数成分と自然数選択部１１０２で選択された自然数の組とによって定まる値である。その場合、双線形写像ｅφの性質から、ｕφ’＝（ｃφ，１ｕ，ｃφ，２ｕ）に対して
ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））
＝ｅφ（μφ，ｇ１，ｍφｙ（σ（φ），２）ｒ’’（φ））／ｅφ（μφｇ１ｒ’’ （φ），ｙ（σ（φ），２））
＝ｅφ（μφ，ｇ１，ｍφｙ（σ（φ），２））ｒ’’（φ）／ｅφ（μφ，ｇ１，ｙ（σ（φ），２））ｒ’’（φ）
＝ｅφ（μφ，ｇ１，ｍφ）ｅφ（μφ，ｇ１，ｙ（σ（φ），２））／ｅφ（μφ，ｇ１，ｙ（σ（φ），２））
＝ｅφ（μφ，ｇ１，ｍφ）
を満たす可能性が高い。また、ｖφ’＝（ｃφ，１ｖ，ｃφ，２ｖ）に対して
ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））
＝ｅφ（μφ，ｇ１，ｍφｙ（σ（φ），２）ｒ’’’（φ））／ｅφ（μφ，ｇ１ｒ’’’（φ），ｙ（σ（φ），２））
＝ｅφ（μφ，ｇ１，ｍφｙ（σ（φ），２））ｒ’’’（φ）／ｅφ（μφ，ｇ１，ｙ（σ（φ），２））ｒ’’’（φ）
＝ｅφ（μφ，ｇ１，ｍφ）ｅφ（μφ，ｇ１，ｙ（σ（φ），２））／ｅφ（μφ，ｇ１，ｙ（σ（φ），２））
＝ｅφ（μφ，ｇ１，ｍφ）
を満たす可能性が高い。よって、ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属する場合、関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を満たす可能性が高い。
【０１３４】
次に、ｕφ’とｖφ’とが互いに異なる暗号文の類に属すると仮定する。すなわち、ｕφ’が平文ｍφ，ｕに対応する暗号文の類ＣＬφ（ｍφ，ｕ）に属し、ｖφ’が平文ｍφ，ｖ（ｍφ，ｖ≠ｍφ，ｕ）に対応する暗号文の類ＣＬφ（ｍφ，ｖ）に属すると仮定する。すると、ｕφ’＝（μφ，ｇ１ｒ’’（φ），ｍφ，ｕｙ（σ（φ），２）ｒ’’（φ））ｘφ，１かつｖφ’＝（μφ，ｇ１ｒ’’’（φ），ｍφ，ｖｙ（σ（φ），２）ｒ’’’（φ））ｘφ，２となる。そのため、ｕφ’＝（ｃφ，１ｕ，ｃφ，２ｕ）に対してｅφ，（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｍφ，ｕ）ｘφ，１を満たし、ｖφ’＝（ｃφ，１ｖ，ｃφ，２ｖ）に対してｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｍφ，ｖ）ｘφ，２を満たす。よって、ｕφ’とｖφ’とが互いに異なる暗号文の類に属する場合、関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））≠ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））となる可能性が高い。
【０１３５】
《特殊な群Ｇφ，１，Ｇφ，２や双線形写像ｅφ》
群Ｇφ，１，Ｇφ，２や双線形写像ｅφの構成を以下のように限定した場合、ステップＳ４１０７及びＳ４１１０の処理を仲介装置４１に実行させることができる者を制限することができる。以下にその詳細を述べる。
【０１３６】
この特殊な例では、Ｎφが素数ωφと素数ιφの合成数、群Ｇφ，１，Ｇφ，２がそれぞれ合成数Ｎφを法とした剰余環Ｚ／ＮφＺ上で定義された第一楕円曲線Ｅφ，１上の点からなる部分群、Ｇφ，１ω，Ｇφ，２ωが素数ωφを法とした剰余体Ｚ／ωφＺ上で定義された第二楕円曲線Ｅφ，２上の点からなる部分群、Ｇφ，１ι，Ｇφ，２ιが素数ιφを法とした剰余体Ｚ／ιφＺ上で定義された第三楕円曲線Ｅφ，３上の点からなる部分群、ｅφ（α，β）が（α，β）∈Ｇφ，１×Ｇφ，２に対して巡回群などの有限可換群Ｇφ，Ｔの元を与える双線形写像、ｅφ，ω（αω，βω）が（αω，βω）∈Ｇφ，１ω×Ｇφ，２ωに対して巡回群などの有限可換群Ｇφ，Ｔωの元を与える第二双線形写像、ｅφ，ι（αι，βι）が（αι，βι）∈Ｇφ，１ι×Ｇφ，２ιに対して巡回群などの有限可換群Ｇφ，Ｔιの元を与える第三双線形写像、ＨＭφが第一楕円曲線Ｅφ，１上の点を第二楕円曲線Ｅφ，２上の点と第三楕円曲線Ｅφ，３上の点とに写す同型写像、ＨＭφ−１が同型写像ＨＭφの逆像である。
【０１３７】
この例の場合、双線形写像ｅφ（α，β）は剰余環Ｚ／ＮφＺ上で定義された第一楕円曲線Ｅφ，１上で定義される。しかしながら、剰余環上で定義された楕円曲線上で定義された双線形写像ｅφ（α，β）を多項式時間で計算する方法は知られておらず、多項式時間で計算可能な剰余環上で定義された楕円曲線上で定義された双線形写像ｅφ（α，β）の構成方法も知られていない（参考文献５：Alexander W. Dent and Steven D. Galbraith, "Hidden Pairings and Trapdoor DDH Groups," ANTS 2006, LNCS 4076, pp. 436-451, 2006.）。このような設定の場合、判定部４１１１は、双線形写像ｅφを剰余環Ｚ／ＮφＺ上で直接計算して関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を満たすか否かを判定することができない。
【０１３８】
一方、剰余体Ｚ／ωφＺ，Ｚ／ιφＺ上で定義された楕円曲線上で定義されたｅφ，ω（αω，βω）やｅφ，ι（αι，βι）としては、多項式時間で計算可能なWeilペアリングやTateペアリングなどが存在する（参考文献３，４等参照）。また、このようなｅφ，ω（αω，βω）やｅφ，ι（αι，βι）を多項式時間で行うアルゴリズムとしてMiller のアルゴリズム（参考文献６：V. S. Miller, “Short Programs for functions on Curves,”1986，インターネット＜http://crypto.stanford.edu/miller/miller.pdf＞」などがよく知られている。さらに、このようなｅφ，ω（αω，βω）やｅφ，ι（αι，βι）を効率的に行うための楕円曲線や巡回群などの有限可換群の構成方法もよく知られている（例えば、参考文献４、参考文献７：A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献８：P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」、参考文献９：R. Dupont, A. Enge, F. Morain, "Building curves with arbitrary small MOV degree over finite prime fields," http://eprint.iacr.org/2002/094/等参照）。
【０１３９】
また、中国人の剰余定理（Chinese remainder theorem）に基づき、合成数Ｎφ（Ｎφ＝ωφ・ιφ）を法とした剰余環Ｚ／ＮφＺから剰余体Ｚ／ωφＺと剰余体Ｚ／ιφＺとの直積に写す同型写像が存在すること、及び剰余体Ｚ／ωφＺと剰余体Ｚ／ιφＺとの直積から剰余環Ｚ／ＮφＺに写す同型写像が存在することがよく知られている（参考文献１０：ヨハネス ブーフマン，”暗号理論入門”，シュプリンガー・フェアラーク東京 (2001/07)， ISBN-10: 4431708669 ISBN-13，pp. 52-56）。すなわち、第一楕円曲線Ｅφ，１上の点を第二楕円曲線Ｅφ，２上の点と第三楕円曲線Ｅφ，３上の点とに写す同型写像ＨＭφ、及びその逆像ＨＭφ−１が存在する。一例を挙げると、剰余環Ｚ／ＮφＺの元κ ｍｏｄ Ｎφを剰余体Ｚ／ωφＺの元κ ｍｏｄ ωφと剰余体Ｚ／ιφＺの元κ ｍｏｄ ιφとに写す同型写像をＨＭφとし、剰余体Ｚ／ωφＺの元κω ｍｏｄ ωφと剰余体Ｚ／ιφＺの元κι ｍｏｄ ιφとを剰余環Ｚ／ＮφＺの元κωιφιφ’+κιωφωφ’ｍｏｄ Ｎφに写す写像をＨＭφ−１とすることができる。ただし、ωφ’及びιφ’はωφωφ’＋ιφιφ’＝１を満たす自然数である。このようなωφ’，ιφ’は拡張ユークリッドの互除法を用いて容易に生成できる。ωφωφ’＋ιφιφ’＝１の関係から、κωιφιφ’+κιωφωφ’ｍｏｄ ＮにＨＭφを作用させると
κωιφιφ’+κιωφωφ’ ｍｏｄ ωφ＝κωιφιφ’ｍｏｄ ωφ＝κω（１−ωφωφ’）ｍｏｄ ωφ＝κω ｍｏｄ ωφ∈Ｚ／ωφＺ
κωιφιφ’+κιωφωφ’ ｍｏｄιφ＝κιωφωφ’ ｍｏｄιφ＝κι（１−ιφιφ’） ｍｏｄιφ＝κι ｍｏｄιφ∈Ｚ／ιφＺ
となり、この一例での写像はＨＭφとＨＭφ−１との関係にあることが分かる。
【０１４０】
そのため、合成数Ｎφを素因数分解した値、すなわち素数ωφと素数ιφとの値が与えられるのであれば、判定部４１１１は、以下のステップＡ〜Ｄの処理によって、剰余環Ｚ／ＮφＺ上で定義された第一楕円曲線Ｅφ，１上の双線形写像ｅφ（α，β）を計算することができる。
【０１４１】
（ステップＡ）判定部４１１１は、同型写像ＨＭφを用い、剰余環Ｚ／ＮφＺ上で定義された第一楕円曲線Ｅφ，１上の点α∈Ｇφ，１を、剰余体Ｚ／ωφＺ上で定義された第二楕円曲線Ｅφ，２上の点θω（α）∈Ｇφ，１ωと剰余体Ｚ／ιφＺ上で定義された第三楕円曲線Ｅφ，３上の点θι（α）∈Ｇφ，１ιとに写す。
【０１４２】
（ステップＢ）判定部４１１１は、同型写像ＨＭφを用い、剰余環Ｚ／ＮφＺ上で定義された第一楕円曲線Ｅφ，１上の点β∈Ｇφ，２を、剰余体Ｚ／ωφＺ上で定義された第二楕円曲線Ｅφ，２上の点θω（β）∈Ｇφ，２ωと剰余体Ｚ／ιφＺ上で定義された第三楕円曲線Ｅφ，３上の点θι（β）∈Ｇφ，２ιとに写す。
【０１４３】
（ステップＣ）判定部４１１１は、第二楕円曲線Ｅφ，２及び第三楕円曲線Ｅφ，３でのｅφ，ω（θω（α），θω（β））及びｅφ，ι（θι（α），θι（β））を求める。
【０１４４】
（ステップＤ）判定部４１１１は、得られた演算結果ｅφ，ω（θω（α），θω（β））及びｅφ，ι（θι（α），θι（β））に逆像ＨＭφ−１を作用させた値をｅφ（α，β）とする。
【０１４５】
よって素数ωφと素数ιφとの値が与えられるのであれば、判定部４１１１は、ステップＡ〜Ｄに従ってｅφ（μφ，ｇ１，ｃφ，２ｕ），ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２）），ｅφ（μφ，ｇ１，ｃφ，２ｖ），ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を計算し、関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を満たすか否かを判定することができる。
【０１４６】
一方、大きな合成数Ｎφの素因数分解を多項式時間で行う方法は知られていない。よって、この設定の場合、素数ωφ及び素数ιφの少なくとも一方が与えられていない判定部４１１１は、関係ｅφ（μφ，ｇ１，ｃφ，２ｕ）／ｅφ（ｃφ，１ｕ，ｙ（σ（φ），２））＝ｅφ（μφ，ｇ１，ｃφ，２ｖ）／ｅφ（ｃφ，１ｖ，ｙ（σ（φ），２））を満たすか否かを判定することができない。
【０１４７】
以上のような特殊な群Ｇφ，１，Ｇφ，２や双線形写像ｅφを用いた場合、ステップＳ４１０７及びＳ４１１０の処理を仲介装置４１に実行させることができる者を素数ωφ及び素数ιφの少なくとも一方を知る者に制限することができる。
【０１４８】
［第五実施形態］
上述の各実施形態では、仲介装置の自然数記憶部１１０１に、互いに素である２つの自然数ａ（φ），ｂ（φ）の組（ａ（φ），ｂ（φ））が複数種類記憶され、これらの組（ａ（φ），ｂ（φ））を用いて各処理が実行されることとした。しかしながら、ａ（φ），ｂ（φ）の一方が定数であってもよい。例えば、ａ（φ）が１に固定されていてもよいし、ｂ（φ）が１に固定されていてもよい。言い換えると、第一乱数化可能標本器又は第二乱数化可能標本器の一方が標本器に置換されていてもよい。ａ（φ），ｂ（φ）の一方が定数である場合、定数とされたａ（φ）又はｂ（φ）を選択する処理が不要となり、各処理部は定数とされたａ（φ）又はｂ（φ）が入力されることなく、それを定数として扱って計算を行うことができる。また、定数とされたａ（φ）又はｂ（φ）が１である場合には、ａ’（φ）やｂ’（φ）を用いることなく、ｆφ（Ｃφ，１）＝ｕφｂ’（φ）ｖφａ’（φ）をｆφ（Ｃφ，１）＝ｖφ又はｆφ（Ｃφ，１）＝ｕφとして得ることができる。
【０１４９】
第五実施形態は、そのような変形の一例であり、ｂ（φ）が１に固定され、第二乱数化可能標本器が標本器に置換された形態である。以下では、第一実施形態との相違点を中心に説明する。また、第一乱数化可能標本器や標本器の具体例は、第二実施形態から第四実施形態で説明したのと同様であるため、説明を省略する。
【０１５０】
＜構成＞
図１に例示するように、第五実施形態の情報提供システム５は、第一実施形態の仲介装置１１が仲介装置５１に置換され、情報提供装置１２−φが情報提供装置５２−φに置換されたものである。
【０１５１】
図１１に例示するように、第五実施形態の仲介装置５１は、例えば、自然数記憶部５１０１と自然数選択部５１０２と入力情報提供部５１０４と第一計算部５１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部５１０８と第二リスト記憶部５１１０と判定部５１１１と処理部１１１２と最終出力部１１１３と制御部１１１４とを有する。
【０１５２】
図３に例示するように、第五実施形態の情報提供装置５２−φは、例えば、第一出力情報計算部５２０１−φと第二出力情報計算部５２０２−φと鍵記憶部１２０４−φと暗号文記憶部１２０５−φと出力部１２０６−φと復号部１２０７−φと制御部１２０８−φとを有する。
【０１５３】
＜処理の前提＞
仲介装置５１の自然数記憶部５１０１には自然数ｂ（φ）が記憶されておらず、自然数ａ（φ）のみが複数種類記憶されている。その他の前提は、上述の第一実施形態から第四実施形態の何れかと同様である。
【０１５４】
＜処理＞
図１２に例示するように、まず、仲介装置５１（図１１）の自然数選択部５１０２が、自然数記憶部５１０１に記憶された複数の自然数ａ（φ）から１つの自然数ａ（φ）をランダムに読み込む。読み込まれた自然数ａ（φ）の情報は、入力情報提供部５１０４及び第一べき乗計算部１１０６に送られる（ステップＳ５１００）。
【０１５５】
制御部１１１４は、ｔ＝１とする（ステップＳ１１０２）。
【０１５６】
入力情報提供部５１０４は、入力された第一暗号文Ｃφ，１にそれぞれ対応する第一入力情報τφ，１及び第二入力情報τφ，２を生成して出力する。好ましくは、第一入力情報τφ，１及び第二入力情報τφ，２はそれぞれ第一暗号文Ｃφ，１との関係をかく乱させた情報である。これにより、仲介装置５１は、第一暗号文Ｃφ，１を情報提供装置５２−φに対して隠蔽できる。また、好ましくは、本形態の第二入力情報τφ，２は自然数選択部５１０２で選択された自然数ａ（φ）にさらに対応する。これにより、情報提供装置５２−φから提供された再暗号化能力を仲介装置５１が高い精度で評価することが可能となる（ステップＳ５１０３）。第一入力情報τφ，１及び第二入力情報τφ，２の組みの具体例は、第二実施形態から第四実施形態の何れかのｂ（φ）＝１とした第一入力情報τφ，１及び第二入力情報τφ，２の組みである。
【０１５７】
図８に例示するように、第一入力情報τφ，１は情報提供装置５２−φ（図３）の第一出力情報計算部５２０１−φに入力され、第二入力情報τφ，２は第二出力情報計算部５２０２−φに入力される（ステップＳ５２００）。
【０１５８】
第一出力情報計算部５２０１−φは、第一入力情報τφ，１と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）とを用い、或る確率より大きな確率でｆφ（τφ，１）を正しく計算し、得られた計算結果を第一出力情報ｚφ，１とする（ステップＳ５２０１）。第二出力情報計算部５２０２−φは、第二入力情報τφ，２と鍵記憶部１２０４−φに格納された第一復号鍵ｓ（φ，１）及び第二暗号化鍵ｙ（σ（φ），２）を用い、或る確率より大きな確率でｆφ（τφ，２）を正しく計算し、得られた演算結果を第二出力情報ｚφ，２とする（ステップＳ５２０２）。すなわち、第一出力情報計算部５２０１−φや第二出力情報計算部５２０２−φは、意図的又は意図的ではない誤差を含んだ計算結果を出力し得る。言い換えると、第一出力情報計算部５２０１−φでの計算結果がｆφ（τφ，１）の場合もあればｆφ（τφ，１）でない場合もあり、第二出力情報計算部５２０２−φでの計算結果がｆφ（τφ，２）の場合もあればｆφ（τφ，２）でない場合もある。第一出力情報ｚφ，１及び第二出力情報ｚφ，２の組の具体例は、第二実施形態から第四実施形態の何れかのｂ（φ）＝１とした第一出力情報ｚφ，１及び第二出力情報ｚφ，２の組である。
【０１５９】
第一出力情報計算部５２０１−φは第一出力情報ｚφ，１を出力し、第二出力情報計算部５２０２−φは第二出力情報ｚφ，２を出力する（ステップＳ５２０３）。
【０１６０】
図１２に戻り、第一出力情報ｚφ，１は仲介装置５１（図１１）の第一計算部５１０５に入力され、第二出力情報ｚφ，２は第二計算部５１０８に入力される。これらの第一出力情報ｚφ，１及び第二出力情報ｚφ，２が、情報提供装置５２−φから仲介装置５１に与えられた再暗号化能力に相当する（ステップＳ５１０４）。
【０１６１】
第一計算部５１０５は、第一出力情報ｚφ，１から演算結果ｕφ＝ｆφ（Ｃφ，１）ｘφ，１を生成する。演算結果ｕφの具体例は、第二実施形態から第四実施形態の何れかのｂ（φ）＝１とした演算結果ｕφである。演算結果ｕφは第一べき乗計算部１１０６に送られる（ステップＳ５１０５）。
【０１６２】
第一べき乗計算部１１０６はｕφ’＝ｕφａ（φ）を計算する。計算結果ｕφとその計算結果に基づいて計算されたｕφ’との組（ｕφ，ｕφ’）は、第一リスト記憶部１１０７に記憶される（ステップＳ１１０６）。
【０１６３】
第二計算部５１０８は、第二出力情報ｚφ，２から演算結果ｖφ＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２を生成する。演算結果ｖφの具体例は、第二実施形態から第四実施形態の何れかの演算結果ｖφである。演算結果ｖφは第二リスト記憶部５１１０に記憶される（ステップＳ５１０８）。
【０１６４】
判定部５１１１は、第一実施形態から第四実施形態の何れかと同様に、第一リスト記憶部１１０７に記憶された組（ｕφ，ｕφ’）及び第二リスト記憶部５１１０に記憶されたｖφの中で、ｕφ’とｖφとが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属するものがあるかを判定する（ステップＳ５１１０）。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφとの組があった場合には、ステップＳ５１１４に進む。同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφとの組がなかった場合には、ステップＳ１１１１に進む。
【０１６５】
ステップＳ１１１１では、制御部１１１４がｔ＝Ｔであるか判定する（ステップＳ１１１１）。Ｔは予め定められた自然数である。ｔ＝Ｔであれば、処理部１１１２が、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１１３）、処理を終える。ｔ＝Ｔでない場合には、制御部１１１４は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ１１１２）、ステップＳ５１０３に戻る。
【０１６６】
ステップＳ５１１４では、処理部１１１２が、同一の暗号文の類ＣＬφ（Ｍφ）に属すると判定されたｕφ’とｖφとの組が含むｕφ’に対応するｕφを出力する（ステップＳ５１１４）。このように得られたｕφは、第一実施形態から第四実施形態でｂ（φ）＝１とした場合のｕφｂ’（φ）ｖφａ’（φ）に相当する。すなわち、このように得られたｕφは高い確率でｆφ（Ｃφ，１）となる。よって、少なくともφについての自己訂正処理を複数回繰り返し、ステップＳ５１１４で得られた値のうち最も頻度の高い値ｕφを選択すれば、選択されたｕφが第２暗号文Ｃφ，２であることの信頼度は所定値以上となる。また、後述するように、設定によっては圧倒的な確率でｕφ＝ｆφ（Ｃφ，１）となる。その場合にはステップＳ５１１４で得られた値ｕφが第２暗号文Ｃφ，２であることの信頼度は必ず所定値以上となる。
【０１６７】
≪ｆφ（Ｃφ，１）が得られる理由について≫
次に、本形態の仲介装置５１で復号結果ｆφ（Ｃφ，１）が得られる理由を説明する。まず、説明に必要な事項を定義する。
【０１６８】
ブラックボックス（ｂｌａｃｋ−ｂｏｘ）：
ｆφ（τφ）のブラックボックスＦφ（τφ）とは、τφ∈Ｈφを入力としてｚφ∈Ｇφを出力する処理部を意味する。本形態では、第一出力情報計算部５２０１−φ及び第二出力情報計算部５２０２−φが、それぞれ関数ｆφ（τφ）のブラックボックスＦφ（τφ）に相当する。群Ｈφから任意に選択された元τφ∈ＵＨφ及びｚφ＝Ｆφ（τφ）に対してｚφ＝ｆφ（τφ）を満たす確率がδ（０＜δ≦１）よりも大きい場合、すなわち、
Ｐｒ［ｚφ＝ｆφ（τφ）｜τφ∈ＵＨφ，ｚφ＝Ｆφ（τφ）］＞δ  …（１）
を満たすｆφ（τφ）のブラックボックスＦφ（τφ）のことを、信頼性δ（δ−ｒｅｌｉａｂｌｅ）のｆφ（τφ）のブラックボックスＦφ（τφ）という。なお、δは正の値であり、前述した「或る確率」に相当する。
【０１６９】
自己訂正器（ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘφ）とは、ｘφ∈Ｈφを入力とし、ｆφ（τφ）のブラックボックスＦφ（τφ）を用いて計算を行い、ｊ∈Ｇ∪⊥を出力する処理部を意味する。本形態では、仲介装置５１が自己訂正器ＣＦ（ｘφ）に相当する。
【０１７０】
オールモスト自己訂正器（ａｌｍｏｓｔ  ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘφ）が、ｘφ∈Ｈφを入力とし、δ−ｒｅｌｉａｂｌｅのｆφ（τφ）のブラックボックスＦφ（τφ）を用い、正しい値ｊ＝ｆφ（ｘφ）を出力する確率が、誤った値ｊ≠ｆφ（ｘφ）を出力する確率よりも十分大きい場合を想定する。すなわち、
Ｐｒ［ｊ＝ｆφ（ｘφ）｜ｊ＝ＣＦ（ｘφ），ｊ≠⊥］
＞Ｐｒ［ｊ≠ｆφ（ｘφ）｜ｊ＝ＣＦ（ｘφ），ｊ≠⊥］＋Δ    …（２）
を満たす場合を想定する。なお、Δは或る正の値（０＜Δ＜１）である。このような場合、自己訂正器ＣＦ（ｘφ）はオールモスト自己訂正器であるという。例えば、或る正の値Δ’（０＜Δ’＜１）に対して
Ｐｒ［ｊ＝ｆφ（ｘφ）｜ｊ＝ＣＦ（ｘφ）］＞（１／３）＋Δ’
Ｐｒ［ｊ＝⊥｜ｊ＝ＣＦ（ｘφ）］＜１／３
Ｐｒ［ｊ≠ｆφ（ｘφ）かつｊ≠⊥｜ｊ＝ＣＦ（ｘφ）］＜１／３
を満たす場合、自己訂正器ＣＦ（ｘφ）はオールモスト自己訂正器である。Δ’の例はΔ’＝１／１２や１／３である。
【０１７１】
ローバスト自己訂正器（ｒｏｂｕｓｔ  ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘφ）が、ｘφ∈Ｈを入力とし、δ−ｒｅｌｉａｂｌｅのｆφ（τφ）のブラックボックスＦφ（τφ）を用い、正しい値ｊ＝ｆφ（ｘφ）又はｊ＝⊥を出力する確率が圧倒的である場合を想定する。すなわち、無視することができる誤差ξ（０≦ξ＜１）に対して
Ｐｒ［ｊ＝ｆφ（ｘφ）またはｊ＝⊥｜ｊ＝ＣＦ（ｘφ）］＞１−ξ    …（３）
を満たす場合を想定する。このような場合、自己訂正器ＣＦ（ｘφ）はローバスト自己訂正器であるという。なお、無視することができる誤差ξの例は、セキュリティパラメータｋの関数値ξ（ｋ）である。関数値ξ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きいｋに対して｛ξ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数値ξ（ｋ）の具体例は、ξ（ｋ）＝２−ｋやξ（ｋ）＝２−√ｋなどである。
【０１７２】
また、オールモスト自己訂正器からローバスト自己訂正器を構成することができる。すなわち、同一のｘに対してオールモスト自己訂正器を複数回実行させ、⊥を除いて最も頻度が高い出力値をｊとすることで、ローバスト自己訂正器を構成できる。例えば、同一のｘに対してオールモスト自己訂正器をＯ（ｌｏｇ（１／ξ））回実行させ、最も頻度が高い出力値をｊとすることで、ローバスト自己訂正器を構成できる。なお、Ｏ（・）はオー記法を表す。
【０１７３】
擬似自由（ｐｓｅｕｄｏ−ｆｒｅｅ）な作用：
群Ｇφ、自然数の集合Ωφ＝｛０，．．．，Ｍφ｝（Ｍφは１以上の自然数）、群Ｇφに値を持つ確率変数Ｘφ，１，Ｘφ，２の各実現値αφ∈Ｘφ，１（αφ≠ｅφ，ｇ），βφ∈Ｘφ，２、及びａ（φ）∈Ωφについて、αφａ（φ）＝βφとなる確率
Ｐｒ［αφａ（φ）＝βφかつαφ≠ｅφ，ｇ｜ａ（φ）∈ＵΩ，αφ∈Ｘφ，１，βφ∈Ｘφ，２］    …（４）
について、あらゆる可能なＸφ，１，Ｘφ，２に関する上限値を、組（Ｇφ，Ωφ）の疑似自由指標とよび、これをＰ（Ｇφ，Ωφ）と表すことにする。ある無視することができる関数ζ（ｋ）が存在して、
Ｐ（Ｇφ，Ωφ）＜ζ（ｋ）      …（５）
である場合、組（Ｇφ，Ωφ）によって定義される演算は擬似自由な作用であるという。なお、「αφａ（φ）」は、群Ｇφで定義された演算をαφに対してａ（φ）回作用させることを意味する。また、無視することができる関数ζ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きいｋに対して｛ζ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数ζ（ｋ）の具体例は、ζ（ｋ）＝２−ｋやζ（ｋ）＝２−√ｋなどである。例えば、セキュリティパラメータｋとに対し、式（４）の確率がＯ（２−k）未満である場合、組（Ｇφ，Ωφ）によって定義される演算は擬似自由な作用である。また、例えば、任意のαφ∈Ｇφでαφ≠ｅφ，ｇであるものについて、集合Ωφ・αφ＝｛ａ（φ）（αφ）｜ａ（φ）∈Ωφ｝の要素数｜Ωφ・αφ｜が２ｋを超える場合、組（Ｇφ，Ωφ）によって定義される演算は擬似自由な作用といえる。なお、ａ（φ）（αφ）は、ａ（φ）とαφに所定の演算を作用させた結果を表す。このような具体例は数多く存在する。例えば、群Ｇφが素数ｐを法とする剰余群Ｚ／ｐＺであり、素数ｐが２ｋのオーダーであり、集合Ωφ＝｛０，．．．，ｐ−２｝であり、ａ（φ）（αφ）がαφａ（φ）∈Ｚ／ｐＺであり、αφ≠ｅφ，ｇである場合、Ωφ・αφ＝｛αφａ（φ）｜ａ（φ）＝０，．．．，ｐ−２｝＝｛ｅφ，ｇ，αφ１，．．．，αφｐ−２｝となり、｜Ωφ・αφ｜＝ｐ−１である。素数ｐが２ｋのオーダーであるため、ある定数Ｃが存在して、ｋが十分大きければ｜Ωφ・αφ｜＞Ｃ２ｋを満たす。ここで式（４）の確率はＣ−１２−ｋ未満であり、このような組（Ｇφ，Ωφ）によって定義される演算は擬似自由な作用である。
【０１７４】
信頼性δγ（δγ−ｒｅｌｉａｂｌｅ）の乱数化可能標本器：
自然数ａ（φ）が与えられるたびに、δ−ｒｅｌｉａｂｌｅのｆφ（τφ）のブラックボックスＦφ（τφ）を用い、ｗφ∈Ｇφについて、確率変数Ｘφに従った標本ｘφ’に対応するｗφａ（φ）ｘφ’を返す乱数化可能標本器であって、ｗφａ（φ）ｘφ’＝ｗφａ（φ）である確率がδγよりも大きい（γは正定数）、すなわち、
Ｐｒ［ｗφａ（φ）ｘφ’＝ｗφａ（φ）］＞δγ      …（６）
を満たすものを、信頼性δγの乱数化可能標本器という。本形態の入力情報提供部５１０４と第二出力情報計算部５２０２−φと第二計算部５１０８との組は、ｗφ＝ｆφ（ｘφ）について、信頼性δγの乱数化可能標本器である。
【０１７５】
次に、これらの定義を用い、本形態の仲介装置５１でｆφ（Ｃφ，１）が得られる理由を説明する。
【０１７６】
本形態のステップＳ５１１０では同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφ’とｖφとの組があるか、すなわち、同一の暗号文の類ＣＬφ（Ｍφ）に属するｕφａ（φ）とｖφとの組があるかを判定している。本形態の入力情報提供部５１０４と第二出力情報計算部５２０２−φと第二計算部５１０８との組は信頼性δγの乱数化可能標本器であるため（式（６））、Ｔをｋ、δ、γから定まる一定値よりも大きい値とすれば、漸近的に大きい確率でｕφａ（φ）とｖφとが同一の暗号文の類ＣＬφ（Ｍφ）に属することになる（ステップＳ５１１０でｙｅｓとなる）場合が生じる。たとえば、Ｔ≧４／δγとすれば、ｕφａ（φ）とｖφとが同一の暗号文の類ＣＬφ（Ｍφ）に属する（ステップＳ５１１０でｙｅｓとなる）確率は１／２よりも大きいことがＭａｒｋｏｖの不等式によってわかる。
【０１７７】
また、本形態ではｕφ＝ｆφ（Ｃφ，１）ｘφ，１及びｖφ＝ｆφ（Ｃφ，１）ａ（φ）ｘφ，２なのであるから、ｕφａ（φ）とｖφとが同一の暗号文の類ＣＬφ（Ｍφ）に属する場合にはＤφ，２（ｓ（σ（φ），２），ｆφ（Ｃφ，１）ｘφ，１）＝Ｄφ，２（ｓ（σ（φ），２），ｆφ（Ｃφ，１）ｘφ，２１／ａ（φ））が成立する。ただし、Ｄφ，２（ｓ（σ（φ），２），υ）は第二暗号化方式ＥＮＣφ，２に則ってυ∈Ｇφを第二復号鍵ｓ（σ（φ），２）で復号するための関数を表す。この場合、第２暗号化方式ＥＮＣφ，２が確定暗号方式なのであればｘφ，１ａ（φ）＝ｘφ，２が成立する。また、第２暗号化方式ＥＮＣφ，２が確率暗号方式であったとしてもｆφ（Ｃφ，１）が準同型関数なのであればｘφ，１ａ（φ）＝ｘφ，２が成立する。
【０１７８】
ｘφ，１ａ（φ）＝ｘφ，２が成立する場合には、ｘφ，１＝ｘφ，２＝ｅφ，ｇである場合とｘφ，１≠ｅφ，ｇである場合とがある。ｘφ，１＝ｘφ，２＝ｅφ，ｇである場合には、ｕφ＝ｆφ（Ｃφ，１）となるのであるから、ステップＳ５１１４で出力されるｕφは正しいｆφ（Ｃφ，１）となる。一方、ｘφ，１≠ｅφ，ｇである場合には、ｕφ≠ｆφ（Ｃφ，１）となるのであるから、ステップＳ５１１４で出力されるｕφは正しいｆφ（Ｃφ，１）ではない。
【０１７９】
群Ｇφと自然数ａ（φ）が属する集合Ωφとの組（Ｇφ，Ωφ）によって定義される演算が擬似自由な作用であるか、疑似自由指標Ｐ（Ｇφ，Ωφ）についてＴ２Ｐ（Ｇφ，Ωφ）が漸近的に小さい場合、ｘφ，１ａ（φ）＝ｘφ，２の場合にｘφ，１≠ｅφ，ｇである確率（式（４））は漸近的に小さい。したがって、ｘφ，１ａ（φ）＝ｘφ，２の場合にｘφ，１＝ｅφ，ｇである確率は漸近的に大きい。よって、組（Ｇφ，Ωφ）によって定義される演算が擬似自由な作用であるか、Ｔ２Ｐ（Ｇφ，Ωφ）が漸近的に小さい場合、ｕφａ（φ）とｖφとが同一の暗号文の類ＣＬφ（Ｍφ）に属する場合に誤ったｆφ（Ｃφ，１）が出力される確率は、ｕφａ（φ）とｖφとが同一の暗号文の類ＣＬφ（Ｍφ）に属する場合に正しいｆφ（Ｃφ，１）が出力される確率よりも十分小さい。この場合の仲介装置５１はオールモスト自己訂正器であるといえる（式（２）参照）。そのため、前述のように、仲介装置５１からローバスト自己訂正器を構成することが可能であり、圧倒的な確率で正しいｆφ（Ｃφ，１）を得ることができる。（Ｇφ，Ωφ）で定義される演算が疑似自由な作用である場合には、ｕφａ（φ）とｖφとが同一の暗号文の類ＣＬφ（Ｍφ）に属する場合に誤ったｆφ（Ｃφ，１）が出力される確率も無視できる。この場合の仲介装置５１は、圧倒的な確率で正しいｆφ（Ｃφ，１）または⊥を出力する。
【０１８０】
なお、任意の定数ρに対してｋ０が定まり、このｋ０に対してｋ０＜ｋ’を満たす任意のｋ’に対する関数値η（ｋ’）がρ未満となる場合「η（ｋ’）が漸近的に小さい」という。ｋ’の例はセキュリティパラメータｋである。また、任意の定数ρに対してｋ０が定まり、このｋ０に対してｋ０＜ｋ’を満たす任意のｋ’に対する関数値１−η（ｋ’）がρ未満となる場合「η（ｋ’）が漸近的に大きい」という。
【０１８１】
また、ａ（φ）をａ（φ）／ｂ（φ）に置換すれば分かるように、上述の証明は第一実施形態で述べた「ｕφ’とｖφ’とが互いに同一の暗号文の類ＣＬφ（Ｍφ）に属するのは、第一乱数化可能標本器がｕφ＝ｆφ（Ｃφ，１）ｂ（φ）を正しく計算しており、第二乱数化可能標本器がｖφ＝ｆφ（Ｃφ，１）ａ（φ）を正しく計算している（ｘφ，１及びｘφ，２が群Ｇφの単位元ｅφ，ｇである）可能性が高い」ことの証明ともなる。
【０１８２】
《信頼性δγの乱数化可能標本器と安全性について》
以下のような攻撃を想定する。
【０１８３】
・ブラックボックスＦφ（τφ）又はその部分が意図的に不正なｚφを出力する、又は、ブラックボックスＦφ（τφ）から出力された値が不正なｚφに改ざんされる。
【０１８４】
・不正なｚφに対応するｗφａ（φ）ｘφ’が乱数化可能標本器から出力される。
【０１８５】
・不正なｚφに対応するｗφａ（φ）ｘφ’は、自己訂正器ＣＦ（Ｃφ，１）にｕφａ（φ）とｖφとが同一の暗号文の類ＣＬφ（Ｍφ）に属すると判定させる（ステップＳ５１１０でｙｅｓなる）にもかかわらず、自己訂正器ＣＦ（Ｃφ，１）が誤った値を出力する確率を増加させる。
【０１８６】
このような攻撃は、与えられた自然数ａ（φ）に対して乱数化可能標本器から出力されたｗφａ（φ）ｘφ’の誤差の確率分布Ｄａ＝ｗφａ（φ）ｘφ’ｗφ−ａ（φ）が自然数ａ（φ）に依存する場合に可能となる。例えば、第二計算部５１０８から出力されるｖφがｆφ（Ｃφ，１）ａ（φ）ｘφ，１ａ（φ）となるような不正が行われた場合、ｘφ，１の値にかかわらず、必ずｕφａ（φ）＝ｖφが成立してｕφａ（φ）とｖφとが同一の暗号文の類ＣＬφ（Ｍφ）に属すると判定されることになる。よって、与えられた自然数ａ（φ）に対して乱数化可能標本器から出力されたｗφａ（φ）ｘφ’の誤差の確率分布Ｄａ＝ｗφａ（φ）ｘφ’ｗφ−ａ（φ）が当該自然数ａ（φ）に依存しないことが望ましい。
【０１８７】
あるいは、集合Ωφのいかなる元ａ（φ）∈∀Ωφについても、ｗφａ（φ）ｘφ’の誤差の確率分布Ｄａ＝ｗφａ（φ）ｘφ’ｗφ−ａ（φ）と区別することができない群Ｇφに値を持つ確率分布Ｄが存在する（確率分布Ｄａと確率分布Ｄとが統計的に近似する（ｓｔａｔｉｓｔｉｃａｌｌｙ−ｃｌｏｓｅ））乱数化可能標本器であることが望ましい。なお、確率分布Ｄは自然数ａ（φ）に依存しない。また、確率分布Ｄａと確率分布Ｄとを区別することができないとは、多項式時間アルゴリズムによって確率分布Ｄａと確率分布Ｄとを区別することができないことを意味し、例えば、無視することができるζ（０≦ζ＜１）に対して
Σｇ∈Ｇ｜Ｐｒ［ｇ∈Ｄ］−Ｐｒ［ｇ∈Ｄａ］｜＜ζ      …（７）
を満たすならば、多項式時間アルゴリズムによって確率分布Ｄａと確率分布Ｄとを区別することができない。無視することができるζの例は、セキュリティパラメータｋの関数値ζ（ｋ）である。関数値ζ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きなｋに対して｛ζ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数値ζ（ｋ）の具体例は、ζ（ｋ）＝２−ｋやζ（ｋ）＝２−√ｋなどである。また、これらの点は自然数ａ（φ）及びｂ（φ）を使用する第一実施形態から第四実施形態についても同様である。
【０１８８】
［変形例等］
上記の各実施形態ではΦ＝２、σ（１）＝２、σ（２）＝１の場合を例示したが、その他のΦ，σ（φ）について本発明が実施されてもよい。図１３では、Φ＝３の場合の情報提供システム６を例示している。図１３の例の場合、例えば、Φ＝３、σ（１）＝２、σ（２）＝３、σ（３）＝１として上記の各実施形態の処理を実行すればよい。その他、Φ＝４の場合には、例えば、σ（１）＝２、σ（２）＝３、σ（３）＝４、σ（４）＝１としたり、σ（１）＝２、σ（２）＝１、σ（３）＝４、σ（４）＝３としたりしてもよい。
【０１８９】
確率変数Ｘφ，１、Ｘφ，２及びＸφ，３は、同じでも異なっていてもよい。
【０１９０】
第一乱数生成部、第二乱数生成部、第三乱数生成部のそれぞれは、一様乱数を生成することにより、情報提供システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部、第二乱数生成部、第三乱数生成部の少なくとも一部が、一様乱数ではない乱数を生成してもよい。また、演算効率上からは、上述の各実施形態のように、選択される自然数の乱数は０以上Ｋφ，Ｈ未満の自然数であることが望ましいが、その代わりにＫφ，Ｈ以上の自然数の乱数が選択されてもよい。
【０１９１】
仲介装置が同一のａ（φ），ｂ（φ）に対応する第一入力情報τφ，１及び第二入力情報τφ，２を情報提供装置に提供するたびに、情報提供装置の処理が複数回実行させてもよい。これにより、仲介装置が第一入力情報τφ，１及び第二入力情報τφ，２を情報提供装置に一回提供するたびに、仲介装置は第一出力情報ｚφ，１や第二出力情報ｚφ，２や第三出力情報ｚφ，３を複数個得ることができる。これにより、仲介装置と情報提供装置との間のやり取り回数や通信量を減らすことができる。
【０１９２】
また、仲介装置が複数種類の第一入力情報τφ，１及び第二入力情報τφ，２を情報提供装置にまとめて提供し、対応する第一出力情報ｚφ，１や第二出力情報ｚφ，２や第三出力情報ｚφ，３を複数個まとめて取得してもよい。これにより、仲介装置と情報提供装置との間のやり取り回数を減らすことができる。
【０１９３】
仲介装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、情報提供装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【０１９４】
また、各実施形態の第一計算部や第二計算部において得られたｕφやｖφが群Ｇφの元であるかを確認し、群Ｇφの元であった場合には上述した処理を続行し、ｕφ又はｖφが群Ｇφの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号「⊥」が出力されてもよい。
【０１９５】
その他、本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１９６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１９７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１９８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１９９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【符号の説明】
【０２００】
１〜６  情報提供システム
１１〜５１  仲介装置
１２−φ〜５２−φ  情報提供装置
【図１】
0005596616.tif 000002
【図２】
0005596616.tif 000003
【図３】
0005596616.tif 000004
【図４】
0005596616.tif 000005
【図５】
0005596616.tif 000006
【図６】
0005596616.tif 000007
【図７】
0005596616.tif 000008
【図８】
0005596616.tif 000009
【図９】
0005596616.tif 000010
【図１０】
0005596616.tif 000011
【図１１】
0005596616.tif 000012
【図１２】
0005596616.tif 000013
【図１３】
0005596616.tif 000014