(57)【要約】第１のユーザ設備と第２のユーザ設備との間で共通の秘密データアイテムを生成する方法は、各ユーザ設備が、少なくとも部分的に秘密であるそれぞれ固有の量に基づくそれぞれ相補的なデータで相互に対称的な演算を実行することにより行われる。演算の結果は、前記共通の秘密データアイテムとして前記ユーザ設備の双方で使用される。特に、その方法は、Abelian  Varietyに定められるGAP  Diffie-Hellmann問題に属する前記相補的なデータを定めることに基づく。更に、Abelian  Varietyは、楕円曲線を通じた１次元を有する
2006500814.tif 000002
【特許請求の範囲】
【請求項１】
各ユーザ設備により、少なくとも部分的に秘密であるそれぞれ固有の量に基づくそれぞれ相補的なデータで相互に対称的な演算を実行することを通じて、第１のユーザ設備iと第２のユーザ設備jとの間で共通の秘密データアイテムを生成する方法であって、
前記演算の結果は、前記共通の秘密データアイテムとして前記ユーザ設備の双方で使用され、
前記方法は、Abelian  Varietyに定められるGAP  Diffie-Hellmann問題に属する前記相補的なデータを定めることに基づくことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、
前記Abelian  Varietyは、楕円曲線を通じた１次元を有する方法。
【請求項３】
請求項１に記載の方法であって、
双一次特性と非縮退特性と計算可能特性とを特徴とするペアFを、前記Abelian  Varietyの２つの線形独立のポイントPとD(P)に適用することを有する方法。
【請求項４】
請求項１に記載の方法であって、
ユーザ設備iの前記演算は、Si=fT(ri)及びPi=g(ri)に従った一方向関数fとgに基づき、パラメータTは、信頼できるマスター設備から取得したマスター秘密であり、結果Sは秘密に保持され、共通の秘密データは、
Kij=F(Si,Pj)=F(Sj,Pi)=Kji
に従って計算される方法。
【請求項５】
請求項４に記載の方法であって、
前記演算は、データSi及びPiに基づき、
Si:Si1=T11+riT12;      (5’)
Si2=T21+riT22;      (6’)
Pi:Pi1=riP;            (7’)
Pi2=ri2P;          (8’)
である方法。
【請求項６】
請求項１に記載の方法であって、
ユーザ設備1は、データr1D(P),r12D(P)をユーザ設備2に送信し、
ユーザ設備2は、データr2D(P),r22D(P)をユーザ設備1に送信し、
それに続いて、トリプルr2D(P),r2D(P),r22D(P)がDiffie-Hellmannトリプルであるか否かをユーザ設備1が検査し、トリプルr1D(P),r1D(P),r12D(P)がDiffie-Hellmannトリプルであるか否かをユーザ設備2が検査し、
肯定的な場合に、
Πk=12e((tk1+r1tk2)P,v(r2)kD(P))=e(P,D(P))<v(r1),Tv(r2)>
に従ってユーザ設備1による共有鍵を計算し、ここで、t12=t21であり、v(r2)kはベクトルv(r2)の第k成分を意味する方法。
【請求項７】
請求項１に記載の方法であって、
固有のパラメータを各ユーザ設備に割り当てることを通じて、１つ以上の選択されたユーザ設備を排除する標準的な機構の上に、取消機構を更に有する方法。
【請求項８】
請求項１に記載の方法であって、
前記共有の秘密の生成が、識別又は認証手順の初期ステップとして使用される方法。
【請求項９】
請求項１に記載の方法であって、
Weil  Pairingは、真のプロトコルの実行の実質的に前にある時に求められる方法。
【請求項１０】
請求項１に記載の方法であって、
以前の秘密情報の漏洩に対して秘密情報を更新することを有する方法。
【請求項１１】
請求項１に記載の方法であって、
単一の統合した暗号化レベルのみを使用することを通じて実行される方法。
【請求項１２】
請求項１に記載の方法であって、
ランダム化機構が共通の秘密に適用される方法。
【請求項１３】
請求項１２に記載の方法であって、
前記ランダム化機構は、チャレンジ・レスポンス型機構に基づく方法。
【請求項１４】
第１のユーザ設備と第２のユーザ設備とを有し、請求項１に記載の方法に従って通信するように構成されたシステム。
【請求項１５】
請求項１４に記載のシステムの第１及び／又は第２のユーザ設備として動作するように構成された装置。
【請求項１６】
請求項１に記載の方法を実施するように１つ以上のデータ処理指向のハードウェアエンティティを制御する命令を有するコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各ユーザ設備により、少なくとも部分的に秘密であるそれぞれ固有の量に基づくそれぞれ相補的なデータで相互に対称的な演算を実行することを通じて、第１のユーザ設備と第２のユーザ設備との間で共通の秘密データアイテムを生成する方法に関するものであり、請求項１のプリアンブルに更に記載されているように、前記演算の結果は、前記共通の秘密データアイテムとして前記ユーザ設備の双方で使用される。
【背景技術】
【０００２】
共有鍵の生成は、暗号化で重要な問題である。その問題は、家庭用電化製品のPay  TVシステムや、多様な識別手順のような適用分野まで広がっている。秘密データアイテムは、ユーザ設備又はその他のものの間で相互の認証を実行する暗号鍵又は複号鍵として使用されることがある。従来技術は広くDiffie-Hellmann機構を検討してきたが、不利なことに、その機構は計算された秘密データアイテムの信頼性を検査する制御機構を欠いている。代替として、共有秘密データアイテムの設定可能にする証明書に基づくシステムが、特に本発明の共同発明者の１人により本譲受人に譲渡された米国特許5,218,637(代理人管理番号PHQ90.021)に提案されている。この技術は前記の問題を解決するが、他方で少なくとも２つのレベルの公開鍵の暗号化を利用する複雑な機構を必要とする。本発明の第１の目的は、単一の統合した暗号化レベルのみを使用することである。これは、確認動作を実行するために第２の秘密データアイテムが必要とされないことを意味する。
【０００３】
本発明の更なる目的は、本発明により実現される既存のシステムと同じレベルの秘密性を提供する特別のユーザ施設でシステムが拡張可能であるが、このような既存のシステムに更なる修正を必要としないことである。本発明の更にその他の目的は、ユーザ設備の任意の大量のサブセットに関する秘密データアイテムの認識が、システムに存在するその他のユーザ設備の各秘密データアイテムの簡単且つ実現可能な計算を可能にしないことである。本発明の更なる目的は、使用される多様な量とデータアイテムのコンパクトな表示を可能にすることである。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
したがって、特に、前述の要件を満たしながら、２つのユーザ設備の間で共通の秘密データアイテムを生成する改善した方法を提供することが本発明の目的である。
【課題を解決するための手段】
【０００５】
従って、その態様の１つによれば、本発明は、請求項１の特徴部分に従って特徴付けられる。特に、本発明の第１実施例は、Dan  BonehとMatt  Franklinによる“Identity  Based  Encryption  from  the  Weil  Pairing”という題のCRYPTO2001で提示された明確な論文に十分に説明されている、いわゆるWeil  Pairingの使用に基づく。更に、本発明の第２実施例及び更に広い実施例は、いわゆるAbelian  Varietiesの使用に基づき、Weil  Pairingが実行される楕円曲線がサブクラスを構成する。しかし、前記の概念は、本発明と同じ動作方法と目的について検討されていない。Abelian  Varietiesは、K.RubinとA.Silverbergによる“Supersingular  Abelian  Varieties  in  Cryptology”という題のCRYPTO2002で提示された明確な論文に十分に説明されている。本発明の更に有利な態様は、効果的に使用される簡単な数学手順のため、コンパクトな表示が可能になることである。
【０００６】
本発明はまた、第１のユーザ設備と第２のユーザ設備とを有し、請求項１に記載の方法に従って通信するように構成されたシステムに関するものであり、請求項１４に記載のシステムの第１及び／又は第２のユーザ設備として動作するように構成された装置に関するものであり、請求項１に記載の方法を実施するように１つ以上のデータ処理指向のハードウェアエンティティを制御するコンピュータ命令を有するコンピュータプログラム製品に関するものである。本発明の更に有利な態様が従属項に記載されている。
【発明を実施するための最良の形態】
【０００７】
本発明の前記及び更なる態様と利点について、好ましい実施例の開示を参照して、特に添付図面を参照して以下に詳細に説明する。
【０００８】
［使用する手順の数学的な概略］
本発明の基本的な実施例はWeil  pairingに基づき、そのWeil  pairingは楕円曲線から有限フィールドへの双一次マッピング(bilinear  mapping)である。それは、楕円曲線のコンパクトな表示について有限フィールドでのDiscrete  Log問題を表現するために使用される。この手順は、従来技術のものと同等又はそれより大きい計算の複雑性を備えた暗号解読を示し、そのような暗号解読を有効に実行不可能にする一方で、共有の秘密データアイテムと、200ビット未満の長さのビットを有することができる更なるパラメータとを使用することを可能にする。提案のシステムは、有限の数の関係者のデータの認識がシステムの秘密を明かさないという点で、更に非常に頑強である。そうでなければ、任意の従属のユーザで新しい共有鍵の生成が可能になる。
【０００９】
更に、各ユーザ又は装置はその固有のパラメータを有し、その固有のパラメータにより、必要な場合に、選択された装置を排除する標準的な機構の上に、取消機構を設定することが可能になる。従って、そのシステムにより、従来のシステムよりかなり小さい記憶容量しか必要としない一方で、ユーザの如何なるペアの間で共有の秘密データアイテムを生成することが可能になる。
【００１０】
次に、本実施例の提案プロトコルは、Diffie-Hellmann問題の拡張版に基づく。楕円曲線Eについて、Computational  Diffie-Hellmann(CDH)問題は以下のように見える。ポイントP∈Eと所定のaPとbPを仮定すると、多項式時間でabPを計算するアルゴリズムは存在しない。次に、本発明は、本発明に関しては以下のように定義付けられる拡張Diffie-Hellmann問題、すなわちEDHを適用する。
【００１１】
P,aP,bP,a2P,b2P→abP
明らかに、これは、計算について難解な問題を依然としてもたらす。ところで、楕円曲線のDecision  Diffie  Hellmann、すなわちDDH問題は、かなり簡単である。DDH問題は、P∈EであるつのポイントaP,bP,cPを仮定すると、cP=(a*b)Pであるか否かを決定することにより定められる。この相対的な簡潔さは、Weil  Pairingとして知られる効率的な計算可能双一次マッピングから得られる。そのWeil  Pairingについては以下に詳細に説明する。更に、参照刊行物が追加情報を提供する。特に、DDHが相対的に簡単であるがCDHが難解であるようなグループは、GAP  Diffie-Hellmanグループを示すと言われる。このようなグループはAbelian  Varietiesに存在し、その特異な(supersingular)楕円曲線は、その１次元でのサブカテゴリである。Computational  Diffie-Hellmann問題が難解であるがDDHが簡単であるような多様な実現可能な楕円曲線のうち、以下の例示的な実施例の曲線を使用する。
【００１２】
E+:y2=x3+2x+1  over  F3l
E-:y2=x3+2x-1  over  F3l
ここで、<P>を、安全パラメータαを備えたプライムオーダー(prime  order)qのE/Fplのサブグループとする。このパラメータαは、Computational  Diffie-Hellmann問題CDHが十分に難解であるが、それと同時に、Decision  Diffie-Hellmannの計算を非効率的に難解にしないように、十分に大きくなければならない。２つの例示的な曲線の上の安全パラメータはα=6である点に留意すべきである(Bonehを参照)。更に、ポイントD(P)∈E/FplがポイントPと線形独立になるように、歪みマップ(distortion  map)D又はグループ同形(group  isomorphism)の可用性を自由に仮定する。歪みマップは、主にE.Verheulによる刊行物“Evidence  that  XTR  is  more  Secure  than  Supersingular  Elliptic  Curve  Cryptosystems”、EUROCRYPT2001に明確に説明されている。この歪みマップは、グループ<P>と<D(P)>とで効率的な計算可能同形(efficiently  computable  isomorphism)を構成する。この例の楕円曲線は、その多数の中から２つのみである点に留意すべきである。
【００１３】
次に、２つの線形独立のポイントPとD(P)で、ある問題を解決するためにWeil  Pairingを使用することができる。E[q]を、PとD(P)により生成されたE/Fplαのサブグループを示すものとする。この場合、Weil  Pairingはe:E[q]xE[q]→F*plに従ったマップであり、以下の特性を満たす。
１．P∈E[q]について、e(P,P)=1を有する。
２．P1,P2∈E[q]とr,s∈Zについて、e(aP1,bP2)=e(P1,P2)ab、つまり、双一次特性を有する。
３．P∈E[q]において、全てのP’∈E[q]についてe(P,P’)=1を有する場合、P=O、つまり、非縮退特性(non-degeneration  property)である。
４．全てのP1,P2∈E[q]について、Weil  Pairing  e(P1,P2)が効率的に計算され得る。つまり、計算可能特性である。
【００１４】
以下の機構が設定される。２つのユーザ設備のそれぞれは、信頼できる第三者機関から以下の秘密データアイテムを取得する。以下、そのアイテムがユーザiについて記載される(信頼できる機関は２つの共同動作するユーザ設備のうちの１つでもよい点に留意すべきである)。
【００１５】
５．(t11+rit12)P
６．(t12+rit22)P
更に、以下の２つのデータアイテムも同様に提供される。
【００１６】
７．riD(P)
８．ri2D(P)
しかし、後者の２つのデータアイテムは必ずしも秘密に保持される必要はなく、そのため、後の参照のため、例えば公開ディレクトリに格納されてもよい。更に、以下の対称マトリクスT(T12=T21)が定められる。
【００１７】
【数１】
2006500814.tif 000003
更に、v(r)=(1,r)のように、ポイントr∈Zqに関連付けられるベクトルv(r)を導入する。その後、プロトコルは以下のように進む。
【００１８】
最初に、ユーザ1がデータr1D(P),r12D(P)をユーザ2に送信し、更に、ユーザ2がデータr2D(P),r22D(P)をユーザ1に送信し、それに続いて、トリプルr2D(P),r2D(P),r22D(P)がDiffie-Hellmannトリプルであるか否かをユーザ1が検査し、トリプルr1D(P),r1D(P),r12D(P)がDiffie-Hellmannトリプルであるか否かをユーザ2が検査し、肯定的な場合に、双方がΠi=12e((ti1+r1ti2)P,v(r2)iD(P))=e(P,D(P))<v(r1),Tv(r2)>に従ってユーザ1による共有鍵、すなわち秘密の共通鍵を計算する。ここで、t12=t21であり、v(r2)はベクトルv(r2)の第i成分を意味する。前記のプロトコルの安全性が高いことがわかる。実質的に、安全性は拡張Diffie-Hellmann問題が難解であることを見出すことにある。
【００１９】
安全レベルを更に高める更なる措置は、タイムスタンプの適用と共に、生成した共有鍵のハッシュである。更に、共有の秘密を生成するプロトコルの生成は、この出願の同じ譲受人に割り当てられた欧州特許出願02  075  983.3(代理人管理番号PHNL020192)に開示された識別手順の初期ステップとして使用され得る。
【００２０】
更に、事前にWeil  Pairing  e((t11+r1t12)P,D(P))の計算を既に計算することにより、プロトコルがより効率的になり得る。これは、真のプロトコルの実行時にこのWeil  Pairingの計算を行う必要性を回避するが、上昇する記憶装置の要件とのトレードオフになる。
【００２１】
［好ましい実施例の詳細な説明］
図１は、ネットワークを介して相互接続され、本発明に従って動作するように構成されたシステム100を示している。一例として、このシステムはホームシステムであり、ラジオ受信機やテレビセット等のような装置を有してもよい。一般的に、特定の装置はシステムのマスターであり、他のものを制御する。一般的に、コンテンツは、ブロードバンドやインターネットや衛星のような外部ソースから、住宅用ゲートウェイ又はセットトップボックス101のような１つ以上の装置を通じて受信される。最終的に、コンテンツは、装置のうちの１つの適切な処理でネットワークを通じて転送される。
【００２２】
一般的に、ホームネットワークの全ての装置は、実装の要件に従った安全のフレームワークを実装する。このフレームワークを使用して、これらの装置は相互に認証し、安全な方法でコンテンツを配信する。真のコンテンツへのアクセスは、セキュリティシステムにより管理される。これにより、プロテクトされていないコンテンツが無許可の装置に漏れることを防止し、信頼のない装置から生じたデータがシステムに入ることを防止する。このようなプロテクションで、装置は、事前にうまく認証している他の装置にのみコンテンツを配信してもよい。このことにより、対抗者が不当な装置を通じて無許可のコピーを受信しないことを確保する。例えば、許可された製造者のみが認証の成功に必要な特定の秘密を認識しているため、装置は信頼できる第三者機関により発行された証明書を備えているため、ある装置は、許可された製造者により作られた場合にのみ、それ自体をうまく認証することができる。
【００２３】
図２は、図１のシステムの一般化を示している。ここで、証明器Pと検証器Vと信頼できる第三者機関TTPが共同動作する。ここで、検証器Vは、信頼できる第三者機関TTPから受信した情報を使用して、証明器Pを認証しようとする。好ましくは、検証器Vが信頼できることを証明器Pが認識するように、認証は相互であるべきである。
【００２４】
証明器Pに対して検証器Vを認証するために必要な情報は、TTPから関係者PとVに事前に配信されていると仮定する。これは、３つの関係者間の適切な通信設備で行われ得る。これはプロトコルを動的にし、対抗者が以前に配信された秘密に対して無許可のアクセスを取得しようとした場合に、情報の更新を可能にする。
【００２５】
証明器Pと検証器Vは、必要な機能を備えるチップを備えた図１のキャリア120でもよく、更には音声再生装置105のような装置でもよい。このような場合、TTPから証明器Pと検証器Vへの通信チャネルが存在しない可能性が高い。そこで、秘密の配信は製造中のように事前に行われなければならない。
【００２６】
証明器は、ネットワークモジュール301と、暗号化プロセッサ302と、記憶媒体303とを有する。ネットワークモジュール301を使用して、証明器Pは、検証器Vに対してデータを送受信することができる。ネットワークモジュール301は、図１のネットワーク110に接続されてもよく、また、検証器Vと無線のような直接接続を確立してもよい。
【００２７】
暗号化プロセッサ302は、本発明による方法を実行するように構成される。通常は、このプロセッサ302はハードウェアとソフトウェアの組合せとして実現されるが、代替として、ソフトウェアモジュール又はオブジェクトの集合のように、完全にその一方で実現されてもよい。
【００２８】
証明器Pは実行するアルゴリズムの多様なパラメータを記憶媒体に格納してもよいが、認証の成功の後に、検証器Vに配信するある程度のコンテンツを保持してもよい。記憶媒体303は、TTPから受信した情報を格納するために更に使用されてもよい。システムの安全性を高めるために、個々のパラメータのデータを格納するのではなく、その代わりに、又は代替として、１つ以上の中間計算結果が格納されてもよい。
【００２９】
同様に、検証器Vは、証明器Pのものに対応する機能を備えたネットワークモジュール311と、暗号化プロセッサ312と、記憶設備313とを有する。検証器Vがディスク内チップ(Chip-in-Disc)を備えたキャリアとして具体化される場合、記憶設備313は、如何なる光ディスク又はその他のディスクに利用可能な記憶装置に対応してもよいが、ディスク内チップのROMに格納されることが好ましい。
【００３０】
更に、証明器Pと検証器Vは、ハードウェア又はソフトウェアで実現され、暗号強度の強い擬似乱数を備えた擬似乱数生成器304,314を備えてもよい。この数は、本発明の多様な好ましい用途で使用される。
【００３１】
［補足の数学的説明］
前記では、共通の秘密鍵は、以下に従って行われている。
【００３２】
Kij=F(Si,Pj)==F(Sj,Pi)Kji
しかし、以下のデータが伝達される。
【００３３】
Si=fT(ri)      (5,6)、及び
Pi=g(ri)      (7,8)
伝達されるデータアイテムのその他の表示は次に従う。
Si      Si1=T11+riT12      (5’)
Si2=T21+riT22      (6’)
Pi      Pi1=riP            (7’)
Pi2=ri2P          (8’)
ここで、Tij=tij*Pであり、数字は前の表示との対応を示す。
【図面の簡単な説明】
【００３４】
【図１】ネットワークを介して相互接続され、本発明に従って動作するように構成された多様な装置を有するシステムである。
【図２】図１のシステムの一般化である。
【図１】
2006500814.tif 000004
【図２】
2006500814.tif 000005
【国際調査報告】
2006500814.tif 000006
2006500814.tif 000007