(57)【要約】  第一計算部がｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとし、第二計算部がｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとする。最終計算部は、計算結果ｕ及びｖがｕa＝ｖｂを満たす場合に、ｄ＝ａ’ａ＋ｂ’ｂについての（ｕb’ｖa’）１／ｄを出力する。ただし、Ｇ，Ｈが群であり、ｆが群Ｈの元ｘを群Ｇへ写す関数であり、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数であり、確率変数Ｘ１の実現値がｘ１であり、確率変数Ｘ２の実現値がｘ２であり、ａ，ｂ，ａ’，ｂ’が整数である。
2015008605.tif 000002
【特許請求の範囲】
【請求項１】
Ｇ，Ｈが群であり、ｆが群Ｈの元ｘを群Ｇへ写す関数であり、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数であり、確率変数Ｘ１の実現値がｘ１であり、確率変数Ｘ２の実現値がｘ２であり、ａ，ｂ，ａ’，ｂ’が整数であり、
ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとする第一計算部と、
ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとする第二計算部と、
前記計算結果ｕ及びｖがｕa＝ｖｂを満たす場合に、ｄ＝ａ’ａ＋ｂ’ｂについての（ｕb’ｖa’）１／ｄを出力する最終計算部と、
を有する計算装置。
【請求項２】
請求項１の計算装置であって、
前記最終計算部は、ｄ＝ａ’ａ＋ｂ’ｂを得て（ｕb’ｖa’）１／ｄを出力する、計算装置。
【請求項３】
請求項１または２の計算装置であって、
ｄ≠１である、計算装置。
【請求項４】
Ｇ，Ｈが群であり、ｆが群Ｈの元ｘを群Ｇへ写す関数であり、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数であり、確率変数Ｘ１の実現値がｘ１であり、確率変数Ｘ２の実現値がｘ２であり、ａ，ｂ，ａ’，ｂ’が整数であり、
第一計算部で、ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとするステップと、
第二計算部で、ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとするステップと、
前記計算結果ｕ及びｖがｕa＝ｖｂを満たす場合に、最終計算部でｄ＝ａ’ａ＋ｂ’ｂについての（ｕb’ｖa’）１／ｄを出力するステップと、
を有する計算方法。
【請求項５】
請求項１の計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に自己訂正技術に関する。
【背景技術】
【０００２】
暗号技術の一つに自己訂正（Self-Correcting）技術がある（例えば、特許文献１，２等参照）。自己訂正技術とは、必ずしも正しい計算結果を出力するとは限らない計算機やシステムを用いて常に正しい計算を行う（正しい計算結果を出力する計算機を用いた場合に正しい計算結果を出力し、必ずしも正しい結果を出力するとは限らない計算機を用いた場合に、正しい計算結果を得るか、または計算できない旨の結果を得る）技術である。例えば、自己訂正技術を用いたクラウド鍵管理型の復号技術では、復号鍵を保持する復号能力提供装置が復号鍵を復号装置に与えることなく、復号装置が暗号文を復号するための情報のみを復号装置に与える。復号装置は、この情報を用いて常に正しい復号演算を行うことができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開ＷＯ／２０１１／０８６９９２号公報
【特許文献２】国際公開ＷＯ／２０１２／０５７１３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１，２に記載された自己訂正技術は、互いに素である２つの自然数ａ，ｂを用い、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’についてｕb’ｖa’を得るものであり、ａ，ｂが互いに素でない場合や、ａ’，ｂ’がａ’ａ＋ｂ’ｂ＝１の関係を満たさない場合には利用できなかった。【０００５】
本発明は、このような点に鑑みてなされたものであり、設定の自由度が高い自己訂正技術を提供することを課題とする。
【課題を解決するための手段】
【０００６】
本発明では、ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとし、ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとし、計算結果ｕ及びｖがｕa＝ｖｂを満たす場合に、ｄ＝ａ’ａ＋ｂ’ｂについての（ｕb’ｖa’）１／ｄを出力する。
【発明の効果】
【０００７】
本発明では、ｄ＝ａ’ａ＋ｂ’ｂについての（ｕb’ｖa’）１／ｄを得るため、ａ，ｂが互いに素でない場合や、ａ’，ｂ’がａ’ａ＋ｂ’ｂ＝１の関係を満たさない場合にも利用可能であり、設定の自由度が高い。
【図面の簡単な説明】
【０００８】
【図１】図１は、第１実施形態の自己訂正技術を実行する計算装置の構成を例示したブロック図である。
【図２】図２は、第１実施形態の自己訂正方法を例示するためのフロー図である。
【図３】図３は、第２実施形態の自己訂正技術を実行する計算システムの構成を例示したブロック図である。
【図４】図４は、図３の計算装置の構成を例示したブロック図である。
【図５】図５は、図３の能力提供装置の構成を例示したブロック図である。
【図６】図６は、第２実施形態の計算装置の処理を例示するためのフロー図である。
【図７】図７は、第２実施形態の能力提供装置の処理を例示するためのフロー図である。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施形態を説明する。
［第一実施形態］
＜構成＞
図１に例示するように、第一実施形態の計算装置１は、整数選択部１１２、第一べき乗計算部１１３、第一リスト記憶部１１４、判定部１１５、第二べき乗計算部１１６、第二リスト記憶部１１７、制御部１１８、最終計算部１１９、第一乱数化可能標本器１２１、及び第二乱数化可能標本器１２２を有する。第一実施形態においては、第一乱数化可能標本器１２１及び第二乱数化可能標本器１２２が、それぞれ「第一計算部」及び「第二計算部」に対応する。Ｇ，Ｈを群（例えば、巡回群などの有限可換群）、関数ｆ：Ｈ→Ｇを群Ｈの元ｘを群Ｇへ写す関数、群Ｇ，Ｈの生成元をそれぞれμｇ，μｈ、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２とする。計算装置１は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、単独で処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００１０】
＜処理＞
図２に例示するように、整数選択部１１２は、整数ａ，ｂ，ａ’，ｂ’をランダムに選択する（ステップＳ１０１）。整数ａ，ｂ，ａ’，ｂ’はどのような範囲から選択されてもよい。ａ，ｂは互いに素であってもよいし、互いに素でなくてもよい。例えば、ａ，ｂは正の整数である。しかしながら、ａ，ｂの少なくとも一方が０であってもよいし、負の整数であってもよい。整数ａ，ｂについての情報は、第一べき乗計算部１１３、第二べき乗計算部１１６、第一乱数化可能標本器１２１、及び第二乱数化可能標本器１２２に送られる。整数ａ，ｂ，ａ’，ｂ’についての情報は、最終計算部１１９に送られる。
【００１１】
制御部１１８は、ｔ＝１とする（ステップＳ１０２）。
【００１２】
第一乱数化可能標本器１２１は、ｆ（ｘ）ｂｘ１を計算可能であり、ｘ及びｂを用いて計算を行い、その計算結果をｕとする（ステップＳ１０３）。計算結果ｕの具体例は後述する。計算結果ｕは、第一べき乗計算部１１３に送られる。この出願において、計算可能とは、無視することができない確率以上の確率で正しく計算することができることを意味する。無視することができない確率とは、セキュリティパラメータｋ（ただし、ｋは正の自然数）についての広義単調関数である多項式を多項式Ｆ（ｋ）として、１／Ｆ（ｋ）以上の確率である。広義単調関数の例は、広義単調増加関数（非減少関数）である。ここで、ｆ（ｘ）ｂｘ１を計算するとは、ｆ（ｘ）ｂｘ１と定義される式の値を計算することである。式ｆ（ｘ）ｂｘ１の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。また、この出願では、群で定義された演算を乗法的に表現する。
【００１３】
第一べき乗計算部１１３は、ｕ’＝ｕａを計算する（ステップＳ１０４）。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部１１４に記憶される。
【００１４】
判定部１１５は、第一リスト記憶部１１４に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１１７に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ１０５）。もし、第二リスト記憶部１１７に組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ１０５の処理を行わずに、次のステップＳ１０６の処理を行う。ｕ’＝ｖ’となるものがあった場合には、ステップＳ１１２に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ１０６に進む。
【００１５】
第二乱数化可能標本器１２２は、ｆ（ｘ）ａｘ２を計算可能であり、ｘ及びａを用いて計算を行い、その計算結果をｖとする（ステップＳ１０６）。計算結果ｖの具体例は後述する。計算結果ｖは、第二べき乗計算部１１６に送られる。第二べき乗計算部１１６は、ｖ’＝ｖｂを計算する（ステップＳ１０７）。計算結果ｖとその計算結果に基づいて計算されたｖ’との組（ｖ，ｖ’）は、第二リスト記憶部１１７に記憶される。
【００１６】
判定部１１５は、第一リスト記憶部１１４に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１１７に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ１０８）。ｕ’＝ｖ’となるものがあった場合には、ステップＳ１１２に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ１１０に進む。
【００１７】
制御部１１８は、ｔ＝Ｔであるか判定する（ステップＳ１１０）。Ｔは予め定められた正の自然数である。ｔ＝Ｔであれば、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１１）、処理を終える。計算をすることができなかった旨の情報（この例では記号「⊥」）は、正しく計算を行う信頼性がＴで定められる基準を下回るということを意味する。言い換えれば、Ｔ回の繰り返しで正しい演算を行うことができなかったということを意味する。ｔ＝Ｔでない場合には、制御部１１８は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ１０９）、ステップＳ１０３に戻る。
【００１８】
最終計算部１１９は、ｕ’＝ｖ’であると判定された場合には、ｄ＝ａ’ａ＋ｂ’ｂを計算し（ステップＳ１１２）、そのｕ’及びｖ’に対応するｕ及びｖ、並びにａ’，ｂ’及びｄを用い、（ｕb’ｖa’）１／ｄを計算して出力する（ステップＳ１１３）。すなわち、最終計算部１１９は、ｄ＝ａ’ａ＋ｂ’ｂを得てｄについての（ｕb’ｖa’）１／ｄを出力する。出力された（ｕb’ｖa’）１／ｄは（ｕb’ｖa’）１／ｄ＝ｆ（ｘ）を満たす。以下にその理由を説明する。
【００１９】
≪（ｕb’ｖa’）１／ｄ＝ｆ（ｘ）を満たす理由≫
特許文献１，２で開示されているように、ｕ’＝ｖ’が成立するのは、すなわちｕａ＝ｖｂが成立するのは、第一乱数化可能標本器１２１がｕ＝ｆ（ｘ）ｂｘ１を正しく計算しており、第二乱数化可能標本器１２２がｖ＝ｆ（ｘ）ａｘ２を正しく計算しており、さらにｘ１及びｘ２が群Ｇの単位元ｅｇである可能性が非常に高い。第一乱数化可能標本器１２１がｕ＝ｆ（ｘ）ｂｘ１を正しく計算しており、第二乱数化可能標本器１２２がｖ＝ｆ（ｘ）ａｘ２を正しく計算しており、ｘ１及びｘ２が群Ｇの単位元ｅｇであるとき、ｕｂ’ｖａ’＝（ｆ（ｘ）ｂｘ１）ｂ’（ｆ（ｘ）ａｘ２）ａ’＝（ｆ（ｘ）ｂｅｇ）ｂ’（ｆ（ｘ）ａｅｇ）ａ’＝ｆ（ｘ）ｂｂ’ｅｇｂ’ｆ（ｘ）ａａ’ｅｇａ’＝ｆ（ｘ）（ａ’ａ＋ｂ’ｂ）となる。ここでｄ＝ａ’ａ＋ｂ’ｂとするとｕｂ’ｖａ’＝ｆ（ｘ）ｄとなるため、（ｕｂ’ｖａ’）１／ｄ＝ｆ（ｘ）を満たす。
【００２０】
≪ｕ，ｖの具体例≫
ｕ，ｖの例は、特許文献１，２に開示されたｕ，ｖである。例えば、ｕ＝ｚ１ν−ｒ１及びｖ＝ｚ２ν−ｒ２である。ただし、群Ｈが巡回群、巡回群Ｈの生成元がμｈ、ｒ１，ｒ２が０以上のランダムな自然数、ν＝ｆ（μｈ）、τ１＝μｈｒ１ｘｂ、τ２＝μｈｒ２ｘａであり、或る確率より大きな確率でｚ１＝ｆ（τ１）であり、或る確率より大きな確率でｚ２＝ｆ（τ２）である。すなわち、ｚ１＝ｆ（τ１）である場合もあれば、ｚ１≠ｆ（τ１）である場合もあり、ｚ２＝ｆ（τ２）である場合もあれば、ｚ２≠ｆ（τ２）である場合もある。すなわち、ｚ１，ｚ２は、それぞれ、意図的又は意図的ではない誤差を含んだ計算結果ｆ（τ１），ｆ（τ２）となる。「或る確率」は１００％未満であり０％以上の確率である。「或る確率」の例は無視することができない確率である。
【００２１】
或いは、ｕ＝ｚ１Ｙ−ｒ４μｇ−ｒ５及びｖ＝ｚ２Ｙ−ｒ６μｇ−ｒ７であってもよい。ただし、群Ｈが群Ｇの直積群Ｇ×Ｇ、群Ｇが巡回群、巡回群Ｇの生成元がμｇ、ｘ＝（ｃ１，ｃ２），（Ｖ，Ｗ）が群Ｈの元、ｆ（Ｖ，Ｗ）＝Ｙであり、ｒ４〜ｒ７が０以上の自然数の乱数であり、τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）であり、τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）であり、或る確率より大きな確率でｚ１＝ｆ（τ１）であり、或る確率より大きな確率でｚ２＝ｆ（τ２）である。
【００２２】
［第一実施形態の変形例］
整数ａ，ｂの一方が１などの定数であってもよく、整数ａ’，ｂ’の少なくとも一方が定数であってもよい。整数ａ，ｂ，ａ’，ｂ’の一部を定数とし、一部の処理部やステップが省略されてもよい。例えば、ｂが定数１である場合には、ステップＳ１０１での整数ｂの選択が不要となり、ｖ’＝ｖとなり、第二べき乗計算部１１６およびステップＳ１０７が不要となる。或いは、ｄを１以外の定数または乱数とし、ステップＳ１０１でｄ＝ａ’ａ＋ｂ’ｂを満たす整数ａ，ｂ，ａ’，ｂ’が選択され、ステップＳ１１２の処理が省略されてもよい。或いは、ステップＳ１０１で、整数選択部１１２が整数ａ，ｂ，ａ’，ｂ’の選択とｄ＝ａ’ａ＋ｂ’ｂの計算とを行ってもよい。或いは、ステップＳ１０２よりも後、ステップＳ１１３よりも前の何れかの時点で、整数選択部１１２がｄ＝ａ’ａ＋ｂ’ｂを計算してもよい。これらの場合、ステップＳ１１２の処理が省略され、最終計算部１１９は整数選択部１１２からｄを得る。また、最終計算部１１９が、ｄ≠０のときに（ｕb’ｖa’）１／ｄを出力することとしてもよい。ｄ＝０の場合にエラー終了することにしてもよいし、ｄ＝０の場合にステップＳ１０１で整数ａ，ｂ，ａ’，ｂ’の少なくとも一部が再選択され、処理がやり直されてもよい。また、演算にａ’，ｂ’が必要となる前であれば、どの時点でａ’，ｂ’が選択されてもよい。
【００２３】
［第二実施形態］
第二実施形態は、第一実施形態をクラウド型の鍵管理システムに適用した形態である。以下では第一実施形態との相違点を中心に説明し、第一実施形態と共通する事項については説明を省略する。
【００２４】
＜構成＞
図３に例示するように、第二実施形態の代理計算システム２は、例えば、復号鍵を保持していない計算装置２１と復号鍵を保持する能力提供装置２２とを有し、計算装置２１が能力提供装置２２に暗号文の復号能力の提供を依頼し、能力提供装置２２から提供された復号能力を用いて暗号文を復号する。計算装置２１と能力提供装置２２とは情報のやり取りが可能なように構成される。例えば、計算装置２１と能力提供装置２２とは、伝送線やネットワークや可搬型記録媒体などを経由した情報のやり取りが可能とされている。
【００２５】
図４に例示するように、第二実施形態の計算装置２１は、例えば、整数選択部２１０２と入力情報提供部２１０４と第一計算部２１０５と第一べき乗計算部２１０６と第一リスト記憶部２１０７と第二計算部２１０８と第二べき乗計算部２１０９と第二リスト記憶部２１１０と判定部２１１１と最終出力部２１１２と制御部２１１３とを有する。計算装置２１の例は、カードリーダライタ装置や携帯電話などの計算機能と記憶機能とを備えた機器や、特別なプログラムが読み込まれた前述のようなコンピュータなどである。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路ではなく、単独で処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。
【００２６】
図５に例示するように、第二実施形態の能力提供装置２２は、例えば、第一出力情報計算部２２０１と第二出力情報計算部２２０２と鍵記憶部２２０４と制御部２２０５とを有する。能力提供装置２２の例は、ＩＣカードやＩＣチップなどの耐タンパ性モジュールや、携帯電話などの計算機能と記憶機能とを備えた機器や、特別なプログラムが読み込まれた前述のようなコンピュータなどである。
【００２７】
＜処理＞
次に本形態の処理を説明する。処理の前提として、Ｇ，Ｈを群（例えば、巡回群などの有限可換群）、ｆ（ｘ）を群Ｈの元である暗号文ｘを特定の復号鍵ｓで復号して群Ｇの元を得るための復号関数、群Ｇ，Ｈの生成元をそれぞれμg，μh、Ｘ1，Ｘ2を群Ｇに値を持つ確率変数、確率変数Ｘ1の実現値をｘ1、確率変数Ｘ2の実現値をｘ2とする。計算装置２１の各処理は制御部２１１３の制御のもとで実行され、能力提供装置２２の各処理は制御部２２０５の制御のもとで実行される。
【００２８】
図６に例示するように、まず、計算装置２１（図４）の整数選択部２１０２が、整数ａ，ｂ，ａ’，ｂ’をランダムに選択する（ステップＳ２１０１）。整数ａ，ｂの少なくとも一部の情報は、入力情報提供部２１０４、第一べき乗計算部２１０６、および第二べき乗計算部２１０９に送られる。整数ａ，ｂ，ａ’，ｂ’の情報は最終出力部２１１２に送られる。
【００２９】
制御部２１１３は、ｔ＝１とする（ステップＳ２１０２）。
【００３０】
入力情報提供部２１０４は、入力された暗号文ｘにそれぞれ対応する群Ｈの元である第一入力情報τ1及び第二入力情報τ2を生成して出力する（ステップＳ２１０３）。好ましくは、第一入力情報τ1及び第二入力情報τ2はそれぞれ暗号文ｘとの関係をかく乱させた情報である。例えば、第一入力情報τ1及び第二入力情報τ2はそれぞれ暗号文ｘに対応するが、第一入力情報τ1及び第二入力情報τ2のみから暗号文ｘを得ることが困難である。「暗号文ｘを得ることが困難」とは、例えば、多項式時間内に暗号文ｘを得ることができないことを意味する。これにより、計算装置２１は、暗号文ｘを能力提供装置２２に対して隠蔽できる。好ましくは、本形態の第一入力情報τ1は整数選択部２１０２で選択された整数ｂにさらに対応し、第二入力情報τ2は整数選択部２１０２で選択された整数ａにさらに対応する。これにより、能力提供装置２２から提供された復号能力を計算装置２１が高い精度で評価することが可能となる。τ1，τ2の具体例は、第一実施形態で例示した通りである。
【００３１】
図７に例示するように、第一入力情報τ1は能力提供装置２２（図５）の第一出力情報計算部２２０１に入力され、第二入力情報τ2は第二出力情報計算部２２０２に入力される（ステップＳ２２００）。
【００３２】
第一出力情報計算部２２０１は、第一入力情報τ1と鍵記憶部２２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（τ1）を正しく計算し、得られた計算結果を第一出力情報ｚ1とする（ステップＳ２２０１）。第二出力情報計算部２２０２は、第二入力情報τ2と鍵記憶部１２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（τ2）を正しく計算し、得られた計算結果を第二出力情報ｚ2とする（ステップＳ２２０２）。すなわち、第一出力情報計算部２２０１や第二出力情報計算部２２０２は、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部２２０１での計算結果がｆ（τ1）の場合もあればｆ（τ1）でない場合もあり、第二出力情報計算部２２０２での計算結果がｆ（τ2）の場合もあればｆ（τ2）でない場合もある。
【００３３】
第一出力情報計算部２２０１は第一出力情報ｚ1を出力し、第二出力情報計算部２２０２は第二出力情報ｚ2を出力する（ステップＳ２２０３）。
【００３４】
図６に戻り、第一出力情報ｚ1は計算装置２１（図４）の第一計算部２１０５に入力され、第二出力情報ｚ2は第二計算部２１０８に入力される。これらの第一出力情報ｚ1及び第二出力情報ｚ2が、能力提供装置２２から計算装置２１に与えられた復号能力に相当する（ステップＳ２１０４）。
【００３５】
第一計算部２１０５は、第一出力情報ｚ1から計算結果ｕ＝ｆ（ｘ）bｘ1を生成する。ｚ1＝ｆ（τ1）である場合もあれば、ｆ（τ1）でない場合もあり、第一計算部２１０５は、計算結果ｕ＝ｆ（ｘ）bｘ1を生成可能である。ｚ1からｕを生成する方法の具体例は、第１実施形態で示した通りである。例えば、τ１＝μｈｒ１ｘｂである場合にはｕ＝ｚ１ν−ｒ１であり、τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）である場合にはｕ＝ｚ１Ｙ−ｒ４μｇ−ｒ５である。計算結果ｕは第一べき乗計算部２１０６に送られる（ステップＳ２１０５）。
【００３６】
第一べき乗計算部２１０６はｕ’＝ｕaを計算する。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部２１０７に記憶される（ステップＳ２１０６）。
【００３７】
判定部２１１１は、第一リスト記憶部２１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部２１１０に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ２１０７）。もし、第二リスト記憶部２１１０に組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ２１０７の処理を行わずに、次のステップＳ２１０８の処理を行う。ｕ’＝ｖ’となるものがあった場合には、ステップＳ２１１４に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ２１０８に進む。
【００３８】
ステップＳ２１０８では、第二計算部２１０８が、第二出力情報ｚ2から計算結果ｖ＝ｆ（ｘ）aｘ2を生成する。ｚ2＝ｆ（τ2）である場合もあれば、ｆ（τ2）でない場合もあり、第一計算部２１０５は、計算結果ｖ＝ｆ（ｘ）aｘ2を生成可能である。ｚ２からｖを生成する方法の具体例は、第１実施形態で示した通りである。例えば、τ２＝μｈｒ２ｘａの場合にはｖ＝ｚ２ν−ｒ２であり、τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）の場合にはｖ＝ｚ２Ｙ−ｒ６μｇ−ｒ７である。計算結果ｖは第二べき乗計算部２１０９に送られる（ステップＳ２１０８）。
【００３９】
第二べき乗計算部２１０９はｖ’＝ｖｂを計算する。計算結果ｖとその計算結果に基づいて計算されたｖ’との組（ｖ，ｖ’）は、第二リスト記憶部２１１０に記憶される（ステップＳ２１０９）。
【００４０】
判定部２１１１は、第一リスト記憶部２１０７に記憶された組（ｕ，ｕ’）及び第二リスト記憶部２１１０に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ２１１０）。ｕ’＝ｖ’となるものがあった場合には、ステップＳ２１１４に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ２１１１に進む。
【００４１】
ステップＳ２１１１では、制御部２１１３がｔ＝Ｔmaxであるか判定する（ステップＳ２１１１）。Ｔmaxは予め定められた自然数である。ｔ＝Ｔmaxであれば、制御部２１１３は、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ２１１３）、処理を終える。ｔ＝Ｔmaxでない場合には、制御部２１１３は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ２１１２）、ステップＳ２１０３に戻る。
【００４２】
ステップＳ２１１４では、最終出力部２１１２が、ｄ＝ａ’ａ＋ｂ’ｂを計算し（ステップＳ２１１４）、そのｕ’及びｖ’に対応するｕ及びｖ、並びにａ’，ｂ’及びｄを用い、（ｕb’ｖa’）１／ｄを計算して出力する（ステップＳ２１１５）。すなわち、最終出力部２１１２は、ｄ＝ａ’ａ＋ｂ’ｂを得てｄについての（ｕb’ｖa’）１／ｄを出力する。出力された（ｕb’ｖa’）１／ｄは高い確率で暗号文ｘの復号結果ｆ（ｘ）となる。また、上述した処理を複数回繰り返し、ステップＳ２１１５で得られた値のうち最も頻度の高い値を復号結果としてもよい。
【００４３】
［第二実施形態の変形例］
整数ａ，ｂの一方が１などの定数であってもよく、整数ａ’，ｂ’の少なくとも一方が定数であってもよい。整数ａ，ｂ，ａ’，ｂ’の一部を定数とし、一部の処理部やステップが省略されてもよい。例えば、ｂが定数１である場合には、ステップＳ２１０１での整数ｂの選択が不要となり、ｖ’＝ｖとなり、第二べき乗計算部２１０９およびステップＳ２１０９が不要となる。或いは、ｄを１以外の定数または乱数とし、ステップＳ２１０１でｄ＝ａ’ａ＋ｂ’ｂを満たす整数ａ，ｂ，ａ’，ｂ’が選択され、ステップＳ２１１４の処理が省略されてもよい。或いは、ステップＳ２１０１で、整数選択部２１１２が整数ａ，ｂ，ａ’，ｂ’の選択とｄ＝ａ’ａ＋ｂ’ｂの計算とを行ってもよい。或いは、ステップＳ２１０２よりも後、ステップＳ２１１５よりも前の何れかの時点で、整数選択部２１０２がｄ＝ａ’ａ＋ｂ’ｂを計算してもよい。これらの場合、ステップＳ２１１４の処理が省略され、最終計算部２１１２は整数選択部２１０２からｄを得る。また、最終計算部２１１２が、ｄ≠０のときに（ｕb’ｖa’）１／ｄを出力することとしてもよい。ｄ＝０の場合にエラー終了することにしてもよいし、ｄ＝０の場合にステップＳ２１０１で整数ａ，ｂ，ａ’，ｂ’の少なくとも一部が再選択され、処理がやり直されてもよい。また、演算にａ’，ｂ’が必要となる前であれば、どの時点でａ’，ｂ’が選択されてもよい。
【００４４】
［その他の変形例］
本発明は上述の実施の形態に限定されるものではない。例えば、特許文献２、特開２０１２−２３７８８１、特開２０１２−２２０８３４、特開２０１２−２２０８１４、および特開２０１２−１５１７５６等の各実施形態の自己訂正技術を本発明の自己訂正技術に置換した形態であってもよい。
【００４５】
例えば、第二実施形態において、計算システムがさらに復号制御装置を有してもよい。この復号制御装置は、計算装置の復号処理を制御する復号制御命令を能力提供装置に出力し、能力提供装置は、復号制御命令に従って第一出力情報ｚ1及び第二出力情報ｚ2の両方が出力されるか否かを制御してもよい。さらに計算システムが複数個の能力提供装置を有し、復号制御命令を何れかの能力提供装置に出力し、各能力提供装置は、復号制御命令に従って第一出力情報ｚ1及び第二出力情報ｚ2の両方が出力されるか否かを制御してもよい。
【００４６】
第二実施形態において、計算システムがさらに復号制御装置を有し、Ｇι，Ｈιが群、ωが２以上の整数、ι＝１，・・・，ω、ｆι（λι）が群Ｈιの元である暗号文λιを特定の復号鍵ｓιで復号して群Ｇιの元を得るための復号関数、Ｘι,1，Ｘι,2が群Ｇιに値を持つ確率変数、ｘι,1が確率変数Ｘι,1の実現値、ｘι,2が確率変数Ｘι,2の実現値、ａ（ι），ｂ（ι），ａ’（ι），ｂ’（ι）が整数であり、群Ｇが群Ｇ1、群Ｈが群Ｈ1、暗号文ｘが暗号文λ1、復号関数ｆ（ｘ）が復号関数ｆ1（λ1）、確率変数Ｘ1が確率変数Ｘ1,1、確率変数Ｘ2が確率変数Ｘ1,2、実現値ｘ1が実現値ｘ1,1、実現値ｘ2が実現値ｘ1,2、整数ａが整数ａ（１）、整数ｂが整数ｂ（１）、整数ａ’が整数ａ’（１）、整数ｂ’が整数ｂ’（１）であってもよい。この場合、計算装置は、暗号文λιに対応する、群Ｈιの元である第一入力情報τι,1及び第二入力情報τι,2を出力し、能力提供装置は、第一入力情報τι,1を用い、或る確率より大きな確率でｆι（τι,1）を正しく計算し、得られた演算結果を第一出力情報ｚι,1として出力し、第二入力情報τι,2を用い、或る確率より大きな確率でｆι（τι,2）を正しく計算し、得られた演算結果を第二出力情報ｚι,2として出力する。計算装置は、第一出力情報ｚι,1から演算結果ｕι＝ｆι（λι）b(ι)ｘι,1を生成し、第二出力情報ｚι,2から演算結果ｖι＝ｆι（λι）a(ι)ｘι,2を生成し、演算結果ｕι及びｖιがｕιa(ι)＝ｖιb(ι)を満たす場合に、例えばａ’（ι）ａ（ι）＋ｂ’（ι）ｂ（ι）＝ｄ（ι）を得て、ｄ（ι）についての（ｕιb’(ι)ｖιa’(ι)）１／ｄ（ι）を出力する。復号制御装置は、計算装置の復号処理を制御する復号制御命令を能力提供装置に出力し、能力提供装置は、復号制御命令に従って、第一出力情報計算部及び第二出力情報計算部から、第一出力情報ｚι,1及び第二出力情報ｚι,2の両方が出力されるか否かを制御する。
【００４７】
また、この場合に、復号制御命令が何れかの復号関数ｆιに対応し、能力提供装置が復号制御命令に対応する復号関数ｆιに対応する第一出力情報ｚι,1及び第二出力情報ｚι,2の両方の出力の有無を制御してもよい。また、計算装置が、さらに最終出力部から出力された各ι＝１，・・・，ωについての（ｕιb’(ι)ｖιa’(ι)）１／ｄ（ι）を用い、各ι＝１，・・・，ωについての暗号文λιを復号鍵ｓιで復号して得られる復号値がすべて得られた場合にのみ復元可能な復元値を生成してもよい。
【００４８】
また、第二実施形態において、計算システムが複数個の計算装置を有し、複数の計算装置が１個の能力提供装置を利用して復号結果を得てもよい。
【００４９】
また第二実施形態では、ｆ（ｘ）が群Ｈの元である暗号文ｘを特定の復号鍵ｓで復号して群Ｇの元を得るための復号関数であった。しかしながら、第二実施形態において、群Ｈの元ｘを入力として群Ｇの元を得るその他の関数をｆ（ｘ）としてもよい。例えば、ｆ（ｘ）が暗号化関数であってもよい。
【００５０】
その他、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。あるいは、計算装置が複数の装置によって構成されてもよいし、能力提供装置が複数の装置によって構成されてもよい。
【００５１】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５２】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００５３】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００５５】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００５６】
１，２１  計算措置
２  代理計算システム
【図１】
2015008605.tif 000003
【図２】
2015008605.tif 000004
【図３】
2015008605.tif 000005
【図４】
2015008605.tif 000006
【図５】
2015008605.tif 000007
【図６】
2015008605.tif 000008
【図７】
2015008605.tif 000009
【手続補正書】
【提出日】平成28年1月6日(2016.1.6)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
第一出力情報計算部２２０１は、第一入力情報τ1と鍵記憶部２２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（τ1）を正しく計算し、得られた計算結果を第一出力情報ｚ1とする（ステップＳ２２０１）。第二出力情報計算部２２０２は、第二入力情報τ2と鍵記憶部２２０４に格納された復号鍵ｓとを用い、或る確率より大きな確率でｆ（τ2）を正しく計算し、得られた計算結果を第二出力情報ｚ2とする（ステップＳ２２０２）。すなわち、第一出力情報計算部２２０１や第二出力情報計算部２２０２は、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部２２０１での計算結果がｆ（τ1）の場合もあればｆ（τ1）でない場合もあり、第二出力情報計算部２２０２での計算結果がｆ（τ2）の場合もあればｆ（τ2）でない場合もある。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
ステップＳ２１０８では、第二計算部２１０８が、第二出力情報ｚ2から計算結果ｖ＝ｆ（ｘ）aｘ2を生成する。ｚ2＝ｆ（τ2）である場合もあれば、ｆ（τ2）でない場合もあり、第二計算部２１０８は、計算結果ｖ＝ｆ（ｘ）aｘ2を生成可能である。ｚ２からｖを生成する方法の具体例は、第１実施形態で示した通りである。例えば、τ２＝μｈｒ２ｘａの場合にはｖ＝ｚ２ν−ｒ２であり、τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）の場合にはｖ＝ｚ２Ｙ−ｒ６μｇ−ｒ７である。計算結果ｖは第二べき乗計算部２１０９に送られる（ステップＳ２１０８）。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
［第二実施形態の変形例］
整数ａ，ｂの一方が１などの定数であってもよく、整数ａ’，ｂ’の少なくとも一方が定数であってもよい。整数ａ，ｂ，ａ’，ｂ’の一部を定数とし、一部の処理部やステップが省略されてもよい。例えば、ｂが定数１である場合には、ステップＳ２１０１での整数ｂの選択が不要となり、ｖ’＝ｖとなり、第二べき乗計算部２１０９およびステップＳ２１０９が不要となる。或いは、ｄを１以外の定数または乱数とし、ステップＳ２１０１でｄ＝ａ’ａ＋ｂ’ｂを満たす整数ａ，ｂ，ａ’，ｂ’が選択され、ステップＳ２１１４の処理が省略されてもよい。或いは、ステップＳ２１０１で、整数選択部２１０２が整数ａ，ｂ，ａ’，ｂ’の選択とｄ＝ａ’ａ＋ｂ’ｂの計算とを行ってもよい。或いは、ステップＳ２１０２よりも後、ステップＳ２１１５よりも前の何れかの時点で、整数選択部２１０２がｄ＝ａ’ａ＋ｂ’ｂを計算してもよい。これらの場合、ステップＳ２１１４の処理が省略され、最終出力部２１１２は整数選択部２１０２からｄを得る。また、最終出力部２１１２が、ｄ≠０のときに（ｕb’ｖa’）１／ｄを出力することとしてもよい。ｄ＝０の場合にエラー終了することにしてもよいし、ｄ＝０の場合にステップＳ２１０１で整数ａ，ｂ，ａ’，ｂ’の少なくとも一部が再選択され、処理がやり直されてもよい。また、演算にａ’，ｂ’が必要となる前であれば、どの時点でａ’，ｂ’が選択されてもよい。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
１，２１  計算装置
２  代理計算システム
【手続補正書】
【提出日】平成28年11月25日(2016.11.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
Ｇ，Ｈが群であり、ｆが群Ｈの元ｘを群Ｇへ写す関数であり、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数であり、確率変数Ｘ１の実現値がｘ１であり、確率変数Ｘ２の実現値がｘ２であり、ａ，ｂ，ａ’，ｂ’が整数であり、
ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとする第一計算部と、
ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとする第二計算部と、
前記計算結果ｕ及びｖがｕa＝ｖｂを満たす場合に、ｄ＝ａ’ａ＋ｂ’ｂについての（ｕb’ｖa’）１／ｄを出力する最終計算部と、
を有し、
ｄ≠１である、計算装置。
【請求項２】
請求項１の計算装置であって、
前記最終計算部は、ｄ＝ａ’ａ＋ｂ’ｂを得て（ｕb’ｖa’）１／ｄを出力する、計算装置。
【請求項３】
Ｇ，Ｈが群であり、ｆが群Ｈの元ｘを群Ｇへ写す関数であり、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数であり、確率変数Ｘ１の実現値がｘ１であり、確率変数Ｘ２の実現値がｘ２であり、ａ，ｂ，ａ’，ｂ’が整数であり、
第一計算部で、ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとするステップと、
第二計算部で、ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとするステップと、
前記計算結果ｕ及びｖがｕa＝ｖｂを満たす場合に、最終計算部でｄ＝ａ’ａ＋ｂ’ｂについての（ｕb’ｖa’）１／ｄを出力するステップと、
を有し、
ｄ≠１である、計算方法。
【請求項４】
請求項１または２の計算装置としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2015008605.tif 000010
2015008605.tif 000011
2015008605.tif 000012
2015008605.tif 000013