(57)【要約】      （修正有）【課題】消費者が利用可能なコンピュータリソースの増大に対応して、署名を破るために利用することができないように、複数の同種写像を用いて署名を生成し検証するための技法を提供する。【解決手段】一実装形態において、方法は、秘密鍵に含まれる複数の同種写像を利用することによって署名を生成すること、ならびに、その署名および公開鍵を製品に組み込むことを含み、公開鍵は、署名を検証するように構成される。また、複数の同種写像は、楕円曲線上の点を用いてマップされる。【選択図】図５
2006311477.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵に含まれる複数の同種写像を利用することによって署名を生成するステップと、
前記署名、および公開鍵を、製品に組み込むステップとを備え、前記公開鍵は、前記署名を検証するように構成されることを特徴とする方法。
【請求項２】
前記署名、および前記公開鍵は、製品に組み込まれ、前記署名は、前記製品のための製品識別子の少なくとも一部分を形成することを特徴とする請求項１に記載の方法。
【請求項３】
前記複数の同種写像は、楕円曲線Ｅ１上の点を、楕円曲線Ｅ２上の点にマップし、前記秘密鍵は、
前記楕円曲線Ｅ１と、
Ｅ１上の２つの有限点であるＰ，Ｑとをさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
前記公開鍵は、楕円曲線Ｅ１上の点において評価される、有限体と、楕円曲線Ｅ２と、ペアリング関数と、前記複数の同種写像を適用の像とを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記像は、楕円曲線Ｅ２上の点であることを特徴とする請求項１に記載の方法。
【請求項６】
前記署名は、楕円曲線加算、および同種写像加算を利用して計算されることを特徴とする請求項１に記載の方法。
【請求項７】
前記計算は、式：
【数１】
2006311477.tif 000007
を用いて実行され、上式において、「σ」は、署名であり、Φ１からΦｔは、前記秘密鍵における前記同種写像であり、前記署名は、同種である（ｉｓｏｇｅｎｏｕｓ）楕円曲線Ｅ２上の点であることを特徴とする請求項６に記載の方法。
【請求項８】
前記公開鍵は、前記複数の同種写像を楕円曲線上の点に適用した複数の結果を含むことにより、前記署名を検証するように構成されることを特徴とする請求項１に記載の方法。
【請求項９】
前記検証は、式：
ｅ２（σ，ｍ１Φ１（Ｑ）＋…＋ｍｔΦｔ（Ｑ））＝ｅ１（Ｐ，Ｑ）
が真であるかどうかを決定することを含み、上式において、ｅ１およびｅ２は、ペアリング関数であり、ＰおよびＱは、楕円曲線Ｅ１上の点であり、ｍ１からｍｔは、メッセージ「ｍ」を形成する整数値であることを特徴とする請求項８に記載の方法。
【請求項１０】
署名を受け取るステップと、
複数の同種写像を楕円曲線上の点に適用した複数の結果を有する公開鍵を利用して、前記署名を検証するステップとを備えることを特徴とする方法。
【請求項１１】
前記署名、および前記公開鍵は、製品に含まれることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記製品は、コンピュータ可読媒体であることを特徴とする請求項１１に記載の方法。
【請求項１３】
検証するステップは、式：
ｅ２（σ，ｍ１Φ１（Ｑ）＋…＋ｍｔΦｔ（Ｑ））＝ｅ１（Ｐ，Ｑ）
が真であるかどうかを決定するステップを含み、上式において、ｅ１およびｅ２は、ペアリング関数であり、ＰおよびＱは、楕円曲線Ｅ１上の点であり、ｍ１からｍｔは、メッセージ「ｍ」を形成する整数値であることを特徴とする請求項１０に記載の方法。
【請求項１４】
前記メッセージ「ｍ」は、前記署名を生成するために利用されることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記署名は、秘密鍵に含まれる複数の同種写像を利用することにより生成されることを特徴とする請求項１０に記載の方法。
【請求項１６】
前記複数の同種写像は、楕円曲線Ｅ１上の点を、楕円曲線Ｅ２上の点にマップし、前記秘密鍵は、
前記楕円曲線Ｅ１と、
Ｅ１上の２つの有限点であるＰ，Ｑとをさらに含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
前記署名は、式：
【数２】
2006311477.tif 000008
を使用して生成され、上式において、「σ」は、前記署名であり、Φ１からΦｔは、秘密鍵における同種写像であり、前記署名は、同種である楕円曲線Ｅ２上の点であることを特徴とする請求項１０に記載の方法。
【請求項１８】
署名と、
複数の同種写像を楕円曲線上の点に適用することにより得た複数の結果を有する公開鍵と、
前記公開鍵を使用して前記署名を検証するために実行可能な１つまたは複数のモジュールとを備えることを特徴とするコンピュータ可読媒体。
【請求項１９】
クライアント上でのインストールおよび実行のための少なくとも１つの他のモジュールをさらに備え、前記１つまたは複数のモジュールは、前記署名の前記検証の結果に基づいて前記少なくとも１つの他のモジュールをインストールするかどうかを決定するために実行可能であることを特徴とする請求項１８に記載のコンピュータ可読媒体。
【請求項２０】
前記署名は、秘密鍵に含まれる複数の同種写像を利用して生成されることを特徴とする請求項１８に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、署名に関し、より詳細には、同種写像ベースの署名（ｉｓｏｇｅｎｙ−ｂａｓｅｄ  ｓｉｇｎａｔｕｒｅ）に関する。
【背景技術】
【０００２】
製品の偽造および海賊行為の問題はかつてなく増大しており、製品の製造業者だけでなく海賊版の製品の消費者にも影響を及ぼしている。例えば、ツールなどのコピーして作られた製品は、コピー元の製品と等価な品質を有するように作られていないことがある。したがって、コピー製品は、消費者の意図する用途に適切でないことがある。この問題がさらに複雑になるのは、消費者がその製品を真正であると信じている場合に、製造業者の商品の品質について誤った印象を消費者に与えるときである。他の例では、製品が、ソフトウェアのコピーされたバージョンの場合である。しかし、そのソフトウェアは、真正でないため、真正のバージョンのソフトウェアで利用可能な、ソフトウェア自体に含まれる機能やソフトウェアの製造業者により提供される更新に対するアクセスなどソフトウェアのすべての機能を利用することはできない。
【０００３】
製品の偽造および海賊行為を制限するために用いられる技法の１つは、署名の使用である。署名は、例えば、数学的技法を用いて生成することができる。署名を検査するために、署名にある数学的特性が存在するかどうかを識別するために署名が処理される。一般に、その数学的特性が存在する場合、署名は有効である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、消費者が使用できるコンピューティングリソースの量が増大し続けるのに伴い、かつてなく増大している使用可能なコンピュータリソースを、署名を「破る（ｂｒｅａｋ）」ために利用することができないように、このような増大に対応し署名を生成し検証するための改良された技法を開発する必要がある。
【課題を解決するための手段】
【０００５】
署名を生成し検証するための技法を説明する。一実装形態において、方法は、秘密鍵に含まれる複数の同種写像を利用し、署名、および公開鍵を製品に組み込むことにより署名を生成することを含み、公開鍵は、署名を検証するように構成される。
【０００６】
他の実装形態では、方法は、署名を受け取ること、および、複数の同種写像を楕円曲線上の点に適用した複数の結果を有する公開鍵を利用する署名を検証することを含む。
【０００７】
さらなる実施形態では、コンピュータ可読媒体が、署名と、複数の同種写像を楕円曲線上の点に適用することにより得られた複数の像を有する公開鍵と、公開鍵を用いて署名の検証を実行することができる１つまたは複数のモジュールとを含む。
【発明を実施するための最良の形態】
【０００８】
事例の説明において、同様の構造および構成要素を参照するために、同じ参照番号が使用されている。
【０００９】
概要
署名を生成し検証するための技法を説明する。署名は、例えばメッセージの送信者およびドキュメントの署名者のＩＤの認証などの様々な用途に使用することができる。例えば、署名は、プロダクトＩＤとも呼ばれる製品識別子（ＰＩＤ）の全部または部分として構成することができる。次いで、製品識別子は、対応する製品が「真正（ａｕｔｈｅｎｔｉｃ）」であるかどうかを決定するために使用することができる。例えば、ソフトウェア開発者は、コンピュータ実行可能命令（例えばアプリケーション）を、ＣＤ−ＲＯＭなどのコンピュータ可読媒体に書き込むことができる。ソフトウェア開発者は、数学的技法を用いて生成された署名を含むＰＩＤを、ＣＤ−ＲＯＭ上に含めることができる。
【００１０】
ユーザがアプリケーションをコンピュータにインストールしようとするとき、インストレーションプロセス（ｉｎｓｔａｌｌａｔｉｏｎ  ｐｒｏｃｅｓｓ）は、ＰＩＤを用いてソフトウェアが真正であるかどうかを決定するための検査を含むことができる。例えば、インストレーションプロセスは、ＰＩＤ、より具体的にはＰＩＤ内の署名が、特定の数学的特性を示しているかどうかを決定することができる。それが示されていると決定した場合、アプリケーションは真正であると見なされ、インストレーションプロセスが続行される。そうでない場合、アプリケーションの不正なコピーのインストールを防止するためにインストレーションプロセスは終了する。他の様々な技法が、署名と関連して利用されてもよく、それらについては、以下で図面に関連してさらに論じる。
【００１１】
以下の議論では、まず、署名の生成および検証のための技法を利用することができる例示的環境について説明する。次いで、例示的環境ならびに他の環境で実施可能な例示的手順について説明する。本説明において、同様の構造および構成要素を参照する場合、同じ参照番号が使用される。
【００１２】
例示的環境
図１は、署名の生成および検証のための技法を利用して動作可能な例示的実装形態における環境１００を示す。例示的環境１００は、製品プロバイダ１０２と、複数のクライアント１０４（ｌ）、…、１０４（ｎ）、…、１０４（Ｎ）と、製品ディストリビュータ（ｄｉｓｔｒｉｂｕｔｏｒ）１０６を含む。製品プロバイダ１０２は、さらに、複数のクライアント１０４（ｌ）〜１０４（Ｎ）に配布するための複数の製品１０８（ｍ）（ただし、「ｍ」は、１から「Ｍ」までの任意の整数値とすることができる）を含むものとして例示されている。製品１０８（ｍ）は、様々な方法で構成することができる。例えば、１つまたは複数の製品１０８（ｍ）は、物理アイテム（ｐｈｙｓｉｃａｌ  ｉｔｅｍ）（例えば、製造品で、コンピュータ実行可能命令を有するコンピュータ可読媒体）、ならびに、電子コンテンツ（例えば、ダウンロード可能な歌曲、ソフトウェア、およびデジタルフォト（ｄｉｇｉｔａｌ  ｐｈｏｔｏ））などとして構成することができる。
【００１３】
次いで、製品１０８（ｍ）は、配布のために、デリバリチャネル（ｄｅｌｉｖｅｒｙ  ｃｈａｎｎｅｌ）１１０を介して製品ディストリビュータ１０６に送ることができる。例えば、デリバリチャネル１１０は、製品ディストリビュータ１０６への製品１０８（ｍ）の物理的送達、例えば、製造プラントから現実世界の（ｂｒｉｃｋｓ−ａｎｄ−ｍｏｒｔａｒ）店への物理的移送を表す。他の例では、デリバリチャネル１１０は、製品１０８（ｍ）の電子的に伝達するためのネットワークなどの通信チャネルとして構成することができる。次いで、製品ディストリビュータ１０６は、製品１０８（ｍ）を、複数のクライアント１０４（ｌ）、１０４（ｎ）、１０４（Ｎ）に、それぞれ配布チャネル１１２（ｌ）、１１２（ｎ）、１１２（Ｎ）を介して配布することができ、これらのチャネルは、例えば、物理、ネットワークなどの配布チャネル１１０と同じであっても異なっていてもよい。
【００１４】
前述のように、製品の不正なコピーに対する懸念は、かつてなく高まっている。したがって、製品プロバイダ１０２は、複数の製品のそれぞれについて署名１１６（ｍ）を生成するために、署名システム１１４を利用することができる。一実装形態では、各製品１０８（ｍ）は、互いに異なる複数の署名１１６（ｍ）のうちの対応する１つを有する。それぞれ異なる製品グループごとの署名をグループ化するなど他の様々な実装形態も企図される。
【００１５】
署名システム１１４は、署名１１６（ｍ）の生成、および／または署名１１６（ｍ）の検査を実行することができる署名モジュール１１８を含むものとして示されている。例えば、署名モジュール１１８は、署名１１６（ｍ）が有効であるかどうかを決定するために利用され得る試験に各署名１１６（ｍ）が合格するように、署名１１６（ｍ）を生成することができ、したがって、署名１１６（ｍ）は、悪意のあるパーティによって生成されない。
【００１６】
署名１１６（ｍ）の検査は、様々な方法で実行することできる。例えば、製品プロバイダ１０２と通信することなく署名１１６（ｍ）が有効であるかどうかを決定するための技法が、複数のクライアント１０４（ｌ）〜１０４（Ｎ）それぞれに提供される。この例では、このような検査は、製品プロバイダ１０２との通信結合を必要としないため、「オフライン」で実行することができる。他の例では、クライアント１０４（ｌ）、１０４（ｎ）、１０４（Ｎ）のうち１つまたは複数が、製品プロバイダ１０２に署名１１６（ｍ）を伝達することができ、そうすることにより、製品プロバイダ１０２は、その署名が有効であるかどうかを決定することができる。例えば、クライアント１０４（ｎ）は、アプリケーションとして構成されている製品１０８（ｍ）に対するソフトウェアの更新を受け取ることを求めることができる。したがって、クライアント１０４（ｎ）は、対応する署名１１６（ｍ）を、（例えば、インターネット、電話などを介して）製品プロバイダ１０２に伝達することができる。次いで、製品プロバイダ１０２は、クライアント１０４（ｎ）が、「有効」（すなわち真正）なバージョンを有しているかどうかを決定することができ、それから、更新を受け取ることを許可する。さらに他の例では、検査は、製品プロバイダ１０２またはクライアント１０４（ｌ）〜１０４（Ｎ）以外の、スタンドアロンの検査サービスなど他のエンティティによって実行することができる。署名１１６（ｍ）の生成および検査については、図２に関連してさらに論じる。
【００１７】
一般に、本明細書に記載の任意の機能は、ソフトウェア、ファームウェア（例えば、固定論理回路）、手動処理、またはこれらの実装の組合わせを用いて実装することができる。本明細書で使用される用語「モジュール」および「論理（ｌｏｇｉｃ）」は、一般に、ソフトウェア、ファームウェア、または、ソフトウェアとファームウェアの組合わせを表す。ソフトウェアで実装する場合には、モジュール、機能、または論理は、プロセッサ（例えば、１つまたは複数のＣＰＵ）で実行されるときに指定されたタスクを実行するプログラムコードを表す。プログラムコードは、１つまたは複数のコンピュータ可読メモリデバイスに格納することができ、これについては、図２に関連してさらに説明する。以下で説明する生成および検証の技法の機能は、プラットフォーム独立であり、つまり、これらの技法は、様々なプロセッサを有する市販の様々なコンピューティングプラットフォーム上で実装することができる。
【００１８】
図２は、図１の製品プロバイダ１０２およびクライアント１０４（ｎ）をより詳細に示す例示的実装形態におけるシステム２００を示す図である。製品プロバイダ１０２は、複数の署名サーバ２０２（ｓ）（「ｓ」は、１から「Ｓ」までの任意の整数値とすることができる）を含むものとして示され、クライアント１０４（ｎ）は、クライアントデバイスとして示されている。クライアント１０４（ｎ）は、様々な異なるデバイスとして構成することができる。例えば、クライアント１０４（ｎ）は、デスクトップコンピュータなどのコンピューティングデバイス、モバイルステーション、娯楽機器（ｅｎｔｅｒｔａｉｎｍｅｎｔ  ａｐｐｌｉａｎｃｅ）、ディスプレイデバイスに通信結合されたセットトップボックス、無線電話、および、ゲームコンソールなどとして構成することができる。したがって、クライアント１０４（ｎ）は、十分なメモリとプロセッサ（ｐｒｏｃｅｓｓｏｒ）リソースを備えたフルリソース（ｆｕｌｌ  ｒｅｓｏｕｒｃｅ）のデバイス（例えば、パーソナルコンピュータ、ゲームコンソール）から、限られたメモリおよび／またはプロセッシング（ｐｒｏｃｅｓｓｉｎｇ）リソースを備えたローリソース（ｌｏｗ−ｒｅｓｏｕｒｃｅ）のデバイス（例えば、従来のセットトップボックス、ハンドヘルドゲームコンソール）にまで及び得る。以下の議論では、クライアント１０４（ｎ）は、クライアントを操作する人物および／またはエンティティにも関連付けられることがある。すなわち、クライアント１０４（ｎ）は、ユーザ、ソフトウェア、および／またはデバイスを含む論理クライアントを表すこともある。
【００１９】
署名サーバ２０２（ｓ）、およびクライアント１０４（ｎ）は、それぞれのプロセッサ２０４（ｏ）、２０６（ｎ）、および、それぞれのメモリ２０８（ｏ）、２１０（ｎ）を含むものとして示されている。プロセッサは、プロセッサを形成している材料、あるいは、プロセッサで用いられる処理メカニズムによって限定されない。例えば、プロセッサは、半導体および／またはトランジスタ（例えば、電子集積回路（ＩＣ））から成ることが可能である。この文脈では、プロセッサ実行可能命令は、電子的に実行可能な命令とすることができる。あるいは、プロセッサのメカニズムまたはプロセッサのためのメカニズム、したがって、コンピューティングデバイスのメカニズムまたはそのためのメカニズムには、これらに限定されないが、量子コンピューティング、光コンピューティング、および、（例えばナノテクノロジを用いた）メカニカルコンピューティング（ｍｅｃｈａｎｉｃａｌ  ｃｏｍｐｕｔｉｎｇ）などが含まれ得る。さらに、署名サーバ２０２（ｓ）およびクライアント１０４（ｎ）で用いるために、それぞれ、単一のメモリ２０８（ｏ）および２１０（ｎ）が示されているが、例えば、ＲＡＭ（ランダムアクセスメモリ）、ハードディスクメモリ、およびリムーバル媒体メモリなどの非常に様々なタイプおよび組合わせのメモリを用いることができる。
【００２０】
署名モジュール１１８は、プロセッサ２０４（ｏ）上で実行されるものとして例示されており、メモリ２０８（ｏ）に格納可能である。署名モジュール１１８はまた、署名生成モジュール２１２、および署名検証モジュール２１４を含むものとして例示されている。署名生成モジュール２１２は、署名を生成するための機能を代表して示すものである。署名検証モジュール２１４は、署名の真正性を検査して、署名生成モジュール２１２、または、許可されたサードパーティなどの署名を生成するための独自仕様の技法を利用するエンティティによって、署名が生成されたかどうかの見込みを決定するための機能を代表して示すものである。
【００２１】
署名生成モジュール２１２は、署名１１６（ｍ）の生成を実行することができ、この署名は、署名検証モジュール２１４によって行われる試験に合格する。このとき、署名検証モジュールは、署名１１６（ｍ）が有効であるかどうか、したがって悪意のあるパーティによって生成されたものではないかどうかを決定するために使用される。署名１１６（ｍ）は、コンピュータ可読媒体として構成される製品１０８（ｍ）に含まれるプロダクトＩＤ２１６（ｍ）に含まれるものとして例示されている。製品１０８（ｍ）（すなわち、コンピュータ可読媒体）はまた、クライアント１０４（ｎ）に配布するための（署名１１６（ｍ）、およびプロダクトＩＤ２１６（ｍ）に対応している）アプリケーション２１８（ｍ）を含むものとして例示されている。したがって、この例における製品１０８（ｍ）は、アプリケーション２１８（ｍ）、および／またはアプリケーション２１８（ｍ）を含むコンピュータ可読媒体であると見なすことができる。
【００２２】
プロダクトＩＤ２１６（ｍ）は、一般に、文字および／または番号を使用して表される。署名１１６（ｍ）をシーケンス番号に変換して数学的アルゴリズムを適用することにより、エンティティ（例えば、クライアント１０４（ｎ）および／または製品プロバイダ１０２）はプロダクトＩＤ２１６（ｍ）を検査し、その検査により、署名１１６（ｍ）の生成のために利用される技法を使用しているエンティティ（例えば、図１の署名システム１１４）によってシーケンス番号つまり署名１１６（ｍ）が生成されたかどうかを決定することができるように、プロダクトＩＤ２１６（ｍ）を構成することができる。
【００２３】
署名１１６（ｍ）を生成するために、様々な技法を用いることができる。例えば、署名サーバ２０２（ｓ）は、秘密鍵２２０、公開鍵２２２、および、メモリ２０８（ｏ）に格納されるメッセージ２２６（ｋ）のデータベース２２４（「ｋ」は、１から「Ｋ」までの任意の整数値とすることができる）を含むものとして示されている。署名生成モジュール２１２は、複数の署名１１６（ｍ）を生成するために、秘密鍵２２０を使用して、複数のメッセージ２２６（ｋ）の処理を実行することができる。つまり、署名生成モジュール２１２は、署名１１６（ｍ）を得るために、メッセージ２２６（ｋ）に「変換（ｔｒａｎｓｆｏｒｍａｔｉｏｎ）」を施す。署名を生成するためのメッセージ２２６（ｋ）の処理については、図３に関連してさらに論じる。
【００２４】
例示では、製品プロバイダ１０２は、署名生成モジュール２１２を実行して署名１１６（ｍ）を生成するソフトウェア製造業者である。署名生成モジュール２１２は、特定の数学的特性を有する技法を利用して署名を生成する。次いで、署名１１６（ｍ）は、製品１０８（ｍ）上のプロダクトＩＤ２１６（ｍ）の少なくとも一部分として含まれる。図２の実装形態における製品１０８（ｍ）は、製品ディストリビュータ１０６を介してクライアント１０４（ｎ）に配布されるコンピュータ可読媒体であり、クライアント１０４（ｎ）にインストールするためのアプリケーション２１８（ｍ）、および、公開鍵２２２（ｍ）として例示されるあるバージョンの公開鍵を含む。製品のクライアントバージョンは、製品１０８（ｎ）として示され、プロダクトＩＤ２１６（ｎ）、および署名１１６（ｎ）を含む。
【００２５】
署名検証モジュール２１４は、署名生成モジュール２１２によって生成された署名１１６（ｍ）の検査を実行することができる。例えば、署名検証モジュール２１４は、製品１０８（ｍ）に含まれる公開鍵２２２（ｍ）を使用し署名１１６（ｍ）を処理して、２つの回答、すなわち、（１）はい、署名１１６（ｍ）は有効です、または、（２）いいえ、署名１１６（ｍ）は有効ではありません、のうち一方を得ることができる。これらの回答は、署名１１６（ｍ）が特定の数学的特性を示しているかどうかに基づいて行われ、これについては図４に関連してさらに論じる。一実装形態では、公開鍵２２２は、署名を生成していない他のエンティティが署名１１６（ｍ）を検査することができるように公開されるが、秘密鍵２２０は、秘密のままにされるので、他のエンティティは、特定の数学的特性を有する署名を生成することができない。
【００２６】
上述の例を続けると、例えば、クライアント１０４（ｎ）は、アプリケーション２１８（ｎ）についての更新を受け取ることを所望することがある。クライアント１０４（ｎ）がソフトウェアの許可されたコピーを有することを「証明する」ために、クライアント１０４（ｎ）は、プロダクトＩＤ２１６（ｎ）を製品プロバイダ１０２に供給する。次いで、製品プロバイダ１０２は、署名検証モジュール２１４を実行し、検証技法を利用して、プロダクトＩＤ２１６（ｎ）、より詳細には署名１１６（ｎ）が、特定の数学的特性を示しているかどうかを決定することができる。特定の数学的特性が示されていると決定した場合、プロダクトＩＤ２１６（ｎ）は、「本物」と見なされ、クライアント１０４（ｎ）は、更新を受け取ることを許可される。製品プロバイダ１０２が署名検証モジュール２１４を実行することによって行われる検証について説明したが、検証は、クライアント１０４（ｎ）上の署名検証モジュール２１４（ｎ）、ならびに、前述のサードパーティの検査機構（ｖｅｒｉｆｉｅｒ）の実行によって行われてもよい。
【００２７】
秘密鍵２２０、および公開鍵２２２は、生成および検査技法を提供するための様々な方法で構成することができる。例えば、これらの技法は、同種写像に基づくことが可能であり、以下の例では、複数の楕円曲線間でのマッピングとして構成される。生成された同種写像は、署名を提供するために、単一の曲線の代わりに複数の曲線を使用することが可能である。これらの技法は、（例えば、ユーザによってタイプ入力される、または、低バンド幅チャネルを介して送信される）比較的短いデジタル署名、および、暗号化（例えば、記憶可能な公開鍵を可能にするＩＢＥ（アイデンティティベース暗号化（ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ））ソリューション）などに適用することができる。
【００２８】
例えば、公開鍵２２２は、有限体（ｆｉｎｉｔｅ  ｆｉｅｌｄ）、楕円曲線、および、以下のように表すことができるペアリング関数（ｐａｉｒｉｎｇ  ｆｕｎｃｔｉｏｎ）を含むことができる。
【００２９】
有限体であるＫと、
Ｋ上の楕円曲線であるＥ２と、
Ｅ２上の点のペアをＫの非ゼロ要素（ｅｌｅｍｅｎｔ）にマップするペアリング関数。
【００３０】
秘密鍵２２０は、以下の情報を含む：
やはりＫ上の楕円曲線であり、Ｅ２に対し同種（ｉｓｏｇｅｎｏｕｓ）（場合によっては同じ）である（つまりＥ１とＥ２は群の位数が同じであることが示唆される）Ｅ１と、
Ｅ１上の点のペアをＫの非ゼロ要素にマップするペアリング関数ｅ１と、
Ｅ１上の２つの有限点（ｆｉｎｉｔｅ  ｐｏｉｎｔ）であるＰ，Ｑと、
複数の同種写像（Φ１，…，Φｔ）。
【００３１】
複数の各同種写像（Φ１，…，Φｔ）は、楕円曲線Ｅ１上の点を、楕円曲線Ｅ２上の点にマップする。２２０および２２２におけるペアリング関数ｅ１およびｅ２は、Φ：Ｅ１→Ｅ２が同種写像の場合にＥ１上のすべてのＰ１，Ｑ１についてｅ２（Φ（Ｐ１），Φ（Ｑ１））＝ｅ１（ｄｅｇ（Φ）Ｐ１，Ｑ１）となるように選ばれる。整数値ｄｅｇ（Φ）は、ｄｅｇ（Φ）の次数（ｄｅｇｒｅｅ）であり、ｄｅｇ（Φ）Ｐ１は、曲線Ｅ１上での楕円曲線スカラー倍算（ｓｃａｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）を意味する。検査を提供するために、公開鍵２２２はまた、Ｑに対する複数の同種写像の適用の結果情報を含み、この情報は次のように表すことができる。
Φ１（Ｑ），Φ２（Ｑ），Φ３（Ｑ），…，Φｔ（Ｑ）
【００３２】
これらの各像は、Ｅ２上の点である。公開鍵２２２は、体Ｋの要素であるｅ１（Ｐ，Ｑ）の値を含むこともできる。したがって、この例における公開鍵は、署名が特定の数学的特性を示すことを検査するために利用することができ、この場合、その数学的特性を示す追加の署名を生成するために公開鍵を使用することができる必要がない。これについては、以下で図面に関連してさらに論じる。
【００３３】
例示的手順
以下の議論では、前述のシステムおよびデバイスを利用して実装することができる生成および検査技法を説明する。各手順の態様は、ハードウェア、ファームウェア、ソフトウェア、またはそれらの組合せとして実装することができる。この手順は、１つまたは複数のデバイスによって行われる動作を規定する一連のブロックとして示されるが、各ブロックの動作を行う順序は、示されている順序に必ずしも限定されない。以下の説明のいくつかの部分では、図１の環境１００、および図２のシステム２００を参照する。
【００３４】
図３は、同種写像ベースの技法を用いて署名が生成される例示的実装形態における手順３００を示す流れ図である。メッセージ「ｍ」が受け取られる（ブロック３０２）。このメッセージは、様々な方法で、例えば、乱数ジェネレータ、および、対応する製品の特性を指定する記述文字列（ｄｅｓｃｒｉｐｔｉｖｅ  ｓｔｒｉｎｇ）などから受け取ることができる。
【００３５】
署名生成モジュール２１２により、メッセージ「ｍ」は、下記のように表すことができる整数値のリストと見なされる。
ｍ１，ｍ２，ｍ３，…，ｍｔ
【００３６】
例えば、整数値のリストは、前述の乱数ジェネレータ、および、変換された英数字文字列などから得ることができる。
【００３７】
次いで、署名「σ」が、秘密鍵２２０を用いてメッセージ「ｍ」から生成される（ブロック３０４）。例えば、署名「σ」は、秘密鍵２２０から得た情報を使用した楕円曲線加算（ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ａｄｄｉｔｉｏｎ）、および同種写像加算（ｉｓｏｇｅｎｙ  ａｄｄｉｔｉｏｎ）を含む、同種写像技法を利用して計算することができ、この例は、次式（ＳＩＧＭＡ）
【００３８】
【数１】
2006311477.tif 000003
【００３９】
で示される。したがって、上式に示すように、まとまってメッセージｍを形成する各整数値（例えば、ｍ１，ｍ２，ｍ３，…，ｍｔ）は、秘密鍵２２０の対応する同種写像関数（例えば、Φ１，Φ２，Φ３，…，Φｔ）と乗算される。さらに、署名は、楕円曲線Ｅ２上の点である。上式では、分子は、楕円曲線の加算を利用して計算され、分母は、同種写像加算を利用して得られた量の次数として計算される。
【００４０】
例えば、前述のように、Φ１，Φ２，Φ３，…，Φｔは、同種写像であり、それは次数と呼ばれる数学的特性を有する。整数値と乗算した同種写像は、同種写像である。さらに、同じペアの曲線の間での２つ以上の同種写像が追加されたとき、その結果もまた同種写像である。したがって、対応する整数値（例えば、ｍ１，ｍ２，ｍ３，…，ｍｔ）と乗算したΦ１，Φ２，Φ３，…，Φｔの結果の加算は、同種写像であり、「同種写像加算」を用いて計算される。分子では、Ｅ２上の楕円曲線点（同種写像の像（ｉｓｏｇｅｎｉｃ  ｉｍａｇｅｓ））Φ１（Ｐ），Φ２（Ｐ），Φ３（Ｐ），…，Φｔ（Ｐ）を対応する整数値（例えば、ｍ１，ｍ２，ｍ３，…，ｍｔ）と乗算するために、楕円曲線加算が用いられる。署名「σ」は、秘密鍵２２０を知ることなく計算することができないことに留意されたい。例えば、メッセージに署名するために、整数値（例えば、ｍ１，ｍ２，ｍ３，…，ｍｔ）は知られているが、同種写像（例えば、Φ１，Φ２，Φ３，…，Φｔ）、およびＰにおけるそれらの像は、この例では、秘密鍵２２０だけに排他的に含まれている。σの分母における次数は、整数値であり、除算は、共通の群の位数（ｃｏｍｍｏｎ  ｇｒｏｕｐ  ｏｒｄｅｒ）｜Ｅ１｜＝｜Ｅ２｜を法として分母を逆にすることによって行われる。
【００４１】
次いで、生成された署名１１６（ｍ）、および（公開鍵２２２（ｍ）として例示される）公開鍵２２２の１つのバージョンは、製品１０８（ｍ）に組み込まれ（ブロック３０６）、製品は、クライアント１０４（ｎ）に配布される（ブロック３０８）。例えば、生成された署名１１６（ｍ）は、コンピュータ実行可能コード、例えばアプリケーション２１８（ｍ）を含むコンピュータ可読媒体（例えばＣＤ−ＲＯＭ）に組み込まれる。次いで、生成された署名１１６（ｍ）は、コンピュータ可読媒体が真正であることを検査するために利用されるが、これについては、以下で図面に関連してさらに論じる。
【００４２】
図４は、図３の手順３００によって生成された署名１１６（ｍ）が、署名１１６（ｍ）を有する製品１０８（ｍ）にも含まれる図２の公開鍵２２２（ｍ）を用いて検査される、例示的実装形態における手順４００を示す流れ図である。クライアント１０４（ｎ）は、署名「σ」および公開鍵２２２（ｍ）を含む製品（例えば、前述のコンピュータ可読媒体）を受け取る（ブロック４０２）。例えば、クライアントは、コンピュータ可読媒体を、店舗で、あるいはインターネットを介するなどして購入することができる。次いで、受け取られた製品は、ローカルでクライアントに利用可能であり、図２では、製品１０８（ｎ）、アプリケーション２１８（ｎ）、公開鍵２２２（ｎ）、プロダクトＩＤ２１６（ｎ）、および署名１１６（ｎ）として示される。
【００４３】
次いで、モジュール（例えば、署名検証モジュール２１４（ｎ））は、コンピュータ可読媒体に組み込まれている生成された署名が、有効であることを検査するために実行される（ブロック４０４）。例えば、署名検証モジュール２１４（ｎ）は、アプリケーション２１８（ｍ）のインストレーションモジュール（ｉｎｓｔａｌｌａｔｉｏｎ  ｍｏｄｕｌｅ）の一部分として含まれ得る。したがって、アプリケーション２１８（ｍ）をインストールするために、インストレーションモジュールは、署名検証モジュール２１４（ｎ）を開始して、ユーザによって入力された署名１１６（ｍ）が有効であるかどうかを決定する。例えば、署名検証モジュール２１４（ｎ）は、実行されたとき、公開鍵を利用して、下記の式が真であるかどうかを決定することができる（判断ブロック４０６）。
ｅ２（σ，ｍ１Φ１（Ｑ）＋ｍ２Φ２（Ｑ）＋…＋ｍｔΦｔ（Ｑ））＝ｅ１（Ｐ，Ｑ）
【００４４】
前述のように、体の要素ｅ１（Ｐ，Ｑ）は、像Φ１（Ｑ），Φ２（Ｑ），…，Φｔ（Ｑ）と同様に、公開鍵に含まれる。上述の関係が真である場合（判断ブロック４０６で「はい」の場合）、署名１１６（ｍ）は、有効である（ブロック４０８）。上述の関係が真でない場合（判断ブロック４０６で「いいえ」の場合）、署名１１６（ｍ）は、無効である（ブロック４１０）。次いで、検証の結果は、署名検証モジュールにより、ユーザインターフェースなどを介して、アプリケーション２１８（ｍ）のインストールを担当するインストレーションモジュールなどに出力される（ブロック４１２）。例えば、検査の結果は、署名が有効であることをクライアント１０４（ｎ）に通知するために使用することができ、したがって、署名を有する対応する製品のためのソフトウェアの更新を得ることができる。この検査は、他の様々な理由で実行され得るが、これについては図５に関連してさらに論じる。
【００４５】
したがって、上述の式に示されるように、検査は、署名、メッセージ、および公開鍵を使用して実行することができる。したがって、公開鍵を有する任意のクライアントは、署名が有効であるかどうか検査することができるが、秘密鍵２２０を知ることなく新しい署名を生成することはできない。
【００４６】
σを、式（ＳＩＧＭＡ）で定義されるような楕円曲線Ｅ２上の点とする。下記は、検査技法の証明（ｐｒｏｏｆ）を示す。
【００４７】
【数２】
2006311477.tif 000004
【００４８】
上式は、次のように簡略化することができる。
【００４９】
【数３】
2006311477.tif 000005
【００５０】
Φ＝ｍ１Φ１＋ｍ２Φ２＋…＋ｍｔΦｔとする。これは、Ｅ１からＥ２への同種写像である。上式は、公開鍵および秘密鍵２２０、２２２について前に述べた等式および記載の関係を使用して次のようになる。
ｅ２（σ，Φ（Ｑ））＝ｅ２（Φ（Ｐ）／ｄｅｇ（Φ），Φ（Ｑ））＝ｅ２（Φ（Ｐ／ｄｅｇ（Φ）），Φ（Ｑ））＝ｅ１（Ｐ，Ｑ）
【００５１】
ｅ１（Ｐ，Ｑ）は、署名１１６（ｍ）を検査するために利用された公開鍵２２２に含まれる式の１つであることは明らかであろう。したがって、署名１１６（ｍ）は、秘密鍵を使用せずに検査することができる。
【００５２】
公開鍵を選択する際に、異なるメッセージが異なる署名を生成するように、同種写像を選ぶことができる。これは、点Φｉ（Ｑ）の非自明の小さい線型結合が０でないことを保証することにより行うことができる。というのは、このような特性は、後述のメッセージリカバリ（ｍｅｓｓａｇｅ  ｒｅｃｏｖｅｒｙ）手順が、署名σが単に与えられたオリジナルメッセージを復元することを保証するからである。後者は、適切に定義された格子（ｌａｔｔｉｃｅ）における小さな非ゼロベクトルが存在しないことと等価である。所与の格子におけるこのような小さい非ゼロのベクトルの存在を除外するために、標準格子基底縮小方法（ｓｔａｎｄａｒｄ  ｌａｔｔｉｃｅ  ｂａｓｉｓ  ｒｅｄｕｃｔｉｏｎ  ｍｅｔｈｏｄ）を用いることができる。上記で同種写像を使用することによっても、このシステムは、標準的離散ログベースシステム（ｓｔａｎｄａｒｄ  ｄｉｓｃｒｅｔｅ  ｌｏｇ  ｂａｓｅｄ  ｓｙｓｔｅｍ）とは区別することができる。というのは、後者の実施形態は、離散ログ攻撃（ｄｉｓｃｒｅｔｅ  ｌｏｇ  ａｔｔａｃｋ）に屈するが、上述のシステムはそうではないからである。
【００５３】
図５は、同種写像技法が署名を検査するために利用される例示的実施形態における他の手順５００を示す流れ図である。ユーザは、２５個の文字を含む関連する製品識別子（ＩＤ）を有する製品を購入する（ブロック５０２）。次いで、プロダクトＩＤは、数「ｘ」に変換される（ブロック５０４）。
【００５４】
次いで、数「ｘ」から署名が計算される（ブロック５０６）。例えば、数「ｘ」は、次のように２つの部分に分割される。
【００５５】
【数４】
2006311477.tif 000006
【００５６】
上式において、ｚ＝｜Ｋ｜は、有限体Ｋにおける要素の数である。剰余（ｒｅｍｉｎｄｅｒ）「ｒ」は、｜Ｋ｜より小さく、Ｋの要素を識別する。次いで、その集団（ｆｉｅｌｄ）の要素は、プロダクトＩＤのためのσのｘ座標署名として受け取られる（ブロック５０８）。商（ｑｕｏｔｉｅｎｔ）「ｑ」は、メッセージを突き止める「ヒント」として使用される。
【００５７】
署名は、完全な点ではなく、楕円曲線上の点のｘ座標と見なすことができる（ブロック５１０）。例えば、楕円曲線「Ｅ」は、下記のように表すことができる。
Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂ
【００５８】
上式では、「ａ」および「ｂ」は、有限体での定数であり、「ｘ」と「ｙ」は、Ｋにおける変数である。Ｅ上の有限点は、上記の楕円曲線「Ｅ」の式を満たす座標（ｘ，ｙ）のペアである。ｘのみが既知の場合、体Ｋにおいて平方根を用いてｙの可能な値を求めることができる。平方根が存在しない場合は、ｘを棄却することができる。
【００５９】
次いで、各候補署名σ＝（ｘ，ｙ）および埋め込まれたメッセージｍが、署名が真正であることを示す数学的特性を有しているかどうかを決定することによって、検証される（ブロック５１２）。そのコードは、商「ｑ」を、メッセージを見つけることができる場所を示す「ヒント」として使用する（ブロック５１４）。例えば、検査の際に、モジュール（例えば、署名検証モジュール２１４）を実行して、下記の式とｅ１（Ｐ，Ｑ）を等しくするメッセージが発見されるまで、（ｍ１，ｍ２，ｍ３，…，ｍｔ）の各可能な値ごとに下記の式を計算する。
ｅ２（σ，（ｍ１φ１（Ｑ）＋ｍ２φ２（Ｑ）＋…＋ｍｔφｔ（Ｑ）））
【００６０】
一実装形態では、署名検証モジュール２１４を実行して、比較的少ない時間量でプロセッサ（例えば、プロセッサ２０４（ｏ））によって実行することができる計算数を利用することにより、メッセージの位置を突き止めるために「全数検索（ｅｘｈａｕｓｔｉｖｅ  ｓｅａｒｃｈ）」を使用することができる。この例では、ヒント「ｑ」は、より効率的にメッセージを突き止めるために利用することもでき、それにより、メッセージを計算するために使用する「ステップ」の数（例えば処理リソース）が抑えられる。したがって、ヒント「ｑ」は、可能なサーチスペース（ｓｅａｒｃｈ  ｓｐａｃｅ）を減少させる。式がｅ１（Ｐ，Ｑ）と等しくなるような、（ｘ，ｙ）のペアおよびメッセージが発見された場合、署名は有効であり、有効であることを示す結果が返される。そうではなく、このようなメッセージが発見されなかった場合、図４に関連して先に述べたように、署名は無効と見なされ、無効であることを示す結果が返される。様々な検索技法が、メッセージリカバリのために利用することができ、例えば、ベビーステップジャイアントステップ（ｂａｂｙ−ｓｔｅｐ−ｇｉａｎｔ−ｓｔｅｐ）またはポラードのラムダ（Ｐｏｌｌａｒｄ’ｓ  ｌａｍｂｄａ）方法は、「ブルートフォース（ｂｒｕｔｅ  ｆｏｒｃｅ）」の検索方法よりも漸近的に高速であり、ブルートフォースと比較し、復元することができるメッセージの長さを倍にすることができる。
【００６１】
結論
本発明は、構造的特徴および／または方法論的作用に特有の言葉で説明されているが、添付の明細書に定義される本発明は、説明された特定の特徴または作用に必ずしも限定されないことは理解されよう。特定の特徴および作用は、むしろ、請求項に係わる発明を実装するための例示的形態として開示されている。
【図面の簡単な説明】
【００６２】
【図１】署名の生成および検証のための技法を利用し動作することができる例示的実施形態における環境を示す図である。
【図２】図１の製品プロバイダおよびクライアントをより詳細に示す例示的実装形態におけるシステムを示す図である。
【図３】図２における秘密鍵を含む同種写像ベース技法（ｉｓｏｇｅｎｙ−ｂａｓｅｄ  ｔｅｃｈｎｉｑｕｅ）を用いて署名が生成される、例示的実施形態における手順を示す流れ図である。
【図４】図３の手順で生成された署名が、その署名を有する製品にも含まれる図２の公開鍵を使用して検査される、例示的実装形態における手順を示す流れ図である。
【図５】同種写像技法が、署名を検査するために利用される、例示的実装形態における他の手順を示す流れ図である。
【符号の説明】
【００６３】
１０２  製品プロバイダ
１０４（１）  クライアント
１０４（ｎ）  クライアント
１０４（Ｎ）  クライアント
１０６  製品ディストリビュータ
１０８（ｍ）  製品
１１４  署名システム
１１６（ｍ）  署名
１１８  署名モジュール
【図１】
2006311477.tif 000009
【図２】
2006311477.tif 000010
【図３】
2006311477.tif 000011
【図４】
2006311477.tif 000012
【図５】
2006311477.tif 000013