(57)【特許請求の範囲】
【請求項１】
Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ４は０と１からなるビット列をＬ（ただしＬは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ５は０と１からなるビット列をＭ（ただしＭは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数であり、
値ｋをＺｑからランダムに生成する乱数生成部と、
上記生成元ｇと上記秘密鍵ｘと上記値ｋとが入力され、値ｕをｕ＝ｇk∈Ｇにより計算し、値ｈをｈ＝Ｈ１(ｕ)により計算し、値ｚをｚ＝ｈｘ∈Ｇにより計算し、値ｖをｖ＝ｈｋ∈Ｇにより計算し、計算したそれぞれの値を出力する第１生成計算部と、
０と１からなる任意のビット長|ｍ|のメッセージｍが入力され、Ｍビット長のリカバリメッセージｍrecと、|ｍ|−Ｍビット長のクリアメッセージｍclrとに分割して出力する入力部と、
上記公開鍵ｙと上記生成元ｇと上記クリアメッセージｍclrと上記値ｚと上記値ｈと上記値ｕと上記値ｖとが入力され、鍵ｗをｗ＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ，ｕ，ｖ)により計算し出力する第３生成計算部と、
上記鍵ｗと上記リカバリメッセージｍrecとが入力され、値ｈ１をｈ１＝Ｈ４(ｗ，ｍrec)により計算し、値ｈ２を
【数１】
0004914377.tif 000006
により計算し、値ｒをｒ＝ｈ１|ｈ２により求めて出力する第４生成計算部と、
上記秘密鍵ｘと上記公開鍵ｙと上記生成元ｇと上記値ｋと上記クリアメッセージｍclrと上記値ｚと上記値ｒとが入力され、値ｃをｃ＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｓをｓ＝ｋ＋ｃ・ｘ∈Ｚｑにより計算し、上記値ｚと上記値ｓと上記値ｒとを署名σとして出力するとともに、上記クリアメッセージｍclrを出力する第２生成計算部と、
を備えることを特徴とする署名生成装置。
【請求項２】
Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、ＥｗはＫビット長の鍵ｗによりＬ＋Ｍ（ただしＬとＭは正の整数）ビット長の０と１からなるビット列を同じ長さの０と１からなるビット列に暗号化する共通鍵暗号の暗号化関数、０ＬはＬビット長のすべてが０からなるビット列であり、
値ｋをＺｑからランダムに生成する乱数生成部と、
上記生成元ｇと上記秘密鍵ｘと上記値ｋとが入力され、値ｕをｕ＝ｇk∈Ｇにより計算し、値ｈをｈ＝Ｈ１(ｕ)により計算し、値ｚをｚ＝ｈｘ∈Ｇにより計算し、値ｖをｖ＝ｈｋ∈Ｇにより計算し、計算したそれぞれの値を出力する第１生成計算部と、
０と１からなる任意のビット長|ｍ|のメッセージｍが入力され、Ｍビット長のリカバリメッセージｍrecと、|ｍ|−Ｍビット長のクリアメッセージｍclrとに分割して出力する入力部と、
上記公開鍵ｙと上記生成元ｇと上記クリアメッセージｍclrと上記値ｕと上記値ｈと上記値ｚと上記値ｖとが入力され、上記鍵ｗをｗ＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ、ｕ，ｖ)により計算し出力する第３生成計算部と、
上記鍵ｗと上記リカバリメッセージｍrecとが入力され、値ｄを０Ｌ|ｍrecにより求め、値ｒをｒ＝Ｅｗ(ｄ)により計算して出力する第４生成計算部と、
上記秘密鍵ｘと上記公開鍵ｙと上記生成元ｇと上記値ｋと上記クリアメッセージｍclrと上記値ｚと上記値ｒとが入力され、値ｃをｃ＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｓをｓ＝ｋ＋ｃ・ｘ∈Ｚｑにより計算し、上記値ｚと上記値ｓと上記値ｒとを署名σとして出力するとともに、上記クリアメッセージｍclrを出力する第２生成計算部と、
を備えることを特徴とする署名生成装置。
【請求項３】
Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ４は０と１からなるビット列をＬ（ただしＬは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ５は０と１からなるビット列をＭ（ただしＭは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数であり、
値ｚ∈Ｇと値ｓ∈ＺｑとＬ＋Ｍビット長の０と１からなるビット列である値ｒとからなる署名σ、公開鍵ｙ、生成元ｇ、及び|ｍ|−Ｍ（ただし|ｍ|−Ｍは正の整数）ビット長のクリアメッセージｍclrが入力され、値ｃ'をｃ'＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｕ'をｕ'＝ｇｓ・ｙ−ｃ'∈Ｇにより計算し、値ｈ'をｈ'＝Ｈ１(ｕ')により計算し、値ｖ'をｖ'＝ｈ'ｓ・ｚ−ｃ'∈Ｇにより計算し、値ｕ’、値ｈ’、及び値ｖ’を出力する第１検証計算部と、
上記クリアメッセージｍclrと上記生成元ｇと上記公開鍵ｙと上記値ｚと上記値ｈ'と上記値ｕ'と上記値ｖ'とが入力され、鍵ｗ'をｗ'＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ'，ｕ'，ｖ')により計算して出力する第２検証計算部と、
上記値ｒと上記鍵ｗ’とが入力され、上記値ｒをＬビット長の値ｈ１'とＭビット長の値ｈ２'とに分割し、リカバリメッセージｍrec'を
【数２】
0004914377.tif 000007
により計算し、値ａをａ＝Ｈ４(ｗ'，ｍrec')により計算し、上記値ｈ１'と上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとを出力する第３検証計算部と、
上記値ｈ１'と上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとが入力され、ａとｈ１'とが等しい場合はメッセージｍをｍ＝ｍrec' |ｍclrにより求めてaccept 1とともに出力し、ａとｈ１'とが等しくない場合はreject 0を出力する出力部と、
を備えることを特徴とする署名検証装置。
【請求項４】
Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｄｗ'はＫビット長の鍵ｗ'によりＬ＋Ｍ（ただしＬとＭは正の整数）ビット長の０と１からなる暗号化されたビット列を同じ長さの０と１からなるビット列に復号化する共通鍵暗号の復号化関数、０ＬはＬビット長のすべてが０からなるビット列であり、
値ｚ∈Ｇと値ｓ∈ＺｑとＬ＋Ｍビット長の０と１からなるビット列である値ｒとからなる署名σ、公開鍵ｙ、生成元ｇ、及び|ｍ|−Ｍ（ただし|ｍ|−Ｍは正の整数）ビット長のクリアメッセージｍclrが入力され、値ｃ'をｃ'＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｕ'をｕ'＝ｇｓ・ｙ−ｃ'∈Ｇにより計算し、値ｈをｈ'＝Ｈ１(ｕ')により計算し、値ｖ'をｖ'＝ｈ'ｓ・ｚ−ｃ'∈Ｇにより計算し、値ｕ’、値ｈ’、及び値ｖ’を出力する第１検証計算部と、
上記クリアメッセージｍclrと上記生成元ｇと上記公開鍵ｙと上記値ｚと上記値ｈ'と上記値ｕ'と上記値ｖ'とが入力され、上記鍵ｗ'をｗ'＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ'，ｕ'，ｖ')により計算して出力する第２検証計算部と、
上記値ｒと上記鍵ｗ’とが入力され、値ｄ'をｄ'＝Ｄｗ' (ｒ)により計算し、当該値ｄ'をＬビット長の値ａとＭビット長のリカバリメッセージｍrec'とに分割し、上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとを出力する第３検証計算部と、
上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとが入力され、ａと０Ｌとが等しい場合はメッセージｍをｍ＝ｍrec'|ｍclrにより求めてaccept 1とともに出力し、ａと０Ｌとが等しくない場合はreject 0を出力する出力部と、
を備えることを特徴とする署名検証装置。
【請求項５】
請求項１の署名生成装置と請求項３の署名検証装置とを備える署名生成検証システム。
【請求項６】
請求項２の署名生成装置と請求項４の署名検証装置とを備える署名生成検証システム。
【請求項７】
Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ４は０と１からなるビット列をＬ（ただしＬは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ５は０と１からなるビット列をＭ（ただしＭは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数であり、
乱数生成部が、値ｋをＺｑからランダムに生成する乱数生成ステップと、
第１生成計算部が、上記生成元ｇと上記秘密鍵ｘと上記値ｋとから、値ｕをｕ＝ｇk∈Ｇにより計算し、値ｈをｈ＝Ｈ１(ｕ)により計算し、値ｚをｚ＝ｈｘ∈Ｇにより計算し、値ｖをｖ＝ｈｋ∈Ｇにより計算し、計算したそれぞれの値を出力する第１生成計算ステップと、
入力部が、０と１からなる任意のビット長|ｍ|のメッセージｍを、Ｍビット長のリカバリメッセージｍrecと、|ｍ|−Ｍビット長のクリアメッセージｍclrとに分割して出力する入力ステップと、
第３生成計算部が、上記公開鍵ｙと上記生成元ｇと上記クリアメッセージｍclrと上記値ｚと上記値ｈと上記値ｕと上記値ｖとから、鍵ｗをｗ＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ，ｕ，ｖ)により計算し出力する第３生成計算ステップと、
第４生成計算部が、上記鍵ｗと上記リカバリメッセージｍrecとから、値ｈ１をｈ１＝Ｈ４(ｗ，ｍrec)により計算し、値ｈ２を
【数３】
0004914377.tif 000008
により計算し、値ｒをｒ＝ｈ１|ｈ２により求めて出力する第４生成計算ステップと、
第２生成計算部が、上記秘密鍵ｘと上記公開鍵ｙと上記生成元ｇと上記値ｋと上記クリアメッセージｍclrと上記値ｚと上記値ｒとから、値ｃをｃ＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｓをｓ＝ｋ＋ｃ・ｘ∈Ｚｑにより計算し、上記値ｚと上記値ｓと上記値ｒとを署名σとして出力するとともに、上記クリアメッセージｍclrを出力する第２生成計算ステップと、
を実行することを特徴とする署名生成方法。
【請求項８】
Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、ＥｗはＫビット長の鍵ｗによりＬ＋Ｍ（ただしＬとＭは正の整数）ビット長の０と１からなるビット列を同じ長さの０と１からなるビット列に暗号化する共通鍵暗号の暗号化関数、０ＬはＬビット長のすべてが０からなるビット列であり、
乱数生成部が、値ｋをＺｑからランダムに生成する乱数生成ステップと、
第１生成計算部が、上記生成元ｇと上記秘密鍵ｘと上記値ｋとから、値ｕをｕ＝ｇk∈Ｇにより計算し、値ｈをｈ＝Ｈ１(ｕ)により計算し、値ｚをｚ＝ｈｘ∈Ｇにより計算し、値ｖをｖ＝ｈｋ∈Ｇにより計算し、計算したそれぞれの値を出力する第１生成計算ステップと、
入力部が、０と１からなる任意のビット長|ｍ|のメッセージｍを、Ｍビット長のリカバリメッセージｍrecと、|ｍ|−Ｍビット長のクリアメッセージｍclrとに分割して出力する入力ステップと、
第３生成計算部が、上記公開鍵ｙと上記生成元ｇと上記クリアメッセージｍclrと上記値ｕと上記値ｈと上記値ｚと上記値ｖとから、上記鍵ｗをｗ＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ、ｕ，ｖ)により計算し出力する第３生成計算ステップと、
第４生成計算部が、上記鍵ｗと上記リカバリメッセージｍrecとから、値ｄを０Ｌ|ｍrecにより求め、値ｒをｒ＝Ｅｗ(ｄ)により計算して出力する第４生成計算ステップと、
第２生成計算部が、上記秘密鍵ｘと上記公開鍵ｙと上記生成元ｇと上記値ｋと上記クリアメッセージｍclrと上記値ｚと上記値ｒとから、値ｃをｃ＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｓをｓ＝ｋ＋ｃ・ｘ∈Ｚｑにより計算し、上記値ｚと上記値ｓと上記値ｒとを署名σとして出力するとともに、上記クリアメッセージｍclrを出力する第２生成計算ステップと、
を実行することを特徴とする署名生成方法。
【請求項９】
Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ４は０と１からなるビット列をＬ（ただしＬは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ５は０と１からなるビット列をＭ（ただしＭは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数であり、
第１検証計算部が、値ｚ∈Ｇと値ｓ∈ＺｑとＬ＋Ｍビット長の０と１からなるビット列である値ｒとからなる署名σ、公開鍵ｙ、生成元ｇ、及び|ｍ|−Ｍ（ただし|ｍ|−Ｍは正の整数）ビット長のクリアメッセージｍclrから、値ｃ'をｃ'＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｕ'をｕ'＝ｇｓ・ｙ−ｃ'∈Ｇにより計算し、値ｈ'をｈ'＝Ｈ１(ｕ')により計算し、値ｖ'をｖ'＝ｈ'ｓ・ｚ−ｃ'∈Ｇにより計算し、値ｕ’、値ｈ’、及び値ｖ’を出力する第１検証計算ステップと、
第２検証計算部が、上記クリアメッセージｍclrと上記生成元ｇと上記公開鍵ｙと上記値ｚと上記値ｈ'と上記値ｕ'と上記値ｖ'とから、鍵ｗ'をｗ'＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ'，ｕ'，ｖ')により計算して出力する第２検証計算ステップと、
第３検証計算部が、上記値ｒと上記鍵ｗ’とから、上記値ｒをＬビット長の値ｈ１'とＭビット長の値ｈ２'とに分割し、リカバリメッセージｍrec'を
【数４】
0004914377.tif 000009
により計算し、値ａをａ＝Ｈ４(ｗ'，ｍrec')により計算し、上記値ｈ１'と上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとを出力する第３検証計算ステップと、
出力部が、ａとｈ１'とが等しい場合はメッセージｍをｍ＝ｍrec'|ｍclrにより求めてaccept 1とともに出力し、ａとｈ１'とが等しくない場合はreject 0を出力する出力ステップと、
を実行することを特徴とする署名検証方法。
【請求項１０】
Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｄｗ'はＫビット長の鍵ｗ'によりＬ＋Ｍ（ただしＬとＭは正の整数）ビット長の０と１からなる暗号化されたビット列を同じ長さの０と１からなるビット列に復号化する共通鍵暗号の復号化関数、０ＬはＬビット長のすべてが０からなるビット列であり、
第１検証計算部が、値ｚ∈Ｇと値ｓ∈ＺｑとＬ＋Ｍビット長の０と１からなるビット列である値ｒとからなる署名σ、公開鍵ｙ、生成元ｇ、及び|ｍ|−Ｍ（ただし|ｍ|−Ｍは正の整数）ビット長のクリアメッセージｍclrから、値ｃ'をｃ'＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｕ'をｕ'＝ｇｓ・ｙ−ｃ'∈Ｇにより計算し、値ｈをｈ'＝Ｈ１(ｕ')により計算し、値ｖ'をｖ'＝ｈ'ｓ・ｚ−ｃ'∈Ｇにより計算し、値ｕ’、値ｈ’、及び値ｖ’を出力する第１検証計算ステップと、
第２検証計算部が、上記クリアメッセージｍclrと上記生成元ｇと上記公開鍵ｙと上記値ｚと上記値ｈ'と上記値ｕ'と上記値ｖ'とから、上記鍵ｗ'をｗ'＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ'，ｕ'，ｖ')により計算して出力する第２検証計算ステップと、
第３検証計算部が、上記値ｒと上記鍵ｗ’とから、値ｄ'をｄ'＝Ｄｗ' (ｒ)により計算し、当該値ｄ'をＬビット長の値ａとＭビット長のリカバリメッセージｍrec'とに分割し、上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとを出力する第３検証計算ステップと、
出力部が、ａと０Ｌとが等しい場合はメッセージｍをｍ＝ｍrec'|ｍclrにより求めてaccept 1とともに出力し、ａと０Ｌとが等しくない場合はreject 0を出力する出力ステップと、
を実行することを特徴とする署名検証方法。
【請求項１１】
請求項１〜６のいずれかに記載した装置又はシステムとしてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、詳しくは、署名からメッセージを復元するメッセージ復元署名技術において、より安全性を高めるための、署名生成装置、署名検証装置、署名生成検証システム、それらの方法及びプログラムに関する。
【背景技術】
【０００２】
メッセージ復元型の署名方式は、署名と復元できないメッセージの部分とをそれぞれ受信者に送信し、それらを用いてメッセージを復元する方式であり、例えば非特許文献１にはハッシュ関数によるリカバリパディング技術を用いた方式が、また非特許文献２には共通鍵関数によるリカバリパディング技術を用いた方式がそれぞれ開示されている。これらの文献で開示された方式は、ランダムオラクルモデル、イデアルサイファモデルで離散対数問題仮定に基づき安全性が証明されるという利点がある。
【０００３】
一方、署名添付型の署名方式は、署名とメッセージ全部とをそれぞれ受信者に送信する方式であり、例えば非特許文献３において開示されている。非特許文献３で開示されている方式は、Computational Diffie-Hellman問題仮定にタイトに帰着するため、特に安全性に優れている。以下、非特許文献３で開示されている署名方式について説明する。当該署名方式は、位数ｑ（ただしｑは素数）の巡回群Ｇ上の離散対数問題を利用したものである。
【０００４】
[鍵生成]
巡回群Ｇの生成元をｇとし、秘密鍵ｘをｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成するとともに、公開鍵ｙをｙ＝ｇｘ∈Ｇにより生成する。
【０００５】
[署名生成]
図９に署名生成装置１０の機能構成を、図１０にその処理フローを示す。署名生成装置１０は、乱数生成部１１と第１生成計算部１２と入力部１３と第２生成計算部１４とを備える。なお、以下の計算において、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数である。
【０００６】
乱数生成部１１は、値ｋをＺｑからランダムに生成し出力する（Ｓ１）。第１生成計算部１２は、上記生成元ｇと上記秘密鍵ｘと上記値ｋとが入力され、値ｕをｕ＝ｇk∈Ｇにより計算し、値ｈをｈ＝Ｈ１(ｕ)により計算し、値ｚをｚ＝ｈｘ∈Ｇにより計算し、値ｖをｖ＝ｈｋ∈Ｇにより計算し、計算したそれぞれの値を出力する（Ｓ２）。入力部１３は、０と１からなる任意のビット長|ｍ|のメッセージｍを装置に取り込む（Ｓ３）。なお、Ｓ３についてはＳ１〜Ｓ２との処理の前後関係は問わない。第２生成計算部１４は、上記秘密鍵ｘと上記公開鍵ｙと上記生成元ｇと上記値ｋと上記メッセージｍと上記値ｚと上記値ｈと上記値ｕと上記値ｖとが入力され、値ｃをｃ＝Ｈ２(ｍ，ｇ，ｙ，ｚ，ｈ，ｕ，ｖ)により計算し、値ｓをｓ＝ｋ＋ｃ・ｘ∈Ｚｑにより計算し、上記値ｚと上記値ｓと上記値ｃとを署名σとして出力するとともに、上記メッセージｍを出力する（Ｓ４）。なお、上記Ｈ２(ｍ，ｇ，ｙ，ｚ，ｈ，ｕ，ｖ)は、ｍ，ｇ，ｙ，ｚ，ｈ，ｕ，ｖのビット結合値に対しハッシュ関数Ｈ２によりハッシュ関数計算を行うことを意味し、以下のハッシュ関数に係る表記も同様な意味である。
【０００７】
[署名検証]
図１１に署名検証装置４０の機能構成を、図１２にその処理フローを示す。署名検証装置４０は、第１検証計算部４１と第２検証計算部４２と出力部４４とを備える。第１検証計算部４１は、上記値ｚと上記値ｓと上記値ｃとからなる上記署名σ、上記公開鍵ｙ、上記生成元ｇ、及び上記メッセージｍが入力され、値ｕ'をｕ'＝ｇｓ・ｙ−ｃ∈Ｇにより計算し、値ｈ'をｈ'＝Ｈ１(ｕ')により計算し、値ｖ'をｖ'＝ｈ'ｓ・ｚ−ｃ∈Ｇにより計算し、計算したそれぞれの値を出力する（Ｓ２１）。第２検証計算部４２は、上記メッセージｍ、上記生成元ｎｇ、上記公開鍵ｙ、上記値ｚ、上記値ｈ'、上記値ｕ'、及び上記値ｖ'が入力され、値ａをａ＝Ｈ２(ｍ，ｇ，ｙ，ｚ，ｈ'，ｕ'，ｖ')により計算し出力する（Ｓ２２）。出力部４４は、上記値ａと上記値ｃとが入力され、ａとｃとが等しい場合は検証成功を意味するaccept 1を出力し、等しくない場合は検証失敗を意味するreject 0を出力する（Ｓ２３）。
【非特許文献１】Masayuki Abe and Tatsuaki Okamoto、"A Signature Scheme with Message Recovery as Secure as Discrete Logarithm"、ASIACRYPT'99、1999、p378-389
【非特許文献２】Leon A. Pintsov and Scott A.Vanstone、"Postal Revenue Collection in the Digital Age"、Financial Cryptography 2000、2000、p105-120
【非特許文献３】Benoit Chevallier-Mames、"An Efficient CDH-Based Signature Scheme with a Tight Security Reduction"、CRYPTO 2005、2005、p511-526
【発明の開示】
【発明が解決しようとする課題】
【０００８】
メッセージ復元型の署名方式に係る非特許文献１、２で開示された技術は、離散対数問題仮定に基づき安全性が証明されるものの、離散対数問題にタイトに帰着せず、帰着効率が攻撃者がハッシュ関数オラクルに聞く回数に反比例してしまうため、安全性確保のためには鍵長を長くする必要があり、効率が良くなかった。
【０００９】
本発明の目的は、メッセージ復元型の署名方式において、Computational Diffie-Hellman問題仮定などの数学的に困難と広く信じられている問題に、安全性証明上タイトに帰着可能な、署名生成・検証装置、システム及び方法の実現にある。
【課題を解決するための手段】
【００１０】
本発明の署名生成装置は、乱数生成部、第１生成計算部、入力部、第３生成計算部、第４生成計算部、及び第２生成計算部を備える。なお、Ｇは位数ｑ（ただしｑは素数）の離散対数問題が困難な巡回群、ｇはＧの生成元、ｘはｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成された秘密鍵、ｙはｙ＝ｇｘ∈Ｇにより生成された公開鍵、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ４は０と１からなるビット列をＬ（ただしＬは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ５は０と１からなるビット列をＭ（ただしＭは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数である。
【００１１】
乱数生成部は、値ｋをＺｑからランダムに生成する。第１生成計算部は、上記生成元ｇと上記秘密鍵ｘと上記値ｋとが入力され、値ｕをｕ＝ｇk∈Ｇにより計算し、値ｈをｈ＝Ｈ１(ｕ)により計算し、値ｚをｚ＝ｈｘ∈Ｇにより計算し、値ｖをｖ＝ｈｋ∈Ｇにより計算し、計算したそれぞれの値を出力する。入力部は、０と１からなる任意のビット長|ｍ|のメッセージｍが入力され、Ｍビット長のリカバリメッセージｍrecと、|ｍ|−Ｍビット長のクリアメッセージｍclrとに分割して出力する。第３生成計算部は、上記公開鍵ｙと上記生成元ｇと上記クリアメッセージｍclrと上記値ｚと上記値ｈと上記値ｕと上記値ｖとが入力され、鍵ｗをｗ＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ，ｕ，ｖ)により計算し出力する。第４生成計算部は、上記鍵ｗと上記リカバリメッセージｍrecとが入力され、値ｈ１をｈ１＝Ｈ４(ｗ，ｍrec)により計算し、値ｈ２を
【数５】
0004914377.tif 000002
により計算し、値ｒをｒ＝ｈ１|ｈ２により求めて出力する。第２生成計算部は、上記秘密鍵ｘと上記公開鍵ｙと上記生成元ｇと上記値ｋと上記クリアメッセージｍclrと上記値ｚと上記値ｒとが入力され、値ｃをｃ＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｓをｓ＝ｋ＋ｃ・ｘ∈Ｚｑにより計算し、上記値ｚと上記値ｓと上記値ｒとを署名σとして出力するとともに、上記クリアメッセージｍclrを出力する。
【００１２】
また、本発明の署名検証装置は、第１検証計算部、第２検証計算部、第３検証計算部、及び出力部を備える。第１検証計算部は、値ｚと値ｓと値ｒとからなる署名σ、公開鍵ｙ、生成元ｇ、及びクリアメッセージｍclrが入力され、値ｃ'をｃ'＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｕ'をｕ'＝ｇｓ・ｙ−ｃ'∈Ｇにより計算し、値ｈをｈ'＝Ｈ１(ｕ')により計算し、値ｖ'をｖ'＝ｈ'ｓ・ｚ−ｃ'∈Ｇにより計算し、値ｕ’、値ｈ’、及び値ｖ’を出力する。第２検証計算部は、上記クリアメッセージｍclrと上記生成元ｇと上記公開鍵ｙと上記値ｚと上記値ｈ'と上記値ｕ'と上記値ｖ'とが入力され、上記鍵ｗ'をｗ'＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ'，ｕ'，ｖ')により計算して出力する。第３検証計算部は、上記値ｒと上記鍵ｗ’とが入力され、上記値ｒをＬビット長の値ｈ１'とＭビット長の値ｈ２'とに分割し、リカバリメッセージｍrec'を
【数６】
0004914377.tif 000003
により計算し、値ａをａ＝Ｈ４(ｗ'，ｍrec')により計算し、上記値ｈ１'と上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとを出力する。出力部は、上記値ｈ１'と上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとが入力され、ａとｈ１'とが等しい場合はメッセージｍをｍ＝ｍrec' |ｍclrにより求めてaccept 1とともに出力し、ａとｈ１'とが等しくない場合はreject 0を出力する。
【発明の効果】
【００１３】
本発明の署名生成・検証装置、システム及び方法によれば、安全性証明においてComputational Diffie-Hellman問題仮定にタイトに帰着するため、帰着効率が攻撃者がハッシュ関数オラクルに聞く回数に反比例せず、よって同じ安全性で鍵長が短いメッセージ復元署名を構成することができる。また、方式の中で用いるハッシュ関数の出力長や共通鍵暗号化関数の入出力長を変化させることで、リカバリメッセージの長さを変化させることができる。
【発明を実施するための最良の形態】
【００１４】
本発明では、上記背景技術において説明したComputational Diffie-Hellman問題仮定にタイトに帰着可能な非特許文献３の署名添付型の署名方式に、非特許文献１及び２のメッセージ復元型の署名方式で用いられているメッセージリカバリパディング技術を適用することにより、Computational Diffie-Hellman問題仮定にタイトに帰着可能なメッセージ復元型の署名方式を実現する。
【００１５】
〔第１実施形態〕
本実施形態は、非特許文献３の署名方式に非特許文献１のハッシュ関数によるメッセージリカバリパディング技術を適用した形態である。
【００１６】
本発明の署名方式は、位数ｑ（ただしｑは素数）の巡回群Ｇ上の離散対数問題を利用したものであり、Ｇとしては例えば、有限体の乗法群や楕円曲線上の有理点のなす加法群などを用いることができる。なお、本明細書においては便宜上、群演算を乗法で表記しているが（例えばｙの場合はｙ＝ｇｘ∈Ｇ）、この表記はＧが乗法群の場合の乗法演算だけでなく、Ｇが加法群の場合の加法演算（例えばｙの場合はｙ＝ｘ・ｇ∈Ｇ）も含む趣旨である。
【００１７】
また、背景技術において既に説明した構成部や処理ステップと共通している部分については同じ符号を付し、説明は省略する。
【００１８】
[鍵生成]
巡回群Ｇの生成元をｇとし、秘密鍵ｘをｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成するとともに、公開鍵ｙをｙ＝ｇｘ∈Ｇにより生成する。
[署名生成]
図１に署名生成装置２０の機能構成例を、図２にその処理フロー例を示す。署名生成装置２０は、乱数生成部１１と第１生成計算部１２と入力部２３と第３生成計算部２５と第４生成計算部２６と第２生成計算部２４とを備える。乱数生成部１１と第１生成計算部１２は、背景技術の署名生成装置１０で使用されているものと共通である。なお、以下の計算において、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ４は０と１からなるビット列をＬ（ただしＬは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、Ｈ５は０と１からなるビット列をＭ（ただしＭは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数である。これらのハッシュ関数の入力には、クリアメッセージｍclrを入れることも、公開鍵ｙを入れることも、群Ｇを特定するパラメータを入れることも可能である。
【００１９】
入力部２３は、０と１からなる任意のビット長|ｍ|のメッセージｍが入力され、Ｍビット長のリカバリメッセージｍrecと、|ｍ|−Ｍビット長のクリアメッセージｍclrとに分割してそれぞれを出力する（Ｓ５）。第３生成計算部２５は、上記公開鍵ｙと上記生成元ｇと上記クリアメッセージｍclrと上記値ｚと上記値ｈと上記値ｕと上記値ｖとが入力され、鍵ｗをｗ＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ，ｕ，ｖ)により計算し出力する（Ｓ６）。第４生成計算部２６は、上記鍵ｗと上記リカバリメッセージｍrecとが入力され、値ｈ１をｈ１＝Ｈ４(ｗ，ｍrec)により計算し、値ｈ２を
【数７】
0004914377.tif 000004
により計算し、値ｒをｒ＝ｈ１|ｈ２により求めて出力する（Ｓ７）。第２生成計算部２４は、上記秘密鍵ｘと上記公開鍵ｙと上記生成元ｇと上記値ｋと上記クリアメッセージｍclrと上記値ｚと上記値ｒとが入力され、値ｃをｃ＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｓをｓ＝ｋ＋ｃ・ｘ∈Ｚｑにより計算し、上記値ｚと上記値ｓと上記値ｒとを署名σとして出力するとともに、上記クリアメッセージｍclrを出力する（Ｓ８）。
【００２０】
[署名検証]
図３に署名検証装置５０の機能構成例を、図４にその処理フロー例を示す。署名生成装置５０は、基本的に署名生成装置２０と対向して使用され、第１検証計算部５１と第２検証計算部５２と第３検証計算部５３と出力部５４とを備える。
【００２１】
第１検証計算部５１は、値ｚ∈Ｇと値ｓ∈ＺｑとＬ＋Ｍビット長の０と１からなるビット列である値ｒとからなる署名σ、公開鍵ｙ∈Ｇ、生成元ｇ∈Ｇ、及び|ｍ|−Ｍ（ただし|ｍ|−Ｍは正の整数）ビット長のクリアメッセージｍclrが入力され、値ｃ'をｃ'＝Ｈ２(ｍclr，ｇ，ｙ，ｚ，ｒ)により計算し、値ｕ'をｕ'＝ｇｓ・ｙ−ｃ'∈Ｇにより計算し、値ｈ'をｈ'＝Ｈ１(ｕ')により計算し、値ｖ'をｖ'＝ｈ'ｓ・ｚ−ｃ'∈Ｇにより計算し、値ｕ’、値ｈ’、及び値ｖ’を出力する（Ｓ２４）。第２検証計算部５２は、上記クリアメッセージｍclrと上記生成元ｇと上記公開鍵ｙと上記値ｚと上記値ｈ'と上記値ｕ'と上記値ｖ'とが入力され、上記鍵ｗ'をｗ'＝Ｈ３(ｍclr，ｇ，ｙ，ｚ，ｈ'，ｕ'，ｖ')により計算して出力する（Ｓ２５）。第３検証計算部５３は、上記値ｒと上記鍵ｗ’とが入力され、上記値ｒをＬビット長の値ｈ１'とＭビット長の値ｈ２'とに分割し、リカバリメッセージｍrec'を
【数８】
0004914377.tif 000005
により計算し、値ａをａ＝Ｈ４(ｗ'，ｍrec')により計算し、上記値ｈ１'と上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとを出力する（Ｓ２６）。出力部５４は、上記値ｈ１'と上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとが入力され、ａとｈ１'とが等しい場合はメッセージｍをｍ＝ｍrec' |ｍclrにより求めてaccept 1とともに出力し、ａとｈ１'とが等しくない場合はreject 0を出力する（Ｓ２７）。
【００２２】
以上の構成においては、署名生成装置２０の第１生成計算部１２、第３生成計算部２５、及び第２生成計算部２４、並びに、署名検証装置５０の第１検証計算部５１、及び第２検証計算部５２が、Computational Diffie-Hellman問題仮定へのタイト帰着を実現するための基礎部分であり、署名生成装置２０の第４生成計算部２６及び署名検証装置５０の第３検証計算部５３において第３生成計算部２５で生成された鍵ｗを用いて、ハッシュ関数によるリカバリパディング処理を上記基礎部分における署名生成・検証処理と一体的に行う。そのため、以上の構成をとることにより、Computational Diffie-Hellman問題仮定にタイトに帰着可能な安全性の高いメッセージ復元型の署名方式を実現することできる。また、方式の中で用いるハッシュ関数の出力長を変化させることで、リカバリメッセージの長さを変化させることができる。
【００２３】
〔第２実施形態〕
本実施形態は、非特許文献３の署名方式に非特許文献２の共通鍵によるメッセージリカバリパディング技術を適用した形態である。
【００２４】
本発明の署名方式も、位数ｑ（ただしｑは素数）の巡回群Ｇ上の離散対数問題を利用したものであり、Ｇとしては例えば、有限体の乗法群や楕円曲線上の有理点のなす加法群などを用いることができる。なお、本明細書においては便宜上、群演算を乗法で表記しているが（例えばｙの場合はｙ＝ｇｘ∈Ｇ）、この表記はＧが乗法群の場合の乗法演算だけでなく、Ｇが加法群の場合の加法演算（例えばｙの場合はｙ＝ｘ・ｇ∈Ｇ）も含む趣旨である。
【００２５】
また、背景技術及び第１実施形態において既に説明した構成部や処理ステップと共通している部分については同じ符号を付し、説明は省略する。
【００２６】
[鍵生成]
巡回群Ｇの生成元をｇとし、秘密鍵ｘをｑを法とする剰余類の代表元の集合Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに生成するとともに、公開鍵ｙをｙ＝ｇｘ∈Ｇにより生成する。
【００２７】
[署名生成]
図５に署名生成装置３０の機能構成例を、図６にその処理フロー例を示す。署名生成装置３０は、乱数生成部１１と第１生成計算部１２と入力部２３と第３生成計算部２５と第４生成計算部３６と第２生成計算部２４とを備える。乱数生成部１１と第１生成計算部１２は、背景技術の署名生成装置１０で使用されているものと共通であり、入力部２３と第３生成計算部２５と第２生成計算部２４は第１実施形態の署名生成装置２０で使用されているものと共通である。なお、以下の計算において、Ｈ１は０と１からなるビット列をＧのいずれかの元に写像するハッシュ関数、Ｈ２は０と１からなるビット列をＺｑのいずれかの元に写像するハッシュ関数、Ｈ３は０と１からなるビット列をＫ（ただしＫは正の整数）ビット長の０と１からなるビット列に写像するハッシュ関数、ＥｗはＫビット長の鍵ｗによりＬ＋Ｍ（ただしＬとＭは正の整数）ビット長の０と１からなるビット列を同じ長さの０と１からなるビット列に暗号化する共通鍵暗号の暗号化関数、０ＬはＬビット長のすべてが０からなるビット列である。これらのハッシュ関数の入力には、クリアメッセージｍclrを入れることも、公開鍵ｙを入れることも、群Ｇを特定するパラメータを入れることも可能である。
【００２８】
第４生成計算部３６は、第３生成計算部２５で生成された鍵ｗと入力部２３で入力・分割されたリカバリメッセージｍrecとが入力され、値ｄを０Ｌとｍrecとのビット結合により求め、値ｒをｒ＝Ｅｗ(ｄ)により計算して出力する（Ｓ９）。
【００２９】
[署名検証]
図７に署名検証装置６０の機能構成例を、図８にその処理フロー例を示す。署名検証装置６０は、第１検証計算部５１と第２検証計算部５２と第３検証計算部６３と出力部６４とを備える。第１検証計算部５１と第２検証計算部５２は第１実施形態の署名検証装置５０で使用されているものと共通である。なお、以下の計算において、Ｄｗ'はＫビット長の鍵ｗ'によりＬ＋Ｍ（ただしＬとＭは正の整数）ビット長の０と１からなる暗号化されたビット列を同じ長さの０と１からなるビット列に復号化する共通鍵暗号の復号化関数である。
【００３０】
第３検証計算部６３は、署名σの一部である値ｒと第２検証計算部６２で生成された鍵ｗ’とが入力され、値ｄ'をｄ'＝Ｄｗ' (ｒ)により計算し、当該値ｄ'をＬビット長の値ａとＭビット長のリカバリメッセージｍrec'とに分割し、上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとを出力する（Ｓ２８）。出力部６４は、上記値ａと上記リカバリメッセージｍrec'と上記クリアメッセージｍclrとが入力され、値ａと０Ｌとが等しい場合はメッセージｍをｍ＝ｍrec'|ｍclrにより求めてaccept 1とともに出力し、値ａと０Ｌとが等しくない場合はreject 0を出力する（Ｓ２９）。
【００３１】
以上の構成においては、署名生成装置３０の第１生成計算部１２、第３生成計算部２５、及び第２生成計算部２４、並びに、署名検証装置６０の第１検証計算部５１、及び第２検証計算部５２が、Computational Diffie-Hellman問題仮定へのタイト帰着を実現するための基礎部分であり、署名生成装置３０の第４生成計算部３６及び署名検証装置６０の第３検証計算部６３において第３生成計算部２５で生成された鍵ｗを用いて、共通鍵関数によるリカバリパディング処理を上記基礎部分における署名生成・検証処理と一体的に行う。そのため、以上の構成をとることにより、Computational Diffie-Hellman問題仮定にタイトに帰着可能な安全性の高いメッセージ復元型の署名方式を実現することできる。また、方式の中で用いる共通鍵暗号化・復号化関数の入出力長を変化させることで、リカバリメッセージの長さを変化させることができる。
【００３２】
本発明におけるデータ検証システム、その方法、識別子生成装置、データ検証装置は、上記の実施形態に限定されるものではなく、本発明を逸脱しない範囲で適宜変更が可能である。また、上記に説明した処理は記載の順に従った時系列において実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００３３】
また、上記署名生成装置、上記署名検証装置、及び上記署名生成装置と上記署名検証装置とを組み合わせた署名生成検証システムにおける処理機能をコンピュータによって実現する場合、上記署名生成装置、上記署名検証装置、及び署名生成検証システムが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより上記署名生成装置、上記署名検証装置、及び署名生成検証システムにおける処理機能がコンピュータ上で実現される。
【００３４】
また、上記各形態ではコンピュータ上で所定のプログラムを実行させることにより、上記署名生成装置、上記署名検証装置、及び署名生成検証システムを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００３５】
本発明は、装置やシステム等にメッセージ復元型の署名方式を採用する場合において、より短い鍵を用いたい時に有用である。
【図面の簡単な説明】
【００３６】
【図１】本発明による署名生成装置２０の構成例を示す図。
【図２】本発明による署名生成装置２０の処理フロー例を示す図。
【図３】本発明による署名生成装置３０の構成例を示す図。
【図４】本発明による署名生成装置３０の処理フロー例を示す図。
【図５】本発明による署名検証装置５０の構成例を示す図。
【図６】本発明による署名検証装置５０の処理フロー例を示す図。
【図７】本発明による署名検証装置６０の構成例を示す図。
【図８】本発明による署名検証装置６０の処理フロー例を示す図。
【図９】従来技術による署名生成装置１０の構成例を示す図。
【図１０】従来技術による署名生成装置１０の処理フロー例を示す図。
【図１１】従来技術による署名検証装置４０の構成例を示す図。
【図１２】従来技術による署名検証装置４０の処理フロー例を示す図。
【図１】
0004914377.tif 000010
【図２】
0004914377.tif 000011
【図３】
0004914377.tif 000012
【図４】
0004914377.tif 000013
【図５】
0004914377.tif 000014
【図６】
0004914377.tif 000015
【図７】
0004914377.tif 000016
【図８】
0004914377.tif 000017
【図９】
0004914377.tif 000018
【図１０】
0004914377.tif 000019
【図１１】
0004914377.tif 000020
【図１２】
0004914377.tif 000021