(57)【要約】  計算方法の実装のコピーの追跡を容易にする改良されたシステム。前記計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することによって構成される前記ネットワークを生成するネットワーク生成手段。関連する入力値ドメインに対応するバージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの複数の異なるバージョンを、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することによって生成するパーソナル化手段。各バージョンを各ステーション又はステーションの各ユーザに関連付ける関連付け手段。計算方法は、暗号化方式と暗号キーとを含む。
2010515945.tif 000002
【特許請求の範囲】
【請求項１】
計算方法の実装のコピーの追跡を容易にするシステムであって、
前記計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することによって構成される前記ネットワークを生成するネットワーク生成手段と、
関連する入力値ドメインに対応するバージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの複数の異なるバージョンを、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することによって生成するパーソナル化手段と、
各バージョンを各ステーション又はステーションの各ユーザに関連付ける関連付け手段と、
を有するシステム。
【請求項２】
前記計算方法は、暗号化方式と暗号キーとを有し、
前記ネットワーク生成手段と前記パーソナル化手段とは、前記暗号キーにより前記暗号化方式を実行するよう処理可能なルックアップテーブルのネットワークを生成するよう構成される、請求項１記載のシステム。
【請求項３】
前記パーソナル化手段は、前記計算方法のｗｈｉｔｅ−ｂｏｘ実装を生成するよう構成される、請求項１記載のシステム。
【請求項４】
前記ｗｈｉｔｅ−ｂｏｘ実装の出力符号化及び／又は入力復号化は、異なるバージョンにおいて異なる、請求項１記載のシステム。
【請求項５】
前記パーソナル化手段は、異なるバージョンについて異なって選択される演算子を用いて、前記ｗｈｉｔｅ−ｂｏｘ実装を難読化するよう構成され、
前記演算子は、前記ネットワークの第１の複数のルックアップテーブルに統合され、
前記演算子の逆演算子は、前記ネットワークの第２の複数のルックアップテーブルに統合される、請求項１記載のシステム。
【請求項６】
前記第１の複数のルックアップテーブルの少なくとも１つ又は前記第２の複数のルックアップテーブルの少なくとも１つは、入力及び／又は出力符号化を、前記ネットワークを介したデータのフローに関して前記ネットワークにおけるそれの各自の先行するもの及び／又は後続するものにより無効にされる、請求項１記載のシステム。
【請求項７】
前記演算子は、線形ミキシング全単射であり、
前記入力及び／又は出力符号化の少なくとも１つは、非線形である、請求項１記載のシステム。
【請求項８】
前記パーソナル化手段は、異なる等価性クラスの演算子を用いてバージョンを生成するよう構成され、
等価性クラスは、対応するルックアップテーブルのネットワークが所定の変更群からの変更を前記入力及び／又は出力符号化に適用することによって、互いから取得可能にする演算子を有する、請求項１記載のシステム。
【請求項９】
前記パーソナル化手段は、異なる等価性クラスのバージョンを生成するよう構成され、
等価性クラスは、所定の変更群からの変更を前記バージョンに適用することによって、互いから取得可能なバージョンを有する、請求項１記載のシステム。
【請求項１０】
前記ルックアップテーブルのネットワークの各バージョンを単一の媒体を介し前記関連付けされたステーション又はユーザに提供する出力をさらに有する、請求項１記載のシステム。
【請求項１１】
当該システムは、複数のステーションへのコンテンツの制御された配布のためのものであり、
前記計算方法は、解読方法を有し、
当該システムはさらに、
暗号化されたバージョンを取得するため、前記ユーザに係るバージョンを、前記ユーザに係るユーザ固有の暗号キーにより暗号化する暗号化手段と、
暗号化されたコンテンツを取得するため、前記暗号化方式と前記暗号キーとに従ってコンテンツを暗号化するコンテンツプリプロセッサと、
前記ユーザに前記暗号化されたバージョンと前記暗号化されたコンテンツとを提供する出力と、
を有する、請求項１記載のシステム。
【請求項１２】
ユーザに対する計算を実行するシステムであって、
計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することにより構成される前記ネットワークをデータに適用するデータ処理ユニットを有し、
前記ルックアップテーブルのネットワークは、関連する入力値ドメインに対応する前記計算方法の最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することにより取得される前記ルックアップテーブルのネットワークの複数の異なるバージョンのあるバージョンを構成し、
各バージョンは、各ユーザに関連付けされる、システム。
【請求項１３】
計算方法の実装のコピーを特定するシステムであって、
前記実装は、計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することにより構成される前記ネットワークを有し、
前記ルックアップテーブルのネットワークは、関連する入力値ドメインに対応する前記バージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することにより取得される前記ルックアップテーブルのネットワークの複数の異なるバージョンのあるバージョンであり、
当該システムは、前記実装の前記ルックアップテーブルの少なくとも１つと前記バージョンの少なくとも１つとを比較する比較手段を有する、システム。
【請求項１４】
前記実装における前記バージョンに対応する等価性クラスを構成する等価性クラス構成手段をさらに有し、
等価性クラスは、スタートバージョンから、攻撃者に想到されると仮定される変更群からの変更を前記バージョンに適用することによって取得可能なバージョンを有する、請求項１３記載のシステム。
【請求項１５】
計算方法の実装のコピーのユーザの追跡を容易にする方法であって、
前記計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することによって構成される前記ネットワークを生成するステップと、
関連する入力値ドメインに対応するバージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの複数の異なるバージョンを、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することによって生成するステップと、
各バージョンを各ユーザに関連付けるステップと、
を有する方法。
【請求項１６】
請求項１５記載の方法をプロセッサに実行させるための命令を有するコンピュータプログラム。
【請求項１７】
計算方法の実装のコピーを特定する方法であって、
前記実装は、計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することにより構成される前記ネットワークを有し、
前記ルックアップテーブルのネットワークは、関連する入力値ドメインに対応する前記バージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することにより取得される前記ルックアップテーブルのネットワークの複数の異なるバージョンのあるバージョンであり、
当該方法は、前記実装の前記ルックアップテーブルの少なくとも１つと前記バージョンの少なくとも１つとを比較するステップを有する、方法。
【請求項１８】
請求項１７記載の方法をプロセッサに実行させるための命令を有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算方法の実装のコピーの追跡を容易にするシステムに関する。
【背景技術】
【０００２】
インターネットは、ユーザにデジタルコンテンツへの便利かつユビキタスなアクセスを提供する。著作権保護されたコンテンツのための配布媒体としてのインターネットの利用は、コンテンツプロバイダの利益を確保するため強力なチャレンジを生じさせる。特に、コンテンツプロバイダの著作権及びビジネスモデルを補償することが求められる。ますます多くの家電機器（ＣＥ）プラットフォームが、適切なソフトウェアがロードされたプロセッサを用いて実行される。このようなソフトウェアは、オーディオ及び／又はビデオなどのデジタルコンテンツのレンダリング（再生）を行う機能の要部を含むかもしれない。再生ソフトウェアの制御は、コンテンツの使用条項及び条件を含むコンテンツ所有者の利益を行使するための１つの方法である。従来、多数のＣＥプラットフォーム（ＰＣ及びＰＤＡを除く）はクローズされて使用されていたが、現在は、ますます多くのプラットフォームが少なくとも部分的にオープンとされている。特にＰＣプラットフォームでは、一部のユーザは、コンテンツへのアクセスと、コンテンツ保護機構にアタック及びバイパスするための大量の時間及びリソースとを提供するハードウェア及びソフトウェアに対する完全な制御を有することが想定されるかもしれない。このため、コンテンツプロバイダは、必ずしもすべてのユーザ又は装置が信頼できるとは限らないコミュニティに対して敵対的なネットワークを介しユーザを正当化するためのコンテンツを提供しなければならない。
【０００３】
侵害者からムービーなどのデジタルコンテンツを保護するため、それらはしばしばユーザに暗号化された形式により提供される。配布コストを低く抑えるため、コンテンツは一般に１回しか暗号化されない。すなわち、正当な各ユーザは、コンテンツを解読可能な同一のキーを取得する。これは、攻撃者が当該キーを未承認のユーザに配布することが可能であり、保護機構を破るという脆弱性を意味する。
【０００４】
“Ｃｈｏｗ  １”として以降において参照されるＳｔａｎｌｅｙ  Ｃｈｏｗ，Ｐｈｉｌｉｐ  Ｅｉｓｅｎ，Ｈａｒｏｌｄ  Ｊｏｈｎｓｏｎ，ａｎｄ  Ｐａｕｌ  Ｃ．Ｖａｎ  Ｏｏｒｓｃｈｏｔによる“Ｗｈｉｔｅ−Ｂｏｘ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ａｎ  ＡＥＳ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”（ｉｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ：９ｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ，ＳＡＣ  ２００２，Ｓｔ．Ｊｏｈｎ‘ｓ，Ｎｅｗｆｏｕｎｄｌａｎｄ，Ｃａｎａｄａ，Ａｕｇｕｓｔ  １５−１６，２００２）と、“Ｃｈｏｗ  ２”として以降において参照されるＳｔａｎｌｅｙ  Ｃｈｏｗ，Ｐｈｉｌｉｐ  Ｅｉｓｅｎ，Ｈａｒｏｌｄ  Ｊｏｈｎｓｏｎ，ａｎｄ  Ｐａｕｌ  Ｃ．Ｖａｎ  Ｏｏｒｓｃｈｏｔによる“Ａ  Ｗｈｉｔｅ−Ｂｏｘ  ＤＥＳ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｆｏｒ  ＤＲＭ  Ａｐｐｌｉｃａｔｉｏｎｓ”（ｉｎ  Ｄｉｇｉｔａｌ  Ｒｉｇｈｔｓ  Ｍａｎａｇｅｍｅｎｔ：ＡＣＭ  ＣＣＳ−９  Ｗｏｒｋｓｈｏｐ，ＤＲＭ  ２００２，Ｗａｓｈｉｎｇｔｏｎ，ＤＣ，ＵＳＡ，Ｎｏｖｅｍｂｅｒ  １８，２００２）とは、ルックアップテーブルのネットワークにおいてキーを難読化することによって、キーを隠蔽する方法を開示する。これは、攻撃者がキーを抽出及び配布することをより困難にする。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
計算方法の実装のコピーの追跡を容易にする改良されたシステムを有することが効果的である。
【課題を解決するための手段】
【０００６】
上記事項に良好に対処するため、本発明の第１の態様では、
前記計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することによって構成される前記ネットワークを生成するネットワーク生成手段と、
関連する入力値ドメインに対応するバージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの複数の異なるバージョンを、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することによって生成するパーソナル化手段と、
各バージョンを各ステーション又はステーションの各ユーザに関連付ける関連付け手段と、
を有するシステムが提供される。
【０００７】
パーソナル化手段は、ルックアップテーブルのネットワークにおける固有の冗長性を利用して、ルックアップテーブルのネットワークの異なるバージョンを生成する。あるバージョンの（潜在的に不正な）コピーが検出されると、当該バージョンに係るステーション又はユーザが確定される。これは、各バージョンは異なり、個々のバージョンは個々のステーション又はステーションの個々のユーザに関連付けされているためである。
【０００８】
異なるバージョンを生成するのに適用される変更は、一般にバージョンの透かしと呼ばれるかもしれない。ネットワーク生成手段とパーソナル化手段は同一であってもよく、すなわち、１つのユニットがすべてのバージョンを生成するようにしてもよい。変更された値は、ルックアップテーブルの１つにおける値であるかもしれない。ネットワークの構成（ルックアップテーブルの何れの出力がルックアップテーブルの何れの入力に適用されるか規定する構成）がパラメータ化されてもよいことが理解されるであろう。このような場合、変更された値は、当該構成を規定するパラメータに関連するものであってもよい。
【０００９】
一実施例では、前記計算方法（６０２）は、暗号化方式と暗号キーとを有し、前記ネットワーク生成手段（６０４）と前記パーソナル化手段（６０６）とは、前記暗号キーにより前記暗号化方式を実行するよう処理可能なルックアップテーブルのネットワークを生成するよう構成される。当該システムは、暗号キーがしばしば脆弱であるため、上記ケースにおいて特に有用である。このようなキーの不正な配布は、望ましくない。システムは、ルックアップテーブルのネットワークのバージョンの（不正に配布された）コピーが検出されると、関連付けされたステーション又はユーザを特定するのに使用される。明らかに再配布されたバージョンのコピーが検出された場合、関連付けされたユーザに対してアクションをとることが可能となる。
【００１０】
一実施例では、前記パーソナル化手段は、前記計算方法のｗｈｉｔｅ−ｂｏｘ実装を生成するよう構成される。ルックアップテーブルのネットワークを用いたアルゴリズムのｗｈｉｔｅ−ｂｏｘ実装は、例えば、Ｃｈｏｗなどから知られている。これらのｗｈｉｔｅ−ｂｏｘ実装における冗長性と特に難読化は、第三者（すなわち、攻撃者）による分離及び／又は削除を困難にする変更をネットワークに適用することを容易にする。
【００１１】
一実施例では、前記ｗｈｉｔｅ−ｂｏｘ実装の出力符号化及び／又は入力復号化は、異なるバージョンにおいて異なる。ルックアップテーブルのネットワークの異なるバージョンを生成するための変更を行う比較的シンプルな方法は、ルックアップテーブルの１つの出力を異なる方法により符号化し、ルックアップテーブルのネットワークの次のルックアップテーブルによりこれを復号化することである。
【００１２】
一実施例では、前記パーソナル化手段は、異なるバージョンについて異なって選択される演算子を用いて、前記ｗｈｉｔｅ−ｂｏｘ実装を難読化するよう構成され、前記演算子は、前記ネットワークの第１の複数のルックアップテーブルに統合され、前記演算子の逆演算子は、前記ネットワークの第２の複数のルックアップテーブルに統合される。
【００１３】
これは、複数のルックアップテーブル又はネットワークの構成に対する連動した変更が必要とされるため、攻撃者が透かしを完全に削除することを比較的複雑なタスクにする。複数のルックアップテーブルが演算子の実装に寄与するという意味で、演算子は複数のネットワークにおいて統合される。しかしながら、演算子の結果は、ルックアップテーブルが中間的及び／又は最終結果のさらなる符号化を提供するかもしれないため、ｗｈｉｔｅ−ｂｏｘ実装において直接的には可視化されないかもしれない。
【００１４】
一実施例では、前記第１の複数のルックアップテーブルの少なくとも１つ又は前記第２の複数のルックアップテーブルの少なくとも１つは、入力及び／又は出力符号化を、前記ネットワークを介したデータのフローに関して前記ネットワークにおけるそれの各自の先行するもの及び／又は後続するものにより無効にされる。これは、攻撃者が透かしを削除することをさらに困難にする。
【００１５】
一実施例では、前記演算子は、線形ミキシング全単射（ｌｉｎｅａｒ  ｍｉｘｉｉｎｇ  ｂｉｊｅｃｔｉｏｎ）であり、前記入力及び／又は出力符号化の少なくとも１つは、非線形である。非線形入力及び／又は出力符号化と組み合わされた線形ミキシング全単射は、ｗｈｉｔｅ−ｂｏｘ実装について一般的である。線形ミキシング全単射は、複数のルックアップテーブルに効率的に統合可能である。非線形出力及び入力符号化は、ｗｈｉｔｅ−ｂｏｘ実装を破ることをより困難にする。
【００１６】
一実施例では、前記パーソナル化手段は、異なる等価性クラスの演算子を用いてバージョンを生成するよう構成され、等価性クラスは、対応するルックアップテーブルのネットワークが所定の変更群からの変更を前記入力及び／又は出力符号化に適用することによって、互いから取得可能にする演算子を有する。入力及び／又は出力符号化の順列を含む変更の適用は、攻撃者に想到すると想定されうるタスクである。従って、透かしは、変更適用後も透かしと係るユーザが依然として特定可能であるという点で、透かしがこのような変更に“耐性”を有するべきである。個々のバージョンが個々のステーション又はユーザに関連付けされるため、個々の等価性クラスが個々のステーション又はユーザに関連付けされる。
【００１７】
一実施例では、前記パーソナル化手段は、異なる等価性クラスのバージョンを生成するよう構成され、等価性クラスは、所定の変更群からの変更を前記バージョンに適用することによって、互いから取得可能なバージョンを有する。所定の変更群は、攻撃者に想到すると想定される変更を表す。透かしは、攻撃者に想到するこのような変更に対する“耐性”を有するべきである。透かしと係るユーザは、バージョンが異なる等価性クラスにある場合、このような変更の適用後も依然として特定可能である。好ましくは、各等価性クラスにおいて高々１つのバージョンが生成される。個々のバージョンが個々のステーション又はユーザに関連付けされるため、個々の等価性クラスが個々のステーション又はユーザに関連付けされる。
【００１８】
一実施例は、前記ルックアップテーブルのネットワークの各バージョンを単一の媒体を介し前記関連付けされたステーション又はユーザに提供する出力を有する。これは、ステーション又はユーザが単一の媒体を介しルックアップテーブルのネットワークを便利に受け取ることを可能にする。ネットワークの何れの部分もステーションに予めプログラムされる必要はない。このように、経時的に異なって変更されるバージョンが、第２の媒体を使用することなく又はステーションに対するハードウェア又はファームウェアの変更を要することなく、各ステーション又はユーザに関連付けされ、容易に提供される。それは、ステーションが各バージョンになされた変更とは独立に予めプログラム可能であるため、システムをより効率的にする。任意的には、ステーションは同一である。バージョンはユーザ間に（不正に）配布されるかもしれないが、このような（不正に）配布されたバージョンのソースは追跡可能である。ネットワークのバージョンはまず媒体を用いて提供されたステーション又はステーションのユーザに当ガーバージョンが関連付けられるためである。容易すぎる（不正な）配布は、暗号化形式によりルックアップテーブルのネットワークのバージョンを提供することによって依然として回避されるかもしれない。
【００１９】
一実施例では、当該システムは、複数のステーションへのコンテンツの制御された配布のためのものであり、前記計算方法は、解読方法を有し、
当該システムはさらに、
暗号化されたバージョンを取得するため、前記ユーザに係るバージョンを、前記ユーザに係るユーザ固有の暗号キーにより暗号化する暗号化手段と、
暗号化されたコンテンツを取得するため、前記暗号化方式と前記暗号キーとに従ってコンテンツを暗号化するコンテンツプリプロセッサと、
前記ユーザに前記暗号化されたバージョンと前記暗号化されたコンテンツとを提供する出力と、
を有する。
【００２０】
本実施例は、特定のアプリケーションコンテクストを記載する。バージョンは、ユーザ固有のキーを用いて暗号化され、各ユーザに提供されるかもしれない。あるいは、バージョンは、セキュアなチャネル又は媒体などを介し暗号化されることなく提供されるかもしれない。他の実施例では、ルックアップテーブルのネットワークの一部は、予め固定され、ユーザにすでにあり、ルックアップテーブルのネットワークの残りの部分のみユーザに提供される。
【００２１】
一実施例はユーザに対する計算を実行するシステムであって、
計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することにより構成される前記ネットワークをデータに適用するデータ処理ユニットを有し、
前記ルックアップテーブルのネットワークは、関連する入力値ドメインに対応する前記計算方法の最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することにより取得される前記ルックアップテーブルのネットワークの複数の異なるバージョンのあるバージョンを構成し、
各バージョンは、各ユーザに関連付けされる、システムを有する。
【００２２】
これは、ルックアップテーブルのネットワークのバージョンに従ってデータを処理するようステーション又はユーザ端末に実現可能である。
【００２３】
一実施例は、計算方法の実装のコピーを特定するシステムであって、前記実装は、計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することにより構成される前記ネットワークを有し、
前記ルックアップテーブルのネットワークは、関連する入力値ドメインに対応する前記バージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することにより取得される前記ルックアップテーブルのネットワークの複数の異なるバージョンのあるバージョンであり、
当該システムは、前記実装の前記ルックアップテーブルの少なくとも１つと前記バージョンの少なくとも１つとを比較する比較手段を有する、システムを有する。
【００２４】
これは、特定のバージョンに係るユーザを特定するのに使用される。
【００２５】
一実施例は、前記実装における前記バージョンに対応する等価性クラスを構成する等価性クラス構成手段をさらに有し、等価性クラスは、スタートバージョンから、攻撃者に想到されると仮定される変更群からの変更を前記バージョンに適用することによって取得可能なバージョンを有する。これは、透かし処理されたバージョンが変更された後であっても、ユーザを特定するのに利用される。
【００２６】
一実施例は、計算方法の実装のコピーのユーザの追跡を容易にする方法であって、
前記計算方法の各ステップを表すルックアップテーブルのネットワークであって、第１ルックアップテーブルの出力値を異なる第２ルックアップテーブルの入力値として使用することによって構成される前記ネットワークを生成するステップと、
関連する入力値ドメインに対応するバージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの複数の異なるバージョンを、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することによって生成するステップと、
各バージョンを各ユーザに関連付けるステップと、
を有する方法を有する。
【００２７】
一実施例は、計算方法の実装のコピーを特定する方法であって、
前記実装は、計算方法の各ステップを表すルックアップテーブルのネットワーク（２８）であって、第１ルックアップテーブル（２０）の出力値を異なる第２ルックアップテーブルの入力値として使用することにより構成される前記ネットワークを有し、
前記ルックアップテーブルのネットワークは、関連する入力値ドメインに対応する前記バージョンの最終結果が各バージョンについて実質的に同一となる、前記ルックアップテーブルのネットワークの少なくとも１つの値を変更することにより取得される前記ルックアップテーブルのネットワークの複数の異なるバージョンのあるバージョンであり、
当該方法は、前記実装の前記ルックアップテーブルの少なくとも１つと前記バージョンの少なくとも１つとを比較するステップを有する、方法を有する。
【００２８】
一実施例は、上述した方法の何れかをプロセッサに実行させるための命令を有するコンピュータプログラムを有する。
【００２９】
ＷＯ０１／３１４１９は、情報がパーソナル値を有するキーにより暗号化され、ユーザが他人とキーを共有することを禁止するようクライアントのユーザに知られているコンピュータにより実現される方法を開示する。
【図面の簡単な説明】
【００３０】
本発明の上記及び他の特徴はさらに、図面を参照して解明及び説明されるであろう。
【図１】図１は、ＡＥＳのラウンドにおける処理を示す図である。
【図２】図２は、テーブルを難読化する一例を示す図である。
【図３】図３は、ｗｈｉｔｅ−ｂｏｘ  ＡＥＳ実装におけるカラムのラウンドを示す図である。
【図４】図４は、タイプＩａテーブルに搭載されるマッピングを示す図である。
【図５】図５は、タイプＩＩテーブルに搭載されるマッピングを示す図である。
【図６】図６は、タイプＩＩＩテーブルに搭載されるマッピングを示す図である。
【図７】図７は、タイプＩＶテーブルに搭載されるマッピングを示す図である。
【図８】図８は、タイプＩｂテーブルに搭載されるマッピングを示す図である。
【図９】図９は、ルックアップテーブルのネットワークにおいて１つのルックアップテーブルから次のルックアップテーブルへの情報ビットのフローを示す図である。
【図１０】図１０は、一実施例を示す図である。
【図１１】図１１は、一実施例を示す図である。
【発明を実施するための形態】
【００３１】
ｗｈｉｔｅ−ｂｏｘ暗号化は、攻撃者が実装からキーＫを抽出することを困難にするように、固定されたキーＫのブロック暗号を実装することに関する。ｗｈｉｔｅ−ｂｏｘ暗号化において仮定される攻撃モデルは、ｗｈｉｔｅ−ｂｏｘ攻撃モデルである。この攻撃モデルでは、攻撃者は、ソフトウェアへの完全なアクセスを有し、実行環境に対する完全な制御を有すると仮定される。
【００３２】
一実施例は、有料テレビのための限定受信システムに関する。コンテンツプロバイダは、ＡＥＳとコンテンツキーＫにより暗号化されたコンテンツを配信する。限定受信システムに関して解決される必要のある問題の１つは、コンテンツを解読するためのコンテンツキーを加入者のみに配布する方法である。以下において、２つのアプローチが説明される。第１の直接的なアプローチは、コンテンツキーＫを経時的に固定し続け、加入者のみにキーＫを提供するものである。しかしながら、この実装は、以下の２つの問題点を有する。第１の問題点は、ユーザを登録解除することができないことである。一度キーＫを有すると、ユーザは永久にコンテンツを解読できる。この直接的な実装の第２の問題点は、長期間固定されたキーを用いることによって、攻撃者がそれを検出できる危険が増大することである。
【００３３】
第２のアプローチは、以下のように機能する。コンテンツキーが、例えば、毎日又は毎週など、定期的に変更される。各加入者ｓは一意的な秘密キーｋｓを取得し、各加入者ｓについて、キーＫがそれの秘密キーｋｓにより暗号化される。キーＫを暗号化したものの集合｛Ｅｋｓ（Ｋ）｜ｓは正当な加入者｝が、暗号化されたコンテンツと共に配信される。その後、正当な加入者のみがＫを取得し、コンテンツを解読することができる。キーｋｓが良好に隠蔽されることが重要である。一般に、これはハードウェアにより実行される。このアプローチでは、ユーザを登録解除することができる。ユーザｓを登録解除するため、変更後にユーザに暗号化されたコンテンツキーを提供しない。これにより、コンテンツキーがＫからＫ’に変更された場合、ユーザｓにはＥｋｓ（Ｋ’）が提供されない。
【００３４】
上述された第２のアプローチは第１のものよりは良好であるが、それは依然として以下の攻撃のため脆弱な限定受信システムをもたらす。加入者の１人がコンテンツキーＫを導出可能であるかもしれない。これは、例えば、加入者ｓが解読アルゴリズムを調べ、それからキーを抽出することが可能であるため、又はｓが加入者自身のキーｋｓを決定することができるため、そうなる可能性がある。コンテンツキーＫが次に不正に配布されると、コンテンツプロバイダは、この配布の原因となる悪意ある加入者を特定することはできない。この結果、コンテンツプロバイダは、正当な加入者を含むすべての加入者について、解読アルゴリズムの実装及び／又は加入者のキーｋｓの置換などの厳格なアクションをとる必要があるかもしれない。
【００３５】
一実施例では、キーＫによりコンテンツを解読するための解読アルゴリズムの実装が、Ｃｈｏｗらにより記載されるようなｗｈｉｔｅ−ｂｏｘ実装と実質的に置換される。このｗｈｉｔｅ−ｂｏｘの実装では、ＡＥＳ解読アルゴリズムは、それらの入出力を符号化することによって難読化されたルックアップテーブルの集合により実現される。さらに、異なる符号化が異なる加入者のテーブルに適用される。この結果、各加入者は異なるｗｈｉｔｅ−ｂｏｘ実装を取得する。しかしながら、これらすべてのｗｈｉｔｅ−ｂｏｘ実装は、同一の機能を有する。（それは、キーＫにより解読を実行する。）コンテンツキーＫが変更された場合、加入者には、新たなｗｈｉｔｅ−ｂｏｘ実装（すなわち、新たなルックアップテーブルの集合）が提供されるかもしれない。
【００３６】
ｗｈｉｔｅ−ｂｏｘ実装が十分安全である場合、攻撃者が基礎となるキーＫを抽出し、それを公表することは容易でない。代わりに、加入者は完全なｗｈｉｔｅ−ｂｏｘ実装（すなわち、ルックアップテーブルの集合）を公表しなければならない。しかしながら、悪意ある加入者が自らのｗｈｉｔｅ−ｂｏｘ実装を公表した場合、コンテンツプロバイダは、加入者が一意的なｗｈｉｔｅ−ｂｏｘ実装を有しているため、当該加入者を追跡することができる。この結果、コンテンツプロバイダは、攻撃者を無効にし、すなわち、攻撃者の登録を解除することができる。これは、異なるキーＫ’により暗号化されたさらなるコンテンツに対して、攻撃者はキーＫ’により解読アルゴリズムを実現するｗｈｉｔｅ−ｂｏｘ実装を受け取ることができなくなる。
【００３７】
異なる符号化を選択することによって、同一の機能を有する複数のｗｈｉｔｅ−ｂｏｘ実装が生成可能である。（例えば、それらはすべて、キーＫによるＡＥＳ解読を実現する。）この変形は、裏切り者の追跡に利用可能である。各ユーザには、ｗｈｉｔｅ−ｂｏｘ実装が与えられた場合、符号化を調べることによってｗｈｉｔｅ−ｂｏｘ−実装のソースを特定できるように、異なるｗｈｉｔｅ−ｂｏｘ実装の変形が与えられる。ｗｈｉｔｅ−ｂｏｘ実装の符号化はフォレンシックな透かしの役割を担うことに留意されたい。
【００３８】
以下において、Ｃｈｏｗらにより提案されたＡＥＳ  ｗｈｉｔｅ−ｂｏｘ実装を利用したいくつかの実施例が説明される。しかしながら、これらの実施例はＡＥＳに限定されるものでない。当業者は、他の暗号化方式、特にそれのｗｈｉｔｅ−ｂｏｘ実装に開示された技術を適用するのに必要な変更を行うことが可能である。また、この技術は、当業者に理解されるように、アルゴリズムがルックアップテーブルのネットワークを適用することを含む何れかの状況において、暗号化の範囲外で適用可能である。
［ＡＥＳのｗｈｉｔｅ−ｂｏｘ実装］
ＡＥＳは、１２８ビット又は１６バイトのブロックサイズによるブロック暗号である。平文は、符号化アルゴリズムの初期状態を構成する１６バイトの各ブロックに分割され、符号化アルゴリズムの最終状態は暗号文となる。ＡＥＳを概念的に説明するため、状態のバイトは４×４バイトのマトリックスとして構成される。ＡＥＳは、いくつかのラウンドから構成される。各ラウンドは、状態マトリックスのバイト、行又は列に対して実行される同様の処理ステップから構成され、各ラウンドは、これらの処理ステップにおいて異なるラウンドキーを使用する。
【００３９】
図１は、ＡＥＳのラウンドのいくつかの主要な処理ステップを示す。処理ステップは、
ＡｄｄＲｏｕｎｄＫｅｙ２−状態の各バイトが、ラウンドキーのバイトとＸＯＲ演算される。
【００４０】
ＳｕｂＢｙｔｅｓ４−ルックアップテーブルを用いたバイト・ツー・バイトの置換
ＳｈｉｆｔＲｏｗｓ６−状態の各行が一定のバイト数回転される。
【００４１】
ＭｉｘＣｏｌｕｍｎｓ８−各列が、ＧＦ（２８）のモジュロー乗算を用いて処理される。
【００４２】
ＳｕｂＢｙｔｅｓ４，ＳｈｉｆｔＲｏｗｓ６，ＭｉｘＣｏｌｕｍｎｓ８の各ステップは、使用される特定のキーから独立している。キーは、ＡｄｄＲｏｕｎｄＫｅｙ２のステップで適用される。ＳｈｉｆｔＲｏｗｓ６のステップを除いて、これらの処理ステップは、その他の列を知ることなく４×４の状態マトリックスの各列に対して実行可能である。このため、それらは、各列が４つの８ビット値から構成されるとき、３２ビット演算とみなすことができる。破線１０は、必要とされる回数のラウンドが実行されるまで、当該処理が繰り返されることを示す。
【００４３】
各ステップ又はステップのくむ合わせは、ルックアップテーブル又はルックアップテーブルのネットワーク（Ｓ−ｂｏｘｅｓ）により表現されるかもしれない。また、ルックアップテーブルのネットワークとＡＥＳのフルラウンドとを置換することが可能である。例えば、ＡｄｄＲｏｕｎｄＫｅｙステップは、単にラウンドキーとＸＯＲ演算することによって実現可能であるが、ＳｕｂＢｙｔｅｓ，ＳｈｉｆｔＲｏｗｓ，ＭｉｘＣｏｌｕｍｎｓの各ステップはテーブルルックアップを用いて実現される。しかしながら、これは、キーが依然としてｗｈｉｔｅ−ｂｏｘ攻撃コンテクストにおいて攻撃者に依然として可視的であることを意味する。ＡｄｄＲｏｕｎｄＫｅｙステップはまたルックアップテーブルに埋め込み可能であり、これは、キーを検出することを自明なものにしない。
【００４４】
図２は、キーを抽出することをさらに困難にする方法を示す。Ｘ及びＹを２つの関数とする。演算
【００４５】
【数１】
2010515945.tif 000003
を検討する。ここで、
【００４６】
【数２】
2010515945.tif 000004
は、図２のダイアグラム１２として示される関数の合成を示し、ｃは、例えば、４バイトの状態列などの入力値である。しかしながら、このアプローチは、任意のタイプの入力値ｃに適用される。マッピングＸ及びＹは、メモリに格納可能なルックアップテーブルとして実現可能であるが、それらがメモリに格納されるとき、これらの値は攻撃者により読まれる可能性がある。ダイアグラム１４は、ルックアップテーブルのコンテンツが入力符号化Ｆと出力符号化Ｈとを用いることによって、どのように難読化できるかを示す。
【００４７】
【数３】
2010515945.tif 000005
に対応するルックアップテーブルが、Ｘ及びＹの代わりに図示されるように格納され、Ｘ及びＹの抽出を困難にする。ダイアグラム１６は、２つのテーブルの中間結果がまた符号化されるように、さらなるランダムなどの全単射関数Ｇを追加する方法を示す。この場合、２つのテーブル
【００４８】
【数４】
2010515945.tif 000006
が、メモリに格納される。これは、ダイアグラム１８において再び示される。
【００４９】
【数５】
2010515945.tif 000007
ただし、Ｘ及びＹは、ルックアップテーブルを用いた実装に適した関数である。本明細書では、
【００５０】
【数６】
2010515945.tif 000008
は、通常通り関数の合成を示す。（すなわち、任意の２つの関数ｆ（ｘ）及びｇ（ｘ）に対して、定義によって、
【００５１】
【数７】
2010515945.tif 000009
となる。同様に、２より多くの関数から構成されるネットワークが符号化できる。Ｘ及びＹを符号化する実際のテーブルは、単一のルックアップテーブルにおいて
【００５２】
【数８】
2010515945.tif 000010
を合成し、単一のルックアップテーブルにおいて、
【００５３】
【数９】
2010515945.tif 000011
を合成することによって難読化される。Ｆ，Ｇ及び／又はＨが未知である限り、攻撃者はルックアップテーブルからＸ及び／又はＹに関する情報を抽出できず、Ｘ及び／又はＹの基礎となるキーを抽出することはできない。ＤＥＳ及びＲｉｊｎｄａｅｌ（そのＡＥＳが特定のインスタンス化である）を含む他の暗号化アルゴリズムがまた、上述したものと同様の方法により難読化可能なルックアップテーブル（のカスケード又はネットワーク）として符号化されてもよい。これはまた、置換・順列ネットワークやＦｅｉｄｔｅｌネットワークなどに基づく暗号に対して成り立つ。本発明は、上述した暗号化アルゴリズムに限定されるものでない。
【００５４】
Ｃｈｏｗ  １は、個別のステップでなく合成を表すランダムな全単射によりそれのテーブルを符号化することによって、キーを隠蔽する方法を開示している。秘密キーの抽出を防ぐことは、攻撃者は、ソフトウェア保護目的が他のマシーンについてバイパスされることを可能にするキーイングマテリアルを抽出したり、又はインストールされたソフトウェアの大きなユーザベースに対するセキュリティ手段を無効にする“グローバルクラック”を効果的に生成するキーイングマテリアルを公表することが禁じられるという効果を有する。それは、ソフトウェアのみのソリューション及び敵意のあるホストの現実の各制約が与えられると、より高い程度の保護を提供する。Ｃｈｏｗ  １のアプローチでは、キーは、（１）個別ステップでなく合成のためのテーブルを使用し、（２）これらのテーブルをランダム全単射により符号化し、（３）暗号化アルゴリズムを超えた暗号境界を包含するアプリケーションに拡張することによって隠蔽され、攻撃者（リバースエンジニア）に彼らの目的を達成するためかなり大きなコードセグメントを理解させる。Ｃｈｏｗ  １は、固定キーアプローチについて記載している。キーは、キー入力が不要となるように、キーに関する部分的評価により実装に埋め込まれる。部分的評価とは、キーに関する表現が可能な限り妥当に評価され、その結果が完全な表現でなくコードに置かれることを意味する。攻撃者は、キー固有の実装を抽出可能であり、キーの代わりにそれを利用することができる。しかしながら、暗号化は、典型的には、コンポーネントが設計される操作又は符号化形式により入力を暗号化コンポーネントに提供可能であるが、敵対者が削除することが困難だとわかる、より大きな包含システムのコンポーネントである。符号化テーブルのステップを参照すると、符号化は任意的なものであるため、１つのステップの出力符号化が次のステップの入力符号化に一致する場合に限って、意味がある。例えば、ステップＸの後にステップＹが続く場合（
【００５５】
【数１０】
2010515945.tif 000012
の計算をもたらす）、当該計算は、
【００５６】
【数１１】
2010515945.tif 000013
として符号化可能である。このように、
【００５７】
【数１２】
2010515945.tif 000014
は、入力がＦにより符号化される必要があり、出力がＨ―１により復号化される必要があるにもかかわらず、適切に計算される。これらのステップは、Ｆ，Ｇ，ＨはＸ及びＹと共に隠蔽されるように、Ｙ’及びＸ’に対応するテーブルとして別々に表現される。
【００５８】
このようなコンフュージョンステップ（ｃｏｎｆｕｓｉｏｎ  ｓｔｅｐ）とは別に、Ｃｈｏｗ  １は、さらに基礎となる演算を偽装するため、線形変換によるデフュージョンステップ（ｄｉｆｆｕｓｉｏｎ  ｓｔｅｐ）を利用する。ミキシング全単射という用語は、上述の意味で使用される線形全単射を記述するのに使用される。Ｃｈｏｗ  １の実装は、操作形式により入力を受け取り、異なる操作形式により出力を生成し、これにより、ＷＢＡＣ（Ｗｈｉｔｅ−Ｂｏｘ  Ａｔｔａｃｋ  Ｃｏｎｔｅｘｔ）耐性ＡＥＳをそれの包含アプリケーションから分離することを困難にする。
【００５９】
ｗｈｉｔｅ−ｂｏｘ  ＡＥＳ実装は、以下のように記述することができる。ＡＥＳ暗号化解読アルゴリズムへの入力は、単一の１２８ビットブロックである。このブロックは、１６バイトから構成される４×４のマトリックにより表現される。ＡＥＳは、通常はＡＥＳ−１２８について１０ラウンドから構成される。各ラウンドは、ＡＥＳの状態を構成する１６バイトの集合を更新し、これにより、各ＡＥＳラウンドは１２８ビットを処理する。ＡＥＳ−１２８は、１２８ビットのキーを使用する。このキーは、キーを１２８ビットの異なるラウンドキーに変換するアルゴリズムの入力として機能する。基本ラウンドは、
・ＳｕｂＢｙｔｅｓ
・ＳｈｉｆｔＲｏｗｓ
・ＭｉｘＣｏｌｕｍｎｓ
・ＡｄｄＲｏｕｎｄＫｅｙ
の４つの部分から構成される。
【００６０】
この演算順序は、ＡＥＳ暗号化に適用される。ＡＥＳ解読の標準的な演算順序は異なるが、ＡＥＳ暗号化と同じ演算順序を有するようにＡＥＳ解読アルゴリズムを書き換えることが可能である。
【００６１】
第１ラウンド前に、追加的なＡｄｄＲｏｕｎｄＫｅｙ演算が実行され、１０回目のラウンドでは、ＭｉｘＣｏｌｕｍｎｓ演算は省略される。キーを使用する部分はＡｄｄＲｏｕｎｄＫｅｙのみであり、その他の３つの部分はキーなしで可能である。実装では、ラウンドの境界は、次のラウンドのＡｄｄＲｏｕｎｄＫｅｙステップとＳｕｂＢｙｔｅｓステップとを１つのステップに統合するよう変更される。ラウンドは、ＡｄｄＲｏｕｎｄＫｅｙとＳｕｂＢｙｔｅｓから始められ、その後にＳｈｉｆｔＲｏｗｓ及び最後にＭｉｘＣｏｌｕｍｎｓに続く。
【００６２】
まず、キーは、ＳｕｂＢｙｔｅｓステップとＡｄｄＲｏｕｎｄＫｅｙを１つのステップに合成することによって隠蔽される。これは、キーをもはやそれ自体可視できないものにする。キーは予め知られているため、キーに関する演算は予め評価できる。このことは、ＳｕｂＢｙｔｅｓステップにおいて用いられる標準的なＳ−Ｂｏｘがキー固有のＳ−Ｂｏｘに置換可能であることを意味する。ＡＥＳ−１２８のキー固有のインスタンスを生成するため、キーは、以下のように定義される１６個の８×８（すなわち、８ビットの入力と８ビットの出力）ルックアップテーブルＴｒｉ，ｊを生成することによって、ＳｕｂＢｙｔｅｓ変換に統合される。
【００６３】
【数１３】
2010515945.tif 000015
ここで、ＳはＡＥＳ  Ｓ−ｂｏｘ（可逆的な８ビットマッピング）であり、ｋｒｉ，ｊはラウンドｒのラウンドキーを表す４×４のマトリックスのポジションｉ，ｊにおけるＡＥＳサブキーバイトである。これらのＴ−Ｂｏｘは、前のラウンドのＡｄｄＲｐｕｎｄＫｅｙステップによりＳｕｂＢｙｔｅｓステップを構成する。第１０ラウンドのＴ−Ｂｏｘは、以下のようにホワイト化後のキーを吸収する。
【００６４】
【数１４】
2010515945.tif 000016
ここで、ｓｒ（ｉ，ｊ）は、ＳｈｉｆｔＲｏｗｓステップ後のセルｉ，ｊの新たな位置を示す。Ｔ−ｂｏｘの総数は、１０かける１６＝１６０である。しかしながら、キーは、Ｓ−１が公知であるため、Ｔ−ｂｏｘから容易に復元できる。入力を各Ｔ−ｂｏｘに分散させるため、線形変換が用いられる。これらの線形変換は、ミキシング全単射と呼ばれ、ＧＦ（２）上の８×８のマトリックスとして表現できる。ミキシング全単射は、それらの効果を無効にするため前の計算により反転される。
【００６５】
図３は、（ＳｈｉｆｔＲｏｗｓの適用後の）状態の１つの３２ビット列のｗｈｉｔｅ−ｂｏｘ  ＡＥＳのラウンドに関するテーブルを示す。ここでは、異なるタイプのテーブルの名前が導入される。それらは、以降においてより詳細に説明される。ラウンド前に、１２８ビットの状態の各バイトが、各タイプのＩａテーブルに適用される。これは、４つの３２ビット値に分割される１２８ビット出力を提供するためタイプＩＶテーブルのネットワークを利用して、ＸＯＲ演算される各１２８ビット値をもたらす。ここで、第１ラウンドが開始される。各３２ビット値の処理ステップがここに概略される。３２ビット値の４つのバイトは、４つの各自のタイプＩＩテーブル２０に入力される。４つのタイプＩＩテーブル２０のそれぞれは、３２ビットの出力をもたらす。これらの出力は、タイプＩＶテーブル２２を用いてビット単位でＸＯＲ演算が実行される。各タイプＩＶテーブル２２は、４ビット単位のＸＯＲを実行する。タイプＩＶテーブルの入力と出力とを適切に接続することによって、４つの３２ビット出力のビット単位のＸＯＲが、当業者に理解されるように実現可能である。このステップの結果は、３２ビット値である。この値の４バイトのそれぞれが、各自のタイプＩＩＩテーブル２４に適用される。各タイプＩＩＩテーブルは、３２ビット出力を提供する。これらの出力は、再びタイプＩＶテーブル２２のネットワークと同様に、タイプＩＶテーブル２６のネットワークを用いてビット単位にＸＯＲ演算される。この出力は、状態の列を示す３２ビット値である。ラウンド２〜９は、この第１ラウンドと同様である。１２８ビット値の各バイトは、タイプＩｂテーブルに適用され、その結果がタイプＩＶテーブルのネットワークを用いてＸＯＲ演算される。最後のラウンド（通常は、第１０ラウンド）は、外部の符号化により吸収されるかもしれない。
【００６６】
図４は、タイプＩａテーブル１００を示す。図５は、タイプＩＩテーブル２００を示す。図６は、タイプＩＩＩテーブル３００を示す。図７は、タイプＩＶテーブル４００を示す。図８は、タイプＩｂテーブル５００を示す。
【００６７】
ミキシング全単射は、以下のように用いられる。ＡＥＳ状態は、バイトから構成される４×４のマトリックスにより表現される。ＭｉｘＣｏｌｕｍｎｓステップは、一度に１カラム（４つの８ビットセル）に対して実行される。３２×３２のマトリックスＭＣを考える。これがテーブルにより表現される場合、当該テーブルは、２３２×３２＝１３７４３８９５３４７２ビット＝１６ＧＢを要する。このような大きなテーブルを回避するため、マトリックスは４つのセクションにブロック化される。
【００６８】
ＭＣは、４つの３２×８のセクションＭＣ０，ＭＣ１，ＭＣ２，ＭＣ３（ブロック２０８）にブロック化される。３２ビットベクトルｘ＝（ｘ０，．．．，ｘ３１）とＭＣとの乗算は、ｘのビットを４バイトに分割し、ＭＣの各セクションとこれらのバイトの１つと乗算することによって実行され、４つの３２ビットベクトル（ｚ０，．．．，ｚ３）をもたらす。この後、３つの３２ビットのＸＯＲが実行され、最終的に３２ビットの結果ｚが与えられる。４つのテーブルは共に、４×２８×３２＝３２７６８ビット＝４ＫＢしか要しない。
【００６９】
３つのＸＯＲは、それぞれが適切な連結によるおそらく符号化されたルックアップテーブルにより表される２４の４ビットＸＯＲに分割される。例えば、
【００７０】
【数１５】
2010515945.tif 000017
であり、
【００７１】
【数１６】
2010515945.tif 000018
は連結を示し、＋はＸＯＲを示す。これらのストリップと細分化されたＸＯＲとを用いることによって、各ステップは小さなルックアップテーブルにより表現される。特に、ｉ＝０，．．．，３について、ｚｉは８×３２テーブルを用いて計算され、４ビットＸＯＲは２４個の８×４テーブルになる。図７は、入力復号化４０２と出力符号化４０６とがＸＯＲ４０４の近傍においてどのように配置可能であるか示す。これらの符号化は、通常はランダムに選択された非線形４×４全単射である、ＸＯＲテーブルは、タイプＩＶテーブル４００と呼ばれる。タイプＩＶテーブルは、前の２つの計算のそれぞれから入力として４ビットをとる。これらの計算の出力符号化２１２は、互いに無効にするため、タイプＩＶテーブルの入力復号化４０２と一致される。４×４非線形全単射の選択は、テーブルのサイズに依存する。この状況において、タイプＩＶテーブルは２８×４ビット＝１２８バイトしかない。一緒では３ＫＢを要する２４のテーブルが必要とされる。ＸＯＲが分割されない場合、３２ビットＸＯＲを計算した３つのＸＯＲテーブルが必要とされる。Ｔ−ｂｏｘ２０６と３×３２テーブル２０８とは、独立したルックアップテーブルとして表現可能である。代わりに、それらが構成可能であり、ＳｕｂＢｙｔｅｓとＡｄｄＲｏｕｎｄＫｅｙ変換と共にいｘＣｏｌｕｍｎｓの一部を計算する新たな８×３２テーブル２００が生成される。これは、スペース（Ｔ−ｂｏｘを格納するための）と時間（ルックアップテーブルを実行するための）の両方を節約する。状機能にＭＣをＭＣｉに分割する前、ＭＣは、フルランクの４×４のサブマトリックスを有する非特異マトリックスとして選ばれる、図５の参照番号２１０により示される３２×３２ミキシング全単射と左方乗算される。ミキシング全単射の使用は、特定のテーブルについて可能な構成数を増加させる。
【００７２】
図５は、４×４の入力復号化２０２と４×４の出力符号化２１２とを含む８×３２のタイプＩＩテーブル２００を示す。これらの出力符号化と入力復号化とは、タイプＩＶテーブル４００の入力復号化と出力符号化とに一致する必要がある非線形４×４全単射である。タイプＩＩテーブル２００の後に、タイプＩＶテーブル４００が続く。ＭＢを反転するため、追加的なテーブルセットがＭＢ−１を計算するため用いられる。
【００７３】
【数１７】
2010515945.tif 000019
をＭｉｘＣｏｌｕｍｎｓへの入力とし、
【００７４】
【数１８】
2010515945.tif 000020
をＭｉｘＣｏｌｕｍｎｓの後の出力とする。
【００７５】
【数１９】
2010515945.tif 000021
をＭＢとの乗算後の結果とする。
【００７６】
【数２０】
2010515945.tif 000022
は、タイプＩＩＩテーブル３００への入力として用いられる。テーブルの出力符号化は次のテーブルの入力復号化により無効にされるため、ここでは入力復号化と出力符号化とは考慮される必要はないことに留意されたい。タイプＩＩＩテーブル３００では、ＭＢ−１が適用され（３０４）、次のラウンドの４つのタイプＩＩテーブル２００の４つの入力されるミキシング全単射の逆が適用される（３０８）。
【００７７】
図６は、４×４の非線形入力復号化と４×４の非線形出力符号化とを含む８×３２のタイプＩＩＩテーブル３００を示す。これらのテーブルの後に、対応するタイプＩＶテーブル４００が続く。
【００７８】
データ演算の１回のラウンドは、１２８ビット状態マトリックスに対する演算に関する。１２８ビット状態マトリックスの３２ビットの４つのストリップのそれぞれに対して実行されるデータ演算は、以下の通りである。３２ビットストリップは、４つの８ビットバイトに分割される。４つのバイトのそれぞれは、タイプＩＩテーブル２００に供給され、４つの３２ビット出力値をもたらす。これらの値は、難読化されたタイプＩＶテーブル４００を用いてＸＯＲ演算される必要がある。このため、各３２ビット出力値は、８つの４ビットニブルに分割され、適切なニブルのペアが、４つの３２ビット出力値のＸＯＲが符号化形式により取得されるように、各自のタイプＩＶテーブルに入力される。
【００７９】
この３２ビットの結果としての符号化されたＸＯＲ結果は、再びバイトに分割され、各バイトはタイプＩＩＩテーブル３００に入力される。タイプＩＩＩテーブルの各ニブルの入力復号化は、最後に適用されたタイプＩＶテーブルの出力符号化に対応する。タイプＩＩＩテーブルは再び、難読化されたタイプＩＶテーブル４００を用いてＸＯＲ演算される４つの３２ビット出力値をもたらす。
【００８０】
すなわち、ラウンドはルックアップテーブルにより実現される。１回のラウンドのルックアップテーブルは、以下のようにネットワーク化される。データは、タイプＩＩテーブルに供給される。これらのテーブルの出力は、符号化されたＸＯＲを表すタイプＩＶテーブルのネットワークに供給される。このネットワークの出力は、タイプＩＩテーブルにより挿入されたミキシング全単射符号化を相殺するタイプＩＩＩテーブルに供給される。ラウンドの符号化された出力は、最終的にはタイプＩＩＩテーブルの出力を符号化されたＸＯＲを表すタイプＩＶテーブルのネットワークに再び供給することによって求められる。
【００８１】
さらに、ｗｈｉｔｅ−ｂｏｘ実装は、外部符号化を相殺及び挿入するため、それぞれ始め（タイプＩａテーブル１００）と終わり（タイプＩｂテーブル５００）とにおいてタイプＩテーブルを有する。タイプＩａテーブル１００は、単一のテーブルルックアップを適用することによって、図４に示されるようなマッピングの連結を適用するのに利用可能である。この連結では、４ビットニブル入力復号化１０２がまず行われる。その後、８ビットから１２８ビットへの全単射１０４が行われ、この全単射は、ネットワークの入力と出力との符号化を実行する。このマッピングは、プログラムの他の何れかにおいては無効にすることができる。全単射１０４の結果は。各８ビット全単射１０６が適用される１６個の８ビット部分に分割される。最終的には、出力ニブル符号化１０８が適用される。上述されるように、マッピング１０２，１０４，１０６，１０８のカスケードは予め評価され、最終結果がルックアップテーブルに記述される。これは、それぞれ１２８ビットの高々２５６個のエントリを有するテーブルをもたらす。タイプＩｂテーブル５００に含まれるマッピングの連結が、図８に概略的に示される。第１マッピングは、入力ニブル復号化５０２であり、その後に８ビット全単射５０４、Ｔ−ｂｏｘ  Ｔｒｉ，ｊ５０６（ここで、ｒは最後のラウンドに対応する）、出力符号化を提供する８ビットから１２８ニットへのマッピング、及び出力ニブル符号化５１０が続く。このタイプのテーブルの１２８ビット出力は、他のタイプＩｂテーブルの出力とＸＯＲ演算され、再びニブル入出力符号化されたタイプＩＶテーブル４００が利用される。出力符号化５０８は、プログラムの他の何れかにおいて無効にされ、すなわち、プログラムの暗号部分の外部において無効にされる。これは、攻撃者がプログラムの暗号部分の入出力のみを解析することによって、テーブルの符号化を破ることをさらに困難にする。
【００８２】
ｗｈｉｔｅ−ｂｏｘ暗号化は、攻撃者がｗｈｉｔｅ−ｂｏｘ攻撃も出るにおけるキーを抽出することができないように、ソフトウェアにブロック暗号を実装することに関する。ｗｈｉｔｅ−ｂｏｘ攻撃モデルは、攻撃者が当該実装への完全なアクセスを有し、実行環境に対する完全な制御を有すると仮定されるため、最も強力な想定されうる攻撃モデルのうちの１つである。ｗｈｉｔｅ−ｂｏｘ実装は、ＡＥＳ、ＤＥＳ及び他の暗号化方式について存在する。これらのｗｈｉｔｅ−ｂｏｘ実装は、上記と同様のアイデアに基づくものであってもよく、当業者は、他の暗号化方式のｗｈｉｔｅ−ｂｏｘ実装を生成するため、ｗｈｉｔｅ−ｂｏｘ実装の原理を適用することが可能である。
［透かし］
悪意のあるユーザが自らの実装を配布した場合、当該ユーザを追跡できるように、フォレンシック透かしがｗｈｉｔｅ−ｂｏｘ実装に追加されてもよい。すなわち、特定のｗｈｉｔｅ−ｂｏｘ実装Ｙが与えられると、Ｘ１，Ｘ２，．．．，Ｘｎの各実装の何れにそれが相当するか決定できるように、複数のｗｈｉｔｅ−ｂｏｘ実装Ｘ１，Ｘ２，．．．，Ｘｎが生成されてもよい。実装Ｙは、悪意のあるユーザｕが機能変更することなく自らの実装Ｘｉに変更を加えることが可能であるかもしれないため、実装Ｘｉと全く同一である必要はない。
【００８３】
一実施例では、フォレンシック透かしは、ｗｈｉｔｅ−ｂｏｘ  ＡＥＳ実装に追加される。このアプローチでは、複数のｗｈｉｔｅ−ｂｏｘ  ＡＥＳ実装が、ｗｈｉｔｅ−ｂｏｘ実装のテーブルを難読化するため異なる符号化を選択することにより生成される。異なる符号化を選択することによって、複数のｗｈｉｔｅ−ｂｏｘ  ＡＥＳ実装Ｘ１，Ｘ２，．．．，Ｘｎが生成される。例えば、所与のタイプＩＩテーブルＵの第１出力ニブルの非線形ニブル符号化ｆに関してのみ異なるものとなるように、Ｘ１，Ｘ２，．．．，Ｘｎを定義する（図５の２１２）。これは、後続するタイプＩＶ  ＸＯＲテーブルＶについて、２つの入力ニブル復号化ｇの１つが異なる実装では異なることを意味する。その理由は、ｇ＝ｆ−１であるということである。すなわち、Ｕの第１出力ニブルに設けられた出力符号化ｆは、ＸＯＲテーブルＶに含まれるニブル復号化により相殺される。当業者は、これがタイプＩＩテーブルの第１出力ニブルに限定されないことを理解するであろう。対応する出力ニブル符号化と入力ニブル復号化の何れかのペアが、透かしを適用するのに利用可能である。また、このようなペアの何れかの組み合わせが透かしとして利用可能である。特に強力な透かしは、すべてのニブル符号化／復号化をランダムに選択し、これを各ユーザについて異なって実行することによって取得可能である。これは、攻撃者がニブル符号化／復号化ペアの一部しか変更できない場合、ユーザが残りのニブル符号化／復号化ペアにより依然として特定可能であるというさらなる効果を有する。
【００８４】
ニブル符号化の変更は、解読結果に影響を与えない。ニブル出力符号化が他のテーブルのニブル入力復号化において無効にされるとき、最終結果は同じになる。このため、テーブルの多数の異なるバージョンが異なるユーザに配布されるようにしてもよい。ここで、これらのバージョンのすべてが同一の暗号キーによる同一の暗号化方法を表す。
【００８５】
攻撃者は、以下のようにニブル符号化を変更できる。Ｕ，Ｖをｗｈｉｔｅ−ｂｏｘ  ＡＥＳ実装における２つの連続するテーブルとし、ｆをテーブルＵにより返されたニブルの出力符号化とする。これは、テーブルＶが入力ニブル復号化ｆ−１を有し、すなわち、テーブルＶがＵからのニブルにｆ−１を適用することを意味していることに留意されたい。この出力符号化は、任意の（非線形）符号化ｇに変更可能である。
【００８６】
【数２１】
2010515945.tif 000023
となるように、ｈを定義する。その後、ｈによりＵの出力を符号化し、Ｖにニブル復号化ｈ−１を含める。図９において、この原理が、タイプＩＶテーブルの特別なケースについて示される。このアクションの結果は、テーブルＵの出力符号化がｇにより与えられるということである。さらに、攻撃者がＵ及びＶにおいて使用された符号化に関する情報を必要としないため、攻撃者はアクションを実行することが可能である。攻撃者が実現可能な第２の変更は、テーブルの入出力ビットを再構成することを含む。テーブルＶの入力ビットを構成するテーブルＵの出力ビットが、攻撃者により異なる順序で与えられる可能性がある。ビットの順序に関するこの変更は、テーブルＶにおいて無効にされる。攻撃者が適用可能なこれらの変更の可能性は、ルックアップテーブルのネットワークから透かしを削除する脅威を与える。
【００８７】
攻撃者は透かしを含むルックアップテーブルのネットワークを変更可能であることが示された。これについて、以下の問題は、ロウバストな透かしを提供する役割を担う。第１に、すべてが機能的に等価である、すなわち、すべてが所与のキーＫについてのＡＥＳを実装する複数のｗｈｉｔｅ−ｂｏｘ  ＡＥＳ実装Ｘ１，Ｘ２，．．．，Ｘｎの生成の仕方。第２に、それは、攻撃者ｕが実装Ｘｕに対して透かしを削除するため何れのタイプの変更を仮定しているか特定し、依然として所望の機能を有することを助ける。第３に、Ｙをこのような変更を（おそらく）適用することによって、ｗｈｉｔｅ−ｂｏｘ実装Ｘｕから取得される変更されたｗｈｉｔｅ−ｂｏｘ実装とする。Ｙが他の何れかの実装ＸｉからでなくＸｕから導出されたことを依然として判定可能であることが望ましい。これら３つの問題は、フォレンシック透かし問題と呼ばれるかもしれない。
【００８８】
一実施例では、透かしは、攻撃者がニブル符号化の１以上を変更し、及び／又はあるテーブルから次のテーブルに移るビットの順序を変更したとしても、透かしが復元できるように追加される。より一般には、攻撃者は、次の同じテーブルへの入力ビットを構成するテーブルの出力ビットの集合に対して何れかの変換を適用したかもしれない。これを実現する１つの方法は、以下の数学的理論により良好に理解されるかもしれない。
［等価性問題］
以下の概念が使用される。ニブルは４ビットベクトルであり、バイトは８ビットベクトルであり、各（４ｎ）ビットベクトルｘは、ニブルｘ１，．．．，ｘｎについてｘ＝（ｘ１，．．．，ｘｎ）としてｎ個のニブルに分割されると仮定される。このため、分割された（４ｎ）ビットベクトルｘは、長さｎのニブルベクトルと呼ばれるかもしれない。ニブル変換はマップｆ＝（ｆ１，．．．，ｆｎ）であり、各ｆｉはニブルマップであり、すなわち、ニブルをニブルにマッピングする。このようなマップは、上述されるようにニブルに分割された（４ｎ）ビットベクトルｘ＝（ｘ１，．．．，ｘｎ）に適用され、ベクトルｘを
【００８９】
【数２２】
2010515945.tif 000024
にマッピングする。
【００９０】
このようなニブル変換ｆは、各ニブルマップｆｉが可逆である場合、かつその場合に限って可逆となることに留意されたい。可逆名ニブル変換は、それらが出力ニブル符号化として機能する場合にはルックアップテーブルの出力において使用され、それらが入力ニブル復号化として機能する場合にはルックアップテーブルの入力において使用される。ニブル順列は、（４ｎ）ビットベクトルｘ＝（ｘ１，．．．，ｘｎ）に対してそれのニブルを並び替えることにより実行されると仮定される順列
【００９１】
【数２３】
2010515945.tif 000025
であり、ここで、
【００９２】
【数２４】
2010515945.tif 000026
である。このようなπは、ｘを
【００９３】
【数２５】
2010515945.tif 000027
にマッピングすると仮定される。
【００９４】
タイプＩＩテーブル２００により実現される演算Ｏは、２つのニブルａ１，ａ２からなる入力バイトａ＝（ａ１，ａ２）を、８つのニブルｚ１，．．．，ｚ８からなる３２ビット出力ベクトルｚ＝（ｚ１，．．．，ｚ８）に変換し、
【００９５】
【数２６】
2010515945.tif 000028
の形式をとる。ここで各種演算は以下の形式を有する。
・マップｇ＝（ｇ１，ｇ２）は、入力バイトａ＝（ａ１，ａ２）に対するニブル復号化２０２を表し、ａをｇ＝（ｇ１（ａ１），ｇ２（ａ２））にマッピングする。ここで、各ｇｉは、ニブルからニブルへの可逆マップである。
・マップＡは、バイトからバイトへの非特異線形マップ２０４を表す。
・マップＴは、バイトをバイトにマッピングする“Ｔ−ｂｏｘ演算”２０６を表す。
・マップＣは、ミキシング演算２０８の一部を表し、バイトから３２ビットベクトルへの線形マップから構成される。
・マップＢは、ミキシング全単射２１０である。それは、３２ビットベクトルを３２ビットベクトルにマッピングする。一実施例では、このマップＢは透かしを符号化するのに使用される。
・最後に、ｆ＝（ｆ１，．．．，ｆ８）は、ニブルｕ１，．．．，ｕ８に分割された３２ビットベクトルｕ＝（ｕ１，．．．，ｕ８）を出力ベクトル
【００９６】
【数２７】
2010515945.tif 000029
にマッピングするニブル符号化２１２を表す。
【００９７】
ａ（１），．．．，ａ（４）が出力列ｂに寄与する４つの入力バイトである場合、
【００９８】
【数２８】
2010515945.tif 000030
の形式の４つのタイプＩＩテーブルＯ（１），．．．，Ｏ（４）が関係する。このとき、出力列ｂは、
【００９９】
【数２９】
2010515945.tif 000031
を充足する。ただし、
【０１００】
【数３０】
2010515945.tif 000032
である。
【０１０１】
３２×３２のマトリックスＣ＝［Ｃ１Ｃ２Ｃ３Ｃ４］（ただし、Ｃｉは（２）のものである）がフルミキシング演算を表していることに留意されたい。
【０１０２】
（３）について求められる演算は、数レイヤのタイプＩＶテーブルにより実現される。ここで、タイプＩＶテーブル４００により実現される演算Ａは、ニブル入力のペア（ｘ，ｙ）をニブルｚに変換し、
【０１０３】
【数３１】
2010515945.tif 000033
の形式をとる。ここで、各種演算は、以下の形式を有する。
・マップｇ（ｇ１，ｇ２）は、ニブルの入力ペア（ｘ，ｙ）に対するニブル復号化４０２を表し、それらを（ｇ１（ｘ），ｇ２（ｙ））にマッピングする。ここで、各ｇｉは、ニブルからニブルへの可逆マップである。
・マップＳは、４０４における４ビットＸＯＲ演算
【０１０４】
【数３２】
2010515945.tif 000034
を表す。
・最後に、ｆは、ニブルｕをニブルｆ（ｕ）にマッピングするニブル符号化４０６を表す。
【０１０５】
従って、（３）における出力列ｂの和を実現するため、テーブルＯ（ｉ）の３２ビット加数ｚ（ｉ）のそれぞれはまず、８つのニブルｚ（ｉ）ｊ（ｊ＝１，．．．，８）に分割される。その後、出力列ｂのニブルｂｊは、
【０１０６】
【数３３】
2010515945.tif 000035
のように２つのレイヤのタイプＩＶテーブルにより計算される。
【０１０７】
最後のレイヤの各タイプＩＶテーブルにおける最終的な出力符号化の結果として、ルックアップテーブルネットワークの当該部分は、ある出力ニブル符号化ｈについて実際にｃ＝ｈ（ｂ）を計算する。
【０１０８】
それのフォレンシック透かしＢを隠蔽することを所望する攻撃者は、出力ベクトルｃ＝ｈ（ｂ）を操作するいくつかの可能性を有している。第１に、同一の順列πにより各ベクトルｚ（ｉ）のニブルを並び替えることは、出力ベクトルのニブルがまたπにより並び替えられるという効果を有する。第２に、タイプＩＶテーブルの最後のレイヤの出力ニブル符号化の変更（可逆的な方法による）は、この符号化をｃのニブルに効果的に適用する。攻撃者がまずｃのバイトが提供される後続のネットワークを並び替えることによって、これら双方の演算を無効にすることができることに留意されたい。
【０１０９】
従って、攻撃者は、出力ｃ＝ｈ（ｂ）の代わりに、生成される実際の出力が、
【０１１０】
【数３４】
2010515945.tif 000036
であることを確認することができる。ただし、
【０１１１】
【数３５】
2010515945.tif 000037
は、未知の可逆ニブル順列であり、
【０１１２】
【数３６】
2010515945.tif 000038
は、未知の可逆ニブル変換であり、このため、
【０１１３】
【数３７】
2010515945.tif 000039
は、
【０１１４】
【数３８】
2010515945.tif 000040
を充足する。
【０１１５】
現在のテーブルルックアップネットワークにおいて実現されるシステムの（想像上の）非難読化（標準）ＡＥＳ実装が与えられると、すべての中間的計算結果を調べることができ、解読タイプ演算によって所定の値に設定できる。特に、Ｏ（ｉ）において実行される計算におけるすべての中間結果
【０１１６】
【数３９】
2010515945.tif 000041
は、また標準ＡＥＳ計算においても実行され、その和が
【０１１７】
【数４０】
2010515945.tif 000042
となり、攻撃者のアクションに関係なく任意の所定値に設定可能である。
【０１１８】
【数４１】
2010515945.tif 000043
となるため、（３）から、
【０１１９】
【数４２】
2010515945.tif 000044
となる。
【０１２０】
しかしながら、攻撃者の操作（及びオリジナルのニブル出力符号化）の結果として、ｂの代わりに、（６）と同様にｂから取得されるベクトルｂ’が、未知であるが固定されたニブル順列πとニブル変換ｆと共に観察される。
【０１２１】
この結果、未知のマップＴの入出力が検察可能となる。ここで、Ｔは、未知のニブル順列π、可逆ニブル変換ｆ及びオリジナルのフォレンシック透かしＢに関する情報が所望される（未知の）透かしを表す可逆線形マップＢによって、
【０１２２】
【数４３】
2010515945.tif 000045
の形式を有することが知られる。
【０１２３】
２つの３２×３２の可逆マトリックス（又はフォレンシック透かし）ＢとＢ’は、２つの式
【０１２４】
【数４４】
2010515945.tif 000046
が等しくなるようなニブル順列π，σ及び可逆ニブル変換ｆ，ｇが存在する場合、等価であると言われる。この定義の結果、上記モデルでは、等価なフォレンシック透かしを区別することは明らかに不可能である。
【０１２５】
以降の利用のため、まずマトリックスが等価となるための必要十分条件が求められる。このため、いくつかの補題が求められる。第１の補題は、大まかにはニブル順列とニブル変換の順序が互いに変更可能であることを述べるものである。第２の補題は、ニブル変換に先行するニブル順列が線形マップであるときを調べるものである。
・補題１  πをニブル順列とし、ｆ＝（ｆ１，．．．，ｆ８）を可逆ニブル変換とする。このとき、
【０１２６】
【数４５】
2010515945.tif 000047
となる。ただし、
【０１２７】
【数４６】
2010515945.tif 000048
である。
【０１２８】
証明：ｘ＝（ｘ１，．．．，ｘ８）Ｔが任意の３２ビットベクトルである場合（ただし、ｘ１，．．．，ｘ８はニブル）、ベクトル
【０１２９】
【数４７】
2010515945.tif 000049
は、すべてのｉに対して、
【０１３０】
【数４８】
2010515945.tif 000050
を充足する。ここで、
【０１３１】
【数４９】
2010515945.tif 000051
であり、すべてのベクトルｘに対して、
【０１３２】
【数５０】
2010515945.tif 000052
である。
・補題２  πをニブル順列とし、ｈ＝（ｈ１，．．．，ｈ８）を可逆ニブル変換とし、Ｋを
【０１３３】
【数５１】
2010515945.tif 000053
となるような可逆線形マップとする。このマップのマトリックスＫが、ｉ，ｊ＝１，．．．，８に対して４×４のサブマトリックスＫｉ，ｊに分割されていると仮定する。このとき、各ｈｉは、ニブル上の可逆線形マップである。さらに、各ｊに対して、Ｋｉ，ｊ≠０とτ（ｉ）＝ｊは同値である。
【０１３４】
証明：Ｋ＝（Ｋ１，．．．，Ｋ８）Ｔが８つの４×３２のマトリックスＫ１，．．．，Ｋ８に分割されるとする。ここで、ｘ＝（ｘ１，．．．，ｘ８）Ｔが任意の３２ビットベクトルである場合（ただし、ｘ１，．．．，ｘ８はニブル）、ベクトル
【０１３５】
【数５２】
2010515945.tif 000054
は、すべてのｉに対して、
【０１３６】
【数５３】
2010515945.tif 000055
を充足する。次に、ｊを任意とし、ｊ＝τ（ｓ）とする。マトリックスＫｓ＝（Ｋｓ，１，．．．，Ｋｓ，８）が４×４のサブマトリックスＫｓ，１，．．．，Ｋｓ，８に分割されると仮定する。ここで、すべてのｉ≠ｊに対してｘｉ＝０であって、ｘｊ＝ｚが任意である場合、（１０）から、
【０１３７】
【数５４】
2010515945.tif 000056
となり、この結果、
【０１３８】
【数５５】
2010515945.tif 000057
は、それが可逆であるため非ゼロの線形マップとなる。さらに、ｚ，ｕを任意とし、すべてのｉ≠ｒ，ｓに対して、ｘｓ＝ｚ，ｘｒ＝ｕ，ｘｉ＝０とすることによって、すべてのｉ≠τ−１（ｊ）に対して、Ｋｉ，ｊ＝０となる。
【０１３９】
これら２つの補題から、以下が得られる。
・定理３  Ｎ＝（Ｎ１，．．．，Ｎ８）Ｔ，Ｍ＝（Ｍ１，．．．，Ｍ８）Ｔを２つのマトリックスとし、それぞれがサイズ４×３２のサブマトリックスＮ１，．．．，Ｎ８，Ｍ１，．．．，Ｍ８に分割されるとする。このとき、Ｎ，Ｍは、ｉ＝１，．．．，８に対して、
【０１４０】
【数５６】
2010515945.tif 000058
となるような可逆の４×４のマトリックスの集合Ｌ１，．．．，Ｌ８とニブル順列ｖが存在する場合、かつその場合に限って、等価である。
【０１４１】
証明：Ｍ，Ｎが等価であると仮定する。このとき、
【０１４２】
【数５７】
2010515945.tif 000059
となるようなニブル順列π，σと、可逆ニブル変換ｆ，ｇが存在する。この結果、
【０１４３】
【数５８】
2010515945.tif 000060
となる。
【０１４４】
補題１を用いて、
【０１４５】
【数５９】
2010515945.tif 000061
は、適切なニブル順列τと可逆ニブル変換ｈに対して、
【０１４６】
【数６０】
2010515945.tif 000062
と記述できる。このとき、線形マップＫ＝ＮＭ−１に対して、
【０１４７】
【数６１】
2010515945.tif 000063
が成り立ち、補題２により、τ（ｉ）≠ｊのとき、マップ
【０１４８】
【数６２】
2010515945.tif 000064
は可逆であり、Ｋｉ，ｊ＝０である。この結果、
【０１４９】
【数６３】
2010515945.tif 000065
が得られ、ｊ＝τ（ｉ），ｖ＝τ−１とすると、
【０１５０】
【数６４】
2010515945.tif 000066
が得られる。
【０１５１】
逆は、Ｎ，Ｍの２つのマトリックスは、当該条件が成り立つ場合に等価であることは明らかである。
・系４  可逆マトリックスＮをｉ，ｊ＝１，．．．，８に対してサイズ４×４のサブマトリックスＮｉ，ｊに分割されるとする。このとき、Ｎは、各ニブル行と各ニブル列において、ちょうど１つのサブマトリックスＮｉ，ｊが非ゼロである場合、かつその場合に限って、サイズ３２×３２の単位行列に等価である。
【０１５２】
証明：定理３の直接的な結果である。
【０１５３】
仮定された攻撃モデルにおいて、攻撃者は、それの透かしであるサイズ３２×３２のマトリックスを等価マトリックスに変換するが、他の何れにも変換できない。定理３は、所与の何れかのマトリックスに等価なマトリックスの最大数を推定し、これにより、実質的に異なるフォレンシック透かしの最小数を推定するのに利用可能である。このため、Ｎｉｎｖ（ｎ）を可逆なサイズｎ×ｎの（バイナリ）マトリックスの個数を示すとする。周知であり、容易に理解されるように、
【０１５４】
【数６５】
2010515945.tif 000067
であり、この結果、
【０１５５】
【数６６】
2010515945.tif 000068
である。また、８つのニブルに対する順列の個数は、
【０１５６】
【数６７】
2010515945.tif 000069
である。以下は、定理３の結果である。
・定理５  所与のサイズ３２×３２のマトリックスＭに等価なマトリックスの個数Ｎｅｑ（Ｍ）は、
【０１５７】
【数６８】
2010515945.tif 000070
を充足する。
【０１５８】
証明：定理３により、各マトリックスＮは、Ｎｉｎｖ（４）の選択肢のそれぞれについて、８つの可逆なサイズ４×４のマトリックスＬ１，．．．，Ｌ８と、８！個存在するニブル順列τとにより決定される。
・系６  少なくとも
【０１５９】
【数６９】
2010515945.tif 000071
個の等価でない可逆なサイズ３２×３２の（バイナリ）マトリックス（非等価な透かし）が存在する。
【０１６０】
次に、Ｎ個のフォレンシック透かしＭ１，．．．，ＭＮが提供されているとしたとき、攻撃者が自分の透かしを等価な透かしＮに変更したと仮定する。攻撃者のオリジナルの透かしを構成するため、未知のニブル順列π、可逆ニブル変換ｆ及び可逆マトリックスＮにより、式
【０１６１】
【数７０】
2010515945.tif 000072
であることが知られているマップＴの入出力を観察できることが上述された。攻撃者を特定するため、（１３）のマトリックスＮが所与のマトリックスＭに等価であるかテストすることが可能であることが必要である。まず、一般性を失うことなく、Ｍ＝Ｉの単位行列であると仮定されてもよい。実際、必要に応じて、Ｔの代わりに、演算
【０１６２】
【数７１】
2010515945.tif 000073
を調べることが可能であり、
【０１６３】
【数７２】
2010515945.tif 000074
の形式を有する。定義から、ＮＭ−１がＩに等価である場合、かつその場合に限って、ＮはＭに等価であることは明らかである。
【０１６４】
以下において、所与のマップ
【０１６５】
【数７３】
2010515945.tif 000075
がＩに等価なＮを有しているかテストするための手順が概略される。これについて、このタスクは、ｉ＝１，．．．，ｍに対する出力ベクトルｙｉ＝Ｔ（ｘｉ）を調べることが、ＮがＩに等価であるか決定するのに十分となるような３２ビット入力ベクトルｘ１，．．．，ｘｍを生成することである。以下において、使用される入力ベクトルの個数ｍが少なくとも３２である場合に、等価性をテストする方法が説明される。
【０１６６】
ｍ＝３３とする。ｊ＝１，．．．，３２に対して、ｘｊ＝ｅｊとする。ただし、ｅｊは、第ｊビットに１を有し、他のすべてのビットに０を有する第ｊ単位ベクトルを示す。最終的には、すべてがゼロのベクトルｘ３３＝０をとる。ｉ＝１，．．．，３２に対して第ｊ出力ベクトルを示すためｙｊ＝Ｔ（ｅｊ）を記述し、最後の出力ベクトルを示すためｃ＝Ｔ（０）を記述する。ｃ＝（ｃ１，．．．，ｃ８）Ｔがニブルｃ１，．．．，ｃ８を有すると仮定する。ｉ＝１，．．．，８に対して、Ｃｉをそれのすべての列がｃｉに等しいサイズ４×４のマトリックスを示すとする。
【０１６７】
ここで、ｊ＝１，．．．，３２に対して、それの第ｊ列としてベクトルｙｊを有するサイズ３２×３２のマトリックスＹを考える。Ｙをサイズ４×４のサブマトリックスＹｉ，ｊに分割する。ここで、（ａ）各ニブル行ｉにおいて、サブマトリックスＹｉ，ｓの１つ以外のすべてがＣｉに等しく、（ｂ）各ニブル列ｊにおいて、Ｙｒ，ｊの１つ以外のすべてがＣｒに等しい場合、ＮはＩに等価である。逆に、これが成り立たない場合、ＮはＩに等価でない。（実際、Ｎが可逆であると知られている場合、（ｂ）のテストのみで十分である。なぜなら、（ｂ）は（ａ）を意味するためである。）
これは、以下のように説明される。３２ビットポジションを８つのニブルポジション集合Ｊ１＝｛１，２，３，４｝，．．．，Ｊ８＝｛２９，３０，３１，３２｝に分割する。Ｎをｉ，ｊ＝１，．．．，８に対するサイズ４×４のサブマトリックスＮｉ，ｊに分割する。まず、ＮがＩに等価であると仮定する。系４によると、８つのニブル行の各行お跳び８つのニブル列の各列において、ちょうど１つのサブマトリックスＮｉ，ｊが非ゼロである場合、ＮはＩに等価である。このため、Ｎｉ，ｊがτ（ｉ）＝ｊであるときに非ゼロとなるような順列τが存在する。８つのニブル列の各列において、ちょうど１つのサブマトリックスＮｉ，ｊが非ゼロである場合、ニブル魚宇蓮について同じことが成り立つか、又はすべてのサブマトリックスがゼロとなるニブル行が存在する。Ｎが可逆である場合、第２の可能性は生じ得ない。
【０１６８】
まず、ｃ＝Ｔ（０）を考える。明らかに、Ｎ（０）＝０であり、このため、
【０１６９】
【数７４】
2010515945.tif 000076
であり、すべてのｉに対して、
【０１７０】
【数７５】
2010515945.tif 000077
となる。
【０１７１】
次に、｛１，．．．，４｝のあるｓに対して、ニブル集合Ｊｊに含まれるｒ、すなわち、ｒ＝４ｊ＋ｓを考える。このとき、Ｎｉ，ｊの第ｓ列に等しいｚｒ，ｉにより、
【０１７２】
【数７６】
2010515945.tif 000078
となり、この結果、おそらくτ（ｉ）＝ｊのときを除いて、４ビットのオールゼロのベクトルｚｒ，ｉ＝０となる。このとき、第ｒ出力ベクトル
【０１７３】
【数７７】
2010515945.tif 000079
は、
【０１７４】
【数７８】
2010515945.tif 000080
を充足する。
【０１７５】
このため、τ（ｉ）＝ｊであるときを除いて、
【０１７６】
【数７９】
2010515945.tif 000081
となる。これは、Ｊｊのすべてのｒに対して成り立ち、ｙｒ，ｉがサブマトリックスＹｉ，ｊの第ｓ列であるため、おそらくτ（ｉ）＝ｊであるときを除いて、Ｙｉ，ｊ＝Ｃｉとなる。
【０１７７】
逆に、ＮがＩに等価でないと仮定する。このとき、ニブル行ｉ１，ｉ２（ｉ１≠ｉ２）に２つの非ゼロサブマトリックスを有する列ｊのニブル列が存在する。
【０１７８】
【数８０】
2010515945.tif 000082
の列ｓ１と、
【０１７９】
【数８１】
2010515945.tif 000083
の列ｓ２の双方が非ゼロとなるようなカラムｓ１，ｓ２が１，．．．，４に存在する。ここで、ｒ１＝８ｊ＋ｓ１，ｒ２＝８ｊ＋ｓ２とし（ニブルポジション集合ｊの双方）、２つのベクトル
【０１８０】
【数８２】
2010515945.tif 000084
を考える。
【０１８１】
【数８３】
2010515945.tif 000085
である場合、
【０１８２】
【数８４】
2010515945.tif 000086
は共に非ゼロであり、このため、ｔ＝１，２に対して
【０１８３】
【数８５】
2010515945.tif 000087
となる。この結果、出力ベクトル
【０１８４】
【数８６】
2010515945.tif 000088
のニブルπ（ｉｔ）は、ｔ＝１，２に対して、
【０１８５】
【数８７】
2010515945.tif 000089
に等しくなく、このため、マトリックスＹは所望の式を有さない。
【０１８６】
以下は、上記手順のシンプルな定式化を表す。まず、ｃ＝（ｃ１，．．．，ｃ８）をｃ＝Ｔ（０）として計算する。次に、各ニブルｊ＝１，．．．，８に対して、Ｔの元での４つの単位ベクトルｅ８ｊ＋１，．．．，ｅ８ｊ＋４の像ｕ１，．．．，ｕ４とｃとを比較する。ここで、ニブルτ（ｊ）においてのみベクトルｕ１，．．．，ｕ４がｃと異なるような一意的なニブル数τ（ｊ）が存在すべきである。各ｊに対してこれが成り立つ場合、ＮはＩに等価であり、そうでない場合、ＮはＩに等価でない。
【０１８７】
この手順は、ほとんど最適である。実際、次の定理は、少なくとも３２の入力ベクトルが等価性を決定するのに必要とされることを示す。
・定理７  ｘ１，．．．，ｘ３１を任意の３１の入力ベクトルとする。このとき、すべてのｉに対してＮｘｉ＝ｘｉとなるようなＩに等価でないサイズ３２×３２のマトリックスＮが存在する。
【０１８８】
証明：ｂをすべてのベクトルｘｉに直交する非ゼロベクトルとし（空間全体の次元が３２であるため、このようなベクトルは存在しなければならない）、
【０１８９】
【数８８】
2010515945.tif 000090
とする。ｖを（ｂ，ｖ）＝１となるベクトルとし、このため、
【０１９０】
【数８９】
2010515945.tif 000091
である。最後に、
【０１９１】
【数９０】
2010515945.tif 000092
をｗ≠ｖのＨの外部の第２のベクトルとする。このため、（ｂ，ｗ）＝１であり、（ｂ，ｖ−ｗ）＝０、すなわち、
【０１９２】
【数９１】
2010515945.tif 000093
である。
【０１９３】
【数９２】
2010515945.tif 000094
をそれ自身にマップし（このため、ＮはＨ上の単位として機能する）、ｖをｗにマップする線形可逆マップＮを考える。このとき、
【０１９４】
【数９３】
2010515945.tif 000095
が成り立つ。ただし、ｂ＝（β１，．．．，β３２）はビットβｉから構成される。実際、ｘ＝（ｘ１，．．．，ｘ３２）である場合、
【０１９５】
【数９４】
2010515945.tif 000096
となり、
【０１９６】
【数９５】
2010515945.tif 000097
に対して、Ｎｘ＝ｘであり、
【０１９７】
【数９６】
2010515945.tif 000098
となる。
【０１９８】
最後のステップは、（１４）と同様のマトリックスによるＮがＩに等価でないようなＨの外部のｗを選択可能であることを示すためのものである。このため、ニブルｖ１，．．．，ｖ８に対してｖ＝（ｖ１，．．．，ｖ８）とし、ニブルｂ１，．．．，ｂ８に対してｂ＝（ｂ１，．．．，ｂ８）とする。このとき、２つのケースを区別する。
【０１９９】
あるｊ≠１についてｂｊ≠０である場合、ｉ≠ｊに対してｗ＝（ｗ１，．．．，ｗ８）（ただし、ｗｉ＝ｖｉ）と、あるニブルｕｊ≠０に対してｗｊ＝ｖｊ＋ｕｊ（ただし、（ｕｊ，ｂｊ）＝０）とする。このとき、ｉ≠ｊ及びｕｊ≠０に対して、ｗ−ｖ＝ｕ＝（ｕ１，．．．，ｕ８）（ただし、ｕｉ＝０）となる。
【０２００】
ｂ２＝・・・＝ｂ８＝０である場合、ｂ１≠０となる。ここで、ｉ≠２及びｗ２≠ｖ２に対して、ｗ＝（ｗ１，．．．，ｗ８）（ただし、ｗｉ＝ｖｉ）とする。再び、ｗ≠ｖ及び（ｗ，ｂ）＝（ｗ１，ｂ１）＝（ｖ１，ｂ１）＝（ｖ，ｂ）＝１であるため、
【０２０１】
【数９７】
2010515945.tif 000099
となる。
【０２０２】
何れのケースでも、Ｎの第１ニブル列は、ニブル行１とニブル行ｊ≠１（第１のケース）又はニブル行２（第２のケース）の双方において非ゼロとなり、このため、系４により、何れのケースでも、ＮはＩに等価でない。
【０２０３】
結論：おそらく、Ｎ＝Ｉであり、Ｎ≡Ｉである。しかし、Ｎ＝Ｔの可能性もある（πとｆが同一であるケースを考えよ）。
・等価性テスト
マップＴは、ある未知のニブル順列π＝（π１，．．．，π８）、可逆ニブル変換ｆ＝（ｆ１，．．．，ｆ８）、及びサイズ３２×３２の可逆線形変換Ｎに対して、
【０２０４】
【数９８】
2010515945.tif 000100
を有すると仮定する。さらに、任意の入力ベクトルｘが与えられると、出力ベクトルｙ＝Ｔ（ｘ）を計算することができると仮定する。このとき、以下のアルゴリズムは、Ｎが所与の任意のサイズ３２×３２の可逆線形変換Ｍに等価であるか決定する。（ここで、０は３２ビットのオールゼロのベクトルを示し、ｅｉはビットｉにｉを有し、他のすべてのビットに０を有する３２ビットの第ｉ単位ベクトルを示す。）
【０２０５】
【数９９】
2010515945.tif 000101
［等価でない透かしの生成］
サイズ４×４のサブマトリックスＷｉ，ｊ（ｊ＝１，．．．，８）に分割するとき、以下の性質を有するサイズ３２×３２のすべてのバイナリマトリックスＷから構成される集合｛Ｗ｝を考える。
・ブロックＷｉ，ｊは、ｉ＞ｊのときは常にオールゼロのマトリックスである。
・すべてのブロックＷｉ，ｉは、サイズ４×４の単位行列である。
従って、任意のマトリックス
【０２０６】
【数１００】
2010515945.tif 000102
は可逆であり、
【０２０７】
【数１０１】
2010515945.tif 000103
の形式を有する。
【０２０８】
｛Ｗ｝からの任意の２つの相異なるマトリックスは等価でない。これを確認するため、定理３を用いる。Ｎ，Ｍを｛Ｗ｝からの２つの等価なマトリックスとする。このとき、ｉ＝１，．．．，８に対して、Ｎτ（ｉ）＝ＬｉＭｉとなるようなサイズ４×４の可逆マトリックスＬ１，．．．，Ｌ８と、ニブル順列τとが存在する。ここで、Ｍ，Ｎは｛Ｗ｝の要素であるため、Ｍ，Ｎのニブル行ｉは、ちょうど（ｉ−１）個のオールゼロブロックから始まり、ブロックＩに続く。また、ＬｉＭｉは、ちょうど（ｉ−１）個のオールゼロブロックから始まり、ある非ゼロのブロックＬｉに続く。この結果、ニブル行数ｉは、ＮｉとＬｉＭｉから一意的に特定することができる。従って、順列τは同一でなければならず、各Ｌｉは単位行列でなければならず、Ｎ＝Ｍである。｛Ｗ｝は、（２１６）７＋６＋・・・＋１＝２４４８＞１０１３４個のマトリックスを含むことに留意されたい。｛Ｗ｝から異なるマトリックスを選択することによって、異なる透かしが生成されるかもしれない。
【０２０９】
異なる等価性クラスの透かしを生成する他の方法は、線形変換Ｎをランダムに選択し、等価性検出のためのアルゴリズムを用いて、選択したＮが以前に選択された線形変換に等価であるか検証することを含む。
【０２１０】
上記では、ルックアップテーブルのネットワークとそれらの難読化及び透かし処理の特別なケースに着目した。透かし処理の原理はこれら特別なケースの性質とは独立に適用可能であることが理解されるであろう。例えば、ＡＥＳは、符号化及びミキシング全単射を用いたｗｈｉｔｅ−ｂｏｘ実装を説明するため、メインキャリアとして使用された。しかしながら、当業者は、ＡＥＳ、符号化及びミキシング全単射がルックアップテーブルのネットワークへの透かしの適用に必須でないことを理解するであろう。
【０２１１】
図１０は、本発明の一実施例を示す。図は、計算方法６０２の実装のコピーのユーザを追跡することを容易にするシステム６００を示す。計算方法６０２のユーザ６３２は、それらの実装があるステーション６１０を有し、この場合、各ユーザは各自のステーションと一体とされるかもしれない。あるいは、ユーザは、異なるＩＰアドレスを有するか、又は自らのログインＩＤとパスワードとを用いて実装を取得するシステムにログインするようにしてもよい。ルックアップテーブルのネットワークの各バージョンなどのオブジェクトは、ＩＰアドレスやログインＩＤなどを参照して、ユーザ又はステーションに関連付けされてもよい。オブジェクトとステーション又はそのユーザとを関連付けるための他の配布システム及び方法は、当業者に明らかであろう。システム６００は、ハードウェア及び／又はソフトウェアにより実現されてもよい。例えば、それは、コンテンツプロバイダのサーバ上で実行されるソフトウェアモジュールとすることも可能である。システム６００は、ユーザ６３２（又はステーション６１０）の少なくとも１人への配布のため、計算方法６０２の実装を用意するよう構成される。このため、システム６００は、計算方法の各ステップを表すルックアップテーブルのネットワークを生成するためのネットワーク生成手段６０４を有する。例えば、ルックアップテーブルのネットワークは、図１〜９に関して上述されたｗｈｉｔｅ−ｂｏｘ実装の形式をとる。しかしながら、所与の計算方法についてこのようなルックアップテーブルのネットワークを生成する他の方法は、当業者に想到され、適用されるかもしれない。
【０２１２】
システム６００はさらに、パーソナル化手段６０６を有する。パーソナル化手段は、ルックアップテーブルのネットワークの複数の異なるバージョンを生成する。それは、ルックアップテーブルのネットワークにおける少なくとも１つの値を変更することによってこれを実行する。ルックアップテーブルのネットワークの異なるバージョンにより実行可能な計算の最終結果は、特に関連する入力値ドメインについて、ルックアップテーブルのネットワークの異なるバージョンについて実質的に同一である。関連する入力値ドメインは、例えば、それの仕様に従って実装の日々の使用において処理される必要のある値に対応する。この変更は異なる方法により行われてもよい。例えば、第１のルックアップテーブルは、ルックアップテーブルの出力値のペアを交換することによって変更されてもよい。ネットワークの同一の出力値を維持するため、ルックアップテーブルのネットワークの少なくとも１つの次のテーブルのエントリが、第１のルックアップテーブルになされた変更を無効にするよう交換されてもよい。ルックアップテーブルのネットワークの構成に応じて、ネットワークの出力値を全体として変更することなく、単一のルックアップテーブルに変更をすることが可能である。ネットワークはまた、関連する入力値ドメインの結果が実質的に変更されない限り、さらなるルックアップテーブルにより拡張されてもよいし、又は再構成されてもよい。
【０２１３】
システム６００はまた、関連付け手段６０８を有する。関連付け手段は、生成された異なるネットワークと、データベース６１４に格納されているユーザ又はステーションとを、それらのＩＰアドレス、ログインＩＤ又は他の何れかのタイプのタグを用いて関連付ける。ユーザに関連付けされた生成されたルックアップテーブルのネットワークは、データベース６１４に格納される。
【０２１４】
一実施例では、計算方法は、ＡＥＳなどの暗号化方式により特徴付けされる。ＤＥＳなどの他の暗号化方式及びデジタル著作権管理に適した他の暗号化方式が、当業者に明らかであろう。暗号化方式は、暗号キーと共に機能する。パーソナル化手段は、同一のキーにより同一の暗号化方式を実現するすべてのルックアップテーブルのネットワークの複数のバージョンを生成するよう構成される。このように、複数のユーザが、同一の暗号化方式とキーとを用いてデータを暗号化又は解読するかもしれない。同時に、ルックアップテーブルの個別のバージョンは、一意的であり、これにより、あるバージョンのルックアップテーブルから、当該バージョンに関連付けされたユーザが誰であるか求めることが可能である。これは、特に、多数のユーザに同一の配信データが提供される放送システムに有用である。配信データは暗号化され、すべてのユーザは、配信データを解読するため、同一の暗号化方式とキーとを適用する必要がある。パーソナル化手段は、例えば、暗号化方式の異なるｗｈｉｔｅ−ｂｏｘ実装を生成する。
【０２１５】
一実施例では、パーソナル化手段は、計算方法のｗｈｉｔｅ−ｂｏｘ実装を生成するよう構成される。ｗｈｉｔｅ−ｂｏｘ実装の具体例が上述された。それらは、原則的に任意の計算方法について生成されるかもしれない。パーソナル化手段６０８は、最終結果が変更されないように、ルックアップテーブルの値を変更するよう構成される。例えば、ニブル符号化又はミキシング全単射の１以上が変更されてもよい。あるいは、若しくは加えて、ネットワークの構成が変更されてもよい。すなわち、ネットワークをデータが流れる方法が、変更されてもよい。各ルックアップテーブルは、ルックアップテーブルのネットワークに追加又は削除されてもよい。
【０２１６】
一実施例では、パーソナル化手段は、線形又は非線型演算子を用いてｗｈｉｔｅ−ｂｏｘ実装を難読化するよう構成される。この演算子は、ネットワークの第１の複数のルックアップテーブルに統合され、演算子の逆演算は、ネットワークの第２の複数のルックアップテーブルに統合される。異なる演算子が異なるバージョンにおいて利用される。これは、攻撃者が選択された演算子のすべてのトレースを削除することを所望するとき、攻撃者は第１及び第２の複数のルックアップテーブルの複雑な相互依存性について多くの洞察を必要とすることを意味する。これらのテーブルの１以上は、入力及び／又は出力符号化を有してもよい。これは、使用された演算子を求め、これらの入出力符号化が異なるバージョンについて異なって選択されるとき、さらなる特徴的な性質を透かしに付加することを困難にする。ＡＥＳの具体例に適用するとき、演算子はミキシング全単射であり、入出力符号化はニブル符号化であるかもしれない。
【０２１７】
好ましくは、パーソナル化手段は、等価なクラスが、入出力符号化に変更を適用することによって、対応するルックアップテーブルのネットワークが相互に取得可能な演算子を有する異なる等価なクラスの演算子を用いて各バージョンを生成するよう構成される。入出力符号化は、攻撃者により容易に変更されるため、これらの符号化に対する変更後、それらが互いに依然として区別できるように異なる演算子を選択することが必要とされる。“等価性問題”というタイトルのセクションにおいて説明された等価性クラスが、この具体例である。
【０２１８】
より一般には、パーソナル化手段６０６は、攻撃者に想到されると仮定される変更の集合からの変更をバージョンに適用することによって、異なる等価性クラスのバージョンを生成するよう構成される。これは、バージョンを生成するため変更をランダムに適用し、それが以前に生成されたバージョンの等価性クラスに属しているか検証することによって実現されてもよい。同一の等価性クラスのバージョンがすでに生成されていると判明している場合、新たに生成されるバージョンは破棄され、破棄されたバージョンを置換するため、他のバージョンが生成される。あるいは、パーソナル化手段６０６は、式（１５）に従って、
【０２１９】
【数１０２】
2010515945.tif 000104
の１つのマトリックスを（擬似）ランダムに選択するよう構成される。
【０２２０】
一実施例は、配布サーバ６２４を有する。配布サーバ６２４は、データベース６１４からユーザ６３２に係るバージョンを取得し、このバージョンをユーザ６３２又はユーザのステーション６１０に提供する。意図した受信者しか当該バージョンを受信しないことを確保するため、それはユーザ固有のキーにより暗号化される。コンテンツ（オーディオデータ、ビデオデータ、ソフトウェアなど）は、ルックアップテーブルのネットワークのバージョンにおいて実装された暗号キーと暗号化方式により暗号化される。暗号化されたバージョンとコンテンツは、ユーザ６３２のステーション６１０に送信される。これは配布方法の単なる一実施例であることは理解されるであろう。パーソナル化されたバージョンは、何れかの方法、すなわち、完全に又は部分的に暗号化されるか又は暗号化されないなどにより配布されてもよい。それらは、ネットワーク（インターネットなど）又は記憶媒体（ＣＤなど）を介し配布可能である。バージョンを安全に配布する１つの方法は、配信チャネルを介しルックアップテーブルのネットワークの一部のみを送信することによるものである。この部分は、タイプＩＩテーブル２０（対応するタイプＩＶテーブル２２を有する）とすることが可能である。対応するタイプＩＶテーブル２６を有するタイプＩＩＩテーブル２４は、例えば、スマートカードなどを用いて異なる方法によりステーションに提供されてもよい。これは、透かしがスマートカードに存在するルックアップテーブルの部分により完全に又は部分的に規定されるため、透かしとユーザとの間の関連付けを強化する。
【０２２１】
一実施例は、ステーション６１０を有する。ステーション６１０は、計算方法の各ステップを表すルックアップテーブルのネットワークを受け付けるための入力を有する。ネットワークは、ユーザ固有のキーにより暗号化されてもよく、この場合、それが最初に解読される。ネットワークは、配布サーバ６２４から受信される。ステーション６１０は、データを処理するため、ルックアップテーブル６３４のネットワークを適用するデータ処理ユニット６１２を有する。データは、例えば、ＣＤ−ＲＯＭ又は配布サーバ６２４などから提供されるオーディオ又はビデオコンテンツなどである。ルックアップテーブルのネットワークは、システム６００によりそれに適用された透かしを有する。サーバ６２４から受信したルックアップテーブルのネットワークは原則的に一意的であるが、ルックアップテーブルの他のネットワークが、攻撃者などによりステーション６１０の入力に提供することが可能である。当該他のルックアップテーブルのネットワークは、配布サーバ６２４から受信したルックアップテーブルのネットワークより多くの又は異なる機能を提供してもよい。ステーションは当該他のバージョンのルックアップテーブルのネットワークの機能を有してもよいが、それは一意的な性質を有し、発信元のユーザ又はステーションに関連付けされるため、ルックアップテーブルのバージョンのソースを追跡することが可能である。
【０２２２】
一実施例は、計算方法の実装のコピーを特定するシステム６１６を有する。システム６１６は、これらの実装の異なるバージョンを有するデータベース６１４に接続される。ルックアップテーブルの１以上のネットワーク（以降において入力バージョンと呼ばれる）が、データベース６１４に格納されているバージョンとマッチングするため、システム６１６の入力６１８に提供される。各実装は、計算方法の各ステップを表すルックアップテーブルのネットワークを有する。システム６１６は、これらのバージョンの少なくとも１つと実装におけるルックアップテーブルとを比較する比較手段６２０を有する。比較手段は、バイト単位の比較により実現可能であり、入力バージョンがデータベースのバージョンと一致するか報告するようにしてもよい。それはまた、入力バージョンとデータベースのバージョンとの間の類似度を報告してもよい。それはまた、入力バージョンに最も類似するデータベース６１４のバージョンを求めるようにしてもよい。
【０２２３】
システム６１６は、入力バージョンが属する等価性クラスを構成し、同一の等価性クラスを有するデータベースの１以上のバージョンを特定する等価性クラス構成手段６２２を有してもよい。等価性クラスは、好ましくは、攻撃者に想到されると仮定される変更群からの変更をバージョンに適用することによって、互いに変換可能なすべてのバージョンを含む。
【０２２４】
図１１は、コンテンツプロバイダのサーバなどにより実現可能な本発明の一実施例を示す。それはまた、標準的なＰＣにより実現可能である。図は、処理対象となるコンテンツ及び／又はルックアップテーブルのネットワークのバージョンなどの情報を提供する通信ポート９５を示す。通信ポート９５は、インターネットなどに接続するよう構成される。ルックアップテーブルのネットワークのバージョンはまた、ＤＶＤやＣＤなどの記憶媒体９６に格納されてもよい。図はさらに、プロセッサ９２とメモリ９１を示す。メモリは、プロセッサに与えられた方法によりルックアップテーブルのネットワークの複数のバージョンを生成させる命令を有する。ルックアップテーブルのネットワークは、例えば、特定の暗号キーによる暗号化方式など、計算方法のステップを表す。メモリ９１には、生成される各バージョンが、テーブルなどにより各ユーザに関連付けされる。図はまた、オペレータによりシステムを操作するためのキーボード及び／又はマウスなどの入力９４及びディスプレイ９３を示す。
【０２２５】
他の実施例がまた、図１１を参照して説明されてもよい。本実施例は、パーソナルコンピュータ、セットトップボックス、デジタルビデオプレーヤー、ターミナル、又はスマートカードなどのステーションを有する。ステーションは、ユーザに係るルックアップテーブルのネットワークのバージョンを取得するため、サーバに接続する通信ポート９５を有する。さらに又はあるいは、ステーションは、ルックアップテーブルのネットワークのバージョンが格納されるＣＤやＤＶＤなどの記憶媒体９６を読み込む手段を有する。ステーションは、ルックアップテーブルのネットワークを適用することによって、データを処理するプロセッサ９２を有する。データはまた、通信ポート９５及び／又は記憶媒体９６を介し取得されてもよい。例えば、ルックアップテーブルのネットワークは、計算方法の各ステップを表す。計算方法は、任意のデータ処理方法を有してもよい。例えば、ＰｉｘｅｌＰｌｕｓなどのビデオエンハンスメントアルゴリズムの１以上の処理ステップが、ルックアップテーブルのネットワークを用いて実現されてもよい。また、ルックアップテーブルのネットワークは、暗号化アルゴリズムや解読アルゴリズムなどの暗号化方式の各ステップを実現してもよい。このような解読アルゴリズムは、ディスプレイ９３上に再生するコンテンツを解読するのに利用可能である。システムは、ユーザにシステムを制御させるためのキーボードやリモコンなどのユーザ入力９４を有する。
【０２２６】
本発明はまた、本発明を実行するよう構成されるコンピュータプログラム、特にキャリア上のコンピュータプログラムに拡張されることが理解されるであろう。プログラムは、ソースコード、オブジェクトコード、部分的にコンパイルされた形式などのコード中間ソース及びオブジェクトコードの形式、又は本発明による方法の実現に使用するのに適した他の何れかの形式であってもよい。キャリアは、プログラムを担持可能な任意のエンティティ又は装置であってもよい。例えば、キャリアは、ＣＤ  ＲＯＭや半導体ＲＯＭなどのＲＯＭやフロッピー（登録商標）ディスキャハードディスクなどの磁気記憶媒体などの記憶媒体を有してもよい。さらに、キャリアは、電気若しくは光ケーブル又は無線若しくは他の手段などにより伝送される電気又は光信号などの伝送可能キャリアであってもよい。プログラムがこのような信号に実現されるとき、キャリアはこのようなケーブル又は他の装置若しくは手段により構成されてもよい。あるいは、キャリアは、プログラムが埋め込まれ、関連する方法の実行のため又は実行における利用のために構成される集積回路であってもよい。
【０２２７】
上述した実施例は、本発明を限定するものでなく例示するものであり、当業者は、添付した請求項の範囲から逸脱することなく他の多数の実施例を設計可能であることに留意すべきである。請求項において、括弧内の参照符号は、請求項を限定するものとして解釈されるべきでない。“有する”という動詞とその派生語の使用は、請求項に記載された以外の要素又はステップの存在を排除するものでない。要素に先行する“ある”という冠詞は、当該要素が複数存在することを排除するものでない。本発明は、複数の異なる要素を有するハードウェアと、適切にプログラムされたコンピュータにより実現されてもよい。複数の手段を記載した装置クレームにおいて、これらの手段のいくつかは単一かつ同一のハードウェアアイテムにより実現されてもよい。特定の手段が互いに異なる従属クレームに記載されるという事実は、これらの手段の組み合わせが効果的には利用可能でないことを示すものでない。
【図１】
2010515945.tif 000105
【図２】
2010515945.tif 000106
【図３】
2010515945.tif 000107
【図４】
2010515945.tif 000108
【図５】
2010515945.tif 000109
【図６】
2010515945.tif 000110
【図７】
2010515945.tif 000111
【図８】
2010515945.tif 000112
【図９】
2010515945.tif 000113
【図１０】
2010515945.tif 000114
【図１１】
2010515945.tif 000115
【国際調査報告】
2010515945.tif 000116
2010515945.tif 000117
2010515945.tif 000118