(57)【要約】環の位数のｂｉｔ長をLとしたとき、秘密分散の方法に依らず、通信ラウンド数をＯ（Ｌｏｇ_（L））に抑えて実行する。秘密等号判定システムは、乱数生成サーバ装置とマスク値復元サーバ装置と秘密計算サーバ装置とを備える。乱数生成サーバ装置は、乱数を生成する乱数生成部と、乱数と秘密等号判定における被演算子の秘密分散データを用いてマスクされた秘密分散データを生成するシェア加算部と、入力された値の秘密分散データを生成する秘密分散データ生成部と、秘密分散データを復元して元の値を得る秘密分散データ復元部と、秘密分散データを用いて秘密等号判定を行う判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部とを有する。マスク値復元サーバ装置は、入力された値の秘密分散データを生成する秘密分散データ生成部と、秘密分散データを復元して元の値を得る秘密分散データ復元部と、秘密分散データを用いて秘密等号判定を行う判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部とを有する。秘密計算サーバ装置は、入力された値の秘密分散データを生成する秘密分散データ生成部と、秘密分散データを復元して元の値を得る秘密分散データ復元部と、秘密分散データを用いて秘密等号判定を行う判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部とを有する。
2019111319.tif 000002
【特許請求の範囲】
【請求項１】
乱数を生成する乱数生成部と、
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する秘密分散データ生成部と、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するシェア加算部と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する秘密分散データ復元部と、
を備える乱数生成サーバ装置。
【請求項２】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、復元した値のｂｉｔのシェアを生成する秘密分散データ生成部と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、前記復元した値を出力する秘密分散データ復元部と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備え、
前記秘密分散データ復元部は、前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する、マスク値復元サーバ装置。
【請求項３】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する秘密分散データ生成部と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する秘密分散データ復元部と、
を備える秘密計算サーバ装置。
【請求項４】
請求項１に記載の乱数生成サーバ装置と、請求項２に記載のマスク値復元サーバ装置と、請求項３に記載の秘密計算サーバ装置の複数台とが、ネットワークで接続されて成る秘密等号判定システム。
【請求項５】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数を生成するステップと、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するステップと、
前記乱数のｂｉｔのシェアを生成するステップと、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含む乱数生成サーバ装置での秘密等号判定方法。
【請求項６】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力するステップと、
該復元した値のｂｉｔのシェアを生成するステップと、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含むマスク値復元サーバ装置での秘密等号判定方法。
【請求項７】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する秘密分散データ生成部と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含む秘密計算サーバ装置での秘密等号判定方法。
【請求項８】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数を生成する処理と、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、
前記乱数のｂｉｔのシェアを生成する処理と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
を乱数生成サーバ装置のコンピュータに実行させる秘密等号判定プログラムを記録した記録媒体。
【請求項９】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力する処理と、
該復元した値のｂｉｔのシェアを生成する処理と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
をマスク値復元サーバ装置のコンピュータに実行させる秘密等号判定プログラムを記録した記録媒体。
【請求項１０】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
を秘密計算サーバ装置のコンピュータに実行させる秘密等号判定プログラムを記録した記録媒体。
【請求項１１】
２つ被演算子を秘密分散して、２つの被演算子に関するｒｉｎｇのシェアを生成し、該生成した２つの被演算子に関するｒｉｎｇのシェアを複数のサーバ装置へ送信する秘密分散データ生成部と、
前記複数のサーバ装置から受け取った判定結果に基づいて、等号判定の結果を復元する秘密分散データ復元部と、
を備える秘密分散プロキシ装置。
【請求項１２】
乱数を生成する乱数生成部と、
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する秘密分散データ生成部と、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するシェア加算部と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備える乱数生成サーバ装置。
【請求項１３】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、復元した値のｂｉｔのシェアを生成する秘密分散データ生成部と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、前記復元した値を出力する秘密分散データ復元部と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備えるマスク値復元サーバ装置。
【請求項１４】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する秘密分散データ生成部と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備える秘密計算サーバ装置。
【請求項１５】
請求項１１に記載の秘密分散プロキシ装置と、請求項１２に記載の乱数生成サーバ装置と、請求項１３に記載のマスク値復元サーバ装置と、請求項１４に記載の秘密計算サーバ装置の複数台とが、ネットワークで接続されて成る秘密等号判定システム。
【請求項１６】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数を生成する乱数生成部と、
前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信するステップと、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するステップと、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含む乱数生成サーバ装置での秘密等号判定方法。
【請求項１７】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力するステップと、
前記復元した値のｂｉｔのシェアを生成するステップと、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含むマスク値復元サーバ装置での秘密等号判定方法。
【請求項１８】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含む秘密計算サーバ装置での秘密等号判定方法。
【請求項１９】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数を生成する処理と、
前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する処理と、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
を乱数生成サーバ装置のコンピュータに実現させる秘密等号判定プログラムを記録した記録媒体。
【請求項２０】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力する処理と、
前記復元した値のｂｉｔのシェアを生成する処理と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
をマスク値復元サーバ装置のコンピュータに実現させる秘密等号判定プログラムを記録した記録媒体。
【請求項２１】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
を秘密計算サーバ装置のコンピュータに実現させる秘密等号判定プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は秘密計算プロトコルに関し、特に効率よく秘密等号判定を行うことができる秘密等号判定システム、秘密等号判定方法および秘密等号判定プログラム記録媒体に関する。
【背景技術】
【０００２】
秘密計算プロトコルとは、プロトコルの各参加者の入力や計算過程の値を秘匿しつつ、計算結果のみを求めることができる技術である。秘密計算プロトコルとして、論理回路や算術回路をベースとして任意の計算を実行できる一般的な方式が提案されている。【０００３】
なお、秘密計算プロトコルによって任意の計算を実行する場合、通信コストが発生する。通信コストは、通信ラウンド数と通信量との２つの評価軸によって評価される。ここで、通信ラウンド数とは、ある計算処理を秘密計算プロトコルによって実行する際に、秘密計算プロトコルの各参加者間で生じた通信回数のことである。このとき、たとえば、秘密計算プロトコルの三名の参加者をＰ１、Ｐ２、Ｐ３とする。ある計算処理を秘密計算プロトコルによって実行する際に、Ｐ１−Ｐ２間で１回の通信、Ｐ２−Ｐ３間で１回の通信、Ｐ３−Ｐ１間で１回の通信がそれぞれ発生したとして、これらの通信が並行して行えるものであれば、１ラウンドとして通信ラウンド数を数えることに注意する。また、通信量とは、ある計算処理を秘密計算プロトコルによって実行する際に、秘密計算プロトコルの各参加者間で生じた通信データの量のことである。【０００４】
秘匿化されたデータを秘匿化したままで検索できる秘匿検索技術が、従来から種々提案されている。【０００５】
秘匿検索を実現する一つの技術として、マルチパーティ計算（Multi-Party Computation：ＭＰＣ）技術が知られている（例えば、非特許文献１参照）。【０００６】
ＭＰＣは、それぞれ秘密情報を持つ２台以上のサーバ装置が協力して計算することで、それぞれの秘密情報を漏らすことなく、秘密情報を入力とする任意の関数値を計算する。ＭＰＣを用いて秘匿検索を実現するには、次のようにすればよい。まず、預けるデータを秘密分散法（例えば、非特許文献１参照）で上記２台以上のサーバ装置に分散して保持する。そして、上記関数として「ある部分データを含むデータが秘密分散されてサーバ装置に保存されているときに１を、そうでないときに０を返す関数」のように定義する。【０００７】
ＭＰＣを実現する手段として、非特許文献１に記載されている、Shamirのしきい値型秘密分散法（Shamir’s Secret Sharing：ＳＳＳ）を用いる手段がある。まず、非特許文献１について説明する。【０００８】
しきい値型秘密分散法とは、秘密情報を複数の分散情報に変換する技術である。しきい値型秘密分散法は、変換された分散情報をしきい値以上の個数を集めることによって秘密情報を復元でき、しきい値以下の個数の分散情報からは元の秘密情報を漏らさないという特徴を持つ。【０００９】
非特許文献１のＳＳＳは、Ｎ台のサーバ装置で有限体Zpに属する数aを秘密に分散する方法であり、k-1次多項式f_a(x)を用いる。この方法では、例えばf_a(0)=aとし、第iのサーバ装置（１≦i≦N）には、それぞれ多項式上の点f_a(i)を配る。配られる情報f_a(i)をSSSにおけるxの分散情報と呼ぶ。このとき、k台のサーバ装置が協力すると、多項式上のk個の点からk-1次多項式f_a(x)を一意に復元することができるので、秘密情報であるf_a(0)を求めることができる。【００１０】
秘密情報aを、pを法とする多項式f_a(x)を用いてＮ台のサーバ装置で分散するときに生成される、秘密情報aの分散情報を、[a]p=(f_a(1), f_a(2), …, f_a(N))と書くことにする。このとき、識別子i（１≦i＜Ｎ）を持つ第iのサーバ装置にf_a(i)が保持されているものとする。【００１１】
任意の計算を実行できる一般的な方式として、たとえば、非特許文献２、非特許文献３、非特許文献４、非特許文献５が挙げられる。大まかな方式の種類は、非特許文献４に代表されるＧａｒｂｌｅｄ  Ｃｉｒｃｕｉｔベースの方式と、非特許文献２、非特許文献３、非特許文献５のような秘密分散法ベースの方式とに分けられる。なお、秘密分散法とは、ある値を複数に分散し、分散された値を閾値以上の個数分だけ集めると、元の秘密情報を復元できる、というものである。ここで、分散した値を、秘密分散データやシェアと呼ぶ。【００１２】
非特許文献３は、論理回路と算術回路および両者を混合した回路について、計算を実行可能な秘密計算プロトコルを開示している。非特許文献２と異なり、非特許文献３は、非特許文献１の秘密分散法を用いており、素数pを位数とする体上での計算となる。このため、非特許文献３では、体の位数の大きさに比例して、通信量が増大する。ここで、論理回路と算術回路の混合回路を計算する際に、論理回路における値と算術回路における値は、ともに素数pを位数とする体に属する値であることに注意する。なお、非特許文献３では、位数の大きさに関わらず、定数回の通信ラウンド数で計算が実行できる。ただし、多量の通信量を必要とする。【００１３】
非特許文献４は、論理回路ベースで計算を実行する秘密計算プロトコルを開示している。非特許文献４の方式は、疑似ランダム関数と紛失通信プロトコルを用いた方式で、定数回の通信ラウンド数で計算が実行できる。ただし、非特許文献４の方式では、多量の通信量を必要とする。【００１４】
非特許文献２は、論理回路と算術回路および両者を混合した回路について、計算を実行可能な秘密計算プロトコルを開示している。非特許文献２の方式は、剰余環上の加法秘密分散法をベースとした方式で、環の位数の大きさに比例して、通信量が増大する。また、非特許文献２の方式は、非特許文献３の方式と異なり、論理回路と算術回路の混合回路を計算する際に、それぞれの値に応じた環上で計算することが可能である。たとえば、論理回路の値は位数２の環に属する値、算術回路の値は位数２＾ｎ’（ｎ’は２より大きい整数）の環に属する値として、計算可能である。非特許文献３の方式は、論理回路における値０，１も素数ｐを位数とする体上で計算する必要があるため、非特許文献２の方が通信量を小さく抑えることができる。なお、非特許文献３や非特許文献４といった、定数回の通信ラウンド数で計算を実行する方式と比べると、同じ計算処理を行う場合、非特許文献２の方が少ない通信量で実行できる。ただし、非特許文献２の方式は、計算処理の回路の深さに比例して、通信ラウンド数が増大する。【００１５】
ここで、計算処理の回路の深さとは、入力ゲートから出力ゲートまでに通過する必要がある最大ゲート総数ではなく、入力ゲートから出力ゲートまでに通過する必要がある論理積ゲートと乗算ゲートの最大ゲート総数を指す。以降、回路の深さとは、入力ゲートから出力ゲートまでに通過する必要がある論理積ゲートと乗算ゲートと秘密分散復元ゲートの最大ゲート総数を意味することとする。【００１６】
非特許文献５は、論理回路と算術回路との両者を混合した回路について、計算を実行可能な秘密計算プロトコルを開示している。非特許文献５の方式は、剰余環上の複製型秘密分散法をベースとした方式で、位数の大きさに比例して、通信量が増大する。ここで、非特許文献５の方式は、非特許文献２の方式と同様に非特許文献３の方式と異なり、論理回路と算術回路の混合回路を計算する際に、それぞれの値に応じた環上で計算することが可能である。このため、非特許文献５の方が非特許文献３の方式より通信量を小さく抑えることができる。また、非特許文献３や非特許文献４といった、定数回の通信ラウンド数で計算を実行する方式と比べると、同じ計算処理を行う場合、非特許文献５の方が少ない通信量で実行できる。ただし、非特許文献５の方式は、計算処理の回路の深さに比例して、通信ラウンド数が増大する。【００１７】
ここで、たとえば、通信ラウンド数の面で効率が良い秘密計算プロトコルは、ｌａｔｅｎｃｙが大きい通信環境で有効な方式といえる。また、通信量の面で効率が良い秘密計算プロトコルは、通信帯域が狭い通信環境で有効な方式である。秘密分散ベースの秘密計算プロトコルでは、回路の深さに比例して通信が発生するために、大量の入力を一度に処理することで単位時間あたりの処理量の向上を図ることがある。このため特に、通信帯域が狭い通信環境でも単位時間あたりの処理量を確保したい場合は、通信量について効率の良い秘密計算プロトコルの提案が重要となる。【００１８】
このとき、排他的論理和や論理積、加算や乗算といった基本的な二項演算に対して、効率の良い方法を提案するだけでなく、より上位の計算プロトコルについて提案することも必要といえる。上位の計算プロトコルとは、たとえば、秘密等号判定が挙げられる。ここで、秘密等号判定とは、秘匿されたある環上の要素ａ,ｂを引数に取り、ａとｂが一致するのであれば位数２の環上の要素である１を秘匿した値、不一致であれば位数２の環上の要素である０を秘匿した値をそれぞれ返す処理である。秘密等号判定は、秘密計算プロトコルにおける部分一致判定や距離計算といった文字列処理にて多用される。【００１９】
ここで、非特許文献２の秘密等号判定による通信ラウンド数は（Ｌｏｇ（L）＋１）回、通信量は(１７L−１５)となる。なお、Ｌｏｇの底は２であり、Lは環の位数のビット長である。非特許文献２では、秘密等号判定の通信ラウンド数を抑えるために、非特許文献２で用いられる加法秘密分散法に依存した技法を用いている。具体的には値ｖを秘密分散する際に、ある参加者の秘密分散データをｖとし、残りの参加者の秘密分散データを０とすることで、通信ラウンド数を削減している。このため、非特許文献２の秘密等号判定の方法を非特許文献５によって実施することはできない。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】Ａｄｉ  Ｓｈａｍｉｒ、“Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ、”  Ｃｏｍｍｕｎ．  ＡＣＭ  ２２（１１）、  ｐｐ．６１２−６１３、  １９７９．
【非特許文献２】Ｄａｎ  Ｂｏｇｄａｎｏｖ、Ｍａｒｇｕｓ  Ｎｉｉｔｓｏｏ、Ｔｏｍａｓ  Ｔｏｆｔ、Ｊａｎ  Ｗｉｌｌｅｍｓｏｎ、  “Ｈｉｇｈ−ｐｅｒｆｏｒｍａｎｃｅ  ｓｅｃｕｒｅ  ｍｕｌｔｉ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｆｏｒ  ｄａｔａ  ｍｉｎｉｎｇ  ａｐｐｌｉｃａｔｉｏｎｓ、”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ、１１（６）、４０３−４１８．
【非特許文献３】Ｔａｋａｓｈｉ  Ｎｉｓｈｉｄｅ、Ｋａｚｕｏ  Ｏｈｔａ、  “Ｍｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ  ｆｏｒ  Ｉｎｔｅｒｖａｌ，Ｅｑｕａｌｉｔｙ，ａｎｄ  Ｃｏｍｐａｒｉｓｏｎ  ｗｉｔｈｏｕｔ  Ｂｉｔ−Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  Ｐｒｏｔｏｃｏｌ、”  Ｉｎ  ＰＫＣ２００７、ＬＮＣＳ、ｖｏｌ．４４５０、ｐｐ．９０−１０４、Ｓｐｒｉｎｇｅｒ、Ｂｅｒｌｉｎ、Ｈｅｉｄｅｌｂｅｒｇ．
【非特許文献４】Ａｎｄｒｅｗ  Ｃ．Ｙａｏ、“Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｓｅｃｕｒｅ  ｃｏｍｐｕｔａｔｉｏｎｓ、”Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２１ｓｔ  Ａｎｎｕａｌ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  ｔｈｅ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、ｐｐ．１６０−１６４、１９８２．
【非特許文献５】Ｔｏｓｈｉｎｏｒｉ  Ａｒａｋｉ、Ｊｕｎ  Ｆｕｒｕｋａｗａ、Ｙｅｈｕｄａ  Ｌｉｎｄｅｌｌ、Ａｒｉｅｌ  Ｎｏｆ、Ｋａｚｕｍａ  Ｏｈａｒａ、“Ｈｉｇｈ−Ｔｈｒｏｕｇｈｐｕｔ  Ｓｅｍｉ−Ｈｏｎｅｓｔ  Ｓｅｃｕｒｅ  Ｔｈｒｅｅ−ｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ  ｗｉｔｈ  ａｎ  Ｈｏｎｅｓｔ  Ｍａｊｏｒｉｔｙ、”  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０１６  ＡＣＭ  ＳＩＧＳＡＣ  Ｃｏｎｆｅｒｅｎｅｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ、ｐｐ．８０５−８１７、ＡＣＭ．
【発明の概要】
【発明が解決しようとする課題】
【００２１】
このように非特許文献２では、秘密等号判定を行う際に、非特許文献２で用いる加法秘密分散法に依存した方法を用いている。このため、論理積や乗算を行う際に、非特許文献２よりも小さい通信量で実行できる、非特許文献５を用いて同様の秘密等号判定を実施することはできなかった。秘密等号判定を行う際に通信量が多いと、通信帯域が狭い通信環境では、単位時間あたりの処理量の低下が生じ得る。特に、等号判定を多用するような文字列処理を秘密計算プロトコルで実行する場合、秘密等号判定における通信量の増加は、計算処理全体の単位時間あたりの処理量低下を引き起こす恐れがある。【００２２】
本発明の目的は、上記課題を解決し、環の位数のｂｉｔ長をLとしたとき、秘密分散の方法に依らず、通信ラウンド数をＯ（Ｌｏｇ（L））に抑えて実行できる、秘密等号判定システム、秘密等号判定方法、および秘密等号判定プログラム記録媒体を提供することにある。
【課題を解決するための手段】
【００２３】
上述の課題に鑑み、本発明の一態様は、ネットワークで接続された乱数生成サーバ装置とマスク値復元サーバ装置と複数の秘密計算サーバ装置とを備える秘密等号判定システムであって、
前記乱数生成サーバ装置は、乱数を生成する乱数生成部と；２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する秘密分散データ生成部と；前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データを前記マスク値復元サーバ装置へ送信するシェア加算部と；前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と；前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果を復元する秘密分散データ復元部と；を有し、
前記マスク値復元サーバ装置は、２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、復元した値のｂｉｔのシェアを生成する秘密分散データ生成部と；前記ｒｉｎｇのシェアと、前記複数の秘密計算サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、前記復元した値を出力する秘密分散データ復元部と；前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と；を備え、前記秘密分散データ復元部は、前記判定結果と他のサーバ装置からの判定結果に基づいて、前記判定結果のｂｉｔのシェアを復元し、
前記秘密計算サーバ装置の各々は、２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する秘密分散データ生成部と；乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と；前記判定結果と他のサーバ装置からの判定結果に基づいて、前記判定結果のｂｉｔのシェアを復元する秘密分散データ復元部と；を有することを特徴とする秘密等号判定システムである。【００２４】
また、本発明の他の態様は、２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、乱数を生成するステップと、前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するステップと、前記乱数のｂｉｔのシェアを生成するステップと、前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、を含む乱数生成サーバでの秘密等号判定方法である。【００２５】
さらに、本発明の別の態様は、２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、乱数を生成する処理と、前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、前記乱数のｂｉｔのシェアを生成する処理と、前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、を乱数生成サーバ装置のコンピュータに実行させる秘密等号判定プログラムを記録した記録媒体である。
【発明の効果】
【００２６】
本発明によれば、被計算値や判定結果や計算過程の値を知ることができない秘密等号判定を、通信ラウンド数をＯ（Ｌｏｇ（L））に抑えながら、構成要素の改善によって通信量を改善することが可能である。Lは環の位数のｂｉｔ長である。たとえば、非特許文献５で本発明を実施すると、非特許文献２における秘密等号判定と比較して、小さい通信量で秘密等号判定を実行できる。【００２７】
本発明の更なる利点及び実施形態を、記述と図面を用いて下記に詳細に説明する。
【図面の簡単な説明】
【００２８】
【図１】本発明の第１の実施形態における秘密等号判定システムの機能構成例を示すブロック図である。
【図２】本発明の第１の実施形態による乱数生成サーバ装置の機能構成を示すブロック図である。
【図３】本発明の第１の実施形態によるマスク値復元サーバ装置の機能構成を示すブロック図である。
【図４】本発明の第１の実施形態による秘密計算サーバ装置の機能構成を示すブロック図である。
【図５】本発明の第１の実施形態による乱数生成サーバ装置の動作例を示すフローチャートである。
【図６】本発明の第１の実施形態によるマスク値復元サーバ装置の動作例を示すフローチャートである。
【図７】本発明の第１の実施形態による秘密計算サーバ装置の動作例を示すフローチャートである。
【図８】本発明の第２の実施形態における秘密等号判定システムの機能構成例を示すブロック図である。
【図９】本発明の第２の実施形態による秘密分散プロキシ装置の機能構成を示すブロック図である。
【図１０】本発明の第２の実施形態による乱数生成サーバ装置の機能構成を示すブロック図である。
【図１１】本発明の第２の実施形態によるマスク値復元サーバ装置の機能構成を示すブロック図である。
【図１２】本発明の第２の実施形態による秘密計算サーバ装置の機能構成を示すブロック図である。
【図１３】本発明の第２の実施形態による秘密分散プロキシ装置の動作例を示すフローチャートである。
【図１４】本発明の第２の実施形態による乱数生成サーバ装置の動作例を示すフローチャートである。
【図１５】本発明の第２の実施形態によるマスク値復元サーバ装置の動作例を示すフローチャートである。
【図１６】本発明の第２の実施形態による秘密計算サーバ装置の動作例を示すフローチャートである。
【発明を実施するための形態】
【００２９】
以下、本発明の実施形態について図面を参照しつつ説明する。但し、以下に説明する実施形態によって本発明の技術的範囲は何ら限定解釈されることはない。
【００３０】
（第１の実施形態）
図１乃至図７を参照して、本発明の第１の実施形態係る秘密等号判定システムについて説明する。
【００３１】
図１は、本発明の第１の実施形態による秘密等号判定システムの機能構成例を示すブロック図である。
【００３２】
図１を参照すると、本発明の第１の実施形態による秘密等号判定システムは、後述する図２で参照される乱数生成サーバ装置１００_０と、後述する図３で参照されるマスク値復元サーバ装置１１０_１と、後述する図４で参照される第２乃至第ｎ（ｎは２以上の整数）のサーバ装置１１０_２、．．．、１１０_ｎとから成る。第１の実施形態による秘密等号判定システムにおいて、乱数生成サーバ装置１００_０とマスク値復元サーバ装置１１０_１と第２乃至第ｎのサーバ装置１１０_２〜１１０_ｎとは、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。
【００３３】
図２に示すように、乱数生成サーバ装置１００_０は、乱数生成部１０１_０と、シェア加算部１０２_０と、秘密分散データ生成部１０３_０と、秘密分散データ復元部１０４_０と、判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０と、データ記憶部１０６_０と、を含む。シェア加算部１０２_０は、マスク値復元サーバ装置１１０_１とネットワーク経由で通信可能に接続されている。秘密分散データ生成部１０３_０と秘密分散データ復元部１０４_０と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部とデータ記憶部１０６_０とは、それぞれ自身が含まれるサーバ装置と異なるサーバ装置とネットワーク経由で通信可能に接続されている。乱数生成部１０１_０は、シェア加算部１０２_０と秘密分散データ生成部１０３_０と、それぞれ通信可能に接続されている。データ記憶部１０６_０は、シェア加算部１０２_０と秘密分散データ生成部１０３_０と秘密分散データ復元部１０４_０と判定ｂｉｔ-ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０と、それぞれ通信可能に接続されている。
【００３４】
図３に示すように、マスク値復元サーバ装置１１０_１は、秘密分散データ生成部１１３_１と、秘密分散データ復元部１１４_１と、判定ｂｉｔ-ｃｏｎｊｕｎｃｔｉｏｎ部１１５_１と、データ記憶部１１６_１と、を含む。秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_１とデータ記憶部１１６_１とは、それぞれ自身が含まれるサーバ装置と異なるサーバ装置とネットワーク経由で通信可能に接続されている。データ記憶部１１６_１は、秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_１と、それぞれ通信可能に接続されている。秘密分散データ生成部１１３_１は秘密分散データ復元部１１４_１と通信可能に接続されている。
【００３５】
図４に示すように、第ｉの秘密計算サーバ装置１１０_ｉ（２≦ｉ≦ｎ）は、第ｉの秘密分散データ生成部１１３_ｉと、第ｉの秘密分散データ復元部１１４_ｉと、第ｉの判定ｂｉｔ-ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと、第ｉのデータ記憶部１１６_ｉと、を含む。秘密分散データ復元部１１３_ｉと秘密分散データ復元部１１４_ｉと判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉは、それぞれ自身が含まれるサーバ装置と異なるサーバ装置とネットワーク経由で通信可能に接続されている。データ記憶部１１６_ｉは、秘密分散データ生成部１１３_ｉと秘密分散データ復元部１１４_ｉと判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと、それぞれ通信可能に接続されている。
【００３６】
このような構成の秘密等号判定システムにおいては、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１、第２乃至第ｎのサーバ装置１１０_２〜１１０_ｎの内のいずれかの装置が入力した値ａ，ｂ、あるいは、データ記憶部１０６_０、１１６_１、１１６_２〜１１６_ｎに記憶された秘密分散データ［ａ］，［ｂ］に対し、その入力や計算過程の値からａ，ｂの値を知られることなく、ａ＝ｂが成り立つか否かの判定結果の秘密分散データを計算し、データ記憶部１０６_０、１１６_１、１１６_２〜１１６_ｎにそれぞれ記憶する。前記判定結果の秘密分散データは、データ記憶部１０６_０、１１６_１、１１６_２〜１１６_ｎに記憶した後、秘密分散データ復元部１０４_０、１１４_１、１１４_２〜１１４_ｎにそれぞれ渡し、復元結果を得ても良い。
【００３７】
次に、本発明の第１の実施形態における秘密等号判定システム、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１および第ｉのサーバ装置１１０_ｉの動作例について詳細に説明する。図５は、乱数生成サーバ装置１００_０の動作例を示すフローチャートである。図６は、マスク値復元サーバ装置１１０_１の動作例を示すフローチャートである。図７は、第ｉの秘密計算サーバ装置１１０_ｉの動作例を示すフローチャートである。
【００３８】
ここで、［ａ］_Ｂは、位数２の環上の値ａの秘密分散データを意味する。また、［ｂ］_Ｒは、位数が２より大きい環上の値ｂの秘密分散データを意味する。以降、［ａ］_Ｂをａのｂｉｔのシェア、［ｂ］_Ｒをｂのｒｉｎｇのシェアと呼称する。特に、第ｉのサーバ装置１１０_ｉのシェアを表す場合、［ａ］_Ｂｉ，［ｂ］_Ｒｉとする。また、乱数生成サーバ装置１００_０のシェアを表す場合は、［ａ］_Ｂ０，［ｂ］_Ｒ０とする。マスク値復元サーバ装置１１０_１のシェアを表す場合は、［ａ］_Ｂ１，［ｂ］_Ｒ１とする。
【００３９】
たとえば、サーバ装置の台数が３、つまり、ｎ＝３であるとする。このとき、非特許文献２や非特許文献５で用いられている秘密分散が例として挙げられる。ここで、
【００４０】
【数１】
2019111319.tif 000003
を、それぞれｂｉｔのシェアに関する排他的論理和、論理積とする。これらは、位数２の環上の要素に対する二項演算子としての排他的論理和、論理積の記号としても以降用いることに注意されたい。ここで、ｂｉｔのシェアに関する排他的論理和、論理積には次の性質が成り立つ。
【００４１】
【数２】
2019111319.tif 000004
さらに、＋，−を、それぞれｒｉｎｇのシェアに関する加法演算子、減法演算子とする。これらは、位数が２より大きい環上の要素に対する二項演算子としての加法演算子、減法演算子としても以降用いることに注意されたい。ここで、ｒｉｎｇのシェアに関する加法演算子、減法演算子には次の性質が成り立つ。
【００４２】
【数３】
2019111319.tif 000005
たとえば、サーバ装置の台数が３、つまり、ｎ＝３であるとする。このとき、非特許文献５ではｂｉｔのシェアに関する排他的論理和を通信不要で計算できる。また、非特許文献５ではｂｉｔのシェアに関する論理積を１ラウンド３ｂｉｔの通信コストで計算できる。
【００４３】
なお、ａ＝ｂが成り立つか否か判定する際に、ａ，ｂのｂｉｔ長をLとする。つまり、ｒｉｎｇのシェアのｂｉｔ長はLである。また、秘密等号判定の結果は、等号が成り立つ場合に［１］_Ｂ、成り立たない場合に［０］_Ｂを出力する。
【００４４】
（ステップＡ１）
図５乃至図７を参照して、乱数生成サーバ装置１００_０、もしくは、マスク値復元サーバ装置１１０_１、あるいは、第ｉのサーバ装置１１０_ｉの動作として、まず、入力（第１の被演算子）ａを図示されない入力装置から秘密分散データ生成部１０３_０、もしくは、１１３_１、あるいは１１３_ｉに渡す。秘密分散データ生成部１０３_０、もしくは、１１３_１、あるいは１１３_ｉは、第１の被演算子ａのｒｉｎｇのシェア［ａ］_Ｒを生成する。乱数生成サーバ装置１００_０は、［ａ］_Ｒ０をデータ記憶部１０６_０に保存する。マスク値復元サーバ装置１１０_１は、［ａ］_Ｒ１をデータ記憶部１１６_１に保存する。第ｉの秘密計算サーバ装置１１０_ｉは、［ａ］_Ｒｉを第ｉのデータ記憶部１１６_ｉに保存する。第１の被演算子ａのｒｉｎｇのシェア［ａ］_Ｒを生成した乱数生成サーバ装置１００_０、もしくは、マスク値復元サーバ装置１１０_１、あるいは、第ｉのサーバ装置１１０_ｉは、自身と異なるサーバ装置に対し、添え字ｉ’に対応する［ａ］_Ｒｉ’を渡す。たとえば、ｉ’＝０なら、乱数生成サーバ装置１００_０は、［ａ］_Ｒ０をデータ記憶部１０６_０に保存する。ｉ’＝１なら、マスク値復元サーバ装置１１０_１は、［ａ］_Ｒ１をデータ記憶部１１６_１に保存する。それ以外の場合は、第ｉ’の秘密計算サーバ装置１１０_ｉ’は、［ａ］_Ｒｉ’を第ｉ’のデータ記憶部１１６_ｉ’に保存する。入力（第２の被演算子）ｂに関しても、同様に処理する。ステップＡ１は計算を開始する際のみに生じるステップである。よって、秘密計算プロトコルの過程で生じたｒｉｎｇのシェアについて秘密等号判定を行う場合、ステップＡ１は発生しない。
【００４５】
（ステップＡ２）
次に、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１、および第ｉの秘密計算サーバ装置１１０_ｉは、それぞれのデータ記憶部１０６_０、１１６_１、１１６_ｉに保存された［ａ］_Ｒ，［ｂ］_Ｒの値から、２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ］_Ｒ−［ｂ］_Ｒ＝［ａ−ｂ］_Ｒを生成する。生成した後、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１、および第ｉの秘密計算サーバ装置１１０_ｉは、それぞれのデータ記憶部１０６_０、１１６_１、１１６_ｉに、それぞれ［ａ−ｂ］_Ｒ０、［ａ−ｂ］_Ｒ１、［ａ−ｂ］_Ｒｉを保存する。
【００４６】
（ステップＢ３）
図５を参照すると、乱数生成サーバ装置１００_０に含まれる乱数生成部１０１_０は、位数が２より大きい環上の値として、乱数ｒを生成する。生成後、乱数生成部１０１_０は、シェア加算部１０２_０および秘密分散データ生成部１０３_０に乱数ｒを送る。
【００４７】
（ステップＢ４）
乱数生成サーバ装置１００_０に含まれるシェア加算部１０２_０は、データ記憶部１０６_０から２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒ０を取り出す。シェア加算部１０２_０は、２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒ０に乱数ｒを加えた［ａ−ｂ＋ｒ］_Ｒ０（＝［ａ−ｂ］_Ｒ０＋ｒ）を、マスクされた秘密分散データとしてマスク値復元サーバ装置１１０_１に含まれる秘密分散データ復元部１１４_１に送る。
【００４８】
（ステップＣ５）
図６を参照すると、マスク値復元サーバ装置１１０_１に含まれる秘密分散データ復元部１１４_１は、データ記憶部１１６_１から２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒ１を取り出す。また、第ｉの秘密計算サーバ装置１１０_ｉ（２≦ｉ≦ｎ）から２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］Ｒｉを取り出す。このとき、データを復元するにあたり必要な秘密分散データの個数をｋとしたとき、［ａ−ｂ］Ｒｉを取り出す個数は（ｋ−２）個となる。秘密分散データ復元部１１４_１は、２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒ１と、（ｋ−２）個の２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］Ｒｉと、前記ステップＢ４にて送られてきたマスクされた秘密分散データ［ａ−ｂ＋ｒ］_Ｒ０とを用いて、マスクされた値ａ−ｂ＋ｒを復元する。復元後、秘密分散データ復元部１１４_１は、復元した値ａ−ｂ＋ｒを秘密分散データ生成部１１３_１に渡す。
【００４９】
（ステップＣ６）
秘密分散データ生成部１１３_１は、前記ステップＣ５にて渡された復元した値ａ−ｂ＋ｒの各ｂｉｔに対し、ｂｉｔのシェアを生成する。ここで、復元した値ａ−ｂ＋ｒのｔ−ｂｉｔ目（ｔ＝０，．．．，L−1の値を（ａ−ｂ＋ｒ）_ｔとする。このとき、復元した値ａ−ｂ＋ｒの各ｂｉｔに対するｂｉｔのシェアとは［（ａ−ｂ＋ｒ）_ｔ］_Ｂを指す。［（ａ−ｂ＋ｒ）_ｔ］_Ｂを生成した後、秘密分散データ生成部１１３_１は、添え字ｉに対応する外部の第ｉの秘密計算サーバ装置１１０_ｉに復元した値のｂｉｔのシェア［（ａ−ｂ＋ｒ）_ｔ］_Ｂｉを送信する。つまり、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１、および第ｉの秘密計算サーバ装置１１０_ｉは、それぞれのデータ記憶部１０６_０、１１６_１、１１６_ｉに、それぞれ復元した値のｂｉｔのシェア［（ａ−ｂ＋ｒ）_ｔ］_Ｂ０、［（ａ−ｂ＋ｒ）_ｔ］_Ｂ１、［（ａ−ｂ＋ｒ）_ｔ］_Ｂｉを保存する。
【００５０】
（ステップＢ７）
図５に戻って、乱数生成サーバ装置１００_０に含まれる秘密分散データ生成部１０３_０は、ステップＢ３にて送られた乱数ｒに対し、乱数ｒの各ｂｉｔについてｂｉｔのシェアを生成する。ここで、乱数ｒのｔ−ｂｉｔ目（ｔ＝０，．．．，L−1）の値をｒ_ｔとする。このとき、乱数ｒの各ｂｉｔに対するｂｉｔのシェアとは、［ｒ_ｔ］_Ｂを指す。［ｒ_ｔ］_Ｂを生成した後、秘密分散データ生成部１０３_０は、添え字ｉに対応する外部の第ｉの秘密計算サーバ装置１１０_ｉに乱数のｂｉｔのシェア［ｒ_ｔ］_Ｂｉを送信する。つまり、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１、および第ｉの秘密計算サーバ装置１１０_ｉは、それぞれのデータ記憶部１０６_０、１１６_１、１１６_ｉに、それぞれ乱数のｂｉｔのシェア［ｒ_ｔ］_Ｂ０、［ｒ_ｔ］_Ｂ１、［ｒ_ｔ］_Ｂｉを保存する。
【００５１】
（ステップＡ８）
図５乃至図７を参照して、ここで、復元した値ｃ＝ａ−ｂ＋ｒとしたとき、ｃ_ｔ（ｔ＝０，．．．，L−１）をｃの各ｂｉｔとする。乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１および第ｉの秘密計算サーバ装置１１０_ｉにそれぞれ含まれる、判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０、１１５_１、１１５_ｉは、
【００５２】
【数４】
2019111319.tif 000006
を計算する。計算を終えた後、判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０、１１５_１、１１５_ｉは、それぞれ判定結果［ｒｅｓ］_Ｂ０、［ｒｅｓ］_Ｂ１、［ｒｅｓ］_Ｂｉをデータ記憶部１０６_０、１１６_１、１１６_ｉに記憶する。なお、
【００５３】
【数５】
2019111319.tif 000007
の計算を実行する回路の深さはＬｏｇ（L）となる。
【００５４】
（ステップＡ９）
等号判定の結果を得る場合、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１および第ｉの秘密計算サーバ装置１１０_ｉにそれぞれ含まれる、秘密分散データ復元部１０４_０、１１４_１、１１４_ｉは、それぞれのデータ記憶部１０６_０、１１６_１、１１６_ｉから、それぞれ判定結果［ｒｅｓ］_Ｂ０、［ｒｅｓ］_Ｂ１、［ｒｅｓ］_Ｂｉを取り出し、外部のサーバ装置に送信する。同時に秘密分散データ復元部１０４_０、１１４_１、１１４_ｉは、外部のサーバ装置より得られた判定結果［ｒｅｓ］_Ｂｊを用いて、ａ＝ｂが成り立つか否かの判定結果を復元する。
【００５５】
以上、説明した本発明の第１の実施形態においては、以下に記載するような効果を奏する。
【００５６】
第１の効果は、秘密等号判定に要するコストの内、秘密分散の方法に依らず、通信ラウンド数に関してＯ（Ｌｏｇ（L））に抑えることができるというものである。これは、通信ラウンド数の内訳が、秘密分散データの分散に要する通信ラウンドと、判定結果［ｒｅｓ］_Ｂの計算に要する通信ラウンドのみで構成されるためである。特に秘密分散データの分散に関して、ステップＢ６、ステップＣ７を加えることにより、非特許文献２と異なり、非特許文献２における加法秘密分散法に依存することなく、本第１の実施形態は実施可能である。これにより、構成要素の改善によって、秘密等号判定に要するコストの内、通信ラウンド数に関してＯ（Ｌｏｇ（L））に抑えたまま、通信量を低減することができる。たとえば、非特許文献５で本第１の実施形態を実施した場合、通信ラウンド数は（Ｌｏｇ（L）＋２）回、通信量は（１２L−３）ｂｉｔとなる。非特許文献２が秘密等号判定を行った場合、通信ラウンド数は（Ｌｏｇ（L）＋１）回、通信量は（１７L−１５）ｂｉｔなので、非特許文献５によって本第１の実施形態を実施した場合の方が、通信量は低減される。
【００５７】
（第２の実施の形態）
続いて、図８乃至図１６を参照して、本発明の第２の実施形態に係る秘密等号判定システムついて説明する。本発明の第２の実施形態に係る秘密等号判定システムは、上述した第１の実施形態に係る秘密等号判定システムの変形例である。以下、本第２の実施形態において、第１の実施形態において既に説明した部分と同様な機能を有する部分には同一符号を付し、説明を省略する。
【００５８】
図８は、第２の実施形態による秘密等号判定システムの機能構成例を示すブロック図である。
【００５９】
図８を参照すると、本発明の第２の実施形態による秘密等号判定システムは、後述する図９で参照される秘密分散プロキシ装置２００と、後述する図１０で参照される乱数生成サーバ装置２１０_０と、後述する図１１で参照されるマスク値復元サーバ装置２２０_１と、後述する図１２で参照される第２乃至第ｎ（ｎは２以上の整数）の秘密計算サーバ装置２２０_２、・・・、２２０_ｎから成る。第２の実施形態による秘密等号判定システムにおいて、秘密分散プロキシ装置２００は、乱数生成サーバ装置２１０_０とマスク値復元サーバ装置２２０_１と第２乃至第ｎの秘密計算サーバ装置２２０_２〜２２０_ｎと、ネットワーク経由で通信可能に接続されている。また、乱数生成サーバ装置２１０_０とマスク値復元サーバ装置２２０_１と第２乃至第ｎの秘密計算サーバ装置２２０_２〜２２０_ｎとは、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。
【００６０】
図９に示すように、秘密分散プロキシ装置２００は、秘密分散データ生成部２０１と、秘密分散データ復元部２０２と、を含む。秘密分散データ生成部２０１と各サーバ装置２１０_０、２２０_１、２２０_２〜２２０_ｎとはネットワーク経由で通信可能に接続されている。秘密分散データ復元部２０２と各サーバ装置２１０_０、２２０_１、２２０_２〜２２０_ｎとはネットワーク経由で通信可能に接続されている。
【００６１】
図１０に示すように、乱数生成サーバ装置２１０_０は、乱数生成部１０１_０とシェア加算部１０２_０と秘密分散データ生成部位１０３_０と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０とデータ記憶部２１６_０と、を含む。シェア加算部１０２_０は、マスク値復元サーバ装置２２０_０とネットワーク経由で通信可能に接続されている。秘密分散データ生成部１０３_０と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０とは、自身と異なる各外部のサーバ装置２２０_１、２２０_２、・・・、２２０_ｎとネットワーク経由で通信可能に接続されている。データ記憶部２１６_０は、外部秘密分散プロキシ装置２００および外部のマスク値復元サーバ装置２２０_１とネットワーク経由で通信可能に接続されている。乱数生成部１０１_０は、シェア加算部１０２_０および秘密分散データ生成部１０３_０と通信可能に接続されている。データ記憶部２１６_０は、シェア加算部１０２_０、秘密分散データ生成部１０３_０および判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０と通信可能に接続されている。
【００６２】
図１１に示すように、マスク値復元サーバ装置２２０_１は、秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_１とデータ記憶部２２６_１と、を含む。秘密分散データ生成部１１３_１と秘密分散データ生成部１１４_１と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉとは、自身と異なる各外部のサーバ装置２２０_０、２２０_２、・・・、２２０_ｎとネットワーク経由で通信可能に接続されている。データ記憶部２２６_１は、外部の秘密分散プロキシ装置２００および外部の乱数生成サーバ装置２１０_０とネットワーク経由で通信可能に接続されている。データ記憶部２２６_１は、秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_１と通信可能に接続されている。秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１とは通信可能に接続されている。
【００６３】
図１２に示すように、第ｉの秘密計算サーバ装置２２０_ｉ（２≦ｉ≦ｎ）は、第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと、第ｉのデータ記憶部２２６_ｉと、を含む。判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉとデータ記憶部２２６_ｉとは、外部の秘密分散プロキシ装置２００および各外部のサーバ装置２１０_０、２２０_１、２２０_ｉ’（ｉ’≠ｉ，２≦ｉ’≦ｎ）とネットワーク経由で通信可能に接続されている。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと第ｉのデータ記憶部２２６_ｉとは通信可能に接続されている。
【００６４】
本第２の実施形態による秘密等号判定システム、秘密分散プロキシ装置２００、乱数生成サーバ装置２１０_０、マスク値復元サーバ装置２２０_１および第２乃至第ｎの秘密計算サーバ装置２２０_２、・・・、２２０_ｎにおいては、図示されない入力装置から秘密分散プロキシ装置２００に入力されたａ，ｂ、あるいは、データ記憶部２１６_０、２２６_１、２２６_２、・・・、２２６_ｎに記憶された秘密分散データ［ａ］_Ｒ，［ｂ］_Ｒに対し、その入力や計算過程の値からａ，ｂの値を知られることなく、ａ＝ｂが成り立つか否かの判定結果の秘密分散データを計算し、データ記憶部２１６_０、２２６_１、２２６_２、・・・、２２６_ｎにそれぞれ記憶する。前記判定結果の秘密分散データは、データ記憶部２１６_０、２２６_１、２２６_２、・・・、２２６_ｎに記憶した後、秘密分散プロキシ装置２００にそれぞれ渡し、復元結果を得ても良い。
【００６５】
次に、本発明の第２の実施形態における秘密等号判定システム、秘密分散プロキシ装置２００、乱数生成サーバ装置２１０_０、マスク値復元サーバ装置２２０_１および第ｉの秘密計算サーバ装置２２０_ｉの動作について詳細に説明する。図１３は、秘密分散プロキシ装置２００の動作例を示すフローチャートである。図１４は、乱数生成サーバ装置２１０_０の動作例を示すフローチャートである。図１５は、マスク値復元サーバ装置２２０_１の動作例を示すフローチャートである。図１６は、第ｉの秘密計算サーバ装置２２０_ｉの動作例を示すフローチャートである。
【００６６】
（ステップＸ１）
図１３を参照すると、秘密分散プロキシ装置２００の動作として、まず、入力（第１の被演算子）ａを図示されない入力装置から秘密分散データ生成部２０１に渡す。秘密分散データ生成部２０１は、第１の被演算子に関するｒｉｎｇのシェア［ａ］_Ｒを生成する。次に、秘密分散データ生成部２０１は、第１の被演算子に関するｒｉｎｇのシェア［ａ］_Ｒ０，［ａ］_Ｒ１，［ａ］_Ｒｉを、それぞれ、乱数生成サーバ装置２１０_０に含まれるデータ記憶部２１６_０、マスク値復元サーバ装置２２０_１に含まれるデータ記憶部２２６_１、第ｉの秘密計算サーバ装置２２０_ｉ（２≦ｉ≦ｎ）に含まれるデータ記憶部２２６_ｉに渡す。データ記憶部２１６_０、２２６_１、２２６_ｉは、それぞれ、第１の被演算子に関するｒｉｎｇのシェア［ａ］_Ｒ０，［ａ］_Ｒ１，[ａ]_Ｒｉを記憶する。入力（第２の被演算子）ｂに関しても、秘密分散プロキシ装置２００と外部のサーバ装置２１０_０、２２０_１、２２０_ｉが、同様に処理する。ここで、ステップＸ１は計算を開始する際のみに生じるステップである。よって、秘密計算プロトコルの過程で生じたｒｉｎｇのシェアについて秘密等号判定を行う場合、ステップＸ１は発生しない。
【００６７】
（ステップＡ２）
図１４乃至図１６を参照して、ステップＡ２は、第１の実施形態による各サーバ装置の動作におけるステップＡ２と等しい。ただし、乱数生成サーバ装置２１０_０、マスク値復元サーバ装置２２０_１、第ｉの秘密計算サーバ装置２２０_ｉは、それぞれのデータ記憶部２１６_０、２２６_１、２２６_ｉに、それぞれ２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒ０、［ａ−ｂ］_Ｒ１、［ａ−ｂ］_Ｒｉを保存する。
【００６８】
（ステップＢ３）
図１４を参照すると、第２の実施形態による乱数生成サーバ装置２１０_０の動作におけるステップＢ３は、第１の実施の形態による乱数生成サーバ装置１００_０の動作におけるステップＢ３と等しい。
【００６９】
（ステップＢ４）
第２の実施形態による乱数生成サーバ装置２１０_０の動作におけるステップＢ４は、第１の実施の形態による乱数生成サーバ装置１００_０の動作におけるステップＢ４と等しい。ただし、シェア加算部１０２_２は、マスクされた秘密分散データ［ａ−ｂ＋ｒ］_Ｒ０（＝［ａ−ｂ］_Ｒ０＋ｒ）を、マスク値復元サーバ装置２２０_１に含まれる秘密分散データ復元部２２４_１に送る。
【００７０】
（ステップＣ５）
図１５を参照すると、第２の実施の形態によるマスク値復元サーバ装置２２０_１の動作におけるステップＣ５は、第１の実施の形態によるマスク値復元サーバ装置１１０_１の動作におけるステップＣ５と等しい。ただし、２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒ１はデータ記憶部２２６_１から取り出される。また、２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］Ｒｉは第ｉの秘密計算サーバ装置１１０_ｉ（２≦ｉ≦ｎ）から取り出される。
【００７１】
（ステップＣ６）
第２の実施の形態によるマスク値復元サーバ装置２２０_１の動作におけるステップＣ６は、第１の実施の形態によるマスク値復元サーバ装置１１０_１の動作におけるステップＣ６と等しい。ただし、復元した値のｂｉｔのシェア［（ａ−ｂ＋ｒ）_ｔ］_Ｂ０，［（ａ−ｂ＋ｒ）_ｔ］_Ｂ１，［（ａ−ｂ＋ｒ）_ｔ］_Ｂｉは、それぞれ、乱数生成サーバ装置２１０_０、マスク値復元サーバ装置２２０_１、第ｉの秘密計算サーバ装置２２０_ｉに送信され、それぞれのデータ記憶部２１６_０、２２６_１、２２６_ｉに保存される。
【００７２】
（ステップＢ７）
図１４に戻って、第２の実施の形態による乱数生成サーバ装置２１０_０の動作におけるステップＢ７は、第１の実施の形態による乱数生成サーバ装置１００_０の動作におけるステップＢ７と等しい。ただし、乱数のｂｉｔのシェア［ｒ_ｔ］_Ｂ０，［ｒ_ｔ］_Ｂ１，［ｒ_ｔ］_Ｂｉは、それぞれ、乱数生成サーバ装置２１０_０、マスク値復元サーバ装置２２０_１、および第ｉの秘密計算サーバ装置２２０_ｉに送られ、それぞれのデータ記憶部２１６_０、２２６_１、２２６_ｉに保存される。
【００７３】
（ステップＡ８）
図１４乃至図１６を参照すると、第２の実施の形態による乱数生成サーバ装置２１０_０、マスク値復元サーバ装置２２０_１、第ｉの秘密計算サーバ装置２２０_ｉの動作におけるステップＡ８は、第１の実施の形態による乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１、第ｉの秘密計算サーバ装置１１０_ｉの動作におけるステップＡ８と等しい。ただし、判定結果［ｒｅｓ］_Ｂ０、［ｒｅｓ］_Ｂ１、［ｒｅｓ］_Ｂｉは、それぞれ、データ記憶部２１６_０、２２６_１、２２６_ｉに記憶される。
【００７４】
（ステップＸ９）
図１３に戻って、等号判定の結果を得る場合、秘密分散プロキシ装置２００に含まれる秘密分散データ復元部２０２は、データ記憶部２１６_０、２２６_１、２２６_ｉから、判定結果［ｒｅｓ］_Ｂ０、［ｒｅｓ］_Ｂ１、［ｒｅｓ］_Ｂｉをそれぞれ取り出し、等号判定の結果を復元する。
【００７５】
以上、説明した本発明の第２の実施形態においては、第１の実施形態で述べた第１の効果の他に以下に記載するような第２の効果を奏する。
【００７６】
第２の効果は、少ない構成モジュールで乱数生成サーバ装置および第ｉの秘密計算サーバ装置が構成されているということである。具体的には、第１の実施形態における乱数生成サーバ装置１００_０より、秘密分散データ復元部１０４_０の分だけ、乱数生成サーバ装置２１０_０は少ない構成モジュールで構成される。また、第１の実施形態における第ｉの秘密計算サーバ装置１１０_ｉより、秘密分散データ生成部１１３_ｉと秘密分散データ復元部１１４_ｉの分だけ、第ｉの秘密計算サーバ装置２２０_ｉは少ない構成モジュールで構成される。ただし、秘密分散プロキシ装置２００が必要なことに注意する。
【００７７】
なお、上記の秘密等号判定システムや各サーバ装置において行われる判定方法は、ハードウェア、ソフトウェア又はこれらの組み合わせにより実現することができる。ここで、ソフトウェアによって実現されるとは、コンピュータが秘密等号判定プログラムを読み込んで実行することにより実現されることを意味する。
【００７８】
秘密等号判定プログラムは、様々なタイプの非一時的なコンピュータ可読媒体(non-transitory computer readable medium)を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体(tangible storage medium)を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えば、フレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば、光磁気ディスク）、ＣＤ−ＲＯＭ(Read Only Memory)、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ(Programmable ROM)、ＥＰＲＯＭ(Erasable PROM)、フラッシュＲＯＭ、ＲＡＭ(random access memory)）を含む。また、秘密等号判定プログラムは、様々なタイプの一時的なコンピュータ可読媒体(transitory computer readable medium)によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、秘密等号判定プログラムをコンピュータに供給できる。
【００７９】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００８０】
上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００８１】
（付記１）乱数を生成する乱数生成部と、
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する秘密分散データ生成部と、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するシェア加算部と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する秘密分散データ復元部と、
を備える乱数生成サーバ装置。
【００８２】
（付記２）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、復元した値のｂｉｔのシェアを生成する秘密分散データ生成部と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、前記復元した値を出力する秘密分散データ復元部と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備え、
前記秘密分散データ復元部は、前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する、マスク値復元サーバ装置。
【００８３】
（付記３）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する秘密分散データ生成部と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する秘密分散データ復元部と、
を備える秘密計算サーバ装置。
【００８４】
（付記４）付記１に記載の乱数生成サーバ装置と、付記２に記載のマスク値復元サーバ装置と、付記３に記載の秘密計算サーバ装置の複数台とが、ネットワークで接続されて成る秘密等号判定システム。
【００８５】
（付記５）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数を生成するステップと、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するステップと、
前記乱数のｂｉｔのシェアを生成するステップと、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含む乱数生成サーバ装置での秘密等号判定方法。
【００８６】
（付記６）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力するステップと、
該復元した値のｂｉｔのシェアを生成するステップと、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含むマスク値復元サーバ装置での秘密等号判定方法。
【００８７】
（付記７）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する秘密分散データ生成部と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含む秘密計算サーバ装置での秘密等号判定方法。
【００８８】
（付記８）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数を生成する処理と、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、
前記乱数のｂｉｔのシェアを生成する処理と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
を乱数生成サーバ装置のコンピュータに実行させる秘密等号判定プログラムを記録した記録媒体。
【００８９】
（付記９）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力する処理と、
該復元した値のｂｉｔのシェアを生成する処理と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
をマスク値復元サーバ装置のコンピュータに実行させる秘密等号判定プログラムを記録した記録媒体。
【００９０】
（付記１０）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
を秘密計算サーバ装置のコンピュータに実行させる秘密等号判定プログラムを記録した記録媒体。
【００９１】
（付記１１）２つ被演算子を秘密分散して、２つの被演算子に関するｒｉｎｇのシェアを生成し、該生成した２つの被演算子に関するｒｉｎｇのシェアを複数のサーバ装置へ送信する秘密分散データ生成部と、
前記複数のサーバ装置から受け取った判定結果に基づいて、等号判定の結果を復元する秘密分散データ復元部と、
を備える秘密分散プロキシ装置。
【００９２】
（付記１２）乱数を生成する乱数生成部と、
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する秘密分散データ生成部と、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するシェア加算部と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備える乱数生成サーバ装置。
【００９３】
（付記１３）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、復元した値のｂｉｔのシェアを生成する秘密分散データ生成部と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、前記復元した値を出力する秘密分散データ復元部と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備えるマスク値復元サーバ装置。
【００９４】
（付記１４）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する秘密分散データ生成部と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備える秘密計算サーバ装置。
【００９５】
（付記１５）付記１１に記載の秘密分散プロキシ装置と、付記１２に記載の乱数生成サーバ装置と、付記１３に記載のマスク値復元サーバ装置と、付記１４に記載の秘密計算サーバ装置の複数台とが、ネットワークで接続されて成る秘密等号判定システム。
【００９６】
（付記１６）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数を生成する乱数生成部と、
前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信するステップと、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するステップと、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含む乱数生成サーバ装置での秘密等号判定方法。
【００９７】
（付記１７）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力するステップと、
前記復元した値のｂｉｔのシェアを生成するステップと、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含むマスク値復元サーバ装置での秘密等号判定方法。
【００９８】
（付記１８）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含む秘密計算サーバ装置での秘密等号判定方法。
【００９９】
（付記１９）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数を生成する処理と、
前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する処理と、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
を乱数生成サーバ装置のコンピュータに実現させる秘密等号判定プログラムを記録した記録媒体。
【０１００】
（付記２０）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力する処理と、
前記復元した値のｂｉｔのシェアを生成する処理と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
をマスク値復元サーバ装置のコンピュータに実現させる秘密等号判定プログラムを記録した記録媒体。
【０１０１】
（付記２１）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
を秘密計算サーバ装置のコンピュータに実現させる秘密等号判定プログラムを記録した記録媒体。
【産業上の利用可能性】
【０１０２】
本発明によれば、たとえば、データベースにおける文字列処理で生じる秘密等号判定を、秘密分散の方法に依らず、通信ラウンド数をＯ（Ｌｏｇ（L））に抑えて実行できる。このため、秘密等号判定や秘密等号判定を用いる上位プロトコルに関して、構成要素の改善により通信量を削減することができる。
【符号の説明】
【０１０３】
１００_０  乱数生成サーバ装置
１０１_０  乱数生成部
１０２_０  シェア加算部
１０３_０  秘密分散データ生成部
１０４_０  秘密分散データ復元部
１０５_０  判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部
１０６_０  データ記憶部
１１０_１  マスク値復元サーバ装置
１１３_１  秘密分散データ生成部
１１４_１  秘密分散データ復元部
１１５_１  判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部
１１６_１  データ記憶部
１１０_ｉ  秘密計算サーバ装置
１１３_ｉ  秘密分散データ生成部
１１４_ｉ  秘密分散データ復元部
１１５_ｉ  判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部
１１６_ｉ  データ記憶部
２００     秘密分散プロキシ装置
２０１     秘密分散データ生成部
２０２     秘密分散データ復元部
２１０_０  乱数生成サーバ装置
２１６_０  データ記憶部
２２０_１  マスク値復元サーバ装置
２２６_１  データ記憶部
２２０_ｉ  秘密計算サーバ装置
２２６_ｉ  データ記憶部
【図１】
2019111319.tif 000008
【図２】
2019111319.tif 000009
【図３】
2019111319.tif 000010
【図４】
2019111319.tif 000011
【図５】
2019111319.tif 000012
【図６】
2019111319.tif 000013
【図７】
2019111319.tif 000014
【図８】
2019111319.tif 000015
【図９】
2019111319.tif 000016
【図１０】
2019111319.tif 000017
【図１１】
2019111319.tif 000018
【図１２】
2019111319.tif 000019
【図１３】
2019111319.tif 000020
【図１４】
2019111319.tif 000021
【図１５】
2019111319.tif 000022
【図１６】
2019111319.tif 000023
【手続補正書】
【提出日】令和2年6月2日(2020.6.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
乱数を生成する乱数生成部と、
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する秘密分散データ生成部と、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するシェア加算部と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する秘密分散データ復元部と、
を備える乱数生成サーバ装置。
【請求項２】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、復元した値のｂｉｔのシェアを生成する秘密分散データ生成部と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、前記復元した値を出力する秘密分散データ復元部と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備え、
前記秘密分散データ復元部は、前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する、マスク値復元サーバ装置。
【請求項３】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する秘密分散データ生成部と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する秘密分散データ復元部と、
を備える秘密計算サーバ装置。
【請求項４】
請求項１に記載の乱数生成サーバ装置と、請求項２に記載のマスク値復元サーバ装置と、請求項３に記載の秘密計算サーバ装置の複数台とが、ネットワークで接続されて成る秘密等号判定システム。
【請求項５】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数を生成するステップと、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するステップと、
前記乱数のｂｉｔのシェアを生成するステップと、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含む乱数生成サーバ装置での秘密等号判定方法。
【請求項６】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力するステップと、
該復元した値のｂｉｔのシェアを生成するステップと、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含むマスク値復元サーバ装置での秘密等号判定方法。
【請求項７】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含む秘密計算サーバ装置での秘密等号判定方法。
【請求項８】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数を生成する処理と、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、
前記乱数のｂｉｔのシェアを生成する処理と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
を乱数生成サーバ装置のコンピュータに実行させる秘密等号判定プログラム。
【請求項９】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力する処理と、
該復元した値のｂｉｔのシェアを生成する処理と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
をマスク値復元サーバ装置のコンピュータに実行させる秘密等号判定プログラム。
【請求項１０】
２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
を秘密計算サーバ装置のコンピュータに実行させる秘密等号判定プログラム。
【請求項１１】
２つ被演算子を秘密分散して、２つの被演算子に関するｒｉｎｇのシェアを生成し、該生成した２つの被演算子に関するｒｉｎｇのシェアを複数のサーバ装置へ送信する秘密分散データ生成部と、
前記複数のサーバ装置から受け取った判定結果に基づいて、等号判定の結果を復元する秘密分散データ復元部と、
を備える秘密分散プロキシ装置。
【請求項１２】
乱数を生成する乱数生成部と、
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する秘密分散データ生成部と、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するシェア加算部と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備える乱数生成サーバ装置。
【請求項１３】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成すると共に、復元した値のｂｉｔのシェアを生成する秘密分散データ生成部と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、前記復元した値を出力する秘密分散データ復元部と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備えるマスク値復元サーバ装置。
【請求項１４】
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部
を備える秘密計算サーバ装置。
【請求項１５】
請求項１１に記載の秘密分散プロキシ装置と、請求項１２に記載の乱数生成サーバ装置と、請求項１３に記載のマスク値復元サーバ装置と、請求項１４に記載の秘密計算サーバ装置の複数台とが、ネットワークで接続されて成る秘密等号判定システム。
【請求項１６】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数を生成するステップと、
前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信するステップと、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するステップと、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含む乱数生成サーバ装置での秘密等号判定方法。
【請求項１７】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力するステップと、
前記復元した値のｂｉｔのシェアを生成するステップと、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含むマスク値復元サーバ装置での秘密等号判定方法。
【請求項１８】
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップ
を含む秘密計算サーバ装置での秘密等号判定方法。
【請求項１９】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数を生成する処理と、
前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する処理と、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
を乱数生成サーバ装置のコンピュータに実現させる秘密等号判定プログラム。
【請求項２０】
秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力する処理と、
前記復元した値のｂｉｔのシェアを生成する処理と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
をマスク値復元サーバ装置のコンピュータに実現させる秘密等号判定プログラム。
【請求項２１】
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理
を秘密計算サーバ装置のコンピュータに実現させる秘密等号判定プログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は秘密計算プロトコルに関し、特に効率よく秘密等号判定を行うことができる秘密等号判定システム、秘密等号判定方法および秘密等号判定プログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
秘密情報aを、pを法とする多項式f_a(x)を用いてＮ台のサーバ装置で分散するときに生成される、秘密情報aの分散情報を、[a]p=(f_a(1), f_a(2), …, f_a(N))と書くことにする。このとき、識別子i（１≦i≦Ｎ）を持つ第iのサーバ装置にf_a(i)が保持されているものとする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
ここで、非特許文献２の秘密等号判定による通信ラウンド数は（Ｌｏｇ（L）＋１）回、通信量は(１７L−１５)ビットとなる。なお、Ｌｏｇの底は２であり、Lは環の位数のビット長である。非特許文献２では、秘密等号判定の通信ラウンド数を抑えるために、非特許文献２で用いられる加法秘密分散法に依存した技法を用いている。具体的には値ｖを秘密分散する際に、ある参加者の秘密分散データをｖとし、残りの参加者の秘密分散データを０とすることで、通信ラウンド数を削減している。このため、非特許文献２の秘密等号判定の方法を非特許文献５によって実施することはできない。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
上述の課題に鑑み、本発明の一態様は、ネットワークで接続された乱数生成サーバ装置とマスク値復元サーバ装置と複数の秘密計算サーバ装置とを備える秘密等号判定システムであって、
前記乱数生成サーバ装置は、乱数を生成する乱数生成部と；２つの被演算子の差の値に関する第１のｒｉｎｇのシェアを生成すると共に、前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する第１の秘密分散データ生成部と；前記第１のｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データを前記マスク値復元サーバ装置へ送信するシェア加算部と；前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて第１の秘密等号判定を行い、第１の判定結果を他のサーバ装置へ送信する第１の判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と；前記第１の判定結果と他のサーバ装置からの判定結果とに基づいて、前記第１の判定結果のｂｉｔのシェアを復元する秘密分散データ復元部と；を有し、
前記マスク値復元サーバ装置は、２つの被演算子の差の値に関する第２のｒｉｎｇのシェアを生成すると共に、復元した値のｂｉｔのシェアを生成する第２の秘密分散データ生成部と；前記第２のｒｉｎｇのシェアと、前記複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、前記乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、前記復元した値を出力する第２の秘密分散データ復元部と；前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて第２の秘密等号判定を行い、第２の判定結果を他のサーバ装置へ送信する第２の判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と；を備え、前記第２の秘密分散データ復元部は、前記第２の判定結果と他のサーバ装置からの判定結果に基づいて、前記第２の判定結果のｂｉｔのシェアを復元し、
前記秘密計算サーバ装置の各々は、２つの被演算子の差の値に関する第３のｒｉｎｇのシェアを生成する第３の秘密分散データ生成部と；乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて第３の秘密等号判定を行い、第３の判定結果を他のサーバ装置へ送信する第３の判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と；前記第３の判定結果と他のサーバ装置からの判定結果に基づいて、前記第３の判定結果のｂｉｔのシェアを復元する第３の秘密分散データ復元部と；を有することを特徴とする秘密等号判定システムである。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
さらに、本発明の別の態様は、２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、乱数を生成する処理と、前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、前記乱数のｂｉｔのシェアを生成する処理と、前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、を乱数生成サーバ装置のコンピュータに実行させる秘密等号判定プログラムである。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
図４に示すように、第ｉの秘密計算サーバ装置１１０_ｉ（２≦ｉ≦ｎ）は、第ｉの秘密分散データ生成部１１３_ｉと、第ｉの秘密分散データ復元部１１４_ｉと、第ｉの判定ｂｉｔ-ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと、第ｉのデータ記憶部１１６_ｉと、を含む。第ｉの秘密分散データ生成部１１３_ｉと第ｉの秘密分散データ復元部１１４_ｉと第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉは、それぞれ自身が含まれるサーバ装置と異なるサーバ装置とネットワーク経由で通信可能に接続されている。第ｉのデータ記憶部１１６_ｉは、第ｉの秘密分散データ生成部１１３_ｉと第ｉの秘密分散データ復元部１１４_ｉと第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと、それぞれ通信可能に接続されている。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】変更
【補正の内容】
【００３６】
このような構成の秘密等号判定システムにおいては、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１、第２乃至第ｎのサーバ装置１１０_２〜１１０_ｎの内のいずれかの装置が入力した値ａ，ｂ、あるいは、データ記憶部１０６_０、１１６_１、１１６_２〜１１６_ｎに記憶された秘密分散データ［ａ］_Ｒ，［ｂ］_Ｒに対し、その入力や計算過程の値からａ，ｂの値を知られることなく、ａ＝ｂが成り立つか否かの判定結果の秘密分散データを計算し、データ記憶部１０６_０、１１６_１、１１６_２〜１１６_ｎにそれぞれ記憶する。前記判定結果の秘密分散データは、データ記憶部１０６_０、１１６_１、１１６_２〜１１６_ｎに記憶した後、秘密分散データ復元部１０４_０、１１４_１、１１４_２〜１１４_ｎにそれぞれ渡し、復元結果を得ても良い。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００４８
【補正方法】変更
【補正の内容】
【００４８】
（ステップＣ５）
図６を参照すると、マスク値復元サーバ装置１１０_１に含まれる秘密分散データ復元部１１４_１は、データ記憶部１１６_１から２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒ１を取り出す。また、第ｉの秘密計算サーバ装置１１０_ｉ（２≦ｉ≦ｎ）から２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒｉを取り出す。このとき、データを復元するにあたり必要な秘密分散データの個数をｋとしたとき、［ａ−ｂ］Ｒｉを取り出す個数は（ｋ−２）個となる。秘密分散データ復元部１１４_１は、２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒ１と、（ｋ−２）個の２つの被演算子の差の値に関するｒｉｎｇのシェア［ａ−ｂ］_Ｒｉと、前記ステップＢ４にて送られてきたマスクされた秘密分散データ［ａ−ｂ＋ｒ］_Ｒ０とを用いて、マスクされた値ａ−ｂ＋ｒを復元する。復元後、秘密分散データ復元部１１４_１は、復元した値ａ−ｂ＋ｒを秘密分散データ生成部１１３_１に渡す。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
（ステップＣ６）
秘密分散データ生成部１１３_１は、前記ステップＣ５にて渡された復元した値ａ−ｂ＋ｒの各ｂｉｔに対し、ｂｉｔのシェアを生成する。ここで、復元した値ａ−ｂ＋ｒのｔ−ｂｉｔ目（ｔ＝０，．．．，L−1）の値を（ａ−ｂ＋ｒ）_ｔとする。このとき、復元した値ａ−ｂ＋ｒの各ｂｉｔに対するｂｉｔのシェアとは［（ａ−ｂ＋ｒ）_ｔ］_Ｂを指す。［（ａ−ｂ＋ｒ）_ｔ］_Ｂを生成した後、秘密分散データ生成部１１３_１は、添え字ｉに対応する外部の第ｉの秘密計算サーバ装置１１０_ｉに復元した値のｂｉｔのシェア［（ａ−ｂ＋ｒ）_ｔ］_Ｂｉを送信する。つまり、乱数生成サーバ装置１００_０、マスク値復元サーバ装置１１０_１、および第ｉの秘密計算サーバ装置１１０_ｉは、それぞれのデータ記憶部１０６_０、１１６_１、１１６_ｉに、それぞれ復元した値のｂｉｔのシェア［（ａ−ｂ＋ｒ）_ｔ］_Ｂ０、［（ａ−ｂ＋ｒ）_ｔ］_Ｂ１、［（ａ−ｂ＋ｒ）_ｔ］_Ｂｉを保存する。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００６１
【補正方法】変更
【補正の内容】
【００６１】
図１０に示すように、乱数生成サーバ装置２１０_０は、乱数生成部１０１_０とシェア加算部１０２_０と秘密分散データ生成部１０３_０と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０とデータ記憶部２１６_０と、を含む。シェア加算部１０２_０は、マスク値復元サーバ装置２２０_１とネットワーク経由で通信可能に接続されている。秘密分散データ生成部１０３_０と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０とは、自身と異なる各外部のサーバ装置２２０_１、２２０_２、・・・、２２０_ｎとネットワーク経由で通信可能に接続されている。データ記憶部２１６_０は、外部秘密分散プロキシ装置２００および外部のマスク値復元サーバ装置２２０_１とネットワーク経由で通信可能に接続されている。乱数生成部１０１_０は、シェア加算部１０２_０および秘密分散データ生成部１０３_０と通信可能に接続されている。データ記憶部２１６_０は、シェア加算部１０２_０、秘密分散データ生成部１０３_０および判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０５_０と通信可能に接続されている。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
図１１に示すように、マスク値復元サーバ装置２２０_１は、秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_１とデータ記憶部２２６_１と、を含む。秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_１とは、自身と異なる各外部のサーバ装置２２０_０、２２０_２、・・・、２２０_ｎとネットワーク経由で通信可能に接続されている。データ記憶部２２６_１は、外部の秘密分散プロキシ装置２００および外部の乱数生成サーバ装置２１０_０とネットワーク経由で通信可能に接続されている。データ記憶部２２６_１は、秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_１と通信可能に接続されている。秘密分散データ生成部１１３_１と秘密分散データ復元部１１４_１とは通信可能に接続されている。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
図１２に示すように、第ｉの秘密計算サーバ装置２２０_ｉ（２≦ｉ≦ｎ）は、第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと、第ｉのデータ記憶部２２６_ｉと、を含む。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと第ｉのデータ記憶部２２６_ｉとは、外部の秘密分散プロキシ装置２００および各外部のサーバ装置２１０_０、２２０_１、２２０_ｉ’（ｉ’≠ｉ，２≦ｉ’≦ｎ）とネットワーク経由で通信可能に接続されている。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１１５_ｉと第ｉのデータ記憶部２２６_ｉとは通信可能に接続されている。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
（ステップＢ４）
第２の実施形態による乱数生成サーバ装置２１０_０の動作におけるステップＢ４は、第１の実施の形態による乱数生成サーバ装置１００_０の動作におけるステップＢ４と等しい。ただし、シェア加算部１０２_２は、マスクされた秘密分散データ［ａ−ｂ＋ｒ］_Ｒ０（＝［ａ−ｂ］_Ｒ０＋ｒ）を、マスク値復元サーバ装置２２０_１に含まれる秘密分散データ復元部１１４_１に送る。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００８７
【補正方法】変更
【補正の内容】
【００８７】
（付記７）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信するステップと、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元するステップと、
を含む秘密計算サーバ装置での秘密等号判定方法。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００８８
【補正方法】変更
【補正の内容】
【００８８】
（付記８）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数を生成する処理と、
前記ｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、
前記乱数のｂｉｔのシェアを生成する処理と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
を乱数生成サーバ装置のコンピュータに実行させる秘密等号判定プログラム。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００８９
【補正方法】変更
【補正の内容】
【００８９】
（付記９）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力する処理と、
該復元した値のｂｉｔのシェアを生成する処理と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
をマスク値復元サーバ装置のコンピュータに実行させる秘密等号判定プログラム。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００９０
【補正方法】変更
【補正の内容】
【００９０】
（付記１０）２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を他のサーバ装置へ送信する処理と、
前記判定結果と他のサーバ装置からの判定結果とに基づいて、前記判定結果のｂｉｔのシェアを復元する処理と、
を秘密計算サーバ装置のコンピュータに実行させる秘密等号判定プログラム。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００９４
【補正方法】変更
【補正の内容】
【００９４】
（付記１４）乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部
を備える秘密計算サーバ装置。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００９６
【補正方法】変更
【補正の内容】
【００９６】
（付記１６）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成するステップと、
乱数を生成するステップと、
前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信するステップと、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信するステップと、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信するステップと、
を含む乱数生成サーバ装置での秘密等号判定方法。
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００９９
【補正方法】変更
【補正の内容】
【００９９】
（付記１９）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
乱数を生成する処理と、
前記乱数のｂｉｔのシェアを生成し、前記乱数のｂｉｔのシェアを他のサーバ装置へ送信する処理と、
前記２つの被演算子の差の値に関するｒｉｎｇのシェアに前記乱数を加えて、マスクされた秘密分散データを生成し、該マスクされた秘密分散データをマスク値復元サーバ装置へ送信する処理と、
前記乱数のｂｉｔのシェアと、前記マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
を乱数生成サーバ装置のコンピュータに実現させる秘密等号判定プログラム。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】０１００
【補正方法】変更
【補正の内容】
【０１００】
（付記２０）秘密分散プロキシ装置から受け取った２つの被演算子に関するｒｉｎｇのシェアから、前記２つの被演算子の差の値に関するｒｉｎｇのシェアを生成する処理と、
前記ｒｉｎｇのシェアと、複数の秘密計算サーバ装置から取り出した複数のｒｉｎｇのシェアと、乱数生成サーバ装置から受け取ったマスクされた秘密分散データとを用いて、マスクされた値を復元し、復元した値を出力する処理と、
前記復元した値のｂｉｔのシェアを生成する処理と、
前記乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、前記復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理と、
をマスク値復元サーバ装置のコンピュータに実現させる秘密等号判定プログラム。
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
（付記２１）乱数生成サーバ装置から受け取った乱数のｂｉｔのシェアと、マスク値復元サーバ装置から受け取った復元した値のｂｉｔのシェアとを用いて秘密等号判定を行い、判定結果を前記秘密分散プロキシ装置へ送信する処理
を秘密計算サーバ装置のコンピュータに実現させる秘密等号判定プログラム。
【手続補正２５】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2019111319.tif 000024
【手続補正２６】
【補正対象書類名】図面
【補正対象項目名】図１０
【補正方法】変更
【補正の内容】
【図１０】
2019111319.tif 000025
【国際調査報告】
2019111319.tif 000026
2019111319.tif 000027
2019111319.tif 000028
2019111319.tif 000029