(57)【要約】  マスクを用いるプライバシ保護リッジ回帰のための方法及びシステムが提供される。本方法は、暗号サービスプロバイダからのガーブル回路を要求するステップと、準同型暗号化を用いて定式化及び暗号化されたデータを複数のユーザから収集するステップと、準同型暗号化を用いて定式化及び暗号化されたデータを加算するステップと、用意されたマスクを、加算されたデータに適用するステップと、用意されたマスクに対応するガーブル入力を、紛失通信を用いて暗号サービスプロバイダから受信するステップと、ガーブル入力及びマスクされたデータを利用して、暗号サービスプロバイダからのガーブル回路を評価するステップとを有する方法。
2016510908.tif 000002
【特許請求の範囲】
【請求項１】
プライバシ保護リッジ回帰を提供する方法であって、
暗号サービスプロバイダからのガーブル回路を要求するステップと、
準同型暗号化を用いて定式化及び暗号化されたデータを複数のユーザから収集するステップと、
準同型暗号化を用いて定式化及び暗号化された前記データを加算するステップと、
用意されたマスクを、加算された前記データに適用するステップと、
用意されたマスクに対応するガーブル入力を、紛失通信を用いて前記暗号サービスプロバイダから受信するステップと、
前記ガーブル入力及び前記マスクされたデータを利用して、前記暗号サービスプロバイダからの前記ガーブル回路を評価するステップと、
を有する方法。
【請求項２】
暗号サービスプロバイダからのガーブル回路を要求する前記ステップが、
前記ガーブル回路の入力変数の次元を提供するステップと、
前記入力変数の値の範囲を提供するステップと、
を有する、請求項1に記載の方法。
【請求項３】
コンピュータ装置に実装されるエバリュエータが前記方法を実行する、請求項1に記載の方法。
【請求項４】
前記暗号サービスプロバイダは、前記エバリュエータが実装される前記コンピュータ装置から離れたコンピュータ装置に実装される、請求項3に記載の方法。
【請求項５】
複数のユーザからの前記データを暗号化するための暗号鍵を提供するステップを更に有する請求項1に記載の方法。
【請求項６】
前記複数のユーザからのデータは、前記暗号サービスプロバイダにより提供される暗号鍵により更に暗号化される、請求項5に記載の方法。
【請求項７】
前記ガーブル回路を評価するステップが、
前記加算されたデータから、前記用意されたマスクを取り除くステップと、
前記ガーブル回路により具現化されるリッジ回帰方程式を解くステップと、
を更に有する請求項1に記載の方法。
【請求項８】
前記複数のユーザから収集する前記ステップが、前記複数のユーザの各々から送信されたデータを、コンピュータ装置により受信するステップを含む、請求項1に記載の方法。
【請求項９】
プライバシ保護リッジ回帰を提供するコンピュータ装置であって、
ユーザデータを保存するストレージと、
処理するデータを保存するメモリと、
プロセッサとを有し、前記プロセッサは、暗号サービスプロバイダからのガーブル回路を要求すること、準同型暗号化を用いて定式化及び暗号化されたデータを複数のユーザから収集すること、準同型暗号化を用いて定式化及び暗号化された前記データを加算すること、用意されたマスクを、加算された前記データに適用すること、マスクされたデータに対応するガーブル入力を、紛失通信を用いて前記暗号サービスプロバイダから受信すること、及び、前記ガーブル入力及び前記マスクされたデータを利用して、前記暗号サービスプロバイダからの前記ガーブル回路を評価することを行うように構成される、コンピュータ装置。
【請求項１０】
ネットワークに接続するためのネットワーク接続を更に有する請求項9に記載のコンピュータ装置。
【請求項１１】
前記暗号サービスプロバイダは、別のコンピュータ装置に実装される、請求項9に記載のコンピュータ装置。
【請求項１２】
暗号サービスプロバイダからのガーブル回路を要求することが、
前記ガーブル回路の入力変数の次元を提供すること、及び
前記入力変数の値の範囲を提供すること、
を含む、請求項9に記載のコンピュータ装置。
【請求項１３】
前記ガーブル回路を評価するこが、
前記加算されたデータから、前記用意されたマスクを取り除くこと、及び
前記ガーブル回路により具現化されるリッジ回帰方程式を解くこと、
を更に有する、請求項9に記載のコンピュータ装置。
【請求項１４】
前記複数のユーザからのデータは、前記暗号サービスプロバイダにより提供される暗号鍵により暗号化され、前記コンピュータ装置による暗号鍵により暗号化される、請求項9に記載のコンピュータ装置。
【請求項１５】
実行される場合にステップを実行する命令を含むマシン読み取り可能な媒体であって、前記ステップは、
暗号サービスプロバイダからのガーブル回路を要求するステップと、
準同型暗号化を用いて定式化及び暗号化されたデータを複数のユーザから収集するステップと、
準同型暗号化を用いて定式化及び暗号化された前記データを加算するステップと、
用意されたマスクを、加算された前記データに適用するステップと、
用意されたマスクに対応するガーブル入力を、紛失通信を用いて前記暗号サービスプロバイダから受信するステップと、
前記ガーブル入力及び前記マスクされたデータを利用して、前記暗号サービスプロバイダからの前記ガーブル回路を評価するステップと、
を有する、媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にデータ検索に関連し、より具体的には、リッジ回帰を用いてデータ検索中のプライバシを保護することに関連する。
【背景技術】
【０００２】
レコメンデーションシステムは、様々なアイテム(item)に対する多くのユーザの好み及び評価を収集し、そのデータに関して学習アルゴリズムを実行することにより、動作する。学習アルゴリズムは、新たなユーザが所定のアイテムをどのように評価するかを予測するために利用可能なモデルを生成する。特に、所定のアイテムについてユーザが提供した評価の下で、モデルはそのユーザが他のアイテムをどのように評価するかを予想することができる。そのような予測モデルを生成する多数のアルゴリズムが存在し、多くはアマゾン(登録商標)やネットフリックス(登録商標)のような大規模なサイトで積極的に使用されている。学習アルゴリズムは、大規模な医療データベース、金融データ及び他の多くの分野でも使用されている。
【０００３】
現在の実装では、学習アルゴリズムは、予測モデルを構築するために、全てのユーザデータを明示的に把握する必要がある。本開示では、データを明示することなく、学習アルゴリズムが動作可能であるか否かが判断され、これにより、ユーザは各自のデータのコントロールを維持することを許容する。医療データの場合、これは、ユーザのプライバシに影響することなく、モデルが構築されることを許容する。書籍や映画の好みに関し、ユーザに各自のデータのコントロールを保持させることは、サービスプロバイダにデータの漏洩が生じた場合に、不測の被害(embarrassment)を被る将来的なリスクを減らす。大まかに言えば、データ検索の私的なユーザデータに至るアプローチは3つ存在する。第1は、秘密共有を用いて複数のサーバ間でユーザが各自のデータを分けるようにする。そしてこれらのサーバは分散プロトコルを用いて学習アルゴリズムを実行し、大部分のサーバが共謀しない限り、プライバシは保証される。第2は、完全な準同型暗号化(fully  homomorphic  encryption)に基づくものであり、暗号化されたデータに対して学習アルゴリズムが実行され、信頼される第三者のみが、最終的な暗号化されたモデルを解読するように信頼される。第3のアプローチでは、ヤオ(Yao)のガーブル回路(garbled  circuit)構成が使用され、暗号化されたデータを算出し、ユーザデータに関して何も学習することなく、最終的なモデルを取得する。しかしながら、Yaoに基づくアプローチは、回帰アルゴリズムの分野には未だかつて適用されていない。
【発明の概要】
【０００４】
準同型暗号化及びヤオのガーブル回路の双方を利用するプライバシ保護リッジ回帰のためのハイブリッドアプローチが提供される。システムのユーザは、例えばPaillier又はRegevのような線形な準同型暗号化システムの下で暗号化された各自のデータを送付する。エバリュエータは、線形な準同型性を利用して、線形処理のみを必要とするアルゴリズムの第1フェーズを実行する。このフェーズは暗号化されたデータを生成する。第1ステージにおいて、本システムは、(システム内のユーザ数nに比例する)多数のレコードを処理するように求められる。第1フェーズにおける処理は、アルゴリズムの第2フェーズがnに依存しないようにデータを準備する。第2フェーズでは、エバリュエータはヤオのガーブル回路を評価し、その場合に、先ず準同型解読を実行し、次に回帰アルゴリズムの残りを実行する(説明されるように、最適化される実現例は、ガーブル回路における解読を避けることができる)。回帰アルゴリズムのこのステップは、高速線形システム・ソルバを必要とし、非常に非線形である。このステップに関し、ヤオのガール回路アプローチは、現在の完全な準同型暗号化方式よりもかなり高速である。すなわち、線形な準同型性を活用して大規模なデータセットを処理し、計算のうち非常に非線形な部分についてはガーブル回路を活用することにより、双方の技術のうちの良い部分が得られる。第2フェーズは、計算方法が2段階に分離されることに起因して、nにも依存しない。
【０００５】
一実施形態では、プライバシ保護リッジ回帰のための方法が提供される。本方法は、暗号サービスプロバイダからのガーブル回路を要求するステップと、準同型暗号化を用いて定式化及び暗号化されたデータを複数のユーザから収集するステップと、準同型暗号化を用いて定式化及び暗号化された前記データを加算するステップと、用意されたマスクを、加算された前記データに適用するステップと、用意されたマスクに対応するガーブル入力を、紛失通信を用いて前記暗号サービスプロバイダから受信するステップと、前記ガーブル入力及び前記マスクされたデータを利用して、前記暗号サービスプロバイダからの前記ガーブル回路を評価するステップとを有する。
【０００６】
別の実施形態では、プライバシ保護リッジ回帰のためのコンピュータ装置が提供される。コンピュータ装置は、ストレージ、メモリ及びプロセッサを含む。ストレージはユーザデータを保存する。メモリは処理するデータを保存する。前記プロセッサは、暗号サービスプロバイダからのガーブル回路を要求すること、準同型暗号化を用いて定式化及び暗号化されたデータを複数のユーザから収集すること、準同型暗号化を用いて定式化及び暗号化された前記データを加算すること、用意されたマスクを、加算された前記データに適用すること、用意されたマスクに対応するガーブル入力を、紛失通信を用いて前記暗号サービスプロバイダから受信すること、及び、前記ガーブル入力及び前記マスクされたデータを利用して、前記暗号サービスプロバイダからの前記ガーブル回路を評価することを行うように構成される。
【０００７】
課題及び効果は、特許請求の範囲に明確に記載される要素及び接続により実現及び達成される。開示される実施形態は、本願における画期的な教示の多くの有用な用途のうちの具体例に過ぎない点に留意することは重要である。上記の一般的な説明及び以下の詳細な説明の双方は、例示的な具体例であり、特許請求の範囲に記載される発明の限定ではないことが、理解されるべきである。更に、何らかの記述は、ある発明事項には適用されるが別の事項には適用されなくてもよい。一般に、断りのない限り、単独の要素は複数個存在してもよく、一般性を失うことなく逆も成り立つ。図面において、同様な数字は複数の図面における同様な部分を指す。
【図面の簡単な説明】
【０００８】
【図１】実施形態によるプライバシ保護リッジ回帰システムの概略ブロック図を示す。
【図２】実施形態によるコンピュータ装置の概略ブロック図を示す。
【図３】実施形態による例示的なガーブル回路を示す。
【図４】実施形態によるプライバシ保護リッジ回帰を規定する方法の上位概念的なフローチャートを示す。
【図５】実施形態によるプライバシ保護リッジ回帰を規定する第1プロトコル処理を示す。
【図６】実施形態によるプライバシ保護リッジ回帰を規定する第1プロトコル処理を示す。
【図７】コレスキー分解のための実施形態によるアルゴリズムの一例を示す。
【発明を実施するための形態】
【０００９】
本開示の関心事は、例えばリッジ回帰(ridge  regression)のような、多くの学習アルゴリズムに使用される基礎的な仕組みに関する。高次元における多数の点の下で、回帰アルゴリズムはこれらの点を通る最も適合する曲線を生成する。その目的は、ユーザデータ又はユーザデータに関する何らかの他の情報を明らかにすることなく、演算を実行することである。これは、図1に示されるようなシステムを利用することにより達成される。
【００１０】
図1には、プライバシ保護リッジ回帰を実現する一形態のシステム100のブロック図が示されている。システムは、エバリュエータ110と、1人以上のユーザ120と、暗号サービスプロバイダ(CSP)とを含み、これらは互いに通信する。エバリュエータ110は、サーバ又はパーソナルコンピュータ(PC)のようなコンピュータ装置に実装される。CSP130も同様にサーバ又はパーソナルコンピュータのようなコンピュータ装置に実装され、イーサーネット(登録商標)又はWi-Fiネットワークのようなネットワークを介してエバリュエータ110と通信する。1人以上のユーザ120は、パーソナルコンピュータ、タブレット、スマートフォン等のようなコンピュータ装置を介して、エバリュエータ110及びCSP130と通信する。
【００１１】
ユーザ120は、暗号化されたデータ(例えば、PCからのデータ)を、学習アルゴリズムを実行するエバリュエータ110(例えば、サーバ上にある)に送信する。所定の時点において、エバリュエータは、エバリュエータ110と共謀しないように信頼される暗号サービスプロバイダ130(別のサーバ上にある)と相互作用する。最終的な成果は、平文予測(cleartext  predictive)モデルβ140である。
【００１２】
図2は、サーバ、PC、タブレット又はスマートフォン等のような例示的なコンピュータ装置200を示し、コンピュータ装置は、プライバシ保護リッジ回帰のための様々な方法及びシステム要素を実現するために使用可能である。コンピュータ装置200は、1つ以上のプロセッサ210、メモリ220、ストレージ230及びネットワークインタフェース240を含む。これらの要素の各々について以下において更に説明する。
【００１３】
プロセッサ210は電子サーバ200の動作を制御する。プロセッサ200は、サーバを動作させることに加えてクラウド・スタート・レコメンデーションの機能を提供するソフトウェアを実行する。プロセッサ210は、メモリ220、ストレージ230及びネットワークインタフェース240に接続され、これらの要素間の情報の転送及び処理を取り扱う。プロセッサ210は、汎用プロセッサ又は特定の機能に特化したプロセッサとすることが可能である。所定の実施形態において、複数のプロセッサが存在してもよい。
【００１４】
メモリ220には、プロセッサにより実行されるべき命令及びデータが保存される。メモリ210は、揮発性メモリ(RAM)、不揮発性メモリ(ROM)又はその他の適切な媒体を含むことが可能である。
【００１５】
ストレージ230には、本願のクラウド・ストレージ・レコメンデーション法を実行するプロセッサにより使用及び生成されるデータが保存される。ストレージは、磁気媒体(ハードドライブ)、光媒体(CD/DVD-ROM)又はフラッシュ方式のストレージであってもよい。
【００１６】
ネットワークインタフェース240はネットワークを介して他の装置とのサーバ200の通信を取り扱う。適切なネットワークの具体例はイーサーネットネットワークである。本開示による恩恵をもたらす他のタイプの適切なホームネットワークも当業者に認められるであろう。
【００１７】
図2で言及される要素は例示的であることが理解されるべきである。サーバ200は任意の数の要素を含むことが可能であり、或る要素は他の要素の機能の全部又は一部を提供してもよい。本開示による恩恵をもたらす他の可能な実現手段も当業者に認められるであろう。
【００１８】
設定及び脅迫モデル
A.アーキテクチャ及びエンティティ
再び図1に関し、システム100は、エバリュエータ110と呼ばれるセントラルサーバにデータを与えるように多数のユーザ120に対して設計される。エバリュエータ110は、提供されたデータに対して回帰を実行し、予測又はレコメンデーションタスクのために後に使用されることが可能なモデルβ140を生成する。より具体的には、各々のユーザi=1;:::;nは、xi∈Rd及びyi∈Rである2変数を有するプライベートレコードを有し、エバリュエータは、yi≒βTxiとなるようなモデルβ∈Rdを算出することを希望している。目的は、回帰アルゴリズムの最終結果であるβ140によって明らかにされるもの以外、エバリュエータはユーザのレコードに関して何も学習しないことを保証することである。システムを起動するには、作業の多くをオフラインで行うここでは「暗号サービスプロバイダ」と言及される第三者が必要とされる。
【００１９】
より正確に言えば、システムの参加者は図1に示されるように以下の通りである：
・ユーザ120：各ユーザiは、暗号化されてエバリュエータ110に送信されるプライベートデータxi,yiを有する。
【００２０】
・エバリュエータ110：暗号化されたデータについて回帰アルゴリズムを実行し、学習されたモデルβ140を明示的に取得する。
【００２１】
・暗号サービスプロバイダ(CSP)130：ユーザ120及びエバリュエータ110にセットアップパラメータを与えることにより、システム100を起動する。
【００２２】
CSP130は、ユーザ120が各自のデータをエバリュエータ110に提供するかなり前に、作業の多くをオフラインで行う。最も効率的な設計では、エバリュエータ110がモデル140を算出する場合に、CSP130にも短い一往復のオンラインステップが求められる。
【００２３】
B.脅迫モデル(Threat  Model)
目的は、学習アルゴリズムの最終結果によって明らかにされるもの以外、エバリュエータ110及びCSP130は、ユーザ120により提供されたデータに関して何も学習できないことを保証することである。エバリュエータ110が何人かのユーザ120と共謀している場合、そのユーザは、学習アルゴリズムの結果によって明らかにされるもの以外、他のユーザ120により提供されたデータに関して何も学習すべきではない。
【００２４】
この例では、エバリュエータ110の最大関心事は、正確なモデルβ140を生成することである、ということが仮定される。従って、本実施形態は、不正確な結果を招くことを促すように演算を乱そうとする悪意のエバリュエータ110には関連しない。しかしながら、エバリュエータ110は、ユーザにより提供されるプライベートデータに関する情報を学習する及び悪く振る舞う動機を有しており、その理由は、そのようなデータは他者(例えば、広告主)に売れる可能性があるからである。従って、悪意のエバリュエータ110には関連でさえ、学習アルゴリズムの結果によって明らかにされるもの以外、ユーザデータに関して何かを学習できないべきである。正直であるが詮索するエバリュエータに対して安全な基本プロトコルが本願で説明される。
【００２５】
非脅迫(Non-threat)：本システムは以下の攻撃から防御されるようには設計されていない：
・エバリュエータ110及びCSP130は共謀してはいないことが仮定される。各々は上述したようにシステムをむしばもうとするかもしれないが、各自は独立に行う。より正確に言えば、セキュリティを議論する場合に、これら2者のうちせいぜい一方にしか悪意はないことが仮定される(これは、安全性が達成されないことを除外する本質的な条件である)。
【００２６】
・セットアップは適切に機能することが仮定され、すなわち全てのユーザ120はCSP130から適切な公開鍵を取得する。これは、認証機関(Certificate  Authority)を適切に利用することで強制できる。
【００２７】
背景
A.線型モデル学習
β140を学習するためにエバリュエータ110がシステム110内で実行するリッジ回帰を簡単に概説する。説明される事項は過去のものであり、多くの統計及びマシン学習の書籍に見受けられる。
【００２８】
線形回帰：n個の入力変数群xi∈Rd及び出力変数群yi∈Rに関し、yi≒f(xi)が回帰として分かるように、関数f:Rd→Rを学習するという問題である。例えば、入力変数は人の年齢、体重、体格指数(BMI)等であり、出力は病気にかかる各人の尤度(又は確率)とすることが可能である。
【００２９】
実際のデータからそのような関数を学習することは、データ検索、統計、及び、マシン学習などにおいて回帰をユビキタスにする多くの興味深い応用分野を有する。一方、関数それ自体は、予測に使用されることが可能であり、すなわち、新たな入力x∈Rdについての出力値yを予測するために使用可能である。更に、fの構造は様々な入力が出力にどのように影響するかを特定することを支援することが可能であり、例えば、年齢よりも体重の方が、疾患に強く関連していることを立証できるかもしれない。
【００３０】
線形回帰は、fが線形写像により十分に近似されるという前提に基づいており、すなわち、あるβ∈Rdに関し、次式が成り立つ：
yi≒βTxi，    i∈[n]≡{1,...,n}
線形回帰は、科学技術における推論及び統計的な分析に最も広く使用される方法の1つである。更に、線形回帰は、カーネル法(kernel  method)のような、統計分析及びマシン学習におけるいくつもの更に進化した方法のための基礎的な構成要素である。例えば、自由度2の多項式である関数を学習することは、xikxik’(1≦k，k’≦d)に関する線形回帰に帰着し、同じ原理が、基底関数の有限集合によって張られる空間内の任意の関数を学習することに一般化できる。
【００３１】
上述したように、予測に関する自明な用途以外に、ベクトルβ=(βk)k=1,...,dは興味深く、なぜなら、それはyが入力変数にどのように依存するかを明らかにするからである。特に、係数βkの符号は出力に対する正又は負の相関性を示し、その大きさは相対的な重要性を示す。これらの係数が比較可能になるだけでなく数値的にも安定することを保証するために、入力xiは同じ有限領域(例えば、[-1;1])にスケーリングされ直す。
【００３２】
係数の計算：ベクトルβ∈Rdを計算するため、Rdに関して以下の二次関数を最小化することにより、後者はデータに適合させられる。
【００３３】
【数１】
2016510908.tif 000003
(1)を最小化する処理はリッジ回帰と呼ばれ；目的関数F(β)はペナルティ項λ‖β‖22を組み込んでおり、倹約的な解を好む傾向がある。直感的には、λ=0である場合、(1)を最小化することは、単純な最小二乗問題を解くことに対応する。正数λ＞0である場合、λ‖β‖22は高さノルムとともに解にペナルティを与え：等しくデータに適合する2つの解があった場合、大きな係数が少ないものが好ましい。βの係数は入力が出力にどのように影響するかについてのインジケータであることを想起すると、これは「オッカムのかみそり(Occam’s  razor)」の場合のように振る舞い：大きな係数が少ない簡易な解が好ましい。実際、λ＞0は、新たな入力に対して、最小二乗に基づく解よりも事実上優れた解をもたらす。y∈Rnが出力のベクトルであり、x∈Rn×dが(行毎につずつ)入力ベクトルを有する行列であるとする：
【００３４】
【数２】
2016510908.tif 000004
次の線形システムを解くことにより、(1)の最小化を計算することが可能である：
Aβ=b      (2)
ここで、A=XTX+λI及びb=XTyである。λ＞0の場合、行列Aは対称的で正定値(symmetric  positive  definite)であり、有効な解は、後述するコレスキー分解(Cholesky  decomposition)を用いて見出すことが可能である。
【００３５】
B.  ヤオのガーブル回路(Yao’s  Garbled  Circuits)
基本的な形式において、ヤオのプロトコル(ガーブル回路とも言及される)は、半分正直な敵対者(semi-honest  adversaries)が存在する場合に関数ｆ(x1;x2)の2者の評価を可能にする。プロトコルは入力オーナーの間で実行される(aiはユーザiのプライベート入力を示す)。プロトコルの終わりにf(a1;a2)の値が得られるが、その出力値から明らかにされるもの以上を誰も学べない。
【００３６】
プロトコルは次のように進行する。第1の者(「ガーブラ(garbler)」と呼ばれる)が、f  を計算する回路についての「不明な(garbled)」バージョンを構築する。ガーブラは、次に、第2の者(「エバリュエータ」と呼ばれる)に、ガーブル回路だけでなくa1に対応するガーブル回路入力値も与える。GI(a1)という表記は、これらの入力値を示すために使用される。ガーブラは、ガーブル回路出力値と実際のビット値との対応関係(マッピング)も提供する。回路を受信すると、エバリュエータは、ガーブラとの1-out-of-2紛失通信プロトコルに携わり、選択者の役割を演じ、プライベート入力a2に対応するガーブル回路入力値GI(a2)を(相手に分からないように)(obliviously)取得する。GI(a1)及びGI(a2)から、エバリュエータはf(a1；a2)を算出することができる。
【００３７】
より詳細な例において、プロトコルは、図3に示されるような論理回路300により関数fを評価する。各々のワイヤwi310、320に関し、ガーブラは、それぞれビット値bi=0及びbi=1に対応する2つのランダム暗号鍵K0wi及びK1w1を関連付ける。入力ワイヤ(wi,wj)310、320及び出力ワイヤwk330とともに、各々のバイナリゲートg(例えば、OR-ゲート)に関し、ガーブラは、4つの暗号文を算出する：
【００３８】
【数３】
2016510908.tif 000005
これら4つのランダムに並べられる一群の暗号文が、ガーブルゲートを規定する。
【００３９】
ペアの鍵によって施錠解錠される対称的な暗号アルゴリズムEncは、選択平文攻撃の下で、区別できない暗号化である必要がある。所与のペアの鍵(Kbiwi,Kbjwj)の下で、対応する解読プロセスは、ガーブルゲートを構成する4つの暗号文から、曖昧性なしにKg(bi,bj)wkの値を復元することも必要とされる。(Kbiwi,Kbjwj)の知識はKg(bi,bj)wkの値のみをもたらすこと、及び、このゲートに関して他の出力値は復元できないことは、言及に値する。エバリュエータは、中間的な計算に関する更なる情報が漏洩しないように、ゲート毎にガーブル回路の全体を評価することが可能である。
【００４０】
ハイブリッドアプローチ
このセットアップにおいて、各々の入力及び出力変数xi，yi，i∈[n]は、プライベートなものであり、異なるユーザによって保持されていることを想起されたい。エバリュエータ110は、λ＞0の下でリッジ回帰により得られるような、入力及び出力変数間の線形関係を決定するβを学習することを望んでいる。
【００４１】
上述したように、βを取得するには、数式(2)に規定されるような行列A∈Rd×d及びベクトルb∈Rdを必要とする。これらの値が得られると、エバリュエータ110は数式(2)の線形システムを解き、βを求めることができる。プライバシを保護する形式でこの問題に対処する幾つかの方法が存在する。1つには、例えば、秘密共有や完全な準同型暗号化を当てにすることが考えられる。今のところ、これらの技術は目下の設定に対して不適切であるように思われ、その理由は、それらがかなりの(オンライン)通信あるいは演算オーバーヘッドを招いてしまうからである。そこで、上述したようなヤオのアプローチが利用される。
【００４２】
ヤオのアプローチを利用する簡易な方法の1つは、i∈[n]に関し、入力xi,yiを有する単独の回路を設計し、行列A及びbを計算し、その後に線形システムAβ=bを解くことである。そのようなアプローチは、オークションの勝者のような、複数のユーザから到来する入力の簡易な関数の組み合わせに関して過去に使用されている。実現性の問題(例えば、線形システムを解く回路をどのように設計するかという問題)を除いて、そのようなソリューションの主な欠点は、結果のガーブル回路が、ユーザの数nだけでなく、βの次元d及び入力変数にも依存することである。実際のアプリケーションでは、nは大きく、百万人規模のユーザ数になり得ることが一般的である。これに対して、dは比較的小さく、例えば10のような大きさのオーダである。従って、スケーラブルな解を得るために、ガーブル回路のnに対する依存性を減らすこと或いは排除することさえ望ましい。この目的のため、考察すべき問題は以下に説明するように変形される。
【００４３】
A.問題の再定式化
行列A及びベクトルbは、以下に説明するように、反復的な形式で算出可能であることに留意を要する。各々のxi及び対応するyiは様々なユーザにより保持され、各々のユーザiは行列Ai=xixiT及びベクトルbi=yixiをローカルに算出できることを仮定する。従って、部分的な寄与の合計が次式をもたらすことは容易に確認される：
【００４４】
【数４】
2016510908.tif 000006
数式(3)は、重要なことに、A及びbが一連の加算(級数)の結果であることを示す。エバリュエータの回帰タスクは、従って、2つのサブタスクに分離することが可能である：(a)行列A及びベクトルbを構築するために、Ai及びbiを収集すること、及び、(b)それらを利用して、線形システム(2)の解により、βを取得すること。
【００４５】
当然に、ユーザは各自のローカルな持ち分(Ai;bi)をエバリュエータに明示的には送信できない。しかしながら、後者が公開鍵加法性準同型暗号化方式(public-key  additive  homomorphic  encryption  scheme)を利用して暗号化されるならば、エバリュエータ110は(Ai;bi)の暗号化されたものから、A及びbの暗号化されたものを再構築することが可能である。残る問題は、CSP130の支援とともに、β以外の如何なる追加的な情報も(エバリュエータ110にもCSP130にも)明らかにすることなく、数式(2)を解くことである；ヤオのガーブル回路を利用することによりそれを実行する2つの異なる方法が、以下に説明される。
【００４６】
より具体的に説明するため、次式を想定する：
【００４７】
【数５】
2016510908.tif 000007
これは、公開鍵pkにより指定される意味論的にセキュアな暗号化方式であり、メッセージ空間Mに属するペア(Ai;bi)を入力としてとり、pkの下で(Ai;bi)を暗号化したものciを返す写像である。従って、任意のpk及び任意の2つのペア(Ai;bi)，(Aj;bj)に関し、何らかの一般的な二進演算子に関し、次式が成立しなければならない：
【００４８】
【数６】
2016510908.tif 000008
そのような暗号化方式は、Ai及びbiの成分毎の入力を暗号化することにより、何らかの意味論的にセキュアな加法性準同型暗号化方式から構築されることが可能である。具体例は、レゲブ(Regev)の方式及びパイラー(Paillier)の方式を含む。
【００４９】
今やプロトコルを提示する準備はできている。図4には上位概念的なフローチャート400が与えられている。フローチャート400は、準備段階410と、第1段階(フェーズ1)420と、第2段階(フェーズ2)とを含む。ユーザの持ち分を統合する段階はフェーズ1(420)として言及され、その段階が関わる加算は線形にnに依存することに留意を要する。A及びbの暗号化された値から方程式(2)に対する解を算出することになる次の段階は、フェーズ2(420)と言及される。フェーズ2(420)はn依存性を有しないことに留意を要する。以下、これらの段階が具体的なプロトコルとともに説明される。システムAβ=bを解くことができる回路の存在は以下において仮定されている点に留意を要し；そのような回路がどのようにして効果的に実装できるかを説明する。
【００５０】
B.第1プロトコル
図5には、第1プロトコルの動作についての上位概念的な表現500が示されている。第1プロトコルは次のように動作する。上述したように、第1プロトコルは、準備段階510、フェーズ1(520)及びフェーズ2(530)という3段階を有する。明らかに、フェーズ2(520)のみが実際にオンラインによる処理を要する。
【００５１】
準備フェーズ(510)。エバリュエータ110は、入力変数の次元(すなわち、パラメータd)及びそれらの値の範囲などのような仕様(specif.)をCSP130に提供する。CSP130は、フェーズ2(530)で説明される回路のためのヤオのガーブル回路を準備し、そのガーブル回路をエバリュエータ110にとって利用可能にする。CSP130は、準同型暗号化方式フラクトゥール(Fraktur)Eのための公開鍵pkcsp及び秘密鍵skcspを生成し、エバリュエータ110は暗号化方式ε(準同型である必要はない)のための公開鍵pkev及び秘密鍵skevを生成する。
【００５２】
フェーズ1(520)。各々ユーザiは、各自の部分的な行列Ai及びベクトルbiをローカルに算出する。これらの値は、次に、CSP130の公開鍵pkcspによる加法性準同型暗号加法フラクトゥールEを用いて暗号化される：
【００５３】
【数７】
2016510908.tif 000009
CSP130がこの値にアクセスすることを防止するため、ユーザiは、エバリュエータ110の公開暗号鍵pkevにより、ciの値を更に暗号化し、
【００５４】
【数８】
2016510908.tif 000010
そして、Ciをエバリュエータ110に送信する。
【００５５】
エバリュエータ110は
【００５６】
【数９】
2016510908.tif 000011
を算出する。エバリュエータ110は、受信される全てのCiを収集し、秘密解読鍵skevを用いてそれらを解読し、ciを復元する：
【００５７】
【数１０】
2016510908.tif 000012
そして、そのように取得された値を統合する：
【００５８】
【数１１】
2016510908.tif 000013
フェーズ2(530)。準備フェーズ510でCSP130により提供されるガーブル回路は、入力としてGI(C)をとる回路のガーブル化(garbling)であり、以下の2段階を実行する：
1)A及びbを復元するためにskcspでcを解読する(ここで、skcspはガーブル回路に組み込まれる)；及び
2)方程式(2)を解き、βを返す。
【００５９】
このフェーズ2(520)において、エバリュエータ110は、cに対応するガーブル回路入力値、すなわちGI(c)を取得することのみを必要とする。これらは、エバリュエータ110及びCSP130の間の標準的な紛失通信(Oblivious  Transfer：OT)を用いて取得される。
【００６０】
上記のハイブリッド計算は、ガーブル回路内の暗号化された入力の解読を実行する。これが必要とされることが可能な場合には、例えばレゲブ方式は非常に簡易な解読回路を有するので、フラクトゥールEを構成する基礎としてレゲブ準同型暗号化方式を利用することが示唆される。
【００６１】
C.第2プロトコル
図6には、第2プロトコルの動作についての上位概念的な表現600が示されている。第2プロトコルは、ランダムマスクを用いてガーブル回路において(A;b)を解読することを回避する変形例を与える。フェーズ1(610)は概ね同じままである。フェーズ2(及びそれに関連する準備フェーズ)はハイライトされる。そのアイディアは、準同型の性質を活用して、入力を加法性マスクで隠すことである。留意すべきことに、(μA;μb)がM(すなわち、準同型暗号化フラクトゥールEのメッセージ空間)に属する要素を示す場合、数式(4)により、次式が成り立つ：
【００６２】
【数１２】
2016510908.tif 000014
従って、エバリュエータ110は、Mに属するランダムマスク(μA;μb)を選択し、上記のようにcを隠し、その結果の値をCSP130に送信することを仮定する。そして、CSP130恥心の解読鍵を適用し、マスクされた値を復元する：
【００６３】
【数１３】
2016510908.tif 000015
その結果、上記の議論において解読がマスクの除去に置換されるプロトコルを適用することが可能になる。より詳細に言えば、以下の事項を含む：
準備フェーズ(610)。上述したように、エバリュエータ110は、評価(処理)をセットアップする。エバリュエータ110は、評価をサポートするガーブル回路を構築するために仕様をCSP130に提供する。CSP130は、回路を準備し、回路をエバリュエータ110にとって利用可能にし、双方ともに公開鍵及び秘密鍵を生成する。エバリュエータ110は、ランダムマスク(μA;μb)∈Mを選択し、CSP130との紛失通信(OT)プロトコルに従事し、(μA;μb)に対応するガーブル回路入力(すなわち、GI(μA;μb))を取得する。
【００６４】
フェーズ1(620)。これは第1プロトコルの場合に類似する。更に、エバリュエータ110はcをマスクする：
【００６５】
【数１４】
2016510908.tif 000016
フェーズ2(630)。エバリュエータ110はc^をCSP130に送信し、CSP130はそれを解読して(A^;b^)を明示的に取得する。次に、CSP130はガーブル回路入力値GI(A^;b^)をエバリュエータ110に返信する。準備フェーズでCSP130により提供されるガーブル回路は、入力としてGI(A^;b^)及びGI(μA;μb)をとる回路のガーブル化であり、以下の2段階を実行する：
1)A及びbを復元するために(A^;b^)からマスク(μA;μb)を減算する；
2)方程式(2)を解き、βを返す。
ガーブル回路だけでなく(μA;μb)に対応するガーブル回路入力GI(μA;μb)も、準備フェーズ610の間に取得される。このフェーズにおいて、エバリュエータ110は、(A^;b^)に対応するガーブル回路入力値であるGI(A^;b^)をCSP130から受信することのみを必要とする。これらは、このフェーズでは紛失通信(OT)は行われないことに留意を要する。
【００６６】
この第2の実現例に関し、解読は回路の一部分としては実行されない。従って、回路として効果的に実現可能な準同型暗号化方式を選択するようには制限されない。フラクトゥールEを構築する基礎として、レゲブの方式ではなく、Paillier方式又はダムガード(Damgard)及びジュリク(Jurik)によるその一般化方式を利用することが示唆される。これらの方式は、レゲブのものより短い暗号文拡大(ciphertext  expansion)を有し、より小さな鍵を必要とする。
【００６７】
D.第3プロトコル
あるアプリケーションに関し、準同型暗号化方式が部分的な準同型の性質しか有しない場合に、関連するアイディアが適用される。この考え方は次の定義により明らかになる。
【００６８】
定義1：部分的な準同型暗号化方式とは、秘密暗号鍵を必要とすることなく、暗号化された平文に定数を加算(部分的な準同型写像が加法的である場合)又は乗算(部分的な準同型写像が乗法的である場合)することが可能であるような暗号化方式である。
【００６９】
幾つかの具体例を示す。
【００７０】
・Fpを素体(prime  field)とし、G=<g>を、gにより生成される乗法群の巡回部分群であるとする。qをGの次数(位数)とする。平文エルガマル暗号(plain  ElGamal  encryption)に関し、メッセージ空間はM=Gである。公開暗号鍵はy=gxであり、秘密鍵はxである。Mに属するメッセージmの暗号化は、(R;c)により与えられ、何らかのランダムなr∈Z/qZに関し、R=gr及びc=myrである。平文mは、m=c/Rxのように秘密鍵xを用いて復元される。
【００７１】
＿上記のシステムはF*pにおける乗法に関して部分的に準同型である：
任意の定数K∈Mに関し、C’=(R;Kc)はメッセージm’=Kmの暗号化である。
【００７２】
・いわゆるハッシュエルガマル暗号システムは、ハッシュ関数Hに加えて、何らかのパラメータkに関し、群要素をGからFk2へ写像することを要する。メッセージ空間はM=Fk2である。鍵生成は平文エルガマルに関連する。メッセージm∈Mの暗号化は(R;c)により与えられ、何らかのランダムなr∈Z/qZに関し、R=gr及びc=m＋H(yr)ある。平文mは、m=c+H(Rx)のように秘密鍵xを用いて復元される。「+」はFk2における加法に対応することに留意を要する(すなわち、kビット文字列におけるXORと同等に考えることが可能である)。
【００７３】
＿上記のシステムはXORに関して部分的に準同型である：
任意のK∈Mに関し、C’=(R;K+c)はメッセージm’=K+mの暗号化である。
【００７４】
非限定的な例として、部分的な準同型暗号化方式(例えば、フラクトゥールE)による(A;b)の暗号化であると仮定し、(μA;μb)がM(すなわち、部分的な準同型暗号化フラクトゥールEのメッセージ空間)に属する要素である場合、ある演算子
【００７５】
【数１５】
2016510908.tif 000017
に関し、次式が成り立つ：
【００７６】
【数１６】
2016510908.tif 000018
(上記の説明において、準同型は加法的に言及されているが、同様なことが乗法的に言及される準同型についても成立する)。
【００７７】
そこで、エバリュエータ110は、Mに属するランダムマスク(μA;μb)を選択し、上記のようにcを隠し、その結果をCSP130に送信することを仮定する。そして、CSP130は、解読鍵を適用し、マスクされた値を復元することができる：
【００７８】
【数１７】
2016510908.tif 000019
その結果、上記の議論において解読がマスクの除去に置換されるプロトコルを適用することが可能になる。
【００７９】
最後に、第2及び第3プロトコルのようにマスクを利用する技術は、リッジ回帰の場合に限定されないことに留意を要する。準同型暗号化(各自の部分的な準同型暗号化)とガーブル回路とをハイブリッド形式で組み合わせる任意のアプリケーションに使用することが可能である。
【００８０】
E.考察
提案されるプロトコルは、現実世界における状況で処理を効率的及び実用的にするいくつもの強みを有する。第1に、プロセスの最中に、ユーザはオンラインに留まる必要がない。フェーズ1(420)は増加性(インクリメンタル)であるので、各々のユーザは各自の入力を送付してシステムを去ることが可能である。
【００８１】
更に、システム100は、リッジ回帰を実行することに何度も容易に適用可能である。エバリュエータが評価をf回実行することを希望する場合、準備フェーズ410の間にCSP130からf個のガーブル回路を取得することが可能である。複数の評価は、新たなユーザ120の到来に対処するために使用可能である。特に、公開鍵は長期間存続するので、それらは頻繁にリフレッシュ(更新)される必要はなく、これは、新たなユーザが更なるペア(Ai;bi)をエバリュエータ110に送付する場合に、後者は、それらを過去の値に加算し、更新後のβを算出できることを意味する。このプロセスは新たなガーブル回路を利用することを要するが、各自の入力を既に送付しているユーザは、それらを送付し直す必要はない。
【００８２】
最終的に、必要な通信量は、秘密共有法の場合よりもかなり少なくなり、エバリュエータ110及びCSP130が紛失通信(OT)を利用して通信するにすぎない。フェーズ1(420)において公開鍵暗号化εを利用すること以外に、ユーザは、エバリュエータ110との秘密通信を確立する任意の手段(例えばSSL)を利用できることに、留意を要する。
【００８３】
F.更なる最適化
行列AはRd×dに属し、ベクトルbはRdに属することを想起されたい。実数を暗号化するために使用されるビットサイズをkとすると、行列A及びbは、それぞれ、d2kビット及びdkビットを各自の表現に必要とする。第2プロトコルはMに属するランダムマスク(μA;μb)を必要とする。準同型暗号化方式フラクトゥールEがPaillier方式のトップで構築され、A及びbのエントリは全て別々にPaillier暗号化されると仮定する。この場合、フラクトゥールEのメッセージ空間Mは、何らかのRSAモジュラスNに関し、Z/NZにおける(d2+d)個の要素に分解される。しかしながら、これらの要素はkビット値であるので、全範囲Z/NZで対応するマスク値を導出する必要はない。対応するエントリを統計的に隠す限り、何らかの(比較的短い)セキュリティ長lに関し、任意の(k+l)ビットであってよい。実際には、これは、準備フェーズにおける更に少ない紛失通信及び小さなガーブル回路をもたらす。
【００８４】
効率を改善する別の方法は、A及びbの複数の平文入力を単独のPaillier暗号文にまとめる(パッキングする)標準的なバッチ技術によるものである。例えば、20個の平文の値を(十分に多くの0により分離される)1つのPaillier暗号文にパッキングすることは、フェーズ1の実行時間を20分の1に削減する。  
実現手段
プライバシ保護システムの実用性を評価するため、合成(synthetic)及び実際のデータベース双方についてシステムが実現され検査された。上記に提案される第2プロトコルが実施され、その理由は、ガーブル回路内で暗号化を必要とせず、(加算のみを含む)フェーズ1に効率的な準同型暗号化の利用を許容するからである。
【００８５】
A.フェーズ1の実現
上記に関し、準同型暗号化のために1024ビット長モジュラスとともにPaillier方式が使用され、これは80ビットのセキュリティレベルに対応する。フェーズ1を高速化するため、上述したように、オンラインによりバッチ処理も実施された。各自の入力を与えるユーザがn人であるとすると、1024ビットの1つのPaillier暗号文にバッチ処理される要素数は1024=(b+log2n)であり、ここでbは数を表現するための総ビット数である。上述したように、bは所望の精度の関数として決定され、従ってこの実施形態では、15ないし30の間の要素がまとめられる。
【００８６】
B.回路のガーブル化フレームワーク
システムはジャバ(登録商標)ベースのオープンソースフレームワークのFastGCの始めに構築され、FastGCは、開発者が、要素のXOR、OR又はANDゲートを利用する任意の回路を決定することを可能にする。回路が構築されると、そのフレームワークは、ガーブル化、紛失通信、及び、ガーブル回路の完全な評価を処理する。FastGCは幾つかの最適化を含む。第1に、回路内のXORゲートのための通信及び計算コストは、「フリーXOR」技術(非XOR化技術)を利用することで大幅に削減される。第2に、kファンイン非XORゲートの場合に計算コストをl=2kにより減らし、25％の通信節約効果をもたらし、その理由は2ファンインゲートがフレームワークで規定されるに過ぎないからである。第3に、FastGCはOT拡張を実現し、k回のOTと追加的なOTにつきいくつかの対称鍵処理とを犠牲にして、事実上回数制限のない転送を実行できる。最後に、最終的な最適化は、簡易な「3ビット加算」回路であり、4つのXORゲート(これらはすべて通信及び計算の観点からは「フリー(free)」である)及び唯1つのANDゲートによる回路を規定する。FastGCは、ガーブル化及び評価を同時に実行できるようにする。より具体的に言えば、CSP130は、回路構造により決定される順序で生成される場合にガーブル化テーブルをエバリュエータ110に送信する。エバリュエータ110は、利用可能な出力値及びテーブルに基づいて、次に何れのゲートを評価するかを決定する。ゲートが評価されると、対応するテーブルは速やかに破棄される。これは、全てのガーブル回路をオフラインで事前に計算する場合と同じ計算及び通信コストになるが、メモリ消費を一定にできる恩恵をもたらす。
【００８７】
C.回路における線形システムの解法
本アプローチの主要な課題の1つは、上記の方程式(2)に規定されるような線形システムAβ=bを解く回路を設計することである。ガーブル回路として関数を実現する場合、データを知り得ない処理(データ不可知処理)(data-agnostic)、すなわち処理の実行経路が入力に依存しない処理を利用することが望ましい。例えば、入力がガーブル化される場合、エバリュエータ110は、if-then-elseステートメントについての全ての可能な経路を実行する必要があり、これは、入れ子になった条件ステートメントが存在する場合に、回路サイズ及び実行時間の双方について指数関数的な増加を招く。これは、例えばガウス消去法のようなピボット処理(要に基づく処理)(pivoting)を要する線形システムを解く従来の何れのアルゴリズムも実現不可能にしてしまう。
【００８８】
簡明化のため、本システムは以下に説明される標準的なコレスキー(Cholesky)アルゴリズムを実行するものとする。しかしながら、その複雑さは、類似する技術を利用するブロック状反転(block-wise  inversion)と同程度の複雑さにまで更に削減可能であることに留意を要する。
【００８９】
線形システムを解くための幾つかの可能な分解法が存在する。コレスキー分解は、行列Aが対称的な正定値である場合に限り適用可能である背系システムを解くためのデータ不可知法である。コレスキー法の主な利点は、ピボット処理を必要としない数値的にロバストであることである。これは、特に、固定小数点数の表現に適している。
【００９０】
実際、λ＞0に関し、A=λI+ΣinxixiTは正定値であるので、本実現手段においてAβ=bを解く方法としてコレスキー法が選択された。
【００９１】
コレスキー分解の主要なステップは以下のように要約される。アルゴリズムは、A=LTLであるような下三角行列Lを構築し；システムAβ=bは、以下の2つのシステムを解くことに帰着する：
LTy=b；及び
Lβ=y
行列L及びLTは三角行列なので、これらのシステムは後退代入法を用いて簡易に解ける。更に、行列Aは正定値なので、行列Lは対角要素に非負の値を有する必要があり、従ってピボット処理は不要である。
【００９２】
図7には、アルゴリズム1において分解A=LTLが示されている。これは、Θ(d3)個の加算、Θ(d3)個の乗算、Θ(d2)個の除算、及びΘ(d)個の平方根演算を含む。更に、後退消去による上記の2つのシステムの解は、Θ(d2)個の加算、Θ(d3)個の乗算、及びΘ(d)個の除算を含む。これらの処理を回路として実現することが以下に説明される。
【００９３】
D.実数表現
線形システム(2)を解くために、二進形式で実数を正確に表現する必要がある。実数を表現する2つの可能なアプローチが考察され、それらは：浮動小数点と固定小数点である。実数aの浮動小数点表現は、次式により与えられる：
[a]=[m;p];ここで、a≒1.m・2p
浮動小数点表現は、多くの実際の任意の大きさに対応できる利点を有する。しかしながら、加算のような浮動小数点表現における要素的な処理は、データ不可知な方法で実現することは困難である。より重要なことに、コレスキー法を利用することは固定小数点法を利用することを必要とし、これは実現をかなり簡易にする。所与の実数aに関し、その固定小数点表現は次式で与えられる：
[a]=[a・2p];ここで、指数pは固定される。
上述したように、実行される必要がある多くの処理は、固定小数点数によりデータ不可知な形式で実行されることが可能である。従って、固定小数点表現のために生成される回路はかなり小さくなる。更に、リッジ回帰の入力変数xiは、典型的には、βの係数が比較可能でありかつ数値的に安定化するように、同じドメイン(-1ないし1の間)にスケーリングされ直すことを想起されたい。そのような設定では、オーバーフローを招かずに、固定小数点数とともに、コレスキー分解がAについて実行可能であることが分かる。更に、yiの境界及び行列Aの条件数の下で、オーバーフローを防止するのに必要なビットは、本方法における少なくとも2つの三角システムを解く間に算出可能である。こうして、このシステムは固定小数点表現を用いて実現された。小数の部分に対するpビット数は、システムパラメータとして選択可能であり、システムの精度と生成される回路のサイズとの間でトレードオフをなす。しかしながら、pを選択することは、所望の精度に基づく原則的な方法で実行されることが可能である。負の数は、標準的な2の補数表現を用いて表現される。
【００９４】
本願で開示される様々な実施形態は、ハードウェア、ファームウェア、ソフトウェア、又は、それらの組み合わせとして実現されることが可能である。更に、ソフトウェアは、好ましくは、プログラムストレージユニット又はコンピュータ読み取り可能な媒体に実際に組み込まれるアプリケーションプログラムとして実現される。アプリケーションプログラムは、適切な任意のアーキテクチャを形成するマシンにより、アップロード及び実行される。好ましくは、マシンは、1つ以上の中央処理ユニット(CPU)、メモリ及び入力/出力インタフェースのようなハードウェアを有する個ピュータプラットフォームで実現される。コンピュータプラットフォームはオペレーティングシステム及び命令コードを含んでもよい。本願で説明される様々な処理及び機能は、そのようなコンピュータ或いはプロセッサが明示的に示されているか否かによらず、CPUにより実行される、マイクロ命令コードの一部、アプリケーションプログラムの一部、又は、それらの組み合わせであってもよい。更に、追加的なデータストレージユニット及び印刷ユニット等のような他の様々な周辺ユニットが、コンピュータプラットフォームに接続されてもよい。
【００９５】
本願で使用される全ての具体例及び条件付けの言葉は、技術を進歩させるように発明者が貢献した概念及び実施形態の原理を読者が理解することを促すように教示的な目的で意図されており、そのように具体的に説明された具体例及び条件に限定することなく(本発明は)解釈されるべきである。更に、本発明についての原理、形態及び変形だけでなくそれらの具体例を示す全ての記述は、それらの構造的及び機能的双方の均等物を包含するように意図される。更に、そのような均等物は、現在既知の均等物に加えて将来的に発展する均等物の双方を包含し、すなわち構造によらず同じ機能を発揮するように開発される任意の要素を包含するように意図される。
【００９６】
関連出願
本願は2013年3月4日付けで出願された米国仮出願第61/772,404号による恩恵を享受し、米国仮出願の内容は全体的に本願のリファレンスに組み込まれる。
【００９７】
本願は「PRIVACY-PRESERVING  RIDGE  REGRESSION」及び「PRIVACY-PRESERVING  RIDGE  REGRESSION  USING  PARTIALLY  HOMOMORPHIC  ENCRYPTION  AND  MASKS」と題する出願にも関連し、それらは同日に出願されかつそれらの内容全体は本願のリファレンスに組み込まれる。
【図１】
2016510908.tif 000020
【図２】
2016510908.tif 000021
【図３】
2016510908.tif 000022
【図４】
2016510908.tif 000023
【図５】
2016510908.tif 000024
【図６】
2016510908.tif 000025
【図７】
2016510908.tif 000026
【国際調査報告】
2016510908.tif 000027
2016510908.tif 000028