(57)【要約】  秘密結合システムは、複数の秘密計算装置を含む秘密結合システムであって、複数の秘密計算装置は、ベクトル結合部１１n、第一置換計算部１２n、第一置換適用部１３n、第一ベクトル生成部１４n、第二ベクトル生成部１５n、ビット反転部１６n、第二置換計算部１７n、第二置換適用部１８n、第三ベクトル生成部１９n、逆置換適用部１１０n、ベクトル分離部１１１n、第三置換適用部１１２n、属性値置換部１１３n及び第四ベクトル生成部１１４nを備えている。
2019244756.tif 000002
【特許請求の範囲】
【請求項１】
複数の秘密計算装置を含む秘密結合システムであって、
Fは任意の環であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、m0,m1,L0,L1は１以上の整数であり、k0∈Fm0は第一テーブルのキーのベクトルであり、k1∈Fm1は第二テーブルのキーのベクトルであり、p=0,…,L0-1としてv0,p∈Fm0は上記第一テーブルの属性pの属性値のベクトルであり、q=0,…,L1-1としてv1,q∈Fm1は上記第二テーブルの属性qの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
上記複数の秘密計算装置は、
上記ベクトルk0のシェア[k0]及び上記ベクトルk1のシェア[k1]を用いて、上記ベクトルk0及び上記ベクトルk1を結合したベクトルk'∈[F]m0+m1のシェア[k']を生成する複数のベクトル結合部と、
上記シェア[k']を用いて、上記ベクトルk'を昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の第一置換計算部と、
上記シェア[k']及び上記シェア{{σ}}を用いて、上記ベクトルk'に上記置換σを適用したベクトルσ(k')のシェア[σ(k')]を生成する複数の第一置換適用部と、
上記シェア[σ(k')]を用いて、上記ベクトルσ(k')のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数の第一ベクトル生成部と、
上記シェア[e]を用いて、上記ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルe'のシェア[e']を生成する複数の第二ベクトル生成部と、
上記シェア[e']を用いて、上記ベクトルe'の各要素をビット反転させたベクトルe''のシェア[e'']を生成する複数のビット反転部と、
上記シェア[e'']を用いて、上記ベクトルe''を昇順に安定ソートする置換σ'のシェア{{σ'}}を生成する複数の第二置換計算部と、
上記シェア[e'']及び上記シェア{{σ'}}を用いて、上記ベクトルe''に上記置換σ'を適用したベクトルσ'(e'')のシェア[σ'(e'')]を生成する複数の第二置換適用部と、
上記シェア[σ'(e'')]を用いて、上記ベクトルσ'(e'')のある要素iが、０である場合には└i/2┘を、０でない場合には０をそのある要素iに対応する要素として持つベクトルxのシェア[x]を生成する複数の第三ベクトル生成部と、
上記シェア[x]、上記シェア{{σ}}及び上記シェア{{σ'}}を用いて、上記ベクトルxに上記置換σ'の逆置換σ'-1及び上記置換σの逆置換σ-1を適用したベクトルσ-1(σ'-1(x))のシェア[σ-1(σ'-1(x))]を生成する複数の逆置換適用部と、
上記シェア[σ-1(σ'-1(x))]を用いて、上記ベクトルσ-1(σ'-1(x))の先頭からm0個の要素からなるベクトルs0のシェア[s0]と、上記ベクトルσ-1(σ'-1(x))の残りのm1個の要素からなるベクトルs1のシェア[s1]とを生成する複数のベクトル分離部と、
上記シェア[s0]、上記シェア[s1]及び上記置換π0,π1を用いて、上記ベクトルs0に上記置換π0を適用したベクトルτ0:=π0(s0)のシェア[π0(s0)]と、上記ベクトルs1に上記置換π1を適用したベクトルτ1:=π1(s1)のシェア[π1(s1)]とを生成して、τ0:=π0(s0)及びτ1:=π1(s1)を公開する複数の第三置換適用部と、
上記置換π0のシェア{{π0}}、上記置換π1のシェア{{π1}}、上記ベクトルv0,pのシェア[v0,p]及び上記ベクトルv1,qのシェア[v1,q]を用いて、上記第一テーブルの各属性pの属性値のベクトルv0,pを上記置換π0で置換したベクトルv'0,pのシェア[v'0,p]と、上記第二テーブルの各属性qの属性値のベクトルv1,qを上記置換π1で置換したベクトルv'1,qのシェア[v'1,q]とを生成する複数の属性値置換部と、
上記ベクトルτ0、上記ベクトルτ1、上記シェア[v'0,p]及び上記シェア[v'1,q]を用いて、上記ベクトルτ0のi'番目の要素が０でない場合には上記ベクトルv'0,pのi'番目の要素をi'-1番目の要素として持つベクトルv''0,pのシェア[v''0,p]と、上記ベクトルτ1のi'番目の要素が０でない場合には上記ベクトルv'1,qのi'番目の要素をi'-1番目の要素として持つベクトルv''1,qのシェア[v''1,q]とを生成する複数の第四ベクトル生成部と、
を含む秘密結合システム。
【請求項２】
請求項１の秘密結合システムの秘密計算装置。
【請求項３】
Fは任意の環であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、m0,m1,L0,L1は１以上の整数であり、k0∈Fm0は第一テーブルのキーのベクトルであり、k1∈Fm1は第二テーブルのキーのベクトルであり、p=0,…,L0-1としてv0,p∈Fm0は上記第一テーブルの属性pの属性値のベクトルであり、q=0,…,L1-1としてv1,q∈Fm1は上記第二テーブルの属性qの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
複数のベクトル結合部が、上記ベクトルk0のシェア[k0]及び上記ベクトルk1のシェア[k1]を用いて、上記ベクトルk0及び上記ベクトルk1を結合したベクトルk'∈[F]m0+m1のシェア[k']を生成する複数のベクトル結合ステップと、
複数の第一置換計算部が、上記シェア[k']を用いて、上記ベクトルk'を昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の第一置換計算ステップと、
複数の第一置換適用部が、上記シェア[k']及び上記シェア{{σ}}を用いて、上記ベクトルk'に上記置換σを適用したベクトルσ(k')のシェア[σ(k')]を生成する複数の第一置換適用ステップと、
複数の第一ベクトル生成部が、上記シェア[σ(k')]を用いて、上記ベクトルσ(k')のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数の第一ベクトル生成ステップと、
複数の第二ベクトル生成部が、上記シェア[e]を用いて、上記ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルe'のシェア[e']を生成する複数の第二ベクトル生成ステップと、
複数のビット反転部が、上記シェア[e']を用いて、上記ベクトルe'の各要素をビット反転させたベクトルe''のシェア[e'']を生成する複数のビット反転ステップと、
複数の第二置換計算部が、上記シェア[e'']を用いて、上記ベクトルe''を昇順に安定ソートする置換σ'のシェア{{σ'}}を生成する複数の第二置換計算ステップと、
複数の第二置換適用部が、上記シェア[e'']及び上記シェア{{σ'}}を用いて、上記ベクトルe''に上記置換σ'を適用したベクトルσ'(e'')のシェア[σ'(e'')]を生成する複数の第二置換適用ステップと、
複数の第三ベクトル生成部が、上記シェア[σ'(e'')]を用いて、上記ベクトルσ'(e'')のある要素iが、０である場合には└i/2┘を、０でない場合には０をそのある要素iに対応する要素として持つベクトルxのシェア[x]を生成する複数の第三ベクトル生成ステップと、
複数の逆置換適用部が、上記シェア[x]、上記シェア{{σ}}及び上記シェア{{σ'}}を用いて、上記ベクトルxに上記置換σ'の逆置換σ'-1及び上記置換σの逆置換σ-1を適用したベクトルσ-1(σ'-1(x))のシェア[σ-1(σ'-1(x))]を生成する複数の逆置換適用ステップと、
複数のベクトル分離部が、上記シェア[σ-1(σ'-1(x))]を用いて、上記ベクトルσ-1(σ'-1(x))の先頭からm0個の要素からなるベクトルs0のシェア[s0]と、上記ベクトルσ-1(σ'-1(x))の残りのm1個の要素からなるベクトルs1のシェア[s1]とを生成する複数のベクトル分離ステップと、
複数の第三置換適用部が、上記シェア[s0]、上記シェア[s1]及び上記置換π0,π1を用いて、上記ベクトルs0に上記置換π0を適用したベクトルτ0:=π0(s0)のシェア[π0(s0)]と、上記ベクトルs1に上記置換π1を適用したベクトルτ1:=π1(s1)のシェア[π1(s1)]とを生成して、τ0:=π0(s0)及びτ1:=π1(s1)を公開する複数の第三置換適用ステップと、
複数の属性値置換部が、上記置換π0のシェア{{π0}}、上記置換π1のシェア{{π1}}、上記ベクトルv0,pのシェア[v0,p]及び上記ベクトルv1,qのシェア[v1,q]を用いて、上記第一テーブルの各属性pの属性値のベクトルv0,pを上記置換π0で置換したベクトルv'0,pのシェア[v'0,p]と、上記第二テーブルの各属性qの属性値のベクトルv1,qを上記置換π1で置換したベクトルv'1,qのシェア[v'1,q]とを生成する複数の属性値置換ステップと、
複数の第四ベクトル生成部が、上記ベクトルτ0、上記ベクトルτ1、上記シェア[v'0,p]及び上記シェア[v'1,q]を用いて、上記ベクトルτ0のi'番目の要素が０でない場合には上記ベクトルv'0,pのi'番目の要素をi'-1番目の要素として持つベクトルv''0,pのシェア[v''0,p]と、上記ベクトルτ1のi'番目の要素が０でない場合には上記ベクトルv'1,qのi'番目の要素をi'-1番目の要素として持つベクトルv''1,qのシェア[v''1,q]とを生成する複数の第四ベクトル生成ステップと、
を含む秘密結合方法。
【請求項４】
請求項２の秘密計算装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密計算技術に関する。この発明は、特に、秘匿性を保ったまま２つのテーブルを結合する技術に関する。
【背景技術】
【０００２】
秘密計算技術の分野において、秘匿性を保ったまま２つのテーブルを結合する技術が求められている。【０００３】
秘匿性を保ったまま２つのテーブルを結合する技術として、例えば非特許文献１に記載された技術が知られている。非特許文献１では、キー重複ありの場合の等結合が実現されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】桐淵直人、五十嵐大、諸橋玄武、濱田浩気、「属性情報と履歴情報の秘匿統合分析に向けた秘密計算による高速な等結合アルゴリズムとその実装」、CSS2016、2016
【発明の概要】
【発明が解決しようとする課題】
【０００５】
この発明は、キー重複がない場合に非特許文献１の技術よりも高速に秘匿性を保ったまま２つのテーブルを結合する秘密結合システム、方法、秘密計算装置及びプログラムを提供することである。
【課題を解決するための手段】
【０００６】
この発明の一態様による秘密結合システムは、複数の秘密計算装置を含む秘密結合システムであって、Fは任意の環であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、m0,m1,L0,L1は１以上の整数であり、k0∈Fm0は第一テーブルのキーのベクトルであり、k1∈Fm1は第二テーブルのキーのベクトルであり、p=0,…,L0-1としてv0,p∈Fm0は第一テーブルの属性pの属性値のベクトルであり、q=0,…,L1-1としてv1,q∈Fm1は第二テーブルの属性qの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、複数の秘密計算装置は、ベクトルk0のシェア[k0]及びベクトルk1のシェア[k1]を用いて、ベクトルk0及びベクトルk1を結合したベクトルk'∈[F]m0+m1のシェア[k']を生成する複数のベクトル結合部と、シェア[k']を用いて、ベクトルk'を昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の第一置換計算部と、シェア[k']及びシェア{{σ}}を用いて、ベクトルk'に置換σを適用したベクトルσ(k')のシェア[σ(k')]を生成する複数の第一置換適用部と、シェア[σ(k')]を用いて、ベクトルσ(k')のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数の第一ベクトル生成部と、シェア[e]を用いて、ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルe'のシェア[e']を生成する複数の第二ベクトル生成部と、シェア[e']を用いて、ベクトルe'の各要素をビット反転させたベクトルe''のシェア[e'']を生成する複数のビット反転部と、シェア[e'']を用いて、ベクトルe''を昇順に安定ソートする置換σ'のシェア{{σ'}}を生成する複数の第二置換計算部と、シェア[e'']及びシェア{{σ'}}を用いて、ベクトルe''に置換σ'を適用したベクトルσ'(e'')のシェア[σ'(e'')]を生成する複数の第二置換適用部と、シェア[σ'(e'')]を用いて、ベクトルσ'(e'')のある要素iが、０である場合には└i/2┘を、０でない場合には０をそのある要素iに対応する要素として持つベクトルxのシェア[x]を生成する複数の第三ベクトル生成部と、シェア[x]、シェア{{σ}}及びシェア{{σ'}}を用いて、ベクトルxに置換σ'の逆置換σ'-1及び置換σの逆置換σ-1を適用したベクトルσ-1(σ'-1(x))のシェア[σ-1(σ'-1(x))]を生成する複数の逆置換適用部と、シェア[σ-1(σ'-1(x))]を用いて、ベクトルσ-1(σ'-1(x))の先頭からm0個の要素からなるベクトルs0のシェア[s0]と、ベクトルσ-1(σ'-1(x))の残りのm1個の要素からなるベクトルs1のシェア[s1]とを生成する複数のベクトル分離部と、シェア[s0]、シェア[s1]及び置換π0,π1を用いて、ベクトルs0に置換π0を適用したベクトルτ0:=π0(s0)のシェア[π0(s0)]と、ベクトルs1に置換π1を適用したベクトルτ1:=π1(s1)のシェア[π1(s1)]とを生成して、τ0:=π0(s0)及びτ1:=π1(s1)を公開する複数の第三置換適用部と、置換π0のシェア{{π0}}、置換π1のシェア{{π1}}、ベクトルv0,pのシェア[v0,p]及びベクトルv1,qのシェア[v1,q]を用いて、第一テーブルの各属性pの属性値のベクトルv0,pを置換π0で置換したベクトルv'0,pのシェア[v'0,p]と、第二テーブルの各属性qの属性値のベクトルv1,qを置換π1で置換したベクトルv'1,qのシェア[v'1,q]とを生成する複数の属性値置換部と、ベクトルτ0、ベクトルτ1、シェア[v'0,p]及びシェア[v'1,q]を用いて、ベクトルτ0のi'番目の要素が０でない場合にはベクトルv'0,pのi'番目の要素をi'-1番目の要素として持つベクトルv''0,pのシェア[v''0,p]と、ベクトルτ1のi'番目の要素が０でない場合にはベクトルv'1,qのi'番目の要素をi'-1番目の要素として持つベクトルv''1,qのシェア[v''1,q]とを生成する複数の第四ベクトル生成部と、を備えている。
【発明の効果】
【０００７】
逆置換を用いることで、キー重複がない場合に非特許文献１の技術よりも高速に秘匿性を保ったまま２つのテーブルを結合することができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、秘密結合システムの機能構成を例示する図である。
【図２】図２は、秘密計算装置の機能構成を例示する図である。
【図３】図３は、秘密結合方法の処理手続きを例示する図である。
【図４】図４は、コンピュータの機能構成例を示す図である。
【発明を実施するための形態】
【０００９】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１０】
図１を参照して、実施形態の秘密結合システムの構成例を説明する。秘密結合システムは、N（≧2）台の秘密計算装置１1,…,１Nを含む。本形態では、秘密計算装置１1, …, １Nはそれぞれ通信網２へ接続されている。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などである。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密計算装置１1, …, １Nへ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から秘密計算装置１1, …,１Nへオフラインで入力するように構成してもよい。
【００１１】
図２を参照して、秘密結合システムに含まれる秘密計算装置１n（n=1, …, N）の構成例を説明する。秘密結合システムの秘密計算装置１nは、例えば、図２に示すように、ベクトル結合部１１n、第一置換計算部１２n、第一置換適用部１３n、第一ベクトル生成部１４n、第二ベクトル生成部１５n、ビット反転部１６n、第二置換計算部１７n、第二置換適用部１８n、第三ベクトル生成部１９n、逆置換適用部１１０n、ベクトル分離部１１１n、第三置換適用部１１２n、属性値置換部１１３n及び第四ベクトル生成部１１４nを備えている。
【００１２】
秘密計算装置１n（1≦n≦N）の各構成部が他の秘密計算装置１n'（n'=1, …, N、ただしn≠n'）の各構成部と協調しながら後述する各ステップの処理を行うことにより実施形態の秘密結合方法が実現される。
【００１３】
なお、各ステップの処理は、秘密計算により行われる。すなわち、秘密計算装置１nは、シェアを復元することなく、言い換えればシェアの中身を知ることなく、各ステップの処理を行う。
【００１４】
秘密計算装置１nは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密計算装置１nは、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密計算装置１nに入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密計算装置１nの各構成部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００１５】
以下の説明において、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであるとする。
【００１６】
図３を参照して、実施形態の秘密結合システムが実行する秘密結合方法の処理手続きを説明する。
【００１７】
以下に説明する秘密結合システムは、第一テーブルと第二テーブルを秘密垂直結合する。言い換えれば、以下に説明する秘密結合システムは、秘匿性を保ちつつ、第一テーブル及び第二テーブルの共通するキーについての、第一テーブルの属性値及び第二テーブルの属性値を得る。
【００１８】
m0,m1,L0,L1は、１以上の整数であるとする。m0,m1,L0,L1は、同じ値であってもよいし、異なる値であってもよい。
【００１９】
第一テーブルは、m0個のレコードを有している。m0個のレコードのそれぞれは、１個のキーと、L0個の属性の属性値とを有している。k0∈Fm0は第一テーブルのキーのベクトルであるとする。p=0,…,L0-1として、v0,p∈Fm0は第一テーブルの属性pの属性値のベクトルであるとする。第一テーブルの中は、重複するキーはないとする。
【００２０】
[F]m0の上付き文字の中のm0は、「m0」を意味する。このように、上付き文字の中では、更なる上付き文字及び下付き文字の表現を省略することがある。同様に、下付き文字の中では、更なる上付き文字及び下付き文字の表現を省略することがある。
【００２１】
第二テーブルは、m1個のレコードを有している。m1個のレコードのそれぞれは、１個のキーと、L1個の属性の属性値とを有している。k1∈Fm1は第二テーブルのキーのベクトルであるとする。q=0,…,L1-1としてv1,q∈Fm1は上記第二テーブルの属性qの属性値のベクトルであるとする。第二テーブルの中では、重複するキーはないとする。
【００２２】
例えば、第一テーブルは、レコード数が３であり、キーのベクトルk0=(1,2,3)Tと、１個の属性z1の属性値のベクトルv0,1=(5,10,1)Tとから構成されているとする。
【００２３】
また、第二テーブルは、レコード数が４であり、キーのベクトルk1=(1,3,4,5)Tと、１個の属性z1'の属性値のベクトルv1,1=(2,4,9,8)Tとから構成されているとする。
【００２４】
＜ステップＳ１＞
ベクトル結合部１１1,…,１１Nに、ベクトルk0のシェア[k0]及びベクトルk1のシェア[k1]が入力される。
【００２５】
ベクトル結合部１１1,…,１１Nは、[k0]と[k1]を結合して[k']∈[F]m0+m1を得る。
【００２６】
より詳細には、ベクトル結合部１１1,…,１１Nは、ベクトルk0のシェア[k0]及びベクトルk1のシェア[k1]を用いて、ベクトルk0及びベクトルk1を結合したベクトルk'∈[F]m0+m1のシェア[k']を生成する（ステップＳ１）。
【００２７】
生成されたシェア[k']は、第一置換計算部１２1,…,１２N及び第一置換適用部１３1,…,１３Nに出力される。
【００２８】
例えば、ベクトルk0=(1,2,3)Tであり、ベクトルk1=(1,3,4,5)Tであるとする。この場合、ベクトルk'=(1,2,3,1,3,4,5)Tとなる。
【００２９】
＜ステップＳ２＞
第一置換計算部１２1,…,１２Nに、シェア[k']が入力される。
【００３０】
第一置換計算部１２1,…,１２Nは、[k']のソート{{σ}}を得る。
【００３１】
より詳細には、第一置換計算部１２1,…,１２Nは、シェア[k']を用いて、ベクトルk'を昇順に安定ソートする置換σのシェア{{σ}}を生成する（ステップＳ２）。
【００３２】
安定ソートとは、同等なデータのソート前の順序が、ソート後も保存されるものをいう。安定ソートを行う置換σのシェア{{σ}}の生成は、例えば参考文献１の手法により実現することができる。
【００３３】
〔参考文献１〕五十嵐大、濱田浩気、菊池亮、千田浩司、「超高速秘密計算ソートの設計と実装：秘密計算がスクリプト言語に並ぶ日」、CSS2017、2017
【００３４】
生成されたシェア{{σ}}は、第一置換適用部１３1,…,１３N及び逆置換適用部１１０1,…, １１０Nに出力される。
【００３５】
例えば、ベクトルk'=(1,2,3,1,3,4,5)Tであるとする。この場合、置換σは以下の式（１）のようになる。例えば、番号が１スタートで表記されるとして、置換σの各列(i,j)Tは、置換が適用されるベクトルのi番目の要素をj番目に移動することを意味する。
【００３６】
【数１】
2019244756.tif 000003
【００３７】
なお、ベクトルk'の各要素は、ビット分解されたものであってもよい。すなわち、ベクトルk'の各要素は、その各要素が0,1のビットで表現されたものであってもよい。
【００３８】
＜ステップＳ３＞
第一置換適用部１３1,…,１３Nに、シェア[k']及びシェア{{σ}}が入力される。
【００３９】
第一置換適用部１３1,…,１３Nは、[k']に{{σ}}を適用して[σ(k')]を得る。
【００４０】
より詳細には、第一置換適用部１３1,…,１３Nは、シェア[k']及びシェア{{σ}}を用いて、ベクトルk'に置換σを適用したベクトルσ(k')のシェア[σ(k')]を生成する（ステップＳ３）。
【００４１】
生成されたシェア[σ(k')]は、第一ベクトル生成部１４1,…,１４Nに出力される。
【００４２】
例えば、ベクトルk'=(1,2,3,1,3,4,5)Tであり、置換σが上記の式（１）で表される置換であるとする。この場合、ベクトルσ(k')=(1,1,2,3,3,4,5)Tとなる。
【００４３】
＜ステップＳ４＞
第一ベクトル生成部１４1,…,１４Nに、シェア[σ(k')]が入力される。
【００４４】
第一ベクトル生成部１４1,…,１４Nは、[ei]:=[σ(k')i=σ(k')i+1]ただし[em0+m1-1]:=[0]なる[e]を得る。iを０以上の整数として、eiはベクトルeのi番目の要素を意味し、σ(k')iはベクトルσ(k')のi番目の要素を意味する。このように、iを０以上の整数として、ベクトルの下付きのiは、そのベクトルのi番目の要素を意味する。":="は、":="の左の変数に":="の右の値を代入することを意味する。例えば、a:=bは、変数aにbの値を代入することを意味する。
【００４５】
なお、ベクトルの要素数をMとすると、ベクトルの最初の要素を０番目の要素と呼び、ベクトルの次の要素を１番目の要素と呼び、ベクトルの最後の要素をM-1番目の要素と呼ぶことにする。
【００４６】
より詳細には、第一ベクトル生成部１４1,…,１４Nは、シェア[σ(k')]を用いて、ベクトルσ(k')のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する（ステップＳ４）。ただし、ベクトルeの最後の要素は０であるとする。
【００４７】
生成されたシェア[e]は、第二ベクトル生成部１５1,…,１５Nに出力される。
【００４８】
例えば、ベクトルσ(k')=(1,1,2,3,3,4,5)Tであるとする。この場合、ベクトルe=(1,0,0,1,0,0,0)Tとなる。
【００４９】
＜ステップＳ５＞
第二ベクトル生成部１５1,…,１５Nに、シェア[e]が入力される。
【００５０】
第二ベクトル生成部１５1,…,１５Nは、[e'i]=[ei(+)ei-1]ただし[e'0]=[e0]なる[e']を得る。(+)は、排他的論理和又は加算である。
【００５１】
より詳細には、第二ベクトル生成部１５1,…,１５Nは、シェア[e]を用いて、ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルe'のシェア[e']を生成する（ステップＳ５）。ただし、ベクトルe'の最初の要素は、ベクトルeの最初の要素と同じであるとする。
【００５２】
生成されたシェア[e']は、ビット反転部１６1,…,１６Nに出力される。
【００５３】
例えば、ベクトルe=(1,0,0,1,0,0,0)Tであるとする。この場合、ベクトルe'=(1,1,0,1,1,0,0)Tとなる。
【００５４】
＜ステップＳ６＞
ビット反転部１６1,…,１６Nに、シェア[e']が入力される。
【００５５】
ビット反転部１６1,…,１６Nは、[e']のビット反転[e'']を得る。
【００５６】
より詳細には、ビット反転部１６1,…,１６Nは、シェア[e']を用いて、ベクトルe'の各要素をビット反転させたベクトルe''のシェア[e'']を生成する（ステップＳ６）。
【００５７】
生成されたシェア[e'']は、第二置換計算部１７1,…,１７N及び第二置換適用部１８1,…,１８Nに出力される。
【００５８】
例えば、e'=(1,1,0,1,1,0,0)Tであるとする。この場合、ベクトルe''=(0,0,1,0,0,1,1)Tとなる。
【００５９】
なお、ベクトルk'の各要素がビット分解されたものであった場合には、例えばmod P変換により、e''の環が変更されてもよい。Pは、３以上の素数である。mod P変換は、例えば参考文献１のScheme 5に記載された手法により実現することができる。
【００６０】
＜ステップＳ７＞
第二置換計算部１７1,…,１７Nに、シェア[e'']が入力される。
【００６１】
第二置換計算部１７1,…,１７Nは、[e'']のソート{{σ'}}を得る。
【００６２】
より詳細には、第二置換計算部１７1,…,１７Nは、シェア[e'']を用いて、ベクトルe''を昇順に安定ソートする置換σ'のシェア{{σ'}}を生成する（ステップＳ７）。
【００６３】
生成されたシェア{{σ'}}は、第二置換適用部１８1,…,１８N及び逆置換適用部１１０1,…, １１０Nに出力される。
【００６４】
例えば、ベクトルe''=(0,0,1,0,0,1,1)Tであるとする。この場合、置換σ'は以下の式（２）のようになる。
【００６５】
【数２】
2019244756.tif 000004
【００６６】
＜ステップＳ８＞
第二置換適用部１８1,…,１８Nに、シェア[e'']及びシェア{{σ'}}が入力される。
【００６７】
第二置換適用部１８1,…,１８Nは、[e'']に{{σ'}}を適用して[σ'(e'')]を得る。
【００６８】
より詳細には、第二置換適用部１８1,…,１８Nは、シェア[e'']及びシェア{{σ'}}を用いて、ベクトルe''に置換σ'を適用したベクトルσ'(e'')のシェア[σ'(e'')]を生成する（ステップＳ８）。
【００６９】
生成されたシェア[σ'(e'')]は、第三ベクトル生成部１９1,…,１９Nに出力される。
【００７０】
例えば、ベクトルe''=(0,0,1,0,0,1,1)Tであり、置換σ'が上記の式（２）により表される置換であるとする。この場合、ベクトルσ'(e'')=(0,0,0,0,1,1,1)Tとなる。
【００７１】
＜ステップＳ９＞
第三ベクトル生成部１９1,…,１９Nに、シェア[σ'(e'')]が入力される。
【００７２】
第三ベクトル生成部１９1,…,１９Nは、[x]:=[σ'(e'')i?0:└i/2┘+1]を得る。
【００７３】
より詳細には、第三ベクトル生成部１９1,…,１９Nは、シェア[σ'(e'')]を用いて、ベクトルσ'(e'')のある要素iが、０である場合には└i/2┘を、０でない場合には０をそのある要素iに対応する要素として持つベクトルxのシェア[x]を生成する（ステップＳ９）。
【００７４】
ここで、i=0,…,m0+m1-1であり、└i/2┘は、i/2以下の最大の整数を意味する。
【００７５】
生成されたシェア[x]は、逆置換適用部１１０1,…,１１０Nに出力される。
【００７６】
例えば、ベクトルσ'(e'')=(0,0,0,0,1,1,1)Tであるとする。この場合、ベクトルx=(1,1,2,2,0,0,0)Tとなる。
【００７７】
＜ステップＳ１０＞
逆置換適用部１１０1,…, １１０Nに、シェア[x]、シェア{{σ}}及びシェア{{σ'}}が入力される。
【００７８】
逆置換適用部１１０1,…, １１０Nは、[x]に{{σ'}}と{{σ}}を逆適用して[σ-1(σ'-1(x))]を得る。
【００７９】
より詳細には、逆置換適用部１１０1,…, １１０Nは、シェア[x]、シェア{{σ}}及びシェア{{σ'}}を用いて、ベクトルxに置換σ'の逆置換σ'-1及び置換σの逆置換σ-1を適用したベクトルσ-1(σ'-1(x))のシェア[σ-1(σ'-1(x))]を生成する（ステップＳ１０）。
【００８０】
生成されたシェア[σ-1(σ'-1(x))]は、ベクトル分離部１１１1,…, １１１Nに出力される。
【００８１】
例えば、ベクトルx=(1,1,2,2,0,0,0)Tであり、置換σが上記の式（１）により表される置換であり、置換σ'が上記の式（２）により表される置換であるとする。この場合、ベクトルσ-1(σ'-1(x))= (1,0,2,1,2,0,0)Tとなる。
【００８２】
＜ステップＳ１１１＞
ベクトル分離部１１１1,…, １１１Nに、シェア[σ-1(σ'-1(x))]が入力される。
【００８３】
ベクトル分離部１１１1,…, １１１Nは、[σ-1(σ'-1(x))]を先頭からm0個の要素[s0]と残りのm1個の要素[s1]とに分離する。
【００８４】
より詳細には、ベクトル分離部１１１1,…, １１１Nは、シェア[σ-1(σ'-1(x))]を用いて、ベクトルσ-1(σ'-1(x))の先頭からm0個の要素からなるベクトルs0のシェア[s0]と、ベクトルσ-1(σ'-1(x))の残りのm1個の要素からなるベクトルs1のシェア[s1]とを生成する（ステップＳ１１）。
【００８５】
生成されたシェア[s0]及びシェア[s1]は、第三置換適用部１１２1,…, １１２Nに出力される。
【００８６】
例えば、ベクトルσ-1(σ'-1(x))=(1,0,2,1,2,0,0)Tであるとする。この場合、ベクトルs0=(1,0,2)T、ベクトルs1=(1,2,0,0)Tとなる。
【００８７】
ベクトルs0,s1は、第一テーブルと第二テーブルで重複するキーの位置を示している。例えば、第一テーブルのキーのベクトルがk0=(1,2,3)Tであり、第二テーブルのキーのベクトルがk1=(1,3,4,5)Tであるとする。この場合、ベクトルs0=(1,0,2)T、ベクトルs1=(1,2,0,0)Tとなる。第一テーブルと第二テーブルで重複するキーは、「1」「3」である。ベクトルs0=(1,0,2)T及びベクトルs1=(1,2,0,0)Tは、それぞれベクトルk0=(1,2,3)T及びk1=(1,3,4,5)Tの中の「1」「3」の位置を示している。
【００８８】
＜ステップＳ１２＞
第三置換適用部１１２1,…, １１２Nに、シェア[s0]及びシェア[s1]が入力される。
【００８９】
第三置換適用部１１２1,…, １１２Nは、[π0(s0)],[π1(s1)]を得て、τ0:=π0(s0),τ1:=π1(s1)を公開する。
【００９０】
より詳細には、第三置換適用部１１２1,…, １１２Nは、シェア[s0]、シェア[s1]及び置換π0,π1を用いて、ベクトルs0に置換π0を適用したベクトルτ0:=π0(s0)のシェア[π0(s0)]と、ベクトルs1に置換π1を適用したベクトルτ1:=π1(s1)のシェア[π1(s1)]とを生成して、ベクトルτ0及びベクトルτ1を公開する（ステップＳ１２）。ベクトルτ0及びベクトルτ1は、秘密計算装置１n（1≦n≦N）に公開される。
【００９１】
置換π0,π1は、所定の置換であり、例えばランダム置換である。置換π0,π1は、予め定められた置換であってもよいし、ステップＳ１２の処理をする際に生成されてもよい。置換π0,π1及びこれらのシェア{{π0}},{{π1}}は、例えば参考文献１の4.1節に記載された手法により生成することができる。秘密計算装置１n（1≦n≦N）は、置換π0,π1及びこれらのシェア{{π0}},{{π1}}についての情報を有しており、置換π0,π1及びこれらのシェア{{π0}},{{π1}}を用いて計算が可能であるとする。
【００９２】
生成されたシェア[π0(s0)]及びシェア[π1(s1)]は、属性値置換部１１３1,…, １１３Nに出力される。
【００９３】
例えば、ベクトルs0=(1,0,2)T、ベクトルs1=(1,2,0,0)Tであり、π0が以下の式（３）により表される置換であり、π1が以下の式（４）により表される置換であるとする。
【００９４】
【数３】
2019244756.tif 000005
【００９５】
この場合、ベクトルτ0=(0,2,1)T、ベクトルτ1=(0,1,0,2)Tとなる。
【００９６】
＜ステップＳ１３＞
属性値置換部１１３1,…, １１３Nに、シェア[v0,p]及びシェア[v1,q]が入力される。
【００９７】
属性値置換部１１３1,…, １１３Nは、第一テーブルの各属性値を{{π0}}、第二テーブルの各属性値{{π1}}により置換する。
【００９８】
より詳細には、属性値置換部１１３1,…, １１３Nは、置換π0のシェア{{π0}}、置換π1のシェア{{π1}}、ベクトルv0,pのシェア[v0,p]及びベクトルv1,qのシェア[v1,q]を用いて、第一テーブルの各属性p(p=0,…,m0-1)の属性値のベクトルv0,pを置換π0で置換したベクトルv'0,pのシェア[v'0,p]と、第二テーブルの各属性q(q=0,…,m1-1)の属性値のベクトルv1,qを置換π1で置換したベクトルv'1,qのシェア[v'1,q]とを生成する（ステップＳ１３）。
【００９９】
生成されたシェア[v'0,p]及びシェア[v'1,q]は、第四ベクトル生成部１１４1,…,１１４Nに出力される。
【０１００】
例えば、第一テーブルの属性z1のベクトルv0,1=(5,10,1)Tであり、第二テーブルの属性z1'のベクトルv1,1=(2,4,9,8)Tであり、π0が上記の式（３）により表される置換であり、π1が上記の式（４）により表される置換であるとする。この場合、ベクトルv'0,1=(10,1,5)T、ベクトルv'1,1=(9,2,8,4)Tとなる。
【０１０１】
＜ステップＳ１４＞
第四ベクトル生成部１１４1,…,１１４Nに、ベクトルτ0、ベクトルτ1、シェア[v'0,p]及びシェア[v'1,q]が入力される。
【０１０２】
第四ベクトル生成部１１４1,…,１１４Nは、i=1,2として、置換した各属性値[v'i,j]について(τi)i'≠0のときに[(v''i,j)(τi)i'-1]:=[(v'i,j)i']とする[(v''i,j)]を得る。
【０１０３】
より詳細には、第四ベクトル生成部１１４1,…,１１４Nは、ベクトルτ0、ベクトルτ1、シェア[v'0,p]及びシェア[v'1,q]を用いて、ベクトルτ0のi'番目の要素が０でない場合にはベクトルv'0,pのi'番目の要素をi'-1番目の要素として持つベクトルv''0,pのシェア[v''0,p]と、ベクトルτ1のi'番目の要素が０でない場合にはベクトルv'1,qのi'番目の要素をi'-1番目の要素として持つベクトルv''1,qのシェア[v''1,q]とを生成する（ステップＳ１４）。第四ベクトル生成部１１４1,…,１１４Nは、この処理を各p(p=0,…,L0-1)及び各q(q=0,…,L1-1)に対して行う。
【０１０４】
例えば、ベクトルτ0=(0,2,1)T、ベクトルv'0,1=(10,1,5)T、ベクトルτ1=(0,1,0,2)T、ベクトルv'1,1=(9,2,8,4)Tであるとする。この場合、ベクトルv''0,1=(5,1)T、ベクトルv''1,1=(2,4)Tとなる。
【０１０５】
ベクトルs0,s1は第一テーブルと第二テーブルで重複するキーの位置を示しているため、ベクトルs0,s1をそれぞれ置換π0,π1により置換したベクトルτ0,τ1は、置換π0,π1による置換後の第一テーブルと第二テーブルで重複するキーの位置を示している。
【０１０６】
上記の例では、ベクトルτ0=(0,2,1)Tの２番目の要素「1」は置換π0による置換後の第一テーブルのキー「1」の位置を示し、ベクトルτ0=(0,2,1)Tの１番目の要素「2」は置換π0による置換後の第一テーブルのキー「3」の位置を示している。
【０１０７】
同様に、上記の例では、ベクトルτ1=(0,1,0,2)Tの１番目の要素「1」は置換π1による置換後の第二テーブルのキー「1」の位置を示し、ベクトルτ1=(0,1,0,2)Tの３番目の要素「2」は置換π1による置換後の第二テーブルのキー「3」の位置を示している。
【０１０８】
このため、(τi)i'≠0のときに[(v''i,j)(τi)i'-1]:=[(v'i,j)i']とすることにより、第一テーブルのキー「1」のレコードの属性z1の属性値「5」をベクトルv''0,1=(5,1)Tの０番目の要素とし、第一テーブルのキー「3」のレコードの属性z1の属性値「1」をベクトルv''0,1=(5,1)Tの１番目の要素とすることができる。
【０１０９】
また、第二テーブルのキー「1」のレコードの属性z1'の属性値「2」をベクトルv''1,1=(2,4)Tの０番目の要素とし、第二テーブルのキー「3」のレコードの属性z1'の属性値「4」をベクトルv''1,1=(2,4)Tの１番目の要素とすることができる。
【０１１０】
言い換えれば、ベクトルv''0,1=(5,1)Tの０番目の要素「5」は第一テーブルのキー「1」のレコードの属性z1の属性値であり、ベクトルv''0,1=(5,1)Tの１番目の要素「1」は、第一テーブルのキー「3」のレコードの属性z1の属性値である。
【０１１１】
また、ベクトルv''1,1=(2,4)Tの０番目の要素「2」は第二テーブルのキー「1」のレコードの属性z1'の属性値であり、ベクトルv''1,1=(2,4)Tの１番目の要素「4」は第二テーブルのキー「3」のレコードの属性z1'の属性値である。
【０１１２】
このように、ベクトルv''0,1=(5,1)T、ベクトルv''1,1=(2,4)Tは、第一テーブル及び第二テーブルの共通するキー「1」「3」についての、第一テーブルの属性値及び第二テーブルの属性値を表していると言える。
【０１１３】
この実施形態によれば、秘匿性を保ったまま、第一テーブル及び第二テーブルの共通するキーについての、第一テーブルの属性値及び第二テーブルの属性値を得ることができる。
【０１１４】
［変形例］
なお、xを2以上の正の整数として、キーの属性が、x個の属性の複合キーであってもよい。この場合には、例えば以下のようにしてステップＳ１の処理を行ってもよい。
【０１１５】
第一テーブルのキーは、k0,0,…,k0,x-1であるとする。第二テーブルのキーは、k1,0,…,k1,x-1であるとする。
【０１１６】
この場合、ステップＳ１の処理で、各i(ただしi=0,…,x-1)でk0,iとk1,iを結合してk'iを得る。そして、各k'iをビット分解してビット表現にし、横に結合する。例えばk'0=(1,2,3,1,3,0,1)T,k'1=(0,0,0,0,0,1,1)Tのとき、k'0をビット分解すると、(k'0)0=(1,0,1,1,1,0,1)T,(k'0)1=(0,1,1,0,1,0,0)Tとなる。
【０１１７】
ここで、k'0は1から3の値を取るため、k'0の各要素は2ビットで表現することができる。(k'0)0はk'0をビット分解したときの下位ビットであり、(k'0)1はk'0をビット分解したときの上位ビットである。k'1はこの例ではもともと1ビット数であるので分解する必要はなく、k'1=(k'1)0とする。(k'0)0,(k'0)1,(k'1)0を横に結合すると、
【０１１８】
【数４】
2019244756.tif 000006
【０１１９】
となる。このようにして並べたものを行列とみなし、この行列の各行を1レコードのキーのビット表現とみなすと、(1,2,3,1,3,4,5)というキーのビット表現のベクトルが得られる。このベクトルをステップＳ２以降で使うk'として用いてもよい。このようにして、複合キーの場合も処理できる。
【０１２０】
複合キーでは、キーの重複とは、全てのキー属性の値の組み合わせの観点で重複するかどうかであり、個々の属性の値が重複しただけでは重複とはみなさないとする。例えば、組み合わせ(1,0)と(1,1)は重複ではない。
【０１２１】
以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。
【０１２２】
実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１２３】
［プログラム、記録媒体］
上述の各種の処理は、図４に示すコンピュータの記録部２０２０に、上記方法の各ステップを実行させるプログラムを読み込ませ、制御部２０１０、入力部２０３０、出力部２０４０などに動作させることで実施できる。
【０１２４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２５】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019244756.tif 000007
【図２】
2019244756.tif 000008
【図３】
2019244756.tif 000009
【図４】
2019244756.tif 000010
【手続補正書】
【提出日】令和2年12月14日(2020.12.14)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
＜ステップＳ１１＞
ベクトル分離部１１１1,…, １１１Nに、シェア[σ-1(σ'-1(x))]が入力される。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の秘密計算装置を含む秘密結合システムであって、
Fは任意の環であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、m0,m1,L0,L1は１以上の整数であり、k0∈Fm0は第一テーブルのキーのベクトルであり、k1∈Fm1は第二テーブルのキーのベクトルであり、p=0,…,L0-1としてv0,p∈Fm0は上記第一テーブルの属性pの属性値のベクトルであり、q=0,…,L1-1としてv1,q∈Fm1は上記第二テーブルの属性qの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
上記複数の秘密計算装置は、
上記ベクトルk0のシェア[k0]及び上記ベクトルk1のシェア[k1]を用いて、上記ベクトルk0及び上記ベクトルk1を結合したベクトルk'∈[F]m0+m1のシェア[k']を生成する複数のベクトル結合部と、
上記シェア[k']を用いて、上記ベクトルk'を昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の第一置換計算部と、
上記シェア[k']及び上記シェア{{σ}}を用いて、上記ベクトルk'に上記置換σを適用したベクトルσ(k')のシェア[σ(k')]を生成する複数の第一置換適用部と、
上記シェア[σ(k')]を用いて、上記ベクトルσ(k')のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数の第一ベクトル生成部と、
上記シェア[e]を用いて、上記ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルe'のシェア[e']を生成する複数の第二ベクトル生成部と、
上記シェア[e']を用いて、上記ベクトルe'の各要素をビット反転させたベクトルe''のシェア[e'']を生成する複数のビット反転部と、
上記シェア[e'']を用いて、上記ベクトルe''を昇順に安定ソートする置換σ'のシェア{{σ'}}を生成する複数の第二置換計算部と、
上記シェア[e'']及び上記シェア{{σ'}}を用いて、上記ベクトルe''に上記置換σ'を適用したベクトルσ'(e'')のシェア[σ'(e'')]を生成する複数の第二置換適用部と、
上記シェア[σ'(e'')]を用いて、上記ベクトルσ'(e'')のある要素iが、０である場合には└i/2┘を、０でない場合には０をそのある要素iに対応する要素として持つベクトルxのシェア[x]を生成する複数の第三ベクトル生成部と、
上記シェア[x]、上記シェア{{σ}}及び上記シェア{{σ'}}を用いて、上記ベクトルxに上記置換σ'の逆置換σ'-1及び上記置換σの逆置換σ-1を適用したベクトルσ-1(σ'-1(x))のシェア[σ-1(σ'-1(x))]を生成する複数の逆置換適用部と、
上記シェア[σ-1(σ'-1(x))]を用いて、上記ベクトルσ-1(σ'-1(x))の先頭からm0個の要素からなるベクトルs0のシェア[s0]と、上記ベクトルσ-1(σ'-1(x))の残りのm1個の要素からなるベクトルs1のシェア[s1]とを生成する複数のベクトル分離部と、
上記シェア[s0]、上記シェア[s1]及び上記置換π0,π1を用いて、上記ベクトルs0に上記置換π0を適用したベクトルτ0:=π0(s0)のシェア[π0(s0)]と、上記ベクトルs1に上記置換π1を適用したベクトルτ1:=π1(s1)のシェア[π1(s1)]とを生成して、τ0:=π0(s0)及びτ1:=π1(s1)を公開する複数の第三置換適用部と、
上記置換π0のシェア{{π0}}、上記置換π1のシェア{{π1}}、上記ベクトルv0,pのシェア[v0,p]及び上記ベクトルv1,qのシェア[v1,q]を用いて、上記第一テーブルの各属性pの属性値のベクトルv0,pを上記置換π0で置換したベクトルv'0,pのシェア[v'0,p]と、上記第二テーブルの各属性qの属性値のベクトルv1,qを上記置換π1で置換したベクトルv'1,qのシェア[v'1,q]とを生成する複数の属性値置換部と、
上記ベクトルτ0、上記ベクトルτ1、上記シェア[v'0,p]及び上記シェア[v'1,q]を用いて、上記ベクトルτ0のi'番目の要素が０でない場合には上記ベクトルv'0,pのi'番目の要素をi'-1番目の要素として持つベクトルv''0,pのシェア[v''0,p]と、上記ベクトルτ1のi'番目の要素が０でない場合には上記ベクトルv'1,qのi'番目の要素をi'-1番目の要素として持つベクトルv''1,qのシェア[v''1,q]とを生成する複数の第四ベクトル生成部と、
を含む秘密結合システム。
【請求項２】
請求項１の秘密結合システムの秘密計算装置。
【請求項３】
Fは任意の環であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、m0,m1,L0,L1は１以上の整数であり、k0∈Fm0は第一テーブルのキーのベクトルであり、k1∈Fm1は第二テーブルのキーのベクトルであり、p=0,…,L0-1としてv0,p∈Fm0は上記第一テーブルの属性pの属性値のベクトルであり、q=0,…,L1-1としてv1,q∈Fm1は上記第二テーブルの属性qの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
複数のベクトル結合部が、上記ベクトルk0のシェア[k0]及び上記ベクトルk1のシェア[k1]を用いて、上記ベクトルk0及び上記ベクトルk1を結合したベクトルk'∈[F]m0+m1のシェア[k']を生成するベクトル結合ステップと、
複数の第一置換計算部が、上記シェア[k']を用いて、上記ベクトルk'を昇順に安定ソートする置換σのシェア{{σ}}を生成する第一置換計算ステップと、
複数の第一置換適用部が、上記シェア[k']及び上記シェア{{σ}}を用いて、上記ベクトルk'に上記置換σを適用したベクトルσ(k')のシェア[σ(k')]を生成する第一置換適用ステップと、
複数の第一ベクトル生成部が、上記シェア[σ(k')]を用いて、上記ベクトルσ(k')のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する第一ベクトル生成ステップと、
複数の第二ベクトル生成部が、上記シェア[e]を用いて、上記ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルe'のシェア[e']を生成する第二ベクトル生成ステップと、
複数のビット反転部が、上記シェア[e']を用いて、上記ベクトルe'の各要素をビット反転させたベクトルe''のシェア[e'']を生成するビット反転ステップと、
複数の第二置換計算部が、上記シェア[e'']を用いて、上記ベクトルe''を昇順に安定ソートする置換σ'のシェア{{σ'}}を生成する第二置換計算ステップと、
複数の第二置換適用部が、上記シェア[e'']及び上記シェア{{σ'}}を用いて、上記ベクトルe''に上記置換σ'を適用したベクトルσ'(e'')のシェア[σ'(e'')]を生成する第二置換適用ステップと、
複数の第三ベクトル生成部が、上記シェア[σ'(e'')]を用いて、上記ベクトルσ'(e'')のある要素iが、０である場合には└i/2┘を、０でない場合には０をそのある要素iに対応する要素として持つベクトルxのシェア[x]を生成する第三ベクトル生成ステップと、
複数の逆置換適用部が、上記シェア[x]、上記シェア{{σ}}及び上記シェア{{σ'}}を用いて、上記ベクトルxに上記置換σ'の逆置換σ'-1及び上記置換σの逆置換σ-1を適用したベクトルσ-1(σ'-1(x))のシェア[σ-1(σ'-1(x))]を生成する逆置換適用ステップと、
複数のベクトル分離部が、上記シェア[σ-1(σ'-1(x))]を用いて、上記ベクトルσ-1(σ'-1(x))の先頭からm0個の要素からなるベクトルs0のシェア[s0]と、上記ベクトルσ-1(σ'-1(x))の残りのm1個の要素からなるベクトルs1のシェア[s1]とを生成するベクトル分離ステップと、
複数の第三置換適用部が、上記シェア[s0]、上記シェア[s1]及び上記置換π0,π1を用いて、上記ベクトルs0に上記置換π0を適用したベクトルτ0:=π0(s0)のシェア[π0(s0)]と、上記ベクトルs1に上記置換π1を適用したベクトルτ1:=π1(s1)のシェア[π1(s1)]とを生成して、τ0:=π0(s0)及びτ1:=π1(s1)を公開する第三置換適用ステップと、
複数の属性値置換部が、上記置換π0のシェア{{π0}}、上記置換π1のシェア{{π1}}、上記ベクトルv0,pのシェア[v0,p]及び上記ベクトルv1,qのシェア[v1,q]を用いて、上記第一テーブルの各属性pの属性値のベクトルv0,pを上記置換π0で置換したベクトルv'0,pのシェア[v'0,p]と、上記第二テーブルの各属性qの属性値のベクトルv1,qを上記置換π1で置換したベクトルv'1,qのシェア[v'1,q]とを生成する属性値置換ステップと、
複数の第四ベクトル生成部が、上記ベクトルτ0、上記ベクトルτ1、上記シェア[v'0,p]及び上記シェア[v'1,q]を用いて、上記ベクトルτ0のi'番目の要素が０でない場合には上記ベクトルv'0,pのi'番目の要素をi'-1番目の要素として持つベクトルv''0,pのシェア[v''0,p]と、上記ベクトルτ1のi'番目の要素が０でない場合には上記ベクトルv'1,qのi'番目の要素をi'-1番目の要素として持つベクトルv''1,qのシェア[v''1,q]とを生成する第四ベクトル生成ステップと、
を含む秘密結合方法。
【請求項４】
請求項２の秘密計算装置の各部としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2019244756.tif 000011
2019244756.tif 000012
2019244756.tif 000013
2019244756.tif 000014