(57)【要約】署名者と検証者との間で通信されるデジタルメッセージの署名を生成して検証するための方法及びシステムが提供される。ウェイルペアリングまたはテートペアリング等のバイリニアなマッピングを使用して（１０４）、これらの方法及びシステムは、効率的なマルチ署名、同一性に基づくリング署名、階層的なプロキシ署名、階層的なオンライン／オフライン署名、を生成して検証することができる。
2005522968.tif 000002
【特許請求の範囲】
【請求項１】
複数のｍ個のメッセージに関する複数のｎ人の署名者によるマルチ署名を生成して検証する方法であって、各署名者がｍ個のメッセージの一部に署名し、最初の署名者によって署名される一部のメッセージが少なくとも一人の他の署名者によって署名される一部のメッセージと異なっており、
ｎ人の署名者の各々の秘密鍵を選択する工程と、
それぞれの秘密鍵を使用して、ｎ人の署名者の各々の公開鍵を計算する工程と、
所定のファンクションを使用して、ｍ個のメッセージの各々のメッセージファンクション値を生成する工程と、
マルチ署名の長さがｎ及びｍに依存しないように、署名者に関連付けられた秘密鍵及びメッセージファンクション値を使用して、デジタル署名を生成する工程と、
デジタルマルチ署名を検証者に対して通信する工程と、
少なくとも署名者の公開鍵及びメッセージファンクション値を使用して、デジタルマルチ署名を検証する工程と、
を備えたことを特徴とする方法。
【請求項２】
各署名者は、１つのメッセージだけに署名する
ことを特徴とする請求項１に記載の署名Ｓｉｇを生成して検証する方法。
【請求項３】
複数のｎ人の署名者によって署名される複数のｍ個のデジタルメッセージＭｊのマルチ署名Ｓｉｇを生成する方法であって、各署名者がｍ個のメッセージの一部に署名し、最初の署名者によって署名される一部のメッセージが少なくとも一人の他の署名者によって署名される一部のメッセージと異なっており、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができるバイリニアで非縮退的なペアリング
【数１】
2005522968.tif 000064
を選択する工程と、
第１の循環群Γ１のジェネレータＰを選択する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができるファンクションＨを選択する工程と、
ｎ人の署名者の各々の秘密鍵ｓｉを選択する工程と、
ファンクションＨを使用して、ｍ個のメッセージＭｊの各々のメッセージファンクション値
【数２】
2005522968.tif 000065
を生成する工程と、
デジタルマルチ署名Ｓｉｇが第１の循環群Γ１の１つの要素から成るように、署名者の秘密鍵ｓｉ及びメッセージファンクション値
【数３】
2005522968.tif 000066
を使用してデジタル署名を生成する工程と、
を備えたことを特徴とする方法。
【請求項４】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項３に記載の署名Ｓｉｇを生成する方法。
【請求項５】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項３に記載の署名Ｓｉｇを生成する方法。
【請求項６】
前記ファンクション
【数４】
2005522968.tif 000067
は、許容できるペアリングである、
ことを特徴とする請求項３に記載の署名Ｓｉｇを生成する方法。
【請求項７】
メッセージファンクション値
【数５】
2005522968.tif 000068
は、
【数６】
2005522968.tif 000069
を使用して生成される
ことを特徴とする請求項３に記載の署名Ｓｉｇを生成する方法。
【請求項８】
メッセージファンクション値
【数７】
2005522968.tif 000070
は、メッセージＭｊと、ファンクションＨと、１または複数の他のファンクション入力と、を少なくとも使用して生成される
ことを特徴とする請求項３に記載の署名Ｓｉｇを生成する方法。
【請求項９】
各署名者は、１つのメッセージだけに署名する
ことを特徴とする請求項３に記載の署名Ｓｉｇを生成する方法。
【請求項１０】
少なくとも一人の署名者が、複数のメッセージに署名する
ことを特徴とする請求項３に記載の署名Ｓｉｇを生成する方法。
【請求項１１】
複数のｎ人の署名者と一人の検証者との間で通信される複数のｍ個のデジタルメッセージＭｊのマルチ署名Ｓｉｇを生成して検証する方法であって、各署名者がｍ個のメッセージの一部に署名し、最初の署名者によって署名される一部のメッセージが少なくとも一人の他の署名者によって署名される一部のメッセージと異なっており、Ｃがｉ番目の署名者がｊ番目のメッセージに署名するといった全ての（ｉ，ｊ）対のセットを含んでいるとして、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができるバイリニアで非縮退的なペアリング
【数８】
2005522968.tif 000071
を選択する工程と、
第１の循環群Γ１のジェネレータＰを選択する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができるファンクションＨを選択する工程と、
ｎ人の署名者の各々の秘密鍵ｓｉを選択する工程と、
ファンクションＨを使用して、ｍ個のメッセージＭｊの各々のメッセージファンクション値
【数９】
2005522968.tif 000072
を生成する工程と、
Ｃ中の各（ｉ，ｊ）対毎に、署名成分
【数１０】
2005522968.tif 000073
を生成する工程と、
Ｃ中の全ての（ｉ，ｊ）対の署名成分Ｓｉｊを組み合わせて、マルチ署名
【数１１】
2005522968.tif 000074
を生成する工程と、
【数１２】
2005522968.tif 000075
を確認することにより署名を検証する工程と、
を備えたことを特徴とする方法。
【請求項１２】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項１１に記載のデジタル署名Ｓｉｇを生成する方法。
【請求項１３】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項１１に記載のデジタル署名Ｓｉｇを生成する方法。
【請求項１４】
前記ファンクション
【数１３】
2005522968.tif 000076
は、許容できるペアリングである、
ことを特徴とする請求項１１に記載のデジタル署名Ｓｉｇを生成する方法。
【請求項１５】
メッセージファンクション値
【数１４】
2005522968.tif 000077
は、
【数１５】
2005522968.tif 000078
を使用して生成される
ことを特徴とする請求項１１に記載の署名Ｓｉｇを生成する方法。
【請求項１６】
メッセージファンクション値
【数１６】
2005522968.tif 000079
は、メッセージＭｊと、ファンクションＨと、１または複数の他のファンクション入力と、を少なくとも使用して生成される
ことを特徴とする請求項１１に記載の署名Ｓｉｇを生成する方法。
【請求項１７】
各署名者は、１つのメッセージだけに署名する
ことを特徴とする請求項１１に記載のデジタル署名Ｓｉｇを生成する方法。
【請求項１８】
少なくとも一人の署名者が、複数のメッセージに署名する
ことを特徴とする請求項１１に記載のデジタル署名Ｓｉｇを生成する方法。
【請求項１９】
一人の署名者と一人の検証者との間で通信されるデジタルメッセージのリング署名を生成して検証する方法であって、署名者は１つのリングの複数のｔ人の構成員のうちの一人であり、当該リングの各構成員は同一性情報に関連付けられており、
リングのｔ人の構成員の各々の秘密鍵を選択する工程であって、各秘密鍵は各リング構成員に関連付けられた同一性情報に関連付けられている、という工程と、
各構成員の秘密鍵を使用して、リングセットのｔ人の構成員の各々の公開鍵を計算する工程であって、各公開鍵は各リング構成員に関連付けられた同一性情報に関連付けられている、という工程と、
所定のファンクションを使用してメッセージファンクション値を生成する工程と、
署名者の秘密鍵と、署名者以外の（ｔ−１）人のリング構成員の各々の公開鍵と、メッセージファンクション値と、を少なくとも使用してリング署名を生成する工程と、
各リング構成員に関連付けられた公開鍵を少なくとも使用して、リング署名がリングの一人の構成員によって生成されたことを検証する工程と、
を備えたことを特徴とする方法。
【請求項２０】
一人の署名者と一人の検証者との間で通信されるデジタルメッセージＭのリング署名Ｓｉｇを生成して検証する方法であって、署名者は１つのセットの複数のｔ人の構成員のうちの一人であり、当該セットの各構成員は同一性セット｛ＩＤ１，．．．．．，ＩＤｔ｝のうちの１つの同一性に関連付けられ、署名者は同一性ＩＤｓ（１≦ｓ≦ｔ）に関連付けられており、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができるバイリニアで非縮退的なペアリング
【数１７】
2005522968.tif 000080
を選択する工程と、
第１の循環群Γ１の第１のジェネレータＰと、第１の循環群Γ１の第２のジェネレータＰ'と、を選択する工程と、
第１のシークレット番号ｓを選択する工程と、
第２のシークレット番号ｓ'を選択する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができるファンクションＨを選択する工程と、
セット構成員に関連付けられた同一性ＩＤｉ及びファンクションＨを使用して、セットのｔ人の構成員の各々にパブリック点Ｑｉを生成する工程と、
署名者のためのプライベート点ｓＰ'＋ｓ'Ｑｓを生成する工程と、
所定のファンクションを使用して、メッセージＭのためのメッセージファンクション値ＰＭを生成する工程と、
署名者のプライベート点ｓＰ'＋ｓ'Ｑ１と、セットのｔ人の構成員の各々のパブリック点Ｑｉと、メッセージファンクション値ＰＭと、を少なくとも使用してリング署名Ｓｉｇを生成する工程と、
セットのｔ人の構成員の各々のパブリック点Ｑｉを少なくとも使用して、リング署名Ｓｉｇがセットの一人の構成員によって生成されたことを検証する工程と、
を備えたことを特徴とする方法。
【請求項２１】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項２２】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項２３】
前記ファンクション
【数１８】
2005522968.tif 000081
は、許容できるペアリングである、
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項２４】
メッセージファンクション値ＰＭは、ＰＭ＝Ｈ（Ｍ）を使用して生成される
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項２５】
メッセージファンクション値ＰＭは、メッセージＭｊと、ファンクションＨと、１または複数の他のファンクション入力と、を使用して生成される
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項２６】
パブリック点Ｑｉは、Ｑｉ＝Ｈ（ＩＤｉ）を使用して生成される
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項２７】
パブリック点Ｑｉは、各セット構成員に関連付けられた同一性ＩＤｉと、ファンクションＨと、１または複数の他のファンクション入力と、を使用して生成される
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項２８】
新たな各プライベート点の生成毎に、新たな第２のシークレット番号ｓ'が選択される
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項２９】
デジタルリング署名Ｓｉｇを生成する前記工程は、
乱数ｒＭ及びｒｉ（１≦ｉ≦ｔ）を選択する工程と、
Ｕ＝ｓＰ'＋ｓ'Ｑｓ＋ｒ１Ｑ１＋ｒ２Ｑ２＋・・・＋ｒｔＱｔ＋ｒＭＰＭ，
Ｖｓ＝ｓ'Ｐ＋ｒｓＰ、ＶＭ＝ｒＭＰ、Ｖｉ＝ｒｉＰ（１≦ｉ≦ｎ、ｉ≠ｓ）において、リング署名Ｓｉｇ＝［Ｕ，Ｖ１，．．．Ｖｔ，ＶＭ］を計算する工程と、
を更に含み、
リング署名Ｓｉｇがリングの一人の構成員によって生成されたことを検証する前記工程は、
【数１９】
2005522968.tif 000082
であることを確認する工程を更に含んでいる
ことを特徴とする請求項２０に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項３０】
ｔ人のリング構成員から成る１つのリングのためのリング署名Ｓｉｇを生成して検証する方法であって、各リング構成員は、階層型システムにおいてルートＰＫＧよりもｌｉレベル下にあり、各リング構成員は、受信者に関連付けられた同一性情報
【数２０】
2005522968.tif 000083
と、ルートＰＫＧと受信者との間の階層中にある（ｌｉ−１）個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｉｌとを含むリング構成員ＩＤ−タプル
【数２１】
2005522968.tif 000084
に関連付けられており、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができるファンクションｅを選択する工程と、
第１の循環群Γ１のルートジェネレータＰ０を選択する工程と、
ルートＰＫＧに関連付けられ且つルートＰＫＧにのみ知られたランダムルート鍵生成シークレットｓ０を選択する工程と、
ルート鍵生成パラメータＱ０＝ｓ０Ｐ０を生成する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができる第１のファンクションＨ１を選択する工程と、
第２の循環群Γ２の１つの要素から第２の二進数字列を生成することができる第２のファンクションＨ２を選択する工程と、
ｔ人のリング構成員の各々に関連付けられた（ｌｉ−１）個の先祖下位レベルＰＫＧの各々に、パブリック要素Ｐｉｌ＝Ｈ１（ＩＤｉ１，．．．，ＩＤｉｌ）（１≦ｉ≦ｔ及び１≦ｌ≦ｌｉ−１）を生成する工程と、
ｔ人のリング構成員の各々に関連付けられた（ｌｉ−１）個の先祖下位レベルＰＫＧの各々に、下位レベル鍵生成シークレットｓｉｔ（１≦ｉ≦ｔ及び１≦ｌ≦ｌｉ−１）を選択する工程と、
ｔ人のリング構成員の各々に関連付けられた（ｌｉ−１）個の先祖下位レベルＰＫＧの各々に、下位レベルシークレット要素Ｓｉｌ＝Ｓｉ（ｌ−１）＋ｓｉ（ｌ−１）Ｐｉｌ（１≦ｉ≦ｔ及び１≦ｌ≦ｌｉ−１）を生成する工程であって、ｓｉ０＝ｓ０であり、Ｓｉｏが０に規定される、という工程と、
ｔ人のリング構成員の各々に関連付けられた（ｌｉ−１）個の先祖下位レベルＰＫＧの各々に、下位レベル鍵生成パラメータＱｉｌ＝ｓｉｌＰ０（１≦ｉ≦ｔ及び１≦ｌ≦ｌｉ−１）を生成する工程と、
ｔ人のリング構成員の各々にリング構成員パブリック要素
【数２２】
2005522968.tif 000085
（１≦ｉ≦ｔ）を生成する工程と、
ｔ人のリング構成員の各々に受信者シークレット要素
【数２３】
2005522968.tif 000086
（１≦ｉ≦ｔ）を生成する工程と、
メッセージＭに署名し、署名者のプライベート点
【数２４】
2005522968.tif 000087
及び署名者以外の（ｔ−１）人のリング構成員の各々のためのＩＤ−タプル
【数２５】
2005522968.tif 000088
を少なくとも使用して、リング署名Ｓｉｇを生成する工程と、
リング署名Ｓｉｇを検証し、ｔ人のリング構成員の各々のためのＩＤ−タプル
【数２６】
2005522968.tif 000089
を少なくとも使用して、署名がリング構成員のうちの一人によって生成されたことを確認する工程と、
を備えたことを特徴とする方法。
【請求項３１】
メッセージＭに署名する前記工程は、
ｔ人のリング構成員の各々に、パブリック点−タプルＰｉｋ＝Ｈ（ＩＤｉ１，．．．．，ＩＤｉｋ）を決定する工程と、
ｔ個のパブリック点−タプルから成るセットから非冗長なパブリック点のセットＲ＝｛Ｒ１，．．．．，Ｒｘ｝を決定する工程と、
リング署名［Ｕ，Ｖ１，．．．．．，Ｖｘ，ＶＭ］を生成する工程であって、Ｕ＝ｓＰ'＋ｒ１Ｒ１＋・・・＋ｒｘＲｘ＋ｒＭＰＭであり、Ｖｋ＝ｒｋＰ（１≦ｋ≦ｘ）であり、ＶＭ＝ｒＭＰである、という工程と、
を更に含み、
リング署名を検証する前記工程は、
【数２７】
2005522968.tif 000090
であることを確認する工程を更に含んでいる
ことを特徴とする請求項３０に記載のリング署名Ｓｉｇを生成して検証する方法。
【請求項３２】
一人のプロキシ署名者と一人の検証者との間で通信されるデジタルメッセージＭのデジタルプロキシ署名Ｓｉｇを生成して検証する方法であって、最初の署名者の代わりにプロキシ署名者によってデジタルメッセージＭが署名され、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができるバイリニアで非縮退的なペアリング
【数２８】
2005522968.tif 000091
を選択する工程と、
第１の循環群Γ１のジェネレータＰを選択する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができるファンクションＨを選択する工程と、
最初の署名者のために秘密鍵ｓｏｒ及び公開鍵ｓｏｒＰを選択する工程と、
プロキシ署名者のために秘密鍵ｓｐｒ及び公開鍵ｓｐｒＰを選択する工程と、
プロキシ秘密鍵ｓｏｒＰｐｒを生成する工程であって、Ｐｐｒはプロキシ署名者の公開鍵ｓｐｒＰとファンクションＨとを使用して決定される、という工程と、
メッセージファンクション値ＰＭ＝Ｈ（Ｍ）を生成する工程と、
デジタル署名Ｓｉｇ＝ｓｏｒＰｐｒ＋ｓｐｒＰＭを生成することによってメッセージＭに署名する工程と、
【数２９】
2005522968.tif 000092
であることを確認することにより、デジタル署名Ｓｉｇを検証する工程と、
を備えたことを特徴とする方法。
【請求項３３】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項３２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項３４】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項３２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項３５】
前記ファンクション
【数３０】
2005522968.tif 000093
は、許容できるペアリングである、
ことを特徴とする請求項３２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項３６】
Ｐｐｒ＝Ｈ（ｓｐｒＰ）を使用してＰｐｒが決定される
ことを特徴とする請求項３２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項３７】
プロキシ署名者の公開鍵ｓｐｒＰと、ファンクションＨと、１または複数の他のファンクション入力とを使用して、Ｐｐｒが決定される
ことを特徴とする請求項３２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項３８】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項３２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項３９】
前記ファンクション
【数３１】
2005522968.tif 000094
は、許容できるペアリングである、
ことを特徴とする請求項３２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項４０】
Ｐｐｒ＝Ｈ（ｓｐｒＰ）を使用してＰｐｒが決定される
ことを特徴とする請求項３２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項４１】
一人の署名者と一人の検証者との間で通信されるデジタルメッセージの署名を生成して検証する方法であって、署名者が階層型システムにおいてルートＰＫＧよりもｔレベル下にあり、署名者は、署名者に関連付けられた同一性情報ＩＤｙｔと、ルートＰＫＧと署名者との間の階層中にある（ｔ−１）個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｙｉと、を含む署名者ＩＤ−タプル（ＩＤｙ１，．．．．，ＩＤｙｔ）に関連付けられており、
（ｔ−ｌ）個の下位レベルＰＫＧの各々に下位レベル公開鍵を生成する工程と、
署名者に関連付けられた署名者秘密鍵を生成する工程と、
ランダム署名者トラップドアシークレットを選択する工程と、
ランダム署名者トラップドアシークレットを使用してパブリックハッシュ鍵を生成する工程と、
ランダムメッセージ及び乱数を選択する工程と、
ランダムメッセージと、乱数と、署名者秘密鍵と、トラップドアシークレットと、を使用してオフライン署名を生成する工程と、
オフライン署名をデジタルメッセージと照合する照合乱数を確認する工程と、
照合乱数及びパブリックハッシュ鍵を少なくとも使用して、署名がデジタルメッセージと一致していることを確認することにより、オフライン署名を検証する工程と、
を備えたことを特徴とする方法。
【請求項４２】
一人の署名者と一人の検証者との間で通信されるデジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法であって、署名者が階層型システムにおいてルートＰＫＧよりもｔレベル下にあり、署名者は、署名者に関連付けられた同一性情報ＩＤｙｔと、ルートＰＫＧと署名者との間の階層中にある（ｔ−１）個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｙｉと、を含む署名者ＩＤ−タプル（ＩＤｙ１，．．．．，ＩＤｙｔ）に関連付けられており、
複数の要素から成る第１の循環群Γ１と、複数の要素から成る第２の循環群Γ２と、を生成する工程と、
第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成することができるバイリニアで非縮退的なペアリング
【数３２】
2005522968.tif 000095
を選択する工程と、
第１の循環群Γ１のルートジェネレータＰ０を選択する工程と、
ルートＰＫＧに関連付けられ且つルートＰＫＧにのみ知られたランダムルート鍵生成シークレットｓ０を選択する工程と、
ルート鍵生成パラメータＱ０＝ｓ０Ｐ０を生成する工程と、
第１の二進数字列から第１の循環群Γ１の１つの要素を生成することができる第１のファンクションＨ１を選択する工程と、
ｔ個の下位レベルＰＫＧの各々に、パブリック要素Ｐｙｉ＝Ｈ１（ＩＤｙ１，．．．，ＩＤｙｉ）（１≦ｉ≦ｔ−１）を生成する工程と、
ｎ個の下位レベルＰＫＧの各々に、下位レベル鍵生成シークレットｓｙｉを選択する工程であって、各下位レベル鍵生成シークレットｓｙｉは、その関連する下位レベルＰＫＧだけに知られている、という工程と、
ｍ個の下位レベルＰＫＧの各々に、下位レベルシークレット要素Ｓｙｉ＝Ｓｙ（ｉ−１）＋ｓｙ（ｉ−１）Ｐｙｉ（１≦ｉ≦ｔ−１）を生成する工程と、
ｍ個の下位レベルＰＫＧの各々に、下位レベル鍵生成パラメータＱｙｉ＝ｓｙｉＰ０（１≦ｉ≦ｔ−１）を生成する工程と、
署名者に関連付けられた署名者パブリック要素Ｐｙｔ＝Ｈ１（ＩＤｙ１，．．．．，ＩＤｙｔ）を生成する工程と、
署名者に対応付けられた署名者シークレット要素
【数３３】
2005522968.tif 000096
を生成する工程と、
ランダム署名者トラップドアシークレットｓｙｔ'  ∈Ｚ／ｑＺを選択する工程と、
パブリックハッシュ鍵Ｑｙｔ'＝ｓｙｔ'Ｐ０を生成する工程と、
ランダムメッセージＭ'及び乱数ｒ'を選択する工程と、
ランダムメッセージＭ'に署名して、デジタル署名
【数３４】
2005522968.tif 000097
を生成する工程であって、ＰＭ'＝Ｈ（（Ｍ'＋ｒ'ｓｙｔ'）Ｐ０）である工程と、
ｒ＝（ｓｙｔ'）−１（Ｍ'−Ｍ）＋ｒ'を生成する工程と、
【数３５】
2005522968.tif 000098
を確認することによりデジタル署名Ｓｉｇを検証する工程であって、ＰＭ＝Ｈ１（ＭＰ０＋ｒＱｙｔ'）である工程と、
を備えたことを特徴とする方法。
【請求項４３】
第１の循環群Γ１および第２の循環群Γ２の両者が、同じプライムオーダーｑから成る
ことを特徴とする請求項４２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項４４】
第１の循環群Γ１は、超特異な楕円曲線またはアーベル多様体上の複数の点から成る付加的な群であり、
第２の循環群Γ２は、有限領域の乗法群である
ことを特徴とする請求項４２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項４５】
前記ファンクション
【数３６】
2005522968.tif 000099
は、許容できるペアリングである、
ことを特徴とする請求項４２に記載のデジタル署名Ｓｉｇを生成して検証する方法。
【請求項４６】
複数のｍ個のメッセージに関する複数のｎ人の署名者によるデジタルマルチ署名を生成するためのシステムであって、各署名者がｍ個のメッセージの一部に署名し、最初の署名者によって署名される一部のメッセージが少なくとも一人の他の署名者によって署名される一部のメッセージと異なっており、ｎ人の署名者の各々が秘密鍵に関連付けられ、所定のファンクションを使用してｍ個のメッセージの各々のためにメッセージファンクション値が生成されるようになっており、
ｎ人の署名者に関連付けられるｎ個の秘密鍵とｍ個のメッセージファンクション値とを少なくとも記憶するように動作するメモリと、
前記メモリと通信するとともに、デジタルマルチ署名の長さがｎ及びｍに依存しないように、ｎ個の秘密鍵とメッセージファンクション値とを少なくとも使用してデジタルマルチ署名を生成するように動作するプロセッサと、
を備えたことを特徴とするシステム。
【請求項４７】
一人の署名者と一人の検証者との間で通信されるデジタルメッセージのリング署名を生成するためのシステムであって、署名者は１つのリングの複数のｔ人の構成員のうちの一人であり、リングの各構成員は同一性情報に関連付けられており、
署名者に関連付けられた秘密鍵と、リング構成員に関連付けられた複数の公開鍵と、を少なくとも記憶するように動作するメモリであって、署名者に関連付けられた前記秘密鍵は署名者の同一性情報に関連付けられ、各リング構成員に関連付けられた公開鍵は各リング構成員の同一性情報に関連付けられている、というメモリと、
前記メモリと通信し、所定のファンクションを使用してメッセージファンクション値を生成するとともに、メッセージファンクション値と、署名者に関連付けられた秘密鍵と、リング構成員に関連付けられた公開鍵と、を少なくとも使用してリング署名を生成する、というように動作するプロセッサと、
を備えたことを特徴とするシステム。
【請求項４８】
一人の署名者と一人の検証者との間で通信されるデジタルメッセージの署名を生成するためのシステムであって、署名者が階層型システムにおいてルートＰＫＧよりもｔレベル下にあり、署名者は、署名者に関連付けられた同一性情報ＩＤｙｔと、ルートＰＫＧと署名者との間の階層中にある（ｔ−１）個の下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｙｉとを含む署名者ＩＤ−タプル（ＩＤｙ１，．．．．，ＩＤｙｔ）に関連付けられており、
（ｔ−１）個の下位レベルＰＫＧの各々に関連付けられた下位レベル公開鍵と、署名者に関連付けられた署名者秘密鍵と、を少なくとも記憶するように動作するメモリと、
前記メモリと通信し、オフライン状態において、ランダムトラップドアシークレットを選択し、ランダムメッセージ及び乱数を選択し、ランダムメッセージと乱数と署名者秘密鍵とトラップドアシークレットとを使用してオフライン署名を生成するように動作するとともに、オンライン状態において、オフライン署名をデジタルメッセージと照合する照合乱数を確認するように動作するプロセッサと、
を備えたことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
ここで、出願人は、３５Ｕ．Ｓ．Ｃ．§１１９（ｅ）の下、２００２年４月１５日に提出された米国仮特許出願６０／３７２，６６８の優先権を主張する。なお、この仮特許出願は、これを参照することにより、本願に組み込まれる。
【０００２】
本発明は、一般に、コンピュータネットワークまたは他のタイプのシステム及び装置を介した暗号化及び安全な通信に関し、特に、公開鍵暗号化を使用するシステムにおいて通信の署名を生成して検証するためのスキームに関する。
【背景技術】
【０００３】
一般的に、公開鍵暗号化を使用するシステムにおいて、各当事者は、秘密鍵及び公開鍵の両方に関連付けられる。公開鍵は、公然と知られており、あるいは、認証局から利用可能である。署名者は、メッセージに署名するため、その秘密鍵を使用する。署名者の秘密鍵と公開鍵とが関連しているため、検証者は、署名者の公開鍵を使用して署名を検証することができる。署名者の秘密鍵は署名者（おそらくは、秘密鍵ジェネレータすなわちＰＫＧも）にのみ知られているため、第三者は、署名者の署名を偽造することができない。
【０００４】
また、本発明の様々な実施形態は、同一性に基づく署名スキームに適合する。概略的には、同一性に基づく署名スキームは、あるエンティティの同一性に関連付けられた情報から当該エンティティの公開鍵が得られる公開鍵スキームである。例えば、同一性情報は、個人的な情報（すなわち、名前、住所、電子メールアドレス等）またはコンピュータ情報（すなわち、ＩＰアドレス等）であり得る。また、同一性情報は、エンティティの同一性に対して厳格に関連付けられる情報だけでなく、日時等の幅広く利用可能な情報をも含み得る。すなわち、同一性情報の概念において重要なのは、エンティティの同一性に対するその厳格な関連性ではなく、エンティティへのメッセージの暗号化を望む誰でもが情報を簡単に利用できることである。
【０００５】
公開鍵暗号化を使用する同一性に基づくシステムにおけるエンティティの秘密鍵は、秘密鍵ジェネレータ（「ＰＫＧ」）として一般に知られる信頼性が高いパーティーまたは論理的プロセスによって生成されて分配される。ＰＫＧは、秘密鍵を生成するためにマスターシークレットを使用する。エンティティの公開鍵はその同一性から得られ得るため、ＢｏｂがＡｌｉｃｅからの署名を検証したい場合、ＢｏｂはＡｌｉｃｅの公開鍵をデータベースから検索する必要がない。その代わり、ＢｏｂはＡｌｉｃｅの識別情報から直接に鍵を得るだけである。公開鍵のデータベースは不要である。認証局（「ＣＡ」）も不要である。Ａｌｉｃｅの同一性がＡｌｉｃｅの公開鍵であるため、Ａｌｉｃｅの公開鍵に対してＡｌｉｃｅの同一性を「見えなくする」必要がない。
【０００６】
同一性に基づくシステムの概念は新しくない。このシステムは、スプリンガー出版から出版の、Ａ．Ｓｈａｍｉｒによる「同一性に基づく暗号システムおよび署名スキーム」、暗号システムの進歩−Ｃｒｙｐｔｏ'  １９８４年、コンピュータサイエンス１９６（１９８４）の講義ノート、Ｐ４７−５３で提案された。しかしながら、実用的な同一性に基づく署名スキームは、最近まで見当たらなかった。
【０００７】
公開鍵及び同一性に基づくシステムは、階層構造を組み込むことにより更に拡張されてきた。例えば、同一性に基づくスキームは、論理的または実体的なＰＫＧの階層を含んでいる。ルートＰＫＧが他のＰＫＧに秘密鍵を発行し、当該他のＰＫＧが特定のドメインのユーザに秘密鍵を発行しても良い。これにより、検証者がシステム内に全くいない場合であっても、検証者がルートＰＫＧのパブリックパラメータを得た限りにおいては、署名者の公開鍵または下位レベルのパブリックパラメータをオンライン検索することなく、署名者からの署名を検証することができる。階層的な同一性に基づく署名スキームの他の利点は、ダメージコントロールである。例えば、ドメインＰＫＧのシークレットの開示内容が高レベルＰＫＧのシークレットを危うくすることはなく、あるいは、危うくされたドメインＰＫＧの直接の子孫ではない任意の他のＰＫＧのシークレットを危うくすることはない。
【０００８】
公知の公開鍵及び同一性に基づくシステムは、デジタル署名を生成して検証するためのスキームを提供してきたが、公知の署名スキームは、重大な欠点を有していた。例えば、マルチ署名スキームは、複数の署名者が複数の文書に署名することを可能としなかった。複数の署名者が複数の文書に署名できるマルチ署名スキームは、署名の効率を大幅に高めることができる。例えば、そのようなマルチ署名を使用して、一連の証明書を圧縮することができる。したがって、複数の署名者が共に複数の文書に署名することができる署名スキームは必要である。
【０００９】
また、公開鍵暗号化を使用する同一性に基づくシステムのためのリング署名スキームの必要性もある。リング署名は、スプリンガー出版から出版の、Ｒ．  Ｒｉｖｅｓｔ，  Ａ．  Ｓｈａｍｉｒ，  Ｙ．  Ｔａｕｍａｎによる「秘密漏洩方法」、暗号作成術の進歩−ＡＳＩＡＣＲＹＰＴ  ２００１、コンピュータサイエンス２２４８（２００１）の講義ノート、Ｐ５５２で最近発表された。リング署名によれば、あるグループのうちの一人の構成員（必ずしも推測的に定められない）は、グループの構成員の誰かが署名を行なったことは第三者が検証できてもそれがどの構成員かを第三者が判断できないというように、１つのメッセージに署名することができる。しかしながら、効率的なリング署名スキームは、同一性に基づく暗号化スキームに利用することができなかった。したがって、同一性に基づくリング署名スキームが必要である。
【００１０】
また、公開鍵暗号化を使用する階層的な同一性に基づくシステムにおいて、代理署名、代理復号化、委任、電子投票の必要性もある。そのような特徴は、非階層システムに関し、Ｐ．  Ｈｏｒｓｔｅｒ，  Ｈ．  Ｐｅｔｅｒｓｅｎによる「自己証明鍵−概念及び用途」、通信及びマルチメディアのセキュリティに関するカンファレンスのＰＲＯＣ．３、１９９７において提案されている。しかしながら、これらの特徴は、階層システムに利用できなかった。したがって、代理署名、代理復号化、委任、電子投票を可能にする階層型の同一性に基づく署名スキームの必要性がある。
【００１１】
また、署名の一部をオフラインで生成することができる更に効率的な階層型の同一性に基づく署名スキームの必要性もある。多くの用途において、オンライン署名時間は、総署名時間よりも重要である。これらの場合、更に多くの署名アルゴリズム及び検証アルゴリズムをオフラインで実行可能とすることにより、スキームの効率を高めることができる。オンライン／オフライン署名スキームは、スプリンガー出版から出版の、Ａ．  Ｓｈａｍｉｒ，  Ｙ．  Ｔａｕｍａｎによる「改良されたオンライン／オフライン署名スキーム」、暗号作成術の進歩−ＣＲＹＰＴＯ  ２００１、コンピュータサイエンス２１３９（２００１）の講義ノート、Ｐ３５５−３６７で提案された。しかしながら、オンライン／オフライン署名スキームは、階層型の同一性に基づくシステムに利用できなかった。したがって、効率的なオンライン／オフラインの階層型の同一性に基づく署名スキームの必要性がある。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、本発明の目的は、複数の署名者が複数の文書に署名することができるマルチ署名スキームを提供することである。本発明の他の目的は、同一性に基づくリング署名スキームを提供することである。本発明の更なる目的は、代理署名、代理復号化、委任、電子投票が可能な階層型の同一性に基づく署名スキームを提供することである。本発明の更なる他の目的は、効率的なオンライン／オフラインの階層型の同一性に基づく署名スキームを提供することである。
【課題を解決するための手段】
【００１３】
本発明においては、安全で実用的かつ効率的な署名スキームを実施するための方法が提供される。
【００１４】
本発明の一態様においては、署名者と検証者との間で通信されるデジタルメッセージのデジタル署名を生成して検証するための方法及びシステムが提供される。これらの方法及びスキームにおいては、各署名者がメッセージの一部に署名し、そして、少なくとも一人の署名者によって署名された一部のメッセージが、少なくとも一人の他の署名者によって署名された一部のメッセージとは異なっている。各署名者毎に秘密鍵が選択され、また、所定のファンクションを使用して、各メッセージ毎にメッセージファンクション値が生成される。各署名者に関連付けられた秘密鍵と、署名されるメッセージに関連付けられたメッセージファンクション値と、を少なくとも使用して、各署名者毎に１または複数の署名成分が生成される。各署名成分を使用して、デジタル署名が生成される。その後、少なくともメッセージファンクション値を使用して、デジタル署名が検証される。
【００１５】
本発明の他の態様においては、署名者と検証者との間で通信されるデジタルメッセージのデジタル署名を生成して検証するための方法及びシステムであって、署名者があるセットの複数の構成員のうちの一人である、という方法及びシステムが提供される。当該署名者はある同一性に関連付けられ、また、セットの他の構成員もそれぞれ同一性に関連付けられる。複数の要素から成る第１及び第２の循環群が生成され、また、第１の循環群の２つの要素から第２の循環群の１つの要素を生成することができるバイリニアで非縮退的なペアリングが選択される。第１の循環群の第１及び第２のジェネレータが選択され、また、二進数字列から第１の循環群の１つの要素を生成できるファンクションが選択される。セットの各構成員毎にパブリック点が生成され、また、署名者のためにプライベート点が生成される。署名者のプライベート点とセットの各構成員のパブリック点とを少なくとも使用してデジタル署名を生成することにより、デジタルメッセージが署名される。セットの各構成員のパブリック点を少なくとも使用して、署名は、セットの一人の構成員によって生成されたことが検証される。
【００１６】
本発明の他の態様においては、代理署名者と検証者との間で通信されるデジタルメッセージの代理署名を生成して検証する方法及びシステムであって、最初の（オリジナル）署名者の代わりに代理（プロキシ）署名者によってメッセージが署名される、という方法及びシステムが提供される。最初の署名者に関連付けられたオリジナル署名者秘密鍵及びオリジナル署名者公開鍵が選択される。また、代理署名者に関連付けられたプロキシ署名者秘密鍵及びプロキシ署名者公開鍵も選択される。その後、オリジナル署名者秘密鍵及びプロキシ署名者公開鍵を使用して、プロキシ秘密鍵が生成される。所定のファンクションを使用してメッセージファンクション値が生成され、また、メッセージファンクション値とプロキシ秘密鍵とプロキシ署名者公開鍵とを少なくとも使用して、プロキシ署名が生成される。オリジナル署名者公開鍵とプロキシ署名者公開鍵とメッセージファンクション値とを少なくとも使用して、プロキシ署名が検証されても良い。
【００１７】
本発明の更なる他の態様においては、署名者と検証者との間で通信されるデジタルメッセージの署名を生成して検証するための方法及びシステムが提供される。署名者は、階層型システムにおいて、ルートＰＫＧよりもｔレベル下にある。署名者は、当該署名者に関連付けられた同一性情報と、ルートＰＫＧと署名者との間の階層中にある（ｔ−１）個の下位レベルＰＫＧの各々に関連付けられた同一性情報と、を含むＩＤ−タプルに関連付けられている。各下位レベルＰＫＧ毎に下位レベル公開鍵が生成される。署名者に関連付けられた署名者秘密鍵が生成される。オフラインモードにおいては、ランダム署名者トラップドアシークレットと、ランダムメッセージと、乱数と、が選択される。その後、ランダムメッセージと、乱数と、トラップドアシークレットと、署名者秘密鍵と、（ｔ−１）個の下位レベルＰＫＧに関連付けられた下位レベル公開鍵と、を使用して、オフライン署名が生成される。オンラインモードにおいては、照合乱数が、オフライン署名と署名されるメッセージとを一致させるように、決定される。その後、照合乱数を使用して、オフライン署名が検証されても良い。
【発明を実施するための最良の形態】
【００１８】
本発明の好ましい実施形態の以下の説明においては、添付図面を参照する。
【００１９】
図１は、現在において好ましい本発明の一実施形態に係る、デジタルメッセージＭのマルチ署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【００２０】
図２は、現在において好ましい本発明の他の実施形態に係る、一人の署名者と一人の検証者との間で通信されるデジタルメッセージＭのリング署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【００２１】
図３は、現在において好ましい本発明の他の実施形態に係る、ある階層中の一人の署名者と一人の検証者との間で通信されるデジタルメッセージＭのリング署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【００２２】
図４は、本発明の他の実施形態に係る、デジタルメッセージＭのプロキシ署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【００２３】
図５は、本発明の他の実施形態に係る、デジタルメッセージＭの署名Ｓｉｇを生成して検証する方法を表わすフローチャートであって、署名アルゴリズム及び検証アルゴリズムの一部がオフラインで完了され得るフローチャートを示している。
【００２４】
図６は、本発明の他の実施形態に係る、署名スキームを実施するためのシステムを表わすブロック図を示している。
【００２５】
本発明の現在好ましい方法は、安全で、実用的で、効率的な、同一性に基づく（ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ）階層型の公開鍵署名スキーム（ｓｃｈｅｍｅ）を提供する。
【００２６】
本発明は、公開鍵署名スキームを提供する。これらは、同一性に基づくスキーム及び同一性に基づかないスキームの両方を含んでいる。また、これらは、階層型のスキーム及び非階層型のスキームの両方を含んでいる。
【００２７】
本発明の階層型の同一性に基づく各署名スキームは、少なくとも１つのルートＰＫＧおよび複数の下位レベルＰＫＧを含むＰＫＧの階層構造を必要とする。階層および下位レベルＰＫＧは、論理的または実体的であっても良い。例えば、１つのエンティティは、ルート鍵生成シークレットと、下位レベルユーザの暗号化鍵または署名鍵がそこから生成される下位レベル鍵生成シークレットと、の両方を生成しても良い。この場合、これらの下位レベルＰＫＧは、別個のエンティティではなく、単なるプロセス、または、論理的な階層中に配置され且つ階層中の子孫ＰＫＧおよびユーザのための鍵を生成するために使用される情報である。あるいは、各下位レベルＰＫＧは、別個のエンティティであっても良い。他の選択肢には、実体的な下位レベルＰＫＧと論理的な下位レベルＰＫＧとの混成が含まれる。説明の目的のため、用語「下位レベルＰＫＧ」は、これらの選択肢のうちの任意の１つを示すべく総称的に使用される。
【００２８】
ここに開示された階層型の同一性に基づくシステムにおいて、同一性に基づく公開鍵は、時間に基づいていても良い。例えば、連続する各時間と共に特定の署名者の同一性が変化しても良い。あるいは、署名者は、それ自身の子または子孫として時間を階層中に設定しても良く、また、検証者は、署名を検証する際に、適当な時間の同一性を使用し得る。どちらにせよ、各鍵は、対応する時間中にだけメッセージに署名する場合に有効であり得る。
【００２９】
本発明の階層型の同一性に基づくスキームは、一般に、５つのアルゴリズム、すなわち、ルートセットアップアルゴリズムと、下位レベルセットアップアルゴリズムと、抽出アルゴリズムと、署名アルゴリズムと、検証アルゴリズムと、を有している。これらのアルゴリズムのうちの３つは、階層中の関連するエンティティの同一性に依存している。各ユーザは、そのＩＤのタプル（ＩＤ１，．．．．ＩＤｉ）によって規定され得る位置を階層中に有していることが好ましい。階層中におけるユーザの先祖は、ルートＰＫＧおよびそのＩＤタプルが｛（ＩＤ１，．．．．ＩＤｉ）：１≦ｉ≦（ｔ−１）｝であるユーザまたはＰＫＧである。ＩＤタプルは、演算のために、二進数字列として表されることが好ましい。
【００３０】
ルートセットアップアルゴリズムにおいて、ルートＰＫＧは、セキュリティパラメータｋを使用して、パブリックシステムパラメータｐａｒａｍｓおよびルート鍵生成シークレットを生成する。システムパラメータは、メッセージスペース
【数１】
2005522968.tif 000003
および署名スペースＳの記述を含んでいる。システムパラメータは公然と利用可能であり、一方、ルートＰＫＧだけがルート鍵生成シークレットを知っている。
【００３１】
下位レベルセットアップアルゴリズムにおいて、各下位レベルＰＫＧは、抽出のために、それ自身の下位レベル鍵生成シークレットを生成することが好ましい。また、下位レベルＰＫＧは、各抽出毎に、ランダム一時シークレットを生成しても良い。
【００３２】
抽出アルゴリズムにおいて、ＰＫＧ（ルートＰＫＧであろうと、あるいは、下位レベルＰＫＧであろうとも）は、それ自身の任意の子のための秘密鍵を生成する。当該秘密鍵は、システムパラメータと、生成するＰＫＧの秘密鍵と、任意の他の好ましいシークレット情報と、を使用して生成される。
【００３３】
署名アルゴリズムにおいて、デジタルメッセージの署名者は、ｐａｒａｍｓおよび署名者の秘密鍵ｄを使用して、メッセージ
【数２】
2005522968.tif 000004
に署名をし署名Ｓｉｇ∈Ｓを生成する。検証アルゴリズムにおいて、署名されたメッセージの検証者は、ｐａｒａｍｓおよび署名者のＩＤ−タプルを使用して、署名Ｓｉｇを検証する。検証アルゴリズムは、「有効」または「無効」を出力することが好ましい。署名および検証は、以下の一貫性制約を満たすことが好ましい。
【数３】
2005522968.tif 000005
ここで、Ｓｉｇ＝署名（ｐａｒａｍｓ、ｄ、Ｍ）である。
【００３４】
（ペアリング）
本発明の現在の好ましい署名スキームは、例えば、楕円曲線またはアーベル多様体に関連付けられたウェイルペアリングまたはテートペアリング等のペアリング（組み合わせ）に基づいている。また、この署名スキームは、ディフィー・ヘルマン問題またはバイリニアなディフィー・ヘルマン問題に基づいている。いずれの場合においても、当該スキームは、好ましくは同じ大きさのプライムオーダーｑから成る２つの循環群Γ１、Γ２を使用する。第１群Γ１は、楕円曲線上またはアーベル多様体上の点から成る群であることが好ましく、Γ１に関する群法則が付加的に書き込まれても良い。第２群Γ２は、有限領域の乗法群であることが好ましく、Γ２に関する群法則が乗法的に書き込まれても良い。しかしながら、本発明と整合性が取れる他のタイプの群をΓ１、Γ２として使用しても良い。
【００３５】
また、この方法は、第１群Γ１のジェネレータＰ０を使用する。また、ペアリングまたはファンクション
【数４】
2005522968.tif 000006
は、第１群Γ１の２つの要素を第２群Γ２の１つの要素に対してマッピングするために与えられる。
【数５】
2005522968.tif 000007
は、３つの条件を満たすことが好ましい。まず第１に、ＱおよびＲがΓ１内にあり且つａ、ｂが整数である場合に、
【数６】
2005522968.tif 000008
となるように、
【数７】
2005522968.tif 000009
はバイリニアであることが好ましい。第２に、マップがΓ１×Γ１における全てのペア（対）をΓ２における同一性に対して送らないように、
【数８】
2005522968.tif 000010
は非縮退的であることが好ましい。第３に、
【数９】
2005522968.tif 000011
は、効率的に演算可能であることが好ましい。これらの３つの条件を満たす
【数１０】
2005522968.tif 000012
は、許容できると考えられる。
【００３６】
また、全てのＱ，Ｒ∈Γ１に関して
【数１１】
2005522968.tif 000013
となるように、
【数１２】
2005522968.tif 000014
は対称的であることが好ましい。しかしながら、対称性は、バイリニア性とΓ１が循環群であるという事実とから直ちに得られる。超特異な楕円曲線またはアーベル多様体に関連付けられたウェイルペアリングおよびテートペアリングは、従来技術に知られた方法にしたがって、そのようなバイリニアなマップを生成するために変更され得る。しかしながら、たとえ第１の循環群Γ１の要素を「点」の群として参照することで、
【数１３】
2005522968.tif 000015
が変更されたウェイルペアリングまたはテートペアリングであることを提案できるとしても、任意の許容できる
【数１４】
2005522968.tif 000016
が働くことが指摘されるべきである。
【００３７】
本発明の署名スキームのセキュリティは、主に、ディフィー・ヘルマン問題またはバイリニアなディフィー・ヘルマン問題の難しさに基づいている。ディフィー・ヘルマン問題は、ランダムに選択されたＰ∈Γ１  およびａＰ、ｂＰ（未知のランダムに選択されたａ、ｂ、ｃ∈Ｚ／ｑＺにおいて）が与えられてａｂＰを見つける問題である。バイリニアなディフィー・ヘルマン問題は、ランダムに選択されたＰ∈Γ１  およびａＰ、ｂＰ、ｃＰ（未知のランダムに選択されたａ、ｂ、ｃ∈Ｚ／ｑＺにおいて）が与えられて
【数１５】
2005522968.tif 000017
を見つける問題である。Γ１においてディフィー・ヘルマン問題を解くことは、
【数１６】
2005522968.tif 000018
であるため、バイリニアなディフィー・ヘルマン問題を解くことである。同様に、Γ２においてディフィー・ヘルマン問題を解くことは、
【数１７】
2005522968.tif 000019
である場合にｇａｂｃ＝（ｇａｂ）ｃであるため、バイリニアなディフィー・ヘルマン問題を解くことである。ここで、
【数１８】
2005522968.tif 000020
であり、また、
【数１９】
2005522968.tif 000021
である。バイリニアなディフィー・ヘルマン問題が難しいため、Γ１またはΓ２のいずれかにおいてディフィー・ヘルマン問題を効率的に解くための周知のアルゴリズムが無いというように、Γ１及びΓ２が選択されるべきである。バイリニアなディフィー・ヘルマン問題が
【数２０】
2005522968.tif 000022
において困難である場合、それは、
【数２１】
2005522968.tif 000023
が非縮退的であるということに従う。
【００３８】
ランダム化アルゴリズムＩΓは、セキュリティパラメータｋ＞０を取得して経時的にｋの多項式を実行し、且つ、好ましくは同じプライムオーダーｑから成る２つの群Γ１及びΓ２の記述と許容できるペアリング
【数２２】
2005522968.tif 000024
の記述とを出力する場合に、バイリニアなディフィー・ヘルマン・ジェネレータである。ＩΓがバイリニアなディフィー・ヘルマンパラメータジェネレータである場合、アルゴリズムＢがバイリニアなディフィー・ヘルマン問題を解く際に有するアドバンテージＡｄνＩΓ（Ｂ）は、アルゴリズムへの入力がΓ１、Γ２、
【数２３】
2005522968.tif 000025
Ｐ、ａＰ、ｂＰ及びｃＰである時にアルゴリズムＢが
【数２４】
2005522968.tif 000026
を出力する確率として規定される。ここで、
【数２５】
2005522968.tif 000027
は、十分に大きいセキュリティパラメータｋにおけるＩΓの出力であり、ＰはΓ１のランダムジェネレータであり、ａ、ｂ及びｃはＺ／ｑＺのランダム要素である。バイリニアなディフィー・ヘルマン問題の根底にある前提は、全ての効率的なアルゴリズムＢにおいてＡｄνＩΓ（Ｂ）が無視できる、ということである。同様な前提が、ディフィー・ヘルマン問題の根底にもある。
【００３９】
（マルチ署名）
前述したように、マルチ署名スキームは、各署名者が文書に個別に署名する場合よりも効率的に、数人の署名者が１（または複数）の文書に署名できる任意のスキームである。通常、この効率の向上は、署名の長さに関してのものである。すなわち、ｎ人の署名者の組み合わされたマルチ署名は、ｎ個の別個の署名よりも短い。これは、当事者のうちの一人が複数のソースから事前承認を得て且つこの複数の事前承認を取引前に転送する必要がある取引（トランザクション）において、都合が良い。前述したように、複数の署名者が複数の文書に効率的に署名できるマルチ署名スキームは、今までなかった。例えば、既存のマルチ署名スキームにおいて、マルチ署名の長さは、少なくとも、署名者の数または署名される文書の数に依存している。本発明は、署名者の数及び文書の数の両方に依存しない長さを持つマルチ署名を生成するように複数の署名者が複数の文書に署名することを可能とする、より効率的なマルチ署名の署名スキームを提供する。
【００４０】
ここで、添付図面を参照すると、図１は、現在において好ましい本発明の一実施形態に係るマルチ署名を生成及び検証する方法を表わすフローチャートを示している。この実施形態においては、ウェイルペアリングやテートペアリング等のバイリニアなマッピングを使用して、複数の署名者が複数の文書に署名することができる。その結果として得られる署名は、異なる署名者の数または異なる署名文書の数にも関わらず、例えば楕円曲線上の１つの点のように、１つのグループの１つの要素として表わされ得る。
【００４１】
図１に関して説明したマルチ署名スキームによれば、ｎ人の署名者は、ｍ個のデジタルメッセージに署名して、１つのマルチ署名を生成することができる。各署名者は、ｍ個のメッセージの一部に署名する。以前の署名スキームとは異なり、このスキームによれば、異なる署名者は、効率を犠牲にすることなく、異なる組のメッセージに署名することができる。この方法は、複数の要素から成る第１及び第２の循環群Γ１及びΓ２を生成することにより、ブロック１０２から開始される。ブロック１０４においては、
【数２６】
2005522968.tif 000028
が選択される。この場合、
【数２７】
2005522968.tif 000029
は、それが第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成できるように選択される。
【数２８】
2005522968.tif 000030
は、前述したように、許容できるペアリングであることが好ましい。ブロック１０６において、第１の循環群Γ１のルートジェネレータＰ０が選択される。ブロック１０８においては、ファンクションＨが選択される。この場合、ファンクションＨは、第１の二進数字列から第１の循環群Γ１の要素を生成できるように選択される。例えば、ファンクションＨはハッシュ関数であっても良い。
【００４２】
ブロック１１０においては、ｎ人の署名者の各々に秘密鍵ｓｉが選択される。ブロック１１２においては、ファンクションＨを使用して、ｍ個のメッセージの各々に、メッセージファンクション値
【数２９】
2005522968.tif 000031
が生成される。ブロック１１４においては、全ての（ｉ，ｊ）∈Ｃに関して、すなわち、ｉ番目の署名者がｊ番目のメッセージに署名するような全ての（ｉ，ｊ）対に関して、式
【数３０】
2005522968.tif 000032
を使用して、署名成分Ｓｉｊが生成される。ブロック１１６に示されるように、これらの署名成分Ｓｉｊが組み合わされて、デジタル署名Ｓｉｇ＝Σ（ｉ，ｊ）∈ＣＳｉｊが生成される。署名スキームの効率は、デジタル署名Ｓｉｇが第１の循環群Ｇ１の１つの要素を含んでいるという事実から流れ出る。この署名は、ブロック１１８において、
【数３１】
2005522968.tif 000033
を確認することにより検証される。
【００４３】
全ての署名者が全てのメッセージに署名する前述のスキームは、有用なタイプのマルチ署名であるが、他の変形例もある。例えば、全ての署名者によってメッセージの全てが署名される必要はない。また、当事者が得た様々な署名及び承認は、以後の取引において、異なる組み合わせで照合され得る。幾人かの署名者が同じメッセージに署名する場合、または、一人の署名者が複数のメッセージに署名する場合には、ペアリング計算を行なう必要が殆どないため、マルチ署名の検証効率が良くなる。このスキームは、従来知られた方法により、検証者がそのｙ座標をそこから回復させることができる署名Ｓｉｇのｘ座標だけを送ることにより、帯域幅が更に効率的となり得る。
【００４４】
図１に関して説明したマルチ署名スキームへの特定のタイプの攻撃を防止するためには、別のセキュリティ対策が役立つかもしれない。そのような攻撃において、攻撃者は、幾らかの他の当事者の公開鍵に応じて、その公開鍵／秘密鍵の対を変更し、それにより、攻撃者は、当該他の当事者の参加がなくても、それ自身と他の当事者とが推定署名者として関与する１つのメッセージマルチ署名を偽造することができる。この種の攻撃は、多くの方法で防止することができる。例えば、一人の当事者が各署名者から署名成分を収集してマルチ署名を形成しても良い。そうすることで、この当事者は、
【数３２】
2005522968.tif 000034
であることを確認することにより、各署名者の署名成分Ｓｉｊを独立に検証することができる。しかしながら、この方法により、マルチ署名の最終的な検証者が再保証されないかもしれない。なぜなら、検証者は、署名成分を収集した当事者がこれらの署名成分を正確に検証したということを信じなければならないからである。
【００４５】
また、例えば、署名者の同一性情報または公開鍵を含むメッセージ、または、各署名者のためにランダムに選択されるメッセージといった、署名者に固有のあるメッセージに個別に署名することを各署名者に要求することにより、攻撃を阻止することができる。例えば、
【数３３】
2005522968.tif 000035
は、
【数３４】
2005522968.tif 000036
に設定されても良い。あるいは、ＣＡは、ＣＡが署名者に対して証明書を発行する前に、ＣＡによって選択されるある「チャレンジ」メッセージに署名することを署名者に要求しても良い。（実際には、ＣＡは、多くの場合、これを既に要求している。）いずれの場合にも、検証者は、署名成分を収集した当事者からの再保証を全く必要とすることなく、マルチ署名を単独で検証することができる。当業者であれば分かるように、他の方法を使用して攻撃を阻止することもできる。
【００４６】
（同一性に基づくリング署名）
リング署名により、あるグループの一人の構成員（必ずしも推測的に定められない）は、グループの構成員の誰かが署名を行なったことは第三者が検証できるが、それがどの構成員かは判断できないように、１つのメッセージに署名することができる。例えば、秘密をマスコミに漏らしたいがある程度匿名のままにしておきたいと望むキャビネット構成員（ｃａｂｉｎｅｔ  ｍｅｍｂｅｒ）  −すなわち、彼は、自分がキャビネット構成員であることをマスコミに知って欲しいが、どの構成員であるかをマスコミに知られたくない−  について考える。リング署名により、署名者は、自分を含む任意のセットを選択することができるとともに、どの構成員であるかを開示することなく自分がそのセットの構成員であることを証明できる。そして、キャビネット構成員は、他のキャビネット構成員の公開鍵と自分の秘密鍵とを組み合わせて使用することにより、キャビネットのためのリング署名を生成することができる。キャビネット固有のリング署名はキャビネット構成員によってのみ生成され得るため、マスコミは、この署名を使用して、その匿名情報源の信頼性を証明することができる。
【００４７】
また、リング署名は、契約交渉においても役立ち得る。当事者Ａが契約案を当事者Ｂに送る場合、当事者Ａは、認証は与えたいが、否認防止は与えたくない場合がある。すなわち、当事者Ａは、契約案が当事者Ａからのものであることを当事者Ｂに証明したいが、当事者Ａが契約案に署名したことを第三者（すなわち、裁判所）に明かす能力を当事者Ｂに与えたくない場合がある。この状況において、当事者Ａは、セット｛Ａ，Ｂ｝のためのリング署名を形成することができる。当事者Ｂは、自分が署名それ自体を形成しなかったため、当事者Ａが署名を形成したことを知る。一方、第三者の観点からは、当事者Ｂも署名を形成することができたのであるから、当事者Ｂは、当事者Ａが署名を形成したことを第三者に確信させることができない。
【００４８】
ここで、図２を参照しながら、同一性に基づくリング署名スキームについて説明する。図２は、現在において好ましい本発明の他の実施形態に係る、署名者と検証者との間で通信されるメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。この場合、署名者は、ある１つのセットのｔ人の構成員のうちの一人である。以下の説明のため、署名者は、同一性ＩＤ１に関連付けられ、セットの他の構成員は、２≦ｉ≦ｔの同一性ＩＤｉに関連付けられる。しかしながら、匿名の署名者が最初に示された同一性に常に関連付けられた場合、署名は、実際には、匿名ではない。
【００４９】
この方法は、複数の要素から成る第１及び第２の循環群Γ１及びΓ２を生成することにより、ブロック２０２から開始される。ブロック２０４においては、
【数３５】
2005522968.tif 000037
が選択される。この場合、
【数３６】
2005522968.tif 000038
は、それが第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成できるように選択される。
【数３７】
2005522968.tif 000039
は、前述したように、許容できるペアリングであることが好ましい。ブロック２０６において、第１の群Γ１の第１及び第２ジェネレータＰ及びＰ’が選択される。ブロック２０８においては、第１及び第２のシークレット番号ｓ、ｓ'が選択される。随意的に、新たな各署名毎に、新たなｓ'が選択され得る。ファンクションＨは、第１の二進数字列から第１の循環群Γ１の要素を生成できるように選択される。ブロック２１２においては、セットのｔ人の構成員の各々に、パブリック点Ｐｉ＝Ｈｉ（ＩＤｉ）が生成される。ブロック２１４においては、署名者のために、プライベート点ｓＰ'＋ｓ'Ｐ１が生成される。
【００５０】
ブロック２１６においては、少なくとも署名者のプライベート点（ｓＰ'＋ｓ'Ｐ１）及びセットのｔ人の各構成員のパブリック点Ｐｉを使用してデジタル署名Ｓｉｇを生成することにより、デジタルメッセージＭが署名される。例えば、以下の方法で、デジタル署名が生成され得る。１≦ｉ≦ｔにおいて乱数ｒＭ、ｒｉが選択され、メッセージファンクション値ＰＭ＝Ｈ２（Ｍ）が生成される。その後、Ｓｉｇ＝［Ｕ，Ｖ１，．．．，Ｖｌ，ＶＭ］を使用して、デジタル署名それ自体が生成される。ここで、
Ｕ＝ｓＰ'＋ｓ'Ｐ１＋ｒ１Ｐ１＋ｒ２Ｐ２＋・・・＋ｒｌＰｌ＋ｒＭＰＭ
Ｖ１＝ｓ'Ｐ＋ｒ１Ｐ
ＶＭ＝ｒＭＰ
Ｖｉ＝ｒｉＰ（２≦ｉ≦ｎ）
ブロック２１８においては、少なくともセットのｔ人の各構成員のパブリック点Ｐｉを使用して、デジタル署名Ｓｉｇがセットの一人の構成員によって生成されたことが検証される。例えば、
【数３８】
2005522968.tif 000040
であることを確認することによって、署名が検証されても良い。
【００５１】
以下は、前述した方法に係る同一性ＩＤ１及びＩＤ２を有する２つのエンティティのための同一性に基づくリング署名の一例である。第１のエンティティのためにＰＫＧによって与えられる秘密鍵は、（ｓＰ'＋ｒ１Ｐ１，ｒ１Ｐ）として表わされ得る。また、第２のエンティティのためにＰＫＧによって与えられる秘密鍵は、（ｓＰ'＋ｒ２Ｐ２，ｒ２Ｐ）として表わされ得る。各秘密鍵における最初の点の最初の部分は、各エンティティをＰＫＧに関連付けるｓＰ'である。各秘密鍵のこの部分は、一定でなければならない。しかしながら、各秘密鍵の残りの部分は変化しても良い。例えば、第１のエンティティにとって等しく有効なプライベート点は、任意のｒ１'において、（ｓＰ'＋ｒ１'Ｐ１，ｒ１'Ｐ）である。この自由度は、リング署名の生成を可能にするために利用される。これら２つのエンティティのためのリング署名は、あるｒ１'、ｒ２'において、（ｓＰ'＋ｒ１'Ｐ１＋ｒ２'Ｐ２，ｒ１'Ｐ，ｒ２'Ｐ）の形式を有している。両方のエンティティの同一性は、これらのエンティティのパブリック点Ｐ１、Ｐ２を使用することにより、このリング署名中に組み込まれる。更に、いずれのクライアントもそのようなリング署名を生成することができる。
【００５２】
例えば、第１のエンティティは、以下のように、両方のエンティティのための１つのリング署名を生成しても良い。便宜上、第１のエンティティの秘密鍵を（Ｓ１，Ｒ１）として表わすことにする。第１のエンティティは、乱数ｂ、ｒ２'を選択するとともに、リング署名（Ｓ１＋ｂＰ１＋ｒ２'Ｐ２，Ｒ１＋ｂＰ，ｒ２'Ｐ）を計算する。ここで、ある乱数ｂにおいて、ｒ１'＝ｒ１＋ｂである。これは、第１及び第２のエンティティにとって有効なリング署名である。なお、第１のエンティティが常にｂ＝０を選択する場合、第１のエンティティがそれぞれの署名を形成したことは明白である。乱数ｂを使用することにより、２つのエンティティのうちのいずれがリング署名を形成したかを判断することが不可能となる。同様に、第２のエンティティは、乱数ｂ、ｒ１'を選択するとともに、リング署名（Ｓ２＋ｒ１'Ｐ１＋ｂＰ２，ｒ２'Ｐ，Ｒ２＋ｂＰ）を計算し得る。
【００５３】
しかしながら、同一性ＩＤ３を有する第３のエンティティは、最初の２つのエンティティにとって有効なリング署名を形成しなくても良い。ＰＫＧにより第３のエンティティに対して与えられる秘密鍵は、（ｓＰ'＋ｒ３Ｐ３，ｒ３Ｐ）として表わされ得る。第３のエンティティは、その秘密鍵からそのパブリック点Ｐ３を除去することができないため、第３のエンティティの秘密鍵は、その同一性によって「汚される」。この汚れは除去することができない。そのため、第３のエンティティは、最初の２つのエンティティにとって有効なリング署名を偽造することができない。本質的に、他のエンティティの同一性を署名しているエンティティの秘密鍵に対して加えることにより、最初の２つのエンティティだけがそのようなリング署名を形成し得る。
【００５４】
また、前述したリング署名スキームは、階層型のリング署名スキームを形成するために修正され得る。ここで、図３を参照しながら、階層型の同一性に基づくリング署名スキームについて説明する。図３は、現在において好ましい本発明の他の実施形態に係る、ある階層中の署名者と検証者との間で通信されるメッセージＭのリング署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。この方法により、階層中のｔ人のリング構成員から成る１つのリングからの一人の署名者は、ｔ人のリング構成員のための１つのリング署名を生成することができる。ｔ人の各エンティティは、
【数３９】
2005522968.tif 000041
等のＩＤ−タプルに関連付けられる。ここで、ｌｉは、階層中の各エンティティのレベルを表わしている。この方法は、複数の要素から成る第１及び第２の循環群Γ１及びΓ２を生成することにより、ブロック３０２から開始される。ブロック３０４においては、
【数４０】
2005522968.tif 000042
が選択される。この場合、
【数４１】
2005522968.tif 000043
は、それが第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成できるように選択される。
【数４２】
2005522968.tif 000044
は、前述したように、許容できるペアリングであることが好ましい。ブロック３０６において、第１の循環群Γ１のルートジェネレータＰ０が選択される。ブロック３０８においては、ルートＰＫＧに関連付けられ且つルートＰＫＧだけに知られたランダムルート鍵生成シークレットｓ０が選択される。ｓ０は、循環群Ｚ／ｑＺの１つの要素であることが好ましい。ブロック３１０においては、ルート鍵生成パラメータＱ０＝ｓ０Ｐ０が生成される。Ｑ０は、第１の循環群Γ１の１つの要素であることが好ましい。ブロック３１２においては、第１のファンクションＨ１が選択される。この場合、ファンクションＨ１は、第１の二進数字列から第１の循環群Γ１の要素を生成できるように選択される。ブロック３１４においては、第２のファンクションＨ２が選択される。この場合、ファンクションＨ２も、第１の二進数字列から第１の循環群Γ１の要素を生成できるように選択される。ブロック３０２からブロック３１４のファンクションは、前述したルートセットアップアルゴリズムの一部であり、ほぼ同時に実行されることが好ましい。一例として、Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎに開示されたファンクションのようなファンクションが、Ｈ１およびＨ２として使用され得る。
【００５５】
次の一連のブロック（ブロック３１６から３２４）は、下位レベルセットアップアルゴリズムの一部として実行されるファンクションを示している。ブロック３１６においては、ｔ人のリング構成員の各々と関連付けられたｌｉ  −１個の先祖下位レベルＰＫＧの各々に、パブリック要素Ｐｉｌが生成される。１≦ｉ≦ｔ及び１≦ｌ≦（ｌｉ−１）において、各パブリック要素Ｐｉｌ＝Ｈ（ＩＤｉ１，．．．．，ＩＤｉｌ）は、第１の循環群Γ１の１つの要素であることが好ましい。全てのパブリック要素Ｐｉｌの生成が１つのブロックで表わされているが、これらのパブリック要素Ｐｉｌの生成は、同時に行なわれることなく経時的に行なわれても良い。
【００５６】
ｔ人のリング構成員の各々に関連付けられたｌｉ−１個の先祖下位レベルＰＫＧの各々に、１≦ｉ≦ｔ及び１≦ｌ≦（ｌｉ−１）において、下位レベル鍵生成シークレットｓｉｌが選択される（ブロック３１８）。下位レベル鍵生成シークレットｓｉｌは、循環群Ｚ／ｑＺの要素であることが好ましく、また、各下位レベル鍵生成シークレットｓＺｉは、その対応する下位レベルＰＫＧだけに知られていることが好ましい。この場合も同様に、下位レベル鍵生成シークレットｓｉｌの選択が１つのブロックで表わされているが、これらの下位レベル鍵生成シークレットｓｉｌの選択は、同時に行なわれることなく経時的に行なわれても良い。
【００５７】
ｔ人のリング構成員の各々に関連付けられたｌｉ−１個の先祖下位レベルＰＫＧの各々に、下位レベルシークレット点Ｓｉｌが生成される（ブロック３２０）。１≦ｉ≦ｔ及び１≦ｌ≦（ｌｉ−１）において、各下位レベルシークレット要素Ｓｉｌ＝Ｓｉ（ｌ−１）＋ｓｉ（ｌ−１）Ｐｉｌは、第１の循環群Γ１の要素であることが好ましい。パブリック要素Ｐｉｌおよびシークレットｓｉｌと同様に、シークレット要素Ｓｉｌの生成が１つのブロックで表わされているが、これらのシークレット要素Ｓｉｌの生成は、同時に行なわれることなく経時的に行なわれても良い。これらの繰り返される鍵生成プロセスのため、Ｓ０は、Γ１の同一性要素として規定される。
【００５８】
また、ｔ人のリング構成員の各々に関連付けられたｌｉ−１個の先祖下位レベルＰＫＧの各々に、下位レベル鍵生成パラメータＱｉｌも生成される（ブロック３２２）。１≦ｉ≦ｔ及び１≦ｌ≦（ｌｉ−１）において、各鍵生成パラメータＱｉｌ＝ｓｉｌＰ０は、第１の循環群Γ１の要素であることが好ましい。全ての鍵生成パラメータＱｉｌの生成が１つのブロックで表わされているが、これらの鍵生成パラメータＱｉｌの生成は、同時に行なわれることなく経時的に行なわれても良い。
【００５９】
次の２つのブロック（ブロック３２４、３２６）のファンクションは、前述した抽出アルゴリズムの一部として実行される。ブロック３２４においては、ｔ人のリング構成員の各々に関連付けられたリング構成員パブリック点
【数４３】
2005522968.tif 000045
が生成される。１≦ｉ≦ｔにおいて、各リング構成員パブリック点
【数４４】
2005522968.tif 000046
は、第１の循環群Γ１の要素であることが好ましい。その後、ブロック３２６において、ｔ人のリング構成員の各々に関連付けられたリング構成員シークレット点
【数４５】
2005522968.tif 000047
が生成される。また、１≦ｉ≦ｔにおいて、各リング構成員シークレット点
【数４６】
2005522968.tif 000048
も、第１の循環群Ｇ１の要素であることが好ましい。
【００６０】
便宜上、第１のファンクションＨ１は、随意的に、反復関数となるように選択されても良い。この場合、例えば、Ｈ１（ＩＤｉ１，．．．，ＩＤｉｌ）としてではなく、Ｈ１（Ｐｉ（ｌ−１），ＩＤｉｌ）として、パブリック点Ｐｉｌが演算され得る。
【００６１】
図３に示される最後の２つのブロック（ブロック３２８，３３０）は、前述した署名アルゴリズム及び検証アルゴリズムを表わしている。ブロック３２８においては、ＩＤ−タプル
【数４７】
2005522968.tif 000049
を有する署名者によってメッセージＭが署名され、リング署名Ｓｉｇが生成される。署名アルゴリズムは、ｔ人の各リング構成員毎に、少なくとも、署名者のプライベート点
【数４８】
2005522968.tif 000050
及びＩＤ−タプル
【数４９】
2005522968.tif 000051
を使用することが好ましい。その後、ブロック３３０において、ｔ人のリング構成員のうちの一人によってリング署名Ｓｉｇが署名されたことを確認するために、リング署名Ｓｉｇが検証される。検証は、ｔ人の各リング構成員毎に、少なくともＩＤ−タプル
【数５０】
2005522968.tif 000052
を使用することが好ましい。これらのＩＤ−タプルは、パブリック点−タプルＰｉｋ＝Ｈ（ＩＤｉ１，．．．．，ＩＤｉｋ）に対応している。
【００６２】
例えば、署名アルゴリズムは、ｔ人のリング構成員のパブリック点−タプルＰｉｋ間の冗長性を除去することによって始まっても良い。任意のリング構成員が共通の先祖ＰＫＧを共有する場合には、これらの点−タプル間には冗長性がある。ｔ個のパブリック点−タプルからのパブリック点の非冗長なセットは、点のセットＲ＝｛Ｒ１，．．．．，Ｒｘ｝によって表わされ得る。その後、署名者は、［Ｕ，Ｖ１，．．．．．，Ｖｘ，ＶＭ］の形式でリング署名を生成する。ここで、Ｕ＝ｓＰ'＋ｒ１Ｒ１＋・・・＋ｒｘＲｘ＋ｒＭＰＭであり、Ｖｋ＝ｒｋＰ（１≦ｋ≦ｘ）であり、ＶＭ＝ｒＭＰである。リング構成員間でその匿名性を保つため、署名者は、そのＩＤ−タプル中にはない点Ｒｋのためにｒｋをランダムに選択するとともに、前述した方法を使用して、そのＩＤ−タプル中にある点Ｒｋのためにスカラーを「分かりにくくする」。この署名は、
【数５１】
2005522968.tif 000053
であることを確認することにより、署名者がｔ人のリング構成員のうちの一人であることを確認すべく検証され得る。
【００６３】
（階層的な同一性に基づくプロキシ（代理）署名）
プロキシ署名により、プロキシ署名者と呼ばれる指定された一人の人または人のグループは、最初の署名者の代わりに署名することができる。プロキシ署名スキームは、以下の特性を有していなければならない。
【００６４】
強い非偽造力：プロキシ署名者は、最初の署名者にとって有効なプロキシ署名を形成することができる。最初の署名者を含む任意の他の第三者は、プロキシ署名を偽造することができない。
【００６５】
強い識別可能性：プロキシ署名から誰でもプロキシ署名者を識別することができる。
【００６６】
強い非否認能力：プロキシ署名者は、有効な署名の形成を無効にすることができない。
【００６７】
本発明は、階層的な同一性に基づくプロキシ署名スキームを提供する。図４は、本発明の他の実施形態に係る、デジタルメッセージＭのデジタルプロキシ署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。署名Ｓｉｇは、最初の署名者の代わりにプロキシ署名者によって署名される。この方法は、複数の要素から成る第１及び第２の循環群Γ１及びΓ２を生成することにより、ブロック４０２から開始される。ブロック４０４においては、
【数５２】
2005522968.tif 000054
が選択される。この場合、
【数５３】
2005522968.tif 000055
は、それが第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成できるように選択される。
【数５４】
2005522968.tif 000056
は、前述したように、許容できるペアリングであることが好ましい。ブロック４０６において、第１の群Γ１のジェネレータＰが選択される。ブロック４０８において、ファンクションＨが選択される。この場合、ファンクションＨは、二進数字列から第１の群Γ１の要素を生成できるように選択される。ブロック４１０においては、最初の署名者のために秘密鍵ｓｏｒが選択される。ブロック４１２においては、最初の署名者のために公開鍵ｓｏｒＰが生成される。同様に、ブロック４１４においては、プロキシ署名者のために秘密鍵ｓｐｒが選択され、また、ブロック４１６においては、プロキシ署名者のために公開鍵ｓｐｒＰが生成される。ブロック４１８において、最初の署名者は、プロキシ秘密鍵ｓｏｒＰｐｒをプロキシ署名者に与える。ここで、Ｐｐｒ＝Ｈ（ｓｐｒＰ）である。ブロック４２０においては、最初の署名者の代わりにメッセージに署名するため、プロキシ署名者は、最初に、メッセージファンクション値ＰＭ＝Ｈ（Ｍ）を生成する。また、メッセージＭに加えて他の情報を使用して、メッセージファンクション値ＰＭを生成しても良い。技術的に分かるように、ファンクションＨへの入力及びファンクションＨそれ自体は、様々な方法で調整され得る。例えば、最初の署名者は、Ｐｐｒ＝Ｈ（ｓｐｒＰ，Ｃ）等のようにファンクション中に「規約」Ｃを含ませることにより、プロキシ署名者の権限の範囲を制限しても良い。その後、ブロック４２２において、プロキシ署名者は、デジタル署名Ｓｉｇ＝ｓｏｒＰｐｒ＋ｓｐｒＰＭを生成することにより、デジタルメッセージＭに署名する。ステップ４２４において、プロキシの署名が最初の署名者の署名を表わすことを検証するため、検証者は、
【数５５】
2005522968.tif 000057
であることを確認する。
【００６８】
（階層的な同一性に基づくオンライン／オフライン署名）
多くの用途において、メッセージの署名に要する総時間は、オンライン署名時間ほど重要ではない。オンライン署名時間は、メッセージを得た後に署名者が署名を作成するために必要な時間であると一般に考えられている。オンライン／オフライン署名スキームは、オンライン署名に要する時間を減らすために提案されてきた。例えば、そのようなスキームの１つは、「トラップドアハッシュ関数」ｈ及び「ハッシュ署名スイッチ」パラダイムを使用する。しかしながら、オンライン／オフライン署名スキームは、階層型の同一性に基づく署名システムに利用できなかった。
【００６９】
本発明は、階層型の同一性に基づくオンライン／オフライン署名スキームを提供する。図５は、本発明の他の実施形態に係る、デジタルメッセージＭのデジタル署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。この方法は、階層型の同一性に基づくシステムとの関連において、２段階の署名プロセスを含んでいる。第１段階の署名プロセスは、オフラインで完了され得る。これにより、第２段階の署名プロセスだけがオンラインで完了され、その結果、オンライン署名時間が短くなる。
【００７０】
この階層型スキームにおける署名者ｙは、階層中のルートＰＫＧよりもｔレベル下であり、ＩＤ−タプル（ＩＤｙ１，．．．．，ＩＤｙｔ）に関連付けられている。署名者のＩＤ−タプルは、署名者に関連付けられた同一性情報ＩＤｙｔと、階層中におけるそのｔ−１個の先祖下位レベルＰＫＧの各々に関連付けられた同一性情報ＩＤｙｉと、を含んでいる。この方法は、複数の要素から成る第１及び第２の循環群Γ１及びΓ２を生成することにより、ブロック５０２から開始される。ブロック５０４においては、
【数５６】
2005522968.tif 000058
が選択される。この場合、
【数５７】
2005522968.tif 000059
は、それが第１の循環群Γ１の２つの要素から第２の循環群Γ２の１つの要素を生成できるように選択される。
【数５８】
2005522968.tif 000060
は、前述したように、許容できるペアリングであることが好ましい。ブロック５０６において、第１の循環群Γ１のルートジェネレータＰ０が選択される。ブロック５０８においては、ルートＰＫＧに関連付けられ且つルートＰＫＧだけに知られたランダムルート鍵生成シークレットｓ０が選択される。ｓ０は、循環群Ｚ／ｑＺの１つの要素であることが好ましい。ブロック５１０においては、ルート鍵生成パラメータＱ０＝ｓ０Ｐ０が生成される。Ｑ０は、第１の循環群Γ１の１つの要素であることが好ましい。ブロック５１２においては、第１のファンクションＨ１が選択される。この場合、ファンクションＨ１は、第１の二進数字列から第１の循環群Γ１の要素を生成できるように選択される。ブロック５１４においては、第２のファンクションＨ２が選択される。この場合、ファンクションＨ２も、第１の二進数字列から第１の循環群Γ１の要素を生成できるように選択される。一例として、Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎに開示されたファンクションのようなファンクションがＨ１およびＨ２として使用され得る。実際には、ファンクションＨ１およびＨ２は、全く同じファンクションであっても良い。しかしながら、潜在的な落とし穴がある。署名者がＭ＝ＩＤｔに署名するように攻撃者が仕向ける虞がある。ここで、ＩＤｔは、実際の同一性を表わしている。この場合、署名者の署名は、実際には、その後にメッセージを復号して署名を偽造するために使用される虞がある、秘密鍵であるかもしれない。しかしながら、この落とし穴は、署名と秘密鍵抽出とを区別する幾つかの方法、例えばＨ２のための異なるファンクションやビットプレフィックス等、を使用することにより、回避することができる。ブロック５０２からブロック５１４のファンクションは、前述したルートセットアップアルゴリズムの一部であり、ほぼ同時に実行されることが好ましい。
【００７１】
次の一連のブロック（ブロック５１６から５２４）は、下位レベルセットアップアルゴリズムの一部として実行されるファンクションを示している。ブロック５１６においては、署名者のｔ−１個の先祖下位レベルＰＫＧの各々に、パブリック要素Ｐｙｉが生成される。１≦ｉ≦ｔ−１において各パブリック要素Ｐｙｉ＝Ｈ（ＩＤ１，．．．．，ＩＤｙｉ）は、第１の循環群Γ１の１つの要素であることが好ましい。全てのパブリック要素Ｐｙｉの生成が１つのブロックで表わされているが、これらのパブリック要素Ｐｙｉの生成は、同時に行なわれることなく経時的に行なわれても良い。
【００７２】
署名者のｔ−１個の先祖下位レベルＰＫＧの各々に、下位レベル鍵生成シークレットｓｙｉが選択される（ブロック５１８）。下位レベル鍵生成シークレットｓｙｉは、１≦ｉ≦ｔ−１において循環群Ｚ／ｑＺの要素であることが好ましく、また、各下位レベル鍵生成シークレットｓｙｉは、その対応する下位レベルＰＫＧだけに知られていることが好ましい。この場合も同様に、シークレットｓｙｉの選択が１つのブロックで表わされているが、これらのシークレットｓｙｉの選択は、同時に行なわれることなく経時的に行なわれても良い。
【００７３】
署名者のｍ個の先祖下位レベルＰＫＧの各々に、下位レベルシークレット要素Ｓｙｉが生成される（ブロック５２０）。１≦ｉ≦ｔ−１において各下位レベルシークレット要素Ｓｙｉ＝Ｓｙ（ｉ−１）＋ｓｙ（ｉ−１）Ｐｙｉは、第１の循環群Γ１の要素であることが好ましい。パブリック要素Ｐｙｉおよびシークレットｓｙｉと同様に、シークレット要素Ｓｙｉの生成が１つのブロックで表わされているが、これらのシークレット要素Ｓｙｉの生成は、同時に行なわれることなく経時的に行なわれても良い。これらの繰り返される鍵生成プロセスのため、Ｓ０は、Γ１の同一性要素として規定されることが好ましい。
【００７４】
また、署名者のｔ−１個の先祖下位レベルＰＫＧの各々に、下位レベル鍵生成パラメータＱｙｉも生成される（ブロック４２２）。１≦ｉ≦ｔ−１において各鍵生成パラメータＱｙｉ＝ｓｙｉＰ０は、第１の循環群Γ１の要素であることが好ましい。鍵生成パラメータＱｙｉの生成が１つのブロックで表わされているが、これらの鍵生成パラメータＱｙｉの生成は、同時に行なわれることなく経時的に行なわれても良い。
【００７５】
次の２つのブロック（ブロック５２４、５２６）のファンクションは、前述した抽出アルゴリズムの一部として実行される。ブロック５２４においては、署名者ｙに関連付けられた署名者パブリック要素Ｐｙｔが生成される。署名者パブリック要素Ｐｙｔ＝Ｈ１（ＩＤｙ１，．．．．，ＩＤｙｔ）は、第１の循環群Γ１の要素であることが好ましい。その後、ブロック５２６において、署名者ｙに関連付けられた署名者シークレット要素Ｓｙｔが生成される。また、署名者シークレット要素
【数５９】
2005522968.tif 000061
も、第１の循環群Γ１の要素であることが好ましい。
【００７６】
便宜上、第１のファンクションＨ１は、随意的に、反復関数となるように選択されても良い。この場合、例えば、Ｈ１（ＩＤ１，．．．，ＩＤｙｉ）としてではなく、Ｈ１（Ｐｙ（ｉ−１），ＩＤｙｉ）として、パブリックポイントＰｉが演算され得る。
【００７７】
図５に示される最後の２つのブロック（ブロック５２８、５３０）は、前述した署名アルゴリズムおよび検証アルゴリズムを表わしている。２段階の署名アルゴリズムは、従来知られた方法にしたがって修正された離散ログに基づくトラップドアハッシュ関数であることが好ましいトラップドアハッシュ関数ｈを使用して、楕円曲線に適用することを含んでいる。したがって、ブロック５２８においては、ランダムトラップドアシークレットｓｙｔ'∈Ｚ／ｑＺが選択される。署名プロセス中、署名者は、そのパブリックハッシュ鍵として、Ｑｙｔ'＝ｓｙｔ'Ｐ０を検証者に対して与えることができる。例えば、署名者は、署名者の下位レベルシークレット要素ｓｙｔと等しくなるようにｓｙｔ'を選択することができる。いずれにしても、ｓｙｔ'は、各署名毎に新たに生成されることが好ましい。
【００７８】
署名者がランダムメッセージＭ'及び乱数ｒ'を選択すると、ブロック５３０において、署名アルゴリズムが継続する。その後、ブロック５３２において、署名者は、ランダムメッセージＭ'に署名して、署名［Ｕ１，Ｑｙ１，．．．．，Ｑｙｔ，Ｑｙｔ'］を生成する。ここで、１≦ｉ≦ｔにおいて、
【数６０】
2005522968.tif 000062
であり、ＰＭ'＝Ｈ２（（Ｍ＋ｒ'ｓｙｔ'）Ｐ０）である。署名アルゴリズムのこの部分は、オフラインで完了され得る。
【００７９】
署名されるべきメッセージＭを署名者が確認した後、署名アルゴリズムのオンライン部分が完了され得る。ブロック５３４において、署名者は、Ｍ＋ｒｓｙｔ'＝Ｍ'＋ｒ'ｓｙｔ'←→ｒ＝（ｓｙｔ'）−１（Ｍ'−Ｍ）＋ｒ'となるように、数ｒを決定する。この場合、ｑを法として、ｓｙｔ'の逆数がとられる。その後、署名者は、メッセージＭ及び署名Ｓｉｇと共に、ｒを検証者に送り得る。
【００８０】
その後、ステップ５３６において、検証者は、検証アルゴリズムを完了し、
【数６１】
2005522968.tif 000063
を確認することにより署名を検証し得る。ここで、ＰＭ＝Ｈ２（ＭＰ０＋ｒＱｙｔ'）＝ＰＭ'である。また、検証アルゴリズムも、検証者が所有している情報に応じて、オンライン段階とオフライン段階とに分解され得る。例えば、署名者は、メッセージＭを知る前に、様々な情報を検証者に対して与え得る。このようにすれば、検証者は、（１）署名者のＱｙｉ値、（２）ＰＭ'、署名者のトラップドアハッシュ関数Ｈ２の極最近の出力、（３）Ｕ、ハッシュ関数出力に関する署名者の部分的な署名、（４）Ｍ、署名されるメッセージ、（５）値ｒを含む署名者の完全な署名、のうちのどれか又は全てを知ることができる。この情報を使用すると、検証者は、メッセージＭが知られ或いは署名される前であっても、署名の一部を検証し始めることができる。例えば、検証者が署名者から先の署名を受けたなら、検証者は署名者のＱｙｉ値を知る。これにより、検証者は、署名者が階層中のどの深さにいようとも、署名者の署名を検証するために必要な２つのペアリングを除く全てを予め計算することができる。検証者は、ＰＭ'及びＰＭ'に関する署名者の署名Ｕを受けた後に、最後の２つのペアリング計算を完了し得る。署名者の完全な署名は、点の付加を使用すること  −検証者は、ＰＭ＝ＭＰ０＋ｒＱｙｔ'を計算してこの値がＰＭ'と同じであることを確認する−  で検証され得る。これは、オンラインで完了されなければならない唯一の検証ステップである。なぜなら、これは、メッセージＭに依存する唯一のステップだからである。計算する必要があるペアリングは無い。したがって、検証のオンライン部分は、非常に効率的である。
【００８１】
（署名スキームと共に使用するためのシステム）
本発明に係るバイリニアなマッピングを含む様々な署名スキ−ムを説明してきた。ここで、図６を参照しながら、これらのスキームを実施するための本発明の他の実施形態に係るシステムについて説明する。このシステムは、多数の端末６０２、６０４、６０６、６０８を有している。これらの各端末は、前述した署名スキームに基づいて署名を生成し或いは検証するエンティティに関連付けられ得る。また、当該システムは、秘密鍵を生成してこれらを様々な端末６０２、６０４、６０６、６０８に分配する１または複数の秘密鍵ジェネレータ（ＰＫＧ）６３０を有している。
【００８２】
各端末は、メモリ６１２と双方向通信を行なうプロセッサ６１０を有している。プロセッサ６１０は、前述した処理を行なってデジタル署名を生成又は検証するための適切なプログラムコードを実行する。また、プロセッサ６１０は、他の端末に送信される情報を生成するために適切なプログラムコードを実行する。適切なプログラムコードは、従来より知られる方法にしたがって生成され得る。メモリ６１２は、プログラムコードと、デジタル署名の生成及び検証の処理の実行中に使用される中間結果及び他の情報と、を記憶する。
【００８３】
通信ネットワーク６２０が与えられ、この通信ネットワーク６２０を介して、エンティティ６０２、６０４、６０６、６０８及びＰＫＧ６３０が通信を行ない得る。通信ネットワーク６２０は、例えば、適切な通信ネットワークを提供するＬＡＮコンピュータネットワーク、ＷＡＮコンピュータネットワーク、及び／又は、携帯電話ネットワークを含む、様々な一般的な形態であり得る。
【００８４】
本発明は、特に好適な実施形態及び例図に関連して詳細に記述されてきたが、本発明の思想及び範囲内で変形や変更が行なわれ得ることが理解される。
【００８５】
（産業上の利用可能性）
前述した方法及びシステムは、一般に、コンピュータネットワークまたは他のタイプのシステム及び装置を介した暗号化及び安全な通信に適用可能である。前記方法及びシステムは、公開鍵暗号化を使用するシステムにおいて通信の署名を生成して検証するためのスキームとして、特に有用である。
【００８６】
このように、本発明に従って、前述した利点を十分に与える方法及びシステムが開示されている。本発明の特定の例示的な実施形態を参照して、本発明を説明して図示してきたが、本発明は、これらの例示的な実施形態に限定されない。当業者であれば分かるように、本発明の思想から逸脱することなく、変形及び変更を行なうことができる。したがって、添付の請求項及びその等価物の範囲内にあるそのような変形及び変更の全てが本発明の中に含まれる。
【図面の簡単な説明】
【００８７】
【図１】現在において好ましい本発明の一実施形態に係る、デジタルメッセージＭのマルチ署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【図２】現在において好ましい本発明の他の実施形態に係る、一人の署名者と一人の検証者との間で通信されるデジタルメッセージＭのリング署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【図３】現在において好ましい本発明の他の実施形態に係る、ある階層中の一人の署名者と一人の検証者との間で通信されるデジタルメッセージＭのリング署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【図４】本発明の他の実施形態に係る、デジタルメッセージＭのプロキシ署名Ｓｉｇを生成して検証する方法を表わすフローチャートを示している。
【図５】本発明の他の実施形態に係る、デジタルメッセージＭの署名Ｓｉｇを生成して検証する方法を表わすフローチャートであって、署名アルゴリズム及び検証アルゴリズムの一部がオフラインで完了され得るフローチャートを示している。
【図６】本発明の他の実施形態に係る、署名スキームを実施するためのシステムを表わすブロック図を示している。
【図１】
2005522968.tif 000100
【図２】
2005522968.tif 000101
【図３】
2005522968.tif 000102
【図４】
2005522968.tif 000103
【図５】
2005522968.tif 000104
【図６】
2005522968.tif 000105
【国際調査報告】
2005522968.tif 000106