(57)【要約】複数の秘密鍵ジェネレータ（「ＰＫＧ」）を含むシステムにおいて送信者と受信者との間でデジタルメッセージをエンコードおよびデコードする方法が提供される。複数のＰＫＧの中には、少なくとも１つのルートＰＫＧと、このルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧと、が含まれている。ルート鍵生成シークレットが選択され、このルート鍵生成シークレットはルートＰＫＧだけに知られている。ルート鍵生成シークレットに基づいてルート鍵生成パラメータが生成される。ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットが選択される。この場合、各下位レベル鍵生成シークレットは、その対応する下位レベルＰＫＧだけに知られている。また、少なくともその対応する下位レベル秘密鍵ジェネレータにおける下位レベル鍵生成シークレットを使用して、ｎ個の下位レベルＰＫＧの各々に、下位レベル鍵生成パラメータが生成される。少なくともルート鍵生成パラメータおよび受信者に関連付けられた受信者同一性情報を使用することにより、メッセージがエンコードされ暗号文が生成される。受信者秘密鍵が、少なくとも、前記ルート鍵生成シークレットと、ｎ個の下位レベル鍵生成シークレットのうちの１または複数と、受信者同一性情報と、に関連付けられるように生成される。少なくとも受信者秘密鍵を使用することにより、暗号文がデコードされメッセージが復元される。
2005521323.tif 000002
【特許請求の範囲】
【請求項１】
送信者と受信者との間でデジタルメッセージをエンコードおよびデコードする方法であって、複数のＰＫＧを含む階層型システムにおいて受信者がルートＰＫＧよりも（ｎ＋１）レベル下にあり、複数のＰＫＧは、少なくとも、ルートＰＫＧと、当該ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧと、を含んでおり、ｎ≧１である方法において、
ルートＰＫＧだけに知られるルート鍵生成シークレットを選択する工程と、
前記ルート鍵生成シークレットに基づいてルート鍵生成パラメータを生成する工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットを選択する工程であって、各下位レベル鍵生成シークレットはその対応する下位レベルＰＫＧだけに知られる、という工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータを生成する工程であって、各下位レベル鍵生成パラメータは少なくともその対応する下位レベルＰＫＧにおける前記下位レベル鍵生成シークレットを使用して生成される、という工程と、
少なくとも前記ルート鍵生成パラメータおよび受信者同一性情報を使用することにより、メッセージをエンコードして暗号文を生成する工程と、
受信者秘密鍵を、少なくとも、前記ルート鍵生成シークレットと、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧに関連付けられたｎ個の前記下位レベル鍵生成シークレットのうちの１または複数と、前記受信者同一性情報とに関連付けられるように生成する工程と、
少なくとも前記受信者秘密鍵を使用することにより、前記暗号文をデコードしてメッセージを復元する工程と、
を備えたことを特徴とする方法。
【請求項２】
前記受信者同一性情報は、受信者に関連付けられた同一性情報ＩＤｚ（ｎ＋１）と、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｚｉと、を有する受信者ＩＤ−タプル（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））を含んでいる
ことを特徴とする請求項１に記載のメッセージをエンコードおよびデコードする方法。
【請求項３】
前記受信者秘密鍵は、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧに関連付けられたｎ個の下位レベル鍵生成シークレットの全てに関連付けられる
ことを特徴とする請求項１に記載のメッセージをエンコードおよびデコードする方法。
【請求項４】
メッセージをエンコードする前記工程は、選択された暗号文攻撃に対して暗号文を保護することを更に含む
ことを特徴とする請求項１に記載のメッセージをエンコードおよびデコードする方法。
【請求項５】
メッセージをエンコードする前記工程は、
対称暗号化スキームにしたがってメッセージを暗号化して、対称暗号を生成する工程と、
一方向暗号化スキームにしたがって前記対称暗号を暗号化して、前記暗号文を生成する工程と、を更に含み、
前記暗号文をデコードする前記工程は、
前記一方向暗号化スキームにしたがって前記暗号文を復号して、前記対称暗号を復元する工程と、
前記対称暗号化スキームにしたがって前記対称暗号を復号して、メッセージを復元する工程と、を更に含む
ことを特徴とする請求項４に記載のメッセージをエンコードおよびデコードする方法。
【請求項６】
複数のＰＫＧを含むシステムにおける送信者と受信者との間でメッセージをエンコードおよびデコードする方法であって、複数のＰＫＧは、ルートＰＫＧと送信者との間の階層中にあるｍ個の下位レベルＰＫＧと、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧと、を含んでおり、ｍ≧１であり、ｎ≧１であり、階層中の複数のＰＫＧのうちの少なくともｌ個は、送信者および受信者の両方に共通の先祖であり、ｌ≧１であり、ＰＫＧｌは、送信者および受信者の両方に共通の先祖ＰＫＧである方法において、
ルートＰＫＧだけに知られるルート鍵生成シークレットを選択する工程と、
前記ルート鍵生成シークレットに基づいてルート鍵生成パラメータを生成する工程と、
ｍ個およびｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットを選択する工程であって、各下位レベル鍵生成シークレットはその対応する下位レベルＰＫＧだけに知られる、という工程と、
ｍ個およびｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータを生成する工程であって、各下位レベル鍵生成パラメータは少なくともその対応する下位レベルＰＫＧにおける下位レベル鍵生成シークレットを使用して生成される、という工程と、
送信者秘密鍵を、少なくとも、送信者同一性情報と、前記ルート鍵生成シークレットと、ルートＰＫＧと送信者との間のｍ個のＰＫＧに関連付けられたｍ個の下位レベル鍵生成シークレットのうちの１または複数と、に関連付けられるように生成する工程と、
受信者秘密鍵を、少なくとも、受信者同一性情報と、前記ルート鍵生成シークレットと、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧに関連付けられたｎ個の下位レベル鍵生成シークレットのうちの１または複数と、に関連付けられるように生成する工程と、
少なくとも、前記受信者同一性情報と、前記送信者秘密鍵と、ルートＰＫＧと送信者との間にあり且つ共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｍ−ｌ＋１）個のＰＫＧに関連付けられるゼロまたはそれ以上の下位レベル鍵生成パラメータと、を使用して、共通の先祖ＰＫＧｌよりも上の（ｌ−１）個のＰＫＧに関連付けられた下位レベル鍵生成パラメータを全く使用しないで、メッセージをエンコードする工程と、
少なくとも、前記受信者秘密鍵と、ルートＰＫＧと受信者との間にあり且つ最下位の共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｎ−ｌ＋１）個のＰＫＧに関連付けられるゼロまたはそれ以上の下位レベル鍵生成パラメータと、を使用して、共通の先祖ＰＫＧｌよりも上の（ｌ−１）個のＰＫＧに関連付けられた下位レベル鍵生成パラメータを全く使用しないで、前記暗号分をデコードする工程と、
を備えたことを特徴とする方法。
【請求項７】
メッセージをエンコードする前記工程は、ルートＰＫＧと送信者との間にあり且つ共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｍ−ｌ＋１）個のＰＫＧに関連付けられた１または複数の下位レベル鍵生成パラメータを使用する工程を更に含み、
メッセージをデコードする前記工程は、ルートＰＫＧと受信者との間にあり且つ最下位の共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｎ−ｌ＋１）個のＰＫＧに関連付けられた１または複数の下位レベル鍵生成パラメータを使用する工程を更に含む
ことを特徴とする請求項６に記載のメッセージをエンコードおよびデコードする方法。
【請求項８】
メッセージをエンコードする前記工程は、ルートＰＫＧと送信者との間にあり且つ共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｍ−ｌ＋１）個のＰＫＧに関連付けられた１または複数の下位レベル鍵生成パラメータを使用する工程を更に含み、
メッセージをデコードする前記工程は、ルートＰＫＧと受信者との間にあり且つ最下位の共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｎ−ｌ＋１）個のＰＫＧに関連付けられたゼロ個の下位レベル鍵生成パラメータを使用する工程を更に含む
ことを特徴とする請求項６に記載のメッセージをエンコードおよびデコードする方法。
【請求項９】
メッセージをエンコードする前記工程は、ルートＰＫＧと送信者との間にあり且つ共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｍ−ｌ＋１）個のＰＫＧに関連付けられたゼロ個の下位レベル鍵生成パラメータを使用する工程を更に含み、
メッセージをデコードする前記工程は、ルートＰＫＧと受信者との間にあり且つ最下位の共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｎ−ｌ＋１）個のＰＫＧに関連付けられた１または複数の下位レベル鍵生成パラメータを使用する工程を更に含む
ことを特徴とする請求項６に記載のメッセージをエンコードおよびデコードする方法。
【請求項１０】
ルートＰＫＧと送信者との間にあり且つ共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｍ−ｌ＋１）個のＰＫＧに関連付けられた全ての下位レベル鍵生成パラメータを使用して、メッセージがエンコードされる
ことを特徴とする請求項６に記載のメッセージをエンコードおよびデコードする方法。
【請求項１１】
ルートＰＫＧと受信者との間にあり且つ共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｎ−ｌ＋１）個のＰＫＧに関連付けられた全ての下位レベル鍵生成パラメータを使用して、メッセージがデコードされる
ことを特徴とする請求項６に記載のメッセージをエンコードおよびデコードする方法。
【請求項１２】
送信者と受信者との間でメッセージのデジタル署名を生成して検証する方法であって、複数のＰＫＧを含む階層型システムにおいて送信者がルートＰＫＧよりも（ｍ＋１）レベル下にあり、複数のＰＫＧは、少なくとも、ルートＰＫＧと、当該ルートＰＫＧと送信者との間の階層中にあるｍ個の下位レベルＰＫＧと、を含んでおり、ｍ≧１である方法において、
ルートＰＫＧだけに知られるルート鍵生成シークレットを選択する工程と、
前記ルート鍵生成シークレットに基づいてルート鍵生成パラメータを生成する工程と、
ｍ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットを生成する工程であって、各下位レベル鍵生成シークレットはその対応する下位レベルＰＫＧだけに知られる、という工程と、
ｍ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータを生成する工程であって、各下位レベル鍵生成パラメータは少なくともその対応する下位レベルＰＫＧにおける下位レベル鍵生成シークレットを使用して生成される、という工程と、
送信者のための送信者秘密鍵を、少なくとも、送信者同一性情報と、前記ルート鍵生成シークレットと、ルートＰＫＧと送信者との間の階層中にあるｍ個の下位レベルＰＫＧに関連付けられたｍ個の位レベル鍵生成シークレットのうちの１または複数と、に関連付けられるように生成する工程と、
少なくとも前記送信者秘密鍵を使用することにより、メッセージに署名をしてデジタル署名を生成する工程と、
少なくとも前記ルート鍵生成パラメータおよび送信者同一性情報を使用して、前記デジタル署名を検証する工程と
を備えたことを特徴とする方法。
【請求項１３】
前記デジタル署名を検証するために、１または複数の下位レベル鍵生成パラメータも使用される
ことを特徴とする請求項１２に記載のデジタル署名を生成して検証する方法。
【請求項１４】
複数のＰＫＧを含むシステム中のあるエンティティのための秘密鍵を生成する方法であって、複数のＰＫＧは、少なくとも、１つのルートＰＫＧと、当該ルートＰＫＧと前記エンティティとの間の階層中にあるｎ個の下位レベルＰＫＧと、を含んでおり、ｎ≧１である方法において、
ルートＰＫＧだけに知られるルート鍵生成シークレットを生成する工程と、
前記ルート鍵生成シークレットに基づいてルート鍵生成パラメータを生成する工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットを生成する工程であって、各下位レベル鍵生成シークレットはその対応する下位レベルＰＫＧだけに知られる、という工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータを生成する工程であって、各下位レベル鍵生成パラメータは少なくともその対応する下位レベルＰＫＧにおける下位レベル鍵生成シークレットを使用して生成される、という工程と、
エンティティのための秘密鍵を、少なくとも、エンティティに関連付けられた同一性情報と、前記ルート鍵生成シークレットと、ルートＰＫＧとエンティティとの間の階層中にあるｎ個の下位レベルＰＫＧに関連付けられたｎ個の前記下位レベル鍵生成シークレットのうちの１または複数と、に関連付けられるように生成する工程と、
前記秘密鍵をエンティティに与える工程と、を含んでいる方法。
【請求項１５】
システム中の受信者ｚのための秘密鍵を生成する方法であって、階層中において受信者ｚはルートＰＫＧよりも（ｎ＋１）レベル下にあり、受信者は、受信者に関連付けられた同一性情報ＩＤｚ（ｎ＋１）と、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｚｉと、を有する受信者ＩＤ−タプル（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））に関連付けられた方法において、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができる
【数１】
2005521323.tif 000060
を選択する工程と、
第１の循環群Γ１のルートジェネレータＰ０を選択する工程と、
ルートＰＫＧに関連付けられ且つルートＰＫＧだけに知られたランダムルート鍵生成シークレットｓ０を選択する工程と、
ルート鍵生成パラメータＱ０＝ｓ０Ｐ０を生成する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができるファンクションＨ１を選択する工程と、
ｎ個の下位レベルＰＫＧの各々に、パブリック要素Ｐｚｉ＝Ｈ１（ＩＤ１，．．．，ＩＤｚｉ）（１≦ｉ≦ｎ）を生成する工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットｓｚｉを選択する工程であって、各下位レベル鍵生成シークレットｓｚｉは、その対応する下位レベルＰＫＧだけに知られる、という工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベルシークレット要素Ｓｚｉを生成する工程であって、Ｓｚｉ＝Ｓｚ（ｉ−１）＋ｓｚ（ｉ−１）Ｐｚｉ（１≦ｉ≦ｎ）であり、ｓｚ０＝ｓ０であり、Ｓｚ０がゼロであるように規定される工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータＱｚｉ＝ｓｚｉＰ０（１≦ｉ≦ｎ）を生成する工程と、
受信者に関連付けられた受信者パブリック要素Ｐｚ（ｎ＋１）＝Ｈ１（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））を生成する工程であって、Ｐｚ（ｎ＋１）は第１の循環群Γ１の１つの要素である、という工程と、
受信者に関連付けられた受信者秘密鍵
【数２】
2005521323.tif 000061
を生成する工程と、
を備えたことを特徴とする方法。
【請求項１６】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項１５に記載の秘密鍵を生成する方法。
【請求項１７】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項１５に記載の秘密鍵を生成する方法。
【請求項１８】
前記
【数３】
2005521323.tif 000062
が許容できるペアリングである
ことを特徴とする請求項１５に記載の秘密鍵を生成する方法。
【請求項１９】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成シークレットｓｚｉが循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｚｉが第１の循環群Γ１の要素であり、
受信者パブリック要素Ｐｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
受信者秘密鍵Ｓｚ（ｎ＋１）が第１の循環群Γ１の要素である
ことを特徴とする請求項１５に記載の秘密鍵を生成する方法。
【請求項２０】
送信者と受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法であって、階層型システムにおいて受信者ｚはルートＰＫＧよりも（ｎ＋１）レベル下にあり、受信者は、受信者に関連付けられた同一性情報ＩＤｚ（ｎ＋１）と、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｚｉと、を有する受信者ＩＤ−タプル（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））に関連付けられた方法において、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができる
【数４】
2005521323.tif 000063
を選択する工程と、
第１の循環群Γ１のルートジェネレータＰ０を選択する工程と、
ルートＰＫＧに関連付けられ且つルートＰＫＧだけに知られたランダムルート鍵生成シークレットｓ０を選択する工程と、
ルート鍵生成パラメータＱ０＝ｓ０Ｐ０を生成する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができる第１のファンクションＨ１を選択する工程と、
第２の循環群Γ２の１つの要素から第２の二進数字列を生成することができる第２のファンクションＨ２を選択する工程と、
ｎ個の下位レベルＰＫＧの各々に、パブリック要素Ｐｚｉ＝Ｈ１（ＩＤ１，．．．，ＩＤｚｉ）（１≦ｉ≦ｎ）を生成する工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットｓｚｉを選択する工程であって、各下位レベル鍵生成シークレットｓｚｉはその対応する下位レベルＰＫＧだけに知られる、という工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベルシークレット要素Ｓｚｉを生成する工程であって、Ｓｚｉ＝Ｓｚ（ｉ−１）＋ｓｚ（ｉ−１）Ｐｚｉ（１≦ｉ≦ｎ）であり、ｓｚ０＝ｓ０であり、Ｓｚ０がゼロであるように規定される工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータＱｚｉ＝ｓｚｉＰ０（１≦ｉ≦ｎ）を生成する工程と、
受信者に関連付けられた受信者パブリック要素Ｐｚ（ｎ＋１）＝Ｈ１（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））を生成する工程と、
受信者に関連付けられた受信者シークレット要素
【数５】
2005521323.tif 000064
を生成する工程と、
少なくとも受信者ＩＤ−タプル（ＩＤ１，．．．，ＩＤｚｉ）およびルート鍵生成パラメータＱ０を使用することにより、メッセージＭをエンコードして暗号文Ｃを生成する工程と、
少なくとも受信者シークレット要素Ｓｚ（ｎ＋１）を使用することにより、前記暗号文ＣをデコードしてメッセージＭを復元する工程と、
を備えたことを特徴とする方法。
【請求項２１】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項２０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項２２】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項２０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項２３】
前記
【数６】
2005521323.tif 000065
は、バイリニアで、非縮退的で、効率的に演算できるペアリングである
ことを特徴とする請求項２０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項２４】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成シークレットｓｚｉが循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｚｉが第１の循環群Γ１の要素であり、
受信者パブリック要素Ｐｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
受信者シークレット要素Ｓｚ（ｎ＋１）が第１の循環群Γ１の要素である
ことを特徴とする請求項２０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項２５】
メッセージＭをエンコードする前記工程は、
ランダムパラメータｒを選択する工程と、
暗号文Ｃ＝［Ｕ０，Ｕ２，．．．．，Ｕｎ＋１，Ｖ］を生成する工程であって、Ｕｉ＝ｒＰｚｉ（ｉ＝０および２≦ｉ≦ｎ＋１）であり、
【数７】
2005521323.tif 000066
であり、
【数８】
2005521323.tif 000067
である工程と、を更に含み、
暗号文Ｃをデコードする前記工程は、
【数９】
2005521323.tif 000068
を使用してメッセージＭを復元する工程を更に含む
ことを特徴とする請求項２０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項２６】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項２５に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項２７】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項２５に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項２８】
前記
【数１０】
2005521323.tif 000069
は、バイリニアで、非縮退的で、効率的に演算できるペアリングである
ことを特徴とする請求項２５に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項２９】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成シークレットｓｚｉが循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｚｉが第１の循環群Γ１の要素であり、
受信者パブリック要素Ｐｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
受信者シークレット要素Ｓｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
ｒが循環群Ｚ／ｑＺの要素であり、
ｇが第２の循環群Γ２の要素である
ことを特徴とする請求項２５に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３０】
第３の二進数字列から循環群Ｚ／ｑＺの整数を生成することができる第３のファンクションＨ３を選択する工程と、
第５の二進数字列から第４の二進数字列を生成することができる第４のファンクションＨ４を選択する工程と、を更に備え、
メッセージＭをエンコードする前記工程は、
ランダム二進数字列σを選択する工程と、
対称暗号化スキームＥを選択する工程と、
ランダム整数ｒ＝Ｈ３（σ，Ｍ，Ｗ）を生成する工程であって、
【数１１】
2005521323.tif 000070
である工程と、
暗号文Ｃ＝［Ｕ０，Ｕ２，．．．．，Ｕｎ＋１，Ｖ，Ｗ］を生成する工程であって、Ｕｉ＝ｒＰｚｉ（ｉ＝０および２≦ｉ≦ｎ＋１）であり、
【数１２】
2005521323.tif 000071
であり、
【数１３】
2005521323.tif 000072
である工程と、を更に含み、
暗号文Ｃをデコードする前記工程は、
【数１４】
2005521323.tif 000073
を使用してランダム二進数字列σを復元する工程と、
【数１５】
2005521323.tif 000074
を使用してメッセージＭを復元する工程と、を更に含む
ことを特徴とする請求項２０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３１】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項３０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３２】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項３０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３３】
前記
【数１６】
2005521323.tif 000075
は、バイリニアで、非縮退的で、効率的に演算できるペアリングである
ことを特徴とする請求項３０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３４】
試験的なランダム整数ｒ'＝Ｈ３（σ，Ｍ，Ｗ）を演算し、Ｕ０＝ｒ'Ｐ０およびＵｉ＝ｒ'Ｐｚｉ（２≦ｉ≦ｎ＋１）を確認することによって、暗号文Ｃの内部整合性を確認する工程を更に含んでいる
ことを特徴とする請求項３０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３５】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成シークレットｓｚｉが循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｚｉが第１の循環群Γ１の要素であり、
受信者パブリック要素Ｐｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
受信者シークレット要素Ｓｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
ｒが循環群Ｚ／ｑＺの要素であり、
ｇが第２の循環群Γ２の要素である
ことを特徴とする請求項３０に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３６】
複数のＰＫＧを含むシステムにおいて送信者ｙと受信者ｚとの間でデジタルメッセージＭをエンコードおよびデコードする方法であって、複数のＰＫＧは、ルートＰＫＧと送信者ｙとの間の階層中にあるｍ個の下位レベルＰＫＧと、ルートＰＫＧと受信者ｚとの間の階層中にあるｎ個の下位レベルＰＫＧと、を含んでおり、ｍ≧１であり、ｎ≧１であり、階層中の複数のＰＫＧのうちの少なくともｌ個は、送信者ｙおよび受信者ｚの両方に共通の先祖であり、ｌ≧１であり、ＰＫＧｌは、送信者および受信者の両方に共通の先祖ＰＫＧであり、送信者ｙは、送信者ｙに関連付けられた同一性情報ＩＤｙ（ｍ＋１）と、ルートＰＫＧと送信者ｙとの間の階層中にあるｍ個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｙｉと、を有する送信者ＩＤ−タプル（ＩＤｙ１，．．．，ＩＤｙ（ｍ＋１））に関連付けられ、受信者は、受信者に関連付けられた同一性情報ＩＤｚ（ｎ＋１）と、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｚｉと、を有する受信者ＩＤ−タプル（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））に関連付けられた方法において、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができる
【数１７】
2005521323.tif 000076
を選択する工程と、
第１の循環群Γ１のルートジェネレータＰ０を選択する工程と、
ルートＰＫＧに関連付けられ且つルートＰＫＧだけに知られたランダムルート鍵生成シークレットｓ０を選択する工程と、
ルート鍵生成パラメータＱ０＝ｓ０Ｐ０を生成する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができる第１のファンクションＨ１を選択する工程と、
第２の循環群Γ２の１つの要素から第２の二進数字列を生成することができる第２のファンクションＨ２を選択する工程と、
ｍ個の下位レベルＰＫＧの各々に、パブリック要素Ｐｙｉ＝Ｈ１（ＩＤｙ１，．．．，ＩＤｙｉ）（１≦ｉ≦ｍ）を生成する工程であって、全てのｉ（≦ｌ）においてＰｙｉ＝Ｐｚｉである工程と、
ｎ個の下位レベルＰＫＧの各々に、パブリック要素Ｐｚｉ＝Ｈ１（ＩＤ１，．．．，ＩＤｚｉ）（１≦ｉ≦ｎ）を生成する工程と、
ｍ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットｓｙｉを選択する工程であって、全てのｉ（≦ｌ）においてｓｙｉ＝ｓｚｉである工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットｓｚｉを選択する工程であって、各下位レベル鍵生成シークレットｓｚｉはその対応する下位レベルＰＫＧだけに知られる、という工程と、
ｍ個の下位レベルＰＫＧの各々に下位レベルシークレット要素Ｓｙｉを生成する工程であって、Ｓｙｉ＝Ｓｙ（ｉ−１）＋ｓｙ（ｉ−１）Ｐｙｉ（１≦ｉ≦ｍ）であり、全てのｉ（≦ｌ）においてＳｙｉ＝Ｓｚｉである工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベルシークレット要素Ｓｚｉを生成する工程であって、Ｓｚｉ＝Ｓｚ（ｉ−１）＋ｓｚ（ｉ−１）Ｐｚｉ（１≦ｉ≦ｎ）であり、ｓｚ０＝ｓ０であり、Ｓｚ０がゼロであるように規定される工程と、
ｍ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータＱｙｉ＝ｓｙｉＰ０（１≦ｉ≦ｍ）を生成する工程であって、全てのｉ（≦ｌ）においてＱｙｉ＝Ｑｚｉである工程と、
ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータＱｚｉ＝ｓｚｉＰ０（１≦ｉ≦ｎ）を生成する工程と、
送信者ｙに関連付けられた送信者パブリック要素Ｐｙ（ｍ＋１）＝Ｈ１（ＩＤｙ１，．．．，ＩＤｙ（ｍ＋１））を生成する工程と、
受信者に関連付けられた受信者パブリック要素Ｐｚ（ｎ＋１）＝Ｈ１（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））を生成する工程と、
送信者に関連付けられた送信者シークレット要素
【数１８】
2005521323.tif 000077
を生成する工程と、
受信者に関連付けられた受信者シークレット要素
【数１９】
2005521323.tif 000078
を生成する工程と、
ｉ＜ｌの下位レベル鍵生成パラメータＱｙｉを使用することなく、少なくともｌ＜ｉ≦ｍの下位レベル鍵生成パラメータＱｙｉおよび送信者シークレット要素Ｓｙ（ｍ＋１）を使用することにより、メッセージＭをエンコードして暗号文Ｃを生成する工程と、
ｉ＜ｌの下位レベル鍵生成パラメータＱｚｉを使用することなく、少なくともｌ＜ｉ≦ｎの下位レベル鍵生成パラメータＱｚｉおよび受信者シークレット要素Ｓｚ（ｎ＋１）を使用することにより、前記暗号文ＣをデコードしてメッセージＭを復元する工程と、を含んでいる、ことを特徴とする方法。
【請求項３７】
メッセージＭをエンコードする前記工程は、下位レベル鍵生成パラメータＱｙｌを使用する工程を更に含んでいる
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３８】
メッセージＭをデコードする前記工程は、下位レベル鍵生成パラメータＱｚｌを使用する工程を更に含んでいる
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項３９】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４０】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項２３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４１】
前記ファンクション
【数２０】
2005521323.tif 000079
は、バイリニアで、非縮退的で、効率的に演算できるペアリングである
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４２】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｚｉが第１の循環群Γ１の要素であり、
各パブリック要素Ｐｙｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成シークレットｓｚｉが循環群Ｚ／ｑＺの要素であり
各下位レベル鍵生成シークレットｓｙｉが循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｚｉが第１の循環群Γ１の要素であり、
各シークレット要素Ｓｙｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｙｉが第１の循環群Γ１の要素であり、
受信者パブリック要素Ｐｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
送信者パブリック要素Ｐｙ（ｍ＋１）が第１の循環群Γ１の要素であり、
受信者シークレット要素Ｓｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
送信者シークレット要素Ｓｙ（ｍ＋１）が第１の循環群Γ１の要素であり、
ｒが循環群Ｚ／ｑＺの要素であり、
ｇが第２の循環群Γ２の要素である
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４３】
メッセージＭをエンコードする前記工程は、
ランダムパラメータｒを選択する工程と、
メッセージＭをエンコードして暗号文Ｃ＝［Ｕ０，Ｕｌ＋１，．．．．，Ｕｎ＋１，Ｖ］を生成する工程であって、Ｕ０＝ｒＰ０であり、Ｕｉ＝ｒＰｚｉ（ｌ＋１≦ｉ≦ｎ＋１）であり、
【数２１】
2005521323.tif 000080
であり、
【数２２】
2005521323.tif 000081
である工程と、を更に含み、
暗号文Ｃをデコードする前記工程は、
【数２３】
2005521323.tif 000082
を使用してメッセージＭを復元する工程を更に含む
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４４】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項４３に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４５】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項４３に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４６】
前記ファンクション
【数２４】
2005521323.tif 000083
は、バイリニアで、非縮退的で、効率的に演算できるペアリングである
ことを特徴とする請求項４３に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４７】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｚｉが第１の循環群Γ１の要素であり、
各パブリック要素Ｐｙｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成シークレットｓｚｉが循環群Ｚ／ｑＺの要素であり
各下位レベル鍵生成シークレットｓｙｉが循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｚｉが第１の循環群Γ１の要素であり、
各シークレット要素Ｓｙｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｙｉが第１の循環群Γ１の要素であり、
受信者パブリック要素Ｐｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
送信者パブリック要素Ｐｙ（ｍ＋１）が第１の循環群Γ１の要素であり、
受信者シークレット要素Ｓｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
送信者シークレット要素Ｓｙ（ｍ＋１）が第１の循環群Γ１の要素であり、
ｒが循環群Ｚ／ｑＺの要素であり、
ｇが第２の循環群Γ２の要素である
ことを特徴とする請求項４３に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４８】
メッセージＭをエンコードする前記工程は、
ランダムパラメータｒを選択する工程と、
メッセージＭをエンコードして暗号文Ｃ＝［Ｕ０，Ｕｌ＋１，．．．．，Ｕｎ＋１，Ｖ］を生成する工程であって、Ｕ０＝ｒＰ０であり、Ｕｌ＋１＝ｒ（Ｐｙ（ｌ＋１）−Ｐｚ（ｌ＋１））であり、Ｕｉ＝ｒＰｚｉ（ｌ＋２≦ｉ≦ｎ）であり、
【数２５】
2005521323.tif 000084
であり、
【数２６】
2005521323.tif 000085
である工程と、を更に含み、
暗号文Ｃをデコードする前記工程は、
【数２７】
2005521323.tif 000086
を使用してメッセージＭを復元する工程を更に含む
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項４９】
メッセージＭをエンコードする前記工程は、
ランダムパラメータｒを選択する工程と、
メッセージＭをエンコードして暗号文Ｃ＝［Ｕ０，Ｕｌ＋２，．．．．，Ｕｎ，Ｖ］を生成する工程であって、Ｕ０＝ｒＰ０であり、Ｕｉ＝ｒＰｚｉ（ｌ＋２≦ｉ≦ｎ）であり、
【数２８】
2005521323.tif 000087
であり、
【数２９】
2005521323.tif 000088
である工程と、を更に含み、
暗号文Ｃをデコードする前記工程は、
【数３０】
2005521323.tif 000089
を使用してメッセージＭを復元する工程を更に含む
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項５０】
第３の二進数字列から循環群Ｚ／ｑＺの整数を生成することができる第３のファンクションＨ３を選択する工程と、
第５の二進数字列から第４の二進数字列を生成することができる第４のファンクションＨ４を選択する工程と、を更に備え、
メッセージＭをエンコードする前記工程は、
ランダム二進数字列σを選択する工程と、
ランダム整数ｒ＝Ｈ３（σ，Ｍ，Ｗ）を演算する工程であって、
【数３１】
2005521323.tif 000090
である工程と、
暗号文Ｃ＝［Ｕ０，Ｕｌ＋１，．．．．，Ｕｎ＋１，Ｖ，Ｗ］を生成する工程であって、Ｕｉ＝ｒＰｚｉ（ｉ＝０およびｌ＋１≦ｉ≦ｎ＋１）であり、
【数３２】
2005521323.tif 000091
であり、
【数３３】
2005521323.tif 000092
である工程と、を更に含み、
暗号文Ｃをデコードする前記工程は、
【数３４】
2005521323.tif 000093
を使用してランダム二進数字列σを復元する工程と、
【数３５】
2005521323.tif 000094
を使用してメッセージＭを復元する工程と、を更に含む
ことを特徴とする請求項３６に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項５１】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項４９に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項５２】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項４９に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項５３】
前記ファンクション
【数３６】
2005521323.tif 000095
は、バイリニアで、非縮退的で、効率的に演算できるペアリングである
ことを特徴とする請求項４９に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項５４】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｚｉが第１の循環群Γ１の要素であり、
各パブリック要素Ｐｙｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成シークレットｓｚｉが循環群Ｚ／ｑＺの要素であり
各下位レベル鍵生成シークレットｓｙｉが循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｚｉが第１の循環群Γ１の要素であり、
各シークレット要素Ｓｙｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｚｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｙｉが第１の循環群Γ１の要素であり、
受信者パブリック要素Ｐｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
送信者パブリック要素Ｐｙ（ｍ＋１）が第１の循環群Γ１の要素であり、
受信者シークレット要素Ｓｚ（ｎ＋１）が第１の循環群Γ１の要素であり、
送信者シークレット要素Ｓｙ（ｍ＋１）が第１の循環群Γ１の要素であり、
ｒが循環群Ｚ／ｑＺの要素であり、
ｇが第２の循環群Γ２の要素である
ことを特徴とする請求項４９に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項５５】
試験的なランダム整数ｒ'＝Ｈ３（σ，Ｍ，Ｗ）を演算し、Ｕ０＝ｒ'Ｐ０およびＵｉ＝ｒ'Ｐｚｉ（ｌ＋１≦ｉ≦ｎ＋１）であることを確認することによって、暗号文Ｃの内部整合性を確認する工程を更に含んでいる
ことを特徴とする請求項４９に記載のデジタルメッセージＭをエンコードおよびデコードする方法。
【請求項５６】
送信者と受信者との間で通信されるデジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法であって、階層型システムにおいて送信者がルートＰＫＧよりも（ｍ＋１）レベル下にあり、送信者は、送信者に関連付けられた同一性情報ＩＤｙ（ｍ＋１）と、ルートＰＫＧと送信者との間の階層中にあるｍ個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｙｉと、を有する送信者ＩＤ−タプル（ＩＤｙ１，．．．，ＩＤｙ（ｍ＋１））に関連付けられている方法において、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができる
【数３７】
2005521323.tif 000096
を選択する工程と、
第１の循環群Γ１のルートジェネレータＰ０を選択する工程と、
ルートＰＫＧに関連付けられ且つルートＰＫＧだけに知られたランダムルート鍵生成シークレットｓ０を選択する工程と、
ルート鍵生成パラメータＱ０＝ｓ０Ｐ０を生成する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができる第１のファンクションＨ１を選択する工程と、
ｍ個の下位レベルＰＫＧの各々に、パブリック要素Ｐｙｉ＝Ｈ１（ＩＤｙ１，．．．，ＩＤｙｉ）（１≦ｉ≦ｍ）を生成する工程と、
ｍ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットｓｙｉを選択する工程であって、各下位レベル鍵生成シークレットｓｙｉはその対応する下位レベルＰＫＧだけに知られる、という工程と、
ｍ個の下位レベルＰＫＧの各々に下位レベルシークレット要素Ｓｙｉを生成する工程であって、Ｓｙｉ＝Ｓｙ（ｉ−１）＋ｓｙ（ｉ−１）Ｐｙｉ（１≦ｉ≦ｍ）である工程と、
ｍ個の下位レベルＰＫＧの各々に下位レベル鍵生成パラメータＱｙｉ＝ｓｙｉＰ０（１≦ｉ≦ｍ）を生成する工程と、
送信者に関連付けられた送信者パブリック要素Ｐｙ（ｍ＋１）＝Ｈ１（ＩＤｙ１，．．．，ＩＤｙ（ｍ＋１））を生成する工程と、
送信者に関連付けられた送信者シークレット要素
【数３８】
2005521323.tif 000097
を生成する工程と、
少なくとも送信者シークレット要素Ｓｙ（ｍ＋１）を使用して、メッセージＭに署名をしてデジタル署名Ｓｉｇを生成する工程と、
少なくともルート鍵生成パラメータＱ０および下位レベル鍵生成パラメータＱｙｉを使用して、前記デジタル署名Ｓｉｇを検証する工程と、
を備えたことを特徴とする方法。
【請求項５７】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項５６に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項５８】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項５６に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項５９】
前記ファンクション
【数３９】
2005521323.tif 000098
は、バイリニアで、非縮退的で、効率的に演算できるペアリングである
ことを特徴とする請求項５６に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項６０】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｙｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成シークレットｓｙｉが循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｙｉが第１の循環群Γ１の要素であり、
各下位レベル鍵生成パラメータＱｙｉが第１の循環群Γ１の要素であり、
送信者パブリック要素Ｐｙ（ｍ＋１）が第１の循環群Γ１の要素であり、
送信者シークレット要素Ｓｙ（ｍ＋１）が第１の循環群Γ１の要素である
ことを特徴とする請求項５６に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項６１】
第２の二進数字列から第１の循環群Γ１の要素を生成することができる第２のファンクションＨ３を選択する工程と、
送信者ｙのための送信者鍵生成シークレットｓｙ（ｍ＋１）を選択する工程であって、送信者鍵生成シークレットｓｙ（ｍ＋１）は送信者だけに知られる、という工程と、
送信者に関連付けられた送信者鍵生成パラメータＱｙ（ｍ＋１）＝ｓｙ（ｍ＋１）Ｐ０を生成する工程と、を更に含み、
メッセージＭに署名する前記工程は、
メッセージ要素ＰＭ＝Ｈ３（ＩＤｙ１，．．．．，ＩＤｙ（ｍ＋１），Ｍ）を生成する工程であって、前記メッセージ要素ＰＭは第１の循環群Γ１の要素である、という工程と、
Ｓｉｇ＝Ｓｙ（ｍ＋１）＋ｓｙ（ｍ＋１）ＰＭを使用してデジタル署名Ｓｉｇを生成する工程と、を更に含み、
デジタル署名Ｓｉｇを検証する前記工程は、
【数４０】
2005521323.tif 000099
を確認する工程を更に含んでいる
ことを特徴とする請求項５６に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項６２】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項６１に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項６３】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項６１に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項６４】
前記ファンクション
【数４１】
2005521323.tif 000100
は、バイリニアで、非縮退的で、効率的に演算できるペアリングである
ことを特徴とする請求項６１に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項６５】
ｓ０が循環群Ｚ／ｑＺの要素であり、
Ｑ０が第１の循環群Γ１の要素であり、
各パブリック要素Ｐｙｉが第１の循環群Γ１の要素であり、
下位レベル鍵生成シークレットｓｙｉおよび送信者鍵生成シークレットｓｙ（ｍ＋１）の各々が循環群Ｚ／ｑＺの要素であり
各シークレット要素Ｓｙｉが第１の循環群Γ１の要素であり、
下位レベル鍵生成パラメータＱｙｉおよび送信者鍵生成パラメータＱｙ（ｍ＋１）の各々が第１の循環群Γ１の要素であり、
送信者パブリック要素Ｐｙ（ｍ＋１）が第１の循環群Γ１の要素であり、
送信者シークレット要素Ｓｙ（ｍ＋１）が第１の循環群Γ１の要素である
ことを特徴とする請求項６１に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この明細書にて、出願人は、３５Ｕ．Ｓ．Ｃ．§１１９（ｅ）の下、２００２年３月２１日に提出された米国仮特許出願６０／３６６，２９２及び２００２年３月２１日に提出された米国仮特許出願６０／３６６，１９６の優先権を主張する。なお、これらの仮特許出願の両方は、これらを参照することにより、本願に組み込まれる。
【０００２】
本発明は、一般に、コンピュータネットワークまたは他のタイプのシステムおよび装置を介した通信の暗号化および保護に関し、特に、通信を暗号化および復号する階層型の同一性に基づくスキームに関する。
【背景技術】
【０００３】
概略的には、同一性（識別子）に基づく暗号システムは、あるエンティティの同一性に関連付けられた情報から当該エンティティの公開鍵が得られる公開鍵暗号システムである。例えば、同一性情報は、個人的な情報（すなわち、名前、住所、電子メールアドレス等）またはコンピュータ情報（すなわち、ＩＰアドレス等）であり得る。しかしながら、同一性情報は、エンティティの同一性に対して厳格に関連付けられる情報だけでなく、日時等の幅広く利用可能な情報をも含み得る。すなわち、同一性情報の概念において重要なのは、エンティティの同一性に対するその厳格な関連性ではなく、エンティティへのメッセージの暗号化を望む誰でもが情報を簡単に利用できることである。
【０００４】
エンティティの秘密鍵は、秘密鍵ジェネレータ（「ＰＫＧ」）として一般に知られる信頼性が高いパーティーまたは論理的プロセスによって生成されて分配される。ＰＫＧは、秘密鍵を生成するためにマスターシークレットを使用する。エンティティの公開鍵はその同一性から得られ得るため、ＡｌｉｃｅがＢｏｂへメッセージを送りたい場合、Ａｌｉｃｅは、Ｂｏｂの公開鍵をデータベースから検索する必要がない。その代わり、ＡｌｉｃｅはＢｏｂの識別情報から直接に鍵を得るだけである。公開鍵のデータベースは不要である。認証局（「ＣＡ」）も不要である。Ｂｏｂの同一性（識別子）がＢｏｂの公開鍵であるため、Ｂｏｂの公開鍵に対してＢｏｂの同一性を「見えなくする」必要がない。
【０００５】
同一性に基づく暗号システムの概念は新しくない。この暗号システムは、スプリンガー出版から出版の、Ａ．Ｓｈａｍｉｒによる「同一性に基づく暗号システムおよび署名スキーム」、暗号システムの進歩−Ｃｒｙｐｔｏ'  １９８４年、コンピュータサイエンス１９６（１９８４）の講義ノート、Ｐ４７−５３で提案された。しかしながら、実用的な同一性に基づく暗号化スキームは、最近まで見当たらなかった。例えば、同一性に基づくスキームは、ｈｔｔｐ：／／ｗｗｗ．ｃｅｓｇ．ｇｏｖ．ｕｋ／ｔｅｃｈｎｏｌｏｇｙ／ｉｄ−ｐｋｃ／ｍｅｄｉａ／ｃｉｒｅｎ．ｐｄｆで利用可能なＣ．Ｃｏｃｋｓの「平方剰余に基づいた同一性に基づく暗号化スキーム」；スプリンガー出版から出版の、Ｄ．Ｂｏｎｅｈ，  Ｍ．Ｆｒａｎｋｌｉｎによる「ウェイルペアリングによる同一性に基づく暗号化」、暗号システムの進歩−Ｃｒｙｐｔｏ  ２００１、コンピュータサイエンス２１３９（２００１）の講義ノート、Ｐ２１３−２２９；ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｓｔａｎｆｏｒｄ．ｅｄｕ／〜ｄａｂｏ／ｐａｐｅｒｓ／ｉｂｅ．ｐｄｆで利用可能なＤ．Ｂｏｎｅｈ，  Ｍ．Ｆｒａｎｋｌｉｎによる「ウェイルペアリングによる同一性に基づく暗号化（拡張版）」、において提案された。Ｃｏｃｋｓのスキームは「平方剰余問題」に基づいており、暗号化および復号がかなり速い（ほぼＲＳＡの速度）が、著しいメッセージ拡張がある（すなわち、暗号文のビット長が何度もプレーンテキストのビット長となる）。Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎのスキームは、秘匿性を「バイリニアなディフィー・ヘルマン問題」に基づいており、超特異な楕円曲線またはアーベル多様体においてウェイルペアリングまたはテートペアリングを使用する際にかなり速く効率が良い。
【０００６】
しかしながら、周知の同一性に基づく暗号化スキームは、それらが階層的ではないという重大な欠点を有している。同一性に基づかない公開鍵暗号化においては、ルートＣＡが他のＣＡのための証明書を発行でき、当該他のＣＡが特定のドメインのユーザのための証明書を発行することができる、というＣＡの階層を有することは可能である。これは、ルートＣＡでの負担を軽減できるため望ましいことである。同一性に基づく暗号化のための実用的な階層型スキームは開発されてこなかった。
【０００７】
理想的には、階層型の同一性に基づく暗号化スキームは、論理的または実体的なＰＫＧから成る階層を含んでいる。例えば、ルートＰＫＧが他のＰＫＧに秘密鍵を発行し、当該他のＰＫＧが特定のドメインのユーザに秘密鍵を発行しても良い。また、送信者がシステム内に全くいない場合であっても、送信者がルートＰＫＧのパブリックパラメータを得た限りにおいては、受信者の公開鍵または下位レベルのパブリックパラメータをオンライン検索することなく、暗号化された通信を送ることもできる。階層型の同一性に基づく暗号化スキームの他の利点は、ダメージ制御である。例えば、ドメインＰＫＧのシークレットの開示は、高位レベルＰＫＧのシークレットを危うくすることはなく、あるいは、危うくされたドメインＰＫＧの直接の子孫ではない任意の他のＰＫＧのシークレットを危うくすることはない。ＣｏｃｋｓおよびＢｏｎｅｈ−Ｆｒａｎｋｌｉｎによって教示されたスキームは、これらの特性を有していない。
【０００８】
安全で且つ実用的な階層型の同一性に基づく暗号化スキームは開発されてこなかった。部分共謀抵抗（ｐａｒｔｉａｌ  ｃｏｌｌｕｓｉｏｎ−ｒｅｓｉｓｔａｎｃｅ）を用いた階層型の同一性に基づく鍵共有化スキームは、スプリンガー出版から出版のＧ．Ｈａｎａｏｋａ，  Ｔ．Ｎｉｓｈｉｏｋａ，  Ｙ．Ｚｈｅｎｇ，  Ｈ．Ｉｍａｉによる「共謀攻撃に抗する効率的な階層型の同一性に基づく鍵共有化方法」、暗号システムの進歩−ＡＳＩＡＣＲＹＰＴ  １９９９、コンピュータサイエンス１７１６（１９９９）の講義ノート、Ｐ３４８−３６２、および、コンピュータジャーナルで出版されているＧ．Ｈａｎａｏｋａ，  Ｔ．Ｎｉｓｈｉｏｋａ，  Ｙ．Ｚｈｅｎｇ，  Ｈ．Ｉｍａｉによる、「メモリサイズが小さく且つ共謀攻撃に対する抵抗が高い階層型の非インタラクティブな鍵共有化スキーム」、において与えられている。また、階層型の同一性に基づく暗号化の入門は、暗号化の進歩−ＥＵＲＯＣＲＹＰＴ  ２００２、コンピュータサイエンスの講義ノート、スプリンガー出版で出ている、Ｊ．Ｈｏｒｗｉｔｚ，  Ｂ．Ｌｙｎｎによる「階層型の同一性に基づく暗号化に関して」において提供された。ＨｏｒｗｉｔｚおよびＬｙｎｎは、第１のレベルで全共謀抵抗（ｔｏｔａｌ  ｃｏｌｌｕｓｉｏｎ−ｒｅｓｉｓｔａｎｃｅ）を用い且つ第２のレベルで部分共謀抵抗（ｐａｒｔｉａｌ  ｃｏｌｌｕｓｉｏｎ−ｒｅｓｉｓｔａｎｃｅ）を用いた２レベルの階層的スキームを提案した（すなわち、ユーザは、自分のドメインＰＫＧのシークレットを取得するために共謀してその後にドメインＰＫＧを装うことができる）。しかしながら、Ｈｏｒｗｉｔｚ−Ｌｙｎｎシステムは、第２のレベルで共謀抵抗を用いるために複雑化し、したがって、スキームは、実用的でもなく、また、安全ともなり得ない。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、安全で且つ実用的な階層型の同一性に基づく暗号化スキームが必要であった。そのため、本発明の目的は、安全で且つ実用的な階層型の同一性に基づく暗号化スキームを提供することである。本発明の他の目的は、安全で且つ実用的な階層型の同一性に基づく署名スキームを提供することである。本発明の更なる目的は、暗号化スキームおよび署名スキームを十分に拡張可能にすることである。本発明の更なる他の目的は、暗号化スキームおよび署名スキームが任意の数のレベルで全共謀抵抗を有し且つ選択された暗号文をランダムオラクルモデルで安全な状態にすることである。
【課題を解決するための手段】
【００１０】
本発明においては、安全で且つ実用的な階層型の同一性に基づく暗号化スキームおよび署名スキームを実行するための方法が提供される。
【００１１】
本発明の一つの特徴によれば、複数の秘密鍵ジェネレータ（「ＰＫＧ」）を含むシステムにおいて送信者と受信者との間でデジタルメッセージをエンコードおよびデコードする方法が提供される。複数のＰＫＧの中には、少なくとも１つのルートＰＫＧと、当該ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧと、が含まれている。ここで、ｎ≧１である。ルート鍵生成シークレットが選択され、このルート鍵生成シークレットはルートＰＫＧにだけ知られている。ルート鍵生成シークレットに基づいて、ルート鍵生成パラメータが生成される。ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットが選択される。この場合、各下位レベル鍵生成シークレットは、その対応する下位レベルＰＫＧだけに知られている。また、少なくともその対応する下位レベル秘密鍵ジェネレータにおける下位レベル鍵生成シークレットを使用して、ｎ個の各下位レベルＰＫＧ毎に、下位レベル鍵生成パラメータも生成される。メッセージがエンコードされ、少なくともルート鍵生成パラメータおよび受信者同一性情報を使用することにより暗号文が生成される。受信者秘密鍵が、少なくとも、前記ルート鍵生成シークレットと、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧに関連付けられたｎ個の下位レベル鍵生成シークレットのうちの１または複数と、受信者同一性情報とに関連付けられるように生成される。少なくとも受信者秘密鍵を使用することにより、暗号文がデコードされてメッセージが復元される。
【００１２】
本発明の他の特徴によれば、複数の秘密鍵ジェネレータ（「ＰＫＧ」）を含むシステムにおいて送信者と受信者との間でデジタルメッセージをエンコードおよびデコードする方法が提供される。複数のＰＫＧの中には、少なくとも１つのルートＰＫＧと、当該ルートＰＫＧと送信者との間の階層中にあるｍ個の下位レベルＰＫＧと、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧと、送信者および受信者の両方に共通の先祖ＰＫＧであるＰＫＧｌと、が含まれている。ここで、ｍ≧１、ｎ≧１である。階層中において、ｍ個の秘密鍵ジェネレータのうちのｌ個は、送信者および受信者の両方に共通する先祖である。ここで、ｌ≧１である。
【００１３】
本発明のこの特徴においては、ルートＰＫＧと送信者との間の階層中にあるｍ個の各下位レベルＰＫＧ毎に、下位レベル鍵生成シークレットが選択される。送信者秘密鍵が、少なくとも、ルート鍵生成シークレットと、ルートＰＫＧと送信者との間の階層中にあるｍ個の下位レベルのＰＫＧに関連付けられたｍ個の下位レベル鍵生成シークレットのうちの１または複数と、送信者同一性情報と、に関連付けられるように生成される。受信者秘密鍵が、少なくとも、ルート鍵生成シークレットと、ルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧに関連付けられたｎ個の下位レベル鍵生成シークレットのうちの１または複数と、受信者同一性情報と、に関連付けられるように生成される。少なくとも、受信者同一性情報と、送信者秘密鍵と、共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｍ−ｌ＋１）個のＰＫＧに関連付けられるゼロまたはそれ以上の下位レベル鍵生成パラメータと、を使用して、共通の先祖ＰＫＧｌよりも上の（ｌ−１）個のＰＫＧに関連付けられる下位レベル鍵生成パラメータは全く使用しないで、メッセージがエンコードされる。少なくとも、送信者同一性情報と、受信者秘密鍵と、共通の先祖ＰＫＧｌのレベルまたはそれよりも下のレベルにある（ｎ−ｌ＋１）個のＰＫＧに関連付けられるゼロまたはそれ以上の下位レベル鍵生成パラメータと、を使用して、共通の先祖ＰＫＧｌよりも上の（ｌ−１）個のＰＫＧに関連付けられる下位レベル鍵生成パラメータは全く使用しないで、メッセージがデコードされる。
【００１４】
本発明の他の特徴によれば、複数のＰＫＧを含むシステムにおいて送信者と受信者との間でメッセージのデジタル署名を生成して検証する方法が提供される。複数のＰＫＧの中には、少なくとも１つのルートＰＫＧと、当該ルートＰＫＧと送信者との間の階層中にあるｎ個の下位レベルＰＫＧと、が含まれている。ここで、ｎ≧１である。ルート鍵生成シークレットが選択され、このルート鍵生成シークレットはルートＰＫＧにだけ知られている。ルート鍵生成シークレットに基づいて、ルート鍵生成パラメータが生成される。ｎ個の下位レベルＰＫＧの各々に下位レベル鍵生成シークレットが選択される。この場合、各下位レベル鍵生成シークレットは、その対応する下位レベルＰＫＧだけに知られている。また、少なくともその対応する下位レベル秘密鍵ジェネレータにおける下位レベル鍵生成シークレットを使用して、ｎ個の各下位レベルＰＫＧ毎に、下位レベル鍵生成パラメータも生成される。送信者のための秘密鍵が、少なくとも、ルート鍵生成シークレットと、送信者同一性情報と、に関連付けられるように生成される。少なくとも送信者秘密鍵を使用することにより、メッセージが署名されてデジタル署名が生成される。少なくともルート鍵生成パラメータおよび送信者同一性情報を使用して、デジタルメッセージが検証される。
【発明を実施するための最良の形態】
【００１５】
本発明の好ましい実施形態の以下の説明においては、添付図面が参照される。
【００１６】
図１は、現在において好ましい本発明の一実施形態に係る、デジタルメッセージをエンコードおよびデコードする方法を表わすフローチャートを示している。
【００１７】
図２は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間でデジタルメッセージをエンコードおよびデコードする方法を表わすフローチャートを示している。
【００１８】
図３は、図２の方法が実行され得る典型的な階層構造を表わすブロック図を示している。
【００１９】
図４は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。
【００２０】
図５は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。
【００２１】
図６は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。
【００２２】
図７は、現在において好ましい本発明の他の実施形態に係る、デジタル署名を生成して検証する方法を表わすフローチャートを示している。
【００２３】
図８は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【００２４】
図９は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【００２５】
本発明の現在の好ましい方法は、安全で且つ実用的な階層型の同一性に基づく暗号化スキーム（「ＨＩＤＥ」）および署名スキーム（「ＨＩＤＳ」）を提供する。階層型スキームは、全面的に拡張可能であり、任意の数のレベルで全共謀抵抗（ｔｏｔａｌ  ｃｏｌｌｕｓｉｏｎ−ｒｅｓｉｓｔａｎｃｅ）を有するとともに、選択された暗号文をランダムオラクルモデルで安全な状態にする。これらの目的は、部分的には、各下位レベルＰＫＧに別個のランダム情報を導入することにより達成される。これらのスキームのうち、直感的に驚くべき態様の１つは、下位レベルＰＫＧが別個のランダム情報を生成する場合であっても、このことが、階層のルートレベルよりも下位のパブリックパラメータを追加することを必要としないという点である。また、下位レベルＰＫＧによって生成されるランダム情報は、暗号化された通信をその下位レベルＰＫＧよりも下のユーザに送るため、その下位レベルＰＫＧよりも下ではないユーザの能力に悪影響を与えない。
【００２６】
本発明のＨＩＤＥスキームおよびＨＩＤＳスキームはそれぞれ、少なくとも１つのルートＰＫＧおよび複数の下位レベルＰＫＧを含むＰＫＧの階層構造を必要とする。階層および下位レベルＰＫＧは、論理的または実体的であっても良い。例えば、１つのエンティティは、ルート鍵生成シークレットと、下位レベルユーザの暗号化鍵または署名鍵がそこから生成される下位レベル鍵生成シークレットと、の両方を生成しても良い。この場合、これらの下位レベルＰＫＧは、別個のエンティティではなく、単なるプロセス、または、論理的な階層中に配置され且つ階層中の子孫ＰＫＧおよびユーザのための鍵を生成するために使用される情報である。あるいは、各下位レベルＰＫＧは、別個のエンティティであっても良い。他の選択肢には、実体的な下位レベルＰＫＧと論理的な下位レベルＰＫＧとの混成が含まれる。説明の目的のため、用語「下位レベルＰＫＧ」は、これらの選択肢のうちの任意の１つを示すべく総称的に使用される。
【００２７】
ここに開示された階層型の同一性に基づく暗号システムにおいて、同一性に基づく公開鍵は、時間に基づいていても良い。例えば、連続する各時間と共に特定の受信者の同一性が変化しても良い。あるいは、受信者は、それ自身の子または子孫として時間を階層中に設定しても良く、また、送信者は、メッセージをエンコードする際に、適当な時間の同一性を使用し得る。どちらにせよ、各鍵は、対応する時間中にだけＢｏｂへのメッセージを暗号化する場合に有効であり得る。
【００２８】
本発明のＨＩＤＥスキームは、一般に、５つのランダム化アルゴリズム、すなわち、ルートセットアップアルゴリズムと、下位レベルセットアップアルゴリズムと、抽出アルゴリズムと、暗号化アルゴリズムと、復号アルゴリズムと、を有している。これらのアルゴリズムのうちの３つは、階層中の関連するエンティティの同一性に依存している。各ユーザは、そのＩＤのタプル（ＩＤ１，．．．．ＩＤｉ）によって規定され得る位置を階層中に有していることが好ましい。階層中におけるユーザの先祖は、ルートＰＫＧおよびそのＩＤタプルが｛（ＩＤ１，．．．．ＩＤｉ）：１≦ｉ≦（ｔ−１）｝であるユーザまたはＰＫＧである。ＩＤタプルは、演算のために、二進数字列として表されることが好ましい。
【００２９】
ルートセットアップアルゴリズムにおいて、ルートＰＫＧは、セキュリティパラメータｋを使用して、パブリックシステムパラメータｐａｒａｍｓおよびルート鍵生成シークレットを生成する。システムパラメータは、メッセージスペースＭおよび暗号文スペースＸの記述を含んでいる。システムパラメータは公然と利用可能であり、一方、ルートＰＫＧだけがルート鍵生成シークレットを知っている。
【００３０】
下位レベルセットアップアルゴリズムにおいて、各下位レベルＰＫＧは、抽出のために、それ自身の下位レベル鍵生成シークレットを生成することが好ましい。また、下位レベルＰＫＧは、各抽出毎に、ランダム一時シークレットを生成しても良い。
【００３１】
抽出アルゴリズムにおいて、ＰＫＧ（ルートＰＫＧであろうと、あるいは、下位レベルＰＫＧであろうとも）は、それ自身の任意の子のための秘密鍵を生成する。当該秘密鍵は、システムパラメータと、生成するＰＫＧの秘密鍵と、任意の他の好ましいシークレット情報と、を使用して生成される。
【００３２】
暗号化アルゴリズムにおいて、送信者は、好ましくは本システムの外側にある幾つかの安全な手段を介して、ルートＰＫＧからシステムパラメータを受信する。送信者が下位レベル鍵生成パラメータを受信する必要はない。送信者は、対象とする受信者のＩＤタプルおよびｐａｒａｍｓを使用して、メッセージＭ∈Ｍをエンコードし暗号文Ｃ∈Ｃを生成する。逆に、復号化アルゴリズムにおいて、受信者は、暗号文Ｃをデコードし、ｐａｒａｍｓおよび受信者の秘密鍵ｄを使用してメッセージＭを復元する。暗号化および復号化は、以下の標準的な一貫性制約を満たすことが好ましい。
∀Ｍ∈Ｍ：復号（ｐａｒａｍｓ、ｄ、Ｃ）＝Ｍ
ここで、Ｃ＝暗号化（ｐａｒａｍｓ、ＩＤ−タプル、Ｍ）である。
【００３３】
ＨＩＤＥスキームと同様に、本発明のＨＩＤＳスキームも、一般に、５つのランダム化アルゴリズム、すなわち、ルートセットアップアルゴリズムと、下位レベルセットアップアルゴリズムと、抽出アルゴリズムと、署名アルゴリズムと、検証アルゴリズムと、を有している。ルートセットアップアルゴリズムの場合、システムパラメータは、署名スペースΣの記述を含むように補足される。下位レベルセットアップアルゴリズムおよび抽出アルゴリズムは、前述したＨＩＤＥの場合と同じであることが好ましい。
【００３４】
署名アルゴリズムにおいて、デジタルメッセージの送信者は、ｐａｒａｍｓおよび送信者の秘密鍵ｄを使用して、メッセージＭ∈Ｍに署名をし署名Ｓ∈Σを生成する。検証アルゴリズムにおいて、署名されたメッセージの受信者は、ｐａｒａｍｓおよび送信者のＩＤ−タプルを使用して、署名Ｓを検証する。検証アルゴリズムは、「有効」または「無効」を出力することが好ましい。署名および検証は、以下の一貫性制約を満たすことが好ましい。
∀Ｍ∈Ｍ：検証（ｐａｒａｍｓ、ＩＤ−タプル、Ｓ）＝「有効」
ここで、Ｓ＝署名（ｐａｒａｍｓ、ｄ、Ｍ）である。
【００３５】
（ＨＩＤＥおよびＨＩＤＳスキームのセキュリティ）
ここでは、ＨＩＤＥおよびＨＩＤＳの両方に関し、本発明を具現化するスキームのセキュリティについて説明する。なお、階層型の同一性に基づかない暗号化において、選択された暗号文のセキュリティの標準的な定義は、同一性に基づくシステムのために強化されなければならない。これは、その選択の任意の同一性（攻撃される特定の同一性以外）に関連付けられた秘密鍵をセキュリティ解析のために敵が取得できることを想定すべきだからである。同じことが、階層型の同一性に基づく暗号化にも当てはまる。したがって、本発明のＨＩＤＥスキームが選択された暗号文の安全性を確保するために、擬似的な攻撃者は、秘密鍵抽出問い合わせを成すことが許容される。また、擬似的な敵は、挑戦されることを望む同一性を選択することが許容される。
【００３６】
また、敵は、そのターゲットの同一性を適応的にあるいは非適応的に選択し得る。そのターゲットを適応的に選択する敵は、最初にハッシュ問い合わせおよび抽出問い合わせを行ない、その後、これらの問い合わせの結果に基づいてそのターゲットを選択する。そのような敵は、攻撃を開始する時には、特定のターゲットのことを考えていないかもしれない。むしろ、敵は、誰かにハッカー行為できれば成功である。一方、非適応的な敵は、ハッシュ問い合わせ及び抽出問い合わせの結果とは無関係に、そのターゲットを選択する。例えば、そのような敵は、個人的な敵をターゲットにするかもしれない。敵は、依然として、ハッシュ問い合わせ及び抽出問い合わせを行なっても良いが、そのターゲット選択は、ターゲットの同一性に厳格に基づいており、問い合わせの結果に基づかない。無論、ターゲットを適応的に選択する敵に対するセキュリティは、より強力であり、したがって、好ましいセキュリティ概念である。しかしながら、本発明におけるＨＩＤＥスキームのセキュリティ解析は、両方のタイプのセキュリティを扱う。
【００３７】
以下のゲームにおいて挑戦者に対して無視できないアドバンテージを有する多項式的に限られた敵Ａがいない場合、ＨＩＤＥスキームは、適応選択された暗号文および適応選択されたターゲット攻撃に対して強秘匿であると言われる。
【００３８】
セットアップ：挑戦者は、セキュリティパラメータｋを取得するとともに、ルートセットアップアルゴリズムを実行する。挑戦者は、その結果として得られるシステムパラメータｐａｒａｍｓを敵に与える。挑戦者は、ルート鍵生成シークレットをそれ自身に対して維持する。
【００３９】
局面１：敵は、問い合わせｑ１，．．．．，ｑｍを発する。ここで、ｑｉは、以下のうちのいずれか１つである。
１．公開鍵問い合わせ（ＩＤ−タプルｉ）：挑戦者は、ＩＤ−タプルｉに基づいてハッシュアルゴリズムを実行し、ＩＤ−タプルｉに対応する公開鍵Ｈ（ＩＤ−タプルｉ）を得る。
２．抽出問い合わせ（ＩＤ−タプルｉ）：挑戦者は、抽出アルゴリズムを実行して、ＩＤ−タプルｉに対応する秘密鍵ｄｉを生成するとともに、そのｄｉを敵に送る。
３．復号問い合わせ（ＩＤ−タプルｉ、Ｃｉ）：挑戦者は、抽出アルゴリズムを実行して、ＩＤ−タプルｉに対応する秘密鍵ｄｉを生成するとともに、復号アルゴリズムを実行して、ｄｉを用いてＣｉを復号し、その結果得られるプレーンテキスト（ｐｌａｉｎｔｅｘｔ）を敵に送る。
これらの問い合わせは、適応的に尋ねられても良い。また、問い合わされたＩＤ−タプルｉは、階層の任意のレベルにある位置に対応し得る。
【００４０】
挑戦：局面１が終了したことを敵が決定すると、敵は、挑戦されることを望む等しい長さの２つのプレーンテキストＭ０、Ｍ１∈Ｍおよび１つのＩＤ−タプルを出力する。唯一の制約は、このＩＤ−タプル及びその先祖のいずれも局面１における秘密鍵抽出問い合わせ中に現れないという点である。挑戦者は、ランダムビットｂ∈｛０，１｝を拾うとともに、Ｃ＝暗号化（ｐａｒａｍｓ、ＩＤ−タプル、Ｍｂ）を設定する。挑戦者は、挑戦としてのＣを敵に送る。
【００４１】
局面２：敵は、更に多くの問い合わせｑｍ＋１，．．．，ｑｎを発する。ここで、ｑｉは、以下のうちのいずれか１つである。
１．公開鍵問い合わせ（ＩＤ−タプルｉ）：挑戦者は、局面１の場合と同様に応答する。
２．抽出問い合わせ（ＩＤ−タプルｉ）：挑戦者は、局面１の場合と同様に応答する。
３．復号問い合わせ（Ｃ，ＩＤ−タプルｉ）：挑戦者は、局面１の場合と同様に応答する。
局面２での問い合わせは、挑戦暗号文Ｃに関連付けられたＩＤ−タプルについて挑戦者が抽出問い合わせを行なえない、あるいは、当該ＩＤ−タプルおよび暗号文Ｃを使用して挑戦者が復号問い合わせを行なえない、という制約を受ける。また、これと同じ制約は、ＩＤ−タプルの全ての先祖にも当てはまる。
【００４２】
推測：敵は、推測ｂ'∈｛０，１｝を出力する。ｂ＝ｂ'の場合に、敵がゲームに勝つ。スキームを攻撃する際の敵のアドバンテージは、｜Ｐｒ［ｂ＝ｂ'］−１／２｜となるように規定される。
【００４３】
後述するゲームにおいて無視できないアドバンテージを有する多項式時間の敵がいない場合、ＨＩＤＥスキームは、一方向暗号化スキームであると言われる。このゲームにおいて、敵Ａは、ランダム公開鍵Ｋｐｕｂと、Ｋｐｕｂを使用してのランダムメッセージＭの暗号化である暗号文Ｃとが与えられるとともに、プレーンテキストのための推測を出力する。ＡがＭを出力する確率がεである場合、敵は、スキームに対してアドバンテージεを有していると言われる。ゲームは、以下のようにして行なわれる。
【００４４】
セットアップ：挑戦者は、セキュリティパラメータｋを取得するとともに、ルートセットアップアルゴリズムを実行する。挑戦者は、その結果として得られるシステムパラメータｐａｒａｍｓを敵に与える。挑戦者は、ルート鍵生成シークレットをそれ自身に対して維持する。
【００４５】
局面１：敵は、前述した選択された暗号文のセキュリティ解析の局面１の場合と同様に、公開鍵および／または抽出問い合わせを行なう。
【００４６】
挑戦：局面１が終了したことを敵が決定すると、敵は、挑戦されることを望む新たなＩＤ−タプルＩＤを出力する。挑戦者は、ランダムＭ∈Ｍを拾うとともに、Ｃ＝暗号化（ｐａｒａｍｓ、ＩＤ−タプル、Ｍ）を設定する。挑戦者は、挑戦としてのＣを敵に送る。
【００４７】
局面２：敵は、ＩＤ及びその先祖以外の同一性について、更に多くの公開鍵問い合わせ及び更に多くの抽出問い合わせを発する。また、挑戦者は、局面１の場合と同様に応答する。
【００４８】
推測：敵は、推測Ｍ'∈Ｍを出力する。Ｍ＝Ｍ'の場合に、敵がゲームに勝つ。スキームを攻撃する際の敵のアドバンテージは、Ｐｒ［Ｍ＝Ｍ'］となるように規定される。
【００４９】
本発明のスキームは、前述した挑戦に対して安全である。また、本発明のＨＩＤＳスキームは、適応的に選択されたメッセージ上に存在する偽造に対して安全である。敵は、たとえ自分の選択のメッセージ上で（適応的に）ターゲットの署名を得た後であっても、ターゲットが予め署名しなかった他のメッセージ上で、そのターゲットの署名を偽造することができない。また、ＨＩＤＳの敵は、公開鍵問い合わせ及び秘密鍵抽出問い合わせをターゲット及びその先祖以外のエンティティ上で行なう能力と、そのターゲットを選択する能力とを有している。ＨＩＤＥと同様に、敵のターゲット選択は、適応的であっても非適応的であっても良い。
【００５０】
（ペアリング）
本発明の現在の好ましいＨＩＤＥスキームおよびＨＩＤＳスキームは、例えば、楕円曲線またはアーベル多様体に関連付けられたウェイルペアリングまたはテートペアリング等のペアリング（組み合わせ）に基づいている。また、これらの方法は、バイリニアなディフィー・ヘルマン問題に基づいている。それらは、好ましくは同じ大きさのプライムオーダーｑから成る２つの循環群Γ１、Γ２を使用する。第１群Γ１は、楕円曲線上またはアーベル多様体上の点から成る群であることが好ましく、Γ１に関する群法則が付加的に書き込まれても良い。第２群Γ２は、有限領域の乗法群であることが好ましく、Γ２に関する群法則が乗法的に書き込まれても良い。しかしながら、本発明と整合性が取れる他のタイプの群をΓ１、Γ２として使用しても良い。
【００５１】
また、この方法は、第１群Γ１のジェネレータＰ０を使用する。また、ペアリングまたはファンクション
【数１】
2005521323.tif 000003
は、第１群Γ１の２つの要素を第２群Γ２の１つの要素に対してマッピングするために与えられる。
【００５２】
【数２】
2005521323.tif 000004
は、３つの条件を満たすことが好ましい。まず第１に、ＱおよびＲがΓ１内にあり且つａ、ｂが整数である場合に、
【数３】
2005521323.tif 000005
となるように、
【数４】
2005521323.tif 000006
はバイリニアであることが好ましい。第２に、マップがΓ１×Γ１における全てのペア（対）をΓ２における同一性に対して送らないように、
【数５】
2005521323.tif 000007
は非縮退的であることが好ましい。第３に、
【数６】
2005521323.tif 000008
は、効率的に演算可能であることが好ましい。これらの３つの条件を満たす
【数７】
2005521323.tif 000009
は、許容できると考えられる。
【００５３】
また、全てのＱ，Ｒ∈Γ１に関して
【数８】
2005521323.tif 000010
となるように、
【数９】
2005521323.tif 000011
は対称的であることが好ましい。しかしながら、対称性は、バイリニア性とΓ１が循環群であるという事実とから直ちに得られる。超特異な楕円曲線またはアーベル多様体に関連付けられたウェイルペアリングおよびテートペアリングは、従来技術に知られた方法にしたがって、そのようなバイリニアなマップを生成するために変更され得る。しかしながら、たとえ第１の循環群Γ１の要素を「点」の群として参照することで、
【数１０】
2005521323.tif 000012
が変更されたウェイルペアリングまたはテートペアリングであることを提案できるとしても、任意の許容できる
【数１１】
2005521323.tif 000013
が働くことが指摘されるべきである。
【００５４】
本発明のＨＩＤＥスキームおよびＨＩＤＳスキームのセキュリティは、主に、バイリニアなディフィー・ヘルマン問題の難しさに基づいている。バイリニアなディフィー・ヘルマン問題は、ランダムに選択されたＰ∈Γ１およびａＰ、ｂＰ、ｃＰ（未知のランダムに選択されたａ、ｂ、ｃ∈Ｚ／ｑＺにおいて）が与えられて
【数１２】
2005521323.tif 000014
を見つける問題である。Γ１においてディフィー・ヘルマン問題を解くことは、
【数１３】
2005521323.tif 000015
であるため、バイリニアなディフィー・ヘルマン問題を解くことである。同様に、Γ２においてディフィー・ヘルマン問題を解くことは、
【数１４】
2005521323.tif 000016
である場合にｇａｂｃ＝（ｇａｂ）ｃであるため、バイリニアなディフィー・ヘルマン問題を解くことである。ここで、
【数１５】
2005521323.tif 000017
であり、また、
【数１６】
2005521323.tif 000018
【００５５】
である。バイリニアなディフィー・ヘルマン問題が難しいため、Γ１またはΓ２のいずれかにおいてディフィー・ヘルマン問題を効率的に解くための周知のアルゴリズムが無いというように、Γ１及びΓ２が選択されるべきである。バイリニアなディフィー・ヘルマン問題が
【数１７】
2005521323.tif 000019
において困難である場合、それは、
【数１８】
2005521323.tif 000020
が非縮退的であるということに従う。
【００５６】
ランダム化アルゴリズムＩΓは、セキュリティパラメータｋ＞０を取得して経時的にｋの多項式を実行し、且つ、好ましくは同じプライムオーダーｑから成る２つの群Γ１及びΓ２の記述と許容できるペアリング
【数１９】
2005521323.tif 000021
の記述とを出力する場合に、バイリニアなディフィー・ヘルマン・ジェネレータである。ＩΓがバイリニアなディフィー・ヘルマンパラメータジェネレータである場合、アルゴリズムＢがバイリニアなディフィー・ヘルマン問題を解く際に有するアドバンテージＡｄνＩΓ（Ｂ）は、アルゴリズムへの入力がΓ１、Γ２、
【数２０】
2005521323.tif 000022
Ｐ、ａＰ、ｂＰ及びｃＰである時にアルゴリズムＢが
【数２１】
2005521323.tif 000023
を出力する確率として規定される。ここで、
【数２２】
2005521323.tif 000024
は、十分に大きいセキュリティパラメータｋにおけるＩΓの出力であり、ＰはΓ１のランダムジェネレータであり、ａ、ｂ及びｃはＺ／ｑＺのランダム要素である。バイリニアなディフィー・ヘルマン問題の根底にある前提は、全ての効率的なアルゴリズムＢにおいてＡｄνＩΓ（Ｂ）が無視できる、ということである。
【００５７】
（ＨＩＤＥスキーム）
ここで、添付図面を参照すると、図１は、現在において好ましい本発明の一実施形態に係るデジタルメッセージの暗号化及び復号の方法を表すフローチャートを示している。この方法は、複数のＰＫＧを有するＨＩＤＥシステム内で行なわれる。これらのＰＫＧは、少なくとも１つのルートＰＫＧと、このルートＰＫＧと受信者との間の階層中にあるｎ個の下位レベルＰＫＧと、を含んでいる。ここで、ｎ≧１である。
【００５８】
ブロック１０２において、ルートＰＫＧは、ルートＰＫＧだけに知られたルート鍵生成シークレットを選択する。ルート鍵生成シークレットは、階層中においてルートＰＫＧよりも下にあるＰＫＧおよび／またはユーザのための秘密鍵を生成するために使用され得る。その後、ブロック１０４において、ルートＰＫＧは、ルート鍵生成シークレットに基づいて、ルート鍵生成パラメータを生成する。ルート鍵生成パラメータは、ルート鍵生成シークレットをマスクするために使用される。ルート鍵生成パラメータは、ルート鍵生成シークレットを危うくすることなく、下位レベルＰＫＧに対して明かされ得る。ブロック１０６において、下位レベルＰＫＧは、下位レベル鍵生成シークレットを選択する。所定の下位レベルＰＫＧに対応する下位レベル鍵生成シークレットは、階層中において対応する下位レベルＰＫＧよりも下にあるＰＫＧおよび／またはユーザのための秘密鍵を生成するために使用され得る。ルート鍵生成シークレットと同様に、各下位レベル鍵生成シークレットは、その対応する下位レベルＰＫＧのみに対して知られている。
【００５９】
ブロック１０８において、下位レベル鍵生成パラメータは、ｎ個の下位レベルＰＫＧの各々に生成される。下位レベル鍵生成パラメータの各々は、その対応する下位レベルＰＫＧにおける下位レベル鍵生成シークレットを少なくとも使用して生成される。ルート鍵生成パラメータと同様に、各下位レベル鍵生成パラメータは、その対応する下位レベル鍵生成シークレットをマスクする。
【００６０】
ブロック１１０において、送信者は、少なくとも受信者に関連付けられた同一性情報およびルート鍵生成パラメータを使用して、メッセージをエンコードし、暗号文を生成する。例えば、メッセージは、ルート鍵生成パラメータおよび受信者の同一性だけを使用してエンコードされ得る。あるいは、デュアルＨＩＤＥスキームに関して後述するように、下位レベル鍵生成パラメータのうちの１つが使用されても良い。ブロック１１２において、下位レベルＰＫＧは、受信者のための秘密鍵を生成する。この場合、秘密鍵は、少なくとも、ルート鍵生成シークレットと、階層中においてルートＰＫＧと受信者との間にあるｎ個の下位レベルＰＫＧに対応するｎ個の下位レベル鍵生成シークレットのうちの１または複数と、受信者の同一性情報と、に関連付けられるように生成される。例えば、ルート鍵生成シークレットおよび受信者の同一性情報に加えて、受信者の秘密鍵も、秘密鍵を受信者に対して発行したＰＫＧの下位レベル鍵生成シークレットに少なくとも関連付けられることが好ましい。あるいは、受信者の秘密鍵は、その先祖ＰＫＧの下位レベル鍵生成シークレットのｎ個の全ておよびルート鍵生成シークレットに関連付けられても良い。ブロック１１４において、受信者は、少なくともその秘密鍵を使用して、暗号文をデコードするとともに、メッセージを復元する。また、受信者は、その秘密鍵を使用してデコードすることに加えて、階層中においてルートＰＫＧと受信者との間にあるｎ個の下位レベルＰＫＧに関連付けられたｎ個の下位レベル鍵生成パラメータを使用することが好ましい。
【００６１】
各下位レベルＰＫＧは、ルートＰＫＧと同様に、鍵生成シークレットを有している。前述したように、下位レベルＰＫＧは、このシークレットを使用して、ルートＰＫＧが行なうのと同様、下位レベルＰＫＧの子の各々に秘密鍵を生成することが好ましい。その結果、子の秘密鍵は、下位レベルＰＫＧの鍵生成シークレットに関連付けられる。このことは、下位レベルＰＫＧがその鍵生成シークレットの変更されたバージョンを使用して後に詳細に述べるようにキーエスクローを規制する目的でそのシークレットを覆い隠す場合であっても、同様である。同時に、下位レベルＰＫＧは、各秘密鍵抽出毎に同じシークレットを常に使用する必要がない。むしろ、ＰＫＧの子の各々毎に、新たな鍵生成シークレットが無作為に生成され、それにより、各子毎に異なる鍵生成パラメータが生成されても良い。
【００６２】
下位レベルＰＫＧは、受信者のための秘密鍵を生成することができる（ブロック１１２）ため、ルートＰＫＧは、それ自身、全ての秘密鍵を生成する必要がない。また、下位レベルＰＫＧは、それ自身の鍵生成シークレットを使用して、その子孫のための秘密鍵を生成するため、ある下位レベル鍵生成シークレットを危うくしても、階層に対する安全性が損なわれるのは、限られた部分だけとなる。下位レベルＰＫＧの破損部分は、階層中の全ての秘密鍵を危うくするのではなく、当該ＰＫＧの秘密鍵および当該ＰＫＧの鍵生成シークレットを使用して生成された秘密鍵（すなわち、危うくされたＰＫＧの直接の階層的子孫であるユーザの秘密鍵）だけを危うくする。
【００６３】
この実施形態の他の利点は、エンコードされたメッセージを受信者に送るために送信者が階層中にいる必要がないという点である。送信者は、受信者に関連付けられた同一性情報と、ルートＰＫＧによって生成されたシステムパラメータと、を単に知っているだけで良い。しかしながら、本発明のＨＩＤＥスキームには、送信者が階層中に位置付けられる時に利用できるようになる特定の更なる利点がある。例えば、送信者および受信者の両方が階層中にいる場合、メッセージ暗号化の効率は、これらの両方の当事者の同一性を使用することにより高められても良い。この種のＨＩＤＥスキームは、送信者および受信者の両方の同一性が暗号化アルゴリズムおよび復号アルゴリズムのための入力として使用されるため、デュアルＨＩＤＥと称される場合がある。以下、図２および図３を参照して、デュアルＨＩＤＥスキームを使用してメッセージをエンコードおよびデコードする方法について説明する。
【００６４】
（デュアルＨＩＤＥ）
図２は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間でデジタルメッセージをエンコードおよびデコードする方法を表わすフローチャートを示している。図３は、この方法を実行することができる一般的な階層構造を表すブロック図を示している。先の実施形態と同様に、この方法は、ルートＰＫＧ３０２と、階層中においてルートＰＫＧ３０２と受信者ｚ３０８との間にあるｎ個の下位レベルＰＫＧ３０４ａ、ｂ、ｄとを少なくとも有するＨＩＤＥシステム内で行なわれる。ここで、ｎ≧１である。また、この実施形態における送信者ｙ３０６は、階層中にいなければならず、また、階層は、ルートＰＫＧ３０２と送信者ｙ３０６との間に、ｍ個の下位レベルＰＫＧ３０４ａ、ｂ、ｃも有している。ここで、ｍ≧１である。ルートＰＫＧ３０２と送信者ｙ３０６との間にあるｍ個のＰＫＧ３０４ａ、ｂ、ｃ、および、ルートＰＫＧ３０２と受信者ｚ３０８との間にあるｎ個の下位レベルＰＫＧ３０４ａ、ｂ、ｄの中には、送信者ｙ３０６および受信者ｚ３０８の両方に共通する先祖であるｌ個のＰＫＧ３０４ａ、ｂがある。ここで、１≦ｌ≦ｍ，ｎである。例えば、これらｌ個の共通の先祖であるＰＫＧ（ＰＫＧｙ１／ＰＫＧｚ１３０４ａおよびＰＫＧｙｌ／ＰＫＧｚｌ３０４ｂ）のうちの２つが図３に示されている。
この実施形態の方法は、ルートＰＫＧ３０２だけに知られたルート鍵生成シークレットをルートＰＫＧ３０２が選択すると、ブロック２０２から開始される。その後、ブロック２０４において、ルートＰＫＧ３０２は、ルート鍵生成シークレットに基づいて、ルート鍵生成パラメータを生成する。ブロック２０６において、下位レベルＰＫＧ３０４ａ−ｄは、下位レベル鍵生成シークレットを選択する。ルート鍵生成シークレットと同様に、各下位レベル鍵生成シークレットは、その対応する下位レベルＰＫＧ３０４ａ−ｄのみに知られている。ブロック２０８において、下位レベル鍵生成パラメータは、ｎ個の下位レベルＰＫＧ３０４ａ−ｄの各々に生成される。各下位レベル鍵生成パラメータは、その対応する下位レベルＰＫＧ３０４ａ−ｄにおける下位レベル鍵生成シークレットを少なくとも使用して生成される。
【００６５】
ブロック２１０において、送信者の親ＰＫＧｙｍ３０４ｃは、送信者ｙ３０６のための秘密鍵を生成する。この場合、秘密鍵は、少なくとも、ルート鍵生成シークレットと、ルートＰＫＧ３０２と送信者ｙ３０６との間にあるｍ個の下位レベルＰＫＧ３０４ａ、ｂ、ｃに対応するｍ個の下位レベル鍵生成シークレットのうちの１または複数と、送信者の同一性情報と、に関連付けられるように生成される。例えば、ルート鍵生成シークレットおよび送信者の同一性情報に加えて、送信者の秘密鍵が、送信者の親ＰＫＧｙｍ３０４ｃの下位レベル鍵生成シークレットに少なくとも関連付けられる。あるいは、送信者の秘密鍵は、その直接の先祖ＰＫＧの下位レベル鍵生成シークレットのｍ個の全ておよびルート鍵生成シークレットに関連付けられても良い。ブロック２１２において、受信者の親ＰＫＧｚｎ３０４ｄは、送信者の親ＰＫＧｙｍ３０４ｃが送信者の秘密鍵を生成するために使用した方法と同様の方法で、受信者ｚのための秘密鍵を生成する。
【００６６】
ブロック２１４において、送信者ｙは、少なくとも、送信者の秘密鍵と、ルートＰＫＧ３０２と送信者ｙ３０６との間にあり且つ送信者ｙ３０６および受信者ｚ３０８の両方に共通する最下位の先祖ＰＫＧ（ＰＫＧｙｌ／ＰＫＧｚｌ３０４ｂ）のレベルまたはそれよりも下のレベルにある（ｍ−ｌ＋１）個のＰＫＧ（すなわち、ＰＫＧｙｌ３０４ｂおよびＰＫＧｙｍ３０４ｃ）に関連付けられた１または複数の下位レベル鍵生成パラメータと、を使用して、メッセージをエンコードして暗号文を生成する。送信者ｙ３０６は、メッセージをエンコードする際、最下位の共通する先祖ＰＫＧ（ＰＫＧｙｌ／ＰＫＧｚｌ３０４ｂ）よりも上にある（ｌ−１）個のＰＫＧ（すなわち、ＰＫＧｙ１３０４ａ）に関連付けられた下位レベル鍵生成パラメータのいずれも使用しないことが好ましい。
【００６７】
その後、ブロック２１６において、受信者ｚ３０８は、少なくとも、受信者の秘密鍵と、ルートＰＫＧ３０２と受信者ｚ３０８との間にあり且つ送信者ｙ３０６および受信者ｚ３０８の両方に共通する最下位の先祖ＰＫＧ（ＰＫＧｙｌ／ＰＫＧｚｌ３０４ｂ）のレベルまたはそれよりも下のレベルにある（ｎ−ｌ＋１）個のＰＫＧ（すなわち、ＰＫＧｚｌ３０４ｂおよびＰＫＧｚｍ３０４ｃ）に関連付けられた１または複数の下位レベル鍵生成パラメータと、を使用して、暗号文をデコードしてメッセージを復元する。受信者ｚ３０８は、メッセージをデコードする際、最下位の共通する先祖ＰＫＧ（ＰＫＧｙｌ／ＰＫＧｚｌ３０４ｂ）よりも上にある（ｌ−１）個のＰＫＧ（すなわち、ＰＫＧｚ１３０４ａ）に関連付けられた下位レベル鍵生成パラメータのいずれも使用しないことが好ましい。
【００６８】
本発明のこのようなデュアルＨＩＤＥの実施形態は、より少ない鍵生成パラメータを使用するだけで済むため、メッセージをより効率的にエンコードおよびデコードするスキームを提供する。例えば、通常のＨＩＤＥスキームにおける復号は、ｎ個の鍵生成パラメータの全てを好ましくは必要とするが、デュアルＨＩＤＥスキームにおける復号は、（ｎ−ｌ＋１）個の鍵生成パラメータだけを好ましくは必要とする。デュアルＨＩＤＥスキームは、ルートＰＫＧのパブリックシステムパラメータを単に得るのではなく、送信者ｙ３０６に、エンコードされたメッセージを受信者ｚ３０８に送る前にその秘密鍵を得ることを要求する。また、デュアルＨＩＤＥスキームによれば、送信者ｙ３０６および受信者ｚ３０８は、後で詳しく述べるように、キーエスクローの範囲を制限することができる。この共有のシークレットは、その最下位の共通する先祖ＰＫＧｙｌ／ＰＫＧｚｌ３０４ｂ以外の第三者に知られない。
【００６９】
（ベーシックＨＩＤＥ）
図４は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。図３に示されるように、受信者ｚ３０８は、階層中においてルートＰＫＧよりも（ｎ＋１）レベル下にあり、ＩＤ−タプル（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））に関連付けられている。受信者のＩＤ−タプルは、受信者に関連付けられた同一性情報ＩＤｚ（ｎ＋１）と、階層中におけるそのｎ個の先祖下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｚｉと、を含んでいる。この方法は、複数の要素から成る第１及び第２の循環群Γ１及びΓ２を生成することにより、ブロック４０２から開始される。ブロック４０４においては、
【数２３】
2005521323.tif 000025
が選択される。この場合、
【数２４】
2005521323.tif 000026
は、それが第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成できるように選択される。
【００７０】
【数２５】
2005521323.tif 000027
は、前述したように、許容できるペアリングであることが好ましい。ブロック４０６において、第１の循環群Γ１のルートジェネレータＰ０が選択される。ブロック４０８においては、ルートＰＫＧ３０２に関連付けられ且つルートＰＫＧ３０２だけに知られたランダムルート鍵生成シークレットｓ０が選択される。ｓ０は、循環群Ｚ／ｑＺの１つの要素であることが好ましい。ブロック４１０においては、ルート鍵生成パラメータＱ０＝ｓ０Ｐ０が生成される。Ｑ０は、第１の循環群Γ１の１つの要素であることが好ましい。ブロック４１２においては、第１のファンクションＨ１が選択される。この場合、ファンクションＨ１は、第１の二進数字列から第１の循環群Γ１の要素を生成できるように選択される。ブロック４１４においては、第２のファンクションＨ２が選択される。この場合、ファンクションＨ２は、第２の循環群Γ２の要素から第２の二進数字列を生成できるように選択される。ブロック４０２からブロック４１４のファンクションは、前述したＨＩＤＥルートセットアップアルゴリズムの一部であり、ほぼ同時に実行されることが好ましい。一例として、Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎに開示されたファンクションのようなファンクションが、Ｈ１およびＨ２として使用され得る。
【００７１】
次の一連のブロック（ブロック４１６から４２４）は、下位レベルセットアップアルゴリズムの一部として実行されるファンクションを示している。ブロック４１６においては、受信者のｎ個の先祖下位レベルＰＫＧの各々に、パブリック要素ＰＺｉが生成される。１≦ｉ≦ｎにおいて各パブリック要素ＰＺｉ＝Ｈ１（ＩＤ１，．．．．，ＩＤＺｉ）は、第１の循環群Γ１の１つの要素であることが好ましい。全てのパブリック要素ＰＺｉの生成が１つのブロックで表わされているが、これらのパブリック要素ＰＺｉの生成は、同時に行なわれることなく経時的に行なわれても良い。
【００７２】
受信者のｎ個の先祖下位レベルＰＫＧ３０４ａ、ｂ、ｄの各々に、下位レベル鍵生成シークレットｓＺｉが選択される（ブロック４１８）。下位レベル鍵生成シークレットｓＺｉは、１≦ｉ≦ｎにおいて循環群Ｚ／ｑＺの要素であることが好ましく、また、各下位レベル鍵生成シークレットｓＺｉは、その対応する下位レベルＰＫＧだけに知られていることが好ましい。この場合も同様に、全ての下位レベル鍵生成シークレットｓＺｉの選択が１つのブロックで表わされているが、これらの下位レベル鍵生成シークレットｓＺｉの選択は、同時に行なわれることなく経時的に行なわれても良い。
【００７３】
送信者のｎ個の先祖下位レベルＰＫＧの各々に、下位レベルシークレット要素ＳＺｉが生成される（ブロック４２０）。１≦ｉ≦ｎにおいて各下位レベルシークレット要素ＳＺｉ＝ＳＺ（ｉ−１）＋ｓｚ（ｉ−１）ＰＺｉは、第１の循環群Γ１の要素であることが好ましい。パブリック要素ＰＺｉおよびシークレットｓＺｉと同様に、全てのシークレット要素ＳＺｉの生成が１つのブロックで表わされているが、これらのシークレット要素ＳＺｉの生成は、同時に行なわれることなく経時的に行なわれても良い。これらの繰り返される鍵生成プロセスのため、Ｓ０は、Γ１の同一性要素として規定される。
【００７４】
また、受信者のｎ個の先祖下位レベルＰＫＧの各々に、下位レベル鍵生成パラメータＱＺｉも生成される（ブロック４２２）。１≦ｉ≦ｎにおいて各鍵生成パラメータＱＺｉ＝ｓＺｉＰ０は、第１の循環群Γ１の要素であることが好ましい。全ての鍵生成パラメータＱＺｉの生成が１つのブロックで表わされているが、これらの鍵生成パラメータＱＺｉの生成は、同時に行なわれることなく経時的に行なわれても良い。
【００７５】
次の２つのブロック（ブロック４２４、４２６）のファンクションは、前述した抽出アルゴリズムの一部として実行される。ブロック４２４においては、受信者ｚに関連付けられた受信者パブリック要素ＰＺ（ｎ＋１）が生成される。受信者パブリック要素ＰＺ（ｎ＋１）＝Ｈ１（ＩＤＺ１，．．．．，ＩＤＺ（ｎ＋１））は、第１の循環群Γ１の要素であることが好ましい。その後、ブロック４２６において、受信者ｚに関連付けられた受信者シークレット要素ＳＺ（ｎ＋１）が生成される。また、受信者シークレット要素
【数２６】
2005521323.tif 000028
も、第１の循環群Γ１の要素であることが好ましい。
【００７６】
便宜上、第１のファンクションＨ１は、随意的に、反復関数となるように選択されても良い。この場合、例えば、Ｈ１（ＩＤ１，．．．，ＩＤｚｉ）としてではなく、Ｈ１（Ｐｚ（ｉ−１），ＩＤｚｉ）として、パブリックポイントＰｉが演算され得る。
【００７７】
図４に示される最後の２つのブロック（ブロック４２８、４３０）は、前述した暗号化アルゴリズムおよび復号アルゴリズムを表わしている。ブロック４２８においては、暗号文Ｃを生成するためにメッセージＭがエンコードされる。このコード化は、少なくともルート鍵生成パラメータＱ０およびＩＤ−タプル（ＩＤｚ１，．．．，ＩＤｚ（ｎ＋１））を使用することが好ましい。その後、ブロック４３０において、暗号文Ｃがデコードされ、メッセージＭが復元される。復号は、１≦ｉ≦ｎにおける下位レベル鍵生成パラメータＱｚｉおよび受信者シークレット要素Ｓｚ（ｎ＋１）を少なくとも使用することが好ましい。
【００７８】
図４に示されるブロックは、その全てが順序通り行なわれる必要はない。例えば、受信者の同一性を知っている送信者は、受信者がその秘密鍵を得る前に、受信者への通信を暗号化しても良い。
【００７９】
次に、図５および図６を参照しながら、メッセージＭおよび暗号文Ｃのコード化および復号における前述したパラメータおよび要素の特定の用法について説明する。図５は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。ベーシックＨＩＤＥと呼ばれるこのスキームにおいて、ルートセットアップアルゴリズム、下位レベルセットアップアルゴリズム及び抽出アルゴリズムは、図４のブロック４０２から４２６で示された実施形態における場合と同じである。図５のフローチャートは、暗号化アルゴリズムおよび復号アルゴリズムを示しており、ブロック５２８ａにおいてランダム暗号化パラメータｒを選択することによって開始される。ｒは、循環群Ｚ／ｑＺの整数であることが好ましい。その後、ブロック５２８ｂにおいて、式Ｃ＝［Ｕ０，Ｕ２，．．．．，Ｕｎ＋１，Ｖ］を使用して、暗号文Ｃが生成される。暗号文Ｃは、階層中における受信者の位置に関連する要素Ｕｉ＝ｒＰｚｉ（ｉ＝０および２≦ｉ≦ｎ＋１）を含んでいる。暗号文Ｃの他の部分は、暗号化された形式の実際のメッセージ、
【数２７】
2005521323.tif 000029
である。ここで、
【数２８】
2005521323.tif 000030
である。要素ｇは、第２の循環群Γ２の構成要素であることが好ましい。メッセージは、エンコードされた後、ベーシックＨＩＤＥ復号アルゴリズムにしたがってデコードされ得る。この復号アルゴリズムにおいて、メッセージＭは、式
【数２９】
2005521323.tif 000031
を使用して暗号文Ｃから復元される（ブロック５３０）。
【００８０】
（完全ＨＩＤＥ）
選択された暗号文の攻撃に対して安全な一方向暗号化スキームを作成する周知の方法を使用して、ベーシックＨＩＤＥスキームは、選択された暗号文がランダムオラクルモデルで安全な完全ＨＩＤＥスキームに変換され得る。以下、図６を参照しながら、選択された暗号文にとって安全な完全ＨＩＤＥについて説明する。
【００８１】
図６は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。本発明のこの実施形態におけるルートセットアップアルゴリズム、下位レベルセットアップアルゴリズム及び抽出アルゴリズムは、この実施形態のルートセットアップアルゴリズムが２つの付加的なファンクションを必要とする点を除き、図４を参照して説明された実施形態の場合と同じである。したがって、図６のフローチャートは、付加的ファンクション（ブロック６１５ａ、６１５ｂ）を選択することにより開始され、暗号化アルゴリズムおよび復号アルゴリズム（ブロック６２８ａから６３０ｄ）に続く。
【００８２】
ルートセットアップアルゴリズムは、第３のファンクションＨ３（ブロック６１５ａ）および第４のファンクションＨ４（ブロック６１５ｂ）を選択することによって終了する。第３のファンクションＨ３は、２つの二進数字列から循環群Ｚ／ｑＺの整数を生成できることが好ましい。第４のファンクションＨ４は、他の二進数字列から１つの二進数字列を生成できることが好ましい。
【００８３】
暗号化アルゴリズムは、ランダム二進数字列σの選択を示すブロック６２８ａから開始される。その後、ブロック６２８ｂに示されるように、ランダム二進数字列σは、ランダム整数ｒ＝Ｈ３（σ，Ｍ，Ｗ）を生成するために使用される。ここで、Ｗは、実際のメッセージＭの対称暗号である。この暗号は、対称暗号化アルゴリズムＥと暗号化鍵としてのＨ４（σ）とを使用して生成されることが好ましい。したがって、
【数３０】
2005521323.tif 000032
となる。ブロック６２８ｃにおいては、暗号文Ｃ＝［Ｕ０，Ｕ２，．．．．，Ｕｎ＋１，Ｖ，Ｗ］が生成される。暗号文Ｃは、階層中における受信者の位置に関連する要素Ｕｉ＝ｒＰｚｉ（ｉ＝０および２≦ｉ≦ｎ＋１）を含んでいる。暗号文Ｃの第２の部分は、暗号化された形式のランダム二進数字列σ
【数３１】
2005521323.tif 000033
である。ここで、
【数３２】
2005521323.tif 000034
である。要素ｇは、第２の循環群Γ２の構成要素であることが好ましい。暗号文Ｃの第３の部分は、Ｗ、すなわち、前述したように対称的に暗号化された形式の実際のメッセージである。
【００８４】
復号アルゴリズムは、ランダム二進数字列σの復元を示すブロック６３０ａから開始される。ランダム二進数字列σは、式
【数３３】
2005521323.tif 000035
を使用して復元される。その後、式
【数３４】
2005521323.tif 000036
を使用して、暗号文ＣからメッセージＭが復元される（ブロック６３０ｂ）。暗号文は、随意的に、内部整合性がチェックされても良い。例えば、ブロック６３０ｃに示されるように、試験的なランダム整数ｒ'＝Ｈ３（σ，Ｍ，Ｗ）が生成されても良い。その後、試験的なランダム整数ｒ'は、ブロック６３０ｄにおいて、Ｕ０＝ｒ'Ｐ０およびＵｉ＝ｒ'Ｐｚｉ（２≦ｉ≦ｎ＋１）であることを確かめるために使用され得る。Ｕ０＝ｒ'Ｐ０およびＵｉ＝ｒ'Ｐｚｉ（２≦ｉ≦ｎ＋１）である場合、暗号文Ｃは真正であると見なされる。
【００８５】
（デュアルベーシックＨＩＤＥおよびデュアル完全ＨＩＤＥ）
図２および図３を参照して説明したデュアルＨＩＤＥの概念は、ベーシックＨＩＤＥスキームおよび完全ＨＩＤＥスキームに適用され得る。図３に示されるように、送信者および受信者の両者が階層構造内にある場合、デュアルＨＩＤＥによって、これらの両者は、自分達の暗号化された通信の効率および安全性を向上させることができる。デュアルＨＩＤＥをベーシックＨＩＤＥスキームおよび完全ＨＩＤＥスキームに適用するには、付加的な情報を決定する必要がある。これらの情報の殆どは、前述した下位レベルセットアップアルゴリズムによって決定される。例えば、パブリック要素Ｐｙｉ、下位レベル鍵生成シークレットｓｙｉ、下位レベルシークレット要素Ｓｙｉ、下位レベル鍵生成パラメータＱｙｉは、送信者のｍ個の先祖下位レベルＰＫＧのために決定されなければならない。しかしながら、送信者ｙおよび受信者ｚの両者に共通の先祖である下位レベルＰＫＧにおいては、送信者ｙおよび受信者ｚの両方を解析する目的のため、これらのパラメータが同じであることが好ましい（すなわち、全てのｉ≦ｌにおいて、Ｐｙｉ＝Ｐｚｉ，ｓｙｉ＝ｓｚｉ，Ｓｙｉ＝Ｓｚｉ，Ｑｙｉ＝Ｑｚｉ）。また、デュアルＨＩＤＥでは、受信者に関してこれらのパラメータを決定する前述した方法と同じ方法を使用して、送信者のための送信者パブリック要素Ｐｙ（ｍ＋１）および送信者シークレット要素Ｓｙ（ｍ＋１）を決定する必要もある。
【００８６】
これらの付加的なパラメータが与えられると、ｉ＜ｌの下位レベル鍵生成パラメータＱｙｉを使用するのではなく、送信者シークレット要素Ｓｙ（ｍ＋１）およびｉ≧ｌの下位レベル鍵生成パラメータＱｙｉを使用することにより、デュアルＨＩＤＥの原理にしたがって、メッセージＭがエンコードされ暗号文Ｃが生成され得る。同様に、ｉ＜ｌの下位レベル鍵生成パラメータＱｚｉを使用するのではなく、受信者シークレット要素Ｓｚ（ｍ＋１）およびｉ≧ｌの下位レベル鍵生成パラメータＱｚｉを使用することにより、暗号文ＣがデコードされメッセージＭが復元され得る。
【００８７】
例えば、ベーシックＨＩＤＥスキーム（図４および図５）において、デュアルＨＩＤＥを適用すると、暗号文Ｃ＝［Ｕ０，Ｕｌ＋１，．．．．，Ｕｎ＋１，Ｖ］を生成するためのメッセージＭのコード化が変わる。ここで、Ｕｉ＝ｒＰｚｉ（ｉ＝０，ｌ＋１≦ｉ≦ｎ＋１）であり、
【数３５】
2005521323.tif 000037
であり、また、
【数３６】
2005521323.tif 000038
である。要素Ｕｉは、前述した方法と同じ方法で計算されるが、それらのうち必要なのは僅かである。しかしながら、デュアルベーシックＨＩＤＥにおいて、送信者ｙは、前述したようにｇを生成するために必要な数よりも多い数の鍵生成パラメータＱｙｉを使用してｇｙｌを生成する必要がある。これは、送信者の同一性が暗号化アルゴリズム中に組み込まれるためである。
【００８８】
復号アルゴリズムの効率の向上は更に劇的である。メッセージＭは、
【数３７】
2005521323.tif 000039
を使用して復元される。この場合も同様に、必要なＵｉパラメータは僅かである。同様に、受信者は、デュアルＨＩＤＥの場合、他の方法において必要であろうよりも少ない鍵生成パラメータＱｚｉを必要とする。
【００８９】
デュアル完全ＨＩＤＥスキームを生成するために、完全ＨＩＤＥもまた変更され得る。暗号化アルゴリズムにおける暗号文Ｃの生成は、Ｃ＝［Ｕ０，Ｕｌ＋１，．．．．，Ｕｎ＋１，Ｖ，Ｗ］となるように変更される。ここで、Ｕｉ＝ｒＰｚｉ（ｉ＝０，ｌ＋１≦ｉ≦ｎ＋１）である。Ｗおよびｒのパラメータは、依然として同じ方法で生成される。
【数３８】
2005521323.tif 000040
また、
【数３９】
2005521323.tif 000041
におけるｇｙｌパラメータは、
【数４０】
2005521323.tif 000042
を使用して生成される。
【００９０】
また、複号アルゴリズムも、デュアル完全ＨＩＤＥスキームにおいて変更される。ランダム二進数字列σは、
【数４１】
2005521323.tif 000043
を使用して復元される。そうでなければ、メッセージＭの復元は変わらない。
【００９１】
送信者ｙおよび受信者ｚの両者に共通する最下位先祖ＰＫＧとしてＰＫＧｌ３０４ｂを使用して、以上のデュアルＨＩＤＥスキームを説明してきたが、ＰＫＧｌ３０４ｂは、任意の共通の先祖ＰＫＧであり得る。暗号化アルゴリズムおよび復号アルゴリズムは同じである。しかしながら、効率を最大にするためには、ＰＫＧｌ３０４ｂは、最下位の共通の先祖ＰＫＧであることが好ましい。
【００９２】
また、本発明のデュアルＨＩＤＥスキームは、効率を高めることに加え、キーエスクローを規制することにより、安全性も高める。前述したベーシックＨＩＤＥスキームおよび完全ＨＩＤＥスキームにおいて、受信者の直接の先祖ＰＫＧの全ては、受信者へのメッセージを復号することができる。しかしながら、デュアルＨＩＤＥスキームは、ＰＫＧｌ−１よりも上の共通の先祖ＰＫＧに知られていないＰＫＧｌ−１（ＰＫＧｌの直接の親）の鍵生成シークレットを組み込んでいるため、これらの共通の先祖ＰＫＧは、送信者ｙと受信者ｚとの間でメッセージを復号することができない。もっとも、ＰＫＧｌ３０４ｂの直接の親は、それ自身の鍵生成シークレットを知っているため、メッセージを復号することができる。
【００９３】
また、キーエスクローは、ＰＫＧｌの直接の親でさえも送信者ｙと受信者ｚとの間でメッセージを復号することができないように制限されても良い。これは、送信者ｙおよび受信者ｚのために秘密鍵（あるいは、送信者ｙおよび受信者ｚの先祖であるＰＫＧｌの子のための秘密鍵）を生成するプロセスにおいてＰＫＧｌの秘密鍵を見えなくするとによって達成され得る。例えば、ＰＫＧｌ３０４ｂは、幾つかのランダムｂ∈Ｚ／ｑＺにおいてＳ'ｌ：＝Ｓｌ＋ｂＰｌおよびＱ'ｌ−１：＝Ｑｌ−１＋ｂＰ０を設定することにより、その秘密鍵を簡単に変え得る。新たな秘密鍵Ｓ'ｌは、同様に効果的であるが、ＰＫＧｌの直接の親に知られていない。したがって、ＰＫＧｌよりも上のＰＫＧにおいて、暗号化された受信者ｚへのメッセージを復号できるものは無い。より具体的には、ＰＫＧｌのドメイン内にある受信者ｚの先祖だけが、受信者ｚへのメッセージを復号することができる。
【００９４】
Ｓ'ｌ：＝Ｓｌ＋ｂＰｌおよびＱ'ｌ−１：＝Ｑｌ−１＋ｂＰ０を設定することによってＰＫＧｌ３０４ｂがその秘密鍵を変える場合、新たな秘密鍵は、依然として、ＰＫＧｌ−１の鍵生成シークレットｓｌ−１に関連付けられる。これは、ｓｌ−１を使用してＰＫＧｌ−１により生成される秘密鍵から新たな秘密鍵が得られるためである。一般に、ここで説明した全てのスキームにおいて、ユーザまたはＰＫＧは、ｂｉ（１≦ｉ≦ｎ）のための値を選択し且つ
【数４２】
2005521323.tif 000044
およびＱ'ｚｉ：＝Ｑｚｉ＋ｂｉＰ０（１≦ｉ≦ｎ）を設定することにより、それ自身のシークレット要素Ｓｚ（ｎ＋１）および鍵生成パラメータＱｚｉ（１≦ｉ≦ｎ）を変更し得る。しかしながら、本発明の目的として、この新たな秘密鍵は、依然として、オリジナルの秘密鍵に関連付けられていると見なされ、そのため、鍵生成シークレットｓｚｉの初期値に関連付けられる。
【００９５】
（暗号化および復号の効率が更に高いデュアルＨＩＤＥスキーム）
前述したデュアルＨＩＤＥスキームにおいては、復号子（ｄｅｃｒｙｐｔｅｒ）が演算しなければならないペアリングの値の数を増やすことなく、暗号化子（ｅｎｃｒｙｐｔｅｒ）が演算しなければならないペアリングの値の数を１だけ減らすことができる。例えば、前述したデュアルベーシックＨＩＤＥ暗号化アルゴリズムは、
【数４３】
2005521323.tif 000045
となるように変更され得る。ここで、
【数４４】
2005521323.tif 000046
である。暗号文がＣ＝［Ｕ０，Ｕｌ＋１，Ｋ，Ｕｎ＋１，Ｖ］として表わされる場合、暗号文は、
【数４５】
2005521323.tif 000047
を使用して復号化され得る。
【００９６】
同様に、暗号化子が演算しなければならない値の数を増やすことなく、復号子が演算しなければならないペアリングの値の数を１だけ減らすことができる。例えば、デュアルベーシックＨＩＤＥ暗号化アルゴリズムは、暗号文Ｃが、
【数４６】
2005521323.tif 000048
となるように変更されても良い。ここで、
【数４７】
2005521323.tif 000049
である。暗号文がＣ＝［Ｕ０，Ｕｌ＋２，Ｋ，Ｕｎ，Ｖ］として表わされる場合、暗号文は、
【数４８】
2005521323.tif 000050
を使用して復号され得る。
【００９７】
（認証された下位レベルルートＰＫＧ）
前述したデュアルＨＩＤＥスキームの能力は、認証された下位レベルルートＰＫＧを生成することにより、階層の外側のメッセージ送信者へと広げられ得る。下位レベルＰＫＧを「認証する」ため、ルートＰＫＧは、ランダムメッセージＭ'等の付加的なパラメータを発行し得る。その後、下位レベルＰＫＧは、Ｍ'に「署名をして」、署名Ｓｉｇ＝Ｓｚｌ＋ｓｚｌＰＭ'を生成する。ここで、Ｓｌは下位レベルＰＫＧの秘密鍵であり、ｓｌはその下位レベル鍵生成シークレットである。下位レベルＰＫＧもＱｉ（１≦ｉ≦ｔ）を発行する。
【００９８】
認証された下位レベルルートＰＫＧを利用して、階層外の送信者は、受信者のｎ個の全ての先祖ＰＫＧについてパブリック要素Ｐｚｉを演算することなく、暗号化されたメッセージを受信者ｚに送信することができる。むしろ、送信者は、認証された下位レベルルートＰＫＧのためのパラメータを使用して、メッセージを更に効率的に暗号化することができる。特に、送信者は、Ｐｚｉ＝Ｈ１（ＩＤ１，．．．．．，ＩＤｚｉ）∈Γ１（ｌ＋１≦ｉ≦ｎ＋１）を演算する。その後、送信者は、ランダムｒ∈Ｚ／ｑＺを選択するとともに、暗号文
【数４９】
2005521323.tif 000051
を生成する。ここで、
【数５０】
2005521323.tif 000052
である。受信された暗号文がＣ＝［Ｕ０，Ｕｌ＋１，．．．．，Ｕｎ＋１，Ｖ］であると、受信者は、暗号文を復号して、メッセージ
【数５１】
2005521323.tif 000053
を復元する。ここで、Ｓｚ（ｎ＋１）は、受信者の秘密鍵である。
【００９９】
（分散型ＰＫＧ）
前述したＨＩＤＥスキームの鍵生成シークレットを更に保護するため、及び、不正なＰＫＧに対して頑強なスキームを形成するため、鍵生成シークレットおよび秘密鍵は、閾値暗号法の周知の技術を使用して分散され得る。
【０１００】
（更に効率的な暗号化）
前述したＨＩＤＥスキームにおける暗号化の効率は、階層の最も高い２つのレベルを合併して１つのルートＰＫＧを生成することにより高められ得る。この場合、
【数５２】
2005521323.tif 000054
は、システムパラメータ中に含まれる。これにより、このペアリングの値を演算する暗号化子のタスクが節約される。しかしながら、復号子は、１つ余分なペアリングを演算しなければならない（ツリーのレベルが１つ下がるため）。
【０１０１】
（ＨＩＤＳスキーム）
ここで、本発明の署名スキームすなわちＨＩＤＳスキームについて考えると、図７は、現在において好ましい本発明の他の実施形態に係る、デジタル署名を生成して検証する方法を表わすフローチャートを示している。この方法は、複数のＰＫＧを有するＨＩＤＳシステム内で実行される。これらのＰＫＧは、少なくとも１つのルートＰＫＧと、このルートＰＫＧと送信者すなわち署名者との間の階層中にあるｎ個の下位レベルＰＫＧと、を含んでいる。ここで、ｎ≧１である。ブロック７０２において、ルートＰＫＧは、ルートＰＫＧだけに知られたルート鍵生成シークレットを選択する。ルート鍵生成シークレットは、階層中においてルートＰＫＧよりも下にあるＰＫＧまたはユーザのための秘密鍵を生成するために使用され得る。その後、ブロック７０４において、ルートＰＫＧは、ルート鍵生成シークレットに基づいて、ルート鍵生成パラメータを生成する。ブロック７０６において、下位レベルＰＫＧは、下位レベル鍵生成シークレットを選択する。所定の下位レベルＰＫＧに対応する下位レベル鍵生成シークレットは、階層中において対応する下位レベルＰＫＧよりも下にあるＰＫＧまたはユーザのための秘密鍵を生成するために使用され得る。ルート鍵生成シークレットと同様に、各下位レベル鍵生成シークレットは、その対応する下位レベルＰＫＧのみに知られている。ブロック７０８において、下位レベル鍵生成パラメータは、ｎ個の下位レベルＰＫＧの各々に生成される。下位レベル鍵生成パラメータの各々は、その対応する下位レベルＰＫＧにおける下位レベル鍵生成シークレットを少なくとも使用して生成される。
【０１０２】
ブロック７１０において、ある下位レベルＰＫＧは、受信者のための秘密鍵を生成する。この場合、秘密鍵は、ｎ個の下位レベル鍵生成シークレットのうちの少なくとも１つに関連付けられるように生成される。例えば、送信者の秘密鍵は、少なくとも、秘密鍵を受信者に対して発行したＰＫＧの下位レベル鍵生成シークレットに関連付けられ得る。しかしながら、受信者の秘密鍵は、その先祖ＰＫＧの下位レベル鍵生成シークレットのｎ個の全ておよびルート鍵生成シークレットに関連付けられることが好ましい。ブロック７１２において、送信者は、少なくともその秘密鍵を使用して、メッセージに署名するとともに、デジタル署名を生成する。その後、ブロック７１４において、受信者すなわち検証者は、少なくとも１つの下位レベル鍵生成パラメータを使用して、デジタル署名を検証する。例えば、署名は、ルート鍵生成パラメータだけを使用して検証されても良い。あるいは、１または複数の下位レベル鍵生成パラメータを使用しても良い。
【０１０３】
図８は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。図３に示されるように、送信者ｙ３０６は、階層中においてルートＰＫＧよりも（ｍ＋１）レベル下にあり、ＩＤ−タプル（ＩＤｙ１，．．．，ＩＤｙ（ｍ＋１））に関連付けられている。送信者のＩＤ−タプルは、送信者に関連付けられた同一性情報ＩＤｙ（ｍ＋１）と、階層中におけるそのｍ個の先祖下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｙｉと、を含んでいる。この方法は、複数の要素から成る第１及び第２の循環群Γ１及びΓ２を生成することにより、ブロック８０２から開始される。ブロック８０４においては、
【数５３】
2005521323.tif 000055
が選択される。この場合、
【数５４】
2005521323.tif 000056
は、それが第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成できるように選択される。
【数５５】
2005521323.tif 000057
は、前述したように、許容できるペアリングであることが好ましい。ブロック８０６において、第１の循環群Γ１のルートジェネレータＰ０が選択される。ブロック８０８においては、ルートＰＫＧ３０２に関連付けられ且つルートＰＫＧ３０２だけに知られたランダムルート鍵生成シークレットｓ０が選択される。ｓ０は、循環群Ｚ／ｑＺの１つの要素であることが好ましい。ブロック８１０においては、ルート鍵生成パラメータＱ０＝ｓ０Ｐ０が生成される。Ｑ０は、第１の循環群Γ１の１つの要素であることが好ましい。ブロック８１２においては、第１のファンクションＨ１が選択される。この場合、ファンクションＨ１は、第１の二進数字列から第１の循環群Γ１の要素を生成できるように選択される。ブロック８１４においては、第２のファンクションＨ３が選択される。この場合、ファンクションＨ３は、第２の循環群Γ２の要素から第２の二進数字列を生成できるように選択される。ブロック８０２からブロック８１４のファンクションは、前述したＨＩＤＳルートセットアップアルゴリズムの一部であり、ほぼ同時に実行されることが好ましい。一例として、Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎに開示されたファンクションのようなファンクションがＨ１およびＨ３として使用され得る。実際には、ファンクションＨ１およびＨ３は、全く同じファンクションであっても良い。しかしながら、潜在的な落とし穴がある。署名者がＭ＝ＩＤｔに署名するように攻撃者が仕向ける虞がある。ここで、ＩＤｔは、実際の同一性を表わしている。この場合、署名者の署名は、実際には、その後にメッセージを復号して署名を偽造するために使用される虞がある、秘密鍵であるかもしれない。しかしながら、この落とし穴は、署名と秘密鍵抽出とを区別する幾つかの方法、例えばＨ３のための異なるファンクションやビットプレフィックス等、を使用することにより、回避することができる。
【０１０４】
次の一連のブロック（ブロック８１６から８２４）は、下位レベルセットアップアルゴリズムの一部として実行されるファンクションを示している。ブロック８１６においては、送信者のｍ個の先祖下位レベルＰＫＧの各々に、パブリック要素Ｐｙｉが生成される。１≦ｉ≦ｍにおいて各パブリック要素Ｐｙｉ＝Ｈ１（ＩＤ１，．．．．，ＩＤｙｉ）は、第１の循環群Γ１の１つの要素であることが好ましい。全てのパブリック要素Ｐｙｉの生成が１つのブロックで表わされているが、これらのパブリック要素Ｐｙｉの生成は、同時に行なわれることなく経時的に行なわれても良い。
【０１０５】
送信者のｍ個の先祖下位レベルＰＫＧ３０４ａ、ｂ、ｄの各々に、下位レベル鍵生成シークレットｓｙｉが選択される（ブロック８１８）。下位レベル鍵生成シークレットｓｙｉは、１≦ｉ≦ｍにおいて循環群Ｚ／ｑＺの要素であることが好ましく、また、各下位レベル鍵生成シークレットｓｙｉは、その対応する下位レベルＰＫＧだけに知られていることが好ましい。この場合も同様に、全てのシークレットｓｙｉの選択が１つのブロックで表わされているが、これらのシークレットｓｙｉの選択は、同時に行なわれることなく経時的に行なわれても良い。
【０１０６】
送信者のｍ個の先祖下位レベルＰＫＧの各々に、下位レベルシークレット要素Ｓｙｉが生成される（ブロック８２０）。１≦ｉ≦ｍにおいて各下位レベルシークレット要素Ｓｙｉ＝Ｓｙ（ｉ−１）＋ｓｙ（ｉ−１）Ｐｙｉは、第１の循環群Γ１の要素であることが好ましい。パブリック要素Ｐｙｉおよびシークレットｓｙｉと同様に、全てのシークレット要素Ｓｙｉの生成が１つのブロックで表わされているが、これらのシークレット要素Ｓｙｉの生成は、同時に行なわれることなく経時的に行なわれても良い。これらの繰り返される鍵生成プロセスのため、Ｓ０は、Γ１の同一性要素として規定されることが好ましい。
【０１０７】
また、送信者のｍ個の先祖下位レベルＰＫＧの各々に、下位レベル鍵生成パラメータＱｙｉも生成される（ブロック８２２）。１≦ｉ≦ｍにおいて各鍵生成パラメータＱｙｉ＝ｓｙｉＰ０は、第１の循環群Γ１の要素であることが好ましい。全ての鍵生成パラメータＱｙｉの生成が１つのブロックで表わされているが、これらの鍵生成パラメータＱｙｉの生成は、同時に行なわれることなく経時的に行なわれても良い。
【０１０８】
次の２つのブロック（ブロック８２４、８２６）のファンクションは、前述した抽出アルゴリズムの一部として実行される。ブロック８２４においては、送信者ｙに関連付けられた送信者パブリック要素Ｐｙ（ｍ＋１）が生成される。送信者パブリック要素Ｐｙ（ｍ＋１）＝Ｈ１（ＩＤｙ１，．．．．，ＩＤｙ（ｍ＋１））は、第１の循環群Γ１の要素であることが好ましい。その後、ブロック８２６において、送信者ｙに関連付けられた送信者シークレット要素Ｓｙ（ｍ＋１）が生成される。また、送信者シークレット要素
【数５６】
2005521323.tif 000058
も、第１の循環群Γ１の要素であることが好ましい。
【０１０９】
便宜上、第１のファンクションＨ１は、随意的に、反復関数となるように選択されても良い。この場合、例えば、Ｈ１（ＩＤ１，．．．，ＩＤｙｉ）としてではなく、Ｈ１（Ｐｙ（ｉ−１），ＩＤｙｉ）として、パブリックポイントＰｉが演算され得る。
【０１１０】
図８に示される最後の２つのブロック（ブロック８２８、８３０）は、前述した署名アルゴリズムおよび検証アルゴリズムを表わしている。ブロック８２８においては、デジタル署名Ｓｉｇを生成するためにメッセージＭが署名される。この署名は、少なくとも送信者シークレット要素Ｓｙ（ｍ＋１）を使用することが好ましい。その後、ブロック８３０において、デジタル署名Ｓｉｇが検証される。この検証は、少なくともルート鍵生成パラメータＱ０および下位レベル鍵生成パラメータＱｙｉを使用することが好ましい。以下、メッセージＭの署名およびデジタル署名Ｓｉｇの検証におけるこれらのパラメータおよび要素の特定の用法について、図９を参照しながら説明する。
【０１１１】
図９は、現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。このスキームにおいて、ルートセットアップアルゴリズム、下位レベルセットアップアルゴリズム及び抽出アルゴリズムは、図８のブロック８０２から８２６に示された実施形態の場合と同じである。したがって、図９のフローチャートは、ブロック９２７ａにおいて、送信者ｙのみに知られる送信者鍵生成シークレットｓｙ（ｍ＋１）を選択することにより開始される。ブロック９２７ｂにおいては、式Ｑｙ（ｍ＋１）＝ｓｙ（ｍ＋１）Ｐ０を使用して、送信者に関連付けられる送信者鍵生成パラメータＱｙ（ｍ＋１）が生成される。その後、ブロック９２８ａにおいて、メッセージ要素ＰＭ＝Ｈ３（ＩＤｙ１，．．．．．，ＩＤｙ（ｍ＋１），Ｍ）を送信者が生成することにより、署名アルゴリズムが開始される。メッセージ要素ＰＭは、第１の循環群Γ１の構成要素であることが好ましい。デジタル署名Ｓｉｇは、それ自身、式Ｓｉｇ＝Ｓｙ（ｍ＋１）＋ｓｙ（ｍ＋１）ＰＭを使用して、ブロック９２８ｂで生成される。受信者は、式
【数５７】
2005521323.tif 000059
が満たされていることを確認することにより、デジタル署名Ｓｉｇを検証する（ブロック９３０）。
【０１１２】
その好ましい実施形態および例示的な実施例を特に参照して本発明を詳細に説明してきたが、本発明は、その思想および範囲内で変形および修正を成すことができる。
【図面の簡単な説明】
【０１１３】
【図１】現在において好ましい本発明の一実施形態に係る、デジタルメッセージをエンコードおよびデコードする方法を表わすフローチャートを示している。
【図２】現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間でデジタルメッセージをエンコードおよびデコードする方法を表わすフローチャートを示している。
【図３】図２の方法が実行され得る典型的な階層構造を表わすブロック図を示している。
【図４】現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。
【図５】現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。
【図６】現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭをエンコードおよびデコードする方法を表わすフローチャートを示している。
【図７】現在において好ましい本発明の他の実施形態に係る、デジタル署名を生成して検証する方法を表わすフローチャートを示している。
【図８】現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【図９】現在において好ましい本発明の他の実施形態に係る、送信者ｙと受信者ｚとの間で通信されるデジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【図１】
2005521323.tif 000101
【図２】
2005521323.tif 000102
【図３】
2005521323.tif 000103
【図４】
2005521323.tif 000104
【図５】
2005521323.tif 000105
【図６】
2005521323.tif 000106
【図７】
2005521323.tif 000107
【図８】
2005521323.tif 000108
【図９】
2005521323.tif 000109
【国際調査報告】
2005521323.tif 000110