(57)【要約】いくつかの装置（３０）を備えているシステム（１０）の認証方法を提供する。方法は、a)  識別値（pi：i=1,…,n）と、多項式鍵を生成するための多項式（P）とを各装置（３０）に供給する工程と、b)上記装置（３０）の中に検証者装置（p1）及び証明者装置(p2)を備える工程と、c)証明者装置(p2)がその存在を検証者装置(p1)に通知するよう構成する工程と、d)検証者装置(p1)が、証明者（p2）装置の多項式（P）鍵を用いてノンスを暗号化するよう証明者装置（p2）にチャレンジし、検証者装置（p1）への応答として、暗号化されたノンスを通信するよう構成する工程と、e)検証者装置(p1)が、証明者装置(p2)からの更なるチャレンジとして、暗号化されたノンスを受信し、(i)記憶された装置識別情報組から生成される多項式鍵を用いてチャレンジを暗号化すること、又は(ii)多項式鍵組を用いて、受信チャレンジを復号することを、検証者装置(p1)が認証の一致を識別するまで行うよう構成する工程とを備えている。
2008515320.tif 000002
【特許請求の範囲】
【請求項１】
相互に通信するよう動作可能な複数の装置を備えるシステムの、多項式に基づいた認証の方法であって、
(a)  多項式鍵を生成するための関連した多項式とともに、対応する識別値を前記複数の装置それぞれに供給する工程と、
(b)  前記複数の装置が検証者装置及び証明者装置を有するよう構成する工程と、
(c)  前記証明者装置がその存在を前記検証者装置に通知するよう構成する工程と、
(d)  前記検証者装置が、前記証明者装置の多項式鍵を用いてノンスを暗号化する旨の第１のチャレンジを前記証明者装置に出し、前記検証者装置への応答として、前記暗号化されたノンスを通信するよう構成する工程と、
(e)  前記検証者装置が、前記証明者装置からの前記応答として、前記暗号化されたノンスを受信し、
(i)  記憶された装置識別情報組から生成される多項式鍵を用いて前記第１のチャレンジを暗号化することと、
(ii)  前記証明者装置から受信した前記応答を、前記多項式鍵を用いて復号することとを、
前記検証者装置が前記応答に対する一致を識別するまで行うよう構成する工程とを備えており、前記一致が認証を示す方法。
【請求項２】
請求項１記載の方法であって、前記識別値及び前記関連した多項式の送出が、第三者機関を介して行われる方法。
【請求項３】
請求項１記載の方法であって、前記複数の装置に相互認証を供給するために前記システムにおいて、前記認証の方法を、一般的な相互認証鍵設定プロトコルに適用する更なる工程を有している方法。
【請求項４】
請求項１記載の方法であって、ランダム値が、前記証明者装置によって更に作成され、前記検証者装置に送り返すために、前記検証者装置からの前記応答とともに暗号化され、前記ランダム値は、セッション鍵として機能するよう動作可能である方法。
【請求項５】
請求項１記載の方法であって、前記検証者装置から前記証明者装置への前記第１のチャレンジは、前記ノンスが乱数であるように実現される方法。
【請求項６】
請求項１記載の方法であって、前記複数の装置が複数の証明者装置及び複数の検証者装置を有するように前記システムを構成する工程を更に有しており、前記複数の証明者装置は、前記複数の検証者装置のうちの特定の検証者装置に対して認証するよう動作可能な証明者装置部分集合を有する方法。
【請求項７】
請求項１記載の方法であって、前記証明者装置は、特定の検証者装置に関連しており、かつ／又は結合されているサービスへのアクセスを可能にするスマート・カード又はタグとして実現される方法。
【請求項８】
請求項1記載の方法であって、前記証明者装置は、ハッシュ関数又は鍵つきハッシュ関数を施して、前記検証者装置からの前記第１のチャレンジに対する応答を作成するよう動作可能である方法。
【請求項９】
請求項１記載の方法によって動作可能なシステム。
【請求項１０】
請求項９記載のシステムであって、
(a)  銀行システム内で実行される金融取引に関連した認証と、
(b)  前記方法によって動作可能なシステム内で認証するタグ又は同様なポータブル識別子による、アクセス、例えば、個人アクセス、の制御と
の少なくとも一方を備えるように適合させたシステム。
【請求項１１】
請求項１記載の方法を実現するためのコンピューティング・ハードウェア上で実行可能なデータ担体上のソフトウェア。
【請求項１２】
認証システムにおいて認証を行うスマート・カード又はタグであって、前記システムが、請求項１記載の方法によって動作可能であるよう構成されたスマート・カード又はタグ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多項式に基づいた認証の方法に関する。更に、本発明は、前述の方法によって動作可能なシステム及び装置にも関する。
【背景技術】
【０００２】
認証プロトコルは、第1の関係者がその識別情報を第2の関係者に対して証明することを可能にする現代の通信システムにおいて用いられる。便宜上、前述の第１の関係者及び第２の関係者は、証明者及び検証者それぞれによって好都合に表される。多くの既知のプロトコルでは、証明者はまず、識別情報を要求し、その後、証明者は、証明者の要求識別情報に関連した特定の秘密を知っていることを証明する。２つの関係者が互いの識別情報を保証されるプロトコルは、「相互認証」と呼ばれる。前述の認証は多くの場合、鍵設定手順を用いて（例えば、公開鍵・秘密鍵認証プロトコルを用いて）実現される。前述の認証プロトコルは識別情報を検証するのみならず、多くの場合、更に、それとの間で更なる通信を暗号化し、認証することが可能なその対称セッション鍵を設定する。
【０００３】
互いに通信している関係者の識別情報を、互いに通信している関係者を観察又は盗聴している第３者によって判定することが可能でないことが望ましいことを本願発明者は認識している。実際に、スマート・カード・リーダ（例えば、セキュリティが強化されたビルの入口にあるスマート・カード・リーダ）に提示される無線スマート・カードを用いてユーザが自らを認証する場合に、前述の状況が潜在的に生じ得る。標準認証プロトコルが入口で利用された場合、盗聴者は仮説的に、単に、この場所にいるユーザが存在していることを検出することが可能である。前述の検出は潜在的には、ユーザの位置追跡を実行するための重要な初期情報を提供することが可能である。更に、この位置追跡は、個人のプライバシの侵害を構成し得る。
【０００４】
この問題点は、Martin  Abadiによって（Springer  Lecture  Notes  in  Computer  Science  vol.  2482/2003,  pp.27-40に講演録が公表されている、「Private  Authentication」（Conference  on  Privacy  Enhancing  Technolgies  (PET2002),  San  Francisco,  USA,  April  2002において発表されている）と題する科学論文において）予見されている。M.  Abadiは前述の論文において、西暦1996年にJohn  Wiley  &  Sons  Inc.によって発行されたB.  Schneiderによる刊行物「Applied  Cryptography」（Second  Edition）において明らかにされた公知のデニング・サッコ（Denning-Sacco）プロトコル及びニーダム・シュレーダー（Needham-Schroeder）プロトコルの変形である２つのプロトコルを開示している。M.  Abadiによって最近提案されている前述のプロトコルの問題点は、その実現に比較的大量の処理能力を要する公開鍵暗号法が利用されていることである（前述の処理能力は多くの場合、小型の消費者向装置上（例えば、バッテリによって電源供給されるポータブル装置上）では実用的でなく、かつ／又は利用可能でない。
【０００５】
より最近の多項式ベースのマルチユーザ鍵生成及び認証の方法は、国際公開（PCT特許出願公開）第０３／０７７４７０号（代理人整理番号PHNL０２０１９２）パンフレットに開示されている。前述のPCT出願には、第１の関係者と第２の関係者との間で共通の秘密を生成する方法が開示されている。前述の関係者は例えば、現代のディジタル著作権管理（DRM）フレームワークによって動作可能なホーム・ネットワークにおける装置であり得る。前述の装置は、先行して第三者機関（TTP）によって配布されたパラメータ及び別の装置から得られたパラメータを用いて２つの多項式P(x,y)及びQ(x,y)の積を求めることによって共通の秘密を算出する。任意的には、各関係者は、別の関係者がゼロ知識プロトコル又はコミットメント・ベースのプロトコルを用いて同じ秘密を生成したことを後に検証する。上記PCT出願公開に開示されている前述の方法は、チップインディスク・タイプの装置などの低電力装置に関して用いるのに特に適している。本発明によって本願発明者が解決しようとしている欠点及び制約を前述の最近の認証方法も有していることを本願発明者は認識している。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、代替的な認証プロトコル方法を提供することである。
【課題を解決するための手段】
【０００７】
本発明の第１の局面によれば、互いに通信するよう動作可能な複数の装置を備えるシステムの、多項式に基づいた認証の方法を提供する。前述の方法は、
(a)  多項式鍵を生成するための関連した多項式（P）とともに、対応する識別値（pi：i=1,n）を上記複数の装置それぞれに供給する工程と、
(b)  上記複数の装置が検証者装置（p1）及び証明者装置(p2)を有するよう構成する工程と、
(c)  証明者装置(p2)がその存在を検証者装置(p1)に通知するよう構成する工程と、
(d)  検証者装置(p1)が、証明者（p2）装置の多項式（P）鍵を用いてノンスを暗号化する旨の第１のチャレンジを証明者装置（p2）に出し、検証者装置（p1）への応答として、暗号化されたノンスを通信するよう構成する工程と、
(e)  検証者装置(p1)が、証明者装置(p2)からの応答として、暗号化されたノンスを受信し、
(i)  記憶された装置識別情報組から生成される多項式鍵を用いて第１のチャレンジを暗号化すること、又は
(ii)  証明者装置(p2)から受信した暗号化応答を、多項式鍵を用いて、復号することを、検証者装置(p1)が上記応答に対する一致を識別するまで行うよう構成する工程とを備えており、上記一致は認証を示す。
【０００８】
多項式に基づいた認証の、より柔軟な手順を提供することができることは、本発明の利点である。
【０００９】
「多項式鍵」は、多項式（例えば、k=Pp1(p2)、kは鍵、Pp1は多項式、ｐ２は、多項式に代入される値である）の数値を求めた結果である。
【００１０】
システム内の個々の装置は、検証者としても証明者としても動作することができる。任意的には、システムの装置の1つ又は複数は、検証者及び証明者として同時に機能することができる。
【００１１】
任意的には、方法の工程(a)において、識別値(pi)及び関連した多項式の送出は、第三者機関を介して行われる。前述の手法によって、システムの展開が、信頼されたものになる。
【００１２】
任意的には、方法は、複数の装置に相互認証を供給するために上記システムにおいて、前述の認証の方法を、一般的な相互認証鍵設定プロトコルに適用する更なる工程を有する。
【００１３】
任意的には、上記方法では、ランダム値が、証明者装置によって更に作成され、検証者装置に送り返すために、検証者装置からの応答とともに暗号化される。前述の乱数（ランダム値）は、セッション鍵として機能するよう動作可能である。このセッション鍵は、通信のシーケンスの記録を備えるのみならず、複数の装置に対する盗聴に対する保護も備えるように効果的に更新される。
【００１４】
任意的には、上記方法では、検証者装置（p1）から証明者装置(p2)への第１のチャレンジはランダム値である。ランダム値として実現されるノンスを用いることによって、システムの盗聴がより難しくなる。
【００１５】
任意的には、方法は、複数の証明者装置及び複数の検証者装置を複数の装置が有するようにシステムを構成する工程を更に有しており、複数の証明者装置は、複数の検証者装置のうちの特定の検証者装置に対して認証するよう動作可能な証明者装置部分集合を有する。
【００１６】
任意的には、方法では、上記証明者装置は、特定の検証者装置に関連しており、かつ／又は結合されているサービスへのアクセスを可能にするスマート・カード又はタグとして実現される。
【００１７】
任意的には、方法では、多項式は、ブロム(Blom)タイプの鍵として機能するよう処理可能である。内容を本明細書及び特許請求の範囲に援用するRolf  Blom（Linkoping  University）による刊行物に関して、前述において明らかにしている。
【００１８】
任意的には、方法では、証明者装置は、ハッシュ関数又は鍵つきハッシュ関数を施して、検証者装置からの第１のチャレンジに対する応答を作成するよう動作可能である。
【００１９】
本発明の第２の局面によれば、本発明の第１の局面の方法によって動作可能なシステムを提供する。任意的には、
(a)銀行システム内で実行される金融取引に関連した認証と、
(b)上記方法によって動作可能なシステム内で認証するタグ又は同様なポータブル識別子によるアクセス（例えば、個人アクセス）の制御と
の少なくとも一方を備えるようシステムを適合させる。
【００２０】
本発明の第３の局面によれば、本発明の第１の局面による方法を実現するためにコンピューティング・ハードウェア上で実行可能なデータ担体上にソフトウェアを提供する。
【００２１】
本発明の第４の局面によれば、認証システムにおいて認証を行うスマート・カード又はタグが提供される。上記システムは、本発明の第１の局面による方法によって動作可能であるよう構成される。
【発明を実施するための最良の形態】
【００２２】
本発明の範囲から逸脱することなくどのような組み合わせでも本発明の特徴を組み合わせることができるということが認識されよう。
【００２３】
本発明の実施例を、単に例として以下の添付図面を参照して次に説明する。
【実施例】
【００２４】
本発明では、公開鍵暗号法の利用に関連した問題なしで盗聴に対するプライバシ及び保護を提供するよう動作可能な認証プロトコルを本願発明者は考え出した。更に、考え出されたプロトコルは使用中に、全く対称の鍵ベースの手法よりも大きな柔軟性を提供することができる。本願発明者の認証プロトコルは、Rolf  Blomによって（Advances  in  Cryptography,  Proceedings  of  Crypto  ’82,  pp.  231-236,  1983において公表された技術論文「Non-public  key  distribution」において）提案された手法に基づいている。R.  Blomによる科学論文における開示は、本発明を明らかにする目的で、内容を本明細書及び特許請求の範囲に援用する。
【００２５】
本発明の実施例（システムとして実現される）は図１を参照して説明する。システムは、(n+1)行×(n+1)列のサイズを有する対称行列Tを選ぶ第三者機関（TTPによって表す）を備える。行列Tは、tijによって表すエレメント・エントリを有し、指数iは行列の列を表し、指数jは行列の行を表す。行列Tが対称性を表すために、エレメント・エントリは、tij=tjiであるように実現される。この行列Tのエントリtijはよって、等式１（式１）によって定義されるP(x,y)によって表すn次の多項式の係数を構成する。
【００２６】
【数１】
2008515320.tif 000003
式１
行列Tが対称であるため、値のフィールドGF(2k)におけるx及びy全てについて、多項式P(x,y)=P(y,x)であることが結果として生じる。第三者機関TTPは、システム内に備えられている各装置iに、識別値ｐと、Ppi(y)によって表される対応するプライベートの予測多項式とを送出する。このプライベートの予測多項式Ppi(y)は、等式２（式２）によって表す装置の識別値piに等しくなるよう多項式P(x,y)の第１の引数を割り当てることによって第三者機関TTPによって生成される。
【００２７】
【数２】
2008515320.tif 000004
式２
式１から、行列Tの対称性、及び多項式P（ｘ,y）の結果として生じる対称性が結果として生じ、等式３（式３）は、pi,pj∈GF（2k）であるような識別値pi,pjの値全てについてあてはまる。
【００２８】
【数３】
2008515320.tif 000005
式３
よって、前述のシステムは、その識別値piに対応する予測多項式Pを第三者機関TTPから各装置が得ることによって動作する。この多項式Pは、(n+1)個の係数gj（pi）（装置にセキュアに記憶される）として伝達される。前述の係数は、等式４（式４）に従って第三者機関TTPによって生成される。
【００２９】
【数４】
2008515320.tif 000006
式４
識別値piを有する特定の装置の予測多項式Ppi(y)はよって、等式５（式５）によって表すことが可能である。
【００３０】
【数５】
2008515320.tif 000007
式５
第三者機関TTPから個々の装置への多項式係数の配布は、図１に示す。図１では、前述のシステムは、全体として１０で示す。第三者機関TTPは２０で示し、割り当てられた識別情報i=4を有する装置の１つは３０で示す。図１では、5個の装置が存在しているが、システム１０は、d個の装置を有するものとする。ここで、dは、値が単位元以上の整数である。整数dは、前述のパラメータnに数値的に等しくなくてよい。システム１０において必要な記憶及び処理の能力を削減するために、n＜dであるよう構成し、システム１０内の装置の広範囲にわたる結託が動作上生起しないものとすることが望ましい。
【００３１】
以上で、多項式Pが第三者機関TTP20によって生成され、装置（例えば、装置３０）に割り当てられるやり方を説明したが、真正性の検証を提供するシステム１０の動作は次に明らかにする。
【００３２】
システム１０内の装置は任意的には、証明者及び検証者として機能するよう動作可能である。例えば、識別情報p2を有する装置は、検証者として動作可能な識別情報p1を有する装置に対して証明者として自らを認証することができる。本発明の実用的な応用例では、検証者として動作可能な装置は、セキュリティが強化されたビルの入口のドアにあるタグ・リーダとして実現することが可能である。更に、実際には、その場合、複数の証明者（例えば、セキュリティが強化されたビルに入るための、ユーザ着用可能なミニチュアＲＦＩＤタグとして容易に実現される）が存在することになる。検証者（例えば、前述のタグ・リーダ）は、その中に記憶された、長さがmのコンフィギュレーション・テーブル（CT）を有する。このコンフィギュレーション・テーブルは、認証することが可能であり、よって、アクセスが許容され得る証明者の識別値piを備える。任意的には、コンフィギュレーション・テーブル（CT）は、公にアクセス可能である。すなわち、秘密又は機密を保持しなくてよい。
【００３３】
システム１０では、コンフィギュレーション・テーブルは、システム管理者のみによる更新が可能である。任意的には、管理者は、検証者の所有者である。コンフィギュレーション・テーブルの改訂において、管理者は、アクセスを付与するために、証明者の識別値をこのテーブル（CT）に加えるよう動作可能である。既知の対称鍵構成と比較対照すれば、本発明は、証明者がテーブル（CT）に加えられる際に証明者と、対応する検証者との間で新たな共有鍵を何ら設定しなくてよいという点を特徴とする。前述の利点が生じるのは、システム１０が、対応するプライベートの多項式Pp2(y)及びPpi(y)それぞれを事前に証明者及び検証者に供給することを伴うからである。
【００３４】
次に、検証者によって受信される「ハロー」メッセージ１００（すなわち、図２に表すような第１の呼び出しメッセージ）を送出することによって証明者（ＰＲ）がその存在を検証者（VE）に通知するシナリオにおいてシステム１０の動作を説明する。検証者VEは次いで、１１０で表すランダム・チャレンジeを生成する。その後、検証者VEはチャレンジeを証明者PRにその識別値p1とともに送出する。次に、証明者PRは、その中の対応する多項式Pp2(y)の値を、y=p1を等しくさせることによって求め、その結果、等式６（式６）によって、１２０で表す秘密鍵Kが生成される。
【００３５】
【数６】
2008515320.tif 000008
式６
次に、証明者PRは次いでこの鍵K１２０を用いて、そこで受信されるチャレンジe110を暗号化する。証明者PRはよって、１３０によって表す応答Aを生成し、応答１３０Aは等式７（式７）によって表される。
【００３６】
【数７】
2008515320.tif 000009
式７
ここで、記号Eは暗号化動作を表し、応答は次いで、検証者VEにもう一度送られる。最後に、１４０によって表すように、検証者ＶＥは、そのコンフィギュレーション・テーブル（CT）における識別値全てを検査して、受信された応答Aが有効な応答であるか否かを判定する。検証者VEはそれによって、テーブル（CT）における識別情報p毎に、秘密鍵Ki=Pp1(pi)を構成し、鍵Kiを用いてチャレンジeを暗号化することができる。検証者VEがそのコンフィギュレーション・テーブル（CT）においてpiの値のうちの1つに対する一致（すなわち、E(Ki)(e)=Aである）を見つけた場合、値piに対応する識別情報が認証される。この例では、検証者VEは、値p2を有する識別情報に対する一致を見つける。前述の一致は、Pp2(p1)=Pp1(p2)のためにK=K2であることから結果として生じる。
【００３７】
よって、図２では、識別情報p2を有する装置（すなわち、証明者PR）が、識別情報p1を有する装置（すなわち、検証者VE）に対して認証されるプライベート認証プロトコルを示している。検証者VEは、認証することが可能な装置組の識別情報を有しているコンフィギュレーション・テーブル（CT）を有している。
【００３８】
図２に表すプロトコルは、識別値p1を有する検証者VEの識別情報を盗聴者が検出することが可能であるが、盗聴者へのリークが可能な、証明者PRに関する識別情報は何らないようなものである。システム１０に対して敵対的な関係者（例えば、敵対者やハッカー）は潜在的には、セッション鍵K=Pｐ2（ｐ１）=Pp1（ｐ２）を取り出すことができる（例えば、式７の暗号化の暗号の強度が低い場合）が、識別情報p1をそこから識別することができなくなり、よって、システム１０は、前述のチャレンジされた状況ではプライバシを維持する。更に、式７におけるようにランダム・チャレンジeを利用するために、応答Aは、識別子p2に関する認証目的のための試行の都度、異なる。よって、盗聴する関係者は、頻度解析によって識別情報を得ることができない。
【００３９】
図１及び図２に表すような前述のプロトコルにおける証明者PRは、その識別情報が検証者VEに見えることが分かる。実際に、証明者は、任意的には、考えられる検証者全てと前述のプロトコルを実現する訳でない。証明者の識別情報を検証者全てが分かることが可能であるためである。潜在的には、システム１０において、一検証者は、例えば敵対的な場合、システム内の装置の１つを追跡することが可能である。前述の問題点を解決するために、特定の証明者PRが通信する準備がある、システム10内の検証者装置VEの識別情報をはじめとするそれ自体のコンフィギュレーション・テーブル（CT）が特定の証明者PRに供給される。証明者PRもコンフィギュレーション・テーブル（CT）を有するこの動作モードでは、証明者PRは、証明者（PR）のCTテーブル上にない検証者からのチャレンジに対応しない。
【００４０】
前述の本発明の実施例を、特許請求の範囲記載の本発明の範囲から逸脱することなく修正することが可能であるということが認識されよう。
【００４１】
システム１０内の装置は、検証機能及び証明機能を同時に提供するよう動作可能であるように構成することができる。
【００４２】
本発明の第１の更なる実施例では、前述のプロトコルを用いて相互認証が実現される場合に対称暗号が利用される。あるいは、証明者PRは、h()によって表す一方向ハッシュ関数を用いることによってその応答Aを生成するよう動作可能である。証明者PRによって生成される応答Aはその場合、等式８（式８）による。
【００４３】
【数８】
2008515320.tif 000010
式８
同様に、検証者VEは、等式９（式９）によって応答Aを検査するよう動作可能である。
【００４４】
【数９】
2008515320.tif 000011
式９
本発明の第２の更なる実施例では、かわりに、コンフィギュレーション・テーブル（CT）内の装置からの考えられる鍵Ki=Pp1(pi)全てによってチャレンジeを暗号化する場合、検証者VEは任意的には、前述の鍵Kiを用いて受信応答Aを復号し、復号された鍵がeに対応するか否かを検査する。
【００４５】
本発明の第３の更なる実施例では、チャレンジeがランダムに選ばれるかわりに、検証者VEは代替的にノンスを用いる。ノンスは、一回限り使用するための一意の数として定義される。
【００４６】
本発明の第４の更なる実施例では、証明者PRは、等式１０（式１０）によって応答を作成することによってセッション鍵rを検証者VEに伝送することが可能である。
【００４７】
【数１０】
2008515320.tif 000012
式１０
ここで、Eは暗号化関数を表す。
【００４８】
等式１０では、チャレンジeもセッション鍵rも鍵K=Pp2(p1)を用いて暗号化される。セッション鍵rは任意的には、証明者PRによって生成される乱数である。検証者VEは、図１及び図２を参照して前述したように証明者PRを識別するために応答Aの第１の部分との一致を見つけるよう動作可能である。特定の証明者PRとの一致が見つかった場合、検証者VEは、更なる後の通信のためのセッション鍵として次いで用いることが可能なセッション鍵rの値を取り出すために、鍵Pp1(p2)を用いることによって応答Aの第２の部分を復号することができる。
【００４９】
以上で明らかにした本発明によるプロトコルは、鍵設定に関して相互認証を達成するのに用いることができる。よって、本発明の多くの実際の利用では、相互認証を提供し、相互認証された鍵を生成するプロトコルを有することが好ましい。多くの現代の相互認証プロトコルは、鍵伝送又は鍵構成に基づいている。対称鍵手法に基づいた前述の現代的なプロトコルは全て、プロトコルが呼び出される前に、相互の長期鍵が利用可能であるものとする。既知のプロトコルと比較対照すれば、本発明による前述のプロトコルは、証明者PRの識別情報を秘密に保つ一方でK=Pp2(pi)（すなわち、等式６）を等しくすることによって長期鍵を供給する。本発明による前述のプロトコルはそれによって、相互に認証された鍵を供給するよう拡張可能である。
【００５０】
図３には、２つの乱数セッション鍵r1、r2を利用した、通信の交換（すなわち、プロトコル）を示す。前述のセッション鍵r1、r2を用いて相互鍵を（例えば、h(r1,r2)によって）導き出すことが可能である。前述の合成プロトコルでは、関係する装置の１つの識別情報は秘密の状態に留まる。一方、別の装置の識別情報は明らかにされる。本発明による前述のプロトコルはよって、半プライベート相互認証鍵設定プロトコルとして知られている。
【００５１】
図３に表すプロトコルは、「Handbook  of  Applied  Cryptography」と題する、Menezesらによる著書の第12章に提示されている、関連したチャレンジ応答を有する「ポイントツーポイント」鍵伝送プロトコルと同様である。しかし、図３のプロトコルは、図１を参照して説明した前述の多項式手法を用いて鍵Kが導き出される点で異なる。証明者PRは、観察者又は盗聴者に対して匿名状態に留まる必要があるために、通信チャネルを介してその識別情報を送出しない。よって、検証者VEがそのリストCT内をサーチして、一致する識別情報を見つけることが必要になる。
【００５２】
図３に表すプロトコルの工程を表１に備える。 
【００５３】
【表１】
2008515320.tif 000013
図３では、ALGOR1及びALGOR2は、表２及び表３それぞれにおいて更に詳細に示す第１のアルゴリズム手順及び第２のアルゴリズム手順に対応する。
【００５４】
【表２】
2008515320.tif 000014
【００５５】
【表３】
2008515320.tif 000015
D{k}(c)は、暗号文cの、鍵kを用いた復号を表す。
【００５６】
E{k}(m)は、メッセージmの、鍵kを用いた暗号化を表す。
【００５７】
動作上、検証者VEは、受信応答Aに一致する識別情報をそのコンフィギュレーション・テーブル（CT）において見つけることができない場合、図３を参照して表１において明らかにしたプロトコルを停止させないことが重要である。すなわち、検証者VEが表１のプロトコルを止めた場合、観察者は潜在的には、認証しようとしている証明者PRがテーブル（CT）においてリストされたエンティティでないことを知ることができる。当然、テーブル（CT）が公にアクセス可能であることは以上から分かるであろう。表１のプロトコルはよって任意的には、一致を見つけることができない場合に検証者VEがおとりメッセージBを作成するように前述の状況において更に精緻化される。観察者はその場合、潜在的には、おとりメッセージBを真のメッセージBと区別することができない。おとりメッセージは、表１に表すプロトコルの実現に利用される特定の形式の暗号化によって構成される。
【００５８】
以上で説明し、識別情報の設定に関して図１に示し、識別情報が設定されたあとのプロトコルに関して図２及び図３に示す、多項式に基づいた認証の方法は、広範囲にわたる実用的な応用例において施すことが可能である。前述の実用的な応用例には、
(a)  タグ読み取り器（例えば、セキュリティが強化された施設、刑務所における要員アクセス・タグ、無線周波数識別情報RFIDに本発明を用いることは特に適切である）、
(b)  セキュアでかつ認証された通信チャネルが必要な通信システム（例えば、銀行システム、個人医療記録をセキュアに記憶し、通信することを要するヘルス・ケア・システム）や、
(c)  偽造防止措置（例えば、本発明に準拠して電子タグが製品に取り付けられている場合、電子タグは、例えば、偽造品を検査するために、輸入時に／税関において電子的に取り調べられる）がある。
【００５９】
特許請求の範囲では、括弧内にある数字や他の記号は特許請求の範囲の理解を支援するために備えられており、いかなるやり方においても特許請求の範囲を限定することを意図するものでない。
【００６０】
「comprise」、「include」、「incorporate」、「contain」、「is」や「have」などの表現は、本明細書及び特許請求の範囲を解釈する場合に非排他的に解される（すなわち、明記されていない他のアイテム又は構成部分も存在することを可能にするよう解される）ものとする。単一形への言及も、複数形への言及として解されるべきであり、逆も同様である。
【図面の簡単な説明】
【００６１】
【図１】本発明による認証の方法を実現するよう設定されたシステムを示す図である。
【図２】証明装置p2が検証装置p1に対して認証するプライベート認証プロトコルにおける、通信の交換を表す図である。
【図３】装置ｐ２と装置ｐ１との間の相互認証における、通信の交換を表す図である。
【図１】
2008515320.tif 000016
【図２】
2008515320.tif 000017
【図３】
2008515320.tif 000018
【国際調査報告】
2008515320.tif 000019
2008515320.tif 000020
2008515320.tif 000021