暗号化技術を用いたツリーに基づく分類のための方法及び装置
【課題】ユーザと分類器との間で相互にプライバシー及びセキュリティを満足することができる、暗号化技術を用いたツリーに基づく分類のための方法等を提供する。
【解決手段】一実施形態において、方法は、第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行うステップ(201)であって、前記第1の位置とは異なる第2の位置とデータを交換して、前記ユーザ入力を取得し、単準同型暗号化を用いてユーザに分類の結果を提供し、それにより、前記ユーザ入力が前記分類器に対して隠され、前記分類ツリーが前記ユーザに対して隠され、前記分類器の出力が前記分類器に対して隠されるようにするステップを有する。
【解決手段】一実施形態において、方法は、第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行うステップ(201)であって、前記第1の位置とは異なる第2の位置とデータを交換して、前記ユーザ入力を取得し、単準同型暗号化を用いてユーザに分類の結果を提供し、それにより、前記ユーザ入力が前記分類器に対して隠され、前記分類ツリーが前記ユーザに対して隠され、前記分類器の出力が前記分類器に対して隠されるようにするステップを有する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明の実施形態は、分類器及び分類におけるその使用の分野に係り、より具体的には、本発明の実施形態は、安全且つオブリビアス(oblivious)な処理を用いる実施形態を含む、ツリーに基づく分類法及びデータ観測法を組み合わせることに係る。
【背景技術】
【0002】
クラウドコンピュータモデルは、主に、投資が不要であり、柔軟性があり、且つ運用コストが削減されることから、多くのビジネスを魅了している。クラウドコンピュータモデルは、企業がビジネスを行う方法を、利用ごとに支払うユーティリティモデルへと変えた。CaaS(Computing as a Service)は、企業が、実施許諾を受けたソフトウェアのコピー、自身の処理ロジック及び計算ハードウェアのセットアップを社内で有する必要なしに、計算能力及び処理ロジックを利用することができるクラウドコンピュータの新興のブランチである。演算処理の1タイプは、このような使用のための候補であるツリーに基づく分類である。データの指数関数的な成長に伴い、大容量のデータセットに対してパターン認識及びマイニングを行う真の必要性が存在する。
【0003】
たとえCaaSが多くの利点を提供するとしても、セキュリティ及びプライバシーに対する懸念は、依然として、多くの企業をクラウドへ移行させない主たる要因である。ユーザは、データを明らかにすることなく、サービスプロバイダがデータに対して演算処理を行うことを可能にする必要があるので、入力データを保護することは困難である。サービスとしての分類(classification as a service)は、サービスプロバイダがツリーをトレーニングするために使用するトレーニングセット及び分類器を保護する更なる課題を有する。
【0004】
以下のシナリオについて考える。ユーザ(クライアント)は画像の組(X)を有する。ユーザは、画像が例えば顔を含むかどうかを決定するために、画像を分類したいと望むことがある。ユーザは、画像を分類するための分類アルゴリズムを実行するリソース及び/又は技能を有していない。従って、ユーザは、分類タスクfを遠隔の分類器(クラウド内のサーバ)に委託し、決定f(x)(なお、x∈X)を得たいと望む。以下は、セキュリティ及びプライバシーの要求である。
1.ユーザは、画像(x個の値)を分類器に明らかにしたくない。
2.分類器は、f(x)から推論され得る情報以外、その分類アルゴリズムfをユーザに明らかにしたくない。
3.ユーザは、分類決定f(x)を分類器に学習させたくない。
【0005】
以下は、当該技術でよく知られている計算原理の幾つかに関する簡単な説明である。
【0006】
[計算原理]
・紛失通信(Oblivious Transfer)(OT)
2分の1(1-out-of-2)紛失通信(OT12)において、1つのパーティ、すなわち送信側は、2つの文字列(M0,M1)から成る入力を有し、第2のパーティ、すなわち選択側の入力は、ビットσである。選択側は、Mσを学習するべきであるが、M1−σについては何ら学習すべきでなく、一方、送信側は、σに関する情報を何も得るべきではない。N分の1紛失通信(OT1N)は、OT12の拡張であり、選択側は1つのMi(1≦i≦N)のみを学習する。N分のk紛失通信(OTkN)は、OT1Nの一般化である。更なる情報のために、M. O. Rabin、“How to Exchange Secrets with Oblivious Transfer”、Cryptology ePrint Archive、Report 2005/187、2005年、http://eprint.iacr.org/(非特許文献1)、S. Even等、“A Randomized Protocol for Signing Contracts”、Commun. ACM、28(6):637-647、1985年(非特許文献2)、及びM. Naor等、“Efficient Oblivious Transfer Protocols”、SODA’01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms、448-457頁、米国ペンシルベニア州フィラデルフィア、2001年、Society for Industrial and Applied Mathematics(非特許文献3)を参照されたし。
【0007】
・秘密多項式評価法(Oblivious Polynomial Evaluation)
秘密多項式評価法(OPE)プロトコルは2つのパーティ、すなわち、何らかの有限フィールド+pにわたる多項式fを有する送信側と、入力x∈+pを有する受信側とを有する。プロトコルの終わりに、受信側はf(x)のみを学習し、送信側は何も学習しない。OPEに関する更なる情報のために、M. Naor等、“Oblivious Transfer and Polynomial Evaluation”、SODA ’99: Proceedings of the thirtyfirst annual ACM symposium on Theory of computing、245-254頁、米国ニューヨーク州ニューヨーク、1999年、ACM(非特許文献4)、H. -D. Li等、“Oblivious Polynomial Evaluation”、J. Comput. Sci. Technol.、19(4):550-554、2004年(非特許文献5)、M. Naor等、“Oblivious Polynomial Evaluation”、SIAM J. Comput.、 35(5):1254-1281、2006年(非特許文献6)、及びY. -C. Chang等、“Oblivious Polynomial Evaluation and Oblivious Neural Learning”、Teor. Comput. Sci.、341(1):39-54、2005年(非特許文献7)を参照されたし。
【0008】
・準同型暗号化(Homomorphic Encryption)
非対称暗号化システムは、キー生成、暗号化(E)及び復号化(Δ)関数から成り、何らかの所与のパブリックキー及びプレーンテキスト空間における何らかの2つのプレーンテキストメッセージm1、m2に関し、以下の暗号化関係:
【数1】
が有効である場合に、準同型である。ここで、
(外1)
は2項演算子である。演算子が加算であるとき、暗号化システムは加法準同型であり(例えば、P. Paillier、“Public-Key Cryptosystems Based On Composite Degree Residuosity Classes”、EUROCRYPT ’99: Proceedings of the 17th international conference on Theory and application cryptographic techniques、223-238頁、ベルリン、ハイデルベルク、1999年、シュプリンガー出版(非特許文献8))、演算子が乗算であるとき、暗号化システムは乗法準同型である(T. El Gamal、“A Public Key Cryptosystem and a Signature Scheme Based On Discrete Logarithms”、Proceedings of CRYPTO 84 on Advances in cryptology、10-18頁、米国ニューヨーク州ニューヨーク、1985年、シュプリンガー出版(非特許文献9))。
【0009】
[紛失通信]
従来のOTプロトコルは全てパブリックキー暗号化(PKC)を必要とする。PKCは冪剰余(modular exponetiation)を伴う。従って、計算オーバヘッドは、その計算オーバヘッドよりも厳しい。ここで、OT12及びOT1Nの実施について記載する。これは、非特許文献3によって提案されているプロトコルに密接に従う。
【0010】
・1/2紛失通信
選択側の入力は、σ∈0,1であり、送信側の入力は、2つの文字列M0,M1である。選択側の出力は、Mσである。プロトコルは、素数位数(prime order)のグループ・qにわたって動作し、gは、該グループの生成元である。構文は、ランダムオラクルとしてモデル化される、すなわち、如何なる参加者も利用可能であり且つ例えばSHA等のハッシュ関数として通常は実施される真ランダム関数として選択される、関数Hを使用する。
【0011】
・エルガマル(ElGamal)暗号化を用いるプロトコル
1.送信側は、ランダム要素rs∈・qを選択し、それを公開する。
2.選択側は、ランダム要素rs∈・qをとり、パブリックキーPKσ=grc及びPK1−σ=rs/PKσを設定し、PK0を送信側に送る。
3.送信側は、PK1=rs/PK0を計算し、ランダム要素r1,r2∈・qを選択する。送信側は、
(外2)
としてE0によってM0を暗号化する(なお、
(外3)
は、ビット単位の2項演算子である。)とともに、
(外4)
を暗号化し、それらを選択側に送る。
4.選択側は、H((grσ)rc)=H(PKσrσ)を計算し、それを用いてMσを復号化する。
【0012】
同じr=r1=r2は、同レベルのプライバシー及びセキュリティを提供するために使用され得る。同じrによれば、送信側は、3つの累乗(うち1つは、プロトコルが始まる前に予め計算され得る。)を計算する必要があり、選択側は、2つの累乗(うち1つは予め計算され得る。)を計算する必要がある。qはnビット素数位数であるとすると、通信複雑度は2n(選択側から)+n+2log2|M|(送信側から)である。複雑度は、メッセージが・qの要素であり、且つ、1つのランダム値rが使用される場合に、5nである。
【0013】
[秘密多項式評価法]
非特許文献7によって紹介されているOPEプロトコルは、OT12を用いる。
【0014】
多項式は、有限フィールド+qにわたる。なお、qは、lビット素数である。受信側は入力x*∈+qを有し、送信側は、
(外5)
を有する。
【0015】
各係数aiは、以下:
【数2】
のように表される。
【0016】
夫々のi∈[1,d]及び夫々のj∈[1,l]について、受信側は、以下:
【数3】
のように値vijを計算する。
【0017】
夫々のi∈[1,d]について、以下:
【数4】
が適用できる点に留意すべきである。
【0018】
プロトコルがOT12を用いるならば:
1.受信側は、(rij,vij+rij)のdl個の対を用意する。なお、各rijは、+qからランダムに一様に選択される。
2.(rij,vij+rij)の各対ごとに、送信側は、aij=0の場合にはrijを、それ以外の場合にはvij+rijを得るよう、受信側とともにOT12を実行する。
3.送信側は、
【数5】
に等しいdlのOT12プロトコルの出力とa0との和を計算する。受信側は、送信側の出力から
(外6)
を減じて、f(x*)を得る。
【0019】
このプロトコルにおける支配的な動作は、OT12動作である。複雑度は、OT12の複雑性のdl倍である(OT12ごとに5つの累乗及び3つの逆演算)。
【0020】
加法準同型暗号化(HE)を用いるプロトコルは、以下の通りである:
1.受信側は、E(vij)のdl個の値を準備する。
2.Eijの各値ごとに、送信側は、aij=0の場合には1を、それ以外の場合にはE(vij)をとる。
3.送信側は、
【数6】
に等しいdl個の暗号化された値の出力とa0との和を計算する。受信側は、復号化して、f(x*)を得る。
【0021】
このプロトコルにおける支配的な動作は、HE動作である。複雑度は、暗号化の複雑度の2dl倍である(すなわち、暗号化ごとに1つの累乗)。最初のプロトコルと比較して、第2のアプローチにおける累乗の数は半分に減らされる。最初のプロトコルと比較して、暗号文空間がプレーンテキスト空間と同じであるとすると、第2のアプローチにおける通信複雑度は、3分の2だけ減らされる。
【0022】
上記に関連する更なる技術は、PPDM(Privacy Preserving Data Mining)を含む。PPDM研究において、主な焦点は、プライバシー及びセキュリティに対する懸念に対処しながら、集合的に予測モデルを学習することであった。かかる研究において、2つの主枝の問題が存在する。両主枝の最終目標は、予測モデルをトレーニングすることであるが、2つの主枝は異なる憶測を立て且つ異なる設定を有する。第1のカテゴリ(摂動入力の問題)は、データマイニング部、すなわち、分類器への入力を秘密のままとしながら、予測モデルを生成するという課題に対処する。第2のカテゴリ(非公開パーティ入力の問題)は、次の問題に対処する:入力データを有する幾つかのパーティが存在し、それは、集合的に、自分たちの入力データを他の関連するパーティに秘密にしながら、予測モデルを生成したいと望む。
【発明の概要】
【発明が解決しようとする課題】
【0023】
非公開パーティ入力の問題において、異なるパーティからの入力データは、水平又は垂直のいずれかの方向において分割される。水平分割されたデータによれば、各パーティは、考慮中の全ての機能に対する完全なデータ設定を有する。対照的に、垂直分割されたデータによれば、各パーティは、考慮中の機能に対する完全なデータ設定を有さない。すなわち、夫々が、完全なデータ設定を構成するよう部分的な入力データを有する。理想的な状況においては、データマイニング手順の終わりに、各パーティは、垂直又は水平に分割された自身のデータのみと、トレーニングされた予測モデルとを知っている。
【0024】
摂動入力の問題において、その名の通り、入力データを所有するユーザは、データマイニング処理の前に“ノイズ”(例えば、一般化、歪み、等)をデータに加え、次いで、原の累積部分(原の値ではない。)を回復するために再構成技術を用いる。ノイズは、分類器からデータを隠す。しかし、そのような方法が提供するプライバシー及びセキュリティのレベルを定量化することは困難である。更に、予測モデルは、ノイズに起因して同程度の偽陽性及び陰性を有する。摂動データから予測モデルを学習した後、モデルは非摂動データを分類することができる。ユーザ入力を保護するために、ユーザは、局所的に分類アルゴリズムを実行するために予測モデルを与えられる。かかるアプローチはユーザ入力のプライバシーを保つが、予測モデルを保護することはできない。
【0025】
従って、本発明は、上記を鑑み、ユーザと分類器との間で相互にプライバシー及びセキュリティを満足することができる、暗号化技術を用いたツリーに基づく分類のための方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【0026】
分類のための方法及び装置について開示する。一実施形態において、方法は、第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行うステップであって、前記第1の位置とは異なる第2の位置とデータを交換して、前記ユーザ入力を取得し、単準同型暗号化を用いてユーザに分類の結果を提供し、それにより、前記ユーザ入力が前記分類器に対して隠され、前記分類ツリーが前記ユーザに対して隠され、前記分類器の出力が前記分類器に対して隠されるようにするステップを有する。
【発明の効果】
【0027】
本発明の実施形態によれば、ユーザと分類器との間で相互にプライバシー及びセキュリティを満足することができる、暗号化技術を用いたツリーに基づく分類のための方法及び装置を提供することが可能となる。
【図面の簡単な説明】
【0028】
【図1】本願で用いられる表記法により決定ツリーの例を表す。
【図2】本願で記載されるアプローチを用いてデータを処理する工程の一実施形態のフロー図である。
【図3】分類器で実行されるアルゴリズムの一実施形態の擬似コードを表す。
【図4】線形な分類ツリーを用いてデータを分類する工程の一実施形態のフロー図である。
【図5】分類器を使用するときにユーザ端末によって行われる動作のアルゴリズムの一実施形態のための擬似コードである。
【図6】線形な分類ツリーを用いてデータを分類する工程の一実施形態のフロー図である。
【図7】各内部ノードでの分裂規則を評価するために分類器で実行されるアルゴリズムの一実施形態のための擬似コードである。
【図8】分類ツリーを用いて分類を行う分類器での分裂規則評価のための工程の一実施形態のフロー図である。
【図9】本願で使用される表記法により分類ツリーの例を表す。
【図10】図9の分類ツリーの例を表す。
【図11】コンピュータシステムのブロック図である。
【発明を実施するための形態】
【0029】
本発明は、本発明の様々な実施形態に係る以下に与えられる詳細な説明及び添付の図面から、より十分に理解されるであろう。なお、それらの実施形態は、本発明を具体的な実施形態に限定するものではなく、説明及び理解のためにのみ挙げられている。
【0030】
以下は、オブリビアスなツリーに基づく分類を行うための新規なアプローチを開示する。1つのアプローチは、紛失通信プロトコルに基づき、一方、他のアプローチは、加法準同型暗号化システムに基づく。一実施形態において、ツリーに基づく分類は、既存のプロトコルよりもずっと有効である新規な秘密多項式評価法プロトコルに基づく準同型暗号化と組み合わされる。一実施形態において、新しいプロトコルが構築され、実際的な暗号化技術が用いられ、それにより、暗号化されたデータに対する特定の算術演算の実行を可能にする。
【0031】
ここで記載される技術は、幾つかのモデルにおいて使用されてよい。
【0032】
以下の記載において、多数の詳細が、本発明のより完全な説明を提供するために示されている。しかし、当業者には当然のことながら、本発明は、それらの具体的な詳細によらずに実施されてよい。他の事例では、よく知られている構成及び装置は、本発明を不明りょうにすることを回避するために、詳細にというよりも、ブロック図形式において示されている。
【0033】
次の詳細な記載の幾つかの部分は、コンピュータメモリ内のデータビットに対する演算のアルゴリズム及びシンボル表現に関連して与えられている。それらのアルゴリズム的記述及び表現は、データ処理技術における当業者によって他の当業者に自身の研究の内容を最も効果的に伝えるために使用される手段である。アルゴリズムは、ここでは、概して、所望の結果をもたらすセルフコンシステントな一連のステップであると考えられる。ステップは、物理量の物理的処置を必要とするものである。通常、必然的ではないが、それらの量は、記憶され、転送され、結合され、比較され、且つ、別なふうに扱わされることが可能な電気的又は磁気的な信号の形態をとる。それらの信号をビット、値、要素、シンボル、文字、項、数等と呼ぶことは、主に公共的使用のために、時々便利である。
【0034】
しかし、それらの及び同様の用語の全ては、適切な物理量と関連づけられるべきであり、単にそれらの量に適用される便利なラベルに過ぎないことが、念頭に置かれるべきである。以下の議論から明らかなように、具体的に別なふうに述べられない限り、明細書全体を通じて、「処理」又は「演算」又は「計算」又は「決定」又は「表示」等の語を用いる議論は、コンピュータシステムのレジスタ及びメモリ内で物理(電子)量として表されるデータを扱い、コンピュータシステムのメモリ若しくはレジスタ又はその他情報記憶、送信又は表示装置等内の物理量として同様に表される他のデータに変換するコンピュータシステム又は同様の電子演算装置の動作又は処理をいう。
【0035】
また、本発明は、ここでは、演算を行うための装置に係る。この装置は、必要とされる目的のために特別に構成されてよく、あるいは、それは、コンピュータに記憶されるコンピュータプログラムによって選択的にアクティブにされ又は再構成される汎用のコンピュータを有してよい。そのようなコンピュータプログラムは、例えば、フロッピー(登録商標)ディスク、光ディスク、CD−ROM及び光磁気ディスクを含む何らかのタイプのディスク、読出専用メモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気若しくは光学カード、又は電子的な命令を記憶するのに適しており且つ夫々コンピュータシステムバスに結合されている何らかのタイプの媒体等の、しかしそれらに限定されないコンピュータ読出可能な記憶媒体に記憶されてよい。
【0036】
ここで提示されるアルゴリズム及び表示は、本質的に、何らかの特定のコンピュータ又は他の装置とは無関係である。様々な汎用システムが、ここでの教示に従うプログラムとともに使用されてよく、あるいは、必要とされる方法ステップを実行するためのより専門の装置を構成することが便利となりうる。様々なそのようなシステムのための必要とされる構成は、以下の記載から明らかである。更に、本発明は、何らかの特定のプログラミング言語を参照して記載されない。様々なプログラミング言語が、ここで記載される本発明の教示を実施するために使用されてよいことは、明らかである。
【0037】
機械読出可能な媒体は、機械(例えば、コンピュータ)によって読出可能な形で情報を記憶又は送信するための如何なるメカニズムも含む。例えば、機械読出可能な媒体には、読出専用メモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス等がある。
【0038】
[表記法]
【表1】
表1は、ここで使用される全てのシンボル及び表記を集約する。
【0039】
[ID3アルゴリズム]
最初に、単一変数線形決定のみを必要とする場合に2に設定された分岐因子を有するツリーに基づいて入力データを非公開で分類することに焦点を当てる。次いで、当該技術は、多変数決定ツリーに拡張される。
【0040】
以下が仮定される:
・分類ツリーは既に学習されている。
・分岐因子は2である。
・カテゴリ及びクラスラベルの数は公然である。
【0041】
2つのパーティが存在する。1つは、非公開の入力ベクトルx=(x1,x2,・・・,xn)tを有するユーザ端末であり、他は、トレーニングされた分類ツリーを有する分類器である。ユーザ端末は、全てのとり得るクラスラベルC={w1,w2,・・・,wt}から自身の入力のクラスラベルを見つけたいと望む。プライバシー及びセキュリティの要求は、以下の通りである。
1.ユーザ端末は、xを分類器に対して明らかにしたくない。
2.分類器は、ユーザ端末に対して分類ツリー、特に、ツリーによって計算される決定を明らかにしたくない。
3.ユーザ端末は、自身の入力についてのクラスラベルを分類器に対して明らかにしたくない。
【0042】
分類ツリーの一例が図1に示されている。
【0043】
多数のアプローチがここで提案されている。一実施形態において、OT12は、ツリーの内部ノードの評価のために使用される。他の実施形態において、加法準同型暗号化は、ツリーの内部ノードの評価のために使用される。これらのアプローチのいずれもが、クラスラベルの評価のために加法準同型暗号化を使用する。ここでの目的のために、前者は、OTに基づくアプローチと呼ばれ、後者は、HEに基づくアプローチと呼ばれる。
【0044】
図2は、2つのアプローチのいずれか一方を用いてデータを処理する工程の一実施形態のフロー図である。処理は、ハードウェア(回路、専用のロジック、等)、ソフトウェア(汎用のコンピュータシステム又は専用の機械で実行されるもの)、又はそれらの組み合わせを有する処理ロジックによって実行される。一実施形態において、処理ロジックは分類器の部分である。
【0045】
図2を参照すると、処理は、第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行う処理ロジックを有し、該処理ロジックは、第1の位置とは異なる第2の位置とデータを交換して、ユーザ入力を取得し、単準同型暗号化を用いてユーザ端末に分類の結果を提供することを含み、それにより、ユーザ入力は分類器に対して隠され、分類ツリーがユーザ端末に対して隠される(処理ブロック201)。一実施形態において、単準同型暗号化(singly homomorphic encryption)は、分類のための重みと、入力のビット単位の多項式表現とを用いる。一実施形態において、多項式表現は、和として多項式を表す。一実施形態において、単準同型暗号化は、加法準同型暗号化を有する。一実施形態において、単準同型暗号化は、準同型暗号化に基づく秘密多項式評価法プロトコルを有する。
【0046】
[OTに基づくアプローチ]
ユーザ端末は、分類器と協働して、分類ツリーにおける各ノードごとにOPEプロトコルを実行する。分類器は、ユーザ端末が分類ツリーにおけるノードの相対位置を学習しないように、一様にランダムにノードを選択する。一般性を失うことなく、分類ノードにおけるノードが、何らかの決定論的だがランダムな順序で、1からmまでインデックスを付されるとする。ノードiでのn次元の特徴ベクトルはyi={y1,y2,・・・,yn}であるとする。各ノードiでの分裂規則fiは形式xtyi≦θiを有するとする。なお、θiは閾値である。一実施形態において、関数fは、この技術の使用前に与えられる。それは、顔や、頁上の書式に対するマーク等の分類器であってよい。一実施形態において、特定の関数は、決定ツリーにおけるノードにおいて実施される。ツリーは前もってトレーニングされている。一実施形態において、関数のクラスは、「一次関数」又は「ドット積関数」である。それらは、決定ツリーにおいて最も幅広く使用されている。
【0047】
ランダム関数fi(x,yi,θi)→{0,1}を用いてノードiでの分裂規則を表すことができる。ここで、1は、分裂規則が満足されたこと(すなわち、「はい(yes)」)を示す。関数fiは:
【数7】
のように定義されてよい。
【0048】
ユーザ端末は、分類器と協働してm回のOPEプロトコルを実行し、ユーザ端末は、各ノードインデックスiごとに0又は1(fiの出力であり何ものでもない。)のいずれかを学習し、分類器は、ユーザ端末の入力及び出力に関して何も学習しない。最後に、ユーザ端末は、全ての出力のビットベクトルZを構成し、オブリビアスにクラスラベルを学習するよう分類器とともに他のプロトコルを実行する。
【0049】
上記の方法により最終的な分類決定(すなわち、分類ツリーにおいてリーフノードに割り当てられるクラス)をオブリビアスに評価するために、各内部ノードでオブリビアスに評価される二分決定(binary decisions)を多項式に変換する必要がある。しかし、このシナリオのために多項式を構成することは、可能性の数が内部ノードの数mとともに指数関数的に増大するので、分類ツリーに2、3のノードしか存在しない簡単な場合を除いて、一般的に、法外に費用がかかる。従って、一実施形態において、大きな分類ツリーに対して加法準同型暗号化システムを用いてオブリビアスにクラスを得るための別の技術が使用される。
【0050】
分類ツリーにおける各経路ごとに、ユーザ端末は、以下のように2つのベクトルZ’及びZ”を計算し、分類器に与える:
【数8】
ここで、Eは加法準同型暗号化であり、且つ、1≦i≦mである。各経路はリーフノード及びその関連するクラスに対応する点に留意すべきである。ユーザ端末はプライベートキーを有する。分類器は乱数r∈・pを選択する。
【0051】
インデックスjを有する経路tでの各ノードごとに、分類器は、分類決定に依存してZ’[j]又はZ”[j]をとり、(Z’[j])r又は(Z”[j])rを計算する。分類器は、各経路に沿って(ルートからリーフノードまで)全てのインデックスについて計算値を乗じる。この値は、ここでは、utと呼ばれる。分類器は、
vt=ut×E(−h×r)×E(wt)
を計算する。ここで、hは、経路における内部ノードの数(すなわち、ツリー高さ)であり、wtは、経路t(1≦t≦P)のリーフノードに関連するクラスラベルであり、P回の別々の乗算を実行する。分類器は、ベクトルV={v1,v2,・・・,vP}を生成する。ユーザ端末がベクトルVの各要素を復号化するとき、クラス値の領域にはただ1つの要素しか存在せず、従って、ユーザ端末は、自身の入力xについて対応するクラスを得る。
【0052】
分類器は、付加的な計算及び通信費用を擬制にして、更に分類ツリーを隠すよう偽のノードを導入してよい。
【0053】
・複雑性の分析
以下は、分類ツリーにおける内部ノードのハイレベルな複雑性分析を示す。n個の特徴及びm個の内部ノードが存在する。完全なOTに基づくアプローチのためのプロトコルが素数位数の有限フィールド+pにわたって動作し、且つ、属性値がlビット(0−2l)であるとする。同じOPEプロトコルは、n個の一次(d=1)多項式の集合として各fiを考えることによって、適用される。OT12を用いるOPEプロトコルに関し、全部でnmdl=mnl回のOT12動作が実行される。すなわち、おおよそ5nml回の累乗及び6nmllog2|p|ビットである。HEを用いるOPEプロトコルに関し、全部で2nl回のHE動作が実行される。すなわち、2nl回の累乗及び2nllog2|p|ビットである。後者の複雑性は、暗号化される値が再利用され得るので、mとは無関係である点に留意すべきである(加算、乗算、及び除算の各演算は、上記の分析においては考慮されない点に留意すべきである。)。
【0054】
・プロトコルの例
図3は、分類器で実行されるアルゴリズムの一実施形態の擬似コードを表す。そのような擬似コードは、当業者にはよく理解されている。
【0055】
図4は、線形な分類ツリー(例えば、決定ツリー)を用いてデータを分類する工程の一実施形態のフロー図である。処理は、ハードウェア(回路、専用のロジック、等)、ソフトウェア(汎用のコンピュータシステム又は専用の機械で実行されるもの)、又はそれらの組み合わせを有する処理ロジックによって実行される。一実施形態において、処理ロジックは分類器の部分であってよい。処理ロジックは、図3において記載される擬似コードを実施する命令を実行してよい。
【0056】
図4を参照して、処理は、処理ロジックが第1の暗号化された入力データを受信することによって開始する(処理ブロック401)。一実施形態において、第1の暗号化された入力データは、加法準同型暗号化システムによりビット単位で暗号化された入力データを有する。
【0057】
次に、処理ロジックは、分類ツリーの各ノードごとに、第1の暗号化されたデータを用いて、分類器により関数を計算する(処理ブロック402)。一実施形態において、分類ツリーは、決定ツリーを有する。一実施形態において、決定ツリーは、1又はそれ以上の多重特徴分裂(multiple-feature split)を有する多変数ツリーである。一実施形態において、決定ツリーは不平衡である。一実施形態において、決定ツリーは、1又はそれ以上の1/2分裂を含む。一実施形態において、関数は分裂規則を表す。
【0058】
分類ツリー上の各ノードごとに関数を計算した後、処理ロジックは、その各ノードごとに関数を計算した結果の暗号化されたバージョンを有する第2の暗号化されたデータを送信する(処理ブロック403)。
【0059】
その後、処理ロジックは、第1及び第2の暗号化されたベクトルを受信する(処理ブロック404)。第1の暗号化されたベクトルは、分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含み、第2の暗号化されたベクトルは、分類ツリーにおける各ノードでの分類決定を含むベクトルの余(complementary)を含む。相補的な2進ベクトルは、各“0”エントリが“1”により置換され、各“1”エントリが“0”により置換されるものである点に留意すべきである。一実施形態において、第1及び第2の暗号化されたベクトルは、P次元の暗号化された2進ベクトルである。一実施形態において、第2の暗号化されたデータにおける各ノードと関連する暗号化されたデータの順序は、分類ツリーにおけるノード位置を示さない。一実施形態において、分類決定は分裂決定を有する。
【0060】
第1及び第2の暗号化されたベクトルのデータを用いて、分類ツリーにおける経路内の夫々のノードについて、処理ロジックは、その各ノードでの分類決定に基づき第1及び第2の暗号化されたベクトルのいずれかから値を選択し、その値に基づく値のベクトルを第1及び第2の暗号化されたベクトルから選択される値を用いて計算する(処理ブロック405)。一実施形態において、値のベクトルを計算することは、経路におけるノードの数、該経路におけるノードと関連するクラスラベル、値のベクトル及び暗号化関数を用いて行われる。暗号関数は、値のベクトルを暗号化するために使用される同じ準同型暗号化関数であってよい(例えば、パイエ(Pailler)準同型暗号化システム)。
【0061】
その後、処理ロジックは値のベクトルを送信し、該値のベクトルから、分類ツリーにおけるノードに割り当てられる対応するクラスが得られる(処理ブロック406)。
【0062】
[HEに基づくアプローチ]
ハイレベルな技術は、ユーザ端末が、加法準同型暗号化システムを用いて入力データxをビット単位で暗号化し、分類器が、それらの暗号化された値を用いて、夫々のノードiについて暗号データに対してxtyi−θiを計算することである。ユーザ端末は、各ノードでの分裂決定を決定するために、それらの暗号化された値を復号化する。OTに基づくアプローチとは異なり、内部ノードを評価するためのユーザ端末における作業の量は、分類ツリーにおけるノードの数mとは無関係であり、このことはユーザ端末における計算費用を大いに削減する点に留意すべきである。ビットベクトルZが計算されると、クラスラベルの評価は、OTに基づくアプローチにおいて先に記載されたものと同様である。
【0063】
より具体的には、xに含まれる要素に関し、ユーザ端末は、OPEプロトコルにおいて見られるようにvij値を計算し、次いで、ユーザ端末で起動される加法準同型暗号化システムにより各vij値を暗号化する(すなわち、ユーザ端末はプライベートキーを有する。)。ユーザ端末は、n×l個の暗号化されたvijを分類器に送る。yiに含まれる夫々の要素に関し、分類器は、xtyiを計算するために、要素の非零ビット位置に基づき正しい暗号化されたvijをとり、それらを掛け合わせる。分類器は、それにθiの暗号化された加法逆(additive inverse)を乗じることによって、閾値θiを減じる。夫々のノードiに関し、分類器は上記の計算を行って、m個の暗号化された要素のベクトルを用意する。ユーザ端末はこのベクトルを復号化し、各ノードでの分裂決定を示すビットベクトルZを計算する。ユーザ端末と分類器との間の残りの相互作用は、上記のOTアプローチと同様である。このアプローチは、加法準同型暗号化システムの利用可能性にのみ依存する点に留意すべきである。
【0064】
・プロトコルの例
図5は、分類器を用いる場合にユーザ端末によって行われる動作のアルゴリズムの一実施形態のための擬似コードである。
【0065】
図6は、線形な分類ツリー(例えば、決定ツリー)を用いてデータを分類する工程の一実施形態のフロー図である。処理は、ハードウェア(回路、専用のロジック、等)、ソフトウェア(汎用のコンピュータシステム又は専用の機械で実行されるもの)、又はそれらの組み合わせを有する処理ロジックによって実行される。一実施形態において、処理ロジックは、分類器と通信しているクライアント(すなわち、分類器にアクセスしている及び/又は分類器を使用している装置又はサービス)の部分である。処理ロジックは、図5において記載される擬似コードを実施する命令を実行してよい。
【0066】
図6を参照して、処理は、処理ロジックが、暗号化された入力データを生成するために加法準同型暗号化システムを用いて入力データのビット単位の暗号化を実行することによって、開始する(処理ブロック601)。処理ロジックは、この情報を分類器に送信する。
【0067】
その後、処理ロジックは、分類器から、入力データを用いて分類ツリーの各ノードでの分類決定を評価した結果を含むベクトルを受信する(処理ブロック602)。
【0068】
ベクトルに含まれるデータを用いて、処理ロジックは、分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、分類ツリーにおける各ノードでの分類決定を含むベクトルの余を含む第2の暗号化されたベクトルとを生成し(処理ブロック603)、第1及び第2の暗号化されたベクトルを分類器に送信する(処理ブロック604)。
【0069】
次に、処理ロジックは、分類器から、第1及び第2の暗号化されたベクトルを用いて分類器によって計算された暗号化されたクラスラベルを受信する(処理ブロック605)。この情報から、処理ロジックは、入力データについてのクラスラベルを検出する(処理ブロック606)。
【0070】
図7は、各内部ノードでの分裂規則を評価する分類器で実行されるアルゴリズムの一実施形態のための擬似コードである。
【0071】
図8は、分類ツリー(例えば、決定ツリー)を用いて分類を行う分類器での分裂規則評価のための工程の一実施形態のフロー図である。処理は、ハードウェア(回路、専用のロジック、等)、ソフトウェア(汎用のコンピュータシステム又は専用の機械で実行されるもの)、又はそれらの組み合わせを有する処理ロジックによって実行される。一実施形態において、処理ロジックは分類器の部分である。処理ロジックは、図7において記載される擬似コードを実施する命令を実行してよい。
【0072】
図8を参照して、処理は、処理ロジックが、加法準同型暗号化システムを用いて入力データを暗号化することで生成された暗号化された入力データを受信することによって、開始する(処理ブロック801)。
【0073】
暗号化された入力データを用いて、処理ロジックは、少なくとも、分類ツリーにおける各ノードごとに暗号データに対する関数を計算し、その各ノードごとに関数を計算した結果を用いて複数の要素を有する出力ベクトル生成し、該出力ベクトルをユーザ端末に送信することによって、分類ツリーの各ノードでの分類決定を評価する(処理ブロック802)。一実施形態において、分類ツリーは、決定ツリーを有する。一実施形態において、決定ツリーは、1又はそれ以上の多重特徴分裂を有する多変数ツリーである。一実施形態において、決定ツリーは不平衡である。一実施形態において、決定ツリーは、1又はそれ以上の1/2分裂を含む。一実施形態において、分類決定は、分裂決定を有する。一実施形態において、関数は、分裂規則を表す。
【0074】
その後、処理ロジックは、分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、分類ツリーにおける各ノードでの分類決定を含むベクトルの余を含む第2の暗号化されたベクトルとを受信する(処理ブロック803)。
【0075】
第1及び第2の暗号化されたベクトルを用いて、処理ロジックは、分類ツリーにおける経路内の夫々のノードについて、その各ノードでの分類決定に基づき第1及び第2の暗号化されたベクトルのいずれかから値を選択し、その値に基づく値のベクトルを計算する(処理ブロック804)。
【0076】
その後、処理ロジックは値のベクトルを送信し、該値のベクトルから、分類ツリーにおけるノードに割り当てられる対応するクラスが得られる(処理ブロック805)。
【0077】
・複雑性の分析
内部ノードの評価のために、ユーザ端末は、nl回の準同型暗号化演算を実行する。夫々の内部ノードについて、分類器は、最悪の場合に、1回の準同型暗号化演算及びn+1回の剰余乗算(modular multiplication)を実行する。全体として、分類器は、内部ノードを評価するために、m回の暗号化及び(n−1)m回の剰余乗算を実行する。リーフノードの評価のために、ユーザ端末は、m回の復号化及び2m回の暗号化を実行し、分類器は、(h+1)P回の剰余乗算及びP回の暗号化を実行する。全体として、ユーザ端末は、nl+2m個の暗号文を送信し、分類器は、m+P個の暗号文を送信する。
【0078】
法nの下で、剰余乗算がO(logn)をとり、冪剰余がO(nlogn)をとるとする。法nを有するパイエ暗号化システムが使用される場合、ユーザ端末における全体の計算複雑度は、
O((nl+2m+m)p2logp2)=O((nl+3m)p2logp2)
であり、分類器は、
O((m+P)p2logp2+((n+1)m+(h+1)P)logp2)
=O((m+P)p2logp2+(nm+hP)logp2)
である。
【0079】
全体の通信複雑度は、O((nl+2n+m+P)logp2)ビットである。
【0080】
・多変数決定ツリー
HEに基づくアプローチ位は、多変数決定ツリーにおける各ノードで複数の特徴を有する線形決定を評価するために容易に拡張され得る点に留意すべきである。その場合に、各yiは、1又はそれ以上の非零要素を有する。ユーザ端末においては複雑性に対する課題は存在しないが、分類器での計算複雑性は増大する。夫々のノードについて、最悪の場合に、分類器は、単変量の場合のO(n)倍の計算を行う必要がある。
【0081】
[例]
幾つかの例が、基本的なアプローチを明らかにするために、以下で与えられる。それらの例は、主に、OTに基づくアプローチに係るが、自明に、HEに基づくアプローチに転用され得る点に留意すべきである。
【0082】
・ハイレベルな例
分類ツリーが図9において見られるようなものである簡単な例を考える。3つの特徴x1、x2、x3と、2つのクラスラベルA、Bとが存在する。
【0083】
以下:
ノード1に関し、
y1={1,0,0}、f1(x,y1,θ1)=r1x1−r1θ1、
ノード2に関し、
y2={0,1,0}、f2(x,y2,θ2)=r2x2−r2θ2、
ノード3に関し、
y3={0,1,0}、f3(x,y3,θ3)=r3x2−r3θ3
を有する。
【0084】
これは比較的簡単な例であるから、関数は、最終出力を決定し且つOPEを使用するために構成される。関数はgであるとする。関数gは、以下の入力表2に従う(表は更に簡略化さえ得る点に留意すべきである。)。
【表2】
【数9】
【0085】
ユーザ端末は、ベクトルZ={z1,z2,z3}を評価し、クラスを得るためにそれらの値をg(Z)に代入する。
【0086】
・詳細例1−OPE及び1つの分裂規則の評価
以下は、パラメータである。目的は、分類ツリーにおけるノードでの分裂の充足可能性をオブリビアスに評価することである。
・p=383(9ビット素数)
・g=379(乗法サイクルグループZ383*の生成元)
・q=128(稼動すべき比較プロトコルに関し、q<p/2。qの長さ、l=7ビット)
・f(x)=5x(次数d=1)。
【0087】
ユーザ端末は値x=3を有し、分類器の閾値θ=10であるとする。閾値は、当該技術において標準である分類器の設計に基づく点に留意すべきである。プロトコルの目的は、ユーザ端末が、出力又は入力のいずれも分類器に知らせることなく、f(x)−θの値(符号)を知ることである。OPEプロトコルによらずに、答えは、5×3−10=5である。
【0088】
ユーザ端末は、以下の行列Vを計算する(この場合に、fの次数が1であるから、Vはベクトルである。)。ここで、v(i,j)=2j−1・viであり、iは指数であり、jはビット位置である。すなわち、
V=(20・3 21・3 22・3 23・3 24・3 25・3 26・3)
=(3 6 12 24 48 96 192)
である。
【0089】
また、ユーザ端末は、以下のランダム値行列R:
R=(11 16 1 12 3 5 2)
を計算する。各値はq/dl、すなわち128/7によって境界され、Vに含まれる値と一対一の対応を有する。
【0090】
分類器は、係数のj番目のビットの値に依存して、夫々の係数iについて、rij又はvijのいずれかを得る。ユーザ端末は、分類器がl=7回のOT12プロトコルを通じてこの演算を行うので、分類器がどの成分を得るのかを知らない。従って、ユーザ端末は、f(x)の係数5を知らない。同時に、分類器は、夫々のOT12プロトコルについてユーザ端末によって送信される2つの値のうち1つの値しか知らないので、ユーザ端末での入力値x=5を知らない。
【0091】
分類器は、最初に、係数ビット行列C:
C=(1 0 1 0 0 0 0)
を構成する。cijは、係数iのj番目のビットの値である。
【0092】
OT12を用いて、分類器は、第1及び第3の係数のみが非零であるから、以下の値:
M=(3+11 16 12+1 3 5 2)
を得る。従って、分類器は、Mにおいてそれら2つの位置についてはvij及びrijをとり、他の位置についてはvijのみをとる。
【0093】
分類器はΣmij=65を計算し、値os=65−10=55を送信する。ユーザ端末は、os−Σrij=55−50=5を計算し、それが分裂規則f(x)>tを満足すると決定する(∵5<128)。分類器は、最終のクラスラベルが、ユーザ端末のみが知っているランダム値内に隠されているので、分裂決定を知らない点に留意すべきである。
【0094】
・詳細例2−OPE及び1つの分裂規則の評価
ユーザ端末の値xを除いて、詳細例1におけるあらゆることが本例についても変わらないままである。ここで、x=1とする。
【0095】
ユーザ端末は、以下の値:
V=(1 2 4 8 16 32 64)
R=(13 11 2 13 5 4 1)
を計算する。
【0096】
分類器は、以下の値:
M=(1+13 11 4+2 13 5 4 1)
を得る。
【0097】
分類器は、Σmij=54を計算し、値os=54−10=44を送信する。ユーザ端末は、os−Σrij=44−49=−5=378を計算し、それが分裂規則f(x)>θを満足しないと決定する(∵378>128)。
【0098】
・詳細例3−OPE及び1つの分裂規則の評価(より高い次数)
関数f(x)を除いて、詳細例1におけるあらゆることが本例についても変わらないままである。f(x)=5x+2x2(d=2)とする。上記の例は全て、一次多項式を用いるが、本例では、二次多項式が用いられる。自明に、これをより高い次数の多項式に拡張することができる。
【0099】
ユーザ端末は、以下の値:
【数10】
を計算する。
【0100】
分類器は、OT12プロトコルにより、以下の値:
【数11】
を得る。
【0101】
分類器は、Σi,jmij=54を計算し、値os=93−10=83を送信する。ユーザ端末は、os−Σr(i、j)=83−60=33を計算し、それが分裂規則f(x)>θを満足すると決定する(∵33<128)。
【0102】
値83は、充足可能性に関して何も分類器に示さない点に留意すべきである。例えば、ランダム値の和は、分類器の出力よりも大きいことがあり、この場合には、ユーザ端末での入力は、分類器出力が128よりも小さい場合でさえ、分裂規則を満足しない。
【0103】
・詳細例4−簡単な分類ツリー
図10は、考慮中の簡単な分類ツリーを示す。図10を参照して、3つの成分x1、x2、x3が存在する。2つのクラスラベルA及びBは、夫々、1及び2としてエンコードされる。分裂規則出力は2進値であり、1は、ユーザ端末での入力が形式xi>θiの分類規則を満足することを示す。
【0104】
この例は、多変数の場合を扱う。具体的に、関数は、1次関数の集合として形成される。
【0105】
gは上記の決定関数であるとする。表2を用いて、gは、以下:
【数12】
のように求められる。ここでziは、ノードiでの規則の充足可能性である。
【0106】
第1に、どのようにユーザ端末が分類ツリーの内部ノードをオブリビアスに評価するのかが検討される。ユーザ端末及び分類器は、以下のような集合アプローチ(aggregated approach)において3つのOPEプロトコルを実行する。
【0107】
ユーザ入力がx={15,50,25}であるとする。上記と同じ公然のパラメータを用いて、ユーザ端末は、以下:
【数13】
のようにV及びRを計算する。
【0108】
分類器は、夫々の内部ノードについて、以下の値:
ノード1については、
【数14】
ノード2については、
【数15】
ノード3については、
【数16】
を得る。
【0109】
ランダム値は、実際のシステムにおいては、これらの例における値よりもずっと大きい点に留意すべきである。ここでは、簡単のために、小さい数が使用されている。
【0110】
ノード1に関し、分類器は、ΣM1=75を計算し、値os=75−10=65を送信する。ユーザ端末は、os−ΣR1=65−60=5を計算し、それが分裂規則f(x)>θを満足すると決定する(∵5<128)。従って、z1=1。
【0111】
ノード2に関し、分類器は、ΣM2=112を計算し、値os=112−75=37を送信する。ユーザ端末は、os−ΣR2=37−62=−25=358を計算し、それが分裂規則f(x)>θを満足しないと決定する(∵358>128)。従って、z1=0。
【0112】
ノード3に関し、ユーザは同様に、z3=0と決定する。
【0113】
このとき、関数g、すなわち分類決定は、オブリビアスに評価される。
【0114】
ユーザ端末は、以下:
【数17】
のようにV及びRを計算する。
【0115】
分類器は、以下の値:
【数18】
を得て、g(Z)=382z2+2を評価する。
【0116】
分類器は、ΣM=55を計算し、os=55+2=57を送信する。ユーザ端末は、os−ΣR=57−55=2を計算し、クラスはBであるとオブリビアスに決定する。
【0117】
明らかなように、各ノードでのOPEプロトコルは、分類器がx及び分裂決定を学習せず、且つ、ユーザ端末が分裂規則を学習しないことを確かにする。
【0118】
[コンピュータシステムの例]
図11は、ここで記載される動作の1又はそれ以上を実行することができる、例となるコンピュータシステムのブロック図である。図11を参照して、コンピュータシステム1100は、例となるクライアント又はサーバコンピュータシステムを有してよい。コンピュータシステム1100は、情報通信のための通信メカニズム又はバス1111と、情報処理のための、バス1111と結合されたプロセッサ1112とを有する。プロセッサ1112は、マイクロプロセッサを含むが、例えば、Pentium(登録商標)、PowerPC(登録商標)、Alpha(登録商標)等のマイクロプロセッサに限られない。
【0119】
システム1100は、更に、プロセッサ1112によって実行される命令及び情報を記憶するための、バス1111と結合されたランダムアクセスメモリ(RAM)又は他の動的記憶装置1104を有する。メインメモリ1104は、また、プロセッサ1112による命令の実行の間一時的に変数又は他の中間情報を記憶するためにも使用されてよい。
【0120】
コンピュータシステム1100は、また、プロセッサ1112のための静的な情報及び命令を記憶するための、バス1111と結合された読出専用メモリ(ROM)及び/又は他の静的記憶装置1106と、磁気ディスク又は光ディスク及びその対応するディスクドライブ等のデータ記憶装置1107とを有する。データ記憶装置1107は、情報及び命令を記憶するためにバス1111と結合されている。命令は、上記の動作を実行するために使用されてよい。
【0121】
コンピュータシステム1100は、更に、コンピュータユーザに情報を表示するための、バス1111と結合された陰極線管(CRT)又は液晶ディスプレイ(LCD)等のディスプレイ装置1121に結合されてよい。英数字及び他のキーを有する英数字入力装置1122も、情報及びコマンド選択をプロセッサ1112に伝えるためにバス1111と結合されてよい。更なるユーザ入力装置は、方向情報及びコマンド選択をプロセッサ1112に伝え、ディスプレイ装置1121でのカーソル移動を制御するための、バス1111と結合されたマウス、トラックボール、トラックパッド、スタイラス、又はカーソル方向キー等のカーソル制御部1123である。
【0122】
バス1111と結合される他の装置はハードコピー装置1124である。これは、用紙、フィルム、又は同様の媒体等の媒体に情報を残すために使用されてよい。バス1111と結合される他の装置は、電話機又は持ち運び可能な手のひらサイズの装置との通信のための有線/無線通信機能部1125である。
【0123】
システム1100及び関連するハードウェアの構成要素は本発明において使用されてよい点に留意すべきである。しかし、当然のことながら、他の構成のコンピュータシステムは一部又は全ての装置を有してよい。
【0124】
本発明の多くの代替案及び変形例は、きっと、上記の説明を読むことで当業者には明らかになるであろうが、当然のことながら、異例として図示及び記載される如何なる特定の実施形態も限定と見なされるべきではない。従って、様々な実施形態の詳細への言及は、本発明にとって必須と見なされる特徴のみを挙げる特許請求の範囲の適用範囲を限定するものではない。
【先行技術文献】
【非特許文献】
【0125】
【非特許文献1】M. O. Rabin、“How to Exchange Secrets with Oblivious Transfer”、Cryptology ePrint Archive、Report 2005/187、2005年、http://eprint.iacr.org/
【非特許文献2】S. Even等、“A Randomized Protocol for Signing Contracts”、Commun. ACM、28(6):637-647、1985年
【非特許文献3】M. Naor等、“Efficient Oblivious Transfer Protocols”、SODA’01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms、448-457頁、米国ペンシルベニア州フィラデルフィア、2001年、Society for Industrial and Applied Mathematics
【非特許文献4】M. Naor等、“Oblivious Transfer and Polynomial Evaluation”、SODA ’99: Proceedings of the thirtyfirst annual ACM symposium on Theory of computing、245-254頁、米国ニューヨーク州ニューヨーク、1999年、ACM
【非特許文献5】H. -D.Li等、“Oblivious Polynomial Evaluation”、J. Comput. Sci. Technol.、19(4):550-554、2004年
【非特許文献6】M. Naor等、“Oblivious Polynomial Evaluation”、SIAM J. Comput.、 35(5):1254-1281、2006年
【非特許文献7】Y. -C. Chang等、“Oblivious Polynomial Evaluation and Oblivious Neural Learning”、Teor. Comput. Sci.、341(1):39-54、2005年
【非特許文献8】P. Paillier、“Public-Key Cryptosystems Based On Composite Degree Residuosity Classes”、EUROCRYPT ’99: Proceedings of the 17th international conference on Theory and application cryptographic techniques、223-238頁、ベルリン、ハイデルベルク、1999年、シュプリンガー出版
【非特許文献9】T. El Gamal、“A Public Key Cryptosystem and a Signature Scheme Based On Discrete Logarithms”、Proceedings of CRYPTO 84 on Advances in cryptology、10-18頁、米国ニューヨーク州ニューヨーク、1985年、シュプリンガー出版
【符号の説明】
【0126】
1100 コンピュータシステム
1104 動的記憶装置
1106 静的記憶装置
1107 データ記憶装置
1111 バス
1112 プロセッサ
1121 ディスプレイ装置
1122 英数字入力装置
1123 カーソル制御部
1124 ハードコピー装置
【技術分野】
【0001】
本発明の実施形態は、分類器及び分類におけるその使用の分野に係り、より具体的には、本発明の実施形態は、安全且つオブリビアス(oblivious)な処理を用いる実施形態を含む、ツリーに基づく分類法及びデータ観測法を組み合わせることに係る。
【背景技術】
【0002】
クラウドコンピュータモデルは、主に、投資が不要であり、柔軟性があり、且つ運用コストが削減されることから、多くのビジネスを魅了している。クラウドコンピュータモデルは、企業がビジネスを行う方法を、利用ごとに支払うユーティリティモデルへと変えた。CaaS(Computing as a Service)は、企業が、実施許諾を受けたソフトウェアのコピー、自身の処理ロジック及び計算ハードウェアのセットアップを社内で有する必要なしに、計算能力及び処理ロジックを利用することができるクラウドコンピュータの新興のブランチである。演算処理の1タイプは、このような使用のための候補であるツリーに基づく分類である。データの指数関数的な成長に伴い、大容量のデータセットに対してパターン認識及びマイニングを行う真の必要性が存在する。
【0003】
たとえCaaSが多くの利点を提供するとしても、セキュリティ及びプライバシーに対する懸念は、依然として、多くの企業をクラウドへ移行させない主たる要因である。ユーザは、データを明らかにすることなく、サービスプロバイダがデータに対して演算処理を行うことを可能にする必要があるので、入力データを保護することは困難である。サービスとしての分類(classification as a service)は、サービスプロバイダがツリーをトレーニングするために使用するトレーニングセット及び分類器を保護する更なる課題を有する。
【0004】
以下のシナリオについて考える。ユーザ(クライアント)は画像の組(X)を有する。ユーザは、画像が例えば顔を含むかどうかを決定するために、画像を分類したいと望むことがある。ユーザは、画像を分類するための分類アルゴリズムを実行するリソース及び/又は技能を有していない。従って、ユーザは、分類タスクfを遠隔の分類器(クラウド内のサーバ)に委託し、決定f(x)(なお、x∈X)を得たいと望む。以下は、セキュリティ及びプライバシーの要求である。
1.ユーザは、画像(x個の値)を分類器に明らかにしたくない。
2.分類器は、f(x)から推論され得る情報以外、その分類アルゴリズムfをユーザに明らかにしたくない。
3.ユーザは、分類決定f(x)を分類器に学習させたくない。
【0005】
以下は、当該技術でよく知られている計算原理の幾つかに関する簡単な説明である。
【0006】
[計算原理]
・紛失通信(Oblivious Transfer)(OT)
2分の1(1-out-of-2)紛失通信(OT12)において、1つのパーティ、すなわち送信側は、2つの文字列(M0,M1)から成る入力を有し、第2のパーティ、すなわち選択側の入力は、ビットσである。選択側は、Mσを学習するべきであるが、M1−σについては何ら学習すべきでなく、一方、送信側は、σに関する情報を何も得るべきではない。N分の1紛失通信(OT1N)は、OT12の拡張であり、選択側は1つのMi(1≦i≦N)のみを学習する。N分のk紛失通信(OTkN)は、OT1Nの一般化である。更なる情報のために、M. O. Rabin、“How to Exchange Secrets with Oblivious Transfer”、Cryptology ePrint Archive、Report 2005/187、2005年、http://eprint.iacr.org/(非特許文献1)、S. Even等、“A Randomized Protocol for Signing Contracts”、Commun. ACM、28(6):637-647、1985年(非特許文献2)、及びM. Naor等、“Efficient Oblivious Transfer Protocols”、SODA’01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms、448-457頁、米国ペンシルベニア州フィラデルフィア、2001年、Society for Industrial and Applied Mathematics(非特許文献3)を参照されたし。
【0007】
・秘密多項式評価法(Oblivious Polynomial Evaluation)
秘密多項式評価法(OPE)プロトコルは2つのパーティ、すなわち、何らかの有限フィールド+pにわたる多項式fを有する送信側と、入力x∈+pを有する受信側とを有する。プロトコルの終わりに、受信側はf(x)のみを学習し、送信側は何も学習しない。OPEに関する更なる情報のために、M. Naor等、“Oblivious Transfer and Polynomial Evaluation”、SODA ’99: Proceedings of the thirtyfirst annual ACM symposium on Theory of computing、245-254頁、米国ニューヨーク州ニューヨーク、1999年、ACM(非特許文献4)、H. -D. Li等、“Oblivious Polynomial Evaluation”、J. Comput. Sci. Technol.、19(4):550-554、2004年(非特許文献5)、M. Naor等、“Oblivious Polynomial Evaluation”、SIAM J. Comput.、 35(5):1254-1281、2006年(非特許文献6)、及びY. -C. Chang等、“Oblivious Polynomial Evaluation and Oblivious Neural Learning”、Teor. Comput. Sci.、341(1):39-54、2005年(非特許文献7)を参照されたし。
【0008】
・準同型暗号化(Homomorphic Encryption)
非対称暗号化システムは、キー生成、暗号化(E)及び復号化(Δ)関数から成り、何らかの所与のパブリックキー及びプレーンテキスト空間における何らかの2つのプレーンテキストメッセージm1、m2に関し、以下の暗号化関係:
【数1】
が有効である場合に、準同型である。ここで、
(外1)
は2項演算子である。演算子が加算であるとき、暗号化システムは加法準同型であり(例えば、P. Paillier、“Public-Key Cryptosystems Based On Composite Degree Residuosity Classes”、EUROCRYPT ’99: Proceedings of the 17th international conference on Theory and application cryptographic techniques、223-238頁、ベルリン、ハイデルベルク、1999年、シュプリンガー出版(非特許文献8))、演算子が乗算であるとき、暗号化システムは乗法準同型である(T. El Gamal、“A Public Key Cryptosystem and a Signature Scheme Based On Discrete Logarithms”、Proceedings of CRYPTO 84 on Advances in cryptology、10-18頁、米国ニューヨーク州ニューヨーク、1985年、シュプリンガー出版(非特許文献9))。
【0009】
[紛失通信]
従来のOTプロトコルは全てパブリックキー暗号化(PKC)を必要とする。PKCは冪剰余(modular exponetiation)を伴う。従って、計算オーバヘッドは、その計算オーバヘッドよりも厳しい。ここで、OT12及びOT1Nの実施について記載する。これは、非特許文献3によって提案されているプロトコルに密接に従う。
【0010】
・1/2紛失通信
選択側の入力は、σ∈0,1であり、送信側の入力は、2つの文字列M0,M1である。選択側の出力は、Mσである。プロトコルは、素数位数(prime order)のグループ・qにわたって動作し、gは、該グループの生成元である。構文は、ランダムオラクルとしてモデル化される、すなわち、如何なる参加者も利用可能であり且つ例えばSHA等のハッシュ関数として通常は実施される真ランダム関数として選択される、関数Hを使用する。
【0011】
・エルガマル(ElGamal)暗号化を用いるプロトコル
1.送信側は、ランダム要素rs∈・qを選択し、それを公開する。
2.選択側は、ランダム要素rs∈・qをとり、パブリックキーPKσ=grc及びPK1−σ=rs/PKσを設定し、PK0を送信側に送る。
3.送信側は、PK1=rs/PK0を計算し、ランダム要素r1,r2∈・qを選択する。送信側は、
(外2)
としてE0によってM0を暗号化する(なお、
(外3)
は、ビット単位の2項演算子である。)とともに、
(外4)
を暗号化し、それらを選択側に送る。
4.選択側は、H((grσ)rc)=H(PKσrσ)を計算し、それを用いてMσを復号化する。
【0012】
同じr=r1=r2は、同レベルのプライバシー及びセキュリティを提供するために使用され得る。同じrによれば、送信側は、3つの累乗(うち1つは、プロトコルが始まる前に予め計算され得る。)を計算する必要があり、選択側は、2つの累乗(うち1つは予め計算され得る。)を計算する必要がある。qはnビット素数位数であるとすると、通信複雑度は2n(選択側から)+n+2log2|M|(送信側から)である。複雑度は、メッセージが・qの要素であり、且つ、1つのランダム値rが使用される場合に、5nである。
【0013】
[秘密多項式評価法]
非特許文献7によって紹介されているOPEプロトコルは、OT12を用いる。
【0014】
多項式は、有限フィールド+qにわたる。なお、qは、lビット素数である。受信側は入力x*∈+qを有し、送信側は、
(外5)
を有する。
【0015】
各係数aiは、以下:
【数2】
のように表される。
【0016】
夫々のi∈[1,d]及び夫々のj∈[1,l]について、受信側は、以下:
【数3】
のように値vijを計算する。
【0017】
夫々のi∈[1,d]について、以下:
【数4】
が適用できる点に留意すべきである。
【0018】
プロトコルがOT12を用いるならば:
1.受信側は、(rij,vij+rij)のdl個の対を用意する。なお、各rijは、+qからランダムに一様に選択される。
2.(rij,vij+rij)の各対ごとに、送信側は、aij=0の場合にはrijを、それ以外の場合にはvij+rijを得るよう、受信側とともにOT12を実行する。
3.送信側は、
【数5】
に等しいdlのOT12プロトコルの出力とa0との和を計算する。受信側は、送信側の出力から
(外6)
を減じて、f(x*)を得る。
【0019】
このプロトコルにおける支配的な動作は、OT12動作である。複雑度は、OT12の複雑性のdl倍である(OT12ごとに5つの累乗及び3つの逆演算)。
【0020】
加法準同型暗号化(HE)を用いるプロトコルは、以下の通りである:
1.受信側は、E(vij)のdl個の値を準備する。
2.Eijの各値ごとに、送信側は、aij=0の場合には1を、それ以外の場合にはE(vij)をとる。
3.送信側は、
【数6】
に等しいdl個の暗号化された値の出力とa0との和を計算する。受信側は、復号化して、f(x*)を得る。
【0021】
このプロトコルにおける支配的な動作は、HE動作である。複雑度は、暗号化の複雑度の2dl倍である(すなわち、暗号化ごとに1つの累乗)。最初のプロトコルと比較して、第2のアプローチにおける累乗の数は半分に減らされる。最初のプロトコルと比較して、暗号文空間がプレーンテキスト空間と同じであるとすると、第2のアプローチにおける通信複雑度は、3分の2だけ減らされる。
【0022】
上記に関連する更なる技術は、PPDM(Privacy Preserving Data Mining)を含む。PPDM研究において、主な焦点は、プライバシー及びセキュリティに対する懸念に対処しながら、集合的に予測モデルを学習することであった。かかる研究において、2つの主枝の問題が存在する。両主枝の最終目標は、予測モデルをトレーニングすることであるが、2つの主枝は異なる憶測を立て且つ異なる設定を有する。第1のカテゴリ(摂動入力の問題)は、データマイニング部、すなわち、分類器への入力を秘密のままとしながら、予測モデルを生成するという課題に対処する。第2のカテゴリ(非公開パーティ入力の問題)は、次の問題に対処する:入力データを有する幾つかのパーティが存在し、それは、集合的に、自分たちの入力データを他の関連するパーティに秘密にしながら、予測モデルを生成したいと望む。
【発明の概要】
【発明が解決しようとする課題】
【0023】
非公開パーティ入力の問題において、異なるパーティからの入力データは、水平又は垂直のいずれかの方向において分割される。水平分割されたデータによれば、各パーティは、考慮中の全ての機能に対する完全なデータ設定を有する。対照的に、垂直分割されたデータによれば、各パーティは、考慮中の機能に対する完全なデータ設定を有さない。すなわち、夫々が、完全なデータ設定を構成するよう部分的な入力データを有する。理想的な状況においては、データマイニング手順の終わりに、各パーティは、垂直又は水平に分割された自身のデータのみと、トレーニングされた予測モデルとを知っている。
【0024】
摂動入力の問題において、その名の通り、入力データを所有するユーザは、データマイニング処理の前に“ノイズ”(例えば、一般化、歪み、等)をデータに加え、次いで、原の累積部分(原の値ではない。)を回復するために再構成技術を用いる。ノイズは、分類器からデータを隠す。しかし、そのような方法が提供するプライバシー及びセキュリティのレベルを定量化することは困難である。更に、予測モデルは、ノイズに起因して同程度の偽陽性及び陰性を有する。摂動データから予測モデルを学習した後、モデルは非摂動データを分類することができる。ユーザ入力を保護するために、ユーザは、局所的に分類アルゴリズムを実行するために予測モデルを与えられる。かかるアプローチはユーザ入力のプライバシーを保つが、予測モデルを保護することはできない。
【0025】
従って、本発明は、上記を鑑み、ユーザと分類器との間で相互にプライバシー及びセキュリティを満足することができる、暗号化技術を用いたツリーに基づく分類のための方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【0026】
分類のための方法及び装置について開示する。一実施形態において、方法は、第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行うステップであって、前記第1の位置とは異なる第2の位置とデータを交換して、前記ユーザ入力を取得し、単準同型暗号化を用いてユーザに分類の結果を提供し、それにより、前記ユーザ入力が前記分類器に対して隠され、前記分類ツリーが前記ユーザに対して隠され、前記分類器の出力が前記分類器に対して隠されるようにするステップを有する。
【発明の効果】
【0027】
本発明の実施形態によれば、ユーザと分類器との間で相互にプライバシー及びセキュリティを満足することができる、暗号化技術を用いたツリーに基づく分類のための方法及び装置を提供することが可能となる。
【図面の簡単な説明】
【0028】
【図1】本願で用いられる表記法により決定ツリーの例を表す。
【図2】本願で記載されるアプローチを用いてデータを処理する工程の一実施形態のフロー図である。
【図3】分類器で実行されるアルゴリズムの一実施形態の擬似コードを表す。
【図4】線形な分類ツリーを用いてデータを分類する工程の一実施形態のフロー図である。
【図5】分類器を使用するときにユーザ端末によって行われる動作のアルゴリズムの一実施形態のための擬似コードである。
【図6】線形な分類ツリーを用いてデータを分類する工程の一実施形態のフロー図である。
【図7】各内部ノードでの分裂規則を評価するために分類器で実行されるアルゴリズムの一実施形態のための擬似コードである。
【図8】分類ツリーを用いて分類を行う分類器での分裂規則評価のための工程の一実施形態のフロー図である。
【図9】本願で使用される表記法により分類ツリーの例を表す。
【図10】図9の分類ツリーの例を表す。
【図11】コンピュータシステムのブロック図である。
【発明を実施するための形態】
【0029】
本発明は、本発明の様々な実施形態に係る以下に与えられる詳細な説明及び添付の図面から、より十分に理解されるであろう。なお、それらの実施形態は、本発明を具体的な実施形態に限定するものではなく、説明及び理解のためにのみ挙げられている。
【0030】
以下は、オブリビアスなツリーに基づく分類を行うための新規なアプローチを開示する。1つのアプローチは、紛失通信プロトコルに基づき、一方、他のアプローチは、加法準同型暗号化システムに基づく。一実施形態において、ツリーに基づく分類は、既存のプロトコルよりもずっと有効である新規な秘密多項式評価法プロトコルに基づく準同型暗号化と組み合わされる。一実施形態において、新しいプロトコルが構築され、実際的な暗号化技術が用いられ、それにより、暗号化されたデータに対する特定の算術演算の実行を可能にする。
【0031】
ここで記載される技術は、幾つかのモデルにおいて使用されてよい。
【0032】
以下の記載において、多数の詳細が、本発明のより完全な説明を提供するために示されている。しかし、当業者には当然のことながら、本発明は、それらの具体的な詳細によらずに実施されてよい。他の事例では、よく知られている構成及び装置は、本発明を不明りょうにすることを回避するために、詳細にというよりも、ブロック図形式において示されている。
【0033】
次の詳細な記載の幾つかの部分は、コンピュータメモリ内のデータビットに対する演算のアルゴリズム及びシンボル表現に関連して与えられている。それらのアルゴリズム的記述及び表現は、データ処理技術における当業者によって他の当業者に自身の研究の内容を最も効果的に伝えるために使用される手段である。アルゴリズムは、ここでは、概して、所望の結果をもたらすセルフコンシステントな一連のステップであると考えられる。ステップは、物理量の物理的処置を必要とするものである。通常、必然的ではないが、それらの量は、記憶され、転送され、結合され、比較され、且つ、別なふうに扱わされることが可能な電気的又は磁気的な信号の形態をとる。それらの信号をビット、値、要素、シンボル、文字、項、数等と呼ぶことは、主に公共的使用のために、時々便利である。
【0034】
しかし、それらの及び同様の用語の全ては、適切な物理量と関連づけられるべきであり、単にそれらの量に適用される便利なラベルに過ぎないことが、念頭に置かれるべきである。以下の議論から明らかなように、具体的に別なふうに述べられない限り、明細書全体を通じて、「処理」又は「演算」又は「計算」又は「決定」又は「表示」等の語を用いる議論は、コンピュータシステムのレジスタ及びメモリ内で物理(電子)量として表されるデータを扱い、コンピュータシステムのメモリ若しくはレジスタ又はその他情報記憶、送信又は表示装置等内の物理量として同様に表される他のデータに変換するコンピュータシステム又は同様の電子演算装置の動作又は処理をいう。
【0035】
また、本発明は、ここでは、演算を行うための装置に係る。この装置は、必要とされる目的のために特別に構成されてよく、あるいは、それは、コンピュータに記憶されるコンピュータプログラムによって選択的にアクティブにされ又は再構成される汎用のコンピュータを有してよい。そのようなコンピュータプログラムは、例えば、フロッピー(登録商標)ディスク、光ディスク、CD−ROM及び光磁気ディスクを含む何らかのタイプのディスク、読出専用メモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気若しくは光学カード、又は電子的な命令を記憶するのに適しており且つ夫々コンピュータシステムバスに結合されている何らかのタイプの媒体等の、しかしそれらに限定されないコンピュータ読出可能な記憶媒体に記憶されてよい。
【0036】
ここで提示されるアルゴリズム及び表示は、本質的に、何らかの特定のコンピュータ又は他の装置とは無関係である。様々な汎用システムが、ここでの教示に従うプログラムとともに使用されてよく、あるいは、必要とされる方法ステップを実行するためのより専門の装置を構成することが便利となりうる。様々なそのようなシステムのための必要とされる構成は、以下の記載から明らかである。更に、本発明は、何らかの特定のプログラミング言語を参照して記載されない。様々なプログラミング言語が、ここで記載される本発明の教示を実施するために使用されてよいことは、明らかである。
【0037】
機械読出可能な媒体は、機械(例えば、コンピュータ)によって読出可能な形で情報を記憶又は送信するための如何なるメカニズムも含む。例えば、機械読出可能な媒体には、読出専用メモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス等がある。
【0038】
[表記法]
【表1】
表1は、ここで使用される全てのシンボル及び表記を集約する。
【0039】
[ID3アルゴリズム]
最初に、単一変数線形決定のみを必要とする場合に2に設定された分岐因子を有するツリーに基づいて入力データを非公開で分類することに焦点を当てる。次いで、当該技術は、多変数決定ツリーに拡張される。
【0040】
以下が仮定される:
・分類ツリーは既に学習されている。
・分岐因子は2である。
・カテゴリ及びクラスラベルの数は公然である。
【0041】
2つのパーティが存在する。1つは、非公開の入力ベクトルx=(x1,x2,・・・,xn)tを有するユーザ端末であり、他は、トレーニングされた分類ツリーを有する分類器である。ユーザ端末は、全てのとり得るクラスラベルC={w1,w2,・・・,wt}から自身の入力のクラスラベルを見つけたいと望む。プライバシー及びセキュリティの要求は、以下の通りである。
1.ユーザ端末は、xを分類器に対して明らかにしたくない。
2.分類器は、ユーザ端末に対して分類ツリー、特に、ツリーによって計算される決定を明らかにしたくない。
3.ユーザ端末は、自身の入力についてのクラスラベルを分類器に対して明らかにしたくない。
【0042】
分類ツリーの一例が図1に示されている。
【0043】
多数のアプローチがここで提案されている。一実施形態において、OT12は、ツリーの内部ノードの評価のために使用される。他の実施形態において、加法準同型暗号化は、ツリーの内部ノードの評価のために使用される。これらのアプローチのいずれもが、クラスラベルの評価のために加法準同型暗号化を使用する。ここでの目的のために、前者は、OTに基づくアプローチと呼ばれ、後者は、HEに基づくアプローチと呼ばれる。
【0044】
図2は、2つのアプローチのいずれか一方を用いてデータを処理する工程の一実施形態のフロー図である。処理は、ハードウェア(回路、専用のロジック、等)、ソフトウェア(汎用のコンピュータシステム又は専用の機械で実行されるもの)、又はそれらの組み合わせを有する処理ロジックによって実行される。一実施形態において、処理ロジックは分類器の部分である。
【0045】
図2を参照すると、処理は、第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行う処理ロジックを有し、該処理ロジックは、第1の位置とは異なる第2の位置とデータを交換して、ユーザ入力を取得し、単準同型暗号化を用いてユーザ端末に分類の結果を提供することを含み、それにより、ユーザ入力は分類器に対して隠され、分類ツリーがユーザ端末に対して隠される(処理ブロック201)。一実施形態において、単準同型暗号化(singly homomorphic encryption)は、分類のための重みと、入力のビット単位の多項式表現とを用いる。一実施形態において、多項式表現は、和として多項式を表す。一実施形態において、単準同型暗号化は、加法準同型暗号化を有する。一実施形態において、単準同型暗号化は、準同型暗号化に基づく秘密多項式評価法プロトコルを有する。
【0046】
[OTに基づくアプローチ]
ユーザ端末は、分類器と協働して、分類ツリーにおける各ノードごとにOPEプロトコルを実行する。分類器は、ユーザ端末が分類ツリーにおけるノードの相対位置を学習しないように、一様にランダムにノードを選択する。一般性を失うことなく、分類ノードにおけるノードが、何らかの決定論的だがランダムな順序で、1からmまでインデックスを付されるとする。ノードiでのn次元の特徴ベクトルはyi={y1,y2,・・・,yn}であるとする。各ノードiでの分裂規則fiは形式xtyi≦θiを有するとする。なお、θiは閾値である。一実施形態において、関数fは、この技術の使用前に与えられる。それは、顔や、頁上の書式に対するマーク等の分類器であってよい。一実施形態において、特定の関数は、決定ツリーにおけるノードにおいて実施される。ツリーは前もってトレーニングされている。一実施形態において、関数のクラスは、「一次関数」又は「ドット積関数」である。それらは、決定ツリーにおいて最も幅広く使用されている。
【0047】
ランダム関数fi(x,yi,θi)→{0,1}を用いてノードiでの分裂規則を表すことができる。ここで、1は、分裂規則が満足されたこと(すなわち、「はい(yes)」)を示す。関数fiは:
【数7】
のように定義されてよい。
【0048】
ユーザ端末は、分類器と協働してm回のOPEプロトコルを実行し、ユーザ端末は、各ノードインデックスiごとに0又は1(fiの出力であり何ものでもない。)のいずれかを学習し、分類器は、ユーザ端末の入力及び出力に関して何も学習しない。最後に、ユーザ端末は、全ての出力のビットベクトルZを構成し、オブリビアスにクラスラベルを学習するよう分類器とともに他のプロトコルを実行する。
【0049】
上記の方法により最終的な分類決定(すなわち、分類ツリーにおいてリーフノードに割り当てられるクラス)をオブリビアスに評価するために、各内部ノードでオブリビアスに評価される二分決定(binary decisions)を多項式に変換する必要がある。しかし、このシナリオのために多項式を構成することは、可能性の数が内部ノードの数mとともに指数関数的に増大するので、分類ツリーに2、3のノードしか存在しない簡単な場合を除いて、一般的に、法外に費用がかかる。従って、一実施形態において、大きな分類ツリーに対して加法準同型暗号化システムを用いてオブリビアスにクラスを得るための別の技術が使用される。
【0050】
分類ツリーにおける各経路ごとに、ユーザ端末は、以下のように2つのベクトルZ’及びZ”を計算し、分類器に与える:
【数8】
ここで、Eは加法準同型暗号化であり、且つ、1≦i≦mである。各経路はリーフノード及びその関連するクラスに対応する点に留意すべきである。ユーザ端末はプライベートキーを有する。分類器は乱数r∈・pを選択する。
【0051】
インデックスjを有する経路tでの各ノードごとに、分類器は、分類決定に依存してZ’[j]又はZ”[j]をとり、(Z’[j])r又は(Z”[j])rを計算する。分類器は、各経路に沿って(ルートからリーフノードまで)全てのインデックスについて計算値を乗じる。この値は、ここでは、utと呼ばれる。分類器は、
vt=ut×E(−h×r)×E(wt)
を計算する。ここで、hは、経路における内部ノードの数(すなわち、ツリー高さ)であり、wtは、経路t(1≦t≦P)のリーフノードに関連するクラスラベルであり、P回の別々の乗算を実行する。分類器は、ベクトルV={v1,v2,・・・,vP}を生成する。ユーザ端末がベクトルVの各要素を復号化するとき、クラス値の領域にはただ1つの要素しか存在せず、従って、ユーザ端末は、自身の入力xについて対応するクラスを得る。
【0052】
分類器は、付加的な計算及び通信費用を擬制にして、更に分類ツリーを隠すよう偽のノードを導入してよい。
【0053】
・複雑性の分析
以下は、分類ツリーにおける内部ノードのハイレベルな複雑性分析を示す。n個の特徴及びm個の内部ノードが存在する。完全なOTに基づくアプローチのためのプロトコルが素数位数の有限フィールド+pにわたって動作し、且つ、属性値がlビット(0−2l)であるとする。同じOPEプロトコルは、n個の一次(d=1)多項式の集合として各fiを考えることによって、適用される。OT12を用いるOPEプロトコルに関し、全部でnmdl=mnl回のOT12動作が実行される。すなわち、おおよそ5nml回の累乗及び6nmllog2|p|ビットである。HEを用いるOPEプロトコルに関し、全部で2nl回のHE動作が実行される。すなわち、2nl回の累乗及び2nllog2|p|ビットである。後者の複雑性は、暗号化される値が再利用され得るので、mとは無関係である点に留意すべきである(加算、乗算、及び除算の各演算は、上記の分析においては考慮されない点に留意すべきである。)。
【0054】
・プロトコルの例
図3は、分類器で実行されるアルゴリズムの一実施形態の擬似コードを表す。そのような擬似コードは、当業者にはよく理解されている。
【0055】
図4は、線形な分類ツリー(例えば、決定ツリー)を用いてデータを分類する工程の一実施形態のフロー図である。処理は、ハードウェア(回路、専用のロジック、等)、ソフトウェア(汎用のコンピュータシステム又は専用の機械で実行されるもの)、又はそれらの組み合わせを有する処理ロジックによって実行される。一実施形態において、処理ロジックは分類器の部分であってよい。処理ロジックは、図3において記載される擬似コードを実施する命令を実行してよい。
【0056】
図4を参照して、処理は、処理ロジックが第1の暗号化された入力データを受信することによって開始する(処理ブロック401)。一実施形態において、第1の暗号化された入力データは、加法準同型暗号化システムによりビット単位で暗号化された入力データを有する。
【0057】
次に、処理ロジックは、分類ツリーの各ノードごとに、第1の暗号化されたデータを用いて、分類器により関数を計算する(処理ブロック402)。一実施形態において、分類ツリーは、決定ツリーを有する。一実施形態において、決定ツリーは、1又はそれ以上の多重特徴分裂(multiple-feature split)を有する多変数ツリーである。一実施形態において、決定ツリーは不平衡である。一実施形態において、決定ツリーは、1又はそれ以上の1/2分裂を含む。一実施形態において、関数は分裂規則を表す。
【0058】
分類ツリー上の各ノードごとに関数を計算した後、処理ロジックは、その各ノードごとに関数を計算した結果の暗号化されたバージョンを有する第2の暗号化されたデータを送信する(処理ブロック403)。
【0059】
その後、処理ロジックは、第1及び第2の暗号化されたベクトルを受信する(処理ブロック404)。第1の暗号化されたベクトルは、分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含み、第2の暗号化されたベクトルは、分類ツリーにおける各ノードでの分類決定を含むベクトルの余(complementary)を含む。相補的な2進ベクトルは、各“0”エントリが“1”により置換され、各“1”エントリが“0”により置換されるものである点に留意すべきである。一実施形態において、第1及び第2の暗号化されたベクトルは、P次元の暗号化された2進ベクトルである。一実施形態において、第2の暗号化されたデータにおける各ノードと関連する暗号化されたデータの順序は、分類ツリーにおけるノード位置を示さない。一実施形態において、分類決定は分裂決定を有する。
【0060】
第1及び第2の暗号化されたベクトルのデータを用いて、分類ツリーにおける経路内の夫々のノードについて、処理ロジックは、その各ノードでの分類決定に基づき第1及び第2の暗号化されたベクトルのいずれかから値を選択し、その値に基づく値のベクトルを第1及び第2の暗号化されたベクトルから選択される値を用いて計算する(処理ブロック405)。一実施形態において、値のベクトルを計算することは、経路におけるノードの数、該経路におけるノードと関連するクラスラベル、値のベクトル及び暗号化関数を用いて行われる。暗号関数は、値のベクトルを暗号化するために使用される同じ準同型暗号化関数であってよい(例えば、パイエ(Pailler)準同型暗号化システム)。
【0061】
その後、処理ロジックは値のベクトルを送信し、該値のベクトルから、分類ツリーにおけるノードに割り当てられる対応するクラスが得られる(処理ブロック406)。
【0062】
[HEに基づくアプローチ]
ハイレベルな技術は、ユーザ端末が、加法準同型暗号化システムを用いて入力データxをビット単位で暗号化し、分類器が、それらの暗号化された値を用いて、夫々のノードiについて暗号データに対してxtyi−θiを計算することである。ユーザ端末は、各ノードでの分裂決定を決定するために、それらの暗号化された値を復号化する。OTに基づくアプローチとは異なり、内部ノードを評価するためのユーザ端末における作業の量は、分類ツリーにおけるノードの数mとは無関係であり、このことはユーザ端末における計算費用を大いに削減する点に留意すべきである。ビットベクトルZが計算されると、クラスラベルの評価は、OTに基づくアプローチにおいて先に記載されたものと同様である。
【0063】
より具体的には、xに含まれる要素に関し、ユーザ端末は、OPEプロトコルにおいて見られるようにvij値を計算し、次いで、ユーザ端末で起動される加法準同型暗号化システムにより各vij値を暗号化する(すなわち、ユーザ端末はプライベートキーを有する。)。ユーザ端末は、n×l個の暗号化されたvijを分類器に送る。yiに含まれる夫々の要素に関し、分類器は、xtyiを計算するために、要素の非零ビット位置に基づき正しい暗号化されたvijをとり、それらを掛け合わせる。分類器は、それにθiの暗号化された加法逆(additive inverse)を乗じることによって、閾値θiを減じる。夫々のノードiに関し、分類器は上記の計算を行って、m個の暗号化された要素のベクトルを用意する。ユーザ端末はこのベクトルを復号化し、各ノードでの分裂決定を示すビットベクトルZを計算する。ユーザ端末と分類器との間の残りの相互作用は、上記のOTアプローチと同様である。このアプローチは、加法準同型暗号化システムの利用可能性にのみ依存する点に留意すべきである。
【0064】
・プロトコルの例
図5は、分類器を用いる場合にユーザ端末によって行われる動作のアルゴリズムの一実施形態のための擬似コードである。
【0065】
図6は、線形な分類ツリー(例えば、決定ツリー)を用いてデータを分類する工程の一実施形態のフロー図である。処理は、ハードウェア(回路、専用のロジック、等)、ソフトウェア(汎用のコンピュータシステム又は専用の機械で実行されるもの)、又はそれらの組み合わせを有する処理ロジックによって実行される。一実施形態において、処理ロジックは、分類器と通信しているクライアント(すなわち、分類器にアクセスしている及び/又は分類器を使用している装置又はサービス)の部分である。処理ロジックは、図5において記載される擬似コードを実施する命令を実行してよい。
【0066】
図6を参照して、処理は、処理ロジックが、暗号化された入力データを生成するために加法準同型暗号化システムを用いて入力データのビット単位の暗号化を実行することによって、開始する(処理ブロック601)。処理ロジックは、この情報を分類器に送信する。
【0067】
その後、処理ロジックは、分類器から、入力データを用いて分類ツリーの各ノードでの分類決定を評価した結果を含むベクトルを受信する(処理ブロック602)。
【0068】
ベクトルに含まれるデータを用いて、処理ロジックは、分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、分類ツリーにおける各ノードでの分類決定を含むベクトルの余を含む第2の暗号化されたベクトルとを生成し(処理ブロック603)、第1及び第2の暗号化されたベクトルを分類器に送信する(処理ブロック604)。
【0069】
次に、処理ロジックは、分類器から、第1及び第2の暗号化されたベクトルを用いて分類器によって計算された暗号化されたクラスラベルを受信する(処理ブロック605)。この情報から、処理ロジックは、入力データについてのクラスラベルを検出する(処理ブロック606)。
【0070】
図7は、各内部ノードでの分裂規則を評価する分類器で実行されるアルゴリズムの一実施形態のための擬似コードである。
【0071】
図8は、分類ツリー(例えば、決定ツリー)を用いて分類を行う分類器での分裂規則評価のための工程の一実施形態のフロー図である。処理は、ハードウェア(回路、専用のロジック、等)、ソフトウェア(汎用のコンピュータシステム又は専用の機械で実行されるもの)、又はそれらの組み合わせを有する処理ロジックによって実行される。一実施形態において、処理ロジックは分類器の部分である。処理ロジックは、図7において記載される擬似コードを実施する命令を実行してよい。
【0072】
図8を参照して、処理は、処理ロジックが、加法準同型暗号化システムを用いて入力データを暗号化することで生成された暗号化された入力データを受信することによって、開始する(処理ブロック801)。
【0073】
暗号化された入力データを用いて、処理ロジックは、少なくとも、分類ツリーにおける各ノードごとに暗号データに対する関数を計算し、その各ノードごとに関数を計算した結果を用いて複数の要素を有する出力ベクトル生成し、該出力ベクトルをユーザ端末に送信することによって、分類ツリーの各ノードでの分類決定を評価する(処理ブロック802)。一実施形態において、分類ツリーは、決定ツリーを有する。一実施形態において、決定ツリーは、1又はそれ以上の多重特徴分裂を有する多変数ツリーである。一実施形態において、決定ツリーは不平衡である。一実施形態において、決定ツリーは、1又はそれ以上の1/2分裂を含む。一実施形態において、分類決定は、分裂決定を有する。一実施形態において、関数は、分裂規則を表す。
【0074】
その後、処理ロジックは、分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、分類ツリーにおける各ノードでの分類決定を含むベクトルの余を含む第2の暗号化されたベクトルとを受信する(処理ブロック803)。
【0075】
第1及び第2の暗号化されたベクトルを用いて、処理ロジックは、分類ツリーにおける経路内の夫々のノードについて、その各ノードでの分類決定に基づき第1及び第2の暗号化されたベクトルのいずれかから値を選択し、その値に基づく値のベクトルを計算する(処理ブロック804)。
【0076】
その後、処理ロジックは値のベクトルを送信し、該値のベクトルから、分類ツリーにおけるノードに割り当てられる対応するクラスが得られる(処理ブロック805)。
【0077】
・複雑性の分析
内部ノードの評価のために、ユーザ端末は、nl回の準同型暗号化演算を実行する。夫々の内部ノードについて、分類器は、最悪の場合に、1回の準同型暗号化演算及びn+1回の剰余乗算(modular multiplication)を実行する。全体として、分類器は、内部ノードを評価するために、m回の暗号化及び(n−1)m回の剰余乗算を実行する。リーフノードの評価のために、ユーザ端末は、m回の復号化及び2m回の暗号化を実行し、分類器は、(h+1)P回の剰余乗算及びP回の暗号化を実行する。全体として、ユーザ端末は、nl+2m個の暗号文を送信し、分類器は、m+P個の暗号文を送信する。
【0078】
法nの下で、剰余乗算がO(logn)をとり、冪剰余がO(nlogn)をとるとする。法nを有するパイエ暗号化システムが使用される場合、ユーザ端末における全体の計算複雑度は、
O((nl+2m+m)p2logp2)=O((nl+3m)p2logp2)
であり、分類器は、
O((m+P)p2logp2+((n+1)m+(h+1)P)logp2)
=O((m+P)p2logp2+(nm+hP)logp2)
である。
【0079】
全体の通信複雑度は、O((nl+2n+m+P)logp2)ビットである。
【0080】
・多変数決定ツリー
HEに基づくアプローチ位は、多変数決定ツリーにおける各ノードで複数の特徴を有する線形決定を評価するために容易に拡張され得る点に留意すべきである。その場合に、各yiは、1又はそれ以上の非零要素を有する。ユーザ端末においては複雑性に対する課題は存在しないが、分類器での計算複雑性は増大する。夫々のノードについて、最悪の場合に、分類器は、単変量の場合のO(n)倍の計算を行う必要がある。
【0081】
[例]
幾つかの例が、基本的なアプローチを明らかにするために、以下で与えられる。それらの例は、主に、OTに基づくアプローチに係るが、自明に、HEに基づくアプローチに転用され得る点に留意すべきである。
【0082】
・ハイレベルな例
分類ツリーが図9において見られるようなものである簡単な例を考える。3つの特徴x1、x2、x3と、2つのクラスラベルA、Bとが存在する。
【0083】
以下:
ノード1に関し、
y1={1,0,0}、f1(x,y1,θ1)=r1x1−r1θ1、
ノード2に関し、
y2={0,1,0}、f2(x,y2,θ2)=r2x2−r2θ2、
ノード3に関し、
y3={0,1,0}、f3(x,y3,θ3)=r3x2−r3θ3
を有する。
【0084】
これは比較的簡単な例であるから、関数は、最終出力を決定し且つOPEを使用するために構成される。関数はgであるとする。関数gは、以下の入力表2に従う(表は更に簡略化さえ得る点に留意すべきである。)。
【表2】
【数9】
【0085】
ユーザ端末は、ベクトルZ={z1,z2,z3}を評価し、クラスを得るためにそれらの値をg(Z)に代入する。
【0086】
・詳細例1−OPE及び1つの分裂規則の評価
以下は、パラメータである。目的は、分類ツリーにおけるノードでの分裂の充足可能性をオブリビアスに評価することである。
・p=383(9ビット素数)
・g=379(乗法サイクルグループZ383*の生成元)
・q=128(稼動すべき比較プロトコルに関し、q<p/2。qの長さ、l=7ビット)
・f(x)=5x(次数d=1)。
【0087】
ユーザ端末は値x=3を有し、分類器の閾値θ=10であるとする。閾値は、当該技術において標準である分類器の設計に基づく点に留意すべきである。プロトコルの目的は、ユーザ端末が、出力又は入力のいずれも分類器に知らせることなく、f(x)−θの値(符号)を知ることである。OPEプロトコルによらずに、答えは、5×3−10=5である。
【0088】
ユーザ端末は、以下の行列Vを計算する(この場合に、fの次数が1であるから、Vはベクトルである。)。ここで、v(i,j)=2j−1・viであり、iは指数であり、jはビット位置である。すなわち、
V=(20・3 21・3 22・3 23・3 24・3 25・3 26・3)
=(3 6 12 24 48 96 192)
である。
【0089】
また、ユーザ端末は、以下のランダム値行列R:
R=(11 16 1 12 3 5 2)
を計算する。各値はq/dl、すなわち128/7によって境界され、Vに含まれる値と一対一の対応を有する。
【0090】
分類器は、係数のj番目のビットの値に依存して、夫々の係数iについて、rij又はvijのいずれかを得る。ユーザ端末は、分類器がl=7回のOT12プロトコルを通じてこの演算を行うので、分類器がどの成分を得るのかを知らない。従って、ユーザ端末は、f(x)の係数5を知らない。同時に、分類器は、夫々のOT12プロトコルについてユーザ端末によって送信される2つの値のうち1つの値しか知らないので、ユーザ端末での入力値x=5を知らない。
【0091】
分類器は、最初に、係数ビット行列C:
C=(1 0 1 0 0 0 0)
を構成する。cijは、係数iのj番目のビットの値である。
【0092】
OT12を用いて、分類器は、第1及び第3の係数のみが非零であるから、以下の値:
M=(3+11 16 12+1 3 5 2)
を得る。従って、分類器は、Mにおいてそれら2つの位置についてはvij及びrijをとり、他の位置についてはvijのみをとる。
【0093】
分類器はΣmij=65を計算し、値os=65−10=55を送信する。ユーザ端末は、os−Σrij=55−50=5を計算し、それが分裂規則f(x)>tを満足すると決定する(∵5<128)。分類器は、最終のクラスラベルが、ユーザ端末のみが知っているランダム値内に隠されているので、分裂決定を知らない点に留意すべきである。
【0094】
・詳細例2−OPE及び1つの分裂規則の評価
ユーザ端末の値xを除いて、詳細例1におけるあらゆることが本例についても変わらないままである。ここで、x=1とする。
【0095】
ユーザ端末は、以下の値:
V=(1 2 4 8 16 32 64)
R=(13 11 2 13 5 4 1)
を計算する。
【0096】
分類器は、以下の値:
M=(1+13 11 4+2 13 5 4 1)
を得る。
【0097】
分類器は、Σmij=54を計算し、値os=54−10=44を送信する。ユーザ端末は、os−Σrij=44−49=−5=378を計算し、それが分裂規則f(x)>θを満足しないと決定する(∵378>128)。
【0098】
・詳細例3−OPE及び1つの分裂規則の評価(より高い次数)
関数f(x)を除いて、詳細例1におけるあらゆることが本例についても変わらないままである。f(x)=5x+2x2(d=2)とする。上記の例は全て、一次多項式を用いるが、本例では、二次多項式が用いられる。自明に、これをより高い次数の多項式に拡張することができる。
【0099】
ユーザ端末は、以下の値:
【数10】
を計算する。
【0100】
分類器は、OT12プロトコルにより、以下の値:
【数11】
を得る。
【0101】
分類器は、Σi,jmij=54を計算し、値os=93−10=83を送信する。ユーザ端末は、os−Σr(i、j)=83−60=33を計算し、それが分裂規則f(x)>θを満足すると決定する(∵33<128)。
【0102】
値83は、充足可能性に関して何も分類器に示さない点に留意すべきである。例えば、ランダム値の和は、分類器の出力よりも大きいことがあり、この場合には、ユーザ端末での入力は、分類器出力が128よりも小さい場合でさえ、分裂規則を満足しない。
【0103】
・詳細例4−簡単な分類ツリー
図10は、考慮中の簡単な分類ツリーを示す。図10を参照して、3つの成分x1、x2、x3が存在する。2つのクラスラベルA及びBは、夫々、1及び2としてエンコードされる。分裂規則出力は2進値であり、1は、ユーザ端末での入力が形式xi>θiの分類規則を満足することを示す。
【0104】
この例は、多変数の場合を扱う。具体的に、関数は、1次関数の集合として形成される。
【0105】
gは上記の決定関数であるとする。表2を用いて、gは、以下:
【数12】
のように求められる。ここでziは、ノードiでの規則の充足可能性である。
【0106】
第1に、どのようにユーザ端末が分類ツリーの内部ノードをオブリビアスに評価するのかが検討される。ユーザ端末及び分類器は、以下のような集合アプローチ(aggregated approach)において3つのOPEプロトコルを実行する。
【0107】
ユーザ入力がx={15,50,25}であるとする。上記と同じ公然のパラメータを用いて、ユーザ端末は、以下:
【数13】
のようにV及びRを計算する。
【0108】
分類器は、夫々の内部ノードについて、以下の値:
ノード1については、
【数14】
ノード2については、
【数15】
ノード3については、
【数16】
を得る。
【0109】
ランダム値は、実際のシステムにおいては、これらの例における値よりもずっと大きい点に留意すべきである。ここでは、簡単のために、小さい数が使用されている。
【0110】
ノード1に関し、分類器は、ΣM1=75を計算し、値os=75−10=65を送信する。ユーザ端末は、os−ΣR1=65−60=5を計算し、それが分裂規則f(x)>θを満足すると決定する(∵5<128)。従って、z1=1。
【0111】
ノード2に関し、分類器は、ΣM2=112を計算し、値os=112−75=37を送信する。ユーザ端末は、os−ΣR2=37−62=−25=358を計算し、それが分裂規則f(x)>θを満足しないと決定する(∵358>128)。従って、z1=0。
【0112】
ノード3に関し、ユーザは同様に、z3=0と決定する。
【0113】
このとき、関数g、すなわち分類決定は、オブリビアスに評価される。
【0114】
ユーザ端末は、以下:
【数17】
のようにV及びRを計算する。
【0115】
分類器は、以下の値:
【数18】
を得て、g(Z)=382z2+2を評価する。
【0116】
分類器は、ΣM=55を計算し、os=55+2=57を送信する。ユーザ端末は、os−ΣR=57−55=2を計算し、クラスはBであるとオブリビアスに決定する。
【0117】
明らかなように、各ノードでのOPEプロトコルは、分類器がx及び分裂決定を学習せず、且つ、ユーザ端末が分裂規則を学習しないことを確かにする。
【0118】
[コンピュータシステムの例]
図11は、ここで記載される動作の1又はそれ以上を実行することができる、例となるコンピュータシステムのブロック図である。図11を参照して、コンピュータシステム1100は、例となるクライアント又はサーバコンピュータシステムを有してよい。コンピュータシステム1100は、情報通信のための通信メカニズム又はバス1111と、情報処理のための、バス1111と結合されたプロセッサ1112とを有する。プロセッサ1112は、マイクロプロセッサを含むが、例えば、Pentium(登録商標)、PowerPC(登録商標)、Alpha(登録商標)等のマイクロプロセッサに限られない。
【0119】
システム1100は、更に、プロセッサ1112によって実行される命令及び情報を記憶するための、バス1111と結合されたランダムアクセスメモリ(RAM)又は他の動的記憶装置1104を有する。メインメモリ1104は、また、プロセッサ1112による命令の実行の間一時的に変数又は他の中間情報を記憶するためにも使用されてよい。
【0120】
コンピュータシステム1100は、また、プロセッサ1112のための静的な情報及び命令を記憶するための、バス1111と結合された読出専用メモリ(ROM)及び/又は他の静的記憶装置1106と、磁気ディスク又は光ディスク及びその対応するディスクドライブ等のデータ記憶装置1107とを有する。データ記憶装置1107は、情報及び命令を記憶するためにバス1111と結合されている。命令は、上記の動作を実行するために使用されてよい。
【0121】
コンピュータシステム1100は、更に、コンピュータユーザに情報を表示するための、バス1111と結合された陰極線管(CRT)又は液晶ディスプレイ(LCD)等のディスプレイ装置1121に結合されてよい。英数字及び他のキーを有する英数字入力装置1122も、情報及びコマンド選択をプロセッサ1112に伝えるためにバス1111と結合されてよい。更なるユーザ入力装置は、方向情報及びコマンド選択をプロセッサ1112に伝え、ディスプレイ装置1121でのカーソル移動を制御するための、バス1111と結合されたマウス、トラックボール、トラックパッド、スタイラス、又はカーソル方向キー等のカーソル制御部1123である。
【0122】
バス1111と結合される他の装置はハードコピー装置1124である。これは、用紙、フィルム、又は同様の媒体等の媒体に情報を残すために使用されてよい。バス1111と結合される他の装置は、電話機又は持ち運び可能な手のひらサイズの装置との通信のための有線/無線通信機能部1125である。
【0123】
システム1100及び関連するハードウェアの構成要素は本発明において使用されてよい点に留意すべきである。しかし、当然のことながら、他の構成のコンピュータシステムは一部又は全ての装置を有してよい。
【0124】
本発明の多くの代替案及び変形例は、きっと、上記の説明を読むことで当業者には明らかになるであろうが、当然のことながら、異例として図示及び記載される如何なる特定の実施形態も限定と見なされるべきではない。従って、様々な実施形態の詳細への言及は、本発明にとって必須と見なされる特徴のみを挙げる特許請求の範囲の適用範囲を限定するものではない。
【先行技術文献】
【非特許文献】
【0125】
【非特許文献1】M. O. Rabin、“How to Exchange Secrets with Oblivious Transfer”、Cryptology ePrint Archive、Report 2005/187、2005年、http://eprint.iacr.org/
【非特許文献2】S. Even等、“A Randomized Protocol for Signing Contracts”、Commun. ACM、28(6):637-647、1985年
【非特許文献3】M. Naor等、“Efficient Oblivious Transfer Protocols”、SODA’01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms、448-457頁、米国ペンシルベニア州フィラデルフィア、2001年、Society for Industrial and Applied Mathematics
【非特許文献4】M. Naor等、“Oblivious Transfer and Polynomial Evaluation”、SODA ’99: Proceedings of the thirtyfirst annual ACM symposium on Theory of computing、245-254頁、米国ニューヨーク州ニューヨーク、1999年、ACM
【非特許文献5】H. -D.Li等、“Oblivious Polynomial Evaluation”、J. Comput. Sci. Technol.、19(4):550-554、2004年
【非特許文献6】M. Naor等、“Oblivious Polynomial Evaluation”、SIAM J. Comput.、 35(5):1254-1281、2006年
【非特許文献7】Y. -C. Chang等、“Oblivious Polynomial Evaluation and Oblivious Neural Learning”、Teor. Comput. Sci.、341(1):39-54、2005年
【非特許文献8】P. Paillier、“Public-Key Cryptosystems Based On Composite Degree Residuosity Classes”、EUROCRYPT ’99: Proceedings of the 17th international conference on Theory and application cryptographic techniques、223-238頁、ベルリン、ハイデルベルク、1999年、シュプリンガー出版
【非特許文献9】T. El Gamal、“A Public Key Cryptosystem and a Signature Scheme Based On Discrete Logarithms”、Proceedings of CRYPTO 84 on Advances in cryptology、10-18頁、米国ニューヨーク州ニューヨーク、1985年、シュプリンガー出版
【符号の説明】
【0126】
1100 コンピュータシステム
1104 動的記憶装置
1106 静的記憶装置
1107 データ記憶装置
1111 バス
1112 プロセッサ
1121 ディスプレイ装置
1122 英数字入力装置
1123 カーソル制御部
1124 ハードコピー装置
【特許請求の範囲】
【請求項1】
第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行うステップであって、前記第1の位置とは異なる第2の位置とデータを交換して、前記ユーザ入力を取得し、単準同型暗号化を用いてユーザに分類の結果を提供し、それにより、前記ユーザ入力が前記分類器に対して隠され、前記分類ツリーが前記ユーザに対して隠され、前記分類器の出力が前記分類器に対して隠されるようにするステップを有する方法。
【請求項2】
前記単準同型暗号化は、分類のために入力のビット単位の多項式表現を用いる、
請求項1に記載の方法。
【請求項3】
前記多項式表現は、多項式を和として表す、
請求項2に記載の方法。
【請求項4】
前記単準同型暗号化は、加法準同型暗号を有する、
請求項1に記載の方法。
【請求項5】
前記単準同型暗号化は、秘密多項式評価法プロトコルに基づく準同型暗号を有する、
請求項1に記載の方法。
【請求項6】
コンピュータ読出可能なコードを記憶したコンピュータ読出可能な媒体を有する装置であって、
前記コンピュータ読出可能なコードは、システムによって実行される場合に、該システムに、
第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行うステップであって、前記第1の位置とは異なる第2の位置とデータを交換して、前記ユーザ入力を取得し、単準同型暗号化を用いてユーザに分類の結果を提供し、それにより、前記ユーザ入力が前記分類器に対して隠され、前記分類ツリーが前記ユーザに対して隠され、前記分類器の出力が前記分類器に対して隠されるようにするステップ
を実行させる、装置。
【請求項7】
第1の暗号化された入力データを受信するステップと、
分類ツリーの各ノードごとに、前記第1の暗号化されたデータを用いて、分類器により関数を計算するステップと、
前記各ノードごとに前記関数を計算した結果の暗号化されたバージョンを有する第2の暗号化されたデータを送信するステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを受信するステップと、
前記分類ツリーにおける経路内の各ノードごとに、該各ノードでの分類決定に基づき前記第1の暗号化されたベクトル又は前記第2の暗号化されたベクトルのいずれかから値を選択し、該値に基づく値のベクトルを前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルから選択される値を用いて計算するステップと、
前記分類ツリーにおいてモードに割り当てられる対応するクラスが得られる前記値のベクトルを送信するステップと
を有する方法。
【請求項8】
前記分類ツリーは、1又はそれ以上の多重特徴分裂を有する多変数ツリーである、
請求項7に記載の方法。
【請求項9】
前記分類ツリーは、不平衡である、
請求項7に記載の方法。
【請求項10】
前記分類ツリーは、1又はそれ以上の1/2分裂を含む、
請求項7に記載の方法。
【請求項11】
前記分類決定は、分裂決定を有する、
請求項7に記載の方法。
【請求項12】
前記関数は、分裂規則を表す、
請求項7に記載の方法
【請求項13】
前記第2の暗号化されたデータにおける各ノードと関連する暗号化されたデータの順序は、前記分類ツリーにおけるノード位置を示さない、
請求項7に記載の方法。
【請求項14】
前記第1の暗号化された入力データは、加法準同型暗号システムを用いてビット単位で暗号化されている入力データを有する、
請求項7に記載の方法。
【請求項15】
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルは、P次元の暗号化された2進ベクトルである、
請求項7に記載の方法。
【請求項16】
前記値のベクトルを計算することは、経路におけるノードの数、該経路におけるノードと関連するクラスラベル、前記値のベクトル及び暗号化関数を用いて行われる、
請求項7に記載の方法。
【請求項17】
コンピュータ読出可能なコードを記憶したコンピュータ読出可能な媒体を有する装置であって、
前記コンピュータ読出可能なコードは、システムによって実行される場合に、該システムに、
第1の暗号化された入力データを受信するステップと、
分類ツリーの各ノードごとに、前記第1の暗号化されたデータを用いて、分類器により関数を計算するステップと、
前記各ノードごとに前記関数を計算した結果の暗号化されたバージョンを有する第2の暗号化されたデータを送信するステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを受信するステップと、
前記分類ツリーにおける経路内の各ノードごとに、該各ノードでの分類決定に基づき前記第1の暗号化されたベクトル又は前記第2の暗号化されたベクトルのいずれかから値を選択し、該値に基づく値のベクトルを前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルから選択される値を用いて計算するステップと、
前記分類ツリーにおいてモードに割り当てられる対応するクラスが得られる前記値のベクトルを送信するステップと
を実行させる、装置。
【請求項18】
加法準同型暗号化システムを用いて入力データを暗号化することによって生成された暗号化された入力データを受信するステップと、
分類器により分類ツリーの各ノードでの分類決定を評価するステップであって、前記分類ツリーにおける各ノードごとに前記暗号化された入力データに対する関数を計算するステップと、該各ノードごとに前記関数を計算した結果を用いて複数の要素を有する出力ベクトル生成するステップと、該出力ベクトルを送信するステップとを含むステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを受信するステップと、
前記分類ツリーにおける経路内の各ノードごとに、該各ノードでの分類決定に基づき前記第1の暗号化されたベクトル又は前記第2の暗号化されたベクトルのいずれかから値を選択し、該値に基づく値のベクトルを前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルから選択される値を用いて計算するステップと、
前記分類ツリーにおいてモードに割り当てられる対応するクラスが得られる前記値のベクトルを送信するステップと
を有する方法。
【請求項19】
前記分類ツリーは、1又はそれ以上の多重特徴分裂を有する多変数ツリーである、
請求項18に記載の方法。
【請求項20】
前記分類ツリーは、不平衡である、
請求項18に記載の方法。
【請求項21】
前記分類ツリーは、1又はそれ以上の1/2分裂を含む、
請求項18に記載の方法。
【請求項22】
前記分類決定は、分裂決定を有する、
請求項18に記載の方法。
【請求項23】
前記関数は、分裂規則を表す、
請求項18に記載の方法
【請求項24】
コンピュータ読出可能なコードを記憶したコンピュータ読出可能な媒体を有する装置であって、
前記コンピュータ読出可能なコードは、システムによって実行される場合に、該システムに、
加法準同型暗号化システムを用いて入力データを暗号化することによって生成された暗号化された入力データを受信するステップと、
分類器により分類ツリーの各ノードでの分類決定を評価するステップであって、前記分類ツリーにおける各ノードごとに前記暗号化された入力データに対する関数を計算するステップと、該各ノードごとに前記関数を計算した結果を用いて複数の要素を有する出力ベクトル生成するステップと、該出力ベクトルを送信するステップとを含むステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを受信するステップと、
前記分類ツリーにおける経路内の各ノードごとに、該各ノードでの分類決定に基づき前記第1の暗号化されたベクトル又は前記第2の暗号化されたベクトルのいずれかから値を選択し、該値に基づく値のベクトルを前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルから選択される値を用いて計算するステップと、
前記分類ツリーにおいてモードに割り当てられる対応するクラスが得られる前記値のベクトルを送信するステップと
を実行させる、装置。
【請求項25】
暗号化された入力データを生成するよう加法準同型暗号化システムを用いて入力データのビット単位の暗号化を行うステップと、
前記入力データを用いて分類ツリーの各ノードでの分類決定を評価した結果を含むベクトルを分類器から受信するステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを前記ベクトルにおけるデータを用いて生成するステップと、
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルを前記分類器へ送信するステップと、
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルを用いて計算された暗号化されたクラスラベルを前記分類器から受信するステップと、
前記入力データについてクラスラベルを検出するステップと
を有する方法。
【請求項26】
コンピュータ読出可能なコードを記憶したコンピュータ読出可能な媒体を有する装置であって、
前記コンピュータ読出可能なコードは、システムによって実行される場合に、該システムに、
暗号化された入力データを生成するよう加法準同型暗号化システムを用いて入力データのビット単位の暗号化を行うステップと、
前記入力データを用いて分類ツリーの各ノードでの分類決定を評価した結果を含むベクトルを分類器から受信するステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを前記ベクトルにおけるデータを用いて生成するステップと、
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルを前記分類器へ送信するステップと、
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルを用いて計算された暗号化されたクラスラベルを前記分類器から受信するステップと、
前記入力データについてクラスラベルを検出するステップと
を実行させる、装置。
【請求項1】
第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行うステップであって、前記第1の位置とは異なる第2の位置とデータを交換して、前記ユーザ入力を取得し、単準同型暗号化を用いてユーザに分類の結果を提供し、それにより、前記ユーザ入力が前記分類器に対して隠され、前記分類ツリーが前記ユーザに対して隠され、前記分類器の出力が前記分類器に対して隠されるようにするステップを有する方法。
【請求項2】
前記単準同型暗号化は、分類のために入力のビット単位の多項式表現を用いる、
請求項1に記載の方法。
【請求項3】
前記多項式表現は、多項式を和として表す、
請求項2に記載の方法。
【請求項4】
前記単準同型暗号化は、加法準同型暗号を有する、
請求項1に記載の方法。
【請求項5】
前記単準同型暗号化は、秘密多項式評価法プロトコルに基づく準同型暗号を有する、
請求項1に記載の方法。
【請求項6】
コンピュータ読出可能なコードを記憶したコンピュータ読出可能な媒体を有する装置であって、
前記コンピュータ読出可能なコードは、システムによって実行される場合に、該システムに、
第1の位置で分類ツリーを有する分類器によってユーザ入力のツリーに基づく分類を行うステップであって、前記第1の位置とは異なる第2の位置とデータを交換して、前記ユーザ入力を取得し、単準同型暗号化を用いてユーザに分類の結果を提供し、それにより、前記ユーザ入力が前記分類器に対して隠され、前記分類ツリーが前記ユーザに対して隠され、前記分類器の出力が前記分類器に対して隠されるようにするステップ
を実行させる、装置。
【請求項7】
第1の暗号化された入力データを受信するステップと、
分類ツリーの各ノードごとに、前記第1の暗号化されたデータを用いて、分類器により関数を計算するステップと、
前記各ノードごとに前記関数を計算した結果の暗号化されたバージョンを有する第2の暗号化されたデータを送信するステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを受信するステップと、
前記分類ツリーにおける経路内の各ノードごとに、該各ノードでの分類決定に基づき前記第1の暗号化されたベクトル又は前記第2の暗号化されたベクトルのいずれかから値を選択し、該値に基づく値のベクトルを前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルから選択される値を用いて計算するステップと、
前記分類ツリーにおいてモードに割り当てられる対応するクラスが得られる前記値のベクトルを送信するステップと
を有する方法。
【請求項8】
前記分類ツリーは、1又はそれ以上の多重特徴分裂を有する多変数ツリーである、
請求項7に記載の方法。
【請求項9】
前記分類ツリーは、不平衡である、
請求項7に記載の方法。
【請求項10】
前記分類ツリーは、1又はそれ以上の1/2分裂を含む、
請求項7に記載の方法。
【請求項11】
前記分類決定は、分裂決定を有する、
請求項7に記載の方法。
【請求項12】
前記関数は、分裂規則を表す、
請求項7に記載の方法
【請求項13】
前記第2の暗号化されたデータにおける各ノードと関連する暗号化されたデータの順序は、前記分類ツリーにおけるノード位置を示さない、
請求項7に記載の方法。
【請求項14】
前記第1の暗号化された入力データは、加法準同型暗号システムを用いてビット単位で暗号化されている入力データを有する、
請求項7に記載の方法。
【請求項15】
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルは、P次元の暗号化された2進ベクトルである、
請求項7に記載の方法。
【請求項16】
前記値のベクトルを計算することは、経路におけるノードの数、該経路におけるノードと関連するクラスラベル、前記値のベクトル及び暗号化関数を用いて行われる、
請求項7に記載の方法。
【請求項17】
コンピュータ読出可能なコードを記憶したコンピュータ読出可能な媒体を有する装置であって、
前記コンピュータ読出可能なコードは、システムによって実行される場合に、該システムに、
第1の暗号化された入力データを受信するステップと、
分類ツリーの各ノードごとに、前記第1の暗号化されたデータを用いて、分類器により関数を計算するステップと、
前記各ノードごとに前記関数を計算した結果の暗号化されたバージョンを有する第2の暗号化されたデータを送信するステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを受信するステップと、
前記分類ツリーにおける経路内の各ノードごとに、該各ノードでの分類決定に基づき前記第1の暗号化されたベクトル又は前記第2の暗号化されたベクトルのいずれかから値を選択し、該値に基づく値のベクトルを前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルから選択される値を用いて計算するステップと、
前記分類ツリーにおいてモードに割り当てられる対応するクラスが得られる前記値のベクトルを送信するステップと
を実行させる、装置。
【請求項18】
加法準同型暗号化システムを用いて入力データを暗号化することによって生成された暗号化された入力データを受信するステップと、
分類器により分類ツリーの各ノードでの分類決定を評価するステップであって、前記分類ツリーにおける各ノードごとに前記暗号化された入力データに対する関数を計算するステップと、該各ノードごとに前記関数を計算した結果を用いて複数の要素を有する出力ベクトル生成するステップと、該出力ベクトルを送信するステップとを含むステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを受信するステップと、
前記分類ツリーにおける経路内の各ノードごとに、該各ノードでの分類決定に基づき前記第1の暗号化されたベクトル又は前記第2の暗号化されたベクトルのいずれかから値を選択し、該値に基づく値のベクトルを前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルから選択される値を用いて計算するステップと、
前記分類ツリーにおいてモードに割り当てられる対応するクラスが得られる前記値のベクトルを送信するステップと
を有する方法。
【請求項19】
前記分類ツリーは、1又はそれ以上の多重特徴分裂を有する多変数ツリーである、
請求項18に記載の方法。
【請求項20】
前記分類ツリーは、不平衡である、
請求項18に記載の方法。
【請求項21】
前記分類ツリーは、1又はそれ以上の1/2分裂を含む、
請求項18に記載の方法。
【請求項22】
前記分類決定は、分裂決定を有する、
請求項18に記載の方法。
【請求項23】
前記関数は、分裂規則を表す、
請求項18に記載の方法
【請求項24】
コンピュータ読出可能なコードを記憶したコンピュータ読出可能な媒体を有する装置であって、
前記コンピュータ読出可能なコードは、システムによって実行される場合に、該システムに、
加法準同型暗号化システムを用いて入力データを暗号化することによって生成された暗号化された入力データを受信するステップと、
分類器により分類ツリーの各ノードでの分類決定を評価するステップであって、前記分類ツリーにおける各ノードごとに前記暗号化された入力データに対する関数を計算するステップと、該各ノードごとに前記関数を計算した結果を用いて複数の要素を有する出力ベクトル生成するステップと、該出力ベクトルを送信するステップとを含むステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを受信するステップと、
前記分類ツリーにおける経路内の各ノードごとに、該各ノードでの分類決定に基づき前記第1の暗号化されたベクトル又は前記第2の暗号化されたベクトルのいずれかから値を選択し、該値に基づく値のベクトルを前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルから選択される値を用いて計算するステップと、
前記分類ツリーにおいてモードに割り当てられる対応するクラスが得られる前記値のベクトルを送信するステップと
を実行させる、装置。
【請求項25】
暗号化された入力データを生成するよう加法準同型暗号化システムを用いて入力データのビット単位の暗号化を行うステップと、
前記入力データを用いて分類ツリーの各ノードでの分類決定を評価した結果を含むベクトルを分類器から受信するステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを前記ベクトルにおけるデータを用いて生成するステップと、
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルを前記分類器へ送信するステップと、
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルを用いて計算された暗号化されたクラスラベルを前記分類器から受信するステップと、
前記入力データについてクラスラベルを検出するステップと
を有する方法。
【請求項26】
コンピュータ読出可能なコードを記憶したコンピュータ読出可能な媒体を有する装置であって、
前記コンピュータ読出可能なコードは、システムによって実行される場合に、該システムに、
暗号化された入力データを生成するよう加法準同型暗号化システムを用いて入力データのビット単位の暗号化を行うステップと、
前記入力データを用いて分類ツリーの各ノードでの分類決定を評価した結果を含むベクトルを分類器から受信するステップと、
前記分類ツリーにおける各ノードでの分類決定を含むベクトルの暗号化されたバージョンを含む第1の暗号化されたベクトルと、前記分類ツリーにおける各ノードでの分類決定を含む前記ベクトルの余を含む第2の暗号化されたベクトルとを前記ベクトルにおけるデータを用いて生成するステップと、
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルを前記分類器へ送信するステップと、
前記第1の暗号化されたベクトル及び前記第2の暗号化されたベクトルを用いて計算された暗号化されたクラスラベルを前記分類器から受信するステップと、
前記入力データについてクラスラベルを検出するステップと
を実行させる、装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2012−163960(P2012−163960A)
【公開日】平成24年8月30日(2012.8.30)
【国際特許分類】
【出願番号】特願2012−21045(P2012−21045)
【出願日】平成24年2月2日(2012.2.2)
【出願人】(000006747)株式会社リコー (37,907)
【Fターム(参考)】
【公開日】平成24年8月30日(2012.8.30)
【国際特許分類】
【出願日】平成24年2月2日(2012.2.2)
【出願人】(000006747)株式会社リコー (37,907)
【Fターム(参考)】
[ Back to top ]