(57)【特許請求の範囲】
【請求項１】
コンピュータに、暗号化された文書（Ｄｉ）についてのブール検索を実行するための方法の各ステップを実行させるコンピュータプログラムであって、各々の文書（Ｄｉ）が、キーワード（ｗｋ）のセットにより特徴付けられ、すべての文書（Ｄｉ）を特徴付けるすべてのキーワード（ｗｋ）が、索引（Ｗ）を形成し、索引（Ｗ）が、索引の各々のキーワード（ｗｋ）が正規直交基底の唯一無二のベクトル（ｕｋ）に対応する、正規直交基底に変換させられ、各々の文書（Ｄｉ）が、正規直交基底のスパン内の合成ベクトルに関連付けられ、合成ベクトルが、暗号化された検索サーバ（７）に格納されているすべての文書に対応し、前記方法が、以下のステップ、すなわち、
−  クエリアから検索クエリを受信するステップ（１１６）、
−  検索クエリを１つのクエリ行列に変換するステップ、
−  クエリ行列と合成ベクトルの各々との間の乗算の結果に基づいて全体的な結果を決定するステップ（１１１）
を含む、コンピュータプログラム。
【請求項２】
前記方法において、
索引が、少なくとも、
−  索引を自由族に変換するステップ（１０３）、
−  自由族を直交族に変換するステップ（１０４）、
−  直交族を、正規直交基底を形成する正規直交族に変換するステップ（１０５）
により正規直交基底に変換させられる、請求項１に記載のコンピュータプログラム。
【請求項３】
前記方法において、
自由族を直交族に変換するステップ（１０４）が、グラム−シュミット直交化アルゴリズムを使用することにより実現される、請求項２に記載のコンピュータプログラム。
【請求項４】
前記方法において、
索引が、少なくとも、
・索引内のキーワードの数のサイズの正規直交基底を生成するステップ、
・正規直交基底の１つのベクトルを、任意の１対１関数によって索引の各々のキーワードに関連付けるステップ
により正規直交基底に変換させられる、請求項１に記載のコンピュータプログラム。
【請求項５】
前記方法において、
文書の１つに関連付けられる合成ベクトルが、文書を特徴付けるすべてのキーワードに対応するすべてのベクトルを線形結合することにより、文書の暗号化の前に決定される（１０７）、請求項１から４のいずれか一項に記載のコンピュータプログラム。
【請求項６】
前記方法において、
検索クエリが検索キーワードを含み、各々のキーワードが、１つの否定演算子または１つの肯定演算子に関連付けられ、検索クエリを、いくつかの行を含むクエリ行列に変換するステップ（１１０）が、以下のステップ、すなわち、
−  クエリを選言標準形で、すなわち、連言節の選言として表現するステップ、
−  各々の連言節で、肯定演算子に関連付けられるキーワードを、否定演算子に関連付けられるものから分離するステップ、
−  各々の連言節で、
○肯定演算子に関連付けられる各々の検索キーワードを、正規直交基底のスパン内の「肯定ベクトル」と呼ばれるベクトルに、
○否定演算子に関連付けられる各々の検索キーワードを、正規直交基底のスパン内の「否定ベクトル」と呼ばれるベクトルに、
変換するステップ、
−  クエリ行列の各々の行が１つの連言節に対応し、各々の行が肯定ベクトルおよび否定ベクトルに基づくベクトルである行列として検索クエリを決定するステップであって、各々の行が、肯定ベクトルが集められる第１の和、および、否定ベクトルが集められる第２の和を含む、決定するステップ
を含む、請求項１から５のいずれか一項に記載のコンピュータプログラム。
【請求項７】
前記方法において、
各々のキーワードと、正規直交基底の各々のベクトルとの間の対応関係が、第１の秘密変換テーブルに格納される、請求項１から６のいずれか一項に記載のコンピュータプログラム。
【請求項８】
前記方法において、
肯定演算子に関連付けられる各々の検索キーワードを、正規直交基底の肯定ベクトルに、否定演算子に関連付けられる各々の検索キーワードを、正規直交基底の否定ベクトルに、それぞれ変換するステップが、第１の秘密変換テーブルに格納される対応関係を提供するステップを含む、請求項６および７に記載のコンピュータプログラム。
【請求項９】
前記方法において、
クエリ行列の各々の行が、すべての文書に付加されている共通キーワードに対応する共通ベクトルをさらに含む、請求項６から８のいずれか一項に記載のコンピュータプログラム。
【請求項１０】
前記方法において、
クエリ行列と、所与の合成ベクトルとの間の乗算の結果が、少なくとも１つの行で１である場合、前記方法が、所望された合成ベクトルの１つとしてクエリアにその合成ベクトルを送信するステップを含む、請求項１から９のいずれか一項に記載のコンピュータプログラム。
【請求項１１】
前記方法において、
文書の各々と合成ベクトルの各々との間の関連付けが、第２の秘密変換テーブルに格納される、請求項１０に記載のコンピュータプログラム。
【請求項１２】
前記方法が、
どの文書が、所望された合成ベクトルに関連付けられるかを、第２の秘密変換テーブルで識別するステップをさらに含む、請求項１０および１１に記載のコンピュータプログラム。
【請求項１３】
前記方法において、
クエリ行列と、すべての合成ベクトルとの間の乗算の結果が、すべての行で１と異なる場合、前記方法が、暗号化された文書のどれも検索クエリとマッチングしないということをクエリアに送信するステップを含む、請求項１から１２のいずれか一項に記載のコンピュータプログラム。
【請求項１４】
請求項１から１３のいずれか一項に記載のコンピュータプログラムを記憶した、コンピュータ可読媒体（７）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化された文書についてのセキュアなブール検索を実行するための方法およびシステムに関する。
【背景技術】
【０００２】
多くのクラウドサービスの価値は、クライアントのデータに関して演算する能力にある。典型的な例は、データストレージ、ウェブメールサービス、広告、ジオロケーションサービス等を含む。しかしながら、クライアントのデータ、例えばファイル、電子メール、ロケーションにアクセスする必要性は、クライアントのデータの機密性の必要性と調和しないことが多く、その機密性の必要性は、そのクライアントのデータを保護するために暗号化を必要とするものである。これらの矛盾する要件を調停し、暗号化されたデータに関する計算を実現することは、重要な研究および工学の問題である。
【０００３】
ここでは、文書に関する索引作成および検索という特定の場合に重点を置く。典型的には文書のセットに関する検索を実行するために、文書に含まれるキーワードの索引を作成し、後で索引に関する検索を実行する。このことは、検索を要求するものと定義されるクエリア（ｑｕｅｒｉｅｒ）、ならびに、文書および索引を格納するものと定義され、実際に検索を実行し結果を返すストレージプロバイダが、相互に完全に信頼しているならば、重大な問題を引き起こさない。難点は、クエリアが、そのデータの機密性を保護し、暗号化された文書および索引を格納し、暗号化されたクエリをさらに送信することを所望するときに生起する。その場合、暗号化された文書の集合体に関する、暗号化された検索を実行することが可能であることが有利となる。そしてより正確には、連言、選言、および否定の検索などの任意のブール検索を含む、暗号化された文書の集合体に関する、すべての種類の暗号化された検索を実行することが可能であることが有利となる。
【０００４】
「選言検索」により本願では、ユーザが、単語１または単語２…または単語ｎを含む暗号化された文書を検索することを可能にする検索を意味する。「連言検索」により本願では、ユーザが、「単語１および単語２…および単語ｎ」を含む暗号化された文書を検索することを可能にする検索を意味する。「否定検索」により本願では、１つまたはいくつかの特定の単語を含まないすべての暗号化された文書を検索することを可能にする検索を意味する。
【０００５】
現在、暗号化されたデータに関するブール検索、すなわち、連言、選言、および否定の検索オプションを同時に実行することを可能にする解決策は存在しない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
したがって解決すべき技術的問題は、暗号化された文書に関する任意の種類のブール検索、すなわち、同時での連言、選言、および否定の検索オプションを実行することを可能にする方法を提供することである。
【課題を解決するための手段】
【０００７】
この目的で本発明は、暗号化された文書についてのブール検索を実行するための方法であって、各々の文書が、キーワードのセットにより特徴付けられ、すべての文書を特徴付けるすべてのキーワードが、索引を形成し、索引が、索引の各々のキーワードが正規直交基底の唯一無二のベクトルに対応するように、正規直交基底に変換させられ、各々の文書が、正規直交基底のスパン内の合成ベクトルに関連付けられ、合成ベクトルが、暗号化された検索サーバに格納されているすべての文書に対応する、方法が、以下のステップ、すなわち：
−  クエリアから検索クエリを受信するステップ、
−  検索クエリを１つのクエリ行列に変換するステップ、
−  クエリ行列と合成ベクトルの各々との間の乗算の結果に基づいて全体的な結果を決定するステップ
を含む、方法に関する。
【０００８】
本発明による手法は、次いで、索引内のキーワードをベクトルと考えること、および、それらのベクトルが独立ベクトルの族を形成するようにそれらのキーワードのパディングを行うことである。そのような族から本願では、結果として得られるベクトル空間の正規直交基底を構築するものであり、そのことは、索引内の各々のキーワードがこの正規直交基の１つのベクトルに関連付けられるということを意味する。次いで各々の文書に対して本願では、文書を特徴付けるキーワードを表すすべてのベクトルの線形結合からの結果として得られる合成ベクトルを関連付ける。
【０００９】
クエリは、次いで、同じ正規直交基底を使用する同じベクトル空間内のいくつかの行を含む行列として表現され、本願では、クエリ行列の各々の行と、文書に対応する合成ベクトルとの間のスカラ積を使用して、その文書が検索クエリを満たすか否かを決める。
【００１０】
したがって、この方法は単に、正規直交基底のベクトルを使用して検索を実現するので、文書は、暗号化された、および秘密の状態のままであることが可能である。キーワードと、対応するベクトルとの間のこの関連付けは、ベクトルのみを観察することによっては、何が対応するキーワードであるかは分かり得ないものであり、正規直交基底のすべてのベクトルを知ることによってでも、過程を逆にし、キーワードを知得することが可能ではないという意味で秘密である。ある意味でこのことは、キーワード索引の暗号化の特定のタイプとみなされ得る。
【００１１】
本発明の１つの実施形態によれば、索引は、少なくとも：
−  索引を自由族に変換するステップ、
−  自由族を直交族に変換するステップ、
−  直交族を、正規直交基底を形成する正規直交族に変換するステップ
により正規直交基底に変換させられる。
【００１２】
実際のところ本発明によれば、第１のステップは正規直交基底の構築である。この第１のステップは、文書の暗号化の前に行われる。その目的で、文書所有者は文書の集合体を有する。その所有者は、最初にこれらの文書から索引を生成し、この索引が、合成ベクトルを作成するために、および、検索を実行するために使用されることになる。索引は、文書からのキーワード、または、例えばタグのような、これらの文書を記述するキーワードを選択することにある。索引は、すべての文書に関連付けられるすべてのキーワードを含むものであり、１つの文書に対してだけではない。次いでこの索引から、正規直交基底が生成される。最終的に大切であることは、索引内の各々のキーワードに対して、正規直交基底の唯一無二のベクトルが対応するということである。
【００１３】
本発明の好ましい実施形態によれば、自由族を直交族に変換するステップは、グラム−シュミット直交化アルゴリズムを使用することにより実現される。
【００１４】
本発明の別の実施形態によれば、索引は、少なくとも：
・索引内のキーワードの数のサイズの正規直交基底を生成するステップ、
・正規直交基底の１つのベクトルを、任意の１対１関数によって索引の各々のキーワードに関連付けるステップ
により正規直交基底に変換させられる。
【００１５】
索引が正規直交基底に変換されると、正規直交基底のスパンからの合成ベクトルが、各々の文書に関連付けられ得る。
【００１６】
文書の１つに関連付けられる合成ベクトルは、文書を特徴付けるすべてのキーワードに対応するすべてのベクトルを加算することにより、文書の暗号化の前に決定され得る。
【００１７】
その後で各々の文書は、秘密鍵を使用することにより暗号化され得る。暗号化アルゴリズムは、高度暗号化標準などの任意の標準的なものであり得る。所有者は次いで、鍵を秘密に維持することが可能である。
【００１８】
これらの動作を遂行した後で、所有者は、暗号化された文書の格納を外部委託することが可能であり、その所有者は、暗号化された文書をストレージプロバイダに送信し、対応するベクトルを暗号化された検索サーバに送信することが可能である。実際上は同じエンティティが、ストレージプロバイダの役割、および暗号化された検索サーバの役割の両方を果たすことが可能であり、または、それらは別々のエンティティであり得る。同じエンティティが両方の役割を果たす場合、合成ベクトルと文書との間の関連付けはこのエンティティにより知られており、一方で、役割が２つの別個のエンティティにより果たされる場合、合成ベクトルと文書との間のこの対応関係は、それらのエンティティのいずれにも知られないものであり、所有者により秘密変換テーブルに格納されるべきものである。
【００１９】
このセットアップ段階が終わると、クエリ段階が開始し得る。そのクエリ段階は、合成ベクトルを使用するのみである。結果的に、暗号化された文書は、これ以上は必要とされない。
【００２０】
本発明の１つの実施形態によれば、検索クエリは検索キーワードを含み、各々の検索キーワードは、１つの否定演算子または１つの肯定演算子に関連付けられ、検索クエリを、いくつかの行を含むクエリ行列に変換するステップが、以下のステップ、すなわち：
−  クエリを選言標準形で、すなわち、連言節の選言として表現するステップ、
−  各々の連言節で、肯定演算子に関連付けられるキーワードを、否定演算子に関連付けられるものから分離するステップ、
−  各々の連言節で：
○肯定演算子に関連付けられる各々の検索キーワードを、正規直交基底のスパン内の「肯定ベクトル」と呼ばれるベクトルに、
○否定演算子に関連付けられる各々の検索キーワードを、正規直交基底のスパン内の「否定ベクトル」と呼ばれるベクトルに、
変換するステップ、
−  各々の行が１つの連言節に対応し、各々の行が肯定ベクトルおよび否定ベクトルに基づくベクトルである行列として検索クエリを決定するステップであって、各々の行が、肯定ベクトルが集められる第１の和、および、否定ベクトルが集められる第２の和を含む、決定するステップ
を含む。
【００２１】
その文書内で、本願では「肯定演算子」を、ブール検索表現式内の否定「ｎｏｔ」を伴わないキーワードとみなし、本願では「否定演算子」を、ブール検索表現式内の演算子「ｎｏｔ」が前に置かれるキーワードとみなす。
【００２２】
各々のキーワードと、正規直交基底の各々のベクトルとの間の対応関係は、好ましくは、第１の秘密変換テーブルに格納される。
【００２３】
結果的に、肯定演算子に関連付けられる各々の検索キーワードを、正規直交基底の肯定ベクトルに、否定演算子に関連付けられる各々の検索キーワードを、正規直交基底の否定ベクトルに、それぞれ変換するステップは、好ましくは、第１の秘密変換テーブルに格納される対応関係を提供するステップを含む。
【００２４】
実際のところクエリは、所有者自体、または別のエンティティであり得るクエリアにより遂行される。所有者がクエリアであるならば、その所有者は、検索キーワードをベクトルに変換するためのすべての必要とされる情報をすでに有している。他の場合ではクエリアは、所有者から何らかの情報を得る必要がある。
【００２５】
クエリを遂行するために、クエリアは確かに、クエリ行列を計算する必要があり、この限りでそのクエリアは、キーワードと正規直交基底のベクトルとの間の対応関係を知る必要がある。クエリアが所有者とは別個である場合では、動作の２つのモード：
ａ／所有者が、クエリアに、第１の秘密変換テーブル、すなわち、索引、およびベクトルとの対応関係を直接提供し、次いでクエリアが、そのクエリア自体で任意のクエリを遂行することが可能であるということ、
ｂ／または、所有者は、クエリアにこの情報を提供するのではなく、代わりに、その所有者にクエリを平文で送信するようにクエリアに要求し、所有者が、そのクエリを適切な行列として表現するということ、のいずれかが存在する。このことは、所有者に追加的な計算を負わせるが、クエリア、およびクエリの内容に応じて、その所有者が可能にすることを所望するクエリがどれかを正確に決める能力をその所有者に提供する。
【００２６】
ｃ／媒介者の解決策は、所有者が、信頼される媒介者に対応関係を提供し、その媒介者が、所有者によりその媒介者に提供されるポリシーによって変換を遂行するということである。
【００２７】
クエリがベクトルによって表現されると、クエリアは、暗号化された検索サーバにクエリ行列を送信する。あるいは場合ｂ／またはｃ／では、所有者または信頼される媒介者が、暗号化された検索サーバにクエリ行列を送信し、クエリアには最終的な結果を送信するだけであるということが、可能性としてある。
【００２８】
本発明の１つの実施形態によれば、クエリ行列の各々の行は、すべての文書に付加されている共通キーワードに対応する共通ベクトルをさらに含む。この共通ベクトルの付加によって、検索クエリ内に否定演算子を伴うキーワードのみが存在する場合に対処することが可能になる。
【００２９】
クエリとマッチングする何らかの文書が存在するかどうかを知るために、行列として表現される検索クエリと、文書の各々に対応する合成ベクトルとの間の乗算が遂行される。
【００３０】
各々の文書に対して、クエリ行列と、関連付けられた合成ベクトルとの間の行列乗算の結果が、すべての行で１と異なる場合、文書は検索クエリとマッチングしない。このことがすべての文書に対して当てはまるならば、そのことは、要求とマッチングする文書がないということを意味し、結果的に方法は、暗号化された文書のどれも検索クエリとマッチングしないということを、全体的な結果としてクエリアに送信するステップを含む。
【００３１】
文書に対して、クエリ行列と、対応する合成ベクトルとの間の乗算の結果が、少なくとも１つの行で１である場合、合成ベクトルに対応する文書は検索クエリとマッチングし、結果的に方法は、マッチングする合成ベクトルの１つとしてクエリアにその合成ベクトルを送信するステップを含む。
【００３２】
次いで、暗号化された検索サーバおよびストレージプロバイダが同じエンティティであるか否かに応じて、２つの場合：
−  それらが同じエンティティであるならば、そのエンティティは、クエリに対応する格納された文書がどれであるかを知っており、それらは、結果としてクエリアに暗号化された文書を直接送信するということ、
−  それらが２つの別々のエンティティであるならば、暗号化された検索サーバは、クエリアに、検索クエリとマッチングする文書の合成ベクトルを送信することのみが可能であるということ、とが存在する。クエリアは次いで、この（これらの）合成ベクトルを対応する文書とマッチングする必要がある。本発明の１つの実施形態によれば、文書の各々と合成ベクトルの各々との間の関連付けは、第２の秘密変換テーブルに格納される。その場合では方法は、どの文書が、識別された合成ベクトルに関連付けられるかを、第２の秘密変換テーブルで識別するステップを含む。別の可能性は、この対応関係は所有者により知られており、そのため、クエリアが所有者とは別個である場合では、そのクエリアは、この情報もまた取り込む必要があるということである。次いで、上記で提示された場合ａ、ｂ、およびｃと同様の３つの可能性：
○所有者が、クエリアに情報を提供し、そのクエリアが次いで、ストレージプロバイダに所与の文書を直接要求するということ、
○または、所有者が、ストレージプロバイダに文書を要求し、次いで、クエリアにこれらの文書を転送する（ただし、クエリアに対応関係は提供しない）ということ、
○または、第三者が、合成ベクトルと文書との間の対応関係を作製することを担当し、ストレージプロバイダに文書を要求し、クエリアにそれらの文書を転送するということのいずれか
が存在する。
【００３３】
この時点でクエリアは、そのクエリアの検索クエリに対応する暗号化された文書を有する。それらの文書を復号するために、そのクエリアは、文書を暗号化するために所有者により使用された秘密鍵を必要とする。そのためやはり、上記で提示された場合ａ、ｂ、およびｃと同様の３つの場合：
−  所有者が、クエリアに鍵を直接提供するということ、
−  または、クエリアが、所有者に暗号化された文書を送信しなければならず、その所有者が次いで、それらの文書を復号し、クエリアに平文の文書を送信するということ、
−  または、所有者が、信頼される媒介者に鍵を与え、その媒介者が、所有者によりその媒介者に提供されるポリシーによって文書を復号することを担当するということのいずれか
が存在する。
【００３４】
本発明の別の態様は、本発明の第１の態様による方法を実現することを可能にするプログラムコードが符号化される、コンピュータ可読媒体に関わるものである。
【図面の簡単な説明】
【００３５】
【図１】本発明の１つの実施形態による方法をセットアップするためのシステムを表す図である。
【図２】本発明の１つの実施形態による検索の方法を実装するシステムを表す図である。
【図３】本発明の１つの実施形態による方法のステップを表す図である。
【発明を実施するための形態】
【００３６】
次に本発明が、付随する図面を参照して説明される。図面は、本発明がどのように実装され得るかの１つの例を提供することが意図されるものであり、本発明の適用可能性を限定することは意図されない。
【００３７】
図１に表されるように、方法はまず初期化段階１０１を含む。その初期化段階１０１の目標は、正規直交基底の作成である。
【００３８】
その目的で文書所有者は、その所有者が暗号化することを所望する文書ＤｉのセットＤを有する。初期化段階１０１の第１のステップ１０２は、文書Ｄｉに基づく索引Ｗの作成である。この索引Ｗは、キーワードのすべてのセットを含み、キーワードの各々のセットは、文書Ｄｉの各々を記述するために選択されるキーワードｗｋを含む。その実施形態ではキーワードは、バイナリコードで表現される。１つの文書Ｄｉを記述するために選択されるキーワードは、例えば、文書に含まれる何らかの単語であり得るものであり、またはそれらのキーワードは、例えばタグなどの、文書を記述する何らかの単語であり得る。各々の文書Ｄｉは、１つまたはいくつかのキーワードにより記述され得る。さらに、すべての文書のキーワードのセットに、同じ共通キーワードＪを付加することが有利である。共通キーワードＪによって、検索クエリ内の選言節内に否定単語のみを有するときなどの、いくつかの個別の場合に対処することが可能になる。
【００３９】
初期化段階１０１は、次いで、索引を正規直交基底に変換させるステップ１０６を含む。
【００４０】
索引を正規直交基底に変換させるそのステップ１０６は、まず、索引を、自由族（ｆｉ）ｉ∈｛０，ｌ｝、すなわち、この索引から独立ベクトルの族に変換するステップ１０３を含む。その目的で本願では、索引のどのキーワードが最大の長さｍを呈するかを識別し、次いで本願では、索引のすべてのキーワードが同じ長さｍを有するように、０を追加することにより、すべてのキーワードのパディングを行う。その段で自由族は、したがって自由キーワードを含む。自由キーワードは順序付けされる。
【００４１】
索引を正規直交基底に変換させるそのステップ１０６は、次いで、自由族（ｆｉ）ｉ∈｛０，ｌ｝を、直交族（ｏｉ）ｉ∈｛０，ｌ｝に変換するステップ１０４を含む。その目的で本願では、下記で解説されるようなグラム−シュミット直交化手順を使用する。
【００４２】
グラム−シュミットの定理によれば、
（ｆｉ）ｉ∈｛０，ｌ｝が前ヒルベルト空間の自由族であるならば：
【００４３】
【数１】
0006035421.tif 000002
であり、
・Ｖｅｃｔ（ｆ１，…，ｆｌ）＝Ｖｅｃｔ（ｏ１，…，ｏｌ）であり、
・スカラ積
【００４４】
【数２】
0006035421.tif 000003
が狭義に正である、
ような直交族（ｏｉ）ｉ∈｛０，ｌ｝が存在する。
【００４５】
結果的に、本願で、順序付けされた自由族（ｆｉ）ｉ∈｛０，ｌ｝を考える場合、グラム−シュミットの定理によれば、本願では次式のようにグラム−シュミットアルゴリズムにしたがって構築することが可能である、一意的な直交族（ｏｉ）ｉ∈｛０，ｌ｝が存在する。
【００４６】
【数３】
0006035421.tif 000004
【００４７】
ただし、
【００４８】
【数４】
0006035421.tif 000005
は、ｏｋにより導かれるベクトル線上の直交射影として定義され、すなわち次式となる。
【００４９】
【数５】
0006035421.tif 000006
【００５０】
（ｏｉ）ｉ∈｛０，ｌ｝は、新しい直交族を形成し、次式が確かめられる。
【００５１】
【数６】
0006035421.tif 000007
【００５２】
この段階で直交族は、本願で直交キーワードと呼ぶものを含む。
【００５３】
索引を正規直交基底に変換させるそのステップ１０６は、次いで、直交族を、正規直交基底を形成する正規直交族に変換するステップ１０５を含む。そのことを行うために本願では、直交族の各々の直交キーワードを、以下のように正規直交にすることになる。
【００５４】
【数７】
0006035421.tif 000008
【００５５】
ｕｋは、正規直交基底のベクトル、または正規直交キーワードとも呼ばれる。
【００５６】
この段階の終わりで、本願では、各々のキーワードｗｋが唯一無二の直交キーワードｕｋに対応するということを指摘しておくべきである。加えて、自由族（ｆｉ）ｉ∈｛０，ｌ｝が順序付けされるという事実は、グラムシュミットアルゴリズムによる構築が一意的であるということを含意する。本願でキーワードの順序を変更する場合、アルゴリズムは異なる正規直交キーワードを出力する。実際、順序は、秘密に維持されるべきである本願での構築の秘密を表す。
【００５７】
索引を正規直交基底に変換させるステップ１０６を遂行する異なる方途は、索引内のキーワードの数のサイズの正規直交基底を生成すること、および次いで、各々の正規直交ベクトルを、任意の１対１関数によって、または、第１の変換テーブルにこの対応関係を格納することにより、１つのキーワードに関連付けることであり得る。
【００５８】
そのステップ１０６の終わりで、正規直交基底の各々のベクトルは、索引の唯一無二のキーワードに対応する。キーワードとベクトルとの間の対応関係は、文書の所有者により、または信頼されるエンティティにより所有され得る、第１の変換テーブルに格納され得る。
【００５９】
初期化段階１０１は、次いで、正規直交基底のスパン内の合成ベクトルχｉを各々の文書Ｄｉに関連付けるステップ１０７を含む。その合成ベクトルχｉは、何が文書Ｄｉに関連付けられたキーワードであるかを表現する。
【００６０】
そのことを行うために、文書の所有者は、擬似ランダム関数ｆ：｛０，１｝ｓ×｛０，１｝ｎ→｛０，１｝ｅを選定することが可能である。ステップ１０６の後で、セットＤ内の各々の文書Ｄｉは、一意的な正規直交キーワード（ｕｋ）ｋ∈ＭｉのセットＭｉに関連付けられるものであり、ただしＭｉは、したがって、Ｄｉを記述するために使用されるキーワードｗｋに対応するベクトルｕｋのセットである。各々の文書Ｄｉに対する合成ベクトルχｉは、次いで、文書を特徴付けるすべてのキーワードに対応するすべてのベクトル、および秘密係数を線形結合することにより計算される。
【００６１】
【数８】
0006035421.tif 000009
【００６２】
文書Ｄｉと合成ベクトルχｉとの間の対応関係は、第２の秘密変換テーブルに格納され得る。その第２の秘密変換テーブルは、文書の所有者により、または信頼されるエンティティにより所有され得る。
【００６３】
初期化段階１０１はここに終わり、文書は暗号化され得る。本発明の別の実施形態によれば、文書は、ステップ１０２の直後に暗号化されている場合もあり、その期間に、文書を特徴付けるキーワードのセットを各々の文書に対して選択している。
【００６４】
各々の文書が、次いで、暗号化１０８のステップの間に秘密鍵４によって暗号化される。暗号化アルゴリズムは、任意の標準的なものであり得るものであり、所有者は鍵４を秘密に維持する。
【００６５】
これらの動作を遂行した後で、所有者は、文書Ｄｉの格納を外部委託することが可能であり、その所有者は、暗号化された文書をストレージプロバイダ６に送信し、合成ベクトルχｉを暗号化された検索サーバ７に送信する。本発明による方法は、暗号化された検索サーバ７が、暗号化された文書をオープンすることなく合成ベクトルχｉによってだけで検索を実行することが可能であるので、特に有利である。
【００６６】
本発明によるクエリ段階１０９が、次に、図２を参照して説明される。
【００６７】
クエリ段階は、クエリアから検索クエリを受信するステップ１１６によって始まる。その検索クエリは、選言標準形で表現されるブール検索である。
【００６８】
クエリ段階は、検索クエリを正規直交基底の１つのクエリ行列に変換するステップ１１０を含む。検索クエリをクエリ行列に変換させるために、検索クエリのキーワードは、正規直交基底のベクトルに変換させられなければならない。クエリ行列の各々の行は、得られたベクトルの線形結合である。
【００６９】
そのため例えば、クエリアが以下の検索クエリを送信すると想定する：
【００７０】
【数９】
0006035421.tif 000010
【００７１】
ただし記号○は、本願では、否定演算子「ｎｏｔ」を伴う、または伴わないキーワードを有し得るということを意味する。
【００７２】
各々の
【００７３】
【数１０】
0006035421.tif 000011
に対して、ｐｊを、Ｌｉ内の肯定演算子に関連付けられるキーワードの数とし、ｎｊを、Ｌｉ内の肯定演算子に関連付けられるキーワードの数とする。各々のｉに対して、および、肯定演算子に関連付けられる検索クエリの各々のキーワードに対して、定数ａｊが、
【００７４】
【数１１】
0006035421.tif 000012
であるように一様ランダムに生成され、一方で、否定演算子に関連付けられる検索クエリの各々のキーワードに対して、定数ａｊ’が、
【００７５】
【数１２】
0006035421.tif 000013
であるように一様ランダムに生成される。すべての文書に付加される共通キーワードに対して、定数ａが、
【００７６】
【数１３】
0006035421.tif 000014
であるように生成される。
【００７７】
クエリ行列の第ｊの行を得るために本願では、検索クエリの第ｊの連言節のキーワードに対応するすべての検索ベクトルを線形結合する。効率のために本願では、肯定演算子に関連付けられるキーワードに対応するベクトルを第１の和に、および、否定演算子に関連付けられるキーワードに対応するベクトルを第２の和に、一体に集める。さらに、共通キーワードに対応するベクトルが、第１および第２の和に関してさらに分離される。
【００７８】
結果的に本願では、以下のクエリ行列「クエリ」を得る。
【００７９】
【数１４】
0006035421.tif 000015
【００８０】
ただし
【００８１】
【数１５】
0006035421.tif 000016
である。
【００８２】
結果的に、クエリ行列の第ｊの行は、３つの異なる部分：
−  否定演算子に関連付けられる検索クエリのキーワードに対応する
【００８３】
【数１６】
0006035421.tif 000017
、
−  肯定演算子に関連付けられる検索クエリのキーワードに対応する
【００８４】
【数１７】
0006035421.tif 000018
、
−  共通キーワードに対応する
【００８５】
【数１８】
0006035421.tif 000019
で表現される。
【００８６】
定数ａ、ａ’ｊ、およびａｊはランダムに生成されるものであり、そのため、同じ検索クエリが何回か遂行される場合でも、定数ａ、ａｊ’、およびａｊは、検索クエリごとに異なることになる。したがって、クエリ行列を復号して、検索クエリで使用されるキーワードを得ることは可能でないので、方法は非常にセキュアである。
【００８７】
クエリ段階１０８は、次いで、クエリ行列の各々の行と合成ベクトルとの間のスカラ乗算の結果に基づいて全体的な結果を決定するステップ１１１を含む。そのステップ１１１の目標は、暗号化された文書の１つが検索クエリとマッチングするかどうかを知ることである。
【００８８】
各々の文書に対して、クエリ行列と、文書に対応する合成ベクトルとの間の乗算が遂行される。
【００８９】
【数１９】
0006035421.tif 000020
【００９０】
クエリ行列と、所与の文書の合成ベクトルとの間の乗算の結果が、すべての行で１と異なる場合、前記文書は検索クエリとマッチングしない。
【００９１】
クエリ行列と、所与の文書の合成ベクトルとの間の乗算の結果が、少なくとも１つの行で１である場合、前記文書は検索クエリとマッチングし、本願では、結果として得られるベクトルを、対応する合成ベクトルのリストに含める。
【００９２】
方法は、次いで、クエリアに結果を送信するステップ１１２を含む。その結果は、第１の場合では、文書のどれも検索クエリとマッチングしないということであり得るものであり、または結果は、第２の場合では所望された合成ベクトルであり得る。
【００９３】
方法は、次いで、所望された合成ベクトルに対応する文書を索出するステップを含み得る。そのことを行うために方法は、どの文書が、所望された合成ベクトルに関連付けられるかを、第２の秘密変換テーブルで識別するステップ１１３を含み得る。
【００９４】
方法は、次いで、クエリアにその暗号化された文書を送信するステップ１１４を含み得る。この時点でクエリアは、そのクエリアのクエリに対応する暗号化された文書を有する。それらの文書を復号するために、そのクエリアは、所有者により使用された秘密鍵を必要とする。そのためやはり、３つの場合：
−  所有者が、クエリアに鍵を直接提供するということ、
−  または、クエリアが、所有者に暗号化された文書を送信しなければならず、その所有者が次いで、それらの文書を復号し、クエリアに平文の文書を送信するということ、
−  または、所有者が、信頼される媒介者に鍵を与え、その媒介者が、所有者によりその媒介者に提供されるポリシーによって文書を復号することを担当するということのいずれか
が存在する。
【００９５】
本発明は、好ましい実施形態を参照して詳細に説明されたが、形式および細部においての変更および修正が、本発明の範囲から逸脱することなく行われ得るということが、当業者には容易に明らかになるはずである。
【図１】
0006035421.tif 000021
【図２】
0006035421.tif 000022
【図３】
0006035421.tif 000023