(57)【要約】  リクエスタは、データベースの暗号化されたカラムに関し、レンジド・ルックアップ演算を要求することができる。インデックス構造を、レンジド・ルックアップ演算を実行するために使用することができる。当該インデックス構造は、多数のエントリを含むことができる。当該インデックス構造の当該エントリの各々は、インデックス値と当該データベースの対応する行を検索するための検索情報とを含むことができる。各エントリの当該インデックス値は、当該データベースの暗号化されたカラムからのそれぞれの復号されたデータ項目に対応することができる。当該復号されたデータ項目は、変換関数により変換されて、当該変換され復号されたデータ項目が、当該変換関数により変換される前の当該復号されたデータ項目より少ない情報を明かすようにすることができる。当該インデックス構造の当該エントリのうちの１個の当該それぞれのインデックス値が、当該受信したレンジド・ルックアップ要求を満たす場合、当該それぞれの検索情報を、当該データベースからデータの対応する行を検索するために使用することができる。
2010507172.tif 000002
【特許請求の範囲】
【請求項１】
データベース内の暗号化されたカラム上でレンジド・ルックアップを実行する方法であって、
前記データベース内の前記暗号化されたカラムに関して受信したレンジド・ルックアップ要求に基づいて、前記データベースのインデックス構造の複数個のエントリのうち少なくとも１個のエントリにアクセスするステップ（図５、行為５０８）であって、前記インデックス構造の前記複数個のエントリの各々はそれぞれのデータ項目および前記データベース内の対応する行を検索する検索情報を含み、前記それぞれのデータ項目は前記データベース内の前記暗号化されたカラムから復号されてそれから変換関数により変換される（図３Ｂ；３０２、３１２、３２０）ステップと、
前記インデックス構造の前記複数個のエントリのうちの１個の前記それぞれのデータ項目が前記受信したレンジド・ルックアップ要求を満たす場合に、前記インデックス構造の前記複数個の前記エントリのうちの前記１個の前記それぞれの検索情報を使用することにより、前記データベースの行を検索するステップ（図５；５１４）において、
前記インデックス構造の前記複数個のエントリは、前記それぞれのデータ項目が前記インデックス構造のインデックス値であるように、前記それぞれのデータ項目に従って配置され（図４；行為４１０）、
前記レンジド・ルックアップ要求の演算は、前記レンジド・ルックアップ要求のリクエスタに関し透過的に実行されるステップ（図５、行為５０２）と
を備えることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記インデックス構造は、Ｂツリーを含むことを特徴とする方法。
【請求項３】
請求項１に記載の方法において、前記変換関数は、復号されたデータ項目からより少ない情報を明かすようにするために、前記暗号化されたカラムから前記復号されたデータ項目を変換することを特徴とする方法。
【請求項４】
請求項１に記載の方法において、前記変換関数は、前記暗号化されたカラムから復号されたデータ項目を複数個のカテゴリのうちの１個を表す値に変換することを特徴とする方法。
【請求項５】
請求項１に記載の方法であって、
前記データベース内の前記暗号化されたカラム上の前記レンジド・ルックアップで使用されることを許可された少なくとも１個のレンジド・ルックアップ演算子を定義するステップをさらに備えることを特徴とする方法。
【請求項６】
請求項１に記載の方法であって、
ユーザーが前記暗号化されたカラムからそれぞれの復号されたデータ項目を変換する変換関数を定義して、前記インデックス構造の前記複数個のエントリの前記それぞれのデータ項目が前記それぞれの復号されたデータ項目より少ない情報を明かすような、前記インデックス構造の前記複数個のエントリの前記それぞれのデータ項目を作成することを許可するステップをさらに備えることを特徴とする方法。
【請求項７】
請求項１に記載の方法であって、
ユーザーが前記暗号化されたカラムからそれぞれの復号されたデータ項目を変換する変換関数を定義して、前記それぞれのデータ項目が前記復号されたデータ項目より少ない情報を明かすような、前記インデックス構造の前記複数個のエントリの前記それぞれのデータ項目を作成することを許可するステップと、
前記ユーザーが新しい変換関数を定義した場合、前記インデックス構造の前記複数個のエントリの前記それぞれのデータ項目のうち少なくとも１個を再計算するステップと
をさらに備えることを特徴とする方法。
【請求項８】
請求項１に記載の方法であって、
前記データベースの全ての暗号化されたカラムからプレーンテキストデータを検索および修正する権限を有するユーザーだけが、前記暗号化されたカラムからそれぞれの復号されたデータ項目を変換する前記変換関数を定義して、前記それぞれのデータ項目が前記復号されたデータ項目より少ない情報を明かすような、前記インデックス構造の前記複数個のエントリの前記それぞれのデータ項目を作成することを許可するステップをさらに備えることを特徴とする方法。
【請求項９】
少なくとも１個のプロセッサに対して保存された命令を有する機械可読媒体であって、
復号されたデータ項目を作成するためにデータベースの暗号化されたカラムの暗号化されたデータ項目を復号する命令と（図４、行為４０２）、
復号され変換されたデータ項目を作成するために変換関数に従い前記復号されたデータ項目を変換する命令と（図４；行為４０４）、
データベースに対しインデックス構造を作成する命令であって、前記インデックス構造は前記データベース内の前記暗号化されたカラム上でのレンジド・ルックアップ実行用であり（図４、行為４０６）、前記インデックス構造は複数個のエントリを含み、前記複数個のエントリの各々は前記データベース内の対応する行を検索する検索情報および前記データベースの前記暗号化されたカラムのそれぞれの暗号化されたデータ項目に対応するそれぞれの復号され変換されたデータ項目を含む命令において（図３Ｂ；３０２、３１２、３２０）、
前記それぞれの復号され変換されたデータ項目が前記インデックス構造のインデックス値であるように、前記インデックス構造の前記複数個のエントリは前記それぞれの復号され変換されたデータ項目に従って配置される（図４；行為４１０）命令と
を備えることを特徴とする方法。
【請求項１０】
請求項９に記載の機械可読媒体であって、
前記変換関数が変更された場合、前記インデックス構造の前記復号され変換されたデータ項目を再計算し、および前記インデックス構造の前記複数個のエントリを再配置する命令をさらに備えることを特徴とする方法。
【請求項１１】
請求項９に記載の機械可読媒体であって、
前記データベースの全ての暗号化されたカラムからプレーンテキストデータを検索および修正する権限を有するユーザーによってのみ前記変換関数が変更されることを許可する命令をさらに備えることを特徴とする方法。
【請求項１２】
請求項９に記載の機械可読媒体において、前記変換関数は、復号されたデータ項目より少ない情報を明かす変換され復号されたデータ項目を作成するため前記復号されたデータ項目を変換するよう配置されることを特徴とする機械可読媒体。
【請求項１３】
請求項９に記載の機械可読媒体において、前記インデックス構造は、Ｂツリーを含むことを特徴とする機械可読媒体。
【請求項１４】
請求項９に記載の機械可読媒体であって、前記データベース内の前記暗号化されたカラム上で実行する少なくとも１個のレンジド・ルックアップ演算子を定義する命令をさらに備えることを特徴とする機械可読媒体。
【請求項１５】
前記データベースの暗号化されたカラム上でレンジドル・ルックアップを実行するリモートデータベースを提供する方法であって、
ネットワーク経由でリクエスタからリモート要求を受信して、前記リモート要求を満たす少なくとも１個のデータベースのエントリに対し前記レンジド・ルックアップを実行するステップ（図５；行為５０２）と、
前記リモート要求を満たすインデックス値を有する複数個のエントリのうちの少なくとも１個を発見するために前記複数個のエントリを含むインデックス構造をトラバースするステップ（図５；５０８）であって、前記複数個のエントリの各々は前記データベース内で対応する行を検索する検索情報と変換関数により変換された前記暗号化されたカラムのそれぞれの復号されたデータ項目に対応するそれぞれのインデックス値とを含むステップ（図３Ｂ；３０２、３１２、３２０および図４、行為４１０）と、
前記リモート要求を満たす前記それぞれのインデックス値を有する前記複数個のエントリのうちの少なくとも１個から前記それぞれの検索情報を使用することにより、前記データベースからデータの行を検索するステップ（図５、行為５１４）と、
前記リクエスタに前記データベースからデータの前記行を与えるステップ（図５、行為５１４）において、
前記レンジド・ルックアップの演算は、前記リクエスタに関し透過的に実行されるステップ（図５、行為５０２）と
をさらに備えることを特徴とする方法。
【請求項１６】
請求項１５に記載の方法であって、
前記リクエスタから受信した前記リモートリクエストに前記変換関数を透過的に適用するステップをさらに備えることを特徴とする方法。
【請求項１７】
請求項１５に記載の方法において、前記変換関数は、前記暗号化されたカラムから復号されたデータ項目を変換して、前記復号されたデータ項目からより少ない情報を明かすステップをさらに備えることを特徴とする方法。
【請求項１８】
請求項１５に記載の方法であって、
前記リクエスタが前記データベースの全ての暗号化されたカラムからプレーンテキストデータを検索および修正する権限を有する場合のみ、前記リクエスタが前記変換関数を定義することを許可するステップにおいて、
前記変換関数は、前記暗号化されたカラムから復号されたデータ項目を変換して、前記復号されたデータ項目からより少ない情報を明かすステップ
をさらに備えることを特徴とする方法。
【請求項１９】
請求項１５に記載の方法であって、
前記リクエスタが前記変換関数を定義することを許可するステップと、
前記リクエスタが前記変換関数を再定義した場合、前記インデックス構造の少なくとも１個のそれぞれのインデックス値を再計算するステップと、
前記それぞれのインデックス値に従い前記インデックス構造の前記複数個のエントリを再配置するステップと
をさらに備えることを特徴とする方法。
【請求項２０】
請求項１５に記載の方法であって、
前記リクエスタからの前記リモート要求に含まれるレンジド・ルックアップ演算子が前記データベースの前記暗号化されたカラム上のレンジド・ルックアップ演算に対し定義されていない場合、前記リクエスタに失敗したレンジド・ルックアップを知らせるステップ
をさらに備えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レンジド・ルックアップに関する。
【背景技術】
【０００２】
企業はデータベースシステムを使用して、ビジネスの様々な態様で使われるデータを保存および検索する。このデータは数百万もの記録を含む可能性があり、これらのうちの少なくとも一部、例えば顧客情報等を、企業は秘密にしておくことを望む。そのようなデータは、悪意を有するかもしれない他人にとって、価値がある可能性がある。もし企業の敵がこのような秘密の情報を手に入れることができた場合、この敵は、会社、顧客、またはその両方にとって問題を引き起こすことができることとなる。
【０００３】
データベース内の価値ある情報を保護するためおよび秘密規則または政策に従うために用いられる一つの一般的な方法は、暗号化である。しかしながら、データベース内での暗号化されたデータの使用は、どのようにして既存のアプリケーションによりデータへの認可されたアクセスを許可するか、ならびにどのようにして全てのデータを復号および線形探索を実行することなく特定の項目を発見するか等の他の問題を引き起こす。
【０００４】
データベース内の暗号化されたデータ上でルックアップ（lookup）の基礎を形成したイコーリティー（equality）を実行する解決法が存在する一方で、レンジド・ルックアップ（ranged lookup）を実行する解決法が望まれているが、自明でない。
【発明の概要】
【０００５】
本概要は、単純化された形式で以下の詳細な説明でさらに説明される概念の選択を紹介するために与えられる。本概要は、特許請求の範囲に記載された主題の主要な特徴または本質的な特徴を識別することを意図しておらず、特許請求の範囲に記載された主題の範囲を限定するために使用されることも意図していない。
【０００６】
以下で論じられる実施形態は、データベースシステムに関し、このデータベース内では暗号化されたデータ上でレンジド・ルックアップを実行することができる。
【課題を解決するための手段】
【０００７】
一実施形態では、データベースの暗号化されたカラムに関してレンジド・ルックアップ要求を受信することができる。多くのエントリを含むインデックス構造をトラバースして、レンジド・ルックアップ要求を満たす１個または複数個のエントリを発見することができる。インデックス構造のエントリの各々は、インデックス値とデータベースの対応する行を検索するための検索情報とを含むことができる。インデックス値は、変換関数により変換された暗号化されたカラムからのそれぞれの暗号化されたデータ項目と対応することができる。インデックス値は、対応する復号されたデータ項目より少ない情報を明かす。インデックス構造のエントリのうちの１つのそれぞれのインデックス値が受信したレンジド・ルックアップ要求を満たす場合、それぞれの検索情報を、データベースからデータの対応する行を検索するために使用することができる。
【０００８】
上述および他の利点および特徴を得ることができる方法を説明するために、より詳しい説明が以下で説明され、添付された図面に示す具体的な実施形態への参照により表される。これらの図面は典型的な実施形態のみを示すことおよび従って発明の範囲を限定するとはみなされないことを理解しながら、実装が、追加の特異性および詳細とともに添付図面の使用を通じて述べられ説明される。
【図面の簡単な説明】
【０００９】
【図１】本開示の主題と一致する実施形態に対し例示的な動作環境を示す図である。
【図２】図１の処理装置１０２および／または処理装置１０４を実装することができる例示的な処理装置の機能ブロック図を示す図である。
【図３Ａ】本開示の主題と一致する実装に使用することができる例示的なインデックス構造を示す図である。
【図３Ｂ】本開示の主題と一致する実装に使用することができる例示的なインデックス構造を示す図である。
【図４】インデックス構造を作成する本開示の主題と一致する実施形態に実装することができる例示的なプロセスの流れ図である。
【図５】レンジド・ルックアップ要求を実行する本開示の主題と一致する実施形態に実装することができる例示的なプロセスの流れ図である。
【図６】ユーザーに変換関数を定義または再定義することを許可する本開示の主題と一致する実施形態に実装することができる例示的なプロセスの流れ図である。
【発明を実施するための形態】
【００１０】
実施形態が以下で詳細に論じられる。具体的な実装が論じられるが、これは図示目的のみのためになされることを理解すべきである。関連技術の当業者は、本開示の主題の趣旨および範囲から離れなければ、他の構成要素および機器構成を使用できることを認識する。
【００１１】
図１は、本開示の主題と一致する実施形態に関して例示的な動作環境１００を示す。動作環境１００は、処理装置１０２、処理装置１０４およびネットワーク１０６を含むことができる。
【００１２】
処理装置１０２は、例えばデータベースシステムを実行することが可能なサーバまたは他の処理装置であってもよい。処理装置１０４は、アプリケーションを実行することおよびネットワーク１０６を介して処理装置１０２と通信することが可能なパーソナルコンピュータ（ＰＣ）または他の処理装置であってもよい。
【００１３】
ネットワーク１０６は、有線または無線ネットワークであってもよいし、並びに有線または無線手段を介して接続されたいくつかの装置を含むことができる。ネットワーク１０４は、１個のネットワークのみまたはいくつかの異なるネットワークを含むことができ、これらのネットワークのいくつかは異なるタイプのネットワークであってもよい。
【００１４】
動作環境１００では、処理装置１０４はアプリケーションを実行することができ、このアプリケーションはネットワーク１０６を介して処理装置１０２のデータベース内の情報にアクセスする。このアプリケーションは、処理装置１０２のデータベース内でデータを作成、消去、読み取りまたは修正することができる。
【００１５】
図１は、例示的な動作環境を示す。他の動作環境または動作環境１００のバリエーションを、本開示の主題と一致する他の実施形態とともに使用することができる。例えば、図１は、処理装置１０２および処理装置１０４を別個のデバイスとして示す。しかしながら、一実施形態では、処理装置１０２および１０４は、単一の処理装置に組み合わされてよい。そのような実施形態では、動作環境は、ネットワーク１０６を含まないことができる。別の実施形態では、処理装置１０２によって実行される関数またはサービスを、多くの処理装置にわたって分散することができ、この多くの処理装置を、例えばネットワーク１０６等のネットワークを介して接続することができる。
【００１６】
図２は、例示的な処理装置２００を示す機能ブロック図であり、処理装置２００は、処理装置１０２、処理装置１０４、または両方の装置を実装するために使用することができる。処理装置２００は、バス２１０、プロセッサ２２０、メモリ２３０、読み取り専用メモリ（ＲＯＭ）２４０、記憶装置２５０、入力装置２６０、出力装置２７０、および通信インターフェース２８０を含むことができる。バス２１０は、処理装置２００の構成要素間の通信を許可することができる。処理装置２００が処理装置１０２と処理装置１０４の両方を単一の処理装置で実装するために使用される実施形態では、処理装置２００の構成要素の１つとして、通信インターフェース２８０を含まないことができる。
【００１７】
プロセッサ２２０は、命令を解釈および実行する少なくとも１つの従来のプロセッサまたはマイクロプロセッサを含むことができる。メモリ２３０は、プロセッサ２２０による実行のための情報および命令を保存するＲＡＭ（random access memory）または別タイプの動的記憶装置であってもよい。メモリ２３０は、プロセッサ２２０による命令の実行の間使用される一時的な変化または他の中間情報を保存することもできる。ＲＯＭ２４０は、プロセッサ２２０に対する静的な情報および命令を保存する、従来のＲＯＭ装置または別タイプの静的記憶装置を含むことができる。記憶装置２５０は、データおよび／または命令を保存する任意のタイプの媒体を含むことができる。処理装置２００が処理装置１０２を実装するために使用される場合、記憶装置２５０は、データベースシステムの１個または複数個のデータベースを含むことができる。
【００１８】
入力装置２６０は、例えばキーボード、マウス、または他の入力装置等、ユーザーが情報を処理装置２００に入力することを許可する１個または複数個の従来の装置を含むことができる。出力装置２７０は、ディスプレイ、プリンタ、または他の出力装置を含む、ユーザーに情報を出力する１個または複数個の従来の装置を含むことができる。通信インターフェース２８０は、処理装置２００が他のデバイスまたはネットワークと通信することを可能にする任意のトランシーバーのような装置を含むことができる。一実施形態では、通信インターフェース２８０は、ネットワーク１０６へのインターフェースを含むことができる。
【００１９】
処理装置２００は、例えばメモリ２３０、または他の媒体等のコンピュータ可読媒体に含まれる一連の命令を実行するプロセッサ２２０に応答してこのような関数を実行することができる。このような命令を、記憶媒体２５０等の別のコンピュータ可読媒体から、または通信インターフェース２８０を介した別個の装置から、メモリ２３０内で読み取ることができる。
【００２０】
概観
一般的なデータシステムでは、データを、テーブル内に保存されているとして、見ることができる。テーブルの行は、ファイル内の記録に対応することができる。一部のデータベースシステムは、テーブルのカラム内に保存されたデータを暗号化することを許可する。データが確定的に暗号化された場合、このようなデータベースシステムは、暗号化されたカラム内のデータ上で同等検索（equality  search）を許可することができる。すなわち、データベースの暗号化されたカラム内で確定的に暗号化されたサイファテキストに対応する特定のプレーンテキスト値を有するテーブル内で行の検索を実行することができる。既定の暗号鍵を使用する場合、確定的暗号化は、常に、プレーンテキストアイテムを同一の対応するサイファテキストアイテムに暗号化する。このようにして、データパターンは、情報漏れが生じることを認識可能であることができる。
【００２１】
例えばランダム初期化ベクタを伴う暗号ブロック連鎖（ＣＢＣ、cipher-block chaining）モードのブロックサイファの使用等の非確定的暗号化方法、または他の非確定的暗号化方法は、同一のプレーンテキストのデータ項目を異なるサイファテキストのデータ項目に暗号化することができる。例えば、ランダム初期化ベクタを伴うＣＢＣモードのブロックサイファの使用による非確定的暗号化は、カレントブロックを暗号化する前に、プレーンテキストのカレントブロックと前のサイファテキストのブロックとの排他的論理和をとること（ＸＯＲｉｎｇ）により、プレーンテキストの各ブロックを暗号化することができる。このように、サイファテキストのデータ項目の値を、対応するプレーンテキストのデータ項目および暗号鍵だけに基づくのではなく、例えば前に暗号化されたデータのブロックまたはランダム初期化ベクタ等の他のデータにも基づくようにすることができる。
【００２２】
本開示の主題と一致する実施形態はデータベースシステムに関し、このデータベースシステム内で、レンジド・ルックアップを、データベースの暗号化されたカラムの確定的にまたは非確定的に暗号化されたデータ上で実行することができる。一実施形態では、データベースの暗号化されたカラム内のデータ上でレンジド・ルックアップを実行するインデックス構造が与えられる。このインデックス構造は、いくつかのエントリを含むことができる。このエントリの各々は、インデックス値を含むことができる。このインデックス値を、データベースの暗号化されたカラムからそれぞれのデータ項目を復号することおよびインデックス値を作成するためそれぞれの復号されたデータ項目に変換関数を適用することにより、計算することができる。変換関数を、作成されたインデックス値がデータベースの暗号化されたカラムからの対応する復号されたデータ項目より少ない情報を明かすような方法で、定義することができる。
【００２３】
一部の実装では、変換関数を、データベースの特定の暗号化されたカラムに対し定義することができる。本開示の主題と一致する実施形態では、ユーザーがデータベースの特定の暗号化されたカラムに対し変換関数を定義または修正することを、許可することができる。一部の実装では、データベースの全ての暗号化されたカラムから復号されたデータを修正および検索することを認可されたそれらのユーザーのみに、データベースの特定の暗号化されたカラムに対し変換関数を定義または修正することを許可することができる。このような実装では、変換関数を定義または修正することを許可されたユーザーのうちのどれかを、データベースの全ての暗号化されたカラムから復号されたデータを修正および検索することを認可されたそれらのユーザーだけに制限することにより、特権攻撃の増大を防止することができる。
【００２４】
特権攻撃の増大の一例として、ユーザーが暗号化されたカラムに対し復号されたデータにアクセスすることを認可されていない場合でさえ、データベースシステムが、ユーザーにデータベースの暗号化されたカラムに対する変換関数を定義することを許可することを仮定する。ユーザーは変換関数を脆弱になるよう定義または修正することができるので、データベースの暗号化されたカラムからのそれぞれの復号されたデータ項目から全ての情報またはほとんど全ての情報を、レンジド・ルックアップ演算実行に対するインデックス構造のインデックス値として保存することができる。現段階で、コピーまたは同等のものが暗号化されたデータの脆弱な変換関数により与えられるので、システムのプレーンテキスト内で利用可能にすることができる。従って、このユーザーは直接見ることを許可され、データ暗号化の利益を無効化する。
【００２５】
本開示の主題を満たす実施形態では、ユーザーが、データベースの特定の暗号化されたカラムに対する変換関数を定義または修正した後、データベースのインデックス構造のそれぞれのエントリ内のインデックス値を修正された変換関数により再計算することができ、およびインデックス構造を再配置することができるので、レンジド・ルックアップを、再計算されたインデックス値に従ってインデックス構造をトラバースすることにより、実行することができる。
【００２６】
一部の実装では、１個または複数個のレンジド・ルックアップ演算子を、データベースの特定の暗号化されたカラム上でレンジド・ルックアップを実行することに対し定義することができる。このような実装では、データベースの特定の暗号化されたカラム上でレンジド・ルックアップを実行することに対し定義されていないレンジド・ルックアップ演算子の使用は、失敗したレンジド・ルックアップ演算をもたらす。
【００２７】
一実装では、インデックス構造はＢツリーまたは他のインデックス構造を含むことができる。これらはレンジド・ルックアップ演算を実行するために使用されて、レンジド・ルックアップ演算を満たすデータベースの暗号化されたカラムの暗号化されたデータに対応する、特定のプレーンテキストのデータ項目を有するデータベース内で１個または複数個の行を発見することができる。
【００２８】
例示的方法
データシステムは、一般的に、データベースのカラム内に保存されたデータを迅速に検索するためいくつかのタイプのインデックススキームを使用して、特定の記録または行にアクセスする。１個の周知なインデックススキームは、Ｂツリーの使用を含むが、他のインデックス構造も他の実施形態において使用することができる。
【００２９】
図３Ａは、本開示の主題と一致する実施形態におけるレンジド・ルックアップ演算実行での使用のためのインデックス構造として用いることができる例示的なＢツリーを示す。例示的なＢツリーは、インデックスノード３０２、３１２、３２０、３２６、３２８、３０、３３２、３３４、３３６、３３８、３４０、および３４２を含むことができる。インデックスノードの各々は、１個または複数個のエントリを含むことができる。インデックスノードはリーフノードではなく、他のインデックスノードへの１個または複数個のリンクを含むことができる。例えば、インデックスノード３０２はいくつかのエントリを含むことができ、例えばインデックスノード３１２、３２０、３２６および３２８等の他のインデックスノードへのリンクをさらに含むことができる。インデックスノード３１２は、いくつかのエントリを含むことができ、例えばインデックスノード３３０、３３２および３３４等の他のインデックスノードへのリンクをさらに含むことができる。この例において、インデックスノード３３０、３３２および３３４は、リーフノードであってもよい。インデックスノード３２０は、少なくとも１個のエントリならびにインデックスノード３３６および３３８へのリンクを含むことができる。この例において、インデックスノード３３６および３３８は、リーフノードであってもよい。インデックスノード３２６は、少なくとも１個のエントリおよびインデックスノード３４０へのリンクを含むことができる。この例において、インデックスノード３４０は、リーフノードであってもよい。インデックスノード３２８は、少なくとも１個のエントリおよびインデックスノード３４２へのリンクを含むことができる。この例において、インデックスノード３４２は、リーフノードであってもよい。
【００３０】
図３Ｂは、本開示の主題と一致する図３Ａの例示的なインデックスノード３０２、３１２、および３２０のより詳細な表示を示す。この例示的なＢツリーのインデックス構造において、インデックスノード内の各エントリは、インデックス値および例えばデータベース内で対応する行へのポインタ等の検索情報を含むことができる。例えば、インデックスノード３０２は、データベースの特定の暗号化されたカラムからデータ項目を復号することおよびインデックス値を作成する変換関数を適用することにより再計算することができたインデックス値を有する第１の項目を含むことができるので、インデックス値は復号されたデータ項目より少ない情報を明かす。一例として、インデックスノード３０２、３１２および３２０のそれぞれのエントリのインデックス値を、社会保障番号を含むことができるデータベースの暗号化されたカラムのデータ項目を復号することおよび例えば社会保障番号の最後の４桁に等しい値を作成することができる変換関数等の変換関数を適用することにより、作成することができる。このように、インデックスノード３０２、３１２および３２０のエントリのそれぞれのインデックス値は、データベースの暗号化されたカラム内の対応する社会保障番号の最後の４桁であってもよい。例示的なインデックスノード３０２では、インデックスノード３０２の第１のエントリは、最後の４桁として３４５２を有する社会保障番号と対応することができ、インデックスノード３０２の第２のエントリは、最後の４桁として６５９８を有する社会保障番号と対応することができ、インデックスノード３０２の第３のエントリは、最後の４桁として８７４６を有する社会保障番号と対応することができる。検索‐ｐｔｒ１、検索‐ｐｔｒ２、検索‐ｐｔｒ３は、インデックスノード３０２のそれぞれのエントリに対応するデータベースの行を検索する情報を含むことができる。図３Ｂに見ることができるように、インデックスノード３１２は、２個のエントリを含むことができる。インデックスノード３１２の第１のエントリは、最後の４桁として１５７８を有する社会保障番号と対応する、インデックス値１５７８を含むことができ、インデックスノード３１２の第２のエントリは、最後の４桁として２０９４を有する社会保障番号と対応する、インデックス値２０９４を含むことができる。検索‐ｐｔｒ４および検索‐ｐｔｒ５は、インデックスノード３１２のそれぞれのエントリに対応するデータベースの行を検索するための情報を含むことができる。インデックスノード３２０は、最後の４桁として４６７８を有する社会保障番号と対応する、インデックス値４６７８を含むことができる。インデックスノード３２０の検索‐ｐｔｒ６は、データベースの対応する行を検索するための情報を含むことができる。
【００３１】
インデックスノード３０２は、リンク３０４、リンク３０６、リンク３０８、およびリンク３１０を含むことができる。リンク３０４は、インデックスノード３０２のインデックス値３４５２より小さい対応するインデックス値を伴うエントリを有するインデックスノード３１２へのリンクであってよい。リンク３０６は、インデックスノード３０２のインデックス値３４５２より大きくかつインデックス値６５９８より小さい対応するインデックス値を伴うエントリを有するインデックスノード３２０へのリンクである。リンク３０８は、インデックスノード３０２を、インデックスノード３０２のインデックス値６５９８より大きくかつインデックス値８７４６より小さいそれぞれのインデックス値を伴う１個または複数個のエントリを有するインデックスノード３２６と結び付けることができる。リンク３１０は、インデックスノード３０２を、インデックスノード３０２のインデックス値８７４６より大きいそれぞれのインデックス値を伴う１個または複数個のエントリを有するインデックスノード３２８と結び付けることができる。
【００３２】
さらに、インデックスノード３１２は、インデックスノード３３０へのリンク３１４、インデックスノード３３２へのリンク３１６、およびインデックスノード３３４へのリンク３１８を含むことができる。インデックスノード３３０は、インデックスノード３１２のインデックス値１５７８より小さいインデックス値を有する１個または複数個のエントリを含むことができる。インデックスノード３３２は、インデックスノード３１２のインデックス値１５７８より大きくかつインデックス値２０９４より小さいインデックス値を含む１個または複数個のエントリを含むことができる。インデックスノード３３４は、インデックスノード３１２のインデックス値２０９４より大きいインデックス値を含む１個または複数個のエントリを含むことができる。インデックスノード３２０は、インデックスノード３３６へのリンク３２２およびインデックスノード３３８へのリンク３２４を含むことができる。インデックスノード３３６は、インデックスノード３２０のインデックス値４６７８より小さいインデックス値を含む１個または複数個のエントリを含むことができる。インデックスノード３３８は、インデックスノード３２０のインデックス値４６７８より大きいインデックス値を含む１個または複数個のエントリを含むことができる。
【００３３】
レンジド・ルックアップ演算は、レンジド・ルックアップ演算を満たすデータベースのいくつかの行をもたらすことができるので、図３Ｂの例示的なＢツリーのインデックス構造は、等しいインデックス値を有するいくつかのエントリに容易にアクセスすることができるように、修正を含むことができる。例えば、例示的なインデックスノード３０２、３１２、および３２０内のエントリは、等しいインデックス値を有する他のエントリへのリンクを有することができる。図３Ｂに示されるように、インデックスノード３０２の第１のエントリはリンク３０５を含み、インデックスノード３０２の第１のエントリを、インデックス値３４５２を有するインデックス構造の別のエントリ（図示されない）に結び付けることができ、インデックスノード３０２の第２のエントリはリンク３０７を含み、インデックスノード３０２の第２のエントリを、インデックス値６５９８を有するインデックス構造の別のエントリ（図示されない）に結び付けることができ、そしてインデックスノード３０２の第３のエントリはリンク３０９を含み、インデックスノード３０２の第３のエントリを、インデックス値８７４６を有するインデックス構造の別のエントリ（図示されない）に結び付けることができる。インデックスノード３１２の第１のエントリはリンク３１５を含み、インデックスノード３１２の第１のエントリを、インデックス値１５７８を有するインデックス構造の別のエントリ（図示されない）に結び付けることができ、そしてインデックスノード３１２の第２のエントリはリンク３１７を含み、インデックスノード３１２の第２のエントリを、インデックス値２０９４を有するインデックス構造の別のエントリ（図示されない）に結び付けることができる。インデックスノード３２０の第１のエントリはリンク３２３を含み、インデックスノード３２０の第１のエントリを、インデックス値４６７８を有するインデックス構造の別のエントリ（図示されない）に結び付けることができる。
【００３４】
インデックスノードの各々は、図３Ｂの例示的なインデックス構造内に示される数と異なる数の項目を含むことができる。例えば、インデックスノード３０２、３１２、または３２０は、それぞれのインデックスノード内部に含まれる、図３Ｂに示される数とは異なる数の項目を有することができる。さらに、上述の変換関数は、例示的な変換関数にすぎない。他の変換関数を定義して、データベースの暗号化されたカラムからのデータ項目に変換関数を実行することによって作成された値が、データベースの暗号化されたカラムからのデータ項目より少ない情報を明かすようにすることができる。別の変換関数の例として、データベースの暗号化されたカラム内のデータ項目が、従業員の年収を含むと仮定する。例示的な変換関数を定義して、０＄‐４００００＄の範囲内の年収を１の値に、４０００１＄‐９００００＄の範囲内の年収を２の値に、等と変換することができる。もちろん、他の変換関数を定義して、暗号化されたカラムからのデータ項目に適用された場合に、変換関数により作成された値が、暗号化されたカラムからのデータ項目より少ない情報を明かすようにすることもできる。
【００３５】
本開示の主題と一致する実施形態では、例えば図３Ａおよび図３Ｂのインデックス構造等のインデックス構造を、処理装置１０２により、インデックス構造内の新しい項目に対応するリンクが図３Ａおよび図３Ｂに示す方法で機能できるように、インデックスノードに項目を追加することまたは新しい項目を含む新しいインデックスノードを追加することで、アップデートすることができる。すなわち、インデックス構造内のリーフノードではないノードに追加された各々新しい項目は、追加された項目のインデックス値より小さいそれぞれのインデックス値を有する１個または複数個の項目を含むインデックスノードを指すリンクおよび追加された項目のインデックス値より大きいそれぞれのインデックス値を有する１個または複数個の項目を含むインデックスノードを指す第２のリンクを有することができる。さらに、新しいインデックスノードがインデックス構造に追加された場合、処理装置１０２は、インデックス構造の既存のリンクのうち少なくとも１個をアップデートして、新しいインデックスノードを指すことができる。処理装置１０２がインデックス構造に追加することができる各々新しい項目は、それぞれのインデックス値およびデータベースの対応する行への参照を含むことができる。さらに、新しく追加されたエントリのインデックス値と等しいインデックス値を有するインデックス構造の１個または複数個のエントリは、新しく追加されたエントリへのリンクを有することができ、または新しく追加されたエントリは、等しいインデックス値を有するインデックス構造の少なくとも１個のエントリへのリンクを有することができる。
【００３６】
図４は、データベースの暗号化されたカラム内で、データのレンジド・ルックアップを実行するためのインデックス構造を作成する例示的なプロセスを示す流れ図である。この例示的なプロセスは、変換関数がデータベースの暗号化されたカラム内のデータに対し前もって定義されたと仮定する。
【００３７】
このプロセスは、処理装置１０２がデータベースの暗号化されたカラムからのデータ項目を復号することで開始することができる（行為４０２）。処理装置１０２は、次いで、変換関数を復号されたデータに適用し、復号されたデータ項目より少ない情報を明かす変換されたデータ項目を作成することができる（行為４０４）。処理装置１０２は、変換され復号されたデータ項目および、例えばポインタまたはリンク等、データベース内の対応する行を検索するための検索情報を含むインデックス構造内にエントリを作成することができる（行為４０６）。処理装置１０２は、次いで、データベースの暗号化されたカラム内にもっとデータ項目があるかどうかを判定することができる（行為４０８）。処理装置１０２が、データベースの暗号化されたカラム内にもっとデータ項目が存在すると判定した場合、次いで処理装置１０２は、データベースの暗号化されたカラムからの次のデータ項目にアクセスすることができ（行為４１２）、それから行為４０２‐４０８を繰り返すことができる。
【００３８】
行為４０８を実行中に、処理装置１０２が、データベースの暗号化されたカラム内にさらなるデータ項目がないと判定した場合、次いで処理装置１０２は、インデックス構造の各エントリ内の変換され復号されたデータ項目を、レンジド・ルックアップ演算実行のためのインデックス値として使用することができるように、インデックス構造のエントリを配置することができる（行為４１０）。一実施形態では、インデックス構造のエントリを配置することは、インデックス構造のリンクまたはポインタを、インデックス構造の他の適切なエントリを指すように設定することを含むことができる。
【００３９】
図５は、本開示の主題と一致する実施形態でレンジド・ルックアップを実行する例示的なプロセスを示す流れ図である。このプロセスは、処理装置１０２が、リクエスタから、データベースの暗号化されたカラムに関して、レンジド・ルックアップ要求を受信することで開始することができる（行為５０２）。このリクエスタは、ローカルもしくはリモートユーザーまたはアプリケーションであってもよい。リクエスタがリモートである場合、リクエスタは、例えば処理装置１０４等のリモート処理装置からレンジド・ルックアップ要求を起動することができる。処理装置１０４は、例えばネットワーク１０６等のネットワーク経由で、処理装置１０２と通信することができる。このレンジド・ルックアップ要求は、データベースの暗号化されたカラムのフィールドの名前、レンジド・ルックアップ演算子および値を含むことができる。例えば、上述から従業員の給料の例を使用すると、ユーザーは、「ＳＥＬＥＣＴ  ＊  ＦＲＯＭ  ｔａｂｌｅ＿１  ＷＨＥＲＥ  ｓａｌａｒｙ  ＜  １００００」のようなレンジド・ルックアップ要求をすることができる。このデータベースシステムは、内部でレンジド・ルックアップ要求を「ＳＥＬＥＣＴ  ＊  ＦＲＯＭ  ｔａｂｌｅ＿１  ＷＨＥＲＥ  ｓａｌａｒｙ．ｒａｎｇｅｄ＿ｌｏｏｋｕｐ  ＜  ｆ（１００００）」と翻訳することができる。ｔａｂｌｅ＿１は、データベースシステムのテーブルであり、ｓａｌａｒｙ．ｒａｎｇｅｄ＿ｌｏｏｋｕｐは、ｔａｂｌｅ＿１の給料カラム上でのレンジド・ルックアップを示し、ｆ（１００００）は、値１００００に変換関数を適用することにより作成された値に対応する。このように、レンジド・ルックアップの演算を、リクエスタに関して透過的に実行することができる。
【００４０】
レンジド・ルックアップ要求を受信後、処理装置１０２は、レンジド・ルックアップ要求のレンジド・ルックアップ演算子がデータベースの暗号化されたカラム上の使用に対し定義されているかどうかを判定することができる（行為５０４）。一実装では、例えば他と同様に「＜」、「
【００４１】
【数１】
2010507172.tif 000003
【００４２】
」、「＞」、「
【００４３】
【数２】
2010507172.tif 000004
【００４４】
＞」、および「ＬＩＫＥ」等のレンジド・ルックアップ演算子を、または異なるレンジド・ルックアップ演算子を、データベースの暗号化されたカラム上でレンジド・ルックアップ演算を実行することに対し定義することができる。「＜」は、特定の値より小さい値を有するデータベース内のエントリを発見するために使用することができ、「
【００４５】
【数３】
2010507172.tif 000005
【００４６】
」は、特定の値より小さいかまたは等しい値を有するデータベース内のエントリを発見するために使用することができ、「＞」は、特定の値より大きい値を有するデータベース内のエントリを発見するために使用することができ、「
【００４７】
【数４】
2010507172.tif 000006
【００４８】
」は、特定の値より大きいかまたは等しい値を有するデータベース内のエントリを発見するために使用することができ、そして「ＬＩＫＥ」は、例えば社会保障番号の最後の４桁に対する特定の値とマッチするエントリ等、変換関数の適用によって切り詰めることができたマッチするエントリを発見するために使用することができる。
【００４９】
行為５０４中に、処理装置１０２が、レンジド・ルックアップ要求内のレンジド・ルックアップ演算子が暗号化されたカラムに関して定義されていないと判定した場合、次いで処理装置１０２は、リクエスタにレンジド・ルックアップ要求を実行することができなかったという指示を戻すことができる（行為５０６）。
【００５０】
行為５０４中に、処理装置１０２が、レンジド・ルックアップ要求内のレンジド・ルックアップ演算子が暗号化されたカラムに関して定義されていると判定した場合、次いで処理装置１０２は、例えば図３Ａおよび図３Ｂのインデックス構造等のインデックス構造、または受信したレンジド要求ルックアップに対応する項目に対して別タイプのインデックス構造を検索またはトラバースすることができる（行為５０８）。処理装置１０２は、次いで行為５０８の実行の結果として、対応する項目が見つかったかどうかを判定することができる（行為５１０）。処理装置１０２が対応する項目が見つからなかったと判定した場合、次いで処理装置１０２は、対応する項目が見つからなかったことを示す指示をリクエスタに戻すことができる（行為５１２）。
【００５１】
処理装置１０２が、行為５０８を実行することの結果として、対応する項目が発見されたと判定した場合、次いで処理装置１０２は、発見された項目に対応するインデックス構造のエントリ内に含まれる検索情報を使用して、データベース内の対応する行を検索することができ、およびリクエスタに対応する行を与えることができる（行為５１４）。処理装置１０２は、次いで、インデックス構造を用いて、さらなる項目がレンジド・ルックアップ要求を満たすかどうかを判定する（行為５１６）。一実装では、図３Ｂの例示的なインデックス構造により示されるような方法で、処理装置１０２がインデックス構造のカレントエントリのインデックス値と等しいインデックス値を有するインデックス構造のエントリへのリンクにアクセスすること、およびインデックス構造をトラバースすることにより、行為５１６を、実行することができる。処理装置１０２がレンジド・ルックアップ要求を満たす１個または複数個の項目が存在すると判定する場合、次いで行為５１４‐５１６を、繰り返すことができる。
【００５２】
このプロセスは、処理装置１０２がレンジド・ルックアップ要求を満たすさらなる項目がないと判断した場合に終了することができる。
【００５３】
図６は、本開示の主題と一致する実施形態で実装することができる例示的なプロセスの流れ図である。図６の流れ図は、ユーザーがデータベースの暗号化されたカラムに対し変換関数を定義または再定義する場合に実行することができる例示的なプロセスを示す。このプロセスは、処理装置１０２が、例えばローカルまたはリモートユーザー等のリクエスタから、データベースの暗号化されたカラム内の項目に対し変換関数を定義または再定義する要求を受信することで開始することができる（行為６０２）。例えば、リモートリクエスタからこの要求を受信した場合、この要求は処理装置１０４経由で始めることができ、およびネットワーク１０６経由で処理装置１０２と通信することができる。処理装置１０２は、次いで、リクエスタが変換関数を定義することを認可されているかどうかを判定する（行為６０４）。例えば、一実装では、データベースの全ての暗号化されたカラムからデータにアクセスすることを認可されたリクエスタだけが、データベースの暗号化されたカラムに対し変換関数を定義または再定義することを認可される。処理装置１０４が、リクエスタはデータベースの暗号化されたカラムに対し変換関数を定義または再定義することを認可されていないと判定した場合、次いで処理装置１０４は、変換関数を定義または再定義する要求を拒否することができる（行為６０６）。
【００５４】
処理装置１０４がリクエスタは変換関数を定義または再定義することを認可されていると判定した場合、次いで、処理装置１０４は変換関数がリクエスタにより定義または変更されることを許可することができる（行為６０８）。処理装置１０４は、次いで、インデックス構造のインデックス値を再計算することができる（行為６１０）。例えば、処理装置１０４は暗号化されたカラムからのデータ項目、復号されたデータ項目にアクセスして、変換関数を適用し、変換されたデータ項目を作成することができる。変換されたデータ項目は、次いで、インデックス構造のエントリ内にインデックス値として保存することができる。処理装置１０４は、全てのインデックス値が再計算されるまで、インデックス構造のインデックス値の再計算を繰り返すことができる。インデックス構造の全てのインデックス値が再計算された後、処理装置１０４は、インデックス構造を再配置することができる（６１２）。例えば、図３Ａおよび図３Ｂに示されるインデックス構造のようなインデックス構造内で、特定の値より小さい、特定の値より大きい、または特定の値と等しいインデックス値を有するエントリへのリンクまたはポインタを、インデックス構造の再計算されたインデックス値に従って、アップデートすることができる。
【００５５】
結論
構造的特長および／または方法論的行為に特有の言語で主題が説明されてきたが、添付された特許請求の範囲内の主題は、必ずしも上述の具体的な特徴または行為に限定されないことが理解されるべきである。むしろ、上述の具体的な特徴および行為は、特許請求の範囲を実装するための例の形として、開示される。
【００５６】
上記の説明は具体的な詳細を含む可能性があるが、それらは決して特許請求の範囲を限定するものとして解釈するべきではない。上述の実施形態の他の機器構成は、本開示の範囲の部分である。さらに、本開示の主題と一致する実装は、上述の行為より多い若しくは少ない行為を有することができ、または示されているものとは異なる順番で行為を実装することができる。したがって、与えられた任意の具体的な例よりむしろ添付された特許請求の範囲およびその法上の均等物のみが、本発明を定義すべきである。
【図１】
2010507172.tif 000007
【図２】
2010507172.tif 000008
【図３Ａ】
2010507172.tif 000009
【図３Ｂ】
2010507172.tif 000010
【図４】
2010507172.tif 000011
【図５】
2010507172.tif 000012
【図６】
2010507172.tif 000013
【国際調査報告】
2010507172.tif 000014
2010507172.tif 000015