(57)【要約】  プライバシー保護リコメンデーションを生成する方法とシステムは、第１のユーザセットから、トークンとアイテムを含む第１のレコードセットを入力として受信することにより始まる；第１のレコードセットに対する行列因子分解に基づき第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計及び評価し、要求ユーザからの第２のレコードに対するリッジ回帰に基づき第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計及び評価し、プライバシー保護して、少なくとも１つのアイテムに関するリコメンデーションを生成し、レコードとそれから抽出される情報がそのソース以外にパーティには秘密にしておかれ、リコメンデーションは要求ユーザのみによって知られる。該システムは、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計する暗号サービスプロバイダと、第１の回路を評価するリコメンダも含む。要求ユーザは第２の回路を評価し、第１のユーザセットには含まれない。
2016510913.tif 000002
【特許請求の範囲】
【請求項１】
行列因子分解とリッジ回帰とによりセキュアにリコメンデーションを生成する方法であって、
第１のレコードセットを受信するステップであって、各レコードは、第１のユーザセット中の各ユーザから受信され、トークンセットとアイテムセットとを含み、前記各ユーザ以外のパーティには秘密にされる、ステップと、
リコメンダ（ＲｅｃＳｙｓ）において第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いて行列因子分解に基づき前記第１のレコードセットを評価するステップであって、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセットのすべてのアイテムのマスクされたアイテムプロファイルを含む、ステップと、
少なくとも１つのアイテムについて要求ユーザからリコメンデーション要求を受信するステップと、
前記要求ユーザが、第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いてリッジ回帰に基づき第２のレコードと前記マスクされたアイテムプロファイルとを評価するステップであって、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記少なくとも１つのアイテムに関するリコメンデーションを含み、前記リコメンデーションは前記要求ユーザのみにより知られる、ステップとを有する、方法。
【請求項２】
前記ＣＳＰ中の第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記第１のレコードセットに対して行列因子分解を行うように設計するステップであって、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセットのすべてのアイテムのマスクされたアイテムプロファイルを含む、ステップと、
前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔをＲｅｃＳｙｓに転送するステップと、
前記ＣＳＰ中の第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記第２のレコードと前記マスクされたアイテムプロファイルとにリッジ回帰を行うように設計するステップであって、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記少なくとも１つのアイテムに関するリコメンデーションを含む、ステップと、
前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記要求ユーザに転送するステップとをさらに有する、
請求項１に記載の方法。
【請求項３】
前記設計するステップは、
行列因子分解演算をブーリアン回路として設計するステップと、
リッジ回帰演算をブーリアン回路として設計するステップとを有する、
請求項２に記載の方法。
【請求項４】
行列因子分解回路を設計するステップは、
前記第１のレコードセットのアレイを構成するステップと、
前記アレイに対して、ソーティング、コピー、更新、比較、及び傾斜貢献の計算の動作を実行するステップとを有する、
請求項３に記載の方法。
【請求項５】
前記第１のレコードセットを暗号化して暗号化レコードを生成するステップであって、暗号化は第１のレコードセットの受信前に行われる、ステップをさらに有する、
請求項２に記載の方法。
【請求項６】
前記ＣＳＰにおいて公開暗号鍵を生成するステップと、
鍵を前記各ユーザに送信するステップとをさらに有する、
請求項５に記載の方法。
【請求項７】
暗号は部分的準同型暗号であり、前記方法は、
前記ＲｅｃＳｙｓにおいて前記暗号化されたレコードをマスクして、マスクされたレコードを生成するステップと、
前記ＣＳＰにおいて、前記マスクされたレコードを復号して、マスクされ復号されたレコードを生成するステップとを有する、
請求項５に記載の方法。
【請求項８】
前記設計するステップは、
前記マスクされ復号されたレコードを、処理する前に、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ内でアンマスクするステップを有する、
請求項７に記載の方法。
【請求項９】
前記ＣＳＰと前記ＲｅｃＳｙｓとの間でｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うステップであって、前記ＲｅｃＳｙｓは前記マスクされ復号されたレコードのｇａｒｂｌｅｄ値を受け取り、前記レコードは前記ＲｅｃＳｙｓと前記ＣＳＰには秘密にしておかれる、
請求項７に記載の方法。
【請求項１０】
リッジ回帰回路を設計するステップは、
前記要求ユーザから、マスクされたアイテムプロファイルと第２のレコードとを受信するステップと、
マスクされたアイテムプロファイルをアンマスクして、トークンと、アイテムと、アイテムプロファイルとを含むタプルアレイを生成するステップであって、対応するアイテムプロファイルは前記第２のレコードからの各トークンとアイテムに加えられる、ステップと、
前記タプルアレイにリッジ回帰を行い、要求ユーザプロファイルを生成するステップと、
前記要求ユーザプロファイルと少なくとも１つのアイテムプロファイルからリコメンデーションを計算するステップとを有する、
請求項３に記載の方法。
【請求項１１】
アレイを生成するステップはソーティングネットワークを用いて行う、
請求項１０に記載の方法。
【請求項１２】
前記要求ユーザ、ＣＳＰ及びＲｅｃＳｙｓの間でプロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うステップであって、前記要求ユーザは前記マスクされたアイテムプロファイルのｇａｒｂｌｅｄ値を受信し、前記マスクされたアイテムプロファイルは前記要求ユーザとＣＳＰには秘密にしておかれる、請求項１に記載の方法。
【請求項１３】
各レコードのトークンとアイテムの数を受け取るステップをさらに有する、
請求項１に記載の方法。
【請求項１４】
各レコードのトークン数が最大値を表す値より小さいとき、トークン数が前記値と等しいレコードを生成するため、各レコードをヌルエントリでパディングするステップをさらに有する、請求項１に記載の方法。
【請求項１５】
前記第１のレコードセットのソースはデータベースであり、前記第２のレコードのソースはデータベースである、請求項１に記載の方法。
【請求項１６】
前記ＣＳＰがｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの設計用のパラメータセットを受信するステップであって、パラメータは前記ＲｅｃＳｙｓにより送信される、ステップをさらに有する、請求項２に記載の方法。
【請求項１７】
行列因子分解とリッジ回帰とによりセキュアにリコメンデーションを生成するシステムであって、
第１のレコードセットを提供する第１のユーザセットと、
第１と第２の回路にセキュアな行列因子分解とリッジ回帰回路を提供する暗号サービスプロバイダ（ＣＳＰ）と、
行列因子分解を評価するＲｅｃＳｙｓと、
第２のレコードを提供し、前記リッジ回帰回路を評価し、各レコードがそのユーザ以外のパーティには秘密にしておかれるようにする、要求ユーザとを有し、
ユーザ、ＣＳＰ及びＲｅｃＳｙｓはそれぞれ、
少なくとも１つの入出力を受けるプロセッサと、
前記プロセッサと信号通信する少なくとも１つのメモリとを有し、
前記ＲｅｃＳｙｓのプロセッサは、
第１のユーザセットから第１のレコードセットを受信し、各レコードは、トークンセットとアイテムセットとを含み、前記各ユーザ以外のパーティには秘密にされ、
要求ユーザから、少なくとも１つのアイテムを求める要求を受信し、
第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いて、行列因子分解に基づいて、前記第１のレコードセットを評価し、
前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は、前記第１のレコードセットのすべてのアイテムのマスクされたアイテムプロファイルを含み、
前記要求ユーザのプロセッサは、
第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いてリッジ回帰に基づいて第２のレコードと前記マスクされたアイテムプロファイルとを評価するように構成され、
前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は少なくとも１つのアイテムに関するリコメンデーションを含み、前記リコメンデーションは前記要求ユーザのみによって知られる、
システム。
【請求項１８】
前記ＣＳＰのプロセッサは、
第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記第１のレコードセットに対して行列因子分解を行うように設計し、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセットのすべてのアイテムのマスクされたアイテムプロファイルを含み、
前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記ＲｅｃＳｙｓに転送し、
第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記第２のレコードと前記マスクされたアイテムプロファイルとにリッジ回帰を行うように設計し、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記少なくとも１つのアイテムに関するリコメンデーションを含み、
前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記要求ユーザに転送するように構成されている、
請求項１７に記載のシステム。
【請求項１９】
前記ＣＳＰプロセッサは、
行列因子分解演算をブーリアン回路として設計し、
リッジ回帰演算をブーリアン回路として設計する
ように構成されていることにより、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計するように構成されている、
請求項１８に記載のシステム。
【請求項２０】
前記ＣＳＰプロセッサは、
前記第１のレコードセットのアレイを構成し、
前記アレイにおけるソーティング、コピー、交信、比較及び傾斜貢献の計算の動作を行う
ように構成されていることにより、行列因子分解回路を設計するように構成されている、
請求項１９に記載のシステム。
【請求項２１】
前記第１のユーザセットの各ユーザプロセッサは、各レコードを暗号化して、前記レコードを提供する前に、暗号化したレコードを生成するように構成されている、
請求項１８に記載のシステム。
【請求項２２】
前記ＣＳＰプロセッサは、さらに、
前記ＣＳＰにおいて公開暗号鍵を生成し、
鍵を前記第１のユーザセットに送信するように構成されている、
請求項２１に記載のシステム。
【請求項２３】
暗号は部分的準同型暗号であり、
ＲｅｃＳｙｓのプロセッサは、さらに、
暗号化されたレコードをマスクして、マスクされたレコードを生成するように構成され、
前記ＣＳＰプロセッサは、さらに、
マスクされたレコードを復号して、マスクされ復号されたレコードを生成するように構成されている、
請求項２１に記載のシステム。
【請求項２４】
前記ＣＳＰプロセッサは、
前記マスクされ復号されたレコードを、処理する前に、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ内でアンマスクするように構成されていることにより、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計するようにさらに構成されている、
請求項２３に記載のシステム。
【請求項２５】
ＲｅｃＳｙｓのプロセッサとＣＳＰのプロセッサは、ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うようにさらに構成され、
前記ＲｅｃＳｙｓはマスクされ復号されたレコードのｇａｒｂｌｅｄ値を受信し、レコードは前記ＲｅｃＳｙｓとＣＳＰには秘密にしておかれる、
請求項２３に記載のシステム。
【請求項２６】
前記ＣＳＰプロセッサは、
前記要求ユーザから、マスクされたアイテムプロファイルと第２のレコードとを受信し、
マスクされたアイテムプロファイルをアンマスクして、トークンと、アイテムと、アイテムプロファイルとのアレイを生成し、対応するアイテムプロファイルは前記第２のレコードからの各トークンとアイテムに加えられ、
タプルアレイにリッジ回帰を行い、要求ユーザプロファイルを生成し、
前記要求ユーザプロファイルと少なくとも１つのアイテムプロファイルからリコメンデーションを計算する
ように構成されていることにより、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計するように構成されている、請求項１９に記載のシステム。
【請求項２７】
前記ＣＳＰプロセッサは、ソーティングネットワークを設計するように構成されていることにより、アレイを生成するように構成されている、
請求項２６に記載のシステム。
【請求項２８】
要求プロセッサ、ＲｅｃＳｙｓのプロセッサ及びＣＳＰのプロセッサは、プロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うようにさらに構成され、
前記要求ユーザは、マスクされたアイテムプロファイルのｇａｒｂｌｅｄ値を受信し、マスクされたアイテムプロファイルは前記要求ユーザとＣＳＰには秘密にしておかれる、
請求項１７に記載のシステム。
【請求項２９】
ＲｅｃＳｙｓのプロセッサは、さらに、
各レコードのトークン数を受信するように構成され、前記トークン数は各レコードのソースにより送信されたものである、
請求項１７に記載のシステム。
【請求項３０】
前記第１のユーザセットの各プロセッサは、各レコードのトークン数が最大値を表す値より小さいとき、トークン数が前記値と等しいレコードを生成するため、各レコードをヌルエントリでパディングするように構成されている、
請求項１７に記載のシステム。
【請求項３１】
前記第１のレコードセットのソースはデータベースであり、前記第２のレコードのソースはデータベースである、
請求項１７に記載のシステム。
【請求項３２】
前記ＣＳＰプロセッサは、さらに、
ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの設計のパラメータセットを受信するように構成され、パラメータは前記ＲｅｃＳｙｓにより送信されたものである、
請求項１８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本原理は、プライバシー保存リコメンデーションシステム及びセキュアマルチパーティ計算に関し、具体的には、プライバシーを守り目隠しをした状態で、行列因子分解とリッジ回帰に基づき、貢献ユーザと非貢献ユーザをレーティングするリコメンデーションの提供に関する。
【背景技術】
【０００２】
ここ十年での多くの研究と商業活動により、リコメンデーションシステムの使用が広がっている。かかるシステムはユーザに映画、テレビ番組、音楽、本、ホテル、レストランなどの多種のアイテムのパーソナライズされたリコメンデーションを提供する。図１は一般的なリコメンデーションシステム１００のコンポーネントを示す図であり、複数のユーザ１１０は、ソースと、ユーザの入力１２０を処理してリコメンデーション１４０を出力するリコメンデーションシステム（ＲｅｃＳｙｓ）１３０とを表す。有用なリコメンデーションを受けるため、ユーザは、自分の嗜好（ユーザの入力）に関する多くのパーソナル情報を供給するが、リコメンダがこのデータを適切に管理するとの信頼をおいている。
【０００３】
それにもかかわらず、非特許文献１及び非特許文献２などの初期の研究は、リコメンダによりかかる情報が乱用されたりユーザがプライバシーの危険にさらされたりすることがある複数の方法を示している。リコメンダは利益を得るためにデータを再販売したり、ユーザが意図的に明かした事以上の情報を抽出したりする衝動にかられることが多い。例えば、映画のレーティングやある人のテレビ視聴履歴など一般的にはセンシティブとは思われていないユーザ嗜好の記録であっても、これを用いてユーザの政党、ジェンダーなどを推論できる。リコメンデーションシステムのデータから推論できるプライベート情報は、新しいデータマイニング及び推論方法が開発されるにつれ、常に進化し続けている。極端に言えば、ユーザ嗜好の記録を用いてユーザを一意的に特定することさえでき、非特許文献３はＮｅｔｆｌｉｘデータセットを匿名の身元を暴くことによりこれをデモンストレーションして驚かせた。というように、リコメンダに悪意がないとしても、かかるデータが意図せずにもれると、ユーザはリンケージ攻撃（ｌｉｎｋａｇｅ  ａｔｔａｃｋ）、すなわちあるデータベースを、別のデータベースにおけるプライバシーを補う補助情報として用いる攻撃にさらされる。
【０００４】
将来の推論の危険、事故的情報漏洩、またはインサイダーによる危険（意図的漏洩）を常に予見できるとは限らないので、ユーザが自分のパーソナルデータを暗号化せずに明かさないリコメンデーションシステムを構成することに興味がある。本願と同日に出願された、発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＲＴＩＯＮ」である本発明者による同時係属中の出願は、行列因子分解に基づくプライバシー保護リコメンデーションシステムについて記載している。これは、ユーザがリコメンダシステムに送信したレーティングに作用する。これは個別ユーザのレーティングや彼らがレーティングしたアイテムを知らなくても、アイテムのレートを決める（ｐｒｏｆｉｌｅｓ）。これは、リコメンダがアイテムプロファイルを学習することにユーザが同意することを仮定する。
本原理は、リコメンダシステムが、ユーザのレーティングやシステムがレーティングしたアイテムに関する情報を何も学習せず、アイテムプロファイルに関する情報や、ユーザデータから抽出された統計情報を何も学習しないプライバシー保護が強いリコメンデーションシステムを提案する。よって、リコメンデーションシステムはレーティングに貢献したユーザにリコメンデーションを提供するが、提供するリコメンデーションについては完全にブラインド（ｂｌｉｎｄ）である。さらに、リコメンデーションシステムは、リッジ回帰を利用することにより、元の行列因子分解演算に参加していない新しいユーザにリコメンデーションを提供できる。
［関連出願との相互参照］
本願は２０１３年８月９日に出願された次の米国仮特許出願の利益と優先権を主張するものである：第６１／８６４０８８号（発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」；第６１／８６４０８５号（発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＣＯＵＮＴＩＮＧ」；第６１／８６４０９４号（発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＴＯ  ＲＡＴＩＮＧ  ＣＯＮＴＲＩＢＵＴＩＮＧ  ＵＳＥＲＳ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」）；及び第６１／８６４０９８号（発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ  ＡＮＤ  ＲＩＤＧＥ  ＲＥＧＲＥＳＳＩＯＮ」）。また、本願は２０１３年１２月１９日に出願された次の国際出願の利益と優先権を主張する：第ＰＣＴ／ＵＳ  １３／７６３５３号（発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＣＯＵＮＴＩＮＧ」。また、２０１３年３月４日に出願された次の米国仮特許出願の利益と優先権を主張する：第６１／７７２４０４号（発明の名称「ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＬＩＮＥＡＲ  ＡＮＤ  ＲＩＤＧＥ  ＲＥＧＲＥＳＳＩＯＮ」）。これらの仮出願及び国際出願はすべての目的においてここに参照援用する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｂ．  Ｍｏｂａｓｈｅｒ，  Ｒ．  Ｂｕｒｋｅ，  Ｒ．  Ｂｈａｕｍｉｋ，  ａｎｄ  Ｃ．  Ｗｉｌｌｉａｍｓ著「Ｔｏｗａｒｄ  ｔｒｕｓｔｗｏｒｔｈｙ  ｒｅｃｏｍｍｅｎｄｅｒ  ｓｙｓｔｅｍｓ：  Ａｎ  ａｎａｌｙｓｉｓ  ｏｆ  ａｔｔａｃｋ  ｍｏｄｅｌｓ  ａｎｄ  ａｌｇｏｒｉｔｈｍ  ｒｏｂｕｓｔｎｅｓｓ」（ＡＣＭ  Ｔｒａｎｓ．  Ｉｎｔｅｒｎｅｔ  Ｔｅｃｈｎ．，  ７（４），  ２００７）
【非特許文献２】Ｅ．  Ａ‘ｉｍｅｕｒ，  Ｇ．  Ｂｒａｓｓａｒｄ，  Ｊ．  Ｍ．  Ｆｅｒｎａｎｄｅｚ，  ａｎｄ  Ｆ．  Ｓ．  Ｍ．  Ｏｎａｎａ著「ＡＬＡＭＢＩＣ：  Ａ  ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｒｅｃｏｍｍｅｎｄｅｒ  ｓｙｓｔｅｍ  ｆｏｒ  ｅｌｅｃｔｒｏｎｉｃ  ｃｏｍｍｅｒｃｅ」（Ｉｎｔ．  Ｊｏｕｒｎａｌ  Ｉｎｆ．  Ｓｅｃ，  ７（５），  ２００８）
【非特許文献３】Ａ．  Ｎａｒａｎｙａｎ  ａｎｄ  Ｖ．  Ｓｈｍａｔｉｋｏｖ著「Ｒｏｂｕｓｔ  ｄｅ−ａｎｏｎｙｍｉｚａｔｉｏｎ  ｏｆ  ｌａｒｇｅ  ｓｐａｒｓｅ  ｄａｔａｓｅｔｓ」（ＩＥＥＥ  Ｓ＆Ｐ，  ２００８）
【発明の概要】
【０００６】
本原理は、プライバシーを保護して、行列因子分解として知られる協調的フィルタリング手法に基づき、セキュアにリコメンデーションを提供する方法を提案する。具体的に、該方法は、ユーザがアイテム（例えば、映画、本）に与えたレーティングを入力として受け取り、各アイテムと各ユーザのプロファイルを生成する。そのプロファイルは、後で、ユーザが各アイテムにどんなレーティングを与えるか予測するのに利用できる。本原理により、行列因子分解に基づくリコメンダシステムは、ユーザのレーティング、ユーザがどのアイテムをレーティングしたか、アイテムプロファイル、又はユーザデータから抽出される任意の統計情報を学習することなく、このタスクを実行できる。特に、リコメンダシステムは、提供するリコメンデーションには完全にブラインドで、レーティングに貢献したユーザに、まだレーティングしていないアイテムをどのようにレーティングするかに対する予測の形式で、リコメンデーションを提供する。さらに、リコメンデーションシステムは、リッジ回帰を利用することにより、元の行列因数分解演算に参加していない新しいユーザにリコメンデーションを提供できる。
【０００７】
本原理の一態様により、行列因子分解とリッジ回帰とによりセキュアにリコメンデーションを生成する方法が提供される。該方法は、第１のレコードセット（２２０）を受信するステップであって、各レコードは、第１のユーザセット（２１０）中の各ユーザから受信され、トークンセットとアイテムセットとを含み、前記各ユーザ（３１５）以外のパーティには秘密にされる、ステップと、リコメンダ（ＲｅｃＳｙｓ）において第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いて行列因子分解に基づき前記第１のレコードセットを評価するステップ（２３０）であって、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ（３５５）の出力は前記第１のレコードセット中のすべてのアイテムのマスクされたアイテムプロファイルを含む、ステップと、少なくとも１つのアイテムについて要求ユーザからリコメンデーション要求を受信するステップ（３３０）と、前記要求ユーザが、第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いてリッジ回帰に基づき第２のレコードと前記マスクされたアイテムプロファイルとを評価するステップであって、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記少なくとも１つのアイテムに関するリコメンデーションを含み、前記リコメンデーションは前記要求ユーザのみにより知られる、ステップ（３８５）とを有する。本方法は、さらに、前記ＣＳＰ中の第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記第１のレコードセットに対して行列因子分解を行うように設計するステップ（３４０）であって、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセット中のすべてのアイテムのマスクされたアイテムプロファイルを含む、ステップと、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記ＲｅｃＳｙｓに転送するステップ（３４５）と、前記ＣＳＰ中の第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記第２のレコードと前記マスクされたアイテムプロファイルとにリッジ回帰を行うように設計するステップ（３６５）であって、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記少なくとも１つのアイテムに関するリコメンデーションを含む、ステップと、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記要求ユーザに転送するステップ（３７０）とをさらに有する。この方法の設計するステップは、行列因子分解演算をブーリアン回路として設計するステップ（３４０２）と、リッジ回帰演算をブーリアン回路として設計するステップ（３６５２）とを有する。行列因子分解回路を設計するステップは、前記第１のレコードセットのアレイを構成するステップと、前記アレイに対して、ソーティング（４２０、４４０、４７０、４９０）、コピー（４３０、４５０）、更新（４７０、４８０）、比較（４８０）、及び傾斜貢献の計算の動作（４６０）を実行するステップとを有する。本方法は、さらに、前記ＣＳＰが前記ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの設計用のパラメータセットを受信するステップであって、パラメータは前記ＲｅｃＳｙｓにより送信される、ステップ（３３５、３６０）をさらに有する。
【０００８】
本原理の一態様により、本方法は、さらに、前記第１のレコードセットを暗号化して暗号化レコードを生成するステップ（３１５）であって、暗号化は第１のレコードセットの受信前に行われる、ステップをさらに有する。本方法は、さらに、前記ＣＳＰにおいて公開暗号鍵を生成するステップと、前記鍵を前記各ユーザに送信するステップ（３１０）とをさらに有する。暗号スキームは部分的準同型暗号であってもよく（３１０）、本方法は、さらに、前記ＲｅｃＳｙｓにおいて前記暗号化されたレコードをマスクして、マスクされたレコードを生成するステップ（３２０）と、前記ＣＳＰにおいて、前記マスクされたレコードを復号して、マスクされ復号されたレコードを生成するステップ（３２５）とを有する。本方法の設計するステップ（３４０）は、さらに、前記マスクされ復号されたレコードを、処理する前に、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ内でアンマスクするステップを有する。本方法は、さらに、前記ＣＳＰと前記ＲｅｃＳｙｓとの間で（３５０２）ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うステップ（３５０）であって、前記ＲｅｃＳｙｓは前記マスクされ復号されたレコードのｇａｒｂｌｅｄ値を受け取り、前記レコードは前記ＲｅｃＳｙｓと前記ＣＳＰには秘密にしておかれる、ステップを有する。
【０００９】
本原理の一態様により、リッジ回帰回路を設計するステップ（３６５）は、前記要求ユーザから、マスクされたアイテムプロファイルと第２のレコードとを受信するステップ（３６５３）と、マスクされたアイテムプロファイルをアンマスクして、トークンと、アイテムと、アイテムプロファイルとのアレイを生成するステップであって、対応するアイテムプロファイルは前記第２のレコードからの各トークンとアイテムに加えられる、ステップ（３６５４）と、前記タプルアレイにリッジ回帰を行い、要求ユーザプロファイルを生成するステップ（３６５６）と、前記要求ユーザプロファイルと少なくとも１つのアイテムプロファイルからリコメンデーションを計算するステップ（３６５８）とを有する。リッジ回帰演算のためのアレイを生成するステップはソーティングネットワークを用いて実行してもよい（３６５４）。本方法は、さらに、前記要求ユーザ、ＣＳＰ及びＲｅｃＳｙｓの間で（３８０２）プロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うステップ（３８０）であって、前記要求ユーザは前記マスクされたアイテムプロファイルのｇａｒｂｌｅｄ値を受信し、前記マスクされたアイテムプロファイルは前記要求ユーザとＣＳＰには秘密にしておかれるステップをさらに有する。
【００１０】
本原理の一態様により、本方法は、さらに、各レコードのトークンとアイテムの数を受け取るステップ（２２０、３０５、３３０）をさらに有する。さらに、本方法は、各レコードのトークン数が最大値を表す値より小さいとき、トークン数が前記値と等しいレコードを生成するため、各レコードをヌルエントリでパディングするステップ（３０５２）をさらに有する。前記第１のレコードセットのソースはデータベースであり、前記第２のレコードのソースはデータベースである。
【００１１】
本原理の一態様により、行列因子分解とリッジ回帰とによりセキュアにリコメンデーションを生成するシステムが提供される。該システムは、第１のレコードセットを提供する第１のユーザセットと、セキュアな行列因子分解とリッジ回帰回路を提供する暗号サービスプロバイダ（ＣＳＰ）と、行列因子分解を評価するＲｅｃＳｙｓと、第２のレコードを提供し、前記リッジ回帰回路を評価し、各レコードがそのユーザ以外のパーティには秘密にしておかれるようにする、要求ユーザとを有し、ユーザ、ＣＳＰ及びＲｅｃＳｙｓはそれぞれ、少なくとも１つの入出力（６０４）を受けるプロセッサ（６０２）と、前記プロセッサと信号通信する少なくとも１つのメモリ（６０６、６０８）と、前記ＲｅｃＳｙｓプロセッサは、第１のユーザセットから第１のレコードセットを受信し、各レコードは、トークンセットとアイテムセットとを含み、前記各ユーザ以外のパーティには秘密にされ、要求ユーザから、少なくとも１つのアイテムを求める要求を受信し、第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いて行列因子分解に基づき前記第１のレコードセットを評価し、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセット中のすべてのアイテムのマスクされたアイテムプロファイルを含み、前記要求ユーザのプロセッサは、第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いてリッジ回帰に基づき第２のレコードと前記マスクされたアイテムプロファイルとを評価し、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記少なくとも１つのアイテムに関するリコメンデーションを含み、前記リコメンデーションは前記要求ユーザのみにより知られる、ように構成され得る。前記ＣＳＰプロセッサは、第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記第１のレコードセットに対して行列因子分解を行うように設計し、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセット中のすべてのアイテムのマスクされたアイテムプロファイルを含み、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記ＲｅｃＳｙｓに転送し、第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記第２のレコードと前記マスクされたアイテムプロファイルとにリッジ回帰を行うように設計し、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記少なくとも１つのアイテムに関するリコメンデーションを含み、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを前記要求ユーザに転送するように構成されている。本システムのＣＳＰプロセッサは、行列因子分解演算をブーリアン回路として設計し、リッジ回帰演算をブーリアン回路として設計するように構成されていることにより、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計するように構成し得る。前記ＣＳＰプロセッサは、前記第１のレコードセットのアレイを構成するように構成されていることにより、前記行列因子分解回路を設計するように構成し得る。前記アレイにおけるソーティング、コピー、交信、比較及び傾斜貢献の計算の動作を行う本システムのＣＳＰプロセッサは、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの設計のパラメータセットを受信するようにさらに構成され、パラメータは前記ＲｅｃＳｙｓにより送信されたものである。
【００１２】
本原理の一態様により、前記第１のユーザセットの各ユーザプロセッサは、各レコードを暗号化して、前記レコードを提供する前に、暗号化したレコードを生成するように構成され得る。本システムのＣＳＰプロセッサは、  前記ＣＳＰにおいて公開暗号鍵を生成し、前記鍵を前記第１のユーザセットに送信するように構成され得る。暗号化スキームは部分的準同型暗号であってもよく、ＲｅｃＳｙｓプロセッサは、暗号化されたレコードをマスクして、マスクされたレコードを生成するようにさらに構成されてもよく、前記ＣＳＰプロセッサは、マスクされたレコードを復号して、マスクされ復号されたレコードを生成するようにさらに構成されてもよい。本システムのＣＳＰプロセッサは、
前記マスクされ復号されたレコードを、処理する前に、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ内でアンマスクするようにさらに構成されていることにより、第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計するように構成し得る。本システムのＲｅｃＳｙｓプロセッサとＣＳＰプロセッサは、ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを実行するようにさらに構成されてもよく、ＲｅｃＳｙｓはマスクされ復号されたレコードのｇａｒｂｌｅｄ値を受信し、レコードはＲｅｃＳｙｓとＣＳＰには秘密にしておかれる。本システムのＣＳＰプロセッサは、
前記要求ユーザから、マスクされたアイテムプロファイルと第２のレコードとを受信し、マスクされたアイテムプロファイルをアンマスクして、トークンと、アイテムと、アイテムプロファイルとのアレイを生成し、対応するアイテムプロファイルは前記第２のレコードからの各トークンとアイテムに加えられ、前記タプルアレイにリッジ回帰を行い、要求ユーザプロファイルを生成し、前記要求ユーザプロファイルと少なくとも１つのアイテムプロファイルからリコメンデーションを計算するように構成されていることにより、第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを設計するように構成し得る。本システムのＣＳＰプロセッサは、ソーティングネットワークを設計するように構成されていることにより、リッジ回帰演算のためのアレイを生成するように構成し得る。要求ユーザプロセッサ、ＲｅｃＳｙｓプロセッサ及びＣＳＰプロセッサは、プロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを実行するようにさらに構成でき、要求ユーザはマスクされたアイテムプロファイルのｇａｒｂｌｅｄ値を受信し、マスクされたアイテムプロファイルは要求ユーザとＣＳＰには秘密にしておかれる。
【００１３】
本原理の一態様により、前記ＲｅｃＳｙｓプロセッサは、各レコードのトークン数を受信するようにさらに構成され、前記トークン数は各レコードのソースにより送信されたものである。前記第１のユーザセットの各プロセッサは、各レコードのトークン数が最大値を表す値より小さいとき、トークン数が前記値と等しいレコードを生成するため、各レコードをヌルエントリでパディングするように構成され得る。前記第１のレコードセットのソースはデータベースであり、前記第２のレコードのソースはデータベースである。
【００１４】
本原理の別のフィーチャ及び利点は、添付した図面を参照する実施形態の詳細な説明から明らかになる。
【図面の簡単な説明】
【００１５】
本原理は簡単に説明する以下の図面を参照してよりよく理解することができる。
【図１】先行技術によるリコメンデーションシステムのコンポーネントを示す図である。
【図２】本原理によるリコメンデーションシステムのコンポーネントを示す図である。
【図３Ａ】本原理によるプライバシー保護リコメンデーション方法を示すフローチャートを示す図である。
【図３Ｂ】本原理によるプライバシー保護リコメンデーション方法を示すフローチャートを示す図である。
【図３Ｃ】本原理によるプライバシー保護リコメンデーション方法を示すフローチャートを示す図である。
【図３Ｄ】は本原理によるプライバシー保護リコメンデーション方法を示すフローチャートを示す図である。
【図４Ａ】本原理による行列因子分解アルゴリズムを示す図である。
【図４Ｂ】本原理による行列因子分解アルゴリズムを示す図である。
【図４Ｃ】本原理による行列因子分解アルゴリズムを示す図である。
【図５】図５Ａ，Ｂは本原理による行列因子分解アルゴリズムにより構成されたデータ構造Ｓを示す図である。
【図６】本原理による実装に利用される計算環境を示すブロック図である。
【発明を実施するための形態】
【００１６】
本原理によると、プライバシー保護かつブラインドなやり方で、行列因子分解として知られる協調的フィルタリング手法に基づきリコメンデーションをセキュアに行う方法を提供する。
【００１７】
本原理の方法は、レコードのコーパス中のアイテムに関するリコメンデーションをするサービスとして機能し得る。各レコードはトークンとアイテムのセットを含む。レコードのセットは二以上のレコードを含み、トークンのセットは少なくとも１つのトークンを含む。当業者には言うまでもなく、上記の例においてレコードはユーザを表すこともあり、トークンはレコード中の対応するアイテムのユーザのレーティングであり得る。トークンはアイテムに関連するランク、加重又はものさし（ｍｅａｓｕｒｅｓ）を表してもよいし、アイテムは人、タスク又はジョブを表しても良い。例えば、ランク、加重又は尺度は個人の健康に関連していてもよいし、研究者は人々の健康尺度の相関をとることを試みている。それらは、個人の生産性と関連づけることもでき、企業はあるジョブのスケジュールを事前の履歴に基づいて予測しようと試みている。しかし、関係する個人のプライバシーを確保するため、サービスは、各レコードの内容、それが提供するアイテムプロファイル、又はユーザデータ（レコード）から抽出される統計的情報について学習することなく、ブラインドでそうしたいと願っている。具体的に、サービスは、（ａ）各トークン／アイテムがどのレコードに現れるか、またはもっと強い理由から（ｂ）各レコード中にどのトークン／アイテムが現れるか、（ｃ）トークンの値、及び（ｄ）ユーザデータから抽出されたアイテムプロファイルまたは統計的情報を学習すべきではない。さらに、サービスは、リッジ回帰を利用することにより、元の行列因子分解演算に参加していない新しいユーザにリコメンデーションを提供できる。以下、「プライバシー保護（ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ）」、「プライベート」及び「セキュア（ｓｅｃｕｒｅ）」などの用語は互換的に用い、ユーザがプライベートだと考えている情報（レコード）がユーザのみに知られていることを示し、「ブラインド（ｂｌｉｎｄ）」との用語はユーザ以外のパーティがリコメンデーションについて知らない（ｂｌｉｎｄ）ことを示す。
【００１８】
プライバシー保護の方法における行列因子分解の実行に関連する幾つかの問題がある。第１の、プライバシー問題を解決するため、行列因子分解はリコメンダがユーザのレーティングや、ユーザがどのアイテムをレーティングしたかを学習せずに実行されなければならない。後者の要請が重要である：初期の研究で、ユーザがどの映画をレーティングしたかを知るだけでそのジェンダーなどを推論するのに用いられることが分かっている。第２に、かかるプライバシー保護アルゴリズムは効率的でなければならず、ユーザによりなされるレーティングの数とともに素直に（ｇｒａｃｅｆｕｌｌｙ）（例えば、リニアに）スケールしなければならない。プライバシー要件は、行列因子分解アルゴリズムがデータｏｂｌｉｖｉｏｕｓ（ｄａｔａ−ｏｂｌｉｖｉｏｕｓ）、すなわちその実行がユーザ入力に依存してはならないことを示唆している。さらに、行列因数分解により行われる演算は非線形である。すなわち、これらの両制約下においてどのように行列因数分解を効率的に実装するかアプリオリには明らかではない。最後に、実際の実世界のシナリオでは、ユーザは、限られた通信及び計算のリソースしか有しておらず、自分のデータを供給した後にはオンラインに留まると期待すべきではない。それよりも、リコメンデーションサービスに対してオンラインとオフラインを行ったり来たりするユーザがいるときに動作可能である「送信して忘れる（ｓｅｎｄ  ａｎｄ  ｆｏｒｇｅｔ）」タイプのソリューションが望ましい。
【００１９】
行列因子分解の概要として、標準的な「協調的フィルタリング」設定では、ｎ人のユーザがｍ個のアイテム（例えば、映画）のサブセットをレーティングする。［ｎ］：＝｛１，．．．，ｎ｝をユーザのセット、［ｍ］：＝｛１，．．．，ｍ｝をアイテムのセットと、レーティングが生成されたユーザ／アイテムのペアをＭ⊆［ｎ］ｘ［ｍ］とし、レーティングの総数をＭ＝［Ｍ］とする。最後に、（ｉ，ｊ）∈Ｍについて、ユーザｉによりアイテムｊに対して生成されたレーティングをｒｉ，ｊ∈Ｒで表す。現実的な設定では、ｎとｍは大きな数であり、一般的には１０４と１０６の間の範囲にある。また、提供されるレーティングはわずかであり、すなわち、Ｍ＝Ｏ（ｎ＋ｍ）であり、これは潜在的レーティングの総数ｎ×ｍよりずっと小さい。これは一般的なユーザの振るまいと一貫性がある。各ユーザは、（「カタログ」サイズｍには依らず）有限数のアイテムのみをレーティングするからである。
【００２０】
Ｍ中のレーティングが与えられると、リコメンダシステムは［ｎ］×［ｍ］＼Ｍ中のユーザ／アイテムペアのレーティングを予測したい。行列因子分解は、既存のレーティングに対してバイリニアモデルをフィッティングすることにより、このタスクを実行する。具体的に、小さな次元ｄ∈Ｎの場合、
【数１】
2016510913.tif 000003
となるベクトルｕｉ∈Ｒｄ、ｉ∈［ｎ］かつｖｊ∈Ｒｄ、ｊ∈［ｍ］があると仮定する。ここでεｉ，ｊは、独立かつ同じ分布を有する（ｉｎｄｅｐｅｎｄｅｎｔ  ａｎｄ  ｉｄｅｎｔｉｃａｌｌｙ  ｄｉｓｔｒｉｂｕｔｅｄ）ガウシアンランダム変数である。ベクトルｕｉとｖｊはそれぞれユーザプロファイルとアイテムプロファイルと呼ばれ、＜ｕｉ，ｖｊ＞はベクトルの内積である。用いた記法は、第ｉ行がユーザｉのプロファイルを含むｎ×ｄ行列の
［外１］
2016510913.tif 000004
と、第ｊ行がアイテムｊのプロファイルを含むｍ×ｄ行列の
［外２］
2016510913.tif 000005
である。
【００２１】
レーティング
［外３］
2016510913.tif 000006
が与えられると、リコメンダは一般的に、λ、μ＞０として、
【数２】
2016510913.tif 000007
の規格化最小二乗最小化を実行して、プロファイルＵとＶを計算する。当業者には言うまでもないが、プロファイルＵとＶのガウシアンプライア（Ｇａｕｓｓｉａｎ  ｐｒｉｏｒｓ）を仮定すると、式（２）の最小化はＵとＶの最大尤度推定に対応する。留意点として、ユーザプロファイルとアイテムプロファイルがあれば、リコメンダは、ユーザｉとアイテムｊに対して、
【数３】
2016510913.tif 000008
のようにレーティング
［外４］
2016510913.tif 000009
を予測できる。
【００２２】
式（２）の規格化された平均二乗誤差は凸関数ではない。この最小化を実行する複数の方法が文献で提案されている。本原理は、よく使われる方法である傾斜降下にフォーカスし、以下に説明する。式（２）の規格化された平均二乗誤差をＦ（Ｕ，Ｖ）と記すと、傾斜降下は適応規則によりプロファイルＵとＶを反復的に適応させることにより動作する：
【数４】
2016510913.tif 000010
ここでγ＞０は小さい利得係数であり、
【数５】
2016510913.tif 000011
ここでＵ（０）とＶ（０）は一様ランダムノルム１行（ｕｎｉｆｏｒｍｌｙ  ｒａｎｄｏｍ  ｎｏｒｍ  １  ｒｏｗｓ）よりなる（すなわち、プロファイルはノルム１ボールから一様にランダムに（ｕｎｉｆｏｒｍｌｙ  ａｔ  ｒａｎｄｏｍ）選択される）。
【００２３】
本原理の他の一態様は、ソートネットワークとＹａｏのｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔｓに基づく行列因子分解のためのセキュアなマルチパーティ計算（ＭＰＣ）アルゴリズムを提案することである。セキュアマルチパーティ計算（ＭＰＣ）は１９８０年代にＡ．Ｃｈｉ−Ｃｈｉｈ  Ｙａｏにより初めて提案された。Ｙａｏのプロトコル（ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔｓとしても知られている）はセキュアマルチパーティ計算の一般的な方法である。Ｖ．  Ｎｉｋｏｌａｅｎｋｏ，  Ｕ．  Ｗｅｉｎｓｂｅｒｇ，  Ｓ．  Ｉｏａｎｎｉｄｉｓ，  Ｍ．  Ｊｏｙｅ，  Ｄ．  Ｂｏｎｅｈ，  及びＮ．  Ｔａｆｔによる「Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  Ｒｉｄｇｅ  Ｒｅｇｒｅｓｓｉｏｎ  ｏｎ  Ｈｕｎｄｒｅｄｓ  ｏｆ  ｍｉｌｌｉｏｎｓ  ｏｆ  ｒｅｃｏｒｄｓ」（ＩＥＥＥ  Ｓ＆Ｐ，  ２０１３）から翻案したその変形例において、プロトコルはｎ人の入力オーナーのセット（ここで、ａｉはユーザｉ、１≦ｉ≦ｎ、のプライベート入力を示す）と、ｆ（ａ１，．．．，ａｎ）の評価を望むエバリュエータと、サードパーティである暗号サービスプロバイダ（ＣＳＰ）の間で行われる。プロトコルの終わりには、エバリュエータはｆ（ａ１，．．．，ａｎ）の値を学習するが、どのパーティもこの出力値から分かることよりも多くのものは学習しない。このプロトコルでは、関数ｆがブール回路として、例えばＯＲ、ＡＮＤ、ＮＯＴ及びＸＯＲゲートのグラフとして表せることが必要であり、エバリュエータとＣＳＰが共謀しないことが必要である。
【００２４】
最近ではＹａｏのｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔｓを実装する多くのフレームワークがある。汎用ＭＰＣに対する異なる１つのアプローチは秘密共有方式に基づき、他の１つのアプローチは完全準同形暗号（ＦＨＥ）に基づく。秘密共有方式は、線形系、線形回帰、オークションの解法などさまざまな線形代数演算について提案されている。秘密共有は、計算の負荷を等しく共有し複数ラウンドで通信する少なくとも３つの共謀しないオンラインオーソリティが必要であり、計算はそれらのうち２つが共謀しない限りセキュアである。ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔｓは、２つの共謀していないオーソリティとずっと少ない通信しか仮定しないので、エバリュエータがクラウドサービスであり暗号サービスプロバイダ（ＣＳＰ）がトラステッドハードウェアコンポーネント（ｔｒｕｓｔｅｄ  ｈａｒｄｗａｒｅ  ｃｏｍｐｏｎｅｎｔ）に実装されたシナリオにより適している。
【００２５】
使用する暗号プリミティブに関わらず、セキュアマルチパーティ計算のための効率的なアルゴリズムを構成する場合の主要な問題は、アルゴリズムをデータｏｂｌｉｖｉｏｕｓな方法（ｄａｔａ−ｏｂｌｉｖｉｏｕｓ  ｆａｓｈｉｏｎ）で実装し、すなわち実行パスが入力に依存しないようにする点にある。一般的に、制限された時間Ｔ内に実行できるＲＡＭプログラムはＯ（Ｔ＾３）チューリングマシン（ＴＭ）に変換できる。これはアランチューリングにより考案された、数学的計算の理想的モデルとして機能する理論的計算機であり、Ｏ（Ｔ＾３）は複雑性がＴ３に比例することを意味する。また、制限されたＴ時間ＴＭはどれでもサイズＯ（Ｔ＾３）の回路に変換でき、これはデータｏｂｌｉｖｉｏｕｓ（ｄａｔａ−ｏｂｌｉｖｉｏｕｓ）である。これは、どの制限されたＴ時間実行可能ＲＡＭプログラムであっても、Ｏ（Ｔ＾３  ｌｏｇＴ）の複雑性を有するデータｏｂｌｉｖｉｏｕｓ回路に変換できることを示唆している。かかる複雑性は高すぎ、ほとんどのアプリケーションでは法外に高すぎる。効率的なデータｏｂｌｉｖｉｏｕｓな実装が知られていないアルゴリズムに関する調査は、Ｗ．  Ｄｕ  ａｎｄ  Ｍ．  Ｊ．  Ａｔａｌｌａｈによる文献「Ｓｅｃｕｒｅ  ｍｕｌｔｉ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｐｒｏｂｌｅｍｓ  ａｎｄ  ｔｈｅｉｒ  ａｐｐｌｉｃａｔｉｏｎｓ：  Ａ  ｒｅｖｉｅｗ  ａｎｄ  ｏｐｅｎ  ｐｒｏｂｌｅｍｓ」（Ｎｅｗ  Ｓｅｃｕｒｉｔｙ  Ｐａｒａｄｉｇｍｓ  Ｗｏｒｋｓｈｏｐ，  ２００１）に記載されている。行列因子分解問題は広い意味でデータマイニング要約問題のカテゴリーに入る。
【００２６】
ソーティングネットワークは当初ソーティングの並列化及びハードウェア実装の効率化を可能にするため開発された。これらのネットワークは、入力シーケンス（ａ１，ａ２，・・・，ａｎ）を単調増加シーケンス（ａ’１，ａ’２，・・・，ａ’ｎ）にソートする回路である。これは、主要構成ブロックである比較・スワップ回路を配線することにより構成されている。幾つかの業績は、暗号化目的のためにソーティングネットワークのデータｏｂｌｉｖｉｏｕｓ性（ｄａｔａ−ｏｂｌｉｖｉｏｕｓｎｅｓｓ）を利用している。しかし、暗号化はプライバシーを確保するには必ずしも十分ではない。敵対者は、暗号化ストレージに対するあなたのアクセスパターンを見ることができれば、あなたのアプリケーションが何をしているかに関するセンシティブな情報を知ることができる。ｏｂｌｉｖｉｏｕｓ  ＲＡＭは、アクセスされた時にメモリを継続的にシャッフルし、どのデータがアクセスされたか、又はそれが以前いつアクセスされたかを完全に隠すことにより、この問題を解決する。ｏｂｌｉｖｉｏｕｓ  ＲＡＭにおいて、データｏｂｌｉｖｉｏｕｓランダム置換をする手段としてソーティングを用いる。最近では、ｏｂｌｉｖｉｏｕｓ  ＲＡＭは凸包、全最近傍、及び加重積集合のデータｏｂｌｉｖｉｏｕｓ計算を実行するのに使われている。
【００２７】
本原理の他の一態様は、当初、行列因子分解演算に参加していない新しいユーザにリコメンデーションを提供するために、リコメンデーションシステムがリッジ回帰を利用することである。リッジ回帰は、多数のデータポイントを入力として取り、これらのポイントを通るベストフィットする曲線を見つけるアルゴリズムである。このアルゴリズムは多くの機械学習アルゴリズムの構成ブロックである。米国仮特許出願第６１／７７２４０４号に説明されているように、ｎ個の入力変数ｘｉ∈Ｒｄのセットと出力変数ｙｉ∈Ｒのセットが与えられると、ｙｉ＝ｆ（ｘｉ）であると関数ｆ：Ｒｄ→Ｒを学習する問題は回帰として知られている。
【００２８】
線形回帰は、ｆが線形写像によりよく近似できる、すなわち幾つかのβ∈Ｒｄに対して、
【数６】
2016510913.tif 000012
となるとの前提に基づく。ここで（・）Ｔは転置演算を示す。
【００２９】
ベクトルβ＝（βｋ）ｋ＝１，．．．，ｄは、予測に使うほか、ｙが入力変数にどう依存するか示す点に興味がある。具体的に、係数βｋは出力に対して正負どちらか相関を示し、大きさは相対的な需要性を捉える。これらの係数が比較可能であり、数値的に安定していることを保証するため、入力ｘｉを同じ有限領域（例えば、［−１，１］）にリスケールする。
【００３０】
ベクトルβ∈Ｒｄを計算するため、次の二次関数
【数７】
2016510913.tif 000013
をＲｄにわたり最小化することにより、後者をデータにフィットする。
【００３１】
式（７）を最小化する手順はリッジ回帰と呼ばれている。目的関数Ｆ（β）はペナルティ項
［外５］
2016510913.tif 000014
を含む。これはｐａｒｓｉｍｏｎｉｏｕｓな解を好む。直感的には、λ＝０の場合、最小化は単純な最小二乗問題を解くことに相当する。λ＞０の場合、ペナルティ項はノルムが大きい解にペナルティを与える。同じようにデータフィットする２つの解のうち、大きい係数が少ないものが好ましい。
【００３２】
本原理は、加重積集合に近いがｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔｓを含むセキュアマルチパーティソーティングに基づく方法を提案する。図２は、本原理によるプライバシー保護リコメンデーションシステムの動作を示す。動作は次の通りである：
Ｉ．リコメンデーションシステム（ＲｅｃＳｙｓ）２３０、ブラインドプライバシー保護行列因子分解演算を実行する装置。具体的に、ＲｅｃＳｙｓは、ユーザに関する有用な事（ユーザがどの映画をレーティングしたか、どんなレートにしたか、またはユーザデータから得られるリコメンデーションを含む統計情報（平均、アイテムプロファイルなど））を学習せずに、ユーザのレーティングに対する行列因子分解から抽出したアイテムプロファイルＶをブラインドで計算する。
ＩＩ．暗号サービスプロバイダ（ＣＳＰ）２５０。これは、どの映画をレーティングしたか、どんなレーティングにしたか、またはリコメンデーションを含むユーザデータから抽出された任意の統計情報（平均、アイテムプロファイルなど）を含む、ユーザに関する有用な事を学習せずにセキュアな計算を可能とする。
ＩＩＩ．各々がアイテムのセット２２０に対するレーティングのセットを有するユーザのセットＡを含む一以上のユーザ２１０よりなるソースＡ。各ユーザｉ∈［ｎ］は、行列因子分解による自分のレーティングｒｉ，ｊ：（ｉ，ｊ）∈Ｍに基づくアイテムのプロファイリングに同意するが、リコメンダには自分のレーティング、どのアイテムをレーティングしたか、及びユーザデータから抽出されるどんな統計情報（平均、アイテムプロファイルなど）も含めて何も開示することを望まない。これらのユーザはリコメンデーションを受けることを望む者もいるし望まない者もいる。例えば、リコメンデーションシステムはユーザのデータに対してお金を払っても良い。同様に、ソースＡは一以上のユーザＡのデータを含むデータベースを表していても良い。
ＩＶ．各々がアイテムのセットに対するレーティングのセットを有し、他人がアイテムをどうレーティングするかの予測の形式のリコメンデーションを受け取ることを望む、ユーザのセットＢ  ２１０４を含む一以上のユーザ２１０よりなるソースＢ。各ユーザは、自分のレーティング、どのアイテムをレーティングしたか、及びユーザデータから抽出されるすべての統計情報（平均、アイテムプロファイルなど）を含め、リコメンダに何も開示したくない。セットＢはセットＡと重なっても重ならなくてもよい。すなわち、リコメンデーションを得たいと思うユーザは行列因子分解演算に参加してもしなくてもよい。よって、セットＡとセットＢは互いに素であってもなくてもよい。同様に、ソースＢは一以上のユーザＢのデータを含むデータベースを表していても良い。
【００３３】
本原理によると、ＲｅｃＳｙｓが行列因子分解を実行でき、一方ＲｅｃＳｙｓもＣＳＰもリコメンデーションＲを含め、ユーザに関する有用なことは学習しないようにするプロトコルが提案される。具体的に、どちらもユーザのレーティング、ユーザがどのアイテムをレーティングしたか学習せず、どちらもアイテムプロファイルＶ、ユーザプロファイルＵ、リコメンデーション、またはユーザデータから抽出した統計情報を学習すべきではない。当業者には明らかであるが、リコメンダがユーザ及びアイテムのプロファイルを両方とも学習できるプロトコルは、公開しすぎる。かかる設計では、リコメンダは式（３）の内積からユーザのレーティングを簡単に推論できる。そのように、本原理は、リコメンダとＣＳＰがユーザプロファイル、アイテムプロファイル、又はユーザデータから抽出される統計的情報を学習しないプライバシー保護プロトコルを提案する。要約すると、これらは完全にブラインド（ｂｌｉｎｄ）で動作を実行し、ユーザに関する又はユーザデータから抽出された有用な情報を学習しない。
【００３４】
アイテムプロファイルは、ユーザ／レコードのセットのレーティングの関数としてアイテムを定義するメトリック（ｍｅｔｒｉｃ）として見なすことができる。同様に、ユーザプロファイルは、ユーザ／レコードのセットのレーティングの関数としてユーザを定義するメトリック（ｍｅｔｒｉｃ）として見なすことができる。この意味で、アイテムプロファイルはアイテムの承認／非承認のものさし（ｍｅａｓｕｒｅ）である。ユーザプロファイルは、ユーザの好き嫌いのものさし、すなわちユーザのパーソナリティの反映である。ユーザ／レコードの大きなセットに基づき計算するとき、アイテムまたはユーザのプロファイルはそれぞれアイテムまたはユーザの独立なものさし（ｍｅａｓｕｒｅ）と考えることができる。当業者は、アイテムプロファイルのみを学習する有用性があることに気づくだろう。第１に、行列因子分解によるアイテムのＲｄへの組み込みにより、リコメンダは類似性を推論（及びエンコード）できる：プロファイルのユークリッド距離が小さいアイテムは、ユーザにより同様にレーティングされるアイテムである。そのため、アイテムプロファイルを学習するタスクは、リコメンダにとって実際のリコメンデーションのタスクよりも関心がある。具体的に、ソースがデータベースである場合のように、ユーザはリコメンデーションを受けることを必要としないまたは望まないことがある。第２に、アイテムプロファイルを取得すると、トリビア（ｔｒｉｖｉａ）がある：リコメンダは、ユーザから追加的データの開示を受けなくても、それを用いて関連するリコメンデーションを提供できる。リコメンダはユーザにＶを送る（又はそれを公開する）；ユーザｉは、自分のアイテム毎のレーティングを知っているので、式（２）をｕｉについて解いて自分の（プライベートな）プロファイルｕｉを推論できる；Ｖが与えられると（これは別の問題である）、各ユーザは自分のレーティングにリッジ回帰を行うことにより、自分のプロファイルを得られる。ｕｉとＶがあれば、ユーザは、式（４）によりローカルで他のアイテムに対する自分のレーティングを予測できる。
【００３５】
上記のシナリオは両方とも、リコメンダもユーザもＶの公開（ｐｕｂｌｉｃ  ｒｅｌｅａｓｅ）に反対しないことを前提とする。単純化のため、及びリコメンダに対するかかるプロトコルの有用性の理由で、本願と同日に出願した本発明者による、発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＲＴＩＯＮ」である同時係属中の出願によりリコメンダはアイテムプロファイルを学習できる。本原理は、リコメンダはブラインドで演算を行い、ユーザに関する有用な情報を（Ｖさえも）学習しないが、ユーザが自分の予測レーティングを学習するように、かつ行列因子分解にレーティングを提供しなかったユーザがリコメンデーションを得られるように、このデザインを拡張する。
【００３６】
本原理によれば、セキュリティ保証は正直だが興味深いスレットモデル（ｔｈｒｅａｔ  ｍｏｄｅｌ）の下で成り立つ。言い換えると、ＲｅｃＳｙｓとＣＳＰは上記の通りプロトコルに従う。しかし、これらの興味を有するパーティは、追加の情報を推論するため、オフラインであっても、プロトコルトランスクリプトを分析することを選ぶ。さらに、リコメンダとＣＳＰは共謀しないと仮定する。
【００３７】
本原理の好ましい実施形態は、図３のフローチャート３００を満たし、次のステップにより記述されるプロトコルを有する：
Ｐ１．ソースＡはＲｅｃＳｙｓに、トークン（レーティング）とアイテムのいくつのペアが各参加レコード３０５に送られるか、レポートする。レコードのセットは二以上のレコードを含み、レコードごとのトークンのセットは少なくとも１つのトークンを含む。ソースがユーザのセットであるとき、各ユーザは自分のトークンとアイテムの数をＲｅｃＳｙｓに個別にレポートする。
Ｐ２．ＣＳＰは部分的準同型スキームξの公開暗号鍵を生成し、それをすべてのユーザ（ソースＡ）に送る（ステップ３１０）。当業者には言うまでもなく、準同型暗号は、暗号の一形式であり、これにより、暗号文に対してあるタイプの計算を実行して暗号化された結果を求め、平文に対して行った演算の結果と一致させることができる。例えば、どちらの人も個別の数字を見いだすことができなくても、ある人は２つの暗号化数字を加え、他の人はその結果を復号できる。部分的準同型暗号は平文に対する１つの演算（加算又は乗算）に関しては準同型である。部分的準同型暗号はスカラーへの加算及び乗算に関しては準同型である。ソースＡがユーザのセットであるとき、各ユーザは自分のトークンとアイテムの数をＲｅｃＳｙｓに個別にレポートする。
Ｐ３．セットＡ中の各ユーザは自分の鍵を用いて自分のデータを暗号化する（３１５）。具体的に、すべてのペア（ｊ，ｒｉ，ｊ）について、ここでｊはアイテムｉｄであり、ｒｉ，ｊはユーザｉがｊに与えたレーティングであり、ユーザは公開暗号鍵を用いてこのペアを暗号化する。セットＡ中の各ユーザは、自分の暗号化データをＲｅｃＳｙｓに送る。
Ｐ４．ＲｅｃＳｙｓは、暗号化データにマスクηを加え、暗号化されマスクされたデータをＣＳＰに送る（３２０）。当業者には言うまでもなく、マスクはデータ難読化の一形式であり、乱数生成器やシャッフリングと同じくらい単純でよい。
Ｐ５．ＣＳＰは暗号化しマスクしたデータを復号する（３２５）。
Ｐ６．ＲｅｃＳｙｓは、すべてのアイテムのコーパス中の少なくとも一アイテムについて、少なくとも一要求ユーザからリコメンデーション要求を受け取る（３３０）。各要求ユーザはセットＢに属し、ステップＰ１の貢献レコードを有しても有しなくてもよい。リコメンデーションを要求する要求ユーザがセットＡからのものであれば、本願と同日に出願され、発明の名称が「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＴＯ  ＲＡＴＩＮＧ  ＣＯＮＴＲＩＢＵＴＩＮＧ  ＵＳＥＲＳ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」である本発明者による同時係属中の出願に記載したように別のプロトコルを使える。各要求ユーザは、いくつのアイテムをレーティングしたか、ＲｅｃＳｙｓにレポートする。
Ｐ７．ＲｅｃＳｙｓは、ＣＳＰに、ユーザとアイテムプロファイルの大きさ（すなわち、パラメータｄ）、レーティングの総数（すなわち、パラメータＭ）、セットＡ中のユーザの総数とアイテムの総数、及びｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ中の実数の整数及び少数部分を表すのに用いられるビット数を含む、第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを構成するのに必要な完全な仕様を送る（３３５）。
Ｐ８．ＣＳＰは、レコードに対して行列因子分解を行う、当業者にｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔとして知られたものを準備する（３４０）。ｇａｒｂｌｅｄであるために、回路はまずブーリアン回路として書かれる（３４０２）。回路への入力は、ＲｅｃＳｙｓがユーザデータをマスクするのに用いたマスクを含む。回路内において、マスクはデータをアンマスク（ｕｎｍａｓｋ）し、次いで行列因子分解するのに用いられる。回路の出力はＶ、すなわちアイテムプロファイルである。ＣＳＰは、アイテムｊごとに１つ、ランダムマスクρｊを選択する。これらは各アイテムｊのプロファイルを隠すのに用いられる。回路は、平文にアイテムプロファイルＶを出力するのではなく、ＣＳＰにより構成された回路はマスクｐｊでマスクされたアイテムプロファイルＶｊを出力する。個別レコードの内容及びレコードから抽出された情報に関する知識は得られない。
Ｐ９．ＣＳＰはＲｅｃＳｙｓに、行列因子分解のためｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを送る（３４５）。具体的に、ＣＳＰは、ｇａｒｂｌｅｄテーブルへのゲートを処理して、それを回路構造により決まる順番でＲｅｃＳｙｓに送信する。
Ｐ１０．ＲｅｃＳｙｓとＣＳＰとの間の（３５０２）ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒ（３５０）により、ＲｅｃＳｙｓは自機またはＣＳＰが実際の値を学習せずに、暗号化されマスクされたレコードのｇａｒｂｌｅｄ値を学習する。当業者には言うまでもなく、普通の（ｐｌａｉｎ）ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒは、送信者が潜在的に多くの情報のうちの一つを（どの情報が転送されたかについてｏｂｌｉｖｉｏｕｓでいる）受信者に転送する一種の転送である。プロキシ（ｐｒｏｘｙ）ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒは４以上のパーティが関与するｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒである。
Ｐ１１．ＲｅｃＳｙｓは、マスクされたアイテムプロファイルを出力し、それをＣＳＰに送るｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを評価する（３５５）。
Ｐ１２．ＲｅｃＳｙｓはＣＳＰに数Ｍｊを知らせ、第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの仕様を与える。ほとんどのパラメータは、ユーザ及びアイテムプロファイルの大きさ（すなわち、パラメータｄ）、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ中の実数の整数及び小数部を表すのに用いるビット数を含む、第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ中のパラメータを複製する（３６０）。
Ｐ１３．ＣＳＰは、要求ユーザのレーティングとマスクされたアイテムプロファイルにリッジ回帰を行いユーザが関心を有するアイテムのリコメンデーションを生成する第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを準備する（３６５）。ｇａｒｂｌｅｄであるために、回路はまずブーリアン回路として書かれる（３６５２）。この回路は次のタスクを実行する：
ａ．ユーザによりレーティングされた各アイテムｗについて、マスクされたアイテムプロファイルνｊ＋ρｊを入力として受け取り、要求ユーザｉからＭｊ個のレーティング（ｗ，ｒｉ，ｗ）を受け取る（３６５２）。
ｂ．アイテムプロファイルをアンマスクし、ユーザによりレーティングされた各アイテムｗについて、それをユーザｉのＭｊ個のペア（ｗ，ｒｊ，ｗ）のタプル（ｗ，ｒｊ，ｗ，νｗ）のアレイに入れる（３６５４）。これは次のステップにより実行される：
ｉ．ユーザによりレーティングされた各アイテムｗについて、ユーザｉのＭｊ個のすべてのペア（ｗ，ｒｊ，ｗ）に次いで、アンマスクされたすべてのアイテムプロファイルνｊをアレイに入れる。
ｉｉ．ソーティングネットワークを用いて、アイテムプロファイルに関してこのアレイをソートする。その際、ソーティングの終わりに、各ペア（ｗ，ｒｊ，ｗ）の次に、それが対応するプロファイルνｗが来るようにする。
ｉｉｉ．回路は、右から左にリニアパスを行い、各アイテムのアンマスクされたプロファイルνｗをそれが対応するタプル（ｗ，ｒｊ，ｗ）にコピーする。
ｉｖ．ソーティングネットワークを用いて、回路は、これらのレーティングタプルをアイテムプロファイルから分離し、レーティングが、コピーされたアイテムプロファイルと共に、アレイの第１のＭｊ個のポジションを占めるようにする。
ｃ．回路は、次いで、レーティングとそのアイテムプロファイルに対してリッジ回帰を行い、必要な代入をすることにより式（７）から導かれる
【数８】
2016510913.tif 000015
の解であるユーザプロファイルｕｉを計算する（３６５６）。これは、米国仮特許出願第６１／７７２４０４に記載されたように、リッジ回帰を行う回路を用いて計算できる。
ｄ．このプロファイルｕｉとアンマスクされたアイテムプロファイルνｊとを用いて、回路は、すべての関心アイテムｊの予測レーティング
［外６］
2016510913.tif 000016
を計算し、これらの予測を出力する（３６５８）。
Ｐ１４．ＣＳＰは、セットＢの要求ユーザｉにこの回路を転送する（３７０）。
Ｐ１５．要求ユーザｉとＣＳＰとの間のｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒ３７５により（３７５２）、ユーザは自分の入力（ｊ，ｒｉ，ｊ）に対するｇａｒｂｌｅｄ値を取得する。
Ｐ１６．要求ユーザｉ、ＲｅｃＳｙｓ、及びＣＳＰの間のプロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒ３８０により、ユーザは、マスクされたアイテムプロファイルνｊ＋ρｊに対応するｇａｒｂｌｅｄ値を取得する。具体的に、このプロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒにおいて、ＲｅｃＳｙｓはマスクされたアイテムプロファイルを提供し、要求ユーザはマスクされたアイテムプロファイルのｇａｒｂｌｅｄ値を受け取り、ＣＳＰはプロキシとして動作する一方、どのパーティもアイテムプロファイルを学習せず、ＲｅｃＳｙｓのみがマスクされたアイテムプロファイルを知っている。
Ｐ１７．要求ユーザは回路を評価し、すべての関心アイテムの予測レーティングを出力として取得する（３８５）。
【００３８】
上記の構成は、セットＢのユーザ（セットＡに含まれても含まれなくてもよい、すなわち行列因子分解演算のため自分のレーティングを送信していてもいなくてもよい）に対してうまく行く。
【００３９】
技術的には、このプロトコルは各ユーザにより提供されたトークン数をリークする。これは簡単なプロトコル修正により、例えば、所定の最大数にいたるまで、適切な「ヌル（ｎｕｌｌ）」エントリーで送信されたレコードに「パディング（ｐａｄｄｉｎｇ）」することにより、直すことができる。単純化のため、プロトコルはこの「パディング」演算無しで説明した。
【００４０】
ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔは一度だけしか使えないので、同じレーティングに対するその後の計算は、ユーザがプロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを通して自分のデータを再送信する必要がある。この理由により、本原理のプロトコルは、公開鍵暗号をｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔと組み合わせるハイブリッドアプローチを取り入れた。
【００４１】
本原理では、公開鍵暗号を次のように用いる：各ユーザｉは、暗号アルゴリズムξｐｋＣＳＰを用いて公開鍵ｐｋＣＳＰの下で自分の各入力（ｊ，ｒｉ，ｊ）を暗号化し、レーティングされた各アイテムｊについて、ユーザはＲｅｃＳｙｓにペア（ｉ，ｃ）をｃ＝ξｐｋＣＳＰ（ｊ，ｒｉ，ｊ）とともに送信する。ここで、全部でＭ個のレーティングが送信される。自分のレーティングを送信したユーザはオフラインになれる。
【００４２】
ＣＳＰ公開鍵暗号アルゴリズムは部分的準同型（ｐａｒｔｉａｌｌｙ  ｈｏｍｏｍｏｒｐｈｉｃ）である：対応する暗号鍵を知らなくても定数を暗号メッセージに適用できる。明らかに、ＰａｉｌｌｉｅｒやＲｅｇｅｖなどの加法的準同型スキームを用いて定数を加算できるが、ｈａｓｈ−ＥｌＧａｍａｌは、部分的準同型であり、これで十分であり、この場合にはより効率的に実装できる。
【００４３】
ユーザからＭ個のレーティングを受け取ると、暗号化は部分的準同型（ｐａｒｔｉａｌｌｙ  ｈｏｍｏｍｏｒｐｈｉｃ）であることを思い出せば、ＲｅｃＳｙｓはそれをランダムマスク
［外７］
2016510913.tif 000017
で見えなくする。ここで、ηはランダム又は疑似ランダム変数であり、演算記号（○に十字）はＸＯＲ演算である。ＲｅｃＳｙｓはそれを、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを構成するのに必要な完全な仕様とともにＣＳＰに送る。具体的に、ＲｅｃＳｙｓは、ユーザ及びアイテムプロファイルの大きさ（ｄｉｍｅｎｓｉｏｎ）（すなわち、パラメータｄ）、レーティングの総数（すなわち、パラメータＭ）、及びユーザ及びアイテムの総数、並びにｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ中の実数の整数及び少数部分を表すのに用いるビット数を指定する。
【００４４】
ＲｅｃＳｙｓは、集積されたＭ個のレーティングに行列因子分解を行いたいたびに、ＭをＣＳＰにレポートする。ＣＳＰは、入力を復号するｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔをＲｅｃＳｙｓに提供し、次いで行列因子分解を行う。Ｖ．  Ｎｉｋｏｌａｅｎｋｏ，  Ｕ．  Ｗｅｉｎｓｂｅｒｇ，  Ｓ．  Ｉｏａｎｎｉｄｉｓ，  Ｍ．  Ｊｏｙｅ，  Ｄ．  Ｂｏｎｅｈ，  ａｎｄ  Ｎ．  Ｔａｆｔによる文献「Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｒｉｄｇｅ  ｒｅｇｒｅｓｓｉｏｎ  ｏｎ  ｈｕｎｄｒｅｄｓ  ｏｆ  ｍｉｌｌｉｏｎｓ  ｏｆ  ｒｅｃｏｒｄｓ」（ＩＥＥＥ  Ｓ＆Ｐ，  ２０１３）では、回路内での復号は、マスクと準同型暗号を用いることにより、回避されている。本原理は行列因子分解についてのこのアイデアを利用するが、部分的準同型暗号スキーム（ｐａｒｔｉａｌｌｙ  ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅ）のみを必要とする。
【００４５】
暗号を受け取ると、ＣＳＰはそれを復号し、マスクされた値
［外８］
2016510913.tif 000018
を得る。次いで、行列因子分解を青写真として用いて、ＣＳＰはＹａｏのｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを準備する。これは、
（ａ）マスクηに対応するｇａｒｂｌｅｄ値を入力として取る；
（ｂ）マスクηを取り除き、対応するタプル（ｉ，ｊ，ｒｉ，ｊ）を回復する；
（ｃ）行列因子分解を行う；及び
（ｄ）
［外９］
2016510913.tif 000019
でマスクされたアイテムプロファイル
［外１０］
2016510913.tif 000020
を出力する。
【００４６】
式（４）と（５）で概説した傾斜降下演算による行列因子分解の計算は、実数の加算、減算及び乗算を含む。これらの演算は回路で効率的に実装できる。傾斜降下（４）のＫ回の繰り返しはＫ個の回路「レイヤ（ｌａｙｅｒｓ）」に対応し、各回路レイヤは前の例やの値からプロファイルの新しい値を計算する。回路の出力はアイテムプロファイルＶであり、ユーザプロファイルは破棄される。
【００４７】
本技術分野の当業者には言うまでもなく、例えば、ＲＡＭモデルにおいて、演算が平文で実行される場合、傾斜降下の各繰り返しを計算する時間的複雑性はＯ（Ｍ）である。各傾斜の計算（５）は２Ｍ個の項の加算を含み、プロファイル更新（４）はＯ（ｎ＋ｍ）＝Ｏ（Ｍ）で行える。
【００４８】
回路として傾斜降下を実装する際の主要な問題は、効率よくそうすることにある。これを例示するため、次のナイーブな実装を考える：
Ｑ１．各ペア（ｉ，ｊ）∈［ｎ］×［ｍ］、入力からインジケータδｉ，ｊ＝１（ｉ，ｊ）∈Ｍ（ｉがｊをレーティングしたら１，そうでなければ０）を生成する。
Ｑ２．各繰り返しにおいて、これらの回路の出力を用いて、各アイテム及びユーザ傾斜を、ｍとｎの積にわたる合計として計算する。ここで、
【数９】
2016510913.tif 000021
である。
【００４９】
残念ながらこの実装は効率的ではない：傾斜降下アルゴリズムの各繰り返しの回路複雑性（ｃｉｒｃｕｉｔ  ｃｏｍｐｌｅｘｉｔｙ）はＯ（ｎ×ｍ）である。Ｍ≪ｎ×Ｍのとき、実際にはこういう場合が普通であるが、上記の回路は平文における傾斜降下（ｇｒａｄｉｅｎｔ  ｄｅｓｃｅｎｔ）より急激に効率的でなくなる。実際、ほとんどのデータセットについて、二次のコストＯ（ｎ×ｍ）は禁止的である。
ナイーブな実装の非効率性は、どのユーザがアイテムをレーティングしたか、どのアイテムが回路デザインの時にユーザによりレーティングされたかを特定できないことに起因する。これがデータに本来備わった希薄性をレバレッジする能力を緩和している。
【００５０】
逆に、本原理の好ましい実施形態では、複雑性がθ（（η＋ｍ＋Ｍ）ｌｏｇ２（ｎ＋ｍ＋Ｍ））である、すなわち平文における実装の多重対数係数内であるソーティングネットワークに基づく回路実装が提供される。要約すると、タプル（ｉ，ｊ，ｒｉ，ｊ）と、ユーザ及びアイテム両方のプロファイルのプレースホルダー（ｐｌａｃｅｈｏｌｄｅｒｓ）｜に対応する両方の入力データが共にアレイに格納される。適当なソーティング演算により、ユーザ又はアイテムプロファイルは、識別子を共有する入力の近くに配置され得る。データをリニアパスすることにより、傾斜の計算とプロファイルの更新ができる。ソーティング時、プレースホルダーは＋∞として、すなわち他のどの数より大きいとして扱われる。
【００５１】
本原理の好ましい実施形態による、図４のフローチャート４００を満たす行列因子分解アルゴリズムは、次のステップで記述され得る：
Ｃ１．行列Ｓを初期化する（４１０）。
アルゴリズムは、入力として、セット
［外１１］
2016510913.tif 000022
を、または同じ事であるが、タプル
［外１２］
2016510913.tif 000023
を受け取り、ｎ＋ｍ＋Ｍ個のタプルのアレイを構成する。Ｓの最初のｎ個とｍ個のタプルは、それぞれユーザ及びアイテムプロファイルのプレースホルダーとして機能し、残りのＭ個のタプルは入力Ｌｉを格納する。より具体的には、各ユーザｉ∈［ｎ］について、アルゴリズムはタプル
［外１３］
2016510913.tif 000024
を構成する。ここで、ｕｉ∈Ｒｄはユーザｉの初期プロファイルであり、ランダムに選択される。各アイテムｊ∈［ｍ］について、アルゴリズムは、タプル
［外１４］
2016510913.tif 000025
を構成する。ここで、νｊ∈Ｒｄはアイテムｊの初期プロファイルであり、これもランダムに選択される。最後に、各ペア（ｉ，ｊ）∈Ｍについて、アルゴリズムは、対応するタプル
［外１５］
2016510913.tif 000026
を構成する。ここで、ｒｉ，ｊはユーザｉのアイテムｊに対するレーティングである。結果として得られるアレイは図５（Ａ）に示した通りである。ｋ番目のタプルのｉ番目の要素により示すと、これらの要素は次の役割を果たす：
（ａ）  ｓ１，ｋ：［ｎ］中のユーザ識別子；
（ｂ）  ｓ２，ｋ：［ｍ］中のアイテム識別子；
（ｃ）ｓ３，ｋ：タプルが「プロファイル」または「入力」タプルであるか示すバイナリフラグ；
（ｄ）  ｓ４，ｋ：「入力」タプル中のレーティング；
（ｅ）  ｓ５，ｋ：Ｒｄ中のユーザプロファイル；
（ｆ）  ｓ６，ｋ：Ｒｄ中のアイテムプロファイル。
Ｃ２．タプルをユーザＩＤに関して（行１と３に関して）昇順でソートする（４２０）。２つのＩＤが等しければ、タプルフラグすなわち各タプルの第３要素を比較することにより、均衡を破る。このように、ソーティング後、各「ユーザプロファイル」タプルは同じＩＤの「入力」タプルにより引き継がれる：
Ｃ３．ユーザプロファイル（左パス）をコピーする（４３０）：
［外１６］
2016510913.tif 000027
Ｃ４．タプルをアイテムＩＤに関して（行２と３に関して）昇順でソートする（４４０）。
４４０．２つのＩＤが等しければ、タプルフラグすなわち各タプルの第３要素を比較することにより、均衡を破る。
Ｃ５．アイテムプロファイル（左パス）をコピーする（４５０）：
［外１７］
2016510913.tif 000028
Ｃ６．∀ｋ＜Ｍについて傾斜貢献を計算する（４６０）：
［外１８］
2016510913.tif 000029
Ｃ７．アイテムプロファイルを更新する（右パス）（４７０）：
［外１９］
2016510913.tif 000030
Ｃ８．行１と３に関してタプルをソートする（４７５）
Ｃ９．ユーザプロファイルを更新する（右パス）（４８０）：
［外２０］
2016510913.tif 000031
Ｃ１０．繰り返し数がＫ未満であればＣ３に進む（４８５）
Ｃ１１．行３と２に関してタプルをソートする（４９０）
Ｃ１２．アイテムプロファイルｓ６，ｋ（ｋ＝１，．．．，ｍ）を出力する（４９５）。出力は少なくとも１つのアイテムプロファイルに制限され得る。
【００５２】
傾斜降下インターラクションは次の３つの主要ステップを有する：
Ａ．プロファイルのコピー：各繰り返しにおいて、各ユーザｉと各アイテムｊのプロファイルｕｉとνｊは、ｉとｊが現れる各「入力」タプルの対応要素ｓ５，ｋとｓ６，ｋにコピーされる。これはアルゴリズムのステップＣ２ないしＣ５に実装されている。例えば、ユーザプロファイルをコピーするため、ユーザＩＤ（すなわち、ｓ１，ｋ）を主インデックスとして、かつフラグ（すなわち、ｓ３，ｋ）を副インデックスとして用いて、Ｓをソートする。Ｓの初期状態に適用されるかかるソーティングの一例を図５（Ｂ）に示した。その後、アルゴリズムのステップＣ３で形式的に説明したように、左から右に（「左」パス）アレイを横切ることにより、ユーザＩＤをコピーする。これは、各「プロファイル」タプルからその隣接する「入力」タプルにｓ５，ｋをコピーする；アイテムプロファイルは同様にコピーされる。
Ｂ．傾斜貢献の計算：プロファイルをコピーした後、例えば、（ｉ，ｊ）に対応する各「入力」タプルは、最後の繰り返しで計算された（ｓ４，ｋの）レーティングｒｉ，ｊと（それぞれｓ５，ｋとｓ６，ｋ中の）プロファイルｕｉとｖｊを格納する。これらから、次の数量が計算される：
［外２１］
2016510913.tif 000032
、これは式（５）で与えられたｕｉとｖｊに関する傾斜中のタプルの「貢献」と見なせる。これらは、アルゴリズムのステップＣ６に示したように、タプルの要素ｓ５，ｋとｓ６，ｋを置き換える。フラグの適切な使用により、この演算は「入力」タプルにのみ影響し、「プロファイル」タプルは変化しない。
Ｃ．プロファイルの更新：最後に、アルゴリズムのステップＣ７乃至Ｃ９に示したように、ユーザ及びアイテムプロファイルが更新される。適切なソーティングにより、「プロファイル」タプルが、ＩＤが共通な「入力」タプルに隣接される。更新されたプロファイルはアレイの右から左への横断（ｔｒａｖｅｒｓｉｎｇ）（「右パス」）により計算される。この動作により、「入力」タプルを横断する時に、傾斜の貢献を加える。「プロファイル」タプルと出会うと、加算された傾斜貢献がプロファイルに加算され、適宜スケールされる。プロファイルを通過した後、フラグｓ３，ｋ、ｓ３，ｋ＋１の適切な使用により、傾斜貢献の加算がゼロから再度始まる。
【００５３】
上記の動作はＫ回、すなわち傾斜降下の所望の繰り返し数だけ繰り返される。最後に、最後の繰り返しの終わりに、フラグ（すなわち、ｓ３，ｋ）を主インデックスとし、アイテムＩＤ（すなわち、ｓ２，ｋ）を副インデックスとして、アレイをソートする。これにより、すべてのアイテムプロファイルタプルは、そのアイテムプロファイルを出力できるアレイ中の最初のｍ個の位置になる。さらに、ユーザプロファイルを取得するため、最後の繰り返しの終わりに、フラグ（すなわち、ｓ３，ｋ）を主インデックスとし、ユーザＩＤ（すなわち、ｓ１，ｋ）を副インデックスとして、アレイをソートする。これにより、すべてのユーザプロファイルタプルは、そのユーザプロファイルを出力できるアレイ中の最初のｎ個の位置になる。
【００５４】
本技術分野の当業者には言うまでもないが、上記の各動作はデータｏｂｌｉｖｉｏｕｓ（ｄａｔａ−ｏｂｌｉｖｉｏｕｓ）であり、回路として実装できる。プロファイルのコピーと更新には、（ｎ＋ｍ＋Ｍ）個のゲートが必要であり、全体的な複雑性は、例えば、Ｂａｔｃｈｅｒの回路を用いて、
［外２２］
2016510913.tif 000033
のコストを生じるものをソートすることにより判断される。アルゴリズムのステップＣ６におけるソーティングと傾斜計算は、最も計算量が大きい演算である；幸い、両者は並列化可能である。また、ソーティングは、各繰り返しにおいて前に計算された比較を再利用することにより、さらに最適化できる。特に、この回路はブーリアン回路（例えば、ＯＲ、ＡＮＤ、ＮＯＴ、及びＸＯＲゲートのグラフとして）実装でき、これにより前述の通り実装をｇａｒｂｌｅｄすることができる。
【００５５】
本原理によると、上記の行列因子分解アルゴリズムと前記のプロトコルの実装により、プライバシーを保護したリコメンデーションの新規な方法が提供される。また、このソリューションにより、ソーティングネットワークを用いることにより、平文において実行される行列因子分解の、多重対数係数内の複雑性を有する回路を提供する。さらに、本実装の付加的利点は、ｇａｒｂｌｉｎｇとこの回路の実行が高度に並列化できることである。
【００５６】
本原理によるシステムの実装では、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ構成は公開されているｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔフレームワークであるＦａｓｔＧＣに基づくものであった。ＦａｓｔＧＣはＪａｖａ（登録商標）ベースのオープンソースフレームワークであり、これにより基本的なＸＯＲ、ＯＲ及びＡＮＤゲートを用いた回路定義が可能となる。回路が構成されると、フレームワークがｇａｒｂｌｉｎｇ、ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒ及びｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの完全な評価を処理する。しかし、回路をｇａｒｂｌｉｎｇし実行する前に、ＦａｓｔＧＣはＪａｖａ（登録商標）オブジェクトのセットとしてメモリ中にｇａｒｂｌｅｄされていない回路全体を表す。これらのオブジェクトは、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔが生じるべきメモリフットプリントに対して大きなメモリオーバーヘッドを生じる。いつの時点でもゲートのサブセットのみがｇａｒｂｌｅｄされ、及び／または実行されるからである。さらに、上記の通り、ＦａｓｔＧＣは実行プロセスと並列にｇａｒｂｌｉｎｇを実行するが、両方の動作は順次に行われる：ゲートは、その入力の準備ができると、一つずつ処理される。当業者には言うまでもなく、この実装は並列化の影響を受けにくい。
【００５７】
結果として、フレームワークはこれらの２つの問題を解決するため修正され、ＦａｓｔＧＣのメモリフットプリントを低減するだけでなく、並列的ｇａｒｂｌｉｎｇ及び複数のプロセッサに跨る計算を可能にした。具体的に、回路を水平にパーティションして順次的「レイヤ」にして、それぞれが並列に実行できる垂直な「スライス」のセットを有する機能を導入した。レイヤは、その入力がすべて準備できた時にのみ、メモリ中に生成される。一旦ｇａｒｂｌｅｄされ評価されると、レイヤ全体がメモリから削除され、次のレイヤが構成でき、こうしてメモリフットプリントが最大レイヤのサイズに制限される。レイヤの実行はスライスをスレッドにアサインして、並列実行を可能にするスケジューラを用いて行われる。並列化は複数のコアを有する単一マシン上に実装されたが、この実装は簡単に複数の異なるマシンにわたる実行に拡張できる。スライス間の共有状態は仮定されていないからである。最後に、アルゴリズムで概説した数値演算を実装するため、ＦａｓｔＧＣを拡張して固定小数点表現の実数の加算と乗算、及びソーティングをサポートした。ソーティングの場合、Ｂａｔｃｈｅｒのソーティングネットワークを用いた。固定小数点表現により、切り捨ての結果生じる精度低下と回路のサイズとの間にトレードオフの関係が生じた。
【００５８】
さらに、アルゴリズムの実装が複数の方法で最適化された。特に、
（ａ）回路の実行の始めに計算される比較を再利用することにより、ソーティングのコストを低減した：
ソーティングネットワークの基本的構成ブロックは、比較及びスワップ回路であり、これは２つのアイテムを比較して、必要に応じてそれをスワップし、出力されるペアを順序付ける。行列因子分解アルゴリズムのソーティング動作（ラインＣ４とＣ８）は、繰り返し毎にまったく同じ入力を用いて、Ｋ個の傾斜降下繰り返しのそれぞれにおいてタプル間の同じ比較を行う。実際、各ソーティングは、各繰り返しにおいて、全く同じ方法で、アレイＳ中のタプルの順序を変える。この特性は、これらのソーティングの比較動作をそれぞれ一度だけ実行することに利用する。特に、（ｉ，ｊ，フラグ，レーティング）形式のタプルのソーティングは、例えば、先にｉとフラグ、ｊとフラグ、そしてまたｉとフラグに関して、（ユーザ又はアイテムプロファイルのペイロード無しに）計算の始めに実行される。その後、比較回路の出力は、傾斜降下中に用いられるスワップ回路への入力としてこれらの各ソーティングにおいて再利用される。結果として、各繰り返しにおいて適用される「ソーティング」ネットワークは、何も比較をしないが、単純にタプルの順序を変える（すなわち、これは「置換」ネットワークである）。
（ｂ）アレイＳのサイズを低減する：
すべての比較を事前に計算しておくと、Ｓ中のタプルのサイズを大幅に削減できる。初めに、当業者には言うまでもなく、ユーザ又はアイテムＩＤに対応する行は、行列因子分解アルゴリズムにおいて、ソーティング中の比較への入力として使われるだけである。フラグとレーティングはコピー及び更新フェーズ中に用いられるが、それらの相対的位置は各繰り返しにおいて同一である。さらに、これらの位置は、計算の初めにおいて、タプル（ｉ，ｊ，フラグ，レーティング）のソーティングの出力として計算できる。そのため、各繰り返しにおいて実行される「置換」動作は、ユーザ及びアイテムプロファイルにのみ適用する必要がある；他のすべての行はアレイＳから削除できる。もう一つの改善により、置換のコストがさらに１／２に低減する：例えば、ユーザプロファイルのセットを固定し、アイテムプロファイルのみを置換する。次いで、アイテムプロファイルが２つの状態の間でローテーションし、一方の状態には他方の状態から置換により到達できる：ユーザプロファイルと合わせられ、部分傾斜が計算される状態と、アイテムプロファイルが更新されコピーされる状態である。
（ｃ）ＸＯＲを用いてスワップ動作を最適化した：
ＸＯＲ演算が「フリー」に実行できるので、可能であれば、ＸＯＲを用いることにより、比較、スワップ、更新及びコピー動作の最適化を行う。本技術分野の当業者には言うまでもなく、フリーＸＯＲゲートは、関連するｇａｒｂｌｅｄテーブル及びそれに対応するハッシング又は対称鍵演算を行わなくてもｇａｒｂｌｅｄでき、計算と通信における顕著な改善である。
（ｄ）計算を並列化する：
ソーティングと傾斜計算は、行列因子分解回路における計算の大部分をなし（コピーと更新による貢献は実行時間の３％及び非ＸＯＲゲートの０．４％未満である）、これらの演算はＦａｓｔＧＣのこの拡張により並列化される。傾斜計算は明らかに並列化可能である；ソーティングネットワークも高度に並列化可能である（並列化はその開発の主要なモチベーションである）。さらに、各ソートの多くのパラレルスライスが同一であるので、回路スライスを確定している同じＦａｓｔＧＣは異なる入力で再利用され、メモリ中でオブジェクトを繰り返し生成及び削除する必要性が大幅に減る。
【００５９】
言うまでもなく、本原理は、ハードウェア、ソフトウェア、ファームウェア、特殊用途プロセッサ、またはこれらの組み合わせなどのいろいろな形体で実施することができる。好ましくはハードウェアとソフトウェアを組み合わせて本原理を実施する。また、プログラム記録装置に有体的に化体されたアプリケーションプログラムとしてソフトウェアを実施してもよい。そのアプリケーションプログラムは、好適なアーキテクチャを有する機械にアップロードされ、実行される。好ましくは、機械は、中央処理装置（ＣＰＵ）、ランダムアクセスメモリ（ＲＡＭ）、及び入出力（Ｉ／Ｏ）インタフェース等のハードウェアを有するコンピュータプラットフォームで実施される。コンピュータプラットフォームはオペレーティングシステムとマイクロコードも含んでもよい。ここに説明した様々なプロセスや機能は、オペレーティングシステムにより実行できる、マイクロ命令コードの一部やアプリケーションプログラムの一部（またはこれらの組み合わせ）であってもよい。また、追加的データ記憶装置や印刷装置等その他の様々な周辺装置をコンピュータプラットフォームに接続してもよい。
【００６０】
図６は、本原理の実装に利用される最小限度の計算環境６００を示すブロック図である。計算環境６００は、プロセッサ６１０、少なくとも１つの（好ましくは２つ以上の）Ｉ／Ｏインタフェース６２０を含む。Ｉ／Ｏインタフェースは、有線又は無線であり、無線の実施形態では、計算環境６００がグローバルネットワーク（例えば、インターネット）上で動作し、他のコンピュータ又はサービス（例えば、クラウドベースの計算又はストレージサービス）と通信できる適切な無線通信プロトコルで予め構成され、本原理が、例えばエンドユーザにリモートで提供されるＳｏｆｔｗａｒｅ  ａｓ  ａ  Ｓｅｒｖｉｃｅ（ＳＡＡＳ）機能をとして提供できるようにしている。一以上のメモリ６３０及び／又はストレージデバイス（ＨＤＤ）６４０も計算環境６００内に提供される。計算環境６００は、本原理の一実施形態による、行列因子分解Ｃ１−Ｃ１２（図４）のためのプロトコルＰ１−Ｐ１７（図３）を実装する。特に、本原理の一実施形態では、計算環境６００はＲｅｃＳｙｓ２３０を実装し得る；別の計算環境６００はＣＳＰ２５０を実装し、ソースはそれぞれが区別できるユーザ２１０に関連する一又は複数の計算環境６００を含み、ＲｅｃＳｙｓ２３０及びＣＳＰ２５０との通信に使われる、デスクトップコンピュータ、セルラー電話、スマートフォン、フォーンウォッチ、タブレットコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、ノートブック及びラップトップコンピュータを含むがこれに限定されない。また、ＣＳＰ２５０は、ソース中に含まれても、または同等であるが、ソースの各ユーザ２２１０の計算環境に含まれても良い。
【００６１】
さらに言うまでもなく、添付した図面に示したシステム構成要素や方法ステップの一部はソフトウェアで実施されてもよいので、システム構成要素（または方法ステップ）間の実際的な結合は本原理をプログラムするそのプログラム方法に応じて異なる。ここに開示された教示を受けて、関連技術分野の当業者は、本原理の同様な実施形態や構成を考えることができるであろう。
【００６２】
例示した実施形態を添付した図面を参照して説明したが、言うまでもなく、本原理はこれらの実施形態には限定されず、当業者は、本原理の範囲と精神から逸脱することなく、様々な変化と修正を施すことができるであろう。かかる変更や修正はすべて添付した請求項に記載した本原理の範囲内に含まれるものである。
【図１】
2016510913.tif 000034
【図２】
2016510913.tif 000035
【図３Ａ】
2016510913.tif 000036
【図３Ｂ】
2016510913.tif 000037
【図３Ｃ】
2016510913.tif 000038
【図３Ｄ】
2016510913.tif 000039
【図４Ａ】
2016510913.tif 000040
【図４Ｂ】
2016510913.tif 000041
【図４Ｃ】
2016510913.tif 000042
【図５】
2016510913.tif 000043
【図６】
2016510913.tif 000044
【手続補正書】
【提出日】平成27年9月10日(2015.9.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
方法であって、
第１のレコードセットを受信するステップであって、前記第１のレコードセットの各レコードは、第１のユーザセット中の各ユーザから受信され、トークンセットとアイテムセットとを含み、前記各ユーザ以外のパーティには秘密にされる、ステップと、
リコメンダシステムが、第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いて行列因子分解に基づき前記第１のレコードセットを評価するステップであって、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセットの複数のアイテムの各々のマスクされたアイテムプロファイルを含む、ステップと、
アイテムについて要求ユーザからリコメンデーション要求を受信するステップと、
前記マスクされたアイテムプロファイルを前記要求ユーザに転送するステップであって、前記要求ユーザはリッジ回帰に基づき第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いることにより第２のレコードと前記マスクされたアイテムプロファイルを評価し、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記アイテムに関するリコメンデーションを含み、前記リコメンデーションは前記要求ユーザのみに知られる、ステップと
を有する、方法。
【請求項２】
暗号サービスプロバイダから第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを受信し、前記第１のレコードセットに対して行列因子分解を行うステップであって、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセットの複数のアイテムの各々のマスクされたアイテムプロファイルを含む、ステップをさらに有する、
請求項１に記載の方法。
【請求項３】
前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔは行列因子分解演算をブーリアン回路として実装し、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔはリッジ回帰演算をブーリアン回路として実装する、
請求項２に記載の方法。
【請求項４】
前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔは、前記第１のレコードセットのアレイを構成し、アレイのソーティング、コピー、更新、比較及び傾斜貢献の計算の演算を実行する、
請求項３に記載の方法。
【請求項５】
前記第１のレコードセットは暗号化されている、請求項２に記載の方法。
【請求項６】
暗号は部分的準同型暗号であり、前記方法は、
前記暗号化されたレコードをマスクして、マスクされたレコードを生成するステップと、
復号のため、前記マスクされたレコードを暗号サービスプロバイダに復号のため転送するステップとを有する、
請求項５に記載の方法。
【請求項７】
前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔはマスクされ復号されたレコードをアンマスクする、請求項６に記載の方法。
【請求項８】
前記暗号サービスプロバイダと前記リコメンダシステムとの間でｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うステップであって、前記リコメンダシステムは前記マスクされ復号されたレコードのｇａｒｂｌｅｄ値を受け取り、前記レコードは前記リコメンダシステムと前記リコメンダシステムには秘密にしておかれる、
請求項６に記載の方法。
【請求項９】
前記要求ユーザ、暗号サービスプロバイダ及びリコメンダシステムの間でプロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うステップであって、リコメンダシステムはマスクされたアイテムプロファイルを提供し、前記要求ユーザは前記マスクされたアイテムプロファイルのｇａｒｂｌｅｄ値を受信し、前記マスクされたアイテムプロファイルは前記要求ユーザと暗号サービスプロバイダには秘密にしておかれる、請求項１に記載の方法。
【請求項１０】
各レコードのトークンとアイテムの数を受け取るステップと、
暗号サービスプロバイダに、ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの実装のためパラメータセットを送信するステップと
をさらに有する、
請求項１に記載の方法。
【請求項１１】
トークン数が最大値と等しいレコードを生成するため、各レコードのトークン数が前記最大値より小さいとき、前記レコードはヌルエントリーでパディングされる、請求項１に記載の方法。
【請求項１２】
前記第１のレコードセットのソースと前記第２のレコードのソースのうち少なくとも一方はデータベースである、請求項１に記載の方法。
【請求項１３】
ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの実装のためのパラメータセットを、前記暗号サービスプロバイダに送信するステップをさらに有する、請求項２に記載の方法。
【請求項１４】
装置であって、
少なくとも１つの入出力インタフェースと通信するプロセッサと、
前記プロセッサと信号通信する少なくとも１つのメモリとを有し、
前記プロセッサは、
第１のユーザセットから第１のレコードセットを受信し、各レコードは、トークンセットとアイテムセットとを含み、前記各ユーザ以外のパーティには秘密にされ、
要求ユーザから、アイテムに対するリコメンデーション要求を受信し、
第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを用いて、行列因子分解に基づいて、前記第１のレコードセットを評価し、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は、前記第１のレコードセットの複数のアイテムの各々のマスクされたアイテムプロファイルを含み、
リッジ回帰に基づき第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔにおいて評価するため、前記マスクされたアイテムプロファイルを前記要求ユーザに転送する、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記アイテムに関するリコメンデーションを含み、前記リコメンデーションは前記要求ユーザにのみ知られる、
装置。
【請求項１５】
第１のレコードセットに行列因子分解を行う第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを実装するステップであって、各レコードは第１のユーザセットの各ユーザから受信され、トークンセットとアイテムセットを含み、各レコードは前記各ユーザ以外のパーティからは秘密にしておかれ、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセットの複数のアイテムの各々のマスクされたアイテムプロファイルを含む、ステップと、
ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔをリコメンダシステムに転送するステップであって、前記リコメンダシステムは前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを評価し、前記マスクされたアイテムプロファイルを提供する、ステップと、
第２のレコードと前記マスクされたアイテムプロファイルとにリッジ回帰を行う第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを実装するステップであって、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力はあるアイテムに関するリコメンデーションを含む、ステップと、
第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔと要求ユーザに転送するステップであって、前記要求ユーザは前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを評価して前記アイテムに関するリコメンデーションを取得するステップとを有する、
方法。
【請求項１６】
実装するステップは、
行列因子分解演算をブーリアン回路として実装するステップと、
リッジ回帰演算をブーリアン回路として実装するステップと、を有する
請求項１５に記載の方法。
【請求項１７】
第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔは、レコードセットのアレイを構成し、前記アレイに、ソーティング、コピー、更新、比較及び傾斜貢献計算の演算を実行することにより、行列因子分解を実行する、
請求項１６に記載の方法。
【請求項１８】
公開暗号鍵を生成するステップと、
鍵を前記各ユーザに送信するステップとをさらに有する、
請求項１５に記載の方法。
【請求項１９】
暗号は部分的準同型暗号であり、前記方法は、
リコメンダシステムからマスクされたレコードを受信するステップと、
前記マスクされたレコードを復号して、マスクされ復号されたレコードを生成するステップとをさらに有する、
請求項１８に記載の方法。
【請求項２０】
第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを実装するステップは、
処理する前に、前記ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ内の前記マスクされ復号されたレコードをアンマスクするステップを有する、
請求項１９に記載の方法。
【請求項２１】
前記リコメンダシステムとｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを行うステップであって、前記リコメンダシステムは前記マスクされ復号されたレコードのｇａｒｂｌｅｄ値を受信し、前記レコードは前記リコメンダシステムと暗号サービスプロバイダには秘密にしておかれる、ステップをさらに有する、
請求項１９に記載の方法。
【請求項２２】
第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔは、要求ユーザからマスクされたアイテムプロファイルと第２のレコードとを受信し、マスクされたアイテムプロファイルをアンマスクし、トークン、アイテム及びアイテムプロファイルを含むタプルのアレイを生成し、対応するアイテムプロファイルが第２のレコードの各トークン及びアイテムに加えられ、前記タプルのアレイにリッジ回帰を実行して要求ユーザプロファイルを生成し、前記要求ユーザプロファイルと少なくとも１つのアイテムプロファイルからリコメンデーションを生成することにより、リッジ回帰を実行する、
請求項２０に記載の方法。
【請求項２３】
アレイを生成するステップはソーティングネットワークを用いて行う、
請求項２２に記載の方法。
【請求項２４】
要求ユーザ及びリコメンダシステムとプロキシｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒを実行するステップであって、前記リコメンダシステムはマスクされたアイテムプロファイルを提供し、前記要求ユーザはマスクされたアイテムプロファイルのｇａｒｂｌｅｄ値を受け取り、マスクされたアイテムプロファイルは要求ユーザ及び暗号サービスプロバイダには秘密にしておかれる、
請求項１５に記載の方法。
【請求項２５】
前記ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの実装のためのパラメータセットを受信するステップであって、パラメータは前記リコメンダシステムにより送信される、ステップをさらに有する、
請求項１６に記載の方法。
【請求項２６】
少なくとも１つの入出力インタフェースと通信するプロセッサと、
前記プロセッサと信号通信する少なくとも１つのメモリと、を有し、前記プロセッサは、
第１のレコードセットに行列因子分解を行う第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを実装し、各レコードは第１のユーザセットの各ユーザから受信され、トークンセットとアイテムセットを含み、各レコードは前記各ユーザ以外のパーティからは秘密にしておかれ、前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力は前記第１のレコードセットの複数のアイテムの各々のマスクされたアイテムプロファイルを含み、
ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔをリコメンダシステムに転送し、前記リコメンダシステムは前記第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを評価し、前記マスクされたアイテムプロファイルを提供し、
第２のレコードと前記マスクされたアイテムプロファイルとにリッジ回帰を行う第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを実装し、前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力はあるアイテムに関するリコメンデーションを含み、
第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔと要求ユーザに転送し、前記要求ユーザは前記第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを評価して前記アイテムに関するリコメンデーションを取得する、
装置。
【請求項２７】
レコードにアクセスするステップであって、前記レコードはトークンセットとアイテムセットを含み、要求ユーザ以外のパーティには秘密にしておかれるステップと、
アイテムに関するリコメンデーション要求をリコメンダシステムに送信するステップと、
リコメンダシステムからマスクされたアイテムプロファイルを受信するステップであって、前記マスクされたアイテムプロファイルは行列因子分解に基づく第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力であるステップと、
入力が前記レコードとマスクされたアイテムプロファイルであり、出力がリコメンデーションであるリッジ回帰に基づき、第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを評価するステップとを有する、
方法。
【請求項２８】
少なくとも１つの入出力インタフェースと通信するプロセッサと、
前記プロセッサと信号通信する少なくとも１つのメモリと、を有し、前記プロセッサは、
レコードにアクセスし、前記レコードはトークンセットとアイテムセットを含み、要求ユーザ以外のパーティには秘密にしておかれ、
アイテムに関するリコメンデーション要求をリコメンダシステムに送信し、
リコメンダシステムからマスクされたアイテムプロファイルを受信し、前記マスクされたアイテムプロファイルは行列因子分解に基づく第１のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔの出力であり、
入力が前記レコードとマスクされたアイテムプロファイルであり、出力がリコメンデーションであるリッジ回帰に基づき、第２のｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔを評価するように構成されている、
装置。

【国際調査報告】
2016510913.tif 000045
2016510913.tif 000046
2016510913.tif 000047
2016510913.tif 000048