(57)【要約】本発明は、準同形の閾値暗号化システムに基づいたセキュアな多数当事者の計算のフレームワークにおいて、標準的な準同形の閾値ＥｌＧａｍａｌ暗号化を使用したシンプルかつ効率的なやり方で実現されるプロトコル及び特別なタイプの乗算ゲートを導入する。加算ゲートは本質的にフリーであり、条件付きゲートは、如何なる関数の回路を構築するだけでなく、広い範囲のタスクの効率的な回路を実際に得るのを可能にする。
2007510947.tif 000002
【特許請求の範囲】
【請求項１】
当事者間のセキュアな多数当事者の乗算プロトコルに当事者が参加する方法であって、
前記プロトコルは、秘密の第一のデータと暗号化された第二のデータの積を計算するために調整され、
前記プロトコルは、
秘密の第一のデータ又は２値化された領域からの第一のデータのいずれかである第一のデータを当事者が取得するステップと、
暗号化された第二のデータを当事者が取得するステップと、
離散的な対数に基づく暗号化システムを使用して、前記第一のデータと前記第二のデータとの積のランダム化された暗号を有する暗号化された出力データを当事者が計算するステップと、
暗号化された出力データが正しいことを示すための証明を当事者が生成するステップと、
を含むサブプロトコルを有することを特徴とする方法。
【請求項２】
前記第一のデータは、２値化領域からのランダムなデータである、
請求項１記載の方法。
【請求項３】
前記離散的な対数ベースの暗号化システムはＥｌＧａｍａｌ暗号化システムである、
請求項１記載の方法。
【請求項４】
前記暗号化されたデータはペダーソンコミットメントである、
請求項１記載の方法。
【請求項５】
前記プロトコルは、前記当事者が、他の参加者の少なくとも１つに前記証明を送信する更なるステップを含む、
請求項１記載の方法。
【請求項６】
前記プロトコルは、前記当事者が、他の参加者の少なくとも１つに前記暗号化された出力データを送信するステップを含む、
請求項１記載の方法。
【請求項７】
前記プロトコルは、２つの当事者間で実行される、
請求項１記載の方法。
【請求項８】
請求項１記載の方法を実現するために構成される装置。
【請求項９】
請求項１記載の方法をプログラマブル装置に実行させるためのコンピュータ実行可能な命令を有する、多数当事者の計算を可能にするコンピュータプログラムプロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多数当事者間でのセキュアな多数当事者用の乗算プロトコルに当事者が参加するための方法、かかる方法を実現するために構成される装置、及びかかる方法をプログラマブル装置に実行させるためのコンピュータ実行可能な命令を有するコンピュータプログラムプロダクトに関する。
【背景技術】
【０００２】
セキュアな多数当事者の計算は、多数の当事者が暗号化されていな出力を得るための関数ｆを計算するプロセスである。計算の間、出力のみが当事者にとって利用可能となる。
【０００３】
これらの種類の計算の公知の例は、オークション、ミリオネイア・プロブレム、セキュアファンクションエバリュエーション、ボーティング、合理的かつセキュアなプロファイルマッチングにより暗号化計算である。
【０００４】
準同形の閾値暗号化システム（Homomorphic  Threshold  Cryptosystems）は、セキュアな多数当事者の計算の基礎を与える。所与のｎ項関数について、その入力配線での所与のｘ1,…,ｘnの暗号化がその出力配線でｆ（ｘ1,…,ｘn）を生成するエレメンタリゲートの回路が構成される。エレメンタリゲートは、同じ方式で動作する。全体の回路の配線は、同じ公開鍵の下で全て暗号化され、対応する秘密鍵は、当事者のグループの間で共有される。
【０００５】
エレメンタリゲートは、ビットで動作するか、又はより大きなドメインのエレメントで動作し、この場合、明らかに後者のタイプが効率の観点から好まれる。
【０００６】
暗号化の下での計算のためのツールボックにおけるベーシックツールは、セキュアな乗算プロトコルである。また、更なるゲートは、如何なる値を復号することなしに評価することができるが、暗号化システム、乗算ゲートの準同形な特性を完全に利用することは、成功するのに少なくとも１つの閾値復号（threshold  decryption）を必要とする。
【０００７】
米国特許第6,772,339号では、セキュアな多数当事者の計算の方法が記載されており、計算されるべき関数に基づいて、第一のデータと第二のデータの対を含むデータセットを発生するステップ、第一のデータと第二のデーらからなるそれぞれの対について、第一のデータと第二のデータを暗号化するステップ、暗号化された第一のデータと第二のデータからなる対を混合するステップ、暗号化された入力データを前記暗号化された入力データと比較して、整合を検出するステップ、及び前記検出された整合に対応する暗号化された第二のデータを選択するステップを含んでいる。
【０００８】
乗算ゲートを評価するために結果的に得られるプロトコルは、そのコンセプトの簡単さにも拘らず、非常に非効率的である。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、本発明の目的は、多数当事者の計算のための効率的なビルディングブロック、特に乗算プロトコルを提供する方法及び装置を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の目的は、参加者間でのセキュアな多数当事者の乗算プロトコルに当事者が参加するための方法により達成され、かかるプロトコルは、秘密の第一のデータと暗号化された第二のデータとの積を計算するために構成され、プロトコルは、秘密の第一のデータ又は２値化ドメインからの第一のデータのいずれかである第一のデータを当事者が取得するステップ、暗号化された第二のデータを当事者が取得するステップ、第一のデータと第二のデータの積のランダムにされた暗号化を含む暗号化された出力データを当事者が計算するステップ、離散的な対数に基づく暗号化システムを使用するステップ、及び、暗号化された出力データが正しいことを示す証明（proof）を当事者が発生するステップを含むサブプロトコルを含む。
【００１１】
乗算プロトコルは、秘密又は暗号化された乗数ｘ及び暗号化された乗数ｙを入力としてとり、積ｘｙの暗号化を出力として多項式の時間（polynomial  time）で生成する。プロトコルは、ｘ、ｙ及びｘｙに関する如何なる情報をリークしない。さらに、セキュリティのため、プロダクトが直接的に計算された公的に認証可能な証明をプロトコルが生成することが必要とされる。
【００１２】
本発明に係る方法によれば、所与の秘密又は暗号化された第一のデータ［［ｘ］］＝（ａ，ｂ）＝（ｇr，ｇxｈr）及び暗号化された第二のデータ［［ｙ］］＝（ｃ，ｄ）であり、この場合に当事者Ｐはｒ，ｘを知っており、離散的な対数に基づく暗号化システムの準同形な特性を使用して、ｓ∈RＺqとして、当事者Ｐはランダムにされた暗号化［［ｘｙ］］＝（ｅ，ｆ）＝（ｇs，ｈs）*［［ｙ］］xを計算する。また、当事者Ｐは、出力が訂正されたこと示す証拠を発生し、これは、ウィットネスｒ；ｓ；ｘ∈Ｚqの情報を与えることを意味し、ａ＝ｇr，ｂ＝ｇxｈr，ｅ＝ｇsｃx，ｆ＝ｈsｄxを満たす。
【００１３】
本方法は、アプリケーションを効率的に実現するのを可能にし、たとえば、本方法は、少なくとも２つのユーザが、幾つかの測定に従ってそれらが類似するか否か以外の情報を表すことなしに、それらの秘密データを比較するのを可能にする。
【００１４】
かかる離散的な対数に基づくソリューションの更なる利点は、閾値バージョンのための鍵の生成が比較的シンプルであることである。
【００１５】
更なる利点は、本方法が悪意のあるケースを扱うことに対処すること、２つの当事者のケースの公平性にも対処することである。
【００１６】
更なる利点は、本発明が、ピアユーザからなる大規模なグループの間でアドホックコンタクトについて特に良好に実行されることであり、この場合、それぞれのユーザが（全体のユーザ数とは独立に）制限された量のセットアップ情報のみを必要とすること、及び、２ユーザの間のプロトコルを実行するための分散された鍵生成のための時間を含む全体の実行時間も同様に制限される。
【００１７】
乗算プロトコルの方法は、乗数のうちの１つが秘密（private）、すなわち１つの当事者により知られていることを必要とする。この制約は、乗算プロトコルがＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ａｓｓｕｍｐｔｉｏｎの下で存在するのを可能にする。
【００１８】
本発明に係る有利な方法は、第一のデータが２値化領域からのランダムなデータであることを特徴とする。
【００１９】
本方法は、少なくとも２つのユーザが２つの数の積を得るのを可能にし、その一方は、２値化領域からのランダム数であり、結果が正しく計算された証明である。
【００２０】
本方法は、２つの暗号化された数の暗号化された積を計算するのを可能にするプロトコルを実現する。
【００２１】
条件付きゲート（conditional  gate）として示される請求項２記載のプロトコルでは、乗数ｘは２分の（２値化）領域からである。この制限は、乗算プロトコルが、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ａｓｓｕｍｐｔｉｏｎの下で存在するのを可能にする。ビットで動作するエレメンタリゲートが乗算を含む多数当事者の計算を効率的に実現するのに十分であることを発明者により実現される。
【００２２】
請求項２記載のプロトコルは、ｘが２値化領域に制限される場合に、暗号化された値ｘ及びｙを効率的に乗算するのが可能である。
【００２３】
本発明に係る有利な方法は、離散的な対数に基づく暗号化がＥｌＧａｍａｌ暗号化システムであることを特徴とする。
【００２４】
基本的に準同形のＥｌＧａｍａｌは広い範囲の問題を有効に扱うのに十分であることを発明者により理解される。第二のデータの暗号化は、準同形のＥｌＧａｍａｌ暗号化であり、この場合、これらの暗号化がランダム化され、これらの暗号化のための公開鍵は常に同じであることが理解される。対応する秘密鍵は、多数の当事者間で共有される。
【００２５】
現在の方法は、まさに準同形な閾値のＥｌＧａｍａｌ暗号化を使用して、たとえばＰａｉｌｌｉｅｒ暗号化システムのようなＲＳＡのような暗号化システムの使用よりもコストが安い標準的なＤｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ａｓｓｕｍｐｔｉｏｎの下で動作するという利点を有する。これは、対応する閾値暗号化システムの共有されるＲＳＡモジュールの発生はコストがかかり、全体のアプリケーションのコストを支配する。たとえ２つの当事者のケースについてであっても、ＲＳＡモジュールを共有することは些細なタスクではない。対照的に、離散的な対数に基づく暗号化システムの分散された鍵生成はシンプルであって、実際に２当事者のケースではフリーである。
【００２６】
更なる利点として、ＥｌＧａｍａｌは、楕円曲線又はＸＴＲのような離散的なログ設定に基づいたソリューションを可能にする。
【００２７】
条件付きゲートを評価するためのそれぞれの当事者の作業は、約１２の指数演算（exponentiation）になる。上述された米国特許からのミックス・アンド・マッチのアプローチは、類似の乗算ゲートについて近似的に１５０の指数演算を必要とし、それぞれの当事者がゲートの暗号化された真のテーブルをなす４×３ＥｌＧａｍａｌ暗号化をブラインド及び交換し、正しさの証明を提供する必要があるためであって、それぞれの当事者は、４つのプレインテキストの均一性テスト（plaintext-equality  test）を平均して参加する。
【００２８】
本発明に係る方法は、したがって、セキュアなオークションのようなＹａｏ’のミリオネイア・プロブレム及び多くの他の問題について、今まで最も効率的なソリューションである。  
本発明に係る有利な方法は、暗号化されたデータがペダーソンコミットメント（Pederson  commitment）であることを特徴とする。
【００２９】
僅かな最適化は、乗算についてＥｌＧａｍａｌ暗号［［ｘ］］＝（ｇr，ｇxｈr）の代わりに、ペダーソンコミットメント＜＜ｘ＞＞＝ｇxｈrを使用することで可能なことがある。  
本発明に係る有利な方法は、プロトコルは、少なくとも１つの他の参加者に証明書を当事者が送信するステップを更に含むことを特徴とする。
【００３０】
本発明に係る有利な方法は、プロトコルが少なくとも１つの他の参加者に暗号化された出力データを当事者が送信する更なるステップを含む。  
本発明に係る有利な方法は、プロトコルが２つの当事者間で実行されることを特徴とする。
【００３１】
本発明の目的は、請求項１に係る方法を実現するために構成される装置により達成される。  
本発明の目的は、請求項１に係る方法をプログラマブル装置に実行させるコンピュータ実行可能な命令を有する、多数当事者の計算を可能にするための、コンピュータプログラムプロダクトにより更に達成される。
【発明を実施するための最良の形態】
【００３２】
多数当事者の乗算プロトコルは、２以上の参加者により実行されるプロトコルである。
プロトコルの入力は、２つの（おそらく暗号化された）数、ｘ及びｙである。数ｘは、プレーヤＰ1により提供され、ｙはプレーヤＰ2により提供される。プロトコルの終わりで、両方のプレーヤは、結果として積［［ｘｙ］］を得る。さらに、当事者は、結果が正しく計算され、他のプレーヤが騙していなかったことの証明を得る。
【００３３】
はじめに、計算の幾つかの準備が説明される。  
Ｇ＝＜ｇ＞は、プライムオーダ（prime  order）ｑのＤｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）が実施不可能であると仮定される有限の巡回的な（乗数の）グループを示すとする。
【００３４】
公開鍵ｈ∈Ｇについて、付加的に準同形のＥｌＧａｍａｌ暗号化が使用され、メッセージｍ∈Ｚqは、ｒ∈Ｚqとして対（ａ，ｂ）＝（ｇr，ｇmｈr）として暗号化される。準同形の特性は、ｍとｍ’の暗号化のコンポーネント毎の乗算がｍ＋ｍ’（法ｑ）：（ａ，ｂ）*（ａ’，ｂ’）＝（ａａ’，ｂｂ’）＝（ｇr+r’，ｇm+m’ｈr+r’）の暗号を生じる。
【００３５】
暗号（ａ，ｂ）＝（ｇr，ｇmｈr）が共通の入力として与えられると、標準的な技術は、（固有の）ウィットネス（ｍ，ｒ）の情報を示す情報の証明を生じる（ｍ∈Ｇによる形式（ｇr，ｍｈr）の暗号化により標準的なＥｌＧａｍａｌ暗号は、乗算の意味で準同形であるが、かかる情報の証明がない）。
【００３６】
等価な関係は、ｌｏｇg（ａ／ａ’）＝ｌｏｇh（ｂ／ｂ’）である場合に暗号（ａ，ｂ）と（ａ’，ｂ’）が等価であることを示すことで、ＧｘＧで定義される。ｍ∈Ｚqであるとして（１，ｇm）を使用することは、正式な表現として、等価な（１，ｇm）のクラスを示すために使用される。言い換えれば、［［ｍ］］は、（公開鍵ｈの下で）ｍの全てのＥｌＧａｍａｌ暗号のセットを示す。ダイレクトプロダクトグループＧｘＧでの演算は、通常のやり方で等価なクラスにリフトされる。準同形の特性は、［［ｘ］］*［［ｙ］］＝［［ｘ＋ｙ］］及び［［ｘ］］C＝［［ｃｘ］］を含む。
【００３７】
したがって、スケーラによる加算及び乗算は、容易に達成される。これらの演算は、決定的な方式で実現されたときに容易に確認することができる。  
ＥｌＧａｍａｌ暗号のランダム化（又はブラインド）は、重要なプリミティブでもある。これは、所与の暗号をランダムなエレメント（ａ，ｂ）∈R［［０］］と乗算することになる。ｌｏｇgａ＝ｌｏｇhｂを提供することで、（ａ，ｂ）が確かに０の暗号であることを示している。
【００３８】
秘密鍵α＝ｌｏｇgｈが与えられると、ｂ／ａαを計算することで復号が実行され、これは、あるｍ∈Ｚqについてｇmに等しい。ｇmからｍを回復することは、一般に難しいとされており、したがってｇmからｍを発見することはｍ∈Ｍのときは何時でも実施可能であるように、十分に小さいサイズのセットＭ∈Ｚqに関してこの暗号化システムを見ることが必要である。本発明では、Ｍのサイズは、非常に小さく、｜Ｍ｜＝２であることがある。
【００３９】
ＥｌＧａｍａｌ暗号化システムは、ＤＤＨ  Ａｓｓｕｍｐｔｉｏｎの下で意味的にセキュアである。  
ＥｌＧａｍａｌの（ｔ，ｎ）−閾値バージョンでは（１≦ｔ≦ｎ）、（先のような）共通の公開鍵ｈで暗号が計算され、ｎ当事者間でジョイントプロトコルを使用して復号が行われ、それぞれの当事者は、秘密鍵α＝ｌｏｇgｈの共有を所持する。少なくともｔの当事者が参加する限り、復号が続いて行われ、ｔ当事者よりも少ない当事者は、上手く復号することができない。当事者は、分散された鍵生成プロトコルを実行することで、それらの共有を取得する。
【００４０】
本発明は、２つの当事者の計算に特に関心があるので、更なる詳細は、（２，２）閾値スキームについて提供される。分散された鍵生成は、当事者Ｐ1，Ｐ2に、はじめに，ｉ＝１，２についてαiｒi∈Ｚqであるコミットメントｃi＝ｇαiｈriをブロードキャストさせ、次いで、ｌｏｇgｈiの情報の証明と共に値ｒiをブロードキャストさせることで達成され、この場合、ｉ＝１，２についてｈi＝ｃi／ｈriである。結合公開鍵は、ｈ＝ｈ1ｈ2であり、秘密鍵α＝α1＋α2である。暗号（ａ，ｂ）を復号するため、プレーヤＰiは、ｌｏｇaｄiがｌｏｇgｈiに等しい証明と共に、ｄi＝ａαiを生成する。次いで、メッセージはｂ／（ａ1ａ2）から回復される。
【００４１】
明らかに、（２，２）閾値のＥｌＧａｍａｌはアドホックの使用を可能にする。鍵を生成する試みは、復号を実行する試みとほぼ同じである。
【００４２】
２つの準同形の暗号［［ｘ］］、［［ｙ］］が与えられると、準同形の暗号［［ｘｙ］］は、以下のステップを含むプロトコルにより計算することができる。  
プレーヤＰiは、ランダム値ｒiを選択し、ｉ＝１，２についてｒiを知っている証明と共に、［［ｒi］］をプレーヤＰ3-iに送出する。  
プレーヤは、［［ｘ＋ｒ1＋ｒ1］］を復号する。  
ｘ1＝ｘ＋ｒ2、ｘ2＝−ｒ2とする。プレーヤＰiは、ｉ＝１，２について証明と共に、［［ｘi］］、［［ｆi］］＝ｘi［［ｂ］］をプレーヤＰ3-iに送出する。  
両方のプレーヤは、［［ｆ1］］＋［［ｆ2］］＝［［ｘｙ］］を計算する。  
証明のいずかが失敗した場合、プロトコルは停止される。
【００４３】
最後の準備として、ペダーソンコミットメントが示される。ｇ，ｈ∈Ｇが与えられると、メッセージｍ∈Ｚqへのコミットメントは、ｒ∈RＺQとして値ｃ＝ｇmｈrである。コミットメントは、ｍ及びｒを表すことで開かれる。パダーソンスキームは、ｌｏｇgｈを決定することができないという仮定の下で、無条件に秘匿し、かつ計算に関してブラインドである。コミットメントスキームは、付加的に準同形であり、＜＜ｍ＞＞は、メッセージに対するコミットメントを示すために使用され、個の場合、ランダム性が抑圧される。
【００４４】
これらの準備に従い、関数ｆは、ｆが加算ゲートとシンプルな乗算ゲートのみからなるＺqにわたる回路として表される場合、多数当事者の設定においてセキュアに評価することができる。加算ゲートは、暗号［［ｘ］］及び［［ｙ］］を入力として受け、［［ｘ］］*［［ｙ］］を出力として生成し、シンプルな乗算ゲートは、［［ｘ］］を入力として受け、公的に知られた値ｃ∈Ｚqについて、［［ｘ］］ｃ＝［［ｃｘ］］を出力として生成する。いずれかの関数ｆを扱うことができるため、両方の入力が暗号化される更に一般的な乗算ゲートが必要とされる。
【００４５】
制約がｘ又はｙに課される場合、［［ｘ］］及び［［ｙ］］を入力として受け、［［ｘｙ］］を出力として効果的に生成する乗算ゲートは、ＤＨ問題が実施不可能であるという仮定で存在することができない。したがって、幾つかの制約を乗数ｘに課して、特定の乗算ゲートが使用される。
【００４６】
本発明の第一の実施の形態では、本方法は、乗数ｘが秘密であることを必要とし、これは１つの当事者により知られていることを意味する。  
本発明の第二の実施の形態では、本方法は、特定の乗算ゲートの使用を含む。このゲートは、条件付きゲートと呼ばれ、乗数ｘが２分の（２値化）領域からであることを必要とする。このプロトコルは、共有される２分の乗算器による乗算プロトコルと呼ばれる。このプロトコルは、一般性が低いが、既に知られているプロトコルよりも遥かに効率的である。  
これらの制約にも拘らず、本発明にかかる方法は、非常に効率的な多数当事者のプロトコルを導く。
【００４７】
はじめに、本発明に係る第一の実施の形態では、乗数ｘが（共有される入力よりはむしろ）秘密の入力である場合に乗算プロトコルが提供される。すなわち、ｘの値は１つの当事者Ｐにより知られる。被乗数ｙに制約が課されない。秘密の乗数による乗算は、条件付きゲートのためのプロトコルにおけるサブプロトコルとして、多数の個別の他のプロトコルで生じる。
【００４８】
図１は、本発明の２つの異なる実施の形態を例示している。当事者Ｐ，１００は、秘密の第一のデータ［［ｘ］］，１０１、暗号化された第二のデータ［［ｙ］］，１０２を取得し、正しさの証明を含む暗号化された出力データ［［ｘｙ］］，１０３を計算する。取得するとは、異なる当事者から受けること、内部メモリから検索すること、又は内部で生成することのいずれかである。
【００４９】
暗号［［ｘ］］＝（ａ，ｂ）＝（ｇr，ｇxｈr）及び［［ｙ］］＝（ｃ，ｄ）が与えられると、この場合当事者Ｐはｒ、ｘを知っており、当事者Ｐは、準同形の特性を使用して、ｓ∈RＺqとして、それ自身のランダム化された暗号［［ｘｙ］］＝（ｅ，ｆ）＝（ｇS，ｈS）*［［ｙ］］xを計算する。次いで、当事者Ｐは、現在の出力であることを示す証明と共に［［ｘｙ］］をブロードキャストし、これは，ａ＝ｇr、ｂ＝ｇxｈr、ｅ＝ｇSｃx、ｆ＝ｈSｄxを満たす、ウィットネスｒ；ｓ；ｘ∈Ｚqの情報を確かめることを意味する。
【００５０】
後の使用のため、先のプロトコルは、シミュレートされる必要がある。シミュレータは、入力として［［ｘ］］及び［［ｙ］］、正しい出力暗号［［ｘｙ］］を取得するが、ｘを知らない。結果として、シミュレータは、シミュレートされた情報の証明を追加する必要がある。シミュレートされたトランスクリプトは、実際のトランスクリプトとは統計的に区別不可能である。
【００５１】
先にプロトコルのバリエーションを使用することが可能であって、秘密の乗数ｘは幾つかの乗数ｙiと同時に乗算される。さらに、乗数についてＥｌＧａｍａｌ暗号［［ｘ］］＝（ｇr，ｇxｈr）の代わりに、ペダーソンコミットメント＜＜ｘ＞＞＝ｇxｈrを使用することで僅かな最適化が可能である。
【００５２】
本発明の第二の実施の形態では、条件付きゲートは、まさに標準的な準同形の閾値ＥｌＧａｍａｌ暗号を使用した驚く程のシンプルかつ効率的なやり方で実現することができる特別なタイプの乗算ゲートとして使用される。加算ゲートは、本質的にフリーであり、条件付きゲートは、如何なる関数の回路を構築するのを可能にするだけでなく、広い範囲のタスクのための効率的な回路が実際に得られる。
【００５３】
二分のドメイン（dichotomous  domain）｛−１，１｝は、説明の目的で便利である。ドメイン｛０，１｝又は何れか他のドメイン｛ａ，ｂ｝，ａ≠ｂは、これらのドメインが線形変換により互いに変換することができるので、代わりに使用することができる。これらの変換を暗号化に適用することもできる。
【００５４】
条件付きゲートは、２つの異なるプロトコルに沿って例示される。条件付きゲートを実現するための第一のプロトコルでは、プロトコルは、プレーヤＰ1．．．，，ＰN，Ｎ≧２が暗号［［ｘｙ］］をセキュアに計算するのを可能にする。簡単さのため、プレーヤは、準同形の暗号化スキーム［［．］］の秘密鍵を共有することとされる。
【００５５】
プロトコルステージ１では，ｉ＝１．．Ｎについて、プレーヤＰiは［［ｘi-1］］を入力として取り、ｓi∈R｛−１，１｝を選択する。プレーヤＰiは、秘密の乗算器による乗算のためのプロトコルを使用して、暗号［［ｓi］］及び［［ｓiｘi-1］］、及び［［ｓiｘi-1］］が正しいw.r.t.［［ｓi］］及び［［ｘi-1］］である証明をブロードキャストする。ｘi＝ｓiｘi-1とする。
【００５６】
プロトコルステージ２では、プレーヤは［［ｘN］］を復号してｘNを取得する。それぞれのプレーヤは、ｘN∈｛−１，１｝であることをチェックする。ｘN及び［［ｙ］］が与えられると、暗号［［ｘNｙ］］は好適に計算される。ｚ0＝ｘNｙとする。
【００５７】
プロトコルステージ３では、ｉ＝１．．Ｎについて、プレーヤＰiは、秘密の乗算器による乗算のためのプロトコルを使用して、［［ｚi-1］］を入力として受け、暗号［［ｓiｚi-1］］、及び［［ｓiｚi-1］］が正しいw.r.t.［［ｓi］］及び［［ｚi-1］］である証明をブロードキャストする。ｚi＝ｓiｚi-1とする。
【００５８】
プロトコルの出力は、［［ｚN］］＝［［ｘｙ］］である。プロトコルは、１つの閾値の復号のみを必要とする。ｘN∈R｛−１，１｝が保持される必要があるので、復号は準同形のＥｌＧａｍａｌ暗号スキームについて実施可能である。プロトコルは、大まかに２Ｎのラウンドを必要とする。
【００５９】
ｘNの値は統計的に独立であるので、少なくともｔ＝Ｎ／２の誠実なプレーヤがプロトコルを上手く完了することができる場合には、ｘNの値は、ｘに関する如何なる情報を表さない。
【００６０】
プロトコルは、任意にロバスにされる。プレーヤＰiがプロトコルステージ２で失敗した場合、プロトコルの残りで単に廃棄される。ステージ２について、ジョイント復号ステップは、定義によりロバストである。ｘN∈｛−１，１｝が失敗したかをチェックする場合、プレーヤは、ｓi∈｛−１，１｝である証明をブロードキャストする必要がある。正しい証明を提供できないプレーヤは使われなくなり、それらのｓiの値が復号される。ｘNの値は、これに応じて調整される。同様に、ステージ２では、プレーヤＰiがそのステップを完了できない場合、その値ｓiは復号され、暗号［［ｓiｚi-1］］は好適に計算される。  
このプロトコルは、正しく、適切であってかつ計算上のｚｋである。
【００６１】
第二の実施の形態の第二のプロトコル実現では、二分のドメインは｛−１，１｝が使用されるが、異なるドメインがリニアマッピングを使用して代わりに使用される。
【００６２】
［［ｘ］］、［［ｙ］］は、ｘ∈｛−１，１｝⊆Ｚq及びｙ∈Ｚqによる暗号化を示すとする。以下のプロトコルは、当事者Ｐ1．．Ｐn，ｎ＞１が暗号［［ｘｙ］］を安全に計算するのを可能にする。簡単さのため、これらの当事者は、（ｔ＋１；ｎ）−閾値スキーム［［．］］の秘密鍵を共有することとされ、ここでｔ＜ｎである。プロトコルは２つのフェーズからなる。
【００６３】
プロトコルフェーズ１。ｘ0＝ｘ及びｙ0＝ｙとする。ｉ＝１．．ｎについて、当事者Ｐiは、［［ｘi-1］］及び［［ｙi-1］］を入力として受け、ｓi∈R｛−１，１｝によるコミットメント＜＜ｓi＞＞をブロードキャストする。その後、Ｐiは、秘密の乗数の乗算プロトコルを乗数＜＜ｓi＞＞及び被乗数［［ｘi-1］］及び［［ｙi-1］］に適用し、ランダムな暗号［［ｘi］］及び［［ｙi］］を得る。ここで、ｘi＝ｓiｘi-1であり、ｙi＝ｓiｙi-1である。Ｐiがこのステップを上手く完了できない場合、即座に停止される。
【００６４】
プロトコルフェーズ２。当事者は、［［ｘn］］を復号してｘnを得る。正しい共有の数が不十分であるために復号が失敗した場合、全体のプロトコルが中止される。
【００６５】
（外１）
2007510947.tif 000003
であるために復号が失敗した場合、それぞれの当事者Ｐiはｓi∈｛−１，１｝である証明をブロードキャストすることが必要とされる。そのようにできない当事者は停止され、（フェーズ１で再び開始して）プログラムは再始動される。ｘn及び［［ｙn］］が与えられると、暗号［［ｘnｙn］］が公的に計算される。全ての当事者が誠実である場合、ｘnｙn＝ｘｙである。
【００６６】
当事者は、レンジ｛−１，１｝の外から値ｓiをとることでフェーズ１の多くとも１つのランについてプロトコルを分離する。ｔ＜ｎ／２について、プロトコルはロバストであって、全体でｔまでの失敗した当事者を許容することができる。ｎ／２≦ｔ＜ｎについて、プロトコルはロバストではないが、このケースでは相手が利点を得ない。
【００６７】
プロトコルは、１つの閾値の復号のみを必要とする。ｘnは２値化が保持されるのが必要とされるので、復号は準同形ＥｌＧａｍａｌ暗号スキームについて実施可能である。ｘnの値はｘについて統計的に独立であるので、ｘnの値は、ｘに関する如何なる情報を表さない。
【００６８】
全体の当事者の数は、評価されるべき条件付きゲートの全体の数に比較して大きい場合、ロバスト性を保証する代替的なやり方は、フェーズ１で、当事者にコミットメント＜＜ｓi＞＞の代わりに暗号［［ｓi］］を使用させることである。さらに、フェーズ２で、
【００６９】
（外２）
2007510947.tif 000004
である場合、全ての当事者は、ｓi∈｛−１，１｝を確かめることが必要とされる。失敗した当事者は廃棄され、それらのｓiの値は、ｘnの値を訂正するために復号される。
【００７０】
プロトコルの性能は、計算上の複雑さ（ビット）及びラウンド（round）の複雑さにより決定される。フェーズ１では、それぞれの当事者は、約１０の値をブロードキャストして、秘密の乗算器による乗算プロトコル（private-multiplier  multiplication  protocol）を適用する。復号について、それぞれの当事者は、多くとも３つの値をブロードキャストする。したがって、乗算の複雑さは、Ｏ（ｎｋ）であり、この場合に秘匿された定数は非常に小さい。一般に、ラウンドの複雑さはＯ（ｎ）であり、これは高いが、２つの当事者の計算のケースではＯ（１）である。また、多くの条件付きゲートが並行に評価されることになるとき、当事者Ｐ1．．Ｐnが条件付きゲートプロトコルのフェーズ１を実行する順序を任意に選択することができることを利用する場合がある。
【００７１】
条件付きゲートの第一の適用として、ｘｏｒ−準同形のＥｌＧａｍａｌ暗号化スキームが示される。ｘ，ｙ∈｛０，１｝として［［ｘ］］及び［［ｙ］］が与えられると、
【００７２】
（外３）
2007510947.tif 000005
は、１つの閾値の復号を使用して以下のように計算される。
【００７３】
ステップ１：ｘ’＝２ｘ−１∈｛−１，１｝により［［ｘ］］から［［ｘ’］］に公的に変換する。  
ステップ２：条件付きゲートを［［ｘ’］］及び［［ｙ］］に適用して［［ｘ’ｙ］］を得る。  
ステップ３：
【００７４】
（外４）
2007510947.tif 000006
に等しい［ｘ−ｘ’ｙ］を公的に計算する。
【００７５】
条件付きゲートの印加は、閾値の復号を必要とし、これは、ｘｏｒ−準同形ＥｌＧａｍａｌ暗号化を達成するために避けられないと考えられる。
【００７６】
当事者当たりの作業は、それぞれの条件付きゲートについて約１３の指数演算に非常に制限される。対照的に、記載された米国特許に従うミックスアンドマッチアプローチは、それぞれの当事者が、（J.  Grothによる“A  verifiable  secret  shuffle  of  homomorphic  encryptions,  public  key  cryptography  PKC’03,  volume  2567  of  Lecture  Notes  in  Computer  Science,  page  145-160,  Berlin,  2003,  Springer-Verlag”の有効なプロトコルを使用して）確認できるやり方で
【００７７】
（外５）
2007510947.tif 000007
について真のテーブルの４行を混合するのを必要とし（ミックスステップ、エントリ、すなわち正しさの証明のための６×１２の指数演算をブラインドするために２４の指数演算を必要とする）、［［ｘ］］及び［［ｙ］］が与えられた
【００７８】
（外６）
2007510947.tif 000008
を発見するために平均４つのプレインテキストの均一性テストを実行する（マッチステップ、４×７の指数演算を必要とする）。したがって、条件付きゲートは、指数演算をカウントして近似的に１０倍の改善を提供する。
【００７９】
条件付きゲートの第二の適用として、論理ゲートの実現が示される。  
２ビットｘ及びｙの演算子は、形式ａ0＋ａ1ｘ＋ａ2ｙ＋ａ3ｘｙの多項式として固有なやり方で表現することができる。係数は、必要なバイナリではない。たとえば、排他的論理和演算子
【００８０】
（外７）
2007510947.tif 000009
は、
【００８１】
（外８）
2007510947.tif 000010
＝ｘ＋ｙ―２ｘｙを満たす。タイプ｛０，１｝2→｛０，１｝の正確な１６の多項式が存在し、これは以下の多項式の形式ｂ0ｘｙ+ｂ1ｘ（１−ｙ）+ｂ2（１−ｘ）ｙ＋ｂ3（１−ｘ）（１−ｙ）を考える場合に直接的であり、ここで係数はバイナリである。一般に、係数は、｛−１，１｝のような他の２値化されたドメインで機能する場合に整数である必要がない。
【００８２】
条件付きゲートの以下のアプリケーションでは、特別の乗算ゲートは、整数の比較及び二進で表現される数の加算のような基本演算のための効果的な回路を得るために適用される。
【００８３】
条件付きゲートの第三のアプリケーションとして、更に一般的な状況への拡張を可能にするＹａｏのミリオネイア・プロブレムの僅かな変形の効率的なソリューションが示される。このアプリケーションでは、それら二進表現、すなわちｘ＝（ｘn-1，．．，ｘ0）及びｙ＝（ｙn-1，．．，ｙ0）のそれぞれにより入力が与えられる。サイン関数を実現するＺに対する多変量多項式Ｐが定義される。
【００８４】
幾つかの多項式は、この関数を実現するために使用することができる。最も有効なソリューションは、以下の多変量低減多項式に基づいて構築することができると考えられる。ｘ，ｙ∈｛０，１｝について、Ｆ（ｓ，ｘ，ｙ）=ｓ+（１−ｓ2）（ｘ−ｙ）
多項式Ｆは、補助的な変数ν＝１−ｓ2を導入することで効率的に評価することができる。はじめに、ｓ＝０及びν＝１である。次いで計算
ｓ，ν＝ｓ＋ν（ｘ−ｙ），ν−ν（ｘ−ｙ2）
は、所望の結果を与える、ｘ及びｙの全てのコンポーネントについて繰り返される。秘密のやり方でこの計算を行うため、３つの基本的なステップが必要とされ、プレーヤは、そのｘ又はｙを所与の準同形の暗号と乗算する。  
プレーヤ１は、［［ν］］及び（（ｘ））から［［νｘ］］を計算する。  
プレーヤ２は、それぞれの［［νｘ］］及び（（ｙ））の［［ν］］から［［νｙ］］及び［［νｘｙ］］を計算する。  
両プレーヤは、（新たなｓである）［［ｓ＋νｘ−νｙ］］を計算する。  
両プレーヤは、（新たなｓである）［［ν−νｘ+２νｘｙ−νｙ］］を計算する。
【００８５】
必要とされる場合、ｓは閾値の復号を使用して復号することができる。なお、このアルゴリズムは、それぞれのビットについて３つの「秘密の乗数による乗算」プロトコルを必要とする。アルゴリズムにおける第二のステップを効率的に実行することができる。このアプローチは、暗号化形式で結果を生成するためにＳｏｃｉａｌｉｓｔ  Ｍｉｌｌｉｏｎａｉｒｅｓ  ｐｒｏｂｌｅｍに適用することができる。
【００８６】
条件付きゲートの第四の適用として、２つの数の加算が示される。それら二進表現により与えられる２つの数ｘ，ｙを加算するため、キャリーを考慮して、それぞれのビットが加算される。出力ｚの次のビットを生成するため、［［ｔ］］＝［［ｘi＋ｙi＋ｃi-1］］を計算することが必要であり、ここでｃi-1はキャリー値である。ｚi＝ｔ  法２、及びｃi＝
【００８７】
（外９）
2007510947.tif 000011
が保持される。計算は、ｚi＝ｘi＋ｙi＋ｃi-1−２ｘiｙi−２ｘiｃi-1−２ｙiｃi-1+４ｘiｙiｃi-1、及びｃi＝ｘiｙi＋ｘiｃi-1＋ｙiｃi-1−２ｘiｙiｃi-1である。ｘ及びｙの両者が秘密である場合、全てのこれらの項は、「シンプルな」乗算プロトコルを使用して計算することができる。４つのかかる乗算は、それぞれのビットについて必要とされる。したがって、Ｏ（ｎ）は前対的にｎラウンドを使用する。１つのみが秘密である場合、１つの二分の乗算が必要とされる。両者が共有される場合、二分の乗算が使用される。
【００８８】
同様に、２つの数ｘ，ｙの乗算は、スクールメソッドにより達成される。これは、Ｏ（ｎ2）ビットの乗算を必要とする。
【００８９】
条件付きゲートの第五の適用として、ハミング距離の計算が示される。Ｚqにおけるエントリにより２つのベクトルｘ及びｙが与えられると、ｘとｙとの間のハミング距離ｄH（ｘ，ｙ）は、
【００９０】
【数１】
2007510947.tif 000012
として定義され、ここでｘ＝０の場合にδ（ｘ）＝０であり、
【００９１】
（外１０）
2007510947.tif 000013
の場合にδ（ｘ）＝１である。このセクションの目的は、ｓ及びｙに関する更なる情報を与えることなしにｘとｙの間のハミング距離を安全に計算することである。更に正確には、２つのプレーヤＰ1及びＰ2が存在するものとされ、それぞれはベクトル、すなわちｘ及びｙをそれぞれ有する。これらプレーヤは、２つの当事者のプロトコルを実行することで、ｄH（ｘ，ｙ）を計算するのを望む。ベクトルｘのｉ番目のエントリは、ｘi∈Ｚqにより示される。エントリｘiは、以下の表現を通してバイナリストリングとして表現することができる。
【００９２】
【数２】
2007510947.tif 000014
均一性テストは、変数ｈを使用して行われる。
【００９３】
プロトコルの終わりで、Ｐ1及びＰ2はｈを復号する。このプロトコルにおける不変性は、
【００９４】
【数３】
2007510947.tif 000015
である。ｄH（ｘ，ｙ）を計算するため、先に定義されたプロトコルは、ベクトルｘ及びｙの各エントリｘi，ｙiについて実行される必要がある。エントリｉの結果をｈiで示す。次いで、以下のようになる。
【００９５】
【数４】
2007510947.tif 000016
その後、両プレーヤは、互いに［［ｄH（ｘ，ｙ）］］を復号する。
【００９６】
条件付きゲートの第六の適用として、ユークリッド距離の計算が示される。ハミング距離の計算との違いは、類似性の測定からなる。レングスｎの２つのベクトルｘ及びｙについて、ユークリッド距離ｄH（ｘ，ｙ）は、
【００９７】
【数５】
2007510947.tif 000017
として定義される。ｄH（ｘ，ｙ）を計算するため、プレーヤは、以下のステップを実行する。
【００９８】
プレーヤ１は、そのｘiの情報から全てのｉ＝１，．．，ｎについて［［ｘi2］］を計算する。同様に、プレーヤ２は、全てのｉ＝１，．．，ｎについて［［ｙi2］］を計算する。  
両プレーヤは、［［ｏi］］＝［［ｘi2−２ｘiｙi＋ｙi2］］を計算する。したがって、プレーヤ１は、プレーヤ２に［［ｘi］］を送出し、プレーヤ２は、次いで、（プレーヤ２が正しいｙi、すなわちｙi2の計算で使用されたのと同じｙiを使用した証明と共に）［［２ｘiｙi］］を計算する。次いで、［［ｘi2−２ｘiｙi＋ｙi2］］を計算する。  
最後に、以下のような、暗号化スキームの準同形の特性を利用することで［［ｄH（ｘ，ｙ）］］を計算する。
【００９９】
【数６】
2007510947.tif 000018
公平な閾値の復号を使用することで、結果が得られる。
【０１００】
さらに、この計算の閾値のバージョンが考慮され、すなわち一方（又は両方）のプレーヤがある閾値μについてデシジョンプロブレムｄH（ｘ，ｙ）＞μへの回答を得るケースが考慮される。その状況では、両方のプレーヤは、それらの入力の二進表現を使用する必要があり、二進表現で結果［［ｏi］］の値を計算する。次いで、先に説明されたのと同じ方法を使用することで、
【０１０１】
（外11）
2007510947.tif 000019
の二進表現を計算する。次いで、暗号化された結果を得るため、ミリオネイアのプロトコルを実行する。最後に、公正な閾値暗号を使用して、両プレーヤにソリューションを与える。
【０１０２】
条件付きゲートの第七の適用として、２つのベクトルを比較するための別の公知の類似性の測定が示され、正規化されたスカラー積は、以下のように定義される。
【０１０３】
【数７】
2007510947.tif 000020
データｘ，ｙは秘密であるので、数１／‖ｘ‖及び１／‖ｙ‖はそれぞれのプレーヤにより秘密に計算することができる。総和
【０１０４】
【数８】
2007510947.tif 000021
は、ＥｌＧａｍａｌ暗号化スキームの準同形の特性を使用して計算することができる。準同形の特性を再度使用して、＜ｘｙ＞を得る。最後に、（公平な）閾値の復号を適用することで、及びＰ−Ａ．Ｆｏｕｑｕｅ，Ｊ．Ｓｔｅｒｎ，Ｇ−Ｊ．Ｗａｃｋｅｒｓ，“ＣｒｙｐｔｏＣｏｍｐｕｔｉｎｇ  ｗｉｔｈ  ｒａｔｉｏｎａｌｓ”ｉｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ，２００１の技術を有理数に対処するためにＥｌＧａｍａｌのケースに拡張することで値が得られる。
【０１０５】
関連するデシジョンプロブレムを解決するため、すなわち、良好に定義された閾値μについて、＜ｘ，ｙ＞  ＞μであるかを判定するため、全ての計算が先に記載されたように二進表現で行われる必要がある。更に０≦μ≦１であるので、関連するデシジョンプロブレムを解くことが好ましい。
【０１０６】
【数９】
2007510947.tif 000022
次いで、ミリオネイアのプロトコルが適用される必要がある。最後に、（公平な）閾値復号を適用することで結果が得られる。
【０１０７】
本発明の広い適用性を例示するため、条件付きゲートの第八の適用であるセキュアなオークションが示される。
【０１０８】
オークションは、２つのフェーズである、参加者がそれらの入札をオークション側に送出する入札フェーズ、オークション側は、最も高い価格及び勝者のアイデンティティを発する開札するフェーズからなる。
【０１０９】
以下のモデルが仮定される。ｍの入札者Ｐ1，．．．，Ｐmが存在する。入札は、ｘ1＝（ｘ1,n-1，．．．，ｘ1,0）2，．．．，ｘm＝（ｘm,n-1，．．．，ｘm,0）2により与えられる。表現は、この表記ではｍｓｂからｌｓｂまで順序付けされる。入札者は、サーバの結合公開鍵でそれらの入札を暗号化し、それらをオークション側［［ｘi］］＝［［ｘi,n-1］］，．．．，［［ｘi,1］］に送出する。ｋのサーバが存在する。最も高い価格のオークションのための方法が記載される。
【０１１０】
最も高い入札者のアイデンティティを決定するアルゴリズムが提供される。このアルゴリズムは、最も高い入札、及び最も高い入札者のアイデンティティを決定するためにサーバにより使用される。したがって、入札ｉ（ｍｓｂから始まる）まで最も高い入札者のアイデンティティを見失わないように、ｎ＋１セレクションベクトルｗi∈｛０，１｝m、ｉ＝−１，．．．，ｎ−１のセットが定義される。アルゴリズムは、ベクトルｗn-1で始まり、最も高い入札者のアイデンティティがベクトルｗ-1に含まれる。ｗiをｗi-1に更新するダイナミクスを与えるため、第二のベクトルのセットｔi∈｛０，１｝m+1、ｉ＝０，．．．，ｎ−１が定義される。ベクトルｔiは、ベクトルｘjｗjはゼロベクトルに等しいかをチェックする。ベクトルｗi、ｔiのｊ番目のコンポーネントは、ｗj,i、ｔj,iにより示される。ｔベクトルの初期条件は、ｔ0,j＝０、ｊ＝０，．．．，ｎ−１により与えられ、ｗベクトルは、ｗn-1＝（１，．．．，１）により与えられる。多項式は、Ｆ（ｓ，ｚ）＝ｓ＋（１−ｓ）ｚ及びＧａ（ｓ，ｚ）＝ｓ（ｚ＋（１−ｚ）（１−ａ））により定義される。次いで、以下の更新ルールによりダイナミクスが定義される。ｔj,i＝Ｆ（ｔj-1,i，ｘj,iｗj,i）、ｔm,i＝Ｆ（．．．Ｆ（Ｆ（ｔ0i,ｘ1iｗ1i），ｘ2iｗ2i）．．．）、及びｗj,i-1＝Ｇtm,i（ｗj,i，ｘj,i）、ｉ＝ｎ−１，．．．，０についてｉ＝ｎ−１で開始し、それぞれｉについて、カウンタｊは１からｍにランする。なお、ｔm,i＝１は、ベクトルｘjｗjの少なくとも１つのコンポーネントが１に等しいことを意味する。ベクトルｗ-1をセキュアに計算するため、サーバは、条件付きゲートに基づいて一般化されたミリオネイアプロトコルを使用する。
【０１１１】
ベクトルｗ-1がセキュアに計算されたとき、サーバは、ベクトルｗ-1のエントリを復号するため、公平な閾値復号を使用する。勝利者となる入札者のアイデンティティは、１に等しいｗ-1のエントリの位置に対応する。この識別子を使用して、対応する最も高い入札を発見し、それを復号するために閾値復号を使用することができる。
【０１１２】
このプロトコルは、上述されたＪｕｅｌｓ及びＪａｋｏｂｓｓｏｎにより規定されるのと同じ利点を満たし、特に、比較的計算的に高価なミックス計算を回避しつつ、非インタラクティブ性、オークションの適合性、フルプライバシー、ロバスト性、マルチプルサーバ及び公的な認証性を満足する。
【０１１３】
このプロトコルは、Ｖｉｃｋｒｅｙ（セカンドプライス）オークションに拡張することができる。Ｖｉｃｋｒｅｙオークションは、最も高い入札者が勝つものの、クリアリングプライスであり、すなわち勝者が支払うべき価格が二番目に高い入札に等しいオークションである。Ｖｉｃｋｒｅｙオークションを実行するため、以下のアプローチが可能である。はじめに、サーバは、先に与えられたプロトコルにより、勝者のアイデンティティを決定する（勝者の入札ではない）。次いで、サーバは、リストから勝者及びそれらの入札をリストから除く。最後に、以下の多項式のセットを評価する。
ｐj＝Ｆ（．．．Ｆ（Ｆ（０，ｘ1,jｗ1,j），ｘm,jｗm,j））、ｊ＝ｎ−１，．．．，０及びＦは先に定義されたような関数である。ベクトルｐ＝（ｐn-1，．．．，ｐ0）は、最大の入札価格を含む。
【０１１４】
最後に、秘密の乗算器による乗算プロトコルが示される。第一の適用は、一般化されたミリオネイア・プロブレムである。
【０１１５】
ミリオネイア・プロブレムでは、それぞれの入力ｘ及びｙは、プレーヤに対して両方共に秘密である。多くの適用（たとえば、セキュアプロファイルマッチング）では、一方又は両方の入力が共有される。１つの入力、すなわちｘが共有される場合、乗算は、アルゴリズムにおける数ステップで秘密の乗算器によるプロトコルと使用される。ミリオネイアアルゴリズムについて、２ｎの秘密の乗算プロトコル及びｎの二分の乗算プロトコルになる。両方の入力が共有される場合、全てのステップで二分の乗算プロトコルを使用することが必要であり、二分の乗算プロトコルの３ｎの使用を与える。
【０１１６】
一方の入力、すなわちｘが共有され、他方の入力が既知の定数Ｔである場合、以下のプロトコルが可能である。ｙiをＴj（ｊ＝０，．．．，ｎ−１）で置き換え、暗号化スキームの準同形の特性を使用することで、｛［［ｘj−Ｔj］］｝（ｊ＝０..ｎ−１）を計算する。このようにして、問題は、不等号ｘ−Ｔ＞０に変換される。次いで、（ｎの二分の乗算につながる）二分の乗算プロトコルで［［ν（ｘj−Ｔj）］］の計算のみが行われる必要がある。
【０１１７】
第二の適用として、セキュアプロファイルマッチングが示される。  
近年、電気的な形式での大量のコンテンツ（オーディオ、ビデオ、テキスト等）のユーザへの可用性は、情報の選択の方法の開発を呼んでいる。かかる方法は、最も一般的に、パーソナライゼーションの考えに基づいており、そのユーザの好みのプロファイルに従って所与のユーザについて情報が選択される。かかるシステムは、推薦システムとして一般に知られる。
【０１１８】
コラボレイティブ・フィルタリング技術は、コンテンツの推薦が所与のユーザのプロファイルと他のユーザのプロファイルとの間の類似性に基づいた（コンテンツ自身の特徴ではない）推薦システムである。（ある前もって定義された基準に従って）２つのプロファイル間の類似性の速度が十分に高い場合、システムは、そのユーザにより未だ見られていない、他のユーザの高く評価されたコンテンツアイテムを１ユーザに推薦する。
【０１１９】
ここでこの設定は、アドホックケースに拡張され、２ユーザは、それらのプロファイルを比較し、類似の趣向を有するかを見つける。類似の趣向を有する場合、互いにコンテンツをやり取りする手順を始める。有さない場合、プロトコルは、プロファイルが類似しないこと以外に、他のプライベート情報が漏洩していないことを保証する。
【０１２０】
２つのプロファイルのプライベートの比較により、ユーザが前に合意したテスト機能を安全に計算することが意図される。第二のフェーズでは、この（暗号化された）値を閾値とセキュアに比較し、すなわち、プロトコルの終わりで、プレーヤが得た情報は、テスト機能の値が閾値を超えるか否かである。
【０１２１】
参加者は、認証されたチャネル互いに有するとされる。明確さのため、この記述は、ユーザのプライベートプロファイルがｘ及びｙとして示された二進ベクトルからケースに制限されるが、非二進ベクトルへの拡張も可能である。
【０１２２】
２つのベクトルを比較するための第一の測定は、それらが異なるエントリの数により与えられる。この測定は、２つのベクトルｘ，ｙ∈｛０，１｝nの間のハミング距離ｄH（ｘ，ｙ）の観点で定義することができ、この距離は、
【０１２３】
【数１０】
2007510947.tif 000023
により与えられ、ｘ＝０の場合にδ（ｘ）＝０であり、ｘ≠０の場合にδ（ｘ）＝１である。考慮される第二の測定は、
【０１２４】
【数１１】
2007510947.tif 000024
のように定義されるスカラー積である。このセクションの目的は、ｄH（ｘ，ｙ）及びｄSｘ，ｙ）がどのように計算され、秘密のやり方でどのように閾値に比較されるかを示すことである。
【０１２５】
ｄH（ｘ，ｙ）の秘密の計算は、秘密の乗算器による乗算プロトコルを実行して、結果を復号するために閾値復号を使用することで実行することができる。ｄS（ｘ，ｙ）の秘密の計算も、秘密に乗算器による乗算プロトコル及びＥｌＧａｍａｌの暗号化システムの準同形の特性に基づいている。
【０１２６】
更に関心のある状況は、一方又は両方のプレーヤにより選択された閾値μについて、デシジョンプロブレムｄH（ｘ，ｙ）＞μ又はｄS（ｘ，ｙ）＞μが秘密のやり方で解決されたときに生じる。μはその二進表現μn-1，．．．，μ0で与えられるものとする。次のプロトコルは、ｄH（ｘ，ｙ）のデシジョンプロブレムを解いて、ｄS（ｘ，ｙ）の状況は完全に類似しており、したがって詳細は省略される。
【０１２７】
はじめに、プレーヤは、鍵生成プロトコルを使用して閾値のＥｌＧａｍａｌシステムをセットアップする。  
それぞれのコンポーネントｉ＝１，．．．，ｎについて、両方のプレーヤは、ミリオネイア・プロブレムのセクションのソシアリスト（socialist）プロトコルを使用するか、秘密の乗算器による乗算プロトコルを使用して［［ｏi］］＝［［（ｘi−ｙi）2］］を計算することで、セキュアに［［ｏi］］＝［［δ（ｘi−ｙi）］］を計算する。  
両方のプレーヤは、
【０１２８】
【数１２】
2007510947.tif 000025
のビット表現を秘密に計算する。
【０１２９】
結果として、プレーヤは（［［ｓn-1］］，．．．，［［ｓ0］］）2；
【０１３０】
（外12）
2007510947.tif 000026
の二進表現。  
プレーヤは、［［ｓ］］≧［［μ］］であるかをチェックするため、［［ｓ］］及び［［μ］］にミリオネイア・プロブレムを実行する。  
最後に、両方のプレーヤは、デシジョンプロブレムの結果を復号するため、（公平な）閾値復号を適用する。
【０１３１】
このプロトコルは、Ｏ（ｎ・ｌｏｇ  ｎ）の指数演算をプレーヤ当たり必要とする。  
前のアプローチは、エントリが離散（bit  not  binary）領域に属するケースに拡張することができる。考えは同じであるが、計算が多くのステップ及び詳細を必要とする。そのケースにおいても、十分なプライバシーを保証できることが強調される。
【０１３２】
図２は、本発明に係る方法を実現する装置及びコンピュータプログラムプロダクトを例示している。
【０１３３】
装置２００は、本発明に係る方法を実現するために構成されるメモリ２０１、処理手段２０２、入力手段２０３、及び出力手段２０４を有している。
【０１３４】
コンピュータプログラムプロダクト２１０は、ロードされたときに、装置２００におけるプログラマブル装置に本発明に係る方法を実現するために必要なステップを実行させる命令を実行する。
【０１３５】
先に記載された実施の形態は、本発明を限定するよりはむしろ例示するものであり、当業者であれば、特許請求の範囲から逸脱することなしに多くの代替的な実施の形態を設計することができる。
【０１３６】
請求項において、括弧の間に配置される参照符号は、請求項を制限するとして解釈されるべきではない。単語「有する“comprising”」は、請求項に列挙されたエレメント又はステップの存在を排除するものではない。エレメントに先行する単語“ａ”又は“ｏｒ”は、複数のかかるエレメントの存在を排除するものではない。本発明は、幾つかの個別のエレメントを有するハードウェアにより、適切にプログラムされたコンピュータにより実現することができる。１つのプロセッサ又は他の（プログラマブル）ユニットは、請求項で引用される幾つかの手段の機能を達成する場合もある。
【０１３７】
幾つかの手段を列挙している装置の請求項では、これら幾つかの手段は、同一のハードウェアにより実施することができる。所定の手段が相互に異なる従属の請求項で引用される単なる事実は、これらの手段の組む合わせを利用することができないことを示すものではない。
【図面の簡単な説明】
【０１３８】
【図１】乗算プロトコルのサブプロトコルを例示する図である。
【図２】本発明に係る方法を実現するための装置を示す図である。
【図１】
2007510947.tif 000027
【図２】
2007510947.tif 000028
【国際調査報告】
2007510947.tif 000029
2007510947.tif 000030
2007510947.tif 000031