(57)【特許請求の範囲】
【請求項１】
少なくとも一個の送信器から数個のデコーダに向けてブロードキャストされるデータを暗号化および／または復号化する追跡可能な方法であって、該方法は、前記各デコーダの個々の正当ユーザの中の不正者であって、権限のないサード・パーティに対して秘密データを通信し、該サード・パーティが、前記送信器によりブロードキャストされるデータを暗号化および／または復号化できるようにする不正者の識別を可能とし、
前記ブロードキャストされるデータの暗号化（８６）において、前記送信器は少なくともひとつの第１の秘密暗号化関数を適用し、かつ、
前記ブロードキャストされたデータの復号化（９２）において、前記デコーダのすべては前記第１の関数もしくはその逆関数と同一である少なくともひとつの第２の秘密暗号化関数を適用し、各デコーダはこの目的のためにメモリ（２１）内に記録された前記第２の関数の数学的記述を参照する、
という追跡可能な方法において、
前記第２の関数の適用（９２）において、各デコーダが参照する該第２の関数の前記数学的記述は、デコーダ毎に又はデコーダのグループ毎に異なることから、参照される前記数学的記述により、すべての前記デコーダの内の特定のデコーダが又はデコーダのグループが一意的に識別され、各デコーダの前記メモリ内に記録された前記数学的記述（ＦKj）は、前記第２の秘密関数を形成するために相互に所定の順序で構成されなければならない数個の基本関数（Ｇi,j）で形成されることを特徴とする、追跡可能な方法。
【請求項２】
各基本関数Ｇi,jは、以下の各式の内のひとつの式による少なくとも３個の関数の合成関数に等しいことを特徴とする、請求項１記載の方法：
Ｇ1,j＝ｆ’1,jｏｇσj(1)ｏＳ
Ｇ2,j＝ｆ’2,jｏｇσj(2)ｏｆ1,j
………………………………………………………
Ｇr-1,j＝ｆ’r-1,jｏｇσj(r-1)ｏｆr-2,j
Ｇr,j＝Ｔｏｇσj(r)ｏｆr-1,j
式中、
Ｇi,jは、ｊがデコーダを又はデコーダのグループを特定する添数として、デコーダｊの第ｉ番目の基本関数であり、
関数ｆi,jおよびｆ’i,jは、各基本関数Ｇi,jを相互間で非可換とする予め定められた関数であり、
σjは、すべての添数｛１；…；ｒ｝の順列であって各デコーダに対し又はデコーダの各グループに対して一意的である順列であり、
ｇσj(t)は、相互間で可換であるｒ個の非線形の予め定められた関数ｇiから形成される所定の集合の内の第σj(t)番目の関数であり、かつ、
ＳおよびＴは、基本関数Ｇ1,jおよびＧr,jの暗号解析を困難とすることができる予め定められた関数である。
【請求項３】
各関数ｆ’i,jは関数ｆi,jの逆関数ｆ-11,jに等しい、請求項２に記載の方法。
【請求項４】
前記関数ｆi,jは、該有限体（Ｌ）の要素のｎ−組の集合（Ｌn）の線形関数であることを特徴とする、請求項２または３に記載の方法。
【請求項５】
関数ＳおよびＴは可逆であることを特徴とする、請求項２〜４のいずれか一項に記載の方法。
【請求項６】
前記関数ＳおよびＴは、有限体（Ｌ）自体に向けた該有限体（Ｌ）の要素のタプルの集合（Ｌn）の線形関数であることを特徴とする、請求項２〜５のいずれか一項に記載の方法。
【請求項７】
前記関数ｇiは、各基本関数Ｇi,jが多変数暗号化アルゴリズムの暗号化ブロックに対応するように選択されることを特徴とする、請求項２〜６のいずれか一項に記載の方法。
【請求項８】
各関数ｇiはｇi（ａ）＝ａeiの形態であり、ａはｑ個の要素を備える次数ｎの基本体Ｌの拡大Ｌ’の要素であることを特徴とする、請求項２〜７のいずれか一項に記載の方法。
【請求項９】
指数ｅiは１＋ｑθ1＋…ｑθi＋…＋ｑθd-1の形態であり、式中、指数θiは所定の整数であることを特徴とする、請求項８記載の方法。
【請求項１０】
デコーダにより請求項１〜９のいずれか一項に記載の追跡可能な暗号化および／または復号化方法を実行させるプログラム。
【請求項１１】
送信器により請求項１〜９のいずれか一項に記載の追跡可能なデータ暗号化および／または復号化方法を実行させるプログラム。
【請求項１２】
ブロードキャストされたデータを暗号化および／または復号化する追跡可能なシステムであって、該システムは、正当ユーザの中の不正者であって、権限のないサード・パーティに対して秘密データを通信し、該サード・パーティが、ブロードキャストされたデータを暗号化および／または復号化できるようにする不正者の識別を可能にし、
該システムは、
ブロードキャストされたデータを暗号化することができる送信器であって、少なくともひとつの第１の秘密暗号化関数を適用することでメッセージを直接的に処理してから前記メッセージをブロードキャストする送信器と、
ブロードキャストされたデータを復号化する数個のデコーダであって、すべてのデコーダは前記ブロードキャストされたメッセージの直接的処理のために前記第１の関数と同一またはその逆関数と同一である第２の秘密暗号化関数を適用可能であり、この目的のために各デコーダは前記第２の関数の数学的記述が記録されるメモリ（２１）を備える数個のデコーダと、
を備える追跡可能なシステムにおいて、
各デコーダのメモリは、他のデコーダのメモリ内または他のデコーダのグループのメモリ内に記録された数学的記述とは異なる前記第２の関数の数学的記述を含むことから、この数学的記述によって、すべてのデコーダの内の特定のデコーダは又はデコーダのグループは一意的に識別され、各デコーダの前記メモリ内に記録された前記数学的記述（ＦKj）は、前記第２の秘密関数を形成するために相互に所定の順序で構成されなければならない数個の基本関数（Ｇi,j）で形成されることを特徴とする、追跡可能なシステム。
【請求項１３】
請求項１２記載の追跡可能なデータ暗号化および／または復号化システムのデコーダに接続されるメモリであって、
前記第２の秘密関数と等価的な数学的記述であって前記デコーダにより使用され得る数学的記述を備え、この数学的記述は、当該数個の基本関数（Ｇi,j）の各々が以下の各式の内のひとつの式による少なくとも３個の関数の合成関数に等しい数個の基本関数（Ｇi,j）から成ることを特徴とするメモリ：
Ｇ1,j＝ｆ’1,jｏｇσj(1)ｏＳ
Ｇ2,j＝ｆ’2,jｏｇσj(2)ｏｆ1,j
………………………………………………………
Ｇr-1,j＝ｆ’r-1,jｏｇσj(r-1)ｏｆr-2,j
Ｇr,j＝Ｔｏｇσj(r)ｏｆr-1,j
式中、
Ｇi,jは、ｊがデコーダを又はデコーダのグループを特定する添数として、デコーダｊの第ｉ番目の基本関数であり、
関数ｆi,jおよびｆ’i,jは、各基本関数Ｇi,jを相互間で非可換とすることができる所定関数であり、
σjは、すべての添数｛１；…；ｒ｝の順列であって各デコーダに対し、又はデコーダの各グループに対して一意的である順列であり、
ｇσj(t)は、相互間で可換であるｒ個の非線形の所定関数ｇiから形成される所定の集合の内の第σj(t)番目の関数であり、かつ、
ＳおよびＴは、基本関数Ｇ1,jおよびＧr,jの暗号解析を困難とすることができる所定関数である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブロードキャストされたデータを暗号化および／または復号化する追跡可能な方法およびシステム、ならびに、該方法を実施する記録媒体に関する。
【０００２】
さらにくわしくは、本発明は、
ブロードキャストされたデータを暗号化する場合、送信器は少なくともひとつの第１の秘密暗号化関数を適用し、かつ、
上記ブロードキャストされたデータを復号化する場合、すべてのデコーダは上記第１の関数またはその逆関数と同一の第２の秘密暗号化関数を適用し、この目的のために各デコーダはメモリ内に記録された上記第２の関数の数学的記述を用いる、
追跡可能な方法に関する。
【背景技術】
【０００３】
追跡可能な暗号化方法とは、不正者（ｔｒａｉｔｏｒ）を追跡する方法を実施することができる方法である。
【０００４】
不正者追跡方法は、ビデオ、テレビ、画像、音楽、テキスト、ウェブ・ページ、電子ブック、プログラムなどの暗号化されたマルチメディア・コンテンツをブロードキャスト・チャネル上で配信するサービスに対する海賊行為に対抗すべく用いられる。不正者追跡方法の目的は、上記サービスのひとり以上の正当ユーザが、自身の復号化機器に埋め込まれた秘密鍵および復号化アルゴリズムから演繹されるデータを再配信することを防止して、上記コンテンツに対して不法ユーザ（海賊）が通常のアクセスを不可能にすることである。これらの方法によれば、かかる不正行為が行われたとしても、不法ユーザに対して再配信されたデータに基づき、上記コンテンツを配信するサービス事業者またはさらに一般的には権限者により、不正行為の起点における少なくともひとりの正当ユーザのＩＤ（身元）を、再構成することができることが保証される。本明細書では以下、不正行為の起点における正当ユーザを“不正者”という。
【０００５】
不正者を追跡するという概念は、ベニー・コール（Ｂｅｎｎｙ  Ｃｈｏｒ）、アモス・フィアット（Ａｍｏｓ  Ｆｉａｔ）およびモニ・ナオール（Ｍｏｎｉ  Ｎａｏｒ）により、１９９４年における論文：“暗号作成術における進歩、不正者の追跡”−Ｃｒｙｐｔｏ’９４、コンピュータサイエンスにおける講義ノート、第８３９巻、シュプリンガ出版社、１９９４年、第２５７〜２７０頁（”Ｔｒａｃｉｎｇ  Ｔｒａｉｔｏｒｓ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ”−Ｃｒｙｐｔｏ’９４，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ８３９，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９４，  ｐｐ．  ２５７−２７０）にて最初に提案された。この論文においては、暗号システムにおける最初の追跡技術が提唱された。不正者追跡方法が実施され得る暗号システムは、“追跡可能”と称される。これらの技術の殆どすべては、組み合わせ的な性質である。換言すると、暗号システムの各正当ユーザに対しては、基本鍵の集合（一般的には十分に大きな集合）から鍵の部分集合が割当てられる。ひとりのユーザに対して割当てられた基本鍵のこの部分集合は、各ユーザに対して一意的でありかつ該ユーザ自身の個人鍵を形成する。
【０００６】
このシステム内でブロードキャストされるデータは、暗号化されたメッセージを含む。暗号化された各メッセージは、コンテンツ暗号化鍵により暗号化されたコンテンツと、各々が基本鍵により暗号化されたヘッダとから形成される。各ヘッダは、コンテンツ暗号化鍵の一部を表す値を含んでいる。
【０００７】
各ユーザがこれらのメッセージの内のひとつのメッセージを受信したとき、各ユーザは自身の基本鍵の部分集合を使用することで、受信したヘッダに含まれた幾つかの値を復号化する。各ユーザは次に、これらの復号化された値を組み合わせてコンテンツ暗号化鍵を再構成すると共に、この再構成されたコンテンツ暗号化鍵はメッセージのコンテンツを復号化すべく使用される。
【０００８】
上記システムの正当ユーザのひとりが自身の個人鍵を不法ユーザに対して通信する場合に、この追跡可能な暗号システムは、上記不法ユーザにより使用された個人鍵から不正者のＩＤを追跡することができる。
【０００９】
しかし、組み合わせ的な性質の不正者追跡方法は、相当の量のヘッダのブロードキャストを必要とするという不都合を有する。特に、ブロードキャストされるべきヘッダの個数は上記システムの正当ユーザの人数の対数に比例し、防護が求められる不正者の連合体の最大サイズｋなどの他のパラメータに比例する。ここで連合体というのは、ｋ人の不正者のグループであって、生成される新たな個人鍵の検証が行われる限りにおいては、各不正者の内のひとりの不正者のＩＤが開示されない場合、各自の個人鍵を組み合わせて、暗号化されたコンテンツを復号化するために使用される新たな個人鍵を生成しようとして、グループを形成するｋ人の不正者のグループを意味する。
【発明の開示】
【００１０】
本発明は、多数のヘッダのブロードキャストを必要としない新規な不正者追跡方法を提案することで、この欠点を克服することを目的とする。
【００１１】
ゆえに本発明は、上述の如き不正者追跡方法において、第２の関数を実施するときに、各デコーダが参照するこの第２の関数の数学的記述は、デコーダ毎にまたはデコーダのグループ毎に異なり、その結果一意的に参照される数学的記述によって、すべてのデコーダの中から特定のデコーダもしくはデコーダ・グループが識別されることを特徴とする不正者追跡方法である。
【００１２】
該方法においては、自身の第２の秘密関数の数学的記述を不法ユーザに対して通信した不正者を、送信されたデータを復号化すべく上記不法ユーザにより使用されたこの第２の関数の数学的記述の分析に基づいて追跡することが可能である。当該システムにおける各数学的記述の構造によれば、上記記述は上記不正者のＩＤを表す。ところで、上記の組み合わせ的方法によれば、各デコーダにおいて一群の個人鍵が使用されるという事実を考慮すると、同一のコンテンツ暗号化鍵が異なる形態で暗号化されて、数回送信される必要がある。ブロードキャストされるコンテンツの最初に載置されるヘッダは、この目的のために使用される。ゆえにヘッダに含まれる情報は極めて冗長であり、かつ、各デコーダは受信したヘッダの一部のみを処理する。
【００１３】
しかし本発明の方法において、不正者の識別は、もはや一群の個人鍵の使用に基づくのではなく、第１の暗号化関数もしくはその逆関数と同じひとつの同一の暗号化関数の個々の記述を送信器が使用することに基づくという事実を考慮すると、ブロードキャストされるデータの少なくとも一部が冗長化されることはもはや必要とされない。その結果、暗号化されたメッセージを上記方法を用いてブロードキャストするために必要とされるヘッダの個数は、組み合わせ的な方法を用いて同一メッセージをブロードキャストするために必要とされるヘッダの個数より少ない。
【００１４】
上記方法の他の特性によれば、該方法は、
上記第２の暗号化関数は非冗長データを処理可能であり、
各デコーダのメモリ内に記録された上記数学的記述ＦKjは、上記第２の秘密関数を形成するために所定順番で次々と構成されるべき数個の基本関数Ｇi,jから形成され、
各基本関数Ｇi,jは、以下の各式の内のひとつの式のように少なくとも３個の関数の合成物に等しく：
Ｇ1,j＝ｆ’1,jｏｇσj(1)ｏＳ
Ｇ2,j＝ｆ’2,jｏｇσj(2)ｏｆ1,j
………………………………………………………
Ｇr-1,j＝ｆ’r-1,jｏｇσj(r-1)ｏｆr-2,j
Ｇr,j＝Ｔｏｇσj(r)ｏｆr-1,j
式中、
Ｇi,jは、ｊをデコーダを又はデコーダのグループを特定する添数として、デコーダｊの第ｉ番目の基本関数であり、
関数ｆi,jおよびｆ’i,jは、各基本関数Ｇi,jを相互間で非可換とすることができる予め定められた関数であり、
σjは、すべての添数｛１；…；ｒ｝の順列であって、各デコーダに対し又はデコーダの各グループに対して一意的である順列であり、
ｇσj(t)は、相互間で可換であるｒ個の非線形の予め定められた関数ｇiから形成される所定の集合の内の第σj(t)番目の関数であり、かつ、
ＳおよびＴは、基本関数Ｇ1,jおよびＧr,jの暗号解析を困難とすることができる予め定められた関数であり、
各関数ｆ’i,jは関数ｆi,jの逆関数ｆ-11,jに等しく、
上記関数ｆi,jは、有限体Ｌから、有限体Ｌの要素のタプルの集合Ｌnへの線形関数であり、
関数ＳおよびＴは可逆であり、
上記関数ＳおよびＴは、有限体Ｌへの完成集合体Ｌの要素のタプルの集合Ｌnの線形関数であり、
上記関数ｇiは、各基本関数Ｇi,jが多変数暗号化アルゴリズムの暗号化ブロックに対応するように選択され、
各関数ｇiはｇi（ａ）＝ａeiの形態であり、ａはｑ個の要素を備える次数ｎの基本体Ｌの拡大Ｌ’の要素であり、
指数ｅiは１＋ｑθ1＋…ｑθi＋…＋ｑθd-1の形態であり、式中、指数θiは所定の整数である、
ことを特徴とする。
【００１５】
本発明の他の主題は、データ記録媒体において、該データ記録媒体は、当該命令がデコーダにより実行される場合、本発明の追跡可能な方法を実行する該命令を備えることを特徴とするデータ記録媒体である。
【００１６】
本発明のさらに他の主題は、データ記録媒体において、該データ記録媒体は、当該命令が送信器により実行される場合、本発明の追跡可能な方法を実行する該命令を備えることを特徴とするデータ記録媒体である。
【００１７】
本発明のさらに他の主題は、ブロードキャストされたデータを暗号化および／または復号化する追跡可能なシステムであって、該システムは、個々の正当ユーザの中の不正者であって権限のないサード・パーティに対して秘密データを通信し、該サード・パーティがブロードキャストされたデータを暗号化および／または復号化することができるようにする不正者を識別することができると共に、
ブロードキャストされたデータを暗号化することができる送信器であって、少なくともひとつの第１の秘密暗号化関数を適用することができる送信器と、
ブロードキャストされたデータを復号化することができる数個のデコーダであって、すべてのデコーダは上記第１の関数と同一またはその逆関数と同一である、少なくともひとつの第２の秘密暗号化関数を適用可能であり、この目的のために各デコーダは上記第２の関数の数学的記述が記録されるメモリを備えるという数個のデコーダと、
を備える追跡可能なシステムにおいて、
各デコーダのメモリは、他のデコーダのメモリ内または他のデコーダのグループのメモリ内に記録された数学的記述とは異なる上記第２の関数の数学的記述を含み、この数学的記述によって、すべてのデコーダの内の特定のデコーダは又はデコーダのグループは一意的に識別されることを特徴とする追跡可能なシステムである。
【００１８】
最後に、本発明のさらに他の主題は、本発明に係る追跡可能な暗号化および／または復号化システムのデコーダに関連するメモリにおいて、
それは、上記第２の秘密関数と等価的な数学的記述であって上記デコーダにより使用され得る数学的記述を備え、この数学的記述は、当該数個の基本関数Ｇi,jの各々が以下の各式の内のひとつの式のように少なくとも３個の関数の合成に等しいという数個の基本関数Ｇi,jから成ることを特徴とするメモリに関する。
【００１９】
Ｇ1,j＝ｆ’1,jｏｇσj(1)ｏＳ
Ｇ2,j＝ｆ’2,jｏｇσj(2)ｏｆ1,j
………………………………………………………
Ｇr-1,j＝ｆ’r-1,jｏｇσj(r-1)ｏｆr-2,j
Ｇr,j＝Ｔｏｇσj(r)ｏｆr-1,j
式中、
Ｇi,jは、ｊがデコーダを又はデコーダのグループを特定する添数として、デコーダｊの第番目の基本関数であり、
関数ｆi,jおよびｆ’i,jは、各基本関数Ｇi,jを相互間で非可換とすることができる所定関数であり、
σjは、すべての添数｛１；…；ｒ｝の順列であって各デコーダに対し又はデコーダの各グループに対して一意的である順列であり、
ｇσj(t)は、相互間で可換であるｒ個の非線形の所定関数ｇiから形成される所定の集合の内の第σj(t)番目の関数であり、かつ、
ＳおよびＴは、基本関数Ｇ1,jおよびＧr,jの暗号解析を困難とすることができる所定関数である。
【発明を実施するための最良の形態】
【００２０】
本発明は、図面を参照して、単なる一例として与えられる以下の説明によりさらに良好に理解されよう。
【００２１】
図１は、追跡可能な暗号システム２を示している。このシステム２は、暗号化されたデータの送信器４と、データ伝送ネットワーク６と、送信器４によりネットワーク６を介してブロードキャストされた暗号化データを復号化することができる複数個のデコーダとを備えて成る。システム２はＮ個のデコーダを備え、Ｎは１００、１０００またはそれ以上の数より大きい整数である。ここでは、図示を簡素化するために唯一個のデコーダ８が示される。他のデコーダ（図示せず）は、たとえばデコーダ８と同一である。以下の説明において、このデコーダ８には添数ｊが付される。
【００２２】
一例として、送信器４は、有料テレビ・チャネルの送信器である。この送信器４は、コンテンツＢaを暗号化するモジュール１０と、制御ワードＣＷaを算出するモジュール１２とを備える。コンテンツＢaはここでは、通常のすなわち暗号化されないテレビ・チャネルを表す一連のデータ・ビットで形成される。モジュール１２によって、数学的記述ＦKにより定義される暗号化関数を実行することができる。この暗号化関数は、ｎ個のキャラクタにわたりコード化されたヘッダＥＢaを直接的に処理することで、該ヘッドを、これもまたｎ個のキャラクタにわたりコード化された制御ワードＣＷaへと変換することを目的としており、ｎはたとえば１００より大きい正の整数である。ここでは一例として、各キャラクタは“０”または“１”のいずれかである。
【００２３】
この目的のために送信器４には、上記暗号化関数の数学的記述ＦKが記録されるメモリ１４が接続される。数学的記述とは、すべての入力値に対してこの関数の対応出力値を計算するために行われるべき数学的演算の厳密なシーケンスを決定する一群のデータであって、該計算を行う上でプログラムに対しては該関数の入力値以外の一切の値を提供する必要がないという一群のデータである。この記述ＦKは、上記送信器により直接的に使用され得るフォーマットでメモリ１４に記録されることから、モジュール１２は、この記述に基づいてその暗号化関数を実行することができる。ここでは、例えば記述ＦKは、コンピュータ・プログラムを形成する一連の命令である。ただし以下の説明において、各関数の数学的記述は単に、従来の記号を用いて表された数学的関係の形態で示される。以下に説明される数学的関係に対応する単一もしくは複数のコンピュータ・プログラムを書くことは容易である。
【００２４】
記述ＦKは、図２に関してさらに詳細に説明される。
【００２５】
モジュール１０は、コンテンツＢaを暗号化するためにモジュール１２により構築された制御ワードＣＷaによりパラメータ化された暗号化関数Ｅを実行することができると共に、対応して暗号化されたコンテンツＣＢaを出力することができる。ここで暗号化関数Ｅは、従来の可逆な暗号化関数である。それは例えば、ＡＥＳ（高度暗号化規格）暗号化関数、または、“ワンタイム・パッド（ｏｎｅ  ｔｉｍｅ  ｐａｄ）”の名称で知られた暗号化アルゴリズムである。
【００２６】
制御ワードＣＷaを用いてモジュール１０により暗号化された各コンテンツＢaに対して、送信器４は、上記システムにおけるすべてのデコーダに向けて、データ対をブロードキャストすることができる。このデータ対は、ヘッダＥＢaと暗号化されたコンテンツＣＢaとにより形成される。送信器４によりネットワーク６を介して送信もしくはブロードキャストされるデータを復号化するために、デコーダ８は、制御ワードＣＷaを計算する計算モジュール２０と、暗号化されたコンテンツＣＢaを復号化する復号化モジュール２２とを備える。
【００２７】
モジュール２０は、暗号化関数を実行することができる。この関数は、記述ＦKとは異なる数学的記述ＦKjにより定義される。さらに正確には、この記述ＦKjは、システム２の他の各デコーダにおいて使用されるすべての記述ＦKjから異なっている。ただし、数学的記述ＦKjは記述ＦKとは異なるとしても、それが定義する上記関数は同一である。結果として、モジュール２０によるヘッダＥＢaの変換により、制御ワードＣＷaが、すなわち、モジュール１２を用いて求められたのと同一の制御ワードが求められ得る。これらの条件下で、記述ＦKjは記述ＦKと等しいと称される。
【００２８】
送信器４と同様に、デコーダ８には、数学的記述ＦKjが記録されるメモリ２１が接続される。
【００２９】
記述ＦKjは、図２に関してさらに詳細に説明される。
【００３０】
モジュール２２は、復号化関数Ｄを実行することができる。この関数Ｄは関数Ｅの逆関数であることから、受信されたヘッダＥＢaに基づきモジュール２０により構築された制御ワードＣＷaを用いて、コンテンツＣＢaを復号化することができる。
【００３１】
デコーダ８はまた、モジュール２２により復号化されたコンテンツＢaをテレビ受像機２６に対して送信して、通常のとおり表示することもできる。
【００３２】
送信器４および上記デコーダの各々は、データ記録媒体上に記録された命令を実行することができる従来のプログラム可能計算機に基づいている。この目的のためにメモリ１４および２１は、送信されたデータを暗号化かつ復号化するための秘密パラメータに加えて、図２における方法を実行するための命令を含んでいる。
【００３３】
次に、図２の方法を参照して、システム２の機能を説明する。
【００３４】
図２における方法は、３つの主要段階に分割される。システム２の設定段階５０、システム２の使用段階５２、および、システム２の種々の正当ユーザの中からひとりの不正者を検索する検索段階５４である。
【００３５】
段階５０は、数学的記述ＦKを構築する構築ステップ６０で開始する。この目的のために、ｒは正の整数として、演算６２においてｒ個の非線形関数ｇiが生成される。関数ｇiの個数ｒは以下の関係を検証すべく選択される：
（１）  Ｎ＜ｒ！
式中、Ｎはシステム２におけるデコーダの個数である。
【００３６】
これらの関数ｇiは、合成の演算において、相互間で可換であるべく構築されることから、以下の関係が検証される：
（２）∀ｉ，ｌ∈｛１，…，ｒ｝、ｉ≠ｌ  ｇiｏｇl＝ｇlｏｇi
式中、記号ｏは２つの数学的関数の合成の演算を表す。
【００３７】
ここで、これらの関数の各々は、ひとつのタプルを別のタプルへと変換する非線形関数である。タプルは、ここではｎ個の要素の集合を意味する。たとえば次数（ｎ−１）の多項式の一群のｎ個の係数はタプルと考えることができる。
【００３８】
ゆえに、各関数ｇiはｎ個の入力変数を取ると共に、計算されたｎ個の変数を出力する。それらの各々は、ｎ変数のｎ次非線形方程式の系に対応し、ｎは、ヘッダＥＢaのキャラクタの個数に対応する正の整数である。
【００３９】
各関数ｇiは、至る所でそれが線形関数により構成されたときに、多変量暗号化アルゴリズムの暗号化ブロックＧiを形成すべく選択される。多変数暗号化アルゴリズムの例は、たとえば、松本勉（Ｔｓｕｔｏｍｕ  Ｍａｔｓｕｍｏｔｏ）氏および今井秀樹（Ｈｉｄｅｋｉ  Ｉｍａｉ）氏の“暗号作成術における進歩、効率的な署名照合およびメッセージ暗号化に対する公開二次多項式タプル”−ＥＵＲＯＣＲＹＰＴ  ’８８（クリストフ・ゲー・ギュンター編）、コンピュータサイエンスにおける講義ノート、第３３０巻、シュプリンガ出版社、１９８８年、第４１９〜４５３頁（”Ｐｕｂｌｉｃ  Ｑｕａｄｒａｔｉｃ  Ｐｏｌｙｎｏｍｉａｌ−ｔｕｐｌｅｓ  ｆｏｒ  Ｅｆｆｉｃｉｅｎｔ  Ｓｉｇｎａｔｕｒｅ  Ｖｅｒｉｆｉｃａｔｉｏｎ  ａｎｄ  Ｍｅｓｓａｇｅ  Ｅｎｃｒｙｐｔｉｏｎ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ”−ＥＩＪＲＯＣＲＹＰＴ  ’８８  （Ｃｒｉｓｔｏｐｈ  Ｇ．  Ｇｕｅｎｔｈｅｒ，  ｅ  ｄ），  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ３３０，  Ｓｐｒｉｎｇｅｒ，  １９８８，  ｐｐ．  ４１９−４５３））において松本氏および今井氏により提案されたＣ*アルゴリズムである。多変量暗号化アルゴリズムの他の例は、ＳＦＬＡＳＨ  ｖ２（ＮＥＳＳＩＥプロジェクト、署名、インテグリティおよび暗号化に対する新たな欧州方式［ＮＥＳＳＩＥ  ｐｒｏｊｅｃｔ，  Ｎｅｗ  Ｅｕｒｏｐｅａｎ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｓｉｇｎａｔｕｒｅｓ，  Ｉｎｔｅｇｒｉｔｙ  ａｎｄ  Ｅｎｃｒｙｐｔｉｏｎ］）、および、ＨＦＥ（ＰＡＴＡＲＩＮジャック、不可視フィールド方程式（ＨＦＥ）および多項式の同型写像（ＩＰ）：非対称アルゴリズムの新たな２つの系統［ＰＡＴＡＲＩＮ  Ｊａｃｑｕｅｓ  Ｈｉｄｄｅｎ  Ｆｉｅｌｄｓ  Ｅｑｕａｔｉｏｎｓ  （ＨＦＥ）  ａｎｄ  Ｉｓｏｍｏｒｐｈｉｓｍｓ  ｏｆ  Ｐｏｌｙｎｏｍｉａｌｓ  （ＩＰ）：  ｔｗｏ  ｎｅｗ  ｆａｍｉｌｉｅｓ  ｏｆ  Ａｓｙｍｍｅｔｒｉｃ  Ａｌｇｏｒｉｔｈｍｓ］（Ｅｕｒｏｃｒｙｐｔ  ９６、シュプリンガ出版社、第３３〜４８頁）である。
【００４０】
各要素ｇiから得られる暗号化ブロックＧiの単純でコンパクトな記述を求めるために、各関数ｇiは、単項式と称される単項関数として選択される。
【００４１】
一例としてここでは、関数ｇiの各々は、ｑ個の要素を備える次数ｎの基本体Ｌの拡大Ｌ’を各要素に関して演算する。たとえばここでは、ｑ＝２およびＬ＝｛０，１｝である。
【００４２】
拡大Ｌ’は、次式の形態の一群の多項式である：
【００４３】
【数１】
0004673302.tif 000002
【００４４】
式中、
各係数は体Ｌの要素であり、
添数ｉは整数であり、かつ、
Ｘは変数である。
【００４５】
拡大Ｌ’は、多項式の加法と、次式により定義される次数ｎの既約多項式を法とした乗法とを備える：
【００４６】
【数２】
0004673302.tif 000003
【００４７】
式中、
係数ｐiは体Ｌの所定要素であり、かつ、
Ｘは変数である。
【００４８】
一例として各関数ｇiは、拡大Ｌ’から拡大Ｌ’への関数であり、次の形態である：
ｇi（ａ）＝ａei
式中、
ａは拡大Ｌ’の要素であり、かつ、
指数ｅiは１＋ｑθ1＋…ｑθi＋…＋ｑθd-1の形態の所定の整数であり、式中、ｑは体Ｌの要素の個数でありかつ指数θiは所定整数である。
【００４９】
ここで、ｄは２に等しく選択されることから、関数ｇiの各々の指数ｅiは１＋ｑθ1の形態を有する。
【００５０】
この形態における指数ｅiの利点は、拡大Ｌ’の各要素ａが係数のタプル（ａ0、ａ1、…、ａn-1）により特定されるなら、式ｂ＝ｇi（ａ）により定義される拡大Ｌ’の要素ｂの係数ｂ0、ｂ1、…、ｂn-1の各々はａの係数ａ0、ａ1、…、ａn-1による次数ｄのみの関数として書かれるということである。すなわち、ここでは、ｄが２に等しい特定の場合における二次関数である。この特定の場合において、各係数ｂiは以下の二次関数の形態で書かれ得る：
ｂi＝（ｃ0ａ0＋…＋ｃn-1ａn-1）＋（ｃ0,1ａ0ａ1＋…＋ｃ0,n-1ａ0ａn-1）＋（ｃ1,2ａ1ａ2＋…＋ｃ1,n-1ａ1ａn-1）＋…＋ｃn-2,n-1ａn-2ａn-1
式中、ｎ個の係数ｃuおよびｎ（ｎ−１）／２個の係数ｃU,Vは体Ｌに属する定数である。
【００５１】
ゆえに、選択された指数の形態により、各関数ｇiの数学的記述はコンパクトでありかつ容易にメモリ内に記録され得る。
【００５２】
引き続き、演算６４においては、ＬnからＬnへの２つの関数ＳおよびＴが選択される。ここでＬnは体Ｌの各要素から形成された一群のタプルである。好適には、これらの関数ＳおよびＴは線形可逆関数である。
【００５３】
たとえば、これらの関数ＳおよびＴの各々の数学的記述は、各要素が体Ｌに属するｎ個の要素×ｎ個の要素の行列である。
【００５４】
記述ＦKは引き続き、演算６６において、各関数ｇiおよび関数ＳおよびＴを以下の様式で構成することにより構築される：
（３）ＦK＝Ｔｏｇrｏｇr-1ｏ…ｏｇ2ｏｇ1ｏＳ
ＦKを構築した後、該方法は、各デコーダに対する等価的記述ＦKjを構築するために、構築ステップ７０により継続される。
【００５５】
ステップ７０において、上記システムにおける各デコーダｊに対し、集合｛１，２，…，ｒ｝の１つの一意的な順列σjが演算７２に定義される。この順列σjはたとえば、ランダムに構築されるか、または、デコーダを特定する添数ｊと秘密パラメータＭとから演繹される。
【００５６】
なお、上記式（１）が成立することから、上記システムにおける各デコーダに対して一意的な順列を構築することが可能であることに注意されたい。
【００５７】
引き続き、演算７４において、ユーザｊに対してはｒ−１個の全単射ｆi,jが選択される。これらの全単射ｆi,jの各々は、集合Ｌnのそれ自体の上への可逆関数である。これらの全単射ｆi,jはたとえば、各要素が集合Ｌに属するｎ個の要素×ｎ個の要素の行列を用いて記述される。
【００５８】
たとえば演算７４において、各全単射ｆi,jは、集合Ｌnのそれ自体の上への一群の可逆線形適用からランダムに引出される。別の可能性は、これらの全単射ｆi,jの各々をデコーダの添数ｊと秘密パラメータＭとから演繹することである。
【００５９】
最後に、演算７６においては数学的記述ＦKjが構築される。この目的のために、デコーダｊに対してはｒ個の基本関数Ｇi,jが構築される。これらの関数Ｇi,jは、関数Ｓ、Ｔおよびｇiを以下の如く構成することで構築される。
【００６０】
（４）
Ｇ1,j＝ｆ-11,j，ｏｇσj(1)ｏＳ
Ｇ2,j＝ｆ-12,j，ｏｇσj(2)ｏｆ1,j
………………………………………………………
Ｇr-1,j＝ｆ-1r-1,j，ｏｇσj(r-1)ｏｆr-2,j
Ｇr,j＝Ｔｏｇσj(r)ｏｆr-1,j
式中、
ｆ-11,jは全単射ｆi,jの逆であり、かつ、
ｇσj(t)は、ｔは集合｛１，２，…，ｒ｝に属するものとし、デコーダｊの順列σjにより添数ｔの順列に等しい添数ｉを有するという関数ｇiである。
【００６１】
式ｂ＝ｇi（ａ）により定義される拡張Ｌ’の要素ｂの各係数ｂiが次数ｄのみの多項式により記述できるという関数ｇiの特性は、該関数ｇiが至る処で全単射または線形関数により構成されたときに保存される。ゆえに、式ｙ＝Ｇi,j（ｘ）により定義されたＬnの要素ｙの成分は、Ｌnの要素ｘの成分ｘiの次数ｄのみの多項式により記述することができる。たとえばｄが２に等しい場合、成分ｙiは以下の数学的記述を用いて定義される：
ｙ1＝（ｃ’0ｘ0＋…＋ｃ’n-1ｘn-1）＋（ｃ’0,1ｘ0ｘ1＋…＋ｃ’0,n-1ｘ0ｘn-1）＋
（ｃ’1,2ｘ1ｘ2＋…＋ｃ’1,n-1ｘ1ｘn-1）＋…＋ｃ’n-2,n-1ｘn-2ｘn-2
式中、
ｎ個の係数ｃ’uおよびｎ（ｎ−１）／２個の係数ｃ’U,Vは、体Ｌに属する定数である。
【００６２】
ゆえに、１＋ｑθ1の形態の指数ｅiを選択することにより、各基本関数Ｇi,jの数学的記述は簡素かつコンパクトであることから、メモリ空間を殆ど取らない。特に、ここで説明される実施例において各基本関数Ｇi,jの数学的記述は、ｎ変数によるｎ次非線形方程式の系である。
【００６３】
記述ＦKjは、これらのｒ個の基本関数Ｇi,jにより形成される。入力メッセージを式（５）：ＦKj＝Ｇr,jｏＧr-1,jｏ…ｏＧ2,jｏＧ1,jにより処理することにより、記述ＦKを用いて求められるであろう出力メッセージと厳密に同一の出力メッセージが求められる。数学的記述ＦKjとＦKとの等価性は、先行する式において、各基本関数Ｇi,jを、式（４）により与えられるそれの定義により置き換えることで容易に検証される。先行する式においてそのようにすることにより、次式が求められる：
ＦKj＝Ｔｏｇσj(r)ｏｇσj(r-1)ｏ…ｏｇσj(2)ｏｇσj(1)ｏＳ
関数ｇiのすべては相互間で可換であることから、記述ＦKjは記述ＦKと等価的であることが示される。
【００６４】
ゆえに、全単射ｆi,jの機能は基本関数Ｇi,jを相互間で非可換とすることであることは理解される。この場合、記述ＦKの等価的記述を求めるために、各基本関数Ｇi,jは、式（５）における如き添数ｉの昇順にのみ相互に構成され得る。
【００６５】
これに加え、本明細書中で説明される具体的な実施例において試みられる一切の暗号解析に対する上記システムの耐性は、ＩＰ問題としても知られる、多項式の同型性の困難さに基づく。関数Ｇi,jが知られた場合、関数ｇ1〜ｇrのすべてを認識したとしても値σj（ｉ）を特定することは数学的に困難である、と言うのも、各基本関数Ｇi,jにおいては至る所で構成による該基本関数のカモフラージュのために未知関数が使用されるからである。ここでこれらの未知関数は、秘密が守られた関数ＳおよびＴ、ならびに、全単射ｆi,jである。すると、一群の有効な基本関数Ｇi,jを処理する不法ユーザは新たな群の基本関数Ｇ’i,jを構築することは不可能であり、その場合には、σjにより定義された順序関係が、各関数ｇi間で維持されない。換言すると、不法ユーザは各基本関数Ｇi,jから関数Ｓ、Ｔおよびｆi,jを見出すことができないので、該ユーザは、各基本関数Ｇi,jが組み合わされるべき順序を改変できず、これらの基本関数の数学的記述を改変することで満足せねばならない。ゆえに、各基本関数Ｇ’i,jが組み合わされる順番は改変されないので、各関数ｇiが組み合わされる順番も改変されない。この特性の利点は、以下の説明により明らかとなろう。
【００６６】
システム２の各ユーザｊに対して夫々の基本関数Ｇi,jが構築されたなら、それらはステップ８０において配信されると共に、たとえばコンピュータ・プログラムの形態で各デコーダ８のメモリ２１内に記録される。
【００６７】
同様に、ステップ８０において、不正者検索段階５４を実行するために必要な情報が、例えばメモリ１４内に記録される。特に、各基本関数Ｇi,jを構築するために使用される関数のすべて、ならびに、使用される順列σjの各々はこのメモリ１４に記録される。各順列σjと、それに対して使用されたデコーダとの間の関係が記録される。同様に、このメモリ１４には、上記デコーダのＩＤからユーザの識別を可能とする関係が記録される。
【００６８】
各デコーダ８の上記メモリ内に関数Ｇi,jが記録されたなら、システム２の使用段階５２を開始することができる。
【００６９】
この段階５２では、送信器４はステップ８４において、例えば毎秒などのように規則的な時間間隔で新たなヘッダＥＢaをランダムに引出す。
【００７０】
このヘッダＥＢaは、制御ワードＣＷaを求めるために、ステップ８６で、モジュール１２により記述ＦKを用いて変換される。
【００７１】
次にステップ８８において、コンテンツＢaは、関数Ｅおよび制御ワードＣＷaを用いてモジュール１０により変換される。暗号化されたコンテンツＣＢa、およびこの目的のために使用されるヘッダＥＢaは次に、ステップ９０において、送信器４によりネットワーク６を介して、システム２内のすべてのデコーダに向けて、結合してブロードキャストされる。
【００７２】
暗号化データの受信時に各デコーダはまず、ステップ９２において、受信したヘッダＥＢaから制御ワードＣＷaの計算に着手する。このステップにおいてモジュール２０は、式（５）に従う各基本関数Ｇi,jの合成に対応する計算を実施するために、そのメモリ２１に記録された基本関数Ｇi,jの各々を順次的にかつ順番に使用する。
【００７３】
このステップ９２の後でモジュール２０は、送信器４のモジュール１２により構築されたのと同一の制御ワードＣＷaを出力する。
【００７４】
この制御ワードＣＷaおよび関数Ｄを用いて、ステップ９４においてモジュール２２は、受信した暗号化コンテンツＣＢaを復号化する。復号化されると共にモジュール２２により供給されたコンテンツＢaは次に、たとえば通常の表示のためにテレビ受像機２６へと送信される。
【００７５】
ステップ８４および９４は、送信器４によりブロードキャストされる各データ項目またはデータ・フレームに対し、システム２の使用段階全体にわたり反復される。
【００７６】
以下の説明では、デコーダｊのユーザが自身の一群の基本関数Ｇi,jを不法ユーザに送信したことから、この不法ユーザはたとえば、送信器４によりブロードキャストされたデータを聴取料を支払わずに復号化する侵害デコーダを使用することができることが仮定される。ゆえにデコーダｊのユーザは不正者である、と言うのも、該ユーザは秘密データを違法かつ不法に送信することで、送信器４によりブロードキャストされたデータの復号化を許容したからである。
【００７７】
不正者検索段階５４は、ステップ１００において上記不法ユーザの海賊デコーダを捕捉かつ分析することにより開始する。このステップにおいては、当該デコーダに対して不正者により不法に通信された各基本関数Ｇi,jと、受信されたヘッダＥＢaを制御ワードＣＷaへと変換すべくこれらの関数Ｇi,jが組み合わされる順番とを該デコーダにおいて検出するために、デコーダの分析が行われる。
【００７８】
海賊デコーダに見られる各基本関数はここではＧi,pと記され、この場合に添数ｉは、制御ワードＥＢaを変換するために、これらの基本関数が使用される順番を表している。
【００７９】
引き続きステップ１０２においては各関数Ｇi,pが分析され、それの構築の基礎とされた関数ｇiが見出される。上記分析は、たとえばシステム２の操作者により可能である、と言うのも、該操作者は該システムの各ユーザの基本関数Ｇi,jを構築するために使用された関数Ｓ、Ｔ、ｆi,jおよびｇiを認識しているからである。
【００８０】
ゆえに、ステップ１０２の後でシステム２の操作者は、基本関数Ｇ1,pおよび基本関数Ｇ2,pを構築するために使用された関数ｇiの添数を、関数ｇmおよびｇnの添数ｍおよびｎが夫々表すという関数Ｇi,pの各々に対し、基本関数Ｇ1,pは関数ｇmから構築され、基本関数Ｇ2,pは関数ｇnから構築され、以下同様である、と述べることができる。
【００８１】
ゆえに、この情報に基づいて、操作者はステップ１０４において、海賊デコーダにおいて使用された基本関数Ｇi,pの構築中に使用された順列σjを再構築することができる。この順列σjが再構築されたなら、それは、ステップ１０６において、ステップ８０においてメモリ１４に記録された種々の順列と比較される。
【００８２】
上記により、不正者すなわちデコーダｊのユーザは識別される、と言うのも、システム２において、各順列σjは、単一のユーザと関連する単一のデコーダ自体に対応するからである。
【００８３】
したがって、このシステムおよびこの方法は、暗号化されたコンテンツＣＢaを復号化するために必要なデータを、正当ユーザが通信するのを防止できるほど制止的であることがわかる。
【００８４】
試行された暗号解析に対する図２の方法の耐性に関する考察が行われた。これらの考察によれば、特に図２のシステムおよび方法は、ｋを２より大きな正の整数としてｋ人の不正者の連合体により行われる攻撃に耐えることが示された。ｋ人の不正者の連合体という用語によって、夫々の群の基本関数Ｇi,jを共同使用することにより関数ＦKの新たな等価的記述を構築せんとするｋ人の正当ユーザのグループを意味する。これらの不法ユーザはせいぜい、これらのｋ個の群の基本関数Ｇi,jから新たな一群以上の基本関数Ｇi,pを用いてひとつの関数を構築することができるだけであることが示された。ただし、各群の基本関数から自由に抽出された連続的なシーケンスの基本関数Ｇi,jの組み合わせからは、任意の新たな群の基本関数Ｇi,pが得られる。たとえば２人の不正者の連合体に対し、不法ユーザが構築することができる新たな群の基本関数Ｇi,pは、第１不正者の最初のｐ個の基本関数｛Ｇ1,1，Ｇ2,1，…，Ｇp,1｝および第２不正者の最後のｒ−ｐ個の基本関数｛Ｇp+1,2，…，Ｇr,2｝から構成される。不正者のＩＤの試行カモフラージュに対抗するために、関数ｇiの個数ｒは十分に大きく選択されることから、少なくともひとりの不正者は、該不正者自身の基本関数Ｇi,jの群を構築すべく使用された順列σjの一部のみを段階５４において識別することに基づくだけで識別され得る。たとえば、２人の不正者の連合体に対してｒは十分に大きく選択されることから、各不正者の少なくとも一方は、最初のｐ個の基本関数Ｇi,1に基づき又は最後のｒ−ｐ個の基本関数Ｇi,2に基づき識別され得る。
【００８５】
なお、上記方法においては、同一の秘密データ、すなわち記述ＦK、ＦKjに関係付けられた暗号化関数が暗号化および復号化に使用されることから、説明された暗号化方法は対称的暗号化のアルゴリズムと同一の特性を有する。特にこの特性により、ここで説明された方法は非対称的暗号化のアルゴリズムよりも迅速である。
【００８６】
ここで関数Ｓ、Ｔ、ｆi,jは秘密に維持される一方、各関数ｇiは選択的に公開される。
【００８７】
システム２においては、送信器４および各デコーダの両方にて、制御ワードＣＷaを計算する唯一個の同一の関数が使用される。ゆえにこの暗号化関数は可逆である必要はなく、各関数ｇiの選択および構築が容易となる。ただし変形例では、記述ＦKは、暗号化関数に対応すると共に、記述ＦKjは、この暗号化関数の逆関数に対応する。この変形例において、上記システムの個々のデコーダに埋め込まれた個々の記述ＦKjは、相互に等価的であり、かつ、記述ＦKにより定義される関数の逆関数と等価的な記述である。先に説明した記述ＦKjの構築が当てはまり、唯一の相違点は、この変形例においては各関数ｇiが可逆でなければならないことである。この場合、記述ＦKは、たとえばコンテンツＢaを直接的に暗号化すべく使用される一方、等価的な記述ＦKjは、暗号化されたコンテンツＣＢaを直接的に復号化すべく使用される。
【００８８】
ここで、記述ＦKおよびＦKjに対応する暗号化関数は、ｎ個のキャラクタにわたりコード化された最初のメッセージを、同様に同一個数のキャラクタにわたりコード化された変換済みメッセージへと変換する。この暗号化関数は、たとえば非対称的アルゴリズムで見られるのとは対照的に、初期メッセージのサイズに関して変換済みメッセージのサイズを増大しない。変形例では、上記暗号化関数は初期メッセージのサイズに関して変換済みメッセージのサイズを増大する。ただし、変形例におけるサイズの増大は不正者の人数に無関係なままである。
【００８９】
システム２は、単一のデコーダに対して記述ＦKjが関係付けられるという特定の場合において説明された。変形例として、一群のデコーダに対して、ひとつの同一の記述ＦKjが関係付けられる。この変形例では、システム２のすべてのデコーダは、数個のグループにグループ分けされることから、記述ＦKjによれば、特定のひとつのデコーダではなく、この特定のデコーダが属するグループが識別される。
【図面の簡単な説明】
【００９０】
【図１】図１は、本発明に係る追跡可能な暗号システムのアーキテクチャの概略図である。
【図２】図２は、本発明の上記不正者追跡方法のフローチャートである。
【図１】
0004673302.tif 000004
【図２】
0004673302.tif 000005