(57)【要約】【課題】秘密計算によって、表に含まれる情報を秘密にしたまま、効率良く、２つ以上の表を、表の大きさが秘密にされた表に等結合する等結合技術を提供する。【解決手段】q個の秘匿化された表[[S]],[[T1]],…,[[Tq-1]]の等結合であって、各表[[Ti]]について、表[[Ti]]のレコード数をmiとし，大きさmiのベクトルの秘匿文（タグベクトル）[[t→S]],[[t→T1']],…,[[t→Tq-1']]を作成し、表とタグを使ってタグの平文の値の関係の計算を行い、各([[S]],[[t→S]]),([[T1']],[[t→T1']]),…,([[Tq-1']],[[t→Tq-1']])をそれぞれランダム置換してから[[tS]],[[t→T1']],…,[[t→Tq-1']]を復元し、タグの平文の値の関係と復元されたタグに基づいて等結合された表を構築する。【選択図】図１
2014139640.tif 000002
【特許請求の範囲】
【請求項１】
複数の秘密計算装置を含み、これら秘密計算装置の協調計算によって、q個の行列表示された表S,T1,…,Tq-1（ただし、Sはm0×n0行列、Tiはmi×ni行列(1≦i<q)とする）の秘匿文[[S]],[[T1]],…,[[Tq-1]]に対して、S,T1,…,Tq-1を等結合してダミーの行（以下、行をレコードといい、ダミーの行を空レコードという）を加えた表R（ただし、m∩をm∩=min(m0,…,mq-1)、nをn=Σi=0q-1 niとして、Rはm∩×n行列である）の秘匿文[[R]]と、表Rの空レコードの位置を特定するためのベクトルg→（以下、空フラグという）の秘匿文[[g→]]を出力する等結合システムであって、
上記等結合システムでは、上記複数の秘密計算装置の協調計算によって、
各整数i∈[1,q)について、[[S]]と[[Ti]]とに共通の属性については、その属性値として[[S]]の値を用い、[[S]]と[[Ti]]とに共通しない属性については、その属性値として任意の秘匿値を用いることによって、レコード数が[[S]]と同じで、[[S]]と[[Ti]]に共通の属性を含む秘匿化された表[[Si']]を[[Ti]]に接続した表[[Ti']]を作成し、
[[S]],[[T1']],…,[[Tq-1']]に対して、対応する表のレコード数と同じ要素数を持ち、対応する表に含まれるレコードを識別するための任意の値を要素に持つベクトルを秘匿化およびランダム置換したタグベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]を作成し、
各整数i∈[1,q)について、
（a） [[t→]]:=[[t→S]]||[[t→Ti']]、[[s→]]:=[[1]]m0||[[0]]mi+m0、[[s→']]:=[[0]]m0+mi||[[1]]m0、[[S]]と[[Ti']]のキー属性を連結したベクトル[[k→]]を作成し、
（b） ([[t→]],[[s→]],[[s→']])を[[k→]]に従って安定ソートし、
（c） [[u→]]を、
【数２０】
2014139640.tif 000023
として定め、
（d） [[u→]],[[t→]],[[s→']]を並べた([[u→]],[[t→]],[[s→']])をランダム置換し、
（e） [[u→]]を復元してu→を得て、
（f） u→[j]≠0を満たす各jについて、[[t→]][j]を復元して並べたベクトルt→i、u→[j]を並べたベクトルu→i、[[s→']][j]を並べたベクトル[[f→i]]を作成し、
各([[S]],[[t→S]]),([[T1']],[[t→T1']]),…,([[Tq-1']],[[t→Tq-1']])をそれぞれランダム置換してから、[[tS]],[[t→T1']],…,[[t→Tq-1']]を復元してタグベクトルの平文tS,t→T1',…,t→Tq-1'を得て、
[[R]]の第j行（1≦j≦m0）である[[R]][j]を、[[R]][j]=[[S]][j]||[[T1']][wj,1]||…||[[Tq-1']][wj,q-1]で計算することによって出力の表[[R]]を作成し（ただし、ここでの記号||は行ベクトルの列方向の連結を表す。また、wj,iは、ti[hj,i]=TTi'[wj,i]を満たす値であり、hj,iは、tS[j]=ui[hj,i]を満たす値である）、[[g→]]の第j要素である[[g→]][j]を、[[g→]][j]=[[f→1]][y1,j]∨…∨[[f→q-1]][yq-1,j]で計算することによって出力の空フラグ[[g→]]を作成する（ただし、yi,jは、tS[j]=ui[y1,j]を満たす値である）ことを特徴とし、
上記各秘密計算装置は、上記秘密計算を計算するための手段を備えている等結合システム。
【請求項２】
複数の秘密計算装置を含み、これら秘密計算装置の協調計算によって、大きさが秘匿されたq個の行列表示された表S,T1,…,Tq-1（ただし、Sはm0×n0行列、Tiはmi×ni行列(1≦i<q)とし、各表は、行にダミーの行（以下、ダミーの行を空レコードという）を含み、列に空レコードの位置を特定するための列ベクトルである空フラグを含んでいるとする）の秘匿文[[S]],[[T1]],…,[[Tq-1]]に対して、S,T1,…,Tq-1を等結合してダミーの行（以下、行をレコードという）を加えた表R（ただし、m∩をm∩=min(m0,…,mq-1)、nをn=Σi=0q-1 niとして、Rはm∩×n行列である）の秘匿文[[R]]と、表Rの空レコードの位置を特定するための空フラグg→の秘匿文[[g→]]を出力する等結合システムであって、
上記等結合システムでは、上記複数の秘密計算装置の協調計算によって、
各整数i∈[1,q)について、[[S]]と[[Ti]]とに共通の属性については、その属性値として[[S]]の値を用い、[[S]]と[[Ti]]とに共通しない属性については、その属性値として任意の秘匿値を用いることによって、レコード数が[[S]]と同じで、[[S]]と[[Ti]]に共通の属性を含む秘匿化された表[[Si']]を[[Ti]]に接続した表[[Ti']]を作成し、
[[S]],[[T1']],…,[[Tq-1']]に対して、対応する表のレコード数と同じ要素数を持ち、対応する表に含まれるレコードを識別するための任意の値を要素に持つベクトルを秘匿化およびランダム置換したタグベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]を作成し、
各整数i∈[1,q)について、
（a） [[t→]]:=[[t→S]]||[[t→Ti']]、[[s→]]:=[[1]]m0||[[0]]mi+m0、[[s→']]:=[[0]]m0+mi||[[1]]m0、[[t→']]:=[[*]]m0+mi||[[t→S]]、[[S]]と[[Ti']]のキー属性値を連結したベクトル[[k→]]、[[S]]と[[Ti]]と[[Si']]の空フラグを連結したベクトル[[z→]]を作成し（ただし、[[*]]は任意の秘匿文である）、
（b） ([[t→]],[[s→]],[[s→']],[[z→]],[[t→']])を([[z→]],[[k→]])に従って安定ソートし（ただし、([[z→]],[[k→]])は、[[z→]][j]||[[k→]][j]をj番目の要素とする(m0+mi+m0)行1列の列ベクトルである）、
（c） [[u→]]を
【数２１】
2014139640.tif 000024
として定め、
（d） [[u→]],[[t→]],[[s→']]を並べた([[u→]],[[t→]],[[s→']])をランダム置換し、
（e） [[u→]]を復元してu→を得て、
（f） u→[j]≠0を満たす各jについて、[[t→]][j]を復元して並べたベクトルt→i、u→[j]を並べたベクトルu→i、[[s→']][j]∨[[z→]][j]を計算して並べたベクトル[[f→i]]を作成し、
各([[S]],[[t→S]]),([[T1']],[[t→T1']]),…,([[Tq-1']],[[t→Tq-1']])をそれぞれランダム置換してから、[[tS]],[[t→T1']],…,[[t→Tq-1']]を復元してタグベクトルの平文tS,t→T1',…,t→Tq-1'を得て、
[[R]]の第j行（1≦j≦m0）である[[R]][j]を、[[R]][j]=[[S]][j]||[[T1']][wj,1]||…||[[Tq-1']][wj,q-1]で計算することによって出力の表[[R]]を作成し（ただし、ここでの記号||は行ベクトルの列方向の連結を表す。また、wj,iは、ti[hj,i]=TTi'[wj,i]を満たす値であり、hj,iは、tS[j]=ui[hj,i]を満たす値である）、[[g→]]の第j要素である[[g→]][j]を、[[g→]][j]=[[f→1]][y1,j]∨…∨[[f→q-1]][yq-1,j]で計算することによって出力の空フラグ[[g→]]を作成する（ただし、yi,jは、tS[j]=ui[y1,j]を満たす値である）ことを特徴とし、
上記各秘密計算装置は、上記秘密計算を計算するための手段を備えている等結合システム。
【請求項３】
複数の秘密計算装置による協調計算によって、q個の行列表示された表S,T1,…,Tq-1（ただし、Sはm0×n0行列、Tiはmi×ni行列(1≦i<q)とする）の秘匿文[[S]],[[T1]],…,[[Tq-1]]に対して、S,T1,…,Tq-1を等結合してダミーの行（以下、行をレコードといい、ダミーの行を空レコードという）を加えた表R（ただし、m∩をm∩=min(m0,…,mq-1)、nをn=Σi=0q-1 niとして、Rはm∩×n行列である）の秘匿文[[R]]と、表Rの空レコードの位置を特定するためのベクトルg→（以下、空フラグという）の秘匿文[[g→]]を出力する等結合方法であって、
上記複数の秘密計算装置の協調計算によって、
各整数i∈[1,q)について、[[S]]と[[Ti]]とに共通の属性については、その属性値として[[S]]の値を用い、[[S]]と[[Ti]]とに共通しない属性については、その属性値として任意の秘匿値を用いることによって、レコード数が[[S]]と同じで、[[S]]と[[Ti]]に共通の属性を含む秘匿化された表[[Si']]を[[Ti]]に接続した表[[Ti']]を作成するステップと、
[[S]],[[T1']],…,[[Tq-1']]に対して、対応する表のレコード数と同じ要素数を持ち、対応する表に含まれるレコードを識別するための任意の値を要素に持つベクトルを秘匿化およびランダム置換したタグベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]を作成するステップと、
各整数i∈[1,q)について、
（a） [[t→]]:=[[t→S]]||[[t→Ti']]、[[s→]]:=[[1]]m0||[[0]]mi+m0、[[s→']]:=[[0]]m0+mi||[[1]]m0、[[S]]と[[Ti']]のキー属性を連結したベクトル[[k→]]を作成し、
（b） ([[t→]],[[s→]],[[s→']])を[[k→]]に従って安定ソートし、
（c） [[u→]]を、
【数２２】
2014139640.tif 000025
として定め、
（d） [[u→]],[[t→]],[[s→']]を並べた([[u→]],[[t→]],[[s→']])をランダム置換し、
（e） [[u→]]を復元してu→を得て、
（f） u→[j]≠0を満たす各jについて、[[t→]][j]を復元して並べたベクトルt→i、u→[j]を並べたベクトルu→i、[[s→']][j]を並べたベクトル[[f→i]]を作成するステップと、
各([[S]],[[t→S]]),([[T1']],[[t→T1']]),…,([[Tq-1']],[[t→Tq-1']])をそれぞれランダム置換してから、[[tS]],[[t→T1']],…,[[t→Tq-1']]を復元してタグベクトルの平文tS,t→T1',…,t→Tq-1'を得るステップと、
[[R]]の第j行（1≦j≦m0）である[[R]][j]を、[[R]][j]=[[S]][j]||[[T1']][wj,1]||…||[[Tq-1']][wj,q-1]で計算することによって出力の表[[R]]を作成し（ただし、ここでの記号||は行ベクトルの列方向の連結を表す。また、wj,iは、ti[hj,i]=TTi'[wj,i]を満たす値であり、hj,iは、tS[j]=ui[hj,i]を満たす値である）、[[g→]]の第j要素である[[g→]][j]を、[[g→]][j]=[[f→1]][y1,j]∨…∨[[f→q-1]][yq-1,j]で計算することによって出力の空フラグ[[g→]]を作成する（ただし、yi,jは、tS[j]=ui[y1,j]を満たす値である）ステップと
を有する等結合方法。
【請求項４】
複数の秘密計算装置による協調計算によって、大きさが秘匿されたq個の行列表示された表S,T1,…,Tq-1（ただし、Sはm0×n0行列、Tiはmi×ni行列(1≦i<q)とし、各表は、行にダミーの行（以下、ダミーの行を空レコードという）を含み、列に空レコードの位置を特定するための列ベクトルである空フラグを含んでいるとする）の秘匿文[[S]],[[T1]],…,[[Tq-1]]に対して、S,T1,…,Tq-1を等結合してダミーの行（以下、行をレコードという）を加えた表R（ただし、m∩をm∩=min(m0,…,mq-1)、nをn=Σi=0q-1 niとして、Rはm∩×n行列である）の秘匿文[[R]]と、表Rの空レコードの位置を特定するための空フラグg→の秘匿文[[g→]]を出力する等結合方法であって、
上記複数の秘密計算装置の協調計算によって、
各整数i∈[1,q)について、[[S]]と[[Ti]]とに共通の属性については、その属性値として[[S]]の値を用い、[[S]]と[[Ti]]とに共通しない属性については、その属性値として任意の秘匿値を用いることによって、レコード数が[[S]]と同じで、[[S]]と[[Ti]]に共通の属性を含む秘匿化された表[[Si']]を[[Ti]]に接続した表[[Ti']]を作成するステップと、
[[S]],[[T1']],…,[[Tq-1']]に対して、対応する表のレコード数と同じ要素数を持ち、対応する表に含まれるレコードを識別するための任意の値を要素に持つベクトルを秘匿化およびランダム置換したタグベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]を作成するステップと、
各整数i∈[1,q)について、
（a） [[t→]]:=[[t→S]]||[[t→Ti']]、[[s→]]:=[[1]]m0||[[0]]mi+m0、[[s→']]:=[[0]]m0+mi||[[1]]m0、[[t→']]:=[[*]]m0+mi||[[t→S]]、[[S]]と[[Ti']]のキー属性値を連結したベクトル[[k→]]、[[S]]と[[Ti]]と[[Si']]の空フラグを連結したベクトル[[z→]]を作成し（ただし、[[*]]は任意の秘匿文である）、
（b） ([[t→]],[[s→]],[[s→']],[[z→]],[[t→']])を([[z→]],[[k→]])に従って安定ソートし（ただし、([[z→]],[[k→]])は、[[z→]][j]||[[k→]][j]をj番目の要素とする(m0+mi+m0)行1列の列ベクトルである）、
（c） [[u→]]を
【数２３】
2014139640.tif 000026
として定め、
（d） [[u→]],[[t→]],[[s→']]を並べた([[u→]],[[t→]],[[s→']])をランダム置換し、
（e） [[u→]]を復元してu→を得て、
（f） u→[j]≠0を満たす各jについて、[[t→]][j]を復元して並べたベクトルt→i、u→[j]を並べたベクトルu→i、[[s→']][j]∨[[z→]][j]を計算して並べたベクトル[[f→i]]を作成するステップと、
各([[S]],[[t→S]]),([[T1']],[[t→T1']]),…,([[Tq-1']],[[t→Tq-1']])をそれぞれランダム置換してから、[[tS]],[[t→T1']],…,[[t→Tq-1']]を復元してタグベクトルの平文tS,t→T1',…,t→Tq-1'を得るステップと、
[[R]]の第j行（1≦j≦m0）である[[R]][j]を、[[R]][j]=[[S]][j]||[[T1']][wj,1]||…||[[Tq-1']][wj,q-1]で計算することによって出力の表[[R]]を作成し（ただし、ここでの記号||は行ベクトルの列方向の連結を表す。また、wj,iは、ti[hj,i]=TTi'[wj,i]を満たす値であり、hj,iは、tS[j]=ui[hj,i]を満たす値である）、[[g→]]の第j要素である[[g→]][j]を、[[g→]][j]=[[f→1]][y1,j]∨…∨[[f→q-1]][yq-1,j]で計算することによって出力の空フラグ[[g→]]を作成する（ただし、yi,jは、tS[j]=ui[y1,j]を満たす値である）ステップと
を有する等結合方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算によって、表に含まれる情報を秘密にしたまま、複数の表に共通のキー属性を鎹として複数の表の等結合を行う等結合技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元することなく指定された演算の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば非特許文献１参照）。非特許文献１の方法では、数値を復元することのできる複数の情報を３つの秘密計算装置に分散するという暗号化を行い、数値を復元することなく、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。一般に、分散数は３に限らずＰ（Ｐは３以上の所定の定数）とすることができ、Ｐ個の秘密計算装置による協調計算によって秘密計算を実現するプロトコルはマルチパーティプロトコルと呼ばれる。
【０００３】
ところで、表に対するデータベース処理では多くの場合、データは複数の属性値（属性に対応する値であり、表１の例では属性であるID、契約、住所、身長、体重のそれぞれの具体的な値“１”,“東京都”,“１８２”,“６２”などである）の組からなるレコード（表１に例示される表の各行のこと）の集合からなる表単位で管理される。データベース処理で重要な処理の一つに等結合がある。等結合は、表１のような複数の表を入力とし、キーと呼ばれる属性（キー属性）の値（キー属性値）がすべての表で共通のレコードを抜き出して、これらを横に並べた新しい表を得る計算である。例えば、表１の各表を、各表に共通のキー属性（この例ではID）を基準として等結合を行うと表２のような表が得られる。関係データベースではデータを多くの小さな表に分割して管理し、利用時に必要な表を等結合して処理を行うことが一般的であり、等結合は非常に重要な処理である。
【表１】
2014139640.tif 000003
【０００４】
秘密計算によって表の結合を実現した方法として、非特許文献２の方法や非特許文献３の方法がある。非特許文献２の方法では、まず入力された複数の表の直積を計算し、その後、結合後の表に含まれない行を削除することにより、出力の表の大きさを秘密にしたまま表の結合を実現している。非特許文献３の方法では、各表のキー属性値を並べてソートすることによって効率よく表の結合を実現している。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】千田浩司、濱田浩気、五十嵐大、高橋克巳、“軽量検証可能３パーティ秘匿関数計算の再考”、In CSS、2010．
【非特許文献２】志村正法、遠藤つかさ、宮崎邦彦、吉浦裕、“安全で機能制限のないデータベースを実現するマルチパーティプロトコルを用いた関係代数演算”、情報処理学会研究報告、CSEC、Vol. 2008、No. 71、pp.187-193、2008.
【非特許文献３】濱田浩気、菊池亮、五十嵐大、千田浩司、“秘匿計算上の結合アルゴリズム”、人工知能学会全国大会（第２６回）論文集、June 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術は表の大きさを秘密にすることと計算効率を両立させることができなかった。
【０００７】
秘密計算がマルチパーティプロトコルで実現されるものとして計算効率の評価を行う場合、マルチパーティプロトコルは複数のパーティ間で通信を行いながら協調計算を行う方式であり、一般的なシステム構成では各パーティが単独で行うローカルの計算に比べて通信に要する時間が著しく大きいので、ローカルの計算は無視できるものとみなせる。従って、通信したデータの量（通信量）の尺度で計算効率の評価を行う。このとき、非特許文献２の方法は、出力の表の大きさを秘密にすることができるが、表の数をh、各表の行数をそれぞれmi(1≦i≦h)とすると、通信量がＯ(Π1≦i≦h mi)と膨大になってしまうという課題がある。非特許文献３の方法は、m=Σ1≦i≦h miとすると、通信量がＯ(m log m)であるが、入出力の表の大きさを秘密にすることができない。また、非特許文献３の方法は３つ以上の表の等結合が可能であるが、非特許文献２の方法は２つの表の等結合を行う方法であり、３つ以上の表の等結合を行う場合、２つの表の等結合を繰り返し実行しなくてはならず非効率である。
【０００８】
そこで本発明は、秘密計算によって、表に含まれる情報を秘密にしたまま、効率良く、２つ以上の表を、表の大きさが秘密にされた表に等結合する等結合技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の等結合技術は、次のとおりである。
複数の秘密計算装置による協調計算によって、q個の行列表示された表S,T1,…,Tq-1（ただし、Sはm0×n0行列、Tiはmi×ni行列(1≦i<q)とする）の秘匿文[[S]],[[T1]],…,[[Tq-1]]に対して、S,T1,…,Tq-1を等結合してダミーの行（以下、行をレコードといい、ダミーの行を空レコードという）を加えた表R（ただし、m∩をm∩=min(m0,…,mq-1)、nをn=Σi=0q-1 niとして、Rはm∩×n行列である）の秘匿文[[R]]と、表Rの空レコードの位置を特定するためのベクトルg→（以下、空フラグという）の秘匿文[[g→]]を出力する等結合技術であり、複数の秘密計算装置の協調計算によって、各整数i∈[1,q)について、[[S]]と[[Ti]]とに共通の属性については、その属性値として[[S]]の値を用い、[[S]]と[[Ti]]とに共通しない属性については、その属性値として任意の秘匿値を用いることによって、レコード数が[[S]]と同じで、[[S]]と[[Ti]]に共通の属性を含む秘匿化された表[[Si']]を[[Ti]]に接続した表[[Ti']]を作成し、[[S]],[[T1']],…,[[Tq-1']]に対して、対応する表のレコード数と同じ要素数を持ち、対応する表に含まれるレコードを識別するための任意の値を要素に持つベクトルを秘匿化およびランダム置換したタグベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]を作成し、各整数i∈[1,q)について、
（a） [[t→]]:=[[t→S]]||[[t→Ti']]、[[s→]]:=[[1]]m0||[[0]]mi+m0、[[s→']]:=[[0]]m0+mi||[[1]]m0、[[S]]と[[Ti']]のキー属性を連結したベクトル[[k→]]を作成し、
（b） ([[t→]],[[s→]],[[s→']])を[[k→]]に従って安定ソートし、
（c） [[u→]]を、
【数１】
2014139640.tif 000004
として定め、
（d） [[u→]],[[t→]],[[s→']]を並べた([[u→]],[[t→]],[[s→']])をランダム置換し、
（e） [[u→]]を復元してu→を得て、
（f） u→[j]≠0を満たす各jについて、[[t→]][j]を復元して並べたベクトルt→i、u→[j]を並べたベクトルu→i、[[s→']][j]を並べたベクトル[[f→i]]を作成し、各([[S]],[[t→S]]),([[T1']],[[t→T1']]),…,([[Tq-1']],[[t→Tq-1']])をそれぞれランダム置換してから、[[tS]],[[t→T1']],…,[[t→Tq-1']]を復元してタグベクトルの平文tS,t→T1',…,t→Tq-1'を得て、[[R]]の第j行（1≦j≦m0）である[[R]][j]を、[[R]][j]=[[S]][j]||[[T1']][wj,1]||…||[[Tq-1']][wj,q-1]で計算することによって出力の表[[R]]を作成し（ただし、ここでの記号||は行ベクトルの列方向の連結を表す。また、wj,iは、ti[hj,i]=TTi'[wj,i]を満たす値であり、hj,iは、tS[j]=ui[hj,i]を満たす値である）、[[g→]]の第j要素である[[g→]][j]を、[[g→]][j]=[[f→1]][y1,j]∨…∨[[f→q-1]][yq-1,j]で計算することによって出力の空フラグ[[g→]]を作成する（ただし、yi,jは、tS[j]=ui[y1,j]を満たす値である）。
【００１０】
あるいは、複数の秘密計算装置による協調計算によって、大きさが秘匿されたq個の行列表示された表S,T1,…,Tq-1（ただし、Sはm0×n0行列、Tiはmi×ni行列(1≦i<q)とし、各表は、行にダミーの行（以下、ダミーの行を空レコードという）を含み、列に空レコードの位置を特定するための列ベクトルである空フラグを含んでいるとする）の秘匿文[[S]],[[T1]],…,[[Tq-1]]に対して、S,T1,…,Tq-1を等結合してダミーの行（以下、行をレコードという）を加えた表R（ただし、m∩をm∩=min(m0,…,mq-1)、nをn=Σi=0q-1 niとして、Rはm∩×n行列である）の秘匿文[[R]]と、表Rの空レコードの位置を特定するための空フラグg→の秘匿文[[g→]]を出力する等結合技術であって、複数の秘密計算装置の協調計算によって、各整数i∈[1,q)について、[[S]]と[[Ti]]とに共通の属性については、その属性値として[[S]]の値を用い、[[S]]と[[Ti]]とに共通しない属性については、その属性値として任意の秘匿値を用いることによって、レコード数が[[S]]と同じで、[[S]]と[[Ti]]に共通の属性を含む秘匿化された表[[Si']]を[[Ti]]に接続した表[[Ti']]を作成し、[[S]],[[T1']],…,[[Tq-1']]に対して、対応する表のレコード数と同じ要素数を持ち、対応する表に含まれるレコードを識別するための任意の値を要素に持つベクトルを秘匿化およびランダム置換したタグベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]を作成し、
各整数i∈[1,q)について、
（a） [[t→]]:=[[t→S]]||[[t→Ti']]、[[s→]]:=[[1]]m0||[[0]]mi+m0、[[s→']]:=[[0]]m0+mi||[[1]]m0、[[t→']]:=[[*]]m0+mi||[[t→S]]、[[S]]と[[Ti']]のキー属性値を連結したベクトル[[k→]]、[[S]]と[[Ti]]と[[Si']]の空フラグを連結したベクトル[[z→]]を作成し（ただし、[[*]]は任意の秘匿文である）、
（b） ([[t→]],[[s→]],[[s→']],[[z→]],[[t→']])を([[z→]],[[k→]])に従って安定ソートし（ただし、([[z→]],[[k→]])は、[[z→]][j]||[[k→]][j]をj番目の要素とする(m0+mi+m0)行1列の列ベクトルである）、
（c） [[u→]]を
【数２】
2014139640.tif 000005
として定め、
（d） [[u→]],[[t→]],[[s→']]を並べた([[u→]],[[t→]],[[s→']])をランダム置換し、
（e） [[u→]]を復元してu→を得て、
（f） u→[j]≠0を満たす各jについて、[[t→]][j]を復元して並べたベクトルt→i、u→[j]を並べたベクトルu→i、[[s→']][j]∨[[z→]][j]を計算して並べたベクトル[[f→i]]を作成し、各([[S]],[[t→S]]),([[T1']],[[t→T1']]),…,([[Tq-1']],[[t→Tq-1']])をそれぞれランダム置換してから、[[tS]],[[t→T1']],…,[[t→Tq-1']]を復元してタグベクトルの平文tS,t→T1',…,t→Tq-1'を得て、[[R]]の第j行（1≦j≦m0）である[[R]][j]を、[[R]][j]=[[S]][j]||[[T1']][wj,1]||…||[[Tq-1']][wj,q-1]で計算することによって出力の表[[R]]を作成し（ただし、ここでの記号||は行ベクトルの列方向の連結を表す。また、wj,iは、ti[hj,i]=TTi'[wj,i]を満たす値であり、hj,iは、tS[j]=ui[hj,i]を満たす値である）、[[g→]]の第j要素である[[g→]][j]を、[[g→]][j]=[[f→1]][y1,j]∨…∨[[f→q-1]][yq-1,j]で計算することによって出力の空フラグ[[g→]]を作成する（ただし、yi,jは、tS[j]=ui[y1,j]を満たす値である）。
【発明の効果】
【００１１】
本発明に拠れば、詳細は後述の実施形態に譲るが、秘密計算によって、表に含まれる情報を秘密にしたまま、効率良く、２つ以上の表を、表の大きさが秘密にされた表に等結合することができる。
【図面の簡単な説明】
【００１２】
【図１】実施形態における等結合の処理手順を示す図。
【発明を実施するための形態】
【００１３】
本発明の実施形態を説明する。
後述する等結合アルゴリズムは、既存の秘密計算上の演算の組み合わせで構築される。この等結合アルゴリズムが必要とする演算は、秘匿化、復元、加算、減算、乗算、ランダム置換、安定ソートである。秘匿化、復元、加算、減算、乗算は例えば上記非特許文献１を、ランダム置換は例えば参考文献１を、安定ソートは例えば参考文献２に従えばよい。
（参考文献１）Sven Laur, Jan Willemson, and Bingsheng Zhang. "Round-efficient oblivious database manipulation" In Xuejia Lai, Jianying Zhou, and Hui Li, editors, ISC, Vol. 7001 of LNCS, pp. 262-277. Springer, 2011.
（参考文献２）濱田浩気、五十嵐大、千田浩司、高橋克巳、“秘匿関数計算上の線形時間ソート”、In SCIS、pp.1-7、2011.
【００１４】
＜定義と記法＞
以下、値はすべて有限環ZN上の値とする。ベクトルa→とベクトルb→を連結したベクトルをa→||b→と書く。すなわち、a→=(a1,…,am)T、b→=(b1,…,bn)Tのとき、a→||b→=(a1,…,am,b1,…,bn)Tである。Tは転置の記号である。特に断りがない限り、(a→1,…,a→Z)は、a→i=(a1,i,…,am,i)T（i=1,…,Z）とすると、ｍ行Ｚ列の行列を表す。行列Mのi行目の行ベクトルをM[i]と表記する。ベクトルv→のj番目の要素をv→[j]と表記する。
【００１５】
＜秘匿化と復元＞
a∈ZNを暗号化や秘密分散などの手段で秘匿化して得られた情報を[[a]]と表記する。ここで、Ｐ個の秘密計算装置による秘密計算を前提とすると、a∈ZNは複数（例えばＰ1個）の秘密値に分散されており、[[a]]は複数の秘密値ai（i∈{1,2,…,P1}）の集合を表している。各秘密計算装置は、各装置に割り当てられた秘密値ai（i∈{1,2,…,P1}）の一部を保有しているが、秘密値ai（i∈{1,2,…,P1}）の全部を保有していないものとする。[[a]]をaの秘匿文などと呼称し、aを秘匿文[[a]]の平文などと呼称する。ベクトルv→=(v1,…,vn)の各要素を秘匿化したベクトル([[v1]],…,[[vn]])を[[v→]]と表記する。ベクトル[[u→]]=([[u1]],…,[[um]])とベクトル[[v→]]=([[v1]],…,[[vn]])を結合したベクトル([[u1]],…,[[um]],[[v1]],…,[[vn]])を[[u→]]||[[v→]]と書く。aの秘匿文[[a]]をn個並べた秘匿文のベクトル([[a]],…,[[a]])を[[a]]nと略記する。行列Aの各要素を秘匿化した行列を[[A]]と表記する。
【００１６】
＜加算、減算、乗算＞
加算、減算、乗算の各演算は２つの値a,b∈ZNの秘匿文[[a]],[[b]]を入力とし、それぞれa+b、a-b、abの計算結果cの秘匿文[[c]]を計算する。これらの演算の実行をそれぞれ
[[c]] ← Add([[a]],[[b]]),
[[c]] ← Sub([[a]],[[b]]),
[[c]] ← Mul([[a]],[[b]])
と記述する。誤解を招く恐れのない場合は、Add([[a]],[[b]])、Sub([[a]],[[b]])、Mul([[a]],[[b]])をそれぞれ[[a]]+[[b]]、[[a]]-[[b]]、[[a]]×[[b]]と略記する。
【００１７】
＜論理和＞
論理和の演算は２つの値a,b∈{0,1}の秘匿文[[a]],[[b]]を入力とし、aとbの論理和cの秘匿文[[c]]を計算する。この演算の実行を
[[c]] ← [[a]] OR [[b]]
と記述し、ここでは
[[c]] ← [[a]]+[[b]]-[[a]]×[[b]]
の計算によって実現する。
【００１８】
＜ランダム置換＞
ランダム置換はベクトルの要素をランダムな順序で並べ替えたベクトルを出力する演算である。ここで扱う秘密計算でのランダム置換演算は、複数の秘匿化されたベクトルに対して同一のランダム置換を施す。すなわち、k個（1≦k）の大きさnのベクトルa→(1),…,a→(k)∈ZNnの秘匿文[[a→(1)]],…,[[a→(k)]]を入力とし、等結合システムに含まれるいずれの装置（全ての秘密計算装置を含む）も知ることのできないランダムな全単射πr:{1,…,n}→{1,…,n}についてb(i)πr(j)=a(i)j（1≦i≦k;1≦j≦n）を満たすベクトルb→(1),…,b→(k)∈ZNnの秘匿文[[b→(1)]],…,[[b→(k)]]を計算する。
【００１９】
＜安定ソート＞
ソートはベクトルの要素を昇順に並べ替えたベクトルを出力する演算である。入力のベクトルk→=(k1,…,kn)に対して出力されるベクトルh→=(h1,…,hn)はh1≦…≦hnを満たすk→の要素を並べ替えたベクトルである。安定ソートは、ソート演算で同じ値が存在した場合に同じ値の要素同士の順序を保存する演算である。k→とh→の各要素はある全単射πs:{1,…,n}→{1,…,n}についてhπs(i)=ki（1≦i≦n）を満たしており、安定ソートでは
πs(i)<πs(j) ⇔ (ki<kj) ∨ (ki=kj ∧ i<j)
が成り立つ。
ここで扱う秘密計算上の安定ソート演算は、複数のベクトルを入力とし、キーとするベクトルの要素の並べ替えに従って他のベクトルの要素の並べ替えを行う。すなわち、安定ソートのキーとする大きさnのベクトルk→∈ZNnとg個（1≦g）の大きさnのベクトルa→(1),…,a→(g)∈ZNnの秘匿文[[k→]],[[a→(1)]],…,[[a→(g)]]を入力とし、ベクトルk→を安定ソートしたときの並べ替えに従って各ベクトルa→(1),…,a→(g)の要素を並べ替えたベクトルb→(1),…,b→(g)∈ZNnの秘匿文[[b→(1)]],…,[[b→(g)]]を計算する。
【００２０】
＜表の大きさの秘匿＞
次に、表の大きさを秘密にする方法を説明する。ここで、表の大きさは表に含まれる行の数、つまり、レコード数である。表の大きさの秘匿は、本来の表に余分な偽物（ダミー）のレコード（空レコードと呼称する）を追加することによって実現する。表の真の大きさを推測できないようにするためには、表の大きさが本来の表が取り得る最大のレコード数以上となるように空レコードを追加すればよい。等結合は入力の表T0,…,Tq-1を等結合して得られる出力の表Rが|R|≦min(|T0|,…,|Tq-1|)を満たすので、出力の表の大きさがmin(|T0|,…,|Tq-1|)となるように空レコードを追加することで本来の出力の表の大きさを秘匿できる。
【００２１】
空レコードと通常のレコードの区別のため、大きさを秘匿された表に対して、空フラグと呼ぶベクトルを付与する。空フラグは、表の（見かけ上の）レコード数と同じ数の要素を持ち、第iレコードが空レコードならば第i要素が1、第iレコードが空レコードでないならば第i要素が0であるベクトルの秘匿文である。
【００２２】
《実施形態１》
実施形態１の等結合処理の入力はそれぞれ行列として与えられたq個の表T0,…,Tq-1の秘匿文[[T0]],…,[[Tq-1]]である。一般性を失うことなく、T0をレコード数が最小の表、各表の１列目を各表に共通のキー属性（例えばID）を表す列とする。実施形態１では、これら入力の表は大きさが秘匿されていない表である。
【００２３】
実施形態１では、等結合システムに含まれる複数の秘密計算装置の協調計算による秘密計算によって、q個の表T0,…,Tq-1から、各表に共通のキー属性値（例えばIDの値）を持つ行（レコード）を抜き出して、キー属性値ごとに同じ行になるように並べ替え、空レコードが追加された新しい表R（等結合された表）と空フラグを表す列ベクトルg→の秘匿文である[[R]]と[[g→]]を得る。但し、各表は属性値を要素とする行列として表示され、Tiはmi×ni行列(0≦i<q)、Rはm∩×n行列とする。ここで、m∩はm∩=min(m0,…,mq-1)、nはn=Σi=0q-1 niである。また、各表では、それぞれ、キー属性値に重複はないものとする。すなわち、Ti(0≦i<q)の１列目の値はすべて異なるものとする。なお、キー属性値を有限環ZNの要素として扱うことから、Nはレコード数の総和m=Σi=0q-1 miに対してm<Nとなるように決められているとする。
【００２４】
実施形態１では、上記非特許文献３と同様に、各表のレコードにタグを付与し、秘密計算によって、異なる表の間で同一のキー属性値を持つレコードのタグ同士を対応付け、後の処理でタグを公開してレコードの並べ替えを行うことによって等結合処理を実現する。ただし、等結合後の表の大きさを秘匿するために、秘匿された表[[T0]]に含まれるレコードに対応するレコードが[[Ti]]に含まれない場合にもタグの対応付けを行う必要がある。この問題を解決するために、表Tiに表T0と同じレコード数の表Si'を加えて拡張し、必ず対応付けができるようにする。
【００２５】
実施形態１の等結合アルゴリズムを以下に示す。
入力はq個の表T0,…,Tq-1の秘匿文[[T0]],…,[[Tq-1]]であり、特にT0をSと表記することにする。出力はT0,…,Tq-1を等結合して空レコードを加えた表Rの秘匿文[[R]]と、表Rの空フラグを表す列ベクトルg→の秘匿文[[g→]]である。
【００２６】
ステップＳ１
各整数i∈[1,q)について、レコード数が[[S]]のレコード数と同じで、[[S]]と[[Ti]]とに共通の属性を含む秘匿化された表[[Si']]を作成する。表[[Si']]は、[[S]]と[[Ti]]とに共通の属性については、その属性値として[[S]]の値をそのまま用い、[[S]]と[[Ti]]とに共通しない属性については、その属性値として任意の秘匿値を用いることによって、作られる。この結果、[[Si']]の属性の数は[[Ti]]の属性の数と等しくなる。[[Ti]]と[[Si']]を縦に並べて接続した表を[[Ti']]とする。
【００２７】
この処理を平文の状態で例示する。ここではq=3、表T0=Sの属性を１列目から順にキー属性、Ｘ、Ｙとし、表T1の属性を１列目から順にキー属性、Ｚ、Ｙとし、表T2の属性を１列目から順にキー属性、Ｗとして、具体的には、下記のとおりに与えられているとする。
【数３】
2014139640.tif 000006
【００２８】
[[S]]と[[T1]]とに共通の属性（キー属性とＹ）については、その属性値として[[S]]の値をそのまま用い、[[S]]と[[T1]]とに共通しない属性については、その属性値として任意の秘匿値を用いて、表[[S1']]が作成されるので、任意の秘匿値の平文を＊と表記すると、表S1'は下記のようになる。同様に、[[S]]と[[T2]]とに共通の属性（キー属性）については、その属性値として[[S]]の値をそのまま用い、[[S]]と[[T2]]とに共通しない属性については、その属性値として任意の秘匿値を用いて、表[[S2']]が作成されるので、任意の秘匿値の平文を＊と表記すると、表S2'は下記のようになる。よって、[[T1]]と[[S1']]を縦に並べて接続した表[[T1']]と、[[T2]]と[[S2']]を縦に並べて接続した表[[T2']]の、それぞれの平文T1'、T2'は下記のようになる。
【数４】
2014139640.tif 000007
【００２９】
ステップＳ２
[[S]],[[T1']],…,[[Tq-1']]に対してランダム置換済みの秘匿化されたベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]を作成する。具体的には、まず、表[[S]],[[T1']],…,[[Tq-1']]のそれぞれに対して対応する表の各レコードに対応する要素を持つ任意のベクトルt→S,t→T1',…,t→Tq-1'を定め、これらのベクトルt→S,t→T1',…,t→Tq-1'を秘匿化して[[t→S]],[[t→T1']],…,[[t→Tq-1']]を得て、次いで、[[t→S]],[[t→T1']],…,[[t→Tq-1']]をそれぞれランダム置換して、ランダム置換後のベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]を得る。これらベクトル[[t→S]],[[t→T1']],…,[[t→Tq-1']]をタグベクトルと呼称する。各タグベクトルは対応する表のレコード数と同じ要素数のベクトルの秘匿文である。各タグベクトルの平文の要素（タグ）は同じ値を含まない。また、第１実施形態では、各タグベクトルの平文の要素は、後に説明するステップＳ３(c)の処理で、j≠0のときに[[u→]][j]の平文が0にならないような値とする。ここで説明する例であれば、各タグベクトルの平文の要素はゼロを含まないようにすればよい。
【００３０】
上記の例に対応するタグベクトルの平文の例を下記に示す。
【数５】
2014139640.tif 000008
【００３１】
ステップＳ３
各整数i∈[1,q)について、以下を実行する。
（a） [[t→]]:=[[t→S]]||[[t→Ti']]、[[s→]]:=[[1]]m0||[[0]]mi+m0、[[s→']]:=[[0]]m0+mi||[[1]]m0、[[S]]と[[Ti']]のキー属性値を連結したベクトル[[k→]]を作成する。
（b） ([[t→]],[[s→]],[[s→']])を[[k→]]に従って安定ソートする。
（c） 以下のように定めた[[u→]]を作成する。
【数６】
2014139640.tif 000009
（d） [[u→]],[[t→]],[[s→']]を列方向に並べた([[u→]],[[t→]],[[s→']])をランダム置換する。
（e） [[u→]]を復元してu→を得る。
（f） u→[j]≠0を満たす各jについて、[[t→]][j]を復元して並べたベクトルt→i、u→[j]を並べたベクトルu→i、[[s→']][j]を並べたベクトル[[f→i]]を作成する。
【００３２】
上記の例に対応するステップＳ３の処理結果の平文の例を下記に示す。
i=1の場合は、(a)の終了段階では下記のベクトルが得られる。
【数７】
2014139640.tif 000010
【００３３】
i=1の場合は、(b)(c)の終了段階では下記のベクトルが得られる。
【数８】
2014139640.tif 000011
【００３４】
i=1の場合は、(f)の終了段階では下記のベクトルが得られる。なお、この例では簡単のため、(d)のランダム置換は無変換とした（ランダム置換の結果が偶然にも元の状態と同じになったと考える）。
【数９】
2014139640.tif 000012
【００３５】
同様に、i=2の場合は、(f)の終了段階では下記のベクトルが得られる。
【数１０】
2014139640.tif 000013
【００３６】
ステップＳ４
各([[S]],[[t→S]]),([[T1']],[[t→T1']]),…,([[Tq-1']],[[t→Tq-1']])をそれぞれランダム置換し、タグベクトル[[tS]],[[t→T1']],…,[[t→Tq-1']]を復元してタグベクトルの平文tS,t→T1',…,t→Tq-1'を得る。
【００３７】
ステップＳ５
[[R]]の第j行（1≦j≦m0）である[[R]][j]を、
[[R]][j]=[[S]][j]||[[T1']][wj,1]||…||[[Tq-1']][wj,q-1]
で計算することによって出力の表[[R]]を作成する。ただし、ここでの記号||は行ベクトルの列方向の連結を表す。また、wj,iは、t→i[hj,i]=t→Ti'[wj,i]を満たす値であり、hj,iは、t→S[j]=u→i[hj,i]を満たす値である。この処理の具体的な手順としては、最初にjを定め、次いで、t→S[j]=u→i[hj,i]を満たす値hj,iをステップＳ３(f)の処理で得られたu→iから探し出し、次いで、t→i[hj,i]=t→Ti'[wj,i]を満たす値wj,iをステップＳ３(f)の処理で得られたt→iとステップＳ４の処理で得られたt→Ti'とを用いて探し出し、[[Ti']][wj,i]を特定する。
また、[[g→]]の第j要素である[[g→]][j]を、
[[g→]][j]=[[f→1]][y1,j]∨…∨[[f→q-1]][yq-1,j]で計算することによって出力の空フラグ[[g→]]を作成する。ただし、yi,jは、t→S[j]=u→i[y1,j]を満たす値である。この処理の具体的な手順としては、最初にjを定め、次いで、t→S[j]=u→i[y1,j]を満たす値yi,jをステップＳ３(f)の処理で得られたu→iから探し出し、[[f→i]][yi,j]を特定する。
【００３８】
上記の例に対応する表[[R]]と空フラグ[[g→]]の平文の例を下記に示す。
【数１１】
2014139640.tif 000014
【００３９】
＜正当性＞
秘匿化された表[[S]]と[[Ti']]に対する処理の結果、Sのレコードの各タグに対して対応するTi'のレコードの異なるタグが計算され、さらにTiに含まれないTi'のレコードに限って対応するベクトルf→iの要素が１となっていることを確認する。
キー属性値はS、Ti、Si'の各表で重複がないため、キー属性値はどの値も高々３回しか現れず、さらに、ステップＳ３(b)での安定ソート後には、ソートの安定性から、ベクトルk→にて同じキー属性値はSのキー属性値、Tiのキー属性値、Si'のキー属性値の順で連続出現する。具体的には、Sに含まれるキー属性値aがTiに含まれる場合、キー属性値aはステップＳ３(b)での安定ソート後にはベクトルk→にてSのキー属性値a、Tiのキー属性値a、Si'のキー属性値aの順で連続出現し、Sに含まれるキー属性値aがTiに含まれない場合、キー属性値aはステップＳ３(b)での安定ソート後にはベクトルk→にてSのキー属性値a、Si'のキー属性値aの順で連続出現する。よって、安定ソート直後の列ベクトルk→においてSのキー属性値の一つ下のキー属性値に対応するタグベクトルt→iの要素（タグ）で指定されるレコードは、元々TiまたはSi'に含まれていたレコードである（復元されるu→iはSに含まれるレコードに対応する全てのタグを要素に持つタグベクトルであり、復元されるt→iはTi'に含まれるレコードに対応するタグの全部または一部を要素に持つベクトルであり、u→[j]≠0を満たす各jについて、u→i[j]とt→i[j]の対はSの各タグと対応するTi'の異なるタグの対になっている）。さらに、f→iの各要素の値はs→'の対応する要素の値と一致するため、Tiに含まれないTi'のレコードに限って対応するベクトルf→iの要素が１となる。
【００４０】
＜安全性＞
上記の等結合アルゴリズムが用いたプロトコルはすべてsemi-honestな攻撃者に対して安全である。従って、等結合アルゴリズムの安全性を確認するには、等結合アルゴリズム中で開示される値から情報が漏れていないことを確認すれば十分である。等結合アルゴリズム中で開示されるのは、ステップＳ３(e)のu→、ステップＳ３(f)のt→i、ステップＳ４のタグである。u→はu→iと0のみからなり、既述のように、u→i[j]とt→i[j]の対はSの各タグと対応するTi'の異なるタグの対になっている。タグの値は表のデータ（属性値）との相関性が無い。また、ステップＳ４で復元されるタグベクトルも、タグベクトルをランダム置換してから復元したものである。これらの値はタグの対応と順序を一様ランダムに決めたものと区別ができない。従って、等結合アルゴリズム中で開示される値から情報が漏れておらず、この等結合アルゴリズムはsemi-honestな攻撃者に対して安全である。
【００４１】
＜計算コスト＞
既述の秘密計算の場合を例にして計算コストの評価を行う。多くのデータベース処理では属性数がレコード数に比べて非常に小さい表を対象とするため、表の属性数すなわち行列の列数は定数とみなす。また、属性値を環ZNの要素として扱うため、環ZNはレコード数の総和mに対してm<Nとなるように決められているとする。参考文献３による比較プロトコルを単位とすると、秘匿化、復元、加算、減算、乗算の通信量は比較プロトコル換算で定数である。要素数nのランダム置換の通信量は比較プロトコル換算でＯ(n)、要素数nの安定ソートの通信量は比較プロトコル換算でＯ(n log n)である。従って、実施形態１の等結合アルゴリズムの通信量は比較プロトコル換算でＯ(m log m)である。
【００４２】
《実施形態２》
実施形態２では、大きさが秘匿された表が入力された場合にも対応できるように実施形態１を拡張する。入力の表の大きさを秘匿する方法は、前述の表の大きさを秘匿する方法と同じである。すなわち、入力の各表[[Ti]]は、行に空レコードを含み、列に属性として空フラグを含んでいるとする。実施形態１からの変更点は、入力の表が大きさの秘匿された表であることとステップＳ３の処理である（ステップＳ１、ステップＳ２、ステップＳ４、ステップＳ５の各処理は実施形態１と同じである）。
【００４３】
ステップＳ３は以下のように変更される。
ステップＳ３
各整数i∈[1,q)について、以下を実行する。
（a） [[t→]]:=[[t→S]]||[[t→Ti']]、[[s→]]:=[[1]]m0||[[0]]mi+m0、[[s→']]:=[[0]]m0+mi||[[1]]m0、[[t→']]:=[[*]]m0+mi||[[t→S]]、[[S]]と[[Ti']]のキー属性値を連結したベクトル[[k→]]、[[S]]と[[Ti]]と[[Si']]の空フラグを連結したベクトル[[z→]]を作成する。ただし、[[*]]は任意の秘匿文である。
（b） ([[t→]],[[s→]],[[s→']],[[z→]],[[t→']])を([[z→]],[[k→]])に従って安定ソートする。ただし、([[z→]],[[k→]])は、[[z→]][j]||[[k→]][j]をj番目の要素とする(m0+mi+m0)行1列の列ベクトルである。
（c） 以下のように定めた[[u→]]を作成する。
【数１２】
2014139640.tif 000015
（d） [[u→]],[[t→]],[[s→']]を列方向に並べた([[u→]],[[t→]],[[s→']])をランダム置換する。
（e） [[u→]]を復元してu→を得る。
（f） u→[j]≠0を満たす各jについて、[[t→]][j]を復元して並べたベクトルt→i、u→[j]を並べたベクトルu→i、[[s→']][j]∨[[z→]][j]を計算して並べたベクトル[[f→i]]を作成する。
【００４４】
実施形態２の処理の具体例を平文の状態で例示する。ここではq=2、表T0=Sの属性を１列目から順に空フラグ、キー属性、Ｘ、Ｙとし、表T1の属性を１列目から順に空フラグ、キー属性、Ｚ、Ｙとして、具体的には、下記のとおりに与えられているとする。
【数１３】
2014139640.tif 000016
【００４５】
このときステップＳ１の処理の終了段階では下記の情報が得られる。
【数１４】
2014139640.tif 000017
【００４６】
上記の例に対応するタグベクトルの平文の例を下記に示す。
【数１５】
2014139640.tif 000018
【００４７】
上記の例に対応するステップＳ３の処理結果の平文の例を下記に示す。
(a)の終了段階では下記のベクトルが得られる。
【数１６】
2014139640.tif 000019
【００４８】
(b)(c)の終了段階では下記のベクトルが得られる。
【数１７】
2014139640.tif 000020
【００４９】
(f)の終了段階では下記のベクトルが得られる。
【数１８】
2014139640.tif 000021
【００５０】
上記の例に対応する表[[R]]と空フラグ[[g→]]の平文の例を下記に示す。
【数１９】
2014139640.tif 000022
【００５１】
＜正当性、秘匿性＞
実施形態２の等結合アルゴリズムの正当性と秘匿性は実施形態１と同様に確認できる。
【００５２】
＜計算コスト＞
実施形態１からの変更点はステップＳ３の処理である。この変更によって、秘匿された値の個数が定数倍、[[u→]]の計算は定数倍、ソート対象データが定数倍、ランダム置換対象データが定数倍、それぞれ増加しており、[[f→i]]の計算には新たに入力の表のレコード数の総和に比例する論理和の計算が追加されている。従って、実施形態２の等結合アルゴリズムも実施形態１の等結合アルゴリズムと同様に、入力の表のレコード数の総和をmとすると通信量は比較プロトコル換算でＯ(m log m)である。
【００５３】
［等結合システム］
実施形態の等結合システムは、Ｐ個（Ｐは３以上の所定の整数）の秘密計算装置を含む。これらの各秘密計算装置は、例えば、インターネットなどの通信網あるいは同報通信路などを経由して、相互に通信可能とされている。
各秘密計算装置は、等結合アルゴリズムで必要とされる演算、つまり、少なくとも秘匿化、復元、加算、減算、乗算、ランダム置換、安定ソートを実行できるように構成されている。本発明において個々の演算を実現するための具体的な機能構成は、例えば上記非特許文献１、上記参考文献１、上記参考文献２のそれぞれで開示されるアルゴリズムを実行できるような構成で十分であり、これらは従来的構成であるから説明を省略する。
【００５４】
＜補記＞
等結合システムに含まれうるハードウェアエンティティ（秘密計算装置）は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい〕、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００５５】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【００５６】
ハードウェアエンティティでは、外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。
【００５７】
各実施形態で説明したハードウェアエンティティの細部においては、数論における数値計算処理が必要となる場合があるが、数論における数値計算処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成24年12月26日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈http://www.math.tu-berlin.de/~kant/kash.html〉［平成24年12月26日検索］を参照のこと）。
また、この点に関する文献として、参考文献Ａを挙げることができる。
（参考文献Ａ）H. Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag, 1993.
【００５８】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００５９】
また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００６０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2014139640.tif 000027