(57)【特許請求の範囲】
【請求項１】
送信者のコンピュータと受信者のコンピュータとの間で通信を行う方法であって、
前記送信者のコンピュータ及び前記受信者のコンピュータはそれぞれ、プロセッサと、情報記憶手段とを有し、
前記方法は、
前記送信者のコンピュータのプロセッサに、受信者の識別情報を取得させる工程と、
前記送信者のコンピュータのプロセッサに、前記受信者が解読鍵を取得するために必要な、受信確認返信要求情報を指定させる工程であって、前記受信確認返信要求情報は、返信アドレスと、前記受信者に送信されるメッセージに対応するメッセージ識別子とを含む、該工程と、
前記送信者のコンピュータのプロセッサに、前記受信者の識別情報および前記受信確認返信要求情報から暗号鍵を導かせる工程と、
前記送信者のコンピュータのプロセッサに、前記受信者の識別情報および前記受信確認返信要求情報から導かれた前記暗号鍵および双線形写像を使用してメッセージを暗号化させる工程であって、前記メッセージを暗号化させる工程は、前記送信者のコンピュータが、代数群の要素Ｐを得て、秘密乱数ｒを選択し、かつｒＰの値を計算する工程を含む、該工程と、
前記送信者のコンピュータのプロセッサに、暗号化されたメッセージおよび計算された値ｒＰを前記送信者のコンピュータから前記受信者のコンピュータに送信させる工程と、
前記受信者のコンピュータに、前記暗号化されたメッセージ及び計算された前記値ｒＰを受信させる工程と、
個人鍵作成器に、前記暗号化されたメッセージの前記受信者からの解読鍵の要求を受信させる工程であって、前記解読鍵の要求は、前記受信確認返信要求情報及び前記受信者の識別情報を含む、該工程と、
前記解読鍵の要求を受け取った後、前記個人鍵作成器に、前記メッセージの受信確認返信を前記送信者のコンピュータに与えさせる工程と、
前記個人鍵作成器に、前記暗号鍵に前記代数群の持つ群作用を適用することによって解読鍵を作成させ、作成された前記解読鍵を受信者に送信させる工程と、
前記受信者のコンピュータのプロセッサに、前記解読鍵を受け取った後、前記解読鍵および前記双線形写像を使用して前記暗号化されたメッセージを解読させる工程とを含むことを特徴とする方法。
【請求項２】
前記個人鍵作成器に、前記解読鍵の要求を受け取った後、受信結果をログの一部として記憶媒体上に格納させる工程を更に含むことを特徴とする請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は一般的に暗号システムに関する。
【背景技術】
【０００２】
公開鍵暗号システムでは、当事者２人がプライベートな認証されたメッセージを交換するのに、秘密鍵を共有するための秘匿性のある通信チャネルを最初に確保する必要がない。最も広く使用されている公開鍵暗号システムの１つは、（特許文献２）で開示されているＲＳＡ暗号システムである。ＲＳＡ暗号システムは、現在、多くの商用システムに搭載されている。この暗号システムは、Ｗｅｂトラフィックの秘匿性保護のためＷｅｂサーバおよびブラウザによって使用され、電子メールのプライバシーと認証の保護、およびリモート・ログイン・セッションの秘匿性保護を目的としても使用され、さらに電子クレジット・カード決済システムの心臓部に配置されている。つまり、ＲＳＡは、デジタル・データの秘匿性が懸念されるアプリケーションで使用されることが多い。
【０００３】
ＲＳＡ暗号システムなどの公開鍵暗号システムによれば、各個人は、秘密にしておく秘密鍵と公開されている公開鍵からなる特定の１対の鍵を持つ。この鍵の対は、（１）公開鍵だけがわかっても、秘密鍵を推論できず、（２）この２つの鍵は相補的である、つまりこの対の一方の鍵で暗号化されたメッセージは、相補的な鍵でしか解読できないという２つの重要な特性を有する。これらのシステムでは、一対の公開鍵と秘密鍵は両方とも、入力として乱数シードを受け取る鍵作成アルゴリズムの出力として一緒に作成される。そのため、これらの暗号システムでは、ユーザが望むような公開鍵または秘密鍵を選択できず、鍵作成アルゴリズムによってユーザ向けに作成された鍵をそのまま使用するしかない。このような方法は、他の人がある人へのメッセージを暗号化しようにも、その人が公開鍵を作成し公開していないと暗号化できないという欠点を有する。このタイプの暗号システムには、ほかに、悪意ある人が公開鍵を公開し、その鍵が誰か他の人のものだと主張することが可能だという問題がある。このような課題を解決するために、信頼できる公開鍵証明書発行機関（ＣＡ）を利用して、個人を認証し、その個人の公開鍵が真正の鍵であることを他の人に証明する。しかし残念なことに、このような対策だと、送信者がすべての受信者の証明書を取得しなければならず、既存の証明書の有効期限が切れる毎に新規証明書を取得する必要があるため、暗号システムの複雑さが増す。さらに、受信者側で、公開鍵を作成し、公開し、証明書をＣＡに登録し、期限が切れる場合にそのような証明書を更新する必要がある。
【０００４】
１９８４年に、シャミール（Ｓｈａｍｉｒ）は、新しいタイプの公開鍵暗号化方式を考えた（（非特許文献１）で説明されている）。シャミール（Ｓｈａｍｉｒ）の方式によれば、ユーザの公開鍵は、ユーザの名前とネットワーク・アドレス、または、名前と電子メール・アドレス、社会保障番号、住所、電話番号、または勤先住所との組み合わせ、などの公開識別子からなる。公開鍵はユーザの既存の公開識別子（ＩＤ）であって、乱数シードから作成された鍵ではないため、この種の公開鍵暗号システムはＩＤベース暗号（ＩＢＥ）方式と呼ばれる。しかし、シャミール（Ｓｈａｍｉｒ）は、具体的な実用的ＩＢＥ暗号システムを提示していなかった。実際、シャミール（Ｓｈａｍｉｒ）は、既存の暗号システム（ＲＳＡなど）は、秘匿性ＩＢＥ暗号システムを実現するのに適さないだろうと主張していた。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国仮出願第６０／３１１９４６号
【特許文献２】米国特許第４，４０５，８２９号
【非特許文献】
【０００６】
【非特許文献１】エー・シャミール（Ａ．Ｓｈａｍｉｒ）"Ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ａｎｄ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ"、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｃｒｙｐｔｏ  '８４、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｖｏｌ．１９６、Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ、４７−５３ページ、１９８４年
【非特許文献２】ディー・ボネ（Ｄ．Ｂｏｎｅｈ），エム・フランクリン（Ｍ．Ｆｒａｎｋｌｉｎ），"Ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  ｐａｉｒｉｎｇ"，ｅｘｔｅｎｄｅｄ  ａｂｓｔｒａｃｔ  ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｃｒｙｐｔｏ  ２００１，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，第２１３９巻、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２３１−２２９、２００１年
【非特許文献３】イー・フジサキ（Ｅ．Ｆｕｊｉｓａｋｉ）およびティー・オカモト（Ｔ．Ｏｋａｍｏｔｏ）"Ｓｅｃｕｒｅ  ｉｎｔｅｇｒａｔｉｏｎ  ｏｆ  ａｓｙｍｍｅｔｒｉｃ  ａｎｄ  ｓｙｍｍｅｔｒｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅｓ"，ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｃｒｙｐｔｏ  '９９，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，第１６６６巻，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．５３７−５５４、１９９９年
【非特許文献４】エー・ミヤジ（Ａ．Ｍｉｙａｊｉ）、エム・ナカバヤシ（Ｍ．Ｎａｋａｂａｙａｓｈｉ）、エス・タカノ（Ｓ．Ｔａｋａｎｏ）"Ｎｅｗ  ｅｘｐｌｉｃｉｔ  ｃｏｎｄｉｔｉｏｎ  ｏｆ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｔｒａｃｅ  ｆｏｒ  ＦＲ−ｒｅｄｕｃｔｉｏｎ"，ＩＥＩＣＥ  Ｔｒａｎｓ．Ｆｕｎｄａｍｅｎｔａｌｓ，第Ｅ８４Ａ巻，Ｎｏ．５，２００１年５月
【非特許文献５】アール・ゲナロ（Ｒ．Ｇｅｎｎａｒｏ）、エス・ジャレッキ（Ｓ．Ｊａｒｅｃｋｉ）、エイチ・クラウチク（Ｈ．Ｋｒａｗｃｚｙｋ）、ティー・レービン（Ｔ．Ｒａｂｉｎ）"Ｓｅｃｕｒｅ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ  ｆｏｒ  Ｄｉｓｃｒｅｔｅ−Ｌｏｇ  Ｂａｓｅｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ"，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｅｕｒｏｃｒｙｐｔ  '９９，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，第１５９２巻，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２９５−３１０，１９９９年
【非特許文献６】ディー・ボネ（Ｄ．Ｂｏｎｅｈ），ビー・リン（Ｂ．Ｌｙｎｎ），エイチ・シャッチャム（Ｈ．Ｓｈａｃｈａｍ），"Ｓｈｏｒｔ  ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  ｐａｉｒｉｎｇ"，ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＡｓｉａＣｒｙｐｔ  ２００１，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，第２２４８巻，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．５１４−５３２，２００１年）
【０００７】
本出願特許の英語原文には、特許出願に使用できない符号が多数使用されているので、翻訳文においては表１の対照表に示す符号を使用した。また、上付きと下付きが上下になっているものは、「Ａｂｃ」のようにずらして入力した。
【表１】
0005933786.tif 000002
【発明の開示】
【発明が解決しようとする課題】
【０００８】
シャミール（Ｓｈａｍｉｒ）がＩＢＥ方式を提案してから数年の間に、ＩＤベース暗号システムを実現する試みがいくつか行われた。いくつかの提案では、ユーザ同士が共謀しないことが必要である。また他の提案では、個人鍵作成器（ＰＫＧ）がそれぞれの個人鍵作成要求を処理するのに非現実的な時間がかかる。また別の提案では、不正操作防止ハードウェアを必要とする。
【０００９】
つまり、改善された暗号化の方法およびシステムが必要とされているということである。
【課題を解決するための手段】
【００１０】
本発明の一実施形態によれば、送信者によって受信者に送信される第１の情報を暗号化する方法は、第２の情報から作成された暗号化鍵を使用する。送信者から受信者に送信される第１の情報の少なくとも一部を暗号化するために、双線形写像および暗号化鍵を使用する。双線形写像は対称でも非対称でもよい。双線形写像は、楕円曲線から導かれる代数群上で定義されたＷｅｉｌペアリングまたはＴａｔｅペアリングに基づく。より一般的には、双線形写像は、代数多様体上で定義されたペアリングに基づいていてよい。
【００１１】
本発明の一実施形態によれば、第１の情報の一部の暗号化は、暗号化鍵に対応する解読鍵を作成する前に完了することが可能である。
本発明の他の実施形態によれば、第２の情報は、暗号化鍵に対応する解読鍵を作成する前に受信者に公開されている。第２の情報は、本発明の異なる実施形態により、受信者に関連付けられた電子メール・アドレス、名前またはその他の識別子を含むことができる。第２の情報はさらに、さまざまな実施形態によれば、１つ以上の時間間隔を定義する日付または一連の日付など、１つ以上の時刻に対応する受信者または情報に関連付けられた属性を含むこともできる。解読鍵は、時刻に対応する情報に関して解読鍵の要求が受信された時刻に基づいて提供され得る。本発明の他の実施形態によれば、第２の情報は、メッセージ識別子、信任状識別子、メッセージ・サブジェクト識別子を含むことができる。
【００１２】
本発明の他の実施形態によれば、双線形写像を使用してメッセージ鍵を暗号化鍵から作成し、暗号ハッシュ関数をそのメッセージ鍵に適用する。
本発明の他の実施形態によれば、第１の情報の一部の暗号化は、双線形写像を使用して第２の情報からマスクを作成することを含む。マスクは、第２の情報の一部に適用される。
【００１３】
本発明の一実施形態は、受信者に関連付けられたＩＤベース暗号化鍵を使用して送信者によって暗号化された暗号文を解読する方法を対象とする。暗号化鍵から導かれる解読鍵が得られる。暗号文の少なくとも一部は、双線形写像および解読鍵を使用して解読される。双線形写像は対称でも非対称でもよい。双線形マップは、楕円曲線から導かれる代数群上で定義されたＷｅｉｌペアリングまたはＴａｔｅペアリングに基づく。
【００１４】
本発明の他の実施形態によれば、暗号文は解読鍵を作成する前に得られる。本発明の他の実施形態によれば、第１の情報は、暗号文を得る前に、また解読鍵を得る前に受信者に公開されている。解読鍵を得るには、暗号文とともに送信された情報も含めて、要求を個人鍵作成器に送る。
【００１５】
本発明の一実施形態は、暗号化鍵に対応する解読鍵を作成する方法を対象とする。代数群、群作用、およびマスター鍵が与えられる。暗号化鍵は、第１の情報に基づいて作成される。解読鍵は、群作用、マスター鍵、および暗号化鍵に基づいて作成される。本発明の一実施形態によれば、群作用を多項式時間内で計算し得る。本発明の他の態様によれば、マスター鍵がない場合、解読鍵を作成するには多項式時間よりも長い時間を要する。
【００１６】
本発明の他の実施形態は、暗号システムのシステム・パラメータを与える方法を対象とする。位数ｑの代数群★Ｇ１および★Ｇ２は、関連する群作用とともに与えられる。さらに、★Ｇ１内の点の対を★Ｇ２の点に対応させる双線形マップが与えられる。他の実施形態では、Ｇ１の要素Ｐを表すシステム・パラメータおよびＧ１の要素Ｐｐｕｂを表すシステム・パラメータが与えられるが、ただし、ＰｐｕｂはＰに適用されるマスター鍵ｓの群作用に基づく。本発明の他の実施形態では、１つ以上のハッシュ関数Ｈ１、Ｈ２、Ｈ３、またはＨ４からなる関数群を表すシステム・パラメータが与えられる。本発明の他の実施形態では、メッセージ空間のサイズｎを表すシステム・パラメータが与えられる。
【００１７】
本発明の他の実施形態は、暗号システムのシステム・パラメータを与える方法を対象とする。位数ｑの代数群★Ｇ１および★Ｇ２は、関連する群作用とともに与えられる。さらに、★Ｇ１内の点の対を★Ｇ２の点に対応させる双線形マップが与えられる。他の実施形態では、Ｇ１の要素Ｐを表すシステム・パラメータおよびＧ１の要素Ｐｐｕｂを表すシステム・パラメータが与えられるが、ただし、ＰｐｕｂはＰに適用されるマスター鍵ｓの群作用に基づく。本発明の他の実施形態では、１つ以上のハッシュ関数Ｈ１、Ｈ２、Ｈ３、またはＨ４からなる関数群を表すシステム・パラメータが与えられる。本発明の他の実施形態では、メッセージ空間のサイズｎを表すシステム・パラメータが与えられる。
【００１８】
本発明の他の実施形態によれば、双線形写像は非対称でも対称でもよい。他の実施形態では、双線形写像は、楕円曲線の一部の上で定義されたＷｅｉｌペアリングまたはＴａｔｅペアリングに基づく。
【００１９】
本発明の他の実施形態によれば、代数群Ｇ１は、位数ｐの場上で定義された楕円曲線により定義され、位数ｑは位数ｐよりも小さい。本発明の他の態様によれば、ｐの長さは少なくとも１０２４ビットであり、ｑの長さは１６０ビット以下である。
【００２０】
本発明の他の実施形態は、マスター鍵の割符を作成することを含む暗号通信を管理する方法を対象とする。割符は、別のシステム内に格納される。秘密鍵を取得する受信者からの要求に対して、別のシステムでマスター鍵のそれぞれの割符から秘密鍵の対応するそれぞれの割符を作成することにより応答する。受信者は秘密鍵の割符から秘密鍵を構成し、その秘密鍵は受信者の識別情報に対応する。
【００２１】
本発明の他の実施形態は、送信者と受信者との間で通信を行うための方法を対象とする。送信者から受信者に送信されるメッセージが暗号化され、メッセージが送信者から受信者に送信される。メッセージの受信者からの解読鍵の要求が受信される。解読鍵の要求を受信した後、受信者がメッセージを受信したことを示す情報が作成され、受信者に解読鍵が与えられる。本発明の実施形態によれば、送信者の返信アドレスがメッセージに含まれ、メッセージを受信したことを示す確認通知が返信アドレスに送信される。本発明の他の態様によれば、メッセージの識別が確認通知に含まれ、その確認通知は送信者に送信される。本発明の他の態様によれば、暗号化鍵は送信者の返信アドレスに基づいて導出される。
【００２２】
本発明の他の実施形態は、送信者と信任状を有する受信者との間で通信を行うための方法を対象とする。受信者の識別情報を取得する。受信者が解読鍵を取得するために必要な信任状を指定すると、受信者の識別情報と信任状から暗号化鍵が導かれる。送信者から受信者に送信されるメッセージは、暗号化鍵および双線形写像を使用して暗号化され、メッセージが、送信者から受信者に送信される。メッセージの受信者からの解読鍵の要求を受信する。受信者が信任状を持っているかどうかが調べられ、受信者が信任状を持っていれば、解読鍵が受信者に与えられる。そこで、受信者は解読鍵と双線形写像を使用してメッセージを解読できる。
【００２３】
本発明の他の実施形態は、送信者と、ターゲット・システム上で解読鍵を格納することにかかわる受信者と、の間で通信を行う方法を対象とする。メッセージを解読する時刻に関連付けられている解読鍵の集まりを導出することができ、解読鍵はターゲット・システムに格納される。暗号化鍵は、メッセージが解読される時刻に関連付けられている文字列から導出される。暗号化鍵を使用してメッセージを暗号化する。ターゲット・システム上でメッセージを受信すると、そのメッセージは、双線形写像および対応する解読鍵を使用して解読される。
【００２４】
本発明の他の実施形態は、責任関係の異なる実体（エンティティ）に関わる送信者と受信者との間で通信を行う方法を対象とする。１組の解読鍵を、マスター鍵および異なる責任関係に関連付けられている１組の文字列から導出する。それぞれの責任関係のあるエンティティに解読鍵が与えられる。暗号化鍵は、異なる責任関係のうちの１つに関連付けられている文字列から導出される。暗号化鍵および双線形写像を使用して、送信者から受信者に送信されるメッセージが暗号化される。特定の責任を有するエンティティが、メッセージを受信し、それぞれの解読鍵および双線形写像を使用してメッセージを解読する。本発明の一実施形態によれば、特定の責任に対応する文字列として、電子メールの件名行がある。
【図面の簡単な説明】
【００２５】
【図１】送信者、受信者、および個人鍵作成器（ＰＫＧ）によって実行される工程およびそれらの間でやり取りされる情報を示す、本発明の実施形態による暗号システムを説明するブロック図。
【図２】本発明の一実施形態により秘密鍵を作成するときにＰＫＧによって実行される工程を説明するブロック図。
【図３】本発明の一実施形態により秘密メッセージ鍵を計算し、その鍵を使用して受信者を送り先とするメッセージを暗号化する場合に送信者によって実行される工程を説明するブロック図。
【図４】本発明の一実施形態により秘密メッセージ鍵を計算し、その鍵を使用して送信者から受信した暗号文を解読する場合に受信者によって実行される工程を説明するブロック図。
【図５】本発明の一実施形態による分散ＰＫＧを説明するブロック図。
【図６】本発明の一実施形態によるエスクロー解読機能を備える暗号システム内の要素を説明するブロック図。
【図７】本発明の一実施形態によるエスクロー解読機能を備えるＥｌＧａｍａｌ暗号システムでメッセージを暗号化する場合に送信者によって実行される工程を説明するブロック図。
【図８】本発明の一実施形態によるエスクロー解読機能を備えるＥｌＧａｍａｌ暗号システムでメッセージを解読する場合に受信者によって実行される工程を説明するブロック図。
【図９】本発明の他の実施形態によるエスクロー解読機能を備えるＥｌＧａｍａｌ暗号システムでメッセージを解読する場合にエスクローによって実行される工程を説明するブロック図。
【図１０】本発明の一実施形態によりＩＤベース暗号化システムで信用状を管理するシステムを説明するブロック図。
【図１１】本発明の一実施形態による鍵委託機能を備えるシステムを説明するブロック図。
【図１２】本発明の一実施形態による受信確認返信機能を備える暗号システムを説明するブロック図。
【発明を実施するための形態】
【００２６】
以下の説明では、本発明の暗号化手法のいくつかの実施例の詳細を述べ、またシステムの秘匿性の技術的内容についても解説する。
概要
現代の暗号システムでは普通のことであるが、本発明でも、その手法は一般的に、通信媒体に接続されたコンピュータ上に実装される。通常、コンピュータはインターネットまたは他のコンピュータ・ネットワークにより接続されるが、通信媒体も使用され得る。
【００２７】
本発明の一実施形態は、ＩＤベース情報から導かれる秘密メッセージ鍵を使用するＩＤベース暗号化システムを含む。送信者側はメッセージ鍵を使用してメッセージを暗号化し、受信者側はそのメッセージを解読することができる。秘密メッセージ鍵は、受信者のＩＤベース公開鍵から送信者により計算される。受信者側では、受信者のＩＤベース公開鍵から導かれる受信者の秘密鍵から同じメッセージ鍵を計算することができる。送信者および受信者は両方とも、双線形写像を使用して同じ秘密鍵を計算する。例えば、一実施形態では、非対称または対称双線形写像ｅ＾：★Ｇ０×★Ｇ１→★Ｇ２を使用するが、ただし、★Ｇ０、★Ｇ１、★Ｇ２は（必ずしも異なるものではない）代数群である。★Ｇ０が★Ｇ１に等しい場合、双線形写像は対称であるといい、ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２と表すことが多い。非退化で、効率よく計算できる双線形写像ｅ＾は、認容写像と呼ぶ。本発明のいくつかの実施形態では、双線形写像は認容的であるのが好ましい。
【００２８】
この説明全体の規約として、★Ｇ０および★Ｇ１の群演算を加法で表し、★Ｇ２の群演算を乗法で表す。素数位数の群★Ｇについては、★Ｇ＊で集合★Ｇ＊＝★Ｇ＼｛Ｏ｝を表すが、ただしＯは群★Ｇの単位要素とする。任意の長さの２進数列の集合を、｛０，１｝＊で表す。★Ｚｑで、ｑを法とする加法による群｛０，．．．，ｑ−１｝を表し、★Ｚ＋で、正の整数の集合を表す。加法の繰り返しにより★Ｇ上に★Ｚｑの自然な群作用が与えられること、および要素Ｐ∈★Ｇに対する要素ａ∈★Ｚｑの作用の結果をａＰと表すことに注意されたい。
【００２９】
本発明の他の実施形態によれば、ある種の計算Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（写像ｅ＾を伴う）は難しい問題である。一実装では、写像ｅ＾は認容的であり、★Ｇ０、★Ｇ１、★Ｇ２の位数の素因数ｑは非常に大きい。。★Ｇ０、★Ｇ１、★Ｇ２の位数は互いに等しくてもよい。以下の説明では、簡単にするため、一般性を失うことなく、★Ｇ０、★Ｇ１、★Ｇ２の位数はすべて素数位数ｑであると仮定する。
【００３０】
実施例では、認容写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を使用して、以下のようにＩＤベース暗号システムを実現している。メッセージを暗号化するために、送信者は、送り先である受信者の公開識別子ＩＤと関連付けられた公開鍵ＱＩＤ∈★Ｇ１を使用する。暗号化されたメッセージを解読するために、受信者は相補的な秘密鍵ｄＩＤ∈★Ｇ１を使用する。秘密鍵は、公開鍵ＱＩＤ、秘密マスター鍵ｓ∈★Ｚ＊ｑ、および★Ｇ１上の★Ｚ＊ｑの群作用から計算される。一実施形態では、例えば、ｄＩＤ＝ｓＱＩＤである。秘密マスター鍵ｓは信頼できるＰＫＧにのみ公開されているため、ユーザは通常、自分自身で秘密鍵を計算することは可能でない。秘密鍵を取得するには、個人が認証の済んだ後にＰＫＧから取得するのが好ましい。しかし、対応する秘密鍵が決定される前であっても、誰でも任意の公開識別子ＩＤに関連付けられた公開鍵ＱＩＤをいつでも計算することが可能である。例えば、一実施形態では、公開鍵ＱＩＤは、（１）従来の指標符号化方式を使用して公開識別子ＩＤを｛０，１｝＊の対応する２進数列に写像し、（２）ハッシュ関数Ｈ１：｛０，１｝＊→★Ｇ＊１を使用して２進数列を★Ｇ＊１の要素ＱＩＤにハッシュすることで得られるが、ただし、ＱＩＤの位数はｑとする。
【００３１】
この実施形態では、公開識別子ＩＤを有する受信者を宛先とするメッセージの暗号化および解読を以下のように行うことができる。送信者は認容写像ｅ＾を使用して、秘密メッセージ鍵を決定することができる。送信者および受信者は同じ情報をすべて共有するわけではないが、写像ｅ＾が双線形であるという事実を使用することで、異なる情報を使って同じメッセージ鍵を計算することが可能である。それぞれプライベートの情報を使用するため、メッセージ鍵は秘密である。
【００３２】
このアプローチの実装方法を説明するため、送信者は★Ｇ１の要素ＰおよびｓＰを知っていると仮定する。一実施形態では、例えば、★Ｇ１の要素ＰおよびＰｐｕｂ＝ｓＰは公開されたシステム・パラメータである。そこでさらに、送信者は非公開で、乱数ｒ∈★Ｚ＊ｑを選択し、受信者のＩＤベース公開鍵ＱＩＤを使用してｇｒＩＤ＝ｅ＾（ｒＱＩＤ，ｓＰ）を使用する。要素ｇｒＩＤはＩＤベースの秘密であり、送信者はこれを秘密メッセージ鍵として使用し、受信者へのメッセージのＩＤベース暗号化を実行する。次に、送信者は、暗号化されたメッセージをｒＰとともに受信者に送信することができる。すると受信者は、ｒＰを受信し、それを秘密鍵ｓＱＩＤとともに使用して、秘密メッセージ鍵ｇｒＩＤ＝ｅ＾（ｓＱＩＤ，ｒＰ）を計算する。この秘密メッセージ鍵は、ｅ＾写像の双線形性より、送信者によって計算される秘密メッセージ鍵に等しい。この計算された要素ｇｒＩＤ∈★Ｇ２は、したがって、受信者が要素ｒＰおよび秘密鍵ｓＱＩＤを使用して計算することができる送信者のＩＤベース秘密鍵である。この秘密鍵は、送信者と受信者との間の暗号化された通信を行うためのメッセージ鍵として使用することができる。
【００３３】
ＰＫＧはさらに、受信者の秘密鍵も知っているため、さらに秘密メッセージ鍵を計算し、メッセージを解読することが可能であることに注意されたい。送信者、受信者、およびＰＫＧすべてに、秘密メッセージ鍵を計算するための十分な情報がすべて用意されている。しかし、他のエンティティにはいっさい、通常、送信者の秘密鍵ｒまたは受信者の秘密ｓＱＩＤは公開されない。この実施形態の秘匿性は、ｒが公開されていない、またはｓＱＩＤが公開されていないと、双線形写像を使用しｒ、ｓ、およびＱＩＤの組み合わせに基づいて秘密メッセージ鍵を計算することの困難さに関係している。
【００３４】
一実施形態では、メッセージ鍵ｇｒＩＤを使用し、ＸＯＲ演算（「○＋」で表される）を使用してメッセージのビットの暗号化および解読を行うのに使用されるマスクを決定する。特に、メッセージＭの暗号文Ｖは、Ｈ２：★Ｇ２→｛０，１｝ｎをハッシュ関数とし、ｎをメッセージのビット長として、Ｖ＝Ｍ○＋Ｈ２（ｇｒＩＤ）を計算して得られる。逆に、メッセージＭは、Ｍ＝Ｖ○＋Ｈ２（ｇｒＩＤ）を計算することにより暗号文Ｖから復元される。
【００３５】
他の実施形態では、上で概要を述べた一方向暗号化方式は、選択暗号文秘匿システムに変換することにより秘匿性を高められる。本発明の一実施形態では、例えば、Ｆｕｊｉｓａｋｉ−Ｏｋａｍｏｔｏの一般的手法を使用する。
【００３６】
他の実施形態では、マスター鍵は、分散ＰＫＧの複数の個人鍵作成器に分散させた成分ｓＩに分割される。識別子ＩＤに基づく公開鍵ＱＩＤを持つユーザが与えられた場合、分散ＰＫＧ内の個人鍵作成器のそれぞれがＱおよびマスター鍵の公開鍵部分ｓＩを使用して秘密鍵部分ｄＩを計算する。これらの秘密鍵部分は、ＱＩＤで暗号化されたメッセージを解読するため、ユーザによって組み合わされ、単一の秘密鍵ｄＩＤとして使用される可能性がある。
【００３７】
他の実施形態では、ＥｌＧａｍａｌ暗号化方式に鍵エスクローが組み込まれる、つまり任意の公開鍵で暗号化された暗号文を１つの大域的なエスクロー鍵で解読することが可能である。この実施形態では、上述のシステム例は以下のように適合される。受信者はさらに、要素ＰおよびｓＰも知っていると想定する。受信者は、ＰＫＧから秘密鍵を取得するのではなく、乱数ｘ∈★Ｚ＊ｑを選択し、群作用を使用してｘＰを計算し、計算結果に基づいて公開鍵を公開することにより公開／秘密鍵の対を作成する。一実施形態では、公開鍵はｘＰであり、相補的秘密鍵はｄ＝ｘ（ｓＰ）である。（したがって、ｘＰは、ＱＩＤの役割を担い、ｄ＝ｘ（ｓＰ）＝ｓ（ｘＰ）はｄＩＤ＝ｓＱＩＤの役割を担う。）受信者へのメッセージを暗号化するには、送信者は前のように、乱数ｒを選択して、ｒＰを受信者に送信する。次に、ｘ（ｓＰ）＝ｄは秘密であるとして、受信者は対（ｒＰ，ｘ（ｓＰ））を知り、ｒ（ｘＰ）は秘密であるとして、送信者は対（ｓＰ，ｒ（ｘＰ））を知る。そのため、送信者および受信者は両用とも、ｇ＝ｅ＾（ｒＰ，ｘ（ｓＰ））＝ｅ＾（ｓＰ，ｒ（ｘＰ））を計算し、ただし、第２の等式はｅ＾の双線形性から導かれる。しかし、この秘密も、マスター鍵の情報ｓからを調べることが可能である。送信者からの要素ｒＰ、受信者の公開鍵ｘＰ、およびマスター鍵ｓを使用し、ｇ＝ｅ＾（ｒＰ，ｓ（ｘＰ））を評価することよりメッセージ鍵を計算することが可能である。この実施形態では、対称双線形写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を使用することに注意されたい。
【００３８】
本発明のいくつかの実施形態では、★Ｇ１は楕円曲線の部分群であり、認容写像ｅ＾は楕円曲線上のＷｅｉｌペアリング（またはＴａｔｅペアリング）から構成される。（ただし、定義より、部分群は、必ずしも、群よりも小さいわけではないことに留意されたい。つまり、★Ｇ１は楕円曲線全体の場合もあるということである。）より一般的には、★Ｇ１をアーベル多様体とし、ｅ＾を★Ｇ１の要素の認容的ペアリングとすることができる。★Ｇ０および★Ｇ１が異なるものとして写像ｅ＾：★Ｇ０×★Ｇ１→★Ｇ２を使用するいくつかの実施形態では、★Ｇ０はさらに、楕円曲線の部分群、つまりアーベル多様体であってもよい。
【００３９】
他の実施形態では、ＩＤベース暗号化のさまざまな新規性のある応用が考えられる。他の種類の公開識別子、または機能強化された公開識別子を使用することによりＩＢＥシステムの新しい有用な応用が可能である。例えば、公開識別子ＩＤは個人に関連付けられた識別子に限られず、個人だけでなく組織、政府機関、企業などのあらゆる種類のエンティティと関連付けられた識別子であってもよい。また、グループを形成する個々のアイデンティティから自然の組み合わせにより、対応するグループ秘密鍵を備えるグループのジョイント・アイデンティティが得られることにも注意されたい。グループの秘密鍵は、ＰＫＧによって発行される必要はなく、単に、グループを構成する別々の秘密鍵の組み合わせである。エンティティのアイデンティティを指定する基本ＩＤは、名前、電子メール・アドレス、住所、またはエンティティの社会保障番号に限られず、ドメイン名、ＵＲＬ、９ケタ郵便番号、納税者番号など他の種類の情報を含めることもできることにも注意しなければならない。多くの応用では、公開識別子ＩＤは、特定のエンティティまたはエンティティの集まりに一意に関連付けられる一般に知られている何らかの文字列を含む。しかし、一般的に、公開識別子ＩＤは、任意の文字列またはその他の任意の情報とすることが可能である。
【００４０】
ＩＢＥのさまざまな有用な応用では、機能強化された公開識別子を利用する。機能強化された識別子は、必ずしも、特定のエンティティの独自性を指定する情報に限られない情報を含む一種の識別子とすることができる。例えば、ＩＤは、エンティティに関連付けられたライセンス番号、肩書き、または機密取扱資格などの信任状記述子を含めることが可能である。機関は、機関が証明するエンティティにのみ秘密鍵を与えることにより信任状を管理することが可能である。一実施例では、ＩＤに、連続番号、車両識別番号、特許番号などの所有物記述子を含めることが可能である。資産所有者の登録および所有者の認証を担当する機関は、その機関によって真の所有者であるとして登録されるエンティティにのみ秘密鍵を与えることにより資産登録を管理することが可能である。より一般的に、２つまたはそれ以上の物事の間の関連は、ＩＤにその識別子を含めることにより管理することが可能である。その後、ＰＫＧは、物事の間の関連付けに対する管理権限を有するものとして機能する。
【００４１】
他の種類の機能強化されたＩＤとして、時刻、時間間隔、または１組の時間間隔を含む識別子がある。このような識別子に対する秘密鍵は、ある時刻になると自動的に期限切れになるように、ある時間の経過後にのみ自動的にアクティブ状態になるように、または１つ以上の指定された時間間隔についてのみ有効となるように構成することが可能である。この手法を信任状および所有権管理と組み合わせることにより、アクティブ化および／または期限切れの時間を制御することが可能である。
【００４２】
上記の例から、本発明によるＩＤベース暗号化システムは特定の種類の識別子に限られないことは明白である。したがって、「ＩＤベース」という用語は、任意の文字列またはその他の任意の情報を基盤として使用できることを示すものとして一般的に理解すべきである。
【００４３】
他の実施形態によれば、ＩＢＥシステムを使用することで解読機能を委託することができる。エンティティは、自分の秘密マスター鍵を使って自分のＩＢＥシステムを設定し、このＩＢＥシステムに対してＰＫＧの役割を担うことが可能である。エンティティにはマスター鍵があるため、エンティティは鍵を発行することで、解読機能を他のエンティティに委託することが可能である。例えば、エンティティが企業であれば、その従業員は企業ＰＫＧから秘密鍵を取得することが可能である。個人に対し、その名前、肩書き、責務、プロジェクト、事例、または職務関係の識別子と一致する秘密鍵を発行することが可能である。他の例では、個人が業務出張時のみ有効な秘密鍵をラップトップに対して発行することが可能である。ラップトップの紛失または盗難が発生した場合でも、その期間の鍵しか損なわれない。マスター鍵は、家に保存しておくため、損なわれることはない。
【００４４】
また、通信の媒体は電子メールまたはインターネットに限られる必要はなく、印刷された刊行物、デジタル記録媒体、ラジオ放送、無線通信などの通信媒体も考えられる。
定義
ＩＤベース暗号化。ＩＤベース暗号化システムおよびその方法＄ｅの実施例では、Ｓｅｔｕｐ、Ｅｘｔｒａｃｔ、Ｅｎｃｒｙｐｔ、Ｄｅｃｒｙｐｔの４つのランダム・アルゴリズムを使用する。
【００４５】
Ｓｅｔｕｐ：秘匿性パラメータｋが与えられた場合、ｐａｒａｍｓ（システム・パラメータ）およびｍａｓｔｅｒ−ｋｅｙを返す。このシステム・パラメータは、有限メッセージ空間＄Ｍの説明および有限暗号文空間＄Ｃの説明を含む。通常、システム・パラメータは、周知であるが、ｍａｓｔｅｒ−ｋｅｙは個人鍵作成器（ＰＫＧ）にのみ公開される。
【００４６】
Ｅｘｔｒａｃｔ：入力として、ｐａｒａｍｓ、ｍａｓｔｅｒ−ｋｅｙ、および任意のＩＤ∈｛０，１｝＊を受け取り、秘密鍵ｄを返す。ここで、ＩＤは公開鍵として使用される任意の文字列であり、ｄは対応する秘密解読鍵である。Ｅｘｔｒａｃｔアルゴリズムは、与えられた公開鍵から秘密鍵を抽出する。抽出にはｍａｓｔｅｒ−ｋｅｙが必要なため、通常は、ＰＫＧによって抽出が実行される。
【００４７】
Ｅｎｃｒｙｐｔ：入力として、ｐａｒａｍｓ、ＩＤ、およびＭ∈＄Ｍを受け取る。暗号文Ｃ∈＄Ｃを返す。
Ｄｅｃｒｙｐｔ：入力として、ｐａｒａｍｓ、Ｃ∈＄Ｃ、および秘密鍵ｄを受け取る。Ｍ∈＄Ｍを返す。
【００４８】
本発明の一実施形態によれば、これらのアルゴリズムは、暗号化されたメッセージが解読により忠実に復元されることを保証する標準の一貫性制約を充足する。より具体的には、ｄがアルゴリズムＥｘｔｒａｃｔによって作成された秘密鍵である場合、公開鍵としてＩＤが与えられると以下の式が成り立つ。
【００４９】
∀Ｍ∈＄Ｍ：Ｄｅｃｒｙｐｔ（ｐａｒａｍｓ，Ｃ，ｄ）＝Ｍ  ただし、Ｃ＝Ｅｎｃｒｙｐｔ（ｐａｒａｍｓ，ＩＤ，Ｍ）。
本発明の一実施形態によるＩＤベース暗号システムでは、図１に示されているように、上記のアルゴリズムが一緒に使用される。送信者１００はＥｎｃｒｙｐｔを使用し、受信者１１０はＤｅｃｒｙｐｔを使用し、ＰＫＧ  １２０はＳｅｔｕｐとＥｘｔｒａｃｔを使用する。メッセージＭを受信者１１０に送信するために、送信者１００は受信者のＩＤ（例えば、受信者の電子メール・アドレス）を取得し、無作為に選択した整数ｒと組み合わせて秘密メッセージ鍵ｇｒＩＤを計算する。要素ｒＰが受信者１１０に送信されると、受信者１１０はその要素を秘密鍵ｄＩＤと組み合わせて、同じメッセージ鍵ｇｒＩＤを決定する。送信者および受信者は秘密メッセージ鍵を共有しているため、送信者によりこの鍵で暗号化されたメッセージは、受信者側で解読することが可能である。特に、送信者はＭをメッセージ鍵で暗号化し、暗号文Ｖを作成して、ｒＰとともに受信者に伝達する。そこで、受信者は、秘密メッセージ鍵を使用して、暗号文を解読し、元のメッセージを復元する。しかし、メッセージを解読するために、受信者１１０は最初に、ＰＫＧ  １２０から秘密鍵ｄＩＤを取得しておかなければならない。ＰＫＧが受信者のアイデンティティを認証した後、受信者に、受信者のＩＤに対応する秘密鍵を供給する。（ただし、この実施形態では、ＰＫＧはシステム内で任意の秘密鍵を計算することが可能であり、したがって、システム内で任意のユーザへの任意のメッセージを解読することが可能であることに注意されたい。）
選択暗号文の秘匿性。選択暗号文の秘匿性（ＩＮＤ−ＣＣＡ）は、公開鍵暗号化方式の秘匿性の標準的な受け入れられる概念である。ＩＤベース暗号化システムおよび方法の実施形態は、この秘匿性という強力な概念を充足するように実装することができる。さらに、選択暗号文の秘匿性の選択されたレベルを少し強化することができる。なぜなら、敵対者がＩＤベース・システム内の公開鍵ＩＤに攻撃をしかけたときに、敵対者はすでに自分が選択したユーザＩＤ１，．．．，ＩＤｎの秘密鍵を所有しているおそれがあるからである。本発明の一実施形態では、システムはこのような攻撃にさらされても秘匿性を保持する。つまり、本システムは、敵対者が自分の選択したアイデンティティＩＤＩに関連する秘密鍵（攻撃されている公開鍵ＩＤ以外）を取得することが可能な場合であっても秘匿性を保持するということである。このようなクエリを秘密鍵抽出クエリと呼ぶ。さらにこの実施形態のシステムは、敵対者が自分の選んだ公開鍵ＩＤについてチャレンジを受けたとしても、秘匿性を保持する（ランダム公開鍵とは反対に）。
【００５０】
以下のＩＮＤ−ＩＤ−ＣＣＡゲームにおいてチャレンジャに対する無視できない優位性を持つ多項式有界敵対者＄Ａがいない場合、ＩＤベース暗号化システムまたは方法＄ｅの実施形態は、適応的選択暗号文攻撃に対する意味秘匿性（ＩＮＤ−ＩＤ−ＣＣＡ）があるという。
【００５１】
Ｓｅｔｕｐ：チャレンジャは、秘匿性パラメータｋを受け取り、Ｓｅｔｕｐアルゴリズムを実行する。これにより、敵対者は、その結果のシステム・パラメータｐａｒａｍｓが与えられる。このアルゴリズムは、マスターキー（ｍａｓｔｅｒ−ｋｅｙ）をそれ自身に保持する。
【００５２】
段階１：敵対者は、クエリｑ１，．．．，ｑｍを発行するが、クエリｑＩは以下のうちの１つである。
−  抽出クエリ＜ＩＤＩ＞。チャレンジャは、アルゴリズムＥｘｔｒａｃｔを実行し公開鍵＜ＩＤＩ＞に対応する秘密鍵ｄＩを作成することにより応答する。ｄＩを敵対者に送信する。
【００５３】
−解読クエリ＜ＩＤＩ，ＣＩ＞。チャレンジャは、アルゴリズムＥｘｔｒａｃｔを実行しＩＤＩに対応する秘密鍵ｄＩを作成することにより応答する。次に、アルゴリズムＤｅｃｒｙｐｔを実行し、秘密鍵ｄＩを使用して暗号文ＣＩを解読する。これは、その結果の平文を敵対者に送信する。
【００５４】
これらのクエリは状況に応じて行われる、つまり、各クエリｑＩはｑ１，．．．，ｑｉ−１への返信に依存する。
チャレンジ：敵対者は、段階１が終了したと判断すると、長さの等しい２つの平文Ｍ０、Ｍ１∈＄Ｍ、およびチャレンジの際のアイデンティティＩＤを出力する。唯一の制約は、ＩＤが段階１で秘密鍵抽出クエリ内に出現していなかったという点である。
【００５５】
チャレンジャは、ランダム・ビットｂ∈｛０，１｝を選択し、Ｃ＝Ｅｎｃｒｙｐｔ（ｐａｒａｍｓ、ＩＤ，Ｍｂ）を設定する。敵対者へのチャレンジとしてＣを送信する。
段階２：敵対者は、さらにクエリｑｍ＋１，．．．，ｑｎを発行し、クエリｑＩは以下のうちの１つである。
【００５６】
−  抽出クエリ＜ＩＤＩ＞、ただし、ＩＤＩ≠ＩＤ。チャレンジャは、段階１と同じように応答する。
−  解読クエリ＜ＩＤＩ，ＣＩ＞≠＜ＩＤ，Ｃ＞。チャレンジャは、段階１と同じように応答する。
【００５７】
これらのクエリは、段階１のように状況に応じて行うことができる。
推測：最後に、敵対者は推測ｂ'∈｛０，１｝を出力する。ｂ＝ｂ'であれば、敵対者がゲームの勝利者である。
【００５８】
このような敵対者＄ＡをＩＮＤ−ＩＤ−ＣＣＡ敵対者と呼ぶ。方式＄Ｅを攻撃する際の敵対者＄Ａの優位性を秘匿性パラメータｋの以下のような関数として定義する（ｋは、チャレンジャへの入力として与えられる）。
【００５９】
【数１】
0005933786.tif 000003
この確率は、チャレンジャと敵対者によって使用されるランダム・ビット上の確率である。
【００６０】
ＩＮＤ−ＩＤ−ＣＣＡゲームを使用して、ＩＢＥ方式の選択暗号文秘匿性を定義することが可能である。通常のように、関数ｇ：★Ｒ→★Ｒは、ｇ（ｋ）が任意の多項式ｆについて１／ｆ（ｋ）よりも小さい場合に、無視できるという。
【００６１】
定義１  ＩＢＥシステム＄ｅは、任意の多項式時間ＩＮＤ−ＩＤ−ＣＣＡ敵対者＄Ａについて関数Ａｄｖ＄ｅ，＄Ａ（ｋ）が無視できる場合に、適応的選択暗号文攻撃に対する意味秘匿性を有するという。簡単に、＄ｅはＩＮＤ−ＩＤ−ＣＣＡ秘匿性があるという。
【００６２】
ただし、選択暗号文秘匿性（ＩＮＤ−ＣＣＡ）の標準的定義は、秘密鍵抽出クエリがないことを除き上述と同じであり、敵対者はランダム公開鍵（自分の選択した公開鍵ではなく）に基づいてチャレンジを受けることに注意されたい。秘密鍵抽出クエリは、マルチユーザ設定での選択暗号文秘匿性の定義に関係している。結局、この定義は、複数ユーザに属す複数の公開鍵を必要とする。マルチユーザＩＮＤ−ＣＣＡは、標準ハイブリッド引数を使用してシングル・ユーザＩＮＤ−ＣＣＡに簡約可能と考えられる。これは、ＩＤベース設定ＩＮＤ−ＩＤ−ＣＣＡでは成立しないが、それは、敵対者が攻撃中に壊れる公開鍵を選択するようになるからである。秘密鍵抽出クエリが重要であることを強調するために、開示されているＩＢＥシステムの１実装を（ハッシュ関数の１つを除去することにより）修正して、秘密鍵抽出クエリが禁止される場合に選択暗号文秘匿性を有するシステムに導入することが可能であることを指摘しておく。しかし、この実装は、抽出クエリが許される場合には秘匿性がない。
【００６３】
意味秘匿ＩＤベース暗号化。このＩＢＥシステムの実装の秘匿性の証明では、意味（ｓｅｍａｎｔｉｃ）秘匿（選択平文攻撃に対する意味秘匿性とも呼ばれる）と呼ばれる秘匿性の弱い概念を利用する。意味秘匿は、敵対者に対する制限が強いことを除いて選択暗号文秘匿（ＩＮＤ−ＩＤ−ＣＣＡ）に類似しており、チャレンジ公開鍵を攻撃している間は、解読クエリを発行し得ない。標準公開鍵システム（ＩＤベース・システムではなく）では、意味秘匿は、（１）チャレンジャによって作成されたランダム公開鍵を敵対者に与え、（２）敵対者は長さの等しい２つのメッセージＭ０およびＭ１を出力し、｛０，１｝でランダムに選択したｂについてチャレンジャからＭｂの暗号化を受け取り、（３）敵対者はｂ'を出力し、ｂ＝ｂ'であれば敵対者が勝利するというゲームを使用して定義される。公開鍵システムは、多項式時間の敵対者が無視できない優位性でゲームに勝利する可能性がない場合に意味秘匿であるという。簡単に、意味秘匿公開鍵はＩＮＤ−ＣＰＡ秘匿性があるという。意味秘匿性には、暗号文が与えられると、敵対者は対応する平文に関して何も情報を得られないという我々の直観に訴えかけるところがある。
【００６４】
ＩＤベース・システムの意味秘匿（ＩＮＤ−ＩＤ−ＣＰＡと表す）を定義するために、敵対者が選択秘密鍵抽出クエリを発行することを許すことにより、標準定義を強化する。同様に、敵対者は、自分の選択した公開鍵ＩＤに関してチャレンジを受ける。ここで、ＩＮＤ−ＩＤ−ＣＰＡゲームを使用してＩＤベース暗号化方式の意味秘匿を定義する。ゲームは、敵対者は解読クエリを実行し得ないという点を除き上で定義したＩＮＤ−ＩＤ−ＣＣＡゲームと同じである。敵対者は、秘密鍵抽出クエリを実行するしかない。以下のＩＮＤ−ＩＤ−ＣＰＡゲームにおいてチャレンジャに対する無視できない優位性を持つ多項式制限敵対者＄Ａがいない場合、ＩＤベース暗号化方式＄ｅは、意味秘匿性（ＩＮＤ−ＩＤ−ＣＰＡ）があるという。
【００６５】
Ｓｅｔｕｐ：チャレンジャは、秘匿性パラメータｋを受け取り、Ｓｅｔｕｐアルゴリズムを実行する。これにより、敵対者は、その結果のシステム・パラメータｐａｒａｍｓが与えられる。このアルゴリズムは、ｍａｓｔｅｒ−ｋｅｙをそれ自身に留める。
【００６６】
段階１：敵対者は、秘密鍵抽出クエリＩＤ１，．．．，ＩＤｍを発行する。チャレンジャは、アルゴリズムＥｘｔｒａｃｔを実行し公開鍵ＩＤＩに対応する秘密鍵ｄＩを作成することにより応答する。ｄＩを敵対者に送信する。これらのクエリは状況に応じて実行することができる。
【００６７】
チャレンジ：敵対者は、段階１が終了したと判断すると、長さの等しい２つの平文Ｍ０、Ｍ１∈＄Ｍ、およびチャレンジの際の公開鍵ＩＤを出力する。唯一の制約は、ＩＤが段階１で秘密鍵抽出クエリ内に出現していなかったという点である。チャレンジャは、ランダム・ビットｂ∈｛０，１｝を選択し、Ｃ＝Ｅｎｃｒｙｐｔ（ｐａｒａｍｓ、ＩＤ，Ｍｂ）を設定する。敵対者へのチャレンジとしてＣを送信する。
【００６８】
段階２：敵対者は、さらに抽出クエリＩＤｍ＋１，．．．，ＩＤｎを発行する。唯一の制約は、ＩＤｉ≠ＩＤである。チャレンジャは、段階１と同じように応答する。
推測：最後に、敵対者は推測ｂ'∈｛０，１｝を出力する。ｂ＝ｂ'であれば、敵対者がゲームの勝利者である。
【００６９】
このような敵対者＄ＡをＩＮＤ−ＩＤ−ＣＰＡ敵対者と呼ぶ。上で行ったように、方式＄ｅに対するＩＮＤ−ＩＤ−ＣＰＡ敵対者＄Ａの優位性は、秘匿性パラメータｋの以下の関数である。
【００７０】
【数２】
0005933786.tif 000004
この確率は、チャレンジャと敵対者によって使用されるランダム・ビット上の確率である。
【００７１】
定義２  ＩＢＥシステム＄ｅは、任意の多項式時間ＩＮＤ−ＩＤ−ＣＰＡ敵対者＄Ａについて関数Ａｄｖ＄ｅ，＄Ａ（ｋ）が無視できる場合に、意味秘匿であるという。簡単に、＄ｅはＩＮＤ−ＩＤ−ＣＰＡ秘匿性があるという。
【００７２】
一方向ＩＤベース暗号化。一方向暗号化（ＯＷＥ）と呼ばれる秘匿性の更に弱い概念を定義することが可能である。大まかにいうと、公開鍵暗号化方式は、ランダム平文の暗号化が与えられたときに、敵対者がその平文をそのまま出力し得ない場合に一方向暗号化である。敵対者が例えば平文のビットの半分を学習するのを妨げるものがないため、一方向暗号化は秘匿性の弱い概念である。したがって、一方向暗号化方式は、一般的に秘匿性のある暗号化を実現しない。ランダム・オラクル・モデルでは、セッション鍵の暗号化に一方向暗号化方式を使用することが可能である（セッション鍵は、平文のハッシュとみなされる）。秘密鍵抽出クエリを定義に加えることにより一方向暗号化の概念をＩＤベース・システムに拡張することが可能であることを注意しておく。秘匿性の最も弱い概念として意味秘匿を使用するため、ここでは完全な定義を掲載しない。
【００７３】
双線形写像および双線形ＤＩＦＦＩＥ−ＨＥＬＭＡＮ仮定
本発明の一実施形態は、ある大きな素数ｑについて位数ｑの群★Ｇ１と★Ｇ２との間の写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を使用するＩＢＥシステムを対象とする。写像ｅ＾は、以下の特性を満たす場合に認容写像と呼ぶことができる。
【００７４】
１．双線形：写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２は、すべての（Ｐ，Ｑ）∈★Ｇ１×★Ｇ１およびすべてのａ，ｂ∈★Ｚについて、ｅ＾（ａＰ，ｂＱ）＝ｅ＾（Ｐ，Ｑ）ａｂを満たす。
【００７５】
２．非退化：この写像は、★Ｇ１×★Ｇ１内のすべての対を★Ｇ２内の単位要素に対応させない。★Ｇ１、★Ｇ１、★Ｇ２は素数位数の群なので、これは、★Ｇ１＝★Ｇ１およびＰが★Ｇ１＝★Ｇ１の作成要素であれば、ｅ＾（Ｐ，Ｐ）は★Ｇ２の作成要素であることを意味していることがわかる。
【００７６】
３．計算可能：任意の（Ｐ，Ｑ）∈★Ｇ１×★Ｇ１についてｅ＾（Ｐ，Ｑ）を計算する効率のよいアルゴリズムが存在する。
実施形態の多くは、写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を参照して説明されているが、これは、本発明の実施形態で使用されている双線形写像の特定の場合にすぎない。より一般的には、写像ｅ＾：★Ｇ０×★Ｇ１→★Ｇ２を使用することができ、★Ｇ０および★Ｇ１は異なっていてもよい。しかし、説明を簡単にするため、実施形態の多くは、★Ｇ１および★Ｇ１が同じである場合について主に詳述しており、この群は両方とも★Ｇ１で表される。以下では、群★Ｇ１、★Ｇ２およびそれらの間の認容写像を使用する詳細な実施例を取りあげる。この実施例では、群★Ｇ１は、楕円曲線Ｅ／★Ｆｐの点の加法群の部分群であり、群★Ｇ２は、有限体★Ｆ＊■の乗法群の部分群である。以下のＩＢＥシステムの詳細な例からわかるように、Ｗｅｉｌペアリング（それ自体は認容写像でない）を使用して、これら２つの群の間の認容写像を構成することが可能である。
【００７７】
上で述べたように認容写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２が存在することで、これらの群に対し２通りの意味が生じる。
ＭＯＶ帰着：★Ｇ１における離散対数問題は★Ｇ２における離散対数問題よりも困難ではない。これを見るために、Ｐ，Ｑ∈★Ｇ１を★Ｇ１における離散対数問題の実例とし、Ｐ、Ｑは両方とも位数ｑであるとする。Ｑ＝αＰとなるようなα∈★Ｚｑを見つけたい。ｇ＝ｅ＾（Ｐ，Ｐ）およびｈ＝ｅ＾（Ｑ，Ｐ）とする。そこで、ｅ＾の双線形性により、ｈ＝ｇαであることがわかる。ｅ＾が非退化であることから、ｇ、ｈは両方とも★Ｇ２において位数ｑである。したがって、★Ｇ１における離散対数問題は、★Ｇ２における離散対数問題に帰着した。よって、離散対数が★Ｇ１において困難であるためには、離散対数が★Ｇ２において困難であるように秘匿性パラメータを選択しなければならない。
【００７８】
決定Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎは容易である：★Ｇ１における決定Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（ＤＤＨ）は、分布＜Ｐ，ａＰ，ｂＰ，ａｂＰ＞と＜Ｐ，ａＰ，ｂＰ，ｃＰ＞とを区別する問題であり、ａ、ｂ、ｃは★Ｚｑにおいてランダムであり、Ｐは★Ｇ１においてランダムである。★Ｇ１におけるＤＤＨが容易であることを見るために、Ｐ、ａＰ、ｂＰ、ｃＰ∈★Ｇ＊１が与えられた場合、以下の式が成り立つことに注意する。
【００７９】
ｃ＝ａｂ  ｍｏｄ  ｑ  ＜＝＝＞  ｅ＾（Ｐ，ｃＰ）＝ｅ＾（ａＰ，ｂＰ）
★Ｇ１における計算Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（ＣＤＨ）は、それでも、困難である可能性がある（★Ｇ１におけるＣＤＨはランダムな＜Ｐ，ａＰ，ｂＰ＞が与えられた場合にａｂＰを見つけることである）。実施例では、★Ｇ１におけるＤＤＨが容易であるとしても★Ｇ１におけるＣＤＨは困難であると考えられる場合に、写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を使用することができる。
【００８０】
双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定（ＢＤＨ）
★Ｇ１における決定Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（ＤＤＨ）は容易なので、本発明の実施形態ではその群で暗号システムを構築するのにＤＤＨを使用しない。その代わりに、このＩＢＥシステムの実施形態の秘匿性は、双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定（ＢＤＨ）と呼ばれる計算Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定の新規性のある変種に基づく。
【００８１】
双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題。★Ｇ１、★Ｇ２を素数位数ｑの２つの群とする。ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を認容写像とし、Ｐを★Ｇ１の作成要素とする。＜★Ｇ１，★Ｇ２，ｅ＾＞のＢＤＨ問題は以下のとおりである。あるａ、ｂ、ｃ∈★Ｚ＊ｑについて＜Ｐ，ａＰ，ｂＰ，ｃＰ＞が与えられたとして、Ｗ＝ｅ＾（Ｐ，Ｐ）ａｂｃ∈★Ｇ２を計算する。アルゴリズム＄Ａには、以下の場合に、＜★Ｇ１，★Ｇ２，ｅ＾＞におけるＢＤＨを解く上で優位性＄ｅがある。
【００８２】
Ｐｒ［＄Ａ（Ｐ，ａＰ，ｂＰ，ｃＰ）＝ｅ＾（Ｐ，Ｐ）ａｂｃ］≧ε
ただし、この確率は★Ｚ＊ｑにおけるａ，ｂ，ｃのランダムな選択、Ｐ∈★Ｇ＊１のランダムな選択、および＄Ａのランダム・ビットについてのものである。
【００８３】
ＢＤＨパラメータ作成要素。ランダム・アルゴリズム＄ｇは、（１）＄ｇが秘匿性パラメータｋ∈★Ｚ＋を受け取り、（２）＄ｇがｋの多項式時間で実行され、（３）＄ｇは素数ｑ、位数ｑの２つの群★Ｇ１、★Ｇ２の説明および許容写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２の説明を出力する場合に、ＢＤＨパラメータ作成要素であるという。＄ｇの出力を＄ｇ（１ｋ）＝＜ｑ，★Ｇ１，★Ｇ２，ｅ＾＞で表す。秘匿性パラメータｋは、ｑのサイズを決定する場合に使用され、例えば、ｑをランダムなｋビット素数とみなすことも可能である。ｉ＝１，２について、群★ＧＩの説明に、★ＧＩにおける群作用を計算するための多項式時間（ｋにおける）アルゴリズムが含まれる、★ＧＩの作成要素が含まれると仮定する。★ＧＩの作成要素により、★ＧＩに一様にランダムな要素を作成することができる。同様に、ｅ＾の説明に、ｅ＾を計算するための多項式時間アルゴリズムが含まれると仮定する。Ｗｅｉｌペアリングを使用するＩＢＥシステムの以下の詳細な例では、ＢＤＨパラメータ作成要素の例を挙げる。
【００８４】
双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定。＄ｇをＢＤＨパラメータ作成要素とする。
アルゴリズム＄Ａは、十分に大きなｋについて以下の式が成り立つ場合に、ＢＤＨ問題を解く際に優位性ε（ｋ）を有するという。
【００８５】
【数３】
0005933786.tif 000005
任意のランダム多項式時間（ｋにおいて）アルゴリズムおよび任意の多項式ｆ∈★Ｚ［ｘ］アルゴリズムについて＄Ａは高々１／ｆ（ｋ）の優位性でＢＤＨ問題を解く場合に、＄ｇはＢＤＨ仮定を満たすという。＄ｇがＢＤＨ仮定を満たす場合、ＢＤＨは、＄ｇによって作成された群において困難であるという。
【００８６】
ＩＢＥシステムの以下の詳細な例の説明では、ＢＤＨ仮定を満たすと思われるＢＤＨパラメータ作成要素の例をいくつか挙げる。
ＢＤＨの困難さ。ＢＤＨ問題と暗号で使用される他の困難な問題との関係を調べると興味深いことがわかる。現在、いえるのは、＜★Ｇ１，★Ｇ２，ｅ＾＞のＢＤＨ問題は★Ｇ１または★Ｇ２におけるＣＤＨ問題よりも困難ではないということである。つまり、★Ｇ１または★Ｇ２のＣＤＨのアルゴリズムは＜★Ｇ１，★Ｇ２，ｅ＾＞のＢＤＨを解くのに十分であるということである。今のところ、この逆、つまり、★Ｇ１または★Ｇ２でＣＤＨを解くのにＢＤＨのアルゴリズムは十分かという問題は未解決である。
【００８７】
以下のＩＢＥシステムの詳細な例では、認容写像によって誘導された★Ｇ１から★Ｇ２への同型写像は、一方向関数であると考えられることを注意しておく。より具体的には、点Ｑ∈★Ｇ＊１について、ｆｑ（Ｐ）＝ｅ＾（Ｐ，Ｑ）により同型写像ｆｑ：★Ｇ１→★Ｇ２を定義する。これらの同型写像のどれか１つでも不可逆であることは判明すれば、ＢＤＨは＜★Ｇ１，★Ｇ２，ｅ＾＞において容易である。幸運なことに、ｆｑの逆を求める効率のよいアルゴリズムがあれば、群★Ｇ２においてＤＤＨを決定する効率のよいアルゴリズムがあることがいえる。実施例では、ＤＤＨは群★Ｇ２において困難であると考えられる。したがって、認容写像によって誘導された同型写像ｆｑ：★Ｇ１→★Ｇ２は一方向関数であると考えられる。
【００８８】
ＩＤベース暗号化方式の例
以下の実施例について段階を追って説明する。まず、適応的選択暗号文攻撃に対して秘匿性がない基本的なＩＤベース暗号化システムと方法について説明する。後述の他の実施形態では、基本的な方式を拡張し、ランダム・オラクル・モデルにおいて適応的選択暗号文攻撃に対する秘匿性（ＩＮＤ−ＩＤ−ＣＣＡ）を有するようにする。後で、ハッシュ関数に対する要求条件を一部弱めて、他の実施形態を提示する。これらの実施形態については、ＢＤＨ仮定を満たすジェネリックなＢＤＨパラメータ作成要素を参照して説明する。後で、Ｗｅｉｌペアリングを使用するＩＢＥシステムの詳細な例を説明する。
【００８９】
ＢａｓｉｃＩｄｅｎｔ
ここでは、ＢａｓｉｃＩｄｅｎｔと呼ばれる基本的な実施形態について説明する。実施形態の説明では、Ｓｅｔｕｐ、Ｅｘｔｒａｃｔ、Ｅｎｃｒｙｐｔ、Ｄｅｃｒｙｐｔという４つのアルゴリズムを取りあげる。ｋをセットアップ・アルゴリズムに与えられる秘匿性パラメータとする。＄ｇをあるＢＤＨパラメータ作成要素とする。
【００９０】
Ｓｅｔｕｐ：秘匿性パラメータｋ∈★Ｚ＋が与えられると、基本的な実施形態のアルゴリズムは以下のようになる。
工程１：入力ｋに対して＄ｇを実行し、素数ｑ、位数ｑの２つの群★Ｇ１、★Ｇ２、および認容写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を作成する。任意の作成要素Ｐ∈★Ｇ１を選択する。
【００９１】
工程２：ランダムなｓ∈★Ｚ＊ｑを選び、Ｐｐｕｂ＝ｓＰと設定する。
工程３：暗号ハッシュ関数Ｈ１：｛０，１｝＊→★Ｇ＊１を選択する。あるｎについて、暗号ハッシュ関数Ｈ２：★Ｇ＊２→｛０，１｝ｎを選択する。秘匿性解析により、Ｈ１、Ｈ２はランダム・オラクルとみなされる。
【００９２】
メッセージ空間は、＄Ｍ＝｛０，１｝ｎである。暗号文空間は、＄Ｃ＝★Ｇ＊１×｛０，１｝ｎである。システム・パラメータは、ｐａｒａｍｓ＝＜ｑ，★Ｇ１，★Ｇ２，ｅ＾，ｎ，Ｐ，Ｐｐｕｂ，Ｈ１，Ｈ２＞である。ｍａｓｔｅｒ−ｋｅｙは、ｓ∈★Ｚ＊ｑである。
【００９３】
ＩＢＥシステムの実施形態を使用して、対称鍵を暗号化できるが、その場合、ｎを、例えば、１２８または２５６とすることができる。ｋについては、例えば、５１２または１０２４または２０４８を使用できる。
【００９４】
Ｅｘｔｒａｃｔ：与えられた２進数列ＩＤ∈｛０，１｝＊について、基本的な実施形態のアルゴリズムは、（１）ＱＩＤ＝Ｈ１（ＩＤ）∈★Ｇ＊１を計算し、（２）ｓをマスター鍵として、秘密鍵ｄＩＤをｄＩＤ＝ｓＱＩＤとなるように設定する。
【００９５】
Ｅｘｔｒａｃｔは、図２に示されているように、さまざまな実施形態におけるＰＫＧにより実行することができる。ＰＫＧは、ブロック２００でマスター鍵を取得し、ブロック２１０で公開識別子ＩＤを取得し、ブロック２２０でＩＤから公開鍵を計算し、ブロック２３０でマスター鍵と公開鍵から秘密鍵を計算する。ブロック２４０で、秘密鍵が、公開識別子ＩＤに関連付けられているエンティティに送られるが、これは通常、エンティティの素性が識別された後に行われる。
【００９６】
Ｅｎｃｒｙｐｔ：公開鍵ＩＤのもとでＭ∈＄Ｍを暗号化するために、（１）ＱＩＤ＝Ｈ１（ＩＤ）∈★Ｇ＊１を計算し、（２）ランダムなｒ∈★Ｚ＊ｑを選択し、（３）暗号文を以下のように設定する。
【００９７】
Ｃ＝＜ｒＰ，Ｍ○＋Ｈ２（ｇｒＩＤ）＞  ただし、ｇＩＤ＝ｅ＾（ＱＩＤ，Ｐｐｕｂ）∈★Ｇ＊２
基本的な実施形態では、メッセージの送信者は図３に示されているようにＥｎｃｒｙｐｔを実行することができる。ブロック３００で、システム・パラメータが取得される（ＰＫＧなどの外部リソース、またはすでに取得されていればローカルの記憶媒体から）。ブロック３１０で、受信者のＩＤが決定され、ブロック３２０で、対応する公開鍵がＩＤから計算される。その後、ブロック３３０で、秘密メッセージ鍵が計算され、ブロック３４０で、メッセージ鍵を使用して、メッセージが暗号化される。
【００９８】
Ｄｅｃｒｙｐｔ：Ｃ＝＜Ｕ，Ｖ＞∈＄Ｃを、公開鍵ＩＤを使用して暗号化された暗号文であるとする。秘密鍵ｄＩＤ∈★Ｇ＊１を使用してＣを暗号化するために、以下を計算する。
【００９９】
Ｖ○＋Ｈ２（ｅ＾（ｄＩＤ，Ｕ））＝Ｍ
基本的な実施形態では、受信者は、図４に示されているようにＤｅｃｒｙｐｔを実行することができる。ブロック４００で、システム・パラメータが取得される（ＰＫＧなどの外部リソース、またはすでに取得されていればローカルの記憶媒体から）。ブロック４１０で、送信者から暗号文Ｖおよび要素ｒＰを取得する。要素ｒＰは、送信者から得られた暗号文全体の一部と考えることができる。ブロック４２０で、受信者は、メッセージを暗号化するために使用された公開識別子ＩＤに対応する秘密鍵ｄＩＤを取得する。秘密鍵は、通常、ＰＫＧなどの外部リソース、またはすでに取得されていればローカルの記憶媒体から取得される。その後、ブロック４３０で、秘密メッセージ鍵が計算され、ブロック４４０で、これを使用して、メッセージが解読される。
【０１００】
これで、基本的な実施形態のＢａｓｉｃＩｄｅｎｔの説明は完了する。最初に整合性を確認する。すべてが上のように計算されると、
１．暗号化時に、ＭとｇｒＩＤのハッシュとのビット排他ＯＲが計算される。
【０１０１】
２．解読時に、Ｖとｅ＾（ｄＩＤ，Ｕ）のハッシュとのビット排他ＯＲが計算される。暗号化および解読時に使用されるこれらのマスクは、以下の式が成り立つため同じである。
【０１０２】
ｅ＾（ｄＩＤ，Ｕ）＝ｅ＾（ｓＱＩＤ，ｒＰ）＝ｅ＾（ＱＩＤ，Ｐ）ｓｒ＝ｅ＾（ＱＩＤ，Ｐｐｕｂ）ｒ＝ｇｒＩＤ
したがって、暗号化の後に解読を適用すると、必要に応じてオリジナルのメッセージＭが出力される。ＢａｓｉｃＩｄｅｎｔの性能上の考慮事項については後述する。
【０１０３】
秘匿性。次に、この基本的な実施形態の秘匿性について調べる。
システムの例の秘匿性は、★Ｇ１における計算Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題の一変種が困難であるという仮定に基づいている。暗号化方式の秘匿性の技術面の詳細については、発明者が（非特許文献２）で解説しており、本願明細書に援用する。
【０１０４】
実施例では、システムの性能は★Ｆ＊ｐにおけるＥｌＧａｍａｌ暗号化の性能に匹敵している。システムの例の秘匿性は、計算Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定の一変種に基づいている。この仮定に基づき、システム例がランダム・オラクル・モデルにおいて選択暗号文秘匿性を有することを示す。分散ＰＫＧ実施形態によれば、閾値暗号化手法を使用することで、ＰＫＧを分散させ、ｍａｓｔｅｒ−ｋｅｙを１カ所だけで利用することをできなくすることが可能である。普通の閾値システムとは異なり、分散ＰＫＧ実施形態の堅牢性は免除されることを示す。
【０１０５】
システム例の秘匿性について論じるため、ＩＤベース暗号化の選択暗号文秘匿性を定義する。このモデルでは、敵対者に、選択暗号文秘匿性の標準モデルよりも大きな権限を与える。最初に、攻撃者が自分の選択した任意の公開鍵ＩＤを攻撃することを許す。次に、ＩＤに対し選択暗号文攻撃がしかけられている間に、攻撃者がＩＤの秘密鍵以外の、自分の選択した公開鍵をＰＫＧから取得することを許す。これにより、自分の選択したいくつかのＩＤに対応する複数の秘密鍵を取得し、自分の選択した他の何らかの公開鍵ＩＤを攻撃しようとする攻撃者のモデルが作成される。このようなクエリの手助けがあっても、システムの意味秘匿を破るという点での攻撃者の優位性がいぜんとして無視できるくらい小さいことが望ましい。
【０１０６】
以下の定理では、ＢＤＨが＄ｇによって作成される群において困難であると仮定して、ＢａｓｉｃＩｄｅｎｔが意味秘匿ＩＤベース暗号化方式（ＩＮＤ−ＩＤ−ＣＰＡ）であることを証明する。
【０１０７】
定理１  ハッシュ関数Ｈ１、Ｈ２はランダム・オラクルであると仮定する。そこで、ＢＤＨが＄ｇによって作成される群において困難であると仮定すると、ＢａｓｉｃＩｄｅｎｔは意味秘匿ＩＤベース暗号化方式（ＩＮＤ−ＩＤ−ＣＰＡ）である。具体的には、方式ＢａｓｉｃＩｄｅｎｔに対し優位性得ε（ｋ）を有するＩＮＤ−ＩＤ−ＣＰＡ敵対者＄Ａが存在すると仮定する。また、＄Ａが高々ｑＥ＞０個の秘密鍵抽出クエリとＨ２へのｑＨ２＞０個のハッシュ・クエリを作成すると仮定する。すると、少なくとも以下の優位性を持つ＄ｇによって作成された群においてＢＤＨを解くアルゴリズム＄Ｂが存在する。
【０１０８】
【数４】
0005933786.tif 000006
ここで、ｅ〜〜２．７１は自然対数の底である。＄Ｂの実行時間のオーダーはＯ（ｔｉｍｅ（＄Ａ））である。
【０１０９】
この定理を証明するために、まずＢａｓｉｃＰｕｂと呼ばれる関連する公開鍵暗号化方式（ＩＤベース方式ではなく）を定義する。ＢａｓｉｃＰｕｂは、ｋｅｙｇｅｎ、ｅｎｃｒｙｐｔ、ｄｅｃｒｙｐｔの３つのアルゴリズムにより記述される。
【０１１０】
ｋｅｙｇｅｎ：秘匿性パラメータｋ∈★Ｚ＋が与えられると、このアルゴリズムは以下のように実行される。
工程１：入力ｋに対して＄ｇを実行し、２つの素数位数の群★Ｇ１、★Ｇ２、および認容写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を作成する。ｑを★Ｇ１、★Ｇ２の位数とする。任意の作成要素Ｐ∈★Ｇ１を選択する。
【０１１１】
工程２：ランダムなｓ∈★Ｚ＊ｑを選び、Ｐｐｕｂ＝ｓＰと設定する。ランダムなＱＩＤ∈★Ｇ＊１を選ぶ。
工程３：あるｎについて、暗号ハッシュ関数Ｈ２：★Ｇ２→｛０，１｝ｎを選択する。
【０１１２】
工程４：公開鍵は、＜ｑ，★Ｇ１，★Ｇ２，ｅ＾，ｎ，Ｐ，Ｐｐｕｂ，Ｈ１，Ｈ２＞である。秘密鍵はｄＩＤ＝ｓＱＩＤ∈★Ｇ＊１である。
ｅｎｃｒｙｐｔ：Ｍ∈｛０，１｝ｎを暗号化するために、ランダムなｒ∈★Ｚ＊ｑを選択し、暗号文を以下のように設定する。
【０１１３】
Ｃ＝＜ｒＰ，Ｍ○＋Ｈ２（ｇｒ）＞  ただし、ｇ＝ｅ＾（ＱＩＤ，Ｐｐｕｂ）∈★Ｇ＊２
ｄｅｃｒｙｐｔ：Ｃ＝＜Ｕ，Ｖ＞を、公開鍵＜ｑ，★Ｇ１，★Ｇ２，ｅ＾，ｎ，Ｐ，Ｐｐｕｂ，を使用して作成された暗号文であるとする。秘密鍵ｄＩＤ∈★Ｇ＊１を使用してＣを解読するために、以下を計算する。
【０１１４】
Ｖ○＋Ｈ２（ｅ＾（ｄＩＤ，Ｕ））＝Ｍ
これで、ＢａｓｉｃＰｕｂの説明は完了である。そこで、定理１を２段階で証明する。まず、ＢａｓｉｃＩｄｅｎｔに対するＩＮＤ−ＩＤ−ＣＰＡ攻撃はＢａｓｉｃＰｕｂに対するＩＮＤ−ＣＰＡ攻撃に変換することが可能であることを示す。この段階で、秘密鍵抽出クエリが敵対者を手助けしないことを示す。次に、ＢＤＨ仮定が成立する場合に、ＢａｓｉｃＰｕｂがＩＮＤ−ＣＰＡ秘匿性を有することを示す。これらの証明は略す。
【０１１５】
補助定理２  Ｈ１を｛０，１｝＊から★Ｇ＊１へのランダム・オラクルとする。＄ＡをＢａｓｉｃＩｄｅｎｔに対し優位性得ε（ｋ）を有するＩＮＤ−ＩＤ−ＣＰＡ敵対者とする。＄Ａは高々ｑＥ＞０個の秘密鍵抽出クエリを作成すると仮定する。すると、ＢａｓｉｃＰｕｂに対して少なくともε（ｋ）／ｅ（１＋ｑＥ）の優位性を持つＩＮＤ−ＣＰＡ敵対者＄Ｂが存在する。この実行時間のオーダーはＯ（ｔｉｍｅ（＄Ａ））である。
【０１１６】
補助定理３  Ｈ２を★Ｇ＊２から｛０，１｝ｎへのランダム・オラクルとする。＄ＡをＢａｓｉｃＰｕｂに対し優位性得ε（ｋ）を有するＩＮＤ−ＣＰＡ敵対者とする。＄ＡはＨ２に対して合計ｑＨ２＞０個のクエリを作成する。すると、少なくとも２ε（ｋ）／ｑＨ２の優位性を有する＄ｇに対するＢＤＨ問題を解くアルゴリズム＄Ｂが存在し、実行時間のオーダーはＯ（ｔｉｍｅ（Ａ））である。
【０１１７】
定理１の証明。この定理は、直接補助定理３および補助定理３から導かれる。両方の帰結を書くと、優位性ε（ｋ）を有するＢａｓｉｃＩｄｅｎｔに対するＩＮＤ−ＩＤ−ＣＰＡ敵対者は、必要に応じて、少なくとも２ε（ｋ）／ｅ（１＋ｑＥ）ｑＨ２の優位性を持つ＄ｇに対するＢＤＨアルゴリズムを与えることが示される。
【０１１８】
選択暗号文秘匿性のあるＩＤベース暗号化
本発明の一実施形態によれば、ＦｕｊｉｓａｋｉおよびＯｋａｍｏｔｏの手法（本願明細書に援用する（非特許文献３）を参照）を適宜適合させ、前節のＢａｓｉｃＩｄｅｎｔ実施形態をランダム・オラクル・モデルにおけるＩＢＥシステム（前で定義した意味において）の選択暗号文秘匿性実施形態に転換することができる。＄ｅを確率論的公開的暗号方式とする。公開鍵ｐｋのもとでランダム・ビットｒを使用するＭの暗号化を＄ｅｐｋ（Ｍ；ｒ）で表す。Ｆｕｊｉｓａｋｉ−Ｏｋａｍｏｔｏは、ハイブリッド方式を以下のように定義する。
【０１１９】
＄ｅｈｙｐｋ（Ｍ）＝＜＄ｅｐｋ（σ；Ｈ３（σ，Ｍ）），Ｈ４（σ）○＋Ｍ＞
ここで、σはランダムに作成され、Ｈ３、Ｈ４は暗号ハッシュ関数である。Ｆｕｊｉｓａｋｉ−Ｏｋａｍｏｔｏは、＄ｅが一方向暗号化方式であれば、＄ｅｈｙはランダム・オラクル・モデルにおいて選択暗号秘匿性システム（ＩＮＤ−ＣＣＡ）であることを示している（＄ｅｐｋがいくつかの自然な制約を満たしていると仮定して）。ここで、意味秘匿は一方向暗号化を意味し、したがって、＄ｅが意味秘匿（ＩＮＤ−ＣＰＡ）であれば、Ｆｕｊｉｓａｋｉ−Ｏｋａｍｏｔｏの結果も適用されることを注意する。
【０１２０】
Ｆｕｊｉｓａｋｉ−Ｏｋａｍｏｔｏ変換をＢａｓｉｃＩｄｅｎｔに適用し、ＩＢＥシステムのその結果の実施形態がＩＮＤ−ＩＤ−ＣＣＡ秘匿性を有することを示す。ＦｕｌｌＩｄｅｎｔという以下のＩＢＥ実施形態を得る。ただし、ｎは暗号化するメッセージの長さであることに留意されたい。
【０１２１】
Ｓｅｔｕｐ：ＢａｓｉｃＩｄｅｎｔ方式の場合と同様。さらに、ハッシュ関数Ｈ３：｛０，１｝ｎ×｛０，１｝ｎ→★Ｚ＊ｑおよびハッシュ関数Ｈ４：｛０，１｝ｎ→｛０，１｝ｎを選ぶ。
【０１２２】
Ｅｘｔｒａｃｔ：ＢａｓｉｃＩｄｅｎｔ方式の場合と同様。
Ｅｎｃｒｙｐｔ：公開鍵ＩＤのもとでＭ∈｛０，１｝ｎを暗号化するために、（１）ＱＩＤ＝Ｈ１（ＩＤ）∈★Ｇ＊１を計算し、（２）ランダムなσ∈｛０，１｝ｎを選択し、（３）ｒ＝Ｈ３（σ，Ｍ）と設定し、（４）暗号文を以下のように設定する。
【０１２３】
Ｃ＝＜ｒＰ，σ○＋Ｈ２（ｇｒＩＤ），Ｍ○＋Ｈ４（σ）＞  ただし、ｇＩＤ＝ｅ＾（ＱＩＤ，Ｐｐｕｂ）∈★Ｇ２
Ｄｅｃｒｙｐｔ：Ｃ＝＜Ｕ，Ｖ、Ｗ＞を、公開鍵ＩＤを使用して暗号化された暗号文であるとする。Ｕ∈／★Ｇ＊１であればその暗号文を却下する。秘密鍵ｄＩＤ∈★Ｇ＊１を使用してＣを暗号化するために、以下を実行する。
【０１２４】
１．Ｖ○＋Ｈ２（ｅ＾（ｄＩＤ，Ｕ））＝σを計算する。
２．Ｗ○＋Ｈ４（σ））＝Ｍを計算する。
３．ｒ＝Ｈ３（σ，Ｍ）と設定する。Ｕ＝ｒＰであることを検査する。そうでなければ、その暗号文を却下する。
【０１２５】
４．ＭをＣの解読として出力する。
これで、ＦｕｌｌＩｎｄｅｎｔの説明は完了である。この実装は、図２、３、４に示されているＢａｓｉｃＩｄｅｎｔと同じ基本パターンに従う。Ｍは、Ｗ＝Ｍ○＋Ｈ４（σ）として暗号化されることに注意されたい。これは、Ｗ＝ＥＨ４（σ）（Ｍ）で置き換えられるが、ただし、Ｅは意味秘匿対称暗号化方式である。
【０１２６】
秘匿性。以下の定理では、ＢＤＨは＄ｇによって作成される群において困難であると仮定して、ＦｕｌｌＩｎｄｅｎｔは選択暗号文秘匿性のあるＩＢＥ（つまり、ＩＮＤ−ＩＤ−ＣＣＡ）であることを証明する。
【０１２７】
定理４  ハッシュ関数Ｈ１、Ｈ２、Ｈ３、Ｈ４はランダム・オラクルであるとする。すると、ＢＤＨが＄ｇによって作成される群において困難であると仮定すると、ＦｕｌｌＩｄｅｎｔは選択暗号文秘匿ＩＢＥ（ＩＮＤ−ＩＤ−ＣＣＡ）である。
【０１２８】
具体的には、方式ＦｕｌｌＩｄｅｎｔに対し優位性得ε（ｋ）を有するＩＮＤ−ＩＤ−ＣＣＡ敵対者＄Ａが存在すると仮定すると、＄Ａは高々ｔ（ｋ）の時間で実行される。また、＄Ａは高々ｑＥ個の抽出クエリ、高々ｑＤ個の解読クエリ、および高々ｑＨ２、ｑＨ３、ｑＨ４個のクエリをハッシュ関数Ｈ２、Ｈ３、Ｈ４に対してそれぞれ作成すると仮定する。すると、以下のような、実行時間がｔ１（ｋ）である＄ｇに対するＢＤＨアルゴリズム＄Ｂが存在する。
【０１２９】
【数５】
0005933786.tif 000007
ただし、関数ＦＯｔｉｍｅおよびＦＯａｄｖは、定理５で定義されている。
定理４の証明は、ＦｕｊｉｓａｋｉとＯｋａｍｏｔｏの以下の結果に基づいている。ＢａｓｉｃＰｕｂｈｙは、Ｆｕｊｉｓａｋｉ−Ｏｋａｍｏｔｏ変換をＢａｓｉｃＰｕｂに適用した結果とする。
【０１３０】
定理５（Ｆｕｊｉｓａｋｉ−Ｏｋａｍｏｔｏ）  ＄Ａは、ＢａｓｉｃＰｕｂｈｙを攻撃したときに優位性ε（ｋ）を得るＩＮＤ−ＣＣＡ敵対者であるものとする。＄Ａは実行時間ｔ（ｋ）が設定され、高々ｑＤ個の解読クエリを作成し、および高々ｑＨ３、ｑＨ４個のクエリをハッシュ関数Ｈ３、Ｈ４に対して作成すると仮定する。すると、以下が成り立てば、実行時間ｔ１（ｋ）、優位性ε１（ｋ）のＢａｓｉｃＰｕｂに対するＩＮＤ−ＣＰＡ敵対者＄Ｂが存在する。
【０１３１】
【数６】
0005933786.tif 000008
ここで、ｑは、群★Ｇ１、★Ｇ２のサイズであり、ｎはσの長さである。
実際には、Ｆｕｊｉｓａｋｉ−Ｏｋａｍｏｔｏは次のさらに強い結果を証明している。定理４の仮説のもとでは、ＢａｓｉｃＰｕｂｈｙは一方向暗号化方式ですらない。本発明の目的に関しては、定理５の結果で十分である。定理４を証明するために、さらに、ＦｕｌｌＩｄｅｎｔに対するＩＮＤ−ＩＤ−ＣＣＡ選択暗号文攻撃とＢａｓｉｃＰｕｂｈｙに対するＩＮＤ−ＣＣＡ選択暗号文攻撃との間の変換に以下の補助定理が必要である。
【０１３２】
補助定理６  ＄ＡをＦｕｌｌＩｄｅｎｔに対し優位性得ε（ｋ）を有するＩＮＤ−ＩＤ−ＣＣＡ敵対者とする。また、＄Ａが高々ｑＥ＞０個の秘密鍵抽出クエリとｑＤ＞０個の解読クエリを作成すると仮定する。すると、ＢａｓｉｃＰｕｂｈｙに対し少なくとも
【０１３３】
【数７】
0005933786.tif 000009
の優位性得を有するＩＮＤ−ＣＣＡ敵対者が存在する。この実行時間のオーダーはＯ（ｔｉｍｅ（＄Ａ））である。
【０１３４】
定理４の証明。補助定理６により、ＦｕｌｌＩｄｅｎｔに対するＩＮＤ−ＩＤ−ＣＣＡ敵対者ならば、ＢａｓｉｃＰｕｂｈｙに対するＩＮＤ−ＣＣＡ敵対者である。定理５から、ＢａｓｉｃＰｕｂｈｙに対するＩＮＤ−ＣＣＡ敵対者ならば、ＢａｓｉｃＰｕｂに対するＩＮＤ−ＣＰＡ敵対者である。補助定理３から、ＢａｓｉｃＰｕｂに対するＩＮＤ−ＣＰＡ敵対者ならば、ＢＤＨのアルゴリズムである。よって、必要条件が得られた。
【０１３５】
ハッシングの要求条件の緩和
前節のＩＢＥシステムは、ハッシュ関数Ｈ１：｛０，１｝＊→★Ｇ＊１を使用していることに留意されたい。次節で述べるＩＢＥシステムの詳細な例では、★Ｇ１を楕円曲線上の点のなす群の部分群として使用する。実際、このような群に直接ハッシュするハッシュ関数を構築することが困難な場合がある。１実施例では、したがって、★Ｇ＊１の上へのハッシュの要求条件を緩和する方法を示す。★Ｇ＊１の上へのハッシュではなく、ある集合Ａ⊆｛０，１｝＊の上へのハッシュを行い、決定論的符号化関数を使用してＡを★Ｇ＊１に写像する。
【０１３６】
認容符号化：★Ｇ１を群とし、Ａ∈｛０，１｝＊を有限集合とする。符号化関数Ｌ：Ａ→★Ｇ＊１が以下の特性を満たす場合、この符号化関数は認容的であるという。
１．計算可能：任意のｘ∈Ａに対しＬ（ｘ）を計算する効率のよい決定論的アルゴリズムが存在する。
【０１３７】
２．＄ｌ対１：任意のｙ∈★Ｇ＊１について、Ｌのもとでのｙのプリイメージのサイズはちょうど＄ｌである。つまり、すべてのｙ∈★Ｇ＊１について｜Ｌ−１（ｙ）｜＝＄ｌが成り立つ。これが成り立てば、｜Ａ｜＝＄ｌ・｜★Ｇ＊１｜であることに注意されたい。
【０１３８】
３．サンプリング可能：＄Ｌ（ｓ）から任意のｙ∈★Ｇ＊１に対するＬ−１（ｙ）上の一様分布が得られるような効率のよいランダム・アルゴリズム＄ＬＳが存在する。つまり、＄Ｌ（ｓ）はＬ−１（ｙ）の一様ランダム要素である。
【０１３９】
ＦｕｌｌＩｄｅｎｔを修正し、Ｈ１をある集合Ａの中へのハッシュ関数で置き換えたＩＢＥシステムのＩＮＤ−ＩＤ−ＣＣＡ秘匿実施形態を得る。変更は比較的小さいため、この新しい方式をＦｕｌｌＩｄｅｎｔ'と呼ぶ。
【０１４０】
Ｓｅｔｕｐ：ＦｕｌｌＩｄｅｎｔ方式の場合と同様。唯一の違いは、Ｈ１がハッシュ関数Ｈ'１：｛０，１｝＊→Ａで置き換えられていることである。システム・パラメータはさらに、認容的符号化関数Ｌ：Ａ→★Ｇ＊１の記述も含む。
【０１４１】
Ｅｘｔｒａｃｔ，Ｅｎｃｒｙｐｔ：ＦｕｌｌＩｄｅｎｔ方式の場合と同様。唯一の違いは、工程１では、これらのアルゴリズムはＱＩＤ＝Ｌ（Ｈ'１（ＩＤ））∈★Ｇ＊１を計算する点である。
【０１４２】
Ｄｅｃｒｙｐｔ：ＦｕｌｌＩｄｅｎｔ方式の場合と同様。
これで、ＦｕｌｌＩｎｄｅｎｔ'説明は完了である。以下の定理では、ＦｕｌｌＩｄｅｎｔを仮定して、ＦｕｌｌＩｎｄｅｎｔ'は選択暗号文秘匿性のあるＩＢＥ（つまり、ＩＮＤ−ＩＤ−ＣＣＡ）であることを証明する。
【０１４３】
定理７  ＄Ａを優位性得ε（ｋ）を満たすＦｕｌｌＩｄｅｎｔ'に対するＩＮＤ−ＩＤ−ＣＣＡ敵対者とする。＄Ａは、ハッシュ関数Ｈ'１への高々ｑＨ１個のクエリを作成するとする。そこで、同じ優位性ε（ｋ）が得られ、ｔｉｍｅ（＄Ｂ）＝ｔｉｍｅ（＄Ａ）＋ｑＨ１・ｔｉｍｅ（ＬＳ）となるＦｕｌｌＩｄｅｎｔに対するＩＮＤ−ＩＤ−ＣＣＡ敵対者＄Ｂが存在する。
【０１４４】
証明の概略  アルゴリズム＄Ｂはアルゴリズム＄Ａを実行することによりＦｕｌｌＩｄｅｎｔを攻撃する。これは、すべての解読クエリ、抽出クエリ、およびハッシュ・クエリを直接＄Ａからチャレンジャに中継し、チャレンジャの応答を＄Ａに中継して戻す。これは、＄Ａがハッシュ・クエリをＨ'１に発行した場合にのみ異なる挙動を示す。ただし、＄Ｂは、ハッシュ関数Ｈ１：｛０，１｝＊→★Ｇ＊１にのみアクセスできることに留意されたい。Ｈ'１クエリに応答するため、後述のように、アルゴリズム＄Ｂはタプル＜ＩＤｊ，ｙｊ＞のリストを保持する。このリストを（Ｈ'１）ｌｉｓｔと呼ぶ。このリストは、最初は空である。＄Ａが点ＩＤＩでオラクルＨ'１にクエリを実行すると、アルゴリズム＄Ｂは以下のように応答する。
【０１４５】
１．クエリＩＤＩがすでにタプル＜ＩＤＩ，ｙＩ＞の（Ｈ'１）ｌｉｓｔ上に出現していれば、Ｈ'１（ＩＤＩ）＝ｙＩ∈Ａで応答する。
２．そうでなければ、＄ＢはＨ１（ＩＤＩ）のクエリを発行する。例えば、Ｈ１（ＩＤＩ）＝α∈★Ｇ＊１である。
【０１４６】
３．＄Ｂはサンプリング関数＄ＬＳ（α）を実行して、ランダム要素ｙ∈Ｌ−１（α）を作成する。
４．＄Ｂは、タプル＜ＩＤＩ，ｙ＞を（Ｈ'）ｌｉｓｔに加え、Ｈ'１（ＩＤＩ）＝ｙ∈Ａで＄Ａに応答する。αは★Ｇ＊１内に一様分布し、Ｌは＄ｌ対１写像であるため、ｙは必要に応じてＡ内に一様分布することに注意されたい。
【０１４７】
Ｈ'１クエリを含む、＄Ａのすべてのクエリへのアルゴリズム＄Ｂの応答は、実際の攻撃における＄Ａの見解と同じである。したがって、＄Ｂは、チャレンジャでゲームに勝利する際のと同じ優位性ε（ｋ）を有する
Ｗｅｉｌペアリングを使用するＩＢＥシステムの詳細例
この節では、ＦｕｌｌＩｄｅｎｔ'を使用して、ＩＢＥシステムの一実施形態の詳細な例を説明する。この実施形態は、Ｗｅｉｌペアリングに基づく。実際にはＴａｔｅペアリングは計算量に関しては有利であり、さまざまな実施形態においてＷｅｉｌペアリングの代わりに使用できるが、比較すると単純なのでＷｅｉｌペアリングを使用する実装について最初に説明する。その後、Ｔａｔｅペアリングについて説明する。
【０１４８】
Ｗｅｉｌペアリングの特性
ｐ＞３を、ｐ＝２  ｍｏｄ  ３を満たす素数とし、ｑをｐ＋１のある素因数とする。Ｅを、★Ｆｐ上の方程式ｙ２＝ｘ３＋１によって定義された楕円曲線とする。この曲線Ｅに関する初等的な事実をいくつか述べる。これ以降、Ｅ（★Ｆ△）は★Ｆ△上で定義されたＥの点からなる群を表すものとする。
【０１４９】
事実１：ｘ３＋１は★Ｆｐ上の順列なので、したがって群Ｅ（★Ｆｐ）はｐ＋１個の点を含む。Ｏで無限遠の点を表す。Ｐ∈Ｅ（★Ｆｐ）を位数ｑの点とし、★Ｇ１をＰによって作成される点のなす部分群とする。
【０１５０】
事実２：任意のｙ０∈★Ｆｐについて、Ｅ（★Ｅｐ）上に一意の点（ｘ０，ｙ０）が存在する、つまり、ｘ０＝（ｙ０２−１）１／３∈★Ｆｐである。したがって、（ｘ，ｙ）がＥ（★Ｆｐ）上のランダムなゼロでない点であれば、ｙは★Ｆｐ上で一様である。この特性を使って、単純な認容的符号化関数を作成する。
【０１５１】
事実３：１≠ζ∈★Ｆ■をｘ３−１＝０  ｍｏｄ  ｐの解とする。すると、写像φ（ｘ，ｙ）＝（ζｘ，ｙ）は、曲線Ｅ上の点のなす群の自己同型写像となる。任意の点Ｑ＝（ｘ，ｙ）∈Ｅ（★Ｆｐ）について、φ（Ｑ）∈Ｅ（★Ｆ■）であるが、φ（Ｑ）∈＼Ｅ（★Ｆｐ）であることに注意されたい。したがって、Ｑ∈Ｅ（★Ｆｐ）はφ（Ｑ）∈Ｅ（★Ｆ■）に関して一次独立である。
【０１５２】
事実４：点Ｐ∈★Ｇ１およびφ（Ｐ）は一次独立なので、これらは、★Ｚｑ×★Ｚｑに同型な群を作成する。この点のなす群をＥ［ｑ］で表す。
★Ｇ２を位数ｑの★Ｆ＊■の部分群とする。曲線Ｅ（★Ｆ■）上のＷｅｉｌペアリングは、写像ｅ：Ｅ［ｑ］×Ｅ［ｑ］→★Ｇ２である。（この写像は、「Ｗｅｉｌペアリングの説明」という表題の節で定義し、説明されている。）任意のＱ、Ｒ∈Ｅ（★Ｆｐ）について、Ｗｅｉｌペアリングはｅ（Ｑ，Ｒ）＝１を満たす。つまり、Ｗｅｉｌペアリングは、Ｅ（★Ｆｐ）上で退化し、したがって、群★Ｇ１上で退化する。非退化写像を得るために、修正したＷｅｉｌペアリングｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を次のように定義する。
【０１５３】
ｅ＾（Ｐ，Ｑ）＝ｅ（Ｐ，φ（Ｑ））
修正したＷｅｉｌペアリングは、以下の特性を満たす。
１．双線形：すべてのＰ、Ｑ∈★Ｇ１について、およびすべてのａ、ｂ∈★Ｚについて、ｅ＾（ａＰ，ｂＱ）＝ｅ＾（Ｐ，Ｑ）ａｂとなる。
【０１５４】
２．非退化：もしＰが★Ｇ１の作成要素ならば、ｅ＾（Ｐ，Ｐ）∈★Ｆ＊■は★Ｇ２の作成要素である。
３．計算可能：Ｐ、Ｑ∈★Ｇ１が与えられた場合、ｅ＾（Ｐ，Ｑ）∈★Ｇ２を計算する効率のよいアルゴリズムが存在する。（このアルゴリズムは、「Ｗｅｉｌペアリングの説明」という表題の以下の節で説明されている。）実行時間は、★Ｆｐの指数に比較しうる。
【０１５５】
計算Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（ＣＤＨ）は群★Ｇ１の中では困難であるように見えるが、決定Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（ＤＤＨ）は★Ｇ１の中では容易である。
【０１５６】
ＢＤＨパラメータ作成要素＄ｇ１：秘匿性パラメータ２＜ｋ∈★Ｚが与えられたとすると、ＢＤＨパラメータ作成要素によりランダムなｋビットの素数ｑを選び、（１）ｐ＝２  ｍｏｄ  ３、（２）ｑはｐ＋１を割り切り、（３）ｑ２はｐ＋１を割り切らないような最小の素数ｐを求める。ｐ＝＄ｌｑ＋１と書く。群★Ｇ１は、★Ｆｐ上の曲線ｙ２＝ｘ３＋１の点のなす群の位数ｑの部分群である。★Ｇ２は★Ｆ＊■の位数ｑの部分群である。双線形写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２は、上で定義した修正されたＷｅｉｌペアリングである。
【０１５７】
ＢＤＨパラメータ作成要素＄ｇ１は、漸近的にＢＤＨ仮定を満たすと考えられる。しかし、それでも、ＢＤＨ問題を十分に困難できる実際に使用可能なｐおよびｑの値には問題がある。最低でも、★Ｇ１における離散対数問題は十分に困難であることを保証することが可能であるのが望ましい。前のほうで指摘したように、★Ｇ１の離散対数問題は、★Ｇ２における離散対数に効率よく帰着できる。したがって、★Ｆ＊■における離散対数を計算することで、十分に★Ｇ１における離散対数を計算できる。実際、★Ｆ＊■の離散対数の固有の秘匿性については、少なくとも５１２ビット長の素数ｐを使用するのが望ましい（したがって、群のサイズは少なくとも１０２４ビット長である）。その結果、実施形態によっては、このＢＤＨパラメータ作成要素は、５１２ビット長以上になりそうな素数ｐで使用される。
【０１５８】
認容的符号化関数：ＭａｐＴｏＰｏｉｎｔ
上で定義したように、★Ｇ１、★Ｇ２を＄ｇ１により作成された２つの群とする。前のほうで説明したＩＢＥシステムは、ハッシュ関数Ｈ１：｛０，１｝＊→★Ｇ＊１を使用していることに留意されたい。ある集合Ａに対するハッシュ関数Ｈ１：｛０，１｝＊→Ａと認容的符号化関数Ｌ：Ａ→★Ｇ＊１を用意するだけで十分である。以下では、集合Ａは★Ｆｐとなり、認容的符号化関数ＬはＭａｐＴｏＰｏｉｎｔと呼ばれ、本発明のさまざまの実施形態で使用することができる。
【０１５９】
この例では、ｐを、ある素数ｑ＞３についてｐ＝２  ｍｏｄ  ３およびｐ＝＄ｌｑ−１を満たす素数とする。この実施例では、ｑは＄ｌを割り切らない（つまり、ｑ２はｐ＋１を割り切らない）。Ｅを★Ｆｐ上の楕円曲線ｙ２＝ｘ３＋１とする。★Ｇ１を位数ｑのＥ上の点のなす部分群とする。さらに、ハッシュ関数Ｈ１：｛０，１｝＊→★Ｆｐを与える。
【０１６０】
この実施例では、アルゴリズムＭａｐＴｏＰｏｉｎｔは入力ｙ０∈★Ｆｐ上で以下のように動作する。
１．ｘ０＝（ｙ０２−１）１／３＝（ｙ０２−１）（２ｐ−１）／３∈★Ｆｐ
２．Ｑ＝（ｘ０，ｙ０）∈Ｅ（★Ｆｐ）とし、ＱＩＤ＝＄ｌＱ∈★Ｇ１と設定する。
【０１６１】
３．ＭａｐＴｏＰｏｉｎｔ（ｙ０）＝ＱＩＤを出力する。
これで、ＭａｐＴｏＰｏｉｎｔの説明は完了である。
＄ｌＱ＝＄ｌ（ｘ０，ｙ０）＝Ｏとなるｙ０∈★Ｆｐの＄ｌ−１個の値が存在することに注意されたい（これらは＄ｌを割り切る位数の非Ｏ点である）。Ｂ⊂★Ｆｐをこれらのｙ０の集合とする。Ｈ１（ＩＤ）がこれら＄ｌ−１個の値の１つであれば、ＱＩＤは★Ｇ１の単位要素である。Ｈ１（ＩＤ）がこれらの点の１つに当たる可能性はほとんどなく、その確率は１／ｑ＜１／２ｋである。したがって、簡単にするため、Ｈ１（ＩＤ）は★Ｆｐ＼Ｂの要素を出力するだけである、つまりＨ１：｛０，１｝＊→★Ｆｐ＼Ｂである。他の実施形態では、異なるハッシュ関数を使用してＩＤを複数回ハッシュすることにより、アルゴリズムＭａｐＴｏＰｏｉｎｔを拡張して値ｙ０∈Ｂを扱えるようにすることが可能である。
【０１６２】
命題８  ＭａｐＴｏＰｏｉｎｔ：★Ｆｐ＼Ｂ→★Ｇ＊１は認容的符号化関数である。
証明  この写像は、明らかに計算可能であり、＄ｌ対１写像である。Ｌがサンプリング可能であることを証明する必要がある。ＰをＥ（★Ｆｐ）の作成要素とする。Ｑ∈★Ｇ＊１が与えられると、サンプリング・アルゴリズム＄ＬＳは、（１）ランダムなｂ∈｛０，．．．，＄ｌ−１｝を選び、（２）Ｑ'＝＄ｌ−１・Ｑ＋ｂｑＰ＝（ｘ，ｙ）を計算し、（３）＄ＬＳ（Ｑ）＝ｙ∈★Ｆｐを出力する。ここで、＄ｌ−１は、★Ｚ＊ｑにおける＄ｌの逆要素である。このアルゴリズムは、必要に応じて、ＭａｐＴｏＰｏｉｎｔ内の＄ｌ個の要素からランダムな要素を出力する。
【０１６３】
ＩＢＥシステムの詳細な例
ＢＤＨパラメータ作成要素＄ｇ１および認容的符号化関数ＭａｐＴｏＰｏｉｎｔを使用して、ＩＢＥシステムの一実施形態の以下の詳細の例を得る。
【０１６４】
Ｓｅｔｕｐ：秘匿性パラメータｋ∈★Ｚ＋が与えられると、このアルゴリズムは以下のように実行する。
工程１：入力ｋでｇを実行し、ｑがｐ＋１を割り切るようなｋビットの素数ｑおよび素数ｐ＝２  ｍｏｄ  ３を作成する。Ｅを、★Ｆｐ上の方程式ｙ２＝ｘ３＋１によって定義された楕円曲線とする。位数ｑの任意のＰ∈Ｅ（★Ｆｐ）を選択する。
【０１６５】
工程２：ランダムなｓ∈★Ｚ＊ｑを選び、Ｐｐｕｂ＝ｓＰと設定する。
工程３：４つのハッシュ関数Ｈ１：｛０，１｝＊→★Ｆｑ、あるｎに対するＨ２：★Ｆ■→｛０，１｝ｎ、Ｈ３：｛０，１｝ｎ×｛０，１｝ｎ→★Ｚ＊ｑ、およびハッシュ関数Ｈ４：｛０，１｝ｎ→｛０，１｝ｎを選ぶ。メッセージ空間は、＄Ｍ＝｛０，１｝ｎである。暗号文空間は、＄Ｃ＝Ｅ（★Ｆｐ）×｛０，１｝ｎである。システム・パラメータは、ｐａｒａｍｓ＝＜ｐ，ｑ，ｎ，Ｐ，Ｐｐｕｂ，Ｈ１，．．．，Ｈ４＞である。ｍａｓｔｅｒ−ｋｅｙは、ｓ∈★Ｚ＊ｑである。
【０１６６】
Ｅｘｔｒａｃｔ：与えられた２進数列ＩＤ∈｛０，１｝＊について、アルゴリズムは秘密鍵ｄを次のように作成する。
工程１：位数ｐのＭａｐＴｏＰｏｉｎｔ（Ｈ１（ＩＤ））＝ＱＩＤ∈Ｅ（★Ｆｐ）を計算する。
【０１６７】
工程２：秘密鍵ｄＩＤをｄＩＤ＝ｓＱＩＤとなるように設定し、ｓはマスター鍵である。
Ｅｎｃｒｙｐｔ：公開鍵ＩＤのもとでＭ∈｛０，１｝ｎを暗号化するには、以下を実行する。
【０１６８】
工程１：位数ｑのＭａｐＴｏＰｏｉｎｔ（Ｈ１（ＩＤ））＝ＱＩＤ∈Ｅ（★Ｆｐ）を計算する。
工程２：ランダムなσ∈｛０，１｝ｎを選択する。
【０１６９】
工程３：ｒ＝Ｈ３（σ，Ｍ）と設定する。
工程４：  暗号文を次のように設定する。
Ｃ＝＜ｒＰ，σ○＋Ｈ２（ｇｒＩＤ），Ｍ○＋Ｈ４（σ）＞  ただし、ｇＩＤ＝ｅ＾（ＱＩＤ，Ｐｐｕｂ）∈★Ｆ■
【０１７０】
Ｄｅｃｒｙｐｔ：Ｃ＝＜Ｕ，Ｖ、Ｗ＞を、公開鍵ＩＤを使用して暗号化された暗号文であるとする。Ｕ∈Ｅ（★Ｆｐ）が位数ｑの点でない場合、その暗号文を拒絶する。秘密鍵ｄＩＤを使用してＣを暗号化するために、以下を実行する。
【０１７１】
工程１．Ｖ○＋Ｈ２（ｅ＾（ｄＩＤ，Ｕ））＝σを計算する。
工程２．Ｗ○＋Ｈ４（σ））＝Ｍを計算する。
工程３．ｒ＝Ｈ３（σ，Ｍ）と設定する。Ｕ＝ｒＰであることを検査する。そうでなければ、その暗号文を却下する。
【０１７２】
工程４．ＭをＣの解読として出力する。
性能。この実施形態では、アルゴリズムＳｅｔｕｐおよびＥｘｔｒａｃｔは非常に単純である。両方のアルゴリズムの中心にあるのは、曲線Ｅ（★Ｆｐ）上の標準の乗法である。アルゴリズムＥｎｃｒｙｐｔでは、エンクリプタがＱＩＤおよびＰｐｕｂのＷｅｉｌペアリングを計算する必要がある。この計算は、メッセージとは無関係であり、したがって、一度だけ実行することが可能であることに注意されたい。ｇＩＤが計算されてしまうと、この実施形態の性能は、標準ＥｌＧａｍａｌ暗号化とほとんど同じである。さらに、ＢａｓｉｃＩｄｅｎｔの実施例の暗号文長は★Ｆｐの通常のＥｌｇａｍａｌの場合と同じであることにも注意されたい。解読は、単純なＷｅｉｌペアリング計算である。
【０１７３】
秘匿性。説明したばかりの詳細な実施例の秘匿性は、定理４と定理７から直接得られる。
系９  上で説明した詳細な実施例は、ＢＤＨパラメータ作成要素＄ｇ１がＢＤＨ仮定を満たしていると仮定した場合の選択暗号文秘匿ＩＢＥシステムである（つまり、ランダム・オラクル・モデルのＩＮＤ−ＩＤ−ＣＣＡ）。
【０１７４】
拡張と観察
Ｔａｔｅペアリングおよびその他の曲線。
このＩＢＥシステムの実施形態は、ＢＤＨ仮定が成立する場合に２つの群★Ｇ１、★Ｇ２の間の効率よく計算できる双線形写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２で動作する。多くの異なる楕円曲線から、このような写像が得られる。例えば、ｐ＝３  ｍｏｄ  ４、ｉ２＝−１、自己準同型写像φ：（ｘ，ｙ）→（−ｘ，ｉｙ）と定められた★Ｆｐ上の曲線ｙ２＝ｘ３＋ｘを使用することが可能である。
【０１７５】
他の実施形態では、ミヤジ他（Ｍｉｙａｊｉ  ｅｔ  ａｌ）（（非特許文献４）を参照）によって説明されている★Ｆｐ上の非超特異楕円曲線族を使用することができる。例えば、この曲線族の曲線Ｅ／★Ｆｐを使用するには、★Ｇ１をＥ（★Ｆ□）（Ｅ（★Ｆｐ）には含まれない）の巡回部分群とみなし、トレース写像を、ペアリングｅ＾を定義するのに使用した自己準同型写像φとして使用することが可能である。なお、ＦｕｌｌＩｄｅｎｔにおける暗号化と解読は両方とも、他の実施形態では、Ｗｅｉｌペアリングの代わりにＴａｔｅペアリングを楕円曲線上で使用することにより、高速化することが可能であることに注意されたい。他の実施形態では、アーベル多様体から適当な双線形写像を誘導することができる。
【０１７６】
非対称ペアリング
前述のように、このＩＢＥシステムの実施形態は、対称写像に限られず、非対称写像をも含むことができる。つまり、実施形態では一般に、★Ｇ０、★Ｇ１を素数位数ｑの群とした場合に、ｅ＾：★Ｇ０×★Ｇ１→★Ｇ２の形式の写像を使用できる。★Ｇ０および★Ｇ１が等しい場合、写像は対称であるという。★Ｇ０と★Ｇ１が等しくない場合、写像は非対称であるという。
【０１７７】
非対称の場合の要素ＱＩＤおよびＰはそれぞれ★Ｇ０および★Ｇ１に属し（逆もまた同様）、ハッシュ関数Ｈ１の対象となる群はそれに応じて選択される。しかし、秘匿性の証明を行うため（特に補助定理２）、ランダムなＰ、ａＰ、ｂＰ∈★Ｇ１およびＱ、ａＱ、ｃＱ∈★Ｇ０が与えられた場合に無視できない確率でｅ＾（Ｐ，Ｑ）ａｂｃを計算することが可能な多項式時間アルゴリズムはないというｃｏ−ＢＤＨ仮定と呼ぶ見かけが少し変わっている複雑度仮定を使用する。この仮定を使用するのであれば、Ｍｉｙａｊｉ  ｅｔ  ａｌの曲線Ｅ／★Ｆｐを使用する実施形態については（上で説明したように）、★Ｇ１を位数ｑの巡回部分群Ｅ（★Ｆｐ）とみなし、★Ｇ０を位数ｑのＥ（★Ｆ□）の別の巡回部分群とみなすことが可能である。これにより、これらの曲線を使用することについて前段落で説明した方法よりも効率的なシステムが得られる。
【０１７８】
分散ＰＫＧ
ＩＢＥシステムの実施例では、ＰＫＧに保管されるｍａｓｔｅｒ−ｋｅｙは保護されるのが望ましい。この鍵を保護する方法として、閾値暗号の手法を使用して異なる複数のサイトに分散させる方法がある。このＩＢＥシステムの実施形態では、これを非常に効率のよい、堅牢な方法でサポートしている。ただし、上述のいくつかの実施形態ては、ｍａｓｔｅｒ−ｋｅｙはあるｓ∈★Ｚ＊ｑとすることができ、ＰＫＧは群作用を使用してｓおよびＱＩＤから秘密鍵を計算し、ＱＩＤはユーザの公開鍵ＩＤから導かれる。例えば、ｄＩＤ＝ｓＱＩＤである。分散ＰＫＧ実施形態は、ｎ個のＰＫＧのそれぞれにｓ  ｍｏｄ  ｑのシャミール秘密分散の１つの割符ｓＩを与えることにより「ｎ個のうちのｔ個」方式で実装することが可能である。ｎ個のＰＫＧはそれぞれ、ｄＩ＝ｓＩＱＩＤを計算することにより、マスター鍵のその割符を使用して、秘密鍵ｄＩＤの対応する割符ｄＩを作成することが可能である。その後、ユーザは、ｎ個のうちのｔ個のＰＫＧに秘密鍵の割符ｄＩを要求し、λＩを適切なラグランジュ補間係数としてｄＩＤ＝ΣＩλＩｄＩを計算することにより割符を結合して秘密鍵全体を構成することが可能である。
【０１７９】
さらに、ＤＤＨは★Ｇ１では容易であるという事実を利用してこの実施形態を堅牢なものにし不正なＰＫＧに対抗するようにすることが容易である。設定時に、ｎ個のＰＫＧのそれぞれＰＩ＝ｓＩＰを公開する。鍵作成要求が出されたら、ユーザは、以下を検査して、ｉ番目のＰＫＧからの応答が有効であることを確認することが可能である。
【０１８０】
ｅ＾（ｄＩ，Ｐ）＝ｅ＾（ＱＩＤ，ＰＩ）
したがって、不正な動作をするＰＫＧは即座に捕捉される。通常の堅牢な閾値方式と同様、ゼロ知識証明の必要はない。ＰＫＧのｍａｓｔｅｒ−ｋｅｙは、Ｒ．ゲナロ他（Ｒ．Ｇｅｎｎａｒｏ  ｅｔ  ａｌ．）（（非特許文献５）を参照）の手法を使用して分散方式で作成することが可能である。また、この手法を使用することで、ＰＫＧは、マスター鍵がどこか１つの場所に存在していなくてもマスター鍵のそれぞれの割符を結合作成できる協調プロトコルを実行することが可能である。
【０１８１】
さらに分散ｍａｓｔｅｒ−ｋｅｙ実施形態を使用すると、メッセージ毎に閾値解読を実行することができ、しかも、対応する解読鍵を導く必要はないことにも注意されたい。例えば、各ＰＫＧがｅ＾（ｓＩ，ＱＩＤ，Ｕ）で応答すれば、ＢａｓｉｃＩｄｅｎｔ暗号文（Ｕ，Ｖ）の閾値解読は簡単である。
【０１８２】
図５は、本発明の一実施形態による分散ＰＫＧシステムを説明するブロック図である。図５は、送信者システム５０１、受信者システム５０２、および３つのＰＫＧ（ＰＫＧ  Ａ  ５０３、ＰＫＧ  Ｂ  ５０４、ＰＫＧ  Ｃ  ５０５）を含む。「３個のうちの２個」分散方式を説明する一実施形態では、３つのＰＫＧはそれぞれ、マスター鍵の異なる割符を含み、３つのうち２つでマスター鍵を誘導することができる。図に示されているように、ＰＫＧ  Ａ  ５０３、ＰＫＧ  Ｂ  ５０４、およびＰＫＧ  Ｃ  ５０５は、それぞれマスター鍵割符ｓ１、５１１、マスター鍵割符ｓ２、５１２、およびマスター鍵割符ｓ３、５１３を含む。「３個の２個」分散方式では、３個のうち２個のＰＫＧにより割符を結合し、マスター鍵を決定することが可能であるが、この実施形態では、それぞれのＰＫＧは秘密のうちにそのマスター鍵割符を保持する。
【０１８３】
送信者システム５０１は、受信者５０２にメッセージを送信する。メッセージ５１４は、受信者の識別子ＩＤに基づく公開鍵を使用して暗号化することができる。対応する秘密鍵を取得するために、受信者システムは、例えば、受信者のＩＤまたは公開鍵を使用して３個のうち２個のＰＫＧにクエリを実行する。図に示されているように、受信者システム５０２は、クエリ５０６および５０７をそれぞれＰＫＧ  Ａ  ５０３およびＰＫＧ  Ｂ  ５０４に送り、秘密鍵の２つの割符を取得する。これらのクエリへの応答として、ＰＫＧ  Ａ  ５０３およびＰＫＧ  Ｂ  ５０４は、それぞれ、秘密鍵ｄ、５１０の割符ｄ１、５０８、および割符ｄ２、５０９を返す。その後、受信者システム５０２は、対応する秘密鍵ｄＩＤを構成することができるが、これは、メッセージ５１４の暗号化に使用された公開鍵に対応している。より一般的には、受信者は３個のうち任意の２個のＰＫＧにクエリを行うように選択しておくことが可能である。例えば、受信者システム５０２は、他の方法として、ＰＫＧ  ＢおよびＣにクエリを実行し、秘密鍵割符ｄ２およびｄ３を結合して、秘密鍵５１０を作成しておくことが可能である。これらの手法は一般化をたやすく行うことができ、ｎ個のうちｔ個という分散方式を使用して類似の実施形態が得られる。
【０１８４】
送信者システム５０１、受信者システム５０２、さらにＰＫＧ  ５０３、５０４、および５０５は、それぞれ、プロセッサおよびメモリおよび他の記憶デバイスなどのコンピュータ可読媒体などの要素を備えるコンピュータ・システムとして実装することができる。それぞれの要素間の通信は、データ・ネットワーク上で送信するデータ・パケットを使用して、または他のさまざまな形態の電子的およびデータ伝送および通信を使用して行うことができる。通信は、各種の有線、無線、およびその他の通信媒体を利用する、インターネットなどのコンピュータ・ネットワークなど、さまざま通信アーキテクチャを介して伝送することができる。
【０１８５】
部分群での動作
上述の詳細なＩＢＥシステムの他の実施形態では、曲線の比較的小さな部分群において動作させることにより性能を改善することができる。例えば、ある１６０ビットの素数ｑについてｐ＝ａｑ−１となる１０２４ビットの素数ｐ＝２  ｍｏｄ  ３を選択する。そこで、点Ｐを、位数ｑの点となるように選択する。各公開鍵ＩＤを曲線Ｑ上の点にハッシュし、その後、ａをその点に掛けてＩＤを群の点に変換する。システムは、Ｐによって作成された群においてＢＤＨ仮定が成立する場合に秘匿性がある。この実施形態の利点は、Ｗｅｉｌ計算が小さな位数の点で実行され、したがってかなり高速であることである。
【０１８６】
ＩＢＥは署名を含む
上述のさまざまなＩＢＥ手法を使用して、公開鍵署名システムおよび方法を実現することが可能である。考え方は以下のとおりである。署名方式の秘密鍵は、ＩＢＥ方式のマスター鍵である。この署名方式の公開鍵は、ＩＢＥ方式の大域的システム・パラメータの集合である。メッセージＭの署名は、ＩＤ＝Ｍに対するＩＢＥ解読鍵である。署名を検証するために、ランダム・メッセージＭ'を選択し、公開鍵ＩＤ＝Ｍを使用してＭ'を暗号化し、それから、Ｍの指定された署名を解読鍵として使用して解読を試みる。ＩＢＥシステムがＩＮＤ−ＩＤ−ＣＣＡの場合、署名方式は選択メッセージ攻撃に対し存在的偽造不可である。ただし、たいていの署名方式とは異なり、この署名検証実施形態はランダム化されている。このことから、ここで説明しているＩＢＥ手法は公開鍵暗号化と電子署名の両方を包含することができる。これらのアプローチから派生する署名方式を使用して、興味深い特性を得ることが可能であるが、これについてはボネ他（Ｂｏｎｅｈ  ｅｔ  ａｌ．）（本願明細書に援用する（非特許文献６）で説明している。
【０１８７】
エスクローＥｌＧａｍａｌ暗号化
この節では、上述のさまざまなＩＢＥ手法を使用して、大域的エスクロー機能を持つＥｌＧａｍａｌ暗号化システムの実施形態を実現することが可能であることを示す。本実施形態では、単一のエスクロー鍵を使用して、任意の公開鍵で暗号化された暗号文の解読を行うことができる。
【０１８８】
１実施例では、ＥｌＧａｍａｌエスクロー・システムは以下のように動作する。ＳｅｔｕｐはＢａｓｉｃＩｄｅｎｔのと類似している。ＩＤベースＢａｓｉｃＩｄｅｎｔと異なり、それぞれのユーザが秘密乱数を選択し、それを使用して、公開鍵／秘密鍵のペアを作成する。こうして、送信者および受信者はＥｎｃｒｙｐｔとＤｅｃｒｙｐｔを使用して、暗号化されたメッセージを伝達することが可能である。メッセージは、マスター鍵ｓをメッセージの解読に使用することが可能なエスクローを除き秘匿される。
【０１８９】
図６は、本発明の一実施形態によるエスクロー解読機能を備える暗号システム内の要素を説明するブロック図である。システムは、暗号化論理回路６１０を備える送信者システム６０１、解読論理回路６１１を備える受信者システム６０２、エスクロー・エージェント・システム６０４、およびブロードキャスト・システム６０５を含む。ブロードキャスト・システム６０５は、エスクロー・エージェント・システム６０４、受信者システム６０２、および送信者システム６０１などの参加者にシステム・パラメータを送信する。受信者システム６０２は、秘密鍵ｘ、６０７を選択し、それを使って、公開鍵Ｐｐｕｂ＝ｘＰ、６０６を作成し、その後、公開する。秘密鍵ｘおよび公開鍵Ｐｐｕｂは、相補的鍵の対を形成する。送信者システム６０１は、公開鍵Ｐｐｕｂ＝ｘＰ、６０６を使用し、暗号化論理回路６１０でメッセージＭを暗号化する。送信者システム６０１は、その結果得られた暗号化されたメッセージ６０３を受信者６０２に送信する。受信者システム６０２は、秘密鍵ｘ、６０７を使用して解読論理回路６１１でメッセージを解読する。エスクロー・エージェント・システム６０４は、メッセージ６０３を横取りし、エスクロー・エージェント鍵ｓ、６０９、公開鍵Ｐｐｕｂ＝ｘＰ、６０６を使用し、解読論理回路６１２でメッセージ６０３を解読する。他の実施形態では、ブロードキャスト・システム６０５およびエスクロー・エージェント６０４は、単一のエンティティであってもよい。さらに他の実施形態では、すでに述べている分散ＰＫＧ実施形態などの方法でエスクロー・エージェント鍵を共有することができる。
【０１９０】
さらに詳細には、この手法の実施例は以下の手順を含む。
Ｓｅｔｕｐ：＄ｇをあるＢＤＨパラメータ作成要素とする。秘匿性パラメータｋ∈★Ｚ＋が与えられると、このアルゴリズムは以下のように実行する。
【０１９１】
工程１：入力ｋに対して＄ｇを実行し、素数ｑ、位数ｑの２つの群★Ｇ１、★Ｇ２、および認容写像ｅ＾：★Ｇ１×★Ｇ１→★Ｇ２を作成する。Ｐを★Ｇ１のある作成要素とする。
【０１９２】
工程２：ランダムなｓ∈★Ｚ＊ｑを選び、Ｑ＝ｓＰと設定する。
工程３：暗号ハッシュ関数Ｈ：★Ｇ２→｛０，１｝ｎを選択する。
メッセージ空間は、＄Ｍ＝｛０，１｝ｎである。暗号文空間は、＄Ｃ＝★Ｇ１×｛０，１｝ｎである。システム・パラメータは、ｐａｒａｍｓ＝＜ｐ，★Ｇ１，★Ｇ２，ｅ＾，ｎ，Ｐ，Ｑ，Ｈ＞である。エスクロー鍵は、ｓ∈★Ｚ＊ｑである。
【０１９３】
ｋｅｙｇｅｎ：ユーザは、ランダムなｘ∈★Ｚ＊ｑを選び、Ｐｐｕｂ＝ｘＰ∈★Ｇ１を計算して、自分自身の公開鍵／秘密鍵の対を作成する。ユーザの秘密鍵はｘ（またはｘＱ）であり、ユーザの公開鍵はＰｐｕｂである。
【０１９４】
Ｅｎｃｒｙｐｔ：公開鍵ＰｐｕｂのもとでＭ∈｛０，１｝ｎを暗号化するために、（１）ランダムなｒ∈★Ｚ＊ｑを選び、（２）暗号文を以下のように設定する。
Ｃ＝＜ｒＰ，Ｍ○＋Ｈ（ｇｒ）＞  ただし、ｇ＝ｅ＾（Ｐｐｕｂ，Ｑ）∈★Ｇ２。
【０１９５】
こと暗号化手法はさらに、図７でも説明されており、そこで、送信者は、ブロック７００で、システム・パラメータおよび要素ＰおよびＱ＝ｓＰを取得し、ブロック７１０で、受信者の公開鍵Ｐｐｕｂ＝ｘＰを取得する。その後、ブロック７２０で、送信者は乱数ｒを選択し、メッセージ鍵を計算する。その後、ブロック７３０で、メッセージ鍵を使用してメッセージを暗号化する。次に、送信者は、カプセル化された鍵ｒＰおよび暗号化されたメッセージＶを受信者に送信する。
【０１９６】
Ｄｅｃｒｙｐｔ：Ｃ＝＜Ｕ，Ｖ＞を、Ｐｐｕｂを使用して暗号化された暗号文であるとする。すると、Ｕ∈★Ｇ１である。秘密鍵ｘを使用してＣを解読するために、以下を実行する。
【０１９７】
Ｖ○＋Ｈ（ｅ＾（Ｕ，ｘＱ））＝Ｍ
図８で説明されているように、受信者は、ブロック８００で、システム・パラメータおよび要素ＰおよびＱ＝ｓＰを取得し、ブロック８１０で、暗号化されたメッセージＶおよびカプセル化された鍵ｒＰを送信者から取得する。その後、ブロック８２０で、受信者はメッセージ鍵を計算し、ブロック８３０で、これを使用してメッセージを解読する。
【０１９８】
送信者および受信者によって計算されたメッセージ鍵が同じであることを見るためには、送信者は秘密ｒだけでなく公開Ｑ＝ｓＰおよびＰｐｕｂ＝ｘＰも知り、これらを使用して、ｅ＾（ｓＰ，ｘＰ）ｒから鍵を計算することに注意されたい。一方、受信者は、秘密ｘだけでなく公開Ｑ＝ｓＰおよびｒＰを知り、これらを使用して、ｅ＾（ｒＰ，ｘ（ｓＰ））からメッセージ鍵を計算する。ｅ＾の双線形性から、ｅ＾（ｓＰ，ｘＰ）ｒ＝ｅ＾（ｒＰ，ｘ（ｓＰ））が成り立ち、ゆえに、送信者および受信者は同じメッセージ鍵を計算する。
【０１９９】
Ｅｓｃｒｏｗ−ｄｅｃｒｙｐｔ：この実施形態の目的は、他の方法で秘匿性のある通信のエスクロー解読を行えるようにすることである。エスクロー鍵ｓを使用してＣ＝＜Ｕ，Ｖ＞を解読するために、以下を計算する。
【０２００】
Ｖ○＋Ｈ（ｅ＾（Ｕ，ｓＰｐｕｂ））＝Ｍ
図９に示されているように、エスクローは、ブロック９００で、システム・パラメータおよび要素Ｐを取得し、ブロック９１０で、受信者の公開鍵ｘＰを取得し、送信者から暗号化されたメッセージＶおよびカプセル化された鍵ｒＰを取得する。その後、ブロック９２０で、エスクローはメッセージ鍵を計算し、ブロック９３０で、これを使用してメッセージを解読する。エスクローは、ｓ、ｒＰ、およびｘＰを知ってメッセージを計算することが可能である。
【０２０１】
標準的な議論から、ＢＤＨが＄ｇで作成され群に対し困難であると仮定すると、この実施形態のシステムは、ランダム・オラクル・モデルにおいて意味秘匿性を有することがわかる（ＤＤＨは容易であるため、ＤＤＨに基づいて意味秘匿性を証明することはできないことに留意されたい）。それでも、エスクロー・エージェントは、ユーザの公開鍵を使用して暗号化した暗号文を解読することが可能である。エスクロー・エージェントの解読機能は、前に述べたＰＫＧ分散手法を使用して分散させることが可能である。
【０２０２】
他の実施形態では、非大域的エスクローを使用するＥｌＧａｍａｌ暗号化システムとともに類似の困難さ仮定を使用する。この実施形態では、それぞれのユーザが２つの対応する秘密鍵を使って公開鍵を構成し、その秘密鍵の一方を信頼できる第三者に与える。信頼できる第三者は、さまざまなユーザから与えられたすべての秘密鍵のデータベースを保持する。秘密鍵は両方とも、解読に使用可能であるが、ユーザの秘密鍵のみ、離散対数ベースの署名方式の署名鍵として同時に使用することが可能である。
【０２０３】
他のさまざまな暗号システムを、上記の実施形態に示されている原理に考案することが可能である。例えば、３つのエンティティＡ、Ｂ、およびＣは、個人として乱数整数ａ、ｂ、ｃを選択し、公開鍵ａＰ、ｂＰ、ｃＰを公開することにより１つのグループとして安全に通信することが可能である。そのうちの１つ、例えばＡはメッセージ鍵ｅ＾（ｂＰ，ｃＰ）ｒを使用してメッセージを暗号化し、ｒＰとともに送信することが可能である。次にＢが、ｅ＾（ｃＰ，ｒＰ）ｒを計算してメッセージを解読し、Ｃは、ｅ＾（ｂＰ，ｒＰ）ｃを計算してそのメッセージを解読することが可能である。同様、ＢがメッセージをＡおよびＣに送信するか、またはＣがメッセージをＡおよびＢに送信することが可能である。
【０２０４】
他の考えられる実施形態では、３つのエンティティのうち２つ、例えばＡとＢは、共有公開鍵ａｂＰを公開することが可能である。次に、Ｃはメッセージ鍵ｅ＾（ａｂＰ，ｃＰ）ｒを使用してメッセージを暗号化し、ｒＰとともに送信することが可能である。すると、ＡもＢも単独ではメッセージを解読しえないが、ＡとＢの両方が一緒にｅ＾（ｃＰ，ｒＰ）ａｂを計算し、共同でメッセージを解読することは可能である。この手法は、任意の数のエンティティに一般化される。例えば、Ｃは、ａｂＰを使用して三者共有公開鍵ａｂｃＰを計算し公開することにより、ＡおよびＢを参加させることが可能である。その後は、誰でも、メッセージ鍵ｅ＾（ａｂｃＰ，ｘＰ）ｒを使用してメッセージを暗号化し、ｒＰとともに送信することが可能になる。その後、ＡおよびＢおよびＣのみが一緒に、ｅ＾（ｘＰ，ｒＰ）ａｂｃを計算し、共同で、メッセージを解読することが可能である。
【０２０５】
しきい値解読
本発明の実施形態では、ｎ個のエンティティが与えられた公開鍵ＩＤに対応する秘密鍵ｄＩＤの割符を所有し、ｎ個のｔ個のエンティティが共同する場合にのみ、そのＩＤを使用して暗号化されたメッセージを解読するようにすることが可能である。秘密鍵ｄＩＤは、決して、単一の場所では再構成されない。このＩＢＥシステムの実施形態ではこれに以下のように対応できる。
【０２０６】
他の実施形態では、ｓ∈★Ｚ＊ｑがマスター鍵であるとして秘密鍵ｄＩＤ＝ｓＱＩＤであることに留意されたい。その代わりに、ｓ１，．．．，ｓｎ∈★Ｚ＊ｑをマスター鍵ｓの「ｎ個のうちｔ個」シャミール秘密分散とする。ｎ人のユーザのそれぞれにｄＩ＝ｓＩＱＩＤを与える。鍵ＩＤを使用して暗号化された暗号文＜Ｕ，Ｖ＞を解読するために、各ユーザはローカルでｇＩ＝ｅ＾（Ｕ，ｄＩ）を計算し、解読工程を管理するユーザにｇＩ∈★Ｇ２を送信する。そのユーザは、λＩをシャミール秘密分散で使用される適切なラグランジュ補間係数としてｇＩＤ＝ΠＩｇＩ▲を計算することにより解読割符を結合する。その後、Ｈ２（ｇＩＤ）○＋Ｖ＝Ｍを計算することによりメッセージを取得する。
【０２０７】
暗号法の当業者であれば、本発明の基本原理を使用する他の多くの方式を考案することができるであろう。
ＩＤベース暗号化の応用
ＩＤベース暗号化の実施形態の一応用として、公開鍵インフラストラクチャの配備の支援が考えられる。この節では、このような応用およびその他の応用のいくつかの実施形態を示す。
【０２０８】
公開鍵の取り消し
この本実施形態では、送信者は、年、日、またはその他の時刻表示などの時間要素を含む情報から誘導された公開鍵を使用して暗号化し、鍵の有効期限またはその他の形式の時間に関係する鍵管理の実現を補助することができる。例えば、一実施形態では、"ｂｏｂ＠ｃｏｍｐａｎｙ．ｃｏｍ  ｜｜  ｃｕｒｒｅｎｔ−ｙｅａｒ"というように公開鍵を使用して、ボブに送信する電子メールをアリスに暗号化してもらうことで鍵の有効期限を定められる。そうすることで、ボブは今年のみ自分の秘密鍵を使用することが可能である。１年に一度、ボブはＰＫＧから新規の秘密鍵を取得する必要がある。こうして、秘密鍵有効期限を１年間に設定する効果が得られる。既存の公開鍵インフラストラクチャとは異なり、ボブが自分の秘密鍵を更新する毎に、アリスがボブから新規証明書を取得する必要はないことに注意されたい。
【０２０９】
他の実施形態において、"ｂｏｂ＠ｃｏｍｐａｎｙ．ｃｏｍ  ｜｜  ｃｕｒｒｅｎｔ−ｄａｔｅ"または他のタイムスタンプを使用してボブ宛の電子メールを暗号化することにより、このアプローチの設定を細かくできる。こうすることで、ボブはいやおうなく新規秘密鍵を毎日取得することになる。この実施形態は、ＰＫＧが企業によって維持されている場合に企業環境内で使用することができる。このアプローチでは、鍵の取り消しは非常に単純であり、ボブが退社し、その鍵を取り消す必要が生じたら、企業ＰＫＧに、ボブの電子メール・アドレスに対応する秘密鍵の発行を停止するよう指令するという形をとる。その結果、ボブは自分の電子メールを読めなくなる。興味深い特性として、アリスは、ボブの毎日の公開鍵を取得するために第三者の証明書ディレクトリとやりとりする必要がないという点が挙げられる。したがって、ＩＤベース暗号化の実施形態は、一日限りの公開鍵を実装する非常に効率のよいメカニズムを実現することが可能である。なお、この実施形態を使用すると、アリスが未来に向けてメッセージを送信することができる、つまりボブはアリスの指定した日付に限り電子メールを解読することができるようになる。
【０２１０】
ユーザ信任状の管理
本発明の一実施形態では、ＩＢＥシステムを使用してユーザ信任状を管理することができる。メッセージは、信任状識別子を含む文字列で暗号化される。例えば、アリスが公開鍵を使用して"ｂｏｂ＠ｃｏｍｐａｎｙ．ｃｏｍ  ｜｜  ｃｕｒｒｅｎｔ−ｙｅａｒ  ｜｜  ｃｌｅａｒａｎｃｅ＝ｓｅｃｒｅｔ"というようボブへのメールを暗号化する。すると、ボブは、指定された日に機密取扱資格がある場合にのみその電子メールを読むことができる。したがって、ＰＫＧを使用するとユーザ信任状の付与および取り消しは非常に容易である。
【０２１１】
図１０は、本発明の一実施形態によりＩＤベース暗号化システムで信用状を管理するシステムを説明するブロック図である。システムは、送信者システム１００１、受信者システム１００２、およびＰＫＧ  １００３を備える。このようなシステムはそれぞれ、コンピュータ・ネットワークに接続されたクライアントまたはサーバなどコンピュータ・システムとして実装することができる。そのため、送信者１００１、受信者１００２、およびＰＫＧ  １００３は、それぞれ、プロセッサ１０１４、プロセッサ１０１３、およびプロセッサ１０１２などのプロセッサを備えることができる。さらに、これらのシステムは、コンピュータ・メモリなどのコンピュータ可読記憶媒体を備え、さらに、有線、無線、またはその他のネットワークとの通信に対応する技術を含む、コンピュータ・ネットワークとのインターフェイスを備えることができる。送信者システム１００１は、ソフトウェア・プラグイン１０１７を備えることができる。このようなプラグインは、暗号機能を実行するソフトウェア・モジュールを含むことができる。本発明の一実施形態によれば、プラグインには、暗号論理回路１００４などが含まれる。プラグイン１０１７は、ネットワーク経由で送信者システム１００１および受信者システム１００２などのさまざまなコンピュータに配布し、ＩＤベース暗号化と関連する機能およびその他の通信機能を展開することができる。ＰＫＧ  １００３などのシステムからのパラメータ１０１５も、コンピュータ・ネットワークまたはその他の通信媒体経由で、送信者システム１００１および受信者システム１００２など送信者および受信者に配布し、これらのシステムでは、メッセージを暗号化または解読する際にプラグイン１０１７とともにそれらのパラメータを使用することができる。一実施形態では、プラグイン１０１７は、パラメータとともに配布される。他の実施形態では、パラメータ１０１５を別々に配布することもできる。
【０２１２】
送信者システム１００１は、プラグイン１０１７の暗号化論理回路１００４を使用してメッセージＭを暗号化する。暗号化論理回路１００４は、選択した信任状１００５およびメッセージの宛先受信者の識別１０１６に基づく暗号鍵１０１１を使用してメッセージを暗号化する。いくつかの実施形態では、この鍵は、他の情報にも基づくことができる。送信者システム１００１は、受信者システム１００２に情報１００６を、例えば、ネットワークまたはその他の通信媒体経由で送信されるデータ・パケットの形式で送信する。受信者システム１００２に送信された情報１００６には、暗号化されたメッセージが入っており、さらに、暗号鍵の基盤の一部として使用される信任状１００５に関する情報１００７も含めることができる。
【０２１３】
情報１００６の受信前であろうと受信後であろうと、受信者システム１００２は要求１００９をＰＫＧ  １００３に送信する。一実施形態では、要求１００９は、受信者のＩＤ  １０１６を含むことができ、さらに、選択した信任状１００５に関係する情報を入れることもできる。応答として、ＰＫＧ  １００３は信任状検査論理回路１００８を使用して受信者１００２の信任状を検証する。このような論理回路は、ソフトウェア、ハードウェア、またはその組み合わせで実装することができる。信任状が受信者に属するものとして検証された場合、ＰＫＧ  １００３は応答１０１０を受信者１００２に送るが、この応答は、暗号鍵１０１１に対応する秘密解読鍵１０１８を含む。次に、秘密解読鍵を使用することで、受信者は情報１００６に含まれる暗号化されたメッセージを解読し、オリジナルのメッセージＭを復要素することができる。したがって、このような実施形態では、暗号鍵の一部として信任状を含めることにより、送信者が受信者宛先のメッセージを暗号化することができ、受信者によるメッセージの解読を受信者の信任状の有効性を条件とするようにできる。
【０２１４】
解読鍵の委託
ＩＢＥシステムを実施形態の他の応用として、解読機能の委託がある。ＰＫＧの役割を果たすユーザであるボブについて説明した２つの実施例を用意する。ボブは、設定アルゴリズムを実行して、自分のＩＢＥシステム・パラメータｐａｒａｍｓおよび自分のｍａｓｔｅｒ−ｋｅｙを作成する。ここで、ｐａｒａｍｓをボブの公開鍵であるとみなす。ボブは、自分の公開鍵ｐａｒａｍｓ用にＣＡからの証明書を入れる。アリスは、ボブにメールを送信したい場合、最初にボブの公開鍵ｐａｒａｍｓをボブの公開鍵証明書から取得する。ボブは、自分のｍａｓｔｅｒ−ｋｅｙを知っている唯一の人物であり、したがって、この設定には鍵エスクローはないことに注意されたい。
【０２１５】
１．ラップトップへの委託。アリスがＩＢＥ暗号鍵として現在の日付を使用してボブへのメールを暗号化すると仮定する（アリスは、ボブのｐａｒａｍｓをＩＢＥシステム・パラメータとして使用する）。ボブはｍａｓｔｅｒ−ｋｅｙを持っているので、このＩＢＥ暗号鍵に対応する秘密鍵を抽出して、メッセージを解読することが可能である。そこで、ボブは７日間旅行に出るとする。通常であれば、ボブは自分の秘密鍵を自分のラップトップに入れる。ラップトップが盗まれると、秘密鍵は危険にさらされることになる。ＩＢＥシステムを使用すると、ボブは単に、自分のラップトップに７日間の旅行期間に対応する７日分の秘密鍵をインストールするだけよい。ラップトップが盗まれた場合でも、７日間の秘密鍵しか損なわれない。ｍａｓｔｅｒ−ｋｅｙは、無事である。
【０２１６】
図１１は、本発明の一実施形態による鍵委託機能を備えるシステムを説明するブロック図である。システムは、ユーザ・システム１１０１およびターゲット・システム１１０２を備える。ターゲット・システムは、ラップトップ・コンピュータなどのコンピュータを含むことができる。ユーザ・システム１１０１は、解読鍵１１０４を作成するために使用される、マスター鍵１１０３を含む。解読鍵１１０４は、ターゲット・システム１１０２にダウンロードされる。上述の鍵取り消しの手法を使用すると、これらの解読鍵は、限られた期間のみ有効にすることができ、したがって、ターゲット・システム１１０１が危険にさらされた場合でも秘匿性を高められる。ユーザ・システム１１０１およびターゲット・システム１１０２は、メモリ１１０６および１１０７さらにプロセッサ１１０５および１１０８などのコンピュータ・システムの要素を備えることができる。ユーザ・システム１１０１は、ユーザＩＤ  １１１３および１つ以上の日付１１１４またはその他のタイムスタンプから導かれる情報に基づきマスター鍵１１０３およびシステム・パラメータ１１１０を使用して秘密解読鍵１１０４を作成する鍵作成器論理回路１１０９を備える。ターゲット・システム１１０２は、ユーザ・システム１１０１およびシステム・パラメータ１１１０から得られた秘密解読鍵１１０４を使用して受信した暗号化されたメッセージ１１１２を解読する、解読論理回路１１１１を備える。ＩＤ  １１１３および日付１１１４の１つに基づいて公開鍵を使用してメッセージ１１１２が暗号化されている場合、秘密解読鍵を使用して、それを解読することができる。したがって、ターゲット・システム１１０２の解読機能を、選択した日付１１１４と関連するメッセージに制限することができる。他の実施形態では、ターゲット・システムは、必要に応じて他のコンピュータ・システムに接続することが可能なデータ記憶媒体または携帯型データ記憶デバイスとすることができ、そのため、これらのシステム上の解読鍵を使用することができる。
【０２１７】
２．職務の委任。アリスが、件名をＩＢＥ暗号鍵として使用してボブへのメールを暗号化するものとする。ボブは、自分のｍａｓｔｅｒ−ｋｅｙを使用してメールを解読することが可能である。そこで、ボブには、複数のアシスタントがおり、それぞれ異なる職務を担当していると仮定する（例えば、「購買」担当、「人事」担当など）。この本実施形態では、ボブはアシスタントの責任に対応する秘密鍵を１つ、各アシスタントに与えることができる。そこで、各アシスタントは、自分の責任範囲内の件名が設定されているメッセージを解読することは可能であるが、他のアシスタントを宛先とするメッセージを解読することは可能でない。アリスは、ボブからの単一の公開鍵（ｐａｒａｍｓ）のみを取得し、その公開鍵を使用して自分の選択した件名が含まれるメールを送信することに注意されたい。メールは、その件名の担当であるアシスタントにとってのみ可読である。
【０２１８】
より一般的には、ＩＢＥの実施形態により、多数の公開鍵を管理するさまざまなシステムを簡素化することが可能である。システムでは、公開鍵の大きなデータベースを保管するのではなく、ユーザの名前からこれらの公開鍵を導くか、または単に、整数１，．．．，ｎを異なる公開鍵として使用することが可能である。例えば、企業では、各社員に一意の社員番号を割り当て、その番号を社員の公開鍵としても使用することができる。
【０２１９】
受信確認返信
図１２は、本発明の一実施形態による受信確認返信機能を備える暗号システムを説明するブロック図である。本発明の一実施形態によれば、送信者は受信者が暗号化されたメッセージを受信したという確認を受信することが可能である。より一般的には、受信者から解読鍵の要求を受信したときに、ＰＫＧは解読鍵を受信者に与えることとは別のアクションを実行する。このようなアクションは、一実施形態による、メッセージを受信したことを示す受信確認を送信者に送る動作を含む。
【０２２０】
受信確認返信機能を備えるシステムの一実施形態が図１２に示されている。システムは、送信者システム１２０１、受信者システム１２０２、およびＰＫＧシステム１２０３を備える。送信者システム１２０１、受信者システム１２０２、およびＰＫＧシステム１２０３は、コンピュータ・ネットワークに結合されたコンピュータ・システムとして実装することができる。例えば、ＰＫＧ  １２０３、送信者システム１２０１、および受信者システム１２０２は、プロセッサ１２１２、プロセッサ１２１３、およびプロセッサ１２１４をそれぞれ備えることができる。これらのコンピュータ・システムは、コンピュータ可読記憶媒体、コンピュータ・メモリ、およびその他の記憶デバイスなどの要素を備えることができる。さらに、これらのシステムは、有線、無線、またはその他のネットワークとの通信に対応する技術を含む、コンピュータ・ネットワークとのインターフェイスを備えることができる。さらに、本発明の一実施形態によれば、それぞれの要素間の通信は、コンピュータ・ネットワーク上で送信されるデータ・パケットを使用して、または他のさまざまな形態の電子的およびデータ伝送および通信を使用して行うことができる。
【０２２１】
送信者１２０１は、メッセージＭを暗号化し、その結果得られた暗号文を受信確認返信要求情報１２０９も含むことができるデータ・パッケージ１２０４で受信者１２０２に送信する。受信確認返信要求情報は、例えば、返信アドレスおよび、特定のメッセージ１２０４に対応するメッセージ識別子を含むことができる。メッセージＭは、送信者により、暗号化論理回路１２１１および暗号鍵１２１５を使用して、暗号化される。暗号鍵１２１５は、受信者ＩＤ（電子メール・アドレスなど）１２１６および受信確認返信要求情報１２０９に基づくことができる。暗号鍵１２１５の決定のため送信者により受信者ＩＤおよび受信確認返信要求情報１２０９が使用されるため、受信者１２０２は、そのメッセージを解読するために使用することができる対応する解読鍵を必要とする。したがって、受信者システム１２０２は、メッセージ１２０４を受信したことに対する応答として、ＰＫＧ  １２０３に要求１２０６を送信するが、これには、受信確認返信要求情報１２０９および受信者のＩＤ、１２１６が含まれる。応答として、ＰＫＧ  １２０３は受信者１２０２に、秘密解読鍵１２０５を送信し、その後受信者はその解読鍵を解読論理回路１２１７で使用してメッセージ１２０４の暗号文を解読し、オリジナルのメッセージＭを復元する。受信者１２０２に解読鍵１２０５を送信するほかに、ＰＫＧ  １２０３はさらに、受信確認返信１２０７を送信者１２０１に送信する。ＰＫＧ  １２０３は、それとは別に、受信確認返信を送信するのではなく、ログの一部として受信結果を記憶媒体上に格納することができる。受信確認返信１２０７は、メッセージ識別子などの情報を含むことができる。こうして、送信者１２０１は、受信者１２０２がメッセージ１２０４を受信したという証明を受信する。システムは、プラグイン・ソフトウェアを送信者システム１２０１および受信者システム１２０２などさまざまなシステムに置くことにより初期化することができる。このようなプラグイン・ソフトウェアに、システム・パラメータを含めることができ、その一部はシステム・マスター鍵から導くことができる。送信者１２０１および受信者１２０２などのローカル・デバイスに格納されているこのようなパラメータを使用して、暗号鍵の作成、暗号化の実行、解読の実行、およびその他の機能を、適宜行う。
【０２２２】
Ｗｅｉｌペアリングの説明
この節では、楕円曲線上のＷｅｉｌペアリングについて説明し、その後、アルゴリズムを使用して効率よく計算する方法を示す。具体的には、ｐ＞３の素体★Ｆｐ上で定義された超特異楕円曲線を使用する例を示す（ｐ＝２  ｍｏｄ  ３の★Ｆｐ上の曲線ｙ２＝ｘ３＋１がこのような曲線の一例である）。以下の説明は、他の楕円曲線上のＷｅｉｌペアリングの計算に容易に一般化できる。
【０２２３】
楕円曲線とＷｅｉｌペアリング
ｐ＞３の素体★Ｆｐ上で定義された超特異楕円曲線に関する初等的な事実をいくつか述べる。
【０２２４】
事実１：超特異曲線Ｅ／★Ｆｐ（ｐ＞３）は★Ｆｐ内にｐ＋１個の点を含む。Ｏで無限遠の点を表す。★Ｆｐ上の点の群は、位数ｐ＋１の巡回群をなす。簡単にするため、Ｐをこの群の作成要素とし、ｎ＝ｐ＋１と設定する。
【０２２５】
事実２：点Ｅ（★Ｆ■）の群は、Ｅ（★Ｆｐ）内の点に関して一次独立である位数ｎの点Ｑを含む。したがって、Ｅ（★Ｆ■）は、群★Ｚ２ｎに同型な部分群を含む。この群は、Ｐ∈Ｅ（★Ｆｐ）およびＱ∈Ｅ（★Ｆ■）によって作成される。この群をＥ［ｐ＋１］＝Ｅ［ｎ］で表す。
【０２２６】
Ｅ［ｎ］内の点の対を★Ｆ＊■に写像するＷｅｉｌペアリングｅ、つまりｅ：Ｅ［ｎ］×Ｅ［ｎ］→★Ｆ＊■を扱う。このペアリングを説明するために、以下の概念を復習する。
【０２２７】
因子  因子とは、曲線Ｅ（★Ｆ■）上の点の形式和のことである。ａＰ∈★Ｚ、Ｐ∈Ｅ（★Ｆ■）として、因子を＄Ａ＝Σｐａｐ（Ｐ）と書く。例えば、＄Ａ＝３（Ｐ１）−２（Ｐ２）−（Ｐ３）は因子である。ここでは、Σｐａｐ＝０として、因子＄Ａ＝Σｐａｐ（Ｐ）のみを考える。
【０２２８】
関数  概して、曲線Ｅ（★Ｆ■）上の関数ｆは、有理関数ｆ（ｘ，ｙ）∈★Ｆ■（ｘ，ｙ）とみなすことができる。任意の点Ｐ＝（ｘ，ｙ）∈Ｅ（★Ｆ■）について、ｆ（Ｐ）＝ｆ（ｘ，ｙ）と定義する。
【０２２９】
関数の因子  ｆを曲線Ｅ（★Ｆ■）上の関数とする。この因子を（ｆ）＝Σｐｏｒｄｐ（ｆ）・Ｐで定義し、（ｆ）で表す。ここで、ｏｒｄｐ（ｆ）は点Ｐにおけるｆの零位数である。例えば、ａｘ＋ｂｙ＋ｃ＝０を、Ｐ１≠±Ｐ２となるような点Ｐ１、Ｐ２∈Ｅ（★Ｆ■）を通る直線とする。この直線は、第３の点Ｐ３∈Ｅ（★Ｆ■）で曲線と交差する。そこで、関数ｆ（ｘ，ｙ）＝ａｘ＋ｂｙ＋ｃは３つの零点Ｐ１、Ｐ２、Ｐ３を持ち、無限遠で位数３の極を持つ。ｆの因子は、（ｆ）＝（Ｐ１）＋（Ｐ２）＋（Ｐ３）−３（Ｏ）となる。
【０２３０】
主因子  ＄Ａを因子とする。（ｆ）＝＄Ａとなるような関数ｆが存在すれば、＄Ａは主因子であるという。因子＄Ａ＝Σｐａｐ（Ｐ）が主因子であるのは、Σｐａｐ＝０および＄Ａ＝ΣｐａｐＰ＝Ｏのときかつそのときに限ることが知られている。第２の和では、曲線上の群作用を使用していることに注意されたい。さらに、主因子＄Ａが与えられた場合、（＄Ａ）＝（ｆ）となるような一意的な関数ｆ（定数倍を除いて）が存在する。
【０２３１】
因子の同値性  ２つの因子＄Ａ、＄Ｂは、差＄Ａ−＄Ｂが主因子であれば、同値であるという。任意の因子＄Ａ＝Σｐａｐ（Ｐ）（Σｐａｐ＝０の場合）は、あるＱ∈Ｅが存在して、＄Ａ'＝（Ｑ）−（Ｏ）の形式の因子に同値であることが知られている。Ｑ＝ΣｐａｐＰであることに注意されたい。
【０２３２】
表記  関数ｆおよび因子＄Ａ＝Σｐａｐ（Ｐ）が与えられたときに、ｆ（＄Ａ）をｆ（＄Ａ）＝Πｐｆ（Ｐ）ａＰと定義する。Σｐａｐ＝０なので、任意のｃ∈★Ｆ■についてｆの代わりにｃｆを使用してもｆ（＄Ａ）は変わらないことに注意されたい。
【０２３３】
これで、２つの点Ｐ、Ｑ∈Ｅ［ｎ］のＷｅｉｌペアリングを説明する準備ができた。＄Ａｐを因子（Ｐ）−（Ｏ）に同値なある因子とする。ｎ＄Ａｐは主因子であることが知られている（これは、明らかに主因子であるｎ（Ｐ）−ｎ（Ｏ）と同値である）。したがって、（ｆｐ）＝ｎ＄Ａｐとなるような関数ｆＰが存在する。＄Ａｑおよびｆｑを同様に定義する。ＰおよびＱのＷｅｉｌペアリングは以下の式で与えられる。
【０２３４】
【数８】
0005933786.tif 000010
この比が矛盾なく定義されている限り（つまり、零による除算が生じない限り）、この比からＰとＱのＷｅｉｌペアリングの値が求められる。この比が不確定の場合、別の因子＄Ａｐ、＄Ａｑを使用して、ｅ（Ｐ，Ｑ）を定義する。Ｐ、Ｑ∈Ｅ（★Ｆ■）ならば、ｅ（Ｐ，Ｑ）∈★Ｆ■である。
【０２３５】
Ｗｅｉｌペアリングが矛盾なく定義されていることを簡単に証明する。つまり、ｅ（Ｐ，Ｑ）の値は、＄Ａｐが（Ｐ）−（Ｏ）に同値である限り因子＄Ａｐの選択とは無関係であり、＄Ａｐから矛盾なく定義された値が得られる。同じことが＄Ａｑについても成り立つ。＄Ａ＾ｐを＄Ａｐと同値な因子とし、ｆ＾ｐを、（ｆ＾ｐ）＝ｎＡ＾ｐとなるような関数とする。すると、ある関数ｇが存在して＄Ａ＾ｐ＝＄Ａｐ＋（ｇ）、ｆ＾ｐ＝ｆｐ・ｇｎとなる。そこで、以下の式が得られた。
【０２３６】
【数９】
0005933786.tif 000011
最後の式は、任意の２つの関数ｆ、ｇについて、ｆ（（ｇ））＝ｇ（（ｆ））が成り立つというＷｅｉｌ相互律と呼ばれる事実から求められる。ゆえに、Ｗｅｉｌペアリングは矛盾なく定義されている。
【０２３７】
事実１０  Ｗｅｉｌペアリングは、以下の特性を持つ。
・  すべてのＰ∈Ｅ［ｎ］について、ｅ（Ｐ，Ｐ）＝１である。
・  双線形：    ｅ（Ｐ１＋Ｐ２，Ｑ）＝ｅ（Ｐ１，Ｑ）・ｅ（Ｐ２，Ｑ）およびｅ（Ｐ，Ｑ１＋Ｑ２）＝ｅ（Ｐ，Ｑ１）・ｅ（Ｐ，Ｑ２）が成り立つ。
【０２３８】
・  Ｐ，Ｑ∈Ｅ［ｎ］が共線形ならば、ｅ（Ｐ，Ｑ）＝１である。同様にｅ（Ｐ，Ｑ）＝ｅ（Ｑ，Ｐ）−１である。
・  ｎ番目の根：すべてのＰ、Ｑ∈Ｅ［ｎ］について、ｅ（Ｐ，Ｑ）ｎ＝１である。
【０２３９】
・  非退化：すべてのすべてのＱ∈Ｅ［ｎ］についてＰがｅ（Ｐ，Ｑ）＝１を満たせば、Ｐ＝Ｏである。
すでに述べたように、ＩＢＥ方式の一実施形態のこの詳細な例では、修正したＷｅｉｌペアリングｅ＾（Ｐ，Ｑ）＝ｅ（Ｐ，φ（Ｑ））を使用し、φはＥの点のなす群上の自己同型写像である。
【０２４０】
Ｔａｔｅペアリング。Ｔａｔｅペアリングは、このシステムの実施形態の必要な特性を有するもう１つの双線形ペアリングである。さまざまなを実施形態において、Ｔａｔｅペアリングのオリジナルの定義を少し修正して本明細書の目的に合わせる。ｆｐおよび＄Ａｐを前のように定義して、２つの点Ｐ、Ｑ∈Ｅ［ｎ］のＴａｔｅペアリングを
【０２４１】
【数１０】
0005933786.tif 000012
として定義する。この定義から、計算可能な双線形ペアリングＴ：Ｅ［ｎ］×Ｅ［ｎ］→★Ｇ２が得られる。
【０２４２】
Ｗｅｉｌペアリングの計算
２つの点Ｐ、Ｑ∈Ｅ［ｎ］が与えられたとして、★ＦｐにおけるＯ（ｌｏｇ  ｐ）の算術演算を使用してｅ（Ｐ，Ｑ）∈★Ｆ＊■を計算する方法を示す。Ｐ≠Ｑと仮定する。次のように進める。２つのランダムな点Ｒ１、Ｒ２∈Ｅ［ｎ］を選ぶ。因子＄Ａｐ＝（Ｐ＋Ｒ１）−（Ｒ１）および＄ＡＱ＝（Ｑ＋Ｒ２）−（Ｒ２）を考える。これらの因子は、（Ｐ）−（Ｏ）および（Ｑ）−（Ｏ）とそれぞれ同値である。そこで、＄Ａｐおよび＄Ａｑを使用して、Ｗｅｉｌペアリングを以下のように計算することが可能である。
【０２４３】
【数１１】
0005933786.tif 000013
この式は、Ｒ１、Ｒ２の選択に関して非常に高い確率で矛盾なく定義されている（失敗の確率は、最大でＯ（ｌｏｇ  ｐ／ｐ）である。ｅ（Ｐ，Ｑ）の計算中に零除算が発生するまれなケースでは、単純に、新しいランダム点Ｒ１、Ｒ２を選んで、この工程を繰り返す。
【０２４４】
ｅ（Ｐ，Ｑ）を評価するために、＄Ａｑで関数ｆｐを評価する方法を示すだけで十分である。ｆｑ（＄Ａｐ）の評価も同様に行われる。倍するのを繰り返してｆｐ（＄Ａｐ）を評価する。正の整数ｂについて、因子を以下のように定義する。
【０２４５】
＄Ａｂ＝ｂ（Ｐ＋Ｒ１）−ｂ（Ｒ１）−（ｂＰ）＋（Ｏ）
これは主因子であり、したがって、（ｆｂ）＝＄Ａｂとなるような関数ｆｂが存在する。（ｆｐ）＝（ｆｎ）であり、したがって、ｆｐ（＄Ａｑ）＝ｆｎ（＄Ａｑ）であることに注意されたい。ｆｎ（＄Ａｑ）を評価する方法を示すので十分である。
【０２４６】
補助定理１１  あるｂ、ｃ＞０についてｆｂ（＄Ａｑ）、ｆｃ（＄Ａｑ）、およびｂＰ、ｃＰ、（ｂ＋ｃ）Ｐが与えられた場合に、ｆｂ＋ｃ（＄Ａｑ）を出力するアルゴリズム＄Ｄが存在する。このアルゴリズムは、★Ｆ■における（少ない）一定数の算術演算を使用するだけである。
【０２４７】
証明  まず、２つの補助線形関数ｇ１、ｇ２を定義する。
１．ａ１ｘ＋ｂ１ｙ＋ｃ１＝０が点ｂＰおよびｃＰを通過する直線とする（ｂ＝ｃであれば、ａ１ｘ＋ｂ１ｙ＋ｃ１＝０をｂＰでＥに接する直線とする）。ｇ１（ｘ，ｙ）＝ａ１ｘ＋ｂ１ｙ＋ｃ１を定義する。
【０２４８】
２．ｘ＋ｃ２＝０を、点（ｂ＋ｃ）Ｐを通過する垂直線とする。ｇ２（ｘ，ｙ）＝ｘ＋ｃ２を定義する。
これらの関数の因子は以下のとおりである。
【０２４９】
（ｇ１）＝（ｂＰ）＋（ｃＰ）＋（−（ｂ＋ｃ）Ｐ）−３（Ｏ）
（ｇ２）＝（（ｂ＋ｃ）Ｐ）＋（−（ｂ＋ｃ）Ｐ）−２（Ｏ）
定義から、以下の式が得られる。
【０２５０】
＄Ａｂ＝ｂ（Ｐ＋Ｒ１）−ｂ（Ｒ１）−（ｂＰ）＋（Ｏ）
＄Ａｃ＝ｃ（Ｐ＋Ｒ１）−ｃ（Ｒ１）−（ｃＰ）＋（Ｏ）
＄Ａ（ｂ＋ｃ）＝（ｂ＋ｃ）（Ｐ＋Ｒ１）−（ｂ＋ｃ）（Ｒ１）−（（ｂ＋ｃ）Ｐ）＋（Ｏ）
そこで、＄Ａ（ｂ＋ｃ）＝＄Ａｂ＋＄Ａｃ＋（ｇ１）−（ｇ２）が得られる。ゆえに、以下の式が得られる。
【０２５１】
【数１２】
0005933786.tif 000014
このことから、ｆｂ＋ｃ（＄Ａｑ）を評価するには、すべてのｉ＝１，２についてｇＩ（＄Ａｑ）を評価し、その結果を式１に差し込むだけで十分である。したがって、ｆｂ（＄Ａｑ）、ｆｃ（＄Ａｑ）、およびｂＰ、ｃＰ、（ｂ＋ｃ）Ｐが与えられると、一定数の算術演算を使用してｆｂ＋ｃ（＄Ａｑ）を計算することが可能である。
【０２５２】
補助定理１１のアルゴリズム＄Ｄの出力を、＄Ｄ（ｆｂ（＄Ａｑ），ｆｃ（＄Ａｑ），ｂＰ，ｃＰ，（ｂ＋ｃ）Ｐ）＝ｆｂ＋ｃ（＄Ａｑ）により表す。次に、以下の標準の倍増手順を使用してｆｐ（＄Ａｑ）＝ｆｎ（＄Ａｑ）を計算することが可能である。ｎ＝ｂｍｂｍ−１．．．ｂ１ｂ０をｎの２進数表現とする、つまり、ｎ＝Σｍｉ＝０ｂＩ２ｉである。
【０２５３】
開始：Ｚ＝Ｏ、Ｖ＝ｆ０（＄Ａｑ）＝１、およびｋ＝０と設定する。
反復：ｉ＝ｍ，ｍ−１，．．．，１，０について以下を実行する。
１：ｂＩ＝１ならば、Ｖ＝＄Ｄ（Ｖ，ｆ１（＄Ａｑ），Ｚ，Ｐ，Ｚ＋Ｐ）を設定し、Ｚ＝Ｚ＋Ｐを設定し、ｋ＝ｋ＋１を設定する。
【０２５４】
２：ｉ＞０ならば、Ｖ＝＄Ｄ（Ｖ，Ｖ，Ｚ，Ｚ，２Ｚ）を設定し、Ｚ＝２Ｚを設定し、ｋ＝２ｋを設定する。
３：各反復の終わりに、ｚ＝ｋＰおよびＶ＝ｆｋ（＄Ａｑ）となることに注意されたい。
【０２５５】
出力：最後の反復の後、ｋ＝ｎとなり、したがって、必要に応じてＶ＝ｆｎ（＄ＡＱ）である。
Ｗｅｉｌペアリングｅ（Ｐ，Ｑ）を評価するために、上記のアルゴリズムを１回実行し、ｆｐ（＄Ａｑ）を計算し、１回実行してｆｑ（＄Ａｐ）を計算する。反復二乗アルゴリズムはｆ１（＄Ａｑ）に評価する必要があることに注意されたい。関数ｆ１（ｘ，ｙ）（その因子は（ｆ１）＝（Ｐ＋Ｒ１）−（Ｒ１）−（Ｐ）＋（Ｏ））は以下のように明示的に書くことが可能なので、この作業は簡単に行える。
【０２５６】
１．ａ１ｘ＋ｂ１ｙ＋ｃ１＝０を、点ＰおよびＲ１を通過する直線とする。関数ｇ１（ｘ，ｙ）＝ａ１ｘ＋ｂ１ｙ＋ｃ１を定義する。
２．ｘ＋ｃ２＝０を、点Ｐ＋Ｒ１を通過する垂直線とする。関数ｇ２（ｘ，ｙ）＝ｘ＋ｃ２を定義する。
【０２５７】
３．関数ｆ１（ｘ，ｙ）は単に、ｆ１（ｘ，ｙ）＝ｇ２（ｘ，ｙ）／ｇ１（ｘ，ｙ）であり、★Ｆ■において容易に評価できる。
【図１】
0005933786.tif 000015
【図２】
0005933786.tif 000016
【図３】
0005933786.tif 000017
【図４】
0005933786.tif 000018
【図５】
0005933786.tif 000019
【図６】
0005933786.tif 000020
【図７】
0005933786.tif 000021
【図８】
0005933786.tif 000022
【図９】
0005933786.tif 000023
【図１０】
0005933786.tif 000024
【図１１】
0005933786.tif 000025
【図１２】
0005933786.tif 000026