(57)【要約】【課題】複数のアイデンティティに基づくデジタル署名を単一のアイデンティティに基づく「アグリゲート」デジタル署名に統合させる方法及びシステムを提供する。【解決手段】このアイデンティティに基づくアグリゲート署名は、もともとのアグリゲートされていないアイデンティティに基づく署名の連結よりも短いビット長を有する。アイデンティティに基づくアグリゲート署名は、どの署名者がどの文書に署名したかの記述と共に、１つ以上の秘密鍵ジェネレータ（ＰＫＧ）の公開鍵を入手できる誰もが検証することができる。検証者は、署名スキームが、「アイデンティティに基づく」ので、署名者毎に相異なる公開鍵を入手する必要はない。ＰＫＧの数は、署名者の数より少なくてもよい。その結果、アイデンティティに基づくアグリゲート署名、つまり、誰が何に署名したかの記述、ＰＫＧの公開鍵、アイデンティティに基づくアグリゲート署名自体、を検証するために必要な全情報は、個別のデジタル署名、つまり、誰が何に署名したかの記述、署名者の全てに対する公開検証鍵、署名者の署名の連結を検証するために必要な情報よりも少なくてよい。幾つかの実施形態において、アイデンティティに基づくアグリゲート署名スキームは、本質的に、可能な限り少ないコルモゴロフの計算量を有する。【選択図】図１【特許請求の範囲】
【請求項１】
文書Ｄに第１のデジタル署名を生成するシステムに実装された方法であって、
定義済み巡回群Ｇ１の複数の項の和Ｓ１を表す信号を生成する工程を有し、
前記項は、ｋ個の項
【数１】
2008508836.tif 000117
を含み、
ｋ及びｓは、前記文書Ｄから独立した定義済み整数であり、
ｋ＞１であり、
Ｃ１，…Ｃｋは、整数であり、
Ｃ１，…Ｃｋのうちの少なくとも２つは、互いに異なり、
Ｃ１，…Ｃｋのうちの少なくとも１つは、前記文書Ｄによって決まり、
Ｐ１，…Ｐｋは、前記文書Ｄから独立した前記群Ｇ１のｋ個の相異なる要素であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を示すことを特徴とする方法。
【請求項２】
前記要素Ｐ１，…Ｐｋは、署名者のアイデンティティの関数であることを特徴とする請求項１に記載の方法。
【請求項３】
第１のアグリゲートデジタル署名を生成する、システムに実装された方法であって、
前記第１のアグリゲートデジタル署名は、複数の個別のデジタル署名ＩＳ_１,…ＩＳ_ｎのアグリゲートを含み、
ｎは、１より大きい整数であり、
各個別のデジタル署名ＩＳ_ｉ(ｉ＝１，…ｎ)は、対応する文書Ｄ_ｉの署名であり、
各署名ＩＳ_ｉは、定義済み巡回群Ｇ１の複数の項の和を表す第１のコンポーネントＳ_ｉを含み、
前記項は、ｋ個の項
【数２】
2008508836.tif 000118
を含み、
ｋ及びｓ_ｉは、前記文書Ｄ_ｉから独立した定義済み整数であり、
ｋ＞１であり、
Ｃ１_ｉ，…Ｃｋ_ｉは、整数であり、
Ｃ１_ｉ，…Ｃｋ_ｉのうちの少なくとも２つは、互いに異なり、
Ｃ１_ｉ，…Ｃｋ_ｉのうちの少なくとも１つは、前記文書Ｄ_ｉによって決まり、
Ｐ１_ｉ，…Ｐｋ_ｉは、前記文書Ｄ_ｉから独立した前記群Ｇ１のｋ個の相異なる要素であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を示し、
前記第１のアグリゲートデジタル署名は、前記和Ｓ_ｉの和Ｓを表す第１のコンポーネントを含み、
前記方法は、
前記和Ｓの項を受け取る工程と、
前記和Ｓの前記項を加算する工程とを有し、
前記和Ｓの各項は、前記和Ｓ_ｉのうちの１又は複数の前記和Ｓ_ｉの和を表すことを特徴とする方法。
【請求項４】
デジタル署名ＤＳ１を検証して、前記デジタル署名ＤＳ１が請求項２の方法によって構成されているかどうかを判断するシステムに実装された方法であって、
前記デジタル署名ＤＳ１は、和Ｓ１に対応する第１のコンポーネントＣＯＭＰ１を含み、
前記方法は、等式
【数３】
2008508836.tif 000119
を検証し、
ｂｐ１は、Ｇ１×Ｇ１から群Ｇ２への非縮退双線型ペアリングであり、
ｆ１は、前記群Ｇ２の要素であり、
「＆」は、前記群Ｇ２の群演算であり、
ｐは、前記群Ｇ１の要素であり、
Ｑ＝ｓ＊Ｐであり、
【数４】
2008508836.tif 000120
であることを特徴とする方法。
【請求項５】
第１のアグリゲートデジタル署名を検証して、前記第１のアグリゲートデジタル署名が、個別のデジタル署名ＩＳ_１,…ＩＳ_ｎのアグリゲートを含むかどうかを判断するシステムに実装された方法であって、
ｎは、１より大きい整数であり、
各個別のデジタル署名ＩＳ_ｉ（ｉ＝１，…ｎ）は、対応する文書Ｄ_ｉの署名であり、
各個別のデジタル署名ＩＳ_ｉは、定義済み巡回群Ｇ１の複数の項の和Ｓ１_ｉである第１のコンポーネントを含む１つ以上のコンポーネントの集合を含み、
前記項は、ｋ個の項
【数５】
2008508836.tif 000121
を含み、
ｋは、１より大きい定義済み整数であり、
ｋは、前記文書Ｄ_１,…Ｄ_ｎから独立であり、
ｋは、前記個別のデジタル署名ＩＳ_ｉの全てに対して同じであり、
各個別のデジタル署名ＩＳ_ｉに対して、
（i）ｓは、前記文書Ｄ_１,…Ｄ_ｎから独立した定義済み整数であり、
（ii）Ｃ１_ｉ,…Ｃｋ_ｉは、非負整数であり、
Ｃ１_ｉ,…Ｃｋ_ｉのうちの少なくとも２つは、互いに異なっており、
Ｃ１_ｉ,…Ｃｋ_ｉのうちの少なくとも１つは、前記対応する文書Ｄ_ｉによって決まり、
（iii）Ｐ１_ｉi,…Ｐｋ_ｉは、前記文書Ｄ_１,…Ｄ_ｎから独立した前記群Ｇ１のｋ個の相異なる要素であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を示し、
前記個別のデジタル署名のアグリゲートは、前記和Ｓ_ｉの和Ｓであるコンポーネント
【数５Ａ】
2008508836.tif 000122
を含み、
前記第１のアグリゲートデジタル署名は、対応するコンポーネントＳｎを含み、
前記方法は、等式
【数６】
2008508836.tif 000123
を検証する工程を有し、
ｂｐ１は、Ｇ１×Ｇ１から群Ｇ２への非縮退双線型ペアリングであり、
Ｐは、前記群Ｇ１のジェネレータであり、
ｆ１は、前記群Ｇ２の要素であり、
「＆」は、前記群Ｇ２の群演算であり、
条件（Ａ）又は条件（Ｂ）のどちらかが真であり、
前記条件（Ａ）は、前記ｓパラメータが、前記個別のデジタル署名の全てに対して同じ値を有し、
【数７】
2008508836.tif 000124
であり
Ｑ＝ｓ＊Ｐであり、
【数７Ａ】
2008508836.tif 000125
が、１からｎまでの全てのｉについて取られる前記項
【数８】
2008508836.tif 000126
の和であるという条件であり、
前記条件（Ｂ）は、前記ｓパラメータが、Ｌ個の相異なる値ｓ_１,…ｓ_Ｌに分布し、
Ｌ＞１であり、
各値ｓ＝ｓ_ｊ（ｊ＝１,…Ｌ）が、１つ以上の前記個別のデジタル署名ＩＳ_ｉに対応し、
【数９】
2008508836.tif 000127
であり、
各ｊ＝１,…Ｌに対して、Ｑ_ｊ=ｓ_ｊ＊Ｐであり、
【数９Ａ】
2008508836.tif 000128
は、前記個別のデジタル署名ＩＳ_ｉが、前記値ｓ_ｊに対応するように、全てのｉについて取られる前記項
【数１０】
2008508836.tif 000129
の和であるという条件であることを特徴とする方法。
【請求項６】
秘密鍵を生成する方法であって、
（１）エンティティのアイデンティティＩＤ１を受け取る工程と、
（２）前記アイデンティティＩＤ１から、定義済み巡回群Ｇ１のｋ個の要素Ｐ１,…Ｐｋを生成する工程とを有し、
ｋ＞１であり、
【数１１】
2008508836.tif 000130
であり、
Ｈ１は、前記群Ｇ１に像を有する定義済み関数であり、
ｐａｒ_１,…ｐａｒ_ｋは、定義済みの相異なるパラメータであり、
ｓは、整数であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表すことを特徴とする方法。
【請求項７】
文書Ｄに第１のアグリゲートデジタル署名を生成するシステムに実装された方法であって、
第１のアグリゲートデジタル署名は、複数の個別のデジタル署名ＩＳ_１,…ＩＳ_ｎのアグリゲートを含み、
ｎは、１より大きい整数であり、
各個別のデジタル署名ＩＳ_ｉ（ｉ＝１,…,ｎ）は、定義済み巡回群Ｇ１の複数の項の和Ｓ_ｉを表す第１のコンポーネントを含み、
前記項は、項ｒ_ｉ＊ＰＤ及び（ｓ_ｉ＊Ｐ_ｉ）を含み、
ｒ_ｉ及びｓ_ｉは、前記文書Ｄから独立した整数であり、
ＰＤ及びＰ_ｉは、前記群Ｇ１の要素であり、
ＰＤは、前記文書Ｄによって決まり、全ての前記署名ＩＳ_ｉに対して同じであり、
Ｐ_ｉは、前記文書Ｄから独立であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表し、
前記第１のアグリゲートデジタル署名は、前記和Ｓ_ｉの和Ｓを表すコンポーネントを含み、
前記方法は、
前記和Ｓの項を受け取る工程と、
前記和Ｓの前記項を加算する工程とを有し、
前記和Ｓの各項は、前記和Ｓ_ｉiの１つ又は複数の前記和Ｓ_ｉの和を表すことを特徴とする方法。
【請求項８】
第１のアグリゲートデジタル署名を検証して、前記第１のアグリゲートデジタル署名が、個別のデジタル署名ＩＳ_１,…ＩＳ_ｎのアグリゲートを含むかどうかを判断するシステムに実装された方法であって、
ｎは、１より大きい整数であり、
各個別のデジタル署名ＩＳ_ｉ（ｉ＝１,…ｎ）が、全ての前記署名ＩＳ_ｉに対して同じ文書である文書Ｄの署名であり、
各個別のデジタル署名ＩＳ_ｉは、定義済み巡回群Ｇ１の複数の項の和Ｓ１_ｉである第１のコンポーネントを含む１つ以上のコンポーネントの集合を含み、
前記項は、ｋ個の項ｒ_ｉ＊ＰＤ及び（ｓ＊Ｐ_ｉ）を含み、
ｒ_ｉ及びｓは、前記文書Ｄから独立した整数であり、
ＰＤ及びＰ_ｉは、前記群Ｇ１の要素であり、
ＰＤは、前記文書Ｄによって決まり、前記署名ＩＳ_ｉの全てに対して同じであり、
Ｐ_ｉは、前記文書Ｄから独立であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表し、
前記第１のアグリゲートデジタル署名は、前記和Ｓ_ｉの和Ｓに対応するコンポーネントＳｎを含み、
前記個別のデジタル署名の前記アグリゲートは、前記和Ｓ１_ｉの和であるコンポーネント
【数１１Ａ】
2008508836.tif 000131
を含み、
前記第１のアグリゲートデジタル署名は、対応するコンポーネントＳｎを含み、
前記方法は、等式
【数１２】
2008508836.tif 000132
を検証し、
ｂｐ１は、Ｇ１×Ｇ１から群Ｇ２への非縮退双線型ペアリングであり、
Ｐは、前記群Ｇ１のジェネレータであり、
ｆ１は、前記群Ｇ２の要素であり、
「＆」は、前記群Ｇ２の群演算であり、
条件（Ａ）又は（Ｂ）のどちらかが真であり、
前記条件（Ａ）は、前記ｓパラメータが、前記個別のデジタル署名ＩＳ_ｉの全てに対して同じ値を有し、
【数１３】
2008508836.tif 000133
であり、
Ｑ＝ｓ＊Ｐであり、
【数１４】
2008508836.tif 000134
であるという条件であり、
前記条件（Ｂ）は、前記ｓパラメータが、Ｌ個の相異なる値ｓ_１,…ｓ_Ｌに分布し、
Ｌ＞１であり、
各値ｓ＝ｓ_ｊ（ｊ＝１,…Ｌ）は、１つ以上の前記個別のデジタル署名ＩＳ_ｊに対応し、
【数１５】
2008508836.tif 000135
であり、
各ｊ=１,…Ｌに対して、Ｑ_ｊ=ｓ_ｊ＊Ｐであり、
【数１６】
2008508836.tif 000136
は、前記値ｓ_ｊに対応する前記個別のデジタル署名の全てについて取られる前記項Ｐ_ｉの和であるという条件であることを特徴とする方法。
【請求項９】
ｍ人の署名者の署名を表す第１のデジタル署名を生成するシステムに実装された方法であって、
ｍは、正の整数であり、
各署名者ｊ（ｊ＝１，…ｍ）は、鍵（ａ_ｊ,１,…ａ_ｊ,ｋ）に関連付けられたエンティティであり、
ｋは、正の整数であり、
ａ_ｊ,１,…ａ_ｊ,ｋは、整数であり、
前記方法は、
（１）前記署名者ｍに関連付けられた文書Ｄ_ｍの関数であるｋビット（ｅ_１,…ｅ_ｋ）を生成する工程と、
（２）定義済み巡回群Ｇ１の項を生成する工程とを有し、
前記項は、
【数１７】
2008508836.tif 000137
であり、
【数１８】
2008508836.tif 000138
は、定義済み正の整数ｎを法とする整数の環Ｚ/ｎＺにおける乗法であり、
Ｓ_ＰＲＥＶ_ｍは、前記群Ｇ１の要素であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表すことを特徴とする方法。
【請求項１０】
秘密鍵を生成するシステムに実装された方法であって、
エンティティのアイデンティティＩＤ１を受け取る工程と、
前記アイデンティティＩＤ１から、定義済み正の整数ｎを法とする剰余類を表すｋ個の整数ａ_１,…ａ_ｋを生成する工程とを有し、
ｋ＞１は、整数であり、
ｊ＝１,…ｋに対して、ａ_ｊ＝（Ｈ１（ＩＤ１,ｐａｒ_ｊ））1/2（ｍｏｄ  ｎ）であり、
Ｈ１は、Ｚ/ｎＺに像を有する定義済み関数であり、
ｐａｒ_１,…ｐａｒ_ｋは、定義済みの相異なるパラメータであることを特徴とする方法。
【請求項１１】
第１のアグリゲートデジタル署名Ｓｎを検証して、前記第１のアグリゲートデジタル署名が、それぞれの文書Ｄ_１,…Ｄ_ｍのｍ人の署名者の署名の署名を表わすかどうかを判断するシステムに実装された方法であって、
ｍ＞１であり、
各署名者ｊ（ｊ＝１,…ｍ）が、鍵（ｂ_ｊ,１,…ｂ_ｊ,ｋ）に関連付けられたエンティティであり、
ｋ,ｂ_ｊ,１1,…ｂ_ｊ,ｋは、整数であり、
Ｓｎは、ジェネレータＰを有する定義済み巡回群Ｇ１の要素であり、
前記方法は、
等式ｂｐ１（Ｓｎ,Ｓｎ）＝ｂｐ１（Ｐ,Ｐ）bを検証する工程を有し、
ｂｐ１は、Ｇ１×Ｇ１から巡回群Ｇ２への双線型写像であり、
ｂは、定義済みモジュラスｎnを法とする全ての前記整数ｂ_ｊ,ｉの積であることを特徴とする方法。
【請求項１２】
複数のコンポーネントを含む秘密暗号鍵を生成するシステムに実装された方法であって、
（１）エンティティのアイデンティティＩＤ１を受け取る工程と、
（２）前記アイデンティティＩＤ１から前記コンポーネントのうちの少なくとも２つを生成する工程とを有し、
前記コンポーネントの前記少なくとも２つは、互いに異なることを特徴とする方法。
【請求項１３】
文書Ｄに第１のデジタル署名を生成するシステムに実装された方法であって、
（１）  署名者のアイデンティティの関数である複数の相異なるコンポーネントを含む署名鍵を取得する工程と、
（２）  前記コンポーネントから前記第１のデジタル署名を生成する工程とを有することを特徴とする方法。
【請求項１４】
第１のアグリゲートデジタル署名を生成するシステムに実装された方法であって、
前記第１のアグリゲートデジタル署名は、複数の個別のデジタル署名のアグリゲートを含み、
各個別のデジタル署名は、少なくとも１つの署名コンポーネントを含み、
前記方法は、
（１）  複数の第１の項を受け取る工程と、
（２）  前記第１の項から前記第１のアグリゲートデジタル署名のコンポーネントを生成する工程とを有し、
各第１の項は、前記個別のデジタル署名のうちの１つの署名コンポーネント、又は、前記個別の署名の２つ以上の署名コンポーネントの和のどちらかであり、
前記第１の項の前記署名コンポーネントのうちの少なくとも１つは、署名者の鍵の関数であり、
前記署名者の鍵は、それぞれが前記署名者のアイデンティティの関数である複数の相異なる鍵コンポーネントを含むことを特徴とする方法。
【請求項１５】
デジタル署名ＤＳ１を検証して、前記デジタル署名ＤＳ１が、請求項１３の方法によって構成されているかどうかを判断するシステムに実装された方法であって、
前記署名者のアイデンティティの少なくとも２つの相異なる関数を含む関係を検証する工程を有することを特徴とする方法。
【請求項１６】
請求項１乃至請求項１５の何れかの方法を実装するコンピュータシステム。
【請求項１７】
コンピュータシステムに請求項１乃至請求項１５の何れか１つの方法を実行させる１つ以上のコンピュータ命令を含むコンピュータで読み取り可能な媒体を含む製品。
【請求項１８】
コンピュータシステムに請求項１乃至請求項１５の何れか１つの方法を実行させる１つ以上のコンピュータ命令を含む、作られた信号。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、この参照により引用に含まれる、２００４年５月２０日出願の米国仮出願第６０５７３６５１号に基づく優先権を主張する。
【０００２】
また、本願は、この参照により引用に含まれる、発明者Ｃｒａｉｇ  Ｂ．Ｇｅｎｔｒｙ）及びＺｕｌｆｉｋａｒ  Ａｍｉｎ  Ｒａｍｚａｎによって出願された「Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  Ｉｎｃｌｕｄｉｎｇ  Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ａｇｇｒｅｇａｔｅ  Ｓｉｇｎａｔｕｒｅｓ」と題する２００５年５月１９日出願の米国特許出願に基づく優先権を主張する。
【０００３】
本発明は、デジタル署名に関し、特に、アイデンティティに基づくデジタル署名、並びに、他の個別署名及びアグリゲート署名に関する。
【背景技術】
【０００４】
デジタル署名は、暗号論的に仮定を「検証」することが可能な文字列（例えば、ビット）である。
【０００５】
例えば、Ｂｏｂが、文書Ｄの内容を承認したとの仮定に対して、Ｂｏｂは、彼の公開署名検証鍵ＶＫに対応する秘密署名鍵ＳＫを使って文書Ｄに対するデジタル署名Ｓを生成することができる。
【０００６】
そして、Ｓ、Ｋ、ＶＫを知っている人（及び、ＶＫが、詐欺師のものではなく、Ｂｏｂのものであることを確認した人）なら誰でも、Ｂｏｂが、実際に文書Ｄを承認したのだということを、暗号論的に検証することができる。
【０００７】
また、追加的に要求される検証情報（Ｄ，ＶＫ）と共に、Ｓが、Ｂｏｂのデジタル署名であるということが、暗号論的に検証することができる。
【０００８】
デジタル署名スキームが、安全であれば、Ｂｏｂ以外の人間は、Ｂｏｂの秘密鍵ＳＫを知らないので、彼のデジタル署名を偽造することは難しいはずである。
【０００９】
デジタル署名の概念は、Ｄｉｆｆｉｅ及びＨｅｌｌｍａｎの論文「Ｎｅｗ  Ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ」により１９７６年に提案された。
【００１０】
それ以来、デジタル署名を「効率的」なものにするために、多くの努力がなされてきた。
【００１１】
例えば、ある系統の研究は、計算速度の遅いプロセッサを有する装置においても、署名の生成又は署名の検証（又は、その両方）を素早く検証することができるという意味において、「計算処理的に効率的」な署名スキームを見出すものである。
【００１２】
他の系統の研究は、デジタル署名スキームが、最小帯域幅のオーバーヘッドを加えるという意味において、「帯域幅的に効率的」な署名スキームを見出すものである。
【００１３】
本特許出願に記載する発明は、主に、後者の系統の研究に属する。
【００１４】
１．従来の解決法
従来技術において、署名スキームを、より帯域幅的に効率的なものにするために、幾つかの手法が取られてきた。
【００１５】
１つは、（Ｓの値を伝達するために必要とされるビット数に関して）Ｓのサイズを可能な限り小さくするというものである。
【００１６】
例えば、この参照により引用に含まれる「Ｓｈｏｒｔ  Ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  Ｐａｉｒｉｎｇ」（Ａｓｉａｃｒｙｐｔ２００１予稿集、ＬＮＣS２２４８、ｐｐ．５１４−５３２、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社）において、Ｂｏｎｅｈ、Ｌｙｎｎ及びＳｈａｃｈａｍは、（「計算処理的なＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定」と呼ばれる仮定の下）、署名が、僅かに約１６０ビットであっても、十分な安全性を実現する署名スキームについて説明している。
【００１７】
しかしながら、Ｓが、僅かに１６０ビットであったとしても、その署名を検証するためには、つまり、署名者の公開署名検証鍵ＶＫ、及び、署名者が署名した文書Ｄの記述を検証するためには、他の情報も必要とされていた。
【００１８】
その結果、署名スキームの全体的な帯域幅は、実際には、１６０ビットではなく、１６０＋｜ＶＫ｜＋｜Ｄ｜である。ここで、｜Ｄ｜は、署名された文書を記述するために必要なビット数を表し、｜ＶＫ｜は、署名者の検証鍵の長さを表す。
【００１９】
帯域幅的に効率的な署名を実現する他の手法は、「メッセージの回復を可能とする署名」である。
【００２０】
これらのスキームにおいて、検証者は、署名Ｓから、Ｄのある数（例えば、ｋ）のビットを回復することができる。よって、署名を検証するために必要な全ビット数は、｜Ｓ｜＋｜ＶＫ｜＋（｜Ｄ｜−ｋ）である。メッセージの回復を可能とする既存の署名スキームの全てにおいて、ｋは、せいぜい｜Ｓ｜−１６０である。
【００２１】
その結果、検証する必要のある全情報は、Ｂｏｎｅｈ−Ｌｙｎｎ−Ｓｈａｃｈａｍスキームのように、依然として、少なくとも、１６０＋｜ＶＫ｜＋｜Ｄ｜である。
【００２２】
また、帯域幅の改善を可能とするとして時々説明される別の手法は、「アイデンティティに基づく署名」である（この参照により引用に含まれる、Ａ．Ｓｈａｍｉｒ著、「Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ａｎｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ」（Ｃｒｙｐｔｏ１９８４予稿集、ＬＮＣＳ１９６、ｐｐ．４７−５３、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社）を参照のこと。）
アイデンティティに基づく署名スキームにおいて、署名者（「Ｂｏｂ」と呼ぶ）は、通常のデジタル署名スキームにおいて行うような署名者自身の鍵のペア（ＳＫ，ＶＫ）を生成しない。
【００２３】
その代わりに、「秘密鍵ジェネレータ（ＰＫＧ）」と呼ばれる高信頼のオーソリティが、Ｂｏｂの「アイデンティティＩＤＢｏｂ（例えば、彼の名前や電子メールアドレス）」、及び、ＰＫＧ自体の秘密鍵ＳＫＰＫＧの関数として、Ｂｏｂの秘密鍵ＳＫＢｏｂを生成する。
【００２４】
また、文書ＤのＢｏｂの署名Ｓを検証するために、検証者は、ＢｏｂのアイデンティティＩＤＢｏｂ及び彼のＰＫＧの公開鍵ＰＫＰＫＧも必要とする。
【００２５】
Ｂｏｂのアイデンティティは、任意に短く（例えば、１６０ビットより随分少なく）てよいが、ＰＫＧの公開鍵は、典型的に十分長い（例えば、１６０ビット以上）。
【００２６】
よって、上述した帯域幅的に効率的な手法には、帯域幅的に際立った利点はない。
【００２７】
しかしながら、（本発明で説明するように、後述するアイデンティティに基づくアグリゲート署名に対して有用である）アイデンティティに基づく署名スキームの興味深い側面、つまり、Ｂｏｂの署名を検証するために、特にＢｏｂに対して個別化された公開検証鍵ＶＫを必要とせず、その代わりに、検証者は、（他の多くのクライアントに対してもＰＫＧとして機能する）ＢｏｂのＰＫＧに対する公開鍵だけを必要とするという側面に留意されたい。
【００２８】
また、帯域幅的に効率的な署名を実現するための別の手法は、「アグリゲート署名」である。
【００２９】
アグリゲート署名スキームにより、相異なる署名者によって生成された相異なる文書の署名を、単一の短い署名に「アグリゲート（集約）」することができる。
【００３０】
より具体的には、公開署名検証鍵（ＶＫ１，…，ＶＫｎ）を有するｎ人の署名者がおり、これらのｎ人の署名者は、それぞれの文書（Ｄ１，…，Ｄｎ）に署名し、それによって、ｎ個の署名（Ｓ１，…，Ｓｎ）を生成するとする。
【００３１】
アグリゲート署名スキームでは、値（Ｓ１，…，Ｓｎ）を、単一の「短い」値Ｓに集約することができる。｜Ｓ｜が、｜Ｓ１｜＋…＋｜Ｓｎ｜より随分少ないときに、それが当てはまる。理想的には、｜Ｓ｜は、ｎ（アグリゲートされた署名の数）によって決まることさえあってはならない。
【００３２】
全てのｉ∈［１，ｎ］に対して、検証鍵ＶＫｉを有する署名者が文書Ｄｉに署名したことを検証するために必要な全ての情報は、｜ＶＫ１｜＋…＋｜ＶＫｎ｜＋｜Ｄ｜＋｜Ｓ｜である。
【００３３】
ここで、Ｄは、Ｄ１からＤｎを個別に一覧にするよりもコンパクトである署名した文書（Ｄ１，…，Ｄｎ）の記述である。
【００３４】
従来技術によるアグリゲート署名スキームにおいては、それぞれの検証鍵の記述を集約することができない。よって、署名した文書Ｄの記述は増えないとしても、全体の検証情報は、ｎに伴って線形的に増える。
【００３５】
近年、２つのアグリゲート署名スキームがある。
【００３６】
第１のアグリゲート署名スキームは、この参照により引用に含まれる、Ｃｒａｉｇ  Ｇｅｎｔｒｙにより２００３年４月１５日に出願された「Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ  Ｕｓｉｎｇ  Ｂｉｌｉｎｅａｒ  Ｍａｐｐｉｎｇ」と題する特許出願番号第１０４９９８５３号に記載されるアグリゲート署名スキームである。
【００３７】
このスキームは、双線型の「ペアリング（例えば、楕円曲線、又は、アーベルバラエティ）」を使用し、これにより、誰もが任意の順序の署名のコレクションを集約することができる。
【００３８】
第２のアグリゲート署名スキームは、この参照により引用に含まれる、Ａ．Ｌｙｓｙａｎｓｋａｙａ、Ｓ．Ｍｉｃａｌｉ、Ｌ．Ｒｅｙｚｉｎ及びＨ．Ｓｈａｃｈａｍ著、「Ｓｅｑｕｅｎｔｉａｌ  Ａｇｇｒｅｇａｔｅ  Ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  Ｔｒａｐｄｏｏｒ  Ｐｅｒｍｕｔａｔｉｏｎｓ」（Ｅｕｒｏｃｒｙｐｔ２００４予稿集、ＬＮＣＳ３０２７、ｐｐ．７４−９０、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社）に記載のスキームである。
【００３９】
このスキームでは、シーケンシャルなアグリゲーションだけが可能である（これは、自由度が低い）が、（近年になってようやく暗号システムを構築するために使用されるようになったペアリングの概念に対して）より広く受け入れられているトラップドア転置処理（Ｔｒａｐｄｏｏｒ  Ｐｅｒｍｕｔａｔｉｏｎｓ）の概念を使用している。
【００４０】
第２のスキームは、アグリゲート署名スキームの「理想的な」目的、つまり、Ｓをｎから独立させるということを実現していない。
【００４１】
むしろ、彼らのスキームにおいては、Ｓのサイズは、署名者が一人増えるごとに、１、２ビットだけ増加する。
【００４２】
｜Ｓ｜は、ｎが増加するにつれて非常にゆっくりと増加するので、彼らのスキームは、理想的な目的を達成していないけれども、アグリゲート署名スキームと見なされている。
【非特許文献１】Ｐ．Ｓ．Ｌ．Ｍ．Ｂａｒｒｅｔｏ、Ｈ．Ｙ．Ｋｉｍ、Ｂ．Ｌｙｎｎ、Ｍ．Ｓｃｏｔｔｏ著、「Ｅｆｆｉｃｉｅｎｔ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｐａｉｒｉｎｇ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ｃｒｙｐｔｏ２００２予稿集、ＬＮＣＳ２４４２、ｐｐ．３５４−３６８、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社、２００２年
【非特許文献２】Ｄ．Ｂｏｎｅｈ、Ｍ．Ｆｒａｎｋｌｉｎ、Ｂ．Ｌｙｎｎ、Ｈ．Ｓｈａｃｈａｍ著、「Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  Ｐａｉｒｉｎｇ」、ＳＩＡＭＪ．Ｃｏｍｐｕｔｉｎｇ、３２（３）、５８６−６１５、２００３年、Ｃｒｙｐｔｏ２００１予稿集の拡張アブストラクト
【非特許文献３】Ｄ．Ｂｏｎｅｈ、Ｃ．Ｇｅｎｔｒｙ著、「Ａｇｇｒｅｇａｔｅ  ａｎｄ  Ｖｅｒｉｆｉａｂｌｙ  Ｅｎｃｒｙｐｔｅｄ  Ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  Ｂｉｌｉｎｅａｒ  Ｍａｐｓ」、Ｅｕｒｏｃｒｙｐ２００３予稿集、ＬＮＣＳ２６５６、ｐｐ．４１６−４３２、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社。２００３年
【非特許文献４】Ｄ．Ｂｏｎｅｈ、Ｂ．Ｌｙｎｎ、Ｈ．Ｓｈａｃｈａｍ著、「Ｓｈｏｒｔ  Ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  Ｐａｉｒｉｎｇ」、Ａｓｉａｓｃｒｙｐｔ２００１予稿集、ＬＮＣＳ２２４８、ｐｐ．５１４−５３２、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社、２００１年
【非特許文献５】Ａ．Ｌｙｓｙａｎｓｋａｙａ、Ｓ．Ｍｉｃａｌｉ、Ｌ．Ｒｅｙｚｉｎ、Ｈ．Ｓｈａｃｈａｍ著、「Ｓｅｑｕｅｎｔｉａｌ  Ａｇｇｒｅｇａｔｅ  Ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  Ｔｒａｐｄｏｏｒ  Ｐｅｒｍｕｔａｔｉｏｎｓ」、Ｅｕｒｏｃｒｙｐ２００４予稿集、ＬＮＳＣ３０２７、ｐｐ．７４−９０、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社、２００４年
【非特許文献６】Ｓ．Ｍｉｃａｌｉ、Ｋ．Ｏｈｔａ、Ｌ．Ｒｅｙｚｉｎ著、「説明可能な部分集合多重署名」（拡張アブストラクト）、ＣＣＳ２００１予稿集、ｐｐ．２４５−５４、ＡＣＭプレス、２００１年
【非特許文献７】Ａ．Ｓｈａｍｉｒ著、「Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍ  ａｎｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ」、Ｃｒｙｐｔｏ１９８４予稿集、ＬＮＣＳ１９６、ｐｐ．４７−５３、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社、１９８５年
【発明の開示】
【発明が解決しようとする課題】
【００４３】
２．以前の解決法の欠点
帯域幅の効率性に注目した系統の研究の究極の目的は、検証に必要な全情報を最小化する署名スキームを見出すことである。
【００４４】
任意の署名スキームに対して、誰が何に署名したかの記述Ｋを持たなければならない（メッセージの回復を有する署名スキームのように、記述のいくらかは、他の変数に折り畳まれているかもしれないが）。Ｋは、Ｋの値を伝達するために必要な最小のビット数である一定の「Ｋｏｌｍｏｇｏｒｏｖ計算量」を有する。
【００４５】
そのため、この系統の研究の究極の目的は、署名を検証するために必要なＫの他に、情報量を最小化することである。或いは、言い換えれば、究極の目的は、「コルモゴロフの最適性（Ｋｏｌｍｏｇｏｒｏｖ−ｏｐｔｉｍａｌ）」に可能な限り近い署名スキームを見出すことである。
【００４６】
せいぜいビットの小さい定数（すなわち、ｎから独立したビットの数）を「コルモゴロフの下界｜Ｋ｜」に加えるスキームに対するニーズがある。
【課題を解決するための手段】
【００４７】
このセクションでは、発明の幾つかの特徴について概要を述べる。他の特徴については、後のセクションで説明する。本発明は、この参照によりこのセクションに含まれる添付した特許請求の範囲により定義される。
【００４８】
本発明の幾つかの実施形態においては、複数の署名者が、複数の文書に署名することを可能にする署名スキームが提供されるが、それは、コルモゴロフの最適性に可能な限り近いものである。
【００４９】
「アイデンティティに基づくアグリゲート署名」と呼ばれる幾つかの実施形態では、所期の目的を実現している。
【００５０】
すなわち、アイデンティティに基づくアグリゲート署名を検証するために必要な情報は、Ｋ＋２の一定の長さの「タグ」である。
【００５１】
タグの１つは、秘密鍵ジェネレータの公開鍵、もう１つのタグは、実際のアイデンティティに基づくアグリゲート署名である。
【００５２】
アグリゲーションは、十分な自由度がある。例えば、誰もが、互換性のあるようにフォーマットされた署名のコレクションを集約することができる。
【００５３】
また、本発明は、さらに高い安全性が立証されているアイデンティティに基づく多重署名スキームを含む（アイデンティティに基づく多重署名スキームは、本質的に、相異なる署名者が同じメッセージに署名する、（縮退型の）アイデンティティに基づくアグリゲート署名スキームである）。
【００５４】
更に、本発明の幾つかの実施形態により、署名者が相異なるＰＫＧを有するアイデンティティに基づくアグリゲート署名が可能となる。
【００５５】
また、本発明には、新規のコンポーネントも含まれる。これらのコンポーネントの幾つかは、アイデンティティに基づくアグリゲート署名を生成するために使用されるアイデンティティに基づく秘密鍵の生成方法、集約することができるアイデンティティに基づく署名の生成方法、アイデンティティに基づく署名（及び、おそらく、アイデンティティに基づくサブアグリゲート署名）をアイデンティティに基づくアグリゲート（又は、より大きいサブアグリゲート）署名に集約する方法、及び、アイデンティティに基づくアグリゲート署名を検証する方法である。
【００５６】
また、本発明は、そのようなコンポーネントを実装するシステムや、そのようなコンポーネントを実装するためのコンピュータ指令及び／又はデータ構造を含むコンピュータにより読み取り可能な媒体や、そのようなコンピュータの指令及び／又はデータ構造を組み合わせるために作られた信号を含む。
【発明の効果】
【００５７】
本発明は、上述した特徴及び長所に制限されるものではない。他の特徴については、以下に説明する。本発明は、添付した特許請求の範囲により定義される。
【発明を実施するための最良の形態】
【００５８】
本発明の幾つかの実施形態では、様々な拡張及びアプリケーションとともに、安全かつ効率的なアイデンティティに基づくアグリゲート署名（及び多重署名）を実装する方法及びシステムが提供される。
【００５９】
まず、アイデンティティに基づくアグリゲート署名とは何であるかについて一般的な用語により明確にする。
【００６０】
＜１．アイデンティティに基づくアグリゲート署名＞
アイデンティティに基づくアグリゲート署名の幾つかの側面を、スキームの性能的な特徴、及び、スキームの安全性の特徴の両方に関して説明する。
【００６１】
＜１．１  性能的な特徴＞
アイデンティティに基づくアグリゲート署名の目的は、コルモゴロフの最適性に近い帯域幅の効率性を実現することにあることを思い出して欲しい。
【００６２】
誰が何に署名したかの記述Kは、署名者の数ｎに伴って、ほぼ直線的に増加する（例えば、「全ての署名者に対して、ｉ番目の署名者が、そのインデックスｉに署名する」という記述は、数ｎがＫの一部として生成されている場合の対数依存性をおそらく除いて、ｎから独立である）。
【００６３】
したがって、アイデンティティに基づくアグリゲート署名を検証する為に必要な情報量は、ｎに伴って必ずしも増加しないことが望ましい。
【００６４】
（注釈）
上述したように、Ｌｙｓｙａｎｓｋａｙａ等のアグリゲート署名スキームにおいて、アグリゲート署名Ｓの大きさは、実際には、ｎに伴って直線的には増加する。
【００６５】
しかし、この事実にも係わらず、彼らのスキームは、依然として、アグリゲート署名スキームと見なされている。
【００６６】
なぜならば、Ｓは、署名者が一人増える毎に、１又は２ビットだけ増加するためである（集約しない署名スキームの場合は、署名者が一人増える毎に、１６０ビット（又は、それ以上）増加するのに対して）。
【００６７】
本発明のアイデンティティに基づくアグリゲート署名の我々の定義は、このわずかな直線的増加の可能性を排除するものと解釈されるべきではないが、我々のアイデンティティに基づくアグリゲート署名の好ましい実施形態の帯域幅の消費は、ｎに従属ではない。
【００６８】
以前のアグリゲート署名スキームでは、誰が何に署名したかの記述Ｋに加えて、検証者は、ｎ個の公開署名検証鍵（ＶＫ１，…，ＶＫｎ）のそれぞれを、ｎ人の署名者のそれぞれに対して必要とする。
【００６９】
これらの以前のアグリゲート署名スキームでは、検証者は、（署名者が誰であるかの記述を含む）Ｋから、（ＶＫ１，…，ＶＫｎ）の値を得ることができない。
【００７０】
つまり、検証者は、署名者のアイデンティティから、署名者の公開鍵を解読することができない。
【００７１】
むしろ、各個別の署名者は、必ずしも署名者のアイデンティティＩＤｉによって決まらないように、自分自身の鍵のペア（ＳＫｉ，ＶＫｉ）をランダムに独立して生成する。
【００７２】
各ＶＫｉは、検証者となる人の観点から見れば、ランダムなので、検証者は、各ＶＫｉを「推測」することができない。
【００７３】
それを検証する前に、それぞれのＶＫｉを個別に求める必要があり、そのため、検証情報の全体の量が、ｎによって決まる。
【００７４】
幾つかの実施形態において、ｎに依存しない署名スキームを実現するため、我々は、各署名者に、その鍵のペアをランダムに生成させない。これにより、アイデンティティに基づく署名スキームの考え方が導かれる。
【００７５】
アイデンティティに基づく署名スキームにおいて、署名者の公開アイデンティティＩＤｉは、その公開鍵として働く。
【００７６】
署名者のアイデンティティ（ＩＤ１，…，ＩＤｎ）は、誰が何に署名したかの記述Ｋ（この場合、Ｋは、ｎに依存する）に、既に含まれていることに留意されたい。
【００７７】
署名者の秘密署名鍵ＳＫｉは、秘密鍵ジェネレータ（ＰＫＧ）と呼ばれる高信頼のオーソリティによって、署名者のアイデンティティＩＤｉ及びＰＫＧの秘密鍵ＳＫＰＫＧの関数として生成される。
【００７８】
署名者は、署名Ｓｉを出力する署名アルゴリズムに対して（Ｄｉ，ＳＫｉ）を入力することで、文書Ｄｉに署名する。
【００７９】
検証者は、Ｓｉが、アイデンティティＩＤｉを有する署名者による文書Ｄｉの有効な署名であることを、署名が有効か無効かによって「０」又は「１」を出力する検証アルゴリズム（ここで、ＰＫＰＫＧは、ＰＫＧの公開鍵）に対して、（Ｓｉ，Ｄｉ，ＩＤｉ，ＰＫＰＫＧ）を入力することによって検証する。
【００８０】
全ての署名者が、同じＰＫＧを使用するとすれば、検証者は、ＰＫＧの公開鍵の１つのコピーだけを必要とし、各署名者に対して、個別の公開鍵ＶＫｉを求める必要はない。
【００８１】
その結果、（集約しない）アイデンティティに基づく署名スキームでは、検証するために必要な全情報は、｜Ｋ｜＋｜ＰＫＰＫＧ｜＋｜Ｓ１｜＋…＋｜Ｓｎ｜である。
【００８２】
この場合、ｎへの依存は、署名者の（従来技術のアグリゲート署名スキームに対する）公開検証鍵ＶＫｉよりもむしろ、署名Ｓｉが起こす。
【００８３】
（注釈）
上記の説明から、「署名者は、単に公開検証鍵ＶＫｉをＩＤｉに等しく設定し、それに対応する秘密鍵を（ＰＫＧの支援なしに）、署名者自身で生成できないのか」という疑問があるかもしれない。
【００８４】
任意の特定の「暗号論的でない」アイデンティティ文字列ＩＤｉを、署名者の公開鍵として機能させる（この場合は、署名者が、その文字列に対する秘密暗号論的知識を持ち合わせていないという意味において「暗号論的でない」（このようなことは、ＩＤｉが、署名者の名前、又は、電子メールアドレスである場合に、おそらく起こり得るであろうが））のであれば、論理的に不可避な結果として、署名者以外の誰かが、署名者の秘密鍵を生成しなければならない。
【００８５】
その理由は、署名者が、自身のアイデンティティ文字列に対して、「特権的な」知識を持たないという想定になっているので、署名者が、自身の秘密鍵を生成できたとすると、同等な計算処理能力を有する他の誰でもが、秘密鍵を生成することができるためである。
【００８６】
その結果、幾つかの実施形態には、署名者の秘密鍵が、署名者の文字列ＩＤｉの関数として、「ＰＫＧ」と呼ばれる第三者（又は、第３者の連合）、及び、ＰＫＧの秘密鍵ＳＫＰＫＧと呼ばれるＰＫＧのみが知っている情報によって生成される。
【００８７】
検証情報のサイズは、アグリゲート署名でもアイデンティティに基づく署名でも、ｎによって決まるが、我々は、２つの概念を組み合わせることにより、ｎへの依存を排除することができる。
【００８８】
これは、言うのは簡単であるが、実際行うのは難しい。既存のアグリゲート署名スキーム、及び、既存のアイデンティティに基づく署名スキームを単に互いに組み合わせることでは、この目的を達成することはできない。
【００８９】
実際、アグリゲート署名が存在し、且つ、アイデンティティに基づく署名スキームが存在するだけでは、アイデンティティに基づくアグリゲート署名スキームが存在するということにはならないのは、確かである。
【００９０】
ここで、アイデンティティに基づくアグリゲート署名の少なくとも幾つかの実施形態において、我々が取得したいと考えるプロパティ及び性能特性について述べる。
【００９１】
アイデンティティに基づく署名等の場合、署名者の公開アイデンティティＩＤｉが、その公開鍵として機能し、署名者の秘密署名鍵ＳＫｉが、秘密鍵ジェネレータ（ＰＫＧ）と呼ばれる高信頼のオーソリティによって、署名者のアイデンティティＩＤｉ及びＰＫＧの秘密鍵ＳＫＰＫＧの関数として生成される。
【００９２】
アイデンティティ（ＩＤ１，…，ＩＤｎ）を有する署名者が、文書（Ｄ１，…，Ｄｎ）に署名するというアイデンティティに基づくアグリゲート署名を生成するために、各署名者は、それぞれの秘密鍵ＳＫｉを何らかの方法で、それぞれの文書Ｄｉに適用する。
【００９３】
アイデンティティに基づくアグリゲート署名Ｓを検証するために必要な情報の大きさは、ｎから独立であるべきである（又は、ｎに伴って緩やかに増加するべきである）。
【００９４】
具体的には、検証情報は、（Ｋ，Ｓ，ＰＫＰＫＧ）である。ここで、Ｓ及びＰＫＰＫＧの大きさは、ｎからは独立である。
【００９５】
署名者がＳを生成するまさにその方法は、スキームごとに異なっている。
【００９６】
我々の好ましい実施形態においては、それぞれの署名者は、自分自身のアイデンティティに基づく署名を、他の署名者のアイデンティティに基づく署名とは本質的に独立したものとして生成することができる。
【００９７】
その後、誰もが、自分達のアイデンティティに基づく署名を、１つのアグリゲートに（後で説明するある方法において、様々なアイデンティティに基づく署名が、「互換性のある」限り）、集約することができ、不特定複数のアグリゲートは、他のアグリゲート、又は、個別の署名と組み合わせることによって、更に他のアグリゲートを生成することができる。
【００９８】
或いは（Ｌｙｓｙａｎｓｋａｙａ等の意味で）、「シーケンシャルな」アイデンティティに基づくアグリゲート署名スキームを有してもよい。
【００９９】
ここに言う「シーケンシャルな」アイデンティティに基づくアグリゲート署名スキームでは、ｉ番目の署名者が、その署名を、（ｉ−１）番目の署名者の出力に対して、直接、集約し、自身の出力を生成する、つまり、署名者だけが、アグリゲーションを実行することができる。
【０１００】
アグリゲーションの方法は変わり得るが、結果は同じである必要がある。すなわち、署名が、ほぼコルモゴロフの最適性の検証情報の大きさを有する必要がある。
【０１０１】
＜１．２  安全性の特徴＞
デジタル署名は、偽造することが難しくなくてはならない。暗号論において、この概念は、適応的選択メッセージの下、実在の偽造に対する安全性として様式化することができる。
【０１０２】
この概念は、典型的には、「挑戦者」と「競争相手」との間で行われる「ゲーム」、つまり、大雑把に言うと、以下に説明する一定の条件次第では、競争相手が有効な偽造を生成すれば、競争相手が勝つという「ゲーム」に関して定義されている。
【０１０３】
我々のアイデンティティに基づくアグリゲート署名スキームでは、競争相手に署名（すなわち、偽造）するメッセージを選択させるだけでなく、攻撃したいと思うアイデンティティの群を選択する能力を与えている。このゲームを、我々は、以下の通り、明確にする。
【０１０４】
（設定）
挑戦者Ｃは、競争相手Ａに対して、ＰＫＧの公開鍵ＰＫＰＫＧを与える。
【０１０５】
（クエリ）
状況に適応しながら、Ａは、アイデンティティＩＤｉを選択し、対応する秘密鍵ＳＫｉを要求することができる。
【０１０６】
また、
【数１】
2008508836.tif 000002
【０１０７】
におけるアイデンティティに基づくアグリゲート署名σｉ−１が与えられているので、Ａは、
【数２】
2008508836.tif 000003
【０１０８】
のアイデンティティに基づくアグリゲート署名σｉを要求することができる。
【０１０９】
（応答）  ある
【数３】
2008508836.tif 000004
【０１１０】
に対して、競争相手Ａは、アイデンティティに基づくアグリゲート署名σｉを出力する。
【０１１１】
アイデンティティに基づくアグリゲート署名σｉが、
【数４】
2008508836.tif 000005
【０１１２】
の有効な署名であり、その署名が自明でない場合、すなわち、あるｉに対して、１≦ｉ≦ｌである場合、Ａが、ＩＤｉに対する秘密鍵を要求せず、ペア（ＩＤｉ，Ｄｉ）を含む署名を要求しない場合には、競争相手の勝ちである。
【０１１３】
非様式的には、上述したゲームは、実生活におけるアイデンティティに基づくアグリゲート署名スキームから、我々が期待する安全性のタイプに倣ったものである。
【０１１４】
実生活では、競争相手は、正当に生成されたアイデンティティに基づくアグリゲート署名の多くを見ることができるであろう。そのため、我々は、ゲームの中で、競争相手に正当な署名を要求する能力を与えたのである。
【０１１５】
現実の生活では、競争相手は、多くの署名者をだまして署名者の秘密鍵を自分に与えるようにする（又は、署名者は、自分の秘密鍵を競争相手に渡すことによって、競争相手と「共謀」する）ことができる。よって、ゲームの中で我々は、競争相手に秘密鍵を要求する能力を与えた。
【０１１６】
このような条件の下、我々が望むことができる最善の安全性のタイプは、競争相手が、既に正当に生成されているものではないアイデンティティに基づくアグリゲート署名を生成できず、署名者の秘密鍵の全てを知らないということである。
【０１１７】
これが、上述したゲームが倣ったものである。競争相手がスキームを破る確率は、競争相手がどのくらいの計算処理能力（又は、時間ｔ）を持つか、そして、どのくらいのクエリを生成できるようになっているのかによるので、我々は、これらの変数に関して安全性を定義している。
【０１１８】
（定義）
アイデンティティに基づくアグリゲート署名の競争相手Ａ（ｔ，ｑＨ，ｑＥ，ｑＳ，ε）は、Ａが、最大でも時間ｔで作動し、最大でｑＨのハッシュ関数クエリを生成し、最大でｑＥの秘密鍵クエリを生成し、最大でｑＳの署名クエリを生成し、また、「ＡｄｖＩＢＡＳｉｇＡ」が、少なくともεの場合に、上述した見本のアイデンティティに基づくアグリゲート署名を破る。
【０１１９】
「ＡｄｖＩＢＡＳｉｇＡ」は、Ａが、ゲームに「勝つ」確率である。
【０１２０】
かかる確率は、鍵生成アルゴリズム及びＡの双方のコイントスによるものである。
【０１２１】
（定義）
どの競争相手（ｔ，ｑＨ，ｑＥ，ｑＳ，ε）も、アイデンティティに基づくアグリゲート署名スキームを破らないとすると、そのスキームは、適応的選択メッセージ且つ適応的選択対象のアイデンティティ攻撃下で、実在の偽造に対して安全な（ｔ，ｑＨ，ｑＥ，ｑＳ，ε）である。
【０１２２】
本発明のアイデンティティに基づく署名スキームの好ましい実施形態は、広く使用されている「ランダムオラクルモデル（Ｒａｎｄｏｍ  Ｏｒａｃｌｅ  Ｍｏｄｅｌ）」（ＲＯＭ）における困難な安全性要件を満たしている。
【０１２３】
ＲＯＭにおいて、暗号論的ハッシュ関数は、安全性を立証するために、完全にランダムな関数のように扱われている。当技術分野に精通している者は、ＲＯＭをよく知っている。
【０１２４】
＜２．ペアリングの検討＞
本発明のアイデンティティに基づく署名スキームの好ましい実施形態では、「ペアリング」と呼ばれる双線型写像を使用する。
【０１２５】
過去数年間の間、ペアリングは、様々な暗号化スキームにおいて用いられ、現在ではよく知られている。
【０１２６】
典型的に使用されているペアリングは、超特異な楕円曲線、又は、アーベルバラエティに関する改良型の「Ｗｅｉｌペアリング」又は「Ｔａｔｅペアリング」である。
【０１２７】
しかしながら、ここでは、ペアリング及び関連した数学的処理を、より一般的な形式において説明する。
【０１２８】
Ｇ１及びＧ２を、ある大きい素数位数ｑの２つの巡回群とする。数ｑ＞３であり、いくつかの実施形態では、ｑ＞２１６０である。Ｇ１は、加算的に表現し、Ｇ２は、乗法的に表現する。
【０１２９】
（許容ペアリング）
【数５】
2008508836.tif 000006
【０１３０】
が、以下のプロパティを有する写像であれば、
【数６】
2008508836.tif 000007
【０１３１】
を、「許容ペアリング」と呼ぶ。
【０１３２】
１．双線型：  全てのＱ，Ｒ∈Ｇ１及び全てのａ，ｂ∈Ｚに対して、
【数７】
2008508836.tif 000008
【０１３３】
である（Ｚは、全ての整数の集合である）。
【０１３４】
２．非縮退：  あるＱ，Ｒ∈Ｇ１に対して、
【数８】
2008508836.tif 000009
【０１３５】
である。
【０１３６】
３．計算可能：  任意のＱ，Ｒ∈Ｇ１に対して、
【数９】
2008508836.tif 000010
【０１３７】
を計算する効率的なアルゴリズムがある。
【０１３８】
本発明は、許容ペアリングに限られるものではなく、特に、計算処理可能なペアリングに限られるものではない。
【数１０】
2008508836.tif 000011
【０１３９】
は、双線型であり、Ｇ１は、巡回群なので、
【数１１】
2008508836.tif 000012
【０１４０】
は、対称的である、すなわち、任意のＱ，Ｒ∈Ｇ１に対して、
【数１２】
2008508836.tif 000013
【０１４１】
であることに留意されたい。
【０１４２】
しかしながら、本発明は、巡回群に限定されるものでも、対称型ペアリングに限定されるものでもない。
【０１４３】
＜計算処理によるＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＣＤＨ）パラメータジェネレータ＞
ＰＧが、安全性のパラメータｋ＞０を取り、ｋにおいて１時間多項式で作動し、同じ素数位数ｑのＧ１及びＧ２の２つの群の記述及び許容ペアリング
【数１３】
2008508836.tif 000014
【０１４４】
の記述を出力すれば、ランダムにされたアルゴリズムＰＧＣＤＨは、ＣＤＨパラメータジェネレータである。
【０１４５】
本明細書のペアリングに基づいたスキームの安全性は、以下の問題の難しさによって決まる。
【０１４６】
＜Ｇ１（ＣＤＨＧ１）における計算処理によるＤｉｆｆｉｅ−Ｈｅｌｌｍａｎの課題＞
Ｐ，ａＰ，ｂＰ∈Ｇ１が与えられえていると、（ランダムに選択した未知のａ，ｂ∈Ｚ/ｑＺに対して）ａｂＰを計算する。ここで、ｑＺは、ｑで割り切れる全ての整数の集合であり、Ｚ/ｑＺは、ｑを法とする剰余類の集合である。
【０１４７】
ＣＤＨＧ１仮定を以下のように定義する。
【０１４８】
（ＣＤＨＧ１仮定）  ＰＧが、ＣＤＨパラメータジェネレータであるとすると、アルゴリズムＢが有するＣＤＨＧ１の課題を解く時の利点ＡｄｖＰＧ（Ｂ）は、アルゴリズムへの入力が、
【数１４】
2008508836.tif 000015
【０１４９】
である場合に、アルゴリズムＢが、ａｂＰを出力する確率であると定義される。
【０１５０】
ここで、
【数１５】
2008508836.tif 000016
【０１５１】
は、十分に大きい安全性のパラメータｋに対するＰＧの出力であり、Ｐは、Ｇ１のランダムジェネレータであり、ａ、ｂは、Ｚ/ｑＺのランダムな要素である。
【０１５２】
ＣＤＨＧ１仮定とは、全ての効率的なアルゴリズムＢに対して、ＡｄｖＰＧ（Ｂ）は、無視できるものであるということである。
【０１５３】
既に述べたように、（大雑把に言うと）我々のアイデンティティに基づくアグリゲート署名スキームの好ましい実施形態は、ＣＤＨＧ１仮定が真であるとの仮定に基づいて、ランダムオラクルモデルにおいて、適応的選択メッセージ且つ適応的選択対象のアイデンティティ攻撃下で、実在の偽造に対して安全であることが証明されている。
【０１５４】
しかしながら、本発明は、この安全性のプロパティを有する実施形態に限定されるものではない。
【０１５５】
＜３．アイデンティティに基づくアグリゲート署名スキームの好ましい実施形態＞
まず、スキームに関して直感的に分かるものを示す。ペアリングに基づく幾つかのスキームを含む様々なアイデンティティに基づく署名スキームが存在している。
【０１５６】
新規のアイデンティティに基づく署名スキームを構成することは難しいことではない。しかしながら、我々が知る限り、既存のアイデンティティに基づく署名スキームは、全て、署名生成がランダムに行われ、結果として得られるアイデンティティに基づく署名が一意的ではないという共通点を有している。
【０１５７】
アイデンティティに基づく署名は、典型的に、２つのコンポーネントからなる。１つは、ランダム性の「マスクされた」形式であり、もう１は、ランダム性に関連付けた後の認識の証明である。
【０１５８】
アグリゲート署名は、最近になってようやく見出され、現在までのところ、本質的に、２つの手法が存在するだけである。
【０１５９】
両方のスキームにおいて、署名生成は、決定論的であり、アグリゲート署名は、一意的である（ＬＭＲＳスキームにおいて、すなわち、Ｌｙｓｙａｎｓｋａｙａ等のスキームにおいて、各署名者は、ランダム性のビットを導入することができるが、これらの各ビットのために、アグリゲート署名の大きさが増す）。
【０１６０】
既存のアグリゲート署名スキームが決定論的であることは、驚きに値しない。なぜならば、各署名者が、署名にランダム性を導入できるのであれば、「ランダム性を集約する」ための何かしらの方法が必要とされるからである。
【０１６１】
実際、ランダム性を集約することは、まさに我々のアイデンティティに基づくアグリゲート署名スキームが行うことである。
【０１６２】
各個別のアイデンティティに基づく署名は、形式
【数１６】
2008508836.tif 000017
【０１６３】
を有する。
【０１６４】
ここで、
【数１７】
2008508836.tif 000018
【０１６５】
は、署名者のアイデンティティＩＤｉ及び署名者が署名するメッセージＭｉから、決定論的に計算される。
【０１６６】
ここで、（Ｐ，Ｐ’）は、全ての署名者に対して同じである点のあるペアであり、ｒｉは、ｉ番目の署名者がランダムに選択するスカラーである。
【０１６７】
そして、個別の署名は、アグリゲートされ、
【数１８】
2008508836.tif 000019
【０１６８】
を得ることができる。
【０１６９】
なお、署名の大きさが増加しないように、ｒｉのランダム値が、どのように加法を通して単に集約されたのかに留意されたい。
【０１７０】
ここで、スキームについてより具体的に説明する。以下の等式において、Ｐ’は、Ｐｗとして表わされている。文字Ｍ（ｍｅｓｓａｇｅ）及びＤ（ｄｏｃｕｍｅｎｔ）は、全体を通して交換可能に使用されている。「メッセージ（Ｍｅｓｓａｇｅ）」及び「文書（ｄｏｃｕｍｅｎｔ）」は、本明細書の中では、同義語として使用されている。
【０１７１】
（設定）
秘密鍵ジェネレータ（ＰＫＧ）は、本質的に、以前のペアリングに基づくスキームと同様に、パラメータ及び鍵を生成する。
【０１７２】
特に、ＰＫＧは、
１．  ある素数位数ｑ、及び、双線型非縮退ペアリング
【数１９】
2008508836.tif 000020
【０１７３】
の群Ｇ１及びＧ２を生成する（これは、許容ペアリングでよく、いくつかの実施形態においては、ｑ＞３であり、他の実施形態においては、Ｇ１が、楕円曲線群、又は、他のタイプの群であり、ｑ＞２１６０である）。
【０１７４】
２．  任意のジェネレータＰ∈Ｇ１を選択する。
【０１７５】
３．  ランダムなｓ∈Ｚ/ｑＺを選択し、Ｑ＝ｓＰを設定する。
【０１７６】
４．  暗号論的ハッシュ関数Ｈ１，Ｈ２：｛０，１｝＊→Ｇ１及びＨ３：｛０，１｝＊→Ｚ/ｑＺを選択する。
【０１７７】
ＰＫＧの公開鍵は、
【数２０】
2008508836.tif 000021
【０１７８】
である。ＰＫＧの秘密ＳＫＰＫＧは、ｓ∈Ｚ/ｑＺである。
【０１７９】
（秘密鍵生成）
アイデンティティＩＤｉを有するクライアントは、ＰＫＧから、ｊ∈｛０，１｝に対して、ｓＰｉ，ｊの値を受け取る。ここで、Ｐｉ，ｊ＝Ｈ１（ＩＤｉ，ｊ）∈Ｇ１である。
【０１８０】
（個別の署名）
第１の署名者は、それまで使ったことのない文字列ｗを選択する。その後に続く各署名者は、第１の署名者によって選択された文字列ｗを自分が使ったことがないということを確認する（又は、予め設定されたスケジュールに従って、異なる署名者が、署名を発行する場合には、例えば、署名が、ある予め設定された時間に生成され、ｗが、その時間によって定義される結果として、例えば、ｗが、署名生成時間の時間及び分によって定義され得る場合には、異なる署名者が、個別に同じｗに到達してもよい）。
【０１８１】
文書Ｄｉに署名するために、アイデンティティＩＤｉを有する署名者は、
１．  Ｐｗ＝Ｈ２（ｗ）∈Ｇ１を計算する。
【０１８２】
２．  ｃｉ＝Ｈ３（Ｄｉ，ＩＤｉ，ｗ）∈Ｚ/ｑＺを計算する。
【０１８３】
３．  ランダムなｒｉ∈Ｚ/ｑＺを生成する。
【０１８４】
４．  署名者の署名（ｗ，Ｓ’ｉ，Ｔ’ｉ）を計算する。ここで、
【数２１】
2008508836.tif 000022
【０１８５】
である。
【０１８６】
（アグリゲーション）
誰もが、同じ文字列ｗを使用する個別の署名のコレクションを集約することができる。
【０１８７】
例えば、１≦ｉ≦ｎに対して、個別の署名（ｗ，Ｓ’ｉ，Ｔ’ｉ）は、（ｗ，Ｓｎ，Ｔｎ）に集約することができる。ここで、
【数２２】
2008508836.tif 000023
【０１８８】
である。
【０１８９】
我々の安全性の証明では、相異なるｗの文字列を使用する個別の（又は、アグリゲート）署名のアグリゲーションを許可していない。
【０１９０】
しかしながら、同じｗを使用する署名は、署名者が、相異なる秘密鍵を有する相異なるＰＫＧを有する場合でも、ＰＫＧが、同じパラメータ
【数２３】
2008508836.tif 000024
【０１９１】
を使用する限り、集約することができる。詳細については、後述する。
【０１９２】
（検証）
（ｗ，Ｓｎ，Ｔｎ）を、アイデンティティに基づくアグリゲート署名とする（ここで、ｎは、署名者数である）。検証者は、
【数２４】
2008508836.tif 000025
【０１９３】
を確認する。ここで、上述の通り、Ｐｉ，ｊ＝Ｈ１（ＩＤｉ，ｊ）、Ｐｗ＝Ｈ２（ｗ）、ｃｉ＝Ｈ３（Ｄｉ，ＩＤｉ，ｗ）である。
【０１９４】
（注釈３Ａ（セクション３、注釈Ａ））
なぜ署名を、単に、ｓＰｉ，０＋ｃ１ｓＰｉ，１と設定しないのか？
それは、２つの署名の後、競争相手が、線形代数を使ってｓＰｉ，０及びｓＰｉ，１の値を回復することができそうだからである。一度だけ使用するＰｗの目的は、この線形を阻害することであり、一方で、全ての署名者が、「ランダム性をアグリゲートできる」場所を提供することである。
【０１９５】
（注釈３Ｂ）
上述のスキームにおいて、各署名者には、単一のｗの値を有する１つのアイデンティティに基づく署名だけが許されている。
【０１９６】
しかしながら、スキームは、アイデンティティＩＤｉを有するクライアントが、ＰＫＧから、ｊ∈［０，ｋ］に対して、ｓＰｉ，ｊである値を受け取るように、秘密鍵生成を変更することによって、各署名者が、ｗの値を有するｋ個の個別のアイデンティティに基づく署名を生成できるように簡単に修正することができる。ここで、Ｐｉ，ｊ＝Ｈ１（ＩＤｉ，ｊ）∈Ｇ１である。
【０１９７】
署名するために、署名者は、１≦ｊ≦ｋに対して、ｃｉｊ＝Ｈ３（Ｄｉ，ＩＤｉ，ｗ）を計算し、
【数２５】
2008508836.tif 000026
【０１９８】
を設定する。
【０１９９】
その署名は、既述した通り（ｗ，Ｓ’ｉ，Ｔ’ｉ）である。個別のアイデンティティに基づく署名は、既述したとおり、同じ加法を使用して集約され得る。
【０２００】
幾つかの実施形態において、用語ｓＰｉ，０を、Ｄｉ、ＩＤｉ、ｗによって決まる又は決まらない定数ｃ０によって乗じる。
【０２０１】
例えば、幾つかの実施形態において、ｃ０∈Ｈ３（Ｄｉ，ＩＤｉ，ｗ，−ｊ）である。定数ｃｉｊ（ｊ＝０，…，ｋ）のうち少なくとも１つは、文書Ｄｉによって決まる。これらの係数の一部又は全てが、ＩＤｉの関数である。
【０２０２】
（注釈）
アイデンティティに基づくアグリゲート署名は、例外的に、帯域幅的に効率的である。
【０２０３】
値ｗ、Ｓｎ、Ｔｎは、十分な安全性を実現しつつ、それぞれ非常に短く（例えば、１６０ビット）なるように取得され得る。
【０２０４】
誰が何を署名したかの記述ｋの考えられる例外としては、アイデンティティに基づくアグリゲート署名を検証するために必要な全情報の大きさ、特に、（ＰＫＰＫＧ，ｗ，Ｓｎ，Ｔｎ）の大きさは、一定の長さであり（すなわち、ｎから独立しており）、現実に非常に小さい。
【０２０５】
（注釈）
計算処理上の効率性という点では、このスキームは、Ｂｏｎｅｈ−Ｇｅｎｔｒｙ−Ｌｙｎｎ−Ｓｃｈａｃｈａｍ（ＢＧＬＳ）スキームよりも実際に効率的である。
【０２０６】
かかるＢＧＬＳスキームのように、検証のための全体の計算処理量は、署名者数において直線的である。
【０２０７】
しかし、ＢＧＬＳ署名スキームでは、ｎ＋１のペアリング計算処理が要求され、非常に計算処理的に重くなる。
【０２０８】
一方、上述したアイデンティティに基づくアグリゲート署名では、３つのペアリング（及び、比較的、計算処理的に軽くなりやすいｎ個のスカラー乗法）の計算処理が要求されるだけである。
【０２０９】
＜４．上述した実施形態の相異なるコンポーネント＞
ここで、上述したアイデンティティに基づくアグリゲート署名スキームを、秘密鍵生成コンポーネント、署名コンポーネント、アグリゲーションコンポーネント、検証コンポーネントを含む様々な新規のコンポーネントに分ける。
【０２１０】
これらのコンポーネントのそれぞれは、例えば、図１のコンピュータシステム１０４を使って、ソフトウェア、及び／又は、ハードウェア回路で実装することができる。
【０２１１】
各システム１０４は、例えば、携帯電話の部品のように、埋め込み式のシステムであってもよい。また、各システム１０４は、分散システムであってもよい。
【０２１２】
システム１０４は、１つ又は複数のプロセッサ１１０、及び、半導体メモリや磁気ディスクや磁気テープ或いは永久的な又は取り外し可能な公知の又はこれから発明される他の種類のコンピュータにより読み取り可能な媒体、又は、記憶装置を備えていてもよいメモリシステム１２０を有する。
【０２１３】
メモリは、コンピュータシステム１０４に、上述した、鍵生成や署名やアグリゲーションや検証等のコンポーネントの関数を実装させるためのコンピュータ命令を含んでいてもよい。
【０２１４】
相異なるコンピュータシステムは、相異なるコンポーネントを実装することができるが、これは必要なものではない。
【０２１５】
また、メモリ１２０も、様々なコンポーネントに必要な鍵や署名等のデータ構造を記憶する。
【０２１６】
コンピュータシステム１０４は、コンピュータネットワーク１３０を介して相互に情報交換を行っている。
【０２１７】
例えば、ＰＫＧのための鍵生成コンポーネントを実装するコンピュータシステム１０４は、秘密鍵を、別のシステム１０４で実装された署名コンポーネント対し、ネットワーク１３０を介して送ることができる。
【０２１８】
署名は、検証コンポーネントを実装するコンピュータシステム１０４に対して、ネットワーク１３０を介して送られ得る。
【０２１９】
ネットワーク１３０は、ＬＡＮ（ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）、ＷＡＮ（ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）を含むネットワーク、及び、例えば、携帯電話ネットワークや、公知の又はこれから発明される他のタイプのネットワークを含むネットワークの組み合わせを含んでいてもよい。
【０２２０】
１つ以上のシステム１０４を使って実装することができる秘密鍵生成コンポーネントは、入力としてアイデンティティ文字列及び秘密鍵を取る、つまり、秘密のアイデンティティに基づく署名鍵を出力する。
【０２２１】
上記のアイデンティティに基づくアグリゲート署名スキームにおいて、各アイデンティティに基づく秘密鍵は、１つ以上のポイント（例えば、単一の署名者に、同じ値ｗを有するｋ−１個の署名を生成させるｓＰｉ，０及びとｓＰｉ，１の２ポイント、又は、（より一般的には）ｋ）からなる。
【０２２２】
一方、ペアリングを使用する（Ｃｒｙｐｔｏ２００１会議で説明された）Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎのアイデンティティに基づく暗号スキームのような従来型のアイデンティティに基づくスキームにおいては、アイデンティティに基づく秘密鍵は、１ポイントだけからなる（例えば、ｓＰｉであり、Ｐｉ＝Ｈ１（ＩＤｉ）である）。
【０２２３】
この秘密鍵生成方法は、現状では、アイデンティティに基づくアグリゲート署名の上述した好ましい実施形態に対して一意的であり、安全性の立証において重要である。
【０２２４】
この方法は、アイデンティティに基づくアグリゲート署名スキームを可能にするアイデンティティに基づく秘密鍵の生成方法であり、最近になってようやく知られるようになった方法である。
【０２２５】
署名コンポーネントは、入力として、アイデンティティに基づく秘密鍵ｓＫｉ、文書Ｄｉ、及び、
【数２６】
2008508836.tif 000027
【０２２６】
に対して、アイデンティティに基づくアグリゲート署名σｉ−１を取る。
【０２２７】
つまり、
【数２７】
2008508836.tif 000028
【０２２８】
にアイデンティティに基づくアグリゲート署名σｉを出力する。
【０２２９】
署名アルゴリズムが、単に個別のアイデンティティに基づく署名を出力する場合に、
【数２８】
2008508836.tif 000029
【０２３０】
が、空集合であってもよい。
【０２３１】
上述した好ましい実施形態においては、第１の署名者に続く署名者達は、それ自体のアイデンティティに基づく署名を構成する前に、どのｗの値を使わなければならないのかを知るだけでよい。
【０２３２】
つまり、Ｓ’ｉ及びＴ’ｉに対する前の署名者の値を知る必要がなく、また、これらの値のアグリゲーションを知る必要もない。
【０２３３】
これは、アイデンティティに基づく署名をまず始めに生成し、必要であれば、後で集約することを可能にするアイデンティティに基づく署名の生成方法であり、最近になってようやく知られるようになった方法である。
【０２３４】
例えば、(アグリゲーションコンポーネント及び署名コンポーネントが、相異なるシステム１０４に実装されている場合)、この署名コンポーネントは、出力を、アグリゲーションコンポーネントシステム１０４に対して、ネットワーク１３０を介して直接送信する。
【０２３５】
アグリゲーションコンポーネントは、個別のアイデンティティに基づく署名、又は、アイデンティティに基づくアグリゲート署名を含んでもよい（1より大きい基数の）集合を、入力として取る。
【０２３６】
この集合の数が、互換性を有していれば、（例えば、上述したスキームにおいて、これらの署名が同じ値ｗを使用するならば）、アグリゲーションコンポーネントは、集合中の署名を単一の署名に集約する。
【０２３７】
検証コンポーネントは、誰が何を署名したかの記述ｋを、アイデンティティに基づくアグリゲート署名Ｓ、及び、１つ以上のＰＫＧの公開鍵と共に、入力として取る。
【０２３８】
つまり、アイデンティティに基づくアグリゲート署名は、示された署名者の各々が、それぞれの文書に実際に署名したということを、暗号論的に「立証する」のかどうかを示す（例えば、「０」又は、「１」）ビットを出力する。
【０２３９】
＜５．上述した好ましい実施形態の安全性＞
スキームの安全性を様式的に立証する前に、アルゴリズムＢが、我々のアイデンティティに基づくアグリゲート署名を破るアルゴリズムＡと相互作用することによって、如何にして計算処理的なＤｉｆｆｉｅ−Ｈｅｌｌｍａｎの問題を解決できるのか、すなわち、如何にしてＰ、ｓＰ、Ｐ’から、ｓＰ’を計算処理することができるのかについて直感的に分かるものを提供する。
【０２４０】
相互作用の間、Ｂは、Ａのクエリに正しく応答するか、中断しなければならない。Ａは、幾つかのタイプのクエリを生成することができる。
【０２４１】
（１．Ｈ１と抽出クエリ）
Ａは、アイデンティティＩＤｉに対応するｊ∈｛０，１｝に対して、アイデンティティに基づく秘密鍵Ｐｉ，ｊを要求することができる。
【０２４２】
Ｂは、このようなクエリを、Ｈ１オラクルの制御を通して取り扱うことができる。
【０２４３】
特に、Ｂは、通常、ｂｉ，ｊ＝ｌｏｇｐＰｉ，ｊを識別し、そして、ｓＰｉ，ｊ＝ｂｉ，ｊｓＰを計算することができるように、Ｐｉ，ｊを生成する。
【０２４４】
しかしながら、Ｂは、時々、Ｐｉ，ｊ＝ｂｉ，ｊＰ＋ｂ’ｉ，ｊＰ’を設定する。この場合、Ｂは、ＩＤｉの抽出クエリに応答することができない。
【０２４５】
しかしながら、Ａが、対象アイデンティティとして、ＩＤｉ後で選択すれば、Ａの偽造は、Ｂが、計算処理的なＤｉｆｆｉｅ−Ｈｅｌｌｍａｎの問題を解決するために役立つ。
【０２４６】
（２．Ｈ２クエリ）
Ｈ２オラクルの制御を通して、Ｂは、通常、ｄｗ＝ｌｏｇＰ’Ｐｗを認識するようにＰｗを生成する。しかし、その代わりに、時々、ｃｗ＝ｌｏｇＰＰｗを認識するようにＰｗを生成する。
【０２４７】
（３．Ｈ３と署名クエリ）
ＩＤｉに対応する秘密鍵を抽出することさえできない場合、ＢのＨ２及びＨ３オラクルに対する制御は、Ｂが、タプル（ＩＤｉ，Ｍｊ，ｗｋ）の署名クエリに対して応答するのに役立っている。
【０２４８】
そのような状況で、Ｂは、どのようにして、Ｐｉ，０、Ｐｉ，１、Ｐｗｋ、ｄｉ，ｊ，ｋ＝Ｈ３（ＩＤｉ，Ｍｊ，ｗｋ）、Ｓ’＝ｒＰｗｋ＋ｓＰｉ，０＋ｄｉｊｋｓＰｉ，１及びＴ’ｉ＝ｒＰの有効かつ無矛盾の値を生成することができるのか。
【０２４９】
特に、Ｂが、ｓＰ’を知っていることを要求しそうなＳ’iを、どのようにして生成できるのか。
【０２５０】
Ｂが、ｌｏｇＰ’Ｐｗを知っていれば、ｒ’ｓＰｗが最後の２つの項から来る複数のｓＰ’を「無効にする」ように、ｒ’の値を計算することができる。
【０２５１】
そして、Ｂは、Ｔ’ｉを、ｒ’ｓＰと設定する。Ｂが、ｌｏｇＰ’Ｐｗを知らなくても、Ｂが使えるトリックがもう１つある。つまり、Ｂは、時々、ｄｉｊｋを、最後の２つの項における複数のｓＰ’を無効にするＺ/ｑＺにおいて一意的な値に設定する。
【０２５２】
この場合、Ｂは、有効な署名を生成することができる。与えられたＩＤｉに対して、この一意的な値が、一旦、明らかにされてしまうと、このトリックを再び使用することはできない（そうでなければ、シミュレーションが、Ａにとって説得力のあるものにならない）。
【０２５３】
Ｂが、幸運であれば、そのシミュレーションは、中断されず、Ａは、ｌｏｇＰＰｉ，ｊを知らないが、ｌｏｇＰ’Ｐｗは知っているタプル（ＩＤｉ，Ｍｊ，ｗｋ）に関して、偽造を生成する。
【０２５４】
ここで、ｄｉｊｋは、上記のトリックを使っては選択されていない。この場合、Ａの偽造は、極めて高い確率で値ｓＰ’をＢに与える。
【０２５５】
以下の定理によって、我々のアイデンティティに基づくアグリゲート署名スキームは安全である。
【０２５６】
（定理１）
Ａを、
【数２９】
2008508836.tif 000030
【０２５７】
が、アイデンティティに基づくアグリゲート署名スキームを破るＩＤＡｇｇＳｉｇ−ＣＭＡ競争相手とする。
【０２５８】
そして、少なくとも
【数３０】
2008508836.tif 000031
【０２５９】
の確率を以って、時間Ｏ（ｔ）で、ＣＤＨＧ１を解くアルゴリズムＢが存在する。
【０２６０】
（証明）
ゲームは、群Ｇ１及びＧ２と許可ペアリング
【数３１】
2008508836.tif 000032
【０２６１】
を取得するために、挑戦者がＰＧを作動させることによって始まる。挑戦者は、
【数３２】
2008508836.tif 000033
【０２６２】
を生成し、
【数３３】
2008508836.tif 000034
【０２６３】
を、Ｂに送信する。Ｂは、以下のように、Ａと相互作用しながら、ＳＰ’∈Ｇ１（ここで、Ｑ＝ｓＰ）の計算処理を試みる。
【０２６４】
（設定）
Ｂは、Ａにシステムパラメータ
【数３４】
2008508836.tif 000035
【０２６５】
を与える。ここで、Ｈｉは、Ｂによって制御されるランダムオラクルである。
【０２６６】
（ハッシュクエリ）
Ａは、いつでも、Ｈ１クエリ、Ｈ２クエリ、Ｈ３クエリを作ることができる。Ｂは、整合性のために、以前のハッシュクエリ応答に関する一覧を維持しながら、同一のクエリに同一の応答を与える。
【０２６７】
また、Ｂは、Ｈ３シミュレーションのある特別なケースに対処するＨ３の一覧２も維持している。Ｂは、（ＩＤｉ，ｊ）に関するＡのＨ１クエリに、以下の通り応答する。
【０２６８】
ｊ∈｛０，１｝に対する（ＩＤｉ，ｊ）についてのＡのＨ１クエリに対して、
１．ＩＤｉが、前のＨ１クエリにあった場合、Ｂは、Ｈ１一覧から、（ｂｉ０，ｂ’ｉ０，ｂｉ１，ｂ’ｉ１）を回復する。
【０２６９】
２．その他、Ｂは、後で決定されるδ１に対して、Ｐｒ［Ｈ１−ｃｏｉｎｉ＝０］＝δ１となるように、ランダムなＨ１−ｃｏｉｎｉ∈｛０，１｝を生成する。
【０２７０】
Ｈ１−ｃｏｉｎｉであれば、Ｂは、ランダムなｂｉ０，ｂｉ１，∈Ｚ/ｑＺを生成し、ｂ’ｉ０＝ｂ’ｉ１＝０を設定する。
【０２７１】
その他、Ｂは、ランダムなｂｉ０，ｂ’ｉ０，ｂｉ１，ｂ’ｉ１∈Ｚ/ｑＺを生成する。Ｂは、Ｈ１の一覧の中の（ＩＤｉ，Ｈ１−ｃｏｉｎ，ｂｉ０，ｂ’ｉ０，ｂｉ１，ｂ’ｉ１）にログインする。
【０２７２】
３．Ｂは、Ｈ１（ＩＤｉ，ｊ）＝Ｐｉｊ＝ｂｉｊＰ＋ｂ’ｉｊＰ’ Ｈ１（ＩＤｉ，ｊ）＝Ｐｉｊ＝ｂｉｊＰ＋ｂ’ｉｊＰ’で応答する。
【０２７３】
ｗｋについてのＡのＨ２クエリに対して、
１．ｗｋが、前のＨ２クエリにあった場合、Ｂは、Ｈ２一覧からｃｋを回復する。
【０２７４】
２．その他、後で決定するδ２に対して、Ｐｒ［Ｈ１−ｃｏｉｎｉ＝０］＝δ２となるように、Ｂは、ランダムなＨ２−ｃｏｉｎｉ∈｛０，１｝を生成し、ランダムなｃｋ∈（Ｚ/ｑＺ）＊を生成する。Ｂは、Ｈ２一覧の中の（ｗｋ，Ｈ２−ｃｏｉｎｋ）にログインする。
【０２７５】
３．Ｈ１−ｃｏｉｎｋ＝０であれば、Ｂは、Ｈ２（ｗｋ）＝Ｐｗｋ＝ｃｋＰ’で応答するか、Ｈ２（ｗｋ）＝Ｐｗｋ＝ｃｋＰで応答する。
【０２７６】
（ＩＤｉ，Ｍｊ，ｗｋ）についてのＡのＨ３クエリに対して、
１．（ＩＤｉ，Ｍｊ，ｗｋ）が、前のＨ３クエリにあった場合、Ｂは、Ｈ３一覧からｄｉｊｋを回復する。
【０２７７】
２．その他、Ｂは、（ＩＤｉ，０）についてのＨ１クエリを作動させ、Ｈ３一覧からｂ’ｉ０及びｂ’ｉ１を回復する。Ｂは、後で決定するδ３に対して、Ｐｒ［Ｈ３−ｃｏｉｎｉｊｋ＝０］＝δ３であるように、ランダムなＨ３−ｃｏｉｎいｊｋ∈｛０，１｝を生成する。
【０２７８】
（ａ）  Ｈ１−ｃｏｉｎｉ＝１、Ｈ２−ｃｏｉｎｋ＝１、Ｈ３−ｃｏｉｎｉｊｋ＝０であれば、Ｂは、Ｈ３一覧２が、
【数３５】
2008508836.tif 000036
【０２７９】
を有するタプル
【数３６】
2008508836.tif 000037
【０２８０】
を含むかどうかを確認する。含む場合、Ｂは中断する。含まない場合、Ｈ３一覧２に（ＩＤｉ，Ｍｊ，ｗｋ）を置き、
【数３７】
2008508836.tif 000038
【０２８１】
を設定する。
【０２８２】
（ｂ）  Ｈ１−ｃｏｉｎｉ＝０、Ｈ２−ｃｏｉｎｋ＝０、Ｈ３−ｃｏｉｎｉｊｋ＝１である場合、Ｂは、ランダムなｄｉｊｋ∈（Ｚ＝ｑＺ）＊を生成する。
【０２８３】
（ｃ）  Ｂは、Ｈ３一覧の中の（ＩＤｉ，Ｍｊ，ｗｋ，Ｈ３−ｃｏｉｎｉｊｋ，ｄｉｊｋ）にログインする。
【０２８４】
３．Ｂは、Ｈ３（ＩＤｉ，Ｍｊ，ｗｋ）＝ｄｉｊｋで応答する。
【０２８５】
（抽出クエリ）
Ａが、ＩＤｉに対応する秘密鍵を要求すると、Ｂは、（Ｈ１−ｃｏｉｎｉ，ｂｉ０，ｂ’ｉ０）を回復する。
【０２８６】
Ｈ１−ｃｏｉｎｉ＝０の場合、Ｂは、（ｓＰｉ，０，ｓＰｉ，１）＝（ｂｉ０Ｑ，ｂｉ１Ｑ）で応答する。Ｈ１−ｃｏｉｎｉ＝１の場合、Ｂは、中断する。
【０２８７】
（署名クエリ）
Ａが、（ＩＤｉ，Ｍｊ，ｗｋ）における（新規の）署名を要求すると、Ｂは、まず、Ａが、前にｗｋにおけるＩＤｉによって署名を要求していなかったことを確認する（要求していた場合、それは、不適当なクエリである）。そして、Ｂは、以下のように続ける。
【０２８８】
１．  Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝Ｈ１−ｃｏｉｎｉｊｋ＝１であれば、Ｂは、中断する。
【０２８９】
２．  Ｈ１−ｃｏｉｎｉ＝０であれば、Ｂは、ランダムなｒ∈Ｚ/ｑＺを生成し、署名（ｗｋ，Ｓ’ｉ，Ｔ’ｉ）を出力する。ここで、
【数３８】
2008508836.tif 000039
【０２９０】
である。
【０２９１】
３．  Ｈ１−ｃｏｉｎｉ＝１及びＨ２−ｃｏｉｎｋ＝０の場合、Ｂは、ランダムなｒ∈Ｚ/ｑＺを生成し、署名（ｗｋ，Ｓ’ｉ，Ｔ’ｉ）を出力する。ここで、
【数３９】
2008508836.tif 000040
【０２９２】
である。
【０２９３】
４．  Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝１及びＨ３−ｃｏｉｎｉｊｋ＝０の場合、Ｂは、ランダムなｒ∈Ｚ/ｑＺを生成し、署名（ｗｋ，Ｓ’ｉ，Ｔ’ｉ）を出力する。ここで、
【数４０】
2008508836.tif 000041
【０２９４】
である。
【０２９５】
以下、シミュレーションの様々な側面について分析する。分析では、Ａが、重複クエリを作らず、Ａに関する署名クエリを作る前に、タプル（ＩＤｉ，Ｍｊ，ｗｋ）に関するＨ３クエリを作らなくてはならないと仮定する。
【０２９６】
Ｅは、Ｂが、シミュレーションにおける特定のポイントに対して、これ迄に作成してきた抽出クエリ応答の集合を表すものとする。
【０２９７】
同様に、Ｓが、署名クエリ応答の集合であるとし、Ｈｉが、ｉ∈｛１，２，３｝に対するＨｉクエリ応答の集合であるとする。
【０２９８】
Ｅ１，＊，＊を、Ｈ１−ｃｏｉｎｉ＝１の事象であるとする。ここで、「＊」は、Ｈ２−ｃｏｉｎｋ及びＨ３−ｃｏｉｎｉｊｋが、それぞれ、０又は１であってもよいことを意味する。Ｅ１，１，＊、Ｅ１，１，１、Ｅ１，１，０は、明らかな方法によって対応する事象を表す。
【０２９９】
（完璧なシミュレーション）
我々が主張するものは、Ｂが、中断しなければ、Ａの概念は、「本物の」攻撃におけるものと同じであるということである。
【０３００】
「本物の」攻撃においては、ハッシュ関数Ｈｉのそれぞれが、ランダム関数のように振る舞う。
【０３０１】
そして、Ｐｉ，ｊ＝Ｈ１（ＩＤｉ，ｊ）、Ｐｗｋ＝Ｈ２（ｗｋ）、ｄｉｊｋ＝Ｈ３（ＩＤｉ，ｊ，Ｍｊ，ｗｋ）の値が与えられている場合、署名は、集合
【数４１】
2008508836.tif 000042
【０３０２】
から一様に選択される。
【０３０３】
同様に、シミュレーションでは、署名は、Ｐｉ，ｊ＝Ｈ１（ＩＤｉ，ｊ）、Ｐｗｋ＝Ｈ２（ｗｋ）、ｄｉｊｋ＝Ｈ３（ＩＤｉ，ｊ，Ｍｊ，ｗｋ）の値が与えられている場合、集合
【数４２】
2008508836.tif 000043
【０３０４】
から一様に選択される。
【０３０５】
また、Ｈｉは、ランダム関数のように振る舞う。すなわち、１対１であり、出力は、一様な分布で選択される。
【０３０６】
唯一、このことが明らかでないのは、Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝１及びＨ３−ｃｏｉｎｉｊｋ＝０の場合である。
【０３０７】
この場合、Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝１及びＨ３−ｃｏｉｎｉｊｋ＝０（この場合、Ｂは中断する）に対する
【数４３】
2008508836.tif 000044
【０３０８】
に関して、Ａが、Ｈ３クエリを未だ作っていなければ、Ｂは、（Ｈ３の出力を一様にランダムに選択するよりも）、Ｈ３（ＩＤｉ，Ｍｊ，ｗｋ）を
【数４４】
2008508836.tif 000045
【０３０９】
に設定する。
【０３１０】
しかしながら、
【数４５】
2008508836.tif 000046
【０３１１】
の値は、それ自体一様にランダムである。
【０３１２】
より具体的には、（ＩＤｉ，Ｍｊ，ｗｋ）に関するＨ３クエリ迄の、つまり、Ｅ、Ｓ、｛Ｈｉ｝の集合迄のＡのビューが与えられているとすると、Ｂが、中断しない限りは、全てのｃ∈Ｚ/ｑＺに対して、
【数４６】
2008508836.tif 000047
【０３１３】
を有する。
【０３１４】
最も驚くことには、Ｈ１（ＩＤｉ）＝ｂｉｊＰ＋ｂ’ｉｊＰ’であっても、値
【数４７】
2008508836.tif 000048
【０３１５】
は、ＩＤｉに関するＨ１クエリ応答からは独立である。
【０３１６】
なぜならば、Ｈ１（ＩＤｉ，０）＝ｂｉ０Ｐ＋ｂ’ｉ０Ｐ’が与えられている場合、
【数４８】
2008508836.tif 000049
【０３１７】
を有するペア（ｂｉ０，ｂ’ｉ０）は、同等にあり得るからである。
【０３１８】
なお、Ｈ３（ＩＤｉ，Ｍｊ，ｗｋ）の値も、ＩＤｉの以外のアイデンティティに関するＨ１クエリ、全ての抽出クエリ応答（これらは、完全に、Ｈ１クエリ応答に従属であるため）、全てのＨ２クエリ、（ＩＤｉ，Ｍｊ，ｗｋ）以外のタプルに関する全てのＨ３クエリ（ここでも、Ｂは、中断しないと仮定する）、及び、（ＩＤｉ，Ｍｊ，ｗｋ）以外のタプルに関する全ての署名クエリから独立であることを明らかにしなければならない。
【０３１９】
（Ｂが中断しない確率）
Ｂは、３つの状況において中断する。
【０３２０】
Ａが、Ｈ１−ｃｏｉｎ１＝１に対して、ＩＤ１に関する抽出クエリを作成する。
【０３２１】
Ａが、Ｈ１−ｃｏｉｎ１＝Ｈ２−ｃｏｉｎｋ＝Ｈ３−ｃｏｉｎｉｊｋ＝１
に対して、タプル（ＩＤｉ，Ｍｊ，ｗｋ）に関する署名クエリを作成する。
【０３２２】
Ａが、Ｈ１−ｃｏｉｎ１＝１、Ｈ２−ｃｏｉｎｋ＝Ｈ２−ｃｏｉｎｋ’＝１、及び、Ｈ３−ｃｏｉｎｉｊｋ＝Ｈ３−ｃｏｉｎｉｊ’ｋ’＝０に対して、２つのＨ３クエリタプル（ＩＤｉ，Ｍｊ，ｗｋ）及び（ＩＤｉ，Ｍｊ’，ｗｋ’）を作成する。
【０３２３】
以下に、これら３つの状況のそれぞれの確率を分析する。
【０３２４】
まず、シミュレーションにおいて所与のポイントにおいて、ＩＤｉに関する抽出クエリが、Ｂに中断させる、すなわち、Ｐｒ［Ｅ１，＊，＊｜Ｅ，Ｓ，Ｈ１，Ｈ２，Ｈ３］である確率を考えてみる。ここで、それぞれのコインの確率（δ１，δ２，δ３）は、陰関数的である。ベイズの公式から、
【数４９】
2008508836.tif 000050
【０３２５】
を得る。
【０３２６】
我々が主張するものは、Ｐｒ［Ｅ１，＊，＊｜Ｅ，Ｓ，Ｈ１，Ｈ２，Ｈ３］は、せいぜいＰｒ［Ｅ１，＊，＊］＝１−δ１であるという結論を導く
【数５０】
2008508836.tif 000051
【０３２７】
である。
【０３２８】
シミュレーションにおいて、Ｈ２の計算処理は、全てのＨ１コインの値からは完全に独立である。
【０３２９】
Ｈ１（ＩＤｉ）の出力は、Ｈ１コインの値に関係なく、一様にランダムであるため、Ｈ１出力も、Ｈ１コインからは独立である。さらには、ＩＤｉに関連する抽出クエリＥが無いので、Ｅも、Ｅ１，＊，＊からは独立である。
【０３３０】
最後に、全ての署名クエリ応答、又は、ＩＤｉ以外のアイデンティティに関連する全てのＨ３クエリ応答は、Ｅ１，＊，＊からは独立である。
【０３３１】
よって、上述した我々の主張は、Ｐｒ［Ｓｉ，Ｈ３，ｉ｜Ｅ１，＊，＊］≦Ｐｒ［Ｓｉ，Ｈ３，ｉ］であるという主張と同等である。ここで、Ｓｉ及びＨ３，ｉは、ＩＤｉに関するＳ及びＨ３の部分集合を表す。
【０３３２】
しかしながら、Ｈ１−ｃｏｉｎ１＝０である時、署名クエリ、又は、（ＩＤｉ，Ｍｊ，ｗｋ）に関するＨ３クエリの間に、Ｂは、決して中断しない、つまり、Ｂは、Ｈ１−ｃｏｉｎ１＝１の時、（時々）中断するだけであるから、この主張は、明らかに真である。
【０３３３】
よって、Ａが、せいぜいｑＥ個の抽出クエリを作成することが許されていれば、抽出クエリ中に、Ｂが中断しない確率は、少なくとも
【数５０Ａ】
2008508836.tif 000052
である。
【０３３４】
第３の状況を考えるにあたって、Ａが、Ａに関する署名クエリを実行する前に、タプルに関するＨ３クエリを実行しなければならないと仮定する。
【０３３５】
第１の状況と同様に、我々は、Ｐｒ［Ｅ１，１，０｜Ｅ，Ｓ，Ｈ１，Ｈ２，Ｈ３］が、せいぜいＰｒ［Ｅ１，１，０］＝（１−δ１）（１−δ２）δ３であることを意味する
【数５１】
2008508836.tif 000053
【０３３６】
であることを主張する。
【０３３７】
上述した理由と同様に、Ｈ１応答、及び、Ｈ２応答は、コイン値からは独立であり、ＩＤｉに関係しない抽出応答は、Ｅ１，１，０からは独立であり、Ｂが、ＩＤｉに関連する抽出クエリに対して首尾よく応答できる確率は、０である。
【０３３８】
さらに、（（ＩＤｉ，Ｍｊ，ｗｋ）に関連する先行する署名クエリの確率を除外しているので）、Ｓ及びＨ３における全てのものが、Ｈ３−ｃｏｉｎｉｊｋ＝０からは独立であり、任意の署名クエリ、又は、ＩＤｉ及びｗｋも含まないＨ３クエリは、Ｅ１，１，０からは独立である。
【０３３９】
よって、上述した我々の主張は、
【数５２】
2008508836.tif 000054
【０３４０】
であるという主張と同等である。
【０３４１】
ここで、ＳｉＶｋ及びＨ３，ｉＶｋは、ＩＤｉ又はｗｋを含むＳ及びＨ３の部分集合である。
【０３４２】
しかし、Ｈ１−ｃｏｉｎｉ＝１又はＨ２−ｃｏｉｎｋ＝１が、アプリオリ（ａ  ｐｒｉｏｒｉ）である時、署名クエリ、又は、（ＩＤｉ’，Ｍｊ’，ｗｋ’）に関するＨ３クエリの間に、Ｂが中断する確率は高いので、この主張もまた、明らかに真である。
【０３４３】
第３の状況の確率を制限するために、任意のＩＤｉに対応するＨ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝１及びＨ３−ｃｏｉｎｉｊｋ＝０の２つ以上の発生がない確率を計算処理する。
【数５３】
2008508836.tif 000055
【０３４４】
とする。（Ｂが中断しなければ）、Ａは、ＩＤｉを含む
【数５４】
2008508836.tif 000056
【０３４５】
クエリを作るものとする。
【０３４６】
Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝１及びＨ３−ｃｏｉｎｉｊｋ＝０の発生がゼロである確率は、少なくとも
【数５５】
2008508836.tif 000057
【０３４７】
である。また、一つが発生する確率は、少なくとも
【数５６】
2008508836.tif 000058
【０３４８】
である。これら２つの確率の和は、
【数５７】
2008508836.tif 000059
【０３４９】
である。
【０３５０】
よって、Ｂが、いかなるＨ３クエリにおいて中断しない確率は、すくなくとも
【数５８】
2008508836.tif 000060
【０３５１】
である。この確率は、少なくとも
【数５９】
2008508836.tif 000061
【０３５２】
である。ここで、
【数６０】
2008508836.tif 000062
【０３５３】
は、Ｈ３クエリの総数である。
【０３５４】
最後に、我々は、Ｂが、署名クエリ中に中断しない確率の境界を下げる。上述した分析で、全てのクエリ応答が、Ｅ１，１，０の条件付き確率を下げた（Ｅ１，１，０の条件付き確率に影響を与えなかった）だけであることを、我々は見出した。
【０３５５】
ここで、（ＩＤｉ，Ｍｊ，ｗｋ）に関するＨ３クエリという１つのクエリのタイプを除いて、状況は同じである。
【０３５６】
Ｂが、（ＩＤｉ，Ｍｊ，ｗｋ）に関するＨ３クエリに首尾よく応答すれば、Ｂは、Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝１及びＨ３−ｃｏｉｎｉｊｋ＝０である確率を減らし、それに対応して他の全てのコインの組み合わせの条件付き確率を高める。
【０３５７】
しかしながら、Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝１及びＨ３−ｃｏｉｎｉｊｋ＝０というケースではないことが確かであっても、このことは、確かに、Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝Ｈ３−ｃｏｉｎｉｊｋ＝１の条件付き確率を
【数６１】
2008508836.tif 000063
【０３５８】
の割合だけ増加させる。
【０３５９】
その結果、任意の単一の署名クエリ中に、Ｂが中断しない確率は、少なくとも、
【数６２】
2008508836.tif 000064
【０３６０】
である。
【０３６１】
ｑＳ個の署名クエリまでの何れかの間に、Ａが中断しない確率は、少なくとも、
【数６３】
2008508836.tif 000065
【０３６２】
である。
【０３６３】
全体で、Ｂが中断しない確率は、少なくとも、
【数６４】
2008508836.tif 000066
【０３６４】
である。
【０３６５】
（Ｂが中断しない場合のＢの成功率）
Ａが、Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝Ｈ３−ｃｏｉｎｉｊｋ＝１に対して、タプル（ＩＤｉ，Ｍｊ，ｗｋ）に関する有効な署名偽造を生成し、
【数６５】
2008508836.tif 000067
【０３６６】
である場合には、Ｂは、成功、すなわち、（計算処理によるＤｉｆｆｉｅ−Ｈｅｌｌｍａｎの実現値を解く）ｓＰ’を計算処理することができる。
【０３６７】
この場合、Ａの偽造は、形式（Ｓｌ，Ｔｌ）を有する。ここで、
【数６６】
2008508836.tif 000068
【０３６８】
であり、ｃｉ’＝Ｈ３（ＩＤｉ’，Ｍｊ’，ｗｋ）を、アイデンティティＩＤｉを有するエンティティによって「署名された」タプルのハッシュとする。Ｈ２−ｃｏｉｎｋ＝１であるので、Ｂは、Pに対するＰｗｋの離散対数ｃｋを知っている。よって、Ｂは、
【数６７】
2008508836.tif 000069
【０３６９】
を計算することができる。
【０３７０】
署名されたタプルのうち少なくとも１つに対してＨ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝１であれば、
【数６８】
2008508836.tif 000070
【０３７１】
である確率は、１−１/ｑであり、
【数６９】
2008508836.tif 000071
【０３７２】
であれば、Ｂは、上述の式からｓＰ’を容易に引き出すことができる。
【０３７３】
Ｐｒ［Ｅ１，１，１｜Ｅ，Ｓ，Ｈ１，Ｈ２，Ｈ３］に関する下限を計算することが残っている。
【０３７４】
上述の理由と同様に、この確率は、Ｈ１及びＨ２から独立である。この確率は、ＩＤｉ’≠ＩＤｉに関する全ての抽出クエリからも独立であり、Ａは、対象アイデンティティＩＤｉに関する抽出クエリを作ることが許されていない。よって、
【数７０】
2008508836.tif 000072
【０３７５】
である。ベイズの公式から、
【数７１】
2008508836.tif 000073
【０３７６】
を得る。
【０３７７】
Ｐｒ［Ｓ，Ｈ３｜Ｅ１，１，１］/Ｐｒ［Ｓ，Ｈ３］の値は、Ｂが、Ｈ１−ｃｏｉｎｉ＝Ｈ２−ｃｏｉｎｋ＝Ｈ３−ｃｏｉｎｉｊｋ＝１であるというアプリオリ知識無しのクエリ
【数７２】
2008508836.tif 000074
【０３７８】
の集合の間にＢが中断しない確率に対する、アプリオリ知識を与えられた
【数７３】
2008508836.tif 000075
【０３７９】
の間にＢが中断しない確率に等しい。この比率は、少なくとも、前者の確率に等しい。この確率については、後で分析する。
【０３８０】
我々は、Ｐｒ［Ｅ１，１，１｜Ｓ，Ｈ３］に関する下限、つまり、どの署名クエリ及びＨ３クエリが、Ｂの中断の確率を最大化させるのかについて見出したいと考えている。
【０３８１】
Ｈ３クエリに関しては、Ａが、署名クエリを作るための全てのタプルに関するＨ３クエリを作成すると仮定する。
【０３８２】
これらを除いては、Ｂが中断する確率は、ｊ’≠ｊに対する（ＩＤｉ，Ｍｊ’，ｗｋ）のクエリによって最大化されている。署名クエリに関しては、Ａは、勿論、（ＩＤｉ，Ｍｊ，ｗｋ）の署名クエリを実行できない。
【０３８３】
しかしながら、Ａは、ＩＤｉ及びｗｋ、つまり、（ＩＤｉ，Ｍｊ，ｗｋ）を含む（少なくとも）１つの署名クエリを実行することはできる。
【０３８４】
Ｂが中断する確率を最大化するために、署名クエリの残りは、ＩＤｉ又はｗｋのどちらかを含まなければならない。
【０３８５】
（ＩＤｉ，Ｍｊ’’，ｗｋ）の署名及びハッシュクエリの間に中断するのを避けるために、Ｈ３−ｃｏｉｎｉｊｋ＝０でなければならない。
【０３８６】
よって、Ａがクエリを作成する他の任意のタプルに対して、Ｈ３−ｃｏｉｎｉｊ’’ｋ＝０であれば、Ｂは中断する。結果として、Ｂがこれらのクエリの間に中断しない確率は、
【数７４】
2008508836.tif 000076
【０３８７】
である。
【０３８８】
他のクエリの間の中断の確率は、署名クエリが、ＩＤｉ又はｗｋを含むかどうかによる。
【０３８９】
ＩＤｉに関する更なるハッシュ及び署名クエリに関して、Ｈ２−ｃｏｉｎｋ＝１であれば、Ｂは中断する。その結果、Ｂがそのようなクエリの間に中断しない確率は、δ２である。
【０３９０】
ｗｋは含むがＩＤｉを含まないハッシュ及び署名クエリペアに関しては、Ｂは、Ｈ１−ｃｏｉｎｉ＝Ｈ３−ｃｏｉｎｉｊｋ＝１である時だけ中断する。その結果、確率１−（１−δ１）（１−δ３）では中断しない。δ４＝ｍｉｎ（δ２，１−（１−δ１）（１−δ３））とする。
【０３９１】
Ｂが中断しない全体の確率は、少なくとも
【数７５】
2008508836.tif 000077
【０３９２】
である。よって、
【数７６】
2008508836.tif 000078
【０３９３】
である。
【０３９４】
（計算結果）
全体として、Ｂの成功の確率は、少なくともεの積である。Ｂが中断しない確率における下限は、
【数７７】
2008508836.tif 000079
【０３９５】
であり、Ａが偽造を生成する場合に、Ｂが成功する確率における下限は、
【数７８】
2008508836.tif 000080
【０３９６】
である。
【０３９７】
この成功の確率の境界を下げるために、（δ１，δ２，δ３）の値を選択する。特に、
【数７９】
2008508836.tif 000081
【０３９８】
に対して、
【数８０】
2008508836.tif 000082
【０３９９】
のそれぞれが少なくとも２であると仮定すると、この積が、少なくとも、
【数８１】
2008508836.tif 000083
【０４００】
であることが得られる。
【０４０１】
（６．多重署名スキーム）
上述したように、アイデンティティに基づく多重署名スキームは、本質的に、相異なる署名者が同じメッセージに署名する（縮退した）アイデンティティに基づくアグリゲート署名スキームである。
【０４０２】
その結果、アイデンティティに基づく多重署名スキームは、アイデンティティに基づくアグリゲート署名スキームよりも自由度が低いことを要求するので、アイデンティティに基づくアグリゲート署名の好ましい実施形態よりも、より良い性能的特徴及びより良い安全性特徴を有するアイデンティティに基づく多重署名スキームを実現することができる。
【０４０３】
ここで、アイデンティティに基づく多重署名スキームの好ましい実施形態を説明する。
【０４０４】
（設定）
秘密鍵ジェネレータ（ＰＫＧ）は、本質的には、前のペアリングに基づいたスキームと同じように、パラメータ及び鍵を生成する。具体的には、
１．  ある素数位数ｑの群Ｇ１及びＧ２、及び、双線型非縮退ペアリング
【数８２】
2008508836.tif 000084
【０４０５】
を生成する（これは、許可ペアリングであってもよく、幾つかの実施形態においては、ｑ＞３であり、他の実施形態においては、Ｇ１は、楕円曲線群、又は、他のタイプの群であり、ｑ＞２１６０である）。
【０４０６】
２．  任意のジェネレータＰ∈Ｇ１を選択する。
【０４０７】
３．  ｓ∈Ｚ/ｑＺを取り、Ｑ＝ｓＰを設定する。
【０４０８】
４．  暗号論的ハッシュ関数Ｈ１，Ｈ２：｛０，１｝＊→Ｇ１を選択する。
【０４０９】
ＰＫＧの公開鍵は、
【数８３】
2008508836.tif 000085
【０４１０】
である。根ＰＫＧの秘密は、ｓ∈Ｚ/ｑＺである。
【０４１１】
（秘密鍵生成）
アイデンティティＩＤｉを有するクライアントは、ＰＫＧからｓＰｉの値を受け取る。ここで、Ｐｉ＝Ｈ１（ＩＤｉ）∈Ｇ１である。
【０４１２】
（個別の署名）
Ｄを署名するために、アイデンティティＩＤｉを有する署名者は、１．  ＰＤ＝Ｈ２（Ｄ）∈Ｇ１を計算する
２．  ランダムなｒｉ∈Ｚ/ｑＺを生成する。
【０４１３】
３．  署名（Ｓ’ｉ，Ｔ’ｉ）を計算する。ここで、Ｓ’ｉ＝ｒｉＰＤ＋ｓＰｉ及びＴ’ｉ＝ｒｉＰである。
【０４１４】
（アグリゲーション）
誰もが、同じ文書Ｄに署名する個別の署名のコレクションを集約することができる。
【０４１５】
例えば、１≦ｉ≦ｎに対する個別の署名（Ｓ’ｉ，Ｔ’ｉ）を、個別の署名（Ｓｎ，Ｔｎ）に集約することができる。ここで、
【数８４】
2008508836.tif 000086
【０４１６】
である。
【０４１７】
アイデンティティに基づくアグリゲート署名スキームに関しては、同じ文書Ｄを使用する署名は、署名者が相異なる秘密鍵を有する相異なるＰＫＧを有する場合でも、ＰＫＧが同じパラメータ
【数８５】
2008508836.tif 000087
【０４１８】
を使用する限り、集約され得る。以下のセクション７を参照。
【０４１９】
（検証）
（Ｓｎ，Ｔｎ）をアイデンティティに基づくアグリゲート署名とする（ここで、ｎは、署名者数である）。検証者は、
【数８６】
2008508836.tif 000088
【０４２０】
を確認する。ここで、上述したように、Ｐｉ＝Ｈ１（ＩＤｉ）及びＰＤ＝Ｈ２（Ｄ）である。
【０４２１】
（７．複数のＰＫＧの拡張）
（７．１  アグリゲート署名）
上記セクション３で説明した、アイデンティティに基づくアグリゲート署名スキームは、署名者が、１つ以上のＰＫＧから署名者の秘密鍵を得られるように拡張することができる。
【０４２２】
以下に、２つのＰＫＧを有するアイデンティティに基づくアグリゲート署名を説明する。２つのＰＫＧから、それ以上のＰＫＧへの拡張は、明らかである。
【０４２３】
（設定）
ＰＫＧ１及びＰＫＧ２は共に、次のように、幾つかの同じパラメータを使用する。
【０４２４】
１．  ある素数位数ｑの群Ｇ１及びＧ２、及び、許可ペアリング
【数８７】
2008508836.tif 000089
【０４２５】
２．  任意のジェネレータＰ∈Ｇ１
３．  暗号論的ハッシュ関数Ｈ２：｛０，１｝→Ｇ１
ＰＫＧ１は、ランダムなｓ１∈ｚ/ｑＺを取り、Ｑ１＝ｓ１Ｐを設定する。同様に、ＰＫＧ２は、Ｓ２及びＱ２を生成する。
【０４２６】
２つのＰＫＧが、Ｈ１の代わりに使用するハッシュ関数は、同じでも異なってもよい。
【０４２７】
以下の好適な実施形態において、ハッシュ関数は同じであると仮定するが、以下に明らかにするように、ＰＫＧ１が、この関数を使用する時は、Ｈ１への入力としてＱ１の値を含み、一方、ＰＫＧ２が、この関数を使用する時は、Ｈ１への入力としてＱ２の値を含むことによって、その出力が異なっていることを（高い確率で）保証する。
【０４２８】
当業者であれば、同様な効果を有する異なった手法を、直ちに認識するであろう。
【０４２９】
ＰＫＧ１の公開鍵は、
【数８８】
2008508836.tif 000090
【０４３０】
であり、一方、ＰＫＧ２の公開鍵は、Ｑ１の代わりにＱ２を使用する。秘密は、それぞれｓ１及びｓ２である。
【０４３１】
（秘密鍵生成）
アイデンティティＩＤｉを有する署名者が、ＰＫＧ１のクライアントであるとすると、署名者は、ＰＫＧ１から、ｊ∈｛０，１｝に対するｓ１Ｐ１，ｉ，ｊの値を受け取る。ここで、Ｐ１，ｉ，ｊ＝Ｈ１（Ｑ１，ＩＤｉ，ｊ）∈Ｇ１である。
【０４３２】
署名者が、ＰＫＧ２のクライアントであるとすると、ｊ∈｛０，１｝に対するｓ２Ｐ２，ｉ，ｊを受け取る。ここで、Ｐ２，ｉ，ｊ＝Ｈ１（Ｑ２，ＩＤｉ，ｊ）∈Ｇ１である。
【０４３３】
このスキームは、上述した注釈３Ｂのケース（ｋは、ｗのものを使用する）まで拡張することができる。
【０４３４】
各秘密鍵は、上述したように生成することができるが、ｋ＋１ポイント、すなわち、ｊ∈｛０，ｋ｝を含んでいる。
【０４３５】
（個別の署名）
第１の署名者は、前に自分が決して使用していない文字列ｗを選択する。それに続く各署名者は、第１の署名者によって選択された文字列ｗを自分が使用していないことを確認する（或いは、例えば、予め計画されたスケジュールによって署名を発行する場合、異なる署名者が、個別に同じｗに到達してもよい）。
【０４３６】
Ｄｉに署名するために、（ａ∈｛１，２｝に対して）、ＰＫＧａのクライアントであるアイデンティティＩＤｉを有する署名者は、
１．  Ｐｗ＝Ｈ２（ｗ）∈Ｇ１を計算する。
【０４３７】
２．  ｃｉ＝Ｈ２（Ｑ，Ｄｉ，ＩＤｉ，ｗ）∈Ｚ/ｑＺを計算する。
【０４３８】
３．  ランダムなｒｉ∈Ｚ/ｑＺを生成する。
【０４３９】
４．  その署名（ｗ，Ｓ’ｉ，Ｔ’ｉ）を計算する。ここで、
【数８８Ａ】
2008508836.tif 000091
である。
【０４４０】
（アグリゲーション）
誰もが、同じ文字列ｗを使用する個別の署名のコレクションを集約することができる。例えば、１≦ｉ≦ｎに対して、個別の署名（ｗ，Ｓ’ｉ，Ｔ’ｉ）を、（ｗ，Ｓｎ，Ｔｎ）に集約することができる。ここで、
【数８９】
2008508836.tif 000092
【０４４１】
である。
【０４４２】
（検証）
（ｗ，Ｓｎ，Ｔｎ）を、アイデンティティに基づくアグリゲート署名とする（ここで、ｎは、署名者数である）。
【０４４３】
Ｉ１を、ｉ番目の署名者が、ＰＫＧ２のクライアントである［１，ｎ］における指数ｉの集合とする。Ｉ２を、ＰＫＧ２に対する指数の対応する（かつ、補足的な）集合とする。検証者は、
【数９０】
2008508836.tif 000093
【０４４４】
を確認する。
【０４４５】
検証者は、ここでは、１つではなく、２つのＰＫＧの公開鍵を知る必要があることに留意されたい。
【０４４６】
当業者であれば、この複数のＰＫＧのアイデンティティに基づくアグリゲート署名スキームにおけるＰＫＧが、上述したように、非階層的クライアント構造に対する秘密鍵生成を監視する独立したＰＫＧだけではなく、階層的なアイデンティティに基づく暗号システムにおいてレベルの低いＰＫＧであってもよいことに気がつくであろう。
【０４４７】
また、複数ＰＫＧスキームは、上記セクション３、注釈３Ｂに説明したケースまで拡張することができる（倍数は、ｗのものを使用する）。
【０４４８】
（注釈７．１Ａ）
ある単一ＰＫＧの実施形態及び複数のＰＫＧ実施形態において、Ｇ２及び
【数９１】
2008508836.tif 000094
【０４４９】
は、検証のためだけに使用されており（上記等式（２）及び（４）を参照）、ＰＫＧによって生成される必要はない。それらは、検証者によって生成され得る。
【０４５０】
複数ＰＫＧの場合、群Ｇ２及びペアリング
【数９２】
2008508836.tif 000095
【０４５１】
が、ＰＫＧによって生成されているならば、相異なるＰＫＧは、相異なるペア
【数９３】
2008508836.tif 000096
【０４５２】
を生成することができる。
【０４５３】
検証者は、署名の検証（４）のために、ペア
【数９４】
2008508836.tif 000097
【０４５４】
の何れかを選択するか、又は、等式（４）が相異なる（可能であれば全ての）ペア
【数９５】
2008508836.tif 000098
【０４５５】
に対しても成り立つかどうかを検証することによって署名を検証することができる。
【０４５６】
（７．２  多重署名）
上記セクション６において説明した多重署名スキームは、拡張され、署名者に１つ以上のＰＫＧから署名者の秘密鍵を得ることができるようにすることができる。
【０４５７】
以下に、２つのＰＫＧを有する多重署名スキームを説明する。２つのＰＫＧから、それ以上のＰＫＧへの拡張は、明らかである。
【０４５８】
（設定）
ＰＫＧ１及びＰＫＧ２は共に、次のように同じパラメータの多くを使用する。例えば、
１．  ある素数位数ｑの群Ｇ１及びＧ２、及び、許可ペアリング
【数９６】
2008508836.tif 000099
【０４５９】
２．  任意のジェネレータＰ∈Ｇ１
３．  暗号論的ハッシュ関数Ｈ２：｛０，１｝→Ｇ１
ＰＫＧ１は、ランダムなｓ１∈Ｚ/ｑＺを取り、Ｑ１＝ｓ１Ｐを設定する。同様に、ＰＫＧ２は、ｓ２及びＱ２を生成する。
【０４６０】
２つのＰＫＧが、Ｈ１の代わりに使用するハッシュ関数は、同じでも異なってもよい。
【０４６１】
下に説明する好適な実施形態では、我々は、ハッシュ関数が同じであると仮定するが、ＰＫＧ１が、この関数を使用する時は、Ｈ１への入力としてＱ１の値を含み、一方、ＰＫＧ２が、この関数を使用する時は、Ｈ１への入力としてＱ２の値を含むことによって、その出力が異なっていることを（高い確率で）保証する。
【０４６２】
ＰＫＧ１の公開鍵は、
【数９７】
2008508836.tif 000100
【０４６３】
であり、一方、ＰＫＧ２の公開鍵は、Ｑ１の代わりにＱ２を使用する。これらの秘密は、それぞれｓ１及びｓ２である。
【０４６４】
（秘密鍵生成）
アイデンティティＩＤｉを有する署名者が、ＰＫＧ１のクライアントであるとすると、署名者は、ＰＫＧ１から、ｓ１Ｐ１，ｉの値を受け取る。ここで、Ｐ１，ｉ＝Ｈ１（Ｑ１，ＩＤｉ）∈Ｇ１である。
【０４６５】
署名者が、ＰＫＧ２のクライアントであるとすると、ｓ２Ｐ２，ｉを受け取る。ここで、Ｐ２，ｉ＝Ｈ１（Ｑ２，ＩＤｉ）∈Ｇ１である。
【０４６６】
（個別の署名）
Ｄに署名するために、（ａ∈｛１，２｝に対して）、ＰＫＧａのクライアントであるアイデンティティＩＤｉを有する署名者は、
１．  ＰＤ＝Ｈ２（Ｄ）を計算する。
【０４６７】
２．  ランダムなｒｉ∈Ｚ/ｑＺを生成する。
【０４６８】
３．  その署名（Ｓ’ｉ，Ｔ’ｉ）を計算する。ここで、Ｓ’ｉ＝ｒｉＰＤ＋ｓａＰａ，ｉ及びＴ’ｉ＝ｒｉＰである。
【０４６９】
（アグリゲーション）
誰もが、同じ文書Ｄを使用する個別の署名のコレクションをアグリゲートすることができる。
【０４７０】
例えば、１≦ｉ≦ｎに対する個別の署名（ｗ，Ｓ’ｉ，Ｔ’ｉ）を、（Ｓｎ，Ｔｎ）に集約することができる。ここで、
【数９８】
2008508836.tif 000101
【０４７１】
である。
【０４７２】
（検証）
（Ｓｎ，Ｔｎ）をアイデンティティに基づくアグリゲート署名とする（ここで、ｎは、署名者数である）。
【０４７３】
Ｉ１を、ｉ番目の署名者が、ＰＫＧ２のクライアントである［１，ｎ］における指数ｉの集合とする。Ｉ２を、ＰＫＧ２に対する指数の対応する（かつ、補足的な）集合とする。検証者は、
【数９９】
2008508836.tif 000102
【０４７４】
を確認する。
【０４７５】
この複数ＰＫＧの多重署名スキームにおけるＰＫＧは、上述したように、非階層的クライアント構造に対する秘密鍵生成を監視する独立したＰＫＧだけではなく、階層的なアイデンティティに基づく暗号システムにおいてレベルの低いＰＫＧであってもよい。注釈７．１Ａは、多重署名に適用することができる。
【０４７６】
（８．安全性が証明されていない決定論的なアイデンティティに基づくアグリゲート署名スキーム）
ここで、アグリゲート署名が決定論的である（すなわち、所与のＰＫＧ、アイデンティティの集合、文書の集合に対して一意的である）、アイデンティティに基づくアグリゲート署名スキームの他の実施形態について説明する。
【０４７７】
本実施形態の欠点は、１つ前のものと比較して、このスキームに対しては、厳密な安全性の立証を見出すことができないことである。
【０４７８】
（設定）
秘密鍵ジェネレータ（ＰＫＧ）は、適切なＲＳＡタイプのモジュラスｎを生成する。但し、例えば、ｎが、２つのランダムに選択された適当に大きな素数ｑ０及びｑ１の積であり、ｑ０及びｑ１のそれぞれは、ある実施形態において、少なくとも５１２ビットの長さを有する。
【０４７９】
また、ＰＫＧは、ハッシュ関数Ｈ１：｛０，１｝＊→Ｚ/ｑＺ及びＨ２：｛０，１｝＊→｛０，１｝ｋも生成する。但し、ｋは、適当に長い、例えば、１２８である。
【０４８０】
また、ＰＫＧは、許可ペアリング
【数１００】
2008508836.tif 000103
【０４８１】
を有する位数ｎの群Ｇ１及びＧ２を生成する。ＰＫＧは、ジェネレータＰ∈Ｇ１を選択する。
【０４８２】
例えば、楕円曲線群の位数が、あるＬに対してｐＬ＋１であるように、素数ｐを法とする整数のフィールドＦｐ上の超特異な楕円曲線を得ることは簡単なことである。
【０４８３】
ｎ｜（ｐＬ＋１）ならば（すなわち、ｎがｐＬ＋１を割り切るのであれば）、位数ｎの部分集合が存在する。ＰＫＧの秘密は、ｑ０及びｑ１である。ＰＫＧの公開鍵は、（ｎ，Ｈ１，Ｈ２）である。
【０４８４】
（秘密鍵生成）
アイデンティティＩＤｉを有するクライアントは、ＰＫＧから、１≦ｊ≦ｋに対する秘密値ａｉ，ｊ＝Ｈ１（ＩＤｉ，ｊ）１/２（ｍｏｄ  ｎ）を受け取る。明らかに、Ｚ/ｎＺにおける全ての数が平方剰余であるというわけではない。
【０４８５】
しかしながら、これを処理する当技術分野において公知である標準的な技術がある。例えば、ｂｉ，ｊ＝Ｈ１（ＩＤｉ，ｊ）１/２（ｍｏｄ  ｎ）とする。そうすれば、ｂｉ，ｊ、２ｂｉ，ｊ、−ｂｉ，ｊ、−２ｂｉ，ｊの１つが、ｎを法とする平方剰余である。
【０４８６】
ｃｉ，ｊｂｉ，ｊが、平方剰余であるように、ｃｉ，ｊを、数１、−１、２、−２のリストにおける１番目とする。そうすれば、ＰＫＧは、１≦ｊ≦ｋに対して、ａｉ，ｊ＝［ｃｉ，ｊＨ１（ＩＤｉ，ｊ）１/２（ｍｏｄ  ｎ）を設定する。
【０４８７】
なお、誰もが、１≦ｊ≦ｋに対する「公開鍵」ｂｉ，ｊ＝Ｈ１（ＩＤｉ，ｊ）１/２（ｍｏｄ  ｎ）を計算することができることに留意されたい。
【０４８８】
（署名）
Ｓｉ−１∈Ｇ１を、文書（Ｄ１，…，Ｄｉ−１）の第１のｉ―１署名者によって生成されたアイデンティティに基づくアグリゲート署名とする（Ｓ０＝Ｐと設定する）。
【０４８９】
Ｄｉの署名を含むために、ｉ番目の署名者は、ｅｉ＝Ｈ２（Ｄｉ）を計算する。ｅｉ，ｊ＝（ｉ，ｊ）を、ｅｉのｊ番目のビットとする。署名者は、
【数１０１】
2008508836.tif 000104
【０４９０】
を計算する。
【０４９１】
（検証）
ｍが、署名者数であるとすれば、
【数１０２】
2008508836.tif 000105
【０４９２】
を確認する。ここで、
【数１０３】
2008508836.tif 000106
【０４９３】
であり、ｅｉ，ｊは、上述したように計算される。
【０４９４】
検証者は、この検証を行うために複数のｃｉ，ｊを必要とする。各ｃｉ，ｊは、２ビットの数値である。
【０４９５】
幾つかの実施形態において、署名者１（第１の署名者）は、その係数ｃ１，ｊ（１≦ｊ≦ｋ）を、次の署名者２に提供する。
【０４９６】
署名者２は、その係数ｃ１，ｊ及びｃ２，ｊ（１≦ｊ≦ｋ）を、署名者３に提供する。
【０４９７】
これを繰り返す。最後の署名者は、係数ｃｉ，ｊの全てを検証者に提供する。これらの係数は、全体の長さでせいぜい２ｍｋビット（２つのビット毎に、ｍｋ個の係数）である。
【０４９８】
他の実施形態は、検証者が、積
【数１０４】
2008508836.tif 000107
【０４９９】
だけを必要とするという観察に基づいている。
【０５００】
この実施形態において、署名者１は、積
【数１０５】
2008508836.tif 000108
【０５０１】
を署名者２に提供する。
【０５０２】
署名者２は、積
【数１０６】
2008508836.tif 000109
【０５０３】
を次の署名者に提供する。
【０５０４】
その後、このプロセスを繰り返す。最後の署名者は、積
【数１０７】
2008508836.tif 000110
【０５０５】
を計算し、この積を検証者に提供する。
【０５０６】
Ｃの大きさは、（各｜ｃｉ，ｊ｜≦２であるので）、せいぜい２ｍｋであり、２の累乗である。
【０５０７】
その結果、Ｃの署名及び値ｌｏｇ２｜Ｃ｜だけを検証者に提供する必要がある。この情報の大きさは、ｌｏｇ２｜Ｃ｜≦ｍｋであるので、せいぜい２＋ｌｏｇ２ｍｋビットである。
【０５０８】
本発明は、上述した実施形態に限定されるものではない。特に、本発明は、特定の群Ｇ１又はＧ２の何れにも限定されるものではない。
【０５０９】
幾つかの実施形態において、Ｇ１又はＧ２は、
【数１０８】
2008508836.tif 000111
【０５１０】
（素数の冪ｐを法とする整数のガロア域Ｆｐの単元群）、又は、
【数１０９】
2008508836.tif 000112
【０５１１】
（素数の冪ｐの既約多項式を法とする多項式のガロア域
【数１１０】
2008508836.tif 000113
【０５１２】
の単元群）であることが可能である。
【０５１３】
幾つかの実施形態において、ｐ＝２である。幾つかの実施形態において、群Ｇ１は、
【数１１１】
2008508836.tif 000114
【０５１４】
、又は、Ｆｐ、又は、他の領域の楕円曲線、又は、上述した領域の何れかのアーベルバラエティである。
【０５１５】
公知のように、フィールドＦの楕円曲線は、次のものから構成される。
【０５１６】
（１）  ｘ及びｙがＦの中にあるペア（ｘ，ｙ）の集合
定義済み整数のａとｂに対して、ｆ（ｘ，ｙ）＝ｙ２−ｘ３−ａｘ−ｂ＝０である。
【０５１７】
（２）  以下のように定義された群演算によって「無限大」でのポイントＯ
１．Ｏ＋Ｏ＝Ｏ
２．（ｘ，ｙ）＋Ｏ＝（ｘ，ｙ）
３．（ｘ，ｙ）＋（ｘ，−ｙ）＝Ｏ
４．ｘ１≠ｘ２のような任意の相異なる点（ｘ１，ｙ１）及び（ｘ２，ｙ２）に対して、その和（ｘ３，ｙ３）が、以下のように定義されている。
【０５１８】
Ｌ＝（ｙ２−ｙ１）/（ｘ２−ｘ１）
ｘ３＝Ｌ２−ｘ１−ｘ２，
ｙ３＝Ｌ（ｘ１−ｘ２）−ｙ１ 
５．任意の点（ｘ１，ｙ１）に対して、その倍加（ｘ１，ｙ１）＋（ｘ１，ｙ１）＝（ｘ２，ｙ２）は、以下のように定義される。
【数１１２】
2008508836.tif 000115
【０５１９】
例えば、共に、この参照により引用に含まれる、１９９９年７月１７日に公開されたＰＣＴ出願番号ＷＯ９９３０４５８、及び、２００４年８月１７日に発行された米国特許第６７７８６６６Ｂ１を参照されたい。
【０５２０】
楕円曲線は、ｆ（ｘ，ｙ）の微分が、曲線のあるポイントで同時に零になれば、超特異と呼ばれる。この条件は、４ａ３＋２７ｂ２＝０と同等である。
【０５２１】
幾つかの実施形態においては、超特異及び非超特異な楕円曲線の両方を、群Ｇ１及びＧ２に使用することができる。また、楕円曲線の多次元の一般化であるアーベルバラエティも使用することができる。
【０５２２】
幾つかの実施形態において、双線型ペアリング
【数１１３】
2008508836.tif 000116
【０５２３】
は、Ｗｅｉｌペアリング、又は、Ｔａｔｅペアリングである。
【０５２４】
これらのペアリングは、Ｄａｎ  Ｂｏｎｅｈ及びＭａｔｔｈｅｗ  Ｆｒａｎｋｌｉｎ著のこの参照により引用に含まれる「Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  Ｐａｉｒｉｎｇ」（ＳＩＡＭＪ of Computing．３２巻、Ｎｏ．３、ｐｐ．５８６−６１５、２００３年）において定義されている。
【０５２５】
本発明は、如何なる特定のハッシュ関数にも限定されない。ハッシュ関数に関して、衝突耐性を反転できないことが望ましいが、必須ではない。
【０５２６】
適切な非制限的な例には、この参照により引用に含まれる「ＳＥＣＵＲＥ  ＨＡＳＨ  ＳＩＧＮＡＴＵＲＥ  ＳＴＡＮＤＡＲＤ」（Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄ  Ｐｕｂｌｉｃａｔｉｏｎ、２００２年8月1日、Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ、米国）に特定されているＳＨＡ−１、ＳＨＡ−２５６、ＳＨＡ−３８４、ＳＨＡ−５１２が含まれる。
【０５２７】
本発明は、コルモゴロフ計算量の低い署名スキームにも、またアイデンティティに基づく署名スキームにも限定されない。
【０５２８】
アイデンティティに基づくスキームにおいて、署名者のアイデンティティは、人間、法人、他の企業、又は、他のエンティティであってよい。
【０５２９】
アイデンティティには、人又は企業の名前、通り、電子メールアドレス、電話番号、ウェブページアドレス、署名者によって提供されなくても検証者によって解明することができるその他の情報の全て又は一部を含むことができる。
【０５３０】
上述したアルゴリズムにおいて、Ｚ/ｑＺ（例えば、ＰＫＧの秘密鍵ｓ）等の剰余類の要素は、単に整数として表すことができる。
【０５３１】
それは、任意の整数、例えば、［１，ｑ−１］又は［２，ｑ−１］、或いは、［−（ｑ−１）/２，（ｑ−１）/２］であってよい。
【０５３２】
また、本発明は、有限群である群Ｇ１及びＧ２に制限されない。他の実施形態及び変形例は、添付した特許請求の範囲により定義される本発明の範囲内である。
【図面の簡単な説明】
【０５３３】
【図１】図１は、本発明の実施形態のいくつかを実装するのに適したネットワーク化されたコンピュータシステムを示す。
【符号の説明】
【０５３４】
１０４…コンピュータシステム
１１０…プロセッサ
１２０…メモリ
１３０…ネットワーク
【図１】
2008508836.tif 000139
【手続補正書】
【提出日】平成19年2月6日(2007.2.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
文書Ｄに第１のデジタル署名を生成するシステムに実装された方法であって、
定義済み巡回群Ｇ１の複数の項の和Ｓ１を表す信号を生成する工程を有し、
前記項は、ｋ個の項
【数１】
2008508836.tif 000140
を含み、
ｋ及びｓは、前記文書Ｄから独立した定義済み整数であり、
ｋ＞１であり、
Ｃ１，…Ｃｋは、整数であり、
Ｃ１，…Ｃｋのうちの少なくとも２つは、互いに異なり、
Ｃ１，…Ｃｋのうちの少なくとも１つは、前記文書Ｄによって決まり、
Ｐ１，…Ｐｋは、前記文書Ｄから独立した前記群Ｇ１のｋ個の相異なる要素であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を示すことを特徴とする方法。
【請求項２】
Ｇ１は、３より大きい素数位数の有限群であり、
Ｃ１，…Ｃｋの各々は、Ｇ１の謂数よりも小さいことを特徴とする請求項１に記載の方法。
【請求項３】
前記要素Ｐ１，…Ｐｋは、署名者のアイデンティティの関数であることを特徴とする請求項１に記載の方法。
【請求項４】
ランダムな整数ｒを生成する工程と、
項ｒＰｗを決定する工程とを有し、
Ｐｗは、前記群の要素であり、
前記和Ｓ１に対する前記複数の項は、前記項ｒＰｗを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記第１のデジタル署名は、前記和Ｓ１を表す第１のコンポーネントを含む１つ以上のコンポーネントの集合を含み、
前記方法は、１つ以上の第２のデジタル署名と共に前記第１のデジタル署名を集約して第１のアグリゲートデジタル署名を取得する工程を有し、
各第２のデジタル署名は、個別のデジタル署名、又は、個別のデジタル署名のアグリゲートを含むアグリゲートデジタル署名であり、
各第２のデジタル署名は、前記群Ｇ１の要素である第１のコンポーネントを含む１つ以上のコンポーネントの集合を含み、
前記第１のアグリゲートデジタル署名を取得するための前記集約する工程は、前記第１のデジタル署名の前記第１のコンポーネントを、前記１つ以上の第２のデジタル署名の前記１つ以上の第１のコンポーネントに加算する工程を有することを含む請求項１に記載の方法。
【請求項６】
各個別のデジタル署名は、和Ｓ１を表す信号を生成する前記工程のインスタンスによって生成され、
各インスタンスは、前記第１のデジタル署名に関する前記同じ群Ｇ１及び同じ整数ｋを用いて実行され、同じ又は異なるパラメータｓ，Ｐ１，…，Ｐｋ，Ｄ，Ｃ１，…，Ｃｋを用いて実行されることを特徴とする請求項５に記載の方法。
【請求項７】
前記第１のデジタル署名の各和Ｓ１の項、及び、各個別のデジタル署名の項は、項ｒＰｗを含み、
Ｐｗは、前記群Ｇ１の要素であり、
rは、整数であり、
Ｐｗは、前記第１のデジタル署名及び各個別のデジタル署名に対して同じであり、
rは、前記第１のデジタル署名及び各個別のデジタル署名に対して同じ又は異なり、
前記第１のアグリゲートデジタル署名は、繰り返しｋ回以上生成され、
前記項Ｐｗは、多くてもｋ回は変わらないままであることを特徴とする請求項６の方法。
【請求項８】
前記Ｐｗは、２進数の入力文字列からハッシュ関数として生成される請求項７の方法。
【請求項９】
第１のアグリゲートデジタル署名を生成する、システムに実装された方法であって、
前記第１のアグリゲートデジタル署名は、複数の個別のデジタル署名ＩＳ_１,…ＩＳ_ｎのアグリゲートを含み、
ｎは、１より大きい整数であり、
各個別のデジタル署名ＩＳ_ｉ(ｉ＝１，…ｎ)は、対応する文書Ｄ_ｉの署名であり、
各署名ＩＳ_ｉは、定義済み巡回群Ｇ１の複数の項の和を表す第１のコンポーネントＳ_ｉを含み、
前記項は、ｋ個の項
【数２】
2008508836.tif 000141
を含み、
ｋ及びｓ_ｉは、前記文書Ｄ_ｉから独立した定義済み整数であり、
ｋ＞１であり、
Ｃ１_ｉ，…Ｃｋ_ｉは、整数であり、
Ｃ１_ｉ，…Ｃｋ_ｉのうちの少なくとも２つは、互いに異なり、
Ｃ１_ｉ，…Ｃｋ_ｉのうちの少なくとも１つは、前記文書Ｄ_ｉによって決まり、
Ｐ１_ｉ，…Ｐｋ_ｉは、前記文書Ｄ_ｉから独立した前記群Ｇ１のｋ個の相異なる要素であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を示し、
前記第１のアグリゲートデジタル署名は、前記和Ｓ_ｉの和Ｓを表す第１のコンポーネントを含み、
前記方法は、
前記和Ｓの項を受け取る工程と、
前記和Ｓの前記項を加算する工程とを有し、
前記和Ｓの各項は、前記和Ｓ_ｉのうちの１又は複数の前記和Ｓ_ｉの和を表すことを特徴とする方法。
【請求項１０】
各署名ＩＳ_ｉに対して、前記対応する要素Ｐ１_ｉ，…，Ｐｋ_ｉは、前記署名ＩＳ_ｉに関連付けられた署名者のアイデンティティの関数であることを特徴とする請求項９に記載の方法。
【請求項１１】
各署名ＩＳ_ｉは、第２のコンポーネントＴ_ｉ＝ｒ_ｉ＊Ｐを更に含み、
ｒ_ｉは、整数であり、Ｐは、前記群Ｇ１の定義済み要素であり、
Ｐは、ｉから独立であり、
前記第１のアグリゲート署名は、前記コンポーネントＴ_ｉの和を表す第２のコンポーネントを更に含み、
前記方法は、
前記コンポーネントＴの項を受け取る工程と、
前記コンポーネントＴの前記項を加算する工程とを有し、
前記コンポーネントＴの各項は、前記コンポーネントＴ_ｉのうちの１つ又は複数の前記コンポーネントＴ_ｉの和を表すことを特徴とする請求項９に記載の方法。
【請求項１２】
デジタル署名ＤＳ１を検証して、前記デジタル署名ＤＳ１が請求項２の方法によって構成されているかどうかを判断するシステムに実装された方法であって、
前記デジタル署名ＤＳ１は、和Ｓ１に対応する第１のコンポーネントＣＯＭＰ１を含み、
前記方法は、等式
【数３】
2008508836.tif 000142
を検証し、
ｂｐ１は、Ｇ１×Ｇ１から群Ｇ２への非縮退双線型ペアリングであり、
ｆ１は、前記群Ｇ２の要素であり、
「＆」は、前記群Ｇ２の群演算であり、
ｐは、前記群Ｇ１の要素であり、
Ｑ＝ｓ＊Ｐであり、
【数４】
2008508836.tif 000143
であることを特徴とする方法。
【請求項１３】
Ｇ１及びＧ２は、３より大きい同じ素数位数を有する有限巡回群であり、
Ｐは、前記群Ｇ１のジェネレータであることを特徴とする請求項１２に記載の方法。
【請求項１４】
署名者のアイデンティティから前記要素Ｐ１，…，Ｐｋを決定する工程を更に含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
第１のアグリゲートデジタル署名を検証して、前記第１のアグリゲートデジタル署名が、個別のデジタル署名ＩＳ_１,…ＩＳ_ｎのアグリゲートを含むかどうかを判断するシステムに実装された方法であって、
ｎは、１より大きい整数であり、
各個別のデジタル署名ＩＳ_ｉ（ｉ＝１，…ｎ）は、対応する文書Ｄ_ｉの署名であり、
各個別のデジタル署名ＩＳ_ｉは、定義済み巡回群Ｇ１の複数の項の和Ｓ１_ｉである第１のコンポーネントを含む１つ以上のコンポーネントの集合を含み、
前記項は、ｋ個の項
【数５】
2008508836.tif 000144
を含み、
ｋは、１より大きい定義済み整数であり、
ｋは、前記文書Ｄ_１,…Ｄ_ｎから独立であり、
ｋは、前記個別のデジタル署名ＩＳ_ｉの全てに対して同じであり、
各個別のデジタル署名ＩＳ_ｉに対して、
（i）ｓは、前記文書Ｄ_１,…Ｄ_ｎから独立した定義済み整数であり、
（ii）Ｃ１_ｉ,…Ｃｋ_ｉは、非負整数であり、
Ｃ１_ｉ,…Ｃｋ_ｉのうちの少なくとも２つは、互いに異なっており、
Ｃ１_ｉ,…Ｃｋ_ｉのうちの少なくとも１つは、前記対応する文書Ｄ_ｉによって決まり、
（iii）Ｐ１_ｉi,…Ｐｋ_ｉは、前記文書Ｄ_１,…Ｄ_ｎから独立した前記群Ｇ１のｋ個の相異なる要素であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を示し、
前記個別のデジタル署名のアグリゲートは、前記和Ｓ_ｉの和Ｓであるコンポーネント
【数５Ａ】
2008508836.tif 000145
を含み、
前記第１のアグリゲートデジタル署名は、対応するコンポーネントＳｎを含み、
前記方法は、等式
【数６】
2008508836.tif 000146
を検証する工程を有し、
ｂｐ１は、Ｇ１×Ｇ１から群Ｇ２への非縮退双線型ペアリングであり、
Ｐは、前記群Ｇ１のジェネレータであり、
ｆ１は、前記群Ｇ２の要素であり、
「＆」は、前記群Ｇ２の群演算であり、
条件（Ａ）又は条件（Ｂ）のどちらかが真であり、
前記条件（Ａ）は、前記ｓパラメータが、前記個別のデジタル署名の全てに対して同じ値を有し、
【数７】
2008508836.tif 000147
であり
Ｑ＝ｓ＊Ｐであり、
【数７Ａ】
2008508836.tif 000148
が、１からｎまでの全てのｉについて取られる前記項
【数８】
2008508836.tif 000149
の和であるという条件であり、
前記条件（Ｂ）は、前記ｓパラメータが、Ｌ個の相異なる値ｓ_１,…ｓ_Ｌに分布し、
Ｌ＞１であり、
各値ｓ＝ｓ_ｊ（ｊ＝１,…Ｌ）が、１つ以上の前記個別のデジタル署名ＩＳ_ｉに対応し、
【数９】
2008508836.tif 000150
であり、
各ｊ＝１,…Ｌに対して、Ｑ_ｊ=ｓ_ｊ＊Ｐであり、
【数９Ａ】
2008508836.tif 000151
は、前記個別のデジタル署名ＩＳ_ｉが、前記値ｓ_ｊに対応するように、全てのｉについて取られる前記項
【数１０】
2008508836.tif 000152
の和であるという条件であることを特徴とする方法。
【請求項１６】
Ｇ１及びＧ２は、３より大きい同じ素数位数を有する有限群であり、
各個別の署名ＩＳ_ｉに対して、ｓ，Ｃ１_ｉ，…，Ｃｋ_ｉのそれぞれは、Ｇ１の前記位数より小さいことを特徴とする請求項１５に記載の方法。
【請求項１７】
各署名ＩＳ_ｉに対して、前記要素Ｐ１，…，Ｐｋを、前記署名ＩＳ_ｉに関連付けられた署名者のアイデンティティから決定する工程を更に含むことを特徴とする請求項１５に記載の方法。
【請求項１８】
秘密鍵を生成する方法であって、
（１）エンティティのアイデンティティＩＤ１を受け取る工程と、
（２）前記アイデンティティＩＤ１から、定義済み巡回群Ｇ１のｋ個の要素Ｐ１,…Ｐｋを生成する工程とを有し、
ｋ＞１であり、
【数１１】
2008508836.tif 000153
であり、
Ｈ１は、前記群Ｇ１に像を有する定義済み関数であり、
ｐａｒ_１,…ｐａｒ_ｋは、定義済みの相異なるパラメータであり、
ｓは、整数であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表すことを特徴とする方法。
【請求項１９】
前記方法は、同じ群Ｇ１及び同じパラメータｓ及び同じ関数Ｈ１を有する相異なるエンティティのアイデンティティに応答して繰り返し実行されることを特徴とする請求項１８に記載の方法。
【請求項２０】
Ｇ１は、３より大きい素数位数を有し、
ｓは、Ｇ１の前記位数より小さいことを特徴とする請求項１８に記載の方法。
【請求項２１】
文書Ｄに第１のアグリゲートデジタル署名を生成するシステムに実装された方法であって、
第１のアグリゲートデジタル署名は、複数の個別のデジタル署名ＩＳ_１,…ＩＳ_ｎのアグリゲートを含み、
ｎは、１より大きい整数であり、
各個別のデジタル署名ＩＳ_ｉ（ｉ＝１,…,ｎ）は、定義済み巡回群Ｇ１の複数の項の和Ｓ_ｉを表す第１のコンポーネントを含み、
前記項は、項ｒ_ｉ＊ＰＤ及び（ｓ_ｉ＊Ｐ_ｉ）を含み、
ｒ_ｉ及びｓ_ｉは、前記文書Ｄから独立した整数であり、
ＰＤ及びＰ_ｉは、前記群Ｇ１の要素であり、
ＰＤは、前記文書Ｄによって決まり、全ての前記署名ＩＳ_ｉに対して同じであり、
Ｐ_ｉは、前記文書Ｄから独立であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表し、
前記第１のアグリゲートデジタル署名は、前記和Ｓ_ｉの和Ｓを表すコンポーネントを含み、
前記方法は、
前記和Ｓの項を受け取る工程と、
前記和Ｓの前記項を加算する工程とを有し、
前記和Ｓの各項は、前記和Ｓ_ｉiの１つ又は複数の前記和Ｓ_ｉの和を表すことを特徴とする方法。
【請求項２２】
Ｇ１は、３より大きい素数位数を有し、
ｓ_ｉ及びｒ_ｉのそれぞれは、Ｇ１の前記位数より小さいことを特徴とする請求項２１に記載の方法。
【請求項２３】
各署名ＩＳ_ｉに対して、前記要素Ｐ_ｉは、前記署名ＩＳ_ｉに関連付けられた署名者のアイデンティティの関数であることを特徴とする請求項２１に記載の方法。
【請求項２４】
第１のアグリゲートデジタル署名を検証して、前記第１のアグリゲートデジタル署名が、個別のデジタル署名ＩＳ_１,…ＩＳ_ｎのアグリゲートを含むかどうかを判断するシステムに実装された方法であって、
ｎは、１より大きい整数であり、
各個別のデジタル署名ＩＳ_ｉ（ｉ＝１,…ｎ）が、全ての前記署名ＩＳ_ｉに対して同じ文書である文書Ｄの署名であり、
各個別のデジタル署名ＩＳ_ｉは、定義済み巡回群Ｇ１の複数の項の和Ｓ１_ｉである第１のコンポーネントを含む１つ以上のコンポーネントの集合を含み、
前記項は、ｋ個の項ｒ_ｉ＊ＰＤ及び（ｓ＊Ｐ_ｉ）を含み、
ｒ_ｉ及びｓは、前記文書Ｄから独立した整数であり、
ＰＤ及びＰ_ｉは、前記群Ｇ１の要素であり、
ＰＤは、前記文書Ｄによって決まり、前記署名ＩＳ_ｉの全てに対して同じであり、
Ｐ_ｉは、前記文書Ｄから独立であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表し、
前記第１のアグリゲートデジタル署名は、前記和Ｓ_ｉの和Ｓに対応するコンポーネントＳｎを含み、
前記個別のデジタル署名の前記アグリゲートは、前記和Ｓ１_ｉの和であるコンポーネント
【数１１Ａ】
2008508836.tif 000154
を含み、
前記第１のアグリゲートデジタル署名は、対応するコンポーネントＳｎを含み、
前記方法は、等式
【数１２】
2008508836.tif 000155
を検証し、
ｂｐ１は、Ｇ１×Ｇ１から群Ｇ２への非縮退双線型ペアリングであり、
Ｐは、前記群Ｇ１のジェネレータであり、
ｆ１は、前記群Ｇ２の要素であり、
「＆」は、前記群Ｇ２の群演算であり、
条件（Ａ）又は（Ｂ）のどちらかが真であり、
前記条件（Ａ）は、前記ｓパラメータが、前記個別のデジタル署名ＩＳ_ｉの全てに対して同じ値を有し、
【数１３】
2008508836.tif 000156
であり、
Ｑ＝ｓ＊Ｐであり、
【数１４】
2008508836.tif 000157
であるという条件であり、
前記条件（Ｂ）は、前記ｓパラメータが、Ｌ個の相異なる値ｓ_１,…ｓ_Ｌに分布し、
Ｌ＞１であり、
各値ｓ＝ｓ_ｊ（ｊ＝１,…Ｌ）は、１つ以上の前記個別のデジタル署名ＩＳ_ｊに対応し、
【数１５】
2008508836.tif 000158
であり、
各ｊ=１,…Ｌに対して、Ｑ_ｊ=ｓ_ｊ＊Ｐであり、
【数１６】
2008508836.tif 000159
は、前記値ｓ_ｊに対応する前記個別のデジタル署名の全てについて取られる前記項Ｐ_ｉの和であるという条件であることを特徴とする方法。
【請求項２５】
前記条件（Ａ）は、真であることを特徴とする請求項２４に記載の方法。
【請求項２６】
Ｇ１は、３より大きい素数位数を有し、
Ｇ２は、Ｇ１と同じ位数の巡回群であり、
前記整数ｓ及びｒ_ｉのそれぞれは、Ｇ１の前記位数より小さいことを特徴とする請求項２４に記載の方法。
【請求項２７】
各署名ＩＳ_ｉに対して、前記要素Ｐ_ｉは、前記署名ＩＳ_ｉに関連付けられた署名者のアイデンティティの関数であることを特徴とする請求項２４に記載の方法。
【請求項２８】
ｍ人の署名者の署名を表す第１のデジタル署名を生成するシステムに実装された方法であって、
ｍは、正の整数であり、
各署名者ｊ（ｊ＝１，…ｍ）は、鍵（ａ_ｊ,１,…ａ_ｊ,ｋ）に関連付けられたエンティティであり、
ｋは、正の整数であり、
ａ_ｊ,１,…ａ_ｊ,ｋは、整数であり、
前記方法は、
（１）前記署名者ｍに関連付けられた文書Ｄ_ｍの関数であるｋビット（ｅ_１,…ｅ_ｋ）を生成する工程と、
（２）定義済み巡回群Ｇ１の項を生成する工程とを有し、
前記項は、
【数１７】
2008508836.tif 000160
であり、
【数１８】
2008508836.tif 000161
は、定義済み正の整数ｎを法とする整数の環Ｚ/ｎＺにおける乗法であり、
Ｓ_ＰＲＥＶ_ｍは、前記群Ｇ１の要素であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表すことを特徴とする方法。
【請求項２９】
ｍ＝１であり、
Ｓ_ＰＲＥＶ_ｍは、前記群Ｇ１のジェネレータであることを特徴とする請求項２８に記載の方法。
【請求項３０】
ｍ＞１であり、
Ｓ_ＰＲＥＶ_ｍは、署名者１，…，ｍ−１のそれぞれ及び前記それぞれの文書Ｄ_１，…，Ｄ_（ｍ−１）に対して、前記工程（１）及び（２）を実行することによって求められることを特徴とする請求項２８に記載の方法。
【請求項３１】
Ｇ１は、前記整数ｎと等しい位数の有限であることを特徴とする請求項２８に記載の方法。
【請求項３２】
ｎは、それぞれが１より大きい２つの素数の積であることを特徴とする請求項２８に記載の方法。
【請求項３３】
各鍵（ａ_ｉ，１，…，ａ_ｉ，ｋ）は、前記署名者ｊのアイデンティティの関数であることを特徴とする請求項２８に記載の方法。
【請求項３４】
秘密鍵を生成するシステムに実装された方法であって、
エンティティのアイデンティティＩＤ１を受け取る工程と、
前記アイデンティティＩＤ１から、定義済み正の整数ｎを法とする剰余類を表すｋ個の整数ａ_１,…ａ_ｋを生成する工程とを有し、
ｋ＞１は、整数であり、
ｊ＝１,…ｋに対して、ａ_ｊ＝（Ｈ１（ＩＤ１,ｐａｒ_ｊ））1/2（ｍｏｄ  ｎ）であり、
Ｈ１は、Ｚ/ｎＺに像を有する定義済み関数であり、
ｐａｒ_１,…ｐａｒ_ｋは、定義済みの相異なるパラメータであることを特徴とする方法。
【請求項３５】
Ｈ１（・）＝ｆ１＊ＨＦ（・）であり、
Ｈ１（・）は、Ｚ/ｎＺに像を有する定義済み関数であり、
ｆ１は、１，-１，２，-２であり、
ｆ１＊ＨＦ（・）は、Ｚ/ｎＺにおける平方であることを特徴とする請求項３４に記載の方法。
【請求項３６】
ｎは、それぞれが１より大きい２つの素数の積であることを特徴とする請求項３４に記載の方法。
【請求項３７】
第１のアグリゲートデジタル署名Ｓｎを検証して、前記第１のアグリゲートデジタル署名が、それぞれの文書Ｄ_１,…Ｄ_ｍのｍ人の署名者の署名の署名を表わすかどうかを判断するシステムに実装された方法であって、
ｍ＞１であり、
各署名者ｊ（ｊ＝１,…ｍ）が、鍵（ｂ_ｊ,１,…ｂ_ｊ,ｋ）に関連付けられたエンティティであり、
ｋ,ｂ_ｊ,１1,…ｂ_ｊ,ｋは、整数であり、
Ｓｎは、ジェネレータＰを有する定義済み巡回群Ｇ１の要素であり、
前記方法は、
等式ｂｐ１（Ｓｎ,Ｓｎ）＝ｂｐ１（Ｐ,Ｐ）bを検証する工程を有し、
ｂｐ１は、Ｇ１×Ｇ１から巡回群Ｇ２への双線型写像であり、
ｂは、定義済みモジュラスｎnを法とする全ての前記整数ｂ_ｊ,ｉの積であることを特徴とする方法。
【請求項３８】
各ｂ_ｊ，ｉは、ｎを法とする平方であることを特徴とする請求項３７に記載の方法。
【請求項３９】
ｎは、それぞれが１より大きい２つの素数の積であることを特徴とする請求項３７に記載の方法。
【請求項４０】
各鍵（ｂ_ｊ，１，…，ｂ_ｊ，ｋ）は、前記署名者ｊのアイデンティティの関数であることを特徴とする請求項３７に記載の方法。
【請求項４１】
複数のコンポーネントを含む秘密暗号鍵を生成するシステムに実装された方法であって、
（１）エンティティのアイデンティティＩＤ１を受け取る工程と、
（２）前記アイデンティティＩＤ１から前記コンポーネントのうちの少なくとも２つを生成する工程とを有し、
前記コンポーネントの前記少なくとも２つは、互いに異なることを特徴とする方法。
【請求項４２】
前記少なくとも２つのコンポーネントは、前記コンポーネントの数より大きい位数の巡回群Ｇ１の要素であることを特徴とする請求項４１に記載の方法。
【請求項４３】
前記少なくとも２つのコンポーネントは、ｋより大きい位数の定義済み巡回群Ｇ１の要素Ｐ１，…，Ｐｋであり、
ｋ＞１であり、
【数１９】
2008508836.tif 000162
であり、
Ｈ１は、前記群Ｇ１に像を有する定義済み関数であり、
ｐａｒ_１，…，ｐａｒ_ｋは、定義済みの相異なるパラメータであり、
ｓは、整数であり、
「＊」は、前記群Ｇ１の要素の整数による乗法を表すことを特徴とする請求項４１に記載の方法。
【請求項４４】
前記方法は、前記同じ群Ｇ１で、相異なるエンティティのアイデンティティに応答して繰り返し実行されることを特徴とする請求項４３に記載の方法。
【請求項４５】
Ｇ１は、３より大きい素数位数を有し、
ｓは、Ｇ１の前記位数より小さいことを特徴とする請求項４３に記載の方法。
【請求項４６】
文書Ｄに第１のデジタル署名を生成するシステムに実装された方法であって、
（１）  署名者のアイデンティティの関数である複数の相異なるコンポーネントを含む署名鍵を取得する工程と、
（２）  前記コンポーネントから前記第１のデジタル署名を生成する工程とを有することを特徴とする方法。
【請求項４７】
前記コンポーネントは、前記コンポーネントの数より大きい位数の定義済み巡回群Ｇ１の要素であることを特徴とする請求項４６に記載の方法。
【請求項４８】
前記工程（２）は、前記群Ｇ１の複数の項の和Ｓ１を表す信号を生成する工程を有し、
前記項は、ｋ個の項
【数２０】
2008508836.tif 000163
を含み、
ＳＫ_１，ＳＫ_２，…，ＳＫ_ｋは、前記コンポーネントであり、
ｋは、前記コンポーネントの数であり、
Ｃ１，…，Ｃｋは、整数であり、
Ｃ１，…，Ｃｋのうちの少なくとも２つは、互いに異なり、
Ｃ１，…，Ｃｋのうちの少なくとも１つは、前記文書Ｄによって決まり、
「＊」は、前記群Ｇ１の要素である整数による乗法を表すことを特徴とする請求項４７に記載の方法。
【請求項４９】
Ｇ１の前記位数は、素数であることを特徴とする請求項４７に記載の方法。
【請求項５０】
第１のアグリゲートデジタル署名を生成するシステムに実装された方法であって、
前記第１のアグリゲートデジタル署名は、複数の個別のデジタル署名のアグリゲートを含み、
各個別のデジタル署名は、少なくとも１つの署名コンポーネントを含み、
前記方法は、
（１）  複数の第１の項を受け取る工程と、
（２）  前記第１の項から前記第１のアグリゲートデジタル署名のコンポーネントを生成する工程とを有し、
各第１の項は、前記個別のデジタル署名のうちの１つの署名コンポーネント、又は、前記個別の署名の２つ以上の署名コンポーネントの和のどちらかであり、
前記第１の項の前記署名コンポーネントのうちの少なくとも１つは、署名者の鍵の関数であり、
前記署名者の鍵は、それぞれが前記署名者のアイデンティティの関数である複数の相異なる鍵コンポーネントを含むことを特徴とする方法。
【請求項５１】
前記第１のアグリゲートデジタル署名の前記コンポーネントは、前記第１の項を含む複数の項の和であることを特徴とする請求項５０に記載の方法。
【請求項５２】
前記署名者の鍵の前記関数は、前記鍵コンポーネントのうち少なくとも２つが相異なる係数を有して存在する一次結合を含むことを特徴とする請求項５０に記載の方法。
【請求項５３】
デジタル署名ＤＳ１を検証して、前記デジタル署名ＤＳ１が、請求項７６に記載の方法によって構成されているかどうかを判断するシステムに実装された方法であって、
前記署名者のアイデンティティの少なくとも２つの相異なる関数を含む関係を検証する工程を有することを特徴とする方法。
【請求項５４】
請求項１、９、１２、１５、１８、２１、２４、２８、３４、３７、４１、４６、５０、５３のいずれか一項に記載の方法を実装することを特徴とするコンピュータシステム。
【請求項５５】
コンピュータシステムに、請求項１、９、１２、１５、１８、２１、２４、２８、３４、３７、４１、４６、５０、５３のいずれか一項に記載の方法を実行させる１つ以上のコンピュータ命令を含むことを特徴とするコンピュータで読み取り可能な媒体。