(57)【要約】アリスのプライベートデータｘをボブの分類器Ｈ(ｘ)で安全に分類。分類器は、    【数１】2009511937.tif 000058(αｎ、βｎ、θｎはスカラー値、ｙｎは分類器のベクトル格納パラメータ)であり、ボブは    【数２】2009511937.tif 000059のようにＮ個の乱数ｓ１，…，ｓＮセットを生成し、各ｎ＝１，…，Ｎに関し、ｘＴｙｎに対し安全なドット積を適用しアリスに対しａｎ、ボブに対してｂｎを取得する工程、安全なmillionaireプロトコルを適用しａｎとθｎ−ｂｎの大小を判断しかつαｎ＋ｓｎ又はβｎ＋ｓｎの結果を返す工程、アリスにより結果をｃｎに累積する工程が実行され、さらに安全なmillionaireプロトコルを適用し    【数３】2009511937.tif 000060より大きいことを判断し、真なら正の符号、偽なら負の符号を返し、プライベートデータｘを分類する。
2009511937.tif 000002
【特許請求の範囲】
【請求項１】
第１のパーティのプライベートデータを第２のパーティの分類器Ｈ(ｘ)を使用して安全に分類する方法であって、
(１)第１のパーティのプライベートデータをベクトルｘとして提供し、第２のパーティによって分類器
【数１】
2009511937.tif 000036
(ここで
【数２】
2009511937.tif 000037
であり、式中、αｎ、βｎ及びθｎはスカラー値であり、ｙｎは前記分類器のベクトル格納パラメータである)
を提供し、そして、前記第２のパーティによって、
【数３】
2009511937.tif 000038
であるように、Ｎ個の乱数ｓ１，…，ｓＮのセットを生成するステップと、
(２)各ｎ＝１，…，Ｎに対し、
(ａ)ｘＴｙｎに対して安全なドット積を適用して前記第１のパーティに対しａｎを取得し、前記第２のパーティに対してｂｎを取得するサブステップと、
(ｂ)安全なmillionaireプロトコルを適用してａｎがθｎ−ｂｎより大きいか否かを判断するとともに、αｎ＋ｓｎ又はβｎ＋ｓｎの結果を返すサブステップと、
(ｃ)前記第１のパーティによって前記結果をｃｎに累積するサブステップと
を実行するステップと、
(３)前記安全なmillionaireプロトコルを適用して
【数４】
2009511937.tif 000039
が
【数５】
2009511937.tif 000040
より大きいか否かを判断するとともに、真である場合に正の符号を返し偽である場合に負の符号を返して前記プライベートデータｘを分類するステップと、
を含む、プライベートデータを安全に分類する方法。
【請求項２】
Ｈ(ｘ)は、弱分類器ｈ(ｘ)の線形結合である強分類器である、請求項１に記載のプライベートデータを安全に分類する方法。
【請求項３】
第１のパーティのプライベートデータを第２のパーティの分類器Ｈ(ｘ)を使用して安全に分類する方法であって、
(１)第１のパーティのプライベートデータをベクトルｘとして提供し、第２のパーティによって分類器
【数６】
2009511937.tif 000041
(ここで
【数７】
2009511937.tif 000042
であり、式中、ｃ及びｄはスカラー値であり、ｙｎは前記分類器のベクトル格納パラメータである)
を提供し、そして、前記第２のパーティによって、
【数８】
2009511937.tif 000043
であるように、Ｎ個の乱数ｓ１，…，ｓＮのセットを生成するステップと、
(２)各ｎ＝１，…，Ｎに対し、
(ａ)ｘＴｙｎに対して安全なドット積を適用して前記第１のパーティに対しａｎを取得し、前記第２のパーティに対してｂｎを取得するサブステップと、
(ｂ)前記第２のパーティによって、多項式
【数９】
2009511937.tif 000044
を構成するサブステップと、
(ｃ)ｆｎ(ａ)に対し紛失多項式評価を適用するサブステップと
を実行するステップと、
(３)前記第１のパーティによって、
【数１０】
2009511937.tif 000045
を確定するステップと、
(４)安全なmillionaireプロトコルを適用してｒがｓより大きいか否かを判断するとともに、真である場合に正の符号を返し偽である場合に負の符号を返して前記プライベートデータｘを分類するステップと、
を含む、プライベートデータを安全に分類する方法。
【請求項４】
第１のパーティのプライベートデータを第２のパーティの分類器Ｈ(ｘ)を使用して安全に分類する方法であって、
(１)第１のパーティのプライベートデータをベクトルｘとして提供し、第２のパーティによって分類器
【数１１】
2009511937.tif 000046
(ここで
【数１２】
2009511937.tif 000047
であり、ｙは前記分類器のベクトル格納パラメータである)
を提供し、そして、前記第２のパーティによって
【数１３】
2009511937.tif 000048
であるように、Ｎ個の乱数ｓ１，…，ｓＮのセットを生成するステップと、
(２)各ｎ＝１，…，Ｎに対し、
(ａ)前記第２のパーティによって乱数ｓＢを選択するとともに、関数ｆ(ｚ)＝γｚ−ｓＢ(ｚはスカラーである)を構成するサブステップと、
(ｂ)紛失多項式評価を適用して前記第１のパーティに対してシェアｓＡ(ここでｓＡ＝ｆ(ｘＴｘ)は安全なドット積である)を取得するサブステップと、
(ｃ)ｘＴ(−２γｙｎ)に対して前記安全なドット積を適用して、前記第１のパーティに対しシェアｒＡを取得し、前記第２のパーティに対してシェアｒＢを取得するサブステップと、
(ｄ)前記第１のパーティによってｔＡ＝ｅｘｐ(ｓＡ)ｅｘｐ(ｒＡ)を構成するサブステップと、
(ｅ)前記第２のパーティによってｔＢ＝ｅｘｐ(ｓＢ)ｅｘｐ(ｒＢ)ｅｘｐ(γｙｎＴｙｎ)を構成するサブステップと、
(ｆ)
【数１４】
2009511937.tif 000049
に対し前記安全なドット積を適用して、前記第１のパーティに対しａｎを取得し、前記第２のパーティに対してｂｎを取得するサブステップと、
を実行するステップと、
(３)前記第１のパーティに対し累算
【数１５】
2009511937.tif 000050
を確定し、前記第２のパーティに対し累算
【数１６】
2009511937.tif 000051
を確定するステップと、
(４)安全なmillionaireプロトコルを適用して、ａがｂより大きいか否かを判断し、真である場合は正の符号を返し、偽である場合は負の符号を返して前記プライベートデータｘを分類するステップと、
を含む、プライベートデータを安全に分類する方法。
【請求項５】
第１のパーティのプライベートデータを第２のパーティの分類器Ｈ(ｘ)を使用して安全に分類する方法であって、
(１)第１のパーティのプライベートデータをベクトルｘとして提供するとともに、第２のパーティによって分類器
【数１７】
2009511937.tif 000052
(ここで、ｈｎ(ｘＴｙｎ)＝１／(１＋ｅｘｐ(ｘＴｙｎ))であり、ｙｎは前記分類器のベクトル格納パラメータである)
を提供するステップと、
(２)各ｎ＝１，…，Ｎに対し、
(ａ)ｘＴｙｎに対して安全なドット積を適用して、前記第１のパーティに対しプライベートシェアａｎを取得し、前記第２のパーティに対してプライベートシェアｂｎを取得するサブステップと、
(ｂ)ｓＡ＋ｓＢ＝ｅｘｐ(ａ)ｅｘｐ(ｂ)に対して前記安全なドット積を適用して、前記第１のパーティに対してｓＡを取得し前記第２のパーティに対してｓＢを取得するサブステップと、
(ｃ)前記第２のパーティによって乱数ｒＢを選択するとともに、ｆ(ｓＡ)＝ｒＢ＋ｒＢ(ｓＡ＋ｓＢ)＝ｒＢ(１＋ｅｘｐ(ｘＴｙｎ))を定義するサブステップと、
(ｄ)紛失多項式評価を適用して、前記第１のパーティに対してｒＡ＝ｆ(ｓＡ)を取得するサブステップと、
(ｅ)
【数１８】
2009511937.tif 000053
に対して前記安全なドット積を適用して、前記第１のパーティに対してｔＡ，ｎを取得し前記第２のパーティに対してｔＢ，ｎを取得するサブステップと
を実行するステップと、
(３)前記第１のパーティによって
【数１９】
2009511937.tif 000054
を確定し、前記第２のパーティによって
【数２０】
2009511937.tif 000055
を確定するステップと、
(４)安全なmillionaireプロトコルを適用し、ｔＡが−ｔＢより大きいか否かを判断し、真である場合は正の符号を返し、偽である場合は負の符号を返して前記プライベートデータｘを分類するステップと、
を含む、プライベートデータを安全に分類する方法。
【請求項６】
第１のパーティのプライベートデータを安全に分類する方法であって、
(１)プライベートデータベクトルｘ、第１のパーティの半径ｒのプライベートシェアｒＡ、並びに第２のパーティの点ｙｉ及び前記半径ｒのプライベートシェアｒＢを提供するステップと、
(２)前記第１のパーティ及び前記第２のパーティによって、各点ｙｉに対し、
(ａ)前記第１のパーティ及び前記第２のパーティによって、前記ドット積(−２ｘ)Ｔｙのプライベートシェアａ及びｂをそれぞれ取得するサブステップと、
(ｂ)前記第２のパーティによって、ｓＢ＝ｂ＋ｙＴｙ及び関数ｆ(ｚ)＝ｚ＋ｓＢ(ｚはスカラーである)を定義するサブステップと、
(ｃ)紛失多項式評価を適用してｓＡ＝ｆ(ｘＴｘ＋ａ)(ｓＡは前記第１のパーティのプライベートシェアである)を評価するサブステップと、
(ｄ)前記第２のパーティによって乱数ｕｉを選択するサブステップと、
(ｅ)millionaireプロトコルを使用してｓＡ−ｒＡとｒＢ−ｓＢとを比較するとともに、ｓＡ−ｒＡ＜ｒＢ−ｓＢ且つｃ(ｙｉ)＝１である場合、ｕｉ＋１を返し、そうでない場合、前記第２のパーティはｕｉを返し、前記第１のパーティは結果をｖｉに格納するサブステップと
を実行するステップと、
(３)前記第１のパーティ及び前記第２のパーティによって、それぞれ
【数２１】
2009511937.tif 000056
及び
【数２２】
2009511937.tif 000057
を確定するステップと、
(４)前記millionaireプロトコルを使用してｖとｕ＋ｋ／２とを比較して、ｖ＞ｕ＋ｋ／２である場合、ｘは１としてラベル付けされ、そうでない場合、０としてラベル付けされるステップと、
を含む、プライベートデータを安全に分類する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には協調コンピューティングに関し、詳細には、暗号化技法を使用してプライベート情報を分類することにより安全な方法で協調コンピューティングを実行することに関する。
【背景技術】
【０００２】
インターネットは、協調コンピューティングに対する機会を提供する。協調コンピューティングでは、ユーザ及びプロバイダは、商品、サービス及び情報を交換することができる。インターネットはまた、データ又は信号を分類するために使用することができる分類器に対するアクセスも提供することができる。
【０００３】
一般に、データ分類は当該技術分野において既知である。特に重要なのは２値分類器である。こうした分類器は、単に、特定のデータが特定のクラスに属するか否かを示すように「はい」又は「いいえ」の回答を与える。
【０００４】
特に、２値分類は、オブジェクトを、それらが何らかの所定の特性を有するか否かに基づいて２つのグループに分類するタスクである。典型的な２値分類タスクには、画像における顔認識、臨床データの医療検査及び製品の品質制御が含まれる。一般に、コンピュータ実装分類器は、分類システムを自動的に「学習する」。２値分類器を学習するために適した既知の方法には、決定木、ベイズネットワーク、サポートベクトルマシン(ＳＶＭ)及びニューラルネットワークが含まれる。
【０００５】
プライベート情報分類器(private information classification)(ＰＩＣ)は、２つのパーティ、たとえばアリス及びボブが、アリスが、ボブに対して何も(分類結果さえも)明らかにすることなく且つ分類要求に対する回答以外、ボブの分類器に関して何も学習することなく、ボブの分類器を使用してデータを分類することができるようにするプロトコルに、関与することができるようにする。ＰＩＣは、機械学習の分野と、暗号化技術の下位分野である協調マルチパーティコンピューティングの分野とを一緒にする。
【０００６】
安全なマルチパーティ計算は、Yao著「How to generate and exchange secrets」(27th FOCS, pp.162-167, 1986)に記載されている。これは、一般的な２パーティ問題に対するソリューションを与えた。具体的な例として、既知の「millionaire問題」を考える。２つのパーティは、どちらがより大きい数を有しているかを、数に関して他に何も自身で明らかにすることなく見つけることを望む。
【０００７】
Goldriech他は、ソリューションをｎ＞２パーティまで拡張した。それらパーティのうちの誰かは、不正行為をしている可能性がある。これについては、O. Goldreich、S. Micali及びA. Wigderson著「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)を参照されたい。
【０００８】
しかしながら、オリジナルの理論的構造は、実際に使用されるためには要求が多すぎた。暗号化技術の概説は、B. Schneierにより、Applied Cryptography(1996)に記載されており、より進歩的且つ理論的な処理は、O. Goldreichにより、Foundations of Cryptography(2004)に記載されている。
【０００９】
それ以来、さまざまなアプリケーションに対し多くの安全なプロトコルが記述されてきた。本発明に関連するのは、安全なドット積(secure dot-product)及び紛失多項式評価(oblivious polynomial evaluation)、決定木学習並びにプライベート情報検索(private information retrieval)(ＰＩＲ)である。これについては、Y.C. Chang及びC.J. Lu著「Oblivious polynomial evaluation and oblivious neural learning」(AsiaCrypt: Advances in Cryptology. LNCS, Springer-Verlag, 2001)、B. Chor、O. Goldreich、E. Kushilevitz及びM. Sudan著「Private Information Retrieval」(FOCS, 1995)、Y. Lindell及びB. Pinkas著「Privacy preserving data mining」(Advances in Cryptology - Crypto2000, LNCS 1880, 2000)並びにM. Naor及びB. Pinkas著「Oblivious Polynomial Evaluation」(Proc. of the 31st Sympt. on Theory of Computer Science (STOC), pp.245-254, May 1-4, 1999)を参照されたい。
【００１０】
安全なドット積では、アリス及びボブは、互いに結果以外は何も明らかにすることなく、自身のプライベートデータベクトルのドット積をそれぞれ確定する。ドット積プロトコルの変形によっては、アリスは、ドット積とボブしか知らない何らかの乱数との和を取得するが、ボブは何も学習しない。これは、より複雑なプロトコルに対する基礎単位としての役割を果たす。
【００１１】
紛失多項式評価(ＯＰＥ)では、ボブは多項式Ｐ(ｘ)を有し、アリスは特定の値ｘを有する。アリスは、ボブに値ｘを知らしめることなく、値ｘにおいて多項式を評価する。ボブは、多項式を明らかにすることなくそれを行う。
【００１２】
ＯＰＥは、また、２つのパーティによってトレーニングデータが保持される決定木を学習するためにも使用されてきた。パーティは、自身のプライベートデータを互いに明らかにすることなく決定木を共同で学習するように望む。最後に、各パーティは、結合データを使用してトレーニングされた決定木を学習するが、一方のパーティのプライベートデータは他方のパーティに明らかにされない。
【００１３】
ＰＩＣは、プライベート情報検索(ＰＩＲ)の拡張である。ＰＩＲでは、アリスは、ボブのデータベースからデータ項目を、ボブに対してアリスがいずれの要素を選択したかを知らしめることなく検索することに関心がある。たとえば、ボブは、株価のデータベースを有し、アリスは、特定の株の価格を、ボブに対しアリスがいずれの株を選択したかを知らしめることなく取得したいと考える。ボブは、アリスがそうすることをいとわない。しかしながら、ボブは、アリスがただ１つの株価にしかアクセスできないことを確実にしたい。
【００１４】
ＰＩＲによって要求される通信資源及び計算資源を低減する多数の方法が知られている。これについては、A. Beimel、Y. Ishai、E. Kushilevitz及びJ.-F. Raymond著「Breaking the 0(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval」(FOCS, 2002)並びにE. Kushilevitz及びR. Ostrovsky著「Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval」(FOCS 1997)を参照されたい。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明は、第１のパーティのプライベートデータｘを第２のパーティの分類器Ｈ(ｘ)を使用して安全に分類する方法を提供する。
【課題を解決するための手段】
【００１６】
分類器は
【数１】
2009511937.tif 000003
であり、ここで
【数２】
2009511937.tif 000004
であり、式中、αｎ、βｎ及びθｎはスカラー値であり、ｙｎは分類器のベクトル格納パラメータである。第２のパーティによって、
【数３】
2009511937.tif 000005
であるように、Ｎ個の乱数ｓ１，…，ｓＮのセットを生成する。各ｎ＝１，…，Ｎに対し、第１のパーティに対しａｎを取得し、第２のパーティに対してｂｎを取得するように、ｘＴｙｎに対して安全なドット積を適用するサブステップと、ａｎがθｎ−ｂｎより大きいか否かを判断するように安全なmillionaireプロトコルを適用するとともに、αｎ＋ｓｎ又はβｎ＋ｓｎの結果を返すサブステップと、第１のパーティによって結果をｃｎに累積するサブステップとが実行される。
【００１７】
そして、
【数４】
2009511937.tif 000006
が
【数５】
2009511937.tif 000007
より大きいか否かを判断するように安全なmillionaireプロトコルが適用され、真である場合に正の符号を返し偽である場合に負の符号を返してプライベートデータｘを分類する。
【発明を実施するための最良の形態】
【００１８】
第１のパーティ、たとえばアリスは、プライベートデータベクトルｘを有し、第２のパーティ、たとえばボブは、関数Ｈ(ｘ)の形式でトレーニングされた「強」分類器を有する。通常、強分類器は、弱分類器ｈｎ(ｘ)の線形結合である。これについては、参照により本明細書に援用される、Y. Freund及びR.E. Schapire著「A short introduction to boosting」(Journal of Japanese Society for Artificial Intelligence, 14(5), pp.771-780, September 1999)を参照されたい。
【００１９】
アリス及びボブは、ボブがアリスのデータベクトルｘを分類することができるようにする安全なプロトコルに関与したいと望む。特に、両パーティは、暗号化ツールを使用して、以下の分類関数を評価する。
【００２０】
【数６】
2009511937.tif 000008
【００２１】
ここで、ベクトルｘ∈ＦＬであり、ベクトル
【００２２】
【数７】
2009511937.tif 000009
【００２３】
であり、ｙｎ∈ＦＬは、有限体Ｆに対するＬ次元ベクトルである。当該技術分野において既知であるように、表記ｘＴｙｎはドット積である。
【００２４】
ベクトルｙｎは、分類関数のパラメータを格納する。ボブは、データ認識、特に画像における顔認識又は音声信号における音声認識等、特定の分類タスクに対して分類器をトレーニングする従来のメカニズムを使用して、パラメータｙｎを「学習する」。データをいかに分類するか、及び、さまざまなタスクに対して分類器をいかにトレーニングするかは既知である。
【００２５】
アリスはプライベートデータｘを有し、ボブはパラメータ(Ｎ、ｈｎ()及びｙｎ)を有する。最終的に、アリスはｓｉｇｎ(Ｈ(ｘ))を学習するがほかは何も学習せず、ボブはアリスのプライベートデータベクトルｘに関して何も学習しない。
【００２６】
特に、ここでは、分類関数ｈ(ｘＴｙ)の以下の形式を安全な方法でいかに評価するかについて述べる。
【００２７】
閾値分類関数
【００２８】
【数８】
2009511937.tif 000010
【００２９】
ここで、α、β及びθはトレーニング中にボブによって学習されるスカラー値、たとえば１及び０である。
【００３０】
多項式分類関数ｈ(ｘＴｙ)＝(ｘＴｙ＋ｃ)ｄ、ここで、ｃ及びｄはボブのみが知るスカラー値である。
【００３１】
ガウス分類関数
【００３２】
【数９】
2009511937.tif 000011
【００３３】
ここで、γはボブのみが知るスカラー値である。
【００３４】
シグモイド分類関数ｈ(ｘＴｙ)＝１／(１＋ｅｘｐ(ｘＴｙ))。
【００３５】
なお、ガウス関数及びシグモイド関数は、多項式関数と近似させることができることに留意する。ここで、ガウス関数及びシグモイド関数を直接いかに安全に評価するかについて述べる。さらに、安全なｋ−ｎｎ分類器をいかに構成するかについて述べる。
【００３６】
まず、予備的な表記及びいくつかの既知のサブプロトコルについて述べ、その後、本発明の実施の形態によるさまざまな安全な分類器Ｈについて述べる。
【００３７】
紛失多項式評価プロトコル
ここでは、既知の紛失多項式評価(ＯＰＥ)プロトコルを使用する。これについては、参照により本明細書に援用される、Y.C. Chang及びC.J. Lu著「Oblivious polynomial evaluation and oblivious neural learning」(AsiaCrypt: Advances in Cryptology. LNCS, Springer-Verlag, 2001)、並びに、参照により本明細書に援用される、M. Naor及びB. Pinkas著「Oblivious Polynomial Evaluation」(Proc. of the 31st Symp. on Theory of Computer Science (STOC), pp.245-254, May 1-4, 1999)を参照されたい。
【００３８】
紛失通信(Oblivious Transfer)プロトコル
紛失通信(ＯＴ)によってアリスは、ボブが保持する要素のデータベースから１つの要素を、ボブに対していずれの要素が選択されたかを明らかにすることなく、且つデータベースの他の要素に関して何も学習することなく選択することができる。紛失通信プロトコルは、Even他によりRabinの「紛失通信」の一般化として記述された。これについては、参照により本明細書に援用される、S. Even、O. Goldreich及びA. Lempel著「A Randomized Protocol for Signing Contracts」(Communications of the ACM 28, pp.637-647, 1985)、並びに、参照により本明細書に援用される、M.O. Rabin著「How to exchange secrets by oblivious transfer」(Tech. Memo TR-81, Aiken Computation Laboratory, 1981)を参照されたい。
【００３９】
たとえば、ボブは、プライベート要素Ｍ０及びＭ１を有し、アリスは、それら要素のうちの１つを、ボブに対しアリスがいずれの要素を選択したかを知らしめることなく選択することを望む。ボブは、アリスが他の要素に関して何も学習しないのであれば、アリスがそうすることをいとわない。ＲＳＡ暗号化に基づく以下のプロトコルを使用して、この問題を解決することができる。
１．ボブはアリスに、２つの異なる公開暗号化鍵Ｋ０及びＫ１を送信する。
２．アリスは秘密鍵Ｋを生成し、自身の秘密鍵Ｋを、ボブの公開暗号化鍵Ｋ０又はＫ１のいずれかを用いて暗号化する。この例では、アリスはボブの公開鍵Ｋ０を使用する。アリスはボブにＥ(Ｋ，Ｋ０)を送信する。ここでＥ(Ｋ，Ｋ０)は、ボブの公開鍵によるアリスの秘密鍵の暗号化を示す。
３．ボブは、アリスが自身の秘密鍵を暗号化するためにいずれの公開鍵を使用したかを知らない。したがって、ボブは、Ｅ(Ｋ，Ｋ０)を自身の秘密鍵の両方を用いて解読する。このため、ボブは、正しい鍵Ｋ及び間違った鍵Ｋ’をともに取得する。
４．ボブはアリスに、暗号化Ｅ(Ｍ０，Ｋ)及びＥ(Ｍ１，Ｋ’)を送信する。アリスは、これらメッセージのうちの最初のものを自身の秘密鍵Ｋで解読し、Ｍ０を取得する。
【００４０】
安全なドット積プロトコル
既知のドット積プロトコルの詳細について説明する前に、直観的な概略を提供する。目的は、ドット積演算ｘＴｙの結果を２つのシェア(share)ａ及びｂに分割することであり、ここでシェアａはアリスのみに既知であり、シェアｂはボブのみに既知である。
【００４１】
ドット積は、ｘＴｙ＝ａ＋ｂを保持する。ここではこれを、要素のすべての対の積ｘｉ×ｙｉを２つのシェアａｉ及びｂｉに分割し、その後、アリス及びボブに対し、ドット積のシェアを取得するようにそれぞれベクトルａ及びｂを合計させることによって行う。以下でそのプロトコルを説明する。
【００４２】
入力：アリスはベクトルｘを有し、ボブはベクトルｙを有する。
【００４３】
出力：アリス及びボブは、ａ＋ｂ＝ｘＴｙであるようなシェアａ及びｂを有する。
１．ボブはランダムベクトルｂ∈ＦＬを生成する。
２．各ｉ＝１，…，Ｌに対し、アリス及びボブは以下のサブステップを実行する。
(ａ)ボブは、ａｉ＝ｘｉ×ｙｉ−ｂｉであるように、要素ｘｉのあり得るすべての値に対し、｜Ｆ｜次元ベクトルａを構成する。
(ｂ)アリスは、インデックスとしてのｘｉとともにＯＴ１｜Ｆ｜を使用して、ベクトルａから要素を選択する。アリスは結果をａｉに格納する。
３．アリス及びボブは、それぞれ自身のプライベートベクトルａ及びｂを合計して、ドット積ｘＴｙのシェアａ及びｂを取得する。
【００４４】
安全なmillionaireプロトコル
アリス及びボブは、いずれがより大きい数を有するかを、自身の数に関して他に何も明らかにすることなく確定したいと考える。これについては、参照により本明細書に援用される、A.C. Yao著「How to generate and exchange secrets」(27th FOCS, pp.162-167, 1986)を参照されたい。Millionaire(ミリオネーヤ)プロトコルは、ＯＴプロトコルを使用する。この概念は、アリス及びボブに、自身の数をバイナリ形式で表させ、２進数を１度に１ビットずつ、最上位ビットから最下位ビットまでスキャンさせ、その後結果を得させることである。
【００４５】
各ビットに対し、ボブは、自身の現ビット値及びアリスの２つのあり得るビット値に基づくルックアップテーブルを用意する。アリスはＯＴ１２を使用して何らかの中間結果を取得し、アリス及びボブはともに次のビットに続く。
【００４６】
millionaire問題を解決するために、ここでは、以下の３つの状態のうちの１つをとることができる状態変数ｓを使用する。
１−アリスの方が大きい数を有する、
２−ボブの方が大きい数を有する、又は
３−未決定。
【００４７】
各ビットに対し、ボブは、ｓの３つの状態とアリスの数の次のビットの２つのあり得る値とを含む６分割(six-way)ルックアップテーブルを構成する。出力は、現ビットを評価した後の次の状態である。
【００４８】
たとえば、ｓ＝１(アリスの方が大きい数を有する)であり、ボブの現ビットが１であり、アリスの現ビットが０である場合、アリスの方が大きい数を有するため出力状態はｓ＝１であり、アリス及びボブは次のビットに移動する。
【００４９】
アリスが状態ｓを解明しないように、ボブは、各ビットに対して異なる順列を使用することができる。たとえば、第１のビットに対し、ｓ＝１は、アリスの方が大きい数を有することを意味するが、第２のビットに対し、ｓ＝１は、ボブの方が大きい数を有することを意味してもよい。詳細は後述する。
【００５０】
入力：アリス及びボブは、それぞれ非負数ｘ及びｙを有する。
【００５１】
出力：アリス及びボブは、数ｘ又はｙを明らかにすることなくｘ＞ｙであるか否かを学習する。
１．ボブは、それぞれ以下に対応する３つの状態｛Ａ，Ｂ，Ｕ｝を定義する。すなわち、アリスの方が大きい数を有する、ボブの方が大きい数を有する、及び未決定である。各ビットに対し、ボブは、数｛１，２，３｝の異なる順列を使用して｛Ａ，Ｂ，Ｕ｝を符号化する。
２．最左ビットに対し、ボブは、以下のように２入力ルックアップテーブルｚ(ｎ)を構成する。
【００５２】
【表１】
2009511937.tif 000012
【００５３】
ここで、ｙｎは、数ｙの最上位ビットである。ｙｎ＝０である場合、ボブは左の列を選択すべきであり、そうでない場合、右の列を使用すべきである。
３．アリスはインデックスとしてのｘｎとともにＯＴ１２を使用してｓ(ｎ)＝ｚ(ｎ)(ｘｎ)を取得する。
４．各ｉ＝ｎ−１，…，１に対し、アリス及びボブは以下のサブステップを行う。
(ａ)ボブは、以下のようにｓ(ｉ)及びｘｉによってインデックスされる６入力ルックアップテーブルｚ(ｉ)を構成する。
【００５４】
【表２】
2009511937.tif 000013
【００５５】
ｙｎ＝０である場合、ボブは左の列を選択すべきであり、そうでない場合、右の列を使用すべきである。
(ｂ)アリスは、インデックスとしてのｓ(ｉ＋１)及びｘｉとともにＯＴ１６を使用してｓ(ｉ)＝ｚ(ｉ)(ｓ(ｉ＋１)，ｘｉ)を取得する。
５．ボブはアリスに、最下位ビットのｓ(１)の３つの状態の意味を送信する。この時アリスは、いずれの数の方が大きいかを知る。
【００５６】
ここで、上述した基本の既知の安全なプロトコルを使用して、プライベートデータの安全な分類について説明する。
【００５７】
プライベート情報分類
図１は、本発明の一実施の形態のステップを示す。
【００５８】
安全な閾値分類器
入力：アリスは入力データベクトルｘを有し、ボブは強分類器
【００５９】
【数１０】
2009511937.tif 000014
【００６０】
を有し、ここで、
【００６１】
【数１１】
2009511937.tif 000015
【００６２】
は弱分類器であり、αｎ、βｎ及びθｎは、トレーニング中に学習されるスカラー値、たとえば１及び０である。
【００６３】
ベクトルｙｎは、ボブが、決定木、ベイズネットワーク、サポートベクトルマシン(ＳＶＭ)及びニューラルネットワーク等、従来のトレーニング方法を使用して「学習する」、ボブの分類器のパラメータを格納する。
【００６４】
出力：アリスは結果ｓｉｇｎ(Ｈ(ｘ))を取得するがそれ以外は何も取得せず、ボブはデータｘに関して何も学習しない。
１．アリスはデータｘ１０１を提供し、ボブは、各々が超平面ｙｎ１０２を有するＮ個の閾値分類器ｈｎ(ｘ)を提供する。ボブはまた、
【００６５】
【数１２】
2009511937.tif 000016
【００６６】
であるように、Ｎ個の乱数ｓ１，…，ｓＮのセットを生成する(１１０)。
２．各ｎ＝１，…，Ｎに対し、アリス及びボブは以下のサブステップを実行する。
(ａ)アリス及びボブは、安全なドット積プロトコルを使用して、ドット積ｘＴｙｎ１２０のプライベートシェアａｎ１２１及びｂｎ１２２をそれぞれ取得する。
(ｂ)アリス及びボブは、安全なmillionaireプロトコルを使用して、ａｎ又はθｎ−ｂｎのいずれの数の方が大きいかを判断する(１３０)。αｎ又はβｎを返す代りに、プロトコルは、結果１３１としてαｎ＋ｓｎ又はβｎ＋ｓｎのいずれかを返す。
(ｃ)アリスは結果をｃｎ１３２に格納する。
３．アリス及びボブは、安全なmillionaireプロトコルを使用して、数
【００６７】
【数１３】
2009511937.tif 000017
【００６８】
又は
【００６９】
【数１４】
2009511937.tif 000018
【００７０】
のいずれの方が大きいかを判断する(１４０)。結果１０３は符号である。アリスの方が大きい数を有する場合、ｘは正に分類され、そうでない場合、ｘは負に分類される。
【００７１】
安全な多項式カーネル分類器
図２は、本発明の一実施の形態のステップを示す。
【００７２】
入力：アリスはデータｘを有し、ボブは、分類器
【００７３】
【数１５】
2009511937.tif 000019
【００７４】
を有し、ここで、ｈ(ｘＴｙ)＝(ｘＴｙ＋ｃ)ｄであり、式中、ｃ及びｄはボブのみが知るパラメータである。
【００７５】
出力：アリスは結果ｓｉｇｎ(Ｈ(ｘ))を有するがそれ以外は何も有さず、ボブはデータｘに関して何も学習しない。
１．アリスはデータｘ１０１を提供し、ボブは、各々が超平面ｙｎ１０２を有するＮ個の多項式分類器ｈｎ(ｘ)を提供する。ボブは、
【００７６】
【数１６】
2009511937.tif 000020
【００７７】
であるように、Ｎ個の乱数ｓ１，…，ｓＮのセットを生成する(１１０)。
２．各ｎ＝１，…，Ｎに対し、アリス及びボブは以下のサブステップを実行する。
(ａ)アリス及びボブは、安全なドット積プロトコルを使用して、ドット積ｘＴｙｎ１２０のプライベートシェアａｎ１２１及びｂｎ１２２をそれぞれ取得する。
(ｂ)ボブは、多項式ｆｎ(ａ)＝(ａｎ＋ｂｎ＋ｃ)ｄ＋ｓｎ＝(ｘＴｙｎ＋ｃ)ｄ＋ｓｎを構成する(２３０)。
(ｃ)アリス及びボブはＯＰＥプロトコルを使用してｆｎ(ａ)を評価し
【００７８】
【数１７】
2009511937.tif 000021
【００７９】
を確定する(２３５)。
３．アリス及びボブは、安全なmillionaireプロトコルを使用して、ｒ又はｓのいずれの数の方が大きいかを判断する(２４０)。アリスの方が大きい数を有する場合、ｘは正に分類され、そうでない場合、ｘは負に分類される。
【００８０】
安全なガウスカーネル分類器
図３は、本発明の一実施の形態のステップを示す。
【００８１】
入力：アリスは入力データｘを有し、ボブは、分類器
【００８２】
【数１８】
2009511937.tif 000022
【００８３】
を有し、ここで、
【００８４】
【数１９】
2009511937.tif 000023
【００８５】
、すなわちノルム２又はユークリッド距離であり、γはトレーニング中にボブによって学習されるスカラーである。
【００８６】
出力：アリスは結果ｓｉｇｎ(Ｈ(ｘ))を取得するがそれ以外は何も取得せず、ボブはデータｘに関して何も学習しない。
１．アリスはデータｘ１０１を提供し、ボブは、各々が超平面ｙｎ１０２を有するＮ個の多項式分類器ｈｎ(ｘ)を提供する。
２．各ｎ＝１，…，Ｎに対し、アリス及びボブは以下のサブステップを行う。
(ａ)ボブは乱数ｓＢを選択し、関数ｆ(ｚ)＝γｚ−ｓＢを構成し(３１０)、ここでｚはスカラーである。
(ｂ)アリス及びボブはＯＰＥを使用して、アリスに対するシェアｓＡ３２１を取得する(３２０)。ここでは、ｓＡ＝ｆ(ｘＴｘ)、すなわち安全なドット積である。
(ｃ)アリス及びボブは、安全なドット積プロトコルを使用して、ドット積ｘＴ(−２γｙｎ)のシェアｒＡ３３１及びｒＢ３３２をそれぞれ取得する(３３０)。
(ｄ)アリスはｔＡ＝ｅｘｐ(ｓＡ)ｅｘｐ(ｒＡ)を構成する(３３３)。
(ｅ)ボブはｔＢ＝ｅｘｐ(ｓＢ)ｅｘｐ(ｒＢ)ｅｘｐ(γｙｎＴｙｎ)を構成する(３３４)。
(ｆ)アリス及びボブは、安全なドット積プロトコルを使用して、ドット積
【００８７】
【数２０】
2009511937.tif 000024
【００８８】
のプライベートシェアａｎ３４１及びｂｎ３４２を取得する(３４０)。
３．アリスは、累算
【００８９】
【数２１】
2009511937.tif 000025
【００９０】
３４３を確定し、ボブは、累算
【００９１】
【数２２】
2009511937.tif 000026
【００９２】
３４４を確定する。
４．アリス及びボブは、安全なmillionaireプロトコルを使用して、ａ又はｂのいずれの数の方が大きいかを示す符号１０３を確定する(３５０)。アリスの方が大きい数を有する場合、ｘは正に分類され、そうでない場合、ｘは負に分類される。
【００９３】
安全なシグモイドカーネル分類器
入力：アリスはデータｘ１０１を有し、ボブは、分類器
【００９４】
【数２３】
2009511937.tif 000027
【００９５】
を有し、ここで、ｈ(ｘＴｙ)＝１／(１＋ｅｘｐ(ｘＴｙ))である。
【００９６】
出力：アリスは結果ｓｉｇｎ(Ｈ(ｘ))を有するがそれ以外は何も有さず、ボブはデータｘに関して何も学習しない。
１．各ｎ＝１，…，Ｎに対し、アリス及びボブは以下のサブステップを実行する。
(ａ)アリス及びボブは、安全なドット積プロトコルを使用してドット積ｘＴｙｎのシェアａｎ１２１及びｂｎ１２２をそれぞれ取得し(１２０)、ここでｙｎ１０２は上述したようにボブによって提供されるベクトルである。
(ｂ)アリス及びボブは、安全なドット積プロトコルを使用して、ｓＡ＋ｓＢ＝ｅｘｐ(ａ)ｅｘｐ(ｂ)であるように、プライベートシェアｓＡ４３１及びｓＢ４３２を確定する(４３０)。
(ｃ)ボブはランダムにｒＢを選択し、ｆ(ｓＡ)＝ｒＢ＋ｒＢ(ｓＡ＋ｓＢ)＝ｒＢ(１＋ｅｘｐ(ｘＴｙｎ))を定義する(４４０)。
(ｄ)アリス及びボブは、ＯＰＥを使用して、ｒＡ＝ｆ(ｓＡ)を確定する(４５０)。
(ｅ)アリス及びボブは、ドット積プロトコルを使用して、ドット積
【００９７】
【数２４】
2009511937.tif 000028
【００９８】
のシェアｔＡ，ｎ及びｔＢ，ｎを確定する(４６０)。
２．アリスは
【００９９】
【数２５】
2009511937.tif 000029
【０１００】
４７１を確定する。
３．ボブは
【０１０１】
【数２６】
2009511937.tif 000030
【０１０２】
４７２を確定する。
４．アリス及びボブは、安全なmillionaireプロトコルを使用して、ｔＡ又は−ｔＢのいずれの数の方が大きいかを示す符号１０３を確定する(４８０)。アリスの方が大きい数を有する場合、ｘは正に分類され、そうでない場合、ｘは負に分類される。
【０１０３】
安全なｋ−ｎｎ分類器
このプロトコルは、ｋ−ｎｎ分類器の安全な実現である。アリスはデータｘを有する。ボブは、関連するラベルｃ(ｙｉ)を有する点
【０１０４】
【数２７】
2009511937.tif 000031
【０１０５】
を有する。データｘが与えられる場合、目的は、データｘに最も近いｋ個のベクトルｙｉの大部分のラベルを見つけることである。ここでは、２値分類器に焦点を当てる。アリス及びボブは、半径距離ｒという追加のシェアを有し、距離ｒ内には、正確にｋ個の点ｙｉ１，…，ｙｉｋがある。
【０１０６】
アリス及びボブは、後述する半径(radius)プロトコルを使用して値の数をプライベートにカウントすることができ、それらのラベルを使用してデータｘに対する正しいラベルをプライベートに確定することができる。しかしながら、ｋ−ｎｎ分類器は、半径ｒではなくｋに関して定義されるため、ここでは、ｋが与えられる場合に半径ｒを確定することができるプロトコルを提供する。
【０１０７】
これを行うために、データｘからｋ番目の最遠点の半径であるようにｒｋを定義し、ｋが与えられる場合、ｒｋをいかに見つけるかについて説明する。半径ｒｋが得られた後、ｘのラベルを確定することができる。ここでは、アリス及びボブは、上述した安全なドット積プロトコルを使用して点ｘと複数の点ｙｉのうちの任意のものとの間のユークリッド平方距離ｄ(ｘ，ｙｉ)のプライベートシェアを確定することができるものとする。
【０１０８】
これら方法の基本ステップを、擬似コードに関連して図５に示す。
【０１０９】
入力：アリスは入力データｘと半径ｒのプライベートシェアｒＡとを有し、ボブは点ｙｉと半径ｒのプライベートシェアｒＢとを有する。
【０１１０】
出力：アリスは、ｘの分類ラベルを学習するがそれ以外は何も学習せず、ボブは何も学習しない。
１．各点ｙｉに対し、アリス及びボブは、以下のサブステップを実行する。
(ａ)アリス及びボブは、ドット積(−２ｘ)Ｔｙのプライベートシェアａ及びｂを取得する。
(ｂ)ボブは、ｓＢ＝ｂ＋ｙＴｙ及び関数ｆ(ｚ)＝ｚ＋ｓＢを定義する。
(ｃ)アリス及びボブは、ＯＰＥを使用して、ｓＡ＝ｆ(ｘＴｘ＋ａ)を評価し、ここでｓＡはアリスのプライベートシェアである。
(ｄ)ボブはランダムにｕｉを選択する。
(ｅ)アリス及びボブは、millionaireプロトコルを使用してｓＡ−ｒＡとｒＢ−ｓＢとを比較する。これは、ユークリッド平方距離ｄ(ｘ，ｙｉ)と半径ｒとを比較することと等価である。ｓＡ−ｒＡ＜ｒＢ−ｓＢ且つｃ(ｙｉ)＝１である場合、ボブはｕｉ＋１を返し、そうでない場合、ボブはｕｉを返す。アリスは結果をｖｉに格納する。
２．アリス及びボブは、それぞれ
【０１１１】
【数２８】
2009511937.tif 000032
【０１１２】
及び
【０１１３】
【数２９】
2009511937.tif 000033
【０１１４】
を確定する。
３．アリス及びボブは、millionaireプロトコルを使用してｖとｕ＋ｋ／２とを比較する。ｖ＞ｕ＋ｋ／２である場合、ｘは１にラベル付けされ、そうでない場合、ラベルは０である。
【０１１５】
半径プロトコル
入力：アリスは入力データｘを有し、ボブは点ｙｉのリストと値ｋとを有する。
【０１１６】
出力：アリスは、ｘのｋ個の最近傍の半径ｒのシェアｒＡを有し、ボブはシェアｒＢを有し、半径ｒ＝ｒＡ＋ｒＢである。ボブは、データｘに関して何も学習しない。
１．アリス及びボブは、それぞれｒＡ及びｒＢをランダムに選択する。
２．終了まで以下を行う。
(ａ)各点ｙｉに対し、アリス及びボブは以下のサブステップを実行する。
ｉ．アリス及びボブは、ドット積(−２ｘ)Ｔｙｉのシェアａ及びｂを取得する。
ｉｉ．ボブは、ｓＢ＝ｂ＋ｙｉＴｙｉ及び関数ｆ(ｚ)＝ｚ＋ｓＢを定義する。
ｉｉｉ．アリス及びボブは、ＯＰＥを使用して、ｓＡ＝ｆ(ｘＴｘ＋ａ)を評価し、ここでｓＡはアリスのプライベートシェアである。
ｉｖ．ボブは、ランダムにｕｉを選択する。
ｖ．アリス及びボブは、millionaireプロトコルを使用して、ｓＡ−ｒＡとｒＢ−ｓＢとを比較する。これは、ユークリッド平方距離ｄ(ｘ，ｙｉ)とｒとを比較することと等価である。ｓＡ−ｒＡ＜ｒＢ−ｓＢである場合、ボブはｕｉ＋１を返し、そうでない場合、ボブはｕｉを返す。アリスは、結果をｖｉに格納する。
(ｂ)アリス及びボブは、それぞれ
【０１１７】
【数３０】
2009511937.tif 000034
【０１１８】
及び
【０１１９】
【数３１】
2009511937.tif 000035
【０１２０】
を確定する。
(ｃ)アリス及びボブは、millionaireプロトコルを使用して、ｖとｕ＋ｋとを比較し、以下を行う。
ｉ．ｖ＞ｕ＋ｋである場合、ｒは大きすぎ、アリスがｒＡを１だけ低減するか、又はボブがｒＢを１だけ低減し、繰り返す。
ｉｉ．ｖ＜ｕ＋ｋである場合、ｒは小さすぎ、アリスがｒＡを１だけ増大するか、又はボブがｒＢを１だけ増大し、繰り返す。
ｉｉｉ．ｖ＝ｕ＋ｋである場合、終了する。
【０１２１】
本発明は、サポートベクトルマシン(ＳＶＭ)、ニューラルネットワーク、ＡｄａＢｏｏｓｔ及びｋ−ｎｎ分類器等、種々のドット積ベースの分類器を使用してプライベート情報を分類する方法を提供する。
【０１２２】
本発明の精神及び範囲内で、他の種々の適応及び変更を行ってもよい、ということが理解されるべきである。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内にあるこうしたすべての変形及び変更を包含することである。
【産業上の利用可能性】
【０１２３】
本発明のプライベートデータを安全に分類する方法は、多くの種類の分野に適用可能である。
【図面の簡単な説明】
【０１２４】
【図１】本発明の一実施の形態による安全な閾値分類器を使用してプライベートデータを分類するフローチャートである。
【図２】本発明の一実施の形態による安全な多項式分類器を使用してプライベートデータを分類するフローチャートである。
【図３】本発明の一実施の形態による安全なガウス関数分類器を使用してプライベートデータを分類するフローチャートである。
【図４】本発明の一実施の形態による安全なシグモイド分類器を使用してプライベートデータを分類するフローチャートである。
【図５】本発明の一実施の形態による安全なｋ−ｎｎカーネル分類器を使用してプライベートデータを分類する擬似コードのチャートである。
【図１】
2009511937.tif 000061
【図２】
2009511937.tif 000062
【図３】
2009511937.tif 000063
【図４】
2009511937.tif 000064
【図５】
2009511937.tif 000065
【国際調査報告】
2009511937.tif 000066
2009511937.tif 000067