(57)【要約】レコメンデーションシステムで使用されるように行列因子分解によりアイテムをセキュアにプロファイルする方法及びシステムは、如何なる個々のレコードのコンテンツも学習することなしに、トークンとアイテムとを含むレコードの組を入力として受け取り、レコードの組に対する行列因子分解に基づきGarbled回路を設計及び評価して、如何なる個々のレコードのコンテンツ又はアイテムプロファイル以外のレコードから取り出された如何なる情報も学習することなしに、少なくとも１つのアイテムに関してプライバシーを保護する様にアイテムプロファイルを生成することによって、開始する。システムは、３つのパーティ、すなわち、複数のユーザ又はレコードのためのソースに相当するデータベース、Garbled回路を設計する暗号サービスプロバイダ、及び回路を評価するレコメンダシステムを含み、それにより、レコード及び、アイテムプロファイル以外の、レコードから取り出された如何なる情報も、それらのソース以外のパーティから秘密にされる。
2016510912.tif 000002
【特許請求の範囲】
【請求項１】
行列因子分解によりアイテムをセキュアにプロファイルする方法であって、
トークンの組とアイテムの組とを有するレコードの組をソースから受け取るステップであって、夫々のレコードは前記ソース以外のパーティから秘密に保たれる、ステップと、
少なくとも１つの別のアイテムを受け取るステップと、
行列因子分解に基づきGarbled回路を使用することによってレコメンダにおいて前記レコードの組と前記少なくとも１つの別のアイテムとを評価するステップであって、前記Garbled回路の出力は前記少なくとも１つの別のアイテムについてのアイテムプロファイルを有する、ステップと
を有する方法。
【請求項２】
前記レコードの組と前記少なくとも１つの別のアイテムとに対して行列因子分解を実行するように暗号サービスプロバイダにおいて前記Garbled回路を設計するステップであって、該Garbled回路の出力は前記少なくとも１つの別のアイテムについての前記アイテムプロファイルを有する、ステップと、
前記Garbled回路を前記レコメンダに渡すステップと
を更に有する請求項１に記載の方法。
【請求項３】
前記設計するステップは、行列因子分解演算をブール回路として設計するステップを有する、
請求項２に記載の方法。
【請求項４】
前記行列因子分解演算を設計するステップは、
前記レコードの組のアレイを構成するステップと、
前記アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行するステップと
を有する、請求項３に記載の方法。
【請求項５】
暗号化されたレコードを生成するように前記レコードの組を暗号化するステップを更に有し、
前記暗号化するステップは、前記レコードの組を受け取るステップより前に実行される、
請求項２に記載の方法。
【請求項６】
公開暗号鍵を前記暗号サービスプロバイダにおいて生成するステップと、
前記鍵を前記ソースへ送るステップと
を更に有する請求項５に記載の方法。
【請求項７】
前記暗号化は、部分準同型暗号であり、当該方法は、
マスキングをかけたレコードを生成するように前記レコメンダにおいて前記暗号化されたレコードをマスキングするステップと、
暗号解読されたマスキングをかけられたレコードを生成するように前記暗号サービスプロバイダにおいて前記マスキングをかけられたレコードを暗号解読するステップと
を更に有する、請求項５に記載の方法。
【請求項８】
前記設計するステップは、前記Garbled回路内で前記暗号解読されたマスキングをかけられたレコードを、それらを処理するより前に、アンマスキングするステップを有する、
請求項７に記載の方法。
【請求項９】
前記暗号サービスプロバイダと前記レコメンダとの間で紛失通信を実行する更にステップを有し、
前記レコメンダは、前記暗号解読されたマスキングをかけられたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダ及び前記暗号サービスプロバイダから秘密にされる、
請求項７に記載の方法。
【請求項１０】
夫々のレコードのトークン及びアイテムの数を受け取るステップ
を更に有する請求項１に記載の方法。
【請求項１１】
トークンの数が最大値に相当する値に等しいレコードを生成するために、夫々のレコードのトークンの数が前記値よりも小さい場合に夫々のレコードをnullエントリで埋めるステップ
を更に有する請求項１に記載の方法。
【請求項１２】
前記レコードの組の前記ソースは、データベース、及びユーザの組のうちの１つであり、夫々のユーザは、１つのレコードのソースであり、該１つのレコードは前記夫々のユーザ以外のパーティから秘密に保たれる、
請求項１に記載の方法。
【請求項１３】
前記暗号サービスプロバイダによる前記Garbled回路の設計のための、前記レコメンダによって送信されたパラメータの組を受け取るステップ
を更に有する請求項２に記載の方法。
【請求項１４】
行列因子分解によりアイテムをセキュアにプロファイルするシステムであって、
レコードの組を提供するソースと、
セキュアな行列因子分解回路を提供する暗号サービスプロバイダと、
前記レコードが前記ソース以外のパーティから秘密にされるように前記レコードを評価するレコメンダと
を有し、
前記ソース、前記暗号サービスプロバイダ、及び前記レコメンダは、夫々が
少なくとも１つの入力／出力を受けるプロセッサと、
前記プロセッサとシグナル通信する少なくとも１つのメモリと
を有し、
前記レコメンダのプロセッサは、
夫々のレコードがトークンの組及びアイテムの組を有するレコードの組を受け取り、夫々のレコードが秘密に保たれ、
少なくとも１つの別のアイテムを受け取り、
行列因子分解に基づきGarbled回路により前記レコードの組及び前記少なくとも１つの別のアイテムを評価し、前記Garbled回路の出力が前記少なくとも１つの別のアイテムについてのアイテムプロファイルを有する
ように構成される、システム。
【請求項１５】
前記暗号サービスプロバイダのプロセッサは、
前記レコードの組及び前記少なくとも１つの別のアイテムの行列因子分解を実行するように前記Garbled回路を設計し、該Garbled回路の出力が前記少なくとも１つの別のアイテムについての前記アイテムプロファイルを有し、
前記Garbled回路を前記レコメンダに渡す
ように構成される、請求項１４に記載のシステム。
【請求項１６】
前記暗号サービスプロバイダのプロセッサは、行列因子分解演算をブール回路として設計するよう構成されることによって、前記Garbled回路を設計するよう構成される、
請求項１５に記載のシステム。
【請求項１７】
前記暗号サービスプロバイダのプロセッサは、
前記レコードの組のアレイを構成し、
前記アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行する
よう構成されることによって、前記行列因子分解演算を設計するよう構成される、
請求項１６に記載のシステム。
【請求項１８】
前記ソースのプロセッサは、前記レコードの組を提供するより前に、暗号化されたレコードを生成するように前記レコードの組を暗号化するよう構成される、
請求項１５に記載のシステム。
【請求項１９】
前記暗号サービスプロバイダのプロセッサは更に、
公開暗号鍵を生成し、
前記鍵を前記ソースへ送る
よう構成される、請求項１８に記載のシステム。
【請求項２０】
前記暗号化は、部分準同型暗号であり、
前記レコメンダのプロセッサは更に、マスキングをかけたレコードを生成するように前記暗号化されたレコードをマスキングするよう構成され、
前記暗号サービスプロバイダのプロセッサは更に、暗号解読されたマスキングをかけられたレコードを生成するように前記マスキングをかけられたレコードを暗号解読するよう構成される、
請求項１８に記載のシステム。
【請求項２１】
前記暗号サービスプロバイダのプロセッサは、前記Garbled回路内で前記暗号解読されたマスキングをかけられたレコードを、それらを処理するより前に、アンマスキングするよう構成されることによって、前記Garbled回路を設計するよう構成される、
請求項２０に記載のシステム。
【請求項２２】
前記レコメンダのプロセッサ及び前記暗号サービスプロバイダのプロセッサは更に、紛失通信を実行するよう構成され、前記レコメンダは、前記暗号解読されたマスキングをかけられたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダ及び前記暗号サービスプロバイダから秘密にされる、
請求項２０に記載のシステム。
【請求項２３】
前記レコメンダのプロセッサは更に、前記ソースによって送信された夫々のレコードのトークンの数を受け取るよう構成される、
請求項１４に記載のシステム。
【請求項２４】
前記ソースのプロセッサは、トークンの数が最大値に相当する値に等しいレコードを生成するために、夫々のレコードのトークンの数が前記値よりも小さい場合に夫々のレコードをnullエントリで埋めるよう構成される、
請求項１４に記載のシステム。
【請求項２５】
前記レコードの組の前記ソースは、データベース、及びユーザの組のうちの１つであり、
前記ソースがユーザの組である場合に、夫々のユーザは、少なくとも１つの入力／出力を受けるプロセッサと、少なくとも１つのメモリとを有し、夫々のユーザは、１つのレコードのソースであり、該１つのレコードは前記夫々のユーザ以外のパーティから秘密に保たれる、
請求項１４に記載のシステム。
【請求項２６】
前記暗号サービスプロバイダのプロセッサは更に、前記Garbled回路の設計のための、前記レコメンダによって送信されたパラメータの組を受け取るよう構成される、
請求項１５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本原理は、プライバシーを保護するレコメンデーションシステム及びセキュアな分散計算法（Secure  Multiparty  Computation）に関し、特に、アイテムをプロファイルするためにプライバシーを保護する様に、行列因子分解として知られている協調フィルタリング技術をセキュアに実行することに関する。
【背景技術】
【０００２】
この１０年における多大な研究及び商業活動は、レコメンデーションシステムの広範囲にわたる使用をもたらしてきた。そのようなシステムは、例えば映画、テレビ番組、音楽、本、ホテル、レストラン、それ以上のような、多くの種類のアイテムについて、ユーザ個別のレコメンデーションを提供する。図１は、一般的なレコメンデーションシステム１００の構成要素、すなわち、ソースに相当する多数のユーザ１１０と、ユーザの入力１２０を処理し、レコメンデーション１４０を出力するレコメンデーションシステム（RecSys）１３０とを表す。有用なレコメンデーションを受け取るために、ユーザは、自身の好みに関する十分な個人情報を、レコメンダがこのデータを適切に管理するであろうと信頼して、供給する。
それにもかかわらず、例えば、B.  Mobasher、R.  Burke、R.  Bhaumik、及びC.  Williams：“Toward  trustworthy  recommender  systems:  An  analysis  of  attack  models  and  algorithm  robustness”、ACM  Trans.  Internet  Techn.、7(4)、２００７年（非特許文献１）及びE.  Aimeur、G.  Brassard、J.  M.  Fernandez、及びF.  S.  M.  Onana：“ALAMBIC:  A  privacy-preserving  recommender  system  for  electronic  commerce”、Int.  Journal  Inf.  Sec.、7(5)、２００８年（非特許文献２）などの先の研究は、レコメンダがそのような情報を悪用したり、あるいは、ユーザをプライバシーの脅威にさらしたりし得る多くの方法を特定してきた。レコメンダは、利益のためにデータを転売したり、更には、ユーザによって意図的に明らかにされるものを越えて情報を取り出したりする気にしばしばなる。例えば、通常は機密でないと見なされるユーザ嗜好の記録、例えば映画の評価又はある個人のテレビ視聴履歴などさえも、ユーザの所属政党、性別、などを推測するのに使用され得る。レコメンデーションシステムにおいてデータから推測され得る個人情報は、新しいデータマイニングとして絶えず進化しており、推測方法は、悪意のある又は害のない目的のために、開発される。極端に、ユーザ嗜好の記録は、ユーザを一意的に識別するためにさえ使用され得る。A.  Naranyan及びV.  Shmatikovは、“Robust  de-anonymization  of  large  sparse  datasets”、IEEE  S&P、２００８年（非特許文献３）において、Netflixデータセットで匿名性を奪うことによって、このことを明白に実証した。そのようなものとして、たとえレコメンダに悪意がないとしても、そのようなデータの意図しない漏えいは、ユーザを、リンケージアタック（linkage  attacks）、すなわち、１つのデータベースを、別のデータベースでのプライバシーを危うくするように補助情報として使用する攻撃、を受けやすくする。
【０００３】
人は、将来の、推測の脅威、予想外の情報漏えい、又はインサイダーの脅威（目的のある漏えい）を常には見越すことができないので、ユーザが自身の個人データを平文で明らかにしないレコメンデーションシステムを構築することに関心が持たれている。暗号化されたデータに作用する実際的なレコメンデーションシステムは今日存在しない。加えて、ユーザが提供する評価、又はどのアイテムをユーザが評価したのかを学習することさえなしに、アイテムをプロファイルすることができるレコメンダを構築することに関心が持たれている。本原理は、そのようなセキュアなレコメンデーションシステムを提案する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】B.  Mobasher、R.  Burke、R.  Bhaumik、及びC.  Williams：“Toward  trustworthy  recommender  systems:  An  analysis  of  attack  models  and  algorithm  robustness”、ACM  Trans.  Internet  Techn.、7(4)、２００７年
【非特許文献２】E.  Aimeur、G.  Brassard、J.  M.  Fernandez、及びF.  S.  M.  Onana：“ALAMBIC:  A  privacy-preserving  recommender  system  for  electronic  commerce”、Int.  Journal  Inf.  Sec.、7(5)、２００８年
【非特許文献３】A.  Naranyan及びV.  Shmatikov、“Robust  de-anonymization  of  large  sparse  datasets”、IEEE  S&P、２００８年
【発明の概要】
【０００５】
本原理は、アイテムをプロファイルするためにプライバシーを保護する様に、行列因子分解として知られている協調フィルタリング技術をセキュアに実行する方法を提案する。特に、方法は、ユーザがアイテム（例えば、映画、本）に与えた評価を入力として受け取り、アイテムごとのプロファイルを生成する。プロファイルは、どのような評価をユーザが各アイテムに与える可能性があるのかを予測するためにその後に使用され得る。本原理は、行列因子分解に基づくレコメンダシステムが、ユーザの評価、又はどのアイテムをユーザが評価しているのかさえ学習することなしに、このタスクを実行することを可能にする。
【０００６】
本原理の一態様に従って、行列因子分解によりアイテムをセキュアにプロファイルする方法が提供される。方法は、トークンの組とアイテムの組とを有するレコードの組（２２０）をソースから受け取るステップであって、夫々のレコードは前記ソース以外のパーティから秘密に保たれる、ステップと、少なくとも１つの別のアイテムを受け取るステップ（３６０）と、行列因子分解に基づきGarbled回路を使用することによってレコメンダ（RecSys）（２３０）において前記レコードの組と前記少なくとも１つの別のアイテムとを評価するステップ（３９５）であって、前記Garbled回路の出力は前記少なくとも１つの別のアイテムについてのアイテムプロファイルを有する、ステップとを有する。方法は、前記レコードの組（３８０）と前記少なくとも１つの別のアイテム（３６０）とに対して行列因子分解を実行するように暗号サービスプロバイダ（Crypto-System  Provider）（CSP）において前記Garbled回路を設計するステップであって、該Garbled回路の出力は前記少なくとも１つの別のアイテムについての前記アイテムプロファイルを有する、ステップと、前記Garbled回路を前記RecSysに渡すステップ（３８５）とを更に有することができる。方法における前記設計するステップは、行列因子分解演算をブール回路として設計するステップ（３８２）を有することができる。方法において行列因子分解回路を設計するステップは、前記レコードの組のアレイを構成するステップ（４１０）と、前記アレイに対してソーティング（４２０，４４０，４７０，４９０）、コピー（４３０，４５０）、更新（４７０，４８０）、比較（４８０）及び勾配寄与（gradient  contributions）の計算（４６０）の動作を実行するステップとを有することができる。方法は、前記CSPによる前記Garbled回路の設計のための、前記RecSysによって送信されたパラメータの組を受け取るステップ（３３０）を更に有することができる。
【０００７】
本原理の一態様に従って、方法は、暗号化されたレコードを生成するように前記レコードの組を暗号化するステップ（３３０）を更に有することができ、前記暗号化するステップは、前記レコードの組を受け取るステップより前に実行される。方法は、公開暗号鍵が前記CSPにおいて生成されて前記ソースへ送信されるようにすることができる（３２０）。方法は、公開暗号鍵を前記CSPにおいて生成するステップと、前記鍵を前記ソースへ送るステップ（３２０）とを更に有することができる。前記暗号化のスキームは、部分準同型暗号（partially  homomorphic  encryption）（３３０）であることができ、方法は、マスキングをかけたレコードを生成するように前記RecSysにおいて前記暗号化されたレコードをマスキングするステップ（３４０）と、暗号解読されたマスキングをかけられたレコードを生成するように前記CSPにおいて前記マスキングをかけられたレコードを暗号解読するステップ（３５０）とを更に有することができる。方法における前記設計するステップ（３８０）は、前記Garbled回路内で前記暗号解読されたマスキングをかけられたレコードを、それらを処理するより前に、アンマスキングするステップを有することができる。方法は、前記CSPと前記RecSysとの間で紛失通信（oblivious  transfer）（３９２）を実行するステップ（３９０）を有することができ、前記RecSysは、前記暗号解読されたマスキングをかけられたレコードのGarbled値を受け取り、前記レコードは、前記RecSys及び前記CSPから秘密にされる。
【０００８】
本原理の一態様に従って、方法は、夫々のレコードのトークン及びアイテムの数を受け取るステップ（２２０，３１０）を更に有することができる。更に、方法は、トークンの数が最大値に相当する値に等しいレコードを生成するために、夫々のレコードのトークンの数が前記値よりも小さい場合に夫々のレコードをnullエントリで埋めるステップ（３１２）を有することができる。方法における前記レコードの組の前記ソースは、データベース、及びユーザの組（２１０）のうちの１つであることができ、夫々のユーザは、１つのレコードのソースであり、該１つのレコードはその対応するユーザ以外のパーティから秘密に保たれる。
【０００９】
本原理の一態様に従って、行列因子分解によりアイテムをセキュアにプロファイルするシステムが提供される。システムは、レコードの組を提供するソースと、セキュアな行列因子分解回路を提供する暗号サービスプロバイダ（CSP）と、前記レコードが前記ソース以外のパーティから秘密にされるように前記レコードを評価するRecSysとを有し、前記ソース、前記CSP、及び前記RecSysは、夫々が少なくとも１つの入力／出力（６０４）を受けるプロセッサ（６０２）と、前記プロセッサとシグナル通信する少なくとも１つのメモリ（６０６，６０８）とを有し、前記RecSysのプロセッサは、夫々のレコードがトークンの組及びアイテムの組を有するレコードの組を受け取り、夫々のレコードが秘密に保たれ、少なくとも１つの別のアイテムを受け取り、行列因子分解に基づきGarbled回路により前記レコードの組及び前記少なくとも１つの別のアイテムを評価し、前記Garbled回路の出力が前記少なくとも１つの別のアイテムについてのアイテムプロファイルであるように構成される。システムにおける前記CSPのプロセッサは、前記レコードの組及び前記少なくとも１つの別のアイテムの行列因子分解を実行するように前記Garbled回路を設計し、該Garbled回路が前記少なくとも１つの別のアイテムについての前記アイテムプロファイルを出力し、前記Garbled回路を前記RecSysに渡すように構成され得る。システムにおける前記CSPのプロセッサは、行列因子分解演算をブール回路として設計するよう構成されることによって、前記Garbled回路を設計するよう構成され得る。システムにおける前記CSPのプロセッサは、前記レコードの組のアレイを構成し、前記アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行するよう構成されることによって、前記行列因子分解演算を設計するよう構成され得る。システムにおける前記CSPのプロセッサは更に、前記Garbled回路の設計のための、前記RecSysによって送信されたパラメータの組を受け取るよう構成され得る。
【００１０】
本原理の一態様に従って、システムにおける前記ソースのプロセッサは、前記レコードの組を提供するより前に、暗号化されたレコードを生成するように前記レコードの組を暗号化するよう構成され得る。システムにおける前記CSPのプロセッサは更に、公開暗号鍵を生成し、前記鍵を前記ソースへ送るよう構成され得る。前記暗号化のスキームは、部分準同型暗号であることができ、前記RecSysのプロセッサは更に、マスキングをかけたレコードを生成するように前記暗号化されたレコードをマスキングするよう構成され得、前記CSPのプロセッサは更に、暗号解読されたマスキングをかけられたレコードを生成するように前記マスキングをかけられたレコードを暗号解読するよう構成され得る。システムにおける前記CSPのプロセッサは、前記Garbled回路内で前記暗号解読されたマスキングをかけられたレコードを、それらを処理するより前に、アンマスキングするよう構成されることによって、前記Garbled回路を設計するよう構成され得る。前記RecSysのプロセッサ及び前記CSPのプロセッサは更に、紛失通信を実行するよう構成され得、前記RecSysは、前記暗号解読されたマスキングをかけられたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダ及び前記暗号サービスプロバイダから秘密にされる。
【００１１】
本原理の一態様に従って、システムにおける前記RecSysのプロセッサは更に、前記ソースによって送信された夫々のレコードのトークンの数を受け取るよう構成され得る。システムにおける前記ソースのプロセッサは、トークンの数が最大値に相当する値に等しいレコードを生成するために、夫々のレコードのトークンの数が前記値よりも小さい場合に夫々のレコードをnullエントリで埋めるよう構成され得る。前記レコードの組の前記ソースは、データベース、及びユーザの組のうちの１つであることができ、前記ソースがユーザの組である場合に、夫々のユーザは、少なくとも１つの入力／出力（６０４）を受けるプロセッサ（６０２）と、少なくとも１つのメモリ（６０６，６０８）とを有し、夫々のユーザは、１つのレコードのソースであり、該１つのレコードはその対応するユーザ以外のパーティから秘密に保たれる。
【００１２】
本原理の更なる特徴及び利点は、添付の図を参照して進められる実例となる実施形態の以下の詳細な説明から明らかになるであろう。
【図面の簡単な説明】
【００１３】
本原理は、以下で簡単に記載される次の例図に従って、より良く理解され得る。
【図１】先行技術のレコメンデーションシステムの構成要素を表す。
【図２】本原理に従うレコメンデーションシステムの構成要素を表す。
【図３Ａ】本原理に従う、行列因子分解によりアイテムをプロファイルするプライバシー保護方法のフローチャートを表す。
【図３Ｂ】本原理に従う、行列因子分解によりアイテムをプロファイルするプライバシー保護方法のフローチャートを表す。
【図３Ｃ】本原理に従う、行列因子分解によりアイテムをプロファイルするプライバシー保護方法のフローチャートを表す。
【図４Ａ】本原理に従う行列因子分解アルゴリズムのフローチャートを表す。
【図４Ｂ】本原理に従う行列因子分解アルゴリズムのフローチャートを表す。
【図４Ｃ】本原理に従う行列因子分解アルゴリズムのフローチャートを表す。
【図５】本原理に従う行列因子分解アルゴリズムによって構成されるデータ構造Ｓを表す。
【図６】本原理を実施するのに利用されるコンピュータ環境のブロック図を表す。
【発明を実施するための形態】
【００１４】
本原理に従って、アイテムをプロファイルするためにプライバシーを保護する様に、行列因子分解として知られている協調フィルタリング技術をセキュアに実行する方法が、提供される。
【００１５】
本原理の方法は、夫々のレコードがトークン及びアイテムの組を有するレコードのコーパスにおいて少なくとも１つのアイテムをプロファイルするためのサービスとして働くことができる。レコードの組は１つよりも多いレコードを含み、トークンの組は少なくとも１つのトークンを含む。当業者は、上記の例において、レコードはユーザを表すことができ、トークンは、レコードに含まれる対応するアイテムに対するユーザの評価であることができると認識するであろう。トークンはまた、アイテムに関連するランク、重み、又は指標を表すこともでき、アイテムは、人、タスク、又はジョブを表すことができる。例えば、ランク、重み、又は指標は、個人の健康に関連付けられてよく、リサーチャーは、母集団の健康対策を相関させようと試みる。あるいは、それらは、個人の生産性と関連付けられてよく、企業は、それまでの履歴に基づき、特定のジョブについてのスケジュールを予測しようと試みる。なお、関連する個人のプライバシーを保証するために、サービスは、夫々のレコードのコンテンツ、又はアイテムプロファイル以外のレコードから取り出される如何なる情報も学習することなしに、そうすることを望む。特に、サービスは、（ａ）どのレコードにおいて夫々のトークン／アイテムが現れたか、又は（ｂ）どのトークン／アイテムが夫々のレコードにおいて現れるのか及び（ｃ）トークンの値さえ学習すべきでない。以下で、「プライバシー保護（privacy-preserving）」、「個人（private）」及び「セキュア（secure）」との用語は、ユーザ（レコード）によって私的であると見なされた情報がユーザによってしか知られないことを示すために同義的に使用される。
【００１６】
プライバシーを保護する様に行列因子分解を実行することに付随する幾つかの課題が存在する。第１に、プライバシーに対する懸念に対処するように、行列因子分解は、レコメンダがユーザの評価、又は彼らがどのアイテムを評価しているのかさえ学習することなしに、実行されるべきである。後者の要件は重要であり、先の研究は、どの映画をユーザが評価しているのかを知ることさえも、例えば彼らの性別を推測するために使用され得ることを示している。第２に、そのようなプライバシー保護アルゴリズムは、有効であって、ユーザによって提起される評価の数とともに率直に（例えば、線形に）増減すべきである。プライバシー要求は、行列因子分解アルゴリズムがデータ忘却型であるべきであり、その実行がユーザ入力に依存すべきでないことを暗示する。更に、行列因子分解によって実行される演算は非線形であり、よって、それら両方の制約の下で如何にして行列因子分解を有効に実施すべきかは先験的に明らかでない。最後に、実際の、現実世界のシナリオでは、ユーザは、限られた通信及び計算リソースを有し、彼らが自身のデータを供給した後に引き続きオンラインであり続けると期待されるべきではない。代わりに、レコメンデーションサービスからオンライン及びオフラインであることの間を行き来するユーザの存在下で動作することができる“応答不要送信（send  and  forget）”タイプの解決法を有することが望ましい。
【００１７】
行列因子分解の概要として、標準的な“協調フィルタリング（collaborative  filtering）”設定において、n人のユーザはm個の可能なアイテム（例えば、映画）のサブセットを評価する。[n]:={1,…,n}のユーザの組と、[m]:={1,…,m}のアイテムの組について、評価が生成されたユーザ／アイテム対はM⊆[n]×[m]によって表され、評価の総数はM=[M]によって表される。最後に、(i,j)∈Mについて、アイテムjについてユーザiによって生成される評価はri,j∈Rによって表される。実際の設定において、n及びmはいずれも大きい数であり、通常は１０４から１０６の間の範囲に及ぶ。加えて、提供される評価は疎、すなわち、M=O(n+m)であり、潜在的な評価の総数n×mよりもずっと少ない。このことは、夫々のユーザが限られた数のアイテムしか評価し得ない（m、すなわち“カタログ”サイズに依存しない）ので、典型的なユーザ挙動と一致する。
【００１８】
Mにおける評価を考えると、レコメンダシステムは、[n]×[m]＼Mにおけるユーザ／アイテム対についての評価を予測したいと望む。行列因子分解は、双一次モデルを既存の評価において適合させることによって、このタスクを実行する。特に、何らかの小さい次元d∈Nについて、
ri,j=<ui,vj>+εi,j        （１）
であるように、ベクトルui∈Rd、i∈[n]、及びvj∈Rd、j∈[m]が存在するとする。ここで、εi,jは、i.i.d（independent  and  identically  distributed）ガウスランダム変数である。ベクトルui及びvjは、夫々ユーザプロファイル及びアイテムプロファイルと呼ばれ、<ui,vj>は、ベクトルの内積である。使用されている表記法は、i番目の行がユーザiのプロファイルを有するn×d行列についてU=[uiT]i∈[n]∈Rn×dであり、j番目の行がアイテムjのプロファイルを有するm×d行列についてV=[vjT]j∈[m]∈Rm×dである。
【００１９】
評価R={ri,j:(i,j)∈M}を考えると、レコメンダは、通常は、何らかの正数λ，μ＞０について、以下の公式化された最小二乗法による最小化を実行して、プロファイルU及びVを計算する：
【数１】
2016510912.tif 000003
当業者は、プロファイルU及びVについてガウス事前分布を仮定して、（２）における最小化がU及びVの最大尤度推定に対応すると認識するであろう。ユーザプロファイル及びアイテムプロファイルによれば、レコメンダは、ユーザi及びアイテムjについて
【数２】
2016510912.tif 000004
であるように、評価
【数３】
2016510912.tif 000005
をその後に予測することができる点に留意されたい。
【００２０】
（２）における公式化された平均二乗誤差は、凸関数ではない。この最小化を実行する幾つかの方法が、文献において提案されてきた。本原理は、次のように記載される、実際に使用される一般的な手法である勾配降下に焦点を当てる。F(U,V)が（２）における公式化された平均二乗誤差を表すとすると、勾配降下は、適応ルールに従ってプロファイルU及びVを繰り返し適応させることによって動作する：
ui(t)＝ui(t-1)-γ∇uiF(U(t-1),V(t-1))
（４）
vi(t)＝vi(t-1)-γ∇viF(U(t-1),V(t-1))
ここで、γ＞０はスモールゲイン係数である。そして：
【数４】
2016510912.tif 000006
ここで、U(0)及びV(0)は、一様にランダムなノルム１の行から成る（すなわち、プロファイルは、ノルム１のボールからu.a.r.（uniformly  at  random）で選択される。）。
【００２１】
本原理の他の態様は、ソーティングネットワーク及びYaoのGarbled回路に基づく行列因子分解のためのセキュアな分散計算法（Multiparty  Computation）（MPC）を提案している。セキュアな分散計算法（MPC）は、１９８０年代にA.  Chi-Chih  Yaoによって最初に提案された。Yaoのプロトコル（別名Garbled回路）は、セキュアな分散計算法のための一般的な方法である。V.  Nikolaenko、U.  Weinsberg、S.  Ioannidis、M.  Joye、D.  Boneh、及びN.  Taftによって２０１３年にIEEE  S&Pにおいて“Privacy-preserving  Ridge  Regression  on  Hundreds  of  millions  of  records”から適応されたその変形において、プロトコルは、n個の入力オーナーの組（このとき、aiは、ユーザi（1≦i≦n）の個人入力を表す。）と、f(a1,…,an)を評価したいと望むエバリュエータと、サードパーティ、すなわち、暗号サービスプロバイダ（CSP）との間で実行される。プロトコルの終わりに、エバリュエータは、f(a1,…,an)の値を学習するが、パーティは、この出力値から明らかにされるもの以外は学習しない。プロトコルは、関数fがブール関数として、例えば、OR、AND、NOT及びXORのグラフとして、表現され得ることと、エバリュエータ及びCSPが共謀しないこととを求める。
【００２２】
近年、YaoのGarbled回路を実施する多くのフレームワークが存在する。汎用のMPCへの別のアプローチは秘密分散法（secret-sharing  schemes）に基づき、他は、完全準同型暗号（fully-homomorphic  encryption）（FHE）に基づく。秘密分散法は、様々な線形代数演算、例えば、線形システムを解くこと、線形回帰、及びオークションなどのために提案されてきた。秘密分散は、計算の仕事量を等しく共有し、複数のラウンドにわたって通信する少なくとも３つの共謀しないオンライン当局を必要とする。計算は、それらのうちの２つが共謀しない限りはセキュアである。Garbled回路は、唯２つの共謀しない当局及び極少ない通信を前提とする。そのような回路は、エバリュエータがクラウドサービスであり且つ暗号サービスプロバイダ（CSP）が信頼できるハードウェアコンポーネントにおいて実施されるシナリオにより良く適する。
【００２３】
使用される暗号プリミティブにかかわらず、セキュアな分散計算のための有効なアルゴリズムを構築することにおける主な課題は、データ忘却な様式において、すなわち、実行パスが入力に依存しないように、アルゴリズムを実施することにある。一般に、有界な時間Tにおいて実行可能な如何なるRAMプログラムも、O(T^3)チューリングマシン（Turing  Machine）（TM）に変換され得る。これは、数学上の計算のための理想的なモデルとなるようにAlan  Turingによって発明された理論計算機械である。O(T^3)は、複雑さがT3に比例することを意味する。加えて、如何なる有界なT時間のTMも、データ忘却型であるサイズO(T  log  T)の回路に変換され得る。このことは、如何なる有界なT時間の実行可能RAMプログラムも、O(T^3  log  T)の複雑さを持ったデータ忘却型回路に変換され得ることを暗示する。そのような複雑さは高過ぎ、ほとんどの用途で手が出せない。有効なデータ忘却型実施が知られていないアルゴリズムの概況は、W.  Du及びM.  J.  Atallah、“Secure  multi-party  computation  problems  and  their  applications:  A  review  and  open  problems”、New  Security  Paradigms  Workshop、２００１年において見つけられ得る。行列因子分解の問題は、データマイニングの要約問題のカテゴリに入る。
【００２４】
ソーティングネットワークは、ソーティング並列化及び有効なハードウェア実装を可能にするようにそもそも開発された。それらのネットワークは、入力シーケンス（a1,a2,…,an）を、単調増大するシーケンス（a’1,a’2,…,a’n）にソートする回路である。それらは、それらの主たる基礎的要素であるコンペア・アンド・スワップ（Compare-and-Swap）回路をワイヤでつなぎ合わせることによって構成される。幾つかの作業は、暗号化のためにソーティングネットワークのデータ忘却性を利用する。しかし、暗号化は、プライバシーを保障するのに常に十分ではない。敵が、暗号化されたストレージへのあなたのアクセスパターンを監視することができる場合は、彼らは、あなたのアプリケーションが何を行っているのかに関する機密情報を依然として学習することができる。忘却型RAMは、メモリがアクセスされている場合にそのメモリを連続的に移し替えて、どのようなデータがアクセスされているのか、又はいつそのメモリが以前にアクセスされたのかさえ完全に隠すことによって、この問題を解決する。忘却型メモリにおいて、ソーティングは、データ忘却型ランダム置換を発生させる手段として使用される。より最近では、それは、凸包、全最近傍問題（all-nearest  neighbors）、及び重み付き積集合のデータ忘却計算を実行するために使用されている。
【００２５】
本原理は、重み付き積集合に近いがGarbled回路を組み込むセキュアな分散ソーティングに基づく方法を提案する。図２は、本原理に従う、プライバシーを保護する行列因子分解における主体又は関係者を表す。それらは次のとおりである：
Ｉ．レコメンダシステム（RecSys）２３０。プライバシーを保護する行列因子分解演算を実行するエンティティ。特に、RecSysは、ユーザ評価に対する行列因子分解から取り出されるアイテムプロファイルV  ２４０を、ユーザに関して有用であるか、又はアイテムプロファイル以外のユーザデータから取り出されるあらゆるものを学習することなしに、学習したいと望む。
ＩＩ．暗号サービスプロバイダ（CSP）２５０。それは、ユーザに関して有用であるか、又はユーザデータから取り出されるあらゆるものを学習することを伴わないセキュアな計算を可能にする。
ＩＩＩ．１つ以上のユーザ２１０から成るソース。夫々のユーザは、アイテムの組２２０に対する評価の組を有する。夫々のユーザi∈[n]は、行列因子分解を通じた彼らの評価ri,j:(i,j)∈Mに基づくアイテムのプロファイリングを承諾するが、彼らの評価、又は彼らがどのアイテムを評価しているのかさえ、レコメンダに明らかにすることは望まない。同等に、ソースは、１つ以上のユーザのデータを含むデータベースに相当してよい。
【００２６】
本原理に従って、プロトコルが提案される。プロトコルは、RecSysが行列因子分解を実行してアイテムプロトコルを提供することを可能にしながら、RecSysもCSPもアイテムプロファイル、すなわち、図２におけるRecSysの唯一の出力であるV以外に何も学習しないようにする。特に、どちらも、ユーザの評価、又はどのアイテムをユーザが実際に評価しているのかさえ、学習すべきでない。当業者には当然ながら、レコメンダがユーザプロファイル及びアイテムプロファイルの両方を学習することを可能にするプロトコルはさらしすぎであり、そのような設計では、レコメンダは、通常は、（３）における内積からユーザの評価を推測することができる。そのようなものとして、本原理は、レコメンダがアイテムプロファイルしか学習しないプライバシー保護プロトコルを提案する。
【００２７】
アイテムプロファイルは、ユーザ／レコードの組の評価の関数としてアイテムを定義するメトリックと見なされ得る。同様に、ユーザプロファイルは、ユーザ／レコードの組の評価の関数としてユーザを定義するメトリックと見なされ得る。この意味において、アイテムプロファイルは、アイテムの認否の指標、すなわち、アイテムの特徴又は特性の反映である。そして、ユーザプロファイルは、ユーザの好き嫌いの指標、すなわち、ユーザの性格の反映である。ユーザ／レコードの大きな組に基づき計算される場合に、アイテム又はユーザプロファイルは、夫々、アイテム又はユーザの独立した指標と見なされ得る。当業者は、アイテムプロファイルのみを学習することに有用性があると認識するであろう。第１に、行列因子分解によるRdにおけるアイテムの埋め込みは、レコメンダが類似性を推測（及び符号化）することを可能にする。ユークリッド距離が小さいプロファイルを持つアイテムは、ユーザによって同じように評価されるアイテムである。そのようなものとして、アイテムプロファイルを学習するタスクは、レコメンデーションの実際のタスクを越えてレコメンダにとって興味深い。特に、ユーザは、ソースがデータベースである場合にそうであるように、レコメンデーションを受け取る必要性又は要望がないことがある。第２に、アイテムプロファイルを取得すると、トリビアが存在する。レコメンダは、それらを使用して、ユーザによる如何なる追加のデータ公開もなしに、関連したレコメンデーションを提供することができる。レコメンダは、Vをユーザに送信する（又はそれを公開する）ことができる。アイテムごとの自身の評価を知ると、ユーザiは、uiに関して（２）を解くことによって、自身の（個人）プロファイルuiを推測することができる。所与のV（これは分離可能な問題である。）について、そして、夫々のユーザは、リッジ回帰を自身の評価に対して実行することによって、自身のプロファイルを得ることができる。ui及びVによれば、ユーザは、（４）によりローカルで他のアイテムに対する全ての自身の評価を予測することができる。これは、本願と同日付けで“A  METHOD  AND  SYSTEM  FOR  PRIVACY-PRESERVING  RECOMMENDATION  BASED  ON  MATRIX  FACTORIZATION  AND  RIDGE  REGRESSION”と題して出願された本発明者による同時係属出願の主題である。
【００２８】
上記のシナリオのいずれも、レコメンダもユーザもVの公開に反対しないと仮定する。簡単のために、更には、レコメンダに対するそのようなプロトコルの有用性によって、本原理は、レコメンダがアイテムプロファイルを学習することを可能にする。しかし、本願と同日付けで“A  METHOD  AND  SYSTEM  FOR  PRIVACY-PRESERVING  RECOMMENDATION  TO  RATING  CONTRIBUTING  USERS  BASED  ON  MATRIX  FACTORIZATION”及び“A  METHOD  AND  SYSTEM  FOR  PRIVACY-PRESERVING  RECOMMENDATION  BASED  ON  MATRIX  FACTORIZATION  AND  RIDGE  REGRESSION”と題して出願された本発明者による同時係属出願で記載されるように、ユーザが自身の予測される評価を学習し、一方、レコメンダが、ユーザに関して有用であるか、又はユーザデータから取り出されるあらゆるもの（Vでさえない。）を学習しないように、この設計を拡張する方法も存在する。
【００２９】
当業者は、一般に、プロファイルVの出力又はユーザについての評価予測が、他のユーザの評価に関する何かを明らかにし得ると理解するであろう。例えば２つのユーザしか存在しない異常な場合において、両方の発覚は、ユーザに夫々の他方の評価を見つけさせ得る。本原理は、そのような場合に焦点を当てない。アイテムプロファイル又は個々の評価のいずれかの発覚のプライバシー推測が許容されない場合に、例えば差分プライバシーなどの技術は、それらの出力にノイズを付加して、そのような漏れから守るために使用され得る。
【００３０】
本原理に従って、安全の保障は、正直であるが好奇心が強い脅威モデルの下にあるとする。言い換えると、RecSys及びCSPは上記のプロトコルに従うが、それらの当事者は、何らかの追加情報を推測するために、オフラインでさえ、プロトコルトランスクリプトを解析することに決めることがある。更に、レコメンダ及びCSPは共謀しないとする。
【００３１】
本原理の好適な実施形態は、図３におけるフローチャート３００を満足し且つ以下のステップによって記載されるプロトコルを有する：
Ｐ１．ソースは、幾つのトークン（評価）及びアイテムの対が夫々の参加レコードについて提示されようとしているのかを、RecSysに報告する（３１０）。レコードの組は、１つよりも多いレコードを含み、レコードごとのトークンの組は、少なくとも１つのトークンを含む。
Ｐ２．CSPは、部分準同型方式のための公開暗号鍵ξを生成し、それを全てのユーザ（ソース）へ送信する（３２０）。当業者に明らかなように、準同型暗号化は、特定のタイプの計算が暗号文に対して実行され、暗号解読されたものが平文に対して実行された演算の結果と一致する暗号化結果を得ることを可能にする暗号化の形式である。例えば、１人は２つの暗号化された数字を加え、次いで、他者は、個々の数字の値を見つけることができなくても、その結果を暗号解読することができる。部分準同型暗号化は、平文に対する１つの演算（加算又は乗算）に関して準同型である。部分準同型暗号化は、スカラーに対する加算及び乗算に関して準同型であってよい。
Ｐ３．夫々のユーザは、そのデータをその鍵を用いて暗号化し、自身の暗号化されたデータをRecSysに送信する（３３０）。特に、jがアイテムIDであり且つri,jがユーザiがjに与えた評価であるとして、あらゆる対（j,ri,j）について、ユーザは、この対を、公開暗号鍵を用いて暗号化する。
Ｐ４．RecSysは、暗号化されたデータにマスクηを加え、マスキングされた暗号化されたデータをCSPへ送信する（３４０）。当業者は、マスクがデータ難読化の一形式であり、乱数発生器を加えること又は乱数によってごちゃ混ぜにすることと同じくらい簡単であり得ると理解するであろう。
Ｐ５．CSPは、マスキングされたデータを暗号解読する（３５０）。
Ｐ６．RecSysは、行列因子分解を計算すべきアイテムの別の組を受け取るか、又は決定する（３６０）。このアイテムの組は、コーパス内の全てのアイテム、全てのアイテムのサブセット、又はレコードに存在しないアイテムさえも含んでよい。
Ｐ７．RecSysは、ユーザプロファイル及びアイテムプロファイルの大きさ（すなわち、パラメータd）３７２と、評価の総数（すなわち、パラメータM）３７４と、ユーザ及びアイテムの総数３７６と、Garbled回路における実数の整数及び小数部分を表すのに使用されるビットの数３７８とを含む、Garbled回路を構築するのに必要な完全な仕様をCSPに送信する（３７０）。アイテムの別の組は、全てのアイテムがレコードに存在しない場合に、パラメータに含まれる。
Ｐ８．CSPは、アイテムの別の組に関してレコードに対して行列因子分解を実行するGarbled回路として当業者に知られるものを準備する（３８０）。難読化されている（Garbled）ために、回路は、最初に、ブール回路３８２として作成される。回路への入力は、RecSysがユーザデータをマスキングするために使用したマスクを有する。回路内で、マスクは、データをアンマスキングするために使用され、次いで、行列因子分解を実行する。回路の出力はV、すなわち、ユーザプロファイルである。如何なる個々のレコードの、及びアイテムプロファイル以外にレコードから取り出される如何なる情報のコンテンツに関しても認識は得られない。
Ｐ９．CSPは、行列因子分解のためのGarbled回路をRecSysへ送信する（３８５）。具体的に、CSPは、Garbled回路へのゲートを処理し、それらを、回路構造によって定義された順序において、RecSysへ送信する。
Ｐ１０．RecSysとCSPとの間３９２の紛失通信３９０を通じて、RecSysは、それ自身又はCPSのいずれもが実際の値を学習することなしに、暗号解読されたマスキングされたレコードのGarbled値を学習する。当業者は、紛失通信が、送信側が潜在的に多数存在する情報片のうちの１つを受信側に転送し、（もしあれば）どのような片が転送されたのかに関して忘却したままである転送の一種である。
Ｐ１１．RecSysは、アイテムプロファイルVを計算するGarbled回路を評価し、そのアイテムプロファイルVを出力する（３９５）。
【００３２】
通常は、このプロトコルは、Vを越えて更に、夫々のユーザによって与えられるトークンの数を漏らす。これは、簡単なプロトコル変更によって、例えば、予めセットされた最大数に達するまで、提示されたレコードを適切に“null”エントリにより“埋める（padding）”こと３１２によって、修正され得る。簡単のために、プロトコルは、この“埋める”動作なしで記載された。
【００３３】
Garbled回路が一度しか使用され得ないので、同じ評価に関する如何なる将来の計算も、ユーザが彼らのデータをプロキシ紛失通信を通じて再提示することを必要とする。プロキシ紛失通信は、３つ以上の当事者が関わる紛失通信である。このために、本原理のプロトコルは、公開鍵暗号化をGarbled回路と組み合わせる複合的なアプローチを導入した。
【００３４】
本原理において、公開鍵暗号化は、次のように使用される。夫々のユーザiは、意味的にセキュアな（semantically  secure）暗号化アルゴリズムξpkCSPを持ったCSPによって提供される公開鍵pkCSPの下で、各自の入力(j,ri,k)を暗号化し、評価される夫々のアイテムjについて、ユーザは、c=ξpkCSP(j,ri,j)である対（i,c）をRecSysへ提示する。このとき、全部でM個の評価が提示される。自身の評価を提示したユーザはオフラインになることができる。
【００３５】
CSPの公開鍵暗号化アルゴリズムは、部分的に準同型である。定数は、対応する暗号解読鍵を知らずに、暗号化されたメッセージに適用され得る。明らかに、例えばPaillier又はRegevなどの加法準同型方式も定数を加えるために使用され得るが、部分的にしか準同型でないハッシュElGamalで十分であり、この場合に、より有効に実装され得る。
【００３６】
ユーザからM個の評価を受け取ると、暗号化が部分的に準同型であることを思い出して、RecSysは、ランダムマスク
【数５】
2016510912.tif 000007
によりそれらを覆い隠す。ここで、ηは、ランダム又は疑似ランダム変数であり、丸で囲まれた＋記号は、XOR演算である。RecSysは、それらを、Garbled回路を構築するのに必要とされる完全な仕様とともにCSPへ送信する。特に、RecSysは、ユーザ及びアイテムの大きさ（すなわち、パラメータd）と、評価の総数（すなわち、パラメータM）と、ユーザ及びアイテムの総数と、Garbled回路における実数の整数及び小数部分を表すのに使用されるビットの数とを特定する。アイテムの別の組は、全てのアイテムがレコードに存在しない場合に、パラメータに含まれる。
【００３７】
RecSysがM個の累積された評価に対して行列因子分解を実行したと望むときはいつでも、それはMをCSPへ報告する。CSPは、（ａ）入力を暗号解読し、次いで（ｂ）行列因子分解を実行するGarbled回路をRecSysに提供してよい。V.  Nikolaenko、U.  Weinsberg、S.  Ioannidis、M.  Joye、D.  Boneh、及びN.  Taft、“Privacy-preserving  ridge  regression  on  hundreds  of  millions  of  records”、IEEE  S&P、２０１３年において、その回路内での暗号解読は、マスク及び準同型暗号化を用いることによって回避される。本原理は、この考えを行列因子分解に対して利用するが、部分準同型暗号化法しか必要としない。
【００３８】
暗号化を受け取ると、CSPはそれらを暗号解読し、マスキングされた値
【数６】
2016510912.tif 000008
を得る。次いで、行列因子分解を青写真として使用すると、CSPはYaoのGarbled回路を準備する。Garbled回路は：
（ａ）マスクηに対応するGarbled値を入力としてとり；
（ｂ）対応するタプル（i,j,ri,j）を回復するようにマスクηを取り除き；
（ｃ）行列因子分解を実行し；且つ
（ｄ）アイテムプロファイルVを出力する。
【００３９】
（４）及び（５）において説明された勾配降下演算による行列因子分解の計算は、実数の加算、減算及び乗算を伴う。それらの演算は、回路において有効に実施され得る。勾配降下（４）のK回の繰り返しは、K個の回路“レイヤ”に対応する。夫々のレイヤは、前のレイヤにおける値からプロファイルの新しい値を計算する。回路の出力はアイテムプロファイルVであり、一方、ユーザプロファイルは捨てられる。
【００４０】
当業者に明らかなように、勾配降下の夫々の繰り返しを計算する時間的コストは、演算が平文で、例えばRAMモデルで、実行される場合に、O(M)である。夫々の勾配の計算（５）は、2M個の項を加算することを伴い、プロファイル更新（４）は、O(n+m)=O(M)で実行され得る。
【００４１】
勾配降下を回路として実装することにおける主要な課題は、有効にそれを行うことにある。これを説明するように、次の単純な実施が考えられ得る：
Ｑ１．夫々の対(i,j)∈[n]×[m]について、入力から、iがjを評価した場合に１であり、そうでない場合に０であるインジケータδi,j=1(i,j)∈Mを計算する回路を生成する。
Ｑ２．夫々の繰り返しで、それらの回路の出力を用いて、夫々のアイテム及びユーザ勾配を、夫々、m個及びn個の成果物にわたる合計として計算する。このとき：
【数７】
2016510912.tif 000009
【００４２】
あいにく、この実施は効率的でない。勾配降下アルゴリズムの全ての繰り返しは、O(n×m)の回路複雑性を有する。通常は実際にそうであるように、M≪n×mの場合に、上記の回路は、平文において勾配降下よりも大々的にそれほど効率的でない。実際に、二次費用O(n×m)は、ほとんどのデータセットにとって手が出せない。単純な実施の効率の悪さは、データにおける内在的な疎性を利用する能力を軽減しながら、回路設計時点で、どれをユーザが評価するのか及びどのアイテムがユーザによって評価されるのかを特定することができないことに起因する。
【００４３】
反対に、本原理の好適な実施形態に従って、回路実施は、複雑さがO((n+m+M)log2(n+m+M))であるソーティングネットワークに基づき、すなわち、平文での実施の多対数因数（polylogarithmic  factor）内で、提供される。要約すれば、タプル（i,j,ri,j）に対応する入力データと、ユーザプロファイル及びアイテムプロファイルの両方ためのプレースホルダー⊥とは両方とも、アレイ内に一緒に格納される。適切なソーティング動作を通じて、ユーザプロファイル又はアイテムプロファイルは、それらが識別子を共有する入力の近くに配置され得る。データを通じた線形パスは、勾配の計算と、プロファイルの更新とを可能にする。ソーティング時に、プレースホルダーは、+∞として、すなわち、あらゆる他の数よりも大きいものとして扱われる。
【００４４】
本原理の好適な実施形態に従う、図４におけるフローチャート４００を満足する行列因子分解アルゴリズムは、次のステップによって記載され得る：
Ｃ１．行列Ｓを初期化する（４１０）。アルゴリズムは、入力として組Li={(j,ri,j):(i,j)∈M}、又は同等に、タプル{(i,j,ri,j):(i,j)∈M}を受け取り、タプルのn+m+Mを組み立てる。Sの最初のn個及びm個のタプルは、夫々、ユーザプロファイル及びアイテムプロファイルのためのプレースホルダーとなり、一方、残りのM個のタプルは入力Liを保持する。より具体的には、夫々のユーザi∈[n]について、アルゴリズムはタプル（i,⊥,0,⊥,ui,⊥）を組み立てる。このとき、ui∈Rdは、ランダムに選択されたユーザiの初期プロファイルである。夫々のアイテムj∈[m]について、アルゴリズムは、タプル（⊥,j,0,⊥,⊥,vj,⊥）を組み立てる。このとき、vj∈Rdは、やはりランダムに選択されたアイテムjの初期プロファイルである。最後に、夫々の対(i,j)∈Mについて、アルゴリズムは、対応するタプル（i,j,1,ri,j,⊥,⊥）を組み立てる。このとき、ri,jは、アイテムjに対するユーザiの評価である。結果として得られるアレイは図５（Ａ）に示されるとおりである。k番目のタプルのl番目の要素をsl,kによって表すと、それらの要素は次の役割を果たす：
（ａ）s1,k：[n]におけるユーザ識別子；
（ｂ）s2,k：[m]におけるアイテム識別子；
（ｃ）s3,k：タプルが“プロファイル”又は“入力”タプルである場合を示すバイナリフラグ；
（ｄ）s4,k：“入力”タプルにおける評価
（ｅ）s5,k：Rdにおけるユーザプロファイル；
（ｆ）s6,k：Rdにおけるアイテムプロファイル。
Ｃ２．ユーザ識別子に対して（行１及び３に関して）昇順にタプルをソートする（４２０）。２つの識別子が等しい場合は、タプルフラグ、すなわち、夫々のタプルにおける３番目の要素を比較することによって、均衡が破られる。よって、ソーティング後、夫々の“ユーザプロファイル”タプルは、同じ識別子を持った“入力”タプルが後に続く。
Ｃ３．ユーザプロファイルをコピーする（レフトパス）（４３０）：
s5,k  ←  s3,k*S5,k-1+(1-s3,k)*S5,k    （k=2,…,M+n）
Ｃ４．アイテム識別子に対して（行２及び３に関して）昇順にタプルをソートする（４４０）。２つの識別子が等しい場合に、タプルフラグ、すなわち、夫々のタプルにおける３番目の要素を比較することによって、均衡が破られる。
Ｃ５．アイテムプロファイルをコピーする（レフトパス）（４５０）：
s6,k  ←  s3,k*S6,k-1+(1-s3,k)*S6,k    （k=2,…,M+n）
Ｃ６．勾配寄与∀k＜Mを計算する（４６０）：
【数８】
2016510912.tif 000010
Ｃ７．アイテムプロファイルを更新する（ライトパス）（４７０）：
s6,k  ←  S6,k+s3,k+1*S6,k+1+(1-s3,k)*2γμS6,k    （k=M+n-1,…,1）
Ｃ８．行１及び３に対してタプルをソートする（４７５）。
Ｃ９．ユーザプロファイルを更新する（ライトパス）（４８０）：
s5,k  ←  S5,k+s3,k+1*S5,k+1+(1-s3,k)*2γμS5,k    （k=M+n-1,…,1）
Ｃ１０．繰り返しの数がKよりも小さい場合は、Ｃ３へ移動する（４８５）。
Ｃ１１．行３及び２に対してタプルをソートする（４９０）。
Ｃ１２．k=1,…,mについて、アイテムプロファイルs6,kを出力する。このとき、出力は、少なくとも１つのアイテムプロファイルに制限されてよい。
【００４５】
勾配降下の繰り返しは、以下の３つの主要なステップを有する：
Ａ．プロファイルのコピー：
夫々の繰り返しで、夫々の個別ユーザi及び夫々のアイテムjのプロファイルui及びvjは、i及びjが現れる夫々の“入力”タプルの対応する要素s5,k及びs6,kにコピーされる。これは、アルゴリズムのステップＣ２からＣ５で実施される。例えば、ユーザプロファイルをコピーするよう、Sは、主索引としてユーザ識別子（すなわち、s1,k）を、及び二次索引としてフラグ（すなわち、s3,k）を用いてソートされる。Sの初期状態に適用されるそのようなソーティングの例は、図５（Ｂ）において見つけられ得る。その後に、ユーザ識別子は、アルゴリズムのステップＣ３において形式的に記載されているように、左から右へアレイをトラバースすること（“レフト”パス）によって、コピーされる。これは、s5,kを夫々の“プロファイル”タプルからその隣接する“入力”タプルにコピーする。アイテムプロファイルは同様にコピーされる。
Ｂ．勾配寄与の計算：
プロファイルがコピーされた後、例えば(i,j)に対応する夫々の“入力”タプルは、最後の繰り返しにおいて計算されたプロファイルui及びvj（夫々、s5,k及びs6,kに含まれる。）並びに評価ri,j（s4,kに含まれる。）を格納する。それらから、次の量：vj(ri,j-<ui,vj>)及びui(ri,j-<ui,vj>)が計算される。これは、（５）によって与えられるui及びvjに対する勾配におけるタプルの“寄与”と見なされ得る。それらは、アルゴリズムのステップＣ６によって示されるように、タプルのs5,k及びs6,kを置換する。フラグの適切な使用を通じて、この演算は“入力”タプルのみに作用し、“プロファイル”タプルを不変なままとする。
Ｃ．プロファイルの更新：
最後に、ユーザプロファイル及びアイテムプロファイルは、アルゴリズムステップＣ７からＣ９において示されたように、更新される。適切なソーティングを通じて、“プロファイル”タプルは、それらが識別子を共有する“入力”タプルに再び隣接される。更新されたプロファイルは、アレイを右から左へトラバースすること（“ライトパス”）を通じて計算される。この演算は、それが“入力”タプルをトラバースする場合に、勾配の寄与を加える。“プロファイル”タプルにぶつかると、積算された勾配寄与が、適切に増減されながらプロファイルに加えられる。プロファイルを過ぎた後、勾配寄与の積算は、フラグs3,k,s3,k+1の使用を通じて、ゼロから再開する。
【００４６】
上記の演算はK回、すなわち、勾配公開の所望の繰り返しの回数、繰り返されるべきである。最終的に、最後の繰り返しの終了時に、アレイは、主索引としてのフラグ（すなわち、s3,k）、及び二次索引としてのアイテム識別子（すなわち、s2,k）に関して、ソートされる。これは、アレイ内の最初のm個の位置において全てのアイテムプロファイルタプルを引き込む。それから、アイテムプロファイルは出力され得る。更に、ユーザプロファイルを得るために、最後の繰り返しの終了時に、アレイは、主索引としてのフラグ（すなわち、s3,k）、及び二次索引としてのユーザ識別子（すなわち、s1,k）に関して、ソートされる。これは、アレイ内の最初のn個の位置において全てのユーザプロファイルタプルを引き込む。それから、ユーザプロファイルは出力され得る。
【００４７】
当業者は、上記の演算の夫々はデータ無効型であり、回路として実装され得ると認識するであろう。プロファイルをコピー及び更新することは、(n+m+M)個のゲートを必要とするので、全体の複雑さは、例えばBatcherの回路を用いてO((n+m+M)log2(n+ｍ＋M))費用をもたらすソーティングによって、決定される。アルゴリズムのステップＣ６におけるソーティング及び勾配計算は、最も計算集約的な演算であり、有り難いことに、両方とも大いに並列化可能である。加えて、ソーティングは、前に計算された比較を夫々の繰り返しで再利用することで、更に最適化され得る。特に、この回路は、ブール回路として（例えば、OR、AND、NOT及びXORゲートとして）実装され得る。このことは、先に説明されたように、実施が難読化されていることを可能にする。
【００４８】
本原理に従って、上記のプロトコルとともに上記の行列因子分解アルゴリズムを実施することは、プライバシーを保護する様に、行列因子分解のための新規な方法を提供する。加えて、この解決法は、ソーティングネットワークを用いることによって平文で実行される行列因子分解の多対数因数（polylogarithmic  factor）内の複雑さを持った回路をもたらす。更に、この実施の更なる利点は、この回路の難読化（garbling）及び実行が大いに並列化可能である点である。
【００４９】
本原理に従うシステムの実施において、Garbled回路構成は、公然と利用可能なGarbled回路のフレームワークであるFastGCに基づいた。FastGCは、Java（登録商標）ベースのオープンソースフレームワークであり、基本のXOR、OR及びANDゲートによる回路定義を可能にする。回路が構成されると、フレームワークは、Garbled回路の難読化、紛失通信、及び徹底的な評価を扱う。回路を難読化及び実行する前に、FastGCは、Java（登録商標）オブジェクトの組として、メモリにおいて、難読化されていない回路の全体を表す。それらのオブジェクトは、ゲートのサブセットのみが如何なる時点でも難読化及び／又は実行される場合に、難読化されていない回路が導入すべきメモリフットプリントに対してかなりのメモリオーバーヘッドを招く。更に、たとえFastGCが、上述されたように、実行プロセスと並行して難読化を実行するとしても、両演算は順次的に起こる。すなわち、ゲートは、それらの入力が準備できると、一度に１つを処理される。当業者には当然に、この実施は並列化に従わない。
【００５０】
結果として、フレームワークは、FastGCのメモリフットプリントを低減しながら、複数のプロセッサにわたって並列化された難読化及び計算を可能にするという、それら２つの問題に対処するように変更された。特に、我々は、回路を水平方向に順次的な“レイヤ”に分割する能力を導入した。夫々のレイヤは、並行して実行され得る垂直な“スライス”の組を有する。レイヤは、全てのその入力が準備できる場合にのみメモリにおいて生成される。それが難読化及び評価されると、レイヤ全体がメモリから削除され、次のレイヤが構成され得る。よって、メモリフットプリントは、最大レイヤのサイズに制限される。レイヤの実行は、そのスライスをスレッドに割り当てて、それらが並行して実行されることを可能にするスケジューラにより実行される。たとえ並列化が複数のコアを備えた単一の機械において実施されたとしても、実施は、スライス間での共有状態が考えられないために、異なる機械にわたって率直に実行されるように拡張され得る。
【００５１】
最後に、アルゴリズムにおいて説明された多数の演算を実装するように、FastGCは、ソーティングに加えて、固定小数点表現による実数に対する加算及び乗算をサポートするように拡張された。ソーティングのために、Batcherのソーティングネットワークが使用された。固定小数点表現は、切り捨てにより生じる正確さの喪失と回路のサイズとの間のトレードオフを導入した。
【００５２】
更に、アルゴリズムの実施は、多数の方法において最適化された。特に：
（ａ）それは、回路の実行の開始において計算された比較を再利用することによって、ソーティングの費用を削減した：
ソーティングネットワークの基本的構成単位は、２つのアイテムを比較して、必要に応じてそれらを置換し、出力対が順序付けられるようにするコンペア・アンド・スワップ（Compare-and-Swap）回路である。行列因子分解アルゴリズムのソーティング動作（ラインＣ４及びＣ８）は、繰り返しごとに厳密に同じ入力を用いて、K回の勾配降下の繰り返しの夫々でタプル間での同じ比較を実行する。実際に、夫々のソーティングは、夫々の繰り返しで、厳密に同じように、アレイSにおいてタプルの順序を変える。この特性は、それらのソーティングの夫々について比較動作を一度だけ実行することによって、享受される。特に、フォーム（i,j,フラグ,評価）のタプルのソーティングは、計算の開始において（ユーザプロファイル又はアイテムプロファイルのペイロードなしで）、例えば、最初にi及びフラグ、j及びフラグ、そしてi及びフラグに帰って、実行される。その後に、比較（comparison）回路の出力は、勾配降下の間に使用される置換（swap）回路への入力として、それらのソーティングの夫々において再利用される。結果として、夫々の繰り返しで適用される“ソーティング”ネットワークは、如何なる比較も実行せず、単にタプルの順序を変える（すなわち、それは“置換”ネットワークである。）。
（ｂ）それは、アレイSのサイズを削減した：
全ての比較を再計算することは、我々がSにおけるタプルのサイズを大々的に更に削減することを可能にする。まず第１に、当業者に明らかなように、ユーザ識別子又はプロファイル識別子に対応する行は、ソーティングの間に比較への入力としてのみ行列因子分解アルゴリズムにおいて使用される。フラグ及び評価は、コピー及び更新フェーズの間に使用されるが、それらの相対的な位置は夫々の繰り返しで同じである。更に、それらの位置は、我々の計算の開始時にタプル（i,j,フラグ,評価）のソーティングの出力として計算され得る。そのようなものとして、夫々の繰り返しで実行される“置換”動作は、ユーザプロファイル及びアイテムプロファイルにのみ適用される必要がある。全ての他の行はアレイSから削除され得る。１つの更なる改善は、ひと組のプロファイル、例えばユーザを固定し、アイテムプロファイルのみを置換するように、２の補助係数によって置換の費用を削減する。次いで、アイテムプロファイルは２つの状態の間で循環する。夫々の状態は、他方から置換を通じて到達可能である。アイテムプロファイルがユーザプロファイル及び部分勾配とアライメントされる状態と、アイテムプロファイルが更新されてコピーされる状態とがある。
（ｃ）それは、XORを用いることによって置換動作を最適化した：
もしXOR演算が“フリー（free）”で実行されるならば、比較、置換、更新及びコピー動作の最適化は、可能ならばいつでもXORを用いることによって実行される。当業者に明らかなように、Free-XORゲートは、関連するGarbledテーブル及び対応するハッシング又は対称鍵動作によらずに難読化され得る。これは、計算及び通信における際だった改善を表す。
（ｄ）それは、計算を並列化した：
ソーティング及び勾配計算は、行列因子分解回路における計算の大部分を構成する（ソーティング及び更新は、実行時間の３％及び非XORゲートの０．４％しか構成しない。）。それらの演算は、FastGCの当該実行を通じて並列化される。勾配計算は明らかに並列化可能であり、ソーティングネットワークも大いに並列化可能である（並列化は、それらの開発の背後にある主たる動機付けである。）。更に、夫々のソートにおける並列スライスの多くは同じであるから、回路スライスを定義する同じFastGCオブジェクトは異なる入力により再利用される。これは、メモリにおいてオブジェクトを繰り返し生成及び破棄する必要性を大幅に減らす。
【００５３】
本原理は、様々な形態のハードウェア、ソフトウェア、ファームウェア、特別目的のプロセッサ、又はそれらの組み合わせにおいて実装されてよい点が理解されるべきである。好適には、本原理は、ハードウェア及びソフトウェアの組み合わせとして実装される。更に、ソフトウェアは、好適には、プログラム記憶装置において有形に具現されるアプリケーションプログラムとして実装される。アプリケーションプログラムは、如何なる適切なアーキテクチャも有する機械にアップロードされ、それによって実行されてよい。好適には、機械は、例えば１つ以上の中央演算処理装置（CPU）、ランダムアクセスメモリ（RAM）、及び入出力（I/O）インタフェースなどのハードウェアを備えるコンピュータプラットフォームにおいて実装されてよい。コンピュータプラットフォームは、オペレーティングシステム及びマイクロ命令コードを更に有する。ここで記載される様々なプロセス及び機能は、オペレーティングシステムを介して実行されるマイクロ命令コードの部分又はアプリケーションプログラムの部分（あるいは、それらの組み合わせ）のいずれかであってよい。加えて、様々な他の周辺機器、例えば、追加のデータ記憶装置及び印刷装置などが、コンピュータプラットフォームに結合されてよい。
【００５４】
図６は、本原理を実施するために使用される最低限のコンピュータ環境６００のブロック図を示す。コンピュータ環境６００は、プロセッサ６１０と、少なくとも１つ（好適には１つ以上）のI/Oインタフェース６２０とを有する。I/Oインタフェースは、有線又は無線であることができ、無線実施では、本原理が、例えば、遠隔でエンドユーザに提供されるサース（Software  as  a  Service）（SAAS）として提供されることを可能にするように、コンピュータ環境６００がグローバルネットワーク（例えば、インターネット）上で動作して、他のコンピュータ又はサーバ（例えば、クラウドベースのコンピュータ又は記憶サーバ）と通信することを可能にするよう適切な無線通信プロトコルにより予め設定される。１つ以上のメモリ６３０及び／又は記憶装置（HDD）６４０が更にコンピュータ環境６００内に設けられる。コンピュータ環境６００又は複数のコンピュータ環境６００は、本原理の一実施形態に従う行列因子分解Ｃ１〜Ｃ１２（図４）のために、プロトコルＰ１〜Ｐ１１（図３）を実施してよい。特に、本原理の実施形態において、コンピュータ環境６００はRecSys２３０を実装してよく、別のコンピュータ環境６００はCSP２５０を実装してよく、ソースは、RecSys２３０及びCSP２５０と通信するのに使用されるデスクトップコンピュータ、携帯電話機、スマートフォン、電話機能付き腕時計、タブレットコンピュータ、パーソナルデジタルアシスタント（PDA）、ネットブック及びラップトップコンピュータを含むがそれらに限られない、夫々が個別のユーザ２１０に関連付けられた１つ又は複数のコンピュータ環境６００を含んでよい。加えて、CSP２５０は、ソースにおいて含まれるか、あるいは、同等に、ソースの各ユーザ２１０のコンピュータ環境に含まれてよい。
【００５５】
添付の図面において表されている構成するシステムコンポーネント及び方法ステップの一部は、好適にはソフトウェアにおいて実施されるので、システムコンポーネント（又はプロセスステップ）間の実際の接続は、本原理がプログラムされる様態に応じて異なってよい点が理解されるべきである。ここでの技術を鑑みて、当業者は、本原理のそれらの及びより簡単な実施又は構成を考えつくことができるであろう。
【００５６】
実例となる実施形態がここで添付の図面を参照して記載されてきたが、本原理はそれらの厳密な実施形態に制限されず、様々な変更及び改良が、本原理の適用範囲及び主旨から逸脱することなしに、それらにおいて当業者によって達成され得る点が理解されるべきである。全てのそのような変更及び改良は、添付の特許請求の範囲で挙げられている本原理の適用範囲内に含まれるよう意図される。
【００５７】
［関連出願の相互参照］
本願は、２０１３年８月９日付けで出力された米国特許仮出願第６１／８６４０８８号（発明の名称“A  METHOD  AND  SYSTEM  FOR  PRIVACY  PRESERVING  MATRIX  FACTORIZATION”）、米国特許仮出願第６１／８６４０８５号（発明の名称“A  METHOD  AND  SYSTEM  FOR  PRIVACY  PRESERVING  COUNTING”）、米国特許仮出願第６１／８６４０９４号（発明の名称“A  METHOD  AND  SYSTEM  FOR  PRIVACY-PRESERVING  RECOMMENDATION  TO  RATING  CONTRIBUTING  USERS  BASED  ON  MATRIX  FACTORIZATION”）、及び米国特許仮出願第６１／８６４０９８号（発明の名称“A  METHOD  AND  SYSTEM  FOR  PRIVACY-PRESERVING  RECOMMENDATION  BASED  ON  MATRIX  FACTORIZATION  AND  RIDGE  REGRESSION”）に基づく優先権の利益を享受するものである。加えて、本願は、２０１３年１２月１９日付けで出願された国際特許出願第ＰＣＴ／ＵＳ１３／７６３５３号（発明の名称“A  METHOD  AND  SYSTEM  FOR  PRIVACY  PRESERVING  COUNTING”）、及び２０１３年３月４日付けで出願された米国特許仮出願第６１／７７２４０４号（発明の名称“PRIVACY-PRESERVING  LINEAR  AND  RIDGE  REGRESSION”）に基づく優先権の利益を享受するものである。これらの仮出願及び国際特許出願は、その全文を参照により本願に援用される。
【図１】
2016510912.tif 000011
【図２】
2016510912.tif 000012
【図３Ａ】
2016510912.tif 000013
【図３Ｂ】
2016510912.tif 000014
【図３Ｃ】
2016510912.tif 000015
【図４Ａ】
2016510912.tif 000016
【図４Ｂ】
2016510912.tif 000017
【図４Ｃ】
2016510912.tif 000018
【図５】
2016510912.tif 000019
【図６】
2016510912.tif 000020
【手続補正書】
【提出日】平成27年9月10日(2015.9.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
レコードの組をソースから受け取るステップであって、前記レコードの組に含まれる夫々のレコードはトークンの組とアイテムの組とを有し、夫々のレコードは前記ソース以外のパーティから秘密に保たれる、ステップと、
少なくとも１つの別のアイテムを受け取るステップと、
行列因子分解に基づきGarbled回路を使用することによって前記レコードの組と前記少なくとも１つの別のアイテムとを評価するステップであって、前記Garbled回路の出力は夫々の少なくとも１つの別のアイテムについてのアイテムプロファイルを有する、ステップと
を有する方法。
【請求項２】
前記レコードの組と前記少なくとも１つの別のアイテムとに対して行列因子分解を実行するように暗号サービスプロバイダから前記Garbled回路を受け取るステップを有し、
該Garbled回路の出力は夫々の少なくとも１つの別のアイテムについての前記アイテムプロファイルを有する、
請求項１に記載の方法。
【請求項３】
前記Garbled回路は、前記行列因子分解の演算をブール回路として実装する、
請求項２に記載の方法。
【請求項４】
前記Garbled回路は、前記レコードの組のアレイを構成し、前記アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行する、
請求項３に記載の方法。
【請求項５】
前記レコードは、暗号化されたレコードである、
請求項２に記載の方法。
【請求項６】
前記暗号化は、部分準同型暗号であり、当該方法は、
マスキングをかけたレコードを生成するように前記暗号化されたレコードをマスキングするステップと、
暗号解読のために前記暗号サービスプロバイダへ前記マスキングをかけられたレコードを転送するステップと
を更に有する、請求項５に記載の方法。
【請求項７】
前記Garbled回路は、前記暗号解読をなされたマスキングをかけられたレコードをアンマスキングする、
請求項６に記載の方法。
【請求項８】
前記暗号サービスプロバイダとレコメンダシステムとの間で紛失通信を実行するステップを更に有し、
前記レコメンダシステムは、前記暗号解読をなされたマスキングをかけられたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダシステム及び前記暗号サービスプロバイダから秘密にされる、
請求項６に記載の方法。
【請求項９】
夫々のレコードのトークン及びアイテムの数を受け取るステップと、
前記Garbled回路の実装のために暗号サービスプロバイダへパラメータの組を送信するステップであって、前記パラメータは、レコメンダシステムによって送信された、ステップと
を更に有する請求項１に記載の方法。
【請求項１０】
前記レコードは、トークンの数が最大値に等しいレコードを生成するために、夫々のレコードのトークンの数が前記最大値よりも小さい値である場合にnullエントリで埋められる、
請求項１に記載の方法。
【請求項１１】
前記レコードの組の前記ソースは、データベース、及びユーザの組のうちの１つであり、夫々のユーザは、１つのレコードのソースであり、該１つのレコードは前記夫々のユーザ以外のパーティから秘密に保たれる、
請求項１に記載の方法。
【請求項１２】
前記Garbled回路の実装のために前記暗号サービスプロバイダへパラメータの組を送信するステップであって、前記パラメータは、レコメンダシステムによって送信された、ステップ
を更に有する請求項２に記載の方法。
【請求項１３】
少なくとも１つの入力／出力インタフェースと通信するプロセッサと、
前記プロセッサとシグナル通信する少なくとも１つのメモリと
を有し、
前記プロセッサは、
ソースからレコードの組を受け取り、該レコードの組に含まれる夫々のレコードがトークンの組とアイテムの組とを有し、夫々のレコードが前記ソース以外のパーティから秘密に保たれ、
少なくとも１つの別のアイテムを受け取り、
行列因子分解に基づきGarbled回路により前記レコードの組及び前記少なくとも１つの別のアイテムを評価し、前記Garbled回路の出力が夫々の少なくとも１つの別のアイテムについてのアイテムプロファイルを有する
ように構成される、装置。
【請求項１４】
前記プロセッサは、
前記レコードの組及び前記少なくとも１つの別のアイテムの行列因子分解を実行するように暗号サービスプロバイダから前記Garbled回路を受け取り、該Garbled回路の出力が夫々の少なくとも１つの別のアイテムについての前記アイテムプロファイルを有する
ように更に構成される、請求項１３に記載の装置。
【請求項１５】
前記Garbled回路は、前記行列因子分解の演算をブール回路として実装する、
請求項１４に記載の装置。
【請求項１６】
前記Garbled回路は、前記レコードの組のアレイを構成し、前記アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行する、
請求項１５に記載の装置。
【請求項１７】
前記レコードは、暗号化されたレコードである、
請求項１４に記載の装置。
【請求項１８】
前記暗号化は、部分準同型暗号であり、
前記プロセッサは更に、マスキングをかけたレコードを生成するように前記暗号化されたレコードをマスキングし、暗号解読のために前記暗号サービスプロバイダへ前記マスキングをかけたレコードを転送するよう構成される、
請求項１７に記載の装置。
【請求項１９】
前記Garbled回路は、前記暗号解読をなされたマスキングをかけられたレコードをアンマスキングする、
請求項１８に記載の装置。
【請求項２０】
前記プロセッサは更に、前記暗号サービスプロバイダとの紛失通信を実行するよう構成され、レコメンダシステムは、前記暗号解読をなされたマスキングをかけられたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダシステム及び前記暗号サービスプロバイダから秘密にされる、
請求項１８に記載の装置。
【請求項２１】
前記プロセッサは更に、前記ソースによって送信された夫々のレコードのトークンの数を受け取り、前記Garbled回路の実装のために暗号サービスプロバイダへパラメータの組を送信するよう構成される、
請求項１３に記載の装置。
【請求項２２】
前記レコードは、トークンの数が最大値に等しいレコードを生成するために、夫々のレコードのトークンの数が前記最大値よりも小さい場合にnullエントリで埋められる、
請求項１３に記載の装置。
【請求項２３】
前記レコードの組の前記ソースは、データベース、及びユーザの組のうちの１つであり、
前記ソースがユーザの組である場合に、夫々のユーザは、少なくとも１つの入力／出力を受けるプロセッサと、少なくとも１つのメモリとを有し、夫々のユーザは、１つのレコードのソースであり、該１つのレコードは前記夫々のユーザ以外のパーティから秘密に保たれる、
請求項１３に記載の装置。
【請求項２４】
前記プロセッサは更に、前記Garbled回路の実装のために前記暗号サービスプロバイダへパラメータの組を送信するよう構成される、
請求項１４に記載の装置。
【請求項２５】
夫々のレコードが夫々のユーザから受け取られ且つトークンの組とアイテムの組とを有するレコードの組と、少なくとも１つの別のアイテムとに対して行列因子分解を実行するようにGarbled回路を実装するステップであって、夫々のレコードは前記夫々のレコード以外のパーティから秘密に保たれ、前記Garbled回路の出力は夫々の少なくとも１つの別のアイテムについてのアイテムプロファイルを有する、ステップと、
前記Garbled回路を評価して前記アイテムプロファイルを供給するレコメンダシステムへ前記Garbled回路を転送するステップと
を有する方法。
【請求項２６】
前記実装するステップは、行列因子分解演算をブール回路として実装することを有する、
請求項２５に記載の方法。
【請求項２７】
前記Garbled回路は、前記レコードの組のアレイを構成し、該アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行することによって、行列因子分解を実行する、
請求項２６に記載の方法。
【請求項２８】
公開暗号鍵を生成するステップと、
前記公開暗号鍵を前記夫々のユーザへ送信するステップと
を更に有する請求項２５に記載の方法。
【請求項２９】
暗号化は、部分準同型暗号化であり、当該方法は、
マスキングをかけたレコードを前記レコメンダシステムから受け取るステップと、
暗号解読されたマスキングをかけたレコードを生成するように前記マスキングをかけたレコードを暗号解読するステップと
を更に有する、請求項２８に記載の方法。
【請求項３０】
前記実装するステップは、前記暗号解読されたマスキングをかけたレコードを処理するより前に該暗号解読されたマスキングをかけたレコードをアンマスキングすることを有する、
請求項２９に記載の方法。
【請求項３１】
前記レコメンダシステムとの紛失通信を実行するステップを更に有し、
前記レコメンダシステムは、前記暗号解読されたマスキングをかけたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダシステム及び暗号サービスプロバイダから秘密にされる、
請求項２９に記載の方法。
【請求項３２】
少なくとも１つの入力／出力インタフェースと通信するプロセッサと、
前記プロセッサとシグナル通信する少なくとも１つのメモリと
を有し、
前記プロセッサは、
夫々のレコードが夫々のユーザから受け取られ且つトークンの組とアイテムの組とを有するレコードの組と、少なくとも１つの別のアイテムとに対して行列因子分解を実行するようにGarbled回路を実装し、夫々のレコードが前記夫々のレコード以外のパーティから秘密に保たれ、前記Garbled回路の出力が夫々の少なくとも１つの別のアイテムについてのアイテムプロファイルを有し、
前記Garbled回路を評価して前記アイテムプロファイルを供給するレコメンダシステムへ前記Garbled回路を転送する
ように構成される、装置。
【請求項３３】
前記Garbled回路は、前記行列因子分解の演算をブール回路として実装する、
請求項３２に記載の装置。
【請求項３４】
前記Garbled回路は、前記レコードの組のアレイを構成し、該アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行することによって、行列因子分解を実行する、
請求項３３に記載の装置。
【請求項３５】
前記プロセッサは、公開暗号鍵を生成し、該公開暗号鍵を前記夫々のユーザへ送信するように更に構成される、
請求項３２に記載の装置。
【請求項３６】
暗号化は、部分準同型暗号化であり、前記プロセッサは、
マスキングをかけたレコードを前記レコメンダシステムから受け取り、
暗号解読されたマスキングをかけたレコードを生成するように前記マスキングをかけたレコードを暗号解読する
ように更に構成される、請求項３５に記載の装置。
【請求項３７】
前記プロセッサは、前記暗号解読されたマスキングをかけたレコードを処理するより前に該暗号解読されたマスキングをかけたレコードをアンマスキングするように更に構成されることによって、実装するように構成される、
請求項３６に記載の装置。
【請求項３８】
前記プロセッサは、前記レコメンダシステムとの紛失通信を実行するように更に構成され、
前記レコメンダシステムは、前記暗号解読されたマスキングをかけたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダシステム及び暗号サービスプロバイダから秘密にされる、
請求項３６に記載の装置。
【請求項３９】
レコードをレコメンダシステムへ送信するステップを有し、
夫々のレコードは、トークンの組とアイテムの組とを有し、ユーザ以外のパーティから秘密に保たれ、
前記レコメンダシステムは、前記ユーザによって送信された前記レコードを含むレコードの組と、少なくとも１つの別のアイテムとを、行列因子分解に基づきGarbled回路により評価し、
前記Garbled回路の出力は、夫々の少なくとも１つの別のアイテムについてのアイテムプロファイルを有する、
方法。
【請求項４０】
前記レコードを供給するより前に、該レコードを暗号化して、暗号化されたレコードを生成するステップ
を更に有する請求項３９に記載の方法。
【請求項４１】
少なくとも１つの入力／出力インタフェースと通信するプロセッサと、
前記プロセッサとシグナル通信する少なくとも１つのメモリと
を有し、
前記プロセッサは、レコードをレコメンダシステムへ送信するように構成され、
夫々のレコードは、トークンの組とアイテムの組とを有し、ユーザ以外のパーティから秘密に保たれ、
前記レコメンダシステムは、前記ユーザによって送信された前記レコードを含むレコードの組と、少なくとも１つの別のアイテムとを、行列因子分解に基づきGarbled回路により評価し、
前記Garbled回路の出力は、夫々の少なくとも１つの別のアイテムについてのアイテムプロファイルを有する、
装置。
【請求項４２】
前記プロセッサは、前記レコードを供給するより前に、該レコードを暗号化して、暗号化されたレコードを生成するように更に構成される、
請求項４１に記載の装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
実例となる実施形態がここで添付の図面を参照して記載されてきたが、本原理はそれらの厳密な実施形態に制限されず、様々な変更及び改良が、本原理の適用範囲及び主旨から逸脱することなしに、それらにおいて当業者によって達成され得る点が理解されるべきである。全てのそのような変更及び改良は、添付の特許請求の範囲で挙げられている本原理の適用範囲内に含まれるよう意図される。  
上記の実施形態に加えて、以下の付記を開示する。
（付記１）
行列因子分解によりアイテムをセキュアにプロファイルする方法であって、
トークンの組とアイテムの組とを有するレコードの組をソースから受け取るステップであって、夫々のレコードは前記ソース以外のパーティから秘密に保たれる、ステップと、
少なくとも１つの別のアイテムを受け取るステップと、
行列因子分解に基づきGarbled回路を使用することによってレコメンダにおいて前記レコードの組と前記少なくとも１つの別のアイテムとを評価するステップであって、前記Garbled回路の出力は前記少なくとも１つの別のアイテムについてのアイテムプロファイルを有する、ステップと
を有する方法。
（付記２）
前記レコードの組と前記少なくとも１つの別のアイテムとに対して行列因子分解を実行するように暗号サービスプロバイダにおいて前記Garbled回路を設計するステップであって、該Garbled回路の出力は前記少なくとも１つの別のアイテムについての前記アイテムプロファイルを有する、ステップと、
前記Garbled回路を前記レコメンダに渡すステップと
を更に有する付記１に記載の方法。
（付記３）
前記設計するステップは、行列因子分解演算をブール回路として設計するステップを有する、
付記２に記載の方法。
（付記４）
前記行列因子分解演算を設計するステップは、
前記レコードの組のアレイを構成するステップと、
前記アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行するステップと
を有する、付記３に記載の方法。
（付記５）
暗号化されたレコードを生成するように前記レコードの組を暗号化するステップを更に有し、
前記暗号化するステップは、前記レコードの組を受け取るステップより前に実行される、
付記２に記載の方法。
（付記６）
公開暗号鍵を前記暗号サービスプロバイダにおいて生成するステップと、
前記鍵を前記ソースへ送るステップと
を更に有する付記５に記載の方法。
（付記７）
前記暗号化は、部分準同型暗号であり、当該方法は、
マスキングをかけたレコードを生成するように前記レコメンダにおいて前記暗号化されたレコードをマスキングするステップと、
暗号解読されたマスキングをかけられたレコードを生成するように前記暗号サービスプロバイダにおいて前記マスキングをかけられたレコードを暗号解読するステップと
を更に有する、付記５に記載の方法。
（付記８）
前記設計するステップは、前記Garbled回路内で前記暗号解読されたマスキングをかけられたレコードを、それらを処理するより前に、アンマスキングするステップを有する、
付記７に記載の方法。
（付記９）
前記暗号サービスプロバイダと前記レコメンダとの間で紛失通信を実行するステップを更に有し、
前記レコメンダは、前記暗号解読されたマスキングをかけられたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダ及び前記暗号サービスプロバイダから秘密にされる、
付記７に記載の方法。
（付記１０）
夫々のレコードのトークン及びアイテムの数を受け取るステップ
を更に有する付記１に記載の方法。
（付記１１）
トークンの数が最大値に相当する値に等しいレコードを生成するために、夫々のレコードのトークンの数が前記値よりも小さい場合に夫々のレコードをnullエントリで埋めるステップ
を更に有する付記１に記載の方法。
（付記１２）
前記レコードの組の前記ソースは、データベース、及びユーザの組のうちの１つであり、夫々のユーザは、１つのレコードのソースであり、該１つのレコードは前記夫々のユーザ以外のパーティから秘密に保たれる、
付記１に記載の方法。
（付記１３）
前記暗号サービスプロバイダによる前記Garbled回路の設計のための、前記レコメンダによって送信されたパラメータの組を受け取るステップ
を更に有する付記２に記載の方法。
（付記１４）
行列因子分解によりアイテムをセキュアにプロファイルするシステムであって、
レコードの組を提供するソースと、
セキュアな行列因子分解回路を提供する暗号サービスプロバイダと、
前記レコードが前記ソース以外のパーティから秘密にされるように前記レコードを評価するレコメンダと
を有し、
前記ソース、前記暗号サービスプロバイダ、及び前記レコメンダは、夫々が
少なくとも１つの入力／出力を受けるプロセッサと、
前記プロセッサとシグナル通信する少なくとも１つのメモリと
を有し、
前記レコメンダのプロセッサは、
夫々のレコードがトークンの組及びアイテムの組を有するレコードの組を受け取り、夫々のレコードが秘密に保たれ、
少なくとも１つの別のアイテムを受け取り、
行列因子分解に基づきGarbled回路により前記レコードの組及び前記少なくとも１つの別のアイテムを評価し、前記Garbled回路の出力が前記少なくとも１つの別のアイテムについてのアイテムプロファイルを有する
ように構成される、システム。
（付記１５）
前記暗号サービスプロバイダのプロセッサは、
前記レコードの組及び前記少なくとも１つの別のアイテムの行列因子分解を実行するように前記Garbled回路を設計し、該Garbled回路の出力が前記少なくとも１つの別のアイテムについての前記アイテムプロファイルを有し、
前記Garbled回路を前記レコメンダに渡す
ように構成される、付記１４に記載のシステム。
（付記１６）
前記暗号サービスプロバイダのプロセッサは、行列因子分解演算をブール回路として設計するよう構成されることによって、前記Garbled回路を設計するよう構成される、
付記１５に記載のシステム。
（付記１７）
前記暗号サービスプロバイダのプロセッサは、
前記レコードの組のアレイを構成し、
前記アレイに対してソーティング、コピー、更新、比較及び勾配寄与の計算の動作を実行する
よう構成されることによって、前記行列因子分解演算を設計するよう構成される、
付記１６に記載のシステム。
（付記１８）
前記ソースのプロセッサは、前記レコードの組を提供するより前に、暗号化されたレコードを生成するように前記レコードの組を暗号化するよう構成される、
付記１５に記載のシステム。
（付記１９）
前記暗号サービスプロバイダのプロセッサは更に、
公開暗号鍵を生成し、
前記鍵を前記ソースへ送る
よう構成される、付記１８に記載のシステム。
（付記２０）
前記暗号化は、部分準同型暗号であり、
前記レコメンダのプロセッサは更に、マスキングをかけたレコードを生成するように前記暗号化されたレコードをマスキングするよう構成され、
前記暗号サービスプロバイダのプロセッサは更に、暗号解読されたマスキングをかけられたレコードを生成するように前記マスキングをかけられたレコードを暗号解読するよう構成される、
付記１８に記載のシステム。
（付記２１）
前記暗号サービスプロバイダのプロセッサは、前記Garbled回路内で前記暗号解読されたマスキングをかけられたレコードを、それらを処理するより前に、アンマスキングするよう構成されることによって、前記Garbled回路を設計するよう構成される、
付記２０に記載のシステム。
（付記２２）
前記レコメンダのプロセッサ及び前記暗号サービスプロバイダのプロセッサは更に、紛失通信を実行するよう構成され、前記レコメンダは、前記暗号解読されたマスキングをかけられたレコードのGarbled値を受け取り、前記レコードは、前記レコメンダ及び前記暗号サービスプロバイダから秘密にされる、
付記２０に記載のシステム。
（付記２３）
前記レコメンダのプロセッサは更に、前記ソースによって送信された夫々のレコードのトークンの数を受け取るよう構成される、
付記１４に記載のシステム。
（付記２４）
前記ソースのプロセッサは、トークンの数が最大値に相当する値に等しいレコードを生成するために、夫々のレコードのトークンの数が前記値よりも小さい場合に夫々のレコードをnullエントリで埋めるよう構成される、
付記１４に記載のシステム。
（付記２５）
前記レコードの組の前記ソースは、データベース、及びユーザの組のうちの１つであり、
前記ソースがユーザの組である場合に、夫々のユーザは、少なくとも１つの入力／出力を受けるプロセッサと、少なくとも１つのメモリとを有し、夫々のユーザは、１つのレコードのソースであり、該１つのレコードは前記夫々のユーザ以外のパーティから秘密に保たれる、
付記１４に記載のシステム。
（付記２６）
前記暗号サービスプロバイダのプロセッサは更に、前記Garbled回路の設計のための、前記レコメンダによって送信されたパラメータの組を受け取るよう構成される、
付記１５に記載のシステム。
【国際調査報告】
2016510912.tif 000021
2016510912.tif 000022
2016510912.tif 000023