(57)【特許請求の範囲】
【請求項１】
復号装置と復号能力提供装置と復号制御装置とを有し、
Ｇ，Ｈが巡回群、ｆ（ｘ）が群Ｈの元である暗号文ｘを特定の復号鍵で復号して群Ｇの元を得るための復号関数、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素である自然数であり、
前記復号装置が、
前記暗号文ｘに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を出力する入力情報提供部を含み、
前記復号能力提供装置が、
前記第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた演算結果を第一出力情報ｚ１として出力可能な第一出力情報計算部と、
前記第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２として出力可能な第二出力情報計算部と、を含み、
前記復号装置が、さらに
前記第一出力情報ｚ１から演算結果ｕ＝ｆ（ｘ）ｂｘ１を生成する第一計算部と、
前記第二出力情報ｚ２から演算結果ｖ＝ｆ（ｘ）ａｘ２を生成する第二計算部と、
前記演算結果ｕ及びｖがｕａ＝ｖｂを満たす場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕｂ’ｖａ’を出力する最終出力部と、を含み、
前記復号制御装置が、前記復号装置の復号処理を制御する復号制御命令を前記復号能力提供装置に出力する出力部を含み、
前記復号能力提供装置が、さらに、
前記復号制御命令に従って、前記第一出力情報ｚ１及び前記第二出力情報ｚ２の両方の出力の有無を制御する制御部を含む、
復号制御システム。
【請求項２】
請求項１の復号制御システムにおいて、
前記復号装置が、前記自然数ａ，ｂの少なくとも一方を選択する自然数選択部を含み、
前記第一入力情報τ１が前記自然数ｂにさらに対応し、前記第二入力情報τ２が前記自然数ａにさらに対応する、
復号制御システム。
【請求項３】
請求項１又は２の復号制御システムにおいて、
前記入力情報提供部が、前記暗号文ｘとの関係をかく乱させた情報を前記第一入力情報τ１及び前記第二入力情報τ２とする、
復号制御システム。
【請求項４】
請求項１から３の何れかの復号制御システムにおいて、
前記復号関数ｆ（ｘ）が準同型関数、群Ｈの生成元がμｈ、群Ｈの位数がＫＨ、ν＝ｆ（μｈ）であり、
前記入力情報提供部が、
０以上の自然数の乱数ｒ１を生成する第一乱数生成部と、
前記第一入力情報τ１としてμｈｒ１ｘｂを計算する第一入力情報計算部と、
０以上の自然数の乱数ｒ２を生成する第二乱数生成部と、
前記第二入力情報τ２としてμｈｒ２ｘａを計算する第二入力情報計算部と、を含み、
前記第一出力情報計算部は、前記第一入力情報μｈｒ１ｘｂを用い、或る確率より大きな確率でｆ（μｈｒ１ｘｂ）を正しく計算し、得られた計算結果を前記第一出力情報ｚ１とし、
前記第二出力情報計算部は、前記第二入力情報μｈｒ２ｘａを用い、或る確率より大きな確率でｆ（μｈｒ２ｘａ）を正しく計算し、得られた計算結果を第二出力情報ｚ２とし、
前記第一計算部は、ｚ１ν−ｒ１を計算してその計算結果を前記ｕとし、
前記第二計算部は、ｚ２ν−ｒ２を計算してその計算結果を前記ｖとする、
復号制御システム。
【請求項５】
請求項４の復号制御システムにおいて、
前記第一乱数生成部が、ｂ≠１のときに前記乱数ｒ１を生成し、
前記第一入力情報計算部が、ｂ≠１のときに前記第一入力情報τ１として前記μｈｒ１ｘｂを計算し、
前記第一出力情報計算部が、ｂ≠１のときに前記第一入力情報μｈｒ１ｘｂを用いて得られた前記計算結果を前記第一出力情報ｚ１とし、
前記第一計算部が、ｂ≠１のときにｚ１ν−ｒ１を計算してその計算結果を前記ｕとし、
前記第二乱数生成部が、ａ≠１のときに前記乱数ｒ２を生成し、
前記第二入力情報計算部が、ａ≠１のときに前記第二入力情報τ２としてμｈｒ２ｘａを計算し、
前記第二出力情報計算部が、ａ≠１のときに前記第二入力情報μｈｒ２ｘａを用いて得られた前記計算結果を第二出力情報ｚ２とし、
前記第二計算部が、ａ≠１のときにｚ２ν−ｒ２を計算してその計算結果を前記ｖとし、
前記入力情報提供部が、
０以上の自然数の乱数ｒ３を生成する第三乱数生成部と、
ｂ＝１のときにｘｒ３を前記第一入力情報τ１とし、ａ＝１のときにｘｒ３を前記第二入力情報τ２とする第三入力情報計算部と、を含み、
前記復号能力提供装置が、
前記ｘｒ３を用い、或る確率より大きな確率でｆ（ｘｒ３）を正しく計算し、得られた計算結果を第三出力情報ｚ３とする第三出力情報計算部を含み、
前記復号装置が、
ｂ＝１のときにｚ３１／ｒ３を前記ｕとし、ａ＝１のときにｚ３１／ｒ３を前記ｖとする第三計算部を含む、
復号制御システム。
【請求項６】
請求項１から３の何れかの復号制御システムにおいて、
群Ｈ＝Ｇ×Ｇ、前記復号関数ｆ（ｘ）が準同型関数、群Ｇの生成元がμｇ、群Ｇの位数がＫＧ、ｘ＝（ｃ１，ｃ２），（Ｖ，Ｗ）が群Ｈの元、ｆ（Ｖ，Ｗ）＝Ｙであり、
前記入力情報提供部が、
０以上の自然数の乱数ｒ４を生成する第四乱数生成部と、
０以上の自然数の乱数ｒ５を生成する第五乱数生成部と、
前記第一入力情報τ１としてｃ２ｂＷｒ４及びｃ１ｂＶｒ４μｇｒ５を計算する第一入力情報計算部と、
０以上の自然数の乱数ｒ６を生成する第六乱数生成部と、
０以上の自然数の乱数ｒ７を生成する第七乱数生成部と、
前記第二入力情報τ２としてｃ２ａＷｒ６及びｃ１ａＶｒ６μｇｒ７を計算する第二入力情報計算部と、を含み、
前記第一出力情報計算部が、前記第一入力情報ｃ１ｂＶｒ４μｇｒ５及びｃ２ｂＷｒ４を用い、或る確率より大きな確率でｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）を正しく計算し、得られた計算結果を前記第一出力情報ｚ１とし、
前記第二出力情報計算部が、前記第二入力情報ｃ１ａＶｒ６μｇｒ７及びｃ２ａＷｒ６を用い、或る確率より大きな確率でｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）を正しく計算し、得られた計算結果を前記第二出力情報ｚ２とし、
前記第一計算部が、ｚ１Ｙ−ｒ４μｇ−ｒ５を計算してその計算結果を前記ｕとし、
前記第二計算部が、ｚ２Ｙ−ｒ６μｇ−ｒ７を計算してその計算結果を前記ｖとする、
復号制御システム。
【請求項７】
請求項１から６の何れかの復号制御システムにおいて、
前記演算結果ｕのｆ（ｘ）ｂに対する誤差の確率分布が前記自然数ｂに依存しない、並びに／若しくは、前記演算結果ｖのｆ（ｘ）ａに対する誤差の確率分布が前記自然数ａに依存しない、又は、前記演算結果ｕのｆ（ｘ）ｂに対する誤差の確率分布と区別することができない前記自然数ｂに依存しない確率分布が存在する、並びに／若しくは、前記演算結果ｖのｆ（ｘ）ａに対する誤差の確率分布と区別することができない前記自然数ａに依存しない確率分布が存在する、
復号制御システム。
【請求項８】
請求項１から７の何れかの復号制御システムにおいて、
前記自然数ａ又は前記自然数ｂが定数である、
復号制御システム。
【請求項９】
復号装置と復号能力提供装置と復号制御装置とが実行する復号制御方法であって、
Ｇ，Ｈが巡回群、ｆ（ｘ）が群Ｈの元である暗号文ｘを特定の復号鍵で復号して群Ｇの元を得るための復号関数、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素である自然数であり、
（Ａ）前記復号装置で、前記暗号文ｘに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を出力するステップと、
（Ｂ）前記復号制御装置から出力された前記復号装置の復号処理を制御する復号制御命令に従って、前記復号能力提供装置で、前記第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた演算結果を第一出力情報ｚ１として出力する処理と、前記第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２として出力する処理と、の両方の実行の有無を制御するステップと、
（Ｄ）前記復号装置で、前記第一出力情報ｚ１から演算結果ｕ＝ｆ（ｘ）ｂｘ１を生成するステップと、
（Ｅ）前記復号装置で、前記第二出力情報ｚ２から演算結果ｖ＝ｆ（ｘ）ａｘ２を生成するステップと、
（Ｆ）前記復号装置で、前記演算結果ｕ及びｖがｕａ＝ｖｂを満たす場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕｂ’ｖａ’を出力するステップと、を有する復号制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号文の復号技術に関し、特に、暗号文の復号能力を制御する技術に関する。
【背景技術】
【０００２】
公開鍵暗号方式や共通鍵暗号方式などの暗号方式で暗号化された暗号文を復号するためには、特定の復号鍵が必要である（例えば、非特許文献１参照）。これを利用し、復号装置に復号鍵を与えるか否かによって復号装置による暗号文の復号能力を制御することが可能である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Taher Elgamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," IEEE Transactions on Information Theory, v. IT-31, n. 4, 1985, pp. 469-472 or CRYPTO 84, pp. 10-18, Springer-Verlag.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、復号装置に復号鍵を与えるか否かによって復号装置による暗号文の復号能力を制御する方法では、復号装置に復号鍵を与えることに起因する問題点がある。例えば、この方法では復号装置に復号鍵を与えた後は復号装置の復号能力を再び制限することができず、さらに、復号装置がどのような復号鍵に対応する暗号文を復号しようとしているのかについての情報が復号鍵を提供する側に知られてしまう。
【０００５】
本発明はこのような点に鑑みてなされたものであり、復号装置に復号鍵を与えることなく、復号装置による暗号文の復号能力を制御する技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明では、Ｇ，Ｈを巡回群、ｆ（ｘ）を群Ｈの元である暗号文ｘを特定の復号鍵で復号して群Ｇの元を得るための復号関数、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、ｘ１を確率変数Ｘ１の実現値、ｘ２を確率変数Ｘ２の実現値、ａ，ｂを互いに素である自然数として、復号装置が、暗号文ｘに対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を出力し、復号能力提供装置が、第一入力情報τ１を用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、演算結果を第一出力情報ｚ１として出力可能であり、第二入力情報τ２を用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、演算結果を第二出力情報ｚ２として出力可能であり、復号装置が、第一出力情報ｚ１から演算結果ｕ＝ｆ（ｘ）ｂｘ１を生成し、第二出力情報ｚ２から演算結果ｖ＝ｆ（ｘ）ａｘ２を生成し、演算結果ｕ及びｖがｕａ＝ｖｂを満たす場合に、ａ’ａ＋ｂ’ｂ＝１を満たす整数ａ’，ｂ’についてのｕｂ’ｖａ’を出力する。復号制御装置は、復号装置の復号処理を制御する復号制御命令を復号能力提供装置に出力し、復号能力提供装置は、復号制御命令に従って第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力の有無を制御する。
【発明の効果】
【０００７】
第一出力情報ｚ１及び第二出力情報ｚ２が復号装置に与えられた場合、復号装置はある確率でｕｂ’ｖａ’を出力できる。ｕｂ’ｖａ’は高い確率で暗号文ｘの復号値となる。一方、第一出力情報ｚ１及び第二出力情報ｚ２の両方が復号装置に与えられなかった場合、復号装置は暗号文ｘの復号値を得ることができない。本発明では、復号能力提供装置による第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力の有無を制御することで、復号装置に復号鍵を与えることなく、復号装置による暗号文の復号能力を制御できる。
【図面の簡単な説明】
【０００８】
【図１】実施形態の復号制御システムの構成を説明するためのブロック図。
【図２】実施形態の復号装置の構成を説明するためのブロック図。
【図３】実施形態の復号能力提供装置の構成を説明するためのブロック図。
【図４】実施形態の復号制御装置の構成を説明するためのブロック図。
【図５】実施形態の入力情報提供部の構成を説明するためのブロック図。
【図６】実施形態の入力情報提供部の構成を説明するためのブロック図。
【図７】実施形態の復号装置の処理を説明するためのフローチャート。
【図８】実施形態の復号能力提供装置の処理を説明するためのフローチャート。
【図９】ステップＳ２１０３（Ｓ３１０３）の処理を説明するためのフローチャート。
【図１０】ステップＳ４１０３の処理を説明するためのフローチャート。
【図１１】実施形態の復号装置の構成を説明するためのブロック図。
【図１２】実施形態の復号装置の処理を説明するためのフローチャート。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施形態を説明する。
【００１０】
［第一実施形態］
まず、本発明の第一実施形態を説明する。
【００１１】
＜構成＞
図１に例示するように、第一実施形態の復号制御システム１は、例えば、復号鍵を保持していない復号装置１１と復号鍵を保持する復号能力提供装置１２と復号装置１１の復号能力を制御する復号制御装置１３とを有する。復号制御装置１３は復号能力提供装置１２から復号装置１１へ提供される復号能力を制御し、復号装置１１は復号能力提供装置１２から提供された復号能力を用いて暗号文を復号する。復号装置１１と復号能力提供装置１２と復号制御装置１３とは情報のやり取りが可能なように構成される。例えば、復号装置１１と復号能力提供装置１２と復号制御装置１３とは、伝送線やネットワークや可搬型記録媒体などを経由した情報のやり取りが可能とされている。
【００１２】
図２に例示するように、第一実施形態の復号装置１１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部１１０４と第一計算部１１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部１１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と最終出力部１１１２と制御部１１１３とを有する。復号装置１１の例は、カードリーダライタ装置や携帯電話などの計算機能と記憶機能とを備えた機器や、特別なプログラムが読み込まれたＣＰＵ（ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）やＲＡＭ（ｒａｎｄｏｍ−ａｃｃｅｓｓ  ｍｅｍｏｒｙ）を備えた公知又は専用のコンピュータなどである。
【００１３】
図３に例示するように、第一実施形態の復号能力提供装置１２は、例えば、第一出力情報計算部１２０１と第二出力情報計算部１２０２と鍵記憶部１２０４と制御部１２０５とを有する。復号能力提供装置１２の例は、ＩＣカードやＩＣチップなどの耐タンパ性モジュールや、携帯電話などの計算機能と記憶機能とを備えた機器や、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータなどである。
【００１４】
図４に例示するように、第一実施形態の復号制御装置１３は、例えば、暗号文記憶部１３０１と制御命令部１３０２と出力部１３０３と制御部１３０４とを有する。復号制御装置１３の例は、携帯電話などの計算機能と記憶機能とを備えた機器や、特別なプログラムが読み込まれたＣＰＵやＲＡＭを備えた公知又は専用のコンピュータなどである。
【００１５】
＜復号処理＞
次に本形態の復号処理を説明する。復号処理の前提として、Ｇ，Ｈを巡回群、ｆ（ｘ）を群Ｈの元である暗号文ｘを特定の復号鍵ｓで復号して群Ｇの元を得るための復号関数、群Ｇ，Ｈの生成元をそれぞれμｇ，μｈ、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２とする。また、復号装置１１の自然数記憶部１１０１には、互いに素である２つの自然数ａ，ｂの組（ａ，ｂ）が複数種類記憶されているものとする。「自然数」とは０以上の整数を意味する。Ｉを群Ｇの位数未満の２つの自然数の組で互いに素なものの集合とすると、自然数記憶部１１０１にはＩの部分集合Ｓに対応する自然数ａ，ｂの組（ａ，ｂ）が記憶されていると考えることができる。また、復号能力提供装置１２の鍵記憶部２１０４には、特定の復号鍵ｓが安全に格納されているものとする。また、復号制御装置１３の暗号文記憶部１３０１には暗号文ｘが格納されているものとする。なお、復号装置１１の各処理は制御部１１１３の制御のもとで実行され、復号能力提供装置１２の各処理は制御部１２０５の制御のもとで実行され、復号制御装置１３の各処理は制御部１３０４の制御のもとで実行される。
【００１６】
図７に例示するように、まず、復号装置１１（図２）の自然数選択部１１０２が、自然数記憶部１１０１に記憶された複数の自然数の組（ａ，ｂ）から１つの自然数の組（ａ，ｂ）をランダムに読み込む。読み込まれた自然数の組（ａ，ｂ）の少なくとも一部の情報は、整数計算部１１０３、入力情報提供部１１０４、第一べき乗計算部１１０６及び第二べき乗計算部１１０９に送られる（ステップＳ１１００）。
【００１７】
整数計算部１１０３は、送られた自然数の組（ａ，ｂ）を用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する。自然数ａ，ｂは互いに素であるため、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’は必ず存在して、その計算方法もよく知られている。たとえば拡張互除法などのよく知られたアルゴリズムによって整数ａ’，ｂ’が計算され、自然数の組（ａ’，ｂ’）の情報は、最終出力部１１１２に送られる（ステップＳ１１０１）。
【００１８】
制御部１１１３は、ｔ＝１とする（ステップＳ１１０２）。
【００１９】
復号制御装置１３（図４）の暗号文記憶部１３０１に格納されている暗号文ｘが出力部１３０３から出力され、復号装置１１（図２）に入力される。復号装置１１の入力情報提供部１１０４は、入力された暗号文ｘにそれぞれ対応する群Ｈの元である第一入力情報τ１及び第二入力情報τ２を生成して出力する。好ましくは、第一入力情報τ１及び第二入力情報τ２はそれぞれ暗号文ｘとの関係をかく乱させた情報である。これにより、復号装置１１は、暗号文ｘを復号能力提供装置１２に対して隠蔽できる。また、好ましくは、本形態の第一入力情報τ１は自然数選択部１１０２で選択された自然数ｂにさらに対応し、第二入力情報τ２は自然数選択部１１０２で選択された自然数ａにさらに対応する。これにより、復号能力提供装置１２から提供された復号能力を復号装置１１が高い精度で評価できる（ステップＳ１１０３）。
【００２０】
図８に例示するように、第一入力情報τ１は復号能力提供装置１２（図３）の第一出力情報計算部１２０１に入力され、第二入力情報τ２は第二出力情報計算部１２０２に入力される（ステップＳ１２００）。
【００２１】
第一出力情報計算部１２０１は、第一入力情報τ１と鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする（ステップＳ１２０１）。第二出力情報計算部１２０２は、第二入力情報τ２と鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２とする（ステップＳ１２０２）。なお、「或る確率」は１００％未満の確率である。「或る確率」の例は無視することができない確率であり、「無視することができない確率」の例は、セキュリティパラメータｋについての広義単調増加関数である多項式を多項式ψ（ｋ）とした場合の１／ψ（ｋ）以上の確率である。すなわち、第一出力情報計算部１２０１や第二出力情報計算部１２０２は、意図的又は意図的ではない誤差を含んだ計算結果を出力し得る。言い換えると、第一出力情報計算部１２０１での計算結果がｆ（τ１）の場合もあればｆ（τ１）でない場合もあり、第二出力情報計算部１２０２での計算結果がｆ（τ２）の場合もあればｆ（τ２）でない場合もある。
【００２２】
第一出力情報計算部１２０１は第一出力情報ｚ１を出力し、第二出力情報計算部１２０２は第二出力情報ｚ２を出力する（ステップＳ１２０３）。
【００２３】
図７に戻り、第一出力情報ｚ１は復号装置１１（図２）の第一計算部１１０５に入力され、第二出力情報ｚ２は第二計算部１１０８に入力される。これらの第一出力情報ｚ１及び第二出力情報ｚ２が、復号能力提供装置１２から復号装置１１に与えられた復号能力に相当する（ステップＳ１１０４）。
【００２４】
第一計算部１１０５は、第一出力情報ｚ１から演算結果ｕ＝ｆ（ｘ）ｂｘ１を生成する。ここで、ｆ（ｘ）ｂｘ１を生成（計算）するとは、ｆ（ｘ）ｂｘ１と定義される式の値を計算することである。式ｆ（ｘ）ｂｘ１の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。演算結果ｕは第一べき乗計算部１１０６に送られる（ステップＳ１１０５）。
【００２５】
第一べき乗計算部１１０６はｕ’＝ｕａを計算する。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部１１０７に記憶される（ステップＳ１１０６）。
【００２６】
判定部１１１１は、第一リスト記憶部１１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１１１０に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ１１０７）。もし、第二リスト記憶部１１１０に組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ１１０７の処理を行わずに、次のステップＳ１１０８の処理を行う。ｕ’＝ｖ’となるものがあった場合には、ステップＳ１１１４に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ１１０８に進む。
【００２７】
ステップＳ１１０８では、第二計算部１１０８が、第二出力情報ｚ２から演算結果ｖ＝ｆ（ｘ）ａｘ２を生成する。演算結果ｖは第二べき乗計算部１１０９に送られる（ステップＳ１１０８）。
【００２８】
第二べき乗計算部１１０９はｖ’＝ｖｂを計算する。計算結果ｖとその計算結果に基づいて計算されたｖ’との組（ｖ，ｖ’）は、第二リスト記憶部１１１０に記憶される（ステップＳ１１０９）。
【００２９】
判定部１１１１は、第一リスト記憶部１１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１１１０に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ１１１０）。ｕ’＝ｖ’となるものがあった場合には、ステップＳ１１１４に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ１１１１に進む。
【００３０】
ステップＳ１１１１では、制御部１１１３がｔ＝Ｔであるか判定する（ステップＳ１１１１）。Ｔは予め定められた１以上の自然数である。ｔ＝Ｔであれば、最終出力部１１１２が、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１１３）、処理を終える。ｔ＝Ｔでない場合には、制御部１１１３は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１（ｔ＋１を新たなｔ）として（ステップＳ１１１２）、ステップＳ１１０３に戻る。
【００３１】
計算をすることができなかった旨の情報（この例では記号「⊥」）は、復号能力提供装置１２が正しく計算を行う信頼性がＴで定められる基準を下回るということを意味する。言い換えれば、Ｔ回の繰り返しで正しい演算を行うことができなかったということを意味する。
【００３２】
ステップＳ１１１４では、最終出力部１１１２が、ｕ’＝ｖ’であると判定されたｕ’及びｖ’に対応するｕ及びｖを用いてｕｂ’ｖａ’を計算して、出力する（ステップＳ１１１４）。このように計算されたｕｂ’ｖａ’は高い確率で暗号文ｘを特定の復号鍵ｓで復号した復号結果ｆ（ｘ）となる（高い確率でｕｂ’ｖａ’＝ｆ（ｘ）となる理由については後述する）。よって、上述した処理を複数回繰り返し、ステップＳ１１１４で得られた値のうち最も頻度の高い値を復号結果とすればよい。また、後述するように、設定によっては圧倒的な確率でｕｂ’ｖａ’＝ｆ（ｘ）となる。その場合にはステップＳ１１１４で得られた値をそのまま復号結果としてよい。
【００３３】
≪高い確率でｕｂ’ｖａ’＝ｆ（ｘ）となる理由について≫
Ｘを群Ｇに値を持つ確率変数とする。ｗ∈Ｇについて、要求を受けるたびに確率変数Ｘに従った標本ｘ’に対応するｗｘ’を返すものを、ｗについて誤差Ｘを持つ標本器（ｓａｍｐｌｅｒ）と呼ぶ。
【００３４】
ｗ∈Ｇについて、自然数ａが与えられるたびに確率変数Ｘに従った標本ｘ’に対応するｗａｘ’を返すものを、ｗについて誤差Ｘを持つ乱数化可能標本器（ｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒ）と呼ぶ。乱数化可能標本器はａ＝１として用いられれば標本器として機能する。
【００３５】
本実施形態の入力情報提供部１１０４と第一出力情報計算部１２０１と第一計算部１１０５との組み合わせが、ｆ（ｘ）について誤差Ｘ１を持つ乱数化可能標本器（「第一乱数化可能標本器」と呼ぶ）であり、入力情報提供部１１０４と第二出力情報計算部１２０２と第二計算部１１０８との組み合わせが、ｆ（ｘ）について誤差Ｘ２を持つ乱数化可能標本器（「第二乱数化可能標本器」と呼ぶ）である。
【００３６】
ｕ’＝ｖ’が成立するのは、すなわちｕａ＝ｖｂが成立するのは、第一乱数化可能標本器がｕ＝ｆ（ｘ）ｂを正しく計算しており、第二乱数化可能標本器がｖ＝ｆ（ｘ）ａを正しく計算している（ｘ１及びｘ２が群Ｇの単位元ｅｇである）可能性が高いことを発明者は見出した。説明の簡略化の観点から、この証明は第五実施形態で行う。
【００３７】
第一乱数化可能標本器がｕ＝ｆ（ｘ）ｂを正しく計算しており、第二乱数化可能標本器がｖ＝ｆ（ｘ）ａを正しく計算しているとき（ｘ１及びｘ２が群Ｇの単位元ｅｇであるとき）、ｕｂ’ｖａ’＝（ｆ（ｘ）ｂｘ１）ｂ’（ｆ（ｘ）ａｘ２）ａ’＝（ｆ（ｘ）ｂｅｇ）ｂ’（ｆ（ｘ）ａｅｇ）ａ’＝ｆ（ｘ）ｂｂ’ｅｇｂ’ｆ（ｘ）ａａ’ｅｇａ’＝ｆ（ｘ）（ｂｂ’＋ａａ’）＝ｆ（ｘ）となる。
【００３８】
また、（ｑ１，ｑ２）∈Ｉについて、ｉ＝１，２の各々について関数πｉをπｉ（ｑ１，ｑ２）＝ｑｉで定義する。さらに、Ｌ＝ｍｉｎ（♯π１（Ｓ），♯π２（Ｓ））とする。♯・は、集合・の位数である。群Ｇが巡回群や位数の計算が困難な群であるときには、復号装置１１が「⊥」以外を出力するときの出力がｆ（ｘ）ではない確率は、無視できる程度の誤差の範囲で高々Ｔ２Ｌ／♯Ｓ程度と期待することができる。もしＬ／♯Ｓが無視できる量でＴが多項式オーダー程度の量であれば、復号装置１１は圧倒的な確率で正しいｆ（ｘ）を出力する。Ｌ／♯Ｓが無視できる量になるようなＳの例には、例えばＳ＝｛（１，ｄ）｜ｄ∈［２，｜Ｇ｜−１］｝がある。
【００３９】
＜復号制御処理＞
次に、本形態の復号制御処理を説明する。
【００４０】
復号制御装置１３が復号装置１１の復号処理を制御する場合、復号制御装置１３は、復号装置１１の復号処理を制御する復号制御命令を復号能力提供装置１２に出力する。復号能力提供装置１２は、入力された復号制御命令に従って、第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力の有無を制御する。復号装置１１は、第一出力情報ｚ１及び第二出力情報ｚ２が与えられなければ暗号文ｘを復号することができない。そのため、第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力の有無を制御することで、復号装置１１の復号能力を制御できる。以下に復号処理の制御方法を例示する。
【００４１】
≪復号処理の制御方法の例１≫
復号処理の制御方法の例１では、復号制御命令が復号装置１１の復号能力を制限するための復号制限命令ｃｏｍ−１を含み、復号制限命令ｃｏｍ−１が復号能力提供装置１２の制御部１２０５に入力された場合に制御部１２０５が第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力を禁止する。
【００４２】
復号装置１１の復号能力を制限する場合、復号制御装置１３（図４）の制御命令部１３０２が復号制限命令ｃｏｍ−１を出力する。復号制限命令ｃｏｍ−１は出力部１３０３から復号能力提供装置１２に出力される。
【００４３】
復号能力提供装置１２（図３）の制御部１２０５は、復号制限命令ｃｏｍ−１が入力されたか否かを判断し、復号制限命令ｃｏｍ−１が制御部１２０５に入力されない場合には復号制御処理を行わない。一方、復号制限命令ｃｏｍ−１が制御部１２０５に入力された場合には、制御部１２０５は第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力を禁止する制御を行う（復号制限モード）。
【００４４】
復号制限モードでは、制御部１２０５が第一出力情報計算部１２０１による第一出力情報ｚ１の出力及び第二出力情報計算部１２０１による第二出力情報ｚ２の出力の両方を禁止する。第一出力情報ｚ１及び／又は第二出力情報ｚ２の出力を禁止する制御の一例は、第一出力情報ｚ１及び／又は第二出力情報ｚ２の生成は禁止しないがこれらの出力を禁止する制御である。第一出力情報ｚ１及び／又は第二出力情報ｚ２の出力を禁止する制御の他の例は、第一出力情報ｚ１及び／又は第二出力情報ｚ２の代わりにダミー情報を出力させる制御である。なお、ダミー情報の例は、乱数その他の暗号文ｘに依存しない情報である。第一出力情報ｚ１及び／又は第二出力情報ｚ２の出力を禁止する制御の別の例は、第一出力情報ｚ１及び／又は第二出力情報ｚ２の生成自体を禁止する制御である。第一出力情報ｚ１及び／又は第二出力情報ｚ２の生成自体を禁止する制御を行う場合には、第一出力情報ｚ１及び／又は第二出力情報ｚ２の生成を行うために必要な情報を無効又は削除してもよいし、しなくてもよい。例えば、鍵記憶部１２０４に格納された復号鍵ｓを無効又は削除してもよいし、しなくてもよい。
【００４５】
第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力が禁止された場合、復号能力提供装置１２はステップＳ１２０３で第一出力情報ｚ１及び第二出力情報ｚ２の両方を出力しない。そのため、復号装置１１はステップＳ１１０４で第一出力情報ｚ１及び第二出力情報ｚ２の両方を取得できず、演算結果ｕ及びｖを計算できないため、正しい復号結果を得ることができない。これにより、復号装置１１の復号能力を制限できる。
【００４６】
≪復号処理の制御方法の例２≫
復号処理の制御方法の例２では、復号制御命令が復号装置１１の復号能力の制限を開放するための復号開放命令ｃｏｍ−２を含み、復号開放命令ｃｏｍ−２が復号能力提供装置１２の制御部１２０５に入力された場合、制御部１２０５は第一出力情報ｚ１及び第二出力情報ｚ２の少なくとも一方の出力を許可する。復号処理の制御方法の例２は、例えば、復号処理の制御方法の例１によって第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力が禁止された後、再び、第一出力情報ｚ１及び第二出力情報ｚ２の出力を許可する場合に行われる。この際、第一出力情報ｚ１及び／又は第二出力情報ｚ２の生成を行うために必要な情報が無効又は削除されていた場合には、復号開放命令ｃｏｍ−２が当該情報を含み、当該情報を復号能力提供装置１２に再設定することにしてもよい。その他、復号処理の制御方法の例２は、例えば、初期状態において第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力が禁止されている場合に、第一出力情報ｚ１及び第二出力情報ｚ２の出力を許可する場合に行われてもよい。
【００４７】
復号装置１１の復号能力の制限を開放する場合、復号制御装置１３（図４）の制御命令部１３０２が復号開放命令ｃｏｍ−２を出力する。復号制限命令ｃｏｍ−２は出力部１３０３から復号能力提供装置１２に出力される。
【００４８】
復号能力提供装置１２（図３）の制御部１２０５は、復号開放命令ｃｏｍ−２が入力されたか否かを判断し、復号開放命令ｃｏｍ−２が制御部１２０５に入力されていない場合には復号制御処理を行わない。一方、復号開放命令ｃｏｍ−２が制御部１２０５に入力された場合には、制御部１２０５は第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力を許可する制御を行う（復号許可モード）。
【００４９】
第一出力情報ｚ１及び第二出力情報ｚ２の両方の出力が許可された場合、復号能力提供装置１２はステップＳ１２０３で第一出力情報ｚ１又は第二出力情報ｚ２の両方を出力する。そのため、復号装置１１はステップＳ１１０４で第一出力情報ｚ１又は第二出力情報ｚ２の両方を取得でき、演算結果ｕ又はｖを計算できるため、高い確率で復号結果を得ることができる。これにより、復号装置１１の復号能力の制限を開放することができる。
【００５０】
［第二実施形態］
第二実施形態の復号制御システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した例である。以下、第一実施形態と異なる部分を中心に説明し、復号制御処理などの共通する部分については重複説明を省略する。以下の説明において、同一の参照番号が付された部分は同一の機能を持つものとし、同一の参照番号が付されたステップは同一の処理を表すものとする。
【００５１】
＜構成＞
図１に例示するように、第二実施形態の復号制御システム２は、復号装置１１が復号装置２１に置換され、復号能力提供装置１２が復号能力提供装置２２に置換されたものである。
【００５２】
図２に例示するように、第二実施形態の復号装置２１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部２１０４と第一計算部２１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部２１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と最終出力部１１１２と制御部１１１３とを有する。図５に例示するように、本形態の入力情報提供部２１０４は、例えば、第一乱数生成部２１０４ａと第一入力情報計算部２１０４ｂと第二乱数生成部２１０４ｃと第二入力情報計算部２１０４ｄとを有する。
【００５３】
図３に例示するように、第二実施形態の復号能力提供装置２２は、例えば、第一出力情報計算部２２０１と第二出力情報計算部２２０２と鍵記憶部１２０４と制御部１２０５とを有する。
【００５４】
＜復号処理＞
次に本形態の復号処理を説明する。第二実施形態では、復号関数ｆ（ｘ）を準同型関数とし、群Ｈの生成元をμｈ、群Ｈの位数をＫＨ、ν＝ｆ（μｈ）とする。復号関数ｆ（ｘ）が準同型関数である例はＲＳＡ暗号などである。その他の前提は、復号装置１１が復号装置２１に置換され、復号能力提供装置１２が復号能力提供装置２２に置換されている以外、第一実施形態と同一である。
【００５５】
図７及び図８に例示するように、第二実施形態の処理は第一実施形態のステップＳ１１０３〜Ｓ１１０５，Ｓ１１０８，Ｓ１２００〜Ｓ１２０３が、それぞれ、ステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３に置換されたものである。以下ではステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３の処理のみを説明する。
【００５６】
《ステップＳ２１０３の処理》
復号装置２１（図２）の入力情報提供部２１０４は、入力された暗号文ｘにそれぞれ対応する第一入力情報τ１及び第二入力情報τ２を生成して出力する（図７／ステップＳ２１０３）。以下、図９を用いて本形態のステップＳ２１０３の処理を説明する。
【００５７】
第一乱数生成部２１０４ａ（図５）は、０以上ＫＨ未満の自然数の一様乱数ｒ１を生成する。生成された乱数ｒ１は、第一入力情報計算部２１０４ｂ及び第一計算部２１０５に送られる（ステップＳ２１０３ａ）。第一入力情報計算部２１０４ｂは、入力された乱数ｒ１と暗号文ｘと自然数ｂとを用いて第一入力情報τ１＝μｈｒ１ｘｂを計算する（ステップＳ２１０３ｂ）。ここで、μｈの右肩のｒ１は、ｒ１のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。
【００５８】
第二乱数生成部２１０４ｃは、０以上ＫＨ未満の自然数の一様乱数ｒ２を生成する。生成された乱数ｒ２は、第二入力情報計算部２１０４ｄ及び第二計算部２１０８に送られる（ステップＳ２１０３ｃ）。第二入力情報計算部２１０４ｄは、入力された乱数ｒ２と暗号文ｘと自然数ａとを用いて第二入力情報τ２＝μｈｒ２ｘａを計算する（ステップＳ２１０３ｄ）。
【００５９】
第一入力情報計算部２１０４ｂ及び第二入力情報計算部２１０４ｄは、以上のように生成した第一入力情報τ１及び第二入力情報τ２を出力する（ステップＳ２１０３ｅ）。なお、本形態の第一入力情報τ１及び第二入力情報τ２は、それぞれ、乱数ｒ１，ｒ２によって暗号文ｘとの関係をかく乱させた情報である。これにより、復号装置２２は、暗号文ｘを復号能力提供装置２２に対して隠蔽できる。また、本形態の第一入力情報τ１は自然数選択部１１０２で選択された自然数ｂにさらに対応し、第二入力情報τ２は自然数選択部１１０２で選択された自然数ａにさらに対応する。これにより、復号能力提供装置２２から提供された復号能力を復号装置２１が高い精度で評価できる。
【００６０】
《ステップＳ２２００〜Ｓ２２０３の処理》
図８に例示するように、まず、第一入力情報τ１＝μｈｒ１ｘｂが復号能力提供装置２２（図３）の第一出力情報計算部２２０１に入力され、第二入力情報τ２＝μｈｒ２ｘａが第二出力情報計算部２２０２に入力される（ステップＳ２２００）。
【００６１】
第一出力情報計算部２２０１は、第一入力情報τ１＝μｈｒ１ｘｂと鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（μｈｒ１ｘｂ）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部２２０１での計算結果がｆ（μｈｒ１ｘｂ）となる場合もあれば、ｆ（μｈｒ１ｘｂ）とならない場合もある（ステップＳ２２０１）。
【００６２】
第二出力情報計算部２２０２は、第二入力情報τ２＝μｈｒ２ｘａと鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（μｈｒ２ｘａ）を正しく計算し、得られた計算結果を第二出力情報ｚ２とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部２２０２での計算結果がｆ（μｈｒ２ｘａ）となる場合もあれば、ｆ（μｈｒ２ｘａ）とならない場合もある（ステップＳ２２０２）。
【００６３】
第一出力情報計算部２２０１は第一出力情報ｚ１を出力し、第二出力情報計算部２２０２は第二出力情報ｚ２を出力する（ステップＳ２２０３）。
【００６４】
《ステップＳ２１０４及びＳ２１０５の処理》
図７に戻り、第一出力情報ｚ１は復号装置２１（図２）の第一計算部２１０５に入力され、第二出力情報ｚ２は第二計算部２１０８に入力される。これらの第一出力情報ｚ１及び第二出力情報ｚ２が、復号能力提供装置２２から復号装置２１に与えられた復号能力に相当する（ステップＳ２１０４）。
【００６５】
第一計算部２１０５は、入力された乱数ｒ１及び第一出力情報ｚ１を用いてｚ１ν−ｒ１を計算してその計算結果をｕとする。計算結果ｕは、第一べき乗計算部１１０６に送られる。ここで、ｕ＝ｚ１ν−ｒ１＝ｆ（ｘ）ｂｘ１となる。すなわち、ｚ１ν−ｒ１は、ｆ（ｘ）について誤差Ｘ１を持つ乱数化可能標本器の出力となる。その理由については後述する（ステップＳ２１０５）。
【００６６】
《ステップＳ２１０８の処理》
第二計算部２１０８は、入力された乱数ｒ２及び第二出力情報ｚ２を用いてｚ２ν−ｒ２を計算してその計算結果をｖとする。計算結果ｖは、第二べき乗計算部１１０９に送られる。ここで、ｖ＝ｚ２ν−ｒ２＝ｆ（ｘ）ａｘ２となる。すなわち、ｚ２ν−ｒ２は、ｆ（ｘ）について誤差Ｘ２を持つ乱数化可能標本器の出力となる。その理由については後述する（ステップＳ２１０８）。
【００６７】
≪ｚ１ν−ｒ１，ｚ２ν−ｒ２がｆ（ｘ）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器の出力となる理由について≫
ｃを自然数、Ｒ及びＲ’を乱数として、復号能力提供装置２２がμｈＲｘｃを用いて行う計算の計算結果をＢ（μｈＲｘｃ）とする。すなわち、第一出力情報計算部２２０１や第二出力情報計算部２２０２が復号装置２１に返す計算結果をｚ＝Ｂ（μｈＲｘｃ）とする。さらに、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（μｈＲ’）ｆ（μｈＲ’）−１と定義する。
【００６８】
このとき、ｚν−Ｒ＝Ｂ（μｈＲｘｃ）ｆ（μｈ）−Ｒ＝Ｘｆ（μｈＲｘｃ）ｆ（μｈ）−Ｒ＝Ｘｆ（μｈ）Ｒｆ（ｘ）ｃｆ（μｈ）−Ｒ＝ｆ（ｘ）ｃＸとなる。すなわち、ｚν−Ｒは、ｆ（ｘ）について誤差Ｘを持つ乱数化可能標本器の出力となる。
【００６９】
上記式展開において、Ｘ＝Ｂ（μｈＲ’）ｆ（μｈＲ’）−１＝Ｂ（μｈＲｘｃ）ｆ（μｈＲｘｃ）−１であり、Ｂ（μｈＲｘｃ）＝Ｘｆ（μｈＲｘｃ）であるという性質を用いている。この性質は、関数ｆ（ｘ）が準同型関数であり、Ｒ及びＲ’が乱数であることに基づく。
【００７０】
したがって、ａ，ｂが自然数、ｒ１，ｒ２が乱数であることを考慮すると、同様に、ｚ１ν−ｒ１，ｚ２ν−ｒ２がｆ（ｘ）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器の出力となるのである。
【００７１】
［第三実施形態］
第三実施形態は第二実施形態の変形例であり、ａ＝１やｂ＝１のときに前述した標本器によってｕ又はｖの値を計算する。一般に乱数化可能標本器よりも標本器の計算量は小さい。ａ＝１やｂ＝１のときに乱数化可能標本器に代わり、標本器が計算を行うことで、復号制御システムの計算量を小さくすることができる。以下、第一実施形態及び第二実施形態と異なる部分を中心に説明し、復号制御処理などの共通する部分については重複説明を省略する。
【００７２】
＜構成＞
図１に例示するように、第三実施形態の復号制御システム３は、復号装置２１が復号装置３１に置換され、復号能力提供装置２２が復号能力提供装置３２に置換されたものである。
【００７３】
図２に例示するように、第三実施形態の復号装置３１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部２１０４と第一計算部２１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部２１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と最終出力部１１１２と制御部１１１３と第三計算部３１０９とを有する。
【００７４】
図３に例示するように、第三実施形態の復号能力提供装置３２は、例えば、第一出力情報計算部２２０１と第二出力情報計算部２２０２と鍵記憶部１２０４と制御部１２０５と第三出力情報計算部３２０３とを有する。
【００７５】
＜復号処理＞
次に本形態の復号処理を説明する。第二実施形態との相違点を説明する。
【００７６】
図７及び図８に例示するように、第三実施形態の処理は第二実施形態のステップＳ２１０３〜Ｓ２１０５，Ｓ２１０８，Ｓ２２００〜Ｓ２２０３が、それぞれ、ステップＳ３１０３〜Ｓ３１０５，Ｓ３１０８，Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９に置換されたものである。以下ではステップＳ３１０３〜Ｓ３１０５，Ｓ３１０８，Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理を中心に説明する。
【００７７】
《ステップＳ３１０３の処理》
復号装置３１（図２）の入力情報提供部３１０４は、入力された暗号文ｘにそれぞれ対応する第一入力情報τ１及び第二入力情報τ２を生成して出力する（図７／ステップＳ３１０３）。
【００７８】
以下、図９を用いて本形態のステップＳ３１０３の処理を説明する。
【００７９】
制御部１１１３（図２）は、自然数選択部１１０２で選択された自然数（ａ，ｂ）に応じて入力情報提供部３１０４を制御する。
【００８０】
制御部１１１３でｂが１であるかが判定され（ステップＳ３１０３ａ）、ｂ≠１であると判定された場合、前述のステップＳ２１０３ａ及びＳ２１０３ｂの処理が実行され、ステップＳ３１０３ｇに進む。
【００８１】
一方、ステップＳ３１０３ａでｂ＝１であると判定された場合、第三乱数生成部３１０４ｅが、０以上ＫＨ未満の自然数の乱数ｒ３を生成する。生成された乱数ｒ３は第三入力情報計算部３１０４ｆ及び第三計算部３１０９に送られる（ステップＳ３１０３ｂ）。第三入力情報計算部３１０４ｆは、入力された乱数ｒ３と暗号文ｘとを用いてｘｒ３を計算し、これを第一入力情報τ１とする（ステップＳ３１０３ｃ）。その後、ステップＳ３１０３ｇに進む。
【００８２】
ステップＳ３１０３ｇでは、制御部１１１３でａが１であるかが判定され（ステップＳ３１０３ｇ）、ａ≠１であると判定された場合、前述のステップＳ２１０３ｃ及びステップＳ２１０３ｄの処理が実行される。
【００８３】
一方、ステップＳ３１０３ｇでａ＝１であると判定された場合、第三乱数生成部３１０４ｅが、０以上ＫＨ未満の自然数の乱数ｒ３を生成する。生成された乱数ｒ３は第三入力情報計算部３１０４ｆに送られる（ステップＳ３１０３ｈ）。第三入力情報計算部３１０４ｆは、入力された乱数ｒ３と暗号文ｘとを用いてｘｒ３を計算し、これを第二入力情報τ２とする（ステップＳ３１０３ｉ）。
【００８４】
第一入力情報計算部２１０４ｂ、第二入力情報計算部２１０４ｄ、第三入力情報計算部３１０４ｆは、以上のように生成した第一入力情報τ１及び第二入力情報τ２を対応する自然数（ａ，ｂ）の情報とともに出力する（ステップＳ３１０３ｅ）。なお、本形態の第一入力情報τ１及び第二入力情報τ２は、それぞれ、乱数ｒ１，ｒ２，ｒ３によって暗号文ｘとの関係をかく乱させた情報である。これにより、復号装置３１は、暗号文ｘを復号能力提供装置３２に対して隠蔽できる。
【００８５】
《Ｓ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理》
以下、図８を用いて本形態のＳ２２００〜Ｓ２２０３及びＳ３２０５〜Ｓ３２０９の処理を説明する。
【００８６】
制御部１２０５（図３）は、入力された自然数（ａ，ｂ）に応じ、第一出力情報計算部２２０１、第二出力情報計算部２２０２、及び第三出力情報計算部３２０３を制御する。
【００８７】
制御部１２０５の制御に基づき、ｂ≠１の場合の第一入力情報τ１＝μｈｒ１ｘｂは復号能力提供装置３２（図３）の第一出力情報計算部２２０１に入力され、ａ≠１の場合の第二入力情報τ２＝μｈｒ２ｘａは第二出力情報計算部２２０２に入力される。また、ｂ＝１の場合の第一入力情報τ１＝ｘｒ３やａ＝１の場合の第二入力情報τ２＝ｘｒ３は第三出力情報計算部３２０３に入力される（ステップＳ３２００）。
【００８８】
制御部１１１３でｂが１であるかが判定され（ステップＳ３２０５）、ｂ≠１であると判定された場合、前述のステップＳ２２０１の処理が実行される。その後、制御部１１１３でａが１であるかが判定され（ステップＳ３２０８）、ａ≠１であると判定された場合、前述したステップＳ２２０２の処理が実行されてステップＳ３２０３に進む。
【００８９】
一方、ステップＳ３２０８でａ＝１であると判定された場合、第三出力情報計算部３２０３は、第二入力情報τ２＝ｘｒ３を用い、或る確率より大きな確率でｆ（ｘｒ３）を正しく計算し、得られた計算結果を第三出力情報ｚ３とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部３２０３での計算結果がｆ（ｘｒ３）となる場合もあれば、ｆ（ｘｒ３）とならない場合もある（ステップＳ３２０９）。その後、ステップＳ３２０３に進む。
【００９０】
また、ステップＳ３２０５でｂ＝１であると判定された場合、第三出力情報計算部３２０３は、第二入力情報τ１＝ｘｒ３を用い、或る確率より大きな確率でｆ（ｘｒ３）を正しく計算し、得られた計算結果を第三出力情報ｚ３とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第三出力情報計算部３２０３での計算結果がｆ（ｘｒ３）となる場合もあれば、ｆ（ｘｒ３）とならない場合もある（ステップＳ３２０６）。
【００９１】
その後、制御部１１１３でａが１であるかが判定され（ステップＳ３２０７）、ａ＝１であると判定された場合にはステップＳ３２０３に進み、ａ≠１であると判定された場合にはステップＳ２２０２に進む。
【００９２】
ステップＳ３２０３では、第一出力情報ｚ１を生成した第一出力情報計算部２２０１は第一出力情報ｚ１を出力し、第二出力情報ｚ２を生成した第二出力情報計算部２２０２は第二出力情報ｚ２を出力し、第三出力情報ｚ３を生成した第三出力情報計算部２２０２は第三出力情報ｚ３を出力する（ステップＳ３２０３）。
【００９３】
《ステップＳ３１０４及びＳ３１０５の処理》
図７に戻り、制御部１１１３の制御のもと、第一出力情報ｚ１は復号装置３１（図２）の第一計算部２１０５に入力され、第二出力情報ｚ２は第二計算部２１０８に入力され、第三出力情報ｚ３は第三計算部３１０９に入力される（ステップＳ３１０４）。
【００９４】
ｂ≠１であれば、第一計算部２１０５が、前述のステップＳ２１０５の処理によってｕを生成し、ｂ＝１であれば、第三計算部３１０９が、ｚ３１／ｒ３を計算してその計算結果をｕとする。計算結果ｕは第一べき乗計算部１１０６に送られる。ここで、ｂ＝１の場合、ｕ＝ｚ３１／ｒ３＝ｆ（ｘ）ｘ３となる。すなわち、ｚ３１／ｒ３は、ｆ（ｘ）について誤差Ｘ３を持つ標本器となる。その理由については後述する（ステップＳ３１０５）。
【００９５】
《ステップＳ３１０８の処理》
ａ≠１であれば、第二計算部２１０８が、前述のステップＳ２１０８の処理によってｖを生成し、ａ＝１であれば、第三計算部３１０９が、ｚ３１／ｒ３を計算してその計算結果をｖとする。計算結果ｖは第二べき乗計算部１１０９に送られる。ここで、ａ＝１の場合、ｖ＝ｚ３１／ｒ３＝ｆ（ｘ）ｘ３となる。すなわち、ｚ３１／ｒ３は、ｆ（ｘ）について誤差Ｘ３を持つ標本器となる。その理由については後述する（ステップＳ３１０８）。
【００９６】
なお、ｚ３１／ｒ３の計算、すなわちｚ３のべき乗根の計算が困難な場合には、次のようにしてｕ及び／又はｖを計算してもよい。第三計算部３１０９は、乱数ｒ３とその乱数ｒ３に基づいて計算されたｚ３の組を順次（α１，β１），（α２，β２），…，（αｍ，βｍ），…として図示していない記憶部に記憶する。ｍは１以上の自然数である。第三計算部３１０９は、α１，α２，…，αｍの最小公倍数が１になれば、γ１，γ２，…，γｍを整数としてγ１α１＋γ２α２＋…＋γｍαｍ＝１となるγ１，γ２，…，γｍを計算して、そのγ，γ２，…，γｍを用いてΠｉ＝１ｍβｉγｉ＝β１γ１β２γ２…βｍγｍを計算して、その計算結果をｕ及び／又はｖとしてもよい。
【００９７】
≪ｚ３１／ｒ３がｆ（ｘ）について誤差Ｘ３を持つ標本器となる理由について≫
Ｒを乱数として、復号能力提供装置３２がｘＲを用いて行う計算の計算結果をＢ（ｘＲ）とする。すなわち、第一出力情報計算部２２０１や第二出力情報計算部２２０２や第三出力情報計算部３２０３が復号装置３１に返す計算結果をｚ＝Ｂ（xＲ）とする。さらに、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（ｘＲ）１／Ｒｆ（ｘ）−１と定義する。
【００９８】
このとき、ｚ１／Ｒ＝Ｂ（ｘＲ）１／Ｒ＝Ｘｆ（ｘ）＝ｆ（ｘ）Ｘとなる。すなわち、ｚ１／Ｒは、ｆ（ｘ）について誤差Ｘを持つ標本器となる。
【００９９】
上記式展開において、Ｘ＝Ｂ（ｘＲ）１／Ｒｆ（ｘＲ）−１であり、Ｂ（ｘＲ）１／Ｒ＝Ｘｆ（ｘＲ）であるという性質を用いている。この性質は、Ｒが乱数であることに基づく。
【０１００】
したがって、ｒ３が乱数であることを考慮すると、同様に、ｚ３１／ｒ３がｆ（ｘ）について誤差Ｘ３を持つ標本器となるのである。
【０１０１】
［第四実施形態］
第四実施形態の復号制御システムは、上述した第一乱数化可能標本器及び第二乱数化可能標本器を具体化した他の例である。具体的には、Ｈ＝Ｇ×Ｇ、復号関数ｆ（ｘ）がＥｌＧａｍａｌ暗号の復号関数、すなわち復号鍵ｓ及び暗号文ｘ＝（ｃ１，ｃ２）に対してｆ（ｃ１，ｃ２）＝ｃ１ｃ２−ｓである場合の第一乱数化可能標本器及び第二乱数化可能標本器の例を具体化したものである。以下、第一実施形態と異なる部分を中心に説明し、復号制御処理などの共通する部分については重複説明を省略する。
【０１０２】
図１に例示するように、第四実施形態の復号制御システム４は、復号装置１１が復号装置４１に置換され、復号能力提供装置１２が復号能力提供装置４２に置換されたものである。
【０１０３】
図２に例示するように、第四実施形態の復号装置４１は、例えば、自然数記憶部１１０１と自然数選択部１１０２と整数計算部１１０３と入力情報提供部４１０４と第一計算部４１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部４１０８と第二べき乗計算部１１０９と第二リスト記憶部１１１０と判定部１１１１と最終出力部１１１２と制御部１１１３とを有する。図６に例示するように、本形態の入力情報提供部４１０４は、例えば、第四乱数生成部４１０４ａと第五乱数生成部４１０４ｂと第一入力情報計算部４１０４ｃと第六乱数生成部４１０４ｄと第七乱数生成部４１０４ｅと第二入力情報計算部４１０４ｆとを有する。第一入力情報計算部４１０４ｃは、例えば、第四入力情報計算部４１０４ｃａと第五入力情報計算部４１０４ｃｂとを有し、第二入力情報計算部４１０４ｆは、第六入力情報計算部４１０４ｆａと第七入力情報計算部４１０４ｆｂとを有する。
【０１０４】
図３に例示するように、第四実施形態の復号能力提供装置４２は、例えば、第一出力情報計算部４２０１と第二出力情報計算部４２０２と鍵記憶部１２０４と制御部１２０５とを有する。
【０１０５】
＜復号処理＞
次に本形態の復号処理を説明する。第四実施形態では、群Ｈ＝Ｇ×Ｇ、暗号文ｘ＝（ｃ１，ｃ２）∈Ｈであり、ｆ（ｃ１，ｃ２）が準同型関数であり、群Ｇの生成元をμｇとし、群Ｇの位数をＫＧとし、同じ復号鍵ｓに対する暗号文（Ｖ，Ｗ）∈Ｈとその暗号文を復号した復号文ｆ（Ｖ，Ｗ）＝Ｙ∈Ｇとの組が復号装置４１及び復号能力提供装置４２に事前設定され、復号装置４１及び復号能力提供装置４２がこの組を利用可能とされているものとする。
【０１０６】
図７及び図８に例示するように、第四実施形態の処理は第一実施形態のステップＳ１１０３〜Ｓ１１０５，Ｓ１１０８，Ｓ１２００〜Ｓ１２０３が、それぞれ、ステップＳ４１０３〜Ｓ４１０５，Ｓ４１０８，Ｓ４２００〜Ｓ４２０３に置換されたものである。以下ではステップＳ４１０３〜Ｓ４１０５，Ｓ４１０８，Ｓ４２００〜Ｓ４２０３の処理のみを説明する。
【０１０７】
《ステップＳ４１０３の処理》
復号装置４１（図２）の入力情報提供部４１０４は、入力された暗号文ｘ＝（ｃ１，ｃ２）に対応する第一入力情報τ１及び暗号文ｘ＝（ｃ１，ｃ２）に対応する第二入力情報τ２を生成して出力する（図７／ステップＳ４１０３）。以下、図１０を用いて本形態のステップＳ４１０３の処理を説明する。
【０１０８】
第四乱数生成部４１０４ａ（図６）は、０以上ＫＧ未満の自然数の一様乱数ｒ４を生成する。生成された乱数ｒ４は、第四入力情報計算部４１０４ｃａ、第五入力情報計算部４１０４ｃｂ、及び第一計算部４１０５に送られる（ステップＳ４１０３ａ）。第五乱数生成部４１０４ｂは、０以上ＫＧ未満の自然数の一様乱数ｒ５を生成する。生成された乱数ｒ５は、第五入力情報計算部４１０４ｃｂ、及び第一計算部４１０５に送られる（ステップＳ４１０３ｂ）。
【０１０９】
第四入力情報計算部４１０４ｃａは、自然数選択部１１０２で選択された自然数ｂ、暗号文ｘが含むｃ２、及び乱数ｒ４を用い、第四入力情報ｃ２ｂＷｒ４を計算する（ステップＳ４１０３ｃ）。第五入力情報計算部４１０４ｃｂは、自然数選択部１１０２で選択された自然数ｂ、暗号文ｘが含むｃ１、及び乱数ｒ４，ｒ５を用い、第五入力情報ｃ１ｂＶｒ４μｇｒ５を計算する（ステップＳ４１０３ｄ）。
【０１１０】
第六乱数生成部４１０４ｄは、０以上ＫＧ未満の自然数の一様乱数ｒ６を生成する。生成された乱数ｒ６は、第六入力情報計算部４１０４ｆａ、第七入力情報計算部４１０４ｆｂ、及び第二計算部４１０８に送られる（ステップＳ４１０３ｅ）。第七乱数生成部４１０４ｅは、０以上ＫＧ未満の自然数の一様乱数ｒ７を生成する。生成された乱数ｒ７は、第七入力情報計算部４１０４ｆｂ、及び第二計算部４１０８に送られる（ステップＳ４１０３ｆ）。
【０１１１】
第六入力情報計算部４１０４ｆａは、自然数選択部１１０２で選択された自然数ａ、暗号文ｘが含むｃ２、及び乱数ｒ６を用い、第六入力情報ｃ２ａＷｒ６を計算する（ステップＳ４１０３ｇ）。第七入力情報計算部４１０４ｆｂは、自然数選択部１１０２で選択された自然数ａ、暗号文ｘが含むｃ１、及び乱数ｒ６，ｒ７を用い、第七入力情報ｃ１ａＶｒ６μｇｒ７を計算する（ステップＳ４１０３ｈ）。
【０１１２】
第一入力情報計算部４１０４ｃは、以上のように生成した第四入力情報ｃ２ｂＷｒ４及び第五入力情報ｃ１ｂＶｒ４μｇｒ５を第一入力情報τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）として出力する。第二入力情報計算部４１０４ｆは、以上のように生成した第六入力情報ｃ２ａＷｒ６及び第七入力情報ｃ１ａＶｒ６μｇｒ７を第二入力情報τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）として出力する（ステップＳ４１０３ｉ）。
【０１１３】
《ステップＳ４２００〜Ｓ４２０３の処理》
図８に例示するように、まず、第一入力情報τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）が復号能力提供装置４２（図３）の第一出力情報計算部４２０１に入力され、第二入力情報τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）が第二出力情報計算部４２０２に入力される（ステップＳ４２００）。
【０１１４】
第一出力情報計算部４２０１は、第一入力情報τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）と鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）を正しく計算し、計算結果を第一出力情報ｚ１とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部４２０１での計算結果がｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）となる場合もあれば、ｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）とならない場合もある（ステップＳ４２０１）。
【０１１５】
第二出力情報計算部４２０２は、第二入力情報τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）と鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）を正しく計算可能であり、得られた計算結果を第二出力情報ｚ２とする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部４２０２での計算結果がｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）となる場合もあれば、ｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）とならない場合もある（ステップＳ４２０２）。
【０１１６】
第一出力情報計算部４２０１は第一出力情報ｚ１を出力し、第二出力情報計算部４２０２は第二出力情報ｚ２を出力する（ステップＳ４２０３）。
【０１１７】
《ステップＳ４１０４及びＳ４１０５の処理》
図７に戻り、第一出力情報ｚ１は復号装置４１（図２）の第一計算部４１０５に入力され、第二出力情報ｚ２は第二計算部４１０８に入力される（ステップＳ４１０４）。
【０１１８】
第一計算部４１０５は、入力された第一出力情報ｚ１及び乱数ｒ４，ｒ５を用い、ｚ１Ｙ−ｒ４μｇ−ｒ５を計算してその計算結果をｕとする（ステップＳ４１０５）。計算結果ｕは、第一べき乗計算部１１０６に送られる。ここで、ｕ＝ｚ１Ｙ−ｒ４μｇ−ｒ５＝ｆ（ｃ１，ｃ２）ｂｘ１となる。すなわち、ｚ１Ｙ−ｒ４μｇ−ｒ５は、ｆ（ｃ１，ｃ２）について誤差Ｘ１を持つ乱数化可能標本器の出力となる。その理由については後述する。
【０１１９】
《ステップＳ４１０８の処理》
第二計算部４１０８は、入力された第二出力情報ｚ２及び乱数ｒ６，ｒ７を用い、ｚ２Ｙ−ｒ６μｇ−ｒ７を計算してその計算結果をｖとする。計算結果ｖは、第二べき乗計算部１１０９に送られる。ここで、ｖ＝ｚ２Ｙ−ｒ６μｇ−ｒ７＝ｆ（ｃ１，ｃ２）ａｘ２となる。すなわち、ｚ２Ｙ−ｒ６μｇ−ｒ７は、ｆ（ｃ１，ｃ２）について誤差Ｘ２を持つ乱数化可能標本器の出力となる。その理由については後述する。
【０１２０】
≪ｚ１Ｙ−ｒ４μｇ−ｒ５，ｚ２Ｙ−ｒ６μｇ−ｒ７がｆ（ｃ１，ｃ２）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器の出力となる理由について≫
ｃを自然数、Ｒ１、Ｒ２、Ｒ１’及びＲ２’を乱数として、復号能力提供装置４２がｃ１ｃＶＲ１μｇＲ２及びｃ２ｃＷＲ１を用いて行う計算の計算結果をＢ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）とする。すなわち、第一出力情報計算部４２０１や第二出力情報計算部４２０２が復号装置４１に返す計算結果をｚ＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）とする。さらに、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（ＶＲ１’μｇＲ２’，ＷＲ１’）ｆ（ＶＲ１’μｇＲ２’，ＷＲ１’）−１と定義する。
【０１２１】
このとき、ｚＹ−Ｒ１μｇ−Ｒ２＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１，ｃ２）ｃｆ（Ｖ，Ｗ）Ｒ１ｆ（μｇ，ｅｇ）Ｒ２Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１，ｃ２）ｃＹＲ１μｇＲ２Ｙ−Ｒ１μｇ−Ｒ２＝ｆ（ｃ１，ｃ２）ｃＸとなる。すなわち、ｚＹ−Ｒ１μｇ−Ｒ２は、ｆ（ｘ）について誤差Ｘを持つ乱数化可能標本器の出力となる。なお、ｅｇは、群Ｇの単位元である。
【０１２２】
上記式展開において、Ｘ＝Ｂ（ＶＲ１’μｇＲ２’，ＷＲ１’）ｆ（ＶＲ１’μｇＲ２’，ＷＲ１’）−１＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）ｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）であり、Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）＝Ｘｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）であるという性質を用いている。この性質は、Ｒ１、Ｒ２、Ｒ１’及びＲ２’が乱数であることに基づく。
【０１２３】
したがって、ａ，ｂが自然数、ｒ４，ｒ５，ｒ６及びｒ７が乱数であることを考慮すると、同様に、ｚ１Ｙ−ｒ４μｇ−ｒ５，ｚ２Ｙ−ｒ６μｇ−ｒ７がｆ（ｃ１，ｃ２）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器の出力となるのである。
【０１２４】
［第五実施形態］
上述の各実施形態では、復号装置の自然数記憶部１１０１に、互いに素である２つの自然数ａ，ｂの組（ａ，ｂ）が複数種類記憶され、これらの組（ａ，ｂ）を用いて各処理が実行されることとした。しかしながら、ａ，ｂの一方が定数であってもよい。例えば、ａが１に固定されていてもよいし、ｂが１に固定されていてもよい。言い換えると、第一乱数化可能標本器又は第二乱数化可能標本器の一方が標本器に置換されていてもよい。ａ，ｂの一方が定数である場合、定数とされたａ又はｂを選択する処理が不要となり、各処理部は定数とされたａ又はｂが入力されることなく、それを定数として扱って計算を行うことができる。また、定数とされたａ又はｂが１である場合には、ａ’やｂ’を用いることなく、ｆ（ｘ）＝ｕｂ’ｖａ’をｆ（ｘ）＝ｖ又はｆ（ｘ）＝ｕとして得ることができる。
【０１２５】
第五実施形態は、そのような変形の一例であり、ｂが１に固定され、第二乱数化可能標本器が標本器に置換された形態である。以下では、第一実施形態との相違点を中心に説明し、復号制御処理などの第一実施形態と共通する事項については説明を省略する。また、第一乱数化可能標本器や標本器の具体例も、第二実施形態から第四実施形態で説明したのと同様であるため、説明を省略する。
【０１２６】
＜構成＞
図１に例示するように、第五実施形態の復号制御システム５は、第一実施形態の復号装置１１が復号装置５１に置換され、復号能力提供装置１２が復号能力提供装置５２に置換されたものである。
【０１２７】
図１１に例示するように、第五実施形態の復号装置５１は、例えば、自然数記憶部５１０１と自然数選択部５１０２と入力情報提供部５１０４と第一計算部５１０５と第一べき乗計算部１１０６と第一リスト記憶部１１０７と第二計算部５１０８と第二リスト記憶部５１１０と判定部５１１１と最終出力部１１１２と制御部１１１３とを有する。
【０１２８】
図３に例示するように、第五実施形態の復号能力提供装置５２は、例えば、第一出力情報計算部５２０１と第二出力情報計算部５２０２と鍵記憶部１２０４と制御部１２０５とを有する。
【０１２９】
＜復号処理＞
次に本形態の復号処理を説明する。復号処理の前提として、Ｇ，Ｈを巡回群、ｆ（ｘ）を群Ｈの元である暗号文ｘを特定の復号鍵ｓで復号して群Ｇの元を得るための復号関数、群Ｇ，Ｈの生成元をそれぞれμｇ，μｈ、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２とする。また、復号装置５１の自然数記憶部５１０１には、自然数ａが複数種類記憶されているものとする。
【０１３０】
図１２に例示するように、まず、復号装置５１（図１１）の自然数選択部５１０２が、自然数記憶部５１０１に記憶された複数の自然数ａから１つの自然数ａをランダムに読み込む。読み込まれた自然数ａの情報は、入力情報提供部５１０４及び第一べき乗計算部１１０６に送られる（ステップＳ５１００）。
【０１３１】
制御部１１１３は、ｔ＝１とする（ステップＳ１１０２）。
【０１３２】
入力情報提供部５１０４は、入力された暗号文ｘにそれぞれ対応する第一入力情報τ１及び第二入力情報τ２を生成して出力する。好ましくは、第一入力情報τ１及び第二入力情報τ２はそれぞれ暗号文ｘとの関係をかく乱させた情報である。これにより、復号装置５１は、暗号文ｘを復号能力提供装置５２に対して隠蔽できる。また、好ましくは、本形態の第二入力情報τ２は自然数選択部５１０２で選択された自然数ａにさらに対応する。これにより、復号能力提供装置５２から提供された復号能力を復号装置５１が高い精度で評価できる（ステップＳ５１０３）。第一入力情報τ１及び第二入力情報τ２の組みの具体例は、第二実施形態から第四実施形態の何れかのｂ＝１とした第一入力情報τ１及び第二入力情報τ２の組みである。
【０１３３】
図８に例示するように、第一入力情報τ１は復号能力提供装置５２（図３）の第一出力情報計算部５２０１に入力され、第二入力情報τ２は第二出力情報計算部５２０２に入力される（ステップＳ５２００）。
【０１３４】
第一出力情報計算部５２０１は、第一入力情報τ１と鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果を第一出力情報ｚ１とする（ステップＳ５２０１）。第二出力情報計算部５２０２は、第二入力情報τ２と鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた演算結果を第二出力情報ｚ２とする（ステップＳ５２０２）。すなわち、第一出力情報計算部５２０１や第二出力情報計算部５２０２は、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部５２０１での計算結果がｆ（τ１）の場合もあればｆ（τ１）でない場合もあり、第二出力情報計算部５２０２での計算結果がｆ（τ２）の場合もあればｆ（τ２）でない場合もある。第一出力情報ｚ１及び第二出力情報ｚ２の組の具体例は、第二実施形態から第四実施形態の何れかのｂ＝１とした第一出力情報ｚ１及び第二出力情報ｚ２の組である。
【０１３５】
第一出力情報計算部５２０１は第一出力情報ｚ１を出力し、第二出力情報計算部５２０２は第二出力情報ｚ２を出力する（ステップＳ５２０３）。
【０１３６】
図１２に戻り、第一出力情報ｚ１は復号装置５１（図１１）の第一計算部５１０５に入力され、第二出力情報ｚ２は第二計算部５１０８に入力される。これらの第一出力情報ｚ１及び第二出力情報ｚ２が、復号能力提供装置５２から復号装置５１に与えられた復号能力に相当する（ステップＳ５１０４）。
【０１３７】
第一計算部５１０５は、第一出力情報ｚ１から演算結果ｕ＝ｆ（ｘ）ｘ１を生成する。演算結果ｕの具体例は、第二実施形態から第四実施形態の何れかのｂ＝１とした演算結果ｕである。演算結果ｕは第一べき乗計算部１１０６に送られる（ステップＳ５１０５）。
【０１３８】
第一べき乗計算部１１０６はｕ’＝ｕａを計算する。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部１１０７に記憶される（ステップＳ１１０６）。
【０１３９】
第二計算部５１０８は、第二出力情報ｚ２から演算結果ｖ＝ｆ（ｘ）ａｘ２を生成する。演算結果ｖの具体例は、第二実施形態から第四実施形態の何れかの演算結果ｖである。演算結果ｖは第二リスト記憶部５１１０に記憶される（ステップＳ５１０８）。
【０１４０】
判定部５１１１は、第一リスト記憶部１１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部５１１０に記憶されたｖの中で、ｕ’＝ｖとなるものがあるか判定する（ステップＳ５１１０）。ｕ’＝ｖとなるものがあった場合には、ステップＳ５１１４に進む。ｕ’＝ｖとなるものがなかった場合には、ステップＳ１１１１に進む。
【０１４１】
ステップＳ１１１１では、制御部１１１３がｔ＝Ｔであるか判定する（ステップＳ１１１１）。Ｔは予め定められた１以上の自然数である。ｔ＝Ｔであれば、最終出力部１１１２が、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１１３）、処理を終える。ｔ＝Ｔでない場合には、制御部１１１３は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ１１１２）、ステップＳ５１０３に戻る。
【０１４２】
ステップＳ５１１４では、最終出力部１１１２が、ｕ’＝ｖであると判定されたｕ’に対応するｕを出力する（ステップＳ５１１４）。このように得られたｕは、第一実施形態から第四実施形態でｂ＝１とした場合のｕｂ’ｖａ’に相当する。すなわち、このように得られたｕは高い確率で暗号文ｘを特定の復号鍵ｓで復号した復号結果ｆ（ｘ）となる。よって、上述した処理を複数回繰り返し、ステップＳ５１１４で得られた値のうち最も頻度の高い値を復号結果とすればよい。また、後述するように、設定によっては圧倒的な確率でｕ＝ｆ（ｘ）となる。その場合にはステップＳ５１１４で得られた値をそのまま復号結果としてよい。
【０１４３】
≪復号結果ｆ（ｘ）が得られる理由について≫
次に、本形態の復号装置５１で復号結果ｆ（ｘ）が得られる理由を説明する。まず、説明に必要な事項を定義する。
【０１４４】
ブラックボックス（ｂｌａｃｋ−ｂｏｘ）：
ｆ（τ）のブラックボックスＦ（τ）とは、τ∈Ｈを入力としてｚ∈Ｇを出力する処理部を意味する。本形態では、第一出力情報計算部５２０１及び第二出力情報計算部５２０２が、それぞれ復号関数ｆ（τ）のブラックボックスＦ（τ）に相当する。群Ｈから任意に選択された元τ∈ＵＨ及びｚ＝Ｆ（τ）に対してｚ＝ｆ（τ）を満たす確率がδ（０＜δ≦１）よりも大きい場合、すなわち、
Ｐｒ［ｚ＝ｆ（τ）｜τ∈ＵＨ，ｚ＝Ｆ（τ）］＞δ      …（１）
を満たすｆ（τ）のブラックボックスＦ（τ）のことを、信頼性δ（δ−ｒｅｌｉａｂｌｅ）のｆ（τ）のブラックボックスＦ（τ）という。なお、δは正の値であり、前述した「或る確率」に相当する。
【０１４５】
自己訂正器（ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘ）とは、ｘ∈Ｈを入力とし、ｆ（τ）のブラックボックスＦ（τ）を用いて計算を行い、ｊ∈Ｇ∪⊥を出力する処理部を意味する。本形態では、復号装置５１が自己訂正器ＣＦ（ｘ）に相当する。
【０１４６】
オールモスト自己訂正器（ａｌｍｏｓｔ  ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘ）が、ｘ∈Ｈを入力とし、δ−ｒｅｌｉａｂｌｅのｆ（τ）のブラックボックスＦ（τ）を用い、正しい値ｊ＝ｆ（ｘ）を出力する確率が、誤った値ｊ≠ｆ（ｘ）を出力する確率よりも十分大きい場合を想定する。すなわち、
Ｐｒ［ｊ＝ｆ（ｘ）｜ｊ＝ＣＦ（ｘ），ｊ≠⊥］
＞Ｐｒ［ｊ≠ｆ（ｘ）｜ｊ＝ＣＦ（ｘ），ｊ≠⊥］＋Δ      …（２）
を満たす場合を想定する。なお、Δは或る正の値（０＜Δ＜１）である。このような場合、自己訂正器ＣＦ（ｘ）はオールモスト自己訂正器であるという。例えば、或る正の値Δ’（０＜Δ’＜１）に対して
Ｐｒ［ｊ＝ｆ（ｘ）｜ｊ＝ＣＦ（ｘ）］＞（１／３）＋Δ’
Ｐｒ［ｊ＝⊥｜ｊ＝ＣＦ（ｘ）］＜１／３
Ｐｒ［ｊ≠ｆ（ｘ）かつｊ≠⊥｜ｊ＝ＣＦ（ｘ）］＜１／３
を満たす場合、自己訂正器ＣＦ（ｘ）はオールモスト自己訂正器である。Δ’の例はΔ’＝１／１２や１／３である。
【０１４７】
ローバスト自己訂正器（ｒｏｂｕｓｔ  ｓｅｌｆ−ｃｏｒｒｅｃｔｏｒ）：
自己訂正器ＣＦ（ｘ）が、ｘ∈Ｈを入力とし、δ−ｒｅｌｉａｂｌｅのｆ（τ）のブラックボックスＦ（τ）を用い、正しい値ｊ＝ｆ（ｘ）又はｊ＝⊥を出力する確率が圧倒的である場合を想定する。すなわち、無視することができる誤差ξ（０≦ξ＜１）に対して
Ｐｒ［ｊ＝ｆ（ｘ）またはｊ＝⊥｜ｊ＝ＣＦ（ｘ）］＞１−ξ      …（３）
を満たす場合を想定する。このような場合、自己訂正器ＣＦ（ｘ）はローバスト自己訂正器であるという。なお、無視することができる誤差ξの例は、セキュリティパラメータｋの関数値ξ（ｋ）である。関数値ξ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きいｋに対して｛ξ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数値ξ（ｋ）の具体例は、ξ（ｋ）＝２−ｋやξ（ｋ）＝２−√ｋなどである。
【０１４８】
また、オールモスト自己訂正器からローバスト自己訂正器を構成することができる。すなわち、同一のｘに対してオールモスト自己訂正器を複数回実行させ、⊥を除いて最も頻度が高い出力値をｊとすることで、ローバスト自己訂正器を構成できる。例えば、同一のｘに対してオールモスト自己訂正器をＯ（ｌｏｇ（１／ξ））回実行させ、最も頻度が高い出力値をｊとすることで、ローバスト自己訂正器を構成できる。なお、Ｏ（・）はオー記法を表す。
【０１４９】
擬似自由（ｐｓｅｕｄｏ−ｆｒｅｅ）な作用：
群Ｇ、自然数の集合Ω＝｛０，．．．，Ｍ｝（Ｍは１以上の自然数）、群Ｇに値を持つ確率変数Ｘ１，Ｘ２の各実現値α∈Ｘ１（α≠ｅｇ），β∈Ｘ２、及びａ∈Ωについて、αａ＝βとなる確率
Ｐｒ［αａ＝βかつα≠ｅｇ｜ａ∈ＵΩ，α∈Ｘ１，β∈Ｘ２］      …（４）
について、あらゆる可能なＸ１，Ｘ２に関する上限値を、組（Ｇ，Ω）の疑似自由指標とよび、これをＰ（Ｇ，Ω）と表すことにする。ある無視することができる関数ζ（ｋ）が存在して、
Ｐ（Ｇ，Ω）＜ζ（ｋ）      …（５）
である場合、組（Ｇ，Ω）によって定義される演算は擬似自由な作用であるという。なお、「αａ」は、群Ｇで定義された演算をαに対してａ回作用させることを意味する。また、無視することができる関数ζ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きいｋに対して｛ζ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数ζ（ｋ）の具体例は、ζ（ｋ）＝２−ｋやζ（ｋ）＝２−√ｋなどである。例えば、セキュリティパラメータｋとに対し、式（４）の確率がＯ（２−k）未満である場合、組（Ｇ，Ω）によって定義される演算は擬似自由な作用である。また、例えば、任意の∀α∈Ｇでα≠ｅｇであるものについて、集合Ω・α＝｛ａ（α）｜ａ∈Ω｝の要素数｜Ω・α｜が２ｋを超える場合、組（Ｇ，Ω）によって定義される演算は擬似自由な作用といえる。なお、ａ（α）は、ａとαに所定の演算を作用させた結果を表す。このような具体例は数多く存在する。例えば、群Ｇが素数ｐを法とする剰余群Ｚ／ｐＺであり、素数ｐが２ｋのオーダーであり、集合Ω＝｛０，．．．，ｐ−２｝であり、ａ（α）がαａ∈Ｚ／ｐＺであり、α≠ｅｇである場合、Ω・α＝｛αａ｜ａ＝０，．．．，ｐ−２｝＝｛ｅｇ，α１，．．．，αｐ−２｝となり、｜Ω・α｜＝ｐ−１である。素数ｐが２ｋのオーダーであるため、ある定数Ｃが存在して、ｋが十分大きければ｜Ω・α｜＞Ｃ２ｋを満たす。ここで式（４）の確率はＣ−１２−ｋ未満であり、このような組（Ｇ，Ω）によって定義される演算は擬似自由な作用である。
【０１５０】
信頼性δγ（δγ−ｒｅｌｉａｂｌｅ）の乱数化可能標本器：
自然数ａが与えられるたびに、δ−ｒｅｌｉａｂｌｅのｆ（τ）のブラックボックスＦ（τ）を用い、ｗ∈Ｇについて、確率変数Ｘに従った標本ｘ’に対応するｗａｘ’を返す乱数化可能標本器であって、ｗａｘ’＝ｗａである確率がδγよりも大きい（γは正定数）、すなわち、
Ｐｒ［ｗａｘ’＝ｗａ］＞δγ      …（６）
を満たすものを、信頼性δγな乱数化可能標本器という。本形態の入力情報提供部５１０４と第二出力情報計算部５２０２と第二計算部５１０８との組は、ｗ＝ｆ（ｘ）について、信頼性δγな乱数化可能標本器である。
【０１５１】
次に、これらの定義を用い、本形態の復号装置５１で復号結果ｆ（ｘ）が得られる理由を説明する。
【０１５２】
本形態のステップＳ５１１０ではｕ’＝ｖであるか、すなわち、ｕａ＝ｖであるかを判定している。本形態の入力情報提供部５１０４と第二出力情報計算部５２０２と第二計算部５１０８との組は信頼性δγな乱数化可能標本器であるため（式（６））、Ｔをｋ，δ，γから定まる一定値よりも大きい値とすれば、漸近的に大きい確率でｕａ＝ｖが成立する（ステップＳ５１１０でｙｅｓとなる）場合が生じる。たとえば、Ｔ≧４／δγとすれば、ｕａ＝ｖが成立する（ステップＳ５１１０でｙｅｓとなる）確率は１／２よりも大きいことがＭａｒｋｏｖの不等式によってわかる。
【０１５３】
また、本形態ではｕ＝ｆ（ｘ）ｘ１及びｖ＝ｆ（ｘ）ａｘ２なのであるから、ｕａ＝ｖが成立する場合にはｘ１ａ＝ｘ２が成立する。ｘ１ａ＝ｘ２が成立する場合には、ｘ１＝ｘ２＝ｅｇである場合とｘ１≠ｅｇである場合とがある。ｘ１＝ｘ２＝ｅｇである場合には、ｕ＝ｆ（ｘ）となるのであるから、ステップＳ５１１４で出力されるｕは正しい復号結果ｆ（ｘ）となる。一方、ｘ１≠ｅｇである場合には、ｕ≠ｆ（ｘ）となるのであるから、ステップＳ５１１４で出力されるｕは正しい復号結果ｆ（ｘ）ではない。
【０１５４】
群Ｇと自然数ａが属する集合Ωとの組（Ｇ，Ω）によって定義される演算が擬似自由な作用であるか、疑似自由指標Ｐ（Ｇ，Ω）についてＴ２Ｐ（Ｇ，Ω）が漸近的に小さい場合、ｕａ＝ｖの場合にｘ１≠ｅｇである確率（式（４））は漸近的に小さい。したがって、ｕａ＝ｖの場合にｘ１＝ｅｇである確率は漸近的に大きい。よって、組（Ｇ，Ω）によって定義される演算が擬似自由な作用であるか、Ｔ２Ｐ（Ｇ，Ω）が漸近的に小さい場合、ｕａ＝ｖの場合に誤った復号結果ｆ（ｘ）が出力される確率は、ｕａ＝ｖの場合に正しい復号結果ｆ（ｘ）が出力される確率よりも十分小さい。この場合の復号装置５１はオールモスト自己訂正器であるといえる（式（２）参照）。そのため、前述のように、復号装置５１からローバスト自己訂正器を構成することが可能であり、圧倒的な確率で正しい復号結果ｆ（ｘ）を得ることができる。（Ｇ，Ω）で定義される演算が疑似自由な作用である場合には、ｕａ＝ｖの場合に誤った復号結果ｆ（ｘ）が出力される確率も無視できる。この場合の復号装置５１は、圧倒的な確率で正しい復号結果ｆ（ｘ）または⊥を出力する。
【０１５５】
なお、任意の定数ρに対してｋ０が定まり、このｋ０に対してｋ０＜ｋ’を満たす任意のｋ’に対する関数値η（ｋ’）がρ未満となる場合「η（ｋ’）が漸近的に小さい」という。ｋ’の例はセキュリティパラメータｋである。
【０１５６】
また、任意の定数ρに対してｋ０が定まり、このｋ０に対してｋ０＜ｋ’を満たす任意のｋ’に対する関数値１−η（ｋ’）がρ未満となる場合「η（ｋ’）が漸近的に大きい」という。
【０１５７】
なお、ａをａ／ｂに置換すれば分かるように、上述の証明は第一実施形態で述べた「ｕ’＝ｖ’が成立するのは、第一乱数化可能標本器がｕ＝ｆ（φ）ｂを正しく計算しており、第二乱数化可能標本器がｖ＝ｆ（φ）ａを正しく計算している（ｘ１及びｘ２が群Ｇの単位元ｅｇである）可能性が高い」ことの証明ともなる。
【０１５８】
《信頼性δγな乱数化可能標本器と安全性について》
以下のような攻撃を想定する。
【０１５９】
・ブラックボックスＦ（τ）又はその部分が意図的に不正なｚを出力する、又は、ブラックボックスＦ（τ）から出力された値が不正なｚに改ざんされる。
・不正なｚに対応するｗａｘ’が乱数化可能標本器から出力される。
・不正なｚに対応するｗａｘ’は、自己訂正器ＣＦ（ｘ）でｕａ＝ｖが成立する（ステップＳ５１１０でｙｅｓなる）にもかかわらず、自己訂正器ＣＦ（ｘ）が誤った値を出力する確率を増加させる。
【０１６０】
このような攻撃は、与えられた自然数ａに対して乱数化可能標本器から出力されたｗａｘ’の誤差の確率分布Ｄａ＝ｗａｘ’ｗ−ａが自然数ａに依存する場合に可能となる。例えば、第二計算部５１０８から出力されるｖがｆ（ｘ）ａｘ１ａとなるような不正が行われた場合、ｘ１の値にかかわらず、必ずｕａ＝ｖが成立することになる。よって、与えられた自然数ａに対して乱数化可能標本器から出力されたｗａｘ’の誤差の確率分布Ｄａ＝ｗａｘ’ｗ−ａが当該自然数ａに依存しないことが望ましい。
【０１６１】
あるいは、、集合Ωのいかなる元ａ∈∀Ωについても、ｗａｘ’の誤差の確率分布Ｄａ＝ｗａｘ’ｗ−ａと区別することができない群Ｇに値を持つ確率分布Ｄが存在する（確率分布Ｄａと確率分布Ｄとが統計的に近似する（ｓｔａｔｉｓｔｉｃａｌｌｙ−ｃｌｏｓｅ））乱数化可能標本器であることが望ましい。なお、確率分布Ｄは自然数ａに依存しない。また、確率分布Ｄａと確率分布Ｄとを区別することができないとは、多項式時間アルゴリズムによって確率分布Ｄａと確率分布Ｄとを区別することができないことを意味し、例えば、無視することができるζ（０≦ζ＜１）に対して
Σｇ∈Ｇ｜Ｐｒ［ｇ∈Ｄ］−Ｐｒ［ｇ∈Ｄａ］｜＜ζ      …（７）
を満たすならば、多項式時間アルゴリズムによって確率分布Ｄａと確率分布Ｄとを区別することができない。無視することができるζの例は、セキュリティパラメータｋの関数値ζ（ｋ）である。関数値ζ（ｋ）の例は、任意の多項式ｐ（ｋ）について、十分大きいｋに対して｛ζ（ｋ）ｐ（ｋ）｝が０に収束するものである。関数値ζ（ｋ）の具体例は、ζ（ｋ）＝２−ｋやζ（ｋ）＝２−√ｋなどである。また、これらの点は自然数ａ及びｂを使用する第一実施形態から第四実施形態についても同様である。
【０１６２】
［変形例等］
確率変数Ｘ１、Ｘ２及びＸ３は、同じでも異なっていてもよい。
【０１６３】
第一乱数生成部、第二乱数生成部、第三乱数生成部、第四乱数生成部、第五乱数生成部、第六乱数生成部及び第七乱数生成部のそれぞれが一様乱数を生成することにより、復号制御システムの安全性を高くできる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部、第二乱数生成部、第三乱数生成部、第四乱数生成部、第五乱数生成部、第六乱数生成部及び第七乱数生成部の少なくとも一部が、一様乱数ではない乱数を生成してもよい。また、演算効率上からは、上述の各実施形態のように０以上ＫＨ未満の自然数である乱数や０以上ＫＧ未満の自然数である乱数が選択されることが望ましいが、それらの代わりにＫＨ以上やＫＧ以上の自然数の乱数が選択されてもよい。
【０１６４】
復号装置が同一のａ，ｂに対応する第一入力情報τ１及び第二入力情報τ２を復号能力提供装置に提供するたびに、復号能力提供装置の処理が複数回実行させてもよい。これにより、復号装置が第一入力情報τ１及び第二入力情報τ２を復号能力提供装置に一回提供するたびに、復号装置は第一出力情報ｚ１や第二出力情報ｚ２や第三出力情報ｚ３を複数個得ることができる。これにより、復号装置と復号能力提供装置との間のやり取り回数や通信量を減らすことができる。
【０１６５】
また、復号装置が複数種類の第一入力情報τ１及び第二入力情報τ２を復号能力提供装置にまとめて提供し、対応する第一出力情報ｚ１や第二出力情報ｚ２や第三出力情報ｚ３を複数個まとめて取得してもよい。これにより、復号装置と復号能力提供装置との間のやり取り回数を減らすことができる。
【０１６６】
復号装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、復号能力提供装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【０１６７】
また、各実施形態の第一計算部や第二計算部において得られたｕやｖが群Ｇの元であるかを確認し、群Ｇの元であった場合には上述した処理を続行し、ｕ又はｖが群Ｇの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号「⊥」が出力されてもよい。
【０１６８】
その他、本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１６９】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１７０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１７１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１７２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【符号の説明】
【０１７３】
１〜５  復号制御システム
１１〜５１  復号装置
１２〜５２  復号能力提供装置
１３  復号制御装置
【図１】
0005596612.tif 000002
【図２】
0005596612.tif 000003
【図３】
0005596612.tif 000004
【図４】
0005596612.tif 000005
【図５】
0005596612.tif 000006
【図６】
0005596612.tif 000007
【図７】
0005596612.tif 000008
【図８】
0005596612.tif 000009
【図９】
0005596612.tif 000010
【図１０】
0005596612.tif 000011
【図１１】
0005596612.tif 000012
【図１２】
0005596612.tif 000013