シンボルシーケンスの編集距離のプライバシーを保護した計算の方法およびシステム
【課題】暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるためのシステム及び方法を提供する。
【解決手段】行列３２６の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として再帰的に求め、動的計画法による解３４５を生成する。第１の要素は挿入コスト３３２を表し、第２の要素は削除コスト３３４を表し、第３の要素は置換コスト３３６を表す。現在の要素、第１の要素、第２の要素、及び第３の要素は、公開鍵３６０を用いて準同型に暗号化される。そしてこの方法３００は、動的計画法による解３４５を暗号化された編集距離として選択する。この方法３００のステップは、第１のプロセッサ３１０及び第２のプロセッサ３２０によって実行される。
【解決手段】行列３２６の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として再帰的に求め、動的計画法による解３４５を生成する。第１の要素は挿入コスト３３２を表し、第２の要素は削除コスト３３４を表し、第３の要素は置換コスト３３６を表す。現在の要素、第１の要素、第２の要素、及び第３の要素は、公開鍵３６０を用いて準同型に暗号化される。そしてこの方法３００は、動的計画法による解３４５を暗号化された編集距離として選択する。この方法３００のステップは、第１のプロセッサ３１０及び第２のプロセッサ３２０によって実行される。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には２つのシンボルシーケンス間の編集距離を求めることに関し、より詳細には、２つのシンボルシーケンス間の暗号化された編集距離をセキュアに求めることに関する。
【背景技術】
【０００２】
２つのシンボルシーケンス間の編集距離(レーベンシュタイン距離とも呼ばれる)は通常、第１のシーケンスを第２のシーケンスに変形するのに必要とされる編集操作の最小数として定義される。ここで、許容可能な編集操作は、一度につき単一のシンボルの挿入、削除、又は置換である。シンボルは、ほんの数例を挙げれば、ビット、文字、数字、グリフ、ＤＮＡヌクレオチド、ＯＣＲ文字、又は指紋特徴点マップであり得る。
【０００３】
編集距離は、多数の生物情報学及びデータマイニングの用途において重要な基準である。さらに、２つの入力シーケンスに共通の最長のサブシーケンスの長さが編集距離に関係付けられる。たとえば、２つの入力文字列、「ＪＡＮＵＡＲＹ」及び「ＦＥＢＲＵＡＲＹ」における最長の共通サブシーケンスは「ＵＡＲＹ」である。
【０００４】
編集距離、及び最長の共通サブシーケンスの長さは共に、たとえばワグナー−フィッシャー(Wagner-Fischer)法又はニードルマン−ウンシュ(Needleman-Wunsch)法を使用する動的計画法を介して求めることができる。シンボルシーケンスの長さがそれぞれｎ及びｍである場合、動的計画法による解法はサイズｎ×ｍの行列のエントリを求めることを伴う。
【０００５】
図１は、２つの入力文字列、すなわち長さｍのｓ及び長さｎのｔをとり、これらの２つの文字列間の編集距離を計算する関数ＥｄｉｔＤｉｓｔａｎｃｅのための擬似コードを示している。
【０００６】
図２は、２つの文字列「ＦＡＳＴ」２３０及び「ＦＩＲＳＴ」２４０のための、動的計画法による解法によって使用される行列２１０を示している。行列の要素は、以前に求められた要素の値に基づいて再帰的に求められる。終了時に、行列の右下の要素が編集距離２２０を提供する。
【０００７】
しかしながら、動的計画法による解法はプライバシーを提供しない。２つのプロセッサが動的計画法による解法を使用してシーケンス間の編集距離を得る場合、各プロセッサは、各文字列からの全てのシンボルを知ることになる。用途によっては、シーケンスからのシンボルを明らかにすることなく編集距離を求めることが必要である。
【０００８】
プライバシーを必要とする用途の一例では、第１のプロセッサは、たとえばスミス・ウォーターマン(Smith-Waterman)アルゴリズムを使用して遺伝性疾患に対する罹患性を検査されるＤＮＡシーケンスを有する患者に関する情報を格納する。第２のプロセッサは、これらの疾患に対応するシーケンスのデータベースを有する。患者のプライバシーを保護するために、患者情報は第２のプロセッサに公開されない。同様に、データベース内のシーケンスを分離するには、かなりの調査、時間、及び投資が必要となった場合があるため、第２のプロセッサは、事業を守るために、データベースを公開することを所望しない。それにもかかわらず、第２のプロセッサ及び第１のプロセッサは、患者のＤＮＡシーケンスとデータベース内に格納されているＤＮＡシーケンスとの間の編集距離を求めて、患者のＤＮＡシーケンスが、第２のプロセッサのデータベース内の診断のためのＤＮＡシーケンスのうちのいずれかと概ね適合するか否かを判断する必要がある。法科学におけるＤＮＡプロファイリングは同様のプライバシー要件を有する。
【０００９】
プライバシー制約の下で編集距離を求めることは、セキュアな多者計算(secure multiparty computation)(ＳＭＣ)を使用することができる。ＳＭＣでは、２者の入力の任意の関数を代数回路として表すことができる限り、該２者は該関数をセキュアに計算することができる。しかしながら、２者計算問題の解は、出力及び入力が代数回路によって関係付けられており、非常に少数の入力シーケンスの場合であっても実施するのが複雑である。特に、これらの方法は、高い計算複雑度及び高い通信オーバーヘッドを有する紛失通信プロトコルに依存する。上述したＤＮＡ適合問題のような問題に対する実際的な解のために、扱いやすい計算複雑度を有すると共に、２者間の比較的少数の暗号化された送信を必要とするセキュアなプロトコルを考案することが必要である。
【００１０】
たとえば、１つの方法は、第３のセミオネストであるが信頼されるプロセッサを使用して編集距離をセキュアに求める。しかしながら、第３のプロセッサは常に利用可能であるとは限らない。さらに、第３のプロセッサは、プロセッサのうちの一方と結託し、それによって他方のプロセッサによって処理されるシーケンスを見つけ出す可能性がある。
【００１１】
別の方法は、２者対称プロトコルを開示する。すなわち、２つのプロセッサが、計算複雑度及び通信の観点において全く等しいプロトコルオーバーヘッドを受ける。プロトコルの終了時に、２つのプロセッサはそれぞれ、編集距離が取得される、上述したｍ×ｎの行列の加法シェア(additive share)を保有する。しかしながら、この方法はプロセッサ間で多数の暗号化された送信を必要とする。さらに、この方法は、非常に限られた種類の置換コストに対してしか効果的に機能しない。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
したがって、２つのシンボルシーケンス間で暗号化された編集距離をセキュアに求めるための計算効率のよい方法を見出す必要がある。
【００１３】
この発明の実施の形態は、数字の最小値の暗号化を準同型に暗号化された形式で求めるように構成される最小値発見方法を開示する。
【課題を解決するための手段】
【００１４】
この発明の１つの実施の形態は、暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるための方法を開示する。この方法は、行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として再帰的に求め、動的計画法による解を生成する。前記第１の要素は挿入コストを表し、前記第２の要素は削除コストを表し、前記第３の要素は置換コストを表し、前記現在の要素、前記第１の要素、前記第２の要素、及び前記第３の要素は、公開鍵を用いて準同型に暗号化される。この方法は、動的計画法による解を前記暗号化された編集距離として選択する。この方法のステップは、第１のプロセッサ及び第２のプロセッサによって実行され、前記第１のシーケンスが前記第１のプロセッサにのみ格納されると共に前記第２のプロセッサから秘密にされ、前記第２のシーケンスが前記第２のプロセッサにのみ格納されると共に前記第１のプロセッサから秘密にされるようにする。
【００１５】
この発明の別の実施の形態は、暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるように構成されるシステムであって、前記最小コストは行列の動的計画法による解であり、前記行列の要素は、以前に求められた要素の値に基づいて再帰的に求められる、システムを開示する。
【００１６】
このシステムは、第２のプロセッサとインタラクトして、前記行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として求めるように構成される第１のプロセッサであって、前記第１の要素は前記挿入コストを表し、前記第２の要素は前記削除コストを表し、前記第３の要素は前記置換コストを表し、前記現在の要素、前記第１の要素、前記第２の要素、及び前記第３の要素は、公開鍵を用いて準同型に暗号化されるものと、加法的準同型暗号化の特性に基づいて、前記第１の要素、前記第２の要素、及び前記第３の要素を求めるように構成される第２のプロセッサであって、前記第１のシーケンスは前記第１のプロセッサにのみ格納されると共に該第２のプロセッサから秘密にされ、前記第２のシーケンスは該第２のプロセッサにのみ格納されると共に前記第１のプロセッサから秘密にされるものと、前記動的計画法による解を再帰的に求める手段と、前記動的計画法による解を前記暗号化された編集距離として選択する手段とを備える。
【図面の簡単な説明】
【００１７】
【図１】２つの入力シンボルシーケンス、すなわち長さｍのｓ及び長さｎのｔをとり、これらの２つの入力シーケンス間の編集距離を計算する従来技術の関数ＥｄｉｔＤｉｓｔａｎｃｅの擬似コードである。
【図２】２つの文字列「ＦＡＳＴ」及び「ＦＩＲＳＴ」のための、動的計画法による解によって使用される行列２１０である。
【図３】この発明の実施の形態による、暗号化された編集距離をセキュアに求めるための方法の概略図である。
【図４】この発明の実施の形態による、暗号化された数字の集合において最小の数字の暗号化を求めるための方法のブロック図である。
【図５】この発明の実施の形態による、暗号化された数字の集合において最小の数字の暗号化を求めるための方法のブロック図である。
【図６】この発明の実施の形態による、置換コストを求めるための方法の擬似コードである。
【図７】この発明の実施の形態による、置換コストを求めるための方法の擬似コードである。
【発明を実施するための形態】
【００１８】
暗号化された編集距離
図３は、暗号化された編集距離３４５を、シンボルの第１のシーケンス３１５からシンボルの第２のシーケンス３２５への変形の最小コストの暗号化としてセキュアに求める方法３００の概略図を示している。変形のコストは、下記でより詳細に説明するように、挿入コスト３３２、削除コスト３３４、及び置換コスト３３６に基づいて求められる。この明細書において定義される場合、挿入コストはシンボルを第２のシーケンス内に挿入するコストであり、削除コストは第２のシーケンスからシンボルを削除するコストであり、置換コストは第２のシーケンスからのシンボルを第１のシーケンスからのシンボルに置換するコストである。
【００１９】
シーケンス３１５及び３２５内のシンボルは、たとえば、ビット、文字、数字、及びＤＮＡヌクレオチドであり得る。この発明の様々な実施の形態において、置換コスト、挿入コスト、及び削除コストは、定数であるか、又は置換、挿入、若しくは削除されるシンボルに依拠する。
【００２０】
方法３００のステップは第１のプロセッサ３１０及び第２のプロセッサ３２０によって実行され、第１のシーケンスが第１のプロセッサにのみ格納され、第２のシーケンスが第２のプロセッサにのみ格納されるようにされる。第１のプロセッサと第２のプロセッサとの間で送信される(３３０)データは、公開鍵３６０を用いて準同型に暗号化される。公開鍵は、第１のプロセッサ及び第２のプロセッサの双方に利用可能である。しかしながら、第１のプロセッサのみが秘密鍵３５０を有し、このため、第１のプロセッサのみがシンボルを復号することができる。
【００２１】
この発明の実施の形態は、変形の最小コストを、システム、すなわち行列３２６の動的計画法による解として定式化する。行列の暗号化された(ζ)要素は、以前に求められた要素の値に基づいて再帰的に求められる。
【００２２】
第１のシーケンス
【００２３】
【数１】
【００２４】
及び第２のシーケンス
【００２５】
【数２】
【００２６】
は、方法３００への入力である。シンボルｘｉ及びｙｊは、有限アルファベット集合Ａ(図示せず)に属する。便宜上、サブシーケンス
【００２７】
【数３】
【００２８】
は
【００２９】
【数４】
【００３０】
であり、ここで、インデックスａ、ｂは適切な制限内にあり、シンボルｙｋの挿入コストはＩ(ｙｋ)であり、シンボルｘｋの削除コストはＤ(ｘｋ)であり、シンボルｘｋをシンボルｙｉに置換する置換コストはＳ(ｘｋ，ｙｉ)であり、ここでｋ及びｉはシーケンス内のシンボルのインデックスである。
【００３１】
挿入コストＩ(ｙｋ)、削除コストＤ(ｘｋ)、及び置換コストＳ(ｘｋ，ｙｉ)は様々な実施の形態にわたって変動する。
【００３２】
Ｍ(ｉ，ｊ)がサブシーケンス
【００３３】
【数５】
【００３４】
をサブシーケンス
【００３５】
【数６】
【００３６】
に変形する最小コストである場合、１≦ｉ≦ｎ及び１≦ｊ≦ｍについて以下となる。
【００３７】
【数７】
【００３８】
上述したように、式(１)における行列の要素は再帰的に求められる。すなわち、Ｍ(ｉ，ｊ)は、Ｍ(ｉ−１，ｊ)、Ｍ(ｉ，ｊ−１)、及びＭ(ｉ−１，ｊ−１)を使用して計算される。さらに、編集距離Ｍ(ｎ，ｍ)は、第１のシーケンス
【００３９】
【数８】
【００４０】
を第２のシーケンス
【００４１】
【数９】
【００４２】
に変形する最小コストである。図３に示す例では、文字列「ＦＡＳＴ」及び「ＦＩＲＳＴ」間の編集距離３４０はＭ(４，５)＝２である。
【００４３】
方法３００は、第２のプロセッサにおける暗号化された領域内の行列の要素を求め、第２のプロセッサは、秘密鍵なしで要素の値を復号することができない。この発明の実施の形態は、意味論的にセキュアな(semantically secure：強秘匿性の)準同型暗号化の特性に基づいて、暗号化された数字の集合から最小の数字をセキュアに求めることが可能であるという認識に基づいている。
【００４４】
動的計画法による解３４５が暗号化された編集距離として選択される。暗号化された編集距離をメモリ(図示せず)内に格納しかつ／又は秘密鍵を用いた復号のために第１のプロセッサに送信することができる。
【００４５】
図５は、編集距離を求めることが、式(１)に従ってＭ(ｉ，ｊ)を計算することにまで低減されたものを示している。それぞれ第１のシーケンス及び第２のシーケンスの全てのｉ及びｊ(１≦ｉ≦ｎ、１≦ｊ≦ｍ)について、第１のプロセッサ及び第２のプロセッサは、最小値発見方法４００を使用して、行列の現在の要素４６０を、第１の要素５１０、第２の要素５２０、及び第３の要素５３０の最小値の暗号化として求める。ここで、第１の要素は挿入コスト３３２を表し、第２の要素は削除コスト３３４を表し、第３の要素は置換コスト３３６を表し、現在の要素、第１の要素、第２の要素、及び第３の要素は、公開鍵３６０を用いて準同型に暗号化される(５４０)。現在の要素Ｍ(ｉ，ｊ)の暗号化された値は、
ξ(ｍｉｎ{Ｍ(ｉ−１，ｊ−１)＋Ｓ(ｘｉ，ｙｊ)，Ｍ(ｉ−１，ｊ)＋Ｄ(ｘｉ)，Ｍ(ｉ，ｊ−１)＋Ｉ(ｙｊ)})＝ξ(Ｍ(ｉ，ｊ))
に従って求められる。
【００４６】
値Ｍ(ｉ−１，ｊ−１)３４４、Ｍ(ｉ，ｊ−１)３４６、及びＭ(ｉ−１，ｊ)３４２は、方法３００の以前の反復によって求められる。挿入コストＩ(ｙｊ)の暗号化、すなわちξ(Ｉ(ｙｊ))は、第１のプロセッサから第２のプロセッサに送信される。削除コストＤ(ｘｉ)及びしたがって暗号化ξ(Ｄ(ｘｉ))は第２のプロセッサに利用可能である。置換コストＳ(ｘｉ，ｙｊ)の暗号化、すなわちξ(Ｓ(ｘｉ，ｙｊ))は、下記で説明するように動的に提供されるか又は求められる。
【００４７】
挿入コストを表す第１の要素は、加法的準同型暗号化の特性に基づいて
ξ(Ｉ(ｙｊ))ξ(Ｍ(ｉ，ｊ−１))＝ξ(Ｉ(ｙｊ)＋Ｍ(ｉ，ｊ−１))
に従って求められる。
【００４８】
削除コストを表す第２の要素は、加法的準同型暗号化の特性に基づいて
ξ(Ｄ(ｘｉ))ξ(Ｍ(ｉ−１，ｊ))＝ξ(Ｄ(ｘｉ)＋Ｍ(ｉ−１，ｊ))
に従って求められる。
【００４９】
置換コストを表す第３の要素は、加法的準同型暗号化の特性に基づいて
ξ(Ｓ(ｘｉ，ｙｊ))ξ(Ｍ(ｉ−１，ｊ−１))＝ξ(Ｓ(ｘｉ，ｙｊ)＋Ｍ(ｉ−１，ｊ−１))
に従って求められる。
【００５０】
次に、最小値発見方法は、第１の要素、第２の要素、及び第３の要素を入力として受け取り(５５０)、現在の要素を最小値の暗号化された値として求める。実施の形態では、現在の要素、第１の要素、第２の要素、及び第３の要素は公開鍵を用いて準同型に暗号化される。
【００５１】
いくつかの実施の形態では、初期要素Ｍ(１，１)のための置換コストの表現、すなわちＭ(０，０)＋Ｓ(ｘ１，ｙ１)は、全ての可能なｘ１，ｙ１について双方の要素Ｍ(０，１)及びＭ(１，０)以下である。さらに、挿入コスト及び削除コストは全てのシンボルについて等しく、双方のプロセッサに知られている。１つのそのような一般的に発生する例が図２及び図３に示されている。それらの図においてＭ(０，０)＝０、Ｓ(ｘ１，ｙ１)＝１である。この実施の形態において、任意のシンボルのための挿入コスト及び削除コストは１であり、このため双方のプロセッサがＭ(０，１)＝Ｍ(１，０)＝１であることを知っている。したがって、要素Ｍ(１，１)の暗号化は最小値発見方法を使用して求められない。
【００５２】
この実施の形態では、第２のプロセッサは、適切な置換コストを使用して、ξ(Ｍ(１，１))＝ξ(Ｓ(ｘ１，ｙ１))に従って初期の暗号化された要素を求める。様々な実施の形態において、置換コストの暗号化は、所定であるか又は下記で説明するように動的に計算される。
【００５３】
行列Ｍ内の各要素の暗号化を再帰的に求めた後、１つの実施の形態において、第２のプロセッサは、暗号化された編集距離ξ(Ｍ(ｎ，ｍ))の値を第１のプロセッサに送信する。第１のプロセッサはこの値を復号し、２つのシーケンス
【００５４】
【数１０】
【００５５】
及び
【００５６】
【数１１】
【００５７】
間の編集距離を取得する。１つの実施の形態では、第１のプロセッサは編集距離の値を第２のプロセッサに返送する。このため、編集距離はプライバシーを侵害することなく求められる。すなわち、第１の信号は第１のプロセッサにのみ知られ、第２の信号は第２のプロセッサにのみ知られる。
【００５８】
準同型暗号化
Ｐを二項演算子
【００５９】
【数１２】
【００６０】
に関連付けられる平文の集合とし、Ｈを二項演算子
【００６１】
【数１３】
【００６２】
に関連付けられる暗号文の集合とする。
【００６３】
定義１
全てのａ，ｂ∈Ｐについて以下が成り立つ場合、マッピングξ：Ｐ→Ｈは準同型である。
【００６４】
【数１４】
【００６５】
実施の形態は準同型暗号システムを使用する。準同型暗号システムにおいて、演算子
【００６６】
【数１５】
【００６７】
は加法演算子であり、演算子
【００６８】
【数１６】
【００６９】
は乗法演算子である。そのような暗号システムは、加法性準同型の、たとえばベナロー(Benaloh)暗号システム及びパイエ(Paillier)暗号システムと呼ばれることがある。これらの双方の暗号システムは意味論的にセキュアである。すなわち、同じ平文の反復暗号化の結果、異なる暗号文が生じる。この発明の実施の形態は、様々な意味論的にセキュアな加法性準同型暗号システムを使用する。例として、パイエ暗号システムを以下に簡潔に要約する。
【００７０】
構成：２つの大きな素数ｐ、ｑを選択し、Ｎ＝ｐｑとする。
【００７１】
【数１７】
【００７２】
によって、Ｎ２を法とする逆数を有する非負整数の集合を表す。ｇｃｄ(Ｌ(ｇλ ｍｏｄ Ｎ２)，Ｎ)＝１となるように
【００７３】
【数１８】
【００７４】
を選択する。ここで、λ＝ｌｃｍ(ｐ−１，ｑ−１)及び
【００７５】
【数１９】
【００７６】
である。(Ｎ，ｇ)を公開鍵とし、(ｐ，ｑ)を秘密鍵とする。
【００７７】
暗号化：
【００７８】
【数２０】
【００７９】
を平文とする。次いで、暗号文が以下によって与えられる。
ξｒ(ｍ)＝ｇｍ・ｒＮ ｍｏｄ Ｎ２ (２)
ここで、
【００８０】
【数２１】
【００８１】
はランダムに選択される数字である。
【００８２】
復号：
【００８３】
【数２２】
【００８４】
を暗号文とする。次いで、以下に従って対応する平文が求められる。
【００８５】
【数２３】
【００８６】
復号は暗号化の間に使用される数字ｒの値に関わらず機能する。数字ｒは全ての暗号化ごとにランダムで選択することができるため、パイエ暗号システムは確率的であり、したがって意味論的にセキュアであり、すなわち
【００８７】
【数２４】
【００８８】
である。
【００８９】
また、式(２)に従った、平文集合(ＺＮ，＋)から暗号文集合
【００９０】
【数２５】
【００９１】
へのマッピングの特性は、以下の関係を満たす。
【００９２】
【数２６】
【００９３】
【数２７】
【００９４】
ここで、ｍ１及びｍ２は任意の２つの整数メッセージであり、上記で説明した暗号システムを使用して暗号化される。上記の下付き文字ｒ１、ｒは、式(２)におけるパラメーター「ｒ」を表し、式(２)における「ｒ」の異なる値によって結果として異なる暗号文が生じるように、暗号化時に選択される。「ｒ」の値を暗号化ごとに変更することによって、パイエ暗号化は意味論的セキュリティを達成する。この明細書において、意味論的セキュリティの概念に関連しない場合、下付き文字「ｒ」は表記を簡単にするために省かれる。
【００９５】
この発明のいくつかの実施の形態はパイエ暗号化を使用する。しかしながら、他の実施の形態は他の意味論的にセキュアな加法性準同型方式を使用する。
【００９６】
最小値発見方法
図４は、この発明の実施の形態による、暗号化された数字の集合における最小の数字の暗号化を求めるための方法４００のブロック図である。方法４００は、この発明の実施の形態によって、行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として求めるのに使用される。
【００９７】
たとえば、第２のプロセッサ３２０は、準同型に暗号化された形式の数字の集合
【００９８】
【数２８】
【００９９】
たとえば、Ｌ個の数字ａ１，ａ２，…，ａＬの
【０１００】
【数２９】
【０１０１】
４１０を格納する。最小値発見方法によって、第２のプロセッサが、これらの数字の最小値の暗号化を求める、すなわち、或る係数
【０１０２】
【数３０】
【０１０３】
について、ξｒ(ｍｉｎｉ{ａｉ})４６０を求めることが可能になる。方法４００は、第２のプロセッサが、ａｉ又は最小値のインデックス若しくは値に関するいかなる情報も見つけ出すことを可能にしない。
【０１０４】
同様に、第１のプロセッサは数字ａ１，ａ２，…，ａＬに関するいかなる情報も見つけ出さない。この方法のステップは以下の通りである：
【０１０５】
１． 第２のプロセッサが、正の整数μ及びα４５０をランダムに選択する。すなわちμはスケーリング定数であり、αはランダムに選択される整数シフトである。パイエ暗号システムの場合、μを後に除去することができることを確実にするために、第２のプロセッサはμを集合
【０１０６】
【数３１】
【０１０７】
からランダムに選択する。次いで、第２のプロセッサは公開鍵３６０を使用して暗号化
【０１０８】
【数３２】
【０１０９】
４５１を取得し、ｉ＝１，２，…，Ｌについて暗号化された和
【０１１０】
【数３３】
【０１１１】
４２０を求めて暗号化された和の集合４２０を生成し、該暗号化された和の集合を第１のプロセッサに送信する(４２５)。パイエ暗号システムの場合、暗号化係数ｒ’ｉ＝ｒｉｒ０であり、第２のプロセッサは暗号化係数ｒｉを知ることなく暗号化係数ｒ’ｉを求めることができない。
【０１１２】
２． 第１のプロセッサが秘密鍵３５０を用いて数字を復号し、ｍｉｎｉ{μａｉ}＋α ４３０によって与えられる最小値を求め、次いで、その結果を公開鍵を用いて暗号化して暗号化された最小値
【０１１３】
【数３４】
【０１１４】
４６０を生成し、該暗号化された最小値を第２のプロセッサに返送する(４６５)。
【０１１５】
３． 第２のプロセッサが
【０１１６】
【数３５】
【０１１７】
４５２を計算し、
【０１１８】
【数３６】
【０１１９】
４７０を求める。
【０１２０】
非常に高い確率で、ξｒ(ｍｉｎｉ{μａｉ})が、暗号化
【０１２１】
【数３７】
【０１２２】
のうちのいずれとも等しくないことに留意されたい。これは、第１のプロセッサが、第２のプロセッサに知られていないランダムな暗号化係数ｒＢを選択し、これによって暗号化が意味論的にセキュアになるためである。これによって、第２のプロセッサが最小値の暗号化を取得するとき、元のシーケンス
【０１２３】
【数３８】
【０１２４】
における最小値のインデックスが第２のプロセッサから隠されたままであることが確実になる。
【０１２５】
４． 第２のプロセッサは、
(ξ(ｍｉｎｉ{μａｉ}))１／μ＝(ξｒ(μｍｉｎｉ{ａｉ}))１／μ＝ξｒ(ｍｉｎｉ{ａｉ})
に従って、いずれが暗号化された最小値４６０であるのかを確定する(４８０)。
【０１２６】
正の整数μ及びαを使用することによって、第１のプロセッサが数字αｉのいかなる情報を見つけ出すことも阻止されることに留意されたい。さらに、意味論的セキュリティに起因して、第２のプロセッサは最小値のインデックス「ｉ」を見つけ出すことができない。最後に、第２のプロセッサは、復号鍵を有しないため、最小値の実際の値を求めることができない。
【０１２７】
編集距離を求めるために、３つの値、すなわち上記のＬ＝３を用いて最小値発見方法が実行される。１つの実施の形態では、各シンボルが正の挿入コスト及び削除コスト、並びに非負の置換コストを有する。
【０１２８】
他の実施の形態では、いくつかのシンボルは負若しくはゼロの挿入コスト及び／又は負若しくはゼロの削除コストを有する。付加的に又は代替的に、挿入コスト、削除コスト、及び置換コストに対応する３つのエントリ全てを等しくすることができる。そのような場合、第１のプロセッサが変数μ及びαの値を求めることができない場合であっても、第１のプロセッサは各シンボルの挿入コストに基づいて、最小値を求めることができる。
【０１２９】
そのような実施の形態では、第２のプロセッサは、ベクトル
【０１３０】
【数３９】
【０１３１】
に２つ以上の「ダミー」変数を付加する。すなわち、Ｌ＞３である。最小値発見方法の各反復において、第１のプロセッサがダミー変数に関するいかなる情報を取得することも阻止するために、異なるダミー変数及び／又は異なる数のダミー変数が使用される。次いで、第１のプロセッサは、上記のステップ２のように復号し最小値を求めた後で、１つ又は複数の暗号化された値を求めて該値を第２のプロセッサに送信する。
【０１３２】
たとえば、いくつかの実施の形態では、第２のプロセッサはベクトル
【０１３３】
【数４０】
【０１３４】
にダミーの変数ξ(Ａ)及びξ(Ｂ)を付加する。ここで、ａｉの全ての値と比較して、変数Ａは大きい数であり、変数Ｂは小さい数である。次いで、第２のプロセッサは、第１のプロセッサからの２つの最も小さい値の暗号化を要求する。その際いずれの値が最も小さく、いずれの値が２番目に小さいかが特定される。
【０１３５】
第１のプロセッサは最も小さい値が変数Ｂに対応することを知っているため、第２のプロセッサは、第１のプロセッサから受信した最小値のインデックスに対応する暗号化された要素を除外し、真の最小値の暗号化された値として２番目に小さい値の暗号化を選択する。
【０１３６】
いくつかの実施の形態では、共通の定数αを有する代わりに、第２のプロセッサは２の累乗としてμを使用し、全てのｉ＝１，２，…，Ｌについてαｉ＜μとなるように様々な等しくない定数α１、α２，…，αＬを選択する。第２のプロセッサは、上記のステップ１のように暗号化ξ(μａｉ＋αｉ)を第１のプロセッサに送信する。次いで、第１のプロセッサは、ステップ２と同様に、暗号化を復号し、最小値ｍｉｎｉ μａｉ＋αｉを求める。しかしながら、第１のプロセッサは、最小値の暗号化を返送する代わりに、最小値をバイナリに変換し、各ビットを暗号化し、該暗号化されたビットを第２のプロセッサに送信する。第２のプロセッサがα１、α２，…，αＬの値を選択したため、第２のプロセッサはαｉに対してどれだけ多くのビットが利用されたかを正確に知り、μによってスケーリングされた所望の最小値に対して残りのビットが利用されたことを知っている。全てのｉ＝１，２，…，Ｌについてαｉ＜μであるため、これらのビット間に重複が存在しないことに留意されたい。このため、準同型暗号化の特性を使用して、第２のプロセッサはμによってスケーリングされた最小値に対応するビットを取得する。次いで、第２のプロセッサは上記のステップ４に従ってμによって乗算を反転させる(reverse the multiplication)。第１のプロセッサは、ａｉの値のうちの１つ又は複数が等しい場合であっても、最小値の値を知ることを阻止される。
【０１３７】
置換コストを求める
この発明の実施の形態は、行列の現在の要素を、挿入コスト、削除コスト、及び置換コストを表す要素の最小値の暗号化として求める。異なる実施の形態では、挿入コスト、削除コスト、及び置換コストは所定であるか、動的に求められるか、又はそれらの組み合わせが使用される。
【０１３８】
たとえば、１つの実施の形態では、挿入コスト、削除コスト、及び置換コストは所定である。これらの実施の形態の１つの変形形態では、全てのコストは整数値である。別の実施の形態では、挿入コスト及び削除コストは所定であるが、置換コストは動的に求められる。この実施の形態の１つの変形形態では置換コストは置換されるシンボルの値に基づいて求められる。
【０１３９】
定数の置換コスト
１つの実施の形態では、置換コストは、第１のシーケンス及び第２のシーケンスが異なる場合に或る定数であり、シンボルが同一である場合にゼロである。この実施の形態の１つの変形形態は、アルファベットのシンボルを整数集合{１，２，３，…，Ｑ}にマッピングする。ここでＱはアルファベット集合のサイズである。たとえば、シンボルＡ、Ｔ、Ｃ、Ｇを有するＤＮＡシーケンスの場合、サイズＱ＝４である。この実施の形態における置換コストは、ａ＝ｂの場合にＳ(ａ，ｂ)＝０であり、ａ≠ｂの場合にＳ(ａ，ｂ)である。ここでａは第１のシーケンスのシンボルであり、ｂは第２のシーケンスのシンボルである。
【０１４０】
図６は、以下のステップに従って定数の置換コストを求めるための方法の擬似コードを示している。
１．第１のプロセッサが第１の文字列のシンボル「ａ」を、最初の「ａ」個のビットが１に等しく、最後のＱ−ａ個のビットが０に等しい長さＱの第１のバイナリシーケンスに変換する。第１のバイナリ文字列からの文字列はａｉとして定義される。ここでｉは１からＱの範囲をとる。同様に、第２のプロセッサが第２のシーケンスのシンボル「ｂ」を、最初の「ｂ」個のビットが１に等しく、最後のＱ−ｂ個のビットが０に等しい長さＱの第２のバイナリシーケンスに変換する。
２．第１のプロセッサが、第１のバイナリシーケンス内の各ビットの暗号化を第２のプロセッサに送信する。
３．第２のプロセッサが、第２のバイナリ列からの第１のビット及び第２のビット、並びに第１のバイナリシーケンスからの第１の暗号化されたビット及び第２の暗号化されたビットから、
ξ(Ｕ１)＝ξ(ａ１ｂ１−ａ２ｂ１)＝ξ(ａ１ｂ２)ξ(−ａ２ｂ１)＝［ξ(ｂ２)のａ１乗］＊［ξ(ｂ１)の(−ａ２)乗］
に従って２×２の行列式を計算する。
４．第２のプロセッサが双方のバイナリシーケンスからの第２のビット及び第３のビットに対して、次いで第３のビット及び第４のビットに対して、そして以下同様に、長さＱのシーケンス全体が使い果たされるまで以前のステップを反復する。このようにして、第２のプロセッサは暗号化された２×２の行列式ξ(Ｕ１)，ξ(Ｕ２)，…，ξ(ＵＱ−１)を求める。
５．第２のプロセッサは行列式ξ(Ｕ)の和をΠｉξ(Ｕｉ)＝ξ(ΣｉＵｉ)として計算する。ここでｉは１からＱ−１で変動する。これは加法的準同型暗号化の特性を使用する。
６．第２のプロセッサは数字ｄをランダムに選択し、ξ(Ｕ＋ｄ)＝ξ(Ｕ)ξ(ｄ)を計算し、結果を第１のプロセッサに送信する。
７．第１のプロセッサは２つの数字を暗号化し、積(Ｕ＋ｄ)２＝Ｕ’を求め、積Ｕ’を暗号化してξ(Ｕ’)を第２のプロセッサに返送する。
８．第２のプロッセッサーがξ(Ｕ’)ξ(−２ｄＵ)ξ(−ｄ２)＝ξ(Ｕ’−２ｄＵ−ｄ２)＝ξ(Ｕ２)を計算する。
【０１４１】
構築によって、Ｕ＝０、１、又は−１である。したがって、Ｕ２は、シンボル「ａ」及び「ｂ」が同じであるか又は異なっているかにそれぞれ依拠して、０又は１である。このため、ξ(Ｕ２)は置換コストの暗号化された値を提供する。第２のプロセッサは、実際の時間コストではなく暗号化された置換コストしか取得しない。これは、第２のプロセッサが復号鍵を有しないためである。第１のプロセッサは数字「ｄ」を知らないことに起因して何も知らない。
【０１４２】
絶対距離置換コスト
別の実施の形態では、置換コストは第１のシーケンスのシンボルと第２のシーケンスのシンボルとの間の絶対距離であり、すなわち、シンボルがそれぞれ「ａ」及び「ｂ」である場合、置換コストＳ(ａ，ｂ)＝｜ａ−ｂ｜である。上述の実施の形態と同様に、アルファベットにおけるシンボルは整数集合{１，２，３，…，Ｑ}にマッピングされる。最小化プロトコルによれば、第１のプロセッサは置換コストの暗号化を求めることができる。第２のプロセッサは求めることができない。
【０１４３】
図７は、以下のステップに従って絶対距離置換コストを求めるための方法の擬似コードを示している。
１．第１のプロセッサが第１のシーケンスのシンボル「ａ」を、最初の「ａ」個のビットが１に等しく、最後のＱ−ａ個のビットが０に等しい長さＱの第１のバイナリシーケンスに変換する。第１のバイナリ文字列からの文字列はａｉとして定義される。ここでｉは１からＱの範囲をとる。同様に、第２のプロセッサが第２のシーケンスのシンボル「ｂ」を、最初の「ｂ」個のビットが１に等しく、最後のＱ−ｂ個のビットが０に等しい長さＱの第２のバイナリシーケンスに変換する。
２．第１のプロセッサが、バイナリシーケンス内の各ビットの暗号化を第２のプロセッサに送信する。
３．第２のプロセッサが、加法的準同型暗号化の特性に基づいて以下の式に従って置換コストの暗号化ξ(Ｓ(ａ，ｂ))を求める。
４．
【０１４４】
【数４１】
【０１４５】
多項式関数置換コスト
別の実施の形態では、参照によりこの明細書に援用される米国特許出願第１２／４９５，７２１号に記載されているように、置換コストは２つのシーケンスのシンボルに多項式関数を適用した結果である。たとえば、第２のプロセッサは整数ａを格納し、第１のプロセッサは整数ｂを格納する。実施の形態は、第２のプロセッサにおいて、暗号化された形式の置換コスト
【０１４６】
【数４２】
【０１４７】
を求める。
【０１４８】
置換コストＳ(ａ，ｂ)＝(ａ−ｂ)Ｓはｂにおける次数Ｓの多項式であり、すなわち０≦ｊ≦Ｓである。このため、第２のプロセッサは、或る暗号化係数
【０１４９】
【数４３】
【０１５０】
について置換コストξ(Σｉ，ｊｃｉｊａｉｂｊ)を求める。第２のプロセッサは、秘密鍵を保有していないため、置換コストを復号することができない。第１のプロセッサは整数ｂの値しか知らない。ステップは以下の通りである：
１．０≦ｊ≦Ｓについて、第１のプロセッサがｂｊを暗号化し、
【０１５１】
【数４４】
【０１５２】
を第２のプロセッサに送信する。
２．第２のプロセッサがｃｉ，ｊ及びａの値に基づいて
【０１５３】
【数４５】
【０１５４】
を求める。
【０１５５】
この方法は、紛失通信に基づく方法と比較して、多項式評価法に関して大幅に低い計算及び通信のオーバーヘッドを受ける。紛失通信に基づく方法は非常に単純な多項式の場合であっても極度に複雑となり、大きな送信オーバーヘッドを受ける。
【０１５６】
最も長い共通サブシーケンス
この発明の１つの実施の形態は、第１のシーケンスと第２のシーケンスとの間の最も長い共通サブシーケンスの長さを求める。この実施の形態は、多くの点において編集距離を求めるための実施の形態に類似している。主な違いは２つしかない。
【０１５７】
第１に、方法の各ステップにおいて３つの要素の最小値を計算する代わりに、この実施の形態は３つの要素の最大値を求める。たとえば、数値の場合、２つのプロセッサは全ての値の符号を逆にし、上述した最小値発見方法を使用する。
【０１５８】
第２に、セッサがｍｎ個の暗号化された要素を用いて１つ又は複数の最大値発見プロトコルを実行して、所望の結果を取得することを意味する。所望の結果は、最も長い共通サブシーケン編集距離を行列の最後の要素Ｍ(ｎ，ｍ)として選択する代わりに、行列全体を検索して該行列内の最大の要素を発見する。最大の要素の暗号化は、行列Ｍ内の各要素の符号を逆にし、上述した最小化プロトコルを適用することによって発見することができる。次いで、取得した結果が第１のプロセッサに送信され、第１のプロセッサは、該結果を復号して最大の要素を取得する。最大の要素は最も長い共通サブシーケンスの長さを与える。これは、行列全体を計算した後、２つのプロスの長さの暗号化である。
【０１５９】
この発明を好ましい実施の形態の例として説明してきたが、この発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、この発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【技術分野】
【０００１】
この発明は、包括的には２つのシンボルシーケンス間の編集距離を求めることに関し、より詳細には、２つのシンボルシーケンス間の暗号化された編集距離をセキュアに求めることに関する。
【背景技術】
【０００２】
２つのシンボルシーケンス間の編集距離(レーベンシュタイン距離とも呼ばれる)は通常、第１のシーケンスを第２のシーケンスに変形するのに必要とされる編集操作の最小数として定義される。ここで、許容可能な編集操作は、一度につき単一のシンボルの挿入、削除、又は置換である。シンボルは、ほんの数例を挙げれば、ビット、文字、数字、グリフ、ＤＮＡヌクレオチド、ＯＣＲ文字、又は指紋特徴点マップであり得る。
【０００３】
編集距離は、多数の生物情報学及びデータマイニングの用途において重要な基準である。さらに、２つの入力シーケンスに共通の最長のサブシーケンスの長さが編集距離に関係付けられる。たとえば、２つの入力文字列、「ＪＡＮＵＡＲＹ」及び「ＦＥＢＲＵＡＲＹ」における最長の共通サブシーケンスは「ＵＡＲＹ」である。
【０００４】
編集距離、及び最長の共通サブシーケンスの長さは共に、たとえばワグナー−フィッシャー(Wagner-Fischer)法又はニードルマン−ウンシュ(Needleman-Wunsch)法を使用する動的計画法を介して求めることができる。シンボルシーケンスの長さがそれぞれｎ及びｍである場合、動的計画法による解法はサイズｎ×ｍの行列のエントリを求めることを伴う。
【０００５】
図１は、２つの入力文字列、すなわち長さｍのｓ及び長さｎのｔをとり、これらの２つの文字列間の編集距離を計算する関数ＥｄｉｔＤｉｓｔａｎｃｅのための擬似コードを示している。
【０００６】
図２は、２つの文字列「ＦＡＳＴ」２３０及び「ＦＩＲＳＴ」２４０のための、動的計画法による解法によって使用される行列２１０を示している。行列の要素は、以前に求められた要素の値に基づいて再帰的に求められる。終了時に、行列の右下の要素が編集距離２２０を提供する。
【０００７】
しかしながら、動的計画法による解法はプライバシーを提供しない。２つのプロセッサが動的計画法による解法を使用してシーケンス間の編集距離を得る場合、各プロセッサは、各文字列からの全てのシンボルを知ることになる。用途によっては、シーケンスからのシンボルを明らかにすることなく編集距離を求めることが必要である。
【０００８】
プライバシーを必要とする用途の一例では、第１のプロセッサは、たとえばスミス・ウォーターマン(Smith-Waterman)アルゴリズムを使用して遺伝性疾患に対する罹患性を検査されるＤＮＡシーケンスを有する患者に関する情報を格納する。第２のプロセッサは、これらの疾患に対応するシーケンスのデータベースを有する。患者のプライバシーを保護するために、患者情報は第２のプロセッサに公開されない。同様に、データベース内のシーケンスを分離するには、かなりの調査、時間、及び投資が必要となった場合があるため、第２のプロセッサは、事業を守るために、データベースを公開することを所望しない。それにもかかわらず、第２のプロセッサ及び第１のプロセッサは、患者のＤＮＡシーケンスとデータベース内に格納されているＤＮＡシーケンスとの間の編集距離を求めて、患者のＤＮＡシーケンスが、第２のプロセッサのデータベース内の診断のためのＤＮＡシーケンスのうちのいずれかと概ね適合するか否かを判断する必要がある。法科学におけるＤＮＡプロファイリングは同様のプライバシー要件を有する。
【０００９】
プライバシー制約の下で編集距離を求めることは、セキュアな多者計算(secure multiparty computation)(ＳＭＣ)を使用することができる。ＳＭＣでは、２者の入力の任意の関数を代数回路として表すことができる限り、該２者は該関数をセキュアに計算することができる。しかしながら、２者計算問題の解は、出力及び入力が代数回路によって関係付けられており、非常に少数の入力シーケンスの場合であっても実施するのが複雑である。特に、これらの方法は、高い計算複雑度及び高い通信オーバーヘッドを有する紛失通信プロトコルに依存する。上述したＤＮＡ適合問題のような問題に対する実際的な解のために、扱いやすい計算複雑度を有すると共に、２者間の比較的少数の暗号化された送信を必要とするセキュアなプロトコルを考案することが必要である。
【００１０】
たとえば、１つの方法は、第３のセミオネストであるが信頼されるプロセッサを使用して編集距離をセキュアに求める。しかしながら、第３のプロセッサは常に利用可能であるとは限らない。さらに、第３のプロセッサは、プロセッサのうちの一方と結託し、それによって他方のプロセッサによって処理されるシーケンスを見つけ出す可能性がある。
【００１１】
別の方法は、２者対称プロトコルを開示する。すなわち、２つのプロセッサが、計算複雑度及び通信の観点において全く等しいプロトコルオーバーヘッドを受ける。プロトコルの終了時に、２つのプロセッサはそれぞれ、編集距離が取得される、上述したｍ×ｎの行列の加法シェア(additive share)を保有する。しかしながら、この方法はプロセッサ間で多数の暗号化された送信を必要とする。さらに、この方法は、非常に限られた種類の置換コストに対してしか効果的に機能しない。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
したがって、２つのシンボルシーケンス間で暗号化された編集距離をセキュアに求めるための計算効率のよい方法を見出す必要がある。
【００１３】
この発明の実施の形態は、数字の最小値の暗号化を準同型に暗号化された形式で求めるように構成される最小値発見方法を開示する。
【課題を解決するための手段】
【００１４】
この発明の１つの実施の形態は、暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるための方法を開示する。この方法は、行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として再帰的に求め、動的計画法による解を生成する。前記第１の要素は挿入コストを表し、前記第２の要素は削除コストを表し、前記第３の要素は置換コストを表し、前記現在の要素、前記第１の要素、前記第２の要素、及び前記第３の要素は、公開鍵を用いて準同型に暗号化される。この方法は、動的計画法による解を前記暗号化された編集距離として選択する。この方法のステップは、第１のプロセッサ及び第２のプロセッサによって実行され、前記第１のシーケンスが前記第１のプロセッサにのみ格納されると共に前記第２のプロセッサから秘密にされ、前記第２のシーケンスが前記第２のプロセッサにのみ格納されると共に前記第１のプロセッサから秘密にされるようにする。
【００１５】
この発明の別の実施の形態は、暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるように構成されるシステムであって、前記最小コストは行列の動的計画法による解であり、前記行列の要素は、以前に求められた要素の値に基づいて再帰的に求められる、システムを開示する。
【００１６】
このシステムは、第２のプロセッサとインタラクトして、前記行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として求めるように構成される第１のプロセッサであって、前記第１の要素は前記挿入コストを表し、前記第２の要素は前記削除コストを表し、前記第３の要素は前記置換コストを表し、前記現在の要素、前記第１の要素、前記第２の要素、及び前記第３の要素は、公開鍵を用いて準同型に暗号化されるものと、加法的準同型暗号化の特性に基づいて、前記第１の要素、前記第２の要素、及び前記第３の要素を求めるように構成される第２のプロセッサであって、前記第１のシーケンスは前記第１のプロセッサにのみ格納されると共に該第２のプロセッサから秘密にされ、前記第２のシーケンスは該第２のプロセッサにのみ格納されると共に前記第１のプロセッサから秘密にされるものと、前記動的計画法による解を再帰的に求める手段と、前記動的計画法による解を前記暗号化された編集距離として選択する手段とを備える。
【図面の簡単な説明】
【００１７】
【図１】２つの入力シンボルシーケンス、すなわち長さｍのｓ及び長さｎのｔをとり、これらの２つの入力シーケンス間の編集距離を計算する従来技術の関数ＥｄｉｔＤｉｓｔａｎｃｅの擬似コードである。
【図２】２つの文字列「ＦＡＳＴ」及び「ＦＩＲＳＴ」のための、動的計画法による解によって使用される行列２１０である。
【図３】この発明の実施の形態による、暗号化された編集距離をセキュアに求めるための方法の概略図である。
【図４】この発明の実施の形態による、暗号化された数字の集合において最小の数字の暗号化を求めるための方法のブロック図である。
【図５】この発明の実施の形態による、暗号化された数字の集合において最小の数字の暗号化を求めるための方法のブロック図である。
【図６】この発明の実施の形態による、置換コストを求めるための方法の擬似コードである。
【図７】この発明の実施の形態による、置換コストを求めるための方法の擬似コードである。
【発明を実施するための形態】
【００１８】
暗号化された編集距離
図３は、暗号化された編集距離３４５を、シンボルの第１のシーケンス３１５からシンボルの第２のシーケンス３２５への変形の最小コストの暗号化としてセキュアに求める方法３００の概略図を示している。変形のコストは、下記でより詳細に説明するように、挿入コスト３３２、削除コスト３３４、及び置換コスト３３６に基づいて求められる。この明細書において定義される場合、挿入コストはシンボルを第２のシーケンス内に挿入するコストであり、削除コストは第２のシーケンスからシンボルを削除するコストであり、置換コストは第２のシーケンスからのシンボルを第１のシーケンスからのシンボルに置換するコストである。
【００１９】
シーケンス３１５及び３２５内のシンボルは、たとえば、ビット、文字、数字、及びＤＮＡヌクレオチドであり得る。この発明の様々な実施の形態において、置換コスト、挿入コスト、及び削除コストは、定数であるか、又は置換、挿入、若しくは削除されるシンボルに依拠する。
【００２０】
方法３００のステップは第１のプロセッサ３１０及び第２のプロセッサ３２０によって実行され、第１のシーケンスが第１のプロセッサにのみ格納され、第２のシーケンスが第２のプロセッサにのみ格納されるようにされる。第１のプロセッサと第２のプロセッサとの間で送信される(３３０)データは、公開鍵３６０を用いて準同型に暗号化される。公開鍵は、第１のプロセッサ及び第２のプロセッサの双方に利用可能である。しかしながら、第１のプロセッサのみが秘密鍵３５０を有し、このため、第１のプロセッサのみがシンボルを復号することができる。
【００２１】
この発明の実施の形態は、変形の最小コストを、システム、すなわち行列３２６の動的計画法による解として定式化する。行列の暗号化された(ζ)要素は、以前に求められた要素の値に基づいて再帰的に求められる。
【００２２】
第１のシーケンス
【００２３】
【数１】
【００２４】
及び第２のシーケンス
【００２５】
【数２】
【００２６】
は、方法３００への入力である。シンボルｘｉ及びｙｊは、有限アルファベット集合Ａ(図示せず)に属する。便宜上、サブシーケンス
【００２７】
【数３】
【００２８】
は
【００２９】
【数４】
【００３０】
であり、ここで、インデックスａ、ｂは適切な制限内にあり、シンボルｙｋの挿入コストはＩ(ｙｋ)であり、シンボルｘｋの削除コストはＤ(ｘｋ)であり、シンボルｘｋをシンボルｙｉに置換する置換コストはＳ(ｘｋ，ｙｉ)であり、ここでｋ及びｉはシーケンス内のシンボルのインデックスである。
【００３１】
挿入コストＩ(ｙｋ)、削除コストＤ(ｘｋ)、及び置換コストＳ(ｘｋ，ｙｉ)は様々な実施の形態にわたって変動する。
【００３２】
Ｍ(ｉ，ｊ)がサブシーケンス
【００３３】
【数５】
【００３４】
をサブシーケンス
【００３５】
【数６】
【００３６】
に変形する最小コストである場合、１≦ｉ≦ｎ及び１≦ｊ≦ｍについて以下となる。
【００３７】
【数７】
【００３８】
上述したように、式(１)における行列の要素は再帰的に求められる。すなわち、Ｍ(ｉ，ｊ)は、Ｍ(ｉ−１，ｊ)、Ｍ(ｉ，ｊ−１)、及びＭ(ｉ−１，ｊ−１)を使用して計算される。さらに、編集距離Ｍ(ｎ，ｍ)は、第１のシーケンス
【００３９】
【数８】
【００４０】
を第２のシーケンス
【００４１】
【数９】
【００４２】
に変形する最小コストである。図３に示す例では、文字列「ＦＡＳＴ」及び「ＦＩＲＳＴ」間の編集距離３４０はＭ(４，５)＝２である。
【００４３】
方法３００は、第２のプロセッサにおける暗号化された領域内の行列の要素を求め、第２のプロセッサは、秘密鍵なしで要素の値を復号することができない。この発明の実施の形態は、意味論的にセキュアな(semantically secure：強秘匿性の)準同型暗号化の特性に基づいて、暗号化された数字の集合から最小の数字をセキュアに求めることが可能であるという認識に基づいている。
【００４４】
動的計画法による解３４５が暗号化された編集距離として選択される。暗号化された編集距離をメモリ(図示せず)内に格納しかつ／又は秘密鍵を用いた復号のために第１のプロセッサに送信することができる。
【００４５】
図５は、編集距離を求めることが、式(１)に従ってＭ(ｉ，ｊ)を計算することにまで低減されたものを示している。それぞれ第１のシーケンス及び第２のシーケンスの全てのｉ及びｊ(１≦ｉ≦ｎ、１≦ｊ≦ｍ)について、第１のプロセッサ及び第２のプロセッサは、最小値発見方法４００を使用して、行列の現在の要素４６０を、第１の要素５１０、第２の要素５２０、及び第３の要素５３０の最小値の暗号化として求める。ここで、第１の要素は挿入コスト３３２を表し、第２の要素は削除コスト３３４を表し、第３の要素は置換コスト３３６を表し、現在の要素、第１の要素、第２の要素、及び第３の要素は、公開鍵３６０を用いて準同型に暗号化される(５４０)。現在の要素Ｍ(ｉ，ｊ)の暗号化された値は、
ξ(ｍｉｎ{Ｍ(ｉ−１，ｊ−１)＋Ｓ(ｘｉ，ｙｊ)，Ｍ(ｉ−１，ｊ)＋Ｄ(ｘｉ)，Ｍ(ｉ，ｊ−１)＋Ｉ(ｙｊ)})＝ξ(Ｍ(ｉ，ｊ))
に従って求められる。
【００４６】
値Ｍ(ｉ−１，ｊ−１)３４４、Ｍ(ｉ，ｊ−１)３４６、及びＭ(ｉ−１，ｊ)３４２は、方法３００の以前の反復によって求められる。挿入コストＩ(ｙｊ)の暗号化、すなわちξ(Ｉ(ｙｊ))は、第１のプロセッサから第２のプロセッサに送信される。削除コストＤ(ｘｉ)及びしたがって暗号化ξ(Ｄ(ｘｉ))は第２のプロセッサに利用可能である。置換コストＳ(ｘｉ，ｙｊ)の暗号化、すなわちξ(Ｓ(ｘｉ，ｙｊ))は、下記で説明するように動的に提供されるか又は求められる。
【００４７】
挿入コストを表す第１の要素は、加法的準同型暗号化の特性に基づいて
ξ(Ｉ(ｙｊ))ξ(Ｍ(ｉ，ｊ−１))＝ξ(Ｉ(ｙｊ)＋Ｍ(ｉ，ｊ−１))
に従って求められる。
【００４８】
削除コストを表す第２の要素は、加法的準同型暗号化の特性に基づいて
ξ(Ｄ(ｘｉ))ξ(Ｍ(ｉ−１，ｊ))＝ξ(Ｄ(ｘｉ)＋Ｍ(ｉ−１，ｊ))
に従って求められる。
【００４９】
置換コストを表す第３の要素は、加法的準同型暗号化の特性に基づいて
ξ(Ｓ(ｘｉ，ｙｊ))ξ(Ｍ(ｉ−１，ｊ−１))＝ξ(Ｓ(ｘｉ，ｙｊ)＋Ｍ(ｉ−１，ｊ−１))
に従って求められる。
【００５０】
次に、最小値発見方法は、第１の要素、第２の要素、及び第３の要素を入力として受け取り(５５０)、現在の要素を最小値の暗号化された値として求める。実施の形態では、現在の要素、第１の要素、第２の要素、及び第３の要素は公開鍵を用いて準同型に暗号化される。
【００５１】
いくつかの実施の形態では、初期要素Ｍ(１，１)のための置換コストの表現、すなわちＭ(０，０)＋Ｓ(ｘ１，ｙ１)は、全ての可能なｘ１，ｙ１について双方の要素Ｍ(０，１)及びＭ(１，０)以下である。さらに、挿入コスト及び削除コストは全てのシンボルについて等しく、双方のプロセッサに知られている。１つのそのような一般的に発生する例が図２及び図３に示されている。それらの図においてＭ(０，０)＝０、Ｓ(ｘ１，ｙ１)＝１である。この実施の形態において、任意のシンボルのための挿入コスト及び削除コストは１であり、このため双方のプロセッサがＭ(０，１)＝Ｍ(１，０)＝１であることを知っている。したがって、要素Ｍ(１，１)の暗号化は最小値発見方法を使用して求められない。
【００５２】
この実施の形態では、第２のプロセッサは、適切な置換コストを使用して、ξ(Ｍ(１，１))＝ξ(Ｓ(ｘ１，ｙ１))に従って初期の暗号化された要素を求める。様々な実施の形態において、置換コストの暗号化は、所定であるか又は下記で説明するように動的に計算される。
【００５３】
行列Ｍ内の各要素の暗号化を再帰的に求めた後、１つの実施の形態において、第２のプロセッサは、暗号化された編集距離ξ(Ｍ(ｎ，ｍ))の値を第１のプロセッサに送信する。第１のプロセッサはこの値を復号し、２つのシーケンス
【００５４】
【数１０】
【００５５】
及び
【００５６】
【数１１】
【００５７】
間の編集距離を取得する。１つの実施の形態では、第１のプロセッサは編集距離の値を第２のプロセッサに返送する。このため、編集距離はプライバシーを侵害することなく求められる。すなわち、第１の信号は第１のプロセッサにのみ知られ、第２の信号は第２のプロセッサにのみ知られる。
【００５８】
準同型暗号化
Ｐを二項演算子
【００５９】
【数１２】
【００６０】
に関連付けられる平文の集合とし、Ｈを二項演算子
【００６１】
【数１３】
【００６２】
に関連付けられる暗号文の集合とする。
【００６３】
定義１
全てのａ，ｂ∈Ｐについて以下が成り立つ場合、マッピングξ：Ｐ→Ｈは準同型である。
【００６４】
【数１４】
【００６５】
実施の形態は準同型暗号システムを使用する。準同型暗号システムにおいて、演算子
【００６６】
【数１５】
【００６７】
は加法演算子であり、演算子
【００６８】
【数１６】
【００６９】
は乗法演算子である。そのような暗号システムは、加法性準同型の、たとえばベナロー(Benaloh)暗号システム及びパイエ(Paillier)暗号システムと呼ばれることがある。これらの双方の暗号システムは意味論的にセキュアである。すなわち、同じ平文の反復暗号化の結果、異なる暗号文が生じる。この発明の実施の形態は、様々な意味論的にセキュアな加法性準同型暗号システムを使用する。例として、パイエ暗号システムを以下に簡潔に要約する。
【００７０】
構成：２つの大きな素数ｐ、ｑを選択し、Ｎ＝ｐｑとする。
【００７１】
【数１７】
【００７２】
によって、Ｎ２を法とする逆数を有する非負整数の集合を表す。ｇｃｄ(Ｌ(ｇλ ｍｏｄ Ｎ２)，Ｎ)＝１となるように
【００７３】
【数１８】
【００７４】
を選択する。ここで、λ＝ｌｃｍ(ｐ−１，ｑ−１)及び
【００７５】
【数１９】
【００７６】
である。(Ｎ，ｇ)を公開鍵とし、(ｐ，ｑ)を秘密鍵とする。
【００７７】
暗号化：
【００７８】
【数２０】
【００７９】
を平文とする。次いで、暗号文が以下によって与えられる。
ξｒ(ｍ)＝ｇｍ・ｒＮ ｍｏｄ Ｎ２ (２)
ここで、
【００８０】
【数２１】
【００８１】
はランダムに選択される数字である。
【００８２】
復号：
【００８３】
【数２２】
【００８４】
を暗号文とする。次いで、以下に従って対応する平文が求められる。
【００８５】
【数２３】
【００８６】
復号は暗号化の間に使用される数字ｒの値に関わらず機能する。数字ｒは全ての暗号化ごとにランダムで選択することができるため、パイエ暗号システムは確率的であり、したがって意味論的にセキュアであり、すなわち
【００８７】
【数２４】
【００８８】
である。
【００８９】
また、式(２)に従った、平文集合(ＺＮ，＋)から暗号文集合
【００９０】
【数２５】
【００９１】
へのマッピングの特性は、以下の関係を満たす。
【００９２】
【数２６】
【００９３】
【数２７】
【００９４】
ここで、ｍ１及びｍ２は任意の２つの整数メッセージであり、上記で説明した暗号システムを使用して暗号化される。上記の下付き文字ｒ１、ｒは、式(２)におけるパラメーター「ｒ」を表し、式(２)における「ｒ」の異なる値によって結果として異なる暗号文が生じるように、暗号化時に選択される。「ｒ」の値を暗号化ごとに変更することによって、パイエ暗号化は意味論的セキュリティを達成する。この明細書において、意味論的セキュリティの概念に関連しない場合、下付き文字「ｒ」は表記を簡単にするために省かれる。
【００９５】
この発明のいくつかの実施の形態はパイエ暗号化を使用する。しかしながら、他の実施の形態は他の意味論的にセキュアな加法性準同型方式を使用する。
【００９６】
最小値発見方法
図４は、この発明の実施の形態による、暗号化された数字の集合における最小の数字の暗号化を求めるための方法４００のブロック図である。方法４００は、この発明の実施の形態によって、行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として求めるのに使用される。
【００９７】
たとえば、第２のプロセッサ３２０は、準同型に暗号化された形式の数字の集合
【００９８】
【数２８】
【００９９】
たとえば、Ｌ個の数字ａ１，ａ２，…，ａＬの
【０１００】
【数２９】
【０１０１】
４１０を格納する。最小値発見方法によって、第２のプロセッサが、これらの数字の最小値の暗号化を求める、すなわち、或る係数
【０１０２】
【数３０】
【０１０３】
について、ξｒ(ｍｉｎｉ{ａｉ})４６０を求めることが可能になる。方法４００は、第２のプロセッサが、ａｉ又は最小値のインデックス若しくは値に関するいかなる情報も見つけ出すことを可能にしない。
【０１０４】
同様に、第１のプロセッサは数字ａ１，ａ２，…，ａＬに関するいかなる情報も見つけ出さない。この方法のステップは以下の通りである：
【０１０５】
１． 第２のプロセッサが、正の整数μ及びα４５０をランダムに選択する。すなわちμはスケーリング定数であり、αはランダムに選択される整数シフトである。パイエ暗号システムの場合、μを後に除去することができることを確実にするために、第２のプロセッサはμを集合
【０１０６】
【数３１】
【０１０７】
からランダムに選択する。次いで、第２のプロセッサは公開鍵３６０を使用して暗号化
【０１０８】
【数３２】
【０１０９】
４５１を取得し、ｉ＝１，２，…，Ｌについて暗号化された和
【０１１０】
【数３３】
【０１１１】
４２０を求めて暗号化された和の集合４２０を生成し、該暗号化された和の集合を第１のプロセッサに送信する(４２５)。パイエ暗号システムの場合、暗号化係数ｒ’ｉ＝ｒｉｒ０であり、第２のプロセッサは暗号化係数ｒｉを知ることなく暗号化係数ｒ’ｉを求めることができない。
【０１１２】
２． 第１のプロセッサが秘密鍵３５０を用いて数字を復号し、ｍｉｎｉ{μａｉ}＋α ４３０によって与えられる最小値を求め、次いで、その結果を公開鍵を用いて暗号化して暗号化された最小値
【０１１３】
【数３４】
【０１１４】
４６０を生成し、該暗号化された最小値を第２のプロセッサに返送する(４６５)。
【０１１５】
３． 第２のプロセッサが
【０１１６】
【数３５】
【０１１７】
４５２を計算し、
【０１１８】
【数３６】
【０１１９】
４７０を求める。
【０１２０】
非常に高い確率で、ξｒ(ｍｉｎｉ{μａｉ})が、暗号化
【０１２１】
【数３７】
【０１２２】
のうちのいずれとも等しくないことに留意されたい。これは、第１のプロセッサが、第２のプロセッサに知られていないランダムな暗号化係数ｒＢを選択し、これによって暗号化が意味論的にセキュアになるためである。これによって、第２のプロセッサが最小値の暗号化を取得するとき、元のシーケンス
【０１２３】
【数３８】
【０１２４】
における最小値のインデックスが第２のプロセッサから隠されたままであることが確実になる。
【０１２５】
４． 第２のプロセッサは、
(ξ(ｍｉｎｉ{μａｉ}))１／μ＝(ξｒ(μｍｉｎｉ{ａｉ}))１／μ＝ξｒ(ｍｉｎｉ{ａｉ})
に従って、いずれが暗号化された最小値４６０であるのかを確定する(４８０)。
【０１２６】
正の整数μ及びαを使用することによって、第１のプロセッサが数字αｉのいかなる情報を見つけ出すことも阻止されることに留意されたい。さらに、意味論的セキュリティに起因して、第２のプロセッサは最小値のインデックス「ｉ」を見つけ出すことができない。最後に、第２のプロセッサは、復号鍵を有しないため、最小値の実際の値を求めることができない。
【０１２７】
編集距離を求めるために、３つの値、すなわち上記のＬ＝３を用いて最小値発見方法が実行される。１つの実施の形態では、各シンボルが正の挿入コスト及び削除コスト、並びに非負の置換コストを有する。
【０１２８】
他の実施の形態では、いくつかのシンボルは負若しくはゼロの挿入コスト及び／又は負若しくはゼロの削除コストを有する。付加的に又は代替的に、挿入コスト、削除コスト、及び置換コストに対応する３つのエントリ全てを等しくすることができる。そのような場合、第１のプロセッサが変数μ及びαの値を求めることができない場合であっても、第１のプロセッサは各シンボルの挿入コストに基づいて、最小値を求めることができる。
【０１２９】
そのような実施の形態では、第２のプロセッサは、ベクトル
【０１３０】
【数３９】
【０１３１】
に２つ以上の「ダミー」変数を付加する。すなわち、Ｌ＞３である。最小値発見方法の各反復において、第１のプロセッサがダミー変数に関するいかなる情報を取得することも阻止するために、異なるダミー変数及び／又は異なる数のダミー変数が使用される。次いで、第１のプロセッサは、上記のステップ２のように復号し最小値を求めた後で、１つ又は複数の暗号化された値を求めて該値を第２のプロセッサに送信する。
【０１３２】
たとえば、いくつかの実施の形態では、第２のプロセッサはベクトル
【０１３３】
【数４０】
【０１３４】
にダミーの変数ξ(Ａ)及びξ(Ｂ)を付加する。ここで、ａｉの全ての値と比較して、変数Ａは大きい数であり、変数Ｂは小さい数である。次いで、第２のプロセッサは、第１のプロセッサからの２つの最も小さい値の暗号化を要求する。その際いずれの値が最も小さく、いずれの値が２番目に小さいかが特定される。
【０１３５】
第１のプロセッサは最も小さい値が変数Ｂに対応することを知っているため、第２のプロセッサは、第１のプロセッサから受信した最小値のインデックスに対応する暗号化された要素を除外し、真の最小値の暗号化された値として２番目に小さい値の暗号化を選択する。
【０１３６】
いくつかの実施の形態では、共通の定数αを有する代わりに、第２のプロセッサは２の累乗としてμを使用し、全てのｉ＝１，２，…，Ｌについてαｉ＜μとなるように様々な等しくない定数α１、α２，…，αＬを選択する。第２のプロセッサは、上記のステップ１のように暗号化ξ(μａｉ＋αｉ)を第１のプロセッサに送信する。次いで、第１のプロセッサは、ステップ２と同様に、暗号化を復号し、最小値ｍｉｎｉ μａｉ＋αｉを求める。しかしながら、第１のプロセッサは、最小値の暗号化を返送する代わりに、最小値をバイナリに変換し、各ビットを暗号化し、該暗号化されたビットを第２のプロセッサに送信する。第２のプロセッサがα１、α２，…，αＬの値を選択したため、第２のプロセッサはαｉに対してどれだけ多くのビットが利用されたかを正確に知り、μによってスケーリングされた所望の最小値に対して残りのビットが利用されたことを知っている。全てのｉ＝１，２，…，Ｌについてαｉ＜μであるため、これらのビット間に重複が存在しないことに留意されたい。このため、準同型暗号化の特性を使用して、第２のプロセッサはμによってスケーリングされた最小値に対応するビットを取得する。次いで、第２のプロセッサは上記のステップ４に従ってμによって乗算を反転させる(reverse the multiplication)。第１のプロセッサは、ａｉの値のうちの１つ又は複数が等しい場合であっても、最小値の値を知ることを阻止される。
【０１３７】
置換コストを求める
この発明の実施の形態は、行列の現在の要素を、挿入コスト、削除コスト、及び置換コストを表す要素の最小値の暗号化として求める。異なる実施の形態では、挿入コスト、削除コスト、及び置換コストは所定であるか、動的に求められるか、又はそれらの組み合わせが使用される。
【０１３８】
たとえば、１つの実施の形態では、挿入コスト、削除コスト、及び置換コストは所定である。これらの実施の形態の１つの変形形態では、全てのコストは整数値である。別の実施の形態では、挿入コスト及び削除コストは所定であるが、置換コストは動的に求められる。この実施の形態の１つの変形形態では置換コストは置換されるシンボルの値に基づいて求められる。
【０１３９】
定数の置換コスト
１つの実施の形態では、置換コストは、第１のシーケンス及び第２のシーケンスが異なる場合に或る定数であり、シンボルが同一である場合にゼロである。この実施の形態の１つの変形形態は、アルファベットのシンボルを整数集合{１，２，３，…，Ｑ}にマッピングする。ここでＱはアルファベット集合のサイズである。たとえば、シンボルＡ、Ｔ、Ｃ、Ｇを有するＤＮＡシーケンスの場合、サイズＱ＝４である。この実施の形態における置換コストは、ａ＝ｂの場合にＳ(ａ，ｂ)＝０であり、ａ≠ｂの場合にＳ(ａ，ｂ)である。ここでａは第１のシーケンスのシンボルであり、ｂは第２のシーケンスのシンボルである。
【０１４０】
図６は、以下のステップに従って定数の置換コストを求めるための方法の擬似コードを示している。
１．第１のプロセッサが第１の文字列のシンボル「ａ」を、最初の「ａ」個のビットが１に等しく、最後のＱ−ａ個のビットが０に等しい長さＱの第１のバイナリシーケンスに変換する。第１のバイナリ文字列からの文字列はａｉとして定義される。ここでｉは１からＱの範囲をとる。同様に、第２のプロセッサが第２のシーケンスのシンボル「ｂ」を、最初の「ｂ」個のビットが１に等しく、最後のＱ−ｂ個のビットが０に等しい長さＱの第２のバイナリシーケンスに変換する。
２．第１のプロセッサが、第１のバイナリシーケンス内の各ビットの暗号化を第２のプロセッサに送信する。
３．第２のプロセッサが、第２のバイナリ列からの第１のビット及び第２のビット、並びに第１のバイナリシーケンスからの第１の暗号化されたビット及び第２の暗号化されたビットから、
ξ(Ｕ１)＝ξ(ａ１ｂ１−ａ２ｂ１)＝ξ(ａ１ｂ２)ξ(−ａ２ｂ１)＝［ξ(ｂ２)のａ１乗］＊［ξ(ｂ１)の(−ａ２)乗］
に従って２×２の行列式を計算する。
４．第２のプロセッサが双方のバイナリシーケンスからの第２のビット及び第３のビットに対して、次いで第３のビット及び第４のビットに対して、そして以下同様に、長さＱのシーケンス全体が使い果たされるまで以前のステップを反復する。このようにして、第２のプロセッサは暗号化された２×２の行列式ξ(Ｕ１)，ξ(Ｕ２)，…，ξ(ＵＱ−１)を求める。
５．第２のプロセッサは行列式ξ(Ｕ)の和をΠｉξ(Ｕｉ)＝ξ(ΣｉＵｉ)として計算する。ここでｉは１からＱ−１で変動する。これは加法的準同型暗号化の特性を使用する。
６．第２のプロセッサは数字ｄをランダムに選択し、ξ(Ｕ＋ｄ)＝ξ(Ｕ)ξ(ｄ)を計算し、結果を第１のプロセッサに送信する。
７．第１のプロセッサは２つの数字を暗号化し、積(Ｕ＋ｄ)２＝Ｕ’を求め、積Ｕ’を暗号化してξ(Ｕ’)を第２のプロセッサに返送する。
８．第２のプロッセッサーがξ(Ｕ’)ξ(−２ｄＵ)ξ(−ｄ２)＝ξ(Ｕ’−２ｄＵ−ｄ２)＝ξ(Ｕ２)を計算する。
【０１４１】
構築によって、Ｕ＝０、１、又は−１である。したがって、Ｕ２は、シンボル「ａ」及び「ｂ」が同じであるか又は異なっているかにそれぞれ依拠して、０又は１である。このため、ξ(Ｕ２)は置換コストの暗号化された値を提供する。第２のプロセッサは、実際の時間コストではなく暗号化された置換コストしか取得しない。これは、第２のプロセッサが復号鍵を有しないためである。第１のプロセッサは数字「ｄ」を知らないことに起因して何も知らない。
【０１４２】
絶対距離置換コスト
別の実施の形態では、置換コストは第１のシーケンスのシンボルと第２のシーケンスのシンボルとの間の絶対距離であり、すなわち、シンボルがそれぞれ「ａ」及び「ｂ」である場合、置換コストＳ(ａ，ｂ)＝｜ａ−ｂ｜である。上述の実施の形態と同様に、アルファベットにおけるシンボルは整数集合{１，２，３，…，Ｑ}にマッピングされる。最小化プロトコルによれば、第１のプロセッサは置換コストの暗号化を求めることができる。第２のプロセッサは求めることができない。
【０１４３】
図７は、以下のステップに従って絶対距離置換コストを求めるための方法の擬似コードを示している。
１．第１のプロセッサが第１のシーケンスのシンボル「ａ」を、最初の「ａ」個のビットが１に等しく、最後のＱ−ａ個のビットが０に等しい長さＱの第１のバイナリシーケンスに変換する。第１のバイナリ文字列からの文字列はａｉとして定義される。ここでｉは１からＱの範囲をとる。同様に、第２のプロセッサが第２のシーケンスのシンボル「ｂ」を、最初の「ｂ」個のビットが１に等しく、最後のＱ−ｂ個のビットが０に等しい長さＱの第２のバイナリシーケンスに変換する。
２．第１のプロセッサが、バイナリシーケンス内の各ビットの暗号化を第２のプロセッサに送信する。
３．第２のプロセッサが、加法的準同型暗号化の特性に基づいて以下の式に従って置換コストの暗号化ξ(Ｓ(ａ，ｂ))を求める。
４．
【０１４４】
【数４１】
【０１４５】
多項式関数置換コスト
別の実施の形態では、参照によりこの明細書に援用される米国特許出願第１２／４９５，７２１号に記載されているように、置換コストは２つのシーケンスのシンボルに多項式関数を適用した結果である。たとえば、第２のプロセッサは整数ａを格納し、第１のプロセッサは整数ｂを格納する。実施の形態は、第２のプロセッサにおいて、暗号化された形式の置換コスト
【０１４６】
【数４２】
【０１４７】
を求める。
【０１４８】
置換コストＳ(ａ，ｂ)＝(ａ−ｂ)Ｓはｂにおける次数Ｓの多項式であり、すなわち０≦ｊ≦Ｓである。このため、第２のプロセッサは、或る暗号化係数
【０１４９】
【数４３】
【０１５０】
について置換コストξ(Σｉ，ｊｃｉｊａｉｂｊ)を求める。第２のプロセッサは、秘密鍵を保有していないため、置換コストを復号することができない。第１のプロセッサは整数ｂの値しか知らない。ステップは以下の通りである：
１．０≦ｊ≦Ｓについて、第１のプロセッサがｂｊを暗号化し、
【０１５１】
【数４４】
【０１５２】
を第２のプロセッサに送信する。
２．第２のプロセッサがｃｉ，ｊ及びａの値に基づいて
【０１５３】
【数４５】
【０１５４】
を求める。
【０１５５】
この方法は、紛失通信に基づく方法と比較して、多項式評価法に関して大幅に低い計算及び通信のオーバーヘッドを受ける。紛失通信に基づく方法は非常に単純な多項式の場合であっても極度に複雑となり、大きな送信オーバーヘッドを受ける。
【０１５６】
最も長い共通サブシーケンス
この発明の１つの実施の形態は、第１のシーケンスと第２のシーケンスとの間の最も長い共通サブシーケンスの長さを求める。この実施の形態は、多くの点において編集距離を求めるための実施の形態に類似している。主な違いは２つしかない。
【０１５７】
第１に、方法の各ステップにおいて３つの要素の最小値を計算する代わりに、この実施の形態は３つの要素の最大値を求める。たとえば、数値の場合、２つのプロセッサは全ての値の符号を逆にし、上述した最小値発見方法を使用する。
【０１５８】
第２に、セッサがｍｎ個の暗号化された要素を用いて１つ又は複数の最大値発見プロトコルを実行して、所望の結果を取得することを意味する。所望の結果は、最も長い共通サブシーケン編集距離を行列の最後の要素Ｍ(ｎ，ｍ)として選択する代わりに、行列全体を検索して該行列内の最大の要素を発見する。最大の要素の暗号化は、行列Ｍ内の各要素の符号を逆にし、上述した最小化プロトコルを適用することによって発見することができる。次いで、取得した結果が第１のプロセッサに送信され、第１のプロセッサは、該結果を復号して最大の要素を取得する。最大の要素は最も長い共通サブシーケンスの長さを与える。これは、行列全体を計算した後、２つのプロスの長さの暗号化である。
【０１５９】
この発明を好ましい実施の形態の例として説明してきたが、この発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、この発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【特許請求の範囲】
【請求項１】
暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるための方法であって、
前記最小コストを、行列の動的計画法による解として定式化するステップであって、前記行列の要素が、以前に求められた要素の値に基づいて再帰的に求められるものと、
前記行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として求めるステップであって、前記第１の要素は前記挿入コストを表し、前記第２の要素は前記削除コストを表し、前記第３の要素は前記置換コストを表し、前記現在の要素、前記第１の要素、前記第２の要素、及び前記第３の要素が、公開鍵を用いて準同型に暗号化されるものと、
前記求めるステップを再帰的に反復して前記動的計画法による解を生成するステップと、
前記動的計画法による解を前記暗号化された編集距離として選択するステップと、
を含み、該方法の複数の前記ステップは、第１のプロセッサ及び第２のプロセッサによって実行され、前記第１のシーケンスが前記第１のプロセッサにのみ格納されると共に前記第２のプロセッサから秘密にされ、前記第２のシーケンスが前記第２のプロセッサにのみ格納されると共に前記第１のプロセッサから秘密にされるようにする、方法。
【請求項２】
前記求めるステップは、意味論的にセキュアな準同型暗号化の特性に基づくものである、請求項１に記載の方法。
【請求項３】
前記第１のプロセッサ及び前記第２のプロセッサに前記公開鍵を提供するステップと、
前記第１のプロセッサにのみ秘密鍵を提供するステップと、
をさらに含む、請求項１に記載の方法。
【請求項４】
前記暗号化された編集距離を前記第１のプロセッサに送信するステップと、
前記暗号化された編集距離を前記秘密鍵を用いて復号するステップと、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記行列の初期要素を前記置換コストとして求めるステップをさらに含み、前記第１の要素は前記第１のシーケンスの第１のシンボルであり、前記第２の要素は前記第２のシーケンスの第１のシンボルである、請求項１に記載の方法。
【請求項６】
前記現在の要素を
ξ(ｍｉｎ{Ｍ(ｉ−１，ｊ−１)＋Ｓ(ｘｉ，ｙｊ)，Ｍ(ｉ−１，ｊ)＋Ｄ(ｘｉ)，Ｍ(ｉ，ｊ−１)＋Ｉ(ｙｊ)})＝ξ(Ｍ(ｉ，ｊ))
に従って求めるステップであって、ここで、ξ(．)は暗号化関数であり、Ｍ(ｉ，ｊ)は前記現在の要素であり、Ｉ(ｙｊ)はシンボルｙｊの前記挿入コストであり、Ｄ(ｘｉ)はシンボルｘｉの前記削除コストであり、Ｓ(ｘｉ，ｙｊ)は前記シンボルｘｉを前記シンボルｙｊに置換する前記置換コストであり、ｉ及びｊは前記シーケンス内の前記シンボルのインデックスであるものをさらに含む、請求項１に記載の方法。
【請求項７】
前記第１の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｉ(ｙｊ))ξ(Ｍ(ｉ，ｊ−１))＝ξ(Ｉ(ｙｊ)＋Ｍ(ｉ，ｊ−１))
に従って求めるステップと、
前記第２の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｄ(ｘｉ))ξ(Ｍ(ｉ−１，ｊ))＝ξ(Ｄ(ｘｉ)＋Ｍ(ｉ−１，ｊ))
に従って求めるステップと、
前記第３の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｓ(ｘｉ，ｙｊ))ξ(Ｍ(ｉ−１，ｊ−１))＝ξ(Ｓ(ｘｉ，ｙｊ)＋Ｍ(ｉ−１，ｊ−１))
に従って求めるステップと、
をさらに含む、請求項６に記載の方法。
【請求項８】
前記第１の要素、前記第２の要素、及び前記第３の要素を前記第１のプロセッサに送信するステップをさらに含む、請求項７に記載の方法。
【請求項９】
最小値発見方法を使用して前記現在の要素を求めるステップであって、該最小値発見方法が、準同系に暗号化された形式で数字の最小値の暗号化を求めるようにされているものをさらに含む、請求項１に記載の方法。
【請求項１０】
前記第１の要素、前記第２の要素、及び前記第３の要素のそれぞれについて、暗号化された和を求めるステップであって、暗号化された和の集合を生成し、前記暗号化された和は
【数１】
に従って求められ、ここで、ｉ＝１，２，…，Ｌ及びＬ＝３であり、μは定数であり、αはランダムに選択される整数シフトであり、ｒｉ、ｒ０はランダムに選択される暗号化係数であり、暗号化係数ｒ’ｉ＝ｒｉｒ０であり、ξ(．)は暗号化関数であるものと、
前記第２のプロセッサから前記第１のプロセッサに前記暗号化された和の集合を送信するステップであって、前記第１のプロセッサは、秘密鍵を使用して前記暗号化された和を復号し、前記暗号化された和の集合から最小値を求めると共に、該最小値を前記公開鍵を用いて暗号化して前記現在の要素を生成するようにされたものと、
前記第２のプロセッサによって、前記第１のプロセッサから送信された前記現在の要素を受信するステップと、
をさらに含む、請求項９に記載の方法。
【請求項１１】
スケーリング定数μを２の累乗として選択するステップと、
前記第２のプロセッサによって、各前記整数シフトが前記スケーリング定数よりも小さくなるように、前記第１の要素、前記第２の要素、及び前記第３の要素のために異なる整数シフトαｉ、ｉ＝１，２，３を選択するステップと、
前記第２のプロセッサから前記第１のプロセッサに前記暗号化された和の集合を送信するステップであって、前記第１のプロセッサは秘密鍵を使用して前記暗号化された和を復号し、前記暗号化された和の集合から最小値を求め、該最小値をバイナリ形式に変換すると共に、該最小値を暗号化して暗号化されたビットを生成するものと、
前記第２のプロセッサによって、前記第１プロセッサから前記暗号化されたビットを受信するステップと、
前記整数シフトαｉ及び前記スケーリング定数μに基づいて前記暗号化されたビットから関連するビットのみを選択するステップと、
をさらに含む、請求項１０に記載の方法。
【請求項１２】
前記置換コストは、前記第１のシーケンスからのシンボル及び前記第２のシーケンスからのシンボルの多項式関数である、請求項１に記載の方法。
【請求項１３】
前記置換コストは、前記第１のシーケンスからのシンボルと前記第２のシーケンスからのシンボルとの間の絶対距離である、請求項１に記載の方法。
【請求項１４】
前記置換コストは、前記第１のシーケンスからのシンボルが前記第２のシーケンスからのシンボルと異なる場合に或る定数であり、前記第１のシーケンスからの前記シンボルが前記第２のシーケンスからの前記シンボルと同一である場合にゼロである、請求項１に記載の方法。
【請求項１５】
前記第１のシーケンスと前記第２のシーケンスとの間の最も長い共通サブシーケンスの長さを求めるステップをさらに含む、請求項１に記載の方法。
【請求項１６】
暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるように構成されたシステムであって、前記最小コストは行列の動的計画法による解であり、前記行列の要素は、以前に求められた要素の値に基づいて再帰的に求められ、該システムは、
前記行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として求めるように構成される第１のプロセッサであって、前記第１の要素は前記挿入コストを表し、前記第２の要素は前記削除コストを表し、前記第３の要素は前記置換コストを表し、前記現在の要素、前記第１の要素、前記第２の要素、及び前記第３の要素は、公開鍵を用いて準同型に暗号化されるものと、
加法的準同型暗号化の特性に基づいて、前記第１の要素、前記第２の要素、及び前記第３の要素を求めるように構成される第２のプロセッサであって、前記第１のシーケンスは前記第１のプロセッサにのみ格納されると共に該第２のプロセッサから秘密にされ、前記第２のシーケンスは該第２のプロセッサにのみ格納されると共に前記第１のプロセッサから秘密にされるものと、
前記動的計画法による解を再帰的に求める手段と、
前記動的計画法による解を前記暗号化された編集距離として選択する手段と、
を備える、システム。
【請求項１７】
前記公開鍵は前記第１のプロセッサ及び前記第２のプロセッサに提供され、秘密鍵は前記第１のプロセッサにのみ提供される、請求項１６に記載のシステム。
【請求項１８】
前記第１のプロセッサは、前記現在の要素を
ξ(ｍｉｎ{Ｍ(ｉ−１，ｊ−１)＋Ｓ(ｘｉ，ｙｊ)，Ｍ(ｉ−１，ｊ)＋Ｄ(ｘｉ)，Ｍ(ｉ，ｊ−１)＋Ｉ(ｙｊ)})＝ξ(Ｍ(ｉ，ｊ))
に従って求める手段を備え、ここで、ξ(．)は暗号化関数であり、Ｍ(ｉ，ｊ)は前記現在の要素であり、Ｉ(ｙｊ)はシンボルｙｊの前記挿入コストであり、Ｄ(ｘｉ)はシンボルｘｉの前記削除コストであり、Ｓ(ｘｉ，ｙｊ)は前記シンボルｘｉを前記シンボルｙｊに置換する前記置換コストであり、ｉ及びｊは前記シーケンス内の前記シンボルのインデックスである、請求項１６に記載のシステム。
【請求項１９】
前記第２のプロセッサは、
前記第１の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｉ(ｙｊ))ξ(Ｍ(ｉ，ｊ−１))＝ξ(Ｉ(ｙｊ)＋Ｍ(ｉ，ｊ−１))
に従って求める手段と、
前記第２の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｄ(ｘｉ))ξ(Ｍ(ｉ−１，ｊ))＝ξ(Ｄ(ｘｉ)＋Ｍ(ｉ−１，ｊ))
に従って求める手段と、
前記第３の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｓ(ｘｉ，ｙｊ))ξ(Ｍ(ｉ−１，ｊ−１))＝ξ(Ｓ(ｘｉ，ｙｊ)＋Ｍ(ｉ−１，ｊ−１))
に従って求める手段と、
を備える、請求項１６に記載のシステム。
【請求項２０】
前記第１のプロセッサは、最小値発見方法を使用して前記現在の要素を求める手段であって、該最小値発見方法は、準同系に暗号化された形式で数字の最小値の暗号化を求めるように構成されているものをさらに備える、請求項１６に記載のシステム。
【請求項１】
暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるための方法であって、
前記最小コストを、行列の動的計画法による解として定式化するステップであって、前記行列の要素が、以前に求められた要素の値に基づいて再帰的に求められるものと、
前記行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として求めるステップであって、前記第１の要素は前記挿入コストを表し、前記第２の要素は前記削除コストを表し、前記第３の要素は前記置換コストを表し、前記現在の要素、前記第１の要素、前記第２の要素、及び前記第３の要素が、公開鍵を用いて準同型に暗号化されるものと、
前記求めるステップを再帰的に反復して前記動的計画法による解を生成するステップと、
前記動的計画法による解を前記暗号化された編集距離として選択するステップと、
を含み、該方法の複数の前記ステップは、第１のプロセッサ及び第２のプロセッサによって実行され、前記第１のシーケンスが前記第１のプロセッサにのみ格納されると共に前記第２のプロセッサから秘密にされ、前記第２のシーケンスが前記第２のプロセッサにのみ格納されると共に前記第１のプロセッサから秘密にされるようにする、方法。
【請求項２】
前記求めるステップは、意味論的にセキュアな準同型暗号化の特性に基づくものである、請求項１に記載の方法。
【請求項３】
前記第１のプロセッサ及び前記第２のプロセッサに前記公開鍵を提供するステップと、
前記第１のプロセッサにのみ秘密鍵を提供するステップと、
をさらに含む、請求項１に記載の方法。
【請求項４】
前記暗号化された編集距離を前記第１のプロセッサに送信するステップと、
前記暗号化された編集距離を前記秘密鍵を用いて復号するステップと、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記行列の初期要素を前記置換コストとして求めるステップをさらに含み、前記第１の要素は前記第１のシーケンスの第１のシンボルであり、前記第２の要素は前記第２のシーケンスの第１のシンボルである、請求項１に記載の方法。
【請求項６】
前記現在の要素を
ξ(ｍｉｎ{Ｍ(ｉ−１，ｊ−１)＋Ｓ(ｘｉ，ｙｊ)，Ｍ(ｉ−１，ｊ)＋Ｄ(ｘｉ)，Ｍ(ｉ，ｊ−１)＋Ｉ(ｙｊ)})＝ξ(Ｍ(ｉ，ｊ))
に従って求めるステップであって、ここで、ξ(．)は暗号化関数であり、Ｍ(ｉ，ｊ)は前記現在の要素であり、Ｉ(ｙｊ)はシンボルｙｊの前記挿入コストであり、Ｄ(ｘｉ)はシンボルｘｉの前記削除コストであり、Ｓ(ｘｉ，ｙｊ)は前記シンボルｘｉを前記シンボルｙｊに置換する前記置換コストであり、ｉ及びｊは前記シーケンス内の前記シンボルのインデックスであるものをさらに含む、請求項１に記載の方法。
【請求項７】
前記第１の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｉ(ｙｊ))ξ(Ｍ(ｉ，ｊ−１))＝ξ(Ｉ(ｙｊ)＋Ｍ(ｉ，ｊ−１))
に従って求めるステップと、
前記第２の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｄ(ｘｉ))ξ(Ｍ(ｉ−１，ｊ))＝ξ(Ｄ(ｘｉ)＋Ｍ(ｉ−１，ｊ))
に従って求めるステップと、
前記第３の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｓ(ｘｉ，ｙｊ))ξ(Ｍ(ｉ−１，ｊ−１))＝ξ(Ｓ(ｘｉ，ｙｊ)＋Ｍ(ｉ−１，ｊ−１))
に従って求めるステップと、
をさらに含む、請求項６に記載の方法。
【請求項８】
前記第１の要素、前記第２の要素、及び前記第３の要素を前記第１のプロセッサに送信するステップをさらに含む、請求項７に記載の方法。
【請求項９】
最小値発見方法を使用して前記現在の要素を求めるステップであって、該最小値発見方法が、準同系に暗号化された形式で数字の最小値の暗号化を求めるようにされているものをさらに含む、請求項１に記載の方法。
【請求項１０】
前記第１の要素、前記第２の要素、及び前記第３の要素のそれぞれについて、暗号化された和を求めるステップであって、暗号化された和の集合を生成し、前記暗号化された和は
【数１】
に従って求められ、ここで、ｉ＝１，２，…，Ｌ及びＬ＝３であり、μは定数であり、αはランダムに選択される整数シフトであり、ｒｉ、ｒ０はランダムに選択される暗号化係数であり、暗号化係数ｒ’ｉ＝ｒｉｒ０であり、ξ(．)は暗号化関数であるものと、
前記第２のプロセッサから前記第１のプロセッサに前記暗号化された和の集合を送信するステップであって、前記第１のプロセッサは、秘密鍵を使用して前記暗号化された和を復号し、前記暗号化された和の集合から最小値を求めると共に、該最小値を前記公開鍵を用いて暗号化して前記現在の要素を生成するようにされたものと、
前記第２のプロセッサによって、前記第１のプロセッサから送信された前記現在の要素を受信するステップと、
をさらに含む、請求項９に記載の方法。
【請求項１１】
スケーリング定数μを２の累乗として選択するステップと、
前記第２のプロセッサによって、各前記整数シフトが前記スケーリング定数よりも小さくなるように、前記第１の要素、前記第２の要素、及び前記第３の要素のために異なる整数シフトαｉ、ｉ＝１，２，３を選択するステップと、
前記第２のプロセッサから前記第１のプロセッサに前記暗号化された和の集合を送信するステップであって、前記第１のプロセッサは秘密鍵を使用して前記暗号化された和を復号し、前記暗号化された和の集合から最小値を求め、該最小値をバイナリ形式に変換すると共に、該最小値を暗号化して暗号化されたビットを生成するものと、
前記第２のプロセッサによって、前記第１プロセッサから前記暗号化されたビットを受信するステップと、
前記整数シフトαｉ及び前記スケーリング定数μに基づいて前記暗号化されたビットから関連するビットのみを選択するステップと、
をさらに含む、請求項１０に記載の方法。
【請求項１２】
前記置換コストは、前記第１のシーケンスからのシンボル及び前記第２のシーケンスからのシンボルの多項式関数である、請求項１に記載の方法。
【請求項１３】
前記置換コストは、前記第１のシーケンスからのシンボルと前記第２のシーケンスからのシンボルとの間の絶対距離である、請求項１に記載の方法。
【請求項１４】
前記置換コストは、前記第１のシーケンスからのシンボルが前記第２のシーケンスからのシンボルと異なる場合に或る定数であり、前記第１のシーケンスからの前記シンボルが前記第２のシーケンスからの前記シンボルと同一である場合にゼロである、請求項１に記載の方法。
【請求項１５】
前記第１のシーケンスと前記第２のシーケンスとの間の最も長い共通サブシーケンスの長さを求めるステップをさらに含む、請求項１に記載の方法。
【請求項１６】
暗号化された編集距離を、挿入コスト、削除コスト、及び置換コストに基づいて、第１のシーケンスから第２のシーケンスへの変形の最小コストの暗号化として求めるように構成されたシステムであって、前記最小コストは行列の動的計画法による解であり、前記行列の要素は、以前に求められた要素の値に基づいて再帰的に求められ、該システムは、
前記行列の現在の要素を、第１の要素、第２の要素、及び第３の要素の最小値の暗号化として求めるように構成される第１のプロセッサであって、前記第１の要素は前記挿入コストを表し、前記第２の要素は前記削除コストを表し、前記第３の要素は前記置換コストを表し、前記現在の要素、前記第１の要素、前記第２の要素、及び前記第３の要素は、公開鍵を用いて準同型に暗号化されるものと、
加法的準同型暗号化の特性に基づいて、前記第１の要素、前記第２の要素、及び前記第３の要素を求めるように構成される第２のプロセッサであって、前記第１のシーケンスは前記第１のプロセッサにのみ格納されると共に該第２のプロセッサから秘密にされ、前記第２のシーケンスは該第２のプロセッサにのみ格納されると共に前記第１のプロセッサから秘密にされるものと、
前記動的計画法による解を再帰的に求める手段と、
前記動的計画法による解を前記暗号化された編集距離として選択する手段と、
を備える、システム。
【請求項１７】
前記公開鍵は前記第１のプロセッサ及び前記第２のプロセッサに提供され、秘密鍵は前記第１のプロセッサにのみ提供される、請求項１６に記載のシステム。
【請求項１８】
前記第１のプロセッサは、前記現在の要素を
ξ(ｍｉｎ{Ｍ(ｉ−１，ｊ−１)＋Ｓ(ｘｉ，ｙｊ)，Ｍ(ｉ−１，ｊ)＋Ｄ(ｘｉ)，Ｍ(ｉ，ｊ−１)＋Ｉ(ｙｊ)})＝ξ(Ｍ(ｉ，ｊ))
に従って求める手段を備え、ここで、ξ(．)は暗号化関数であり、Ｍ(ｉ，ｊ)は前記現在の要素であり、Ｉ(ｙｊ)はシンボルｙｊの前記挿入コストであり、Ｄ(ｘｉ)はシンボルｘｉの前記削除コストであり、Ｓ(ｘｉ，ｙｊ)は前記シンボルｘｉを前記シンボルｙｊに置換する前記置換コストであり、ｉ及びｊは前記シーケンス内の前記シンボルのインデックスである、請求項１６に記載のシステム。
【請求項１９】
前記第２のプロセッサは、
前記第１の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｉ(ｙｊ))ξ(Ｍ(ｉ，ｊ−１))＝ξ(Ｉ(ｙｊ)＋Ｍ(ｉ，ｊ−１))
に従って求める手段と、
前記第２の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｄ(ｘｉ))ξ(Ｍ(ｉ−１，ｊ))＝ξ(Ｄ(ｘｉ)＋Ｍ(ｉ−１，ｊ))
に従って求める手段と、
前記第３の要素を、加法的準同型暗号化の特性に基づいて
ξ(Ｓ(ｘｉ，ｙｊ))ξ(Ｍ(ｉ−１，ｊ−１))＝ξ(Ｓ(ｘｉ，ｙｊ)＋Ｍ(ｉ−１，ｊ−１))
に従って求める手段と、
を備える、請求項１６に記載のシステム。
【請求項２０】
前記第１のプロセッサは、最小値発見方法を使用して前記現在の要素を求める手段であって、該最小値発見方法は、準同系に暗号化された形式で数字の最小値の暗号化を求めるように構成されているものをさらに備える、請求項１６に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１１−１６４６０７（Ｐ２０１１−１６４６０７Ａ）
【公開日】平成２３年８月２５日（２０１１．８．２５）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−１９３６８（Ｐ２０１１−１９３６８）
【出願日】平成２３年２月１日（２０１１．２．１）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成２３年８月２５日（２０１１．８．２５）
【国際特許分類】
【出願番号】特願２０１１−１９３６８（Ｐ２０１１−１９３６８）
【出願日】平成２３年２月１日（２０１１．２．１）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]