(57)【要約】【課題】データベースに電子透かしを埋め込む技術を提供する。【解決手段】秘密の情報を使用して、ビット・パターンを確立することによって、データベースのセキュリティを向上させるための方法およびシステム。このパターンは、秘密の情報を使用することだけによって、データベースの（許可された、または未許可の）コピー内で検出され得る透かしを確立する。
2005531828.tif 000002
【特許請求の範囲】
【請求項１】
複数のタプルを含むデータ・レポジトリに電子透かしを入れるためのコンピュータであって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該コンピュータは、少なくとも１つのプロセッサを含み、当該プロセッサは、
透かしを確立するために、秘密の情報に基づいて、前記タプルの少なくともいくつかの、少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立することを含む方法動作を実行する。
【請求項２】
マークされるタプル、タプル内でマークされる属性、属性内でマークされるビット位置、および特定ビットの透かし値のうちの少なくとも１つ、少なくとも２つ、またはすべてが前記秘密の情報に基づいて判断される、請求項１に記載のコンピュータ。
【請求項３】
数字属性内のビット位置だけが、前記透かしの一部である、請求項１に記載のコンピュータ。
【請求項４】
前記透かし値の少なくとも一部は、少なくとも前記秘密の情報の一方向ハッシュ関数に基づいて確立される、請求項１に記載のコンピュータ。
【請求項５】
複数のタプルを含むデータ・レポジトリ内に透かしが存在するかどうかを判断するためのコンピュータであって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該コンピュータは少なくとも１つのプロセッサを含み、当該プロセッサは、
テスト・データ構造体を受信すること、および
前記テスト・データ構造体内に前記透かしが存在するかどうかを判断することを含む。
【請求項６】
前記判断動作が、前記テスト・データ構造体内に、前記透かしが所定の確率内で存在するかどうかを判断することによって行われる、請求項５に記載のコンピュータ。
【請求項７】
複数のタプルを含むデータ・レポジトリに電子透かしを入れるためのコンピュータ・プログラムであって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該コンピュータ・プログラムはコンピュータ上で実行されたとき、
透かしを確立するために、秘密の情報に基づいて、前記タプルの少なくともいくつかの、少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立するステップを実施する、プログラム・コード手段を含む。
【請求項８】
透かし値を確立する前記ステップは、
秘密の情報に基づいて、マークされる複数のタプルを判断するステップと、
マークされる各タプル内で、マークされる少なくとも１つの属性を判断するステップと、
マークされる各属性内で、マークされる少なくとも１つのビットを判断するステップと、
透かしを確立するために、少なくともマークされる各非ヌル・ビットの透かし値を確立するステップとを含む、請求項７に記載のコンピュータ・プログラム。
【請求項９】
複数のタプルを含むデータ・レポジトリに電子透かしを入れるための方法であって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、
当該方法は、透かしを確立するために、秘密の情報に基づいて、前記タプルの少なくともいくつかの、少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立するステップを含む。
【請求項１０】
透かし値を確立する前記ステップは、
秘密の情報に基づいて、前記データ・レポジトリ内のマークされる複数のタプルを判断すること、
マークされる各タプル内で、マークされる少なくとも１つの属性を判断すること、
マークされる各属性内で、マークされる少なくとも１つのビットを判断すること、および
透かしを確立するために、少なくともマークされる各非ヌル・ビットの透かし値を確立することをさらに含む、請求項９に記載の方法。
【請求項１１】
複数のタプルを含むデータ・レポジトリ内に透かしが存在するかどうかを判断するためのコンピュータ・プログラムであって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該コンピュータ・プログラムは、コンピュータ上で実行されたとき、
テスト・データ構造体を受信するステップと、
前記テスト・データ構造体内に前記透かしが存在するかどうかを判断するステップとを実行する、プログラム・コード手段を含む。
【請求項１２】
前記受信ステップが、タプルを含むテスト・データ構造体を受信し、前記判断ステップが、
それぞれのタプルについて、前記タプルが秘密の情報に基づいてマークされたはずかどうかを判断すること、
マークされたはずの各タプル内の少なくとも１つの属性について、前記属性がマークされたはずかどうかを判断すること、
マークされたはずの各属性内の少なくとも１つのビットについて、前記ビットがマークされたはずかどうかを判断すること、および
マークされたはずの各ビットについて、透かし値を判断して、前記テスト・データ構造体が透かしを含むかどうかを判断することを含む、請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
コンピュータ上で実行されたときに、
正確なビット値のカウント数を維持するステップと、
前記カウント数に基づいて、前記テスト・データ構造体内に前記透かしが存在するかどうかを判断するステップとを実施するプログラム・コード手段をさらに含む、請求項１２に記載のコンピュータ・プログラム。
【請求項１４】
複数のタプルを含むデータ・レポジトリ内に透かしが存在するかどうかを判断するための方法であって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該方法は、
テスト・データ構造体を受信するステップと、
前記テスト・データ構造体内に前記透かしが存在するかどうかを判断するステップとを含む。
【請求項１５】
前記判断ステップが、
前記テスト・データ構造体内のそれぞれのタプルについて、前記タプルが秘密の情報に基づいてマークされたはずかどうかを判断すること、
マークされたはずの各タプル内の少なくとも１つの属性について、前記属性がマークされたはずかどうかを判断すること、
マークされたはずの各属性内の少なくとも１つのビットについて、前記ビットがマークされたはずかどうかを判断すること、および
マークされたはずの各ビットについて、透かし値を判断して、前記テスト・データ構造体が透かしを含むかどうかを判断することを含む、請求項１４に記載の方法。
【請求項１６】
それぞれが少なくとも１つの属性を含む複数のタプルであって、各属性が、ビット値をもつ少なくとも１つのビットを含むタプルと、
秘密の情報に基づいて確立される、ビット間の値のパターンとを含むデータ・レポジトリ。
【請求項１７】
少なくともいくつかの属性が主キーを有し、属性の前記主キーを使用して、透かし値を確立する、請求項１６に記載のデータ・レポジトリ。
【請求項１８】
少なくとも第１の属性が主キーを有しておらず、第１の属性のビット区画を使用して、透かし値を確立する、請求項１６に記載のデータ・レポジトリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ・レポジトリのセキュリティに関する。
【背景技術】
【０００２】
ソフトウェア、画像、動画、音声、テキストなどデジタル資産の著作権侵害は、こうした資産の所有者にとって長い間問題となっている。こうした資産の保護は通常、電子透かしをデータに挿入することにより行われる。透かし挿入のソフトウェアは、透かしを入れる対象物に、小さいエラーを組み込む。こうした意図的なエラーは、マークと称され、それらが統合され、透かしを構成する。マークは、データの有用性に、大きな影響を及ぼしてはならないが、データの有用性を損なわない限り、悪意のあるユーザが、それを破壊することができないように挿入しなければならない。したがって、透かしによって、コピー行為そのものは防止されないが、再配布されるコピーの本来の所有権を証明するための手段を提供することによって、不法コピーが抑止される。
【０００３】
「ファイヤウォールの外側において、アプリケーションによるデータベースを用いたデータ処理がますます行われるようになると、データベースにも同様に透かしを入れることの必要性が生じている。たとえば、半導体業界では、半導体部品に関するパラメータ・データが、主に３つの企業、アスペクト社（Aspect）、アイエイチエス社（ＩＨＳ）およびアイシー・マスタ社（IC Master）によって提供されている。それらはすべて、人海戦術で、データベースから手作業で部品仕様を抽出し、パラメータのデータベースを構築する。次いで、それらは、こうしたデータベースを、設計技術者に、高価な価格でライセンス供与する。他にもアクシオム社（Acxiom）のような企業は、消費者および企業データの大規模な収集をまとめてきた。また生命科学業界では、セレラ社（Celera）などの企業の主な資産は、生物学的情報のデータベースである。インターネットは、ユーザが遠隔でデータベースの検索およびアクセスを行えるようにする（しばしばｅユーティリティーズ（e-ulilities）またはウェブ・サービスと称される）サービスを作り出す、こうしたデータ・プロバイダに対して、非常に大きな悩みの種となっている。この動向は、エンドユーザにとっては恩恵であるが、データ・プロバイダをデータ盗用の脅威にさらしている。
【０００４】
データベースとの関連では、データベースに透かしを入れる技法、マルチメディア・データに透かしを入れるための技法では別の課題がもたらされ得る。こうした透かしを入れるための技法の大部分は、当初、静止画のために開発され、後に、動画および音声リソースに拡張されたものである。この点で理解される２つの適用場面の違いは、以下を含む。
１．マルチメディア・オブジェクトは、多数のビットからなり、かなりの冗長性を有する。したがって、その透かしは、十分隠れる。一方、データベース・リレーション（database relation）は、それぞれが別個のオブジェクトである複数のタプルで構成される。透かしは、こうした別個のオブジェクト全体に広められなければならない。
２．マルチメディア・オブジェクトの様々な部分の部分的／一時的な相対的位置決めは一般に、変化しない。一方、リレーションのタプルは、セットを構成し、それらの間に、暗黙の順序付けは存在しない。
３．オブジェクトの知覚的変化を引き起こさずに、マルチメディア・オブジェクトの一部を、任意にドロップしまたは置き換えることはできない。しかし、リレーションの違法コピー行為では、単にデータベースの部のタプルがドロップされ、または他のリレーションからのタプルでそれが置き換えらえる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
こうした違いのために、マルチメディア・データ用に開発された技法を、リレーションに透かしを挿入するために使用することはできない。同様に、フォーマットされたテキストの特殊なプロパティを活用するテキスト用透かし挿入技法は、データベースに容易に適用することができない。さらに、ソフトウェアに透かしを入れるための技法の成功は、限られてきた。それは、コンピュータ・プログラムの命令がしばしば、プログラムのセマンティクスを変更せずに、再構成され得るからである。しかし、この順序付けの変更によって、透かしが破壊され得る。
【課題を解決するための手段】
【０００６】
したがって、本発明は、複数のタプルを含むデータ・レポジトリに電子透かしを入れるためのコンピュータであって、各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含むコンピュータを提供する。このコンピュータは、少なくとも１つのプロセッサを含み、このプロセッサは、透かしを確立するために、秘密の情報（private information）に基づいて、タプルの少なくともいくつかの、少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立することを含む方法動作を実行する。
【０００７】
好ましくは、本発明は、違法なデータ・コピーを識別するために使用され得る。
【０００８】
好ましくは、透かしが挿入され得るデータベースは、その値の一部の変更がアプリケーションに影響を及ぼさない属性を含む。使いやすさを損なわずに、少量のエラーを許容し得る実世界のデータセットが存在する。たとえば、天気予測モデルの構築に使用される、ＡＣＡＲＳ気象データは、１．８ｍ／ｓ、および０．５Ｃの範囲内になるようにそれぞれ予測される、風ベクトルおよび気温の精度を有する。好ましい一実施形態による本発明は、透かし挿入によってもたらされるエラーを、こうしたデータの測定許容範囲内にあるように容易に制限することができると認識する。別の例として、様々なデータ・マイニング技法を使用して分析されている、実験的に取得された遺伝子表現のデータセットについて考えてみる。この場合でも、好ましい一実施形態による本発明は、データ収集および分析技法の本質は、少しのデータ値の変更が結果に影響を及ぼす見込みはないと認識する。同様に、消費財企業の顧客セグメンテーションの結果は、補足データの外部プロバイダが、わずかな取引からのいくらかを追加しまたは減らす場合に、影響を受けない。最後に、上述の半導体部品に関するパラメータ・データについて考えてみる。多数のパラメータについて、透かし挿入によってもたらされるエラーを、測定許容範囲内になるようにすることができる。
【０００９】
データ・レポジトリは、たとえば、ファイル・システム、データベース、または他のレコード・ストアであり得る。好ましくは、コンピュータは、透かしを定義するビット・パターンを確立するために、秘密の情報に基づいて、一部のタプルの一部の属性内の、ビット位置の透かし値を確立する。
【００１０】
好ましい一実施形態では、数字属性内のビット位置だけが、透かしの一部である必要がある。好ましくは、透かし値は、少なくとも秘密の情報の一方向ハッシュ関数に少なくとも一部には基づいて確立される。
【００１１】
好ましい一実施形態によれば、コンピュータは、透かしが挿入されたデータベースからコピーされたものであると疑われるテスト・データベースが、実際に、透かしを含むかどうかを判断することができる。秘密の情報を使用して、好ましくは、コンピュータは、テスト・データ構造体内に、透かしが所定の確率内で存在するかどうかを判断する。
【００１２】
好ましくは、タプルを含むテスト・データ・レポジトリ内に、透かしが存在するかどうかを判断するための汎用コンピュータが提供される。好ましくは、秘密の情報を使用して、テスト・データ構造体内に、透かしが存在するかどうかを判断する。
【００１３】
ある実施形態では、マークされるタプル、タプル内でマークされる属性、属性内でマークされるビット位置、および特定ビットの透かし値のうちの少なくとも１つが、秘密の情報に基づいて判断される。
【００１４】
ある実施形態では、マークされるタプル、タプル内でマークされる属性、属性内でマークされるビット位置、および特定ビットの透かし値のうちの少なくとも２つが、秘密の情報に基づいて判断される。
【００１５】
ある実施形態では、マークされるタプル、タプル内でマークされる属性、属性内でマークされるビット位置、および特定ビットの透かし値のうちのすべてが、秘密の情報に基づいて判断される。
【００１６】
好ましくは、数字属性内のビット位置だけが、透かしの一部である。
【００１７】
好ましくは、透かし値の少なくとも一部は、少なくとも秘密の情報の一方向ハッシュ関数に基づいて確立される。
【００１８】
好ましくは、テスト・データ構造体を受信し、少なくとも一部には秘密の情報を使用して、テスト・データ構造体内に、透かしが存在するかどうかを判断することが可能である。
【００１９】
好ましくは、テスト・データ構造体内に、透かしが所定の確率内で存在するかどうかを判断する。
【００２０】
ある実施形態では、マークされるタプル、タプル内でマークされる属性、属性内でマークされるビット位置、および特定ビットの透かし値のうちの少なくとも１つ、少なくとも２つ、またはすべてが秘密の情報に基づいて判断される。
【００２１】
ある態様によれば、本発明は、複数のタプルを含むデータ・レポジトリ内に透かしが存在するかどうかを判断するためのコンピュータであって、各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含むコンピュータを提供する。このコンピュータは、少なくとも１つのプロセッサを含み、このプロセッサは、テスト・データ構造体を受信し、少なくとも一部には秘密の情報を使用して、テスト・データ構造体内に透かしが存在するかどうかを判断することを含む方法動作を実行する。
【００２２】
好ましくは、テスト・データ構造体内に、透かしが、所定の確率内で存在するかどうかが判断される。
【００２３】
好ましくは、テスト・データ構造体が導出されたデータ・レポジトリについて、透かし値が、タプルの一部の属性の一部の、少なくともいくつかのビット位置について、秘密の情報に基づいて確立される。
【００２４】
好ましい一実施形態によれば、コンピュータ・プログラム装置が提供され、このコンピュータ・プログラム装置は、デジタル処理装置によって読取り可能なコンピュータ・プログラム記憶装置、ならびにデータ・レポジトリのセキュリティを向上させるために、デジタル処理装置によって実行可能な命令を含む、プログラム記憶装置内のプログラムを含む。このプログラムは、マークされる複数のタプルを、秘密の情報に基づいて判断する手段と、マークされる各タプル内でマークされる少なくとも１つの属性を判断する手段と、マークされる各属性でマークされる少なくとも１つのビットを判断する手段と、透かしを確立するために、少なくともマークされる各非ヌル・ビットの透かし値を確立する手段とを含む。
【００２５】
好ましい一実施形態によれば、秘密の情報を使用して、データ・レポジトリ全体にわたって、ビット値のパターンを確立することを含む、データ・レポジトリのセキュリティを向上させるための方法が提供される。
【００２６】
好ましくは、データ・レポジトリ内のマークされる複数のタプルは、秘密の情報に基づいて判断される。
【００２７】
好ましくは、マークされる各タプル内のマークされる少なくとも１つの属性が判断される。
【００２８】
好ましくは、マークされる各属性内のマークされる少なくとも１つのビットが判断される。
【００２９】
好ましくは、透かしの確立のため、少なくともマークされる各非ヌル・ビットについて、透かし値が確立される。
【００３０】
好ましい一実施形態によれば、コンピュータ・プログラム装置が提供され、このコンピュータ・プログラム装置は、デジタル処理装置によって読取り可能なコンピュータ・プログラム記憶装置、ならびにデジタル処理装置によって実行可能な命令を含む、プログラム記憶装置内のプログラムを含む。このプログラムは、タプルを含むテスト・データ構造体を受信する手段と、各タプルについて、タプルが秘密の情報に基づいてマークされたはずかどうかを判断する手段と、マークされたはずの各タプル内の少なくとも１つの属性について、属性がマークされたはずかどうかを判断する手段と、マークされたはずの各属性内の少なくとも１つのビットについて、ビットがマークされたはずかどうかを判断する手段と、マークされたはずの各ビットの透かし値を判断して、テスト・データ構造体が透かしを含んでいるかどうかを判断する手段とを含む。
【００３１】
好ましくは、数字属性のビット位置だけが、透かしの一部であることがテストされる。
【００３２】
好ましくは、正確なビット値のカウント数を維持し、そのカウント数に基づいて、テスト・データ構造体内に透かしが存在するかどうかを判断することが可能である。
【００３３】
好ましくは、透かし値は、少なくとも秘密の情報の一方向ハッシュ関数に、少なくとも一部には基づいて判断される。
【００３４】
好ましい一実施形態によれば、秘密の情報を使用して、テスト・データ構造体内に、値のパターンが存在するかどうかを判断することを含む方法が提供される。
【００３５】
好ましくは、テスト・データ構造体内の各タプルについて、秘密の情報に基づいて、タプルがマークされたはずかどうかが判断される。
【００３６】
好ましくは、マークされたはずの各タプル内の少なくとも１つの属性について、属性がマークされたはずかどうかが判断される。
【００３７】
好ましくは、マークされたはずの各属性内の少なくとも１つのビットについて、ビットがマークされたはずかどうかが判断される。
【００３８】
好ましくは、マークされたはずの各ビットについて、透かし値を判断して、テスト・データ構造体が透かしを含むかどうかが判断される。
【００３９】
ある実施形態では、少なくともいくつかの属性は、主キーを含み、属性の主キーを使用して、透かし値を確立する。
【００４０】
ある実施形態では、少なくとも第１の属性は、主キーを含まず、第１の属性のビット区画を使用して、透かし値を確立する。
【００４１】
ある実施形態では、少なくともいくつかの属性は、主キーを含み、属性の主キーを使用して、ビット値を確立する。
【００４２】
ある態様によれば、本発明は、複数のタプルを含むデータ・レポジトリに透かしを入れるための方法であって、各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含む方法を提供する。この方法は、秘密の情報に基づいて、タプルの少なくともいくつかの少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立するステップを含む。
【００４３】
別の態様によれば、複数のタプルを含むデータ・レポジトリ内に、透かしが存在するかどうかを判断するためのコンピュータ・プログラムであって、各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含むコンピュータ・プログラムが提供される。このコンピュータ・プログラムは、コンピュータ上で実行されたときに、テスト・データ構造体を受信するステップと、少なくとも一部には秘密の情報を使用して、テスト・データ構造体内に透かしが存在するかどうかを判断するステップとを実施するプログラム・コード手段を含む。
【００４４】
別の態様によれば、複数のタプルを含むデータ・レポジトリ内に、透かしが存在するかどうかを判断するための方法であって、各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含む方法が提供される。この方法は、テスト・データ構造体を受信するステップと、少なくとも一部には秘密の情報を使用して、テスト・データ構造体内に透かしが存在するかどうかを判断するステップとを含む。
【００４５】
別の態様によれば、複数のタプルを含むデータ・レポジトリに透かしを入れるためのコンピュータ・プログラムであって、各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含むコンピュータ・プログラムが提供される。このコンピュータ・プログラムは、コンピュータ上で実行されたときに、透かしを確立するために、秘密の情報に基づいて、タプルの少なくともいくつかの少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立するステップを実施するプログラム・コード手段を含む。
【００４６】
別の態様によれば、それぞれが少なくとも１つの属性を含み、それぞれの属性が、ビット値をもつ少なくとも１つのビットを含む複数のタプルと、秘密の情報に基づいて確立されるビット間の値パターンとを含むデータ・レポジトリが提供される。
【００４７】
次に、本発明の好ましい一実施形態について、例示するためだけに、以下の図面を参照して説明する。
【発明を実施するための最良の形態】
【００４８】
最初に図１を参照すると、全体的に符号１０で示されるシステムが示されている。図示するように、システム１０は、ファイル・システムや、図１に示す例示的な実施形態内のリレーショナル・データベース１４などのデータ構造体またはレポジトリにアクセスする、コンピュータ１２を含む。したがって、コンピュータ１２は、リレーショナル・データベース管理システムをホストし得る。図２および３に示す論理を実施するために、コンピュータ１２上で、透かしアプリケーション１６が実行され得る。
【００４９】
例示的また非限定的な実施形態では、透かしアプリケーション１６は、Ｊａｖａ（Ｒ）（商標）で書かれたユーザ定義関数であり得る。コンピュータ１２は、Ｊａｖａ（Ｒ）（商標）データベース・コネクティビティ（ＪＤＢＣ（商標）コネクティビティ）を使用して、ＤＢ２（Ｒ）Universal Database（商標）（ＵＤＢ）バージョン７を実行する、Ｗｉｎｄｏｗｓ（Ｒ）ＮＴ（Ｒ）バージョン４．００ワークステーションであり得る。それだけに限らないが、メイン・フレーム・コンピュータ、ラップトップ、デスクトップ、およびノートブック・コンピュータを含めて、他のタイプのコンピュータが、他のタイプのデータベースと同様に使用され得る。（Ｊａｖａ（Ｒ）、すべてのＪａｖａ（Ｒ）ベースのロゴ、およびＪＤＢＣは、米国、他の国々、またはその両方のサン・マイクロシステムズ社（SunMicrosystems Inc）の商標であり、Ｗｉｎｄｏｗｓ（Ｒ）ＮＴは、米国、他の国々、またはその両方のマイクロソフト社（MicrosoftCorporation）の登録商標であり、またＤＢ２、およびＤＢ２  Ｕｎｉｖｅｒｓａｌ  Ｄａｔａｂａｓｅは、米国、他の国々、またはその両方のインターナショナル・ビジネス・マシーンズ社（InternationalBusiness Machines Corporation）の登録商標である。）
【００５０】
例示するために、図１に、データ・レポジトリ（データベース１４など）がタプル１８を含み、それぞれのタプル１８が１つまたは複数の属性２０を含むことを示す。それぞれの属性２０は、１つまたは複数のデータ・ビット２２を含むことができ、それぞれのビット２２は、たとえば「０」または「１」（あるいは場合によっては、ヌル：null）である値２４を含む。好ましい実施形態では、秘密の情報にアクセスする以外には、結果的には検出され得ない秘密の情報を用いて、ビット値のパターン、またはそれよりは好ましくないが、データベースの属性値のパターンなど、値のパターンが確立される。
【００５１】
このアーキテクチャーについての上記概要に留意して、ここでの論理は、以下で論じるフロー・チャートに従って、図１に示すアーキテクチャー上で実行されることを理解されたい。本明細書では、フロー・チャートは、コンピュータ・プログラム・ソフトウェア内で実施される、好ましい実施形態の論理の構造を示す。フロー・チャートは、好ましい実施形態に従って機能する、コンピュータ・プログラム・コード要素または電子論理回路などの論理要素の構造を示すことが当業者には理解されよう。好ましくは、マシン・コンポーネントは、デジタル処理装置（すなわちコンピュータ）に、図示する内容に対応する機能ステップのシーケンスを実施するよう命令する形で、論理要素を表現する。
【００５２】
換言すれば、論理は、一連のコンピュータ実行可能命令として、プロセッサによって実行されるコンピュータ・プログラムによって実施され得る。こうした命令は、たとえば、ＲＡＭ、ハード・ドライブまたは光ドライブ内に常駐することができ、あるいは、命令は、磁気テープ、電子読取り専用メモリ、または他の適切なデータ記憶装置内に格納することもできる。本発明の例示的な一実施形態では、コンピュータ実行可能命令は、複数行のＪａｖａ（Ｒ）またはコンパイルされたＣ＋＋互換コードであり得る。
【００５３】
次に、図２を参照すると、データベース１４内に、透かしを確立するための論理を見ることができる。ブロック２６で開始して、ループの秘密の情報が使用されるデータベース１４内の各タプル１８について、ＤＯループが入力される。好ましい秘密の情報は、公開鍵・秘密鍵ペアの秘密鍵などの「鍵」であり得るが、秘密の番号列など、任意の適切な秘密の情報が使用され得る。
【００５４】
図２をよりよく理解するために、まず以下の定義を提供する。
【００５５】
データベース１４は、スキームがＲ（Ｐ，Ａ０，．．．，Ａｖ−１）であり、ただしＰは、主キーの属性である、データベース・リレーションＲと見なされ得ると仮定する。例として、すべてのｖ属性Ａ０，．．．，Ａｖ−１が、マーキングの候補であると仮定する。つまり、データベース１４は、η個のタプルを含み、ｖは、マーキングに使用可能なリレーション内の属性の数であり、ξは、属性内のマーキングに使用可能な最下位ビット数である。また１／γは、マーキングされるタプルのおよその割合を表し、ωは、図２の論理の後にマークされているタプルの数を表し、αは、図３を参照して以下でさらに論じるように、テスト・データ構造体内に、透かしが存在するかどうかを判断するためのテストの有意水準を表し、またτは、図３で以下にさらに開示するように、透かしの存在を示すために必要とされる、正確にマーキングされたタプルの最小数を表す。好ましくは、マーキングのすべての候補属性は、数字属性であり、その値は、そのすべてについて、ξ最下位ビット数の変更が知覚できないほどのものである。記号ｒ．Ａｉは、タプルｒ∈Ｒ内の属性Ａｉ、すなわち使用可能な1組の属性の値を意味する。
【００５６】
上記に加えて、一部の関数について、以下に説明する。現在好ましい非限定的な実装では、任意の長さの入力メッセージＭに対して作用する、一方向ハッシュ関数Ｈを使用し、Ｈは、固定長のハッシュ値ｈ、すなわちｈ＝Ｈ（Ｍ）を戻す。好ましいハッシュ関数は、ｉ）Ｍが与えられれば、ｈの計算は簡単である、ｉｉ）ｈが与えられても、Ｈ（Ｍ）＝ｈのように、Ｍを計算することは困難である、ｉｉｉ）Ｍが与えられても、Ｈ（Ｍ）＝Ｈ（Ｍ’）のように、別のメッセージＭ’を見つけることは困難であるという追加の特徴を有する。メッセージ・ダイジェスト５およびＳＨＡは、Ｈに対する２つの適切な選択である。
【００５７】
メッセージ認証コード（ＭＡＣ：message authenticated code）は、鍵に依存する、一方向ハッシュ関数である。Ｆは、タプルｒの主キーの属性の値ｒ．Ｐをランダム化するＭＡＣであり、広範囲の整数値を返すと仮定する。Ｆに、データベース１４の所有者だけに知られている秘密鍵Ｋを入力（seed）することができる。好ましい実施形態では、以下の安全なＭＡＣが使用され得る。
F(r.P) = H(K ; H(K ; r.P))、ただし;は、連結を示す。
【００５８】
上記の定義に留意して、図２の説明が完結され得る。この論理は、判断ひし形２８に移り、好ましい非限定的な一実施形態では、そこで、以下のように、テスト対象のタプルがマークされるべきかどうかが判断される。F(r.P）mod γが０に等しい場合、当該タプルは、マーキングの対象に指定される。秘密の情報Ｋを知るユーザだけが、どのタプルがマークされるか、したがって、どのタプルがマークされたかを簡単に知ることができることが容易に理解されよう。
【００５９】
判断ひし形２８で、マーキングのテストが満たされない場合、方法は戻り、次のタプルを取得する。そうではなく、タプルがマークされる場合は、論理は、ブロック３０に進み、タプルのどの属性をマークするかを判断する。これを行うために、好ましい非限定的な一実装では、第ｉ番の属性がマーク対象に選択され、ただしattribute_index i = F(r.P）mod vである。次いで、ブロック３２に移り、選択された属性について、どのビットをマークするかを判断する。これを行うために、好ましい非限定的な一実装では、第ｊ番の属性がマーク対象に選択され、ただしbit_indexj = F(r.P）mod ξである。マーキングのために、連続したξ最下位ビットを使用する必要はない。たとえば、ビット値の配分にスキューが生じているビット位置は、所望であれば、除外することができる。
【００６０】
次いで、ブロック３４で、ハッシュ関数を使用して、選択されたビットの値を判断する。この値は、「透かし値」と称され得る。好まれる非限定的な一実装では、H(K ; pk)が偶数であれば、第ｊ番最下位ビットが、「０」に設定され、そうでない場合は、ビット値は、「１」である。ただし「ｐｋ」は、主キーの属性である。
【００６１】
以下の擬似コードは、上記論理の一例である。この擬似コードは、計算的に最も効率的な形ではなく、開示を簡略化する形で書かれていることを理解されたい。
【００６２】
【表１】
2005531828.tif 000003
【００６３】
上記に留意して、マーキングによって、属性の値の一部は、減分され、その他の一部は、増分され、また一部変更されないままであることがここで理解され得よう。データベースでは通常、属性がヌル値を取ることができる。タプルをマーキングするときに、ヌル属性が生じる場合は、好ましくは、ヌル値には、マークが適用されず、変更しないままでおく。いずれの場合にも、非限定的な一実装では、ブロック３６で、ＳＱＬ更新関数を使用して、透かし値が、ビット内に挿入され得る。次いで、論理は、次のタプルを取り出して、判断ひし形２８に戻る。
【００６４】
非限定的な一実施形態において定められるように、タプルがマークされるかどうかは、その主キーの属性によって決まる。したがって、他のどのタプルの属性のマーキングをも調べずに、タプルを挿入することができる。同様に、タプルを簡単に削除することができる。タプルの主キー属性を更新する場合、タプルをデータベース内に格納する前に、そのマーキングを再計算することができる。非主キー属性を更新する場合は、アルゴリズムがその属性をマーキングの対象に選択していなければ、何も行う必要はない。一方、その属性がマーキングの候補であれば、好ましくは、データベース内にマークを格納する前に、マークが属性値に適用され得る。
【００６５】
透かしを入れるリレーション内に、主キーが存在しない場合がある。そうである場合に、またリレーションＲが単一の数字属性Ａからなると仮定すると、属性Ａのビットは、２つのグループに分けることができる。値ｒ．Ａの「Ｘ」ビットが、タプル「ｒ」の「主キーの代替」として使用され、残りのξビットが、マーキングに使用される。リレーションが複数の属性を有する場合、そのうちの１つが、代替として使用され、残りがマーキングに使用され得る。重複が最小である属性が、主キーの代替の働きをするように選択される。重複を減らすために、代替を、複数の属性にわたって広めることもできる。
【００６６】
次に、図３を参照すると、データベースのすべてまたは一部などのテスト・データ構造体が、コピーされた可能性があるかどうかが判断され得る論理を見ることができる。以下で明らかになるように、この論理は、確率的なものである。
【００６７】
ブロック３８から開始し、テスト・データ構造体内の各タプルについて、使用可能な秘密の情報Ｋを用いて、ＤＯループが入力される。判断ひし形４０で、許可された透かし挿入の一部として、テスト対象のタプルがマークされたものかどうかを判断する。これを行うために、好ましい非限定的な一実装では、F(r.P）mod γが０に等しいかどうかが判断される。そうである場合は、図２のアルゴリズムによって処理されていれば、タプルはマークされたはずである。判断ひし形３８で、マーキングのテストが満たされない場合、方法は戻って、次のタプルを取得する。
【００６８】
そうではなく、タプルがマークされたはずである場合は、論理は、ブロック４２に進み、図２の透かし挿入が行われたのであれば、タプルのどの属性がたぶんマークされたかを判断する。これを行うために、好ましい非限定的な一実装では、第ｉ番の属性がマーク対象に選択されたものとして指定され、ただしattribute_index i = F(r.P）mod vである。また第ｊビットがマーク対象に選択されたものとして指定され、ただしbit_indexj = F(r.P）mod ξである。
【００６９】
判断ひし形４４に進み、ブロック４２で選択されたビットの実際の値が、データ構造体に秘密の情報Ｋを用いて透かしが挿入された場合になるはずの値と比較される。ブロック４６で、一致した場合は、カウント数が増分される。判断ひし形４８で、最後のタプルがテストされたかどうかが判断される。そうでなければ、論理は判断ひし形４０に戻り、次のタプルを取り出す。そうでない場合は、論理は、判断ひし形５０に進み、カウント数が閾値ｏを超えているかどうかを判断する。そうでなければ、ブロック５２で、「透かし未検出」が返される。そうでない場合は、ブロック５４で、「透かし検出（違法コピーの疑い）」が返される。
【００７０】
以下の擬似コードは、透かし検出論理の非限定的な一実装を示している。
【００７１】
【表２】
2005531828.tif 000004
【００７２】
図３の検出論理は、図３に示す論理によるユーザ定義の集約関数を使用することができ、検出関数によって、透かしが検出された場合は、「１」が返され、そうでない場合は、「０」が返される。
【００７３】
上記の擬似コードでは、行８で使用される閾値サブルーチンは、以下のように指定され得る。図３の論理が「疑わしい」（テスト）データベースから、ω個のタプルをテストすると仮定する。こうしたテストは、論理が、特定のビット位置で、探している対象の値を見つけるのに成功する、１／２の確率のベルヌーイ試行と見なされ得る。ω回の試行の少なくともτ回の成功によって、正確な結果が返される確率がα未満になるように、行８のサブルーチンは、最小τを返す。αの有意性によって、システムが誤ったヒットをどの程度受け入れることができるが決まり、αが低くなると、無実のテスト・データベースを透かしを含むものとして、誤って識別する可能性が低くなる。
【００７４】
図３の論理で、マークされたタプル属性が除外される場合、そのタプルは、無視される。同様に、属性がマークされたはずのタプルが検出されるが、その属性がヌル値を含む場合は、そのタプルは、無視される。いずれにせよ、matchcountおよびtotalcountの値は、影響を受けない。
【００７５】
検出アルゴリズムでは、決定に達するために、元データまたは透かしにアクセスする必要なしに、データから少しの情報を抽出するだけなので、検出アルゴリズムがブラインドであることを理解されたい。これは、データベース・リレーションにとって、リレーションがしばしば更新されるため、重要である。ブラインド検出を行わなければ、透かし検出のため元のバージョンが必要とされるので、リレーションの各バージョンを保持する必要ある。
【００７６】
具体的な非限定的な実装では、上述のように、透かしは、まずＲのタプルを取り出し、選択リスト内に属性Ｐ、Ａが指示されることによって、挿入することができる。選択ステートメントは、追加の文節「Ａの更新」を含むことができ、それによって、データベース・エンジンは、選択されたタプル「ｒ」が更新されることを知ることができる。したがって、取り出された各タプル「ｒ」について、透かし挿入アルゴリズムによって、「ｒ」がギャップの範囲内に入らず、ｒ．Ａの値に変更が必要であると判断した場合は、ｒ．Ａをマークするための更新ステートメントが発行され得る。更新ステートメントは、「カーソル・カレント」文節を含むことができ、それによって、データベース・エンジンは、更新されるタプルがｒであることを知ることができる。
【００７７】
上記でも開示したように、透かし検出は、選択ステートメントを使用して、疑わしいデータベース・リレーションＳのタプルを取り出して、その選択リスト内に、属性Ｐ、Ａが指定されることによって実施することができる。結果のタプル「ｓ」が、ギャップの範囲内でない場合は、カウント数「totalcount」が増分される。「ｓ」がマークを含む場合、カウント数「matchcount」も同様に増分される。すべてのタプルが処理されると、検出アルゴリズムは、「totalcount」タプル内に、「matchcount」マークを検出する確率が有意水準内であるかどうかを判断する。そうである場合、透かしが検出されている。
【００７８】
データがどの程度エラーを許容できるかに応じて、不謹慎なコピー行為者（copiest）に、透かしを消そうとする際に、大きな誤りを犯させるようにし、その行為者のデータを望まれないものにするように、「ギャップ」γと称され得るものの値が選択される。ギャップγは、ω≒η／γによって、マークされたタプル数を判断する、制御パラメータである。γを、属性値内にもたらされるエラーの程度を判断するξとトレードオフすることができる。つまり、より少数のタプルがマークされている場合は、マークされた属性の値に対して行われ得る変更の程度が大きくなる。またξは、値が高すぎる場合、大きなエラーがもたらされると不謹慎なコピー行為者が予想をし、しかし彼が値を過小評価すると、透かしを破壊する成功率が低くなるように選択される。ｖも同様に、不謹慎なコピー行為者による攻撃を失敗させるように確立される。
【００７９】
要約すると、αの値を下げると、誤ったヒットの確率は低くなるが、コピーされ、多分変更されたデータベース内の透かしが見落とされる確率は高くなる。γの値を下げると、攻撃するシステムの堅牢性が増すが、透かしが挿入されたデータのデータ・エラーが増大する。ｖおよびξの値を増加すると、堅牢性が増すが、しかし、ξの場合は、データ内のエラーの値が増加する。
【図面の簡単な説明】
【００８０】
【図１】本発明の好ましい一実施形態によるシステムを示す概略図である。
【図２】本発明の好ましい一実施形態による、データベース内に透かしを確立するための論理のフロー・チャートである。
【図３】本発明の好ましい一実施形態による、テスト・データ構造体内に透かしが存在するかどうかを判断するための論理のフロー・チャートである。
【図１】
2005531828.tif 000005
【図２】
2005531828.tif 000006
【図３】
2005531828.tif 000007
【手続補正書】
【提出日】平成16年4月30日(2004.4.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のタプルを含むデータ・レポジトリに電子透かしを入れるためのコンピュータであって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該コンピュータは、少なくとも１つのプロセッサを含み、当該プロセッサは、
透かしを確立するために、秘密の情報に基づいて、前記タプルの少なくともいくつかの、少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立し、マークされるタプル、タプル内でマークされる属性、属性内でマークされるビット位置、および特定ビットの透かし値のうちの少なくとも２つが前記秘密の情報に基づいて判断されることを含む方法動作を実行する。
【請求項２】
数字属性内のビット位置だけが、前記透かしの一部である、請求項１に記載のコンピュータ。
【請求項３】
前記透かし値の少なくとも一部は、少なくとも前記秘密の情報の一方向ハッシュ関数に基づいて確立される、請求項１に記載のコンピュータ。
【請求項４】
複数のタプルを含むデータ・レポジトリ内に透かしが存在するかどうかを判断するためのコンピュータであって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該コンピュータは少なくとも１つのプロセッサを含み、当該プロセッサは、
タプルを含むテスト・データ構造体を受信すること、ならびに
前記テスト・データ構造体内に前記透かしが存在するかどうかを判断することであって、次の動作のうちの少なくとも２つについて、秘密の情報を使用して判断することを含む方法動作を実行し、
当該動作には、各タプルについて、前記タプルがマークされたはずかどうかを判断する動作と、
マークされたはずの各タプル内の少なくとも１つの属性について、前記属性がマークされたはずかどうかを判断する動作と、
マークされたはずの各属性内の少なくとも１つのビットについて、前記ビットがマークされたはずかどうかを判断する動作と、
マークされたはずの各ビットについて、透かし値を判断して、前記テスト・データ構造体が透かしを含むかどうかを判断する動作とを含む。
【請求項５】
前記判断動作が、前記テスト・データ構造体内に、前記透かしが所定の確率内で存在するかどうかを判断することによって行われる、請求項４に記載のコンピュータ。
【請求項６】
複数のタプルを含むデータ・レポジトリに電子透かしを入れるためのコンピュータ・プログラムであって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該コンピュータ・プログラムはコンピュータ上で実行されたとき、
透かしを確立するために、秘密の情報に基づいて、前記タプルの少なくともいくつかの、少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立するステップであって、マークされるタプル、タプル内でマークされる属性、属性内でマークされるビット位置、および特定ビットの透かし値のうちの少なくとも２つが前記秘密の情報に基づいて判断されるステップを実施する、プログラム・コード手段を含む。
【請求項７】
透かし値を確立する前記ステップは、
秘密の情報に基づいて、マークされる複数のタプルを判断するステップと、
マークされる各タプル内で、マークされる少なくとも１つの属性を判断するステップと、
マークされる各属性内で、マークされる少なくとも１つのビットを判断するステップと、
透かしを確立するために、少なくともマークされる各非ヌル・ビットの透かし値を確立するステップとを含む、請求項６に記載のコンピュータ・プログラム。
【請求項８】
複数のタプルを含むデータ・レポジトリに電子透かしを入れるための方法であって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、
当該方法は、透かしを確立するために、秘密の情報に基づいて、前記タプルの少なくともいくつかの、少なくとも１つの属性について、少なくとも１つのビット位置の透かし値を確立するステップであって、マークされるタプル、タプル内でマークされる属性、属性内でマークされるビット位置、および特定ビットの透かし値のうちの少なくとも２つが前記秘密の情報に基づいて判断されるステップを含む。
【請求項９】
透かし値を確立する前記ステップは、
秘密の情報に基づいて、前記データ・レポジトリ内のマークされる複数のタプルを判断すること、
マークされる各タプル内で、マークされる少なくとも１つの属性を判断すること、
マークされる各属性内で、マークされる少なくとも１つのビットを判断すること、および
透かしを確立するために、少なくともマークされる各非ヌル・ビットの透かし値を確立することをさらに含む、請求項８に記載の方法。
【請求項１０】
複数のタプルを含むデータ・レポジトリ内に透かしが存在するかどうかを判断するためのコンピュータ・プログラムであって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該コンピュータ・プログラムは、コンピュータ上で実行されたとき、
タプルを含むテスト・データ構造体を受信するステップと、
前記テスト・データ構造体内に前記透かしが存在するかどうかを判断するステップであって、
各タプルについて、前記タプルがマークされたはずかどうかを判断すること、
マークされたはずの各タプル内の少なくとも１つの属性について、前記属性がマークされたはずかどうかを判断すること、
マークされたはずの各属性内の少なくとも１つのビットについて、前記ビットがマークされたはずかどうかを判断すること、および
マークされたはずの各ビットについて、透かし値を判断して、前記テスト・データ構造体が透かしを含むかどうかを判断することを含むステップのうちの少なくとも２つについて、秘密の情報を使用して判断するステップとを実行する、プログラム・コード手段を含む。
【請求項１１】
コンピュータ上で実行されたときに、
正確なビット値のカウント数を維持するステップと、
前記カウント数に基づいて、前記テスト・データ構造体内に前記透かしが存在するかどうかを判断するステップとを実施するプログラム・コード手段をさらに含む、請求項１０に記載のコンピュータ・プログラム。
【請求項１２】
複数のタプルを含むデータ・レポジトリ内に透かしが存在するかどうかを判断するための方法であって、
各タプルが１つまたは複数の属性に関連付けられており、各属性が１つまたは複数のビット位置を含んでおり、少なくともいくつかのビット位置がビット値を含み、当該方法は、
タプルを含むテスト・データ構造体を受信するステップと、
前記テスト・データ構造体内に前記透かしが存在するかどうかを判断するステップであって、
それぞれのタプルについて、前記タプルがマークされたはずかどうかを判断すること、
マークされたはずの各タプル内の少なくとも１つの属性について、前記属性がマークされたはずかどうかを判断すること、
マークされたはずの各属性内の少なくとも１つのビットについて、前記ビットがマークされたはずかどうかを判断すること、および
マークされたはずの各ビットについて、透かし値を判断して、前記テスト・データ構造体が透かしを含むかどうかを判断することを含む動作のうちの少なくとも２つについて、秘密の情報を使用して判断するステップとを含む。
【請求項１３】
それぞれが少なくとも１つの属性を含む複数のタプルであって、各属性が、ビット値をもつ少なくとも１つのビットを含むタプルと、
秘密の情報に基づいて確立される、ビット間の値のパターンとを含み、
請求項８に記載の方法を使用して透かしが挿入されるデータ・レポジトリ。
【請求項１４】
少なくともいくつかの属性が主キーを有し、属性の前記主キーを使用して、透かし値を確立する、請求項１３に記載のデータ・レポジトリ。
【請求項１５】
少なくとも第１の属性が主キーを有しておらず、第１の属性のビット区画を使用して、透かし値を確立する、請求項１３に記載のデータ・レポジトリ。
【国際調査報告】
2005531828.tif 000008
2005531828.tif 000009
2005531828.tif 000010
2005531828.tif 000011
2005531828.tif 000012