(57)【要約】【課題】従来よりも短い計算時間で集合演算を行うことができる秘密集合演算技術を提供する。【解決手段】2つの集合SとTについて、SとTの要素を上下に並べ、ソートを行った後に隣接する要素同士が一致するか否かの情報を利用することにより、直積の演算を用いずに集合演算をするための処理を構成する。これにより、計算途中で行数がO(m+n)の行列しか作る必要がないため、従来よりも計算時間を短くすることができる。具体的には、計算時間がO((m+n)log(m+n))である秘密計算上での集合演算を実現することができる。【選択図】図１
2014164145.tif 000002
【特許請求の範囲】
【請求項１】
aを秘匿化している情報を<a>として、
各集合は行列であり第一方向に配置されたダミーのレコードを含む少なくとも１つのレコードから構成されているとし、各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値及び上記各レコードがダミーであるかどうかを表す空フラグから構成されているとし、空フラグが1であれば上記各レコードはダミーを表し空フラグが0であれば上記各レコードはダミーではないことを表し、集合Sの行列を構成するレコード数をmとし、集合Tの行列を構成するレコード数をnとして、
秘密集合演算装置を構成する少なくとも１つの秘密計算装置が、協調計算によって、
集合Tの行列及び集合Sの行列を第一方向に結合した行列をUとして、<T>及び<S>に基づいて<U>を計算し、
Uを第一方向に安定ソートした行列をU1として、<U>に基づいて<U1>を計算し、
iを２以上n+m以下の各整数とし、1番目の要素の値を0とし、U1を構成する第一方向におけるi番目の第二方向のベクトルがU1を構成する第一方向におけるi-1番目の第二方向のベクトルと同じであればi番目の要素の値を1とし、U1を構成する第一方向におけるi番目の第二方向のベクトルがU1を構成する第一方向におけるi-1番目の第二方向のベクトルと異なれば第一方向におけるi番目の要素の値を0とするベクトルをeとして、<U1>に基づいて<e>を計算し、
行われる演算に応じてeの要素の値に変更を加えたベクトルをfとして、<e>に基づいて<f>を計算し、
iを1以上n+m以下の各整数とし、U1のi番目のレコードの空フラグの値とfのi番目の要素の値の少なくとも一方が1であればU1の中のその空フラグの値を1とする行列をVとして、<U1>及び<f>に基づいて<V>を計算する、
秘密集合演算装置。
【請求項２】
請求項１の秘密集合演算装置であって、
上記行われる演算は、集合Sのダミーではないレコードからなる集合と集合Tのダミーではないレコードからなる集合との和集合の演算であるとして、
fをeとして、<e>に基づいて<f>を計算する、
秘密集合演算装置。
【請求項３】
請求項１の秘密集合演算装置であって、
上記行われる演算は、集合Sのダミーではないレコードからなる集合と集合Tのダミーではないレコードからなる集合との差集合の演算であるとして、
1を第一方向にn個並べたベクトルを1nとし、0を第一方向にm個並べたベクトルを0mとし、1n及び0mを第一方向に結合させたベクトルをrとして、<r>を更に計算し、
Uをキーとしてrを安定ソートしたベクトルをr1として、<U>,<r>に基づいて<r1>を更に計算し、
eのi番目の要素の値とr1のi番目の要素の値の少なくとも一方が1であればi番目の要素の値を1とするベクトルをfとして、<e>,<r1>に基づいて<f>を更に計算し、
Vの空フラグをキーとしてVを安定ソートした行列においてm番目までの第二方向のベクトルを残した行列をV1として、<V>に基づいて<V1>を更に計算する、
秘密集合演算装置。
【請求項４】
請求項１の秘密集合演算装置であって、
上記行われる演算は、集合Sのダミーではないレコードからなる集合と集合Tのダミーではないレコードからなる集合との積集合の演算であるとして、
eのi番目の要素の値が0であればi番目の要素の値を1とし、eのi番目の要素の値が1であればi番目の要素の値を0とするベクトルをfとして、<e>に基づいて<f>を計算する、
秘密集合演算装置。
【請求項５】
aを秘匿化している情報を<a>として、
各集合は行列であり第一方向に配置されたダミーのレコードを含む少なくとも１つのレコードから構成されているとし、各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値及び上記各レコードがダミーであるかどうかを表す空フラグから構成されているとし、空フラグが1であれば上記各レコードはダミーを表し空フラグが0であれば上記各レコードはダミーではないことを表し、集合Sの行列を構成するレコード数をmとし、集合Tの行列を構成するレコード数をnとして、
秘密集合演算装置を構成する少なくとも１つの秘密計算装置が、協調計算によって、
集合Tの行列及び集合Sの行列を第一方向に結合した行列をUとして、<T>及び<S>に基づいて<U>を計算するステップと、
Uを第一方向に安定ソートした行列をU1として、<U>に基づいて<U1>を計算するステップと、
iを２以上n+m以下の各整数とし、1番目の要素の値を0とし、U1を構成する第一方向におけるi番目の第二方向のベクトルがU1を構成する第一方向におけるi-1番目の第二方向のベクトルと同じであればi番目の要素の値を1とし、U1を構成する第一方向におけるi番目の第二方向のベクトルがU1を構成する第一方向におけるi-1番目の第二方向のベクトルと異なれば第一方向におけるi番目の要素の値を0とするベクトルをeとして、<U1>に基づいて<e>を計算するステップと、
行われる演算に応じてeの要素の値に変更を加えたベクトルをfとして、<e>に基づいて<f>を計算するステップと、
iを1以上n+m以下の各整数とし、U1のi番目のレコードの空フラグの値とfのi番目の要素の値の少なくとも一方が1であればU1の中のその空フラグの値を1とする行列をVとして、<U1>及び<f>に基づいて<V>を計算するステップと、
を含む秘密集合演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号技術に関する。特に、秘密計算によって、情報を秘密にしたまま集合の演算を行う技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる技術が知られている（例えば、非特許文献１参照。）。非特許文献１に記載された技術では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、これらの３つの秘密計算装置が協調計算を行うことにより、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。
【０００３】
また、秘密計算上で入力と出力の集合の真の大きさを秘匿したまま集合演算を実現した方法として、非特許文献２の技術が知られている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, In CSS, 2010.
【非特許文献２】志村正法, 遠藤つかさ, 宮崎邦彦, 吉浦裕, “安全で機能制限のないデータベースを実現するマルチパーティプロトコルを用いた関係代数演算”, 情報処理学会研究報告. CSEC, Vol.2008, No.71, pp.187-193, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術は直積の演算を要するため、入力の２つの行列の行数をそれぞれm，nとすると計算時間がO(mn)と膨大である。
【０００６】
この発明の目的は、従来よりも短い計算時間で集合演算を実現する秘密集合演算装置及び方法を提供することである。
【課題を解決するための手段】
【０００７】
この発明の一態様による秘密集合演算装置は、aを秘匿化している情報を<a>として、各集合は行列であり第一方向に配置されたダミーのレコードを含む少なくとも１つのレコードから構成されているとし、各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値及び各レコードがダミーであるかどうかを表す空フラグから構成されているとし、空フラグが1であれば各レコードはダミーを表し空フラグが0であれば各レコードはダミーではないことを表し、集合Sの行列を構成するレコード数をmとし、集合Tの行列を構成するレコード数をnとして、秘密集合演算装置を構成する少なくとも１つの秘密計算装置が、協調計算によって、集合Tの行列及び集合Sの行列を第一方向に結合した行列をUとして、<T>及び<S>に基づいて<U>を計算し、Uを第一方向に安定ソートした行列をU1として、<U>に基づいて<U1>を計算し、iを２以上n+m以下の各整数とし、1番目の要素の値を0とし、U1を構成する第一方向におけるi番目の第二方向のベクトルがU1を構成する第一方向におけるi-1番目の第二方向のベクトルと同じであればi番目の要素の値を1とし、U1を構成する第一方向におけるi番目の第二方向のベクトルがU1を構成する第一方向におけるi-1番目の第二方向のベクトルと異なれば第一方向におけるi番目の要素の値を0とするベクトルをeとして、<U1>に基づいて<e>を計算し、行われる演算に応じてeの要素の値に変更を加えたベクトルをfとして、<e>に基づいて<f>を計算し、iを1以上n+m以下の各整数とし、U1のi番目のレコードの空フラグの値とfのi番目の要素の値の少なくとも一方が1であればU1の中のその空フラグの値を1とする行列をVとして、<U1>及び<f>に基づいて<V>を計算する。
【発明の効果】
【０００８】
従来よりも短い計算時間で集合演算を実現することができる。
【図面の簡単な説明】
【０００９】
【図１】秘密集合演算装置の例の機能ブロック図。
【図２】行列の例を説明するための図。
【発明を実施するための形態】
【００１０】
以下、この発明の実施形態について説明する。
【００１１】
［定義］
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が互いに異なる行ベクトルa,b,d,e,fから構成される行列であり、集合Yが行ベクトルa,c,dから構成される行列であるとする。
【００１６】
【数１】
2014164145.tif 000003
【００１７】
このとき、和集合X∪Y、差集合X＼Y、積集合X∩Yは、以下のようになる。
【００１８】
【数２】
2014164145.tif 000004
【００１９】
秘密集合演算装置は、図１に例示するように、Ｎを１以上の整数として、Ｎ個の秘密計算装置を備えている。Ｎ個の秘密計算装置は、協調計算により、秘匿化、復元、論理和、否定、安定ソート、等号判定の演算を行うことができる。
【００２０】
秘匿化の演算は、入力されたaに基づいて、aの秘匿文<a>を計算する処理である。復元の演算は、秘匿文<a>に基づいてaを計算する処理である。秘匿化及び復号の演算の詳細については、例えば非特許文献１を参照のこと。
【００２１】
論理和の演算は、Ｎ個の秘密計算装置による協調計算であり、a,bの秘匿文<a>,<b>を入力とし、それぞれa∨bの計算結果であるcの秘匿文<c>を計算する処理である。
【００２２】
否定の演算は、Ｎ個の秘密計算装置による協調計算であり、aの秘匿文<a>を入力とし、aの否定である¬aの計算結果であるcの秘匿文<c>を計算する処理である。
【００２３】
論理和、否定の演算の詳細については、例えば非特許文献１を参照のこと。
【００２４】
安定ソートの演算は、秘匿化されたベクトル又は行列の要素を第一方向に所定の順序で並び替える処理である。第一方向とは例えば行方向であり、所定の順序とは例えば辞書順である。この場合、行列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’は以下のようになる。
【００２７】
【数３】
2014164145.tif 000005
【００２８】
等号判定の演算は、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.
【００３０】
［上位概念の実施形態］
後述するように、大きさを秘匿した集合<S>及び大きさを秘匿した集合<T>について、第一実施形態は和集合の演算を行うものであり、第二実施形態は差集合の演算を行うものであり、第三実施形態は積集合の演算を行うものである。
【００３１】
まず、第一実施形態から第三実施形態に共通する部分についての実施形態である上位概念の実施形態について説明する。
【００３２】
入力及び出力の対象となる各集合は、図２に例示するように、行列で表されており、第一方向に配置されたダミーのレコードを含む少なくとも１つのレコードから構成されている。各レコードは少なくとも１つの属性にそれぞれ対応する第二方向に配置された少なくとも１つの属性値及びその各レコードがダミーであるかどうかを表す空フラグから構成されている。例えば、空フラグが1であればその各レコードはダミーを表し空フラグが0であればその各レコードはダミーではないことを表す。
【００３３】
以下、第一方向が行方向であり、第二方向が列方向である場合を例に挙げて説明する。
【００３４】
図２に例示した行列は、行方向に配置されたダミーのレコードを含む３個のレコードから構成されている。この例では、３行目のレコードがダミーである。各レコードは、４個の属性にそれぞれ対応する列方向に配置された属性値及び空フラグから構成されている。この例では、空フラグは第１列目に配置されている。この行列の属性は、ID、年齢、性別、職業である。このように、ダミーのレコードを含めることにより、集合の真の大きさを秘匿化することができる。
【００３５】
秘密集合演算装置は、図１に例示するように、Ｎを１以上の整数として、Ｎ個の秘密計算装置を備えている。
【００３６】
行列である集合Sを構成するレコード数をmとし、行列である集合Tを構成するレコード数をnとする。以下に、S,Tの例を挙げる。
【００３７】
【数４】
2014164145.tif 000006
【００３８】
＜ステップＳ１＞
Ｎ個の秘密計算装置は、協調計算により、<T>及び<S>に基づいて<U>を計算する（ステップＳ１）。
【００３９】
ここで、集合Tの行列及び集合Sの行列を第一方向（この例では行方向）に結合した行列をUとする。
【００４０】
Uは以下のようになる。
【００４１】
【数５】
2014164145.tif 000007
【００４２】
＜ステップＳ２＞
Ｎ個の秘密計算装置は、協調計算により、<U>に基づいて<U1>を計算する（ステップＳ２）。
【００４３】
ここで、Uを第一方向に安定ソートした行列をU1とする。
【００４４】
U1は以下のようになる。
【００４５】
【数６】
2014164145.tif 000008
【００４６】
＜ステップＳ３＞
Ｎ個の秘密計算装置は、協調計算により、<U1>に基づいて<e>を計算する（ステップＳ３）。
【００４７】
ここで、iを２以上n+m以下の各整数とし、1番目の要素の値を0とし、U1を構成する第一方向におけるi番目の第二方向のベクトルがU1を構成する第一方向におけるi-1番目の第二方向のベクトルと同じであればi番目の要素の値を1とし、U1を構成する第一方向におけるi番目の第二方向のベクトルがU1を構成する第一方向におけるi-1番目の第二方向のベクトルと異なれば第一方向におけるi番目の要素の値を0とするベクトルをeとする。この例では、第一方向は行方向であり、第二方向のベクトルは行ベクトルである。
【００４８】
eは、以下のようになる。
【００４９】
【数７】
2014164145.tif 000009
【００５０】
すなわち、Ｎ個の秘密計算装置は、協調計算により、以下の式により定義される<e>を計算する。ここで、iは1≦i≦m+nの各整数である。
【００５１】
【数８】
2014164145.tif 000010
【００５２】
＜ステップＳ４＞
Ｎ個の秘密計算装置は、協調計算により、<e>に基づいて<f>を計算する（ステップＳ４）。
【００５３】
ここで、行われる演算に応じてeの要素の値に変更を加えたベクトルをfとする。例えば、和集合の演算を行う場合には、eをそのままfとする。すなわち、iを1≦i≦m+nの各整数として、f[i]=e[i]とする。このステップＳ４におけるfの定義が、後述する各実施形態において異なる。
【００５４】
例えば、和集合の演算を行うためにf=eとした場合には、fは以下のようになる。
【００５５】
【数９】
2014164145.tif 000011
【００５６】
＜ステップＳ５＞
Ｎ個の秘密計算装置は、協調計算により、<U1>及び<f>に基づいて<V>を計算する（ステップＳ５）。
【００５７】
ここで、iを1以上n+m以下の各整数とし、U1のi番目のレコードの空フラグの値とfのi番目の要素の値の少なくとも一方が1であればU1の中のその空フラグの値を1とする行列をVとする。
【００５８】
ステップＳ４において例えば和集合の演算を行うためにf=eとした場合には、Vは以下のようになる。
【００５９】
【数１０】
2014164145.tif 000012
【００６０】
従来技術は直積の演算を要するため、入力の2つの行列の行数をそれぞれm,nとすると、計算途中で行数がmnの行列を作る必要があった。この発明は、直積の演算を用いずに構成されており計算途中で行数がO(m+n)の行列しか作る必要がないため、従来よりも計算時間が短い。具体的には、計算時間がO((m+n)log(m+n))である秘密計算上での集合演算を実現することができる。
【００６１】
また、空フラグにより、入力される行列、出力される行列の大きさ（行数）は秘匿化されている。
【００６２】
［第一実施形態］
第一実施形態の秘密集合演算装置は、大きさを秘匿した集合<S>及び大きさを秘匿した集合<T>について和集合の演算を行うものである。
【００６３】
第一実施形態では、ステップＳ４において、eをそのままfとする。すなわち、iを1≦i≦m+nの各整数として、f[i]=e[i]とする。
【００６４】
この部分のみが最上位概念の実施形態と異なり、他の部分は最上位概念の実施形態と同様であるため重複説明を省略する。
【００６５】
［第二実施形態］
第二実施形態の秘密集合演算装置は、大きさを秘匿した集合<S>及び大きさを秘匿した集合<T>について差集合の演算を行うものである。
【００６６】
以下、最上位概念の実施形態と異なる部分を中心に説明し、最上位概念の実施形態と同様の部分については重複説明を省略する。
【００６７】
＜ステップＳ１＞
Ｎ個の秘密計算装置は、協調計算により、<T>及び<S>に基づいて<U>を計算するのみならず、<r>を更に計算する（ステップＳ１）。
【００６８】
ここで、1を第一方向にn個並べたベクトルを1nとし、0を第一方向にm個並べたベクトルを0mとし、1n及び0mを第一方向に結合させたベクトルをrとする。
【００６９】
U,rは以下のようになる。
【００７０】
【数１１】
2014164145.tif 000013
【００７１】
＜ステップＳ２＞
Ｎ個の秘密計算装置は、協調計算により、<U>に基づいて<U1>を計算するのみならず、<U>,<r>に基づいて<r1>を更に計算する（ステップＳ２）。
【００７２】
ここで、Uをキーとしてrを安定ソートしたベクトルをr1とする。
【００７３】
【数１２】
2014164145.tif 000014
【００７４】
＜ステップＳ４＞
Ｎ個の秘密計算装置は、協調計算により、<U1>に基づいて<e>を計算するのみならず、<e>,<r1>に基づいて<f>を更に計算する（ステップＳ４）。
【００７５】
ここで、eのi番目の要素の値とr1のi番目の要素の値の少なくとも一方が1であればi番目の要素の値を1とするベクトルをfとする。
【００７６】
fは以下のようになる。
【００７７】
【数１３】
2014164145.tif 000015
【００７８】
この場合、ステップＳ５の後のVは以下のようになる。
【００７９】
【数１４】
2014164145.tif 000016
【００８０】
＜ステップＳ６＞
ステップ５の後に、Ｎ個の秘密計算装置は、協調計算により、<V>に基づいて<V1>を計算する（ステップＳ６）
ここで、Vの空フラグをキーとしてVを安定ソートした行列においてm番目までの第二方向のベクトルを残した行列をV1とする。
【００８１】
V1は以下のようになる。
【００８２】
【数１５】
2014164145.tif 000017
【００８３】
［第三実施形態］
第三実施形態の秘密集合演算装置は、大きさを秘匿した集合<S>及び大きさを秘匿した集合<T>について積集合の演算を行うものである。
【００８４】
第三実施形態では、ステップＳ４において、eのi番目の要素の値が0であればi番目の要素の値を1とし、eのi番目の要素の値が1であればi番目の要素の値を0とするベクトルをfとする。すなわち、iを1≦i≦m+nの各整数として、f[i]=¬e[i]とする。
【００８５】
この部分のみが最上位概念の実施形態と異なり、他の部分は最上位概念の実施形態と同様であるため重複説明を省略する。
【００８６】
第三実施形態では、fは、以下のようになる。
【００８７】
【数１６】
2014164145.tif 000018
【００８８】
また、ステップＳ５の後のVは以下のようになる。
【００８９】
【数１７】
2014164145.tif 000019
【００９０】
［変形例］
上記装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００９１】
また、秘密集合演算装置における各処理をコンピュータによって実現する場合、秘密集合演算装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、秘密集合演算装置における処理手段がコンピュータ上で実現される。
【００９２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９３】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００９４】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
2014164145.tif 000020
【図２】
2014164145.tif 000021