"暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第1のシーケンスから第2のシーケンスへの変形の最小コストの暗号化として求めるための方法であって、前記最小コストを、行列の動的計画法による解として定式化するステップであって、前記行列の要素が、以前に求められた要素の値に基づいて再帰的に求められるものと、前記行列の現在の要素を、第1の要素、第2の要素、及び第3の要素の最小値の暗号化として求めるステップであって、前記第1の要素は前記挿入コストを表し、前記第2の要素は前記削除コストを表し、前記第3の要素は前記置換コストを表し、前記現在の要素、前記第1の要素、前記第2の要素、及び前記第3の要素が、公開鍵を用いて準同型に暗号化されるものと、前記求めるステップを再帰的に反復して前記動的計画法による解を生成するステップと、前記動的計画法による解を前記暗号化された編集距離として選択するステップと、を含み、該方法の複数の前記ステップは、第1のプロセッサ及び第2のプロセッサによって実行され、前記第1のシーケンスが前記第1のプロセッサにのみ格納されると共に前記第2のプロセッサから秘密にされ、前記第2のシーケンスが前記第2のプロセッサにのみ格納されると共に前記第1のプロセッサから秘密にされるようにする、方法。前記求めるステップは、意味論的にセキュアな準同型暗号化の特性に基づくものである、請求項1に記載の方法。前記第1のプロセッサ及び前記第2のプロセッサに前記公開鍵を提供するステップと、前記第1のプロセッサにのみ秘密鍵を提供するステップと、をさらに含む、請求項1に記載の方法。前記暗号化された編集距離を前記第1のプロセッサに送信するステップと、前記暗号化された編集距離を前記秘密鍵を用いて復号するステップと、をさらに含む、請求項3に記載の方法。前記行列の初期要素を前記置換コストとして求めるステップをさらに含み、前記第1の要素は前記第1のシーケンスの第1のシンボルであり、前記第2の要素は前記第2のシーケンスの第1のシンボルである、請求項1に記載の方法。前記現在の要素をξS,MD,MI=ξに従って求めるステップであって、ここで、ξは暗号化関数であり、Mは前記現在の要素であり、Iはシンボルyjの前記挿入コストであり、Dはシンボルxiの前記削除コストであり、Sは前記シンボルxiを前記シンボルyjに置換する前記置換コストであり、i及びjは前記シーケンス内の前記シンボルのインデックスであるものをさらに含む、請求項1に記載の方法。前記第1の要素を、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求めるステップと、前記第2の要素を、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求めるステップと、前記第3の要素を、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求めるステップと、をさらに含む、請求項6に記載の方法。前記第1の要素、前記第2の要素、及び前記第3の要素を前記第1のプロセッサに送信するステップをさらに含む、請求項7に記載の方法。最小値発見方法を使用して前記現在の要素を求めるステップであって、該最小値発見方法が、準同系に暗号化された形式で数字の最小値の暗号化を求めるようにされているものをさらに含む、請求項1に記載の方法。前記第1の要素、前記第2の要素、及び前記第3の要素のそれぞれについて、暗号化された和を求めるステップであって、暗号化された和の集合を生成し、前記暗号化された和はに従って求められ、ここで、i=1,2,...,L及びL=3であり、μは定数であり、αはランダムに選択される整数シフトであり、ri、r0はランダムに選択される暗号化係数であり、暗号化係数r’i=rir0であり、ξは暗号化関数であるものと、前記第2のプロセッサから前記第1のプロセッサに前記暗号化された和の集合を送信するステップであって、前記第1のプロセッサは、秘密鍵を使用して前記暗号化された和を復号し、前記暗号化された和の集合から最小値を求めると共に、該最小値を前記公開鍵を用いて暗号化して前記現在の要素を生成するようにされたものと、前記第2のプロセッサによって、前記第1のプロセッサから送信された前記現在の要素を受信するステップと、をさらに含む、請求項9に記載の方法。スケーリング定数μを2の累乗として選択するステップと、前記第2のプロセッサによって、各前記整数シフトが前記スケーリング定数よりも小さくなるように、前記第1の要素、前記第2の要素、及び前記第3の要素のために異なる整数シフトαi、i=1,2,3を選択するステップと、前記第2のプロセッサから前記第1のプロセッサに前記暗号化された和の集合を送信するステップであって、前記第1のプロセッサは秘密鍵を使用して前記暗号化された和を復号し、前記暗号化された和の集合から最小値を求め、該最小値をバイナリ形式に変換すると共に、該最小値を暗号化して暗号化されたビットを生成するものと、前記第2のプロセッサによって、前記第1プロセッサから前記暗号化されたビットを受信するステップと、前記整数シフトαi及び前記スケーリング定数μに基づいて前記暗号化されたビットから関連するビットのみを選択するステップと、をさらに含む、請求項10に記載の方法。前記置換コストは、前記第1のシーケンスからのシンボル及び前記第2のシーケンスからのシンボルの多項式関数である、請求項1に記載の方法。前記置換コストは、前記第1のシーケンスからのシンボルと前記第2のシーケンスからのシンボルとの間の絶対距離である、請求項1に記載の方法。前記置換コストは、前記第1のシーケンスからのシンボルが前記第2のシーケンスからのシンボルと異なる場合に或る定数であり、前記第1のシーケンスからの前記シンボルが前記第2のシーケンスからの前記シンボルと同一である場合にゼロである、請求項1に記載の方法。前記第1のシーケンスと前記第2のシーケンスとの間の最も長い共通サブシーケンスの長さを求めるステップをさらに含む、請求項1に記載の方法。暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第1のシーケンスから第2のシーケンスへの変形の最小コストの暗号化として求めるように構成されたシステムであって、前記最小コストは行列の動的計画法による解であり、前記行列の要素は、以前に求められた要素の値に基づいて再帰的に求められ、該システムは、前記行列の現在の要素を、第1の要素、第2の要素、及び第3の要素の最小値の暗号化として求めるように構成される第1のプロセッサであって、前記第1の要素は前記挿入コストを表し、前記第2の要素は前記削除コストを表し、前記第3の要素は前記置換コストを表し、前記現在の要素、前記第1の要素、前記第2の要素、及び前記第3の要素は、公開鍵を用いて準同型に暗号化されるものと、加法的準同型暗号化の特性に基づいて、前記第1の要素、前記第2の要素、及び前記第3の要素を求めるように構成される第2のプロセッサであって、前記第1のシーケンスは前記第1のプロセッサにのみ格納されると共に該第2のプロセッサから秘密にされ、前記第2のシーケンスは該第2のプロセッサにのみ格納されると共に前記第1のプロセッサから秘密にされるものと、前記動的計画法による解を再帰的に求める手段と、前記動的計画法による解を前記暗号化された編集距離として選択する手段と、を備える、システム。前記公開鍵は前記第1のプロセッサ及び前記第2のプロセッサに提供され、秘密鍵は前記第1のプロセッサにのみ提供される、請求項16に記載のシステム。前記第1のプロセッサは、前記現在の要素をξS,MD,MI=ξに従って求める手段を備え、ここで、ξは暗号化関数であり、Mは前記現在の要素であり、Iはシンボルyjの前記挿入コストであり、Dはシンボルxiの前記削除コストであり、Sは前記シンボルxiを前記シンボルyjに置換する前記置換コストであり、i及びjは前記シーケンス内の前記シンボルのインデックスである、請求項16に記載のシステム。前記第2のプロセッサは、前記第1の要素を、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求める手段と、前記第2の要素を、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求める手段と、前記第3の要素を、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求める手段と、を備える、請求項16に記載のシステム。前記第1のプロセッサは、最小値発見方法を使用して前記現在の要素を求める手段であって、該最小値発見方法は、準同系に暗号化された形式で数字の最小値の暗号化を求めるように構成されているものをさらに備える、請求項16に記載のシステム。したがって、2つのシンボルシーケンス間で暗号化された編集距離をセキュアに求めるための計算効率のよい方法を見出す必要がある。この発明の実施の形態は、数字の最小値の暗号化を準同型に暗号化された形式で求めるように構成される最小値発見方法を開示する。この発明の1つの実施の形態は、暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第1のシーケンスから第2のシーケンスへの変形の最小コストの暗号化として求めるための方法を開示する。この方法は、行列の現在の要素を、第1の要素、第2の要素、及び第3の要素の最小値の暗号化として再帰的に求め、動的計画法による解を生成する。前記第1の要素は挿入コストを表し、前記第2の要素は削除コストを表し、前記第3の要素は置換コストを表し、前記現在の要素、前記第1の要素、前記第2の要素、及び前記第3の要素は、公開鍵を用いて準同型に暗号化される。この方法は、動的計画法による解を前記暗号化された編集距離として選択する。この方法のステップは、第1のプロセッサ及び第2のプロセッサによって実行され、前記第1のシーケンスが前記第1のプロセッサにのみ格納されると共に前記第2のプロセッサから秘密にされ、前記第2のシーケンスが前記第2のプロセッサにのみ格納されると共に前記第1のプロセッサから秘密にされるようにする。この発明の別の実施の形態は、暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第1のシーケンスから第2のシーケンスへの変形の最小コストの暗号化として求めるように構成されるシステムであって、前記最小コストは行列の動的計画法による解であり、前記行列の要素は、以前に求められた要素の値に基づいて再帰的に求められる、システムを開示する。このシステムは、第2のプロセッサとインタラクトして、前記行列の現在の要素を、第1の要素、第2の要素、及び第3の要素の最小値の暗号化として求めるように構成される第1のプロセッサであって、前記第1の要素は前記挿入コストを表し、前記第2の要素は前記削除コストを表し、前記第3の要素は前記置換コストを表し、前記現在の要素、前記第1の要素、前記第2の要素、及び前記第3の要素は、公開鍵を用いて準同型に暗号化されるものと、加法的準同型暗号化の特性に基づいて、前記第1の要素、前記第2の要素、及び前記第3の要素を求めるように構成される第2のプロセッサであって、前記第1のシーケンスは前記第1のプロセッサにのみ格納されると共に該第2のプロセッサから秘密にされ、前記第2のシーケンスは該第2のプロセッサにのみ格納されると共に前記第1のプロセッサから秘密にされるものと、前記動的計画法による解を再帰的に求める手段と、前記動的計画法による解を前記暗号化された編集距離として選択する手段とを備える。暗号化された編集距離図3は、暗号化された編集距離345を、シンボルの第1のシーケンス315からシンボルの第2のシーケンス325への変形の最小コストの暗号化としてセキュアに求める方法300の概略図を示している。変形のコストは、下記でより詳細に説明するように、挿入コスト332、削除コスト334、及び置換コスト336に基づいて求められる。この明細書において定義される場合、挿入コストはシンボルを第2のシーケンス内に挿入するコストであり、削除コストは第2のシーケンスからシンボルを削除するコストであり、置換コストは第2のシーケンスからのシンボルを第1のシーケンスからのシンボルに置換するコストである。シーケンス315及び325内のシンボルは、たとえば、ビット、文字、数字、及びDNAヌクレオチドであり得る。この発明の様々な実施の形態において、置換コスト、挿入コスト、及び削除コストは、定数であるか、又は置換、挿入、若しくは削除されるシンボルに依拠する。方法300のステップは第1のプロセッサ310及び第2のプロセッサ320によって実行され、第1のシーケンスが第1のプロセッサにのみ格納され、第2のシーケンスが第2のプロセッサにのみ格納されるようにされる。第1のプロセッサと第2のプロセッサとの間で送信されるデータは、公開鍵360を用いて準同型に暗号化される。公開鍵は、第1のプロセッサ及び第2のプロセッサの双方に利用可能である。しかしながら、第1のプロセッサのみが秘密鍵350を有し、このため、第1のプロセッサのみがシンボルを復号することができる。この発明の実施の形態は、変形の最小コストを、システム、すなわち行列326の動的計画法による解として定式化する。行列の暗号化された要素は、以前に求められた要素の値に基づいて再帰的に求められる。第1のシーケンス及び第2のシーケンスは、方法300への入力である。シンボルxi及びyjは、有限アルファベット集合Aに属する。便宜上、サブシーケンスはであり、ここで、インデックスa、bは適切な制限内にあり、シンボルykの挿入コストはIであり、シンボルxkの削除コストはDであり、シンボルxkをシンボルyiに置換する置換コストはSであり、ここでk及びiはシーケンス内のシンボルのインデックスである。挿入コストI、削除コストD、及び置換コストSは様々な実施の形態にわたって変動する。Mがサブシーケンスをサブシーケンスに変形する最小コストである場合、1≦i≦n及び1≦j≦mについて以下となる。上述したように、式における行列の要素は再帰的に求められる。すなわち、Mは、M、M、及びMを使用して計算される。さらに、編集距離Mは、第1のシーケンスを第2のシーケンスに変形する最小コストである。図3に示す例では、文字列FAST及びFIRST間の編集距離340はM=2である。方法300は、第2のプロセッサにおける暗号化された領域内の行列の要素を求め、第2のプロセッサは、秘密鍵なしで要素の値を復号することができない。この発明の実施の形態は、意味論的にセキュアな準同型暗号化の特性に基づいて、暗号化された数字の集合から最小の数字をセキュアに求めることが可能であるという認識に基づいている。動的計画法による解345が暗号化された編集距離として選択される。暗号化された編集距離をメモリ内に格納しかつ/又は秘密鍵を用いた復号のために第1のプロセッサに送信することができる。図5は、編集距離を求めることが、式に従ってMを計算することにまで低減されたものを示している。それぞれ第1のシーケンス及び第2のシーケンスの全てのi及びjについて、第1のプロセッサ及び第2のプロセッサは、最小値発見方法400を使用して、行列の現在の要素460を、第1の要素510、第2の要素520、及び第3の要素530の最小値の暗号化として求める。ここで、第1の要素は挿入コスト332を表し、第2の要素は削除コスト334を表し、第3の要素は置換コスト336を表し、現在の要素、第1の要素、第2の要素、及び第3の要素は、公開鍵360を用いて準同型に暗号化される。現在の要素Mの暗号化された値は、ξS,MD,MI=ξに従って求められる。値M344、M346、及びM342は、方法300の以前の反復によって求められる。挿入コストIの暗号化、すなわちξは、第1のプロセッサから第2のプロセッサに送信される。削除コストD及びしたがって暗号化ξは第2のプロセッサに利用可能である。置換コストSの暗号化、すなわちξは、下記で説明するように動的に提供されるか又は求められる。挿入コストを表す第1の要素は、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求められる。削除コストを表す第2の要素は、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求められる。置換コストを表す第3の要素は、加法的準同型暗号化の特性に基づいてξξ=ξMに従って求められる。次に、最小値発見方法は、第1の要素、第2の要素、及び第3の要素を入力として受け取り、現在の要素を最小値の暗号化された値として求める。実施の形態では、現在の要素、第1の要素、第2の要素、及び第3の要素は公開鍵を用いて準同型に暗号化される。いくつかの実施の形態では、初期要素Mのための置換コストの表現、すなわちMSは、全ての可能なx1,y1について双方の要素M及びM以下である。さらに、挿入コスト及び削除コストは全てのシンボルについて等しく、双方のプロセッサに知られている。1つのそのような一般的に発生する例が図2及び図3に示されている。それらの図においてM=0、S=1である。この実施の形態において、任意のシンボルのための挿入コスト及び削除コストは1であり、このため双方のプロセッサがM=M=1であることを知っている。したがって、要素Mの暗号化は最小値発見方法を使用して求められない。この実施の形態では、第2のプロセッサは、適切な置換コストを使用して、ξ=ξに従って初期の暗号化された要素を求める。様々な実施の形態において、置換コストの暗号化は、所定であるか又は下記で説明するように動的に計算される。行列M内の各要素の暗号化を再帰的に求めた後、1つの実施の形態において、第2のプロセッサは、暗号化された編集距離ξの値を第1のプロセッサに送信する。第1のプロセッサはこの値を復号し、2つのシーケンス及び間の編集距離を取得する。1つの実施の形態では、第1のプロセッサは編集距離の値を第2のプロセッサに返送する。このため、編集距離はプライバシーを侵害することなく求められる。すなわち、第1の信号は第1のプロセッサにのみ知られ、第2の信号は第2のプロセッサにのみ知られる。準同型暗号化Pを二項演算子に関連付けられる平文の集合とし、Hを二項演算子に関連付けられる暗号文の集合とする。定義1全てのa,b∈Pについて以下が成り立つ場合、マッピングξ:P→Hは準同型である。実施の形態は準同型暗号システムを使用する。準同型暗号システムにおいて、演算子は加法演算子であり、演算子は乗法演算子である。そのような暗号システムは、加法性準同型の、たとえばベナロー暗号システム及びパイエ暗号システムと呼ばれることがある。これらの双方の暗号システムは意味論的にセキュアである。すなわち、同じ平文の反復暗号化の結果、異なる暗号文が生じる。この発明の実施の形態は、様々な意味論的にセキュアな加法性準同型暗号システムを使用する。例として、パイエ暗号システムを以下に簡潔に要約する。構成:2つの大きな素数p、qを選択し、N=pqとする。によって、N2を法とする逆数を有する非負整数の集合を表す。gcd,N=1となるようにを選択する。ここで、λ=lcm及びである。を公開鍵とし、を秘密鍵とする。暗号化:を平文とする。次いで、暗号文が以下によって与えられる。ξr=gmrNmodN2ここで、はランダムに選択される数字である。復号:を暗号文とする。次いで、以下に従って対応する平文が求められる。復号は暗号化の間に使用される数字rの値に関わらず機能する。数字rは全ての暗号化ごとにランダムで選択することができるため、パイエ暗号システムは確率的であり、したがって意味論的にセキュアであり、すなわちである。また、式に従った、平文集合から暗号文集合へのマッピングの特性は、以下の関係を満たす。ここで、m1及びm2は任意の2つの整数メッセージであり、上記で説明した暗号システムを使用して暗号化される。上記の下付き文字r1、rは、式におけるパラメーターrを表し、式におけるrの異なる値によって結果として異なる暗号文が生じるように、暗号化時に選択される。rの値を暗号化ごとに変更することによって、パイエ暗号化は意味論的セキュリティを達成する。この明細書において、意味論的セキュリティの概念に関連しない場合、下付き文字rは表記を簡単にするために省かれる。この発明のいくつかの実施の形態はパイエ暗号化を使用する。しかしながら、他の実施の形態は他の意味論的にセキュアな加法性準同型方式を使用する。最小値発見方法図4は、この発明の実施の形態による、暗号化された数字の集合における最小の数字の暗号化を求めるための方法400のブロック図である。方法400は、この発明の実施の形態によって、行列の現在の要素を、第1の要素、第2の要素、及び第3の要素の最小値の暗号化として求めるのに使用される。たとえば、第2のプロセッサ320は、準同型に暗号化された形式の数字の集合たとえば、L個の数字a1,a2,...,aLの410を格納する。最小値発見方法によって、第2のプロセッサが、これらの数字の最小値の暗号化を求める、すなわち、或る係数について、ξr460を求めることが可能になる。方法400は、第2のプロセッサが、ai又は最小値のインデックス若しくは値に関するいかなる情報も見つけ出すことを可能にしない。同様に、第1のプロセッサは数字a1,a2,...,aLに関するいかなる情報も見つけ出さない。この方法のステップは以下の通りである:1.第2のプロセッサが、正の整数μ及びα450をランダムに選択する。すなわちμはスケーリング定数であり、αはランダムに選択される整数シフトである。パイエ暗号システムの場合、μを後に除去することができることを確実にするために、第2のプロセッサはμを集合からランダムに選択する。次いで、第2のプロセッサは公開鍵360を使用して暗号化451を取得し、i=1,2,...,Lについて暗号化された和420を求めて暗号化された和の集合420を生成し、該暗号化された和の集合を第1のプロセッサに送信する。パイエ暗号システムの場合、暗号化係数r’i=rir0であり、第2のプロセッサは暗号化係数riを知ることなく暗号化係数r’iを求めることができない。2.第1のプロセッサが秘密鍵350を用いて数字を復号し、miniμaiα430によって与えられる最小値を求め、次いで、その結果を公開鍵を用いて暗号化して暗号化された最小値460を生成し、該暗号化された最小値を第2のプロセッサに返送する。3.第2のプロセッサが452を計算し、470を求める。非常に高い確率で、ξrが、暗号化のうちのいずれとも等しくないことに留意されたい。これは、第1のプロセッサが、第2のプロセッサに知られていないランダムな暗号化係数rBを選択し、これによって暗号化が意味論的にセキュアになるためである。これによって、第2のプロセッサが最小値の暗号化を取得するとき、元のシーケンスにおける最小値のインデックスが第2のプロセッサから隠されたままであることが確実になる。4.第2のプロセッサは、1/μ=1/μ=ξrに従って、いずれが暗号化された最小値460であるのかを確定する。正の整数μ及びαを使用することによって、第1のプロセッサが数字αiのいかなる情報を見つけ出すことも阻止されることに留意されたい。さらに、意味論的セキュリティに起因して、第2のプロセッサは最小値のインデックスiを見つけ出すことができない。最後に、第2のプロセッサは、復号鍵を有しないため、最小値の実際の値を求めることができない。編集距離を求めるために、3つの値、すなわち上記のL=3を用いて最小値発見方法が実行される。1つの実施の形態では、各シンボルが正の挿入コスト及び削除コスト、並びに非負の置換コストを有する。他の実施の形態では、いくつかのシンボルは負若しくはゼロの挿入コスト及び/又は負若しくはゼロの削除コストを有する。付加的に又は代替的に、挿入コスト、削除コスト、及び置換コストに対応する3つのエントリ全てを等しくすることができる。そのような場合、第1のプロセッサが変数μ及びαの値を求めることができない場合であっても、第1のプロセッサは各シンボルの挿入コストに基づいて、最小値を求めることができる。そのような実施の形態では、第2のプロセッサは、ベクトルに2つ以上のダミー変数を付加する。すなわち、L>3である。最小値発見方法の各反復において、第1のプロセッサがダミー変数に関するいかなる情報を取得することも阻止するために、異なるダミー変数及び/又は異なる数のダミー変数が使用される。次いで、第1のプロセッサは、上記のステップ2のように復号し最小値を求めた後で、1つ又は複数の暗号化された値を求めて該値を第2のプロセッサに送信する。たとえば、いくつかの実施の形態では、第2のプロセッサはベクトルにダミーの変数ξ及びξを付加する。ここで、aiの全ての値と比較して、変数Aは大きい数であり、変数Bは小さい数である。次いで、第2のプロセッサは、第1のプロセッサからの2つの最も小さい値の暗号化を要求する。その際いずれの値が最も小さく、いずれの値が2番目に小さいかが特定される。第1のプロセッサは最も小さい値が変数Bに対応することを知っているため、第2のプロセッサは、第1のプロセッサから受信した最小値のインデックスに対応する暗号化された要素を除外し、真の最小値の暗号化された値として2番目に小さい値の暗号化を選択する。いくつかの実施の形態では、共通の定数αを有する代わりに、第2のプロセッサは2の累乗としてμを使用し、全てのi=1,2,...,Lについてαi<μとなるように様々な等しくない定数α1、α2,...,αLを選択する。第2のプロセッサは、上記のステップ1のように暗号化ξを第1のプロセッサに送信する。次いで、第1のプロセッサは、ステップ2と同様に、暗号化を復号し、最小値miniμaiαiを求める。しかしながら、第1のプロセッサは、最小値の暗号化を返送する代わりに、最小値をバイナリに変換し、各ビットを暗号化し、該暗号化されたビットを第2のプロセッサに送信する。第2のプロセッサがα1、α2,...,αLの値を選択したため、第2のプロセッサはαiに対してどれだけ多くのビットが利用されたかを正確に知り、μによってスケーリングされた所望の最小値に対して残りのビットが利用されたことを知っている。全てのi=1,2,...,Lについてαi<μであるため、これらのビット間に重複が存在しないことに留意されたい。このため、準同型暗号化の特性を使用して、第2のプロセッサはμによってスケーリングされた最小値に対応するビットを取得する。次いで、第2のプロセッサは上記のステップ4に従ってμによって乗算を反転させる。第1のプロセッサは、aiの値のうちの1つ又は複数が等しい場合であっても、最小値の値を知ることを阻止される。置換コストを求めるこの発明の実施の形態は、行列の現在の要素を、挿入コスト、削除コスト、及び置換コストを表す要素の最小値の暗号化として求める。異なる実施の形態では、挿入コスト、削除コスト、及び置換コストは所定であるか、動的に求められるか、又はそれらの組み合わせが使用される。たとえば、1つの実施の形態では、挿入コスト、削除コスト、及び置換コストは所定である。これらの実施の形態の1つの変形形態では、全てのコストは整数値である。別の実施の形態では、挿入コスト及び削除コストは所定であるが、置換コストは動的に求められる。この実施の形態の1つの変形形態では置換コストは置換されるシンボルの値に基づいて求められる。定数の置換コスト1つの実施の形態では、置換コストは、第1のシーケンス及び第2のシーケンスが異なる場合に或る定数であり、シンボルが同一である場合にゼロである。この実施の形態の1つの変形形態は、アルファベットのシンボルを整数集合1,2,3,...,Qにマッピングする。ここでQはアルファベット集合のサイズである。たとえば、シンボルA、T、C、Gを有するDNAシーケンスの場合、サイズQ=4である。この実施の形態における置換コストは、a=bの場合にS=0であり、a≠bの場合にSである。ここでaは第1のシーケンスのシンボルであり、bは第2のシーケンスのシンボルである。図6は、以下のステップに従って定数の置換コストを求めるための方法の擬似コードを示している。1.第1のプロセッサが第1の文字列のシンボルaを、最初のa個のビットが1に等しく、最後のQ-a個のビットが0に等しい長さQの第1のバイナリシーケンスに変換する。第1のバイナリ文字列からの文字列はaiとして定義される。ここでiは1からQの範囲をとる。同様に、第2のプロセッサが第2のシーケンスのシンボルbを、最初のb個のビットが1に等しく、最後のQ-b個のビットが0に等しい長さQの第2のバイナリシーケンスに変換する。2.第1のプロセッサが、第1のバイナリシーケンス内の各ビットの暗号化を第2のプロセッサに送信する。3.第2のプロセッサが、第2のバイナリ列からの第1のビット及び第2のビット、並びに第1のバイナリシーケンスからの第1の暗号化されたビット及び第2の暗号化されたビットから、ξ=ξ=ξξ=[ξのa1乗][ξの乗]に従って2×2の行列式を計算する。4.第2のプロセッサが双方のバイナリシーケンスからの第2のビット及び第3のビットに対して、次いで第3のビット及び第4のビットに対して、そして以下同様に、長さQのシーケンス全体が使い果たされるまで以前のステップを反復する。このようにして、第2のプロセッサは暗号化された2×2の行列式ξ,ξ,...,ξを求める。5.第2のプロセッサは行列式ξの和をΠiξ=ξとして計算する。ここでiは1からQ-1で変動する。これは加法的準同型暗号化の特性を使用する。6.第2のプロセッサは数字dをランダムに選択し、ξ=ξξを計算し、結果を第1のプロセッサに送信する。7.第1のプロセッサは2つの数字を暗号化し、積2=U’を求め、積U’を暗号化してξを第2のプロセッサに返送する。8.第2のプロッセッサーがξξξ=ξ=ξを計算する。構築によって、U=0、1、又は-1である。したがって、U2は、シンボルa及びbが同じであるか又は異なっているかにそれぞれ依拠して、0又は1である。このため、ξは置換コストの暗号化された値を提供する。第2のプロセッサは、実際の時間コストではなく暗号化された置換コストしか取得しない。これは、第2のプロセッサが復号鍵を有しないためである。第1のプロセッサは数字dを知らないことに起因して何も知らない。絶対距離置換コスト別の実施の形態では、置換コストは第1のシーケンスのシンボルと第2のシーケンスのシンボルとの間の絶対距離であり、すなわち、シンボルがそれぞれa及びbである場合、置換コストS=|a-b|である。上述の実施の形態と同様に、アルファベットにおけるシンボルは整数集合1,2,3,...,Qにマッピングされる。最小化プロトコルによれば、第1のプロセッサは置換コストの暗号化を求めることができる。第2のプロセッサは求めることができない。図7は、以下のステップに従って絶対距離置換コストを求めるための方法の擬似コードを示している。1.第1のプロセッサが第1のシーケンスのシンボルaを、最初のa個のビットが1に等しく、最後のQ-a個のビットが0に等しい長さQの第1のバイナリシーケンスに変換する。第1のバイナリ文字列からの文字列はaiとして定義される。ここでiは1からQの範囲をとる。同様に、第2のプロセッサが第2のシーケンスのシンボルbを、最初のb個のビットが1に等しく、最後のQ-b個のビットが0に等しい長さQの第2のバイナリシーケンスに変換する。2.第1のプロセッサが、バイナリシーケンス内の各ビットの暗号化を第2のプロセッサに送信する。3.第2のプロセッサが、加法的準同型暗号化の特性に基づいて以下の式に従って置換コストの暗号化ξを求める。4.多項式関数置換コスト別の実施の形態では、参照によりこの明細書に援用される米国特許出願第12/495,721号に記載されているように、置換コストは2つのシーケンスのシンボルに多項式関数を適用した結果である。たとえば、第2のプロセッサは整数aを格納し、第1のプロセッサは整数bを格納する。実施の形態は、第2のプロセッサにおいて、暗号化された形式の置換コストを求める。置換コストS=Sはbにおける次数Sの多項式であり、すなわち0≦j≦Sである。このため、第2のプロセッサは、或る暗号化係数について置換コストξを求める。第2のプロセッサは、秘密鍵を保有していないため、置換コストを復号することができない。第1のプロセッサは整数bの値しか知らない。ステップは以下の通りである:1.0≦j≦Sについて、第1のプロセッサがbjを暗号化し、を第2のプロセッサに送信する。2.第2のプロセッサがci,j及びaの値に基づいてを求める。この方法は、紛失通信に基づく方法と比較して、多項式評価法に関して大幅に低い計算及び通信のオーバーヘッドを受ける。紛失通信に基づく方法は非常に単純な多項式の場合であっても極度に複雑となり、大きな送信オーバーヘッドを受ける。最も長い共通サブシーケンスこの発明の1つの実施の形態は、第1のシーケンスと第2のシーケンスとの間の最も長い共通サブシーケンスの長さを求める。この実施の形態は、多くの点において編集距離を求めるための実施の形態に類似している。主な違いは2つしかない。第1に、方法の各ステップにおいて3つの要素の最小値を計算する代わりに、この実施の形態は3つの要素の最大値を求める。たとえば、数値の場合、2つのプロセッサは全ての値の符号を逆にし、上述した最小値発見方法を使用する。第2に、セッサがmn個の暗号化された要素を用いて1つ又は複数の最大値発見プロトコルを実行して、所望の結果を取得することを意味する。所望の結果は、最も長い共通サブシーケン編集距離を行列の最後の要素Mとして選択する代わりに、行列全体を検索して該行列内の最大の要素を発見する。最大の要素の暗号化は、行列M内の各要素の符号を逆にし、上述した最小化プロトコルを適用することによって発見することができる。次いで、取得した結果が第1のプロセッサに送信され、第1のプロセッサは、該結果を復号して最大の要素を取得する。最大の要素は最も長い共通サブシーケンスの長さを与える。これは、行列全体を計算した後、2つのプロスの長さの暗号化である。この発明を好ましい実施の形態の例として説明してきたが、この発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、この発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。"