(57)【要約】【課題】従来よりも短い計算時間で表の除算を実現する秘密表除算技術を提供する。【解決手段】２つの表SとTについて、SとTを上下に並べた表を作り、Tの属性についてソートを行った後にSにしか含まれない属性について集計をすることにより、直積の演算を用いずに表の除算をするための処理を構成する。これにより、計算途中で行数がO(m+n)の表しか作る必要がないため、従来よりも計算時間を短くすることができる。具体的には、計算時間がO((m+n)log(m+n))である秘密計算上での表の除算を実現することができる。【選択図】図１
2014164144.tif 000002
【特許請求の範囲】
【請求項１】
aを秘匿化している情報を<a>とし、表Sを表Tで除算した表をR1をとして、<S>及び<T>に基づいて<R1>を秘密計算する秘密表除算装置であって、
各表は第一方向に配置された少なくとも１つのレコードから構成されているとし、各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値から構成されているとし、表Sを構成するレコード数をmとし、表Tを構成するレコード数をnとして、
上記秘密表除算装置は、少なくとも１つの秘密計算装置を含み、これら秘密計算装置の協調計算によって、
レコード数が表Tのレコード数と同じであり、表Sの属性と同じ属性を持ち、表Sと表Tに共通の属性についてはその共通の属性に対応する表Tの属性値を取り、表Sのみに存在する属性については任意の値を取る表をT’とし、表S及び表T’を第一方向に結合させた表をUとして、<S>及び<T>に基づいて<U>を計算し、
0を第一方向にm個並べたベクトルを0mとし、1を第一方向にn個並べたベクトルを1nとし、0m及び1nを第一方向に結合させたベクトルをtとして、<0m>及び<1n>に基づいて<t>を計算し、
表Uの中の表Tの属性に対応する属性値により構成される表をKとして、表KをキーとしてU,tを第一方向に安定ソートした表をそれぞれU1,t1として、<U>,<t>に基づいて<U1>及び<t1>を計算し、
表U1の中の表Tの属性に対応する属性値により構成される表をVとして、<U1>に基づいて<V>を計算し、
表Vを構成する第二方向ベクトルの中に、対応する、ベクトルt1の要素が1であるものがあれば、その対応する要素が1である第二方向ベクトルと同じ要素で構成される全ての第二方向ベクトルに対応する、ベクトルt1の要素を1にする処理を行ったベクトルをgとして、<V>及び<t1>に基づいて<g>を計算し、
πrを所定のランダム置換として、U1,t1,gをπrで置換したものをU2,t2,g1として、<U1>,<t1>,<g>に基づいて<U2>,<t2>,<g1>を計算し、
ベクトルt2の中の値が１である要素に対応する、U2,g1の第二方向ベクトルを削除したものをU3,g2として、<U2>,<t2>,<g1>に基づいて<U3>,<g2>を計算し、
表Sに存在するが表Tに存在しない属性の属性値を表U3から取り出した表をRとして、<U3>,<S>,<T>,に基づいて<R>を計算し、
Rをキーとしてg2について集約関数総和を行った結果をcとして、<R>に基づいて<c>を計算し、
cの中の値がnでない要素に対応する要素の値を1とし、cの中の値がnである要素に対応する要素の値を0とするベクトルをeとして、<c>に基づいて<e>を計算し、
e及びRを第二方向に結合させた表をR1として、<e>及び<R>に基づいて<R1>を計算する、
秘密表除算装置。
【請求項２】
aを秘匿化している情報を<a>とし、表Sを表Tで除算した表をR1をとして、<S>及び<T>に基づいて<R1>を秘密計算する秘密表除算方法であって、
各表は第一方向に配置された少なくとも１つのレコードから構成されているとし、各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値から構成されているとし、表Sを構成するレコード数をmとし、表Tを構成するレコード数をnとして、
少なくとも１つの秘密計算装置が、協調計算によって、
レコード数が表Tのレコード数と同じであり、表Sの属性と同じ属性を持ち、表Sと表Tに共通の属性についてはその共通の属性に対応する表Tの属性値を取り、表Sのみに存在する属性については任意の値を取る表をT’とし、表S及び表T’を第一方向に結合させた表をUとして、<S>及び<T>に基づいて<U>を計算するステップと、
0を第一方向にm個並べたベクトルを0mとし、1を第一方向にn個並べたベクトルを1nとし、0m及び1nを第一方向に結合させたベクトルをtとして、<0m>及び<1n>に基づいて<t>を計算するステップと、
表Uの中の表Tの属性に対応する属性値により構成される表をKとして、表KをキーとしてU,tを第一方向に安定ソートした表をそれぞれU1,t1として、<U>,<t>に基づいて<U1>及び<t1>を計算するステップと、
表U1の中の表Tの属性に対応する属性値により構成される表をVとして、<U1>に基づいて<V>を計算するステップと、
表Vを構成する第二方向ベクトルの中に、対応する、ベクトルt1の要素が1であるものがあれば、その対応する要素が1である第二方向ベクトルと同じ要素で構成される全ての第二方向ベクトルに対応する、ベクトルt1の要素を1にする処理を行ったベクトルをgとして、<V>及び<t1>に基づいて<g>を計算するステップと、
πrを所定のランダム置換として、U1,t1,gをπrで置換したものをU2,t2,g1として、<U1>,<t1>,<g>に基づいて<U2>,<t2>,<g1>を計算するステップと、
ベクトルt2の中の値が１である要素に対応する、U2,g1の第二方向ベクトルを削除したものをU3,g2として、<U2>,<t2>,<g1>に基づいて<U3>,<g2>を計算するステップと、
表Sに存在するが表Tに存在しない属性の属性値を表U3から取り出した表をRとして、<U3>,<S>,<T>,に基づいて<R>を計算するステップと、
Rをキーとしてg2について集約関数総和を行った結果をcとして、<R>に基づいて<c>を計算するステップと、
cの中の値がnでない要素に対応する要素の値を1とし、cの中の値がnである要素に対応する要素の値を0とするベクトルをeとして、<c>に基づいて<e>を計算するステップと、
e及びRを第二方向に結合させた表をR1として、<e>及び<R>に基づいて<R1>を計算するステップと、
を含む秘密表除算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号技術に関する。特に、秘密計算によって、表に含まれる情報を秘密にしたまま演算を行う技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる技術が知られている（例えば、非特許文献１参照。）。非特許文献１に記載された技術では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、これらの３つの秘密計算装置が協調計算を行うことにより、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。
【０００３】
また、秘密計算上で表の除算を実現した方法として、非特許文献２の技術が知られている。非特許文献２の技術では、表の除算を直積と差の演算の組み合わせにより実現している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, In CSS, 2010.
【非特許文献２】志村正法, 遠藤つかさ, 宮崎邦彦, 吉浦裕, “安全で機能制限のないデータベースを実現するマルチパーティプロトコルを用いた関係代数演算”, 情報処理学会研究報告. CSEC, Vol.2008, No.71, pp.187-193, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術は直積の演算を要するため、入力の２つの表の行数をそれぞれm，nとすると計算時間がO(m2n)と膨大である。
【０００６】
この発明の目的は、従来よりも短い計算時間で表の除算を実現する秘密表除算装置及び方法を提供することである。
【課題を解決するための手段】
【０００７】
この発明の一態様による秘密表除算装置は、aを秘匿化している情報を<a>とし、表Sを表Tで除算した表をR1をとして、<S>及び<T>に基づいて<R1>を秘密計算する秘密表除算装置であって、各表は第一方向に配置された少なくとも１つのレコードから構成されているとし、各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値から構成されているとし、表Sを構成するレコード数をmとし、表Tを構成するレコード数をnとして、上記秘密表除算装置は、少なくとも１つの秘密計算装置を含み、これら秘密計算装置の協調計算によって、レコード数が表Tのレコード数と同じであり、表Sの属性と同じ属性を持ち、表Sと表Tに共通の属性についてはその共通の属性に対応する表Tの属性値を取り、表Sのみに存在する属性については任意の値を取る表をT’とし、表S及び表T’を第一方向に結合させた表をUとして、<S>及び<T>に基づいて<U>を計算し、0を第一方向にm個並べたベクトルを0mとし、1を第一方向にn個並べたベクトルを1nとし、0m及び1nを第一方向に結合させたベクトルをtとして、<0m>及び<1n>に基づいて<t>を計算し、表Uの中の表Tの属性に対応する属性値により構成される表をKとして、表KをキーとしてU,tを第一方向に安定ソートした表をそれぞれU1,t1として、<U>,<t>に基づいて<U1>及び<t1>を計算し、表U1の中の表Tの属性に対応する属性値により構成される表をVとして、<U1>に基づいて<V>を計算し、表Vを構成する第二方向ベクトルの中に、対応する、ベクトルt1の要素が1であるものがあれば、その対応する要素が1である第二方向ベクトルと同じ要素で構成される全ての第二方向ベクトルに対応する、ベクトルt1の要素を1にする処理を行ったベクトルをgとして、<V>及び<t1>に基づいて<g>を計算し、πrを所定のランダム置換として、U1,t1,gをπrで置換したものをU2,t2,g1として、<U1>,<t1>,<g>に基づいて<U2>,<t2>,<g1>を計算し、ベクトルt2の中の値が１である要素に対応する、U2,g1の第二方向ベクトルを削除したものをU3,g2として、<U2>,<t2>,<g1>に基づいて<U3>,<g2>を計算し、表Sに存在するが表Tに存在しない属性の属性値を表U3から取り出した表をRとして、<U3>,<S>,<T>,に基づいて<R>を計算し、Rをキーとしてg2について集約関数総和を行った結果をcとして、<R>に基づいて<c>を計算し、cの中の値がnでない要素に対応する要素の値を1とし、cの中の値がnである要素に対応する要素の値を0とするベクトルをeとして、<c>に基づいて<e>を計算し、e及びRを第二方向に結合させた表をR1として、<e>及び<R>に基づいて<R1>を計算する。
【発明の効果】
【０００８】
従来よりも短い計算時間で表の除算を実現することができる。
【図面の簡単な説明】
【０００９】
【図１】秘密表除算装置の例の機能ブロック図。
【図２】表の例を説明するための図。
【図３】表の例を説明するための図。
【発明を実施するための形態】
【００１０】
以下、この発明の実施形態について説明する。
【００１１】
［定義］
aを暗号化や秘密分散などにより秘匿化している情報を<a>と表現する。<a>のことをaの秘匿文と呼ぶこともある。aは、スカラー値、ベクトル、行列である。aがベクトルである場合には、<a>はベクトルの各要素を秘匿化した情報である。aが行列である場合には、<a>は行列の各要素を秘匿化した情報である。<a>を復元するための情報は複数の断片に分割されており、複数の断片は協調計算を行う少なくとも１つの秘密計算装置により保有されているものとする。
【００１２】
aがベクトルである場合には、<a>[i]はベクトルaのi番目の要素を意味する。aが行列である場合には、<a>[i]は行列aのi番目の第二方向のベクトルを意味する。i番目の第二方向のベクトルとは、後述するように第一方向が行方向であり第二方向が列方向である場合には、i番目の行ベクトルのことである。
【００１３】
ベクトルxとyの所定の方向での連結をx||yとする。aがスカラー値である場合には秘匿文<a>を所定の方向にn個並べたベクトルを<a>nと表現する。
【００１４】
除算は２つの表による演算である。表Xに対する表Yの除算の結果を表Zとする。
【００１５】
ここでは、各表は、第一方向に配置された少なくとも１つのレコードから構成されている。各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値から構成されている。このように、各表は行列である。表を構成するレコードの各属性値に対応する属性を、その表の属性と表現する。
【００１６】
第一方向が行方向である場合には、第二方向は列方向である。一方、第一方向が列方向である場合には、第二方向は行方向である。以下、第一方向が行方向であり、第二方向が列方向である場合を例に挙げて説明する。
【００１７】
図２に例示した表は、行方向に配置された３個のレコードから構成されている。各レコードは、４個の属性にそれぞれ対応する列方向に配置された属性値から構成されている。この表の属性は、ID、年齢、性別、職業である。
【００１８】
表Xに対する表Yによる除算は、表Xの属性の集合αと表Yの属性の集合βとがβ⊂αという関係を満たす場合に定義される。例えば、表Xの属性の集合α={a1,a2,a3,a4}であり、表Yの属性の集合β={a3,a4}である場合には、β⊂αの関係を満たすため表Xに対する表Yによる除算が定義される。＼を差集合の演算を表現するとして、表Xに対する表Yの除算の結果である表Zの属性はγ=α＼βである。この例では、γ=α＼β={a1,a2,a3,a4}＼{a3,a4}={a1,a2}である。
【００１９】
表Xに対する表Yの除算の結果である表Zは、以下のように定義される。
Z=πγ(X)-πγ((πγ(X)×Y)-X)
【００２０】
ここで、πγ(X)は、表Xの中から属性γの属性値を抜き出した表πγ(X)’において、重複する第二方向ベクトル（行ベクトル）を除いた表である。例えば、属性が(a1,a2,a3,a4)である表X及び属性が(a3,a4)である表Yが以下のように与えられた場合、属性が(a1,a2)であるπγ(X)’,πγ(X),(πγ(X)×Y),(πγ(X)×Y)-X,πγ((πγ(X)×Y)-X),Zは以下のようになる。
【００２１】
【数１】
2014164144.tif 000003
【００２２】
秘密表除算装置は、図１に例示するように、Ｎを１以上の整数として、Ｎ個の秘密計算装置を備えている。Ｎ個の秘密計算装置は、協調計算により、秘匿化、復元、加算、減算、乗算、否定、ランダム置換、安定ソート、等号判定、集約関数総和の演算を行うことができる。
【００２３】
秘匿化の演算は、入力されたaに基づいて、aの秘匿文<a>を計算する処理である。復元の演算は、秘匿文<a>に基づいてaを計算する処理である。秘匿化及び復号の演算の詳細については、例えば非特許文献１を参照のこと。
【００２４】
加算、減算、乗算の各演算は、Ｎ個の秘密計算装置による協調計算であり、a,bの秘匿文<a>,<b>を入力とし、それぞれa+b，a-b，abの計算結果であるcの秘匿文<c>を計算する処理である。加算、減算、乗算の演算の詳細については、例えば非特許文献１を参照のこと。
【００２５】
否定の演算は、Ｎ個の秘密計算装置による協調計算であり、aの秘匿文<a>を入力とし、aの否定である¬aの計算結果であるcの秘匿文<c>を計算する処理である。否定の演算の詳細については、例えば非特許文献１を参照のこと。
【００２６】
ランダム置換の演算は、ランダム置換は協調計算により複数の秘匿化されたベクトルに対して同一のランダム置換πrを施す処理である。すなわち、Lを１以上の整数として、L個の大きさnのベクトルa(1),…,a(L)の秘匿文<a(1)>,…,<a(L)>を入力とし、あるランダムな全単射πr:{1,…,n}→{1,…,n}についてbπr(j)(i)=aj(i)(1≦i≦L,1≦j≦n)を満たすL個の大きさnのベクトルb(1),…,b(L)の秘匿文<b(1)>,…,<b(L)>を、Ｎ個の秘密計算装置はどの秘密計算装置もランダム置換πrを知ることなく協調計算する。ランダム置換の演算の詳細については、例えば参考文献１を参照のこと。
【００２７】
〔参考文献１〕Sven Laur, Jan Willemson, Bingsheng Zhang, “Round-efficient oblivious database manipulation”, In Xuejia Lai, Jianying Zhou, Hui Li, editors, ISC, Vol. 7001 of LNCS, pp.262-277, Springer, 2011.
【００２８】
安定ソートの演算は、秘匿化されたベクトル又は行列の要素を第一方向に所定の順序で並び替える処理である。第一方向とは例えば行方向であり、所定の順序とは例えば辞書順である。この場合、行列Xの安定ソートとは、行列Xを構成するn個の行ベクトルX[1],…,X[n]を辞書順に並び替えることを意味する。なお、辞書順とは、ある行ベクトルx=(x1,…,xm)とある行ベクトルy=(y1,…,ym)との順序を定める際、x<y iff (x1<y1)∨((x1=y1)∧((x2<y2)∨(…)))という基準に基づいてxとyとの順序を定めるものである。iffは、if and only ifの意味である。なお、安定ソートの際、ある行ベクトルとある行ベクトルが同じであり、これらの行ベクトルに辞書順の順序を定めることができない場合には、元の行列Xにおけるこれらの行ベクトルの順序に基づいてこれらの行ベクトルの順序が定まるとする。また、この場合、行列Xをキーとした、ベクトル又は行列であるYの行方向の安定ソートの演算とは、X,Yの行数をnとして、行列Xの行方向の安定ソートに対応する全単射の所定の置換πs:{1,…,n}→{1,…,n}に基づいて、Yを構成する行ベクトルを置換する処理を意味する。安定ソートの演算の詳細については、例えば参考文献２を参照のこと。
【００２９】
〔参考文献２〕濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “秘匿関数計算上の線形時間ソート”, In SCIS, pp.1-7, 2011.
【００３０】
例えば、行列X,Yが以下のように与えられた場合、安定ソート後の行列X’、行列Xをキーとした安定ソート後のY’は以下のようになる。
【００３１】
【数２】
2014164144.tif 000004
【００３２】
等号判定の演算は、a,bの秘匿文<a>,<b>を入力とし、a=bの真偽値cの秘匿文<c>を計算する処理である。真偽値は真のとき1、偽のとき0とする。この演算の実行を(<a>=?<b>)と表現する。等号判定の演算の詳細については、例えば参考文献３を参照のこと。
【００３３】
〔参考文献３〕Takashi Nishide, Kazuo Ohta, “Multiparty computation for interval, equality, and comparison without bitdecomposition protocol”, In PKC, pp.343-360, 2007.
【００３４】
集約関数総和の演算は、行列Xの秘匿文<X>及びベクトルaの秘匿文<a>を入力とし、Xの互いに異なる行ベクトルごとに対応するaの要素の値の総和を計算する演算である。ただし、X,aの行数はnであるとする。この演算を、<X>をキーとする<a>についての集約関数総和の演算とも表現する。出力は、Xを構成する行ベクトルを全単射の所定の置換πg:{1,…,n}→{1,…,n}で置換することにより並べ替えた行列X’の秘匿文<X’>、及び、同じ置換πgでベクトルaの要素を置換することにより並び替えた行列a’の秘匿文<a’>である。X’の互いに異なる行ベクトルxごとに、<X’>[i]=xを満たす１つのiについてa’[i]=Σj∈C(x)a[j]とし、それ以外のa’[i]については0である。ただし、C(x)={j|X[j]=x}である。集約関数総和の演算の詳細については、例えば参考文献４を参照のこと。
【００３５】
〔参考文献４〕五十嵐大, 千田浩司, 濱田浩気, 高橋克巳, “軽量検証可能3 パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理”, In SCIS, pp.1-8, 2011.
【００３６】
例えば、行列X及びベクトルaが以下のように与えられた場合、集約関数総和演算後の行列X’及びベクトルa’は以下のようになる。
【００３７】
【数３】
2014164144.tif 000005
【００３８】
［第一実施形態］
秘密表除算装置は、図１に例示するように、Ｎを１以上の整数として、Ｎ個の秘密計算装置を備えている。表Sに対する表Tの除算の結果を表R1として、Ｎ個の秘密計算装置は、協調計算により、<S>及び<T>に基づいて<R1>を計算する。
【００３９】
第一実施形態の秘密表除算装置は、秘匿文<R>として出力されるRのレコード数を秘匿化する。
【００４０】
表Sを構成するレコード数をmとし、表Tを構成するレコード数をnとする。以下に、表S,Tの例を挙げる。表Sの属性は(a1,a2,a3,a4)であり、表Tの属性は(a3,a4)であるとする。
【００４１】
【数４】
2014164144.tif 000006
【００４２】
＜ステップＳ１＞
Ｎ個の秘密計算装置は、協調計算により、<S>及び<T>に基づいて<U>を計算する（ステップＳ１）。
【００４３】
ここで、レコード数が表Tのレコード数と同じであり、表Sの属性と同じ属性を持ち、表Sと表Tに共通の属性についてはその共通の属性に対応する表Tの属性値を取り、表Sのみに存在する属性については任意の値*を取る表をT’とし、表S及び表T’を第一方向（この例では行方向）に結合させた表をUとする。
【００４４】
表T’,Uは以下のようになる。
【００４５】
【数５】
2014164144.tif 000007
【００４６】
＜ステップＳ２＞
Ｎ個の秘密計算装置は、協調計算により、<0m>及び<1n>に基づいて<t>を計算する（ステップＳ２）。
【００４７】
ここで、0を第一方向にm個並べたベクトルを0mとし、1を第一方向（この例では行方向）にn個並べたベクトルを1nとし、0m及び1nを第一方向（この例では行方向）に結合させたベクトルをtとする。
【００４８】
すなわち、Ｎ個の秘密計算装置は、協調計算により、<t>=<0>m||<1>nを計算する。
【００４９】
tは以下のようになる。
【００５０】
【数６】
2014164144.tif 000008
【００５１】
＜ステップＳ３＞
Ｎ個の秘密計算装置は、協調計算により、<U>,<t>に基づいて<U1>及び<t1>を計算する（ステップＳ３）。
【００５２】
ここで、表Uの中の表Tの属性に対応する属性値により構成される表をKとして、表KをキーとしてU,tを第一方向（この例では行方向）に安定ソートした表をそれぞれU1,t1とする。
【００５３】
表k,U1,t1は、以下のようになる。
【００５４】
【数７】
2014164144.tif 000009
【００５５】
＜ステップＳ４＞
Ｎ個の秘密計算装置は、協調計算により、<U1>に基づいて<V>を計算する（ステップＳ４）。
【００５６】
ここで、表U1の中の表Tの属性に対応する属性値により構成される表をVとする。
【００５７】
Vは以下のようになる。
【００５８】
【数８】
2014164144.tif 000010
【００５９】
＜ステップＳ５＞
Ｎ個の秘密計算装置は、協調計算により、<V>及び<t1>に基づいて<g>を計算する（ステップＳ５）。
【００６０】
ここで、表Vを構成する第二方向ベクトル（この例では行ベクトル）の中に、対応する、ベクトルt1の要素が1であるものがあれば、その対応する要素が1である第二方向ベクトル（この例では行方向）と同じ要素で構成される全ての第二方向ベクトル（この例では行方向）に対応する、ベクトルt1の要素を1にする処理を行ったベクトルをgとする。
【００６１】
ベクトルgは以下のようになる。
【００６２】
【数９】
2014164144.tif 000011
【００６３】
Ｎ個の秘密計算装置は、協調計算により、例えば以下の処理を行うことにより<g>を計算する。
【００６４】
まず、<f>=<t1>とする。すなわち、f=t1として、<t1>に基づいて<f>を計算する。また、d=1とする。そして、d<nの間、以下の(a)から(c)の処理を繰り返し行う。
【００６５】
(a) 各i∈[1,m+n]について、以下の式により定義される<p>を計算する。
【００６６】
【数１０】
2014164144.tif 000012
【００６７】
すなわち、i+d≦nであればf[i+d]*(V[i]=?V[i+d])をp[i]とし、i+d≦nでなければ0をp[i]として、このように定義されるp[i]に基づいて定まるpを秘匿化した<p>を<f>,<V>に基づいて計算する。
【００６８】
(b) [f]=[f]+[p]とする。つまり、[f],[p]に基づいて、f=f+pのように定義される[f]を計算する。
【００６９】
(c) d=2dとする。
【００７０】
＜ステップＳ６＞
Ｎ個の秘密計算装置は、協調計算により、<U1>,<t1>,<g>に基づいて<U2>,<t2>,<g1>を計算する（ステップＳ６）。
【００７１】
ここで、πrを所定のランダム置換として、U1,t1,gをπrで置換したものをU2,t2,g1とする。
【００７２】
U2,t2,g1は例えば以下のようになる。
【００７３】
【数１１】
2014164144.tif 000013
【００７４】
＜ステップＳ７＞
Ｎ個の秘密計算装置は、協調計算により、<U2>,<t2>,<g1>に基づいて<U3>,<g2>を計算する（ステップＳ７）。
【００７５】
ここで、ベクトルt2の中の値が１である要素に対応する、U2,g1の第二方向ベクトル（この例では行ベクトル）を削除したものをU3,g2とする。
【００７６】
U3,g2は以下のようになる。
【００７７】
【数１２】
2014164144.tif 000014
【００７８】
＜ステップＳ８＞
Ｎ個の秘密計算装置は、協調計算により、<U3>,<S>,<T>,に基づいて<R>を計算する（ステップＳ８）。
【００７９】
ここで、表Sに存在するが表Tに存在しない属性の属性値を表U3から取り出した表をRとする。
【００８０】
Rは以下のようになる。
【００８１】
【数１３】
2014164144.tif 000015
【００８２】
＜ステップＳ９＞
Ｎ個の秘密計算装置は、協調計算により、<R>に基づいて<c>を計算する（ステップＳ９）。
【００８３】
ここで、Rをキーとしてg2について集約関数総和を行った結果をcとする。
【００８４】
cは以下のようになる。
【００８５】
【数１４】
2014164144.tif 000016
【００８６】
＜ステップＳ１０＞
Ｎ個の秘密計算装置は、協調計算により、<c>に基づいて<e>を計算する（ステップＳ１０）。
【００８７】
ここで、cの中の値がnでない要素に対応する要素の値を1とし、cの中の値がnである要素に対応する要素の値を0とするベクトルをeとする。
【００８８】
eは以下のようになる。
【００８９】
【数１５】
2014164144.tif 000017
【００９０】
＜ステップＳ１１＞
Ｎ個の秘密計算装置は、協調計算により、<e>及び<R>に基づいて<R1>を計算する（ステップＳ１１）。
【００９１】
ここで、e及びRを第二方向（この例では列方向）に結合させた表をR1とする。
【００９２】
R1は以下のようになる。
【００９３】
【数１６】
2014164144.tif 000018
【００９４】
R1の３列目が0の行の要素うち属性がa1,a2である要素を抜き出した行列R2は、表Sに対する表Tの除算の結果となる。このように、e[i]が1であればその行は空ベクトルであり、e[i]が0であればその行は空ベクトルではない。
【００９５】
【数１７】
2014164144.tif 000019
【００９６】
したがって、R1は表の大きさ（行数）を隠しつつ表Sに対する表Tの除算の結果を表している。
【００９７】
従来技術は直積の演算を要するため、入力の2つの表の行数をそれぞれm,nとすると、計算途中で行数がmnの表を作る必要があった。この発明は、直積の演算を用いずに構成されており計算途中で行数がO(m+n)の表しか作る必要がないため、従来よりも計算時間が短い。具体的には、計算時間がO((m+n)log(m+n))である秘密計算上での表の除算を実現することができる。
【００９８】
［第二実施形態］
秘密表除算装置は、第一実施形態を、入力される表S,Tが秘匿化された表である場合に拡張したものである。
【００９９】
以下、第一実施形態と異なる部分を中心に説明し、第一実施形態と同様の部分については重複説明を省略する。
【０１００】
表S,Tは、図３に例示するように、第一方向に配置されたダミーのレコードを含む少なくとも１つのレコードから構成されている。各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値及びその各レコードがダミーであるかどうかを表す空フラグから構成されている。例えば、空フラグが1であればその各レコードはダミーを表し空フラグが0であればその各レコードはダミーではないことを表す。
【０１０１】
以下、第一方向が行方向であり、第二方向が列方向である場合を例に挙げて説明する。
【０１０２】
図３に例示した表は、行方向に配置されたダミーのレコードを含む３個のレコードから構成されている。この例では、３行目のレコードがダミーである。各レコードは、４個の属性にそれぞれ対応する列方向に配置された属性値及び空フラグから構成されている。この例では、空フラグは第１列目に配置されている。この表の属性は、ID、年齢、性別、職業である。このように、表にダミーのレコードを含めることにより、表の真の大きさを秘匿化することができる。
【０１０３】
このダミーのレコードの追加は、秘密表除算装置により事前に行われる。
【０１０４】
ダミーのレコードを追加した表S,Tの例を以下に挙げる。この例では、空フラグは第１列目に配置されている。
【０１０５】
【数１８】
2014164144.tif 000020
【０１０６】
ステップＳ５以外のステップの処理は、第一実施形態と同様である。
【０１０７】
第二実施形態のステップＳ５では、<f>=<t1>とする代わりに、<f>=<t1>*(¬<L>)とする。すなわち、f=t1*(¬L)として、<t1>,<L>に基づいて<f>を計算する。そして、また、d=1とする。そして、d<nの間、上述の(a)から(c)の処理を繰り返し行う。
【０１０８】
ここで、LはU1の空フラグを表す第一方向ベクトル（この例では列ベクトル）である。
【０１０９】
この場合、ステップＳ２の後に、U,t1は以下のようになる。
【０１１０】
【数１９】
2014164144.tif 000021
【０１１１】
ステップＳ５の後に、U1,V,t1,gは以下のようになる。
【０１１２】
【数２０】
2014164144.tif 000022
【０１１３】
また、ステップＳ７の後にU3,g2は以下のようになる。
【０１１４】
【数２１】
2014164144.tif 000023
【０１１５】
ステップＳ１０の後にR,c,eは以下のようになる。
【０１１６】
【数２２】
2014164144.tif 000024
【０１１７】
［変形例］
上記装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１１８】
また、秘密表除算装置における各処理をコンピュータによって実現する場合、秘密表除算装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、秘密表除算装置における処理手段がコンピュータ上で実現される。
【０１１９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２０】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１２１】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
2014164144.tif 000025
【図２】
2014164144.tif 000026
【図３】
2014164144.tif 000027