(57)【要約】【課題】２変数関数の秘匿計算を汎用的に、かつ、高速に行える秘匿計算装置、秘匿計算方法及び秘匿計算プログラムを提供すること。【解決手段】秘匿計算装置１は、２変数関数の第２変数を定数としたときの、第１変数に応じた関数値を多項式補間により定義した第１多項式の係数を記憶する記憶部２０と、第１暗号文及び第２暗号文の入力を受け付ける入力部１１と、第１暗号文の冪乗を計算する秘匿冪乗演算部１２と、第２変数を定数のいずれかに固定し、第１多項式の係数と第１暗号文の冪乗との内積により、第１多項式の値を算出する秘匿関数演算部１３と、第２暗号文の暗号化前の平文と定数とが異なる場合に０となる判定値を暗号文で算出する秘匿等号演算部１４と、第２変数が取り得る一部の定数毎の秘匿関数演算部１３による算出結果、及び秘匿等号演算部１４による算出結果の積を総和して２変数関数の値を出力する出力部１５と、を備える。【選択図】図１
2020160353.tif 000002
【特許請求の範囲】
【請求項１】
平文の空間内で、第１変数及び第２変数を入力とする２変数関数における前記第２変数を前記空間内の定数に固定したときの、前記第１変数に応じた関数値を多項式補間により定義した第１多項式の係数を、前記定数それぞれについて記憶する第１記憶部と、
前記第１変数の値及び前記第２変数の値をそれぞれ準同型暗号方式により暗号化した、第１暗号文及び第２暗号文の入力を受け付ける入力部と、
前記準同型暗号方式による暗号文の空間内で、前記第１暗号文の冪乗を計算する秘匿冪乗演算部と、
前記第２変数を前記定数のいずれかに固定し、前記第１多項式の係数と前記第１暗号文の冪乗との内積により、前記第１多項式の値を算出する秘匿関数演算部と、
前記第２暗号文の暗号化前の平文と前記定数とが異なる場合に０となる判定値を暗号文で算出する秘匿等号演算部と、
前記第２変数が取り得る前記空間内の一部の定数毎の前記秘匿関数演算部による算出結果、及び前記秘匿等号演算部による算出結果の積を総和することにより、前記第１暗号文及び前記第２暗号文を入力とした前記２変数関数の値を出力する出力部と、を備える秘匿計算装置。
【請求項２】
前記第１記憶部は、前記一部の定数についてのみ、前記第１多項式の係数を記憶する請求項１に記載の秘匿計算装置。
【請求項３】
前記第２変数が前記定数と等しい場合に１となり、異なる場合に０となる関数を多項式補間により定義した第２多項式の係数を、前記定数それぞれについて記憶する第２記憶部を備え、
前記秘匿冪乗演算部は、前記第２暗号文の冪乗をさらに計算し、
秘匿等号演算部は、前記第２多項式の係数と前記第２暗号文の冪乗との内積により、前記第２多項式の値を、前記判定値の暗号文として算出する請求項１又は請求項２に記載の秘匿計算装置。
【請求項４】
前記第２記憶部は、前記一部の定数についてのみ、前記第２多項式の係数を記憶する請求項３に記載の秘匿計算装置。
【請求項５】
前記第２記憶部は、前記第２変数が取り得る値の空間に応じた次数で前記第２多項式を定義し、
前記秘匿冪乗演算部は、前記第２暗号文の冪乗を、前記第１暗号文の冪乗よりも低い前記次数まで計算する請求項４に記載の秘匿計算装置。
【請求項６】
前記２変数関数は、前記第１変数を被除数、前記第２変数を除数とする除算である請求項１又は請求項２に記載の秘匿計算装置。
【請求項７】
平文の空間内で、第１変数及び第２変数を入力とする２変数関数における前記第２変数を前記空間内の定数に固定したときの、前記第１変数に応じた関数値を多項式補間により定義した第１多項式の係数を、前記定数それぞれについて記憶する第１記憶ステップと、
前記第１変数の値及び前記第２変数の値をそれぞれ準同型暗号方式により暗号化した、第１暗号文及び第２暗号文の入力を受け付ける入力ステップと、
前記準同型暗号方式による暗号文の空間内で、前記第１暗号文の冪乗を計算する秘匿冪乗演算ステップと、
前記第２変数を前記定数のいずれかに固定し、前記第１多項式の係数と前記第１暗号文の冪乗との内積により、前記第１多項式の値を算出する秘匿関数演算ステップと、
前記第２暗号文の暗号化前の平文と前記定数とが異なる場合に０となる判定値を暗号文で算出する秘匿等号演算ステップと、
前記第２変数が取り得る前記空間内の一部の定数毎の前記秘匿関数演算ステップにおける算出結果、及び前記秘匿等号演算ステップにおける算出結果の積を総和することにより、前記第１暗号文及び前記第２暗号文を入力とした前記２変数関数の値を出力する出力ステップと、をコンピュータが実行する秘匿計算方法。
【請求項８】
請求項１から請求項６のいずれかに記載の秘匿計算装置としてコンピュータを機能させるための秘匿計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２変数関数の秘匿計算装置、秘匿計算方法及び秘匿計算プログラムに関する。
【背景技術】
【０００２】
従来、暗号化したまま平文の計算を行う秘密計算の手法が提案されている。
例えば、非特許文献１〜３では、入力の整数がビット値に変換された状態、つまり平文がビット値の場合（以下、ｂｉｔ−ｗｉｓｅと表現する）に、完全準同型暗号方式による暗号文上での四則演算アルゴリズム（秘匿加算、秘匿減算、秘匿乗算、秘匿除算）が提案されている。
また、非特許文献４では、入力の整数がビット値に変換されず、つまり平文が整数値の場合（以下、ｉｎｔｅｇｅｒ−ｗｉｓｅと表現する）に、完全準同型暗号方式による暗号文上での２値比較演算のアルゴリズムが提案されている。
さらに、非特許文献５では、加法準同型暗号を用いた二者間プロトコルでの秘匿除算方法が提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｙａｏ  Ｃｈｅｎ  ａｎｄ  Ｇｕａｎｇ  Ｇｏｎｇ．  Ｉｎｔｅｇｅｒ  ａｒｉｔｈｍｅｔｉｃ  ｏｖｅｒ  ｃｉｐｈｅｒｔｅｘｔ  ａｎｄ  ｈｏｍｏｍｏｒｐｈｉｃ  ｄａｔａ  ａｇｇｒｅｇａｔｉｏｎ．  Ｉｎ  ２０１５  ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｎｅｔｗｏｒｋ  Ｓｅｃｕｒｉｔｙ  （ＣＮＳ），  ｐａｇｅｓ  ６２８−６３２，  Ｓｅｐｔ  ２０１５．
【非特許文献２】Ｃｈｅｎ  Ｘｕ，  Ｊｉｎｇｗｅｉ  Ｃｈｅｎ，  Ｗｅｎｙｕａｎ  Ｗｕ，  ａｎｄ  Ｙｏｎｇ  Ｆｅｎｇ．  Ｈｏｍｏｍｏｒｐｈｉｃａｌｌｙ  ｅｎｃｒｙｐｔｅｄ  ａｒｉｔｈｍｅｔｉｃ  ｏｐｅｒａｔｉｏｎｓ  ｏｖｅｒ  ｔｈｅ  ｉｎｔｅｇｅｒ  ｒｉｎｇ．  Ｉｎ  Ｆｅｎｇ  Ｂａｏ，  Ｌｉｑｕｎ  Ｃｈｅｎ，  Ｒｏｂｅｒｔ  Ｈ．  Ｄｅｎｇ，  ａｎｄ  Ｇｕｏｊｕｎ  Ｗａｎｇ，  ｅｄｉｔｏｒｓ，  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒａｃｔｉｃｅ  ａｎｄ  Ｅｘｐｅｒｉｅｎｃｅ，  ｐａｇｅｓ  １６７−１８１，  Ｓｐｒｉｎｇｅｒ，  ２０１６．
【非特許文献３】Ｊｉｎｇｗｅｉ  Ｃｈｅｎ，  Ｙｏｎｇ  Ｆｅｎｇ，  Ｙａｎｇ  Ｌｉｕ，  ａｎｄ  Ｗｅｎｙｕａｎ  Ｗｕ．  Ｆａｓｔｅｒ  ｂｉｎａｒｙ  ａｒｉｔｈｍｅｔｉｃ  ｏｐｅｒａｔｉｏｎｓ  ｏｎ  ｅｎｃｒｙｐｔｅｄ  ｉｎｔｅｇｅｒｓ．  Ｉｎ  ｔｈｅ  ７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｅｎｇｉｎｅｅｒｉｎｇ，  ２０１７．
【非特許文献４】Ｈ．  Ｎａｒｕｍａｎｃｈｉ，  Ｄ．  Ｇｏｙａｌ，  Ｎ．  Ｅｍｍａｄｉ，  ａｎｄ  Ｐ．  Ｇａｕｒａｖａｒａｍ．  Ｐｅｒｆｏｒｍａｎｃｅ  ａｎａｌｙｓｉｓ  ｏｆ  ｓｏｒｔｉｎｇ  ｏｆ  ｔｈｅ  ｄａｔａ：  Ｉｎｔｅｇｅｒ−ｗｉｓｅ  ｃｏｍｐａｒｉｓｏｎ  ｖｓ  ｂｉｔ−ｗｉｓｅ  ｃｏｍｐａｒｉｓｏｎ．  Ｉｎ  ２０１７  ＩＥＥＥ  ３１ｓｔ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｄｖａｎｃｅｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｎｅｔｗｏｒｋｉｎｇ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  （ＡＩＮＡ），  ｐａｇｅｓ  ９０２−９０８，  Ｍａｒｃｈ  ２０１７．
【非特許文献５】Ｍｏｒｔｅｎ  Ｄａｈｌ，  Ｃｈａｏ  Ｎｉｎｇ，  ａｎｄ  Ｔｏｍａｓ  Ｔｏｆｔ．  Ｏｎ  ｓｅｃｕｒｅ  ｔｗｏ−ｐａｒｔｙ  ｉｎｔｅｇｅｒ  ｄｉｖｉｓｉｏｎ．  Ｉｎ  Ａｎｇｅｌｏｓ  Ｄ．  Ｋｅｒｏｍｙｔｉｓ，  ｅｄｉｔｏｒ，  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｄａｔａ  Ｓｅｃｕｒｉｔｙ，  ｐａｇｅｓ  １６４−１７８．  Ｓｐｒｉｎｇｅｒ，  ２０１２．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、ｉｎｔｅｇｅｒ−ｗｉｓｅの秘匿計算は、入力の整数を２進数のビット毎に暗号化する必要がないため、暗号化の回数がｂｉｔ−ｗｉｓｅに比べて少なく有利となる。また、例えばｂｉｔ−ｗｉｓｅの加減算は、２進数演算における繰り上げの処理等、完全準同型暗号において処理速度のネックとなる乗算を用いた処理が必要になる。一方、ｉｎｔｅｇｅｒ−ｗｉｓｅの加減算では、乗算を用いることなく暗号文同士を足し合わせることができるため高速である。
このように、ｉｎｔｅｇｅｒ−ｗｉｓｅでの秘匿計算が望まれる一方で、次のような課題が存在する。
【０００５】
例えば、非特許文献４において、ｉｎｔｅｇｅｒ−ｗｉｓｅの２値比較演算のアルゴリズムが提案されているが、計算量及び乗算回路の深さのために、ｂｉｔ−ｗｉｓｅでの演算に比べて低速である。また、除算は、２値比較演算をサブモジュールとし、２値比較と減算とを繰り返すことで実現可能だが、２値比較を繰り返すことで、さらに低速となっていた。
また、前述の非特許文献５の秘匿除算方法では、割られる数がｌ−ｂｉｔの整数であるのに対し、割る数がｌｏｇ  ｌ−ｂｉｔの整数であるという制限を加えることで高速化を図っているが、割る数がｌ−１以下の整数に限られてしまい、汎用性に欠けていた。
このように、完全準同型暗号でのｉｎｔｅｇｅｒ−ｗｉｓｅの高速な除算アルゴリズム、さらには、任意の２変数関数に適用できるｉｎｔｅｇｅｒ−ｗｉｓｅの高速な秘匿計算アルゴリズムは提案されていなかった。
【０００６】
本発明は、２変数関数の秘匿計算を汎用的に、かつ、高速に行える秘匿計算装置、秘匿計算方法及び秘匿計算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る秘匿計算装置は、平文の空間内で、第１変数及び第２変数を入力とする２変数関数における前記第２変数を前記空間内の定数に固定したときの、前記第１変数に応じた関数値を多項式補間により定義した第１多項式の係数を、前記定数それぞれについて記憶する第１記憶部と、前記第１変数の値及び前記第２変数の値をそれぞれ準同型暗号方式により暗号化した、第１暗号文及び第２暗号文の入力を受け付ける入力部と、前記準同型暗号方式による暗号文の空間内で、前記第１暗号文の冪乗を計算する秘匿冪乗演算部と、前記第２変数を前記定数のいずれかに固定し、前記第１多項式の係数と前記第１暗号文の冪乗との内積により、前記第１多項式の値を算出する秘匿関数演算部と、前記第２暗号文の暗号化前の平文と前記定数とが異なる場合に０となる判定値を暗号文で算出する秘匿等号演算部と、前記第２変数が取り得る前記空間内の一部の定数毎の前記秘匿関数演算部による算出結果、及び前記秘匿等号演算部による算出結果の積を総和することにより、前記第１暗号文及び前記第２暗号文を入力とした前記２変数関数の値を出力する出力部と、を備える。
【０００８】
前記第１記憶部は、前記一部の定数についてのみ、前記第１多項式の係数を記憶してもよい。
【０００９】
前記秘匿計算装置は、前記第２変数が前記定数と等しい場合に１となり、異なる場合に０となる関数を多項式補間により定義した第２多項式の係数を、前記定数それぞれについて記憶する第２記憶部を備え、前記秘匿冪乗演算部は、前記第２暗号文の冪乗をさらに計算し、秘匿等号演算部は、前記第２多項式の係数と前記第２暗号文の冪乗との内積により、前記第２多項式の値を、前記判定値の暗号文として算出してもよい。
【００１０】
前記第２記憶部は、前記一部の定数についてのみ、前記第２多項式の係数を記憶してもよい。
【００１１】
前記第２記憶部は、前記第２変数が取り得る値の空間に応じた次数で前記第２多項式を定義し、前記秘匿冪乗演算部は、前記第２暗号文の冪乗を、前記第１暗号文の冪乗よりも低い前記次数まで計算してもよい。
【００１２】
前記２変数関数は、前記第１変数を被除数、前記第２変数を除数とする除算であってもよい。
【００１３】
本発明に係る秘匿計算方法は、平文の空間内で、第１変数及び第２変数を入力とする２変数関数における前記第２変数を前記空間内の定数に固定したときの、前記第１変数に応じた関数値を多項式補間により定義した第１多項式の係数を、前記定数それぞれについて記憶する第１記憶ステップと、前記第１変数の値及び前記第２変数の値をそれぞれ準同型暗号方式により暗号化した、第１暗号文及び第２暗号文の入力を受け付ける入力ステップと、前記準同型暗号方式による暗号文の空間内で、前記第１暗号文の冪乗を計算する秘匿冪乗演算ステップと、前記第２変数を前記定数のいずれかに固定し、前記第１多項式の係数と前記第１暗号文の冪乗との内積により、前記第１多項式の値を算出する秘匿関数演算ステップと、前記第２暗号文の暗号化前の平文と前記定数とが異なる場合に０となる判定値を暗号文で算出する秘匿等号演算ステップと、前記第２変数が取り得る前記空間内の一部の定数毎の前記秘匿関数演算ステップにおける算出結果、及び前記秘匿等号演算ステップにおける算出結果の積を総和することにより、前記第１暗号文及び前記第２暗号文を入力とした前記２変数関数の値を出力する出力ステップと、をコンピュータが実行する。
【００１４】
本発明に係る秘匿計算プログラムは、前記秘匿計算装置としてコンピュータを機能させるためのものである。
【発明の効果】
【００１５】
本発明によれば、２変数関数の秘匿計算を汎用的に、かつ、高速に行える。
【図面の簡単な説明】
【００１６】
【図１】実施形態に係る秘匿計算装置の機能構成を示すブロック図である。
【図２】実施形態に係る秘匿冪乗演算のアルゴリズムを例示するフローチャートである。
【図３】実施形態に係る秘匿定数等号演算を実行する前の事前計算アルゴリズムを例示するフローチャートである。
【図４】実施形態に係る秘匿定数等号演算のアルゴリズムを例示するフローチャートである。
【図５】実施形態に係る秘匿定数関数演算を実行する前の事前計算アルゴリズムを例示するフローチャートである。
【図６】実施形態に係る秘匿定数関数演算のアルゴリズムを例示するフローチャートである。
【図７】実施形態に係る秘匿２変数関数演算のアルゴリズムを示す図である。
【図８】実施形態に係る秘匿２変数関数演算を秘匿除算演算に適用した場合の実行速度を、制限の有無で比較した実験結果を示す図である。
【図９】実施形態に係る部分集合による制限を設けない場合の、準同型乗算の深さと準同型演算の呼び出し回数とを示す図である。
【図１０】実施形態に係る部分集合による制限を設けた場合の、準同型乗算の深さと準同型演算の呼び出し回数とを示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係る秘匿計算装置１の機能構成を示すブロック図である。
秘匿計算装置１は、サーバ装置又はパーソナルコンピュータ等の情報処理装置（コンピュータ）であり、制御部１０及び記憶部２０の他、各種データの入出力デバイス及び通信デバイス等を備える。
【００１８】
制御部１０は、秘匿計算装置１の全体を制御する部分であり、記憶部２０に記憶された各種プログラムを適宜読み出して実行することにより、本実施形態における各機能を実現する。制御部１０は、ＣＰＵであってよい。
【００１９】
記憶部２０は、ハードウェア群を秘匿計算装置１として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ＲＯＭ、ＲＡＭ、フラッシュメモリ又はハードディスク（ＨＤＤ）等であってよい。具体的には、記憶部２０は、本実施形態の各機能を制御部１０に実行させるためのプログラム（秘匿計算プログラム）及び実行途中のデータを記憶する。
【００２０】
さらに、記憶部２０は、素数ｐを法とする平文の空間Ｚｐ内で、第１変数及び第２変数を入力とする２変数関数ｇにおける第２変数を定数に固定したときの、第１変数に応じた関数値を多項式補間により定義した第１多項式の係数ベクトルを、定数それぞれについて記憶する。
本実施形態では、第２変数（例えば、除算における割る数）の空間は、Ｚｐの部分集合に限定される。したがって、この部分集合が予め固定されている場合には、定数毎の第１多項式の係数ベクトルは、Ｚｐ内の一部の定数についてのみ記憶されてもよい。なお、計算の度に部分集合が変更される場合には、係数ベクトルは、Ｚｐ内の全ての定数について記憶される。
【００２１】
また、記憶部２０は、平文の空間Ｚｐ内で、ある変数が定数と等しい場合に１となり、異なる場合に０となる関数を多項式補間により定義した第２多項式の係数ベクトルを、定数それぞれについて記憶する。
本実施形態では、この関数の入力となる第２変数の空間は、Ｚｐの部分集合に限定される。したがって、この部分集合が予め固定されている場合には、定数毎の第２多項式の係数ベクトルは、Ｚｐ内の一部の定数についてのみ記憶されてもよく、さらに、第２多項式は、第１多項式に比べて、部分集合の大きさに応じた次数に低減されてもよい。なお、計算の度に部分集合が変更される場合には、係数ベクトルは、Ｚｐ内の全ての定数について記憶され、第２多項式の次数は、第１多項式の次数と同じくｐ−１となる。
【００２２】
制御部１０は、入力部１１と、秘匿冪乗演算部１２と、秘匿関数演算部１３と、秘匿等号演算部１４と、出力部１５とを備える。
【００２３】
入力部１１は、２変数関数ｇにおける第１変数の値ａ及び第２変数の値ｂをそれぞれ準同型暗号方式により暗号化した、第１暗号文Ｃａ及び第２暗号文Ｃｂの入力を受け付ける。
【００２４】
秘匿冪乗演算部１２は、準同型暗号方式による暗号文の空間内で、第１暗号文Ｃａの冪乗列ベクトル（Ｃａ，Ｃａ２，Ｃａ３，・・・，Ｃａｐ−１）、及び第２暗号文Ｃｂの冪乗列ベクトル（Ｃｂ，Ｃｂ２，Ｃｂ３，・・・，Ｃｂ｜Ｓ｜−１）を計算する。なお、｜Ｓ｜は、第２変数の取り得る値からなる集合Ｓの大きさであり、｜Ｓ｜＜ｐとする。
【００２５】
秘匿関数演算部１３は、第２変数を定数のいずれかに固定し、記憶部２０に予め記憶された第１多項式の係数ベクトルと、第１暗号文Ｃａの冪乗を並べたベクトルとの内積により、第１多項式の値を算出する。
【００２６】
秘匿等号演算部１４は、第２暗号文Ｃｂの暗号化前の平文ｂと定数とが異なる場合に０となる判定値を暗号文で算出する。
具体的には、秘匿等号演算部１４は、記憶部２０に予め記憶された第２多項式の係数ベクトルと、第２暗号文Ｃｂの冪乗を並べたベクトルとの内積により、第２多項式の値を、判定値の暗号文として算出する。
【００２７】
出力部１５は、Ｚｐの部分空間である第２変数が取り得る値の集合Ｓに含まれる定数毎の、秘匿関数演算部１３による算出結果、及び秘匿等号演算部１４による算出結果の積を総和することにより、第１暗号Ｃａ文及び第２暗号文Ｃｂを入力とした２変数関数の値ｇ（Ｃａ，Ｃｂ）を出力する。
【００２８】
以下、任意の２変数関数に適用できる、ｉｎｔｅｇｅｒ−ｗｉｓｅの秘匿計算方法の手順を詳述する。
ここで、ｐを素数、平文の空間をＺｐ、暗号文の空間を多項式環Ｒｐとする。また、平文ａ，ｂ∈Ｚｐを完全準同型暗号方式により暗号化した暗号文をＣａ，Ｃｂとする。
【００２９】
図２は、本実施形態に係る秘匿２変数関数演算アルゴリズムを構成するサブモジュールの１つである秘匿冪乗演算Ｐｏｗｓ（Ｃａ，ｐ）のアルゴリズムを例示するフローチャートである。
【００３０】
秘匿冪乗演算Ｐｏｗｓ（Ｃａ，ｐ）は、秘匿冪乗演算部１２により実行され、第１変数ａの暗号文Ｃａ、及び平文の空間の大きさ（法）ｐを引数とし、Ｃａ及びＣｂそれぞれの冪乗を、暗号文同士の乗算を用いて計算し、冪乗列ベクトルＣａｐｏｗ：＝（Ｃａ，Ｃａ２，Ｃａ３，・・・，Ｃａｐ−１）及びＣｂｐｏｗ：＝（Ｃａ，Ｃａ２，Ｃａ３，・・・，Ｃａｌ−１）を返す。
【００３１】
ステップＳ１において、秘匿冪乗演算部１２は、ｌｏｇ  ｐを超えない最大の整数ｌを算出する。
ステップＳ２において、秘匿冪乗演算部１２は、インデックスｉを０からｌ−１までインクリメントしながら、ループ処理を行う。
ステップＳ３において、秘匿冪乗演算部１２は、インデックスｊを１から２ｉまでインクリメントしながら、ループ処理を行う。
【００３２】
ステップＳ４において、秘匿冪乗演算部１２は、暗号文Ｃａの（２ｉ＋ｊ）乗を、Ｃａの２ｉ乗とＣａのｊ乗との準同型乗算（ＦＨＥ．Ｍｕｌｔ）により算出する。
この処理が繰り返されることにより、Ｃａの２乗から２ｌ乗までが算出される。
【００３３】
ステップＳ５において、秘匿冪乗演算部１２は、２ｌがｐ−１より小さいか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ６に移り、判定がＮＯの場合、処理はステップＳ８に移る。
【００３４】
ステップＳ６において、秘匿冪乗演算部１２は、インデックスｊを１からｐ−１−２ｌまでインクリメントしながら、ループ処理を行う。
ステップＳ７において、秘匿冪乗演算部１２は、暗号文Ｃａの（２ｌ＋ｊ）乗を、Ｃａの２ｌ乗とＣａのｊ乗との準同型乗算（ＦＨＥ．Ｍｕｌｔ）により算出する。
この処理が繰り返されることにより、Ｃａの（２ｌ＋１）乗から（ｐ−１）乗までが算出される。
【００３５】
ステップＳ８において、秘匿冪乗演算部１２は、暗号文暗号文Ｃａの冪乗列ベクトル（Ｃａ，Ｃａ２，Ｃａ３，・・・，Ｃａｐ−１）を出力する。
【００３６】
本アルゴリズムにおいて、乗算の深さはＯ（ｌｏｇ（ｐ））に抑えられる。例えば、ｐ＝１７の場合、Ｃａ２＝Ｃａ×Ｃａ，Ｃａ４＝Ｃａ２×Ｃａ２，Ｃａ８＝Ｃａ４×Ｃａ４，Ｃａ１６＝Ｃａ８×Ｃａ８のように計算でき、乗算の深さは、ｌｏｇ（１６）＝４である。
【００３７】
図３は、本実施形態に係る秘匿２変数関数演算アルゴリズムを構成するサブモジュールの１つである秘匿定数等号演算ＣｏｎｓｔＥｑ（Ｃａｐｏｗ，ｙ）を実行する前の事前計算アルゴリズムを例示するフローチャートである。
【００３８】
ステップＳ１１において、秘匿等号演算部１４は、定数ｙとの等号演算の１変数関数ｇｙ（ｘ）＝１（ｘ＝ｙのとき），０（ｘ≠ｙのとき）を定義し、全てのｘ，ｙ∈Ｚｐについて、データ点ｇｙ（ｘ）を取得する。
【００３９】
ステップＳ１２において、秘匿等号演算部１４は、インデックスｉを０からｐ−１までインクリメントしながら、ループ処理を行う。
ステップＳ１３において、秘匿等号演算部１４は、多項式補間により、全てのｘ∈Ｚｐに対してｆｉ（ｘ）＝ｇｉ（ｘ）を満たす多項式ｆｉ（ｘ）：Ｚｐ→Ｚｐの係数ベクトルａｆｉＣｏｎｓｔＥｑを求める。
この処理が繰り返されることにより、全てのｙ∈Ｚｐに対して、多項式ｆｙ（ｘ）の係数ベクトルａｆｙＣｏｎｓｔＥｑが求まる。
【００４０】
ステップＳ１４において、秘匿等号演算部１４は、全てのｙ∈Ｚｐに対する係数ベクトルａｆｙＣｏｎｓｔＥｑを、定数行列として記憶部２０（第２記憶部）に保存する。
【００４１】
本アルゴリズムにおいて、仮に、ｐ＝１７、第２引数の候補集合Ｓ＝｛２，３，５｝の場合、例えばｙ＝２∈Ｓについて、秘匿等号演算部１４は、データ点群（２，１），（３，０），（５，０）を取得し、多項式補間により、（ｌｏｇ  ｐ）−１＝３次の多項式ｆｙ（ｘ）を求める。秘匿等号演算部１４は、ｙ＝３，５∈Ｓについても同様に多項式補間を行い、それぞれの係数ベクトルを保存する。
【００４２】
図４は、本実施形態に係る秘匿２変数関数演算アルゴリズムを構成するサブモジュールの１つである秘匿定数等号演算ＣｏｎｓｔＥｑ（Ｃａｐｏｗ，ｙ）のアルゴリズムを例示するフローチャートである。
【００４３】
秘匿定数等号演算ＣｏｎｓｔＥｑ（Ｃａｐｏｗ，ｙ）は、秘匿等号演算部１４により実行され、第１変数ａの暗号文Ｃａの冪乗列ベクトルＣａｐｏｗ、及び定数の平文ｙを引数とし、条件式（ａ＝ｙ）の値（例えば、ＴＲＵＥ＝１、ＦＡＬＳＥ＝０）の暗号文であるＣ（ａ＝ｙ）を返す。
【００４４】
ステップＳ２１において、秘匿等号演算部１４は、引数である定数ｙに対応する係数ベクトルａｆｙＣｏｎｓｔＥｑを、事前計算により保存されている定数行列から取得する。
【００４５】
ステップＳ２２において、秘匿等号演算部１４は、条件式（ａ＝ｙ）の暗号文Ｃ（ａ＝ｙ）を、次のように、係数ベクトルと暗号文ａの冪乗列ベクトルとの内積により計算し出力する。
Ｃ（ａ＝ｙ）＝ｆｙ（Ｃａ）
＝（ａｆｙＣｏｎｓｔＥｑ）Ｔ・Ｃａｐｏｗ  ｍｏｄ  ｐ
【００４６】
図５は、本実施形態に係る秘匿２変数関数演算アルゴリズムを構成するサブモジュールである秘匿定数関数演算ＣｏｎｓｔＦｕｎｃ（Ｃａｐｏｗ，ｙ）を実行する前の事前計算アルゴリズムを例示するフローチャートである。
【００４７】
ステップＳ３１において、秘匿関数演算部１３は、予め定められた２変数関数ｇ（ｘ，ｙ）：Ｚｐ×Ｚｐ→Ｚｐに対して、ｙを定数とした１変数関数ｇｙ（ｘ）＝ｇ（ｘ，ｙ）を定義し、全てのｘ，ｙ∈Ｚｐについて、データ点ｇｙ（ｘ）を取得する。
【００４８】
ステップＳ３２において、秘匿関数演算部１３は、インデックスｉを０からｐ−１までインクリメントしながら、ループ処理を行う。
ステップＳ３３において、秘匿関数演算部１３は、多項式補間により、全てのｘ∈Ｚｐに対してｆｉ（ｘ）＝ｇｉ（ｘ）を満たす多項式ｆｉ（ｘ）：Ｚｐ→Ｚｐの係数ベクトルａｆｉＣｏｎｓｔＦｕｎｃを求める。
この処理が繰り返されることにより、全てのｙ∈Ｚｐに対して、多項式ｆｙ（ｘ）の係数ベクトルａｆｙＣｏｎｓｔＦｕｎｃが求まる。
【００４９】
ステップＳ３４において、秘匿関数演算部１３は、全てのｙ∈Ｚｐに対する係数ベクトルａｆｙＣｏｎｓｔＦｕｎｃを、定数行列として記憶部２０（第１記憶部）に保存する。
【００５０】
本アルゴリズムにおいて、ｆｙ（０）＝ｇ（０，ｙ），ｆｙ（１）＝ｇ（１，ｙ），・・・，ｆｙ（ｐ−１）＝ｇ（ｐ−１，ｙ）が与えられると、ｆｙ（ｘ）が多項式補間により、「ｆｙ（ｘ）＝ａ｛１，ｙ｝・ｘ＋ａ｛２，ｙ｝・ｘ２＋・・・＋ａ｛ｐ−１，ｙ｝・ｘｐ−１  ｍｏｄ  ｐ」と求められる。これにより、係数ベクトル（ａ｛１，ｙ｝，ａ｛２，ｙ｝，・・・，ａ｛ｐ−１，ｙ｝）がｙ（０≦ｙ＜ｐ）と対応付けて記憶される。
仮に、ｐ＝１７、第２引数の候補集合Ｓ＝｛２，３，５｝の場合、例えばｙ＝２∈Ｓについて、秘匿等号演算部１４は、｛０，１，・・・，１６｝割る２のデータ点群（０，０），（１，０），（２，１），・・・，（１６，８）を取得し、多項式補間により、ｐ−１＝１６次の多項式ｆｙ（ｘ）を求める。秘匿等号演算部１４は、ｙ＝３，５∈Ｓについても同様に多項式補間を行い、それぞれの係数ベクトルを保存する。
【００５１】
図６は、本実施形態に係る秘匿２変数関数演算アルゴリズムを構成するサブモジュールである秘匿定数関数演算ＣｏｎｓｔＦｕｎｃ（Ｃａｐｏｗ，ｙ）のアルゴリズムを例示するフローチャートである。
【００５２】
秘匿定数関数演算ＣｏｎｓｔＦｕｎｃ（Ｃａｐｏｗ，ｙ）は、秘匿関数演算部１３により実行され、第１変数ａの暗号文Ｃａの冪乗列ベクトルＣａｐｏｗ、及び定数の平文ｙを引数とし、２変数関数の第２変数をｙに固定した１変数関数ｇ（ａ，ｙ）の暗号文であるＣ（ａ，ｙ）＝ｇ（Ｃａ，ｙ）を返す。
【００５３】
ステップＳ４１において、秘匿関数演算部１３は、引数である定数ｙに対応する係数ベクトルａｆｙＣｏｎｓｔＦｕｎｃを、事前計算により保存されている定数行列から取得する。
【００５４】
ステップＳ４２において、秘匿関数演算部１３は、ｇ（ａ，ｙ）の暗号文Ｃｇ（ａ，ｙ）を、次のように、係数ベクトルと暗号文ａの冪乗列ベクトルとの内積により計算し出力する。
Ｃｇ（ａ，ｙ）＝ｆｙ（Ｃａ）
＝（ａｆｙＣｏｎｓｔＦｕｎｃ）Ｔ・Ｃａｐｏｗ  ｍｏｄ  ｐ
【００５５】
図７は、本実施形態に係る秘匿２変数関数演算Ｆｕｎｃ（Ｃａ，Ｃｂ，Ｓ）のアルゴリズムを示す図である。
【００５６】
秘匿２変数関数演算Ｆｕｎｃ（Ｃａ，Ｃｂ，Ｓ）は、第１変数ａの暗号文Ｃａ、第２変数ｂの暗号文Ｃｂ、及び第２変数ｂの取り得る値の集合Ｓを引数とし、ｇ（ａ，ｂ）の暗号文であるＣｇ（ａ，ｂ）＝ｇ（Ｃａ，Ｃｂ）を返す。
秘匿２変数関数演算Ｆｕｎｃ（Ｃａ，Ｃｂ，Ｓ）は、前述の３つのサブモジュールＰｏｗｓ、ＣｏｎｓｔＦｕｎｃ、ＣｏｎｓｔＥｑを用いて構成される。
【００５７】
ステップＳ５１において、制御部１０は、内部変数Ｃｓｕｍを０に初期化する。
ステップＳ５２において、制御部１０（秘匿冪乗演算部１２）は、Ｐｏｗｓ（Ｃａ，ｐ）により、引数のＣａについて、１〜ｐ−１を冪指数とする冪乗値からなる冪乗列ベクトルＣａｐｏｗを算出する。
ステップＳ５３において、制御部１０（秘匿冪乗演算部１２）は、Ｐｏｗｓ（Ｃｂ，｜Ｓ｜）により、引数のＣｂについて、１〜｜Ｓ｜−１を冪指数とする冪乗値からなる冪乗列ベクトルＣｂｐｏｗを算出する。
【００５８】
ステップＳ５４において、制御部１０は、集合Ｓの要素ｉのそれぞれについて、後続のステップＳ５５〜Ｓ５７を繰り返すループ処理を行う。
ステップＳ５５において、制御部１０（秘匿関数演算部１３）は、ｉを定数として、Ｃｇ（ａ，ｉ）＝ｇ（Ｃａ，ｉ）＝ＣｏｎｓｔＦｕｎｃ（Ｃａｐｏｗ，ｉ）を計算する。
ステップＳ５６において、制御部１０（秘匿等号演算部１４）は、ｉを定数として、Ｃ（ｂ＝ｉ）＝ＣｏｎｓｔＥｑ（Ｃｂｐｏｗ，ｉ）を計算する。
【００５９】
ステップＳ５７において、制御部１０（出力部１５）は、Ｃｇ（ａ，ｉ）とＣ（ｂ＝ｉ）との準同型乗算（ＦＨＥ．Ｍｕｌｔ）をＣｓｕｍに足し合わせる。
ここで、Ｃｇ（ａ，ｉ）×Ｃ（ｂ＝ｉ）は、ｉ＝ｂのときＣｇ（ａ，ｂ）となり、ｉ≠ｂのときＣ０となる。したがって、ループ処理が終了し、Ｃｇ（ａ，ｉ）とＣ（ｂ＝ｉ）との積が総和されると、Ｃｓｕｍ＝Ｃｇ（ａ，ｂ）となる。
ステップＳ５８において、制御部１０（出力部１５）は、結果として得られたＣｇ（ａ，ｂ）＝Ｃｓｕｍを出力する。
【００６０】
図８は、本実施形態に係る秘匿２変数関数演算Ｆｕｎｃを秘匿除算演算に適用した場合の実行速度を、部分集合Ｓによる制限の有無で比較した実験結果を示す図である。
ここでは、第２引数（割る数）ｄの大きさ｜Ｓ｜を、平文空間ｐ＝２ｌに対して、ｌに制限している。
【００６１】
例えば、ｐ＝１７の場合、制限付きの場合の実行時間は０．８７秒となり、制限のない場合の３．１５秒に比べて、大幅に短縮された、この他、ｐ＝３７，６７，１３１，２５７のいずれの場合についても同様に、実行時間は大幅に短縮された。
【００６２】
図９及び１０は、本実施形態に係る秘匿２変数関数演算Ｆｕｎｃ及びサブモジュールにおける準同型乗算の深さ（Ｄｅｐｔｈ）と、準同型乗算（ＦＨＥ．Ｍｕｌｔ）、（準同型加算ＦＨＥ．Ａｄｄ）及び準同型定数乗算（ＦＨＥ．ｍｕｌｔＣｏｎｓｔ）の呼び出し回数とを示す図である。
ここで、図９は、部分集合Ｓによる制限を設けない場合を、図１０は、部分集合Ｓによる制限を設けた場合を示している。
【００６３】
部分集合Ｓの要素数｜Ｓ｜＝ｌとしたとき、ｌビット長の入力に対する乗算の深さと、準同型演算の呼び出し回数は、制限を設けない場合に比べて削減されている。
この結果、理論的計算量は、Ｏ（２２ｌ）からＯ（ｌ２ｌ）に削減された。
【００６４】
本実施形態によれば、秘匿計算装置１は、任意の２変数関数（例えば、除算、２値比較等）について、第２変数を固定した場合の１変数関数を、多項式補間により表現する。秘匿計算装置１は、この多項式の係数と引数の冪乗とを用いた秘匿定数関数演算ＣｏｎｓｔＦｕｎｃ、及び秘匿定数等号演算ＣｏｎｓｔＥｑにより、任意の２変数関数の秘匿計算を汎用的に実現できる。
【００６５】
ここで、秘匿計算装置１は、完全準同型暗号により任意の２変数関数の秘匿計算を実現した。例えば非特許文献５の二者間プロトコルを用いた手法では、ユーザとサーバとの間で少なくともｌｏｇ  ｌラウンドの通信回数が必要だが、本実施形態の通信回数は１ラウンドのみとなる。
さらに、秘匿計算装置１は、平文の空間Ｚｐに対して、第２変数を任意の部分集合Ｓに制限した。これにより、秘匿計算装置１は、Ｚｐ全体を対象とする汎用性を維持しつつ、秘匿定数等号演算ＣｏｎｓｔＥｑ、秘匿定数関数演算ＣｏｎｓｔＦｕｎｃ、及び処理負荷の大きい準同型乗算の実行回数を削減して高速化を実現した。
また、秘匿計算装置１は、第２変数が取り得る値が部分集合Ｓの要素のみのため、秘匿定数等号演算ＣｏｎｓｔＥｑにおける第２多項式は｜Ｓ｜−１次式となり、計算量を削減できる。
【００６６】
秘匿計算装置１は、秘匿冪乗演算Ｐｏｗｓによって、引数である暗号文の冪乗列ベクトルを一度計算すると、このベクトルを再利用することで、暗号文同士の乗算の回数が抑制される。
また、秘匿計算装置１は、秘匿定数等号演算ＣｏｎｓｔＥｑ及び秘匿定数関数演算ＣｏｎｓｔＦｕｎｃにおいて、事前計算によって係数ベクトルを保存しておくことで、再利用を可能にした。さらに、集合Ｓに含まれる定数についてのみ、秘匿定数等号演算ＣｏｎｓｔＥｑ及び秘匿定数関数演算ＣｏｎｓｔＦｕｎｃにおける係数ベクトルを保存しておくことにより、事前計算の処理負荷を低減できる。
【００６７】
特に、秘匿計算装置１は、ｉｎｔｅｇｅｒ−ｗｉｓｅの秘匿除算演算を、従来に比べて高速に実現できる。
これにより、秘匿計算装置１は、除算を含む種々の秘匿計算、例えば、秘匿平均値計算又は秘匿機械学習等を高速に実現できる。
【００６８】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、前述した実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、実施形態に記載されたものに限定されるものではない。
【００６９】
秘匿計算装置１による秘匿計算方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００７０】
１  秘匿計算装置
１０  制御部
１１  入力部
１２  秘匿冪乗演算部
１３  秘匿関数演算部
１４  秘匿等号演算部
１５  出力部
２０  記憶部（第１記憶部、第２記憶部）
【図１】
2020160353.tif 000003
【図２】
2020160353.tif 000004
【図３】
2020160353.tif 000005
【図４】
2020160353.tif 000006
【図５】
2020160353.tif 000007
【図６】
2020160353.tif 000008
【図７】
2020160353.tif 000009
【図８】
2020160353.tif 000010
【図９】
2020160353.tif 000011
【図１０】
2020160353.tif 000012