(57)【要約】【課題】秘密計算における計算量及び通信量を調節できる大小比較の計算システム、計算方法及び計算プログラムを提供する。【解決手段】計算システム１は、二値が取り得る値をリーフノードとして持つ二分木を記憶する記憶部１０と、ｓｏｍｅｗｈａｔ準同型暗号の秘密鍵を生成し公開鍵を共有する鍵共有部２１と、ポイントエンコーディング部２２と、レンジエンコーディング部２３と、ダミーノードを追加するノード追加部２４と、暗号化部２５と、加法準同型性を用いて各階層のノードの減算を行う加法演算部２６と、減算の結果を設定数ずつのグループに分割し、乗法準同型性を用いてグループ毎に乗算を行う乗法演算部２７と、グループ毎の乗算の結果それぞれについて、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルを実行するゼロ比較処理部２８と、加法準同型性を用いてグループの値の総和とグループの数との差に基づく大小比較結果を出力する出力部２９と、を備える。【選択図】図１
2019040047.tif 000002
【特許請求の範囲】
【請求項１】
第１の数値を記憶する第１の端末と、第２の数値を記憶する第２の端末との間で、前記第１の数値と前記第２の数値との大小比較を行う計算システムであって、
前記第１の数値及び前記第２の数値が取り得る値をリーフノードとして持ち、全ノードの値が少なくとも各階層において互いに異なる二分木を記憶する記憶部と、
ｓｏｍｅｗｈａｔ準同型暗号の秘密鍵を生成し、当該秘密鍵に対応する公開鍵を前記第１の端末及び前記第２の端末で共有する鍵共有部と、
前記第１の端末において、前記第１の数値に対応するリーフノードからルートノードまでの経路上の全ノードからなる第１の集合を求めるポイントエンコーディング部と、
前記第２の端末において、前記第２の数値以上の値に対応するリーフノードの範囲のみを、全てカバーする最少のノードからなる第２の集合を求めるレンジエンコーディング部と、
前記第２の端末において、前記第１の集合のノード数と前記第２の集合のノード数とが等しくなるように、前記第２の集合に対して、前記二分木とは値が異なるダミーノードを追加するノード追加部と、
前記第１の集合及び前記第２の集合を、前記ｓｏｍｅｗｈａｔ準同型暗号により暗号化する暗号化部と、
前記ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、前記第１の集合及び前記第２の集合の各階層のノードの減算を行う加法演算部と、
前記減算の結果を設定数ずつのグループに分割し、前記ｓｏｍｅｗｈａｔ準同型暗号の乗法準同型性を用いて、前記グループ毎に前記減算の結果の乗算を行う乗法演算部と、
前記グループ毎の乗算の結果それぞれについて、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルにより、「０」及び「０以外」の暗号データを、「０」及び「１」の暗号データに変換するゼロ比較処理部と、
前記ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、前記グループの値の総和と前記グループの数との差に基づく大小比較結果を出力する出力部と、を備える計算システム。
【請求項２】
前記ｓｏｍｅｗｈａｔ準同型暗号は、乗算可能回数が異なる複数の暗号方式から選択され、
前記乗法演算部は、前記乗算可能回数に基づいて、分割する際の前記設定数を決定する請求項１に記載の計算システム。
【請求項３】
前記ｓｏｍｅｗｈａｔ準同型暗号は、前記グループに分割する際の前記設定数に基づいて、乗算可能回数が異なる複数の暗号方式から選択される請求項１に記載の計算システム。
【請求項４】
前記二分木におけるノードの値は、階層情報を含む整数値である請求項１から請求項３のいずれかに記載の計算システム。
【請求項５】
第１の数値を記憶する第１の端末と、第２の数値を記憶する第２の端末との間で、前記第１の数値と前記第２の数値との大小比較を行う計算方法であって、
前記第１の端末及び前記第２の端末がそれぞれ、前記第１の数値及び前記第２の数値が取り得る値をリーフノードとして持ち、全ノードの値が少なくとも各階層において互いに異なる二分木を記憶し、
ｓｏｍｅｗｈａｔ準同型暗号の秘密鍵を生成し、当該秘密鍵に対応する公開鍵を前記第１の端末及び前記第２の端末で共有する鍵共有ステップと、
前記第１の端末において、前記第１の数値に対応するリーフノードからルートノードまでの経路上の全ノードからなる第１の集合を求めるポイントエンコーディングステップと、
前記第２の端末において、前記第２の数値以上の値に対応するリーフノードの範囲のみを、全てカバーする最少のノードからなる第２の集合を求めるレンジエンコーディングステップと、
前記第２の端末において、前記第１の集合のノード数と前記第２の集合のノード数とが等しくなるように、前記第２の集合に対して、前記二分木とは値が異なるダミーノードを追加するノード追加ステップと、
前記第１の集合及び前記第２の集合を、前記ｓｏｍｅｗｈａｔ準同型暗号により暗号化する暗号化ステップと、
前記ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、前記第１の集合及び前記第２の集合の各階層のノードの減算を行う加法演算ステップと、
前記減算の結果を設定数ずつのグループに分割し、前記ｓｏｍｅｗｈａｔ準同型暗号の乗法準同型性を用いて、前記グループ毎に前記減算の結果の乗算を行う乗法演算ステップと、
前記グループ毎の乗算の結果それぞれについて、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルにより、「０」及び「０以外」の暗号データを、「０」及び「１」の暗号データに変換するゼロ比較処理ステップと、
前記ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、前記グループの値の総和と前記グループの数との差に基づく大小比較結果を出力する出力ステップと、を実行する計算方法。
【請求項６】
請求項１から請求項４のいずれかに記載の計算システムにおける前記第１の端末又は前記第２の端末としてコンピュータを機能させるための計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算により大小比較を行う計算システム、計算方法及び計算プログラムに関する。
【背景技術】
【０００２】
従来、プライバシ保護型のデータマイニングアルゴリズム等を実現するにあたり、二者間での秘密計算（ｓｅｃｕｒｅ  ｃｏｍｐｕｔａｔｉｏｎ）、つまり互いの情報を教えることなく演算を行い、演算結果のみを取得する技術が必要とされ、研究されている。
秘密計算の一つに、二値の大小比較プロトコルがある。このプロトコルは、例えば非特許文献１でセキュアなｋ−ｍｅａｎｓアルゴリズムを実現するサブプロトコルとして用いられる等、広く研究されている。非特許文献２では、二値の大小比較プロトコルの実現手法が提案されている。また、非特許文献３では、Ｓｏｍｅｗｈａｔ準同型暗号を用いて二値の大小比較を行う手法が提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｂｕｎｎ，  Ｐａｕｌ，  ａｎｄ  Ｒａｆａｉｌ  Ｏｓｔｒｏｖｓｋｙ．  “Ｓｅｃｕｒｅ  ｔｗｏ−ｐａｒｔｙ  ｋ−ｍｅａｎｓ  ｃｌｕｓｔｅｒｉｎｇ．”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １４ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｓｅｃｕｒｉｔｙ．  ＡＣＭ，  ２００７．
【非特許文献２】Ｖｅｕｇｅｎ，  Ｔｈｉｊｓ，  ｅｔ  ａｌ．  “Ｓｅｃｕｒｅ  ｃｏｍｐａｒｉｓｏｎ  ｐｒｏｔｏｃｏｌｓ  ｉｎ  ｔｈｅ  ｓｅｍｉ−ｈｏｎｅｓｔ  ｍｏｄｅｌ．”  ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｆ  Ｓｅｌｅｃｔｅｄ  Ｔｏｐｉｃｓ  ｉｎ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  ９．７  （２０１５）：  １２１７−１２２８．
【非特許文献３】Ｇｅｎｔｒｙ，  Ｃｒａｉｇ，  ｅｔ  ａｌ．  “Ｐｒｉｖａｔｅ  ｄａｔａｂａｓｅ  ａｃｃｅｓｓ  ｗｉｔｈ  ｈｅ−ｏｖｅｒ−ｏｒａｍ  ａｒｃｈｉｔｅｃｔｕｒｅ．”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｎｅｔｗｏｒｋ  Ｓｅｃｕｒｉｔｙ．  Ｓｐｒｉｎｇｅｒ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｐｕｂｌｉｓｈｉｎｇ，  ２０１５．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、Ｓｏｍｅｗｈａｔ準同型暗号は、原理上、復号可能な乗算の回数に上限があり、この乗算可能回数によって計算時間が異なる。したがって、Ｓｏｍｅｗｈａｔ準同型暗号を用いて二値の大小比較プロトコルを実装する場合、計算量又は二者間の通信量が膨大となる可能性があった。
【０００５】
本発明は、秘密計算における計算量及び通信量を調節できる大小比較の計算システム、計算方法及び計算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る計算システムは、第１の数値を記憶する第１の端末と、第２の数値を記憶する第２の端末との間で、前記第１の数値と前記第２の数値との大小比較を行うシステムであって、前記第１の数値及び前記第２の数値が取り得る値をリーフノードとして持ち、全ノードの値が少なくとも各階層において互いに異なる二分木を記憶する記憶部と、ｓｏｍｅｗｈａｔ準同型暗号の秘密鍵を生成し、当該秘密鍵に対応する公開鍵を前記第１の端末及び前記第２の端末で共有する鍵共有部と、前記第１の端末において、前記第１の数値に対応するリーフノードからルートノードまでの経路上の全ノードからなる第１の集合を求めるポイントエンコーディング部と、前記第２の端末において、前記第２の数値以上の値に対応するリーフノードの範囲のみを、全てカバーする最少のノードからなる第２の集合を求めるレンジエンコーディング部と、前記第２の端末において、前記第１の集合のノード数と前記第２の集合のノード数とが等しくなるように、前記第２の集合に対して、前記二分木とは値が異なるダミーノードを追加するノード追加部と、前記第１の集合及び前記第２の集合を、前記ｓｏｍｅｗｈａｔ準同型暗号により暗号化する暗号化部と、前記ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、前記第１の集合及び前記第２の集合の各階層のノードの減算を行う加法演算部と、前記減算の結果を設定数ずつのグループに分割し、前記ｓｏｍｅｗｈａｔ準同型暗号の乗法準同型性を用いて、前記グループ毎に前記減算の結果の乗算を行う乗法演算部と、前記グループ毎の乗算の結果それぞれについて、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルにより、「０」及び「０以外」の暗号データを、「０」及び「１」の暗号データに変換するゼロ比較処理部と、前記ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、前記グループの値の総和と前記グループの数との差に基づく大小比較結果を出力する出力部と、を備える。
【０００７】
前記ｓｏｍｅｗｈａｔ準同型暗号は、乗算可能回数が異なる複数の暗号方式から選択され、前記乗法演算部は、前記乗算可能回数に基づいて、分割する際の前記設定数を決定してもよい。
【０００８】
前記ｓｏｍｅｗｈａｔ準同型暗号は、前記グループに分割する際の前記設定数に基づいて、乗算可能回数が異なる複数の暗号方式から選択されてもよい。
【０００９】
前記二分木におけるノードの値は、階層情報を含む整数値であってもよい。
【００１０】
本発明に係る計算方法は、第１の数値を記憶する第１の端末と、第２の数値を記憶する第２の端末との間で、前記第１の数値と前記第２の数値との大小比較を行う方法であって、前記第１の端末及び前記第２の端末がそれぞれ、前記第１の数値及び前記第２の数値が取り得る値をリーフノードとして持ち、全ノードの値が少なくとも各階層において互いに異なる二分木を記憶し、ｓｏｍｅｗｈａｔ準同型暗号の秘密鍵を生成し、当該秘密鍵に対応する公開鍵を前記第１の端末及び前記第２の端末で共有する鍵共有ステップと、前記第１の端末において、前記第１の数値に対応するリーフノードからルートノードまでの経路上の全ノードからなる第１の集合を求めるポイントエンコーディングステップと、前記第２の端末において、前記第２の数値以上の値に対応するリーフノードの範囲のみを、全てカバーする最少のノードからなる第２の集合を求めるレンジエンコーディングステップと、前記第２の端末において、前記第１の集合のノード数と前記第２の集合のノード数とが等しくなるように、前記第２の集合に対して、前記二分木とは値が異なるダミーノードを追加するノード追加ステップと、前記第１の集合及び前記第２の集合を、前記ｓｏｍｅｗｈａｔ準同型暗号により暗号化する暗号化ステップと、前記ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、前記第１の集合及び前記第２の集合の各階層のノードの減算を行う加法演算ステップと、前記減算の結果を設定数ずつのグループに分割し、前記ｓｏｍｅｗｈａｔ準同型暗号の乗法準同型性を用いて、前記グループ毎に前記減算の結果の乗算を行う乗法演算ステップと、前記グループ毎の乗算の結果それぞれについて、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルにより、「０」及び「０以外」の暗号データを、「０」及び「１」の暗号データに変換するゼロ比較処理ステップと、前記ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、前記グループの値の総和と前記グループの数との差に基づく大小比較結果を出力する出力ステップと、を実行する。
【００１１】
本発明に係る計算プログラムは、前記計算システムにおける前記第１の端末又は前記第２の端末としてコンピュータを機能させるためのものである。
【発明の効果】
【００１２】
本発明によれば、大小比較を行う秘密計算において、計算量及び通信量を調節できる。
【図面の簡単な説明】
【００１３】
【図１】実施形態に係る計算システムの機能構成を示すブロック図である。
【図２】実施形態に係るポイントエンコーディングを例示する図である。
【図３】実施形態に係るレンジエンコーディングを例示する図である。
【図４】実施形態に係る二値の大小比較の仕組みを説明する図である。
【図５】実施形態に係る計算方法を例示するフローチャートである。
【発明を実施するための形態】
【００１４】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係る計算システム１の機能構成を示すブロック図である。
計算システム１は、第１の端末Ａと、第２の端末Ｂとを備え、二者がそれぞれ記憶している数値の大小比較を、秘密計算により行う。
【００１５】
端末Ａ及び端末Ｂは、それぞれ記憶部１０及び制御部２０の他、入出力デバイス及び通信インタフェース等を備えた情報処理装置（コンピュータ）であり、各端末は、それぞれ記憶部１０に格納されたソフトウェア（計算プログラム）を制御部２０が実行することにより、本実施形態の各機能を実現する。
【００１６】
記憶部１０は、端末Ａ及び端末Ｂが記憶している計算対象の数値が取り得る値をリーフノードとして持ち、全ノードの値が少なくとも各階層において互いに異なる二分木を記憶する。
取り得る値の範囲が［１，２ｎ］であれば、リーフノード（階層：０）の数は２ｎ、上位の階層１，２，・・・のノード数は、順に半数になり、ルートノード（階層：ｎ）が一つ設けられる。
ここで、二分木におけるノードの値は、階層情報を含む整数値であってよい。例えば、最上位の数字を階層０，・・・，ｎとすると、リーフノードの値は、０１，０２，・・・となり、１階層上位のノードの値は、１１，１２，・・・となる。
【００１７】
制御部２０は、鍵共有部２１と、ポイントエンコーディング部２２と、レンジエンコーディング部２３と、ノード追加部２４と、暗号化部２５と、加法演算部２６と、乗法演算部２７と、ゼロ比較処理部２８と、出力部２９とを備える。
【００１８】
鍵共有部２１は、ｓｏｍｅｗｈａｔ準同型暗号に用いる秘密鍵を生成し、この秘密鍵に対応する公開鍵を端末Ａ及び端末Ｂで共有する。
【００１９】
ポイントエンコーディング部２２は、端末Ａにおいて、記憶部１０の二分木を参照し、第１の数値に対応するリーフノードからルートノードまでの経路上の全ノードからなる第１の集合を求める。
【００２０】
図２は、本実施形態に係るポイントエンコーディングを例示する図である。
この例では、計算対象の数値の取り得る範囲を［１〜８］とし、４階層の二分木により数値をエンコードする場合を示している。
例えば、「６」をエンコードする場合、リーフノード「０６」からルートノード「３１」までの経路上の全ノード、すなわち「０６，１３，２２，３１」がポイントエンコーディングの結果として出力される。
【００２１】
レンジエンコーディング部２３は、端末Ｂにおいて、記憶部１０の二分木を参照し、第２の数値以上の値に対応するリーフノードの範囲のみを、全てカバーする最少のノードからなる第２の集合を求める。
【００２２】
図３は、本実施形態に係るレンジエンコーディングを例示する図である。
この例では、計算対象の値の取り得る範囲を［１〜８］とし、４階層の二分木により値域（レンジ）をエンコードする場合を示している。
【００２３】
例えば、レンジ［４，８］をエンコードする場合、このレンジに対応するリーフノード０４〜０８のみを全てカバーするノードの集合、すなわち下位の階層へ展開したときに入力レンジと一致するノードの集合が１又は複数選択される。さらに、選択された集合のうち、最もノード数が少ない集合「０４，２２」がレンジエンコーディングの結果として出力される。
【００２４】
ここで、ノード１３及び１４も入力レンジの一部をカバーしているが、これらの上位階層にあるノード２２も入力レンジの一部をカバーしているため、ノード１３及び１４よりもノード２２が優先される。さらに、ノード２２の上位階層にあるノード３１は、入力レンジ外もカバーしているため除外され、この結果、ノード２２が集合の要素として決定される。
同様にノード０４の上位階層にあるノード１２は、レンジ外をカバーしているため、ノード０４が集合の要素として決定される。
【００２５】
レンジエンコーディングの結果は、各階層に最大一つのノードを含む。
また、レンジエンコーディングの結果は、親子関係にある複数のノードを同時に要素として含まない。したがって、数値ｘをポイントエンコーディングした結果と、レンジ［ｙ，２ｎ］をレンジエンコーディングした結果とは、ｘ≧ｙであれば一つのノードのみが一致し、ｘ＜ｙであればいずれのノードも一致しない。
【００２６】
ノード追加部２４は、端末Ｂにおいて、ポイントエンコーディングの結果である集合のノード数と、レンジエンコーディングの結果である集合のノード数とが等しくなるように、レンジエンコーディングの結果である集合に対して、二分木に存在するノードとは値が異なるダミーノードを追加する。これにより、ノード数によって一部の情報が漏れることが抑制される。
例えば、図３のレンジエンコーディングの結果である「０４，２２」に対して、階層：１のダミーノード１９と、階層：３のダミーノード３９とが追加される。ダミーノードは、二分木に存在しない値であるため、ポイントエンコーディングの結果とは一致しない。
【００２７】
暗号化部２５は、端末Ａ及び端末Ｂのそれぞれにおいて、ポイントエンコーディングの結果である第１の集合、及びダミーノードを追加した後のレンジエンコーディングの結果である第２の集合を、ノード毎にｓｏｍｅｗｈａｔ準同型暗号により暗号化する。
【００２８】
加法演算部２６は、端末Ｂにおいて、ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、第１の集合と第２の集合とを階層毎に減算した値の暗号化データの集合を生成する。
【００２９】
乗法演算部２７は、加法演算部２６による減算の結果を設定数ずつのグループに分割し、ｓｏｍｅｗｈａｔ準同型暗号の乗法準同型性を用いて、グループ毎に要素全てを乗算した値の暗号化データを生成する。
【００３０】
ゼロ比較処理部２８は、乗法演算部２７によるグループ毎の乗算の結果それぞれについて、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルにより、「０」及び「０以外」の暗号データを、「０」及び「１」の暗号データに変換する。
Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルは、例えば非特許文献３に記載され、端末Ｂが秘密鍵を持つ端末Ａと協働し、暗号化データを、「０」の暗号データ又は「１」の暗号データに変換することにより、平文が０か否かを判定するための処理である。
なお、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルは、通信量が多い処理であるため、グループの数（分割数）が多いほど、プロトコルの実行回数が増えて効率が低下する。
一方、グループの数（分割数）を少なくし、グループの要素数を多くすると、乗法準同型による乗算の回数が増えるため、ｓｏｍｅｗｈａｔ準同型暗号の乗算可能回数を増やすために処理負荷が増大する。
【００３１】
出力部２９は、ｓｏｍｅｗｈａｔ準同型暗号の加法準同型性を用いて、各グループのゼロ比較処理部２８による処理結果の値の総和とグループの数との差に基づく大小比較結果を出力する。
具体的には、前述のように、数値ｘをポイントエンコーディングした結果と、レンジ［ｙ，２ｎ］をレンジエンコーディングした結果とは、ｘ≧ｙであれば一つのノードのみが一致し、ｘ＜ｙであればいずれのノードも一致しないことから、ゼロ比較処理部２８の処理結果は、ｘ≧ｙのときに限り「０」の暗号データが一つだけ存在し、この他は「１」の暗号データとなる。
【００３２】
したがって、グループ数と、ゼロ比較処理部２８の処理結果の平文（０又は１）の総和との差は、ｘ≧ｙのときに限り「１」となり、ｘ＜ｙのときは「０」となり、この「１」又は「０」の暗号データが出力される。
あるいは、ゼロ比較処理部２８の処理結果の平文（０又は１）の総和と、「グループ数−１」との差は、ｘ≧ｙのときに限り「０」となり、ｘ＜ｙのときは「１」となり、この「０」又は「１」の暗号データが出力される。
【００３３】
本実施形態において、ｓｏｍｅｗｈａｔ準同型暗号は、例えばユーザによって、乗算可能回数が異なる複数の暗号方式から選択されてよい。このとき、乗法演算部２７は、乗算可能回数に基づいて、分割する際の設定数（グループの要素数）を決定する。
あるいは、ｓｏｍｅｗｈａｔ準同型暗号は、例えばユーザによって入力されたグループに分割する際の設定数（グループの要素数）に基づいて、乗算可能回数が異なる複数の暗号方式から選択されてもよい。
【００３４】
図４は、本実施形態に係る二値の大小比較の仕組みを説明する図である。
この例では、図２及び図３の二分木を用いて、二値の大小比較を行っている。
なお、図中のノード及び演算結果の数値は、平文で記述しているが、ｓｏｍｅｗｈａｔ準同型暗号により、暗号化されたまま演算される。
【００３５】
数値「６」に対するポイントエンコーディングの結果「０６，１３，２２，３１」と、「４」（レンジ［４，８］）に対するレンジエンコーディング及びダミーノードの追加の結果「０４，１９，２２，３９」とは、「６≧４」であることから、一つのノード「２２」のみが一致する。したがって、階層毎の両者の差は、一つの階層のみが「０」となる。
【００３６】
要素数が２の２つのグループに分割して乗算を行い、それぞれＥｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルを実行すると、一つのグループが「０」となり、他のグループが「１」となる。
そこで、これらの演算値の総和（０＋１）から「グループ数−１」（２−１）を減算すると「０」となり、二値の大小関係が「６≧４」であることを示す「０」の暗号データが出力される。
【００３７】
図５は、本実施形態に係る計算方法を例示するフローチャートである。
この計算方法を実行する端末Ａと端末Ｂとは、それぞれｘ，ｙ（≦２ｎ）の値を持ち、互いにｘ，ｙに関する情報を渡すことなくｘ，ｙの大小比較を実施する。
このとき、端末Ａ及び端末Ｂの共通パラメータとして、ｓｏｍｅｗｈａｔ準同型暗号の乗算可能回数ｌ、ビットサイズｎが入力される。
【００３８】
ステップＳ１において、端末Ａは、ｓｏｍｅｗｈａｔ準同型暗号の秘密鍵ｓｋを生成する。
ステップＳ２において、端末Ａは、秘密鍵ｓｋに対応する公開鍵ｐｋを生成し端末Ｂと共有する。
【００３９】
ステップＳ３において、端末Ａは、数値ｘに対してポイントエンコーディングｐｏｉｎｔＥｎｃ（ｘ）を実行する。
ステップＳ４において、端末Ｂは、数値ｙに対してレンジエンコーディングｒａｎｇｅＥｎｃ（［ｙ，２ｎ］）を実行する。
ステップＳ５において、端末Ｂは、ノードの数がｎとなるまでダミーノードを追加する。
【００４０】
ステップＳ６及びＳ７において、端末Ａと端末Ｂとは、それぞれパラメータとして入力された乗算可能回数のｓｏｍｅｗｈａｔ準同型暗号を用いて、エンコーディング結果の各ノードを暗号化する。
ステップＳ８において、端末Ａは、端末Ｂに暗号化したノードの集合を送信する。
【００４１】
ステップＳ９において、端末Ｂは、加法準同型性を利用して、各階層のノードに対応する暗号文同士を減算する。これらの暗号文をＥ（Ｒｉ）（ｉ＝１，・・・，ｎ）とすると、ｘ≧ｙを満たしている場合に限り、Ｒｊ＝０となるｊが存在する。
【００４２】
ステップＳ１０において、端末Ｂは、Ｅ（Ｒｉ）をｌ個ずつのグループに分割する。
ステップＳ１１において、端末Ｂは、乗法準同型性を利用してグループ毎に、Ｅ（Ｒ１×・・・×Ｒｌ）＝Ｅ（Ｑ１），Ｅ（Ｒｌ＋１×・・・×Ｒ２ｌ）＝Ｅ（Ｑ２），・・・，Ｅ（Ｒｎ−ｌ＋１×・・・×Ｒｎ）＝Ｅ（Ｑｎ／ｌ）を計算する。
【００４３】
ステップＳ１２において、端末Ｂは、端末Ａと協働し、∀Ｅ（Ｑｉ）に対してＥｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルを実行する。これにより、Ｅ（Ｑｉ）＝Ｅ（０）となる暗号文はＥ（Ｑ’ｉ）＝Ｅ（０）となり、これ以外はＥ（Ｑ’ｉ）＝Ｅ（１）となる。
ここで、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルは通信回数が多いため、処理を効率化するにはｌを大きくしてグループを少なくしたいが、一方で乗算可能回数が増えるにつれて、暗号化に関する計算（暗号化、復号、暗号化した状態での計算等）に掛かる時間が増大する。したがって、ｌを調整することで、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルの実行回数と乗算可能回数との調整が可能となる。
【００４４】
ステップＳ１３において、端末Ｂは、加法準同型性を利用して、Ｅ（Ｑ’１＋・・・＋Ｑ’ｎ／ｌ−（ｎ／ｌ−１））を計算し、二値の比較結果として出力する。このとき、ｘ≧ｙを満たしている場合に限りＥ（０）、それ以外はＥ（１）となる。
【００４５】
なお、以上の計算方法の例では、端末Ａ（第１の端末）がポイントエンコーディングを、端末Ｂ（第２の端末）がレンジエンコーディングを行うこととしたが、これには限られず、端末Ｂがポイントエンコーディングを、端末Ａがレンジエンコーディングを行ってもよい。
【００４６】
本実施形態では、初期状態として、端末Ａ及び端末Ｂがそれぞれ数値ｘ，ｙ（平文）を持っていることとしているが、これには限られず、例えば以下の（１）又は（２）のような変換が公知の技術により実現できる。したがって、これらの入力のバリエーションは、二値比較が用いられる場面に応じて適宜選択される。
【００４７】
（１）端末Ａがｓｏｍｅｗｈａｔ準同型暗号の秘密鍵を持ち、端末ＢがＥ（ｘ）及びＥ（ｙ）を持つ。
非特許文献２に記載された技術を用いることにより、端末ＢがＥ（ｘ）及びＥ（ｙ）を暗号文として持つ初期状態から、端末Ａ及び端末Ｂがそれぞれ平文を持つ状態へと変換できる。
【００４８】
（２）端末Ａが数値ｘ，ｙのｓｈａｒｅ  ｘＡ及びｙＡを、端末Ｂがｘ，ｙのｓｈａｒｅ  ｘＢ及びｙＢを持つ。
この場合、端末Ｂが持つｓｈａｒｅを一度暗号化して端末Ａに送り、端末Ａは、Ｅ（ｘ）＝Ｅ（ｘＡ＋ｘＢ）及びＥ（ｙ）＝Ｅ（ｙＡ＋ｙＢ）を端末Ｂに送り返す。これにより、端末Ｂがｘ，ｙの暗号文を持つ状態となるため、（１）の手法を用いて変換できる。
【００４９】
また、大小比較結果の出力に関しても同様に、端末Ｂが暗号文として持つ、端末Ａ及び端末Ｂがｓｈａｒｅとして持つ、端末Ａが平文として持つといった変換が可能である。
【００５０】
本実施形態によれば、計算システム１は、設定された要素数のグループを作成し、グループ毎に乗法準同型演算とＥｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルとを実行することにより、秘密計算による二値の大小比較を行う。したがって、二値比較の秘密計算において、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルの実行回数に応じた通信量と、乗算可能回数に応じた計算量との調節が可能となる。
【００５１】
このとき、グループは、ｓｏｍｅｗｈａｔ準同型暗号の乗算可能回数に応じた要素数に分割され、又は要素数に応じた暗号方式が選択されるので、Ｅｑｕａｌ−ｔｏ−Ｚｅｒｏプロトコルの実行回数、又は乗算可能回数に基づいて、適度な通信量及び計算量に容易に調節が可能である。
【００５２】
また、計算に用いられるノードの値そのものに二分木の階層情報が含まれることにより、データの保持、及び階層毎の演算が容易となる。
【００５３】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００５４】
計算システム１による計算方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００５５】
１  計算システム
１０  記憶部
２０  制御部
２１  鍵共有部
２２  ポイントエンコーディング部
２３  レンジエンコーディング部
２４  ノード追加部
２５  暗号化部
２６  加法演算部
２７  乗法演算部
２８  ゼロ比較処理部
２９  出力部
【図１】
2019040047.tif 000003
【図２】
2019040047.tif 000004
【図３】
2019040047.tif 000005
【図４】
2019040047.tif 000006
【図５】
2019040047.tif 000007