"第1プロセッサと第2プロセッサとの間の安全なマルチパーティ通信を使用して、暗号化されたベクトル内の暗号化された要素を、該暗号化されたベクトル内の該暗号化された要素の順序により、選択する方法であって、前記第2プロセッサは強秘匿な加法的準同形写像暗号システムのための1対の鍵を格納し、該1対の鍵は秘密解読鍵および公開暗号鍵を含み、また、前記暗号化されたベクトルは、前記公開鍵で暗号化されて、前記第1プロセッサに格納され、また、前記第1プロセッサは、暗号化された領域においてのみ動作するものであり、前記方法は、前記暗号化されたベクトルの要素の値を、該暗号化されたベクトル内の該要素の順序が維持されるように、スケーリングするステップと、スケーリングされ順列化されたベクトルを生成するために、前記暗号化されたベクトルの前記要素の順序を順列化するステップと、前記暗号化された領域の情報を前記第2プロセッサへ提供するステップであって、基礎となる、暗号化されていない領域の情報は、前記スケーリングされ順列化されたベクトルの中の要素の順序を示すものである、ステップと、前記スケーリングされ順列化されたベクトルの中の前記暗号化された要素の暗号化されたインデックスを得るステップと、前記暗号化されたインデックスに基づいて、前記暗号化された要素を選択するステップと、を含み、本方法の前記各ステップは前記第1プロセッサによって行われる、方法。前記暗号化されたベクトル内の前記暗号化された要素の順序は、前記秘密鍵で前記第2プロセッサにより解読された、前記暗号化されたベクトルの複数の要素の値の順序で決定される、請求項1の方法。前記暗号化されたインデックスは、前記暗号化されていない領域において、前記スケーリングされ順列化されたベクトルの中の要素の順序により前記第2プロセッサによって決定され、前記公開鍵で暗号化される、請求項1の方法。前記提供するステップは、前記スケーリングされ順列化されたベクトルを第1加算的ベクトルと第2加算的ベクトルとに分割するステップと、前記第1加算的ベクトルの要素対の差のベクトルを決定するステップと、前記暗号化されたインデックスを決定するために、前記要素対の差のベクトルおよび前記第2加算的ベクトルを前記第2プロセッサへ与えるステップと、をさらに含む、請求項1の方法。前記提供するステップは、前記暗号化されたインデックスを決定するために、前記スケーリングされ順列化されたベクトルを前記第2プロセッサへ与えるステップ、をさらに含む、請求項1の方法。前記選択するステップは、前記インデックスの第1摂動項および第2摂動関数によって修正変更された、前記暗号化されたベクトルを前記第2プロセッサに提供するステップであって、前記暗号化されたインデックスでの前記第2摂動関数の値が零に等しいものである、ステップと、前記暗号化されたインデックスに対応する、前記暗号化されたベクトルの要素を前記第2プロセッサから得るステップと、前記暗号化されたベクトルの前記暗号化された要素を得るために、前記暗号化された領域において前記第1摂動項を減算するステップと、をさらに含む、請求項1の方法。前記暗号化されたインデックスは、順序規則に基づいて決定される、請求項1の方法。前記順序規則は、前記暗号化された要素がそれぞれ、前記暗号化されたベクトル内の最小要素あるいは前記暗号化されたベクトル内の最小要素であるように、最小あるいは最大の要素を選択するものである、請求項7の方法。前記スケーリングするステップは、順序を維持する行列を構成するステップと、前記暗号化されたベクトルに前記順序を維持する行列を乗算するステップと、をさらに含む、請求項1の方法。整数g>0を選択するステップと、次式により順序を維持する行列G∈ZNxNを決定するステップであって、ここで、Zは整数のセット組であり、Nは前記暗号化されたベクトル内の要素の数であり、また、要素giは整数である、ステップと、をさらに含む、請求項9の方法。システムの第1プロセッサと第2プロセッサとの間の安全なマルチパーティ通信を使用して、暗号化されたベクトル内の暗号化された要素を、該暗号化されたベクトル内の該暗号化された要素の順序により、選択するためのシステムであって、前記第2プロセッサは強秘匿な加法的準同形写像暗号システムのための1対の鍵を格納し、該1対の鍵は秘密解読鍵および公開暗号鍵を含み、また、前記暗号化されたベクトルは、前記公開鍵で暗号化されて、前記第1プロセッサに格納され、また、前記第1プロセッサは暗号化された領域においてのみ動作するものであり、前記システムは、前記暗号化されたベクトルの要素の値を、該暗号化されたベクトル内の該要素の順序が維持されるように、スケーリングするための手段と、スケーリングされ順列化されたベクトルを生成するために、前記暗号化されたベクトルの前記要素の順序を順列化する手段と、前記暗号化された領域の情報を前記第2プロセッサへ提供するための手段であって、暗号化されていない領域の情報は、前記スケーリングされ順列化されたベクトルの中の要素の順序を示すものである、手段と、前記スケーリングされ順列化されたベクトルの中の前記暗号化された要素の暗号化されたインデックスを得る手段と、前記暗号化されたインデックスに基づいて、前記暗号化された要素を選択する手段と、を含み、本システムの前記各手段は前記第1プロセッサによって行われる、システム。前記スケーリングされ順列化されたベクトルを第1加算的ベクトルと第2加算的ベクトルとに分割する手段と、前記第1加算的ベクトルの要素対の差のベクトルを決定する手段と、前記暗号化されたインデックスを決定するために、前記要素対の差のベクトルおよび前記第2加算的ベクトルを前記第2プロセッサへ与える手段と、をさらに含む、請求項11のシステム。前記暗号化されたインデックスを決定するために、前記スケーリングされ順列化されたベクトルを前記第2プロセッサへ与える手段、をさらに含む、請求項11のシステム。前記インデックスの第1摂動項および第2摂動関数によって修正変更された、前記暗号化されたベクトルを前記第2プロセッサに提供する手段であって、前記暗号化されたインデックスでの前記第2摂動関数の値が零に等しいものである、手段と、前記暗号化されたインデックスに対応する、前記暗号化されたベクトルの要素を前記第2プロセッサから得る手段と、前記暗号化されたベクトルの前記暗号化された要素を得るために、前記暗号化された領域において前記第1摂動項を減算する手段と、をさらに含む、請求項11のシステム。第1プロセッサと第2プロセッサとの間の安全なマルチパーティ通信を使用して、暗号化されたベクトル内の暗号化された要素を、該暗号化されたベクトル内の該暗号化された要素の順序により、選択するための方法であって、前記第2プロセッサは強秘匿な加法的準同形写像暗号システムのための1対の鍵を格納し、該1対の鍵は秘密暗号鍵および公開解読鍵を含み、また、前記暗号化されたベクトルは、前記公開鍵で暗号化されて、第1プロセッサに格納され、また、前記第1プロセッサは暗号化された領域においてのみ動作するものであり、前記方法は、前記暗号化されたベクトルの要素の値を、該暗号化されたベクトル内の該要素の順序が維持されるように、スケーリングするステップと、スケーリングされ順列化されたベクトルを生成するために、前記暗号化されたベクトルの前記要素の順序を順列化するステップと、前記スケーリングされ順列化されたベクトルを第1加算的ベクトルと第2加算的ベクトルとに分割するステップと、前記第1加算的ベクトルの要素対の差のベクトルを決定するステップと、暗号化されたインデックスを決定するために、前記要素対の差のベクトルおよび前記第2加算的ベクトルを前記第2プロセッサへ与えるステップと、前記スケーリングされ順列化されたベクトルの中の暗号化された要素の暗号化されたインデックスを得るステップと、前記インデックスの第1摂動項および第2摂動関数によって修正変更された、前記暗号化されたベクトルを前記第2プロセッサに提供するステップであって、前記暗号化されたインデックスでの前記第2摂動関数の値が零に等しいものである、ステップと、前記暗号化されたインデックスに対応する、前記暗号化されたベクトルの要素を前記第2プロセッサから得るステップと、前記暗号化されたベクトルの前記暗号化された要素を得るために、前記暗号化された領域において前記第1摂動項を減算するステップと、を含み、本方法の前記各ステップは前記第1プロセッサによって行われる、方法。前記暗号化された要素は前記暗号化されたベクトル内の最小要素である、請求項15の方法。順序を維持する行列を構成するステップと、前記暗号化されたベクトルに前記順序を維持する行列を乗算するステップと、をさらに含む、請求項15の方法。次式により前記順序を維持する行列G∈ZNxNを決定するステップであって、ここで、gは正の整数であり、Zは整数のセット組であり、Nは前記暗号化されたベクトル内の要素の数であり、また、要素giは整数である、ステップ、をさらに含む、請求項17の方法。したがって、暗号化されたベクトル内の暗号化された或る1つの要素を、該暗号化されたベクトル内の該暗号化された複数の要素の順序により、選択する必要がある。この発明は、暗号化されたベクトル内の暗号化された或る1つの要素を、該暗号化されたベクトル内の該暗号化された要素の順序により、選択するためのシステムおよび方法を提供することを目的とする。暗号化されたベクトル内の暗号化された要素の順序は、秘密鍵で解読された、暗号化されたベクトルの複数の要素の値の順序で決定される。たとえば、いくつかのこの発明の実施の形態では、プライバシを保護するように、暗号化されたベクトルから最小要素を選択する。同様に、いくつかの実施の形態では、暗号化されたベクトル内で、最大の要素あるいは所定の順序を有する要素を選択した。この発明の実施の形態では、第1プロセッサと第2プロセッサとの間の安全なマルチパーティ多数共同通信を使用して、暗号化された要素を選択する。第2プロセッサは強秘匿なsemanticallysecure加法的準同形写像暗号システムadditivelyhomomorphiccryptosystem用の1対の鍵を有し、該1対の鍵は秘密鍵と公開鍵とを含む。第2プロセッサは主に、暗号化されていない領域において動作する。反対に、第1プロセッサは公開鍵だけを格納し、暗号化された領域においてのみ動作する。暗号化されたベクトルは、公開鍵で暗号化され、第1プロセッサに格納される。この発明の実施の形態は2つの認識に基づく。第一に、第1プロセッサは順序を維持するマッピングを要素のシーケンスに適用して、その結果を第2プロセッサへ送信することができ、該第2プロセッサは、要素を知らずに、要素の順序に基づいて要素のインデックスを決定することができる。第二に、順序を維持するマッピングは、暗号化されたドメイン領域において適用することができ、それによって、要素のシーケンス全体を第1プロセッサおよび第2プロセッサの両方から秘密にしておく。したがって、この発明の実施の形態では、暗号化されたベクトル内の要素の順序が維持されるように、暗号化されたドメイン領域における暗号化されたベクトルの値をスケーリング拡大、縮小する。順序の順列permutationと組み合わせて、順序を維持しながらスケーリングすることにより、スケーリングされ順列化されたベクトルscaledpermutedvectorを生成する。而して、スケーリングされ順列化されたベクトルに関する情報を、秘密鍵を格納する2番目のプロセッサに与えることができ、一方、暗号化されていない領域の情報はスケーリングされ順列化されたベクトル内の要素の順序を表示する。暗号化されたベクトルの実際の値および実際の順序はスケーリングと順列化permutationによって隠されるので、そのような伝送送信transmissionが可能である。したがって、この発明の実施の形態1は、第1プロセッサと第2プロセッサとの間の安全なマルチパーティ通信を使用して、暗号化されたベクトル内の暗号化された要素を、該暗号化されたベクトル内の該暗号化された要素の順序により、選択する方法を開示するものであり、ここで、上記第2プロセッサは強秘匿な加法的準同形写像暗号システムのための1対の鍵を格納し、該1対の鍵は秘密解読鍵および公開暗号鍵を含み、また、上記暗号化されたベクトルは、上記公開鍵で暗号化されて、上記第1プロセッサに格納され、また、上記第1プロセッサは、該第1プロセッサが暗号化された領域においてのみ動作するように、上記公開鍵だけを格納するものであり、上記方法は、暗号化されたベクトルの要素の値を、該暗号化されたベクトル内の該要素の順序が維持されるように、スケーリングするステップと、スケーリングされ順列化されたベクトルを生成するために、上記暗号化されたベクトルの上記要素の順序を順列化するpermutingステップと、上記暗号化された領域の情報を上記第2プロセッサへ提供するステップであって、暗号化されていない領域の情報は、上記スケーリングされ順列化されたベクトルの中の要素の順序を示すものである、ステップと、上記スケーリングされ順列化されたベクトルの中の暗号化された要素の暗号化されたインデックスを得るステップと、上記暗号化されたインデックスに基づいて、上記暗号化された要素を選択するステップと、を含み、本方法の上記各ステップは上記第1プロセッサによって行われる。他の実施の形態は、システムの第1プロセッサと第2プロセッサとの間の安全なマルチパーティ通信を使用して、暗号化されたベクトル内の暗号化された要素を、該暗号化されたベクトル内の該暗号化された要素の順序により、選択するためのシステムを開示するものであり、ここで、上記第2プロセッサは強秘匿な加法的準同形写像暗号システムのための1対の鍵を格納し、該1対の鍵は秘密解読鍵および公開暗号鍵を含み、また、上記暗号化されたベクトルは、上記公開鍵で暗号化されて、上記第1プロセッサに格納され、また、上記第1プロセッサは暗号化された領域においてのみ動作するものであり、上記システムは、上記暗号化されたベクトルの要素の値を、該暗号化されたベクトル内の該要素の順序が維持されるように、スケーリングするための手段と、スケーリングされ順列化されたベクトルを生成するために、上記暗号化されたベクトルの上記要素の順序を順列化する手段と、上記暗号化された領域の情報を上記第2プロセッサへ提供するための手段であって、暗号化されていない領域の情報は、上記スケーリングされ順列化されたベクトルの中の要素の順序を示すものである、手段と、上記スケーリングされ順列化されたベクトルの中の上記暗号化された要素の暗号化されたインデックスを得る手段と、上記暗号化されたインデックスに基づいて、上記暗号化された要素を選択する手段と、を含み、本システムの上記各手段は上記第1プロセッサによって行われる。さらに他の実施の形態は、システムの第1プロセッサと第2プロセッサとの間の安全なマルチパーティ通信を使用して、暗号化されたベクトル内の暗号化された要素を、該暗号化されたベクトル内の該暗号化された要素の順序により、選択するための方法を開示するものであり、ここで、上記第2プロセッサは強秘匿な加法的準同形写像暗号システムのための1対の鍵を格納し、該1対の鍵は秘密暗号鍵および公開解読鍵を含み、また、上記暗号化されたベクトルは、上記公開鍵で暗号化されて、上記第1プロセッサに格納され、また、上記第1プロセッサは暗号化された領域においてのみ動作するものであり、上記方法は、上記暗号化されたベクトルの要素の値を、該暗号化されたベクトル内の該要素の順序が維持されるように、スケーリングするステップと、スケーリングされ順列化されたベクトルを生成するために、上記暗号化されたベクトルの上記要素の順序を順列化するステップと、上記スケーリングされ順列化されたベクトルを第1加算的ベクトルfirstadditivevectorと第2加算的ベクトルsecondadditivevectorとに分割するステップと、上記第1加算的ベクトルの要素対の差pairwisedifferencesofelementsのベクトルを決定するステップと、暗号化されたインデックスを決定するために、上記要素対の差のベクトルおよび上記第2加算的ベクトルを上記第2プロセッサへ与えるステップと、上記スケーリングされ順列化されたベクトルの中の上記暗号化された要素の暗号化されたインデックスを得るステップと、上記インデックスの第1摂動項firstperturbationtermおよび第2摂動関数secondperturbationfunctionによって修正変更された、上記暗号化されたベクトルを上記第2プロセッサに提供するステップであって、上記暗号化されたインデックスでの上記第2摂動関数の値が零に等しいものである、ステップと、上記暗号化されたインデックスに対応する、上記暗号化されたベクトルの要素を上記第2プロセッサから得るステップと、上記暗号化されたベクトルの上記暗号化された要素を得るために、上記暗号化された領域において上記第1摂動項を減算するステップと、を含み、本方法の上記各ステップは上記第1プロセッサによって行われる。定義この発明の実施の形態について記述する際に、次の定義がそれらの実施の形態上記を含みを通して適用可能である。コンピュータとは、構造化された入力を受け付け、所定の規則により該構造化された入力を処理し、また、その処理の結果を出力として生成することができる、あらゆる装置を指すものである。そのようなコンピュータの例としては、コンピュータ、汎用コンピュータ、スーパーコンピュータ、メインフレーム、スーパーミニコンピュータ、ミニコンピュータ、ワークステーション、マイクロコンピュータ、サーバー、対話型テレビジョン、コンピュータと対話型テレビジョンとのハイブリッド結合組合せ、およびコンピュータおよびまたはソフトウェアをエミュレートするアプリケーションに特有のハードウェア、を含む。コンピュータは、単一のロセッサ、あるいは並列におよびまたは並列ではなく動作することができる多数のプロセッサを有することができる。コンピュータはまた、コンピュータ間で情報を送信または受信するために、ネットワークを介して共に接続された2つ以上のコンピュータをも指す。そのようなコンピュータの一例は、ネットワークによってリンク結合された複数のコンピュータを介して情報を処理するための分散形計算機システム、を含む。中央演算処理装置CPUあるいはプロセッサは、コンピュータ、あるいはソフトウェア命令を読み取って実行するコンピュータのコンポーネント構成要素を指す。メモリあるいはコンピュータ可読媒体は、コンピュータによってアクセス可能なデータを格納するための、あらゆる記憶装置を指す。それらの例としては、磁気ハードディスク、フロッピー登録商標ディスク、CD-ROMまたはDVDのような光ディスク、磁気テープ、メモリチップ、および電子メールを送受信する際あるいはネットワークにアクセスする際に使用されるような、コンピュータが読み取り可能な電子化データを搬送するのに使用される搬送波とたとえばランダムアクセスメモリRAM等のコンピュータメモリー、を含む。ソフトウェアとは、コンピュータを作動させるための所定の予め定められた規則を指す。そのようなソフトウェアの例としては、ソフトウェア、コードセグメント、命令、コンピュータプログラム、およびプログラムされたロジック論理、を含む。インテリジェントシステムのソフトウェアは自己学習ができてもよい。モジュールあるいはユニットとは、タスクあるいはタスクの一部を行うコンピュータ内の基本的なコンポーネント構成要素を指す。それはソフトウェアやハードウェアのいずれかによって実行することができる。この発明の実施の形態は、順序を維持したままのスケーリングを使用することにより、ベクトルの要素対ペアの比較を回避する。マッピングは、暗号化されていない領域における関心要素のインデックスの決定を可能にする。実施の形態1.図1は、第1プロセッサ101と第2プロセッサ102との間の安全なマルチパーティ通信を使用して、暗号化されたベクトル105内の暗号化された要素180を、該暗号化されたベクトル105内の該暗号化された要素180の順序orderにより、選択するための方法100を示している。暗号化されたベクトル内の暗号化された要素の順序は、秘密鍵で解読された、暗号化されたベクトルの複数の要素の値の順序で決定される。暗号化された要素は、順序ルール規則151によって選択される。順序規則の例としては、最小要素を選択すること、最大の要素を選択すること、暗号化されたベクトル内の2番目の最小要素を選択すること、あるいは中央の要素を選択すること、を含む。様々な実施の形態では、第2プロセッサあるいは両方のプロセッサが順序規則を知っている。第2プロセッサは、強秘匿な加法的準同形写像暗号システムのための1対の鍵を有する。その1対の鍵は、秘密解読鍵141および公開暗号鍵161を含む。第2プロセッサは主に、暗号化されていない領域において動作する。反対に、第1プロセッサは暗号化された領域においてのみ動作する。暗号化されたベクトル105は、公開鍵で暗号化され、第1プロセッサに格納される。たとえば、それらの鍵の対ペアκe、κdは、強秘匿な加法的準同形写像公開鍵暗号システムのための暗号化/解読の鍵の対である。暗号化関数はξであり、また、解読関数はξ-1である。加法的準同形写像特性は、要素m1,m2のベクトルに対して、ξm1ξm2=ξm1m2およびξm1m2=ξm1m2を保証する。さらに、要素z∈ZNのベクトルに対して、暗号化されたベクトル105はξz=ξz1、ξz2、、ξzNである。したがって、第1プロセッサは公開暗号鍵κeおよび暗号化されたベクトルξzを有し、第2プロセッサは鍵の対ペアκe、κdを有する。本方法100を行った後に、第1プロセッサはξmin1≦i≦Nziを得る。第2プロセッサは何も得ない。この発明の実施の形態1では、暗号化されたドメイン領域の暗号化されたベクトル内の要素の値をスケーリング110して、スケーリングされたベクトル115を生成する。そのスケーリングの後、暗号化されたベクトル内の要素の順序は維持されている。たとえば、暗号化されたベクトル内の最小要素のインデックスは、スケーリングされたベクトル内の最小要素のインデックスに等しい。そのスケーリングは、以下により詳細に記述されるように、順序を維持する行列210を使用して行われる。次に、スケーリングされたベクトル内の要素の順序は、スケーリングされ順列化されたベクトル125を生成するために、順列化120され、また、暗号化された領域の情報135は第2プロセッサに提供130される。ここで、暗号化されていない領域の情報は、スケーリングされ順列化されたベクトルの中の要素の順序を示す。この発明の実施の形態1では、その情報はスケーリングされ順列化されたベクトル自体である。他の実施の形態では、スケーリングされ順列化されたベクトルを第1加算的ベクトルと第2加算的ベクトルへ分割する。また、情報は、第1加算的ベクトルと第2加算的ベクトルの要素対ペアの差のベクトルである。第2プロセッサは、秘密鍵を使用して情報を解読140して、順序規則151により、暗号化されていない領域の情報142から要素のインデックス151を決定150する。次に、第2プロセッサは公開鍵でそのインデックスを暗号化160して、暗号化されたインデックスを第1プロセッサへ提供165する。第1プロセッサは、暗号化されたインデック165に基づいて、暗号化された要素180を選択170する。様々な実施の形態では、要素の暗号化されたインデックスに基づく暗号化された要素の選択は、以下に述べるように、第1プロセスと第2プロセッサとの間のオブリビアスoblivious:紛失通信に基づいている。順序を維持するスケーリング順序を維持するスケーリングの目的は、ベクトルの要素の順序を維持しながら、暗号化されたベクトルの値を修正変更することである。この発明の実施の形態1は、順序を維持するマッピングが、暗号化されたドメイン領域において適用することができ、それによって、要素のシーケンス全体を第1プロセッサおよび第2プロセッサの両方から秘密にしておく、という認識に基づく。図2は、順序を維持するスケーリングの概略図を示す。たとえば、ベクトル220は5つの要素221~225を有する。要素222および223は等しい値を有する。順序を維持する行列210でベクトル220を乗算することにより、異なる値であるが要素の順序が同じである、5つの要素231~235を有するスケーリングされたベクトル230を生成する。たとえば、インデックス1を有する要素224がベクトル220内の最小要素である場合、同一のインデックス1を有する要素234はスケーリングされたベクトル230内の最小要素である。そのスケーリングは、ベクトル220内の同一の値、たとえば要素222-223、を有する要素がスケーリングされたベクトル230において同一の値を有することを保証しない。しかしながら、要素232-233の異なる値は、スケーリングされたベクトル230内の要素の順序を乱さない。したがって、この発明の実施の形態1では、第1プロセッサは、そのセット{1,2,,N}上で順列πを生成して、ここで、Nは暗号化されたベクトルの大きさであり、順列化permutedされたベクトルξν=πξzを得る。そして、第1プロセッサは整数g>0を選択して、次式によって順序を維持する行列G∈ZNxN210を生成する。この発明の実施の形態1では、スケーリングは、暗号化されたベクトルに順序を維持する行列を乗算することにより達成される。たとえば、スケーリングされ順列化されたベクトルは、ω=Gνである。順序を維持する行列において、要素giは整数である。如何なる1≦i、j≦Nに対して、ωi-ωj=gνi-νjであり、それは、g>0に対して、Gは順序を維持する行列であること、すなわち、ωi≦ωjである時かつそのときに限り、νi≦νjであることを意味する。加法的準同形写像暗号化の特性を使用して、第1プロセッサはξω=ξGνを決定する。順序を表示する情報スケーリングされ順列化されたベクトルに関する情報は、秘密鍵を格納する第2プロセッサに与えられ、たとえば、送信される。一方、基礎となる、暗号化されていない領域の情報は、スケーリングされ順列化されたベクトルの中の要素の順序を表わしており、また、気付かずにobliviously、順序を維持する行列の構成による暗号化されたベクトル内の要素の順序に関するものである。暗号化されたベクトルの実際の値および実際の順序はスケーリングと順列化permutingによって隠されるので、そのような伝送送信が可能である。図3に示される実施の形態では、スケーリングされ順列化されたベクトルが第1加算的ベクトルと第2加算的ベクトルとへ分割され、また、情報は、第1加算的ベクトルおよび第2加算的ベクトル自体の要素対の差のベクトルによって形成される。具体的には、第1プロセッサは、乱数の第1加算的ベクトル315a∈ZNを生成310する。準同形写像特性を使用して、第1プロセッサは、第2加算的ベクトル325ξω-aを決定320する。次に、第1プロセッサは、対ペアの差aΔのベクトル335を構成する。ベクトル335の要素は第1加算的ベクトルaの要素対の差である。したがって、以下となる。対差のベクトル335および第2加算的ベクトル325は、スケーリングされ順列化されたベクトルの中の要素の順序を表示する情報135を形成する。情報135は第2プロセッサに提供130される。この発明の実施の形態の1つの変形例では、対差のベクトルの値がノイズベクトル345で修正変更340される。たとえば、第1プロセッサは、間隔[-g,g]に亘ってランダムノイズηを生成し、-g≦ηij≦gおよびΣ1≦i≦j≦Nηij=ηのように、ノイズベクトルを決定する。対差のベクトルは、aΔ-ηによってノイズベクトルで修正変更され、そして第2プロセッサへ伝送送信される。第2プロセッサは、暗号化された領域において第2付加的加算的シェアsecondadditiveshareを得ており、また、要素毎の解読によってb=ω-aを得る。第1プロセッサは第1加算的ベクトルαを有し、また、第2プロセッサは第2加算的ベクトルbを有し、それらはスケーリングされ順列化されたベクトルωの加算的加法的なシェアである。したがって、αibi≦αjbjのとき、かつそのときに限り、またαi-αj≦bi-bjのとき、かつそのときに限り、ωi≦ωjである。次に、式により、第2プロセッサは、第2加算的加法的シェアの対差のベクトルを決定する。両方の対差aΔおよびbΔのベクトルは要素を含む。第2プロセッサは、aΔ-ηおよび-bΔの対応する要素を比較する。ノイズベクトルηの任意の要素ηijに対して、第2プロセッサは、1≦i<j≦Nに対してαi-αj-ηij≦bj-biであるか否かを決定する。この決定は、行列G行列の構成によって、gνi-νj-ηij≦0であるか否かを決定することと等価である。-g≦ηij≦gであるため、第2プロセッサは、のとき、かつそのときに限り、であると決定する。ここで、オペレータは、場合に応じて、より大きい、またはより小さいを意味する。而して、νi≠νjのとき、順序が維持される。νi=νjならば、第1プロセッサによって選択されたノイズベクトルηijの要素の値に依存して、αi-αj-ηijはbj-biより大きくなったり、あるいは、小さくなったりする。しかしながら、このような摂動変動:perturbationにより、第2プロセッサが、スケーリングされ順列化されたベクトルの要素を知らずに、インデックス151、たとえば、α=argmin1≦i≦Nνi、を決定することをさらに可能にする。暗号化されたインデックス165は第1プロセッサに与えられる。要素の暗号化されたインデックスに基づいて選択すること様々な実施の形態では、暗号化された要素の選択を該要素の暗号化されたインデックスに基づいて行うことが、第1プロセッサと第2プロセッサとの間のオブリビアス紛失通信を使用する。たとえば、1つの実施の形態では、第1プロセッサは、1≦i≦Nに対して、数γおよびβiをランダム無作為に選択して、ξβii-ανiγを決定するために、準同形写像特性を使用する。ここで、γは第1摂動項であり、また、βii-αは、その値が暗号化されたインデックスで零と等しいインデックスの第2摂動関数である。第1プロセッサは、その結果として生じる、N個の暗号化されたエントリー項目を有するベクトルを第2プロセッサへ与える。第2プロセッサは、修正変更された要素ναγを得るためインデックスi=αに対応するエントリーを解読する。第2プロセッサは、修正変更された要素を再暗号化して、第1プロセッサに提供する。第1プロセッサは、次式を介して第1摂動項γにより導入されたノイズを削除して暗号化された要素180を生成するために、加法的準同形写像特性を使用する。図4は、この実施の形態の、自明である擬似コードを示す。従来の方法は、安全なミリオネアmillionaireプロトコルの変形例を使用して、プライバシを保護したままベクトルの要素を決定する。たとえば、それらの方法は、ベクトルの最小要素を決定するために、安全なミリオネアプロトコルを繰り返し適用することを行う。しかしながら、それらの方法は、両方のプロセッサでの通信オーバヘッドがN2に比例するので、計算演算上非能率的である。この発明の実施の形態は、順序を維持したままのスケーリングを使用することにより、ベクトルの要素対ペアの比較を回避する。マッピングは、暗号化されていない領域における関心要素のインデックスの決定を可能にする。この発明は好ましい実施の形態の例として記述されたが、この発明の趣旨および範囲内で、様々な他の改変および変更が行われてもよいことが理解されるべきである。したがって、この発明の真実の趣旨および範囲内に入るような、すべての変更例および変形例をカバーすることが、添付の特許請求の範囲の目的である。"