(57)【要約】  パスワード（π）を用いて、クライアント（Ｃ）が、サーバ（Ｓ）のパスワード検証情報の一部（Ｈ１（＜Ｃ，πＣ＞））を計算し、クライアント（Ｃ）及びサーバ（Ｓ）は共にこの情報を用いて互いを認証し、オフライン辞書攻撃に耐性を有する方法を用いて、暗号鍵(Ｋ’)を確立する。その後、サーバは、暗号鍵に基づく安全なチャネル上で、サーバが検証鍵(ｐｋ)を知っている署名スキームに対して、署名鍵（ｓｋ）の暗号（ＥＥ＜Ｃ、π＞（ｓｋ））を送信する。暗号は、非展性であり、及び／又は、復号可能な部分（Ｅ＜Ｃ、π＞（ｓｋ））及び、復号可能な部分を復号して得られた復号値の検証のために用いる検証部分(Ｈ８（ｓｋ）)を含む。署名鍵は、パスワードに基づくものであり、サーバに知られていない。クライアントは、パスワードを用いて署名鍵を取得し、メッセージに署名し、署名をサーバに返す。サーバは、検証鍵を用いてメッセージを検証するため、クライアントがパスワードを知っていることの別の証明を得る。クライアント及びサーバは、その後の通信のためにパスワードよりも安全な共有秘密鍵(Ｋ”)を生成する。
2009503934.tif 000002
【特許請求の範囲】
【請求項１】
第１コンピュータシステムが第２のコンピュータシステムに対して所定の値πを知っていることを証明する暗号認証方法を行うためにコンピュータに実装される方法であって、
前記第１のコンピュータシステムは、
（１）前記第１及び前記第２のコンピュータシステムの少なくとも一方に対して、前記第１及び前記第２のコンピュータシステムの他方が、前記値πの所定関数を知っていることを証明するプロトコルを実行し、前記プロトコルにおいて用いられるデータを使って暗号鍵Ｋ’を生成する工程と、
（２）ネットワーク上で第１の値を受信する工程と、
（３）前記第１の値に対して復号方法を適用し、復号値を取得する工程と、
（４）前記工程（３）で取得された前記復号値から取得される署名鍵を有するメッセージに対するデジタル署名を生成する工程と、
（５）前記デジタル署名を前記第２のコンピュータシステムに組み込むデータを送信する工程とを有し、
前記復号方法は、
（３Ａ）ｃが、Ｍとは別の任意のｆに対して
【数１】
2009503934.tif 000058
と等しくない（すなわち、前記値
【数２】
2009503934.tif 000059
は、Ｍに基づく）ように、Ｍを第１の暗号値ｃに暗号化する第１の暗号方法と、
（３B）前記第１の暗号値ｃを、前記暗号鍵Ｋ’を用いて第２の暗号値に暗号化する第２の暗号方法と
を用いて暗号化された任意の値Ｍを復号するための方法である
ことを特徴とするコンピュータに実装される方法。
【請求項２】
第１のコンピュータシステムが第２のコンピュータシステムに対して所定の値πを知っていることを証明する暗号認証方法を行うためにコンピュータに実装される方法であって、
前記第２のコンピュータシステムは、
（１）ネットワーク上でデータの送受信を行い、前記第２のコンピュータシステムに対して、前記第１のコンピュータシステムが前記値πの所定関数を知っていることを証明するプロトコルを実行する工程と、
（２）前記値πを用いて値Ｍを暗号化する第１の暗号方法により、署名鍵の暗号化に等しい第１の暗号値ｃを取得する工程と、
（３）第２の暗号方法を適用し、前記プロトコルにおいて用いられるデータを用いて取得された暗号鍵Ｋ’を用いて、前記第１の暗号値ｃを第２の暗号値に暗号化する工程と、
（４）前記第２の暗号値を含むデータを前記第１のコンピュータシステムに送信する工程と、
（５）ネットワーク上で値を受信し、前記署名鍵に対応する検証鍵による検証方法を適用し、受信した前記値がメッセージに対する有効な署名であることを検証する工程とを有し、
ｃは、Ｍとは別の任意のｆに対して
【数３】
2009503934.tif 000060
に等しくない（すなわち、値
【数４】
2009503934.tif 000061
はＭに基づく）値であることを特徴とするコンピュータに実装される方法。
【請求項３】
請求項１に記載の方法を実行するように構成されているコンピュータシステム。
【請求項４】
請求項１に記載の方法を実行するコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【請求項５】
請求項２の方法を実行するよう構成されているコンピュータシステム。
【請求項６】
請求項２の方法を実行するコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の説明）
本願は、２００５年７月１９日に出願された米国仮特許出願第６０／７００７６９号に対する優先権を主張する。本明細書中、同文献を参考のため援用する。米国指定により、優先権の主張は、米国特許法第１１９条（ｅ）に基づく優先権を含む。
【０００２】
また、本願は、Ｃｒａｉｇ  Ｂ．Ｇｅｎｔｒｙ、Ｐｈｉｌｉｐ  Ｍａｃｋｅｎｚｉｅ及びＺｕｌｆｉｋａｒ  Ａｍｉｎ  Ｒａｍｚａｎによって２００６年７月１４日に出願された「展性攻撃に対して改良された安全性を有する技術（これに限定されない）を含む非ワンタイムパッド暗号で暗号化した署名鍵を用いた、暗号認証、及び／又は共有暗号鍵の設定(CRYPTOGRAPHIC AUTHENTICATION, AND/OR ESTABLISHMENT OF SHARED CRYPTOGRAPHIC KEYS, USING A SIGNING KEY ENCRYPTED WITH A NON-ONE-TIME-PAD ENCRYPTION, INCLUDING (BUT NOT LIMITED TO) TECHNIQUES WITH IMPROVED SECURITY AGAINST MALLEABILITY ATTACKS) 」と題される米国非仮特許出願第       号に対する優先権を主張する。米国指定により、本願は、上述した非仮特許出願の継続出願である。
【０００３】
本発明は、暗号に関し、より具体的には、認証及び、二者が情報を有する（できれば短い）秘密を用いて共有暗号鍵を設定することに関する。
【背景技術】
【０００４】
アリスとボブの二者を考えてみる。アリスとボブは、ロジック処理を実行可能な、ハードワイヤード、及び／又は、ソフトウエアプログラマブルな回路を用いて実装され得る。ここで、アリスとボブが、それぞれが本人であることを検証する手段として短い秘密のパスワード（例えば、４桁の暗証番号）を用いて、安全でないネットワーク上で、安全に通信したい場合を考える。なお、アリスはその短い秘密のパスワードの、パスワードそのものを知っており、ボブは、少なくとも、ある「パスワード検証情報」を知っている。具体的には、どちらも他者に対応する公開鍵を知らず、認証公開鍵（すなわち、その認証を他者が検証可能な公開鍵）も持っていないことが想定される。このシナリオでは、アリスは、彼女の会話を盗み聞きしてパスワードを盗もうとしている盗聴者に注意しなければならないだけでなく、彼女が会話している相手がボブであるかどうか予め確信することもできないので、会話している相手にも注意しなければならない。ボブの置かれた状況も同様である。
【０００５】
アリスとボブが、強い暗号鍵（すなわち、長い秘密）を共有している場合、この問題は、ＢｅｌｌａｒｅやＲｏｇａｗａｙのプロトコルなど、安全なチャネルを設定する技術で公知である標準的な解決方法により解決することができるだろう［４］。しかし、アリスとボブは、短いパスワードについての情報しか持っていないので、オフライン辞書攻撃にも気をつけなければならない。オフライン辞書攻撃は、攻撃者がパスワード推測をオフラインで検証するために用いることが可能なパスワード検証情報を取得した時に発生する。例えば、アリスとボブがパスワードπを共有しており、攻撃者が、ある方法でそのパスワードのハッシュｈ（π）を入手したものとする。ここで、ｈは、ＳＨＡ−１などの共通暗号化ハッシュ関数である［３９］。そうすると、攻撃者は、オフラインにして、パスワード候補の辞書｛π１，π２，・・・｝を用いて、それぞれのパスワード候補をｈ（π）に対してテストする。例えば、πｉが正しいパスワードかどうかを調べる場合、攻撃者は、ｈ（πｉ）を計算し、ｈ（πｉ）＝ｈ（π）であるか否かを調べる。一般的に、攻撃者が入手したパスワード検証情報は、パスワードのハッシュのようにシンプルではなく、攻撃者は、そのパスワード検証情報に対する可能なパスワードの全てを調べることができるとは限らない。しかし、攻撃者が非常に多くのパスワードを調べることが可能である場合は、これは、オフライン辞書攻撃であると見なされる。Ｗｕ［４７］は、オフライン辞書攻撃がどの程度有効であるかを説明している。
【０００６】
従って、アリスとボブとが、短い秘密（パスワード）の情報から、安全なチャネルを提供するために使用可能な長い秘密（暗号鍵）を導き出すことができるように、アリスとボブの間の通信用プロトコルを設定することが望ましい。
【０００７】
そのようなプロトコルは、当技術分野では、パスワード認証鍵交換（ＰＡＫＥ）プロトコルと呼ばれる。プロトコルを攻撃する実行可能な方法が、反復的にパスワードを推測し、一方になりすます、単純なオンライン辞書攻撃である場合、ＰＡＫＥプロトコルは、非公式にではあるが、安全である（このタイプの攻撃は、一般に検出可能であり、以下に説明するように公知の方法によって停止させることができる）。安全なＰＡＫＥプロトコルを設計する際の問題点が、ＢｅｌｌｏｖｉｎとＭｅｒｒｉｔｔ［６］及び、Ｇｏｎｇ等［２１］によって提唱されており、以来、広範囲に研究されてきた。
【０００８】
ＰＡＫＥプロトコルにおいて、アリスとボブの一方をクライアントと指定し、他方をサーバと指定したとする。このとき、例えサーバがセキュリティ侵害の危険に晒されても、少なくもとオフライン辞書攻撃を実行せずに、クライアントになりすますために使用され得るいかなる情報も漏らさない場合、ＰＡＫＥプロトコルは、サーバの危殆化に対して耐性を持っていると言える。そのようなプロトコルは、拡張ＰＡＫＥプロトコルとも呼ばれる。この拡張ＰＡＫＥプロトコルの設計上の問題は、Ｂｅｌｌｏｖｉｎ及びＭｅｒｒｉｔｔによって提唱されており［７］、広範囲に研究されてきた。上述したように、この問題を解決するために提案されてきた当技術分野における多くの技術について以下に述べる。
【０００９】
ＰＡＫＥの重要な適用方法のひとつは、公開鍵基盤（ＰＫＩ）を導き出すことである。具体的には、ユーザは、ＰＡＫＥプロトコルを用いて信用できる記憶装置への安全なチャネルを設定し、公開鍵の証明書と対応する秘密鍵とを安全にダウンロードする。よって、ユーザは、ラップトップコンピュータの盗難（これ自体大問題であるが）、あるいは、単なる紛失、ユーザがディバイスを地面に落としてハードドライブを破損させたりする恐れのあるローカルディバイス上に、ユーザの秘密鍵を記憶させておくことに注意を払う必要はない。ＰＡＫＥプロトコルをそのように用いる一例として、Ｐｌａｎ９がある。より具体的には、Ｐｌａｎ９におけるＳｅｃｕｒｅＳｔｏｒｅである。
【００１０】
従来の解決方法
当技術分野における共通パスワード認証技術の多くは、一方向認証技術である。つまり、一方（ユーザ又はクライアント）のみが、他方（サーバ）に対して認証され、その逆は存在しない認証技術である。（一方、上述したＰＡＫＥプロトコルは、双方向認証技術である。）説明をしやすくするために、以下では、２者アリス及びボブを説明するのに、クライアント及びサーバというラベルを用いるが、これらの用語は、単に便宜上のラベルにすぎないことに留意されたい。
【００１１】
簡単な技術のひとつは、クライアントが、サーバに対して、何らかの暗号的な保護なしに、パスワードを送ることである。このタイプの認証は、旧式のインターネットアプリケーションや、多くのウェブメールアプリケーションにおいて用いられている。しかしながら、これは、ネットワーク上の盗聴者に対して危険である。この技術は、盗聴が比較的困難なチャネルに対しては許容できるものである。
【００１２】
より高度な技術としては、チャレンジ／レスポンス方式がある。これは、サーバがチャレンジをクライアントに送信し、クライアントが、例えば、チャレンジとパスワードとの連結に対するハッシュなどの、チャレンジとパスワードに基づくメッセージを用いてレスポンスを行うものである。このタイプの認証は、ネットワークアクセスを可能にするいくつかのオペレーティングシステムにおいて用いられる。しかしながら、この技術は、盗聴者によるオフライン辞書攻撃に対して脆弱である。なぜなら、チャレンジ及びそれに対応するレスポンスが、共にパスワード検証情報を構成するからである。通信を盗聴している攻撃者は、会話の写し（すなわち、チャレンジとハッシュ値）を受け取り、パスワードが合致するまで、全ての可能なパスワードを試すことができてしまう。
【００１３】
より安全性の高い技術には、匿名の安全なチャネルにより、公開鍵を用いて検証されるサーバに対して、パスワードを送信するものが含まれる。このタイプの認証は、遠隔端末アプリケーションやウェブベースのアプリケーションにおいて用いられており、サーバの公開鍵を検証するクライアントの性能に本質的に基づいている。ウェブを用いる場合、サ―バの公開鍵は、クライアントが信頼している認証機関によって証明される。遠隔端末アプリケーションの場合、通常は、信頼できる第三者が存在せず、安全性は、公開鍵の「指紋」やハッシュにより、公開鍵を認識するクライアントに依存している。サーバの公開鍵が検証可能である限り、このタイプの認証は安全である。しかしながら、サーバの公開鍵が検証できない場合、このタイプの認証は、サーバへのなりすましが可能な攻撃者に対して脆弱である。例えば、このことは、ウェブに基づくアプリケーションにおいては、攻撃者が不正に証明書を取得する場合に発生し、遠隔端末アプリケーションにおいては、クライアントマシーンがサーバの公開鍵を予め記憶していない場合に発生する。
【００１４】
したがって、オフライン辞書攻撃の恐れのないパスワード認証鍵交換（ＰＡＫＥ）アルゴリズムを見つけることが要求される。そのような安全性は、少なくともどの当事者もセキュリティ侵害の危険に晒されない場合に実現されるはずである。当事者が、敵対者によってセキュリティ侵害の危険に晒されている場合、敵対者は、オフライン辞書攻撃に対するセキュリティを破るパスワード検証情報を入手することができる。しかしながら、例えば、サーバがセキュリティ侵害の危険に晒されている場合、オフライン辞書攻撃の間にセキュリティが破られても、プロトコルは、サーバの危殆化に対して耐性を持つことが望ましい。
【００１５】
オフライン辞書攻撃から守ることが、ＰＡＫＥプロトコルの目的であることがわかる。ＰＡＫＥの問題が紹介されて以来、広範囲に研究されてきており、多くのＰＡＫＥプロトコルが提案されてきた。例えば、［７、２１、２０、２４、２５、３４、４５、４６、３３、３２］。これらのプロトコルの多くが安全でないことが示されてきた［１０、４０］。そのため、合理的な暗号的仮定により安全であると証明可能なプロトコルを開発することが望ましい。また、これらのプロトコルの多くは、サーバの危殆化に対して耐性を持つことも必要とする。例えば、［７、２５、４６、３３、３８］。そして、合理的な暗号的仮定によりサーバの危殆化に対して耐性を持つと証明可能なプロトコルを開発することが望ましい。
【００１６】
より最近のＰＡＫＥプロトコルは、公知の暗号学的仮定に基づく安全性の証明を有している。これらの証明のいくつかは、理想的なハッシュ関数（ブラックボックスでランダムな関数）や理想的な暗号（鍵置換）の存在を仮定するものではあるが。そのような方法は、自らの研究の安全性の数学的証明を他の当業者に提供するために、暗号技術分野の当業者が一般に用いている。最近の論文のいくつか［２、１２、１］では、［７］のＥＫＥプロトコルの改良点が論じてあり、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＨ）仮定に基づく安全性を証明している［１６］。第１の論文は、理想的な暗号文及び理想的なハッシュの両方を仮定し、他の論文は、理想的なハッシュだけを仮定している。他の論文［３５、５１］では、［３４］のＯＫＥプロトコルの改良点が論じられ、ＲＳＡ仮定［４２］に基づいた安全性が証明される。これら全ては、理想的ハッシュを仮定するものである。他の論文［３０］では、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号システム［１５］の改良に基づいた新しいプロトコルが発表され、（理想的ハッシュ関数ではなく）公開ランダム文字列だけを仮定する、決定ＤＨ仮定（例えば、［１１］参照）に基づいた安全性が提供されている。プロトコル［３０］のいくつかの改良が、［１８、２９、１３］に発表されている。別のパスワード認証鍵交換プロトコルについては、［１９］に展開されており、セットアップ仮定ではなく、同じパスワードの同時セッションを禁止する規制を用いる落とし戸順列に基づいて、安全性が証明されている。
【００１７】
サーバの危殆化に対する耐性という点において、以下の論文には、理想的ハッシュ関数が存在すると仮定することで安全性が証明されたプロトコルが含まれる［１２、３７、３５］。
【００１８】
ＰＫＩを導き出すためには、完全なＰＡＫＥプロトコルが必要であるわけではなく、一連の証明書（又は、少なくとも、暗号化された証明書を復号するのに用いられる統計的な暗号鍵）をダウンロードするためのパスワードに基づくプロトコルだけが必要であることが知られている。これを実践するプロトコルが、［１７］であり、その改良が［２６］である。これらのプロトコルの安全性は、Ｄｉｆｆｉｅ  Ｈｅｌｌｍａｎに関連した標準的ではない仮定に基づいている。
【００１９】
従来のパスワード認証鍵交換スキームは、商業製品に実装し、いくつかの技術標準内で用いるように指定されてきた。ＳＲＰプロトコル［４６］は、ｔｅｌｎｅｔ及ｆｐｔを含む多くのアプリケーション用に実装されてきた［５０］。ＳＲＰに関連する二つのＩＥＦＴのＲＦＣとしては、ＲＦＣ２９４４［４６］及びＲＳＦ２９４５［４９］もある。ＳＰＥＫＥプロトコル［２４］は実装され、ライセンス用に入手可能［４１］である。ＰＡＫプロトコル［１２］は実装され、ＳｅｃｕｒｅＳｔｏｒｅプロトコル［１４］において用いられる。
【００２０】
最近、ＩＥＥＥのＰ１３６３作業部会及び、ＩＳＯ／ＩＥＣの１１７７０−４作業部会において開発されているＰＡＫＥ標準がある。ＩＥＥＥのＰ１３６３作業部会は、パスワードに基づく公開鍵暗号化技術用のＰ１３６３．２の暫定標準仕様を開発している。それには、おそらく、ＰＡＫ［１２］、ＳＰＥＫＥ［２４］、ＳＲＰ［４６］、ＡＭＰ［３３］、Ｆｏｒｄ−Ｋａｌｉｓｋｉ／Ｊａｂｌｏｎプロトコル［１７、２６］、及び、これらのプロトコルの変形例が含まれるであろう。ＩＳＯ／ＩＥＣ  １１７７０−４の暫定標準は、ＰＡＫ以外のこれら全てを含む可能性が非常に高くなるだろう。
【００２１】
図１は、［３８］において説明されているＰＡＫＥプロトコルを説明する図である。このプロトコルでは、クライアントＣ（例えば、アリス）及びサーバＳ（例えば、ボブ）が、それぞれがパスワード認証情報Ｈ１（π）を知っていることを互いに証明することによって、互いを認証する。ここで、πは、パスワードであり、Ｈ１（）は、ハッシュ関数である。また、クライアントＣ及びサーバＳは、後続のセッションにおいて、ＣとＳとの間の対称暗号として用いることができる長い秘密鍵Ｋを生成する。
【００２２】
関数Ｈ１（）は、パスワードを、位数ｑの有限巡回群Ｇｑにマッピングする。Ｇｑは、素数ｐを法とする整数環Ｚｐの乗法群Ｚｐ＊の部分群となることができる。要素ｇは、Ｇｑの生成元である。記号Ｈｉ（例えば、Ｈ２、Ｈ３、Ｈ４）は、様々なハッシュ関数を表す。例えば、次のハッシュ関数を用いることができる。
【数１】
2009503934.tif 000003
【００２３】
ここで、Ｈ（）は、ＳＨＡ−１関数、又は、他のハッシュ関数である。関数Ｈ１及びＨ２は、Ｇｑにおいてそれぞれ値を有するので、ＧｑがＺｐ＊の部分群であれば、ｉ＝１、２に対して
【数２】
2009503934.tif 000004
【００２４】
を設定することができる。他の適当なハッシュ関数は、[３８]に説明されている。
【００２５】
より優れた安全性のためには、クライアントＣもサーバＳもパスワードπを記憶する必要がない。クライアントＣは、キーボード又は他の入力装置を介したユーザからの入力として、パスワード及びサーバの名前Ｓを受信することができる。パスワードπ＝πＣを有するクライアントＣ毎に、サーバは、値Ｈ１（πＣ）を含むデータベースレコードπｓ［Ｃ］を記憶する。図１において、サーバは、計算処理の効率を向上させるために、逆数値Ｈ１（πＣ）ー１を代わりに記憶する（その詳細は、ステップ１３０Ｓに関連して以下に説明する）。
【００２６】
ステップ１１０Ｃでは、クライアントＣが、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ秘密鍵交換プロトコルなどを行う。特に、クライアントは、Ｚｑのランダム要素ｘ（すなわち、ｘは、０からｑ−１までの整数である）を生成し、α＝ｇｘを計算する。ステップ１２０Ｃにおいて、クライアントは、Ｈ１（π）を計算してから、ｍ＝α・Ｈ１（π）を計算する。ステップ１２４Ｃにおいて、クライアントは、その名前Ｃ及び値ｍをサーバに送信する。
【００２７】
ステップ１１０Ｓにおいて、サーバは、ｍについて簡単な確認を（関数ＡＣＣＥＰＴＡＢＬＥ（）を用いて）行い、確認が失敗した場合は、処理を中止する。その確認では、ｐを法とするｍが０でないことを確認する。ステップ１２０Ｓにおいて、サーバは、Ｚｑのランダムなｙを生成し、μ＝ｇｙを計算する。ステップ１３０Ｓにおいて、サーバは、記憶された値Ｈ１（πＣ）−１を用いてクライアントの値α（ステップ１１０Ｃ参照）：
α＝ｍ・Ｈ１（πＣ）−１
を計算する。
【００２８】
ステップ１４０Ｓにおいて、サーバは、ＤＨ共有鍵値σ＝αｙを計算する（この値は、ｇｘｙに等しい）。ステップ１５０Ｓにおいて、サーバは、値ｋ＝Ｈ２（＜Ｃ，Ｓ，ｍ，μ，σ，Ｈ１（πＣ）−１＞）を計算する。ステップ１６０Ｓにおいて、サーバは、値μ、ｋをクライアントに送信し、サーバがＨ１（πＣ）−１を知っていることを証明する。（Ｈ１（πＣ）−１の逆数の算出はＧｑでは容易であることを仮定して、Ｈ１（πＣ）を知っていること証明する。なお、逆数の算出は、拡張ユークリッドアルゴリズムを用いてＺｑ＊において容易に行われる。）
クライアントは、サーバの証明をステップ１３０Ｃ及びステップ１４０Ｃにおいて検証する。より詳しくは、ステップ１３０Ｃにおいて、σをμｘとして計算する。ステップ１４０Ｃにおいて、クライアントは、Ｈ１（π）−１を計算してから、Ｈ２（＜Ｃ，Ｓ，ｍ，μ，σ，Ｈ１（π）−１＞）を計算し、この後者の値がサーバのｋと一致しない場合は、処理を中止する。ステップ１６０Ｃにおいて、クライアントは、値ｋ’＝Ｈ３（＜Ｃ，Ｓ，ｍ，μ，σ，Ｈ１（πＣ）−１＞）を計算し、この値を、クライアントがＨ１（π）を知っていることの証明としてサーバに送信する（ステップ１７０Ｃ）。ステップ１７０Ｓにおいて、サーバは、Ｈ３（＜Ｃ，Ｓ，ｍ，μ，σ，Ｈ１（πＣ）−１＞）を計算し、計算した値がｋ’と等しいことを確認することにより、証明を検証する。
【００２９】
ステップ１８０Ｃ及びステップ１８０Ｓのそれぞれにおいて、クライアント及びサーバは、共有セッション鍵Ｋ＝Ｈ４（＜Ｃ，Ｓ，ｍ，μ，σ，Ｈ１（πＣ）−１＞）をそれぞれ生成する。Ｋは、長い鍵であっても良い。
【００３０】
なお、ネットワーク上で送信された情報（すなわち、値Ｃ、ｍ、μ、ｋ、ｋ’）をオフライン辞書攻撃に用いることは困難である。例えば、（ステップ１５０Ｓ及びステップ１６０Ｃの）ｋ及びｋ’の式におけるσの利用や、σの生成における乱数ｙの利用により、ＣとＳの間の通信が盗聴されたとしても、オフライン辞書攻撃を行うことは困難となる。
【００３１】
しかしながら、敵対者がサーバＳをセキュリティ侵害の危険に晒す場合、その敵対者は、πｓ［Ｃ］から値Ｈ１（π）−１を求め、Ｈ１（π）を計算することが可能である。このとき、プロトコルが、Ｈ１（π）以外のπについての情報を知っていることを証明することをクライアントに対して要求することはないので、敵対者は、クライアントＣになりすますことができる。よって、このプロトコルは、サーバの危殆化に対して耐性を持たない。
【００３２】
図２は、［３８］から改良したプロトコル「ＰＡＫ−Ｚ」を説明する図である。これは、拡張ＰＡＫＥプロトコルであり、拡張ＰＡＫＥプロトコルは、πについての追加情報を知っていることをサーバに証明することを、クライアントに対して要求する。クライアントＣ毎のサーバのレコードπｓ［Ｃ］には、値Ｈ１（＜Ｃ、πＣ＞）−１、ある署名スキームに従ってデジタル署名を検証する署名検証鍵ｐｋ及び、ｐｋに関する署名鍵ｓｋの暗号
【数３】
2009503934.tif 000005
【数４】
2009503934.tif 000006
【００３３】
が含まれる。ここで、Ｈ７（）は、例えば、（１）又は（２）にあるような、最適なハッシュ関数である。この暗号化は、「ワンタイムパッド」と呼ばれる。
【００３４】
クライアントは、図１と同様にステップ１１０Ｃからステップ１２４Ｃを行う。サーバは、図１と同様にステップ１１０Ｓから１５０Ｓを行う。また、ステップ２１０Ｓ及びステップ２１４Ｓにおいて、サーバは、
【数５】
2009503934.tif 000007
【００３５】
の暗号ｃ’を計算する。
【数６】
2009503934.tif 000008
【００３６】
ここで、Ｈ５は、（例えば、（１）又は（２）などのような）あるハッシュ関数である。ステップ１６０Ｓにおいて、サーバは、値ｃ’をμ及びｋと共にクライアントに送信する。
【００３７】
クライアントは、図１と同様に、ステップ１３０Ｃ及びステップ１４０Ｃを行う。ステップ２１０Ｃにおいて、クライアントは、ｃ’を
【数７】
2009503934.tif 000009
【数８】
2009503934.tif 000010
【００３８】
に復号する。
【００３９】
ステップ２２０Ｃにおいて、クライアントは、
【数９】
2009503934.tif 000011
【００４０】
を署名鍵ｓｋ
【数１０】
2009503934.tif 000012
【００４１】
に復号する。
【００４２】
また、クライアントは、ｓｋについての正当性を確認し、確認が失敗した場合、処理を中止する。ステップ２３０Ｃにおいて、クライアントは、鍵ｓｋに基づいてサーバのＤＨ鍵μ（図１のステップ１２０Ｓ参照）についてのデジタル署名ｓ＝Ｓｉｇｓｋ（μ）を計算する。ステップ２４０Ｃにおいて、クライアントは、署名ｓを値
【数１１】
2009503934.tif 000013
【００４３】
に暗号化し、ｓ’をサーバに送信する（ステップ２５０Ｃ）。ステップ２２０Ｓにおいて、サーバは、
【数１２】
2009503934.tif 000014
【００４４】
を計算することで署名ｓを回復する。
【００４５】
ステップ２３０Ｓにおいて、サーバは、πｓ［Ｃ］から求めた公開鍵ｐｋを用いて署名を検証する。検証が失敗した場合、サーバは処理を中止する。共有鍵の生成（ステップ１８０Ｃ及び１８０Ｓ）は図１と同様に行われる。
【発明の開示】
【発明が解決しようとする課題】
【００４６】
発明者は、図２のＰＡＫ−Ｚプロトコルが、いくつかの署名スキーム（Ｓｉｇ、Ｖｅｒｉｆｙ）（ステップ２３０Ｃ及びステップ２３０Ｓ参照）に対するサーバの危殆化に対してあまり耐性がないことに注目している。離散対数（ＤＬ）に基づく署名スキームを用いる場合（例えば、以下の付録に説明されるＳｃｈｎｏｒｒ署名スキーム、ＥｌＧａｍａｌ、又は、ＤＳＳ）、ＰＡＫ−Ｚプロトコルは、「シングル・ビット・展性攻撃」と我々が呼ぶところの攻撃に対して脆弱である。この攻撃において、敵対者がサーバを乗っ取った場合、敵対者は、（Ｈ１（＜Ｃ、πＣ＞）に加えて）署名鍵ｓｋを決定することができる。このとき、敵対者は、パスワードπを知らずに署名ステップ２３０Ｃを行うことが可能であるため、敵対者は、クライアントになりすますことができる。
【００４７】
攻撃によって、署名スキームに基づく離散対数の次のような特性が悪用される。署名鍵ｓｋと対応する検証鍵ｐｋ＝ｐｋ（ｓｋ）とは、
【数１３】
2009503934.tif 000015
【００４８】
となるように関連している。ここで、ｇは、有限巡回群の要素であり、署名者は、ｇを知っている。したがって、任意の整数ｊに対して、
【数１４】
2009503934.tif 000016
【００４９】
となり、ｐｋ（ｓｋ＋ｊ）は、ｓｋを知らずとも計算可能となる。
【００５０】
シングル・ビット・展性攻撃は、以下のように進む。ステップ２１０Ｓを参照すると、ｄ＝｜ｃ｜、すなわち、ｃのビット長を表す。そして、ｃは、
【数１５】
2009503934.tif 000017
【００５１】
と書き表すことができる。ここで、各ｃｉは、２進数字である。ステップ２１０Ｓにおいて、敵対者は、ｃの１ビット、例えば、ビットｉを反転させ、
【数１６】
2009503934.tif 000018
【００５２】
を求める。ここでｃｉ＊＝１−ｃｉである。暗号化（３）を参照し、π＝πＣとすると、
【数１７】
2009503934.tif 000019
【００５３】
と書き表すことができる。ここで、ｓｋ＊（ｉ）は、ｓｋのｉ番目のビットｓｋｉを反転させることによりｓｋから求めることができる。敵対者は、ｓｋのｉ番目は知らないが、
【数１８】
2009503934.tif 000020
【００５４】
であることは知っている。
【００５５】
敵対者は、ｃの代わりにｃ＊（ｉ）を用いてステップ２１４Ｓ及びステップ１６０Ｓを行う。クライアント側では、ステップ２１０Ｃにおいて、ｃの代わりにｃ＊（ｉ）を出力し、ステップ２２０Ｃにおいて、ｓｋの代わりにｓｋ＊（ｉ）を出力する。ｓｋ＊（ｉ）が適切な範囲にある場合、ＶＡＬＩＤ（ｓｋ＊（ｉ））が、ＴＲＵＥを返す。ステップ２３０Ｃ、２４０Ｃ、２５０Ｃは、ｓｋの代わりにｓｋ＊（ｉ）を用いて行われる。
【００５６】
サーバ側では、ステップ２２０Ｓにおいて、値
【数１９】
2009503934.tif 000021
【００５７】
を出力する。そして、敵対者が
【数２０】
2009503934.tif 000022
【００５８】
を計算する。すなわち、ｐｋ＊＝ｐｋ（ｓｋ＋２ｉ）である。（１０）を参照。その後、敵対者は、
【数２１】
2009503934.tif 000023
【００５９】
を実行する。この関数が１を返す場合、敵対者は、ｐｋ（ｓｋ＋２ｉ）がｓｋ＊（ｉ）に対応する検証鍵であり、よって、ｓｋ＊＝ｓｋ＋２ｉであると、結論付ける。すなわち、ｓｋのｉ番目のビットは０である。（（１２）参照）。
【数２２】
2009503934.tif 000024
【００６０】
である場合、敵対者は、ｉ番目のビットは１であると結論付ける。
【００６１】
よって、敵対者は、プロトコルのｄ回の実行におけるｓｋの全ビットを決定することができ得る。ｄが、可能なパスワードの辞書よりもずっと小さければ、攻撃は、辞書攻撃よりもより効率的となり得る。
【課題を解決するための手段】
【００６２】
ここでは、本発明のいくつかの技術的特徴を要約する。本発明は、添付の請求項によって定義される。
【００６３】
本発明の一実施形態において、（３）のワンタイムパッド暗号化方式Ｅは、他の暗号化方式ＥＥ、例えば、本質的に非展性な暗号化方式に置き換えられる。一実施形態において、ＥＥは、次のようなものである。ｃがｓｋの暗号である場合、ｃ＊（ｉ）は、ＥＥに基づく有効な暗号ではない、又は、ｃ＊（ｉ）は、ある値ｓｋ＊の有効な暗号であるが、「合理的時間」において、敵対者がｓｋ＊を見つけることができる確率は、敵対者がｃを知らずに（例えば、ｓｋ＊を値のプールからランダムに選択することによって）ｓｋ＊を見つけることができる確率と「ほぼ同じ」である。ここで、「合理的な時間」とは、セキュリティパラメータκにおける少なくともひとつの多項式に関する多項式時間を意味する。セキュリティパラメータκは、任意のパラメータであってよく、例えば、成功裡のセキュリティ攻撃が、無視できない確率でおよそ２κの演算を必要とするように、選択され得る。一実施形態において、κは、ｓｋのサイズ（例えば、ビット長）を表す。（例えば、κは、ｓｋのビット長の半分であってよい。）確率が「ほぼ同じ」という表現は、確率がせいぜい「無視できる程度」異なることを意味している。「無視できる程度」とは、κが無限大に近似する時のκの多項式の逆数よりも速く、大きさが０に近似する値のことである。それぞれの確率は、値の関係する集合の一様分布を仮定することで定義される。
【００６４】
一実施形態において、暗号化方式（３）ではなく、クライアントが復号された値ｓｋを検証できるようにする暗号化スキームを用いる。例えば、次のスキームが用いられる。
【数２３】
2009503934.tif 000025
【００６５】
ここで、Ｅ＜Ｃ、π＞（ｓｋ）は、（３）と同様であり、Ｈ８（）は、暗号化ハッシュ関数である。
【数２４】
2009503934.tif 000026
【００６６】
と表せば、
【数２５】
2009503934.tif 000027
【００６７】
である。
【００６８】
クライアントがｃ＝ＥＥ＜Ｃ，π＞（ｓｋ）を取得したと仮定する。クライアントは、（６）と同様に、ｃＥをｓｋに復号し、そして、Ｈ８（ｓｋ）を計算し、計算した値がｃｖと等しいことを検証する。
【００６９】
一実施形態において、関数Ｈ８（）は、暗号化ハッシュ関数ではない。例えば、この関数は、一方向性がなく、及び／又は、衝突耐性のないものである。一実施形態において、Ｈ８（）は、Ｈ８（ｓｋ）の少なくとも１ビットが、ｓｋの少なくとも２ビットに基づくようになっている。一実施形態において、Ｈ８（ｓｋ）のひとつ以上のビットの各々と、おそらくＨ８（ｓｋ）の各ビットとは、ｓｋの２つ以上のビット、そしておそらくｓｋの全ビットに基づいている。また、Ｈ８（ｓｋ）は、一実施形態において、ｓｋの全ビットに基づいている（すなわち、任意のビット位置ｊに対して、ビットｊにおいてのみ異なる２つのｓｋ値が存在し、対応する値Ｈ８（ｓｋ）は異なる値である）。一実施形態において、ｓｋ及びＨ８（ｓｋ）のそれぞれは、少なくとも８０ビットを有する。他の実施形態も可能である。
【００７０】
本発明は、上述した実施形態に限定されるものではない。本発明は、各当事者が、他方の公開鍵又は認証公開鍵を持たない場合、又は上述した他の場合に限定されるものではない。本発明の他の特徴を以下に説明する。本発明は、添付の請求項によって定義される。
【発明を実施するための最良の形態】
【００７１】
本発明は、以下に詳述する説明及び本発明の様々な実施形態の添付図からより完全に理解されるであろう。しかしながら、これらは、本発明を特定の実施形態に限定するものであると理解されるべきではなく、単に説明と理解のためだけのものである。
【００７２】
以下の説明では、本発明をより完全に説明するために、様々な詳細が記載されている。しかしながら、当業者には、本発明をそのような詳細を用いることなく実践できるということが明らかとなるであろう。また、本発明が不明瞭になることを回避するために、公知の構造及び装置を詳細ではなく、ブロック図として表す。
【００７３】
以下に続く詳細な説明のいくつかの部分は、コンピュータメモリ内のデータビットに関するアルゴリズムや演算の記号表現の観点から表される。これらのアルゴリズムの説明及び表現は、データ処理技術における当業者が、自らの研究を当技術分野の他の技術者に伝達するために用いる手段である。アルゴリズムは、所望の結果へ導く方法である。ステップは、物理量の物理的操作を要求するものである。通常、これらの量は、必然的にではないが、記憶し、転送し、組み合わせ、比較し、操作することが可能な電気又は磁気信号の形式をとる。これらの信号を、場合によっては、主に共通使用の理由から、ビット、値、要素、記号、文字、語、数字などとして参照することが有効であることが証明されている。
【００７４】
しかしながら、これら全て及び同様の語が、適当な物理量と関連付けられることもあり、これらの量に対して付された便利なラベルであるにすぎないことに留意すべきである。以下の説明から明確であり特に言及がない限り、以下の説明を通して、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」、「計算する（ｃｏｍｐｕｔｉｎｇ）」、「計算する（ｃａｌｃｕｌａｔｉｎｇ）」、「決定する（ｄｅｔｅｒｍｉｎｉｎｇ）」、「表示する（ｄｉｓｐｌａｙｉｎｇ）」などの語を利用する議論は、コンピュータシステム又は同様の電気計算機の動作及び処理に関して言及するものである。なお、コンピュータシステム又は同様の電気計算機は、コンピュータシステムのレジストリやメモリ内の物理的（電気的）量として表されるデータを操作し、同様にコンピュータシステムのメモリ、レジストリ、他の情報記憶装置、送信装置、又は、表示装置内の物理量として表される他のデータに変換する。
【００７５】
また、本発明は、本明細書に記載する動作を行う装置にも関する。この装置は、必要とされる用途のために特別に構成されても良いし、汎用コンピュータを使用し、コンピュータに記憶されているコンピュータプログラムによって選択的に起動もしくは再構成されるものであっても良い。そのようなコンピュータプログラムが記憶されるコンピュータ読み取り可能な記憶媒体としては、フロッピディスク、光学ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、読み取り専用メモリ（ＲＯＭ）、ランダム・アクセス・メモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気又は光学カード、或いは、コンピュータの指示を記憶するのに適したあらゆる形式の媒体など、あらゆる形式のディスクが含まれるが、これらに限定するわけではない。なお、各々は、コンピュータのシステムバスに連結される。コンピュータプログラムは、ネットワーク上のデータキャリア信号によって搬送されてもよい。従って、プログラムは、搬送波、赤外線信号、デジタル信号などによって運ぶことが可能である。
【００７６】
暗号技術分野の当業者にとって、暗号に関する多くの発明が、計算処理が困難なある仮定に基づいていることは公知である。例えば、暗号システムは、特定の数字を効率的に素数に分解することが困難である限り安全であることを証明しようとするものであってもよい。「計算処理的な（ｃｏｍｐｕｔａｔｉｏｎａｌ）」という用語は、当技術分野においては、このクラスの暗号の発明を特定するために用いることが多い。本発明は、パスワード認証鍵交換用の計算処理的スキームを提供する。「情報論的（ｉｎｆｏｒｍａｔｉｏｎ  ｔｈｅｏｒｅｔｉｃ）」又は「無条件に（ｕｎｃｏｎｄｉｔｉｏｎａｌ）」という用語は、当技術分野においては、いかなる種類の仮定を行うことなく、特定の重要な安全性の定義と数学的に合致するスキームとの関連において用いられることが多い。
【００７７】
純粋にセキュリティの観点から、いかなる計算処理的仮定も持たないことが一般的に好ましいが、そのような仮定なしでは解決できない問題がある（本発明は、そのような例に役立つ）。特に、この最新技術では、公開鍵暗号を要求せずにＰＡＫＥスキームを構築することは不可能である［２２］。さらに、最新技術では、ある形式の計算処理的仮定なしに公開鍵暗号を実行する方法は知られていない。よって、ここに説明する技術を含むＰＡＫＥスキームの全てが、何らかの形式の計算処理的仮定を要求する。これらの仮定については、後述する。さらに、暗号化方法が計算処理的仮定と組み合わせることによってさらに効率的となることは、当業者にとって一般的に公知である。
【００７８】
ひとつの仮定が他の仮定を暗示することが多いことも記載するに値する。すなわち、仮定のうちのひとつが実際に真であったとすると、他の仮定が、数学的論理的議論により真であるとみなされる。典型的には、そのような推測を示すために当業者が用いる手段は、第２の仮定を破るためのメカニズムを第１の仮定を破るためのメカニズムに変える変換（当技術分野においては還元として知られている）である。そのような場合、第１の仮定は「強い」、第２の仮定は「弱い」と呼ばれている。一般に、弱い仮定が好ましい。
【００７９】
署名スキーム
署名スキームＳは、３つのアルゴリズム（Ｇｅｎｓ、Ｓｉｇ、Ｖｅｒｉｆｙ）を含んでも良い。最初の２つのアルゴリズムは、確率的なものであってもよい。一実施形態において、３つ全てのアルゴリズムは期待される多項式時間において実行される。Ｇｅｎｓは、セキュリティパラメータ（通常、κとして表され、単項形式、すなわち、１κで表される）を入力としてもよく、鍵ペア（ｐｋ、ｓｋ）、すなわち、（ｐｋ，ｓｋ）←Ｇｅｎｓ（１κ）を出力する。Ｓｉｇｎは、メッセージｍと署名鍵ｓｋを入力とし、ｍに対する署名σ、すなわちσ←Ｓｉｇｓｋ（ｍ）を出力する。Ｖｅｒｉｆｙは、メッセージｍ、検証鍵ｐｋ及びｍに対する候補署名σ’を入力とし、σ’がｍに対して正当な署名であるかどうかの指示を返す。例えば、Ｖｅｒｉｆｙ＝Ｖｅｒｉｆｙｐｋ（ｍ，σ’）は、σ’が、秘密鍵に対応し、ｍに対して正当な署名であった場合は、値１を返し、そうでなければ、０を返す。もちろん、σ←Ｓｉｇｓｋ（ｍ）であれば、Ｖｅｒｉｆｙ＝Ｖｅｒｉｆｙｐｋ（ｍ、σ）＝１である。
【００８０】
多く場合、ｓｋは、署名者によって秘密に保持され、ｐｋは、公開される。他の場合、ｓｋ及びｐｋは共に、秘密に保持される。
【００８１】
署名スキームの一例として、Ｓｃｈｎｏｒｒ署名［４４］がある。以下の付録も参照のこと。この例は、説明のためだけのものであり、本発明を限定するものと理解されるべきではない。
【００８２】
対称暗号化スキーム
対称暗号化スキームＥは、２つペアのアルゴリズム（Ｅｎｃ、Ｄｅｃ）である。一実施形態において、その両方のアルゴリズムは、期待される多項式時間において実行される。Ｅｎｃは、対称鍵ｋとメッセージｍとを入力とし、ｍに対する暗号ｃを出力する。これをｃ←Ｅｎｃｋ（ｍ）と表す。Ｄｅｃは、暗号文ｃと対称鍵ｋとを入力とし、ｃがｍの正当な暗号であるようにメッセージｍを、そのようなｍが存在する場合に返し、そうでなければ、エラーを指示する（⊥）を返す。未知の鍵ｋに基づいて未知のメッセージｍの暗号ｃが与えられる場合、暗号化スキームは、本質的に非展性であると考える。すなわち、少なくともｍを決定することなしに鍵ｋに基づく関連するメッセージｍ’の新しい暗号ｃ’≠ｃを計算することが難しくなる。
【００８３】
非展性であることが本質的ではない対称暗号化スキームの例示として、ワンタイムパッドがある。ワンタイムパッドは、
【数２６】
2009503934.tif 000028
【００８４】
であり、ここでＨ（）はｍと同じ長さの出力を有するハッシュ関数で、
【数２７】
2009503934.tif 000029
【００８５】
はビット単位の排他的論理和演算である。上記（３）も参照のこと。未知の鍵ｋに基づく未知のメッセージｍの暗号文ｃが与えられると、関連するメッセージ
【数２８】
2009503934.tif 000030
【００８６】
の暗号文
【数２９】
2009503934.tif 000031
【００８７】
を、ｍを決定することなしに構成することができる。ここで、上記関連するメッセージは、反転した最後のビットを有するｍである実際、ｍのｉ番目のビットを反転させることにより取得した任意のメッセージｍ＊（ｉ）の暗号文ｃ＊（ｉ）を構成することが可能である。（１１）を参照のこと。
【００８８】
本質的に非展性である対称暗号化スキームの例として、暗号化ハッシュ関数Ｈ’（）に対するメッセージの暗号化ハッシュ、すなわち
【数３０】
2009503934.tif 000032
【００８９】
に連結されたワンタイムパッドがある。（１４）も参照のこと。これは、本質的に非展性である。なぜならば、ワンタイムパッドの部分が更新された場合、暗号化ハッシュは、メッセージが既に決定されていることを暗示しながら、正しいメッセージを用いて再計算しなければならないからである。
【００９０】
本発明の一実施形態は、「本質的に非展性である」という概念を参照せずに説明することができる。本発明は、本質的に非展性な暗号スキームに限定されるものではないと考えられる。
【００９１】
ハッシュ関数
暗号化ハッシュ関数Ｈは、次の特性を満たす関数である。
【００９２】
（ａ）一方向性
一方向性とは、Ｈ（ｘ）が与えられるとき、Ｈ（ｚ）＝Ｈ（ｘ）となる原像ｚを見つけることは、無視できるほどに小さい確率を除いて、計算処理的に不可能であることである。
【００９３】
（ｂ）衝突耐性又は少なくとも弱衝突耐性
Ｈ（ｍ１）＝Ｈ（ｍ２）となるｍ１≠ｍ２を計算処理的に見つけることが不可能である場合、Ｈ（）は、衝突耐性（又は、強衝突耐性）であると言われる。ｍ１が与えられるとき、Ｈ（ｍ１）＝Ｈ（ｍ２）となるｍ２≠ｍ１を計算処理的に見つけることが不可能である場合、Ｈ（）は、弱衝突耐性であると言われる。
【００９４】
「計算処理的に不可能」とは、セキュリティパラメータκを与えられるとき、κの固定の多項式以下の時間内に、無視できるほどに小さい確率を除いて、計算できないことを意味する（この確率は、κが無限大に近似する場合にκにおける多項式の逆数より速い速度で０に近似するという意味において無視できる）。セキュリティパラメータκは、例えば、｜Ｈ（ｍ）｜の半分など、Ｈ（ｍ）のサイズを測定するものである。（ここで、｜Ｈ（ｍ）｜はＨ（ｍ）のビット長を表す）。
【００９５】
当技術分野においては、一般的に、ＳＨＡ−１及びＭＤ５の関数は一方向性を有し、衝突耐性があると考えられている。（例えば、参考のために援用される「ＲＦＣ−２１０４,Ｒｅｑｕｅｓｔ  ｆｏｒ  Ｃｏｍｍｅｎｔｓ，  Ｎｅｔｗｏｒｋｉｎｇ  Ｗｏｒｋｉｎｇ  Ｇｒｏｕｐ, Ｈ．Ｋｒａｗｃｚｙｋ, 「ＨＭＡＣ：  Ｋｅｙｅｄ−Ｈａｓｈｉｎｇ  ｆｏｒ  Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ」、１９９７年２月。」」Ｈ（）がＳＨＡ−１又はＭＤ５である場合、関数（１）は、一方向性を有し、衝突耐性があると考えられる。Ｈ（）がＳＨＡ−１又はＭＤ５であり、ｐが十分に大きい（例えば、セキュリティパラメータ以上のビット長を持っている）場合、関数（２）は、一方向性を有し、衝突耐性があると考えられる。つまり、そのような関数を反転する公知のアルゴリズム、又は、与えられた関数値の２つの異なる原像ｍ１とｍ２を見つける公知のアルゴリズム、更に、ｍ１とｍ２が同じ像にマッピングされるように与えられたｍ１とは異なる原像ｍ２を見つける公知のアルゴリズムは、セキュリティパラメータにおける多項式時間では、無視できるほどに小さい確率を除いて、存在しない。
【００９６】
本発明の一実施形態の安全性を証明するために、ハッシュ関数は、当技術分野においてランダムオラクル［３］として言及される、ブラックボックスの完全なランダム関数のように振る舞うものと仮定される。［３］には、ランダムオラクルをインスタンス化する方法に関する議論が広範囲にわたってなされ、［２３］には、鍵生成関数に関する議論がなされている。しかしながら、本発明は、そのような関数に限定されない。
【００９７】
Πを辞書におけるパスワードの集合とし、πがΠにおける１つのパスワードを表すものとする。ここでパスワードは、好ましくは少人数の当事者間でお互いに知られている量を表し、典型的には秘密とされるものである。本発明の開示内容では、パスワードは、おそらく一意的なビット列へ、容易にマッピング可能な任意の量を表すものであっても良い。一実施形態において、パスワードは、覚えやすいものである。一実施形態において、ビット列は、一意的であるが、同じビット列にマッピングされる2つのパスワードを計算処理的に見つけることは不可能である。さらに、本発明の内容では、「パスワード」及び「短い秘密」という語は、同義である。また、「短い」という用語を使用するのは、好ましくは、容易に記憶可能な量を示すためだけであり、本発明を、特定の長さの秘密に限定すべきものではない。
【００９８】
本発明のＰＡＫＥプロトコルの一実施形態は、ネットワーク３０２上で送信された信号を用いて通信する、クライアントのコンピュータシステムＣと、サーバのコンピュータシステムＳの間で実行される(図３)。システムＣ及びシステムＳは、必ずしもクライアントとサーバである必要はなく、任意のシステムと入れ替えることができる。クライアントＣは、コンピュータ命令を実行する一つ以上のコンピュータプロセッサ３０４Ｃを含む。クライアントＣは、命令とデータを記憶するためにコンピュータ記録装置３０６Ｃ(半導体メモリ、磁気又は光学ディスク、及び／又は他のタイプの記憶装置)を含む。クライアントＣは、パスワードやサーバの名前Ｓなどのデータを受信可能な入力装置３０８Ｃも含む。サーバＳは、コンピュータの命令を実行する一つ以上のプロセッサ３０４Ｓ、及び、命令やデータを記憶する記憶装置３０６Ｓも含む。クライアント及びサーバは、他の装置を適宜含むこともできる。
【００９９】
一実施形態において、クライアントシステムＣは、パスワードπＣ（πとのみ表すこともある）と関連付けられる。一実施形態において、パスワードは、コンピュータシステムよりも人間であるユーザと関連付けられる。我々は、クライアントシステムＣを、パスワードπＣに関連付けられたユーザによって用いられるコンピュータシステムと見なすことができる。同じコンピュータシステムが、異なるユーザよって用いられる場合や、異なるパスワードを持つ同じユーザによって用いられる場合、当該同じコンピュータシステムは、異なる「クライアント」と見なされてもよく、異なるパスワードと関連付けられていもよい。
【０１００】
一実施形態において、クライアントシステムＣは、サーバ毎の情報（サーバ証明など）又はユーザ毎のデータ(パスワードやパスワードのハッシュなど)を記憶するものではない。図3の３１２Ｃで示されるように、クライアントシステムは、ユーザからの入力として、パスワードπとサーバの識別子Ｓを受信する。しかしながら、クライアントシステムは、プロトコルの記載やそのプロトコルの公開パラメータを記憶しても良い。一実施形態において、サーバＳは、ユーザ毎にデータレコードπＳ［Ｃ］を記憶することができる。このレコードには、ユーザのパスワードπＣ、及び／又は、パスワードのある関数、及び／又は、ユーザと関連付けられた補助データが含まれていても良い。サーバの危殆化に対して耐性を有するＰＡＫＥの場合、サーバは、パスワードを記憶せず、パスワードの関数と補助データのみを記憶する。図3の場合、３１２Ｓで示されるように、
【数３１】
2009503934.tif 000033
【０１０１】
である。ここで、（Ｈ１（＜Ｃ、πＣ＞））―1は、図2と同様であり、ｐｋ及びｓｋは、それぞれ署名スキームに対する検証鍵及び署名鍵であり、ＥＥは、ある暗号化スキーム(ＥＥ、ＤＤ)の暗号化アルゴリズムである。一実施形態において、暗号化スキームは、本質的に非展性である。一実施形態において、暗号化スキームは、対称的である。一実施形態において、暗号化アルゴリズムＥＥは、復号した値の正当性を検証するために、復号段階で用いられる検証情報を生成する。検証情報は、復号値の関数(例えば、暗号化ハッシュ関数)である。一実施形態において、ＥＥは、(１４)と同様に、いくつかの関数Ｈ７及びＨ８(例えば、一方向性と、おそらく、衝突耐性を有する関数)を用いており、すなわち、
【数３２】
2009503934.tif 000034
【０１０２】
である。（記号｜と‖は同義であり、文字列の連結を表す。）他の実施形態も可能である。例えば、関数Ｈ７は、Ｃに基づいており、例えば、
【数３３】
2009503934.tif 000035
【０１０３】
である。一実施形態において、Ｈ１（Ｃ、πＣ）は、第１の引数に基づいておらず、すなわち、Ｈ１（Ｃ、πＣ）=Ｈ１（πＣ）である。また、サーバは、（Ｈ１（Ｃ、πＣ））―1の代わりに、Ｈ１（Ｃ、πＣ）又はＨ１（πＣ）を記憶してもよい。一実施形態において、関数Ｈｉ()は、一方向性を有する。適当な例として、（１）及び（２）を参照のこと。
【０１０４】
プロトコルの説明
サーバの危殆化に対して耐性を持っていても持っていなくても良いＰＡＫＥプロトコルＰ’を拡張することで、図3の拡張ＰＡＫＥプロトコルＰを構成する。クライアント及びサーバのそれぞれのステップ３１４Ｃ及びステップ３１４Ｓを参照のこと。一実施形態において、Ｐ’は、図１のプロトコルである。よって、クライアント及びサーバは、ステップ３１４Ｃ及びステップ３１４Ｓにおいて、Ｈ１（Ｃ、π）を知っていることを互いに証明する。
【０１０５】
Ｐ’が終わり、暗号的に強い共有鍵Ｋを導出すると、サーバは、Ｋから導いた一時的なセッション鍵Ｋ’を用いて、
【数３４】
2009503934.tif 000036
【０１０６】
をクライアントに対して安全に送信する(一実施形態において以下に詳述する)。クライアントは、Ｋとπを用いて適当な鍵を導出し、ｓｋを取得し、そして、Ｐ’のトランスクリプト上にｓｋを有する署名を生成する。あるいは、クライアントは、サーバによるトランスクリプトの一部など、トランスクリプトに依存しているメッセージに署名することができる。実際、これにより、クライアント(プロトコルＰ’においてサーバと通信しているもの)がπを知っていることが証明される。Ｐの最終的な出力は、Ｋから導き出した他の鍵Ｋ”である。
【０１０７】
より詳細には、一実施形態は、次のように実行する。
【０１０８】
クライアント  その１：
ステップ３１４Ｃにおいて、クライアントは、Ｈ１（＜Ｃ、π＞）を計算し、ＰＡＫＥプロトコルＰ’の一部を実行し、共有暗号鍵Ｋを導き出す。ステップ３２０Ｃにおいて、クライアントは、あるハッシュ関数Ｈ２０（）を用いて、鍵Ｋ’＝Ｈ２０（Ｋ）を計算し、あるハッシュ関数Ｈ２１（）を用いて、Ｋ”＝Ｈ２１（Ｋ）を計算する。一実施形態において、関数Ｈ２０、Ｈ２１は、一方向性、及び／又は衝突耐性を有する。
【０１０９】
サーバ  その１：
ステップ３１４Ｓにおいて、サーバは、ＰＡＫＥプロトコルＰ’の一部を実行し、共有暗号鍵Ｋを導き出す。ステップ３２０Ｓにおいて、サーバは、鍵Ｋ’＝Ｈ２０（Ｋ）とＫ”＝Ｈ２１（Ｋ）とを計算する。
【０１１０】
一実施形態において、サーバ及びクライアントは、図１のようには鍵Ｋを計算しない。ステップ１８０Ｃ及びステップ１８０Ｓは、省略することができる。その代わりに、例えば、鍵Ｋ’及びＫ”は、
【数３５】
2009503934.tif 000037
【数３６】
2009503934.tif 000038
【０１１１】
のように、直接計算される。
【０１１２】
サーバ  その２、ステップ１：
ステップ３３０Ｓにおいて、サーバは、レコードπＳ［Ｃ］から値
【数３７】
2009503934.tif 000039
【０１１３】
を読み込み、この値を、鍵Ｋ’を用いて
【数３８】
2009503934.tif 000040
【０１１４】
に暗号化する。一実施形態において、暗号方法Ｅ’は、暗号化ハッシュ関数であってもなくても良いハッシュ関数Ｈ２２（）に対する対称暗号化スキーム(Ｅ’、Ｄ’)の一部、例えば、ワンタイムパッド、
【数３９】
2009503934.tif 000041
【０１１５】
である。ステップ３５０Ｓにおいて、サーバは、値ｃ’をクライアントに送信する。
【０１１６】
クライアント  その2、ステップ1：
クライアントは、値ｃ’を受信する。クライアントは、復号を実行してｓｋを計算する。特に、ステップ３２４Ｃにおいて、ｃ＝Ｄ’Ｋ’（ｃ’）を計算する。例えば、スキーム（２０）に対して、クライアントは
【数４０】
2009503934.tif 000042
【０１１７】
を計算する。ステップ３３４Ｃにおいて、クライアントは、ｓｋ＝ＤＤπ(ｃ)を計算する。特に、ｃを
【数４１】
2009503934.tif 000043
【０１１８】
とする。ここで、ｊ＝｜ｓｋ｜であり、ｃＥはｃの最初からｊビットである。（１５）及び（１６）も参照のこと。クライアントは、
【数４２】
2009503934.tif 000044
【０１１９】
を計算する。
【０１２０】
その後、クライアントは、Ｈ８（ｓｋ）を計算し、この値がｃｖに等しくない場合、処理を中止する。オプションとして、クライアントは、ｓｋに対する追加の正当性確認、例えば、ｓｋが適切な範囲であるか否かの確認を行ってもよい。処理の中止は、クライアントが、認証の失敗を示す信号を生成し、ステップ３４０Ｃ、３４４Ｃ、おそらく３５０Ｃをスキップすることを示す。
【０１２１】
ステップ３４０Ｃにおいて、クライアントは、ｓｋを用いてＰ’のトランスクリプトに署名、すなわち、ｓ＝Ｓｉｇｓｋ(ｔｒａｎｓｃｒｉｐｔ)を計算する。例えば、図１の場合、トランスクリプトは、文字列＜Ｃ，ｍ，μ，ｋ＞であっても、この文字列のいくつかの部分であっても良い。ステップ３４４Ｃにおいて、クライアントは、署名ｓをサーバに送信する。ステップ３５０Ｃにおいて、クライアントは、セッション鍵Ｋ”を出力する。
【０１２２】
サーバ その2、ステップ２:
サーバは、署名ｓを受信し、ステップ３６０Ｓにおいて、ｂ＝Ｖｅｒｉｆｙｐｋ(ｔｒａｎｓｃｒｉｐｔｓ)を計算する。ｂ＝０の場合、サーバは処理を中止する。そうでなければ(ステップ３７０Ｓ)、サーバは、セッション鍵Ｋ”を出力する。
【０１２３】
図２のＰＡＫ−Ｚプロトコルに対する図３のプロトコルの利点は、より広範なクラスの署名スキームに対して安全性を提供することである。安全性の証明の例示としては、ＣＲＹＰＴＯ２００６に提出された、Ｃ．  Ｇｅｎｔｒｙ、Ｐ．  ＭａｃＫｅｎｚｉｅ及びＺ．Ｒａｍｚａｎによる「サーバの危殆化に耐性を有するパスワードに基づく鍵交換方法(Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｍａｋｉｎｇ  Ｐａｓｓｗｏｒｄ−Ｂａｓｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  Ｒｅｓｉｌｉｅｎｔ  ｔｏ  Ｓｅｒｖｅｒ  Ｃｏｍｐｒｏｍｉｓｅ)」と題される論文に見いだすことができる。この論文は、ＣＲＹＰＴＯ２００６の予稿集（Ｃｙｎｔｈｉａ Ｄｗｏｒｋ編集）に掲載されることになっているが、安全性の証明はなされていない。安全性の証明は、汎用的結合可能性の枠組みにおいてなされており、図３のプロトコルが以下の条件を満たす限り安全であることを示している。その条件とは、（１）基本的なデジタル署名スキームが安全であること、（２）基本的な関数が理想的なハッシュ関数のように振る舞うこと、（３）基本的な暗号化アルゴリズムが安全であること、である。すなわち、プロトコルの安全性は、基本的な構成単位の安全性に還元される。
【０１２４】
さらに、図３のプロトコルは、任意のＰＡＫＥプロトコルＰ’及びステップ３４０Ｃ及びステップ３６０Ｓのための任意の署名スキーム（Ｇｅｎ、Ｓｉｇ、Ｖｅｒｉｆｙ）を用いて構成され、これらは、暗号論的仮定がその安全性を証明するために用いられることに基づいて選択可能である。例えば、同じ暗号論的仮定に基づくＰＡＫＥプロトコルＰ’及び署名スキームを選択することができる。また、一実施形態においては、秘密鍵ｓｋは、ステップ３３４Ｃにおいて、安価な排他的論理和演算を用いてクライアントによって計算される。しかしながら、本発明は、これらの利点を有するプロトコルに限定されるものではない。
【０１２５】
効率性に関して、図３のプロトコルは、ＰＡＫＥプロトコルＰ’に対して、クライアントによる、いくつかのハッシュ操作、対称暗号化及び復号化操作、署名計算と、サーバによる署名検証とに加えて、別の１ラウンドの通信を追加する（ステップ３５０Ｓ及びステップ３４４Ｃ）。別の１ラウンドの通信は、図２に示すように、実際のプロトコルメッセージの上に乗せて行うことができることもある。特に、図３のＰ’プロトコルが図１のプロトコルである場合、ステップ３５０Ｓは図１のステップ１６０Ｓと組み合わせることができ、ステップ３４４Ｃは、ステップ１７０Ｃと組み合わせることができる。実際、ステップ３５０Ｓにおいて、サーバは、Ｋから導出した鍵Ｋ’を用いて求めた値ｃ’を送信する。ここで、Ｋは、図１のステップ１８０Ｓにおいて導出されるが、ステップ１８０Ｓは、ステップ１６０Ｓの前に行うことができる。このため、Ｋ’は、ステップ１６０Ｓの前に求めることもできる。（ステップ３２０Ｓは、ステップ１６０Ｓの前に行うことができる）。同様に、クライアント側では、Ｋの計算（ステップ１８０Ｃ）は、ステップ１７０Ｃの前に行うことができるので、ステップ１７０Ｃの前に計算することができる鍵Ｋ’を用いて、署名を導出する（ステップ３２４Ｃ）。署名には、まだ別の計算がある。当技術分野におけるいくつかのプロトコルは、この別の計算を回避するために拡張ＰＡＫＥ用に特別に設計されている。（ＳＲＰ［４６］及びＡＭＰ［３３］は、二つのそのようなプロトコルであるが、ランダムオラクルモデルにおいても、どちらとも安全性の証明を持たない）。本発明は、図３のプロトコルの効率的な特性に限定されるものではない。
【０１２６】
セキュリティパラメータの選択
我々のプロトコルは、暗号化セキュリティパラメータκを含むか、或いは、プロトコルの「ビット−セキュリティ」が選択される。（一実施形態においては、κは、Ｈ８（）の出力の半分のサイズである）。当技術分野の現状によれば、κ＝８０が適当な選択である。とはいえ、ハッシュ関数のアプリケーションのためには、その数は、およそκ＝１２８まで増やされるべきである。しかしながら、当業者には、本発明がこの特定のパラメータを選択しなくても実践できることが明らかとなるであろう。
【０１２７】
本発明は、上述した実施形態に限定されるものではなく、以下の付録に記されたデジタル署名スキームに限定されるものでもない。図３の関数Ｈ８（）は、ｓｋ以外の値に基づいても良い。例えば、パスワード、クライアントの名前（Ｃ）や、他の値などである。よって、一実施形態において、（１４）は、
【数４３】
2009503934.tif 000045
【０１２８】
に置き換えられてもよい。本発明は、一方向性あるいは弱又は強衝突耐性を有する関数に限定されるものではない。なお、「一方向性」、「衝突耐性」、「本質的に非展性」という用語は、多項式時間から見て定義されている。例えば、一方向関数は、無視できるほど小さい確率を除いて、多項式時間において逆変換することができない関数である。しかしながら、大きい多項式Ｐ（κ）にとって、安全性は、例え、関連する関数が、多項式時間ｐ（κ）において、無視できない確率で逆変換できたとしても、少なくともいくつかのアプリケーションには適正である。また、無視できる確率及び無視できる量は、多項式の逆数より早い速度で０に近似する量として定義されている。多項式が大きい場合、その逆数は小さく、適正な安全性は、関連する確率又は量が無視できない（すなわち、ある多項式の逆数以上である）場合でも実現できる。他の実施形態及び変形例は、添付の請求項によって定義される本発明の請求項の範囲内のものである。
【０１２９】
付録
一実施形態のための署名スキーム
１.  エルガマル（ＥｌＧａｍａｌ）署名
１Ａ．  鍵生成：  ランダムな素数ｐ及びｐを法とする原始根ｇを生成する。集合｛１、２、．．．、ｐ−２｝におけるランダムな整数ａを選択する。ｐを法とするＡ＝ｇａを計算する。署名鍵はａである。検証鍵は、（ｐ、ｇ、Ａ）である。
【０１３０】
１Ｂ：  署名：署名アルゴリズムは、公知の衝突耐性ハッシュ関数を用いる。
【数４４】
2009503934.tif 000046
【０１３１】
メッセージ
【数４５】
2009503934.tif 000047
【０１３２】
に署名するために、ｐ−１と互いに素である乱数
【数４６】
2009503934.tif 000048
【０１３３】
を選択する。
【数４７】
2009503934.tif 000049
【０１３４】
を計算する。
【０１３５】
ここで、ｋ−１は、ｐ−１を法とするｋの逆数である。署名はペア（ｒ、ｓ）である。
【０１３６】
１Ｃ  検証：
【数４８】
2009503934.tif 000050
【０１３７】
である場合かつその場合のみ、受け付ける。
【０１３８】
２．  ＤＳＳ署名
２Ａ．  鍵生成：  エルガマル（ＥｌＧａｍａｌ）署名と同じように、ｇがｐを法とする原始根である必要はないが、鍵を生成する。ｇは、ある位数ｑのＺｐ＊の任意の要素となり得る。
【０１３９】
２Ｂ．  署名：  メッセージ
【数４９】
2009503934.tif 000051
【０１４０】
に署名するために、ｑと互いに素である乱数ｋを選択する。
【数５０】
2009503934.tif 000052
【０１４１】
を計算する。
【０１４２】
ここで、ｋ−１はｑを法とするｋの逆数である。署名は、ペア（ｒ、ｓ）である。
【０１４３】
２Ｃ．  検証：
【数５１】
2009503934.tif 000053
【０１４４】
である場合のみ、受け付ける。
【０１４５】
３．  シュノル（Ｓｃｈｎｏｒｒ）署名
３Ａ．  鍵生成：  エルガマル（ＥｌＧａｍａｌ）と同じように生成するが、ｇは、素数位数ｐの任意の（公開）群Ｇ生成元であっても良い。また、ａは、ｐ−１と等しくすることができる。
【０１４６】
３Ｂ．  署名：  ランダムな整数
【数５２】
2009503934.tif 000054
【０１４７】
を選択する。
【数５３】
2009503934.tif 000055
【０１４８】
を計算する。
【０１４９】
ここで、ｈは、公開ハッシュ関数である。署名は、ペア（ｅ、ｓ）である。
【０１５０】
３Ｃ．  検証：
【数５４】
2009503934.tif 000056
【０１５１】
を計算する。
【数５５】
2009503934.tif 000057
【０１５２】
である場合のみ、受け付ける。
【０１５３】
参考文献
以下の参考文献の全ては、参照によりここに引用したものとする。
【０１５４】
［１］Ｍ．Ａｂｄａｌｌａ及び、Ｄ．Ｐｏｉｎｔｃｈｅｖａｌ著、「単純なパスワードに基づく暗号鍵の交換プロトコル（Ｓｉｍｐｌｅ  Ｐａｓｓｗｏｒｄ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  Ｐｒｏｔｏｃｏｌｓ）」、ＲＳＡ会議会議、Ｃｒｙｐｔｏｇｒａｐｈｅｒ’ｓ  Ｔｒａｃｋ、ＬＮＣＳ３３７６、  １９１−２０８ページ、２００５年  
［２］Ｍ．Ｂｅｌｌａｒｅ、Ｄ．Ｐｏｉｎｔｃｈｅｖａｌ及びＰ．Ｒｏｇａｗａｙ著、「辞書攻撃に対して安全な認証鍵交換（Ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ）」、ＥＵＲＯＣＲＹＰＴ２０００、ＬＮＣＳ１８０７、１３９―１５５ページ、２０００年
［３］Ｍ．Ｂｅｌｌａｒｅ及びＰ．Ｒｏｇａｗａｙ著、「ランダムオラクルは実用的である：効率的なプロトコルのデザインのためのパラダイム（Ｒａｎｄｏｍ  ｏｒａｃｌｅｓ  ａｒｅ  ｐｒａｃｔｉｃａｌ：  Ａ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｄｅｓｉｇｎｉｎｇ  ｅｆｆｉｃｉｅｎｔ  ｐｒｏｔｏｃｏｌｓ）」、コンピュータ・通信セキュリティに関する第１回ＡＣＭ会議、６２−７３ページ、１９９３年１１月
［４］Ｍ．Ｂｅｌｌａｒｅ及びＰ．Ｒｏｇａｗａｙ著、「エンティティ認証及び鍵配布（Ｅｎｔｉｔｙ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  ｋｅｙ  ｄｉｓｔｒｉｂｕｔｉｏｎ）」、ＣＲＹＰＴＯ’９３、ＬＮＣＳ７７３、２３２−２４９ページ、１９９３年
［５］Ｍ．Ｂｅｌｌａｒｅ及びＰ．Ｒｏｇａｗａｙ著、「おそらく安全なセッション鍵配布―三者の場合（Ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｓｅｓｓｉｏｎ  ｋｅｙ  ｄｉｓｔｒｉｂｕｔｉｏｎ−ｔｈｅ  ｔｈｒｅｅ  ｐａｒｔｙ  ｃａｓｅ）」、計算理論に関する第２７回ＡＣＭシンポジウム、５７−６６ページ、  １９９５年  
［６］Ｓ．Ｍ．Ｂｅｌｌｏｖｉｎ及びＭ．Ｍｅｒｒｉｔｔ著、「暗号鍵交換：辞書攻撃に対して安全なパスワードに基づくプロトコル（Ｅｎｃｒｙｐｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ：  Ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｐｒｏｔｏｃｏｌｓ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ）」、セキュリティとプライバシーの研究に関するＩＥＥＥシンポジウム、７２−８４ページ、１９９２年
［７］Ｓ．Ｍ．Ｂｅｌｌｏｖｉｎ及びＭ．Ｍｅｒｒｉｔｔ著、「拡張暗号鍵交換：辞書攻撃及びパスワードファイルの危険性に対するパスワードに基づいたプロトコル（Ａｕｇｍｅｎｔｅｄ  ｅｎｃｒｙｐｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ：  Ａ  ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｐｒｏｔｏｃｏｌ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ  ａｎｄ  ｐａｓｓｗｏｒｄ  ｆｉｌｅ  ｃｏｍｐｒｏｍｉｓｅ）」、コンピュータ及び通信セキュリティに関するＡＣＭ会議、２４４−２５０ページ、１９９３年
［８］Ｓ．Ｍ．Ｂｅｌｌｏｖｉｎ及びＭ．Ｍｅｒｒｉｔｔ著、「安全な通信のための暗号プロトコル（Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  Ｓｅｃｕｒｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）」、  米国特許第５２４１５９９号
［９］Ｓ．Ｍ．Ｂｅｌｌｏｖｉｎ及びＭ．Ｍｅｒｒｉｔｔ著、「遠隔認証用暗号プロトコル（Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  Ｒｅｍｏｔｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ）」、米国特許第５４４０６３５号  
［１０］Ｄ．Ｂｌｅｉｃｈｅｎｂａｃｈｅｒ著、「パーソナルコミュニケーション（Ｐｅｒｓｏｎａｌ  ｃｏｍｍｕｎｉｃａｔｉｏｎ）」
［１１］Ｄ．Ｂｏｎｅｈ著、「判定ＤＨ問題（Ｔｈｅ  ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｐｒｏｂｌｅｍ）」、予稿集、第３回アルゴリズム的数論シンポジウム、ＬＮＣＳ１４２３、４８−６３ページ、１９９８年
［１２］Ｖ．Ｂｏｙｋｏ、Ｐ．ＭａｃＫｅｎｚｉｅ及びＳ．Ｐａｔｅｌ著、「おそらく安全なパスワード認証及びディフィーヘルマンを用いた鍵交換（Ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｐａｓｓｗｏｒｄ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｕｓｉｎｇ  Ｄｉｆｆｉｅ−  Ｈｅｌｌｍａｎ）」、ＥＵＲＯＣＲＹＰＴ２０００、ＬＮＣＳ１８０７、１５６−１７１ページ、２０００年
［１３］Ｒ．Ｃａｎｅｔｔｉ、Ｓ．Ｈａｌｅｖｉ、Ｊ．Ｋａｔｚ、Ｙ．Ｌｉｎｄｅｌｌ及び、Ｐ．ＭａｃＫｅｎｚｉｅ著、「汎用的に構成可能なパスワードに基づいた鍵交換（Ｕｎｉｖｅｒｓａｌｌｙ−ｃｏｍｐｏｓａｂｌｅ  ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ）」、Ｅｕｒｏｃｒｙｐｔ、２００５年  
［１４］Ｒ．Ｃｏｘ、Ｅ．Ｇｒｏｓｓｅ、Ｒ．Ｐｉｋｅ、Ｄ．Ｐｒｅｓｏｔｔｏ及び、Ｓ．Ｑｕｉｎｌａｎ著、「プラン９における安全性（Ｓｅｃｕｒｉｔｙ  ｉｎ  Ｐｌａｎ  ９）」、Ｕｓｅｎｉｘ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ２００２年  
［１５］Ｒ．Ｃｒａｍｅｒ及びＶ．Ｓｈｏｕｐ著、「適応的選択暗号文攻撃に対しておそらく安全な、実用的公開鍵暗号システム（Ａ  ｐｒａｃｔｉｃａｌ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ  ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ａｄａｐｔｉｖｅ  ｃｈｏｓｅｎ  ｃｉｐｈｅｒｔｅｘｔ  ａｔｔａｃｋ）」、ＣＲＹＰＴＯ’９８、ＬＮＣＳ１４６２、１３−２５ページ、１９９８年
［１６］Ｗ．Ｄｉｆｆｉｅ及びＭ．Ｈｅｌｌｍａｎ著、「暗号技術の新しい方向（Ｎｅｗ  ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  ｃｒｙｐｔｏｇｒａｐｈｙ）」、ＩＥＥＥ、Ｔｒａｎｓ．  Ｉｎｆｏ．  Ｔｈｅｏｒｙ、２２（６）、６４４−６５４ページ、１９７６年
［１７］Ｗ．Ｆｏｒｄ及びＢ．Ｓ．Ｋａｌｉｓｋｉ．Ｊｒ著、「パスワードからの強い秘密のサーバ支援による生成（Ｓｅｒｖｅｒ−ａｓｓｉｓｔｅｄ  ｇｅｎｅｒａｔｉｏｎ  ｏｆ  ａ  ｓｔｒｏｎｇ  ｓｅｃｒｅｔ  ｆｒｏｍ  ａ  ｐａｓｓｗｏｒｄ）」、予稿集、企業セキュリティに関する第５回ＩＥＥＥ国際ワークショップ２０００年
［１８］Ｒ．Ｇｅｎｎａｒｏ及びＹ．Ｌｉｎｄｅｌｌ著、「パスワードに基づく認証鍵交換の構成（Ａ  Ｆｒａｍｅｗｏｒｋ  ｆｏｒ  Ｐａｓｓｗｏｒｄ−Ｂａｓｅｄ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ）」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｅｕｒｏｃｒｙｐｔ  ２００３，  ＬＮＣＳ  ｖｏｌ．  ２６５６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社、５２４−５４３ページ、２００３年  
［１９］Ｏ．Ｇｏｌｄｒｅｉｃｈ及びＹ．Ｌｉｎｄｅｌｌ著、「ヒューマンパスワードのみを用いたセッション鍵生成（Ｓｅｓｓｉｏｎ−Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ  ｕｓｉｎｇ  Ｈｕｍａｎ  Ｐａｓｓｗｏｒｄｓ  Ｏｎｌｙ）」、ＣＲＹＰＴＯ２００１、ＬＮＣＳ２１３９、４０８−４３２ページ、２００１年
［２０］Ｌ．Ｇｏｎｇ著、「バスワード推測攻撃に強い最適認証プロトコル（Ｏｐｔｉｍａｌ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｐｒｏｔｏｃｏｌｓ  ｒｅｓｉｓｔａｎｔ  ｔｏ  ｐａｓｓｗｏｒｄ  ｇｕｅｓｓｉｎｇ  ａｔｔａｃｋｓ）」、第８回ＩＥＥＥコンピュータセキュリティ基盤ワークショップ、２４−２９ページ、１９９５年  
［２１］Ｌ．Ｇｏｎｇ、Ｔ．Ｍ．Ａ．Ｌｏｍａｓ、Ｒ．Ｍ．Ｎｅｅｄｈａｍ及びＪ．Ｈ．Ｓａｌｔｚｅｒ著、「誤って選んだ秘密の推測攻撃からの保護（Ｐｒｏｔｅｃｔｉｎｇ  ｐｏｏｒｌｙ  ｃｈｏｓｅｎ  ｓｅｃｒｅｔｓ  ｆｒｏｍ  ｇｕｅｓｓｉｎｇ  ａｔｔａｃｋｓ）」、通信における選択領域に関するＩＥＥＥジャーナル１１（５）、６４８−６５６ページ、１９９３年６月
［２２］Ｓ．Ｈａｌｅｖｉ及びＨ．Ｋｒａｗｃｚｙｋ著、「公開鍵暗号方式及びパスワードプロトコル（Ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ｐａｓｓｗｏｒｄ  ｐｒｏｔｏｃｏｌｓ）」、情報及びシステムセキュリティに関するＡＣＭトランザクション（ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  （ＴＩＳＳＥＣ））、第２巻、Ｎｏ．３、２３０−２６８ページ、１９９９年８月、ＡＣＭ、（暫定版が第５回ＡＣＭ−ＣＣＳで発表される）１２２−１３１ページ、１９９８年、ＡＣＭ
［２３］ＩＥＥＥ標準１３６３−２０００、「公開鍵暗号方式の標準仕様（Ｓｔａｎｄａｒｄ  ｓｐｅｃｉｆｉｃａｔｉｏｎｓ  ｆｏｒ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｇｒａｐｈｙ）」、２０００年  
［２４］Ｄ．Ｊａｂｌｏｎ著、「強いパスワードのみの認証鍵交換（Ｓｔｒｏｎｇ  ｐａｓｓｗｏｒｄ−ｏｎｌｙ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ）」、ＡＣＭ通信レビュー（ＡＣＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ（ＡＣＭ  ＳＩＧＣＯＭＭ））、２６（５）、５−２０ページ、１９９６年
［２５］Ｄ．Ｊａｂｌｏｎ著、「辞書攻撃の危険性のない拡張パスワード鍵交換プロトコル（Ｅｘｔｅｎｄｅｄ  ｐａｓｓｗｏｒｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｐｒｏｔｏｃｏｌｓ  ｉｍｍｕｎｅ  ｔｏ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋ）」、ＷＥＴＩＣＥ’９７、企業セキュリティに関するワークショップ、１９９７年
［２６］Ｄ．Ｊａｂｌｏｎ著、「複数のサーバを用いたパスワード認証（Ｐａｓｓｗｏｒｄ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｕｓｉｎｇ  ｍｕｌｔｉｐｌｅ  ｓｅｒｖｅｒｓ）」、ＲＳＡ会議２００１、Ｃｒｙｐｔｏｇｒａｐｈｅｒｓ’Ｔｒａｃｋ、ＬＮＣＳ２０２０、３４４−３６０ページ、２００１年  
［２７］Ｄ．Ｊａｂｌｏｎ著、「遠隔認証用暗号法（Ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｒｅｍｏｔｅ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ）」、米国特許第６２２６３８３号  
［２８］Ｄ．Ｊａｂｌｏｎ著、「遠隔認証用暗号法（Ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｒｅｍｏｔｅ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ）」、米国特許第６７９２５３３号
［２９］Ｓ．Ｊｉａｎｇ及びＧ．Ｇｏｎｇ、「バスワードに基づく相互認証による鍵交換（Ｐａｓｓｗｏｒｄ  ｂａｓｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｗｉｔｈ  ｍｕｔｕａｌ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ）」、暗号の選択領域に関するワークショップ（Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ（ＳＡＣ））、２００４年
［３０］Ｊ．Ｋａｔｚ、Ｒ．Ｏｓｔｒｏｖｓｋｙ及びＭ．Ｙｕｎｇ著、「標準的な仮定の下でおそらく安全である実用的パスワード認証鍵交換（Ｐｒａｃｔｉｃａｌ  ｐａｓｓｗｏｒｄ−ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｕｎｄｅｒ  ｓｔａｎｄａｒｄ  ａｓｓｕｍｐｔｉｏｎｓ）」、Ｅｕｒｏｃｒｙｐｔ２００１、ＬＮＣＳ２０４５、４７５−４９４ページ、２００１年  
［３１］Ｊ．Ｋａｔｚ及びＭ．Ｙｕｎｇ著、「確率的秘密鍵の暗号化のための安全性の概念の完全特性（Ｃｏｍｐｌｅｔｅ  ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ  ｏｆ  ｓｅｃｕｒｉｔｙ  ｎｏｔｉｏｎｓ  ｆｏｒ  ｐｒｏｂａｂｉｌｉｓｔｉｃ  ｐｒｉｖａｔｅ−ｋｅｙ  ｅｎｃｒｙｐｔｉｏｎ）」  計算理論に関するＡＣＭシンポジウム、２４５−２５４ページ、２０００年
［３２］Ｃ．ＫａｕｆｍａｎｎＲ．Ｐｅｒｌｍａｎ著、  「製品データ管理：新しい強いパスワードに基づくプロトコル（ＰＤＭ：  Ａ  Ｎｅｗ  Ｓｔｒｏｎｇ  Ｐａｓｓｗｏｒｄ−Ｂａｓｅｄ  Ｐｒｏｔｏｃｏｌ）」、ユーセニックスセキュリティシンポジウム、２００１年  
［３３］Ｔ．Ｋｗｏｎ著、「認証及び記憶可能なパスワードを介した鍵合意（Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  Ｋｅｙ  Ａｇｒｅｅｍｅｎｔ  ｖｉａ  Ｍｅｍｏｒａｂｌｅ  Ｐａｓｓｗｏｒｄｓ）」、２００１年インターネットソサエティネットワーク及び分散型システムセキュリティシンポジウム（２００１  Ｉｎｔｅｒｎｅｔ  Ｓｏｃｉｅｔｙ  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ）、２００１年
［３４］Ｓ．Ｌｕｃｋｓ著、「オープン鍵交換：公開鍵の暗号化なしに辞書攻撃を撃退する方法（Ｏｐｅｎ  ｋｅｙ  ｅｘｃｈａｎｇｅ：  Ｈｏｗ  ｔｏ  ｄｅｆｅａｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ  ｗｉｔｈｏｕｔ  ｅｎｃｒｙｐｔｉｎｇ  ｐｕｂｌｉｃ  ｋｅｙｓ）」、予稿集、セキュリティプロトコルに関するシンポジウム（ｔｈｅ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ）、１９９７年  
［３５］Ｐ．ＭａｃＫｅｎｚｉｅ、Ｓ．Ｐａｔｅｌ及びＲ．Ｓｗａｍｉｎａｔｈａｎ」著、「ＲＳＡに基づいたパスワード認証鍵交換（Ｐａｓｓｗｏｒｄ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｂａｓｅｄ  ｏｎ  ＲＳＡ）」、（ＡＳＩＡＣＲＹＰＴ２０００、ＬＮＣＳ１９７６、５９９−６１３ページ、２０００年  
［３６］Ｐ．ＭａｃＫｅｎｚｉｅ及びＲ．Ｓｗａｍｉｎａｔｈａｎ著、「安全な相互ネットワーク認証プロトコル（Ｓｅｃｕｒｅ  ｍｕｔｕａｌ  ｎｅｔｗｏｒｋ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｐｒｏｔｏｃｏｌ）」、米国特許６７５７８２５号
［３７］Ｐ．ＭａｃＫｅｎｚｉｅ著、「より効率的なパスワード認証鍵交換（Ｍｏｒｅ  Ｅｆｆｉｃｉｅｎｔ  Ｐａｓｓｗｏｒｄ−Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ）」、ＲＳＡ会議（ＲＳＡ  Ｃｏｎｆｅｒｅｎｃｅ）、Ｃｒｙｐｔｏｇｒａｐｈｅｒ’ｓ  Ｔｒａｃｋ、エル・エヌ・シー・エス（ＬＮＣＳ）２０２０、３６１−３７７ページ、２００１年
［３８］Ｐ．ＭａｃＫｅｎｚｉｅ著、「ＰＡＫスーツ：パスワード認証鍵交換用プロトコル（Ｔｈｅ  ＰＡＫ  ｓｕｉｔｅ：  Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｐａｓｓｗｏｒｄ−ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ）」、ＤＩＭＡＣＳテクニカルレポート（ＤＩＭＡＣＳ  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ）２００２―４６、２００２年１０月
［３９］米国標準技術局（ＮＩＳＴ）、「セキュリティハッシュの標準の発表（Ａｎｎｏｕｎｃｉｎｇ  ｔｈｅ  Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｓｔａｎｄａｒｄ）、ＦＩＰＳ  １８０−１、米国商務省、１９９５年４月  
［４０］Ｓ．Ｐａｔｅｌ著、「安全なパスワードスキームへの数論攻撃（Ｎｕｍｂｅｒ  ｔｈｅｏｒｅｔｉｃ  ａｔｔａｃｋｓ  ｏｎ  ｓｅｃｕｒｅ  ｐａｓｓｗｏｒｄ  ｓｃｈｅｍｅｓ）」、予稿集、セキュリティとプライバシーの研究に関するＩＥＥＥシンポジウム（ｔｈｅ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｒｅｓｅａｒｃｈ  ｉｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ）、２３６−２４７ページ、１９９７年  
［４１］Ｐｈｏｅｎｉｘ  Ｔｅｃｈｎｏｌｏｇｉｅｓ、ｈｔｔｐ：／／ｗｗｗ．ｐｈｏｅｎｉｘ．ｃｏｍ／、２００５年  
［４２］Ｒ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ及びＬ．Ａｄｌｅｍａｎ著、「デジタル署名及び公開鍵暗号システムの取得方法（Ａ  ｍｅｔｈｏｄ  ｆｏｒ  ｏｂｔａｉｎｉｎｇ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅ  ａｎｄ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ）」、ＡＣＭ通信２１：１２０−１２６、１９７８年
［４３］Ｍ．Ｒｏｅ、Ｂ．Ｃｈｒｉｓｔｉａｎｓｏｎ及び、Ｄ．Ｗｈｅｅｌｅｒ著、「弱い秘密からセッションを守る（Ｓｅｃｕｒｅ  ｓｅｓｓｉｏｎｓ  ｆｒｏｍ  ｗｅａｋ  ｓｅｃｒｅｔｓ）」、テクニカルレポート、ケンブリッジ大学及びハートフォードシャー大学、１９９８年  
［４４］Ｃ．Ｐ．Ｓｃｈｎｏｒｒ著、「スマートカード用の効率的な識別及び署名（Ｅｆｆｉｃｉｅｎｔ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｏｒ  ｓｍａｒｔ  ｃａｒｄｓ）」、Ｃｒｙｐｔｏ’８９、ＬＮＣＳ４３５、２３５−２５１ページ、１９９０年  
［４５］Ｍ．Ｓｔｅｉｎｅｒ、Ｇ．Ｔｓｕｄｉｋ及びＭ．Ｗａｉｄｎｅｒ著、「暗号鍵交換の改良と拡張（Ｒｅｆｉｎｅｍｅｎｔ  ａｎｄ  ｅｘｔｅｎｓｉｏｎ  ｏｆ  ｅｎｃｒｙｐｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ）」、  ＡＣＭオペレーティングシステムレビュー（ＡＣＭ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ  Ｒｅｖｉｅｗ）２９：２２−３０、１９９５年
［４６］Ｔ．Ｗｕ、「安全な遠隔パスワードプロトコル（Ｔｈｅ  ｓｅｃｕｒｅ  ｒｅｍｏｔｅ  ｐａｓｓｗｏｒｄ  ｐｒｏｔｏｃｏｌ）」、１９９８年インターネットソサエティネットワーク及び分散型システムセキュリティシンポジウム（１９９８  Ｉｎｔｅｒｎｅｔ  Ｓｏｃｉｅｔｙ  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ）、９７−１１１ページ、１９９８年
［４７］Ｔ．Ｗｕ著、「ケルベロスパスワードセキュリティのリアルワールド解析（Ａ  ｒｅａｌ−ｗｏｒｌｄ  ａｎａｌｙｓｉｓ  ｏｆ  Ｋｅｒｂｅｒｏｓ  ｐａｓｓｗｏｒｄ  ｓｅｃｕｒｉｔｙ）」、予稿集、１９９９年ネットワーク及び分散型システムセキュリティシンポジウム（ｔｈｅ  １９９９  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ）、１９９９年２月  
［４８］Ｔ．Ｗｕ著、「テルネット認証（Ｔｅｌｎｅｔ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ）」、  ＳＲＰ．ＩＥＴＦ  ＲＦＣ２９４４、２０００年
［４９］Ｔ．Ｗｕ著、「ＳＲＰ認証及び鍵交換システム（Ｔｈｅ  ＳＲＰ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｓｙｓｔｅｍ）」、ＩＥＴＦ  ＲＦＣ２９４５、２０００年
［５０］Ｔ．Ｗｕ著、「ＳＲＰオープンソースパスワードユーティリティ（ＳＲＰ  ｏｐｅｎ  ｓｏｕｒｃｅ  ｐａｓｓｗｏｒｄ  ｕｔｉｌｉｔｙ）」、ｈｔｔｐ：／／ｓｒｐ．ｓｔａｎｆｏｒｄ．ｅｄｕ／、２００５年  
［５１］Ｍ．Ｚｈａｎｇ著、「ＲＳＡに基づくパスワード認証鍵交換の新手法（Ｎｅｗ  Ａｐｐｒｏａｃｈｅｓ  ｔｏ  Ｐａｓｓｗｏｒｄ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  Ｂａｓｅｄ  ｏｎ  ＲＳＡ）」、ＡＳＩＡＣＲＹＰＴ、２３０−２４４ページ、２００４年  
【図面の簡単な説明】
【０１５５】
【図１】図１は、従来技術によるＰＡＫＥ方法のフローチャートである。
【図２】図２は、従来技術によるＰＡＫＥ方法のフローチャートである。
【図３】図３は、本発明の一実施形態によるＰＡＫＥ方法を説明する図である。
【図１】
2009503934.tif 000062
【図２】
2009503934.tif 000063
【図３】
2009503934.tif 000064
【手続補正書】
【提出日】平成20年3月21日(2008.3.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１コンピュータシステムが第２のコンピュータシステムに対して所定の値πを知っていることを証明する暗号認証方法を行うためにコンピュータに実装される方法であって、
前記第１のコンピュータシステムは、
（１）前記第１及び前記第２のコンピュータシステムの少なくとも一方に対して、前記第１及び前記第２のコンピュータシステムの他方が、前記値πの所定関数を知っていることを証明するプロトコルを実行し、前記プロトコルにおいて用いられるデータを使って暗号鍵Ｋ’を生成する工程と、
（２）ネットワーク上で第１の値を受信する工程と、
（３）前記第１の値に対して復号方法を適用し、復号値を取得する工程と、
（４）前記工程（３）で取得された前記復号値から取得される署名鍵を有するメッセージに対するデジタル署名を生成する工程と、
（５）前記デジタル署名を前記第２のコンピュータシステムに組み込むデータを送信する工程とを有し、
前記復号方法は、
（３Ａ）ｃが、Ｍとは別の任意のｆに対して
【数１】
2009503934.tif 000065
と等しくない（すなわち、前記値
【数２】
2009503934.tif 000066
は、Ｍに基づく）ように、Ｍを第１の暗号値ｃに暗号化する第１の暗号方法と、
（３B）前記第１の暗号値ｃを、前記暗号鍵Ｋ’を用いて第２の暗号値に暗号化する第２の暗号方法と
を用いて暗号化された任意の値Ｍを復号するための方法である
ことを特徴とするコンピュータに実装される方法。
【請求項２】
前記第１の暗号値ｃは、
前記値Ｍに復号可能な第１の部分と、
前記値Ｍを検証するための検証部分と
を有することを特徴とする請求項１に記載の方法。
【請求項３】
前記工程（３）は、前記検証部分を用いて前記復号された値を検証し、前記復号された値の検証において前記復号された値が有効でないことが示された場合、認証失敗を示し、前記工程（５）を省略することを特徴とする請求項２に記載の方法。
【請求項４】
前記検証部分は、少なくとも前記値Ｍに基づく関数の値を含むことを特徴とする請求項２に記載の方法。
【請求項５】
前記関数は、Ｍの一方向関数であることを特徴とする請求項４に記載の方法。
【請求項６】
前記第１の暗号方法において、少なくとも１ビットの前記第１の暗号値ｃは、少なくとも２ビットのＭの関数であることを特徴とする請求項１に記載の方法。
【請求項７】
前記第２のコンピュータシステムと通信するために、前記値πに基づく暗号鍵Ｋ”を生成する工程を更に有することを特徴とする請求項１に記載の方法。
【請求項８】
前記鍵Ｋ”は、前記認証のトランスクリプトにも基づくことを特徴とする請求項７に記載の方法。
【請求項９】
前記メッセージは、前記第１及び前記第２のコンピュータシステム間で、前記工程（５）の前に交換されたデータのトランスクリプトに基づくことを特徴とする請求項１に記載の方法。
【請求項１０】
第１のコンピュータシステムが第２のコンピュータシステムに対して所定の値πを知っていることを証明する暗号認証方法を行うためにコンピュータに実装される方法であって、
前記第２のコンピュータシステムは、
（１）ネットワーク上でデータの送受信を行い、前記第２のコンピュータシステムに対して、前記第１のコンピュータシステムが前記値πの所定関数を知っていることを証明するプロトコルを実行する工程と、
（２）前記値πを用いて値Ｍを暗号化する第１の暗号方法により、署名鍵の暗号化に等しい第１の暗号値ｃを取得する工程と、
（３）第２の暗号方法を適用し、前記プロトコルにおいて用いられるデータを用いて取得された暗号鍵Ｋ’を用いて、前記第１の暗号値ｃを第２の暗号値に暗号化する工程と、
（４）前記第２の暗号値を含むデータを前記第１のコンピュータシステムに送信する工程と、
（５）ネットワーク上で値を受信し、前記署名鍵に対応する検証鍵による検証方法を適用し、受信した前記値がメッセージに対する有効な署名であることを検証する工程とを有し、
ｃは、Ｍとは別の任意のｆに対して
【数３】
2009503934.tif 000067
に等しくない（すなわち、値
【数４】
2009503934.tif 000068
はＭに基づく）値であることを特徴とするコンピュータに実装される方法。
【請求項１１】
前記第１の暗号値ｃは、
前記値Ｍに復号可能な第１の部分と、
前記値Ｍを検証するための検証部分と
を有することを特徴とする請求項１０に記載の方法。
【請求項１２】
前記検証部分は、少なくとも前記値Ｍに基づく関数の値を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記関数は、Ｍの一方向関数であることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記第１の暗号方法において、少なくとも１ビットの前記第１の暗号値ｃは、少なくとも２ビットのＭの関数であることを特徴とする請求項１０に記載の方法。
【請求項１５】
前記第１のコンピュータシステムと通信するために、前記値πに基づく暗号鍵Ｋ”を生成する工程を更に有することを特徴とする請求項１０に記載の方法。
【請求項１６】
前記鍵Ｋ”は、前記認証のトランスクリプトにも基づくことを特徴とする請求項１５に記載の方法。
【請求項１７】
前記メッセージは、前記第１及び前記第２のコンピュータシステム間で、前記工程（５）の前に交換されたデータのトランスクリプトに基づくことを特徴とする請求項１０に記載の方法。
【請求項１８】
請求項１に記載の方法を実行するように構成されているコンピュータシステム。
【請求項１９】
請求項１に記載の方法を実行するコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【請求項２０】
請求項１０の方法を実行するよう構成されているコンピュータシステム。
【請求項２１】
請求項１０の方法を実行するコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【国際調査報告】
2009503934.tif 000069