(57)【要約】  秘密結合システムは、複数の秘密計算装置を含む秘密結合システムであって、複数の秘密計算装置は、ベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n及び第二ベクトル分離部１１４n、第三置換適用部１１５n、第四置換適用部１１６n及び第一結合テーブル生成部１１７nを備えている。
2020036127.tif 000002
【特許請求の範囲】
【請求項１】
複数の秘密計算装置を含む秘密結合情報生成システムであって、
Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は上記第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は上記第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
上記複数の秘密計算装置は、
上記ベクトルk0のシェア[k0]及び上記ベクトルk1のシェア[k1]を用いて、上記ベクトルk0及び上記ベクトルk1を結合したベクトルk∈[Fk]m0+m1のシェア[k]を生成する複数のベクトル結合部と、
m0個の０と、m1個の１とを結合したベクトルfのシェア[f]を生成する複数の第一ベクトル生成部と、
上記シェア[k]を用いて、上記ベクトルkを安定ソートする置換σのシェア[σ]を生成する複数の第一置換計算部と、
上記シェア[k]、上記シェア[σ]及び上記シェア[f]を用いて、上記ベクトルkに上記置換σを適用したベクトルσ(k)のシェア[σ(k)]と、上記ベクトルfに上記置換σを適用したベクトルσ(f)のシェア[σ(f)]とを生成する複数の第一置換適用部と、
上記シェア[σ(k)]を用いて、上記ベクトルσ(k)のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数の第二ベクトル生成部と、
上記シェア[e]を用いて、上記ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルの各要素をビット反転させたベクトルe'のシェア[e']を生成する複数の第三ベクトル生成部と、
上記シェア[e']を用いて、上記ベクトルe'を安定ソートする置換σ'のシェア[σ']を生成する複数の第二置換計算部と、
上記シェア[σ(f)]及び上記シェア[σ']を用いて、上記ベクトルσ(f)に上記置換σ'を適用したベクトルf'=σ'(σ(f))のシェア[f']を生成する複数の第二置換適用部と、
上記シェア[f']を用いて、各要素が、上記ベクトルf'のその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルsのシェア[s]と、上記ベクトルf'の各要素をビット反転させたベクトルをビット反転ベクトルとして、各要素が、上記ビット反転ベクトルのその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルs'のシェア[s']とを生成する複数の第四ベクトル生成部と、
上記シェア[f']、上記シェア[s]及び上記シェア[s']を用いて、ベクトルσ''=f's+(1-f')s'-1のシェア[σ'']を計算する複数の第五ベクトル生成部と、
上記シェア[e']及び上記シェア[σ]を用いて、上記ベクトルe'に上記置換σの逆置換σ-1を適用したベクトルe''=σ-1(e')のシェア[e'']を生成する複数の第一逆置換適用部と、
上記シェア[e'']を用いて、上記ベクトルe''の先頭からm0個の要素からなるベクトルg0のシェア[g0]と、上記ベクトルe''の残りのm1個の要素からなるベクトルg1のシェア[g1]とを生成する複数の第一ベクトル分離部と、
上記シェア[σ'']、上記シェア[σ]及び上記シェア[σ']を用いて、上記ベクトルxに上記置換σ'の逆置換σ'-1及び上記置換σの逆置換σ-1を適用したベクトルσ'''-1=σ-1(σ'-1(σ''))のシェア[σ'''-1]を生成する複数の第二逆置換適用部と、
上記シェア[σ'''-1]を用いて、上記ベクトルσ'''-1の先頭からm0個の要素からなるベクトルσ0-1のシェア[σ0-1]と、上記ベクトルσ'''-1の残りのm1個の要素からなるベクトルσ1-1のシェア[σ1-1]とを生成する複数の第二ベクトル分離部と、
上記シェア[σ0-1]、上記シェア[σ１-1]及び上記置換π0のシェア[π0]及び上記置換π1のシェア[π1]を用いて、上記ベクトルσ0-1に上記置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、上記ベクトルσ１-1に上記置換π1を適用したベクトルπ1(σ１-1)のシェア[π1(σ１-1)]とを生成して、π0(σ０-1)及びπ1(σ１-1)を公開する複数の第三置換適用部と、
を含む秘密結合情報生成システム。
【請求項２】
請求項１の秘密結合情報生成システムの複数の秘密計算装置を含み、
上記複数の秘密計算装置は、
上記ベクトルk0のシェア[k0]、上記ベクトルv0のシェア[v0]、上記ベクトルk1のシェア[k1]及び上記ベクトルv1のシェア[v1]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1'=(π1(σ1-1))-1(π1(k1'))のシェア[k1']と、ベクトルv1'=(π1(σ1-1))-1(π1(v1'))のシェア[v1']とを計算する複数の第四置換適用部と、
上記シェア[k0']、上記シェア[v0']、上記シェア[k1']及び上記シェア[v1']を用いて、上記ベクトルg0又は上記ベクトルg1の０の要素の数をcとして、上記ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合した結合テーブルを生成する複数の第一結合テーブル生成部と、
を更に含む秘密結合システム。
【請求項３】
複数の秘密計算装置を含む秘密結合システムであって、
Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は上記第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は上記第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
上記複数の秘密計算装置は、
上記ベクトルk0のシェア[k0]、上記ベクトルk1のシェア[k1]、上記置換π0のシェア[π0]及び上記置換π1のシェア[π1]を用いて、上記第一テーブルの各ベクトルを置換σ0で置換すると上記第一テーブルと上記第二テーブルに共通するキーのレコードが先頭側に移動する置換σ0の逆置換σ0-1に上記置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、上記第二テーブルの各ベクトルを置換σ1で置換すると上記第一テーブルと上記第二テーブルに共通するキーのレコードが先頭側に移動する置換σ1の逆置換σ1-1に上記置換π1を適用したベクトルπ1(σ1-1)のシェア[π1(σ1-1)]と、上記第一テーブルのi番目のレコードが、上記第一テーブルと上記第二テーブルに共通するキーのレコードかどうかを表す値g0,iから構成されるベクトルg0のシェア[g0]と、上記第二テーブルのi番目のレコードが、上記第一テーブルと上記第二テーブルに共通するキーのレコードかどうかを表す値g1,iから構成されるベクトルg1のシェア[g1]と、を生成する複数の秘密結合情報生成部と、
上記シェア[g1]、上記ベクトルk1のシェア[k1]及び上記ベクトルv1のシェア[v1]を用いて、上記ベクトルg1のi番目の要素をg1,iとして、g1,i=1である場合には、上記第二テーブルのキーのi番目の要素を予め定めた空を示す値u1,kとし、上記第二テーブルの属性のi番目の要素を予め定めた空を示す値u1,vとした変形第二テーブルを生成する複数のフィルタリング部と、
上記ベクトルk0のシェア[k0]、上記ベクトルv0のシェア[v0]、上記変形第二テーブルのキーのベクトルであるk1'のシェア[k1']、上記変形第二テーブルの属性値のベクトルであるv1'のシェア[v1']、上記置換π0のシェア[π0]、上記置換π1のシェア[π1]、上記シェア[π0(σ0-1)]及び上記シェア[π1(σ1-1)]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1''=(π1(σ1-1))-1(π1(k1'))のシェア[k1'']と、ベクトルv1''=(π1(σ1-1))-1(π1(v1'))のシェア[v1'']とを計算する複数の第五置換適用部と、
上記シェア[k0']、上記シェア[v0']、上記シェア[k1'']及び上記シェア[v1'']を用いて、m0<m1である場合には、上記ベクトルk0'と、上記ベクトルv0'と、上記ベクトルk1''の先頭からm0個の要素を抜き出したベクトルと、上記ベクトルv1''の先頭からm0個の要素を抜き出したベクトルとを結合した結合テーブルを、m0>m1である場合には、上記ベクトルk0'と、上記ベクトルv0'と、上記ベクトルk1''にm0-m1個の予め定めた空を示す値ukの要素を追加したベクトルと、上記ベクトルv1''にm0-m1個の予め定めた空を示す値uvの要素を追加したベクトルとを結合した結合テーブルを生成する複数の第二結合テーブル生成部と、
を含む秘密結合システム。
【請求項４】
複数の秘密計算装置を含む秘密結合システムであって、
Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は上記第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は上記第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
上記複数の秘密計算装置は、
上記ベクトルk0のシェア[k0]、上記ベクトルk1のシェア[k1]、上記置換π0のシェア[π0]及び上記置換π1のシェア[π1]を用いて、上記第一テーブルの各ベクトルを置換σ0で置換すると上記第一テーブルと上記第二テーブルに共通するキーのレコードが先頭側に移動する置換σ0の逆置換σ0-1に上記置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、上記第二テーブルの各ベクトルを置換σ1で置換すると上記第一テーブルと上記第二テーブルに共通するキーのレコードが先頭側に移動する置換σ1の逆置換σ1-1に上記置換π1を適用したベクトルπ1(σ1-1)のシェア[π1(σ1-1)]と、上記第一テーブルのi番目のレコードが、上記第一テーブルと上記第二テーブルに共通するキーのレコードかどうかを表す値g0,iから構成されるベクトルg0のシェア[g0]と、上記第二テーブルのi番目のレコードが、上記第一テーブルと上記第二テーブルに共通するキーのレコードかどうかを表す値g1,iから構成されるベクトルg1のシェア[g1]と、を生成する複数の秘密結合情報生成部と、
上記ベクトルk0のシェア[k0]、上記ベクトルv0のシェア[v0]、上記ベクトルk1のシェア[k1]及び上記ベクトルv1のシェア[v1]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1'=(π1(σ1-1))-1(π1(k1'))のシェア[k1']と、ベクトルv1'=(π1(σ1-1))-1(π1(v1'))のシェア[v1']とを計算する複数の第四置換適用部と、
上記シェア[k0']、上記シェア[v0']、上記シェア[k1']及び上記シェア[v1']を用いて、上記ベクトルg0又は上記ベクトルg1の０の要素の数をcとして、上記ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合したテーブル(1)と、上記ベクトルk0'の残りm0-c個の要素を抜き出したベクトルと上記ベクトルv0'の残りm0-c個の要素を抜き出したベクトルと上記第二テーブルの属性値に対応する値を予め定めた空を示す値u'1,vとしたベクトルとを結合したテーブル(2)と、上記ベクトルv0'の残りm0-c個の要素を抜き出したベクトルと上記ベクトルv1'の残りm1-c個の要素を抜き出したベクトルと上記第一テーブルの属性値に対応する値を予め定めた空を示す値u'0,vとしたベクトルとを結合したテーブル(3)とを結合した結合テーブルを生成する複数の第三結合テーブル生成部と、
を含む秘密結合システム。
【請求項５】
請求項３又は４の秘密結合システムであって、
上記複数の秘密計算装置は、
上記ベクトルk0のシェア[k0]及び上記ベクトルk1のシェア[k1]を用いて、上記ベクトルk0及び上記ベクトルk1を結合したベクトルk∈[Fk]m0+m1のシェア[k]を生成する複数のベクトル結合部と、
m0個の０と、m1個の１とを結合したベクトルfのシェア[f]を生成する複数の第一ベクトル生成部と、
上記シェア[k]を用いて、上記ベクトルkを安定ソートする置換σのシェア[σ]を生成する複数の第一置換計算部と、
上記シェア[k]、上記シェア[σ]及び上記シェア[f]を用いて、上記ベクトルkに上記置換σを適用したベクトルσ(k)のシェア[σ(k)]と、上記ベクトルfに上記置換σを適用したベクトルσ(f)のシェア[σ(f)]とを生成する複数の第一置換適用部と、
上記シェア[σ(k)]を用いて、上記ベクトルσ(k)のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数の第二ベクトル生成部と、
上記シェア[e]を用いて、上記ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルの各要素をビット反転させたベクトルe'のシェア[e']を生成する複数の第三ベクトル生成部と、
上記シェア[e']を用いて、上記ベクトルe'を安定ソートする置換σ'のシェア[σ']を生成する複数の第二置換計算部と、
上記シェア[σ(f)]及び上記シェア[σ']を用いて、上記ベクトルσ(f)に上記置換σ'を適用したベクトルf'=σ'(σ(f))のシェア[f']を生成する複数の第二置換適用部と、
上記シェア[f']を用いて、各要素が、上記ベクトルf'のその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルsのシェア[s]と、上記ベクトルf'の各要素をビット反転させたベクトルをビット反転ベクトルとして、各要素が、上記ビット反転ベクトルのその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルs'のシェア[s']とを生成する複数の第四ベクトル生成部と、
上記シェア[f']、上記シェア[s]及び上記シェア[s']を用いて、ベクトルσ''=f's+(1-f')s'-1のシェア[σ'']を計算する複数の第五ベクトル生成部と、
上記シェア[e']及び上記シェア[σ]を用いて、上記ベクトルe'に上記置換σの逆置換σ-1を適用したベクトルe''=σ-1(e')のシェア[e'']を生成する複数の第一逆置換適用部と、
上記シェア[e'']を用いて、上記ベクトルe''の先頭からm0個の要素からなるベクトルg0のシェア[g0]と、上記ベクトルe''の残りのm1個の要素からなるベクトルg1のシェア[g1]とを生成する複数の第一ベクトル分離部と、
上記シェア[σ'']、上記シェア[σ]及び上記シェア[σ']を用いて、上記ベクトルxに上記置換σ'の逆置換σ'-1及び上記置換σの逆置換σ-1を適用したベクトルσ'''-1=σ-1(σ'-1(σ''))のシェア[σ'''-1]を生成する複数の第二逆置換適用部と、
上記シェア[σ'''-1]を用いて、上記ベクトルσ'''-1の先頭からm0個の要素からなるベクトルσ0-1のシェア[σ0-1]と、上記ベクトルσ'''-1の残りのm1個の要素からなるベクトルσ1-1のシェア[σ1-1]とを生成する複数の第二ベクトル分離部と、
上記シェア[σ0-1]、上記シェア[σ１-1]及び上記置換π0のシェア[π0]及び上記置換π1のシェア[π1]を用いて、上記ベクトルσ0-1に上記置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、上記ベクトルσ１-1に上記置換π1を適用したベクトルπ1(σ１-1)のシェア[π1(σ１-1)]とを生成して、π0(σ０-1)及びπ1(σ１-1)を公開する複数の第三置換適用部と、
を更に含む秘密結合システム。
【請求項６】
請求項１の秘密結合情報生成システム又は請求項２から５の何れかの秘密結合システムの秘密計算装置。
【請求項７】
Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は上記第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は上記第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
複数のベクトル結合部が、上記ベクトルk0のシェア[k0]及び上記ベクトルk1のシェア[k1]を用いて、上記ベクトルk0及び上記ベクトルk1を結合したベクトルk∈[Fk]m0+m1のシェア[k]を生成するベクトル結合ステップと、
複数の第一ベクトル生成部が、m0個の０と、m1個の１とを結合したベクトルfのシェア[f]を生成する第一ベクトル生成ステップと、
複数の第一置換計算部が、上記シェア[k]を用いて、上記ベクトルkを安定ソートする置換σのシェア[σ]を生成する第一置換計算ステップと、
複数の第一置換適用部が、上記シェア[k]、上記シェア[σ]及び上記シェア[f]を用いて、上記ベクトルkに上記置換σを適用したベクトルσ(k)のシェア[σ(k)]と、上記ベクトルfに上記置換σを適用したベクトルσ(f)のシェア[σ(f)]とを生成する第一置換適用ステップと、
複数の第二ベクトル生成部が、上記シェア[σ(k)]を用いて、上記ベクトルσ(k)のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する第二ベクトル生成ステップと、
複数の第三ベクトル生成部が、上記シェア[e]を用いて、上記ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルの各要素をビット反転させたベクトルe'のシェア[e']を生成する第三ベクトル生成ステップと、
複数の第二置換計算部が、上記シェア[e']を用いて、上記ベクトルe'を安定ソートする置換σ'のシェア[σ']を生成する第二置換計算ステップと、
複数の第二置換適用部が、上記シェア[σ(f)]及び上記シェア[σ']を用いて、上記ベクトルσ(f)に上記置換σ'を適用したベクトルf'=σ'(σ(f))のシェア[f']を生成する第二置換適用ステップと、
複数の第四ベクトル生成部が、上記シェア[f']を用いて、各要素が、上記ベクトルf'のその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルsのシェア[s]と、上記ベクトルf'の各要素をビット反転させたベクトルをビット反転ベクトルとして、各要素が、上記ビット反転ベクトルのその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルs'のシェア[s']とを生成する第四ベクトル生成ステップと、
複数の第五ベクトル生成部が、上記シェア[f']、上記シェア[s]及び上記シェア[s']を用いて、ベクトルσ''=f's+(1-f')s'-1のシェア[σ'']を計算する第五ベクトル生成ステップと、
複数の第一逆置換適用部が、上記シェア[e']及び上記シェア[σ]を用いて、上記ベクトルe'に上記置換σの逆置換σ-1を適用したベクトルe''=σ-1(e')のシェア[e'']を生成する第一逆置換適用ステップと、
複数の第一ベクトル分離部が、上記シェア[e'']を用いて、上記ベクトルe''の先頭からm0個の要素からなるベクトルg0のシェア[g0]と、上記ベクトルe''の残りのm1個の要素からなるベクトルg1のシェア[g1]とを生成する第一ベクトル分離ステップと、
複数の第二逆置換適用部が、上記シェア[σ'']、上記シェア[σ]及び上記シェア[σ']を用いて、上記ベクトルxに上記置換σ'の逆置換σ'-1及び上記置換σの逆置換σ-1を適用したベクトルσ'''-1=σ-1(σ'-1(σ''))のシェア[σ'''-1]を生成する第二逆置換適用ステップと、
複数の第二ベクトル分離部が、上記シェア[σ'''-1]を用いて、上記ベクトルσ'''-1の先頭からm0個の要素からなるベクトルσ0-1のシェア[σ0-1]と、上記ベクトルσ'''-1の残りのm1個の要素からなるベクトルσ1-1のシェア[σ1-1]とを生成する第二ベクトル分離ステップと、
複数の第三置換適用部が、上記シェア[σ0-1]、上記シェア[σ１-1]及び上記置換π0のシェア[π0]及び上記置換π1のシェア[π1]を用いて、上記ベクトルσ0-1に上記置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、上記ベクトルσ１-1に上記置換π1を適用したベクトルπ1(σ１-1)のシェア[π1(σ１-1)]とを生成して、π0(σ０-1)及びπ1(σ１-1)を公開する第三置換適用ステップと、
を含む秘密結合情報生成方法。
【請求項８】
請求項７の秘密結合情報生成システムの各ステップと、
複数の第四置換適用部が、上記ベクトルk0のシェア[k0]、上記ベクトルv0のシェア[v0]、上記ベクトルk1のシェア[k1]及び上記ベクトルv1のシェア[v1]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1'=(π1(σ1-1))-1(π1(k1'))のシェア[k1']と、ベクトルv1'=(π1(σ1-1))-1(π1(v1'))のシェア[v1']とを計算する第四置換適用ステップと、
複数の第一結合テーブル生成部が、上記シェア[k0']、上記シェア[v0']、上記シェア[k1']及び上記シェア[v1']を用いて、上記ベクトルg0又は上記ベクトルg1の０の要素の数をcとして、上記ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合した結合テーブルを生成する第一結合テーブル生成ステップと、
を含む秘密結合方法。
【請求項９】
Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は上記第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は上記第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
複数の秘密結合情報生成部が、上記ベクトルk0のシェア[k0]、上記ベクトルk1のシェア[k1]、上記置換π0のシェア[π0]及び上記置換π1のシェア[π1]を用いて、上記第一テーブルの各ベクトルを置換σ0で置換すると上記第一テーブルと上記第二テーブルに共通するキーのレコードが先頭側に移動する置換σ0の逆置換σ0-1に上記置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、上記第二テーブルの各ベクトルを置換σ1で置換すると上記第一テーブルと上記第二テーブルに共通するキーのレコードが先頭側に移動する置換σ1の逆置換σ1-1に上記置換π1を適用したベクトルπ1(σ1-1)のシェア[π1(σ1-1)]と、上記第一テーブルのi番目のレコードが、上記第一テーブルと上記第二テーブルに共通するキーのレコードかどうかを表す値g0,iから構成されるベクトルg0のシェア[g0]と、上記第二テーブルのi番目のレコードが、上記第一テーブルと上記第二テーブルに共通するキーのレコードかどうかを表す値g1,iから構成されるベクトルg1のシェア[g1]と、を生成する秘密結合情報生成ステップと、
複数のフィルタリング部が、上記シェア[g1]、上記ベクトルk1のシェア[k1]及び上記ベクトルv1のシェア[v1]を用いて、上記ベクトルg1のi番目の要素をg1,iとして、g1,i=1である場合には、上記第二テーブルのキーのi番目の要素を予め定めた空を示す値u1,kとし、上記第二テーブルの属性のi番目の要素を予め定めた空を示す値u1,vとした変形第二テーブルを生成するフィルタリングステップと、
複数の第五置換適用部が、上記ベクトルk0のシェア[k0]、上記ベクトルv0のシェア[v0]、上記変形第二テーブルのキーのベクトルであるk1'のシェア[k1']、上記変形第二テーブルの属性値のベクトルであるv1'のシェア[v1']、上記置換π0のシェア[π0]、上記置換π1のシェア[π1]、上記シェア[π0(σ0-1)]及び上記シェア[π1(σ1-1)]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1''=(π1(σ1-1))-1(π1(k1'))のシェア[k1'']と、ベクトルv1''=(π1(σ1-1))-1(π1(v1'))のシェア[v1'']とを計算する第五置換適用ステップと、
複数の第二結合テーブル生成部が、上記シェア[k0']、上記シェア[v0']、上記シェア[k1'']及び上記シェア[v1'']を用いて、m0<m1である場合には、上記ベクトルk0'と、上記ベクトルv0'と、上記ベクトルk1''の先頭からm0個の要素を抜き出したベクトルと、上記ベクトルv1''の先頭からm0個の要素を抜き出したベクトルとを結合した結合テーブルを、m0>m1である場合には、上記ベクトルk0'と、上記ベクトルv0'と、上記ベクトルk1''にm0-m1個の予め定めた空を示す値ukの要素を追加したベクトルと、上記ベクトルv1''にm0-m1個の予め定めた空を示す値uvの要素を追加したベクトルとを結合した結合テーブルを生成する第二結合テーブル生成ステップと、
を含む秘密結合方法。
【請求項１０】
Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は上記第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は上記第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、
複数の秘密結合情報生成部が、上記ベクトルk0のシェア[k0]、上記ベクトルk1のシェア[k1]、上記置換π0のシェア[π0]及び上記置換π1のシェア[π1]を用いて、上記第一テーブルの各ベクトルを置換σ0で置換すると上記第一テーブルと上記第二テーブルに共通するキーのレコードが先頭側に移動する置換σ0の逆置換σ0-1に上記置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、上記第二テーブルの各ベクトルを置換σ1で置換すると上記第一テーブルと上記第二テーブルに共通するキーのレコードが先頭側に移動する置換σ1の逆置換σ1-1に上記置換π1を適用したベクトルπ1(σ1-1)のシェア[π1(σ1-1)]と、上記第一テーブルのi番目のレコードが、上記第一テーブルと上記第二テーブルに共通するキーのレコードかどうかを表す値g0,iから構成されるベクトルg0のシェア[g0]と、上記第二テーブルのi番目のレコードが、上記第一テーブルと上記第二テーブルに共通するキーのレコードかどうかを表す値g1,iから構成されるベクトルg1のシェア[g1]と、を生成する秘密結合情報生成ステップと、
複数の第四置換適用部が、上記ベクトルk0のシェア[k0]、上記ベクトルv0のシェア[v0]、上記ベクトルk1のシェア[k1]及び上記ベクトルv1のシェア[v1]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1'=(π1(σ1-1))-1(π1(k1'))のシェア[k1']と、ベクトルv1'=(π1(σ1-1))-1(π1(v1'))のシェア[v1']とを計算する第四置換適用ステップと、
複数の第三結合テーブル生成部が、上記シェア[k0']、上記シェア[v0']、上記シェア[k1']及び上記シェア[v1']を用いて、上記ベクトルg0又は上記ベクトルg1の０の要素の数をcとして、上記ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、上記ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合したテーブル(1)と、上記ベクトルk0'の残りm0-c個の要素を抜き出したベクトルと上記ベクトルv0'の残りm0-c個の要素を抜き出したベクトルと上記第二テーブルの属性値に対応する値を予め定めた空を示す値u'1,vとしたベクトルとを結合したテーブル(2)と、上記ベクトルv0'の残りm0-c個の要素を抜き出したベクトルと上記ベクトルv1'の残りm1-c個の要素を抜き出したベクトルと上記第一テーブルの属性値に対応する値を予め定めた空を示す値u'0,vとしたベクトルとを結合したテーブル(3)とを結合した結合テーブルを生成する第三結合テーブル生成ステップと、
を含む秘密結合方法。
【請求項１１】
請求項６の秘密計算装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密計算技術に関する。この発明は、特に、秘匿性を保ったまま２つのテーブルを結合するための技術に関する。
【背景技術】
【０００２】
秘密計算技術の分野において、秘匿性を保ったまま２つのテーブルを結合する技術が求められている。【０００３】
秘匿性を保ったまま２つのテーブルを結合する技術として、例えば非特許文献１に記載された技術が知られている。非特許文献１では、キー重複ありの場合の等結合が実現されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】桐淵直人、五十嵐大、諸橋玄武、濱田浩気、「属性情報と履歴情報の秘匿統合分析に向けた秘密計算による高速な等結合アルゴリズムとその実装」、CSS2016、2016
【発明の概要】
【発明が解決しようとする課題】
【０００５】
この発明は、キー重複がない場合に非特許文献１の技術よりも高速に秘匿性を保ったまま２つのテーブルを結合するために必要な情報を生成する秘密結合情報生成システム、秘密結合システム、これらの方法、秘密計算装置及びプログラムを提供することである。
【課題を解決するための手段】
【０００６】
この発明の一態様による秘密結合情報生成システムによれば、複数の秘密計算装置を含む秘密結合情報生成システムであって、Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、複数の秘密計算装置は、ベクトルk0のシェア[k0]及びベクトルk1のシェア[k1]を用いて、ベクトルk0及びベクトルk1を結合したベクトルk∈[Fk]m0+m1のシェア[k]を生成する複数のベクトル結合部と、m0個の０と、m1個の１とを結合したベクトルfのシェア[f]を生成する複数の第一ベクトル生成部と、シェア[k]を用いて、ベクトルkを安定ソートする置換σのシェア[σ]を生成する複数の第一置換計算部と、シェア[k]、シェア[σ]及びシェア[f]を用いて、ベクトルkに置換σを適用したベクトルσ(k)のシェア[σ(k)]と、ベクトルfに置換σを適用したベクトルσ(f)のシェア[σ(f)]とを生成する複数の第一置換適用部と、シェア[σ(k)]を用いて、ベクトルσ(k)のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数の第二ベクトル生成部と、シェア[e]を用いて、ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルの各要素をビット反転させたベクトルe'のシェア[e']を生成する複数の第三ベクトル生成部と、シェア[e']を用いて、ベクトルe'を安定ソートする置換σ'のシェア[σ']を生成する複数の第二置換計算部と、シェア[σ(f)]及びシェア[σ']を用いて、ベクトルσ(f)に置換σ'を適用したベクトルf'=σ'(σ(f))のシェア[f']を生成する複数の第二置換適用部と、シェア[f']を用いて、各要素が、ベクトルf'のその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルsのシェア[s]と、ベクトルf'の各要素をビット反転させたベクトルをビット反転ベクトルとして、各要素が、ビット反転ベクトルのその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルs'のシェア[s']とを生成する複数の第四ベクトル生成部と、シェア[f']、シェア[s]及びシェア[s']を用いて、ベクトルσ''=f's+(1-f')s'-1のシェア[σ'']を計算する複数の第五ベクトル生成部と、シェア[e']及びシェア[σ]を用いて、ベクトルe'に置換σの逆置換σ-1を適用したベクトルe''=σ-1(e')のシェア[e'']を生成する複数の第一逆置換適用部と、シェア[e'']を用いて、ベクトルe''の先頭からm0個の要素からなるベクトルg0のシェア[g0]と、ベクトルe''の残りのm1個の要素からなるベクトルg1のシェア[g1]とを生成する複数の第一ベクトル分離部と、シェア[σ'']、シェア[σ]及びシェア[σ']を用いて、ベクトルxに置換σ'の逆置換σ'-1及び置換σの逆置換σ-1を適用したベクトルσ'''-1=σ-1(σ'-1(σ''))のシェア[σ'''-1]を生成する複数の第二逆置換適用部と、シェア[σ'''-1]を用いて、ベクトルσ'''-1の先頭からm0個の要素からなるベクトルσ0-1のシェア[σ0-1]と、ベクトルσ'''-1の残りのm1個の要素からなるベクトルσ1-1のシェア[σ1-1]とを生成する複数の第二ベクトル分離部と、シェア[σ0-1]、シェア[σ１-1]及び置換π0のシェア[π0]及び置換π1のシェア[π1]を用いて、ベクトルσ0-1に置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、ベクトルσ１-1に置換π1を適用したベクトルπ1(σ１-1)のシェア[π1(σ１-1)]とを生成して、π0(σ０-1)及びπ1(σ１-1)を公開する複数の第三置換適用部と、を備えている。【０００７】
この発明の一態様による秘密結合システムは、上記の秘密結合情報生成システムの複数の秘密計算装置を含み、こららの複数の秘密計算装置は、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、ベクトルk1のシェア[k1]及びベクトルv1のシェア[v1]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1'=(π1(σ1-1))-1(π1(k1'))のシェア[k1']と、ベクトルv1'=(π1(σ1-1))-1(π1(v1'))のシェア[v1']とを計算する複数の第四置換適用部と、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1']を用いて、ベクトルg0又はベクトルg1の０の要素の数をcとして、ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合した結合テーブルを生成する複数の第一結合テーブル生成部と、を更に含む。【０００８】
この発明の一態様による秘密結合システムによれば、複数の秘密計算装置を含む秘密結合システムであって、Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、複数の秘密計算装置は、ベクトルk0のシェア[k0]、ベクトルk1のシェア[k1]、置換π0のシェア[π0]及び置換π1のシェア[π1]を用いて、第一テーブルの各ベクトルを置換σ0で置換すると第一テーブルと第二テーブルに共通するキーのレコードが先頭側に移動する置換σ0の逆置換σ0-1に置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、第二テーブルの各ベクトルを置換σ1で置換すると第一テーブルと第二テーブルに共通するキーのレコードが先頭側に移動する置換σ1の逆置換σ1-1に置換π1を適用したベクトルπ1(σ1-1)のシェア[π1(σ1-1)]と、第一テーブルのi番目のレコードが、第一テーブルと第二テーブルに共通するキーのレコードかどうかを表す値g0,iから構成されるベクトルg0のシェア[g0]と、第二テーブルのi番目のレコードが、第一テーブルと第二テーブルに共通するキーのレコードかどうかを表す値g1,iから構成されるベクトルg1のシェア[g1]と、を生成する複数の秘密結合情報生成部と、シェア[g1]、ベクトルk1のシェア[k1]及びベクトルv1のシェア[v1]を用いて、ベクトルg1のi番目の要素をg1,iとして、g1,i=1である場合には、第二テーブルのキーのi番目の要素を予め定めた空を示す値u1,kとし、第二テーブルの属性のi番目の要素を予め定めた空を示す値u1,vとした変形第二テーブルを生成する複数のフィルタリング部と、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、変形第二テーブルのキーのベクトルであるk1'のシェア[k1']、変形第二テーブルの属性値のベクトルであるv1'のシェア[v1']、置換π0のシェア[π0]、置換π1のシェア[π1]、シェア[π0(σ0-1)]及びシェア[π1(σ1-1)]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1''=(π1(σ1-1))-1(π1(k1'))のシェア[k1'']と、ベクトルv1''=(π1(σ1-1))-1(π1(v1'))のシェア[v1'']とを計算する複数の第五置換適用部と、シェア[k0']、シェア[v0']、シェア[k1'']及びシェア[v1'']を用いて、m0<m1である場合には、ベクトルk0'と、ベクトルv0'と、ベクトルk1''の先頭からm0個の要素を抜き出したベクトルと、ベクトルv1''の先頭からm0個の要素を抜き出したベクトルとを結合した結合テーブルを、m0>m1である場合には、ベクトルk0'と、ベクトルv0'と、ベクトルk1''にm0-m1個の予め定めた空を示す値ukの要素を追加したベクトルと、ベクトルv1''にm0-m1個の予め定めた空を示す値uvの要素を追加したベクトルとを結合した結合テーブルを生成する複数の第二結合テーブル生成部と、を備えている。【０００９】
この発明の一態様による秘密結合システムによれば、複数の秘密計算装置を含む秘密結合システムであって、Fk,Fvは任意の環であり、αを任意のベクトル又は任意の置換として[α]はαが秘密分散されたシェアであり、m0,m1は１以上の整数であり、k0∈Fkm0は第一テーブルのキーのベクトルであり、v0∈Fvm0は第一テーブルの属性値のベクトルであり、k1∈Fkm1は第二テーブルのキーのベクトルであり、v1∈Fvm1は第二テーブルの属性値のベクトルであり、π0,π1はそれぞれ長さm0,m1の所定の置換であり、複数の秘密計算装置は、ベクトルk0のシェア[k0]、ベクトルk1のシェア[k1]、置換π0のシェア[π0]及び置換π1のシェア[π1]を用いて、第一テーブルの各ベクトルを置換σ0で置換すると第一テーブルと第二テーブルに共通するキーのレコードが先頭側に移動する置換σ0の逆置換σ0-1に置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、第二テーブルの各ベクトルを置換σ1で置換すると第一テーブルと第二テーブルに共通するキーのレコードが先頭側に移動する置換σ1の逆置換σ1-1に置換π1を適用したベクトルπ1(σ1-1)のシェア[π1(σ1-1)]と、第一テーブルのi番目のレコードが、第一テーブルと第二テーブルに共通するキーのレコードかどうかを表す値g0,iから構成されるベクトルg0のシェア[g0]と、第二テーブルのi番目のレコードが、第一テーブルと第二テーブルに共通するキーのレコードかどうかを表す値g1,iから構成されるベクトルg1のシェア[g1]と、を生成する複数の秘密結合情報生成部と、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、ベクトルk1のシェア[k1]及びベクトルv1のシェア[v1]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1'=(π1(σ1-1))-1(π1(k1'))のシェア[k1']と、ベクトルv1'=(π1(σ1-1))-1(π1(v1'))のシェア[v1']とを計算する複数の第四置換適用部と、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1']を用いて、ベクトルg0又はベクトルg1の０の要素の数をcとして、ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合したテーブル(1)と、ベクトルk0'の残りm0-c個の要素を抜き出したベクトルとベクトルv0'の残りm0-c個の要素を抜き出したベクトルと第二テーブルの属性値に対応する値を予め定めた空を示す値u'1,vとしたベクトルとを結合したテーブル(2)と、ベクトルv0'の残りm0-c個の要素を抜き出したベクトルとベクトルv1'の残りm1-c個の要素を抜き出したベクトルと第一テーブルの属性値に対応する値を予め定めた空を示す値u'0,vとしたベクトルとを結合したテーブル(3)とを結合した結合テーブルを生成する複数の第三結合テーブル生成部と、を備えている。
【発明の効果】
【００１０】
逆置換を用いることで、キー重複がない場合に非特許文献１の技術よりも高速に秘匿性を保ったまま２つのテーブルを結合するために必要な情報を生成することができる。また、これらの情報を用いて、キー重複がない場合に非特許文献１の技術よりも高速に秘匿性を保ったまま２つのテーブルを結合することができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、秘密結合システムの機能構成を例示する図である。
【図２】図２は、内部結合を行う秘密結合システムの秘密計算装置の機能構成を例示する図である。
【図３】図３は、内部結合を行う秘密結合方法、左外部結合を行う秘密結合方法、完全外部結合を行う秘密結合方法の処理手続きを例示する図である。
【図４】図４は、内部結合を行う秘密結合方法、完全外部結合を行う秘密結合方法の処理手続きを例示する図である。
【図５】図５は、左外部結合を行う秘密結合方法の処理手続きを例示する図である。
【図６】図６は、左外部結合を行う秘密結合システムの秘密計算装置の機能構成を例示する図である。
【図７】図７は、完全部結合を行う秘密結合システムの秘密計算装置の機能構成を例示する図である。
【発明を実施するための形態】
【００１２】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１３】
[内部結合を行う秘密結合システム]
図１を参照して、実施形態の秘密結合システムの構成例を説明する。この秘密結合システム及び方法は、いわゆる内部結合を行うものである。すなわち、この秘密結合システムは、秘匿性を保ちつつ、第一テーブル及び第二テーブルに共通するレコードを結合する。
【００１４】
秘密結合システムは、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、第四置換適用部１１６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∈Fkm0は第一テーブルのキーのベクトルであるとする。v0∈Fvm0は第一テーブルの各属性の属性値のベクトルであるとする。第一テーブルの中は、重複するキーはないとする。第一テーブルに複数の属性の属性値が含まれている場合には、v0は複数の属性の属性値を連結したベクトルであってもよい。例えば、第一テーブルは、レコード数が２であり、２個の属性の属性値を含んでおり、１個目の属性の属性値のベクトルはv0,1=(29,169)であり、２個目の属性の属性値のベクトルはv0,1=(35,175)であるとする。この場合、v0は、これらの２個の属性の属性値を連結したベクトルv0=((29,35),(169,175))であってもよい。
【００２３】
[Fk,Fv]m0の上付き文字の中のm0は、「m0」を意味する。このように、上付き文字の中では、更なる上付き文字及び下付き文字の表現を省略することがある。同様に、下付き文字の中では、更なる上付き文字及び下付き文字の表現を省略することがある。
【００２４】
第二テーブルは、m1個のレコードを有している。m1個のレコードのそれぞれは、１個のキーと、L1個の属性の属性値とを有している。k1∈Fkm1は第二テーブルのキーのベクトルであるとする。v1∈Fvm1は上記第二テーブルの各属性の属性値のベクトルであるとする。第二テーブルの中では、重複するキーはないとする。第二テーブルに複数の属性の属性値が含まれている場合には、v0と同様にして、v1は、複数の属性の属性値を連結したベクトルであってもよい。
【００２５】
一般に環を要素とするベクトルはやはり環であるため、あるレコードに含まれる各属性の値を並べたデータは、ベクトル、つまり環とみなすことができる。
【００２６】
例えば、第一テーブルは、レコード数が３であり、キーのベクトルk0=(1,2,3)と、１個の属性の属性値のベクトルv0=(5,10,1)とから構成されているとする。
【００２７】
また、第二テーブルは、レコード数が４であり、キーのベクトルk1=(1,3,4,5)と、１個の属性の属性値のベクトルv1=(2,4,9,8)とから構成されているとする。
【００２８】
＜ステップＳ１＞
ベクトル結合部１１1,…,１１Nに、ベクトルk0のシェア[k0]及びベクトルk1のシェア[k1]が入力される。
【００２９】
ベクトル結合部１１1,…,１１Nは、[k0]と[k1]を結合して[k]∈[Fk]m0+m1を得る。
【００３０】
より詳細には、ベクトル結合部１１1,…,１１Nは、ベクトルk0のシェア[k0]及びベクトルk1のシェア[k1]を用いて、ベクトルk0及びベクトルk1を結合したベクトルk∈[Fk]m0+m1のシェア[k]を生成する（ステップＳ１）。
【００３１】
生成されたシェア[k]は、第一置換計算部１３1,…,１３N及び第一置換適用部１４1,…,１４Nに出力される。
【００３２】
例えば、ベクトルk0=(1,2,3)であり、ベクトルk1=(1,3,4,5)であるとする。この場合、ベクトルk=(1,2,3,1,3,4,5)となる。
【００３３】
＜ステップＳ２＞
第一ベクトル生成部１２1,…,１２Nは、m0個の０と、m1個の１とを結合したベクトルfのシェア[f]を生成する（ステップＳ２）。
【００３４】
シェア[f]は、第一置換適用部１４1,…,１４Nに出力される。
【００３５】
例えば、m0=3,m1=4である場合には、ベクトルf=(0,0,0,1,1,1,1)となる。
【００３６】
＜ステップＳ３＞
第一置換計算部１３1,…,１３Nに、シェア[k]が入力される。
【００３７】
第一置換計算部１３1,…,１３Nは、シェア[k]を用いて、ベクトルkを安定ソートする置換σのシェア[σ]を生成する（ステップＳ３）。
【００３８】
シェア[σ]は、第一置換適用部１４1,…,１４N及び第二逆置換適用部１１３1,…,１１３Nに出力される。
【００３９】
例えば、k=(1,2,3,1,3,4,5)である場合には、置換σは以下の式（１）のようになる。例えば、番号が１スタートで表記されるとして、置換σの各列(i,j)Tは、置換が適用されるベクトルのi番目の要素をj番目に移動することを意味する。
【００４０】
【数１】
2020036127.tif 000003
【００４１】
安定ソートとは、同等なデータのソート前の順序が、ソート後も保存されるものをいう。安定ソートを行う置換σのシェア[σ]の生成は、例えば参考文献１の手法により実現することができる。
〔参考文献１〕五十嵐大、濱田浩気、菊池亮、千田浩司、「超高速秘密計算ソートの設計と実装：秘密計算がスクリプト言語に並ぶ日」、CSS2017、2017
【００４２】
＜ステップＳ４＞
第一置換適用部１４1,…,１４Nに、シェア[k]、シェア[σ]及びシェア[f]が入力される。
【００４３】
第一置換適用部１４1,…,１４Nは、シェア[k]、シェア[σ]及びシェア[f]を用いて、ベクトルkに置換σを適用したベクトルσ(k)のシェア[σ(k)]と、ベクトルfに置換σを適用したベクトルσ(f)のシェア[σ(f)]とを生成する（ステップＳ４）。
【００４４】
シェア[σ(k)]は、第二ベクトル生成部１５1,…,１５Nに出力される。
【００４５】
シェア[σ(f)]は、第二置換適用部１８1,…,１８Nに出力される。
【００４６】
例えば、ベクトルk=(1,2,3,1,3,4,5)であり、ベクトルf=(0,0,0,1,1,1,1)であり、置換σが上記式（１）により定義される置換である場合には、ベクトルσ(k)=(1,1,2,3,3,4,5)となり、ベクトルσ(f)=(0,1,0,0,1,1,1)となる。
【００４７】
＜ステップＳ５＞
第二ベクトル生成部１５1,…,１５Nに、シェア[σ(k)]が入力される。
【００４８】
第二ベクトル生成部１５1,…,１５Nは、シェア[σ(k)]を用いて、ベクトルσ(k)のある要素とそのある要素の次の要素とが、同じ場合には１を、違う場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する（ステップＳ５）。ここで、en-1=0とする。
【００４９】
シェア[e]は、第三ベクトル生成部１６1,…,１６Nに出力される。
【００５０】
例えば、ベクトルσ(k)=(1,1,2,3,3,4,5)である場合には、ベクトルe=(1,0,0,1,0,0,0)となる。
【００５１】
＜ステップＳ６＞
第三ベクトル生成部１６1,…,１６Nに、シェア[e]が入力される。
【００５２】
第三ベクトル生成部１６1,…,１６Nは、シェア[e]を用いて、ベクトルeのある要素とそのある要素の前の要素の一方が１の場合には１を、そうでない場合には０をそのある要素に対応する要素として持つベクトルの各要素をビット反転させたベクトルe'のシェア[e']を生成する（ステップＳ６）。
【００５３】
シェア[e']は、第二置換計算部１７1,…,１７Nに出力される。
【００５４】
例えば、ベクトルe=(1,0,0,1,0,0,0)である場合には、ベクトルe'=(0,0,1,0,0,1,1)となる。
【００５５】
＜ステップＳ７＞
第二置換計算部１７1,…,１７Nに、シェア[e']が入力される。
【００５６】
第二置換計算部１７1,…,１７Nは、シェア[e']を用いて、ベクトルe'を安定ソートする置換σ'のシェア[σ']を生成する（ステップＳ７）。
【００５７】
シェア[σ']は、第二置換適用部１８1,…,１８N及び第二逆置換適用部１１３1,…,１１３Nに出力される。
【００５８】
例えば、ベクトルe'=(0,0,1,0,0,1,1)である場合には、置換σ'は以下の式（２）のようになる。
【００５９】
【数２】
2020036127.tif 000004
【００６０】
＜ステップＳ８＞
第二置換適用部１８1,…,１８Nに、シェア[σ(f)]及びシェア[σ']が入力される。
【００６１】
第二置換適用部１８1,…,１８Nは、シェア[σ(f)]及びシェア[σ']を用いて、ベクトルσ(f)に置換σ'を適用したベクトルf'=σ'(σ(f))のシェア[f']を生成する（ステップＳ８）。
【００６２】
シェア[f']は、第四ベクトル生成部１９1,…,１９Nに出力される。
【００６３】
例えば、ベクトルσ(f)=(0,1,0,0,1,1,1)であり、置換σ'が上記式（２）により定義される置換である場合には、ベクトルf'=(0,1,0,1,0,1,1)となる。
【００６４】
＜ステップＳ９＞
第四ベクトル生成部１９1,…,１９Nに、シェア[f']が入力される。
【００６５】
第四ベクトル生成部１９1,…,１９Nは、シェア[f']を用いて、各要素が、ベクトルf'のその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルsのシェア[s]と、ベクトルf'の各要素をビット反転させたベクトルをビット反転ベクトルとして、各要素が、ビット反転ベクトルのその各要素に対応する要素を含むその各要素に対応する要素までの要素の和であるベクトルs'のシェア[s']とを生成する（ステップＳ９）。
【００６６】
シェア[s]及びシェア[s']は、第五ベクトル生成部１１０1,…,１１０Nに出力される。
【００６７】
例えば、ベクトルf'=(0,1,0,1,0,1,1)である場合には、ベクトルs=(0,1,1,2,2,3,4)となり、ベクトルs'=(1,1,2,2,3,3,3)となる。
【００６８】
＜ステップＳ１０＞
第五ベクトル生成部１１０1,…,１１０Nに、シェア[s]及びシェア[s']が入力される。
【００６９】
第五ベクトル生成部１１０1,…,１１０Nは、シェア[f']、シェア[s]及びシェア[s']を用いて、ベクトルσ''=f's+(1-f')s'-1のシェア[σ'']を計算する（ステップＳ１０）。
【００７０】
シェア[σ'']は、第一逆置換適用部１１１1,…,１１１Nに出力される。
【００７１】
例えば、ベクトルs=(0,1,1,2,2,3,4)であり、ベクトルs'=(1,1,2,2,3,3,3)である場合には、σ''=(0,0,1,1,2,2,3)となる。
【００７２】
＜ステップＳ１１＞
第一逆置換適用部１１１1,…,１１１Nに、シェア[e']及びシェア[σ]が入力される。
【００７３】
第一逆置換適用部１１１1,…,１１１Nは、シェア[e']及びシェア[σ]を用いて、ベクトルe'に置換σの逆置換σ-1を適用したベクトルe''=σ-1(e')のシェア[e'']を生成する（ステップＳ１１）。
【００７４】
シェア[e'']は、第一ベクトル分離部１１２1,…,１１２Nに出力される。
【００７５】
例えば、ベクトルe'=(0,0,1,0,0,1,1)であり、置換σが上記式（１）の置換である場合には、ベクトルe''=(0,1,0,0,0,1,1)となる。
【００７６】
＜ステップＳ１２＞
第一ベクトル分離部１１２1,…,１１２Nに、シェア[e'']が入力される。
【００７７】
第一ベクトル分離部１１２1,…,１１２Nは、シェア[e'']を用いて、ベクトルe''の先頭からm0個の要素からなるベクトルg0のシェア[g0]と、ベクトルe''の残りのm1個の要素からなるベクトルg1のシェア[g1]とを生成する（ステップＳ１２）。
【００７８】
シェア[g1]は、に出力される。
【００７９】
例えば、ベクトルe''=(0,1,0,0,0,1,1)である場合には、ベクトルg0=(0,1,0)となり、ベクトルg0=(0,0,1,1)となる。
【００８０】
＜ステップＳ１３＞
第二逆置換適用部１１３1,…,１１３Nに、シェア[σ]及びシェア[σ']が入力される。
【００８１】
第二逆置換適用部１１３1,…,１１３Nは、シェア[σ'']、シェア[σ]及びシェア[σ']を用いて、ベクトルxに置換σ'の逆置換σ'-1及び置換σの逆置換σ-1を適用したベクトルσ'''-1=σ-1(σ'-1(σ''))のシェア[σ'''-1]を生成する（ステップＳ１３）。
【００８２】
シェア[σ'''-1]は、第二ベクトル分離部１１４1,…,１１４Nに出力される。
【００８３】
例えば、置換σが上記式（１）の置換であり、置換σ'が上記式（２）の置換である場合には、σ'''-1=(0,2,1,0,1,2,3)となる。
【００８４】
＜ステップＳ１４＞
第二ベクトル分離部１１４1,…,１１４Nに、シェア[σ'''-1]が入力される。
【００８５】
第二ベクトル分離部１１４1,…,１１４Nは、シェア[σ'''-1]を用いて、ベクトルσ'''-1の先頭からm0個の要素からなるベクトルσ0-1のシェア[σ0-1]と、ベクトルσ'''-1の残りのm1個の要素からなるベクトルσ1-1のシェア[σ1-1]とを生成する（ステップＳ１４）。
【００８６】
シェア[σ1-1]とは、に出力される。
【００８７】
例えば、σ'''-1=(0,2,1,0,1,2,3)である場合には、ベクトルσ0-1=(0,2,1)となり、ベクトルσ1-1=(0,1,2,3)となる。
【００８８】
＜ステップＳ１５＞
第三置換適用部１１５1,…,１１５Nに、シェア[σ１-1]及び置換π0のシェア[π0]及び置換π1のシェア[π1]が入力される。
【００８９】
第三置換適用部１１５1,…,１１５Nは、シェア[σ0-1]、シェア[σ１-1]及び置換π0のシェア[π0]及び置換π1のシェア[π1]を用いて、ベクトルσ0-1に置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、ベクトルσ１-1に置換π1を適用したベクトルπ1(σ１-1)のシェア[π1(σ１-1)]とを生成して、π0(σ0-1)及びπ1(σ１-1)を公開する（ステップＳ１５）。
【００９０】
置換π0,π1は、所定の置換であり、例えばランダム置換である。置換π0,π1は、予め定められた置換であってもよいし、ステップＳ１５の処理をする際に生成されてもよい。置換π0,π1及びこれらのシェア[π0],[π1]は、例えば参考文献１の4.1節に記載された手法により生成することができる。秘密計算装置１n（1≦n≦N）は、置換π0,π1及びこれらのシェア[π0],[π1]についての情報を有しており、置換π0,π1及びこれらのシェア[π0],[π1]を用いて計算が可能であるとする。
【００９１】
例えば、ベクトルσ0-1=(0,2,1)であり、ベクトルσ1-1=(0,1,2,3)であり、π0が以下の式（３）により表される置換であり、π1が以下の式（４）により表される置換であるとする。
【００９２】
【数３】
2020036127.tif 000005
【００９３】
この場合、ベクトルπ0(σ0-1)=(2,1,0)、ベクトルπ1(σ1-1)=(2,0,3,1)となる。
【００９４】
＜ステップＳ１６＞
第四置換適用部１１６1,…,１１６Nに、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、ベクトルk1のシェア[k1]及びベクトルv1のシェア[v1]が入力される。
【００９５】
第四置換適用部１１６1,…,１１６Nは、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、ベクトルk1のシェア[k1]及びベクトルv1のシェア[v1]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1'=(π1(σ1-1))-1(π1(k1'))のシェア[k1']と、ベクトルv1'=(π1(σ1-1))-1(π1(v1'))のシェア[v1']とを計算する（ステップＳ１６）。
【００９６】
シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1']は、第一結合テーブル生成部１１７1,…,１１７Nに出力される。
【００９７】
例えば、ベクトルk0=(1,2,3)であり、ベクトルv0=(5,10,1)であり、ベクトルk1=(1,3,4,5)であり、ベクトルv1'=(2,4,9,8)であり、置換π0が上記式（３）により表される置換であり、置換π1が上記式（４）により表される置換である場合には、ベクトルk0'=(1,3,2)となり、ベクトルv0'=(5,1,10)となり、ベクトルk1''=(1,3,4,5)となり、ベクトルv1''=(2,4,9,8)となる。
【００９８】
＜ステップＳ１７＞
第一結合テーブル生成部１１７1,…,１１７Nに、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1']が入力される。
【００９９】
第一結合テーブル生成部１１７1,…,１１７Nは、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1']を用いて、ベクトルg0又はベクトルg1の０の要素の数をcとして、ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合した結合テーブルを生成する（ステップＳ１７）。
【０１００】
例えば、ベクトルg0=(0,1,0)であり、ベクトルk0'=(1,3,2)であり、ベクトルv0'=(5,1,10)であり、ベクトルk1''=(1,3,4,5)であり、ベクトルv1''=(2,4,9,8)である場合には、結合テーブルは以下のテーブルとなる。
【０１０１】
【数４】
2020036127.tif 000006
【０１０２】
上記（Ａ）の結合テーブルは、レコード数が３であり、キーのベクトルk0=(1,2,3)と、１個の属性の属性値のベクトルv0=(5,10,1)とから構成されている第一テーブルと、キーのベクトルk1=(1,3,4,5)と、１個の属性の属性値のベクトルv1=(2,4,9,8)とから構成されている第二テーブルとを左外部結合したテーブルとなっている。
【０１０３】
このように、逆置換を用いることで、キー重複がない場合に非特許文献１の技術よりも高速に秘匿性を保ったまま２つのテーブルを結合することができる。
【０１０４】
[左外部結合を行う秘密結合システム]
図６を参照して、実施形態の秘密結合システムの構成例を説明する。この秘密結合システム及び方法は、いわゆる左外部結合を行うものである。すなわち、この秘密結合システムは、秘匿性を保ちつつ、第一テーブル及び第二テーブルに共通するレコードと、第一テーブルのみに存在するレコードとを結合する。
【０１０５】
左外部結合を行う秘密結合システムは、第四置換適用部１１６n、第一結合テーブル生成部１１７nを備えていない代わりに、フィルタリング部１１８n、第五置換適用部１１９n、第二結合テーブル生成部１２０nを備えている点を除けば、内部結合を行う秘密結合システムと同様である。
【０１０６】
左外部結合を行う秘密結合方法は、ステップＳ１６からステップＳ１７の処理を行わない代わりに、ステップＳ１８及びステップＳ２０の処理を行う点を除けば、内部結合を行う秘密結合方法と同様である。
【０１０７】
以下では、内部結合を行う秘密結合システム及び方法と異なる部分について説明する。内部結合を行う秘密結合システム及び方法と同じ部分については重複説明を省略する。
【０１０８】
秘密結合システムの秘密計算装置１nは、例えば、図６に示すように、ベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n及び第二ベクトル分離部１１４n、第三置換適用部１１５n、第四置換適用部１１６n、第一結合テーブル生成部１１７n、フィルタリング部１１８n、第五置換適用部１１９n及び第二結合テーブル生成部１２０nを備えている。
【０１０９】
まず、＜ステップＳ１＞から＜ステップＳ１５＞の処理が行われる。＜ステップＳ１＞から＜ステップＳ１５＞の処理は、[内部結合を行う秘密結合システム及び方法]の欄で説明した＜ステップＳ１＞から＜ステップＳ１５＞の処理と同様であるため、ここでは重複説明を省略する。
【０１１０】
その後、以下に説明するステップＳ１８からステップＳ２０の処理が行われる。
【０１１１】
＜ステップＳ１８＞
フィルタリング部１１８1,…,１１８Nに、シェア[g1]、ベクトルk1のシェア[k1]及びベクトルv1のシェア[v1]が入力される。
【０１１２】
フィルタリング部１１８1,…,１１８Nは、シェア[g1]、ベクトルk1のシェア[k1]及びベクトルv1のシェア[v1]を用いて、ベクトルg1のi番目の要素をg1,iとして、g1,i=1である場合には、第二テーブルのキーのi番目の要素を予め定めた空を示す値u1,kとし、第二テーブルの属性のi番目の要素を予め定めた空を示す値u1,vとした変形第二テーブルを生成する（ステップＳ１８）。変形第二テーブルのキーのベクトルをk1'とし、変形第二テーブルの属性値のベクトルをv1'とする。
【０１１３】
変形第二テーブルは、第五置換適用部１１９1,…,１１９Nに出力される。
【０１１４】
例えば、第二テーブルが、キーのベクトルk1=(1,3,4,5)と、１個の属性の属性値のベクトルv1=(2,4,9,8)とから構成されており、ベクトルg1=(0,0,1,1)である場合には、変形第二テーブルは、以下のテーブルとなる。
【０１１５】
【数５】
2020036127.tif 000007
【０１１６】
＜ステップＳ１９＞
第五置換適用部１１９1,…,１１９Nに、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、変形第二テーブルのキーのベクトルであるk1'のシェア[k1']、変形第二テーブルの属性値のベクトルであるv1'のシェア[v1']、置換π0のシェア[π0]、置換π1のシェア[π1]、シェア[π0(σ0-1)]及びシェア[π1(σ1-1)]が入力される。
【０１１７】
第五置換適用部１１９1,…,１１９Nは、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、変形第二テーブルのキーのベクトルであるk1'のシェア[k1']、変形第二テーブルの属性値のベクトルであるv1'のシェア[v1']、置換π0のシェア[π0]、置換π1のシェア[π1]、シェア[π0(σ0-1)]及びシェア[π1(σ1-1)]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1''=(π1(σ1-1))-1(π1(k1'))のシェア[k1'']と、ベクトルv1''=(π1(σ1-1))-1(π1(v1'))のシェア[v1'']とを計算する（ステップＳ１８）。
【０１１８】
シェア[k0']、シェア[v0']、シェア[k1'']及びシェア[v1'']は、第二結合テーブル生成部１２０1,…,１２０Nに出力される。
【０１１９】
例えば、ベクトルk0=(1,2,3)であり、ベクトルv0=(5,10,1)であり、ベクトルk1'=(1,3,u1,k,u1,k)であり、ベクトルv1'=(2,4,u1,v,u1,v)であり、置換π0が上記式（３）により表される置換であり、置換π1が上記式（４）により表される置換である場合には、ベクトルk0'=(1,3,2)となり、ベクトルv0'=(5,1,10)となり、ベクトルk1''=(1,3,u1,k,u1,k)となり、ベクトルv1''=(2,4,u1,v,u1,v)となる。
【０１２０】
＜ステップＳ２０＞
第二結合テーブル生成部１２０1,…,１２０Nに、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1'']が入力される。
【０１２１】
第二結合テーブル生成部１２０1,…,１２０Nは、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1'']を用いて、m0<m1である場合には、ベクトルk0'と、ベクトルv0'と、ベクトルk1''の先頭からm0個の要素を抜き出したベクトルと、ベクトルv1''の先頭からm0個の要素を抜き出したベクトルとを結合した結合テーブルを、m0>m1である場合には、ベクトルk1''にm0-m1個の予め定めた空を示す値ukの要素を追加したベクトルと、ベクトルv1''にm0-m1個の予め定めた空を示す値uvの要素を追加したベクトルと、ベクトルk0'と、ベクトルv0'とを結合した結合テーブルを生成する（ステップＳ２０）。
【０１２２】
例えば、ベクトルk0'=(1,3,2)であり、ベクトルv0'=(5,1,10)であり、ベクトルk1''=(1,3,u1,k,u1,k)であり、ベクトルv1''=(2,4,u1,v,u1,v)である場合には、結合テーブルは以下のテーブルとなる。
【０１２３】
【数６】
2020036127.tif 000008
【０１２４】
上記（Ｃ）の結合テーブルは、レコード数が３であり、キーのベクトルk0=(1,2,3)と、１個の属性の属性値のベクトルv0=(5,10,1)とから構成されている第一テーブルと、キーのベクトルk1=(1,3,4,5)と、１個の属性の属性値のベクトルv1=(2,4,9,8)とから構成されている第二テーブルとを左外部結合したテーブルとなっている。
【０１２５】
また、例えば、ベクトルk0'=(1,3,4,5)であり、ベクトルv0'=(2,4,9,8)であり、ベクトルk1''=(1,3)であり、ベクトルv1''=(5,1)である場合には、結合テーブルは以下のテーブルとなる。
【０１２６】
【数７】
2020036127.tif 000009
【０１２７】
この実施形態によれば、秘匿性を保ったまま、第一テーブル及び第二テーブルを左外部結合することができる。
【０１２８】
このように、逆置換を用いることで、キー重複がない場合に非特許文献１の技術よりも高速に秘匿性を保ったまま２つのテーブルを結合することができる。
【０１２９】
[完全外部結合を行う秘密結合システム及び方法]
図７を参照して、実施形態の秘密結合システムの構成例を説明する。この秘密結合システム及び方法は、いわゆる完全外部結合を行うものである。言い換えれば、この秘密結合システムは、秘匿性を保ちつつ、第一テーブル及び第二テーブルに共通するレコードと、第一テーブルのみに存在するレコードと、第二テーブルのみに存在するレコードとを結合する。
【０１３０】
完全外部結合を行う秘密結合システムは、第一結合テーブル生成部１１７nを備えていない代わりに、第三結合テーブル生成部１２１nを備えている点を除けば、内部結合を行う秘密結合システムと同様である。
【０１３１】
完全外部結合を行う秘密結合方法は、ステップＳ１７の処理を行わない代わりに、ステップＳ２１の処理を行う点を除けば、内部結合を行う秘密結合方法と同様である。
【０１３２】
以下では、内部結合を行う秘密結合システム及び方法と異なる部分について説明する。内部結合を行う秘密結合システム及び方法と同じ部分については重複説明を省略する。
【０１３３】
秘密結合システムの秘密計算装置１nは、例えば、図７に示すように、ベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n及び第二ベクトル分離部１１４n、第三置換適用部１１５n、第四置換適用部１１６n及び第三結合テーブル生成部１２１nを備えている。
【０１３４】
まず、＜ステップＳ１＞から＜ステップＳ１６＞の処理が行われる。＜ステップＳ１＞から＜ステップＳ１６＞の処理は、[内部結合を行う秘密結合システム及び方法]の欄で説明した＜ステップＳ１＞から＜ステップＳ１６＞の処理と同様であるため、ここでは重複説明を省略する。
【０１３５】
その後、以下に説明するステップＳ２１の処理が行われる。
【０１３６】
＜ステップＳ２１＞
第三結合テーブル生成部１２１1,…,１２１Nに、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1']が入力される。
【０１３７】
第三結合テーブル生成部１２１1,…,１２１Nは、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1']を用いて、ベクトルg0又はベクトルg1の０の要素の数をcとして、ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合したテーブル(1)と、ベクトルk0'の残りm0-c個の要素を抜き出したベクトルとベクトルv0'の残りm0-c個の要素を抜き出したベクトルと第二テーブルの属性値に対応する値を予め定めた空を示す値u'1,vとしたベクトルとを結合したテーブル(2)と、ベクトルv0'の残りm0-c個の要素を抜き出したベクトルとベクトルv1'の残りm1-c個の要素を抜き出したベクトルと第一テーブルの属性値に対応する値を予め定めた空を示す値u'0,vとしたベクトルとを結合したテーブル(3)とを結合した結合テーブルを生成する（ステップＳ２１）。
【０１３８】
例えば、ベクトルg0=(0,1,0)であり、ベクトルk0'=(1,3,2)であり、ベクトルv0'=(5,1,10)であり、ベクトルk1''=(1,3,4,5)であり、ベクトルv1''=(2,4,9,8)である場合には、結合テーブルは以下のテーブルとなる。
【０１３９】
以下のテーブルの、１行目から２行目のテーブルがテーブル(1)に相当し、３行目のテーブルがテーブル(2)に相当し、４行目から５行目のテーブルがテーブル(3)に相当する。
【０１４０】
【数８】
2020036127.tif 000010
【０１４１】
上記（Ｅ）の結合テーブルは、レコード数が３であり、キーのベクトルk0=(1,2,3)と、１個の属性の属性値のベクトルv0=(5,10,1)とから構成されている第一テーブルと、キーのベクトルk1=(1,3,4,5)と、１個の属性の属性値のベクトルv1=(2,4,9,8)とから構成されている第二テーブルとを完全外部結合したテーブルとなっている。
【０１４２】
このように、逆置換を用いることで、キー重複がない場合に非特許文献１の技術よりも高速に秘匿性を保ったまま２つのテーブルを結合することができる。
【０１４３】
[秘密結合情報生成システム]
なお、上記説明した秘密結合システムの秘密計算装置１nの中のベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n及び第二ベクトル分離部１１４n、第三置換適用部１１５nの部分が、秘密結合情報生成システムである。
【０１４４】
言い換えれば、秘密結合情報生成システムの秘密計算装置１nは、図２、図６及び図７において破線で示すように、ベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n及び第二ベクトル分離部１１４n、第三置換適用部１１５を備えている。
【０１４５】
秘密結合情報生成方法は、秘密結合情報生成システムの秘密計算装置１nの各部が、ステップＳ１からステップＳ１５の各ステップを行うことにより実現される。ステップＳ１からステップＳ１５の処理は、上記に説明したものと同様であるため重複説明を省略する。
【０１４６】
秘密結合情報生成システムの複数の秘密結合情報生成部１1, …, １Nは、ベクトルk0のシェア[k0]、ベクトルk1のシェア[k1]、置換π0のシェア[π0]及び置換π1のシェア[π1]を用いて、第一テーブルの各ベクトルを置換σ0で置換すると第一テーブルと第二テーブルに共通するキーのレコードが先頭側に移動する置換σ0の逆置換σ0-1に置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、第二テーブルの各ベクトルを置換σ1で置換すると第一テーブルと第二テーブルに共通するキーのレコードが先頭側に移動する置換σ1の逆置換σ1-1に置換π1を適用したベクトルπ1(σ1-1)のシェア[π1(σ1-1)]と、第一テーブルのi番目のレコードが、第一テーブルと第二テーブルに共通するキーのレコードかどうかを表す値g0,iから構成されるベクトルg0のシェア[g0]と、第二テーブルのi番目のレコードが、第一テーブルと第二テーブルに共通するキーのレコードかどうかを表す値g1,iから構成されるベクトルg1のシェア[g1]と、を生成する言える。
【０１４７】
［変形例］
以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。
【０１４８】
例えば、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を横に結合すると、
【０１５２】
【数９】
2020036127.tif 000011
【０１５３】
となる。このようにして並べたものを行列とみなし、この行列の各行を1レコードのキーのビット表現とみなすと、(1,2,3,1,3,4,5)というキーのビット表現のベクトルが得られる。このベクトルをステップＳ２以降で使うk'として用いてもよい。このようにして、複合キーの場合も処理できる。
【０１５４】
複合キーでは、キーの重複とは、全てのキー属性の値の組み合わせの観点で重複するかどうかであり、個々の属性の値が重複しただけでは重複とはみなさないとする。例えば、組み合わせ(1,0)と(1,1)は重複ではない。
【０１５５】
実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１５６】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１５７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１５８】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１５９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１６０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2020036127.tif 000012
【図２】
2020036127.tif 000013
【図３】
2020036127.tif 000014
【図４】
2020036127.tif 000015
【図５】
2020036127.tif 000016
【図６】
2020036127.tif 000017
【図７】
2020036127.tif 000018
【手続補正書】
【提出日】令和3年2月8日(2021.2.8)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
この発明の一態様による秘密結合システムは、上記の秘密結合情報生成システムの複数の秘密計算装置を含み、これらの複数の秘密計算装置は、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、ベクトルk1のシェア[k1]及びベクトルv1のシェア[v1]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1'=(π1(σ1-1))-1(π1(k1'))のシェア[k1']と、ベクトルv1'=(π1(σ1-1))-1(π1(v1'))のシェア[v1']とを計算する複数の第四置換適用部と、シェア[k0']、シェア[v0']、シェア[k1']及びシェア[v1']を用いて、ベクトルg0又はベクトルg1の０の要素の数をcとして、ベクトルk0'の先頭からc個の要素を抜き出したベクトルと、ベクトルv0'の先頭からc個の要素を抜き出したベクトルと、ベクトルk1'の先頭からc個の要素を抜き出したベクトルと、ベクトルv1'の先頭からc個の要素を抜き出したベクトルとを結合した結合テーブルを生成する複数の第一結合テーブル生成部と、を更に含む。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
【図１】図１は、秘密結合システムの機能構成を例示する図である。
【図２】図２は、内部結合を行う秘密結合システムの秘密計算装置の機能構成を例示する図である。
【図３】図３は、内部結合を行う秘密結合方法、左外部結合を行う秘密結合方法、完全外部結合を行う秘密結合方法の処理手続きを例示する図である。
【図４】図４は、内部結合を行う秘密結合方法、完全外部結合を行う秘密結合方法の処理手続きを例示する図である。
【図５】図５は、左外部結合を行う秘密結合方法の処理手続きを例示する図である。
【図６】図６は、左外部結合を行う秘密結合システムの秘密計算装置の機能構成を例示する図である。
【図７】図７は、完全外部結合を行う秘密結合システムの秘密計算装置の機能構成を例示する図である。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
[内部結合を行う秘密結合システム及び方法]
図１を参照して、実施形態の秘密結合システムの構成例を説明する。この秘密結合システム及び方法は、いわゆる内部結合を行うものである。すなわち、この秘密結合システムは、秘匿性を保ちつつ、第一テーブル及び第二テーブルに共通するレコードを結合する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
図２を参照して、秘密結合システムに含まれる秘密計算装置１n（n=1, …, N）の構成例を説明する。秘密結合システムの秘密計算装置１nは、例えば、図２に示すように、ベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n、第二ベクトル分離部１１４n、第三置換適用部１１５n、第四置換適用部１１６n及び第一結合テーブル生成部１１７nを備えている。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
シェア[σ]は、第一置換適用部１４1,…,１４N、第一逆置換適用部１１１1,…,１１１N及び第二逆置換適用部１１３1,…,１１３Nに出力される。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
シェア[e']は、第二置換計算部１７1,…,１７N及び第一逆置換適用部１１１1,…,１１１Nに出力される。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
シェア[f']は、第四ベクトル生成部１９1,…,１９N及び第五ベクトル生成部１１０1,…,１１０Nに出力される。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００６８
【補正方法】変更
【補正の内容】
【００６８】
＜ステップＳ１０＞
第五ベクトル生成部１１０1,…,１１０Nに、シェア[f']、シェア[s]及びシェア[s']が入力される。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
シェア[σ'']は、第二逆置換適用部１１３1,…,１１３Nに出力される。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００７８
【補正方法】変更
【補正の内容】
【００７８】
シェア[g1]は、出力される。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
例えば、ベクトルe''=(0,1,0,0,0,1,1)である場合には、ベクトルg0=(0,1,0)となり、ベクトルg1=(0,0,1,1)となる。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００８０
【補正方法】変更
【補正の内容】
【００８０】
＜ステップＳ１３＞
第二逆置換適用部１１３1,…,１１３Nに、シェア[σ'']、シェア[σ]及びシェア[σ']が入力される。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００８６
【補正方法】変更
【補正の内容】
【００８６】
シェア[σ0-1]及びシェア[σ1-1]は、第三置換適用部１１５1,…,１１５Nに出力される。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００８８
【補正方法】変更
【補正の内容】
【００８８】
＜ステップＳ１５＞
第三置換適用部１１５1,…,１１５Nに、シェア[σ0-1]、シェア[σ１-1]、置換π0のシェア[π0]及び置換π1のシェア[π1]が入力される。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００９７
【補正方法】変更
【補正の内容】
【００９７】
例えば、ベクトルk0=(1,2,3)であり、ベクトルv0=(5,10,1)であり、ベクトルk1=(1,3,4,5)であり、ベクトルv1=(2,4,9,8)であり、置換π0が上記式（３）により表される置換であり、置換π1が上記式（４）により表される置換である場合には、ベクトルk0'=(1,3,2)となり、ベクトルv0'=(5,1,10)となり、ベクトルk1'=(1,3,4,5)となり、ベクトルv1'=(2,4,9,8)となる。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１００
【補正方法】変更
【補正の内容】
【０１００】
例えば、ベクトルg0=(0,1,0)であり、ベクトルk0'=(1,3,2)であり、ベクトルv0'=(5,1,10)であり、ベクトルk1'=(1,3,4,5)であり、ベクトルv1'=(2,4,9,8)である場合には、結合テーブルは以下のテーブルとなる。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０１０２
【補正方法】変更
【補正の内容】
【０１０２】
上記（Ａ）の結合テーブルは、レコード数が３であり、キーのベクトルk0=(1,2,3)と、１個の属性の属性値のベクトルv0=(5,10,1)とから構成されている第一テーブルと、キーのベクトルk1=(1,3,4,5)と、１個の属性の属性値のベクトルv1=(2,4,9,8)とから構成されている第二テーブルとを内部結合したテーブルとなっている。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０１０４
【補正方法】変更
【補正の内容】
【０１０４】
[左外部結合を行う秘密結合システム及び方法]
図６を参照して、実施形態の秘密結合システムの構成例を説明する。この秘密結合システム及び方法は、いわゆる左外部結合を行うものである。すなわち、この秘密結合システムは、秘匿性を保ちつつ、第一テーブル及び第二テーブルに共通するレコードと、第一テーブルのみに存在するレコードとを結合する。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】０１０６
【補正方法】変更
【補正の内容】
【０１０６】
左外部結合を行う秘密結合方法は、ステップＳ１６からステップＳ１７の処理を行わない代わりに、ステップＳ１８からステップＳ２０の処理を行う点を除けば、内部結合を行う秘密結合方法と同様である。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】０１０８
【補正方法】変更
【補正の内容】
【０１０８】
秘密結合システムの秘密計算装置１nは、例えば、図６に示すように、ベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n、第二ベクトル分離部１１４n、第三置換適用部１１５n、フィルタリング部１１８n、第五置換適用部１１９n及び第二結合テーブル生成部１２０nを備えている。                    
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】０１１７
【補正方法】変更
【補正の内容】
【０１１７】
第五置換適用部１１９1,…,１１９Nは、ベクトルk0のシェア[k0]、ベクトルv0のシェア[v0]、変形第二テーブルのキーのベクトルであるk1'のシェア[k1']、変形第二テーブルの属性値のベクトルであるv1'のシェア[v1']、置換π0のシェア[π0]、置換π1のシェア[π1]、シェア[π0(σ0-1)]及びシェア[π1(σ1-1)]を用いて、ベクトルk0'=(π0(σ0-1))-1(π0(k0))のシェア[k0']と、ベクトルv0'=(π0(σ0-1))-1(π0(v0))のシェア[v0']と、ベクトルk1''=(π1(σ1-1))-1(π1(k1'))のシェア[k1'']と、ベクトルv1''=(π1(σ1-1))-1(π1(v1'))のシェア[v1'']とを計算する（ステップＳ１９）。    
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】０１２０
【補正方法】変更
【補正の内容】
【０１２０】
＜ステップＳ２０＞
第二結合テーブル生成部１２０1,…,１２０Nに、シェア[k0']、シェア[v0']、シェア[k1'']及びシェア[v1'']が入力される。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】０１２１
【補正方法】変更
【補正の内容】
【０１２１】
第二結合テーブル生成部１２０1,…,１２０Nは、シェア[k0']、シェア[v0']、シェア[k1'']及びシェア[v1'']を用いて、m0<m1である場合には、ベクトルk0'と、ベクトルv0'と、ベクトルk1''の先頭からm0個の要素を抜き出したベクトルと、ベクトルv1''の先頭からm0個の要素を抜き出したベクトルとを結合した結合テーブルを、m0>m1である場合には、ベクトルk1''にm0-m1個の予め定めた空を示す値ukの要素を追加したベクトルと、ベクトルv1''にm0-m1個の予め定めた空を示す値uvの要素を追加したベクトルと、ベクトルk0'と、ベクトルv0'とを結合した結合テーブルを生成する（ステップＳ２０）。
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】０１３３
【補正方法】変更
【補正の内容】
【０１３３】
秘密結合システムの秘密計算装置１nは、例えば、図７に示すように、ベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n、第二ベクトル分離部１１４n、第三置換適用部１１５n、第四置換適用部１１６n及び第三結合テーブル生成部１２１nを備えている。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】０１３８
【補正方法】変更
【補正の内容】
【０１３８】
例えば、ベクトルg0=(0,1,0)であり、ベクトルk0'=(1,3,2)であり、ベクトルv0'=(5,1,10)であり、ベクトルk1'=(1,3,4,5)であり、ベクトルv1'=(2,4,9,8)である場合には、結合テーブルは以下のテーブルとなる。
【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】０１４３
【補正方法】変更
【補正の内容】
【０１４３】
[秘密結合情報生成システム]
なお、上記説明した秘密結合システムの秘密計算装置１nの中のベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n、第二ベクトル分離部１１４n、第三置換適用部１１５nの部分が、秘密結合情報生成システムである。
【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】０１４４
【補正方法】変更
【補正の内容】
【０１４４】
言い換えれば、秘密結合情報生成システムの秘密計算装置１nは、図２、図６及び図７において破線で示すように、ベクトル結合部１１n、第一ベクトル生成部１２n、第一置換計算部１３n、第一置換適用部１４n、第二ベクトル生成部１５n、第三ベクトル生成部１６n、第二置換計算部１７n、第二置換適用部１８n、第四ベクトル生成部１９n、第五ベクトル生成部１１０n、第一逆置換適用部１１１n、第一ベクトル分離部１１２n、第二逆置換適用部１１３n、第二ベクトル分離部１１４n、第三置換適用部１１５nを備えている。
【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】０１４６
【補正方法】変更
【補正の内容】
【０１４６】
秘密結合情報生成システムの複数の秘密結合情報生成部は、ベクトルk0のシェア[k0]、ベクトルk1のシェア[k1]、置換π0のシェア[π0]及び置換π1のシェア[π1]を用いて、第一テーブルの各ベクトルを置換σ0で置換すると第一テーブルと第二テーブルに共通するキーのレコードが先頭側に移動する置換σ0の逆置換σ0-1に置換π0を適用したベクトルπ0(σ0-1)のシェア[π0(σ0-1)]と、第二テーブルの各ベクトルを置換σ1で置換すると第一テーブルと第二テーブルに共通するキーのレコードが先頭側に移動する置換σ1の逆置換σ1-1に置換π1を適用したベクトルπ1(σ1-1)のシェア[π1(σ1-1)]と、第一テーブルのi番目のレコードが、第一テーブルと第二テーブルに共通するキーのレコードかどうかを表す値g0,iから構成されるベクトルg0のシェア[g0]と、第二テーブルのi番目のレコードが、第一テーブルと第二テーブルに共通するキーのレコードかどうかを表す値g1,iから構成されるベクトルg1のシェア[g1]と、を生成すると言える。
【国際調査報告】
2020036127.tif 000019
2020036127.tif 000020
2020036127.tif 000021
2020036127.tif 000022