(57)【要約】【課題】複数のクラスタリング実行が組み合わされた攻撃に対しても、安全性が保証できる状態で、分散データのクラスタリングができるようにする。【解決手段】クラスタリング装置Ａ１００は、データベースＡ１０１，第１変換部１０２，設定部１０３，第３変換部１０４，多項式通知部１０５，多項式計算部１０６，第５変換部１０７，第７変換部１０８，変換値通知部１０９，中心設定部１１０，およびクラスタリング情報記憶部１１１を備える。また、クラスタリング装置Ｂ１５０は、データベースＢ１５１，第２変換部１５２，設定部１５３，第４変換部１５４，多項式通知部１５５，多項式計算部１５６，第６変換部１５７，第８変換部１５８，変換値通知部１５９，中心設定部１６０，およびクラスタリング情報記憶部１６１を備える。【選択図】  図１
2011090538.tif 000002
【特許請求の範囲】
【請求項１】
第１クラスタリング装置が有する第１データベースに含まれてベクトルで表されたデータ群からなる第１クラスのデータ数と、
前記第１クラスタリング装置とネットワークを介して接続している第２クラスタリング装置が有する第２データベースに含まれてベクトルで表されたデータ群からなる第２クラスのデータ数と
から、これらと和が等しいａ１およびａ２を求める第１ステップと、
前記第１クラスタリング装置では、予め設定されている自然数Ｎ２を用いてｂ1,i＝ａ１×１／２i（ｉ＝２，・・・Ｎ２＋１）を求め、
前記第２クラスタリング装置では、予め設定されている自然数Ｎ１を用いてｂ2,j＝ａ２×１／２j（ｊ＝２，・・・Ｎ１＋１）を求める第２ステップと、
前記第１クラスタリング装置では、ｂ1,iを有限体上のｃ1,iに変換し、
前記第２クラスタリング装置では、ｂ2,jを有限体上のｃ2,jに変換する第３ステップと、
前記第１クラスタリング装置で任意に設定されたｍ１と、前記第２クラスタリング装置で任意に設定されたｍ２とから、これらと和が等しいｄ１およびｄ２を求める第４ステップと、
前記第１クラスタリング装置では、
任意に設定した有理数からなる定数ｅ１と変数ｘとを用いて以下の式（１）で示される多項式を生成して前記第２クラスタリング装置に通知し、
【数１】
2011090538.tif 000006
前記第２クラスタリング装置では、任意に設定した有理数からなる定数ｆ１と変数ｘとを用いて以下の式（２）で示される多項式を生成して前記第１クラスタリング装置に通知する第５ステップと、
【数２】
2011090538.tif 000007
第１クラスタリング装置では、前記式（２）によるＲ２（ｄ１）＝ｆ２を算出し、第２クラスタリング装置では、前記式（１）によるＲ２（ｄ２）＝ｅ２を算出する第６ステップと、
ｅ１＋ｆ１とｅ２＋ｆ２との積に和が等しいｇ１およびｇ２を求める第７ステップと、
前記第１クラスのデータの座標の和と前記第２クラスのデータの座標の和とから、これらと和が等しいｈ１およびｈ２を求める第８ステップと、
前記第１クラスタリング装置では、Ｍ１＝ｇ１×ｈ１×２-N2を計算して前記Ｍ１を第２クラスタリング装置に通知し、
前記第２クラスタリング装置では、Ｍ２＝ｇ２×ｈ２×２-N1を計算して前記Ｍ２を第１クラスタリング装置に通知する第９ステップと、
前記第１クラスタリング装置および前記第２クラスタリング装置の各々において、Ｍ１×Ｍ２を求め、Ｍ１×Ｍ２を、前記第１クラスと前記第２クラスとを合わせた新たなクラスタの中心とする第１０ステップと
を少なくとも備え、
前記第１ステップでは、
前記第１クラスタリング装置で、前記第１クラスのデータ数より抽出したこのデータ数に関連する情報を含む第１部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２クラスタリング装置で、前記第２クラスのデータ数より抽出したこのデータ数に関連する情報を含む第２部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１クラスタリング装置で、前記第２部分情報と前記第１クラスのデータ数とよりａ１を求め、
前記第２クラスタリング装置で、前記第１部分情報と前記第２クラスのデータ数とよりａ２を求め、
前記第４ステップでは、
前記第１クラスタリング装置で、ｍ１より抽出したｍ１に関連する情報を含む第３部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２クラスタリング装置で、ｍ２より抽出したｍ２に関連する情報を含む第４部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１クラスタリング装置で、前記第４部分情報とｍ１とよりｄ１を求め、
前記第２クラスタリング装置で、前記第３部分情報とｍ２とよりｄ２を求め、
前記第７ステップでは、
前記第１クラスタリング装置で、ｅ１＋ｆ１より抽出したｅ１＋ｆ１に関連する情報を含む第５部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２クラスタリング装置で、ｅ２＋ｆ２より抽出したｅ２＋ｆ２に関連する情報を含む第６部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１クラスタリング装置で、前記第６部分情報とｅ１＋ｆ１とよりｇ１を求め、
前記第２クラスタリング装置で、前記第５部分情報とｅ２＋ｆ２とよりｇ２を求め、
前記第８ステップでは、
前記第１クラスタリング装置で、前記第１クラスのデータの座標の和より抽出した前記第１クラスのデータの座標の和に関連する情報を含む第７部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２クラスタリング装置で、前記第２クラスのデータの座標の和より抽出した前記第２クラスのデータの座標の和に関連する情報を含む第８部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１クラスタリング装置で、前記第８部分情報と前記第１クラスのデータの座標の和とよりｈ１を求め、
前記第２クラスタリング装置で、前記第７部分情報と前記第２クラスのデータの座標の和とよりでｈ２を求める
ことを特徴とする分散データのクラスタリング方法。
【請求項２】
第１クラスタリング装置が有する第１データベースに含まれてベクトルで表されたデータ群からなる第１クラスのデータ数と、
前記第１クラスタリング装置とネットワークを介して接続している第２クラスタリング装置が有する第２データベースに含まれてベクトルで表されたデータ群からなる第２クラスのデータ数と
から、これらと和が等しいａ１およびａ２を求める第１変換手段および第２変換手段と、
予め設定されている自然数Ｎ２を用いてｂ1,i＝ａ１×１／２i（ｉ＝２，・・・Ｎ２＋１）を求める前記第１クラスタリング装置に配置された第１設定手段と、
予め設定されている自然数Ｎ１を用いてｂ2,j＝ａ２×１／２j（ｊ＝２，・・・Ｎ１＋１）を求める前記第２クラスタリング装置に配置された第２設定手段と、
前記第１クラスタリング装置で任意に設定されたｍ１と、前記第２クラスタリング装置で任意に設定されたｍ２とから、これらと和が等しいｄ１およびｄ２を求める第３変換手段および第４変換手段と、
前記第１クラスタリング装置に配置され、任意に設定した有理数からなる定数ｅ１と変数ｘとを用いて以下の式（１）で示される多項式を生成して前記第２クラスタリング装置に通知する第１多項式通知手段と、
【数３】
2011090538.tif 000008
前記第２クラスタリング装置に配置され、任意に設定した有理数からなる定数ｆ１と変数ｘとを用いて以下の式（２）で示される多項式を生成して前記第１クラスタリング装置に通知する第２多項式通知手段と、
【数４】
2011090538.tif 000009
第１クラスタリング装置に配置されて前記式（２）によるＲ２（ｄ１）＝ｆ２を算出する第１多項式計算手段と、
第２クラスタリング装置に配置されて前記式（１）によるＲ２（ｄ２）＝ｅ２を算出する第２多項式計算手段と、
ｅ１＋ｆ１とｅ２＋ｆ２との積に和が等しいｇ１およびｇ２を求める第５変換手段および第６変換手段と、
前記第１クラスのデータの座標の和と前記第２クラスのデータの座標の和とから、これらと和が等しいｈ１およびｈ２を求める第７変換手段および第８変換手段と、
前記第１クラスタリング装置に配置されてＭ１＝ｇ１×ｈ１×２-N2を計算して前記Ｍ１を第２クラスタリング装置に通知する第１変換値通知手段と、
前記第２クラスタリング装置に配置されてＭ２＝ｇ２×ｈ２×２-N1を計算して前記Ｍ２を第１クラスタリング装置に通知する第２変換値通知手段と、
前記第１クラスタリング装置および前記第２クラスタリング装置の各々に配置され、Ｍ１×Ｍ２を求め、Ｍ１×Ｍ２を、前記第１クラスと前記第２クラスとを合わせた新たなクラスタの中心とする第１中心設定手段および第２中心設定手段と
を少なくとも備え、
前記第１変換手段は、前記第１クラスタリング装置に配置され、前記第１クラスのデータ数より抽出したこのデータ数に関連する情報を含む第１部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２変換手段は、前記第２クラスタリング装置に配置され、前記第２クラスのデータ数より抽出したこのデータ数に関連する情報を含む第２部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１変換手段は、前記第２部分情報と前記第１クラスのデータ数とよりａ１を求め、
前記第２変換手段は、前記第１部分情報と前記第２クラスのデータ数とよりａ２を求め、
前記第３変換手段は、前記第１クラスタリング装置に配置され、ｍ１より抽出したｍ１に関連する情報を含む第３部分情報を生成して前記第２クラスタリング装置に通知し、
前記第４変換手段は、前記第２クラスタリング装置に配置され、ｍ２より抽出したｍ２に関連する情報を含む第４部分情報を生成して前記第１クラスタリング装置に通知し、
前記第３変換手段は、前記第４部分情報とｍ１とよりｄ１を求め、
前記第４変換手段は、前記第３部分情報とｍ２とよりｄ２を求め、
前記第５変換手段は、前記第１クラスタリング装置に配置され、ｅ１＋ｆ１より抽出したｅ１＋ｆ１に関連する情報を含む第５部分情報を生成して前記第２クラスタリング装置に通知し、
前記第６変換手段は、前記第２クラスタリング装置に配置され、ｅ２＋ｆ２より抽出したｅ２＋ｆ２に関連する情報を含む第６部分情報を生成して前記第１クラスタリング装置に通知し、
前記第５変換手段は、前記第６部分情報とｅ１＋ｆ１とよりｇ１を求め、
前記第６変換手段は、前記第５部分情報とｅ２＋ｆ２とよりｇ２を求め、
前記第７変換手段は、前記第１クラスタリング装置に配置され、前記第１クラスのデータの座標の和より抽出した前記第１クラスのデータの座標の和に関連する情報を含む第７部分情報を生成して前記第２クラスタリング装置に通知し、
前記第８変換手段は、前記第２クラスタリング装置に配置され、前記第２クラスのデータの座標の和より抽出した前記第２クラスのデータの座標の和に関連する情報を含む第８部分情報を生成して前記第１クラスタリング装置に通知し、
前記第７変換手段は、前記第８部分情報と前記第１クラスのデータの座標の和とよりｈ１を求め、
前記第８変換手段は、前記第７部分情報と前記第２クラスのデータの座標の和とよりでｈ２を求める
ことを特徴とする分散データのクラスタリングシステム。
【請求項３】
コンピュータに、
第１クラスタリング装置が有する第１データベースに含まれてベクトルで表されたデータ群からなる第１クラスのデータ数と、
前記第１クラスタリング装置とネットワークを介して接続している第２クラスタリング装置が有する第２データベースに含まれてベクトルで表されたデータ群からなる第２クラスのデータ数と
から、これらと和が等しいａ１およびａ２を求める第１機能と、
前記第１クラスタリング装置では、予め設定されている自然数Ｎ２を用いてｂ1,i＝ａ１×１／２i（ｉ＝２，・・・Ｎ２＋１）を求め、
前記第２クラスタリング装置では、予め設定されている自然数Ｎ１を用いてｂ2,j＝ａ２×１／２j（ｊ＝２，・・・Ｎ１＋１）を求める第２機能と、
前記第１クラスタリング装置では、ｂ1,iを有限体上のｃ1,iに変換し、
前記第２クラスタリング装置では、ｂ2,jを有限体上のｃ2,jに変換する第３機能と、
前記第１クラスタリング装置で任意に設定されたｍ１と、前記第２クラスタリング装置で任意に設定されたｍ２とから、これらと和が等しいｄ１およびｄ２を求める第４機能と、
前記第１クラスタリング装置では、
任意に設定した有理数からなる定数ｅ１と変数ｘとを用いて以下の式（１）で示される多項式を生成して前記第２クラスタリング装置に通知し、
【数５】
2011090538.tif 000010
前記第２クラスタリング装置では、任意に設定した有理数からなる定数ｆ１と変数ｘとを用いて以下の式（２）で示される多項式を生成して前記第１クラスタリング装置に通知する第５機能と、
【数６】
2011090538.tif 000011
第１クラスタリング装置では、前記式（２）によるＲ２（ｄ１）＝ｆ２を算出し、第２クラスタリング装置では、前記式（１）によるＲ２（ｄ２）＝ｅ２を算出する第６機能と、
ｅ１＋ｆ１とｅ２＋ｆ２との積に和が等しいｇ１およびｇ２を求める第７機能と、
前記第１クラスのデータの座標の和と前記第２クラスのデータの座標の和とから、これらと和が等しいｈ１およびｈ２を求める第８機能と、
前記第１クラスタリング装置では、Ｍ１＝ｇ１×ｈ１×２-N2を計算して前記Ｍ１を第２クラスタリング装置に通知し、
前記第２クラスタリング装置では、Ｍ２＝ｇ２×ｈ２×２-N1を計算して前記Ｍ２を第１クラスタリング装置に通知する第９機能と、
前記第１クラスタリング装置および前記第２クラスタリング装置の各々において、Ｍ１×Ｍ２を求め、Ｍ１×Ｍ２を、前記第１クラスと前記第２クラスとを合わせた新たなクラスタの中心とする第１０機能と
をすくなくとも実現させ、
前記第１機能では、
前記第１クラスタリング装置で、前記第１クラスのデータ数より抽出したこのデータ数に関連する情報を含む第１部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２クラスタリング装置で、前記第２クラスのデータ数より抽出したこのデータ数に関連する情報を含む第２部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１クラスタリング装置で、前記第２部分情報と前記第１クラスのデータ数とよりａ１を求め、
前記第２クラスタリング装置で、前記第１部分情報と前記第２クラスのデータ数とよりａ２を求め、
前記第４機能では、
前記第１クラスタリング装置で、ｍ１より抽出したｍ１に関連する情報を含む第３部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２クラスタリング装置で、ｍ２より抽出したｍ２に関連する情報を含む第４部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１クラスタリング装置で、前記第４部分情報とｍ１とよりｄ１を求め、
前記第２クラスタリング装置で、前記第３部分情報とｍ２とよりｄ２を求め、
前記第７機能では、
前記第１クラスタリング装置で、ｅ１＋ｆ１より抽出したｅ１＋ｆ１に関連する情報を含む第５部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２クラスタリング装置で、ｅ２＋ｆ２より抽出したｅ２＋ｆ２に関連する情報を含む第６部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１クラスタリング装置で、前記第６部分情報とｅ１＋ｆ１とよりｇ１を求め、
前記第２クラスタリング装置で、前記第５部分情報とｅ２＋ｆ２とよりｇ２を求め、
前記第８機能では、
前記第１クラスタリング装置で、前記第１クラスのデータの座標の和より抽出した前記第１クラスのデータの座標の和に関連する情報を含む第７部分情報を生成して前記第２クラスタリング装置に通知し、
前記第２クラスタリング装置で、前記第２クラスのデータの座標の和より抽出した前記第２クラスのデータの座標の和に関連する情報を含む第８部分情報を生成して前記第１クラスタリング装置に通知し、
前記第１クラスタリング装置で、前記第８部分情報と前記第１クラスのデータの座標の和とよりｈ１を求め、
前記第２クラスタリング装置で、前記第７部分情報と前記第２クラスのデータの座標の和とよりでｈ２を求める
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上に分散している複数のデータベースをクラスタリングする分散データのクラスタリング方法、システム、およびプログラムに関するものである。
【背景技術】
【０００２】
インターネットなどのネットワーク上に分散している複数のデータベースをクラスタリングし、類似したデータを分類することで、大量のデータより目的のデータをより迅速に検索することが可能となる。また、このようなクラスタリングにより、大領のデータの特徴を把握することができるようになる。
【０００３】
ただし、このようなクラスタリングを実施するためには、ネットワーク上に分散している他のデータベースを参照することになるため、プライバシーなどの秘密保持が重要となる。このため、データベースの特徴を抽出したデータを用いてクラスタリングする技術（秘密クラスタリング）がある（非特許文献１，２参照）。非特許文献１では、分散決定木学習を利用した、効率のよい秘密クラスタリングを提案している。また、非特許文献２では、マルチパーティプロトコルを利用し、安全な秘密クラスタリングを提案している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Y.Lindell and B.Pinkas, "Privacy Preserving Data Mining", Proceedings of CRYPTO 2000, pp.36-54.
【非特許文献２】J.Vaidya, C.Clifton, "Privacy-Preserving K-Means Clustering over Vertically Partitioned Data", KDD 2003, pp.206-215.
【非特許文献３】E.Kiltz, et al. ,"Secure Computation of the Mean and Related Statistics", J. Kilian (Ed.): TCC 2005, LNCS 3378, pp.283-302, 2005.
【非特許文献４】蘇  春華、櫟  粛之、櫻井  幸一、「汎用的結合性のある秘密多項式評価法」、電子情報通信学会総合大会、情報・システム講演論文集1、DS-1-1、２００８年。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１の技術では、効率的にクラスタリングができるが、安全性については弱い面がある。また、非特許文献２の技術では、効率がよくなく、また、安全性も十分ではないという問題がある。
【０００６】
これらの技術では、クラスタリングに参加する攻撃者が、作業中のクラスタリングにおいて、他の（相手の）データベースにおける秘密保持に関し、このデータベースの情報を得ることができないという安全性を保証している。しかしながら、インターネットなどの匿名性の強いネットワークでは、この安全性では不十分である。例えば、攻撃者が別の参加者を名乗るというなりすましにより、本来のクラスタリング作業と当時に、なりすました参加者としてクラスタリング計算を行い、このクラスタリング計算において得られた情報を利用し、相手のデータベースの秘密情報を手に入れてしまう可能性がある。
【０００７】
本発明は、以上のような問題点を解消するためになされたものであり、複数のクラスタリング実行が組み合わされた攻撃に対しても、安全性が保証できる状態で、分散データのクラスタリングができるようにすることを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る分散データのクラスタリング方法は、第１クラスタリング装置が有する第１データベースに含まれてベクトルで表されたデータ群からなる第１クラスのデータ数と、第１クラスタリング装置とネットワークを介して接続している第２クラスタリング装置が有する第２データベースに含まれてベクトルで表されたデータ群からなる第２クラスのデータ数とから、これらと和が等しいａ１およびａ２を求める第１ステップと、第１クラスタリング装置では、予め設定されている自然数Ｎ２を用いてｂ1,i＝ａ１×１／２i（ｉ＝２，・・・Ｎ２＋１）を求め、第２クラスタリング装置では、予め設定されている自然数Ｎ１を用いてｂ2,j＝ａ２×１／２j（ｊ＝２，・・・Ｎ１＋１）を求める第２ステップと、第１クラスタリング装置では、ｂ1,iを有限体上のｃ1,iに変換し、第２クラスタリング装置では、ｂ2,jを有限体上のｃ2,jに変換する第３ステップと、第１クラスタリング装置で任意に設定されたｍ１と、第２クラスタリング装置で任意に設定されたｍ２とから、これらと和が等しいｄ１およびｄ２を求める第４ステップと、第１クラスタリング装置では、任意に設定した有理数からなる定数ｅ１と変数ｘとを用いて以下の式（１）で示される多項式を生成して第２クラスタリング装置に通知し、第２クラスタリング装置では、任意に設定した有理数からなる定数ｆ１と変数ｘとを用いて以下の式（２）で示される多項式を生成して第１クラスタリング装置に通知する第５ステップと、第１クラスタリング装置では、式（２）によるＲ２（ｄ１）＝ｆ２を算出し、第２クラスタリング装置では、式（１）によるＲ２（ｄ２）＝ｅ２を算出する第６ステップと、ｅ１＋ｆ１とｅ２＋ｆ２との積に和が等しいｇ１およびｇ２を求める第７ステップと、第１クラスのデータの座標の和と第２クラスのデータの座標の和とから、これらと和が等しいｈ１およびｈ２を求める第８ステップと、第１クラスタリング装置では、Ｍ１＝ｇ１×ｈ１×２-N2を計算してＭ１を第２クラスタリング装置に通知し、第２クラスタリング装置では、Ｍ２＝ｇ２×ｈ２×２-N1を計算してＭ２を第１クラスタリング装置に通知する第９ステップと、第１クラスタリング装置および第２クラスタリング装置の各々において、Ｍ１×Ｍ２を求め、Ｍ１×Ｍ２を、第１クラスと第２クラスとを合わせた新たなクラスタの中心とする第１０ステップとを少なくとも備え、第１ステップでは、第１クラスタリング装置で、第１クラスのデータ数より抽出したこのデータ数に関連する情報を含む第１部分情報を生成して第２クラスタリング装置に通知し、第２クラスタリング装置で、第２クラスのデータ数より抽出したこのデータ数に関連する情報を含む第２部分情報を生成して第１クラスタリング装置に通知し、第１クラスタリング装置で、第２部分情報と第１クラスのデータ数とよりａ１を求め、第２クラスタリング装置で、第１部分情報と第２クラスのデータ数とよりａ２を求め、第４ステップでは、第１クラスタリング装置で、ｍ１より抽出したｍ１に関連する情報を含む第３部分情報を生成して第２クラスタリング装置に通知し、第２クラスタリング装置で、ｍ２より抽出したｍ２に関連する情報を含む第４部分情報を生成して第１クラスタリング装置に通知し、第１クラスタリング装置で、第４部分情報とｍ１とよりｄ１を求め、第２クラスタリング装置で、第３部分情報とｍ２とよりｄ２を求め、第７ステップでは、第１クラスタリング装置で、ｅ１＋ｆ１より抽出したｅ１＋ｆ１に関連する情報を含む第５部分情報を生成して第２クラスタリング装置に通知し、第２クラスタリング装置で、ｅ２＋ｆ２より抽出したｅ２＋ｆ２に関連する情報を含む第６部分情報を生成して第１クラスタリング装置に通知し、第１クラスタリング装置で、第６部分情報とｅ１＋ｆ１とよりｇ１を求め、第２クラスタリング装置で、第５部分情報とｅ２＋ｆ２とよりｇ２を求め、第８ステップでは、第１クラスタリング装置で、第１クラスのデータの座標の和より抽出した第１クラスのデータの座標の和に関連する情報を含む第７部分情報を生成して第２クラスタリング装置に通知し、第２クラスタリング装置で、第２クラスのデータの座標の和より抽出した第２クラスのデータの座標の和に関連する情報を含む第８部分情報を生成して第１クラスタリング装置に通知し、第１クラスタリング装置で、第８部分情報と第１クラスのデータの座標の和とよりｈ１を求め、第２クラスタリング装置で、第７部分情報と第２クラスのデータの座標の和とよりでｈ２を求める。
【０００９】
また、本発明に係る分散データのクラスタリング装置は、第１クラスタリング装置が有する第１データベースに含まれてベクトルで表されたデータ群からなる第１クラスのデータ数と、第１クラスタリング装置とネットワークを介して接続している第２クラスタリング装置が有する第２データベースに含まれてベクトルで表されたデータ群からなる第２クラスのデータ数とから、これらと和が等しいａ１およびａ２を求める第１変換手段および第２変換手段と、予め設定されている自然数Ｎ２を用いてｂ1,i＝ａ１×１／２i（ｉ＝２，・・・Ｎ２＋１）を求める第１クラスタリング装置に配置された第１設定手段と、予め設定されている自然数Ｎ１を用いてｂ2,j＝ａ２×１／２j（ｊ＝２，・・・Ｎ１＋１）を求める第２クラスタリング装置に配置された第２設定手段と、第１クラスタリング装置で任意に設定されたｍ１と、第２クラスタリング装置で任意に設定されたｍ２とから、これらと和が等しいｄ１およびｄ２を求める第３変換手段および第４変換手段と、第１クラスタリング装置に配置され、任意に設定した有理数からなる定数ｅ１と変数ｘとを用いて以下の式（１）で示される多項式を生成して第２クラスタリング装置に通知する第１多項式通知手段と、第２クラスタリング装置に配置され、任意に設定した有理数からなる定数ｆ１と変数ｘとを用いて以下の式（２）で示される多項式を生成して第１クラスタリング装置に通知する第２多項式通知手段と、第１クラスタリング装置に配置されて式（２）によるＲ２（ｄ１）＝ｆ２を算出する第１多項式計算手段と、第２クラスタリング装置に配置されて式（１）によるＲ２（ｄ２）＝ｅ２を算出する第２多項式計算手段と、ｅ１＋ｆ１とｅ２＋ｆ２との積に和が等しいｇ１およびｇ２を求める第５変換手段および第６変換手段と、第１クラスのデータの座標の和と第２クラスのデータの座標の和とから、これらと和が等しいｈ１およびｈ２を求める第７変換手段および第８変換手段と、第１クラスタリング装置に配置されてＭ１＝ｇ１×ｈ１×２-N2を計算してＭ１を第２クラスタリング装置に通知する第１変換値通知手段と、第２クラスタリング装置に配置されてＭ２＝ｇ２×ｈ２×２-N1を計算してＭ２を第１クラスタリング装置に通知する第２変換値通知手段と、第１クラスタリング装置および第２クラスタリング装置の各々に配置され、Ｍ１×Ｍ２を求め、Ｍ１×Ｍ２を、第１クラスと第２クラスとを合わせた新たなクラスタの中心とする第１中心設定手段および第２中心設定手段とを少なくとも備え、第１変換手段は、第１クラスタリング装置に配置され、第１クラスのデータ数より抽出したこのデータ数に関連する情報を含む第１部分情報を生成して第２クラスタリング装置に通知し、第２変換手段は、第２クラスタリング装置に配置され、第２クラスのデータ数より抽出したこのデータ数に関連する情報を含む第２部分情報を生成して第１クラスタリング装置に通知し、第１変換手段は、第２部分情報と第１クラスのデータ数とよりａ１を求め、第２変換手段は、第１部分情報と第２クラスのデータ数とよりａ２を求め、第３変換手段は、第１クラスタリング装置に配置され、ｍ１より抽出したｍ１に関連する情報を含む第３部分情報を生成して第２クラスタリング装置に通知し、第４変換手段は、第２クラスタリング装置に配置され、ｍ２より抽出したｍ２に関連する情報を含む第４部分情報を生成して第１クラスタリング装置に通知し、第３変換手段は、第４部分情報とｍ１とよりｄ１を求め、第４変換手段は、第３部分情報とｍ２とよりｄ２を求め、第５変換手段は、第１クラスタリング装置に配置され、ｅ１＋ｆ１より抽出したｅ１＋ｆ１に関連する情報を含む第５部分情報を生成して第２クラスタリング装置に通知し、第６変換手段は、第２クラスタリング装置に配置され、ｅ２＋ｆ２より抽出したｅ２＋ｆ２に関連する情報を含む第６部分情報を生成して第１クラスタリング装置に通知し、第５変換手段は、第６部分情報とｅ１＋ｆ１とよりｇ１を求め、第６変換手段は、第５部分情報とｅ２＋ｆ２とよりｇ２を求め、第７変換手段は、第１クラスタリング装置に配置され、第１クラスのデータの座標の和より抽出した第１クラスのデータの座標の和に関連する情報を含む第７部分情報を生成して第２クラスタリング装置に通知し、第８変換手段は、第２クラスタリング装置に配置され、第２クラスのデータの座標の和より抽出した第２クラスのデータの座標の和に関連する情報を含む第８部分情報を生成して第１クラスタリング装置に通知し、第７変換手段は、第８部分情報と第１クラスのデータの座標の和とよりｈ１を求め、第８変換手段は、第７部分情報と第２クラスのデータの座標の和とよりでｈ２を求める。
【００１０】
また、本発明に係るプログラムは、コンピュータに、第１クラスタリング装置が有する第１データベースに含まれてベクトルで表されたデータ群からなる第１クラスのデータ数と、第１クラスタリング装置とネットワークを介して接続している第２クラスタリング装置が有する第２データベースに含まれてベクトルで表されたデータ群からなる第２クラスのデータ数とから、これらと和が等しいａ１およびａ２を求める第１機能と、第１クラスタリング装置では、予め設定されている自然数Ｎ２を用いてｂ1,i＝ａ１×１／２i（ｉ＝２，・・・Ｎ２＋１）を求め、第２クラスタリング装置では、予め設定されている自然数Ｎ１を用いてｂ2,j＝ａ２×１／２j（ｊ＝２，・・・Ｎ１＋１）を求める第２機能と、第１クラスタリング装置では、ｂ1,iを有限体上のｃ1,iに変換し、第２クラスタリング装置では、ｂ2,jを有限体上のｃ2,jに変換する第３機能と、第１クラスタリング装置で任意に設定されたｍ１と、第２クラスタリング装置で任意に設定されたｍ２とから、これらと和が等しいｄ１およびｄ２を求める第４機能と、第１クラスタリング装置では、任意に設定した有理数からなる定数ｅ１と変数ｘとを用いて以下の式（１）で示される多項式を生成して第２クラスタリング装置に通知し、第２クラスタリング装置では、任意に設定した有理数からなる定数ｆ１と変数ｘとを用いて以下の式（２）で示される多項式を生成して第１クラスタリング装置に通知する第５機能と、第１クラスタリング装置では、式（２）によるＲ２（ｄ１）＝ｆ２を算出し、第２クラスタリング装置では、式（１）によるＲ２（ｄ２）＝ｅ２を算出する第６機能と、ｅ１＋ｆ１とｅ２＋ｆ２との積に和が等しいｇ１およびｇ２を求める第７機能と、第１クラスのデータの座標の和と第２クラスのデータの座標の和とから、これらと和が等しいｈ１およびｈ２を求める第８機能と、第１クラスタリング装置では、Ｍ１＝ｇ１×ｈ１×２-N2を計算してＭ１を第２クラスタリング装置に通知し、第２クラスタリング装置では、Ｍ２＝ｇ２×ｈ２×２-N1を計算してＭ２を第１クラスタリング装置に通知する第９機能と、第１クラスタリング装置および第２クラスタリング装置の各々において、Ｍ１×Ｍ２を求め、Ｍ１×Ｍ２を、第１クラスと第２クラスとを合わせた新たなクラスタの中心とする第１０機能とを少なくとも実現させ、第１機能では、第１クラスタリング装置で、第１クラスのデータ数より抽出したこのデータ数に関連する情報を含む第１部分情報を生成して第２クラスタリング装置に通知し、第２クラスタリング装置で、第２クラスのデータ数より抽出したこのデータ数に関連する情報を含む第２部分情報を生成して第１クラスタリング装置に通知し、第１クラスタリング装置で、第２部分情報と第１クラスのデータ数とよりａ１を求め、第２クラスタリング装置で、第１部分情報と第２クラスのデータ数とよりａ２を求め、第４機能では、第１クラスタリング装置で、ｍ１より抽出したｍ１に関連する情報を含む第３部分情報を生成して第２クラスタリング装置に通知し、第２クラスタリング装置で、ｍ２より抽出したｍ２に関連する情報を含む第４部分情報を生成して第１クラスタリング装置に通知し、第１クラスタリング装置で、第４部分情報とｍ１とよりｄ１を求め、第２クラスタリング装置で、第３部分情報とｍ２とよりｄ２を求め、第７機能では、第１クラスタリング装置で、ｅ１＋ｆ１より抽出したｅ１＋ｆ１に関連する情報を含む第５部分情報を生成して第２クラスタリング装置に通知し、第２クラスタリング装置で、ｅ２＋ｆ２より抽出したｅ２＋ｆ２に関連する情報を含む第６部分情報を生成して第１クラスタリング装置に通知し、第１クラスタリング装置で、第６部分情報とｅ１＋ｆ１とよりｇ１を求め、第２クラスタリング装置で、第５部分情報とｅ２＋ｆ２とよりｇ２を求め、第８機能では、第１クラスタリング装置で、第１クラスのデータの座標の和より抽出した第１クラスのデータの座標の和に関連する情報を含む第７部分情報を生成して第２クラスタリング装置に通知し、第２クラスタリング装置で、第２クラスのデータの座標の和より抽出した第２クラスのデータの座標の和に関連する情報を含む第８部分情報を生成して第１クラスタリング装置に通知し、第１クラスタリング装置で、第８部分情報と第１クラスのデータの座標の和とよりｈ１を求め、第２クラスタリング装置で、第７部分情報と第２クラスのデータの座標の和とよりでｈ２を求める。
【００１１】
【数１】
2011090538.tif 000003
【発明の効果】
【００１２】
以上説明したように、本発明によれば、一方のデータ数と、他方のデータ数とから、これらと和が等しくなるように求めたａ１およびａ２と、各々で任意に設定した各々の多項式と、一方のデータの座標の和と他方のデータの座標の和とから、これらと和が等しくなるように求めたｈ１およびｈ２とより、２つのクラスの中心の近似値を求めるようにしたので、安全性が保証できる状態で、分散データのクラスタリングができるようになるという優れた効果が得られる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態における分散クラスタリングシステムの構成を示す構成図である。
【図２】実施の形態における分散データのクラスタリングシステムの動作について説明するフローチャートである。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について図を参照して説明する。図１は、本発明の実施の形態における分散データのクラスタリングシステムの構成を示す構成図である。以下では、２つのクラスタリング装置Ａ１００およびクラスタリング装置Ｂ１５０によりシステムが構成されている場合を例に説明する。クラスタリング装置Ａ１００およびクラスタリング装置Ｂ１５０は、例えば、インターネット通信網などのネットワーク１４０を介して接続されている。なお、クラスタリング装置は、２つに限るものはない。
【００１５】
まず、クラスタリング装置Ａ１００は、データベースＡ１０１，第１変換部１０２，設定部１０３，第３変換部１０４，多項式通知部１０５，多項式計算部１０６，第５変換部１０７，第７変換部１０８，変換値通知部１０９，中心設定部１１０，およびクラスタリング情報記憶部１１１を備える。また、クラスタリング装置Ｂ１５０は、データベースＢ１５１，第２変換部１５２，設定部１５３，第４変換部１５４，多項式通知部１５５，多項式計算部１５６，第６変換部１５７，第８変換部１５８，変換値通知部１５９，中心設定部１６０，およびクラスタリング情報記憶部１６１を備える。
【００１６】
第１変換部１０２および第２変換部１５２は、データベースＡ１０１に含まれてベクトルで表されたデータ群からなる第１クラスのデータ数と、データベースＢ１５１に含まれてベクトルで表されたデータ群からなる第２クラスのデータ数とから、これらと和が等しいａ１およびａ２を求める。
【００１７】
まず、第１変換部１０２が、上記第１クラスのデータ数より抽出したこのデータ数に関連する情報を含む第１部分情報を生成してクラスタリング装置Ｂ１５０に通知する。また、第２変換部１５２が、クラスタリング装置Ｂ１５０に配置され、第２クラスのデータ数より抽出したこのデータ数に関連する情報を含む第２部分情報を生成してクラスタリング装置Ａ１００に通知する。
【００１８】
このようにして、第１部分情報および第２部分情報を交換した後、第１変換部１０２では、第２部分情報と第１クラスのデータ数とよりａ１を求め、第２変換部１５２では、第１部分情報と第２クラスのデータ数とよりａ２を求める。上述した部分情報の交換を繰り返すことで、第１クラスのデータ数および第２クラスのデータ数との和と、ａ１およびａ２の和とが等しい状態となるａ１およびａ２が、第１変換部１０２および第２変換部１５２の各々で得られるようになる（非特許文献３参照）。
【００１９】
設定部１０３は、自然数Ｎ２を用いてｂ1,i＝ａ１×１／２i（ｉ＝２，・・・Ｎ２＋１）を求め、求めたｂ1,iを有限体上のｃ1,iに変換する。また、設定部１５３は、自然数Ｎ１を用いてｂ2,j＝ａ２×１／２j（ｊ＝２，・・・Ｎ１＋１）を求め、求めたｂ2,jを有限体上のｃ2,jに変換する。自然数Ｎ１は、クラスタリング装置Ａ１００において設定され、クラスタリング装置Ｂ１５０に通知される。また、自然数Ｎ２は、クラスタリング装置Ｂ１５０において設定され、クラスタリング装置Ａ１００に通知される。
【００２０】
第３変換部１０４および第４変換部１５４は、クラスタリング装置Ａ１００で任意に設定されたｍ１と、クラスタリング装置Ｂ１５０で任意に設定されたｍ２とから、これらと和が等しいｄ１およびｄ２を求める。
【００２１】
まず、第３変換部１０４が、設定されたｍ１より抽出したｍ１に関連する情報を含む第３部分情報を生成してクラスタリング装置Ｂ１５０に通知する。同様に、第４変換部１５４が、設定されたｍ２より抽出したｍ２に関連する情報を含む第４部分情報を生成してクラスタリング装置Ａ１００に通知する。
【００２２】
このようにして、第３部分情報および第４部分情報を交換した後、第３変換部１０４は、第４部分情報とｍ１とよりｄ１を求め、第４変換部１５４は、第３部分情報とｍ２とよりｄ２を求める。ｄ１およびｄ２を求める方法は、上述したａ１およびａ２を求める方法と同様である（非特許文献３参照）。
【００２３】
多項式通知部１０５は、以上のようにして求めたｃ1,i，ｄ１、および任意に設定した有理数からなる定数ｅ１と変数ｘとを用いて以下の式（１）で示される多項式を生成し、生成した多項式をクラスタリング装置Ｂ１５０に通知する。
【００２４】
【数２】
2011090538.tif 000004
【００２５】
同様に、多項式通知部１５５は、以上のようにして求めたｃ2,j，ｄ２、および任意に設定した有理数からなる定数ｆ１と変数ｘとを用いて以下の式（２）で示される多項式を生成し、生成した多項式をクラスタリング装置Ａ１００に通知する。
【００２６】
【数３】
2011090538.tif 000005
【００２７】
多項式計算部１０６は、多項式通知部１５５より通知された式（２）を用い、これにｄ１を代入してＲ２（ｄ１）＝ｆ２を算出する。同様に、多項式計算部１５６は、多項式通知部１０５より通知された式（１）を用い、これにｄ２を代入してＲ２（ｄ２）＝ｅ２を算出する。
【００２８】
第５変換部１０７および第６変換部１５７は、ｅ１＋ｆ１とｅ２＋ｆ２との積に和が等しいｇ１およびｇ２を求める。まず、第５変換部１０７が、ｅ１＋ｆ１より抽出したｅ１＋ｆ１に関連する情報を含む第５部分情報を生成してクラスタリング装置Ｂ１５０に通知する。同様に、第６変換部１５７が、クラスタリング装置Ｂ１５０に配置され、ｅ２＋ｆ２より抽出したｅ２＋ｆ２に関連する情報を含む第６部分情報を生成してクラスタリング装置Ａ１００に通知する。
【００２９】
このようにして、第５部分情報および第６部分情報を交換した後、第５変換部１０７は、第６部分情報とｅ１＋ｆ１とよりｇ１を求め、第６変換部１５７は、第５部分情報とｅ２＋ｆ２とよりｇ２を求める。ｇ１およびｇ２を求める方法は、上述したａ１およびａ２を求める方法と同様である（非特許文献３参照）。
【００３０】
第７変換部１０８および第８変換部１５８は、データベースＡ１０１における第１クラスのデータの座標の和と、データベースＢ１５１における第２クラスのデータの座標の和とから、これらと和が等しいｈ１およびｈ２を求める。
【００３１】
まず、第７変換部１０８は、第１クラスのデータの座標の和より抽出した第１クラスのデータの座標の和に関連する情報を含む第７部分情報を生成してクラスタリング装置Ｂ１５０に通知する。同様に、第８変換部１５８は、第２クラスのデータの座標の和より抽出した第２クラスのデータの座標の和に関連する情報を含む第８部分情報を生成してクラスタリング装置Ａ１００に通知する。
【００３２】
このようにして、第７部分情報および第８部分情報を交換した後、第７変換部１０８は、第８部分情報と第１クラスのデータの座標の和とよりｈ１を求め、第８変換部１５８は、第７部分情報と第２クラスのデータの座標の和とよりでｈ２を求める。１およびｈ２を求める方法は、上述したａ１およびａ２を求める方法と同様である（非特許文献３参照）。
【００３３】
変換値通知部１０９は、Ｍ１＝ｇ１×ｈ１×２-N2を計算し、Ｍ１をクラスタリング装置Ｂ１５０に通知する。また、変換値通知部１５９は、Ｍ２＝ｇ２×ｈ２×２-N1を計算し、Ｍ２をクラスタリング装置Ａ１００に通知する。
【００３４】
中心設定部１１０は、変換値通知部１０９が計算したＭ１と、クラスタリング装置Ｂ１５０（変換値通知部１５９）より通知されたＭ２とよりＭ１×Ｍ２を求め、求めたＭ１×Ｍ２を、第１クラスと第２クラスとを合わせた新たなクラスタの中心とする。このようにして得られたクラスタリング情報が、クラスタリング情報記憶部１１１に記憶される。
【００３５】
同様に、中心設定部１６０は、変換値通知部１５９が計算したＭ２と、クラスタリング装置Ａ１００（変換値通知部１０９）より通知されたＭ１とよりＭ１×Ｍ２を求め、求めたＭ１×Ｍ２を、第１クラスと第２クラスとを合わせた新たなクラスタの中心とする。このようにして得られたクラスタリング情報が、クラスタリング情報記憶部１６１に記憶される。
【００３６】
次に、本実施の形態における分散データのクラスタリングシステムの動作（分散データのクラスタリング方法）について図２のフローチャートを用いて説明する。
【００３７】
まず、ステップＳ２０１で、第１変換部１０２および第２変換部１５２が、データベースＡ１０１に含まれてベクトルで表されたデータ群からなる第１クラスのデータ数と、データベースＢ１５１に含まれてベクトルで表されたデータ群からなる第２クラスのデータ数とから、各クラスのデータ数を変換したデータ（変換値）としてこれらと和が等しいａ１およびａ２を求める。
【００３８】
次に、ステップＳ２０２で、設定部１０３が、クラスタリング装置Ｂ１５０より通知された自然数Ｎ２を用い、ａ１を変換したｂ1,i＝ａ１×１／２i（ｉ＝２，・・・Ｎ２＋１）を求める。また、設定部１５３が、クラスタリング装置Ａ１００より通知された自然数Ｎ１を用い、ａ２を変換したｂ2,j＝ａ２×１／２j（ｊ＝２，・・・Ｎ１＋１）を求める。
【００３９】
次に、ステップＳ２０３で、設定部１０３が、求めたｂ1,iを有限体上のｃ1,iに変換し、また、設定部１５３が、求めたｂ2,jを有限体上のｃ2,jに変換する。
【００４０】
次に、ステップＳ２０４で、第３変換部１０４および第４変換部１５４が、クラスタリング装置Ａ１００で任意に設定されたｍ１と、クラスタリング装置Ｂ１５０で任意に設定されたｍ２とから、これらと和が等しいｄ１およびｄ２を求める。
【００４１】
次に、ステップＳ２０５で、多項式通知部１０５が、上記式（１）で示される多項式を生成し、生成した多項式をクラスタリング装置Ｂ１５０に通知し、多項式通知部１５５が、上記式（２）で示される多項式を生成し、生成した多項式をクラスタリング装置Ａ１００に通知する。
【００４２】
次に、ステップＳ２０６で、多項式計算部１０６が、多項式通知部１５５より通知された式（２）を用い、Ｒ２（ｄ１）＝ｆ２を算出し、多項式計算部１５６が、多項式通知部１０５より通知された式（１）を用い、Ｒ２（ｄ２）＝ｅ２を算出する。
【００４３】
次に、ステップＳ２０７で、第５変換部１０７および第６変換部１５７が、ｅ１＋ｆ１とｅ２＋ｆ２との積に和が等しいｇ１およびｇ２を求める。
【００４４】
次に、ステップＳ２０８で、第７変換部１０８および第８変換部１５８が、データベースＡ１０１における第１クラスのデータの座標の和と、データベースＢ１５１における第２クラスのデータの座標の和とから、これらと和が等しいｈ１およびｈ２を求める。
【００４５】
次に、ステップＳ２０９で、変換値通知部１０９が、Ｍ１＝ｇ１×ｈ１×２-N2を計算し、Ｍ１をクラスタリング装置Ｂ１５０に通知し、また、変換値通知部１５９が、Ｍ２＝ｇ２×ｈ２×２-N1を計算し、Ｍ２をクラスタリング装置Ａ１００に通知する。
【００４６】
次に、ステップＳ２１０で、中心設定部１１０が、変換値通知部１０９が計算したＭ１と、クラスタリング装置Ｂ１５０（変換値通知部１５９）より通知されたＭ２とよりＭ１×Ｍ２を求め、求めたＭ１×Ｍ２を、第１クラスと第２クラスとを合わせた新たなクラスタの中心とする。このようにして得られたクラスタリング情報は、クラスタリング情報記憶部１１１に記憶する。同様に、中心設定部１６０が、変換値通知部１５９が計算したＭ２と、クラスタリング装置Ａ１００（変換値通知部１０９）より通知されたＭ１とよりＭ１×Ｍ２を求め、求めたＭ１×Ｍ２を、第１クラスと第２クラスとを合わせた新たなクラスタの中心とする。このようにして得られたクラスタリング情報は、クラスタリング情報記憶部１６１に記憶する。
【００４７】
以上に説明したように、本実施の形態によれば、各々のデータベースの情報を変換した値を用いてクラスタの中心を近似値として求めるようにしたので、ネットワーク１４０上に分散しているデータベースＡ１０１とデータベースＢ１５１を、互いのデータベースの実態が相手に知られることなくクラスタリングができるようになる。なお、各クラスタリング装置は、ＣＰＵと主記憶装置と外部記憶装置とネットワーク接続装置となどを備えたコンピュータ機器であり、主記憶装置に展開されたプログラムによりＣＰＵが動作することで、上述した各機能が実現される。また、各機能は、複数のコンピュータ機器に分散させるようにしてもよい。
【００４８】
以下、より詳細に説明する。前述したように、分散データのクラスタリングにおいては、複数のクラスタリング実行が組み合わされた攻撃に対しても、安全性が保証でき着るようにすることが重要となる。この安全性は、普遍結合的安全性と呼ばれている。
【００４９】
普遍的結合性理論の枠組みを利用し、理想的に安全なサブプロトコルを段階的に実現し、これらを合成してクラスタリングの動作手続き（プロトコル）を与える。この置き換えの正当性は、次に示す事実によるものである。普遍的結合性理論では、理想的に安全なサブシステムＳを実現するサブプロトコルＱにたいし、ＰでのＳの呼び出しをＱで置き換えたプロトコルＰ（Ｑ）も、理想的に安全であることが保証されている。
【００５０】
次に、普遍的結合性理論による本発明の分散データのクラスタリングについて説明する。このクラスタリングでは、処理の本体である分散「ｋ−ｍｅａｎ」計算があり、この計算の中に、分散平均計算を呼び出す部分がある。分散平均計算では、処理の本体の中に、「oblivious polynomial evaluation」（ＯＰＥ）計算を呼び出す部分がある。また、ＯＰＥ計算は、処理本他に加えて「share」を計算する部分がある。
【００５１】
ＯＰＥ計算は、「受信者」（例えば、クラスタリング装置Ａ１００）と、「送信者」（例えば、クラスタリング装置Ｂ１５０）と呼ばれる役割を持つ２つの「party」の間の秘密通信で、受信者は、ある値ｗを秘密に持ち、送信者は、ある多項式Ｐ（ｘ）を秘密に持ち、互いに自分の秘密に関する情報を一切漏らさずに、受信者が値Ｐ（ｗ）を入手する計算である（非特許文献４参照）。この正確な働きは、理想的ＯＰＥ計算ＦOPEとして、以下のように定められる。
【００５２】
［ＦOPE］：受信者Ａから値ｗ、送信者Ｂから多項式Ｐ（ｘ）が得られると、受信者ＡにＰ（ｗ）を与える。
【００５３】
上述した理想計算ＦOPEを実現するプロトコルとして、本発明では、以下に示すプロトコルを用いる。
【００５４】
ステップ１：送信者ＢがＰ（ｘ）＝Σmi=0ａiｘiを生成する。
【００５５】
ステップ２：受信者Ａは、準同形性「Ｅｎｃ（ａ）×Ｅｎｃ（ｂ）＝Ｅｎｃ（ａ＋ｂ）」を持つ公開鍵Ｅｎｃを使い、Ｅｎｃ（ｗ），・・・，Ｅｎｃ（ｗm）を生成し、これを送信者Ｂに送る。
【００５６】
ステップ３：送信者Ｂは、Πmi=0Ｅｎｃ（ｗi）ai＝Ｅｎｃ（Ｐ（ｗ））を計算し、受信者Ａに送信。
【００５７】
ステップ４：受信者Ａは、Ｅｎｃ（Ｐ（ｗ））を復号してＰ（ｗ）を得る。
【００５８】
次に、分散平均計算について説明する。分散平均計算は、２つの「party」Ａ，Ｂが、各々値（α，ｍ）および（β，ｎ）を秘密に持ち、自分の値に関する情報を一切与えることなく、互いに（α＋β）／（ｍ＋ｎ）の近似値（誤差内）を得る計算である。
【００５９】
ここで、（α，ｍ）のαは、「party」ＡにおけるデータベースＤａを分割して得られるベクトルで表されたデータ群からなるクラスＡのデータの座標の和であり、ｍは、データ数である。（β，ｎ）のβは、「party」ＢにおけるデータベースＤｂを分割して得られるベクトルで表されたデータ群からなるクラスＢのデータの座標の和であり、ｎは、データ数である。また、（α＋β）／（ｍ＋ｎ）は、上述した２つのクラスＡおよびクラスＢをクラスタリングするときのクラスタの中心を示すものである。従って、分散平均計算は、選択された２つのクラスＡ，クラスＢの中心座標を近似的に示すものである。
【００６０】
以下、分散平均計算の手続きＦMを実現するプロトコルπMについて説明する。このプロトコルでは、上述したＦOPEを利用する。以下では、Ａが値（α，ｍ）を持ち、Ｂが値（β，ｎ）を持つ場合の、Ａの動作を中心について説明する。なお、以下のプロトコルでは、Ｎ１およびＮ２という互いに知り得るパラメータを用いる。
【００６１】
ステップ１：自身のｎをオラクル（非特許文献３参照）に入力し、相手の入力（ｍ）との有限体上での和と等しいａ１＋ａ２のａ１を得る。
【００６２】
ステップ２：ａ１をオラクルに入力し、相手の入力（ａ１）との整数上での和と等しい
ａ’１＋ａ’２のａ’１を得る。
【００６３】
ステップ３：ｂ1,i＝ａ’１／２i（ｉ＝２，・・・、Ｎ２＋１）を計算する。
【００６４】
ステップ４：ステップＳ３で計算したｂ1,iを有限体上のｃ1,iに変換する。
【００６５】
ステップ５：任意に設定したｍ１をオラクルに入力し、相手の入力（ｍ２）との和ｍ１＋ｍ２と等しい和となるｄ１＋ｄ２のｄ１を得る。
【００６６】
ステップ６：有限体上の任意のｅ１を設定し、また、多項式Ｒ１（ｘ）＝ΣN2+1i=2 c1,iＰi（ｄ１＋ｘ）−ｅ１を設定し、前述したＦOPEにより、相手がｆ２＝Ｒ１（ｄ２）を得るようにする。ｄ２は、ステップＳ５において、相手が得ているものである。自身では、相手より多項式Ｒ２（ｘ）＝ΣN1+1i=2 c2,iＰi（ｄ２＋ｘ）−ｅ２を得て、ｆ１＝Ｒ２（ｄ１）を得る。
【００６７】
ステップ７：ｅ１＋ｆ１，ｅ２＋ｆ２の積と和が等しくなるｇ１およびｇ２［（ｅ１＋ｆ１）×（ｅ２＋ｆ２）＝ｇ１＋ｇ２］を、各々がオラクルより得る。
【００６８】
ステップ８：自身のαをオラクルに入力し、相手の入力（β）との有限体上での和と等しいｈ１＋ｈ２のｈ１を得る。
【００６９】
ステップ９：Ｍ１＝ｇ１×ｈ１×２-N2を計算して相手に送る。（相手は、Ｍ２＝ｇ２×ｈ２×２-N1を計算して送ってくる。）
【００７０】
ステップ１０：Ｍ１×Ｍ２を計算する。これが、（α＋β）／（ｍ＋ｎ）の近似値となる。
【００７１】
次に、処理の本体である、基本的な分散「ｋ−ｍｅａｎ」計算について説明する。「ｋ−ｍｅａｎ」計算は、２つの「party」Ａ，Ｂが、各々のデータベースＤａ，Ｄｂより、自身のデータの情報を相手に知らせることなく、クラスタリングを行い出力を共有する計算である。なお、以下では、Ｄ＝Ｄａ∪Ｄｂとする。
【００７２】
ステップ１：Ｄから任意の個数のデータを任意に選び、クラスタの仮の中心とする。
【００７３】
ステップ２：距離計算により、Ｄの各データに対して一番近い中心を対応させ、Ｄのデータをクラスタリングする。
【００７４】
ステップ３：ステップ２で計算したクラスタ毎に中心を計算し直す。
【００７５】
ステップ４：各クラスタの新しく計算した中心と、直前の中心との距離が、設定されている閾値以下となったら、計算した中心をクラスタの中心とし、閾値を超えている場合は、ステップ２に戻る。
【００７６】
次に、前述した分散平均計算の手続きＦMを利用して、上述した「ｋ−ｍｅａｎ」の手続きを実現するプロトコルπKMについて、説明する。
【００７７】
ステップ１：自身のデータを以下の計算で標準化する。
Ｄａ＝｛ｄA1，・・・，ｄAn1｝とし、Ｋ１＝（Σn1i=1ｄAi）／ｎ１としたとき、（ｎ１，Σn1i=1（ｄAi−Ｋ１）2）を用い、プロトコルπMを用いて処理し、得られた近似値から、σ＝√［１／（ｎ１＋ｎ２）｛Σn1i=1（ｄAi−Ｋ１）2＋Σn2i=1（ｄBi−Ｋ１）2｝］を計算し、Ｄａ内のデータ間の距離を全て１／σ倍する。
なお、このデータ標準化は、以降のステップの処理をより円滑に行うためにしてお小物であり、行う必要はない。
【００７８】
ステップ２：データベースから任意の個数のデータρA1，・・・，ρAkを選択し、相手に送る。また、相手より受け取った同様のデータをもとに、仮の中心として、Ｃｌ1＝ρA1＋ρB1，・・・・，Ｃｌk＝ρAk＋ρBkを計算する。
【００７９】
ステップ３：計算したＣｌ1，・・・，Ｃｌkを中心として、データベースの各データ（要素）の距離を計算し直す。
【００８０】
ステップ４：プロトコルπM（分散平均計算の手続きＦM）により、新しい中心Ｃｌ’1，・・・，Ｃｌ’kを求める。
【００８１】
ステップ５：｜Ｃｌ1−Ｃｌ’1｜＜閾値，・・・，｜Ｃｌk−Ｃｌ’k｜＜閾値なら終了し、｜Ｃｌ1−Ｃｌ’1｜≧閾値，・・・，｜Ｃｌk−Ｃｌ’k｜≧閾値なら、Ｃｌ1＝Ｃｌ’1，・・・，Ｃｌk＝Ｃｌ’kとしてステップ３に戻る。
【００８２】
上述した本発明の分散クラスタリングにより、例えば、複数インスタンスの同時実行による攻撃など、より強力な攻撃に対しても、秘密が保持された状態で安全にクラスタリングができるようになる。本発明により、各々の実データを公開することなく、インターネットなどの広域網上にある膨大なデータの傾向の把握，自分のデータの位置づけに関する情報の把握，および情報検索などなどが、個人情報を完全に保護した状態で行えるようになる。
【符号の説明】
【００８３】
１００…クラスタリング装置Ａ、１０１…データベースＡ、１０２…第１変換部、１０３…設定部、１０４…第３変換部、１０５…多項式通知部、１０６…多項式計算部、１０７…第５変換部、１０８…第７変換部、１０９…変換値通知部、１１０…中心設定部、１１１…クラスタリング情報記憶部、１５０…クラスタリング装置Ｂ、１５１…データベースＢ、１５２…第２変換部、１５３…設定部、１５４…第４変換部、１５５…多項式通知部、１５６…多項式計算部、１５７…第６変換部、１５８…第８変換部、１５９…変換値通知部、１６０…中心設定部、１６１…クラスタリング情報記憶部。
【図１】
2011090538.tif 000012
【図２】
2011090538.tif 000013