(57)【特許請求の範囲】
【請求項１】
複数のコンピュータが実行する方法であって、
第１コンピュータまたは第３コンピュータが、複数の点を、第１の楕円曲線から第２の楕円曲線上にマップするアイソジャニを生成するステップであって、前記アイソジャニは、複素乗法生成、モジュラー生成、一次独立生成、およびそれらの組み合わせを含む群から選択された技術を用いて生成される、アイソジャニを生成するステップと、
前記第１コンピュータまたは前記第３コンピュータが、前記アイソジャニに対応する公開鍵を記憶手段に格納するステップと、
第２コンピュータが、前記格納された公開鍵に対応する暗号化キーを使って、メッセージを暗号化し、暗号化されたメッセージを前記第１コンピュータに送信するステップと、
前記第１コンピュータが、前記アイソジャニに対応するデクリプションキーを使って、バイリニアペアリングにより前記暗号化されたメッセージをデクリプトするステップと、を含み、
前記バイリニアペアリングは、ワイルペアリング、テートペアリング、およびスクエアペアリングを含む群から選択されたペアリングであることを特徴とする方法。
【請求項２】
前記暗号化キーまたは前記デクリプションキーの少なくとも一方はプライベートキーであり、前記プライベートキーは、前記アイソジャニのデュアルアイソジャニであることを特徴とする請求項１に記載の方法。
【請求項３】
前記生成するステップでは、前記第１コンピュータまたは前記第３コンピュータは、複数の点を第１の楕円曲線から複数の楕円曲線上にマップするように構成されていることを特徴とする請求項１に記載の方法。
【請求項４】
前記楕円曲線はアーベル多様体であることを特徴とする請求項１に記載の方法。
【請求項５】
前記メッセージの暗号化では、前記第２コンピュータは、メッセージに署名するように構成されていることを特徴とする請求項１に記載の方法。
【請求項６】
前記メッセージの暗号化では、前記第２コンピュータは、アイデンティティに基づく暗号化を行うように構成されていることを特徴とする請求項１に記載の方法。
【請求項７】
前記生成するステップでは、前記第１コンピュータまたは前記第３コンピュータは、複数のモジュラーアイソジャニを合成して、どの中間曲線も明らかにすることなく単一の前記アイソジャニを生成するように構成されていることを特徴とする請求項１に記載の方法。
【請求項８】
前記第１コンピュータが、ベースフィールドに達するまでトレースマップを用いることにより、前記アイソジャニによりマップされた楕円曲線上の点を削減するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記第１コンピュータが、トレースマップを用いることにより、アーベル多様体上の点を削減するステップをさらに含むことを特徴とする請求項４に記載の方法。
【請求項１０】
複数のコンピュータが実行する方法であって、
送信側コンピュータが、複数の点を第１の楕円曲線から第２の楕円曲線上にマップするアイソジャニに対応した公開鍵を記憶手段に格納するステップであって、前記アイソジャニは、複素乗法生成、モジュラー生成、一次独立生成、およびそれらの組み合わせを含む群から選択された技術を用いて生成される、公開鍵を記憶手段に格納するステップと、
受信側コンピュータが、前記格納されたアイソジャニに対応するデクリプションキーを使って、バイリニアペアリングにより暗号化されたメッセージをデクリプトするステップと、を含み、
前記バイリニアペアリングは、ワイルペアリング、テートペアリング、およびスクエアペアリングを含む群から選択されたペアリングであることを特徴とする方法。
【請求項１１】
前記デクリプションキーは、前記アイソジャニのデュアルアイソジャニであることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記アイソジャニは、複数の点を第１の楕円曲線から複数の楕円曲線上にマップされていることを特徴とする請求項１０に記載の方法。
【請求項１３】
前記アイソジャニはアーベル多様体であることを特徴とする請求項１０に記載の方法。
【請求項１４】
前記送信側コンピュータが、メッセージに署名するステップをさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１５】
前記送信側コンピュータが、アイデンティティに基づく暗号化を行うステップをさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１６】
前記受信側コンピュータが、ベースフィールドに到達するまでトレースマップを用いることにより、前記アイソジャニによりマップされた楕円曲線上の点を削減するステップをさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１７】
複数のコンピュータを含むシステムであって、
第１コンピュータまたは第３コンピュータは、
複数の点を、第１の楕円曲線から第２の楕円曲線上にマップするアイソジャニを生成するように構成されるとともに、前記アイソジャニは、複素乗法生成、モジュラー生成、一次独立生成、およびそれらの組み合わせを含む群から選択された技術を用いて生成され、
前記アイソジャニに対応する公開鍵を記憶手段に格納するように構成されており、
第２コンピュータは、
前記格納されたアイソジャニに対応する暗号化キーを使って、メッセージを暗号化し、暗号化されたメッセージを前記第１コンピュータに送信し、
前記第１コンピュータは、
前記アイソジャニに対応するデクリプションキーを使って、バイリニアペアリングにより前記暗号化されたメッセージをデクリプトするように構成され、
前記バイリニアペアリングは、ワイルペアリング、テートペアリング、およびスクエアペアリングを含む群から選択されたペアリングであることを特徴とするシステム。
【請求項１８】
前記暗号化キーまたは前記デクリプションキーの少なくとも一方はプライベートキーであり、前記プライベートキーは、前記アイソジャニのデュアルアイソジャニである、ことを特徴とする請求項１７に記載のシステム。
【請求項１９】
前記第１コンピュータまたは前記第３コンピュータは、前記アイソジャニを生成するときに、複数の点を、第１の楕円曲線から複数の楕円曲線上にマップするように構成されていることを特徴とする請求項１７に記載のシステム。
【請求項２０】
前記第１コンピュータまたは前記第３コンピュータは、複数の点を第１の楕円曲線から複数の楕円曲線上にマップするように構成されていることを特徴とする請求項１７に記載のシステム。
【請求項２１】
前記楕円曲線はアーベル多様体であることを特徴とする請求項１７に記載のシステム。
【請求項２２】
前記第２コンピュータは、メッセージに署名するように構成されていることを特徴とする請求項１７に記載のシステム。
【請求項２３】
前記第２コンピュータは、アイデンティティに基づく暗号化を行うように構成されていることを特徴とする請求項１７に記載のシステム。
【請求項２４】
前記第１コンピュータまたは前記第３コンピュータは、複数のモジュラーアイソジャニを合成して、どの中間曲線も明らかにすることなく単一の前記アイソジャニを生成するように構成されていることを特徴とする請求項１７に記載のシステム。
【請求項２５】
前記第１コンピュータがさらに、ベースフィールドに達するまでトレースマップを用いることにより、前記アイソジャニによりマップされた楕円曲線上の点を削減するように構成されていることを特徴とする請求項１７に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的には暗号作成術(cryptology)に関し、より詳細には、暗号システム(cryptosystem)の設計におけるアイソジャニ(isogeny)の使用に関する。
【背景技術】
【０００２】
本出願は、２００３年１１月３日に出願した米国特許仮出願第６０／５１７，１４２号「Use of Isogenies for Design of Cryptosystems」の優先権を主張するものである。
【０００３】
デジタル通信が一般的になるのに従って、関連する通信チャネルを安全なものにする必要性が、一層高まっている。たとえば、現在の技術は、ユーザが、銀行口座、医療データ、ならびに他の個人情報および機密情報にリモートアクセスすることを可能にする。
【０００４】
暗号作成術(cryptology)は、安全なデジタル通信をもたらすために広く使用されている。暗号作成術は概して、メッセージの暗号を作ること（すなわち暗号化(encrypting)）、および暗号を解くこと（デクリプト(decrypting)）に関する。この暗号化およびデクリプトは、何らかの秘密情報(secret information)（たとえば鍵(key)）を使用する。様々な暗号化方法において、単一の鍵または複数の鍵が、暗号化およびデクリプトに使われる。
【０００５】
一般に使用される複数キー暗号システムの１つは、公開鍵暗号化システム(public-key encryption system)である。公開鍵システムでは、受信者(recipient)に対して暗号化されたメッセージ(encrypted message)を送信したいと思う送信者(sender)は、プライベートキー(private key)を用いて生成される、受信者用の認証された公開鍵(authenticated public key)を取得する。この名前が意味するように、公開鍵は、公開されているソースから入手可能であり得る。さらに、偽装攻撃を避けるために、公開鍵は頻繁に認証される。公開鍵の認証は、信頼できるチャネルを介した鍵の交換、信頼できる公開ファイルの使用、信頼できるオンラインサーバの使用、またはオフラインサーバおよび証明書の使用などの技術によって行われることができる。
【０００６】
認証された公開鍵(authenticated public key)を取得した後、送信者は、公開鍵(public key)を用いて元のメッセージ(original message)を暗号化し、暗号文を生成する。指定受信者は次いで、プライベートキー(private key)を使用し、暗号文をデクリプト(decrypt)して元のメッセージを引き出す。プライベートキーにアクセスせずに暗号文をデクリプトすることは、実行不可能と思われている。したがって、プライベートキーへのアクセス権を有する当事者のみが、暗号文のデクリプトに成功することができる。
【０００７】
対称暗号システム(symmetric cryptosystem)（ストリーム暗号やブロック暗号など）を介した公開鍵システムの重大な利点の１つは、二者間通信では、プライベートキーのみが秘密にされればよいことである（対称暗号システムでは、鍵は両側において秘密にされる）。
【０００８】
現在の公開鍵暗号化システムは、有限フィールド(finite field)上の特定の楕円曲線（ＥＣ:elliptic curve）を使用する。楕円曲線から導出される、公開される１対の値が、公開鍵（曲線上の点と、曲線上で単純な乗算（すなわち、整数の乗算）によって生成される、そうした点に対応する公開鍵とを含む）として使用される。検証(verification)（ベリファイ）は、曲線上のバイリニアペアリング(bilinear pairing)を用いて行われる。
【０００９】
概して、楕円曲線は、ＲＳＡ（Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ、およびＡｄｌｅｍａｎ公開鍵暗号化技術）など従来のシステムより比較的低い通信要件を有する暗号化システムを提供し、同程度のセキュリティレベルを維持するものと思われている。
【００１０】
現在の公開鍵暗号化システムに伴う問題点は、安全であることが証明されているシステムがないことである。その結果、現在の公開鍵暗号化システムの安全性は、一組の整数論的(numbertheoretic)問題の難しさに基づいて推定される。
【００１１】
【非特許文献１】A. Menezes, P. van Oorschot, and S. Vanstone entitled, "Handbook of Applied Cryptography," fifth printing (August 2001), published by CRC Press
【非特許文献２】GALBRAITH, S. D., HESS, F., SMART, N.P. ;“Extending the GHS Weil Descent Attack” EUROCRYPT 2002, pgs 29-44
【非特許文献３】BARRETO, P.S.L.M;“The Pairing-Based Crypto Lounge” Published on the internet at http://planeta.terra.com.br/informatica/paublobarret/html9/13/2002, last updated 3/28/2004,22 pgs
【非特許文献４】BONEH, D., GENTRY, C.;“Aggregate and verifiably Encrypted Signature from Bilinear Maps” Proceedings of EUROCRYPT 2003, 22 pgs
【非特許文献５】BONEH, D., SIVERBERG, A.;“Applications of Multilinear Forms to Cryptography”Published to the internet at http://eprint.iacr.org 2002, 20 pages
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、一層の安全性をもたらす公開鍵暗号化システムが望まれる。
【課題を解決するための手段】
【００１３】
公開鍵暗号化システム(pubkic-key encryption system)を提供する技術が開示される。より具体的には、アーベル多様体(Abelian Variety)（たとえば、一次元の事例における楕円曲線）のアイソジャニ(isogeny)が、公開鍵暗号化システムを提供するために使用される。たとえば、このアイソジャニ(isogeny)は、より安全な暗号化(secure encryption)を実現するために、単一の曲線(single curve)ではなく複数の曲線(multiple curves)の使用を可能にする。こうした技術は、デジタル署名(digital signature)および／またはアイデンティティに基づく暗号化（ＩＢＥ:identity based encryptio）による解決法に適用することができる。さらに、アイソジャニ(isogeny)は、たとえばブラインド署名(blind signature)、階層システム(hierarchical system)など、他のアプリケーションでも使うことができる。さらに、これらアイソジャニ(isogeny)を生成するための解決策（ソリューション(solution)）を開示している。
【００１４】
本発明のある態様において、一つの方法は、アイソジャニ(isogeny)に対応した公開鍵を公開すること、を含んでいる。この方法は、さらに加えて、アイソジャニ(isogeny)に対応するデクリプションキー(descryption key)を用いて（たとえば、そのデュアルアイソジャニ(dual isogeny)）、暗号化されたメッセージ(encrypted message)をデクリプトする、ことを含む。
【発明を実施するための最良の形態】
【００１５】
添付の図面を参照して、詳細な説明を行う。これらの各図面において、参照番号のうち左側の数字は、その参照番号が最初に現れる図の番号を指す。また、異なる図面における同じ参照番号の使用は、類似または同一の項目を示す。
【００１６】
以下の説明では、読者が暗号技術に精通していると仮定している。暗号技術の基本的な概論として、読者は、たとえば、非特許文献１を参照されたい。
【００１７】
以下の説明では、複数の楕円曲線（すなわち、一般的にはアーベル多様体）に基づく公開鍵システムを改良する技術を説明する。これら曲線の間でアイソジャニ(isogeny)を生成する（すなわちマッピング(mapping)）ための様々な技術が開示される。生成されたアイソジャニ(generated isogeny)は、公開された暗号化を実現するために、単一の曲線ではなく複数の曲線の使用を可能にする。さらに、こうした技術は、（たとえば、ユーザによってタイプ入力され、または低帯域幅チャネルを介して送信される）比較的短いデジタル署名および／またはアイデンティティに基づく暗号化（ＩＢＥ）による、（たとえば、記憶可能な公開鍵を許可する）解決法に適用することができる。この短い署名(short signature)は、集合検証(aggregate verification)による一層の効率をもたらすことができる。
【００１８】
アイソジャニ(isogeny)を用いた暗号システムの概論
図１は、暗号システムにおいてアイソジャニ(isogeny)を使用する、例示的な方法１００を示す。ステージ１０２は、（楕円曲線、またはより一般的にはアーベル多様体）のアイソジャニ(isogeny)を生成する。アイソジャニ(isogeny)は、受信側または別の当事者（たとえば、図５を参照してさらに説明する、信頼できる当事者）によって生成することができる。ステージ１０２は、生成されたアイソジャニ(isogeny)それぞれに対して、対応するデュアルアイソジャニ(dual isogeny)を生成することもできる（後でさらに説明される）。アイソジャニ(isogeny)を生成する様々な方法は、同じタイトルの章において後で詳述する。さらに、図３および図５を参照してさらに詳述するように、生成されたアイソジャニ(isogeny)は、公開鍵を提供するのに使用され、公開鍵が公開される（１０４）。公開鍵は、送信側または信頼できる機関によって公開することができる（たとえば、図３および図５の説明を参照されたい）。
【００１９】
送信側は次いで、暗号化キーを用いて、メッセージを暗号化する（またはそれに署名する）（１０６）。ステージ１０６の暗号化されたメッセージは、暗号化または署名の信頼性を判定するためのデクリプションキーを用いて、受信側によってベリファイ／デクリプトされることができる（１０８）。一実施形態では、ワイルペアリング(Weil pairing)が、暗号化されたメッセージ(encrypted message)をベリファイ（検証(verify)）するのに使用される（たとえば、同じタイトルの章において後で説明する）。ただし、ワイルペアリングは、ベリファイまたはデクリプト用に使用することができるペアリングの一例に過ぎない。たとえば、テートペアリング(Tate pairing)およびスクエアペアリング(square pairing)など、他のバイリニア(bilinear)および／または非縮退(non-degenerae)ペアリング技術(pairing technique)を使用することができる。
【００２０】
アイソジャニ(isogeny)の概論
図２は、２つの曲線（たとえば、楕円曲線）の間のアイソジャニ(isogeny)の例示的なマップ(map)２００を示す。本図に示すように、曲線Ｅ１は、アイソジャニ(isogeny)φによって、曲線Ｅ２にマップすることができる（ここでφ：Ｅ１→Ｅ２）。また図２は、デュアルアイソジャニ(dual isogeny)
【００２１】
【数１】
0004809598.tif 000002
【００２２】
を示している。
【００２３】
様々な実施形態において、暗号システムにおけるアイソジャニ(isogeny)の使用は、たとえば以下のような性質を提供すると想像される。すなわち、曲線Ｅ１が与えられると、ペア（φ，Ｅ２）の生成は比較的効率的であり、この場合、φ：Ｅ１→Ｅ２はアイソジャニ(isogeny)であるが、アイソジャニ曲線(isogenous curve)のペア（Ｅ１，Ｅ２）が与えられると、ゼロでないどのアイソジャニ(isogeny)φ：Ｅ１→Ｅ２を構成することも比較的困難であり、特殊なアイソジャニ(isogeny)の構成はさらに困難と思われる。したがって、（どの後続メッセージも多項式時間において中断されることを可能にする計算として定義される）グローバルブレーク(global break)と、インスタンスごとのブレーク(per-instance break)との間で違いが引き出される場合、アイソジャニ(isogeny)に基づく暗号システムに対するする、この時点で最もよく知られている攻撃には、グローバルブレーク用の別個のログ(discrete log)、またはそうでなければ、「原始的な(naive)」インスタンスごとの攻撃(native per-instance attack)用の、メッセージごとに１つの別個のログ計算(one discrete log computation)より実質的に長い時間がかかる。
【００２４】
たとえば、各クライアントが、何らかのサービスへのアクセス権（低い値のものでよい）を付与する特殊な署名付きメッセージを与えられる場合のトークンシステム(token system)を検討すると、クライアントは、代表者への電話においてトークンを読み出さなければならない場合があり、したがって、署名は比較的短くてよい。提供されるサービスよりコストが高い、メッセージごとの攻撃を行うのに十分な程大きいパラメータを使うとともに、グローバルブレークを非常にコストが高いものにしておくことが合理的であろう。
【００２５】
アイソジャニ(isogeny)の詳細
フィールド(field)ｋは、ｑ要素(element)を備えるとともに代数的閉包(algebraic closure)
【００２６】
【数２】
0004809598.tif 000003
【００２７】
を有する指標(characteristic)ｐを用いて、確定されることができる。Ｅ／ｋが、体ｋ上で定義される楕円曲線であり、Ｅ（ｋ）が、ｋ上で定義される群であり、ｋ（Ｅ）が、楕円曲線の関数体を表すものとする。また、［ｎ］Ｅまたは［ｎ］が、Ｅにおけるマップ
【００２８】
【数３】
0004809598.tif 000004
【００２９】
を表し、Ｅ［ｎ］が、このマップの核(kernel)を表すものとする。
【００３０】
アイソジャニ(isogeny)φ：Ｅ１→Ｅ２は、Ｅ１のアイデンティティ要素(identity element)をＥ２のアイデンティティ要素に送る不定値の射(non-constant morphism)である。このようなアイソジャニ(isogeny)が存在する場合、Ｅ１およびＥ２はアイソジャニ(isogeny)であるということができる。φが、ｋ中の係数を有する定義式をもつ場合、アイソジャニ(isogeny)は、ｋ上で定義される。どのアイソジャニ(isogeny)も、群準同形、すなわち、すべてのＰ，Ｑ∈Ｅ１に対してφ（Ｐ＋Ｑ）＝φ（Ｐ）＋φ（Ｑ）であることになり、この式で、左辺での加算は、Ｅ１における群法則であり、右辺での加算は、Ｅ２の群法則である。したがって、φの核は、Ｅ１の部分群である。
【００３１】
Ｈｏｍｋ（Ｅ１，Ｅ２）が、ｋ上で定義されるＥ１からＥ２までのアイソジャニ(isogeny)の組を表すものとする。
【００３２】
【数４】
0004809598.tif 000005
【００３３】
は、Ｈｏｍ（Ｅ１，Ｅ２）によって表される。どのアイソジャニ(isogeny)φ：Ｅ１→Ｅ２に対しても、デュアルアイソジャニ(isogeny)
【００３４】
【数５】
0004809598.tif 000006
【００３５】
が存在し、このデュアルアイソジャニ(isogeny)は、
【００３６】
【数６】
0004809598.tif 000007
【００３７】
のようになり、上式で、ｎ＝ｄｅｇ（φ）がアイソジャニ(isogeny)の次数である。デュアルアイソジャニ(isogeny)は、標準的な性質
【００３８】
【数７】
0004809598.tif 000008
【００３９】
を満たす。
【００４０】
一実施形態では、有限マップ(finite map)としてのφの次数が、フィールドｋ（Ｅ２）の（φによる）引戻しにおける、ｋ（Ｅ１）の拡大の次数としてさらに定義されることができ、ここで、φは、ｋ上で定義される。これは、（関数体の拡大が可分であると仮定して）その核の大きさによって、または上記の式によって考えると便利であろう。したがって、アイソジャニ(isogeny)は、その次数がＢ−スムーズである（すなわち、ｄｅｇ（φ）の素因子がＢ以下である）場合、Ｂ−スムーズであるといわれる。楕円曲線Ｅの自己準同形の組Ｈｏｍ（Ｅ，Ｅ）は、Ｅｎｄ（Ｅ）と表され、この組は、定義
【００４１】
【数８】
0004809598.tif 000009
【００４２】
によって与えられるリング(ring)の構造(structure)を有する。
【００４３】
概して、群(group)Ｈｏｍ（Ｅ１，Ｅ２）は、トーション(torsion)のない、左Ｅｎｄ（Ｅ２）−モジュールおよび右Ｅｎｄ（Ｅ１）−モジュールである。Ｅ１＝Ｅ２＝Ｅの場合、代数的構造(algebraic atructure)は、より豊富になる。すなわち、Ｈｏｍ（Ｅ１，Ｅ２）＝Ｅｎｄ（Ｅ）は、非零因子(zero divisor)を有する（単なるモジュールではなく）リングであり、指標ゼロ(characteristic zero)をもつ。
【００４４】
一実施形態では、これはラティス(lattice)であると考えることができる。すなわち、Ｅが、何らかのフィールドｋ上で定義される楕円曲線であるとする。この場合、Ｅｎｄ（Ｅ）は、二次虚数フィールド中のオーダ(order)Ｚか、または四元数(quatrnion)代数(algebra)中の最大オーダに対して同形(isomorphic)である。どの２つの楕円曲線Ｅ１、Ｅ２に対しても、群Ｈｏｍ（Ｅ１，Ｅ２）は、階数(rank)が最大４の自由Ｚ−モジュールである。Ｅｎｄ（Ｅ）がＺより大きいとき、Ｅは複素乗法をもつという。フロベニウス自己準同形に対応する、Ｅｎｄ（Ｅ）中の要素
【００４５】
【数９】
0004809598.tif 000010
【００４６】
は、πによって表され、特性方程式ｘ２−ｔｒ（Ｅ）ｘ＋ｑ＝０を満たす。楕円曲線ｃのコンダクタ(conductor)は、［Ｅｎｄ（Ｅ）：Ｚ［π］］である。
【００４７】
ワイル(Weil)ペアリング
ワイルペアリングｅｎ：Ｅ［ｎ］×Ｅ［ｎ］→μｎは、ｋにおける１のｎ乗根からなる群中の値を有するバイリニアの非縮退マップである。一実施形態では、ワイルペアリングは、図１のベリファイ／デクリプトステージ１０８を実施するのに使用される。ただし、ワイルペアリングは、ベリファイまたはデクリプト用に使用されることができるペアリングの一例に過ぎない。たとえば、テート(Tate)ペアリングおよびスクエアペアリングなど、他のバイリニアおよび／または非縮退ペアリング技術が使用されることができる。ワイルペアリングは、以下の性質を満たす。
【００４８】
【数１０】
0004809598.tif 000011
【００４９】
ここで、
【００５０】
【数１１】
0004809598.tif 000012
【００５１】
は、Ｅ１に対するペアリング計算であり、ｅｎ（φ（Ｓ），Ｔ）は、Ｅ２に対するペアリング計算である。両方の曲線がｎ−トーション点をもつことによって、その位数に制約が課せられることに留意されたい。このことは問題を引き起こさない。というのは、点からなる２つの群が同じ位数を有するとき、かつそのときに限り、テートの定理により、Ｅ１（ｋ）およびＥ２（ｋ）がｋ上のアイソジャニ(isogeny)であるからである。
【００５２】
ワイルペアリングは、一次従属であるすべての入力ペア用のアイデンティティを評価する。したがって、入力点が互いのスカラー乗でないことを保証する機構が有益であろう。１つの手法は、ｎ−トーション点の完全な群
【００５３】
【数１２】
0004809598.tif 000013
【００５４】
がｋ上で定義されるほど十分に大きい有限フィールドｋ上で定義される曲線Ｅ２を使うことである。この状況において、１／ｎのオーダにおいて、群Ｅ２［ｎ］の２つのランダム要素が一次従属である確率は無視することができるので、ワイルペアリングの値は、高い確率で自明でない場合がある。上記の式は、Ｅ１におけるペアリング値の分散が、Ｅ２におけるペアリング値の分散と一致することを保証する。
【００５５】
あるいは、修正されたペアリング関数
【００５６】
【数１３】
0004809598.tif 000014
【００５７】
が、λが任意の非スカラー自己準同形である場合に使われることができ、その結果、Ｐおよびλ（Ｐ）は、一次独立であり、
【００５８】
【数１４】
0004809598.tif 000015
【００５９】
となる。このようなマップλは、Ｅのディストーション(distortion)またはツイスト(twist)と呼ばれる。
【００６０】
アイソジャニ(isogeny)の生成(generation)
様々な実施形態において、いくつかの方法は、図１のステージ１０２を参照して説明したような、高次の(hign degree)アイソジャニ(isogeny)（たとえば、楕円曲線、またはより一般的にはアーベル多様体のアイソジャニ(isogeny)）およびアイソジャニ(isogeny)のペアデュアルを構成するのに用いることができる。本明細書において論じられる短いデジタル署名およびＩＢＥ暗号システムは、値（Ｐ，φ（Ｐ））のペアが公開鍵として公開されるという規約に従うことができ、デュアル
【００６１】
【数１５】
0004809598.tif 000016
【００６２】
の評価が、プライベートキーを構成する。
【００６３】
一実施形態では、こうした構成は、以下のように要約されることができる。すなわち、任意のＥが与えられる場合、その次数ｎがランダムに分散されるとともに、確率
【００６４】
【数１６】
0004809598.tif 000017
【００６５】
を有する素数であるアイソジャニ(isogeny)Ｅ→Ｅを構成するアルゴリズムが存在する。任意の曲線Ｅ１が与えられる場合、時間Ｏ（Ｂ３）において、Ｅ１からランダムターゲットまで、ランダムなＢ−スムーズアイソジャニ(isogeny)を構成するアルゴリズムが存在する。相対的素数次(relatively prime degree)を有する、Ｈｏｍｋ（Ｅ１，Ｅ２）におけるＥ１、Ｅ２および２つの一次独立アイソジャニ(isogeny)が与えられる場合、素数次のアイソジャニ(isogeny)を構成するアルゴリズムが存在する（たとえば、独立アイソジャニ(isogeny)に関する以下の説明を参照されたい）。
【００６６】
複素乗法アイソジャニ(complex multiplication isogeny)
Ｅ１＝Ｅ２を前述同様とし、Ｅ１は判別式Ｄ＜０である虚数二次オーダＯＤによる複素乗法（ＣＭ）をもつと仮定する。確率的アルゴリズムは、｜Ｄ｜において期待される時間多項式中の、素数次が大きいＥ１の自己準同形φを伴って、このような曲線Ｅ１を生じるために記述されることができる。
【００６７】
１．判別式Ｄのヒルバートクラスの多項式ＨＤ（Ｘ）を計算する。Ｋは、Ｑ上のＨＤ（Ｘ）の分解体を表すものとする。
【００６８】
２．ＨＤ（Ｘ）の任意の根ｘを選択し、ｘと等しいｊ−不変量をもつ、Ｃ上の楕円曲線Ｅを構成する。Ｅは、ナンバーフィールドＫ上で定義されることに留意されたい。
【００６９】
３．構成により、曲線Ｅは、
【００７０】
【数１７】
0004809598.tif 000018
【００７１】
による複素乗法をもつ。ｑ−拡大(expansion)に対する線形代数を用いて、アイソジャニ(isogeny)
【００７２】
【数１８】
0004809598.tif 000019
【００７３】
に対応するＫ中の係数を有する有理関数Ｉ（Ｘ，Ｙ）を明示的にみつける。
【００７４】
４．ａ２−ｂ２Ｄが素数となるまで、ランダム整数ａおよびｂを選択する。そうすると、アイソジャニ(isogeny)
【００７５】
【数１９】
0004809598.tif 000020
【００７６】
は、素数次をもつＥの自己準同形(endomorphism)となる。
【００７７】
５．Ｋの任意の素イデアル(prime ideal)Ｐを選択し、Ｐをモジュロ(modulo)としてＥおよびＩの係数(coefficient)を減少する。Ｅ１は、Ｅの減少(reduction)を表すものとし、φは、
【００７８】
【数２０】
0004809598.tif 000021
【００７９】
の減少であるとする。
【００８０】
アルゴリズムのステージ１〜３は、決定論的であり、｜Ｄ｜における多項式時間である。ステージ４に関して、ナンバーフィールドに関する素数定理は、ａ２−ｂ２Ｄが素数である確率が１／ｌｏｇ（ａ２−ｂ２Ｄ）であることを意味し、したがって、サイズがｎの整数ａおよびｂに対して、ステージ４はｌｏｇ（Ｄｎ２）の試行後に終了すると期待することができる。
【００８１】
結果として得られる自己準同形φは、素数次がＥ１の自己準同形である。φおよびそのデュアル
【００８２】
【数２１】
0004809598.tif 000022
【００８３】
両方は、ａおよびｂを知ることにより、スカラー乗算および加算に伴う有理関数Ｉ（Ｘ，Ｙ）のみを使って評価されることができる。このようなアイソジャニ(isogeny)φは、ＣＭ−アイソジャニ(isogeny)と呼ばれることができる。
【００８４】
モジュラアイソジャニ(modular isogeny)
任意の素数ｌに対して、モジュラ曲線Ｘ０（ｌ）は、次数ｌのアイソジャニ(isogeny)Ｅ１→Ｅ２の同形マップクラスをパラメータ化する。より具体的には、Φｌ（ｊ（Ｅ１），ｊ（Ｅ２））＝０の場合、かつその場合に限り、Ｅ１およびＥ２がｌ−アイソジャニ(isogeny)であるという性質を有する、Ｘ０（ｌ）に対する多項式Φｌ（Ｘ，Ｙ）が存在する。
【００８５】
多項式Φｌ（Ｘ，Ｙ）を用いて、任意のＥ１に対して、次数ｌのアイソジャニ(isogeny)Ｅ１→Ｅ２に関する明示的な多項式とともにｌ−アイソジャニ(isogeny)曲線Ｅ２を計算することができる。モジュラ多項式は、ＸおよびＹにおいて対称なので、反転されたｊ−不変量を用いた計算が、デュアルアイソジャニ(dual isogeny)をみつけるのに使うことができる。
【００８６】
実際には、多項式Φｌ（Ｘ，Ｙ）の係数がかなり大きいので、実際の計算のためにこうした多項式を使うことはできない。そうではなく、異なるものではあるが等価な多項式モデルが、より小さい係数を有するＸ０（ｌ）に対して使うことができる。計算のために使われる厳密なモデルに関わらず、このようにして導出されたアイソジャニ(isogeny)は、モジュラアイソジャニ(modular isogeny)と呼ぶことができる。
【００８７】
モジュラアイソジャニ(modular isogeny)を計算する、現在公知であるアルゴリズムは、概して、ｌという小さい値に対して実行可能である。単独では、小さい次数のモジュラアイソジャニ(modular isogeny)の使用は、あまり安全性を向上させない。というのは、曲線Ｅ１およびＥ２を知っている攻撃者は、各ｌごとに、曲線がｌ−アイソジャニ(isogeny)であるか調べ、ｌ−アイソジャニ(isogeny)である場合には、そのｌ−アイソジャニ(isogeny)を復元することができるからである。ただし、（たとえば、ｌの異なる選択に対して）多くのモジュラアイソジャニ(modular isogeny)を、大きいスムーズ度(smooth degree) 
【００８８】
【数２２】
0004809598.tif 000023
【００８９】
である１つのアイソジャニ(isogeny)φに合成し、中間曲線を明らかにすることなく、φをアイソジャニ(isogeny)として使うことができる。任意の点においてφを評価する能力のある攻撃者はさらに、Ｅ１のｌ−トーション点すべてを計算することによって、また、そうしたトーション点のいずれかがφによって削減されるかを調べることによって、素数ｌを演繹することができる。ただし、デュアルアイソジャニ(dual isogeny)の計算問題は難しいという仮定の下では、攻撃者は、自分が選択した点上でφの評価を行うことができない。さらに、一実施形態において、大きい非スムーズ係数(non-smooth factor)を(degree)に導入するために、スカラアイソジャニ(isogeny)またはＣＭアイソジャニ(isogeny)のいずれかを有する、結果として得られるアイソジャニ(isogeny)を合成することもできる。
【００９０】
一次独立アイソジャニ(linearly independent isogeny)
一実施形態では、一次独立アイソジャニ(isogeny)φおよびψは、相対的素数次(relatively prime degree)のＥ１からＥ２に与えられる。その結果、線形組み合わせ(linear combination)ａφ＋ｂψは、２つの変数ａおよびｂにおける二次形式
【００９１】
【数２３】
0004809598.tif 000024
【００９２】
によって与えられる次数をもつ。外側の係数の次数はφおよびψであり、中間項はｄｅｇ（φ＋ψ）−ｄｅｇ（φ）−ｄｅｇ（ψ）と等しいので、この二次形式の係数は整数であることに留意されたい。二次形式は、原始的なので、ａおよびｂがすべてのペア（ａ，ｂ）∈Ｚ２に対して変化するとき、素数値を無限頻度で保持する。このようにして、大きい非スムーズ（または偶素数）次数の多くのアイソジャニ(isogeny)Ｅ１→Ｅ２を取得することができる。結果として得られる次数が非スムーズである確率も、推定することができる。
【００９３】
アイソジャニ(isogeny)を用いた短い署名スキーム(short signature scheme)
一実施形態として本明細書において論じられる技術は、（たとえば、ユーザによってタイプ入力され、または低帯域幅チャネルを介して送信される）比較的短い署名スキームに適用することができる。楕円曲線におけるアイソジャニ(isogeny)およびペアリングの数学的性質に部分的に基づく２つの署名方式を以下に論じる。
ガロアの不変署名(Galois invariant signature)
【００９４】
【数２４】
0004809598.tif 000025
【００９５】
を、次数ｎの有限フィールドの拡大であるとする。楕円曲線Ｅ１を、
【００９６】
【数２５】
0004809598.tif 000026
【００９７】
上で定義されるアイソジャニ(isogeny)φ：Ｅ１→Ｅ２を伴ってＦｑ上で定義されると解釈し、Ｅ２は、
【００９８】
【数２６】
0004809598.tif 000027
【００９９】
上で定義される楕円曲線である。一実施形態では、曲線Ｅ２は、Ｌの部分体上ではなくＬ上で定義されるが、Ｅ２を、部分体上でのみ定義されると解釈することも可能である。しかし、安全性の理由のため、アイソジャニ(isogeny)φは、
【０１００】
【数２７】
0004809598.tif 000028
【０１０１】
の適切などの部分体上でも定義されることができない。さらに、アイソジャニ(isogeny)φは、上で論じたような様々な技術に従って生成することができる。
【０１０２】
図３は、アイソジャニ(isogeny)を用いてメッセージに署名する、例示的な方法３００を示す。方法３００は、以下のステージを含む。
【０１０３】
公開鍵  ランダムなＰ∈Ｅ１（Ｆｑ）を選択し、Ｑ＝φ（Ｐ）である（Ｐ，Ｑ）を公開する（３０２）。ＰはＦｑ上で定義されるが、φがＦｑ上で定義されないので、ＱはＦｑ上で定義されないことに留意されたい。
【０１０４】
秘密キー  φのデュアルアイソジャニ(isogeny)
【０１０５】
【数２８】
0004809598.tif 000029
【０１０６】
である。
【０１０７】
署名  Ｈを、メッセージ空間から、Ｅ２上のｋ−トーション点の組までの（公開）ランダムオラクルであるとする。メッセージｍが与えられる場合、
【０１０８】
【数２９】
0004809598.tif 000030
【０１０９】
を計算する（上述したように生成された秘密／プライベートキーを用いて、署名を提供するステージ３０４）。上式で、πはｑ乗のフロベニウスマップであり、和は、Ｅ１上の楕円曲線の和を表す。便宜上、演算子
【０１１０】
【数３０】
0004809598.tif 000031
【０１１１】
を、Ｔｒ（「トレース」の略）で表す。Ｓ∈Ｅ１（Ｆｑ）を署名として出力する。署名は次いで、受信側に送信され、受信側によって受信される（それぞれ３０６および３０８）。ガロア群は
【０１１２】
【数３１】
0004809598.tif 000032
【０１１３】
であり、したがってＳはガロア不変量であり、Ｆｑ上で定義されることに留意されたい。
【０１１４】
検証（ベリファイ）(verification)  ｅ１およびｅ２は、それぞれＥ１［ｋ］およびＥ２［ｋ］上のワイルペアリングを表すものとする。公開鍵（Ｐ，Ｑ）およびメッセージ−署名のペア（ｍ，Ｓ）が与えられる場合、
【０１１５】
【数３２】
0004809598.tif 000033
【０１１６】
であるか調べる（上述したように生成された公開鍵を用いて、受信した署名をベリファイするステージ３１０）。したがって、有効な署名は、以下の式を満たす。
【０１１７】
【数３３】
0004809598.tif 000034
【０１１８】
また、トレースマップ(trace map)は、楕円曲線上の（または、より一般的には任意のアーベル多様体上の）点を削減するために、ベースフィールド(base field)に達するまで使うことができる。言い換えると、楕円曲線（すなわち高次アーベル多様体）上のトレースマップの出力は、より低いフィールド上のデータを使うことによって、拡大フィールド(extension field)上の点の表現を簡略化する方法として使用されることができる。
【０１１９】
複数の楕円曲線を用いた署名
短い署名方式の強度を高めるための別の方法は、複数の公開鍵を使用し、得られる署名を合計することである。この修正形態は、単独で使われることもでき、上で論じたガロア不変量の強化と組み合わされて使われることもできる。
【０１２０】
図４を参照して、それぞれ、メッセージｍを楕円曲線Ｅｉ上の点にマップする、アイソジャニ(isogeny)φｉ：Ｅ→Ｅｉの族、およびランダムオラクルハッシュ関数Ｈｉの族があると仮定する。図３を参照して論じたステージと同様のステージがある。
【０１２１】
公開鍵  ランダムなＰ∈Ｅを取り出し、Ｐ，Ｑ１，Ｑ２，．．．，Ｑｎを公開する（たとえば３０２を参照されたい）。ここで、Ｑｉ＝φｉ（Ｐ）である。
【０１２２】
秘密キー  アイソジャニ(isogeny)φｉのファミリーである。
【０１２３】
署名  各メッセージｍに対して、ｍ（Ｓ）の署名は、
【０１２４】
【数３４】
0004809598.tif 000035
【０１２５】
である（たとえば３０４を参照されたい）。署名付きメッセージは次いで、受信側に送信される（たとえば３０６を参照されたい）。
【０１２６】
検証（ベリファイ）  （メッセージ、署名）のペア（ｍ，Ｓ）が与えられる場合、
【０１２７】
【数３５】
0004809598.tif 000036
【０１２８】
であるか調べる（たとえば、図３を参照して論じたステージ３１０を参照されたい）。有効な署名に対して、この式は、
【０１２９】
【数３６】
0004809598.tif 000037
【０１３０】
なので成り立つ。
【０１３１】
本システムは、少なくとも、ただ１つのアイソジャニ(isogeny)を用いる場合と同程度に安全であると思われる。というのは、複数のアイソジャニ(isogeny)バージョンを破ることができる人は誰でも、複数のアイソジャニ(isogeny)によって定義されるアイソジャニ(isogeny)φ２，．．．，φｎにおいて加算を行うことによって、単一アイソジャニ(isogeny)バージョンを複数のアイソジャニ(isogeny)バージョンに変換することができるからである。さらに、このようなシステムに対して、複数のアイソジャニ(isogeny)バージョンにおいて成功するどの攻撃も、単一(single)アイソジャニ(isogeny)φ１からφｎの全部を同時に破る必要がある。
【０１３２】
アイソジャニ(isogeny)を用いた、アイデンティティに基づく暗号化（ＩＢＥ:identity based encryption）スキーム
図５は、アイソジャニ(isogeny)を用いた、アイデンティティに基づく暗号化（ＩＢＥ）の例示的な方法５００を示す。楕円曲線の間の単方向のアイソジャニ(isogeny)は、アイデンティティに基づく暗号化（ＩＢＥ）スキームを、計算型ディフィ−ヘルマン（ＣＤＨ）に対して安全なものにする可能性がある。ＩＢＥスキームは、以下のように定義することができる。
【０１３３】
点へのマップ(map to point)：何らかの曲線Ｅに対して、演算
【０１３４】
【数３７】
0004809598.tif 000038
【０１３５】
を定義する。より具体的には、Ｈ（ｉｄ）を計算し、点を定義するのに使うことができる。Ｈは、ランダムオラクルのようにふるまうと仮定することができる。あるいは、点およびハッシュＩＤからなるテーブルを、重みからなるランダム文字列中に保持し、重み付けされた和を得ることもできる。信頼できる機関、およびユーザの有限な組が存在し、それぞれが、対応する公開鍵がそこから計算されることができる何らかのＩＤをもつと仮定することもできる。各ユーザは、信頼できる機関(trusted authority)による適切な識別(identification)の後、自分のプライベートキーを入手する。
【０１３６】
信頼できる機関用の公開鍵：α∈Ｅ１、β＝φ（α）である。したがって、信頼できる機関（または受信側など、別のエンティティ）は、公開鍵を提供し公開する（５０２）。ツイストλが使われている場合、α＝λ（ａ）は何らかの点ａのツイストされたイメージであると仮定することができる。
【０１３７】
信頼できる機関用のプライベートキー  効率的に計算可能な
【０１３８】
【数３８】
0004809598.tif 000039
【０１３９】
である。
【０１４０】
たとえば、ボブからアリスへの、暗号化されたデータは、以下のようにして実現されることができる。
【０１４１】
アリス用の公開鍵：Ｔ∈Ｅ２が、たとえば、ｍａｐ−ｔｏ−ｐｏｉｎｔ関数
【０１４２】
【数３９】
0004809598.tif 000040
【０１４３】
を介して、信頼できる機関（または受信側など、別のエンティティ）によって提供される（５０２）。
【０１４４】
アリス用のプライベートキー：
【０１４５】
【数４０】
0004809598.tif 000041
【０１４６】
である。各クライアントごとにプライベートキーを素早く入手するための攻撃は、（上で論じた）署名システムに対するグローバルブレーク(global breeak)と同程度に時間がかかることに留意されたい。その結果、こうしたシステムは、二段システム(two-tier system)と呼ぶことができる。
【０１４７】
ボブによる暗号化  ＡＬＩＣＥ
【０１４８】
【数４１】
0004809598.tif 000042
【０１４９】
を計算する（生成された公開鍵を用いてメッセージを暗号化するステージ５０４）。メッセージをｍとする。ランダム整数ｒを選ぶ。アリスにペア：
【０１５０】
【数４２】
0004809598.tif 000043
【０１５１】
を送信する（５０６）。
【０１５２】
アリスによるデクリプト  暗号文を［ｃ，Ｔ］とする。送信された暗号化されたメッセージは、適切な識別の後、信頼できる機関（または受信側など、別のエンティティ）によって提供された（５１０）プライベートキーを用いてデクリプトされる（５０８）。その結果、クリアテキスト(clear text)は、以下のようになる。
【０１５３】
【数４３】
0004809598.tif 000044
【０１５４】
これは、暗号化ステージにおいてハッシュされる量が
【０１５５】
【数４４】
0004809598.tif 000045
【０１５６】
なので、うまく作用する。
【０１５７】
この量は、デクリプトのステージにおいてハッシュされる量と等しい。アイソジャニ(isogeny)は、以下で説明するように表わすことができる（たとえば、エントリからなるテーブルに関わる、確率的手法を用いる）。
【０１５８】
アイソジャニ(isogeny)の指定
アイソジャニ(isogeny)がスムーズである場合、アイソジャニ(isogeny)は、多項式計算を表す直線プログラムによって与えられる、小さい次数のアイソジャニ(isogeny)の合成として表すことができる。ある実施形態では、対象となっている拡大(extensin)上の曲線に対して、入出力のペアからなる小さいテーブルで十分である。
【０１５９】
【数４５】
0004809598.tif 000046
【０１６０】
を考えると、ｋの有限拡大が考慮されることができ、この拡大は、適切に指定されることができる。一実施形態では、アイソジャニ(isogeny)は、ベースフィールドの何らかの有限拡大上の点からなる群に対するアイソジャニ(isogeny)の動作によって指定される。２つのアイソジャニ(isogeny)は、いくつかの拡大までは一致し得るが、より大きいフィールドでは異なり得ることに留意されたい。したがって、１組の生成元Ｓにおいてφを指定するだけで十分である。概して、群は循環的であり、または上記のように｜Ｓ｜＝２である。生成元をみつけることは容易でないと思われるが、Ｓを無作為に選択することができる。
【０１６１】
より具体的には、アーベル群として、Ｅ（ｋ）（ｋはｑ要素の有限フィールドであることを思い出されたい）はＺ／ｍＺ×Ｚ／ｎＺに対する同形であり、ここで、ｍｎ＝＃Ｅ（ｋ），ｎ｜ｍ、さらにｎ｜Ｄ，Ｄ＝（ｍｎ，ｑ−１）である。ショーフのアルゴリズムを用いてｍｎ＝＃Ｅ（ｋ）を計算することができ、Ｄの因数分解が既知である場合、ｎは、ランダム化多項式時間アルゴリズムを用いて取得することができる。
【０１６２】
【数４６】
0004809598.tif 000047
【０１６３】
および
【０１６４】
【数４７】
0004809598.tif 000048
【０１６５】
は、それぞれオーダがｎおよびｍであることによってどの点も
【０１６６】
【数４８】
0004809598.tif 000049
【０１６７】
と書くことができる場合、エシュロンフォームにおける生成元(generator in echelon form)と呼ばれ、
【０１６８】
【数４９】
0004809598.tif 000050
【０１６９】
アルゴリズムを、その構成に用いることができる。
【０１７０】
無作為選択（エルドス−レーニイ(Erdos-Renyi)）に移り、Ｇを有限アーベル群、ｇ１，．．．，ｇｋをＧのランダム要素とする。
【０１７１】
【数５０】
0004809598.tif 000051
【０１７２】
である場合、部分和がＧにわたってほぼ一様に分散される小さい定数ｃが存在する。具体的には、ｇｉは、Ｇを生成することができる。テーブルの大きさを小さくするために、群オーダ(group order)が素数(prime)であるとき、部分和ではなく重み付けされた部分和の強化を利用することができる。これは、パラメータの少量の損失を伴って、任意のオーダにまで及ぶ。
【０１７３】
さらに、Ｅ（ｋ）の構造は、より詳しい情報を得るのに使われることができる。ランダム点
【０１７４】
【数５１】
0004809598.tif 000052
【０１７５】
を取り出し、そうした点を
【０１７６】
【数５２】
0004809598.tif 000053
【０１７７】
と書くことができる。より具体的には、行列
【０１７８】
【数５３】
0004809598.tif 000054
【０１７９】
が可逆モジュロｍ（ｎ｜ｍであることに留意されたい）である場合、階段生成元をそれぞれ、Ｐｉの一次結合で表すことができる。これが起こると、｛Ｐｉ｝が、群を生成する。
【０１８０】
【数５４】
0004809598.tif 000055
【０１８１】
によって生成される群における、確率（Ｐ１およびＰ２の両方）の低下は、ｍ−２であることに留意されたい。同様に、
【０１８２】
【数５５】
0004809598.tif 000056
【０１８３】
によって生成される群に対する確率は、ｎ−２である。したがって、こうした２つのイベントはいずれも、確率（１−ｍ−２）（１−ｎ−２）＝１＋（＃Ｅ）−２−（ｍ−２＋ｎ−２）では起こらない。
【０１８４】
ハードウェアの実施形態
図６は、本明細書で説明する技術を実施するのに使うことができる、一般的なコンピュータ環境６００を示す。たとえば、コンピュータ環境６００は、先行の図面を参照して論じたタスクの実施に関連づけられた命令を実行するのに使用されることができる。さらに、本明細書において論じる各エンティティ（たとえば、図１、３、および５に関連する、信頼できる当事者、受信側、および／または送信側など）は、それぞれ、一般的なコンピュータ環境へのアクセス権をもつことができる。
【０１８５】
コンピュータ環境６００は、計算機環境の一例に過ぎず、コンピュータおよびネットワークアーキテクチャの使用または機能の範囲に関するどのような限定を示唆することも意図されない。また、コンピュータ環境６００は、例示的なコンピュータ環境６００に示されるコンポーネントのどの１つまたはその組み合わせに関するどのような依存も要件も有していると解釈すべきではない。
【０１８６】
コンピュータ環境６００は、汎用計算デバイスをコンピュータ６０２の形で含む。コンピュータ６０２のコンポーネントは、（任意選択で暗号プロセッサまたはコプロセッサを含む）１つまたは複数のプロセッサまたは処理ユニット６０４と、システムメモリ６０６と、プロセッサ６０４など様々なシステムコンポーネントをシステムメモリ６０６に結合するシステムバス６０８とを含むことができるが、これに限定されない。
【０１８７】
システムバス６０８は、様々なバスアーキテクチャのどれをも使用するメモリバスまたはメモリコントローラ、周辺機器バス、グラフィック専用高速バス、およびローカルバスなどいくつかのタイプのバス構造のいずれかの１つまたは複数を表す。例として、このようなアーキテクチャは、ＩＳＡ（業界標準アーキテクチャ）バス、ＭＣＡ（マイクロチャネルアーキテクチャ）バス、ＥＩＳＡ（拡張ＩＳＡ）バス、ＶＥＳＡ（米国ビデオ電子装置規格化協会）ローカルバス、およびメザニンバスとしても知られるＰＣＩ（周辺装置相互接続）バスを含むことができる。
【０１８８】
コンピュータ６０２は通常、様々なコンピュータ可読媒体を含む。このような媒体は、コンピュータ６０２によってアクセス可能であるとともに揮発性媒体および不揮発性媒体、取外し可能媒体および固定型媒体両方を含む、利用可能などの媒体でもよい。
【０１８９】
システムメモリ６０６は、コンピュータ可読媒体を、ＲＡＭ（ランダムアクセスメモリ）６１０など揮発性メモリ、および／またはＲＯＭ（読出し専用メモリ）６１２など不揮発性メモリの形で含む。ＢＩＯＳ（基本入出力システム）６１４は、たとえば起動中にコンピュータ６０２内部の要素間の情報の転送を助ける基本ルーチンを含み、ＲＯＭ６１２に格納される。ＲＡＭ６１０は一般に、処理ユニット６０４にただちにアクセス可能なかつ／または処理ユニット６０４によって現在操作されるデータおよび／またはプログラムモジュールを含む。
【０１９０】
コンピュータ６０２は、他の取外し可能／固定型、揮発性／不揮発性コンピュータ記憶媒体を含むこともできる。例として、図６は、固定型の不揮発性磁気媒体（図示せず）からの読出しまたはそこへの書込みを行うハードディスクドライブ６１６、取外し可能な不揮発性磁気ディスク６２０（たとえば「フロッピー（登録商標）ディスク」）からの読出しまたはそこへの書込みを行う磁気ディスクドライブ６１８、および、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、または他の光学媒体など取外し可能な不揮発性光ディスク６２４からの読出しまたはそこへの書込みを行う光ディスクドライブ６２２を示す。ハードディスクドライブ６１６、磁気ディスクドライブ６１８、および光ディスクドライブ６２２はそれぞれ、１つまたは複数のデータ媒体インターフェース６２６によって、システムバス６０８に接続される。あるいは、ハードディスクドライブ６１６、磁気ディスクドライブ６１８、および光ディスクドライブ６２２は、１つまたは複数のインターフェース（図示せず）によってシステムバス６０８に接続することができる。
【０１９１】
ディスクドライブおよびそれに関連するコンピュータ可読媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびコンピュータ６０２のための他のデータの不揮発性記憶を実現する。この例はハードディスク６１６、取外し可能な磁気ディスク６２０、および取外し可能な光ディスク６２４を示すが、コンピュータによってアクセス可能なデータを格納することができる他のタイプのコンピュータ可読媒体、たとえば磁気カセットまたは他の磁気記憶装置、フラッシュメモリカード、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光学記憶装置、ＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（読出し専用メモリ）、ＥＥＰＲＯＭ（電気的消去書込み可能読出し専用メモリ）なども、例示的な計算機システムおよび環境を実施するのに使用することができることを理解されたい。
【０１９２】
プログラムモジュール、たとえばオペレーティングシステム６２５、１つまたは複数のアプリケーションプログラム６２８、他のプログラムモジュール６３０、およびプログラムデータ６３２はいくつでも、ハードディスク６１６、磁気ディスク６２０、光ディスク６２４、ＲＯＭ６１２、および／またはＲＡＭ６１０上に格納することができる。このようなオペレーティングシステム６２５、１つまたは複数のアプリケーションプログラム６２８、他のプログラムモジュール６３０、およびプログラムデータ６３２（またはその何らかの組み合わせ）はそれぞれ、分散型ファイルシステムをサポートする常駐コンポーネントの全部または一部を実現することができる。
【０１９３】
ユーザは、キーボード６３４および指示装置６３６（たとえば「マウス」）などの入力装置を介して、コマンドおよび情報をコンピュータ６０２に入力することができる。他の入力装置６３８（具体的には図示せず）は、マイクロホン、ジョイスティック、ゲーム用パッド、衛星パラボラアンテナ、直列ポート、スキャナなどを含み得る。こうしたおよび他の入力装置は、システムバス６０８に結合される入出力インターフェース６４０を介して処理ユニット６０４に接続されるが、他のインターフェースおよびバス構造、たとえば並列ポート、ゲームポート、ＵＳＢ（ユニバーサルシリアルバス）によって接続されることもできる。
【０１９４】
モニタ６４２または他のタイプの表示装置も、ビデオアダプタ６４４などのインターフェースを介してシステムバス６０８に接続されることができる。モニタ６４２に加え、他の出力周辺装置は、入出力インターフェース６４０を介してコンピュータ６０２に接続されることができるスピーカ（図示せず）およびプリンタ６４６などを含み得る。
【０１９５】
コンピュータ６０２は、リモート計算デバイス６４８など１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク接続された環境において動作することができる。例として、リモート計算デバイス６４８は、パーソナルコンピュータ、可搬型コンピュータ、サーバ、ルータ、ネットワークコンピュータ、ピア装置または他の共通ネットワークノード、ゲーム機などでよい。リモート計算デバイス６４８は、コンピュータ６０２に関連して本明細書において説明した要素および特徴の多くまたはすべてを含むことができる可搬型コンピュータとして示される。
【０１９６】
コンピュータ６０２およびリモートコンピュータ６４８の間の論理接続は、ＬＡＮ（ローカルエリアネットワーク）６５０および一般的なＷＡＮ（ワイドエリアネットワーク）６５２として図示してある。このようなネットワーク環境は、会社、企業規模のコンピュータネットワーク、イントラネットおよびインターネットにおいてよく見られる。
【０１９７】
ＬＡＮネットワーク環境において実施する場合、コンピュータ６０２は、ネットワークインターフェースまたはネットワークアダプタ６５４を介してローカルネットワーク６５０に接続される。ＷＡＮネットワーク環境において実施する場合、コンピュータ６０２は通常、モデム６５６、またはワイドネットワーク６５２を介した通信を確立する他の手段を含む。モデム６５６は、コンピュータ６０２の内部にあっても外部にあってもよく、入出力インターフェース６４０または他の適切な機構を介してシステムバス６０８に接続されることができる。図示したネットワーク接続は例示的なものであり、コンピュータ６０２および６４８の間の通信リンク（群）を確立する他の手段も利用されることができることを理解されたい。
【０１９８】
計算機環境６００で示したような、ネットワーク接続された環境では、コンピュータ６０２に関連して図示したプログラムモジュールまたはその一部は、リモートメモリ記憶装置に格納することができる。例として、リモートアプリケーションプログラム６５８は、リモートコンピュータ６４８のメモリ装置に常駐する。説明のために、アプリケーションプログラム、およびオペレーティングシステムなど他の実行可能なプログラムコンポーネントは、本明細書では別個のブロックとして示してあるが、このようなプログラムおよびコンポーネントは、様々な時に計算デバイス６０２の異なる記憶要素に常駐し、コンピュータのデータプロセッサ（群）によって実行されることが理解されよう。
【０１９９】
本明細書では、様々なモジュールおよび技術は、１つまたは複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュールなど、コンピュータ実行可能命令の一般的な状況において説明した。概して、プログラムモジュールは、特定のタスクを実施し、または特定の抽象データタイプを実行するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。一般に、プログラムモジュールの機能は、様々な実施形態において要望に応じて組み合わせ、または分散する、ことができる。
【０２００】
こうしたモジュールおよび技術を実施した結果は、何らかの形のコンピュータ可読媒体に格納することもでき、その媒体を介して伝送することもできる。コンピュータ可読媒体は、コンピュータによってアクセスすることができる利用可能などの媒体でもよい。限定ではなく一例として、コンピュータ可読媒体は、「コンピュータ記憶媒体」および「通信媒体」を含むことができる。
【０２０１】
「コンピュータ記憶媒体(computer storage media)」は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報の格納のためのどの方法でも技術でも実施される揮発性媒体および不揮発性媒体、取外し可能媒体および固定型媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（デジタル多用途ディスク）または他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置または他の磁気記憶装置、あるいは、所望の情報を格納するのに使うことができると共に、コンピュータによってアクセスされることができる他のどの媒体も含むが、それに限定されない。
【０２０２】
「通信媒体(communication media)」は一般に、変調データ信号、たとえば搬送波や他の移送機構中の、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを含む。通信媒体はまた、どの情報配信媒体も含む。「変調データ信号」という用語は、信号に情報を符号化するようなやり方でその特性の１つまたは複数が設定されまたは変更された信号を意味する。限定ではなく例として、通信媒体は、有線ネットワークや直接有線接続などの有線媒体、ならびに音響、ＲＦ（無線周波数）、ＩＲ（赤外線）、Ｗｉ−Ｆｉ（たとえば、ＩＥＥＥ８０２．１１ｂ無線ネットワーク）（無線忠実度）、セルラー、ブルートゥース可能、および他の無線媒体などの無線媒体を含む。上記のどのような組み合わせも、やはりコンピュータ可読媒体の範囲に含まれる。
【０２０３】
結論
上述の通り、構造上の特徴および／または方法における動作について特有の言葉で説明してきたが、特許請求の範囲において定義される本発明は、これまで説明した特定の特徴あるいは動作に限定されない。すなわち、こうした特定の特徴および動作は、本発明を実施するための例示的な具体例として開示したものである。たとえば、本明細書において論じた楕円曲線は、アーベル多様体の一次元の事例である。また、アイソジャニ(isogeny)は、たとえばブラインド署名、階層システムなど、他のアプリケーションでも使うことができる。このように、本明細書において説明した技術は、より高次元のアーベル多様体に適用することができる。
【図面の簡単な説明】
【０２０４】
【図１】暗号システムにおいてアイソジャニを使用した例示的な方法を示す図である。
【図２】２つの曲線の間におけるアイソジャニの例示的なマップを示す図である。
【図３】アイソジャニを用いてメッセージに署名する例示的な方法を示す図である。
【図４】複数の曲線の間におけるアイソジャニの例示的なマップを示す図である。
【図５】アイソジャニを用いたＩＢＥ（アイデンティティに基づく暗号化）の例示的な方法を示す図である。
【図６】本明細書で説明した技術を実施するための、一般的なコンピュータ環境６００を示す図である。
【図１】
0004809598.tif 000057
【図２】
0004809598.tif 000058
【図３】
0004809598.tif 000059
【図４】
0004809598.tif 000060
【図５】
0004809598.tif 000061
【図６】
0004809598.tif 000062