(57)【特許請求の範囲】
【請求項１】
ネットワークを介して接続されたクライアント端末と、分類器を含むサーバとの間で行われるコンピュータによるデータ分類方法であって、
前記クライアント端末により、分類されるべきデータベクトルｘを生成するステップと、
前記サーバにより、起こり得るクラスの各々に対して１つの多変量ガウス分布がある、一組の多変量ガウス分布を用いて分類器を定義するステップと、
各多変量ガウス分布及び前記データベクトルｘに対し、内積手続きを適用し、各適用に対して前記クライアント端末に対するベクトルａｉ及び前記サーバに対するベクトルｂｉを生成するステップと、
各ベクトルｂｉ及び前記データベクトルｘに対し、前記内積手続きを適用し、前記クライアント端末に対するスカラーｒｉ及び前記サーバに対するスカラーｑｉを生成するステップと、
要素の合計されたベクトル［（ａ１ｘ＋ｑ１＋ｒ１），…，（ａＮｘ＋ｑＮ＋ｒＮ）］を形成するステップと、
最大値を有する特定の要素に対し前記データベクトルｘのクラスである前記合計されたベクトルのインデックスを確定するステップと
を含む、コンピュータによるデータ分類方法。
【請求項２】
前記内積手続きは、安全な暗号化プロトコルである、請求項１に記載のコンピュータによるデータ分類方法。
【請求項３】
前記内積手続きは、安全な代数プロトコルである、請求項１に記載のコンピュータによるデータ分類方法。
【請求項４】
前記分類器は、Ｎ個のクラスに対し、ｉ＝１，２，…，Ｎに対する行列Ｗｉであり、クラスｉに対する前記ガウス分布のパラメータを記述する該行列Ｗｉは、Ｗｊｉが該行列Ｗｉのｊ番目の列である場合、［Ｗ１ｉＷ２ｉ…Ｗｄ＋１ｉ］である、請求項１に記載のコンピュータによるデータ分類方法。
【請求項５】
前記インデックスは安全に確定される、請求項１に記載のコンピュータによるデータ分類方法。
【請求項６】
起こり得る各クラスｉに対し多変量ガウス分布の混合があり、Ｊｉがｉ番目の混合におけるガウス分布の数である場合、ｉ＝１，２，…，Ｎ及びｊ＝１，２，…，Ｊｉに対し、各多変量ガウス分布Ｗｉｊは、混合重みαｉｊ及び事前確率Ｐ（ωｉ）に関連付けられる、請求項１に記載のコンピュータによるデータ分類方法。
【請求項７】
ネットワークを介して接続されたクライアント端末と、分類器を含むサーバとの間で行われ、前記クライアント端末によって生成されるベクトルｘを前記サーバによって提供される分類器を用いて分類し、前記分類器は一組の多変量ガウス分布として定義され、Ｎ個のクラスの各々に対して１つの多変量ガウス分布があり、前記分類器は、ｉ＝１，２，…，Ｎに対する行列Ｗｉとして表され、該行列Ｗｉは、Ｗｊｉが該行列Ｗｉのｊ番目の列である場合、［Ｗ１ｉＷ２ｉ…Ｗｄ＋１ｉ］として表される、コンピュータによる分類方法であって、
安全な内積手続きＳＩＰ（ｘ，Ｗｊｉ）及び安全な内積手続きＳＩＰ（ｂｉ，ｘ）を実行し、安全な内積手続きＳＩＰ（ｘ，Ｗｊｉ）により、ｉ＝１，２，…，Ｎに対して、且つｊ＝１，…，ｄ＋１に対して、前記クライアント端末に対するベクトルａｉ＝［ａ１ｉ…ａｄ＋１ｉ］及びベクトルａｉｘ並びに前記サーバに対するベクトルｂｉ＝［ｂ１ｉ…ｂｄ＋１ｉ］を取得するとともに、安全な内積手続きＳＩＰ（ｂｉ，ｘ）により、前記クライアント端末に対するスカラーｑｉ及び前記サーバに対するスカラーｒｉを取得する第１のステップと、
前記クライアント端末によりベクトルＡ＝［（ａ１ｘ＋ｑ１）…（ａＮｘ＋ｑＮ）］を構成し、前記サーバによりベクトルＢ＝［ｒ１…ｒＮ］を構成する第２のステップと、
安全な最大インデックスプロトコルＳＭＡＸ（Ａ，Ｂ）を実行して、前記クライアント端末が前記データベクトルｘに関連するクラスＩを取得する第３のステップと
を含む、コンピュータによる分類方法。
【請求項８】
前記分類器は、ｉ＝１，２，…，Ｎ及びＪ＝１，２，…，Ｊｉに対し、行列Ｗｉｊ、混合重みαｉｊ及び事前確率Ｐ（ωｉ）として定義され、
（１）ｉ＝１，２，…，Ｎに対し
（ａ）Ｊｉ多変量ガウス分布に対して請求項７に記載の前記第１及び第２のステップを実行し、Ａｉｊ＋Ｂ’ｉｊ＝ｌｉｊ（ｘ）であるように、前記クライアント端末に対するベクトル
【数１】
0004828355.tif 000054
及び前記サーバに対するベクトル
【数２】
0004828355.tif 000055
を取得するステップと、
（ｂ）前記サーバにより、Ｂｉｊ＝Ｂ’ｉｊ＋ｌｎαｉｊである場合に、ベクトル
【数３】
0004828355.tif 000056
を構成するステップと、
（ｃ）安全な最大インデックスプロトコルＳＭＡＸ（Ａｉ，Ｂｉ）を実行し、前記クライアント端末及び前記サーバがインデックスＫｉを取得するステップと、
（ｄ）前記クライアント端末によりベクトル
【数４】
0004828355.tif 000057
を構成し、前記サーバによりベクトル
【数５】
0004828355.tif 000058
を構成するステップと、
（ｅ）前記安全な内積
【数６】
0004828355.tif 000059
を実行し、前記サーバのためにφｉを取得するステップと、
（２）前記サーバにより、
【数７】
0004828355.tif 000060
である場合にベクトルｕ＝［ｕ１…ｕＮ］を構成するとともに、前記クライアント端末により、
【数８】
0004828355.tif 000061
である場合にベクトルｖ＝［ｖ１…ｖＮ］を構成するステップと、
（３）前記安全な最大インデックスプロトコルＳＭＡＸ（ｕ，ｖ）を実行し、前記クライアント端末が前記データベクトルｘに関連する前記クラスＩを取得するステップ
をさらに含む、請求項７に記載のコンピュータによる分類方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはデータを分類することに関し、特にデータを安全に(securely)分類することに関する。
【背景技術】
【０００２】
グローバル通信ネットワークが利用可能であることにより、今では、多くの理由によりデータ処理タスクを第三者に「アウトソースする」ことが一般的である。たとえば、コストを下げて処理を行うことができたり、あるいは第三者の方が優れた計算資源及び／又は優れた技術を有する。データ処理をアウトソースする１つの問題は、第三者によって機密情報が不適切に使用されるということである。
【０００３】
データ処理資源が限られていることの多いユーザ又はクライアントは、データを分類したいと望む。第三者又はサーバは、必要な資源のうちのいくつかを有する。データを第三者に明らかにすることなく分類させることが望まれる。同時に、第三者は、その分類器を秘密のままにしたいと望む。こうした用途に対し、従来の暗号法は、移送中のデータのみを保護し、第三者による処理は保護しない。
【０００４】
特定の適用例では、クライアント、アリスはデータベクトルを有する。サーバ、ボブは、ガウス分布を使用する分類器を有する。ボブの分類器を使用して、アリスのデータベクトルを分類することができる。アリス及びボブは、ボブに対してデータベクトルを明らかにすることなく且つアリスに対して分類器を明らかにすることなく、ボブに対してアリスのデータを分類させるプロトコルを採用したいと考える。
【０００５】
安全なマルチパーティ計算は、正確さ、安全性及びオーバヘッドに関して分析されることが多い。正確さは、安全なプロセスが理想的な解にどれほど近づくかを評価する。安全性は、マルチパーティ交換から得られる情報の量を評価する。オーバヘッドは、複雑性及び効率の尺度である。
【０００６】
アリスとボブとの間の２パーティプロトコルは、アリス及びボブの両方に対してプライバシ及び正確さが保証される場合に安全である。そのプロトコルは、分散された計算によって「漏洩する」情報が、計算での指定された出力から学習することができる情報に限られる場合に、プライバシを保護する。半誠実な（semi-honest）場合、両当事者は指示されるようにプロトコルに従うが、すべてのメッセージを記録し、後にプロトコル出力からだけでは導出することができない情報を推論することが可能である。しかしながら、悪意のある場合、両当事者の挙動に関していかなる想定もなされない。一方の当事者のプライバシはもう一方の当事者の任意の挙動に関しても保護されることが必要である。半誠実な場合のプロトコルを、両当事者がそのプロトコルに従うというゼロ知識証明を添付した場合に、悪意のある場合において安全にすることができる。
【０００７】
ゼロ知識プロトコル
ゼロ知識プロトコル又は安全なマルチパーティプロトコルは、最初、特定の問題に対して、Yao著「How to generate and exchange secrets」（Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp.162-167, 1986）に記載された。後に、そのゼロ知識技法は他の問題にも拡張された。これについては、Goldreich他著「How to play any mental game - a completeness theorem for protocols with honest majority」（19th ACM Symposium on the Theory of Computing, pp 218-229, 1987）を参照されたい。しかしながら、それら理論的構成は依然として、実際的な適用に役立つためには非常に要求が厳しいものである。
【０００８】
それ以降、多くの安全な方法が述べられてきた。これについては、Chang他著「Oblivious Polynomial Evaluation and Oblivious Neural Learning」（Advances in Cryptology, Asiacrypt '01, Lecture Notes in Computer Science Vol.2248, pages 369-384, 2001）、Clifton他著「Tools of Privacy Preserving Distributed Data Mining」（SIGKDD Explorations, 4(2):28-34, 2002）、Koller他著「Protected Interactive 3D Graphics Via Remote Rendering」（SIGGRAPH 2004）、Lindell他著「Privacy preserving data mining」（Advances in Cryptology- Crypto 2000, LNCS 1880, 2000）、Naor他著「Oblivious Polynomial Evaluation」（Proc. of the 31st Symp. on Theory of Computer Science (STOC), pp.245-254, May 1999）及びDu他著「Privacy-preserving cooperative scientific computations」（4th IEEE Computer Security Foundations Workshop, pp.273-282, June 11, 2001）を参照されたい。問題の処置全体については参照文献、Goldreich著「Foundations of Cryptography」（Cambridge University Press, 1998）に記載されている。これらはすべて参照により本明細書に援用される。
【０００９】
安全な内積（inner dot product：ドット積）
多数のコンピュータによる方法及びアプリケーションでは、内積を計算する必要がある。したがって、安全な内積（secure inner dot product）（ＳＩＰ）を確定するプロトコル及び手続きが開発されてきた。これらのプロトコルは当業者には既知であることが理解される。
【００１０】
プロトコルを、広く、暗号化プロトコルと代数プロトコルとに類別することができる。これらのプロトコルは、異なるレベルの安全性及び効率を提供する。一般に、計算コストは常に低減しているため、プロトコルを評価する際の主な問題は安全性及び通信コストである。
【００１１】
一般に、２つのベクトルｘ及びｙの内積は、ｔが転置演算子である場合ｘｔｙ＝ａ＋ｂにより２つのスカラー値ａ及びｂをもたらす。
【００１２】
暗号化プロトコル
安全な内積を提供するいくつかの方法が既知である。これについては、Goethals他著「On private scalar product computation for privacy-preserving data mining」（C.Park及びS.Chee編、Intl.Conference on Information Security and Cryptology, Vol.2506 of Lecture Notes in Computer Science, pp.104-120, 2004）、Feigenbaum他著「Secure multiparty computation of approximations」（Proceedings of the Intl. Colloquium on Automata, Languages and Programming, Vol.2076 of Lecture Notes in Computer Science, pp.927-938, 2001）及びCanetti他著「Selective private function evaluation with applications to private statistics」（Proceedings of the ACM symposium on principles of distributed computing, pp.293-304, 2001）を参照されたい。これらはすべて参照により本明細書に援用される。
【００１３】
Goethal他のプロトコルでは、ボブ及びアリスのそれぞれに属する秘密ベクトルｘ及びｙを入力とし、ａ＋ｂ＝ｘｔｙであるようなスカラー値ａ及びｂを出力とする。初期化段階の間、ボブは、秘密鍵及び公開鍵の対（ｓｋ，ｐｋ）を生成する。ボブはｐｋをアリスに送信する。そして、各ｉ∈｛１，…，ｄ｝に対し、ボブは、新たなランダム文字列ｒｉを生成し、ｃｉ＝Ｅｎ（ｐｋ；ｘｉ，ｒｉ）をアリスに送信する。これに応答して、アリスは、
【００１４】
【数１】
0004828355.tif 000002
【００１５】
を設定し、ランダムな平文ｂ及びランダムなノンスｒ’を生成し、ｚ’＝ｚ・Ｅｎ（ｐｋ；−ｂ，ｒ’）をボブに送信する。そして、ボブは、ａ＝Ｄｅ（ｓｋ；ｚ’）＝ｘｔｙ−ｂを確定する。Goethals他は、プロトコルが正しく且つ安全であるという証拠を述べている。ｋ’が、アリスによって送信される各暗号化メッセージのビットサイズであり、大きいｍに対して
【００１６】
【数２】
0004828355.tif 000003
【００１７】
である場合、通信オーバヘッドはｋ’／τであることも示すことができる。準同型暗号システムでは、一般的な値はｋ’≒２０４８及びｍ≒２１０２４となる。これについては、Paillier著「Public-key cryptosystems based on composite degree residuosity classes」（J.Stern編、Proceedings of Advances in Cryptology- EUROCRYPT '99, Vol.1592 of Lecture Notes in Computer Science, pp.223-238, 1999）及びDamgard他著「A generalization, simplification and some applications of Paillier's probabilistic public-key system」（Proceedings of the Intl. Workshop on Practice and Theory in Public Key Cryptography, Vol.1992 of Lecture Notes in Computer Science, pp.119-136, 2001）を参照されたい。これらはすべて参照により本明細書に援用される。
【００１８】
別のプロトコルは、紛失多項式評価（oblivious polynomial evaluation）（ＯＰＥ）の技法を使用する。これについては、参照により本明細書に援用される、Naor他著、「Oblivious transfer and polynomial evaluation」（Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp.245-254, 1999）を参照されたい。このプロトコルは、ドット積ｘｔｙのすべての項ｘｊｙｊを計算しｊ番目の項を
【００１９】
【数３】
0004828355.tif 000004
【００２０】
として表す加法オラクル（additive oracle）を使用する。アリス及びボブは、すべてのｊに対してそれぞれ
【００２１】
【数４】
0004828355.tif 000005
【００２２】
及び
【００２３】
【数５】
0004828355.tif 000006
【００２４】
を受け取る。結果ｘｔｙは、
【００２５】
【数６】
0004828355.tif 000007
【００２６】
によって与えられる。アリス及びボブは、ＯＰＥを使用して加法オラクルを実行することができる。
【００２７】
Canetti他は、データベースから一組の数の重み付き和を確定する準同型暗号化を使用するプロトコルについて述べている。Feigenbaum他は、２つのベクトル間のＬ２距離を確定するプロトコルについて述べている。これについては、Feigenbaum他著「Secure multiparty computation of approximations」（Proceedings of the Intl. Colloquium on Automata, Languages and Programming, Vol.2076 of Lecture Notes in Computer Science, pages 927-938, 2001）を参照されたい。これらはすべて参照により本明細書に援用される。それらのプロトコルの両方を使用して、ドット積を安全に確定することができる。
【００２８】
代数プロトコル
安全なドット積を確定するために、代数プロトコルを使用することも可能である。しかしながら、これらのプロトコルの大部分は何らかの情報を漏らす。これについては、Du他著「Privacy-preserving cooperative statistical analysis」（Proceedings of the 17th Annual Computer Security Applications Conference, December 2001）、Du他著「A practical approach to solve secure multi-party computation problems」（Proceedings of New Security Paradigms Workshop, September 23-26 2002）、Ioannidis他著「A secure protocol for computing dot-products in clustered and distributed environments」（Proceedings of the Intl. Conf. on Parallel Processing, 2002）、Ravikumar他著「A secure protocol for computing string distance metrics」（Proceedings of the Workshop on Privacy and Security Aspects of Data Mining, pages 40-46, Brighton, UK, 2004）及びVaidya他著「Privacy preserving association rule mining in vertically partitioned data」（Proceedings of the Intl. Conf. on Knowledge Discovery and Data Mining）を参照されたい。これらのプロトコルのうちのいくつかの特性及び弱点は分析されている。これについては、Kiltz他著「Secure computation of the mean an related statistics」（Proceedings of the Theory of Cryptography Conference, Vol.3378 of Lecture Notes in Computer Science, pages 283-302, 2005）及びGoethals他著「On private scalar product computation for privacy-preserving data mining」（C.Park及びS.Chee編、Intl, Conference on Information Security and Cryptology, Vol.2506 of Lecture Notes in Computer Science, pp.104-120, 2004）を参照されたい。これらはすべて、参照により本明細書に援用される。
【００２９】
Du他のプロトコルにおける基本的な考え方は、ベクトルｘをＭ個のランダムベクトルの和、すなわち
【００３０】
【数７】
0004828355.tif 000008
【００３１】
として表すということである。すべてのｍに対し、アリスは、ｋ個のランダムベクトルの組に隠されるｕｍを送信する。ボブは、ベクトルのすべてに対してｙを用いてドット積を計算し、すべての積に対して乱数ｒｍを加算する。その結果はアリスに送信される。アリス及びボブは、これをＭ回繰り返す。最後に、アリス及びボブは、それぞれ
【００３２】
【数８】
0004828355.tif 000009
【００３３】
及び
【００３４】
【数９】
0004828355.tif 000010
【００３５】
を有し、それらは加算された時に必要な結果を与える。
【００３６】
Du他は、ランダム順列を使用する。π（ｘ）を、要素がｘの要素のランダム順列であるベクトルとする。積π（ｘ）ｔπ（ｙ）は、ｘｔｙに等しい。ボブは、ｙをＭ個のランダムベクトルの和、すなわち
【００３７】
【数１０】
0004828355.tif 000011
【００３８】
として表す。ボブは、ｍ個のランダムベクトルｒｉ及びｍ個のランダム順列πｍを生成する。各ｍに対し、アリスは、πｍ及びｒｍを学習することなくπｍ（ｘ＋ｒｍ）を学習する。Du他におけるような準同型暗号化方式を使用して、ボブは、πｍ（ｖｍ）をアリスに送信し、アリスはπｍ（ｘ＋ｒｍ）ｔπ（ｖｍ）を計算する。最後に、アリスは
【００３９】
【数１１】
0004828355.tif 000012
【００４０】
を有し、ボブは
【００４１】
【数１２】
0004828355.tif 000013
【００４２】
を有し、それらは合せて結果を形成する。ｙにおけるすべての要素を正しく推測するアリスの可能性は
【００４３】
【数１３】
0004828355.tif 000014
【００４４】
である。
【００４５】
別のプロトコルは、データベクトルｘにおける要素の数ｄが一様であると仮定する。ベクトルｘ１は、ベクトルｘの前半のｄ／２個の要素を含むｄ／２次元ベクトルとして定義され、ベクトルｘ２は、ｘの後半のｄ／２個の要素を含み、ｘｔｙ＝ｘｔ１ｙ１＋ｘｔ２ｙ２であるとする。アリス及びボブは、共同で、ランダムな可逆ｄ×ｄ行列Ｍを生成する。アリスは、ｘ’１及びｘ’２に分割されるｘ’＝ｘｔＭを計算し、ｘ’２をボブに送信する。ボブは、ｙ’＝Ｍ−１ｙを計算し、それをｙ’１及びｙ’２に分割し、ｙ’１をアリスに送信する。アリスはｘ’１ｙ’１を計算し、ボブはｘ’２ｙ’２を計算し、それにより、それらの和が必要とされる結果となる。
【００４６】
ドット積を計算する他の代数プロトコルも既知である。これについては、Ioannidis他著「A secure protocol for computing dot-products in clustered and distributed environments」（Proceedings of the Intl. Conf. on Parallel Processing, 2002）、Vaidya他著「Privacy preserving association rule mining in vertically partitioned data」（Proceedings of the Intl. Conf. on Knowledge Discovery and Data Mining, 2002）及びRavikumar他著「A secure protocol for computing string distance metrics」（Proceedings of the Workshop on Privacy and Security Aspects of Data Mining, pp.40-46, 2004）を参照されたい。これらはすべて参照により本明細書に援用される。
【００４７】
分類器
データ分類は既知である。データが多変量分布を有する場合、分類器は、通常、多変量ガウス分布を使用する。各クラスを、単一多変量ガウス分布によってモデル化してもよく、又は多変量ガウス分布の混合によってモデル化してもよい。
【００４８】
分類器は、すべてのクラスωｉに対して識別関数
【００４９】
【数１４】
0004828355.tif 000015
【００５０】
の値を確定し、すべてのｊ≠ｉに対しｇｉ（ｘ）＞ｇｊ（ｘ）である場合、データｘをクラスωｉに割り当てる。ここで、ｐ（ｘ｜ωｉ）はクラス条件付き確率密度関数であり、ｐ（ωｉ）はクラスωｉの事前確率である。
【００５１】
単一多変量ガウス分布
ｉ番目のクラスの平均ベクトル及び共分散行列は、それぞれμｉ及びΣｉである。ここで、
【００５２】
【数１５】
0004828355.tif 000016
【００５３】
であり、上記式を、
【００５４】
【数１６】
0004828355.tif 000017
【００５５】
と表すことができる。
【００５６】
項（ｄ／２）ｌｎ２πを無視すると、式（１）は、
【００５７】
【数１７】
0004828355.tif 000018
【００５８】
である場合、
【００５９】
【数１８】
0004828355.tif 000019
【００６０】
と書き直すことができる。
【００６１】
（ｄ＋１）次元のベクトル
【００６２】
【数１９】
0004828355.tif 000020
【００６３】
及びｗｉを、ベクトルｘに値１を付加し、ベクトル
【００６４】
【数２０】
0004828355.tif 000021
【００６５】
に要素ｗｉ０を付加することによって生成することができる。行列
【００６６】
【数２１】
0004828355.tif 000022
【００６７】
を、最後の行の最初のｄ個の成分が０であり最後の列がｗｔｉに等しい（ｄ＋１）×（ｄ＋１）行列Ｗｉに変換することにより、式（２）を
【００６８】
【数２２】
0004828355.tif 000023
【００６９】
と書くことができる。
【００７０】
【数２３】
0004828355.tif 000024
【００７１】
をｘとして表すと、式は
【００７２】
【数２４】
0004828355.tif 000025
【００７３】
となる。
【００７４】
ガウス分布の混合
クラスωｉにおけるｊ番目のガウス分布の平均ベクトル及び共分散行列は、それぞれμｉｊ及びΣｉｊである。ここで、Ｊｉがクラスωｉを記述するガウス分布の数、αｉｊがガウス分布の混合の係数であるとすると、
【００７５】
【数２５】
0004828355.tif 000026
【００７６】
となる。
【００７７】
ｉ番目のクラスのｊ番目のガウス分布に対する対数尤度は、
【００７８】
【数２６】
0004828355.tif 000027
【００７９】
である場合、
【００８０】
【数２７】
0004828355.tif 000028
【００８１】
によって与えられる。
【００８２】
上述したようにｘを（ｄ＋１）次元ベクトルとして表し、
【００８３】
【数２８】
0004828355.tif 000029
【００８４】
を合せて（ｄ＋１）×（ｄ＋１）行列Ｗｉｊとして表すことにより、式（４）は
【００８５】
【数２９】
0004828355.tif 000030
【００８６】
となる。
【００８７】
ここで、ｉ番目のクラスの識別関数は、
【００８８】
【数３０】
0004828355.tif 000031
【００８９】
及び
【００９０】
【数３１】
0004828355.tif 000032
【００９１】
である場合、
【００９２】
【数３２】
0004828355.tif 000033
【００９３】
と書くことができる。
【００９４】
以下、データベクトルｘは、特に記述のない限り、最後の成分が１に等しい（ｄ＋１）次元ベクトルを示す。
【発明の開示】
【発明が解決しようとする課題】
【００９５】
本発明は、コンピュータによりデータを安全に分類する方法を提供することを目的とする。
【課題を解決するための手段】
【００９６】
本発明は、データを安全に分類する方法を提供する。第１の当事者は、分類されるべきデータベクトルｘを有する。第２の当事者は、一組の多変量ガウス分布として定義される分類器を有する。起こり得る各クラスに対して１つの多変量ガウス分布がある。
【００９７】
各多変量ガウス分布及びデータベクトルｘに対して安全な内積手続きを適用することにより、各適用に対し第１の当事者に対するベクトルａｉ及び第２の当事者に対するベクトルｂｉを生成する。その後、安全な内積を各ベクトルｂｉ及びデータベクトルｘに適用することにより、各適用に対し第１の当事者に対するスカラーｒｉ及び第２の当事者に対するスカラーｑｉを生成する。
【００９８】
要素の合計されたベクトル［（ａ１ｘ＋ｑ１＋ｒ１）…（ａＮｘ＋ｑＮ＋ｒＮ）］を形成し、最大値を有する特定の要素に対する合計されたベクトルのインデックスＩが、データベクトルｘのクラスである。
【発明の効果】
【００９９】
本発明は、コンピュータによりデータを安全に分類する方法を提供することができる。
【発明を実施するための最良の形態】
【０１００】
図１は、本発明の一実施の形態によるデータを分類する安全な方法１００を示す。アリス、すなわちクライアント１１０は、ベクトルｘ１１１の形式のデータを有する。ボブ、すなわちサーバ１２０は、多変量ガウス分布を使用する分類器Ｗｉ１２１を有する。図１に示す本発明のこの実施の形態では、各データクラスに対して１つの多変量ガウス分布がある。図２に示す別の実施の形態では、分類器は、各クラスに対し多変量ガウス分布の混合に関する。
【０１０１】
単一多変量ガウス分布
分類器１２１は、ｉ＝１，２，…，Ｎに対して行列Ｗｉの形式になる。ここでは、Ｗｊｉが行列Ｗｉのｊ番目の列である場合、行列Ｗｉを［Ｗ１ｉＷ２ｉ…Ｗｄ＋１ｉ］として表す。
【０１０２】
本発明の一実施の形態は、安全な内積（ＳＩＰ）手続き１３０を使用する。ＳＩＰのステップは、上述したように、一部はアリス１１０によって実行され、一部はボブ１２０によって実行される。ＳＩＰは、ベクトルｘ１１１及びガウス分布Ｗｉ１２１を入力とする。分類器Ｗｉ１２１のすべての列ＷｊｉへのＳＩＰ手続き１３０の各適用に対し、一対のスカラー値ａｊ及びｂｊが生成される。すべてのｉに対し、アリスは、スカラー値ａｊのすべてをベクトルａｉ＝［ａ１…ａｄ＋１］１１２として取得し、ａｉｘ１０５を確定し、ボブは、スカラー値ｂｊのすべてをベクトルｂｉ＝［ｂ１…ｂｄ＋１］１２２として取得する。
【０１０３】
そして、データベクトルｘ１１１及びベクトルｂｉ１２２に対して再びＳＩＰ１３０を適用する。これにより、スカラー値ｑｉ１１３及びｒｉ１２３がそれぞれ生成される。
【０１０４】
アリスは、合計１１５を用いてベクトルＡ＝［（ａ１ｘ＋ｑ１）…（ａＮｘ＋ｑＮ）］１１４を構成し、ボブは、ベクトルＢ＝［ｒ１…ｒＮ］１２４を構成する。
【０１０５】
そして、アリス及びボブは、ベクトルＡ及びＢに対して安全な最大プロトコル（ＳＭＡＸ手続き）１４０を実行し、アリスは、データベクトルｘ１１１の分類Ｉ１０１であるＳＭＡＸ（Ａ，Ｂ）を取得する。
【０１０６】
正確さ
ベクトルａｉ及びｂｉは、ａｉ＋ｂｉ＝ｘｔＷｉであるような値である。また、ｂｉｘ＝ｑｉ＋ｒｉである。ここで、ｘｔＷｉｘは、ａｉｘ＋ｑｉ＋ｒｉによって与えられる。値Ｉは、ｘｔＷｉｘが最大であるインデックスｉの値に等しい。
【０１０７】
効率
所与のｉ＝Ｉに対し、上記プロトコルは（ｄ＋２）回のＳＩＰコールを有する。ここで、プロトコルは、ＳＩＰ手続き１３０に対してＮ（ｄ＋２）回のコールを必要とし、ＳＭＡＸに対して１回のコールを必要とする。
【０１０８】
安全性
アリスもボブもいかなるドット積の完全な結果も学習しない。このため、ＳＩＰ及びＳＭＡＸに対するプロトコルが安全である場合、プロトコル全体は安全である。
【０１０９】
多変量ガウス分布の混合
図２は、ガウス分布の混合を用いてデータを分類する方法２００を示す。この方法では、ＳＩＰ手続き１３０に対して３回のコールと、ＳＭＡＸ手続き１４０に対して２回のコールとがある。
【０１１０】
上述したように、アリス(クライアント)２１０はデータベクトルｘ１１１を有する。ボブ(サーバ)２２０は今、分類器２２１を有する。図２に示す実施の形態では、分類器２２１は、各クラスに対し、ｉ＝１，２，…，Ｎ及びｊ＝１，２，…Ｊｉに対して、ガウス分布の混合ｗｉｊ、混合重みαｉｊ及び事前確率Ｐ（ωｉ）を含む。アリスは、出力として、すべてのｊ≠Ｉに対してｇＩ（ｘ）＞ｇｊ（ｘ）であるようなクラスＩ１０１を取得する。
【０１１１】
方法２００は以下のステップを実行する。ベクトル１１１と、ｉ番目の混合における各ガウス分布２２１Ｗｉｊとに対してＳＩＰ手続き１３０を適用することにより、中間分類インデックスＫｉ２０１を取得し、その後、上述したように導出される各対Ａｉ２１４及びＢｉ２２４に対してＳＭＡＸ手続きを適用する。
【０１１２】
ベクトル２１４は
【０１１３】
【数３３】
0004828355.tif 000034
【０１１４】
であり、ベクトル２２４は
【０１１５】
【数３４】
0004828355.tif 000035
【０１１６】
であることが留意されるべきである。
【０１１７】
ボブによる中間ステップでは、スカラー値ｒｉ１２３からベクトル
【０１１８】
【数３５】
0004828355.tif 000036
【０１１９】
を構成し、ｌが、上記式（５）及び（６）で使用したような対数尤度である場合、Ｂｉｊ＝Ｂ’ｉｊ＋ｌｎαｉｊであり、そのためＡｉｊ＋Ｂ’ｉｊ＝ｌｉｊ（ｘ）となる。
【０１２０】
アリス及びボブは、インデックスＫｉ２０１を使用して、行列Ａｉ２１４及びＢｉ２２４からそれぞれ要素
【０１２１】
【数３６】
0004828355.tif 000037
【０１２２】
及び
【０１２３】
【数３７】
0004828355.tif 000038
【０１２４】
を選択する。アリスは、すべての要素
【０１２５】
【数３８】
0004828355.tif 000039
【０１２６】
からベクトルＵ２０５を構成する。
【０１２７】
アリス及びボブは、それぞれ中間ベクトル
【０１２８】
【数３９】
0004828355.tif 000040
【０１２９】
及び
【０１３０】
【数４０】
0004828355.tif 000041
【０１３１】
を確定し、これらのベクトルを指数として使用することによりベクトル
【０１３２】
【数４１】
0004828355.tif 000042
【０１３３】
を形成する。
【０１３４】
ベクトル
【０１３５】
【数４２】
0004828355.tif 000043
【０１３６】
にＳＩＰ手続き１３０を適用する。結果はφｉである。
【０１３７】
ボブは、
【０１３８】
【数４３】
0004828355.tif 000044
【０１３９】
である場合、ベクトル２０６、すなわちＶ＝［ｖ１…ｖＮ］を構成する。アリスは、上述したように、
【０１４０】
【数４４】
0004828355.tif 000045
【０１４１】
である場合、ベクトル２０５、すなわちＵ＝［ｕ１…ｕＮ］を構成する。ベクトルＵ２０５及びＶ２０６にＳＭＡＸ手続き１４０を適用し、アリスはクラスＩ１０１を取得する。
【０１４２】
正確さ
上記プロトコルによれば、ｕｉ＋ｖｉ＝ｇｉ（ｘ）である。式（６）を参照されたい。
【０１４３】
効率
所与のｉに対し、ＳＩＰ手続き１３０に対して（Ｊｉ（ｄ＋２）＋１）回のコールがあり、ＳＭＡＸ手続き１４０に対して２回のコールがある。
【０１４４】
安全性
アリス及びボブは、ベクトルＡｉ＋Ｂｉの最大値のインデックスを取得する。これは、ボブに対してベクトルｘに関する何らかの情報を漏らすように見える可能性がある。実際には、ボブは、ベクトルＡｉ＋Ｂ’ｉの最大値のインデックスを知っている場合、ｘが混合のいずれのガウスにあるかを知る。ボブは、すべてのクラスからのこの情報を使用して、データベクトルｘの分布に関して学習することができる。しかしながら、ボブは、すべての要素にｌｎαｉｊを加算した後にしかインデックスを学習しない。したがって、ボブが学習するインデックスは、Ａｉ＋Ｂ’ｉの最大値のインデックスとは異なる可能性がある。ボブがインデックスを学習する可能性をなくすために、以下の代替プロトコルを提供する。
【０１４５】
安全な最大値を用いる多変量ガウス分布の混合
図３は、ガウス分布の混合を用いてデータベクトルを分類する方法３００を示す。この方法では、後述するように、ＳＩＰ手続き１３０に対して３回のコールがあり、ＳＭＡＸ手続き１４０に対して１回のコールがあり、ＳＶＡＬ手続き３１０に対して１回のコールがある。
【０１４６】
このプロトコルは、上述したようにボブが最大値のインデックスを学習する可能性を無くす。このプロトコルは、図２のプロトコルに類似する。
【０１４７】
このプロトコルでは、アリス及びボブは、直接
【０１４８】
【数４５】
0004828355.tif 000046
【０１４９】
を使用する代りに中間値ｙｉ３１１及びｚｉ３１２を使用する。このため、プロトコル３００を以下のように表すことができる。
【０１５０】
入力
上述したように、アリスはデータベクトルｘ１１１を有し、ボブは、ｉ＝１，２，…，Ｎ及びｊ＝１，２，…Ｊｉに対して分類器Ｗｉｊ２２１、混合重みαｉｊ及び事前確率Ｐ（ωｉ）を有する。
【０１５１】
出力
アリスは、すべてのｊ≠Ｉに対しｇＩ（ｘ）＞ｇｊ（ｘ）であるようなＩ１０１を学習する。ボブは、データベクトルｘに関して何も学習しない。
１．ｉ＝１，２，…，Ｎに対して
（ａ）アリス及びボブは、ｉ番目の混合におけるＪｊガウスに対し上述したようなステップを実行することにより、ベクトル
【０１５２】
【数４６】
0004828355.tif 000047
【０１５３】
を取得する。なお、Ａｉｊ＋Ｂ’ｉｊ＝ｌｉｊ（ｘ）であることに留意されたい。
（ｂ）ボブは、Ｂｉｊ＝Ｂ’ｉｊ＋ｌｎαｉｊである場合に、ベクトル
【０１５４】
【数４７】
0004828355.tif 000048
【０１５５】
を構成する。
（ｃ）アリス及びボブは、ベクトルＡｉ２１４及びＢｉ２２４を用いて安全な最大値ＳＶＡＬプロトコル(ＳＶＡＬ手続き)３１０を採用することにより、中間ｙｉ３１１及びｚｉ３１２を取得する。すなわち、ｙｉ＋ｚｉ＝ＳＶＡＬ（Ａｉ，Ｂｉ）である。
（ｄ）アリス及びボブは、それぞれ
【０１５６】
【数４８】
0004828355.tif 000049
【０１５７】
を確定する。
（ｅ）アリス及びボブは、ＳＩＰ１３０を使用してベクトル
【０１５８】
【数４９】
0004828355.tif 000050
【０１５９】
との間のドット積を確定し、ボブは、ドット積の結果φｉ２５５を取得する。
２．ボブは、ｖｉ＝ｚｉ＋ｌｎψｉ＋ｌｎＰ（ωｉ）である場合にベクトルＶ＝［ｖ１，…，ｖＮ］を確定する。アリスは、ｕｉ＝ｙｉである場合にベクトルＵ＝［ｕ１，…，ｕＮ］を確定する。
３．アリス及びボブは、ベクトルＵ２０５とＶ２０６との間の安全な最大インデックスプロトコル(ＳＭＡＸ手続き)１４０を実行し、アリスはクラスＩ１０１を取得する。
【０１６０】
正確さ
上記プロトコルによれば、ｕｉ＋ｖｉ＝ｇｉ（ｘ）である。式（６）を参照されたい。
【０１６１】
効率
所与のｉに対し、（Ｊｉ（ｄ＋２）＋１）回のＳＩＰコールがあり、１回のＳＶＡＬコールがあり、１回のＳＭＡＸコールがある。
【０１６２】
安全性
ＳＩＰ、ＳＶＡＬ及びＳＭＡＸが安全である場合、上記プロトコルは安全である。
【０１６３】
安全な最大インデックス（ＳＭＡＸ）
概して、ＳＭＡＸ手続き１４０は、ベクトルｘ＝［ｘ１，…，ｘｄ］且つベクトルｙ＝［ｙ１，…，ｙｄ］である場合、ｄ要素ベクトル
［（ｘ１＋ｙ１），…，（ｘｄ＋ｙｄ）］＝ｘ＋ｙ
のうちの一つの要素に対するインデックスを確定する。たとえば、第５の要素が最大値を有する要素、すなわち（ｘ５＋ｙ５）である場合、インデックス５が生成される。同様の手続きを使用して最小インデックスを確定することができる。
【０１６４】
本発明による手続きは、Du他により、「Privacy-preserving cooperative stanalysis」（Proceedings of the 17th Annual Computer Security, December 2001）において述べられている手続きの新規な拡張である。
【０１６５】
ボブは、ｚｉ≦ｚｊである場合且つその場合にのみｆ’（ｚｉ）≦ｆ’（ｚｊ）であるような、２つの変数ｆ（ｘ，ｙ）＝ｆ’（ｘ＋ｙ）においてランダム多項式を生成する。各ｉ＝１，２，…，ｄに対し、アリスは、紛失多項式評価（ＯＰＥ）を使用して、ｈｉ（ｘ）＝ｆ（ｘ，ｙｉ）である場合、ｈｉ（ｘｉ）を確定する。ｈｉ（ｘｉ）が最大であるインデックスが、アリスが求める回答である。なお、いずれの当事者も最大要素の値を確定することができないが、アリスは、ベクトルｘ＋ｙにおける要素の順序を確定することができる、ということに留意されたい。
【０１６６】
安全な最大値プロトコル（ＳＶＡＬ）
アリスはベクトルｘ＝［ｘ１，…，ｘｄ］を有し、ボブはベクトルｙ＝［ｙ１，…，ｙｄ］を有する。アリス及びボブは、ｚ＝ｘ＋ｙにおける最大要素の値を確定したいと考える。プロトコルの後、いずれの当事者も最大要素のインデックスを知るべきではない。なお、同じプロトコルを使用して最小値の値を計算することができることに留意されたい。
【０１６７】
まず、単純な（naive）な手法を考える。なお、
【０１６８】
【数５０】
0004828355.tif 000051
【０１６９】
であることに留意されたい。アリス及びボブは、こうした対の比較を行い任意の従来の最大発見プロセスをまねることにより、最大の値を学習することができる。比較を安全に実行するために、アリス及びボブはYaoのミリオネーヤー(millionaire)プロトコルを使用してもよい。これについては、Yao著「Protocols for secure computation」（Proc. of the 23rd IEEE Symposium on Foundations of Computer Science, pp.160-164, 1982）を参照されたい。
【０１７０】
しかしながら、アリス及びボブは、その単純な手法に従う場合、ともに最大のインデックスを見つけることもできる。改良では、アリス及びボブは、合計がｚのランダム順列である２つのベクトルを取得する。アリスもボブも順列を知らない。そして、アリス及びボブは、それらの新たに取得されたベクトルに対しての上記単純な手法に従うことにより、最大要素の加法シェア（additive share）を確定することができる。
【０１７１】
順列生成プロトコル
入力
アリス及びボブは、それぞれｄ成分ベクトルｘ及びｙを有する。ボブはランダム順列πを有する。
【０１７２】
出力
アリス及びボブは、ｑ＋ｓ＝π（ｘ）＋π（ｙ）であるようなｑ及びｓを取得する。
１．アリスは、準同型暗号化のための公開鍵及び秘密鍵を生成し、その公開鍵をボブに送信する。Ｅ（・）はアリスの公開鍵を用いた暗号化を示す。
２．アリスは、ベクトルｘの各要素を暗号化し、結果としてのベクトル
【０１７３】
【数５１】
0004828355.tif 000052
【０１７４】
をボブに送信する。
３．ボブは、ランダムベクトルｒを生成し、ｉ＝１，…，ｄに対し
【０１７５】
【数５２】
0004828355.tif 000053
【０１７６】
である、新たなベクトルθを計算する。
４．ボブはθの順列を作成し、π（θ）をアリスに送信する。アリスはベクトルを解読してｑを取得する。
５．ボブはｙ−ｒを計算した後、πを用いてその順列を作成し、ｓ＝π（ｙ−ｒ）を取得する。
【０１７７】
アリス及びボブは、上記順列作成プロトコルを２回採用し、２回目ではそれらの役割を交換する。これを行った後、アリス及びボブは、和が元の和のランダム順列である２つのベクトルを有するが、それらはいずれも順列が何であるかを知らない。そして、それらは、その単純な最大発見手法に従って、最大要素の加法シェアを計算する。
【図面の簡単な説明】
【０１７８】
【図１】本発明の一実施の形態による多変量ガウス分布を用いてデータを分類する安全な方法を示すブロック図である。
【図２】本発明の一実施の形態による多変量ガウス分布の混合を用いてデータを分類する安全な方法を示すブロック図である。
【図３】本発明の一実施の形態による多変量ガウス分布の混合を用いてデータを分類する安全な方法を示すブロック図である。
【図１】
0004828355.tif 000062
【図２】
0004828355.tif 000063
【図３】
0004828355.tif 000064