(57)【要約】      （修正有）【課題】秘匿共通集合演算の計算量を効果的に削減する秘匿共通集合演算システムを提供する。【解決手段】秘匿共通集合演算システムは、サーバと、３以上の端末とを備える。３以上の端末の各々は、当該端末の保持する集合の要素をデータ構造化することによってビット列を生成し、当該ビット列をサーバへと送信する。サーバは、３以上の端末をグルーピングするための複数の組み合わせのうち最適な組み合わせを上記ビット列に基づいて探索し、探索した最適な組み合わせに応じて３以上の端末の各々に対して当該端末が属するグループを通知する。３以上の端末の各々は、当該端末が属するグループ内で秘匿共通集合演算を行う。【選択図】図５
2014157264.tif 000002
【特許請求の範囲】
【請求項１】
サーバと、３以上の端末とを具備し、
前記３以上の端末の各々は、当該端末の保持する集合の要素をデータ構造化することによってビット列を生成し、当該ビット列を前記サーバへと送信し、
前記サーバは、前記３以上の端末をグルーピングするための複数の組み合わせのうち最適な組み合わせを前記ビット列に基づいて探索し、探索した最適な組み合わせに応じて前記３以上の端末の各々に対して当該端末が属するグループを通知し、
前記３以上の端末の各々は、当該端末が属するグループ内で秘匿共通集合演算を行う、
秘匿共通集合演算システム。
【請求項２】
前記サーバは、所与の組み合わせに含まれる複数のグループの各々に属する端末のビット列同士の類似度の総和を算出し、前記総和が最小となる組み合わせを前記最適な組み合わせとして探索する、請求項１の秘匿共通集合演算システム。
【請求項３】
所与のグループの前記類似度は、当該グループに属する端末のビット列同士の論理積に含まれる１の総数である、請求項２の秘匿共通集合演算システム。
【請求項４】
前記サーバは、いずれかのグループ内で行われた前記秘匿共通集合演算によって当該グループ内の共通集合が空集合になると、前記３以上の端末に対して秘匿共通集合演算の終了を指示する、請求項１の秘匿共通集合演算システム。
【請求項５】
３以上の端末の各々が、当該端末の保持する集合の要素をデータ構造化することによってビット列を生成し、当該ビット列をサーバへと送信することと、
前記サーバが、前記３以上の端末をグルーピングするための複数の組み合わせのうち最適な組み合わせを前記ビット列に基づいて探索し、探索した最適な組み合わせに応じて前記３以上の端末の各々に対して当該端末が属するグループを通知することと、
前記３以上の端末の各々が、当該端末が属するグループ内で秘匿共通集合演算を行うことと
を具備する、秘匿共通集合演算方法。
【請求項６】
前記サーバは、所与の組み合わせに含まれる複数のグループの各々に属する端末のビット列同士の類似度の総和を算出し、前記総和が最小となる組み合わせを前記最適な組み合わせとして探索する、請求項５の秘匿共通集合演算方法。
【請求項７】
所与のグループの前記類似度は、当該グループに属する端末のビット列同士の論理積に含まれる１の総数である、請求項６の秘匿共通集合演算方法。
【請求項８】
前記サーバが、いずれかのグループ内で行われた前記秘匿共通集合演算によって当該グループ内の共通集合が空集合になると、前記３以上の端末に対して秘匿共通集合演算の終了を指示することを更に具備する、請求項５の秘匿共通集合演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘匿共通集合演算に関する。
【背景技術】
【０００２】
従来、様々なアプリケーションにおいて、データベースに保存された複数の集合に含まれる共通の要素からなる共通集合を導出する共通集合演算が利用されている。例えば、ＳＮＳ（Ｓｏｃｉａｌ  Ｎｅｔｗｏｒｋｉｎｇ  Ｓｅｒｖｉｃｅ）において、ユーザが知り合いを容易に発見できるよう、当該ユーザに対して他のユーザとの間で共通する友人情報を共通集合演算によって導出し、これを表示する機能が活用されている。
【０００３】
全ての集合要素が友人情報のような公開情報に相当するならば、複数の集合に含まれる要素同士を単純に比較することによって、共通集合を導出することができる。しかしながら、一部の要素がプライバシ情報に相当する場合には、共通集合演算を可能な限り秘匿化することが好ましい。具体的には、各ユーザに関連付けられる集合の要素は、共通集合演算を実行するサーバ及び他のユーザに対して基本的に秘匿され、複数の集合間で共通する一部の要素に限ってこれらサーバ及び複数のユーザに対して開示されることが望まれる。しかしながら、共通集合演算を秘匿化するためには、通常よりも複雑なプロトコルが求められる。
【０００４】
具体的には、要素を暗号化またはハッシュ化してから演算を行うことによって、各集合に含まれる要素を秘匿しながら共通集合を導出する秘匿共通集合演算が提案されている（非特許文献１及び非特許文献２）。この秘匿共通集合演算は、共通集合に含まれない要素がプライバシ情報に相当する場合、必要以上の要素が公開されることが好ましくない場合などでの適用が期待されている。例えば、飛行機の乗客リストをテロリストのデータベースと照合する場合、グループ内でメンバのスケジュールを調整する場合などにこの秘匿共通集合演算を適用することによって、一般乗客のプライバシを守りつつテロリストを発見したり、グループの各メンバが他のメンバに全てのスケジュールを開示することなくスケジュールを調整したりすることが可能となる。
【０００５】
しかしながら、この秘匿共通集合演算は、暗号化処理、復号化処理、べき乗計算された数値を用いた演算などを伴う。即ち、この秘匿共通集合演算は、最低でも５１２ビットから１０２４ビット程度の桁の大きな数値を取り扱う必要がある。故に、この秘匿共通集合演算は、必要な計算時間及びハードウェアリソースが大きくなりがちである。特に、演算能力の高いサーバではなくユーザの所持するスマートフォン、タブレットなどの情報処理端末が要素を暗号化またはハッシュ化するのであれば、当該情報処理端末に備えられるメモリ及びＣＰＵの性能が概して高くないことを考慮して、暗号化またはハッシュ化される要素数を適切に絞り込むことが好ましい。
【０００６】
また、単純な秘匿共通集合演算は、各集合の全ての要素の取り得る組み合わせを確認するものであるが、これによると集合数が増えるほど計算量は指数関数的に増大する。係る組み合わせ数を削減するために、複数の集合からなるグループをより小さなグループに分割し、秘匿共通集合演算を繰り返し実行する技法も提案されている（非特許文献３）。
【０００７】
更に、秘匿共通集合演算の高速化に関して、非特許文献４に開示されたブルームフィルタ（Ｂｌｏｏｍ  ｆｉｌｔｅｒ）を利用した技法が提案されている（非特許文献５）。この技法によれば、プレイヤー１は自己の集合の各要素に対してハッシュ計算を行い、このハッシュ計算の結果に基づいて自己の集合の各要素を要素数の２倍程度のビット長のビット列としてデータ構造化する。そして、プレイヤー２は、自己の集合の各要素をプレイヤー１と同一の方法でビット列としてデータ構造化し、このビット列をプレイヤー１のビット列と照合することによって、プレイヤー１との間で共通の要素が含まれているかどうかを判定する。この技術によれば、集合の各要素は要素数の２倍程度のビット長の短いビット列としてデータ構造化されるので、高速演算が可能であると共に必要なハードウェアリソースも小さい。反面、この技術には、偽陽性の問題が生じる。例えば、プレイヤー２は、プレイヤー１の集合に含まれず、かつ、プレイヤー２の集合に含まれる要素と、共通集合の真の要素とを区別することができない。そして、偽陽性の要素を完全に除去するためには、前述の暗号化またはハッシュ化を用いた秘匿共通集合演算などが必要となる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ｍｉｃｈａｅｌ  Ｊ．  Ｆｒｅｅｄｍａｎ，  Ｋｏｂｂｉ  Ｎｉｓｓｉｍ  ａｎｄ  Ｂｅｎｎｙ  Ｐｉｎｋａｓ：  “Ｅｆｆｉｃｉｅｎｔ  Ｐｒｉｖａｔｅ  Ｍａｔｃｈｉｎｇ  ａｎｄ  Ｓｅｔ Ｉｎｔｅｒｓｅｃｔｉｏｎ,”  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＥＵＲＯＣＲＹＰＴ  ２００４，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｖｏｌｕｍｅ  ３０２７，  ２００４，  ｐｐ  １−１９．
【非特許文献２】Ｒａｋｅｓｈ  Ａｇｒａｗａｌ，  Ａｌｅｘａｎｄｒｅ  Ｅｖｆｉｍｉｅｖｓｋｉ，  ａｎｄ  Ｒａｍａｋｒｉｓｈｎａｎ  Ｓｒｉｋａｎｔ：  “Ｉｎｆｏｒｍａｔｉｏｎ  ｓｈａｒｉｎｇ  ａｃｒｏｓｓ  ｐｒｉｖａｔｅ  ｄａｔａｂａｓｅｓ，”  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＳＩＧＭＯＤ  ’０３，  ＡＣＭ，    ２００３，  ｐｐ８６−９７．
【非特許文献３】Ｊａｉｄｅｅｐ  Ｖａｉｄｙａ，  Ｃｈｒｉｓ  Ｃｌｉｆｔｏｎ：  ”Ｓｅｃｕｒｅ  ｓｅｔ  ｉｎｔｅｒｓｅｃｔｉｏｎ  ｃａｒｄｉｎａｌｉｔｙ  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ａｓｓｏｃｉａｔｉｏｎ  ｒｕｌｅ  ｍｉｎｉｎｇ，”  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｅｃｕｒｉｔｙ，  Ｖｏｌｕｍｅ  １３，  Ｎｏ  ４，  ２００５，  ｐｐ５９３−６２２
【非特許文献４】Ｂｕｒｔｏｎ  Ｈ．  Ｂｌｏｏｍ：  “Ｓｐａｃｅ／ｔｉｍｅ  ｔｒａｄｅ−ｏｆｆｓ  ｉｎ  ｈａｓｈ  ｃｏｄｉｎｇ  ｗｉｔｈ  ａｌｌｏｗａｂｌｅ  ｅｒｒｏｒｓ，”  Ｃｏｍｍｕｎ．  ＡＣＭ，  １９７０，  ｖｏｌ．１３，  ｉｓｓｕｅ．７，  ｐｐ４２２−４２６．
【非特許文献５】Ｄｉｌｉｐ  Ｍａｎｙ，  Ｍａｒｔｉｎ  Ｂｕｒｋｈａｒｔ，  Ｘｅｎｏｆｏｎｔａｓ  Ｄｉｍｉｔｒｏｐｏｕｌｏｓ，  “Ｆａｓｔ  Ｐｒｉｖａｔｅ  Ｓｅｔ  Ｏｐｅｒａｔｉｏｎｓ  ｗｉｔｈ  ＳＥＰＩＡ，”  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ，  ＴＩＫ  ｒｅｐｏｒｔ  ｎｏ．  ３４５，  ＥＴＨ  Ｚｕｒｉｃｈ，  Ｍａｒｃｈ  １，  ２０１２．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明は、秘匿共通集合演算の計算量を効果的に削減することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の一態様に係る秘匿共通集合演算システムは、サーバと、３以上の端末とを備える。３以上の端末の各々は、当該端末の保持する集合の要素をデータ構造化することによってビット列を生成し、当該ビット列をサーバへと送信する。サーバは、３以上の端末をグルーピングするための複数の組み合わせのうち最適な組み合わせをビット列に基づいて探索し、探索した最適な組み合わせに応じて３以上の端末の各々に対して当該端末が属するグループを通知する。３以上の端末の各々は、当該端末が属するグループ内で秘匿共通集合演算を行う。
【発明の効果】
【００１１】
本発明によれば、秘匿共通集合演算の計算量を効果的に削減することが可能である。
【図面の簡単な説明】
【００１２】
【図１】第１の実施形態に係る秘匿共通集合演算システムを例示する図。
【図２】図１の秘匿共通集合演算システムの動作を例示するフローチャート。
【図３】図１の秘匿共通集合演算システムの動作を例示するフローチャート。
【図４】図１の秘匿共通集合演算システムの動作を例示するフローチャート。
【図５】図１の秘匿共通集合演算システムの動作を例示するシーケンス図。
【図６】図１の秘匿共通集合演算システムの動作例の説明図。
【図７】図１の秘匿共通集合演算システムの動作例の説明図。
【図８】図１の秘匿共通集合演算システムの動作例の説明図。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら実施形態の説明が述べられる。  
（第１の実施形態）  
第１の実施形態に係る秘匿共通集合演算システムは、図１に例示されるように、中間処理サーバと、ｋ（ｋは３以上の整数）人のプレイヤーに関連付けられたｋ個のプレイヤー端末（例えば、スマートフォン、タブレット、ＰＣなど）とを備える。中間処理サーバ及び各プレイヤー端末は、ネットワークを介してデータをやり取りできる。各プレイヤー端末は、複数の要素からなる集合を記憶部に保持している。例えば、プレイヤーｋに関連付けられたプレイヤー端末は、ｎ個の要素ｋ１，ｋ２，・・・ｋｎからなる集合Ｓｋを保持している。
【００１４】
尚、中間処理サーバは、プレイヤー端末と別体である必要はない。即ち、いずれかのプレイヤー端末が、当該プレイヤー端末の動作に加えて中間処理サーバの動作を行ってもよい。
中間処理サーバ及びｋ個のプレイヤー端末は、プロトコル上の手続に従ってｋ個の集合Ｓ１，Ｓ２，・・・，Ｓｋに対して秘匿共通集合演算を行うことによって、共通集合（Ｓ１∩Ｓ２∩・・・∩Ｓｋ）を導出する。この秘匿共通集合演算において、各プレイヤー端末に保持された集合の要素は秘匿される。例えば、集合Ｓｋの要素は、プレイヤーｋ以外のプレイヤーに関連付けられたプレイヤー端末にも中間処理サーバにも開示されない。
【００１５】
図１の秘匿共通集合演算システムは、図５に例示されるように動作できる。  
第１の手順として、各プレイヤー端末は、当該プレイヤー端末が保持する集合の要素数を示す情報を中間処理サーバへと送信する。図５の例によれば、プレイヤー１，２，・・・，ｋに関連付けられたプレイヤー端末は、集合Ｓ１，Ｓ２，・・・，Ｓｋの要素数ｎ１，ｎ２，・・・，ｎｋを示す情報を中間処理サーバに対して送信する。
【００１６】
第２の手順として、中間処理サーバは、各集合の要素数を用いて所定の演算を行うことによって後述されるビット列のビット長を導出し、当該ビット長を示す情報を各プレイヤー端末へと送信する。図５の例によれば、中間処理サーバは、要素数ｎ１，ｎ２，・・・，ｎｋの平均値Ａｖｅを所定の関数ｆ（ｘ）に代入することによってビット長Ｌｂを導出し、当該ビット長Ｌｂを示す情報を各プレイヤー端末へと送信する。
【００１７】
所定の関数ｆ（ｘ）は、例えば、変数ｘを２倍してから整数値に丸めるものであってよい。所定の関数ｆ（ｘ）は、プレイヤー端末間で事前に決定されていてもよい。また、中間処理サーバはビット長Ｌｂそのものではなく中間値（例えば、前述の平均値Ａｖｅ）を導出し、各プレイヤー端末が中間値からビット長Ｌｂを導出してもよい。
【００１８】
第３の手順として、各プレイヤー端末は、当該プレイヤー端末が保持する集合の要素を上記ビット長に基づいてデータ構造化することによってビット列を生成し、当該ビット列を中間処理サーバへと送信する。集合の要素は、例えばブルームフィルタを用いてデータ構造化される。この場合に、ビット列は、ブルームフィルタの結果に相当する。図５の例によれば、プレイヤー１，２，・・・，ｋのプレイヤー端末は、集合Ｓ１，Ｓ２，・・・，Ｓｋの要素をビット長Ｌｂに基づいてデータ構造化することによって、ビット列Ｂ１，Ｂ２，・・・，Ｂｋを生成し、当該ビット列Ｂ１，Ｂ２，・・・，Ｂｋを中間処理サーバへと送信する。
【００１９】
具体的には、各プレイヤー端末は、Ｌｂ個のビットからなるビット列を初期化する。ここで、ビット列の初期化とは、ビット列内の全てのビットを０にすることを意味する。それから、各プレイヤー端末は、当該プレイヤー端末が保持する集合の要素の各々に対して好ましくは２種類以上のハッシュ関数を用いてハッシュ計算を行い、導出されたハッシュ値に基づいてビット列を変更する。
【００２０】
ハッシュ関数は、Ｌｂ種類のハッシュ値を生成可能なものであって、好ましくは高い一様性を備える。また、ハッシュ関数は、プレイヤー端末間で事前に決定されてもよい。尚、中間処理サーバはハッシュ関数を使用しないので、ハッシュ関数はプレイヤー端末間に限って事前に決定及び共有されてもよい。中間処理サーバに対してハッシュ関数を秘匿することによって、プレイヤー以外の第三者が中間処理サーバに集約されたビット列から元の要素を復元するという事態をより確実に防止できる。勿論、一般に、ブルームフィルタの結果から元の要素を復元することは困難である。
【００２１】
各プレイヤー端末は、集合の要素の１つに対してハッシュ関数の１つを用いて当該要素のハッシュ値Ｈを生成してからビット列内のＨ番目のビットを１に変更する。係るビット列の変更処理は、各プレイヤー端末において、全要素及び全ハッシュ関数の組み合わせについて行われる。例えば、ハッシュ関数が２種類であるならば、プレイヤーｋのプレイヤー端末はビット列の変更処理を２ｎｋ回に亘って行う。
【００２２】
尚、ビット列の変更処理において、ハッシュ値の衝突が生じることがある。即ち、ハッシュ値Ｈが、既に生成されたハッシュ値と同じであるかもしれない。この場合には、ビット列のＨ番目のビットは１であるので、プレイヤー端末はビット列を変更しない。ハッシュ値の衝突は、ハッシュ関数の種類が多いほど発生しやすく、ビット長Ｌｂが短いほど発生しやすい。ハッシュ値の衝突は頻繁に生じるので、ブルームフィルタによって生成されたビット列から元の要素を推測することは困難である。
【００２３】
ハッシュ関数はＬｂ種類のハッシュ値を生成可能なものであると説明したが、ビット長Ｌｂを導出するよりも前にハッシュ関数を決定することも可能である。具体的には、プレイヤー端末は、事前に決定されたハッシュ関数を用いてハッシュ値を生成し、当該ハッシュ値をＬｂで除算することによって得られる剰余をＨとして扱ってもよい。
【００２４】
第４の手順として、中間処理サーバは、各プレイヤー端末からのビット列の論理積を演算し、演算結果に相当するビット列を各プレイヤー端末へと送信する。図５の例によれば、中間処理サーバは、ビット列Ｂ１，Ｂ２，・・・，Ｂｋの論理積を演算し、演算結果に相当するビット列Ｂｓｅｒｖｅｒをプレイヤー１，２，・・・，ｋのプレイヤー端末へと送信する。
【００２５】
ここで、全ての集合に共通する要素があるならば、全てのプレイヤー端末はビット列（即ち、ブルームフィルタの結果）Ｂ１，Ｂ２，・・・，Ｂｋにおいて当該要素のハッシュ値に対応する場所のビットを１に変更しているので、ビット列Ｂｓｅｒｖｅｒにおいてもこの場所のビットは１である。反対に、あるプレイヤー端末がビット列においてある要素のハッシュ値に対応する場所のビットを１に変更したにも関わらず、ビット列Ｂｓｅｒｖｅｒにおいてこの場所のビットが０であるならば、当該要素は少なくとも１つの他のプレイヤー端末が保持する集合に含まれていないから、共通集合の要素ではない。概括すれば、ビット列Ｂｓｅｒｖｅｒにおいて、共通集合の真の要素及び偽陽性の要素に関する場所のビットのみが１である。
【００２６】
第５の手順として、各プレイヤー端末は、中間処理サーバからのビット列に基づいて、当該プレイヤー端末が保持する集合を絞り込む。図５の例によれば、各プレイヤー端末は、中間処理サーバからのビット列Ｂｓｅｒｖｅｒに基づいて、当該プレイヤー端末が保持する集合Ｓ１，Ｓ２，・・・，Ｓｋを絞り込む。
【００２７】
具体的には、各プレイヤー端末は、ビット列の変更処理と同じく、集合の要素の１つに対してハッシュ関数の１つを用いて当該要素のハッシュ値Ｈを生成する。中間処理サーバからのビット列ＢｓｅｒｖｅｒのＨ番目のビットが０であれば、各プレイヤー端末はこの要素を集合から除外する。換言すれば、各プレイヤー端末は、ビット列Ｂｓｅｒｖｅｒにおいて、ある要素に基づいて生成された全てのハッシュ値に対応する場所のビットが１であるならば当該要素を集合に維持し、そうでなければ当該要素を集合から除外する。各プレイヤー端末は、全ての要素について係る絞り込み処理を行うことによって新たな集合を得る。新たな集合は、絞り込み処理を行う前の集合のサブセットに相当する。新たな集合は、共通集合の真の要素及び偽陽性の要素の一方または両方からなる。
【００２８】
第６の手順として、中間処理サーバは、各プレイヤー端末からのビット列に基づいて最適なグループの組み合わせを探索し、最適なグループを示す情報を各プレイヤー端末に通知する。この第６の手順は、前述の第５の手順と並列に実行することができる。図５の例によれば、中間処理サーバは、ビット列Ｂ１，Ｂ２，・・・，Ｂｋに基づいて最適なグループの組み合わせを探索し、最適なグループを示す情報を各プレイヤー端末に送信する。各プレイヤー端末は第６の手順において通知された情報に従ってグルーピングされ、各グループ（例えば、ペア）に属するプレイヤー端末同士で秘匿共通集合演算を実行する。具体的には、グループに属する全てのプレイヤー端末が、第５の手順を通じて得られた集合の各要素について暗号化またはハッシュ化を行い、中間処理サーバを介して暗号化またはハッシュ化された要素を互いにやり取りして比較することによって、偽陽性の要素を除外する。
【００２９】
尚、偽陽性の要素が除外されたことによって、あるグループに属するプレイヤー端末の共通集合が空集合になることがある。あるグループに属するプレイヤー端末の共通集合が空集合になることは、全体の共通集合もまた空集合であることを意味するので、これ以上の演算は無駄である。故に、プレイヤー端末は、中間処理サーバに空集合の発生を示す情報を送信する。中間処理サーバは、係る情報を受信すると、全てのプレイヤー端末に対して処理中断を指示する情報を送信して秘匿共通集合演算を打ち切らせる。秘匿共通集合演算の打ち切りによって、中間処理サーバ及びプレイヤー端末における無駄なリソース消費を削減することが可能となる。
【００３０】
ここで、最適なグループの組み合わせとは、秘匿共通集合演算の計算量を最小にする組み合わせを意味する。例えば、中間処理サーバは、任意の組み合わせについて、当該組み合わせに含まれる各グループに属するプレイヤー端末のビット列同士の類似度の総和を当該組み合わせの評価値として算出してもよい。そして、中間処理サーバは、評価値の最も小さい組み合わせを最適なグループの組み合わせとして探索してもよい。係るグループの組み合わせによれば、グループ内の共通集合の真の要素及び偽陽性の要素の数を少なくすることが可能となるので、秘匿共通集合演算において確認する必要のある要素の組み合わせの数も少なくなる。グループに属するプレイヤー端末のビット列同士の類似度は、これらビット列の論理積に含まれる１の総数であってもよい。
【００３１】
中間処理サーバは、最適なグループの組み合わせを探索するために、全ての組み合わせについて評価値を算出してもよい。例えば、プレイヤー端末が４つであって、グループがペアに相当するならば、｛（プレイヤー１，プレイヤー２），（プレイヤー３，プレイヤー４）｝，｛（プレイヤー１，プレイヤー３），（プレイヤー２，プレイヤー４）｝，｛（プレイヤー１，プレイヤー４），（プレイヤー２，プレイヤー３）｝の合計３通りの組み合わせが可能である。
【００３２】
尚、第５の手順及び第６の手順は必要に応じて繰り返されてもよい。この場合には、各グループを新たなプレイヤー端末と定義し、当該グループに属する全てプレイヤー端末のビット列の論理積を当該新たなプレイヤー端末のビット列と定義すればよい。
以下、図６、図７及び図８を用いて、図１の秘匿共通集合演算システムの動作例が説明される。この動作例によれば、４人のプレイヤー１，２，３及び４に関連付けられたプレイヤー端末が保持する集合Ｓ１，Ｓ２，Ｓ３及びＳ４の共通集合が導出される。
【００３３】
図６、図７及び図８の動作例において、集合Ｓ１＝｛１，２，３，４｝であり、集合Ｓ２＝｛１，２，３，５｝であり、集合Ｓ３＝｛１，８，９，１０｝であり、集合Ｓ４＝｛１，９，１０，１３｝である。
図６に例示されるように、第１の手順に従って、プレイヤー１のプレイヤー端末は集合Ｓ１の要素数＝４を中間処理サーバに通知し、プレイヤー２のプレイヤー端末は集合Ｓ２の要素数＝４を中間処理サーバに通知し、プレイヤー３のプレイヤー端末は集合Ｓ３の要素数＝４を中間処理サーバに通知し、プレイヤー４のプレイヤー端末は集合Ｓ４の要素数＝４を中間処理サーバに通知する。
【００３４】
第２の手順に従って、中間処理サーバは、通知された要素数を用いて所定の演算を行うことによってビット列のビット長Ｌｂ＝４を導出し、これを各プレイヤー端末に通知する。図６の動作例では、所定の演算は平均化である。即ち、中間処理サーバは、（４＋４＋４＋４）／４を演算することによって、Ｌｂ＝４を導出する。
【００３５】
第３の手順に従って、各プレイヤー端末は、Ｌｂ＝４ビットに基づいて当該プレイヤー端末の保持する集合の要素をデータ構造化することによってビット列を生成し、これを中間処理サーバへと送信する。まず、各プレイヤー端末は、図６に例示されるように、初期化されたビット列「００００」を生成する。それから、各プレイヤー端末は、図７に例示されるように、ハッシュ計算に基づいてビット列を変更する。尚、図７の動作例によれば、１種類のハッシュ関数Ｈ（ｘ）が使用され、Ｈ（ｘ）＝ｘ  ｍｏｄ  ４である。
【００３６】
プレイヤー１のプレイヤー端末は、集合Ｓ１＝｛１，２，３，４｝の各要素に対してハッシュ計算を行い、Ｈ（１）＝１、Ｈ（２）＝２、Ｈ（３）＝３及びＨ（４）＝０というハッシュ値を生成する。プレイヤー１のプレイヤー端末は、生成したハッシュ値に基づいて、ビット列Ｂ１の左から１番目、２番目、３番目及び４番目のビットを１にすることによって、ビット列Ｂ１を「１１１１」に変更する。
【００３７】
プレイヤー２のプレイヤー端末は、集合Ｓ２＝｛１，２，３，５｝の各要素に対してハッシュ計算を行い、Ｈ（１）＝１、Ｈ（２）＝２、Ｈ（３）＝３及びＨ（５）＝１というハッシュ値を生成する。プレイヤー２のプレイヤー端末は、生成したハッシュ値に基づいて、ビット列Ｂ２の左から２番目、３番目及び４番目のビットを１にすることによって、ビット列Ｂ２を「０１１１」に変更する。
【００３８】
プレイヤー３のプレイヤー端末は、集合Ｓ３＝｛１，８，９，１０｝の各要素に対してハッシュ計算を行い、Ｈ（１）＝１、Ｈ（８）＝０、Ｈ（９）＝１及びＨ（１０）＝２というハッシュ値を生成する。プレイヤー３のプレイヤー端末は、生成したハッシュ値に基づいて、ビット列Ｂ３の左から１番目、２番目及び３番目のビットを１にすることによって、ビット列Ｂ３を「１１１０」に変更する。
【００３９】
プレイヤー４のプレイヤー端末は、集合Ｓ４＝｛１，９，１０，１３｝の各要素に対してハッシュ計算を行い、Ｈ（１）＝１、Ｈ（９）＝１、Ｈ（１０）＝２及びＨ（１３）＝１というハッシュ値を生成する。プレイヤー４のプレイヤー端末は、生成したハッシュ値に基づいて、ビット列Ｂ４の左から２番目及び３番目のビットを１にすることによって、ビット列Ｂ４を「０１１０」に変更する。
【００４０】
第４の手順に従って、中間処理サーバは、各プレイヤー端末からのビット列Ｂ１＝「１１１１」，Ｂ２＝「０１１１」，Ｂ３＝「１１１０」及びＢ４＝「０１１０」の論理積を演算し、演算結果に相当するビット列Ｂｓｅｒｖｅｒ＝「０１１０」を各プレイヤー端末へと送信する。第４の手順において生成されるビット列Ｂｓｅｒｖｅｒ＝「０１１０」は、各プレイヤー端末からのビット列Ｂ１＝「１１１１」，Ｂ２＝「０１１１」，Ｂ３＝「１１１０」及びＢ４＝「０１１０」の各々に比べて疎であるか少なくとも同一である。
【００４１】
第５の手順に従って、各プレイヤー端末は、図８に例示されるように、中間処理サーバからのビット列Ｂｓｅｒｖｅｒ＝「０１１０」に基づいて、当該プレイヤー端末が保持する集合を絞り込む。
プレイヤー１のプレイヤー端末は、集合Ｓ１＝｛１，２，３，４｝の各要素に対してハッシュ計算を行い、Ｈ（１）＝１、Ｈ（２）＝２、Ｈ（３）＝３及びＨ（４）＝０というハッシュ値を生成する。ビット列Ｂｓｅｒｖｅｒ＝「０１１０」のうち左から１番目のビット及び４番目のビットは０である。故に、プレイヤー１のプレイヤー端末は、ハッシュ値Ｈ（４）＝０の元となる要素「４」及びハッシュ値Ｈ（３）＝３の元となる要素「３」を集合Ｓ１から除外することによって、新たな集合Ｓ１’＝｛１，２｝を得る。
【００４２】
プレイヤー２のプレイヤー端末は、集合Ｓ２＝｛１，２，３，５｝の各要素に対してハッシュ計算を行い、Ｈ（１）＝１、Ｈ（２）＝２、Ｈ（３）＝３及びＨ（５）＝１というハッシュ値を生成する。ビット列Ｂｓｅｒｖｅｒ＝「０１１０」のうち左から１番目のビット及び４番目のビットは０である。故に、プレイヤー２のプレイヤー端末は、ハッシュ値Ｈ（３）＝３の元となる要素「３」を集合Ｓ２から除外することによって、新たな集合Ｓ２’＝｛１，２，５｝を得る。
【００４３】
プレイヤー３のプレイヤー端末は、集合Ｓ３＝｛１，８，９，１０｝の各要素に対してハッシュ計算を行い、Ｈ（１）＝１、Ｈ（８）＝０、Ｈ（９）＝１及びＨ（１０）＝２というハッシュ値を生成する。ビット列Ｂｓｅｒｖｅｒ＝「０１１０」のうち左から１番目のビット及び４番目のビットは０である。故に、プレイヤー３のプレイヤー端末は、ハッシュ値Ｈ（８）＝０の元となる要素「８」を集合Ｓ３から除外することによって、新たな集合Ｓ３’＝｛１，９，１０｝を得る。
【００４４】
プレイヤー４のプレイヤー端末は、集合Ｓ４＝｛１，９，１０，１３｝の各要素に対してハッシュ計算を行い、Ｈ（１）＝１、Ｈ（９）＝１、Ｈ（１０）＝２及びＨ（１３）＝１というハッシュ値を生成する。ビット列Ｂｓｅｒｖｅｒ＝「０１１０」のうち左から１番目のビット及び４番目のビットは０である。故に、プレイヤー４のプレイヤー端末は、集合Ｓ４の全ての要素を維持することによって、新たな集合Ｓ４＝Ｓ４’＝｛１，９，１０，１３｝を得る。
【００４５】
これら新たな集合Ｓ１’，Ｓ２’，Ｓ３’及びＳ４’において、共通集合の真の要素である「１」は失われておらず、適度に偽陽性の要素が残っている。例えば、Ｓ４’の「１３」のように他の集合と全く一致していない要素も偽陽性を示す。
第６の手順に従って、中間処理サーバは、各プレイヤー端末からのビット列Ｂ１＝「１１１１」，Ｂ２＝「０１１１」，Ｂ３＝「１１１０」及びＢ４＝「０１１０」に基づいて最適なグループの組み合わせを探索し、最適なグループを示す情報を各プレイヤー端末に通知する。図８の動作例において、グループはペアに相当する。
【００４６】
中間処理サーバは、｛（プレイヤー１，プレイヤー２），（プレイヤー３，プレイヤー４）｝，｛（プレイヤー１，プレイヤー３），（プレイヤー２，プレイヤー４）｝，｛（プレイヤー１，プレイヤー４），（プレイヤー２，プレイヤー３）｝の合計３通りの組み合わせについて前述の評価値を算出する。
【００４７】
具体的には、中間処理サーバは、｛（プレイヤー１，プレイヤー２），（プレイヤー３，プレイヤー４）｝という組み合わせについて、Ｂ１∩Ｂ２＝「０１１１」及びＢ３∩Ｂ４＝「０１１０」に含まれる１の総数である「５（＝３＋２）」を評価値として算出する。
【００４８】
中間処理サーバは、｛（プレイヤー１，プレイヤー３），（プレイヤー２，プレイヤー４）｝という組み合わせについて、Ｂ１∩Ｂ３＝「１１１０」及びＢ２∩Ｂ４＝「０１１０」に含まれる１の総数である「５（＝３＋２）」を評価値として算出する。
中間処理サーバは、｛（プレイヤー１，プレイヤー４），（プレイヤー２，プレイヤー３）｝という組み合わせについて、Ｂ１∩Ｂ４＝「０１１０」及びＢ２∩Ｂ３＝「０１１０」に含まれる１の総数である「４（＝２＋２）」を評価値として算出する。
【００４９】
従って、図８の動作例によれば、評価値が最小である｛（プレイヤー１，プレイヤー４），（プレイヤー２，プレイヤー３）｝という組み合わせを最適なグループの組み合わせとして各プレイヤー端末に通知する。
プレイヤー１のプレイヤー端末及びプレイヤー４のプレイヤー端末は、中間処理サーバを介して秘匿共通集合演算を行う。集合Ｓ１’の要素数は２であり、集合Ｓ４’の要素数は４であるので、２×４＝８通りの組み合わせについて確認が必要である。秘匿共通集合演算の結果、集合Ｓ１’に含まれる偽陽性の要素｛２，３｝が除外され、集合Ｓ４’に含まれる偽陽性の要素｛９，１０，１３｝が除外される。
【００５０】
同様に、プレイヤー２のプレイヤー端末及びプレイヤー３のプレイヤー端末は、中間処理サーバを介して秘匿共通集合演算を行う。集合Ｓ２’の要素数は３であり、集合Ｓ３’の要素数は３であるので、３×３＝９通りの組み合わせについて確認が必要である。秘匿共通集合演算の結果、集合Ｓ２’に含まれる偽陽性の要素｛２，５｝が除外され、集合Ｓ３’に含まれる偽陽性の要素｛９，１０｝が除外される。
【００５１】
最後に、プレイヤー１及び４のプレイヤー端末ならびにプレイヤー２及び３のプレイヤー端末は、中間処理サーバを介して秘匿共通集合演算を行う。集合Ｓ１∩Ｓ４の要素数は１であり、集合Ｓ２∩Ｓ３の要素数は１であるので、１×１＝１通りの組み合わせについて各荷が必要である。秘匿共通集合演算の結果、共通集合として｛１｝が得られる。
【００５２】
前述の｛（プレイヤー１，プレイヤー４），（プレイヤー２，プレイヤー３）｝というグルーピングによれば、秘匿共通集合演算の全体で合計１８（＝８＋９＋１）通りの組み合わせを確認する必要がある。仮に、グルーピング（即ち、第６の手順）を省略して４つのプレイヤー端末間でまとめて秘匿共通集合演算を行うのであれば、合計７２（＝２×３×３×４）通りの組み合わせを確認する必要がある。また、ブルームフィルタを利用した集合の絞り込み（即ち、第１乃至第５の手順）を省略して４つのプレイヤー端末間でまとめて秘匿共通集合演算を行うのであれば、合計２５６（＝４×４×４×４）通りの組み合わせを確認する必要がある。これらの数値例から、グルーピングは秘匿共通集合演算における計算量及びリソース消費を効果的に削減することが確認された。
【００５３】
尚、｛（プレイヤー１，プレイヤー２），（プレイヤー３，プレイヤー４）｝というグルーピングが採用されていたならば、秘匿共通集合演算の全体で合計２４（＝６＋１２＋６）通りの組み合わせを確認する必要がある。或いは、｛（プレイヤー１，プレイヤー３），（プレイヤー２，プレイヤー４）｝というグルーピングが採用されていたならば、合計１９（＝６＋１２＋１）通りの組み合わせを確認する必要がある。これらの数値例から、前述の評価値の最も小さい組み合わせに従ってグルーピングすると、他の組み合わせに従ってグルーピングする場合に比べて、秘匿共通集合演算における計算量及びリソース消費をいっそう効果的に削減できることが確認された。
【００５４】
以下、図２、図３及び図４を用いて、図１の秘匿共通集合演算システムにおける中間処理サーバ及びプレイヤーｋのプレイヤー端末の動作例が説明される。尚、以降の説明は、プレイヤーｋのプレイヤー端末に限られず他の任意のプレイヤー端末についてもあてはまる。また、図２、図３及び図４の動作例において、２種類のハッシュ関数が用いられているが、１種類または３種類以上のハッシュ関数が用いられてもよい。
【００５５】
最初に中間処理サーバは、プレイヤーｋを含む各プレイヤーのプレイヤー端末へ、開始メッセージを送信する（ステップＳ１０１）。プレイヤーｋのプレイヤー端末は、中間処理サーバから開始メッセージを受信し（ステップＳ２０１）、集合Ｓｋの要素数ｎｋを示す情報を中間処理サーバへと送信する（ステップＳ２０２）。
【００５６】
中間処理サーバは、プレイヤーｋを含む各プレイヤーのプレイヤー端末から要素数ｎ１，ｎ２，・・・，ｎｋを示す情報を受信し（ステップＳ１０２）、要素数ｎ１，ｎ２，・・・，ｎｋに基づいてビット列のビット長Ｌｂを導出する（ステップＳ１０３）。
【００５７】
中間処理サーバは、プレイヤーｋを含む各プレイヤーのプレイヤー端末へ、ビット長Ｌｂを示す情報を送信する（ステップＳ１０４）。更に、中間処理サーバは、Ｌｂビットのビット列Ｂｓｅｒｖｅｒを生成する（ステップｓ１０５）
プレイヤーｋのプレイヤー端末は、ビット長Ｌを示す情報を受信し（ステップＳ２０３）、Ｌｂビットのビット列Ｂｋを生成する（ステップＳ２０４）。尚、ステップＳ２０４において、ビット列Ｂｋのビットは全て０である。プレイヤーｋのプレイヤー端末は、ステップＳ２０５乃至ステップＳ２１０のループを通じて、ビット列Ｂｋを変更する。このループは、ｉ＝１，２，・・・，ｍについて繰り返される。
【００５８】
ステップＳ２０５において、プレイヤーｋのプレイヤー端末は、第１のハッシュ関数Ｈ１（ｘ）を用いて集合Ｓｋの第ｉ番目の要素であるｋｉをハッシュ化することによって、ハッシュ値Ｈ１（ｋｉ）を生成する。ビット列ＢｋのＨ１（ｋｉ）番目のビットが１であれば処理はステップＳ２０８へと進み、そうでなければ処理はステップＳ２０７へと進む（ステップＳ２０６）。ステップＳ２０７において、プレイヤーｋのプレイヤー端末は、ビット列ＢｋのＨ１（ｋｉ）番目のビットを１にする。ステップＳ２０７の終了後に、処理はステップＳ２０８へと進む。
【００５９】
ステップＳ２０８において、プレイヤーｋのプレイヤー端末は、第２のハッシュ関数Ｈ２（ｘ）を用いてｋｉをハッシュ化することによって、ハッシュ値Ｈ２（ｋｉ）を生成する。ビット列ＢｋのＨ２（ｋｉ）番目のビットが１であればループの終了判定が行われ、そうでなければ処理はステップＳ２１０へと進む（ステップＳ２０９）。ステップＳ２１０において、プレイヤーｋのプレイヤー端末は、ビット列ＢｋのＨ２（ｋｉ）番目のビットを１にする。ステップＳ２１０の終了後に、ループの終了判定が行われる。集合Ｓｋの全ての要素が処理済みであるならばループは終了し、そうでなければ未処理の要素に関してループが続行する。
【００６０】
ステップＳ２０５乃至ステップＳ２１０のループ終了後に、プレイヤーｋのプレイヤー端末は、ビット列Ｂｋを中間処理サーバへと送信する（ステップＳ２１１）。中間処理サーバは、プレイヤーｋを含む各プレイヤーのプレイヤー端末からビット列Ｂ１，・・・，Ｂｋを受信する（ステップＳ１０６）。
【００６１】
中間処理サーバは、ビット列Ｂ１，・・・，Ｂｋの論理積を演算し、演算結果をビット列Ｂｓｅｒｖｅｒに代入する（ステップＳ１０７）。中間処理サーバは、プレイヤーｋを含む各プレイヤーのプレイヤー端末へ、ビット列Ｂｓｅｒｖｅｒを送信する（ステップＳ１０８）。プレイヤーｋのプレイヤー端末は、中間処理サーバからビット列Ｂｓｅｒｖｅｒを受信する（ステップＳ２１２）。
【００６２】
プレイヤーｋのプレイヤー端末は、新たな集合Ｓｋ’を生成し、これを空集合に初期化する（ステップＳ２１３）。プレイヤーｋのプレイヤー端末は、ステップＳ２１４乃至ステップＳ２１８のループを通じて、集合Ｓｋの要素をビット列Ｂｓｅｒｖｅｒに基づいて絞り込んだ新たな集合Ｓｋ’を得る。このループは、ｉ＝１，２，・・・，ｍについて繰り返される。
【００６３】
ステップＳ２１４において、プレイヤーｋのプレイヤー端末は、第１のハッシュ関数Ｈ１（ｘ）を用いて集合Ｓｋの第ｉ番目の要素であるｋｉをハッシュ化することによって、ハッシュ値Ｈ１（ｋｉ）を生成する。ビット列ＢｓｅｒｖｅｒのＨ１（ｋｉ）番目のビットが１であれば処理はステップＳ２１６に進み、そうでなければループの終了判定が行われる（ステップＳ２１５）。
【００６４】
ステップＳ２１６において、プレイヤーｋのプレイヤー端末は、第２のハッシュ関数Ｈ２（ｘ）を用いてｋｉをハッシュ化することによって、ハッシュ値Ｈ２（ｋｉ）を生成する。ビット列ＢｓｅｒｖｅｒのＨ２（ｋｉ）番目のビットが１であれば処理はステップＳ２１８に進み、そうでなければループの終了判定が行われる（ステップＳ２１７）。
【００６５】
ステップＳ２１８において、プレイヤーｋのプレイヤー端末は、要素ｋｉを集合Ｓｋ’に加える。ステップＳ２１８の終了後に、ループの終了判定が行われる。集合Ｓｋの全ての要素が処理済みであるならばループは終了し、そうでなければ未処理の要素に関してループが続行する。
【００６６】
他方、中間処理サーバは、ステップＳ１０９のループを通じて、プレイヤー１，２，・・・ｋのプレイヤー端末のうち組み合わせることのできる全てのペアについて当該ペアに属するプレイヤー端末のビット列同士の類似度Ｃを算出する。所与のペアの類似度Ｃは、当該ペアに属するプレイヤー端末のビット列同士の論理積に含まれる１の総数である。そして、中間処理サーバは、ペアの組み合わせのうち類似度Ｃの総和が最小の組み合わせＧ＝｛ｇ１，ｇ２，・・・，ｇｌ｝を探索する（ステップＳ１１０）。
【００６７】
中間処理サーバは、各プレイヤー端末へ、当該プレイヤー端末の属するグループを示す情報を送信する（ステップＳ１１１）。具体的には、中間処理サーバは、プレイヤーｋのプレイヤー端末が属するグループｇｌを示す情報を当該プレイヤー端末へと送信する。
【００６８】
プレイヤーｋのプレイヤー端末は、当該プレイヤー端末が属するグループｇｌを示す情報を受信する（ステップＳ２１９）。プレイヤーｋのプレイヤー端末は、集合Ｓｋ’に含まれる各要素について、グループｇｌ内で秘匿共通集合演算を行う（ステップＳ２２０）。プレイヤーｋのプレイヤー端末は、秘匿共通集合演算の結果、グループｇｌ内の共通集合をＳｋ’’として獲得する（ステップＳ２２１）。尚、グループｇｌ内の共通集合をＳｋ’’が空集合であるならば処理はステップＳ２２８に進み、そうでなければプレイヤーｋのプレイヤー端末は中間処理サーバから新たなグループが通知されるのを待機する（ステップＳ２２２）。
【００６９】
他方、中間処理サーバは、更なるグルーピングを行う。具体的には、中間処理サーバは、ステップＳ１１２のループを通じて、グループｇ１，・・・，ｇｌのうち組み合わせることのできる全てのペアについて当該ペアに属するプレイヤー端末のビット列同士の類似度Ｃ’を算出する。所与のペアの類似度Ｃ’は、当該ペアに属するプレイヤー端末のビット列同士の論理積に含まれる１の総数である。そして、中間処理サーバは、ペアの組み合わせのうち類似度Ｃ’の総和が最小の組み合わせＧ＝｛ｇ１’，ｇ２’，・・・，ｇｌ’｝を探索する（ステップＳ１１３）。中間処理サーバは、各プレイヤー端末へ、当該プレイヤー端末の属するグループを示す情報を送信する（ステップＳ１１４）。具体的には、中間処理サーバは、プレイヤーｋのプレイヤー端末が属するグループｇｌ’を示す情報を当該プレイヤー端末へと送信する。尚、ステップＳ１１３において探索された組み合わせに含まれるグループの総数が１であるならば処理はステップＳ１１６に進み、そうでなければ処理がステップＳ１１２のループに戻って中間処理サーバは更なるグルーピングを行う（ステップＳ１１５）。
【００７０】
プレイヤーｋのプレイヤー端末は、当該プレイヤー端末が属するグループｇｌ’を示す情報を受信する（ステップＳ２２３）。プレイヤーｋのプレイヤー端末は、集合Ｓｋ’’に含まれる各要素について、グループｇｌ’内で秘匿共通集合演算を行う（ステップＳ２２４）。プレイヤーｋのプレイヤー端末は、秘匿共通集合演算の結果、グループｇｌ’内の共通集合をＳｋ’’’として獲得する（ステップＳ２２５）。それから、プレイヤーｋのプレイヤー端末は、中間処理サーバから新たなグループが通知されるのを待機する。新たなグループが通知されれば処理はステップＳ２２３に戻り、そうでなければ処理はステップＳ２２７へと進む（ステップＳ２２６）。尚、図示されていないが、グループｇｌ’内の共通集合をＳｋ’’’が空集合であるならば処理はステップＳ２２８に進んでもよい。
【００７１】
ステップＳ１１６において、中間処理サーバは、プレイヤーｋを含む各プレイヤーのプレイヤー端末へ、終了メッセージを送信して動作終了する。ステップＳ２２７において、プレイヤーｋのプレイヤー端末は終了メッセージを受信して動作終了する。
ステップＳ２２８において、プレイヤーｋのプレイヤー端末は、空集合の発生を示す情報を中間処理サーバへと送信する。中間処理サーバは、プレイヤーｋまたは他のプレイヤーのプレイヤー端末から空集合の発生を示す情報を受信する（ステップＳ１１７）。それから、中間処理サーバは、プレイヤーｋを含む各プレイヤーのプレイヤー端末へ、処理中断を指示する情報を送信する（ステップＳ１１８）。ステップＳ１１８の終了後に処理はステップＳ１１６へと進む。プレイヤーｋのプレイヤー端末は、処理中断を指示する情報を受信する（ステップＳ２２９）。ステップＳ２２９の終了後に、処理はステップＳ２２７へと進む。
【００７２】
以上説明したように、第１の実施形態に係る秘匿共通集合演算システムにおいて、プレイヤー端末は当該プレイヤー端末の保持する集合の要素を例えばブルームフィルタを用いてデータ構造化することによってビット列を生成する。中間処理サーバは、プレイヤー端末をグルーピングするための最適な組み合わせをこれらのビット列に基づいて探索する。そして、プレイヤー端末は、中間処理サーバから通知されたグループ内で秘匿共通集合演算を行う。上記最適な組み合わせに従ってグルーピングを行うことによって、秘匿共通集合演算の対象となる組み合わせの総数は効果的に削減される。従って、この秘匿共通集合演算システムによれば、秘匿共通集合演算における計算量及びリソース消費を効果的に削減することができる。
【００７３】
尚、ブルームフィルタを利用した集合の絞り込み及びグルーピングは、主にハッシュ計算及びビット列の論理積演算によって実現される。従って、これらのオーバーヘッドは通信時間を含めたとしても、秘匿共通集合演算に比べて小さい。
プレイヤー端末は、ブルームフィルタに限られず他のフィルタを用いてデータ構造化を行ってもよい。具体的には、プレイヤー端末は、ブルームフィルタの実装の一種であるＣｏｕｎｔｉｎｇ  ｆｉｌｔｅｒを用いてデータ構造化を行ってもよい。この場合のデータ構造は整数値の配列となり、類似度として共通の整数値を持つ配列の数やすべての配列の差分の絶対値の和の逆数を定義することが考えられる。
【００７４】
本実施形態に係る秘匿共通集合演算システムは、例えばＳＮＳにおけるユーザの関係抽出に適用されてもよい。この秘匿共通集合演算システムによれば、ユーザの情報（例えば、電話帳、アドレス帳などの個人情報）をサーバ及び他のユーザに開示することなく、当該ユーザについて高速な関係抽出を実現することができる。更に、この秘匿共通集合演算システムは、プライバシ保護協調フィルタリングのような共通集合演算を伴う他の秘匿計算に応用することも可能である。
【００７５】
上記実施形態の処理は、汎用のコンピュータを基本ハードウェアとして用いることで実現可能である。上記実施形態の処理を実現するプログラムは、コンピュータで読み取り可能な記憶媒体に格納して提供されてもよい。プログラムは、インストール可能な形式のファイルまたは実行可能な形式のファイルとして記憶媒体に記憶される。記憶媒体としては、磁気ディスク、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリなどである。記憶媒体は、プログラムを記憶でき、かつ、コンピュータが読み取り可能であれば、何れであってもよい。また、上記実施形態の処理を実現するプログラムを、インターネットなどのネットワークに接続されたコンピュータ（サーバ）上に格納し、ネットワーク経由でコンピュータ（クライアント）にダウンロードさせてもよい。
【００７６】
尚、上記実施形態は、その記載の通りに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して実施形態できる。また、上記実施形態に開示されている複数の構成要素を適宜組み合わせることによって種々の態様を形成できる。また、例えば、実施形態に示される全構成要素からいくつかの構成要素を削除した構成も考えられる。
【符号の説明】
【００７７】
１，２，３，４，ｋ・・・プレイヤー  
【図１】
2014157264.tif 000003
【図２】
2014157264.tif 000004
【図３】
2014157264.tif 000005
【図４】
2014157264.tif 000006
【図５】
2014157264.tif 000007
【図６】
2014157264.tif 000008
【図７】
2014157264.tif 000009
【図８】
2014157264.tif 000010