(57)【特許請求の範囲】
【請求項１】
コンピュータの保護されたワーキングメモリに記憶され、同期化された検索および順序データ構造を使用して、非一時的なコンピュータ可読媒体に記憶されたデータの集合に、前記コンピュータに実装されたデータベース管理システムがアクセスする方法であって、
前記集合内の要素に対する参照と、それらの参照の関連付けられた暗号鍵とだけを格納している検索データ構造を、暗号化鍵値によって編成するステップと、
前記集合内の要素に対する参照と、それらの参照の関連付けられた暗号鍵とだけを格納する順序データ構造を、非暗号化鍵値によって編成するステップと、
前記検索データ構造と前記順序データ構造とを検索および更新することによって挿入または削除操作を実行し、関連付けられた前記集合の要素を挿入または削除するステップと、
前記集合の望ましい前記要素を求めて前記検索データ構造を検索し、関連付けられた値を更新することによって更新操作を実行するステップと、
検索鍵に従って前記検索データ構造を検索することによって検索操作を実行するステップと、
前記順序データ構造を検索して値の範囲を特定し、その後望ましい方向で前記順序データ構造をトラバースすることによってソート操作を実行するステップと、
２つまたはそれ以上の命令データ構造からエントリをトラバースし、選択することによってマージ操作を実行するステップと、
それらの操作の結果をユーザにレポートするステップと、
を含み、
前記データベース管理システムが、上記各ステップを実行することを特徴とする方法。
【請求項２】
特定の実装形態への依存度を最小限に抑えるために、データ構造および暗号操作のためにアプリケーション・プログラム・インターフェイスとプラグインアーキテクチャとを用いる、請求項１に記載の方法。
【請求項３】
ハードウェアとソフトウェアとの一方または両方を選ぶことに依存しない実装形態である、請求項１に記載の方法。
【請求項４】
前記検索および順序データ構造が複合データ構造を備える、請求項１に記載の方法。
【請求項５】
前記順序データ構造を編成することが鍵の難読化を用いる、請求項１に記載の方法。
【請求項６】
鍵の難読化が、鍵のソルト化、鍵ビットの並べ替え、鍵ビットの拡張のうちの１つもしくはそれ以上を含む、請求項５に記載の方法。
【請求項７】
コンピュータのワーキングメモリをクリアするステップが、データ構造操作の完了後に前記方法を実行するステップをさらに含む、請求項１に記載の方法。
【請求項８】
保護された処理を用いてコンピュータで前記方法を実行することをさらに含む、請求項１に記載の方法。
【請求項９】
前記データの集合が暗号化データの集合である、請求項１に記載の方法。
【請求項１０】
前記データの集合が非暗号化データの集合である、請求項１に記載の方法。
【請求項１１】
ソート操作を実行することが複数列ソート操作を実行することを含む、請求項１に記載の方法。
【請求項１２】
挿入操作を実行することが挿入可能な位置値を用いることを含む、請求項１に記載の方法。
【請求項１３】
ソート操作を実行することが内部または外部ソートを実行することを含み、マージ操作を実行することが内部または外部マージを実行することを含む、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２０１１年５月３日に出願された「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  Ｅｎｃｒｙｐｔｅｄ  Ｄａｔａ」と題する米国仮特許出願第６１／４８１，８２５号と、２０１２年５月１日に出願された「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  Ｅｎｃｒｙｐｔｅｄ  Ｄａｔａ（）」と題する米国実用特許出願第１３／４６１，４６２号とに対する優先権およびその利益を主張するものであり、これらの明細書および請求項は、参照により本出願に援用される。
（連邦政府の後援による研究または開発に関する声明）
【０００２】
なし。
（コンパクトディスクで提出された資料の参照による援用）
【０００３】
なし。
（著作権のある資料）
【０００４】
なし。
【０００５】
本発明は、データベースまたはファイルアクセスの分野に関し、特に、暗号化されたデータベースを、暗号化されたままで効率良くソートまたは検索することに関するものである。
【背景技術】
【０００６】
記憶されたデータは、法的義務や業務上の理由から、プライバシーを必要とすることが多い。ＨＩＰＡＡなどの法律、そして銀行規制は、個人情報を安全に取り扱うことを義務付けている。企業秘密などのビジネス情報は、概して競合相手から隠しておく必要がある。
【０００７】
現在流通しているデータベースシステムは、大半がデータベースを非暗号化形態でディスクに記憶するため、十分な保護を提供できない。秘匿性の個人情報やビジネス情報の盗難は一般に、盗まれやすいラップトップコンピュータや電子的に妥協したサーバに記憶されることの多い非暗号化データベースで起こる。これにより、盗まれたデータの所有者は、データベース内の個人情報を泥棒に明け渡すことになり、なりすまし犯罪を招いてしまうことが多いだけでなく、責任を問われる。
【０００８】
データ・ストレージ・システムが盗まれた場合や、サーバに電子的に侵入された場合でも、データが暗号化された形態で残っている限り、データベースを暗号化することは、データの逸失を防ぐ優れた方法になり得る。ただしこのプロセスは一般に、操作上の問題へとつながる。その大半は、データベースのソートと検索に関連する問題である。
【０００９】
一般に、暗号化されたデータベースをソートし、検索するには、データベース全体を復号するか、あるいは一部または全部のデータを「その場で」復号することによってデータを復号する必要がある。この作業には相当の演算オーバーヘッドが必要であり、少なくとも一部のデータを非暗号化形態にさらしてしまう。
【００１０】
一般に、データベースを暗号化する数少ないシステムは、最初のユーザがデータベースを開いたときにディスク上でデータベースを復号し、最後のユーザがデータベースを閉じたときに再びそれを暗号化する。そのため、システムが使用中である限り、ファイルシステム上のデータは非暗号化形態のままとなる。そのため、多くのオンライン金融処理および銀行業務アプリケーションで、データが外部記憶装置媒体で、週７日、１日２４時間、常に非暗号化形態でさらされている場合がある。ストレージシステムによっては、非暗号化データを格納している一時ファイルの断片が、オペレーティングシステムによって再割り当てされ、上書きされるまで、外部記憶装置上で露出されたままになっている場合もある。
【００１１】
非暗号化データがディスクに記憶されていれば、泥棒によって容易に「判読可能」である。システムが「クラッシュ」したり、「休眠」モードに入ったり、あるいは、不適切に終了されたりすれば、ディスク上のデータが非暗号化形態のままになるので、窃盗に遭いやすくなる。仮想メモリを使用しているオペレーティングシステムは、メモリページファイルがディスクに書き込まれるため、問題を呈する。そのため、ずる賢い泥棒であれば、ＲＡＭに保持されたどんな非暗号化データでも発見してしまう。このことは、データベースシステムが保護されたワーキングメモリ（すなわちＲＡＭまたは内蔵レジスタ）に保持する非暗号化データは最小限に抑えるべきであることを示唆している。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】米国特許公報第２００５／０１４７２４０号
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明は、演算オーバーヘッドを最小限に抑えつつ、非暗号化データの露出も最小限に抑えることを目的としている。用いた戦略は、できるだけ多くのデータを暗号化しておき、非暗号化形態でのデータ露出を最小限に抑え、非暗号化データを決して外部記憶装置、すなわちディスクに記憶しないというものである。
【００１４】
他の手法だと、それを本発明ほど全般的に有用なものとはしない厳しい制約がある。順序を保持する暗号化アルゴリズムは、暗号化システムの順序を狂わせる要件のために、実装が困難あるいは不可能である。そのようなアルゴリズムの作成にはいくらかの進歩がこれまでに見られたものの（例えば、特許文献１を参照）、現在のところ、高セキュリティアプリケーションに妥当な汎用性を備えている、すなわち十分な強度を有するとは考えられていない。
【００１５】
本発明は、セキュリティアプリケーションに最適化され得る暗号プラグインを用いて実装されているため、この種の暗号上の弱点がない。
【００１６】
Ｏｎ  Ｔｈｅ  Ｆｌｙ  Ｅｎｃｒｙｐｔｉｏｎ（ＯＴＦＥ）は、データの読み出しや書き込みが行われる際に、ハードウェアまたはファームウェアによって（ディスクサブシステムの場合）、あるいはソフトウェアによって（ディスク・デバイス・ドライバの場合）ディスク上にあるデータのすべてを暗号化および復号するプロセスである。
【００１７】
ＯＴＦＥの実装形態がハードウェアとソフトウェアのどちらであっても、オーバーヘッドは、本発明を用いた場合よりもはるかに大きい。ハードウェアによるソリューションは、ソフトウェアによるソリューションよりも一般に費用が高く、既存のシステムでの実装が難しい場合が多い。
【課題を解決するための手段】
【００１８】
本発明は、同期化された検索および順序データ構造を使用して、非一時的なコンピュータ可読媒体に記憶されたデータの集合にアクセスする方法に関するものであり、その集合内の要素に対する参照とそれらの参照の関連付けられた暗号鍵とだけを格納している検索データ構造を暗号化鍵値によって編成することと、その集合内の要素に対する参照とそれらの参照の関連付けられた暗号鍵とだけを格納する順序データ構造を非暗号化鍵値によって編成することと、その集合に対する操作時に、最大２つのクリア・テキスト・データを露出させることと、検索データ構造と順序データ構造とを検索および更新することによって挿入または削除操作を実行し、関連付けられた集合の要素を挿入または削除することと、望ましい集合要素を求めて検索データ構造を検索し、関連付けられた値を更新することによって更新操作を実行することと、検索鍵に従って検索データ構造を検索することによって検索操作を実行することと、順序データ構造を検索して値の範囲を特定し、その後望ましい方向でその順序データ構造をトラバースすることによってソート操作を実行することと、２つまたはそれ以上の命令データ構造からエントリをトラバースし、選択することによってマージ操作を実行することと、それらの操作の結果をユーザにレポートすることと、を含む。好適な実施形態では、データ構造および暗号操作のためにアプリケーション・プログラム・インターフェイスとプラグインアーキテクチャとを用いて、特定の実装形態への依存度を最小限に抑えている。この方法は、ハードウェアとソフトウェアとの一方または両方を選ぶことに依存しない実装形態である。検索データ構造と順序データ構造とを組み合わせて複合データ構造を構成することもできる。順序データ構造を編成するには、鍵の難読化を用い、最も好ましくは鍵のソルト化、鍵ビットの並べ替え、鍵ビットの拡張のうち１つもしくはそれ以上を用いる。本発明は、コンピュータのワーキングメモリをクリアすることをさらに含み得、クリアすることは、データ構造操作の完了後にその方法を実行すること、保護されたワーキングメモリを使用してコンピュータ上でその方法を実行すること、および／または保護されたプロセスを使用してコンピュータ上でその方法を実行すること、を含む。このデータ集合は、暗号化データの集合であっても、かつ／または非暗号化データの集合であっても良い。ソート操作を実行することは、複数列ソート操作を実行することを含むことがあり、挿入操作を実行することは、挿入可能な位置値を用いることを含むことがあり、ソート操作を実行することは、内部または外部ソートを実行することを含むことがあり、マージ操作を実行することは、内部または外部マージを実行することを含むことがある。
【００１９】
本発明のさらなる応用範囲が、添付の図面を参照しながら、以降の詳細な説明に一部記載されている。以降の内容を精査すれば、その範囲の一部が当業者にとって明らかになるであろうし、本発明を実施することによって把握できる可能性もある。本発明の目的と利点は、添付の請求項の中で具体的に指摘されている手段と組み合わせとによって実現および達成され得る。
【００２０】
添付の図面は、本明細書に組み込まれ、本明細書の一部を成すものであり、本発明の１つもしくはそれ以上の実施形態を示しており、記載内容と併せて、本開示の原理を説明するのに役に立つ。これらの図面は本発明の１つもしくはそれ以上の好適な実施形態を表すことだけを目的としており、本発明を制限するものと解釈されるべきでない。
【図面の簡単な説明】
【００２１】
【図１】本発明の好適なデータ構造の概要を示す。
【図２】検索データ構造１２２について説明している。
【図３】順序データ構造１２８について説明している。
【図４】ＣＲＥＡＴＥ操作のフローチャートである。
【図５】ＩＮＳＥＲＴ操作のフローチャートである。
【図６】ＤＥＬＥＴＥ操作のフローチャートである。
【発明を実施するための形態】
【００２２】
本発明は、演算オーバーヘッドを最小限に抑えつつ、非暗号化データの露出も最小限に抑えることを目的としている。用いた戦略は、できるだけデータを暗号化しておき、非暗号化形態でのデータの露出を最小限に抑え、非暗号化データをディスクなどの外部記憶装置に決して記憶しないというものである。
【００２３】
本明細書に記載されている発明は、関連付けられたデータベース管理システムによって操作される暗号化データの効率的で安全な記憶および検索を可能にするもので、データが暗号化された形態にあるまま、その暗号化データに対する検索とソートとをサポートするように設計されたデータ構造と操作方法とを備える。本発明は、関連付けられたデータベースの形態と暗号化の方法との両方から独立しており、関連付けられたデータベース管理システムに統合されるように設計されている。
定義、頭文字、略語
【００２４】
本明細書の記載内容を通じて使用されている語句は、別段の明示がない限り、Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ  Ｄｉｃｔｉｏｎａｒｙ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｅｃｈｎｏｌｏｇｙ（ＡＮＳＤＩＴ）、ＡＮＳＩ／ＩＳＯ／ＩＥＣ  ９０７５：１９９９、およびＮＩＳＴ  ＩＲ−７２９８の定義に従う。
【００２５】
データベース管理システム（ＤＢＭＳ）では、データが１つもしくはそれ以上のデータコンテナに記憶されている。各データコンテナにはレコードが格納されている。各レコード内のデータは、１つもしくはそれ以上のフィールドへと編成される。リレーショナル・データベース・システム（ＲＤＢＭＳ）において、データコンテナはテーブルと呼ばれ、レコードは行、フィールドは列と呼ばれる。
【００２６】
本発明を具現化するシステムは、特定の種類のデータ構造に制限されない。ただし説明のために、本明細書で使用されている実施例および用語は、一般にリレーショナルデータベースと関連付けられているものとする。そのため、「テーブル」、「行」、「列」という用語は、本明細書において、それぞれストレージデータ構造１１０、その構造内のレコード、そのレコード内のフィールドを言及する目的で使用されるものとする。関連フィールドのグループがレコードに関連付けられている任意のデータ構造が使用され得る。
【００２７】
「レコード」という用語は「行」という用語と等しく、各用語は互換的に使用され得る。
【００２８】
「フィールド」という用語は「列」という用語と等しく、各用語は互換的に使用され得る。
頭文字と略語
ＡＮＳＩ  Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄｓ  Ｉｎｓｔｉｔｕｔｅ（米国国家規格協会）
ＡＰＩ  アプリケーション・プログラム・インターフェイス
ＤＢＭＳ  データベース管理システム
ＨＩＰＡＡ  Ｈｅａｌｔｈ  Ｉｎｓｕｒａｎｃｅ  Ｐｏｒｔａｂｉｌｉｔｙ  ａｎｄ  Ａｃｃｏｕｎｔａｂｉｌｉｔｙ  Ａｃｔ
ＩＥＣ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｅｌｅｃｔｒｏｔｅｃｈｎｉｃａｌ  Ｃｏｍｍｉｓｓｉｏｎ（国際電気標準会議）
ＩＳＯ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄｓ  Ｏｒｇａｎｉｚａｔｉｏｎ（国際標準化機構）
ＪＴＡＧ  Ｊｏｉｎｔ  Ｔｅｓｔ  Ａｃｔｉｏｎ  Ｇｒｏｕｐ
ＮＩＳＴ  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ（米国国立標準技術研究所）
ＯＴＦＥ  Ｏｎ−Ｔｈｅ−Ｆｌｙ  Ｅｎｃｒｙｐｔｉｏｎ
ＲＡＭ  ランダム・アクセス・メモリ
ＲＤＢＭＳ  リレーショナルデータベース管理システム
ＳＱＬ  Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ
参考資料
「Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ  Ｄｉｃｔｉｏｎａｒｙ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｅｃｈｎｏｌｏｇｙ（ＡＮＳＤＩＴ）」
オンラインサイト：ｈｔｔｐ：／／ｗｗｗ．ｉｎｃｉｔｓ．ｏｒｇ／ＡＮＳＤＩＴ／Ａｎｓｄｉｔ．ｈｔｍ（２０１１年１月１０日にアクセス）
「Ｄａｔａｂａｓｅ  Ｌａｎｇｕａｇｅ  ＳＱＬ」
Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ  ＡＮＳＩ／ＩＳＯ／ＩＥＣ  ９０７５：１９９９
「Ｇｌｏｓｓａｒｙ  ｏｆ  Ｋｅｙ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  Ｔｅｒｍｓ」
ＮＩＳＴ  ＩＲ−７２９８；Ｋｉｓｓｅｌ，Ｒｉｃｈａｒｄ，ｅｄｉｔｏｒ；Ａｐｒｉｌ  ２５，２００６
「Ｔｈｅ  Ａｒｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｐｒｏｇｒａｍｍｉｎｇ，Ｖｏｌ．３：Ｓｏｒｔｉｎｇ  ａｎｄ  Ｓｅａｒｃｈｉｎｇ，Ｓｅｃｏｎｄ  Ｅｄｉｔｉｏｎ」
Ｋｎｕｔｈ，Ｄｏｎａｌｄ；Ｒｅａｄｉｎｇ，Ｍａｓｓａｃｈｕｓｅｔｔｓ：Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，１９９８
「Ａｌｇｏｒｉｔｈｍｓ  Ａｎｄ  Ｔｈｅｏｒｙ  Ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎ  Ｈａｎｄｂｏｏｋ」
Ｍｉｋｈａｉｌ  Ｊ．Ａｔａｌｌａｈにより編集；ＣＲＣ  Ｐｒｅｓｓ  ＬＬＣ−１９９９
「Ｌｉｔｅｒａｒｙ  Ｍａｃｈｉｎｅｓ」
Ｎｅｌｓｏｎ，Ｔｅｄ；Ｍｉｎｄｆｕｌ  Ｐｒｅｓｓ−１９８８
「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｒｄｅｒ−ｐｒｅｓｅｒｖｉｎｇ  Ｅｎｃｒｙｐｔｉｏｎ  ｏｆ  Ｎｕｍｅｒｉｃ  Ｄａｔａ」
米国特許出願公開第２００５／０１４７２４０Ａ１号、２００５年７月７日
操作要件
【００２９】
ＡＮＳＩ／ＩＳＯ／ＩＥＣの標準ＳＱＬで記述された、本発明によってサポートされるデータベース操作は、以下を含まなければならない。
ＣＲＥＡＴＥステートメントによって実行される操作、
ＩＮＳＥＲＴステートメントによって実行される操作、
ＤＥＬＥＴＥステートメントによって実行される操作、
ＵＰＤＡＴＥステートメントによって実行される操作、
ＳＥＬＥＣＴステートメントによって実行される操作、
ＳＥＬＥＣＴステートメントのＯＲＤＥＲ  ＢＹ節によって実行される操作。
【００３０】
なお、これらの操作はＳＱＬで記述されるものの、これらの記述によって特定のデータベース実装形態が示唆されているわけではなく、単なる典型的なデータベース操作の汎用例とみなすべきである。ＮｏＳＱＬデータベースシステムなどでも同様の操作を確立することができる。
【００３１】
ＳＱＬ  ＳＥＬＥＣＴステートメントとそのＯＲＤＥＲ  ＢＹ節によって例示されるとおり、ソートと検索は最も頻出し、かつ最も複雑であることの多いデータベース操作である。暗号化処理の目的がデータ項目の順序と値とをわかりにくくすることなので、これらの操作は暗号化によってより困難になる。
効率と効果
【００３２】
暗号化および復号操作とインデックス更新とを最小限に抑えることが、この方法を効率良く機能させるための鍵である。
【００３３】
本発明では、データの大半が、計算、画面表示、またはレポート印刷の場合に限って復号する必要がある。本発明によるオーバーヘッド増は最小限であり、その操作はユーザに対して透過的となるように設計されている。
【００３４】
本発明は単体のシステムではなく、データベースシステムに統合されるように設計されている。
【００３５】
本発明は、データの記憶方法に依存しないように設計されており、その実装形態は、統合先のシステムの詳細に依存する。
脆弱性
【００３６】
どれほど優れた設計のシステムであっても、脆弱性は存在する。本発明は、脆弱性ができるだけ少なくなるように設計されており、以降、最も一般的な攻撃面特性についていつくか説明する。
【００３７】
仮想マシン攻撃は、ハードウェアとソフトウェアのどちらでも行うことができる。この攻撃は、仮想マシン上で本発明を実行し、その操作を分析することを伴う。これは最も洗練された形態の攻撃で、防御するのが非常に難しい。
【００３８】
仮想マシン攻撃は通常、追跡または探査対象のシステムによって検出できないことから、ロジックアナライザ、ハードウェアエミュレータ、ハードウェア・デバッグ・サポート、またはＪＴＡＧサポートを用いた追跡・探査技法でも、防御するのが難しい。
【００３９】
コード注入、Ｏ／Ｓフック、ルートキットを用いた中間者攻撃も一般的な攻撃ベクトルである。
攻撃面の最小化
【００４０】
システムのセキュリティを確保するにあたっては、潜在的な盗人にさらされる「攻撃面」を最小限に抑えることが目標となる。
【００４１】
ユーザが実行できるアクションが多いほど、あるいはこれらのアクションによってアクセス可能なリソースが多いほど、攻撃面は増大する。攻撃面が大きいほど、システムが攻撃されやすくなるため、システムのセキュリティは低下する。攻撃面を減らすことにより、攻撃の成功率が下がり、それによってシステムのセキュリティが高まる。
【００４２】
攻撃面を最小化する第１の方法は、非暗号化形態のデータへのアクセスを制限することである。これは、システムへの物理的なアクセスを制限することと、システムへの電子的なアクセスが持つ有用性を制限することによって実現できる。物理的なアクセス制御については、本発明の一部でないため、ここでは説明しない。電子的なアクセスによって取得したデータの潜在的な有用性は、暗号化を使用することと、非暗号化データの露出を最小限に抑えることとによって制限される。
【００４３】
本発明における非暗号化データは、暗号／復号鍵と、記述されるデータ値または読み出された値と、現在の検索比較値とに制限される。さらに、本発明は、非暗号化データを決して外部（ディスクなど）に記憶しない。
【００４４】
本発明は、可能であれば、保護されたＲＡＭを使用する。保護されたＲＡＭは、ディスクに書き込まれることがなく、内部メモリに固定されている。他のプログラムによるアクセスからＲＡＭのセキュリティを保護するために、可能であれば、アクセス制御などのハードウェアメモリ管理をさらに使用し得る。
【００４５】
順序データ構造内のエントリ（入力項目）をわかりにくくするために、鍵の「ソルト化」、鍵ビットの並べ替え、鍵ビットの拡張などの鍵難読化技法が使用され得る。なお、鍵の難読化は、検索データ構造内のエントリには適していないため、使用してはならない。
【００４６】
ハードウェアメモリ管理方式は、キーと暗号化／複合処理とをさらに保護する目的でも使用され得る。
【００４７】
暗号化／復号は、完了まで実行される保護された処理として実行され得る。このことは、別のタスクによるプリエンプションがない、すなわち、割り込みが許可されないことを示唆している。
【００４８】
加えて、悪意のあるタスクによるデータの復号を支援し得るようなものをメモリに何も残さないように、暗号化処理から復帰したらワーキングＲＡＭとレジスタとをクリアするのが望ましい。
【００４９】
暗号化／複合処理は、一部のオペレーティングシステムでさらなる保護を提供するＯ／Ｓサービスとしても実行され得る。
考え得る解決策
【００５０】
この問題を解決し得る２つの方法として、以下が検討された。
１．順序を保存する数学的な暗号化関数。このような関数ｆ（ｋ，ｄ）を機能させるためには、次の制約を満たす必要がある。
一意性：
ｆ（ｋ，ｄ）がすべての｛ｋ，ｄ｝に対して一意であること。
対称鍵（非対称鍵の場合でも定式化でき得る）：
すべての｛ｋ，ｄ｝についてｆ（ｋ，ｆ（ｋ，ｄ））＝ｄであること。
整列：
すべての｛ｋ，ｄ，ｅ｝についてｆ（ｋ，ｄ）＝ｆ（ｋ、ｅ）ｉｆｆ  ｄ＝ｅであること。
すべての｛ｋ，ｄ，ｅ｝についてｆ（ｋ，ｄ）＞ｆ（ｋ、ｅ）ｉｆｆ  ｄ＞ｅであること。
すべての｛ｋ，ｄ，ｅ｝についてｆ（ｋ，ｄ）＜ｆ（ｋ、ｅ）ｉｆｆ  ｄ＜ｅであり、式中、
ｋ＝暗号化／復号鍵
ｄ＝データ値
ｅ＝データ値であること。
【００５１】
これらの要件をすべて満たす関数は、データの非暗号化値が暗号解析によって発見されにくくなるように、暗号化を機能させる要素の一部が順序を狂わしてしまうことから、生成が困難または不可能な場合がある。
【００５２】
第１の解決策は実現性が低いため、以下に示す第２の手法が開発された。
２．ソートおよび検索のために順序は保存するが、非暗号化データは格納しないデータ構造。
データ構造は、一般にソートおよび検索に使用される（Ｄｏｎａｌｄ  Ｋｎｕｔｈ著「Ｔｈｅ  Ａｒｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｐｒｏｇｒａｍｍｉｎｇ，Ｖｏｌ．３：Ｓｏｒｔｉｎｇ  ａｎｄ  Ｓｅａｒｃｈｉｎｇ」を参照）。
【００５３】
本発明を具現化し得る構造は、いくつか案出できる。これらの構造はすべて、ストレージデータ構造１１０で暗号化列をインデックス化するための２つの同期させたデータ構造、具体的には、特定のデータ片をすばやく見つけるための検索データ構造１２２と、そのデータをソートするための順序データ構造１２８と、を維持することに依存している。各々の構造は、それぞれの目的を果たすために最適化されている。２つのデータ構造を使用してデータをインデックス化することにより、暗号化と、ソートおよび検索のしやすさとの両方が提供される。
【００５４】
データベーステーブルを作成する際（行と列、すなわちレコードとフィールドを有していれば、フラットファイルやＲＤＢＭＳなどの、アドレス指定可能な任意のデータ構造であって良い）、暗号化列ごとに、順序データ構造１２８と検索データ構造１２２という２つのデータ構造が作成される。
【００５５】
暗号化データの列ごとにこれらのデータ構造を保ち、データ暗号化を維持することにより、復号をほとんど、あるいはまったく必要とせずにソートと検索とを行うことができる。
【００５６】
順序データ構造と検索データ構造はともに、ポインタと暗号化データとを記憶するだけである。
【００５７】
順序データ構造１２８が非暗号化値によって編成されるのに対し、検索データ構造１２２は暗号化値によって編成される。
【００５８】
これらのデータ構造は、ローカルメモリまたは外部記憶装置に実装されるストレージデータ構造１１０にアクセスするためのインデックスとして使用される。ストレージデータ構造１１０は、行と列によってアドレス指定できる必要がある。各々の列アドレスと行アドレスとの交点には、１つの値が記憶される。
【００５９】
順序データ構造１２８を作成または更新する際、新規エントリと、順序データ構造１２８の１エントリという２つのデータ片だけは暗号化しないでおく必要がある。検索データ構造１２２についても同じ条件が該当する。これらのデータ群を復号する必要があるのは、画面表示、計算、またはレポート印刷の場合に限られる。他の操作事例ではいずれも、データが暗号化されたままである。
【００６０】
データ構造は、最小限のＡＰＩをサポートするだけで良く、厳密な実装形態はアプリケーション要件に依存する。
【００６１】
たとえば、順序データ構造１２８がスキップリスト構造で実装され得るのに対し、検索データ構造１２２は、平衡バイナリツリー、すなわちさらに別のスキップリストという形態であり得る。これらのデータ構造の各種実装形態については参考資料の中で十分に説明されているため、本明細書でこれ以上詳しくは説明しない。
【００６２】
他のデータ構造も可能であり、様々な動作効率を提供する。選択するデータ構造は、アプリケーションのニーズに依存する。必要なのはＡＰＩレベルにおける機能上の同等性だけである。
【００６３】
暗号化データの列ごとにこれらのデータ構造を保ち、データ暗号化を維持することにより、復号をほとんど、あるいはまったく必要とせずにソートと検索とを行うことができる。
【００６４】
順序データ構造１２８を作成または更新する際、新規エントリと、順序データ構造１２８の１エントリという２つのデータ片だけは暗号化しないでおく必要がある。
【００６５】
これらのデータ群を復号する必要があるのは、画面表示、計算、またはレポート印刷の場合に限られる。他の操作事例ではいずれも、データが暗号化されたままである。
効率に関する検討事項
【００６６】
暗号化／複合操作とインデックス更新とを最小限に抑えることが、本発明を効率良く機能させるための鍵である。
【００６７】
挿入操作は、順序データ構造１２８と検索データ構造１２２との両方を更新する必要があることから、演算オーバーヘッドが最も大きい。削除操作にも、同じように大きな演算オーバーヘッドが存在する。
【００６８】
更新操作は、順序データ構造１２８と検索データ構造１２２とに対する変更、ならびにストレージデータ構造１１０に対する変更を伴う。
【００６９】
マージ操作（merge operation:結合操作）は、本発明により、インデックス化されるデータ間でも、最小限の非暗号化データ露出で行うことができる。マージ処理中の２つのカレントレコードに存在する鍵フィールドのみ、マージの所定段階で復号する必要がある。
【００７０】
実装対象のデータ構造を選択することにより、このシステムの性能特性が決定される。どのデータ構造が選択されるかは、アプリケーションのニーズに依存する。
スケーラビリティ
【００７１】
本発明は拡張が容易であり、内部ソートでも外部ソートでも実装することができる。慎重に実装すれば、複数列ソートで必要とされるソートスケーラビリティが実現される。
利点
【００７２】
本発明は、他の解決策に勝る以下の利点を提供する。
１．オーバーヘッドが小さい。データを処理するのに必要な暗号化および復号操作が最小限に抑えられる。
２．ソフトウェアのみで解決され得る。アルゴリズム全体がソフトウェアで実装され得る。
３．ハードウェアの支援を受けてソフトウェアで実装され得る。アルゴリズムの重要部分の速度を上げるために、データ構造操作ハードウェアに加え、必要に応じて専用の暗号化・復号ハードウェアも使用され得る。
４．モジュール式の解決策である。本発明は、プラグインアーキテクチャを使用して、実装時の柔軟性を最大限に高める。アルゴリズムの一部が、残り部分の機能を妨げることなく取り替えられ得る。
５．暗号化データ列をインデックス化する目的で使用されるインデックス構造が、非暗号化データ列をインデックス化する目的でも使用することができるため、非暗号化データ列のソート速度が向上する。
６．本発明は拡張が容易であり、内部ソートでも外部ソートでも実装することができる。
７．本発明は、基底のオペレーティング・システム・アーキテクチャに依存せず、実装形態によっては、オペレーティング・システム・アーキテクチャとの直接的なやりとりさえ必要としない。
８．本発明は、基底のハードウェアアーキテクチャに依存しないが、利用可能なハードウェア機能を活かす形態で実装され得る。
９．本発明は、その実装形態で使用される言語に依存せず、特定の実装方法にふさわしいアセンブリ言語、解釈コード、あるいはより高水準のコンパイル言語で実装され得る。
１０．本発明は、関連付けられた使用記憶装置構造の形態に依存しない。
システムに依存しない機能定義
【００７３】
コンピュータサイエンスの慣例に倣い、ＡＰＩベースのシステムモデルについて説明する。インターフェイスの詳細と、インターフェイスが表す機能についてのみ詳述する。この手法により、実装形態を柔軟に選ぶことができる。複数の実装形態が可能であり、実装する側は、アプリケーションのニーズに応じて最適な実装形態を選ぶものと仮定する。
【００７４】
以降の説明は、データ構造に関するシステム非依存型の記述から成る抽象モデルの使用と、そのモデルでの操作とに基づく。これはオブジェクト指向の説明だが、オブジェクト指向の実装を示唆するものでも、要求するものでもない。
【００７５】
本発明の構造は、課題に固有の構造に続いて記載されている。本発明の好適な実装形態がプラグインアーキテクチャを使用して基本構造の安定性を保つのに対し、実装形態の詳細は必要に応じて自由に変更できる。
データ構造
【００７６】
本発明の好適な実装形態は、以下の抽象データ構造オブジェクトに基づく。
ストレージデータ構造
【００７７】
ストレージシステムのデータ構造によって実装されるストレージデータ構造１１０は、データベースに記憶されたデータのリポジトリである。
【００７８】
ストレージデータ構造１１０は、行と列によるアドレス指定が可能である。各々の列アドレスと行アドレスとの交点には、１つの値が記憶される。この値のサイズは実装依存なので、ここでは指定しない。
【００７９】
ストレージデータ構造１１０は、ローカルメモリまたは外部記憶装置で実装され得る。暗号化方法はいずれも本発明のプラグインアーキテクチャによって提供されるため、ストレージデータ構造１１０の実装形態が暗号化サポートを統合する必要はない。
順序データ構造
【００８０】
ＯｒｄｅｒＳｔｒｕｃｔｕｒｅデータ構造によって実装される順序データ構造１２８により、暗号化値間での範囲比較が可能となり、ソートがしやすくなる。
【００８１】
順序データ構造１２８は、検索鍵の非暗号化値によって順序付けられる。
【００８２】
順序データ構造１２８を作成または更新する際、新規エントリと、順序データ構造１２８の１エントリという２つのデータ片だけは非暗号化形態である必要がある。他の事例ではいずれも、データが暗号化された形態のままである。
【００８３】
順序データ構造１２８から特定の検索値を検索すると、その検索値を有するレコードのリストを保持するデータ構造エントリへのポインタか、あるいはその検索値が属する場所（新しいデータ構造エントリ挿入箇所）の前にあるデータ構造エントリへのポインタが返される。
【００８４】
値範囲の捜索は、順序データ構造１２８によって行われる。そのためには、順序データ構造１２８内の調査中エントリが、確定中の限度との比較のためにＲＡＭ内で一時的に復号される必要がある。
【００８５】
順序データ構造１２８におけるＡおよびＢの相対位置が見つかると、その間にあるレコードは、順序データ構造１２８をＡからＢへとトラバースする（traverse:入れ替える、検討する、考慮する）だけで検索することができる。
【００８６】
順序データ構造１２８はデータの非暗号化値に従ってソートされた順序に保たれているため、ソートはわずかで、順序データ構造１２８を適切な昇順または降順にトラバースするだけでソートできる。
検索データ構造
【００８７】
特定値の検索は、ＳｅａｒｃｈＳｔｒｕｃｔｕｒｅデータ構造によって実装された検索データ構造１２２により、検索対象データの暗号化値を検索鍵として使用して行われる。
【００８８】
検索データ構造１２２は、検索鍵の暗号化値によって順序付けられる。
【００８９】
検索データ構造１２２から特定の検索値を検索すると、その検索値を有するレコードのリストを保持するデータ構造エントリへのポインタか、あるいはその検索値が属する場所（新しいデータ構造エントリの挿入箇所）の前にあるデータ構造エントリへのポインタが返される。
データ型
【００９０】
本発明の好適な実装形態の操作では、次の抽象データ型が使用される。各々の型は実装依存である。これらの定義は、適切な実装形態を選択できるよう導くことを目的としており、その実装形態で必要な最低要件であるとみなすべきである。
ＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅ
【００９１】
このデータ型は、レコードの構造を、ＳｔｏｒａｇｅＳｔｒｕｃｔｕｒｅオブジェクトによって実装されるストレージデータ構造１１０に存在するものと定義する。このデータ型は、レコード内の列ごとに１エントリを格納している。
【００９２】
各々の列エントリは、アプリケーションのニーズによって判断される実装依存のデータであり得るとともに、その実装形態で利用可能なデータ型のものであり得る。これらのエントリは、単純値、値構造、あるいは単純値または値構造へのポインタであり得る。
ＲｅｃｏｒｄＩＤ
【００９３】
このデータ型は、一意のレコード識別子を定義する。このデータ型は、相対的な指数として実装されるのが一般的で、実装依存であるサイズを有する０ベースまたは１ベースの整数値である。
ＳｔｏｒａｇｅＡｄｄｒｅｓｓ
【００９４】
このデータ型は、ＳｔｏｒａｇｅＳｙｓｔｅｍオブジェクト内のレコードに付けられた一意の実装依存アドレスである。このデータ型は、単純値（相対的な記憶装置インデックスなど）、または値構造（デバイス、トラック、セクタ、オフセット、長さなど）であり得る。
ＯｒｄｅｒＥｎｔｒｙ
【００９５】
このデータ型は、ＯｒｄｅｒＳｔｒｕｃｔｕｒｅオブジェクト内のノードエントリの構造を定義する。このデータ型は実装依存だが、スキップリスト実装を想定した場合、各々のノードは、鍵エントリと、データエントリと、１もしくはそれ以上の正方向ポインタと、１もしくはそれ以上の逆方向ポインタとを一般に必要とする。
ＳｅａｒｃｈＥｎｔｒｙ
【００９６】
このデータ型は、ＳｅａｒｃｈＳｔｒｕｃｔｕｒｅ内のノードエントリの構造を定義する。このデータ型は実装依存だが、平衡バイナリツリー実装を想定した場合、各々のノードは、同じ鍵を有するＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅエントリを指し示すＲｅｃｏｒｄＩＤエントリの鍵エントリと、左ポインタと、右ポインタと、リストあるいはリストへのポインタとを一般に必要とする。
ＣｌｅａｒＶａｌｕｅＴｙｐｅ
【００９７】
このデータ型は、非暗号化値の構造を定義する。このデータ型は実装依存であり、単純値であり得るか、または値構造へのポインタであり得る。
ＥｎｃｒｙｐｔｅｄＶａｌｕｅＴｙｐｅ
【００９８】
このデータ型は、暗号化値の構造を定義する。このデータ型は実装依存であり、単純値であり得るか、または値構造へのポインタであり得る。
ＫｅｙＴｙｐｅ
【００９９】
このデータ型は、鍵値の構造を定義する。このデータ型は実装依存であり、単純値であり得るか、または値構造へのポインタであり得る。
ＡｌｇＴｙｐｅ
【０１００】
このデータ型は、暗号化アルゴリズムまたは復号アルゴリズムへのポインタである。ポインタは、適切なプラグイン暗号化アルゴリズムのアドレスを指定しなければならない。指定されたアルゴリズムは実装依存である。
ＥｒｒｏｒＣｏｄｅ
【０１０１】
このデータ型は、エラーコードの形態を定義する。このデータ型は実装依存であり、単純値であり得るか、または値構造へのポインタであり得る。
データベース管理システムとの統合
【０１０２】
本発明の統合先とならなければならないホストデータベース管理システムには、次の４つの操作領域がある。
セットアップ（ＤＢＭＳ  ＣＲＥＡＴＥ操作）
【０１０３】
データベースの初回作成時に、本発明用のサポートデータ構造を作成する必要がある。これは、ホストデータベース管理システムに与えられる、暗号化される列に関する情報に基づいて行われる。
起動
【０１０４】
ホストデータベース管理システムの起動時には、ユーザから暗号鍵を取得する必要がある。本明細書では指定しないが、これは安全な方法で行われる必要がある。
実行（ＤＢＭＳ  ＩＮＳＥＲＴ、ＤＥＬＥＴＥ、およびＳＥＬＥＣＴ操作）
【０１０５】
ホストデータベース管理システムの操作時には、本発明によって維持されるデータ構造を照会し、場合によっては更新する必要がある。
【０１０６】
これらの操作は、本節に続いて記載されている「ＡＰＩの詳細」でさらに指定されている。
停止
【０１０７】
本発明の停止は、すべての暗号鍵情報とワーキングメモリとをシステムメモリからクリアすることから成る。場合によってはワーキングメモリも含め、暗号鍵情報以外のすべての情報が暗号化形態であることから、本発明の操作を終了するにはそれらをクリアすれば必要十分である。
ＡＰＩの詳細
ＳｔｏｒａｇｅＳｙｓｔｅｍメソッド
【０１０８】
これらのメソッドは、ローカルメモリに、または外部記憶装置に実装され得るＳｔｏｒａｇｅＳｙｓｔｅｍオブジェクトにアクセスする目的で使用される。
ＲｅｃｏｒｄＩＤ  ｉｎｓｅｒｔ（
ＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅ  ｒｅｃｏｒｄＶａｌｕｅ）
【０１０９】
このメソッドは、ＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅのｒｅｃｏｒｄＶａｌｕｅパラメータをＳｔｏｒａｇｅＳｙｓｔｅｍオブジェクトに追加し、追加されたＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅのＳｔｏｒａｇｅＳｙｓｔｅｍオブジェクトにおける一意のアドレスを提供するＲｅｃｏｒｄＩＤを返す。
【０１１０】
ＳｔｏｒａｇｅＳｙｓｔｅｍオブジェクトがリクエストを満たせない場合には、ＮＵＬＬ値が返される。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅ  ｒｅａｄ（
ＲｅｃｏｒｄＩＤ  ｗｈｉｃｈＲｅｃｏｒｄ）
【０１１１】
このメソッドは、ＳｔｏｒａｇｅＳｙｓｔｅｍオブジェクト内の所定ＲｅｃｏｒｄＩＤに記憶されたＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅへのポインタを返す。ＲｅｃｏｒｄＩＤが無効の場合には、ＮＵＬＬポインタが返される。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ｂｏｏｌｅａｎ  ｕｐｄａｔｅ（
ＲｅｃｏｒｄＩＤ  ｗｈｉｃｈＲｅｃｏｒｄ，
ＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅ  ｒｅｃｏｒｄＶａｌｕｅ）
【０１１２】
このメソッドは、ｗｈｉｃｈＲｅｃｏｒｄパラメータによって指定されたＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅを、ｒｅｃｏｒｄＶａｌｕｅパラメータによってアドレス指定されたＲｅｃｏｒｄＳｔｒｕｃｔｕｒｅで置き換える。
【０１１３】
アップデートが成功した場合には、ｂｏｏｌｅａｎ値ｔｒｕｅが返される。アップデートが失敗した場合には、ｂｏｏｌｅａｎ値ｆａｌｓｅが返される。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ＳｔｏｒａｇｅＡｄｄｒｅｓｓ  ｃｏｎｖｅｒｔＩＤｔｏＡｄｄｒｅｓｓ（
ＲｅｃｏｒｄＩＤ  ｗｈｉｃｈＲｅｃｏｒｄ）
【０１１４】
このメソッドは、ｗｈｉｃｈＲｅｃｏｒｄによって指定されたＲｅｃｏｒｄＩＤに対応するＳｔｏｒａｇｅＡｄｄｒｅｓｓの実装依存値を返す。
ＲｅｃｏｒｄＩＤ  ｃｏｎｖｅｒｔＡｄｄｒｅｓｓＴｏＩＤ（
ＳｔｏｒａｇｅＡｄｄｒｅｓｓ  ｗｈｉｃｈＡｄｄｒｅｓｓ）
【０１１５】
このメソッドは、ｗｈｉｃｈＡｄｄｒｅｓｓによって指定されたＳｔｏｒａｇｅＡｄｄｒｅｓｓに対応するＲｅｃｏｒｄＩＤの実装依存値を返す。
ＥｒｒｏｒＣｏｄｅ  ｇｅｔＬａｓｔＥｒｒｏｒ（）
【０１１６】
このメソッドは、ストレージシステムで呼び出された最後のメソッドの失敗理由を示す値を返す。この値は実装固有であり、ここではこれ以上定義されない。
ＯｒｄｅｒＳｔｒｕｃｔｕｒｅメソッド
【０１１７】
これらのメソッドは、ＯｒｄｅｒＳｔｒｕｃｔｕｒｅオブジェクトと通信するためのＡＰＩを定義する。
ＯｒｄｅｒＥｎｔｒｙ  ａｄｄ（
Ｋｅｙ  Ｔｙｐｅ  ｃｏｌｕｍｎＫｅｙ，
ＣｌｅａｒＶａｌｕｅＴｙｐｅ  ｃｌｅａｒＫｅｙＶａｌｕｅ，
ＲｅｃｏｒｄＩＤ  ｗｈｉｃｈＲｅｃｏｒｄ）
【０１１８】
このメソッドは、ｗｈｉｃｈＲｅｃｏｒｄによって特定されたレコードを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用してｃｌｅａｒＫｅｙＶａｌｕｅによって指定された鍵値を有するＯｒｄｅｒＳｔｒｕｃｔｕｒｅオブジェクトに追加する。
【０１１９】
指定された鍵値を有するレコードがすでに存在する場合、新しいレコードはその鍵値を有するレコードのリストの末尾に追加され、追加されたエントリへのポインタが返される。このメソッドがレコードを追加できない場合には、ＮＵＬＬポインタが返され得る。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ｂｏｏｌｅａｎ  ｒｅｍｏｖｅ（ＫｅｙＴｙｐｅ  ｃｏｌｕｍｎＫｅｙ，
ＣｌｅａｒＶａｌｕｅＴｙｐｅ  ｃｌｅａｒＫｅｙＶａｌｕｅ，
ＲｅｃｏｒｄＩＤ  ｗｈｉｃｈＲｅｃｏｒｄ）
【０１２０】
このメソッドは、ｗｈｉｃｈＲｅｃｏｒｄによって特定された最初のレコードを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用してｃｌｅａｒＫｅｙＶａｌｕｅによって指定された鍵値を有するＯｒｄｅｒＳｔｒｕｃｔｕｒｅオブジェクトから除去する。
【０１２１】
削除が成功した場合には、ｂｏｏｌｅａｎ値ｔｒｕｅが返される。削除が失敗した場合には、ｂｏｏｌｅａｎ値ｆａｌｓｅが返される。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ｂｏｏｌｅａｎ  ｒｅｍｏｖｅ（
Ｋｅｙ  Ｔｙｐｅ  ｃｏｌｕｍｎＫｅｙ，
ＯｒｄｅｒＥｎｔｒｙ  ｗｈｉｃｈＥｎｔｒｙ）
【０１２２】
このメソッドは、ｗｈｉｃｈＥｎｔｒｙによって特定されたＯｒｄｅｒＥｎｔｒｙを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用してＯｒｄｅｒＳｔｒｕｃｔｕｒｅオブジェクトから除去する。
【０１２３】
削除が成功した場合には、ｂｏｏｌｅａｎ値ｔｒｕｅが返される。削除が失敗した場合には、ｂｏｏｌｅａｎ値ｆａｌｓｅが返される。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ＯｒｄｅｒＥｎｔｒｙ  ｆｉｎｄ（
Ｋｅｙ  Ｔｙｐｅ  ｃｏｌｕｍｎＫｅｙ，
ＣｌｅａｒＶａｌｕｅＴｙｐｅ  ｃｌｅａｒＫｅｙＶａｌｕｅ）
【０１２４】
このメソッドは、ｃｌｅａｒＫｅｙＶａｌｕｅによって指定されたＯｒｄｅｒＳｔｒｕｃｔｕｒｅオブジェクト内のＯｒｄｅｒＥｎｔｒｙを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用して見つける。
【０１２５】
見つかった場合には、ｃｌｅａｒＫｅｙＶａｌｕｅに対応する最初のＯｒｄｅｒＥｎｔｒｙへのポインタが返される。そのようなレコードが存在しない場合には、ＮＵＬＬポインタが返される。
ＯｒｄｅｒＥｎｔｒｙ  ｇｅｔＮｅｘｔＥｎｔｒｙ（
Ｋｅｙ  Ｔｙｐｅ  ｃｏｌｕｍｎＫｅｙ）
【０１２６】
このメソッドは、ＯｒｄｅｒＳｔｒｕｃｔｕｒｅオブジェクトにおける次のＯｒｄｅｒＥｎｔｒｙを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用して見つける。
【０１２７】
ｆｉｎｄ（）がＮＵＬＬを返した場合、すなわちリストにエントリが無くなった場合には、ＮＵＬＬポインタが返される。
ＥｒｒｏｒＣｏｄｅ  ｇｅｔＬａｓｔＥｒｒｏｒ（）
【０１２８】
このメソッドは、ＯｒｄｅｒＳｔｒｕｃｔｕｒｅオブジェクトで呼び出された最後のメソッドの失敗の理由を示す値を返す。この値は実装固有であり、ここではこれ以上定義されない。
ＳｅａｒｃｈＳｔｒｕｃｔｕｒｅメソッド
【０１２９】
これらのメソッドは、ＳｅａｒｃｈＳｔｒｕｃｔｕｒｅオブジェクトと通信するためのＡＰＩを定義する。
ＳｅａｒｃｈＥｎｔｒｙ  ａｄｄ（
ＫｅｙＴｙｐｅ  ｃｏｌｕｍｎＫｅｙ，
ＣｌｅａｒＶａｌｕｅＴｙｐｅ  ｃｌｅａｒＶａｌｕｅ，
ＲｅｃｏｒｄＩＤ  ｗｈｉｃｈＲｅｃｏｒｄ）
【０１３０】
このメソッドは、ｗｈｉｃｈＲｅｃｏｒｄによって特定されたレコードを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用してｃｌｅａｒＫｅｙＶａｌｕｅによって指定された鍵値を有するＳｅａｒｃｈＳｔｒｕｃｔｕｒｅオブジェクトに追加する。
【０１３１】
指定された鍵値を有するレコードがすでに存在する場合、新しいレコードはその鍵値を有するレコードのリストの末尾に追加され、追加されたエントリへのポインタが返される。このメソッドがレコードを追加できない場合には、ＮＵＬＬポインタが返され得る。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ｂｏｏｌｅａｎ  ｒｅｍｏｖｅ（
ＫｅｙＴｙｐｅ  ｃｏｌｕｍｎＫｅｙ，
ＣｌｅａｒＶａｌｕｅＴｙｐｅ  ｖａｌｕｅ，
ＲｅｃｏｒｄＩＤ  ｗｈｉｃｈＲｅｃｏｒｄ）
【０１３２】
このメソッドは、ｗｈｉｃｈＲｅｃｏｒｄによって特定されたレコードを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用してｃｌｅａｒＫｅｙＶａｌｕｅによって指定された鍵値を有するＳｅａｒｃｈＳｔｒｕｃｔｕｒｅオブジェクトから除去する。
【０１３３】
削除が成功した場合には、ｂｏｏｌｅａｎ値ｔｒｕｅが返される。削除が失敗した場合には、ｂｏｏｌｅａｎ値ｆａｌｓｅが返される。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ｂｏｏｌｅａｎ  ｒｅｍｏｖｅ（
ＫｅｙＴｙｐｅ  ｃｏｌｕｍｎＫｅｙ，
ＳｅａｒｃｈＥｎｔｒｙ  ｗｈｉｃｈＥｎｔｒｙ）
【０１３４】
このメソッドは、ｗｈｉｃｈＥｎｔｒｙで特定されたＳｅａｒｃｈＥｎｔｒｙを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用してＳｅａｒｃｈＳｔｒｕｃｔｕｒｅオブジェクトから除去する。
【０１３５】
削除が成功した場合には、ｂｏｏｌｅａｎ値ｔｒｕｅが返される。削除が失敗した場合には、ｂｏｏｌｅａｎ値ｆａｌｓｅが返される。リクエストの失敗理由は、下記ｇｅｔＬａｓｔＥｒｒｏｒ（）メソッドを使用して調査され得る。
ＳｅａｒｃｈＥｎｔｒｙ  ｆｉｎｄ（ＫｅｙＴｙｐｅ  ｃｏｌｕｍｎＫｅｙ，
ＣｌｅａｒＶａｌｕｅＴｙｐｅ  ｃｌｅａｒＶａｌｕｅ）
【０１３６】
このメソッドは、ｃｌｅａｒＫｅｙＶａｌｕｅによって指定されたＳｅａｒｃｈＳｔｒｕｃｔｕｒｅオブジェクト内のＳｅａｒｃｈＥｎｔｒｙを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用して見つける。
【０１３７】
見つかった場合には、ｃｌｅａｒＫｅｙＶａｌｕｅに対応する最初のＳｅａｒｃｈＥｎｔｒｙへのポインタが返される。そのようなレコードが存在しない場合には、ＮＵＬＬポインタが返され得る。
ＳｅａｒｃｈＥｎｔｒｙ  ｇｅｔＮｅｘｔＥｎｔｒｙ（
ＫｅｙＴｙｐｅ  ｃｏｌｕｍｎＫｅｙ）
【０１３８】
このメソッドは、ＳｅａｒｃｈＳｔｒｕｃｔｕｒｅオブジェクトにおける次のＳｅａｒｃｈＥｎｔｒｙを、ｃｏｌｕｍｎＫｅｙによって指定された暗号鍵を使用して見つける。
【０１３９】
リストにエントリが無くなった場合には、ＮＵＬＬポインタが返される。
ＥｒｒｏｒＣｏｄｅ  ｇｅｔＬａｓｔＥｒｒｏｒ（）
【０１４０】
このメソッドは、ＳｅａｒｃｈＳｔｒｕｃｔｕｒｅオブジェクトで呼び出された最後のメソッドの失敗理由を示す値を返す。
【０１４１】
返された値は実装固有であり、ここではこれ以上定義されない。
暗号化アルゴリズムメソッド
【０１４２】
これらのメソッドは、データを暗号化および復号する目的で使用されるアルゴリズム用のＡＰＩを指定する。
ＥｎｃｒｙｐｔｅｄＶａｌｕｅＴｙｐｅ  ｅｎｃｒｙｐｔ（
ＡｌｇＴｙｐｅ  ｅｎｃｒｙｐｔｏｒ，
ＫｅｙＴｙｐｅ  ｋｅｙＶａｌｕｅ，
ＣｌｅａｒＶａｌｕｅＴｙｐｅ  ｃｌｅａｒＶａｌｕｅ）
【０１４３】
このメソッドは、暗号鍵ｋｅｙＶａｌｕｅと、暗号化器によって指定されたプラグイン暗号化アルゴリズムとを使用して、ｃｌｅａｒＶａｌｕｅに対応する暗号化値を返す。
ＣｌｅａｒＶａｌｕｅＴｙｐｅ  ｄｅｃｒｙｐｔ（
ＡｌｇＴｙｐｅ  ｄｅｃｒｙｐｔｏｒ，
ＫｅｙＴｙｐｅ  ｋｅｙＶａｌｕｅ，
ＥｎｃｒｙｐｔｅｄＶａｌｕｅＴｙｐｅ  ｅｎｃｒｙｐｔｅｄＶａｌｕｅ）
【０１４４】
このメソッドは、復号鍵ｋｅｙＶａｌｕｅと、復号器によって指定されたプラグイン復号アルゴリズムとを使用して、ｅｎｃｒｙｐｔｅｄＶａｌｕｅに対応するクリア値を返す。
【０１４５】
ここで図に戻ると、以下の記載内容には、本発明を徹底的に理解してもらうために、説明目的で多数の具体的な詳細情報が記載されている。しかし、これらの具体的な詳細情報がなくとも本発明を実施し得ることは、当業者にとって明らかであろう。他の事例では、本発明を無用にわかりにくくすることを避けるために、公知の構造およびデバイスがブロック図形式で明示されている。たとえば、ある特定の実装形態が、実際には正逆両方向のポインタを使用し得るものの、リストデータ構造内の正方向ポインタだけが明示されている。
【０１４６】
本明細書の一部を成しており、本発明が実施され得る特定の実施形態が例示されている添付の図面を参照する。本発明の範囲を逸脱しない限り、他の実施形態が利用され得ることを理解すべきである。
【０１４７】
本発明を具現化するシステムは、特定の種類のストレージデータ構造１１０、検索データ構造１２２、または順序データ構造１２８に制限されない。ただし説明のために、本明細書で使用されている実施例および用語は、一般にリレーショナルデータベースと関連付けられているものとする。そのため、「テーブル」、「行」、「列」は、本明細書において、それぞれストレージデータ構造１１０、その構造内のレコード、そのレコード内のフィールドを言及する目的で使用される。関連するフィールドのグループがレコードに関連付けられる任意のデータ構造が使用され得る。
【０１４８】
以降、「ストレージデータ構造」１１０という用語は、ＡＰＩの説明の中で定義されたＳｔｏｒａｇｅＳｔｒｕｃｔｕｒｅを表し、「検索データ構造」１２２という用語は、ＡＰＩの説明の中で定義されたＳｅａｒｃｈＳｔｒｕｃｔｕｒｅを表し、「順序データ構造」１２８という用語は、ＡＰＩの説明の中で定義されたＯｒｄｅｒＳｔｒｕｃｔｕｒｅを表す。
【０１４９】
本発明の本質は、図１の概要に示すとおり、暗号操作の数を最小限に抑え、プロセッサの内部メモリに格納する非暗号化データを最小限に保ちながら、同期させた一対のインデックス１２０を使用して、ストレージデータ構造１１０で暗号化データの検索とソートと実行することにある。
【０１５０】
検索データ構造鍵およびポインタ構造１２４、ならびに順序データ構造鍵およびポインタ構造１３０における検索鍵値の内容は、暗号化された形態で保たれる。
【０１５１】
ストレージデータ構造１１０は、暗号化列と非暗号化（クリアテキスト）列との両方を格納しているデータベーステーブル１１２に、行と列とでアドレス指定された状態でデータを記憶する。
【０１５２】
データベーステーブル１１２は、少なくとも１つの暗号化列１１６を格納しており、０またはそれ以上の非暗号化クリアテキスト列１１４、１１８を格納している。
【０１５３】
各々の暗号化列１１６は、検索データ構造１２２と順序データ構造１２８とから成る一対の指数１２０によってインデックス化されている。
【０１５４】
検索データ構造１２２は、指定された検索鍵値を格納している特定の単数または複数のレコードを見つける目的で使用される。
【０１５５】
検索データ構造１２２内には、検索データ構造鍵およびポインタ構造１２４、ならびに関連付けられた検索データ構造レコードリスト１２６がある。
【０１５６】
検索データ構造鍵およびポインタ構造１２４は、それらに記憶された暗号化値によって順序が保たれる。
【０１５７】
検索データ構造鍵とポインタ構造１２４は、望ましい値を格納している第１の、あるいは唯一のレコードのレコード識別子を格納している検索データ構造レコードリスト１２６の位置を判断する目的で使用される。
【０１５８】
図２では、バイナリツリーを検索データ構造１２２の実装例として使用して、検索データ構造ルートポインタ２１０によって参照されるルートノード２１２から検索が始まり、望ましいデータ値を有するノードが見つかるまで、あるいは検索が失敗するまで、ツリーノードのバイナリ検索を続行する。
【０１５９】
検索データ構造１２２内に望ましい値が存在する場合には、その値を格納しているレコードを参照している順序データ構造レコードリスト２１４へのポインタが返される。
【０１６０】
一致するレコードが見つからない場合には、エラーコードが返される。
【０１６１】
望ましい値を格納しているレコードが複数存在する場合には、それらのレコードが、検索データ構造レコードリスト１２６内の以降のエントリによって参照される。
【０１６２】
順序データ構造１２８は、ストレージデータ構造１１０におけるレコードの範囲を選択する目的で使用される。
【０１６３】
順序データ構造１２８内には、順序データ構造鍵およびポインタ構造１３０、ならびに、関連付けられた一対の順序データ構造レコード・リスト・エントリ１３４、１３６を格納している順序データ構造レコードリスト１３２がある。
【０１６４】
順序データ構造鍵およびポインタ構造１３０は、それらに記憶された暗号化値によって順序が保たれる。
【０１６５】
順序データ構造鍵およびポインタ構造１３０は、望ましい最小の値を格納している第１の、あるいは唯一のレコードのレコード識別子を格納している順序データ構造レコード・リスト・エントリ１３４、および望ましい最大の値を格納している第１の、あるいは唯一のレコードのレコード識別子を格納している順序データ構造レコード・リスト・エントリ１３６の位置を判断する目的で使用される。
【０１６６】
図３では、Ｓｋｉｐ  Ｌｉｓｔを順序データ構造１２８の実装例として使用して、ルートノードポインタ３１０から検索が始まり、スキップインデックス３１４、３１５、３１６へと続行して、望ましい範囲を開始（３１８）し、終了（３２０）する鍵値を有する２つのエントリ３１８、３２０が見つかるまで継続する。
【０１６７】
順序データ構造レコードリスト１３２はその後、望ましい範囲内に含まれるレコードを検索するために、昇順または降順でトラバースされる。
【０１６８】
望ましい最小の値を格納しているレコードが複数存在する場合には、それらのレコードが、順序データ構造レコード・リスト・エントリ１３４内の以降のエントリによって参照される。
【０１６９】
望ましい最大の値を格納しているレコードが複数存在する場合には、それらのレコードが、順序データ構造レコード・リスト・エントリ１３６内の以降のエントリによって参照される。
【０１７０】
順序データ構造レコード・リスト・エントリ１３４内の１つまたは複数のレコードで始まり、順序データ構造レコード・リスト・エントリ１３６内の１つまたは複数のレコードで終わるレコードをトラバースすることにより、一群のレコードが昇順になる。
【０１７１】
順序データ構造レコード・リスト・エントリ１３６内の１つまたは複数のレコードで始まり、順序データ構造レコード・リスト・エントリ１３４内の１つまたは複数のレコードで終わるレコードをトラバースすることにより、一群のレコードが降順になる。
【０１７２】
新しいレコードがレコード・リスト・エントリ１３４、１３６のうちの一方に追加される場合、それらのレコードは、ソートの安定性を維持するようにそのリストエントリの末尾に追加される。
【０１７３】
順序データ構造１２８の一時的なコピーを作成することにより、複数列ソートが達成され得る。
【０１７４】
これらの一時的なコピーは、前の一時的なコピーの各々をトラバースすることによって作成され、最初のコピーは、最も重要度の低いソート列の順序データ構造１２８をトラバースすることによって作成される。
【０１７５】
図４は、データベーステーブルの作成時に実行されるステップを示している。
【０１７６】
ステップ４１０で空の順序データ構造１２８を作成し、ステップ４１２で、新しい暗号化列１１６ごとに空の検索データ構造１２２を作成する。
【０１７７】
なお、必要であれば、非暗号化列でのソートおよび検索の性能を高めるために、それらの列に対してさらなるインデックスデータ構造がセットアップされ得る。このインデックスデータ構造については、本発明の一部でないため、ここでは説明しない。
【０１７８】
図５は、データベーステーブルに新しいレコードを追加する際に実行されるステップを示している。
【０１７９】
新しいレコードごとに、以下を実行する：
１．０  暗号化フィールドごとに：
ステップ５１０で、挿入される検索データ構造１２２の列値を確認する：
ステップ５１２で、検索データ構造１２２にその列値が存在するか？
１．１  はい、存在する：
１．１ａ．ステップ５１４で、検索データ構造１２２が更新され、新しいレコードにリンクされる。
１．１ｂ．ステップ５１６で、順序データ構造１２８が更新され、新しいレコードにリンクにされる。
１．２  いいえ、存在しない：
１．２ａ．ステップ５１８で、順序データ構造１２８における列値の位置を特定する。
１．２ｂ．ステップ５２０で、順序データ構造１２８を更新して、暗号化列値と、ストレージデータ構造１１０におけるそのレコード位置とを有するエントリを格納する。
１．２ｃ．ステップ５２２で、検索データ構造１２２を更新して、ストレージデータ構造１１０におけるレコード位置などの、新しい暗号化列値のエントリを格納する。
２．０  ステップ５２４で、ストレージデータ構造１１０内のデータベーステーブル１１２に新しいレコードを挿入する。
【０１８０】
このステップでは、ストレージデータ構造１１０で記憶装置スペースを割り当て、ＲｅｃｏｒｄＩＤからＳｔｏｒａｇｅＡｄｄｒｅｓｓへのマッピングを作成し、レコードをストレージデータ構造１１０に挿入する。
【０１８１】
なお、挿入操作が既存のレコードの位置値との競合をもたらす場合には、順序データ構造１２８を再編成する必要性を低減するために、テッド・ネルソンの「Ｔｕｍｂｌｅｒｓ」などの、挿入可能な位置値が使用され得る。
【０１８２】
図６は、レコードの削除時に実行されるステップを示している。
【０１８３】
ステップ６１０で、そのレコードのインデックスエントリが検索データ構造１１０から除去される。
【０１８４】
ステップ６１２で、そのレコードのインデックスエントリが順序データ構造５１４から除去される。
【０１８５】
ステップ６１４で、そのレコードがストレージデータ構造１１０から除去される。
【０１８６】
当業者であれば十分に理解できるとおり、一部の詳細事項は、本発明が適用される特定のアプリケーションに依存する。次に、かかる特定の詳細事項について説明する。
【０１８７】
本発明では、データの大半が、計算、画面表示、またはレポート印刷の場合に限って復号する必要がある。本発明によるオーバーヘッド増は最小限であり、その操作はユーザに対して透過的となるように設計されている。
【０１８８】
本発明は、データの記憶方法に依存しないように設計されており、その実装形態は、統合先のシステムの詳細に依存する。
【０１８９】
本発明は、可能であれば、保護されたＲＡＭを使用する。保護されたＲＡＭは、ディスクに書き込まれることがなく、内部メモリに固定されている。他のプログラムによるアクセスからＲＡＭのセキュリティを保護するために、可能であれば、アクセス制御などのハードウェアメモリ管理をさらに使用し得る。
【０１９０】
順序データ構造内のエントリをわかりにくくするために、鍵の「ソルト化」、鍵ビットの並べ替え、鍵ビットの拡張などの鍵難読化技法が使用され得る。なお、鍵の難読化は、検索データ構造内のエントリには適していないため、使用してはならない。
【０１９１】
ハードウェアメモリ管理方式は、キーと暗号化／複合処理とをさらに保護する目的でも使用され得る。
【０１９２】
暗号化／復号は、完了まで実行される保護された処理として実行され得る。このことは、割り込みが許可されないなど、別のタスクによるプリエンプションがないことを示唆している。
【０１９３】
加えて、悪意のあるタスクによるデータの復号を支援し得るようなものをメモリに何も残さないように、暗号化処理から復帰したらワーキングＲＡＭとレジスタとをクリアするのが望ましい。
【０１９４】
暗号化／複合処理は、一部のオペレーティングシステムでさらなる保護を提供するＯ／Ｓサービスとしても実行され得る。
【０１９５】
データ構造は、最小限のＡＰＩをサポートするだけで良く、厳密な実装形態はアプリケーション要件に依存する。
【０１９６】
たとえば、順序データ構造１２８がスキップリスト構造で実装され得るのに対し、検索データ構造１２２は、平衡バイナリツリー、すなわちさらに別のスキップリストという形態であり得る。
【０１９７】
他のデータ構造も可能であり、様々な動作効率を提供する。選択するデータ構造は、アプリケーションのニーズに依存する。必要なのはＡＰＩレベルにおける機能上の同等性だけである。
【０１９８】
暗号化データの列ごとにこれらのデータ構造を保ち、データ暗号化を維持することにより、復号をほとんど、あるいはまったく必要とせずにソートと検索とを行うことができる。
【０１９９】
順序データ構造１２８を作成または更新する際、新規エントリと、順序データ構造１２８の１エントリという２つのデータ片だけは暗号化しないでおく必要がある。
【０２００】
これらのデータ群を復号する必要があるのは、画面表示、計算、またはレポート印刷の場合に限られる。他の操作事例ではいずれも、データが暗号化されたままである。
【０２０１】
実装対象のデータ構造を選択することにより、このシステムの性能特性が決定される。どのデータ構造が選択されるかは、アプリケーションのニーズに依存する。
【０２０２】
好適な実施形態において、かつ当業者によって容易に理解されるとおり、本発明にかかる機器は、上記のステップを実施するコンピュータソフトウェアでプログラミングされた汎用または特定用途のコンピュータあるいは分散システムを含み、コンピュータソフトウェアは、Ｃ＋＋、ＦＯＲＴＲＡＮ、ＢＡＳＩＣ、Ｊａｖａ（登録商標）、アセンブリ言語、マイクロコード、配信されたプログラミング言語など、任意の適切なコンピュータ言語であり得る。この機器は、各種ハードウェア実装形態における（インターネットおよび／または１つもしくはそれ以上イントラネット経由などで接続された）複数のかかるコンピュータ／分散システムも含み得る。たとえば、データ処理は、適切にプログラムされたマイクロプロセッサ、クラウドコンピューティング、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）などにより、適切なメモリ、ネットワーク、およびバス要素と組み合わせて実行することができる。
【０２０３】
なお、明細書およびクレームにおいて、「概ね」または「約」は、引用された数量の２０パーセント（２０％）以内を意味する。本明細書に開示されたコンピュータソフトウェアは、ＣＤ−ＲＯＭと、ＤＶＤ−ＲＯＭと、ハードドライブ（ローカルまたはネットワークストレージ装置）と、ＵＳＢキーと、他のリムーバブルドライブと、ＲＯＭと、ファームウェアとを含むが、それらに限定されない任意の非一時的なコンピュータ可読媒体（媒体の組み合せを含む）で具現化され得る。
【０２０４】
本発明について、上記好適な実施形態を特に参照しながら詳述してきたが、他の実施形態でも同じ結果を成し遂げることができる。当業者にとっては本発明の変形および変更が明らかであり、かかる変更および均等物は、添付の請求項で網羅することが意図される。引用した上記すべての参考資料、アプリケーション、特許、および出版物の開示内容は、参照により本明細書に援用される。
【図１】
0006049699.tif 000002
【図２】
0006049699.tif 000003
【図３】
0006049699.tif 000004
【図４】
0006049699.tif 000005
【図５】
0006049699.tif 000006
【図６】
0006049699.tif 000007