(57)【特許請求の範囲】
【請求項１】
再暗号化装置と能力提供装置とを有し、
Ｇ，Ｈが有限可換群、ｆが第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元である第一暗号文Ｃ１が与えられたとき、当該第一暗号文Ｃ１を、第二暗号化方式に則って前記平文ｍを第二暗号化鍵ｙ２で暗号化して得られる群Ｇの元である第二暗号文ｆ（Ｃ１）＝Ｃ２に変換するための関数、ａ，ｂが互いに素である自然数、第二暗号化方式に則って当該平文を前記第二暗号化鍵ｙ２で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値であり、
前記再暗号化装置が、
前記第一暗号文Ｃ１に対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を出力する入力情報提供部を含み、
前記能力提供装置が、
前記第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた演算結果を第一出力情報ｚ１とする第一出力情報生成部と、
前記第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２とする第二出力情報生成部と、を含み、
前記再暗号化装置が、さらに
前記第一出力情報ｚ１から演算結果ｕ＝ｆ（Ｃ１）ｂｘ１を生成する第一計算部と、
前記第二出力情報ｚ２から演算結果ｖ＝ｆ（Ｃ１）ａｘ２を生成する第二計算部と、
前記演算結果ｕに対する値ｕａと前記演算結果ｖに対する値ｖｂとが互いに同一の暗号文の類に属する場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についての値ｕｂ’ｖａ’を出力する最終出力部と、を含む、
再暗号化システム。
【請求項２】
請求項１の再暗号化システムであって、
前記再暗号化装置が、前記自然数ａ，ｂの少なくとも一方を選択する自然数選択部を含み、
前記第一入力情報τ１が、前記自然数ｂにさらに対応し、前記第二入力情報τ２が、前記自然数ａにさらに対応する、
再暗号化システム。
【請求項３】
請求項１又は２の再暗号化システムにおいて、
前記入力情報提供部が、前記第一暗号文Ｃ１との関係をかく乱させた情報を前記第一入力情報τ１及び前記第二入力情報τ２とする、
再暗号化システム。
【請求項４】
請求項１から３の何れかのの再暗号化システムにおいて、
前記関数ｆが準同型関数である、
再暗号化システム。
【請求項５】
請求項１から４の何れかの再暗号化システムであって、
前記関数ｆが準同型関数であり、
前記入力情報提供部が、
群Ｈの任意の元ｈｒ１を生成する第一乱数生成部と、
前記第一暗号化方式に則って前記元ｈｒ１を前記第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元Ｃ１’に対応するＣ１ｂＣ１’を前記第一入力情報τ１として得る第一入力情報計算部と、
群Ｈの任意の元ｈｒ２を生成する第二乱数生成部と、
前記第一暗号化方式に則って前記元ｈｒ２を前記第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元Ｃ１”に対応するＣ１ａＣ１”を前記第二入力情報τ２として得る第二入力情報計算部と、
前記第一出力情報計算部は、前記第一入力情報Ｃ１ｂＣ１’を用い、或る確率より大きな確率でｆ（Ｃ１ｂＣ１’）を正しく計算し、得られた計算結果を前記第一出力情報ｚ１とし、
前記第二出力情報計算部は、前記第二入力情報Ｃ１ａＣ１”を用い、或る確率より大きな確率でｆ（Ｃ１ａＣ１”）を正しく計算し、得られた計算結果を第二出力情報ｚ２とし、
前記第一計算部は、前記第二暗号化方式に則って前記元ｈｒ１を前記第二暗号化鍵ｙ２で暗号化して得られた群Ｈの元Ｃ２’に対応するｚ１（Ｃ２’）−１を前記ｕとし、
前記第二計算部は、前記第二暗号化方式に則って前記元ｈｒ２を前記第二暗号化鍵ｙ２で暗号化して得られた群Ｈの元Ｃ２”に対応するｚ２（Ｃ２”）−１を前記ｖとする、
再暗号化システム。
【請求項６】
請求項１から５の何れかの再暗号化システムにおいて、
前記関数ｆが準同型関数、群Ｇが群Ｇ１，Ｇ２の直積Ｇ１×Ｇ２、μｇ１が群Ｇ１の生成元、μｇ２が群Ｇ２の生成元、ｓ２が前記第二暗号化鍵ｙ２に対応する復号鍵、前記第二暗号化鍵ｙ２がμｇ２ｓ２、ｒが整数の乱数、前記第二暗号文Ｃ２が（μｇ１ｒ，ｍｙ２ｒ）、前記値ｕａが（ｃ１ｕ，ｃ２ｕ）∈Ｇ１×Ｇ２、前記値ｖｂが（ｃ１ｖ，ｃ２ｖ）∈Ｇ１×Ｇ２、ｅ（α，β）が（α，β）∈Ｇ１×Ｇ２に対して有限可換群ＧＴの元を与える双線形写像であり、
前記最終出力部は、関係ｅ（μｇ１，ｃ２ｕ）／ｅ（ｃ１ｕ，ｙ２）＝ｅ（μｇ１，ｃ２ｖ）／ｅ（ｃ１ｖ，ｙ２）を満たす場合に前記値ｕｂ’ｖａ’を出力する、
再暗号化システム。
【請求項７】
請求項６の再暗号化システムであって、
Ｎが素数ωと素数ιの合成数、前記群Ｇ１，Ｇ２がそれぞれ前記合成数Ｎを法とした剰余環上で定義された第一楕円曲線上の点からなる部分群、Ｇ１ω，Ｇ２ωが前記素数ωを法とした剰余体上で定義された第二楕円曲線上の点からなる部分群、Ｇ１ι，Ｇ２ιが前記素数ιを法とした剰余体上で定義された第三楕円曲線上の点からなる部分群、ｅω（αω，βω）が（αω，βω）∈Ｇ１ω×Ｇ２ωに対して有限可換群ＧＴωの元を与える第二双線形写像、ｅι（αι，βι）が（αι，βι）∈Ｇ１ι×Ｇ２ιに対して有限可換群ＧＴιの元を与える第三双線形写像、ＨＭが前記第一楕円曲線上の点を前記第二楕円曲線上の点と前記第三楕円曲線上の点とに写す同型写像、ＨＭ−１が前記同型写像ＨＭの逆像であり、
前記再暗号化装置は、
前記同型写像ＨＭを用いて前記第一楕円曲線上の点αを前記第二楕円曲線上の点θω（α）と前記第三楕円曲線上の点θι（α）とに写し、前記同型写像ＨＭを用いて前記第一楕円曲線上の点βを前記第二楕円曲線上の点θω（β）と前記第三楕円曲線上の点θι（β）とに写し、ｅω（θω（α），θω（β））及びｅι（θι（α），θι（β））を求め、ｅω（θω（α），θω（β））及びｅι（θι（α），θι（β））に対する前記逆像ＨＭ−１をｅ（α，β）として求め、前記関係を満たすか否かを判定する判定部をさらに含む、
再暗号化システム。
【請求項８】
請求項１から４の何れかの再暗号化システムにおいて、
前記関数ｆが準同型関数、μｈが群Ｈの生成元、ＫＨが群Ｈの位数、ν＝ｆ（μｈ）であり、
前記入力情報提供部は、
０以上の自然数の乱数ｒ１を生成する第一乱数生成部と、
前記第一入力情報τ１としてμｈｒ１Ｃ１ｂを計算する第一入力情報計算部と、
０以上の自然数の乱数ｒ２を生成する第二乱数生成部と、
前記第二入力情報τ２としてμｈｒ２Ｃ１ａを計算する第二入力情報計算部と、を含み、
前記第一出力情報計算部が、前記第一入力情報μｈｒ１Ｃ１ｂを用い、或る確率より大きな確率でｆ（μｈｒ１Ｃ１ｂ）を正しく計算し、得られた計算結果を前記第一出力情報ｚ１とし、
前記第二出力情報計算部は、前記第二入力情報μｈｒ２Ｃ１ａを用い、或る確率より大きな確率でｆ（μｈｒ２Ｃ１ａ）を正しく計算し、得られた計算結果を第二出力情報ｚ２とし、
前記第一計算部は、ｚ１ν−ｒ１を計算してその計算結果を前記ｕとし、
前記第二計算部は、ｚ２ν−ｒ２を計算してその計算結果を前記ｖとする、
再暗号化システム。
【請求項９】
請求項８の再暗号化システムにおいて、
前記第一乱数生成部が、ｂ≠１のときに前記乱数ｒ１を生成し、
前記第一入力情報計算部が、ｂ≠１のときに前記第一入力情報τ１として前記μｈｒ１Ｃ１ｂを計算し、
前記第一出力情報計算部が、ｂ≠１のときに前記第一入力情報μｈｒ１Ｃ１ｂを用いて得られた前記計算結果を前記第一出力情報ｚ１とし、
前記第一計算部が、ｂ≠１のときにｚ１ν−ｒ１を計算してその計算結果を前記ｕとし、
前記第二乱数生成部が、ａ≠１のときに前記乱数ｒ２を生成し、
前記第二入力情報計算部が、ａ≠１のときに前記第二入力情報τ２としてμｈｒ２Ｃ１ａを計算し、
前記第二出力情報計算部が、ａ≠１のときに前記第二入力情報μｈｒ２Ｃ１ａを用いて得られた前記計算結果を第二出力情報ｚ２とし、
前記第二計算部が、ａ≠１のときにｚ２ν−ｒ２を計算してその計算結果を前記ｖとし、
前記入力情報提供部が、
０以上の自然数の乱数ｒ３を生成する第三乱数生成部と、
ｂ＝１のときにＣ１ｒ３を前記第一入力情報τ１とし、ａ＝１のときにＣ１ｒ３を前記第二入力情報τ２とする第三入力情報計算部と、を含み、
前記能力提供装置が、
前記Ｃ１ｒ３を用い、或る確率より大きな確率でｆ（Ｃ１ｒ３）を正しく計算し、得られた計算結果を第三出力情報ｚ３とする第三出力情報計算部を含み、
前記再暗号化装置が、
ｂ＝１のときにｚ３１／ｒ３を前記ｕとし、ａ＝１のときにｚ３１／ｒ３を前記ｖとする第三計算部を含む、
再暗号化システム。
【請求項１０】
請求項１から９の何れかの再暗号化システムにおいて、
前記演算結果ｕのｆ（Ｃ１）ｂに対する誤差の確率分布が前記自然数ｂに依存しない、並びに／若しくは、前記演算結果ｖのｆ（Ｃ１）ａに対する誤差の確率分布が前記自然数ａに依存しない、又は、前記演算結果ｕのｆ（Ｃ１）ｂに対する誤差の確率分布と区別することができない前記自然数ｂに依存しない確率分布が存在する、並びに／若しくは、前記演算結果ｖのｆ（Ｃ１）ａに対する誤差の確率分布と区別することができない前記自然数ａに依存しない確率分布が存在する、
再暗号化システム。
【請求項１１】
請求項１から１０の何れかの再暗号化システムにおいて、
前記自然数ａ又は前記自然数ｂが定数である、再暗号化システム。
【請求項１２】
Ｇ，Ｈが有限可換群、ｆが第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元である第一暗号文Ｃ１が与えられたとき、当該第一暗号文Ｃ１を、第二暗号化方式に則って前記平文ｍを第二暗号化鍵ｙ２で暗号化して得られる群Ｇの元である第二暗号文ｆ（Ｃ１）＝Ｃ２に変換するための関数、前記第二暗号化方式に則って当該平文を前記第二暗号化鍵ｙ２で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素である自然数であり、
演算結果ｕ＝ｆ（Ｃ１）ｂｘ１を生成する第一計算部と、
演算結果ｖ＝ｆ（Ｃ１）ａｘ２を生成する第二計算部と、
前記演算結果ｕに対する値ｕａと前記演算結果ｖに対する値ｖｂとが互いに同一の暗号文の類に属する場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についての値ｕｂ’ｖａ’を出力する最終出力部と、
を有する再暗号化装置。
【請求項１３】
Ｇ，Ｈが有限可換群、ｆが第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元である第一暗号文Ｃ１が与えられたとき、当該第一暗号文Ｃ１を、第二暗号化方式に則って前記平文ｍを第二暗号化鍵ｙ２で暗号化して得られる群Ｇの元である第二暗号文ｆ（Ｃ１）＝Ｃ２に変換するための関数であり、
請求項１２の再暗号化装置から出力された、前記第一暗号文Ｃ１に対応する群Ｈの元である第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた演算結果を第一出力情報ｚ１とする第一出力情報生成部と、
請求項１２の再暗号化装置から出力された、前記第一暗号文Ｃ１に対応する群Ｈの元である第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２とする第二出力情報生成部と、
を有する能力提供装置。
【請求項１４】
Ｇ，Ｈが有限可換群、ｆが第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元である第一暗号文Ｃ１が与えられたとき、当該第一暗号文Ｃ１を、第二暗号化方式に則って前記平文ｍを第二暗号化鍵ｙ２で暗号化して得られる群Ｇの元である第二暗号文ｆ（Ｃ１）＝Ｃ２に変換するための関数、前記第二暗号化方式に則って当該平文を前記第二暗号化鍵ｙ２で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素である自然数であり、
再暗号化装置で、前記第一暗号文Ｃ１に対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を出力する入力情報提供ステップと、
能力提供装置で、前記第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた演算結果を第一出力情報ｚ１とする第一出力情報生成ステップと、
前記能力提供装置で、前記第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２とする第二出力情報生成ステップと、
前記再暗号化装置で、前記第一出力情報ｚ１から演算結果ｕ＝ｆ（Ｃ１）ｂｘ１を生成する第一計算ステップと、
前記再暗号化装置で、前記第二出力情報ｚ２から演算結果ｖ＝ｆ（Ｃ１）ａｘ２を生成する第二計算ステップと、
前記再暗号化装置で、前記演算結果ｕに対する値ｕａと前記演算結果ｖに対する値ｖｂとが互いに同一の暗号文の類に属する場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についての値ｕｂ’ｖａ’を出力する最終出力ステップと、
を有する再暗号化方法。
【請求項１５】
Ｇ，Ｈが有限可換群、ｆが第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元である第一暗号文Ｃ１が与えられたとき、当該第一暗号文Ｃ１を、第二暗号化方式に則って前記平文ｍを第二暗号化鍵ｙ２で暗号化して得られる群Ｇの元である第二暗号文ｆ（Ｃ１）＝Ｃ２に変換するための関数、前記第二暗号化方式に則って当該平文を前記第二暗号化鍵ｙ２で暗号化して得られる可能性がある暗号文を要素とする集合を当該暗号文が属する暗号文の類、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素である自然数であり、
第一計算部で、演算結果ｕ＝ｆ（Ｃ１）ｂｘ１を生成する第一計算ステップと、
第二計算部で、演算結果ｖ＝ｆ（Ｃ１）ａｘ２を生成する第二計算ステップと、
最終出力部で、前記演算結果ｕに対する値ｕａと前記演算結果ｖに対する値ｖｂとが互いに同一の暗号文の類に属する場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についての値ｕｂ’ｖａ’を出力する最終出力ステップと、
を有する再暗号化方法。
【請求項１６】
Ｇ，Ｈが有限可換群、ｆが第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元である第一暗号文Ｃ１が与えられたとき、当該第一暗号文Ｃ１を、第二暗号化方式に則って前記平文ｍを第二暗号化鍵ｙ２で暗号化して得られる群Ｇの元である第二暗号文ｆ（Ｃ１）＝Ｃ２に変換するための関数であり、
請求項１５の再暗号化方法を実行する再暗号化装置から出力された、前記第一暗号文Ｃ１に対応する群Ｈの元である第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた演算結果を第一出力情報ｚ１とする第一出力情報生成部と、
請求項１５の再暗号化方法を実行する再暗号化装置から出力された、前記第一暗号文Ｃ１に対応する群Ｈの元である第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２とする第二出力情報生成部と、
を有する能力提供方法。
【請求項１７】
コンピュータに請求項１５の再暗号化方法の各ステップを実行させるためのプログラム。
【請求項１８】
コンピュータに請求項１６の能力提供方法の各ステップを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号文の再暗号化技術に関し、特に、暗号文の再暗号化能力を他の装置に提供する技術に関する。
【背景技術】
【０００２】
通常、或る第一暗号化鍵で暗号化された第一暗号文を他の第二暗号化鍵で再暗号化した第二暗号文を生成するためには、第一暗号化鍵に対応する第一復号鍵を用いて第一暗号文を復号し、その復号結果を第二暗号化鍵で暗号化する必要がある（例えば、特許文献１等参照）。
【０００３】
第一復号鍵を保持していない再暗号化装置がこの再暗号化を行うための従来方法の一つは、第一復号鍵を保持している第一装置が再暗号化装置に第一復号鍵を提供し、再暗号化装置が第一復号鍵を用いて再暗号化を行う方法である。他の従来方法は、再暗号化装置が第一暗号文を第一装置に提供し、第一装置が第一復号鍵を用いて第一暗号文を再暗号化し、得られた第二暗号文を再暗号化装置に提供する方法である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３８６８２１８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、第一装置が再暗号化装置に第一復号鍵を提供する方法では、第一復号鍵を第一装置の外部に取り出さなければならず、安全上の問題がある。一方、再暗号化装置が第一暗号文を第一装置に提供し、第一装置が第一復号鍵を用いて第一暗号文を再暗号化する方法では、再暗号化装置が第一装置の再暗号化処理の正当性を検証できない。
【０００６】
本発明はこのような点に鑑みてなされたものであり、復号鍵を提供することなく暗号文を別の暗号化鍵で再暗号化する能力を提供する技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明では、Ｇ，Ｈを有限可換群として、第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化して得られた群Ｈの元である第一暗号文Ｃ１が与えられたとき、当該第一暗号文Ｃ１を、第二暗号化方式に則って前記平文ｍを第二暗号化鍵ｙ２で暗号化して得られる群Ｇの元である第二暗号文ｆ（Ｃ１）＝Ｃ２に変換するための関数をｆとする。ａ，ｂが互いに素である自然数、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値であるとする。さらに、第二暗号化方式に則って平文を第二暗号化鍵ｙ２で暗号化して得られる可能性がある暗号文を要素とする集合を、当該暗号文が属する暗号文の類と呼ぶことにする。
【０００８】
再暗号化装置は、第一暗号文Ｃ１に対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を出力する。能力提供装置は、第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた演算結果を第一出力情報ｚ１し、第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２とする。再暗号化装置は、第一出力情報ｚ１から演算結果ｕ＝ｆ（Ｃ１）ｂｘ１を生成し、第二出力情報ｚ２から演算結果ｖ＝ｆ（Ｃ１）ａｘ２を生成し、演算結果ｕに対する値ｕａと演算結果ｖに対する値ｖｂとが互いに同一の暗号文の類に属する場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についての値ｕｂ’ｖａ’を出力する。
【発明の効果】
【０００９】
本発明では、能力提供装置が復号鍵を提供することなく、第一出力情報ｚ１及び第二出力情報ｚ２を再暗号化装置に提供し、再暗号化装置がｕｂ’ｖａ’を出力する。ｕｂ’ｖａ’は高い確率で第二暗号文ｆ（Ｃ１）となる。このように本発明では、能力提供装置が復号鍵を提供することなく暗号文を別の暗号化鍵で再暗号化する能力を再暗号化装置に提供できる。
【図面の簡単な説明】
【００１０】
【図１】実施形態の再暗号化システムの構成を説明するためのブロック図。
【図２】実施形態の再暗号化装置の構成を説明するためのブロック図。
【図３】実施形態の能力提供装置の構成を説明するためのブロック図。
【図４】実施形態の再暗号文取得装置の構成を説明するためのブロック図。
【図５】実施形態の入力情報提供部の構成を説明するためのブロック図。
【図６】実施形態の入力情報提供部の構成を説明するためのブロック図。
【図７】実施形態の再暗号化装置の処理を説明するためのフローチャート。
【図８】実施形態の能力提供装置の処理を説明するためのフローチャート。
【図９】ステップＳ２１０３（Ｓ３１０３）の処理を説明するためのフローチャート。
【図１０】ステップＳ４１０３の処理を説明するためのフローチャート。
【図１１】実施形態の再暗号化装置の構成を説明するためのブロック図。
【図１２】実施形態の再暗号化装置の処理を説明するためのフローチャート。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施形態を説明する。
【００１２】
［第一実施形態］
まず、本発明の第一実施形態を説明する。
【００１３】
＜構成＞
図１に例示するように、第一実施形態の再暗号化システム１は、例えば、暗号化装置１０と再暗号化装置１１と能力提供装置１２と再暗号文取得装置１３とを有する。各装置は情報のやり取りが可能なように構成される。例えば、各装置は伝送線やネットワークや可搬型記録媒体などを経由した情報のやり取りが可能とされている。
【００１４】
本形態では、暗号化装置１０が、第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化した第一暗号文Ｃ１を出力する。第一暗号文Ｃ１を取得した再暗号化装置１１は、第一暗号文Ｃ１を第二暗号文Ｃ２に再暗号化する能力の提供を、能力提供装置１２に依頼する。本形態の能力提供装置１２はこの能力を再暗号化装置１１に提供し、再暗号化装置１１は提供された能力を用いて第一暗号文Ｃ１を第二暗号文Ｃ２に再暗号化する。再暗号化装置１１は第二暗号文Ｃ２を再暗号文取得装置１３に提供し、再暗号文取得装置１３は第二暗号文Ｃ２を復号して復号結果ｍ’を得る。また、再暗号文取得装置１３が第一暗号文Ｃ１を取得し、当該第一暗号文Ｃ１を第二暗号文Ｃ２に再暗号化する能力の提供を、再暗号化装置１１及び／又は能力提供装置１２に対して依頼してもよい。この場合、この能力が再暗号文取得装置１３に提供され、再暗号文取得装置１３は提供された能力を用いて第一暗号文Ｃ１を第二暗号文Ｃ２に再暗号化する。
【００１５】
図２に例示するように、第一実施形態の再暗号化装置１１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部１１０４と第一計算部１１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部１１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と最終出力部１１１２と制御部１１１３とを有する。再暗号化装置１１は、制御部１１１３の制御のもとで各処理を実行する。再暗号化装置１１の例は、特別なプログラムが読み込まれたＣＰＵ（ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）やＲＡＭ（ｒａｎｄｏｍ−ａｃｃｅｓｓ  ｍｅｍｏｒｙ）を備えた公知又は専用のコンピュータや、サーバ装置やゲートウェイ装置やカードリーダライタ装置や携帯電話などの計算機能と記憶機能とを備えた機器などである。
【００１６】
図３に例示するように、第一実施形態の能力提供装置１２は、例えば、第一出力情報計算部１２０１と第二出力情報計算部１２０２と鍵記憶部１２０４と制御部１２０５とを有する。能力提供装置１２は、制御部１２０５の制御のもとで各処理を実行する。能力提供装置１２の例は、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータや、携帯電話などの計算機能と記憶機能とを備えた機器や、ＩＣカードやＩＣチップなどの耐タンパ性モジュールなどである。
【００１７】
図４に例示するように、第一実施形態の再暗号文取得装置１３は、例えば、再暗号化装置１３１１と復号部１３１２と制御部１３１３と鍵記憶部１３１４とを有する。再暗号化装置１３１１の構成は図２の再暗号化装置１１と同じである。再暗号文取得装置１３は、制御部１３１３の制御のもとで各処理を実行する。再暗号文取得装置１３の例は、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータや、携帯電話などの計算機能と記憶機能とを備えた機器などである。
【００１８】
詳細構成は省略するが、第一実施形態の暗号化装置１０は、第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化する能力を持つ装置である。暗号化装置１０の例は、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータや、携帯電話などの計算機能と記憶機能とを備えた機器などである。
【００１９】
＜処理の前提＞
Ｇ，Ｈが有限可換群（例えば巡回群）であり、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数であり、ｘ１が確率変数Ｘ１の実現値であり、ｘ２が確率変数Ｘ２の実現値であり、ｆが与えられた群Ｈの元である第一暗号文Ｃ１を群Ｇの元である第二暗号文ｆ（Ｃ１）＝Ｃ２に変換するための関数であるとする。ここで第一暗号文Ｃ１は第一暗号化方式に則って平文ｍを第一暗号化鍵ｙ１で暗号化して得られた暗号文であり、第二暗号文Ｃ２は第二暗号化方式に則って平文ｍを第二暗号化鍵ｙ２で暗号化して得られる暗号文である。第一暗号化方式や第二暗号化方式は、公開鍵暗号方式であってもよいし、共通鍵暗号方式であってもよい。また、第一暗号化方式や第二暗号化方式は、確率暗号方式であってもよいし、確定暗号方式であってもよい。さらに、第一暗号化方式と第二暗号化方式とが同一の暗号化方式であってもよいし、これらが異なる暗号化方式であってもよい。第一暗号化方式や第二暗号化方式の例は、準同型関数を暗号化関数及び復号関数とする暗号化方式である。そのような例は、ＥｌＧａｍａｌ暗号方式（参考文献１：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)）などである。また、Ｇ＝Ｈであってもよいし、Ｇ≠Ｈであってもよい。また、以下では群Ｇ，Ｈ上の演算を乗法的に表現する。
【００２０】
第一暗号化鍵ｙ１には第一復号鍵s１が対応し、第二暗号化鍵ｙ２には第二復号鍵s２が対応する。第一暗号化方式が公開鍵暗号方式である場合、第一暗号化鍵ｙ１は公開鍵であり、第一復号鍵s１は秘密鍵である。一方、第一暗号化方式が共通鍵暗号方式である場合、第一暗号化鍵ｙ１及び第一復号鍵s１は共通鍵である。第二暗号化方式が公開鍵暗号方式である場合、第二暗号化鍵ｙ２は公開鍵であり、第二復号鍵s２は秘密鍵である。一方、第二暗号化方式が共通鍵暗号方式である場合、第二暗号化鍵ｙ２及び第二復号鍵s２は共通鍵である。
【００２１】
また、第二暗号化方式に則って平文を第二暗号化鍵ｙ２で暗号化して得られる暗号文Ｃ２について、Ｃ２と同一の平文と同一の暗号化鍵を用いて第二暗号化方式によって得られる可能性がある暗号文の集合を当該暗号文Ｃ２が属する「暗号文の類」と呼ぶ。例えば、第二暗号化方式がＥｌＧａｍａｌ暗号方式のような確率暗号方式である場合、同一の平文と暗号化鍵との組に対して複数の暗号文が対応するため、任意の暗号文Ｃについて、Ｃが属する暗号文の類には複数の要素が属する。一方、例えば、第二暗号化方式がＲＳＡ暗号方式のような確定暗号方式である場合、同一の平文と暗号化鍵との組に対して暗号文が一義的に定まるため、同一の暗号文の類には一つの要素のみが属する。同一の暗号文の類に一つの要素のみが属する場合、二つの値が同一の暗号文の類に属することと当該二つの値が等しいこととが等価となる。すなわち、第二暗号化方式が確定暗号方式である場合、二つの値が同一の暗号文の類に属するかの判定は当該二つの値が等しいかを判定することで行うことができる。
【００２２】
また、再暗号化装置１１（図２）の自然数記憶部１１０１に、互いに素である２つの自然数ａ，ｂの組（ａ，ｂ）が複数種類記憶されているものとする。Ｉを群Ｇの位数未満の２つの自然数の組で互いに素なものの集合とすると、自然数記憶部１１０１にはＩの部分集合Ｓに対応する自然数ａ，ｂの組（ａ，ｂ）が記憶されていると考えることができる。ａ，ｂは互いに素な自然数であり、「自然数」とは０以上の整数を表す。また、第一暗号化鍵ｙ１が暗号化装置１０の鍵記憶部（図示せず）に格納され、第一復号鍵ｓ１及び第二暗号化鍵ｙ２が能力提供装置１２（図３）の鍵記憶部１２０４に格納され、第二復号鍵ｓ２が再暗号文取得装置１３（図４）の鍵記憶部１３１４に格納されているものとする。
【００２３】
＜処理＞
まず、暗号化装置１０が、鍵記憶部（図示せず）から読み出した第一暗号化鍵ｙ１を用い、入力された平文ｍを第一暗号化方式に則って暗号化して第一暗号文Ｃ１∈Ｈを生成し、当該第一暗号文Ｃ１を出力する。
【００２４】
第一暗号文Ｃ１は再暗号化装置１１（図２）の入力情報提供部１１０４に入力される。第一暗号文Ｃ１が入力された再暗号化装置１１の自然数選択部１１０２は、図７に例示するように、自然数記憶部１１０１に記憶された複数の自然数の組（ａ，ｂ）から１つの自然数の組（ａ，ｂ）をランダムに読み込む。読み込まれた自然数の組（ａ，ｂ）少なくとも一部の情報は、整数計算部１１０３、入力情報提供部１１０４、第一べき乗計算部１１０６及び第二べき乗計算部１１０９に送られる（ステップＳ１１００）。
【００２５】
整数計算部１１０３は、送られた自然数の組（ａ，ｂ）を用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する。自然数ａ，ｂは互いに素であるため、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’は必ず存在して、その計算方法もよく知られている。たとえば拡張互除法などのよく知られたアルゴリズムによって整数ａ’，ｂ’が計算され、自然数の組（ａ’，ｂ’）の情報は、最終出力部１１１２に送られる（ステップＳ１１０１）。
【００２６】
制御部１１１３は、ｔ＝１とする（ステップＳ１１０２）。
【００２７】
入力情報提供部１１０４は、入力された第一暗号文Ｃ１にそれぞれ対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を生成して出力する。好ましくは、第一入力情報τ１及び第二入力情報τ２はそれぞれ第一暗号文Ｃ１との関係をかく乱させた情報である。これにより、再暗号化装置１１は、第一暗号文Ｃ１を能力提供装置１２に対して隠蔽できる。また、好ましくは、本形態の第一入力情報τ１は自然数選択部１１０２で選択された自然数ｂにさらに対応し、第二入力情報τ２は自然数選択部１１０２で選択された自然数ａにさらに対応する。これにより、能力提供装置１２から提供された再暗号化能力を再暗号化装置１１が高い精度で評価することができる（ステップＳ１１０３）。
【００２８】
図８に例示するように、第一入力情報τ１は能力提供装置１２（図３）の第一出力情報計算部１２０１に入力され、第二入力情報τ２は第二出力情報計算部１２０２に入力される（ステップＳ１２００）。
【００２９】
第一出力情報計算部１２０１は、第一入力情報τ１と鍵記憶部１２０４に格納された第一復号鍵ｓ１及び第二暗号化鍵ｙ２とを用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする（ステップＳ１２０１）。第二出力情報計算部１２０２は、第二入力情報τ２と鍵記憶部１２０４に格納された第一復号鍵ｓ１及び第二暗号化鍵ｙ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２とする（ステップＳ１２０２）。なお、関数ｆの例は、第一暗号化方式に則って第一復号鍵ｓ１で暗号文を復号して得られる値を、第二暗号化方式に則って第二暗号化鍵ｙ２で暗号化するための準同型関数である。また、「或る確率」は１００％未満の確率である。「或る確率」の例は無視することができない確率であり、「無視することができない確率」の例は、セキュリティパラメータｋについての広義単調増加関数である多項式を多項式ψ（ｋ）とした場合の１／ψ（ｋ）以上の確率である。すなわち、第一出力情報計算部１２０１や第二出力情報計算部１２０２は、意図的又は意図的ではない誤差を含んだ計算結果を出力し得る。言い換えると、第一出力情報計算部１２０１での計算結果がｆ（τ１）の場合もあればｆ（τ１）でない場合もあり、第二出力情報計算部１２０２での計算結果がｆ（τ２）の場合もあればｆ（τ２）でない場合もある。第一出力情報計算部１２０１は第一出力情報ｚ１を出力し、第二出力情報計算部１２０２は第二出力情報ｚ２を出力する（ステップＳ１２０３）。
【００３０】
図７に戻り、第一出力情報ｚ１は再暗号化装置１１（図２）の第一計算部１１０５に入力され、第二出力情報ｚ２は第二計算部１１０８に入力される。これらの第一出力情報ｚ１及び第二出力情報ｚ２が、能力提供装置１２から再暗号化装置１１に与えられた再暗号化能力に相当する（ステップＳ１１０４）。
【００３１】
第一計算部１１０５は、第一出力情報ｚ１から演算結果ｕ＝ｆ（Ｃ１）ｂｘ１を生成する。ここで、ｆ（Ｃ１）ｂｘ１を生成（計算）するとは、ｆ（Ｃ１）ｂｘ１と定義される式の値を計算することである。式ｆ（Ｃ１）ｂｘ１の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。演算結果ｕは第一べき乗計算部１１０６に送られる（ステップＳ１１０５）。
【００３２】
第一べき乗計算部１１０６はｕ’＝ｕａを計算する。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部１１０７に記憶される（ステップＳ１１０６）。
【００３３】
判定部１１１１は、第一リスト記憶部１１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１１１０に記憶された組（ｖ，ｖ’）の中で、ｕ’とｖ’とが互いに同一の暗号文の類に属するものがあるかを判定する。言い換えると、判定部１１１１は、同一の平文に対する暗号文の類に属するｕ’とｖ’との組があるか判定する。例えば、第二暗号化方式が確定暗号方式の場合、判定部１１１１は、ｕ’＝ｖ’であるかを判定する（ステップＳ１１０７）。もし、第二リスト記憶部１１１０に組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ１１０７の処理を行わずに、次のステップＳ１１０８の処理を行う。同一の平文に対する暗号文の類に属するｕ’とｖ’との組があった場合には、ステップＳ１１１４に進む。同一の平文に対する暗号文の類に属するｕ’とｖ’との組がなかった場合には、ステップＳ１１０８に進む。
【００３４】
ステップＳ１１０８では、第二計算部１１０８が、第二出力情報ｚ２から演算結果ｖ＝ｆ（Ｃ１）ａｘ２を生成する。演算結果ｖは第二べき乗計算部１１０９に送られる（ステップＳ１１０８）。
【００３５】
第二べき乗計算部１１０９はｖ’＝ｖｂを計算する。計算結果ｖとその計算結果に基づいて計算されたｖ’との組（ｖ，ｖ’）は、第二リスト記憶部１１１０に記憶される（ステップＳ１１０９）。
【００３６】
判定部１１１１は、第一リスト記憶部１１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１１１０に記憶された組（ｖ，ｖ’）の中で、ｕ’とｖ’とが互いに同一の平文に対する暗号文の類に属するものがあるかを判定する。例えば、第二暗号化方式が確定暗号方式の場合、判定部１１１１は、ｕ’＝ｖ’であるかを判定する（ステップＳ１１１０）。同一の平文に対する暗号文の類に属するｕ’とｖ’との組があった場合には、ステップＳ１１１４に進む。同一の平文に対する暗号文の類に属するｕ’とｖ’との組がなかった場合には、ステップＳ１１１１に進む。
【００３７】
ステップＳ１１１１では、制御部１１１３がｔ＝Ｔであるか判定する（ステップＳ１１１１）。Ｔは予め定められた自然数である。ｔ＝Ｔであれば、最終出力部１１１２が、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１１３）、処理を終える。ｔ＝Ｔでない場合には、制御部１１１３は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１（ｔ＋１を新たなｔ）として（ステップＳ１１１２）、ステップＳ１１０３に戻る。
【００３８】
計算をすることができなかった旨の情報（この例では記号「⊥」）は、能力提供装置１２が正しく計算を行う信頼性がＴで定められる基準を下回るということを意味する。言い換えれば、Ｔ回の繰り返しで正しい演算を行うことができなかったということを意味する。
【００３９】
ステップＳ１１１４では、最終出力部１１１２が、同一の平文に対する暗号文の類に属すると判定されたｕ’とｖ’との組に対応するｕ及びｖを用いてｕｂ’ｖａ’を計算して、出力する（ステップＳ１１１４）。このように計算されたｕｂ’ｖａ’は、高い確率で第二暗号文ｆ（Ｃ１）＝Ｃ２∈Ｇとなる（高い確率でｕｂ’ｖａ’＝ｆ（Ｃ１）となる理由については後述する）。よって、上述した処理を複数回繰り返し、ステップＳ１１１４で得られた値のうち最も頻度の高い値を第２暗号文Ｃ２とすればよい。また、後述するように、設定によっては圧倒的な確率でｕｂ’ｖａ’＝ｆ（Ｃ１）となる。その場合にはステップＳ１１１４で得られた値をそのまま第２暗号文Ｃ２としてよい。
【００４０】
第二暗号文Ｃ（ｙ２，ｍ）は、再暗号文取得装置１３（図４）の復号部１３１２に入力される。復号部１３１２は、鍵記憶部１３１４から読み出した第二復号鍵s２を用いて第二暗号文Ｃ２を復号し、それによって得られる復号結果ｍ’を出力する。
【００４１】
また、再暗号文取得装置１３が再暗号化装置１１から与えられた第二暗号文を信頼できない場合も想定し得る。例えば、再暗号化装置１１の処理自体が不正であった場合や、再暗号化装置１１から出力された第二暗号文が改ざんされる可能性がある場合などである。このような場合には、再暗号文取得装置１３がローカルに含む再暗号化装置１３１１に第一暗号文Ｃ１が入力され、再暗号化装置１３１１と能力提供装置１２との間で、前述の図７及び図８に記載された処理が実行されてもよい。この処理は例えば再暗号化装置１１が再暗号化装置１３１１に置換された処理となる。或いは、この処理の際、上述した能力提供装置１２の処理の少なくとも一部が再暗号化装置１１によって実行されてもよい。また再暗号化装置１３１１は、再暗号化装置１１及び能力提供装置１２がそれぞれどのような処理を行っているかを知る必要はない。少なくとも、再暗号化装置１１及び能力提供装置１２からなるシステムとして図８に記載された処理が実行されればよい。
【００４２】
このようにして得られた第二暗号文Ｃ２は復号部１３１２に入力され、同様に第二復号鍵s２を用いて復号される。これにより、たとえ第一暗号文Ｃ１が確率暗号であったとしても、第一暗号文Ｃ１と第二暗号文Ｃ２とが同一の平文ｍに対応することを確認できる。同様に、第一暗号文Ｃ１が確定暗号である場合にも、第一暗号文Ｃ１と第二暗号文Ｃ２とが同一の平文ｍに対応することを確認できる。
【００４３】
≪高い確率でｕｂ’ｖａ’＝ｆ（Ｃ１）となる理由について≫
Ｘを群Ｇに値を持つ確率変数とする。ｗ∈Ｇについて、要求を受けるたびに確率変数Ｘに従った標本ｘ’に対応するｗｘ’を返すものを、ｗについて誤差Ｘを持つ標本器（ｓａｍｐｌｅｒ）と呼ぶ。
【００４４】
ｗ∈Ｇについて、自然数ａが与えられるたびに確率変数Ｘに従った標本ｘ’に対応するｗａｘ’を返すものを、ｗについて誤差Ｘを持つ乱数化可能標本器（ｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒ）と呼ぶ。乱数化可能標本器はａ＝１として用いられれば標本器として機能する。
【００４５】
本実施形態の入力情報提供部１１０４と第一出力情報計算部１２０１と第一計算部１１０５との組み合わせが、ｆ（Ｃ１）について誤差Ｘ１を持つ乱数化可能標本器（「第一乱数化可能標本器」と呼ぶ）であり、入力情報提供部１１０４と第二出力情報計算部１２０２と第二計算部１１０８との組み合わせが、ｆ（Ｃ１）について誤差Ｘ２を持つ乱数化可能標本器（「第二乱数化可能標本器」と呼ぶ）である。
【００４６】
ｕ’とｖ’とが互いに同一の平文に対する暗号文の類に属するのは、第一乱数化可能標本器がｕ＝ｆ（Ｃ１）ｂを正しく計算しており、第二乱数化可能標本器がｖ＝ｆ（Ｃ１）ａを正しく計算している（ｘ１及びｘ２が群Ｇの単位元ｅｇである）可能性が高いことを発明者は見出した。説明の簡略化の観点から、この証明は第五実施形態で行う。
【００４７】
第一乱数化可能標本器がｕ＝ｆ（Ｃ１）ｂを正しく計算しており、第二乱数化可能標本器がｖ＝ｆ（Ｃ１）ａを正しく計算しているとき（ｘ１及びｘ２が群Ｇの単位元ｅｇであるとき）、ｕｂ’＝（ｆ（Ｃ１）ｂｘ１）ｂ’＝（ｆ（Ｃ１）ｂｅｇ）ｂ’＝ｆ（Ｃ１）ｂｂ’となり、ｖａ’＝（ｆ（Ｃ１）ａｘ２）ａ’＝（ｆ（Ｃ１）ａｅｇ）ａ’＝ｆ（Ｃ１）ａａ’となる。そのため、第二暗号化方式が確定暗号方式なのであればｕｂ’ｖａ’＝ｆ（Ｃ１）（ｂｂ’＋ａａ’）＝ｆ（Ｃ１）となる。一方、第二暗号化方式が確率暗号方式であったとしてもｆ（Ｃ１）が準同型関数なのであれば、ｕｂ’ｖａ’＝ｆ（Ｃ１（ｂｂ’＋ａａ’））＝ｆ（Ｃ１）となる。
【００４８】
また、（ｑ１，ｑ２）∈Ｉについて、ｉ＝１，２の各々について関数πｉをπｉ（ｑ１，ｑ２）＝ｑｉで定義する。さらに、Ｌ＝ｍｉｎ（♯π１（Ｓ），♯π２（Ｓ））とする。♯・は、集合・の位数である。群Ｇが巡回群や位数の計算が困難な群であるときには、再暗号化装置１１が「⊥」以外を出力するときの出力がｆ（Ｃ１）ではない確率は、無視できる程度の誤差の範囲で高々Ｔ２Ｌ／♯Ｓ程度と期待することができる。もしＬ／♯Ｓが無視できる量でＴが多項式オーダー程度の量であれば、再暗号化装置１１は圧倒的な確率で正しいｆ（Ｃ１）を出力する。Ｌ／♯Ｓが無視できる量になるようなＳの例には、例えばＳ＝｛（１，ｄ）｜ｄ∈［２，｜Ｇ｜−１］｝がある。
【００４９】
［第二実施形態］
第二実施形態の再暗号化システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した例である。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。以下の説明において、同一の参照番号が付された部分は同一の機能を持つものとし、同一の参照番号が付されたステップは同一の処理を表すものとする。
【００５０】
＜構成＞
図１に例示するように、第二実施形態の再暗号化システム２は、再暗号化装置１１が再暗号化装置２１に置換され、能力提供装置１２が能力提供装置２２に置換され、再暗号文取得装置１３が再暗号文取得装置２３に置換されたものである。
【００５１】
図２に例示するように、第二実施形態の再暗号化装置２１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部２１０４と第一計算部２１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部２１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と最終出力部１１１２と制御部１１１３とを有する。図５に例示するように、本形態の入力情報提供部２１０４は、例えば、第一乱数生成部２１０４ａと第一入力情報計算部２１０４ｂと第二乱数生成部２１０４ｃと第二入力情報計算部２１０４ｄとを有する。
【００５２】
図３に例示するように、第二実施形態の能力提供装置２２は、例えば、第一出力情報計算部２２０１と第二出力情報計算部２２０２と鍵記憶部１２０４と制御部１２０５とを有する。
【００５３】
図４に例示するように、第二実施形態の再暗号文取得装置２３は、例えば、再暗号化装置２３２１と復号部１３１２と制御部１３１３と鍵記憶部１３１４とを有する。再暗号化装置２３２１の構成及び処理は図２の再暗号化装置２１と同じである。
【００５４】
＜処理の前提＞
第二実施形態では、関数ｆを準同型関数とし、群Ｈの生成元をμｈ、群Ｈの位数をＫＨ、ν＝ｆ（μｈ）とする。その他の前提は、再暗号化装置１１が再暗号化装置２１に置換され、能力提供装置１２が能力提供装置２２に置換され、再暗号文取得装置１３が再暗号文取得装置２３に置換されている以外、第一実施形態と同一である。
【００５５】
＜処理＞
図７及び図８に例示するように、第二実施形態の処理は第一実施形態のステップＳ１１０３〜Ｓ１１０５，Ｓ１１０８，Ｓ１２００〜Ｓ１２０３が、それぞれ、ステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３に置換されたものである。以下ではステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３の処理のみを説明する。
【００５６】
《ステップＳ２１０３の処理》
再暗号化装置２１（図２）の入力情報提供部２１０４は、入力された第一暗号文Ｃ１にそれぞれ対応する第一入力情報τ１及び第二入力情報τ２を生成して出力する（図７／ステップＳ２１０３）。以下、図９を用いて本形態のステップＳ２１０３の処理を説明する。
【００５７】
第一乱数生成部２１０４ａ（図５）は、０以上ＫＨ未満の自然数の一様乱数ｒ１を生成する。生成された乱数ｒ１は、第一入力情報計算部２１０４ｂ及び第一計算部２１０５に送られる（ステップＳ２１０３ａ）。第一入力情報計算部２１０４ｂは、入力された乱数ｒ１と第一暗号文Ｃ１と自然数ｂとを用いて第一入力情報τ１＝μｈｒ１Ｃ１ｂを計算する（ステップＳ２１０３ｂ）。ここで、μｈの右肩のｒ１は、ｒ１のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。
【００５８】
第二乱数生成部２１０４ｃは、０以上ＫＨ未満の自然数の一様乱数ｒ２を生成する。生成された乱数ｒ２は、第二入力情報計算部２１０４ｄ及び第二計算部２１０８に送られる（ステップＳ２１０３ｃ）。第二入力情報計算部２１０４ｄは、入力された乱数ｒ２と第一暗号文Ｃ１と自然数ａとを用いて第二入力情報τ２＝μｈｒ２Ｃ１ａを計算する（ステップＳ２１０３ｄ）。
【００５９】
第一入力情報計算部２１０４ｂ及び第二入力情報計算部２１０４ｄは、以上のように生成した第一入力情報τ１及び第二入力情報τ２を出力する（ステップＳ２１０３ｅ）。なお、本形態の第一入力情報τ１及び第二入力情報τ２は、それぞれ、乱数ｒ１，ｒ２によって第一暗号文Ｃ１との関係をかく乱させた情報である。これにより、再暗号化装置２２は、第一暗号文Ｃ１を能力提供装置２２に対して隠蔽できる。また、本形態の第一入力情報τ１は自然数選択部１１０２で選択された自然数ｂにさらに対応し、第二入力情報τ２は自然数選択部１１０２で選択された自然数ａにさらに対応する。これにより、能力提供装置２２から提供された再暗号化能力を再暗号化装置２１が高い精度で評価することができる。
【００６０】
《ステップＳ２２００〜Ｓ２２０３の処理》
図８に例示するように、まず、第一入力情報τ１＝μｈｒ１Ｃ１ｂが能力提供装置２２（図３）の第一出力情報計算部２２０１に入力され、第二入力情報τ２＝μｈｒ２Ｃ１ａが第二出力情報計算部２２０２に入力される（ステップＳ２２００）。
【００６１】
第一出力情報計算部２２０１は、第一入力情報τ１＝μｈｒ１Ｃ１ｂと鍵記憶部１２０４に格納された第一復号鍵ｓ１及び第二暗号化鍵ｙ２とを用い、或る確率より大きな確率でｆ（μｈｒ１Ｃ１ｂ）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部２２０１での計算結果がｆ（μｈｒ１Ｃ１ｂ）となる場合もあれば、ｆ（μｈｒ１Ｃ１ｂ）とならない場合もある。なお、関数ｆの例は、第一暗号化方式に則って第一復号鍵ｓ１で暗号文を復号して得られる値を、第二暗号化方式に則って第二暗号化鍵ｙ２で暗号化するための準同型関数である。このような関数ｆに対応する第一暗号化方式や第二暗号化方式の例はＲＳＡ暗号方式である（ステップＳ２２０１）。
【００６２】
第二出力情報計算部２２０２は、第二入力情報τ２＝μｈｒ２Ｃ１ａと鍵記憶部１２０４に格納された第一復号鍵ｓ１及び第二暗号化鍵ｙ２とを用い、或る確率より大きな確率でｆ（μｈｒ２Ｃ１ａ）を正しく計算し、得られた計算結果を第二出力情報ｚ２とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部２２０２での計算結果がｆ（μｈｒ２Ｃ１ａ）となる場合もあれば、ｆ（μｈｒ２Ｃ１ａ）とならない場合もある（ステップＳ２２０２）。
【００６３】
第一出力情報計算部２２０１は第一出力情報ｚ１を出力し、第二出力情報計算部２２０２は第二出力情報ｚ２を出力する（ステップＳ２２０３）。
【００６４】
《ステップＳ２１０４及びＳ２１０５の処理》
図７に戻り、第一出力情報ｚ１は再暗号化装置２１（図２）の第一計算部２１０５に入力され、第二出力情報ｚ２は第二計算部２１０８に入力される。これらの第一出力情報ｚ１及び第二出力情報ｚ２が、能力提供装置２２から再暗号化装置２１に与えられた再暗号化能力に相当する（ステップＳ２１０４）。
【００６５】
第一計算部２１０５は、入力された乱数ｒ１及び第一出力情報ｚ１を用いてｚ１ν−ｒ１を計算してその計算結果をｕとする。計算結果ｕは、第一べき乗計算部１１０６に送られる。ここで、ｕ＝ｚ１ν−ｒ１＝ｆ（Ｃ１）ｂｘ１となる。すなわち、ｚ１ν−ｒ１は、ｆ（Ｃ１）について誤差Ｘ１を持つ乱数化可能標本器の出力となる。その理由については後述する（ステップＳ２１０５）。
【００６６】
《ステップＳ２１０８の処理》
第二計算部２１０８は、入力された乱数ｒ２及び第二出力情報ｚ２を用いてｚ２ν−ｒ２を計算してその計算結果をｖとする。計算結果ｖは、第二べき乗計算部１１０９に送られる。ここで、ｖ＝ｚ２ν−ｒ２＝ｆ（Ｃ１）ａｘ２となる。すなわち、ｚ２ν−ｒ２は、ｆ（Ｃ１）について誤差Ｘ２を持つ乱数化可能標本器の出力となる。その理由については後述する（ステップＳ２１０８）。
【００６７】
≪ｚ１ν−ｒ１，ｚ２ν−ｒ２がｆ（Ｃ１）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器の出力となる理由について≫
ｃを自然数、Ｒ及びＲ’を乱数として、能力提供装置２２がμｈＲＣ１ｃを用いて行う計算の計算結果をＢ（μｈＲＣ１ｃ）とする。すなわち、第一出力情報計算部２２０１や第二出力情報計算部２２０２が再暗号化装置２１に返す計算結果をｚ＝Ｂ（μｈＲＣ１ｃ）とする。さらに、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（μｈＲ’）ｆ（μｈＲ’）−１と定義する。
【００６８】
このとき、ｚν−Ｒ＝Ｂ（μｈＲＣ１ｃ）ｆ（μｈ）−Ｒ＝Ｘｆ（μｈＲＣ１ｃ）ｆ（μｈ）−Ｒ＝Ｘｆ（μｈ）Ｒｆ（Ｃ１）ｃｆ（μｈ）−Ｒ＝ｆ（Ｃ１）ｃＸとなる。すなわち、ｚν−Ｒは、ｆ（Ｃ１）について誤差Ｘを持つ乱数化可能標本器の出力となる。
【００６９】
上記式展開において、Ｘ＝Ｂ（μｈＲ’）ｆ（μｈＲ’）−１＝Ｂ（μｈＲＣ１ｃ）ｆ（μｈＲＣ１ｃ）−１であり、Ｂ（μｈＲＣ１ｃ）＝Ｘｆ（μｈＲＣ１ｃ）であるという性質を用いている。この性質は、関数ｆが準同型関数であり、Ｒ及びＲ’が乱数であることに基づく。
【００７０】
したがって、ａ，ｂが自然数、ｒ１，ｒ２が乱数であることを考慮すると、同様に、ｚ１ν−ｒ１，ｚ２ν−ｒ２がｆ（Ｃ１）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器の出力となるのである。
【００７１】
《その他》
第一実施形態と同様、再暗号文取得装置２３がローカルに含む再暗号化装置２３２１に第一暗号文Ｃ１が入力され、再暗号化装置２３２１と能力提供装置２２との間で、前述の図７及び図８に記載された処理が実行されてもよい。この処理は例えば再暗号化装置２１が再暗号化装置２３２１に置換された処理となる。或いは、この処理の際、上述した能力提供装置２２の処理の少なくとも一部が再暗号化装置２１によって実行されてもよい。また再暗号化装置２３２１は、再暗号化装置２１及び能力提供装置２２がそれぞれどのような処理を行っているかを知る必要はない。少なくとも、再暗号化装置２１及び能力提供装置２２からなるシステムとして図８に記載された処理が実行されればよい。
【００７２】
［第三実施形態］
第三実施形態は第二実施形態の変形例であり、ａ＝１やｂ＝１のときに前述した標本器によってｕ又はｖの値を計算する。一般に乱数化可能標本器よりも標本器の計算量は小さい。ａ＝１やｂ＝１のときに乱数化可能標本器に代わり、標本器が計算を行うことで、再暗号化システムの計算量を小さくすることができる。以下、第一実施形態及び第二実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。
【００７３】
＜構成＞
図１に例示するように、第三実施形態の再暗号化システム３は、再暗号化装置２１が再暗号化装置３１に置換され、能力提供装置２２が能力提供装置３２に置換され、再暗号文取得装置２３が再暗号文取得装置３３に置換されたものである。
【００７４】
図２に例示するように、第三実施形態の再暗号化装置３１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部２１０４と第一計算部２１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部２１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と最終出力部１１１２と制御部１１１３と第三計算部３１０９とを有する。
【００７５】
図３に例示するように、第三実施形態の能力提供装置３２は、例えば、第一出力情報計算部２２０１と第二出力情報計算部２２０２と鍵記憶部１２０４と制御部１２０５と第三出力情報計算部３２０３とを有する。
【００７６】
図４に例示するように、第三実施形態の再暗号文取得装置３３は、例えば、再暗号化装置３３３１と復号部１３１２と制御部１３１３と鍵記憶部１３１４とを有する。再暗号化装置３３３１の構成及び処理は図２の再暗号化装置３１と同じである。
【００７７】
＜処理＞
次に本形態の処理を説明する。第二実施形態との相違点を説明する。
【００７８】
図７及び図８に例示するように、第三実施形態の処理は第二実施形態のステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３が、それぞれ、ステップＳ３１０３〜Ｓ３１０５，Ｓ３１０８，Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９に置換されたものである。以下ではステップＳ３１０３〜Ｓ３１０５，Ｓ３１０８，Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理を中心に説明する。
【００７９】
《ステップＳ３１０３の処理》
再暗号化装置３１（図２）の入力情報提供部３１０４は、入力された第一暗号文Ｃ１にそれぞれ対応する第一入力情報τ１及び第二入力情報τ２を生成して出力する（図７／ステップＳ３１０３）。
【００８０】
以下、図９を用いて本形態のステップＳ３１０３の処理を説明する。
【００８１】
制御部１１１３（図２）は、自然数選択部１１０２で選択された自然数（ａ，ｂ）に応じて入力情報提供部３１０４を制御する。
【００８２】
制御部１１１３でｂが１であるかが判定され（ステップＳ３１０３ａ）、ｂ≠１であると判定された場合、前述のステップＳ２１０３ａ及びＳ２１０３ｂの処理が実行され、ステップＳ３１０３ｇに進む。
【００８３】
一方、ステップＳ３１０３ａでｂ＝１であると判定された場合、第三乱数生成部３１０４ｅが、０以上ＫＨ未満の自然数の乱数ｒ３を生成する。生成された乱数ｒ３は第三入力情報計算部３１０４ｆ及び第三計算部３１０９に送られる（ステップＳ３１０３ｂ）。第三入力情報計算部３１０４ｆは、入力された乱数ｒ３と第一暗号文Ｃ１とを用いてＣ１ｒ３を計算し、これを第一入力情報τ１とする（ステップＳ３１０３ｃ）。その後、ステップＳ３１０３ｇに進む。
【００８４】
ステップＳ３１０３ｇでは、制御部１１１３でａが１であるかが判定され（ステップＳ３１０３ｇ）、ａ≠１であると判定された場合、前述のステップＳ２１０３ｃ及びステップＳ２１０３ｄの処理が実行される。
【００８５】
一方、ステップＳ３１０３ｇでａ＝１であると判定された場合、第三乱数生成部３１０４ｅが、０以上ＫＨ未満の自然数の乱数ｒ３を生成する。生成された乱数ｒ３は第三入力情報計算部３１０４ｆに送られる（ステップＳ３１０３ｈ）。第三入力情報計算部３１０４ｆは、入力された乱数ｒ３と第一暗号文Ｃ１とを用いてＣ１ｒ３を計算し、これを第二入力情報τ２とする（ステップＳ３１０３ｉ）。
【００８６】
第一入力情報計算部２１０４ｂ、第二入力情報計算部２１０４ｄ、第三入力情報計算部３１０４ｆは、以上のように生成した第一入力情報τ１及び第二入力情報τ２を対応する自然数（ａ，ｂ）の情報とともに出力する（ステップＳ３１０３ｅ）。なお、本形態の第一入力情報τ１及び第二入力情報τ２は、それぞれ、乱数ｒ１，ｒ２，ｒ３によって第一暗号文Ｃ１との関係をかく乱させた情報である。これにより、再暗号化装置３１は、第一暗号文Ｃ１を能力提供装置３２に対して隠蔽できる。
【００８７】
《Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理》
以下、図８を用いて本形態のＳ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理を説明する。
【００８８】
制御部１２０５（図３）は、入力された自然数（ａ，ｂ）に応じ、第一出力情報計算部２２０１、第二出力情報計算部２２０２、及び第三出力情報計算部３２０３を制御する。
【００８９】
制御部１２０５の制御に基づき、ｂ≠１の場合の第一入力情報τ１＝μｈｒ１Ｃ１ｂは能力提供装置３２（図３）の第一出力情報計算部２２０１に入力され、ａ≠１の場合の第二入力情報τ２＝μｈｒ２Ｃ１ａは第二出力情報計算部２２０２に入力される。また、ｂ＝１の場合の第一入力情報τ１＝Ｃ１ｒ３やａ＝１の場合の第二入力情報τ２＝Ｃ１ｒ３は第三出力情報計算部３２０３に入力される（ステップＳ３２００）。
【００９０】
制御部１１１３でｂが１であるかが判定され（ステップＳ３２０５）、ｂ≠１であると判定された場合、前述のステップＳ２２０１の処理が実行される。その後、制御部１１１３でａが１であるかが判定され（ステップＳ３２０８）、ａ≠１であると判定された場合、前述したステップＳ２２０２の処理が実行されてステップＳ３２０３に進む。
【００９１】
一方、ステップＳ３２０８でａ＝１であると判定された場合、第三出力情報計算部３２０３は、第二入力情報τ２＝Ｃ１ｒ３と鍵記憶部１２０４に格納された第一復号鍵ｓ１及び第二暗号化鍵ｙ２とを用い、或る確率より大きな確率でｆ（Ｃ１ｒ３）を正しく計算し、得られた計算結果を第三出力情報ｚ３とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部３２０３での計算結果がｆ（Ｃ１ｒ３）となる場合もあれば、ｆ（Ｃ１ｒ３）とならない場合もある（ステップＳ３２０９）。その後、ステップＳ３２０３に進む。
【００９２】
また、ステップＳ３２０５でｂ＝１であると判定された場合、第三出力情報計算部３２０３は、第二入力情報τ１＝Ｃ１ｒ３と鍵記憶部１２０４に格納された第一復号鍵ｓ１及び第二暗号化鍵ｙ２とを用い、或る確率より大きな確率でｆ（Ｃ１ｒ３）を正しく計算し、得られた計算結果を第三出力情報ｚ３とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部３２０３での計算結果がｆ（Ｃ１ｒ３）となる場合もあれば、ｆ（Ｃ１ｒ３）とならない場合もある（ステップＳ３２０６）。
【００９３】
その後、制御部１１１３でａが１であるかが判定され（ステップＳ３２０７）、ａ＝１であると判定された場合にはステップＳ３２０３に進み、ａ≠１であると判定された場合にはステップＳ２２０２に進む。
【００９４】
ステップＳ３２０３では、第一出力情報ｚ１を生成した第一出力情報計算部２２０１は第一出力情報ｚ１を出力し、第二出力情報ｚ２を生成した第二出力情報計算部２２０２は第二出力情報ｚ２を出力し、第三出力情報ｚ３を生成した第三出力情報計算部３２０２は第三出力情報ｚ３を出力する（ステップＳ３２０３）。
【００９５】
《ステップＳ３１０４及びＳ３１０５の処理》
図７に戻り、制御部１１１３の制御のもと、第一出力情報ｚ１は再暗号化装置３１（図２）の第一計算部２１０５に入力され、第二出力情報ｚ２は第二計算部２１０８に入力され、第三出力情報ｚ３は第三計算部３１０９に入力される（ステップＳ３１０４）。
【００９６】
ｂ≠１であれば、第一計算部２１０５が、前述のステップＳ２１０５の処理によってｕを生成し、ｂ＝１であれば、第三計算部３１０９が、ｚ３１／ｒ３を計算してその計算結果をｕとする。計算結果ｕは第一べき乗計算部１１０６に送られる。ここで、ｂ＝１の場合、ｕ＝ｚ３１／ｒ３＝ｆ（Ｃ１）ｘ３となる。すなわち、ｚ３１／ｒ３は、ｆ（Ｃ１）について誤差Ｘ３を持つ標本器となる。その理由については後述する（ステップＳ３１０５）。
【００９７】
《ステップＳ３１０８の処理》
ａ≠１であれば、第二計算部２１０８が、前述のステップＳ２１０８の処理によってｖを生成し、ａ＝１であれば、第三計算部３１０９が、ｚ３１／ｒ３を計算してその計算結果をｖとする。計算結果ｖは第二べき乗計算部１１０９に送られる。ここで、ａ＝１の場合、ｖ＝ｚ３１／ｒ３＝ｆ（Ｃ１）ｘ３となる。すなわち、ｚ３１／ｒ３は、ｆ（Ｃ１）について誤差Ｘ３を持つ標本器となる。その理由については後述する（ステップＳ３１０８）。
【００９８】
なお、ｚ３１／ｒ３の計算、すなわちｚ３のべき乗根の計算が困難な場合には、次のようにしてｕ及び／又はｖを計算してもよい。第三計算部３１０９は、乱数ｒ３とその乱数ｒ３に基づいて計算されたｚ３の組を順次（α１，β１），（α２，β２），…，（αｍ，βｍ），…として図示していない記憶部に記憶する。ｍは自然数である。第三計算部３１０９は、α１，α２，…，αｍの最小公倍数が１になれば、γ１，γ２，…，γｍを整数としてγ１α１＋γ２α２＋…＋γｍαｍ＝１となるγ１，γ２，…，γｍを計算して、そのγ，γ２，…，γｍを用いてΠｉ＝１ｍβｉγｉ＝β１γ１β２γ２…βｍγｍを計算して、その計算結果をｕ及び／又はｖとしてもよい。
【００９９】
≪ｚ３１／ｒ３がｆ（Ｃ１）について誤差Ｘ３を持つ標本器となる理由について≫
Ｒを乱数として、能力提供装置３２がＣ１Ｒを用いて行う計算の計算結果をＢ（Ｃ１Ｒ）とする。すなわち、第一出力情報計算部２２０１や第二出力情報計算部２２０２や第三出力情報計算部３２０３が再暗号化装置３１に返す計算結果をｚ＝Ｂ（Ｃ１Ｒ）とする。さらに、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（Ｃ１Ｒ）１／Ｒｆ（Ｃ１）−１と定義する。
【０１００】
このとき、ｚ１／Ｒ＝Ｂ（Ｃ１Ｒ）１／Ｒ＝Ｘｆ（Ｃ１）＝ｆ（Ｃ１）Ｘとなる。すなわち、ｚ１／Ｒは、ｆ（Ｃ１）について誤差Ｘを持つ標本器となる。
【０１０１】
上記式展開において、Ｘ＝Ｂ（Ｃ１Ｒ）１／Ｒｆ（Ｃ１Ｒ）−１であり、Ｂ（Ｃ１Ｒ）１／Ｒ＝Ｘｆ（Ｃ１Ｒ）であるという性質を用いている。この性質は、Ｒが乱数であることに基づく。
【０１０２】
したがって、ｒ３が乱数であることを考慮すると、同様に、ｚ１／Ｒがｆ（Ｃ１）について誤差Ｘ３を持つ標本器となるのである。
【０１０３】
《その他》
第一実施形態と同様、再暗号文取得装置３３がローカルに含む再暗号化装置３３３１に第一暗号文Ｃ１が入力され、再暗号化装置３３３１と能力提供装置３２との間で、前述の図７及び図８に記載された処理が実行されてもよい。この処理は例えば再暗号化装置３１が再暗号化装置３３３１に置換された処理となる。或いは、この処理の際、上述した能力提供装置３２の処理の少なくとも一部が再暗号化装置３１によって実行されてもよい。また再暗号化装置３３３１は、再暗号化装置３１及び能力提供装置３２がそれぞれどのような処理を行っているかを知る必要はない。少なくとも、再暗号化装置３１及び能力提供装置３２からなるシステムとして図８に記載された処理が実行されればよい。
【０１０４】
［第四実施形態］
第四実施形態の再暗号化システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した他の例である。具体的には、第二暗号化方式がＥｌＧａｍａｌ暗号方式であり、関数ｆが準同型関数である例を示す。なお、第一暗号化方式には特に限定はなく、第一暗号化方式はＥｌＧａｍａｌ暗号方式のような確率暗号方式であってもよいし、ＲＳＡ暗号方式のような確定暗号方式であってもよい。
【０１０５】
以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。
【０１０６】
図１に例示するように、第四実施形態の再暗号化システム４は、再暗号化装置１１が再暗号化装置４１に置換され、能力提供装置１２が能力提供装置４２に置換され、再暗号文取得装置１３が再暗号文取得装置４３に置換されたものである。
【０１０７】
図２に例示するように、第四実施形態の再暗号化装置４１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部４１０４と第一計算部４１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部４１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部４１１１と最終出力部１１１２と制御部１１１３とを有する。図６に例示するように、本形態の入力情報提供部４１０４は、例えば、第一乱数生成部４１０４ａと第一入力情報計算部４１０４ｂと第二乱数生成部４１０４ｃと第二入力情報計算部４１０４ｄと鍵記憶部４１０４ｅとを有する。
【０１０８】
図３に例示するように、第四実施形態の能力提供装置４２は、例えば、第一出力情報計算部４２０１と第二出力情報計算部４２０２と鍵記憶部１２０４と制御部１２０５とを有する。
【０１０９】
＜処理の前提＞
第四実施形態では、群Ｇが巡回群Ｇ１，Ｇ２の直積Ｇ１×Ｇ２、μｇ１が群Ｇ１の生成元、μｇ２が群Ｇ２の生成元、第二暗号化鍵ｙ２がμｇ２ｓ２、第二暗号文Ｃ２が（μｇ１ｒ，ｍｙ２ｒ）∈Ｇ１×Ｇ２、ｒが整数の乱数、値ｕａが（ｃ１ｕ，ｃ２ｕ）∈Ｇ１×Ｇ２、値ｖｂが（ｃ１ｖ，ｃ２ｖ）∈Ｇ１×Ｇ２である。Ｇ１＝Ｇ２であってもよいし、Ｇ１≠Ｇ２であってもよい。また、前述のように第一暗号化方式には限定はないが、例えば第一暗号化方式がＥｌＧａｍａｌ暗号方式である場合には、群Ｈが巡回群Ｈ１，Ｈ２の直積Ｈ１×Ｈ２、ｒ’が整数の乱数、μｈ１が群Ｈ１の生成元、μｈ２が群Ｈ２の生成元、第一暗号化鍵ｙ１がμｈ２ｓ１、第一暗号文Ｃ１が（μｈ１ｒ’，ｍｙ１ｒ’）∈Ｈ１×Ｈ２となる。Ｈ１＝Ｈ２であってもよいし、Ｈ１≠Ｈ２であってもよい。
【０１１０】
なお、Α＝（α１，α２）∈Ｇ１×Ｇ２，Β＝（β１，β２）∈Ｇ１×Ｇ２，及びεが自然数である場合、Αεは（α１ε，α２ε）を表し、Α−εは（α１−ε，α２−ε）を表し、ΑΒは（α１β１，α２β２）を表す。同様に、εが自然数、Α＝（α１，α２）∈Ｈ１×Ｈ２，Β＝（β１，β２）∈Ｈ１×Ｈ２である場合、Αεは（α１ε，α２ε）を表し、Α−εは（α１−ε，α２−ε）を表し、ΑΒは（α１β１，α２β２）を表す。また、ｅ（α，β）を（α，β）∈Ｇ１×Ｇ２に対して巡回群ＧＴの元を与える双線形写像とする。双線形写像の例は、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等参照）。また、第一暗号化鍵ｙ１及び第二暗号化鍵ｙ２が、再暗号化装置１１の入力情報提供部４１０４が含む鍵記憶部４１０４ｅに格納されているものとする。
【０１１１】
＜処理＞
図７及び図８に例示するように、第四実施形態の処理は第一実施形態のステップＳ１１０３〜Ｓ１１０５，Ｓ１１０７，Ｓ１１０８，Ｓ１１１０，Ｓ１２００〜Ｓ１２０３が、それぞれ、ステップＳ４１０３〜Ｓ４１０５，Ｓ４１０７，Ｓ４１０８，Ｓ４１１０，Ｓ４２００〜Ｓ４２０３に置換されたものである。以下ではステップＳ４１０３〜Ｓ４１０５，Ｓ４１０７，Ｓ４１０８，Ｓ４１１０，Ｓ４２００〜Ｓ４２０３の処理のみを説明する。
【０１１２】
《ステップＳ４１０３の処理》
再暗号化装置４１（図２）の入力情報提供部４１０４は、入力された第一暗号文Ｃ１に対応する第一入力情報τ１及び第二入力情報τ２を生成して出力する（図７／ステップＳ４１０３）。以下、図１０を用いて本形態のステップＳ４１０３の処理を説明する。
【０１１３】
第一乱数生成部４１０４ａ（図６）は、群Ｈの任意の元ｈｒ１∈Ｈを生成する。本形態では群Ｈからランダムかつ一様に元ｈｒ１が選択される（一様乱数）。生成された元ｈｒ１は、第一入力情報計算部４１０４ｂ、及び第一計算部４１０５に送られる（ステップＳ４１０３ａ）。
【０１１４】
第一入力情報計算部４１０４ｂは、自然数選択部１１０２で選択された自然数ｂ、第一暗号文Ｃ１、元ｈｒ１、及び鍵記憶部４１０４ｅから抽出した第一暗号化鍵ｙ１を用い、第一暗号化方式によって第一暗号化鍵ｙ１を用いて元ｈｒ１を暗号化したある暗号文Ｃ１’についてＣ１ｂＣ１’を計算し、Ｃ１ｂＣ１’を第一入力情報τ１とする（ステップＳ４１０３ｂ）。
【０１１５】
第二乱数生成部４１０４ｃは、群Ｈの任意の元ｈｒ２∈Ｈを生成する。本形態では群Ｈからランダムかつ一様に元ｈｒ２が選択される（一様乱数）。生成された元ｈｒ２は、第二入力情報計算部４１０４ｄ、及び第二計算部４１０８に送られる（ステップＳ４１０３ｃ）。
【０１１６】
第二入力情報計算部４１０４ｂは、自然数選択部１１０２で選択された自然数ａ、第一暗号文Ｃ１、元ｈｒ２、及び鍵記憶部４１０４ｅから抽出した第一暗号化鍵ｙ１を用い、第一暗号化方式によって第一暗号化情報ｙ１を用いて元ｈｒ２を暗号化したある暗号文Ｃ１”について、Ｃ１ａＣ１”を計算し、Ｃ１ａＣ１”を第二入力情報τ２とする（ステップＳ４１０３ｄ）。
【０１１７】
第一入力情報計算部４１０４ｂは、以上のように生成した第一入力情報τ１＝Ｃ１ｂＣ１’を出力する。第二入力情報計算部４１０４ｄは、以上のように生成した第二入力情報τ２＝Ｃ１ａＣ１”を出力する（ステップＳ４１０３ｅ）。
【０１１８】
《ステップＳ４２００〜Ｓ４２０３の処理》
図８に例示するように、まず、第一入力情報τ１＝Ｃ１ｂＣ１’が能力提供装置４２（図３）の第一出力情報計算部４２０１に入力され、第二入力情報τ２＝Ｃ１ａＣ２”が第二出力情報計算部４２０２に入力される（ステップＳ４２００）。
【０１１９】
第一出力情報計算部４２０１は、第一入力情報τ１＝Ｃ１ｂＣ１’と鍵記憶部１２０４に格納された第一復号鍵ｓ１及び第二暗号化鍵ｙ２とを用い、或る確率より大きな確率でｆ（Ｃ１ｂＣ１’）を正しく計算し、計算結果を第一出力情報ｚ１とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部４２０１での計算結果がｆ（Ｃ１ｂＣ１’）となる場合もあれば、ｆ（Ｃ１ｂＣ１’）とならない場合もある（ステップＳ４２０１）。
【０１２０】
なお、本形態の関数ｆは、第一暗号化方式に則って第一復号鍵ｓ１で暗号文を復号して得られる値をＥｌＧａｍａｌ暗号方式に則って第二暗号化鍵ｙ２で暗号化するための準同型関数である。例えば、第一暗号化方式も第二暗号化方式もＥｌＧａｍａｌ暗号方式で或る場合、関数ｆは、ＥｌＧａｍａｌ暗号方式に則って第一復号鍵ｓ１で暗号文を復号して得られる値を、ＥｌＧａｍａｌ暗号方式に則って第二暗号化鍵ｙ２で暗号化するための準同型関数である。
【０１２１】
第二出力情報計算部４２０２は、第二入力情報τ２＝Ｃ１ａＣ１”と鍵記憶部１２０４に格納された第一復号鍵ｓ１及び第二暗号化鍵ｙ２とを用い、或る確率より大きな確率でｆ（Ｃ１ａＣ１”）を正しく計算可能であり、得られた計算結果を第二出力情報ｚ２とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部４２０２での計算結果がｆ（Ｃ１ａＣ１”）となる場合もあれば、ｆ（Ｃ１ａＣ１”）とならない場合もある（ステップＳ４２０２）。
【０１２２】
第一出力情報計算部４２０１は第一出力情報ｚ１を出力し、第二出力情報計算部４２０２は第二出力情報ｚ２を出力する（ステップＳ４２０３）。
【０１２３】
《ステップＳ４１０４及びＳ４１０５の処理》
図７に戻り、第一出力情報ｚ１は再暗号化装置４１（図２）の第一計算部４１０５に入力され、第二出力情報ｚ２は第二計算部４１０８に入力される（ステップＳ４１０４）。
【０１２４】
第一計算部４１０５は、入力された第一出力情報ｚ１、元ｈｒ１、及び鍵記憶部４１０４ｅ（図６）から読み出した第二暗号化鍵ｙ２を用い、第二暗号化方式によって第二暗号化鍵ｙ２を用いて元ｈｒ１を暗号化したある暗号文Ｃ２’について、ｚ１（Ｃ２’）−１を計算してその計算結果をｕとする（ステップＳ４１０５）。計算結果ｕは、第一べき乗計算部１１０６に送られる。ここで、ｕ＝ｚ１（Ｃ２’）−１＝ｆ（Ｃ１）ｂｘ１となる。すなわち、ｚ１（Ｃ２’）−１は、ｆ（Ｃ１）について誤差Ｘ１を持つ乱数化可能標本器の出力となる。その理由については後述する。
【０１２５】
《ステップＳ４１０８の処理》
第二計算部４１０８は、入力された第二出力情報ｚ２、元ｈｒ２、及び鍵記憶部４１０４ｅ（図６）から読み出した第二暗号化鍵ｙ２を用い、第二暗号化方式によって第二暗号化鍵ｙ２を用いて元ｈｒ２を暗号化したある暗号文Ｃ２”について、ｚ２（Ｃ２”）−１を計算してその計算結果をｖとする。計算結果ｖは、第二べき乗計算部１１０９に送られる。ここで、ｖ＝ｚ２（Ｃ２”）−１＝ｆ（Ｃ１）ａｘ２となる。すなわち、ｚ２（Ｃ２”）−１は、ｆ（Ｃ１）について誤差Ｘ２を持つ乱数化可能標本器の出力となる。その理由については後述する。
【０１２６】
《ステップＳ４１０７の処理》
判定部４１１１は、第一リスト記憶部１１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１１１０に記憶された組（ｖ，ｖ’）の中で、ｕ’とｖ’とが互いに同一の平文に対する暗号文の類に属するものがあるかを判定する。本形態の判定部４１１１は、ｕ’＝（ｃ１ｕ，ｃ２ｕ）及びｖ’＝（ｃ１ｖ，ｃ２ｖ）に対して、関係ｅ（μｇ１，ｃ２ｕ）／ｅ（ｃ１ｕ，ｙ２）＝ｅ（μｇ１，ｃ２ｖ）／ｅ（ｃ１ｖ，ｙ２）を満たすものがあるかを判定する（ステップＳ４１０７）。ｕ’とｖ’がこの関係を満たすかを判定することで、ｕ’とｖ’とが互いに同一の平文に対する暗号文の類に属することを判定できる理由については後述する。
【０１２７】
もし、第二リスト記憶部１１１０に組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ４１０７の処理を行わずに、次のステップＳ１１０８の処理を行う。同一の平文に対する暗号文の類に属するｕ’とｖ’との組があった場合（上記の関係を満たすｕ’とｖ’との組があった場合）には、ステップＳ１１１４に進む。同一の平文に対する暗号文の類に属するｕ’とｖ’との組がなかった場合には、ステップＳ４１０８に進む。
【０１２８】
《ステップＳ４１１０の処理》
判定部４１１１は、第一リスト記憶部１１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部４１１０に記憶された組（ｖ，ｖ’）の中で、ｕ’とｖ’とが互いに同一の平文に対する暗号文の類に属するものがあるかを判定する。本形態の判定部４１１１は、ｕ’＝（ｃ１ｕ，ｃ２ｕ）及びｖ’＝（ｃ１ｖ，ｃ２ｖ）に対して、関係ｅ（μｇ１，ｃ２ｕ）／ｅ（ｃ１ｕ，ｙ２）＝ｅ（μｇ１，ｃ２ｖ）／ｅ（ｃ１ｖ，ｙ２）を満たすものがあるかを判定する（ステップＳ４１１０）。同一の平文に対する暗号文の類に属するｕ’とｖ’との組があった場合には、ステップＳ１１１４に進む。同一の平文に対する暗号文の類に属するｕ’とｖ’との組がなかった場合には、ステップＳ１１１１に進む。
【０１２９】
なお、特殊な群Ｇ１，Ｇ２や双線形写像ｅを用いた場合、ステップＳ４１０７及びＳ４１１０の処理を再暗号化装置４１に実行させることができる者を制限できる。この詳細については後述する。
【０１３０】
《ｚ１（Ｃ２’）−１，ｚ２（Ｃ２”）−１がｆ（Ｃ１）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器の出力となる理由について》
任意の元ｈｒ１を固定して考えると、第二暗号文Ｃ（ｙ２，ｍ）＝（μｇ１ｒ，ｍｙ２ｒ）における乱数ｒを確率空間とする確率分布について、以下の関係が成り立つ。ただし、Ｄ（ｓ１，Ｃ１）は、第一暗号化方式に則って第一暗号文Ｃ１を第一復号鍵ｓ１で復号するための関数を表す。また、ｈｒ２’＝Ｄ（ｓ１，Ｃ１）ａｈｒ２とする。ｒを乱数として、あるｒ２が存在して
ｆ（Ｃ１ａＣ１”）（Ｃ２”）−１
＝（μｇ１ｒ，Ｄ（ｓ１，Ｃ１）ａｈｒ２ｙ２ｒ）（μｇ１ｒ２，ｈｒ２ｙ２ｒ２）−１
となるから、
ｆ（Ｃ１ａＣ１”）（Ｃ２”）−１
＝（μｇ１ｒ−ｒ２，Ｄ（ｓ１，Ｃ１）ａｙ２ｒ−ｒ２）
となる。したがって、確率分布ｆ（Ｃ１ａＣ１”）（Ｃ２”）−１は確率分布ｆ（Ｃ１）ａと等しい。
【０１３１】
したがって、Ｃ１”を確率変数とみなして、群Ｇに値を持つ確率変数Ｘ２＝ｚ２ｆ（Ｃ１ａＣ１”）−１を考えると、
ｚ２（Ｃ２”）−１＝ｚ２ｆ（Ｃ１ａＣ１”）−１ｆ（Ｃ１ａＣ１”）（Ｃ２”）−１
であるから、この確率分布はｘ２∈Ｘ２についてｘ２ｆ（Ｃ１）ａの確率分布と等しい。
【０１３２】
同様に、ｚ１（Ｃ２’）−１の確率分布はｘ１∈Ｘ１についてｆ（Ｃ１）ｂｘ１の確率分布と等しい。Ｃ１”を確率変数とみなすとき、Ｃ１ａＣ１”の分布はＣ１”の分布と等しいから、確率変数Ｘ２の確率分布は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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【符号の説明】
【０２０２】
１〜５  再暗号化システム
１１〜５１  再暗号化装置
１２〜５２  能力提供装置
１３〜５３  再暗号文取得装置
【図１】
0005562284.tif 000002
【図２】
0005562284.tif 000003
【図３】
0005562284.tif 000004
【図４】
0005562284.tif 000005
【図５】
0005562284.tif 000006
【図６】
0005562284.tif 000007
【図７】
0005562284.tif 000008
【図８】
0005562284.tif 000009
【図９】
0005562284.tif 000010
【図１０】
0005562284.tif 000011
【図１１】
0005562284.tif 000012
【図１２】
0005562284.tif 000013