(57)【要約】【課題】多項式Pの階数を増加させなくても、グローバルな秘密の異なるシェアをより多数、当事者に配布可能にする方法を提供すること。【解決手段】デジタル権利管理 (DRM: Digital Rights Management) フレームワークにしたがって動作する家庭ネットワーク (100) 内のデバイス (101〜105) であることが好ましい第一当事者と第二当事者との間の共通の秘密を生成する方法。これらのデバイスは、信頼できる第三当事者 (TTP: Trusted Third Party) により予め配布されているパラメータ、および他方の当事者から得たパラメータを用いて、2つの多項式 P(x, y) と Q(x, z) の積を評価することにより、共通の秘密を計算する。これらの当事者は、他方の当事者がゼロ知識プロトコルまたはコミットメントに基づいたプロトコルを用いて同じ秘密を生成済みであることを、後で検証することが好ましい。この方法は、特に、チップインディスク・タイプのデバイスなどのパワーが非常に低いデバイスに適している。
2005520395.tif 000002
【特許請求の範囲】
【請求項１】
第一当事者と第二当事者との間の共通の秘密を生成する方法であって、
前記第一当事者が、値 p1 と、第一引数が前記値 p1 により固定されている対称多項式 P(x, y) とを保持し、かつ、
前記第一当事者が、
前記第二当事者に前記値 p1 を送信するステップと、
前記第二当事者から値 p2 を受信するステップと、
多項式 P(p1, y) のp2 を求めることにより共通の秘密 S1 を計算するステップと、
を行う方法において、
前記第一当事者が、値 q1 と、第一引数が前記値 q1 により固定されている対称多項式 Q(x, z) とを更に保持し、かつ
前記第二当事者に q1 を送信するステップと、
前記第二当事者から値 q2 を受信するステップと、
前記秘密 S1 を 
2005520395.tif 000183
として計算するステップと、
を更に行うことを特徴とする方法。
【請求項２】
前記第一当事者が、
乱数 r1 を得るステップと、
2005520395.tif 000184
を計算するステップと、
前記第二当事者に 
2005520395.tif 000185
を送信するステップと、
前記第二当事者から
2005520395.tif 000186
を受信するステップと、
前記秘密 S1 を
2005520395.tif 000187
として計算するステップと、
を更に実行する、請求項1の方法。
【請求項３】
前記第一当事者が、
任意に選択された値 r により乗算された前記値 q1、および、
個々の多項式 P(p1, y) と Q(q1, z) ではなく積 Q(q1, z)P(p1, y) を保持し、かつ
前記第一当事者が、
2005520395.tif 000188
を計算するステップと、
前記第二当事者に
2005520395.tif 000189
を送信するステップと、
前記第二当事者から
2005520395.tif 000190
を受信するステップと、
前記秘密 S1 を
2005520395.tif 000191
として計算するステップと、
を行う、請求項2の方法。
【請求項４】
前記対称多項式 P(x, y) の前記第一引数が前記値 p2 により固定され、前記対称多項式 Q(x, z) の前記第一引数が前記値 q2 により固定されている状態で、前記第二当事者が、値 p2 と値 q2 を保持し、かつ、
前記第二当事者が、
前記第一当事者に q2 を送信するステップと、
前記第一当事者から q1 を受信するステップと、
秘密 S2 を
2005520395.tif 000192
として計算するステップと、
を行い、
このことにより、前記秘密 S2 が前記秘密 S1 に等しい場合は前記共通の秘密が生成済みとなる、請求項1の方法。
【請求項５】
信頼できる第三者が、
(n+1)×(n+1) の対称行列 T を選択するステップと、
行列 T からのエントリを前記多項式 P の各係数として用いて前記多項式 P を構築するステップと、
前記多項式 Q(x, y) を構築するステップと、
前記値 p1、前記値 p2、前記値 q1、および前記値 q2 を選択するステップと、
と
前記値 p1 と、前記値 q1 と、第一引数が前記値 p1 により固定されている前記多項式 P(x, y) と、第一引数が前記値 q1 により固定されている前記多項式 Q(x, z) とを、前記第一当事者に送信するステップと、
前記値 p2 と、前記値 q2 と、第一引数が前記値 p2 により固定されている前記多項式 P(x, y) と、第一引数が値 q2 により固定されている前記多項式 Q(x, z) とを、前記第二当事者に送信するステップと、
を行う、請求項1の方法。
【請求項６】
前記信頼できる第三者が、更に、
値 r を任意に選択し、
前記第一当事者に、前記値 q1 ではなく値 r×q1 を送信し、かつ前記個々の多項式 P(p1, y) と Q(q1, z) ではなく前記積 Q(q1, z)P(p1, y) を送信し、かつ、
前記第二当事者に、前記値 q2 ではなく値
2005520395.tif 000193
を送信し、かつ前記個々の多項式 P(p2, y) と Q(q2, z) ではなく前記積 Q(q2, z)P(p2, y) を送信する、
請求項5の方法。
【請求項７】
前記信頼できる第三者が、更に、
前記値 p1 と前記 p2 を含む
2005520395.tif 000194
個の値 pi を有するセットを選択するステップと、
値 pi の前記セットから組み立てられたバンデルモンド・ベクトル
2005520395.tif 000195
のテンソル積
2005520395.tif 000196
から空間
2005520395.tif 000197
を計算するステップと、
前記空間
2005520395.tif 000198
の垂直空間
2005520395.tif 000199
から、ベクトル
2005520395.tif 000200
とベクトル
2005520395.tif 000201
を選択するステップと、
前記ベクトル
2005520395.tif 000202
から行列
2005520395.tif 000203
を構築し、かつ前記ベクトル
2005520395.tif 000204
から行列
2005520395.tif 000205
を構築するステップと、
前記行列
2005520395.tif 000206
からのエントリを用いて多項式
2005520395.tif 000207
を構築し、かつ第一引数が前記値 p1 により固定されている前記多項式
2005520395.tif 000208
を前記第一当事者に送信するステップと、
前記行列
2005520395.tif 000209
からのエントリを用いて多項式
2005520395.tif 000210
を構築し、かつ第一引数が前記値 p2 により固定されている前記多項式
2005520395.tif 000211
を前記第二当事者に送信するステップと、
を行う請求項5の方法。
【請求項８】
値 pi の数
2005520395.tif 000212
(
2005520395.tif 000213
) 
が、追加された当事者に配布される、請求項5の方法。
【請求項９】
前記第一当事者と前記第二当事者が、前記生成された秘密 S1 と S2 の各々に非線形関数を用いた後に、この秘密を更なる通信内で秘密鍵として用いる、請求項1の方法。
【請求項１０】
一方向ハッシュ関数が、前記生成された秘密 S1 と S2 に適用される、請求項9の方法。
【請求項１１】
多項式の形態をした非線形関数が、前記生成された秘密 S1 と S2 に適用される、請求項9の方法。
【請求項１２】
前記第二当事者が前記秘密 S1 を知っていることを検証するステップを更に含む、請求項1の方法。
【請求項１３】
前記第一当事者が、ゼロ知識プロトコルを後で適用して、前記第二当事者が前記秘密 S1 を知っていることを検証する、請求項12の方法。
【請求項１４】
前記第一当事者が、コミットメントに基づいたプロトコルを後で適用して、前記第二当事者が前記秘密 S1 を知っていることを検証する、請求項12の方法。
【請求項１５】
前記第二当事者が、ランダムなチャレンジを暗号化する対称暗号を用い、かつ前記暗号化されたランダムなチャレンジを前記第一当事者に送信し、かつ、
前記第一当事者が、前記同一の対称暗号をコミット関数として後で用いて、前記暗号化されたランダムなチャレンジの復号化に自分自身をコミットさせる、
請求項14の方法。
【請求項１６】
上記請求項の何れかの方法を実行するように構成されている、第一当事者 (P) と、第二当事者 (V) と、信頼できる第三者 (TTP) とを有するシステム。
【請求項１７】
請求項16の前記システム内で、前記第一当事者として、および／または、前記第二当事者として動作するように構成されているデバイス (P)。
【請求項１８】
前記多項式 P と前記多項式 Q を、これらの各々の係数の形態で格納するための記憶手段を有する、請求項17のデバイス。
【請求項１９】
上記請求項1〜15の何れかの方法を、一つ以上のプロセッサに実行させるための、コンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、
第一当事者と第二当事者との間の共通の秘密を生成する方法であって、
前記第一当事者が、値 p1 と、第一引数が前記値 p1 により固定されている対称多項式 P(x, y) とを保持し、かつ、
前記第一当事者が、
前記第二当事者に前記値 p1 を送信するステップと、
前記第二当事者から値 p2 を受信するステップと、
多項式 P(p1, y) の p2 を求めることにより秘密 S1 を計算するステップと、
を行う方法に関する。
【０００２】
本発明は、更に、このような方法を実行するように構成されている、第一当事者と、第二者当事者と、信頼できる第三当事者とを有するシステム、このシステム内で第一当事者または第二当事者として機能するように構成されているデバイス、およびコンピュータ・プログラム製品に関する。
【背景技術】
【０００３】
第一段落による方法の一実施例は、R. Blom の「非公開鍵の配布、暗号学における進歩 (Non-public key distribution, Advances in Cryptology)」（Crypto 82の議事録、231〜236頁、1983年）から知られている。
【０００４】
認証は、デジタル通信ネットワークとコンテンツ保護システムで、重要な役割を演ずる。互いに通信するデバイスは、互いの信頼性について確信を抱いている必要がある。これらのデバイスは、信頼できない当事者に秘密情報を与えるべきではない。認証手順は、処理パワーを大量に必要とする公開鍵技術に基づいていることが多い。多くのアプリケーションでは、この（処理）パワーを利用することができないので、この場合、これらの公開鍵技術をそのまま適用することはできない。
【０００５】
時折提案される解決策は、消費パワーがかなり少ない対称暗号を用いることに基づいている。しかしながら、これらの暗号には、グローバル・システムの秘密が各デバイス内で必要となり、これは多数出回る製品には望ましくない、という欠点がある。
【０００６】
デジタル通信ネットワークは、CE 用アプリケーションでもますます一般的になりつつあるため、安価かつ低パワーの認証プロトコルの必要性が高まっている。パワーに関する制約は、一般に、携帯型 CE デバイス、スマートカードなどに該当するが、本出願の同一出願人による国際特許公開公報第 02/017316 号（社内整理番号 PHNL010233）に解説されているような「チップインディスク (CID: Chip In Disc)」タイプの製品の場合、特に厳しい。
【０００７】
CID の背景にある基本的なアプローチは、CD または DVD のようなキャリア上にチップを配置した後に、このチップをコンテンツ保護のために用いることである。このチップは、プレーヤを信用できることが確信でき次第、プレーヤがコンテンツをプレイすること（チップが持っているデスクランブル鍵へのアクセスをプレーヤに与えること）を可能にする。他方、プレーヤは、信頼できないディスク上のコンテンツは全くプレイしないであろう。したがって、プレーヤと CID の両方に、認証のための何らかの手段が必要となる。
【０００８】
留意すべき重要な点は、チップが自由に使用できるパワーが非常に限られている（約0.5 mW）ので、非常に複雑な計算を行うことができないことである。このことは、（RSA または ElGamal などの）公開鍵技術を直ちに使用することができないことを意味する。CID 認証問題は、CE の世界での認証問題の典型例である。
【０００９】
上記に参照されている Blom による論文は、2変数の対称多項式に基づいた秘密共有プロトコルを用いた共通鍵、つまり、会議鍵の生成方法を開示している。このプロトコルは、図1に示されている。基本的に、「証明者」（P と略記する）と呼ばれる一方の当事者が、「検証者」（V と略記する）と呼ばれるシステム内の別の当事者に、検証者にも知られている秘密を自分が知っているということを確信させようと試みる。検証者が確信した場合、証明者は認証される。
【００１０】
システム内で、信頼できる第三者 (TTP: Trusted Third Party) は、(n+1)×(n+1) の対称行列Tを選択する。この行列のエントリ
2005520395.tif 000003
は、2変数のn次多項式Pの各係数を表している。この多項式Pは、以下のように定義される。
2005520395.tif 000004
【００１１】
この多項式の領域内の全ての x と y に対して、
2005520395.tif 000005
であることは明らかである。例えば 
2005520395.tif 000006
のように、引数 x を特定値に固定することにより、多項式 P を1変数の n 次多項式の空間上に投射させることができる。多項式 P の定義、行列 T の対称性、およびこの結果得られる P(x, y) の対称性から、全ての p と q に対して
2005520395.tif 000007
が成り立つ。
【００１２】
Blom によると、他方のデバイスと共通の秘密を生成可能であることが必要な全てのデバイスは、対 (Pp(y), p)（つまり、多項式 P は p が固定されており、かつこの値 p は、P(x, y) から Pp(y) を生成するために用いられたものである）を受信する。デバイス (Pp, p) と (Pq, q) との間で共有される秘密は、p と q を交換することにより生成される Pp(q) = Pq(p) と、これらの多項式を評価して P の秘密 S1 と V の秘密 S2 を生じさせることにより与えられる。
【００１３】
このアプローチの場合、グローバルな秘密は、対称であるという理由により
2005520395.tif 000008
個の独立したエントリを持つ行列 T から成る。この秘密のシェア (share) は、各々の値 p と、
2005520395.tif 000009
の形態の n + 1個の係数を有する多項式 Pp(y) の形態で、全ての当事者に与えられる。
【００１４】
こうすることにより、未知数 tij が
2005520395.tif 000010
個である n + 1 個の線形方程式が全ての当事者に与えられるので、一当事者がグローバルな秘密 T を取り出すことは明らかに不可能となる。異なる一値 p を全当事者が有している n + 1 の当事者が協力した場合にしか、行列Tを取り出すことはできない。
【００１５】
このことは、この公知のプロトコルの主な欠点を示している。つまり、pi の異なる値の数が n+1 個未満でない限り、十分な数の当事者が協力すれば、グローバルな秘密 T を取り出すことが可能となってしまう。しかしながら、このことは、グローバル・システムの秘密 T を明らかにさせないようにするために、異なるシェアの数が、多項式の次数に限定されてしまうことを意味している。更に、二者の当事者が通信すると、これらの当事者が常に同じ共通の秘密を生成してしまう。
【００１６】
【特許文献１】国際特許公開公報第02/017316号
【特許文献２】国際特許出願第PCT/IB02/04803号
【特許文献３】米国特許第5,140,634号
【非特許文献１】R. Blom の「非公開鍵の配布、暗号学における進歩 (Non-public key distribution, Advances in Cryptology)」（Crypto 82の議事録、231〜236頁、1983年）
【非特許文献２】A. Menezes、P. van Oorschot、および S. van Stone による「応用暗号学の手引き (Handbook of Applied Cryptography)」(CRC Press、405〜416頁、1996年)
【発明の開示】
【課題を解決するための手段】
【００１７】
本発明の目的は、多項式 P の階数を増加させる必要なく、グローバルな秘密のより多数の異なるシェアを、当事者に配布可能にする方法を提供することである。
【００１８】
この目的は、本発明によると、第一当事者が、
値 q1 と、
第一引数が値 q1 により固定されている対称多項式 Q(x, y) と、
を更に保持し、かつ更に、
第二当事者に q1 を送信するステップと、
第二当事者から値 q2 を受信するステップと、
秘密S1を 
2005520395.tif 000011
として計算するステップと、
を行うことを特徴とする方法で達成される。
【００１９】
pi の値の数を依然として n に限定しつつ、より多数の異なるシェアを当事者に配布することができる。システム全体での qi の値の数は、Blom のシステムの場合のように多項式 P の次数により限定されることはなく、Q 領域内の可能な要素の数 qi のみにより限定される。こうすることにより、十分な数の qi によってグローバルな秘密の固有なシェアを全ての当事者に供給することが可能となる。
【００２０】
一実施例の場合、第一当事者は、
乱数 r1 を得るステップと、
2005520395.tif 000012
を計算するステップと、
第二当事者に
2005520395.tif 000013
を送信するステップと、
第二当事者から
2005520395.tif 000014
を受信するステップと、
秘密 S1 を
2005520395.tif 000015
として計算するステップと、
を更に行う。乱数 r1 と r2 は、q1 と q2 の値を隠す。このことにより、盗聴者つまり非準拠のデバイスが q1 と q2 について何かを知ってしまうことが、非常に困難となる。第二に、r1 と r2 の値は、多項式 P と Q の評価の結果、結局乗算されるので、計算された秘密S1と S2 は、乱文字も持つことになる。このことは、S1 と S2 が後で対称暗号内の鍵として用いられれば、盗聴者が暗号を破ることが困難となることを意味する。更に今度は、2つのデバイス間での全ての新たなセッションで、異なる共通の秘密を生成することが可能となる。
【００２１】
更なる一実施例の場合、第一当事者は、任意に選択された値 r により乗算された値 q1 と、個々の多項式 P(p1, y) と Q(q1, z) ではなく積 Q(q1, z)P(p1, y) を保持し、かつ第一当事者は、
2005520395.tif 000016
を計算するステップと、
第二当事者に
2005520395.tif 000017
を送信するステップと、
第二当事者から
2005520395.tif 000018
を受信するステップと、
秘密 S1 を
2005520395.tif 000019
として計算するステップと、
を行う。このようにして、値 q1 と q2 は、デバイスにアクセスしかつグローバルな秘密 T、および／または、値 q1 または q2 を知ろうと試みる敵対者には機密となる。
【００２２】
更なる一実施例の場合、第一当事者と第二当事者は、生成された秘密 S1 と S2 の各々に非線形関数を用いた後に、この秘密を更なる通信内の秘密鍵として用いる。この非線形関数は、一方向ハッシュ関数として実施されることが好ましいが、多項式の形態を取ることもできる。非線形関数を用いることにより、前後方向へのスキームが安全になる。換言すれば、攻撃者が鍵を入手したとしても、この入手された鍵から、前または後の鍵を導出することはできない。
【００２３】
第二当事者が秘密S1を知っているということを、第一当事者は後で検証することが好ましい。第一当事者は、第二当事者が秘密 S1 を知っているということを検証するために、ゼロ知識プロトコルを適用することもできる。このプロトコルは、公開値
2005520395.tif 000020
と
2005520395.tif 000021
を用いる Guillou-Quisquater プロトコルであることが好ましい。このことの利点は、本発明では
2005520395.tif 000022
の値が低い場合でも、Guillou-Quisquater プロトコルにより、敵対者はチャレンジを予期することができなくなるので、このプロトコルが非常に安全になり得ることである。更に、Guillou-Quisquater プロトコルは、通信とメモリ使用の点で効率的である。
【００２４】
これに代えて、第一当事者は、コミットメントに基づいたプロトコルを適用して、第二当事者が秘密 S1 を知っているということを検証することができる。DES、Lombok、またはAES などの対称暗号に基づいたコミットメント・プロトコルを用いることは、この方法を実行するデバイス内でのパワー消費の点で非常に効率的である。第一当事者は、同一の対称暗号を後で commit 関数として用いて、暗号化されているランダムなチャレンジの復号化に自らをコミットさせることが好ましい。こうすることにより得られる更なる利点は、チャレンジを暗号化するためのハードウエアおよび／またはソフトウエアが、コミット関数を実行するために再使用可能となるので、この実施態様の複雑さが低減されることである。
【００２５】
他の有利な実施例は、従属請求項に提示されている。
【発明を実施するための最良の形態】
【００２６】
本発明のこれらの態様と他の態様は、図面に示されている実施例から明らかとなり、かつこれらの実施例を参照することにより解明されるであろう。
【００２７】
図面全体に渡って、同じ参照番号は、同様なまたは対応する特徴を示している。図面に示されている特徴の幾つかは、通常、ソフトウエア内で実施され、かつそれ自体で、ソフトウエア・モジュールまたはオブジェクトなどのソフトウエアの実体を表している。
【００２８】
図2は、ネットワーク110を介して相互接続されているデバイス101〜105を有するシステム100を概略的に示している。この実施例の場合、システム100は家庭内ネットワークである。典型的なデジタル家庭ネットワークには、例えば、ラジオ受信器、チューナ／デコーダ、CD プレーヤ、1対のスピーカ、テレビジョン、VCR、テープデッキなどの幾つかのデバイスが含まれている。これらのデバイスは、1つのデバイス（例えばテレビジョン）が別のデバイス（例えば VCR）を制御することができるように、通常は相互接続されている。通常は、1つのデバイス（例えばチューナ／デコーダまたはセット・トップ・ボックス (STB: set top box) など）が中央のデバイスとなって、他のデバイスに対する中央制御を行う。
【００２９】
コンテンツは、通常は、音楽、歌、映画、テレビ番組、画像のようなものを含んでおり、住宅用のゲートウェイ、つまりセット・トップ・ボックス101を通して受信される。ソースは、ブロードバンド・ケーブル・ネットワーク、インターネット接続、衛星ダウンリンクなどへの接続とすることも可能である。次に、コンテンツをネットワーク110上でシンクに転送して、レンダリングさせることができる。シンクは、例えば、テレビ表示装置102、携帯型表示デバイス103、移動電話104、および／または、オーディオ再生デバイス105とすることもできる。
【００３０】
コンテンツ品目をレンダリングさせる適格な方法は、デバイスのタイプとコンテンツのタイプに依存する。例えば、ラジオ受信器の場合、レンダリングには、オーディオ信号を生成することと、これらの信号をラウド・スピーカにフィードすることが含まれる。テレビ受信器の場合、レンダリングには通常、オーディオ信号とビデオ信号を生成することと、これらの信号を表示画面とラウド・スピーカにフィードすることが含まれる。他のタイプのコンテンツに対しても、同様の適切な処置を行わなければならない。レンダリングには、受信された信号の復号化つまりデスクランブリング、オーディオ信号とビデオ信号との同期化などの動作を含めてもよい。
【００３１】
システム100内のセット・トップ・ボックス101、または他の何れかのデバイスは、受信されたコンテンツを記録し、かつ後で再生することを可能にする、適切な大きさのハードディスクなどの格納媒体S1を有してもよい。格納装置S1は、セット・トップ・ボックス101が接続されている、ある種類のパーソナル・デジタル・レコーダ (PDR: Personal Digital Recorder)（例えばDVD+RWレコーダ）とすることができる。CD (Compact Disc) またはDVD（Digital Versatile Disc）などのキャリア120上に格納されているシステム100に、コンテンツを設けることもできる。
【００３２】
携帯型表示デバイス103と移動電話104は、例えば Bluetooth（登録商標） または IEEE 802.11b を用いている基地局111を使用して、ネットワーク110にワイヤレス接続される。他のデバイスは、従来の結線接続を用いて接続される。デバイス101〜105の相互作用を可能にさせるには、相互運用性に関する幾つかの規格を利用することができる。これらの規格によって、異なるデバイスがメッセージと情報を交換し、かつ互いに制御し合うことが可能となる。周知の規格の1つとして、ホーム・オーディオ・ビデオ相互運用性 (HAVi: Home Audio/Video Interoperability) 規格バージョン1.0が挙げられる。これは、2000年1月に公布され、かつインターネット上のアドレス http://www.havi.org/ から入手可能である。他の周知の規格として、（D2B: domestic digital bus）規格、IEC 1030に解説されている通信プロトコル、およびユニバーサル・プラグ・アンド・プレイ（http://www.upnp.org）が挙げられる。
【００３３】
多くの場合に重要な点は、家庭ネットワーク内のデバイス101〜105が、コンテンツのコピーを無権限で作らないようにさせることである。こうするには、デジタル著作権管理 (DRM: Digital Rights Management) システムと通常呼ばれているセキュリティ・フレームワークが必要である。
【００３４】
このようなフレームワークの1つの場合、家庭ネットワークは、概念的に、条件付きアクセス（CA: conditional access）領域とコピー保護（CP: copy protection）領域とに分割される。通常、シンクは CP 領域内に配置される。こうすることにより、コンテンツがシンクに提供された場合に、このコピー保護スキームが CP 領域内に配置されているので、コンテンツのコピーを無権限で作ることが不可能となる。CP 領域内のデバイスは、一時的なコピーを作る格納媒体を有してもよいが、このようなコピーは、CP 領域からエクスポートしてはならない。このフレームワークは、本出願と同一の出願人による国際特許出願第 PCT/IB02/04803号（社内管理番号 PHNL010880）に説明されている。
【００３５】
セキュリティ・フレームワークを実施する家庭内ネットワーク内の全てのデバイスは、選択された特定のアプローチとは無関係に、実施要件にしたがってセキュリティ・フレームワークを実施する。これらのデバイスは、このフレームワークを用いて互いに認証を行い、かつコンテンツを安全に配布することができる。コンテンツへのアクセスは、セキュリティ・システムにより管理される。このことにより、保護されていないコンテンツが無権限のデバイスに漏れてしまうことがなくなり、かつ信頼できないデバイスから生じたデータがシステムに入ってしまうことがなくなる。
【００３６】
デバイスはコンテンツの配布を、デバイスが予め認証に成功している他のデバイスにしか行わないことが重要である。こうすることによって、敵対者が不当なデバイスを使用してコピーを無権限に作ってしまうことが不可能になる。デバイスがそれ自身の認証に成功することができるのは、権限を与えられた製造業者によりデバイスが組み立てられており、例えば、認証に成功するために必要な特定の秘密を、権限を与えられた製造業者しか知らないか、またはこれらの製造業者のデバイスに、信頼できる第三者により発行された認定が与えられている場合のみである。
【００３７】
秘密の共有
何れの認証スキームでも、何らかのグローバルな秘密、つまり、共通情報が存在していなければならない。また、別の当事者に自らを認証させることを望んでいるいかなる当事者も、この他の当事者と共通の何らかの情報を、少なくとも持っていなくてはならない。グローバルな秘密を全てのデバイスに与えることは、理論的には可能だが、実際には薦められない。なぜならば、（例えば1つのデバイスがハッキングされることによって）グローバルな秘密が知られてしまった場合、信頼できる当事者にグローバルな秘密を最初に配布した信頼できる第三者 (TTP: Trusted Third Party) の役割を、敵対者が支配してしまうことがあり得るからである。こうして、非準拠のデバイスがシステムに入ってしまい、かつ初期システムの安全性が損なわれ、認証が無駄になってしまう。グローバルな秘密が完全に知られてしまっているので、非準拠のデバイスを検出することが不可能となってしまうであろう。
【００３８】
このことを解決する可能な方法は、秘密の共有 (secret sharing) である。つまり、信頼できる全ての当事者が、グローバルな秘密のシェアを1つ入手するのである。このシェアにより、信頼できる当事者は他の当事者に自らを十分に認証させることができるが、（こうすることが仮にも可能な場合に）グローバルな秘密を再構築させるためには、多数のシェアが必要となる。1つのデバイスが損なわれてしまった場合、グローバルな秘密のシェアは1つしか知られることがないので、このデバイスを無効にさせるための手段を講じることができる。
【００３９】
本発明は、当事者が共通の秘密を決定することを可能にする秘密共有プロトコルを用いる。その後、当事者は通常、他の当事者が秘密を知っているということを検証するであろう（以下のセクション「秘密の検証」を参照されたい）。しかしながら、当事者は、明示的に照合を行うことなく、先へ進んでもよい。例えば、秘密を暗号化鍵として用いて、他の当事者に送信される何らかの情報を暗号化することができる。他の当事者は、同じ秘密を持っていなければ、情報を復号化することはできない。この秘密は、他の当事者に暗示的に権限を与えるのである。
【００４０】
図3は、証明者 P と、検証者 V と、信頼できる第三者 TTP とを有する、図2のシステムを一般化したものを概略的に示している。本発明によると、検証者Vは、信頼できる第三者 TTP から受信された情報を用いて、証明者 P を認証することを望む。この認証は、検証者 V が信頼に足るものであることが証明者 P にも分かるように、相互に行われることが好ましい。
【００４１】
検証者 V を証明者 P に認証させるために必要な情報は、TTP から当事者 P と V に予め配布されていることが想定されている。この配布は、当事者 P と V と、TTP との間の通信チャネル上で行うことができる。こうすることによりプロトコルは動的になり、かつ予め配布された秘密に対する無権限のアクセスを敵対者が得てしまった場合に、情報を容易に更新することが可能となる。
【００４２】
証明者 P と検証者 V を、必要な機能性を提供するチップが備えられているキャリア120のようなデバイスと、オーディオ再生デバイス105とすることができる。このような場合、TTP から証明者と検証者への通信チャネルは、おそらく存在しないことがほとんどであろう。したがって、秘密の配布は、例えば、キャリア120またはデバイス105が製造されている工場内で、予め行われなければならない。
【００４３】
証明者 P は、ネットワーク・モジュール301、暗号プロセッサ302、および格納媒体303を有する。証明者 P は、ネットワーク・モジュール301を用いて、検証者 V とのデータの送受信を行うことができる。ネットワーク・モジュール301は、ネットワーク110に接続したり、または検証者Vとの直接接続（例えばワイヤレス・チャネル）を確立することができる。
【００４４】
暗号プロセッサ302は、本発明による方法を実行するように構成されている。このプロセッサ302は、通常はハードウエアとソフトウエアの組み合わせとして実現されるが、ハードウエアまたはソフトウエアの内部で、例えば、ソフトウエア・モジュールまたはオブジェクトの集まりとして完全に実現させることもできる。
【００４５】
証明者 P は、例えば、多項式 P と Q の係数を格納媒体303内に格納することができるが、認証が成功した後に検証者Vに配布したい幾つかのコンテンツを保持させるために、格納媒体303を使用してもよい。更に、TTP から受信された情報を格納させるために、格納媒体303を使用してもよい。システムのセキュリティを高めるためには、個々の多項式 P と Q を格納するのではなく、積 Qq(z)Pp(y) を代わりに格納すべきである。
【００４６】
同様に、検証者Vは、ネットワーク・モジュール311と、暗号プロセッサ312と、証明者 P の格納装置に対応した機能性を有する格納装置313とを有している。検証者 V が、チップインディスクを有するキャリア120として具現化される場合、格納装置313は、何れの（光）ディスクでも利用可能な格納装置に対応してもよいが、チップインディスク上の ROM 内に格納させることが好ましい。
【００４７】
さらに、証明者 P と検証者 V には、暗号的に強い疑似乱数を提供する、（ハードウエアおよび／またはソフトウエア内の）擬似乱数生成器304、314を設けてもよい。これらの疑似乱数は、本発明による方法の好ましい実施例で用いられる。次に、証明者 P を検証者 V に認証させる幾つかの実施例を、図4と図5を参照しながら説明する。
【００４８】
2つの対称多項式を用いて共通の秘密を生成する
図4は、本発明の好ましい一実施例による、各々2変数の2つの対称多項式に基づいた秘密共有プロトコルを示している。当事者により行われる設定とステップの部分は、図1を参照して既に説明済みなので、ここでは繰り返さない。
【００４９】
対称多項式 P は、対称多項式 Q(x, z)（例えば、
2005520395.tif 000023
）により乗算される。多項式 P の pi を固定させることに加えて、今度は同様に多項式 Q も qi を固定させる。次に証明者は、p1 が固定されている多項式 P ではなく、還元された多項式の積、
2005520395.tif 000024
および値 p1 と q1 を、TTP から受信する。同様に、検証者は、p2 が固定されている多項式Pではなく、還元された多項式の積、
2005520395.tif 000025
および値 p2 と q2 を受信する。証明者と検証者は、これらの多項式を、これらの係数の形態、
2005520395.tif 000026
で格納することが好ましい。
【００５０】
値 q1 と q2 は、最初に TTP によって、乱因子
2005520395.tif 000027
により乗算されることが好ましい。こうして、証明者および／または検証者を具現化しているデバイスに対する無権限のアクセスを得てしまう可能性がある敵対者に対して、値 q1 と q2 が機密になるので、敵対者が権限のあるデバイスとして通用してしまうことがなくなる。
【００５１】
上記の内容から、下式が成り立つ。
2005520395.tif 000028
この式は、実際の値 q を隠すためにブラインド化因子
2005520395.tif 000029
が用いられている場合でも、証明者と検証者は、これらが持っている要素 pi と qi、および証明者と検証者が他の当事者から受信した要素 pi と qi を用いて、共通の秘密を多項式 P と Q の積として生成できるということを示している。
【００５２】
ここで、pi の値の数を n 以下に限定してしまうと、多項式 P と Q の係数を取り出すことができなくなってしまう。システム全体での qi の値の数は、Blom のシステムの場合と同様、多項式 P の次数により限定されてしまうことはなく、Q の領域内の可能な要素 qi によって限定されるだけである。こうすることにより、十分な数の値 qi によってグローバルな秘密の独自のシェア、全ての当事者に供給することが可能となる。
【００５３】
当事者 P と V は、多項式 P と Q との積、および値 pi と qi (または
2005520395.tif 000030
)
を受信すると、図4に示されているように、共通の秘密の生成を試みる。両方の当事者は、それらの pi と qi（または
2005520395.tif 000031
）の値を交換し、かつそれらの各々の秘密 S1 と S2 を算出する。当事者 P と V は、各々の乱数 r1 と r2 を最初に生成することが好ましい。次に、当事者 P と V は、
2005520395.tif 000032
と
2005520395.tif 000033
を各々算出し、かつ値 q1 と q2 自体ではなく、
2005520395.tif 000034
と
2005520395.tif 000035
の積を交換する。こうすることには幾つかの利点がある。これらの利点の内、乱数 r1 と r2 が q1 と q2 の値を隠すことによって、盗聴者または非準拠のデバイスが、q1とq2に関して何かを知ってしまうことが非常に困難となる、という事実が挙げられる。さらに、当事者の一方（例えば、証明者 P）が、その秘密 S1 を、
2005520395.tif 000036
として計算することが可能になる。
【００５４】
本システムの更なる改良点は、両当事者が、計算された秘密 S1 と S2 に非線形関数を適用した後に、この秘密を秘密鍵として用いることにより、達成することができる。この非線形関数は、一方向ハッシュ関数として実施することが好ましいが、多項式の形態を取ることもできる。
【００５５】
限定された対称多項式を用いて共通の秘密を生成する
図5は、多項式 P が限られた数の点でしか対称でない、図4のプロトコルに基づいた変種を示している。多項式 P は、対称行列 T に基づいていており、かつ多項式 P(x, y) が、P の領域内の全ての x と y の値に対して対称であることを示すことができる。しかしながら、n 個を超える異なる値 pi が用いられる場合、敵対者が行列 T を再構築することが理論的には可能となる。したがって、多項式 P は、
2005520395.tif 000037
個の値 p1, …, pm (
2005520395.tif 000038
) でしか対称とならない必要がある。限られた数の点でしか対称でない多項式を組み立てる方法を説明するために、最初に幾つかの定義を提示する。
【００５６】
2つの n 次ベクトル
2005520395.tif 000039
と
2005520395.tif 000040
の内積は、
2005520395.tif 000041
により与えられる。
2005520395.tif 000042
と
2005520395.tif 000043
とのテンソル積
2005520395.tif 000044
は、
2005520395.tif 000045
により与えられる。
【００５７】
長さがn+1のバンデルモンド・ベクトル
2005520395.tif 000046
は、
2005520395.tif 000047
により与えられる p に関連付けられる。特に明言しない限り、全てのバンデルモンド・ベクトルは、長さが n + 1 である。また、表記を容易にするために、下付きの n は省略する。
2005520395.tif 000048
である別個の値のサブセット {p1, …, pm} が与えられると、バンデルモンド・ベクトル 
2005520395.tif 000049
が形成される。これらの
2005520395.tif 000050
個のベクトルは、線形独立である。したがって、これらのベクトルは、サブ空間
2005520395.tif 000051
の基底ベクトルである。
【００５８】
次に、
2005520395.tif 000052
に対する可能な全てのテンソル積
2005520395.tif 000053
を考える。テンソル算法からは、これらの
2005520395.tif 000054
個のテンソル積がテンソル空間
2005520395.tif 000055
の基底を形成することが知られている。全てのベクトル
2005520395.tif 000056
に対して、下式が成り立つ。
2005520395.tif 000057
【００５９】
上記の定義を用いて多項式 P(x, y) を内積として書き直すと、下式が得られる。
2005520395.tif 000058
式中、
2005520395.tif 000059
は、ベクトル (t00, …, t0n, t10, …, tnn) を表している。すなわち、
2005520395.tif 000060
は、行列 T のエントリを含んでいる。P は、その書き直された形態でも対称のままである。
【００６０】
次に、
2005520395.tif 000061
個の別個要素 p1, …, pm を選択する。これらの要素を用いてバンデルモンド・ベクトル
2005520395.tif 000062
を組み立て、かつこれらのバンデルモンド・ベクトルから、テンソル積
2005520395.tif 000063
を組み立てる。次に、上述したように空間
2005520395.tif 000064
の垂直空間
2005520395.tif 000065
からベクトル
2005520395.tif 000066
を選択する。次に、多項式 P の書き直された形態は、好ましいセット {p1, …, pm} から選択された点で評価することができる。ベクトル
2005520395.tif 000067
はベクトル
2005520395.tif 000068
に加算可能であり、かつ
2005520395.tif 000069
であることから、下式が得られる。
2005520395.tif 000070
【００６１】
換言すれば、ベクトル
2005520395.tif 000071
から、行列、
2005520395.tif 000072
を導出し、かつこの行列
2005520395.tif 000073
を行列 T に加算した場合、好ましいセット内の全ての pi と pj には、依然として P(pi, pj) = P(pj, pi) が成り立つ。
【００６２】
TTP は上記の所見を用いて、以下の動作を行うことによりシステムを設定する。
1. TTP は、(n+1)×(n+1) の対称行列 T をランダムに選択し、かつ任意値
2005520395.tif 000074
を選択することが好ましい。
2. TTP は、
2005520395.tif 000075
個の別個の要素 p1, …, pm (
2005520395.tif 000076
) をランダムに選択する。
3. TTP は、テンソル積
2005520395.tif 000077
から、空間
2005520395.tif 000078
を計算する。
4. TTP は、
2005520395.tif 000079
個の要素 p1, …, pm から、最初の
2005520395.tif 000080
個の要素を選択することが好ましい。こうして、システムの更新が可能となる（以下のセクション「更新可能性」で説明する）。
【００６３】
TTP は、次にデバイスを発行することができる。つまり、TTP が、グローバルな秘密のシェアをデバイスに提供すると、これらのデバイスは、グローバルな秘密のシェアを有する他のデバイスに自らを（相互に）認証させることができるようになる。このようなデバイスは、多くの場合、認定されたデバイス、または権限のあるデバイスと呼ばれる。認定済みのデバイスは、他の認定済みのデバイスとの相互認証に次いで、無権限のデバイスを検出することができる。この検出は通常、このデバイスの認証が失敗することによって行うことができる。
【００６４】
デバイスを発行するために、TTP は以下のステップを行う。
1. TTP は、デバイス
2005520395.tif 000081
に対して、
2005520395.tif 000082
をランダムに選択し、かつ
2005520395.tif 000083
個の要素 p1, …, pm を有するセットから、好ましくは
2005520395.tif 000084
個の要素を有する選択されたサブセットから、pi をランダムに選択する。
2. TTP は、
2005520395.tif 000085
から行列
2005520395.tif 000086
を生成し、かつ行列
2005520395.tif 000087
を形成する
3. TTP は、
2005520395.tif 000088
から2変数の多項式 P(x, y) を組み立て、かつ
2005520395.tif 000089
と表現することができる一変数の多項式 P(pi, y) の係数を計算する。
4. TTP は、値pi,
2005520395.tif 000090
とベクトル
2005520395.tif 000091
を、デバイス
2005520395.tif 000092
に配布する。
【００６５】
当事者 P と V は、これらの各々の情報を受信すると、図5に示されているように、次はそれらの値 pi と
2005520395.tif 000093
を交換し、かつ P と V の各々の秘密 S1 と S2 を下式のように生成する。
2005520395.tif 000094
【００６６】
S1=S2 であれば、これらの当事者は共通の秘密を生成済みである。これらの当事者は、他の当事者も秘密を知っているということを暗示的に結論付けるか、または他の当事者が同じ秘密を知っているということを明示的に検証することができる。この点に関しては、下記の「秘密の検証」で説明する。
【００６７】
更新可能性
更新可能性は、システム100のようなシステム向けの、いかなる認証スキームまたはいかなる共通鍵生成スキームの重要な側面である。TTP は、元の秘密への無権限のアクセスを得てしまった敵を撃退するために、デバイス101〜105内に組み込まれている秘密を周期的に交換させることを望む場合がある。
【００６８】
図5に示されている実施例を用いて、前のセクションで説明した属性を利用することにより、システム100に更新可能性を導入することができる。最初に、TTPは、
2005520395.tif 000095
(
2005520395.tif 000096
) が空間
2005520395.tif 000097
に広がるように、要素 p1, …, pm (
2005520395.tif 000098
) のみを用いてデバイスを発行する。しかしながら、行列
2005520395.tif 000099
は、
2005520395.tif 000100
から導出された
2005520395.tif 000101
を用いる。デバイス
2005520395.tif 000102
内に格納されている多項式を
2005520395.tif 000103
と表した場合、このデバイスには対
2005520395.tif 000104
が含まれる。
【００６９】
ここで、敵が
2005520395.tif 000105
個の要素 pi と、更に何らかのデバイス多項式
2005520395.tif 000106
とを、例えば、デバイスを破り開けることによって、どうにか取り出すことができたと想定する。これで敵は、新たなベクトル
2005520395.tif 000107
を生成し、かつ
2005520395.tif 000108
を含むデバイスを発行することが可能となった。これらのデバイスは、値 p1, …, pm の内の1つを含む準拠する全てのデバイスと協働してしまうであろう。すなわち、敵のデバイスは、準拠デバイスから
2005520395.tif 000109
を受信し、かつ、
2005520395.tif 000110
と評価し、かつ第二当事者は、
2005520395.tif 000111
と評価する。この式は、両方の評価が等しいことを示している。
【００７０】
これらのようなデバイスが敵により発行されているということに TTP が気づいた場合、TTPは、
2005520395.tif 000112
のテンソル積が空間
2005520395.tif 000113
に広がるように、
2005520395.tif 000114
(
2005520395.tif 000115
) 
を用いてデバイスを発行し始めることができる。
2005520395.tif 000116
であることに留意されたい。したがって、敵が
2005520395.tif 000117
と選択してしまっている場合、これらの新たなデバイスは、敵のデバイスと協働してしまうであろう。
2005520395.tif 000118
が
2005520395.tif 000119
内でランダムに選択されていれば、
2005520395.tif 000120
が
2005520395.tif 000121
内にも存在してしまう確率は非常に僅かとなる。
【００７１】
このことによって、システムには、ある程度の更新可能性が与えられる。つまり、TTP により発行された新たな準拠デバイスが敵のデバイスと協働しない確率は、非常に高くなる。システムを更新させることができる最大回数は、
2005520395.tif 000122
（nは多項式Pの次数）である。この回数は、更新毎に、
2005520395.tif 000123
の値が１つ加算されると、発生する。
【００７２】
秘密の検証
当事者の各々が秘密を独立して生成した後、プロトコルの次のステップは、他の当事者が秘密を知っているということを検証することである。当事者の内の一者は、自分が秘密を知っていることを他の当事者に証明可能であれば、他の当事者に認証される。更に、他の当事者が同様に自らを第一当事者に認証させて、相互認証を達成してもよい。
【００７３】
検証者は、証明者が秘密を知っているということを検証したら、次に秘密 S1 を用いて、何らかの情報を証明者に安全に通信させることができる。例えば、暗号化されているコンテンツにアクセスするために必要な暗号化鍵を、S1 により暗号化することができる。この暗号化の結果は、証明者に伝送可能である。今度は証明者が、S2（これが S1 に等しいということは、検証が成功したことにより証明済みである）を用いてこの暗号化鍵を回復させ、次いで暗号化されているコンテンツを復号化させ、かつこのコンテンツにアクセスすることができる。
【００７４】
上記のように生成された秘密を一当事者が知っているということを検証する方法は、幾つかある。好ましい2つの実施例は、ゼロ知識プロトコルとコミットメントに基づいたプロトコルとに基づいている。
【００７５】
ゼロ知識に基づいた検証
最初に、ゼロ知識（ZK: zero-knowledge）プロトコルに基づいた検証について説明する。ZKプロトコルは、A. Menezes、P. van Oorschot、および S. van Stone による、「応用暗号学の手引き (Handbook of Applied Cryptography)」(CRC Press、405〜416頁、1996年)で論じられている。好ましい一実施例では、メモリ要件と通信の点で効率的であるという理由から、(GQ: Guillou-Quisquater) ゼロ知識プロトコルが用いられている。GQ プロトコルは、本出願と同一の代理人による、米国特許第 140,634 号（社内整理番号 PHQ 87030）から知られている。
【００７６】
図4と図5を参照して上述したように、当事者 P と V の両者は、それらの多項式を評価し、かつこうして値 S1 と S2 を各々得ている。次に、何れかの当事者は、自分が S1 を知っているということを、他方の当事者にZKで証明しなければならない。GQ プロトコルは公開鍵暗号法に基づいているので、2つの素数 p と q の積である合成数 
2005520395.tif 000124
、および
2005520395.tif 000125
となるような数
2005520395.tif 000126
が必要である。
【００７７】
Pは、
2005520395.tif 000127
の
2005520395.tif 000128
乗根を知っているということを V に証明する。図6には、GQ プロトコルが示されている。ここで、値
2005520395.tif 000129
と
2005520395.tif 000130
は公開されている。このプロトコルは、以下のステップにしたがって進行する。
1. V が、
2005520395.tif 000131
を計算するステップ。
2. P が、乱数
2005520395.tif 000132
を選択し、かつ re を V に送信するステップ。
3. V が、ランダムなチャレンジ
2005520395.tif 000133
を選択し、かつ c を P に送信するステップ。
4. P が、
2005520395.tif 000134
によって応答するステップ。
5. V が、ye を算出し、かつ、
2005520395.tif 000135
である場合のみ、（この式が S1=S2 であることを示しているので）P は V と同じ秘密を知っていると結論付けるステップ。
【００７８】
GQ プロトコルの ZK 属性のため、V も盗聴者も、P の秘密 S1 に関する何かを知ることはない。P が V により承認されると直ちに、P と V の役割は入れ替わり、かつ V は、
2005520395.tif 000136
の
2005520395.tif 000137
乗根を知っているということを、P に示すであろう。このようにして、P と V は相互認証される。
【００７９】
このプロトコルの設定は、上述文献の記述内容とは多少異なる。すなわち、通常は、
2005520395.tif 000138
が公表され、かつ P がチャレンジ
2005520395.tif 000139
を予期した場合、P は第一メッセージとして
2005520395.tif 000140
を送信し、かつ S2 を知らなくても、依然として、V による承認を受けることができる。適切なチャレンジを選択する確率は、e-1 である。現在の設定では、
2005520395.tif 000141
を公表する必要はない。このことによって、予期されたチャレンジから P が
2005520395.tif 000142
を計算することは不可能となり、かつこのことによって、不当な承認が行われてしまう確率が
2005520395.tif 000143
に低減される。したがって、
2005520395.tif 000144
を 2 程度の低さに選択して、エラー確率は
2005520395.tif 000145
のまま GQ を Fiat-Shamir プロトコルに有効に変換することが、1ラウンドで可能となる。このことは、デバイスがモジュラ指数化を、例えば RSA とは対照的に、小さな指数で行えばよいことを意味する。
【００８０】
これをより効率的なものにさせるには、Montgomery の表現法を用いた実施態様を考えてもよい（P.L.Montgomeryの「試行除算を用いないモジュラ乗算 (Modular multiplication without trial division)」（Mathematics of Computation, 第44巻、第170番、519〜521頁、1985年4月）を参照されたい)。
【００８１】
コミットメントに基づいた検証
ZK プロトコルに代えて、コミットメントに基づいたプロトコルを用いて、一方の当事者は、他の当事者が秘密を知っているということを検証することができる。このアプローチの利点の1つは、非常に効率的に実施可能な対称鍵暗号法が利用可能であることである。
【００８２】
前の状況とは対照的に、当事者 P と V の両方が検証者と証明者の役割を同時に果たすので、このことによりプロトコルの通信が効率的になる。前記のように、 P は S1 を算出し、かつ V は S2 を算出する。このプロトコル（図7を参照されたい）は、以下のステップを行う。
1. V が、対称暗号のブロック長にマッチングした長さの乱数
2005520395.tif 000146
を選択するステップ。
2. V が、S2 を鍵とした対称暗号を用いて
2005520395.tif 000147
を暗号化し、かつこの暗号化されたもの ES2(r) を P に送信するステップ。
3. Pが、このメッセージを S1 を用いて復号化し、
2005520395.tif 000148
を得るステップ。
4. P が、乱数
2005520395.tif 000149
を選択し、かつ
2005520395.tif 000150
へのコミットメントを V に送信するステップ。このコミットメントは、以下に説明する関数
2005520395.tif 000151
として得られる。
5. Vが、
2005520395.tif 000152
を P に送信し、かつ P が、
2005520395.tif 000153
であるか否かを照合し、
2005520395.tif 000154
でない場合は、V との更なる通信を停止させるステップ。
6. P が、
2005520395.tif 000155
と
2005520395.tif 000156
を V に送信するステップ。V は、このコミットメントを開き、かつ
2005520395.tif 000157
であるか否かを照合し、かつこの照合が満たされない場合は、P との更なる通信を停止させる。
【００８３】
2005520395.tif 000158
関数は、コミットメントの結合属性と隠れ属性を実施する必要がある。結合とは、コミットメント内の値
2005520395.tif 000159
を変える、P の能力のことである。
2005520395.tif 000160
となるような値
2005520395.tif 000161
を P が見つけることは、困難または不可能でなければならない。隠れ属性とは、
2005520395.tif 000162
の受信後に
2005520395.tif 000163
に関する情報を得る、Vの能力のことである。実際には、暗号ハッシュ関数つまり一方向関数が
2005520395.tif 000164
関数として用いられることが多い。
【００８４】
この設定では、
2005520395.tif 000165
を暗号化するために用いられる対称暗号は、
2005520395.tif 000166
関数として用いることもできる。隠れ属性が満たされることは自明である。なぜならば、V は、ランダムに選択された R に関する知識がなければ、V の算出パワー量とは無関係に、
2005520395.tif 000167
に関する情報を得ることはできないからである。したがって、コミットメントは、無条件に隠れている。対称暗号の場合には、EK(x) = z は K の一方向関数（xとzは既知）であることが知られており、つまり、
2005520395.tif 000168
と
2005520395.tif 000169
が与えられても、
2005520395.tif 000170
となるような値
2005520395.tif 000171
を、255 回未満の演算で見つけ出す方法は分からない、という事実から、結合属性は成り立っている。したがって、コミットメントは、算出を行うことにより結合される。
【００８５】
次に、プロトコルの完全性と安定性について考える。完全性とは、両当事者が、プロトコルを正確に実行し、かつ
2005520395.tif 000172
である場合のことである。したがって、両当事者は、対称暗号の精査と対称属性とにより、
2005520395.tif 000173
のときは
2005520395.tif 000174
であることを見出すであろう。
【００８６】
安定性とは、P が S1 を知らないか、または V が S2 を知らない場合に、相互に承認してしまう状況に関する。P は、承認を不当に受けるために、V へのコミットメントとしてどのような値 z でも送信することができる。P は、V から
2005520395.tif 000175
を受信した後、
2005520395.tif 000176
となるような値
2005520395.tif 000177
を見つけなければならない。上述したように、
2005520395.tif 000178
は、
2005520395.tif 000179
を見つけ出すことを困難な問題にさせる、与えられた x と z に対する K の一方向関数である。
【００８７】
同様に、V は、S2 を知らない場合、P に対してどのような値 z でも選択することができる。P は、ER(DS2(z)) によって応答するであろう。V は、承認されるためには、DS2(z) を得なければならない。このことは、コミットメントがランダムな値
2005520395.tif 000180
によって無条件に隠れているので、非常に困難である。偶然に S1 が弱い DES 暗号化鍵である場合、V は、DS1(z) = z となるような z を選択すれば、承認されてしまうであろう。弱い鍵の場合、このような定点は 232 個あり、かつ P により不当に承認されてしまう確率は、232/264 = 2-32 である。
【００８８】
本発明の幾つかの利点
本発明の方法により、本発明が実行されるデバイス内で必要なエネルギー（パワー）を相当節約すること、および RSA に基づいた認証と比較して処理時間を実質的に節約することが達成される。
【００８９】
一般に、パワー消費は、実施態様のアーキテクチャに依存する。例えば、このアーキテクチャを変化させて、クロック・スピードとパワー消費をトレードすることができる。第二の重要な要因は、用いられる技術である。つまり、最小特徴サイズが小さく、かつ供給電圧が低い最新技術は、一般に、古い技術よりも余りパワーを必要としないであろう。
【００９０】
以下の表は、各プロトコルの異なる部分に必要な作用力の推定値を、n（多項式の次数）、k（値のビット長）、l（GQ モジュラスのビット長）、および h（RSA モジュラスのビット長）で記したものである。この推定された作用力は、単精度乗算（つまり、2ビットの乗算を、2つの k ビットの数を乗算させることで行うこと）で表現されている。
2005520395.tif 000181
【００９１】
以下の表は、n、k、l、およびhの幾つかの値の場合ごとにサブプロトコルが必要とするエネルギーの推定値（ジュール）、および0.5 mWのパワーを利用できるチップインディスク・アプリケーションに本発明が用いられた場合の処理時間量を示している。
2005520395.tif 000182
【００９２】
上記の値は、単精度乗算毎に必要となるエネルギーの推定値に基づいていることに留意すべきである。実エネルギーは、選択されたアーキテクチャ、レイアウト、設計プロセスでの最適化目標（例えば、パワーまたはスピード）などに依存する。それでもやはり、上記の表内のデータは、異なるプロトコルに必要なエネルギー比に対する見識を与えてくれる。最後の列では、次数が2048の多項式と、64ビットの値の場合でさえ、新たなプロトコルの方がRSAよりも30〜100倍効率的であることが分かる。
【００９３】
最大 0.5 mW のパワーが利用可能な CID の特殊な場合、RSA プロトコルには約1秒必要だが、対称多項式に基づいたプロトコルには、多くても 52 ms だけ必要となることが導き出せる。
【００９４】
上述の実施例は、本発明を限定しているのではなく例示しているのであり、かつ当業者は、添付の請求の範囲の範囲内で、代替実施例を多数設計できることに留意すべきである。上記では、コンテンツ保護とデジタル権利管理との関連で認証方法が詳述されているが、本発明は、勿論、この関連事項には制限されない。
【００９５】
本発明は、特に、パワー消費量が低いことが重要な場合に、コンポーネントおよび／またはデバイスのいかなる対の間でのインタフェースで認証を行うためのユニバーサルな組み立てブロックとして考えることができる。したがって、本発明は、例えば、CD2内、セット・トップ・ボックス内、ワイヤレス・スマートカード内、有線ネットワークまたはワイヤレス・ネットワークなどにも適用可能である。本発明は、人間である検証者が人間である証明者を、各々に相互接続された2つのデバイスを用いて認証する必要がある場合にも有効である。
【００９６】
上記で、「乱数」または「任意に選択された数」という用語が用いられている場合、これには、真にランダムなイベントから導出されたシード値を用いてまたは用いずに、ハードウエアおよび／またはソフトウエア内で実施される擬似乱数生成器を使用して選択された数が含まれていることが明らかとなるであろう。本方法のセキュリティは、擬似乱数生成器の品質に依存するところが大きい。
【００９７】
請求項では、括弧間に配置されている何れの引用符号も、請求項を限定するものと解釈してはならない。「有する」という語は、請求項に列挙されているもの以外の要素またはステップの存在を除外するものではない。ある要素の前にある語「1つの」という語は、そのような要素が複数存在することを除外するものではない。本発明は、幾つかの個別要素を有するハードウエアと、最適にプログラムされたコンピュータとにより実施可能である。
【００９８】
幾つかの手段を列挙しているデバイス請求項では、これらの手段の幾つかを、全く同一ハードウエア品目により具現化させることができる。特定の手段が相互に異なる従属クレーム内に詳述されているという単なる事実は、これらの手段の組み合わせを有利に用いることができないことを示している訳ではない。
【図面の簡単な説明】
【００９９】
【図１】Blom による2変数の対称多項式に基づいた秘密共有プロトコルを示す。
【図２】本発明にしたがって動作するように構成されている、ネットワークを介して相互接続されているデバイスを有するシステムを、概略的に示す。
【図３】証明者、検証者、および信頼できる第三者を有する、図2のシステムを一般化したものを概略的に示す。
【図４】各々2変数の2つの対称多項式に基づいた、証明者と検証者との間の秘密共有プロトコルを示す。
【図５】2つの多項式が限られた数の点でしか対称でない、図4のプロトコルに基づいた変種を示す。
【図６】Guillou-Quisquater プロトコルを示す。
【図７】コミットメントに基づいたプロトコルを示す。
【符号の説明】
【０１００】
100…家庭ネットワーク
101…セット・トップ・ボックス
102…テレビ表示装置
103…携帯型表示デバイス
104…移動電話
105…オーディオ再生デバイス
110…ネットワーク
111…基地局
120…キャリア
301…ネットワーク・モジュール
302…暗号プロセッサ
303…格納媒体
304…擬似乱数生成器
311…ネットワーク・モジュール
312…暗号プロセッサ
313…格納装置
314…擬似乱数生成器
【図１】
2005520395.tif 000214
【図２】
2005520395.tif 000215
【図３】
2005520395.tif 000216
【図４】
2005520395.tif 000217
【図５】
2005520395.tif 000218
【図６】
2005520395.tif 000219
【図７】
2005520395.tif 000220
【国際調査報告】
2005520395.tif 000221