(57)【要約】      （修正有）【課題】サービングＧＰＲＳ支援ノード（一般パケット無線サービス）において実行される認証方法であって、サービングＧＰＲＳ支援ノードとＨＬＲ／ＡｕＣ（ホームロケーションレジスタ／認証センタ）が互いに遠く離れて位置する場合、認証ベクトルを待機するに際し、長期遅延を防止する。【解決手段】サービングＧＰＲＳ支援ノードのカバー領域に進入した移動端末について、K  (K>1)個の認証ベクトルを、ホームロケーションレジスタ/認証センタから取得し、取得した認証ベクトルをメモリに追加し、メモリに記憶されている認証ベクトルを先入れ先出し方式で用いて移動端末を認証し、メモリに記憶されている未使用の認証ベクトルの数がK-b(0≦b≦K-1)以下になったときに、移動端末についてさらにK個の認証ベクトルをホームロケーションレジスタ/認証センタから取得する。【選択図】図２
2007019752.tif 000002
【特許請求の範囲】
【請求項１】
サービングGPRS（一般パケット無線サービス）支援ノードにおいて実行される認証方法であって、
前記サービングGPRS支援ノードのカバー領域に進入した移動端末について、K(K>1)個の認証ベクトルを、ホームロケーションレジスタ/認証センタから取得する第一取得ステップ、
前記取得した認証ベクトルをメモリに追加する追加ステップ、
前記メモリに記憶されている認証ベクトルを先入れ先出し方式で用いて前記移動端末を認証する認証ステップ、
前記メモリに記憶されている未使用の認証ベクトルの数がK-b(0≦b≦K-1)以下になったときに、前記移動端末についてさらにK個の認証ベクトルを前記ホームロケーションレジスタ/認証センタから取得する第二取得ステップ、
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第三世代無線ネットワークにおける認証方法に関し、特に、SGSN（サービシングGPRS（一般パケット無線サービス）支援ノード）とHLR/AuC（ホームロケーションレジスタ/認証センタ）が互いから遠く離れて位置するとき、またはこの両者が異なる事業者により運営されているとき、または移動端末（MT）による電話・移動活動が頻繁であるときに、認証ベクトル（AV）を待機するに際し起こり得る長期遅延に対処するための相互認証の改良方法に関する。
【背景技術】
【０００２】
近年、次世代無線ネットワーク認証のための種々のメカニズムが提案されている。たとえば、第三世代無線ネットワークにおける認証プロトコルに関する技術が以下の非特許文献に記載されている。
［非特許文献１］  http://www.3gpp.org
［非特許文献２］  http://www.3gpp2.org
［非特許文献３］  3GPP、第三世代パートナーシッププロジェクト；テクニカルスペシフィケーション・コアネットワーク；移動体応用部（MAP）仕様（１９９９年リリース）、２０００年、テクニカルスペシフィケーション3G  TS  29.002  V3.7.0（２０００年１２月）
［非特許文献４］  3GPP、第三世代パートナーシッププロジェクト；テクニカルスペシフィケーション・グループコアネットワーク；移動体無線インターフェース層３仕様；１９９９年、２０００年リリースの3G  TS  24.008バージョン3.6.0のためのコアネットワークプロトコルステージ３（２０００年１２月）
［非特許文献５］  3GPP、第三世代パートナーシッププロジェクト；テクニカルスペシフィケーション・グループサービス・システムの特徴；第三世代セキュリティ；セキュリティアーキテクチャ、２０００年、テクニカルスペシフィケーション3G  TS  33.102  V3.7.0（２０００年１２月）
［非特許文献６］  3G  TS  33.105、第三世代セキュリティ；暗号アルゴリズム要件
［非特許文献７］  3G  TS  35.205、第三世代セキュリティ；MILENAGEアルゴリズムセットの詳細；3GPP認証とキー生成関数f1、f1*、f2、f3、f4、f5、f5*のアルゴリズムセット例；文書１：概論
［非特許文献８］  3G  TS  35.206、第三世代セキュリティ；MILENAGEアルゴリズムセットの詳細；3GPP認証とキー生成関数f1、f1*、f2、f3、f4、f5、f5*のアルゴリズムセット例；文書２：アルゴリズムの詳細
［非特許文献９］  中国の無線通信規格；第三世代デジタル携帯電話通信システム；セキュリティに関するネットワークの機能（リリース３）；CWTS  TSM  03.20  V3.0.0  （２００２年８月）
［非特許文献１０］  3GPP、第三世代パートナーシッププロジェクト；テクニカルスペシフィケーション・グループサービス・システムの特徴；一般パケット無線サービス（GPRS）；サービス記述；ステージ２、２０００年、テクニカルスペシフィケーション3G  TS  23.060  バージョン3.6.0（２００１年１月）
［非特許文献１１］  ISO/IEC、「情報技術−セキュリティ技術――エンティティ認証――第４部：暗号による監視機能を使用したメカニズム、」ISO/ISE、Tech.  
Rep.  ISO/ISE  9798-4、１９９９年
［非特許文献１２］  Y. B. Lin、Y. K. Chen、「第三世代移動体ネットワークにおける認証信号経路の交通量を軽減する」、IEEE Trans.  Wireless Commun.、２巻、３号、４９３−５０１頁、２００３年５月
［非特許文献１３］  P. V. Orlik  S. S. Rappaport、「一般的なセッション・ドウェル時間分布での無線携帯電話通信における、通信の交通性能と経路保持時間特性のモデル」、IEEE  J. Select. Areas in Commun.、１巻、１６、５号、７８８−８０３頁、１９９８年６月
［非特許文献１４］  Y. Fang、I. Chlamtac、「通信の交通分析と、PCSネットワークのためモビリティモデリング」、IEEE Trans.  Commun.、４７巻、１０６２−１０７２頁、１９９９年７月
［非特許文献１５］  B. H. Soong、J.A. Barria、「通信の交通のモビリティモデリングのための経路保持時間分布のcoxianモデル」、IEEE Comms.  Letters、４巻、１２号、２０００年１２月
［非特許文献１６］  M. F. Neuts、確率論的モデルにおける行列幾何学的解法：アルゴリズム的アプローチ、Johns Hopkins University Press、Baltimore、１９８１年
［非特許文献１８］  http://app.stb.com.sg/asp/tou/tou02.asp
［非特許文献１９］  N. L. Johnson、S. Kotz、統計上の分布、連続的な単変量分布、Wiley、New York  （１９７０年）
［非特許文献２０］  F. P. Kelly、可逆性と確率論的ネットワーク。New York：Wiley、１９７９年
【０００３】
第三世代無線ネットワークの規格となるべき三つの候補、つまり、UMTS［非特許文献１］［非特許文献４］［非特許文献１０］、CDMA2000［非特許文献２］、TD-SCDMA［非特許文献２］はいずれも相互認証法を採用して移動端末（MT/USIM）とサービングネットワーク（SN）の間の確実な通信を保証している［非特許文献５］［非特許文献９］［非特許文献１１］。
【０００４】
位置管理コストを軽減する目的で、ネットワーク全体がいくつかのサービングGPRS支援ノード（SGSN）サービスエリアに区分されている。各々のSGSNエリアはいくつかのルーティングエリア（RA）から構成され、ルーティングエリアがさらにいくつかのセルを含んでいる。MTがRAから新しいRAへと移動したとき、位置更新メッセージがMTから当該RAをカバーしているSGSNへとトリガされる。
【０００５】
図１はUMTSネットワークにおける認証・鍵合意（AKA）のメカニズムを示している。プロトコルはMTとホームロケーションレジスタ/認証センタ（HLR/AuC）との間で共有される永久秘密キー（１２８ビット）に基づいている。このマスターキーはいかなる環境下においても公開されてはならない。AKA手順には二局面がある：認証ベクトル（AV）の分配と、MTとSGSN間の認証とキー確立である。
【０００６】
（認証ベクトルの分配）
あるMTがローミングして、あるSGSNのカバー範囲へと進入したき、当該SGSNはそのMTの正当なレコードを保持しておらず、認証が必要となる。そのため、SGSNは認証データ要求（ADR）を当該MTに固有の国際移動電話加入者識別番号（IMSI）とともに、HLR/AuCへと伝送する。受信したIMSIに基づき、HLR/AuCはHLRデータベースを参照して当該MTに対応するマスターキーKを探し出す。
【０００７】
次に、HLR/AuCはシグナリング・オーバーヘッドを抑制するために、信号１AVのかわりに$K$認証ベクトル（AV）を生成する。生成する毎に、認証関数f1〜f5［非特許文献６］［非特許文献７］［非特許文献８］によりAVが算出される。
【０００８】
AV構造は五つの成分からなる：乱数（RAND）、期待認証応答（XRES）、暗号キー（CK）、整合性キー（IK）、ネットワーク認証トークン（AUTN）である［非特許文献５］。
【０００９】
K個のAVの生成に成功すると、AuCはそれらをSGSNへと返送し、SGSNはK個のAVを当該特定のMTのために保存する。この局面はMTがSGSNエリアへ進入したときだけでなく、認証を必要とするアクションの到着によりAVが確保できないときにも実行されるということに注意を喚起したい。
【００１０】
（認証とキー確立）
認証を必要とするアクション毎にSGSNはAVを一つずつ、先入れ先出し方式で消費する。詳しくは、通話要求（通話発信、呼び出しのどちらか）やルーティングエリア（RA）の位置更新毎に、SGSNはユーザ認証要求（UAR）メッセージとパラメータとしてのi番目（i = 1, 2, ..., K）のAVをMTへ送信する。AVを受信すると、USIMはAUTNの正当性を調べる。
【００１１】
そのために、UEはAUTNから連続番号（SQN）成分を取り出し、X-MAC-Aを算出する。次に、USIMはX-MAC-AとAUTNの中のMAC-A成分を比較し、それらが等しければネットワークは認証される。等しくなければ、MTはUARを、そしてその結果としてネットワークを拒否する。MTがネットワークを認証するプロセスは第二世代と比較して第三世代移動体ネットワークに固有の特徴である。
【００１２】
ネットワークを確認した後、USIMはAV 3G TS33.102が新鮮であること、すなわちAVが過去に使用されていないことを調べる。
【００１３】
それに成功すると、MTは認証応答RESを算出し、それをユーザ認証応答メッセージに含めてSGSNへと送信する。RESがAVに含まれるXRESと同じであれば相互認証が成功し、それに続く確実な通信のためのIKとCKの確立が成功する。
【００１４】
［非特許文献１２］において、LinとChenはメッセージを信号伝達するコストという観点から見た認証プロトコル性能を調査するための解析モデルを提案している。また、ユーザごとにKの値を決定するためのアルゴリズムも提案している。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明の目的は、第三世代無線ネットワークにおける改良型認証プロトコルを提案することである。
【課題を解決するための手段】
【００１６】
本発明の目的と本発明により解決される課題は以下に示す技術的解決により達成される。
【００１７】
サービングGPRS（一般パケット無線サービス）支援ノードにおいて実行される認証方法であって、前記サービングGPRS支援ノードのカバー領域に進入した移動端末について、K(K>1)個の認証ベクトルを、ホームロケーションレジスタ/認証センタから取得し、前記取得した認証ベクトルをメモリに追加し、前記メモリに記憶されている認証ベクトルを先入れ先出し方式で用いて前記移動端末を認証し、前記メモリに記憶されている未使用の認証ベクトルの数がK-b(0≦b≦K-1)以下になったときに、前記移動端末についてさらにK個の認証ベクトルを前記ホームロケーションレジスタ/認証センタから取得する。
【発明を実施するための最良の形態】
【００１８】
これから、TS33.102においても先行の研究においても放置されてきたもう一つの重大な難題を提示する。
【００１９】
イベントという用語を、UARをトリガするイベントを示すものとして、そのイベントが、たとえば通話発信・着信、位置更新等の特定のイベントであることを明言せずに、用いる。
【００２０】
いくつかのイベントの後にAVが全て消費され、それ以後のイベントの到着時にAVが確保できない場合はいつでも、SGSNは認証ベクトル分配手順を実行してHLR/AuCからK個のAVを得る。AVを受信した後にのみMTとSGSNの間の相互認証を継続可能である。そのため、SGSNとHLR/AuCが互いから遠く離れて位置する場合にはイベントは長期の遅延期間の間、待機しなければならない可能性がある。分かり易くするため、この状況の例を挙げてみる。
【００２１】
シンガポール観光局の統計［非特許文献１８］によると、２００４年１月から２００４年９月までのシンガポールへの中国と日本からの訪問者の数はそれぞれ６３７，０００人、４４８，０００人である。また、旅行者の数は継続的な増加傾向にある。そのため、訪問者の母国への通話を求める要求が大幅に増大することが予想される。
【００２２】
図２は、シンガポールを訪れている中国人、オーストラリア人、日本人のMTを認証する際の状況を示している。
【００２３】
ある中国人のMTについて、シンガポールのネットワークの中のSGSNにAVが確保できないときには、SGSNは遠く中国からAVのアレイを入手する。中国に存在するHLR/AuCとシンガポールに存在するSGSNの間の距離が大きいために、この入手過程は、ユーザの交通や移動のパターンの率という感覚からすると大変に長く続く。
【００２４】
ADRを送出した時点からK個のAVを含む応答を受信する時点までの間の長期遅延は、SGSNとHLR/AuCが異なる事業者により運営されている場合にも起こり得る。
【００２５】
長期遅延の結果、通話が出来なかったり位置更新が失敗したりして、サービスの質が低下する。それゆえ、3GPPテクニカルスペシフィケーションTS33.102［非特許文献５］における現在の認証プロトコルを修正して改良型を提案する。
【００２６】
図３は、イベントがその到着時にAVが入手不可能であるためにSGSN内で待機しなければならない確率と定義される待機確率を減らすための改良型認証プロトコルを示す。黒い小型の四角形は、時間軸上のそれぞれの時点においてSGSNに存在するAVの数を表す。第一のイベント時に、当該MTのレコードが存在しないため、第一のADRがSGSNからHLR/AuCへと送出される。このステップはTS33.102と同じである。
【００２７】
SGSNは、(K-b)個のイベントを認証した後に当該MTにはb(0≦b≦K-1)個のAVが残存していることを確認する。SGSNはADRをHLR/AuCへ送信する。ADRの送出から認証データ応答を受信するまでの遅延X2の間、最大b個の認証要求を満足するb個のAVが存在している。
【００２８】
遅延X2の間のイベントの数をM2と表す。M２≦bであれば、全ての要求について認証を行うことが可能である。それに続く(b+1)番目のイベントは、SGSNがHLR/AuCから応答を得るまで待機しなければならない。それ以後、K個のAVと(K-M2)個の認証イベントを受信すると、SGSNは再びb個のAVを保有することになる。そしてSGSNはADRをHLR/AuCへと送信してAVを得る。同じ手順がMTが新たなSGSNサービスエリアに進入するたびに繰り返される。
【００２９】
b = 0であるときにADRがトリガされる瞬間が異なるという点で、我々が提案するスキームと3GPP TS33.102でのオリジナルのメカニズムとは異なる。3GPPにおいては、イベントが到着したとき、SGSNはAVの数を調べ、AVが存在しなければADRが送出される。これに比較して、我々のスキームでは、SGSNはイベントを認証した後にAVの数を調べ、ゼロであればADRがトリガされる。3GPPではイベント到着後にAVを取得するのに対し、この修正によりわれわれの方法ではイベント到着前にAVを取得するので、待機確率を減少させることができる。
【００３０】
本実施形態において、SGSNにおいて実行される提案する認証方法は、以下に示すものを含む。
【００３１】
SGSNのカバー領域に進入したMTについて、K  (K>1)個のAVを、HLR/AuCから取得する第一取得ステップ、
【００３２】
取得したAVをメモリに追加する追加ステップ、
【００３３】
メモリに記憶されているAVを先入れ先出し方式で用いてMTを認証する認証ステップ、
【００３４】
メモリに記憶されている未使用のAVの数がK-b(0≦b≦K-1)以下になったときに、MTについてさらにK個のAVをHLR/AuCから取得する第二取得ステップ。
【００３５】
（性能分析）
MTがSGSNサービスエリアに滞留しているときのイベントの数をEと表す。また、この期間におけるSGSNからHLR/AuCへのADRの数をNとする。Nが大きいほど、SGSNとHLR/AuC間の信号伝達交換や、HLRデータベースの参照や、AVアレイの生成が頻繁であり、それゆえシグナリング・オーバーヘッドが大きい。これ以降、Nの期待値は認証プロトコルにおけるシグナリング・オーバーヘッドを反映することができるものとする。
A.  Nの期待値
【００３６】
SGSN内のMTについての無効なレコードのために、MTがSGSNのカバー領域に進入したに直後に、SGSNはHLR/AuCへADRを送信しなければならないため、少なくとも一つのADRが存在している。
【００３７】
図３は、イベントの数が(K-b)以下であるときにNが1である状態を示している。
【００３８】
N=n>1である場合、イベントの数はE=(K-b)+(n-2)K+kであり、この式において、成分(K-b)は一番目と二番目のADRの間のイベントの数を表し、第二の成分(n-2)Kは二番目とn番目のADRの間のイベントの数を表し、kはn番目のADR後かつ(n+1)番目のADR前に起こりうるイベントを表している。
【００３９】
それゆえ、確率変数Nの分布を以下のように表す。
【数１】
2007019752.tif 000003
【００４０】
SGSNへ到着する認証を必要とするイベントの総体を、到着率がlのポアソン過程であると想定する。
【００４１】
MTがSGSNサービスエリア内に在留している時間分をSGSN在留時間という用語で表す。TSGSNとTSGSNがそれぞれ、平均1/mであるSGSN在留時間、確率密度関数（pdf）fTSGSN(t)を表し、そのラプラス変換（LT）をfTSGSN*(s)であるとする。期間TSGSNの間にE個のイベントが存在する確率は、
【数２】
2007019752.tif 000004
により与えられる。
【００４２】
但し、fTSGSN(E)(s)は、sについてのfTSGSN*(s)の、E番目の微分を表す。
【００４３】
［数２］を［数１］に代入して正規化制約を考慮に入れると、最終的に以下に示すようなNの分布を得る。n=1の場合、
【数３】
2007019752.tif 000005
【００４４】
n>1の場合、
【数４】
2007019752.tif 000006
【００４５】
式の定義に従うと、SGSN在留時間におけるあるMTのADRの期待数は、
【数５】
2007019752.tif 000007
により与えられる。
【００４６】
［数３］、［数４］、［数５］を観察すると、f(E)がNの期待値を算出する上での中心的要素であることがわかる。平均が1/m、分散がVにおいてガンマ分布したSGSN在留時間についてのpdfのLTは、
【数６】
2007019752.tif 000008
である。
【００４７】
この場合、［数２］のφ(E)は、
【数７】
2007019752.tif 000009
となる。
【００４８】
［数７］においてμ2V=1と設定すると、SGSN在留時間についてのφf(E)の指数関数を、
【数８】
2007019752.tif 000010
のように得る。
【００４９】
［非特許文献１６］における相型（PH）分布は重要な特徴をいくつか有している：
【００５０】
（１）負でない確率変数のどのような分布でもPHでランダムに近似することが出来る；
【００５１】
（２）［非特許文献１９］の指数アーラン、［非特許文献１５］の超指数とcoxian、［非特許文献１４］［非特許文献２０］の超アーランのそれぞれの分布はすべてPH分布の特殊ケースである；
【００５２】
（３）大抵の数値操作は行列的操作に還元される。aと次数１のUを用いて表されたPH分布のSGSN在留時間について、pdfとそのラプラス変換を表すと、
【数９】
2007019752.tif 000011
である。
【００５３】
但し、αは大きさが１である行ベクトルであり、1×1の行列Uは対角線上に負の要素を有し、対角線外に正の要素を有する正則行列であり、1×1のベクトルeはコンテクストに基づいた適切な大きさを有する列ベクトルを表している。この場合、f(E)の確率生成関数は、
【数１０】
2007019752.tif 000012
により与えられる。
【００５４】
それゆえ、離散PH分布とその確率生成関数の関係に基づくと［非特許文献１６］、この場合のf(E)は、(g, S)で表される離散PH分布である。但し、
【数１１】
2007019752.tif 000013
である。
【００５５】
そして、この離散PH分布の確率質量関数は、
【数１２】
2007019752.tif 000014
である。
【００５６】
α=1、U=-μであるとき、すなわち、SGSN在留時間が指数分布に従う場合、［数１２］は［数８］に還元される。
B.  待機確率
【００５７】
Xi（i=1, 2, ...）とMi（i=1, 2, ...）を一般化してそれぞれX、Mと表す。
【００５８】
M≦bであるときには、SGSN内に確保可能なAVが存在するので、全てのイベントはSGSN内で待機することなく即座にチャレンジ−レスポンスを実行することができる。期間Xにおいて、SGSN内のMTについてのb個のAVが全て使い尽くされたとき、それに続く(b+1)番目のイベントは、SGSNがHLR/AuCから認証のためのAVアレイを受信するまで待機しなければならない。
【００５９】
(b+1)番目のイベントがAVを待機している間、認証を必要とする後続のアクションはないものと想定する。このMTは通話または位置更新に拘わっている最中のMTであるので、この想定は妥当である。結果的に、期間Xにおけるイベントの最大数はb+1までである。
【００６０】
イベントがその到着時にAVが確保できないためにSGSN内で待機しなければならない待機確率をbによって表す。到着したイベントがSGSN内でAVを待機しなければならないという状況は、期間Xにおいてb+1個のイベントが存在するという状況と等価である。
【数１３】
2007019752.tif 000015
【００６１】
但し、b0は正規化定数であり、
【数１４】
2007019752.tif 000016
により与えられる。
【００６２】
［数１４］において、確率Pr(M=m)は、
【数１５】
2007019752.tif 000017
と表される。
【００６３】
［数１５］を［数１３］と［数１４］に代入すると、
【数１６】
2007019752.tif 000018
が得られる。
【００６４】
平均1/η、分散Vxにおいてガンマ分布したXの場合、待機確率［数１６］は、
【数１７】
2007019752.tif 000019
となる。
【００６５】
［数１７］においてVx=1/η2と設定することにより、指数関数の場合の待機確率、
【数１８】
2007019752.tif 000020
を得る。
【００６６】
pdfを有する、PH分布した次数lxの遅延X、
【数１９】
2007019752.tif 000021
について、
【００６７】
確率関数を、
【数２０】
2007019752.tif 000022
のように得る。
【００６８】
［非特許文献５］のオリジナルの規格TS33.102においては、イベントが即座に入手不可能なAVを待機しなければならない確率は、
【数２１】
2007019752.tif 000023
により与えられる。
【００６９】
（数値結果）
ここで、代表的な例を提示して待機確率特性とシグナリング・オーバーヘッドを説明する。
【００７０】
特に明言しない場合、SGSN在留時間TSGSNは、平均１／μ、分散Ｖ＝１．５×（１／μ^２）のガンマ分布に従うものとする。SGSNとHLR/AuC間の遅延Xは、平均１／η、分散ＶＸ＝１．５×（１／η∧２）＄においてガンマ分布する。
【００７１】
［非特許文献３］の推奨値K=5を採用する。
【００７２】
図４は、異なる遅延期間でのbに対する待機確率bを示している。3GPPにおいては遅延問題を解決するための格別なメカニズムを採用していないので、イベントの待機確率は1/K=20%の高率で固定されている。
【００７３】
我々の提案するスキームでは、b=0の場合でさえも待機確率をオリジナルのプロトコルよりも減少させることができる。これは、上述したように、我々のスキームではADRがトリガされる瞬間が異なることによる。この結果は、様々な状況下で、b=1であれば十分に待機確率を２％未満に減少させることができることを示している。
【００７４】
図５は、Xの分散を異ならせた場合の、bに対する待機確率を示している。より具体的には、VX=1/μ2の曲線が指数関数の場合であり、Vx=0.5/μ2の直線がXのアーラン分布である。さらにこれらの結果は、実用の場面では、待機確率を減少させるためにbの値を非常に大きくする必要はないということを証明している。bは１に等しくてよいということが示唆されている。
【００７５】
図６は、lに対するλの期待値を示している。ここでの比較は、われわれの認証プロトコルスキームによるシグナリング・オーバーヘッドの増加は重大なものでないことを証明している。本出願においては提示していない指数関数分布のSGSN在留時間及び/またはSGSNとHLR/AuC間の遅延についても実験し、類似した結果を観察した。
【００７６】
SGSNにおいて実際に実施するための方法が二通りある。第一の方法は非常に簡単で、bを定数１に設定する方法であり、これにより、証明されたとおり、シグナリング・オーバーヘッドが微増するが実質的に待機確率を減少させることができる。第二の方法では、MTがローカルサービスエリア、かつMTが登録したネットワークに在留しているときには、bをゼロに設定する。MTがHLR/AuCから離れた位置に移動したとき、たとえば国際ローミングしているときには、bを１に設定する。
【００７７】
3GPPテクニカルスペシフィケーションTS33.102においては、認証・鍵合意（AKA）をトリガするアクションがAVを待機しなければならない確率は２０％もの高率に固定されている。われわれの提案するスキームによると、シグナリング・オーバーヘッドが無視してよい程度に微増するだけで、この確率を２％未満にすることができる。
【００７８】
本出願において、HLR/AuCからSGSNへの応答が潜在的に長くなってしまうという課題に対処するための、次世代無線ネットワーク認証プロトコルの新しいメカニズムを提案した。我々のスキームは、シグナリング・オーバーヘッドの微増を許容してしまうが、3GPP TS33.102の方法と比較して非常に低い待機確率を達成できる。
【図面の簡単な説明】
【００７９】
【図１】図１は、UMTSネットワークにおける認証・鍵合意（AKA）メカニズムの概略図である。
【図２】図２は、シンガポールを訪問している中国人、オーストラリア人、日本人のMTを認証する際の状況を示す概略図である。
【図３】図３は、改良型認証プロトコルの概略図である。
【図４】図４は、異なる遅延期間でのbに対する待機確率βを示す概略図である。
【図５】図５は、Xの分散を異ならせた場合の、bに対する待機確率を示す概略図である。
【図６】図６は、λに対するNの期待値を示す概略図である。
【図１】
2007019752.tif 000024
【図２】
2007019752.tif 000025
【図３】
2007019752.tif 000026
【図４】
2007019752.tif 000027
【図５】
2007019752.tif 000028
【図６】
2007019752.tif 000029
【外国語明細書】
A Method for Authentication in the Third-Generation Wireless Networks
Field of Invention
[0001]   The present invetion relates to a method for authentication in the third-generation wireless network, specially an improvement for the mutual authentication to address the potential long delay in waiting for authentication vector (AV)when SGSN (servicing GPRS(General Packet Radio Service) supporting node)and HLR/AuC (home location register/authentication center) locate far away from each other, or when the two entities are operated by different operators, or when the Mobile Terminal (MT) call/mobility activity is frequent.  
Description of the Related Art
[0002]   Various mechanisms for the next generation wireless networks authentication are proposed in the recent years.  For example, the technologies for authentication protocol in the third-generation wireless networks are described in:
[Doc.1] http://www.3gpp.org
[Doc.2] http://www.3gpp2.org
[Doc.3] 3GPP, 3rd Generation Partnership Project; Technical Specification Core Network; Mobile Application Part (MAP) Specification (Release 1999), 2000, Technical Specification 3G TS 29.002 V3.7.0(2000-12).  
[Doc.4] 3GPP, 3rd Generation Partnership Project; Technical Specification Group Core Network; Mobile Radio Interface Layer 3 Specification;Core Network Protocols Stage 3 for Release 1999, 2000, 3G TS 24.008 version 3.6.0 (2000-12).  
[Doc.5] 3GPP, 3rd Generation Partnership Project; Technical Specification Group Services and Systems Aspects; 3G Security; Security Architecture, 2000, Technical Specification 3G TS 33.102 V3.7.0(2000-12).  
[Doc.6] 3G TS 33.105, 3G Security; Cryptographic Algorithm Requirements.  
[Doc.7] 3G TS 35.205, 3G Security; Specification of the MILENAGE Algorithm Set: An Example Algorithm Set for the 3GPP Authentication and Key Generation Functions f1, f1*, f2, f3, f4, f5, and f5*; Document 1:General.  
[Doc.8] 3G TS 35.206, 3G Security; Specification of the MILENAGE Algorithm Set: An Example Algorithm Set for the 3GPP Authentication and Key Generation Functions f1, f1*, f2, f3, f4, f5, and f5*; Document 2:Algorithm Specification.  
[Doc.9] China Wireless Telecommunication Standard; 3G digital cellular telecommunications system; Security related network functions(Release 3); CWTS TSM 03.20 V3.0.0 (2002-08).  
[Doc.10] 3GPP, 3rd Generation Partnership Project; Technical Specification Group Services and Systems Aspects; General Packet Radio Service(GPRS); Service Descripton; Stage 2, 2000, Technical Specification 3G TS 23.060 version 3.6.0 (2001-01).  
[Doc.11] ISO/IEC, "Information technology-security techniques -- Entity authentication -- Part 4: Mechanisms using a cryptographic check function," ISO/IEC, Tech.  Rep.  ISO/IEC 9798-4, 1999.  
[Doc.12] Y.  B.  Lin and Y.  K.  Chen, "Reducing authentication signaling traffic in third-generation mobile network", IEEE Trans. Wireless Commun., vol.2, no.3, pp.493-501, May 2003.  
[Doc.13] P.  V.  Orlik and S.  S.  Rappaport, "A model for teletraffic performance and channel holding time characterization in wireless cellular communication with general session and dwell time distributions", IEEE J. Select. Areas in Commun., vol.  16, no.5, pp.  788-803, Jun 1998.  
[Doc.14] Y.  Fang and I.  Chlamtac, "Teletraffic analysis and mobility modeling for PCS networks," IEEE Trans. Commun., vol.  47, pp.  1062-1072, July 1999.  
[Doc.15] B.  H.  Soong and J.  A.  Barria, "A coxian model for channel holding time distribution for teletraffic mobility modeling", IEEE Comms. Letters, vol.4, no.12, Dec 2000.  
[Doc.16] M.  F.  Neuts, Matrix geometric soluctions in stochastic model: an algorithmic approach. Johns Hopkins University Press, Baltimore, 1981.  
[Doc.18] http://app.stb.com.sg/asp/tou/tou02.asp
[Doc.19] N.  L.  Johnson and S.  Kotz, Distributions in Statistics, Continuous Univariate Distributions, Wiley, New York (1970).  
[Doc.20] F.  P.  Kelly, Reversibility and Stochastic Networks.  New York: Wiley, 1979.  
[0003]   All three standard candidates for the third-generation wireless networks, UMTS [Doc.1] [Doc.4] [Doc.10], CDMA2000 [Doc.2] and TD-SCDMA [Doc.2], employ the mutual authentication to ensure the secure communication between Mobile Terminal (MT/USIM) and Serving Network (SN) [Doc.5] [Doc.9] [Doc.11].  
[0004]   For the sake of reducing the location management cost, the whole networks is partitioned into several Serving GPRS Support Node(SGSN) service area.  Each SGSN area is comprised of several routing area (RA), which further includes a few cells.  When an MT moves from RA to a new RA, a location update message is triggered from the MT to the SGSN covering the RA.  
[0005]   Fig.1 shows the Authentication and Key Agreement(AKA) mechanism in UMTS network.  The protocol is based on a permanent secret key K (128-bit) that is shared between the MT and the Home Location Register/Authentication Center(HLR/AuC).  This master key must not be exposed under any environment.  There are two phases in the AKA procedure:Distribution of Authentication Vector (AV) and Authentication and Key Establishment between the MT and SGSN.  
[0006]     (Distribution of Authentication Vector)
When an MT roams into the coverage of an SGSN, the SGSN has no valid record for the MT and the authentication is needed.  For this, the SGSN will delivery an Authentication Data Request (ADR) to the HLR/AuC with the MT's unique International Mobile Subscriber Identity (IMSI).  Based on the received IMSI, HLR/AuC lookups the HLR database and find the according master key K for the particular MT.  
[0007]   Then, HLR/AuC generates $K$ Authentication Vector (AV) instead of single one AV for the sake of saving signaling overhead.  For each generation, an AV is calculated by means of the authentication function f1-f5 [Doc.6] [Doc.7] [Doc.8].  
[0008]   The AV structure is comprised of five components: a random number (RAND), an expected authentication response (XRES), a cipher key (CK), an integrity key (IK) and a network authentication token (AUTN) [Doc.5].  
[0009]   After successfully generating K AVs, AuC sends back them to the SGSN, which saves the K AVs for the particular MT.  It is noteworthy that this phase executes not only upon MT entering SGSN area, but when there is no AVs available upon an action arrival which requires authentication.  
[0010]     (Authentication and Key Establishment)
For each action requesting authentication, SGSN consumes one AV in the FIFO manner.  Specifically, for each call request (either call origination or paging) and Routing Area (RA) location update, the SGSN initiates the User Authentication Request (UAR) message to the MT with the i-th (i=1, 2, ..., K) AV as parameter.  Upon receiving the AV, the USIM checks the validity of AUTN.  
[0011]   For this goal, the UE retrieves the sequence number (SQN) component from AUTN and calculates X-MAC-A.  The USIM then compares X-MAC-A and MAC-A component in AUTN, if they are equal to each other, the network is verified.  Otherwise, the MT rejects the UAR and consequently the network.  The process that MT verifies network is a particular characteristics of the third-generation mobile networks in comparison with the second-generation.  
[0012]   After the network is identified, the USIM checks the freshness of AV 3GTS33.102, i.e.  the AV has never been used before.  
[0013]   When succeeds, the MT computes the authentication response RES and sends it in a User Authentication Response message to the SGSN.  If RES equals to the expected response XRES stored in the AV, the mutual authentication is successful, and the IK and CK for subsequent secure communication are successfully established.  
[0014]   In [Doc.12], Lin and Chen propose an analytical model to investigate the authentication protocol performance in terms of the signaling message cost.  An algorithm is also suggested to determine the value of K on the per-user basis.  
Summary of Invention
[0015]   The object of the present invention is to propose an improved authentication protocol in the third-generation wireless networks.  
[0016]   The objects of and problems to be solved by the present invention are achieved with the following techmical solution.  
[0017]   An authentication method executed in a serving GPRS (General Packet Radio Service) support node, fetching from a home location register/authentication center, K (K>1) authentication vectors for a mobile terminal entering into the coverage area of the serving GPRS support node, adding the fetched authenticaion vectors to a memory, authenticating the mobile terminal using an authentication vector stored in the memory in FIFO manner, fetching further K authentication vectors for the mobile terminal from the home location register/authentication center when the number of the unused authentication vectors stored in the memory is less than or equal to K-b (0≦b≦K-1).  
Brief Description of Drawings
[0018]   Fig.1 is  a schematic graph for the authentication and key agreement(AKA) mechanism in UMTS network.  
[0019]   Fig.2 is  a schematic graph for the condition when authenticating a Chinese/Austrilian/Japanese MT visiting Singapore.  
[0020]   Fig.3 is  a schematic graph for the improved authentication protocol.  
[0021]   Fig.4 is  a schematic graph for the waiting probability β in terms of b with different delay.  
[0022]   Fig.5 is  a schematic graph for the waiting probability with respect to b under different variance of X.  
[0023]   Fig.6 is  a schematic graph for the expectation of N in terms of λ.  
Detailed Description
[0024]   Now we will present another significant challenge which is neglected in the TS33.102 as well as in the previous studies.  
[0025]   We will use the term event to represent any events triggering UAR without specifying the particular event, e.g.  call origination/termination or location update.  
[0026]   Whenever all AVs are used up after several events and there is no AV available upon the moment of a subsequent event arrival, SGSN will execute Distribution of Authentication Vector procedure to fetch K AVs from HLR/AuC.  Only after receiving the AVs, the mutual authentication between MT and SGSN is able to continue.  As a consequence, an event may have to wait for a potential long delay when SGSN and HLR/AuC locates far away from each other.  For clearance, we describe an example for this situation.  
[0027]   Referring to the statistics in Singapore Tourism Board[Doc.18], the number of visitors from China and Japan to Singapore between Jan.2004 and Sep.2004 is 637000 and 448000, respectively.  Moreover, the number of travellers is in the continuously increasing trend.  Hence, it is envisioned that the request to call back to a visitor's homeland will increase significantly.  
[0028]   Fig.2 illustrates the condition when authenticating a Chinese/Austrilian/Japanese MT visiting Singapore.  
[0029]   For a specific Chinese MT, whenever there is no AV in the SGSN in Singapore network, it will retrieve an array of AV from remote China.  This retrieval may last very long in the sense of the rate of the user's traffic and mobility pattern due to the long distance between HLR/AuC in China and the SGSN in Singapore.  
[0030]   Note that the long delay from the epoch sending out ADR to the instant receiving the response with K AVs can also occur when SGSN and HLR/AuC are operated by different operators.  
[0031]   The consequence of long delay includes call blocking and location update failure, and hence degraded Quality of Service.  For this, we modify and propose an improvement for the current authentication protocol in 3GPP Technical Specification TS33.102[Doc.5].  
[0032]   Fig.3 depicts the improved authentication protocol in order to reduce the waiting probability, defined as the probability that an event has to wait in SGSN due to unavailable AV upon its arrival.  The black small box represents the number of AVs in SGSN at the corresponding instant in the time axis.  In the first event, since there is no record for this MT, the first ADR issues from SGSN to HLR/AuC.  This step is same as TS33.102.  
[0033]   After authenticating (K-b) events, SGSN finds that there are b (0 ≦ b ≦ K-1) AVs left for the MT.  SGSN sends ADR to HLR/AuC.  During the delay X2, from ADR sending out to the moment of receiving Authentication Data Response, there are b AVs to satisfy maximal b authenticating request.  
[0034]   We denote the number of events during X2 as M2.  If M2 ≦ b, all the requests can be authenticated.  For the subsequent (b+1)stevent, it has to wait until the SGSN receives response from HLR/AuC.  Subsequently, after receiving K AVs and authentication (K-M2) events, SGSN has b AVs again.  SGSN will then send ADR to HLR/AuC to obtain AVs.  The same procedure is repeated whenever MT enters a new SGSN service area.  
[0035]   It is noteworthy that, when b=0, our scheme is not identical as the original mechanism in 3GPP TS33.102 since the instants of triggering ADR are different.  In 3GPP, after an event's arrival, the SGSN will check the number of AVs.  If no AVs are available, ADR is sent out.  Comparatively, in our scheme, SGSN checks the number of AVs right after authenticating an event.  If it is zero, ADR is triggered.  This modification is able to reduce the waiting probability since we retrieve AV before event arrival while 3GPP fetches AV after event arrival.  
[0036]   In this embodiment, the proposed authentication method executed in a SGSN comprising:
[0037]   a first fetching step for fetching from a HLR/AuC, K (K>1) AVs for a MT entering into the coverage area of the SGSN, 
[0038]   an adding step for adding the fetched AVs to a memory, 
[0039]   an authenticating step for authenticating the MT using an AV stored in the memory in FIFO manner, 
[0040]   a second fetching step for fetching further K AVs for the MT from the HLR/AuC when the number of the unused AVs stored in the memory is less than or equal to K-b (0≦b≦K-1).  
[0041]     (Performance Analysis)
Denote the number of events as E when an MT stays in an SGSN service area.  And, during this period, let N be the number of ADR request from SGSN to HLR/AuC.  Larger N shows that the signaling exchange between SGSN and HLR/AuC, the HLR database lookup and AV array generation are more frequent, and hence heavier signaling overhead.  Thereafter, the expected value of N is able to reflect the signaling overhead in the authentication protocol.  
A.  Expectation of N
[0042]   It is seen that there are at least one ADR since SGSN must send ADR to HLR/AuC right after the MT enters its coverage due to the invalid record for the MT in SGSN.  
[0043]   Fig.3 indicates that N is equal to 1 when the number of events is no more than (K-b).  
[0044]   In case of N=n > 1, the number of events is E=(K-b)+(n-2)K+k, where the component (K-b) accounts for the number of events between the first and the second ADR, the second item (n-2)K represents the number of events between the second and the n-th ADR and k stands for the possible events after the n-th ADR and before (n+1)-th ADR.  
[0045]   Hence, we express the distribution for the random variable N as follows.  
[Math.1]
2007019752.tif 000030
[0046]   We assume the aggregate events to SGSN requiring authentication as Poisson process with arrival rate λ.  
[0047]   The time duration an MT stays in a SGSN service area is termed as the SGSN residence time.  Let TSGSN and tSGSN denote the SGSN residence time with mean 1/μ, probability density function (pdf) fTSGSN(t) and its Laplace transform (LT) fTSGSN*(s).  The probability that there are E events during the period TSGSN is given by
[Math.2]
2007019752.tif 000031
[0048]   where fTSGSN(E)(s) represents the E-th derivatives of fTSGSN*(s) with respect to s.  
[0049]   Substituting [Math.2] into [Math.1] and taking into account the normalization constraint, we finally obtain the distribution for N as follows.  For n=1, 
[Math.3]
2007019752.tif 000032
[0050]   For n>1, 
[Math.4]
2007019752.tif 000033
[0051]   Following the formal definition, The expected number of ADR for an MT during the SGSN residence time is given by
[Math.5]
2007019752.tif 000034
[0052]   Observing [Math.3] [Math.4] and [Math.5], we can see that φ(E) is the core item to compute the expectation of N.  For the Gamma distributed SGSN residence time with mean 1/μ and variance V, and LT of pdf
[Math.6]
2007019752.tif 000035
[0053]   In this case, φ(E) in [Math.2] becomes
[Math.7]
2007019752.tif 000036
[0054]   By setting μ2V=1 in [Math.7], we obtainφ(E) for the exponential SGSN residence time as
[Math.8]
2007019752.tif 000037
[0055]   Phase-type (PH) distribution [Doc.16] has several significant characteristics:
[0056]   (1) any distribution of a non-negative random variable can be randomly approximated by PH;
[0057]   (2) the exponential, Erlang [Doc.19], hyper-exponential, coxian [Doc.15] and hyper-Erlang [Doc.14] [Doc.20] distribution are all special cases of PH distributions;
[0058]   (3) most numerical integrations are reduced to matrix manipulations.  For PH distributed SGSN residence time with representation α, U of order l, pdf and its Laplace transform
[Math.9]
2007019752.tif 000038
[0059]   where α is row vector of size l, l×l matrix U is nonsingular with negative diagonal elements and nonnegative off-diagonal elements, l×1 vector e denotes the column vector of ones with the appropriate dimension depending on the context.  In this case, the probability generation function of φ(E) is given by
[Math.10]
2007019752.tif 000039
[0060]   Hence, based on the relationship between the discrete PH distribution and its probability generation function[Doc.16], φ(E) in this case is a discrete PH distribution with representation(γ,S) where
[Math.11]
2007019752.tif 000040
[0061]   And its probability mass function
[Math.12]
2007019752.tif 000041
[0062]   When α=1 and U=-μ, i.e.  SGSN residence time follows the exponential distribution, [Math.12] reduces to [Math.8].  
B.  Waiting probability
[0063]   We denote the generic form of Xi (i=1, 2, ...) and Mi (i=1, 2, ...) as X and M, respectively.  
[0064]   When M≦b, all the events will not wait in SGSN and can execute the challenge-and-response instantly since there are available AV in the SGSN.  When all of the b AVs are used up in the SGSN for the MT during the duration X, the subsequent (b+1)-st event has to wait until SGSN receives the AV array from HLR/AuC for authentication.  
[0065]   When the (b+1)-st event is waiting for AV, we assume that there is no subsequent action triggering authentication.  This assumption is reasonable, since an MT is when an MT is involved in a call or location update.  As a consequence, the maximum number of events during X can be up to b+1.  
[0066]   We denote the waiting probability by β that an event has to wait in SGSN due to unavailable AV upon its arrival.  The situation that an arriving event has to wait for an AV in SGSN is equivalent to the condition that there are b+1 number of events in the period X.  
[Math.13]
2007019752.tif 000042
[0067]   where β0 is the normalization constant and give by
[Math.14]
2007019752.tif 000043
[0068]   In [Math.14], the probability Pr(M=m) is expressed as
[Math.15]
2007019752.tif 000044
[0069]   Substituting [Math.15] into [Math.13] and[Math.14], we have
[Math.16]
2007019752.tif 000045
[0070]   In case of Gamma distributed X with mean 1/η and variance Vx, the waiting probability [Math.16] becomes
[Math.17]
2007019752.tif 000046
[0071]   By setting Vx=1/η2 in [Math.17], we obtain the waiting probability in the exponential case
[Math.18]
2007019752.tif 000047
[0072]   For PH distributed delay X of order lx with pdf
[Math.19]
2007019752.tif 000048
[0073]   We obtain the waiting probability as
[Math.20]
2007019752.tif 000049
[0074]   In the original standard TS33.102 [Doc.5], the probability that an event has to wait for an AV without an instant availability is given by
[Math.21]
2007019752.tif 000050
[0075]     (Numerical Results)
Here, we will present the representative examples to illustrate the waiting probability characteristics as well as signaling overhead.  
[0076]   If not specified, SGSN residence timeTSGSN follows the Gamma distribution with mean 1/μ and variance V=1.5×(1/μ^2).  The delay X between SGSN and HLR/AuC is Gamma distributed with mean 1/η and variance Vx=1.5×(1/η^2)$.  
[0077]   We employ the recommended value K=5 in [Doc.3].  
[0078]   Fig.4 shows the waiting probability β in terms of b with different delay.  Since no specific mechanism is employed to resolve the delay problem in 3GPP, the waiting probability for an event is fixed as high as 1/K=20％.  
[0079]   With our proposed scheme, even b=0 is able to decrease the waiting probability as compared to the original protocol.  This is due to the different time instant in triggering ADR in our scheme as explained above.  The result indicates that b=1 is sufficient to reduce the waiting probability to lower than 2％ under different scenarios.  
[0080]   Fig.5 illustrates the waiting probability with respect to b under different variance of X.  More specifically, the curve with Vx= 1/μ2 is the exponential case and the line with Vx=0.5/μ2 is the Erlang distributed X.  The results further demonstrate that the much greater value of b is not necessary in practice to decrease the waiting probability.  It is suggested b is equal to 1.  
[0081]   Fig.6 shows the expectation of N in terms of λ.  The comparison demonstrates that the increased signaling overhead due to our introduced scheme for authentication protocol is insignificant.  We have examined and observed the similar results under exponentially distributed SGSN residence time and/or delay between SGSN and HLR/AuC, which is not presented in this application.  
[0082]   There are two ways for the practical implementation in SGSN.  The first one is very simple by setting b as a constant equal to 1, which, as demonstrated, can substantial reduce the possibility of waiting with minor increased signaling overhead.  In the second method, when the MT is staying in the local service area and the same network as the registered one, b is set to be zero.  As the MT moves into a far location from HLR/AuC, e.g.  international roaming, b is set to one.  
[0083]   In the 3GPP Technical Specification TS33.102, the probability that an action triggering Authentication and Key Agreement (AKA) has to wait for an AV is fixed as high as 20％.  Our proposed scheme is able to achieve this probability lower than 2％ with negligible increased signaling overhead.  
[0084]   In this application, a new mechanism for the next generation wireless networks authentication protocol is proposed to address the challenge as the response from HLR/AuC to SGSN is potentially long.  Comparing with the strategy in 3GPP TS33.102, our scheme is able to achieve very small waiting probability with minor increased signaling overhead.  
1.  An authentication method executed in a serving GPRS (General Packet Radio Service) support node, comprising:
a first fetching step for fetching from a home location register/authentication center, K (K>1) authentication vectors for a mobile terminal entering into the coverage area of the serving GPRS support node, 
an adding step for adding the fetched authenticaion vectors to a memory, 
an authenticating step for authenticating the mobile terminal using an authentication vector stored in the memory in FIFO manner, 
a second fetching step for fetching further K authentication vectors for the mobile terminal from the home location register/authentication center when the number of the unused authentication vectors stored in the memory is less than or equal to K-b (0≦b≦K-1).  
An authentication method executed in a serving GPRS (General Packet Radio Service) support node, fetching from a home location register/authentication center, K (K>1) authentication vectors for a mobile terminal entering into the coverage area of the serving GPRS support node, adding the fetched authenticaion vectors to a memory, authenticating the mobile terminal using an authentication vector stored in the memory in FIFO manner, fetching further K authentication vectors for the mobile terminal from the home location register/authentication center when the number of the unused authentication vectors stored in the memory is less than or equal to K-b (0≦b≦K-1).  
【図1】
2007019752.tif 000051
【図2】
2007019752.tif 000052
【図3】
2007019752.tif 000053
【図4】
2007019752.tif 000054
【図5】
2007019752.tif 000055
【図6】
2007019752.tif 000056