(57)【要約】レコードを安全に計数する方法は、レコードのセットを入力として受信するステップであって、上記レコードのセットは少なくとも１つのレコードを含み、各レコードはトークンのセットを含み、上記トークンのセットは少なくとも１つのトークンを含む、ステップと、少なくとも１つのトークンを含むトークンの別個のセットを受信するステップと、上記レコードのセットおよび上記トークンの別個のセットを処理して、任意の個々のレコードの内容および当該総数以外の上記レコードから抽出された任意の情報の総数を知ることなく、別個のトークンのセットに属する各トークンがいくつのレコードに出現するかを計数する、ステップと、を含む。
2016509268.tif 000002
【特許請求の範囲】
【請求項１】
レコードを安全に計数して、前記レコードを評価する評価器（２３０）に対して前記レコードがプライベートに保たれるようにする方法であって、
レコードのセットを受信するステップ（２２０，３４０）であって、各レコードはトークンのセットを含み、各レコードは前記レコードのソース以外のパーティから秘密に保たれる、前記受信するステップと、
ガーブル回路（３７０）により前記レコードのセットを評価するステップであって、前記ガーブル回路の出力は総数である、前記評価するステップと、
を含む、前記方法。
【請求項２】
トークンの別個のセットを受信するかまたは決定するステップ（３２０）をさらに含む、請求項１に記載の方法。
【請求項３】
前記レコードのセット内の前記トークンの別個のセットを計数するために、前記ガーブル回路を暗号システムプロバイダ（ＣＳＰ）において設計するステップ（３５０）と、
前記ガーブル回路を前記評価器に転送するステップ（３６０）と、
をさらに含む、請求項２に記載の方法。
【請求項４】
前記設計するステップは、
カウンタをブール回路として設計するステップ（３５２）をさらに含む、請求項３に記載の方法。
【請求項５】
カウンタを設計する前記ステップは、
前記レコードのセットおよび前記トークンの別個のセットの配列を構築するステップ（４１０）と、
前記配列上でソート（４２０，４４０）、シフト（４３０）、加算（４３０）および格納の動作を実行するステップと、
を含む、請求項４に記載の方法。
【請求項６】
前記受信するステップは、ソース、前記評価器および前記ＣＳＰの間でプロキシ紛失通信（３４２）により実行され（３５０）、前記ソースは前記レコードを提供し、前記レコードは前記評価器および前記ＣＳＰに対してプライベートに保たれ、前記ガーブル回路は入力として前記レコードのガーブル値を取得する、請求項１に記載の方法。
【請求項７】
暗号化されたレコードを作成するために前記レコードのセットを暗号化するステップ（３８０）をさらに含み、前記暗号化するステップは、前記レコードのセットを受信するステップの前に実行される、請求項３に記載の方法。
【請求項８】
前記設計するステップ（３５０）は、
前記暗号化されたレコードを、処理の前に前記ガーブル回路の内部で復号化するステップ（３５４）を含む、請求項７に記載の方法。
【請求項９】
前記暗号化は部分的準同型暗号化であり（３８２）、
前記評価器において前記暗号化されたレコードをマスクしてマスクされたレコードを作成するステップ（３８５）と、
前記ＣＳＰにおいて前記マスクされたレコードを復号化して復号化されマスクされたレコードを作成するステップ（３９５）と、
を含む、請求項７に記載の方法。
【請求項１０】
前記設計するステップ（３５０）は、
前記ガーブル回路の内部で、前記復号化されマスクされたレコードを、処理の前にマスク解除するステップ（３５６）を含む、請求項９に記載の方法。
【請求項１１】
各レコードは重みのセットをさらに含み、
前記重みのセットは少なくとも１つの重みを含む、請求項１に記載の方法。
【請求項１２】
前記重みは、前記レコードのそれぞれのトークンの頻度の測度および評点のうちの１つに対応する、請求項１１に記載の方法。
【請求項１３】
各レコードのトークンの数を受信するステップ（２２０、３１０）をさらに含む、請求項１に記載の方法。
【請求項１４】
各レコードのトークンの数が最大値を表す値より小さい場合、前記値に等しい数のトークンによりレコードを作成するために、各レコードをヌルエントリでパディングするステップ（３１２）
をさらに含む、請求項１に記載の方法。
【請求項１５】
前記レコードのセットのソースは、データベースとユーザのセット（２１０）とのうちの一方であり、前記ソースがユーザのセットである場合、各ユーザは少なくとも１つのレコードを提供する、請求項１に記載の方法。
【請求項１６】
前記ＣＳＰにより、ガーブル回路の設計のためのパラメータのセットを受信するステップをさらに含み、前記パラメータは前記評価器により送信されたものである（３３０）、請求項３に記載の方法。
【請求項１７】
レコードを安全に計数するシステムであって、前記レコードを提供するソース、安全なカウンタを提供する暗号サービスプロバイダ（ＣＳＰ）および前記レコードを評価する評価器を含み、前記レコードが前記評価器および前記ＣＳＰに対してプライベートに保たれるようにしたシステムであって、前記ソース、前記ＣＳＰおよび前記評価器はそれぞれ、
少なくとも１つの入力／出力（４０４）を受信するプロセッサー（４０２）と、
前記プロセッサーと信号通信する少なくとも１つのメモリ（４０６、４０８）と、
を備え、前記評価器のプロセッサーは、
レコードのセットを受信し、各レコードはトークンのセットを含み、各レコードは秘密に保たれ、
ガーブル回路により前記レコードのセットを評価し、前記ガーブル回路の出力が総数となるように構成される、前記システム。
【請求項１８】
前記評価器のプロセッサーは、トークンの別個のセットを受信するように構成される、請求項１７に記載のシステム。
【請求項１９】
前記ＣＳＰのプロセッサーは、
前記レコードのセット内の前記トークンの別個のセットを計数するために、前記ガーブル回路を設計し、
前記ガーブル回路を前記評価器に転送するように構成される、請求項１８に記載のシステム。
【請求項２０】
前記ＣＳＰのプロセッサーは、
カウンタをブール回路として設計するように構成されることにより、前記ガーブル回路を設計するように構成される、請求項１９に記載のシステム。
【請求項２１】
前記ＣＳＰのプロセッサーは、
前記レコードのセットおよび前記トークンの別個のセットの配列を構築し、
前記配列上で、ソート、シフト、加算および格納の動作を実行するように構成されることにより、前記カウンタを設計するように構成される、請求項２０に記載のシステム。
【請求項２２】
前記ソースのプロセッサー、前記評価器のプロセッサーおよび前記ＣＳＰのプロセッサーはプロキシ紛失通信を実行するように構成され、前記ソースは前記レコードを提供し、前記レコードは前記評価器および前記ＣＳＰに対してプライベートに保たれ、前記ガーブル回路は入力として前記レコードのガーブル値を取得する、請求項１７に記載のシステム。
【請求項２３】
前記ソースのプロセッサーは、
暗号化されたレコードを作成するために、前記レコードのセットを処理の前に暗号化するように構成される、請求項１９に記載のシステム。
【請求項２４】
前記ＣＳＰのプロセッサーは、
前記暗号化されたレコードを、処理の前に前記ガーブル回路の内部で復号化するようにさらに構成されることにより、前記ガーブル回路を設計するように構成される、請求項２３に記載のシステム。
【請求項２５】
前記暗号化は部分的準同型暗号化であり、前記評価器のプロセッサーは、
前記暗号化されたレコードをマスクしてマスクされたレコードを作成するようにさらに構成され、前記ＣＳＰのプロセッサーは、
前記マスクされたレコードを復号化して復号化されマスクされたレコードを作成するようにさらに構成される、請求項２３に記載のシステム。
【請求項２６】
前記ＣＳＰのプロセッサーは、
前記ガーブル回路の内部で、前記復号化されマスクされたレコードを、処理の前にマスク解除するようにさらに構成されることにより前記ガーブル回路を設計するように構成される、請求項２５に記載のシステム。
【請求項２７】
各レコードは重みのセットをさらに含み、
前記重みのセットは少なくとも１つの重みを含む、請求項１７に記載のシステム。
【請求項２８】
前記重みは、前記レコードのそれぞれのトークンの頻度の測度および評価のうちの１つに対応する、請求項２７に記載のシステム。
【請求項２９】
前記評価器のプロセッサーは、
各レコードのトークンの数を受信するようにさらに構成され、前記トークンの数は前記ソースから送信されたものである、請求項１７に記載のシステム。
【請求項３０】
前記ソースのプロセッサーは、
各レコードのトークンの数が最大値を表す値より小さい場合、前記値に等しい数のトークンによりレコードを作成するために、各レコードをヌルエントリでパディングするようにさらに構成される、請求項１７に記載のシステム。
【請求項３１】
前記レコードのセットのソースは、データベースとユーザのセットとのうちの一方であり、前記ソースがユーザのセットである場合、各ユーザは、少なくとも１つの入力／出力（５０４）を受信するプロセッサー（５０２）と、少なくとも１つのメモリ（５０６、５０８）とを含み、各ユーザは少なくとも１つのレコードを提供する、請求項１７に記載のシステム。
【請求項３２】
前記ＣＳＰのプロセッサーは、
ガーブル回路の設計のためのパラメータのセットを受信するようにさらに構成され、前記パラメータは前記評価器により送信されたものである、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本願は、米国特許法第１１９条（ｅ）の下で、２０１３年８月９日に出願された米国仮特許出願、第６１／８６４０８５号明細書、発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＣＯＵＮＴＩＮＧ」、第６１／８６４０８８号明細書、発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ  ＰＲＥＳＥＲＶＩＮＧ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」、第６１／８６４０９４号明細書、発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＴＯ  ＲＡＴＩＮＧ  ＣＯＮＴＲＩＢＵＴＩＮＧ  ＵＳＥＲＳ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ」、および第６１／８６４０９８号明細書、発明の名称「Ａ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＦＯＲ  ＰＲＩＶＡＣＹ−ＰＲＥＳＥＲＶＩＮＧ  ＲＥＣＯＭＭＥＮＤＡＴＩＯＮ  ＢＡＳＥＤ  ＯＮ  ＭＡＴＲＩＸ  ＦＡＣＴＯＲＩＺＡＴＩＯＮ  ＡＮＤ  ＲＩＤＧＥ  ＲＥＧＲＥＳＳＩＯＮ」に対する優先権を主張する。これら仮出願は、実質上その全体が参照によって本明細書に明示的に組み込まれる。
【０００２】
本発明の原理は、プライバシーを保護する提案システムおよび安全なマルチパーティ演算に関し、より詳細にはプライバシーを保護する方式で安全に計数することに関する。
【背景技術】
【０００３】
過去１０年間における多量の研究と商業活動の結果、提案システムが広く使用されるようになっている。そのようなシステムは、映画、ＴＶ番組、音楽、書籍、ホテル、飲食店等の種々の項目について、個人に合わせた提案をユーザに提供する。図１は一般的な提案システム１００の構成要素を示し、構成要素は、ソースを表す多数のユーザ１１０、およびユーザの入力１２０を処理して提案１４０を出力するレコメンダ（recommender）システム（ＲｅｃＳｙｓ）１３０である。有用な提案を受け取るために、ユーザは、レコメンダが自分の個人情報データを適切に管理することを信頼して、自分の嗜好に関するかなり多くの個人情報（ユーザの入力）を供給する。
【０００４】
それでも、Ｂ．Ｍｏｂａｓｈｅｒ，Ｒ．Ｂｕｒｋｅ，Ｒ．Ｂｈａｕｍｉｋ，ａｎｄ  Ｃ．Ｗｉｌｌｉａｍｓ：“Ｔｏｗａｒｄ  ｔｒｕｓｔｗｏｒｔｈｙ  ｒｅｃｏｍｍｅｎｄｅｒ  ｓｙｓｔｅｍｓ：Ａｎ  ａｎａｌｙｓｉｓ  ｏｆ  ａｔｔａｃｋ  ｍｏｄｅｌｓ  ａｎｄ  ａｌｇｏｒｉｔｈｍ  ｒｏｂｕｓｔｎｅｓｓ．”，  ＡＣＭ  Ｔｒａｎｓ．  Ｉｎｔｅｒｎｅｔ  Ｔｅｃｈｎ．，７（４），２００７、およびＥ．Ａ’ｉｍｅｕｒ，Ｇ．Ｂｒａｓｓａｒｄ，Ｊ．Ｍ．Ｆｅｒｎａｎｄｅｚ，ａｎｄ  Ｆ．Ｓ．Ｍ．Ｏｎａｎａ：“ＡＬＡＭＢＩＣ：Ａ  ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｒｅｃｏｍｍｅｎｄｅｒ  ｓｙｓｔｅｍ  ｆｏｒ  ｅｌｅｃｔｒｏｎｉｃ  ｃｏｍｍｅｒｃｅ”，Ｉｎｔ．Ｊｏｕｒｎａｌ  Ｉｎｆ．Ｓｅｃ．，７（５），２００８等の先立つ研究は、レコメンダがそのような情報を悪用する、またはユーザをプライバシー脅威にさらすことが可能な手段を複数特定している。レコメンダはしばしば利益のためにデータを転売することを考えるが、ユーザによって意図的に明らかにされた事以外の情報を抽出しようと考えることもある。例えば、通例は機密性があると認識されないユーザ嗜好のレコード、例えば映画の評点や個人のテレビ視聴履歴さえもが使用されて、ユーザの所属政党や性別などを推測することができる。提案システムにあるデータから推測されることができる個人情報は、新たなデータマイニング方法または推論方法が、悪意ある目的のためであれ、有益な目的のためであれ開発されるのに伴って常に進展している。極端な場合には、ユーザ嗜好のレコードが使用されてユーザを一意に特定することさえできる。Ａ．ＮａｒａｎｙａｎおよびＶ．Ｓｈｍａｔｉｋｏｖは、２００８年のＩＥＥＥ  Ｓ＆Ｐにおける“Ｒｏｂｕｓｔ  ｄｅ−ａｎｏｎｙｍｉｚａｔｉｏｎ  ｏｆ  ｌａｒｇｅ  ｓｐａｒｓｅ  ｄａｔａｓｅｔｓ”，でＮｅｔｆｌｉｘのデータセットの匿名性を破ることによってそれを実証し、関心を集めた。そのため、レコメンダに悪意がなくとも、そのようなデータが意図せず漏洩すると、ユーザはリンケージ攻撃、すなわち１つのデータベースを補助情報として使用して別のデータベースのプライバシーを危険にさらす攻撃を受けやすくなる。
【０００５】
将来発生する推論脅威、不測の情報漏洩、またはインサイダー脅威（故意の漏洩）は予測できるとは限らないため、ユーザが自分の個人データを平文の状態で公開しない提案システムを構築することに関心が持たれる。現在、暗号化されたデータに基づいて動作する実用的な提案システムは存在しない。また、ユーザが提供する評点、さらにはユーザがどの項目を評点付けしたかも一度も知ることなく項目を分析することができるレコメンダを構築することにも関心が持たれる。本発明はそのような安全な提案システムの一態様を扱い、このシステムは提案以外の目的にも利用されることができる。
【発明の概要】
【０００６】
本発明の原理は、プライバシーを保護する方式で安全に計数する方法およびシステムを提案する。詳細には、この方法は、各々が各自のトークンのセットを備えるレコードのセット（「コーパス」）」を入力として受け取る。また、上記方法は、入力として別のトークンのセットを受け取り、各トークンがいくつのレコードに出現するかを求める。上記方法は、個々のレコードの内容、または総数以外のレコードから抽出される情報を一切知ることなく、各トークンがいくつのレコードに出現するかを安全な方式で計数する。
【０００７】
本発明の原理の一態様によると、安全にレコードを計数する方法が提供され、レコードは、そのレコードを評価する評価器（２３０）からプライベートに保たれ、上記方法は、レコードのセットを受け取るステップ（２２０、３４０）であって、各レコードはトークンのセットを備え、各レコードはそのレコードのソース以外のパーティに対して秘密に保たれる、ステップと、上記レコードのセットをガーブル（garbled）回路で評価するステップ（３７０）であって、上記ガーブル回路の出力は総数である、ステップとを含む。上記方法は、別のトークンのセットを受け取るか、または決定するステップ（３２０）を含むことができる。上記方法は、暗号システムプロバイダ（ＣＳＰ）内で上記ガーブル回路を、上記レコードのセットにおける上記別のトークンのセットを計数するように設計するステップ（３５０）と、上記ガーブル回路を上記評価器に転送するステップ（３６０）とをさらに含むことができる。この方法における設計のステップは、カウンタをブール回路として設計するステップ（３５２）を含むことができる。この方法におけるカウンタを設計するステップは、上記レコードのセットおよび上記別のトークンのセットの配列を構築するステップ（４１０）と、上記配列上で、ソート（４２０、４４０）、シフト（４３０）、加算（４３０）、および格納の動作を実行するステップとを含むことができる。この方法における受け取るステップは、上記ソースと、上記評価器と、上記ＣＳＰとの間のプロキシ紛失通信（３４２）を通じて実行される（３５０）ことができ、上記ソースがレコードを提供し、レコードは上記評価器および上記ＣＳＰからプライベートに保たれ、上記ガーブル回路はそのレコードのガーブル値を入力として受け取る。上記方法は、上記ＣＳＰによりガーブル回路の設計のためのパラメータのセットを受け取るステップをさらに含むことができ、それらのパラメータは評価器から送信されたものである（３３０）。
【０００８】
本発明の原理の一態様によると、上記方法は、レコードのセットを暗号化して暗号化されたレコードを作成するステップ（３８０）をさらに含むことができ、暗号化のステップは、レコードのセットを受け取るステップの前に行われる。この方法における設計のステップ（３５０）は、ガーブル回路の内部で、暗号化されたレコードを復号化するステップ（３５４）を含むことができる。上記暗号化システムは、部分的準同型暗号化（３８２）であることが可能であり、上記方法は、暗号化されたレコードを上記評価器内でマスクしてマスクされたレコードを作成するステップ（３８５）と、そのマスクされたレコードを上記ＣＳＰ内で復号化して復号化されマスクされたレコードを作成するステップ（３９５）とをさらに含むことができる。この方法における設計のステップ（３５０）は、上記ガーブル回路の内部で、上記復号化されマスクされたレコードをそれらを処理する前にマスク解除するステップ（３５６）を含むことができる。
【０００９】
本発明の原理の一態様によると、この方法における各レコードはさらに重みのセットを含むことができ、重みのセットは少なくとも１つの重みを備える。この方法における重みは、上記レコード中のそれぞれのトークンの頻度の測度および評点の一方に対応することができる。
【００１０】
本発明の原理の一態様によると、上記方法は、各レコードのトークンの数を受け取るステップ（２２０、３１０）をさらに含むことができる。さらに、上記方法は、各レコードのトークンの数が、最大値を表す値よりも小さい場合は、その値に等しい数のトークンを持つレコードを作成するために、各レコードをヌルエントリでパディングするステップ（３１２）をさらに含むことができる。この方法における上記レコードのセットのソースは、ユーザの組（２１０）およびデータベースのうちの一方であることが可能であり、上記ソースがユーザのセットである場合、各ユーザは少なくとも１つのレコードを提供する。
【００１１】
本発明の原理の一態様によると、安全にレコードを計数するシステムが提案され、システムは、レコードを提供するソースと、安全なカウンタを提供する暗号サービスプロバイダ（ＣＳＰ）と、レコードが評価器およびＣＳＰからプライベートに保たれるようにレコードを評価する評価器とを含み、上記ソース、上記ＣＳＰ、および上記評価器は各々、少なくとも１つの入力／出力（４０４）を受け取るプロセッサー（４０２）と、そのプロセッサーと信号通信する少なくとも１つのメモリ（４０６、４０８）とを含み、上記評価器のプロセッサーは、レコードのセットを受け取り、各レコードはトークンのセットを含み、各レコードは秘密に保たれ、レコードのセットをガーブル回路で評価するように構成され、上記ガーブル回路の出力は総数である。上記システムの上記評価器のプロセッサーは、別のトークンのセットを受け取るように構成されることができる。上記システムの上記ＣＳＰのプロセッサーは、ＣＳＰ内で上記ガーブル回路を、上記レコードのセットにおける上記別のトークンのセットを計数するように設計し、そのガーブル回路を上記評価器に転送するように構成されることができる。上記システムの上記ＣＳＰのプロセッサーは、カウンタをブール回路として設計するように構成されることにより、上記ガーブル回路を設計するように構成されることができる。上記システムの上記ＣＳＰのプロセッサーは、上記レコードのセットおよび上記別のトークンのセットの配列を構築し、その配列にソート、シフト、加算、および格納の動作を行うように構成されることにより、上記カウンタを設計するように構成されることができる。上記ソースのプロセッサー、上記評価器のプロセッサー、および上記ＣＳＰのプロセッサーは、プロキシ紛失通信を行うように構成されることができ、ソースがレコードを提供し、上記評価器は上記レコードのガーブル値を受け取り、レコードは評価器およびＣＳＰからプライベートに保たれ、上記ガーブル回路はそのレコードのガーブル値を入力として受け取る。このシステムの上記ＣＳＰのプロセッサーは、ＣＳＰによるガーブル回路の設計のためのパラメータのセットを受け取るようにさらに構成されることができ、それらのパラメータは上記評価器から送信されたものである。
【００１２】
本発明の原理の一態様によると、上記システムの上記ソースのプロセッサーは、上記レコードのセットを提供する前に上記レコードのセットを暗号化して暗号化されたレコードを作成するように構成されることができる。上記システムの上記ＣＳＰのプロセッサーは、それらを処理する前に暗号化されたレコードを上記ガーブル回路の内部で復号化するようにさらに構成されることにより、上記ガーブル回路を設計するように構成されることができる。上記暗号化は、部分的準同型暗号化であることが可能であり、上記システムの上記評価器のプロセッサーは、暗号化されたレコードをマスクしてマスクされたレコードを作成するようにさらに構成されることができ、上記ＣＳＰのプロセッサーは、そのマスクされたレコードを復号化して復号化されマスクされたレコードを作成するようにさらに構成されることができる。上記ＣＳＰのプロセッサーは、上記ガーブル回路の内部で、上記復号化されマスクされたレコードをそれらを処理する前にマスク解除するようにさらに構成されることにより、上記ガーブル回路を設計するように構成されることができる。
【００１３】
本発明の原理の一態様によると、このシステムにおける各レコードはさらに重みのセットを含むことができ、重みのセットは少なくとも１つの重みを備える。このシステムにおける重みは、上記レコード中のそれぞれのトークンの頻度の測度および評点の一方に対応することができる。
【００１４】
本発明の原理の一態様によると、このシステムの上記評価器のプロセッサーは、各レコードのトークンの数を受け取るようにさらに構成されることができ、トークンの数はソースから送信されたものである。このシステムの上記ソースのプロセッサーは、各レコードのトークンの数が、最大値を表す値よりも小さい場合は、その値に等しい数のトークンを持つレコードを作成するために、各レコードをヌルエントリでパディングするように構成されることができる。このシステムにおける上記レコードのセットのソースは、データベースおよびユーザのセットの１つであることが可能であり、上記ソースがユーザのセットである場合、各ユーザは、少なくとも１つの入力／出力（４０４）を受け取るプロセッサー（４０２）と、プロセッサーと信号通信する少なくとも１つのメモリ（４０６、４０８）とを備え、各ユーザは少なくとも１つのレコードを提供する。
【００１５】
本発明のその他の特徴および利点は、添付図面を参照して進める以下の例示的実施形態の詳細な説明から明らかにされる。
【図面の簡単な説明】
【００１６】
本発明の原理は、下記に簡単に説明される以下の例示的な図に沿ってよりよく理解されよう。
【図１】従来技術の提案システムの構成要素を示す図である。
【図２】本発明の原理によるプライバシーを保護する計数システムの構成要素を示す図である。
【図３Ａ】本発明の原理によるプライバシーを保護する計数方法のフローチャートを示す図である。
【図３Ｂ】本発明の原理によるプライバシーを保護する計数方法のフローチャートを示す図である。
【図３Ｃ】本発明の原理によるプライバシーを保護する計数方法のフローチャートを示す図である。
【図３Ｄ】本発明の原理によるプライバシーを保護する計数方法のフローチャートを示す図である。
【図３Ｅ】本発明の原理によるプライバシーを保護する計数方法のフローチャートを示す図である。
【図３Ｆ】本発明の原理によるプライバシーを保護する計数方法のフローチャートを示す図である。
【図３Ｇ】本発明の原理によるプライバシーを保護する計数方法のフローチャートを示す図である。
【図４】本発明の原理によるカウンタのフローチャートを示す図である。
【図５】本発明の原理を実装するために利用される演算環境のブロック図である。
【発明を実施するための形態】
【００１７】
本発明の原理によると、プライバシーを保護する方式で安全に計数する方法が提供される。当業者は、本発明には多数の用途があることを認められよう。可能な用途の１つは、所与のセットにあるキーワードが個人または複数の個人の電子メールにどれほど頻繁に出現するかを計数するものである。オンラインサービスは、ユーザ（複数可）にどの広告を表示するかを決めるために、例えば「映画」、「チケット」、「靴」等の単語が電子メールのコーパスに出現する頻度を求めたい場合がある。この方法は、サービスが、各電子メールの内容を一度も明示的に知ることなく、そのような計数を行うことを可能にする。
【００１８】
本発明の原理によって解決される問題を正式に説明すると、各々がトークンのセットを備えるレコードのコーパス中でトークンが出現する回数をサービスが計数したいというものである。当業者は、上記の例で、レコードは電子メールであることが可能であり、トークンは単語であることが可能であり、サービスは、特定のキーワードを使用しているレコードの数を計数したいということを認識されよう。ただし、関与する個人のプライバシーを保証するために、サービスは、そのような計数の他には何も知ることなく計数を行いたい。詳細には、サービスは、（ａ）各キーワードがどのレコード／電子メールに出現したか、または、さらには、（ｂ）各電子メールにどのトークン／単語が出現するか、は知るべきではない。
【００１９】
別の用途は、各映画を評点付けしたのが誰であるか、またはそれらの者が付与した評点を明らかにすることなく、評点のコーパスから項目、例えば映画の閲覧回数、さらには平均の評点を算出するものである。その場合、レコードは、ユーザによって評点付け／閲覧された映画のセットとそれぞれの評点であり、トークンはｍｏｖｉｅ＿ｉｄである。本発明が使用されて、どのユーザがどの映画を閲覧したかを一度も知ることなく、何人のユーザが映画を評点付けまたは閲覧したかを計数することができる。さらに、本発明が使用されて、どのユーザがどの映画を評点付けしたか、またはユーザが付与した評点を一度も知ることなく、各映画の平均評点などの統計を算出することができる。同様に、本発明は、各ユーザの投票内容を一度も知ることなく、１人の候補（例えば市長やコンペの勝者）または複数人の候補（例えば代表取締役会）の選出で票数を計算するためにも使用されることができる。
【００２０】
したがって、本発明の原理によると、方法は、各々が各自のトークンのセットを備えるレコードのセット（「コーパス」）」を入力として受け取る。このセットまたはレコードは少なくとも１つのレコードを含み、トークンのセットは少なくとも１つのトークンを含む。また、方法は、入力として別のトークンのセットを受け取り、その別のトークンのセットにある各トークンがいくつのレコードに出現するかを求める。別のトークンのセットは、すべてのレコードにあるすべてのトークン、すべてのレコードにあるトークンのサブセットを含むことができ、又はレコードに存在しないトークンさえ含むこともできる。方法は、個々のレコードの内容や、総数以外のレコードから抽出される情報を一切知ることなく、各トークンがいくつのレコードに出現するかを安全な方式で計数する。この方法は、下記に議論するように安全なマルチパーティ演算（multi-party computation）（ＭＰＣ）アルゴリズムによって実装される。
【００２１】
安全なマルチパーティ演算（ＭＰＣ）は、１９８０年代にＡ．Ｃｈｉ−Ｃｈｉｈ  Ｙａｏによって最初に提案された。Ｙａｏのプロトコル（「ガーブル（garbled）回路」とも称される）は、安全なマルチパーティ演算の汎用的な方法である。Ｖ．Ｎｉｋｏｌａｅｎｋｏ，Ｕ．Ｗｅｉｎｓｂｅｒｇ，Ｓ．Ｉｏａｎｎｉｄｉｓ，Ｍ．Ｊｏｙｅ，Ｄ．Ｂｏｎｅｈ，ａｎｄ  Ｎ．Ｔａｆｔによる“Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  Ｒｉｄｇｅ  Ｒｅｇｒｅｓｓｉｏｎ  ｏｎ  Ｈｕｎｄｒｅｄｓ  ｏｆ  ｍｉｌｌｉｏｎｓ  ｏｆ  ｒｅｃｏｒｄｓ”，ＩＥＥＥ  Ｓ＆Ｐ，  ２０１３から応用されたその変形例では、このプロトコルは、ｎ人の入力所有者のセット（ａiはユーザｉのプライベートな入力を表し、１≦ｉ≦ｎ）と、ｆ（ａ1，．．．，ａn）を評価しようとする評価器と、サードパーティである暗号サービスプロバイダ（ＣＳＰ）との間で実行される。プロトコルの終了時に、評価器は、ｆ（ａ1，．．．，ａn）の値を知るが、どのパーティもその出力値から明らかにされる事よりも多くのことを知ることはない。このプロトコルは、関数ｆがブール回路として、例えばＯＲ、ＡＮＤ、ＮＯＴ、およびＸＯＲゲートのグラフとして表されることができることを必要とし、また評価器とＣＳＰが共謀しないことを必要とする。
【００２２】
近年、Ｙａｏのガーブル回路を実装した機構が多く存在する。汎用的なＭＰＣの別の手法は秘密共有方式に基づくものであり、別の手法は完全準同型暗号化（ＦＨＥ）に基づく。秘密共有方式は、線形システム、線形回帰の解決などの各種の線形代数動作および競売向けに提案されている。秘密共有には、演算の作業負荷を均等に分担し、複数回にわたって通信を行う共謀していないオンライン機関が少なくとも３つ必要であり、演算はそれらのうち二者が共謀しない限り安全である。ガーブル回路は、共謀していない２つのみの機関と、はるかに少ない通信を想定し、このことは、評価器がクラウドサービスであり、暗号サービスプロバイダ（ＣＳＰ）が信頼されるハードウェア構成要素で実装される事例により適する。
【００２３】
使用される暗号プリミティブに関係なく、安全なマルチパーティ演算の効率的なアルゴリズムを構築する際の主要な課題は、データオブリビアス（ｄａｔａ−ｏｂｌｉｖｉｏｕｓ）方式で、すなわち実行経路が入力に依存しないようにアルゴリズムを実装することである。一般に、有界時間Ｔ内に実行することができるＲＡＭプログラムはいずれもＯ（Ｔ＾３）のチューリング機械（ＴＭ）に変換されることができる。チューリング機械は、数学計算の理想化モデルとして機能するためにアラン・チューリングによって発明された理論上の演算機械であり、Ｏ（Ｔ＾３）は複雑度がＴ3に比例することを意味する。また、有界のＴ時間のＴＭはいずれも大きさＯ（Ｔ  ｌｏｇ  Ｔ）の回路に変換されることができ、これはデータオブリビアスである。これは、有界のＴ時間で実行可能なＲＡＭプログラムはいずれもＯ（Ｔ＾３  ｌｏｇ  Ｔ）の複雑度でデータオブリビアス回路に変換されることが可能であることを意味する。そのような複雑度は高過ぎ、大半の用途では採り入れることができない。効率的なデータオブリビアスな実装が知られていないアルゴリズムの概説が、Ｗ．Ｄｕ  ａｎｄ  Ｍ．Ｊ．Ａｔａｌｌａｈによる２００１年のＮｅｗ  Ｓｅｃｕｒｉｔｙ  Ｐａｒａｄｉｇｍｓ  Ｗｏｒｋｓｈｏｐでの“Ｓｅｃｕｒｅ  ｍｕｌｔｉ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｐｒｏｂｌｅｍｓ  ａｎｄ  ｔｈｅｉｒ  ａｐｐｌｉｃａｔｉｏｎｓ：  Ａ  ｒｅｖｉｅｗ  ａｎｄ  ｏｐｅｎ  ｐｒｏｂｌｅｍｓ”に見出されることができる。
【００２４】
ソーティングネットワークは、元々はソートの並列化ならびに効率的なハードウェア実装を可能にするために開発されたものである。そのようなネットワークは、入力列（ａ1，ａ2，．．，ａn）をソートして、単調増加列（ａ’1，ａ’2，．．，ａ’n）にする回路である。それらは、主要な構築ブロックとなるコンペア・アンド・スワップ回路を共に配線することによって構築される。いくつかの研究が、暗号化の目的でソーティングネットワークのデータ紛失性（ｄａｔａ−ｏｂｌｉｖｉｏｕｓｎｅｓｓ）を利用している。しかし、暗号化はプライバシーを保証するのに十分であるとは限らない。攻撃者が暗号化された記憶へのユーザのアクセスパターンを観察することができれば、ユーザのアプリケーションが何を行っているのかについての機密性のある情報を知ることができる。
【００２５】
本発明の原理は、重み付き集合の共通部分に近いもののガーブル回路を組み込み、計数に特化する安全なマルチパーティソーティングに基づく方法を提案する。ガーブル回路を使用する本発明の原理のカウンタを実装する単純な方式は非常に高い演算コストを有し、コーパス中のトークンの数に対して二次関数的に増加する演算を必要とする。本発明の原理で提案される実装ははるかに高速であり、コーパスにあるトークンの数に対してほぼ線形の費用となる。
【００２６】
本発明の原理は、図２に示すように３つの構成要素からなる。
【００２７】
Ｉ．評価器システム（Ｅｖａｌ）２３０。レコードについても、総数Ｃ２４０以外のレコードから抽出される情報についても一切知ることなく、安全な計数を行うエンティティ。
【００２８】
ＩＩ．暗号サービスプロバイダ（ＣＳＰ）２５０。レコードまたはレコードから抽出される情報について何も知ることなく、安全な演算を可能にする。
【００２９】
ＩＩＩ．ソース。１または複数のユーザ２１０からなり、各ユーザはレコードまたはレコードのセット２２０を有し、各レコードは計数されるトークンのセットを備え、各レコードはそのレコードのソース（すなわちユーザ）以外のパーティには秘密に保たれる。換言すると、ソースは１または複数のユーザのデータを保持するデータベースを表すことができる。
【００３０】
本発明の原理の好ましい実施形態は、図３のフローチャート３００を満たし、以下のステップで説明されるプロトコルを備える。
【００３１】
Ｐ１。ソースが、関係するレコード各々について、提出される予定のトークンの数を評価器に報告する（３１０）。
【００３２】
Ｐ２。評価器が、ガーブル回路を設計するのに必要なパラメータをＣＳＰに報告し（３３０）、これはトークンの数３３２と、総数を表すために使用されるビット数３３４とを含む。また、評価器は、それに基づいて総数を算出する別のトークンのセットを受け取るか、または決定する（３２０）。このトークンのセットは、コーパスにあるすべてのトークン、すべてのトークンのサブセット、さらにはレコードに存在しないトークンを備えることもできる。この別のトークンのセットは、すべてのトークンではなくとも、パラメータに含められる。
【００３３】
Ｐ３。ＣＳＰが、総数を算出する、当業者に「ガーブル回路」として知られるものを用意する（３５０）。ガーブル化されるために、回路はまずブール回路として書かれる（３５２）。回路への入力は、トークンのリスト（ｔｏｋｅｎ＿ｉｄ＿１，ｔｏｋｅｎ＿ｉｄ＿２，．．．，ｔｏｋｅｎ＿ｉｄ＿Ｍ）と想定され、Ｍはコーパスにあるトークンの総数である（すなわち各ユーザから提出されたトークンの和）。具体的には、ガーブル回路は入力としてレコード／トークンのガーブル値を受け取り、レコードのセットおよび別のトークンのセットＴ１を処理して、個々のレコードの内容や総数以外のレコードから抽出される情報は一切知ることなく、別のトークンのセットに属する各トークンがいくつのレコードに出現するかを計数する。
【００３４】
Ｐ４。ＣＳＰがこの回路をガーブル化し、評価器に送信する（３６０）。具体的には、ＣＳＰは、ゲートを処理してガーブルテーブルにし、それらを回路構造で定義される順序で評価器に送信する。
【００３５】
Ｐ５。ソース、評価器、およびＣＳＰ間のプロキシ紛失通信３４２を通じて、評価器が、評価器自体もＣＰＵも実際の値を知ることなくユーザの入力のガーブル値を知る。紛失通信は、送信側が多数ある可能性のある情報の１つを受信者に送信し、受信者はどの情報（存在する場合）が転送されたのかを意識しないままであるタイプの転送であることを当業者は理解されよう。プロキシ紛失通信は、３者以上のパーティが関与する紛失通信である。詳細には、このプロキシ紛失通信では、ソースがレコード／トークンを提供し、評価器がレコード／トークンのガーブル値を受け取り、ＣＳＰがプロキシの役割を果たし、評価器もＣＳＰもレコードを知ることはない。
【００３６】
Ｐ６。評価器がガーブル回路を評価し、要求される値を出力する（３７０）。
【００３７】
技術的には、このプロトコルは、Ｃ２４０以外に、各ユーザから提供されたトークンの数も漏らす。これは、単純なプロトコル変形、例えば、事前に設定された最大数に達するまで提出されたレコードを「ヌル（null）」エントリで適切に「パディング」することにより是正することができる（３１２）。単純化のために、プロトコルはこの「パディング」動作を含めずに説明された。
【００３８】
本発明で提案される回路実装はソーティングネットワークを使用する。簡潔に言うと、回路は、トークンごとのカウンタと併せてすべての入力を配列に入れる。そして、それは、計数されるべきトークンのすぐ隣にそれらが来るようにカウンタが置き換えられることを保証しながら配列をソートする。配列に線形パスを行うことにより、回路はトークンが何回出現するかを計数することができ、その情報を該当するカウンタに格納する。
【００３９】
本発明の原理の計数回路の例示的な詳細な説明では、標準的な「協働フィルタリング」の設定が想定され、ここではｎ人のユーザがｍ個の可能な項目（例えば映画）のサブセットを評点付けする。［ｎ］：＝｛１，．．．，ｎ｝のユーザのセットおよび［ｍ］：＝｛１，．．．，ｍ｝の項目のセットについて、評点が生成されているユーザ／項目のペアを
【００４０】
【数１】
2016509268.tif 000003
【００４１】
で表し、評点の総数を
【００４２】
【数２】
2016509268.tif 000004
【００４３】
で表す。最後に、
【００４４】
【数３】
2016509268.tif 000005
【００４５】
について、項目ｊについてユーザｉによって生成された評点を
【００４６】
【数４】
2016509268.tif 000006
【００４７】
で表す。
【００４８】
実際的な設定では、ｎとｍはともに大きな数であり、典型的には１０4と１０6の間の範囲である。また、提供される評点は疎であり、すなわちＭ＝Ｏ（ｎ＋ｍ）であり、これは、存在しうる評点の総数ｎ×ｍよりもはるかに少ない。各ユーザは有限数の項目しか評点付けしない可能性があるため（ｍ、すなわち「カタログ」の大きさに依存しない）、これは典型的なユーザの行動と整合する。
【００４９】
本発明の原理はまた、
【００５０】
【数５】
2016509268.tif 000007
【００５１】
が、項目ｊ∈［ｍ］が受け取った評点の数であり、回路は入力としてセット
【００５２】
【数６】
2016509268.tif 000008
【００５３】
を受け取り、総数
【００５４】
【数７】
2016509268.tif 000009
【００５５】
を出力すると想定する。当業者は、ＲＡＭモデルにおけるそのような作業の複雑度はＯ（ｍ＋Ｍ）になることを理解されよう。これは、並列度を高くするという犠牲を払うことで、
【００５６】
【数８】
2016509268.tif 000010
【００５７】
に対する１回のパスですべてのｃjが同時に算出されることができるためである。それに対して、ｉがｊを評点付けした場合は１に、それ以外の場合は０になる指標
【００５８】
【数９】
2016509268.tif 000011
【００５９】
を使用する単純な回路実装は、Ｏ（ｎ×ｍ）の回路複雑度を生じ、これは極めて高い。
【００６０】
単純な実装の非効率性は、どのユーザが項目を評点付けするのか、およびどの項目がユーザによって評点付けされるのかを回路設計時に特定できないことから生じ、データの固有の疎性（ｓｐａｒｓｉｔｙ）を活用する能力を低下させている。それに対し、本発明の原理は、そのようなユーザと項目間のマッチングを回路内で効率的に行い、ソーティングネットワークを使用してＯ（（ｍ＋Ｍ）ｐｏｌｙｌｏｇ（ｍ＋Ｍ））回のステップで
【００６１】
【数１０】
2016509268.tif 000012
【００６２】
を返すことができる回路を提案し、ｐｏｌｙｌｏｇは多重対数関数を示唆する。
【００６３】
図４のフローチャート４００を満たす本発明の原理の好ましい実施形態によるカウンタは、以下のステップにより説明されることができる。
【００６４】
Ｃ１．入力として
【００６５】
【数１１】
2016509268.tif 000013
【００６６】
を与えられて、（ｍ＋Ｍ）個のタプルの配列Ｓを構築する（４１０）。まず、各ｊ∈［ｍ］について、（ｊ，⊥，０）の形態のタプルを作成し、「ヌル」の記号⊥はプレースホルダーである（４１２）。２番目に、各
【００６７】
【数１２】
2016509268.tif 000014
【００６８】
について、（ｊ，１，１）の形態のタプルを作成して
【００６９】
【数１３】
2016509268.tif 000015
【００７０】
を生じる（４１４）。
【００７１】
直感的に、最初のｍ個のタプルが「カウンタ」として機能し、トークンごとのカウント数を格納する。残りのＭ個のタプルは、計数される「入力」を含んでいる。各タプルの３番目の要素はバイナリーフラグとして機能し、カウンタを入力から分離する。
【００７２】
Ｃ２．項目ＩＤ、すなわち各タプルの最初の要素に対して昇順でタプルをソートする（４２０）。２つのＩＤが等しい場合は、タプルフラグ、すなわち各タプルの３番目の要素を比較することによって決着をつける。したがって、ソート後、各「カウンタ」のタプルの後には同じＩＤを持つ「入力」のタプルがある。
【００７３】
【数１４】
2016509268.tif 000016
【００７４】
Ｃ３．一番右のタプルから開始し、右から左へと移動して、各タプルの２番目のエントリの値を加算する（４３０）。カウンタのタプル（すなわちゼロのフラグ）が到達されたら、算出された値を⊥のエントリに格納し、計数を再度開始する。より正式には、ｋ番目のタプルのｌ番目の要素をｓl,kで表す。この「右から左」へのパスは以下の代入に相当する。
【００７５】
（ｍ＋Ｍ−１）から１までの範囲のｋについて、
ｓ2,k←ｓ3,k＋ｓ3,k+1×ｓ2,k+1   （３）
Ｃ４．今度はフラグｓl,kに対して昇順で再度配列をソートする（４４０）。その結果得られる配列の最初のｍ個のタプルはカウンタを含んでおり、それらが出力として公開される。
【００７６】
当業者は、上記のカウンタは、入力として
【００７７】
【数１５】
2016509268.tif 000017
【００７８】
を受け取り、すべての項目ｊ∈［ｍ］について（ｊ，ｃj）を出力する回路として容易に実装されることが可能であることを認識されよう。ステップ１は、Ｏ（ｍ＋Ｍ）個のゲートを使用して、入力がタプル
【００７９】
【数１６】
2016509268.tif 000018
【００８０】
で出力が最初の配列Ｓである回路として実装されることができる。ソート動作は、例えば、入力として最初の配列を受け取り、ソート後の配列を出力するＢａｔｃｈｅｒのソーティングネットワークを使用して行われることができ、Ｏ（（ｍ＋Ｍ）ｌｏｇ’（ｍ＋Ｍ））個のゲートを必要とする。最後に、右から左へと行われるパスは、この場合もＯ（ｍ＋Ｍ）個のゲートを使用して、各タプルに（３）を行う回路として実装されることができる。極めて重要な点として、このパスはデータ紛失である。すなわち、（３）ではフラグｓ3,kおよびｓ3,k+1を通じて「入力」のタプルから「カウンタ」を区別するが、同じ動作が配列のすべての要素に行われる。詳細には、この回路は、上記のように実装がガーブル化されることを可能にするブール回路（例えばＯＲ、ＡＮＤ、ＮＯＴ、およびＸＯＲゲートのグラフ）として実装されることができる。例えば、ガーブル回路の構築は、基本的なＸＯＲ、ＯＲ、およびＡＮＤゲートを使用した回路定義を可能にする、Ｊａｖａ（登録商標）に基づくオープンソースのフレームワークであるＦａｓｔＧＣに基づくことができる。回路が構築されると、フレームワークが、ガーブル処理、紛失通信、およびガーブル回路の完全な評価を扱う。
【００８１】
本発明の原理によると、上記のプロトコルと組み合わせた上記のカウンタの実装は、プライバシーを保護する方式で安全に計数する新規の方法を提供する。また、この解決法は、ソーティングネットワークを使用することにより、平文で行われるカウンタの多重対数倍以内の複雑度の回路を生じる。
【００８２】
同じく図３のフローチャート３００に示される本発明の第２の実施形態（フローチャート中の追加Ａ、Ｂ、およびＣを含む）では、ユーザが各自の入力の暗号化された値を評価器に提出し（３８０）、ＣＳＰが、その入力をまず復号化して（３５４）からデータに作用する回路を用意する（３５０）。ガーブル回路は評価器に送られ（３６０）、評価器は、（プロキシではない平文の）紛失通信３４４を通じて暗号化データのガーブル値を取得し、それらを使用して回路を評価する。この実装は、ユーザが自身の入力を提出した後はプロトコルを「離れる」ことができる（すなわちオンラインのままでいることを必要とされない）という利点を有する。
【００８３】
同じく図３のフローチャート３００に示される本発明の第３の実施形態（フローチャート中の追加Ａ、Ｂ、Ｄ、およびＥを含む）では、ユーザは、部分的準同型暗号化３８２を通じて、各自の入力の暗号化された値を提出する（３８０）。当業者は、準同型暗号化とは、暗号文に対して行われ、復号化されたものが平文に実行された演算の結果と一致する暗号化された結果を得るための特定種類の演算を可能にする暗号化の形態であることを理解されよう。例えば、１人の人物が２つの暗号化された数を足し、別の人物がその結果を復号化することができるが、どちらの人物も個々の数の値を求めることはできない。部分的準同型暗号化は、平文に対する１回の動作（加算または乗算）に対して準同型となる。部分的準同型暗号化は、スカラーに対する加算または乗算に対して準同型とすることもできる。
【００８４】
暗号化された値を受け取ると、評価器はユーザ入力にマスクを付加する（３８５）。当業者は、マスクはデータ難読化の形態であり、乱数生成器やシャフリング（shuffling）と同程度に単純であり得ることが理解されよう。評価器はその後、マスクされたユーザ入力をＣＳＰに送り（３９０）、ＣＳＰがそれらを復号化する（３９５）。ＣＳＰは次いでガーブル回路を用意し（３５０）、その回路が評価器からマスクを受け取って入力のマスクを解除し（３５６）、その後計数を行い、それをガーブル化し、評価器に送る（３６０）。（プロキシでない、平文の）紛失通信３４４を通じて、評価器は、マスクされたデータのガーブル値を取得し、その後それらを使用して回路を評価する。この実装は、ユーザが自身の入力を提出した後はプロトコルを「離れる」ことができ（すなわちオンラインのままでいることを必要とされない）、またＣＳＰ内での復号化を必要としないという利点を有する。
【００８５】
同じく図３のフローチャート３００を満たす本発明の第４の実施形態では、ユーザは形態（ｔｏｋｅｎ＿ｉｄ，重み）の入力を提出し、重みは、例えばキーワードがコーパスに出現する頻度、すなわちユーザにとってのその重要性に対応する。レコードが、閲覧された映画および／または評点である場合には、重みは評点に対応する。すると、回路に適宜変更を加えることにより、本発明の方法により、映画ごとの平均評点が算出されることができる。映画にいくつの評点が対応するのかを計数することと併せて、「右から左」へのパス（ステップＣ３）ですべての評点の和も得る。評点の和と総数の比は平均の評点を生じ、同様の変更により他の統計（分散など）も算出されることができる。
【００８６】
本発明の原理は、各種形態のハードウェア、ソフトウェア、ファームウェア、特殊目的プロセッサー、またはそれらの組み合わせで実装され得ることを理解されたい。好ましくは、本発明の原理はハードウェアとソフトウェアの組み合わせとして実装される。さらに、ソフトウェアは、好ましくは、プログラム記憶装置に有形に具現化されたアプリケーションプログラムとして実装される。アプリケーションプログラムは、任意の適切なアーキテクチャを備えるマシンにアップロードされ、マシンによって実行されることができる。好ましくは、マシンは、１または複数の中央演算処理装置（ＣＰＵ）、ランダムアクセスメモリ（ＲＡＭ）、および入出力（Ｉ／Ｏ）インターフェースなどのハードウェアを有するコンピュータプラットフォーム上で実装される。コンピュータプラットフォームは、オペレーティングシステムおよびマイクロ命令コードも含む。本明細書に記載される各種プロセスおよび機能は、オペレーティングシステムを介して実行される、マイクロ命令コードの一部であっても、アプリケーションプログラムの一部（またはそれらの組み合わせ）であってもよい。また、追加的なデータ記憶装置や印刷装置など、各種の他の周辺機器がコンピュータプラットフォームに接続されてよい。
【００８７】
図５は、本発明の原理を実装するために使用される最小限の演算環境５００のブロック図を示す。演算環境５００は、プロセッサー５１０、および少なくとも１つの（好ましくは１つよりも多い）Ｉ／Ｏインターフェース５２０を含む。Ｉ／Ｏインターフェースは有線である場合もワイヤレスである場合もあり、ワイヤレスの実装では、適切なワイヤレス通信プロトコルと共に事前に構成されて、演算環境５００が世界規模のネットワーク（例えばインターネット）で動作し、他のコンピュータやサーバー（例えばクラウドに基づく演算サーバーや記憶サーバー）と通信することにより、本発明の原理が、例えばエンドユーザに遠隔から提供されるサービスとしてのソフトウェア（ＳＡＡＳ）機能として提供されるようにする。１または複数のメモリ５３０および／または記憶装置（ＨＤＤ）５４０も演算環境５００内に提供される。演算環境５００または複数のコンピュータ環境５００は、本発明の原理の一実施形態により、カウンタＣ１〜Ｃ４（図４）に対応するプロトコルＰ１〜６（図３）を実装することができる。詳細には、本発明の原理の一実施形態では、演算環境５００が評価器２３０を実装し、別の演算環境５００がＣＳＰ２５０を実装し、ソースが１または複数のコンピュータ環境５００を含むことができ、各環境５００は、別々のユーザ２１０に関連付けられ、評価器２３０およびＣＳＰ２５０と通信するために使用される、これらに制限されないが、デスクトップコンピュータ、携帯電話、スマートフォン、腕時計型電話機、タブレットコンピュータ、携帯情報端末（ＰＤＡ）、ネットブック、およびラップトップコンピュータを含む。また、ＣＳＰ２５０は独立したプロセッサーとして、またはソースプロセッサーによって実行されるコンピュータプログラムとしてソースに含まれるか、またはそれらと同等にソースの各ユーザ２１０のコンピュータ環境に含まれることができる。
【００８８】
さらに、添付図面に示すシステムを構成する構成要素および方法のステップの一部はソフトウェアとして実装されることが好ましいため、システム構成要素（または処理ステップ）間の実際の接続は本発明の原理がプログラミングされる方式に応じて異なる可能性があることを理解されたい。本明細書の教示から、当業者は、本発明の原理の上記および同様の実装または構成を企図することができよう。
【００８９】
本明細書では添付図面を参照して例示的実施形態が説明されたが、本発明の原理は上記の通りの実施形態に制限されず、本発明の原理の範囲または主旨から逸脱することなく、当分野の当業者により様々な変更および改変が実施されることが可能であることを理解されたい。そのような変更および改変はすべて、添付の特許請求の範囲に述べられる本発明の原理の範囲内に含まれることが意図される。
【図１】
2016509268.tif 000019
【図２】
2016509268.tif 000020
【図３Ａ】
2016509268.tif 000021
【図３Ｂ】
2016509268.tif 000022
【図３Ｃ】
2016509268.tif 000023
【図３Ｄ】
2016509268.tif 000024
【図３Ｅ】
2016509268.tif 000025
【図３Ｆ】
2016509268.tif 000026
【図３Ｇ】
2016509268.tif 000027
【図４】
2016509268.tif 000028
【図５】
2016509268.tif 000029
【国際調査報告】
2016509268.tif 000030
2016509268.tif 000031
2016509268.tif 000032