(57)【要約】秘密分散の方法に依らず、位数２の環上で行う時と位数が２より大きい環上で行う時とで、通信ラウンド数に差が生じずに実行できるサーバ装置、秘密等号判定システム、秘密等号判定方法および秘密等号判定プログラムを提供する。本発明によるサーバ装置は、秘密分散データ生成部とデータ記憶部とマスク部と乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と乱数シェア生成部と判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と秘密分散データ復元部とを備える。秘密分散データ生成部は、秘密分散データを生成する。データ記憶部は、秘密分散データを記憶する。マスク部は、乱数の秘密分散データを用いて、ある秘密分散データをマスクする。乱数シェア生成部は、乱数を秘密分散した乱数シェアを生成する。乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部は、乱数を秘密分散した値同士の論理積計算を他の計算と並行して行う。判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部は、乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部が出力した値を用いて秘密等号判定を行う。
2019111318.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）回となる。つまり、引数に位数が２より大きい環の秘密分散のシェアを取ったとき、秘密等号判定における通信ラウンド数で１回分のロスが生じていることとなる。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】Ａｄｉ  Ｓｈａｍｉｒ、“Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ、”  Ｃｏｍｍｕｎ．  ＡＣＭ  ２２（１１）、  ｐｐ．６１２−６１３、  １９７９．
【非特許文献２】Ｄａｎ  Ｂｏｇｄａｎｏｖ、Ｍａｒｇｕｓ  Ｎｉｉｔｓｏｏ、Ｔｏｍａｓ  Ｔｏｆｔ、Ｊａｎ  Ｗｉｌｌｅｍｓｏｎ、  “Ｈｉｇｈ−ｐｅｒｆｏｒｍａｎｃｅ  ｓｅｃｕｒｅ  ｍｕｌｔｉ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｆｏｒ  ｄａｔａ  ｍｉｎｉｎｇ  ａｐｐｌｉｃａｔｉｏｎｓ、”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ、１１（６）、４０３−４１８．
【非特許文献３】Ｔａｋａｓｈｉ  Ｎｉｓｈｉｄｅ、Ｋａｚｕｏ  Ｏｈｔａ、  “Ｍｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ  ｆｏｒ  Ｉｎｔｅｒｖａｌ，Ｅｑｕａｌｉｔｙ，ａｎｄ  Ｃｏｍｐａｒｉｓｏｎ  ｗｉｔｈｏｕｔ  Ｂｉｔ−Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  Ｐｒｏｔｏｃｏｌ、”  Ｉｎ  ＰＫＣ２００７、ＬＮＣＳ、ｖｏｌ．４４５０、ｐｐ．９０−１０４、Ｓｐｒｉｎｇｅｒ、Ｂｅｒｌｉｎ、Ｈｅｉｄｅｌｂｅｒｇ．
【非特許文献４】Ａｎｄｒｅｗ  Ｃ．Ｙａｏ、“Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｓｅｃｕｒｅ  ｃｏｍｐｕｔａｔｉｏｎｓ、”Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２１ｓｔ  Ａｎｎｕａｌ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  ｔｈｅ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、ｐｐ．１６０−１６４、１９８２．
【非特許文献５】Ｔｏｓｈｉｎｏｒｉ  Ａｒａｋｉ、Ｊｕｎ  Ｆｕｒｕｋａｗａ、Ｙｅｈｕｄａ  Ｌｉｎｄｅｌｌ、Ａｒｉｅｌ  Ｎｏｆ、Ｋａｚｕｍａ  Ｏｈａｒａ、“Ｈｉｇｈ−Ｔｈｒｏｕｇｈｐｕｔ  Ｓｅｍｉ−Ｈｏｎｅｓｔ  Ｓｅｃｕｒｅ  Ｔｈｒｅｅ−ｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ  ｗｉｔｈ  ａｎ  Ｈｏｎｅｓｔ  Ｍａｊｏｒｉｔｙ、”  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０１６  ＡＣＭ  ＳＩＧＳＡＣ  Ｃｏｎｆｅｒｅｎｅｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ、ｐｐ．８０５−８１７、ＡＣＭ．
【発明の概要】
【発明が解決しようとする課題】
【００２１】
このように、非特許文献２では、位数２の環上で秘密等号判定を行う時と位数が２より大きい環上で秘密等号判定を行う時とで、通信ラウンド数に差が生じ、後者の方が通信ラウンド数の点でコストが大きくなっていた。ラウンド数が増加すると、ネットワーク遅延が大きい通信環境では、性能の悪化が生じ得る。特に、等号判定を多用するような文字列処理を秘密計算プロトコルで実行する場合、秘密等号判定における通信ラウンド数の増加は、計算処理全体の性能低下を引き起こす恐れがある。一方で、非特許文献１、非特許文献３では、位数の大きさに関わらず通信ラウンド数は定数回のものの、通信量が加法秘密分散ベースの非特許文献２より多くなってしまうという問題があった。【００２２】
本発明の目的は、上記課題を解決し、秘密分散の方法に依らず通信ラウンド数が少ない秘密等号判定を実行することができる、サーバ装置、秘密等号判定システム、秘密等号判定方法、および秘密等号判定プログラム記録媒体を提供することにある。
【課題を解決するための手段】
【００２３】
上述の課題に鑑み、本発明の一態様は、第１の秘密分散データを生成する秘密分散データ生成部と、前記第１の秘密分散データと他のサーバ装置で生成された第２の秘密分散データとを保存するデータ記憶部と、乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶する乱数シェア生成部と、前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶するマスク部と、前記マスクしたデータを他のサーバ装置へ送信すると共に、他のサーバ装置から取得したマスクしたデータから元のデータを復元し、復元したデータを出力する秘密分散データ復元部と、前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力する乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、前記復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行う判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、を備えるサーバ装置である。【００２４】
また、本発明の他の態様は、第１の秘密分散データを生成するステップと、前記第１の秘密分散データと他のサーバ装置で生成された第２の秘密分散データとをデータ記憶部に保存するステップと、乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶するステップと、前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶するステップと、前記マスクしたデータを他のサーバ装置へ送信すると共に、他のサーバ装置から取得したマスクしたデータから元のデータを復元し、復元したデータを出力するステップと、前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力するステップと、前記復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行うステップと、を備える秘密等号判定方法である。【００２５】
さらに、本発明の別の態様は、第１の秘密分散データを生成する処理と、前記第１の秘密分散データと他のサーバ装置で生成された第２の秘密分散データとをデータ記憶部に保存する処理と、乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶する処理と、前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶する処理と、前記マスクしたデータを他のサーバ装置へ送信すると共に、他のサーバ装置から取得したマスクしたデータから元のデータを復元し、復元してデータを出力する処理と、前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力する処理と、前記復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行う処理と、をコンピュータに実行させる秘密等号判定プログラムを記録した記録媒体である。
【発明の効果】
【００２６】
本発明によれば、被計算値や判定結果や計算過程の値を知ることができない秘密等号判定を、位数２の環上で行う時と位数が２より大きい環上で行う時とで、全体の通信ラウンド数に差が生じずに実行できる。また、本発明は秘密分散の方法に依存しないため、構成要素の改善によって効率を改善することが可能である。たとえば、非特許文献５で本発明を実施すると、非特許文献２で実施した場合と比べて、小さい通信量で秘密等号判定を実行できる。【００２７】
本発明の更なる利点及び実施形態を、記述と図面を用いて下記に詳細に説明する。
【図面の簡単な説明】
【００２８】
【図１】本発明の第１の実施形態における秘密等号判定システムの機能構成例を示すブロック図である。
【図２】本発明の第１の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図３】本発明の第１の実施形態によるサーバ装置の動作例を示すフローチャートである。
【図４】本発明の第２の実施形態における秘密等号判定システムの機能構成例を示すブロック図である。
【図５】本発明の第２の実施形態による秘密分散プロキシ装置の機能構成を示すブロック図である。
【図６】本発明の第２の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図７】本発明の第２の実施形態による秘密分散プロキシ装置の動作例を示すフローチャートである。
【図８】本発明の第２の実施形態によるサーバ装置の動作例を示すフローチャートである。
【発明を実施するための形態】
【００２９】
以下、本発明の実施形態について図面を参照しつつ説明する。但し、以下に説明する実施形態によって本発明の技術的範囲は何ら限定解釈されることはない。
【００３０】
（第１の実施形態）
図１乃至図３を参照して、本発明の第１の実施形態に係る秘密等号判定システムついて説明する。
【００３１】
図１は、本発明の第１の実施形態による秘密等号判定システムの機能構成例を示すブロック図である。
【００３２】
図１を参照すると、本発明の第１の実施形態による秘密等号判定システムは、後述する図２で参照される第１乃至第ｎ（ｎは２以上の整数）のサーバ装置１００_１、１００_２、．．．、１００_ｎから成る。第１の実施形態による秘密等号判定システムにおいて、第１乃至第ｎのサーバ装置１００_１〜１００_ｎは、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図２は、第ｉのサーバ装置１００_ｉ（１≦ｉ≦ｎ）の機能構成例を示すブロック図である。
【００３３】
図２に示すように、第ｉのサーバ装置１００_ｉは、第ｉの秘密分散データ生成部１０１_ｉと、第ｉのデータ記憶部１０２_ｉと、第ｉのマスク部１０３_ｉと、第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉと、第ｉの乱数シェア生成部１０５_ｉと、第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉと、第ｉの秘密分散データ復元部１０７_ｉと、を含む。第ｉの秘密分散データ生成部１０１_ｉと第ｉのマスク部１０３_ｉと第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉと第ｉの秘密分散データ復元部１０７_ｉとは、それぞれ自身が含まれるサーバ装置と異なるサーバ装置に対し、ネットワーク経由で通信可能に接続されている。第ｉのデータ記憶部１０２_ｉは、第ｉの秘密分散データ生成部１０１_ｉと第ｉのマスク部１０３_ｉと第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉと第ｉの乱数シェア生成部１０５_ｉと第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉと第ｉの秘密分散データ復元部１０７_ｉと、それぞれ接続されている。第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉは、第ｉの乱数シェア生成部１０５_ｉと第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉと、それぞれ接続されている。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉと第ｉの秘密分散データ復元部１０７_ｉは接続されている。
【００３４】
このような構成の秘密等号判定システムにおいては、第１乃至第ｎのサーバ装置１００_１〜１００_ｎの内のいずれかの装置が入力した値ａ，ｂ、あるいは、第１乃至第ｎのデータ記憶部１０２_１〜１０２_ｎに記憶された秘密分散データ［ａ］，［ｂ］に対し、その入力や計算過程の値からａ，ｂの値を知られることなく、ａ＝ｂが成り立つか否かの判定結果の秘密分散データを計算し、第１乃至第ｎのデータ記憶部１０２_１〜１０２_ｎにそれぞれ記憶する。前記判定結果の秘密分散データは、第１乃至第ｎのデータ記憶部１０２_１〜１０２_ｎに記憶した後、第１乃至第ｎの秘密分散データ復元部１０７_１〜１０７_ｎにそれぞれ渡し、復元結果を得ても良い。
【００３５】
次に、本発明の第１の実施形態における秘密等号判定システムおよび第ｉのサーバ装置１００_ｉの動作について詳細に説明する。図３は、第ｉのサーバ装置１００_ｉの動作例を示すフローチャートである。
【００３６】
ここで、［ａ］_Ｂは、位数２の環上の値ａの秘密分散データを意味する。また、［ｂ］_Ｒは、位数が２より大きい環上の値ｂの秘密分散データを意味する。以降、［ａ］_Ｂをａのｂｉｔのシェア、［ｂ］_Ｒをｂのｒｉｎｇのシェアと呼称する。特に、第ｉのサーバ装置１００_ｉのシェアを表す場合、［ａ］_Ｂｉ，［ｂ］_Ｒｉとする。
【００３７】
たとえば、サーバ装置の台数が３、つまり、ｎ＝３であるとする。このとき、非特許文献２や非特許文献５で用いられている秘密分散が例として挙げられる。ここで、
【００３８】
【数１】
2019111318.tif 000003
を、それぞれｂｉｔのシェアに関する排他的論理和、論理積とする。これらは、位数２の環上の要素に対する二項演算子としての排他的論理和、論理積の記号としても以降用いることに注意されたい。ここで、ｂｉｔのシェアに関する排他的論理和、論理積には次の性質が成り立つ。
【００３９】
【数２】
2019111318.tif 000004
さらに、＋，−を、それぞれｒｉｎｇのシェアに関する加法演算子、減法演算子とする。これらは、位数が２より大きい環上の要素に対する二項演算子としての加法演算子、減法演算子としても以降用いることに注意されたい。ここで、ｒｉｎｇのシェアに関する加法演算子、減法演算子には次の性質が成り立つ。
【００４０】
【数３】
2019111318.tif 000005
たとえば、サーバ装置の台数が３、つまり、ｎ＝３であるとする。このとき、非特許文献５ではｂｉｔのシェアに関する排他的論理和を通信不要で計算できる。また、非特許文献５ではｂｉｔのシェアに関する論理積を１ラウンド３ｂｉｔの通信コストで計算できる。
【００４１】
なお、ａ＝ｂが成り立つか否か判定する際に、ａ，ｂのｂｉｔ長をLとする。つまり、ｒｉｎｇのシェアのｂｉｔ長はLである。また、秘密等号判定の結果は、等号が成り立つ場合に［１］_Ｂ、成り立たない場合に［０］_Ｂを出力する。
【００４２】
（ステップＡ１）
第ｉのサーバ装置１００_ｉの動作として、まず、入力ａを図示されない入力装置から第ｉの秘密分散データ生成部１０１_ｉに渡す。第ｉの秘密分散データ生成部１０１_ｉは、［ａ］_Ｒを生成する。第ｉのサーバ装置１００_ｉは、［ａ］_Ｒｉを第ｉのデータ記憶部１０２_ｉに保存する。第ｉのサーバ装置１００_ｉは、［ａ］_Ｒｉ’（ｉ’≠ｉ）を第ｉ’のサーバ装置１００_ｉ’に渡し、第ｉ’のサーバ装置１００_ｉ’は［ａ］_Ｒｉ’を第ｉ’のデータ記憶部１０２_ｉ’に保存する。入力ｂに関しても、第ｊ（ｊ≠ｉ）のサーバ装置１００_ｊが、同様に処理する。ステップＡ１は計算を開始する際のみに生じるステップである。よって、秘密計算プロトコルの過程で生じたｒｉｎｇのシェアについて秘密等号判定を行う場合、ステップＡ１は発生しない。
【００４３】
（ステップＡ２）
次に、第ｉの乱数シェア生成部１０５_ｉは、位数２の環上の乱数ｒ_ｔ（ｔ＝０，．．．，L−１）のｂｉｔのシェア［ｒ_ｔ］_Ｂｉを生成する。第ｉの乱数シェア生成部１０５_ｉは、［ｒ_ｔ］_Ｂｉを、第ｉのデータ記憶部１０２_ｉに保存する。また、第ｉの乱数シェア生成部１０５_ｉは［ｒ_ｔ］_Ｂｉを、第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉに渡す。第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉは、
【００４４】
【数４】
2019111318.tif 000006
の計算を、後述するステップＡ３、Ａ４、Ａ５の計算と並行して行う。数４の計算を実行するための回路の深さは、Ｌｏｇ（L）となる。第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉは、Ｌｏｇ（L）段すべてを計算する必要はなく、ステップＡ３、Ａ４、Ａ５の計算に要する回路の深さの分だけ、計算を行う。また第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉは、数４の計算を行うにあたり、計算過程で発生する１段ごとの論理積の値を、それぞれ第ｉのデータ記憶部１０２_ｉに保存する。たとえば、１段目の論理積の値は、
【００４５】
【数５】
2019111318.tif 000007
となる。
【００４６】
（ステップＡ３）
さらに、第ｉの乱数シェア生成部１０５_ｉは、ステップＡ２で生成した［ｒ_ｔ］_Ｂｉを、［ｒ_ｔ］_Ｒｉに変換する。変換後、第ｉの乱数シェア生成部１０５_ｉは、
【００４７】
【数６】
2019111318.tif 000008
を計算し、乱数シェア［ｒ］_Ｒｉを第ｉのデータ記憶部１０２_ｉに保存する。
【００４８】
（ステップＡ４）
第ｉのマスク部１０３_ｉは、第ｉのデータ記憶部１０２_ｉに保存された秘密分散データ［ａ］_Ｒｉ，［ｂ］_Ｒｉ，［ｒ］_Ｒｉを取り出し、
【００４９】
【数７】
2019111318.tif 000009
を計算する。第ｉのマスク部１０３_ｉは、第ｉのデータ記憶部１０２_ｉにマスクしたデータ［ａ−ｂ＋ｒ］_Ｒｉを保存する。
【００５０】
（ステップＡ５）
第ｉの秘密分散データ復元部１０７_ｉは、第ｉのデータ記憶部１０２_ｉから［ａ−ｂ＋ｒ］_Ｒｉを取り出し、外部の第ｊのサーバ装置１００_ｊに送信する。同時に、第ｉの秘密分散データ復元部１０７_ｉは、外部の第ｊのサーバ装置１００_ｊから得られた［ａ−ｂ＋ｒ］_Ｒｊ（ｊ≠ｉ）を用いて、ａ−ｂ＋ｒを復元したデータとして復元する。第ｉの秘密分散データ復元部１０７_ｉは、第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉにａ−ｂ＋ｒを渡す。
【００５１】
（ステップＡ６）
ここで、ｃ＝ａ−ｂ＋ｒとしたとき、ｃ_ｔ（ｔ＝０，．．．，L−１）をｃの各ｂｉｔとする。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｎは、
【００５２】
【数８】
2019111318.tif 000010
を計算する。この計算を実行する回路の深さは、Ｌｏｇ（L）となる。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｎは、第ｉのデータ記憶部１０２_ｉから、第ｉの乱数シェア生成部１０５_ｉが生成した値と、第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉが生成した値とを取り出す。このとき、ステップＡ２からステップＡ５までの計算回路の深さの分だけ、第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉは、［ｒｅｓ］_Ｂｉの計算を変形して行う。たとえば、計算回路の１段目であれば、
【００５３】
【数９】
2019111318.tif 000011
の計算を行う。残りの段数は、変形せずに行う。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉは、上述の計算を終えた後に、［ｒｅｓ］_Ｂｉを第ｉのデータ記憶部１０２_ｉに記憶する。
【００５４】
（ステップＡ７）
等号判定の結果を得る場合、第ｉの秘密分散データ復元部１０７_ｉは、第ｉのデータ記憶部１０２_ｉから［ｒｅｓ］_Ｂｉを取り出し、外部の第ｊのサーバ装置１００_ｊに送信する。同時に第ｉの秘密分散データ復元部１０７_ｉは、外部の第ｊのサーバ装置１００_ｊより得られた［ｒｅｓ］_Ｂｊ（ｊ≠ｉ）を用いて、ａ＝ｂが成り立つか否かの判定結果を復元する。
【００５５】
以上、説明した本発明の第１の実施形態においては、以下に記載するような効果を奏する。
【００５６】
第１の効果は、秘密等号判定に要するコストの内、通信ラウンド数に関して削減するというものである。これは、第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉが、ステップＡ３、Ａ４、Ａ５の計算と並行して［ｒ_ｔ］_Ｂｉの論理積の計算を実行しているためである。これにより、ステップＡ６で第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉは、［ｒｅｓ］_Ｂｉの計算を変形して行うことが可能となる。ステップＡ６で変形して計算した段数分、通信ラウンド数を削減できる。これにより、ステップＡ３、Ａ４、Ａ５の通信ラウンド数分が相殺される。よって、位数２の環上で行う時と位数が２より大きい環上で行う時とで、通信ラウンド数に差が生じずに実行できる。ただし、これはＬｏｇ(L)がステップＡ３、Ａ４、Ａ５の通信ラウンド数以上の場合に得られる効果となる。Ｌｏｇ(L)がステップＡ３、Ａ４、Ａ５の合計通信ラウンド数より小さい場合は、秘密等号判定の通信ラウンド数は、ステップＡ３、Ａ４、Ａ５の合計通信ラウンド数と一致する。たとえば、ステップＡ３、Ａ４、Ａ５の合計通信ラウンド数が３のとき、Lが８以上のときに、第１の効果が得られる。
【００５７】
第２の効果は、秘密等号判定に要するコストの内、通信量に関して構成要素の改善によって削減可能だというものである。これは、本第１の実施形態が秘密分散の形態に依らず実施できるためである。たとえば、非特許文献２の方式を用いて本第１の実施形態を実施する場合よりも、非特許文献５の方式を用いて本第１の実施形態を実施した方が、通信量を削減することができる。
【００５８】
（第２の実施の形態）
続いて、図４乃至図８を参照して、本発明の第２の実施形態に係る秘密等号判定システムついて説明する。本発明の第２の実施形態に係る秘密等号判定システムは、上述した第１の実施形態に係る秘密等号判定システムの変形例である。以下、本第２の実施形態において、第１の実施形態において既に説明した部分と同様な機能を有する部分には同一符号を付し、説明を省略する。
【００５９】
図４は、第２の実施形態による秘密等号判定システムの機能構成例を示すブロック図である。
【００６０】
図４を参照すると、本発明の第２の実施形態による秘密等号判定システムは、後述する図５で参照される秘密分散プロキシ装置２１０と、後述する図６で参照される第１乃至第ｎ（ｎは２以上の整数）のサーバ装置２１０_１、２１０_２、．．．、２１０_ｎから成る。第２の実施形態による秘密等号判定システムにおいて、秘密分散プロキシ装置２１０と第１乃至第ｎのサーバ装置２１０_１〜２１０_ｎとはネットワーク経由で通信可能に接続されている。また、第１乃至第ｎのサーバ装置２１０_１〜２１０_ｎは、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。
【００６１】
図５に示すように、秘密分散プロキシ装置２１０は、秘密分散データ生成部２１１と、秘密分散データ復元部２１２と、を含む。秘密分散データ生成部２１１と第１乃至第ｎのサーバ装置２１０_１〜２１０_ｎとはネットワーク経由で通信可能に接続されている。秘密分散データ復元部２１２と第１乃至第ｎのサーバ装置２１０_１〜２１０_ｎとはネットワーク経由で通信可能に接続されている。
【００６２】
図６に示すように、第ｉのサーバ装置２００_ｉ（１≦ｉ≦ｎ）は、第ｉのデータ記憶部２０２_ｉと、第ｉのマスク部１０３_ｉと、第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉと、第ｉの乱数シェア生成部１０５_ｉと、第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部２０６_ｉと、を含む。第ｉのデータ記憶部２０２_ｉと第ｉのマスク部１０３_ｉと第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部２０６_ｉとは、それぞれ自身が含まれるサーバ装置と異なるサーバ装置に対し、ネットワーク経由で通信可能に接続されている。
【００６３】
本第２の実施形態による秘密等号判定システム、第１乃至第ｎのサーバ装置２００_１〜２００_ｎおよび秘密分散プロキシ装置２１０においては、図示されない入力装置から秘密分散プロキシ装置２１０に入力された値ａ，ｂ、あるいは、第１乃至第ｎのデータ記憶部２０２_１〜２０２_ｎに記憶された秘密分散データ［ａ］_Ｒ，［ｂ］_Ｒに対し、その入力や計算過程の値からａ，ｂの値を知られることなく、ａ＝ｂが成り立つか否かの判定結果の秘密分散データを計算し、第１乃至第ｎのデータ記憶部２０２_１〜２０２_ｎにそれぞれ記憶する。前記判定結果の秘密分散データは、第１乃至第ｎのデータ記憶部２０２_１〜２０２_ｎに記憶した後、秘密分散プロキシ装置２１０にそれぞれ渡し、復元結果を得ても良い。
【００６４】
次に、本発明の第２の実施形態における秘密等号判定システム、秘密分散プロキシ装置２１０および第ｉのサーバ装置２００_ｉの動作について詳細に説明する。図７は、秘密分散プロキシ装置２１０の動作例を示すフローチャートである。また、図８は、第ｉのサーバ装置２００_ｉの動作例を示すフローチャートである。
【００６５】
（ステップＢ１）
まず、図７を参照すると、秘密分散プロキシ装置２１０の動作として、まず、入力ａを図示されない入力装置から秘密分散データ生成部２１１に渡す。秘密分散データ生成部２１１は、［ａ］_Ｒを生成する。次に、秘密分散データ生成部２１１は［ａ］_Ｒｉを、外部の第ｉのサーバ装置２００_ｉの第ｉのデータ記憶部２０２_ｉに渡す。第ｉのデータ記憶部２０２_ｉは、［ａ］_Ｒｉを記憶する。入力ｂに関しても、秘密分散プロキシ装置２１０と外部の第ｉのサーバ装置２００_ｉが、同様に処理する。ステップＢ１は計算を開始する際のみに生じるステップである。よって、秘密計算プロトコルの過程で生じたｒｉｎｇのシェアについて秘密等号判定を行う場合、ステップＢ１は発生しない。
【００６６】
（ステップＣ１）
図８を参照して、ステップＣ１は、第１の実施形態による第ｉのサーバ装置１００_ｉの動作におけるステップＡ２と等しい。ただし、値を保存するのは第ｉのデータ記憶部２０２_ｉとなる。また、第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉは、
【００６７】
【数１０】
2019111318.tif 000012
の計算を、ステップＣ２、Ｃ３、Ｂ２、Ｃ４の計算と並行して行う。数１０の計算を実行するための回路の深さは、Ｌｏｇ（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)によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、秘密等号判定プログラムをコンピュータに供給できる。
【００７８】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【００７９】
本発明によれば、たとえば、データベースにおける文字列処理で生じる秘密等号判定を、位数２の環上で行う時と位数が２より大きい環上で行う時とでラウンド数に差が生じずに実行でき、通信ラウンド数の削減を実現できる。これにより、秘密等号判定を用いる上位プロトコルに関しても、通信ラウンド数を削減することができる。また、本発明は秘密分散の方法に依存しないため、非特許文献２や非特許文献５といった、通信量の少ない秘密計算プロトコルで実施可能である。
【符号の説明】
【００８０】
１００_ｉ  サーバ装置
１０１_ｉ  秘密分散データ生成部
１０２_ｉ  データ記憶部
１０３_ｉ  マスク部
１０４_ｉ  乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部
１０５_ｉ  乱数シェア生成部
１０６_ｉ  判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部
１０７_ｉ  秘密分散データ復元部
２００_ｉ  サーバ装置
２０２_ｉ  データ記憶部
２０６_ｉ  判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部
２１０     秘密分散プロキシ装置
２１１     秘密分散データ生成部
２１２     秘密分散データ復元部
【図１】
2019111318.tif 000013
【図２】
2019111318.tif 000014
【図３】
2019111318.tif 000015
【図４】
2019111318.tif 000016
【図５】
2019111318.tif 000017
【図６】
2019111318.tif 000018
【図７】
2019111318.tif 000019
【図８】
2019111318.tif 000020
【手続補正書】
【提出日】令和2年5月19日(2020.5.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１の秘密分散データを生成する秘密分散データ生成部と、
前記第１の秘密分散データと他のサーバ装置で生成された第２の秘密分散データとを保存するデータ記憶部と、
乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶する乱数シェア生成部と、
前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶するマスク部と、
前記マスクしたデータを他のサーバ装置へ送信すると共に、他のサーバ装置から取得したマスクしたデータから元のデータを復元し、復元したデータを出力する秘密分散データ復元部と、
前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力する乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
前記復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行う判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備えることを特徴とするサーバ装置。
【請求項２】
ネットワークで接続された請求項１に記載のサーバ装置を複数台備える秘密等号判定システム。
【請求項３】
第１の秘密分散データを生成するステップと、
前記第１の秘密分散データと他のサーバ装置で生成された第２の秘密分散データとをデータ記憶部に保存するステップと、
乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶するステップと、
前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶するステップと、
前記マスクしたデータを他のサーバ装置へ送信すると共に、他のサーバ装置から取得したマスクしたデータから元のデータを復元し、復元したデータを出力するステップと、
前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力するステップと、
前記復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行うステップと、
を備えることを特徴とする秘密等号判定方法。
【請求項４】
第１の秘密分散データを生成する処理と、
前記第１の秘密分散データと他のサーバ装置で生成された第２の秘密分散データとをデータ記憶部に保存する処理と、
乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶する処理と、
前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶する処理と、
前記マスクしたデータを他のサーバ装置へ送信すると共に、他のサーバ装置から取得したマスクしたデータから元のデータを復元し、復元したデータを出力する処理と、
前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力する処理と、
前記復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行う処理と、
をコンピュータに実行させる秘密等号判定プログラム。
【請求項５】
第１の秘密分散データと他のサーバ装置用の第２の秘密分散データとを保存するデータ記憶部と、
乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶する乱数シェア生成部と、
前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶するマスク部と、
前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力する乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行う判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部と、
を備えることを特徴とするサーバ装置。
【請求項６】
ネットワークで接続された請求項５に記載のサーバ装置の複数台と、秘密分散プロキシ装置とを備える秘密等号判定システムであって、前記秘密分散プロキシ装置は、
前記複数のサーバ装置用の秘密分散データを生成する秘密分散データ生成部と、
前記複数のサーバ装置から取得したマスクしたデータから元のデータを復元し、前記復元したデータを出力する秘密分散データ復元部と、
を有することを特徴とする秘密等号判定システム。
【請求項７】
第１の秘密分散データと他のサーバ装置用の第２の秘密分散データとをデータ記憶部に保存するステップと、
乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶するステップと、
前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶するステップと、
前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力するステップと、
復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行うステップと、
を備えることを特徴とする秘密等号判定方法。
【請求項８】
第１の秘密分散データと他のサーバ装置用の第２の秘密分散データとをデータ記憶部に保存する処理と、
乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶する処理と、
前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶する処理と、
前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力する処理と、
復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行う処理と、
をコンピュータに実行させる秘密等号判定プログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は秘密計算プロトコルに関し、特に効率よく秘密等号判定を行うことができるサーバ装置、秘密等号判定システム、秘密等号判定方法および秘密等号判定プログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
秘密情報aを、pを法とする多項式f_a(x)を用いてＮ台のサーバ装置で分散するときに生成される、秘密情報aの分散情報を、[a]p=(f_a(1), f_a(2), …, f_a(N))と書くことにする。このとき、識別子i（１≦i≦Ｎ）を持つ第iのサーバ装置にf_a(i)が保持されているものとする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
さらに、本発明の別の態様は、第１の秘密分散データを生成する処理と、前記第１の秘密分散データと他のサーバ装置で生成された第２の秘密分散データとをデータ記憶部に保存する処理と、乱数を秘密分散した乱数シェアを生成し、該乱数シェアを前記データ記憶部に記憶する処理と、前記データ記憶部に保存された、前記乱数シェアと前記第１の秘密分散データとを用いて、前記第２の秘密分散データをマスクし、マスクしたデータを前記データ記憶部に記憶する処理と、前記マスクしたデータを他のサーバ装置へ送信すると共に、他のサーバ装置から取得したマスクしたデータから元のデータを復元し、復元してデータを出力する処理と、前記乱数を秘密分散した値同士の論理積計算を他の計算と並行して行い、論理積の値を出力する処理と、前記復元したデータと前記乱数シェアと前記論理積の値とを用いて秘密等号判定を行う処理と、をコンピュータに実行させる秘密等号判定プログラムである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
このような構成の秘密等号判定システムにおいては、第１乃至第ｎのサーバ装置１００_１〜１００_ｎの内のいずれかの装置が入力した値ａ，ｂ、あるいは、第１乃至第ｎのデータ記憶部１０２_１〜１０２_ｎに記憶された秘密分散データ［ａ］_Ｒ，［ｂ］_Ｒに対し、その入力や計算過程の値からａ，ｂの値を知られることなく、ａ＝ｂが成り立つか否かの判定結果の秘密分散データを計算し、第１乃至第ｎのデータ記憶部１０２_１〜１０２_ｎにそれぞれ記憶する。前記判定結果の秘密分散データは、第１乃至第ｎのデータ記憶部１０２_１〜１０２_ｎに記憶した後、第１乃至第ｎの秘密分散データ復元部１０７_１〜１０７_ｎにそれぞれ渡し、復元結果を得ても良い。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
（ステップＡ６）
ここで、ｃ＝ａ−ｂ＋ｒとしたとき、ｃ_ｔ（ｔ＝０，．．．，L−１）をｃの各ｂｉｔとする。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉは、
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
【数８】
2019111318.tif 000021
を計算する。この計算を実行する回路の深さは、Ｌｏｇ（L）となる。第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉは、第ｉのデータ記憶部１０２_ｉから、第ｉの乱数シェア生成部１０５_ｉが生成した値と、第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉが生成した値とを取り出す。このとき、ステップＡ２からステップＡ５までの計算回路の深さの分だけ、第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉは、［ｒｅｓ］_Ｂｉの計算を変形して行う。たとえば、計算回路の１段目であれば、
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
第１の効果は、秘密等号判定に要するコストの内、通信ラウンド数に関して削減するというものである。これは、第ｉの乱数シェアｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０４_ｉが、ステップＡ３、Ａ４、Ａ５の計算と並行して［ｒ_ｔ］_Ｂｉの論理積の計算を実行しているためである。これにより、ステップＡ６で第ｉの判定ｂｉｔ−ｃｏｎｊｕｎｃｔｉｏｎ部１０６_ｉは、［ｒｅｓ］_Ｂｉの計算を変形して行うことが可能となる。ステップＡ６で変形して計算した段数分、通信ラウンド数を削減できる。これにより、ステップＡ３、Ａ４、Ａ５の通信ラウンド数分が相殺される。よって、位数２の環上で行う時と位数が２より大きい環上で行う時とで、通信ラウンド数に差が生じずに実行できる。ただし、これはＬｏｇ(L)がステップＡ３、Ａ４、Ａ５の合計通信ラウンド数以上の場合に得られる効果となる。Ｌｏｇ(L)がステップＡ３、Ａ４、Ａ５の合計通信ラウンド数より小さい場合は、秘密等号判定の通信ラウンド数は、ステップＡ３、Ａ４、Ａ５の合計通信ラウンド数と一致する。たとえば、ステップＡ３、Ａ４、Ａ５の合計通信ラウンド数が３のとき、Lが８以上のときに、第１の効果が得られる。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
図４を参照すると、本発明の第２の実施形態による秘密等号判定システムは、後述する図５で参照される秘密分散プロキシ装置２１０と、後述する図６で参照される第１乃至第ｎ（ｎは２以上の整数）のサーバ装置２００_１、２００_２、．．．、２００_ｎから成る。第２の実施形態による秘密等号判定システムにおいて、秘密分散プロキシ装置２１０と第１乃至第ｎのサーバ装置２００_１〜２００_ｎとはネットワーク経由で通信可能に接続されている。また、第１乃至第ｎのサーバ装置２００_１〜２００_ｎは、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００６１
【補正方法】変更
【補正の内容】
【００６１】
図５に示すように、秘密分散プロキシ装置２１０は、秘密分散データ生成部２１１と、秘密分散データ復元部２１２と、を含む。秘密分散データ生成部２１１と第１乃至第ｎのサーバ装置２００_１〜２００_ｎとはネットワーク経由で通信可能に接続されている。秘密分散データ復元部２１２と第１乃至第ｎのサーバ装置２００_１〜２００_ｎとはネットワーク経由で通信可能に接続されている。
【国際調査報告】
2019111318.tif 000022
2019111318.tif 000023
2019111318.tif 000024
2019111318.tif 000025