(57)【要約】【課題】  各数値を暗号化してなる各暗号化データを用いて当該各数値を加減算でき、当該加減算における被減数と減数との間の大小関係を判定する。【解決手段】  実施形態の鍵生成装置は、複数の数値を暗号化するための暗号化鍵と、暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成する。暗号化装置は、各数値を暗号化鍵に基づいて暗号化し、複数の暗号化データを生成する。演算装置は、各暗号化データに基づいて、各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成する。演算支援装置は、一次演算結果、二次演算鍵及び乱数に基づいて、一次演算結果をランダム化してなる二次演算結果を生成する。演算装置は、二次演算結果及び三次演算鍵に基づいて、三次演算結果を生成し、三次演算結果に基づいて式における被減数と減数との間の大小関係を判定する。【選択図】図１
2014178379.tif 000002
【特許請求の範囲】
【請求項１】
クライアント端末、演算装置及び演算支援装置を備えた暗号化データ演算システムであって、
前記クライアント端末は、
複数の数値を記憶する数値記憶手段と、
前記各数値を暗号化するための暗号化鍵と、前記暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成する鍵生成手段と、
前記各数値を前記暗号化鍵に基づいて暗号化し、複数の暗号化データを生成する暗号化手段と、
を備え、
前記演算装置は、
前記三次演算鍵を記憶する三次演算鍵記憶手段と、
前記各暗号化データに基づいて一次演算処理を実行することにより、前記各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成する一次演算手段と、
前記一次演算結果をランダム化してなる二次演算結果が前記演算支援装置により生成された場合、前記二次演算結果及び前記三次演算鍵に基づいて三次演算処理を実行することにより、前記加減算した式の演算結果を乱数のみで秘匿化したデータに相当する三次演算結果を生成する三次演算手段と、
前記三次演算結果に基づいて、前記式における被減数と減数との間の大小関係を判定する大小判定手段と、
を備え、
前記演算支援装置は、
前記二次演算鍵を記憶する二次演算鍵記憶手段と、
前記乱数を生成する乱数生成手段と、
前記一次演算結果、前記二次演算鍵及び前記乱数に基づいて二次演算処理を実行することにより、前記二次演算結果を生成する二次演算手段と、
を備えたことを特徴とする暗号化データ演算システム。
【請求項２】
演算装置及び演算支援装置に通信可能なクライアント端末であって、
複数の数値を記憶する数値記憶手段と、
前記各数値を暗号化するための暗号化鍵と、前記暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成する鍵生成手段と、
前記各数値を前記暗号化鍵に基づいて暗号化し、複数の暗号化データを生成する暗号化手段と、
を備え、
前記演算装置は、
前記各暗号化データに基づいて一次演算処理を実行することにより、前記各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成し、
前記演算支援装置は、
前記一次演算結果、前記二次演算鍵及び乱数に基づいて二次演算処理を実行することにより、前記一次演算結果をランダム化してなる二次演算結果を生成し、
前記演算装置は、
前記二次演算結果及び前記三次演算鍵に基づいて三次演算処理を施すことにより、前記加減算した式の演算結果を前記乱数のみで秘匿化したデータに相当する三次演算結果を生成し、前記三次演算結果に基づいて前記式における被減数と減数との間の大小関係を判定する
ことを特徴とするクライアント端末。
【請求項３】
クライアント端末及び演算支援装置に通信可能な演算装置であって、
前記クライアント端末が、複数の数値を暗号化するための暗号化鍵と、前記暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成し、前記各数値を前記暗号化鍵に基づいて暗号化し、複数の暗号化データを生成した場合に、前記三次演算鍵を記憶する三次演算鍵記憶手段と、
前記各暗号化データに基づいて一次演算処理を実行することにより、前記各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成する一次演算手段と、
前記一次演算結果をランダム化してなる二次演算結果が前記演算支援装置により生成された場合、前記二次演算結果及び前記三次演算鍵に基づいて三次演算処理を実行することにより、前記加減算した式の演算結果を乱数のみで秘匿化したデータに相当する三次演算結果を生成する三次演算手段と、
前記三次演算結果に基づいて、前記式における被減数と減数との間の大小関係を判定する大小判定手段と、
を備え、
前記演算支援装置は、
前記一次演算結果、前記二次演算鍵及び前記乱数に基づいて二次演算処理を実行することにより、前記二次演算結果を生成する
ことを特徴とする演算装置。
【請求項４】
請求項３に記載の演算装置において、
前記一次演算手段は、０以上Ｎ未満の整数の集合のうちのｋ個の前記各数値ｍ１，ｍ２，…，ｍｋが前記暗号化鍵（ａ，ｓｖ）により暗号化されてなる前記各暗号化データＣｉ（ｉ＝１，２，…，ｋ）に基づいて、前記各数値を加減算した式Ｆの演算結果を暗号化したデータに相当する前記一次演算結果Ｘ１，Ｘ２を生成し、
前記三次演算手段は、前記一次演算結果Ｘ１，Ｘ２を前記二次演算鍵（ａ-1，ｓ）及び乱数Ｒ，ｚによりランダム化してなる二次演算結果Ｙ１，Ｙ２と、前記三次演算鍵（ｖ）とに基づいて、前記三次演算結果Ｗ（＝ＦＲ−ｚ）を生成し（但し、ａ-1 はａ  ｍｏｄ  Ｎ２を満たす値、Ｒは集合｛１，…，Ｌ｝からランダムに選択されたβ個の乱数の積、Ｌβ ＜Ｎ/２、ｚは集合｛０，１，…，Ｊ｝から選択された乱数、Ｒ＜Ｊとなる確率は十分小さい）、
前記大小判定手段は、前記三次演算結果Ｗに基づいて、前記式Ｆにおける被減数と減数との間の大小関係を判定する、
ことを特徴とする演算装置。
【請求項５】
クライアント端末及び演算装置に通信可能な演算支援装置であって、
前記クライアント端末が、複数の数値を記憶し、前記各数値を暗号化するための暗号化鍵と、前記暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成し、前記各数値を前記暗号化鍵に基づいて暗号化し、複数の暗号化データを生成した後に、前記演算装置が、前記三次演算鍵を記憶し、前記各暗号化データに基づいて一次演算処理を実行することにより、前記各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成した場合に、前記二次演算鍵を記憶する二次演算鍵記憶手段と、
乱数を生成する乱数生成手段と、
前記一次演算結果、前記二次演算鍵及び前記乱数に基づいて二次演算処理を実行することにより、前記一次演算結果をランダム化してなる二次演算結果を生成する二次演算手段と、
を備え、
前記演算装置は、前記二次演算結果及び前記三次演算鍵に基づいて三次演算処理を実行することにより、前記加減算した式の演算結果を前記乱数のみで秘匿化したデータに相当する三次演算結果を生成し、前記三次演算結果に基づいて、前記式における被減数と減数との間の大小関係を判定する
ことを特徴とする演算支援装置。
【請求項６】
請求項５に記載の演算支援装置において、
前記二次演算鍵記憶手段は、前記クライアント端末が、０以上Ｎ未満の整数の集合のうちのｋ個の前記各数値ｍ１，ｍ２，…，ｍｋを前記暗号化鍵（ａ，ｓｖ）により暗号化して前記各暗号化データＣｉ（ｉ＝１，２，…，ｋ）を生成した後に、前記演算装置が、前記各暗号化データＣｉ（ｉ＝１，２，…，ｋ）に基づいて、前記各数値を加減算した式Ｆの演算結果を暗号化したデータに相当する前記一次演算結果Ｘ１，Ｘ２を生成した場合に、前記二次演算鍵（ａ-1，ｓ）を記憶し（但し、ａ-1 はａ  ｍｏｄ  Ｎ２を満たす値）、
前記乱数生成手段は、前記乱数Ｒ，ｚを生成し（但し、Ｒは集合｛１，…，Ｌ｝からランダムに選択されたβ個の乱数の積、Ｌβ ＜Ｎ/２、ｚは集合｛０，１，…，Ｊ｝から選択された乱数、Ｒ＜Ｊとなる確率は十分小さい）、
前記二次演算手段は、前記一次演算結果Ｘ１，Ｘ２、前記二次演算鍵（ａ-1，ｓ）及び前記乱数Ｒ，ｚに基づいて、前記二次演算結果Ｙ１，Ｙ２を生成し、
前記演算装置は、前記二次演算結果Ｙ１，Ｙ２及び前記三次演算鍵（ｖ）に基づいて、前記三次演算結果Ｗ（＝ＦＲ−ｚ）を生成し、前記三次演算結果Ｗに基づいて、前記式Ｆにおける被減数と減数との間の大小関係を判定する
ことを特徴とする演算支援装置。
【請求項７】
複数の数値を記憶する数値記憶手段を有し、演算装置及び演算支援装置に通信可能なクライアント端末に用いられるプログラムであって、
前記クライアント端末を、
前記各数値を暗号化するための暗号化鍵と、前記暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成する鍵生成手段、
前記各数値を前記暗号化鍵に基づいて暗号化し、複数の暗号化データを生成する暗号化手段、
として機能させ、
前記演算装置は、
前記各暗号化データに基づいて一次演算処理を実行することにより、前記各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成し、
前記演算支援装置は、
前記一次演算結果、前記二次演算鍵及び乱数に基づいて二次演算処理を実行することにより、前記一次演算結果をランダム化してなる二次演算結果を生成し、
前記演算装置は、
前記二次演算結果及び前記三次演算鍵に基づいて三次演算処理を施すことにより、前記加減算した式の演算結果を前記乱数のみで秘匿化したデータに相当する三次演算結果を生成し、前記三次演算結果に基づいて前記式における被減数と減数との間の大小関係を判定する
ことを特徴とするプログラム。
【請求項８】
三次演算鍵記憶手段を有し、クライアント端末及び演算支援装置に通信可能な演算装置に用いられるプログラムであって、
前記演算装置を、
前記クライアント端末が、複数の数値を暗号化するための暗号化鍵と、前記暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成し、前記各数値を前記暗号化鍵に基づいて暗号化し、複数の暗号化データを生成した場合に、前記三次演算鍵を前記三次演算鍵記憶手段に書込む手段、
前記各暗号化データに基づいて一次演算処理を実行することにより、前記各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成する一次演算手段、
前記一次演算結果をランダム化してなる二次演算結果が前記演算支援装置により生成された場合、前記二次演算結果及び前記三次演算鍵に基づいて三次演算処理を実行することにより、前記加減算した式の演算結果を乱数のみで秘匿化したデータに相当する三次演算結果を生成する三次演算手段、
前記三次演算結果に基づいて、前記式における被減数と減数との間の大小関係を判定する大小判定手段、
として機能させ、
前記演算支援装置は、
前記一次演算結果、前記二次演算鍵及び前記乱数に基づいて二次演算処理を実行することにより、前記二次演算結果を生成する
ことを特徴とするプログラム。
【請求項９】
二次演算鍵記憶手段を有し、クライアント端末及び演算装置に通信可能な演算支援装置に用いられるプログラムであって、
前記演算支援装置を、
前記クライアント端末が、複数の数値を記憶し、前記各数値を暗号化するための暗号化鍵と、前記暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成し、前記各数値を前記暗号化鍵に基づいて暗号化し、複数の暗号化データを生成した後に、前記演算装置が、前記三次演算鍵を記憶し、前記各暗号化データに基づいて一次演算処理を実行することにより、前記各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成した場合に、前記二次演算鍵を二次演算鍵記憶手段に書込む手段、
乱数を生成する乱数生成手段、
前記一次演算結果、前記二次演算鍵及び前記乱数に基づいて二次演算処理を実行することにより、前記一次演算結果をランダム化してなる二次演算結果を生成する二次演算手段、
として機能させ、
前記演算装置は、前記二次演算結果及び前記三次演算鍵に基づいて三次演算処理を実行することにより、前記加減算した式の演算結果を前記乱数のみで秘匿化したデータに相当する三次演算結果を生成し、前記三次演算結果に基づいて、前記式における被減数と減数との間の大小関係を判定する
ことを特徴とする演算支援装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、暗号化データ演算システム、装置及びプログラムに関する。
【背景技術】
【０００２】
数値ａ，ｂを暗号化し、暗号化データＥ（ａ），Ｅ（ｂ）が得られる。このような暗号化データＥ（ａ），Ｅ（ｂ）を復号せずに、暗号化データＥ（ａ），Ｅ（ｂ）に基づいて、数値ａ，ｂの大小比較を行う大小比較方法が知られている。
【０００３】
この種の大小比較方法においては、始めに、あるエンティティＡが、乱数ｒを選択し、乱数ｒ及び暗号化データＥ（ａ），Ｅ（ｂ）に基づいて、暗号化データＥ（ｒ（ａ−ｂ））を計算する。他の複数（例、３つ）のエンティティＢ，Ｃ，Ｄは、暗号化データＥ（ｒ（ａ−ｂ））を復号するための復号鍵を分割して保持している。
【０００４】
他のエンティティＢ，Ｃ，Ｄは、分割された復号鍵を持ち寄り、当該持ち寄った復号鍵に基づいて暗号化データＥ（ｒ（ａ−ｂ））を復号する。また、復号結果ｒ（ａ−ｂ）の正負により、数値ａ，ｂの大小関係を判定する。なお、この大小比較方法では、大小比較に必要な復号鍵を比較鍵とも呼ぶ。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Kun Peng, Juanma Gonzalez Nieto and Ed Dawson, “Ciphertext Comparison, a New Solution to the Millionaire Problem,” http://eprints.qut.edu.au/24891/1/Ciphertext_Comparison%2C_a_New_Solution_to_the_Millionaire_Problem.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、以上のような大小比較方法は、通常は特に問題ないが、本発明者の検討によれば、各暗号化データＥ（ａ），Ｅ（ｂ），Ｅ（ｃ），…を用いて各数値を加減算し（例、Ｅ（３ａ＋ｂ−４ｃ））、当該加減算における被減数（例、３ａ＋ｂ）と減数（例、４ｃ）との間の大小関係を判定することができない。
【０００７】
本発明が解決しようとする課題は、各数値を暗号化してなる各暗号化データを用いて当該各数値を加減算でき、当該加減算における被減数と減数との間の大小関係を判定し得る暗号化データ演算システム、装置及びプログラムを提供することである。
【課題を解決するための手段】
【０００８】
実施形態の暗号化データ演算システムは、クライアント端末、演算装置及び演算支援装置を備えている。
【０００９】
前記クライアント端末は、数値記憶手段、鍵生成手段及び暗号化手段を備えている。
【００１０】
前記数値記憶手段は、複数の数値を記憶する。
【００１１】
前記鍵生成手段は、前記各数値を暗号化するための暗号化鍵と、前記暗号化鍵に対応する復号鍵を構成する二次演算鍵と三次演算鍵とを生成する。
【００１２】
前記暗号化手段は、前記各数値を前記暗号化鍵に基づいて暗号化し、複数の暗号化データを生成する。
【００１３】
前記演算装置は、三次演算鍵記憶手段、一次演算手段、三次演算手段及び大小判定手段を備えている。
【００１４】
前記三次演算鍵記憶手段は、前記三次演算鍵を記憶する。
【００１５】
前記一次演算手段は、前記各暗号化データに基づいて一次演算処理を実行することにより、前記各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成する。
【００１６】
前記三次演算手段は、前記一次演算結果をランダム化してなる二次演算結果が前記演算支援装置により生成された場合、前記二次演算結果及び前記三次演算鍵に基づいて三次演算処理を実行することにより、前記加減算した式の演算結果を乱数のみで秘匿化したデータに相当する三次演算結果を生成する。
【００１７】
前記大小判定手段は、前記三次演算結果に基づいて、前記式における被減数と減数との間の大小関係を判定する。
【００１８】
前記演算支援装置は、二次演算鍵記憶手段、乱数生成手段及び二次演算手段を備えている。
【００１９】
前記二次演算鍵記憶手段は、前記二次演算鍵を記憶する。
【００２０】
前記乱数生成手段は、前記乱数を生成する。
【００２１】
前記二次演算手段は、前記一次演算結果、前記二次演算鍵及び前記乱数に基づいて二次演算処理を実行することにより、前記二次演算結果を生成する。
【図面の簡単な説明】
【００２２】
【図１】第１の実施形態に係る暗号化データ演算システムの構成例を示す模式図である。
【図２】同実施形態における暗号化データ演算システムの他の構成例を示す模式図である。
【図３】同実施形態における暗号化データ演算システムの概要を示す模式図である。
【図４】同実施形態における各装置の構成を示す模式図である。
【図５】同実施形態における鍵生成処理の動作を説明するためのシーケンス図である。
【図６】同実施形態における暗号化処理の動作を説明するためのシーケンス図である。
【図７】同実施形態における一次演算処理の動作を説明するためのシーケンス図である。
【図８】同実施形態における二次演算処理の動作を説明するためのシーケンス図である。
【図９】同実施形態における三次演算処理の動作を説明するためのシーケンス図である。
【発明を実施するための形態】
【００２３】
以下、各実施形態について図面を用いて説明する。なお、以下の各装置は、それぞれハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又はコンピュータ読み取り可能な記憶媒体からコンピュータにインストールされ、対応する装置の機能を当該コンピュータに実現させるためのプログラムが用いられる。
【００２４】
（第１の実施形態）
始めに、本実施形態に係る暗号化データ演算システムの構成例について図１を用いて説明する。暗号化データ演算システムは、鍵生成装置１０、暗号化装置２０、記憶装置３０、演算装置４０及び演算支援装置５０を備えている。
【００２５】
ここで、鍵生成装置１０、記憶装置３０、演算装置４０及び演算支援装置５０は、サービスを提供するサービス提供者の有する情報処理装置である。
【００２６】
暗号化装置２０は、当該サービスの利用者であるユーザの有する情報処理装置である。各装置１０，２０，３０，４０，５０は通信網を介して通信可能に接続されている。
【００２７】
通信網とは、例えば、無線ＬＡＮ（Local Area Network）、有線ＬＡＮ、光回線網、電話回線網、イントラネット、イーサネット（登録商標）及びインターネットやこれらの組み合わせである。尚、図１では、暗号化データ演算システムに接続される各装置は各々１つのみ示されているが、これらは各々複数であっても良い。また、図１では、各装置が暗号化データ演算システムにそれぞれ独立に接続される例が示されているが、これに限らず、複数の装置が１つの情報処理装置に含まれていても良い。例えば、図２に示すように、鍵生成装置１０及び暗号化装置２０が１つのクライアント端末（図示せず）に含まれていてもよい。また例えば、図示しないが、記憶装置３０及び演算装置４０が１つのサーバ装置に含まれていてもよい。
【００２８】
図３は、暗号化データ演算システムの概要を示す模式図である。この暗号化データ演算システムは、ユーザ、サービス提供者Ａ、及びサービス提供者Ｂからなる。尚、図３中、鍵生成装置１０の図示を省略したが、鍵生成装置１０は信頼できる第三者が保持していても良いし、ユーザが保持していても良い。
【００２９】
ユーザは、鍵生成装置１０において生成された暗号化鍵を用いて、数値ｍｉ（ｉ＝１,２,３,…）を暗号化装置２０において暗号化する。次に、ユーザは、生成した暗号化データＥ（ｍｉ）を、サービス提供者Ａへ送信する。
【００３０】
サービス提供者Ａは、受信した暗号化データＥ（ｍｉ）を記憶装置３０に記憶する。サービス提供者Ａは、（一次演算処理に必要な）暗号化データＥ（ｍｉ）を記憶装置３０から取得し、一次演算処理を演算装置４０において行う。サービス提供者Ａは、一次演算処理結果をサービス提供者Ｂへ送信する。
【００３１】
サービス提供者Ｂには、鍵生成装置１０において生成された、二次演算を行うための鍵（以下、二次演算鍵と呼ぶ）が予め渡されている。サービス提供者Ｂは、受信した一次演算処理結果と、予め渡された二次演算鍵とを用いて、二次演算処理を演算支援装置５０において行う。サービス提供者Ｂは、二次演算処理結果をサービス提供者Ａへ送信する。
【００３２】
サービス提供者Ａには、鍵生成装置１０において生成された、三次演算を行うための鍵（以下、三次演算鍵と呼ぶ）が予め渡されている。サービス提供者Ａは、受信した二次演算処理結果と、予め渡された三次演算鍵とを用いて、三次演算処理を演算装置４０において行う。最後に、サービス提供者Ａは、三次演算処理結果をユーザへ送信する。または、サービス提供者Ａは、上述の処理を複数回実行して得られる複数の三次演算処理結果に対してさらに演算処理を行った結果をユーザへ送信しても良い。
【００３３】
どのエンティティがどの装置を保持するかについては、上述の例に限定されるものではなく、様々なバリエーションが適用可能となっている。
【００３４】
続いて、図４を用いて、鍵生成装置１０、暗号化装置２０、記憶装置３０、演算装置４０及び演算支援装置５０の構成を具体的に説明する。
【００３５】
鍵生成装置１０は、鍵生成パラメータ記憶部１１、一時データ記憶部１２、パラメータ生成部１３、鍵生成部１４、通信部１５及び制御部１６を備えている。
【００３６】
ここで、鍵生成パラメータ記憶部１１は、鍵生成パラメータを記憶する記憶装置である。鍵生成パラメータとしては、例えば、鍵生成に関する合成数Ｎ＝ｐｑのビット数の下限を定めるためのセキュリティパラメータλが使用可能となっている。
【００３７】
一時データ記憶部１２は、演算対象の複数の数値、各生成部１３，１４の処理途中及び処理結果などの一時データを記憶する記憶装置である。
【００３８】
パラメータ生成部１３は、鍵生成のパラメータを生成する。
【００３９】
鍵生成部１４は、暗号化鍵（例、ａ，ｓｖ）、二次演算鍵（例、ａ-1，ｓ）、及び三次演算鍵（例、ｖ）を生成する。暗号化鍵は、各数値を暗号化するための鍵である。二次演算鍵及び三次演算鍵は、暗号化鍵に対応する復号鍵（例、ａ-1，ｓ，ｖ）を構成している。
【００４０】
通信部１５は、他の装置２０〜５０と通信するための通信インタフェースであり、例えば、制御部１６に制御されて一時データ記憶部１２内の二次演算鍵、三次演算鍵を演算支援装置５０、演算装置４０にそれぞれ送信する機能をもっている。なお、以下の説明では、送受信時の冗長な記載を避ける観点から、送受信の際に、通信部１５を介する旨の記載を省略する場合がある。これは他の装置２０〜５０の通信部２５，３２，４４，５５についても同様である。
【００４１】
制御部１６は、図５に示す動作を実行するように、各部１１〜１５を制御する機能をもっている。
【００４２】
暗号化装置２０は、暗号化パラメータ生成部２１、一時データ記憶部２２、暗号文生成部２３、暗号化鍵記憶部２４、通信部２５及び制御部２６を備えている。
【００４３】
ここで、暗号化パラメータ生成部２１は、暗号化パラメータを生成する。暗号化パラメータとしては、例えば、０以上Ｎ2未満の整数の集合ＺＮ2からランダムに選択されるｋ個の乱数ｒ1，…，ｒkが使用可能となっている。
【００４４】
一時データ記憶部２２は、各生成部２１，２３の処理途中及び処理結果などの一時データを記憶する記憶装置である。
【００４５】
暗号文生成部２３は、各数値を暗号化鍵に基づいて暗号化し、複数の暗号文（複数の暗号化データ）を生成する。
【００４６】
暗号化鍵記憶部２４は、暗号化鍵を記憶する記憶装置である。
【００４７】
通信部２５は、他の装置１０、３０〜５０と通信するための通信インタフェースであり、例えば、制御部２６に制御されて一時データ記憶部２２内の暗号文を記憶装置３０に送信する機能をもっている。
【００４８】
制御部２６は、図６に示す動作を実行するように、各部２１〜２５を制御する機能をもっている。
【００４９】
記憶装置３０は、暗号文記憶部３１、通信部３２及び制御部３３を備えている。
【００５０】
ここで、暗号文記憶部３１は、暗号文を記憶する記憶装置である。
【００５１】
通信部３２は、他の装置１０、２０、４０、５０と通信するための通信インタフェースであり、例えば、制御部３３に制御されて暗号文記憶部３１内の暗号文を演算装置４０に送信する機能をもっている。
【００５２】
制御部３３は、各部３１、３２を制御する機能をもっている。
【００５３】
演算装置４０は、一時データ記憶部４１、計算部４２、判定部４３、通信部４４、制御部４５及び三次演算鍵記憶部４６を備えている。
【００５４】
ここで、一時データ記憶部４１は、計算部４２，判定部４３の処理途中及び処理結果などの一時データを記憶する記憶装置である。
【００５５】
計算部４２は、一次演算結果及び三次演算結果を計算する。詳しくは、計算部４２は、以下の各機能(f42-1)〜(f42-2)をもっている。
【００５６】
(f42-1)  各暗号文（各暗号化データ）に基づいて一次演算処理を実行することにより、各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果（例、Ｘ１，Ｘ２）を生成する一次演算機能。例えば、各暗号化データＣｉ（ｉ＝１，２，…，ｋ）は、０以上Ｎ未満の整数の集合のうちのｋ個の各数値ｍ１，ｍ２，…，ｍｋが暗号化鍵（例、ａ，ｓｖ）により暗号化されて生成される。
【００５７】
(f42-2)  一次演算結果（例、Ｘ１，Ｘ２）をランダム化してなる二次演算結果（例、Ｙ１，Ｙ２）が演算支援装置５０により生成された場合、二次演算結果及び三次演算鍵（例、ｖ）に基づいて三次演算処理を実行することにより、三次演算結果Ｗ（＝ＦＲ−ｚ）を生成する三次演算機能（例、ａ-1 はａ  ｍｏｄ  Ｎ２を満たす値である。Ｒは集合｛１，…，Ｌ｝からランダムに選択されたβ個の乱数の積である。Ｌβ ＜Ｎ/２の関係がある。ｚは集合｛０，１，…，Ｊ｝から選択された乱数である。Ｒ＜Ｊとなる確率は十分小さい。）。三次演算結果Ｗ（＝ＦＲ−ｚ）は、加減算した式Ｆの演算結果を乱数（例、Ｒ，ｚ）のみで秘匿化したデータに相当する。
【００５８】
判定部４３は、三次演算結果に基づき、式Ｆ（Ｆについては後述する）の正負判定を行う。具体的には、判定部４３は、三次演算結果Ｗに基づいて、式Ｆにおける被減数と減数との間の大小関係を判定する。
【００５９】
通信部４４は、他の装置１０〜３０、５０と通信するための通信インタフェースであり、例えば、制御部４５に制御されて一時データ記憶部４１内の一次演算結果を演算支援装置５０に送信する機能をもっている。
【００６０】
制御部４５は、図７及び図９に示す動作を実行するように、各部４１〜４４，４６を制御する機能をもっている。
【００６１】
三次演算鍵記憶部４６は、三次演算鍵を記憶する記憶装置である。
【００６２】
演算支援装置５０は、二次演算処理パラメータ生成部５１、一時データ記憶部５２、計算部５３、二次演算鍵記憶部５４、通信部５５及び制御部５６を備えている。
【００６３】
ここで、二次演算処理パラメータ生成部５１は、二次演算処理パラメータを生成する。二次演算処理パラメータ生成部５１は、例えば、乱数を生成する乱数生成機能をもっている。乱数生成機能は、例えば、乱数Ｒ，ｚを生成する機能である（例、Ｒは集合｛１，…，Ｌ｝からランダムに選択されたβ個の乱数の積である。Ｌβ ＜Ｎ/２の関係がある。ｚは集合｛０，１，…，Ｊ｝から選択された乱数である。Ｒ＜Ｊとなる確率は十分小さい。）。
【００６４】
一時データ記憶部５２は、二次演算処理パラメータ生成部５１、計算部５３の処理途中及び処理結果などの一時データを記憶する記憶装置である。
【００６５】
計算部５３は、二次演算結果を計算する。具体的には、計算部５３は、一次演算結果（例、Ｘ１，Ｘ２）、二次演算鍵（例、ａ-1，ｓ）及び乱数（例、Ｒ，ｚ）に基づいて二次演算処理を実行することにより、二次演算結果（例、Ｙ１，Ｙ２）を生成する。
【００６６】
二次演算鍵記憶部５４は、二次演算鍵を記憶する記憶装置である。例えば、二次演算鍵記憶部５４は、クライアント端末（１０，２０）が各暗号化データＣｉ（ｉ＝１，２，…，ｋ）を生成した後に、演算装置４０が、各暗号化データＣｉ（ｉ＝１，２，…，ｋ）に基づいて一次演算結果（例、Ｘ１，Ｘ２）を生成した場合に、二次演算鍵（例、ａ-1，ｓ）を記憶する（例、ａ-1 はａ  ｍｏｄ  Ｎ２を満たす値である。）。なお、クライアント端末（１０，２０）は、０以上Ｎ未満の整数の集合のうちのｋ個の各数値ｍ１，ｍ２，…，ｍｋを暗号化鍵（例、ａ，ｓｖ）により暗号化して各暗号化データＣｉ（ｉ＝１，２，…，ｋ）を生成する。演算装置４０は、各暗号化データＣｉ（ｉ＝１，２，…，ｋ）に基づいて、当該各数値を加減算した式Ｆの演算結果を暗号化したデータに相当する一次演算結果（例、Ｘ１，Ｘ２）を生成する。
【００６７】
通信部５５は、他の装置１０〜４０と通信するための通信インタフェースであり、例えば、制御部５６に制御されて一時データ記憶部５２内の二次演算結果を演算装置４０に送信する機能をもっている。
【００６８】
制御部５６は、図８に示す動作を実行するように、各部５１〜５５を制御する機能をもっている。
【００６９】
次に、鍵生成処理、暗号化処理、一次演算処理、二次演算処理、及び三次演算処理の各処理について具体的に説明する。
【００７０】
［０．鍵生成処理］
鍵生成処理は、鍵生成装置１０により、図５及び以下の各ステップＳＴ１〜ＳＴ７に示すように実行される。
【００７１】
始めに、鍵生成装置１０のパラメータ生成部１３は、ｐ’＝（ｐ−１）／２，ｑ’＝（ｑ−１）／２が素数となる素数ｐ，ｑを生成する、又は外部から入手する（ＳＴ１）。ここで、パラメータ生成部１３は、予め鍵生成パラメータ記憶部１１に記憶したセキュリティパラメータλに基づいて、合成数Ｎ＝ｐｑのビット数がλ又はλより大きい値となるような素数ｐ，ｑを生成する、又は外部から入手する。
【００７２】
次に、パラメータ生成部１３は、パラメータｐｐ’ｑｑ’及びＮを計算し、パラメータｐｐ’ｑｑ’及びＮを一時データ記憶部１２に書き込む（ＳＴ２）。
【００７３】
次に、パラメータ生成部１３は、位数がｐｐ’ｑｑ’である乗法群Ｇを生成し、Ｇの元ｇをＧからランダムに選択し、選択した元ｇを一時データ記憶部１２に書き込む（ＳＴ３）。位数がｐｐ’ｑｑ’である乗法群Ｇを生成するには、例えば、ＺＮ2＊の元をＺＮ2＊からランダムに選択し、選択した元を二乗して得られた値をｇとすれば良い。ここで、ＺＮ2＊はＺＮ2かつＮ２と互いに素な整数の集合（＝（Ｚ／Ｎ２Ｚ）＊）であり、合成数Ｎ２に対する乗法群ＺＮ2＊と呼んで良い。ＺＮ2は０以上Ｎ２未満の整数の集合（＝（Ｚ／Ｎ２Ｚ）である。
【数１】
2014178379.tif 000003
【００７４】
次に、鍵生成部１４は、一時データ記憶部１２に記憶されているパラメータｐｐ’ｑｑ’及びＮを取得し、各鍵の一部ａ，ｓ，ｖを集合｛１，…，ｐｐ’ｑｑ’｝からそれぞれランダムに選択する（ＳＴ４）。
【００７５】
続いて、鍵生成部１４は、ａ・ａ−１ｍｏｄＮ２＝１を満たすａ−１の値と、ｇｓｖの値とを計算し、暗号化鍵ａ，ｇｓｖ，ｇ，Ｎ、二次演算鍵ａ−１，ｓ，Ｎ、及び三次演算鍵ｖ，Ｎを一時データ記憶部１２に書き込む。ここで、通信部１５は、制御部１６に制御されて一時データ記憶部１２内の暗号化鍵ａ，ｇｓｖ，ｇ，Ｎを暗号化装置２０に送信する（ＳＴ５）。暗号化鍵ａ，ｇｓｖ，ｇ，Ｎは暗号化装置２０の暗号化鍵記憶部２４に記憶される。
【００７６】
次に、通信部１５は、制御部１６に制御されて一時データ記憶部１２内の二次演算鍵ａ−１，ｓ，Ｎを演算支援装置５０に送信する（ＳＴ６）。二次演算鍵ａ−１，ｓ，Ｎは演算支援装置５０の二次演算鍵記憶部５４に記憶される。
【００７７】
さらに、通信部１５は、制御部１６に制御されて一時データ記憶部１２内の三次演算鍵ｖ，Ｎを演算装置４０に送信する（ＳＴ７）。三次演算鍵ｖ，Ｎは演算装置４０の三次演算鍵記憶部４６に記憶される。なお、暗号化鍵は、ａ，ｓｖ，ｇ，Ｎであっても良いし、ａ，ｓ，ｖ，ｇ，Ｎであっても良い。
【００７８】
なお、ステップＳＴ５、ＳＴ６、ＳＴ７において、通信部１５は、Ｎ２も暗号化装置２０、演算支援装置５０、演算装置４０に送信しても良い。この場合、ステップＳＴ２においてパラメータ生成部１３は、Ｎ２も一時データ記憶部１２に書き込む。また、ｇ，Ｎ，Ｎ２は暗号化鍵、二次演算鍵、及び三次演算鍵に含めず、公開パラメータとして各装置に対して公開しておいても良い。まとめると、暗号鍵はａ，ｓ，ｖ（又はａ，ｓｖ）を含む。二次演算鍵はａ−１，ｓを含む。三次演算鍵はｖを含む。
【００７９】
これらのことは、後述する他の実施形態においても同様である。
【００８０】
以上により、鍵生成処理が完了する。なお、本明細書では、Ｇを乗法群と想定した記法を採用しているが、これに限らず、Ｇを加法群と想定した記法で表すことも可能である。
【００８１】
［１．暗号化処理］
以下に述べる暗号化処理は、暗号文（暗号化データ）を生成する処理である。
【００８２】
暗号化処理は、暗号化装置２０により、図６及び以下の各ステップＳＴ１１〜ＳＴ１４に示すように実行される。暗号化装置２０がｋ（ｋは自然数）個の平文（暗号化対象の数値データ）ｍ１，…，ｍｋを暗号化する例を説明する。各平文ｍｉはＺＮの元である。ＺＮは０以上Ｎ未満の整数の集合（＝（Ｚ／ＮＺ）である。
【００８３】
始めに、暗号化装置２０の暗号化パラメータ生成部２１は、ｋ個の乱数ｒ１，…，ｒｋをＺＮ2＊からランダムにそれぞれ選択する（ＳＴ１１）。次に、暗号化パラメータ生成部２１は、生成した乱数ｒ１，…，ｒｋを一時データ記憶部２２に書き込む（ＳＴ１２）。暗号文生成部２３は、一時データ記憶部２２から取得した乱数ｒ１，…，ｒｋと、暗号化鍵記憶部２４に記憶されている暗号化鍵ａ，ｇｓｖ，ｇ，Ｎとを用いて、次式により平文ｍ１，…，ｍｋを暗号化する（ＳＴ１３）。
【数２】
2014178379.tif 000004
【００８４】
暗号文生成部２３は、生成した暗号文Ｃｉ（ｉ＝１，…，ｋ）を一時データ記憶部２２に書き込む。通信部２５は、制御部２６に制御されて一時データ記憶部２２内の暗号文Ｃｉ（ｉ＝１，…，ｋ）を記憶装置３０に送信する（ＳＴ１４）。
【００８５】
なお、暗号化鍵ａは、前述したように鍵生成装置１０が生成しても良く、暗号化装置２０が生成しても良い。この場合、ステップＳＴ５において、鍵生成装置１０は、暗号化鍵ｇｓｖ，ｇ，Ｎを暗号化装置２０に送信し、ステップＳＴ１１において、暗号化装置２０の暗号化パラメータ生成部２１は、暗号化鍵ａを生成し、また、ａ−１の値を計算し、二次演算鍵ａ−１を演算支援装置５０に送信する。なお、暗号化装置２０がｐｐ’ｑｑ’の値を知らない場合、暗号化鍵ａをＺＮ2＊の中からランダムに選択すれば良い。
【００８６】
以上により、暗号化処理が完了する。
【００８７】
［２．一次演算処理］
以下に述べる一次演算処理は、暗号文（暗号化データ）を加減算する処理である。
【００８８】
一次演算処理は、演算装置４０により、図７及び以下の各ステップＳＴ２１〜ＳＴ２３に示すように実行される。演算装置４０が次式Ｆの正負を（後述する三次演算処理において）判定する例を説明する。
【数３】
2014178379.tif 000005
【００８９】
ここで、ｎｉは任意の整数である。また、Ｋは、式Ｆの計算に必要なインデックスｉの集合である。例えば、Ｆ＝２ｍ１−ｍ２の場合、ｎ１＝２，ｎ２＝−１，Ｋ＝｛１，２｝である。また、加減算の式Ｆにおける被減数ｍａと減数ｍｂとの間の大小関係を判定したい場合、例えば、Ｆ＝ｍａ−ｍｂ＝３ｍ２−４ｍ３＋ｍ５とし、ｎ２＝３，ｎ３＝−４，ｎ５＝１，Ｋ＝｛２，３，５｝である。ここで、被減数ｍａは３ｍ２＋ｍ５であり、減数ｍｂは４ｍ３である。また、数値ａ，ｂの大小関係を判定したい場合、Ｆ＝ｍａ−ｍｂ＝ｍ１−ｍ２とし、ｎ１＝１，ｎ２＝−１，Ｋ＝｛１，２｝とすればよい。
【００９０】
演算装置４０の通信部４４は、制御部４５に制御されて、式Ｆの計算に必要な暗号文Ｃｉ（ｉ∈Ｋ）を記憶装置３０より取得し、一時データ記憶部４１に記憶する（ＳＴ２１）。次に、計算部４２は、一時データ記憶部４１から取得した暗号文Ｃｉ（ｉ∈Ｋ）を用いて、次式により、一次演算結果Ｘ１，Ｘ２を計算する（ＳＴ２２）。
【数４】
2014178379.tif 000006
【００９１】
計算部４２は、生成した一次演算結果Ｘ１，Ｘ２を一時データ記憶部４１に書き込む。通信部４４は、制御部４５に制御されて一時データ記憶部４１内の一次演算結果Ｘ１，Ｘ２を演算支援装置５０に送信する（ＳＴ２３）。
【００９２】
以上により、一次演算処理が完了する。
【００９３】
［３．二次演算処理］
以下に述べる二次演算処理は、加減算された暗号文（暗号化データ）をランダム化する処理である。二次演算処理は、演算支援装置５０により、図８及び以下の各ステップＳＴ３１〜ＳＴ３４に示すように実行される。
【００９４】
演算支援装置５０の二次演算処理パラメータ生成部５１は、パラメータＬ，Ｊ，β，Ｄを生成し、パラメータＬ，Ｊ，β，Ｄを一時データ記憶部５２に書き込む（ＳＴ３１）。これらのパラメータＬ，Ｊ，β，Ｄを選択する指標については後述する。なお、パラメータＬ，Ｊ，β，Ｄは外部から与えられても良い。この場合、ステップＳＴ３１において、二次演算処理パラメータ生成部５１は、外部から取得したパラメータＬ，Ｊ，β，Ｄを一時データ記憶部５２に書き込む。
【００９５】
次に、二次演算処理パラメータ生成部５１は、β個の乱数ｒ’ｉ（ｉ＝０，…，β−１）を集合｛１，…，Ｌ｝の中からランダムにそれぞれ選択する。ここで、β＝１であっても良いし、β≧２であっても良い。これは他の実施形態や変形例においても同様である。また、乱数ｚを集合｛０，１，…，Ｊ｝の中からランダムに選択する。そして、二次演算処理パラメータ生成部５１は、次式に示す乱数Ｒを計算し、乱数Ｒ，ｚを一時データ記憶部５２に書き込む（ＳＴ３２）。
【数５】
2014178379.tif 000007
【００９６】
次に、計算部５３は、二次演算鍵記憶部５４に記憶されている二次演算鍵ａ−１，ｓ，Ｎと、一時データ記憶部５２から取得した一次演算結果Ｘ１，Ｘ２及び乱数Ｒ，ｚとを用いて、次式により、二次演算結果Ｙ１，Ｙ２を計算する（ＳＴ３３）。
【数６】
2014178379.tif 000008
【００９７】
計算部５３は、生成した二次演算結果Ｙ１，Ｙ２を一時データ記憶部５２に書き込む。通信部５５は、制御部５６に制御されて一時データ記憶部５２内の一次演算結果Ｙ１，Ｙ２を演算装置４０に送信する（ＳＴ３４）。
【００９８】
ここで、各パラメータを選択する指標について説明する。正負判定可能な絶対値の最大値をＤとする。すなわち、０＜Ｆ＜ＤのときＦを正と判定し，−Ｄ＜Ｆ＜０のときＦを負と判定できるようにしたいとする。このとき、二次演算処理パラメータ生成部５１は、次式を満たすように、β個の乱数ｒ’ｉを選択する。
【数７】
2014178379.tif 000009
【００９９】
また、二次演算処理パラメータ生成部５１は、β個の乱数ｒ’ｉの積であるＲを上記のように選択したとき，Ｒ＜Ｊとなる確率が十分小さくなるようにＪを選択する。
【０１００】
以上により、二次演算処理が完了する。
【０１０１】
［４．三次演算処理］
以下に述べる三次演算処理は、ランダム化及び加減算された暗号文（暗号化データ）から加減算の式における被減数と減数との間の大小関係を判定する処理である。
【０１０２】
三次演算処理は、演算装置４０により、図９及び以下の各ステップＳＴ４１〜ＳＴ４２に示すように実行される。
【０１０３】
演算装置４０の計算部４２は、三次演算鍵記憶部４６に記憶されている三次演算鍵ｖ，Ｎと、一時データ記憶部４１から取得した二次演算結果Ｙ１，Ｙ２とを用いて、次式により、Ｗ’を計算する。
【数８】
2014178379.tif 000010
【０１０４】
Ｗ’がＮの倍数でない場合、以降の計算を行わず、三次演算処理を終了する。そうでない場合（Ｗ’がＮの倍数である場合）、計算部４２は、次式により、三次演算結果Ｗを計算する（ＳＴ４１）。
【数９】
2014178379.tif 000011
【０１０５】
次に、判定部４３は、Ｗ＜Ｎ／２ならば式Ｆは正であると判定し、そうでないならば式Ｆは負（又は０）と判定する（ＳＴ４２）。
【０１０６】
Ｆ＝Ｍａ−Ｍｂの形で表されるとき、Ｆが正であれば、Ｍａ＞Ｍｂと判定できる。Ｆが負であれば、Ｍａ≦Ｍｂと判定できる。
【０１０７】
以上により、三次演算処理が完了する。
【０１０８】
なお、ステップＳＴ４２において、判定部４３は、−Ｊ≦Ｗ≦０ならばＦ＝０と判定しても良い。この場合、判定部４３は、−Ｎ／２＜Ｗ＜−ＪならばＦは負であると判定する。これは他の実施形態や変形例においても同様である。
【０１０９】
ここで、Ｆ＝３ｍ２−４ｍ３＋ｍ５の場合を例に取って、Ｗ＝ＦＲ−ｚとなることを示す。一次演算結果Ｘ１，Ｘ２、二次演算結果Ｙ１，Ｙ２及び三次演算結果Ｗはそれぞれ以下のように表される。
【数１０】
2014178379.tif 000012
【０１１０】
三次演算結果Ｗにおいては、Ｗ＝ＦＲ−ｚであり、ＦＲからｚを引いている。しかしながら、上述したようにＲの値を適切に設定すれば、ステップＳＴ４２において判定部４３は、乱数ｚの値に影響を受けることなく、正しくＦの正負判定を行うことができる。
【０１１１】
上述した例では、Ｆ＝Ｍａ−Ｍｂ＝３ｍ２−４ｍ３＋ｍ５であるので、例えば、被減数Ｍａ＝３ｍ２＋ｍ５、減数Ｍｂ＝４ｍ３とおくことにより、被減数（３ｍ２＋ｍ５）と減数（４ｍ３）との間の大小関係を判定できる。また、例えば、被減数Ｍａ＝３ｍ２、減数Ｍｂ＝４ｍ３−ｍ５とみなすことにより、被減数（３ｍ２）と減数（４ｍ３−ｍ５）との間の大小関係を判定することもできる。
【０１１２】
上述したように本実施形態によれば、演算装置４０は、各暗号化データに基づいて、各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成する。演算支援装置５０は、一次演算結果、二次演算鍵及び乱数に基づいて、一次演算結果をランダム化してなる二次演算結果を生成する。演算装置４０は、二次演算結果及び三次演算鍵に基づいて、加減算した式の演算結果を乱数のみで秘匿化したデータに相当する三次演算結果を生成し、三次演算結果に基づいて式における被減数と減数との間の大小関係を判定する。
【０１１３】
以上のように、各数値を暗号化してなる各暗号化データを用いて当該各数値を加減算でき、当該加減算における被減数と減数との間の大小関係を判定することができる。
【０１１４】
また、暗号化データＥ（ａ），Ｅ（ｂ）の復号鍵と、比較鍵（三次演算鍵）とを異ならせることができ、比較鍵を用いても暗号化データＥ（ａ），Ｅ（ｂ）を復号できない。
【０１１５】
（変形例１）
本実施形態に係る暗号化データ演算システムにおいて、暗号文Ｃｉを復号する復号装置（図示せず）が存在していても良い。復号装置は、復号鍵ｓｖ，ａ−１，Ｎ（又はｓ，ｖ，ａ−１，Ｎ）を記憶した記憶部と、計算を実行する計算部とを備えている。復号装置は、以下の処理により暗号文Ｃｉを復号できる。復号装置の計算部は、記憶部内の復号鍵ｓｖ，ａ−１，Ｎと、暗号文Ｃｉとを用いて、次式によりＤ’を計算する。
【数１１】
2014178379.tif 000013
【０１１６】
Ｄ’がＮの倍数でない場合、以降の計算を行わず、復号処理を終了する。そうでない場合（Ｄ’がＮの倍数である場合）、復号装置の計算部は、次式により、平文を計算する。
【数１２】
2014178379.tif 000014
【０１１７】
（第２の実施形態）
第１の実施形態においては、二次演算鍵ｓと三次演算鍵ｖとがそれぞれ１つ生成される例を説明したが、これに限らず、二次演算鍵と三次演算鍵とがそれぞれ複数生成されても良い。以下、ある期間ｔ１にｓｔ１，ｖｔ１が用いられ、次の期間ｔ２にｓｔ２，ｖｔ２が用いられる、といった具合に、複数の二次演算鍵ｓｔ１，ｓｔ２，…と複数の三次演算鍵ｖｔ１，ｖｔ２，…とが生成される例を説明する。
【０１１８】
以下、本実施形態における鍵生成処理、暗号化処理、一次演算処理、二次演算処理、及び三次演算処理について説明する。但し、第１の実施形態と共通する部分については、同一の符号を用いて説明し、重複した説明を省略する。
【０１１９】
［０．鍵生成処理］
ステップＳＴ１〜ＳＴ３の処理は第１の実施形態と同一である。
【０１２０】
鍵生成部１４は、一時データ記憶部１２に記憶されているｐｐ’ｑｑ’及びＮを取得し、ａ，ｓｔ，ｖＴを｛１，…，ｐｐ’ｑｑ’｝からそれぞれランダムに選択する（ＳＴ４’）。ここで、表記を一般化するために、ｓの添え字としてｔを、ｖの添え字としてＴをそれぞれ用いている。ｓｔは期間ｔに用いられるｓの値という意味であり、ｖＴは期間Ｔに用いられるｖの値という意味である。期間ｔの値と期間Ｔの値は異なっていても良いし、ｔ＝Ｔであっても良い。
【０１２１】
この場合、暗号化鍵はａ，ｇ＾｛ｓtｖT｝，ｇ，Ｎと表される（但し、＾は、ベキ乗を表す記号である。）。二次演算鍵はａ−１，ｓｔ，Ｎと表される。三次演算鍵はｖＴ，Ｎと表される。
【数１３】
2014178379.tif 000015
【０１２２】
鍵生成部１４は、各期間で用いられる暗号化鍵、二次演算鍵、及び三次演算鍵を各期間が来る度に生成しても良いし、予め複数期間分の暗号化鍵、二次演算鍵、及び三次演算鍵を生成し、暗号化装置２０、演算支援装置５０、及び演算装置４０へそれぞれ渡しておいても良い。
【０１２３】
［１．暗号化処理］
ステップＳＴ１１、ＳＴ１２、及びＳＴ１４の処理は第１の実施形態と同一である。
【０１２４】
暗号文生成部２３は、一時データ記憶部２２から取得した乱数ｒ１，…，ｒｋと、暗号化鍵記憶部２４に記憶されている暗号化鍵ａ，ｇ＾｛ｓtｖT｝，ｇ，Ｎとを用いて、次式により平文ｍ１，…，ｍｋを暗号化する（ＳＴ１３’）。
【数１４】
2014178379.tif 000016
【０１２５】
［２．一次演算処理］
ステップＳＴ２１の処理は第１の実施形態と同一である。
【０１２６】
計算部４２は、一時データ記憶部４１から取得した暗号文Ｃｉ（ｉ∈Ｋ）を用いて、各（ｔ，Ｔ）について、次式により、一次演算結果｛Ｘ１（ｔ，Ｔ），Ｘ３，Ｘ４｝，Ｘ２を計算する（ＳＴ２２’）。
【数１５】
2014178379.tif 000017
【０１２７】
ここで、Ｘ１（ｔ，Ｔ）は、（Ｃｉ，３，Ｃｉ，４）が同一である、一つ又は複数のＣｉを用いて計算される。例えば、（ｔ，Ｔ）＝（１，１）のＣｉと、（ｔ，Ｔ）＝（２，１）のＣｉが存在する場合、Ｘ１（１，１）とＸ１（２，１）とをそれぞれ計算することになる。各（ｔ，Ｔ）について計算したＸ１（ｔ，Ｔ），Ｘ３，Ｘ４の集合を｛Ｘ１（ｔ，Ｔ），Ｘ３，Ｘ４｝と表記する。
【０１２８】
計算部４２は、生成した一次演算結果｛Ｘ１（ｔ，Ｔ），Ｘ３，Ｘ４｝，Ｘ２を一時データ記憶部４１に書き込む。通信部４４は、制御部４５に制御されて一時データ記憶部４１内の一次演算結果｛Ｘ１（ｔ，Ｔ），Ｘ３，Ｘ４｝，Ｘ２を演算支援装置５０に送信する（ＳＴ２３’）。
【０１２９】
［３．二次演算処理］
ステップＳＴ３１及びステップＳＴ３２の処理は第１の実施形態と同一である。
【０１３０】
計算部５３は、二次演算鍵記憶部５４に記憶されている二次演算鍵ｓｔ，Ｎと、一時データ記憶部５２から取得した一次演算結果｛Ｘ１（ｔ，Ｔ）｝とを用いて、各（ｔ，Ｔ）について、次式により、Ｙ１（ｔ，Ｔ）を計算し、Ｙ１（ｔ，Ｔ）を一時データ記憶部５２に書き込む。
【数１６】
2014178379.tif 000018
【０１３１】
次に、計算部５３は、二次演算鍵記憶部５４に記憶されている二次演算鍵ａ−１，Ｎと、一時データ記憶部５２から取得したＹ１（ｔ，Ｔ）、一次演算結果Ｘ２、及び乱数Ｒ，ｚとを用いて、各Ｔについて、次式により、二次演算結果｛Ｙ１（Ｔ），Ｙ３｝，Ｙ２を計算する（ＳＴ３３’）。
【数１７】
2014178379.tif 000019
【０１３２】
ここで、Ｙ１（Ｔ）は、Ｘ４が同一である、一つ又は複数のＸ１（ｔ，Ｔ）を用いて計算される。例えば、（ｔ，Ｔ）＝（１，１）のＸ１（ｔ，Ｔ）と、（ｔ，Ｔ）＝（１，２）のＸ１（ｔ，Ｔ）が存在する場合、Ｙ１（１）とＹ２（２）とをそれぞれ計算することになる。各Ｔについて計算したＹ１（Ｔ），Ｙ３の集合を｛Ｙ１（Ｔ），Ｙ３｝と表記する。
【０１３３】
計算部５３は、生成した二次演算結果｛Ｙ１（Ｔ），Ｙ３｝，Ｙ２を一時データ記憶部５２に書き込む。通信部５５は、制御部５６に制御されて一時データ記憶部５２内の二次演算結果｛Ｙ１（Ｔ），Ｙ３｝，Ｙ２を演算装置４０に送信する（ＳＴ３４’）。
【０１３４】
［４．三次演算処理］
ステップＳＴ４２の処理は第１の実施形態と同一である。
【０１３５】
計算部４２は、三次演算鍵記憶部４６に記憶されている三次演算鍵ｖＴ，Ｎと、一時データ記憶部４１から取得した二次演算結果｛Ｙ１（Ｔ），Ｙ３｝，Ｙ２とを用いて、次式により、Ｗ’を計算する。
【数１８】
2014178379.tif 000020
【０１３６】
Ｗ’がＮの倍数でない場合、以降の計算を行わず、三次演算処理を終了する。そうでない場合（Ｗ’がＮの倍数である場合）、計算部４２は、次式により、三次演算結果Ｗを計算する（ＳＴ４１’）。
【数１９】
2014178379.tif 000021
【０１３７】
第１の実施形態と同様に、Ｆ＝Ｍａ−Ｍｂの形で式が表されるとき、式Ｆが正であれば、Ｍａ＞Ｍｂと判定できる。式Ｆが負であれば、Ｍａ≦Ｍｂと判定できる。これにより、三次演算処理が完了する。
【０１３８】
次に、以上のような一次演算処理、二次演算処理及び三次演算処理について、例を挙げて説明する。具体的には、Ｆ＝ｍ１−ｍ２＋ｍ３＋ｍ４＋ｍ５であり、次式に示す暗号文Ｃ1，Ｃ2，Ｃ3，Ｃ4，Ｃ5が記憶装置３０に記憶されている場合を例に挙げて、Ｗ＝ＦＲ−ｚとなることを示す。
【数２０】
2014178379.tif 000022
【０１３９】
【数２１】
2014178379.tif 000023
【０１４０】
上述の例においてはＦ＝Ｍａ−Ｍｂ＝ｍ１−ｍ２＋ｍ３＋ｍ４＋ｍ５であるので、例えば、Ｍａ＝ｍ１＋ｍ３＋ｍ４＋ｍ５、Ｍｂ＝ｍ２とおくことができ、ｍ１＋ｍ３＋ｍ４＋ｍ５と、ｍ２との大小比較を行うことができる。
【０１４１】
また、例えば、Ｍａ＝ｍ１＋ｍ３＋ｍ４、Ｍｂ＝ｍ２−ｍ５とみなすこともできるので、ｍ１＋ｍ３＋ｍ４と、ｍ２−ｍ５との大小比較を行っているとみなすこともできる。
【０１４２】
上述したように本実施形態によれば、複数の期間ｔ１，ｔ２に応じて、複数の二次演算鍵ｓｔ１，ｓｔ２と複数の三次演算鍵ｖｔ１，ｖｔ２とをそれぞれ生成する構成により、第１の実施形態の効果に加え、鍵漏洩の被害を抑えつつ，期間ｔ１において生成された暗号文Ｅ（ｔ１）（ａ）と、期間ｔ２において生成された暗号文Ｅ（ｔ２）（ｂ）とを用い、各数値を暗号化した状態で大小関係を判定することができる。
【０１４３】
補足すると、一般に、鍵漏洩の被害を抑制する観点から、定期的に比較鍵を更新することが望ましい。しかしながら、従来の大小関係の判定方法では、比較鍵の更新前に生成した暗号化データＥ(t1)（ａ）と、比較鍵の更新後に生成した暗号化データＥ(t2)（ｂ）とを用いた場合には、数値ａ，ｂの値の大小を判定できない問題がある。
【０１４４】
これに対し、本実施形態によれば、前述した通り、期間ｔ１において生成された暗号文Ｅ（ｔ１）（ａ）と、期間ｔ２において生成された暗号文Ｅ（ｔ２）（ｂ）とを用い、各数値を暗号化した状態で大小関係を判定することができる。
【０１４５】
（変形例２）
本実施形態に係る暗号化データ演算システムにおいて、暗号文Ｃｉを復号する復号装置（図示せず）が存在していても良い。復号装置は、復号鍵ｓｔｖＴ，ａ−１，Ｎ（又はｓｔ，ｖＴ，ａ−１，Ｎ）を記憶した記憶部と、計算を実行する計算部とを備えている。復号装置は、以下の処理により暗号文Ｃｉを復号できる。復号装置の計算部は、記憶部内の復号鍵ｓｔｖＴ，ａ−１，Ｎと、暗号文Ｃｉとを用いて、次式によりＤ’を計算する。
【数２２】
2014178379.tif 000024
【０１４６】
Ｄ’がＮの倍数でない場合、以降の計算を行わず、復号処理を終了する。そうでない場合（Ｄ’がＮの倍数である場合）、復号装置の計算部は、次式により、平文を計算する。
【数２３】
2014178379.tif 000025
【０１４７】
（変形例３）
第２の実施形態においては、ある期間ｔｉにｓｉ，ｖｉが用いられる例を説明したが、これに限らず、ユーザ毎（暗号化装置２０毎）に異なるｓｉ，ｖｉを用いても良い。この場合、第２の実施形態において、ｔｉをユーザの識別情報（暗号化装置２０の識別情報）とみなせば良い。つまり、鍵生成処理、暗号化処理、一次演算処理、二次演算処理、及び三次演算処理の各処理は同一で、インデックスの意味を変えるだけ（すなわち、「期間」を「ユーザ（暗号化装置２０）」に置き換えるだけ）で良い。
【０１４８】
（変形例４）
二次演算鍵ｓｉは１つのみで、三次演算鍵ｖｉが複数であっても良い。この場合、第２の実施形態においてｓ１＝ｓ２＝…＝ｓと置き換えれば良い。また、二次演算鍵ｓｉは複数で、三次演算鍵ｖｉが１つのみであっても良い。この場合、第２の実施形態においてｖ１＝ｖ２＝…＝ｖと置き換えれば良い。
【０１４９】
以上説明した少なくとも一つの実施形態によれば、演算装置４０は、各暗号化データに基づいて、各数値を加減算した式の演算結果を暗号化したデータに相当する一次演算結果を生成する。演算支援装置５０は、一次演算結果、二次演算鍵及び乱数に基づいて、一次演算結果をランダム化してなる二次演算結果を生成する。演算装置４０は、二次演算結果及び三次演算鍵に基づいて、加減算した式の演算結果を乱数のみで秘匿化したデータに相当する三次演算結果を生成し、三次演算結果に基づいて式における被減数と減数との間の大小関係を判定する。
【０１５０】
以上のように、各数値を暗号化してなる各暗号化データを用いて当該各数値を加減算でき、当該加減算における被減数と減数との間の大小関係を判定することができる。
【０１５１】
なお、上記の各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１５２】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１５３】
そして、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１５４】
さらに、各実施形態における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１５５】
また、記憶媒体は１つに限らず、複数の媒体から上記の各実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１５６】
なお、各実施形態におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記の各実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１５７】
また、各実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１５８】
なお、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１５９】
１０…鍵生成装置、１１…鍵生成パラメータ記憶部、１２，２２，４１，５２…一時データ記憶部、１３…パラメータ生成部、１４…鍵生成部、１５，２５，３２，４４，５５…通信部、１６，２６，３３，４５，５６…制御部、２０…暗号化装置、２１…暗号化パラメータ生成部、２３…暗号文生成部、２４…暗号化鍵記憶部、３０…記憶装置、３１…暗号文記憶部、４０…演算装置、４２，５３…計算部、４３…判定部、４６…三次演算鍵記憶部、５０…演算支援装置、５１…二次演算処理パラメータ生成部、５４…二次演算鍵記憶部。
【図１】
2014178379.tif 000026
【図２】
2014178379.tif 000027
【図３】
2014178379.tif 000028
【図４】
2014178379.tif 000029
【図５】
2014178379.tif 000030
【図６】
2014178379.tif 000031
【図７】
2014178379.tif 000032
【図８】
2014178379.tif 000033
【図９】
2014178379.tif 000034