内在的証明書方式
【課題】少なくとも１つの信頼できるエンティティＣＡおよび加入者エンティティＡを有する保護されたディジタル通信システム内で公開鍵を生成する方法を提供する。
【解決手段】各エンティティＡについて、ＣＡがエンティティＡを区別する一意のアイデンティティＩAを選択することと、信頼できる当事者ＣＡのジェネレータをエンティティＡの私的な値と数学的に組み合わせることによって、対（ＩA、γA）がＡの内在的証明書として働くように、エンティティＡの公開鍵再構成公開データγAを生成することと、数学関数Ｆ（γA、ＩA）に従って内在的証明書情報（ＩA、γA）を組み合わせてエンティティ情報ｆを導出することと、エンティティ情報ｆに署名することによってエンティティＡの秘密鍵（ａ）を生成することと、秘密鍵（ａ）をエンティティＡに送信することを含む、方法。
【解決手段】各エンティティＡについて、ＣＡがエンティティＡを区別する一意のアイデンティティＩAを選択することと、信頼できる当事者ＣＡのジェネレータをエンティティＡの私的な値と数学的に組み合わせることによって、対（ＩA、γA）がＡの内在的証明書として働くように、エンティティＡの公開鍵再構成公開データγAを生成することと、数学関数Ｆ（γA、ＩA）に従って内在的証明書情報（ＩA、γA）を組み合わせてエンティティ情報ｆを導出することと、エンティティ情報ｆに署名することによってエンティティＡの秘密鍵（ａ）を生成することと、秘密鍵（ａ）をエンティティＡに送信することを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（発明の分野）
本発明は、暗号化鍵の転送および認証のための鍵配送方式に関する。
【背景技術】
【０００２】
（発明の背景）
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有（Diffie-Hellman key agreement）は、暗号システムでの鍵配送問題（Key distribution problem）に対する最初の実用的な解決策をもたらした。この鍵共有プロトコルでは、事前に会ったことも共有（分散）鍵材料（sharedkey material）を有したこともない２つの当事者が、オープンな（保護されない）チャネルを介してメッセージ（文書）を交換することによって、共有される秘密（sharedsecret）を確立することができる。セキュリティは、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題の扱い難さと、関連する離散対数の計算問題にかかっている。
【０００３】
インターネットおよび類似物の出現に伴って、公開鍵（Public key；パブリック・キー）および公開鍵証明書（Public key certificate）の大規模な配送の必要が、ますます重要になりつつある。公開鍵証明書は、それによって、検出不能な改ざんの危険性（dangerof undetectable manipulation）なしに、保護されない媒体（unsecured media）を介して公開鍵を格納、配送、または転送することのできる媒介物（vehicle）である。その目的は、一方の当事者の公開鍵を他方の当事者が入手できるようにし、その認証性（authenticity）および有効性（validity）を検証可能に（verfiable）することである。
【０００４】
公開鍵証明書は、データ部分および署名部分からなるデータ構造を有する。データ部分には、最低限として公開鍵およびそれに関連する当事者を識別する文字列を含む平文データが含まれる。署名部分は、データ部分に対する認証機関（certification authority、ＣＡ）のディジタル署名からなり、これによって、エンティティのアイデンティティ（identity;個人情報）が、指定された公開鍵と結びつけられる。ＣＡは信頼できる第三者であり、証明書のＣＡの署名は対象のエンティティに結びつけられた公開鍵の認証性（Authenticity）を保証する。
【０００５】
アイデンティティに基づくシステム（ＩＤに基づくシステム）は、通常の公開鍵システムに類似し、秘密変換（private transformation）と公開変換(public transformation)を用いるが、当事者は、以前のように明示的な公開鍵を有しない。その代わりに、公開鍵は、効果的に、一般に入手可能な当事者のアイデンティティ情報（たとえば氏名またはネットワーク・アドレス）に置換される。当事者を一意に識別し、その当事者に否定不能な形で（undeniably）関連付けることができる、一般に入手可能な情報であれば、どのような情報でもアイデンティティ情報として使用可能である。
【０００６】
公開鍵配送の代替手法では、内在的に証明される公開鍵（Implicitly certified public keys）が使用される。この場合、明示的なユーザー公開鍵が存在するが、その鍵は、証明書に基づくシステムのように公開鍵証明書（public-keycertificate）によって運ばれるのではなく、再構成（reconstruct）されなければならない。したがって、内在的に証明される公開鍵は、公開鍵（たとえばＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵）を配送するための代替手段として使用することができる。
【０００７】
内在的に証明される公開鍵機能の１例が、Ｇｕｎｔｈｅｒの内在的に証明される（ＩＤに基づく）公開鍵方法である。この方法では、
１．信頼できるサーバＴ（trusted server）が、適当な固定された公開の素数ｐ、およびＺp*のジェネレータαを選択する。Ｔは、１≦ｔ≦ｐ−２かつｇｃｄ（ｔ，ｐ−１）＝１であるランダムな整数ｔをその秘密鍵（privatekey）として選択し、公開鍵ｕ＝αt ｍｏｄ ｐをαおよびｐと共に公開する。
【０００８】
２．Ｔは、各当事者Ａに、一意の名前または識別する文字列ＩAおよび、ｇｃｄ（ｋA、ｐ−１）＝１であるランダムな整数ｋA、を割り当てる。Ｔは、その後、
【０００９】
【数１】
【００１０】
を計算する。ＰAは、Ａの鍵再構成公開データであり、これを用いて、他の当事者が、以下で示すように（ＰA）aを計算することができるようになる。
【００１１】
３．適当なハッシュ関数ｈを使用して、Ｔは、ａについて下の式を解く。
Ｈ（ＩA）≡ｔ．ＰA＋ｋAａ（ｍｏｄ ｐ−１）
４．Ｔは、ＩAに対するＴのＥｌＧａｍａｌ署名である対（ｒ，ｓ）＝（ＰA，ａ）を、保護された形でＡに送信する（ａは、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有のためのＡの秘密鍵である）。
【００１２】
５．他の当事者は、次式を計算することによって、一般に入手可能な情報（α、ＩA、ｕ、ＰA、ｐ）だけから、ＡのＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ公開鍵ＰAαを再構成することができる。
【００１３】
【数２】
【００１４】
したがって、離散対数問題の場合、証明書への署名は１回の累乗（exponentiation）演算を必要とするが、ＩＤに基づく内在的に証明される公開鍵の再構成は、２回の累乗が必要である。群（group）Ｚp*での累乗およびＥ（Ｆｑ）内の点のアナログ・スカラ乗算は、計算量的に強烈（computationallyintensive）であることが既知である。たとえば、ＲＳＡ方式は、楕円曲線システムと比較して極端に低速である。しかし、ＲＳＡタイプのシステムに対するＥＣシステムの明確な効率にもかかわらず、これは、特に「スマート・カード」、ポケット・ベル、および類似物などの限られた計算能力を有するコンピューティング装置にとって、まだ問題である。
【発明の概要】
【課題を解決するための手段】
【００１５】
（発明の概要）
本発明は、既存の方式に対して改良された計算速度をもたらす、効率的なＩＤに基づく内在的証明書方式の提供を試みる。便宜上、本明細書ではＺpに対する方式を説明するが、これらの方式は、楕円曲線暗号システムでも同等に実施可能である。
【００１６】
本発明によれば、少なくとも１つの信頼できるエンティティＣＡおよび加入者エンティティＡを有する保護されたディジタル通信システム内でアイデンティティに基づく公開鍵を生成する方法であって、
（ａ）各エンティティＡについて、ＣＡが、エンティティＡを区別する一意のアイデンティティＩAを選択するステップと、
（ｂ）信頼できる当事者ＣＡのジェネレータをエンティティＡの私的な値（private value）と数学的に組み合わせ、対（ＩA、γA）がＡの内在的証明書として働くようにすることによって、エンティティＡの公開鍵再構成公開データγAを生成するステップと、
（ｃ）エンティティ情報ｆを導出するために、数学関数Ｆ（γA、ＩA）に従って内在的証明書情報（ＩA、γA）を組み合わせるステップと、
（ｄ）エンティティ情報ｆに署名することによってエンティティＡの秘密鍵を生成するステップと、
秘密鍵をエンティティＡに送信するステップとを含み、
これによって、エンティティＡの公開鍵を、公開情報、ジェネレータγA、およびアイデンティティＩAから比較的効率的に再構成できるようにする方法が提供される。
【００１７】
本発明のもう１つの態様によれば、異なるビット強度（bit strengths）を有する複数の公開鍵を含み、公開鍵の１つが内在的に証明される公開鍵になることを特徴とする、公開鍵証明書が提供される。
例えば、本発明は以下を提供する。
（項目１） 少なくとも１つの信頼できるエンティティＣＡおよび加入者エンティティＡを有する保護されたディジタル通信システムで公開鍵を生成する方法であって、
（ａ）各エンティティＡについて、前記ＣＡが、前記エンティティＡを区別する一意のアイデンティティＩAを選択するステップと、
（ｂ）前記信頼できる当事者ＣＡのジェネレータを前記エンティティＡの私的な値（private value）と数学的に組み合わせてエンティティＡの公開鍵再構成公開データγAを生成するステップであって、前記対（ＩA、γA）がＡの内在的証明書（implicitcertificate）として働くように前記γAを生成するステップと、
（ｃ）数学関数Ｆ（γA、ＩA）に従って前記内在的証明書情報（ＩA、γA）を組み合わせてエンティティ情報ｆを導出するステップと、
（ｄ）前記エンティティ情報ｆに署名することによって前記エンティティＡの秘密鍵（private key）を生成するステップと
前記秘密鍵を前記エンティティＡに送信するステップとを備え、
これによって、前記エンティティＡの公開鍵は、前記公開情報、前記ジェネレータγA、および前記アイデンティティＩAから比較的効率的に再構成されることできることを特徴とする公開鍵の生成する方法。
（項目２） ディジタル通信システムにおける公開鍵証明書を生成する方法であって、
（ａ）公開鍵暗号アルゴリズムに従って、公開鍵証明書を生成するステップと、
（ｂ）複数の公開鍵であって、前記公開鍵の少なくとも１つが、内在的に署名される公開鍵（implicitly signed public key）である前記複数の公開鍵を公開鍵証明書内に埋め込むステップと、
（ｃ）前記証明書を公開するステップと
を含むとを特徴とする公開鍵証明書の生成方法。
（項目３） 信頼できるエンティティＣＡによって加入者エンティティＡの公開鍵証明書を生成する方法であって、
ａ）前記加入者エンティティＡの一意のアイデンティティ情報ＩAを選択するステップと、
ｂ）前記加入者エンティティＡの私的な値ｃAを生成するステップと、
ｃ）前記私的な値（private value）ｃAから前記エンティティＡの公開値γAを生成するステップと、
ｄ）値ｆを生成するために、暗号関数内で前記公開値γAおよび前記アイデンティティ情報ＩAを使用するステップと、
ｅ）署名ａを作るために前記値ｆに署名するステップと、
ｆ）前記署名ａ、公開値γA、および前記アイデンティティ情報ＩAを前記加入者エンティティに送信するステップと
を含むとを特徴とする公開鍵証明書の生成方法。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態に従って構成された第１のシステムの概略図である。
【図２】本発明の実施形態に従って構成された第２のシステムの概略図である。
【発明を実施するための形態】
【００１９】
（好ましい実施形態の詳細な説明）
図１を参照すると、内在的に証明される公開鍵（Implicitly certified public key）を有するシステムが、全般的に符号１０によって示されている。このシステム１０には、信頼できる第三者のＣＡおよび、少なくとも第１通信者Ａおよび第２通信者Ｂの対が含まれる。通信者ＡおよびＢは、通信チャネルを介して情報を交換し、通信者ＡおよびＢのそれぞれには、認定／検証（finding/verification）および暗号化／非暗号化（解読）（encryption/decryption）を実行する暗号装置（cryptographicunit）が含まれる。
【００２０】
図１を参照すると、信頼できる当事者ＣＡは、大きい素数ｑについてｐ＝ｔｑ＋１である適当な素数ｐと、オーダー（order）ｑのジェネレータαを選択する。ＣＡは、その秘密鍵として１≦ｃ≦ｑ−１のランダムな整数ｃを選択し、公開鍵β＝αcを計算し、（β、α、ｐ、ｑ）を公開する。
【００２１】
方式１：
１．各当事者Ａについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１≦ｃA≦ｑ−１のランダムな整数ｃAを選択する。次に、ＣＡは、
【００２２】
【数３】
【００２３】
を計算する（γAは、当事者Ａの公開鍵再構成公開データである。対（ＩA、γA）は、Ａの内在的証明書として働く）。
【００２４】
２．ＣＡは、関数ｆ＝Ｆ（ＩA、γA）を選択する。たとえば、Ｆ（γA、ＩA）＝γA＋ｈ（ＩA）またはＦ（γA、ＩA）＝ｈ（γA＋ＩA）である。ここで、ｈは、安全なハッシュ関数であり、当事者Ａの秘密鍵であるａについて次式を解く。ａ＝０の場合には、ＣＡは、別のｃAを選択し、もう一度次式を解く。
１＝ｃｆ＋ｃAａ（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。ここで、
αは、Ａの秘密鍵であり、
γAは、Ａのジェネレータであり、
【００２５】
【数４】
【００２６】
は、Ａの公開鍵である。
Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算し、したがって公開鍵を導出することによって、公開ドメインから当事者Ａの（ＩＤに基づく）内在的に検証可能な公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
このように上述の式から公開鍵を引き出すことは、ただ１つの累乗演算（exponentiation operation）を必要とする。
【００２７】
誰でも公開データから当事者Ａの公開鍵を再構成することができるが、これは、再構成された公開鍵γAaが証明されたことを意味しない。この方式は、当事者Ａが対応する秘密鍵の完全な知識を有することを示すアプリケーション・プロトコルと組み合わされたときに、より効果的になる。たとえば、ＭＱＶ鍵共有方式またはなんらかの署名方式、特にＫＣＤＳＡ（Korean Certificate based Digital Signature Algorithm）と組み合わされたときである。一般に、この内在的証明書方式は、証明書を検証することを必要とするどの方式とも、共に使用することができる。これは、ＤＳＡ（DigitalSignature Algorithm）署名方式に言及することによって実証することができる。
【００２８】
アリスが、公開鍵α、ジェネレータγAを有し、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開すると仮定する。次に、アリスは、ＤＳＡを使用してメッセージＭに署名しようとする。
アリスは、下記を実行する。
１．ランダムにｋを選択し、ｒ＝γAk（ｍｏｄ ｐ）を計算する。
２．ｅ＝ｓｈａ−１（Ｍ）を計算する。
３．ｓ＝ｋ-1（ｅ＋ａｒ）（ｍｏｄ ｐ）を計算する。
４．Ｍに対する署名は、（ｒ、ｓ）になる。
【００２９】
検証者は、下記を実行する。
１．アリスの公開データ（α、ＩA、β、γA、ｐ、ｑ）を取得し、公開鍵を再構成する。
δA＝γAa＝αβ-1（ｍｏｄ ｐ）
２．ｅ＝ｓｈａ−１（Ｍ）を計算する。
３．ｕ1＝ｅｓ-1（ｍｏｄ ｑ）およびｕ2＝ｒｓ-1（ｍｏｄ ｑ）を計算する。
４．
【００３０】
【数５】
【００３１】
を計算する。
５．ｒ＝ｒ’の場合には、署名が検証される。それと同時に、アリスの（ＩＤに基づく）公開鍵が、内在的に検証される。
【００３２】
対（ＩA、γA）は、アリスの証明書として働く。公開鍵の再構成は、アプリケーション・プロトコルが有効な検証をもたらすときに、内在的検証として働く。公開鍵を取得するために、１回の累乗演算だけが必要であることを想起されたい。
【００３３】
代替実施形態では、署名方程式を適当に変更することによって、この方式をほとんどのＥｌＧａｍａｌ署名方式に一般化することができる。以下の節で、いくつかの例を示す。
【００３４】
方式２：
ＣＡは、署名方程式ｌ＝ｃａ＋ｃAｆ（ｍｏｄ ｑ）を使用する。ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信し、その後、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
この方式では、各ユーザーが、同一のジェネレータβを有し、このβは、ＣＡの公開鍵である。
【００３５】
方式３：
ＣＡは、署名方程式ａ＝ｃｆ＋ｃA（ｍｏｄ ｑ）を使用する。ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信し、その後、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
この方式では、ＣＡを含む各ユーザーが、同一のジェネレータαを有する。
【００３６】
方式４：
ＣＡは、署名方程式ａ≡ｃAｆ＋ｃ（ｍｏｄ ｑ）を使用する。ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信し、その後、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
この方式では、ＣＡを含む各ユーザーが、同一のジェネレータαを有する。
【００３７】
上の方式では、ユーザーまたは当事者Ａは、それ自体の秘密鍵を選択する権利を有しない。図２に示された以下の方式は、ＣＡおよびユーザーの両方が、ユーザーの秘密鍵を制御するが、ユーザーだけがその秘密鍵を知っている。
【００３８】
方式５’：
Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。ＣＡは、
【００３９】
【数６】
【００４０】
を計算し、ｋAについて以下の署名方程式を解く。
１＝ｃｆ＋ｃAｋA（ｍｏｄ ｑ）
その後、ＣＡは、
【００４１】
【数７】
【００４２】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。Ａは、ａ＝ｋAｋ-1（ｍｏｄ ｑ）およびγA＝（γA1）k（ｍｏｄ ｐ）を計算する。その後、ａがＡの秘密鍵、γAがＡのジェネレータ、γAaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
方式６：
１．Ａは、まず、整数ｋをランダムに選択し、βkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００４３】
【数８】
【００４４】
およびｆ＝Ｆ（γA、ＩA）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｋA＋ｃAｆ（ｍｏｄ ｑ）
その後、ＣＡは、
【００４５】
【数９】
【００４６】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
注：（γA1、ｋA、ＩA）は、公開チャネルによって送信することができる。
３．Ａは、
【００４７】
【数１０】
【００４８】
、ｆ＝Ｆ（γA、ＩA）、およびａ＝ｋA−ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、βa＝αγA-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
【００４９】
βa＝αγA-f（ｍｏｄ ｐ）
方式７：
Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。ここでＣＡは、
【００５０】
【数１１】
【００５１】
を計算し、ｋAについて署名方程式を解く。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
その後、ＣＡは、
【００５２】
【数１２】
【００５３】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。Ａは、
【００５４】
【数１３】
【００５５】
を計算する。その後、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）がＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式８：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００５６】
【数１４】
【００５７】
およびｆ＝Ｆ（γA、ＩA）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃAｆ＋ｃ（ｍｏｄ ｑ）
その後、ＣＡは、
【００５８】
【数１５】
【００５９】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
注：（γA1、ｋA、ＩA）は、公開チャネルによって送信することができる。
３．Ａは、
【００６０】
【数１６】
【００６１】
、ｆ＝Ｆ（γA、ＩA）およびａ＝ｋA＋ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝γAfβであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
上の方式５〜８では、ｋAが公開チャネルによって送信されるので、誰もが、ユーザーＡの秘密鍵αの部分的な情報を得ることができる。この情報を隠し、上の方式の計算を高速化するために、ＤＥＳ暗号化を導入して、方式５〜８を変更することによって、以下の方式９〜１２を得た。方式９〜１２の長所は、βが固定されているので、ユーザーが簡単にＫを計算できることである。
【００６２】
方式９：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００６３】
【数１７】
【００６４】
およびｆ＝Ｆ（γA、β、ＩA）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｆ＋ｃAｋA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝（ａk）c（ｍｏｄ ｐ）および
【００６５】
【数１８】
【００６６】
を計算し、３つ組
【００６７】
【数１９】
【００６８】
をＡに送信する。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【００６９】
【数２０】
【００７０】
、およびａ＝ｋAｋ-1（ｍｏｄ ｑ）を計算する（ａ＝１の場合には、ステップ１に戻る）。その後、γAa＝αβ-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、γAがＡのジェネレータ、γAaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
方式１０：
１．Ａは、まず、整数ｋをランダムに選択し、βkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００７１】
【数２１】
【００７２】
およびｆ＝Ｆ（γA、β、ＩA）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｋA＋ｃAｆ（ｍｏｄ ｑ）
次に、ＣＡは、
【００７３】
【数２２】
【００７４】
を計算し、３つ組
【００７５】
【数２３】
【００７６】
をＡに送信する。
注：
【００７７】
【数２４】
【００７８】
は、公開チャネルによって送信することができる。
３．Ａは、
【００７９】
【数２５】
【００８０】
を計算し、ａ＝ｋA−ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、βa＝αγA-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
方式１１：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００８１】
【数２６】
【００８２】
およびｆ＝Ｆ（γA、β、ＩA）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA＝ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝（αk）c（ｍｏｄ ｐ）および
【００８３】
【数２７】
【００８４】
を計算し、３つ組
【００８５】
【数２８】
【００８６】
をＡに送信する。
注：
【００８７】
【数２９】
【００８８】
は、公開チャネルによって送信することができる。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【００８９】
【数３０】
【００９０】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、αa＝γAf（ｍｏｄ ｐ）を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
【００９１】
方式１２：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００９２】
【数３１】
【００９３】
およびｆ＝Ｆ（γA、β、ＩA）を計算し、ｋA（ｋA＝０の場合には、別のｃAを選択する）ｋA＝ｃAｆ＋ｃ（ｍｏｄ ｑ）を計算する。
次に、ＣＡは、Ｋ＝（αk）c（ｍｏｄ ｐ）および
【００９４】
【数３２】
【００９５】
を計算し、３つ組
【００９６】
【数３３】
【００９７】
をＡに送信する。
注：
【００９８】
【数３４】
【００９９】
は、公開チャネルによって送信することができる。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【０１００】
【数３５】
【０１０１】
、ｆ＝Ｆ（γA、β、ＩA）、およびａ＝ｋA＋ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝γAfβであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
方式９〜１２の長所は、βが固定されているのでユーザーＡがＫを簡単に計算できることと、ｋAが暗号化され、他人がそれを知ることができなくなっていることである。
【０１０２】
方式５〜１２の場合、関数Ｆ（γA、β、ＩA）にオプション・パラメータＯＰを追加すること（すなわち、ｆ＝Ｆ（γA、β、ＩA、ＯＰ）によって、これらの方式がより役立つものになる。たとえば、
【０１０３】
【数３６】
【０１０４】
である。ここでａEは、ユーザーＡの秘密暗号化鍵であり、
【０１０５】
【数３７】
【０１０６】
は、Ａの公開暗号化鍵である。下の方式１５は、方式７の変形形態である。方式５〜１２を、同一の形で変更することができる。方式１〜４も、同一の形で変更することができる。
【０１０７】
方式１３：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０１０８】
【数３８】
【０１０９】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０１１０】
【数３９】
【０１１１】
を計算し、３つ組
【０１１２】
【数４０】
【０１１３】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０１１４】
【数４１】
【０１１５】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、γA＝αaβ-f（ｍｏｄ ｐ）を計算し、ｆ＝Ｆ（γA、ＩA、ＯＰ）であるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
さらに、方式１４に従うことによって、帯域幅（bandwidth）を減らすことができる。
【０１１６】
方式１４：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０１１７】
【数４２】
【０１１８】
を計算し、
【０１１９】
【数４３】
【０１２０】
をγAの最初の８０個の最下位ビットとしてセットする。その後、
【０１２１】
【数４４】
【０１２２】
およびｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝（αk）c（ｍｏｄ ｐ）および
【０１２３】
【数４５】
【０１２４】
を計算し、３つ組
【０１２５】
【数４６】
【０１２６】
をＡに送信する。
注：
【０１２７】
【数４７】
【０１２８】
は、公開チャネルによって送信することができる。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【０１２９】
【数４８】
【０１３０】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、
【０１３１】
【数４９】
【０１３２】
、γA＝αaβ-f（ｍｏｄ ｐ）を計算し、γAの最初の８０個の最下位ビットが
【０１３３】
【数５０】
【０１３４】
であるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式５．ｃのセキュリティ・レベルは、前に述べた他の方式ほどではない。方式５．ｃは、８０ビットのセキュリティだけを有する。しかし、現在の実用的なアプリケーションにはこれでよい。最初の８０個の最下位ビットを、γAの半分の下位ビットに拡張することができる。
【０１３５】
内在的証明書は、情報にオプション・パラメータＯＰを含めることによって、他の有用な情報を証明するのに使用することができる。たとえば、
【０１３６】
【数５１】
【０１３７】
である。ここで、ａEは、Ａのもう１つの秘密鍵であり、
【０１３８】
【数５２】
【０１３９】
は、対応する公開鍵である。下の方式１５は、方式７の変形形態である。他の方式も、同一の形で変更することができる。
【０１４０】
方式１５：
１．整数ａEをランダムに選択し、
【０１４１】
【数５３】
【０１４２】
を計算する。
２．Ａは、整数ｋをランダムに選択し、αkを計算し、αkおよび
【０１４３】
【数５４】
【０１４４】
をＣＡに送信する。
３．ＣＡは、整数ｃAをランダムに選択し、
【０１４５】
【数５５】
【０１４６】
および
【０１４７】
【数５６】
【０１４８】
（たとえば
【０１４９】
【数５７】
【０１５０】
）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA＝ｃｆ＋ｃA（ｍｏｄ ｑ）
その後、ＣＡは、
【０１５１】
【数５８】
【０１５２】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
注：（γA1、ｋA、ＩA）は、公開チャネルによって送信することができる。
４．Ａは、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算し（ａ＝０、１の場合には、ステップ１に戻る）、
【０１５３】
【数５９】
【０１５４】
を計算する。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密署名鍵であり、αがＡのジェネレータ、αaがＡの公開署名鍵であり、ａEがＡの秘密暗号化鍵、
【０１５５】
【数６０】
【０１５６】
がＡの公開暗号化鍵である。Ａは、公開ドメインで
【０１５７】
【数６１】
【０１５８】
を公開する。
５．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
注：（方式１３〜１５について）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、方式１１の注２に記載の方法によって行うことができる。
３．
【０１５９】
【数６２】
【０１６０】
または
【０１６１】
【数６３】
【０１６２】
または（γA1、ｋA、ＩA）を、公開チャネルによって送信することができる。
本発明の方式では、（α、γA）は、ＡのＩＤ、ＩAに対するＣＡの署名であり、これは公衆によって知られると思われた。しかし、現在は、ユーザーＡだけがａを知る。したがって、本発明の方式を使用するときには、アプリケーション・プロトコルで、ユーザーＡが自分自身の秘密鍵を知るようにしなければならない。言い換えると、アプリケーション・プロトコルは、Ａが計算に自分の秘密鍵を使用することを保証しなければならない。
【０１６３】
新方式のセキュリティは、署名方程式に依存する。たとえば、方式１では、署名方程式は次式である。
１＝ｃｆ＋ｃAａ（ｍｏｄ ｑ） （１）
以下で、１方向関数Ｆ（γA、ＩA）の選択について、新しい方式１がＤＳＡと同等であることを示す。
【０１６４】
ＣＡが、ＡのアイデンティティＩAに署名するのにＤＳＡ署名方程式を使用すると仮定する。まず、ＣＡは、ｃAをランダムに選択し、
【０１６５】
【数６４】
【０１６６】
を計算し、次に、ＣＡは、安全なハッシュ関数ｈを使用してｈ（ＩA）を計算し、最後に、ＣＡは、ｓについて次式を解く。
ｈ（ＩA）≡ｃγA＋ｃAｓ（ｍｏｄ ｑ） （２）
ここで、（γA、ｓ）は、ＩAに対するＣＡの署名である。
式（２）にｈ（ＩA）-1を乗ずることによって、次式が得られる。
１≡ｃγAｈ（ＩA）-1＋ｃAｓｈ（ＩA）-1（ｍｏｄ ｑ）
Ｆ（γA、ＩA）＝γAｈ（ＩA）-1であると仮定し、上の式のｓｈ（ＩA）-1をａで置換することによって、式（１）が得られる。明らかに、式（２）は、Ｆ（γA、ＩA）＝γAｈ（ＩA）-1の場合に、式（１）と同等である。これは、誰かが署名方程式（１）を使用してこの方式を破ることができる場合に、その人物が、ＤＳＡ方式である署名方程式（２）を使用してこの方式を破ることができることを意味する。
【０１６７】
ヒューリスティックな（heuristic）議論から、Ｆ（γA、ＩA）＝γAｈ（ＩA）またはＦ（γA、ＩA）＝ｈ（γA、ＩA）である場合に、本発明の新方式が、Ｆ（γA、ＩA）の適当な選択について安全であることが暗示される。Ｆ（γA、ＩA）は、なんらかの他の形にすることができ、たとえば、ＩAが小さく、たとえば２０ビットであるが、ｑが１８０ビットを超えるときに、Ｆ（γA、ＩA）＝γA＋ＩAを使用することができる。新方式の短所は、すべてのユーザーおよびＣＡが同一のフィールド・サイズを使用することである。しかし、これは、たとえばＧｉｒａｕｌｔのＲＳＡに基づくＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ公開鍵共有方式など、すべてのＩＤに基づく内在的に証明される公開鍵方式が動作する方法である。
【０１６８】
もう１組の方式も、次のように説明することができる。
【０１６９】
システム・セットアップ：信頼できる当事者ＣＡは、大きい素数ｑについてｐ＝ｔｑ＋１である適当な素数ｐと、オーダー（位数）ｑのジェネレータαを選択する。ＣＡは、その秘密鍵として１＜ｃ＜ｑ−１のランダムな整数ｃを選択し、公開鍵β＝αc ｍｏｄ ｐを計算し、（β、α、ｐ、ｑ）を公開する。その後、ＣＡは、特殊な暗号関数ｆ＝Ｆ（γA、ＩA、ＯＰ）（ｆ：｛０、１｝*→｛１、２、…、（ｑ−１）｝）を選択し、この関数を用いて、内在的証明書を作るのに使用される署名方式が安全になるようにする。ここで、ＯＰは、ユーザーが関係することのできるなんらかのオプション・パラメータ（日付、またはＣＡの公開鍵β）を表す。たとえば、ｈが安全なハッシュ関数であるものとすると、ｆは、以下の形式のいずれかにすることができる。
１．Ｆ（γA、ＩA、ＯＰ）＝γA＋β＋ｈ（ＩA）
２．Ｆ（γA、ＩA、ＯＰ）＝ｈ（γA‖β‖ＩA）
３．Ｆ（γA、ＩA、ＯＰ）＝γA＋β＋ＩA、ここで、ＩAは、なんらかのパターン（または、ＩAが小さく、たとえば２０ビットであり、ｑが１８０ビットを超えるとき）を有する。
４．Ｆ（γA、ＩA、ＯＰ）＝γA＋ｈ（ＩA）
５．Ｆ（γA、ＩA、ＯＰ）＝ｈ（γA‖ＩA）
６．Ｆ（γA、ＩA、ＯＰ）＝γA＋ＩA、ここで、ＩAは、なんらかのパターン（または、ＩAが小さく、たとえば２０ビットであり、ｑが１８０ビットを超えるとき）を有する。
７．パラメータを少し変更して、所与の安全な署名方式から安全な署名方式を得ることは非常に簡単である。したがって、Ｆ（γA、ＩA、ＯＰ）は、内在的証明書を作るのに使用された署名方式が安全であることを保障する他の形式とすることができる。Ｆ（γA、ＩA、ＯＰ）を適当に選択することによって、これまでに知られているＥｌｇａｍａｌ様署名方式が、変更の後に内在的証明書方式として使用される場合の本明細書で提案される４系列の方式の１つと同等になることに留意されたい。しかし、本明細書で提案される方式は、より高い効率を有する。
【０１７０】
注：上記のシステム・セットアップが、以下の方式で仮定される。
【０１７１】
方式１．ａ：
１．各エンティティＡについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１＜ｃA＜ｑのランダムな整数ｃAを選択する。次に、ＣＡは、
【０１７２】
【数６５】
【０１７３】
を計算する。（γAは、Ａの公開鍵再構成公開データである。（ＩA、γA）は、Ａの内在的証明書として働く）。
２．ＣＡは、ｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ａについて次式を解く（ａ＝０、１、ｃ、ｃA-1ｃの場合には、別のｃAを選択し、式をもう一度解く）。
１＝ｃｆ＋ｃAａ（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。その後、ａがＡの秘密鍵、γAがＡのジェネレータ、
【０１７４】
【数６６】
【０１７５】
がＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
注：
１．ステップ１では、アイデンティティＩAをエンティティＡが選択することができる。
２．ステップ２では、ａ＝０、１を排除した。というのは、この場合に、誰もがＡの秘密鍵を簡単に知ることができるからである。特にａ＝０，ｃA-1ｃのときには、１＝ｃｆ（ｍｏｄ ｑ）からＣＡの秘密鍵ｃを誰でも簡単に計算することができる。
３．この方式では、各ユーザーが異なるシステム・ジェネレータγAを有する。
【０１７６】
方式１．ｂ：
１．各エンティティＡについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１＜ｃA＜ｑのランダムな整数ｃAを選択する。次に、ＣＡは、
【０１７７】
【数６７】
【０１７８】
を計算する（γAは、Ａの公開鍵再構成公開データである。（ＩA、γA）は、Ａの内在的証明書として働く）。
２．ＣＡは、ｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ａについて次式を解く（ａ＝０、１、ｃの場合には、別のｃAを選択し、式をもう一度解く）。
１≡ｃａ＋ｃAｆ（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。その後、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
注：
１．ステップ１では、アイデンティティＩAをエンティティＡが選択することができる。
２．ステップ２では、ａ＝０、１を排除した。というのは、この場合に、誰もがＡの秘密鍵を簡単に知ることができるからであり、ａ＝０のときには、証明書は、ＣＡに関係しない。
３．この方式では、各ユーザーが同一のシステム・ジェネレータβを有する。
【０１７９】
方式１．ｃ：
１．各エンティティＡについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１＜ｃA＜ｑのランダムな整数ｃAを選択する。次に、ＣＡは、
【０１８０】
【数６８】
【０１８１】
を計算する（γAは、Ａの公開鍵再構成公開データである。（ＩA、γA）は、Ａの内在的証明書として働く）。
２．ＣＡは、ｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ａについて次式を解く（ａ＝０、１、またはｃの場合には、別のｃAを選択し、式をもう一度解く）。
ａ≡ｃｆ＋ｃA（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
注：
１．ステップ１では、アイデンティティＩAをエンティティＡが選択することができる。
２．ステップ２では、ａ＝０、１を排除した。というのは、この場合に、誰もがＡの秘密鍵を簡単に知ることができるからである。
３．この方式では、各ユーザーが同一のシステム・ジェネレータαを有する。
【０１８２】
方式１．ｄ：
１．各エンティティＡについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１＜ｃA＜ｑのランダムな整数ｃAを選択する。次に、ＣＡは、
【０１８３】
【数６９】
【０１８４】
を計算する（γAは、Ａの公開鍵再構成公開データである。（ＩA、γA）は、Ａの内在的証明書として働く）。
２．ＣＡは、ｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ａについて次式を解く（ａ＝０、１、またはｃの場合には、別のｃAを選択し、式をもう一度解く）。
【０１８５】
ａ≡ｃAｆ＋ｃ（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
注：
１．ステップ１では、アイデンティティＩAをエンティティＡが選択することができる。
２．ステップ２では、ａ＝０、１を排除した。というのは、この場合に、誰もがＡの秘密鍵を簡単に知ることができるからである。
３．この方式では、各ユーザーが同一のシステム・ジェネレータαを有する。
【０１８６】
誰でも公開データからユーザーＡの公開鍵を再構成することができるが、これは、再構成された公開鍵が証明されたことを意味しない。証明書を明示的に検証するためには、ａを知る必要がある。ａを知ったならば、検証プロセスは、ＩAに対するＣＡの署名を検証することになる。たとえば、方式１．ａでは、検証者がαβ-fを計算し、ユーザーＡがａを使用してγAaを計算する場合に、検証者およびユーザーが、一緒に証明書を検証することができる。しかし、検証者は、ユーザーＡが実際にａを知っていることを確認しなければならない。したがって、公開鍵の再構成は、ユーザーＡが対応する秘密鍵の完全な知識を有することを示すアプリケーション・プロトコルと組み合わされる場合に限って、内在的検証として働く。一般に、内在的証明書方式は、対象のエンティティおよび公開鍵の認証を必要とするすべての公開鍵方式と共に使用することができる。
【０１８７】
内在的に証明される公開鍵システムとしてＤＳＡ署名方式を使用し、内在的証明書方式として方式１．ａを使用して、これを実証する。
【０１８８】
アリスが、秘密鍵ａ、ジェネレータγAを有し、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開すると仮定する。次に、アリスは、ＤＳＡを使用してメッセージＭに署名しようとする。
アリスは、下記を実行する。
１．ランダムにｋを選択し、ｒ＝γAk（ｍｏｄ ｐ）を計算する。
２．ｅ＝ｓｈａ−１（Ｍ）を計算する。
３．ｓ＝ｘ-1（ｅ＋ａｒ）（ｍｏｄ ｑ）を計算する。
４．Ｍに対する署名は、（ｒ、ｓ）になる。
検証者は、下記を実行する。
１．アリスの公開データ（α、ＩA、β、γA、ｐ、ｑ）を取得し、ｆを計算し、公開鍵を再構成する。
βA＝γAa＝αβ-f（ｍｏｄ ｐ）
２．ｅ＝ｓｈａ−１（Ｍ）を計算する。
３．ｕ1＝ｅｓ-1（ｍｏｄ ｑ）およびｕ2＝ｒｓ-1（ｍｏｄ ｑ）を計算する。
４．
【０１８９】
【数７０】
【０１９０】
を計算する。
５．ｒ＝ｒ’の場合には、署名が検証される。それと同時に、アリスの（ＩＤに基づく）公開鍵が、内在的に検証される。
対（ＩA、γA）は、アリスの証明書として働く。ＤＳＡの場合、ａを知らずにアリスの署名を偽造することが非常に困難であることがわかっている。公開鍵の再構成は、アプリケーション・プロトコルが最後に有効になるときに、内在的検証として働く。公開鍵を取得するために、１回の累乗演算だけが必要であることを想起されたい。この理由から、本発明人は、内在的証明書の検証が、１回の累乗演算を必要とすると主張する。
【０１９１】
以下の内在的証明書方式は、ＣＡおよびエンティティの両方が、エンティティの秘密鍵を制御するが、対象のエンティティだけがその秘密鍵を知るように、上の方式を変更することによって導出することができる。
【０１９２】
この節では、もう１つのシステム・パラメータＨ（＊）が必要であり、このＨ（＊）は、安全なハッシュ関数または１方向関数またはアイデンティティ・マップとすることができる暗号関数である。
【０１９３】
方式２．ａ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０１９４】
【数７１】
【０１９５】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAについて署名方程式を解く（ｋA＝０またはｃの場合には、別のｃAを選択する）。
１＝ｃｆ＋ｃAｋA（ｍｏｄ ｑ）
その後、ＣＡは、
【０１９６】
【数７２】
【０１９７】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
３．Ａは、ａ＝ｋAｋ-1（ｍｏｄ ｑ）を計算し（ａ＝１の場合には、ステップ１に戻る）、γA＝（γA1）k（ｍｏｄ ｐ）を計算する。その後、γAa＝αβ-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、γAがＡのジェネレータ、γAaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
方式２．ｂ：
５．Ａは、整数ｋをランダムに選択し、βkを計算し、これをＣＡに送信する。
６．ＣＡは、整数ｃAをランダムに選択し、
【０１９８】
【数７３】
【０１９９】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｋA＋ｃAｆ（ｍｏｄ ｑ）
その後、ＣＡは、
【０２００】
【数７４】
【０２０１】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
７．Ａは、
【０２０２】
【数７５】
【０２０３】
、ｆ＝Ｆ（γA、ＩA、ＯＰ）、およびａ＝ｋA−ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、βa＝αγA-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
８．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
方式２．ｃ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２０４】
【数７６】
【０２０５】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝ｃの場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
その後、ＣＡは、
【０２０６】
【数７７】
【０２０７】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
３．Ａは、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算し（ａ＝０、１の場合には、ステップ１に戻る）、
【０２０８】
【数７８】
【０２０９】
を計算する。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式２．ｄ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２１０】
【数７９】
【０２１１】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝ｃAの場合には、別のｃAを選択する）。
ｋA≡ｃAｆ＋ｃ（ｍｏｄ ｑ）
その後、ＣＡは、
【０２１２】
【数８０】
【０２１３】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
３．Ａは、
【０２１４】
【数８１】
【０２１５】
、ｆ＝Ｆ（γA、ＩA、ＯＰ）、およびａ＝ｋA＋ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝γAfβであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
注：（方式２．ａ、２．ｂ、２．ｃ、２．ｄについて）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、ＣＡの面前での存在または保護されたチャネルまたは音声（たとえば電話での）または次の方法のいずれかによって行うことができる。
ステップ２で、３つ組（γA1、ｋA、ＩA）をＡに送信する代わりに、ＣＡが、まずγA1をＡに送信する。Ａは、γAを計算し、Ｋ＝Ｈ（γA）にセットし、ＤＥＳ（または他の対称鍵システム）によってＡの認証情報ＡAI（ＶＩＳＡ情報など）を暗号化し、ＤＥＳK（ＡAI）をＣＡに送信する。ＣＡは、ＤＥＳK（ＡAI）を非暗号化してＡAIを得る。ＡAIの有効性を検査した後に、ＣＡは（ｋA、ＩA）をＡに送信する。
３．（γA1、ｋA、ＩA）は、公開チャネルによって送信することができる。
【０２１６】
上の方式２．ａ〜２．ｄでは、内在的証明書方式が、対象のエンティティおよびＣＡによって完了される。各方式は、本質的に２つの部分すなわち鍵交換部分および署名部分に分割される。鍵交換部分の機能の１つが、公開チャネルによってＣＡからＡに内在的証明書情報を送信することである（詳細な説明は節６で行う）。上の方式の計算を高速化するために、鍵交換部分を変更することができる。以下の方式３．ａ〜３．ｄは、方式２．ａ〜２．ｄを変更することによって得られた。方式３．ａ〜３．ｄの長所は、βが固定されているので、ユーザーＡが、ＣＡから応答を得る前にＫを計算できることである。この特性は、特にオンラインの場合に好ましい。
【０２１７】
方式３．ａ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２１８】
【数８２】
【０２１９】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｆ＋ｃAｋA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０２２０】
【数８３】
【０２２１】
を計算し、３つ組
【０２２２】
【数８４】
【０２２３】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０２２４】
【数８５】
【０２２５】
、およびａ＝ｋAｋ-1（ｍｏｄ ｑ）を計算する（ａ＝１の場合には、ステップ１に戻る）。その後、γAa＝αβ-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、γAがＡのジェネレータ、γAaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
方式３．ｂ：
１．Ａは、整数ｋをランダムに選択し、βkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２２６】
【数８６】
【０２２７】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｋA＋ｃAｆ（ｍｏｄ ｑ）
次に、ＣＡは、
【０２２８】
【数８７】
【０２２９】
およびｋ￣A＝ＤＥＳk（ＫA）を計算し、３つ組
【０２３０】
【数８８】
【０２３１】
をＡに送信する。
３．Ａは、
【０２３２】
【数８９】
【０２３３】
を計算し、ａ＝ｋA−ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、βa＝αγA-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
注：（方式３．ｂについて）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、ＣＡの面前での存在または保護されたチャネルまたは音声（たとえば電話での）または次の方法のいずれかによって行うことができる。
ステップ２で、３つ組
【０２３４】
【数９０】
【０２３５】
をＡに送信する代わりに、ＣＡが、まずγAをＡに送信する。Ａは、
【０２３６】
【数９１】
【０２３７】
を計算し、ＤＥＳ（または他の対称鍵システム）によってＡの認証情報ＡAI（ＶＩＳＡ情報など）を暗号化し、ＤＥＳK（ＡAI）をＣＡに送信する。ＣＡは、ＤＥＳK（ＡAI）を非暗号化してＡAIを得る。ＡAIの有効性を検査した後に、ＣＡは
【０２３８】
【数９２】
【０２３９】
をＡに送信する。
３．
【０２４０】
【数９３】
【０２４１】
は、公開チャネルによって送信することができる。
【０２４２】
方式３．ｃ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２４３】
【数９４】
【０２４４】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０２４５】
【数９５】
【０２４６】
を計算し、３つ組
【０２４７】
【数９６】
【０２４８】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０２４９】
【数９７】
【０２５０】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式３．ｄ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２５１】
【数９８】
【０２５２】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃAｆ＋ｃ（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０２５３】
【数９９】
【０２５４】
を計算し、３つ組
【０２５５】
【数１００】
【０２５６】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０２５７】
【数１０１】
【０２５８】
、ｆ＝Ｆ（γA、ＩA、ＯＰ）、およびａ＝ｋA＋ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝γAfβであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
注：（方式３．ａ、３．ｃ、３．ｄについて）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、ＣＡの面前での存在または保護されたチャネルまたは音声（たとえば電話での）または次の方法のいずれかによって行うことができる。
ステップ１で、Ａは、αkおよびＫ＝Ｈ（βk）を計算し、αkおよびＤＥＳK（ＡAI）をＣＡに送信する。ＣＡは、Ｋ＝Ｈ（（αk）c）を計算し、ＤＥＳK（ＡAI）を非暗号化してＡAIを得る。ＡAIの有効性を検査した後に、ＣＡはステップ２を継続する。
３．（γA、ｋA、ＩA）は、公開チャネルによって送信することができる。
【０２５９】
方式３．ａ、３．ｃ、および３．ｄの長所は、βが固定されているのでユーザーＡがＫを簡単に計算できることと、ｋAが暗号化され、他人がそれを知ることができなくなっていることである。実際に、ｋAが知れわたることが、証明書方式のセキュリティを低下させない。ｋAを暗号化する目的は、エンティティが確実にｋを知るようにするためである。したがって、方式３．ａ〜３．ｄについて、証明書方式で注２で説明した方法を使用するならば、ＤＥＳ暗号化部分を除去することができ、
【０２６０】
【数１０２】
【０２６１】
をｋAで置換することができる。
【０２６２】
上の方式の送信帯域幅を節約するために、γAの代わりにｆ＝Ｆ（γA、ＩA、ＯＰ）を送信することによって上の方式を変更することができる（一般に、γAのサイズは１６０ビットより大きく、ｆはちょうど１６０ビットであることに留意されたい）。下の方式４．ｃは、方式３．ｃの変形形態である。
【０２６３】
方式４．ｃ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２６４】
【数１０３】
【０２６５】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０２６６】
【数１０４】
【０２６７】
を計算し、３つ組
【０２６８】
【数１０５】
【０２６９】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０２７０】
【数１０６】
【０２７１】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、γA＝αaβ-f（ｍｏｄ ｐ）を計算し、ｆ＝Ｆ（γA、ＩA、ＯＰ）であるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
さらに、方式５．ｃに従うことによって、帯域幅を減らすことができる。
【０２７２】
方式５．ｃ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２７３】
【数１０７】
【０２７４】
を計算し、
【０２７５】
【数１０８】
【０２７６】
をγAの最初の８０個の最下位ビットとしてセットする。その後、
【０２７７】
【数１０９】
【０２７８】
およびｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝（αk）c（ｍｏｄ ｐ）および
【０２７９】
【数１１０】
【０２８０】
を計算し、３つ組
【０２８１】
【数１１１】
【０２８２】
をＡに送信する。
【０２８３】
注：
【０２８４】
【数１１２】
【０２８５】
は、公開チャネルによって送信することができる。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【０２８６】
【数１１３】
【０２８７】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、
【０２８８】
【数１１４】
【０２８９】
、γA＝αaβ-f（ｍｏｄ ｐ）を計算し、γAの最初の８０個の最下位ビットが
【０２９０】
【数１１５】
【０２９１】
であるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式５．ｃのセキュリティ・レベルは、前に述べた他の方式ほどではない。方式５．ｃは、８０ビットのセキュリティだけを有する。しかし、現在の実用的なアプリケーションにはこれでよい。最初の８０個の最下位ビットを、γAの半分の下位ビットに拡張することができる。
【０２９２】
内在的証明書は、情報にオプション・パラメータＯＰを含めることによって、他の有用な情報を証明するのに使用することができる。たとえば、
【０２９３】
【数１１６】
【０２９４】
である。ここで、αEは、Ａのもう１つの秘密鍵であり、
【０２９５】
【数１１７】
【０２９６】
は、対応する公開鍵である。下の方式６．ｃは、方式２．ｃの変形形態である。他の方式を、同一の形で変更することができる。
【０２９７】
方式６．ｃ：
１．Ａは、整数ａEをランダムに選択し、
【０２９８】
【数１１８】
【０２９９】
を計算する。
２．Ａは、整数ｋをランダムに選択し、αkを計算し、αkおよび
【０３００】
【数１１９】
【０３０１】
をＣＡに送信する。
【０３０２】
３．ＣＡは、整数ｃAをランダムに選択し、
【０３０３】
【数１２０】
【０３０４】
を計算し（たとえば
【０３０５】
【数１２１】
【０３０６】
）、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
その後、ＣＡは、
【０３０７】
【数１２２】
【０３０８】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
４．Ａは、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算し（ａ＝０、１の場合には、ステップ１に戻る）、
【０３０９】
【数１２３】
【０３１０】
を計算する。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密署名鍵であり、αがＡのジェネレータ、αaがＡの公開署名鍵である。ａEがＡの秘密暗号化鍵、
【０３１１】
【数１２４】
【０３１２】
がＡの公開暗号化鍵である。Ａは、公開ドメインで
【０３１３】
【数１２５】
【０３１４】
を公開する。
５．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
注：（方式４．ｃ、５．ｃ、６．ｃについて）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、方式３．ｃの注２に記載の方法によって行うことができる。
【０３１５】
【数１２６】
【０３１６】
または
【０３１７】
【数１２７】
【０３１８】
または（γA1、ｋA、ＩA）を、公開チャネルによって送信することができる。
【０３１９】
ＣＡ連鎖（ＣＡ ｃｈａｉｎｉｎｇ）方式
ＣＡ連鎖構造を実施するために、すなわち、ＣＡ１がＣＡ２を認証し、ＣＡ２がＣＡ３を認証し、ＣＡ３がユーザーＡを認証する。この節では、ＣＡ連鎖内に３つのＣＡがある例を提示する。基本方式３’を使用して、この例を実証する。
【０３２０】
システム・セットアップ：
最上位の信頼できる当事者ＣＡ１は、大きい素数ｑについてｐ＝ｔｑ＋１である適当な素数ｐと、オーダー（位数）ｑのジェネレータαを選択する。ＣＡ１は、その秘密鍵として１≦ｃ1≦ｑ−１のランダムな整数ｃ1を選択し、公開鍵
【０３２１】
【数１２８】
【０３２２】
を計算し、（β1、α、ｐ、ｑ）を公開する。
フェーズ１ ＣＡ２が、ＣＡ１からの内在的に証明される公開鍵を問い合わせる。
１．ＣＡ２は、整数ｋ2をランダムに選択し、
【０３２３】
【数１２９】
【０３２４】
を計算し、これをＣＡ１に送信する。
【０３２５】
２．ＣＡ１は、一意の区別される名前またはアイデンティティＩCA2および、１≦ｃCA2≦ｑ−１のランダムな整数ｃCA2を選択する。次に、ＣＡ１は、
【０３２６】
【数１３０】
【０３２７】
を計算する（γCA2は、ＣＡ２の公開鍵再構成公開データである）。
３．ＣＡ１は、関数ｆ1＝Ｆ（γCA2、ＩCA2）を選択し、ｋCA2を計算する（ｋCA2＝０の場合には、ステップ２で別のｃCA2を選択し、ｋCA2を再計算する）。
ｋCA2＝ｃ1ｆ1＋ｃCA2（ｍｏｄ ｑ）
４．ＣＡ１が、
【０３２８】
【数１３１】
【０３２９】
を計算し、３つ組（γCA21、ｋCA2、ＩCA2）をＣＡ２に送信する。
５．ＣＡ２が、
【０３３０】
【数１３２】
【０３３１】
を計算する。その後、ｃ2＝ｋCA2＋ｋ2（ｍｏｄ ｑ）がＣＡ２の秘密鍵、αがＣＡ２のジェネレータ、
【０３３２】
【数１３３】
【０３３３】
がＣＡ２の公開鍵になる。ＣＡ２は、公開ドメインで（α、ＩCA2、β1、β2、γCA2、ｐ、ｑ）を公開する。
注：ユーザーがＣＡ２を信頼するときには、β2を直接に使用することができる。
６．誰もが、次式を計算することによって、公開ドメインからＣＡ２の（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
【０３３４】
【数１３４】
【０３３５】
フェーズ２ ＣＡ３が、ＣＡ２からの内在的に証明される公開鍵を問い合わせる。
１．ＣＡ３は、整数ｋ3をランダムに選択し、
【０３３６】
【数１３５】
【０３３７】
を計算し、これをＣＡ２に送信する。
【０３３８】
２．ＣＡ２は、一意の区別される名前またはアイデンティティＩCA3および、１≦ｃCA3≦ｑ−１のランダムな整数ｃCA3を選択する。ＣＡ２が、
【０３３９】
【数１３６】
【０３４０】
を計算する（γCA3は、ＣＡ３の公開鍵再構成公開データである）。
３．ＣＡ２は、関数ｆ2＝Ｆ（γCA3、ＩCA3）を選択し、ｋCA3を計算する（ｋCA3＝０の場合には、ステップ２で別のｃCA3を選択し、ｋCA3を再計算する）。
ｋCA3≡ｃ2ｆ2＋ｃCA3（ｍｏｄ ｑ）
４．ＣＡ２が、
【０３４１】
【数１３７】
【０３４２】
を計算し、３つ組（γCA31、ｋCA3、ＩCA3）をＣＡ３に送信する。
５．ＣＡ３が、
【０３４３】
【数１３８】
【０３４４】
を計算する。その後、ｃ3＝ｋCA3＋ｋ3（ｍｏｄ ｑ）がＣＡ３の秘密鍵、αがＣＡ３のジェネレータ、
【０３４５】
【数１３９】
【０３４６】
がＣＡ３の公開鍵になる。ＣＡ３は、公開ドメインで（α、ＩCA3、β2、β3、γCA3、ｐ、ｑ）を公開する。
【０３４７】
注：エンティティがＣＡ３を信頼するときには、β3を直接に使用することができる。
６．誰もが、次式を計算することによって、公開ドメインからＣＡ３の（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
【０３４８】
【数１４０】
【０３４９】
フェーズ３ ユーザーＡが、ＣＡ３からの内在的に証明される公開鍵を問い合わせる。
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡ３に送信する。
２．ＣＡ３は、一意の区別される名前またはアイデンティティＩAおよび、１≦ｃA≦ｑ−１のランダムな整数ｃAを選択する。ＣＡ３が、
【０３５０】
【数１４１】
【０３５１】
を計算する（γAは、Ａの公開鍵再構成公開データである）。
３．ＣＡ３は、注意深く選択された関数ｆ3＝Ｆ（γA、ＩA）を選択し、ｋAを計算する（ｋA＝０の場合には、ステップ２で別のｃAを選択し、ｋAを再計算する）。
【０３５２】
ｋA≡ｃ3ｆ3＋ｃA（ｍｏｄ ｑ）
４．ＣＡ３は、
【０３５３】
【数１４２】
【０３５４】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
【０３５５】
５．Ａが、
【０３５６】
【数１４３】
【０３５７】
を計算する。その後、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）がＡの秘密鍵、αがＡのジェネレータ、βA＝αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β3、βA、γA、ｐ、ｑ）を公開する。
注：ユーザーがＡを信頼するときには、βAを直接に使用することができる。
【０３５８】
６．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
【０３５９】
【数１４４】
【０３６０】
フェーズ４ ユーザーＡの署名および検証
メッセージＭに署名するために、ユーザーＡは下記を実行する。
１．ランダムにｘを選択し、ｒ＝αx（ｍｏｄ ｐ）を計算する。
２．ｅ＝ｆA＝Ｆ（ｒ，Ｍ）を計算する。ここで、Ｆはなんらかの固定された関数である。
３．ｓ＝ａｅ＋ｘ（ｍｏｄ ｑ）を計算する。
４．Ｍに対する署名は、（ｒ、ｓ）になる。
検証者は、下記を実行する。
１．ＣＡ１、ＣＡ２、ＣＡ３，およびユーザーＡの公開データを得る。
【０３６１】
（α、ＩCA2、ＩCA3、ＩA、β1、β2、β3、βA、γCA2、γCA3、γA、ｐ、ｑ）
２．ユーザーＡの公開鍵を再構成する。
【０３６２】
【数１４５】
【０３６３】
３．ｅ＝ｆA＝Ｆ（ｒ、Ｍ）を計算する。
４．ｒ’＝αsβA-e（ｍｏｄ ｐ）を計算する。
５．ｒ＝ｒ’の場合には、署名が検証される。それと同時に、ＣＡ２、ＣＡ３、およびユーザーＡの（ＩＤに基づく）公開鍵が、内在的に検証される。
【０３６４】
ユーザーＡの公開鍵の再構成には、３つの既知の基底累乗演算および３つの乗算演算だけが必要である。署名が有効なときには、ＣＡ２、ＣＡ３、およびユーザーＡの（ＩＤに基づく）公開鍵が、内在的に検証される。
【０３６５】
注：
１．検証者がＡを信頼する場合には、Ａの公開鍵はβAになる。
２．検証者がＣＡ３を信頼する場合には、Ａの再構成公開鍵は
【０３６６】
【数１４６】
【０３６７】
になる。
【０３６８】
３．検証者がＣＡ２を信頼する場合には、Ａの再構成公開鍵は
【０３６９】
【数１４７】
【０３７０】
になる。
【０３７１】
連署（Ｃｏ−ｓｉｇｎｉｎｇ）方式
以下では、複数のＣＡが１つの内在的証明書に署名できるようにする方式を説明する。これは、基本方式３’を使用して３つのＣＡが証明書に連署する場合によって例示される。
【０３７２】
システム・セットアップ：
ＣＡ１、ＣＡ２、およびＣＡ３が、次の共通のシステム・パラメータを有すると仮定する。（１）大きい素数ｑに対してｐ＝ｔｑ＋１になる素数ｐ、（２）オーダーｑのジェネレータα、（３）注意深く選択された関数ｆ＝Ｆ（γ，（ＩA1＋ＩA2＋ＩA3））。ＣＡ１は、その秘密鍵として１≦ｃ1≦ｑ−１のランダムな整数ｃ1を選択し、公開鍵
【０３７３】
【数１４８】
【０３７４】
を計算し、（β1、α、ｐ、ｑ）を公開する。ＣＡ２は、その秘密鍵として１≦ｃ2≦ｑ−１のランダムな整数ｃ2を選択し、公開鍵
【０３７５】
【数１４９】
【０３７６】
を計算し、（β2、α、ｐ、ｑ）を公開する。ＣＡ３は、その秘密鍵として１≦ｃ3≦ｑ−１のランダムな整数ｃ3を選択し、公開鍵
【０３７７】
【数１５０】
【０３７８】
を計算し、（β3、α、ｐ、ｑ）を公開する。
【０３７９】
ステップ１ Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡ１、ＣＡ２、およびＣＡ３に送信する。
ステップ２ ＣＡが、情報を交換し、内在的証明書を計算する。
【０３８０】
フェーズ１
１．ＣＡ１が、一意の区別される名前またはアイデンティティＩA1および、１≦ｃA1≦ｑ−１のランダムな整数ｃA1を選択し、
【０３８１】
【数１５１】
【０３８２】
を計算し、（
【０３８３】
【数１５２】
【０３８４】
）をＣＡ２およびＣＡ３に送信する。
２．ＣＡ２が、一意の区別される名前またはアイデンティティＩA2および、１≦ｃA2≦ｑ−１のランダムな整数ｃA2を選択し、（
【０３８５】
【数１５３】
【０３８６】
）を計算し、
【０３８７】
【数１５４】
【０３８８】
をＣＡ１およびＣＡ３に送信する。
【０３８９】
３．ＣＡ３が、一意の区別される名前またはアイデンティティＩA3および、１≦ｃA3≦ｑ−１のランダムな整数ｃA3を選択し、
【０３９０】
【数１５５】
【０３９１】
を計算し、
【０３９２】
【数１５６】
【０３９３】
をＣＡ１およびＣＡ２に送信する。
【０３９４】
フェーズ２
１．ＣＡ１が、
【０３９５】
【数１５７】
【０３９６】
を計算し（γは、Ａの公開鍵再構成公開データである）、ｆ＝Ｆ（γ、（ＩA1＋ＩA2＋ＩA3））を計算し、ｋA1を計算する（ｋA1＝０の場合、フェーズ１に戻る）。
ｋA1≡ｃ1ｆ＋ｃA1（ｍｏｄ ｑ）
ＣＡ１は、
【０３９７】
【数１５８】
【０３９８】
を計算し、３つ組（γA11、ｋA1、ＩA1）をＡに送信する。
２．ＣＡ２が、
【０３９９】
【数１５９】
【０４００】
を計算し（γは、Ａの公開鍵再構成公開データである）、ｆ＝Ｆ（γ、（ＩA1＋ＩA2＋ＩA3））を計算し、ｋA2を計算する（ｋA2＝０の場合、フェーズ１に戻る）。
ｋA2≡ｃ2ｆ＋ｃA2（ｍｏｄ ｑ）
ＣＡ２は、
【０４０１】
【数１６０】
【０４０２】
を計算し、３つ組（γA21、ｋA2、ＩA2）をＡに送信する。
【０４０３】
３．ＣＡ３が、
【０４０４】
【数１６１】
【０４０５】
を計算し（γは、Ａの公開鍵再構成公開データである）、ｆ＝Ｆ（γ、（ＩA1＋ＩA2＋ＩA3））を計算し、ｋA3を計算する（ｋA3＝０の場合、フェーズ１に戻る）。
ｋA3≡ｃ3ｆ＋ｃA3（ｍｏｄ ｑ）
ＣＡ３は、
【０４０６】
【数１６２】
【０４０７】
を計算し、３つ組（γA31、ｋA3、ＩA3）をＡに送信する。
ステップ３ Ａが、内在的に連署された秘密鍵および公開鍵再構成情報を計算する。
１．Ａは、ａ＝ｋA1＋ｋA2＋ｋA3＋ｋ（ｍｏｄ ｑ）を計算する（ａが０または１の場合には、ステップ１に戻る）。
２．Ａが、
【０４０８】
【数１６３】
【０４０９】
およびｆ＝Ｆ（γ、（ＩA1＋ＩA2＋ＩA3））を計算する。その後、αa＝（β1β2β3）fγ（ｍｏｄ ｐ）であるかどうかを検証する。
３．ここで、ａがＡの内在的に連署された秘密鍵、αがＡのジェネレータ、ＩA＝ＩA1＋ＩA2＋ＩA3がＡの共通ＩＤ、（β1β2β3）fγがＡの内在的に共同証明される公開鍵である。
４．Ａは、公開ドメインで（α、ＩA1、ＩA2、ＩA3、β1、β2、β3、γ、ｐ、ｑ）を公開する。
【０４１０】
５．誰もが、（β1β2β3）fγ（ｍｏｄ ｐ）を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に共同証明された公開鍵を得ることができる。
【０４１１】
応用例
以下の例は、ＣＡの署名方程式として方式３（または方式７’）に関して示される。というのは、この方式では全員が同一のジェネレータを共用するからである。各ユーザーは、ＣＡがシステム・パラメータ（ｐ、ｑ、ｄ）を使用し、各ユーザーが同一のジェネレータを有する限り、異なるＣＡを有することができる。
【０４１２】
セット・アップ：
ＣＡ１： システム・パラメータ（α、β1、ｐ、ｑ、ｄ）
アリスが、秘密鍵ａ、ジェネレータαを有し、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
ＣＡ２： システム・パラメータ（α、β2、ｐ、ｑ）
ボブが、秘密鍵ｂ、ジェネレータαを有し、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
ＭＴＩ／Ｃ０鍵共有プロトコルを使用して、本発明の新方式を使用する方法の実例を示す。アリスとボブが鍵交換を実行したいと思っていると仮定する。
【０４１３】
ＭＴＩ／Ｃ０プロトコル
１．アリスは、ボブの公開鍵
【０４１４】
【数１６４】
【０４１５】
を再構成し、整数ｘをランダムに選択し、（αb）xを計算し、ボブに送信する。
【０４１６】
２．ボブは、アリスのの公開鍵
【０４１７】
【数１６５】
【０４１８】
を再構成し、整数ｙをランダムに選択し、（αa）yを計算し、アリスに送信する。
【０４１９】
３．アリスは、共有鍵（shared key）
【０４２０】
【数１６６】
【０４２１】
を計算する。
【０４２２】
４．ボブは、共有鍵（shared key）
【０４２３】
【数１６７】
【０４２４】
を計算する。
【０４２５】
これは２パス・プロトコルである。本発明の内在的証明書方式を用いると、各当事者は、３つの累乗演算を実行するだけで共有鍵（shared key）を得ると同時に、認証鍵共有および内在的公開鍵検証を実行する。
【０４２６】
以下は、サインクリプション（signcryption）方式の例である。ＣＡの署名方程式として方式３（または方式７）を使用する。というのは、この方式では、全員が同一のジェネレータを共用するからである。その後の方式では、ＣＡの署名方程式として方式１３を使用する。この節のすべての方式について、各ユーザーは、ＣＡが同一のシステム・パラメータ（ｐ、ｑ、α）を使用し、各ユーザーが同一のジェネレータを使用する限り、異なるＣＡを有することができる。
【０４２７】
セット・アップ：
ＣＡ１： システム・パラメータ（α、β1、ｐ、ｑ）
アリス： 秘密鍵ａ、ジェネレータα、および公開ドメインの（α、ＩA、β1、γA、ｐ、ｑ）。
ＣＡ２： システム・パラメータ（α、β2、ｐ、ｑ）
ボブ： 秘密鍵ｂ、ジェネレータα、および公開ドメインの（α、ＩB、β2、γB、ｐ、ｑ）。
ボブは、署名され暗号化されたメッセージＭをアリスに送信したいと思っている。
【０４２８】
サインクリプション・プロトコル１：
ボブが、署名され暗号化されたメッセージＭをアリスに送信したいと思っていると仮定する。
ボブは、下記を実行する。
１．アリスの公開鍵
【０４２９】
【数１６８】
【０４３０】
を再構成する。
２．整数ｘをランダムに選択し、鍵ｒ＝（αa）x（ｍｏｄ ｐ）を計算する。
３．Ｃ＝ＤＥＳr（Ｍ）を計算する。
４．ｅ＝ｈａｓｈ（Ｃ ＩA）を計算する。
５．ｓ＝ｂｅ＋ｘ（ｍｏｄ ｑ）を計算する。
６．対（Ｃ、ｓ）をアリスに送信し、したがって、Ｃは、暗号化されたメッセージであり、ｓは、署名である。
【０４３１】
メッセージを復元するために、アリスは下記を実行する。
１．ｅ＝ｈａｓｈ（Ｃ ＩA）を計算する。
２．ボブの公開鍵
【０４３２】
【数１６９】
【０４３３】
を再構成する。
３．αas（αb）-ac（ｍｏｄ ｐ）を計算する。これはｒである。
４．メッセージＭ＝ＤＥＳr（Ｃ）を非暗号化する。
５．冗長性に関する検査を行う。
したがって、ボブは、２回の累乗演算だけを行い、アリスは、３回の累乗演算を行う。しかし、アリスとボブの両方が、お互いの認証を確信している。この方式の場合、メッセージＭが、なんらかの冗長性またはパターンを有しなければならないことに留意されたい。
【０４３４】
サインクリプション・プロトコル２（一般的な場合）：
セット・アップ：
ＣＡ１： システム・パラメータ（α、β1、ｐ、ｑ）
アリス： 秘密鍵ａ、ジェネレータα、および公開ドメインの（α、ＩA、β1、γA、ｐ、ｑ）。
ＣＡ２： システム・パラメータ（α、β2、ｐ、ｑ）
ボブ： 秘密鍵ｂ、ジェネレータα、および公開ドメインの（α、ＩB、β2、γB、ｐ、ｑ）。
【０４３５】
注：このセット・アップは、内在的証明書用である。通常の証明書方式システムの場合、アリスとボブが同一のジェネレータを有することだけが必要である。
【０４３６】
アリスへのメッセージをサインクリプト(signcrypt)するために、ボブは下記を実行する。
【０４３７】
１．アリスの公開鍵αaを得る（内在的証明書方式の場合、アリスの公開鍵
【０４３８】
【数１７０】
【０４３９】
を再構成する）。
２．整数ｘをランダムに選択し、ｒ＝（αa）x（ｍｏｄ ｐ）を計算する。
３．Ｃ＝ＤＥＳr（Ｍ）を計算する。
４．ｅ＝ｈａｓｈ（Ｃ‖αa）を計算する。
５．ｓ＝ｂｅ＋ｘ（ｍｏｄ ｑ）を計算する。
６．（Ｃ、ｓ）をアリスに送信する。Ｃは、暗号化されたメッセージであり、ｓは、署名である。
メッセージを復元するために、アリスは下記を実行する。
１．ｅ＝ｈａｓｈ（Ｃ‖αa）を計算する。
２．ボブの公開鍵αbを得る（内在的証明書方式の場合、ボブの公開鍵
【０４４０】
【数１７１】
【０４４１】
を再構成する）。
３．αas（αb）-ae（ｍｏｄ ｐ）を計算する。これはｒである。
４．メッセージＭ＝ＤＥＳr（Ｃ）を非暗号化する。
【０４４２】
注：
１．証明書方式が、本明細書に記載の内在的証明書でない場合には、アリスおよびボブの公開鍵を検証しなければならない。
２．メッセージＭが、なんらかの冗長性またはパターンを有しなければならない。
【０４４３】
３．１つの値ｒを知っているアリスは、値αabが露出されるので、ボブからアリスへのすべてのメッセージを非暗号化することができる。
４．一般に、ハッシュｅにオプション・パラメータを含めなければならない、すなわち、ｅ＝ｈａｓｈ（Ｃ‖αa‖ＯＰ）。たとえば、ＯＰ＝αbまたはＯＰ＝αb‖β1‖β2。
【０４４４】
上のサインクリプション方式は、署名者が自分の秘密署名鍵を失った場合に、その署名者がサインクリプトしたすべてのメッセージが公衆に露出されるという短所を有する。事後暗号化の保護のために、新しいサインクリプション方式を提案する。新方式では、各ユーザーが、２対の鍵を有し、１対は署名鍵用、もう１対は暗号化鍵である。新方式は、あらゆる証明書方式と共に使用することができる。しかし、本発明の内在的証明書方式と共に使用される場合に、新方式は最も効果的になる。
【０４４５】
サインクリプション・プロトコル３（一般的な場合）：
セット・アップ：
アリス： 秘密署名鍵ａ、秘密暗号化鍵ａE、ジェネレータα、および公開ドメインの
【０４４６】
【数１７２】
【０４４７】
。
【０４４８】
ＣＡ２： システム・パラメータ（α、β2、ｐ、ｑ）
ボブ： 秘密署名鍵ｂ、秘密暗号化鍵ｂE、ジェネレータα、および公開ドメインの
【０４４９】
【数１７３】
【０４５０】
。
注：このセット・アップは、方式６．ｃを使用する内在的証明書用である。通常の証明書方式システムの場合、アリスとボブが同一のジェネレータを有することだけが必要である。
【０４５１】
アリスへのメッセージをサインクリプトするために、ボブは下記を実行する。
【０４５２】
１ アリスの公開署名鍵αaおよび公開暗号化鍵
【０４５３】
【数１７４】
【０４５４】
を得る（内在的証明書方式の場合、アリスの公開署名鍵
【０４５５】
【数１７５】
【０４５６】
を再構成する）。
２ 整数ｘをランダムに選択し、
【０４５７】
【数１７６】
【０４５８】
を計算する。
３ Ｃ＝ＤＥＳr（Ｍ）を計算する。
４
【０４５９】
【数１７７】
【０４６０】
を計算する。
５ ｓ＝ｂｅ＋ｘ＋ｂE（ｍｏｄ ｑ）を計算する。
６ （Ｃ、ｓ）をアリスに送信する。Ｃは、暗号化されたメッセージであり、ｓは、署名である。
メッセージを復元するために、アリスは下記を実行する。
【０４６１】
１．
【０４６２】
【数１７８】
【０４６３】
を計算する。
２．ボブの公開署名鍵αbおよび公開暗号化鍵
【０４６４】
【数１７９】
【０４６５】
を得る（内在的証明書方式の場合、ボブの公開署名鍵
【０４６６】
【数１８０】
【０４６７】
を再構成する）。
３．
【０４６８】
【数１８１】
【０４６９】
を計算する。これはｒである。
４．メッセージＭ＝ＤＥＳr（Ｃ）を非暗号化する。
【０４７０】
注：
１．受信者アリスの秘密鍵がａ＋ａEであると考えることができる。これは、受信者が、２つの秘密鍵ではなく１つの秘密鍵だけを必要とすることを意味する。しかし、送信者ボブは、２つの秘密鍵を必要とする。通常の証明書の場合、受信者は、１つの秘密鍵だけを必要とする。
２．証明書方式が、本明細書に記載の内在的証明書でない場合には、アリスおよびボブの公開鍵を検証しなければならない。
３．メッセージＭが、なんらかの冗長性またはパターンを有しなければならない。
４．
【０４７１】
【数１８２】
【０４７２】
の中のパラメータＯＰは、空またはＯＰ＝β1‖β2とすることができる。
５．１つのｒの値を知っても、ポスト・メッセージの情報は明らかにならない。
６．内在的証明書方式を用いると、ボブは、２回の累乗演算だけを実行し、アリスは、４回の累乗演算を実行する。しかし、双方が認証部分（authentification part）であることを、アリスとボブの双方は秘密にしている（are confidential）。
７．誰かがアリスの秘密鍵ａ＋ａEを知るか、ボブが両方の秘密鍵を失った場合、事後暗号化されたメッセージを保護することはできない。
【０４７３】
通常の署名の場合、１つの問題は、署名者が、自分がその署名を署名したことを否定することである。これを否認（repudiation）と呼ぶ。上のプロトコル１および２は、ジャッジ(judge)を信頼するならば、否認拒否機能（non-repudiationfeature）を有する。すなわち、署名者は、自分がサインクリプトされた(signcrypted)メッセージに署名したことを拒否することができない。プロトコル３は、ジャッジが信頼されないときであっても否認拒否機能を有する。次のプロトコルで、ボブが署名を拒否したい場合にジャッジがどのように判断するかを示す。
【０４７４】
否認拒否プロトコル：
１．アリスが（Ｃ、ｓ）をジャッジに送信する。
２．ジャッジは、
【０４７５】
【数１８３】
【０４７６】
を計算する（注：アリスおよびボブの２対の公開鍵を検証しなければならない。内在的証明書方式の場合、再構成公開データから公開鍵を計算しなければならない）。
３．ジャッジは、２つの整数ｒ1およびｒ2をランダムに選択し、
【０４７７】
【数１８４】
【０４７８】
を計算し、Ｌをアリスに送信する。
４．アリスは、
【０４７９】
【数１８５】
【０４８０】
を計算し、ジャッジに送り返す。
５．ジャッジは、
【０４８１】
【数１８６】
【０４８２】
を計算し、Ｍ＝ＤＥＳr（Ｃ）によってメッセージを復元する。
６．Ｍが正しいフォーマットを有する場合、（Ｃ、ｓ）はボブによってサインクリプトされたものに違いない。
７．ジャッジは、判断を行った後に、値
【０４８３】
【数１８７】
【０４８４】
をアリスおよびボブに送信して、自分の判断を確認する。
【０４８５】
他の２つのサインクリプション・プロトコルの場合、否認拒否（non-repudiation）プロトコルは、ジャッジが完全に信頼されるならば類似したものになる。
【０４８６】
結論として、本発明の方式は、ユーザーの秘密鍵を計算に直接に使用しなければならないアプリケーション・プロトコルと組み合わされたときに、内在的に証明される、ＩＤに基づくユーザーの公開鍵を提供する。これらの方式は、鍵認証センタ（Key Authentication Center、ＫＡＣ）が、内在的に証明される公開鍵をユーザーに配送するのに使用することもできる。
【０４８７】
内在的に証明される公開鍵のもう１つの応用例は、認証機関のビット強度が、証明されるユーザーまたはエンティティの公開鍵と同一であることである。ビット強度によって、相対的な鍵サイズおよび関係するエンティティの処理能力が暗示される。
【０４８８】
この問題に対処する手法の１つが、Ｘ．５０９証明書で指定されるものなどの従来の証明書構造に、内在的に証明される公開鍵を埋め込むことである。この場合、証明書に対する署名は、内在的に証明される公開鍵より高いビット強度になる。したがって、ＣＡは、２つの異なるセキュリティ・レベルでユーザー公開鍵を証明している。公開鍵を取り出す他のエンティティは、受け入れたいセキュリティ・レベルについて決定することができる。一部の応用分野では、必要な性能をもたらすために、内在的な値（implicit value）によって提供される、より低いレベルだけが必要になる可能性がある。
【０４８９】
本発明の特定の実施形態および特定の用途に関して本発明を説明してきたが、請求項に記載された本発明の趣旨から逸脱せずに、当業者は本発明のさまざまな変更形態を思い浮かべるであろう。たとえば、好ましい実施形態の上の説明では、乗法表現（multiplicative notation）を利用したが、本発明の方法は、加法表現（additive notation）を使用しても同様に良好に説明することができる。たとえば、ＥＣＤＳＡで実施された楕円曲線アルゴリズムがＤＳＡと同等であることは周知であり、そして、楕円曲線は離散対数アルゴリズムに類似することは、モジュロ素数の整数（integersmoduro a prime）の乗法群Ｆp*の設定（setting）で通常記述される。群Ｆp*および楕円曲線群Ｅ（Ｆq）の要素および演算の間には対応関係がある。さらに、この署名技法は、ＦpおよびＦ2”上で定義されるフィールド（field）の中で実行される関数にも同様に良好に適用可能である。また、上で説明したＤＳＡ署名方式は、当技術分野で既知の一般化されたＥｌＧａｍａｌ署名方式の特定の実例（specificinstance）であり、したがって、本発明の技法がこれに適用可能であることに留意されたい。
【技術分野】
【０００１】
（発明の分野）
本発明は、暗号化鍵の転送および認証のための鍵配送方式に関する。
【背景技術】
【０００２】
（発明の背景）
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有（Diffie-Hellman key agreement）は、暗号システムでの鍵配送問題（Key distribution problem）に対する最初の実用的な解決策をもたらした。この鍵共有プロトコルでは、事前に会ったことも共有（分散）鍵材料（sharedkey material）を有したこともない２つの当事者が、オープンな（保護されない）チャネルを介してメッセージ（文書）を交換することによって、共有される秘密（sharedsecret）を確立することができる。セキュリティは、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題の扱い難さと、関連する離散対数の計算問題にかかっている。
【０００３】
インターネットおよび類似物の出現に伴って、公開鍵（Public key；パブリック・キー）および公開鍵証明書（Public key certificate）の大規模な配送の必要が、ますます重要になりつつある。公開鍵証明書は、それによって、検出不能な改ざんの危険性（dangerof undetectable manipulation）なしに、保護されない媒体（unsecured media）を介して公開鍵を格納、配送、または転送することのできる媒介物（vehicle）である。その目的は、一方の当事者の公開鍵を他方の当事者が入手できるようにし、その認証性（authenticity）および有効性（validity）を検証可能に（verfiable）することである。
【０００４】
公開鍵証明書は、データ部分および署名部分からなるデータ構造を有する。データ部分には、最低限として公開鍵およびそれに関連する当事者を識別する文字列を含む平文データが含まれる。署名部分は、データ部分に対する認証機関（certification authority、ＣＡ）のディジタル署名からなり、これによって、エンティティのアイデンティティ（identity;個人情報）が、指定された公開鍵と結びつけられる。ＣＡは信頼できる第三者であり、証明書のＣＡの署名は対象のエンティティに結びつけられた公開鍵の認証性（Authenticity）を保証する。
【０００５】
アイデンティティに基づくシステム（ＩＤに基づくシステム）は、通常の公開鍵システムに類似し、秘密変換（private transformation）と公開変換(public transformation)を用いるが、当事者は、以前のように明示的な公開鍵を有しない。その代わりに、公開鍵は、効果的に、一般に入手可能な当事者のアイデンティティ情報（たとえば氏名またはネットワーク・アドレス）に置換される。当事者を一意に識別し、その当事者に否定不能な形で（undeniably）関連付けることができる、一般に入手可能な情報であれば、どのような情報でもアイデンティティ情報として使用可能である。
【０００６】
公開鍵配送の代替手法では、内在的に証明される公開鍵（Implicitly certified public keys）が使用される。この場合、明示的なユーザー公開鍵が存在するが、その鍵は、証明書に基づくシステムのように公開鍵証明書（public-keycertificate）によって運ばれるのではなく、再構成（reconstruct）されなければならない。したがって、内在的に証明される公開鍵は、公開鍵（たとえばＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵）を配送するための代替手段として使用することができる。
【０００７】
内在的に証明される公開鍵機能の１例が、Ｇｕｎｔｈｅｒの内在的に証明される（ＩＤに基づく）公開鍵方法である。この方法では、
１．信頼できるサーバＴ（trusted server）が、適当な固定された公開の素数ｐ、およびＺp*のジェネレータαを選択する。Ｔは、１≦ｔ≦ｐ−２かつｇｃｄ（ｔ，ｐ−１）＝１であるランダムな整数ｔをその秘密鍵（privatekey）として選択し、公開鍵ｕ＝αt ｍｏｄ ｐをαおよびｐと共に公開する。
【０００８】
２．Ｔは、各当事者Ａに、一意の名前または識別する文字列ＩAおよび、ｇｃｄ（ｋA、ｐ−１）＝１であるランダムな整数ｋA、を割り当てる。Ｔは、その後、
【０００９】
【数１】
【００１０】
を計算する。ＰAは、Ａの鍵再構成公開データであり、これを用いて、他の当事者が、以下で示すように（ＰA）aを計算することができるようになる。
【００１１】
３．適当なハッシュ関数ｈを使用して、Ｔは、ａについて下の式を解く。
Ｈ（ＩA）≡ｔ．ＰA＋ｋAａ（ｍｏｄ ｐ−１）
４．Ｔは、ＩAに対するＴのＥｌＧａｍａｌ署名である対（ｒ，ｓ）＝（ＰA，ａ）を、保護された形でＡに送信する（ａは、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有のためのＡの秘密鍵である）。
【００１２】
５．他の当事者は、次式を計算することによって、一般に入手可能な情報（α、ＩA、ｕ、ＰA、ｐ）だけから、ＡのＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ公開鍵ＰAαを再構成することができる。
【００１３】
【数２】
【００１４】
したがって、離散対数問題の場合、証明書への署名は１回の累乗（exponentiation）演算を必要とするが、ＩＤに基づく内在的に証明される公開鍵の再構成は、２回の累乗が必要である。群（group）Ｚp*での累乗およびＥ（Ｆｑ）内の点のアナログ・スカラ乗算は、計算量的に強烈（computationallyintensive）であることが既知である。たとえば、ＲＳＡ方式は、楕円曲線システムと比較して極端に低速である。しかし、ＲＳＡタイプのシステムに対するＥＣシステムの明確な効率にもかかわらず、これは、特に「スマート・カード」、ポケット・ベル、および類似物などの限られた計算能力を有するコンピューティング装置にとって、まだ問題である。
【発明の概要】
【課題を解決するための手段】
【００１５】
（発明の概要）
本発明は、既存の方式に対して改良された計算速度をもたらす、効率的なＩＤに基づく内在的証明書方式の提供を試みる。便宜上、本明細書ではＺpに対する方式を説明するが、これらの方式は、楕円曲線暗号システムでも同等に実施可能である。
【００１６】
本発明によれば、少なくとも１つの信頼できるエンティティＣＡおよび加入者エンティティＡを有する保護されたディジタル通信システム内でアイデンティティに基づく公開鍵を生成する方法であって、
（ａ）各エンティティＡについて、ＣＡが、エンティティＡを区別する一意のアイデンティティＩAを選択するステップと、
（ｂ）信頼できる当事者ＣＡのジェネレータをエンティティＡの私的な値（private value）と数学的に組み合わせ、対（ＩA、γA）がＡの内在的証明書として働くようにすることによって、エンティティＡの公開鍵再構成公開データγAを生成するステップと、
（ｃ）エンティティ情報ｆを導出するために、数学関数Ｆ（γA、ＩA）に従って内在的証明書情報（ＩA、γA）を組み合わせるステップと、
（ｄ）エンティティ情報ｆに署名することによってエンティティＡの秘密鍵を生成するステップと、
秘密鍵をエンティティＡに送信するステップとを含み、
これによって、エンティティＡの公開鍵を、公開情報、ジェネレータγA、およびアイデンティティＩAから比較的効率的に再構成できるようにする方法が提供される。
【００１７】
本発明のもう１つの態様によれば、異なるビット強度（bit strengths）を有する複数の公開鍵を含み、公開鍵の１つが内在的に証明される公開鍵になることを特徴とする、公開鍵証明書が提供される。
例えば、本発明は以下を提供する。
（項目１） 少なくとも１つの信頼できるエンティティＣＡおよび加入者エンティティＡを有する保護されたディジタル通信システムで公開鍵を生成する方法であって、
（ａ）各エンティティＡについて、前記ＣＡが、前記エンティティＡを区別する一意のアイデンティティＩAを選択するステップと、
（ｂ）前記信頼できる当事者ＣＡのジェネレータを前記エンティティＡの私的な値（private value）と数学的に組み合わせてエンティティＡの公開鍵再構成公開データγAを生成するステップであって、前記対（ＩA、γA）がＡの内在的証明書（implicitcertificate）として働くように前記γAを生成するステップと、
（ｃ）数学関数Ｆ（γA、ＩA）に従って前記内在的証明書情報（ＩA、γA）を組み合わせてエンティティ情報ｆを導出するステップと、
（ｄ）前記エンティティ情報ｆに署名することによって前記エンティティＡの秘密鍵（private key）を生成するステップと
前記秘密鍵を前記エンティティＡに送信するステップとを備え、
これによって、前記エンティティＡの公開鍵は、前記公開情報、前記ジェネレータγA、および前記アイデンティティＩAから比較的効率的に再構成されることできることを特徴とする公開鍵の生成する方法。
（項目２） ディジタル通信システムにおける公開鍵証明書を生成する方法であって、
（ａ）公開鍵暗号アルゴリズムに従って、公開鍵証明書を生成するステップと、
（ｂ）複数の公開鍵であって、前記公開鍵の少なくとも１つが、内在的に署名される公開鍵（implicitly signed public key）である前記複数の公開鍵を公開鍵証明書内に埋め込むステップと、
（ｃ）前記証明書を公開するステップと
を含むとを特徴とする公開鍵証明書の生成方法。
（項目３） 信頼できるエンティティＣＡによって加入者エンティティＡの公開鍵証明書を生成する方法であって、
ａ）前記加入者エンティティＡの一意のアイデンティティ情報ＩAを選択するステップと、
ｂ）前記加入者エンティティＡの私的な値ｃAを生成するステップと、
ｃ）前記私的な値（private value）ｃAから前記エンティティＡの公開値γAを生成するステップと、
ｄ）値ｆを生成するために、暗号関数内で前記公開値γAおよび前記アイデンティティ情報ＩAを使用するステップと、
ｅ）署名ａを作るために前記値ｆに署名するステップと、
ｆ）前記署名ａ、公開値γA、および前記アイデンティティ情報ＩAを前記加入者エンティティに送信するステップと
を含むとを特徴とする公開鍵証明書の生成方法。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態に従って構成された第１のシステムの概略図である。
【図２】本発明の実施形態に従って構成された第２のシステムの概略図である。
【発明を実施するための形態】
【００１９】
（好ましい実施形態の詳細な説明）
図１を参照すると、内在的に証明される公開鍵（Implicitly certified public key）を有するシステムが、全般的に符号１０によって示されている。このシステム１０には、信頼できる第三者のＣＡおよび、少なくとも第１通信者Ａおよび第２通信者Ｂの対が含まれる。通信者ＡおよびＢは、通信チャネルを介して情報を交換し、通信者ＡおよびＢのそれぞれには、認定／検証（finding/verification）および暗号化／非暗号化（解読）（encryption/decryption）を実行する暗号装置（cryptographicunit）が含まれる。
【００２０】
図１を参照すると、信頼できる当事者ＣＡは、大きい素数ｑについてｐ＝ｔｑ＋１である適当な素数ｐと、オーダー（order）ｑのジェネレータαを選択する。ＣＡは、その秘密鍵として１≦ｃ≦ｑ−１のランダムな整数ｃを選択し、公開鍵β＝αcを計算し、（β、α、ｐ、ｑ）を公開する。
【００２１】
方式１：
１．各当事者Ａについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１≦ｃA≦ｑ−１のランダムな整数ｃAを選択する。次に、ＣＡは、
【００２２】
【数３】
【００２３】
を計算する（γAは、当事者Ａの公開鍵再構成公開データである。対（ＩA、γA）は、Ａの内在的証明書として働く）。
【００２４】
２．ＣＡは、関数ｆ＝Ｆ（ＩA、γA）を選択する。たとえば、Ｆ（γA、ＩA）＝γA＋ｈ（ＩA）またはＦ（γA、ＩA）＝ｈ（γA＋ＩA）である。ここで、ｈは、安全なハッシュ関数であり、当事者Ａの秘密鍵であるａについて次式を解く。ａ＝０の場合には、ＣＡは、別のｃAを選択し、もう一度次式を解く。
１＝ｃｆ＋ｃAａ（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。ここで、
αは、Ａの秘密鍵であり、
γAは、Ａのジェネレータであり、
【００２５】
【数４】
【００２６】
は、Ａの公開鍵である。
Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算し、したがって公開鍵を導出することによって、公開ドメインから当事者Ａの（ＩＤに基づく）内在的に検証可能な公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
このように上述の式から公開鍵を引き出すことは、ただ１つの累乗演算（exponentiation operation）を必要とする。
【００２７】
誰でも公開データから当事者Ａの公開鍵を再構成することができるが、これは、再構成された公開鍵γAaが証明されたことを意味しない。この方式は、当事者Ａが対応する秘密鍵の完全な知識を有することを示すアプリケーション・プロトコルと組み合わされたときに、より効果的になる。たとえば、ＭＱＶ鍵共有方式またはなんらかの署名方式、特にＫＣＤＳＡ（Korean Certificate based Digital Signature Algorithm）と組み合わされたときである。一般に、この内在的証明書方式は、証明書を検証することを必要とするどの方式とも、共に使用することができる。これは、ＤＳＡ（DigitalSignature Algorithm）署名方式に言及することによって実証することができる。
【００２８】
アリスが、公開鍵α、ジェネレータγAを有し、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開すると仮定する。次に、アリスは、ＤＳＡを使用してメッセージＭに署名しようとする。
アリスは、下記を実行する。
１．ランダムにｋを選択し、ｒ＝γAk（ｍｏｄ ｐ）を計算する。
２．ｅ＝ｓｈａ−１（Ｍ）を計算する。
３．ｓ＝ｋ-1（ｅ＋ａｒ）（ｍｏｄ ｐ）を計算する。
４．Ｍに対する署名は、（ｒ、ｓ）になる。
【００２９】
検証者は、下記を実行する。
１．アリスの公開データ（α、ＩA、β、γA、ｐ、ｑ）を取得し、公開鍵を再構成する。
δA＝γAa＝αβ-1（ｍｏｄ ｐ）
２．ｅ＝ｓｈａ−１（Ｍ）を計算する。
３．ｕ1＝ｅｓ-1（ｍｏｄ ｑ）およびｕ2＝ｒｓ-1（ｍｏｄ ｑ）を計算する。
４．
【００３０】
【数５】
【００３１】
を計算する。
５．ｒ＝ｒ’の場合には、署名が検証される。それと同時に、アリスの（ＩＤに基づく）公開鍵が、内在的に検証される。
【００３２】
対（ＩA、γA）は、アリスの証明書として働く。公開鍵の再構成は、アプリケーション・プロトコルが有効な検証をもたらすときに、内在的検証として働く。公開鍵を取得するために、１回の累乗演算だけが必要であることを想起されたい。
【００３３】
代替実施形態では、署名方程式を適当に変更することによって、この方式をほとんどのＥｌＧａｍａｌ署名方式に一般化することができる。以下の節で、いくつかの例を示す。
【００３４】
方式２：
ＣＡは、署名方程式ｌ＝ｃａ＋ｃAｆ（ｍｏｄ ｑ）を使用する。ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信し、その後、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
この方式では、各ユーザーが、同一のジェネレータβを有し、このβは、ＣＡの公開鍵である。
【００３５】
方式３：
ＣＡは、署名方程式ａ＝ｃｆ＋ｃA（ｍｏｄ ｑ）を使用する。ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信し、その後、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
この方式では、ＣＡを含む各ユーザーが、同一のジェネレータαを有する。
【００３６】
方式４：
ＣＡは、署名方程式ａ≡ｃAｆ＋ｃ（ｍｏｄ ｑ）を使用する。ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信し、その後、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
この方式では、ＣＡを含む各ユーザーが、同一のジェネレータαを有する。
【００３７】
上の方式では、ユーザーまたは当事者Ａは、それ自体の秘密鍵を選択する権利を有しない。図２に示された以下の方式は、ＣＡおよびユーザーの両方が、ユーザーの秘密鍵を制御するが、ユーザーだけがその秘密鍵を知っている。
【００３８】
方式５’：
Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。ＣＡは、
【００３９】
【数６】
【００４０】
を計算し、ｋAについて以下の署名方程式を解く。
１＝ｃｆ＋ｃAｋA（ｍｏｄ ｑ）
その後、ＣＡは、
【００４１】
【数７】
【００４２】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。Ａは、ａ＝ｋAｋ-1（ｍｏｄ ｑ）およびγA＝（γA1）k（ｍｏｄ ｐ）を計算する。その後、ａがＡの秘密鍵、γAがＡのジェネレータ、γAaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
方式６：
１．Ａは、まず、整数ｋをランダムに選択し、βkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００４３】
【数８】
【００４４】
およびｆ＝Ｆ（γA、ＩA）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｋA＋ｃAｆ（ｍｏｄ ｑ）
その後、ＣＡは、
【００４５】
【数９】
【００４６】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
注：（γA1、ｋA、ＩA）は、公開チャネルによって送信することができる。
３．Ａは、
【００４７】
【数１０】
【００４８】
、ｆ＝Ｆ（γA、ＩA）、およびａ＝ｋA−ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、βa＝αγA-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
【００４９】
βa＝αγA-f（ｍｏｄ ｐ）
方式７：
Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。ここでＣＡは、
【００５０】
【数１１】
【００５１】
を計算し、ｋAについて署名方程式を解く。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
その後、ＣＡは、
【００５２】
【数１２】
【００５３】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。Ａは、
【００５４】
【数１３】
【００５５】
を計算する。その後、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）がＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式８：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００５６】
【数１４】
【００５７】
およびｆ＝Ｆ（γA、ＩA）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃAｆ＋ｃ（ｍｏｄ ｑ）
その後、ＣＡは、
【００５８】
【数１５】
【００５９】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
注：（γA1、ｋA、ＩA）は、公開チャネルによって送信することができる。
３．Ａは、
【００６０】
【数１６】
【００６１】
、ｆ＝Ｆ（γA、ＩA）およびａ＝ｋA＋ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝γAfβであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
上の方式５〜８では、ｋAが公開チャネルによって送信されるので、誰もが、ユーザーＡの秘密鍵αの部分的な情報を得ることができる。この情報を隠し、上の方式の計算を高速化するために、ＤＥＳ暗号化を導入して、方式５〜８を変更することによって、以下の方式９〜１２を得た。方式９〜１２の長所は、βが固定されているので、ユーザーが簡単にＫを計算できることである。
【００６２】
方式９：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００６３】
【数１７】
【００６４】
およびｆ＝Ｆ（γA、β、ＩA）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｆ＋ｃAｋA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝（ａk）c（ｍｏｄ ｐ）および
【００６５】
【数１８】
【００６６】
を計算し、３つ組
【００６７】
【数１９】
【００６８】
をＡに送信する。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【００６９】
【数２０】
【００７０】
、およびａ＝ｋAｋ-1（ｍｏｄ ｑ）を計算する（ａ＝１の場合には、ステップ１に戻る）。その後、γAa＝αβ-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、γAがＡのジェネレータ、γAaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
方式１０：
１．Ａは、まず、整数ｋをランダムに選択し、βkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００７１】
【数２１】
【００７２】
およびｆ＝Ｆ（γA、β、ＩA）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｋA＋ｃAｆ（ｍｏｄ ｑ）
次に、ＣＡは、
【００７３】
【数２２】
【００７４】
を計算し、３つ組
【００７５】
【数２３】
【００７６】
をＡに送信する。
注：
【００７７】
【数２４】
【００７８】
は、公開チャネルによって送信することができる。
３．Ａは、
【００７９】
【数２５】
【００８０】
を計算し、ａ＝ｋA−ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、βa＝αγA-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
方式１１：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００８１】
【数２６】
【００８２】
およびｆ＝Ｆ（γA、β、ＩA）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA＝ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝（αk）c（ｍｏｄ ｐ）および
【００８３】
【数２７】
【００８４】
を計算し、３つ組
【００８５】
【数２８】
【００８６】
をＡに送信する。
注：
【００８７】
【数２９】
【００８８】
は、公開チャネルによって送信することができる。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【００８９】
【数３０】
【００９０】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、αa＝γAf（ｍｏｄ ｐ）を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
【００９１】
方式１２：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【００９２】
【数３１】
【００９３】
およびｆ＝Ｆ（γA、β、ＩA）を計算し、ｋA（ｋA＝０の場合には、別のｃAを選択する）ｋA＝ｃAｆ＋ｃ（ｍｏｄ ｑ）を計算する。
次に、ＣＡは、Ｋ＝（αk）c（ｍｏｄ ｐ）および
【００９４】
【数３２】
【００９５】
を計算し、３つ組
【００９６】
【数３３】
【００９７】
をＡに送信する。
注：
【００９８】
【数３４】
【００９９】
は、公開チャネルによって送信することができる。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【０１００】
【数３５】
【０１０１】
、ｆ＝Ｆ（γA、β、ＩA）、およびａ＝ｋA＋ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝γAfβであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
方式９〜１２の長所は、βが固定されているのでユーザーＡがＫを簡単に計算できることと、ｋAが暗号化され、他人がそれを知ることができなくなっていることである。
【０１０２】
方式５〜１２の場合、関数Ｆ（γA、β、ＩA）にオプション・パラメータＯＰを追加すること（すなわち、ｆ＝Ｆ（γA、β、ＩA、ＯＰ）によって、これらの方式がより役立つものになる。たとえば、
【０１０３】
【数３６】
【０１０４】
である。ここでａEは、ユーザーＡの秘密暗号化鍵であり、
【０１０５】
【数３７】
【０１０６】
は、Ａの公開暗号化鍵である。下の方式１５は、方式７の変形形態である。方式５〜１２を、同一の形で変更することができる。方式１〜４も、同一の形で変更することができる。
【０１０７】
方式１３：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０１０８】
【数３８】
【０１０９】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０１１０】
【数３９】
【０１１１】
を計算し、３つ組
【０１１２】
【数４０】
【０１１３】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０１１４】
【数４１】
【０１１５】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、γA＝αaβ-f（ｍｏｄ ｐ）を計算し、ｆ＝Ｆ（γA、ＩA、ＯＰ）であるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
さらに、方式１４に従うことによって、帯域幅（bandwidth）を減らすことができる。
【０１１６】
方式１４：
１．Ａは、まず、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０１１７】
【数４２】
【０１１８】
を計算し、
【０１１９】
【数４３】
【０１２０】
をγAの最初の８０個の最下位ビットとしてセットする。その後、
【０１２１】
【数４４】
【０１２２】
およびｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝（αk）c（ｍｏｄ ｐ）および
【０１２３】
【数４５】
【０１２４】
を計算し、３つ組
【０１２５】
【数４６】
【０１２６】
をＡに送信する。
注：
【０１２７】
【数４７】
【０１２８】
は、公開チャネルによって送信することができる。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【０１２９】
【数４８】
【０１３０】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、
【０１３１】
【数４９】
【０１３２】
、γA＝αaβ-f（ｍｏｄ ｐ）を計算し、γAの最初の８０個の最下位ビットが
【０１３３】
【数５０】
【０１３４】
であるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式５．ｃのセキュリティ・レベルは、前に述べた他の方式ほどではない。方式５．ｃは、８０ビットのセキュリティだけを有する。しかし、現在の実用的なアプリケーションにはこれでよい。最初の８０個の最下位ビットを、γAの半分の下位ビットに拡張することができる。
【０１３５】
内在的証明書は、情報にオプション・パラメータＯＰを含めることによって、他の有用な情報を証明するのに使用することができる。たとえば、
【０１３６】
【数５１】
【０１３７】
である。ここで、ａEは、Ａのもう１つの秘密鍵であり、
【０１３８】
【数５２】
【０１３９】
は、対応する公開鍵である。下の方式１５は、方式７の変形形態である。他の方式も、同一の形で変更することができる。
【０１４０】
方式１５：
１．整数ａEをランダムに選択し、
【０１４１】
【数５３】
【０１４２】
を計算する。
２．Ａは、整数ｋをランダムに選択し、αkを計算し、αkおよび
【０１４３】
【数５４】
【０１４４】
をＣＡに送信する。
３．ＣＡは、整数ｃAをランダムに選択し、
【０１４５】
【数５５】
【０１４６】
および
【０１４７】
【数５６】
【０１４８】
（たとえば
【０１４９】
【数５７】
【０１５０】
）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA＝ｃｆ＋ｃA（ｍｏｄ ｑ）
その後、ＣＡは、
【０１５１】
【数５８】
【０１５２】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
注：（γA1、ｋA、ＩA）は、公開チャネルによって送信することができる。
４．Ａは、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算し（ａ＝０、１の場合には、ステップ１に戻る）、
【０１５３】
【数５９】
【０１５４】
を計算する。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密署名鍵であり、αがＡのジェネレータ、αaがＡの公開署名鍵であり、ａEがＡの秘密暗号化鍵、
【０１５５】
【数６０】
【０１５６】
がＡの公開暗号化鍵である。Ａは、公開ドメインで
【０１５７】
【数６１】
【０１５８】
を公開する。
５．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
注：（方式１３〜１５について）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、方式１１の注２に記載の方法によって行うことができる。
３．
【０１５９】
【数６２】
【０１６０】
または
【０１６１】
【数６３】
【０１６２】
または（γA1、ｋA、ＩA）を、公開チャネルによって送信することができる。
本発明の方式では、（α、γA）は、ＡのＩＤ、ＩAに対するＣＡの署名であり、これは公衆によって知られると思われた。しかし、現在は、ユーザーＡだけがａを知る。したがって、本発明の方式を使用するときには、アプリケーション・プロトコルで、ユーザーＡが自分自身の秘密鍵を知るようにしなければならない。言い換えると、アプリケーション・プロトコルは、Ａが計算に自分の秘密鍵を使用することを保証しなければならない。
【０１６３】
新方式のセキュリティは、署名方程式に依存する。たとえば、方式１では、署名方程式は次式である。
１＝ｃｆ＋ｃAａ（ｍｏｄ ｑ） （１）
以下で、１方向関数Ｆ（γA、ＩA）の選択について、新しい方式１がＤＳＡと同等であることを示す。
【０１６４】
ＣＡが、ＡのアイデンティティＩAに署名するのにＤＳＡ署名方程式を使用すると仮定する。まず、ＣＡは、ｃAをランダムに選択し、
【０１６５】
【数６４】
【０１６６】
を計算し、次に、ＣＡは、安全なハッシュ関数ｈを使用してｈ（ＩA）を計算し、最後に、ＣＡは、ｓについて次式を解く。
ｈ（ＩA）≡ｃγA＋ｃAｓ（ｍｏｄ ｑ） （２）
ここで、（γA、ｓ）は、ＩAに対するＣＡの署名である。
式（２）にｈ（ＩA）-1を乗ずることによって、次式が得られる。
１≡ｃγAｈ（ＩA）-1＋ｃAｓｈ（ＩA）-1（ｍｏｄ ｑ）
Ｆ（γA、ＩA）＝γAｈ（ＩA）-1であると仮定し、上の式のｓｈ（ＩA）-1をａで置換することによって、式（１）が得られる。明らかに、式（２）は、Ｆ（γA、ＩA）＝γAｈ（ＩA）-1の場合に、式（１）と同等である。これは、誰かが署名方程式（１）を使用してこの方式を破ることができる場合に、その人物が、ＤＳＡ方式である署名方程式（２）を使用してこの方式を破ることができることを意味する。
【０１６７】
ヒューリスティックな（heuristic）議論から、Ｆ（γA、ＩA）＝γAｈ（ＩA）またはＦ（γA、ＩA）＝ｈ（γA、ＩA）である場合に、本発明の新方式が、Ｆ（γA、ＩA）の適当な選択について安全であることが暗示される。Ｆ（γA、ＩA）は、なんらかの他の形にすることができ、たとえば、ＩAが小さく、たとえば２０ビットであるが、ｑが１８０ビットを超えるときに、Ｆ（γA、ＩA）＝γA＋ＩAを使用することができる。新方式の短所は、すべてのユーザーおよびＣＡが同一のフィールド・サイズを使用することである。しかし、これは、たとえばＧｉｒａｕｌｔのＲＳＡに基づくＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ公開鍵共有方式など、すべてのＩＤに基づく内在的に証明される公開鍵方式が動作する方法である。
【０１６８】
もう１組の方式も、次のように説明することができる。
【０１６９】
システム・セットアップ：信頼できる当事者ＣＡは、大きい素数ｑについてｐ＝ｔｑ＋１である適当な素数ｐと、オーダー（位数）ｑのジェネレータαを選択する。ＣＡは、その秘密鍵として１＜ｃ＜ｑ−１のランダムな整数ｃを選択し、公開鍵β＝αc ｍｏｄ ｐを計算し、（β、α、ｐ、ｑ）を公開する。その後、ＣＡは、特殊な暗号関数ｆ＝Ｆ（γA、ＩA、ＯＰ）（ｆ：｛０、１｝*→｛１、２、…、（ｑ−１）｝）を選択し、この関数を用いて、内在的証明書を作るのに使用される署名方式が安全になるようにする。ここで、ＯＰは、ユーザーが関係することのできるなんらかのオプション・パラメータ（日付、またはＣＡの公開鍵β）を表す。たとえば、ｈが安全なハッシュ関数であるものとすると、ｆは、以下の形式のいずれかにすることができる。
１．Ｆ（γA、ＩA、ＯＰ）＝γA＋β＋ｈ（ＩA）
２．Ｆ（γA、ＩA、ＯＰ）＝ｈ（γA‖β‖ＩA）
３．Ｆ（γA、ＩA、ＯＰ）＝γA＋β＋ＩA、ここで、ＩAは、なんらかのパターン（または、ＩAが小さく、たとえば２０ビットであり、ｑが１８０ビットを超えるとき）を有する。
４．Ｆ（γA、ＩA、ＯＰ）＝γA＋ｈ（ＩA）
５．Ｆ（γA、ＩA、ＯＰ）＝ｈ（γA‖ＩA）
６．Ｆ（γA、ＩA、ＯＰ）＝γA＋ＩA、ここで、ＩAは、なんらかのパターン（または、ＩAが小さく、たとえば２０ビットであり、ｑが１８０ビットを超えるとき）を有する。
７．パラメータを少し変更して、所与の安全な署名方式から安全な署名方式を得ることは非常に簡単である。したがって、Ｆ（γA、ＩA、ＯＰ）は、内在的証明書を作るのに使用された署名方式が安全であることを保障する他の形式とすることができる。Ｆ（γA、ＩA、ＯＰ）を適当に選択することによって、これまでに知られているＥｌｇａｍａｌ様署名方式が、変更の後に内在的証明書方式として使用される場合の本明細書で提案される４系列の方式の１つと同等になることに留意されたい。しかし、本明細書で提案される方式は、より高い効率を有する。
【０１７０】
注：上記のシステム・セットアップが、以下の方式で仮定される。
【０１７１】
方式１．ａ：
１．各エンティティＡについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１＜ｃA＜ｑのランダムな整数ｃAを選択する。次に、ＣＡは、
【０１７２】
【数６５】
【０１７３】
を計算する。（γAは、Ａの公開鍵再構成公開データである。（ＩA、γA）は、Ａの内在的証明書として働く）。
２．ＣＡは、ｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ａについて次式を解く（ａ＝０、１、ｃ、ｃA-1ｃの場合には、別のｃAを選択し、式をもう一度解く）。
１＝ｃｆ＋ｃAａ（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。その後、ａがＡの秘密鍵、γAがＡのジェネレータ、
【０１７４】
【数６６】
【０１７５】
がＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
注：
１．ステップ１では、アイデンティティＩAをエンティティＡが選択することができる。
２．ステップ２では、ａ＝０、１を排除した。というのは、この場合に、誰もがＡの秘密鍵を簡単に知ることができるからである。特にａ＝０，ｃA-1ｃのときには、１＝ｃｆ（ｍｏｄ ｑ）からＣＡの秘密鍵ｃを誰でも簡単に計算することができる。
３．この方式では、各ユーザーが異なるシステム・ジェネレータγAを有する。
【０１７６】
方式１．ｂ：
１．各エンティティＡについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１＜ｃA＜ｑのランダムな整数ｃAを選択する。次に、ＣＡは、
【０１７７】
【数６７】
【０１７８】
を計算する（γAは、Ａの公開鍵再構成公開データである。（ＩA、γA）は、Ａの内在的証明書として働く）。
２．ＣＡは、ｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ａについて次式を解く（ａ＝０、１、ｃの場合には、別のｃAを選択し、式をもう一度解く）。
１≡ｃａ＋ｃAｆ（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。その後、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
注：
１．ステップ１では、アイデンティティＩAをエンティティＡが選択することができる。
２．ステップ２では、ａ＝０、１を排除した。というのは、この場合に、誰もがＡの秘密鍵を簡単に知ることができるからであり、ａ＝０のときには、証明書は、ＣＡに関係しない。
３．この方式では、各ユーザーが同一のシステム・ジェネレータβを有する。
【０１７９】
方式１．ｃ：
１．各エンティティＡについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１＜ｃA＜ｑのランダムな整数ｃAを選択する。次に、ＣＡは、
【０１８０】
【数６８】
【０１８１】
を計算する（γAは、Ａの公開鍵再構成公開データである。（ＩA、γA）は、Ａの内在的証明書として働く）。
２．ＣＡは、ｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ａについて次式を解く（ａ＝０、１、またはｃの場合には、別のｃAを選択し、式をもう一度解く）。
ａ≡ｃｆ＋ｃA（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
注：
１．ステップ１では、アイデンティティＩAをエンティティＡが選択することができる。
２．ステップ２では、ａ＝０、１を排除した。というのは、この場合に、誰もがＡの秘密鍵を簡単に知ることができるからである。
３．この方式では、各ユーザーが同一のシステム・ジェネレータαを有する。
【０１８２】
方式１．ｄ：
１．各エンティティＡについて、ＣＡは、一意の区別される名前またはアイデンティティＩA（たとえば、氏名、住所、電話番号）および、１＜ｃA＜ｑのランダムな整数ｃAを選択する。次に、ＣＡは、
【０１８３】
【数６９】
【０１８４】
を計算する（γAは、Ａの公開鍵再構成公開データである。（ＩA、γA）は、Ａの内在的証明書として働く）。
２．ＣＡは、ｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ａについて次式を解く（ａ＝０、１、またはｃの場合には、別のｃAを選択し、式をもう一度解く）。
【０１８５】
ａ≡ｃAｆ＋ｃ（ｍｏｄ ｑ）
３．ＣＡは、３つ組（γA、ａ、ＩA）を保護された形でＡに送信する。この３つ組は、ＩAに対するＣＡの署名である。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
注：
１．ステップ１では、アイデンティティＩAをエンティティＡが選択することができる。
２．ステップ２では、ａ＝０、１を排除した。というのは、この場合に、誰もがＡの秘密鍵を簡単に知ることができるからである。
３．この方式では、各ユーザーが同一のシステム・ジェネレータαを有する。
【０１８６】
誰でも公開データからユーザーＡの公開鍵を再構成することができるが、これは、再構成された公開鍵が証明されたことを意味しない。証明書を明示的に検証するためには、ａを知る必要がある。ａを知ったならば、検証プロセスは、ＩAに対するＣＡの署名を検証することになる。たとえば、方式１．ａでは、検証者がαβ-fを計算し、ユーザーＡがａを使用してγAaを計算する場合に、検証者およびユーザーが、一緒に証明書を検証することができる。しかし、検証者は、ユーザーＡが実際にａを知っていることを確認しなければならない。したがって、公開鍵の再構成は、ユーザーＡが対応する秘密鍵の完全な知識を有することを示すアプリケーション・プロトコルと組み合わされる場合に限って、内在的検証として働く。一般に、内在的証明書方式は、対象のエンティティおよび公開鍵の認証を必要とするすべての公開鍵方式と共に使用することができる。
【０１８７】
内在的に証明される公開鍵システムとしてＤＳＡ署名方式を使用し、内在的証明書方式として方式１．ａを使用して、これを実証する。
【０１８８】
アリスが、秘密鍵ａ、ジェネレータγAを有し、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開すると仮定する。次に、アリスは、ＤＳＡを使用してメッセージＭに署名しようとする。
アリスは、下記を実行する。
１．ランダムにｋを選択し、ｒ＝γAk（ｍｏｄ ｐ）を計算する。
２．ｅ＝ｓｈａ−１（Ｍ）を計算する。
３．ｓ＝ｘ-1（ｅ＋ａｒ）（ｍｏｄ ｑ）を計算する。
４．Ｍに対する署名は、（ｒ、ｓ）になる。
検証者は、下記を実行する。
１．アリスの公開データ（α、ＩA、β、γA、ｐ、ｑ）を取得し、ｆを計算し、公開鍵を再構成する。
βA＝γAa＝αβ-f（ｍｏｄ ｐ）
２．ｅ＝ｓｈａ−１（Ｍ）を計算する。
３．ｕ1＝ｅｓ-1（ｍｏｄ ｑ）およびｕ2＝ｒｓ-1（ｍｏｄ ｑ）を計算する。
４．
【０１８９】
【数７０】
【０１９０】
を計算する。
５．ｒ＝ｒ’の場合には、署名が検証される。それと同時に、アリスの（ＩＤに基づく）公開鍵が、内在的に検証される。
対（ＩA、γA）は、アリスの証明書として働く。ＤＳＡの場合、ａを知らずにアリスの署名を偽造することが非常に困難であることがわかっている。公開鍵の再構成は、アプリケーション・プロトコルが最後に有効になるときに、内在的検証として働く。公開鍵を取得するために、１回の累乗演算だけが必要であることを想起されたい。この理由から、本発明人は、内在的証明書の検証が、１回の累乗演算を必要とすると主張する。
【０１９１】
以下の内在的証明書方式は、ＣＡおよびエンティティの両方が、エンティティの秘密鍵を制御するが、対象のエンティティだけがその秘密鍵を知るように、上の方式を変更することによって導出することができる。
【０１９２】
この節では、もう１つのシステム・パラメータＨ（＊）が必要であり、このＨ（＊）は、安全なハッシュ関数または１方向関数またはアイデンティティ・マップとすることができる暗号関数である。
【０１９３】
方式２．ａ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０１９４】
【数７１】
【０１９５】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAについて署名方程式を解く（ｋA＝０またはｃの場合には、別のｃAを選択する）。
１＝ｃｆ＋ｃAｋA（ｍｏｄ ｑ）
その後、ＣＡは、
【０１９６】
【数７２】
【０１９７】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
３．Ａは、ａ＝ｋAｋ-1（ｍｏｄ ｑ）を計算し（ａ＝１の場合には、ステップ１に戻る）、γA＝（γA1）k（ｍｏｄ ｐ）を計算する。その後、γAa＝αβ-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、γAがＡのジェネレータ、γAaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
方式２．ｂ：
５．Ａは、整数ｋをランダムに選択し、βkを計算し、これをＣＡに送信する。
６．ＣＡは、整数ｃAをランダムに選択し、
【０１９８】
【数７３】
【０１９９】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｋA＋ｃAｆ（ｍｏｄ ｑ）
その後、ＣＡは、
【０２００】
【数７４】
【０２０１】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
７．Ａは、
【０２０２】
【数７５】
【０２０３】
、ｆ＝Ｆ（γA、ＩA、ＯＰ）、およびａ＝ｋA−ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、βa＝αγA-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
８．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
方式２．ｃ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２０４】
【数７６】
【０２０５】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝ｃの場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
その後、ＣＡは、
【０２０６】
【数７７】
【０２０７】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
３．Ａは、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算し（ａ＝０、１の場合には、ステップ１に戻る）、
【０２０８】
【数７８】
【０２０９】
を計算する。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式２．ｄ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２１０】
【数７９】
【０２１１】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝ｃAの場合には、別のｃAを選択する）。
ｋA≡ｃAｆ＋ｃ（ｍｏｄ ｑ）
その後、ＣＡは、
【０２１２】
【数８０】
【０２１３】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
３．Ａは、
【０２１４】
【数８１】
【０２１５】
、ｆ＝Ｆ（γA、ＩA、ＯＰ）、およびａ＝ｋA＋ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝γAfβであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
注：（方式２．ａ、２．ｂ、２．ｃ、２．ｄについて）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、ＣＡの面前での存在または保護されたチャネルまたは音声（たとえば電話での）または次の方法のいずれかによって行うことができる。
ステップ２で、３つ組（γA1、ｋA、ＩA）をＡに送信する代わりに、ＣＡが、まずγA1をＡに送信する。Ａは、γAを計算し、Ｋ＝Ｈ（γA）にセットし、ＤＥＳ（または他の対称鍵システム）によってＡの認証情報ＡAI（ＶＩＳＡ情報など）を暗号化し、ＤＥＳK（ＡAI）をＣＡに送信する。ＣＡは、ＤＥＳK（ＡAI）を非暗号化してＡAIを得る。ＡAIの有効性を検査した後に、ＣＡは（ｋA、ＩA）をＡに送信する。
３．（γA1、ｋA、ＩA）は、公開チャネルによって送信することができる。
【０２１６】
上の方式２．ａ〜２．ｄでは、内在的証明書方式が、対象のエンティティおよびＣＡによって完了される。各方式は、本質的に２つの部分すなわち鍵交換部分および署名部分に分割される。鍵交換部分の機能の１つが、公開チャネルによってＣＡからＡに内在的証明書情報を送信することである（詳細な説明は節６で行う）。上の方式の計算を高速化するために、鍵交換部分を変更することができる。以下の方式３．ａ〜３．ｄは、方式２．ａ〜２．ｄを変更することによって得られた。方式３．ａ〜３．ｄの長所は、βが固定されているので、ユーザーＡが、ＣＡから応答を得る前にＫを計算できることである。この特性は、特にオンラインの場合に好ましい。
【０２１７】
方式３．ａ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２１８】
【数８２】
【０２１９】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｆ＋ｃAｋA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０２２０】
【数８３】
【０２２１】
を計算し、３つ組
【０２２２】
【数８４】
【０２２３】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０２２４】
【数８５】
【０２２５】
、およびａ＝ｋAｋ-1（ｍｏｄ ｑ）を計算する（ａ＝１の場合には、ステップ１に戻る）。その後、γAa＝αβ-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、γAがＡのジェネレータ、γAaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
γAa＝αβ-f（ｍｏｄ ｐ）
方式３．ｂ：
１．Ａは、整数ｋをランダムに選択し、βkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２２６】
【数８６】
【０２２７】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAについて署名方程式を解く（ｋA＝０の場合には、別のｃAを選択する）。
１＝ｃｋA＋ｃAｆ（ｍｏｄ ｑ）
次に、ＣＡは、
【０２２８】
【数８７】
【０２２９】
およびｋ￣A＝ＤＥＳk（ＫA）を計算し、３つ組
【０２３０】
【数８８】
【０２３１】
をＡに送信する。
３．Ａは、
【０２３２】
【数８９】
【０２３３】
を計算し、ａ＝ｋA−ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、βa＝αγA-fであるかどうかを検査する。ここで、ａがＡの秘密鍵、βがＡのジェネレータ、βaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
βa＝αγA-f（ｍｏｄ ｐ）
注：（方式３．ｂについて）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、ＣＡの面前での存在または保護されたチャネルまたは音声（たとえば電話での）または次の方法のいずれかによって行うことができる。
ステップ２で、３つ組
【０２３４】
【数９０】
【０２３５】
をＡに送信する代わりに、ＣＡが、まずγAをＡに送信する。Ａは、
【０２３６】
【数９１】
【０２３７】
を計算し、ＤＥＳ（または他の対称鍵システム）によってＡの認証情報ＡAI（ＶＩＳＡ情報など）を暗号化し、ＤＥＳK（ＡAI）をＣＡに送信する。ＣＡは、ＤＥＳK（ＡAI）を非暗号化してＡAIを得る。ＡAIの有効性を検査した後に、ＣＡは
【０２３８】
【数９２】
【０２３９】
をＡに送信する。
３．
【０２４０】
【数９３】
【０２４１】
は、公開チャネルによって送信することができる。
【０２４２】
方式３．ｃ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２４３】
【数９４】
【０２４４】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０２４５】
【数９５】
【０２４６】
を計算し、３つ組
【０２４７】
【数９６】
【０２４８】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０２４９】
【数９７】
【０２５０】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式３．ｄ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２５１】
【数９８】
【０２５２】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃAｆ＋ｃ（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０２５３】
【数９９】
【０２５４】
を計算し、３つ組
【０２５５】
【数１００】
【０２５６】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０２５７】
【数１０１】
【０２５８】
、ｆ＝Ｆ（γA、ＩA、ＯＰ）、およびａ＝ｋA＋ｋｆ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、αa＝γAfβであるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝γAfβ（ｍｏｄ ｐ）
注：（方式３．ａ、３．ｃ、３．ｄについて）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、ＣＡの面前での存在または保護されたチャネルまたは音声（たとえば電話での）または次の方法のいずれかによって行うことができる。
ステップ１で、Ａは、αkおよびＫ＝Ｈ（βk）を計算し、αkおよびＤＥＳK（ＡAI）をＣＡに送信する。ＣＡは、Ｋ＝Ｈ（（αk）c）を計算し、ＤＥＳK（ＡAI）を非暗号化してＡAIを得る。ＡAIの有効性を検査した後に、ＣＡはステップ２を継続する。
３．（γA、ｋA、ＩA）は、公開チャネルによって送信することができる。
【０２５９】
方式３．ａ、３．ｃ、および３．ｄの長所は、βが固定されているのでユーザーＡがＫを簡単に計算できることと、ｋAが暗号化され、他人がそれを知ることができなくなっていることである。実際に、ｋAが知れわたることが、証明書方式のセキュリティを低下させない。ｋAを暗号化する目的は、エンティティが確実にｋを知るようにするためである。したがって、方式３．ａ〜３．ｄについて、証明書方式で注２で説明した方法を使用するならば、ＤＥＳ暗号化部分を除去することができ、
【０２６０】
【数１０２】
【０２６１】
をｋAで置換することができる。
【０２６２】
上の方式の送信帯域幅を節約するために、γAの代わりにｆ＝Ｆ（γA、ＩA、ＯＰ）を送信することによって上の方式を変更することができる（一般に、γAのサイズは１６０ビットより大きく、ｆはちょうど１６０ビットであることに留意されたい）。下の方式４．ｃは、方式３．ｃの変形形態である。
【０２６３】
方式４．ｃ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２６４】
【数１０３】
【０２６５】
およびｆ＝Ｆ（γA、ＩA、ＯＰ）を計算し、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝Ｈ（（αk）c）および
【０２６６】
【数１０４】
【０２６７】
を計算し、３つ組
【０２６８】
【数１０５】
【０２６９】
をＡに送信する。
３．Ａは、Ｋ＝Ｈ（βk）、
【０２７０】
【数１０６】
【０２７１】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、γA＝αaβ-f（ｍｏｄ ｐ）を計算し、ｆ＝Ｆ（γA、ＩA、ＯＰ）であるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
さらに、方式５．ｃに従うことによって、帯域幅を減らすことができる。
【０２７２】
方式５．ｃ：
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡに送信する。
２．ＣＡは、整数ｃAをランダムに選択し、
【０２７３】
【数１０７】
【０２７４】
を計算し、
【０２７５】
【数１０８】
【０２７６】
をγAの最初の８０個の最下位ビットとしてセットする。その後、
【０２７７】
【数１０９】
【０２７８】
およびｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
次に、ＣＡは、Ｋ＝（αk）c（ｍｏｄ ｐ）および
【０２７９】
【数１１０】
【０２８０】
を計算し、３つ組
【０２８１】
【数１１１】
【０２８２】
をＡに送信する。
【０２８３】
注：
【０２８４】
【数１１２】
【０２８５】
は、公開チャネルによって送信することができる。
３．Ａは、Ｋ＝βk（ｍｏｄ ｐ）、
【０２８６】
【数１１３】
【０２８７】
、およびａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算する（ａ＝０、１の場合には、ステップ１に戻る）。その後、
【０２８８】
【数１１４】
【０２８９】
、γA＝αaβ-f（ｍｏｄ ｐ）を計算し、γAの最初の８０個の最下位ビットが
【０２９０】
【数１１５】
【０２９１】
であるかどうかを検査する。ここで、ａがＡの秘密鍵、αがＡのジェネレータ、αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
４．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
方式５．ｃのセキュリティ・レベルは、前に述べた他の方式ほどではない。方式５．ｃは、８０ビットのセキュリティだけを有する。しかし、現在の実用的なアプリケーションにはこれでよい。最初の８０個の最下位ビットを、γAの半分の下位ビットに拡張することができる。
【０２９２】
内在的証明書は、情報にオプション・パラメータＯＰを含めることによって、他の有用な情報を証明するのに使用することができる。たとえば、
【０２９３】
【数１１６】
【０２９４】
である。ここで、αEは、Ａのもう１つの秘密鍵であり、
【０２９５】
【数１１７】
【０２９６】
は、対応する公開鍵である。下の方式６．ｃは、方式２．ｃの変形形態である。他の方式を、同一の形で変更することができる。
【０２９７】
方式６．ｃ：
１．Ａは、整数ａEをランダムに選択し、
【０２９８】
【数１１８】
【０２９９】
を計算する。
２．Ａは、整数ｋをランダムに選択し、αkを計算し、αkおよび
【０３００】
【数１１９】
【０３０１】
をＣＡに送信する。
【０３０２】
３．ＣＡは、整数ｃAをランダムに選択し、
【０３０３】
【数１２０】
【０３０４】
を計算し（たとえば
【０３０５】
【数１２１】
【０３０６】
）、ｋAを計算する（ｋA＝０の場合には、別のｃAを選択する）。
ｋA≡ｃｆ＋ｃA（ｍｏｄ ｑ）
その後、ＣＡは、
【０３０７】
【数１２２】
【０３０８】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
４．Ａは、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）を計算し（ａ＝０、１の場合には、ステップ１に戻る）、
【０３０９】
【数１２３】
【０３１０】
を計算する。その後、αa＝βfγAであるかどうかを検査する。ここで、ａがＡの秘密署名鍵であり、αがＡのジェネレータ、αaがＡの公開署名鍵である。ａEがＡの秘密暗号化鍵、
【０３１１】
【数１２４】
【０３１２】
がＡの公開暗号化鍵である。Ａは、公開ドメインで
【０３１３】
【数１２５】
【０３１４】
を公開する。
５．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に証明される公開鍵を得ることができる。
αa＝βfγA（ｍｏｄ ｐ）
注：（方式４．ｃ、５．ｃ、６．ｃについて）
１．アイデンティティＩAは、ＣＡまたはエンティティＡのいずれかによって選択することができる。
２．ＣＡは、エンティティＡを認証しなければならない。これは、方式３．ｃの注２に記載の方法によって行うことができる。
【０３１５】
【数１２６】
【０３１６】
または
【０３１７】
【数１２７】
【０３１８】
または（γA1、ｋA、ＩA）を、公開チャネルによって送信することができる。
【０３１９】
ＣＡ連鎖（ＣＡ ｃｈａｉｎｉｎｇ）方式
ＣＡ連鎖構造を実施するために、すなわち、ＣＡ１がＣＡ２を認証し、ＣＡ２がＣＡ３を認証し、ＣＡ３がユーザーＡを認証する。この節では、ＣＡ連鎖内に３つのＣＡがある例を提示する。基本方式３’を使用して、この例を実証する。
【０３２０】
システム・セットアップ：
最上位の信頼できる当事者ＣＡ１は、大きい素数ｑについてｐ＝ｔｑ＋１である適当な素数ｐと、オーダー（位数）ｑのジェネレータαを選択する。ＣＡ１は、その秘密鍵として１≦ｃ1≦ｑ−１のランダムな整数ｃ1を選択し、公開鍵
【０３２１】
【数１２８】
【０３２２】
を計算し、（β1、α、ｐ、ｑ）を公開する。
フェーズ１ ＣＡ２が、ＣＡ１からの内在的に証明される公開鍵を問い合わせる。
１．ＣＡ２は、整数ｋ2をランダムに選択し、
【０３２３】
【数１２９】
【０３２４】
を計算し、これをＣＡ１に送信する。
【０３２５】
２．ＣＡ１は、一意の区別される名前またはアイデンティティＩCA2および、１≦ｃCA2≦ｑ−１のランダムな整数ｃCA2を選択する。次に、ＣＡ１は、
【０３２６】
【数１３０】
【０３２７】
を計算する（γCA2は、ＣＡ２の公開鍵再構成公開データである）。
３．ＣＡ１は、関数ｆ1＝Ｆ（γCA2、ＩCA2）を選択し、ｋCA2を計算する（ｋCA2＝０の場合には、ステップ２で別のｃCA2を選択し、ｋCA2を再計算する）。
ｋCA2＝ｃ1ｆ1＋ｃCA2（ｍｏｄ ｑ）
４．ＣＡ１が、
【０３２８】
【数１３１】
【０３２９】
を計算し、３つ組（γCA21、ｋCA2、ＩCA2）をＣＡ２に送信する。
５．ＣＡ２が、
【０３３０】
【数１３２】
【０３３１】
を計算する。その後、ｃ2＝ｋCA2＋ｋ2（ｍｏｄ ｑ）がＣＡ２の秘密鍵、αがＣＡ２のジェネレータ、
【０３３２】
【数１３３】
【０３３３】
がＣＡ２の公開鍵になる。ＣＡ２は、公開ドメインで（α、ＩCA2、β1、β2、γCA2、ｐ、ｑ）を公開する。
注：ユーザーがＣＡ２を信頼するときには、β2を直接に使用することができる。
６．誰もが、次式を計算することによって、公開ドメインからＣＡ２の（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
【０３３４】
【数１３４】
【０３３５】
フェーズ２ ＣＡ３が、ＣＡ２からの内在的に証明される公開鍵を問い合わせる。
１．ＣＡ３は、整数ｋ3をランダムに選択し、
【０３３６】
【数１３５】
【０３３７】
を計算し、これをＣＡ２に送信する。
【０３３８】
２．ＣＡ２は、一意の区別される名前またはアイデンティティＩCA3および、１≦ｃCA3≦ｑ−１のランダムな整数ｃCA3を選択する。ＣＡ２が、
【０３３９】
【数１３６】
【０３４０】
を計算する（γCA3は、ＣＡ３の公開鍵再構成公開データである）。
３．ＣＡ２は、関数ｆ2＝Ｆ（γCA3、ＩCA3）を選択し、ｋCA3を計算する（ｋCA3＝０の場合には、ステップ２で別のｃCA3を選択し、ｋCA3を再計算する）。
ｋCA3≡ｃ2ｆ2＋ｃCA3（ｍｏｄ ｑ）
４．ＣＡ２が、
【０３４１】
【数１３７】
【０３４２】
を計算し、３つ組（γCA31、ｋCA3、ＩCA3）をＣＡ３に送信する。
５．ＣＡ３が、
【０３４３】
【数１３８】
【０３４４】
を計算する。その後、ｃ3＝ｋCA3＋ｋ3（ｍｏｄ ｑ）がＣＡ３の秘密鍵、αがＣＡ３のジェネレータ、
【０３４５】
【数１３９】
【０３４６】
がＣＡ３の公開鍵になる。ＣＡ３は、公開ドメインで（α、ＩCA3、β2、β3、γCA3、ｐ、ｑ）を公開する。
【０３４７】
注：エンティティがＣＡ３を信頼するときには、β3を直接に使用することができる。
６．誰もが、次式を計算することによって、公開ドメインからＣＡ３の（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
【０３４８】
【数１４０】
【０３４９】
フェーズ３ ユーザーＡが、ＣＡ３からの内在的に証明される公開鍵を問い合わせる。
１．Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡ３に送信する。
２．ＣＡ３は、一意の区別される名前またはアイデンティティＩAおよび、１≦ｃA≦ｑ−１のランダムな整数ｃAを選択する。ＣＡ３が、
【０３５０】
【数１４１】
【０３５１】
を計算する（γAは、Ａの公開鍵再構成公開データである）。
３．ＣＡ３は、注意深く選択された関数ｆ3＝Ｆ（γA、ＩA）を選択し、ｋAを計算する（ｋA＝０の場合には、ステップ２で別のｃAを選択し、ｋAを再計算する）。
【０３５２】
ｋA≡ｃ3ｆ3＋ｃA（ｍｏｄ ｑ）
４．ＣＡ３は、
【０３５３】
【数１４２】
【０３５４】
を計算し、３つ組（γA1、ｋA、ＩA）をＡに送信する。
【０３５５】
５．Ａが、
【０３５６】
【数１４３】
【０３５７】
を計算する。その後、ａ＝ｋA＋ｋ（ｍｏｄ ｑ）がＡの秘密鍵、αがＡのジェネレータ、βA＝αaがＡの公開鍵になる。Ａは、公開ドメインで（α、ＩA、β3、βA、γA、ｐ、ｑ）を公開する。
注：ユーザーがＡを信頼するときには、βAを直接に使用することができる。
【０３５８】
６．誰もが、次式を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に検証された公開鍵を得ることができる。
【０３５９】
【数１４４】
【０３６０】
フェーズ４ ユーザーＡの署名および検証
メッセージＭに署名するために、ユーザーＡは下記を実行する。
１．ランダムにｘを選択し、ｒ＝αx（ｍｏｄ ｐ）を計算する。
２．ｅ＝ｆA＝Ｆ（ｒ，Ｍ）を計算する。ここで、Ｆはなんらかの固定された関数である。
３．ｓ＝ａｅ＋ｘ（ｍｏｄ ｑ）を計算する。
４．Ｍに対する署名は、（ｒ、ｓ）になる。
検証者は、下記を実行する。
１．ＣＡ１、ＣＡ２、ＣＡ３，およびユーザーＡの公開データを得る。
【０３６１】
（α、ＩCA2、ＩCA3、ＩA、β1、β2、β3、βA、γCA2、γCA3、γA、ｐ、ｑ）
２．ユーザーＡの公開鍵を再構成する。
【０３６２】
【数１４５】
【０３６３】
３．ｅ＝ｆA＝Ｆ（ｒ、Ｍ）を計算する。
４．ｒ’＝αsβA-e（ｍｏｄ ｐ）を計算する。
５．ｒ＝ｒ’の場合には、署名が検証される。それと同時に、ＣＡ２、ＣＡ３、およびユーザーＡの（ＩＤに基づく）公開鍵が、内在的に検証される。
【０３６４】
ユーザーＡの公開鍵の再構成には、３つの既知の基底累乗演算および３つの乗算演算だけが必要である。署名が有効なときには、ＣＡ２、ＣＡ３、およびユーザーＡの（ＩＤに基づく）公開鍵が、内在的に検証される。
【０３６５】
注：
１．検証者がＡを信頼する場合には、Ａの公開鍵はβAになる。
２．検証者がＣＡ３を信頼する場合には、Ａの再構成公開鍵は
【０３６６】
【数１４６】
【０３６７】
になる。
【０３６８】
３．検証者がＣＡ２を信頼する場合には、Ａの再構成公開鍵は
【０３６９】
【数１４７】
【０３７０】
になる。
【０３７１】
連署（Ｃｏ−ｓｉｇｎｉｎｇ）方式
以下では、複数のＣＡが１つの内在的証明書に署名できるようにする方式を説明する。これは、基本方式３’を使用して３つのＣＡが証明書に連署する場合によって例示される。
【０３７２】
システム・セットアップ：
ＣＡ１、ＣＡ２、およびＣＡ３が、次の共通のシステム・パラメータを有すると仮定する。（１）大きい素数ｑに対してｐ＝ｔｑ＋１になる素数ｐ、（２）オーダーｑのジェネレータα、（３）注意深く選択された関数ｆ＝Ｆ（γ，（ＩA1＋ＩA2＋ＩA3））。ＣＡ１は、その秘密鍵として１≦ｃ1≦ｑ−１のランダムな整数ｃ1を選択し、公開鍵
【０３７３】
【数１４８】
【０３７４】
を計算し、（β1、α、ｐ、ｑ）を公開する。ＣＡ２は、その秘密鍵として１≦ｃ2≦ｑ−１のランダムな整数ｃ2を選択し、公開鍵
【０３７５】
【数１４９】
【０３７６】
を計算し、（β2、α、ｐ、ｑ）を公開する。ＣＡ３は、その秘密鍵として１≦ｃ3≦ｑ−１のランダムな整数ｃ3を選択し、公開鍵
【０３７７】
【数１５０】
【０３７８】
を計算し、（β3、α、ｐ、ｑ）を公開する。
【０３７９】
ステップ１ Ａは、整数ｋをランダムに選択し、αkを計算し、これをＣＡ１、ＣＡ２、およびＣＡ３に送信する。
ステップ２ ＣＡが、情報を交換し、内在的証明書を計算する。
【０３８０】
フェーズ１
１．ＣＡ１が、一意の区別される名前またはアイデンティティＩA1および、１≦ｃA1≦ｑ−１のランダムな整数ｃA1を選択し、
【０３８１】
【数１５１】
【０３８２】
を計算し、（
【０３８３】
【数１５２】
【０３８４】
）をＣＡ２およびＣＡ３に送信する。
２．ＣＡ２が、一意の区別される名前またはアイデンティティＩA2および、１≦ｃA2≦ｑ−１のランダムな整数ｃA2を選択し、（
【０３８５】
【数１５３】
【０３８６】
）を計算し、
【０３８７】
【数１５４】
【０３８８】
をＣＡ１およびＣＡ３に送信する。
【０３８９】
３．ＣＡ３が、一意の区別される名前またはアイデンティティＩA3および、１≦ｃA3≦ｑ−１のランダムな整数ｃA3を選択し、
【０３９０】
【数１５５】
【０３９１】
を計算し、
【０３９２】
【数１５６】
【０３９３】
をＣＡ１およびＣＡ２に送信する。
【０３９４】
フェーズ２
１．ＣＡ１が、
【０３９５】
【数１５７】
【０３９６】
を計算し（γは、Ａの公開鍵再構成公開データである）、ｆ＝Ｆ（γ、（ＩA1＋ＩA2＋ＩA3））を計算し、ｋA1を計算する（ｋA1＝０の場合、フェーズ１に戻る）。
ｋA1≡ｃ1ｆ＋ｃA1（ｍｏｄ ｑ）
ＣＡ１は、
【０３９７】
【数１５８】
【０３９８】
を計算し、３つ組（γA11、ｋA1、ＩA1）をＡに送信する。
２．ＣＡ２が、
【０３９９】
【数１５９】
【０４００】
を計算し（γは、Ａの公開鍵再構成公開データである）、ｆ＝Ｆ（γ、（ＩA1＋ＩA2＋ＩA3））を計算し、ｋA2を計算する（ｋA2＝０の場合、フェーズ１に戻る）。
ｋA2≡ｃ2ｆ＋ｃA2（ｍｏｄ ｑ）
ＣＡ２は、
【０４０１】
【数１６０】
【０４０２】
を計算し、３つ組（γA21、ｋA2、ＩA2）をＡに送信する。
【０４０３】
３．ＣＡ３が、
【０４０４】
【数１６１】
【０４０５】
を計算し（γは、Ａの公開鍵再構成公開データである）、ｆ＝Ｆ（γ、（ＩA1＋ＩA2＋ＩA3））を計算し、ｋA3を計算する（ｋA3＝０の場合、フェーズ１に戻る）。
ｋA3≡ｃ3ｆ＋ｃA3（ｍｏｄ ｑ）
ＣＡ３は、
【０４０６】
【数１６２】
【０４０７】
を計算し、３つ組（γA31、ｋA3、ＩA3）をＡに送信する。
ステップ３ Ａが、内在的に連署された秘密鍵および公開鍵再構成情報を計算する。
１．Ａは、ａ＝ｋA1＋ｋA2＋ｋA3＋ｋ（ｍｏｄ ｑ）を計算する（ａが０または１の場合には、ステップ１に戻る）。
２．Ａが、
【０４０８】
【数１６３】
【０４０９】
およびｆ＝Ｆ（γ、（ＩA1＋ＩA2＋ＩA3））を計算する。その後、αa＝（β1β2β3）fγ（ｍｏｄ ｐ）であるかどうかを検証する。
３．ここで、ａがＡの内在的に連署された秘密鍵、αがＡのジェネレータ、ＩA＝ＩA1＋ＩA2＋ＩA3がＡの共通ＩＤ、（β1β2β3）fγがＡの内在的に共同証明される公開鍵である。
４．Ａは、公開ドメインで（α、ＩA1、ＩA2、ＩA3、β1、β2、β3、γ、ｐ、ｑ）を公開する。
【０４１０】
５．誰もが、（β1β2β3）fγ（ｍｏｄ ｐ）を計算することによって、公開ドメインからＡの（ＩＤに基づく）内在的に共同証明された公開鍵を得ることができる。
【０４１１】
応用例
以下の例は、ＣＡの署名方程式として方式３（または方式７’）に関して示される。というのは、この方式では全員が同一のジェネレータを共用するからである。各ユーザーは、ＣＡがシステム・パラメータ（ｐ、ｑ、ｄ）を使用し、各ユーザーが同一のジェネレータを有する限り、異なるＣＡを有することができる。
【０４１２】
セット・アップ：
ＣＡ１： システム・パラメータ（α、β1、ｐ、ｑ、ｄ）
アリスが、秘密鍵ａ、ジェネレータαを有し、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
ＣＡ２： システム・パラメータ（α、β2、ｐ、ｑ）
ボブが、秘密鍵ｂ、ジェネレータαを有し、公開ドメインで（α、ＩA、β、γA、ｐ、ｑ）を公開する。
ＭＴＩ／Ｃ０鍵共有プロトコルを使用して、本発明の新方式を使用する方法の実例を示す。アリスとボブが鍵交換を実行したいと思っていると仮定する。
【０４１３】
ＭＴＩ／Ｃ０プロトコル
１．アリスは、ボブの公開鍵
【０４１４】
【数１６４】
【０４１５】
を再構成し、整数ｘをランダムに選択し、（αb）xを計算し、ボブに送信する。
【０４１６】
２．ボブは、アリスのの公開鍵
【０４１７】
【数１６５】
【０４１８】
を再構成し、整数ｙをランダムに選択し、（αa）yを計算し、アリスに送信する。
【０４１９】
３．アリスは、共有鍵（shared key）
【０４２０】
【数１６６】
【０４２１】
を計算する。
【０４２２】
４．ボブは、共有鍵（shared key）
【０４２３】
【数１６７】
【０４２４】
を計算する。
【０４２５】
これは２パス・プロトコルである。本発明の内在的証明書方式を用いると、各当事者は、３つの累乗演算を実行するだけで共有鍵（shared key）を得ると同時に、認証鍵共有および内在的公開鍵検証を実行する。
【０４２６】
以下は、サインクリプション（signcryption）方式の例である。ＣＡの署名方程式として方式３（または方式７）を使用する。というのは、この方式では、全員が同一のジェネレータを共用するからである。その後の方式では、ＣＡの署名方程式として方式１３を使用する。この節のすべての方式について、各ユーザーは、ＣＡが同一のシステム・パラメータ（ｐ、ｑ、α）を使用し、各ユーザーが同一のジェネレータを使用する限り、異なるＣＡを有することができる。
【０４２７】
セット・アップ：
ＣＡ１： システム・パラメータ（α、β1、ｐ、ｑ）
アリス： 秘密鍵ａ、ジェネレータα、および公開ドメインの（α、ＩA、β1、γA、ｐ、ｑ）。
ＣＡ２： システム・パラメータ（α、β2、ｐ、ｑ）
ボブ： 秘密鍵ｂ、ジェネレータα、および公開ドメインの（α、ＩB、β2、γB、ｐ、ｑ）。
ボブは、署名され暗号化されたメッセージＭをアリスに送信したいと思っている。
【０４２８】
サインクリプション・プロトコル１：
ボブが、署名され暗号化されたメッセージＭをアリスに送信したいと思っていると仮定する。
ボブは、下記を実行する。
１．アリスの公開鍵
【０４２９】
【数１６８】
【０４３０】
を再構成する。
２．整数ｘをランダムに選択し、鍵ｒ＝（αa）x（ｍｏｄ ｐ）を計算する。
３．Ｃ＝ＤＥＳr（Ｍ）を計算する。
４．ｅ＝ｈａｓｈ（Ｃ ＩA）を計算する。
５．ｓ＝ｂｅ＋ｘ（ｍｏｄ ｑ）を計算する。
６．対（Ｃ、ｓ）をアリスに送信し、したがって、Ｃは、暗号化されたメッセージであり、ｓは、署名である。
【０４３１】
メッセージを復元するために、アリスは下記を実行する。
１．ｅ＝ｈａｓｈ（Ｃ ＩA）を計算する。
２．ボブの公開鍵
【０４３２】
【数１６９】
【０４３３】
を再構成する。
３．αas（αb）-ac（ｍｏｄ ｐ）を計算する。これはｒである。
４．メッセージＭ＝ＤＥＳr（Ｃ）を非暗号化する。
５．冗長性に関する検査を行う。
したがって、ボブは、２回の累乗演算だけを行い、アリスは、３回の累乗演算を行う。しかし、アリスとボブの両方が、お互いの認証を確信している。この方式の場合、メッセージＭが、なんらかの冗長性またはパターンを有しなければならないことに留意されたい。
【０４３４】
サインクリプション・プロトコル２（一般的な場合）：
セット・アップ：
ＣＡ１： システム・パラメータ（α、β1、ｐ、ｑ）
アリス： 秘密鍵ａ、ジェネレータα、および公開ドメインの（α、ＩA、β1、γA、ｐ、ｑ）。
ＣＡ２： システム・パラメータ（α、β2、ｐ、ｑ）
ボブ： 秘密鍵ｂ、ジェネレータα、および公開ドメインの（α、ＩB、β2、γB、ｐ、ｑ）。
【０４３５】
注：このセット・アップは、内在的証明書用である。通常の証明書方式システムの場合、アリスとボブが同一のジェネレータを有することだけが必要である。
【０４３６】
アリスへのメッセージをサインクリプト(signcrypt)するために、ボブは下記を実行する。
【０４３７】
１．アリスの公開鍵αaを得る（内在的証明書方式の場合、アリスの公開鍵
【０４３８】
【数１７０】
【０４３９】
を再構成する）。
２．整数ｘをランダムに選択し、ｒ＝（αa）x（ｍｏｄ ｐ）を計算する。
３．Ｃ＝ＤＥＳr（Ｍ）を計算する。
４．ｅ＝ｈａｓｈ（Ｃ‖αa）を計算する。
５．ｓ＝ｂｅ＋ｘ（ｍｏｄ ｑ）を計算する。
６．（Ｃ、ｓ）をアリスに送信する。Ｃは、暗号化されたメッセージであり、ｓは、署名である。
メッセージを復元するために、アリスは下記を実行する。
１．ｅ＝ｈａｓｈ（Ｃ‖αa）を計算する。
２．ボブの公開鍵αbを得る（内在的証明書方式の場合、ボブの公開鍵
【０４４０】
【数１７１】
【０４４１】
を再構成する）。
３．αas（αb）-ae（ｍｏｄ ｐ）を計算する。これはｒである。
４．メッセージＭ＝ＤＥＳr（Ｃ）を非暗号化する。
【０４４２】
注：
１．証明書方式が、本明細書に記載の内在的証明書でない場合には、アリスおよびボブの公開鍵を検証しなければならない。
２．メッセージＭが、なんらかの冗長性またはパターンを有しなければならない。
【０４４３】
３．１つの値ｒを知っているアリスは、値αabが露出されるので、ボブからアリスへのすべてのメッセージを非暗号化することができる。
４．一般に、ハッシュｅにオプション・パラメータを含めなければならない、すなわち、ｅ＝ｈａｓｈ（Ｃ‖αa‖ＯＰ）。たとえば、ＯＰ＝αbまたはＯＰ＝αb‖β1‖β2。
【０４４４】
上のサインクリプション方式は、署名者が自分の秘密署名鍵を失った場合に、その署名者がサインクリプトしたすべてのメッセージが公衆に露出されるという短所を有する。事後暗号化の保護のために、新しいサインクリプション方式を提案する。新方式では、各ユーザーが、２対の鍵を有し、１対は署名鍵用、もう１対は暗号化鍵である。新方式は、あらゆる証明書方式と共に使用することができる。しかし、本発明の内在的証明書方式と共に使用される場合に、新方式は最も効果的になる。
【０４４５】
サインクリプション・プロトコル３（一般的な場合）：
セット・アップ：
アリス： 秘密署名鍵ａ、秘密暗号化鍵ａE、ジェネレータα、および公開ドメインの
【０４４６】
【数１７２】
【０４４７】
。
【０４４８】
ＣＡ２： システム・パラメータ（α、β2、ｐ、ｑ）
ボブ： 秘密署名鍵ｂ、秘密暗号化鍵ｂE、ジェネレータα、および公開ドメインの
【０４４９】
【数１７３】
【０４５０】
。
注：このセット・アップは、方式６．ｃを使用する内在的証明書用である。通常の証明書方式システムの場合、アリスとボブが同一のジェネレータを有することだけが必要である。
【０４５１】
アリスへのメッセージをサインクリプトするために、ボブは下記を実行する。
【０４５２】
１ アリスの公開署名鍵αaおよび公開暗号化鍵
【０４５３】
【数１７４】
【０４５４】
を得る（内在的証明書方式の場合、アリスの公開署名鍵
【０４５５】
【数１７５】
【０４５６】
を再構成する）。
２ 整数ｘをランダムに選択し、
【０４５７】
【数１７６】
【０４５８】
を計算する。
３ Ｃ＝ＤＥＳr（Ｍ）を計算する。
４
【０４５９】
【数１７７】
【０４６０】
を計算する。
５ ｓ＝ｂｅ＋ｘ＋ｂE（ｍｏｄ ｑ）を計算する。
６ （Ｃ、ｓ）をアリスに送信する。Ｃは、暗号化されたメッセージであり、ｓは、署名である。
メッセージを復元するために、アリスは下記を実行する。
【０４６１】
１．
【０４６２】
【数１７８】
【０４６３】
を計算する。
２．ボブの公開署名鍵αbおよび公開暗号化鍵
【０４６４】
【数１７９】
【０４６５】
を得る（内在的証明書方式の場合、ボブの公開署名鍵
【０４６６】
【数１８０】
【０４６７】
を再構成する）。
３．
【０４６８】
【数１８１】
【０４６９】
を計算する。これはｒである。
４．メッセージＭ＝ＤＥＳr（Ｃ）を非暗号化する。
【０４７０】
注：
１．受信者アリスの秘密鍵がａ＋ａEであると考えることができる。これは、受信者が、２つの秘密鍵ではなく１つの秘密鍵だけを必要とすることを意味する。しかし、送信者ボブは、２つの秘密鍵を必要とする。通常の証明書の場合、受信者は、１つの秘密鍵だけを必要とする。
２．証明書方式が、本明細書に記載の内在的証明書でない場合には、アリスおよびボブの公開鍵を検証しなければならない。
３．メッセージＭが、なんらかの冗長性またはパターンを有しなければならない。
４．
【０４７１】
【数１８２】
【０４７２】
の中のパラメータＯＰは、空またはＯＰ＝β1‖β2とすることができる。
５．１つのｒの値を知っても、ポスト・メッセージの情報は明らかにならない。
６．内在的証明書方式を用いると、ボブは、２回の累乗演算だけを実行し、アリスは、４回の累乗演算を実行する。しかし、双方が認証部分（authentification part）であることを、アリスとボブの双方は秘密にしている（are confidential）。
７．誰かがアリスの秘密鍵ａ＋ａEを知るか、ボブが両方の秘密鍵を失った場合、事後暗号化されたメッセージを保護することはできない。
【０４７３】
通常の署名の場合、１つの問題は、署名者が、自分がその署名を署名したことを否定することである。これを否認（repudiation）と呼ぶ。上のプロトコル１および２は、ジャッジ(judge)を信頼するならば、否認拒否機能（non-repudiationfeature）を有する。すなわち、署名者は、自分がサインクリプトされた(signcrypted)メッセージに署名したことを拒否することができない。プロトコル３は、ジャッジが信頼されないときであっても否認拒否機能を有する。次のプロトコルで、ボブが署名を拒否したい場合にジャッジがどのように判断するかを示す。
【０４７４】
否認拒否プロトコル：
１．アリスが（Ｃ、ｓ）をジャッジに送信する。
２．ジャッジは、
【０４７５】
【数１８３】
【０４７６】
を計算する（注：アリスおよびボブの２対の公開鍵を検証しなければならない。内在的証明書方式の場合、再構成公開データから公開鍵を計算しなければならない）。
３．ジャッジは、２つの整数ｒ1およびｒ2をランダムに選択し、
【０４７７】
【数１８４】
【０４７８】
を計算し、Ｌをアリスに送信する。
４．アリスは、
【０４７９】
【数１８５】
【０４８０】
を計算し、ジャッジに送り返す。
５．ジャッジは、
【０４８１】
【数１８６】
【０４８２】
を計算し、Ｍ＝ＤＥＳr（Ｃ）によってメッセージを復元する。
６．Ｍが正しいフォーマットを有する場合、（Ｃ、ｓ）はボブによってサインクリプトされたものに違いない。
７．ジャッジは、判断を行った後に、値
【０４８３】
【数１８７】
【０４８４】
をアリスおよびボブに送信して、自分の判断を確認する。
【０４８５】
他の２つのサインクリプション・プロトコルの場合、否認拒否（non-repudiation）プロトコルは、ジャッジが完全に信頼されるならば類似したものになる。
【０４８６】
結論として、本発明の方式は、ユーザーの秘密鍵を計算に直接に使用しなければならないアプリケーション・プロトコルと組み合わされたときに、内在的に証明される、ＩＤに基づくユーザーの公開鍵を提供する。これらの方式は、鍵認証センタ（Key Authentication Center、ＫＡＣ）が、内在的に証明される公開鍵をユーザーに配送するのに使用することもできる。
【０４８７】
内在的に証明される公開鍵のもう１つの応用例は、認証機関のビット強度が、証明されるユーザーまたはエンティティの公開鍵と同一であることである。ビット強度によって、相対的な鍵サイズおよび関係するエンティティの処理能力が暗示される。
【０４８８】
この問題に対処する手法の１つが、Ｘ．５０９証明書で指定されるものなどの従来の証明書構造に、内在的に証明される公開鍵を埋め込むことである。この場合、証明書に対する署名は、内在的に証明される公開鍵より高いビット強度になる。したがって、ＣＡは、２つの異なるセキュリティ・レベルでユーザー公開鍵を証明している。公開鍵を取り出す他のエンティティは、受け入れたいセキュリティ・レベルについて決定することができる。一部の応用分野では、必要な性能をもたらすために、内在的な値（implicit value）によって提供される、より低いレベルだけが必要になる可能性がある。
【０４８９】
本発明の特定の実施形態および特定の用途に関して本発明を説明してきたが、請求項に記載された本発明の趣旨から逸脱せずに、当業者は本発明のさまざまな変更形態を思い浮かべるであろう。たとえば、好ましい実施形態の上の説明では、乗法表現（multiplicative notation）を利用したが、本発明の方法は、加法表現（additive notation）を使用しても同様に良好に説明することができる。たとえば、ＥＣＤＳＡで実施された楕円曲線アルゴリズムがＤＳＡと同等であることは周知であり、そして、楕円曲線は離散対数アルゴリズムに類似することは、モジュロ素数の整数（integersmoduro a prime）の乗法群Ｆp*の設定（setting）で通常記述される。群Ｆp*および楕円曲線群Ｅ（Ｆq）の要素および演算の間には対応関係がある。さらに、この署名技法は、ＦpおよびＦ2”上で定義されるフィールド（field）の中で実行される関数にも同様に良好に適用可能である。また、上で説明したＤＳＡ署名方式は、当技術分野で既知の一般化されたＥｌＧａｍａｌ署名方式の特定の実例（specificinstance）であり、したがって、本発明の技法がこれに適用可能であることに留意されたい。
【特許請求の範囲】
【請求項１】
公開鍵を生成する方法であって、本願明細書に記載の方法。
【請求項１】
公開鍵を生成する方法であって、本願明細書に記載の方法。
【図１】
【図２】
【図２】
【公開番号】特開２０１０−９７２３６（Ｐ２０１０−９７２３６Ａ）
【公開日】平成２２年４月３０日（２０１０．４．３０）
【国際特許分類】
【出願番号】特願２０１０−２３６０２（Ｐ２０１０−２３６０２）
【出願日】平成２２年２月４日（２０１０．２．４）
【分割の表示】特願２０００−５３８４６３（Ｐ２０００−５３８４６３）の分割
【原出願日】平成１１年３月２３日（１９９９．３．２３）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
【公開日】平成２２年４月３０日（２０１０．４．３０）
【国際特許分類】
【出願日】平成２２年２月４日（２０１０．２．４）
【分割の表示】特願２０００−５３８４６３（Ｐ２０００−５３８４６３）の分割
【原出願日】平成１１年３月２３日（１９９９．３．２３）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
[ Back to top ]