(57)【要約】  対称の双線形写像をもつ群にも適用できる群構造維持署名方式であって、署名長が短く、かつ、検証式の計算効率が良い方式を提供する。少なくともｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとする。そして、署名装置は、０以上ｐ−１以下の整数からランダムにζ，ρを選び、ｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する。検証装置は、２つの検証式を用いて署名σを確認する。
2013111673.tif 000002
【特許請求の範囲】
【請求項１】
署名を生成する署名装置と、署名を検証する検証装置を有する署名検証システムであって、
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
前記署名装置は、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録部と、
０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数１８】
2013111673.tif 000020
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成部と
を備え、
前記検証装置は、
前記公開鍵ｖｋを記録する検証記録部と、
【数１９】
2013111673.tif 000021
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証部
を備える
署名検証システム。
【請求項２】
署名を生成する署名装置と、署名を検証する検証装置を有する署名検証システムであって、
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
前記署名装置は、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録部と、
０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２０】
2013111673.tif 000022
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成部と
を備え、
前記検証装置は、
前記公開鍵ｖｋを記録する検証記録部と、
【数２１】
2013111673.tif 000023
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証部
を備える
署名検証システム。
【請求項３】
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録部と、
０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２２】
2013111673.tif 000024
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成部と
を備える署名装置。
【請求項４】
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録部と、
０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２３】
2013111673.tif 000025
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成部と
を備える署名装置。
【請求項５】
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとして記録する検証記録部と、
【数２４】
2013111673.tif 000026
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証部
を備える検証装置。
【請求項６】
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとして記録する検証記録部と、
【数２５】
2013111673.tif 000027
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証部
を備える検証装置。
【請求項７】
署名を生成する署名装置と、署名を検証する検証装置を用いた署名検証方法であって、
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
前記署名装置が、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録ステップと、
前記署名装置が、０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２６】
2013111673.tif 000028
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成ステップと、
前記検証装置が、前記公開鍵ｖｋを記録する検証記録ステップと、
前記検証装置が、
【数２７】
2013111673.tif 000029
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証ステップ
を有する署名検証方法。
【請求項８】
署名を生成する署名装置と、署名を検証する検証装置を用いた署名検証方法であって、
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
前記署名装置が、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録ステップと、
前記署名装置が、０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２８】
2013111673.tif 000030
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成ステップと、
前記検証装置が、前記公開鍵ｖｋを記録する検証記録ステップと、
前記検証装置が、
【数２９】
2013111673.tif 000031
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証ステップ
を有する署名検証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号プロトコル中で利用しやすいデジタル署名方法を提供する署名検証システム、署名装置、検証装置、署名検証方法に関する。
【背景技術】
【０００２】
デジタル署名は、公開鍵ｐｋに対応する秘密鍵ｓｋを知る署名者が、メッセージＭに対して秘密鍵ｓｋを正しく使ったときにのみ計算できる値ｓを算出し、これを電子的な署名として用いるものである。正しく計算された署名は、誰でも公開鍵ｐｋを用いてその正当性を検証することが可能であり、秘密鍵ｓｋを知らないいかなる第三者も正当な署名ｓを算出することはできない。【０００３】
デジタル署名は、電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより、署名構成要素（公開鍵ｐｋ，署名ｓ，メッセージＭ）の一部あるいは全部を秘密にしたまま、それらが検証式を満たす正しいものであることを任意の第三者に納得させるなど、高度な利用形態がしばしば見受けられる。【０００４】
近年のペアリング技術の進展によって、群の要素が双線形写像の積で記述された等式を満たすという事実を効率的に証明するゼロ知識証明（Jens Groth and Amit Sahai, “Efficient Non-interactive Proof Systems for Bilinear Groups”, Eurocrypt 2008, LNCS 2965, pp.415-432）が構成可能になった。これによって、署名構成要素がいずれも群要素であり、署名検証式が双線形写像の積である署名方式があれば、どの署名構成要素でも容易に秘匿することができるようになった。署名構成要素がいずれも群要素であり、署名検証式が双線形写像の積である署名方式は群構造維持署名方式とよばれる。【０００５】
群構造維持署名方式としては、非特許文献１〜４などが従来技術として知られている。非特許文献１の技術は、いわゆるCL-Signatureと呼ばれる方法である。しかしながら、この方法ではランダムオラクルと呼ばれる理想化された実現不可能な構成要素を用いており、現実の実施においてはその安全性が明確でない。【０００６】
非特許文献２には、CL-Signatureを、ランダムオラクルを用いないように改良した方式が示されている。しかし、この方式はランダムに選んだメッセージに対する安全性のみを保証しており、署名の安全性として一般的に求められる選択メッセージ攻撃に対する安全性は明確でない。【０００７】
非特許文献３には、選択メッセージ攻撃に強いことが保証されている方法が示されている。この方法では、署名は、以下の２つの検証式を満たす７つの群要素σ＝（ｚ，ｒ，ｓ，ｔ，ｕ，ｖ，ｗ）からなる。【０００８】
【数１】
2013111673.tif 000003
【０００９】
なお、検証式中でσに含まれていない要素はすべて公開鍵である。【００１０】
非特許文献４には、非特許文献３の方式よりも少ない個数の群要素から署名が構成できる方式が示されている。しかし、この方法は非対称の双線形写像をもつ群においてのみ安全であり、暗号プロトコルの構成でしばしば用いられる対称の双線形写像を持つ群においては具体的な攻撃が存在する。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Jan Camenisch and Anna Lysyanskaya, “Signature Schemes and Anonymous Credentials from Bilinear Maps”, Crypto 2004, LNCS 3152, pp.56-72.
【非特許文献２】Matthew Green and Susan Hohenberger, “Universally Composable Adaptive Oblivious Transfer”, IACR e-Print archive, 2008/163 ［平成２３年１２月３１日検索］、インターネット<URL: http://eprint.iacr.org/cgi-bin/getfile.pl?entry=2008/163&version=20080806:150034&file=163.pdf>.
【非特許文献３】Masayuki Abe, Kristiyan Haralambiev and Miyako Ohkubo, “Signing on Elements in Bilinear Groups for Modular Protocol Design”, IACR e-print 2010/133 ［平成２３年１２月３１日検索］、インターネット<URL: http://eprint.iacr.org/2010/133>.
【非特許文献４】Masayuki Abe, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo, “Optimal Structure-Preserving Signatures in Asymmetric Bilinear Groups”, Crypto 2011, Springer.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上述の非特許文献１、２は現実の実施における安全性が不明確という問題がある。非特許文献３の方式は署名が群要素７つからなり、群要素Ｋ個からなるメッセージに対する署名検証には１０＋２Ｋ回のペアリング演算を要する。したがって、署名ビット長、演算量ともに多い。非特許文献４の方式は、対称の双線形写像をもつ群においては安全ではない。【００１３】
これらの問題点に鑑み、本発明は、対称の双線形写像をもつ群であっても適用できる群構造維持署名方式であって、署名長が短く、かつ、検証式の計算効率が良い方式を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の署名検証システムは、署名を生成する署名装置と、署名を検証する検証装置を有する。まず、Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ  （ただし、ｋ＝１，…，Ｋ）
とする。【００１５】
署名装置は、少なくとも署名記録部と署名生成部を備える。署名記録部は、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する。署名生成部は、０以上ｐ−１以下の整数からランダムにζ，ρを選び、【００１６】
【数２】
2013111673.tif 000004
【００１７】
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する。【００１８】
検証装置は、少なくとも検証記録部と検証部を備える。検証記録部は、公開鍵ｖｋを記録する。検証部は、【００１９】
【数３】
2013111673.tif 000005
【００２０】
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する。【００２１】
なお、γｕとγｖは０と決めてもよい。この場合は、ｇｕ＝ｇｖ＝１，ｅ（ｇｕ，ｇｖ）＝１なので、公開鍵ｖｋにｅ（ｇｕ，ｇｖ）を求めるために必要な情報は必要ない。また、秘密鍵ｓｋにγｕとγｖは必要ない。また、署名生成部は、ｒを、【００２２】
【数４】
2013111673.tif 000006
【００２３】
のように求めればよい。そして、検証部は、【００２４】
【数５】
2013111673.tif 000007
【００２５】
の２つの式が成り立つかを確認すればよい。
【発明の効果】
【００２６】
本発明の署名検証システムによれば、２つの検証式を用いて検証しているので、非特許文献３の方法と同じように、対称の双線形写像の場合でも安全性を確保できる。その上で、署名σは４つの群要素ｗ，ｓ，ｔ，ｒで構成されるので、７つの群要素を必要とする非特許文献３に比べて署名長を短くできる。また、検証でのペアリング演算の回数を、γｕとγｖを０にした場合は６＋２Ｋ回、γｕとγｖをランダムに選択した場合は７＋２Ｋ回にできる。したがって、非特許文献３の１０＋２Ｋ回に比べて計算量を減らすことができる。
【図面の簡単な説明】
【００２７】
【図１】本発明の署名検証システムの構成例を示す図。
【図２】署名装置の処理フローを示す図。
【図３】検証装置の処理フローを示す図。
【発明を実施するための形態】
【００２８】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２９】
＜構成と処理＞
図１に本発明の署名検証システムの構成例を示す。図２に署名装置の処理フローを、図３に検証装置の処理フローを示す。署名検証システムは、少なくとも署名装置１００と検証装置２００を含む。署名装置１００は秘密鍵ｓｋと公開鍵ｖｋとを記録し、メッセージＭに対する署名σを生成する。検証装置２００は公開鍵ｖｋを記録し、署名σが正しく秘密鍵ｓｋを用いて生成したメッセージＭに対する署名かを検証する。公開鍵ｖｋ、メッセージＭ、署名σは、署名装置１００と検証装置２００との間で共有されるが、共有させる方法はネットワークを使用した手段であっても、可搬の記録媒体を使用した手段であってもよい。図１では、署名装置１００と検証装置２００は、ネットワーク８００でつながれている。【００３０】
まず、Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とする。【００３１】
鍵生成部１１０は、０以上ｐ−１以下の整数からγｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を選択する。選択はランダムに行えばよい。そして、ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ  （ただし、ｋ＝１，…，Ｋ）
のように求める（Ｓ１１０）。これらのデータは、あらかじめ求めておいていくつかの署名に対して共通に用いてもよいし、署名生成のたびに変更してもよい。【００３２】
署名装置１００は、少なくとも署名記録部１９０と署名生成部１２０を備える。鍵生成部１１０は、署名装置１００が備えてもよいし、署名装置１００以外の別の装置が備えてもよい。署名装置１００は、ネットワーク８００を介してデータを授受するための署名入出力部１８０も備えてもよい。署名記録部１９０は、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する（Ｓ１９０）。例えば、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す記述Λと、ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を公開鍵ｖｋとしてもよい。あるいは、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す記述Λと、ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ），｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を公開鍵ｖｋとしてもよい。【００３３】
署名生成部１２０は、０以上ｐ−１以下の整数からランダムにζ，ρを選び、【００３４】
【数６】
2013111673.tif 000008
【００３５】
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する（Ｓ１２０）。署名の対象となるメッセージＭは、Ｋ個の群Ｇ１の元からなる。通常のメッセージは任意長の整数であるが、本願発明では、Ｋ個の群Ｇ１の元をメッセージＭとする。署名の対象となるメッセージが短い場合には、Ｋ個の群Ｇ１の元となるようにパディングによってメッセージＭを作ればよい。なお、パディングする値は、群Ｇ１の元の中の１つをあらかじめ選んでおけばよい。署名入出力部１８０は、ネットワーク８００を介して署名σを検証装置２００に送る（Ｓ１８０）。【００３６】
検証装置２００は、少なくとも検証記録部２９０と検証部２１０を備える。検証記録部２９０は、公開鍵ｖｋを記録する（Ｓ２９０）。検証装置２００は、ネットワーク８００を介してデータの授受を行う検証入出力部２８０を備えてもよい。検証入出力部２８０は、ネットワーク８００を介して署名σを受け取る（Ｓ２８０）。【００３７】
検証部２１０は、【００３８】
【数７】
2013111673.tif 000009
【００３９】
の２つの検証式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する（Ｓ２１０）。
＜検証式の解説＞
上述の検証式の１つ目の式の左辺は、【００４０】
【数８】
2013111673.tif 000010
【００４１】
である。一方、右辺は、【００４２】
【数９】
2013111673.tif 000011
【００４３】
である。したがって、署名が正しければ１つ目の式が成り立つ。また、２つ目の式の左辺は、【００４４】
【数１０】
2013111673.tif 000012
【００４５】
である。一方、右辺は、【００４６】
【数１１】
2013111673.tif 000013
【００４７】
である。したがって、署名が正しければ２つ目の式が成り立つ。【００４８】
＜対称の双線形写像でも安全な理由＞
対称の双線形写像の場合、
ｅ（ｇ１，ｇ２）ｅ（ｇ２，ｇ１−１）
＝ｅ（ｇ１，ｇ２）ｅ（ｇ２，ｇ１）−１
＝１
なので、ｅ（ｇ１，ｇ２）ｅ（ｇ２，ｇ１−１）を乗算しても、群上の演算結果は変わらない。例えば、検証式の１つ目の式は以下のように変形できる。【００４９】
【数１２】
2013111673.tif 000014
【００５０】
つまり、ｍ１’＝ｍ１ｇ２，ｍ２’＝ｍ２ｇ１−１であるｍ１’，ｍ２’を含むメッセージＭ’＝（ｍ１’，ｍ２’，…，ｍＫ）であっても１つ目の式だけであれば成り立つことになる。したがって、１つの式だけでは対称の双線形写像の場合には署名の安全性を確保できない。【００５１】
ここで、メッセージＭ’に対する２つ目の式について確認する。２つ目の式の右辺は、【００５２】
【数１３】
2013111673.tif 000015
【００５３】
となる。しかし、ｅ（ｈ１，ｇ２）ｅ（ｈ２，ｇ１−１）は１ではないので、この式は左辺であるｅ（ｈｕ，ｈｖ）とは一致しない。したがって、２つ目の式が成り立たない。したがって、２つの検証式を用いれば、対称の双線形写像の場合でも安全性を確保できる。【００５４】
＜効果＞
本発明の署名検証システムによれば、２つの検証式を用いて検証しているので、非特許文献３の方法と同じように、対称の双線形写像の場合でも安全性を確保できる。したがって、対称の双線形写像をもつ群上で構成される他の暗号プロトコル構成要素（公開鍵暗号、コミットメントなど）と組み合わせて効率的に暗号プロトコルを構成できる。その上で、署名σは４つの群要素ｗ，ｓ，ｔ，ｒで構成されるので、７つの群要素を必要とする非特許文献３に比べ、署名長を短くできる。また、検証でのペアリング演算の回数を、７＋２Ｋ回にできる。したがって、非特許文献３の１０＋２Ｋ回に比べ、計算量を減らすことができる。【００５５】
［変形例］
本変形例も図１〜３を用いて説明する。本変形例の署名検証システムは、少なくとも署名装置１００’と検証装置２００’を含む。群や変数の条件で実施例１と異なるのは、γｕとγｖを０とする点だけである。この場合、ｇｕ＝ｇｖ＝１，ｅ（ｇｕ，ｇｖ）＝１なので、公開鍵ｖｋにｅ（ｇｕ，ｇｖ）を求めるために必要な情報は必要ない。また、秘密鍵ｓｋにγｕとγｖは必要ない。また、署名生成部１２０’は、ｒを、【００５６】
【数１４】
2013111673.tif 000016
【００５７】
のように求めればよい。そして、検証部２１０’は、【００５８】
【数１５】
2013111673.tif 000017
【００５９】
の２つの式が成り立つかを確認すればよい。言い換えると、以下のように本発明の署名検証システムを、γｕ，γｖ，ｇｕ，ｇｖを用いない署名検証システムに変形できる。【００６０】
鍵生成部１１０’は、０以上ｐ−１以下の整数からγｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を選択する。選択はランダムに行えばよい。そして、ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ  （ただし、ｋ＝１，…，Ｋ）
のように求める（Ｓ１１０’）。【００６１】
署名記録部１９０’は、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する（Ｓ１９０’）。例えば、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す記述Λと、ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を公開鍵ｖｋとしてもよい。あるいは、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す記述Λと、ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｅ（ｈｕ，ｈｖ），｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を公開鍵ｖｋとしてもよい。【００６２】
署名生成部１２０’は、０以上ｐ−１以下の整数からランダムにζ，ρを選び、【００６３】
【数１６】
2013111673.tif 000018
【００６４】
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する（Ｓ１２０’）。署名入出力部１８０’は、ネットワーク８００を介して署名σを検証装置２００’に送る（Ｓ１８０’）。【００６５】
検証装置２００’は、少なくとも検証記録部２９０’と検証部２１０’を備える。検証記録部２９０’は、公開鍵ｖｋを記録する（Ｓ２９０’）。検証装置２００’は、ネットワーク８００を介してデータの授受を行う検証入出力部２８０’を備えてもよい。検証入出力部２８０’は、ネットワーク８００を介して署名σを受け取る（Ｓ２８０’）。【００６６】
検証部２１０’は、【００６７】
【数１７】
2013111673.tif 000019
【００６８】
の２つの検証式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する（Ｓ２１０’）。【００６９】
本変形例の場合、実施例１と異なるのはγｕとγｖを０とする点だけである。この場合、ｇｕ＝ｇｖ＝１，ｅ（ｇｕ，ｇｖ）＝１なので、署名が正しければ上記の２つの検証式が成り立つ。【００７０】
本変形例の場合も、２つの検証式を用いて検証しているので、非特許文献３の方法と同じように、対称の双線形写像の場合でも安全性を確保できる。その上で、署名σは４つの群要素ｗ，ｓ，ｔ，ｒで構成されるので、７つの群要素を必要とする非特許文献３に比べ、署名長を短くできる。さらに、検証でのペアリング演算の回数を、６＋２Ｋ回にできる。したがって、非特許文献３の１０＋２Ｋ回に比べ、計算量を減らすことができる。
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。【００７１】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。【００７２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。【００７３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。【００７４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。【００７５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７６】
本発明は、電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用することができる。
【符号の説明】
【００７７】
１００，１００’  署名装置          １１０，１１０’  鍵生成部
１２０，１２０’  署名生成部        １８０，１８０’  署名入出力部
１９０，１９０’  署名記録部        ２００，２００’  検証装置
２１０，２１０’  検証部            ２８０，２８０’  検証入出力部
２９０，２９０’  検証記録部        ８００  ネットワーク
【図１】
2013111673.tif 000032
【図２】
2013111673.tif 000033
【図３】
2013111673.tif 000034
【手続補正書】
【提出日】平成26年7月4日(2014.7.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
署名を生成する署名装置と、署名を検証する検証装置を有する署名検証システムであって、
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
前記署名装置は、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録部と、
０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数１８】
2013111673.tif 000035
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成部と
を備え、
前記検証装置は、
前記公開鍵ｖｋを記録する検証記録部と、
【数１９】
2013111673.tif 000036
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証部
を備える
署名検証システム。
【請求項２】
署名を生成する署名装置と、署名を検証する検証装置を有する署名検証システムであって、
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
前記署名装置は、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録部と、
０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２０】
2013111673.tif 000037
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成部と
を備え、
前記検証装置は、
前記公開鍵ｖｋを記録する検証記録部と、
【数２１】
2013111673.tif 000038
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証部
を備える
署名検証システム。
【請求項３】
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録部と、
０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２２】
2013111673.tif 000039
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成部と
を備える署名装置。
【請求項４】
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録部と、
０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２３】
2013111673.tif 000040
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成部と
を備える署名装置。
【請求項５】
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、ｗを群Ｇ１の元、ｓ、ｔ、ｒはＧ２の元、検証の対象となる署名をｗ、ｓ、ｔ、ｒを含むデータ、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとして記録する検証記録部と、
【数２４】
2013111673.tif 000041
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証部
を備える検証装置。
【請求項６】
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、ｗを群Ｇ１の元、ｓ、ｔ、ｒはＧ２の元、検証の対象となる署名をｗ、ｓ、ｔ、ｒを含むデータ、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとして記録する検証記録部と、
【数２５】
2013111673.tif 000042
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証部
を備える検証装置。
【請求項７】
署名を生成する署名装置と、署名を検証する検証装置を用いた署名検証方法であって、
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｇｕ，ｈｕ，ｇｖ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｇｕ＝ｇ１＾γｕ，  ｈｕ＝ｇ１＾δｕ，
ｇｖ＝ｇ２＾γｖ，  ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
前記署名装置が、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｇｕ，ｇｖ），ｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，γｕ，δｕ，γｖ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録ステップと、
前記署名装置が、０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２６】
2013111673.tif 000043
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成ステップと、
前記検証装置が、前記公開鍵ｖｋを記録する検証記録ステップと、
前記検証装置が、
【数２７】
2013111673.tif 000044
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証ステップ
を有する署名検証方法。
【請求項８】
署名を生成する署名装置と、署名を検証する検証装置を用いた署名検証方法であって、
Ｇ１，Ｇ２，ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、Ｋを１以上のあらかじめ定めた整数、ｋを１以上Ｋ以下の整数、ｍ１，…，ｍＫを群Ｇ１の元、メッセージＭをＭ＝（ｍ１，…，ｍＫ）、＾をべき乗を示す記号とし、
γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝はそれぞれ０以上ｐ−１以下の整数であり、
ｇｓ，ｈｓ，ｇｔ，ｈｔ，ｈｕ，ｈｖ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝は
ｇｓ＝ｇ１＾γｓ，  ｈｓ＝ｇ１＾δｓ，
ｇｔ＝ｇ１＾γｔ，  ｈｔ＝ｇ１＾δｔ，
ｈｕ＝ｇ１＾δｕ，
ｈｖ＝ｇ２＾δｖ，
ｇｋ＝ｇ１＾γｋ，  ｈｋ＝ｇ１＾δｋ 
ただし、ｋ＝１，…，Ｋ
であり、
前記署名装置が、ｐ，Ｇ１，Ｇ２，ＧＴ，ｅ，ｇ１，ｇ２を示す情報とｅ（ｈｕ，ｈｖ）を求めるために必要な情報とｇｓ，ｈｓ，ｇｔ，ｈｔ，｛ｇ１，ｈ１｝，…，｛ｇＫ，ｈＫ｝を含むデータを公開鍵ｖｋとし、ｖｋ，γｓ，δｓ，γｔ，δｔ，δｕ，δｖ，｛γ１，δ１｝，…，｛γＫ，δＫ｝を含むデータを秘密鍵ｓｋとして記録する署名記録ステップと、
前記署名装置が、０以上ｐ−１以下の整数からランダムにζ，ρを選び、
【数２８】
2013111673.tif 000045
であるｗ，ｓ，ｔ，ｒを求め、ｗ，ｓ，ｔ，ｒを含むデータを署名σとして生成する署名生成ステップと、
前記検証装置が、前記公開鍵ｖｋを記録する検証記録ステップと、
前記検証装置が、
【数２９】
2013111673.tif 000046
の２つの式が成り立つかを確認し、両方の式が成り立つときは正しい署名であると判断し、いずれか一方でも成り立たないときは正しい署名でないと判断する検証ステップ
を有する署名検証方法。
【国際調査報告】
2013111673.tif 000047
2013111673.tif 000048
2013111673.tif 000049
2013111673.tif 000050