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