(57)【要約】  サーバ（１２０）は、パスワードπを用いて、（隠された）スムースな位数の部分群（<ｘ’>）をもつ乗法群ＺＮ＊を生成する。クライアント（１１０）は、パスワードの知識を用いて、群におけるルートエクストラクション問題インスタンス（ｚ）を生成し、サーバが部分群における離数対数問題インスタンス（ｙ’）を生成することを可能とするデータ（ｙ）を生成する。サーバは、群の位数の知識を用いて、ルートエクストラクション問題を解決し、部分群のスムースさを利用することによって、離数対数問題を解決する。共有鍵（ｓｋ）は、離数対数問題インスタンスとルートエクストラクション問題インスタンスとを解決するための関数として計算される。一実施形態における紛失通信では、サーバは、パスワードによって定義される、データベース（２１０）内の位置のデータをクライアントに問い合わせる（２３０）。クライアントは、サーバからの問い合わせに関連付けられたデータの位置を知ることなく、データを提供する（２４０）。クライアントは、パスワードとは別のデータの位置を取得する。データの位置および／または各データは、認証と共有鍵の生成のために用いられる。他の実施形態が提供される。
2008541568.tif 000002
【特許請求の範囲】
【請求項１】
第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、コンピュータに実装される暗号認証方法であって、
前記第１のコンピュータシステムは、
（１）絶対値が１よりも大きい正の整数値である、Ｎとｘとを示すデータを受信する工程と、
（２）整数ｅと、Ｎに対して素である整数ｂとを示すデータを生成する工程と、
（３）  ｙが、ｘｅ  ｍｏｄ  Ｎ  と等しくなり、zが、
【数１】
2008541568.tif 000143
と等しくなるように、値ｙと値ｚとを定義するデータを生成する工程と、
（４）値ｅと値ｂと値Ｐπと値
【数２】
2008541568.tif 000144
のうちのいずれか１つ以上を示すデータを前記第２のコンピュータシステムに送信することなく、前記値ｙと前記値zとを示すデータを前記第２のコンピュータシステムに送信する工程とを有し、
【数３】
2008541568.tif 000145
であり、
Ｐπは、非ゼロ整数の集合ＰＰの真部分集合θ（π）を形成する１つ以上の整数の積であり、
前記真部分集合θ（π）は、前記値πと関連付けられており、
Ｐは、前記集合ＰＰ内の全ての前記非ゼロ整数の積である
ことを特徴とする暗号認証方法。
【請求項２】
第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、コンピュータに実装される暗号認証方法であって、
前記第２のコンピュータシステムは、
（１）合成数Ｎと整数ｘとを示すデータを生成する工程と、
（２）前記値Ｎと前記値ｘとを示すデータを前記第１のコンピュータシステムに送信し、整数値ｙと整数値ｚとを示すレスポンスデータを受信する工程と、
（３）底ｘ’に対するｙ’の対数  ｍｏｄ  Ｐπ  と等しい値ａを示すデータを生成する工程と、
（４）値
【数４】
2008541568.tif 000146
と等しい値ｂを示すデータを生成する工程と、
（５）前記値ａと前記値ｂとを用いて、前記値πの知識を証明する工程とを有し、
ｘ’およびｙ’は、ｘおよびｙから取得され、
Ｐπは、整数の集合ＰＰの部分集合θ（π）を形成する１つ以上の整数の積であり、
前記部分集合θ（π）は、前記値πと関連付けられており、
【数５】
2008541568.tif 000147
は、ＰＰ−θ（π）内の整数の積である
ことを特徴とする暗号認証方法。
【請求項３】
第１および第２のコンピュータシステムのうち少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、かつ／または、前記第１および第２のコンピュータシステムで共有される暗号鍵を生成するために、コンピュータに実装される暗号認証方法であって、
前記第２のコンピュータシステムと双方向で動作する記第１のコンピュータシステムは、
データベース内において、前記値πによって定義される第１の位置のデータを決定する工程と、
前記第１のコンピュータシステムが１つ以上のクエリを受信し、前記第２のコンピュータシステムに前記第２の位置のデータを提供するためのプロトコルを実行する工程と、
前記第１の位置と前記第２の位置とが同一であることを検証し、かつ／または、前記第１の位置と前記第２の位置とが同一であることを前記第２のコンピュータシステムが検証できるように、前記第１の位置の関数を前記第２のコンピュータシステムに送信し、かつ／または、前記第１の位置の関数として前記暗号鍵を生成する工程とを有し、
前記クエリは、第1のコンピュータシステムに対して前記データベース内の第２の位置を知らせることなく、前記第２の位置のデータを取得するためのものであることを特徴とする暗号認証方法。
【請求項４】
第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、コンピュータに実装される暗号認証方法であって、
前記第１のコンピュータシステムと双方向で動作する前記第２のコンピュータシステムは、
前記第２のコンピュータシステムがデータベース内のデータのための１つ以上のクエリを送信し、前記第１のコンピュータシステムから前記クエリに対する１つ以上のレスポンスを受信するためのプロトコルを実行する工程と、
前記所定の位置と前記第１のコンピュータシステムによって前記値πから決定された第１の位置とが同一であることを検証し、かつ／または、前記第１の位置と前記所定の位置とが同一であることを前記第１のコンピュータシステムが検証できるように、前記所定の位置の関数を前記第１のコンピュータシステムに送信し、かつ／または、前記所定の位置の関数として暗号鍵を生成する工程とを有し、
前記クエリは、前記第1のコンピュータシステムに対して前記データベース内の所定の位置を知らせることなく、前記所定の位置のデータを取得するためのものであり、
前記所定の位置は、前記値πによって定義されることを特徴とする暗号認証方法。
【請求項５】
第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、かつ／または、前記第１および第２のコンピュータシステムで共有される暗号鍵を生成するために、コンピュータに実装される暗号認証方法であって、
前記第１のコンピュータシステムは、
（１）群Ｇの記述を示すデータを受信する工程と、
（２）整数ｅと前記群Ｇの要素ｂとを示すデータを生成する工程と、
（３）ｙ＝ｘeとなり、
【数６】
2008541568.tif 000148
となるように、値ｙと値ｚとを定義するデータを生成する工程と、
（４）前記第２のコンピュータシステムが前記値ｅと前記値ｂとに一致する値を示すデータを生成できるように、前記値ｙと前記値ｚとを示すデータを前記第２のコンピュータシステムに送信する工程と、
（５）前記値ｅと前記値ｂとが前記第２のコンピュータシステムによって取得された値と一致することを検証し、かつ／または、前記値ｅと前記値ｂとが前記第２のコンピュータシステムによって取得された値と一致することを前記第２のコンピュータシステムが検証できるように、前記値ｅと前記値ｂとの所定の関数を示すデータを前記第２のコンピュータシステムに提供し、かつ／または、前記値ｅと前記値ｂから前記暗号鍵を生成する工程とを有し、
【数７】
2008541568.tif 000149
は、前記値πに基づいて選択された１つ以上の整数の積であることを特徴とする暗号認証方法。
【請求項６】
所定の安全性値πに基づいて第１及び第２のコンピュータシステムとの間の安全な通信を確立するために、コンピュータに実装される暗号認証方法であって、
前記第２のコンピュータシステムは、
（１）位数が前記値πと所定の関係を有する群Ｇの記述を示す第１のデータを生成する工程と、
（２）前記第１のデータを前記第１のコンピュータシステムに送信し、前記群Ｇの要素ｙと要素ｚとを示すレスポンスデータを受信する工程と、
（３）底ｘ’に対するｙ’の離散対数によって定義される値ａを示すデータを生成する工程と、
（４）値
【数８】
2008541568.tif 000150
を示すデータを生成する工程と、
（５）前記値ａと前記値ｂとを用いて、第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明し、かつ／または、暗号鍵を生成する工程とを有し、
ｙの関数であるｙ’と、ｘ’とは、Ｇの真部分群の要素であり、
【数９】
2008541568.tif 000151
は、前記値πに基づいて選択された１つ以上の整数の積であることを特徴とする暗号認証方法。
【請求項７】
請求項１、３または５に記載の暗号認証方法における第１のコンピュータシステムの動作を行うように構成されているコンピュータシステム。
【請求項８】
請求項１、３または５に記載の暗号認証方法における第１のコンピュータシステムの動作を行うように構成されているコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【請求項９】
請求項２、４または６に記載の暗号認証方法における第２のコンピュータシステムの動作を行うように構成されているコンピュータシステム。
【請求項１０】
請求項２、４または６に記載の暗号認証方法における第２のコンピュータシステムの動作を行うように構成されているコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の説明）
本願は、米国仮特許出願第６０／６７７，４８３号（出願日：２００５年５月３日）に対する優先権を主張する。本明細書中、同文献を参考のため援用する。
【０００２】
本発明は暗号化に関し、より具体的には、パスワード認証などの認証に関する。いくつかの実施形態において、本発明は、２つのコンピュータシステム間の安全な通信チャネルの確立を可能とする。
【背景技術】
【０００３】
ＡｌｉｃｅおよびＢｏｂの２つのパーティが、それぞれコンピュータシステム１１０および１２０（図１）を用いて、安全なネットワーク１３０を介して安全に通信しようとする場合を考えてみる。ＡｌｉｃｅおよびＢｏｂが互いの識別情報を検証するために、短い秘密パスワード（例えば、４桁の暗証番号π）が用いられる場合を想定する。具体的には、ＡｌｉｃｅおよびＢｏｂのいずれも他方のパーティの公開鍵を知らず、また、いずれも認証された公開鍵（すなわち、証明書が他方によって検証できる公開鍵）を有していない。ここで、Ａｌｉｃｅは、通信相手のパーティが本当にＢｏｂであるかを予め確認することができない。このため、Ａｌｉｃｅは、盗聴者についてだけではなく、自身の通信相手のパーティついても心配しなければならない。Ｂｏｂについても、同様の問題がある。
【０００４】
ＡｌｉｃｅおよびＢｏｂが高強度暗号鍵（すなわち、長い秘密）を共有していれば、安全なチャネルを設定するための標準的解法（例えば、［４］；この［］中の数字は、本明細書の最終部分に引用されている参考文献を示す）を用いて、この問題を解決することができる。
【０００５】
しかしながら、ＡｌｉｃｅおよびＢｏｂは、短い秘密パスワードを共有しているだけであるため、オフライン辞書攻撃についても心配しなければならない。オフライン辞書攻撃が発生する状況としては、攻撃者が、パスワード推測のためのオフライン検証を行うことを可能にする情報を取得した場合がある。ここで、攻撃者が取得した情報をパスワード検証情報と呼ぶことにする。例えば、以下の例を考えてみる。ＡｌｉｃｅおよびＢｏｂがパスワードπを共有し、攻撃者が何らかの方法で当該パスワードのハッシュｈ（π）を取得したとする。ここで、ｈは、一般的な暗号ハッシュ関数（例えば、ＳＨＡ−１［４０］）である。この場合、攻撃者はオフラインで可能性のあるパスワード｛π１、π２、…｝の辞書について一通り、ｈ(πｉ)＝ｈ（π）であるか否かを試すことができる。一般的には、攻撃者が取得したパスワード検証情報は、パスワードのハッシュほど簡単ではなく、攻撃者は、当該パスワード検証情報に対して、可能性のあるパスワードの全てを必ずしも試せるわけではない。しかしながら、攻撃者が有意な数のパスワードを試すことができるならば、やはりオフライン辞書攻撃とみなされるべきである。オフライン辞書攻撃が以下に効果的に行われ得るかについてのごく最近の実証については、Ｗｕ［４６］を参照されたい。
【０００６】
パスワード認証に関する多くの一般的技術は、片方向認証技術（すなわち、一方のパーティ（クライアント１１０または１２０のユーザ））が、他方のパーティ（サーバ１２０または１１０）に対して認証されるが、その逆は無い）である。そのため、このような技術の場合、オフライン辞書攻撃に対して脆弱であるか、または、認証された（あるいは他の場合に認証された）公開鍵に依存する。
【０００７】
もっとも簡単なパスワード認証技術としては、クライアントが暗号化せずにパスワードをサーバに送信する方法がある。この技術は、いくつかの従来のインターネットアプリケーションおよび多数のウェブベースのメールアプリケーションにおいて用いられる。この技術は、明らかに、ネットワーク上の盗聴者に対して安全ではないが、盗聴が比較的困難なチャネル上においては容認できるものである。
【０００８】
より先進的な技術としては、チャレンジレスポンス方式がある。この方式では、サーバがクライアントにチャレンジを送信し、クライアントは、当該チャレンジおよびパスワードに応じたメッセージ（例えば、当該チャレンジにパスワードを連結したものに対するハッシュ）でレスポンスする。この種の認証は、ネットワークアクセスを可能とするいくつかのオペレーティングシステムで用いられている。この種の認証は、チャレンジおよびその対応するレスポンスが共にパスワード検証情報を構成するため、盗聴者によるオフライン辞書攻撃に対して脆弱である。
【０００９】
より安全な技術では、匿名セキュアチャネルを介してサーバにパスワードを送信する方式がある。匿名セキュアチャネルでは、サーバが公開鍵を用いて検証されている。この種の認証は、いくつかのリモートターミナルアプリケーションおよびウェブベースのアプリケーションにおいて用いられている。また、この種の認証は、クライアントが有するサーバの公開鍵を検証する機能に本質的に依存する（当該機能が無い場合、攻撃者はサーバになりすますことができる）。ウェブ上で用いられる場合、サーバの公開鍵は、クライアントが信頼すると推定される認証機関により、認証される。一般的に、リモートターミナルアプリケーションの場合、信頼できるサードパーティは存在しないため、安全性は、公開鍵の「指紋」またはハッシュを用いて公開鍵を認識するクライアントに依存する。
【００１０】
パスワード認証型鍵交換（ＰＡＫＥ）
ＰＡＫＥの目的は、事前認証された公開鍵なしに、相互パスワード認証を提供することである。ＰＡＫＥでは、ＰＡＫＥプロトコルを攻撃するための実行可能な方法が、単にパスワードを反復的に推測し、パーティの１つになりすまそうとするオンライン辞書攻撃のみとなる（なお、オンライン攻撃は、検出および阻止が比較的容易である）。ＰＡＫＥプロトコルを用いて、認証側パーティは、短い秘密（パスワード）を長い秘密（暗号鍵）に「ブートストラップ」することができる。なお、この長い秘密（暗号鍵）は、安全なチャネルを提供するために用いられる。
【００１１】
安全なＰＡＫＥプロトコルの設計にまつわる問題について、ＢｅｌｌｏｖｉｎおよびＭｅｒｒｉｔｔ［６］ならびにＧｏｎｇら［２５］によって提案が為されており、広範囲にわたって研究されている。多数のＰＡＫＥプロトコルは、例えば、［７、２５、２４、２８、２９、３６、４４、４５、３３、３２］において提案されており、これらのプロトコルのうち多数が、安全ではないことが分かっている（例えば、［４１］を参照）。最近のプロトコルは、周知の暗号仮定に基づいて安全性が証明されているが、これらの証明のいくつかは、理想的なハッシュ関数または理想的な暗号（すなわち、ブラックボックスで完全にランダムな関数（ランダムオラクル）または鍵置換）の存在を前提としている。最近の論文［２、１０、１］では、ＥＫＥプロトコルの改良が提示され［７］、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＨ）仮定に基づいて安全性が証明されている［１９］。第１の論文は、理想的な暗号および理想的なハッシュを前提とし、他方の論文は、理想的なハッシュのみを前提としている。他の論文［３７、４７］は、ＯＫＥプロトコルの改良［３６］を提示し、ＲＳＡ仮定に基づいて安全性が証明されている［４３］。これらの論文は全て、理想的なハッシュを前提としている。別の論文［３１］では、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号システムの改良に基づく新規なプロトコル［１６］が提示され、ｄｅｃｉｓｉｏｎａｌ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）仮定（例えば、［８］を参照）に基づいて安全性が証明されている。当該論文では、公開ランダム文字列（これは、理想的なハッシュ関数ではない）のみを前提としている。［３１］プロトコルのいくつかの変形例が、［２１、３０、１３］に提示されている。別のパスワード認証型鍵交換プロトコルが［２３］において開発されており、いかなるセットアップ仮定も必要とせずに、トラップドア置換に基づいて安全性が証明されている。ただし、同一パスワードでの同時セッションが禁止されているという制約はある。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
効率的なＰＡＫＥプロトコルを設計するための多くの既存技術は、基本パラダイムの改良であり、かなりの既存技術が、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定またはＲＳＡ仮定のいずれかに基づいている。特に、効率的で安全なＰＡＫＥプロトコルを設計するためのかなりの既存技術は、以下の２つの基本的なパラダイムのうち１つに当てはまる。
【００１３】
・パスワードを用いて、メッセージのうち一部を暗号化して鍵交換を行う（例えば、［１、６、１０、３１、３７、４６、４７］）。あるいは、
・パスワードを用いて、標準的鍵交換におけるパラメータを選択する（例えば、［２８、３２］）。
【００１４】
ＰＡＫＥ達成のための別のアプローチでは、ＮａｏｒおよびＰｉｎｋａｓによって紹介されたプリミティブである秘密多項式評価法（ＯＰＥ）が用いられる［３９］。ＯＰＥは、より一般的な形態の紛失通信（ＯＴ）であり、Ｒａｂｉｎによって最初に提案された［４２］。［３９］の提案後、ＧｏｌｄｒｅｉｃｈおよびＬｉｎｄｅｌｌ［２３］は、ＯＰＥを用いることにより、トラップドア置換のみを用いた標準的モデルでＰＡＫＥを達成できることを示した。これらは重要な理論的貢献であるが、ＯＰＥに基づいたＰＡＫＥプロトコルは、多くの効率的なＰＡＫＥプロトコルに対して競合力を持っていない。
【課題を解決するための手段】
【００１５】
以下において、本発明のいくつかの特徴をまとめる。本発明は、添付の特許請求の範囲により、定義される。
【００１６】
２つのコンピュータシステム（一方を「クライアント」とし、他方を「サーバ」とする）間の通信のための実施形態をいくつか例示する。例えば、図１において、コンピュータシステム１１０はクライアントであり、コンピュータシステム１２０はサーバである。しかしながら、ある実施形態は、任意のコンピュータシステムに適している。「クライアント」および「サーバ」は相互交換することができ、さらに、コンピュータシステムは、相互にクライアントおよびサーバでなくてもよい。
【００１７】
ある実施形態では、サーバは、位数がパスワードπに対して所定の特性を有するの群を生成する。例えば、この群を、ＺＮ＊とする。この群は、オイラーのファイ関数φ（Ｎ）が、パスワードπに基づいて選択されたいくつかの数で割り切れ、かつ、当該パスワードに基づいて選択された他のいくつかの数に対して素となる。この群の記述は、クライアントに送信される。ある実施形態では、群の位数はクライアントに提供されない。
【００１８】
クライアントは、この群において、ルートエクストラクション問題インスタンスおよび離散対数問題インスタンスを生成し、当該２つのインスタンスをサーバへと送信する。サーバがパスワードを知らない場合、サーバが当該２つの問題インスタンスを正確に解くことのできる可能性は無視できるほどに小さい。一実施形態において、サーバは、群Ｇにおける離散対数問題をＧの部分群における異なる離散対数問題へと変換する。一実施形態において、この部分群は、Ｇよりも低い位数を持つため、離散対数問題をより効率的に解くことができる。一実施形態において、この部分群は、Ｇよりも低い位数を持っても持たなくてもよい。しかし、この部分群は、合成数の位数の巡回部分群であるため、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズム（下記の付録に記載）を用いて、離散対数問題をより低い位数の部分群における離散対数問題まで低減することができる。特に、この合成数の位数が「スムース」である（すなわち、合成数の位数が、素因数の指数ｐｅ（ｐ）の積であり、値ｐが全て小さい範囲内にある）場合、高い効率を得ることができる。一実施形態において、離散対数問題インスタンスおよび／またはルートエクストラクション問題インスタンスはパスワードに基づいて生成されるため、クライアントのパスワードに関する知識の証拠となる。ルートエクストラクション問題インスタンスおよび離散対数問題インスタンスは、パスワードよりも多くのエントロピーを有する（すなわち、攻撃者による予測がより困難であるため、オフライン辞書攻撃に対してより安全である）共有秘密鍵ｓｋを生成することにより、解決することができる。このエントロピーの増加は、秘密鍵ｓｋがパスワードπよりも長いことに起因する。あるいはまたはさらに、一般的な単語または句、誕生日、電話番号、または人間に対して意味を為すためパスワードとして選択されやすい文字列ではなく、よりランダムな文字列である秘密鍵を用いることにより、エントロピーを増加することができる。
【００１９】
一実施形態において、サーバおよびクライアントは、紛失通信プロトコルに係る。サーバは、データベース内の位置がパスワードによって定義されたデータについて、クライアントに問い合わせる。例えば、クライアントは、ランダム文字列の対の集合であるデータベースを生成し、サーバは、各対から１つの文字列を選択する。クライアントは、サーバのクエリと関連付けられている、データ位置を知ることなく、要求されたデータをサーバに提供する。例えば、一実施形態において、クライアントは、データベース全体を暗号化された様態でサーバに送る。そして、サーバは、所望の位置のデータを復号化できるが、残りのデータの復号化はできないようにし、一方、クライアントは、サーバがデータ全体の復号化はできないことを確認できるが、サーバが復号可能なデータを判定することはできないようにする。しかしながら、クライアントはパスワードを知っているため、クライアントは、別のデータ位置を取得する。その後、クライアントおよびサーバは、データ交換を行って、それぞれが互いに同一のデータ位置を持つことを検証することができる。例えば、クライアントは、クライアントのデータ位置および／または各データのハッシュ関数Ｈ１である確認値ν１を計算し、この値ｖをサーバに送信する。サーバは、その自身のデータ位置および／またはクライアントから得たデータについて同一ハッシュ関数を計算し、サーバは、その結果得られた値がνに等しいことを確認する。サーバは、異なるハッシュ関数Ｈ２を用いて計算された別の確認値ν２をクライアントに提供して、クライアントが同様の検証を行うことを可能にする。また、データ位置または各データを用いて、共有秘密鍵ｓｋ（例えば、データ位置および／または各データのハッシュ関数Ｈ０）を生成することができる。鍵ｓｋならびに確認値ν１およびν２は補助データ（例えば、カウンタまたはノンス）によるものでもよく、これにより、これらの鍵および確認値がフレッシュであることが保証できる。これらの鍵および確認値は、パスワードによるものでもよい。一実施形態において、確認値の前に鍵を生成し、確認値をハッシュ関数ｓｋ（例えばｖ＝Ｈ（ｓｋ））として生成する。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の一実施形態について説明する。本発明は、特定の計算、プロセッサおよび他の特徴によって限定されない。本発明は、添付の特許請求の範囲によって説明される。
【００２１】
以下の記述において、本発明のより詳細な説明を提供するため、多数の詳細について説明する。しかしながら、本発明はこれらの特定の詳細無しでも実施可能であることは、当業者にとって明らかである。他の場合において、周知の構造およびデバイスは、本発明を不明瞭にしないために、詳細にではなく、ブロック図の様態で図示している。
【００２２】
以下の詳細な説明のいくつかの部分は、コンピュータメモリ内のデータビット上の動作のアルゴリズムおよび記号の表示によって説明される。これらのアルゴリズム記述および表示は、データ処理分野の当業者がその研究の要旨を他分野の当業者に対して最も効果的に伝えるために用いられる手段である。アルゴリズムとは、物理量の物理的操作を必要とする方法である。通常、必要ではないが、これらの量は、保存、転送、組み合わせ、比較および他の場合に操作が可能な電気信号または磁気信号の形態をとる。これらの信号をビット、値、要素、記号、文字、用語、数字などと呼ぶと便利であるし、また通常用いられていることが多い。
【００２３】
以下の説明中、「処理」または「計算」または「計算」または「決定」または「表示」などの用語は、コンピュータシステムまたは類似の電子計算デバイスの動作およびプロセスを指示するものである。なお、上記動作およびプロセスは、コンピュータシステムのレジスタおよびメモリ内の物理（電子）量として表されるデータを、コンピュータシステムメモリまたはレジスタあるいは他のこのような情報保存デバイス、伝送デバイスまたは表示デバイス内の物理量として同様に表される他のデータに、操作および変換するものである。
【００２４】
本発明の一実施形態は、ハードワイヤード回路構成および／またはソフトウェアコンピュータプログラムに実装することができる。このようなコンピュータプログラムは、コンピュータ読み出し可能な記憶媒体（例えば、任意の種類のディスク（例えば、フロッピー(登録商標)ディスク、光学ディスク、ＣＤ−ＲＯＭ、および光磁気ディスク、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カードまたは光学カード（ただし、これらに限定されない））、あるいはコンピュータ命令の保存に適した、コンピュータシステムバスにそれぞれ連結された任意の種類の媒体またはデータキャリア内に保存することができる。コンピュータプログラムは、ネットワークを介してデータキャリア信号によって搬送されてもよい。よって、これらのプログラムは、キャリア波、赤外線信号、デジタル信号などによって搬送することができる。
【００２５】
暗号分野の当業者にとって、多くの暗号関連発明の安全性がある計算量的困難性の仮定（例えば、暗号システムは、ある数字をその素因数に効率的に分解することが困難である限り、安全であるが証明されている）に依存することはよく知られている。「計算的」という用語は、当該分野において、このクラスの暗号発明を特定する際に用いられることが多い。本発明は、パスワード認証型鍵交換のための計算的スキームを提供する。「情報理論的」または「無条件」という用語は、当該分野において、特定の意味のある安全性の定義を（任意の種類の仮定無く）数学的に満足すると思われるスキームと関連して用いられることが多い。
【００２６】
安全性的側面だけから見ると、どのようなものであれ、いかなる計算的仮定も無い方が一般的には好ましいが、このような仮定無しには解決することができない問題が実際には存在する（本発明は、このような例として機能する）。特に、当該分野の現状によれば、公開鍵暗号化を要求すること無くＰＡＫＥスキームを構築するのは不可能である［２７］。さらに、当該分野の現状によれば、特定の様態の計算的仮定無しに、公開鍵暗号化を実装する方法は不明である。そのため、当該分野における全てのＰＡＫＥスキーム（例えば、本明細書中記載のもの）は、何らかの様態の計算的仮定を必要とする。これらの仮定については後述する。さらに、計算的仮定を取り入れることによって暗号方法をより効率的にすることが可能である場合もあることが、当業者にとって一般的に知られている。
【００２７】
また、１つの仮定が別の仮定を暗示する場合がある点も留意に値する。すなわち、仮定のうち１つが真である場合、数学的な論理的根拠により、別の仮定も真であるとされる。典型的には、このような暗示を示すために当業者によって用いられる手段として、変換（これは、当該分野において節減として知られている）がある。この変換により、第２の仮定を侵害するメカニズムを、第１の仮定を侵害するメカニズムに変換する。このような場合、第１の仮定が「より強い」とされ、あるいは第２の仮定が「より弱い」とされる。一般的に、より弱い仮定が好適である。
【００２８】
１．準備
まず、いくつかの表記を説明する。通常、Ｚは、整数環を示し、ＺＮは、正の整数Ｎを法とする最小の非負の剰余の環である。環については、アスタリスク（＊）が、環の乗法群を示す。そのため、ＺＮ＊は、（ＺＮの全可逆元からなる）ＺＮの乗法群である。φ（Ｎ）は、オイラーのファイ関数である（これは、Ｎ未満であり、かつＮに対して素である正の整数の数に等しい）。
【００２９】
群Ｇの場合、｜Ｇ｜は、Ｇの位数を示す。群要素ｘの場合、＜ｘ＞は、ｘによって生成される巡回部分群を示す。「ｇｃｄ」という頭字語は、「最大公約数」を示す。
【００３０】
本発明の一実施形態では、ＰＡＫＥを達成するために紛失通信のいくつかの局面を用いる。第１に、１−ｏｕｔ−ｏｆ−２（文字列）ＯＴプロトコルでは、送信者は、２つの文字列ｒ０およびｒ１で開始し、選択者は、ビットｂ∈｛０、１｝で開始する。このプロトコルの最後に、選択者は、ｒ１―ｂに関するいかなる情報も知ることなく、かつ送信者に対するｂに関する情報を明らかにすること無く、ｒｂを知る。１つの例（図２）において、システム１１０（例えば、クライアント）は、「送信者」の役割を果たし、システム１２０（例えば、サーバ）は、「選択者」として機能する。
【００３１】
より具体的には、一実施形態において、クライアントおよびサーバ双方は、メモリ内にパスワードπを保存する。数値２０４は、パスワードと、クライアントまたはサーバのパスワードを格納する物理的メモリとの双方を示す。クライアントは、ｎ個の対のエントリ｛（ｐ１，０，ｐ１，１），（ｐ２，０，ｐ２，１）．．．（ｐｎ，０，ｐｎ，１）により、ランダム「データベース」２１０を生成する。各エントリｐｉ，ｊは、例えば、２ｌビットの文字列である。パスワードは、（恐らくは単射的に）ｎビット文字列にマッピングされる。図２の例において、パスワードπは、文字列ｓ＝０１…１であるか、または文字列ｓ＝０１…１にマッピングされる。各数字ｉ＝１、…ｎについて、ビットｓｉを用いて、対（ｐｉ，０，ｐｉ，１）の数の位置（０または１）を定義する。例えば、一実施形態において、ｓｉ＝０である場合、ビットｓｉはデータベースエントリｐｉ，０と関連付けられ、ｓｉ＝１である場合、ビットｓｉはデータベースエントリｐｉ，１と関連付けられる。そのため、図２の例において、パスワードπ（ｓ＝０１…１）は、エントリｐ１，０，ｐ２，１…１ｐｎ，１の文字列と関連付けられる。サーバ１２０は、これらの文字列ｓを計算し、各数字ｉについて、対（ｐｉ，０，ｐｉ，１）から位置ｓｉにおけるデータベースエントリを回復するための１−ｏｕｔ−ｏｆ−２ＯＴクエリ２３０を構築する。クライアントは、サーバのクエリにレスポンスする（２４０）。サーバ１２０は、このレスポンスを用いて、対応するデータベースエントリを計算する（２４４）。サーバは、他のデータベースエントリについて知ることは無く、対２１０内で２４４において計算されたエントリの位置を知ることも無い。よって、サーバは、クライアント側のパスワードπまたは文字列ｓを知ることが無い。同様に、クライアントは、サーバ側のパスワードπまたは文字列ｓを知ることが無い。クライアント１１０は、確認値ν１を計算する（２４６）。確認値ν１の計算には、例えば、ハッシュ（クライアント側のパスワードと当該パスワードに対応するｎ個のデータベースエントリを含む文字列の公開ハッシュ関数Ｈ１）が用いられる。クライアントは、確認値ν１をサーバに送信する（２５０）。サーバは、２４４において計算されたエントリで同様のハッシュを計算し（２５２）、この計算の結果が
ν１と異なる場合、処理を中止する。これら２つの値が等しい場合、認証動作はサーバにおいて成功したと見なされる。（もちろん、この認証動作を他の認証動作と組み合わせてもよい）。
【００３２】
必要に応じて、サーバは、サーバがパスワードを知っている旨の確認をクライアントに提供する。例えば、２５４において、サーバは、確認値ν２を計算する。確認値ν２の計算には、例えば、ハッシュ（２４４において計算されたｎ個のデータベースエントリおよびパスワードを含む文字列の公開ハッシュ関数Ｈ２）が用いられる。サーバは、確認値ν２をサーバに送信する（２６０）。クライアントは、クライアント側のパスワードから決定されたエントリで同様のハッシュを計算し（２６１）、この計算の結果がν２と異なる場合、処理を中止する。これら２つの値が等しい場合、認証動作は、認証動作はクライアントにおいて成功したと見なされる。
【００３３】
確認値ν１はパスワードの関数であるため、クライアントは、パスワードπを知らずに認証プロトコルを完成することはできない。確認値がパスワードの関数ではない場合、クライアントは、各ｉ（各ｉについて、ｐｉ，０＝ｐｉ，１）に関する全く同一のデータベース番号を選択することによってだますことができ、その結果、クライアントは、パスワードを知ることなくプロトコルを完成することができる。
【００３４】
サーバを検証することを重要視する場合、ステップ２４６、２５０および２５２は省略してもよい。
【００３５】
その後、（２６２における）クライアントおよび（２６４における）サーバは、共有暗号鍵ｓｋを計算する。共有暗号鍵ｓｋは、パスワードに対応するｎ個のエントリ（これらのエントリは、クライアントによる文字列ｓによって定義され、２４４においてサーバによって計算される）の関数（例えば、公開ハッシュ関数Ｈ０）である。一実施形態において、鍵ｓｋは、パスワードπよりもより多くのエントロピーを持つ（例えば、より長くかつ／または人間にとってよりランダムに見える）。鍵ｓｋは、クライアントとサーバとの間の後続通信の対称暗号化のために用いることができる。悪意を持つクライアントに対する安全性は、ＯＴスキームの選択者のプライバシーに従う。概略を説明すると、悪意を持つサーバに対する安全性は、送信者のプライバシーに従う。サーバは、クライアントのＯＴレスポンスを用いて、１つのパスワード（すなわち、サーバがＯＴクエリをパラメータ化するのに用いられるパスワード）のみを検証することができる。サーバの推測が誤っている場合、送信者のプライバシーは、クライアントがハッシュに入力した高エントロピーの文字列（２ｌビット）のうち１つに関する情報をサーバが実質的に保持しないことを保証し、その結果、クライアントのハッシュをパスワード検証情報として用いることができない。
【００３６】
本発明は、図２の正確な工程または工程シーケンスに限定されない。例えば、クライアントおよびサーバは、それぞれ、工程２４６および２５２の前に鍵を計算してもよく、その後、共有鍵のハッシュ関数である確認値ν１およびν２（例えば、ν１＝Ｈ１（ｓｋ）、ν２＝Ｈ２（ｓｋ））を計算してもよい。他の改変例も可能である。
【００３７】
一実施形態において、我々は、エラー訂正コードを用いることにより、我々のスキームの性能を改善する。すなわち、図３に示すように、パスワードπをｋ＜ｎのｋビットの文字列にマッピングし（例えば、パスワードπは、ｋビットの文字列となる）、最小距離ｄを有するコードを用いて、ｋビットの文字列をｎビットの文字列ｓにマッピングする（後者のマッピングを図３のａとして図示する）。この設定においては、サーバ１２０は、パスワードπの検証を実行できるだけである。なお、当該パスワードのｎビットの文字列ｓは、ｎ個のＯＴクエリと関連付けられたｎビットの文字列に（Ｈａｍｍｉｎｇ距離的に）最も近い。他の候補パスワードについては、（簡単に言えば）クライアントがハッシュ関数に入力する少なくともｄｌビットに足りない。多様な性能の「スゥイートスポット」については、（ｎ，ｋ，ｄ，ｌ）を次の条件とすることで発見される。すなわち、ｄｌは、オフライン推測を実行不可能にする位に十分に大きく（例えば、８０）し、ｎｌは、効率のために合理的に小さくし、（ｎ，ｋ，ｄ）は、効率的なエラー訂正コードに対応するようにする。この設定において、我々の高レベルなＯＴベースの記述は必要以上に強いことが分かる。なぜならば、１−ｏｕｔ−ｏｆ−２ＯＴスキームが全体として安全である限り、１−ｏｕｔ−ｏｆ−２ＯＴスキームが個別に安全であることを必要とされないからである。さらに、我々のＰＡＫＥスキームの一実施形態は、（全データベースではなく）十分にランダムなデータベース２１０の集合のために機能する。また、我々のＰＡＫＥスキームの一実施形態では、ｎ個のＯＴクエリおよびレスポンスを１つの短いクエリおよびレスポンスに効率的に「バッチング」するための数論的方法も用いる。
【００３８】
一実施形態において、我々のスキームでは、ｎ個の（公開）対の素数｛（ｐｉ，０，ｐｉ，1）：ｉ∈［１，ｎ］｝を用い、また、或る意味において、互いに「双対」である２つの問題を用いる。すなわち、巡回群Ｇおよび素数ｐについて、以下を用いる。
【００３９】
・（離散対数（弱体化バージョン））：生成元ｘ∈Ｇおよびｈ＝ｘｅとし、ｅ  ｍｏｄ  ｐ  を計算する。
【００４０】
・（ルートエクストラクション）：Ｊ∈Ｇとし、ｊｌ／ｐを計算する。
【００４１】
なぜこれらの問題は相互に「双対」なのだろうか？第１に、ｐで群の位数｜Ｇ｜を除算する場合を考える。その後、上記の離散対数問題は、｛０，．．．，ｐ−ｌ｝で唯一の解法を有する。しかしながら、ｊがＧ内のｐ留数である場合（すなわち、ｊがＧ内の要素のｐ乗である場合）、ルートエクストラクション問題に対する解法は唯一ではなく、ｐ個の有効解法がある。次に、ｐで｜Ｇ｜を除算しない場合について考える。ここで、これら２つの問題の「可解性」状況が逆転する。ルートエクストラクション問題は、唯一の解法を有する（ＲＳＡ復号化は、この事実に基づく）。しかしながら、離散対数問題は、ｐ個の有効解法を有する。すなわち、ｅ’∈Ｚがｈ＝ｘｅ’を満足する場合、全ての｛ｅ＝ｅ’＋ｒ｜Ｇ｜：ｒ∈Ｚ｝について、ｈ＝ｘｅが成り立つ。ｇｃｄ（ｐ，｜Ｇ｜）＝１であるため、ｅ  ｍｏｄ  ｐ  の値は、｛０，…，ｐ―１｝の全てを網羅する。
【００４２】
これを念頭において、クライアント１１０（図４）は、図２のようにデータベース２１０を生成するが、この時、データベースは、サーバ１２０と共有される。あるいはデータベースは、サーバ１２０および／または他のパーティによっても生成されてもよい。数字ｐｉ，ｊは、異なる値であり、素数であり、または少なくとも対関係において互いに素である。クライアントおよびサーバはそれぞれ、自身側のパスワード２０４を秘密にして保持する。４１０において、サーバは、群Ｇの位数が数字
【数１】
2008541568.tif 000003
【００４３】
の全てで割り切れるように（ただし、
【数２】
2008541568.tif 000004
【００４４】
ではない）、群Ｇを構築する（一実施形態において、Ｇ＝ＺＮ＊であり、ここで、Ｎは合成数であり、サーバによって生成されたＲＳＡ係数である）。サーバは、群Ｇの記述（例えば、係数Ｎ）および群の生成元ｘをクライアントに送信する（４２０）。クライアントは、Ｇ、ｘを用いて、サーバに対する「チャレンジ」を生成して、
【数３】
2008541568.tif 000005
【００４５】
に関する離散対数問題のインスタンスおよび
【数４】
2008541568.tif 000006
【００４６】
に関するルートエクストラクション問題のインスタンスを解く。例えば、一実施形態において、それぞれｉ＝１，…ｎの場合、
１．クライアントは、ｅｉ∈Ｚをランダム生成し（４３０）、その後
【数５】
2008541568.tif 000007
【００４７】
を計算する（４４０）。
【００４８】
２．クライアントは、ｂｉ∈Ｇをランダム生成し（４５０）、その後
【数６】
2008541568.tif 000008
【００４９】
を計算する（４６０）。
【００５０】
４７０において、クライアントは、値ｙｉおよびｚｉをサーバに送信する。サーバは、離散対数問題
【数７】
2008541568.tif 000009
【００５１】
を解く。このように、クライアントは、ｙｉから、
【数８】
2008541568.tif 000010
【００５２】
を決定する（４７４）。一実施形態では、離散対数問題は、Ｇの真部分群内で解かれるため、当該離散対数問題を効率的に解くことができる。
【００５３】
サーバは、ルートエクストラクション（開方）を行って、ｚｉからｂｉを決定する（４７８）。Ｇの位数が
【数９】
2008541568.tif 000011
【００５４】
の全てで割り切れる場合（ただし、
【数１０】
2008541568.tif 000012
【００５５】
ではない）にのみ、
その解ｅｉおよびｂｉは、唯一である。
【００５６】
その後、クライアントおよびサーバは、自身の各値ｂｉと
【数１１】
2008541568.tif 000013
【００５７】
とが同一であり、かつ、同一パスワードに対応することを検証する。例えば、クライアントおよびサーバは、それぞれ、クライアントおよびサーバのパスワードから構築されたいくつかの値に２つの公開ハッシュ関数Ｈ０およびＨ１を適用する（４８０、４８４）。図４の例において、これらの値は、形式（π，ａｉ，ｂｉ）の文字列である（クライアントは、４３０において生成された値ｅｉからａｉを決定する）。このような文字列は、ｉごとに構築してもよいし、あるいは、全てのｉについての値ａｉおよびｂｉを含む単一の文字列が形成されてもよい。値ａｉおよびｂｉの代わりに、または値ａｉおよびｂｉに加えて、当該文字列は、値
【数１２】
2008541568.tif 000014
【００５８】
のいくつかまたは全てを含んでもよく、あるいは値
【数１３】
2008541568.tif 000015
【００５９】
のいくつかまたは全てを含んでもよい。図４において、関数Ｈ０の値は、クライアント側ではν０と、サーバ側ではν’０と示される。関数Ｈ１の値は、クライアント側ではν１と、サーバ側ではν’１と示される。その後、クライアントは、ν０をサーバに送信し（４８６）、サーバは、ν’１をクライアントに送信する（４８８）。サーバは、クライアントのν０がサーバのν’０に等しい場合、認証ステップが成功したと見なす（４９０）。同様に、クライアントは、クライアントのν１がサーバのν’１に等しい場合、認証ステップが成功したと見なす（４９２）。共有認証鍵ｓｋは、クライアントおよびサーバにより、値
【数１４】
2008541568.tif 000016
【００６０】
または、値
【数１５】
2008541568.tif 000017
【００６１】
および／または値ａｉ、ｂｉ、πおよび／または他の値の関数として、生成されてもよい（このステップは、図４において図示していない）。鍵ｓｋはハッシュ関数として生成され、一実施形態において、値ν０、ν’０、ν１、ν’１は、図２を参照して上述したように、共有鍵ｓｋのハッシュとして生成される。
【００６２】
一実施形態において、離散対数およびルートエクストラクション（開方）がまとめて処理され、これにより、サーバは、
【数１６】
2008541568.tif 000018
【００６３】
を位数とするＧの部分群において、単一の離散対数問題を行い、１つの群要素の累乗根
【数１７】
2008541568.tif 000019
【００６４】
を計算する。一実施形態において、ｐｉ，ｊは小さな素数であるため、サーバは、例えばＰｏｈｌｉｇ−Ｈｅｌｌｍａｎおよびｂａｂｙ−ｓｔｅｐ／ｇｉａｎｔ−ｓｔｅｐアルゴリズム（［４８］）を用いて、
【数１８】
2008541568.tif 000020
【００６５】
をを位数とする部分群において、離散対数問題を極めて効率的に解くことができる。悪意を持つクライアントに対する安全性は、Ｃａｃｈｉｎ、Ｍｉｃａｌｉ、およびＳｔａｄｌｅｒのハイディング仮定
【数１９】
2008541568.tif 000021
【００６６】
［１１］の変形例に基づいており、すなわち、適切に生成された合成数係数Ｎがおおよそ与えられた場合、２つの数字Ｐ１およびＰ２のうちの１つが絶対にφ（Ｎ）を除算すると分かっている（ここで、Ｐ１およびＰ２は、それぞれ素数のｎの積であり、各対からの１つである）場合にも、これら２つの数字Ｐ１およびＰ２のうちどちらがφ（Ｎ）を除算するのかを区別するのは困難である。
【００６７】
我々のスキームの一実施形態は、効率的である。我々は、一実施形態を実施し、多様なコンピュータプロセッサにおいて実験を行った。３２ビット符号語（ｎ＝３２）にマッピングされた１４ビットのパスワード（例えば、暗証番号）の場合、我々のスキームでは、３．２０ＧＨｚのＸｅｏｎプロセッサ上で２６（各２３）ミリ秒のクライアント（各サーバ）の計算が必要となる。６４ビット符号語にマッピングされたパスワードの任意辞書と共に用いる場合、本スキームでは、クライアントおよびサーバ双方においておよそ２倍の計算が必要となる。
【００６８】
パスワードの集合に関する表記
ここで、Πを辞書内のパスワードπの集合とし、ｆΠ：Π→｛０，１｝ｋを、長さｋの文字列にパスワードをマッピングする関数とする。例えば、暗証番号の場合、これは、識別情報マッピングであってもよく、任意の辞書の場合、これは、衝突耐性ハッシュ関数であってもよい。ここで、α：｛０，１｝ｋ→｛０，１｝ｎを距離ｄのエラー訂正コードとする。よって、α（ｆΠ（π））は、パスワードπに対応するｎビット符号語となる。このｎビットの文字列をｓπとする。
【００６９】
素数の集合に関する表記
ここで、ＰＰ＝｛ｐ１，０，ｐ１，１，ｐ２，０，ｐ２，１，…，ｐｎ，０，ｐｎ，１｝を、（概念的に）対に分割された２ｎ（ｌ＋１）ビットの素数の集合であるとする。ここで、
【数２０】
2008541568.tif 000022
【００７０】
とする。文字列ｓ∈｛０，１｝ｎの場合、θ（ｓ）が
【数２１】
2008541568.tif 000023
【００７１】
と等しいとし、
【数２２】
2008541568.tif 000024
【００７２】
とする。各パスワードπについて、
【数２３】
2008541568.tif 000025
【００７３】
とし、
【数２４】
2008541568.tif 000026
【００７４】
とする。ここで、
【数２５】
2008541568.tif 000027
【００７５】
は、ｓのビット単位の補数である（すなわち、
【数２６】
2008541568.tif 000028
【００７６】
）。係数Ｎについては、ＰＰＮとして示されるＮの素数集合が、ＰＰ内のφ（Ｎ）の素因数であるとする。
【数２７】
2008541568.tif 000029
【００７７】
の場合、要素
【数２８】
2008541568.tif 000030
【００７８】
をＰＰに関する疑似的な生成元とする。
【００７９】
エラー訂正コード
我々のＰＡＫＥプロトコルの一実施形態では、バイナリエラー訂正コード（ＥＣＣ）（具体的には、ＢＣＨコード［９，２６］（［３５］を参照））が用いられる。ここで、このようなコードに関連するいくつかの用語が定義される。
【００８０】
（ｎ，ｋ，ｄ）エラー訂正コードは、ｋ個の文字列をｎビット符号語にマッピングする際、２つの符号語間のＨａｍｍｉｎｇ距離が少なくともｄとなる（ビット文字列ａとビット文字列ｂとの間のＨａｍｍｉｎｇ距離は、
【数２９】
2008541568.tif 000031
【００８１】
内の１の数である）。このようなコードは、
【数３０】
2008541568.tif 000032
【００８２】
個のエラーを訂正することができる。しかしながら、一実施形態では、エラーを実際には訂正することはなく、符号語を復号することも全くない。ビット文字列を符号化することと、２つの符号語は少なくともｄのＨａｍｍｉｎｇ距離を持つという事実を利用することとが単に必要とされる。
【００８３】
ハッシュ関数
鍵生成および検証値生成のためにハッシュ関数Ｈが用いられる。我々の安全性の証明のため、ハッシュ関数が、ブラックボックスの完全ランダム関数（すなわち、ランダムオラクル［３］）のように動くと仮定する。ランダムオラクルが真のハッシュ関数［１２］によってインスタンス化される場合、ランダムオラクルモデルにおいて安全なプロトコルは、必ずしも安全であるとは限らないことを示したが、ランダムオラクルモデルにおける安全性の証明は、プロトコルの安全性の信頼性を提供する。
【００８４】
システムモデル
一実施形態では、クライアントの集合Ｃｌｉｅｎｔｓとサーバの集合Ｓｅｒｖｅｒｓとが存在すると仮定する。我々のＰＡＫＥプロトコルは、クライアントＣ∈Ｃｌｉｅｎｔｓと、サーバＳ∈Ｓｅｒｖｅｒｓとの間で実行される。一実施形態では、Ｃ１１０は、任意のサーバ毎の情報（例えば、サーバ証明書）や任意のパスワードデータを保存する必要はない。Ｃが保存するのは、プロトコル記述と当該プロトコルの公開パラメータとのみである。Ｃは、入力５１０（図５）により、パスワードπｃ（πとして示す）と、Ｃが行うＰＡＫＥプロトコルの相手先であるサーバの識別情報Ｓとを受信する。入力５１０は、ユーザ（例えば、図１のＡｌｉｃｅ）から受信される。Ｓは、Ｃ毎のレコードπｓ［Ｃ］からなるパスワードファイル５１４を保存する。このレコードは、例えば、パスワードの関数またはＰＡＫＥプロトコルにおいてＣを認証するために用いられる他の補助データを含んでもよい（この仮定は、実際には効率のみのためである。パスワードのみが与えられた場合にこれらの値をオンザフライで計算することにより、サーバに実装することができる）。本セクションにおいて、５１０および５１４のような参照符号は、値と当該値を含む物理的コンピュータストレージとの双方を示す。クライアントおよびサーバは、異なる相手とＰＡＫＥプロトコルを複数回行うことができると仮定する。また、各参加者のためにプロトコルの無限数の（おそらくは同時の）インスタンスを可能にすることにより、これをモデル化する。クライアントＣのインスタンスｉは、
【数３１】
2008541568.tif 000033
【００８５】
として示され、サーバＳのインスタンスｊは、
【数３２】
2008541568.tif 000034
【００８６】
として示される。
【００８７】
２．一実施形態のための本発明の複雑性仮定
本発明は、いかなる複雑性仮定にも限定されるものではない。
【００８８】
決定部分群仮定
先ず、我々は、いくつかのＰＡＫＥ実施形態の安全性の根底となる複雑性仮定（「決定部分群問題」の仮定された困難性）について述べる。簡単に説明すると、
【数３３】
2008541568.tif 000035
【００８９】
および
【数３４】
2008541568.tif 000036
【００９０】
が、「適切な様式」（すなわち、ｉ∈｛０、１｝について、
【数３５】
2008541568.tif 000037
【００９１】
は、
【数３６】
2008541568.tif 000038
【００９２】
の素数の集合となるように）で生成された２つの合成数（ＲＳＡタイプ）の係数である場合、
【数３７】
2008541568.tif 000039
【００９３】
から値ｂを決定するのは困難である（ただし、ｂが｛０，１｝からランダムかつ均等に取り出される場合）。この仮定は、Ｃａｃｈｉｎ、Ｍｉｃａｌｉ、およびＳｔａｄｌｅｒ［１１］によるハイディング仮定
【数３８】
2008541568.tif 000040
【００９４】
のより強力なバージョンである。
【００９５】
この条件は以下のようにして形式化される。形式化されると、この仮定は、合成数係数に基づく群だけではなく、隠蔽されたスムースな位数の部分群を有するいかなる群にも適用することができる（整数ｎの素因数がｍ以下である場合、整数ｎはｍ−ｓｍｏｏｔｈであるという）。
【００９６】
κを安全性パラメータとし、ＰＰを素数の集合とし、ＰＰ’をＰＰの非空部分集合とする。
【数３９】
2008541568.tif 000041
【００９７】
が群をランダム生成する（ここで、当該群の位数は、
（１）
【数４０】
2008541568.tif 000042
【００９８】
の範囲内にあり、
（２）
【数４１】
2008541568.tif 000043
【００９９】
で割り切れ、かつ
（３）
【数４２】
2008541568.tif 000044
【０１００】
によって割り切れないものとする）場合、
Ｇｅｎ（１κ，ＰＰ，ＰＰ’）を、関数ｆ（）およびｆ’（）に関連付けられた群生成関数とする（すなわち、Ｇｅｎは、このような群上の超関数を誘導する）。それから、敵対者Ａ＝（Ａ１，Ａ２）について、Ａ１（１κ，ＰＰ）は、いくつかの状態と共に、２つの非空部分集合
【数４３】
2008541568.tif 000045
【０１０１】
および
【数４４】
2008541568.tif 000046
【０１０２】
を構築する。加えて、
【数４５】
2008541568.tif 000047
【０１０３】
および
【数４６】
2008541568.tif 000048
【０１０４】
とする。
【０１０５】
ここで、
【数４７】
2008541568.tif 000049
【０１０６】
は、
【数４８】
2008541568.tif 000050
【０１０７】
のｔで実行する全敵対者Ａに対して最大である（ここで、ｔはκの関数であるとする）。（Ｇｅｎ，ＰＰ）決定部分群仮定は、
【数４９】
2008541568.tif 000051
【０１０８】
が無視できることを示す。便宜上、我々は、
【数５０】
2008541568.tif 000052
【０１０９】
の代わりに表記
【数５１】
2008541568.tif 000053
【０１１０】
を用いる。なお、Ｇｅｎはセクション３で記載した通りであり、ＰＰは文脈から暗黙である。以下の議論において、ηはｆ(κ)を示し、ｐはｆ’(κ)を示すとする
（Ｇｅｎ、ＰＰ）決定部分群仮定は、Ｇｅｎ（１κ，ＰＰ，ＰＰ’）が、特定の様式で構築されたＲＳＡ係数を法とする乗法群を生成する場合に、真であると考えられる。ここで、ηは、所与の安全性パラメータκに対応するＲＳＡ係数のサイズであり（［３４］を参照）、ρ＜η／４である。
【０１１１】
例えば、Ｎを生成する以下の方法について考える。ここで、ρ＋２ｌ＜η／４が設定される。サーバは、形式２ＰπＲ１ｕ１＋１の素数Ｑ１を生成する。ここで、ｕ１は、小さな整数（｜ｕ1｜＝ｌ）であり、Ｒ１は、｜Ｑ１｜＝η／２を保証するのに適切なサイズの素数であり、ｐ∈ＰＰのサイズよりも大きいものとする。サーバは、形式２Ｒ２ｕ２＋１の素数Ｑ２を生成する。ここで、上記と同様に、ｕ２は小さな整数（｜ｕ２｜＝ｌ）であり、Ｒ２は、｜Ｑ２｜＝η／２を保証するのに適切なサイズの素数である（ｕ１＝ｕ２＝ｌを設定することができ、この場合、Ｑ２は、安全な素数（すなわち、素数Ｒ２について形式２Ｒ２＋１の素数）であり、上述のＱ１およびＱ２の生成は、実質的により高速である））。サーバは、Ｎ＝Ｑ１Ｑ２を設定する。しかしながら、任意のｐ∈ＰＰについて
【数５２】
2008541568.tif 000054
【０１１２】
の場合、サーバは、Ｎを拒否し、開始する。
【０１１３】
このＮの構造では、Ｐπがφ（Ｑ１）を除算するため、Ｐπがφ（Ｎ）を除算することが保証され、
【数５３】
2008541568.tif 000055
【０１１４】
は、Ｐπ（明らかに）、Ｒ１およびＲ２（なぜならば、Ｒ１およびＲ２は、任意のｐ∈ＰＰよりも大きい素数であるため）、Ｕ１およびＵ２（なぜならば、Ｕ１およびＵ２はどちらとも１ビット（すなわち、任意のｐ∈ＰＰよりも小さい））に対して素であるため、
【数５４】
2008541568.tif 000056
【０１１５】
が保証される。ρ＋２ｌ＜η／４を選択し、Ｑ１およびＱ２を選択することによって、少なくともη／４のサイズのφ（Ｎ）の要素を発見する明白な方法は無いことを保証する。特に、サイズｌのｕ１およびｕ２の場合、要素Ｐπｕ１ｕ２のサイズはη／４よりも小さい。最後に、ｐ∈ＰＰについては、いかなる
【数５５】
2008541568.tif 000057
【０１１６】
も拒否して、明らかな識別攻撃を回避する。なぜならば、
【数５６】
2008541568.tif 000058
【０１１７】
の場合は必ず
【数５７】
2008541568.tif 000059
【０１１８】
であるが、
【数５８】
2008541568.tif 000060
【０１１９】
の場合は必ずしもそうとは限らないためである。
【０１２０】
Ｃｏｐｐｅｒｓｍｉｔｈの方法に基づいた攻撃を回避するようにρ’＝ρ＋２ｌ＜η／４を生成する（［１４］、［１５］、［３８］を参照）制約を課すことにより、Ｑ１−１又はＱ１２−１の要素
【数５８−１】
2008541568.tif 000061
を知っている場合、Ｎを因数分解できるようにする。この仮定に関する１つの安全性の課題は、ρ’をいかにη／４よりも小さくするか（すなわち、ηがρ’よりも大きい場合に、Ｃｏｐｐｅｒｓｍｉｔｈの方法（これは、格子ベースの攻撃に基づく）の性能がどの程度劣化するか）である。
【数５８−２】
2008541568.tif 000062
の場合にＣｏｐｐｅｒｓｍｉｔｈの方法は（多項式時間において）良好に機能するため、アルゴリズムの性能が徐々にしか低下しない（例えば、
【数５８−３】
2008541568.tif 000063
の場合、恐らくは格子節減の非効率に起因して、アルゴリズムが（多項式時間ではないときに）若干超多項式のみになる）ことを期待することができる。しかしながら、［２２］で指摘されている通り、これは正しくない。すなわち、η／ρ’が４よりも大きい場合、Ｃｏｐｐｅｒｓｍｉｔｈの方法において用いられる目標ベクトル（すなわち、係数の因数分解を支援するもの）は、格子内の最短ベクトルさえでもない。よって、完璧な格子節減アルゴリズム自身でさえも、攻撃を機能させることはできない。これらの考えにより、ρ’＜η／４である限り、そして（ＰＰ’を用いて）サイズη／４以上の部分群の存在を容易に推測する方法はない。上述したように、ＲＳＡ係数を用いて決定部分群問題を安全にインスタンス化することができるという信頼が得られる。
【０１２１】
この決定部分群仮定においてさらなる信頼を得るために、一般的攻撃に対するその脆弱性を考えることができる。一般的攻撃は、従来、未知の位数の群において行われると考えられてきた［１８］。［２２］のモデルでは、決定部分群仮定も考えられている。
【０１２２】
これらの文献の概要によれば、（それぞれＰＰ０、ＰＰ１に基づく）２つの群集合と関連付けられた２つの超関数として、各々は、均等に分布した大きな素数によって割り切れる位数を有する群Ｇを出力しがちになるため、決定部分群問題は、一般的攻撃に対して困難になる。換言すれば、一般的攻撃に対する決定部分群問題の安全性は、｜Ｇ：Ｈ｜の超関数に依存する度合いよりも、Ｇ内に隠蔽された部分群の位数Ｈに依存する。
【０１２３】
３．本発明のパスワード認証型鍵交換スキームの一実施形態
パラメータ
我々は、Π、ｆΠ、αおよびＰＰが本発明のスキームの公開的に利用可能な「パラメータ」であると見なす。このスキームでは、２つの暗号ハッシュ関数Ｈ０およびＨ１も用いる。これらの暗号ハッシュ関数Ｈ０およびＨ１は、独立ランダムオラクルとして安全性証明においてモデル化される。このスキームでは、クライアントがクライアントのパスワードがサーバにとって既知であることを確認したいと望む場合、さらなる暗号ハッシュ関数Ｈ２を用いることもできる。
【０１２４】
プロトコル
図５は、プロトコルを与える。ここで、より詳細について説明する。
【０１２５】
クライアントＣおよびサーバＳは、それぞれ、各ストレージにおいて、クライアント側の素数集合ＰＰ（２１０Ｃ）と、サーバ側の素数集合ＰＰ（２１０Ｓ）とを保存する。クライアントは、５１０に示すように、上述のパスワードπとサーバ識別情報Ｓとを入力として受信する。サーバは、５１４に示すように、クライアント側のレコードπｓ［Ｃ］を保存する。このレコードは、パスワードπおよび以下に示す他のいくつかのデータを含む。
【０１２６】
サーバ初期化
セクション２に記載の方法に従って、サーバは、素数集合θ（ｓπ）と、対応するファイ関数値φ（Ｎ）と、疑似生成元ｘ∈ＺＮ＊とにより、係数Ｎを生成する。サーバは、これらの値をレコード５１４内に保存することにより、同一クライアントとの後続セッションにおいてこれらの値を再利用できるようにする。
【０１２７】
注目すべきは、セクション２のようなＮの構造は、（全ての素数ｐｉ，ｊが別個であると仮定する）疑似生成元の存在を保証する。実際には、φ（Ｎ）＝φ（Ｑ１）φ（Ｑ２）＝４ＰπＲ１ｕ１Ｒ２ｕ２である。Ｐπは４Ｒ１ｕ１Ｒ２ｕ２に対して素であるため、Ｐπの各素因数は、第１の累乗内のφ（Ｎ）の因数分解によって生じる。従って、ＺＮ＊は、位数Ｐπの要素ｘを含む。φ（Ｎ）はＰπに対して素であるため、
【数５９】
2008541568.tif 000064
【０１２８】
は、Ｐに対して素であり、このｘについて方程式（１）が成立する。
【０１２９】
疑似生成元は、位数ＰπのＺＮ＊の要素ｘとして選択することができ、以下のようにして選択することができる。ＺＮ＊の要素ｇをランダム選択し、
【数６０】
2008541568.tif 000065
【０１３０】
を設定する。明らかに、
【数６１】
2008541568.tif 000066
【０１３１】
である。Ｐπの全ての素因数ｐについて、
【数６２】
2008541568.tif 000067
【０１３２】
であることを確認する。この条件が真である場合、ｘが疑似生成元となる。そうでない場合、別のランダムｇを選択し、手順を反復する。
【０１３３】
クライアントの第１のアクション
セッションを開始する際、クライアントは、ランダムノンスＲｃ∈｛０，１｝κを生成し（５１８）、その識別情報Ｃおよびノンス値をサーバに送信する（５２０）。注目すべきは、これらのノンス値および範囲、ノンス値の使用、および多くの他の詳細は、例示的なものであり、非限定的なものであることである。
【０１３４】
サーバの第１のアクション
サーバは、ランダムノンスＲｓ∈｛０，１｝κを生成し（５２２）、Ｎ、ｘおよびノンス値をクライアントに送信する（５２４）。［２２］では、決定部分群問題が困難であり、問題インスタンスが疑似生成元ｘも含む場合、この決定部分群問題は困難であり続けることが記載されている。よって、Ｎおよびｘを送信したとしても、パスワードπの決定を容易にする情報は明らかにされることがないと（非形式的に）言える。
【０１３５】
（以下に示す安全性分析のため、セッションＩＤ
【数６３】
2008541568.tif 000068
【０１３６】
を定義することができ、Ｃのための相手ＩＤをｐｉｄＣ＝ＳおよびＳのための相手ＩＤをｐｉｄＳ＝Ｃと定義することができる。）
クライアントの第２のアクション
クライアントは、以下のようにして、（位数Ｐπの部分群内の）解ａにより、離散対数問題インスタンスｙを構築する。
【０１３７】
ステップ５２８：範囲［０，Ｎ・Ｐ・２κ］において、ランダム値ｅを生成する。この範囲は必要に応じて使用すればよく、他の範囲を用いてもよい（例えば、Ｐπよりも大きな他の範囲）。
【０１３８】
ステップ５３２：ａ←ｅ  ｍｏｄ  Ｐπを計算する（よって、この値ａは、ｅ  ｍｏｄ  Ｐπと等しい最小の非負整数である）。
【０１３９】
ステップ５３４：ｙ←ｘｅ  ｍｏｄ  Ｎを計算する。
【０１４０】
よって、ａ＝ＤＬｘｙ  ｍｏｄ  Ｐπとなる。
【０１４１】
クライアントはまた、解ｂにより、（群ＺＮ＊内の）ルートエクストラクション問題インスタンスｚを以下のように構築する。
【０１４２】
ステップ５３８：ＺＮ＊のランダム要素ｂ’を生成する。
【０１４３】
ステップ５４０：ｂ←（ｂ’）Ｐπ  ｍｏｄ  Ｎを計算する。
【０１４４】
ステップ５４２：ｚ←（ｂ’）Ｐ  ｍｏｄ  Ｎを計算する。
【０１４５】
ステップ５４４において、クライアントは、確認値ν１＝Ｈ１（<Ｓ，ｔｒａｎｓｃｒｉｐｔ，π，ａ，ｂ>）を計算する。ここで、ｔｒａｎｓｃｒｉｐｔは、クライアント／サーバ間で送信されるメッセージの転写又は当該転写に基づくものである。例えば、ｔｒａｎｓｃｒｉｐｔは、文字列<Ｓ，Ｃ，ＲＣ，ＲＳ，Ｎ，ｘ>であり得る。よって、クライアントは、明示的にπの知識を証明する（一方、サーバは、既に、その係数Ｎ内で暗黙のパスワード推測を行っている）。５４８において、クライアントは、ν１、ｙおよびｚをサーバに送信する。
【０１４６】
サーバの第２のアクション
サーバは、問題ｙおよびｘを解いて、解ａおよびｂを得る。より具体的には、離散対数問題に対して、以下を行う。
【０１４７】
ステップ５５０：
【数６４】
2008541568.tif 000069
【０１４８】
を計算する。
【０１４９】
ステップ５５４：
【数６５】
2008541568.tif 000070
【０１５０】
を計算する。
【０１５１】
ステップ５５８：
【数６６】
2008541568.tif 000071
【０１５２】
を計算する。
【０１５３】
一実施形態では、離散対数を効率的に計算することができる（５５８）。なぜならば、この離散対数は、位数ＰπのＺＮ＊内の（スムースな）巡回部分群<ｘ’>内で解かれるからである。なお、ｘはＺＮ＊内の疑似生成元であるため、ｘ’は位数Ｐπを有する（式（１）参照）一実施形態において、この部分群内の離散対数の計算は、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズム（［４８］および下記付録参照）を用いて容易に行われる。なぜならば、Ｐπの素因子は全て小さいからである（例えば、ｌ＋１ビット）。ここで、数字ｌを極めて小さい（例えば、１０）とする（ｌの選択方法については、セクション３を参照のこと）。
【０１５４】
５６０において、ルートエクストラクション（開方）は、サーバによる以下の計算で行われる。
【数６７】
2008541568.tif 000072
【０１５５】
一実施形態において、サーバは実際にオイラーの関数φ（Ｎ）を知っているため、開方を効率的に行うことができる。特に、値
【数６８】
2008541568.tif 000073
【０１５６】
を拡張ユークリッドアルゴリズムを用いて計算することができる。これは、
【数６９】
2008541568.tif 000074
【０１５７】
であるからである。
【０１５８】
５７０において、サーバは、クライアントから受信した値ν１がＨ１（<Ｓ，ｔｒａｎｓｃｒｉｐｔ，π，ａ，ｂ>）に等しいか否かを確認する。等しくない場合、サーバは処理を中止する。
【０１５９】
サーバは、当該サーバがパスワードπを知っているという付加的確認をクライアントに提供してもよい。例えば、サーバは、値ν２＝Ｈ２（<Ｓ，ｔｒａｎｓｃｒｉｐｔ，π，ａ，ｂ>）を計算し（５７４）、サーバは、この値をクライアントに送信してもよい（５７８）。５８０において、クライアントは、値ν２がＨ２（<Ｓ，ｔｒａｎｓｃｒｉｐｔ，π，ａ，ｂ>）に等しいか否かを確認する。等しくない場合、クライアントは処理を中止する。
【０１６０】
一実施形態では、付加的確認（５７４、５７８、５８０）は省略される。あるいは、パスワード知識に関するサーバのテストを重要視する場合（クライアントを信頼し、サーバを信頼しない場合）、ステップ５７０は省略されてもよく、クライアントは、ステップ５４８において値ν１をサーバに提供しなくてよい。
【０１６１】
ジョイントセッション鍵
ジョイントセッション鍵は、例えば、ｓｋ＝Ｈ０（<Ｓ，ｔｒａｎｓｃｒｉｐｔ，π，ａ，ｂ>）であり、５８２におけるクライアントと５８６におけるサーバとによって計算される。一実施形態において、セッション鍵は、ステップ５４４および５７４の前に計算され、値ν１およびν２は、鍵の関数（例えば、それぞれハッシュ関数Ｈ１（ｓｋ）、Ｈ２（ｓｋ））として計算される。
【０１６２】
直観的に、正当なパスワードに対応する素数を用いてＮが構築される場合（すなわち、θ（ｓπ）＝ＰＰＮ）、（ａ，ｂ）を（ｙ，ｚ）から計算することができる（これは、以下の「正当性」のセクションで説明される）。しかしながら、Ｎが「正当ではない」素数の集合で構築される場合、「正当ではない」全ての素数について、クライアントが（ｙ，ｚ）を計算するのにに用いることが可能な値（ａ，ｂ）が、（素数に等しい）倍数因子により増加する。その後、セクション５に示すように、クライアントがＰＰＮに「最も近い」θ（ｓπ）を持つ（せいぜい）１つのパスワードπを用いない限り、エラー訂正コードのために、所与の（ｙ，ｚ）に対する（ａ，ｂ）の可能性の数が膨大になる。
【０１６３】
正確性
サーバが回復する（ａ，ｂ）値は、クライアントが生成した各値と全く同一であることを示せば十分である。ｂについては、
【数７０】
2008541568.tif 000075
【０１６４】
であるため、
【数７１】
2008541568.tif 000076
【０１６５】
が存在し、ＺＮにおいて唯一である。さらに、以下が得られる。
【数７２】
2008541568.tif 000077
【０１６６】
（ここで、ｂおよびｂ’は、ステップ５３８および５４０においてクライアントによって生成される値である）。
【０１６７】
値ａが同一であるのを確認するために、先ず、特定の整数ｍについて、ｅをａ＋ｍＰπとする。ここで、ａは、クライアントの値である（５３２）。
【０１６８】
ここで、以下が得られる。
【数７３】
2008541568.tif 000078
【０１６９】
従って、クライアントの値ａは、値ＤＬｘ’（ｙ’）のうちの１つである。ｘは疑似生成元であり、ＺＮ＊の要素であるため、ｘ’の位数はＰπであり、従って、ＤＬｘ’（ｙ’）は、Ｐπを法とする唯一のものである。従って、サーバの値ａおよびクライアントの値ａは、いずれも｛０，…，Ｐπ｝内であるため（５３２、５３８）、これらのα値は一致する（ｘ’およびｙ’はいずれも、Ｚ＊ＮのＰπの位数部分群＜ｘ’＞である）。
【０１７０】
３．１．  エラー訂正コードのインスタンス作成
我々のスキームを効率的かつ安全にするために、エラー訂正コード、特に（ｎ，ｋ，ｄ）パラメータは、注意深く選択されなければならない（しかしながら、本発明は、安全かつ効率的なスキームに限定されない点に留意されたい）。ｎは符号語のビット数であり、ｋは入力のビット数（すなわち、パスワード表示）であり、ｄは符号化の距離（２つの符号語間の最小のＨａｍｍｉｎｇ距離）であるとする。また、Ｚ＊Ｎの隠蔽されたスムースな部分群＜ｘ’＞内の全素数の長さは、少なくともｌ＋１でなければならないため、パラメータｌも重要である。
【０１７１】
柔軟性のためには、大きな辞書を処理可能にすべきであることから、ｋをできる限り大きくすることが望まれる（これに関しては、セクション３．２を参照）。少なくとも４桁の暗証番号の安全性を達成するためは、
【数７３−１】
2008541568.tif 000079
が必要である。
【０１７２】
効率のため、ｎ｛ｌ＋１｝をできる限り小さくすることが望まれる（スムースな部分群のために用いられるｎ個の素数は全てｌ＋１ビットであり、そうではない場合、この値はより大きくなるとする）。これは、セクション２で説明したように係数のサイズに影響を与えるからである。特に、公知のいかなる攻撃をも回避するため、｜Ｎ｜は、少なくともこの値の４倍に加えて、十分なマージンを必要とする。あるいは、異なる係数間でｎビットの符号語を（その対応する素数に従って）分割し、各係数のサイズがｎ’（ｌ＋１）の少なくとも４倍であるとして、複数の係数を利用するために、プロトコルを一般化する。ここで、ｎ’は、当該係数に割り当てられたビット数である（モジュール方程式は、係数のサイズにおいて三次方程式となるのに時間を必要とするため、この代替例がより効率的となる場合もある）。
【０１７３】
クライアントとして振舞う敵対者に対する安全性のため、敵対者が決定部分群仮定を破ることができないことを保証する必要があるため、上述したように、
【数７３−２】
2008541568.tif 000080
となる（κ＝８０の場合、
【数７３−３】
2008541568.tif 000081
（［３４］を参照））。
【０１７４】
サーバとして振舞う敵対者に対する安全性のため、敵対者が２つの候補パスワードの正当性／非正当性を同時に試すことを可能にする係数を当該敵対者が構築できないことを保証する必要がある。以下のようにして、安全性を分析する。
【０１７５】
本発明の構造により、符号語の各ビットは、１つの（ｌ＋１）ビットの素数の包含と、異なる（ｌ＋１）ビットの素数の排他とに対応する。符号語間の距離はｄであるため、これは、２つの符号語が２ｄ個の素数の包含／排他において異なることを示す。これは、敵対者によって選択された係数が、せいぜい１つの符号語のｄ個の包含／排他よりも少ないことを意味する。安全性の証明から分かるように、敵対者がパスワードの正当性／非正当性を試したい場合、当該敵対者は、誤って推測された包含または排他について、少なくともｂビットを推測しなければならない。よって、２つのパスワードを試すためには、１つのパスワードは少なくともｄ個の包含／排他であり、敵対者は、ｄｌビットを推測しなければならない。κビットの安全性を達成するため、
【数７３−４】
2008541568.tif 000082
が必要となる。
【０１７６】
上記をまとめると、以下を満たす（ｎ，ｋ，ｄ）−ＥＣＣおよび値ｌを得る必要がある。
【数７３−５】
2008541568.tif 000083
下記の表１では、既知のコードに関するパラメータ（すべて、パリティビットが付加されたＢＣＨコードである）と、本発明の第１の要件を満足するための対応するｌ値と、κ＝８０レベルにおける安全性のために必要な係数のサイズとが得られる。係数のサイズの後の（）の数字は、複数の係数を示す。係数のサイズは、２５６の倍数に丸められている。他のパラメータも検討したが、他のパラメータでの性能は悪化した。
【表１】
2008541568.tif 000084
【０１７７】
暗証番号の安全性のため、ｌ＝１０および｜Ｎ｜＝１５３６のときの（３，１６，８）ＥＣＣが、良い選択であると思われる。任意の辞書に関する安全性（セクション３．２で説明）のため、ｌ＝１０および２つの１５３６ビット係数のときの（６４，４５，８）ＥＣＣが、良い選択であると思われる。
【０１７８】
３．２．任意の辞書
ここで、パスワードをビット文字列にマッピングする関数ｆΠについて考える。一対一のマッピングがある場合、オンライン辞書攻撃に対する完全安全性を得ることができる。すなわち、ｑ個のオンライン認証試行および辞書Ｄの場合、成功する確率は、せいぜいｑ/｜Ｄ｜よりも大きく、無視できる程度である。例えば、４桁の暗証番号を用いる場合、ｆΠは、これらの数字を、０〜９９９９の数値に対応する長さ１４ビットの文字列にマッピングするにすぎない。一方、任意の長さの文字列を含む辞書が与えられた場合、自明なマッピングになる可能性がある。そこで、代わりに、文字列をｋビットにハッシュするハッシュ関数を利用する。これらのｋビットをエラー訂正コードに対する入力として用いてもよい。
【０１７９】
不幸なことに、衝突耐性ハッシュ関数は、大きな出力サイズを必要とする。例えば、ＳＨＡ−１は１６０ビットを出力する。効率的なコードのために必要なビット数（例えば、ｋ＝４５）に切り捨てられた、或るバージョンのＳＨＡ−１は、必ずしも衝突耐性でない。よって、本発明の安全性が低減されるかもしれない。ここで、合理的に高レベルの安全性を維持していることを示すために、いくつかの分析を行う。基本的に、ビット安全性は、ｋの最小の位数と、望む限り有効である辞書サイズの対数とによる（ただし、辞書サイズが２ｋよりもずっと大きい場合、厳しい解釈によれば、安全なＰＡＫＥプロトコルを有さないとも言える。しかしながら、パスワードスペースをＤからｋビットの文字列の集合に本質的に変更することを考えた場合、新しいパスワードスペースにおいて、安全なＰＡＫＥプロトコルを有すると言うことができる。もちろん、これは、大きなｋ（例えばｋ＞３０）のみにおいて推奨される。）
先ず、Ｃｈｅｒｎｏｆｆ限界を念頭におく。成功確率ｐの実験がｎ個ある場合、成功の回数を示すランダム変数Ｘは以下のように表される。
【数７４】
2008541568.tif 000085
【０１８０】
本発明のシナリオでは、辞書サイズを多くとも２ａ、ｋビット出力のランダム関数ｆΠ、実験（ｉ、π）がｆΠ（π）＝ｉであるか否かを想定する。これは、本質的にボールとビンのモデルでありであり、パスワードがボールを表し、２ｋ出力がビンを示す。このとき、ｎ＝２ａおよびｐ＝２−ｋである。便宜上、γ＝ｃ２ｋ−ａ−１とし、これにより、１つのビンがｃ個よりも多いボールを持つ確率に限界を設ける。これにより、以下が得られる。
【数７５】
2008541568.tif 000086
【０１８１】
値２ｋＰｒ（Ｘ＞ｃ）により、いかなるビンもｃ個よりも多いｂａｌｌを持つ確率（すなわち、いかなる出力も、ｃ個よりも多いパスワードにマッピングされる確率）に限界を設けてもよい。この値は、多くともｃ２―αでなければならない。なぜならば、これは、多くともｃ個のパスワードが所与の出力にマッピングされることを想定すると、１つのｋビット出力が正しいパスワードに対応する確率となるからである。よって、以下が必要となる。
【数７６】
2008541568.tif 000087
【０１８２】
上記は、以下に節減することができる。
【数７７】
2008541568.tif 000088
【０１８３】
任意の辞書に用いることが可能な上記表の３つのＢＣＨコードは、ｋ＝３９、ｋ＝４５、またはｋ＝５１のいずれかである。一例としてｋ＝４５とし、辞書サイズを２３５（すなわち、ａ＝３５、またはおよそ３２０億）とする。この場合、出力単語が７個よりも多いパスワードにマッピングされる可能性がせいぜい７／２３５であることを確認するためには、
【数７７−１】
2008541568.tif 000089
でなければならず、この結果、およそ３２ビットの安全性が達成される。
【０１８４】
図６は、合理的な辞書サイズにわたる各値ｋについて、達成されるビット安全性を示す。辞書サイズのバイナリ対数は、横軸上にプロットされ、ビット安全性は、縦軸上にプロットされる。下側曲線は、３９ビットの出力サイズを示す。中間曲線は、４５ビットの出力サイズを示す。上側曲線は、５１ビットの出力サイズを示す。一般的に、ビット安全性は、ａの値がより小さくなると小さな定数によって低減されるが、ａがｋに近づくと、ビット安全性は安定し、最終的にはおよそｋ−ｌｏｇｅ（すなわち、およそｋ−１．４４）となる。
【０１８５】
４．実装
我々のプロトコルの効率を検査するため、単一マシン上において（よって、通信コストは無視する）クライアント側およびサーバ側双方のプロトコルを実行する実証版を実装した。この実装は、多倍精度計算のためのＧＮＵ  ＭＰライブラリを用いて、Ｃで記載されている。ＯｐｅｎＳＳＬライブラリは、暗号ハッシュ関数および暗号乱数生成のために用いられた。
【０１８６】
ｌ＝１０および１５３６ビットの係数について、（３２，１６，Ｓ）ＥＣＣを用いて、以下の結果が得られた。上述したように、これは、４桁の暗証番号の場合に適している。任意サイズの辞書を処理可能な２つの１５３６係数についての（６４，４５，８）ＥＣＣを用いた実験を行っていないが、クライアントおよびサーバ双方における計算コストが実質的に２倍になることが明らかである。性能増強のため、以下の最適化を用いた。
【０１８７】
・サーバは、Ｎの２つの素因数の知識と（ＲＳＡ復号化においてよく行われるような）中国人剰余定理とを用いて、合成数係数Ｎについて累乗法を行った。
【０１８８】
・スムースな部分群を、Ｎの要素のうちの１つだけの部分群として配置した結果、離散対数の計算に関連する全計算を、Ｎの代わりに当該１つの要素を法として行うことができた。
【０１８９】
・再帰アルゴリズムを、
【数７８】
2008541568.tif 000090
【０１９０】
を計算する大きなＤＬ問題から３２個の小さなＤＬ問題を決定するために用いた。これについては、以下で説明する。
【０１９１】
・ｂａｂｙ−ｓｔｅｐ／ｇｉａｎｔ−ｓｔｅｐアルゴリズムを離散対数の計算に用いた。
【０１９２】
我々は、各マシン上でプロトコル実行を２５回行い、計算時間を平均化した。
【表２】
2008541568.tif 000091
【０１９３】
クライアントにおける主な計算コストは、１５３６ビットよりも大きい指数の１５３６ビットの係数にわたる累乗法である。サーバにおける主な計算コストは、３２個のＤＬ問題を決定し、これらの問題を解くことによって、およそ均等に分割される。
【０１９４】
これらの性能数値は、３．２ＧＨｚで動作するＸｅｏｎプロセッサを有するサーバは、１秒間に４０回の認証試行を処理することができることを示す。明らかに、いかなる暗号プロトコルと同様に、サービス拒否（ＤｏＳ）攻撃を考える必要がある。幸運なことに、サーバは、第２のメッセージを受け取るまではいかなる暗号動作も行わなくてよい。そのため、スプーフィングされたＩＰアドレスによる攻撃の心配は少ない。しかしながら、真のＩＰアドレスからの攻撃は依然として発生し得るため、十分な保護（例えば、クライアント側のパズル［２０］）を構築して、これらの攻撃の効果を軽減すべきである。
【０１９５】
小さなＤＬ問題の計算のための再帰アルゴリズム
サーバは、２つの値ｘ’およびｙ’を計算し、ＤＬｘ’（ｙ’）  ｍｏｄ  Ｐπを計算することを望む。ここで、Ｐπは、ｎ（ｌ＋１）ビットの素数の積である（上述の場合では、ｎ＝３２およびｌ＝１０）。これを効率的に行うため、Ｐπを除算する各素数ｐｉについて、ｐｉを法とする離散対数を計算することができる。しかしながら、ｘ’の位数はＰπであるため、
【数７９】
2008541568.tif 000092
【０１９６】
を計算する必要がある（すなわち、Ｐｉを除く全ての素数の積により、ｘ’およびｙ’をそれぞれ増加することにより、ｘ’ｉおよびｙ’ｉを計算する）。これにより、ｘ’ｉの位数はＰｉであり、
【数８０】
2008541568.tif 000093
【０１９７】
ステップを用いた標準的方法（例えば、ｂａｂｙ−ｓｔｅｐ／ｇｉａｎｔ−ｓｔｅｐ）を用いて、
【数８１】
2008541568.tif 000094
【０１９８】
を計算することができる。
【０１９９】
よって、目的は、各ｉについてｘ’ｉおよびｙ’ｉを効率的に計算することである。この単純な方法は、サイズがおよそ（ｎ―１）／（ｌ＋１）の指数を有する底Ｎにわたって、ｎ個の累乗法を必要とする（または、本発明の場合、各指数がおよそ３１・１１＝３４１ビットを有する、およそ３２個の累乗法）。より高速の方法として、再帰アルゴリズムを用いてｘ’ｉおよびｙ’ｉの値を計算する方法がある。ここで、値ｘ’ｉに注目する。なお、値ｙ’ｉも同様である。素数の積を２つの積に分割し、第１の半数および第２の半数を得る。ｘ’を各積まで増加させ、これらをｘ’ｌｏｗおよびｘ’ｈｉｇｈとする。それから、ｘ’ｈｉｇｈから始まる値ｘ’ｉの第１の半数の計算問題と、ｘ’ｌｏｗから始まる値ｘ’ｉの第２の半数の計算問題とを再帰的に解く。ただし、各値ｘ’ｉは最終的には全てｐｊ（ｊ≠ｉ）まで増加されるｘ’となる。
【０２００】
５．安全性モデルおよび定理
我々の安全性モデルについて説明し、任意の所与のシステムパラメータκ、ｎ、ｄ、ｋおよびｌの安全性に関する正式な定理の記述を提供する。
【０２０１】
安全性モデル
安全性の証明のため、［２］のモデルを用いる（このモデルは、［４］および［５］に基づいて構築され、［３１］によっても用いられているが、簡潔にするため、明示的な認証の提供またはパーティの破損の問題については考えない）。このモデルは、２つのパーティ間の認証された鍵交換（ａｋｅ）の問題のために設計されている。なお、クライアントおよびサーバは、秘密を共有する。その目的は、プロトコルに従事するパーティが、当該プロトコルの終了後に、それぞれ、当該パーティ以外の誰にも知られていないセッション鍵を保持するようにすることである。
【０２０２】
以下において、公知である［２］のモデルを仮定する。
【０２０３】
プロトコル参加者
ＩＤをプリンシパルの非空集合とする。各原理は、クライアントまたはサーバのいずれかである。よって、
【数８２】
2008541568.tif 000095
【０２０４】
であり、ここで、ＣｌｉｅｎｔｓおよＳｅｒｖｅｒｓは有限でありかつ互いに素な非空集合である。各プリンシパルＵ∈ＩＤは、文字列によってラベル付けされ、当該文字列を示すためにＵを用いる。
【０２０５】
各クライアントＣ∈Ｃｌｉｅｎｔは、秘密パスワードπｃを有し、各サーバＳ∈Ｓｅｒｖｅｒは、
【数８３】
2008541568.tif 000096
【０２０６】
を有する。エントリπｓ［Ｃ］は、パスワードレコードである（ただし、πｓ［Ｃ］は、単なるπｃよりもより多くの情報を含み得る）。ここで、Ｐａｓｓｗｏｒｄｃを、クライアントＣ用のパスワードの選択対象となる（おそらくは小さな）集合とする。
【数８４】
2008541568.tif 000097
【０２０７】
とする（しかしながら、本発明の結果は、他のパスワード超関数にも容易に利用可能である）。クライアントおよびサーバは、入力テープおよび出力テープを有する確率的多項式時間アルゴリズムとしてモデル化される。
【０２０８】
プロトコルの実行
プロトコルＰは、環境からの入力に応じてプリンシパルがどのように動作するかを決定するアルゴリズムである。実世界において、各プリンシパルは、異なる相手と何度もＰを実行することができ、我々は、各プリンシパルの無限数のインスタンスを可能にすることにより、これをモデル化する。プリンシパルＵ∈ＩＤのインスタンスｉを
【数８５】
2008541568.tif 000098
【０２０９】
として示す。
【０２１０】
プロトコルの安全性を記述するため、環境（主にネットワーク）に対する完全な制御を有する敵対者Ａが存在し、よってプリンシパルのインスタンスに対する入力を提供すると仮定する。正式には、この敵対者は、区別されたクエリテープをもつ確率的アルゴリズムである。このテープに書かれたクエリは、Ｐに従って、プリンシパルによって応答され、許可されたクエリは、［２］において正式に定義され、以下において要約される。
【０２１１】
Ｓｅｎｄ（Ｕ，ｉ，Ｍ）：メッセージＭをインスタンス
【数８６】
2008541568.tif 000099
【０２１２】
に送信する。このインスタンスは、プロトコルが何を示すか、状態が更新されるか、計算の出力がＡに与えられるかを計算する。このクエリが
【数８７】
2008541568.tif 000100
【０２１３】
に受付または終了させる場合、これはＡにも示される（ただし、受付は、３種類の数（ｐｉｄ，ｓｉｄ，ｓｋ）を生成することを示し、終了は、受付とメッセージがこれ以上出力されないこととを示す。プロトコルがこれ以上のメッセージを送らないが終了はしないことを示すために、状態はＤＯＮＥに設定され、条件はＦＡＬＳＥに設定される）。クライアントＣおよびサーバＳ間のセッションを開始するため、敵対者は、サーバの名称Ｓを含むメッセージをＣの未使用のインスタンスに送信する。
【０２１４】
Ｅｘｅｃｕｔｅ（Ｃ，ｉ，Ｓ，ｊ）：
【数８８】
2008541568.tif 000101
【０２１５】
と、
【数８９】
2008541568.tif 000102
【０２１６】
との間の完成するまで、Ｐを実行し、この実行の転写を出力する。このクエリは、Ｐの実行を単に盗聴した受動的敵対者の直観を取得する。
【０２１７】
Ｒｅｖｅａｌ（Ｕ，ｉ）：
【数９０】
2008541568.tif 000103
【０２１８】
によって保持されるセッション鍵を出力する。
【０２１９】
テスト（Ｕ，ｉ）：
【数９１】
2008541568.tif 000104
【０２２０】
にビットｂを反転させる。ｂ＝１である場合、セッション鍵
【数９２】
2008541568.tif 000105
【０２２１】
が出力され、ｂ＝１ではない場合、文字列が、セッション鍵のスペースから均一に引き出され、出力される。テストクエリは、Ｐの実行中、いつでも問い合わせられるが、一度しか問い合わせられない。
【０２２２】
相手認証
クライアントまたはサーバのインスタンスは、相手ｉｄであるｐｉｄ、セッションｉｄであるｓｉｄ、およびセッション鍵ｓｋを保持する。その後、インスタンス
【数９３】
2008541568.tif 000106
【０２２３】
および
【数９４】
2008541568.tif 000107
【０２２４】
は、双方が受け付ける場合、相手として認証され、それぞれ、（ｐｉｄ，ｓｉｄ，ｓｋ）および（ｐｉｄ，ｓｉｄ，ｓｋ）を保持する。ここで、ｐｉｄ＝Ｓ、ｐｉｄ＝Ｃ、ｓｉｄ＝ｓｉｄ、およびｓｋ＝ｓｋであり、ｓｉｄに等しいセッションｉｄによって受け付けられる他のインスタンスは無い。
【０２２５】
フレッシュ性
（１）Ｒｅｖｅａｌ（Ｕ，ｉ）クエリが発生するかまたは（２）Ｒｅｖｅａｌ（Ｕ’，ｊ）クエリが発生しない限り、インスタンス
【数９５】
2008541568.tif 000108
【０２２６】
はフレッシュである。ここで、
【数９６】
2008541568.tif 000109
【０２２７】
は、
【数９７】
2008541568.tif 000110
【０２２８】
の相手である。
【０２２９】
敵対者の利点
ここで、認証された鍵交換（ａｋｅ）のプロトコルＰに対する敵対者の利点を正式に定義する。
【数９８】
2008541568.tif 000111
【０２３０】
を、終了したあるフレッシュなインスタンス
【数９９】
2008541568.tif 000112
【０２３１】
に向けられた単一のテストクエリをＡが作成するイベントであるとし、最終的にビットｂ’を出力する。ここで、テストクエリにおいて選択されたビットｂについてｂ’＝ｂである。Ｐを攻撃するＡの利点を以下に定義する。
【数１００】
2008541568.tif 000113
【０２３２】
以下の事実は、容易に検証される。
【０２３３】
事実１
【数１０１】
2008541568.tif 000114
【０２３４】
安全性定理
モデルを提供してきたが、我々の安全性定理について詳細に説明する。節減における詳細な安全性の損失を定量化するため、定理の記述は、３つの数量ｔｐｒｏｔ，ｔｓａｍｐ，ｔｅｘｐについて言及する。これらは、それぞれ、単一プロトコル実行に要される時間、プロトコル実行中に群Ｇのランダム要素をサンプリングするための時間、および当該群において累乗法を行うための時間である。
【０２３５】
定理１
Ｐを、図５（ステップ５１８〜５７０）において説明された、パスワード辞書Ｄと｛０，１｝ｋに一対一マッピングしているｆΠとを用いたプロトコルとする。時間ｔで実行する敵対者Ａを固定し、ｎｓｅ，ｎｅｘ，ｎｒｅを、Ｓｅｎｄ、Ｅｘｅｃｕｔｅ、Ｒｅｖｅａｌそれぞれのクエリとし、ｎｒｏを、ランダムオラクルに対するクエリとする。この場合、
【数１０２】
2008541568.tif 000115
【０２３６】
について、以下が得られる。
【数１０３】
2008541568.tif 000116
【０２３７】
ｆΠが｛０、１｝ｋに対するランダムマッピングである場合、初項は
【数１０４】
2008541568.tif 000117
【０２３８】
となり、ここで、δは、セクション３．２において計算されたビット安全性であり、追加物２−δは、２−δよりも大きいパスワードが所与のｋビットの文字列にマッピングされる確率から来ている。
【０２３９】
証明（スケッチ）
先ず、Ｐ（Ｐ０＝Ｐ）に関連する一連のプロトコルＰ０、Ｐ１、…、Ｐ６を導入する。Ｐ６において、Ａは、直接的分析を許す単純なオンライン推測攻撃に低減される。
【０２４０】
Ｐ０：オリジナルプロトコルＰ
Ｐ１：正当なパーティが、プロトコル実行において以前に見られた値ＲｃまたはＲｓをランダムに選択する場合、このプロトコルは停止し、敵対者は失敗する。
【０２４１】
Ｐ２：プロトコルは、任意のランダムオラクルクエリを生成せずに、ＳｅｎｄクエリおよびＥｘｅｃｕｔｅクエリを応答する。敵対者による後続ランダムオラクルクエリは、できる限りバックパッチされ、これにより、ＳｅｎｄクエリおよびＥｘｅｃｕｔｅクエリに対するレスポンスと一致する。なお、サーバは、敵対者が正しいランダムオラクル
【数１０５】
2008541568.tif 000118
【０２４２】
クエリを生成していない、値ｖを受信する場合、非マッチングセッションで処理を終了する。また、敵対者がパーティのセッション鍵または検証値を決定するための正しいランダムオラクルクエリを作成する場合、シミュレーションは停止し、敵対者が成功する（これは、ランダムオラクルを伴う証明のための標準的技術である）。
【０２４３】
Ｐ３：サーバインスタンスに対して「ほとんど正しい」パスワード推測が行われた場合、プロトコルは停止し、敵対者は自動的に成功する。（なお、パスワード推測がほとんど正しいかは、サーバインスタンスに送信された検証値ｖによって決定され、ここで、ｖは、正しいパスワードの場合に、値ａおよびｂに関係なく、
【数１０６】
2008541568.tif 000119
【０２４４】
クエリの出力に等しい）
Ｐ４：サーバインスタンスは、各クライアントについて係数Ｎを完成させるためにダミーパスワードを用いる。
【０２４５】
Ｐ５：
【数１０７】
2008541568.tif 000120
【０２４６】
クエリが生成される場合、Ｅｘｅｃｕｔｅクエリに対する一貫性については確認されない。すなわち、シミュレーションを停止する代わりに、ランダムレスポンスがクエリに返送される。
【０２４７】
Ｐ６：敵対者が同一クライアントインスタンスに対して２つのパスワード推測を行う場合、プロトコルは停止し、敵対者は失敗する。
【０２４８】
１から６までの各ｉについて、プロトコルＰｉ-1を攻撃しているＡの利点はプロトコルＰｉを攻撃しているＡの利点よりもせいぜい無視できるくらいのレベルでしか大きくないことを証明する必要がある。第１の３つの「遷移」に関する証明は比較的直接的である。Ｐ３からＰ４への遷移については、決定部分群問題の困難性を用いる。Ｐ４からＰ５への遷移およびＰ５からＰ６への遷移については、以下のアサーションを用いる。
【０２４９】
アサーション１：係数Ｎおよびｘ∈ＺＮ＊をとる。パスワードπをとる。ＰＰ’を、ＰＮまたはθ（ｓπ）双方ではなくいずれかの中にある素数の集合とし、ｄ＝｜ＰＰ’｜とする。このとき、クライアントによって生成されるいかなる（ｙ，ｚ）についても、（ａ，ｂ）が（ｙ，ｚ）によって生成される確率はせいぜい（１＋２−κ）２−ｄｌである。
【０２５０】
簡単に言えば、このアサーションは、ＰＰＮとθ（ｓπ）との間の集合差が高濃度となるようにサーバが係数Ｎを選択する場合、サーバは（ｙ，ｚ）から「正しい」（ａ，ｂ）の値を実行可能に取り出すことはできないことを示す。なぜなら、膨大な数（およそ２ｄｌ）の対（ａ，ｂ）が全て同一（ｙ，ｚ）に対応するためである。
【０２５１】
証明
（Ｎ，ｘ，π）が与えられた場合、ａの値は、ｂおよびｚの値とは別であり、ｂの値は、ａおよびｙの値とは別である。よって、Ｐｒ[(ａ，ｂ)｜(ｙ，ｚ)]＝Ｐｒ[ａ｜ｙ]Ｐｒ[ｂ｜ｚ]が成立する。
【０２５２】
先ず、Ｐｒ[ａ｜ｙ]について限界を設ける。ＰＰπ−Ｎ＝θ（ｓπ）＼ＰＰＮ（すなわち、ＰＰＮではなく、θ（ｓπ）内の素数の集合）とし、Ｐπ―ＮをＰＰπ―Ｎ内の素数の積とする。直観的に、φ（Ｎ）はＰπ―Ｎに対して素であるため、ｅが十分に大きな間隔から取られる場合、ｙの値は、ｅ  ｍｏｄ  Ｐπ―Ｎの値を実際には拘束しない（ただし、ｅ  ｍｏｄ  φ（Ｎ）の取り得る値を拘束する）。したがって、ａ←ｅ  ｍｏｄ  Ｐπは、本質的に均等な確率を有するＰπ―Ｎ個の異なる値を仮定することができる。より正式には、｜<ｘ>｜を、Ｎを法とするｘの位数とする。また、以下とする。
【数１０８】
2008541568.tif 000121
【０２５３】
この場合、
【数１０９】
2008541568.tif 000122
【０２５４】
が得られる。Ｅｙの値は、差｜<ｘ>｜の等差数列を形成し、｜<ｘ>｜はＰπ―Ｎに対して素であるため、Ｅｙサイクル（期間はＰπ―Ｎ）の値は、Ｐπ―Ｎを法とする全ての留数を通じて繰り返される。そして、
【数１１０】
2008541568.tif 000123
【０２５５】
が得られる。ここで、最終等式は、以下に従う。
【数１１１】
2008541568.tif 000124
【０２５６】
よって、
【数１１２】
2008541568.tif 000125
【０２５７】
が得られる。
【０２５８】
次に、Ｐｒ[ｂ｜ｚ]に限界を設ける。
【数１１３】
2008541568.tif 000126
【０２５９】
する。、集合
【数１１４】
2008541568.tif 000127
【０２６０】
の濃度が最大化されるように、ｂ０∈ＺＮ＊とする。なお、
【数１１５】
2008541568.tif 000128
【０２６１】
となる。
【０２６２】
ｕ∈ＺＮ＊を、Ｎを法とするプリミティブなＰＮ番目の原始根とする。
【数１１６】
2008541568.tif 000129
【０２６３】
とし（すなわち、θ（ｓπ）ではなくＰＰＮ内の素数の集合）、ＰＮ―πをＰＰＮ―π内の素数の積とする。このとき、ｔ∈[０，ＰＮ―π−１]について、値
【数１１７】
2008541568.tif 000130
【０２６４】
は区別できるものであり、よって、集合
【数１１８】
2008541568.tif 000131
【０２６５】
は互いに素である。さらに、
【数１１９】
2008541568.tif 000132
【０２６６】
であるため、
【数１２０】
2008541568.tif 000133
【０２６７】
である。よって、
【数１２１】
2008541568.tif 000134
【０２６８】
となる。
【０２６９】
最後に、ＰＰ内の素数は２ｌ以上であるため、
【数１２２】
2008541568.tif 000135
【０２７０】
が得られる。
【０２７１】
最後に、Ｐ６において、敵対者が、クライアントおよびサーバインスタンスの各々に対して、せいぜい１つのパスワード推測しか行うことができないことが容易にわかる。これにより、敵対者が成功する確率に
【数１２３】
2008541568.tif 000136
【０２７２】
が追加される。敵対者がパスワードを推測しない場合、敵対者のビューは各フレッシュなセッション鍵とは別であることは明らかであるため、テストクエリからの成功確率は正確に１／２である。
【０２７３】
従って、
【数１２４】
2008541568.tif 000137
【０２７４】
が得られる。この定理は、各プロトコルＰｉ−１と後継のプロトコルＰｉとの間に、敵対者によって得られた利点において追加することにより、続いて得られる。
【０２７５】
結論として、パスワード認証型鍵交換プロトコルを提示したが、その一実施形態は、（決定部分群仮定に基づいた）ランダムオラクルモデルにおいてオフライン辞書攻撃に対しておそらく安全である点に留意されたい。本発明のアプローチでは、パスワードを用いて、「部分的に」スムースな位数の乗法群を構築する（すなわち、その素因数の「ほとんど」の位数がスムースなパラメータ以下である）。これは、パスワード認証型鍵交換プロトコルの設計において、新規なパラダイムのように思える（典型的なパスワード認証型鍵交換プロトコルでは、パスワードを用いて、標準的鍵交換プロトコルのメッセージを暗号化し、または、パスワードを用いて、標準的鍵交換プロトコルのパラメータを選択する）。本発明のスキームは、最近のプライベート情報回復スキーム［２２］に対していくつかの類似点を有する。Ｃｒａｉｇ  Ｇｅｎｔｒｙ、Ｐｈｉｌｉｐ  Ｍａｃｋｅｎｚｉｅ、Ｚｕｌｆｉｋａｒ  Ｒａｍｚａｎによる「Ｐａｓｓｗｏｒｄ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  Ｕｓｉｎｇ  Ｈｉｄｄｅｎ  Ｓｍｏｏｔｈ  Ｓｕｂｇｒｏｕｐｓｓ」（ＡＣＭ  ＣＣＳ  ２００５、２００５）も参照されたい。本明細書中、同文献を参考のため援用する。
【０２７６】
本発明は、上記の実施形態に限定されない。例えば、一実施形態において、クライアントおよびサーバは互いに認証するが、共有セッション鍵を生成しない（プレーンテキスト通信のみが要求される場合）。例えば、データベース２１０において、数字の対を数字の組に交換することができる。ＯＴクエリ２３０（図２）は、各組から１つの数字を選択てもよい。本発明は、エラー訂正コードの使用や特定の長さの数字ｐｉ，ｊ、または同一の長さを有する数字に限定されない。関数Ｈ０、Ｈ１、Ｈ２は、暗号ハッシュ関数である必要はない。本発明は、任意の複雑性仮定に限定されない。値πは、完全なパスワードではなく、パスワードの一部であってもよい。本発明は、ノンス値、転写値（図５）、または他の詳細の使用に限定されない。本発明は、整数または留数のいかなる表示にも限定されない。特に、ＺＮの要素は、０〜Ｎ−１の範囲の整数、または、他の範囲のその合同の整数によって示れてもよい。例えば、ステップ５４２において、ｚをｚ＋Ｎと交換することができる。同様に、ステップ５３２およびステップ５５８において、値ａをａ−Ｐπと交換することができる。ステップ５４８（図５）における値（ｙ，ｚ）は、（２ｙ，２ｚ）（すなわち、二倍）としてあるいは他のいくつかの形式において（ｙ，ｙ＋ｚ）と示すことができる。他の実施形態および改変例が、添付の特許請求の範囲によって定義されるような本発明の範囲内にある。
【０２７７】
付録
Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズム
Ｇを巡回群（例えば、上記の<ｘ’>）とし、その位数ｎは、各累乗ｅ（ｐ）まで増加された個別の素数の積、すなわち、
【数１２５】
2008541568.tif 000138
【０２７８】
である（図５では、ｎ＝Ｐπ）。ＸをＧの生成元とし、ｙをＧの要素とする。
【数１２６】
2008541568.tif 000139
【０２７９】
とする。方程式ｘａ＝ｙを満たす非負整数を見つけるため、以下のアルゴリズムを用いることができる。
【０２８０】
１．ｎの各素因数ｐを見つけるため、
【数１２７】
2008541568.tif 000140
【０２８１】
となるようなａ（ｐ）を見つける。これは、位数Ｐｅ(ｐ)の群<ｘｐ>における離散対数問題である。
【０２８２】
２．このとき、中国人剰余定理を用いて、以下となるようなａを発見する。
【０２８３】
ａは、ｎの全ての素因数ｐに関するａ(ｐ)  ｍｏｄ  Ｐｅ(ｐ)に対して合同である。
【０２８４】
特に、ａを以下が得られるように設定することができる。
【数１２８】
2008541568.tif 000141
【０２８５】
ここで、ｄ（ｐ）は、
【数１２９】
2008541568.tif 000142
【０２８６】
となるような整数である。
【０２８７】
参考文献
以下の番号が付与された参考文献は、本明細書中、参考のため援用される。
【０２８８】
［１］Ｍ．ＡｂｄａｌｌａおよびＤ．Ｐｏｉｎｔｃｈｅｖａｌ「Ｓｉｍｐｌｅ  ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｐｒｏｔｏｃｏｌｓ」、予稿集、ＣＴ−ＲＳＡ２００５、ＬＮＣＳ３３７６、ｐｐ．１９１−２０８．Ｓｐｒｉｎｇｅｒ、２００５．
［２］Ｍ．Ｂｅｌｌａｒｅ、Ｄ．ＰｏｉｎｔｃｈｅｖａｌおよびＰ．Ｒｏｇａｗａｙ「Ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ」、予稿集、Ｅｕｒｏｃｒｙｐｔ２０００、ＬＮＣＳ１８０７、ｐｐ．１３９−１５５．Ｓｐｒｉｎｇｅｒ、２０００
［３］Ｍ．ＢｅｌｌａｒｅおよびＰ．Ｒｏｇａｗａｙ「Ｒａｎｄｏｍ  ｏｒａｃｌｅｓ  ａｒｅ  ｐｒａｃｔｉｃａｌ：  ａ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｄｅｓｉｇｎｉｎｇ  ｅｆｆｉｃｉｅｎｔ  ｐｒｏｔｏｃｏｌｓ．」、予稿集、ＡＣＭＣＣＳ１９９３、ｐｐ．６２−７３．ＡＣＭ、１９９３
［４］Ｍ．ＢｅｌｌａｒｅおよびＰ．Ｒｏｇａｗａｙ「Ｅｎｔｉｔｙ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  ｋｅｙ  ｄｉｓｔｒｉｂｕｔｉｏｎ」、予稿集、Ｃｒｙｐｔｏ１９９３、ＬＮＣＳ７７３、ｐｐ．２３２−２４９．Ｓｐｒｉｎｇｅｒ、１９９４
［５］Ｍ．ＢｅｌｌａｒｅおよびＰ．Ｒｏｇａｗａｙ．「Ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｓｅｓｓｉｏｎ  ｋｅｙ  ｄｉｓｔｒｉｂｕｔｉｏｎ：  ｔｈｅ  ｔｈｒｅｅ  ｐａｒｔｙ  ｃａｓｅ．」、予稿集、ＳＴＯＣ１９９５、ｐｐ．５７−６６．ＡＣＭ、１９９５
［６］Ｓ．Ｍ．ＢｅｌｌｏｖｉｎおよびＭ．Ｍｅｒｒｉｔｔ「Ｅｎｃｒｙｐｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ：  ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｐｒｏｔｏｃｏｌｓ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ」、ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｒｅｓｅａｒｃｈ  ｉｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ、ｐｐ．７２−８４．ＩＥＥＥ、１９９２
［７］Ｓ．Ｍ．ＢｅｌｌｏｖｉｎおよびＭ．Ｍｅｒｒｉｔｔ「Ａｕｇｍｅｎｔｅｄ  ｅｎｃｒｙｐｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ：  ａ  ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｐｒｏｔｏｃｏｌ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ  ａｎｄ  ｐａｓｓｗｏｒｄ  ｆｉｌｅ  ｃｏｍｐｒｏｍｉｓｅ」、ＡＣＭ  ＣＣＳ１９９３、ｐｐ．２４４−２５０．ＡＣＭ、１９９３
［８］Ｄ．Ｂｏｎｅｈ「Ｔｈｅ  ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｐｒｏｂｌｅｍ」、予稿集、ＡＮＴＳ−ＩＩＩ、ＬＮＣＳ１４２３、ｐｐ．４８−６３．Ｓｐｒｉｎｇｅｒ、１９９８
［９］Ｒ．Ｃ．ＢｏｓｅおよびＤ．Ｋ．Ｒａｙ−Ｃｈａｕｄｈｕｒｉ．「Ｏｎ  ａ  ｃｌａｓｓ  ｏｆ  ｅｒｒｏｒ  ｃｏｒｒｅｃｔｉｎｇ  ｂｉｎａｒｙ  ｇｒｏｕｐ  ｃｏｄｅｓ」、Ｉｎｆ．Ｃｏｎｔｒｏｌ、３、ｐｐ．６８−７９、１９６０
［１０］Ｖ．Ｂｏｙｋｏ、Ｐ．ＭａｃＫｅｎｚｉｅおよびＳ．Ｐａｔｅｌ「Ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｐａｓｓｗｏｒｄ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｕｓｉｎｇ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ」、予稿集、Ｅｕｒｏｃｒｙｐｔ２０００、ＬＮＣＳ  １８０７、ｐｐ．１５６−１７１．Ｓｐｒｉｎｇｅｒ、２０００）
［１１］Ｃ．Ｃａｃｈｉｎ、Ｓ．Ｍｉｃａｌｉ、Ｍ．Ｓｔａｄｌｅｒ「Ｃｏｍｐｕｔａｔｉｏｎａｌ  ｐｒｉｖａｔｅ  ｉｎｆｏｒｍａｔｉｏｎ  ｒｅｔｒｉｅｖａｌ  ｗｉｔｈ  ｐｏｌｙｌｏｇａｒｉｔｈｍｉｃ  ｃｏｍｍｕｎｉｃａｔｉｏｎ」、予稿集、Ｅｕｒｏｃｒｙｐｔ１９９９、ＬＮＣＳ１５９２、ｐｐ．４０２−４１４、Ｓｐｒｉｎｇｅｒ、１９９９
［１２］Ｒ．Ｃａｎｅｔｔｉ、Ｏ．ＧｏｌｄｒｅｉｃｈおよびＳ．Ｈａｌｅｖｉ「Ｔｈｅ  ｒａｎｄｏｍ  ｏｒａｃｌｅ  ｍｅｔｈｏｄｏｌｏｇｙ，  ｒｅｖｉｓｉｔｅｄ」（ＪＡＣＭ、ｖｏｌ．５１、ｎｏ．４、ｐｐ．５５７−５９４．ＡＣＭ、２００４．（予備版がＳＴＯＣ１９９８に記載、ｐｐ．２０９−２１８）
［１３］Ｒ．Ｃａｎｅｔｔｉ、Ｓ．Ｈａｌｅｖｉ、Ｊ．Ｋａｔｚ、Ｙ．ＬｉｎｄｅｌｌａｎｄＰ．ＭａｃＫｅｎｚｉｅ「Ｕｎｉｖｅｒｓａｌｌｙ−ｃｏｍｐｏｓａｂｌｅ  ｐａｓｓｗｏｒｄ−ベースｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ」、予稿集、Ｅｕｒｏｃｒｙｐｔ２００５、ＬＮＣＳ３４９４、ｐｐ．４０４−４２１．Ｓｐｒｉｎｇｅｒ、２００５
［１４］Ｄ．Ｃｏｐｐｅｒｓｍｉｔｈ「Ｆｉｎｄｉｎｇ  ａ  ｓｍａｌｌ  ｒｏｏｔ  ｏｆ  ａ  ｂｉｖａｒｉａｔｅ  ｉｎｔｅｇｅｒ  ｅｑｕａｔｉｏｎ；  ｆａｃｔｏｒｉｎｇ  ｗｉｔｈ  ｈｉｇｈ  ｂｉｔｓ  ｋｎｏｗｎ」、予稿集、Ｅｕｒｏｃｒｙｐｔ１９９６、ＬＮＣＳ１０７０、ｐｐ．１７８−１８９．Ｓｐｒｉｎｇｅｒ、１９９６
［１５］Ｄ．Ｃｏｐｐｅｒｓｍｉｔｈ「Ｆｉｎｄｉｎｇ  ａ  ｓｍａｌｌ  ｒｏｏｔ  ｏｆ  ａ  ｕｎｉｖａｒｉａｔｅ  ｍｏｄｕｌａｒ  ｅｑｕａｔｉｏｎ」、予稿集、Ｅｕｒｏｃｒｙｐｔ１９９６、ＬＮＣＳ１０７０、ｐｐ．１５５−１６５．Ｓｐｒｉｎｇｅｒ、１９９６
［１６］Ｒ．ＣｒａｍｅｒおよびＶ．Ｓｈｏｕｐ「Ａ  ｐｒａｃｔｉｃａｌ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ  ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ａｄａｐｔｉｖｅ  ｃｈｏｓｅｎ  ｃｉｐｈｅｒｔｅｘｔ  ａｔｔａｃｋ」、予稿集、Ｃｒｙｐｔｏ１９９８、ＬＮＣＳ１４６２、ｐｐ．１３−２５．Ｓｐｒｉｎｇｅｒ、１９９８
［１７］Ｒ．ＣｒａｍｅｒおよびＶ．Ｓｈｏｕｐ「Ｕｎｉｖｅｒｓａｌ  ｈａｓｈ  ｐｒｏｏｆｓ  ａｎｄ  ａ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｃｈｏｓｅｎ  ｃｉｐｈｅｒｔｅｘｔ  ｓｅｃｕｒｅ  ｐｕｂｌｉｃ  ｋｅｙ  ｅｎｃｒｙｐｔｉｏｎ」、予稿集、Ｅｕｒｏｃｒｙｐｔ２００２、ＬＮＣＳ２３３２、ｐｐ．４５−６４．Ｓｐｒｉｎｇｅｒ、２００２）
［１８］Ｉ．ＤａｍｇａｒｄおよびＭ．Ｋｏｐｒｏｗｓｋｉ「Ｇｅｎｅｒｉｃ  ｌｏｗｅｒ  ｂｏｕｎｄｓ  ｆｏｒ  ｒｏｏｔ  ｅｘｔｒａｃｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ  ｉｎ  ｇｅｎｅｒａｌ  ｇｒｏｕｐｓ」、予稿集、Ｅｕｒｏｃｒｙｐｔ２００２、ＬＮＣＳ２３３２、ｐｐ．２５６−２７１．Ｓｐｒｉｎｇｅｒ、２００２
［１９］Ｗ．ＤｉｆｆｉｅおよびＭ．Ｈｅｌｌｍａｎ．「Ｎｅｗ  ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  ｃｒｙｐｔｏｇｒａｐｈｙ」、ＩＥＥＥＴｒａｎｓ．Ｉｎｆｏ．Ｔｈｅｏｒｙ、２２（６）：６４４−６５４、１９７６
［２０］Ｃ．ＤｗｏｒｋおよびＭ．Ｎａｏｒ「Ｐｒｉｃｉｎｇ  ｖｉａ  ｐｒｏｃｅｓｓｉｎｇ  ｏｒ  ｃｏｍｂａｔｔｉｎｇ  ｊｕｎｋ  ｍａｉｌ」、予稿集、Ｃｒｙｐｔｏ１９９２、ＬＮＣＳ７４０、ｐｐ．１３９−１４７．Ｓｐｒｉｎｇｅｒ、１９９３
［２１］Ｒ．ＧｅｎｎａｒｏおよびＹ．Ｌｉｎｄｅｌｌ．「Ａ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｐａｓｓｗｏｒｄ−ベースｄ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ」、予稿集、Ｅｕｒｏｃｒｙｐｔ２００３、ＬＮＣＳ２６５６、ｐｐ．５２４−５４３．Ｓｐｒｉｎｇｅｒ、２００３
［２２］Ｃ．ＧｅｎｔｒｙおよびＺ．Ｒａｍｚａｎ「Ｓｉｎｇｌｅ−ｄａｔａｂａｓｅ  ｐｒｉｖａｔｅ  ｉｎｆｏｒｍａｔｉｏｎ  ｒｅｔｒｉｅｖａｌ  ｗｉｔｈ  ｃｏｎｓｔａｎｔ  ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｒａｔｅ」、予稿集、ＩＣＡＬＰ２００５、ｐｐ．８０３−８１４．Ｓｐｒｉｎｇｅｒ、２００５
［２３］Ｏ．ＧｏｌｄｒｅｉｃｈおよびＹ．Ｌｉｎｄｅｌｌ．「Ｓｅｓｓｉｏｎ−ｋｅｙ  ｇｅｎｅｒａｔｉｏｎ  ｕｓｉｎｇ  ｈｕｍａｎ  ｐａｓｓｗｏｒｄｓ  ｏｎｌｙ」、予稿集、Ｃｒｙｐｔｏ２００１、ＬＮＣＳ２１３９、ｐｐ．４０８−４３２．Ｓｐｒｉｎｇｅｒ、２００１
［２４］Ｌ．Ｇｏｎｇ「Ｏｐｔｉｍａｌ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｐｒｏｔｏｃｏｌｓ  ｒｅｓｉｓｔａｎｔ  ｔｏ  ｐａｓｓｗｏｒｄ  ｇｕｅｓｓｉｎｇ  ａｔｔａｃｋｓ」、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｅｃｕｒｉｔｙ  Ｆｏｕｎｄａｔｉｏｎｓ  Ｗｏｒｋｓｈｏｐ、ｐａｇｅｓ２４−２９．ＩＥＥＥ、１９９５
［２５］Ｌ．Ｇｏｎｇ、Ｔ．Ｍ．Ａ．Ｌｏｍａｓ、Ｒ．Ｍ．ＮｅｅｄｈａｍおよびＪ．Ｈ．Ｓａｌｔｚｅｒ「Ｐｒｏｔｅｃｔｉｎｇ  ｐｏｏｒｌｙ  ｃｈｏｓｅｎ  ｓｅｃｒｅｔｓ  ｆｒｏｍ  ｇｕｅｓｓｉｎｇ  ａｔｔａｃｋｓ」、ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、１１（５）：６４８−６５６、Ｊｕｎｅ１９９３
［２６］Ａ．Ｈｏｃｑｕｅｎｇｈｅｍ「Ｃｏｄｅｓ  ｃｏｒｅｃｔｅｕｒｓ  ｄ’ｅｒｒｅｕｒｓ．  Ｃｈｉｆｆｒｅｓ」（２、ｐｐ．１４７−１５６、１９５９）
［２７］ＩＥＥＥ  Ｓｔａｎｄａｒｄ  １３６３−２０００，  Ｓｔａｎｄａｒｄ  ｓｐｅｃｉｆｉｃａｔｉｏｎｓ  ｆｏｒ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｇｒａｐｈｙ，  ２０００
［２８］Ｄ．Ｊａｂｌｏｎ．「Ｓｔｒｏｎｇ  ｐａｓｓｗｏｒｄ−ｏｎｌｙ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ」、ＡＣＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ、ＡＣＭＳＩＧＣＯＭＭ、２６（５）：５−２０、１９９６
［２９］Ｄ．Ｊａｂｌｏｎ「Ｅｘｔｅｎｄｅｄ  ｐａｓｓｗｏｒｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｐｒｏｔｏｃｏｌｓ  ｉｍｍｕｎｅ  ｔｏ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋ」ＷＥＴＩＣＥ’９７  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｅｎｔｅｒｐｒｉｓｅ  Ｓｅｃｕｒｉｔｙにおける、ｐｐ．２４８−２５５．ＩＥＥＥ、１９９７
［３０］Ｓ．ＪｉａｎｇおよびＧ．Ｇｏｎｇ．「Ｐａｓｓｗｏｒｄ  Ｂａｓｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｗｉｔｈ  ｍｕｔｕａｌ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ」、ＳＡＣ２００４、ＬＮＣＳ３３５７、ｐｐ．２６７−２７９．Ｓｐｒｉｎｇｅｒ、２００４
［３１］Ｊ．Ｋａｔｚ、Ｒ．ＯｓｔｒｏｖｓｋｙおよびＭ．Ｙｕｎｇ．「Ｐｒａｃｔｉｃａｌ  ｐａｓｓｗｏｒｄ−ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｕｎｄｅｒ  ｓｔａｎｄａｒｄ  ａｓｓｕｍｐｔｉｏｎｓ」、予稿集、Ｅｕｒｏｃｒｙｐｔ２００１、ＬＮＣＳ２０４５、ｐｐ．４７５−４９４．Ｓｐｒｉｎｇｅｒ、２００１
［３２］Ｃ．ＫａｕｆｍａｎおよびＲ．Ｐｅｒｍｉａｎ．ＰＤＭ「ａ  ｎｅｗ  ｓｔｒｏｎｇ  ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｐｒｏｔｏｃｏｌ」、Ｕｓｅｎｉｘ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ、２００１
［３３］Ｔ．Ｋｗｏｎ「Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  ｋｅｙ  ａｇｒｅｅｍｅｎｔ  ｖｉａ  ｍｅｍｏｒａｂｌｅ  ｐａｓｓｗｏｒｄｓ」、予稿集、ＮＤＳＳ２００１．ＩＳＯＣ、２００１
［３４］Ａ．ＬｅｎｓｔｒａおよびＥ．Ｖｅｒｈｅｕｌ．「Ｓｅｌｅｃｔｉｎｇ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｋｅｙ  ｓｉｚｅｓ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｈｇｙ、１４（４）：２５５−２９３、２００１
［３５］Ｓ．ＬｉｎおよびＤ．Ｊ．Ｃｏｓｔｅｌｌｏ、Ｊｒ．「Ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｃｏｄｉｎｇ：  ｆｕｎｄａｍｅｎｔａｌｓ  ａｎｄ  ａｐｐｌｉｃａｔｉｏｎｓ」、Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ、ＥｎｇｌｅｗｏｏｄＣｌｉｆｆｓ、ＮＪ、１９８３
［３６］Ｓ．Ｌｕｃｋｓ「Ｏｐｅｎ  ｋｅｙ  ｅｘｃｈａｎｇｅ：  Ｈｏｗ  ｔｏ  ｄｅｆｅａｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ  ｗｉｔｈｏｕｔ  ｅｎｃｒｙｐｔｉｎｇ  ｐｕｂｌｉｃ  ｋｅｙｓ」、予稿集、Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ  Ｗｏｒｋｓｈｏｐ、ＬＮＣＳ１３６１、ｐｐ．７９−９０．Ｓｐｒｉｎｇｅｒ、１９９８
［３７］Ｐ．ＭａｃＫｅｎｚｉｅ、Ｓ．ＰａｔｅｌおよびＲ．Ｓｗａｍｉｎａｔｈａｎ「Ｐａｓｓｗｏｒｄ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ベースｄ  ｏｎ  ＲＳＡ」、予稿集、Ａｓｉａｃｒｙｐｔ２０００、ＬＮＣＳ１９７６、ｐｐ．５９９−６１３．Ｓｐｒｉｎｇｅｒ、２０００
［３８］Ａ．Ｍａｙ．「Ａ  ｔｏｏｌ  ｋｉｔ  ｆｏｒ  ｆｉｎｄｉｎｇ  ｓｍａｌｌ  ｒｏｏｔｓ  ｏｆ  ｂｉｖａｒｉａｔｅ  ｐｏｌｙｎｏｍｉａｌｓ  ｏｖｅｒ  ｔｈｅ  ｉｎｔｅｇｅｒｓ」、予稿集、Ｅｕｒｏｃｒｙｐｔ２００５、ＬＮＣＳ３４９４、ｐｐ．２５１−２６７．Ｓｐｒｉｎｇｅｒ、２００５
［３９］Ｍ．ＮａｏｒおよびＢ．Ｐｉｎｋａｓ「Ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒ  ａｎｄ  ｐｏｌｙｎｏｍｉａｌ  ｅｖａｌｕａｔｉｏｎ」、予稿集、ＳＴＯＣ１９９９、ｐｐ．２４５−２５４．ＡＣＭ、１９９９
［４０］Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ  （ＮＩＳＴ）「Ａｎｎｏｕｎｃｉｎｇ  ｔｈｅ  Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｓｔａｎｄａｒｄ」、ＦＩＰＳ  １８０−１、Ｕ．Ｓ．  Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｃｏｍｍｅｒｃｅ、Ａｐｒｉｌ、１９９５
［４１］Ｓ．Ｐａｔｅｌ「Ｎｕｍｂｅｒ  ｔｈｅｏｒｅｔｉｃ  ａｔｔａｃｋｓ  ｏｎ  ｓｅｃｕｒｅ  ｐａｓｓｗｏｒｄ  ｓｃｈｅｍｅｓ」、予稿集、ｔｈｅ  ＩＥＥＥ  Ｓｙｍ．  ｏｎ  Ｒｅｓｅａｒｃｈ  ｉｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ、ｐｐ．２３６−２４７、１９９７
［４２］Ｍ．Ｏ．Ｒａｂｉｎ「Ｈｏｗ  ｔｏ  ｅｘｃｈａｎｇｅ  ｓｅｃｒｅｔｓ  ｂｙ  ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒ」、未発表原稿、１９８１
［４３］Ｒ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ、およびＬ．Ａｄｌｅｍａｎ「Ａ  ｍｅｔｈｏｄ  ｆｏｒ  ｏｂｔａｉｎｉｎｇ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅ  ａｎｄ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ、２１：１２０−１２６、１９７８
［４４］Ｍ．Ｓｔｅｉｎｅｒ、Ｇ．Ｔｓｕｄｉｋ、およびＭ．Ｗａｉｄｎｅｒ「Ｒｅｆｉｎｅｍｅｎｔ  ａｎｄ  ｅｘｔｅｎｓｉｏｎ  ｏｆ  ｅｎｃｒｙｐｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ」、Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ  Ｒｅｖｉｅｗ、２９：２２−３０．ＡＣＭ、１９９５
［４５］Ｔ．Ｗｕ．「Ｔｈｅ  ｓｅｃｕｒｅ  ｒｅｍｏｔｅ  ｐａｓｓｗｏｒｄ  ｐｒｏｔｏｃｏｌ」、予稿集、ＮＤＳＳ１９９８、ｐｐ．９７−１１１．ＩＳＯＣ、１９９８）
［４６］Ｔ．Ｗｕ．「Ａ  ｒｅａｌ−ｗｏｒｌｄ  ａｎａｌｙｓｉｓ  ｏｆＫｅｒｂｅｒｏｓ  ｐａｓｓｗｏｒｄ  ｓｅｃｕｒｉｔｙ」、予稿集、ＮＤＳＳ１９９９、ＩＳＯＣ、１９９９
［４７］Ｍ．Ｚｈａｎｇ「Ｎｅｗ  ａｐｐｒｏａｃｈｅｓ  ｔｏ  ｐａｓｓｗｏｒｄ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｂａｓｅｄ  ｏｎ  ＲＳＡ」、予稿集、Ａｓｉａｃｒｙｐｔ２００４、ＬＮＣＳ３３２９、ｐｐ．２３０−２４４．Ｓｐｒｉｎｇｅｒ、２００４
［４８］Ｊ．Ａ．Ｂｕｃｈｍａｎｎ「Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、第二版、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ）、ｐａｇｅｓ［０２３２］２１３−２２６
【図面の簡単な説明】
【０２８９】
【図１】従来技術の通信および本発明の一実施形態において用いられるネットワーク型コンピュータシステムのブロック図である。
【図２】本発明の一実施形態による通信プロトコルを示す。
【図３】本発明の一実施形態において用いられるパスワードマッピングを示す。
【図４】本発明の一実施形態による通信プロトコルを示す。
【図５】本発明の一実施形態による通信プロトコルを示す。
【図６】本発明の一実施形態のためのビット安全性対辞書サイズのグラフである。
【図１】
2008541568.tif 000152
【図２】
2008541568.tif 000153
【図３】
2008541568.tif 000154
【図４】
2008541568.tif 000155
【図５】
2008541568.tif 000156
【図６】
2008541568.tif 000157
【手続補正書】
【提出日】平成20年1月7日(2008.1.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、コンピュータに実装される暗号認証方法であって、
前記第１のコンピュータシステムは、
（１）絶対値が１よりも大きい正の整数値である、Ｎとｘとを示すデータを受信する工程と、
（２）整数ｅと、Ｎに対して素である整数ｂとを示すデータを生成する工程と、
（３）  ｙが、ｘｅ  ｍｏｄ  Ｎ  と等しくなり、zが、
【数１】
2008541568.tif 000158
と等しくなるように、値ｙと値ｚとを定義するデータを生成する工程と、
（４）値ｅと値ｂと値Ｐπと値
【数２】
2008541568.tif 000159
のうちのいずれか１つ以上を示すデータを前記第２のコンピュータシステムに送信することなく、前記値ｙと前記値zとを示すデータを前記第２のコンピュータシステムに送信する工程とを有し、
【数３】
2008541568.tif 000160
であり、
Ｐπは、非ゼロ整数の集合ＰＰの真部分集合θ（π）を形成する１つ以上の整数の積であり、
前記真部分集合θ（π）は、前記値πと関連付けられており、
Ｐは、前記集合ＰＰ内の全ての前記非ゼロ整数の積である
ことを特徴とする暗号認証方法。
【請求項２】
前記第１のコンピュータシステムが、ｅおよびｂの関数の値を表すデータを前記第２のコンピュータシステムデータに送信する工程をさらに含むことを特徴とする請求項１に記載の暗号認証方法。
【請求項３】
ｅに対する前記関数の依存は、ｅ  ｍｏｄ  Ｐπ  と等しい値ａに対する依存であることを特徴とする請求項２に記載の暗号認証方法。
【請求項４】
Ｐπは、
【数４】
2008541568.tif 000161
に対して素であることを特徴とする請求項１に記載の暗号認証方法。
【請求項５】
前記工程（２）は、Ｎに対して素である値ｂ’を表すデータを生成する工程を更に含み、
ｂは、
【数５】
2008541568.tif 000162
と等しい値であり、
前記工程（３）は、
【数６】
2008541568.tif 000163
と等しい値としてｚを示す工程を更に含むことを特徴とする請求項１に記載の暗号認証方法。
【請求項６】
第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、コンピュータに実装される暗号認証方法であって、
前記第２のコンピュータシステムは、
（１）合成数Ｎと整数ｘとを示すデータを生成する工程と、
（２）前記値Ｎと前記値ｘとを示すデータを前記第１のコンピュータシステムに送信し、整数値ｙと整数値ｚとを示すレスポンスデータを受信する工程と、
（３）底ｘ’に対するｙ’の対数  ｍｏｄ  Ｐπ  と等しい値ａを示すデータを生成する工程と、
（４）値
【数７】
2008541568.tif 000164
と等しい値ｂを示すデータを生成する工程と、
（５）前記値ａと前記値ｂとを用いて、前記値πの知識を証明する工程とを有し、
ｘ’およびｙ’は、ｘおよびｙから取得され、
Ｐπは、整数の集合ＰＰの部分集合θ（π）を形成する１つ以上の整数の積であり、
前記部分集合θ（π）は、前記値πと関連付けられており、
【数８】
2008541568.tif 000165
は、ＰＰ−θ（π）内の整数の積である
ことを特徴とする暗号認証方法。
【請求項７】
前記第２のコンピュータシステムは、Ｎおよび／またはオイラーのファイ関数φ（Ｎ）の１つ以上の素因数を表す第１のデータを生成するが、このようなデータを前記第１のコンピュータシステムに提供せず、
前記第２のコンピュータシステムは、前記第１のデータを用いて、前記値ｂを表すデータを生成することを特徴とする請求項６に記載の暗号認証方法。
【請求項８】
Ｐπは、オイラーのファイ関数φ（Ｎ）を除算し、Ｐπは、
【数９】
2008541568.tif 000166
に対して素であることを特徴とする請求項６に記載の暗号認証方法。
【請求項９】
ｘ’＝ｘおよびｙ’＝ｙであることを特徴とする請求項６に記載の暗号認証方法。
【請求項１０】
ｘ’＝ｘｕおよびｙ’＝ｙｕであり、
ｕ＝φ（Ｎ）／Ｐπであり、
φ（Ｎ）は、オイラーのファイ関数であることを特徴とする請求項６に記載の暗号認証方法。
【請求項１１】
ｘは、ＰＰに関するＺＮ＊の疑似生成元であることを特徴とする請求項６に記載の暗号認証方法。
【請求項１２】
第１および第２のコンピュータシステムのうち少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、かつ／または、前記第１および第２のコンピュータシステムで共有される暗号鍵を生成するために、コンピュータに実装される暗号認証方法であって、
前記第２のコンピュータシステムと双方向で動作する記第１のコンピュータシステムは、
データベース内において、前記値πによって定義される第１の位置のデータを決定する工程と、
前記第１のコンピュータシステムが１つ以上のクエリを受信し、前記第２のコンピュータシステムに前記第２の位置のデータを提供するためのプロトコルを実行する工程と、
前記第１の位置と前記第２の位置とが同一であることを検証し、かつ／または、前記第１の位置と前記第２の位置とが同一であることを前記第２のコンピュータシステムが検証できるように、前記第１の位置の関数を前記第２のコンピュータシステムに送信し、かつ／または、前記第１の位置の関数として前記暗号鍵を生成する工程とを有し、
前記クエリは、第1のコンピュータシステムに対して前記データベース内の第２の位置を知らせることなく、前記第２の位置のデータを取得するためのものであることを特徴とする暗号認証方法。
【請求項１３】
前記第１の位置が前記第２の位置と同一であると検証する工程は、前記第１の位置の前記データが前記第１の位置の前記データと同一であることを検証する工程を含むことを特徴とする請求項１２に記載の暗号認証方法。
【請求項１４】
（ｉ）前記第１の位置の関数および（ｉｉ）前記暗号鍵のうちの少なくとも１つは、前記第１の位置の前記データの前記関数であることを特徴とする請求項１２に記載の暗号認証方法。
【請求項１５】
第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、コンピュータに実装される暗号認証方法であって、
前記第１のコンピュータシステムと双方向で動作する前記第２のコンピュータシステムは、
前記第２のコンピュータシステムがデータベース内のデータのための１つ以上のクエリを送信し、前記第１のコンピュータシステムから前記クエリに対する１つ以上のレスポンスを受信するためのプロトコルを実行する工程と、
前記所定の位置と前記第１のコンピュータシステムによって前記値πから決定された第１の位置とが同一であることを検証し、かつ／または、前記第１の位置と前記所定の位置とが同一であることを前記第１のコンピュータシステムが検証できるように、前記所定の位置の関数を前記第１のコンピュータシステムに送信し、かつ／または、前記所定の位置の関数として暗号鍵を生成する工程とを有し、
前記クエリは、前記第1のコンピュータシステムに対して前記データベース内の所定の位置を知らせることなく、前記所定の位置のデータを取得するためのものであり、
前記所定の位置は、前記値πによって定義されることを特徴とする暗号認証方法。
【請求項１６】
第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明するために、かつ／または、前記第１および第２のコンピュータシステムで共有される暗号鍵を生成するために、コンピュータに実装される暗号認証方法であって、
前記第１のコンピュータシステムは、
（１）群Ｇの記述を示すデータを受信する工程と、
（２）整数ｅと前記群Ｇの要素ｂとを示すデータを生成する工程と、
（３）ｙ＝ｘeとなり、
【数１０】
2008541568.tif 000167
となるように、値ｙと値ｚとを定義するデータを生成する工程と、
（４）前記第２のコンピュータシステムが前記値ｅと前記値ｂとに一致する値を示すデータを生成できるように、前記値ｙと前記値ｚとを示すデータを前記第２のコンピュータシステムに送信する工程と、
（５）前記値ｅと前記値ｂとが前記第２のコンピュータシステムによって取得された値と一致することを検証し、かつ／または、前記値ｅと前記値ｂとが前記第２のコンピュータシステムによって取得された値と一致することを前記第２のコンピュータシステムが検証できるように、前記値ｅと前記値ｂとの所定の関数を示すデータを前記第２のコンピュータシステムに提供し、かつ／または、前記値ｅと前記値ｂから前記暗号鍵を生成する工程とを有し、
【数１１】
2008541568.tif 000168
は、前記値πに基づいて選択された１つ以上の整数の積であることを特徴とする暗号認証方法。
【請求項１７】
前記値ｅおよびｂと一致する値は、ａ＝ｅ  ｍｏｄ  Ｐπを含み、ここで、Ｐπは、前記値πに基づいて選択された１つ以上の整数の積であり、
【数１２】
2008541568.tif 000169
に対して素であることを特徴とする請求項１６に記載の暗号認証方法。
【請求項１８】
所定の安全性値πに基づいて第１及び第２のコンピュータシステムとの間の安全な通信を確立するために、コンピュータに実装される暗号認証方法であって、
前記第２のコンピュータシステムは、
（１）位数が前記値πと所定の関係を有する群Ｇの記述を示す第１のデータを生成する工程と、
（２）前記第１のデータを前記第１のコンピュータシステムに送信し、前記群Ｇの要素ｙと要素ｚとを示すレスポンスデータを受信する工程と、
（３）底ｘ’に対するｙ’の離散対数によって定義される値ａを示すデータを生成する工程と、
（４）値
【数１３】
2008541568.tif 000170
を示すデータを生成する工程と、
（５）前記値ａと前記値ｂとを用いて、第１および第２のコンピュータシステムの少なくとも１つが前記第１および第２のコンピュータシステムの他方に対して所定の値πの知識を証明し、かつ／または、暗号鍵を生成する工程とを有し、
ｙの関数であるｙ’と、ｘ’とは、Ｇの真部分群の要素であり、
【数１４】
2008541568.tif 000171
は、前記値πに基づいて選択された１つ以上の整数の積であることを特徴とする暗号認証方法。
【請求項１９】
【数１５】
2008541568.tif 000172
であり、
Ｐπは、前記値πに基づいて選択された１つ以上の整数の積であり、
【数１６】
2008541568.tif 000173
に対して素であり、
前記部分群は位数Ｐπを有することを特徴とする請求項１８に記載の暗号認証方法。
【請求項２０】
前記群Ｇの位数は、
【数１７】
2008541568.tif 000174
に対して素であるが、Ｐπで割り切れ、
Ｐπは、前記値πに基づいて選択された１つ以上の整数の積であり、
【数１８】
2008541568.tif 000175
に対して素であることを特徴とする請求項１８に記載の暗号認証方法。
【請求項２１】
請求項１に記載の暗号認証方法における第１のコンピュータシステムの動作を行うように構成されているコンピュータシステム。
【請求項２２】
請求項１に記載の暗号認証方法における第１のコンピュータシステムの動作を行うように構成されているコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【請求項２３】
請求項６に記載の暗号認証方法における第２のコンピュータシステムの動作を行うように構成されているコンピュータシステム。
【請求項２４】
請求項６に記載の暗号認証方法における第２のコンピュータシステムの動作を行うように構成されているコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【請求項２５】
請求項１２に記載の暗号認証方法における第１のコンピュータシステムの動作を行うように構成されているコンピュータシステム。
【請求項２６】
請求項１２に記載の暗号認証方法における第１のコンピュータシステムの動作を行うように構成されているコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【請求項２７】
請求項15に記載の暗号認証方法における第２のコンピュータシステムの動作を行うように構成されているコンピュータシステム。
【請求項２８】
請求項15に記載の暗号認証方法における第２のコンピュータシステムの動作を行うように構成されているコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【請求項２９】
請求項１６に記載の暗号認証方法における第１のコンピュータシステムの動作を行うように構成されているコンピュータシステム。
【請求項３０】
請求項１６に記載の暗号認証方法における第１のコンピュータシステムの動作を行うように構成されているコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【請求項３１】
請求項１８に記載の暗号認証方法における第２のコンピュータシステムの動作を行うように構成されているコンピュータシステム。
【請求項３２】
請求項１８に記載の暗号認証方法における第２のコンピュータシステムの動作を行うように構成されているコンピュータシステムのための１つ以上のコンピュータ命令を含むデータキャリア。
【国際調査報告】
2008541568.tif 000176