(57)【要約】  ツリー形式により構成されるプロテクトされたデータのクエリ方法及び装置。対象となるノードからスタートするツリーのブランチにおいて出現するノード名に割り当てられた識別子に等しい入力に対しては、各ノードポリノミアルはゼロと評価するように、対応するノードポリノミアルのツリーが構成される。ノードポリノミアルのツリーの各ポリノミアルが、ブラインドポリノミアルのツリーにおける対応するポリノミアルと差分ポリノミアルのツリーにおける対応するポリノミアルとの和に等しくなるように、対応するブラインドポリノミアルのツリーと差分ポリノミアルのツリーとが構成される。ブラインドツリーはクライアントに、差分ツリーはサーバに与えられる。クライアントとサーバの評価結果を組み合わせることによって、与えられたクエリに該当するノードを特定することが可能である。
2008501175.tif 000002
【特許請求の範囲】
【請求項１】
プロテクトされたデータのクエリを可能にするコンピュータにより実現される方法であって、
前記データは、各自のノード名を有するノードを有するツリーとして構成され、各ノード名には一意的な識別子が割り当てられており、
当該方法は、
対象となるノードからスタートするツリーのブランチにおいて出現するノード名に割り当てられた識別子に等しい入力に対しては、各ノードポリノミアルはゼロと評価するように、前記データが構成されるツリーに構成上対応するノードポリノミアルのツリーを構成するステップと、
前記ノードポリノミアルのツリーの各ポリノミアルが、ブラインドポリノミアルのツリーにおける対応するポリノミアルと差分ポリノミアルのツリーにおける対応するポリノミアルとの和に等しくなるように、前記データが構成されるツリーに双方構成上対応する前記ブラインドポリノミアルのツリーと前記差分ポリノミアルのツリーとを構成するステップと、
前記ブラインドポリノミアルのツリーと前記差分ポリノミアルのツリーとの１つをサーバシステムに利用可能にし、他方をクライアント装置に利用可能にするステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、さらに、
前記一意的な識別子に等しいｘに対してゼロに評価するｘの識別ポリノミアルを各ノード名に割り当てるステップを有することを特徴とする方法。
【請求項３】
請求項２記載の方法であって、
前記識別ポリノミアルは、第１次ポリノミアルであることを特徴とする方法。
【請求項４】
請求項２又は３記載の方法であって、さらに、
前記ツリーの各ノードに対して、該ノードがリーフノードである場合、前記ノードポリノミアルは前記ノードの識別ポリノミアルに等しく、そうでない場合、前記ノードポリノミアルは、前記ノードの識別ポリノミアルと前記ノードのチャイルドノードのノードポリノミアルとの積に等しいように、前記ノードポリノミアルのツリーを構成するステップを有することを特徴とする方法。
【請求項５】
請求項１記載の方法であって、
前記ブラインドポリノミアルのツリーは、前記クラインと装置に利用可能にされ、
前記差分ポリノミアルのツリーは、前記サーバシステムに利用可能にされる、
ことを特徴とする方法。
【請求項６】
請求項１記載の方法であって、
前記ブラインドポリノミアルのツリーは、該ブラインドポリノミアルの係数を（擬似）ランダムに選択することによって構成されることを特徴とする方法。
【請求項７】
請求項５又は６記載の方法であって、
前記ブラインドポリノミアルのツリーは、該ブラインドポリノミアルの係数が生成された擬似乱数生成装置を初期化するのに使用されるシードを前記クラインと装置に利用可能にすることによって、前記クラインと装置に利用可能にされることを特徴とする方法。
【請求項８】
請求項１記載の方法であって、さらに、
前記ノードポリノミアルのツリーの各ポリノミアルが、前記ブラインドポリノミアルのツリーにおける対応するポリノミアルと前記差分ポリノミアルのツリーにおける対応するポリノミアルとの和に等しくなるように、複数のブラインドポリノミアルを構成するステップと、
前記ブラインドポリノミアルの複数のツリー又は前記差分ポリノミアルの１つを前記サーバシステムに利用可能にし、他方のツリーを各クラインと装置に利用可能にするステップと、
を有することを特徴とする方法。
【請求項９】
請求項１記載の方法であって、さらに、
前記ツリーのデータノードをトライ表現に変換するステップを有し、
これにより、データセグメントの第２キャラクタに続く第１キャラクタが、前記第２キャラクタのチャイルドノードとして表される、
ことを特徴とする方法。
【請求項１０】
プロテクトされたデータのクエリを可能にする装置であって、
前記データは、各自のノード名を有するノードを有するツリーとして構成され、各ノード名には一意的な識別子が割り当てられており、
当該装置は、
対象となるノードからスタートするツリーのブランチにおいて出現するノード名に割り当てられた識別子に等しい入力に対しては、各ノードポリノミアルはゼロと評価するように、前記データが構成されるツリーに構成上対応するノードポリノミアルのツリーを構成する手段と、
前記ノードポリノミアルのツリーの各ポリノミアルが、ブラインドポリノミアルのツリーにおける対応するポリノミアルと差分ポリノミアルのツリーにおける対応するポリノミアルとの和に等しくなるように、前記データが構成されるツリーに双方構成上対応する前記ブラインドポリノミアルのツリーと前記差分ポリノミアルのツリーとを構成する手段と、
前記ブラインドポリノミアルのツリーと前記差分ポリノミアルのツリーとの１つをサーバシステムに利用可能にし、他方をクライアント装置に利用可能にする手段と、
を有することを特徴とする装置。
【請求項１１】
請求項１０記載の装置であって、
当該装置は、前記クライアント装置として動作するよう構成されることを特徴とする装置。
【請求項１２】
プロテクトされたデータに対してサーバをクエリするクライアント装置であって、
前記データは、各自のノード名を有するノードを有するツリーとして構成され、各ノード名には一意的な識別子が割り当てられており、
当該クライアント装置は、
ノード名に対するクエリを受信することに応答して、前記ノード名に割り当てられた一意的な識別子を決定する手段と、
前記決定された識別子に等しい入力に対して、請求項１記載の方法によってサーバシステムに利用可能にされる前記ツリーのポリノミアルを評価するリクエストを前記サーバシステムと通信する手段と、
前記決定された識別子に等しい入力に対して、請求項１記載の方法によって前記クライアント装置に利用可能にされる前記ツリーのポリノミアルを評価する手段と、
前記サーバシステムから受け付けた評価結果と、前記クライアント装置による評価結果との和がゼロに等しいか判断する手段と、
前記決定された和がゼロに等しいものであって、前記ノードのチャイルドノードの和がゼロに等しくならないノードを、前記クエリの回答として返す手段と、
を有することを特徴とするクライアント装置。
【請求項１３】
請求項１２記載のクライアント装置であって、さらに、
あるブランチのポリノミアルの評価を、該ブランチのルートノードの前記サーバシステムによる評価が非ゼロとなる場合、前記サーバシステムに通知する手段を有することを特徴とするクライアント装置。
【請求項１４】
請求項１２記載のクライアント装置であって、さらに、
あるノードに含まれるデータセグメントに対するクエリを、前記データセグメントのトライ表現に対するクエリに先行する前記ノードに対するクエリに変換する手段を有することを特徴とするクライアント装置。
【請求項１５】
請求項１０記載の装置として計算装置が動作することを可能にする命令を有するコンピュータプログラム。
【請求項１６】
請求項１２記載の装置として計算装置が動作することを可能にする命令を有するコンピュータプログラム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
ＸＭＬ構造化文書などのデータをリモートデータベースに格納する必要性が増大している。このようなデータが、例えば、患者情報や（音声）映像コンテンツに対する営業上貴重なメタデータなどの機密情報を含むとき、それはプロテクトされるべきである。通常のアプローチは、データをリモートデータベースに格納する前にデータを暗号化するというものである。そのとき、どのようにクライアント装置が以降においてデータベースをクエリすることができるかという問題が生じる。最も自明な解法は、データベース全体をローカルにダウンロードし、その後にクエリを実行するというものである。もちろん、これはかなり非効率的である。他の選択肢は、データベースサーバに解読キーを提供するというものであるが、これは、データベースサーバシステムやそれを管理する人々に完全な信頼を必要とするため、常に望ましいとは限らない。
【０００２】
従って、この分野における問題は、サーバが暗号化されたデータ、特にＸＭＬ構造化データを効率的にクエリすることを可能にする方法に関する。Ｗ３Ｃは、要素コンテンツが対称キーにより暗号化され、さらにそれが受信者の公開キーにより暗号化される対称キーと公開キーの組み合わせを利用して、ＸＭＬデータの暗号化を可能にするため、「ＸＭＬ暗号化シンタックス」を推奨している。ｈｔｔｐ：／／ｗｗｗ．ｗ３．ｏｒｇ／ＴＲ／ｘｍｌ−ｅｎｃｒｙｐｔｉｏｎ−ｒｅｑにおけるＷ３Ｃノート“ＸＭＬ  Ｅｎｃｒｙｐｔｉｏｎ  Ｒｅｑｕｉｒｅｍｅｎｔｓ”（２００２年３月４日）と、ｈｔｔｐ：／／ｗｗｗ．ｗ３．ｏｒｇ／ＴＲ／ｘｍｌｅｎｃ−ｃｏｒｅ／におけるＷ３Ｃ勧告“ＸＭＬ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｙｎｔａｘ  ａｎｄ  Ｐｒｏｃｅｓｓｉｎｇ”（２００２年１２月１０日）を参照されたい。
【０００３】
クエリは、ＸＭＬデータに対して実行される基本的処理であるため、実行すべき第１ステップは、暗号化されたＸＭＬデータのクエリに関する問題を解決することである。暗号化されたＸＭＬデータを検索する直接的なアプローチは、まず暗号化されたデータを解読し、その後に解読されたＸＭＬデータについて検索を行うというものである。しかしながら、これは必然的に、大量の不要な解読作業を伴い、特に検索されるデータが大きなものであって、検索ターゲットがそのわずかな部分からしか得られないものであるときには、クエリパフォーマンスを大変悪いものにする。
【０００４】
効果的には、本発明は、請求項１記載のプロテクトされたデータのクエリを可能にするコンピュータにより実現される方法及び請求項９記載の対応する装置を提供する。本発明はまた、請求項１１記載のクライアント装置を提供する。
【０００５】
データはツリーにより構成されていると仮定されている。データが構成されるツリーに構造上対応するノードポリノミアル（ｎｏｄｅ  ｐｏｌｙｎｏｍｉａｌ）のツリーが構成される。当該ツリーの各ノードポリノミアルは、対称となるノードからスタートするツリーのブランチに出現するノード名に割り当てられる識別子に等しい入力に対してゼロと評価する。
【０００６】
構成されたツリーは、クライアント部分とサーバ部分に分割される。クライアント部分はランダムに選択され、サーバ部分は元のデータツリーとの差分である。クエリに応答して、クライアントとサーバは共に、各自の部分におけるポリノミアルを評価し、その結果をクエリソース（クライアント自体であるかもしれない）に供給する。これらの結果の何れも、元のデータを再構成するのに十分な情報を含んでいる。従って、当該データはプロテクトされたままである。
【０００７】
クライアント部分とサーバ部分の評価結果を合成することによって、与えられたクエリに該当するノードを特定することが可能である。これらの部分の評価の和は、任意のノード名に対して、当該ノード名の元のノードポリノミアルの評価と同じになる。そして、この評価は、クエリのノード名が当該ノード名のノード名に一致する場合にはゼロとなる。従って、クエリは、サーバが答えを知ることなく回答することが可能である。
【０００８】
一致するノードが検出されると、それらの（暗号化された）コンテンツが、サーバから抽出され、クライアントによって解読することが可能である。
【０００９】
好適な実施例では、ツリーのデータノードは、トライ（ｔｒｉｅ）表現に変換され、これにより、データセグメントの第２キャラクタに続く第１キャラクタは、当該第２キャラクタのチャイルドノードとして表現することが可能となる。これは、暗号化された文書における要素のデータコンテンツの検索を可能にする。
【００１０】
図面を通じて、同様の参照番号は、同様又は対応する特徴を示す。図面に示される特徴のいくつかは、典型的には、ソフトウェアにより実現され、また、ソフトウェアモジュール又はオブジェクトなどのソフトウェアエンティティを表す。
【００１１】
図１は、本発明によるシステムの概略を示す。サーバ１００は、データを有するデータベース１０１を維持し、当該技術分野において周知なように、１以上のクライアント１０２からのクエリに回答するよう構成される。これらのクエリは、インターネットなどのネットワーク１１０を介し受信される。データベース１０１に格納されているデータは、データソースシステム１０３により提供されたものである。このシステム１０３は、クライアント１０２の１つであってもよいが、また独立したシステムであることも可能である。もちろん、当該データは、複数のソースからのものであり、サーバ１００により管理されているものとすることも可能である。
【００１２】
例えば、クライアント１０２は、患者情報が入力される病院内の端末とすることも可能である。このとき、患者情報は、いくつかの理由により、遠隔地にあるデータベース１０１に格納される。患者情報は、プライバシーの点からプロテクトされる必要がある。以降において、クライアント１０２は、以前に入力された患者情報を抽出するため、データベース１０１をクエリするのに利用される。このような場合、データソースシステム１０３は、クライアント１０２との同一である。
【００１３】
他の実施例では、データソースシステム１０３は、映画や音楽などのコンテンツを顧客に利用可能にするコンテンツプロバイダとすることも可能である。さらに、コンテンツプロバイダは、それの顧客が販売するコンテンツのタイトルやアーチストなどのメタデータによりデータベースをクエリすることを可能にする。効率性の点から、プロバイダは、データベースの管理を第三者にアウトソースすることを所望するかもしれない。また、データベースは経済的に大変貴重なものであり、プロバイダは、データベース内のデータをプロテクトする必要がある。
【００１４】
データは、ＸＭＬベース文書の場合など、ツリー状の構成を有していると仮定される。ＸＭＬ文書では、各ノードは、名前とおそらく値を有している。２つのノードの間には複数のパスは存在しない。以下において、異例となるＸＭＬベース文書が示される。それのツリー表現が、図２（ａ）に示されている。
【００１５】
【表１】
2008501175.tif 000003
図２（ａ）において、「ｃｕｓｔｏｍｅｒｓ」要素が、ツリーのルート、すなわち、最上位ノードとなっていることを確認することができる。その下に「ｃｌｉｅｎｔ」と名付けられた２つのノードが存在し、当該ノードはそれぞれ「ｎａｍｅ」と名付けられた「チャイルド」ノードを有する。「ｎａｍｅ」というノードはリーフノードであり、すなわち、それらはチャイルドノードを有しない。
【００１６】
このデータはまた、電子メールメッセージなどのフラットテキストファイルの検索を可能にするインデックス構成とすることも可能である。非構造化データは、ツリー状に構成されたフォーマットにまず変換可能である。
【００１７】
データを復元するのに十分な情報がサーバ１００に存在しないように、データをプロテクトすることが望ましい。従って、データソースシステム１０３は、以下のようにプロテクトされた形式によりデータを供給する。
【００１８】
各ノード名には、まず識別子と、当該ノード名の識別子に等しいｘに対してはゼロと評価する対応する識別ポリノミアルｉ（ｘ）が割り当てられる。ノード名から識別子への一例となるマッピングが、テーブル１において示される。各名前に対して、これらの識別子は一意的なものとなるべきである。それらは、（擬似）ランダムに選択され、あるいは、オペレータなどによって割り当てることも可能である。このマッピングによって、識別ポリノミアルｉ（ｘ）を構成することが可能である。好ましくは、識別ポリノミアルは、必ずしも必要ではないが、第１次ポリノミアル（ｆｉｒｓｔ−ｄｅｇｒｅｅ  ｐｏｌｙｎｏｍｉａｌ）である。第１次ポリノミアルは、ちょうど１つの入力に対してのみゼロと評価する。より高い次数のポリノミアルを使用することは、回答が正しいものを検出するためフィルタリングされる必要があることを意味する。
【００１９】
本明細書を通じて使用される実施例において使用されるシンプルな構成は、ｉ（ｘ）＝ｘ−ｎの形式のポリノミアルを使用するものである。ただし、ｎはノード名に割り当てられた識別子に等しい。
【００２０】
ノード名自体をサーバ１００から秘密に維持することが望ましい場合、ノード名から識別子へのマッピングはもちろん、サーバ１００に提供されるべきではない。サーバ１００は、以下において明らかになるように、クエリを実行可能にするためにこの情報を必要としない。
【００２１】
次に、すべてのノード名には、対応するノードポリノミアルｎ（ｘ）が割り当てられる。リーフノードに対しては、それのノードポリノミアルは、それの識別ポリノミアルに等しい。非リーフノードに対しては、それのノードポリノミアルは、それの識別ポリノミアルとそれのすべてのチャイルドノードのノードポリノミアルの積として計算される。図２（ｂ）において、これが示される。
【００２２】
大きな次数のポリノミアルを回避するため、例えば、Ｆｐ［ｘ］やＺ［ｒ（ｘ）］などの有限フィールドで作業することが好ましい。有限フィールドを使用することは、何れの情報も失うことはない。
【００２３】
第１の例では、ポリノミアルの係数は、モジュローｐに減少される。ｐが素数である場合、
【００２４】
【数１】
2008501175.tif 000004
となる。従って、すべてのポリノミアルは、Ｆｐの係数を有するｐ−１未満の次数のポリノミアルに減少することが可能である。これは、ｐ＝５の選択による図３（ｂ）に示される。
【００２５】
第２の例では、ポリノミアルは、還元不可能な（ｉｒｒｅｄｕｃｉｂｌｅ）ポリノミアルｒ（ｘ）のモジュローに減少される。このポリノミアルの次数は、ｒ（ｘ）の次数未満となる。しかしながら、その係数は、Ｚ、すなわち、すべての数の要素となり、多数のノード名を有するデータ構造について大変大きなものとなりうる。これは、ｒ（ｘ）＝ｘ２＋１の選択による図３（ｂ）に示される。
【００２６】
まとめると、実施例のノード名、割り当てられた識別子、識別ポリノミアル及びノード名に対するノードポリノミアルが以下で概略される。
【００２７】
【表２】
2008501175.tif 000005
ポリノミアルのツリーを構成すると、次のステップは、ツリーをサーバ部分とクライアント部分に分割することである。サーバ部分はサーバ１００に格納され、クライアント部分は、以降においてサーバをクエリするクライアント１０２に格納される。データソースシステム１０３が、クライアント１０２と同一のシステムではない場合、クライアント部分は、クライアント１０２に送信される必要がある。
【００２８】
好適な実施例では、ポリノミアルのツリーは、以下のように分割される。各ノードには、そのノードポリノミアルと同一の次数の自ら（擬似）ランダムに選択したブラインドポリノミアルが割り当てられる。このことは、同一の名前を有する２つのノードは通常は異なるブラインドポリノミアルに割り当てられることを意味する。図４（ａ）において、図２（ａ）の一例となるツリーのこのような割り当ての例が示される。図４（ａ）のツリーは、ブラインドポリノミアルのツリーと呼ばれる。これらのポリノミアルはすべて、Ｆ５［ｘ］に含まれる。
【００２９】
次に、各ノードに対して、差分ポリノミアルが、ブラインドポリノミアルと差分ポリノミアルの和がノードポリノミアルに等しくなるように計算される。図４（ｂ）において、一例となるツリーについて対応する「差分ポリノミアルのツリー」が示される。各ノードに対して、当該ノードの図４（ａ）のブラインドポリノミアルが図４（ｂ）の対応する差分ポリノミアルに加えられる場合、その結果が図３（ａ）の当該ノードのノードポリノミアルとなることは真である。例えば、図４（ｂ）のルートノードに加えて、図４（ａ）のルートノードは、図３（ａ）のルートノードに等しい
【００３０】
【数２】
2008501175.tif 000006
となる。
【００３１】
図５（ａ）及び５（ｂ）において、Ｚ［ｘ２＋１］の対応する例が示される。図５（ａ）のルートノードが図５（ｂ）のルートノードに加えられる場合、その結果は図３（ｂ）のルートノードとなる。
【００３２】
【数３】
2008501175.tif 000007
クライアント１０２とサーバ１００の一方にブラインドポリノミアルのツリーが与えられ、他方には差分ポリノミアルのツリーが与えられる。これのツリーの何れも、ポリノミアルの元のツリーを再構成するのに十分な情報を有していない。これらのツリーは、ネットワークを介し送信可能であるか、あるいは、ＣＤ−ＲＯＭなどのデータキャリア上で利用可能にすることが可能である。
【００３３】
原則的には、クライアント１０２とサーバ１００の何れがどのツリーを受信するかは重要ではない。しかしながら、クライアント１０２が限られた格納容量しか有しない場合には、差分ポリノミアルのツリーをサーバ１００に割り当てることが効果的である。そのとき、クライアント１０２には、ブラインドポリノミアルが生成された擬似乱数生成装置を初期化するのに使用されるシードしか提供することはできない。このとき、クライアント１０２は、必要なときには常に、ブラインドポリノミアルを再生成することができる。例えば、携帯電話は、限られた格納容量しか有しないが、必要な計算を実行するのに十分なパワーを有する。
【００３４】
ブラインド及び差分ポリノミアルのツリーがクライアントとサーバに供給された後、クライアントは、サーバを照会することが可能である。まず、シンプルな要素検索、すなわち、ノード名が与えられたとき、ツリーからノードを検出することが説明される。
【００３５】
ＸＰａｔｈと呼ばれるＷ３Ｃ勧告は、あるパスを含むＸＭＬ文書の検索を記載している。「ｃｌｉｅｎｔ」という名前のノードの要素検索は、ＸＰａｔｈにおいて“／／ｃｌｉｅｎｔ」として示される。通常、サーバ１００は、ツリー全体を探索し、「ｃｌｉｅｎｔ」という名前とすべてのノード名を比較することによってこのような検索を実行する。これはやや非効率であり、さらに、サーバが実際のノード名を有していない場合には、差分ポリノミアル（又はブラインドポリノミアル）のツリーのみにより行うことは不可能である。
【００３６】
本発明によると、クライアント１０２はまず、対象となるノード名に割り当てられた識別子を決定する。「ｃｌｉｅｎｔ」という名前に対しては、上述したように識別子は「２」である。このとき、クライアント１０２は、サーバ１００に当該識別子、本例ではｘ＝２に等しいｘについてそれのツリーにおけるポリノミアルを評価し、結果を返すよう問い合わせる。好ましくは、サーバ１００は、さらなる不要な計算を行うことを回避するため、クライアント１０２がサーバ１００に計算終了時間を通知することができるように、計算が終了するとすぐに、各ポリノミアルの各結果を返すべきである。このことが、以下において説明される。
【００３７】
クライアント１０２はまた、ｘ＝２の与えられた値に対して、１つずつそれのポリノミアルを評価する。さらに、クライアント１０２は、各ノードに対して、それ自体の評価とサーバ１００によって当該ノードに返された評価結果との和を計算する。この和がゼロに等しい場合、当該ノードのノードポリノミアルは、係数（ｘ−２）を含む。このことは、このノードが「ｃｌｉｅｎｔ」というノード名を有しているか、あるいは、それの下位の何れかにその名前を有するノードがあることを意味する。
【００３８】
この和が非ゼロである場合、ノードポリノミアルは係数（ｘ−２）を含まない。このことは、当該ノードの下位の何れにも「ｃｌｉｅｎｔ」というノード名が存在しないことを意味する。従って、このブランチにおいてさらなる検索を実行することは不要である。このとき、クライアント１０２は、それが当該ブランチのポリノミアルの評価を止めることが可能であることをサーバ１００に通知することが可能である。
【００３９】
和がゼロに等しく、それのチャイルドの和がゼロに等しくない各ノードは、クエリに対する回答を表している。これは、図６（ａ）〜（ｃ）に示されている。すべての評価は、Ｆ５［ｘ］に属する。図７（ａ）〜（ｃ）において、Ｚ［ｘ２＋１］の同一の例が示される。
【００４０】
図６（ａ）は、クライアントツリーのすべてのポリノミアル（従って、ブラインドポリノミアル）の評価を示す。図６（ｂ）は、サーバツリーのすべてのポリノミアル（従って、差分ポリノミアル）の評価を示す。図６（ｃ）は、図６（ａ）と（ｂ）のポリノミアルの各評価の各自の和を示す。図６（ｃ）から図２（ａ）を比較することによって確認することができるように、図２（ａ）の「ｃｌｉｅｎｔ」という名前を有するノードはゼロの和を有し、それらのチャイルドは非ゼロの和を有する。「ｃｕｓｔｏｍｅｒｓ」というノードはゼロの和を有し、またチャイルドもまたゼロの和を有する。このことは、当該ノードの下位には「ｃｌｉｅｎｔ」という名前のノードが１以上存在することを示している。
【００４１】
このアプローチは、あるノード名がツリーの複数のレベルに出現可能である場合には、完全に正確な結果を提供しない。例えば、データが以下のように構成された場合、
【００４２】
【表３】
2008501175.tif 000008
ライン３の「ｃｌｉｅｎｔ」と名付けられたノードは、一致したノードとして特定されない。このノードは、「ｃｌｉｅｎｔ」という名前の下位ノードがライン５に存在するという事実のため、ゼロの和を有するチャイルドノードを有する。
【００４３】
この問題を有しない一致したノードを特定するより良好な方法が利用可能である。それは、ノードの一部について元のノードポリノミアルを再構成することを要求する。クライアント１０２がブラインドポリノミアルのツリーを受信していることを仮定する。サーバ１００から回答を受信し、上述のような特定のノードを特定した後、クライアント１０２は、特定された各ノードに対して、それの差分ポリノミアルと当該ノードの直接のチャイルドの差分ポリノミアルとをサーバ１００からリクエストする。例えば、図６（ｃ）の例では、ルートノードは一致したノードである。クライアント１０２は、ルートノードと当該ルートノードの直接下位にある２つのノードの差分ポリノミアルを要求する。
【００４４】
ここで、クライアント１０２は、対象となる各ノードに対して、関連するブラインドポリノミアルと差分ポリノミアルを単に加えることによって、ノードポリノミアルを再構成することが可能である。その後、ゼロの和を有するノードのノードポリノミアルは、それの直接のチャイルドのノードポリノミアルによって除算される。これは、ゼロの和を有するノードの識別ポリノミアルを明らかにする。識別ポリノミアルが、与えられたクエリに対してゼロに評価されるか否かは、容易に評価することが可能である。これから、対象となるノードがクエリに該当するか、あるいは、回答がチャイルドの１つに求められるべきか結論付けることができる。
【００４５】
さらに、サーバからの回答の正しさをチェックすることも可能である。ｆをノードのノードポリノミアルとし、ｑ１，．．．，ｑｎをそれのｎ個のチャイルドノードのノードポリノミアルとする。回答の正しさをチェックするため、ｔに対して以下の式が解かれる必要がある。
【００４６】
【数４】
2008501175.tif 000009
ｔの値は、クエリに使用されるノード名の識別子に等しくなるべきである。この例では、当該識別子はクエリに使用される「ｃｌｉｅｎｔ」というノード名に割り当てられていたため、ｔは２に等しくなるべきである。これは、以下のように解くことができる。
【００４７】
【数５】
2008501175.tif 000010
これから、以下の式が成り立つ。
【００４８】
【数６】
2008501175.tif 000011
ただし、各ａｉはｔの関数である。これは、以下の方程式の系列により書き換えることが可能である。
【００４９】
【数７】
2008501175.tif 000012
１つの等式が、ｔを解くのに十分である。その他の等式は、サーバによって提供される回答をチェックするのに使用されてもよい。サーバが正しい回答を提供すると信頼される場合、最後の等式のみで十分である。この場合、サーバに格納される各ポリノミアルの一定の係数のみが送信される必要がある。これは、帯域幅を低減し、効率性を向上させるが、セキュリティを低下させる。
【００５０】
該当するノードが検出されると、クライアント１０２は、サーバ１００からこれらのノードの（暗号化された）コンテンツを要求し、当該コンテンツをローカルに解読することが可能である。このように、暗号化されたデータベースの全体の代わりに、該当するノードのコンテンツのみがサーバ１００からクライアント１０２に送信されるだけでよい。
【００５１】
いくつかのアプリケーションでは、ノードは、エンプティであり、すなわち、コンテンツを有していないかもしれない。このとき、すべての情報は、ノード名に含まれ、ノードの構成はツリーに含まれる。
【００５２】
本発明はまた、より高度なＸＰａｔｈのクエリがプロテクトされたデータに対して実行することを可能にする。もちろん、“／／ａ／ｂ／／ａ／ｄ／ｅ”などのクエリが、左から右に評価することが可能である。すなわち、まず‘ａ’の出現についてツリーを検索し、その後、‘ｂ’と名付けられたノードに対してこの名前を有するノードの下位のブランチ内において検索などが行われる。一度にクエリ全体を評価することは、はるかにより効率的である。
【００５３】
ツリーのすべてのポリノミアルは、それのすべての下位ノードのルートを有する。これは、１つのクエリが特定の下位ノードを含むすべての要素を検出することを可能にする。上述した例のクエリを解くには、以下のステップを必要とする。
１．ルートノードから、ツリーのより下位の何れかにある‘ｂ’、‘ｃ’、‘ｄ’及び‘ｅ’という名前を有する要素を有する‘ａ’という名前を有するすべての要素を検出する。
２．検出された名前‘ａ’を有するすべての要素から、ツリーのより下位の何れかにある‘ｃ’、‘ｄ’及び‘ｅ’という名前を有する要素を有する‘ｂ’という名前を有するすべての直接のチャイルドを検出する。
３．検出された名前‘ｂ’を有するすべての要素から、ツリーのより下位の何れかにある‘ｄ’及び‘ｅ’という名前を有する要素を有する‘ｃ’という名前を有するすべての下位ノードを検出する。
４．検出された名前‘ｃ’を有するすべての要素から、ツリーのより下位の何れかにある‘ｅ’という名前を有する要素を有する‘ｄ’という名前を有するすべての直接的なチャイルドを検出する。
５．検出された名前‘ｄ’を有するすべての要素から、‘ｅ’という名前を有するすべての直接的なチャイルドを検出する。
【００５４】
上記実施例は、要素名が例えば、ＤＴＤにより記述された固定サイズのセットから選択されるが、異なるデータ要素の個数が無限に存在しうるため、ＸＭＬ要素のコンテンツについては使用することはできないと仮定している。以下において、データ検索に適した実施例が提供される。
【００５５】
本実施例では、元のＸＭＬ文書のデータ文字列は、各ノードが小さなセットから選択されるノードのパスに変換される。好ましくは、この小さなセットは、もちろん、他のキャラクタが当該セットに含まれてもよいが、アルファベット、すなわち、｛‘Ａ’，．．．，‘Ｚ’，‘ａ’，．．．，‘ｚ’｝である。
【００５６】
当該セットは、すべてのデータ要素が当該セットからのキャラクタのみを使用して表現することができるように選択されてもよい。しかしながら、データ要素に使用されるすべてのキャラクタの限られたサブセットのみを選択することによって、当該セットを構成することも可能である。例えば、句読点、スペースなどは排除することができる。セットの選択は、何れのタイプのクエリがデータに対して実行可能であるか決定する。当該セットがアルファベットのみを含む場合、ワードに対するクエリのみが実行可能である。
【００５７】
セットを構成した後、次のステップは、データノードをいわゆる「トライ」表現に変換することである。このタイプの表現は、Ｅｄｗａｒｄ  Ｆｒｅｄｋｉｎ、Ｂｏｌｔ  Ｂｅｒａｎｅｋ及びＮｅｗｍａｎによる“Ｔｒｉｅ  ｍｅｍｏｒｙ”（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，３（９）：４９０−４９９，Ｓｅｐｔｅｍｂｅｒ  １９６０）に記載されている。効果的に、データセグメントのトライ表現により、データセグメントの第２キャラクタに続く第１キャラクタが、当該第２キャラクタのチャイルドノードとして表現される。
【００５８】
図８（ａ）は、データコンテンツを有するＸＭＬ要素の一例を示す。この例では、当該要素は、“ｎａｍｅ”と呼ばれ、“Ｊｏａｎ  Ｊｏｈｎｓｏｎ”というデータを含む。
【００５９】
図８（ｂ）は、このＸＭＬ要素の圧縮されたトライ表現を示す。図８（ｃ）は、このＸＭＬ要素の圧縮されていないトライ表現を示す。圧縮されていないトライは、オリジナルと正確に同一の情報を格納し、圧縮されたトライは、ワードのオーダ及びカージナリティ（ｃａｒｄｉｎａｌｉｔｙ）を欠落している。この例では、文字列は、パスによって表されるワードに分割され、その後、各パスは複数のキャラクタに分割される。文字列をノードに分割する他の方法は、大変良好に可能である。これらの図において確認することができるように、データセグメント“Ｊｏａｎ”のキャラクタ“Ｊ”に続くキャラクタ“ｏ”が、“Ｊ”のノードのチャイルドノードとして表される。
【００６０】
この処理は、セット内の要素と同数の新たな要素名を生成する。例えば、テキストがアルファベット（ａ，ｂ，．．．，ｚ）の小文字に分割されるとき、これは２６個の新たな名前を与える。ポリノミナルを可能な限り少数に維持するため、２９の素数ｐが妥当である。書く文字は、ｐ＊ｌｏｇ＿２（ｐ）ビット＝１８バイトをとる。従って、ワーストケースシナリオでは（共通のプリフィックスが存在しないとき）、テキストのサイズは、この定数により増大する。しかしながら、当該文書が大きいほど、共通のプリフィックスの個数は増加し、これにより、サイズの増加はより小さくなる。変換された文書が元の文書より小さくなる可能性はさらに小さい。
【００６１】
元のＸＭＬツリーを（圧縮された）トライに変換すると、上述したものと同様の方針が文書を符号化するのに利用可能である。ここでは、ＸＭＬ文書のデータコンテンツを検索することが可能である。例えば、このクエリはここでは可能である。
【００６２】
【数８】
2008501175.tif 000013
このクエリは、テキスト“Ｊｏａｎ”を含むすべてのテキスト（データ）ノードを検索する。このクエリは、まず
【００６３】
【数９】
2008501175.tif 000014
に変換され、その後に、
【００６４】
【数１０】
2008501175.tif 000015
に変換される。「．」や「．＊」などのシンプルな正規表現は、それのトライ等価な「＊」及び「／／」にマッピングすることが可能である。
【００６５】
上記検索方針を利用して、まず、「ｎａｍｅ」という名前を有するＸＭＬ要素が配置される。次のステップは、この要素はデータ文字列“Ｊｏａｎ”を含むか判断するというものである。これは、上記のようにこの要素（及びそれのチャイルド）に対してクエリ“Ｊ／ｏ／ａ／ｎ”を実行することによって行われる。言い換えると、クエリ“Ｊｏａｎ”は、“Ｊｏａｎ”のトライ表現に対するクエリに変換される。
【００６６】
図８（ｂ）及び（ｃ）において確認することができるように、それの下位にノード“ｏ”があり、それは“Ｊｏａｎ”のその他のキャラクタである“ａ”と“ｎ”のノードに後続する。従って、上記方針を使用してクエリ“Ｊ／ｏ／ａ／ｎ”は、ノード“ｎａｍｅ”が“Ｊｏａｎ”の値を含むか明らかにする。
【００６７】
上述したように、本実施例は、当初選択されたセットのキャラクタを使用して構成される文書のデータを検索することを可能にする。セット｛‘Ａ’，．．．，‘Ｚ’，‘ａ’，．．．，‘ｚ’｝により、ワードに対するクエリを実行することが可能である。当該セットに属しないデータのキャラクタは、それらは具体的に指定されたキャラクタにマッピングすることも可能であるが、好ましくは、トライにおいて省略される。トライにおいてこのようなキャラクタを省略することによって、このようなキャラクタはクエリにおいて指定される必要はない。例えば、図８（ｂ）のトライにおいて、“Ｊｏａｎ  Ｊｏｈｎｓｏｎ”に対するクエリは、“Ｊｏａｎ”と“Ｊｏｈｎｓｏｎ”との間のクエリのスペースキャラクタがトライに存在しなくても、成功するであろう。
【００６８】
さらなる精緻化では、キャラクタのセットは、データ要素において使用されるすべての一意的なキャラクタを決定することによって構成される。あるいは、ＸＭＬ文書は、それの符号化を決定するため検討可能であり、それから何れのキャラクタセットが使用されるか判断することが可能である。このとき、当該セットは、キャラクタセットに等しいように選択される。これは、特にＵｎｉｃｏｄｅキャラクタセットが使用されるときには、比較的大きなセットを与えるが、可能性のあるすべてのクエリを検索することが可能である。
【００６９】
必要な計算を実行するため、サーバ１００とクライアント１０２には、特別に記述されたソフトウェア及び／又はハードウェアを設けることが可能である。大部分の計算はポリノミアルの評価であるため、標準的なＣＰＵがソフトウェアを実行するため利用可能である。
【００７０】
上記実施例は本発明を限定するものではなく、説明するものであって、当業者は添付した請求項の範囲から逸脱することなく他の多数の実施例を構成することが可能であるということに留意すべきである。
【００７１】
例えば、ブラインドポリノミアルのツリーを第１サーバに、差分ポリノミアルのツリーを第２サーバに格納することが可能である。そのとき、クライアントは、双方のサーバに与えられたｘの値に対してそれらのポリノミアルを評価することを要求することが可能であり、これらの結果を加えるだけでよい。このように、クライアントは、自らポリノミアルを評価する必要はない。
【００７２】
ノードポリノミアルを有するツリーは、３以上の主体がクエリを解くのに必要とされるように、３以上のツリーに分割することが可能である。これを実行する直接的な方法の１つは、各ノードに対して複数の（擬似）ランダムにブラインドポリノミアルを選択することである。その後、各ノードの差分ポリノミアルが、当該ノードに対するすべてのブラインドポリノミアルと差分ポリノミアルの和が当該ノードのノードポリノミアルに等しくなるように、選択される。各主体は、ブラインドポリノミアルのツリー又は差分ポリノミアルのツリーの１つを受信する。１つのノードに対してすべてのポリノミアルのすべての評価を加えることによって、当該ノードがクエリに該当しているか確認することが可能である。
【００７３】
請求項では、括弧内におかれる参照記号は、請求項を限定するものとして解釈されるべきでない。「有する」という用語は、請求項に列挙された以外の要素又はステップの存在を排除するものではない。要素に先行する「ある」という用語は、そのような要素が複数存在することを排除するものではない。
【００７４】
本発明は、複数の相異なる要素を有するハードウェア及び適切にプログラムされたコンピュータによって実現することが可能である。請求項に記載される「手段」は、各自のソフトウェアライブラリ又はモジュールによって実現可能である。複数の手段が、１つのコンピュータプログラムによって実現可能である。
【００７５】
複数の手段を列挙した装置クレームでは、これらの手段のいくつかが、１つの同一のハードウェアアイテムにより実現することが可能である。ある手段が互いに異なる従属クレームに記載されているという事実は、これらの手段の組み合わせが効果的には利用可能でないことを示すものではない。
【図面の簡単な説明】
【００７６】
【図１】図１は、本発明によるシステムの概略を示す。
【図２ａ】図２（ａ）は、一例となるＸＭＬベース文書のツリー表現を示す。
【図２ｂ】図２（ｂ）は、ノード名に割り当てられるノードポリノミアルのツリーを示す。
【図３ａ】図３（ａ）は、Ｆ５［ｘ］のノードポリノミアルのツリーを示す。
【図３ｂ】図３（ｂ）は、Ｚ［ｘ２＋１］のノードポリノミアルのツリーを示す。
【図４ａ】図４（ａ）は、Ｆ５［ｘ］のブラインドポリノミアルのツリーを示す。
【図４ｂ】図４（ｂ）は、Ｆ５［ｘ］の差分ポリノミアルのツリーを示す。
【図５ａ】図５（ａ）は、Ｚ［ｘ２＋１］のブラインドポリノミアルのツリーを示す。
【図５ｂ】図５（ｂ）は、Ｚ［ｘ２＋１］の差分ポリノミアルのツリーを示す。
【図６ａ】図６（ａ）は、図４（ａ）のブラインドポリノミアルのツリーのすべてのポリノミアルのＦ５［ｘ］における評価を示す。
【図６ｂ】図６（ｂ）は、図４（ｂ）の差分ポリノミアルのツリーのすべてのポリノミアルのＦ５［ｘ］における評価を示す。
【図６ｃ】図６（ｃ）は、図６（ａ）及び６（ｂ）のポリノミアルの各評価のＦ５［ｘ］における各自の和を示す。
【図７ａ】図７（ａ）は、図５（ａ）のブラインドポリノミアルのツリーのすべてのポリノミアルのＺ［ｘ２＋１］における評価を示す。
【図７ｂ】図７（ｂ）は、図５（ｂ）の差分ポリノミアルのツリーのすべてのポリノミアルのＺ［ｘ２＋１］における評価を示す。
【図７ｃ】図７（ｃ）は、図７（ａ）及び７（ｂ）のポリノミアルの各評価のＺ［ｘ２＋１］における各自の和を示す。
【図８ａ】図８（ａ）は、データコンテンツを有するＸＭＬ要素の一例を示す。
【図８ｂ】図８（ｂ）は、このＸＭＬ要素の圧縮されたトライ表現を示す。
【図８ｃ】図８（ｃ）は、このＸＭＬ要素の圧縮されていないトライ表現を示す。
【図１】
2008501175.tif 000016
【図２（ａ）】
2008501175.tif 000017
【図２（ｂ）】
2008501175.tif 000018
【図３（ａ）】
2008501175.tif 000019
【図３（ｂ）】
2008501175.tif 000020
【図４（ａ）】
2008501175.tif 000021
【図４（ｂ）】
2008501175.tif 000022
【図５（ａ）】
2008501175.tif 000023
【図５（ｂ）】
2008501175.tif 000024
【図６（ａ）】
2008501175.tif 000025
【図６（ｂ）】
2008501175.tif 000026
【図６（ｃ）】
2008501175.tif 000027
【図７（ａ）】
2008501175.tif 000028
【図７（ｂ）】
2008501175.tif 000029
【図７（ｃ）】
2008501175.tif 000030
【図８ａ】
2008501175.tif 000031
【図８ｂ】
2008501175.tif 000032
【図８ｃ】
2008501175.tif 000033
【国際調査報告】
2008501175.tif 000034
2008501175.tif 000035
2008501175.tif 000036