(57)【要約】【課題】署名長が短く、検証式の計算量がより少なく、高い安全性が証明可能な、群要素メッセージに対するデジタル署名方法を提供する。【解決手段】署名装置は、少なくとも署名記録部、署名確認部、署名乱数生成部、署名計算部、署名出力部を備える。検証装置は、検証入力部、検証確認部を備える。署名確認部は、ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）を確認する。署名乱数生成部は、１以上ｑ−１以下のランダムな整数ｒを生成する。署名計算部は、Ａ１＝ｇ１ｒ、Ａ２＝Ｍ１ｒｙ、Ｂ３＝ｇ２ｒｘＭ２ｒｘｙ、Ｂ４＝ｇ２ｒｙを計算する。署名出力部は、（Ａ１，Ａ２，Ｂ３，Ｂ４）を出力する。検証確認部は、Ａ１とＭ１とが群Ｇ１上の１以外の元であること、ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）、ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）、ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）、ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）を確認する。【選択図】図４
2011107319.tif 000002
【特許請求の範囲】
【請求項１】
Ｇ１、Ｇ２、ＧＴを位数ｑの群であってＧ１→Ｇ２の写像およびその逆写像が効率的には計算できない群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙとし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２，ｘ，ｙを記録する署名記録部と、
ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であることを確認する署名確認部と、
１以上ｑ−１以下のランダムな整数ｒを生成する署名乱数生成部と、
Ａ１＝ｇ１ｒ、
Ａ２＝Ｍ１ｒｙ、
Ｂ３＝ｇ２ｒｘＭ２ｒｘｙ、
Ｂ４＝ｇ２ｒｙ
を計算する署名計算部と、
（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する署名出力部と
を備える署名装置と、
メッセージｍと署名σとを受信する検証入力部と、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置と
を有する署名・検証システム。
【請求項２】
請求項１記載の署名・検証システムであって、
前記署名装置は、さらに
整数ｘと整数ｙを生成する鍵乱数生成部と、
Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙを計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部
も備える
ことを特徴とする署名・検証システム。
【請求項３】
Ｇ１、Ｇ２、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１とｈ１を群Ｇ１の任意の生成元、ｇ２とｈ２（ただし、ｈ２＝ｇ２α）を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙとし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２，α，ｘ，ｙを記録する署名記録部と、
ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であることを確認する署名確認部と、
１以上ｑ−１以下のランダムな整数ｒを生成する署名乱数生成部と、
Ａ１＝ｇ１ｒ、
Ａ２＝Ｍ１ｒｙ、
Ｂ３＝ｈ２ｒｘＭ２ｒｘｙ、
Ｂ４＝ｇ２ｒｙ
を計算する署名計算部と、
（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する署名出力部と
を備える署名装置と、
メッセージｍと署名σとを受信する検証入力部と、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置と
を有する署名・検証システム。
【請求項４】
請求項３記載の署名・検証システムであって、
前記署名装置は、さらに
整数ｘと整数ｙを生成する鍵乱数生成部と、
Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙを計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部
も備える
ことを特徴とする署名・検証システム。
【請求項５】
署名装置と検証装置とを含む署名・検証システムでの署名・検証方法であって、
Ｇ１、Ｇ２、ＧＴを位数ｑの群であってＧ１→Ｇ２の写像およびその逆写像が効率的には計算できない群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙとし、
前記署名装置において、
署名記録部に、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２をあらかじめ記録しておき、
鍵乱数生成部が、整数ｘと整数ｙを生成する鍵乱数生成ステップと、
鍵計算部が、Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙを計算する鍵計算ステップと、
鍵生成部が、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成ステップと、
署名確認部が、ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であることを確認する署名確認ステップと、
署名乱数生成部が、１以上ｑ−１以下のランダムな整数ｒを生成する署名乱数生成ステップと、
署名計算部が、
Ａ１＝ｇ１ｒ、
Ａ２＝Ｍ１ｒｙ、
Ｂ３＝ｇ２ｒｘＭ２ｒｘｙ、
Ｂ４＝ｇ２ｒｙ
を計算する署名計算ステップと、
署名出力部が、（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する署名出力ステップと
を有し、
前記検証装置において、
検証入力部が、メッセージｍと署名σとを受信する検証入力ステップと、
検証確認部が、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する検証確認ステップと、
検証出力部が、前記検証確認ステップがすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する検証出力ステップと
を有する署名・検証方法。
【請求項６】
署名装置と検証装置とを含む署名・検証システムでの署名・検証方法であって、
Ｇ１、Ｇ２、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１とｈ１を群Ｇ１の任意の生成元、ｇ２とｈ２（ただし、ｈ２＝ｇ２α）を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙとし、
前記署名装置において、
署名記録部に、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２をあらかじめ記録しておき、
鍵乱数生成部が、整数ｘと整数ｙを生成する鍵乱数生成ステップと、
鍵計算部が、Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙを計算する鍵計算ステップと、
鍵生成部が、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成ステップと、
署名確認部が、ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であることを確認する署名確認ステップと、
署名乱数生成部が、１以上ｑ−１以下のランダムな整数ｒを生成する署名乱数生成ステップと、
署名計算部が、
Ａ１＝ｇ１ｒ、
Ａ２＝Ｍ１ｒｙ、
Ｂ３＝ｈ２ｒｘＭ２ｒｘｙ、
Ｂ４＝ｇ２ｒｙ
を計算する署名計算ステップと、
署名出力部が、（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する署名出力ステップと
を有し、
前記検証装置において、
検証入力部が、メッセージｍと署名σとを受信する検証入力ステップと、
検証確認部が、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する検証確認ステップと、
検証出力部が、前記検証確認ステップがすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する検証出力ステップと
を有する署名・検証方法。
【請求項７】
Ｇ１、Ｇ２、ＧＴを位数ｑの群であってＧ１→Ｇ２の写像およびその逆写像が効率的には計算できない群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙとし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２，ｘ，ｙを記録する署名記録部と、
ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であることを確認する署名確認部と、
１以上ｑ−１以下のランダムな整数ｒを生成する署名乱数生成部と、
Ａ１＝ｇ１ｒ、
Ａ２＝Ｍ１ｒｙ、
Ｂ３＝ｇ２ｒｘＭ２ｒｘｙ、
Ｂ４＝ｇ２ｒｙ
を計算する署名計算部と、
（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する署名出力部と
を備える署名装置。
【請求項８】
請求項７記載の署名装置であって、
整数ｘと整数ｙを生成する鍵乱数生成部と、
Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙを計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部
も備えることを特徴とする署名装置。
【請求項９】
Ｇ１、Ｇ２、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１とｈ１を群Ｇ１の任意の生成元、ｇ２とｈ２（ただし、ｈ２＝ｇ２α）を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙとし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２，α，ｘ，ｙを記録する署名記録部と、
ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であることを確認する署名確認部と、
１以上ｑ−１以下のランダムな整数ｒを生成する署名乱数生成部と、
Ａ１＝ｇ１ｒ、
Ａ２＝Ｍ１ｒｙ、
Ｂ３＝ｈ２ｒｘＭ２ｒｘｙ、
Ｂ４＝ｇ２ｒｙ
を計算する署名計算部と、
（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する署名出力部と
を備える署名装置。
【請求項１０】
請求項９記載の署名装置であって、
整数ｘと整数ｙを生成する鍵乱数生成部と、
Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙを計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部
も備えることを特徴とする署名装置。
【請求項１１】
Ｇ１、Ｇ２、ＧＴを位数ｑの群であってＧ１→Ｇ２の写像およびその逆写像が効率的には計算できない群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙとし、
メッセージｍと署名σとを受信する検証入力部と、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置。
【請求項１２】
Ｇ１、Ｇ２、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１とｈ１を群Ｇ１の任意の生成元、ｇ２とｈ２（ただし、ｈ２＝ｇ２α）を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙとし、
メッセージｍと署名σとを受信する検証入力部と、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置。
【請求項１３】
請求項７から１０のいずれかに記載の署名装置、もしくは請求項１１または１２に記載の検証装置のいずれかの装置として、コンピュータを動作させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、主に電気通信を介したメッセージの授受の際に用いる署名・検証システム、署名・検証方法、署名装置、検証装置、プログラムに関する。
【背景技術】
【０００２】
デジタル署名はメッセージｍに対して、公開鍵ｐｋに対応する秘密鍵ｓｋを知る署名者が、メッセージｍに対して秘密鍵ｓｋを正しく使ったときにのみ計算できる値ｓを算出し、これを電子的な署名として用いるものである。正しく計算された署名は誰でも公開鍵ｐｋを用いてその正当性を検証でき、秘密鍵ｓｋを知らないいかなる第三者も正当な署名ｓを算出することはできない。
【０００３】
デジタル署名は、電子現金やクレデンシャルシステムなど様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより署名ｓを明かさないまま、あるメッセージｍに対する正しい署名ｓを保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がしばしば見受けられる。
【０００４】
近年のペアリング技術の進展によって、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能になった（非特許文献１）。これによって、署名ｓが効率的なペアリングを持つ群Ｇの要素である場合、即ちｓ∈Ｇである場合、前述のように署名ｓを明かさないまま、正しい署名ｓを保持しているという事実を証明することが可能である。例えば、非特許文献２に示されている、いわゆるCL-Signatureと呼ばれる方法では、メッセージｍ∈Ｚｑに対する署名ｓは３つの群要素（ａ，ｂ，ｃ）∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-signatureのように、ランダムオラクル等の（実現不可能と知られている）理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の署名方法では、メッセージｍが群Ｇの要素ではない。そのため、メッセージを秘匿した状態で、その秘匿したメッセージに対する正しい署名を保持していることを証明するという応用には供さない。メッセージが群Ｇの要素である場合にも安全な署名方法として、上記のCL-Signatureを改良した方式が非特許文献３に示されており、ランダムメッセージ攻撃に対して安全であることが示されているが、より強い選択メッセージ攻撃に対する安全性は不明である。
【０００６】
メッセージが群要素であって、選択メッセージ攻撃に強いことが証明されている方法として、非特許文献４に示された方法がある。この方法を以下に説明する。図１は署名・検証システムの構成例を示す図であり、図２は署名装置の処理フローを示す図、図３は検証装置の処理フローを示す図である。署名・検証システムは、ネットワーク８００に接続された署名装置７００と検証装置９００で構成される。
【０００７】
ｖ＝（ｑ，Ｇ，ＧＴ，ｅ，ｇ）を公開パラメータとする。ｑは大きな素数、Ｇ，ＧＴは位数ｑの群、ｅはＧ×Ｇ→ＧＴの効率的な計算が可能なペアリング、ｇを群Ｇの任意の生成元、Ｆ，Ｈ，Ｋ，Ｔを群Ｇの生成元とする。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たすものに限られているとする。
【０００８】
署名装置７００は、１以上ｑ−１以下のランダムな整数ｘを生成する（Ｓ７１０）。そして、Ｘ＝ｘｇ、Ｙ＝ｘＨを計算し（Ｓ７２０）、（ｖ，ｘｇ，ｘＨ）を公開鍵ｐｋとし、ｘを秘密鍵ｓｋとする（Ｓ７３０）。
【０００９】
署名装置７００は、１以上ｑ−１以下の乱数ｃ，ｒを生成し（Ｓ７５０）、
【００１０】
【数１】
2011107319.tif 000003
【００１１】
ａ２＝ｃｇ
ａ３＝ｃＦ
ａ４＝ｒｇ
ａ５＝ｒＨ
を計算する（Ｓ７６０）。そして、５つの組（ａ１，ａ２，ａ３，ａ４，ａ５）∈Ｇ５を署名σとする（Ｓ７７０）。
【００１２】
検証装置９００は、ネットワーク８００を介して署名σを受け取る（Ｓ９１０）。そして、メッセージ対（Ｍ，Ｎ）と署名σに対して、
ｅ（ａ１，Ｘ＋ａ２）＝ｅ（Ｋ＋Ｍ，ｇ）ｅ（Ｔ，ａ４）であること、
ｅ（ａ２，Ｆ）＝ｅ（ｇ，ａ３）であること、
ｅ（ａ４，Ｈ）＝ｅ（ｇ，ａ５）であること、
ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）であること、
ｅ（Ｘ，Ｈ）＝ｅ（ｇ，Ｙ）であること
を確認する（Ｓ９２０）。そして、すべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する（Ｓ９３０）。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Jens Groth and Amit Sahai, “Efficient Non-interactive Proof Systems for Bilinear Groups”, Eurocrypt 2008, LNCS 2965, pp.415-432.
【非特許文献２】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>.
【非特許文献４】Georg Fuchsbauer, “Automorphic Signatures in Bilinear Groups”, IACR e-print 200/320 ［平成２１年１０月２７日検索］、インターネット<URL: http://eprint.iacr.org/2009/320.pdf>.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来技術は署名・検証システムでは、署名が群Ｇの５つの要素からなり、また、検証においては５つのペアリングの等式を確認するため、効率が悪いという課題がある。
【００１５】
そこで、本発明では、署名長が短く、検証式の計算量がより少なく、高い安全性が証明可能な、群要素メッセージに対するデジタル署名方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の署名・検証システムは、署名装置と検証装置を含む。署名装置は、少なくとも署名記録部、署名確認部、署名乱数生成部、署名計算部、署名出力部を備える。署名装置は、さらに鍵乱数生成部、鍵計算部、鍵生成部も備えてもよい。検証装置は、検証入力部、検証確認部、検証出力部を備える。
【００１７】
本発明の第１の署名・検証システムでは、Ｇ１、Ｇ２、ＧＴを位数ｑの群であってＧ１→Ｇ２の写像およびその逆写像が効率的には計算できない群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙとする。鍵乱数生成部は、整数ｘと整数ｙを生成する。鍵計算部は、Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙを計算する。鍵生成部は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，ｘ，ｙ）を秘密鍵ｓｋとする。なお、Γ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２）とし、公開鍵ｐｋを（Γ，Ｘ２，Ｙ２）としてもよい。署名記録部は、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２，ｘ，ｙを記録する。署名確認部は、ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であることを確認する。署名乱数生成部は、１以上ｑ−１以下のランダムな整数ｒを生成する。署名計算部は、
Ａ１＝ｇ１ｒ、
Ａ２＝Ｍ１ｒｙ、
Ｂ３＝ｇ２ｒｘＭ２ｒｘｙ、
Ｂ４＝ｇ２ｒｙ
を計算する。署名出力部は、（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する。検証入力部は、メッセージｍと署名σとを受信する。検証確認部は、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する。検証出力部は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する。
【００１８】
本発明の第２の署名・検証システムでは、Ｇ１、Ｇ２、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１とｈ１を群Ｇ１の任意の生成元、ｇ２とｈ２（ただし、ｈ２＝ｇ２α）を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙとする。なお、この署名・検証システムでは群Ｇ１とＧ２とは同じ群であってもかまわない。
【００１９】
鍵乱数生成部は、整数ｘと整数ｙを生成する。鍵計算部は、Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙを計算する。鍵生成部は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする。なお、Γ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２）とし、公開鍵ｐｋを（Γ，Ｘ２，Ｙ２）としてもよい。署名記録部は、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２，α，ｘ，ｙを記録する。署名確認部は、ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であることを確認する。署名乱数生成部は、１以上ｑ−１以下のランダムな整数ｒを生成する。署名計算部は、
Ａ１＝ｇ１ｒ、
Ａ２＝Ｍ１ｒｙ、
Ｂ３＝ｈ２ｒｘＭ２ｒｘｙ、
Ｂ４＝ｇ２ｒｙ
を計算する。署名出力部は（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する。検証入力部は、メッセージｍと署名σとを受信する。検証確認部は、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する。検証出力部は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報を出力する。
【発明の効果】
【００２０】
本発明の署名・検証システムによれば、署名を４つの群要素で構成でき、検証装置で確認しなければならないペアリングの等式を４つにできる。また、署名によって確認しなければならない事項（各要素が偽造されていないかなど）を減らすことなく、署名の構成を変えることだけで署名長を短くしているので、安全性の劣化を生じない。したがって、署名長が短く、検証式の計算量がより少なく、高い安全性が証明可能な、群要素メッセージに対するデジタル署名方法を提供できる。
【図面の簡単な説明】
【００２１】
【図１】従来の署名・検証システムの構成例を示す図。
【図２】従来の署名装置の処理フローを示す図。
【図３】従来の検証装置の処理フローを示す図。
【図４】本発明の署名・検証システムの構成例を示す図。
【図５】本発明の署名装置の処理フローを示す図。
【図６】本発明の検証装置の処理フローを示す図。
【発明を実施するための形態】
【００２２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２３】
図４は実施例１の署名・検証システムの構成例を示す図、図５は署名装置の処理フローを示す図、図６は検証装置の処理フローを示す図である。署名・検証システムは、署名装置１００と検証装置２００を含む。この図では、署名装置１００と検証装置２００とはネットワーク８００によって接続されている。なお、署名装置１００が出力した署名σを検証装置２００に渡す方法は、ネットワークを用いる方法に限定する必要はない。例えば、記録媒体によって署名装置１００から検証装置２００に渡されてもよい。署名装置１００は、少なくとも署名記録部１９０、署名確認部１４０、署名乱数生成部１５０、署名計算部１６０、署名出力部１７０を備える。署名装置１００は、さらに鍵乱数生成部１１０、鍵計算部１２０、鍵生成部１３０も備えてもよい。鍵乱数生成部１１０、鍵計算部１２０、鍵生成部１３０を備えていない場合は、公開鍵ｐｋと対応する秘密鍵ｓｋを何らかの方法で鍵生成装置（鍵乱数生成部１１０、鍵計算部１２０、鍵生成部１３０を備える装置）から受け取り、署名記録部１９０に記録しておけばよい。なお、以下の説明では、鍵乱数生成部１１０、鍵計算部１２０、鍵生成部１３０を備えている場合について説明する。また、検証装置２００は、検証入力部２１０、検証確認部２２０、検証出力部２３０、検証記録部２９０を備える。実施例１では、Ｇ１、Ｇ２、ＧＴを位数ｑの群であってＧ１→Ｇ２の写像およびその逆写像が効率的には計算できない群、ｅをＧ１×Ｇ２→ＧＴのペアリング、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｇ２ｘ、Ｙ２＝ｇ２ｙとする。
【００２４】
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２）が公開情報Γとして公開されており、署名記録部１９０が、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録している。鍵乱数生成部１１０は、整数ｘと整数ｙを生成する（Ｓ１１０）。鍵計算部１２０は、
Ｘ２＝ｇ２ｘ
Ｙ２＝ｇ２ｙ
を計算する（Ｓ１２０）。鍵生成部１３０は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，ｘ，ｙ）を秘密鍵ｓｋとし、署名記録部１９０に記録する（Ｓ１３０）。なお、公開鍵ｐｋを（Γ，Ｘ２，Ｙ２）としてもよい。ここまでの処理で、署名記録部１９０は、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ｘ２，Ｙ２，ｘ，ｙを記録した状態となる。署名確認部１４０は、ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）の条件を満たすかを確認する。そして、この条件を満たさない場合は、エラーを出力し、処理を終了する。この条件を満たす場合は次の処理に進む（Ｓ１４０）。署名乱数生成部１５０は、１以上ｑ−１以下のランダムな整数ｒを生成する（Ｓ１５０）。署名計算部１６０は、
Ａ１＝ｇ１ｒ
Ａ２＝Ｍ１ｒｙ
Ｂ３＝ｇ２ｒｘＭ２ｒｘｙ
Ｂ４＝ｇ２ｒｙ
を計算する（Ｓ１６０）。署名出力部１７０は、（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する（Ｓ１７０）。検証入力部２１０は、メッセージｍと署名σとを受信する（Ｓ２１０）。検証確認部２２０は、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｇ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する（Ｓ２２０）。検証出力部２３０は、検証確認部２２０がすべての条件を満たすと確認した場合には署名が正しいことを示す情報（例えば、“１”）を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報（例えば、“０”）を出力する（Ｓ２３０）。
【００２５】
実施例１の署名・検証システムによれば、署名を４つの群要素で構成でき、検証装置で確認しなければならないペアリングの等式を４つにできる。また、署名によって確認しなければならない事項（各要素が偽造されていないかなど）を減らすことなく、署名の構成を変えることだけで署名長を短くしているので、安全性の劣化を生じない。したがって、署名長が短く、検証式の計算量がより少なく、高い安全性が証明可能な、群要素メッセージに対するデジタル署名方法を提供できる。
【実施例２】
【００２６】
実施例２の署名・検証システムは、構成要素の種類は実施例１と同じであり、各構成要素の処理が異なる。実施例２の署名・検証システムの構成例を図４、署名装置の処理フローを図５、検証装置の処理フローを図６に示す。実施例２の署名・検証システムは、署名装置３００と検証装置４００を含む。この図では、署名装置３００と検証装置４００とはネットワーク８００によって接続されているが、ネットワーク以外によって署名σを渡してもよい。署名装置３００は、少なくとも署名記録部３９０、署名確認部３４０、署名乱数生成部３５０、署名計算部３６０、署名出力部３７０を備える。署名装置３００は、さらに鍵乱数生成部３１０、鍵計算部３２０、鍵生成部３３０も備えてもよい。鍵乱数生成部３１０、鍵計算部３２０、鍵生成部３３０を備えていない場合は、公開鍵ｐｋと対応する秘密鍵ｓｋを何らかの方法で鍵生成装置（鍵乱数生成部３１０、鍵計算部３２０、鍵生成部３３０を備える装置）から受け取り、署名記録部３９０に記録しておけばよい。なお、以下の説明では、鍵乱数生成部３１０、鍵計算部３２０、鍵生成部３３０を備えている場合について説明する。また、検証装置４００は、検証入力部４１０、検証確認部４２０、検証出力部４３０、検証記録部４９０を備える。実施例２では、Ｇ１、Ｇ２、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１とｈ１を群Ｇ１の任意の生成元、ｇ２とｈ２（ただし、ｈ２＝ｇ２α）を群Ｇ２の任意の生成元、（Ｍ１，Ｍ２）を群Ｇ１上の１以外の元であるＭ１と群Ｇ２の元であるＭ２からなるメッセージｍ、ｘとｙを１以上ｑ−１以下の任意の整数、Ｘ２＝ｈ２ｘ、Ｙ２＝ｇ２ｙとする。なお、この署名・検証システムでは群Ｇ１とＧ２とは同じ群であってもかまわない。
【００２７】
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２）が公開情報Γとして公開されており、署名記録部３９０が、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２を記録している。鍵乱数生成部３１０は、整数ｘと整数ｙを生成する（Ｓ３１０）。鍵計算部３２０は、
Ｘ２＝ｈ２ｘ
Ｙ２＝ｇ２ｙ
を計算する（Ｓ３２０）。鍵生成部３３０は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする。なお、公開鍵ｐｋを（Γ，Ｘ２，Ｙ２）としてもよい。ここまでの処理で、署名記録部３９０は、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｈ１，ｇ２，ｈ２，Ｘ２，Ｙ２，α，ｘ，ｙを記録した状態となる。署名確認部３４０は、ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）の条件を満たすかを確認する。そして、この条件を満たさない場合は、エラーを出力し、処理を終了する。この条件を満たす場合は次の処理に進む（Ｓ３４０）。署名乱数生成部３５０は、１以上ｑ−１以下のランダムな整数ｒを生成する（Ｓ３５０）。署名計算部３６０は、
Ａ１＝ｇ１ｒ
Ａ２＝Ｍ１ｒｙ
Ｂ３＝ｈ２ｒｘＭ２ｒｘｙ
Ｂ４＝ｇ２ｒｙ
を計算する（Ｓ３６０）。署名出力部３７０は（Ａ１，Ａ２，Ｂ３，Ｂ４）を署名σとして出力する（Ｓ３７０）。検証入力部４１０は、メッセージｍと署名σとを受信する（Ｓ４１０）。検証確認部４２０は、
Ａ１とＭ１とが群Ｇ１上の１以外の元であること、
ｅ（Ｍ１，ｈ２）＝ｅ（ｇ１，Ｍ２）であること、
ｅ（Ａ１，Ｙ２）＝ｅ（ｇ１，Ｂ４）であること、
ｅ（Ａ２，ｇ２）＝ｅ（Ｍ１，Ｂ４）であること、
ｅ（ｇ１，Ｂ３）＝ｅ（Ａ１Ａ２，Ｘ２）であること
を確認する（Ｓ４２０）。検証出力部４３０は、検証確認部４２０がすべての条件を満たすと確認した場合には署名が正しいことを示す情報（例えば、“１”）を出力し、いずれかの条件を満たさないと確認した場合に書名が正しくないことを示す情報（例えば、“０”）を出力する（Ｓ４３０）。
【００２８】
実施例２の署名・検証システムでも、署名を４つの群要素で構成でき、検証装置で確認しなければならないペアリングの等式を４つにできる。また、署名によって確認しなければならない事項（各要素が偽造されていないかなど）を減らすことなく、署名の構成を変えることだけで署名長を短くしているので、安全性の劣化を生じない。したがって、署名長が短く、検証式の計算量がより少なく、高い安全性が証明可能な、群要素メッセージに対するデジタル署名方法を提供できる。
【００２９】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００３０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００３１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００３２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００３３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００３４】
本発明は、電子データの正当性を証明するために利用することができる。
【符号の説明】
【００３５】
１００、３００、７００  署名装置        １１０、３１０  鍵乱数生成部
１２０、３２０  鍵計算部                １３０、３３０  鍵生成部
１４０、３４０  署名確認部              １５０、３５０  署名乱数生成部
１６０、３６０  署名計算部              １７０、３７０  署名出力部
１９０、３９０  署名記録部              ２００、４００、９００  検証装置
２１０、４１０  検証入力部              ２２０、４２０  検証確認部
２３０、４３０  検証出力部              ２９０、４９０  検証記録部
８００  ネットワーク
【図１】
2011107319.tif 000004
【図２】
2011107319.tif 000005
【図３】
2011107319.tif 000006
【図４】
2011107319.tif 000007
【図５】
2011107319.tif 000008
【図６】
2011107319.tif 000009