(57)【要約】【課題】複数の当事者が秘匿データを他の当事者と共有することなく、クラスタリングするための分類装置、分類方法及び分類プログラムを提供すること。【解決手段】サーバＳは、複数の端末Ｐから、完全準同型の暗号方式により公開鍵で暗号化された複数のデータを受信する第１受信部１１と、データ間のユークリッド距離と所定の距離との大小関係を求める演算を、暗号化された状態で行う演算部１２と、演算の結果を複数のパーティに送信する第１送信部１３と、演算の結果を各パーティの秘密鍵を用いたマルチパーティ計算により復号した値により得られた大小関係の判定値を受信する第２受信部１４と、判定値に基づいて、複数のデータを分類したクラスタを生成するクラスタリング部１５と、クラスタの情報を公開鍵により暗号化し、複数のパーティに送信する第２送信部１６と、を備える。【選択図】図２
2018124513.tif 000002
【特許請求の範囲】
【請求項１】
複数のパーティから、完全準同型の暗号方式により公開鍵で暗号化された複数のデータを受信する第１受信部と、
前記データ間のユークリッド距離と所定の距離との大小関係を求める演算を、暗号化された状態で行う演算部と、
前記演算の結果を前記複数のパーティに送信する第１送信部と、
前記演算の結果を各パーティの秘密鍵を用いたマルチパーティ計算により復号した値により得られた前記大小関係の判定値を受信する第２受信部と、
前記判定値に基づいて、前記複数のデータを分類したクラスタを生成するクラスタリング部と、
前記クラスタの情報を前記公開鍵により暗号化し、前記複数のパーティに送信する第２送信部と、を備える分類装置。
【請求項２】
前記演算部は、前記ユークリッド距離の２乗と、前記所定の距離の２乗と、の差分値の暗号データを算出し、
前記第２受信部は、前記差分値に基づく前記大小関係の判定値を受信する請求項１に記載の分類装置。
【請求項３】
複数のパーティから、完全準同型の暗号方式により公開鍵で暗号化された複数のデータを受信する第１受信ステップと、
前記データ間のユークリッド距離と所定の距離との大小関係を求める演算を、暗号化された状態で行う演算ステップと、
前記演算の結果を前記複数のパーティに送信する第１送信ステップと、
前記演算の結果を各パーティの秘密鍵を用いたマルチパーティ計算により復号した値により得られた前記大小関係の判定値を受信する第２受信ステップと、
前記判定値に基づいて、前記複数のデータを分類したクラスタを生成するクラスタリングステップと、
前記クラスタの情報を前記公開鍵により暗号化し、前記複数のパーティに送信する第２送信ステップと、をコンピュータが実行する分類方法。
【請求項４】
複数のパーティから、完全準同型の暗号方式により公開鍵で暗号化された複数のデータを受信する第１受信ステップと、
前記データ間のユークリッド距離と所定の距離との大小関係を求める演算を、暗号化された状態で行う演算ステップと、
前記演算の結果を前記複数のパーティに送信する第１送信ステップと、
前記演算の結果を各パーティの秘密鍵を用いたマルチパーティ計算により復号した値により得られた前記大小関係の判定値を受信する第２受信ステップと、
前記判定値に基づいて、前記複数のデータを分類したクラスタを生成するクラスタリングステップと、
前記クラスタの情報を前記公開鍵により暗号化し、前記複数のパーティに送信する第２送信ステップと、をコンピュータに実行させるための分類プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘匿されたデータを分類する分類装置、分類方法及び分類プログラムに関する。
【背景技術】
【０００２】
従来、ＤＢＳＣＡＮ（Ｄｅｎｓｉｔｙ−Ｂａｓｅｄ  Ｓｐａｔｉａｌ  Ｃｌｕｓｔｅｒｉｎｇ  ｏｆ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｗｉｔｈ  Ｎｏｉｓｅ）と呼ばれるクラスタリング手法が利用されている。
個人情報又は機密情報を所有するユーザは、ＤＢＳＣＡＮを使用して、一方の当事者のデータを他の当事者に明らかにすることなく、統合されたデータセットから意味のある情報を抽出したい場合がある。非特許文献１及び２では、プライバシを保護して２者のデータをクラスタリングする分散型ＤＢＳＣＡＮのプロトコルが提案されている。
また、非特許文献３では、秘匿された複数パーティのデータの、準同型暗号による演算方式が提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｊ．  Ｌｉｕ，  Ｌ．  Ｘｉｏｎｇ，  Ｊ．  Ｌｕｏ，  ａｎｄ  Ｊ．  Ｚ．  Ｈｕａｎｇ，  “Ｐｒｉｖａｃｙ  ｐｒｅｓｅｒｖｉｎｇ  ｄｉｓｔｒｉｂｕｔｅｄ  ＤＢＳＣＡＮ  ｃｌｕｓｔｅｒｉｎｇ，”  Ｔｒａｎｓ．  Ｄａｔａ  Ｐｒｉｖａｃｙ，  ｖｏｌ．  ６，  ｎｏ．  １，  ｐｐ．  ６９−８５，  ２０１３．
【非特許文献２】Ｋ．  Ａ．  Ｋｕｍａｒ  ａｎｄ  Ｃ．  Ｐ．  Ｒａｎｇａｎ，  “Ｐｒｉｖａｃｙ  ｐｒｅｓｅｒｖｉｎｇ  ｄｂｓｃａｎ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｃｌｕｓｔｅｒｉｎｇ，”  ｉｎ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｄｖａｎｃｅｄ  Ｄａｔａ  Ｍｉｎｉｎｇ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ．  Ｓｐｒｉｎｇｅｒ，  ２００７，  ｐｐ．  ５７−６８．
【非特許文献３】Ａ．  Ｌｏｐｅｚ−Ａｌｔ，  Ｅ．  Ｔｒｏｍｅｒ，  ａｎｄ  Ｖ．  Ｖａｉｋｕｎｔａｎａｔｈａｎ，  “Ｃｌｏｕｄ−ａｓｓｉｓｔｅｄ  ｍｕｌｔｉｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｆｒｏｍ  ｆｕｌｌｙ  ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ．”  ＩＡＣＲ  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ，  ｖｏｌ．  ２０１１．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来のＤＢＳＣＡＮのプロトコルは、３者以上のマルチパーティを効率的に扱うことができなかった。
【０００５】
本発明は、複数の当事者が秘匿データを他の当事者と共有することなく、クラスタリングするための分類装置、分類方法及び分類プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る分類装置は、複数のパーティから、完全準同型の暗号方式により公開鍵で暗号化された複数のデータを受信する第１受信部と、前記データ間のユークリッド距離と所定の距離との大小関係を求める演算を、暗号化された状態で行う演算部と、前記演算の結果を前記複数のパーティに送信する第１送信部と、前記演算の結果を各パーティの秘密鍵を用いたマルチパーティ計算により復号した値により得られた前記大小関係の判定値を受信する第２受信部と、前記判定値に基づいて、前記複数のデータを分類したクラスタを生成するクラスタリング部と、前記クラスタの情報を前記公開鍵により暗号化し、前記複数のパーティに送信する第２送信部と、を備える。
【０００７】
前記演算部は、前記ユークリッド距離の２乗と、前記所定の距離の２乗と、の差分値の暗号データを算出し、前記第２受信部は、前記差分値に基づく前記大小関係の判定値を受信してもよい。
【０００８】
本発明に係る分類方法は、複数のパーティから、完全準同型の暗号方式により公開鍵で暗号化された複数のデータを受信する第１受信ステップと、前記データ間のユークリッド距離と所定の距離との大小関係を求める演算を、暗号化された状態で行う演算ステップと、前記演算の結果を前記複数のパーティに送信する第１送信ステップと、前記演算の結果を各パーティの秘密鍵を用いたマルチパーティ計算により復号した値により得られた前記大小関係の判定値を受信する第２受信ステップと、前記判定値に基づいて、前記複数のデータを分類したクラスタを生成するクラスタリングステップと、前記クラスタの情報を前記公開鍵により暗号化し、前記複数のパーティに送信する第２送信ステップと、をコンピュータが実行する。
【０００９】
本発明に係る分類プログラムは、複数のパーティから、完全準同型の暗号方式により公開鍵で暗号化された複数のデータを受信する第１受信ステップと、前記データ間のユークリッド距離と所定の距離との大小関係を求める演算を、暗号化された状態で行う演算ステップと、前記演算の結果を前記複数のパーティに送信する第１送信ステップと、前記演算の結果を各パーティの秘密鍵を用いたマルチパーティ計算により復号した値により得られた前記大小関係の判定値を受信する第２受信ステップと、前記判定値に基づいて、前記複数のデータを分類したクラスタを生成するクラスタリングステップと、前記クラスタの情報を前記公開鍵により暗号化し、前記複数のパーティに送信する第２送信ステップと、をコンピュータに実行させる。
【発明の効果】
【００１０】
本発明によれば、複数の当事者が秘匿データを他の当事者と共有することなく、クラスタリングできる。
【図面の簡単な説明】
【００１１】
【図１】実施形態に係る分類システムの構成を示す図である。
【図２】実施形態に係るサーバの機能構成を示す図である。
【図３】実施形態に係る分類方法を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係る分類システム１００の構成を示す図である。
分類システム１００は、秘匿対象データを保有する複数（Ｎ）パーティそれぞれの端末Ｐｉ（１≦ｉ≦Ｎ）と、分類装置としてのサーバＳとを備え、互いにネットワークで通信接続されている。
【００１３】
端末Ｐｉは、後述のＭｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ（マルチパーティ計算）により協働することによって、データの暗号化及び復号を行える。端末Ｐｉは、それぞれが保有するデータセットを互いに、さらには第三者のサーバＳにも明らかにすることなく、クラスタリングの演算結果を取得する。
サーバＳは、端末Ｐｉから準同型暗号による秘匿データを受信し、後述のＤＢＳＣＡＮによってクラスタリングの演算を行う。
【００１４】
まず、分類システム１００で利用される要素技術について説明する。
［Ｍｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ（ＭＰＣ）］
ＭＰＣのプロトコルでは、キー準同型の公開鍵暗号方式により、各ユーザの公開鍵ｐｋ１、・・・、ｐｋＮから結合公開鍵ｐｋと、各ユーザの秘密鍵ｓｋ１、・・・、ｓｋＮから結合秘密鍵ｓｋとが生成される。各ユーザは、それぞれの所有データを結合公開鍵ｐｋで暗号化できる。このプロトコルは、ｔ（＜Ｎ）人のユーザの秘密鍵ｓｋｉ（１≦ｉ≦ｔ）を用いて暗号データが復号される。
【００１５】
［準同型暗号］
完全準同型の暗号方式は、メッセージ空間Ｍ内の要素ｍ１、ｍ２について、以下の２つの特性を持つ。
ｄｅｃｒｙｐｔ（ｅｎｃｒｙｐｔ（ｍ１）＋ｅｎｃｒｙｐｔ（ｍ２））＝ｍ１＋ｍ２
ｄｅｃｒｙｐｔ（ｅｎｃｒｙｐｔ（ｍ１）×ｅｎｃｒｙｐｔ（ｍ２））＝ｍ１×ｍ２
なお、演算「＋」及び「×」は、要素ごとの加算及び乗算である。
【００１６】
［ＤＢＳＣＡＮ］
定義１：密度到達可能（ｄｅｎｓｉｔｙ−ｒｅａｃｈａｂｌｅ）
あるオブジェクト（データ点）ｐｉから特定の半径ε内に最小個数ＭｉｎＰｔｓ以上のデータ点を含む場合、半径ε内のデータ点ｐｉ＋１はデータ点ｐｉから直接密度到達可能である。
直接密度到達可能なデータ点ｐ１、・・・、ｐｎの有限列がある場合、ｐ１＝ｑ、ｐｎ＝ｑとすると、データ点ｐはデータ点ｑから密度到達可能である。
【００１７】
定義２：密度接続（ｄｅｎｓｉｔｙ−ｃｏｎｎｅｃｔｅｄ）
データ点ｐ及びデータ点ｑの両方がデータ点ｏから密度到達可能であるようなデータ点ｏがある場合、データ点ｐとデータ点ｑとは、密度接続な関係にある。
【００１８】
定義３：クラスタ
Ｄをデータ点の集合とする。クラスタＣは、以下の条件を満たすＤの空でない部分集合である。
・クラスタＣは、全データ集合Ｄに含まれる全データ点に対して、密度到達可能なデータ点の極大集合である（極大性）。
・クラスタＣ内の全データ点は、相互に密度接続の関連にある（接続性）。
【００１９】
定義４：ノイズ
ノイズは、クラスタＣに属さない集合Ｄ内のデータ点の集合である。
【００２０】
ここで、あるデータ点ｐから半径εの範囲内にＭｉｎＰｔｓ以上のデータ点がある場合、このデータ点ｐはコアポイントと呼ばれる。コアポイントは、クラスタの内部にある。境界ポイントは、コアポイントの近傍にあるが、半径εの範囲内のデータ点がＭｉｎＰｔｓよりも少ない。ノイズポイントは、コアポイント又は境界ポイントではない任意のポイントである。
【００２１】
次に、分類システム１００によるクラスタリング手法を説明する。
図２は、本実施形態に係るサーバＳの機能構成を示す図である。
サーバＳは、第１受信部１１と、演算部１２と、第１送信部１３と、第２受信部１４と、クラスタリング部１５と、第２送信部１６とを備える。
【００２２】
第１受信部１１は、複数のパーティの端末Ｐｉから、完全準同型の暗号方式により公開鍵で暗号化された複数のデータを受信する。
【００２３】
演算部１２は、データ間のユークリッド距離ｄｉｓｔと所定の距離（前述の半径ε）との大小関係を求める演算を、暗号化された状態で行う。具体的には、演算部１２は、ｄｉｓｔの２乗と、εの２乗との差分値の暗号データを算出する。
【００２４】
第１送信部１３は、演算部１２による演算の結果を複数のパーティの端末Ｐｉに送信する。
演算結果を受信した端末Ｐｉは、演算の結果を各パーティの秘密鍵を用いたＭＰＣにより復号し、復号結果である差分値から、ｄｉｓｔとεとの大小関係を判定する。
【００２５】
第２受信部１４は、端末Ｐｉから、ｄｉｓｔとεとの大小関係の判定値を受信する。
例えば、第２受信部１４は、ｄｉｓｔ≦εの場合に「１」を、ｄｉｓｔ＞εの場合に「０」を受信する。
【００２６】
クラスタリング部１５は、第２受信部１４が受信した判定値に基づいて、ＤＢＳＣＡＮにより複数のデータを分類したクラスタを生成する。
【００２７】
第２送信部１６は、クラスタの情報を公開鍵により暗号化し、複数のパーティの端末Ｐｉに送信する。
端末Ｐｉは、受信したデータをＭＰＣにより復号し、クラスタリングの結果を取得する。
【００２８】
図３は、本実施形態に係る分類方法を示すフローチャートである。
ステップＳ１において、各パーティの端末Ｐｉは、データｘｉを暗号化し（ｃｉ＝Ｅｎｃｐｋ（ｘｉ））、暗号化データｃｉを生成する。
ステップＳ２において、端末Ｐｉは、暗号化データｃｉをサーバＳに送信する。
【００２９】
ステップＳ３において、サーバＳは、暗号化データｃｉをデータ点ｐとして選択し、ｐと別のデータ点ｐ’との間の暗号化されたユークリッド距離ｄｉｓｔを、次のように計算する。
ｄｉｓｔ２＝（Ｅｎｃｐｋ（ｐ）−Ｅｎｃｐｋ（ｐ’））２
＝Ｅｎｃｐｋ（ｐ）２−２Ｅｎｃｐｋ（ｐ）Ｅｎｃｐｋ（ｐ’）＋Ｅｎｃｐｋ（ｐ’）２
さらに、サーバＳは、ｄｉｓｔとεとを比較する演算として、次の計算を行う。
ｄｉ２＝Ｅｎｃｐｋ（ｄｉｓｔ２）＋Ｅｎｃｐｋ（−ε２）
＝Ｅｎｃｐｋ（ｄｉｓｔ２−ε２）
【００３０】
ステップＳ４において、サーバＳは、暗号化データｄｉ２を複数の端末Ｐに送信する。
ステップＳ５において、複数の端末Ｐは、ＭＰＣにより協働してｄｉ２を復号し、ｄｉｓｔとεとの大小関係を判定する。
【００３１】
ステップＳ６において、端末Ｐのいずれかは、ステップＳ５の判定結果を平文でサーバＳに送信する。具体的には、例えば、ｄｉｓｔ≦εの場合に「１」が、ｄｉｓｔ＞εの場合に「０」が送信される。
【００３２】
ステップＳ７において、サーバＳは、データ点ｐからＤＢＳＣＡＮのプロトコルに従い、ε及びＭｉｎＰｔｓに関して密度到達可能な全ての点を取得する。
このとき、ｐがコアポイントであれば、クラスタが形成される。
【００３３】
ステップＳ８において、サーバＳは、全てのデータ点を処理したか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ９に移り、判定がＮＯの場合、処理はステップＳ３に戻り、次のデータ点が選択される。
【００３４】
ステップＳ９において、サーバＳは、形成されたクラスタの情報を公開鍵により暗号化する。
ステップＳ１０において、サーバＳは、暗号化したクラスタの情報を複数パーティの端末Ｐに送信する。
ステップＳ１１において、複数の端末Ｐは、ステップＳ９で受信した暗号データをＭＰＣにより協働して復号し、クラスタの情報を取得する。
【００３５】
本実施形態によれば、分類システム１００において、複数のパーティは、完全準同型の暗号方式により、データセットを互いに共有することなく、さらに、サーバＳにも知られることなく、ＤＢＳＣＡＮによるクラスタリングの計算をサーバＳに実行させる。このとき、サーバＳは、データ間のユークリッド距離と所定の距離との大小関係を、暗号化されたまま演算するが、複数パーティによるＭＰＣにより結果のみを取得する。
具体的には、サーバＳは、大小関係を２乗の差分として計算することにより、加算及び乗算のみで結果を得ることができるので、完全準同型の暗号方式により、暗号化されたまま演算できる。
【００３６】
このように、分類システム１００は、高負荷な演算をサーバＳにアウトソースすることで、複数パーティの端末Ｐの処理負荷を低減させつつも、サーバＳに対してデータセットを公開することなく、安全にクラスタリングを実行できる。
【００３７】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００３８】
分類システム１００による分類方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００３９】
Ｐ  端末
Ｓ  サーバ
１１  第１受信部
１２  演算部
１３  第１送信部
１４  第２受信部
１５  クラスタリング部
１６  第２送信部
１００  分類システム
【図１】
2018124513.tif 000003
【図２】
2018124513.tif 000004
【図３】
2018124513.tif 000005