(57)【特許請求の範囲】
【請求項１】
複数のデバイスを含むシステムで情報を認証する方法であって、前記デバイスのそれぞれは、他のデバイスの１つまたは複数と通信するように適合可能であり、前記方法は、
前記複数のデバイスの第１デバイスにおいて、該第１デバイスに関連する第１パスワードの第１共有および第２共有を生成するステップと、
前記第１共有および前記第２共有を、それぞれ、前記複数のデバイスの第２デバイスおよび第３デバイスに記憶するステップと
を具え、
前記第２デバイスおよび前記第３デバイスの少なくとも１つへの前記第１デバイスに関連する追加情報のサブミットの時に、前記第１共有および前記第２共有の各々は、前記追加情報の前記第１パスワードとの対応だけから判定することが実行不可能であるという特性を有する要素を含み、
前記第２デバイスおよび前記第３デバイスは、前記各々の第１共有および第２共有を使用して、前記追加情報の前記第１パスワードとの前記対応を判定し、
前記追加情報は、前記第１共有および前記第２共有に関連した認証するために使用される第３共有および第４共有を含み、
前記第３共有は、前記第１デバイスによって前記第２デバイスに配信され、
前記第４共有は、前記第１デバイスによって前記第３デバイスに配信されることを特徴とする方法。
【請求項２】
複数のデバイスを含むシステムで情報を認証する方法であって、前記デバイスのそれぞれは、他のデバイスの１つまたは複数と通信するように適合可能であり、前記方法は、
前記複数のデバイスの第１デバイスにおいて、該第１デバイスに関連する第１パスワードの第１共有および第２共有を生成するステップと、
前記第１共有および前記第２共有を、それぞれ、前記複数のデバイスの第２デバイスおよび第３デバイスに記憶するステップと
を具え、
前記第２デバイスおよび前記第３デバイスの少なくとも１つへの前記第１デバイスに関連する追加情報のサブミットの時に、前記第１共有および前記第２共有の各々は、前記追加情報の前記第１パスワードとの対応だけから判定することが実行不可能であるという特性を有する要素を含み、
前記第２デバイスおよび前記第３デバイスは、前記各々の第１共有および第２共有を使用して、前記追加情報の前記第１パスワードとの前記対応を判定し、
第３共有および第４共有は、各々の第１共有および第２共有ならびに前記追加情報の少なくとも一部の関数として各々の前記第２デバイスおよび前記第３デバイスによって計算されることを特徴とする方法。
【請求項３】
前記第１デバイスは、クライアントデバイスを含み、
前記第２デバイスおよび前記第３デバイスは、ネットワークを介して前記クライアントデバイスに接続可能な各々の第１サーバおよび第２サーバを含むことを特徴とする請求項１記載の方法。
【請求項４】
前記生成ステップおよび記憶ステップは、前記追加情報の後続認証のための前記第１パスワードの登録を提供することを特徴とする請求項１記載の方法。
【請求項５】
前記第１共有および前記第２共有は、代数群内の各々の第１要素および第２要素を含み、
前記群の演算子の下での前記第１要素および前記第２要素の合成は、前記第１パスワードの表現を作ることを特徴とする請求項１記載の方法。
【請求項６】
複数のデバイスを含むシステムで情報を認証する方法であって、前記デバイスのそれぞれは、他のデバイスの１つまたは複数と通信するように適合可能であり、前記方法は、
前記複数のデバイスの第１デバイスにおいて、該第１デバイスに関連する第１パスワードの第１共有および第２共有を生成するステップと、
前記第１共有および前記第２共有を、それぞれ、前記複数のデバイスの第２デバイスおよび第３デバイスに記憶するステップと
を具え、
前記第２デバイスおよび前記第３デバイスの少なくとも１つへの前記第１デバイスに関連する追加情報のサブミットの時に、前記第１共有および前記第２共有の各々は、前記追加情報の前記第１パスワードとの対応だけから判定することが実行不可能であるという特性を有する要素を含み、
前記第２デバイスおよび前記第３デバイスは、前記各々の第１共有および第２共有を使用して、前記追加情報の前記第１パスワードとの前記対応を判定し、
前記第１デバイスは、クライアントデバイスを含み、
前記第２デバイスおよび前記第３デバイスは、ネットワークを介して前記クライアントデバイスに接続可能な各々の第１サーバおよび第２サーバを含み、
前記追加情報は、前記クライアントデバイスに関連する第２パスワードの第３共有および第４共有を含むことを特徴とする方法。
【請求項７】
前記複数のデバイスは、前記クライアントデバイスならびに、前記第１サーバおよび前記第２サーバを含むｎ個のサーバを具え、
前記クライアントデバイスは、１≦ｉ≦ｎについて、ランダム多項式ｐの対応する点ｐ（ｉ）として、ｎ個のサーバのそれぞれＳｉの第１パスワードの共有を生成し、点ｐ（０）は、前記第１パスワードのハッシュを表すことを特徴とする請求項６記載の方法。
【請求項８】
前記複数のデバイスは、前記クライアントデバイスならびに前記第１サーバおよび第２サーバを含むｎ個のサーバを具え、
前記クライアントデバイスは、１≦ｉ≦ｎについて、ランダム多項式ｐの対応する点ｐ（ｉ）としてのｎ個のサーバのそれぞれＳｉの前記第１パスワードの共有、およびｐ上の点に対するコミットメントの集合Ｃ＝｛（ｐ（ｉ））２  ｍｏｄ  Ｎ｝を生成し、
前記コミットメントの集合は、前記ｎ個のサーバのそれぞれに送信され、前記多項式は、Ｎを法とする剰余系の環ＺＮの上で定義されることを特徴とする請求項６記載の方法。
【請求項９】
メモリに結合されたプロセッサを有するデバイスを含む装置であって、
前記デバイスは、それぞれが１つまたは複数の他のデバイスと通信するように適合可能である複数のデバイスの１つであり、
前記デバイスは、前記複数のデバイスの第１デバイスにおいて、該第１デバイスに関連する第１パスワードの少なくとも第１共有および第２共有を前記複数のデバイスの各々の第２デバイスおよび第３デバイスに記憶するシステムで使用可能であり、
前記第１デバイスに関連する追加情報の前記第２デバイスおよび前記第３デバイスの少なくとも１つへのサブミットのときに、前記第１共有および前記第２共有の各々は、前記追加情報の前記第１パスワードとの対応だけから判定することが実行不可能であるという特性を有する要素を含み、前記第２デバイスおよび前記第３デバイスは、前記追加情報の前記第１パスワードとの前記対応を判定するためにめいめいの前記第１共有および前記第２共有を使用し、
前記追加情報は、前記第１共有および前記第２共有に関連した認証するために使用される第３共有および第４共有を含み、
前記第３共有は、前記第１デバイスによって前記第２デバイスに配信され、
前記第４共有は、前記第１デバイスによって前記第３デバイスに配信されることを特徴とする装置。
【請求項１０】
各々が１つまたは複数の他のデバイスと通信するように適合可能な複数のデバイスを含むシステムで情報を認証する方法であって、
パスワードの共有がそれぞれ前記複数のデバイスの１つに対応して記憶されるように、前記共有を前記システム内で記憶するステップと、
前記共有を記憶する前記デバイスの特定の１つが追加情報とパスワードとの間の対応を判定できないように、前記デバイスの少なくとも１つにサブミットされる追加情報の真正性を判定するのに前記共有を使用するステップと
を具え、
前記追加情報のサブミットは、前記デバイスの別の１つによって前記デバイスの前記所与の１つに供給される匿名に基づいて、少なくとも前記共有を記憶する前記デバイスの所与の１つに知られることを特徴とする方法。
【請求項１１】
それぞれが１つまたは複数の他のデバイスと通信するように適合可能な複数のデバイスを含むシステムで情報を認証する方法であって、
前記複数のデバイスの第１のデバイスは、前記複数のデバイスの少なくとも第２のデバイスに追加情報をサブミットするステップ
を具え、
前記第２デバイスは、前記サブミットされた情報が真正であるかどうかを判定するために、前記複数のデバイスの少なくとも第３のデバイスと相互作用する匿名を使用し、
前記第１デバイスは、前記第２デバイスによって供給される匿名によって前記第３デバイスに対して識別され、
前記第２デバイスは、ユーザ識別子を匿名に写像するのに１方向関数を使用し、複数の認証要求のそれぞれについて、前記第２デバイスが前記第３デバイスに所与の対応する匿名を提示していることを前記第３デバイスに証明するために前記第１デバイスと共に動作することを特徴とする方法。
【請求項１２】
前記共有のそれぞれは、ライフクエスチョンの組に対する回答の部分に対応し、前記追加情報は、認証のためにサブミットされるライフクエスチョンの前記組に対する回答の対応する部分を具え、
前記使用するステップは、ライフクエスチョンの前記組に対する正しい回答の数が指定された閾値を超える場合に、前記追加情報が真正であると判定されるように構成されることを特徴とする請求項１記載の方法。
【請求項１３】
前記追加情報が真正と判定される場合に、前記第２デバイスおよび前記第３デバイスは少なくとも１つのポスト認証アクションを実行するステップを具えたことを特徴とする請求項１記載の方法。
【請求項１４】
前記共有を記憶する前記デバイスは、前記追加情報の真正性を判定するのに前記共有を使用する際に、ミックスネットワークとして動作することを特徴とする請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的には、コンピュータネットワークまたは他の通信媒体を介するセキュア通信を提供する暗号技法に関し、具体的には、セキュアローミングまたはモバイル通信デバイスを伴う他の認証応用での使用に特に適する暗号技法に関する。
【背景技術】
【０００２】
ユーザのモビリティの高まりおよび様々なコンピューティングデバイスの使用の増加が、セキュアローミングへの幅広い関心に動機を与えてきた。特に重要なのが、ユーザが、短い鍵または他の「弱い」パスワードを使用して、信頼されるサーバとのセキュア機能性を達成する能力である。ローミングユーザの非常に一般的な目的は、信頼されるサーバから「軽量」デバイスすなわち限られた処理能力、メモリ、または他の計算リソースを有するデバイスに認証をダウンロードすることである。そのようなデバイスに、例えば、携帯電話機、携帯情報端末（ＰＤＡ）、ゲーム機などが含まれる。そのようなデバイスのユーザは、その代わりに、デジタル署名および公開鍵ベース暗号化解除などの集中型計算または注意深い鍵ストレージを必要とする暗号動作を信頼されるサーバに委任することを求める場合がある。ローミングユーザに関するもう１つの重要な必要は、パスワード回復またはリセットの必要である。
【０００３】
ローミングユーザは、そのすべてが必ずしも同一のソフトウェアまたはコンフィギュレーションを有しない、任意の数の異なるデバイスのいずれでも使用することができる。スマートカードおよび類似する鍵ストレージデバイスは、モバイルユーザのセキュリティへの手際良く調和された手法を提供するが、適当に開発されたサポートするインフラストラクチャがない。現在、例えば、特に米国で、非常に少数のコンピューティングデバイスに、スマートカードリーダが含まれる。さらに、多くのユーザが、物理的認証トークンが不便であることに気付いている。また、トークンを失ったか忘れたローミングユーザを認証する必要がある場合がある。現在、これは、一般に、ユーザに１組の「ライフクエスチョン（ｌｉｆｅ  ｑｕｅｓｔｉｏｎ）」すなわち、個人情報またはプライベート情報に関する質問への回答を提供するように求めることによって達成される。これらの観察から、認証の形として、覚えやすい短い情報または他の弱いパスワードをローミングユーザが使用できるようにする必要が強調される。
【０００４】
多くの基本的ローミングプロトコルで、パスワードは、中央データベースに保管され、その結果、サーバが危険にさらされた場合の１まとめにしての盗難に脆弱である。そのようなプロトコルは、しばしば、ＳＰＡＫＡ（secure password-authenticated key agreement）に基づく。通常のＳＰＡＫＡプロトコル実装では、クライアントおよびサーバが、パスワードを共有し、このパスワードが、暗号的に強いセッション鍵がこの２つの当事者によって秘密に共有されることの相互保証を達成するのに使用される。弱いパスワードの問題に対処するために、ＳＰＡＫＡプロトコルは、アクティブな攻撃者が存在する場合であっても、パスワード情報を漏らさないように構成されている。信頼されるサーバから認証を得るための認証手段として使用される時に、ＳＰＡＫＡプロトコルは、通常は、オンライン推測攻撃を防ぐために、スロットリングまたはロックアウト機構を用いて増補される。多くのローミング認証提案に、認証を得るための挺子の支点として、または自立した認証プロトコルとしてのＳＰＡＫＡプロトコルの使用が含まれる。
【０００５】
しかし、上述したように、ほとんどのＳＰＡＫＡプロトコルの設計は、サーバ自体が深刻な脆弱性を表すという基本的な問題を見逃している。ＳＰＡＫＡプロトコルは、検証するサーバがユーザパスワードまたは派生材料への平文アクセスを必要とするので、サーバが危険にさらされることが、潜在的にパスワードのデータベース全体の露出につながる。多くのＳＰＡＫＡプロトコルでは、パスワードがいわゆる「ソルト（ｓａｌｔ）」と組み合わせてまたは累乗された形で保管されるが、攻撃者は、オフライン辞書攻撃を開始する可能性を有する。さらに、これらのシステムは、サーバ破壊に対する抵抗を提供しない。認証サーバの制御を得た攻撃者は、成功裡のログインの試みになりすますことができる。
【０００６】
普通のＳＰＡＫＡベース技法に関する上記の問題に対処するために、ＦｏｒｄおよびＫａｌｉｓｋｉは、複数のサーバを用い、少なくともいくつかのサーバが危険にさらされないままである場合にパスワードプライバシが保たれる、パスワード「強化（ｈａｒｄｅｎｉｎｇ）」方式の集合を提案した（例えば、参照によって本明細書に組み込まれる非特許文献１参照）。このシステムでは、クライアントが、それぞれがサーバ秘密を使用してパスワードをブラインド（ｂｌｉｎｄ）変換する１つまたは複数の強化サーバとの対話を介して、弱いパスワードを強いパスワードに拡張する。
【０００７】
具体的な例として、ＦｏｒｄおよびＫａｌｉｓｋｉのシステムの１バージョンのクライアントは、各強化サーバＳｉからのパスワードＰに対するブラインド関数評価σｉまたは「共有（ｓｈａｒｅ）」とみなすことができるものを入手する。問題の関数は、各サーバおよびユーザアカウントに一意の秘密に基づく。クライアントは、秘密の集合｛σｉ｝を単一の秘密σに組み合わせ、このσは、例えば認証の暗号化解除、ユーザ自身の認証など、セキュア認証応用でユーザが使用できる強い鍵として働く。ブラインド関数評価方式の適当な選択を与えられれば、このプロトコルのサーバは、情報理論の意味で、パスワードＰに関する情報を学習しないものとすることができる。
【０００８】
ＦｏｒｄおよびＫａｌｉｓｋｉのシステムは、閾値設定に拡張され、幅広く包含的な攻撃モデル（例えば、参照によって本明細書に組み込まれる非特許文献２参照）での厳格なセキュリティ保証を有するがより複雑なプロトコルにつながった。具体的に言うと、Ｐ．Ｍａｃｋｅｎｚｉｅ他は、ｎ個のうちのｋ個のサーバと通信するクライアントが、パスワードベース認証によってｋ個のサーバのそれぞれとのセッション鍵を確立でき、ｋ−１個のサーバが共謀する場合であっても、クライアントのパスワードがプライベートのままであるプロトコルを実証した。このシステムを単純に活用して、セキュアダウンロード可能認証を達成することができる。
【０００９】
しかし、Ｍａｃｋｅｎｚｉｅ他のシステムは、複数のタイプのかなりのオーバーヘッドを負わせる。第１に、サーバは、共有されるグローバル鍵およびローカル鍵も所有しなければならず、合計４ｎ＋１個の公開鍵を所有しなければならない。さらに、クライアントは、ｎ＋１個の証明された公開鍵を保管しなければならない。クライアントは、セッションを開始するごとに、サーバごとに複数のべき剰余（ｍｏｄｕｌａｒ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）を実行しなければならず、サーバに対する計算負荷も高い。最後に、Ｍａｃｋｅｎｚｉｅ他のプロトコルは、計算的におよび実装に関しての両方で、かなり複雑である。その一方で、Ｍａｃｋｅｎｚｉｅ他のプロトコルは、明らかに、ｒａｎｄｏｍ  ｏｒａｃｌｅモデルでのＤｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定の下でのセキュリティの厳格な証明を与えられた最初のプロトコルである。
【００１０】
長所にもかかわらず、上で説明した既知の技法は、特に軽量デバイスを介して通信される弱いパスワードを使用するセキュアで効率的な形でユーザが自分自身を認証できるようにすることに関して、ローミングユーザのセキュリティの必要を完全には満足していない。
【００１１】
【非特許文献１】W. Ford and B.S. Kaliski Jr., "Server-Assisted Generation of a Strong Secret from a Password," Proceedings of the IEEE 9th International Workshop on Enabling Technologies (WETICE), NIST, Gaithersburg MD, June 2000
【非特許文献２】P. Mackenzie et al., "Threshold Password-Authenticated Key Exchange," Research Papers on Strong Password Authentication, http: //www.integritysciences.com/links.html, 2002
【非特許文献３】A.J. Menezes et al., Handbook of Applied Cryptography, CRC Press, 1997
【非特許文献４】V. Shoup. "A Proposal for an ISO Standard for Public Key Encryption (Version 2.1)," http: //shoup.net/papers/, December 20, 2001
【非特許文献５】M. Jakobsson and A. Juels, "Mix and Match: Secure Function Evaluation Via Ciphertexts," ASIACRYPT '00, LNCS No. 1976, T. Okamoto, editor, Springer-Verlag, pp. 162-177, 2000
【非特許文献６】P.C. van Oorschot and M.J. Wiener, "On Diffie-Hellman Key Agreement with Short Exponents," EUROCRYPT 1996, pp. 332-343
【非特許文献７】M. Blum, "Coin flipping by telephone," Proc. of 24th IEEE Compcon, pp. 133-137, 1982
【非特許文献８】A. Shamir, "How to Share a Secret," Communications of the Association for Computing Machinery, 22(11): 612-613
【非特許文献９】P. Paillier, "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes," EUROCRYPT '99, LNCS No. 1592, J. Stern, editor, pp. 223-238, 1999
【非特許文献１０】R. Cramer et al., "Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols," CRYPTO '94, LNCS No. 839, Y.G. Desmedt, editor, pp. 174-187, Springer-Verlag, 1994
【非特許文献１１】A. de Santis et al., "On Monotone Formula Closure of SZK," FOCS '94, IEEE Press, pp. 454-465, 1994
【非特許文献１２】E. Fujisaki and T. Okamoto, "Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations," CRYPTO '97, LNCS No. 1294, B. Kaliski, editor, Springer-Verlag, pp. 16-30, 1997
【非特許文献１３】I. Damgard and E. Fujisaki, "An Integer Commitment Scheme Based on Groups with Hidden Order," IACR eArchive, 2001
【非特許文献１４】D. Chaum, "Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms," Communications of the ACM, 24(2): 84-88, 1981
【非特許文献１５】A. Juels, "Targeted Advertising ... and Privacy Too," RSA-CT '01, LNCS No. 2020, D. Naccache, editor, pp. 408-424, 2001
【非特許文献１６】J. Furukawa and K. Sako, "An Efficient Scheme for Proving a Shuffle," CRYPTO '01, LNCS No. 2139, Springer-Verlag, pp. 368-387, 2001
【非特許文献１７】A. Neff, "A Verifiable Secret Shuffle and its Application to E-voting," ACM CCS '01, ACM Press, pp. 116-125, 2001
【非特許文献１８】M. Ohkubo and M. Abe, "A Length-Invariant Hybrid Mix," ASIACRYPT '00, LNCS No. 1976, T. Okamoto, editor, pp. 178-191, 2000
【非特許文献１９】M. Jakobsson and A. Juels, "An Optimally Robust Hybrid Mix Network," Principles of Distributed Computing (PODC) '01, ACM Press, pp. 284-292, 2001
【非特許文献２０】D.J. Bernstein, http: //cr.yp.to/syncookies.html, 2002
【非特許文献２１】A. Juels and J. Brainard, "Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks," Networks and Distributed System Security, S. Kent, editor, pp. 151-165, 1999
【非特許文献２２】http: //addurl.altavista.com/sites/addurl/newurl
【非特許文献２３】D.P. Jablon, "Password Authentication Using Multiple Servers," Topics in Cryptology - CT-RSA 2001, LNCS No. 2020, D. Naccache, editor, Springer-Verlag, pp. 344-360, 2001
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、限られた計算リソースを有するモバイル通信デバイスでの使用に特に適するセキュア認証プロトコルを実施する方法および装置を提供することである。
【課題を解決するための手段】
【００１３】
本発明の一態様によれば、ネットワークベースのシステムに、クライアントデバイスおよび少なくとも２つのサーバが含まれる。第１共有および第２共有が、クライアントデバイスに関連する第１パスワードから生成され、それぞれ第１サーバおよび第２サーバに保管される。第１サーバおよび第２サーバの少なくとも１つへの、クライアントに関連する追加情報のサブミットの際に、第１共有および第２共有のそれぞれが、第１パスワードへの追加情報の対応だけから判定することが実行不可能であるという特性を有し、第１サーバおよび第２サーバは、各々の第１共有および第２共有を使用して、第１パスワードへの追加情報の前記対応を集合的に判定する。この配置の長所は、クライアントデバイスとサーバの一方または両方とのそれ以上の対話を必要とせずに、対応判定を行えることである。もう１つの長所は、クライアントデバイスが、重要な暗号計算を実行する必要がないことである。
【００１４】
本発明のもう１つの態様によれば、追加情報に、例えば、クライアントデバイスに関連する第２パスワードに対する第３共有および第４共有を含めることができる。追加情報は、第１サーバおよび第２サーバが第１共有および第３共有の関数として第１サーバによって生成される第１量を第２共有および第４共有の関数として第２サーバによって生成される第２量と比較することによって、処理される。第１サーバおよび第２サーバは、第１量と第２量が実質的に同等と判定される場合に、追加情報を真正として受け入れる。
【００１５】
本発明のセキュア認証プロトコルの他の態様は、例えば、サーバによって計算される上記の量の同等性テスト、１つまたは複数のサーバでのユーザ識別の匿名保護、複雑さを減らされた変形、ｎが２を超えるｎサーバ変形、および多項式ベース認証に関する。
【００１６】
本発明のセキュア認証プロトコルは、前に説明した従来の技法に関連する問題の１つまたは複数を克服し、軽量デバイスを介して通信される弱いパスワードを使用してセキュアで効率的な形でユーザがユーザ自身を認証できるようにする。本発明の上記および他の特徴および長所は、添付図面および下の詳細な説明からすぐに明白になる。
【発明を実施するための最良の形態】
【００１７】
本明細書で、クライアントがネットワークを介して１つまたは複数のサーバと通信する、例のネットワークベース通信システムに関して本発明を説明する。しかし、本発明が、これまたは他の特定のシステム構成での使用に制限されないことを諒解されたい。
【００１８】
本明細書に記載のある従来の暗号技法に関する追加の詳細は、例えば参照によって本明細書に組み込まれる非特許文献３にある。
【００１９】
例示的システム
図１は、本発明のセキュア認証技法を示すのに使用される、単純化されたネットワークベース通信システム１００を示す。システム１００には、クライアント１０２、第１サーバ１０４Ｒ、および第２サーバ１０４Ｂが含まれ、これらのすべてが、ネットワーク１０６を介して通信するように構成される。図を単純にするためおよび表記の都合上、第１サーバ１０４Ｒおよび第２サーバ１０４Ｂを、本明細書でそれぞれ「Ｒｅｄ」サーバおよび「Ｂｌｕｅ」サーバと称し、本発明によるセキュア認証プロトコルの一部を実施する例のサーバ対をこれに含める。サーバ１０４の特定の１つをＲｅｄサーバ、他方をＢｌｕｅサーバとする表記は、任意である。というのは、これらのサーバの役割を、本明細書に記載のプロトコルで逆転できるからである。
【００２０】
図１には、単一のクライアントだけが示されているが、システム１００の実用的実施形態が、実質的に多数のクライアントをサポートすると期待される。同様に、図１にはサーバの単一の対だけが示されているが、本発明によるシステムに、多数のそのようなサーバの対ならびにサーバの他の配置、例えば一般的な数ｎ個のサーバ（ｎ≧２）を含めることができる。したがって、本発明は、特定の個数のクライアントデバイスまたはサーバデバイスに制限されず、システム内のサーバデバイスの特定のペアリングまたは他の配置を必要としない。
【００２１】
クライアント１０２は、携帯電話機、ＰＤＡ、ゲーム機などの軽量デバイスを表すことができる。クライアント１０２は、デスクトップパーソナルコンピュータ（ＰＣ）、ラップトップＰＣ、ミニコンピュータ、ワークステーション、メインフレームコンピュータ、有線電話機、ファクシミリ機、テレビジョンセットトップボックス、または本発明のセキュア認証技法から利益を得ることができる他の情報処理デバイスを表すことができる。したがって、クライアント１０２を、サーバとして実施することもできる。言い換えると、本発明は、ローミング軽量クライアントデバイスがサーバにそれ自体を認証する応用での使用に特に適するが、それ自体がサーバであるデバイスを含むすべてのタイプの情報処理デバイスのセキュア認証に使用することができる。
【００２２】
クライアント１０２を、本明細書でユーザと称する場合もある。用語「ユーザ」は、クライアントデバイス、デバイスを使用するか他の形でデバイスに関連する人、またはその両方を含むものとして理解されたい。したがって、ユーザによって実行されるものとして本明細書に記載の動作は、デバイス、デバイスを使用するか他の形でデバイスに関連する人、またはユーザおよびデバイスの両方によって実行することができる。同様に、デバイスに関連するパスワードは、デバイスのユーザのパスワードとすることができる。この場合に、パスワードは、それぞれが異なるパスワードを有する複数のユーザにサービスするデバイスの場合のように、ユーザによるデバイスへのパスワードの入力の際に、デバイスに一時的に関連付けられるものとすることができる。
【００２３】
サーバ１０４Ｒおよび１０４Ｂは、本明細書に記載のセキュア認証機能を実行するようにプログラムされた、それ以外は普通のサーバとして、または他のタイプの適当にプログラムされた情報処理デバイスとして、実施することができる。
【００２４】
ネットワーク１０６は、インターネット、広域ネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、衛星網、電話網、ケーブルネットワーク、あるいは上記および他のタイプのネットワークの様々な部分または組合せを表すことができる。
【００２５】
前述から明白なように、図１に示されたシステム１００は、より一般的に、互いに通信するように構成され、デバイスの所与の１つが他のデバイスに対してそれ自体を認証する、少なくとも３つの処理デバイスを有するシステムと見ることができる。したがって、図１のデバイスについて示された特定の「クライアント」および「サーバ」のラベルは、本発明の制限ではなく、例示とみなされなければならない。
【００２６】
図２は、図１のシステムの処理デバイス１０２、１０４Ｒ、または１０４Ｂの所与の１つの１つの可能な実施形態を示す。この実施形態のデバイスに、メモリ２０２およびネットワークインターフェース２０４に結合されたプロセッサ２００が含まれる。これらのデバイス要素は、全体としてまたは部分的に、普通のマイクロプロセッサ、デジタル信号プロセッサ、特定用途向け集積回路（ＡＳＣＩ）、または他のタイプの回路ならびにそのような回路要素の部分または組合せとして実施することができる。当業者が諒解するように、本発明によるセキュア認証プロトコルは、少なくとも部分的に、デバイスメモリ２０２に保管され、対応するプロセッサ２００によって実行される１つまたは複数のソフトウェアプログラムの形で実施することができる。メモリ２０２は、本発明のセキュア認証プロトコルに関連する計算または他の動作の実行に使用される情報を保管するのにも使用される。
【００２７】
前述したように、本発明は、その一態様に従って、図１のシステム１００のクライアント１０２などの１つのデバイスが、システム１００のサーバ１０４Ｒおよび１０４Ｂなどの他のデバイスの対にそれ自体を認証するセキュア認証技法を提供する。本発明の第１の例示的実施形態による例の２サーバセキュア認証プロトコルを、下で図３から図６に関して説明する。計算の複雑さを減らされた代替の２サーバ実施形態を、図７および図８に関して説明する。その後、マルチサーバ変形および多数の他の変形を説明する。
【００２８】
本明細書で説明する例示的実施形態での本発明は、それ自体がクライアントおよびサーバの相互認証を提供しないという点で、前に説明した従来のＳＰＡＫＡプロトコルとは異なる。その代わりに、本発明は、従来の技法に関連する計算的な重荷が回避されるように、クライアントが分散された形で複数のサーバにそれ自体を認証する特に効率的な技法を提供する。具体的に言うと、従来の技法に関する本発明の重要な特徴は、クライアントデバイスによる集中型の暗号計算を本質的に必要としないように実施できることである。もう１つの長所は、クライアントデバイス側の特殊目的ソフトウェアを必要としない形で実施でき、したがって、ハイパーテキストマークアップ言語（ＨＴＭＬ）フォームまたは他の類似する機構を使用する現在のパスワードサブミット技法と完全に互換であることである。例示的実施形態では、サーバ側認証を仮定するが、これは、例えば、当業者が諒解するように、サーバ側証明書の提示、正しいＵＲＬ（ｕｎｉｆｏｒｍ  ｒｅｓｏｕｒｃｅ  ｌｏｃａｔｏｒ）へのルーティング、または他の技法、ならびにその組合せによって実施することができる。
【００２９】
２サーバセキュア認証プロトコル
図３は、本発明の第１の例示的実施形態による、２サーバセキュア認証プロトコルを示す。この実施形態では、図１のクライアント１０２に関連するユーザが、サーバ１０４Ｒおよび１０４Ｂの対に対して自分自身を認証する。上で注記したように、ユーザによって実行されるものとして示された動作は、少なくとも部分的に、関連するクライアントデバイスによって実行される。図３には、ユーザがパスワードＰを２つのサーバ用の共有に分割する登録部分３００と、後続認証のためにパスワードＰ’を提示する際に、ユーザが２つのサーバにＰ’の新しいランダムな共有を提供する認証部分３０２が含まれる。この処理の認証部分では、パスワードＰ’が、登録されたパスワードＰと実質的に等しいかどうかを判定する。具体的に言うと、この例示的実施形態の処理の認証部分の一部として、サーバは、Ｐ＝Ｐ’であるかどうかを学習するが、サーバの１つが不正を試みる場合であっても意味のある追加情報を学習しない形で、２つの共有ＰおよびＰ’を比較する。
【００３０】
パスワードＰ’は、本明細書でより一般的に「追加情報」と称するものの例であり、この例示的実施形態では、パスワードＰの登録の後にユーザまたは関連するデバイスによってサブミットされる情報を表す。しかし、本明細書で使用される時の用語「追加情報」を、すべてのタイプの情報とすることができることを理解されたい。
【００３１】
図３の例示的実施形態は、パスワードＰの共有のそれぞれが、所与の共有だけからパスワードＰとのパスワードＰ’の対応を判定することが実行不可能であるという特性を有する。上で示したように、認証部分３０２で、２つのサーバが、めいめいの第１共有および第２共有を使用して、パスワードＰとのパスワードＰ’の対応を集合的に判定する。この文脈で使用される用語「対応」は、例えば、制限なしに、第１の情報と第２の情報の完全なまたは正確な対応、あるいは、例えば情報が単純にランダムに選択される場合に存在するものを超える第１の情報と第２の情報の間に存在する関係を示す、部分的対応を含むことが意図されている。
【００３２】
所与のパスワードを、図３のプロトコルの登録部分および認証部分へのサブミットの前に、従来の技法を使用してクライアントデバイスによって前処理できることに留意されたい。そのような前処理動作の結果の出力も、本明細書ではパスワードと称する。
【００３３】
したがって、本明細書で使用する用語「パスワード」は、例えば、制限なしに、実際の単語、数のシーケンス、文字または他のシンボル、２進コード、暗号鍵、個人識別番号（ＰＩＮ）、秘密、パスコード、ライフクエスチョンに対する回答またはそのような回答の組、ユーザプロファイルまたはその一部、ＲＳＡ  ＳｅｃｕｒＩＤ（登録商標）トークンに関連する１つまたは複数の値、または類似物などの、認証に使用されるのに適するデータを含むように広義に解釈されることが意図されている。
【００３４】
用語「共有」は、例えば、制限なしに、パスワードの一部を含むことが意図されている。
【００３５】
セキュア認証プロトコルの登録部分３００に、ステップ３０４、３０６、および３０８が含まれる。Ｈが、大きい群（例えば１６０ビット次数の）であり、＋が群演算子であるものとする。ｆが、衝突のないハッシュ関数ｆ：｛０，１｝＊→Ｈであるものとする。ステップ３０４で、ユーザが、ランダムな群要素Ｒ∈ＵＨを選択する。ユーザは、ステップ３０６で、Ｐｂｌｕｅ＝ｆ（Ｐ）＋ＲとしてＢｌｕｅサーバ１０４Ｂの共有Ｐｂｌｕｅを計算し、Ｒｅｄサーバ１０４Ｂの共有ＰｒｅｄにＲをセットする。ステップ３０８で、共有ＰｂｌｕｅおよびＰｒｅｄを、めいめいのＢｌｕｅサーバおよびＲｅｄサーバに送信する。各サーバの共有が、個別にはパスワードＰに関する情報を提供しないことを観察されたい。
【００３６】
このプロトコルの上で説明した登録部分をシミュレートすることによって、単純な形でレガシデータを共有に変換でき、サーバにロードできることに留意されたい。そのようなレガシデータは、一般に、これと同一のシミュレーション手法を介して、他のローミング認証プロトコルの共有に変換することもできる。
【００３７】
セキュア認証プロトコルの認証部分３０２には、ステップ３１０から３２０が含まれる。ステップ３１０で、ユーザが、新しいランダム群要素Ｒ’∈ＵＨを選択し、Ｐ’ｂｌｕｅ＝ｆ（Ｐ’）＋Ｒ’を計算し、Ｐ’ｒｅｄにＲ’をセットし、Ｐ’ｂｌｕｅをＢｌｕｅサーバ１０４Ｂに送信し、Ｐ’ｒｅｄをＲｅｄサーバ１０４Ｒに送信することによって、パスワードＰ’に基づく認証を開始する。
【００３８】
ＲｅｄサーバおよびＢｌｕｅサーバは、次のように、登録中に供給された共有を認証のために供給された共有と組み合わせる。ステップ３１２で、Ｂｌｕｅサーバが、Ｑｂｌｕｅ＝Ｐｂｌｕｅ−Ｐ’ｂｌｕｅ＝（ｆ（Ｐ）−ｆ（Ｐ’））＋（Ｒ−Ｒ’）を計算し、ステップ３１４で、Ｒｅｄサーバが、同様にＱｒｅｄ＝Ｐｒｅｄ−Ｐ’ｒｅｄ＝Ｒ−Ｒ’を計算する。Ｐ＝Ｐ’の場合すなわち、ユーザが、正しいパスワードを提供した場合に、ｆ（Ｐ）とｆ（Ｐ’）が打ち消しあい、その結果、Ｑｂｌｕｅ＝Ｑｒｅｄになることを観察されたい。そうでない場合に、ｆの衝突しにくさによって、結果はＱｂｌｕｅ≠Ｑｒｅｄになる。したがって、認証のためにサブミットされたユーザパスワードをテストするために、２つのサーバは、ステップ３１６に示されているように、好ましくは追加情報をまったく明らかにせずに、Ｑｂｌｕｅ＝Ｑｒｅｄであるかどうかをテストするだけでよい。ステップ３１６のテストで、Ｑｂｌｕｅ＝Ｑｒｅｄであることが確かめられる場合には、ステップ３１８に示されているように、ユーザパスワードＰ’が受け入れられ、認証が完了し、そうでない場合には、ステップ３２０に示されているように、パスワードが拒絶され、認証が失敗する。
【００３９】
前述したように正確な同等性ではなく、実質的な同等性に基づいて真正性を判定するように、本発明の他の実施形態を構成できることに留意されたい。
【００４０】
上述したように、関数ｆは、パスワードを大きい群に写像する。実際には、出力が指定された群に含まれるように適当に修正されたハッシュ関数を用いて達成することができる。例えば、Ｈが、ビット単位ＸＯＲ演算の下の１６０ビットストリングの群である場合に、１６０ビットハッシュ関数が適当である。その代わりに、Ｈが、１６０ビット要素を有する乗法群である場合に、ハッシュ関数の出力にあるモジュラリダクション（ｍｏｄｕｌａｒ  ｒｅｄｕｃｔｉｏｎ）を適用する必要が生じる場合がある。Ｈが、ハッシュ関数の出力より長い要素（例えば１０２４ビット要素）を有する群である場合に、ハッシュ関数の出力の拡張が必要になる場合がある。この拡張を達成する形の１つが、ＲＳＡ  ＬａｂｏｒａｔｏｒｉｅｓのＰＫＣＳ（Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｓｔａｎｄａｒｄ）＃１、Ｖｅｒｓｉｏｎ  ２．１、Ｊｕｎｅ  ２００２（http://www.rsasecurity.com/rsalabs/pkcs/で入手可能）のＭＧＦ１などのマスク生成関数を適用することである。
【００４１】
パスワードの他に、他の入力を関数ｆに与えることができる。この入力に、辞書攻撃に対する対抗手段として普通に行われているように、秘密でないソルト値を含めることもできる。秘密でないソルト値は、登録部分３００中にクライアントまたはサーバの一方によって生成し、サーバの一方でユーザに関する他の情報と共に保管し、認証部分３０２中にクライアントに供給することができる。入力に、ユーザの名前およびサーバの名前などの他の固定パラメータを含めて、関数ｆの出力をこれらのパラメータに関連付けることもできる。
【００４２】
前述では、関数ｆが１方向であることを仮定した。しかし、関数ｆが可逆であるシステムを構成することも可能である。そのような構成の長所は、パスワードＰ（または他の秘密）を、共有ＰｂｌｕｅおよびＰｒｅｄから再計算できることである。この場合に、関数ｆは、パスワードＰを、可逆の形で群要素に写像する。Ｈが、ビット単位ＸＯＲ演算の下の１６０ビットストリングの群であり、Ｐが１６０ビットより短い場合に、単純なパディングフォーマットが適当である。
【００４３】
実際には、クライアントは、ＲｅｄにＲおよびＲ’などの値を供給することに関する複数のオプションを有する。一例として、クライアントは、Ｒｅｄの公開鍵の下でＲｅｄと共に確立したプライベートチャネルを介してＲｅｄに直接に値を配布することができる。もう１つの例として、クライアントは、プライベートチャネルを介して「ベース」値を確立することができ、ここで、クライアントとＲｅｄは、１方向関数を介してベース値からＲまたはＲ’などの１つまたは複数の値を導出する。この後者のオプションは、クライアントとＲｅｄが所与のセッション中に１つのベース値を確立するだけでよく、このベース値からＲおよびＲ’などの複数の値を導出できるという長所を有する。例えば、複数のライフクエスチョンがある場合に、１方向関数への入力にクエスチョンインデックスを含めることによって、異なる値を同一のベース値から導出することができる。クライアントが、所与のセッション中に１つのライフクエスチョンに複数の回答を行う場合に、１方向関数への入力に試行インデックスを含めることによって、試行ごとに異なる値を導出することができる。具体的に言うと、ｉ番目の質問のｊ番目の試行の値Ｒ’ｉｊを、ベース値、インデックスｉ、およびｊを１方向関数に適用することによって得ることができる。
【００４４】
Ｒｅｄが、ＲＳＡ公開鍵（ｎ，ｅ）を有し、ｎが剰余、ｅが公開べきである場合に、ベース値を確立する方法の１つは、ＲＳＡ−ＫＥＭ技法（例えば、参照によって本明細書に組み込まれる非特許文献４参照）の変形を介することである。この変形では、クライアントが、０とｎ−１の間のランダムな整数ｒを生成し、Ｒｅｄの公開鍵を用いてｒを暗号化して、ｃ＝ｒｅ  ｍｏｄ  ｎを入手し、ｃをＲｅｄに送信する。ベース値は、１方向関数を介して整数ｒから導出することができる。Ｒｅｄは、その秘密鍵を用いてｃを暗号化解除して、ｒを回復し、同様にベース値を導出する。その代わりに、整数ｒ自体を、ベース値とみなすことができる。他の公開鍵暗号に基づく類似する技法が可能である。
【００４５】
前述の例の全てで、派生される値をパラメータに関連付けるのに有用と一般に考えられる、ＲｅｄおよびＢｌｕｅの名前、タイムスタンプ、Ｒｅｄの公開鍵、暗号文ｃなどの他のパラメータを、１方向関数への入力に含めることができる。
【００４６】
図３のプロトコルで、クライアントが、意味のある暗号計算を実行する必要がないことに留意されたい。したがって、このプロトコルは、軽量クライアントデバイスと共に使用することによく適する。しかし、クライアントが、ある暗号計算を実行して、ＲｅｄサーバおよびＢｌｕｅサーバとのセキュア接続を確立できることに留意されたい。例えば、周知のＳＳＬ（ｓｅｃｕｒｅ  ｓｏｃｋｅｔｓ  ｌａｙｅｒ）手法を、クライアントとサーバの間の接続を確立するのに使用する場合に、使用されるＲＳＡ暗号化に、少数の剰余乗算が含まれる。さらに、クライアントは、ステップ３１０で共有をサブミットしたならば、このプロセスの認証部分にこれ以上関係する必要はない。ＲｅｄサーバおよびＢｌｕｅサーバが、一緒に、認証のためにサブミットされたパスワードの正しさを判断する。成功裡の認証の場合に、これらのサーバの一方または両方が、ユーザの代わりに１つまたは複数のポスト認証アクションを実行することができる。例えば、各サーバが、秘密鍵の共有をユーザに送信することができ、２つのサーバが、単一の認証の別々の部分を発行することができ、あるいは、サーバが、協同で、デジタル署名または認証を作ることができる。
【００４７】
ステップ３１６での同等性テストを、これから詳細に説明する。ステップ３１６の同等性テストを実行するのに使用される、例の同等制定ストプロトコルを、図４に関して説明する。同等性テストでは、次数ｑの第２の大きい群Ｇを利用し、これに関して、乗算が群演算を表すものとする。群Ｇは、その上での離散対数問題が困難な群でなければならない。２つのサーバが、前もってこの群について同意し、Ｇの生成元ｇに合意し、検証したと仮定する。また、衝突のない写像ｗ：Ｈ→Ｇを使用する。値ＱｂｌｕｅおよびＱｒｅｄの同等性テストについて、考え方は、２つのサーバがＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵交換の変形を実行することである。しかし、この変形では、値ＱｂｌｕｅおよびＱｒｅｄが、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵によって「マスク」される。
【００４８】
結果の同等性テストプロトコルは、ＰＥＴプロトコル（例えば、参照によって本明細書に組み込まれる非特許文献５参照）の技術的単純化とみなすことができる。しかし、この同等性テストプロトコルは、ＰＥＴでのコンポーネントの通常の対ではなく、Ｅｌ  Ｇａｍａｌ暗号の１つのコンポーネントだけを使用する。同等性テストプロトコルは、ＥＫＥ（ｅｎｃｒｙｐｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ）などのＳＰＡＫＡプロトコルとの類似性も共有する。例えば、同等性Ｑｂｌｕｅ＝Ｑｒｅｄを、共有される秘密鍵をもたらすものとみなし、非同等性を、２つのサーバの異なる鍵をもたらすものとみなすことができる。しかし、本発明では、このプロトコル実行から共有鍵を導出することはせずに、最小の情報漏れで２つの秘密値の同等性をテストすることを求める。
【００４９】
この同等性テストプロトコルでは、さらに、２つのサーバの間のプライベートで相互に認証されるチャネルを前提とする。この例ではＢｌｕｅサーバと仮定される、サーバの特定の１つが、「開始サーバ」として指定される。同等性テストプロトコルは、開始サーバが、所与のユーザアカウントに関する複数同時の認証セッションを確立しようとする場合に、他方のサーバが拒絶するように構成される。具体的に言うと、図４のプロトコルで、Ｒｅｄサーバは、最初のフローが以前に確立されたアクティブな認証セッションと同一のユーザアカウントを指定するセッションの開始を拒絶する。さらに、どちらのサーバも、所与のユーザアカウントに対する単一のアクティブ認証セッションだけを許容する。単一アカウントに関する並列ログイン要求を許容する代替手法は、可能であるが、より複雑である。Ｂｌｕｅサーバが、Ｒｅｄサーバがユーザから対応する認証要求を受信していないユーザＵに関するＲｅｄサーバを伴う認証要求を開始する場合に、Ｒｅｄサーバは、ある適当な遅延の後に、その認証を拒絶する。
【００５０】
Ｑｂｌｕｅ，Ｕが、ＢｌｕｅサーバがユーザＵについてテストしたい現在の共有組合せを表し、Ｑｒｅｄ，Ｕが、ユーザＵとの類似するＲｅｄサーバ共有組合せを表すものとする。どちらのサーバについても、「拒絶」が、ユーザＵから来たと主張する認証セッションの拒絶および終了を表し、「受け入れ」が、ユーザＵから発したものとしてのセッションの受け入れを表すものとする。
【００５１】
図４のプロトコルならびに本明細書に記載の他のプロトコルでは、サーバが、
【００５２】
【数１】
0004639084.tif 000002
【００５３】
によって表される数学的関係の検証に失敗する場合に、そのサーバは、プロトコル失敗が発生したと判定する。
【００５４】
∈Ｒが、ある集合からの一様でランダムな選択を表すものとする。大括弧によって、望まれる場合にＢｌｕｅによるプロトコル開始の前にＲｅｄが行うことができる計算を表す。Ｚｒｅｄ、Ｙ１、Ｙ１’、Ｈｒｅｄなどの添字ｒｅｄまたは１が、Ｒｅｄによって計算されるか受け取られる値を表し、Ｚｂｌｕｅ、Ｙ０、Ｈｂｌｕｅなどのｂｌｕｅまたは０が、Ｂｌｕｅによって計算されるか受け取られる値を表すものとする。見た目の明瞭さのために、これらの表記の形を交替させる。ｈが、１方向ハッシュ関数を表すものとし、この関数は、ｒａｎｄｏｍ  ｏｒａｃｌｅによるセキュリティ分析のためにモデリングすることができる。システムに、複数のＢｌｕｅサーバおよび／またはＲｅｄサーバを含めることができる場合に、ハッシュＨｒｅｄに、サーバ識別も含まれなければならない。‖は、ストリング連結を表すものとする。
【００５５】
説明を単純にするために、図４の例の同等性テストプロトコルについて、特定の群Ｇを固定する。具体的に言うと、Ｇは、素数ｐ＝２ｑ＋１である、Ｚｐの次数ｑの素数部分集合であると考える。この特定の群の使用は、図４のプロトコルで、（１）送信される値の操作での群へのメンバシップを保証するための偶数のべきｅ０およびｅ１の使用と、（２）｛２，．．．，ｐ−２｝でのメンバシップ検査によって反映されている。群の他の選択に関して、操作される値の群メンバシップを、当業者にすぐに明白になる他の手段によって保証することができる。すべての算術が、ｐを法とする剰余系で実行される。
【００５６】
図４を参照すると、Ｂｌｕｅは、集合｛２，４，．．．，ｑ−１｝からランダムにｅ０を選択し、Ａ＝ｗ（Ｑｂｌｕｅ，Ｕ）および
【００５７】
【数２】
0004639084.tif 000003
【００５８】
を計算する。Ｒｅｄは、集合｛２，４，．．．，ｑ−１｝からランダムにｅ１を選択し、
【００５９】
【数３】
0004639084.tif 000004
【００６０】
を計算する。ＢｌｕｅはＹ０およびＵをＲｅｄに送信し、Ｒｅｄは、Ｂ＝ｗ（Ｑｒｅｄ，Ｕ）、Ｙ１＝ＢＹ１’、および
【００６１】
【数４】
0004639084.tif 000005
【００６２】
を計算する。Ｒｅｄは、Ｚｒｅｄ≠０であるかどうかを検査し、Ｚｒｅｄ、Ｙ０、Ｙ１、およびＵのストリング連結にハッシュ関数ｈを適用したものとしてＨｒｅｄを計算する。Ｒｅｄは、Ｙ１およびＨｒｅｄをＢｌｕｅに送信し、Ｂｌｕｅは
【００６３】
【数５】
0004639084.tif 000006
【００６４】
を計算する。Ｂｌｕｅは、Ｚｂｌｕｅ≠０であるかどうかを検査し、ＺｂｌｕｅおよびＨｒｅｄのストリング連結にハッシュ関数ｈを適用したものとしてＨｂｌｕｅを計算する。Ｂｌｕｅは、ＨｂｌｕｅをＲｅｄに送信する。Ｂｌｕｅは、Ｈｒｅｄが、Ｚｂｌｕｅ、Ｙ０、Ｙ１、およびＵのストリング連結にハッシュ関数ｈを適用した結果と同等である場合に受け入れ、そうでない場合に拒絶する。Ｒｅｄは、Ｈｂｌｕｅが、ＺｒｅｄとＨｒｅｄのストリング連結にハッシュ関数ｈを適用した結果と同等である場合に受け入れ、そうでない場合に拒絶する。
【００６５】
図４のプロトコルでのｐの適切な選択は、他の値を使用することができるが、１０２４ビット素数である。より短いべきｅ０およびｅ１、例えば１６０ビットを選択することによって、より高い効率を達成することができる。その代わりに、群Ｇの他の選択によって、より高い効率をもたらすことができる。例えば、１つの可能性が、楕円曲線上の適当な群としてのＧの選択である。これは、べき演算よりはるかによい効率をもたらし、群メンバシップの効率的なテストも有する。Ｈについて、例えば１６０ビットストリングからなり、群演算子としてＸＯＲを有する群を単純に選択することができる。これは、登録または認証するクライアントによる剰余算術を必要としないという長所を有する。多数の他の手法が、ＧまたはＨの選択について可能である。
【００６６】
群Ｈから群Ｇへの写像ｗについて、上のハッシュ関数およびマスク生成関数を用いる技法を適用することができる。Ｇが、楕円曲線群である場合に、点への識別子の最初の写像は、群要素をもたらさない場合がある（すべての点が曲線上にあるわけではない）が、当技術分野で周知のように、群要素がもたらされるまで、通常は少ない回数だけ、変形の写像を適用することができる。
【００６７】
ＢｌｕｅサーバとＲｅｄサーバの間の情報の流れのすべてが、クライアントを通過できることに留意されたい。これらの流れに対する保全性保護は、両方のサーバが正当である場合の悪意のあるクライアントに対する保護のために働く。流れの暗号化は、匿名の暴露に対して保護するように働く。流れは、やはり暗号化および保全性保護の使用を伴って、下で説明する代替の複数サーバ変形でもクライアントを通過することができる。
【００６８】
図３および４の２サーバプロトコルで、クライアントと２つのサーバの間の完全にプライベートなチャネルが前提になっていることにも留意されたい。
【００６９】
セキュリティに関して、２つのサーバの１つの制御を有する敵対者およびユーザの任意の集合が、正当なユーザのアカウントを攻撃する際に、本質的にランダムなオンライン推測よりよく行動できないことを示すことができる。そのような推測を伴う攻撃は、標準的なスロットリング機構、例えば３回の不正な推測の後に所与のアカウントをシャットダウンすることによって、阻止することができる。上で注記したハッシュ関数に関するｒａｎｄｏｍ−ｏｒａｃｌｅ仮定および適当なモデルを使用して、上で説明したシステムのセキュリティを、群Ｇの計算的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定に縮小することができる。
【００７０】
単純なサーバ故障に対する堅牢性は、ＲｅｄサーバおよびＢｌｕｅサーバの複製を介して単純に達成することができる。
【００７１】
図３および４の２サーバプロトコルのセキュリティは、ＲｅｄおよびＢｌｕｅの両方を危険にさらす攻撃者の能力に依存する。したがって、サーバ構成の不均一性が、ここで検討される重要な実用的セキュリティである。最も単純なレベルで、ＲｅｄサーバおよびＢｌｕｅサーバは、異なるオペレーティングシステムを実行することができ、これによって、自称攻撃者が直面する技術的障害の範囲が広がる。この方向でのさらなるステップは、インサイダ攻撃またはソーシャルエンジニアリング攻撃のリスクを最小にすることを期待して、ＲｅｄおよびＢｌｕｅを異なる組織に配置することであろう。
【００７２】
組織にまたがるセキュリティの分散は、危険にさらすことに関する法的責任および財政的責任を柔軟に割り振ることができる、リスク管理の魅力的なモデルを提供する。具体的に言うと、これを、２つのサーバの一方、例えばＢｌｕｅサーバが、サービスプロバイダによって操作され、他方のサーバ、Ｒｅｄサーバが、「プライバシプロバイダ」と呼ぶことができるものによって操作される、プライバシアウトソーシングの一形態とみなすことができる。プライバシプロバイダは、プライバシ暴露に関連する法的責任および財政的責任の大きい部分を引き受ける、セキュリティ維持などの主要な重荷を引き受ける意志を持ち、特殊な専門技術を有する組織とすることができる。
【００７３】
サービスプロバイダが、大きい潜在的なモバイルユーザ人口に魅力的な形でこの手法を採用するためには、２つの顕著な要件がある。第１は、一般性すなわち、クライアントが特殊目的ソフトウェアをインストールする必要がないことである。具体的に言うと、クライアントは、ＨＴＭＬおよびＪａｖａ（登録商標）などの標準ブラウザコンポーネントによってシステムとインターフェースできなければならない。第２の要件は、匿名性すなわち、プライバシプロバイダ、この例ではＲｅｄが、アカウントに関連するユーザ名への明示的アクセスを得ることができてはならないことである。最小限でも、クライアントは、匿名ですなわち、真のアカウント名またはＩＰアドレスにリンク可能でない識別子を用いて、このサーバと相互作用できなければならない。これによって、Ｒｅｄのオペレータの側でのアカウント情報の不正使用に対する技術的障害がもたらされる。Ｒｅｄが危険にさらされた場合のアカウント識別子の露出を制限するためにも、この形で匿名を使用することが有用である。
【００７４】
匿名性要件、特にＲｅｄがクライアントのＩＰアドレスを学習してはならないと言う概念に鑑みて、プライバシプロバイダは、バックエンドサーバすなわち、クライアントではなく他のサーバだけと相互作用するサーバとしてＲｅｄを操作することが好ましい。この構成のもう１つの動機づけが、Ｒｅｄのセキュリティに対する強調である。アウトソーシングモデルでは、責任およびセキュリティの主要な重荷が、Ｒｅｄにかかり、プライバシプロバイダは、セキュリティ専門技術の主要なソースである。したがって、Ｒｅｄをインターネット上のオープンコミュニティから隔離し、その相互作用を１つまたは複数のＢｌｕｅサーバに制限することが望ましい。この構成は、サービス拒否攻撃へのＲｅｄの露出を最小にするのにも役立ち、この攻撃は、それ自体のユーザベースにより精通したＢｌｕｅが、それを処理するためのよりよい備えを有する。
【００７５】
この文脈で、ＲｅｄおよびＢｌｕｅを、その代わりに、エンタープライズモデルに従って構成することができ、その場合に、ＲｅｄおよびＢｌｕｅが、エンタープライズ内の異なるグループによって制御されるか、適当な形で分離されることに留意されたい。
【００７６】
一般性の要件は、セキュア認証プロトコルのソフトウェアが、多分ブラウザプラグインまたは独立の実行可能ファイルとして一部のクライアントにインストールされるが、Ｊａｖａ（登録商標）アプレットの形で使用可能でもある必要があることを示す。このアプレットは、Ｂｌｕｅによって、またはその代わりに追加サーバによって、分配することができる。このアプレットに、図３の基本的な２サーバプロトコルのクライアント部分を実行するソフトウェアが含まれ、Ｒｅｄの公開鍵も含めることができる。この公開鍵は、Ｂｌｕｅを介するＲｅｄへのプライベートチャネルを確立するためにも働く。
【００７７】
Ｂｌｕｅによるそのようなアプレットの配布は、Ｂｌｕｅが危険にさらされた場合に、Ｂｌｕｅが悪いアプレットを配布する可能性があるという直接の問題を示す。具体的に言うと、能動的な形でＢｌｕｅを危険にさらした攻撃者は、そのサーバに、Ｒｅｄの誤った公開鍵を含むか、実際にＲｅｄ宛の共有を暗号化しないアプレットをこのサーバに配布させることができる。信頼されるソフトウェアの問題は、ローミングクライアントがオンザフライでそのようなソフトウェアをインストールする必要がある場合に、ＳＰＡＫＡプロトコルにも存在する。アプレットまたは他のソフトウェアにデジタル署名することができるが、ほとんどのユーザは、ブラウザが提供する検証ツールを使用して、関連するコードに署名する証明書の正しさを検査する方法を理解している可能性が低い。そうではなく、発明人は、この問題に関する次の観察を行った。第１に、Ｂｌｕｅのコアコンポーネントを能動的に危険にさらすことは、受動的に危険にさらすことよりはるかに難しい可能性が高い。また、悪意のあるコード変更を検出するように特に設計されたシステム保全性チェッカツールを利用することができる。さらに、この形でＢｌｕｅを危険にさらすという攻撃者の作業は、原理的にすべての観察者がアプレットを検査することによって危険にさらされたことを検出できるという点で、従来の暗号設定での能動的な危険にさらす作業より困難である。したがって、プライバシプロバイダは、Ｂｌｕｅとの認証要求を周期的に開始して、その保全性を監視することができる。もう１つの相補的な手法は、Ｒｅｄが、Ｂｌｕｅがサービスするコードのハッシュを検証するソフトウェアを、関心を持つクライアントに配布することである。
【００７８】
より深刻な問題が、匿名性要件に伴って生じる。この要件を満たすために、Ｂｌｕｅは、固定された匿名Ｖに従って、Ｒｅｄに所与のユーザ名Ｕを識別しなければならない。この場合に可能な攻撃の１つが、Ｒｅｄが、識別子Ｕの下で認証するクライアントを装い、Ｂｌｕｅがどの関連する匿名Ｖをアサートするかを見ることである。これによって、Ｒｅｄは、ＵとＶの間のリンケージを知ることができる。このタイプの攻撃に対する防御の実用的な方法は、事実上ない。その代わりに、Ｒｅｄの側でのそのような振る舞いに先んずるために、社会的要因に頼る。例えば、サービスプロバイダとして、アカウント名のリストを保持するのはＢｌｕｅであり、その結果、Ｒｅｄが、これらをひとまとめにして累積することは困難である。さらに、評判の低下と言う危険に対して、Ｒｅｄは、匿名に対する攻撃を開始することを嫌わなければならない。もちろん、匿名の使用は、Ｒｅｄを受動的に危険にさらすことが、真のアカウント識別子を露出しないという点で、まだ有益である。
【００７９】
しかし、より深刻なのが、壊されたＢｌｕｅサーバによる、大量のオンライン偽匿名攻撃の可能性である。具体的に言うと、Ｂｌｕｅは、それが選んだパスワードの辞書を用いて、偽の匿名
【００８０】
【数６】
0004639084.tif 000007
【００８１】
の下でＲｅｄの架空のアカウントの任意の大きい集合を作成することができる。Ｂｌｕｅは、匿名
【００８２】
【数７】
0004639084.tif 000008
【００８３】
に対する所与のクライアントによる認証要求を再演することができる。一致を達成するまで再演を繰り返すことによって、Ｂｌｕｅは、アカウントＵに関する秘密情報を知る。この攻撃は、検出されずに無限に進行できるという点で特に深刻である。この種の挙動は、例えば不正アプレットの配布を伴う攻撃と異なって、公に検出可能ではない。
【００８４】
この問題に対処するために、Ｂｌｕｅに、秘密の静的な１方向関数ｆを使用して、ユーザ識別子を匿名に写像することを要求することができる。Ｂｌｕｅは、クライアントと共に、正しい匿名をアサートすることを、認証要求のすべてについてＲｅｄに証明する。この証明戦略を使用するプロトコルを設計する際の課題の１つが、認証された後になるまで、クライアントがアカウントの匿名を知ることを許可できないことである。そうしないと、Ｒｅｄが、クライアントを装うことによって匿名を学習することができる。第２の課題は、Ｒｅｄ、Ｂｌｕｅ、および特にクライアントにとって軽量な証明プロトコルの設計である。図５に、そのような匿名証明プロトコルの例を示す。この例のプロトコルは、クライアントによる集中型の暗号計算を必要とせず、１つのモジュラインバージョン（ｍｏｄｕｌａｒ  ｉｎｖｅｒｓｉｏｎ）および複数の対称鍵計算だけを必要とする。
【００８５】
図５の匿名証明プロトコルの基礎は、Ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が困難である次数ｑ’の群Ｇ’でのｆｘ：ｍ→ｍｘの形のべき剰余を含む１方向関数である。１方向関数のこの選択は、複数の特に好ましい特徴を有する。第１に、別個のログに対する標準的な非対話型ゼロ知識証明を使用することによって、ｆの適用に関するステートメントを証明することが可能である。さらに、関数ｆｘは、乗法準同形を有するすなわち、ｆｘ（ａ）ｆｘ（ｂ）＝ｆｘ（ａｂ）である。ｆｘを秘密に保つために、値ｘが、Ｂｌｕｅによって秘密に保たれる整数であることが好ましい。ｙ＝ｇｘが、Ｒｅｄに配布される対応する公開鍵を表すものとする。
【００８６】
べき剰余演算で、短いべきを使用できることに留意されたい（例えば、参照によって本明細書に組み込まれる非特許文献６参照）。
【００８７】
匿名証明プロトコルをクライアントにとって軽量にするために、「カットアンドチューズ（ｃｕｔ−ａｎｄ−ｃｈｏｏｓｅ）」証明戦略を使用する。考え方は、クライアント識別子Ｕを、Ｇ’の非自明な群要素として表すことである。クライアントは、Ｇ’上のＵの共有Ｕ０およびＵ１へのランダムな乗法分割を計算し、したがってＵ＝Ｕ０Ｕ１である。クライアントは、Ｕ０およびＵ１へのコミットメントＣ０およびＣ１も計算し、これらをＢｌｕｅに送信する。Ｂｌｕｅは、共有Ｕ０およびＵ１のそれぞれにｆｘを適用することによってＶを計算する。具体的に言うと、Ｂｌｕｅは、値Ｖ０＝ｆｘ（Ｕ０）およびＶ１＝ｆｘ（Ｕ１）をＲｅｄに送信する。ｆｘの乗法準同形によって、Ｒｅｄが、匿名Ｖ＝ｆｘ（Ｕ）＝ｆｘ（Ｕ０）ｆｘ（Ｕ１）＝Ｖ０Ｖ１を計算できることを観察されたい。
【００８８】
群要素としてのクライアント識別子Ｕの表現は、複数の標準的な形で達成することができる。群Ｇ’が、素数を法とする乗法群である場合に、上で述べたようにハッシュ関数またはマスク生成関数を適用することによって、または識別子が適当なサイズである場合に直接に、識別子を群の整数要素に写像することができる。やはり上で注記したように、群が楕円曲線群である場合に、標準的な技法が使用可能である。
【００８９】
この匿名Ｖが正しい匿名であることを証明するために、Ｒｅｄは、ランダムなチャレンジビットｂをＢｌｕｅに送信する。Ｂｌｕｅは、Ｕｂを明らかにし、Ｖｂ＝ｆｘ（Ｕｂ）であることを証明する。このプロトコルで不正をするＢｌｕｅが検出される可能性は、適当な暗号仮定の下で、１／２に極端に近い。したがって、Ｂｌｕｅが、例えば８０回、匿名攻撃を開始することを試みる場合に、これは、圧倒的な確率でＲｅｄによって検出される。したがって、このカットアンドチューズ匿名証明プロトコルは、Ｂｌｕｅによるそのような攻撃の脅威を、パスワード推測をサブミットするならず者のクライアントの脅威よりはるかに軽くする。
【００９０】
図５の匿名証明プロトコルの特徴の１つは、クライアントが、共有の対（Ｕ０，Ｕ１）に対するそのコミットメントを認証しなければならず、その結果、Ｒｅｄが、Ｂｌｕｅがそれを変更していないことを知るようになることである。これを達成するために、クライアントは、Ｒ’の下のメッセージ認証コード（ＭＡＣ）すなわちＲｅｄに送信するパスワード共有を適用する。説明を単純にするために、図５では、この図のトランスポート機構を明示的に含むことなく、ＲｅｄがＲ’をプライベートに受信すると仮定する。Π＝ＤＬＥＱ［ａ，ｂ，ｃ，ｄ］が、群Ｇ’での同等性ｌｏｇａｂ＝ｌｏｇｃｄの知識の非対話型ゼロ知識証明を表すものとする。Ｂｌｕｅが、同等性
【００９１】
【数８】
0004639084.tif 000009
【００９２】
を検証できない場合に、ＢｌｕｅおよびＲｅｄがサブミットされたパスワードをテストする前であっても、認証要求は失敗する。同様に、Ｂｌｕｅが、Ｕ０およびＵ１がＵの正しい共有でないと判定する場合に、Ｂｌｕｅは、要求を拒絶する。Ｒｅｄが、
【００９３】
【数９】
0004639084.tif 000010
【００９４】
を検証できないか、証明Πを検証できない場合に、Ｒｅｄは、Ｂｌｕｅが壊されたと結論する。Ｒｅｄが、
【００９５】
【数１０】
0004639084.tif 000011
【００９６】
を検証できない場合に、Ｒｅｄは、クライアントが無効な要求をサブミットしたか、ＢｌｕｅがＭを変更したと結論する。どちらの場合でも、Ｒｅｄは、匿名Ｖによって識別されるアカウントのパスワード検証を許可しないか、これに加わらない。
【００９７】
図５の量ｙは、ｙ＝ｇｘによって与えられ、Ｂｌｕｅの公開鍵を表すとみなすことができ、このｘは、Ｂｌｕｅの秘密鍵を表す。
【００９８】
図５では、クライアントが、共有Ｕ０およびＵ１ならびにコミットメントＣ０およびＣ１をＢｌｕｅに送信する。しかし、クライアントが、これらの値を決定するのに十分な情報をＢｌｕｅに送信することだけが必要である。例えば、クライアントは、Ｕ０だけを送信することができる。ＢｌｕｅはＵを知っているので、Ｇ’上のＵ／Ｕ０としてＵ１を判定することができる。コミットメントが、決定論的に計算されると仮定すると、Ｂｌｕｅは、Ｕ０およびＵ１からこれを再計算することができる。同様に、Ｂｌｕｅは、Ｖ０、Ｖ１、Ｃ０、Ｃ１、Ｖ、およびその後にＵ０またはＵ１を判定するのに十分な情報をＲｅｄに送信することだけが必要である。例えば、Ｖ０およびＶ１を送信する代わりに、Ｂｌｕｅは、Ｖ０およびＶを送信することができ、Ｒｅｄは、必要な場合にＶ／Ｖ０としてＶ１を再計算することができる。
【００９９】
コミットメントを、Ｅｌ  Ｇａｍａｌ暗号化を用いるものなど、コミットメントの他の技法に基づいて、決定論的に計算しないことが可能である。この場合に、通常は、クライアントがコミットメントをＢｌｕｅに送信し、Ｂｌｕｅが、多分別の当事者（例えばＲｅｄ）との相互作用によって、再計算せずにコミットメントを検証する。
【０１００】
ここおよび他所で、
【０１０１】
【数１１】
0004639084.tif 000012
【０１０２】
などの表記を、一般に、クライアントとＲｅｄによって共有される鍵Ｒ’を用いる値Ｃの適当な認証を示すものとして理解されたい。当技術分野で周知のように、ＭＡＣ鍵は、Ｒ’から導出される異なる鍵とすることができる。より一般的には、ＭＡＣ鍵は、上で述べた例に似て、クライアントとＲｅｄの間で確立されるベース値から導出される異なる鍵とすることができる。ＭＡＣへの入力に、値Ｃに加えて、ＭＡＣの意図を示すあるコンテキスト情報（すなわち、本明細書の他所に記載の鍵Ｒ’を用いるＭＡＣの別の応用のように、別のタイプの値ではなく値Ｃを認証するためのものであること）を含めることができる。その代わりに、鍵Ｒ’を用いて複数の値が認証されなければならない場合に、ＭＡＣを、鍵Ｒ’または関連する鍵を用いて、複数の値を表す適当な入力に基づいて計算することができる。また、一般に、トランザクションにパラメータを関連付けるのに有用と一般にみなされる、他のパラメータを、１方向関数への入力に含めることができる。
【０１０３】
図６に、図５の匿名証明プロトコルと共に使用できる反射対抗プロトコルを示す。下で説明するように、このプロトコルは、反射攻撃からシステムを保護するように設計されている。
【０１０４】
クライアントがプライベートチャネルを介してＲｅｄおよびＢｌｕｅと直接に通信する場合に、サーバのいずれかを制御する敵対者は、１つの共有から導出されるデータだけにアクセスできるので、反射攻撃を開始する能力を有しない。しかし、クライアントがＢｌｕｅを介してＲｅｄと通信する上の実施形態では、もやはそうではない。実際に、クライアントによってＲｅｄに送信される共有の新鮮さを保証する追加機構がなければ、Ｂｌｕｅを制御する敵対者が、単純にクライアントからの通信のすべてを繰り返すことによって、反射攻撃を開始することができる。敵対者は、この形でパスワードＰを学習しないが、敵対者は、成功裡の認証を不正にシミュレートすることができる。
【０１０５】
単純な対抗策は、タイムスタンプを使用することである。具体的に言うと、Ｂｌｕｅは、現在時刻をクライアントに送信することができる。他の情報と共に、クライアントは、このタイムスタンプのＲ’の下でのＭＡＣを送信する。Ｒｅｄが、ユーザパスワードごとに成功裡の認証に付随する最新のタイムスタンプを保管するならば、Ｒｅｄは、関連するタイムスタンプがパスワードについて保管された最新のタイムスタンプの後に続くことを検証することによって、受信した共有の新鮮さを検証することができる。しかし、この手法の短所は、時刻同期化要件によって導入されるエンジニアリングの複雑さである。
【０１０６】
代替手法では、カウンタの使用が用いられる。この手法では、ＢｌｕｅおよびＲｅｄが、ユーザパスワードごとに、成功裡の認証の試みの数をログ記録するカウンタを維持する。Ｂｌｕｅは、ログインの時にクライアントに最新のカウンタ値を供給し、クライアントは、Ｒｅｄに転送される保全性を保護されたベリファイヤとして、このカウンタのＲ’の下でのＭＡＣを送信する。このベリファイヤを使用することによって、Ｒｅｄは、関連するログイン要求の新鮮さを確認することができる。
【０１０７】
上で説明したカウンタ手法の短所は、アカウント情報の漏洩である。所与のユーザを装う攻撃者は、ユーザのパスワードのカウンタ値を知ることができ、したがって、ユーザのログインパターンに関する情報を収集することができる。Ｒｅｄを制御する敵対者は、さらに、認証の試みを開始せずに、したがって潜在的に疑わしい挙動に対してＢｌｕｅに警戒させる危険を冒さずに、そのカウンタ値を入手することができる。このカウンタ値をＲｅｄによって保管されたカウンタ値と突き合わせることによって、そのような敵対者は、匿名をユーザ識別に相関させることができる。
【０１０８】
したがって、平文のカウンタ値をクライアントに送信しないことが重要である。その代わりに、Ｂｌｕｅは、認証するクライアントに、主張されるユーザ識別のカウンタ値γのコミットメントζを送信することができる（例えば、参照によって本明細書に組み込まれる非特許文献７参照）。クライアントは、そのログイン情報にζのＲ’の下のＭＡＣを与えて、Ｒｅｄに転送する。認証要求を開始する時に、Ｂｌｕｅは、カウンタ値γおよびζに関連する証拠ρをＲｅｄに供給する。この２つのデータ、γおよびρが一緒になって、関連するカウンタ値をデコミットする。この形で、クライアントはγを学習しないが、カウンタ値γと所与の認証要求の間の束縛の保全性が保たれる。
【０１０９】
ハッシュ関数は、上で説明したコミットメント方式を実現する効率的な形を表し、ｒａｎｄｏｍ  ｏｒａｃｌｅ仮定の下で計算的に束縛的であり、隠蔽的である。具体的に言うと、Ｂｌｕｅは、ζ＝ｈ（γ‖ρ）としてγをコミットし、ここで、証拠ρ∈Ｒ｛０，１｝ｌは、適当なセキュリティパラメータｌに関する、長さｌのランダムビットストリングである。通常の実施形態で、ｌは、少なくとも１６０ビットの長さであることが好ましい。デコミットするために、Ｂｌｕｅは、γおよびρを供給し、Ｒｅｄがζの正しさを検証できるようにする。
【０１１０】
上で説明したプロトコルを、図６に示す。このプロトコルに関連する流れは、図３のプロトコルの認証部分として使用される図５の匿名証明プロトコルなど、前に説明した他のプロトコルの１つまたは複数の流れにオーバーレイすることができる。
【０１１１】
図６のプロトコルでは、γｂｌｕｅ，Ｕが、ログインを試みるユーザＵのパスワードアカウントについて保管されたカウンタ値を表し、γｒｅｄ，Ｕが、Ｒｅｄによって保管される対応するカウンタ値を表す。図６のプロトコルの最後に、クライアントによる成功裡の認証時に、Ｂｌｕｅは、γｂｌｕｅ，Ｕを１つ増分し、Ｒｅｄは、γｒｅｄ，Ｕを１つ増分する。この図の量Ｄは、上で説明した、ζのＲ’の下でのＭＡＣを表す。
【０１１２】
図５の匿名証明プロトコルをもう一度参照すると、Ｂｌｕｅは、アカウントＵのデータベースエントリにＶを保管することによって、その計算負荷を減らすことができる。Ｕに対する認証要求時に、Ｂｌｕｅは、Ｖ０＝ｆｘ（Ｕ０）およびＶ１＝Ｖ／Ｖ０を計算する。もう１つの可能な最適化が、クライアントに、Ｕ０およびＵ１’＝Ｕ  Ｕ０（（Ｕ１＝Ｕ／Ｕ０ではなく）にコミットさせ、対
【０１１３】
【数１２】
0004639084.tif 000013
【０１１４】
をＢｌｕｅに送信させることである。これによって、クライアントが、計算的により高価なモジュラインバージョンを剰余乗算に置換することによって、その計算負荷を減らすことが可能になる。図５のプロトコルの残りは、この場合にそれ相応に変更されなければならない。
【０１１５】
図５の匿名証明プロトコルの流れは、自然な形で、それぞれ図３および４に関して上で説明した基本認証プロトコルおよび同等性テストプロトコルの流れにオーバーレイすることができる。具体的に言うと、クライアントは、その認証情報および匿名証明情報を、Ｒｅｄの暗号化された共有を含めてＢｌｕｅにサブミットする。Ｂｌｕｅは、Ｒｅｄと共に図４の同等性テストプロトコルを実行する。これは、図５の匿名証明プロトコルに似て、３フローのプロトコルである。したがって、そのうちの２つを、３フローの過程で並列に実行することができる。図６の反射対抗プロトコルは、同様に、他のプロトコルに便利に一体化することができる。
【０１１６】
図５の匿名証明プロトコルおよび図６の反射対抗プロトコルを、本明細書で２つ以上のサーバを伴う認証プロトコルの文脈で説明したが、これらは、他の設定でのより一般的な応用を有する。例えば、これらを、フロントエンドサーバ（Ｂｌｕｅによって表される）を介してバックエンドサーバ（Ｒｅｄによって表される）のユーザにプライバシを提供することに適用することができる。共通の要素は、Ｂｌｕｅがクライアントに扮することができないように、クライアントが、あるトランザクションを実行する意図をＲｅｄに保証することである。しかし、クライアントおよびＲｅｄの両方が、クライアントの匿名を学習しない。
【０１１７】
Ｒｅｄのデータベースの内容のほとんどをＢｌｕｅにオフロードすることによって、Ｒｅｄに対する動作要件をさらに減らすことが可能であることに留意されたい。具体的に言うと、Ｒｅｄは、Ｒｅｄが保持する秘密鍵の下で暗号化されたアカウントレコードのそれぞれをＢｌｕｅに保管することができる。所与のアカウントの認証要求が開始される時に、Ｂｌｕｅは、適当な暗号化されたレコードをＲｅｄに送信する。レコードの新鮮さを保証するために、Ｒｅｄは、各アカウントのカウンタを保管し、現在のカウンタ値を最も最近のレコードに束縛することができる。これは、例えば、Ｒｅｄの秘密鍵の下でレコードおよびカウンタ値にＭＡＣを適用することによって、達成することができる。その代わりに、Ｒｅｄが、各アカウントの最も最近のレコードのハッシュを保管することができる。
【０１１８】
Ｂｌｕｅによる正しい匿名形成のより強い証明が、クライアントによる追加の暗号計算を用いて可能であることに留意されたい。この代替手法の例で、クライアントは、本質的にその識別に対するブラインデッドＥｌ  Ｇａｍａｌ暗号文の一種であるものを構築する。ユーザ識別子Ｕを用いて認証するために、クライアントは、暗号文（α，β）＝（ｙｋ，Ｕｇｋ）を構築する。ただし、
【０１１９】
【数１３】
0004639084.tif 000014
【０１２０】
である。Ｕに対する従来のＥｌ  Ｇａｍａｌ暗号文が、（Ｕｙｋ，ｇｋ）の形をとる、すなわち、平文Ｕが、対の第２成分ではなく第１成分に乗算されることを観察されたい。
【０１２１】
暗号文（α，β）は、標準Ｅｌ  Ｇａｍａｌ暗号化解除の下で、関連する平文がＵではなくＵｘであるという特性を有する。言い換えると、α／βｘ＝Ｕ−ｘ＝１／Ｖである。したがって、βｘ＝Ｖαである。したがって、この方式では、クライアントが、Ｖまたは秘密の１方向関数ｆｘを知らずに、匿名Ｖ＝ｆ（Ｕ）の逆数の暗号文を構築することができる。（α，β）を構築した後に、クライアントは、Ｒｅｄに送信したパスワード共有に基づく鍵を使用してＭＡＣを適用することによって、Ｒｅｄについてクライアントを認証する。Ｂｌｕｅは、この共有をＲｅｄに送信する時に、アカウント匿名Ｖ＝ｆｘ（Ｕ）をアサートする。Ｂｌｕｅは、１／Ｖが（α，β）に対応する平文であることの非対話型ゼロ知識証明を供給することによって、Ｖが正しいことを証明する。この証明は、ＤＬＥＱ［ｇ，ｙ，β，Ｖα］の形になる。
【０１２２】
より一般的に、クライアントは、好ましくはｑ’に対して素である整数ｄについて、暗号文（ｙｋ，Ｕｄｇｋ）を構築することができる。この場合に、標準Ｅｌ  Ｇａｍａｌ暗号化解除の下での関連する平文は、Ｖ−ｄであり、証明は、ＤＬＥＱ［ｇ，ｙ，β，Ｖｄα］の形になる。例えばｄ＝−１の場合に、関連する平文は、Ｖ自体になる。
【０１２３】
より弱い匿名証明を使用することも可能である。例えば、ＲｅｄサーバがＢｌｕｅによる匿名の正しさを検証するはるかに単純な形は、Ｒｅｄが、証拠Ｗの下でアカウント識別子Ｕに対応するコミットメントＣＵ＝Ｃ（Ｕ，Ｗ）を匿名ＶのＲｅｄレコードに付随させることであり、このコミットメントＣＵは、登録中に計算される。アカウント識別子Ｕは、この手法では特定の群に属する必要がないが、証拠Ｗは、例えば１方向関数ｈおよびＢｌｕｅによって秘密に保たれる値σのｈ（Ｗ，σ）として、Ｂｌｕｅによって導出することができる。
【０１２４】
認証時に、クライアントは、アカウント識別子Ｕをその認証要求に束縛する。これは、例えば、クライアントが鍵Ｒ’の下でＵに対するＭＡＣを供給する、図５のプロトコルで使用されるものに似た手法を使用することによって可能である。Ｂｌｕｅは、単に証拠Ｗを供給することによって、Ｒｅｄに対して関連する匿名Ｖの正しさを証明し、このＷによって、コミットメントＣＵに関する検証が可能になる。この手法は、図５に関して上で説明したカットアンドチューズ証明より単純であり、効率的である。この手法は、アカウント識別子のＲｅｄへの短時間の露出を許すと言う短所を有する。言い換えると、この手法では、Ｒｅｄが、認証要求に関連するアカウント識別子を見、これらをセキュアに消去するものとして信頼されなければならない。
【０１２５】
匿名攻撃を防ぐもう１つの可能な手法は、Ｒｅｄが、τによってパラメータ化される、ある時間ウィンドウ内で、認証要求のレコードを保つことである。この手法では、クライアントは、その要求に時間依存値を含め、これを、所与のセッション内の後続の再試行に暗号的に束縛する。Ｒｅｄは、時間τより古い要求を、満了したものとみなす。したがって、Ｂｌｕｅは、このケースで、単一の署名に対する所与の認証だけを向ける、すなわち、所与のアカウントのユーザからのセッションごとに１回だけ匿名攻撃を開始することができる。Ｂｌｕｅが、多数の匿名攻撃を開始する場合には、Ｒｅｄは、失敗する認証の試みの異常な外見上誤ったパターンをユーザが報告することの結果として、これを検出することができる。しかし、この種の検出は、不確実である。この手法のもう１つの短所は、実装詳細の複雑さである。
【０１２６】
あるクラスのクライアントが、Ｊａｖａ（登録商標）アプレットを実行できないことが期待される。そのようなクライアントを、本明細書では「ゼロフットプリント（ｚｅｒｏ−ｆｏｏｔｐｒｉｎｔ）クライアント」と称する。これには、例えば、古臭いブラウザまたは低機能ブラウザを走らせるクライアントと、非常に制限的なセキュリティ設定を有するクライアントを含めることができる。説明を単純にするために「Ｇｒｅｅｎ」と呼ぶことができる第３のサーバを展開することによって、そのようなクライアントに対処することが可能である。Ｇｒｅｅｎは、プライベートチャネル、例えばＳＳＬリンクを介して、クライアントからパスワードを受け入れる。Ｇｒｅｅｎは、クライアントの代わりに上で説明したプロトコルを実行し、その後、パスワードを消去する。これは、もちろん、Ｒｅｄ／Ｂｌｕｅサーバコンフィギュレーションで使用可能なセキュリティの力をかなり減らし、サブミットされるパスワードの短期間の露出をもたらす。しかし、Ｇｒｅｅｎサーバの使用は、従来の単一サーバパスワードベース認証システムより優れた総合的セキュリティを有するシステムをもたらす。単一サーバシステムは、既に、短期間のパスワード露出によって引き起こされる脆弱性を有する。しかし、さらに、単一サーバシステムは、受動的攻撃者が、サーバデータベース内のすべてのパスワードのハッシュを入手することも許容し、オフライン辞書攻撃が可能になる。対照的に、Ｇｒｅｅｎを危険にさらす唯一の形は、短期間だけ露出されるパスワードを介するものである。したがって、Ｇｒｅｅｎに対する成功裡の攻撃は、かなりの数のパスワードを明らかにしなければならない場合に、永続的である必要がある。Ｇｒｅｅｎを、最も単純に別々のサーバとしてではなく、Ｂｌｕｅのモジュールとして展開できることに留意されたい。
【０１２７】
貧者の変形
ゼロフットプリントクライアントをサポートするさらに単純な手法が、本明細書で「貧者の変形」と称する図３のプロトコルの複雑さを減らした変形である。この複雑さを減らされたセキュア認証プロトコルは、クライアントだけではなく、サーバ自体が、計算集中型の暗号演算を実質的に実行しないように構成されている。図３のプロトコルに似て、貧者の変形には、登録部分と認証部分が含まれる。貧者の変形の登録部分および認証部分を、それぞれ図７および８に関して下で説明する。
【０１２８】
貧者の変形では、クライアントが、明示的な形でフロントエンドサーバにパスワードＰを明かし、フロントエンドサーバは、クライアントの代わりに分割を実行し、Ｐを消去する。この変形は、特殊目的ソフトウェアなしで展開でき、パスワードは、例えばＨＴＭＬブラウザを介してサブミットすることができる。クライアントとフロントエンドサーバの間のプライベートチャネルが、フォワードシークレシ（ｆｏｒｗａｒｄ  ｓｅｃｒｅｃｙ）を有すると仮定すると、前にサブミットされたパスワードは、フロントエンドサーバの状態が完全に危険にさらされている場合であっても、プライベートのままになる。
【０１２９】
図７に、貧者の変形の登録部分を示す。ユーザは、従来の「アウトオブバンド」方法を使用して自分の身元を証明すると仮定され、これらの相互作用は、この図には示されていない。ＢｌｕｅおよびＲｅｄは、長さｌのラダムビットストリングを用いるハッシングを介して、ユーザが供給したパスワードＰＵの間接共有を作成し、ｌは、セキュリティパラメータである。ここでは、Ｕが、どちらのサーバにも登録されていないと仮定する。そうでない場合には、サーバは、再登録の試みに対するめいめいの適当なポリシに従う。ｈ１およびｈ２が、衝突が困難な１方向関数を表すものとする。ユーザパスワードＰに基づく秘密値について消去を行わなければならないステップに関する明示的ガイドラインを提供する。ＰのハッシュであるＨが、Ｐに基づく副ハッシュである
【０１３０】
【数１４】
0004639084.tif 000015
【０１３１】
の消去の前に消去されることがわかる。これによって、Ｒｅｄからの応答を待っている間にＢｌｕｅのメモリにＨを保たないという些細な利益が提供される。攻撃者は、この期間中にも
【０１３２】
【数１５】
0004639084.tif 000016
【０１３３】
に対する辞書攻撃を開始することができるが、少なくとも、Ｈに直接にはアクセスできない。
【０１３４】
図８に、貧者の変形の認証部分を示す。この図では、Ｈ’が、パスワードＰ’Ｕにハッシュ関数ｈ１を適用した結果を表す。Ｒｅｄは、所与のアカウントＵの正しい入力鍵
【０１３５】
【数１６】
0004639084.tif 000017
【０１３６】
を受信する時に、保管された鍵（ｓＵ）を解放すると仮定する。そうでない場合に、Ｒｅｄは、拒絶メッセージを送信する。貧者の変形の目的は、Ｂｌｕｅ単独で所与の認証セッションを受け入れるか拒絶することを可能にすることと仮定する。より高度なセキュア認証プロトコルは、Ｂｌｕｅに対（ｓＵ，ｔＵ）をクライアントに送信させ、クライアントが値の対から鍵を導出できるようにすることによって達成することができる。これは、ＢｌｕｅへのｓＵの短期間の露出をもたらす。しかし、秘密がＢｌｕｅに永続的な形では保管されないと言う点で、貧者の変形の基本的セキュリティは変更されない。もう１つの拡張は、Ｂｌｕｅ自体が対（ｓＵ，ｔＵ）から鍵を再構築することである。
【０１３７】
この変形の様々な異なる実現が可能である。一例として、入力鍵
【０１３８】
【数１７】
0004639084.tif 000018
【０１３９】
を直接にＲｅｄに送信するのではなく、Ｂｌｕｅが、Ｒｅｄとの認証プロトコルを実行して、
【０１４０】
【数１８】
0004639084.tif 000019
【０１４１】
が正しいことを実証することができる。このプロトコルは、従来のＳＰＡＫＡ技法を含む、Ｒｅｄに認証するための標準的なパスワードベースプロトコルとすることができる。Ｒｅｄは、成功裡の認証時に他のエンティティに他の保管された情報へのアクセスを許可するのと同様に、保管された鍵ｓＵへのＢｌｕｅのアクセスを許可する。したがって、Ｒｅｄを、原理的に、ファイルサーバまたは類似するネットワークリソースとして実装することができる。
【０１４２】
Ｒｅｄは、入力鍵
【０１４３】
【数１９】
0004639084.tif 000020
【０１４４】
を検証することだけを必要とし、それを保管する必要はない。したがって、Ｒｅｄは、従来の認証プロトコルで使用される技法に似た技法を使用して、
【０１４５】
【数２０】
0004639084.tif 000021
【０１４６】
のハッシュ化されたバージョンをその代わりに保管することができる。Ｒｅｄは、上で説明したタイプのクライアントまたは第２システムのサーバの１つの役割を演ずることによって、入力キーを検証することもできる。
【０１４７】
もう１つの例として、入力鍵
【０１４８】
【数２１】
0004639084.tif 000022
【０１４９】
を、Ｈ’およびｔＵから導出される公開鍵／秘密鍵対の秘密鍵とすることができる。Ｂｌｕｅは、Ｒｅｄに認証するために公開鍵を用いる動作を実行し、Ｒｅｄは、秘密鍵を用いてそれを検証する。この場合に、
【０１５０】
【数２２】
0004639084.tif 000023
【０１５１】
ではなく公開鍵がＲｅｄに保管され、図７の登録プロトコルが、それ相応に変更される。
【０１５２】
ＲｅｄおよびＢｌｕｅは、ＳＳＬを介して確立されるものなどのプライベートチャネルを介して相互作用することができ、あるいは、認証プロトコルに応じて、値
【０１５３】
【数２３】
0004639084.tif 000024
【０１５４】
自体が、プライベートチャネルの確立を提供することができる。
【０１５５】
ＢｌｕｅがＲｅｄを認証する時に、Ｂｌｕｅは、それ自体が、まず保管されたｔＵ値との組合せを介してパスワードを「強化」するので、単なるクライアントのプロキシではない。Ｂｌｕｅが、同一のパスワードを用いてクライアントの代わり認証する単純なプロキシである場合に、Ｒｅｄが危険にさらされると、標準的なパスワードベースのプロトコルと同様に、攻撃者がパスワードに対する辞書攻撃を開始できるようになる。本発明の方法では、Ｒｅｄが危険にさらされる場合であっても、パスワードがプライベートのままになる。
【０１５６】
複数サーバ変形
多項式秘密共有の標準的技法を使用するｎ中ｋシステムに基づく変形形態など（例えば、参照によって本明細書に組み込まれる非特許文献８参照）、複数のサーバを有する変形を構成して、より強いセキュリティを提供することができる。しかし、２サーバプロトコルと同様に、このより強い変形は、クライアントの側での計算集中型計算をほとんどまたはまったく必要としない。
【０１５７】
複数のサーバ、すなわち一般的な数ｎ個のサーバ（ただしｎ≧２）に適する、図３のセキュア認証プロトコルの変形をこれから説明する。もちろん、図３のプロトコルのそのような複数サーバ変形は、冗長サーバの使用および複数の２サーバプロトコルの同時使用によって、単純に得ることができる。この変形には、その代わりに、ｎ個のサーバと閾値アクセス構造が含まれ、ｎ個のうちの少なくともｋ個のサーバが動作している場合に、ユーザが成功裡に認証できるようになっている。
【０１５８】
複数サーバ変形は、限られた数の単純なサーバ故障すなわち、すべてのサーバが正しく振る舞っているが、故障の可能性がある情況に対する堅牢性を提供する。この変形は、ビザンチン障害（Ｂｙｚａｎｔｉｎｅ  ｆａｉｌｕｒｅ）すなわち、サーバが悪意をもって振る舞う可能性がある障害の一般的な場合での堅牢性は提供しないが、ビザンチン堅牢性の問題は、下でさらに詳細に対処する。
【０１５９】
複数サーバ変形では、クライアントが、標準多項式秘密共有によって、複数のサーバの間でパスワードを分散する。パスワードＰは、ゼロ点ｐ（０）がパスワードの表現と等しいランダム多項式ｐによって登録される。クライアントは、主張されるパスワードＰ’を表す独立のランダム多項式ｐ’によって認証する。サーバの仕事は、ｐ（０）＝ｐ’（０）であるかどうか、またはこれと同等に、（ｐ−ｐ’）（０）＝０であるかどうかを、追加情報を漏らさずに判定することである。サーバは、各々の共有のブラインデッド変換を交換することによって達成する。言い換えると、サーバは、共有の値を隠すが、それでも条件
【０１６０】
【数２４】
0004639084.tif 000025
【０１６１】
をテストできるようにする暗号文を交換する。
【０１６２】
説明を明瞭にするために、マルチサーバ変形は、ｑが大きい素数、例えば長さ１６０ビットであるＺｑ上の体を使用すると仮定するが、体Ｆｑの他の表現を使用するように変形を拡張することが可能である。さらに、ｈが、衝突が困難なハッシュ関数｛０，１｝＊→Ｚｑであるものとする。Ｇが、Ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が困難である、公開された生成元ｇを有する次数ｑの群であるものとする。次の説明での用語「ブロードキャスト」は、個々のすべてのサーバへのあるデータの送信を示すのに使用される。実際には、真のブロードキャストチャネルの使用は必要でなく、この変形の有利な特徴である。Ｓｉが、ｉ番目のサーバを表し、［ｉ，ｊ］が、両端を含むｉとｊの間の整数の集合を表すものとする。最後に、λ０，ｊが、整数ｊでの多項式の評価を与えられた時の、Ｚｑ上の（ｋ−１）次多項式の自由項の再構築のためのラグランジュ係数を表すものとする。
【０１６３】
複数サーバ変形の登録部分では、パスワードＰが、次数ｋ−１のＦ上のランダム多項式ｐとして、ｐ（０）＝ｈ（Ｐ）になるようにエンコードされる。１≦ｉ≦ｎについて、クライアントは、サーバＳｉに点ｐ（ｉ）を送信する。
【０１６４】
認証部分では、クライアントが、次数ｋ−１のランダム多項式ｐ’を、ｐ’（０）＝ｈ（Ｐ’）になるように構成することによって、パスワードＰ’を提示する。１≦ｉ≦ｎについて、クライアントは、サーバＳｉに点ｐ’（ｉ）を送信する。ｎ個のサーバが、ｋ個の機能するサーバの集合で、Ｕによるすべてのログインの試みの一意のセッション識別子ＩＤＵに基づいて判断すると仮定する。例えば、各アカウントのカウンタを持たせ、カウンタ不一致の場合に停止させることによって達成することができる。一般性を失わずに、これをＳ１、Ｓ２，．．．，Ｓｋと表すことができる。ｒが、多項式ｐ−ｐ’を表すものとすると、各サーバＳｉが、それ自体の評価ｒ（ｉ）＝ｐ（ｉ）−ｐ’（ｉ）を計算できることが観察される。サーバは、次のステップを実行する。いつでも、サーバが、別のサーバから不正なデコミットメントを受信する場合に、そのサーバは、終了し、拒絶する。
【０１６５】
１．各サーバＳｉは、ランダムなブラインディング係数ｂｉ∈ＵＺｑを選択する。
【０１６６】
２．各サーバＳｉは、
【０１６７】
【数２５】
0004639084.tif 000026
【０１６８】
を計算し、コミットメントＣｉ＝Ｃ（μｉ，Ｕ，ＩＤＵ）をブロードキャストする。
【０１６９】
３．コミットメントのすべての集合
【０１７０】
【数２６】
0004639084.tif 000027
【０１７１】
を受信する時に、各サーバＳｉは、
【０１７２】
【数２７】
0004639084.tif 000028
【０１７３】
をブロードキャストする。
【０１７４】
４．ｊ＝２からｋについて：
ａ．各サーバＳｉは、ｄ＝ｉ＋（ｊ−１）ｍｏｄ  ｋおよび
【０１７５】
【数２８】
0004639084.tif 000029
【０１７６】
を計算する。
【０１７７】
ｂ．各サーバＳｉは、
【０１７８】
【数２９】
0004639084.tif 000030
【０１７９】
をブロードキャストする。
【０１８０】
ｃ．コミットメントのすべての集合
【０１８１】
【数３０】
0004639084.tif 000031
【０１８２】
を受信する時に、各サーバＳｉは、
【０１８３】
【数３１】
0004639084.tif 000032
【０１８４】
をブロードキャストする。
【０１８５】
ｄ．各サーバＳｉは、すべてのｄについてデコミットメント
【０１８６】
【数３２】
0004639084.tif 000033
【０１８７】
を検査する。
【０１８８】
５．サーバＳｉは、
【０１８９】
【数３３】
0004639084.tif 000034
【０１９０】
を計算する。
【０１９１】
６．ｗｉ＝１の場合に、サーバＳｉは、ｒ（０）＝０であると結論し、受け入れる。そうでない場合には、拒絶する。
【０１９２】
このマルチサーバ変形では、図３の２サーバプロトコルと同様に、クライアントが、登録および認証のどちらについても、計算集中型の暗号演算を実行する必要がないことを観察されたい。この変形のセキュリティを、Ｇ上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定およびハッシュ関数ｈの衝突の困難さに還元できることを示すことができる。しかし、敵対者が簡単にサービス拒否攻撃を開始できるという意味で、この変形ではセキュリティが限られていることに留意することが重要である。実際に、悪意のある敵対者は、単純に不正なブラインデッド共有値を供給することによって、認証の試みの誤った拒絶を引き起こすことができる。
【０１９３】
成功裡の部分集合が見つかるか完全な失敗が達成されるまで、網羅的な形でｋ個の共有のすべての可能な部分集合を検査することによって、最も単純にビザンチン障害の問題を回避することが可能である。この手法は、ｋ個の共有の異なる組合せによってそれぞれがインスタンス化される複数のパスワード推測を攻撃者が効果的に行うことを可能にするという危険を冒す。有効なパスワードがＧのごく小さいランダムな部分集合を占めるようにする、例えば、その範囲がＧの小さい部分集合を構成するハッシュ関数を使用してパスワードをＧに写像することによって、この問題を回避することができる。この手法は、多数のサーバがある時には、完全に非実用的である。しかし、少数のサーバだけがある時には、多少実現可能である。さらに、監査者は、クライアントを装うことによって、この手法を使用して、不正を働くサーバを検出し、除去することができる。
【０１９４】
ビザンチン堅牢性を有する代替の複数サーバ変形
これから、クライアントが計算集中型の暗号を使用せずに自分のパスワードに対する検証可能に正しいＥｌ  Ｇａｍａｌ暗号文をサブミットできるようにする、未分析のセキュリティを有する複数サーバプロトコル変形を説明する。考え方は、体ではなく、ＲＳＡ  ｍｏｄｕｌｕｓ  Ｎの環ＺＮ上の多項式を定義することである。しかし、この環は、
【０１９５】
【数３４】
0004639084.tif 000035
【０１９６】
内の要素の圧倒的な部分が乗算逆数を有すると言う意味で、ほとんど体である。クライアントは、ｐの点へのコミットメントの集合Ｃ＝｛（ｐ（ｉ））２  ｍｏｄ  Ｎ｝を計算し、これをすべてのサーバに送信する。クライアントは、個々の点ｐ（ｉ）もサーバＳｉに送信する。サーバは、Ｃの一貫性のあるバージョンに基づいて、存在する場合には多数決によって、判断する。
【０１９７】
このシステムでは、Ｅｌ  Ｇａｍａｌ暗号文が、多項式が構成される環と同一の次数Ｎの基礎になる群で作られる。具体的に言うと、サーバは、次数Ｎの
【０１９８】
【数３５】
0004639084.tif 000036
の部分群からなる群ＧでＥｌ  Ｇａｍａｌ暗号文を操作する。この部分群の生成元は、ｇ＝１＋Ｎである。これは、Ｐａｉｌｌｉｅｒ暗号法（参照によって本明細書に組み込まれる非特許文献９参照）のセットアップとして当業者に既知である。各サーバは、Ｅｌ  Ｇａｍａｌ暗号文Ｅ［ｇｐ（ｉ）］をポストし、Ｃで提供される、（ｐ（ｉ））２  ｍｏｄ  Ｎに関する非対話型ゼロ知識証明でその正しさを証明する。
【０１９９】
そのような証明は、周知の技法の単純な使用によって構成することができる（例えば、参照によって本明細書に組み込まれる非特許文献１０および非特許文献１１参照）。しかし、実用的な効率を達成するためには、変形を使用する必要が生じる場合がある（例えば、参照によって本明細書に組み込まれる非特許文献１２および非特許文献１３参照）。これらの変形は、未知の次数の群、例えばＲＳＡ  ｍｏｄｕｌｕｓ  Ｎ’の
【０２００】
【数３６】
0004639084.tif 000037
【０２０１】
の部分群で機能し、Ｓｔｒｏｎｇ  ＲＳＡ  Ａｓｓｕｍｐｔｉｏｎの追加の実施を必要とする。共有がポストされ、検証されたならば、サーバは、ユーザのパスワードに対する登録されたＥｌ  Ｇａｍａｌ暗号文に対してサブミットされたＥｌ  Ｇａｍａｌ暗号文を検査することができる。これは、例えば上で注記したＰＥＴプロトコルを使用して、セキュアに行うことができる。その結果は、完全なビザンチン堅牢性を有するプロトコル変形である。
【０２０２】
このプロトコル変形のセキュリティは、コミットメント（ｐ（ｉ））２  ｍｏｄ  Ｎがｐ（ｉ）に関する十分な情報を隠蔽する能力に依存する。この変形のセキュリティは、詳細には分析されていないが、Ｓｔｒｏｎｇ  ＲＳＡ  ＡｓｓｕｍｐｔｉｏｎおよびＧでのＤｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定に還元できると思われる。
【０２０３】
本発明のセキュア認証プロトコルの複数の例の応用をこれから説明する。次の説明では、説明を単純明瞭にするために、主に図３の２サーバプロトコルに言及するが、これらの応用は、一般に、貧者の変形および複数サーバ変形ならびに他の変形にも適用可能である。説明される例の応用は、ローミング認証、プロキシ署名、サインドアサーション（ｓｉｇｎｅｄ  ａｓｓｅｒｔｉｏｎ）、ライフクエスチョン、プライベート情報分割、プライバシ保護データマイニング、および２シードＲＳＡ  ＳｅｃｕｒＩＤ（登録商標）認証である。
【０２０４】
ローミング認証
前に説明したＦｏｒｄおよびＫａｌｉｓｋｉのシステムに似て、本発明のセキュア認証プロトコルは、ローミングユーザがセキュリティを強化された状態で認証をダウンロードすることを可能にするように適合することができる。図３のプロトコルを参照すると、２つの共有
【０２０５】
【数３７】
0004639084.tif 000038
【０２０６】
および
【０２０７】
【数３８】
0004639084.tif 000039
【０２０８】
の形で、ＢｌｕｅおよびＲｅｄにまたがって秘密鍵σＵを分散することができる（秘密鍵をまず生成してから共有に分割するか、まず共有を生成し、それらから秘密鍵を導出することができる）。ユーザが成功裡に認証する時に、２つのサーバが、その共有をユーザに解放する。
【０２０９】
Ｒｅｄがバックエンドサーバとして働く配置では、Ｒｅｄは、Ｒ’またはそれから導出された鍵の下で
【０２１０】
【数３９】
0004639084.tif 000040
【０２１１】
を暗号化でき、上で注記したように、Ｒ’は、認証のためにクライアントによって供給される共有である。
【０２１２】
より一般的に、秘密鍵または認証を、一方のサーバに保管された鍵を用いて暗号化することができ、暗号化の結果は、他方のサーバに保管される。成功裡の認証時に、一方のサーバは、暗号化鍵をクライアントに返し、他方のサーバは、暗号化された認証を返す。
【０２１３】
プロキシ署名
各サーバがユーザの認証の共有を使用して、ユーザの代わりに暗号動作を実行する、上記の代替手法が可能である。例えば、上の
【０２１４】
【数４０】
0004639084.tif 000041
【０２１５】
および
【０２１６】
【数４１】
0004639084.tif 000042
【０２１７】
は、それぞれ、ＲＳＡ署名鍵の共有とすることができる。標準的な閾値技法を使用して、ＲｅｄおよびＢｌｕｅが、ユーザによる成功裡の認証時に、ユーザの「プロキシ」としてユーザの秘密鍵を使用してデジタル署名を作ることができる。ここで、ユーザは、署名されるメッセージをサーバにサブミットする（サーバへの今認証されたチャネルによって提供される適当な保全性保護を用いて）。もちろん、暗号化解除など、他の形の暗号サービス委任も可能である。
【０２１８】
同等性テストプロトコルが成功する場合に、両方のサーバが、他方がユーザを成功裡に認証したことの保証を得る。原則として、サーバの一方が、その後、ユーザが両方のサーバによって認証されたことを保証された状態で、ユーザのプロキシとして単独で動作することができる。例えば、一方のサーバだけで、ユーザの代わりにデジタル署名を作ることができる。これは、クライアントではなくサーバの一方で共有
【０２１９】
【数４２】
0004639084.tif 000043
【０２２０】
および
【０２２１】
【数４３】
0004639084.tif 000044
【０２２２】
からユーザの秘密鍵を再構成することによって行うことができる。この形で、秘密鍵は、クライアントではなく、サーバの一方で一時的にのみ露出される。閾値技法に基づく手法は、さらに、秘密鍵が一時的にも露出されないという長所を有する。
【０２２３】
サインドアサーション
上のデジタル署名手法のもう１つの変形として、ＲｅｄおよびＢｌｕｅが、ユーザに関連する鍵ではなく、２つのサーバを表す鍵を用いて協同して署名を作ることができる。この署名は、例えばＳＡＭＬ（Ｓｅｃｕｒｉｔｙ  Ａｓｓｅｒｔｉｏｎ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）で指定されるものなど、ユーザによる成功裡の認証を他の頼る当事者に示すように働くことができる。これは、ユーザに関する認証情報またはサインドアサーションの発行のいずれかに関する単一の危険にさらされる点がないので、認証サービスに対する役に立つ機能強化である。もちろん、上で注記したように、別のコンフィギュレーションに、両方によるユーザの成功裡の認証時にサインドアサーションを発行するサーバが１つだけ含まれる。
【０２２４】
ライフクエスチョン
上で注記したように、多くのサービスプロバイダは、現在、登録時に、１組のライフクエスチョンすなわちユーザに関する個人的質問の組への回答を供給するようにユーザに要求する。そのような質問の例が、「在籍した高校の名前は？」である。失われたパスワードを回復するために、ユーザは、これらの質問に対する回答をもう一度供給する。サービスプロバイダは、供給される回答全体を検証する。ユーザが、十分に正しい回答、例えば５問中３問に応える場合に、サービスプロバイダは、忘れられたパスワードまたはＰＩＮを解放するか、ユーザがそれをリセットすることを許可する。
【０２２５】
本発明のセキュア認証プロトコルを使用して、例えばこの種の個人的質問に対する回答を個々のパスワードとして扱うことによって、これらの回答を保護することができる。しかし、そのような変形は、追加の設計特徴を必要とする。個人的ライフクエスチョンに対する推測攻撃を防ぐために、システムは、質問の集合全体に関する試みをスロットリングしなければならない。すなわち、質問に対する回答のすべてを、一緒に単一のアカウントに属するものとみなさなければならず、同時に検証するか、ポリシ判断で集合的にカウントしなければならない。例えば、異なるライフクエスチョンに対する回答に対応するプロトコル値を、集合としてＢｌｕｅおよびＲｅｄに送信し、並列に処理することができ、最終決断は、各値（およびある閾値）に関するプロトコルの成功に依存する。アカウント全体を、失敗した認証の試みの数に基づいてロックしなければならず、成功または失敗は、質問集合全体に適用されるシステムポリシである。
【０２２６】
実際には、１つのサーバ、例えばＢｌｕｅサーバだけが、ユーザのパスワードを管理することができる。ユーザは、ライフクエスチョンを介して両方に認証し、成功裡の認証の時に、１つのサーバが、ユーザが自分のパスワードをリセットすることを許可する。
【０２２７】
テーマに従ってライフクエスチョンをグループ化することも可能である。具体的に言うと、ユーザがテーマの組の中から選択でき、テーマのそれぞれに、テーマによって統一された質問の組が含まれるように、システムを構成することができる。例えば、「ロックンロール」テーマに、ロックバンドに関する質問を含めることができる。そのようなテーマベースの質問が、本明細書で使用される用語「ライフクエスチョン」に含まれることが意図されている。
【０２２８】
プライベート情報分割
認証は、ＲｅｄとＢｌｕｅの間で便利に分割できる、プライベート情報の唯一の形ではない。例えば、ライフクエスチョンシステムで、成功裡に認証されたユーザに、誤って回答された質問に対する回答を思い出させることが便利である。これらの回答は、既に２つのサーバにまたがって分割されているので、関連する共有をクライアントにダウンロードし、表示のために再アセンブルすることができる。クレジットカード情報、住所情報などの他のプライベートユーザ情報を、同様に、２つのサーバにまたがる共有を介して保護することができ、クライアントまたはいずれかのサーバで適当に再アセンブルすることができる。その代わりに、この情報を第三者に送信する、例えばクレジットカード情報を商人に送信することを望むクライアントについて、ユーザ情報を、成功裡のユーザ認証時にリモートでアセンブルすることができる。
【０２２９】
この拡張を見る１つの形が、Ｒｅｄが、一方はＢｌｕｅに関し、他方はクライアントに関する２つの鍵を保管できると考えることである。この形で、Ｂｌｕｅは、クレジットカード番号およびユーザプロファイルなど、ユーザが成功裡に認証された後に限って暗号化解除される情報を保管することができる。情報が、Ｂｌｕｅに解放された鍵を用いて保護される場合に、Ｂｌｕｅは、その情報をローカルに暗号化解除することができる。情報が、クライアントに解放された鍵を用いて保護される場合に、クライアントが、その情報を暗号化解除することができる。
【０２３０】
ライフクエスチョンに対する回答または他の秘密が、再構成を必要としない場合に、値自体ではなく、値の１方向関数を、前に説明したように分割することができる。
【０２３１】
プライバシ保護データマイニング
多数のユーザの２つのサーバにまたがるプライベート情報共有を与えられて、匿名データマイニングに適するように変える形で情報をブラインド化することが可能である。ユーザデータδが、ある適当な群で乗法的に共有され、共有δｒｅｄがＲｅｄによって保持され、δｂｌｕｅがＢｌｕｅによって保持され、δ＝δｒｅｄδｂｌｕｅであると仮定する。ｙが、対応する秘密鍵が２つのサーバによって共有されるＥｌ  Ｇａｍａｌ公開鍵であり、ｇが、基礎になる群の生成元であるものとする。Ｒｅｄが、ランダム暗号化係数ｋ０を使用してδｒｅｄで暗号文
【０２３２】
【数４４】
0004639084.tif 000045
【０２３３】
を構成し、Ｂｌｕｅが、δｂｌｕｅで類似する暗号文（α１，β１）を構成すると仮定する。暗号文（α，β）＝（α０α１，β０β１）が、Ｅｌ  Ｇａｍａｌの乗法準同形に起因して、対応する平文δを有することを観察されたい。
【０２３４】
そのような暗号文のリストを構成した後に、ＲｅｄおよびＢｌｕｅは、あるタイプの２サーバデクリプションミックス（ｄｅｃｒｙｐｔｉｏｎ  ｍｉｘ）ネットワーク（例えば、参照によって本明細書に組み込まれる非特許文献１４参照）として働くことができる。デクリプションミックスは、サーバの集合が入力として暗号文のリストをとり、秘密のランダム置換に従って並べ返られた対応する平文を出力する構成である。ミックスネットワークの特殊なセキュリティ特性は、サーバの過半数を制御しない敵対者が置換を判定できないという事実である。したがって、結果の出力に、すべての平文すなわちユーザのプライベート情報が、ＲｅｄまたはＢｌｕｅのいずれか単独によって個々の情報をその所有者に結び付けられないように、完全に匿名の形で含まれる。この情報は、例えば第三者への提示またはプライバシが保たれるターゲティングされた宣伝の実行（例えば、参照によって本明細書に組み込まれる非特許文献１５参照）など、ユーザ人口に関する有用な匿名化された統計を編集するのに使用することができる。
【０２３５】
プロファイル匿名化という考え方は、複数サーバの場合、ＲＳＡなどの他の非対称暗号法の使用、およびクライアント自体がミキシング用の暗号文を直接に用意するシナリオに、単純に拡張することができる。２サーバ設定では、ＲｅｄがＢｌｕｅに直接に匿名情報を供給する単純化が可能である。この場合に、Ｒｅｄが、１サーバデクリプションミックスとして働くこと、すなわち、各暗号文に関するＲｅｄの暗号化共有と共に、Ｂｌｕｅに再暗号化された暗号文のランダム置換を送ることが可能である。Ｂｌｕｅは、暗号文自体の暗号化解除を完了することができる。
【０２３６】
１サーバまたは２サーバのいずれかのミックスネットワークでの最強のセキュリティは、正しさを実施する構成を使用して達成可能である。そのようなミックスネットワークでは、各参加するサーバが、それがミキシング動作を正しく実行したことの証明と、それが正しい暗号化解除共有に寄与したことの証明を提供する。しかし、しばしば、ミキシング処理中にサーバが不正に振る舞う誘因は、小さい。その場合に、正しい挙動の証明を省略することが可能である。これによって、この方式がより効率的になるが、これは、ミックスが、最も強い意味で、過半数未満のサーバが受動的に危険にさらされることに対してのみ攻撃に抵抗することを意味する。
【０２３７】
本発明の複数サーバ認証変形のように、３つ以上のサーバがある場合に有用なミックスネットワークのもう１つの特性が、堅牢性である。これは、少数のサーバが何らかの形で故障する場合であってもミックスネットワークがそれに従って機能する特性である。
【０２３８】
Ｅｌ  Ｇａｍａｌ暗号文のミキシングに関する正しさおよび堅牢性を提供する最近のミックスネットワーク構成の例が、文献に記載されている（例えば、参照によって本明細書に組み込まれる非特許文献１６および非特許文献１７参照）。
【０２３９】
いくつかの場合に、ユーザプロファイル内の情報の１つが、標準的な長さ、例えば１０２４ビットの単一の非対称暗号文でのエンコーディングを可能にするのに長すぎる場合がある。そのような情報を、複数の非対称暗号文にまたがってエンコードすることができるが、これは、暗号文の非効率的なアセンブリおよび非効率的なミキシングにつながる可能性がある。この問題を迂回するために、本発明では、ハイブリッドミックスネットワークと称するものを使用することができる。この用語は、広義に、長い入力暗号文の効率的なミキシングを可能にするための、対称暗号と非対称暗号を組み合わせるミックスネットワークを指す。
【０２４０】
例えば、上で示した文献（非特許文献１４参照）のオリジナル提案は、ハイブリッドミックスネットワークと見ることができ、次のように本発明と共に使用するために適合することができる。ｍが、ミックスネットワークを介して渡される１つのユーザプロファイル情報であるものとする。ＲｅｄおよびＢｌｕｅの両方を用いる２サーバミックスについて、クライアントは、暗号文
【０２４１】
【数４５】
0004639084.tif 000046
【０２４２】
を供給することができ、ここで、
【０２４３】
【数４６】
0004639084.tif 000047
【０２４４】
は、例えば長い平文の標準公開鍵暗号化などのエンベローピングを使用する公開鍵ＰＫｉの下での暗号化を表す。ミキシング動作を実行するために、Ｒｅｄは、各入力暗号文の外側層を暗号化解除し、結果の暗号文のリストをランダムに置換し、Ｂｌｕｅに渡す。Ｂｌｕｅは、類似する動作を実行し、ランダムに置換し、結果の平文を出力する。Ｒｅｄだけを用いるハイブリッドミックスでは、クライアントが、Ｒｅｄに送信される暗号文
【０２４５】
【数４７】
0004639084.tif 000048
【０２４６】
を用意することで十分である。
【０２４７】
正しさおよび／または堅牢性などのセキュリティ特性が望まれる場合に、クライアントは、適当な特性を提供するハイブリッドミックス（例えば、参照によって本明細書に組み込まれる非特許文献１８および非特許文献１９参照）に適当な暗号文を用意することができる。
【０２４８】
図３のプロトコルの認証部分でパスワードの共有に使用される＋演算子を、実際には、例えばＸＯＲ演算子ではなく、Ｈでの剰余乗算を用いてインスタンス化できることに留意されたい。この場合、Ｈは、Ｅｌ  Ｇａｍａｌ暗号化およびミキシングに使用される乗法群である。この形で、サーバにまたがるパスワード共有およびミキシングに関する他のプライベート情報の共有の処理の調和をとることができる。
【０２４９】
２シードＲＳＡ  ＳｅｃｕｒＩＤ（登録商標）
ＲＳＡ  ＳｅｃｕｒＩＤ（登録商標）は、米国マサチューセッツ州ベッドフォードのＲＳＡ  Ｓｅｃｕｒｉｔｙ  Ｉｎｃ．社が市販する、ハードウェアベースのユーザ認証トークンである。これは、トークンおよび認証サーバによって共有される一意の秘密σによって機能する。一意の秘密σを、「シード」とも称する。トークンは、本質的に次のように動作する。毎分、トークンは、σおよび現在時刻ｔ（１分の粒度を有する）を擬似乱数ジェネレータｆに供給し、出力ｆ（σ，ｔ）を作ることによって計算される、数字の新しいシーケンスを含むパスコードを表示する。認証するために、ユーザは、このパスコードをクライアントに入力し、クライアントは、そのコードを検証のために認証サーバに送信する。このシステムでは、認証サーバが危険にさらされると、システムが危険にさらされる結果になる可能性がある。
【０２５０】
しかし、本発明の技法を使用すると、ＲＳＡ  ＳｅｃｕｒＩＤ（登録商標）または、秘密のシードおよび事項または他の変化する値の関数としてパスワードが変更される類似する動的認証方法の２サーバ変形または複数サーバ変形を構築することが可能である。１つのシードσを含めるのではなく、ユーザＵのトークンに、２つのシードσｒｅｄおよびσｂｌｕｅが含まれると仮定する。トークンは、Ｐ’＝ｆ（σｒｅｄ，ｔ）＋ｆ（σｂｌｕｅ，ｔ）を表示する。ここで、上と同様に、すべての算術が、適当な代数群で行われる。クライアントは、
【０２５１】
【数４８】
0004639084.tif 000049
【０２５２】
になるように、Ｐ’をランダムに共有
【０２５３】
【数４９】
0004639084.tif 000050
【０２５４】
および
【０２５５】
【数５０】
0004639084.tif 000051
【０２５６】
に分割する。次に、Ｒｅｄが、Ｐｒｅｄ＝ｆ（σｒｅｄ，ｔ）を計算し、Ｂｌｕｅが、同様に、Ｐｂｌｕｅ＝ｆ（σｂｌｕｅ，ｔ）を計算する。ユーザによって供給される共有の正しさを検査するために、２つのサーバは、図４の同等性テストプロトコルを使用して、Ｒｅｄによって計算される値
【０２５７】
【数５１】
0004639084.tif 000052
【０２５８】
およびＢｌｕｅによって計算される類似する値Ｑｂｌｕｅの同等性を検査する。このシステムでは、２つのサーバの１つを危険にさらす攻撃者は、まだ、成功裡に認証することができない。ユーザは、ＲＳＡ  ＳｅｃｕｒＩＤ（登録商標）システムのＰＩＮも使用できることに留意されたい。これらは、上で説明した技法を使用して、パスワードと同一の形で分割することができる。ＰＩＮおよびシードの両方が、２つのサーバの間で分割される場合には、一方のサーバが危険にさらされることが、ユーザの認証の１「要因」を手に入れるのにも不十分であり、ＰＩＮが一方のサーバに保管され、シードが他方のサーバに保管されるより直接的な手法に対する長所である。
【０２５９】
他のローミングプロトコルへの適用
上の応用は、全般的に、複数のサーバを使用する他のローミングプロトコルに適用可能である。例えば、これらを、Ｆｏｒｄ−Ｋａｌｉｓｋｉプロトコルに適用することができる。そのプロトコルでは、クライアントが、複数のサーバとの相互作用を介して、パスワードなどの弱い秘密から強い秘密を入手する。その後、強い秘密を適用して、認証を暗号化解除し、サーバに認証することができる。
【０２６０】
１つまたは複数のサーバでの認証は、クライアントがＦｏｒｄ−Ｋａｌｉｓｋｉプロトコルで強い秘密を入手した後に行われ、そのサーバによって、それ以上のサービス（ローカルなレコード保存以外）はユーザに与えられない。しかし、上述した様々な応用では、さらなるサービスが、サーバでの認証の後にユーザに与えられる。これと同一のサービスを、Ｆｏｒｄ−Ｋａｌｉｓｋｉプロトコルに適用することができる。
【０２６１】
具体的に言うと、Ｆｏｒｄ−Ｋａｌｉｓｋｉプロトコルでのサーバへのユーザによる認証の後に、サーバは、（ａ）認証の共有をユーザに供給し、（ｂ）ユーザの代わりにデジタル署名を計算するか他の暗号動作を実行し（１つのサーバで、または複数のサーバを用いる閾値技法を介して）、（ｃ）成功裡の認証のサインドアサーションを発行し（例えばＳＡＭＬアサーション）、（ｄ）ライフクエスチョンへの正しい回答のユーザによる提供に基づいてパスワードをリセットし、（ｅ）クライアントに、互いに、および／または別の当事者にプライベート情報の共有を供給することができる。プライバシ保護データマイニングは、一般に、２つのサーバが用いられるコンテキストにも適用可能であり、認証の処理と別々に実行することができる。
【０２６２】
次に、システムのセキュリティおよび信頼性を高めるように設計された複数の例のプロトコル拡張を説明する。これらの拡張は、先を見越したセキュリティおよびサービス拒否攻撃に対するセキュリティである。やはり、主に図３の２サーバプロトコルの文脈で説明するが、これらの拡張は、他の変形およびローミングプロトコルにも適用可能である。
【０２６３】
先を見越したセキュリティ
先を見越したセキュリティは、一般に、異なる時に両方のサーバが危険にさらされることに対するセキュリティを指す。考え方は、サーバにまたがる情報共有の周期的再ランダム化を実行することである。ＰｒｅｄおよびＰｂｌｕｅが、ＲｅｄおよびＢｌｕｅにまたがるパスワードＰの追加の共有を表すものとする。所与のパスワードＰの可能な再ランダム化手順の１つが、次である。
【０２６４】
１．サーバの１つ、例えばＢｌｕｅが、ρ∈ＲＨを選択し、ρをＲｅｄに送信する。
【０２６５】
２．Ｒｅｄが、ＰｒｅｄをＰｒｅｄ＋ρに更新する。
【０２６６】
３．Ｂｌｕｅが、ＰｂｌｕｅをＰｂｌｕｅ−ρに更新する。
【０２６７】
再ランダム化手順の前だけにＲｅｄを受動的に危険にさらすことを達成し、再ランダム化の後だけにＢｌｕｅを受動的に危険にさらすことを達成した攻撃者を検討されたい。そのような攻撃者は、ＰｒｅｄおよびＰｂｌｕｅ−ρを学習する。しかし、ρは、Ｐの共有と独立のランダムな値なので、Ｐ自体に関する情報は、攻撃者に明かされていない。同一の考え方が、攻撃の後にすべてのコードおよびデータが復元される場合に、敵対者が限られた時間期間だけ各サーバの能動的制御を達成する時にあてはまる。
【０２６８】
しかし、送信される値ρを保護するという追加の問題が残っている。Ｂｌｕｅが、Ｒｅｄに属する公開鍵ＰＫｒｅｄの下のプライベートチャネルを介してρを送信すると仮定する。受動的な形でＲｅｄを危険にさらした攻撃者は、対応する秘密鍵ＳＫｒｅｄを学習する。したがって、この攻撃者は、どちらのサーバの制御を有しない場合であっても、再ランダム化中の２つのサーバの間の通信を暗号化解除することができる。これは、ρを危険にさらすことをもたらし、先を見越したセキュリティ特性を傷つける。
【０２６９】
その結果、先を見越したセキュリティのもう１つの重要な要件が、サーバ（または、少なくともＲｅｄ）が、定期的にその公開鍵を更新することである。これは、例えば、証明機関（ＣＡ）への新しい証明書の定期的登録を介して達成することができる。攻撃者が、新しい公開鍵の登録時または再ランダム化手順中にサーバを制御しないならば、先を見越したセキュリティの望みの特性が達成される。ＲｅｄおよびＢｌｕｅは、共有チャネルでのフォワードシークレシを達成するために、アウトオブバンド対称鍵配布など、証明書リフレッシュ以外の機構も使用することができる。
【０２７０】
サービス拒否攻撃に対するセキュリティ
本発明のセキュア認証プロトコルの一部は、特にライフクエスチョン変形で、サーバに対する適度に高い計算の重荷を課す可能性がある。したがって、検討すべきもう１つのセキュリティ問題は、サービス拒否攻撃の問題である。攻撃者は、アカウントのロックダウンおよび多分いくつかのアカウントを危険にさらすことをもたらす正当なアカウントに対する推測攻撃と、サーバに対する維持できない計算の重荷を作る認証要求のすばやいサブミットとの組合せを介して、正当なユーザに対してサービスを拒否させることを求めることができる。次に、この種のサービス拒否攻撃を扱う複数の手法を説明する。
【０２７１】
サービス拒否攻撃の機先を制する手法の１つが、ＩＰトレーシングによって仮定の攻撃のソースを識別し、疑わしいＩＰアドレスへのサービスをスロットリングすることである。例えば、信頼性のあるＩＰトレーシングを容易にする機構が、Ｓｙｎｃｏｏｋｉｅｓ（例えば、参照によって本明細書に組み込まれる非特許文献２０参照）によって提供され、これは、現在、最新のＬｉｎｕｘオペレーティングシステムおよびＦｒｅｅＢＳＤオペレーティングシステムの標準部分である。しかし、攻撃者が、複数のＩＰアドレスを介してまたは正当なユーザの大きいベースと共有されるＩＰアドレスを介して攻撃を開始することを求めることができるので、ＩＰトレーシングは、いくつかの場合に限られた有用性を有する場合がある。
【０２７２】
サービス拒否攻撃をスロットリングするもう１つの手法が、攻撃が検出された時に、認証するクライアントにリソースチャージを課すことである。例えば、「クライアントパズル（ｃｌｉｅｎｔ  ｐｕｚｚｌｅ）」手法（参照によって本明細書に組み込まれる非特許文献２１参照）では、クライアントが、サービスを得るために、適度に困難な暗号「パズル」に対する正しい解をサブミットすることを要求される。これは、攻撃を開始するためにかなりの計算リソースを集めることを攻撃者に要求するという効果を有する。したがって、クライアントパズルは、大規模分散サービス拒否攻撃を開始する攻撃者に対する非常に限られた有用性を有する。
【０２７３】
代替の同盟手法では、クライアントに要求されるリソースを、認証プロセスへの人間の能動的な参加とすることができる。この手法は、複数のウェブサイトで採用されており、これらのウェブサイトは、ユーザに、サービスを得るために、ある時間制限以内に光学文字認識（ＯＣＲ）に基づく問題を解くように要求する。この問題は、コンピュータによって効果的に解くことができないが、人間にとって比較的簡単と思われるものである。例えば、ＡｌｔａｖｉｓｔａのＵＲＬサブミッションサービスを参照されたい（例えば、非特許文献２２参照）。
【０２７４】
複数の不成功のログインの試みの後に所与のアカウントをロックダウンすることの代替案が、ある時間期間の間、そのアカウントに対する認証要求を拒否することである。これは、アカウント識別子の小さい集合だけを知っている攻撃者の側での推測攻撃を低速にさせるという効果を有する可能性がある。しかし、多数のアカウント識別子のリストを有する攻撃者は、単純にこのリストを通って、遅延が課せられるまで所与のアカウントを攻撃し、その後、新しいアカウントに移ることができる。
【０２７５】
アカウントロックダウンを伴うサービス拒否攻撃は、正当なユーザによる誤ったログインの試みによってさらに悪化する可能性がある。具体的に言うと、そのような正当なユーザは、失敗した認証の試みのカウントを故意でなく増やす。経時的に個々のアカウントに対する失敗の総数を登録するシステムでは、これが、早めのアカウントのロックダウンをもたらす場合がある。この問題に対する部分的解決策が、「弁解（ａｐｏｌｏｇｙ）」機構によって提供される（例えば、参照によって本明細書に組み込まれる非特許文献２３参照）。この提案は、次の通りである。成功裡に認証する時に、ユーザは、自分の前の誤った試みを認め、これによって、対応するユーザアカウントに対する誤った試みのレコードからこれらを除去することができる。
【０２７６】
上で説明した特定のセキュア認証技法が、例として提供されたものであり、本発明を特定の実施形態または実施形態のグループに制限するものとして解釈されてはならないことをもう一度強調する必要がある。さらに、様々な例示的実施形態の説明の過程で上で行った様々な単純化の仮定は、本発明の要件または制限ではなく、例示とみなされなければならない。請求項の範囲内の多数の代替実施形態が、当業者にすぐに明白になる。
【図面の簡単な説明】
【０２７７】
【図１】本発明の暗号技法を実施できる例のシステムを示す単純化されたブロック図である。
【図２】図１のシステムのクライアントデバイスまたはサーバデバイスの所与の１つの１つの可能な実施形態を示す図である。
【図３】本発明の技法による、図１のシステムのクライアントおよび１対のサーバを用いるセキュア認証プロトコルの例示的実施形態の登録部分および認証部分を示す流れ図である。
【図４】本発明による図３のプロトコルの認証で使用される同等性テストプロトコルを示す図である。
【図５】本発明による図３のプロトコルの認証部分で使用される匿名証明プロトコルを示す図である。
【図６】図５の匿名証明プロトコルと共に使用される反射対抗プロトコルを示す図である。
【図７】図３の実施形態に関して減らされた計算の複雑さを有する本発明の代替実施形態によるセキュア認証プロトコルの登録部分を示す図である。
【図８】図３の実施形態に関して減らされた計算の複雑さを有する本発明の代替実施形態によるセキュア認証プロトコルの認証部分を示す図である。
【図１】
0004639084.tif 000053
【図２】
0004639084.tif 000054
【図３】
0004639084.tif 000055
【図４】
0004639084.tif 000056
【図５】
0004639084.tif 000057
【図６】
0004639084.tif 000058
【図７】
0004639084.tif 000059
【図８】
0004639084.tif 000060