(57)【要約】行列因数分解によって推薦を安全に生成するための方法及びシステムであって、如何なる個人のレコードのコンテンツを学習することなく、トークンの組および項目の組を含むレコードの組を入力として受け取るステップと、レコードの組に対する行列因数分解に基づいてガーブル回路を設計及び評価して、如何なる個人のレコード、又は、推薦を含む、レコードから抽出された如何なる情報のコンテンツも学習せずに、少なくとも１つの項目についてプライバシー保護のやり方で、推薦を生成するステップとによって開始する。本システムは：複数のユーザ又はレコードのソースを表すデータベース；ガーブル回路を設計する暗号サービスプロバイダ及び当該回路を評価するリコメンダシステムからなる３つのパーティを含み、その結果、レコード及びレコードから抽出された任意の情報がこれらのソース以外のパーティには秘密に保たれ、推薦は要求パーティによってのみ知られる。
2016517069.tif 000002
【特許請求の範囲】
【請求項１】
行列因数分解によって推薦を安全に生成するための方法であって、前記方法は、
レコードの組（２２０）を受け取るステップであって、各レコードは、それぞれのユーザから受け取られ、トークンの組および項目の組を備え、各レコードは、前記それぞれのユーザ以外のパーティに秘密に保たれる、ステップと、
要求ユーザから少なくとも１つの特定の項目に対する要求を受け取るステップ（３３０）と、
行列因数分解に基づいてガーブル回路を用いることによって、リコメンダ（ＲｅｃＳｙｓ）（２３０）において前記レコードの組を評価するステップ（３５５）であって、前記ガーブル回路の出力は、前記少なくとも１つの特定の項目に対するマスクされた項目プロファイルと、１つの前記要求ユーザに対するマスクされたユーザプロファイルと、を備える、ステップと、
前記少なくとも１つの特定の項目について前記要求ユーザに対する推薦を生成するために、前記要求ユーザと、前記ＲｅｃＳｙｓと、暗号サービスプロバイダ（ＣＳＰ）との間で、前記マスクされた項目プロファイルおよび前記マスクされたユーザプロファイルを共同で評価するステップ（３６０〜３８５）であって、前記要求ユーザに対する各推薦およびユーザプロファイルは、前記要求ユーザ以外のパーティには秘密に保たれ、前記少なくとも１つの特定の項目に対する前記項目プロファイルは、すべてのパーティに秘密に保たれ、ユーザプロファイルおよび項目プロファイルは、それぞれの前記マスクされた項目プロファイルおよびマスクされたユーザプロファイルのマスク解除されたバージョンである、ステップと、
を含む、前記方法。
【請求項２】
前記レコードの組に対して行列因数分解を実行するために前記ＣＳＰにおいて前記ガーブル回路を設計するステップ（３４０）であって、前記ガーブル回路の出力は、前記少なくとも１つの特定の項目に対するマスクされた項目プロファイルおよび前記１つの要求ユーザに対するマスクされたユーザプロファイルを含む、ステップと、
前記ガーブル回路を前記ＲｅｃＳｙｓに伝送するステップ（３４５）と、
をさらに含む、請求項１に記載の方法。
【請求項３】
設計する前記ステップは、行列因数分解演算をブール回路として設計するステップ（３４０２）を含む、請求項２に記載の方法。
【請求項４】
行列因数分解回路を設計する前記ステップは、
前記レコードの組の配列を構築するステップと、前記配列に対して、ソートし（４２０、４４０、４７０、４９０）、コピーし（４３０、４５０）、更新し（４７０、４８０）、比較し（４８０）、勾配寄与を計算する（４６０）、動作を実行するステップと、を含む、請求項３に記載の方法。
【請求項５】
前記レコードの組を暗号化して、暗号化されたレコードを生成する、暗号化するステップ（３１５）をさらに含み、前記暗号化するステップは、レコードの組を受け取るステップの前に実行される、請求項２に記載の方法。
【請求項６】
前記ＣＳＰにおいて公開暗号化鍵を生成するステップと、
前記鍵を前記それぞれのユーザに送るステップと、
をさらに含む、請求項５に記載の方法。
【請求項７】
前記暗号化は、部分的準同型暗号化であり（３１０）、前記方法は、
前記ＲｅｃＳｙｓにおいて前記暗号化されたレコードをマスクして、マスクされたレコードを生成するステップ（３２０）と、
前記ＣＳＰにおいて前記マスクされたレコードを復号して、復号済みのマスクされたレコードを生成するステップと、
を含む、請求項５に記載の方法。
【請求項８】
設計する前記ステップ（３４０）は、
それらを処理する前に前記ガーブル回路内で前記復号済みのマスクされたレコードをマスク解除するステップを含む、請求項７に記載の方法。
【請求項９】
前記ＣＳＰと前記ＲｅｃＳｙｓとの間（３５０２）で、紛失通信を実行するステップ（３５０）であって、前記ＲｅｃＳｙｓは、前記復号済みのマスクされたレコードのガーブル値を受け取り、前記レコードは、前記ＲｅｃＳｙｓ及び前記ＣＳＰには秘密に保たれる、ステップをさらに含む、請求項７に記載の方法。
【請求項１０】
共同で評価する前記ステップは、
前記マスクされたユーザプロファイルを第１のマスクでマスク解除して前記ユーザプロファイルを取得するステップ（３６０）と、
前記ユーザプロファイルを暗号化して、暗号化されたユーザプロファイルを生成するステップ（３６０）と、
前記ＲｅｃＳｙｓにおいて、前記少なくとも１つの特定の項目に対する前記暗号化されたユーザプロファイルとマスクされた項目プロファイルとの第１の積を計算するステップ（３７０）と、
前記ＣＳＰにおいて、前記少なくとも１つの特定の項目に対する前記暗号化されたユーザプロファイルと少なくとも第２のマスクとの少なくとも１つの第２の積を計算するステップ（３７５）と、
前記ＲｅｃＳｙｓにおいて、前記第１の積から前記少なくとも１つの第２の積を減算して、前記少なくとも１つの特定の項目に対する少なくとも１つの暗号化された推薦を生成するステップ（３８０）と、
前記少なくとも１つの特定の項目に対する前記少なくとも１つの暗号化された推薦を復号するステップ（３８５）と、
をさらに含む、請求項１に記載の方法。
【請求項１１】
前記第１のマスクは、前記要求ユーザによって選択され（３１５）、前記少なくとも１つの第２のマスクは、前記ＣＳＰによって選択される（３４０）、請求項１０に記載の方法。
【請求項１２】
暗号化および復号する前記ステップは、前記要求ユーザによって選択された加法的準同型暗号方式を用いる（３６０）、請求項１０に記載の方法。
【請求項１３】
各レコードのトークンおよび項目の数を受け取るステップ（２２０、３０５）をさらに含む、請求項１に記載の方法。
【請求項１４】
各レコードのトークンの数が最大値を表す値より小さいときに、前記値に等しいトークンの数を有するレコードを生成するために、ヌルエントリで各レコードをパッディングするステップ（３０５２）をさらに含む、請求項１に記載の方法。
【請求項１５】
前記レコードの組のソースは、データベースとすることができる、請求項１に記載の方法。
【請求項１６】
前記ＣＳＰによる前記ガーブル回路の前記設計のためのパラメータの組を受け取るステップであって、前記パラメータは、前記ＲｅｃＳｙｓによって送られた（３３５）、ステップをさらに含む、請求項２に記載の方法。
【請求項１７】
行列因数分解によって推薦を安全に生成するためのシステムであって、前記システムは、レコードのそれぞれの組を提供するユーザの組と、安全な行列因数分解回路を提供する暗号サービスプロバイダ（ＣＳＰ）と、各レコードがそれぞれのユーザ以外のパーティに秘密に保たれるように前記レコードを評価するＲｅｃＳｙｓと、を備え、各ユーザ、前記ＣＳＰ、および前記ＲｅｃＳｙｓはそれぞれ、
少なくとも１つの入力／出力（６０４）を受け取るためのプロセッサー（６０２）と、
前記プロセッサーと信号通信する少なくとも１つのメモリ（６０６、６０８）と、を含み、前記ＲｅｃＳｙｓのプロセッサーは、
レコードの組を受け取ることであって、各レコードは、トークンの組および項目の組を含み、各レコードは、前記それぞれのユーザ以外のパーティに秘密に保たれる、レコードの組を受け取ることと、
要求ユーザから少なくとも１つの特定の項目に対する要求を受け取ることと、
行列因数分解に基づいてガーブル回路によって前記レコードの組を評価することであって、前記ガーブル回路の出力は、前記少なくとも１つの特定の項目に対するマスクされた項目プロファイルおよび１つの前記要求ユーザに対するマスクされたユーザプロファイルを備える、評価することと、を実行するように構成され、
前記要求ユーザ、ＲｅｃＳｙｓ、およびＣＳＰのプロセッサーは、前記少なくとも１つの特定の項目について前記要求ユーザに推薦を生成するために、前記マスクされた項目プロファイルおよび前記マスクされたユーザプロファイルを共同で評価するように構成され（３６０〜３８５）、
前記要求ユーザに対する各推薦およびユーザプロファイルは、前記要求ユーザ以外のパーティには秘密に保たれ、前記少なくとも１つの特定の項目に対する前記項目プロファイルはすべてのパーティに秘密に保たれ、ユーザプロファイルおよび項目プロファイルは、それぞれの前記マスクされた項目プロファイルおよびマスクされたユーザプロファイルのマスク解除されたバージョンである、前記システム。
【請求項１８】
前記ＣＳＰのプロセッサーは、前記レコードの組に対して行列因数分解を実行するために前記ガーブル回路を設計することであって、前記ガーブル回路の出力は、前記少なくとも１つの特定の項目に対するマスクされた項目プロファイルと、前記１つの要求ユーザに対するマスクされたユーザプロファイルと、を含む、設計することと、
前記ガーブル回路を前記ＲｅｃＳｙｓに伝送することと、
を実行するように構成される、請求項１７に記載のシステム。
【請求項１９】
前記ＣＳＰのプロセッサーは、行列因数分解演算をブール回路として設計するように構成されることによって前記ガーブル回路を設計するように構成される、請求項１８に記載のシステム。
【請求項２０】
前記ＣＳＰのプロセッサーは、
前記レコードの組の配列を構築し、
前記配列に対して、ソートし、コピーし、更新し、比較し、および勾配寄与を計算する動作を実行ように構成されることによって前記行列因数分解回路を設計するように構成される、請求項１９に記載のシステム。
【請求項２１】
各ユーザのプロセッサーは、前記レコードを提供する前に、前記それぞれのレコードを暗号化して、暗号化されたレコードを生成するように構成される、請求項１８に記載のシステム。
【請求項２２】
前記ＣＳＰのプロセッサーは、
前記ＣＳＰにおいて公開暗号鍵を生成し、
前記鍵を前記ユーザの組に送る
ようにさらに構成される、請求項２１に記載のシステム。
【請求項２３】
前記暗号化は、部分的準同型暗号化であり、
前記ＲｅｃＳｙｓのプロセッサーは、前記暗号化されたレコードをマスクして、マスクされたレコードを生成するようにさらに構成され、
前記ＣＳＰのプロセッサーは、前記マスクされたレコードを復号して、復号済みのマスクされたレコードを生成するようにさらに構成される、請求項２１に記載のシステム。
【請求項２４】
前記ＣＳＰのプロセッサーは、前記復号済みのマスクされたレコードを、それらを処理する前に、前記ガーブル回路内部でマスク解除するようにさらに構成されることによって、前記ガーブル回路を設計するように構成される、請求項２３に記載のシステム。
【請求項２５】
前記ＲｅｃＳｙｓのプロセッサーおよび前記ＣＳＰのプロセッサーは、紛失通信を実行するようにさらに構成され、前記ＲｅｃＳｙｓは、前記復号済みのマスクされたレコードの前記ガーブル化された値を受け取り、前記レコードは、前記ＲｅｃＳｙｓおよび前記ＣＳＰに秘密に保たれる、請求項２３に記載のシステム。
【請求項２６】
前記要求ユーザのプロセッサーは、
前記マスクされたユーザプロファイルを第１のマスクでマスク解除して、前記ユーザプロファイルを取得し、
前記ユーザプロファイルを暗号化して、暗号化されたユーザプロファイルを生成し、
前記少なくとも１つの特定の項目に対する少なくとも１つの暗号化された推薦を復号する
ようにさらに構成され、前記ＲｅｃＳｙｓのプロセッサーは、
前記少なくとも１つの特定の項目に対する前記暗号化されたユーザプロファイルと前記マスクされた項目プロファイルとの第１の積を計算し、
前記第１の積から少なくとも１つの第２の積を減算して、前記少なくとも１つの特定の項目に対する少なくとも１つの暗号化された推薦を生成する
ようにさらに構成され、前記ＣＳＰのプロセッサーは、
前記ＣＳＰにおいて、前記少なくとも１つの特定の項目に対する前記暗号化されたユーザプロファイルと少なくとも１つの第２のマスクとの少なくとも１つの第２の積を計算するようにさらに構成される、請求項１７に記載のシステム。
【請求項２７】
前記第１のマスクは、前記要求ユーザによって選択され、前記少なくとも１つの第２のマスクは前記ＣＳＰによって選択される、請求項２６に記載のシステム。
【請求項２８】
前記要求ユーザのプロセッサーは、前記要求ユーザによって選択された加法的準同型暗号方式を用いるように構成される、請求項２６に記載のシステム。
【請求項２９】
前記ＲｅｃＳｙｓのプロセッサーは、各レコードのトークンの数を受け取るようにさらに構成され、前記トークンの数はソースによって送られた、請求項１７に記載のシステム。
【請求項３０】
各ユーザのプロセッサーは、各レコードのトークンの数が最大値を表す値より小さいときに、前記値に等しいトークンの数を有するレコードを生成するために、ヌルエントリで前記各レコードをパッディングするように構成される、請求項１７に記載のシステム。
【請求項３１】
前記レコードの組のソースは、データベースとすることができる、請求項１７に記載のシステム。
【請求項３２】
前記ＣＳＰのプロセッサーは、前記ガーブル回路の前記設計のためのパラメータの組を受け取るようにさらに構成され、前記パラメータは前記ＲｅｃＳｙｓによって送られた、請求項１８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、第６１／８６４０８８号明細書で名称が「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」、第６１／８６４０８５号明細書で名称が「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＣＯＵＮＴＩＮＧ」、第６１／８６４０９４号明細書で名称が「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＴＯ  ＲＡＴＩＮＧ  ＣＯＮＴＲＩＢＵＴＩＮＧ  ＵＳＥＲＳ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」、および第６１／８６４０９８号明細書で名称が「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ  ＡＮＤ  ＲＩＤＧＥ  ＲＥＧＲＥＳＳＩＯＮ」の、２０１３年８月９日に出願された米国特許仮出願の利益および優先権を主張するものである。さらに、本出願は、２０１３年１２月１９日に出願された「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＣＯＵＮＴＩＮＧ」という名称のＰＣＴ特許出願第ＰＣＴ／ＵＳ１３／７６３５３号、および２０１３年３月４日に出願された「ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＬＩＮＥＡＲ  ＡＮＤ  ＲＩＤＧＥ  ＲＥＧＲＥＳＳＩＯＮ」という名称の米国特許仮出願第６１／７７２４０４号明細書の利益および優先権を主張するものである。仮出願およびＰＣＴ出願は、すべての目的においてそれらの全体が参照により明確に本明細書に組み込まれる。
【０００２】
本原理は、プライバシー保護推薦システムおよび安全な複数パーティ計算に関し、特にプライバシー保護および盲目的（blind）なやり方で、行列因数分解に基づいてユーザに寄与する評点に対して推薦を提供することに関する。
【背景技術】
【０００３】
最近の１０年間の多大な研究および商業的活動は、推薦システムの広範囲に及ぶ使用に繋がっている。このようなシステムは、映画、テレビ番組、音楽、書籍、ホテル、レストランその他などの、多くの種類の項目に対する個人を対象とした推薦をユーザに提供する。図１は一般の推薦システム１００の構成要素である、ソースを表すいくつかのユーザ１１０およびユーザの入力１２０を処理し、推薦１４０を出力するリコメンダシステム（ＲｅｃＳｙｓ）１３０を示す。役に立つ推薦を受け取るためにユーザは、リコメンダがこのデータを適切に管理することを信頼して、彼等の好み（ユーザの入力）についてのかなりの個人情報を供給する。
【０００４】
それにもかかわらず、Ｂ．  Ｍｏｂａｓｈｅｒ，  Ｒ．  Ｂｕｒｋｅ，Ｒ．  Ｂｈａｕｍｉｋ，  およびＣ．  Ｗｉｌｌｉａｍｓ：”Ｔｏｗａｒｄ  ｔｒｕｓｔｗｏｒｔｈｙ  ｒｅｃｏｍｍｅｎｄｅｒ  ｓｙｓｔｅｍｓ：  Ａｎ  ａｎａｌｙｓｉｓ  ｏｆ  ａｔｔａｃｋ  ｍｏｄｅｌｓ  ａｎｄ  ａｌｇｏｒｉｔｈｍ  ｒｏｂｕｓｔｎｅｓｓ．”，ＡＣＭ  Ｔｒａｎｓ．  Ｉｎｔｅｒｎｅｔ  Ｔｅｃｈｎ．，  ７（４），  ２００７およびＥ．  Ａｉｍｅｕｒ，  Ｇ．  Ｂｒａｓｓａｒｄ，  Ｊ．Ｍ．  Ｆｅｒｎａｎｄｅｚ，  およびＦ．Ｓ．Ｍ．  Ｏｎａｎａ：”ＡＬＡＭＢＩＣ：  Ａ  ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｒｅｃｏｍｍｅｎｄｅｒ  ｓｙｓｔｅｍ  ｆｏｒ  ｅｌｅｃｔｒｏｎｉｃ  ｃｏｍｍｅｒｃｅ”，  Ｉｎｔ．  Ｊｏｕｒｎａｌ  Ｉｎｆ．  Ｓｅｃ，  ７（５），  ２００８などの以前の研究は、リコメンダがこのような情報を悪用する、またはユーザをプライバシーの脅威にさらし得る複数の方法を特定している。リコメンダは、しばしば利益のためにデータを転売するように動機付けられるが、またユーザによって意識的に明らかにされたもの以上の情報を抽出するようにも動機付けられる。例えば、映画評点または個人のテレビ視聴履歴などの通常は機密と見なされないユーザの好みの記録でさえ、ユーザの政治的友好関係、性別などを推論するために用いられ得る。推薦システムにおいてデータから推論され得る個人情報は、悪意のあるまたは悪意のない目的のために新しいデータマイニングおよび推論方法が開発されるのに従って、常に進化している。極端に言えば、ユーザの好みの記録は、ユーザを一意的に特定するために用いられることができ、Ａ．  Ｎａｒａｎｙａｎ、およびＶ．  Ｓｈｍａｔｉｋｏｖは、”Ｒｏｂｕｓｔ  ｄｅ−ａｎｏｎｙｍｉｚａｔｉｏｎ  ｏｆ  ｌａｒｇｅ  ｓｐａｒｓｅ  ｄａｔａｓｅｔｓ”，  ＩＥＥＥ  Ｓ＆Ｐ，  ２００８において、Ｎｅｔｆｌｉｘデータセットを非匿名化することによってこれを際立って実証している。したがって、リコメンダに悪意がない場合でも、このようなデータの意図的でない漏洩は、ユーザがリンク攻撃、すなわち１つのデータベースを補助的情報として用いて別のデータベースにおけるプライバシーを危うくする攻撃を受けやすくする。
【０００５】
将来の推論の脅威、偶発的な情報漏洩、または内部者の脅威（意図的な漏洩）を常に予見することはできないので、ユーザが彼等のプライベートなデータをクリアテキストにおいて明らかにしない推薦システムを組み立てることは興味深い。本出願と同じ日に出願された、「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」という名称の発明者らによる同時係属の出願は、行列因数分解に基づくプライバシー保護推薦システムについて述べている。これは、個々のユーザの評点または彼等が評点した項目を学習することなく、項目評点をプロファイルするリコメンダシステムに対してユーザが提出した評点上で、動作する。これは、ユーザが項目プロファイルを学習するリコメンダに対して同意していると見なしている。
【０００６】
本原理は、リコメンダシステムが、ユーザの評点およびシステムが評点した項目についてのいかなる情報も学習することなく、推薦を含む、項目プロファイルについてのいかなる情報またはユーザデータから抽出されたいかなる統計情報も学習することがない、より強力なプライバシー保護推薦システムを提案する。したがって、推薦システムは、それが提供する推薦に対しては完全に盲目的な状態で、評点を提供したユーザに推薦を提供する。
【発明の概要】
【０００７】
本原理は、プライバシー保護のやり方で、安全に、行列因数分解として知られている協調フィルタリング技法に基づいて推薦を提供するための方法を提案する。特に、この方法は、入力としてユーザが項目（例えば映画、書籍）に与えた評点を受け取り、ユーザが各項目にどのような評点を与え得るかを後に予測するために用いられ得る、各項目および各ユーザに対するプロファイルを生成する。本原理は、リコメンダシステムが行列因数分解に基づいて、ユーザの評点、どの項目をユーザが評点したか、項目プロファイル、またはユーザデータから抽出された統計データを学習することなく、このタスクを実行することを可能にする。特に、推薦システムは、それが提供する推薦に対して完全に盲目的な状態で、評点に寄与したユーザに、彼等がまだ評点していない項目を彼等がどのように評点するであろうかについての予測の形で推薦を提供する。
【０００８】
本原理の一態様によれば、行列因数分解によって推薦を安全に生成するための方法が提供される。上記方法は、レコードの組（２２０）を受け取るステップであって、各レコードは、それぞれのユーザから受け取られ、トークンの組および項目の組を備え、各レコードは、上記それぞれのユーザ以外のパーティに秘密に保たれる、ステップと、要求ユーザから少なくとも１つの特定の項目に対する要求を受け取るステップ（３３０）と、行列因数分解に基づいてガーブル回路を用いることによって、リコメンダ（ＲｅｃＳｙｓ）（２３０）において上記レコードの組を評価するステップ（３５５）であって、上記ガーブル回路の出力は、上記少なくとも１つの特定の項目に対するマスクされた項目プロファイルと、１つの上記要求ユーザに対するマスクされたユーザプロファイルと、を備える、ステップと、上記少なくとも１つの特定の項目について上記要求ユーザに対する推薦を生成するために、上記要求ユーザと、上記ＲｅｃＳｙｓと、暗号サービスプロバイダ（ＣＳＰ）との間で、上記マスクされた項目プロファイルおよび上記マスクされたユーザプロファイルを共同で評価するステップ（３６０〜３８５）であって、上記要求ユーザに対する各推薦およびユーザプロファイルは、上記要求ユーザ以外のパーティには秘密に保たれ、上記少なくとも１つの特定の項目に対する上記項目プロファイルは、すべてのパーティに秘密に保たれ、ユーザプロファイルおよび項目プロファイルは、それぞれマスクされた項目プロファイルおよびマスクされたユーザプロファイルのマスク解除されたバージョンである、ステップと、を含む。上記方法は、上記レコードの組に対して行列因数分解を実行するために上記ＣＳＰにおいて上記ガーブル回路を設計するステップ（３４０）であって、上記ガーブル回路の出力は、上記少なくとも１つの特定の項目に対するマスクされた項目プロファイルおよび上記１つの要求ユーザに対するマスクされたユーザプロファイルを含む、ステップと、上記ガーブル回路を上記ＲｅｃＳｙｓに伝送するステップ（３４５）と、をさらに含むことができる。上記方法における設計する上記ステップは、行列因数分解演算をブール回路として設計するステップ（３４０２）を含むことができる。行列因数分解回路を設計する上記ステップは、上記レコードの組の配列を構築するステップと、上記配列に対してソートし（４２０、４４０、４７０、４９０）、コピーし（４３０、４５０）、更新し（４７０、４８０）、比較し（４８０）、勾配寄与を計算する（４６０）動作を実行するステップと、を含むことができる。上記方法は、上記ＣＳＰによる上記ガーブル回路の上記設計のためのパラメータの組を受け取るステップをさらに含み、上記パラメータは、上記ＲｅｃＳｙｓによって送られる（３３５）。
【０００９】
本原理の一態様によれば、上記方法は、上記レコードの組を暗号化して、暗号化されたレコードを生成する、暗号化するステップ（３１５）をさらに含むことができ、上記暗号化するステップは、レコードの組を受け取る上記ステップの前に行われる。上記方法は、上記ＣＳＰにおいて公開暗号鍵を生成し、これらの鍵を上記それぞれのユーザに送るステップ（３１０）をさらに含むことができる。上記暗号化は、部分的準同型暗号化（３１０）とすることができ、上記方法は、上記ＲｅｃＳｙｓにおいて上記暗号化されたレコードをマスクして、マスクされたレコードを生成するステップ（３２０）と、上記ＣＳＰにおいて上記マスクされたレコードを復号して、復号済みのマスクされたレコードを生成するステップ（３２５）と、を含むことができる。設計する上記ステップ（３４０）は、上記復号済みのマスクされたレコードを、それらを処理する前に、上記ガーブル回路内部でマスク解除するステップを含む。上記方法は、上記ＣＳＰと上記ＲｅｃＳｙｓの間で（３５０２）、紛失通信を実行するステップ（３５０）をさらに含むことができ、上記ＲｅｃＳｙｓは、上記復号済みのマスクされたレコードの上記ガーブル化された値を受け取り、上記レコードは、上記ＲｅｃＳｙｓおよび上記ＣＳＰに秘密に保たれる。
【００１０】
本原理の一態様によれば、共同で評価する上記ステップは、上記マスクされたユーザプロファイルを第１のマスクでマスク解除して上記ユーザプロファイルを取得するステップ（３６０）と、上記ユーザプロファイルを暗号化して、暗号化されたユーザプロファイルを生成するステップ（３６０）と、上記ＲｅｃＳｙｓにおいて、上記少なくとも１つの特定の項目に対する上記暗号化されたユーザプロファイルと上記マスクされた項目プロファイルとの第１の積を計算するステップ（３７０）と、上記ＣＳＰにおいて、上記少なくとも１つの特定の項目に対する上記暗号化されたユーザプロファイルと少なくとも１つの第２のマスクとの少なくとも１つの第２の積を計算するステップ（３７５）と、上記ＲｅｃＳｙｓにおいて、上記第１の積から上記少なくとも１つの第２の積を減算して、上記少なくとも１つの特定の項目に対する少なくとも１つの暗号化された推薦を生成するステップ（３８０）と、上記少なくとも１つの特定の項目に対する上記少なくとも１つの暗号化された推薦を復号するステップ（３８５）と、をさらに含むことができる。上記第１のマスクは、上記要求ユーザによって選択されることができ（３１５）、上記少なくとも１つの第２のマスクは、上記ＣＳＰによって選択され得る（３４０）。暗号化および復号する上記ステップは、上記要求ユーザによって選択された加法的準同型暗号方式を用いることができる（３６０）。
【００１１】
本原理の一態様によれば、上記方法は、各レコードのトークンおよび項目の数を受け取るステップ（２２０、３０５）をさらに含むことができる。さらに、上記方法は、各レコードのトークンの数が最大値を表す値より小さいときに、上記値に等しいトークンの数を有するレコードを生成するために、ヌルエントリで各レコードをパッディングするステップ（３０５２）をさらに含むことができる。上記レコードの組のソースは、データベースとすることができる。
【００１２】
本原理の一態様によれば、行列因数分解によって推薦を安全に生成するためのシステムが提供され、上記システムは、レコードのそれぞれの組を提供するユーザの組と、安全な行列因数分解回路を提供する暗号サービスプロバイダ（ＣＳＰ）と、各レコードがそのそれぞれのユーザ以外のパーティに秘密に保たれるように上記レコードを評価するＲｅｃＳｙｓと、を備え、各ユーザ、上記ＣＳＰ、および上記ＲｅｃＳｙｓはそれぞれ、少なくとも１つの入力／出力（６０４）において受け取るためのプロセッサー（６０２）と、そのプロセッサーと信号通信する少なくとも１つのメモリ（６０６、６０８）とを含み、上記ＲｅｃＳｙｓのプロセッサーは、レコードの組を受け取ることであって、各レコードは、トークンの組および項目の組を備え、各レコードは、上記それぞれのユーザ以外のパーティに秘密に保たれる、レコードの組を受け取ることと、要求ユーザから少なくとも１つの特定の項目に対する要求を受け取ることと、行列因数分解に基づいてガーブル回路によってレコードの組を評価することであって、上記ガーブル回路の出力は、上記少なくとも１つの特定の項目に対するマスクされた項目プロファイルおよび上記１つの要求ユーザに対するマスクされたユーザプロファイルを備える、評価することと、を実行するように構成され、上記要求ユーザ、ＲｅｃＳｙｓ、およびＣＳＰのプロセッサーは、上記少なくとも１つの特定の項目について上記要求ユーザに推薦を生成するために、上記マスクされた項目プロファイルおよび上記マスクされたユーザプロファイルを共同で評価するように構成され（３６０〜３８５）、上記要求ユーザに対する各推薦およびユーザプロファイルは、上記要求ユーザ以外のパーティには秘密に保たれ、上記少なくとも１つの特定の項目に対する上記項目プロファイルはすべてのパーティに秘密に保たれ、ユーザプロファイルおよび項目プロファイルは、それぞれマスクされた項目プロファイルおよびマスクされたユーザプロファイルのマスク解除されたバージョンである。上記システム内の上記ＣＳＰのプロセッサーは、上記レコードの組に対して行列因数分解を実行するためにガーブル回路を設計することであって、上記ガーブル回路の出力は、上記少なくとも１つの特定の項目に対するマスクされた項目プロファイルと、上記１つの要求ユーザに対するマスクされたユーザプロファイルと、を含む、設計することと、上記ガーブル回路を上記ＲｅｃＳｙｓに伝送することと、を実行するように構成され得る。上記システム内の上記ＣＳＰのプロセッサーは、行列因数分解演算をブール回路として設計するように構成されることによって上記ガーブル回路を設計するように構成され得る。上記システム内の上記ＣＳＰのプロセッサーは、上記レコードの組の配列を構築するように構成されることによって上記行列因数分解回路を設計し、上記配列に対してソートし、コピーし、更新し、比較し、および勾配寄与を計算する動作を実行するように構成され得る。上記システム内の上記ＣＳＰのプロセッサーは、上記ガーブル回路の上記設計のためのパラメータの組を受け取るようにさらに構成されることができ、上記パラメータは上記ＲｅｃＳｙｓによって送られる。
【００１３】
本原理の一態様によれば、各ユーザのプロセッサーは、上記レコードを提供する前に、上記それぞれのレコードを暗号化して、暗号化されたレコードを生成するように構成され得る。上記ＣＳＰのプロセッサーは、上記ＣＳＰにおいて公開暗号鍵を生成し、それらの鍵を上記ユーザの組に送るようにさらに構成され得る。上記暗号化は、部分的準同型暗号化とすることができ、上記ＲｅｃＳｙｓのプロセッサーは、上記暗号化されたレコードをマスクして、マスクされたレコードを生成するようにさらに構成され、上記ＣＳＰのプロセッサーは、上記マスクされたレコードを復号して、復号済みのマスクされたレコードを生成するようにさらに構成される。上記システム内の上記ＣＳＰのプロセッサーは、上記復号済みのマスクされたレコードを、それらを処理する前に、上記ガーブル回路内部でマスク解除するようにさらに構成されることによって、上記ガーブル回路を設計するように構成され得る。上記システム内の上記ＲｅｃＳｙｓのプロセッサーおよび上記ＣＳＰのプロセッサーは、紛失通信を実行するようにさらに構成されることができ、上記ＲｅｃＳｙｓは、上記復号済みのマスクされたレコードの上記ガーブル化された値を受け取り、上記レコードは、上記ＲｅｃＳｙｓおよび上記ＣＳＰに秘密に保たれる。
【００１４】
本原理の一態様によれば、上記要求ユーザのプロセッサーは、上記マスクされたユーザプロファイルを第１のマスクでマスク解除して上記ユーザプロファイルを取得し、上記ユーザプロファイルを暗号化して、暗号化されたユーザプロファイルを生成し、上記少なくとも１つの特定の項目に対する少なくとも１つの暗号化された推薦を復号するようにさらに構成されることができ、上記ＲｅｃＳｙｓのプロセッサーは、上記少なくとも１つの特定の項目に対する上記暗号化されたユーザプロファイルと上記マスクされた項目プロファイルとの第１の積を計算し、上記第１の積から少なくとも１つの第２の積を減算して、上記少なくとも１つの特定の項目に対する少なくとも１つの暗号化された推薦を生成するようにさらに構成され、上記ＣＳＰのプロセッサーは、上記少なくとも１つの特定の項目に対する上記暗号化されたユーザプロファイルと少なくとも１つの第２のマスクとの少なくとも１つの第２の積を計算するようにさらに構成される。上記第１のマスクは上記要求ユーザによって選択されることができ、上記少なくとも１つの第２のマスクは上記ＣＳＰによって選択され得る。上記要求ユーザのプロセッサーは、上記要求ユーザによって選択された加法的準同型暗号方式を用いるように構成され得る。
【００１５】
本原理の一態様によれば、上記システム内の上記ＲｅｃＳｙｓのプロセッサーは、各レコードのトークンの数を受け取るようにさらに構成されることができ、上記トークンの数はソースによって送られたものである。各ユーザのプロセッサーは、各レコードのトークンの数が最大値を表す値より小さいときに、上記値に等しいトークンの数を有するレコードを生成するために、ヌルエントリで上記各レコードをパッディングするように構成され得る。上記レコードの組のソースは、データベースとすることができる。
【００１６】
本原理のさらなる特徴および利点については、添付の図を参照して以下の例示的実施形態の詳細な説明から明らかにされるであろう。
【図面の簡単な説明】
【００１７】
本原理については、以下に簡潔に述べられる例示の図によってよりよく理解され得る。
【図１】従来技術の推薦システムの構成要素を示す図である。
【図２】本原理による推薦システムの構成要素を示す図である。
【図３Ａ】本原理によるプライバシー保護推薦方法のフローチャートである。
【図３Ｂ】本原理によるプライバシー保護推薦方法のフローチャートである。
【図３Ｃ】本原理によるプライバシー保護推薦方法のフローチャートである。
【図３Ｄ】本原理によるプライバシー保護推薦方法のフローチャートである。
【図４Ａ】本原理による例示の行列因数分解アルゴリズムを示す図である。
【図４Ｂ】本原理による例示の行列因数分解アルゴリズムを示す図である。
【図４Ｃ】本原理による例示の行列因数分解アルゴリズムを示す図である。
【図５】本原理による行列因数分解アルゴリズムによって構築されたデータ構造Ｓを示す図である。
【図６】本原理を実現するために利用されるコンピューティング環境のブロック図である。
【発明を実施するための形態】
【００１８】
本原理によれば、安全にプライバシーを保護するおよび盲目的なやり方で、行列因数分解として知られている協調フィルタリング技法に基づいて、推薦を実行するための方法が提供される。
【００１９】
本原理の方法は、各レコードがトークンおよび項目の組を備える、レコードのコーパスにおける項目について推薦を実行するサービスとして働くことができる。レコードの組は２つ以上のレコードを含み、トークンの組は少なくとも１つのトークンを含む。当業者は、上記の例において、レコードがユーザを表すことができ、トークンがレコードにおける対応する項目に対するユーザの評点となり得ることを認識するであろう。トークンはまた、項目に関連する順位、重みまたは測度を表すことができ、項目は個人、タスクまたは仕事を表すことができる。例えば順位、重みまたは測度は個人の健康に関連付けられることができ、研究者は人口の健康測度を相関させることを試みる。またはそれらは、個人の生産性に関連付けられることができ、会社は、前の履歴に基づいて、一定の仕事に対するスケジュールを予測することを試みる。しかしながら、関係する個人のプライバシーを保証するために、サービスはそれを、各レコードの内容、それが提供する項目プロファイル、またはユーザデータ（レコード）から抽出された統計データを学習することなく、盲目的なやり方で行うことを望む。特に、サービスは、（ａ）各トークン／項目がどのレコードに現れたか、まして（ｂ）各レコードにどのようなトークン／項目が現れるか、（ｃ）トークンの値、および（ｄ）項目プロファイルまたはユーザデータから抽出された統計データを、学習するべきではない。以下では、「プライバシー保護」、「プライベート（private）」、および「安全な」などの用語および語句は、ユーザによってプライベートと見なされる情報（レコード）はユーザのみによって知られることを表すように同義的に用いられ、「盲目的（blind）」という語句は、ユーザ以外のパーティは推薦に対しても盲目的であることを表すように用いられる。
【００２０】
プライバシー保護の方法で行列因数分解を実行することに関連するいくつかの課題が存在する。第一に、プライバシーの懸念に対処するために、行列因数分解は、リコメンダがいかなるときも、ユーザの評点さらには彼等がどの項目を評点したかを学習することなく実行されるべきである。後者の要件は重要であり、以前の研究は、ユーザがどの映画を評点したかを知ることでさえ、例えばその性別を推論するために用いられ得ることを示している。第二に、このようなプライバシー保護アルゴリズムは、効率的であり、ユーザによって提出された評点の数に対して優雅に（例えば線形的に）スケール化するべきである。プライバシー要件は、行列因数分解アルゴリズムがデータ紛失（data-obvious）であるべきで、その実行はユーザ入力に依存するべきではないことを意味する。さらに、行列因数分解によって行われる演算は非線形であり、したがってこれらの両方の制約のもとでどのように行列因数分解を効率的に実装するかは、先験的には明らかではない。最後に、実際的な現実世界のシナリオにおいて、ユーザは限られた通信および計算リソースを有し、彼等が彼等のデータの供給した後にオンラインのままでいることは期待されるべきではない。代わりに、推薦サービスに対してオンラインおよびオフラインの間を交互するユーザの存在下で動作することができる、「送って忘れる」タイプのソリューションを有することが望ましい。
【００２１】
行列因数分解の概要として、標準の「協調フィルタリング」設定では、ｎ人のユーザがｍ個の可能な項目のサブセット（例えば映画）を評点する。ユーザの組［ｎ］：＝｛１，．．．，ｎ｝、および項目の組［ｍ］：＝｛１，．．．，ｍ｝に対して、評点がそれらに対して生成されたユーザ／項目対を、
【００２２】
【数１】
2016517069.tif 000003
【００２３】
で表し、評点の総数を
【００２４】
【数２】
2016517069.tif 000004
【００２５】
で表す。最後に、
【００２６】
【数３】
2016517069.tif 000005
【００２７】
に対して、項目ｊに対してユーザｉによって生成された評点を、
【００２８】
【数４】
2016517069.tif 000006
【００２９】
で表す。実際の設定では、ｎおよびｍは共に大きな数となり、通常は１０4から１０6の範囲となる。さらに、提供される評点はまばらであり、すなわちＭ＝Ｏ（ｎ＋ｍ）であり、これは可能性がある評点の総数ｎ×ｍよりずっと少ない。これは、各ユーザが有限な数の項目のみを評点し得る（「カタログ」サイズｍに依存しない）ので、通常のユーザの挙動と一致する。
【００３０】
【数５】
2016517069.tif 000007
【００３１】
における評点を所与としてリコメンダシステムは、
【００３２】
【数６】
2016517069.tif 000008
【００３３】
におけるユーザ／項目対に対する評点を予測することを望む。行列因数分解は、このタスクを、双一次式モデルを既存の評点にフィッティングすることによって実行する。特に、ある小さな次元
【００３４】
【数７】
2016517069.tif 000009
【００３５】
に対して、ベクトル
【００３６】
【数８】
2016517069.tif 000010
【００３７】
が存在すると仮定し、それにより、
ｒi,j＝＜ｕi，ｖj＞＋εi,j  （１）
となり、εi,jはｉ．ｉ．ｄ（独立で同一に分布する）ガウス分布ランダム変数である。ベクトルｕiおよびｖjは、それぞれユーザおよび項目プロファイルと呼ばれ、＜ｕi，ｖj＞はベクトルの内積である。用いられる表記法は、そのｉ番目の行がユーザｉのプロファイルを備えるｎ×ｄマトリックスに対して、
【００３８】
【数９】
2016517069.tif 000011
【００３９】
であり、そのｊ番目の行が項目ｊのプロファイルを備えるおよびｍ×ｄマトリックスに対して、
【００４０】
【数１０】
2016517069.tif 000012
【００４１】
である。
【００４２】
評点
【００４３】
【数１１】
2016517069.tif 000013
【００４４】
を所与として、リコメンダは通常、ある正のλ、μ＞０に対して、以下の正規化最小二乗最小化を行ってプロファイルＵおよびＶを計算する：
【００４５】
【数１２】
2016517069.tif 000014
【００４６】
当業者は、プロファイルＵおよびＶに対してガウス事前分布を仮定し、（２）での最小化はＵおよびＶの最尤推定に対応することを認識するであろう。ユーザおよび項目プロファイルを有して、リコメンダはその後に、ユーザｉおよび項目ｊに対して、
【００４７】
【数１３】
2016517069.tif 000015
【００４８】
となるように評点
【００４９】
【数１４】
2016517069.tif 000016
【００５０】
を予測できることに留意されたい。
【００５１】
（２）での正規化平均二乗誤差は凸関数ではなく、この最小化を実行するためのいくつかの方法が文献に提案されている。本原理は、実際面で用いられる人気のある方法である勾配降下に焦点を当て、これには以下のように述べられる。Ｆ（Ｕ，Ｖ）によって（２）での正規化平均二乗誤差を表して、勾配降下は以下の適合規則を通してプロファイルＵおよびＶを反復して適合することによって動作する。
【００５２】
【数１５】
2016517069.tif 000017
【００５３】
γ＞０は小さな利得係数であり、
【００５４】
【数１６】
2016517069.tif 000018
【００５５】
Ｕ（０）およびＶ（０）は一様にランダムなノルム１行からなる（すなわちプロファイルは、ノルム１ボールからｕ．ａ．ｒ．（一様にランダム）に選択される）。
【００５６】
本原理の別の態様は、ソーティングネットワークおよびヤオのガーブル回路に基づく安全な複数パーティ計算（ＭＰＣ）アルゴリズムを提案する。安全な複数パーティ計算は、１９８０年代にＡ．  Ｃｈｉ−Ｃｈｉｈ  Ｙａｏによって提案された。ヤオのプロトコル（ガーブル回路としても知られる）は、安全な複数パーティ計算のための一般的な方法である。”Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｒｉｄｇｅ  ｒｅｇｒｅｓｓｉｏｎ  ｏｎ  ｈｕｎｄｒｅｄｓ  ｏｆ  ｍｉｌｌｉｏｎｓ  ｏｆ  ｒｅｃｏｒｄｓ”，ＩＥＥＥ  Ｓ＆Ｐ，  ２０１３，ｂｙ  Ｖ．  Ｎｉｋｏｌａｅｎｋｏ，  Ｕ．  Ｗｅｉｎｓｂｅｒｇ，  Ｓ．  Ｉｏａｎｎｉｄｉｓ，  Ｍ．  Ｊｏｙｅ，  Ｄ．  Ｂｏｎｅｈ，  およびＮ．  Ｔａｆｔから改造されたその変形では、プロトコルは、ｎ個の入力保有者の組と、ａｉはユーザｉのプライベート入力を表し１≦ｉ≦ｎとして、ｆ（ａ1，．．，ａn）を評価することを望む評価器と、サードパーティである暗号サービスプロバイダ（ＣＳＰ）との間で実行される。プロトコルの終わりでは評価器は、ｆ（ａ1，．．，ａn）の値を学習するが、いずれのパーティもこの出力値から明らかにされるもの以上を学習することはない。プロトコルは、関数ｆがブール回路、例えばＯＲ、ＡＮＤ、ＮＯＴ、およびＸＯＲのグラフとして表現されることができること、ならびに評価器およびＣＳＰは共謀しないことを必要とする。
【００５７】
最近では、ヤオのガーブル回路を実現する多くのフレームワークがある。汎用ＭＰＣに対する別の方法は秘密共有方式に基づき、もう１つは完全準同型暗号（ＦＨＥ）に基づく。秘密共有方式は、線形システムを解くこと、線形回帰、およびオークションなどの多様な線形代数演算のために提案されている。秘密共有は、計算の作業負荷を等しく共有し、複数回にわたって通信する、少なくとも３つの共謀しないオンライン権限者を必要とし、計算はそれらのうちの２つが共謀しない限り安全である。ガーブル回路は２つだけの共謀しない権限者およびはるかに少ない通信を前提とし、これは評価器がクラウドサービスであり、暗号サービスプロバイダ（ＣＳＰ）が信頼されたハードウェア構成要素内に実装されているシナリオに、より適している。
【００５８】
用いられる暗号プリミティブに関わらず、安全な複数パーティ計算のための効率的なアルゴリズムの組み立てにおける主な課題は、データ紛失的なやり方で、すなわち実行パスが入力に依存しないようにアルゴリズムを実装することにある。一般に、制限された時間Ｔ内で実行可能ないずれのＲＡＭプログラムも、数学的計算のための理想化モデルとして役立つようにＡｌａｎ  Ｔｕｒｉｎｇによって発明された理論的計算機械であるＯ（Ｔ＾３）チューリングマシン（ＴＭ）に変換されることができ、Ｏ（Ｔ＾３）はＴ3に比例する複雑度を意味する。さらに、いずれのＴ時間に制限されたＴＭも、データ紛失であるサイズＯ（ＴｌｏｇＴ）の回路に変換され得る。これは、いずれのＴ時間に制限された実行可能なＲＡＭプログラムも、Ｏ（Ｔ＾３ｌｏｇＴ）の複雑度を有するデータ紛失回路に変換され得ることを示唆する。このような複雑度は、高過ぎてほとんどの用途において過大である。効率的なデータ紛失の実装が知られていないアルゴリズムの調査は、”Ｓｅｃｕｒｅ  ｍｕｌｔｉ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｐｒｏｂｌｅｍｓ  ａｎｄ  ｔｈｅｉｒ  ａｐｐｌｉｃａｔｉｏｎｓ：  Ａ  ｒｅｖｉｅｗ  ａｎｄ  ｏｐｅｎ  ｐｒｏｂｌｅｍｓ”，  ｉｎ  Ｎｅｗ  Ｓｅｃｕｒｉｔｙ  Ｐａｒａｄｉｇｍｓ，  Ｗｏｒｋｓｈｏｐ，  ２００１，ｂｙ  Ｗ．  Ｄｕ，  Ｍ．Ｊ．  Ａｔａｌｌａｈに見出されることができ、行列因数分解問題はデータマイニング集計問題の範疇に広く包含される。
【００５９】
ソーティングネットワークは、もともとソーティング並列化および効率的なハードウェア実装を可能にするために開発された。これらのネットワークは、入力シーケンス（ａ1，ａ2，．．．，ａn）を、単調増加シーケンス（ａ’1，ａ’2，．．．，ａ’n）にソートする回路である。それらは、それらの主なビルディングブロックである比較交換回路を共同で配線することによって構築される。いくつかの研究は、暗号の目的のためにソーティングネットワークのデータ紛失性を活用する。しかしながら、暗号化は、プライバシーを保証するのに常には十分ではない。敵対者が、暗号化されたストレージへのあなたのアクセスパターンを認識できる場合は、彼等はさらにあなたのアプリケーションが何をしているかについての機密情報を学習することができる。紛失ＲＡＭは、メモリがアクセスされるのに従ってそれを連続してシャッフルすることによってこの問題を解決し、それによって何のデータがアクセスされているか、さらにはそれが以前にいつアクセスされたかを完全に隠蔽する。紛失ＲＡＭではソートは、データ紛失ランダム並べ換えを発生させる手段として用いられる。より最近では、凸閉包、全最近傍問題、および重み付き積集合のデータ紛失計算を実行するために用いられている。
【００６０】
本原理は、重み付き積集合に近いがガーブル回路を組み込んだ、安全な複数パーティソーティングに基づく方法を提案する。図２は、本原理によるプライバシー保護推薦システムにおける動作者を示す。それらは以下の通りである。
【００６１】
Ｉ．盲目的なプライバシー保護行列因数分解演算を実行するエンティティである、リコメンダシステム（ＲｅｃＳｙｓ）２３０。特に、ＲｅｃＳｙｓは、彼等がどの映画を評点したか、彼等がどんな評点を与えたか、またはユーザによって取得される推薦を含むユーザデータから抽出された統計情報（平均、項目プロファイルなど）を含む、ユーザについての役立つものを学習することなく、ユーザ評点に対する行列因数分解から抽出されるように、項目プロファイルＶ２４０を盲目的に計算する。
【００６２】
ＩＩ．暗号サービスプロバイダ（ＣＳＰ）２５０。これは、彼等がどの映画を評点したか、彼等がどんな評点を与えたか、または推薦を含むユーザデータから抽出された統計情報（平均、項目プロファイルなど）を含む、ユーザについての役立つものを学習することなく、安全な計算を可能にする。
【００６３】
ＩＩＩ．１または複数のユーザ２１０からなり、それぞれが項目の組２２０に対する評点の組を有するソース。各ユーザｉ∈［ｎ］は行列因数分解による、彼等の評点
【００６４】
【数１７】
2016517069.tif 000019
【００６５】
に基づく項目のプロファイリングに同意するが、リコメンダに対して彼等の評点、彼等がその項目を評点したか、およびユーザデータから抽出された統計情報（手段、項目プロファイルなど）を含むいずれについても明らかにしないことを望む。等価的に、ソースは、１または複数のユーザのデータを含むデータベースを表すことができる。
【００６６】
本原理によれば、ＲｅｃＳｙｓが行列因数分解を実行し、推薦を提供することを可能するプロトコルが提案され、ＲｅｃＳｙｓまたはＣＳＰのいずれも、それに対して暗号化された値が図２におけるＲｅｃＳｙｓの出力である、ユーザに与えられた推薦
【００６７】
【数１８】
2016517069.tif 000020
【００６８】
を含む、ユーザについての役に立つものを学習することはない。特に、いずれもユーザの評点、さらにはユーザがどの項目を実際に評点したかを学習するべきではなく、いずれも項目プロファイルＶ、ユーザプロファイルＵ、推薦、またはユーザデータから抽出された統計情報を学習するべきではない。当業者は、リコメンダがユーザおよび項目プロファイルの両方を学習することを可能にするプロトコルは余りに多くを明らかにし、このような設計では、リコメンダは、（３）における内積からユーザの評点を自明に推論できることを明らかに認識するであろう。したがって、本原理は、リコメンダおよびＣＳＰが、ユーザプロファイル、項目プロファイル、またはユーザデータから抽出された統計データを学習することがない、プライバシー保護プロトコルを提案する。要約すると、それらは完全に盲目的なやり方で動作を行い、ユーザについての役立つ情報、またはユーザデータから抽出されたものを学習することはない。
【００６９】
項目プロファイルは、項目をユーザ／レコードの組の評点に応じて定義するメトリックと見なされ得る。同様に、ユーザプロファイルは、ユーザをユーザ／レコードの組の評点に応じて定義するメトリックと見なされ得る。この意味で、項目プロファイルは、項目の支持／不支持の測度、すなわち項目の特徴または特性の反映である。そして、ユーザプロファイルは、ユーザの好き／嫌いの測度、すなわちユーザの個性の反映である。大きなユーザ／レコードの組に基づいて計算された場合は、項目またはユーザプロファイルは、それぞれ項目またはユーザの独立の測度と見なされ得る。当業者は、項目プロファイルのみを学習することでの有用性が存在することが分かるであろう。第一に、行列因数分解を通して、
【００７０】
【数１９】
2016517069.tif 000021
【００７１】
における項目を埋め込むことでリコメンダが類似度を推論（および符号化）することを可能にし、そのプロファイルが小さなユークリッド距離を有する項目は、ユーザによって同じように評点される項目となる。したがって、リコメンダにとって項目プロファイルを学習するタスクは、実際の推薦のタスクよりも関心がある。特に、ソースがデータベースである場合に当てはまり得るように、ユーザは推薦を受け取ることを必要とせずまたは望まない場合がある。第二に、項目プロファイルを取得すると、リコメンダは、些細なことでユーザが追加のデータを明らかにすることなく、それらを用いて関連のある推薦を提供することができる。リコメンダはＶをユーザに送る（またはそれを公開する）ことができ、ユーザは項目ごとのその評点を知り、所与のＶに対して、ｕiについて（２）を解くことによって、その（個人の）プロファイルｕiを推論することができ、各ユーザはその評点にわたってリッジ回帰を実行することによってそのプロファイルを取得することができる。ｕiおよびＶを有して、ユーザは式（４）を通して他の項目に対するすべてのその評点をローカルに予測することができる。これは本出願と同じ日に発明者らによって出願された、「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ  ＡＮＤ  ＲＩＤＧＥ  ＲＥＧＲＥＳＳＩＯＮ」という名称の同時係属の出願の主題である。
【００７２】
上述のシナリオの両方とも、リコメンダおよびユーザのいずれもＶの公開に反対しないことを前提とする。簡単にするために、およびリコメンダに対するこのようなプロトコルの有用性のために、本出願と同じ日に出願された「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」という名称の、発明者らによる同時係属の出願は、リコメンダが項目プロファイルを学習することを可能にする。本原理はこの設計を、ユーザが彼等の予測された評点を学習するように拡張し、一方、リコメンダは演算を盲目的なやり方で行い、ユーザについての役立つ情報を、Ｖさえをも学習することはない。
【００７３】
本原理によれば安全保証は、正直であるが好奇心のある脅威モデルのもとで成り立つようになることが仮定される。言い換えれば、ＲｅｃＳｙｓおよびＣＳＰは、規定されたようにプロトコルに従うが、これらの関心のあるパーティは、プロトコルの写しをオフラインでも分析して何らかの追加情報を推論することを選び得る。さらに、リコメンダおよびＣＳＰは共謀しないことが仮定される。
【００７４】
本原理の好ましい実施形態は、図３におけるフローチャート３００の要件を満たすプロトコルを備え、以下のステップによって記述される。
【００７５】
Ｐ１．ソースは、どれだけ多くのトークン（評点）および項目の対が、それぞれの参加レコードに対して提出されるかを報告する３０５。組またはレコードは２つ以上のレコードを含み、レコード当たりのトークンの組は少なくとも１つのトークンを含む。ソースがユーザの組である場合は、各ユーザは、ＲｅｃＳｙｓに、それらのそれぞれのトークンおよび項目の数を個別に報告する。
【００７６】
Ｐ２．ＣＳＰは、部分的準同型方式ξのための公開暗号鍵を生成し、それをすべてのユーザ（ソース）に送る３１０。準同型暗号化は、特定のタイプの計算に、暗号化テキスト上で実行されること、及び復号されたものが平文に対して行われた演算の結果と一致する暗号化された結果を取得することを可能にする、暗号化の形であることを当業者は理解するであろう。例えば、彼等のいずれも個々の数の値を見出すことはできないまま、一個人が２つの暗号化された数を追加することができ、次いで別の個人がその結果を復号することができる。部分的準同型暗号化は、平文に対する１つの演算（加算または乗算）に対して準同型である。部分的準同型暗号化は、スカラに対する加算および乗算に対して準同型である。
【００７７】
Ｐ３．各ユーザｉはマスクθiを選択し、それをＣＳＰの公開鍵のもとで暗号化し、暗号化されたマスクｔiを生成する。マスクがデータ難読化の形であり、乱数発生器の追加または乱数によるシャフリングのように簡単なものとし得ることを当業者は理解するであろう。このマスクは、ユーザｉのプロファイルｕiを隠蔽するために用いられることになる。さらに、各ユーザは、その鍵を用いてそのデータを暗号化する。特に、ｊを項目ｉｄとし、ｒi,jをユーザｉがｊに与えた評点として、ユーザは、あらゆる対（ｊ，ｒi,j）に対してこの対を公開暗号鍵を用いて暗号化する。ユーザは、暗号化されたマスクｔiおよび暗号化されたデータをＲｅｃＳｙｓに送る３１５。
【００７８】
Ｐ４．ＲｅｃＳｙｓは、マスクηを暗号化されたデータに加算し、暗号化されたマスクｔiおよび暗号化されマスクされたデータをＣＳＰに転送する３２０。
【００７９】
Ｐ５．ＣＳＰは、暗号化されたマスクｔiを復号し、復号されたマスクθiを取り出し、また暗号化されたマスクされたデータを復号する３２５。
【００８０】
Ｐ６．ＲｅｃＳｙｓは、少なくとも１つの要求ユーザから、すべての項目のコーパスにおける少なくとも１つの特定の項目に対する推薦要求を受け取る（３３０）。各要求ユーザは、レコードを提供したユーザの１つである。
【００８１】
Ｐ７．ＲｅｃＳｙｓは、ユーザおよび項目プロファイルの次元（すなわちパラメータｄ）３３５２、評点の総数（すなわちパラメータＭ）３３５４、ユーザおよび項目の総数３３５６並びにガーブル回路において実数の整数および小数部を表すのに用いられるビット数３３５８を含む、ガーブル回路を組み立てるのに必要な完全な仕様をＣＳＰに送る３３５。レコード内に存在するすべての項目ではないにしろ、項目の別の組がパラメータに含まれることになる。
【００８２】
Ｐ８．ＣＳＰは、項目の別々の組に関して、レコードに対して行列因数分解を実行するガーブル回路として当業者に知られているものを用意する。ガーブル化されるために、回路は、最初にブール回路として書かれる３４０２。回路への入力は、ＲｅｃＳｙｓがユーザデータをマスクするために用いたマスクを備える。回路の内部では、マスクは、データをマスク解除し、次いで行列因数分解を実行するために用いられる。回路の出力は、項目プロファイルＶおよびユーザプロファイルＵである。ＣＳＰはまた、項目ｊごとに１つ、それ自体のランダムマスクρjを選択する。これらは、各項目ｊのプロファイルを隠蔽するために用いられる。項目およびユーザプロファイルをクリアテキストで出力するのではなく、ＣＳＰによって構築された回路は、（ａ）マスクρjでマスクされた項目プロファイルｖjおよび（ｂ）マスクθiでマスクされたユーザプロファイルｕiを出力する。個々のレコードおよびレコードから抽出された情報の内容についての知識が得られることはない。
【００８３】
Ｐ９．ＣＳＰは、行列因数分解のためのガーブル回路をＲｅｃＳｙｓに送る３４５。具体的には、ＣＳＰは、ゲートをガーブル化されたテーブルに処理し、回路構造によって規定された順番にそれらをＲｅｃＳｙｓに送信する。
【００８４】
Ｐ１０．ＲｅｃＳｙｓとＣＳＰの間３５０２の紛失通信を通して３５０、ＲｅｃＳｙｓは、それ自体またはＣＳＰが実際の値を学習することなく、復号されマスクされたレコードのガーブル化された値を学習する。紛失通信は、何が（もしあれば）伝送されたかについては紛失的なままである受信側に、送出側が潜在的に多くの情報の１つを伝送する、伝送のタイプであることを当業者は理解するであろう。
【００８５】
Ｐ１１．ＲｅｃＳｙｓは回路を評価し、マスクされたｕiを各ユーザｉに送り３５５、それらはそれをマスク解除する。
【００８６】
Ｐ１２．ユーザが推薦を入手することを望む場合は、ユーザはそのプロファイルｕｉをマスク解除し、次いで加法的準同型暗号方式
【００８７】
【数２０】
2016517069.tif 000022
【００８８】
を用いておよびそれ自体の公開鍵を用いて暗号化する３６０。
【００８９】
Ｐ１３．ユーザは暗号化されたｕiをＲｅｃＳｙｓに送り、ＲｅｃＳｙｓはそれをＣＳＰに転送する３６５。
【００９０】
Ｐ１４．ＲｅｃＳｙｓは、あらゆる項目ｊに対して、＜ｕi，（ｖj＋ρj）＞、ｊ∈［ｍ］の暗号化された値を計算し３７０、これは暗号方式が加法的準同型であるので行うことができる。
【００９１】
Ｐ１５．ＣＳＰは、あらゆる項目ｊに対して、＜ｕi，ρj＞、ｊ∈［ｍ］の暗号化された値を計算し、これは暗号方式が加法的準同型であるので行うことができ、この値をＲｅｃＳｙｓに送る３７５。
【００９２】
Ｐ１６．ＲｅｃＳｙｓは、＜ｕi，ρj＞、ｊ∈［ｍ］の暗号化された値を、対応する＜ｕi，（ｖj＋ρj）＞、ｊ∈［ｍ］の暗号化された値から減算し、＜ｕi，ｖj＞，ｊ∈［ｍ］の暗号化された値を取得し、これらをユーザに送る３８０。
【００９３】
Ｐ１７．ユーザは、これらの＜ｕi，ｖj＞，ｊ∈［ｍ］の暗号化された値を、その秘密復号鍵を用いて復号し、それにより式（３）に示されるように、あらゆる項目に対するその予測された評点を入手する３８５。
【００９４】
上記の構築は、そのユーザプロファイルが行列因数分解を通して計算されたユーザのみに対して正しく動作する。まだそのデータを提出していない新しいユーザは、この方法で推薦を入手することはできない。「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ  ＡＮＤ  ＲＩＤＧＥ  ＲＥＧＲＥＳＳＩＯＮ」という名称の同時係属の出願は、この特定の場合に対処する。
【００９５】
技術的には、このプロトコルは、各ユーザによって提供されるトークンの数を漏洩する。これは、簡単なプロトコル変更を通して、例えば提出されたレコードを、予め設定された最大数に達するまで、適切に「ヌル」エントリで「パッディング（padding）」することによって修正される３１２。話を簡単にするために、プロトコルは、この「パッディング」動作なしで述べられた。
【００９６】
ガーブル回路は一度使用され得るだけなので、同じ評点に対する将来の計算は、ユーザがプロキシ紛失通信を通して彼等のデータを再提出することが必要になる。プロキシ紛失通信は、３つ以上のパーティが関係する紛失通信である。この理由により、本原理のプロトコルは、公開鍵暗号化をガーブル回路と組み合わせたハイブリッド方法を採用した。
【００９７】
本原理では、公開鍵暗号化は、以下のように用いられる。各ユーザｉは、強秘匿暗号化アルゴリズム
【００９８】
【数２１】
2016517069.tif 000023
【００９９】
を用いて、ＣＳＰによって提供された公開鍵ｐｋcspのもとで、そのそれぞれのマスクθiを暗号化し、暗号化されたマスク
【０１００】
【数２２】
2016517069.tif 000024
【０１０１】
を提出する。さらに、各ユーザｉは、暗号化アルゴリズム
【０１０２】
【数２３】
2016517069.tif 000025
【０１０３】
を用いて、公開鍵ｐｋcspのもとで、そのそれぞれの入力（ｊ，ｒi,j）を暗号化し、評点された各項目ｊに対してユーザは、
【０１０４】
【数２４】
2016517069.tif 000026
【０１０５】
によって対（ｉ，ｃ）をＲｅｃＳｙｓに提出し、合計でＭ個の評点が提出される。その評点を提出したユーザはオフラインになることができる。
【０１０６】
ＣＳＰ公開鍵暗号化アルゴリズムは、部分的準同型であり、対応する復号鍵の知識なしに、暗号化されたメッセージに定数が適用され得る。明らかに、定数を加算するためにＰａｉｌｌｉｅｒまたはＲｅｇｅｖなどの加法的準同型方式も用いられ得るが、部分的準同型なだけであるハッシュＥｌＧａｍａｌで十分であり、この場合にはより効率的に実装され得る。
【０１０７】
暗号が部分的準同型であることを想起すると、ユーザからＭ個の評点を受け取るとすぐに、ＲｅｃＳｙｓはそれらをランダムマスク
【０１０８】
【数２５】
2016517069.tif 000027
【０１０９】
を用いて不明瞭化し、ηはランダムまたは擬似ランダム変数であり、
【０１１０】
【数２６】
2016517069.tif 000028
【０１１１】
はＸＯＲ演算である。ＲｅｃＳｙｓはそれらを、ガーブル回路を組み立てるのに必要な完全な仕様と共同でＣＳＰに送る。特に、ＲｅｃＳｙｓは、ユーザおよび項目プロファイルの次元（すなわちパラメータｄ）、評点の総数（すなわちパラメータＭ）、ユーザおよび項目の総数、ならびにガーブル回路において実数の整数および小数部を表すのに用いられるビット数を指定する。
【０１１２】
ＲｅｃＳｙｓがＭ個の蓄積された評点にわたって行列因数分解を実行することを望むときはいつでも、それはＭをＣＳＰに報告する。ＣＳＰは、（ａ）入力を復号し、次いで（ｂ）行列因数分解を実行する、ガーブル回路をＲｅｃＳｙｓに提供することができる。”Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｒｉｄｇｅ  ｒｅｇｒｅｓｓｉｏｎ  ｏｎ  ｈｕｎｄｒｅｄｓ  ｏｆ  ｍｉｌｌｉｏｎｓ  ｏｆ  ｒｅｃｏｒｄｓ”，ＩＥＥＥ  Ｓ＆Ｐ，  ２０１３，ｂｙ  Ｖ．  Ｎｉｋｏｌａｅｎｋｏ，  Ｕ．  Ｗｅｉｎｓｂｅｒｇ，  Ｓ．  Ｉｏａｎｎｉｄｉｓ，  Ｍ．  Ｊｏｙｅ，  Ｄ．  Ｂｏｎｅｈ，  およびＮ．  Ｔａｆｔでは、回路内での復号は、マスクおよび準同型暗号を用いることによって回避される。本原理はこの着想を行列因数分解に利用するが、部分的準同型暗号方式が必要なだけである。
【０１１３】
暗号を受け取るとすぐに、ＣＳＰはそれらを復号し、マスクされた値
【０１１４】
【数２７】
2016517069.tif 000029
【０１１５】
を入手する。次いで行列因数分解を設計図として用い、ＣＳＰは以下を行うヤオのガーブル回路を用意する。
【０１１６】
（ａ）入力としてマスクηに対応するガーブル化された値を取り込む。
【０１１７】
（ｂ）マスクηを除去して対応するタプル（ｉ，ｊ，ｒi,j）を回復する。
【０１１８】
（ｃ）行列因数分解を実行する。
【０１１９】
（ｄ）ρjでマスクされた項目プロファイル
【０１２０】
【数２８】
2016517069.tif 000030
【０１２１】
および
【０１２２】
【数２９】
2016517069.tif 000031
【０１２３】
でマスクされたユーザプロファイルを出力する。ここで、ｊ∈［ｍ］、
【０１２４】
【数３０】
2016517069.tif 000032
【０１２５】
、ｉ∈［ｎ］である。
【０１２６】
プロトコルの終わりには、ＲｅｃＳｙｓはそれぞれの
【０１２７】
【数３１】
2016517069.tif 000033
【０１２８】
を各ユーザｉに送り、それは次いでマスク
【０１２９】
【数３２】
2016517069.tif 000034
【０１３０】
、ｉ∈［ｎ］を除去することによってそのプロファイルｕiを回復する。ユーザｉが項目推薦を入手することを望む場合、ユーザは、そのプロファイルをそれ自体の公開鍵ｐｋiのもとで加法的準同型暗号アルゴリズム
【０１３１】
【数３３】
2016517069.tif 000035
【０１３２】
（例えばＰａｉｌｌｉｅｒの暗号システムなど）によって暗号化し、結果として生じる値
【０１３３】
【数３４】
2016517069.tif 000036
【０１３４】
をＲｅｃＳｙｓに送る。ＲｅｃＳｙｓは、それをＣＳＰに転送し、またｊ∈［ｍ］に対して、
【０１３５】
【数３５】
2016517069.tif 000037
【０１３６】
を計算する。ＣＳＰは、ｊ∈［ｍ］に対して、
【０１３７】
【数３６】
2016517069.tif 000038
【０１３８】
を計算し、この値をＲｅｃＳｙｓに返す。最後に、ＲｅｃＳｙｓは、
【０１３９】
【数３７】
2016517069.tif 000039
【０１４０】
を
【０１４１】
【数３８】
2016517069.tif 000040
【０１４２】
から減算して、すべての項目ｊ∈［ｍ］に対する予測された評点
【０１４３】
【数３９】
2016517069.tif 000041
【０１４４】
の暗号化を取得し、それらをユーザｉに送る。次いでユーザｉは、その秘密復号鍵を用いてクリアテキストでの推薦、すなわち
【０１４５】
【数４０】
2016517069.tif 000042
【０１４６】
を取得することができる。
【０１４７】
（４）および（５）に概要が示された勾配降下演算による行列因数分解の計算は、実数の加算、減算、および乗算が関係する。これらの演算は、回路において効率的に実装され得る。勾配降下（４）のＫ回の反復は、Ｋ個の回路「レイヤ」に対応し、それぞれはすぐ前のレイヤにおける値から、プロファイルの新しい値を計算する。回路の出力は項目プロファイルＶであり、一方、ユーザプロファイルは廃棄される。
【０１４８】
演算がクリアテキストで、例えばＲＡＭモデルにおいて行われるときは、勾配降下の各反復を計算する時間複雑度がＯ（Ｍ）であることに当業者は気付くであろう。各勾配の計算（５）は２Ｍ個の項の加算を必要とし、プロファイル更新（４）はＯ（ｎ＋ｍ）＝Ｏ（Ｍ）において行われ得る。
【０１４９】
勾配降下を回路として実装することにおける主要な課題は、それを効率的に行うことにある。これを示すために、以下の単純な実装について考えることができる。
【０１５０】
Ｑ１．各対（ｉ，ｊ）∈［ｎ］×［ｍ］に対して、回路は入力からインジケータδi，ｊ＝１(i,j)∈Mを計算し、これはｉがｊを評点した場合は１、そうでなければ０となる。
【０１５１】
Ｑ２．各反復においてこれらの回路の出力を用いて、各項目およびユーザ勾配を、それぞれｍ個およびｎ個の積にわたる合計として計算する。
【０１５２】
【数４１】
2016517069.tif 000043
【０１５３】
残念ながら、この実装は非効率的であり、勾配降下アルゴリズムのあらゆる反復は、Ｏ（ｎ×ｍ）の回路複雑度を有することになる。実際面では、通常のケースであるようにＭ≪ｎ×ｍのときは、上記の回路は、クリアテキストでの勾配降下より大幅に効率が低くなる。実際、二次コストＯ（ｎ×ｍ）は、ほとんどのデータセットに対して極端に高くなる。単純な実装の非効率性は、回路の設計の時点でどのユーザが項目を評点したか、およびユーザによってどの項目が評点されたかを特定できないことから生じ、データにおける固有のまばらさを活用する能力を減じる。
【０１５４】
反対に、本原理の好ましい実施形態によれば、回路実装は、その複雑度がＯ（（ｎ＋ｍ＋Ｍ）ｌｏｇ2（ｎ＋ｍ＋Ｍ））である、すなわちクリアテキストでの実装の対数多項式係数以内であるソーティングネットワークに基づいて提供される。要約すると、タプル（ｉ，ｊ，ｒi,j）に対応する入力データと、ユーザおよび項目プロファイルの両方のためのプレースホルダ⊥との両方は、配列内に共同で記憶される。適切なソート動作を通じて、ユーザおよび項目プロファイルは、それらが識別子をそれと共有する入力の近くに配置され得る。データを通した線形パスは、勾配の計算およびプロファイルの更新を可能にする。ソートするときは、プレースホルダは、＋∞すなわち他のどの数より大きなものとして扱われる。
【０１５５】
本原理の好ましい実施形態による図４のフローチャート４００の要件を満たす行列因数分解アルゴリズムは、以下のステップによって記述され得る。
【０１５６】
Ｃ１．マトリックスＳを初期化する４１０
アルゴリズムは入力として、組
【０１５７】
【数４２】
2016517069.tif 000044
【０１５８】
、または等価的にタプル
【０１５９】
【数４３】
2016517069.tif 000045
【０１６０】
を受け取り、ｎ＋ｍ＋Ｍ個のタプルの配列を構築する。Ｓの最初のｎ個およびｍ個のタプルはそれぞれユーザおよび項目プロファイルのためのプレースホルダとして働き、残りのＭ個のタプルは入力Ｌiを記憶する。より具体的には、各ユーザｉ∈［ｎ］に対して、アルゴリズムはタプル（ｉ，⊥，０，⊥，ｕi，⊥）を構築し、
【０１６１】
【数４４】
2016517069.tif 000046
【０１６２】
はランダムに選択されたユーザｉの初期プロファイルである。各項目ｊ∈［ｍ］に対して、アルゴリズムはタプル（⊥，ｊ，０，⊥，⊥，ｖj，⊥）を構築し、
【０１６３】
【数４５】
2016517069.tif 000047
【０１６４】
はやはりランダムに選択された項目ｊの初期プロファイルである。最後に、各対
【０１６５】
【数４６】
2016517069.tif 000048
【０１６６】
に対して、アルゴリズムは対応するタプル（ｉ，ｊ，１，ｒi,j，⊥，⊥）を構築し、ｒi,jはユーザｉの項目ｊに対する評点である。結果として生じる配列は、図５（Ａ）に示される。ｋ番目のタプルのｌ番目の要素をｓl,kによって表すと、これらの要素は以下の役割をする。
（ａ）ｓ1,k：［ｎ］におけるユーザ識別子
（ｂ）ｓ2,k：［ｍ］における項目識別子
（ｃ）ｓ3,k：タプルが「プロファイル」または「入力」タプルであるかを示す２進フラグ
（ｄ）ｓ4,k：「入力」タプルにおける評点
（ｅ）ｓ5,k：Ｒdにおけるユーザプロファイル
（ｆ）ｓ6,k：Ｒdにおける項目プロファイル
Ｃ２．タプルを、ユーザｉｄに関して（行１および３に関して）昇順にソートする４２０。２つのｉｄが等しい場合は、タプルフラグすなわち各タプル内の３番目の要素を比較することによって均衡を破る。したがって、ソートの後には、各「ユーザプロファイル」タプルは、同じｉｄを有する「入力」タプルによって後続される。
【０１６７】
Ｃ３．ユーザプロファイルをコピーする（左パス）４３０。
【０１６８】
ｓ5,k←ｓ3,k＊ｓ5,k-1＋（１−ｓ3,k）＊ｓ5,k、    ｋ＝２，．．．，Ｍ＋ｎ
Ｃ４．タプルを、項目ｉｄに関して（行２および３に関して）昇順にソートする４４０。２つのｉｄが等しい場合は、タプルフラグすなわち各タプル内の３番目の要素を比較することによって均衡を破る。
【０１６９】
Ｃ５．項目プロファイルをコピーする（左パス）４５０。
【０１７０】
ｓ6,k←ｓ3,k＊ｓ6,k-1＋（１−ｓ3,k）＊ｓ6,k、    ｋ＝２，．．．，Ｍ＋ｍ
Ｃ６．勾配寄与を計算する４６０  ∀ｋ＜Ｍ。
【０１７１】
【数４７】
2016517069.tif 000049
【０１７２】
、∀ｋ＜Ｍ
Ｃ７．項目プロファイルを更新する（右パス）４７０。
【０１７３】
ｓ6,k←ｓ6,k＋ｓ3,k+1＊ｓ6,k+1＋（１−ｓ3,k）＊２γμｓ6,k、    ｋ＝Ｍ＋ｎ−１，・・・，１
Ｃ８．行１および３に関してタプルをソートする４７５。
【０１７４】
Ｃ９．ユーザプロファイルを更新する（右パス）４８０。
【０１７５】
ｓ5,k←ｓ5,k＋ｓ3,k+1＊ｓ5,k+1＋（１−ｓ3,k）＊２γμｓ5,k、    ｋ＝Ｍ＋ｎ−１，・・・，１
Ｃ１０．反復数がＫ未満の場合はＣ３へ行く４８５。
【０１７６】
Ｃ１１．行３および２に関してタプルをソートする４９０。
【０１７７】
Ｃ１２．ｋ＝１，．．．，ｍに対して項目プロファイルｓ6,kを出力し４９５、出力は少なくとも１つの項目プロファイルに制限され得る。
【０１７８】
勾配降下反復は、以下の３つの主要なステップを含む。
【０１７９】
Ａ．プロファイルをコピーする：各反復において、各それぞれのユーザｉおよび各項目ｊのプロファイルｕiおよびｖjは、ｉおよびｊが現れる各「入力」タプルの対応する要素ｓ5,kおよびｓ6,kにコピーされる。これは、アルゴリズムのステップＣ２からＣ５において実装される。例えば、ユーザプロファイルをコピーするために、Ｓはユーザｉｄ（すなわちｓ1,k）を主インデックスとして用い、フラグ（すなわちｓ3,k）を副インデックスとして用いてソートされる。Ｓの初期状態に適用されるこのようなソートは、図５（Ｂ）に見出され得る。その後に、ユーザｉｄは、アルゴリズムのステップＣ３に形式的に記述されるように、配列を左から右に移動（「左」パス）することによってコピーされる。これは、ｓ5,kを各「プロファイル」タプルからその隣接する「入力」タプルにコピーし、項目プロファイルも同様にコピーされる。
【０１８０】
Ｂ．勾配寄与を計算する：プロファイルがコピーされた後に、例えば（ｉ，ｊ）に対応する各「入力」タプルは、最後の反復において計算されたのに従って、評点ｒi,j（ｓ4,kにおける）、ならびにプロファイルｕiおよびｖj（それぞれｓ5,kおよびｓ6,kにおける）を記憶する。これらから以下の量ｖj（ｒi,j−＜ｕi，ｖj＞）およびｕi（ｒi,j−＜ｕi，ｖj＞）が計算され、これらは（５）によって与えられるのに従って、ｕiおよびｖjに対する勾配におけるタプルの「寄与」と見なされ得る。これらは、アルゴリズムのステップＣ６によって示されるように、タプルのｓ5,kおよびｓ6,k要素を置き換える。フラグの適切な使用によりこの演算は、「入力」タプルのみに影響し、「プロファイル」タプルは不変のままにする。
【０１８１】
Ｃ．プロファイルを更新する：最後にアルゴリズムのステップＣ７からＣ９に示されるように、ユーザおよび項目プロファイルが更新される。適切なソートによって「プロファイル」タプルは再び、それらがｉｄを共有する「入力」タプルに隣接される。更新されたプロファイルは、配列の右から左への移動（右パス）によって計算される。この演算は、「入力」タプルを移動するのに従って、勾配の寄与を加算する。「プロファイル」タプルに出会うと、合計された勾配寄与はプロファイルに加算され、適切にスケール化される。プロファイルを過ぎた後は、勾配寄与の合計は、フラグｓ3,k、ｓ3,k+1の適切な使用によりゼロから再開する。
【０１８２】
上記の演算はＫ回、すなわち勾配降下の所望の反復の数、繰り返される。最終的に、最後の反復の終了において、配列は、主インデックスとしてフラグ（すなわちｓ3,k）、および副インデックスとして項目ｉｄ（すなわちｓ2,k）に関してソートされる。これはすべての項目プロファイルタプルを配列内の最初のｍ個の位置に提供し、それらから項目プロファイルが出力され得る。さらにユーザプロファイルを取得するために、最後の反復の終了において配列は、主インデックスとしてフラグ（すなわちｓ3,k）および副インデックスとしてユーザｉｄ（すなわちｓ1,k）に関してソートされる。これはすべてのユーザプロファイルタプルを配列内の最初のｎ個の位置に提供し、それらからユーザプロファイルが出力され得る。
【０１８３】
当業者は、上記の演算のそれぞれはデータ紛失的であり、回路として実装され得ることを認識するであろう。プロファイルをコピーし更新することは、（ｎ＋ｍ＋Ｍ）個のゲートを必要とし、したがって全体の複雑度はソートによって決定され、これは例えばＢａｔｃｈｅｒの回路を用いてＯ（（ｎ＋ｍ＋Ｍ）ｌｏｇ2（ｎ＋ｍ＋Ｍ））のコストを生じる。アルゴリズムのステップＣ６におけるソートおよび勾配計算は、最も多量の計算を必要とする演算であり、幸いにも両方とも高度に並列化可能である。さらに、ソートは、各反復において以前に計算された比較を再利用することによってさらに最適化され得る。特に、この回路は、ブール回路として（例えばＯＲ、ＡＮＤ、ＮＯＴ、およびＸＯＲのグラフとして）実装されることができ、これは前に説明されたように実装がガーブル化されることを可能にする。
【０１８４】
本原理によれば、上述の行列因数分解アルゴリズムの実装は、前述のプロトコルと共に、プライバシー保護のやり方での推薦のための新規な方法を提供する。さらにこのソリューションは、ソーティングネットワークを用いることによってクリアテキストにおいて行われる行列因数分解の対数多項式係数以内の複雑度を有する回路を生じる。さらに、この実装の追加の利点は、この回路のガーブル化および実行が、高度に並列化可能なことである。
【０１８５】
本原理によるシステムの実装においてガーブル回路構築は、公的に利用可能なガーブル回路フレームワークであるＦａｓｔＧＣが基にされた。ＦａｓｔＧＣはＪａｖａベースのオープンソースフレームワークであり、基本的なＸＯＲ、ＯＲ、およびＡＮＤゲートを用いた回路定義を可能にする。回路が構築された後に、フレームワークは、ガーブル化、紛失通信、およびガーブル回路の完全な評価を取り扱う。しかしながら、回路をガーブル化および実行する前に、ＦａｓｔＧＣは、メモリにおいてガーブル化されない回路全体を、Ｊａｖａオブジェクトの組として表す。いずれの時点においてもゲートのサブセットのみがガーブル化および／または実行されるので、これらのオブジェクトは、ガーブル化されない回路が提供するべきメモリフットプリントに対してかなりのメモリオーバヘッドを招く。さらに、ＦａｓｔＧＣは、上述のように実行プロセスと並列にガーブル化を実行するが、両方の動作は順次的なやり方で生じ、ゲートは、それらの入力が準備できた後に、一時に１つずつ処理される。この実装は並列化の適用ができないことを当業者は明らかに認識するであろう。
【０１８６】
結果として、フレームワークは、ＦａｓｔＧＣのメモリフットプリントを低減するが、複数のプロセッサーにわたる並列化されたガーブル化および計算を可能にして、上記２つの問題に対処するように修正された。特に、我々は、それぞれ１つが、並列に実行され得る垂直な「スライス」の組を備える、順次的な「レイヤ」に回路を水平に分割する能力を導入した。レイヤは、すべてのその入力が準備できたときにのみ、メモリ内に生成される。ガーブル化され評価された後にレイヤ全体がメモリから除去され、次のレイヤが構築されることができ、したがってメモリフットプリントを、最も大きなレイヤのサイズに制限する。レイヤの実行は、そのスライスをスレッドに割り当てるスケジューラを用いて行われ、それらが並列に実行することを可能にする。並列化は複数のコアを有する単一のマシン上に実装されたが、スライス間で共有される状態は想定されないので、実装は異なるマシンにわたって実行するように直接的なやり方で拡張され得る。
【０１８７】
最後に、アルゴリズムにおいて概要が示された数値演算を実施するために、ＦａｓｔＧＣは、ソーティングに加えて、固定小数点数表示を有する実数にわたる加算および乗算をサポートするように拡張された。ソーティングのために、Ｂａｔｃｈｅｒのソーティングネットワークが用いられた。固定小数点数表示は、打ち切りから結果として生じる精度低下と、回路のサイズとのトレードオフを提供した。さらに、アルゴリズムの実装は、複数の方法で最適化され、特に、
（ａ）回路の実行の始めにおいて計算された比較を再利用することによってソーティングのコストを低減した。
【０１８８】
ソーティングネットワークのビルディングブロックは、２つの項目を比較し、出力対が順序付けられるように必要に応じてそれらを交換する比較交換回路である。行列因数分解アルゴリズムのソーティング演算（行Ｃ４およびＣ８）は、Ｋ回の勾配降下反復のそれぞれにおいて、反復ごとに全く同じ入力を用いて、タプル間の同一の比較を実行する。実際、各ソーティングは、各反復において全く同じやり方で配列Ｓ内のタプルを並べ換える。この特性は、これらのソーティングのそれぞれに対して比較演算を１回だけ実行することによって活用される。特に、（ｉ，ｊ，フラグ，評点）の形のタプルのソーティングは、例えば最初ｉとフラグ、ｊとフラグ、戻ってｉとフラグに関して、計算の最初に（ユーザまたは項目プロファイルのペイロードなしに）行われる。その後に、これらのソーティングのそれぞれにおいて、比較回路の出力は、勾配降下の間に用いられる交換回路への入力として再利用される。結果として、各反復において適用される「ソーティング」ネットワークは、比較を行わずに単にタプルを並べ換える（すなわち、これは「並べ換え」ネットワークである）。
【０１８９】
（ｂ）配列Ｓのサイズを低減した。
【０１９０】
すべての比較を予め計算することはまた、Ｓ内のタプルのサイズを大幅に低減することを可能にする。まず始めに、ユーザまたは項目ｉｄに対応する行は、ソーティング時の比較への入力として、行列因数分解アルゴリズムにおいてのみ用いられることを当業者は認めることができる。フラグおよび評点は、コピーおよび更新段階の間に用いられるが、各反復においてそれらの相対位置は同一である。さらに、これらの位置は、我々の計算の始めにおいて、タプル（ｉ，ｊ，フラグ，評点）のソーティングの出力として計算され得る。したがって、各反復において行われる「並べ換え」演算は、ユーザおよび項目プロファイルに適用される必要があるだけで、すべての他の行は配列Ｓから除去され得る。もう１つの改善は、１組のプロファイル、例えばユーザを固定すること、項目プロファイルのみを並べ換えることの２つの付加的要因により、並べ換えのコストを低減する。次いで項目プロファイルは２つの状態の間で循環し、それぞれ一方は並べ換えを通して他方から到達可能であり、１つにおいてそれらはユーザプロファイルと整列され、部分的勾配が計算され、１つにおいては項目プロファイルが更新されコピーされる。
【０１９１】
（ｃ）ＸＯＲを用いることによって交換演算を最適化した。
【０１９２】
ＸＯＲ演算は「無償」で実行され得るということを前提として、可能な場合は常にＸＯＲを用いることによって、比較、交換、更新、およびコピー演算の最適化が行われる。当業者は、無償ＸＯＲが、関連するガーブル化されたテーブルおよび対応するハッシュまたは対称鍵演算なしに、ガーブル化されることができ、計算および通信における著しい改善になることを理解するであろう。
【０１９３】
（ｄ）計算を並列化した。
【０１９４】
ソーティングおよび勾配計算は、行列因数分解回路における計算の大部分を構成し（コピーおよび更新の寄与は実行時間の３％以下であり、非ＸＯＲゲートの０．４％である）、これらの演算は、ＦａｓｔＧＣのこの拡張により並列化される。勾配計算は明らかに並列化可能であり、ソーティングネットワークも高度に並列化可能である（並列化は彼等の開発の主要な動機である）。さらに、各ソートにおける並列スライスの多くは同一であるので、回路スライスを定義する同じＦａｓｔＧＣオブジェクトは、異なる入力を有して再利用され、メモリにおいてオブジェクトを繰り返し生成および破棄する必要性を大幅に低減する。
【０１９５】
本原理は、ハードウェア、ソフトウェア、ファームウェア、専用プロセッサー、またはそれらの組み合わせの様々な形で実装され得ることが理解されるべきである。本原理はハードウェアおよびソフトウェアの組み合わせとして実装されることが好ましい。さらにソフトウェアは、プログラム記憶装置上に有形に具体化されたアプリケーションプログラムとして実装されることが好ましい。アプリケーションプログラムは、任意の適切なアーキテクチャを備えたマシンにアップロードされ、それによって実行され得る。マシンは、１または複数の中央処理装置（「ＣＰＵ」）、ランダムアクセスメモリ（ＲＡＭ）、および入力／出力（Ｉ／Ｏ）インターフェースなどのハードウェアを有する、コンピュータプラットフォーム上に実装されることが好ましい。コンピュータプラットフォームはまた、オペレーティングシステムおよびマイクロ命令コードを含む。本明細書で述べられた様々なプロセスおよび機能は、オペレーティングシステムによって実行される、マイクロ命令コードの一部もしくはアプリケーションプログラムの一部（またはそれらの組み合わせ）とすることができる。さらに追加のデータ記憶装置および印刷装置などの様々な他の周辺装置が、コンピュータプラットフォームに接続され得る。
【０１９６】
図６は、本原理を実装するために用いられる、最小のコンピューティング環境６００のブロック図を示す。コンピューティング環境６００は、プロセッサー６１０、および少なくとも１つ（および好ましくは２つ以上）のＩ／Ｏインターフェース６２０を含む。Ｉ／Ｏインターフェースは有線または無線とすることができ、無線での実装においては、例えばエンドユーザに遠隔に提供される「サービスとしてのソフトウェア」（ＳＡＡＳ）機能として本原理が提供されることを可能にするために、コンピューティング環境６００がグローバルネットワーク（例えばインターネット）上で動作し、他のコンピュータまたはサーバー（例えばクラウドベースのコンピューティングまたはストレージサーバー）と通信することを可能にするように、適切な無線通信プロトコルによって予め構成される。１または複数のメモリ６３０および／または記憶装置（ＨＤＤ）６４０も、コンピューティング環境６００内に提供される。コンピューティング環境６００または複数のコンピュータ環境６００は、本原理の一実施形態による行列因数分解Ｃ１〜Ｃ１２（図４）のためのプロトコルＰ１〜Ｐ１７（図３）を実装することができる。特に本原理の実施形態では、コンピューティング環境６００はＲｅｃＳｙｓ２３０を実装することができ、別のコンピューティング環境６００はＣＳＰ２５０を実装することができ、ソースは１または複数のコンピュータ環境６００を含むことができ、それぞれはＲｅｃＳｙｓ２３０およびＣＳＰ２５０と通信するために用いられる、非限定的にデスクトップコンピュータ、携帯電話、スマートフォン、フォンウォッチ、タブレットコンピュータ、携帯情報端末（ＰＤＡ）、ノートブック、およびラップトップコンピュータを含み、互いに異なるユーザ２１０に関連付けられる。さらにＣＳＰ２５０はソースに含まれることができ、または等価的にソースの各ユーザ２１０のコンピュータ環境に含められ得る。
【０１９７】
さらに、添付の図に示される、構成するシステム構成要素および方法ステップのいくつかは、ソフトウェアにおいて実装されることが好ましいので、システム構成要素（またはプロセスステップ）の間の実際の接続は、本原理がプログラムされるやり方に応じて異なり得ることが理解されるべきである。本明細書の教示に鑑みて、当業者は本原理のこれらのおよび同様な実装または構成を検討することができるであろう。
【０１９８】
例示的実施形態について本明細書において添付の図を参照して述べてきたが、本原理はそれらの正確な実施形態に限定されず、本原理の範囲および趣旨から逸脱せずに、当業者によってそれらに様々な変更および修正を提供し得ることが理解されるべきである。すべてのこのような変更および修正は、添付の特許請求の範囲に記載された本原理の範囲に含まれるものである。
【図１】
2016517069.tif 000050
【図２】
2016517069.tif 000051
【図３Ａ】
2016517069.tif 000052
【図３Ｂ】
2016517069.tif 000053
【図３Ｃ】
2016517069.tif 000054
【図３Ｄ】
2016517069.tif 000055
【図４Ａ】
2016517069.tif 000056
【図４Ｂ】
2016517069.tif 000057
【図４Ｃ】
2016517069.tif 000058
【図５】
2016517069.tif 000059
【図６】
2016517069.tif 000060
【国際調査報告】
2016517069.tif 000061
2016517069.tif 000062
2016517069.tif 000063