(57)【特許請求の範囲】
【請求項１】
Ｇ，Ｈが巡回群、ｆ（ｘ）が群Ｈの元である第３暗号文ｘを特定の秘密鍵で復号して群Ｇの元を得るための復号関数、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素である自然数であり、
何れかの端末装置に対応する登録許可情報を格納する登録許可情報記憶部と、
暗号文と端末情報とが入力される入力部と、
前記暗号文の復号結果に対応する応答情報を生成する復号部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記応答情報を出力する出力部と、を含む鍵装置と、
前記第３暗号文ｘの生成に用いられた公開鍵に対応する鍵装置情報で特定される前記鍵装置に対し、前記第３暗号文ｘに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２である前記暗号文と前記端末装置に対応する端末情報とを出力する入力情報提供部を含む端末装置と、
を有し、
前記鍵装置の前記復号部は、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする第一出力情報生成部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた計算結果を第二出力情報ｚ２とする第二出力情報生成部と、を含み、
前記応答情報は、前記第一出力情報ｚ１及び前記第二出力情報ｚ２であり、
前記端末装置は、
前記第一出力情報ｚ１から計算結果ｕ＝ｆ（ｘ）ｂｘ１を生成する第一計算部と、
前記第二出力情報ｚ２から計算結果ｖ＝ｆ（ｘ）ａｘ２を生成する第二計算部と、
前記計算結果ｕ及びｖがｕａ＝ｖｂを満たす場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕｂ’ｖａ’を出力する最終出力部と、を含む、
ことを特徴とする復号システム。
【請求項２】
ＧＭ，ＨＭが行列の集合、ｆＭ（ｘＭ）が集合ＨＭの元である第３暗号文ｘＭを特定の秘密鍵で復号して集合ＧＭの元を得るための復号関数、ＭＸ１，ＭＸ２が集合ＧＭに値を持つ確率変数、Ｍｘ１が確率変数ＭＸ１の実現値、Ｍｘ２が確率変数ＭＸ２の実現値、ａＭが集合ＨＭの元であり、
何れかの端末装置に対応する登録許可情報を格納する登録許可情報記憶部と、
暗号文と端末情報とが入力される入力部と、
前記暗号文の復号結果に対応する応答情報を生成する復号部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記応答情報を出力する出力部と、を含む鍵装置と、
前記第３暗号文ｘＭの生成に用いられた公開鍵に対応する鍵装置情報で特定される前記鍵装置に対し、前記第３暗号文ｘＭに対応する群Ｈの元である第一入力情報Ｍτ１及び第二入力情報Ｍτ２である前記暗号文と前記端末装置に対応する端末情報とを出力する入力情報提供部を含む端末装置と、
を有し、
前記鍵装置の前記復号部は、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第一入力情報Ｍτ１を用い、或る確率より大きな確率でｆＭ（Ｍτ１）を正しく計算し、得られた計算結果を第一出力情報Ｍｚ１とする第一出力情報生成部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第二入力情報Ｍτ２を用い、或る確率より大きな確率でｆＭ（Ｍτ２）を正しく計算し、得られた計算結果を第二出力情報Ｍｚ２とする第二出力情報生成部と、を含み、
前記応答情報は、前記第一出力情報Ｍｚ１及び前記第二出力情報Ｍｚ２であり、
前記端末装置は、
前記第一出力情報Ｍｚ１から計算結果ｕＭ＝ｆＭ（ｘＭ）＋Ｍｘ１を生成する第一計算部と、
前記第二出力情報Ｍｚ２から計算結果ｖＭ＝ｆＭ（ｘＭ）ａＭ＋Ｍｘ２を生成する第二計算部と、
前記計算結果ｕＭ及びｖＭがｕＭ・ａＭ＝ｖＭを満たす場合にｕＭを出力する最終出力部と、を含む、
ことを特徴とする復号システム。
【請求項３】
請求項１または２の復号システムであって、
前記端末装置に対応する登録許可情報は、前記端末装置に固有な情報であり、
前記端末情報は、何れかの端末装置に固有な情報である、
ことを特徴とする復号システム。
【請求項４】
請求項１から３の何れかの復号システムであって、
前記端末情報に対応する復号鍵である端末復号鍵を格納する端末情報記憶部を含む端末装置を有し、
前記端末情報に対応する前記登録許可情報は暗号化鍵であり、
前記応答情報は、前記端末情報に対応する前記登録許可情報を暗号化鍵とし、前記暗号文の復号結果を暗号化した情報であり、
前記端末装置は、前記端末復号鍵を用いて前記応答情報を復号する第２復号部を含む、
ことを特徴とする復号システム。
【請求項５】
Ｇ，Ｈが巡回群、ｆ（ｘ）が群Ｈの元である第３暗号文ｘを特定の秘密鍵で復号して群Ｇの元を得るための復号関数であり、
何れかの端末装置に対応する登録許可情報を格納する登録許可情報記憶部と、
前記第３暗号文ｘに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２、並びに端末情報が入力される入力部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１として出力する第一出力情報生成部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた計算結果を第二出力情報ｚ２として出力する第二出力情報生成部と、
を有する鍵装置。
【請求項６】
ＧＭ，ＨＭが行列の集合、ｆＭ（ｘＭ）が集合ＨＭの元である第３暗号文ｘＭを特定の秘密鍵で復号して集合ＧＭの元を得るための復号関数であり、
何れかの端末装置に対応する登録許可情報を格納する登録許可情報記憶部と、
前記第３暗号文ｘＭに対応する群Ｈの元である第一入力情報Ｍτ１及び第二入力情報Ｍτ２、並びに端末情報が入力される入力部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第一入力情報Ｍτ１を用い、或る確率より大きな確率でｆＭ（Ｍτ１）を正しく計算し、得られた計算結果を第一出力情報Ｍｚ１として出力する第一出力情報生成部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第二入力情報Ｍτ２を用い、或る確率より大きな確率でｆＭ（Ｍτ２）を正しく計算し、得られた計算結果を第二出力情報Ｍｚ２として出力する第二出力情報生成部と、
を有する鍵装置。
【請求項７】
Ｇ，Ｈが巡回群、ｆ（ｘ）が群Ｈの元である第３暗号文ｘを特定の秘密鍵で復号して群Ｇの元を得るための復号関数であり、
何れかの端末装置に対応する登録許可情報を鍵装置の登録許可情報記憶部に格納するステップと、
前記第３暗号文ｘに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２、並びに端末情報が前記鍵装置の入力部に入力されるステップと、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、第一出力情報生成部で、前記第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１として出力するステップと、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、第二出力情報生成部で、前記第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた計算結果を第二出力情報ｚ２として出力するステップと、
を有する復号方法。
【請求項８】
ＧＭ，ＨＭが行列の集合、ｆＭ（ｘＭ）が集合ＨＭの元である第３暗号文ｘＭを特定の秘密鍵で復号して集合ＧＭの元を得るための復号関数であり、
何れかの端末装置に対応する登録許可情報を鍵装置の登録許可情報記憶部に格納するステップと、
前記第３暗号文ｘＭに対応する群Ｈの元である第一入力情報Ｍτ１及び第二入力情報Ｍτ２、並びに端末情報が前記鍵装置の入力部に入力されるステップと、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、第一出力情報生成部で、前記第一入力情報Ｍτ１を用い、或る確率より大きな確率でｆＭ（Ｍτ１）を正しく計算し、得られた計算結果を第一出力情報Ｍｚ１として出力するステップと、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、第二出力情報生成部で、前記第二入力情報Ｍτ２を用い、或る確率より大きな確率でｆＭ（Ｍτ２）を正しく計算し、得られた計算結果を第二出力情報Ｍｚ２として出力するステップと、
を有する復号方法。
【請求項９】
請求項７又は８の復号方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号文の復号技術に関する。
【背景技術】
【０００２】
秘密文書などの秘密情報が暗号化された暗号文の復号を特定の端末装置のみに許可し、許可された端末装置のみに復号結果を閲覧させる技術がある。このような技術では、許可された端末装置が紛失や盗難などの事情で第三者の手に渡ったときに、その端末装置を入手した第三者が秘密情報を閲覧できるという問題がある。
【０００３】
このような問題に対する従来技術には大きく２つの方針がある。第１の方針は、端末装置に対して遠隔操作を施し、第三者の手に渡った端末装置を無効化するものである。第２の方針は、端末装置の他に端末装置と通信する安全なデバイスを設置して、そのデバイスを制御することで、端末装置の復号機能を無効化するものである。
【０００４】
第１の方針による技術には、携帯電話に対する遠隔ロックサービスなどがある（例えば、非特許文献１等参照）。第２の方針による技術には、有効期限が限られた鍵を払い出すデバイスを用いる方式がある（例えば、非特許文献２等参照）。例えばＩＤベース暗号方式などに則り、安全なデバイスに格納されたマスター秘密鍵から一定期間のみ復号アルゴリズムの鍵として機能する二次秘密鍵を生成し、二次秘密鍵のみを端末装置に格納する。端末装置は二次秘密鍵を用いて暗号文を復号できるが、一定期間を過ぎた二次秘密鍵では暗号文を復号できない。第三者の手に渡った端末装置では、格納された二次秘密鍵が更新されないため、一定期間の後にはその端末装置の復号機能が無効化される。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】涌井道子、竹内伸夫、一瀬晃弘、小野木雅、”端末管理に対する多様なニーズに対応した端末管理制御基盤システムの開発”、[online]、平成２１年１０月、ＮＴＴ ＤＯＣＯＭＯテクニカル・ジャーナルＶｏｌ.１７ Ｎｏ.３、Ｐ５０−５４、[平成２２年１２月３１日検索]、インターネット＜http://www.nttdocomo.co.jp/binary/pdf/corporate/technology/rd/technical_journal/bn/vol17_3/vol17_3_050jp.pdf＞
【非特許文献２】A. Boldyreva, V. Goyal, V. Kumar, “Identity-based Encryption with Efficient Revocation,” Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS 2008, ACM Press, 2008, pp. 417-426.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、第１の方針では端末装置の機能を遠隔操作でロックすることができない場合には、端末装置の復号機能を無効化できない。第２の方針では、すべての端末装置に格納された鍵の更新が必要となり、運用のためのコストがかさむ。
【０００７】
本発明はこのような点に鑑みてなされたものであり、端末装置に対する制御を行うことなく、端末装置が暗号文の復号結果を閲覧する権限を無効化できる技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
何れかの端末装置に対応する登録許可情報を鍵装置の登録許可情報記憶部に格納しておく。鍵装置に暗号文と端末情報とが入力されると、鍵装置は当該端末情報が登録許可情報記憶部に格納された何れかの登録許可情報に対応する場合に、暗号文の復号結果に対応する応答情報を出力する。
【発明の効果】
【０００９】
登録許可情報が登録許可情報記憶部に格納された端末装置に対応する端末情報と暗号文とが鍵装置に入力された場合、当該端末装置は鍵装置から出力された応答情報から復号結果を得ることができる。一方、登録許可情報記憶部から当該登録許可情報が削除された場合には鍵装置から応答情報は出力されず、当該端末装置は復号結果を得ることができない。
【００１０】
このように本発明では、端末装置に対する制御を行うことなく、登録許可情報記憶部に格納された登録許可情報を削除することで、削除した登録許可情報に対応する端末装置が暗号文の復号結果を閲覧する権限を無効化できる。
【図面の簡単な説明】
【００１１】
【図１】実施形態の復号システムの全体構成を説明するための図。
【図２】第一実施形態の端末装置と鍵装置の機能構成を説明するための図。
【図３】第一実施形態の復号方法を説明するための図。
【図４】第二実施形態の端末装置と鍵装置の機能構成を説明するための図。
【図５】第二実施形態の復号方法を説明するための図。
【図６】第三実施形態の端末装置と鍵装置の機能構成を説明するための図。
【図７】第三実施形態の復号方法を説明するための図。
【図８】実施形態の復号システムの機能構成を説明するための図。
【図９】実施形態の鍵装置ＤＢ（データベース）の機能構成を説明するための図。
【図１０】実施形態の端末装置と鍵装置の機能構成を説明するための図。
【図１１】実施形態の復号処理部の機能構成を説明するための図。
【図１２】実施形態の判定復号部の機能構成を説明するための図。
【図１３】第五実施形態の入力情報提供部の機能構成を説明するための図。
【図１４】第六実施形態の入力情報提供部の機能構成を説明するための図。
【図１５】実施形態の復号方法を説明するための図。
【図１６】実施形態の自己訂正処理を説明するための図。
【図１７】実施形態の自己訂正処理を説明するための図。
【図１８】ステップＳ５０４ｄの処理を説明するための図。
【図１９】ステップＳ６０４ｄの処理を説明するための図。
【図２０】第七実施形態の復号処理部の機能構成を説明するための図。
【図２１】第七実施形態の自己訂正処理を説明するための図。
【図２２】第八実施形態の復号処理部の機能構成を説明するための図。
【図２３】第八実施形態の判定復号部の機能構成を説明するための図。
【図２４】第八実施形態の入力情報提供部の機能構成を説明するための図。
【図２５】実施形態の自己訂正処理を説明するための図。
【図２６】実施形態の自己訂正処理を説明するための図。
【図２７】ステップＳ８０４ｄの処理を説明するための図。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施形態を説明する。
【００１３】
［第一実施形態］
本発明の第一実施形態を説明する。
【００１４】
＜構成＞
図１に例示するように、第一実施形態の復号システム１は、Ｕ（Ｕは１以上の整数）個の端末装置１１−ｕ（ｕ＝１，・・・，Ｕ）と鍵装置１２とを有し、これらはネットワークを通じて通信可能に構成されている。
【００１５】
図２に例示するように、本形態の端末装置１１−ｕは、それぞれアドレス記憶部１１１−ｕと暗号文記憶部１１２−ｕと入力部１１３−ｕと出力部１１４−ｕと制御部１１５−ｕと復号処理部１１６−ｕとを有する。本形態の鍵装置１２は、安全に管理される装置であり、登録許可情報記憶部１２１と秘密鍵記憶部１２２と入力部１２３と出力部１２４と制御部１２５と復号部１２６と登録処理部１２７とを有する。端末装置１１−ｕ及び鍵装置１２は、ルータ装置、サーバ装置、携帯電話、ＩＣカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたＣＰＵ(central processing unit)やＲＡＭ(random-access memory)を備えた公知又は専用のコンピュータなどである。端末装置１１−ｕは制御部１１５−ｕの制御のもとで各処理を実行し、鍵装置１２は制御部１２５の制御のもとで各処理を実行する。
【００１６】
＜事前処理＞
端末装置１１−ｕ（図２）の暗号文記憶部１１２−ｕには、公開鍵暗号方式に則って公開鍵ｙで平文ｍを暗号化して得られる暗号文Ｃ＝Ｅｎｃ（ｙ，ｍ）が格納されている。公開鍵暗号方式の例は、ＥｌＧａｍａｌ暗号方式、ＲＳＡ暗号方式、Ｐａｉｌｌｅｒ暗号方式などである。アドレス記憶部１１１−ｕには、端末装置１１−ｕのアドレスＡｄｄ（ｕ）（端末情報）が格納されている。アドレスの例はＩＰアドレスなどである。
【００１７】
鍵装置１２の秘密鍵記憶部１２２には、公開鍵ｙに対応する秘密鍵ｓが格納されている。登録許可情報記憶部１２１には、何れかの端末装置１１−ｕ’（ｕ’＝１，・・・，Ｕ）のアドレスＡｄｄ（ｕ’）（登録許可情報）のリストＬｉｓｔが格納されている。登録処理部１２７は、リストＬｉｓｔに端末装置１１−ｕ’のアドレスＡｄｄ（ｕ’）を追加する旨の指示や、リストＬｉｓｔから端末装置１１−ｕ’のアドレスＡｄｄ（ｕ’）を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部１２７は、登録許可情報記憶部１２１に格納されたリストＬｉｓｔに、指示された端末装置１１−ｕ’のアドレスＡｄｄ（ｕ’）を追加する。後者の指示が入力された登録処理部１２７は、登録許可情報記憶部１２１に格納されたリストＬｉｓｔから、指示された端末装置１１−ｕ’のアドレスＡｄｄ（ｕ’）を削除する。
【００１８】
＜復号処理＞
図３に例示するように、端末装置１１−ｕ（図２）の復号処理部１１６−ｕは、復号を行う暗号文Ｃを暗号文記憶部１２２−ｕから読み込み、端末装置１１−ｕのアドレスＡｄｄ（ｕ）をアドレス記憶部１１１−ｕから読み込み、これらを出力部１１４−ｕに送る。出力部１１４−ｕには鍵装置１２のアドレスまたはそれに対応する情報が格納されており、出力部１１４−ｕは暗号文ＣとアドレスＡｄｄ（ｕ）とを鍵装置１２に対して出力する（ステップＳ１０１）。
【００１９】
暗号文ＣとアドレスＡｄｄ（ｕ）はネットワーク経由で鍵装置１２に送信され、鍵装置１２の入力部１２３に入力される（ステップＳ１０２）。暗号文ＣとアドレスＡｄｄ（ｕ）は復号部１２６に送られる。復号部１２６は、送られたアドレスＡｄｄ（ｕ）が登録許可情報記憶部１２１に格納されたリストＬｉｓｔが含む何れかのアドレスＡｄｄ（ｕ’）に一致するか（対応するか）を判定する（ステップＳ１０３）。
【００２０】
ステップＳ１０３で、送られたアドレスＡｄｄ（ｕ）がリストＬｉｓｔに含まれる何れかのアドレスＡｄｄ（ｕ’）に一致すると判定された場合、復号部１２６は、秘密鍵記憶部１２２から秘密鍵ｓを読み込み、秘密鍵ｓを用い、公開鍵暗号方式に則って暗号文Ｃを復号して復号結果ｍ’＝Ｄｅｃ（ｓ，Ｃ）を生成する（ステップＳ１０４）。復号結果ｍ’（暗号文の復号結果に対応する応答情報）は出力部１２４に送られ、出力部１２４は、暗号文Ｃを送信した端末装置１１−ｕに対して復号結果ｍ’を出力する（ステップＳ１０５）。
【００２１】
ステップＳ１０３で、送られたアドレスＡｄｄ（ｕ）がリストＬｉｓｔに含まれる何れのアドレスＡｄｄ（ｕ’）とも一致しないと判定された場合、復号部１２６は、復号することができなかったことを示すエラー情報⊥を出力する。情報⊥は出力部１２４に送られ、出力部１２４は暗号文Ｃを送信した端末装置１１−ｕに対してエラー情報⊥を出力する（ステップＳ１０６）。
【００２２】
復号結果ｍ’またはエラー情報⊥は端末装置１１−ｕの入力部１１３−ｕに入力され、復号処理部１１６−ｕに送られる（ステップＳ１０７）。復号処理部１１６−ｕは復号結果ｍ’またはエラー情報⊥を出力する（ステップＳ１０８）。
【００２３】
＜第一実施形態の特徴＞
本形態では、登録許可情報記憶部１２１に格納されたリストＬｉｓｔが含むアドレスに対応する端末装置１１−ｕから送信された暗号文Ｃのみが復号される。そのため、登録許可情報記憶部１２１に格納されたリストＬｉｓｔにアドレスＡｄｄ（ｕ）を追加したり、リストＬｉｓｔからアドレスＡｄｄ（ｕ）を削除したりするだけで、端末装置１１−ｕに暗号文Ｃの復号結果を取得させるか否かを制御できる。その結果、端末装置１１−ｕに対する制御を行うことなく、登録許可情報記憶部１２１に格納されたアドレスＡｄｄ（ｕ）を削除することで、削除したアドレスＡｄｄ（ｕ）に対応する端末装置１１−ｕが暗号文Ｃの復号結果を閲覧する権限を無効化できる。
【００２４】
［第二実施形態］
本発明の第二実施形態を説明する。インターネットなどのネットワークでは、ＤＨＣＰ(Dynamic Host Configuration Protocol)等の技術によって端末装置のアドレスが動的に付与される場合がある。このような場合、端末装置のアドレスをあらかじめ鍵装置に格納しておくことは現実的ではない。これに対して第二実施形態では、端末装置に固有な情報を鍵装置に格納し、鍵装置の出力情報を、固有な情報に対応する端末装置によって復号可能なように暗号化する。以下では第一実施形態との相違点を中心に説明し、第一実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。
【００２５】
＜構成＞
図１に例示するように、第二実施形態の復号システム２は、Ｕ個の端末装置２１−ｕ（ｕ＝１，・・・，Ｕ）と鍵装置２２とを有し、これらはネットワークを通じて通信可能に構成されている。
【００２６】
図４に例示するように、本形態の端末装置２１−ｕは、それぞれ固有情報記憶部２１１−ｕと暗号文記憶部１１２−ｕと入力部１１３−ｕと出力部１１４−ｕと制御部１１５−ｕと復号処理部２１６−ｕと復号部２１７−ｕとを有する。本形態の鍵装置２２は、安全に管理される装置であり、登録許可情報記憶部２２１と秘密鍵記憶部１２２と入力部１２３と出力部１２４と制御部１２５と復号部２２６と登録処理部２２７とを有する。復号部２２６は判定復号部２２６１と暗号化部２２６２とを有する。端末装置２１−ｕ及び鍵装置２２は、ルータ装置、サーバ装置、携帯電話、ＩＣカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータなどである。端末装置２１−ｕは制御部１１５−ｕの制御のもとで各処理を実行し、鍵装置２２は制御部１２５の制御のもとで各処理を実行する。
【００２７】
＜事前処理＞
本形態ではアドレス情報記憶部にアドレスが格納される代わりに、端末装置２１−ｕの固有情報記憶部２１１−ｕに、端末装置２１−ｕに固有な固有公開情報ＰＴ（ｕ）（端末情報）及び固有秘密情報ＳＴ（ｕ）（端末復号鍵）が格納されている。固有公開情報ＰＴ（ｕ）及び固有秘密情報ＳＴ（ｕ）は、或る暗号化方式における互いに対応する暗号化鍵及び復号鍵のペアである。この暗号化方式の例は、共通鍵暗号、公開鍵暗号、ＩＤベース暗号などである。例えば、この暗号化方式が共通鍵暗号であればＰＴ（ｕ）＝ＳＴ（ｕ）である。この暗号化方式が公開鍵暗号方式であれば、固有公開情報ＰＴ（ｕ）は公開鍵であり、固有秘密情報ＳＴ（ｕ）はそれに対応する秘密鍵である。この暗号化方式がＩＤベース暗号方式であれば、固有公開情報ＰＴ（ｕ）は鍵装置２２のＩＤであり、固有秘密情報ＳＴ（ｕ）は鍵装置２２のＩＤに対応する秘密鍵である。
【００２８】
また本形態では鍵装置の登録許可情報記憶部に何れかの端末装置のアドレスのリストが格納される代わりに、鍵装置２２の登録許可情報記憶部２２１に何れかの端末装置２１−ｕ’（ｕ’＝１，・・・，Ｕ）の固有公開情報ＰＴ（ｕ’）（登録許可情報）のリストＬｉｓｔＴが格納されている。登録処理部２２７は、リストＬｉｓｔＴに端末装置２１−ｕ’の固有公開情報ＰＴ（ｕ’）を追加する旨の指示や、リストＬｉｓｔＴから端末装置２１−ｕ’の固有公開情報ＰＴ（ｕ’）を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部２２７は、登録許可情報記憶部１２１に格納されたリストＬｉｓｔＴに、指示された固有公開情報ＰＴ（ｕ’）を追加する。後者の指示が入力された登録処理部１２７は、登録許可情報記憶部１２１に格納されたリストＬｉｓｔＴから、指示された固有公開情報ＰＴ（ｕ’）を削除する。
【００２９】
その他は第一実施形態と同様である。
【００３０】
＜復号処理＞
図５に例示するように、端末装置２１−ｕ（図４）の復号処理部２１６−ｕは、復号を行う暗号文Ｃを暗号文記憶部１２２−ｕから読み込み、端末装置１１−ｕの固有公開情報ＰＴ（ｕ）を固有情報記憶部２１１−ｕから読み込み、これらを出力部１１４−ｕに送る。出力部１１４−ｕには鍵装置１２のアドレスまたはそれに対応する情報が格納されており、出力部１１４−ｕは暗号文Ｃと固有公開情報ＰＴ（ｕ）とを鍵装置２２に対して出力する（ステップＳ２０１）。
【００３１】
暗号文Ｃと固有公開情報ＰＴ（ｕ）はネットワーク経由で鍵装置２２に送信され、鍵装置２２の入力部１２３に入力される（ステップＳ２０２）。暗号文Ｃと固有公開情報ＰＴ（ｕ）は復号部２２６に送られる。復号部２２６の判定復号部２２６１は、送られた固有公開情報ＰＴ（ｕ）が登録許可情報記憶部１２１に格納されたリストＬｉｓｔＴが含む何れかの固有公開情報ＰＴ（ｕ’）に一致するか（対応するか）を判定する（ステップＳ２０３）。
【００３２】
ステップＳ２０３で、送られた固有公開情報ＰＴ（ｕ）がリストＬｉｓｔＴに含まれる何れかの固有公開情報ＰＴ（ｕ’）に一致すると判定された場合、判定復号部２２６１は、秘密鍵記憶部１２２から秘密鍵ｓを読み込み、秘密鍵ｓを用い、公開鍵暗号方式に則って暗号文Ｃを復号して復号結果ｍ’＝Ｄｅｃ（ｓ，Ｃ）を生成する（ステップＳ１０４）。復号結果ｍ’と固有公開情報ＰＴ（ｕ）とは暗号化部２２６２に送られる。暗号化部２２６２は、固有公開情報ＰＴ（ｕ）（端末情報に対応する登録許可情報）を暗号化鍵とし、暗号文Ｃの復号結果ｍ’を暗号化した暗号文Ｃ’＝Ｅｎｃ’（ＰＴ（ｕ），ｍ’）を生成する（ステップＳ２０４）。暗号文Ｃ’（暗号文の復号結果に対応する応答情報）は出力部１２４に送られ、出力部１２４は、暗号文Ｃを送信した端末装置２１−ｕに対して暗号文Ｃ’を出力する（ステップＳ２０５）。暗号文Ｃ’は端末装置２１−ｕの入力部１１３−ｕに入力され、復号部２１７−ｕに送られる（ステップＳ２０７）。復号部２１７−ｕ（第２復号部）は、固有情報記憶部２１１−ｕから固有秘密情報ＳＴ（ｕ）を読み込み、固有秘密情報ＳＴ（ｕ）を復号鍵として用いて暗号文Ｃ’を復号し、復号結果ｍ’’＝Ｄｅｃ’（ＳＴ（ｕ），Ｃ’）を生成する。復号結果ｍ’’は復号処理部２１６−ｕに送られ（ステップＳ２０８）、復号処理部２１６−ｕは復号結果ｍ’’を出力する（ステップＳ１０８）。
【００３３】
一方ステップＳ２０３で、送られた固有公開情報ＰＴ（ｕ）がリストＬｉｓｔＴに含まれる何れの固有公開情報ＰＴ（ｕ’）とも一致しないと判定された場合、復号部２２６は、復号することができなかったことを示すエラー情報⊥を出力する。情報⊥は出力部１２４に送られ、出力部１２４は暗号文Ｃを送信した端末装置１１−ｕに対してエラー情報⊥を出力する（ステップＳ１０６）。エラー情報⊥は端末装置２１−ｕの入力部１１３−ｕに入力され、復号処理部２１６−ｕに送られて（ステップＳ１０７）出力される（ステップＳ１０８）。
【００３４】
＜第二実施形態の特徴＞
本形態では、登録許可情報記憶部２２１に格納されたリストＬｉｓｔＴが含む固有公開情報に対応する端末装置２１−ｕから送信された暗号文Ｃのみが復号される。そのため登録許可情報記憶部１２１に格納されたリストＬｉｓｔＴに固有公開情報ＰＴ（ｕ）を追加したり、リストＬｉｓｔＴから固有公開情報ＰＴ（ｕ）を削除したりするだけで、端末装置２１−ｕに暗号文Ｃの復号結果を取得させるか否かを制御できる。その結果、端末装置２１−ｕに対する制御を行うことなく、登録許可情報記憶部２２１に格納された固有公開情報ＰＴ（ｕ）を削除することで、削除した固有公開情報ＰＴ（ｕ）に対応する端末装置２１−ｕが暗号文Ｃの復号結果を閲覧する権限を無効化できる。
【００３５】
また、本形態では端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。
【００３６】
［第三実施形態］
本発明の第三実施形態を説明する。上述の各実施形態では鍵装置の管理者が暗号文Ｃの復号結果を知ることができる。したがって、鍵装置の管理者が端末装置の使用者と異なる場合、端末装置の使用者のみが知るべき情報が鍵装置の管理者に知られる可能性がある。これに対して第三実施形態では、鍵装置がランダム帰着可能な暗号文の復号を行う点がこれまでの実施形態と相違する。ランダム帰着可能な暗号化方式は、ランダム化アルゴリズムと復元アルゴリズムとからなる。ランダム化アルゴリズムは、暗号文と乱数とを用いて別の暗号文を出力する確率アルゴリズムで、出力は入力によらずランダムに選ばれた暗号文と識別できない確率分布に従う。復元アルゴリズムはランダム化アルゴリズムの出力である暗号文を復号した結果とランダム化アルゴリズムで用いられた乱数を入力として、もとの暗号文を復号した平文を出力する。このような暗号方式は、例えばElGamal暗号、楕円ElGamal 暗号、RSA暗号、Pailler暗号などの準同型暗号方式を用いて容易に構成できる。第三の実施形態は、準同型暗号方式を用いてランダム自己帰着可能な暗号方式を構成した例を示しながら記述する。以下では第一及び第二実施形態との相違点を中心に説明し、第一及び第二実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。
【００３７】
＜構成＞
図１に例示するように、第三実施形態の復号システム３は、Ｕ個の端末装置２１−ｕ（ｕ＝１，・・・，Ｕ）と鍵装置３２とを有し、これらはネットワークを通じて通信可能に構成されている。
【００３８】
図６に例示するように、本形態の端末装置３１−ｕは、それぞれ固有情報記憶部２１１−ｕと暗号文記憶部１１２−ｕと入力部１１３−ｕと出力部１１４−ｕと制御部１１５−ｕと復号処理部３１６−ｕと復号部３１７−ｕとを有する。復号処理部３１６−ｕは、乱数生成部３１６１−ｕと暗号化部３１６２−ｕと復号部３１６３−ｕとを有する。本形態の鍵装置３２は、安全に管理される装置であり、登録許可情報記憶部２２１と秘密鍵記憶部１２２と入力部１２３と出力部１２４と制御部１２５と復号部３２６と登録処理部２２７とを有する。復号部３２６は判定復号部３２６１と暗号化部３２６２とを有する。端末装置３１−ｕ及び鍵装置３２は、ルータ装置、サーバ装置、携帯電話、ＩＣカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータなどである。端末装置３１−ｕは制御部１１５−ｕの制御のもとで各処理を実行し、鍵装置３２は制御部１２５の制御のもとで各処理を実行する。
【００３９】
＜事前処理＞
第二実施形態と同様である。
【００４０】
＜復号処理＞
図７に例示するように、端末装置３１−ｕ（図６）の復号処理部３１６−ｕの乱数生成部３１６１−ｕが乱数Ｒａｎｄを生成し、それを暗号化部３１６２−ｕ及び復号部３１６３−ｕに送る。乱数Ｒａｎｄは暗号化部３１６２−ｕ及び復号部３１６３−ｕ内に格納される（ステップＳ３０１１）。暗号化部３１６２−ｕは、復号を行う暗号文Ｃを暗号文記憶部１２２−ｕから読み込み、暗号方式のランダム自己帰着性から定義されるランダム化アルゴリズムに則り、暗号文Ｃ（第２暗号文）と乱数Ｒａｎｄとに対応する暗号文ＣＲを生成する。例えば暗号文Ｃが準同型暗号方式の暗号文である場合、暗号化部３１６２−ｕはそれと同じ準同型暗号方式に則って公開鍵ｙで乱数Ｒａｎｄを暗号化して得られる暗号文（乱数暗号文）をＥｎｃ（ｙ，Ｒａｎｄ）とし、Ｅｎｃ（ｙ，Ｒａｎｄ）とＣとの乗法によって暗号文ＣＲ＝Ｅｎｃ（ｙ，Ｒａｎｄ）・Ｃを生成する。暗号文ＣＲと固有公開情報ＰＴ（ｕ）とは出力部１１４−ｕに送られる（ステップＳ３０１２）。出力部１１４−ｕには鍵装置３２のアドレスまたはそれに対応する情報が格納されており、出力部１１４−ｕは暗号文ＣＲと固有公開情報ＰＴ（ｕ）とを鍵装置３２に対して出力する（ステップＳ３０１３）。
【００４１】
暗号文ＣＲと固有公開情報ＰＴ（ｕ）はネットワーク経由で鍵装置３２に送信され、鍵装置３２の入力部１２３に入力される（ステップＳ３０２）。暗号文ＣＲと固有公開情報ＰＴ（ｕ）は復号部３２６に送られる。復号部３２６の判定復号部３２６１は、送られた固有公開情報ＰＴ（ｕ）が登録許可情報記憶部１２１に格納されたリストＬｉｓｔＴが含む何れかの固有公開情報ＰＴ（ｕ’）に一致するか（対応するか）を判定する（ステップＳ２０３）。
【００４２】
ステップＳ２０３で、送られた固有公開情報ＰＴ（ｕ）がリストＬｉｓｔＴに含まれる何れかの固有公開情報ＰＴ（ｕ’）に一致すると判定された場合、判定復号部３２６１は、秘密鍵記憶部１２２から秘密鍵ｓを読み込み、秘密鍵ｓを用い、前述の準同型暗号化方式に則って暗号文ＣＲを復号して復号結果ｍＲ＝Ｄｅｃ（ｓ，ＣＲ）を生成する（ステップＳ３０４１）。復号結果ｍＲと固有公開情報ＰＴ（ｕ）とは暗号化部３２６２に送られる。暗号化部３２６２は、固有公開情報ＰＴ（ｕ）（端末情報に対応する登録許可情報）を暗号化鍵とし、暗号文ＣＲの復号結果ｍＲを暗号化した暗号文ＣＲ’＝Ｅｎｃ’（ＰＴ（ｕ），ｍＲ）を生成する（ステップＳ３０４２）。暗号文ＣＲ’（暗号文の復号結果に対応する応答情報）は出力部１２４に送られ、出力部１２４は、暗号文ＣＲを送信した端末装置３１−ｕに対して暗号文ＣＲ’を出力する（ステップＳ３０５）。暗号文ＣＲ’は端末装置３１−ｕの入力部１１３−ｕに入力され、復号部３１７−ｕに送られる（ステップＳ３０７）。復号部３１７−ｕ（第２復号部）は、固有情報記憶部３２１−ｕから固有秘密情報ＳＴ（ｕ）を読み込み、固有秘密情報ＳＴ（ｕ）を復号鍵として用いて暗号文ＣＲ’を復号し、復号結果ｍＲ’＝Ｄｅｃ’（ＳＴ（ｕ），ＣＲ’）を生成する（ステップＳ３０８）。復号結果ｍＲ’は復号処理部３１６も復号部３１６３−ｕに送られ、復号部３１６３−ｕ（第３復号部）は、暗号方式のランダム自己帰着性から定義される復元アルゴリズムに則り、復号結果ｍＲ’と前述の乱数Ｒａｎｄとから暗号文Ｃ（第２暗号文）の復号結果ｍ’を生成する。例えば前述した暗号文ＣＲ＝Ｅｎｃ（ｙ，Ｒａｎｄ）・Ｃである例の場合、復号部３１６３−ｕは乱数Ｒａｎｄの逆元Ｒａｎｄ−１を用い、ｍＲ’と元Ｒａｎｄ−１との乗法ｍ’＝（Ｒａｎｄ−１）・ｍＲ’によって暗号文Ｃの復号結果ｍ’を得ることができる。これは準同型暗号方式の暗号化関数および復号関数が準同型性を持つことに基づく。復号処理部３１６−ｕは復号結果ｍ’を出力する（ステップＳ１０８）。
【００４３】
一方ステップＳ２０３で、送られた固有公開情報ＰＴ（ｕ）がリストＬｉｓｔＴに含まれる何れの固有公開情報ＰＴ（ｕ’）とも一致しないと判定された場合、復号部３２６が復号することができなかったことを示すエラー情報⊥を出力し、第二実施形態のステップＳ１０６−Ｓ１０８と同様に処理される。
【００４４】
＜第三実施形態の特徴＞
本形態でも端末装置３１−ｕに対する制御を行うことなく、登録許可情報記憶部２２１に格納された固有公開情報ＰＴ（ｕ）を削除することで、削除した固有公開情報ＰＴ（ｕ）に対応する端末装置３１−ｕが暗号文Ｃの復号結果を閲覧する権限を無効化できる。
【００４５】
また、端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。
【００４６】
さらに本形態では、鍵装置３２で復号されるのは暗号文Ｃと乱数Ｒａｎｄとに対応する暗号文ＣＲであり、暗号文Ｃそのものではない。鍵装置３２は暗号文ＣＲの復号結果ｍＲを得ることができても、鍵装置３２は乱数Ｒａｎｄを知らないため復号結果ｍＲから暗号文Ｃの復号結果を復元することはできない。これにより、鍵装置３２の管理者に暗号文Ｃの復号結果が知られることを防止できる。
【００４７】
［第四実施形態］
本発明の第四実施形態を説明する。上述の各実施形態では、あらかじめ信頼できる鍵装置が設定され、そのアドレスまたはそれに対応する情報があらかじめ端末装置に格納されている必要があった。これに対して第四実施形態では自己訂正技術を用いることで、信頼できる鍵装置があらかじめ設定されていない場合や、信頼できるか否かが定かではない複数の鍵装置しか存在しない場合であっても、運用が可能な形態である。以下では上述の各実施形態との相違点を中心に説明し、上述の各実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。
【００４８】
＜構成＞
図８に例示するように、第四実施形態の復号システム４は、Ｕ個の端末装置２１−ｕ（ｕ＝１，・・・，Ｕ）とＫ（Ｋは１以上の整数）個の鍵装置２２−ｋ（ｋ＝１，・・・，Ｋ）と鍵装置ＤＢ（データベース）装置４３を有し、これらはネットワークを通じて通信可能に構成されている。
【００４９】
図９に例示するように、本形態の鍵装置ＤＢ装置４３は、鍵装置情報記憶部４３１と入力部４３２と出力部４３３と検索部４３４とを有する。図１０に例示するように、本形態の端末装置４１−ｕは、それぞれ固有情報記憶部２１１−ｕと暗号文記憶部４１２−ｕと入力部１１３−ｕと出力部１１４−ｕと制御部１１５−ｕと復号処理部４１６−ｕと復号部４１７−ｕとを有する。本形態の鍵装置４２−ｋは、安全に管理される装置であり、登録許可情報記憶部４２１−ｋと秘密鍵記憶部４２２−ｋと入力部４２３−ｋと出力部４２４−ｋと制御部４２５−ｋと復号部４２６−ｋと登録処理部４２７−ｋとを有する。復号部４２６−ｋは判定復号部４２６１−ｋと暗号化部４２６２−ｋとを有する。図１１に例示するように、本形態の復号処理部４１６−ｕは、例えば、自然数記憶部４１６ａ−ｕと自然数選択部４１６ｂ−ｕと整数計算部４１６ｃ−ｕと入力情報提供部４１６ｄ−ｕと第一計算部４１６ｅ−ｕと第一べき乗計算部４１６ｆ−ｕと第一リスト記憶部４１６ｇ−ｕと第二計算部４１６ｈ−ｕと第二べき乗計算部４１６ｉ−ｕと第二リスト記憶部４１６ｊ−ｕと判定部４１６ｋ−ｕと最終出力部４１６ｍ−ｕと制御部４１６ｎ−ｕとを有する。図１２に例示するように、本形態の判定復号部４２６１−ｋは、例えば、第一出力情報計算部４２６１ａ−ｋと第二出力情報計算部４２６１ｂ−ｋと判定部４２６１ｃ−ｋと制御部４２６１ｎ−ｋとを有する。
【００５０】
鍵装置ＤＢ装置４３、端末装置４１−ｕ及び鍵装置４２は、ルータ装置、サーバ装置、携帯電話、ＩＣカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータなどである。端末装置４１−ｕは制御部１１５−ｕの制御のもとで各処理を実行し、鍵装置４２−ｋは制御部４２５−ｋの制御のもとで各処理を実行する。
【００５１】
＜事前処理＞
鍵装置ＤＢ装置４３（図９）の鍵装置情報記憶部４３１には、公開鍵ｙ（ｋ）をキーとして何れかの鍵装置４２−ｋのアドレスＫａｄｄ（ｋ）（鍵装置を特定するための鍵装置情報）を記録した鍵装置データベースが格納される。例えば、公開鍵のハッシュ値をｂａｓｅ６４などの方法でアスキーテキストに変換して、それをホスト名と見なすダイナミックＤＮＳが構成される。鍵装置データベースを用いることで公開鍵ｙ（ｋ）に対応する鍵装置４２−ｋのアドレスが特定される。なお、必ずしも鍵装置４２−ｋのアドレスが真正である必要はなく、鍵装置４２−ｋが公開鍵ｙ（ｋ）に対応する秘密鍵ｓ（ｋ）で常に正しく復号処理を行うことが保証されている必要もない。
【００５２】
端末装置４１−ｕ（図１０）に対する事前処理は、暗号文記憶部に公開鍵暗号方式に則って公開鍵ｙで平文ｍを暗号化して得られる暗号文Ｃ＝Ｅｎｃ（ｙ，ｍ）が格納されている代わりに、暗号文記憶部１１２−ｕに、公開鍵暗号方式に則って公開鍵ｙ（ｋ）で平文ｍを暗号化して得られる暗号文Ｃ＝Ｅｎｃ（ｙ（ｋ），ｍ）が格納されている。それ以外は第二実施形態と同様である。
【００５３】
鍵装置４２−ｋの秘密鍵記憶部１２２−ｋには、公開鍵ｙ（ｋ）に対応する秘密鍵ｓ（ｋ）が格納されている。鍵装置４２−ｋの登録許可情報記憶部４２１−ｋに何れかの端末装置４１１−ｕ’（ｕ’＝１，・・・，Ｕ）の固有公開情報ＰＴ（ｕ’）（登録許可情報）のリストＬｉｓｔＴが格納されている。登録処理部４２７−ｋは、リストＬｉｓｔＴに端末装置４１１−ｕ’の固有公開情報ＰＴ（ｕ’）を追加する旨の指示や、リストＬｉｓｔＴから端末装置４１１−ｕ’の固有公開情報ＰＴ（ｕ’）を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部４２７−ｋは、登録許可情報記憶部４２１−ｋに格納されたリストＬｉｓｔＴに、指示された固有公開情報ＰＴ（ｕ’）を追加する。後者の指示が入力された登録処理部４２７−ｋは、登録許可情報記憶部４２１−ｋに格納されたリストＬｉｓｔＴから、指示された固有公開情報ＰＴ（ｕ’）を削除する。
【００５４】
＜復号処理＞
端末装置４１−ｕ（図１０）の復号処理部は、復号を行う暗号文Ｃ＝Ｅｎｃ（ｙ（ｋ），ｍ）に対応する公開鍵ｙ（ｋ）を出力部１１４−ｕに出力し、出力部１１４−ｕは公開鍵ｙ（ｋ）を鍵装置ＤＢ装置４３に送信する。公開鍵ｙ（ｋ）は鍵装置ＤＢ装置４３（図９）の入力部４３２に入力され、検索部４３４に送られる。検索部４３４は、公開鍵ｙ（ｋ）に対応する鍵装置４２−ｋのアドレスＫａｄｄ（ｋ）を抽出し、アドレスＫａｄｄ（ｋ）は出力部４３３から出力される。アドレスＫａｄｄ（ｋ）は端末装置４１−ｕの入力部１１３−ｕに入力され復号処理部４１６−ｕに送られる。
【００５５】
図１５に例示するように、次に復号処理部４１６−ｕは、復号を行う暗号文Ｃを暗号文記憶部４２２−ｕから読み込み、端末装置４１−ｕの固有公開情報ＰＴ（ｕ）を固有情報記憶部２１１−ｕから読み込み、これらとアドレスＫａｄｄ（ｋ）とを出力部１１４−ｕに送る。出力部１１４−ｕは暗号文Ｃと固有公開情報ＰＴ（ｕ）とをアドレスＫａｄｄ（ｋ）で特定される鍵装置４２−ｋに対して出力する（ステップＳ４０１）。
【００５６】
暗号文Ｃと固有公開情報ＰＴ（ｕ）はネットワーク経由で鍵装置４２−ｋに送信され、鍵装置４２−ｋの入力部４２３−ｋに入力される（ステップＳ４０２）。暗号文Ｃと固有公開情報ＰＴ（ｕ）は復号部４２６−ｋに送られる。復号部４２６−ｋの判定復号部４２６１−ｋは、送られた固有公開情報ＰＴ（ｕ）が登録許可情報記憶部４２１−ｋに格納されたリストＬｉｓｔＴが含む何れかの固有公開情報ＰＴ（ｕ’）に一致するか（対応するか）を判定する（ステップＳ４０３）。
【００５７】
送られた固有公開情報ＰＴ（ｕ）が登録許可情報記憶部４２１−ｋに格納されたリストＬｉｓｔＴが含む何れの固有公開情報ＰＴ（ｕ’）とも一致しないと判定された場合、前述したステップＳ１０６−Ｓ１０８と同様な処理が実行される。
【００５８】
一方、送られた固有公開情報ＰＴ（ｕ）が登録許可情報記憶部４２１−ｋに格納されたリストＬｉｓｔＴが含む何れかの固有公開情報ＰＴ（ｕ’）に一致すると判定された場合、その旨が端末装置４１−ｕに通知され、端末装置４１−ｕと登録許可情報記憶部４２１−ｋとの間で以下の自己訂正処理が実行される（ステップＳ４０４）。そして、復号処理部４１６−ｕがその結果である暗号文Ｃの復号結果ｍ’またはエラー情報⊥を出力する（ステップＳ１０８）。
【００５９】
＜自己訂正処理（ステップＳ４０４）＞
図１６及び１７を参照して本形態の自己訂正処理を説明する。処理の前提として、Ｇ，Ｈを巡回群、暗号文Ｃを群Ｈの元、暗号文Ｃの復号結果が群Ｇの元、ｆ（ｘ）を群Ｈの元である暗号文ｘ＝Ｃを特定の秘密鍵ｓ（ｋ）で復号して群Ｇの元を得るための復号関数Ｄｅｃ（ｓ（ｋ），ｘ）、群Ｇ，Ｈの生成元をそれぞれμｇ，μｈ、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２とする。また、復号処理部４１６−ｕの自然数記憶部４１６ａ−ｕには、互いに素である２つの自然数ａ，ｂの組（ａ，ｂ）が複数種類記憶されているものとする。「自然数」とは０以上の整数を意味する。Ｉを群Ｇの位数未満の２つの自然数の組で互いに素なものの集合とすると、自然数記憶部４１６ａ−ｕにはＩの部分集合Ｓに対応する自然数ａ，ｂの組（ａ，ｂ）が記憶されていると考えることができる。
【００６０】
図１６及び１７に例示するように、まず、復号処理部４１６−ｕ（図１１）の自然数選択部４１６ｂ−ｕが、自然数記憶部４１６ａ−ｕに記憶された複数の自然数の組（ａ，ｂ）から１つの自然数の組（ａ，ｂ）をランダムに読み込む。読み込まれた自然数の組（ａ，ｂ）少なくとも一部の情報は、整数計算部４１６ｃ−ｕ、入力情報提供部４１６ｄ−ｕ、第一べき乗計算部４１６ｆ−ｕ及び第二べき乗計算部４１６ｉ−ｕに送られる（ステップＳ４０４ａ）。
【００６１】
整数計算部４１６ｃ−ｕは、送られた自然数の組（ａ，ｂ）を用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する。自然数ａ，ｂは互いに素であるため、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’は必ず存在して、その計算方法もよく知られている。たとえば拡張互除法などのよく知られたアルゴリズムによって整数ａ’，ｂ’を計算して、自然数の組（ａ’，ｂ’）の情報は、最終出力部４１６ｍ−ｕに送られる（ステップＳ４０４ｂ）。
【００６２】
制御部４１６ｎ−ｕは、ｔ＝１とする（ステップＳ４０４ｃ）。
【００６３】
入力情報提供部４１６ｄ−ｕは、入力された暗号文ｘにそれぞれ対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を生成して出力する。好ましくは、第一入力情報τ１及び第二入力情報τ２はそれぞれ暗号文ｘとの関係をかく乱させた情報である。これにより、復号処理部４１６−ｕは、暗号文ｘを判定復号部４２６１−ｋに対して隠蔽できる。また、好ましくは、本形態の第一入力情報τ１は自然数選択部４１６ｂ−ｕで選択された自然数ｂにさらに対応し、第二入力情報τ２は自然数選択部４１６ｂ−ｕで選択された自然数ａにさらに対応する。これにより、判定復号部４２６１−ｋから提供された復号能力を復号処理部４１６−ｕが高い精度で評価することが可能となる。第一入力情報τ１及び第二入力情報τ２は出力部１１４−ｕ（図１０）から出力され、鍵装置４２−ｋの入力部４２３−ｋに入力され判定復号部４２６１−ｋに送られる（ステップＳ４０４ｄ）。
【００６４】
第一入力情報τ１は判定復号部４２６１−ｋ（図１２）の第一出力情報計算部４２６１ａ−ｋに入力され、第二入力情報τ２は第二出力情報計算部４２６１ｂ−ｋに入力される（ステップＳ４０４ｅ）。
【００６５】
第一出力情報計算部４２６１ａ−ｋは、第一入力情報τ１と秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする（ステップＳ４０４ｆ）。第二出力情報計算部４２６１ｂ−ｋは、第二入力情報τ２と秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた計算結果を第二出力情報ｚ２とする（ステップＳ４０４ｇ）。なお、「或る確率」は１００％未満の確率である。「或る確率」の例は無視することができない確率であり、「無視することができない確率」の例は、セキュリティパラメータｋについての広義単調増加関数である多項式を多項式ψ（ｋ）とした場合の１／ψ（ｋ）以上の確率である。すなわち、第一出力情報計算部４２６１ａ−ｋや第二出力情報計算部４２６１ｂ−ｋは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部４２６１ａ−ｋでの計算結果がｆ（τ１）の場合もあればｆ（τ１）でない場合もあり、第二出力情報計算部４２６１ｂ−ｋでの計算結果がｆ（τ２）の場合もあればｆ（τ２）でない場合もある。
【００６６】
第一出力情報計算部４２６１ａ−ｋは第一出力情報ｚ１を出力し、第二出力情報計算部４２６１ｂ−ｋは第二出力情報ｚ２を出力する。第一出力情報ｚ１および第二出力情報ｚ２は暗号化部４２６２−ｋに送られる。暗号化部４２６２−ｋは、固有公開情報ＰＴ（ｕ）（端末情報に対応する登録許可情報）を暗号化鍵とし、第一出力情報ｚ１および第二出力情報ｚ２（以下「ｚ＝（ｚ１，ｚ２））を暗号化した暗号文Ｃｚ＝Ｅｎｃ’（ＰＴ（ｕ），ｚ）を生成する。暗号文Ｃｚ（暗号文の復号結果に対応する応答情報）は出力部４２４−ｋに送られ、出力部４２４−ｋは、第一入力情報τ１及び第二入力情報τ２を送信した端末装置４１−ｕに対して暗号文Ｃｚを出力する（ステップＳ４０４ｈ）。暗号文Ｃｚは端末装置４１−ｕの入力部１１３−ｕに入力され、復号部４１７−ｕに送られる。復号部４１７−ｕ（第２復号部）は、固有情報記憶部４２１−ｕから固有秘密情報ＳＴ（ｕ）を読み込み、固有秘密情報ＳＴ（ｕ）を復号鍵として用いて暗号文Ｃｚを復号し、復号結果ｚ＝Ｄｅｃ’（ＳＴ（ｕ），Ｃｚ）、すなわち第一出力情報ｚ１および第二出力情報ｚ２を生成する。第一出力情報ｚ１は復号処理部４１６−ｕ（図１１）の第一計算部４１６ｅ−ｕに入力され、第二出力情報ｚ２は第二計算部４１６ｈ−ｕに入力される。これらの第一出力情報ｚ１及び第二出力情報ｚ２が、判定復号部４２６１−ｋから復号処理部４１６−ｕに与えられた復号能力に相当する（ステップＳ４０４ｉ）。
【００６７】
第一計算部４１６ｅ−ｕは、第一出力情報ｚ１から計算結果ｕ＝ｆ（ｘ）ｂｘ１を生成する。ここで、ｆ（ｘ）ｂｘ１を生成（計算）するとは、ｆ（ｘ）ｂｘ１と定義される式の値を計算することである。式ｆ（ｘ）ｂｘ１の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。また、第一実施形態では群で定義された演算を乗法的に表現する。すなわちα∈Ｇに対する「αｂ」は、群Ｇで定義された演算をαに対してｂ回作用させることを意味し、α１，α２∈Ｇに対する「α１α２」は、α１とα２とを被演算子とした群Ｇで定義された演算を行うことを意味する（後述する第五から第七実施形態も同様）。計算結果ｕは第一べき乗計算部４１６ｆ−ｕに送られる（ステップＳ４０４ｊ）。
【００６８】
第一べき乗計算部４１６ｆ−ｕはｕ’＝ｕａを計算する。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部４１６ｇ−ｕに記憶される（ステップＳ４０４ｋ）。
【００６９】
判定部４１６ｋ−ｕは、第一リスト記憶部４１６ｇ−ｕに記憶された組（ｕ，ｕ’）及び第二リスト記憶部４１６ｊ−ｕに記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ４０４ｍ）。もし、第二リスト記憶部４１６ｊ−ｕに組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ４０４ｍの処理を行わずに、次のステップＳ４０４ｎの処理を行う。ｕ’＝ｖ’となるものがあった場合には、ステップＳ４０４ｕに進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ４０４ｎに進む。
【００７０】
ステップＳ４０４ｎでは、第二計算部４１６ｈ−ｕが、第二出力情報ｚ２から計算結果ｖ＝ｆ（ｘ）ａｘ２を生成する。計算結果ｖは第二べき乗計算部４１６ｉ−ｕに送られる（ステップＳ４０４ｎ）。
【００７１】
第二べき乗計算部４１６ｉ−ｕはｖ’＝ｖｂを計算する。計算結果ｖとその計算結果に基づいて計算されたｖ’との組（ｖ，ｖ’）は、第二リスト記憶部４１６ｊ−ｕに記憶される（ステップＳ４０４ｐ）。
【００７２】
判定部４１６ｋ−ｕは、第一リスト記憶部４１６ｇ−ｕに記憶された組（ｕ，ｕ’）及び第二リスト記憶部４１６ｊ−ｕに記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ４０４ｑ）。ｕ’＝ｖ’となるものがあった場合には、ステップＳ４０４ｕに進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ４０４ｒに進む。
【００７３】
ステップＳ４０４ｒでは、制御部４１６ｎ−ｕがｔ＝Ｔｍａｘであるか判定する（ステップＳ４０４ｒ）。Ｔｍａｘは予め定められた自然数である。ｔ＝Ｔｍａｘであれば、制御部４１６ｎ−ｕは、計算をすることができなかった旨の情報、例えば記号「⊥」を出力する（ステップＳ４０４ｔ）。ｔ＝Ｔｍａｘでない場合には、制御部４１６ｎ−ｕは、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ４０４ｓ）、ステップＳ４０４ｄに戻る。
【００７４】
計算をすることができなかった旨の情報（この例ではエラー情報⊥）は、判定復号部４２６１−ｋが正しく計算を行う信頼性がＴｍａｘで定められる基準を下回るということを意味する。言い換えれば、Ｔｍａｘ回の繰り返しで正しい演算を行うことができなかったということを意味する。
【００７５】
ステップＳ４０４ｕでは、最終出力部４１６ｍ−ｕが、ｕ’＝ｖ’であると判定されたｕ’及びｖ’に対応するｕ及びｖを用いてｍ’＝ｕｂ’ｖａ’を計算して、出力する（ステップＳ４０４ｕ）。このように計算されたｍ’＝ｕｂ’ｖａ’は高い確率で暗号文ｘ＝Ｃを特定の秘密鍵ｓ（ｋ）で復号した復号結果ｆ（ｘ）となる（高い確率でｕｂ’ｖａ’＝ｆ（ｘ）となる理由については後述する）。よって、上述した自己訂正処理を複数回繰り返し、ステップＳ４０４ｕで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、後述するように、設定によっては圧倒的な確率でｍ’＝ｕｂ’ｖａ’＝ｆ（ｘ）となる。その場合にはステップＳ４０４ｕで得られた値をそのまま復号結果としてよい。
【００７６】
≪高い確率でｕｂ’ｖａ’＝ｆ（ｘ）となる理由について≫
Ｘを群Ｇに値を持つ確率変数とする。ｗ∈Ｇについて、要求を受けるたびに確率変数Ｘに従った標本ｘ’に対応するｗｘ’を返すものを、ｗについて誤差Ｘを持つ標本器（ｓａｍｐｌｅｒ）と呼ぶ。
【００７７】
ｗ∈Ｇについて、自然数ａが与えられるたびに確率変数Ｘに従った標本ｘ’に対応するｗａｘ’を返すものを、ｗについて誤差Ｘを持つ乱数化可能標本器（ｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒ）と呼ぶ。乱数化可能標本器はａ＝１として用いられれば標本器として機能する。
【００７８】
本実施形態の入力情報提供部４１６ｄ−ｕと第一出力情報計算部４２６１ａ−ｋと第一計算部４１６ｅ−ｕとの組み合わせが、ｆ（ｘ）について誤差Ｘ１を持つ乱数化可能標本器（「第一乱数化可能標本器」と呼ぶ）であり、入力情報提供部４１６ｄ−ｕと第二出力情報計算部４２６１ｂ−ｋと第二計算部４１６ｈ−ｕとの組み合わせが、ｆ（ｘ）について誤差Ｘ２を持つ乱数化可能標本器（「第二乱数化可能標本器」と呼ぶ）である。
【００７９】
ｕ’＝ｖ’が成立するのは、すなわちｕａ＝ｖｂが成立するのは、第一乱数化可能標本器がｕ＝ｆ（ｘ）ｂを正しく計算しており、第二乱数化可能標本器がｖ＝ｆ（ｘ）ａを正しく計算している（ｘ１及びｘ２が群Ｇの単位元ｅｇである）可能性が高いことを発明者は見出した。
【００８０】
第一乱数化可能標本器がｕ＝ｆ（ｘ）ｂを正しく計算しており、第二乱数化可能標本器がｖ＝ｆ（ｘ）ａを正しく計算しているとき（ｘ１及びｘ２が群Ｇの単位元ｅｇであるとき）、ｕｂ’ｖａ’＝（ｆ（ｘ）ｂｘ１）ｂ’（ｆ（ｘ）ａｘ２）ａ’＝（ｆ（ｘ）ｂｅｇ）ｂ’（ｆ（ｘ）ａｅｇ）ａ’＝ｆ（ｘ）ｂｂ’ｅｇｂ’ｆ（ｘ）ａａ’ｅｇａ’＝ｆ（ｘ）（ｂｂ’＋ａａ’）＝ｆ（ｘ）となる。
【００８１】
また、（ｑ１，ｑ２）∈Ｉについて、ｉ＝１，２の各々について関数πｉをπｉ（ｑ１，ｑ２）＝ｑｉで定義する。さらに、Ｌ＝ｍｉｎ（♯π１（Ｓ），♯π２（Ｓ））とする。♯・は、集合・の位数である。群Ｇが巡回群や位数の計算が困難な群であるときには、復号処理部４１６−ｕが「⊥」以外を出力するときの出力がｆ（ｘ）ではない確率は、無視できる程度の誤差の範囲で高々Ｔｍａｘ２Ｌ／♯Ｓ程度と期待することができる。もしＬ／♯Ｓが無視できる量でＴｍａｘが多項式オーダー程度の量であれば、復号処理部４１６−ｕは圧倒的な確率で正しいｆ（ｘ）を出力する。Ｌ／♯Ｓが無視できる量になるようなＳの例には、例えばＳ＝｛（１，ｄ）｜ｄ∈［２，｜Ｇ｜−１］｝がある。
【００８２】
＜第四実施形態の特徴＞
本形態でも端末装置４１−ｕに対する制御を行うことなく、登録許可情報記憶部４２１−ｋに格納された固有公開情報ＰＴ（ｕ）を削除することで、削除した固有公開情報ＰＴ（ｕ）に対応する端末装置４１−ｕが暗号文Ｃの復号結果を閲覧する権限を無効化できる。
【００８３】
また、端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。
【００８４】
さらに本形態では、自己訂正技術を用いて復号を行うため、信頼できる鍵装置が設定されていない場合や、信頼できるか否かが定かではない複数の鍵装置しか存在しない場合であっても運用可能である。なお、上述した自己訂正処理は１つの端末装置と１つの鍵装置との間で実行していたが、１つの端末装置が複数の鍵装置と自己訂正処理を実行してもよい。
【００８５】
［第五実施形態］
第五実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した例である。以下、第四実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。以下の説明において、同一の参照番号が付された部分は同一の機能を持つものとし、同一の参照番号が付されたステップは同一の処理を表すものとする。
【００８６】
＜構成＞
図８に例示するように第五実施形態の復号システム５は、第四実施形態の端末装置４１−ｕ（ｕ＝１，・・・，Ｕ）が端末装置５１−ｕ（ｕ＝１，・・・，Ｕ）に置換され、鍵装置４２−ｋ（ｋ＝１，・・・，Ｋ）が鍵装置５２−ｋ（ｋ＝１，・・・，Ｋ）に置換されたものである。図１０に例示するように、端末装置５１−ｕは、第四実施形態の復号処理部４１６−ｕが復号処理部５１６−ｕに置換されたものである。鍵装置５２−ｋは、第四実施形態の判定復号部４２６１−ｋ及び暗号化部４２６２−ｋを含む復号部４２６−ｋが、判定復号部５２６１−ｋ及び暗号化部４２６２−ｋを含む復号部５２６−ｋに置換されたものである。
【００８７】
図１１に例示するように、第五実施形態の復号処理部５１６−ｕは、例えば、自然数記憶部４１６ａ−ｕと自然数選択部４１６ｂ−ｕと整数計算部４１６ｃ−ｕと入力情報提供部５１６ｄ−ｕと第一計算部５１６ｅ−ｕと第一べき乗計算部４１６ｆ−ｕと第一リスト記憶部４１６ｇ−ｕと第二計算部５１６ｈ−ｕと第二べき乗計算部４１６ｉ−ｕと第二リスト記憶部４１６ｊ−ｕと判定部４１６ｋ−ｕと最終出力部４１６ｍ−ｕと制御部４１６ｎ−ｕとを有する。図１３に例示するように、本形態の入力情報提供部５１６ｄ−ｕは、例えば、第一乱数生成部５１６ｄａ−ｕと第一入力情報計算部５１６ｄｂ−ｕと第二乱数生成部５１６ｄｃ−ｕと第二入力情報計算部５１６ｄｄ−ｕとを有する。
【００８８】
図１２に例示するように、第五実施形態の判定復号部５２６１−ｋは、例えば、第一出力情報計算部５２６１ａ−ｋと第二出力情報計算部５２６１ｂ−ｋと判定部４２６１ｃ−ｋと制御部４２６１ｎ−ｋとを有する。
【００８９】
＜自己訂正処理（ステップＳ５０４）＞
本形態ではステップＳ４０４の代わりに以下の自己訂正処理（ステップＳ５０４）が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第五実施形態では、復号関数ｆ（ｘ）を準同型関数とし、群Ｈの生成元をμｈ、群Ｈの位数をＫＨ、ν＝ｆ（μｈ）とする。その他の前提は、復号処理部４１６−ｕが復号処理部５１６−ｕに置換され、判定復号部４２６１−ｋが判定復号部５２６１−ｋに置換されている以外、第四実施形態と同一である。
【００９０】
図１６及び図１７に例示するように、第五実施形態の処理は第四形態のステップＳ４０４ｄ〜Ｓ４０４ｇ，Ｓ４０４ｉ，Ｓ４０４ｊ，Ｓ４０４ｎが、それぞれ、ステップＳ５０４ｄ〜Ｓ５０４ｇ，Ｓ５０４ｉ，Ｓ５０４ｊ，Ｓ５０４ｎに置換されたものである。以下ではステップＳ５０４ｄ〜Ｓ５０４ｇ，Ｓ５０４ｉ，Ｓ５０４ｊ，Ｓ５０４ｎの処理のみを説明する。
【００９１】
《ステップＳ５０４ｄの処理》
復号処理部５１６−ｕ（図１１）の入力情報提供部５１６ｄ−ｕは、入力された暗号文ｘにそれぞれ対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を生成して出力する（図１６／ステップＳ５０４ｄ）。以下、図１８を用いて本形態のステップＳ５０４ｄの処理を説明する。
【００９２】
第一乱数生成部５１６ｄａ−ｕ（図１３）は、０以上ＫＨ未満の自然数の一様乱数ｒ１を生成する。生成された乱数ｒ１は、第一入力情報計算部５１６ｄｂ−ｕ及び第一計算部５１６ｅ−ｕに送られる（ステップＳ５０４ｄａ）。第一入力情報計算部５１６ｄｂ−ｕは、入力された乱数ｒ１と暗号文ｘと自然数ｂとを用いて第一入力情報τ１＝μｈｒ１ｘｂを計算する（ステップＳ５０４ｄｂ）。ここで、μｈの右肩のｒ１は、ｒ１のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。
【００９３】
第二乱数生成部５１６ｄｃ−ｕは、０以上ＫＨ未満の自然数の一様乱数ｒ２を生成する。生成された乱数ｒ２は、第二入力情報計算部５１６ｄｄ−ｕ及び第二計算部５１６ｈ−ｕに送られる（ステップＳ５０４ｄｃ）。第二入力情報計算部５１６ｄｄ−ｕは、入力された乱数ｒ２と暗号文ｘと自然数ａとを用いて第二入力情報τ２＝μｈｒ２ｘａを計算する（ステップＳ５０４ｄｄ）。
【００９４】
第一入力情報計算部５１６ｄｂ−ｕ及び第二入力情報計算部５１６ｄｄ−ｕは、以上のように生成した第一入力情報τ１及び第二入力情報τ２を出力する。第一入力情報τ１及び第二入力情報τ２は出力部１１４−ｕ（図１０）から出力され、鍵装置５２−ｋの入力部４２３−ｋに入力され判定復号部５２６１−ｋに送られる（ステップＳ５０４ｄｅ）。なお、本形態の第一入力情報τ１及び第二入力情報τ２は、それぞれ、乱数ｒ１，ｒ２によって暗号文ｘとの関係をかく乱させた情報である。これにより、判定復号部５２６１−ｋは、暗号文ｘを判定復号部５２６１−ｋに対して隠蔽できる。また、本形態の第一入力情報τ１は自然数選択部４１６ｂ−ｕで選択された自然数ｂにさらに対応し、第二入力情報τ２は自然数選択部４１６ｂ−ｕで選択された自然数ａにさらに対応する。これにより、判定復号部５２６１−ｋから提供された復号能力を復号処理部５１６−ｕが高い精度で評価することが可能となる。
【００９５】
《ステップＳ５０４ｅ〜Ｓ５０４ｇの処理》
図１７に例示するように、まず、第一入力情報τ１＝μｈｒ１ｘｂが判定復号部５２６１−ｋ（図１２）の第一出力情報計算部５２６１ａ−ｋに入力され、第二入力情報τ２＝μｈｒ２ｘａが第二出力情報計算部５２６１ｂ−ｋに入力される（ステップＳ５０４ｅ）。
【００９６】
第一出力情報計算部５２６１ａ−ｋは、第一入力情報τ１＝μｈｒ１ｘｂと秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆ（μｈｒ１ｘｂ）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部５２６１ａ−ｋでの計算結果がｆ（μｈｒ１ｘｂ）となる場合もあれば、ｆ（μｈｒ１ｘｂ）とならない場合もある（ステップＳ５０４ｆ）。
【００９７】
第二出力情報計算部５２６１ｂ−ｋは、第二入力情報τ２＝μｈｒ２ｘａと秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆ（μｈｒ２ｘａ）を正しく計算し、得られた計算結果を第二出力情報ｚ２とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部５２６１ｂ−ｋでの計算結果がｆ（μｈｒ２ｘａ）となる場合もあれば、ｆ（μｈｒ２ｘａ）とならない場合もある（ステップＳ５０４ｇ）。
【００９８】
第一出力情報計算部５２６１ａ−ｋは第一出力情報ｚ１を出力し、第二出力情報計算部５２６１ｂ−ｋは第二出力情報ｚ２を出力する。
【００９９】
《ステップＳ５０４ｉ及びＳ５０４ｊの処理》
図１６に戻り、第四実施形態と同様に復号部４１７−ｕで暗号文Ｃｚを復号して得られた第一出力情報ｚ１は復号処理部５１６−ｕ（図１１）の第一計算部５１６ｅ−ｕに入力され、第二出力情報ｚ２は第二計算部５１６ｈ−ｕに入力される。これらの第一出力情報ｚ１及び第二出力情報ｚ２が、判定復号部５２６１−ｋから復号処理部５１６−ｕに与えられた復号能力に相当する（ステップＳ５０４ｉ）。
【０１００】
第一計算部５１６ｅ−ｕは、入力された乱数ｒ１及び第一出力情報ｚ１を用いてｚ１ν−ｒ１を計算してその計算結果をｕとする。計算結果ｕは、第一べき乗計算部４１６ｆ−ｕに送られる。ここで、ｕ＝ｚ１ν−ｒ１＝ｆ（ｘ）ｂｘ１となる。すなわち、ｚ１ν−ｒ１は、ｆ（ｘ）について誤差Ｘ１を持つ乱数化可能標本器となる。その理由については後述する（ステップ５０４ｊ）。
【０１０１】
《ステップＳ５０４ｎの処理》
第二計算部５１６ｈ−ｕは、入力された乱数ｒ２及び第二出力情報ｚ２を用いてｚ２ν−ｒ２を計算してその計算結果をｖとする。計算結果ｖは、第二べき乗計算部４１６ｉ−ｕに送られる。ここで、ｖ＝ｚ２ν−ｒ２＝ｆ（ｘ）ａｘ２となる。すなわち、ｚ２ν−ｒ２は、ｆ（ｘ）について誤差Ｘ２を持つ乱数化可能標本器となる。その理由については後述する（ステップＳ５０４ｎ）。
【０１０２】
≪ｚ１ν−ｒ１，ｚ２ν−ｒ２がｆ（ｘ）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器となる理由について≫
ｃを自然数、Ｒ及びＲ’を乱数として、判定復号部５２６１−ｋがμｈＲｘｃを用いて行う計算の計算結果をＢ（μｈＲｘｃ）とする。すなわち、第一出力情報計算部５２６１ａ−ｋや第二出力情報計算部５２６１ｂ−ｋが復号処理部５１６−ｕに返す計算結果をｚ＝Ｂ（μｈＲｘｃ）とする。さらに、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（μｈＲ’）ｆ（μｈＲ’）−１と定義する。
【０１０３】
このとき、ｚν−Ｒ＝Ｂ（μｈＲｘｃ）ｆ（μｈ）−Ｒ＝Ｘｆ（μｈＲｘｃ）ｆ（μｈ）−Ｒ＝Ｘｆ（μｈ）Ｒｆ（ｘ）ｃｆ（μｈ）−Ｒ＝ｆ（ｘ）ｃＸとなる。すなわち、ｚν−Ｒは、ｆ（ｘ）について誤差Ｘを持つ乱数化可能標本器となる。
【０１０４】
上記式展開において、Ｘ＝Ｂ（μｈＲ’）ｆ（μｈＲ’）−１＝Ｂ（μｈＲｘｃ）ｆ（μｈＲｘｃ）−１であり、Ｂ（μｈＲｘｃ）＝Ｘｆ（μｈＲｘｃ）であるという性質を用いている。この性質は、関数ｆ（ｘ）が準同型関数であり、Ｒ及びＲ’が乱数であることに基づく。
【０１０５】
したがって、ａ，ｂが自然数、ｒ１，ｒ２が乱数であることを考慮すると、同様に、ｚ１ν−ｒ１，ｚ２ν−ｒ２がｆ（ｘ）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器となるのである。
【０１０６】
［第六実施形態］
第六実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した他の例である。具体的には、Ｈ＝Ｇ×Ｇ、復号関数ｆ（ｘ）がＥｌＧａｍａｌ暗号の復号関数、すなわち秘密鍵ｓ（ｋ）及び暗号文ｘ＝（ｃ１，ｃ２）に対してｆ（ｃ１，ｃ２）＝ｃ１ｃ２−ｓである場合の第一乱数化可能標本器及び第二乱数化可能標本器の例を具体化したものである。以下、第四実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。
【０１０７】
＜構成＞
図８に例示するように第六実施形態の復号システム６は、第四実施形態の端末装置４１−ｕ（ｕ＝１，・・・，Ｕ）が端末装置６１−ｕ（ｕ＝１，・・・，Ｕ）に置換され、鍵装置４２−ｋ（ｋ＝１，・・・，Ｋ）が鍵装置６２−ｋ（ｋ＝１，・・・，Ｋ）に置換されたものである。図１０に例示するように、端末装置６１−ｕは、第四実施形態の復号処理部４１６−ｕが復号処理部６１６−ｕに置換されたものである。鍵装置６２−ｋは、第四実施形態の判定復号部４２６１−ｋ及び暗号化部４２６２−ｋを含む復号部４２６−ｋが、判定復号部６２６１−ｋ及び暗号化部４２６２−ｋを含む復号部６２６−ｋに置換されたものである。
【０１０８】
図１１に例示するように、第六実施形態の復号処理部６１６−ｕは、例えば、自然数記憶部４１６ａ−ｕと自然数選択部４１６ｂ−ｕと整数計算部４１６ｃ−ｕと入力情報提供部６１６ｄ−ｕと第一計算部６１６ｅ−ｕと第一べき乗計算部４１６ｆ−ｕと第一リスト記憶部４１６ｇ−ｕと第二計算部６１６ｈ−ｕと第二べき乗計算部４１６ｉ−ｕと第二リスト記憶部４１６ｊ−ｕと判定部４１６ｋ−ｕと最終出力部４１６ｍ−ｕと制御部４１６ｎ−ｕとを有する。図１４に例示するように、本形態の入力情報提供部６１６ｄ−ｕは、例えば、第四乱数生成部６１６ｄａ−ｕと第五乱数生成部６１６ｄｂ−ｕと第一入力情報計算部６１６ｄｃ−ｕと第六乱数生成部６１６ｄｄ−ｕと第七乱数生成部６１６ｄｅ−ｕと第二入力情報計算部６１６ｄｆ−ｕとを有する。第一入力情報計算部６１６ｄｃ−ｕは、例えば、第四入力情報計算部６１６ｄｃａ−ｕと第五入力情報計算部６１６ｄｃｂ−ｕとを有し、第二入力情報計算部６１６ｄｆ−ｕは、第六入力情報計算部６１６ｄｆａ−ｕと第七入力情報計算部６１６ｄｆｂ−ｕとを有する。
【０１０９】
図１２に例示するように、第六実施形態の判定復号部６２６１−ｋは、例えば、第一出力情報計算部６２６１ａ−ｋと第二出力情報計算部６２６１ｂ−ｋと制御部４２６１ｎ−ｋと判定部４２６１ｃ−ｋとを有する。
【０１１０】
＜自己訂正処理（ステップＳ６０４）＞
本形態ではステップＳ４０４の代わりに以下の自己訂正処理（ステップＳ６０４）が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第六実施形態では、群Ｈ＝Ｇ×Ｇ、暗号文ｘ＝Ｃ＝（ｃ１，ｃ２）∈Ｈであり、ｆ（ｃ１，ｃ２）が準同型関数であり、群Ｇの生成元をμｇとし、群Ｇの位数をＫＧとし、同じ秘密鍵ｓ（ｋ）に対する暗号文（Ｖ，Ｗ）∈Ｈとその暗号文を復号した復号文ｆ（Ｖ，Ｗ）＝Ｙ∈Ｇとの組が復号処理部６１６−ｕ及び判定復号部６２６１−ｋに事前設定され、復号処理部６１６−ｕ及び判定復号部６２６１−ｋがこの組を利用可能とされているものとする。
【０１１１】
図１６及び図１７に例示するように、第六実施形態の処理は第四形態のステップＳ４０４ｄ〜Ｓ４０４ｇ，Ｓ４０４ｉ，Ｓ４０４ｊ，Ｓ４０４ｎが、それぞれ、ステップＳ６０４ｄ〜Ｓ６０４ｇ，Ｓ６０４ｉ，Ｓ６０４ｊ，Ｓ６０４ｎに置換されたものである。以下ではステップＳ６０４ｄ〜Ｓ６０４ｇ，Ｓ６０４ｉ，Ｓ６０４ｊ，Ｓ６０４ｎの処理のみを説明する。
【０１１２】
《ステップＳ６０４ｄの処理》
復号処理部６１６−ｕ（図１１）の入力情報提供部６１６ｄ−ｕは、入力された暗号文ｘ＝（ｃ１，ｃ２）に対応する群Ｈの元である第一入力情報τ１及び暗号文ｘ＝（ｃ１，ｃ２）に対応する群Ｈの元である第二入力情報τ２を生成して出力する（図１６／ステップＳ６０４ｄ）。以下、図１９を用いて本形態のステップＳ６０４ｄの処理を説明する。
【０１１３】
第四乱数生成部６１６ｄａ−ｕ（図１４）は、０以上ＫＧ未満の自然数の一様乱数ｒ４を生成する。生成された乱数ｒ４は、第四入力情報計算部６１６ｄｃａ−ｕ、第五入力情報計算部６１６ｄｃｂ−ｕ、及び第一計算部６１６ｅ−ｕに送られる（ステップＳ６０４ｄａ）。第五乱数生成部６１６ｄｂ−ｕは、０以上ＫＧ未満の自然数の一様乱数ｒ５を生成する。生成された乱数ｒ５は、第五入力情報計算部６１６ｄｃｂ−ｕ、及び第一計算部６１６ｅ−ｕに送られる（ステップＳ６０４ｄｂ）。
【０１１４】
第四入力情報計算部６１６ｄｃａ−ｕは、自然数選択部４１６ｂ−ｕで選択された自然数ｂ、暗号文ｘが含むｃ２、及び乱数ｒ４を用い、第四入力情報ｃ２ｂＷｒ４を計算する（ステップＳ６０４ｄｃ）。第五入力情報計算部６１６ｄｃｂ−ｕは、自然数選択部４１６ｂ−ｕで選択された自然数ｂ、暗号文ｘが含むｃ１、及び乱数ｒ４，ｒ５を用い、第五入力情報ｃ１ｂＶｒ４μｇｒ５を計算する（ステップＳ６０４ｄｄ）。
【０１１５】
第六乱数生成部６１６ｄｄ−ｕは、０以上ＫＧ未満の自然数の一様乱数ｒ６を生成する。生成された乱数ｒ６は、第六入力情報計算部６１６ｄｆａ−ｕ、第七入力情報計算部６１６ｄｆｂ−ｕ、及び第二計算部６１６ｈ−ｕに送られる（ステップＳ６０４ｄｅ）。第七乱数生成部６１６ｄｅ−ｕは、０以上ＫＧ未満の自然数の一様乱数ｒ７を生成する。生成された乱数ｒ７は、第六入力情報計算部６１６ｄｆａ−ｕ、及び第二計算部６１６ｈ−ｕに送られる（ステップＳ６０４ｄｆ）。
【０１１６】
第六入力情報計算部６１６ｄｆａ−ｕは、自然数選択部４１６ｂ−ｕで選択された自然数ａ、暗号文ｘが含むｃ２、及び乱数ｒ６を用い、第六入力情報ｃ２ａＷｒ６を計算する（ステップＳ６０４ｄｇ）。第七入力情報計算部６１６ｄｆｂ−ｕは、自然数選択部４１６ｂ−ｕで選択された自然数ａ、暗号文ｘが含むｃ１、及び乱数ｒ７を用い、第七入力情報ｃ１ａＶｒ６μｇｒ７を計算する（ステップＳ６０４ｄｈ）。
【０１１７】
第一入力情報計算部６１６ｄｃ−ｕは、以上のように生成した第四入力情報ｃ２ｂＷｒ４及び第五入力情報ｃ１ｂＶｒ４μｇｒ５を第一入力情報τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）として出力する。第二入力情報計算部６１６ｄｆ−ｕは、以上のように生成した第六入力情報ｃ２ａＷｒ６及び第七入力情報ｃ１ａＶｒ６μｇｒ７を第二入力情報τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）として出力する（ステップＳ６０４ｄｉ）。
【０１１８】
第一入力情報τ１及び第二入力情報τ２は出力部１１４−ｕ（図１０）から出力され、鍵装置６２−ｋの入力部４２３−ｋに入力され判定復号部６２６１−ｋに送られる。
【０１１９】
《ステップＳ６０４ｅ〜Ｓ６０４ｇの処理》
図１７に例示するように、まず、第一入力情報τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）が判定復号部６２６１−ｋ（図１２）の第一出力情報計算部６２６１ａ−ｋに入力され、第二入力情報τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）が第二出力情報計算部６２６１ｂ−ｋに入力される（ステップＳ６０４ｅ）。
【０１２０】
第一出力情報計算部６２６１ａ−ｋは、第一入力情報τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）と秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）を正しく計算し、計算結果を第一出力情報ｚ１とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部６２６１ａ−ｋでの計算結果がｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）となる場合もあれば、ｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）とならない場合もある（ステップＳ６０４ｆ）。
【０１２１】
第二出力情報計算部６２６１ｂ−ｋは、第二入力情報τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）と秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）を正しく計算可能であり、得られた計算結果を第二出力情報ｚ２とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部６２６１ｂ−ｋでの計算結果がｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）となる場合もあれば、ｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）とならない場合もある（ステップＳ６０４ｇ）。
【０１２２】
第一出力情報計算部６２６１ａ−ｋは第一出力情報ｚ１を出力し、第二出力情報計算部６２６１ｂ−ｋは第二出力情報ｚ２を出力する。
【０１２３】
《ステップＳ６０４ｉ及びＳ６０４ｊの処理》
図１６に戻り、第四実施形態と同様に復号部４１７−ｕで暗号文Ｃｚを復号して得られた第一出力情報ｚ１は復号処理部６１６−ｕ（図１１）の第一計算部６１６ｅ−ｕに入力され、第二出力情報ｚ２は第二計算部６１６ｈ−ｕに入力される（ステップＳ６０４ｉ）。
【０１２４】
第一計算部６１６ｅ−ｕは、入力された第一出力情報ｚ１及び乱数ｒ４，ｒ５を用い、ｚ１Ｙ−ｒ４μｇ−ｒ５を計算してその計算結果をｕとする（ステップＳ６０４ｊ）。計算結果ｕは、第一べき乗計算部４１６ｆ−ｕに送られる。ここで、ｕ＝ｚ４Ｙ−ｒ４μｇ−ｒ５＝ｆ（ｃ１，ｃ２）ｂｘ１となる。すなわち、ｚ４Ｙ−ｒ４μｇ−ｒ５は、ｆ（ｃ１，ｃ２）について誤差Ｘ１を持つ乱数化可能標本器となる。その理由については後述する。
【０１２５】
《ステップＳ６０４ｎの処理》
第二計算部６１６ｈ−ｕは、入力された第二出力情報ｚ２及び乱数ｒ６，ｒ７を用い、ｚ２Ｙ−ｒ６μｇ−ｒ７を計算してその計算結果をｖとする（ステップＳ６０４ｎ）。計算結果ｖは、第二べき乗計算部４１６ｉ−ｕに送られる。ここで、ｖ＝ｚ５Ｙ−ｒ６μｇ−ｒ７＝ｆ（ｃ１，ｃ２）ａｘ２となる。すなわち、ｚ５Ｙ−ｒ６μｇ−ｒ７は、ｆ（ｃ１，ｃ２）について誤差Ｘ２を持つ乱数化可能標本器となる。その理由については後述する。
【０１２６】
≪ｚ４Ｙ−ｒ４μｇ−ｒ５，ｚ５Ｙ−ｒ６μｇ−ｒ７がｆ（ｃ１，ｃ２）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器となる理由について≫
ｃを自然数、Ｒ１、Ｒ２、Ｒ１’及びＲ２’を乱数として、判定復号部６２６１−ｋがｃ１ｃＶＲ１μｇＲ２及びｃ２ｃＷＲ１を用いて行う計算の計算結果をＢ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）とする。すなわち、第一出力情報計算部６２６１ａ−ｋや第二出力情報計算部６２６１ｂ−ｋが復号処理部６１６−ｕに返す計算結果をｚ＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）とする。さらに、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（ＶＲ１’μｇＲ２’，ＷＲ１’）ｆ（ＶＲ１’μｇＲ２’，ＷＲ１’）−１と定義する。
【０１２７】
このとき、ｚＹ−Ｒ１μｇ−Ｒ２＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１，ｃ２）ｃｆ（Ｖ，Ｗ）Ｒ１ｆ（μｇ，ｅｇ）Ｒ２Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１，ｃ２）ｃＹＲ１μｇＲ２Ｙ−Ｒ１μｇ−Ｒ２＝ｆ（ｃ１，ｃ２）ｃＸとなる。すなわち、ｚＹ−Ｒ１μｇ−Ｒ２は、ｆ（ｘ）について誤差Ｘを持つ乱数化可能標本器となる。なお、ｅｇは、群Ｇの単位元である。
【０１２８】
上記式展開において、Ｘ＝Ｂ（ＶＲ１’μｇＲ２’，ＷＲ１’）ｆ（ＶＲ１’μｇＲ２’，ＷＲ１’）−１＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）ｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）であり、Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）＝Ｘｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）であるという性質を用いている。この性質は、Ｒ１、Ｒ２、Ｒ１’及びＲ２’が乱数であることに基づく。
【０１２９】
したがって、ａ，ｂが自然数、ｒ４，ｒ５，ｒ６及びｒ７が乱数であることを考慮すると、同様に、ｚ４Ｙ−ｒ４μｇ−ｒ５，ｚ５Ｙ−ｒ６μｇ−ｒ７がｆ（ｃ１，ｃ２）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器となるのである。
【０１３０】
［第七実施形態］
第四〜六実施形態では、復号処理部の自然数記憶部４１６ａ−ｕに、互いに素である２つの自然数ａ，ｂの組（ａ，ｂ）が複数種類記憶され、これらの組（ａ，ｂ）を用いて各処理が実行されることとした。しかしながら、ａ，ｂの一方が定数であってもよい。例えば、ａが１に固定されていてもよいし、ｂが１に固定されていてもよい。言い換えると、第一乱数化可能標本器又は第二乱数化可能標本器の一方が標本器に置換されていてもよい。ａ，ｂの一方が定数である場合、定数とされたａ又はｂを選択する処理が不要となり、各処理部は定数とされたａ又はｂが入力されることなく、それを定数として扱って計算を行うことができる。また、定数とされたａ又はｂが１である場合には、ａ’やｂ’を用いることなく、ｆ（ｘ）＝ｕｂ’ｖａ’をｆ（ｘ）＝ｖ又はｆ（ｘ）＝ｕとして得ることができる。
【０１３１】
第七実施形態は、そのような変形の一例であり、ｂが１に固定され、第二乱数化可能標本器が標本器に置換された形態である。以下では、第四実施形態との相違点を中心に説明する。また、第一乱数化可能標本器の具体例は、第五実施形態および第六実施形態で説明したのと同様であるため、説明を省略する。
【０１３２】
＜構成＞
図８に例示するように第七実施形態の復号システム７は、第四実施形態の端末装置４１−ｕ（ｕ＝１，・・・，Ｕ）が端末装置７１−ｕ（ｕ＝１，・・・，Ｕ）に置換され、鍵装置４２−ｋ（ｋ＝１，・・・，Ｋ）が鍵装置７２−ｋ（ｋ＝１，・・・，Ｋ）に置換されたものである。図１０に例示するように、端末装置７１−ｕは、第四実施形態の復号処理部４１６−ｕが復号処理部７１６−ｕに置換されたものである。鍵装置７２−ｋは、第四実施形態の判定復号部４２６１−ｋ及び暗号化部４２６２−ｋを含む復号部４２６−ｋが、判定復号部７２６１−ｋ及び暗号化部４２６２−ｋを含む復号部７２６−ｋに置換されたものである。
【０１３３】
図２０に例示するように、第七実施形態の復号処理部７１６−ｕは、例えば、自然数記憶部７１６ａ−ｕと自然数選択部７１６ｂ−ｕと入力情報提供部７１６ｄ−ｕと第一計算部７１６ｅ−ｕと第一べき乗計算部７１６ｆ−ｕと第一リスト記憶部７１６ｇ−ｕと第二計算部７１６ｈ−ｕと第二リスト記憶部７１６ｊ−ｕと判定部７１６ｍ−ｕと最終出力部４１６ｍ−ｕと制御部４１６ｎ−ｕとを有する。
【０１３４】
図１２に例示するように、第七実施形態の判定復号部７２６１−ｋは、例えば、第一出力情報計算部７２６１ａ−ｋと第二出力情報計算部７２６１ｂ−ｋと制御部４２６１ｎ−ｋと判定部４２６１ｃ−ｋとを有する。
【０１３５】
＜自己訂正処理（ステップＳ７０４）＞
本形態ではステップＳ４０４の代わりに以下の自己訂正処理（ステップＳ７０４）が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第七実施形態では、Ｇ，Ｈを巡回群、ｆ（ｘ）を群Ｈの元である暗号文ｘ＝Ｃを特定の秘密鍵ｓ（ｋ）で復号して群Ｇの元を得るための復号関数、群Ｇ，Ｈの生成元をそれぞれμｇ，μｈ、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２とする。また、復号処理部７１６−ｕの自然数記憶部７１６ａ−ｕには、自然数ａが複数種類記憶されているものとする。
【０１３６】
図２１に例示するように、復号処理部７１６−ｕ（図２０）の自然数選択部７１６ｂ−ｕが、自然数記憶部７１６ａ−ｕに記憶された複数の自然数ａから１つの自然数ａをランダムに読み込む。読み込まれた自然数ａの情報は、入力情報提供部７１６ｄ−ｕ及び第一べき乗計算部７１６ｆ−ｕに送られる（ステップＳ７０４ａ）。
【０１３７】
制御部４１６ｎ−ｕは、ｔ＝１とする（ステップＳ７０４ｂ）。
【０１３８】
入力情報提供部７１６ｄ−ｕは、入力された暗号文ｘにそれぞれ対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を生成して出力する。好ましくは、第一入力情報τ１及び第二入力情報τ２はそれぞれ暗号文ｘとの関係をかく乱させた情報である。これにより、復号処理部７１６−ｕは、暗号文ｘを判定復号部７２６１−ｋに対して隠蔽できる。また、好ましくは、本形態の第二入力情報τ２は自然数選択部７１６ｂ−ｕで選択された自然数ａにさらに対応する。これにより、判定復号部７２６１−ｋから提供された復号能力を復号処理部７１６−ｕが高い精度で評価することが可能となる（ステップＳ７０４ｄ）。第一入力情報τ１及び第二入力情報τ２の組みの具体例は、第五実施形態および第六実施形態の何れかのｂ＝１とした第一入力情報τ１及び第二入力情報τ２の組みである。第一入力情報τ１及び第二入力情報τ２は出力部１１４−ｕ（図１０）から出力され、鍵装置７２−ｋの入力部４２３−ｋに入力され判定復号部７２６１−ｋに送られる。図１７に例示するように、第一入力情報τ１は判定復号部７２６１−ｋ（図１２）の第一出力情報計算部７２６１ａ−ｋに入力され、第二入力情報τ２は第二出力情報計算部７２６１ｂ−ｋに入力される（ステップＳ７０４ｅ）。
【０１３９】
第一出力情報計算部７２６１ａ−ｋは、第一入力情報τ１と秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする（ステップＳ７０４ｆ）。第二出力情報計算部７２６１ｂ−ｋは、第二入力情報τ２と秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた計算結果を第二出力情報ｚ２とする（ステップＳ７０４ｇ）。すなわち、第一出力情報計算部７２６１ａ−ｋや第二出力情報計算部７２６１ｂ−ｋは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部７２６１ａ−ｋでの計算結果がｆ（τ１）の場合もあればｆ（τ１）でない場合もあり、第二出力情報計算部７２６１ｂ−ｋでの計算結果がｆ（τ２）の場合もあればｆ（τ２）でない場合もある。第一出力情報ｚ１及び第二出力情報ｚ２の組の具体例は、第五実施形態および第六実施形態の何れかのｂ＝１とした第一出力情報ｚ１及び第二出力情報ｚ２の組である。
【０１４０】
第一出力情報計算部７２６１ａ−ｋは第一出力情報ｚ１を出力し、第二出力情報計算部７２６１ｂ−ｋは第二出力情報ｚ２を出力する。第一出力情報ｚ１および第二出力情報ｚ２は第四実施形態と同様に暗号化部４２６２−ｋで暗号化され、出力部４２４−ｋは、第一入力情報τ１及び第二入力情報τ２を送信した端末装置４１−ｕに対して暗号文Ｃｚを出力する（ステップＳ４０４ｈ）。
【０１４１】
図２１に戻り、第四実施形態と同様に復号部４１７−ｕで暗号文Ｃｚを復号して得られた第一出力情報ｚ１は復号処理部７１６−ｕ（図２０）の第一計算部７１６ｅ−ｕに入力され、第二出力情報ｚ２は第二計算部７１６ｈ−ｕに入力される。これらの第一出力情報ｚ１及び第二出力情報ｚ２が、判定復号部７２６１−ｋから復号処理部７１６−ｕに与えられた復号能力に相当する（ステップＳ７０４ｉ）。
【０１４２】
第一計算部７１６ｅ−ｕは、第一出力情報ｚ１から計算結果ｕ＝ｆ（ｘ）ｘ１を生成する。計算結果ｕの具体例は、第五実施形態および第六実施形態の何れかのｂ＝１とした計算結果ｕである。計算結果ｕは第一べき乗計算部７１６ｆ−ｕに送られる（ステップＳ７０４ｊ）。
【０１４３】
第一べき乗計算部７１６ｆ−ｕはｕ’＝ｕａを計算する。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部４１６ｇ−ｕに記憶される（ステップＳ７０４ｋ）。
【０１４４】
第二計算部７１６ｈ−ｕは、第二出力情報ｚ２から計算結果ｖ＝ｆ（ｘ）ａｘ２を生成する。計算結果ｖの具体例は、第五実施形態および第六実施形態の何れかの計算結果ｖである。計算結果ｖは第二リスト記憶部７１６ｊ−ｕに記憶される（ステップＳ７０４ｎ）。
【０１４５】
判定部７１６ｍ−ｕは、第一リスト記憶部４１６ｇ−ｕに記憶された組（ｕ，ｕ’）及び第二リスト記憶部７１６ｊ−ｕに記憶されたｖの中で、ｕ’＝ｖとなるものがあるか判定する（ステップＳ７０４ｑ）。ｕ’＝ｖとなるものがあった場合には、ステップ７０４ｕ進む。ｕ’＝ｖとなるものがなかった場合には、ステップＳ４０４ｒに進む。
【０１４６】
ステップＳ４０４ｒでは、制御部４１６ｎ−ｕがｔ＝Ｔｍａｘであるか判定する（ステップＳ４０４ｒ）。Ｔｍａｘは予め定められた自然数である。ｔ＝Ｔｍａｘであれば、制御部４１６ｎ−ｕは、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ４０４ｔ）、処理を終える。ｔ＝Ｔｍａｘでない場合には、制御部４１６ｎ−ｕは、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ４０４ｓ）、ステップＳ７０４ｄに戻る。
【０１４７】
ステップＳ７０４ｕでは、最終出力部４１６ｍ−ｕが、ｕ’＝ｖであると判定されたｕ’に対応するｕを復号結果ｍ’として出力する（ステップＳ７０４ｕ）。このように得られたｕは、第四実施形態から第六実施形態でｂ＝１とした場合のｕｂ’ｖａ’に相当する。すなわち、このように得られたｕは高い確率で暗号文ｘを特定の秘密鍵ｓ（ｋ）で復号した復号結果ｆ（ｘ）＝ｍ’となる。よって、上述した処理を複数回繰り返し、ステップＳ７０４ｕで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、後述するように、設定によっては圧倒的な確率でｕ＝ｆ（ｘ）＝ｍ’となる。その場合にはステップＳ７０４ｕで得られた値をそのまま復号結果としてよい。
【０１４８】
≪復号結果ｆ（ｘ）が得られる理由について≫
次に、本形態の復号処理部７１６−ｕで復号結果ｆ（ｘ）が得られる理由を説明する。まず、説明に必要な事項を定義する。
【０１４９】
ブラックボックス（ｂｌａｃｋ−ｂｏｘ）：
ｆ（τ）のブラックボックスＦ（τ）とは、τ∈Ｈを入力としてｚ∈Ｇを出力する処理部を意味する。本形態では、第一出力情報計算部７２６１ａ−ｋ及び第二出力情報計算部７２６１ｂ−ｋが、それぞれ復号関数ｆ（τ）のブラックボックスＦ（τ）に相当する。群Ｈから任意に選択された元τ∈ＵＨ及びｚ＝Ｆ（τ）に対してｚ＝ｆ（τ）を満たす確率がδ（０＜δ≦１）よりも大きい場合、すなわち、
Ｐｒ［ｚ＝ｆ（τ）｜τ∈ＵＨ，ｚ＝Ｆ（τ）］＞δ      …（１）
を満たすｆ（τ）のブラックボックスＦ（τ）のことを、信頼性δ（δ−ｒｅｌｉａｂｌｅ）のｆ（τ）のブラックボックスＦ（τ）という。なお、δは正の値であり、前述した「或る確率」に相当する。
【０１５０】
自己訂正器（ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘ）とは、ｘ∈Ｈを入力とし、ｆ（τ）のブラックボックスＦ（τ）を用いて計算を行い、ｊ∈Ｇ∪⊥を出力する処理部を意味する。本形態では、復号処理部７１６−ｕが自己訂正器ＣＦ（ｘ）に相当する。
【０１５１】
オールモスト自己訂正器（ａｌｍｏｓｔ  ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘ）が、ｘ∈Ｈを入力とし、δ−ｒｅｌｉａｂｌｅのｆ（τ）のブラックボックスＦ（τ）を用い、正しい値ｊ＝ｆ（ｘ）を出力する確率が、誤った値ｊ≠ｆ（ｘ）を出力する確率よりも十分大きい場合を想定する。すなわち、
Ｐｒ［ｊ＝ｆ（ｘ）｜ｊ＝ＣＦ（ｘ），ｊ≠⊥］
＞Ｐｒ［ｊ≠ｆ（ｘ）｜ｊ＝ＣＦ（ｘ），ｊ≠⊥］＋Δ      …（２）
を満たす場合を想定する。なお、Δは或る正の値（０＜Δ＜１）である。このような場合、自己訂正器ＣＦ（ｘ）はオールモスト自己訂正器であるという。例えば、或る正の値Δ’（０＜Δ’＜１）に対して
Ｐｒ［ｊ＝ｆ（ｘ）｜ｊ＝ＣＦ（ｘ）］＞（１／３）＋Δ’
Ｐｒ［ｊ＝⊥｜ｊ＝ＣＦ（ｘ）］＜１／３
Ｐｒ［ｊ≠ｆ（ｘ）かつｊ≠⊥｜ｊ＝ＣＦ（ｘ）］＜１／３
を満たす場合、自己訂正器ＣＦ（ｘ）はオールモスト自己訂正器である。Δ’の例はΔ’＝１／１２や１／３である。
【０１５２】
ローバスト自己訂正器（ｒｏｂｕｓｔ  ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘ）が、ｘ∈Ｈを入力とし、δ−ｒｅｌｉａｂｌｅのｆ（τ）のブラックボックスＦ（τ）を用い、正しい値ｊ＝ｆ（ｘ）又はｊ＝⊥を出力する確率が圧倒的である場合を想定する。すなわち、無視することができる誤差ξ（０≦ξ＜１）に対して
Ｐｒ［ｊ＝ｆ（ｘ）またはｊ＝⊥｜ｊ＝ＣＦ（ｘ）］＞１−ξ      …（３）
を満たす場合を想定する。このような場合、自己訂正器ＣＦ（ｘ）はローバスト自己訂正器であるという。なお、無視することができる誤差ξの例は、セキュリティパラメータｋの関数値ξ（ｋ）である。関数値ξ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きいｋに対して｛ξ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数値ξ（ｋ）の具体例は、ξ（ｋ）＝２−ｋやξ（ｋ）＝２−√ｋなどである。
【０１５３】
また、オールモスト自己訂正器からローバスト自己訂正器を構成することができる。すなわち、同一のｘに対してオールモスト自己訂正器を複数回実行させ、⊥を除いて最も頻度が高い出力値をｊとすることで、ローバスト自己訂正器を構成できる。例えば、同一のｘに対してオールモスト自己訂正器をＯ（ｌｏｇ（１／ξ））回実行させ、最も頻度が高い出力値をｊとすることで、ローバスト自己訂正器を構成できる。なお、Ｏ（・）はオー記法を表す。
【０１５４】
擬似自由（ｐｓｅｕｄｏ−ｆｒｅｅ）な作用：
群Ｇ、自然数の集合Ω＝｛０，．．．，Ｍ｝（Ｍは１以上の自然数）、群Ｇに値を持つ確率変数Ｘ１，Ｘ２の各実現値α∈Ｘ１（α≠ｅｇ），β∈Ｘ２、及びａ∈Ωについて、αａ＝βとなる確率
Ｐｒ［αａ＝βかつα≠ｅｇ｜ａ∈ＵΩ，α∈Ｘ１，β∈Ｘ２］      …（４）
について、あらゆる可能なＸ１，Ｘ２に関する上限値を、組（Ｇ，Ω）の疑似自由指標とよび、これをＰ（Ｇ，Ω）と表すことにする。ある無視することができる関数ζ（ｋ）が存在して、
Ｐ（Ｇ，Ω）＜ζ（ｋ）      …（５）
である場合、組（Ｇ，Ω）によって定義される演算は擬似自由な作用であるという。なお、第５実施形態では群で定義された演算を乗法的に表現する。すなわちα∈Ｇに対する「αａ」は、群Ｇで定義された演算をαに対してａ回作用させることを意味する。また、無視することができる関数ζ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きいｋに対して｛ζ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数ζ（ｋ）の具体例は、ζ（ｋ）＝２−ｋやζ（ｋ）＝２−√ｋなどである。例えば、セキュリティパラメータｋとに対し、式（４）の確率がＯ（２−k）未満である場合、組（Ｇ，Ω）によって定義される演算は擬似自由な作用である。また、例えば、任意のα∈Ｇでα≠ｅｇであるものについて、集合Ω・α＝｛ａ（α）｜ａ∈Ω｝の要素数｜Ω・α｜が２ｋを超える場合、組（Ｇ，Ω）によって定義される演算は擬似自由な作用といえる。このような具体例は数多く存在する。例えば、群Ｇが素数ｐを法とする剰余群Ｚ／ｐＺであり、素数ｐが２ｋのオーダーであり、集合Ω＝｛０，．．．，ｐ−２｝であり、ａ（α）がαａ∈Ｚ／ｐＺであり、α≠ｅｇである場合、Ω・α＝｛αａ｜ａ＝０，．．．，ｐ−２｝＝｛ｅｇ，α１，．．．，αｐ−２｝となり、｜Ω・α｜＝ｐ−１である。素数ｐが２ｋのオーダーであるため、ある定数Ｃが存在して、ｋが十分大きければ｜Ω・α｜＞Ｃ２ｋを満たす。ここで式（４）の確率はＣ−１２−ｋ未満であり、このような組（Ｇ，Ω）によって定義される演算は擬似自由な作用である。
【０１５５】
信頼性δγ（δγ−ｒｅｌｉａｂｌｅ）の乱数化可能標本器：
自然数ａが与えられるたびに、δ−ｒｅｌｉａｂｌｅのｆ（τ）のブラックボックスＦ（τ）を用い、ｗ∈Ｇについて、確率変数Ｘに従った標本ｘ’に対応するｗａｘ’を返す乱数化可能標本器であって、ｗａｘ’＝ｗａである確率がδγよりも大きい（γは正定数）、すなわち、
Ｐｒ［ｗａｘ’＝ｗａ］＞δγ      …（６）
を満たすものを、信頼性δγの乱数化可能標本器という。本形態の入力情報提供部７１６ｄ−ｕと第二出力情報計算部７２６１ｂ−ｋと第二計算部７１６ｈ−ｕとの組は、ｗ＝ｆ（ｘ）について、信頼性δγの乱数化可能標本器である。
【０１５６】
次に、これらの定義を用い、本形態の復号処理部７１６−ｕで復号結果ｆ（ｘ）が得られる理由を説明する。
【０１５７】
本形態のステップＳ７０４ｑではｕ’＝ｖであるか、すなわち、ｕａ＝ｖであるかを判定している。本形態の入力情報提供部７１６ｄ−ｕと第二出力情報計算部７２６１ｂ−ｋと第二計算部７１６ｈ−ｕとの組は信頼性δγの乱数化可能標本器であるため（式（６））、Ｔｍａｘをｋ、δ、γから定まる一定値よりも大きい値とすれば、漸近的に大きい確率でｕａ＝ｖが成立する（ステップＳ７０４ｑでｙｅｓとなる）場合が生じる。たとえば、Ｔｍａｘ≧４／δγとすれば、ｕａ＝ｖが成立する（ステップＳ７０４ｑでｙｅｓとなる）確率は１／２よりも大きいことがＭａｒｋｏｖの不等式によってわかる。
【０１５８】
また、本形態ではｕ＝ｆ（ｘ）ｘ１及びｖ＝ｆ（ｘ）ａｘ２なのであるから、ｕａ＝ｖが成立する場合にはｘ１ａ＝ｘ２が成立する。ｘ１ａ＝ｘ２が成立する場合には、ｘ１＝ｘ２＝ｅｇである場合とｘ１≠ｅｇである場合とがある。ｘ１＝ｘ２＝ｅｇである場合には、ｕ＝ｆ（ｘ）となるのであるから、ステップＳ７０４ｕで出力されるｕは正しい復号結果ｆ（ｘ）となる。一方、ｘ１≠ｅｇである場合には、ｕ≠ｆ（ｘ）となるのであるから、ステップＳ７０４ｕで出力されるｕは正しい復号結果ｆ（ｘ）ではない。
【０１５９】
群Ｇと自然数ａが属する集合Ωとの組（Ｇ，Ω）によって定義される演算が擬似自由な作用であるか、疑似自由指標Ｐ（Ｇ，Ω）についてＴｍａｘ２Ｐ（Ｇ，Ω）が漸近的に小さい場合、ｕａ＝ｖの場合にｘ１≠ｅｇである確率（式（４））は漸近的に小さい。したがって、ｕａ＝ｖの場合にｘ１＝ｅｇである確率は漸近的に大きい。よって、組（Ｇ，Ω）によって定義される演算が擬似自由な作用であるか、Ｔｍａｘ２Ｐ（Ｇ，Ω）が漸近的に小さい場合、ｕａ＝ｖの場合に誤った復号結果ｆ（ｘ）が出力される確率は、ｕａ＝ｖの場合に正しい復号結果ｆ（ｘ）が出力される確率よりも十分小さい。この場合の復号処理部７１６−ｕはオールモスト自己訂正器であるといえる（式（２）参照）。そのため、前述のように、復号処理部７１６−ｕからローバスト自己訂正器を構成することが可能であり、圧倒的な確率で正しい復号結果ｆ（ｘ）を得ることができる。（Ｇ，Ω）で定義される演算が疑似自由な作用である場合には、ｕａ＝ｖの場合に誤った復号結果ｆ（ｘ）が出力される確率も無視できる。この場合の復号処理部７１６−ｕは、圧倒的な確率で正しい復号結果ｆ（ｘ）または⊥を出力する。
【０１６０】
なお、任意の定数ρに対してｋ０が定まり、このｋ０に対してｋ０＜ｋ’を満たす任意のｋ’に対する関数値η（ｋ’）がρ未満となる場合「η（ｋ’）が漸近的に小さい」という。ｋ’の例はセキュリティパラメータｋである。
【０１６１】
また、任意の定数ρに対してｋ０が定まり、このｋ０に対してｋ０＜ｋ’を満たす任意のｋ’に対する関数値１−η（ｋ’）がρ未満となる場合「η（ｋ’）が漸近的に大きい」という。
【０１６２】
《信頼性δγの乱数化可能標本器と安全性について》
以下のような攻撃を想定する。
【０１６３】
・ブラックボックスＦ（τ）又はその部分が意図的に不正なｚを出力する、又は、ブラックボックスＦ（τ）から出力された値が不正なｚに改ざんされる。
【０１６４】
・不正なｚに対応するｗａｘ’が乱数化可能標本器から出力される。
【０１６５】
・不正なｚに対応するｗａｘ’は、自己訂正器ＣＦ（ｘ）でｕａ＝ｖが成立する（ステップＳ７０４ｑでｙｅｓなる）にもかかわらず、自己訂正器ＣＦ（ｘ）が誤った値を出力する確率を増加させる。
【０１６６】
このような攻撃は、与えられた自然数ａに対して乱数化可能標本器から出力されたｗａｘ’の誤差の確率分布Ｄａ＝ｗａｘ’ｗ−ａが自然数ａに依存する場合に可能となる。例えば、第二計算部７１６ｈ−ｕから出力されるｖがｆ（ｘ）ａｘ１ａとなるような不正が行われた場合、ｘ１の値にかかわらず、必ずｕａ＝ｖが成立することになる。よって、乱数化可能標本器は、与えられた自然数ａに対して乱数化可能標本器から出力されたｗａｘ’の誤差の確率分布Ｄａ＝ｗａｘ’ｗ−ａが当該自然数ａに依存しないことが望ましい。
【０１６７】
あるいは、集合Ωのいかなる元ａ∈∀Ωについても、ｗａｘ’の誤差の確率分布Ｄａ＝ｗａｘ’ｗ−ａと区別することができない群Ｇに値を持つ確率分布Ｄが存在する（確率分布Ｄａと確率分布Ｄとが統計的に近似する（ｓｔａｔｉｓｔｉｃａｌｌｙ−ｃｌｏｓｅ））乱数化可能標本器であることが望ましい。なお、確率分布Ｄは自然数ａに依存しない。また、確率分布Ｄａと確率分布Ｄとを区別することができないとは、多項式時間アルゴリズムによって確率分布Ｄａと確率分布Ｄとを区別することができないことを意味し、例えば、無視することができるζ（０≦ζ＜１）に対して
Σｇ∈Ｇ｜Ｐｒ［ｇ∈Ｄ］−Ｐｒ［ｇ∈Ｄａ］｜＜ζ      …（７）
を満たすならば、多項式時間アルゴリズムによって確率分布Ｄａと確率分布Ｄとを区別することができない。無視することができるζの例は、セキュリティパラメータｋの関数値ζ（ｋ）である。関数値ζ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きなｋに対して｛ζ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数値ζ（ｋ）の具体例は、ζ（ｋ）＝２−ｋやζ（ｋ）＝２−√ｋなどである。また、これらの点は自然数ａ及びｂを使用する第四実施形態から第六実施形態についても同様である。
【０１６８】
［第八実施形態］
第八実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した他の例である。本形態は、格子暗号の一種であるGHV暗号化方式（参考文献１「C. Genrty, S. Halevi and V. Vaikuntanathan, “A Simple BGNType Cryptosystem from LWE,”Advances in Cryptology - EUROCRYPT 2010, LNCS 6110, pp.506-522, Springer-Verlag, 2010.」等参照）の復号処理に本発明を適用する形態である。以下では、第四実施形態との相違点を中心に説明する。
【０１６９】
＜構成＞
図８に例示するように第八実施形態の復号システム８は、第四実施形態の端末装置４１−ｕ（ｕ＝１，・・・，Ｕ）が端末装置８１−ｕ（ｕ＝１，・・・，Ｕ）に置換され、鍵装置４２−ｋ（ｋ＝１，・・・，Ｋ）が鍵装置８２−ｋ（ｋ＝１，・・・，Ｋ）に置換されたものである。図１０に例示するように、端末装置８１−ｕは、第四実施形態の復号処理部４１６−ｕが復号処理部８１６−ｕに置換されたものである。鍵装置８２−ｋは、第四実施形態の判定復号部４２６１−ｋ及び暗号化部４２６２−ｋを含む復号部４２６−ｋが、判定復号部８２６１−ｋ及び暗号化部４２６２−ｋを含む復号部８２６−ｋに置換されたものである。
【０１７０】
図２２に例示するように、第八実施形態の復号処理部８１６−ｕは、例えば、行列記憶部８１６ａ−ｕと行列選択部８１６ｂ−ｕと入力情報提供部８１６ｄ−ｕと第一計算部８１６ｅ−ｕと行列積計算部８１６ｆ−ｕと第一リスト記憶部８１６ｇ−ｕと第二計算部８１６ｈ−ｕと第二リスト記憶部８１６ｊ−ｕと判定部８１６ｋ−ｕと最終出力部８１６ｍ−ｕと制御部４１６ｎ−ｕとを有する。
【０１７１】
図２４に例示するように、本形態の入力情報提供部８１６ｄ−ｕは、例えば、第一ランダム行列選択部８１６ｄａ−ｕと第二ランダム行列選択部８１６ｄｂ−ｕと第一暗号化部８１６ｄｃ−ｕと第二暗号化部８１６ｄｄ−ｕと第一入力情報計算部８１６ｄｅ−ｕと第三ランダム行列選択部８１６ｄｆ−ｕと第四ランダム行列選択部８１６ｄｇ−ｕと第三暗号化部８１６ｄｈ−ｕと第四暗号化部８１６ｄｉ−ｕと第二入力情報計算部８１６ｄｊ−ｕとを有する。
【０１７２】
図２３に例示するように、第八実施形態の判定復号部８２６１−ｋは、例えば、第一出力情報計算部８２６１ａ−ｋと第二出力情報計算部８２６１ｂ−ｋと制御部４２６１ｎ−ｋと判定部４２６１ｃ−ｋを有する。
【０１７３】
＜自己訂正処理（ステップＳ８０４）＞
本形態ではステップＳ４０４の代わりに以下の自己訂正処理（ステップＳ８０４）が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。本形態では、ＧＭをι×ι行列の集合、ＨＭをι×ι行列の集合、暗号文ｘＭ＝ＣをＨＭの元、暗号文ｘＭ＝Ｃの復号結果がＧＭの元、ＭＸ１，ＭＸ２を集合ＧＭに値を持つ確率変数、Ｍｘ１を確率変数ＭＸ１の実現値、Ｍｘ２を確率変数ＭＸ２の実現値、ａＭを集合ＨＭの元とする。また本形態では、ｙ（ｋ）を暗号化鍵（公開鍵）であるι×κ行列、ｓ（ｋ）をｙ（ｋ）・ｓ（ｋ）＝０を満たすι×ι行列である復号鍵（秘密鍵）、ＣＭをκ×ι行列、ＮＭをι×ι行列、ＵＭをι×ι単位行列、ＰＴを集合ＧＭの元である平文ＰＴ∈ＧＭ、ｘＭを集合ＨＭの元である暗号文ｘＭ∈ＨＭ、ＥＮＣＭを集合ＧＭの元である平文ＰＴを暗号化して暗号文ｘＭ∈ＨＭを得るための暗号化関数、ｆＭ（ｘＭ）を暗号文ｘＭ∈ＨＭを特定の秘密鍵ｓ（ｋ）で復号して集合ＧＭの元である平文ＰＴを得るための復号関数とする。復号関数ｆＭ（ｘＭ）は準同型関数である。例えば、ＧＭをι×ι行列（Ｚ／２Ｚ）ι×ιの集合、ＨＭをι×ι行列（Ｚ／ｑＺ）ι×ιの集合、暗号化鍵ｙ（ｋ）をι×κ行列（Ｚ／ｑＺ）ι×κ、秘密鍵ｓ（ｋ）をι×ι行列（Ｚ／ｑＺ）ι×ι、ＣＭをランダムに選択されたκ×ι行列（Ｚ／ｑＺ）κ×ι、ＮＭをガウス分布に従うι×ι行列（Ｚ／ｑＺ）ι×ι、ＵＭをι×ι単位行列（Ｚ／２Ｚ）ι×ιとし、暗号化関数ＥＮＣＭ（ＰＴ）をｙ（ｋ）・ＣＭ＋２・ＮＭ＋ＰＴ（ｍｏｄ ｑ）とし、復号関数ｆＭ（ｘＭ）をｓ（ｋ）−１｛ｓ（ｋ）・ｘＭ・ｓ（ｋ）Ｔ（ｍｏｄ ｑ）｝（ｓ（ｋ）Ｔ）−１（ｍｏｄ ２）とする。ただし、κ，ι，ｑは正整数、κ，ι，ｑは正整数、・Ｔは・の転置行列、（Ｚ／ｑＺ）κ×ιはｑを法とする剰余環Ｚ／ｑＺを要素とするκ行ι列行列である。また、第八実施形態では行列α１，α２間の積をα１・α２と表し、和をα１＋α２と表現する。また、行列αの各要素を自然数β倍した行列をβ・αと表す。
【０１７４】
本形態の処理の前提として、復号処理部８１６−ｕ（図２２）の行列記憶部８１６ａ−ｕには、行列ａＭ∈ＨＭが複数種類記憶されているものとする。
【０１７５】
図２５に例示するように、まず、復号処理部８１６−ｕ（図２２）の行列選択部８１６ｂ−ｕが、行列記憶部８１６ａ−ｕに記憶された複数の行列から一様ランダムに１つの行列ａＭを選択して読み込む。読み込まれた行列ａＭの情報は、入力情報提供部８１６ｄ−ｕ及び行列積計算部８１６ｆ−ｕに送られる（ステップＳ８０４ａ）。
【０１７６】
制御部４１６ｎ−ｕは、ｔ＝１とする（ステップＳ８０４ｃ）。
【０１７７】
入力情報提供部８１６ｄ−ｕは、入力された暗号文ｘＭにそれぞれ対応する対応する集合ＨＭの元である第一入力情報Ｍτ１及び第二入力情報Ｍτ２を生成して出力する。好ましくは、第一入力情報Ｍτ１及び第二入力情報Ｍτ２はそれぞれ暗号文ｘＭとの関係をかく乱させた情報である。これにより、復号処理部８１６−ｕは暗号文ｘＭを判定復号部８２６１−ｋに対して隠蔽できる。また、第二入力情報Ｍτ２は元ａＭにさらに対応する。これにより、判定復号部８２６１−ｋから提供された復号能力を復号処理部８１６−ｕが高い精度で評価することが可能となる（ステップＳ８０４ｄ）。以下、図２７を用いてステップＳ８０４ｄの具体例を説明する。
【０１７８】
［ステップＳ８０４ｄの具体例］
入力情報提供部８１６ｄ−ｕ（図２４）の第一ランダム行列選択部８１６ｄａ−ｕが集合ＧＭの元ＭＲ１を一様ランダムに選択する（ステップＳ８０４ｄａ）。選択されたＭＲ１は第一暗号化部８１６ｄｃ−ｕと第一計算部８１６ｅ−ｕに送られる（ステップＳ８０４ｄａ）。第二ランダム行列選択部８１６ｄｂ−ｕがκ×ιの一様ランダムな行列ＣＭ１１及びＣＭ１２∈（Ｚ／ｑＺ）κ×ιを選択する。選択されたＣＭ１１及びＣＭ１２は第一入力情報計算部８１６ｄｅ−ｕに送られる（ステップＳ８０４ｄｂ）。第一暗号化部８１６ｄｃ−ｕが公開鍵ｙ（ｋ）を用い、ＭＲ１の暗号文ＥＮＣＭ（ｙ（ｋ），ＭＲ１）である第一暗号文ＣＲ１＝ｙ（ｋ）・ＣＭ＋２・ＮＭ＋ＭＲ１（ｍｏｄ ｑ）を生成する。第一暗号文ＣＲ１は第一入力情報計算部８１６ｄｅ−ｕに送られる（ステップＳ８０４ｄｃ）。第二暗号化部８１６ｄｄ−ｕが公開鍵ｙ（ｋ）を用い、単位行列ＵＭの暗号文ＥＮＣＭ（ｙ（ｋ），ＵＭ）である第二暗号文ＣＵＭ＝ｙ（ｋ）・ＣＭ＋２・ＮＭ＋ＵＭ（ｍｏｄ ｑ）を生成する。第二暗号文ＣＵＭは第一入力情報計算部８１６ｄｅ−ｕに送られる（ステップＳ８０４ｄｄ）。第一入力情報計算部８１６ｄｅ−ｕにはさらに暗号文ｘＭ＝Ｃが入力される。第一入力情報計算部８１６ｄｅ−ｕは、第一入力情報Ｍτ１として（ｘＭ・ＣＵＭ＋ＣＲ１）＋ｙ（ｋ）・ＣＭ１１＋２・ＮＭ＋ＣＭ１２Ｔ・ｙ（ｋ）Ｔを得て出力する。なお、行列の積の順序に特段の必然性はない。すなわち第一入力情報計算部８１６ｄｅ−ｕは、ＣＸ＝ｘＭ・ＣＵＭ＋ＣＲ１としたＲｅ（ＣＸ）＝ＣＸ＋ｙ（ｋ）・ＣＭ１１＋２・ＮＭ＋ＣＭ１２Ｔ・ｙ（ｋ）Ｔを計算して第一入力情報Ｍτ１を生成してもよいし、ＣＸ＝ＣＵＭ・ｘＭ＋ＣＲ１としたＲｅ（ＣＸ）を計算して第一入力情報Ｍτ１を生成してもよい（ステップＳ８０４ｄｅ）。
【０１７９】
第三ランダム行列選択部８１６ｄｆ−ｕが集合ＧＭの元ＭＲ２を一様ランダムに選択する。選択されたＭＲ２は第三暗号化部８１６ｄｈ−ｕと第二計算部８１６ｈ−ｕに送られる（ステップＳ８０４ｄｆ）。第四ランダム行列選択部８１６ｄｇ−ｕが、κ×ιのランダムな行列ＣＭ２１及びＣＭ２２∈（Ｚ／ｑＺ）κ×ιを選択する。選択されたＣＭ２１及びＣＭ２２は第二入力情報計算部８１６ｄｊ−ｕに送られる（ステップＳ８０４ｄｇ）。第三暗号化部８１６ｄｈ−ｕが公開鍵ｙ（ｋ）を用い、ＭＲ２の暗号文ＥＮＣＭ（ｙ（ｋ），ＭＲ２）である第三暗号文ＣＲ２＝ｙ（ｋ）・ＣＭ＋２・ＮＭ＋ＭＲ２（ｍｏｄ ｑ）を生成する。第三暗号文ＣＲ２は第二入力情報計算部８１６ｄｊ−ｕに送られる（ステップＳ８０４ｄｈ）。第四暗号化部６１０４ｉに行列ａＭが入力される。第四暗号化部６１０４ｉは公開鍵ｙ（ｋ）を用い、行列ａＭの暗号文ＥＮＣＭ（ｙ（ｋ），ａＭ）である第四暗号文Ｃａ＝ｙ（ｋ）・ＣＭ＋２・ＮＭ＋ａＭ（ｍｏｄ ｑ）を生成する。第四暗号文Ｃａは第二入力情報計算部８１６ｄｊ−ｕに送られる（ステップＳ８０４ｄｉ）。第二入力情報計算部８１６ｄｊ−ｕにはさらに暗号文ｘＭ＝Ｃが入力される。第二入力情報計算部８１６ｄｊ−ｕは、第二入力情報Ｍτ２として（ｘＭ・Ｃａ＋ＣＲ２）＋ｙ（ｋ）・ＣＭ２１＋２・ＮＭ＋ＣＭ２２Ｔ・ｙ（ｋ）Ｔを得て出力する。第二入力情報計算部８１６ｄｊ−ｕは、ＣＸ＝ｘＭ・Ｃａ＋ＣＲ２としたＲｅ（ＣＸ）を計算して第二入力情報Ｍτ２を生成してもよいし、ＣＸ＝ｘＭ・Ｃａ＋ＣＲ２としたＲｅ（ＣＸ）を計算して第二入力情報Ｍτ２を生成してもよい（（ステップＳ８０４ｄｊ）／［ステップＳ８０４ｄの具体例］の説明終わり）。
【０１８０】
第一入力情報Ｍτ１及び第二入力情報Ｍτ２は出力部１１４−ｕ（図１０）から出力され、鍵装置８２−ｋの入力部４２３−ｋに入力され判定復号部８２６１−ｋに送られる。図２６に例示するように、第一入力情報Ｍτ１は判定復号部８２６１−ｋ（図２３）の第一出力情報計算部８２６１ａ−ｋに入力され、第二入力情報Ｍτ２は第二出力情報計算部８２６１ｂ−ｋに入力される（ステップＳ８０４ｅ）。
【０１８１】
第一出力情報計算部８２６１ａ−ｋは、第一入力情報Ｍτ１と秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆＭ（Ｍτ１）＝ｓ（ｋ）−１｛ｓ（ｋ）・Ｍτ１・ｓ（ｋ）Ｔ（ｍｏｄ ｑ）｝（ｓ（ｋ）Ｔ）−１（ｍｏｄ ２）を正しく計算し、得られた計算結果を第一出力情報Ｍｚ１とする（ステップＳ８０４ｆ）。第二出力情報生成部６２０２は、第二入力情報Ｍτ２と秘密鍵記憶部４２２−ｋに格納された秘密鍵ｓ（ｋ）とを用い、或る確率より大きな確率でｆＭ（Ｍτ２）＝ｓ（ｋ）−１｛ｓ（ｋ）・Ｍτ２・ｓ（ｋ）Ｔ（ｍｏｄ ｑ）｝（ｓ（ｋ）Ｔ）−１（ｍｏｄ ２）を正しく計算し、得られた計算結果を第二出力情報Ｍｚ２とする（ステップＳ８０４ｇ）。すなわち、第一出力情報計算部８２６１ａ−ｋや第二出力情報計算部８２６１ｂ−ｋは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部８２６１ａ−ｋでの計算結果がｆＭ（Ｍτ１）の場合もあればｆＭ（Ｍτ１）でない場合もあり、第二出力情報計算部８２６１ｂ−ｋでの計算結果がｆＭ（Ｍτ２）の場合もあればｆＭ（Ｍτ２）でない場合もある。
【０１８２】
第一出力情報計算部８２６１ａ−ｋは第一出力情報Ｍｚ１を出力し、第二出力情報計算部８２６１ｂ−ｋは第二出力情報Ｍｚ２を出力する（ステップＳ８０４ｇ）。第一出力情報Ｍｚ１および第二出力情報Ｍｚ２は第四実施形態と同様に暗号化部４２６２−ｋで暗号化され、出力部４２４−ｋは、第一入力情報Ｍτ１及び第二入力情報Ｍτ２を送信した端末装置４１−ｕに対して第一出力情報Ｍｚ１および第二出力情報Ｍｚ２の暗号文Ｃｚを出力する（ステップＳ８０４ｈ）。
【０１８３】
図２５に戻り、第四実施形態と同様に復号部４１７−ｕで暗号文Ｃｚを復号して得られた第一出力情報Ｍｚ１は復号処理部８１６−ｕ（図２２）の第一計算部８１６ｅ−ｕに入力され、第二出力情報Ｍｚ２は第二計算部８１６ｈ−ｕに入力される。これらの第一出力情報Ｍｚ１及び第二出力情報Ｍｚ２が、判定復号部８２６１−ｋから復号処理部８１６−ｕに与えられた復号能力に相当する（ステップＳ８０４ｉ）。
【０１８４】
第一計算部７１６ｅ−ｕは、第一出力情報Ｍｚ１を用いてＭｚ１−ＭＲ１を計算してその計算結果をｕＭとする。計算結果ｕＭは行列積計算部８１６ｆ−ｕに送られる。ここで、ｕＭ＝Ｍｚ１−ＭＲ１＝ｆＭ（ｘＭ）＋Ｍｘ１となる。すなわち、ｕＭはｆＭ（ｘＭ）について誤差ＭＸ１を持つ標本器となる。その理由については後述する（ステップＳ８０４ｊ）。
【０１８５】
行列積計算部８１６ｆ−ｕはｕＭ’＝ｕＭ・ａＭを得る。なお、行列積計算部８１６ｆ−ｕはｕＭ・ａＭの計算によってｕＭ’を得てもよいし、ａＭ・ｕＭの計算によってｕＭ’を得てもよい。計算結果ｕＭとその計算結果に基づいて計算されたｕＭ’との組（ｕＭ，ｕＭ’）は、第一リスト記憶部８１６ｇ−ｕに記憶される（ステップＳ８０４ｋ）。
【０１８６】
第二計算部８１６ｈ−ｕは、第二出力情報Ｍｚ２を用いてＭｚ２−ＭＲ２を計算してその計算結果をｖＭとする。計算結果ｖＭは第二リスト記憶部８１６ｊ−ｕに記憶される。ここで、ｖＭ＝Ｍｚ２−ＭＲ２＝ｆＭ（ｘＭ）・ａＭ＋Ｍｘ２となる。すなわち、ｖＭはｆＭ（ｘＭ）について誤差ＭＸ２を持つ乱数化可能標本器となる。その理由については後述する（ステップＳ８０４ｎ）。
【０１８７】
判定部８１６ｋ−ｕは、第一リスト記憶部８１６ｇ−ｕに記憶された組（ｕＭ，ｕＭ’）及び第二リスト記憶部８１６ｊ−ｕに記憶されたｖＭの中で、ｕＭ’＝ｖＭとなるものがあるか判定する（ステップＳ８０４ｑ）。ｕＭ’＝ｖＭとなるものがあった場合には、ステップＳ８０４ｕに進む。ｕＭ’＝ｖＭとなるものがなかった場合には、ステップＳ４０４ｒに進む。
【０１８８】
ステップＳ４０４ｒでは、制御部４１６ｎ−ｕがｔ＝Ｔｍａｘであるか判定する（ステップＳ４０４ｒ）。Ｔｍａｘは予め定められた自然数である。ｔ＝Ｔｍａｘであれば、制御部４１６ｎ−ｕは、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ４０４ｔ）、処理を終える。ｔ＝Ｔｍａｘでない場合には、制御部４１６ｎ−ｕは、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ４０４ｓ）、ステップＳ８０４ｄに戻る。
【０１８９】
ステップＳ８０４ｕでは、最終出力部８１６ｍ−ｕが、ｕＭ’＝ｖＭであると判定されたｕＭ’に対応するｕＭを出力する（ステップＳ８０４ｕ）。このように得られたｕＭは高い確率で暗号文ｘＭを秘密鍵ｓ（ｋ）で復号した復号結果ｆＭ（ｘＭ）となる（その理由は後述する）。よって、上述した処理を複数回繰り返し、ステップＳ８０４ｕで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、設定によっては圧倒的な確率でｕＭ＝ｆＭ（ｘＭ）となる。その場合にはステップＳ８０４ｕで得られた値をそのまま復号結果としてよい。
【０１９０】
≪Ｍｚ１−ＭＲ１，Ｍｚ２−ＭＲ２がｆＭ（ｘＭ）についてそれぞれ誤差ＭＸ１，ＭＸ２を持つ標本器，乱数化可能標本器となる理由について≫
ｆＭ（ｘＭ）の準同型性より、ｆＭ（ｘＭ・Ｃａ＋ＣＲ２）＝ｆＭ（ｘＭ）・ｆＭ（Ｃａ）+ｆＭ（ＣＲ２）＝ｆＭ（ｘＭ）・ａＭ+ＭＲ２を満たし、ｆＭ（ｘＭ）・ａＭ＝ｆＭ（ｘＭ・Ｃａ＋ＣＲ２）−ＭＲ２＝ｆＭ（Ｍτ２）−ＭＲ２を満たし、ＭＲ２＝ｆＭ（Ｍτ２）−ｆＭ（ｘＭ）・ａＭを満たす。よってＭｚ２＝ＦＭ（Ｍτ２）とおくと、Ｍｚ２−ＭＲ２＝ＦＭ（Ｍτ２）−ｆＭ（Ｍτ２）＋ｆＭ（ｘＭ）・ａＭ＝ｆＭ（ｘＭ）・ａＭ＋｛ＦＭ（Ｍτ２）−ｆＭ（Ｍτ２）｝を満たす。Ｍτ２に対応するＣＭ２１，ＣＭ２２，ＭＲ２の一様ランダム性から、Ｍｚ２−ＭＲ２はｆＭ（ｘＭ）・ａＭ＋Ｍｘ２と統計的に近似する。ただし、Ｍｘ２は確率変数ＭＸ２＝ＦＭ（ＥＮＣＭ（ＭＵ２））−ＭＵ２（ＭＵ２はＧＭ上で一様ランダムに分布）の実現値である。したがって、Ｍｚ２−ＭＲ２はｆＭ（ｘＭ）についてそれぞれ誤差ＭＸ２を持つ乱数化可能標本器となる。
【０１９１】
同様にｆＭ（ｘＭ・ＣＵＭ＋ＣＲ１）＝ｆＭ（ｘＭ）・ｆＭ（ＣＵＭ）+ｆＭ（ＣＲ１）＝ｆＭ（ｘＭ）・ＵＭ+ＭＲ１を満たし、ｆＭ（ｘＭ）＝ｆＭ（ｘＭ・ＣＵＭ＋ＣＲ１）−ＭＲ１＝ｆＭ（Ｍτ１）−ＭＲ１を満たし、ＭＲ１＝ｆＭ（Ｍτ１）−ｆＭ（ｘＭ）を満たす。よってＭｚ１＝ＦＭ（Ｍτ１）とおくと、Ｍｚ１−ＭＲ１＝ＦＭ（Ｍτ１）−ｆＭ（Ｍτ１）＋ｆＭ（ｘＭ）＝ｆＭ（ｘＭ）＋｛ＦＭ（Ｍτ１）−ｆＭ（Ｍτ１）｝を満たす。Ｍτ１に対応するＣＭ１１，ＣＭ１２，ＭＲ１の一様ランダム性から、Ｍｚ１−ＭＲ１はｆＭ（ｘＭ）＋Ｍｘ１と統計的に近似する。ただし、Ｍｘ１は確率変数ＭＸ１＝ＦＭ（ＥＮＣＭ（ＭＵ１））−ＭＵ１（ＭＵ１はＧＭ上で一様ランダムに分布）の実現値である。したがって、Ｍｚ１−ＭＲ１はｆＭ（ｘＭ）についてそれぞれ誤差ＭＸ１を持つ標本器となる。
【０１９２】
≪復号結果ｆＭ（ｘＭ）が得られる理由について≫
第七実施形態の≪復号結果ｆ（ｘ）が得られる理由について≫で説明したのと同様な理由により、本形態でも正しい復号結果ｆＭ（ｘＭ）が得られる。ただし本形態では行列を扱う関係上、第七実施形態の≪復号結果ｆ（ｘ）が得られる理由について≫のＧ，ＨがＧＭ，ＨＭに、ｆ（ｘ）がｆＭ（ｘＭ）に、τがＭτに、Ｆ（τ）がＦＭ（Ｍτ）に、ｚがＭｚに、ｘがｘＭに、Ｘ１，Ｘ２がＭＸ１，ＭＸ２に、ｘ１，ｘ２がＭｘ１，Ｍｘ２に、ｅｇがι×ιの単位行列Ｍｅｇに、乗法的表現が加法的表現に（例えばαβγがα・β＋γに）それぞれ置き換えられる。さらに本形態では「擬似自由（ｐｓｅｕｄｏ−ｆｒｅｅ）な作用」の定義が以下のようにされる。
【０１９３】
擬似自由（ｐｓｅｕｄｏ−ｆｒｅｅ）な作用：
ＧＭ、行列の集合ΩＭ＝｛０Ｍ，．．．，ＭＭ｝、ＧＭ上の確率変数ＭＸ１，ＭＸ２の各実現値αＭ∈ＭＸ１（αＭ≠Ｍｅｇ），βＭ∈ＭＸ２、及びａＭ∈ΩＭについて、αＭ・ａＭ＝βＭとなる確率
Ｐｒ［αＭ・ａＭかつαＭ≠Ｍｅｇ｜ａＭ∈ＵΩＭ，αＭ∈ＭＸ１，βＭ∈ＭＸ２］
について、あらゆる可能なＭＸ１，ＭＸ２に関する上限値を、組（ＧＭ，ΩＭ）の疑似自由指標とよび、これをＰ（ＧＭ，ΩＭ）と表すことにする。ある無視することができる関数ζ（ｋ）が存在して、
Ｐ（ＧＭ，ΩＭ）＜ζ（ｋ）
である場合、組（ＧＭ，ΩＭ）によって定義される演算は擬似自由な作用であるという。
【０１９４】
［変形例等］
確率変数Ｘ１、Ｘ２及びＸ３は、同じでも異なっていてもよい。同様に、確率変数ＭＸ１及びＭＸ２は、同じでも異なっていてもよい。
【０１９５】
第一乱数生成部、第二乱数生成部、第三乱数生成部、第四乱数生成部、第五乱数生成部、第六乱数生成部及び第七乱数生成部のそれぞれは、一様乱数を生成することにより、復号システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部、第二乱数生成部、第三乱数生成部、第四乱数生成部、第五乱数生成部、第六乱数生成部及び第七乱数生成部の少なくとも一部が、一様乱数ではない乱数を生成してもよい。同様に、第八実施形態で行列を一様ランダムに選択する代わりに、一様ではないランダムな行列が選択されてもよい。また、演算効率上からは、上述の各実施形態のように０以上ＫＨ未満の自然数である乱数や０以上ＫＧ未満の自然数である乱数が選択されることが望ましいが、それらの代わりにＫＨ以上やＫＧ以上の自然数の乱数が選択されてもよい。
【０１９６】
復号処理部が同一のａ，ｂに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を判定復号部に提供するたびに、判定復号部の処理が複数回実行させてもよい。これにより、復号処理部が第一入力情報τ１及び第二入力情報τ２を判定復号部に一回提供するたびに、復号処理部は第一出力情報ｚ１や第二出力情報ｚ２や第三出力情報ｚ３を複数個得ることができる。これにより、復号処理部と判定復号部との間のやり取り回数や通信量を減らすことができる。第八実施形態の第一入力情報Ｍτ１及び第二入力情報Ｍτ２についても同様である。
【０１９７】
また、復号処理部が複数種類の第一入力情報τ１及び第二入力情報τ２を判定復号部にまとめて提供し、対応する第一出力情報ｚ１や第二出力情報ｚ２や第三出力情報ｚ３を複数個まとめて取得してもよい。これにより、復号処理部と判定復号部との間のやり取り回数を減らすことができる。第八実施形態の第一入力情報Ｍτ１及び第二入力情報Ｍτ２についても同様である。
【０１９８】
また、第一実施形態から第七実施形態の第一計算部や第二計算部において得られたｕやｖが群Ｇの元であるかを確認し、群Ｇの元であった場合には上述した処理を続行し、ｕ又はｖが群Ｇの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号「⊥」が出力されてもよい。同様に、第八実施形態の第一計算部や第二計算部において得られたｕＭやｖＭがＧＭの元であるかを確認し、ＧＭの元であった場合には上述した処理を続行し、ｕＭ又はｖＭがＧＭの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号「⊥」が出力されてもよい。
【０１９９】
本発明は上述の実施の形態に限定されるものではなく、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０２００】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０２０１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０２０２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０２０３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０２０４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０２０５】
１〜８  復号システム
４１−ｕ〜８１−ｕ  端末装置
４２−ｋ〜８２−ｋ  鍵装置
４３  鍵装置ＤＢ装置
【図１】
0005506704.tif 000002
【図２】
0005506704.tif 000003
【図３】
0005506704.tif 000004
【図４】
0005506704.tif 000005
【図５】
0005506704.tif 000006
【図６】
0005506704.tif 000007
【図７】
0005506704.tif 000008
【図８】
0005506704.tif 000009
【図９】
0005506704.tif 000010
【図１０】
0005506704.tif 000011
【図１１】
0005506704.tif 000012
【図１２】
0005506704.tif 000013
【図１３】
0005506704.tif 000014
【図１４】
0005506704.tif 000015
【図１５】
0005506704.tif 000016
【図１６】
0005506704.tif 000017
【図１７】
0005506704.tif 000018
【図１８】
0005506704.tif 000019
【図１９】
0005506704.tif 000020
【図２０】
0005506704.tif 000021
【図２１】
0005506704.tif 000022
【図２２】
0005506704.tif 000023
【図２３】
0005506704.tif 000024
【図２４】
0005506704.tif 000025
【図２５】
0005506704.tif 000026
【図２６】
0005506704.tif 000027
【図２７】
0005506704.tif 000028