"何れかの端末装置に対応する登録許可情報を格納する登録許可情報記憶部と、暗号文と端末情報とが入力される入力部と、前記暗号文の復号結果に対応する応答情報を生成する復号部と、前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記応答情報を出力する出力部と、を含む鍵装置を有する復号システム。請求項1の復号システムであって、前記端末装置に対応する登録許可情報は、前記端末装置に固有な情報であり、前記端末情報は、何れかの端末装置に固有な情報である、ことを特徴とする復号システム。請求項1又は2の復号システムであって、前記端末情報に対応する復号鍵である端末復号鍵を格納する端末情報記憶部を含む端末装置を有し、前記端末情報に対応する前記登録許可情報は暗号化鍵であり、前記応答情報は、前記端末情報に対応する前記登録許可情報を暗号化鍵とし、前記暗号文の復号結果を暗号化した情報であり、前記端末装置は、前記端末復号鍵を用いて前記応答情報を復号する第2復号部を含む、ことを特徴とする復号システム。請求項1から3の何れかの復号システムであって、第2暗号文と乱数とに対応する前記暗号文を生成する暗号化部と、前記暗号文の復号結果と前記乱数とから前記第2暗号文の復号結果を得る第3復号部と、を含む端末装置を有する、ことを特徴とする復号システム。請求項4の復号システムであって、前記暗号文及び前記第2暗号文は準同型暗号方式に則って暗号化された暗号文であり、前記暗号化部は、前記乱数を暗号化して得られる乱数暗号文と前記第2暗号文との乗法によって前記暗号文を生成し、前記第3復号部は、前記暗号文の復号結果と前記乱数の逆元の乗法によって前記第2暗号文の復号結果を得る、ことを特徴とする復号システム。請求項1から3の何れかの復号システムであって、G,Hが巡回群、fxが群Hの元である第3暗号文xを特定の秘密鍵で復号して群Gの元を得るための復号関数、X1,X2が群Gに値を持つ確率変数、x1が確率変数X1の実現値、x2が確率変数X2の実現値、a,bが互いに素である自然数であり、前記第3暗号文xの生成に用いられた公開鍵に対応する鍵装置情報で特定される鍵装置に対し、前記第3暗号文xに対応する群Hの元である第一入力情報τ1及び第二入力情報τ2である前記暗号文と前記端末装置に対応する端末情報とを出力する入力情報提供部を含む端末装置を有し、前記鍵装置の前記復号部は、前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第一入力情報τ1を用い、或る確率より大きな確率でfτ1を正しく計算し、得られた計算結果を第一出力情報z1とする第一出力情報生成部と、前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第二入力情報τ2を用い、或る確率より大きな確率でfτ2を正しく計算し、得られた計算結果を第二出力情報z2とする第二出力情報生成部と、を含み、前記応答情報は、前記第一出力情報z1及び前記第二出力情報z2であり、前記端末装置は、前記第一出力情報z1から計算結果u=fxbx1を生成する第一計算部と、前記第二出力情報z2から計算結果v=fxax2を生成する第二計算部と、前記計算結果u及びvがua=vbを満たす場合に、a’ab’b=1を満たす整数a’,b’についてのub’va’を出力する最終出力部と、を含む、ことを特徴とする復号システム。請求項1から3の何れかの復号システムであって、GM,HMが行列の集合、fMxMが集合HMの元である第3暗号文xMを特定の秘密鍵で復号して集合GMの元を得るための復号関数、MX1,MX2が集合GMに値を持つ確率変数、Mx1が確率変数MX1の実現値、Mx2が確率変数MX2の実現値、aMが集合HMの元であり、前記第3暗号文xMの生成に用いられた公開鍵に対応する鍵装置情報で特定される鍵装置に対し、前記第3暗号文xMに対応する群Hの元である第一入力情報Mτ1及び第二入力情報Mτ2である前記暗号文と前記端末装置に対応する端末情報とを出力する入力情報提供部を含む端末装置を有し、前記鍵装置の前記復号部は、前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第一入力情報Mτ1を用い、或る確率より大きな確率でfMMτ1を正しく計算し、得られた計算結果を第一出力情報Mz1とする第一出力情報生成部と、前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第二入力情報Mτ2を用い、或る確率より大きな確率でfMMτ2を正しく計算し、得られた計算結果を第二出力情報Mz2とする第二出力情報生成部と、を含み、前記応答情報は、前記第一出力情報Mz1及び前記第二出力情報Mz2であり、前記端末装置は、前記第一出力情報Mz1から計算結果uM=fMxMMx1を生成する第一計算部と、前記第二出力情報Mz2から計算結果vM=fMxMaMMx2を生成する第二計算部と、前記計算結果uM及びvMがuMaM=vMを満たす場合にuMを出力する最終出力部と、を含む、ことを特徴とする復号システム。何れかの端末装置に対応する登録許可情報を格納する登録許可情報記憶部と、暗号文と端末情報とが入力される入力部と、前記暗号文の復号結果に対応する応答情報を生成する復号部と、前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記応答情報を出力する出力部と、を有する鍵装置。何れかの端末装置に対応する登録許可情報を鍵装置の登録許可情報記憶部に格納するステップと、暗号文と端末情報とが前記鍵装置の入力部に入力されるステップと、前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記鍵装置の出力部で前記暗号文の復号結果に対応する応答情報を出力するステップと、を有する復号方法。請求項9の復号方法の各ステップをコンピュータに実行させるためのプログラム。しかしながら、第1の方針では端末装置の機能を遠隔操作でロックすることができない場合には、端末装置の復号機能を無効化できない。第2の方針では、すべての端末装置に格納された鍵の更新が必要となり、運用のためのコストがかさむ。本発明はこのような点に鑑みてなされたものであり、端末装置に対する制御を行うことなく、端末装置が暗号文の復号結果を閲覧する権限を無効化できる技術を提供することを目的とする。何れかの端末装置に対応する登録許可情報を鍵装置の登録許可情報記憶部に格納しておく。鍵装置に暗号文と端末情報とが入力されると、鍵装置は当該端末情報が登録許可情報記憶部に格納された何れかの登録許可情報に対応する場合に、暗号文の復号結果に対応する応答情報を出力する。登録許可情報が登録許可情報記憶部に格納された端末装置に対応する端末情報と暗号文とが鍵装置に入力された場合、当該端末装置は鍵装置から出力された応答情報から復号結果を得ることができる。一方、登録許可情報記憶部から当該登録許可情報が削除された場合には鍵装置から応答情報は出力されず、当該端末装置は復号結果を得ることができない。このように本発明では、端末装置に対する制御を行うことなく、登録許可情報記憶部に格納された登録許可情報を削除することで、削除した登録許可情報に対応する端末装置が暗号文の復号結果を閲覧する権限を無効化できる。以下、図面を参照して本発明の実施形態を説明する。[第一実施形態]本発明の第一実施形態を説明する。<構成>図1に例示するように、第一実施形態の復号システム1は、UUは1以上の整数個の端末装置11-uu=1,,Uと鍵装置12とを有し、これらはネットワークを通じて通信可能に構成されている。図2に例示するように、本形態の端末装置11-uは、それぞれアドレス記憶部111-uと暗号文記憶部112-uと入力部113-uと出力部114-uと制御部115-uと復号処理部116-uとを有する。本形態の鍵装置12は、安全に管理される装置であり、登録許可情報記憶部121と秘密鍵記憶部122と入力部123と出力部124と制御部125と復号部126と登録処理部127とを有する。端末装置11-u及び鍵装置12は、ルータ装置、サーバ装置、携帯電話、ICカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータなどである。端末装置11-uは制御部115-uの制御のもとで各処理を実行し、鍵装置12は制御部125の制御のもとで各処理を実行する。<事前処理>端末装置11-u図2の暗号文記憶部112-uには、公開鍵暗号方式に則って公開鍵yで平文mを暗号化して得られる暗号文C=Ency,mが格納されている。公開鍵暗号方式の例は、ElGamal暗号方式、RSA暗号方式、Pailler暗号方式などである。アドレス記憶部111-uには、端末装置11-uのアドレスAddu端末情報が格納されている。アドレスの例はIPアドレスなどである。鍵装置12の秘密鍵記憶部122には、公開鍵yに対応する秘密鍵sが格納されている。登録許可情報記憶部121には、何れかの端末装置11-u’u’=1,,UのアドレスAddu’登録許可情報のリストListが格納されている。登録処理部127は、リストListに端末装置11-u’のアドレスAddu’を追加する旨の指示や、リストListから端末装置11-u’のアドレスAddu’を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部127は、登録許可情報記憶部121に格納されたリストListに、指示された端末装置11-u’のアドレスAddu’を追加する。後者の指示が入力された登録処理部127は、登録許可情報記憶部121に格納されたリストListから、指示された端末装置11-u’のアドレスAddu’を削除する。<復号処理>図3に例示するように、端末装置11-u図2の復号処理部116-uは、復号を行う暗号文Cを暗号文記憶部122-uから読み込み、端末装置11-uのアドレスAdduをアドレス記憶部111-uから読み込み、これらを出力部114-uに送る。出力部114-uには鍵装置12のアドレスまたはそれに対応する情報が格納されており、出力部114-uは暗号文CとアドレスAdduとを鍵装置12に対して出力するステップS101。暗号文CとアドレスAdduはネットワーク経由で鍵装置12に送信され、鍵装置12の入力部123に入力されるステップS102。暗号文CとアドレスAdduは復号部126に送られる。復号部126は、送られたアドレスAdduが登録許可情報記憶部121に格納されたリストListが含む何れかのアドレスAddu’に一致するか対応するかを判定するステップS103。ステップS103で、送られたアドレスAdduがリストListに含まれる何れかのアドレスAddu’に一致すると判定された場合、復号部126は、秘密鍵記憶部122から秘密鍵sを読み込み、秘密鍵sを用い、公開鍵暗号方式に則って暗号文Cを復号して復号結果m’=Decs,Cを生成するステップS104。復号結果m’暗号文の復号結果に対応する応答情報は出力部124に送られ、出力部124は、暗号文Cを送信した端末装置11-uに対して復号結果m’を出力するステップS105。ステップS103で、送られたアドレスAdduがリストListに含まれる何れのアドレスAddu’とも一致しないと判定された場合、復号部126は、復号することができなかったことを示すエラー情報⊥を出力する。情報⊥は出力部124に送られ、出力部124は暗号文Cを送信した端末装置11-uに対してエラー情報⊥を出力するステップS106。復号結果m’またはエラー情報⊥は端末装置11-uの入力部113-uに入力され、復号処理部116-uに送られるステップS107。復号処理部116-uは復号結果m’またはエラー情報⊥を出力するステップS108。<第一実施形態の特徴>本形態では、登録許可情報記憶部121に格納されたリストListが含むアドレスに対応する端末装置11-uから送信された暗号文Cのみが復号される。そのため、登録許可情報記憶部121に格納されたリストListにアドレスAdduを追加したり、リストListからアドレスAdduを削除したりするだけで、端末装置11-uに暗号文Cの復号結果を取得させるか否かを制御できる。その結果、端末装置11-uに対する制御を行うことなく、登録許可情報記憶部121に格納されたアドレスAdduを削除することで、削除したアドレスAdduに対応する端末装置11-uが暗号文Cの復号結果を閲覧する権限を無効化できる。[第二実施形態]本発明の第二実施形態を説明する。インターネットなどのネットワークでは、DHCP等の技術によって端末装置のアドレスが動的に付与される場合がある。このような場合、端末装置のアドレスをあらかじめ鍵装置に格納しておくことは現実的ではない。これに対して第二実施形態では、端末装置に固有な情報を鍵装置に格納し、鍵装置の出力情報を、固有な情報に対応する端末装置によって復号可能なように暗号化する。以下では第一実施形態との相違点を中心に説明し、第一実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。<構成>図1に例示するように、第二実施形態の復号システム2は、U個の端末装置21-uu=1,,Uと鍵装置22とを有し、これらはネットワークを通じて通信可能に構成されている。図4に例示するように、本形態の端末装置21-uは、それぞれ固有情報記憶部211-uと暗号文記憶部112-uと入力部113-uと出力部114-uと制御部115-uと復号処理部216-uと復号部217-uとを有する。本形態の鍵装置22は、安全に管理される装置であり、登録許可情報記憶部221と秘密鍵記憶部122と入力部123と出力部124と制御部125と復号部226と登録処理部227とを有する。復号部226は判定復号部2261と暗号化部2262とを有する。端末装置21-u及び鍵装置22は、ルータ装置、サーバ装置、携帯電話、ICカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータなどである。端末装置21-uは制御部115-uの制御のもとで各処理を実行し、鍵装置22は制御部125の制御のもとで各処理を実行する。<事前処理>本形態ではアドレス情報記憶部にアドレスが格納される代わりに、端末装置21-uの固有情報記憶部211-uに、端末装置21-uに固有な固有公開情報PTu端末情報及び固有秘密情報STu端末復号鍵が格納されている。固有公開情報PTu及び固有秘密情報STuは、或る暗号化方式における互いに対応する暗号化鍵及び復号鍵のペアである。この暗号化方式の例は、共通鍵暗号、公開鍵暗号、IDベース暗号などである。例えば、この暗号化方式が共通鍵暗号であればPTu=STuである。この暗号化方式が公開鍵暗号方式であれば、固有公開情報PTuは公開鍵であり、固有秘密情報STuはそれに対応する秘密鍵である。この暗号化方式がIDベース暗号方式であれば、固有公開情報PTuは鍵装置22のIDであり、固有秘密情報STuは鍵装置22のIDに対応する秘密鍵である。また本形態では鍵装置の登録許可情報記憶部に何れかの端末装置のアドレスのリストが格納される代わりに、鍵装置22の登録許可情報記憶部221に何れかの端末装置21-u’u’=1,,Uの固有公開情報PTu’登録許可情報のリストListTが格納されている。登録処理部227は、リストListTに端末装置21-u’の固有公開情報PTu’を追加する旨の指示や、リストListTから端末装置21-u’の固有公開情報PTu’を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部227は、登録許可情報記憶部121に格納されたリストListTに、指示された固有公開情報PTu’を追加する。後者の指示が入力された登録処理部127は、登録許可情報記憶部121に格納されたリストListTから、指示された固有公開情報PTu’を削除する。その他は第一実施形態と同様である。<復号処理>図5に例示するように、端末装置21-u図4の復号処理部216-uは、復号を行う暗号文Cを暗号文記憶部122-uから読み込み、端末装置11-uの固有公開情報PTuを固有情報記憶部211-uから読み込み、これらを出力部114-uに送る。出力部114-uには鍵装置12のアドレスまたはそれに対応する情報が格納されており、出力部114-uは暗号文Cと固有公開情報PTuとを鍵装置22に対して出力するステップS201。暗号文Cと固有公開情報PTuはネットワーク経由で鍵装置22に送信され、鍵装置22の入力部123に入力されるステップS202。暗号文Cと固有公開情報PTuは復号部226に送られる。復号部226の判定復号部2261は、送られた固有公開情報PTuが登録許可情報記憶部121に格納されたリストListTが含む何れかの固有公開情報PTu’に一致するか対応するかを判定するステップS203。ステップS203で、送られた固有公開情報PTuがリストListTに含まれる何れかの固有公開情報PTu’に一致すると判定された場合、判定復号部2261は、秘密鍵記憶部122から秘密鍵sを読み込み、秘密鍵sを用い、公開鍵暗号方式に則って暗号文Cを復号して復号結果m’=Decs,Cを生成するステップS104。復号結果m’と固有公開情報PTuとは暗号化部2262に送られる。暗号化部2262は、固有公開情報PTu端末情報に対応する登録許可情報を暗号化鍵とし、暗号文Cの復号結果m’を暗号化した暗号文C’=Enc’PTu,m’を生成するステップS204。暗号文C’暗号文の復号結果に対応する応答情報は出力部124に送られ、出力部124は、暗号文Cを送信した端末装置21-uに対して暗号文C’を出力するステップS205。暗号文C’は端末装置21-uの入力部113-uに入力され、復号部217-uに送られるステップS207。復号部217-u第2復号部は、固有情報記憶部211-uから固有秘密情報STuを読み込み、固有秘密情報STuを復号鍵として用いて暗号文C’を復号し、復号結果m’’=Dec’STu,C’を生成する。復号結果m’’は復号処理部216-uに送られステップS208、復号処理部216-uは復号結果m’’を出力するステップS108。一方ステップS203で、送られた固有公開情報PTuがリストListTに含まれる何れの固有公開情報PTu’とも一致しないと判定された場合、復号部226は、復号することができなかったことを示すエラー情報⊥を出力する。情報⊥は出力部124に送られ、出力部124は暗号文Cを送信した端末装置11-uに対してエラー情報⊥を出力するステップS106。エラー情報⊥は端末装置21-uの入力部113-uに入力され、復号処理部216-uに送られてステップS107出力されるステップS108。<第二実施形態の特徴>本形態では、登録許可情報記憶部221に格納されたリストListTが含む固有公開情報に対応する端末装置21-uから送信された暗号文Cのみが復号される。そのため登録許可情報記憶部121に格納されたリストListTに固有公開情報PTuを追加したり、リストListTから固有公開情報PTuを削除したりするだけで、端末装置21-uに暗号文Cの復号結果を取得させるか否かを制御できる。その結果、端末装置21-uに対する制御を行うことなく、登録許可情報記憶部221に格納された固有公開情報PTuを削除することで、削除した固有公開情報PTuに対応する端末装置21-uが暗号文Cの復号結果を閲覧する権限を無効化できる。また、本形態では端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。[第三実施形態]本発明の第三実施形態を説明する。上述の各実施形態では鍵装置の管理者が暗号文Cの復号結果を知ることができる。したがって、鍵装置の管理者が端末装置の使用者と異なる場合、端末装置の使用者のみが知るべき情報が鍵装置の管理者に知られる可能性がある。これに対して第三実施形態では、鍵装置がランダム帰着可能な暗号文の復号を行う点がこれまでの実施形態と相違する。ランダム帰着可能な暗号化方式は、ランダム化アルゴリズムと復元アルゴリズムとからなる。ランダム化アルゴリズムは、暗号文と乱数とを用いて別の暗号文を出力する確率アルゴリズムで、出力は入力によらずランダムに選ばれた暗号文と識別できない確率分布に従う。復元アルゴリズムはランダム化アルゴリズムの出力である暗号文を復号した結果とランダム化アルゴリズムで用いられた乱数を入力として、もとの暗号文を復号した平文を出力する。このような暗号方式は、例えばElGamal暗号、楕円ElGamal暗号、RSA暗号、Pailler暗号などの準同型暗号方式を用いて容易に構成できる。第三の実施形態は、準同型暗号方式を用いてランダム自己帰着可能な暗号方式を構成した例を示しながら記述する。以下では第一及び第二実施形態との相違点を中心に説明し、第一及び第二実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。<構成>図1に例示するように、第三実施形態の復号システム3は、U個の端末装置21-uu=1,,Uと鍵装置32とを有し、これらはネットワークを通じて通信可能に構成されている。図6に例示するように、本形態の端末装置31-uは、それぞれ固有情報記憶部211-uと暗号文記憶部112-uと入力部113-uと出力部114-uと制御部115-uと復号処理部316-uと復号部317-uとを有する。復号処理部316-uは、乱数生成部3161-uと暗号化部3162-uと復号部3163-uとを有する。本形態の鍵装置32は、安全に管理される装置であり、登録許可情報記憶部221と秘密鍵記憶部122と入力部123と出力部124と制御部125と復号部326と登録処理部227とを有する。復号部326は判定復号部3261と暗号化部3262とを有する。端末装置31-u及び鍵装置32は、ルータ装置、サーバ装置、携帯電話、ICカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータなどである。端末装置31-uは制御部115-uの制御のもとで各処理を実行し、鍵装置32は制御部125の制御のもとで各処理を実行する。<事前処理>第二実施形態と同様である。<復号処理>図7に例示するように、端末装置31-u図6の復号処理部316-uの乱数生成部3161-uが乱数Randを生成し、それを暗号化部3162-u及び復号部3163-uに送る。乱数Randは暗号化部3162-u及び復号部3163-u内に格納されるステップS3011。暗号化部3162-uは、復号を行う暗号文Cを暗号文記憶部122-uから読み込み、暗号方式のランダム自己帰着性から定義されるランダム化アルゴリズムに則り、暗号文C第2暗号文と乱数Randとに対応する暗号文CRを生成する。例えば暗号文Cが準同型暗号方式の暗号文である場合、暗号化部3162-uはそれと同じ準同型暗号方式に則って公開鍵yで乱数Randを暗号化して得られる暗号文乱数暗号文をEncy,Randとし、Ency,RandとCとの乗法によって暗号文CR=Ency,RandCを生成する。暗号文CRと固有公開情報PTuとは出力部114-uに送られるステップS3012。出力部114-uには鍵装置32のアドレスまたはそれに対応する情報が格納されており、出力部114-uは暗号文CRと固有公開情報PTuとを鍵装置32に対して出力するステップS3013。暗号文CRと固有公開情報PTuはネットワーク経由で鍵装置32に送信され、鍵装置32の入力部123に入力されるステップS302。暗号文CRと固有公開情報PTuは復号部326に送られる。復号部326の判定復号部3261は、送られた固有公開情報PTuが登録許可情報記憶部121に格納されたリストListTが含む何れかの固有公開情報PTu’に一致するか対応するかを判定するステップS203。ステップS203で、送られた固有公開情報PTuがリストListTに含まれる何れかの固有公開情報PTu’に一致すると判定された場合、判定復号部3261は、秘密鍵記憶部122から秘密鍵sを読み込み、秘密鍵sを用い、前述の準同型暗号化方式に則って暗号文CRを復号して復号結果mR=Decs,CRを生成するステップS3041。復号結果mRと固有公開情報PTuとは暗号化部3262に送られる。暗号化部3262は、固有公開情報PTu端末情報に対応する登録許可情報を暗号化鍵とし、暗号文CRの復号結果mRを暗号化した暗号文CR’=Enc’PTu,mRを生成するステップS3042。暗号文CR’暗号文の復号結果に対応する応答情報は出力部124に送られ、出力部124は、暗号文CRを送信した端末装置31-uに対して暗号文CR’を出力するステップS305。暗号文CR’は端末装置31-uの入力部113-uに入力され、復号部317-uに送られるステップS307。復号部317-u第2復号部は、固有情報記憶部321-uから固有秘密情報STuを読み込み、固有秘密情報STuを復号鍵として用いて暗号文CR’を復号し、復号結果mR’=Dec’STu,CR’を生成するステップS308。復号結果mR’は復号処理部316も復号部3163-uに送られ、復号部3163-u第3復号部は、暗号方式のランダム自己帰着性から定義される復元アルゴリズムに則り、復号結果mR’と前述の乱数Randとから暗号文C第2暗号文の復号結果m’を生成する。例えば前述した暗号文CR=Ency,RandCである例の場合、復号部3163-uは乱数Randの逆元Rand-1を用い、mR’と元Rand-1との乗法m’=Rand-1mR’によって暗号文Cの復号結果m’を得ることができる。これは準同型暗号方式の暗号化関数および復号関数が準同型性を持つことに基づく。復号処理部316-uは復号結果m’を出力するステップS108。一方ステップS203で、送られた固有公開情報PTuがリストListTに含まれる何れの固有公開情報PTu’とも一致しないと判定された場合、復号部326が復号することができなかったことを示すエラー情報⊥を出力し、第二実施形態のステップS106-S108と同様に処理される。<第三実施形態の特徴>本形態でも端末装置31-uに対する制御を行うことなく、登録許可情報記憶部221に格納された固有公開情報PTuを削除することで、削除した固有公開情報PTuに対応する端末装置31-uが暗号文Cの復号結果を閲覧する権限を無効化できる。また、端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。さらに本形態では、鍵装置32で復号されるのは暗号文Cと乱数Randとに対応する暗号文CRであり、暗号文Cそのものではない。鍵装置32は暗号文CRの復号結果mRを得ることができても、鍵装置32は乱数Randを知らないため復号結果mRから暗号文Cの復号結果を復元することはできない。これにより、鍵装置32の管理者に暗号文Cの復号結果が知られることを防止できる。[第四実施形態]本発明の第四実施形態を説明する。上述の各実施形態では、あらかじめ信頼できる鍵装置が設定され、そのアドレスまたはそれに対応する情報があらかじめ端末装置に格納されている必要があった。これに対して第四実施形態では自己訂正技術を用いることで、信頼できる鍵装置があらかじめ設定されていない場合や、信頼できるか否かが定かではない複数の鍵装置しか存在しない場合であっても、運用が可能な形態である。以下では上述の各実施形態との相違点を中心に説明し、上述の各実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。<構成>図8に例示するように、第四実施形態の復号システム4は、U個の端末装置21-uu=1,,UとKKは1以上の整数個の鍵装置22-kk=1,,Kと鍵装置DBデータベース装置43を有し、これらはネットワークを通じて通信可能に構成されている。図9に例示するように、本形態の鍵装置DB装置43は、鍵装置情報記憶部431と入力部432と出力部433と検索部434とを有する。図10に例示するように、本形態の端末装置41-uは、それぞれ固有情報記憶部211-uと暗号文記憶部412-uと入力部113-uと出力部114-uと制御部115-uと復号処理部416-uと復号部417-uとを有する。本形態の鍵装置42-kは、安全に管理される装置であり、登録許可情報記憶部421-kと秘密鍵記憶部422-kと入力部423-kと出力部424-kと制御部425-kと復号部426-kと登録処理部427-kとを有する。復号部426-kは判定復号部4261-kと暗号化部4262-kとを有する。図11に例示するように、本形態の復号処理部416-uは、例えば、自然数記憶部416a-uと自然数選択部416b-uと整数計算部416c-uと入力情報提供部416d-uと第一計算部416e-uと第一べき乗計算部416f-uと第一リスト記憶部416g-uと第二計算部416h-uと第二べき乗計算部416i-uと第二リスト記憶部416j-uと判定部416k-uと最終出力部416m-uと制御部416n-uとを有する。図12に例示するように、本形態の判定復号部4261-kは、例えば、第一出力情報計算部4261a-kと第二出力情報計算部4261b-kと判定部4261c-kと制御部4261n-kとを有する。鍵装置DB装置43、端末装置41-u及び鍵装置42は、ルータ装置、サーバ装置、携帯電話、ICカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータなどである。端末装置41-uは制御部115-uの制御のもとで各処理を実行し、鍵装置42-kは制御部425-kの制御のもとで各処理を実行する。<事前処理>鍵装置DB装置43図9の鍵装置情報記憶部431には、公開鍵ykをキーとして何れかの鍵装置42-kのアドレスKaddk鍵装置を特定するための鍵装置情報を記録した鍵装置データベースが格納される。例えば、公開鍵のハッシュ値をbase64などの方法でアスキーテキストに変換して、それをホスト名と見なすダイナミックDNSが構成される。鍵装置データベースを用いることで公開鍵ykに対応する鍵装置42-kのアドレスが特定される。なお、必ずしも鍵装置42-kのアドレスが真正である必要はなく、鍵装置42-kが公開鍵ykに対応する秘密鍵skで常に正しく復号処理を行うことが保証されている必要もない。端末装置41-u図10に対する事前処理は、暗号文記憶部に公開鍵暗号方式に則って公開鍵yで平文mを暗号化して得られる暗号文C=Ency,mが格納されている代わりに、暗号文記憶部112-uに、公開鍵暗号方式に則って公開鍵ykで平文mを暗号化して得られる暗号文C=Encyk,mが格納されている。それ以外は第二実施形態と同様である。鍵装置42-kの秘密鍵記憶部122-kには、公開鍵ykに対応する秘密鍵skが格納されている。鍵装置42-kの登録許可情報記憶部421-kに何れかの端末装置411-u’u’=1,,Uの固有公開情報PTu’登録許可情報のリストListTが格納されている。登録処理部427-kは、リストListTに端末装置411-u’の固有公開情報PTu’を追加する旨の指示や、リストListTから端末装置411-u’の固有公開情報PTu’を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部427-kは、登録許可情報記憶部421-kに格納されたリストListTに、指示された固有公開情報PTu’を追加する。後者の指示が入力された登録処理部427-kは、登録許可情報記憶部421-kに格納されたリストListTから、指示された固有公開情報PTu’を削除する。<復号処理>端末装置41-u図10の復号処理部は、復号を行う暗号文C=Encyk,mに対応する公開鍵ykを出力部114-uに出力し、出力部114-uは公開鍵ykを鍵装置DB装置43に送信する。公開鍵ykは鍵装置DB装置43図9の入力部432に入力され、検索部434に送られる。検索部434は、公開鍵ykに対応する鍵装置42-kのアドレスKaddkを抽出し、アドレスKaddkは出力部433から出力される。アドレスKaddkは端末装置41-uの入力部113-uに入力され復号処理部416-uに送られる。図15に例示するように、次に復号処理部416-uは、復号を行う暗号文Cを暗号文記憶部422-uから読み込み、端末装置41-uの固有公開情報PTuを固有情報記憶部211-uから読み込み、これらとアドレスKaddkとを出力部114-uに送る。出力部114-uは暗号文Cと固有公開情報PTuとをアドレスKaddkで特定される鍵装置42-kに対して出力するステップS401。暗号文Cと固有公開情報PTuはネットワーク経由で鍵装置42-kに送信され、鍵装置42-kの入力部423-kに入力されるステップS402。暗号文Cと固有公開情報PTuは復号部426-kに送られる。復号部426-kの判定復号部4261-kは、送られた固有公開情報PTuが登録許可情報記憶部421-kに格納されたリストListTが含む何れかの固有公開情報PTu’に一致するか対応するかを判定するステップS403。送られた固有公開情報PTuが登録許可情報記憶部421-kに格納されたリストListTが含む何れの固有公開情報PTu’とも一致しないと判定された場合、前述したステップS106-S108と同様な処理が実行される。一方、送られた固有公開情報PTuが登録許可情報記憶部421-kに格納されたリストListTが含む何れかの固有公開情報PTu’に一致すると判定された場合、その旨が端末装置41-uに通知され、端末装置41-uと登録許可情報記憶部421-kとの間で以下の自己訂正処理が実行されるステップS404。そして、復号処理部416-uがその結果である暗号文Cの復号結果m’またはエラー情報⊥を出力するステップS108。<自己訂正処理ステップS404>図16及び17を参照して本形態の自己訂正処理を説明する。処理の前提として、G,Hを巡回群、暗号文Cを群Hの元、暗号文Cの復号結果が群Gの元、fxを群Hの元である暗号文x=Cを特定の秘密鍵skで復号して群Gの元を得るための復号関数Decsk,x、群G,Hの生成元をそれぞれμg,μh、X1,X2を群Gに値を持つ確率変数、確率変数X1の実現値をx1、確率変数X2の実現値をx2とする。また、復号処理部416-uの自然数記憶部416a-uには、互いに素である2つの自然数a,bの組a,bが複数種類記憶されているものとする。自然数とは0以上の整数を意味する。Iを群Gの位数未満の2つの自然数の組で互いに素なものの集合とすると、自然数記憶部416a-uにはIの部分集合Sに対応する自然数a,bの組a,bが記憶されていると考えることができる。図16及び17に例示するように、まず、復号処理部416-u図11の自然数選択部416b-uが、自然数記憶部416a-uに記憶された複数の自然数の組a,bから1つの自然数の組a,bをランダムに読み込む。読み込まれた自然数の組a,b少なくとも一部の情報は、整数計算部416c-u、入力情報提供部416d-u、第一べき乗計算部416f-u及び第二べき乗計算部416i-uに送られるステップS404a。整数計算部416c-uは、送られた自然数の組a,bを用いて、a’ab’b=1の関係を満たす整数a’,b’を計算する。自然数a,bは互いに素であるため、a’ab’b=1の関係を満たす整数a’,b’は必ず存在して、その計算方法もよく知られている。たとえば拡張互除法などのよく知られたアルゴリズムによって整数a’,b’を計算して、自然数の組a’,b’の情報は、最終出力部416m-uに送られるステップS404b。制御部416n-uは、t=1とするステップS404c。入力情報提供部416d-uは、入力された暗号文xにそれぞれ対応する群Hの元である第一入力情報τ1及び第二入力情報τ2を生成して出力する。好ましくは、第一入力情報τ1及び第二入力情報τ2はそれぞれ暗号文xとの関係をかく乱させた情報である。これにより、復号処理部416-uは、暗号文xを判定復号部4261-kに対して隠蔽できる。また、好ましくは、本形態の第一入力情報τ1は自然数選択部416b-uで選択された自然数bにさらに対応し、第二入力情報τ2は自然数選択部416b-uで選択された自然数aにさらに対応する。これにより、判定復号部4261-kから提供された復号能力を復号処理部416-uが高い精度で評価することが可能となる。第一入力情報τ1及び第二入力情報τ2は出力部114-u図10から出力され、鍵装置42-kの入力部423-kに入力され判定復号部4261-kに送られるステップS404d。第一入力情報τ1は判定復号部4261-k図12の第一出力情報計算部4261a-kに入力され、第二入力情報τ2は第二出力情報計算部4261b-kに入力されるステップS404e。第一出力情報計算部4261a-kは、第一入力情報τ1と秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfτ1を正しく計算し、得られた計算結果を第一出力情報z1とするステップS404f。第二出力情報計算部4261b-kは、第二入力情報τ2と秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfτ2を正しく計算し、得られた計算結果を第二出力情報z2とするステップS404g。なお、或る確率は100未満の確率である。或る確率の例は無視することができない確率であり、無視することができない確率の例は、セキュリティパラメータkについての広義単調増加関数である多項式を多項式ψkとした場合の1/ψk以上の確率である。すなわち、第一出力情報計算部4261a-kや第二出力情報計算部4261b-kは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部4261a-kでの計算結果がfτ1の場合もあればfτ1でない場合もあり、第二出力情報計算部4261b-kでの計算結果がfτ2の場合もあればfτ2でない場合もある。第一出力情報計算部4261a-kは第一出力情報z1を出力し、第二出力情報計算部4261b-kは第二出力情報z2を出力する。第一出力情報z1および第二出力情報z2は暗号化部4262-kに送られる。暗号化部4262-kは、固有公開情報PTu端末情報に対応する登録許可情報を暗号化鍵とし、第一出力情報z1および第二出力情報z2以下z=z1,z2を暗号化した暗号文Cz=Enc’PTu,zを生成する。暗号文Cz暗号文の復号結果に対応する応答情報は出力部424-kに送られ、出力部424-kは、第一入力情報τ1及び第二入力情報τ2を送信した端末装置41-uに対して暗号文Czを出力するステップS404h。暗号文Czは端末装置41-uの入力部113-uに入力され、復号部417-uに送られる。復号部417-u第2復号部は、固有情報記憶部421-uから固有秘密情報STuを読み込み、固有秘密情報STuを復号鍵として用いて暗号文Czを復号し、復号結果z=Dec’STu,Cz、すなわち第一出力情報z1および第二出力情報z2を生成する。第一出力情報z1は復号処理部416-u図11の第一計算部416e-uに入力され、第二出力情報z2は第二計算部416h-uに入力される。これらの第一出力情報z1及び第二出力情報z2が、判定復号部4261-kから復号処理部416-uに与えられた復号能力に相当するステップS404i。第一計算部416e-uは、第一出力情報z1から計算結果u=fxbx1を生成する。ここで、fxbx1を生成計算するとは、fxbx1と定義される式の値を計算することである。式fxbx1の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。また、第一実施形態では群で定義された演算を乗法的に表現する。すなわちα∈Gに対するαbは、群Gで定義された演算をαに対してb回作用させることを意味し、α1,α2∈Gに対するα1α2は、α1とα2とを被演算子とした群Gで定義された演算を行うことを意味する後述する第五から第七実施形態も同様。計算結果uは第一べき乗計算部416f-uに送られるステップS404j。第一べき乗計算部416f-uはu’=uaを計算する。計算結果uとその計算結果に基づいて計算されたu’との組u,u’は、第一リスト記憶部416g-uに記憶されるステップS404k。判定部416k-uは、第一リスト記憶部416g-uに記憶された組u,u’及び第二リスト記憶部416j-uに記憶された組v,v’の中で、u’=v’となるものがあるか判定するステップS404m。もし、第二リスト記憶部416j-uに組v,v’が記憶されていない場合には、このステップS404mの処理を行わずに、次のステップS404nの処理を行う。u’=v’となるものがあった場合には、ステップS404uに進む。u’=v’となるものがなかった場合には、ステップS404nに進む。ステップS404nでは、第二計算部416h-uが、第二出力情報z2から計算結果v=fxax2を生成する。計算結果vは第二べき乗計算部416i-uに送られるステップS404n。第二べき乗計算部416i-uはv’=vbを計算する。計算結果vとその計算結果に基づいて計算されたv’との組v,v’は、第二リスト記憶部416j-uに記憶されるステップS404p。判定部416k-uは、第一リスト記憶部416g-uに記憶された組u,u’及び第二リスト記憶部416j-uに記憶された組v,v’の中で、u’=v’となるものがあるか判定するステップS404q。u’=v’となるものがあった場合には、ステップS404uに進む。u’=v’となるものがなかった場合には、ステップS404rに進む。ステップS404rでは、制御部416n-uがt=Tmaxであるか判定するステップS404r。Tmaxは予め定められた自然数である。t=Tmaxであれば、制御部416n-uは、計算をすることができなかった旨の情報、例えば記号⊥を出力するステップS404t。t=Tmaxでない場合には、制御部416n-uは、tを1だけインクリメント、すなわちt=t1としてステップS404s、ステップS404dに戻る。計算をすることができなかった旨の情報この例ではエラー情報⊥は、判定復号部4261-kが正しく計算を行う信頼性がTmaxで定められる基準を下回るということを意味する。言い換えれば、Tmax回の繰り返しで正しい演算を行うことができなかったということを意味する。ステップS404uでは、最終出力部416m-uが、u’=v’であると判定されたu’及びv’に対応するu及びvを用いてm’=ub’va’を計算して、出力するステップS404u。このように計算されたm’=ub’va’は高い確率で暗号文x=Cを特定の秘密鍵skで復号した復号結果fxとなる高い確率でub’va’=fxとなる理由については後述する。よって、上述した自己訂正処理を複数回繰り返し、ステップS404uで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、後述するように、設定によっては圧倒的な確率でm’=ub’va’=fxとなる。その場合にはステップS404uで得られた値をそのまま復号結果としてよい。≪高い確率でub’va’=fxとなる理由について≫Xを群Gに値を持つ確率変数とする。w∈Gについて、要求を受けるたびに確率変数Xに従った標本x’に対応するwx’を返すものを、wについて誤差Xを持つ標本器samplerと呼ぶ。w∈Gについて、自然数aが与えられるたびに確率変数Xに従った標本x’に対応するwax’を返すものを、wについて誤差Xを持つ乱数化可能標本器randomizablesamplerと呼ぶ。乱数化可能標本器はa=1として用いられれば標本器として機能する。本実施形態の入力情報提供部416d-uと第一出力情報計算部4261a-kと第一計算部416e-uとの組み合わせが、fxについて誤差X1を持つ乱数化可能標本器第一乱数化可能標本器と呼ぶであり、入力情報提供部416d-uと第二出力情報計算部4261b-kと第二計算部416h-uとの組み合わせが、fxについて誤差X2を持つ乱数化可能標本器第二乱数化可能標本器と呼ぶである。u’=v’が成立するのは、すなわちua=vbが成立するのは、第一乱数化可能標本器がu=fxbを正しく計算しており、第二乱数化可能標本器がv=fxaを正しく計算しているx1及びx2が群Gの単位元egである可能性が高いことを発明者は見出した。第一乱数化可能標本器がu=fxbを正しく計算しており、第二乱数化可能標本器がv=fxaを正しく計算しているときx1及びx2が群Gの単位元egであるとき、ub’va’=fxbx1b’fxax2a’=fxbegb’fxaega’=fxbb’egb’fxaa’ega’=fxbb’aa’=fxとなる。また、q1,q2∈Iについて、i=1,2の各々について関数πiをπiq1,q2=qiで定義する。さらに、L=min♯π1S,♯π2Sとする。♯は、集合の位数である。群Gが巡回群や位数の計算が困難な群であるときには、復号処理部416-uが⊥以外を出力するときの出力がfxではない確率は、無視できる程度の誤差の範囲で高々Tmax2L/♯S程度と期待することができる。もしL/♯Sが無視できる量でTmaxが多項式オーダー程度の量であれば、復号処理部416-uは圧倒的な確率で正しいfxを出力する。L/♯Sが無視できる量になるようなSの例には、例えばS={1,d|d∈[2,|G|-1]}がある。<第四実施形態の特徴>本形態でも端末装置41-uに対する制御を行うことなく、登録許可情報記憶部421-kに格納された固有公開情報PTuを削除することで、削除した固有公開情報PTuに対応する端末装置41-uが暗号文Cの復号結果を閲覧する権限を無効化できる。また、端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。さらに本形態では、自己訂正技術を用いて復号を行うため、信頼できる鍵装置が設定されていない場合や、信頼できるか否かが定かではない複数の鍵装置しか存在しない場合であっても運用可能である。なお、上述した自己訂正処理は1つの端末装置と1つの鍵装置との間で実行していたが、1つの端末装置が複数の鍵装置と自己訂正処理を実行してもよい。[第五実施形態]第五実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した例である。以下、第四実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。以下の説明において、同一の参照番号が付された部分は同一の機能を持つものとし、同一の参照番号が付されたステップは同一の処理を表すものとする。<構成>図8に例示するように第五実施形態の復号システム5は、第四実施形態の端末装置41-uu=1,,Uが端末装置51-uu=1,,Uに置換され、鍵装置42-kk=1,,Kが鍵装置52-kk=1,,Kに置換されたものである。図10に例示するように、端末装置51-uは、第四実施形態の復号処理部416-uが復号処理部516-uに置換されたものである。鍵装置52-kは、第四実施形態の判定復号部4261-k及び暗号化部4262-kを含む復号部426-kが、判定復号部5261-k及び暗号化部4262-kを含む復号部526-kに置換されたものである。図11に例示するように、第五実施形態の復号処理部516-uは、例えば、自然数記憶部416a-uと自然数選択部416b-uと整数計算部416c-uと入力情報提供部516d-uと第一計算部516e-uと第一べき乗計算部416f-uと第一リスト記憶部416g-uと第二計算部516h-uと第二べき乗計算部416i-uと第二リスト記憶部416j-uと判定部416k-uと最終出力部416m-uと制御部416n-uとを有する。図13に例示するように、本形態の入力情報提供部516d-uは、例えば、第一乱数生成部516da-uと第一入力情報計算部516db-uと第二乱数生成部516dc-uと第二入力情報計算部516dd-uとを有する。図12に例示するように、第五実施形態の判定復号部5261-kは、例えば、第一出力情報計算部5261a-kと第二出力情報計算部5261b-kと判定部4261c-kと制御部4261n-kとを有する。<自己訂正処理ステップS504>本形態ではステップS404の代わりに以下の自己訂正処理ステップS504が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第五実施形態では、復号関数fxを準同型関数とし、群Hの生成元をμh、群Hの位数をKH、ν=fμhとする。その他の前提は、復号処理部416-uが復号処理部516-uに置換され、判定復号部4261-kが判定復号部5261-kに置換されている以外、第四実施形態と同一である。図16及び図17に例示するように、第五実施形態の処理は第四形態のステップS404d~S404g,S404i,S404j,S404nが、それぞれ、ステップS504d~S504g,S504i,S504j,S504nに置換されたものである。以下ではステップS504d~S504g,S504i,S504j,S504nの処理のみを説明する。《ステップS504dの処理》復号処理部516-u図11の入力情報提供部516d-uは、入力された暗号文xにそれぞれ対応する群Hの元である第一入力情報τ1及び第二入力情報τ2を生成して出力する図16/ステップS504d。以下、図18を用いて本形態のステップS504dの処理を説明する。第一乱数生成部516da-u図13は、0以上KH未満の自然数の一様乱数r1を生成する。生成された乱数r1は、第一入力情報計算部516db-u及び第一計算部516e-uに送られるステップS504da。第一入力情報計算部516db-uは、入力された乱数r1と暗号文xと自然数bとを用いて第一入力情報τ1=μhr1xbを計算するステップS504db。ここで、μhの右肩のr1は、r1のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。第二乱数生成部516dc-uは、0以上KH未満の自然数の一様乱数r2を生成する。生成された乱数r2は、第二入力情報計算部516dd-u及び第二計算部516h-uに送られるステップS504dc。第二入力情報計算部516dd-uは、入力された乱数r2と暗号文xと自然数aとを用いて第二入力情報τ2=μhr2xaを計算するステップS504dd。第一入力情報計算部516db-u及び第二入力情報計算部516dd-uは、以上のように生成した第一入力情報τ1及び第二入力情報τ2を出力する。第一入力情報τ1及び第二入力情報τ2は出力部114-u図10から出力され、鍵装置52-kの入力部423-kに入力され判定復号部5261-kに送られるステップS504de。なお、本形態の第一入力情報τ1及び第二入力情報τ2は、それぞれ、乱数r1,r2によって暗号文xとの関係をかく乱させた情報である。これにより、判定復号部5261-kは、暗号文xを判定復号部5261-kに対して隠蔽できる。また、本形態の第一入力情報τ1は自然数選択部416b-uで選択された自然数bにさらに対応し、第二入力情報τ2は自然数選択部416b-uで選択された自然数aにさらに対応する。これにより、判定復号部5261-kから提供された復号能力を復号処理部516-uが高い精度で評価することが可能となる。《ステップS504e~S504gの処理》図17に例示するように、まず、第一入力情報τ1=μhr1xbが判定復号部5261-k図12の第一出力情報計算部5261a-kに入力され、第二入力情報τ2=μhr2xaが第二出力情報計算部5261b-kに入力されるステップS504e。第一出力情報計算部5261a-kは、第一入力情報τ1=μhr1xbと秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfμhr1xbを正しく計算し、得られた計算結果を第一出力情報z1とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部5261a-kでの計算結果がfμhr1xbとなる場合もあれば、fμhr1xbとならない場合もあるステップS504f。第二出力情報計算部5261b-kは、第二入力情報τ2=μhr2xaと秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfμhr2xaを正しく計算し、得られた計算結果を第二出力情報z2とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部5261b-kでの計算結果がfμhr2xaとなる場合もあれば、fμhr2xaとならない場合もあるステップS504g。第一出力情報計算部5261a-kは第一出力情報z1を出力し、第二出力情報計算部5261b-kは第二出力情報z2を出力する。《ステップS504i及びS504jの処理》図16に戻り、第四実施形態と同様に復号部417-uで暗号文Czを復号して得られた第一出力情報z1は復号処理部516-u図11の第一計算部516e-uに入力され、第二出力情報z2は第二計算部516h-uに入力される。これらの第一出力情報z1及び第二出力情報z2が、判定復号部5261-kから復号処理部516-uに与えられた復号能力に相当するステップS504i。第一計算部516e-uは、入力された乱数r1及び第一出力情報z1を用いてz1ν-r1を計算してその計算結果をuとする。計算結果uは、第一べき乗計算部416f-uに送られる。ここで、u=z1ν-r1=fxbx1となる。すなわち、z1ν-r1は、fxについて誤差X1を持つ乱数化可能標本器となる。その理由については後述するステップ504j。《ステップS504nの処理》第二計算部516h-uは、入力された乱数r2及び第二出力情報z2を用いてz2ν-r2を計算してその計算結果をvとする。計算結果vは、第二べき乗計算部416i-uに送られる。ここで、v=z2ν-r2=fxax2となる。すなわち、z2ν-r2は、fxについて誤差X2を持つ乱数化可能標本器となる。その理由については後述するステップS504n。≪z1ν-r1,z2ν-r2がfxについてそれぞれ誤差X1,X2を持つ乱数化可能標本器となる理由について≫cを自然数、R及びR’を乱数として、判定復号部5261-kがμhRxcを用いて行う計算の計算結果をBμhRxcとする。すなわち、第一出力情報計算部5261a-kや第二出力情報計算部5261b-kが復号処理部516-uに返す計算結果をz=BμhRxcとする。さらに、群Gに値を持つ確率変数XをX=BμhR’fμhR’-1と定義する。このとき、zν-R=BμhRxcfμh-R=XfμhRxcfμh-R=XfμhRfxcfμh-R=fxcXとなる。すなわち、zν-Rは、fxについて誤差Xを持つ乱数化可能標本器となる。上記式展開において、X=BμhR’fμhR’-1=BμhRxcfμhRxc-1であり、BμhRxc=XfμhRxcであるという性質を用いている。この性質は、関数fxが準同型関数であり、R及びR’が乱数であることに基づく。したがって、a,bが自然数、r1,r2が乱数であることを考慮すると、同様に、z1ν-r1,z2ν-r2がfxについてそれぞれ誤差X1,X2を持つ乱数化可能標本器となるのである。[第六実施形態]第六実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した他の例である。具体的には、H=G×G、復号関数fxがElGamal暗号の復号関数、すなわち秘密鍵sk及び暗号文x=c1,c2に対してfc1,c2=c1c2-sである場合の第一乱数化可能標本器及び第二乱数化可能標本器の例を具体化したものである。以下、第四実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。<構成>図8に例示するように第六実施形態の復号システム6は、第四実施形態の端末装置41-uu=1,,Uが端末装置61-uu=1,,Uに置換され、鍵装置42-kk=1,,Kが鍵装置62-kk=1,,Kに置換されたものである。図10に例示するように、端末装置61-uは、第四実施形態の復号処理部416-uが復号処理部616-uに置換されたものである。鍵装置62-kは、第四実施形態の判定復号部4261-k及び暗号化部4262-kを含む復号部426-kが、判定復号部6261-k及び暗号化部4262-kを含む復号部626-kに置換されたものである。図11に例示するように、第六実施形態の復号処理部616-uは、例えば、自然数記憶部416a-uと自然数選択部416b-uと整数計算部416c-uと入力情報提供部616d-uと第一計算部616e-uと第一べき乗計算部416f-uと第一リスト記憶部416g-uと第二計算部616h-uと第二べき乗計算部416i-uと第二リスト記憶部416j-uと判定部416k-uと最終出力部416m-uと制御部416n-uとを有する。図14に例示するように、本形態の入力情報提供部616d-uは、例えば、第四乱数生成部616da-uと第五乱数生成部616db-uと第一入力情報計算部616dc-uと第六乱数生成部616dd-uと第七乱数生成部616de-uと第二入力情報計算部616df-uとを有する。第一入力情報計算部616dc-uは、例えば、第四入力情報計算部616dca-uと第五入力情報計算部616dcb-uとを有し、第二入力情報計算部616df-uは、第六入力情報計算部616dfa-uと第七入力情報計算部616dfb-uとを有する。図12に例示するように、第六実施形態の判定復号部6261-kは、例えば、第一出力情報計算部6261a-kと第二出力情報計算部6261b-kと制御部4261n-kと判定部4261c-kとを有する。<自己訂正処理ステップS604>本形態ではステップS404の代わりに以下の自己訂正処理ステップS604が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第六実施形態では、群H=G×G、暗号文x=C=c1,c2∈Hであり、fc1,c2が準同型関数であり、群Gの生成元をμgとし、群Gの位数をKGとし、同じ秘密鍵skに対する暗号文V,W∈Hとその暗号文を復号した復号文fV,W=Y∈Gとの組が復号処理部616-u及び判定復号部6261-kに事前設定され、復号処理部616-u及び判定復号部6261-kがこの組を利用可能とされているものとする。図16及び図17に例示するように、第六実施形態の処理は第四形態のステップS404d~S404g,S404i,S404j,S404nが、それぞれ、ステップS604d~S604g,S604i,S604j,S604nに置換されたものである。以下ではステップS604d~S604g,S604i,S604j,S604nの処理のみを説明する。《ステップS604dの処理》復号処理部616-u図11の入力情報提供部616d-uは、入力された暗号文x=c1,c2に対応する群Hの元である第一入力情報τ1及び暗号文x=c1,c2に対応する群Hの元である第二入力情報τ2を生成して出力する図16/ステップS604d。以下、図19を用いて本形態のステップS604dの処理を説明する。第四乱数生成部616da-u図14は、0以上KG未満の自然数の一様乱数r4を生成する。生成された乱数r4は、第四入力情報計算部616dca-u、第五入力情報計算部616dcb-u、及び第一計算部616e-uに送られるステップS604da。第五乱数生成部616db-uは、0以上KG未満の自然数の一様乱数r5を生成する。生成された乱数r5は、第五入力情報計算部616dcb-u、及び第一計算部616e-uに送られるステップS604db。第四入力情報計算部616dca-uは、自然数選択部416b-uで選択された自然数b、暗号文xが含むc2、及び乱数r4を用い、第四入力情報c2bWr4を計算するステップS604dc。第五入力情報計算部616dcb-uは、自然数選択部416b-uで選択された自然数b、暗号文xが含むc1、及び乱数r4,r5を用い、第五入力情報c1bVr4μgr5を計算するステップS604dd。第六乱数生成部616dd-uは、0以上KG未満の自然数の一様乱数r6を生成する。生成された乱数r6は、第六入力情報計算部616dfa-u、第七入力情報計算部616dfb-u、及び第二計算部616h-uに送られるステップS604de。第七乱数生成部616de-uは、0以上KG未満の自然数の一様乱数r7を生成する。生成された乱数r7は、第六入力情報計算部616dfa-u、及び第二計算部616h-uに送られるステップS604df。第六入力情報計算部616dfa-uは、自然数選択部416b-uで選択された自然数a、暗号文xが含むc2、及び乱数r6を用い、第六入力情報c2aWr6を計算するステップS604dg。第七入力情報計算部616dfb-uは、自然数選択部416b-uで選択された自然数a、暗号文xが含むc1、及び乱数r7を用い、第七入力情報c1aVr6μgr7を計算するステップS604dh。第一入力情報計算部616dc-uは、以上のように生成した第四入力情報c2bWr4及び第五入力情報c1bVr4μgr5を第一入力情報τ1=c2bWr4,c1bVr4μgr5として出力する。第二入力情報計算部616df-uは、以上のように生成した第六入力情報c2aWr6及び第七入力情報c1aVr6μgr7を第二入力情報τ2=c2aWr6,c1aVr6μgr7として出力するステップS604di。第一入力情報τ1及び第二入力情報τ2は出力部114-u図10から出力され、鍵装置62-kの入力部423-kに入力され判定復号部6261-kに送られる。《ステップS604e~S604gの処理》図17に例示するように、まず、第一入力情報τ1=c2bWr4,c1bVr4μgr5が判定復号部6261-k図12の第一出力情報計算部6261a-kに入力され、第二入力情報τ2=c2aWr6,c1aVr6μgr7が第二出力情報計算部6261b-kに入力されるステップS604e。第一出力情報計算部6261a-kは、第一入力情報τ1=c2bWr4,c1bVr4μgr5と秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfc1bVr4μgr5,c2bWr4を正しく計算し、計算結果を第一出力情報z1とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部6261a-kでの計算結果がfc1bVr4μgr5,c2bWr4となる場合もあれば、fc1bVr4μgr5,c2bWr4とならない場合もあるステップS604f。第二出力情報計算部6261b-kは、第二入力情報τ2=c2aWr6,c1aVr6μgr7と秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfc1aVr6μgr7,c2aWr6を正しく計算可能であり、得られた計算結果を第二出力情報z2とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部6261b-kでの計算結果がfc1aVr6μgr7,c2aWr6となる場合もあれば、fc1aVr6μgr7,c2aWr6とならない場合もあるステップS604g。第一出力情報計算部6261a-kは第一出力情報z1を出力し、第二出力情報計算部6261b-kは第二出力情報z2を出力する。《ステップS604i及びS604jの処理》図16に戻り、第四実施形態と同様に復号部417-uで暗号文Czを復号して得られた第一出力情報z1は復号処理部616-u図11の第一計算部616e-uに入力され、第二出力情報z2は第二計算部616h-uに入力されるステップS604i。第一計算部616e-uは、入力された第一出力情報z1及び乱数r4,r5を用い、z1Y-r4μg-r5を計算してその計算結果をuとするステップS604j。計算結果uは、第一べき乗計算部416f-uに送られる。ここで、u=z4Y-r4μg-r5=fc1,c2bx1となる。すなわち、z4Y-r4μg-r5は、fc1,c2について誤差X1を持つ乱数化可能標本器となる。その理由については後述する。《ステップS604nの処理》第二計算部616h-uは、入力された第二出力情報z2及び乱数r6,r7を用い、z2Y-r6μg-r7を計算してその計算結果をvとするステップS604n。計算結果vは、第二べき乗計算部416i-uに送られる。ここで、v=z5Y-r6μg-r7=fc1,c2ax2となる。すなわち、z5Y-r6μg-r7は、fc1,c2について誤差X2を持つ乱数化可能標本器となる。その理由については後述する。≪z4Y-r4μg-r5,z5Y-r6μg-r7がfc1,c2についてそれぞれ誤差X1,X2を持つ乱数化可能標本器となる理由について≫cを自然数、R1、R2、R1’及びR2’を乱数として、判定復号部6261-kがc1cVR1μgR2及びc2cWR1を用いて行う計算の計算結果をBc1cVR1μgR2,c2cWR1とする。すなわち、第一出力情報計算部6261a-kや第二出力情報計算部6261b-kが復号処理部616-uに返す計算結果をz=Bc1cVR1μgR2,c2cWR1とする。さらに、群Gに値を持つ確率変数XをX=BVR1’μgR2’,WR1’fVR1’μgR2’,WR1’-1と定義する。このとき、zY-R1μg-R2=Bc1cVR1μgR2,c2cWR1Y-R1μg-R2=Xfc1cVR1μgR2,c2cWR1Y-R1μg-R2=Xfc1,c2cfV,WR1fμg,egR2Y-R1μg-R2=Xfc1,c2cYR1μgR2Y-R1μg-R2=fc1,c2cXとなる。すなわち、zY-R1μg-R2は、fxについて誤差Xを持つ乱数化可能標本器となる。なお、egは、群Gの単位元である。上記式展開において、X=BVR1’μgR2’,WR1’fVR1’μgR2’,WR1’-1=Bc1cVR1μgR2,c2cWR1fc1cVR1μgR2,c2cWR1であり、Bc1cVR1μgR2,c2cWR1=Xfc1cVR1μgR2,c2cWR1であるという性質を用いている。この性質は、R1、R2、R1’及びR2’が乱数であることに基づく。したがって、a,bが自然数、r4,r5,r6及びr7が乱数であることを考慮すると、同様に、z4Y-r4μg-r5,z5Y-r6μg-r7がfc1,c2についてそれぞれ誤差X1,X2を持つ乱数化可能標本器となるのである。[第七実施形態]第四~六実施形態では、復号処理部の自然数記憶部416a-uに、互いに素である2つの自然数a,bの組a,bが複数種類記憶され、これらの組a,bを用いて各処理が実行されることとした。しかしながら、a,bの一方が定数であってもよい。例えば、aが1に固定されていてもよいし、bが1に固定されていてもよい。言い換えると、第一乱数化可能標本器又は第二乱数化可能標本器の一方が標本器に置換されていてもよい。a,bの一方が定数である場合、定数とされたa又はbを選択する処理が不要となり、各処理部は定数とされたa又はbが入力されることなく、それを定数として扱って計算を行うことができる。また、定数とされたa又はbが1である場合には、a’やb’を用いることなく、fx=ub’va’をfx=v又はfx=uとして得ることができる。第七実施形態は、そのような変形の一例であり、bが1に固定され、第二乱数化可能標本器が標本器に置換された形態である。以下では、第四実施形態との相違点を中心に説明する。また、第一乱数化可能標本器の具体例は、第五実施形態および第六実施形態で説明したのと同様であるため、説明を省略する。<構成>図8に例示するように第七実施形態の復号システム7は、第四実施形態の端末装置41-uu=1,,Uが端末装置71-uu=1,,Uに置換され、鍵装置42-kk=1,,Kが鍵装置72-kk=1,,Kに置換されたものである。図10に例示するように、端末装置71-uは、第四実施形態の復号処理部416-uが復号処理部716-uに置換されたものである。鍵装置72-kは、第四実施形態の判定復号部4261-k及び暗号化部4262-kを含む復号部426-kが、判定復号部7261-k及び暗号化部4262-kを含む復号部726-kに置換されたものである。図20に例示するように、第七実施形態の復号処理部716-uは、例えば、自然数記憶部716a-uと自然数選択部716b-uと入力情報提供部716d-uと第一計算部716e-uと第一べき乗計算部716f-uと第一リスト記憶部716g-uと第二計算部716h-uと第二リスト記憶部716j-uと判定部716m-uと最終出力部416m-uと制御部416n-uとを有する。図12に例示するように、第七実施形態の判定復号部7261-kは、例えば、第一出力情報計算部7261a-kと第二出力情報計算部7261b-kと制御部4261n-kと判定部4261c-kとを有する。<自己訂正処理ステップS704>本形態ではステップS404の代わりに以下の自己訂正処理ステップS704が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第七実施形態では、G,Hを巡回群、fxを群Hの元である暗号文x=Cを特定の秘密鍵skで復号して群Gの元を得るための復号関数、群G,Hの生成元をそれぞれμg,μh、X1,X2を群Gに値を持つ確率変数、確率変数X1の実現値をx1、確率変数X2の実現値をx2とする。また、復号処理部716-uの自然数記憶部716a-uには、自然数aが複数種類記憶されているものとする。図21に例示するように、復号処理部716-u図20の自然数選択部716b-uが、自然数記憶部716a-uに記憶された複数の自然数aから1つの自然数aをランダムに読み込む。読み込まれた自然数aの情報は、入力情報提供部716d-u及び第一べき乗計算部716f-uに送られるステップS704a。制御部416n-uは、t=1とするステップS704b。入力情報提供部716d-uは、入力された暗号文xにそれぞれ対応する群Hの元である第一入力情報τ1及び第二入力情報τ2を生成して出力する。好ましくは、第一入力情報τ1及び第二入力情報τ2はそれぞれ暗号文xとの関係をかく乱させた情報である。これにより、復号処理部716-uは、暗号文xを判定復号部7261-kに対して隠蔽できる。また、好ましくは、本形態の第二入力情報τ2は自然数選択部716b-uで選択された自然数aにさらに対応する。これにより、判定復号部7261-kから提供された復号能力を復号処理部716-uが高い精度で評価することが可能となるステップS704d。第一入力情報τ1及び第二入力情報τ2の組みの具体例は、第五実施形態および第六実施形態の何れかのb=1とした第一入力情報τ1及び第二入力情報τ2の組みである。第一入力情報τ1及び第二入力情報τ2は出力部114-u図10から出力され、鍵装置72-kの入力部423-kに入力され判定復号部7261-kに送られる。図17に例示するように、第一入力情報τ1は判定復号部7261-k図12の第一出力情報計算部7261a-kに入力され、第二入力情報τ2は第二出力情報計算部7261b-kに入力されるステップS704e。第一出力情報計算部7261a-kは、第一入力情報τ1と秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfτ1を正しく計算し、得られた計算結果を第一出力情報z1とするステップS704f。第二出力情報計算部7261b-kは、第二入力情報τ2と秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfτ2を正しく計算し、得られた計算結果を第二出力情報z2とするステップS704g。すなわち、第一出力情報計算部7261a-kや第二出力情報計算部7261b-kは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部7261a-kでの計算結果がfτ1の場合もあればfτ1でない場合もあり、第二出力情報計算部7261b-kでの計算結果がfτ2の場合もあればfτ2でない場合もある。第一出力情報z1及び第二出力情報z2の組の具体例は、第五実施形態および第六実施形態の何れかのb=1とした第一出力情報z1及び第二出力情報z2の組である。第一出力情報計算部7261a-kは第一出力情報z1を出力し、第二出力情報計算部7261b-kは第二出力情報z2を出力する。第一出力情報z1および第二出力情報z2は第四実施形態と同様に暗号化部4262-kで暗号化され、出力部424-kは、第一入力情報τ1及び第二入力情報τ2を送信した端末装置41-uに対して暗号文Czを出力するステップS404h。図21に戻り、第四実施形態と同様に復号部417-uで暗号文Czを復号して得られた第一出力情報z1は復号処理部716-u図20の第一計算部716e-uに入力され、第二出力情報z2は第二計算部716h-uに入力される。これらの第一出力情報z1及び第二出力情報z2が、判定復号部7261-kから復号処理部716-uに与えられた復号能力に相当するステップS704i。第一計算部716e-uは、第一出力情報z1から計算結果u=fxx1を生成する。計算結果uの具体例は、第五実施形態および第六実施形態の何れかのb=1とした計算結果uである。計算結果uは第一べき乗計算部716f-uに送られるステップS704j。第一べき乗計算部716f-uはu’=uaを計算する。計算結果uとその計算結果に基づいて計算されたu’との組u,u’は、第一リスト記憶部416g-uに記憶されるステップS704k。第二計算部716h-uは、第二出力情報z2から計算結果v=fxax2を生成する。計算結果vの具体例は、第五実施形態および第六実施形態の何れかの計算結果vである。計算結果vは第二リスト記憶部716j-uに記憶されるステップS704n。判定部716m-uは、第一リスト記憶部416g-uに記憶された組u,u’及び第二リスト記憶部716j-uに記憶されたvの中で、u’=vとなるものがあるか判定するステップS704q。u’=vとなるものがあった場合には、ステップ704u進む。u’=vとなるものがなかった場合には、ステップS404rに進む。ステップS404rでは、制御部416n-uがt=Tmaxであるか判定するステップS404r。Tmaxは予め定められた自然数である。t=Tmaxであれば、制御部416n-uは、計算をすることができなかった旨の情報、例えば記号⊥を出力してステップS404t、処理を終える。t=Tmaxでない場合には、制御部416n-uは、tを1だけインクリメント、すなわちt=t1としてステップS404s、ステップS704dに戻る。ステップS704uでは、最終出力部416m-uが、u’=vであると判定されたu’に対応するuを復号結果m’として出力するステップS704u。このように得られたuは、第四実施形態から第六実施形態でb=1とした場合のub’va’に相当する。すなわち、このように得られたuは高い確率で暗号文xを特定の秘密鍵skで復号した復号結果fx=m’となる。よって、上述した処理を複数回繰り返し、ステップS704uで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、後述するように、設定によっては圧倒的な確率でu=fx=m’となる。その場合にはステップS704uで得られた値をそのまま復号結果としてよい。≪復号結果fxが得られる理由について≫次に、本形態の復号処理部716-uで復号結果fxが得られる理由を説明する。まず、説明に必要な事項を定義する。ブラックボックスblack-box:fτのブラックボックスFτとは、τ∈Hを入力としてz∈Gを出力する処理部を意味する。本形態では、第一出力情報計算部7261a-k及び第二出力情報計算部7261b-kが、それぞれ復号関数fτのブラックボックスFτに相当する。群Hから任意に選択された元τ∈UH及びz=Fτに対してz=fτを満たす確率がδ0<δ≦1よりも大きい場合、すなわち、Pr[z=fτ|τ∈UH,z=Fτ]>δ...1を満たすfτのブラックボックスFτのことを、信頼性δδ-reliableのfτのブラックボックスFτという。なお、δは正の値であり、前述した或る確率に相当する。自己訂正器self-corrector:自己訂正器CFxとは、x∈Hを入力とし、fτのブラックボックスFτを用いて計算を行い、j∈G∪⊥を出力する処理部を意味する。本形態では、復号処理部716-uが自己訂正器CFxに相当する。オールモスト自己訂正器almostself-corrector:自己訂正器CFxが、x∈Hを入力とし、δ-reliableのfτのブラックボックスFτを用い、正しい値j=fxを出力する確率が、誤った値j≠fxを出力する確率よりも十分大きい場合を想定する。すなわち、Pr[j=fx|j=CFx,j≠⊥]>Pr[j≠fx|j=CFx,j≠⊥]Δ...2を満たす場合を想定する。なお、Δは或る正の値0<Δ<1である。このような場合、自己訂正器CFxはオールモスト自己訂正器であるという。例えば、或る正の値Δ’0<Δ’<1に対してPr[j=fx|j=CFx]>1/3Δ’Pr[j=⊥|j=CFx]<1/3Pr[j≠fxかつj≠⊥|j=CFx]<1/3を満たす場合、自己訂正器CFxはオールモスト自己訂正器である。Δ’の例はΔ’=1/12や1/3である。ローバスト自己訂正器robustself-corrector:自己訂正器CFxが、x∈Hを入力とし、δ-reliableのfτのブラックボックスFτを用い、正しい値j=fx又はj=⊥を出力する確率が圧倒的である場合を想定する。すなわち、無視することができる誤差ξ0≦ξ<1に対してPr[j=fxまたはj=⊥|j=CFx]>1-ξ...3を満たす場合を想定する。このような場合、自己訂正器CFxはローバスト自己訂正器であるという。なお、無視することができる誤差ξの例は、セキュリティパラメータkの関数値ξkである。関数値ξkの例は、任意の多項式pkについて、十分大きいkに対して{ξkpk}が0に収束するものである。関数値ξkの具体例は、ξk=2-kやξk=2-√kなどである。また、オールモスト自己訂正器からローバスト自己訂正器を構成することができる。すなわち、同一のxに対してオールモスト自己訂正器を複数回実行させ、⊥を除いて最も頻度が高い出力値をjとすることで、ローバスト自己訂正器を構成できる。例えば、同一のxに対してオールモスト自己訂正器をOlog1/ξ回実行させ、最も頻度が高い出力値をjとすることで、ローバスト自己訂正器を構成できる。なお、Oはオー記法を表す。擬似自由pseudo-freeな作用:群G、自然数の集合Ω={0,...,M}Mは1以上の自然数、群Gに値を持つ確率変数X1,X2の各実現値α∈X1α≠eg,β∈X2、及びa∈Ωについて、αa=βとなる確率Pr[αa=βかつα≠eg|a∈UΩ,α∈X1,β∈X2]...4について、あらゆる可能なX1,X2に関する上限値を、組G,Ωの疑似自由指標とよび、これをPG,Ωと表すことにする。ある無視することができる関数ζkが存在して、PG,Ω<ζk...5である場合、組G,Ωによって定義される演算は擬似自由な作用であるという。なお、第5実施形態では群で定義された演算を乗法的に表現する。すなわちα∈Gに対するαaは、群Gで定義された演算をαに対してa回作用させることを意味する。また、無視することができる関数ζkの例は、任意の多項式pkについて、十分大きいkに対して{ζkpk}が0に収束するものである。関数ζkの具体例は、ζk=2-kやζk=2-√kなどである。例えば、セキュリティパラメータkとに対し、式4の確率がO2-k未満である場合、組G,Ωによって定義される演算は擬似自由な作用である。また、例えば、任意のα∈Gでα≠egであるものについて、集合Ωα={aα|a∈Ω}の要素数|Ωα|が2kを超える場合、組G,Ωによって定義される演算は擬似自由な作用といえる。このような具体例は数多く存在する。例えば、群Gが素数pを法とする剰余群Z/pZであり、素数pが2kのオーダーであり、集合Ω={0,...,p-2}であり、aαがαa∈Z/pZであり、α≠egである場合、Ωα={αa|a=0,...,p-2}={eg,α1,...,αp-2}となり、|Ωα|=p-1である。素数pが2kのオーダーであるため、ある定数Cが存在して、kが十分大きければ|Ωα|>C2kを満たす。ここで式4の確率はC-12-k未満であり、このような組G,Ωによって定義される演算は擬似自由な作用である。信頼性δγδγ-reliableの乱数化可能標本器:自然数aが与えられるたびに、δ-reliableのfτのブラックボックスFτを用い、w∈Gについて、確率変数Xに従った標本x’に対応するwax’を返す乱数化可能標本器であって、wax’=waである確率がδγよりも大きいγは正定数、すなわち、Pr[wax’=wa]>δγ...6を満たすものを、信頼性δγの乱数化可能標本器という。本形態の入力情報提供部716d-uと第二出力情報計算部7261b-kと第二計算部716h-uとの組は、w=fxについて、信頼性δγの乱数化可能標本器である。次に、これらの定義を用い、本形態の復号処理部716-uで復号結果fxが得られる理由を説明する。本形態のステップS704qではu’=vであるか、すなわち、ua=vであるかを判定している。本形態の入力情報提供部716d-uと第二出力情報計算部7261b-kと第二計算部716h-uとの組は信頼性δγの乱数化可能標本器であるため式6、Tmaxをk、δ、γから定まる一定値よりも大きい値とすれば、漸近的に大きい確率でua=vが成立するステップS704qでyesとなる場合が生じる。たとえば、Tmax≧4/δγとすれば、ua=vが成立するステップS704qでyesとなる確率は1/2よりも大きいことがMarkovの不等式によってわかる。また、本形態ではu=fxx1及びv=fxax2なのであるから、ua=vが成立する場合にはx1a=x2が成立する。x1a=x2が成立する場合には、x1=x2=egである場合とx1≠egである場合とがある。x1=x2=egである場合には、u=fxとなるのであるから、ステップS704uで出力されるuは正しい復号結果fxとなる。一方、x1≠egである場合には、u≠fxとなるのであるから、ステップS704uで出力されるuは正しい復号結果fxではない。群Gと自然数aが属する集合Ωとの組G,Ωによって定義される演算が擬似自由な作用であるか、疑似自由指標PG,ΩについてTmax2PG,Ωが漸近的に小さい場合、ua=vの場合にx1≠egである確率式4は漸近的に小さい。したがって、ua=vの場合にx1=egである確率は漸近的に大きい。よって、組G,Ωによって定義される演算が擬似自由な作用であるか、Tmax2PG,Ωが漸近的に小さい場合、ua=vの場合に誤った復号結果fxが出力される確率は、ua=vの場合に正しい復号結果fxが出力される確率よりも十分小さい。この場合の復号処理部716-uはオールモスト自己訂正器であるといえる式2参照。そのため、前述のように、復号処理部716-uからローバスト自己訂正器を構成することが可能であり、圧倒的な確率で正しい復号結果fxを得ることができる。G,Ωで定義される演算が疑似自由な作用である場合には、ua=vの場合に誤った復号結果fxが出力される確率も無視できる。この場合の復号処理部716-uは、圧倒的な確率で正しい復号結果fxまたは⊥を出力する。なお、任意の定数ρに対してk0が定まり、このk0に対してk0<k’を満たす任意のk’に対する関数値ηk’がρ未満となる場合ηk’が漸近的に小さいという。k’の例はセキュリティパラメータkである。また、任意の定数ρに対してk0が定まり、このk0に対してk0<k’を満たす任意のk’に対する関数値1-ηk’がρ未満となる場合ηk’が漸近的に大きいという。《信頼性δγの乱数化可能標本器と安全性について》以下のような攻撃を想定する。ブラックボックスFτ又はその部分が意図的に不正なzを出力する、又は、ブラックボックスFτから出力された値が不正なzに改ざんされる。不正なzに対応するwax’が乱数化可能標本器から出力される。不正なzに対応するwax’は、自己訂正器CFxでua=vが成立するステップS704qでyesなるにもかかわらず、自己訂正器CFxが誤った値を出力する確率を増加させる。このような攻撃は、与えられた自然数aに対して乱数化可能標本器から出力されたwax’の誤差の確率分布Da=wax’w-aが自然数aに依存する場合に可能となる。例えば、第二計算部716h-uから出力されるvがfxax1aとなるような不正が行われた場合、x1の値にかかわらず、必ずua=vが成立することになる。よって、乱数化可能標本器は、与えられた自然数aに対して乱数化可能標本器から出力されたwax’の誤差の確率分布Da=wax’w-aが当該自然数aに依存しないことが望ましい。あるいは、集合Ωのいかなる元a∈∀Ωについても、wax’の誤差の確率分布Da=wax’w-aと区別することができない群Gに値を持つ確率分布Dが存在する確率分布Daと確率分布Dとが統計的に近似するstatistically-close乱数化可能標本器であることが望ましい。なお、確率分布Dは自然数aに依存しない。また、確率分布Daと確率分布Dとを区別することができないとは、多項式時間アルゴリズムによって確率分布Daと確率分布Dとを区別することができないことを意味し、例えば、無視することができるζ0≦ζ<1に対してΣg∈G|Pr[g∈D]-Pr[g∈Da]|<ζ...7を満たすならば、多項式時間アルゴリズムによって確率分布Daと確率分布Dとを区別することができない。無視することができるζの例は、セキュリティパラメータkの関数値ζkである。関数値ζkの例は、任意の多項式pkについて、十分大きなkに対して{ζkpk}が0に収束するものである。関数値ζkの具体例は、ζk=2-kやζk=2-√kなどである。また、これらの点は自然数a及びbを使用する第四実施形態から第六実施形態についても同様である。[第八実施形態]第八実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した他の例である。本形態は、格子暗号の一種であるGHV暗号化方式参考文献1CGenrtySHaleviandVVaikuntanathanASimpleBGNTypeCryptosystemfromLWEAdvancesinCryptologyEUROCRYPT2010LNCS6110pp506522SpringerVerlag2010等参照の復号処理に本発明を適用する形態である。以下では、第四実施形態との相違点を中心に説明する。<構成>図8に例示するように第八実施形態の復号システム8は、第四実施形態の端末装置41-uu=1,,Uが端末装置81-uu=1,,Uに置換され、鍵装置42-kk=1,,Kが鍵装置82-kk=1,,Kに置換されたものである。図10に例示するように、端末装置81-uは、第四実施形態の復号処理部416-uが復号処理部816-uに置換されたものである。鍵装置82-kは、第四実施形態の判定復号部4261-k及び暗号化部4262-kを含む復号部426-kが、判定復号部8261-k及び暗号化部4262-kを含む復号部826-kに置換されたものである。図22に例示するように、第八実施形態の復号処理部816-uは、例えば、行列記憶部816a-uと行列選択部816b-uと入力情報提供部816d-uと第一計算部816e-uと行列積計算部816f-uと第一リスト記憶部816g-uと第二計算部816h-uと第二リスト記憶部816j-uと判定部816k-uと最終出力部816m-uと制御部416n-uとを有する。図24に例示するように、本形態の入力情報提供部816d-uは、例えば、第一ランダム行列選択部816da-uと第二ランダム行列選択部816db-uと第一暗号化部816dc-uと第二暗号化部816dd-uと第一入力情報計算部816de-uと第三ランダム行列選択部816df-uと第四ランダム行列選択部816dg-uと第三暗号化部816dh-uと第四暗号化部816di-uと第二入力情報計算部816dj-uとを有する。図23に例示するように、第八実施形態の判定復号部8261-kは、例えば、第一出力情報計算部8261a-kと第二出力情報計算部8261b-kと制御部4261n-kと判定部4261c-kを有する。<自己訂正処理ステップS804>本形態ではステップS404の代わりに以下の自己訂正処理ステップS804が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。本形態では、GMをι×ι行列の集合、HMをι×ι行列の集合、暗号文xM=CをHMの元、暗号文xM=Cの復号結果がGMの元、MX1,MX2を集合GMに値を持つ確率変数、Mx1を確率変数MX1の実現値、Mx2を確率変数MX2の実現値、aMを集合HMの元とする。また本形態では、ykを暗号化鍵公開鍵であるι×κ行列、skをyksk=0を満たすι×ι行列である復号鍵秘密鍵、CMをκ×ι行列、NMをι×ι行列、UMをι×ι単位行列、PTを集合GMの元である平文PT∈GM、xMを集合HMの元である暗号文xM∈HM、ENCMを集合GMの元である平文PTを暗号化して暗号文xM∈HMを得るための暗号化関数、fMxMを暗号文xM∈HMを特定の秘密鍵skで復号して集合GMの元である平文PTを得るための復号関数とする。復号関数fMxMは準同型関数である。例えば、GMをι×ι行列Z/2Zι×ιの集合、HMをι×ι行列Z/qZι×ιの集合、暗号化鍵ykをι×κ行列Z/qZι×κ、秘密鍵skをι×ι行列Z/qZι×ι、CMをランダムに選択されたκ×ι行列Z/qZκ×ι、NMをガウス分布に従うι×ι行列Z/qZι×ι、UMをι×ι単位行列Z/2Zι×ιとし、暗号化関数ENCMPTをykCM2NMPTmodqとし、復号関数fMxMをsk-1{skxMskTmodq}skT-1mod2とする。ただし、κ,ι,qは正整数、κ,ι,qは正整数、Tはの転置行列、Z/qZκ×ιはqを法とする剰余環Z/qZを要素とするκ行ι列行列である。また、第八実施形態では行列α1,α2間の積をα1α2と表し、和をα1α2と表現する。また、行列αの各要素を自然数β倍した行列をβαと表す。本形態の処理の前提として、復号処理部816-u図22の行列記憶部816a-uには、行列aM∈HMが複数種類記憶されているものとする。図25に例示するように、まず、復号処理部816-u図22の行列選択部816b-uが、行列記憶部816a-uに記憶された複数の行列から一様ランダムに1つの行列aMを選択して読み込む。読み込まれた行列aMの情報は、入力情報提供部816d-u及び行列積計算部816f-uに送られるステップS804a。制御部416n-uは、t=1とするステップS804c。入力情報提供部816d-uは、入力された暗号文xMにそれぞれ対応する対応する集合HMの元である第一入力情報Mτ1及び第二入力情報Mτ2を生成して出力する。好ましくは、第一入力情報Mτ1及び第二入力情報Mτ2はそれぞれ暗号文xMとの関係をかく乱させた情報である。これにより、復号処理部816-uは暗号文xMを判定復号部8261-kに対して隠蔽できる。また、第二入力情報Mτ2は元aMにさらに対応する。これにより、判定復号部8261-kから提供された復号能力を復号処理部816-uが高い精度で評価することが可能となるステップS804d。以下、図27を用いてステップS804dの具体例を説明する。[ステップS804dの具体例]入力情報提供部816d-u図24の第一ランダム行列選択部816da-uが集合GMの元MR1を一様ランダムに選択するステップS804da。選択されたMR1は第一暗号化部816dc-uと第一計算部816e-uに送られるステップS804da。第二ランダム行列選択部816db-uがκ×ιの一様ランダムな行列CM11及びCM12∈Z/qZκ×ιを選択する。選択されたCM11及びCM12は第一入力情報計算部816de-uに送られるステップS804db。第一暗号化部816dc-uが公開鍵ykを用い、MR1の暗号文ENCMyk,MR1である第一暗号文CR1=ykCM2NMMR1modqを生成する。第一暗号文CR1は第一入力情報計算部816de-uに送られるステップS804dc。第二暗号化部816dd-uが公開鍵ykを用い、単位行列UMの暗号文ENCMyk,UMである第二暗号文CUM=ykCM2NMUMmodqを生成する。第二暗号文CUMは第一入力情報計算部816de-uに送られるステップS804dd。第一入力情報計算部816de-uにはさらに暗号文xM=Cが入力される。第一入力情報計算部816de-uは、第一入力情報Mτ1としてxMCUMCR1ykCM112NMCM12TykTを得て出力する。なお、行列の積の順序に特段の必然性はない。すなわち第一入力情報計算部816de-uは、CX=xMCUMCR1としたReCX=CXykCM112NMCM12TykTを計算して第一入力情報Mτ1を生成してもよいし、CX=CUMxMCR1としたReCXを計算して第一入力情報Mτ1を生成してもよいステップS804de。第三ランダム行列選択部816df-uが集合GMの元MR2を一様ランダムに選択する。選択されたMR2は第三暗号化部816dh-uと第二計算部816h-uに送られるステップS804df。第四ランダム行列選択部816dg-uが、κ×ιのランダムな行列CM21及びCM22∈Z/qZκ×ιを選択する。選択されたCM21及びCM22は第二入力情報計算部816dj-uに送られるステップS804dg。第三暗号化部816dh-uが公開鍵ykを用い、MR2の暗号文ENCMyk,MR2である第三暗号文CR2=ykCM2NMMR2modqを生成する。第三暗号文CR2は第二入力情報計算部816dj-uに送られるステップS804dh。第四暗号化部6104iに行列aMが入力される。第四暗号化部6104iは公開鍵ykを用い、行列aMの暗号文ENCMyk,aMである第四暗号文Ca=ykCM2NMaMmodqを生成する。第四暗号文Caは第二入力情報計算部816dj-uに送られるステップS804di。第二入力情報計算部816dj-uにはさらに暗号文xM=Cが入力される。第二入力情報計算部816dj-uは、第二入力情報Mτ2としてxMCaCR2ykCM212NMCM22TykTを得て出力する。第二入力情報計算部816dj-uは、CX=xMCaCR2としたReCXを計算して第二入力情報Mτ2を生成してもよいし、CX=xMCaCR2としたReCXを計算して第二入力情報Mτ2を生成してもよいステップS804dj/[ステップS804dの具体例]の説明終わり。第一入力情報Mτ1及び第二入力情報Mτ2は出力部114-u図10から出力され、鍵装置82-kの入力部423-kに入力され判定復号部8261-kに送られる。図26に例示するように、第一入力情報Mτ1は判定復号部8261-k図23の第一出力情報計算部8261a-kに入力され、第二入力情報Mτ2は第二出力情報計算部8261b-kに入力されるステップS804e。第一出力情報計算部8261a-kは、第一入力情報Mτ1と秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfMMτ1=sk-1{skMτ1skTmodq}skT-1mod2を正しく計算し、得られた計算結果を第一出力情報Mz1とするステップS804f。第二出力情報生成部6202は、第二入力情報Mτ2と秘密鍵記憶部422-kに格納された秘密鍵skとを用い、或る確率より大きな確率でfMMτ2=sk-1{skMτ2skTmodq}skT-1mod2を正しく計算し、得られた計算結果を第二出力情報Mz2とするステップS804g。すなわち、第一出力情報計算部8261a-kや第二出力情報計算部8261b-kは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部8261a-kでの計算結果がfMMτ1の場合もあればfMMτ1でない場合もあり、第二出力情報計算部8261b-kでの計算結果がfMMτ2の場合もあればfMMτ2でない場合もある。第一出力情報計算部8261a-kは第一出力情報Mz1を出力し、第二出力情報計算部8261b-kは第二出力情報Mz2を出力するステップS804g。第一出力情報Mz1および第二出力情報Mz2は第四実施形態と同様に暗号化部4262-kで暗号化され、出力部424-kは、第一入力情報Mτ1及び第二入力情報Mτ2を送信した端末装置41-uに対して第一出力情報Mz1および第二出力情報Mz2の暗号文Czを出力するステップS804h。図25に戻り、第四実施形態と同様に復号部417-uで暗号文Czを復号して得られた第一出力情報Mz1は復号処理部816-u図22の第一計算部816e-uに入力され、第二出力情報Mz2は第二計算部816h-uに入力される。これらの第一出力情報Mz1及び第二出力情報Mz2が、判定復号部8261-kから復号処理部816-uに与えられた復号能力に相当するステップS804i。第一計算部716e-uは、第一出力情報Mz1を用いてMz1-MR1を計算してその計算結果をuMとする。計算結果uMは行列積計算部816f-uに送られる。ここで、uM=Mz1-MR1=fMxMMx1となる。すなわち、uMはfMxMについて誤差MX1を持つ標本器となる。その理由については後述するステップS804j。行列積計算部816f-uはuM’=uMaMを得る。なお、行列積計算部816f-uはuMaMの計算によってuM’を得てもよいし、aMuMの計算によってuM’を得てもよい。計算結果uMとその計算結果に基づいて計算されたuM’との組uM,uM’は、第一リスト記憶部816g-uに記憶されるステップS804k。第二計算部816h-uは、第二出力情報Mz2を用いてMz2-MR2を計算してその計算結果をvMとする。計算結果vMは第二リスト記憶部816j-uに記憶される。ここで、vM=Mz2-MR2=fMxMaMMx2となる。すなわち、vMはfMxMについて誤差MX2を持つ乱数化可能標本器となる。その理由については後述するステップS804n。判定部816k-uは、第一リスト記憶部816g-uに記憶された組uM,uM’及び第二リスト記憶部816j-uに記憶されたvMの中で、uM’=vMとなるものがあるか判定するステップS804q。uM’=vMとなるものがあった場合には、ステップS804uに進む。uM’=vMとなるものがなかった場合には、ステップS404rに進む。ステップS404rでは、制御部416n-uがt=Tmaxであるか判定するステップS404r。Tmaxは予め定められた自然数である。t=Tmaxであれば、制御部416n-uは、計算をすることができなかった旨の情報、例えば記号⊥を出力してステップS404t、処理を終える。t=Tmaxでない場合には、制御部416n-uは、tを1だけインクリメント、すなわちt=t1としてステップS404s、ステップS804dに戻る。ステップS804uでは、最終出力部816m-uが、uM’=vMであると判定されたuM’に対応するuMを出力するステップS804u。このように得られたuMは高い確率で暗号文xMを秘密鍵skで復号した復号結果fMxMとなるその理由は後述する。よって、上述した処理を複数回繰り返し、ステップS804uで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、設定によっては圧倒的な確率でuM=fMxMとなる。その場合にはステップS804uで得られた値をそのまま復号結果としてよい。≪Mz1-MR1,Mz2-MR2がfMxMについてそれぞれ誤差MX1,MX2を持つ標本器,乱数化可能標本器となる理由について≫fMxMの準同型性より、fMxMCaCR2=fMxMfMCafMCR2=fMxMaMMR2を満たし、fMxMaM=fMxMCaCR2-MR2=fMMτ2-MR2を満たし、MR2=fMMτ2-fMxMaMを満たす。よってMz2=FMMτ2とおくと、Mz2-MR2=FMMτ2-fMMτ2fMxMaM=fMxMaM{FMMτ2-fMMτ2}を満たす。Mτ2に対応するCM21,CM22,MR2の一様ランダム性から、Mz2-MR2はfMxMaMMx2と統計的に近似する。ただし、Mx2は確率変数MX2=FMENCMMU2-MU2MU2はGM上で一様ランダムに分布の実現値である。したがって、Mz2-MR2はfMxMについてそれぞれ誤差MX2を持つ乱数化可能標本器となる。同様にfMxMCUMCR1=fMxMfMCUMfMCR1=fMxMUMMR1を満たし、fMxM=fMxMCUMCR1-MR1=fMMτ1-MR1を満たし、MR1=fMMτ1-fMxMを満たす。よってMz1=FMMτ1とおくと、Mz1-MR1=FMMτ1-fMMτ1fMxM=fMxM{FMMτ1-fMMτ1}を満たす。Mτ1に対応するCM11,CM12,MR1の一様ランダム性から、Mz1-MR1はfMxMMx1と統計的に近似する。ただし、Mx1は確率変数MX1=FMENCMMU1-MU1MU1はGM上で一様ランダムに分布の実現値である。したがって、Mz1-MR1はfMxMについてそれぞれ誤差MX1を持つ標本器となる。≪復号結果fMxMが得られる理由について≫第七実施形態の≪復号結果fxが得られる理由について≫で説明したのと同様な理由により、本形態でも正しい復号結果fMxMが得られる。ただし本形態では行列を扱う関係上、第七実施形態の≪復号結果fxが得られる理由について≫のG,HがGM,HMに、fxがfMxMに、τがMτに、FτがFMMτに、zがMzに、xがxMに、X1,X2がMX1,MX2に、x1,x2がMx1,Mx2に、egがι×ιの単位行列Megに、乗法的表現が加法的表現に例えばαβγがαβγにそれぞれ置き換えられる。さらに本形態では擬似自由pseudo-freeな作用の定義が以下のようにされる。擬似自由pseudo-freeな作用:GM、行列の集合ΩM={0M,...,MM}、GM上の確率変数MX1,MX2の各実現値αM∈MX1αM≠Meg,βM∈MX2、及びaM∈ΩMについて、αMaM=βMとなる確率Pr[αMaMかつαM≠Meg|aM∈UΩM,αM∈MX1,βM∈MX2]について、あらゆる可能なMX1,MX2に関する上限値を、組GM,ΩMの疑似自由指標とよび、これをPGM,ΩMと表すことにする。ある無視することができる関数ζkが存在して、PGM,ΩM<ζkである場合、組GM,ΩMによって定義される演算は擬似自由な作用であるという。[変形例等]確率変数X1、X2及びX3は、同じでも異なっていてもよい。同様に、確率変数MX1及びMX2は、同じでも異なっていてもよい。第一乱数生成部、第二乱数生成部、第三乱数生成部、第四乱数生成部、第五乱数生成部、第六乱数生成部及び第七乱数生成部のそれぞれは、一様乱数を生成することにより、復号システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部、第二乱数生成部、第三乱数生成部、第四乱数生成部、第五乱数生成部、第六乱数生成部及び第七乱数生成部の少なくとも一部が、一様乱数ではない乱数を生成してもよい。同様に、第八実施形態で行列を一様ランダムに選択する代わりに、一様ではないランダムな行列が選択されてもよい。また、演算効率上からは、上述の各実施形態のように0以上KH未満の自然数である乱数や0以上KG未満の自然数である乱数が選択されることが望ましいが、それらの代わりにKH以上やKG以上の自然数の乱数が選択されてもよい。復号処理部が同一のa,bに対応する群Hの元である第一入力情報τ1及び第二入力情報τ2を判定復号部に提供するたびに、判定復号部の処理が複数回実行させてもよい。これにより、復号処理部が第一入力情報τ1及び第二入力情報τ2を判定復号部に一回提供するたびに、復号処理部は第一出力情報z1や第二出力情報z2や第三出力情報z3を複数個得ることができる。これにより、復号処理部と判定復号部との間のやり取り回数や通信量を減らすことができる。第八実施形態の第一入力情報Mτ1及び第二入力情報Mτ2についても同様である。また、復号処理部が複数種類の第一入力情報τ1及び第二入力情報τ2を判定復号部にまとめて提供し、対応する第一出力情報z1や第二出力情報z2や第三出力情報z3を複数個まとめて取得してもよい。これにより、復号処理部と判定復号部との間のやり取り回数を減らすことができる。第八実施形態の第一入力情報Mτ1及び第二入力情報Mτ2についても同様である。また、第一実施形態から第七実施形態の第一計算部や第二計算部において得られたuやvが群Gの元であるかを確認し、群Gの元であった場合には上述した処理を続行し、u又はvが群Gの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号⊥が出力されてもよい。同様に、第八実施形態の第一計算部や第二計算部において得られたuMやvMがGMの元であるかを確認し、GMの元であった場合には上述した処理を続行し、uM又はvMがGMの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号⊥が出力されてもよい。本発明は上述の実施の形態に限定されるものではなく、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"