(57)【要約】【課題】署名検証に合格する不正なメッセージ復元署名が第三者に生成されることを防止する。【解決手段】ｘを署名生成装置の秘密鍵とし、mrec∈{0,1}Mをリカバリメッセージとし、mclr∈{0,1}Nをクリアメッセージとし、ｈを署名生成装置と署名検証装置での共有値とし、ｋを任意値とし、ｇを位数ｑの巡回群Ｇの生成元とし、Ｒをgk∈Ｇとし、Ｈ０を出力可変長のハッシュ関数H0:{0,1}*→{0,1}L+Mとし、Ｈ１をハッシュ関数H1:{0,1}*→{0,1}Lとし、Ｈ３をハッシュ関数H3:{0,1}*→Zqとし、β=(R,M)とし、γ=(r,mclr,M)とし、t=H3(γ)とし、s=k-t・x∈Zとし、r=H0(β)(+)(h|mrec)とし〔(+)は排他的論理和演算子〕、署名をσ=(r,s)とする。【選択図】図６
2008113315.tif 000002
【特許請求の範囲】
【請求項１】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し（（＋）は排他的論理和演算子）、当該排他的論理和値ｒを出力する排他的論理和演算部と、
出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第３ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する署名出力部と、を有し、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値である、
ことを特徴とする署名生成装置。
【請求項２】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し（（＋）は排他的論理和演算子）、当該排他的論理和値ｒを出力する排他的論理和演算部と、
出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第３ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する署名出力部と、を有し、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値である、
ことを特徴とする署名生成装置。
【請求項３】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記リカバリメッセージｍｒｅｃに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する第２ハッシュ演算部と、
上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し（（＋）は排他的論理和演算子）、当該排他的論理和値ｒを出力する排他的論理和演算部と、
出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第３ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項４】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記クリアメッセージｍｃｌｒに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する第２ハッシュ演算部と、
上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力する排他的論理和演算部と、
出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第３ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項５】
請求項３又は４に記載の署名生成装置であって、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値である、
ことを特徴とする署名生成装置。
【請求項６】
請求項３又は４に記載の署名生成装置であって、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値である、
ことを特徴とする署名生成装置。
【請求項７】
署名検証する署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’との入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを格納する第２記憶部と、
上記署名σ’のｒ’のビット長から値Ｌ（Ｌは署名生成装置と共有される正の整数）を減じた値Ｍ’を、上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’として抽出するビット長抽出部と、
上記ビット長Ｍ’を格納する第３記憶部と、
整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
出力ビット長がＬ＋Ｍ’ビットのハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する排他的論理和演算部と、
署名生成装置との共有値ｈ∈｛０，１｝Ｌと、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力する比較部と、を有し、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値である、
ことを特徴とする署名検証装置。
【請求項８】
署名検証する署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’との入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを格納する第２記憶部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を格納する第３記憶部と、
上記クリアメッセージｍｃｌｒ’のビット長Ｎ’を格納する第４記憶部と、
整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する排他的論理和演算部と、
署名生成装置との共有値ｈ∈｛０，１｝Ｌと、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力する比較部と、を有し、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値である、
ことを特徴とする署名検証装置。
【請求項９】
署名検証する署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’との入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを格納する第２記憶部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を格納する第３記憶部と、
整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する排他的論理和演算部と、
出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｍｒｅｃ’∈｛０，１｝Ｍ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する第３ハッシュ演算部と、
上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する比較部と、
を有することを特徴とする署名検証装置。
【請求項１０】
署名検証する署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’との入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを格納する第２記憶部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を格納する第３記憶部と、
整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する排他的論理和演算部と、
出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記クリアメッセージｍｃｌｒ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する第３ハッシュ演算部と、
上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する比較部と、
を有することを特徴とする署名検証装置。
【請求項１１】
請求項９又は１０に記載の署名検証装置であって、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値である、
ことを特徴とする署名検証装置。
【請求項１２】
請求項９又は１０に記載の署名検証装置であって、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値である、
ことを特徴とする署名検証装置。
【請求項１３】
署名生成を行う署名生成方法であって、
整数の秘密鍵ｘを第１記憶部に格納するステップと、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納するステップと、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
ビット結合部が、署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が、署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力するステップと、を有し、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値である、
ことを特徴とする署名生成方法。
【請求項１４】
署名生成を行う署名生成方法であって、
整数の秘密鍵ｘを第１記憶部に格納するステップと、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納するステップと、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
ビット結合部が、署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が、署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力するステップと、を有し、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値である、
ことを特徴とする署名生成方法。
【請求項１５】
署名生成を行う署名生成方法であって、
整数の秘密鍵ｘを第１記憶部に格納するステップと、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納するステップと、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記リカバリメッセージｍｒｅｃに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力するステップと、
ビット結合部が、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が、署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１６】
署名生成を行う署名生成方法であって、
整数の秘密鍵ｘを第１記憶部に格納するステップと、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納するステップと、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記クリアメッセージｍｃｌｒに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力するステップと、
ビット結合部が、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が、署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１７】
署名検証する署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とが署名入力部に入力されるステップと、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを第２記憶部に格納するステップと、
ビット長抽出部が、上記署名σ’のｒ’のビット長から値Ｌ（Ｌは署名生成装置と共有される正の整数）を減じた値Ｍ’を、上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’として抽出するステップと、
上記ビット長Ｍ’を第３記憶部に格納するステップと、
第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビットのハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
排他的論理和演算部が、上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
比較部が、署名生成装置との共有値ｈ∈｛０，１｝Ｌと、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力するステップと、を有し、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値である、
ことを特徴とする署名検証方法。
【請求項１８】
署名検証する署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とが署名入力部に入力されるステップと、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを第２記憶部に格納するステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納するステップと、
上記クリアメッセージｍｃｌｒ’のビット長Ｎ’を第４記憶部に格納するステップと、
第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
排他的論理和演算部が、上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
比較部が、署名生成装置との共有値ｈ∈｛０，１｝Ｌと、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力するステップと、を有し、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値である、
ことを特徴とする署名検証方法。
【請求項１９】
署名検証する署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とが署名入力部に入力されるステップと、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを第２記憶部に格納するステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納するステップと、
第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
排他的論理和演算部が、上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
第３ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｍｒｅｃ’∈｛０，１｝Ｍ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力するステップと、
比較部が、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力するステップと、
を有することを特徴とする署名検証方法。
【請求項２０】
署名検証する署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とが署名入力部に入力されるステップと、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを第２記憶部に格納するステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納するステップと、
第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
排他的論理和演算部が、上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
第３ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記クリアメッセージｍｃｌｒ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力するステップと、
比較部が、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力するステップと、
を有することを特徴とする署名検証方法。
【請求項２１】
請求項１から６の何れかに記載の署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項２２】
請求項７から１２の何れかに記載の署名検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に、署名からメッセージが復元できるメッセージ復元署名に関する。
【背景技術】
【０００２】
メッセージ復元署名の従来技術として非特許文献１のものがある。この方式は、復元できるメッセージを可変長にできるという利点がある。以下、非特許文献１の署名方式を簡略化して説明する。
【０００３】
〔背景技術での定義〕
Ｐ：楕円曲線Ｅ上の点からなる巡回群の元
ｈ∈｛０，１｝L，ｑ，Ｌ：署名生成装置と署名検証装置とでの共用パラメータ
ｘ：署名生成装置の秘密鍵
Ｙ：秘密鍵ｘに対応する公開鍵（Y=x・P∈E）
ｍ：署名対象のメッセージ
Ｆ０：{0,1}＊→{0,1}L+M（出力ビット長可変）
Ｆ１：{0,1}＊→Zq
【０００４】
［署名生成］
(s-1) メッセージm∈{0,1}N+Mをリカバリメッセージmrec∈{0,1}Mとクリアメッセージmclr∈{0,1}Nとに分割
(s-2) 乱数ｋ∈｛１，...，ｎ−１｝を選択
(s-3) R=k・P=(R1,R2)∈E
(s-4) Π=F0(R1)∈{0,1}L+M (δ｜εはδとεとのビット結合）
(s-5) d=h|mrec∈{0,1}L+M
(s-6) r=d(+)Π∈{0,1}L+M (δ(+)εはδとεとの排他的論理和）
(s-7) t=F1(r|mclr)∈Zq
(s-8) s=(k-x・t) mod q
(s-9) σ=(r,s),mclr出力
【０００５】
［署名検証］
(v-1) σ'=(r',s'),mclr'入力
(v-2) t'=F1(r'|mclr')∈Zq
(v-3) R'=s'・P+t'・Y=(R1',R2')∈E
(v-4) Π'=F0(R1') ∈{0,1}L+M'（M'はr'のビット長からＬを引いた値）
(v-5) d'=r'(+)Π' ∈{0,1}L+M'
(v-6) d'の上位Ｌビットh'と下位Ｍ’ビットmrec'とを抽出
(v-7) h'=hであれば検証合格。リカバリメッセージとしてmrec'出力
【非特許文献１】"ECPV(Elliptic Curve Pintsov-Vanstone message recovery signature)", INTERNATIONAL STANDARD ISO/IEC 9796-3, pp.27-29.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、非特許文献１の署名方式の場合、署名σ=(s,r)とクリアメッセージｍｃｌｒとを入手した攻撃者が、署名検証に合格する別のメッセージに対する署名を生成できる可能性があるという問題点がある。以下にその詳細を説明する。
署名σ=(s,r)とクリアメッセージｍｃｌｒとを入手した攻撃者は、署名σが有するｒのビットをr=r1|m2clrとなるｒ１とｍ２ｃｌｒとに分割することができる。さらに、この攻撃者は、このように分割したｍ２ｃｌｒと入手したクリアメッセージｍｃｌｒとをビット結合してm1clr=m2clr|mclrを生成できる。
【０００７】
ここで、r1|m1clr=r1|m2clr|mclr=r|mclrを満たすため、正規のｒとｍｃｌｒとの組に対するｔと、攻撃者が抽出した不正なｒ１とｍ１ｃｌｒに対するｔは、
(s-7) t=F1(r|mclr)= F1(r1|m1clr) …(1)
と等しくなる。そして、ｓは
(s-8) s=(k-x・t) mod q  …(2)
によって求めているのだから、正規のｒとｍｃｌｒとの組に対するｓと、攻撃者が抽出した不正なｒ１とｍ１ｃｌｒに対するｓは等しくなる。すなわち、入手した正規な署名σ=(s,r)とクリアメッセージｍｃｌｒとを入手した攻撃者は、不正なクリアメッセージｍ1ｃｌｒに対する署名（ｒ１，ｓ）を生成できる。
【０００８】
このような署名（ｒ１，ｓ）と不正なクリアメッセージｍ1ｃｌｒとを上述のように検証すると以下のようになる。
(v-2) t'=F1(r'|mclr')=F1(r1'|m1clr')=t （(1)より）
(v-3) R'=s'・P+t'・Y= s・P+t・Y=(R1,R2)∈E
(v-4) Π'=F0(R1')=F0(R1)∈{0,1}L+M'（M'はr'のビット長からＬを引いた値）
(v-5) d'=r'(+)Π'=r1(+)Π'∈{0,1}L+M'
(v-6) ｄ'の上位Ｌビットｈ'と下位Ｍ’ビットｍｒｅｃ'とを抽出。ここで、攻撃者がｒ１を生成する際に正規のｒから除去したｍ２ｃｌｒ部分（r=r1|m2clr）のビット数がリカバリメッセージｍｒｅｃのビット数Ｍ以下であり、なおかつ、関数Ｆ０（Ｒ１）の出力値のビット数をＬ＋ＭからＬ＋Ｍ’に変化させた場合にＦ０（Ｒ１）の上位Ｌビットが変化しないならば、攻撃者によってｒからｒ１への改変が行われても、ｄ'の上位Ｌビットｈ'は影響をうけない。すなわちｈ'＝ｈとなり、検証に合格する。
【０００９】
本発明はこのような点に鑑みてなされたものであり、署名σ=(s,r)とクリアメッセージｍｃｌｒとを入手した攻撃者が別のメッセージに対する署名を偽造する攻撃を検出可能な署名方式を提供することを目的とする。
【課題を解決するための手段】
【００１０】
〔第１の本発明〕
第１の本発明では上記課題を解決するために、署名生成装置が以下のように署名生成を行う。
まず、整数の秘密鍵ｘを署名生成装置の第１記憶部に格納し、Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納し、Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納する。次に、署名生成装置の任意値生成部が、整数の任意値ｋを生成し、群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する。なお、「ｇｋ∈Ｇ」とは、巡回群Ｇをなす演算をｇについてｋ回実行することを意味する（詳細は後述）。次に、署名生成装置の第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する。なお、「関数εをδに作用させる」とは、「δ又はδを特定するための値を関数εに代入する」ことを意味する。さらに、署名生成装置のビット結合部が、署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力する。なお、第１ビット位置は必ずしも連続したＬビットの位置である必要はなく、離散的に配置された合計Ｌビットの位置でもよい。同様に、第２ビット位置も必ずしも連続したＭビットの位置である必要はなく、離散的に配置された合計Ｍビットの位置でもよい。ただし、「第１ビット位置」及び「第２ビット位置」がどのビット位置であるかについては、署名生成装置と署名検証装置とで統一しておく。また、署名生成装置の排他的論理和演算部が、ハッシュ値Πとビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力する。なお、（＋）は排他的論理和演算子であり、δ（＋）εはδとεとの排他的論理和である。さらに、署名生成装置の第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、排他的論理和値ｒとクリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する。そして、署名生成装置の整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力し、署名出力部が、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとを出力する。なお、値β及び値γの少なくとも一方の値は、さらに、リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値である。
【００１１】
第１の本発明の署名検証装置は、このように生成された署名を、以下のように検証する。なお、署名検証装置が受け取る署名をσ’＝（ｒ’，ｓ’）と表現し、クリアメッセージをｍｃｌｒ’と表現する。
まず、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを署名検証装置の第１記憶部に格納する。そして、署名σ’＝（ｒ’，ｓ’）とクリアメッセージｍｃｌｒ’とが署名検証装置の署名入力部に入力され、第２記憶部に格納される。また、署名検証装置のビット長抽出部が、署名σ’のｒ’のビット長から値Ｌ（Ｌは署名生成装置と共有される正の整数）を減じた値Ｍ’を、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’として抽出し、第３記憶部に格納する。次に、署名検証装置の第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、署名σ’が有するｒ’とクリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する。また、署名検証装置の群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する。なお、「ｇｓ’・ｙｔ’∈Ｇ」とは、巡回群Ｇをなす演算をｇについてｓ’回施し、当該演算をｙについてｔ’回施し、それらの各演算結果に対して当該演算を施す演算を意味する（詳細は後述）。また、署名検証装置の第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビットのハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する。さらに、署名検証装置の排他的論理和演算部が、ハッシュ値Π’と、署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する。そして、署名検証装置の比較部が、署名生成装置との共有値ｈ∈｛０，１｝Ｌと、排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力する。なお、値β’及び値γ’の少なくとも一方の値は、さらに、リカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値である。また、署名生成装置で用いる値β，γのビット構成と、署名検証装置で用いる値β’，γ’のビット構成とが、それぞれ同一である必要がある。例えば、署名生成装置において、ｒを上位Ｌ＋Ｍビットとし、ｍｃｌｒをその次のＮビットとし、その後のＬビットをＭとして結合した２Ｌ＋Ｍ＋Ｎビットの値をγとする場合、署名検証装置においても、ｒ’を上位Ｌ＋Ｍ’ビットとし、ｍｃｌｒ’をその次のＮ’ビットとし、その後のＬビットをＭ’として結合した２Ｌ＋Ｍ’＋Ｎビットの値をγ’としなければならない（詳細は後述）。
【００１２】
以上のように、第１の本発明では、署名生成装置において、値β及び値γの少なくとも一方の値を、さらに、リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値とし、署名検証装置において、値β’及び値γ’の少なくとも一方の値を、さらに、リカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値とし、各処理を行う。そして、署名検証装置は、入力された署名σ’のｒ’のビット長から値Ｌを減じた値Ｍ’を、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’として抽出する。
ここで、署名検証装置に入力された署名σ’のｒ’が前述の攻撃方法によって生成されたｒ１（ｒ＝ｒ１｜ｍ２ｃｌｒ）であった場合、そのビット長Ｍ’は正当なｒ∈｛０，１｝Ｌ＋Ｍのビット長Ｍよりも短い（Ｍ’＜Ｍ）。この場合、値β’及び値γ’の少なくとも一方の値は、署名検証装置が抽出したビット長Ｍ’に依存して決まる値なのだから、β＝β’及びγ＝γ’の少なくとも一方が不成立となる。
β≠β’となる場合、Π’＝Ｈ０（β’）≠Ｈ０（β）＝Πとなって、ｄ’＝Π’（＋）ｒ’≠ｄとなるため、ｄ’の第１ビット位置の値ｈ’は、ｄの第１ビット位置の値ｈと相違し（ｈ’≠ｈ）、署名検証失敗となる。また、γ≠γ’となる場合もｔ’＝Ｈ３（γ’）≠Ｈ３（γ）＝ｔとなるため、Ｒ’＝ｇｓ’・ｙｔ’≠ｇｋ＝Ｒとなり、Ｒ’に依存して定まる値β’はβ’≠βとなり、同様に署名検証失敗となる。これにより、前述の攻撃方法によって生成された不正な署名を高い確率で検出することができる。
【００１３】
〔第２の本発明〕
第２の本発明では上記課題を解決するために、署名生成装置が以下のように署名生成を行う。
まず、整数の秘密鍵ｘを署名生成装置の第１記憶部に格納し、Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納し、Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納する。次に、署名生成装置の任意値生成部が、整数の任意値ｋを生成し、群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する。また、署名生成装置の第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する。さらに、署名生成装置のビット結合部が、署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力する。そして、署名生成装置の排他的論理和演算部が、ハッシュ値Πとビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力し、第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、排他的論理和値ｒとクリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する。そして、署名生成装置の整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力し、署名出力部が、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとを出力する。なお、値β及び値γの少なくとも一方の値は、さらに、クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値である。
【００１４】
第２の本発明の署名検証装置は、このように生成された署名を、以下のように検証する。
まず、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを署名検証装置の第１記憶部に格納する。そして、署名σ’＝（ｒ’，ｓ’）とクリアメッセージｍｃｌｒ’とが署名検証装置の署名入力部に入力され、第２記憶部に格納される。また、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を署名検証装置の第３記憶部に格納し、クリアメッセージｍｃｌｒ’のビット長Ｎ’を第４記憶部に格納する。なお、署名検証装置がビット長Ｍ’の値を取得する方法については後述する。また、署名検証装置の第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、署名σ’が有するｒ’とクリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する。さらに、署名検証装置の群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力し、第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する。また、署名検証装置の排他的論理和演算部が、ハッシュ値Π’と、署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する。そして、署名検証装置の比較部が、署名生成装置との共有値ｈ∈｛０，１｝Ｌと、排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力する。なお、値β’及び値γ’の少なくとも一方の値は、さらに、クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値である。また、署名生成装置で用いる値β，γのビット構成と、署名検証装置で用いる値β’，γ’のビット構成とが、それぞれ同一である必要がある（詳細は後述）。
【００１５】
以上のように、第２の本発明では、署名生成装置において、値β及び値γの少なくとも一方の値を、さらに、クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値とし、署名検証装置において、値β’及び値γ’の少なくとも一方の値を、さらに、クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値とし、各処理を行う。
ここで、署名検証装置に入力されたクリアメッセージｍｃｌｒ’が前述の攻撃方法によって生成されたｍ１ｃｌｒ（ｍ１ｃｌｒ＝ｍ２ｃｌｒ｜ｍｃｌｒ）であった場合、そのビット長Ｎ’は正当なクリアメッセージｍｃｌｒ∈｛０，１｝Ｎのビット長Ｎよりも長い（Ｎ’＞Ｎ）。この場合、値β’及び値γ’の少なくとも一方の値は、クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値なのだから、β＝β’及びγ＝γ’の少なくとも一方が不成立となる。その結果、第１の本発明と同様に、前述の攻撃方法によって生成された不正な署名を高い確率で検出することができる。
【００１６】
〔第３の本発明〕
第３の本発明では上記課題を解決するために、署名生成装置が以下のように署名生成を行う。
まず、整数の秘密鍵ｘが第１記憶部に格納され、Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍが第２記憶部に格納され、Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎが第３記憶部に格納される。そして、署名生成装置の任意値生成部が、整数の任意値ｋを生成し、群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する。
次に、署名生成装置の第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する。次に、署名生成装置の第２ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、リカバリメッセージｍｒｅｃに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する。また、署名生成装置のビット結合部が、ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力する。次に、署名生成装置の排他的論理和演算部が、ハッシュ値Πとビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力し、第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、排他的論理和値ｒとクリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する。その後、整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力し、署名出力部が、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとを出力する。
【００１７】
第３の本発明の署名検証装置は、このように生成された署名を、以下のように検証する。
まず、署名検証装置の第１記憶部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する。そして、署名σ’＝（ｒ’，ｓ’）とクリアメッセージｍｃｌｒ’とが署名検証装置の署名入力部に入力され、第２記憶部に格納される。また、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納する。なお、署名検証装置がビット長Ｍ’の値を取得する方法については後述する。そして、署名検証装置の第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、署名σ’が有するｒ’とクリアメッセージｍｃｌｒとに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する。さらに、署名検証装置の群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する。次に、第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する。さらに、排他的論理和演算部が、ハッシュ値Π’と、署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する。また、署名検証装置の第３ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｍｒｅｃ’∈｛０，１｝Ｍ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する。そして、署名検証装置の比較部が、排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する。
【００１８】
なお、「ｍｒｅｃに依存して定まる値α」には、値αがｍｒｅｃのみに依存する場合のみならず、値αがｍｒｅｃと他の情報とに依存する場合も含まれる。また、「Ｒに依存して定まる値β」には、値βがＲのみに依存する場合のみならず、値βがＲと他の情報とに依存する場合も含まれ、「ｒとｍｃｌｒとに依存して定まる値γ」には、値γがｒとｍｃｌｒとのみに依存する場合のみならず、値γがΠとｍｒｅｃと他の情報とに依存する場合も含まれる。同様に、「ｍｒｅｃ’に依存して定まる値α’」には、値α’がｍｒｅｃ’のみに依存する場合のみならず、値α’がｍｒｅｃ’と他の情報とに依存する場合も含まれ、「Ｒ’に依存して定まる値β’」には、値β’がＲ’のみに依存する場合のみならず、値β’がＲ’と他の情報とに依存する場合も含まれ、「ｒ’とｍｃｌｒ’とに依存して定まる値γ」には、値γ’がｒ’とｍｃｌｒ’とのみに依存する場合のみならず、値γ’がｒ’とｍｃｌｒ’と他の情報とに依存する場合も含まれる。
ただし、署名生成装置で用いる値α，β，γのビット構成と、署名検証装置で用いる値α’，β’，γ’のビット構成とが、それぞれ同一である必要がある。例えば、署名生成装置において、ｒを上位Ｌ＋Ｍビットとし、ｍｃｌｒを下位Ｎビットとして結合したＬ＋Ｍ＋Ｎビットの値をγとする場合、署名検証装置においても、ｒ’を上位Ｌ＋Ｍ’ビットとし、ｍｃｌｒ’を下位Ｎ’ビットとして結合したＬ＋Ｍ’＋Ｎ’ビットの値をγ’としなければならない（詳細は後述）。
【００１９】
以上のように、第３の本発明では、署名生成装置において、リカバリメッセージｍｒｅｃに依存して定まる値αのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを算出し、ハッシュ値ｈを第１ビット位置に配置し、リカバリメッセージｍｒｅｃを第２ビット位置に配置したビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、演算結果Ｒに依存して定まる値βのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを算出し、ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出する。また、署名検証装置において、ｄ’＝Π’（＋）ｒ’を算出し、ｄ’の第２ビット位置の値ｍｒｅｃ’∈｛０，１｝Ｍ’に依存して定まる値α’のハッシュ値Ｈ１（α’）∈｛０，１｝Ｌと、ｄ’の第１ビット位置の値ｈ’∈｛０，１｝Ｌとを比較し、これらが一致した場合に署名検証合格とする。
【００２０】
ここで、署名検証装置に入力された署名σ’のｒ’が前述の攻撃方法によって生成されたｒ１（ｒ＝ｒ１｜ｍ２ｃｌｒ）であった場合、ｒ’＝ｒ１≠ｒであるから、高い確率でｄ’＝Π’（＋）ｒ’≠ｄとなる。この場合、（ｄ’の第２ビット位置の値ｍｒｅｃ’）＝（ｄの第２ビット位置の値ｍｒｅｃ）及び（ｄ’の第１ビット位置の値ｈ’）＝（ｄの第１ビット位置の値ｈ）の少なくとも一方が必ず不成立となる。その結果、ｄ’の第２ビット位置の値ｍｒｅｃ’∈｛０，１｝Ｍ’に依存して定まる値α’のハッシュ値Ｈ１（α’）∈｛０，１｝Ｌと、ｄ’の第１ビット位置の値ｈ’∈｛０，１｝Ｌとが不一致となり、前述の攻撃方法によって生成された不正な署名を高い確率で検出することができる。
【００２１】
〔第４の本発明〕
第４の本発明では上記課題を解決するために、署名生成装置が以下のように署名生成を行う。
まず、整数の秘密鍵ｘを署名生成装置の第１記憶部に格納し、Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納し、Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納する。また、署名生成装置の任意値生成部が、整数の任意値ｋを生成し、群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する。次に、署名生成装置の第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する。また、署名生成装置の第２ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、クリアメッセージｍｃｌｒに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する。次に、署名生成装置のビット結合部が、ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力する。そして、署名生成装置の排他的論理和演算部が、ハッシュ値Πとビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力し、第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、排他的論理和値ｒとクリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する。そして、署名生成装置の整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力し、署名出力部が、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとを出力する。
【００２２】
第４の本発明の署名検証装置は、このように生成された署名を、以下のように検証する。
まず、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを署名検証装置の第１記憶部に格納する。また、署名σ’＝（ｒ’，ｓ’）とクリアメッセージｍｃｌｒ’とが署名検証装置の署名入力部に入力され、第２記憶部に格納される。さらに、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納する。次に、署名検証装置の第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、署名σ’が有するｒ’とクリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する。さらに、群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する。そして、第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力し、署名検証装置の排他的論理和演算部が、ハッシュ値Π’と、署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する。さらに、署名検証装置の第３ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、クリアメッセージｍｃｌｒ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する。そして、署名検証装置の比較部が、排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する。
【００２３】
以上のように、第４の本発明では、署名生成装置において、クリアメッセージｍｃｌｒに依存して定まる値αのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを算出し、ハッシュ値ｈを第１ビット位置に配置し、リカバリメッセージｍｒｅｃを第２ビット位置に配置したビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、演算結果Ｒに依存して定まる値βのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを算出し、ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出する。また、署名検証装置において、ｄ’＝Π’（＋）ｒ’を算出し、クリアメッセージｍｃｌｒ’に依存して定まる値α’のハッシュ値Ｈ１（α’）∈｛０，１｝Ｌと、ｄ’の第１ビット位置の値ｈ’∈｛０，１｝Ｌとを比較し、これらが一致した場合に署名検証合格とする。
【００２４】
ここで、署名検証装置に入力されたクリアメッセージｍｃｌｒ’が前述の攻撃方法によって生成されたｍ１ｃｌｒ（ｍ１ｃｌｒ＝ｍ２ｃｌｒ｜ｍｃｌｒ）であった場合、必ずα’≠αとなり、ハッシュ値Ｈ１（α’）≠ハッシュ値Ｈ１（α）＝ｈとなる。そのため、ｄ’の第１ビット位置の値ｈ’がｈであったとしてもＨ１（α’）≠ｈ’となり、前述の攻撃方法によって生成された不正な署名を高い確率で検出することができる。
なお、第３，４の本発明に第１，２の本発明を適用してもよい。すなわち、第３，４の本発明において、値β及び値γの少なくとも一方の値を、さらに、リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値とし、値β’及び値γ’の少なくとも一方の値を、さらに、署名検証装置で抽出したリカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値としてもよい。また、第３，４の本発明において、値β及び値γの少なくとも一方の値を、さらに、クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値とし、値β’及び値γ’の少なくとも一方の値を、さらに、署名検証装置に入力されたクリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値としてもよい。これにより、前述の攻撃方法によって生成された不正な署名をより高い確率で検出することができる。
【発明の効果】
【００２５】
以上のように本発明では、署名σ=(s,r)とクリアメッセージｍｃｌｒとを入手した攻撃者が別のメッセージに対する署名を偽造する攻撃を検出できる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔第１実施形態〕
まず、第１実施形態について説明する。第１実施形態は、第１の本発明に係る実施形態である。
＜全体構成＞
図１は、第１実施形態の署名システム１の全体構成を示した概念図である。
図１に示すように、本形態の署名システム１は、署名生成を行う署名生成装置１０と、署名検証を行う署名検証装置２０と、署名生成装置１０の効果鍵を公開する公開鍵サーバ装置３０とを有し、相互にネットワーク４０を通じて通信可能に接続される。なお、署名生成装置１０、署名検証装置２０及び公開鍵サーバ装置３０は、それぞれ、公知のコンピュータに所定のプログラムが読み込まれることにより構成される装置である。
【００２７】
＜署名生成装置１０の構成＞
次に、署名生成装置１０の構成を説明する。
［ハードウェア構成］
図２は、第１実施形態の署名生成装置１０のハードウェア構成を例示したブロック図である。
図２に例示するように、この例の署名生成装置１０は、ＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６、バス１７及び通信部１８を有している。
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、この例の入力部１２は、データが入力される入力ポート、キーボード、マウス等であり、出力部１３は、データを出力する出力ポート、外部記録媒体へのデータ記憶装置、印刷装置、ディスプレイなどである。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、各種プログラムを格納したプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、例えば、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが書き込まれるプログラム領域１６ａ及び各種データが書き込まれるデータ領域１６ｂを有している。また、通信部１８は、ネットワークカードなどである。また、この例のバス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５、ＲＡＭ１６及び通信部１８を、データのやり取りが可能なように接続する。
【００２８】
［ハードウェアとプログラムとの協働］
ＣＰＵ１１（図２）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されているプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。なお、各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。
【００２９】
図３は、ＣＰＵ１１にプログラムが読み込まれることにより構成される第１実施形態の署名生成装置１０の機能構成を例示したブロック図である。なお、図３における矢印はデータの流れを示すが、一時メモリ１０ｔや制御部１０ｓに入出力されるデータの流れは省略してある。
図３に示すように、本形態の署名生成装置１０は、記憶部１０ａと、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、入力部１０ｄと、メッセージ分割部１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部１０ｈ，１０ｐと、ビット結合部１０ｍと、排他的論理和演算部１０ｎと、整数演算部１０ｑと、通信部１０ｒと、制御部１０ｓと、一時メモリ１０ｔとを有する。
また、図４は、ハッシュ演算部１０ｈの機能構成の詳細を示した図である。図４に示すように、ハッシュ演算部１０ｈは、ハッシュ回数演算部１０ｈａと、部分ハッシュ演算部１０ｈｂと、ビット結合部１０ｈｃと、ビット削除部１０ｈｄとを有する。
【００３０】
なお、記憶部１０ａと一時メモリ１０ｔとは、例えば、図２に記載したレジスタ１１ｃ、補助記憶装置１４、ＲＡＭ１６、或いはこれらを結合した記憶領域に相当する。また、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、メッセージ分割部１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部１０ｈ，１０ｐと、ビット結合部１０ｍと、排他的論理和演算部１０ｎと、整数演算部１０ｑと、制御部１０ｓとは、それぞれの処理を実現するためのプログラムがＣＰＵ１１に読み込まれることにより構成されるものである。また、入力部１０ｄは、所定のプログラムが読み込まれたＣＰＵ１１の制御のもと駆動する入力部１２であり、通信部１０ｒは、所定のプログラムが読み込まれたＣＰＵ１１の制御のもと駆動する通信部１８である。また、署名生成装置１０は、制御部１０ｓの制御のもと各処理を実行する。さらに、特に明示しない限り、演算過程の各データは逐一一時メモリ１０ｔに読み書きされる。
また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名生成装置１０の機能をコンピュータに実行させるためのプログラムに相当する。
【００３１】
＜署名検証装置２０の構成＞
次に、署名検証装置２０の構成を説明する。
［ハードウェア構成］
図２に示した署名生成装置１０のハードウェア構成と同様である。
［ハードウェアとプログラムとの協働］
署名検証装置２０も図２に示したようなコンピュータに所定のプログラムが読み込まれることにより構成される。図５は、このように構成される第１実施形態の署名検証装置２０の機能構成を例示したブロック図である。なお、図５における矢印はデータの流れを示すが、一時メモリ２０ｐや制御部２０ｎに入出力されるデータの流れは省略してある。
図５に示すように、本形態の署名検証装置２０は、記憶部２０ａと、通信部２０ｂと、ビット長抽出部２０ｃと、ハッシュ演算部２０ｄ，２０ｆと、群演算部２０ｅと、排他的論理和演算部２０ｇと、ビット抽出部２０ｈと、比較部２０ｉと、出力部２０ｍと、制御部２０ｎと、一時メモリ２０ｐとを有する。
【００３２】
なお、記憶部２０ａと一時メモリ２０ｐとは、例えば、コンピュータが具備するレジスタ、補助記憶装置、ＲＡＭ、或いはこれらを結合した記憶領域に相当する。また、ビット長抽出部２０ｃと、ハッシュ演算部２０ｄ，２０ｆと、群演算部２０ｅと、排他的論理和演算部２０ｇと、ビット抽出部２０ｈと、比較部２０ｉと、制御部２０ｎとは、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。また、出力部２０ｍと通信部２０ｂは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動する。また、署名検証装置２０は、制御部２０ｎの制御のもと各処理を実行する。さらに、特に明示しない限り、演算過程の各データは逐一一時メモリ２０ｐに読み書きされる。
また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名検証装置２０の機能をコンピュータに実行させるためのプログラムに相当する。
【００３３】
＜処理＞
次に、本形態の処理について説明する。
［前処理］
まず、署名システム１で使用する位数ｑの離散対数問題の求解が困難な巡回群Ｇとその生成元ｇ∈Ｇとを決定する。このような巡回群Ｇとしては、例えば、楕円曲線上の有理点のなす群や有限体の乗法群などを用いることができる。なお、安全性の面から位数ｑは素数であることが望ましい。また、署名システム１で使用するビット長パラメータＬ∈Ｚ＞0（０より大きな整数）と、共用値ｈ∈｛０，１｝Ｌとを決定する。
さらに、後述するリカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビットに定まる出力が可変長のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを決定する。なお、このようなハッシュ関数の演算方法については後述する。
【００３４】
また、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌと、また、入力値に対してＺｑ（ｑを法とする完全剰余系）の元を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑとを決定する。ハッシュ関数Ｈ１は、ハッシュ関数Ｈ０と同様に構成でき、ハッシュ関数Ｈ３は、ＳＨＡ−１等のハッシュ値に対し、ｑを法とした剰余演算を行うことで構成できる。
以上のように決定された巡回群Ｇや各ハッシュ関数Ｈ０，Ｈ１，Ｈ３を特定する情報は、例えば、署名生成装置１０や署名検証装置２０を構成する各プログラムに書き込まれ、署名生成装置１０や署名検証装置２０は、決定された巡回群Ｇでの演算や、各ハッシュ関数Ｈ０，Ｈ１，Ｈ３の演算が可能になるものとする。また、ビット長パラメータＬ∈Ｚ＞0や共用値ｈ∈｛０，１｝Ｌや位数ｑや生成元ｇ∈Ｇは、署名生成装置１０の記憶部１０ａと署名検証装置２０の記憶部２０ａに格納される。
【００３５】
［鍵生成処理］
次に、署名生成装置１０が行う鍵生成処理について説明する。
まず、署名生成装置１０の秘密鍵生成部１０ｂが任意の秘密鍵ｘ∈Ｚｑを生成する。なお、この秘密鍵ｘの生成は、擬似乱数をＺｑにマッピングして行ってもよいし、署名生成者によって任意に決定された値を元に行ってもよい。生成された秘密鍵ｘは、署名生成装置１０の記憶部１０ａに安全に格納される。すなわち、署名生成装置１０の外部の装置は、記憶部１０ａから秘密鍵ｘを取得することができない。
【００３６】
次に、署名生成装置１０の公開鍵生成部１０ｃが、記憶部１０ａから秘密鍵ｘと巡回群Ｇの生成元ｇ∈Ｇとを読み込み、巡回群Ｇで定義された演算
y=gx∈G  …(3)
を行って秘密鍵ｘに対応する公開鍵ｙ∈Ｇを生成し、記憶部１０ａに格納する。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（３）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｘ倍）する演算（ｘ・ｇ∈Ｅ）を意味し、公開鍵ｙは楕円曲線Ｅ上の点となる。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（３）の右辺は、ｇｘｍｏｄ ｐ（ただし、ｐ＝２ｑ＋１）の演算を意味し、公開鍵ｙはスカラー値となる。生成された公開鍵ｙは、通信部１０ｒからネットワーク４０を通じて公開鍵サーバ装置３０に送信され、公開鍵サーバ装置３０は、送信された公開鍵ｙを例えば公開鍵証明書とともに公開する。なお、公開鍵ｙ等の公開とは、公開鍵ｙ等が公開鍵サーバ装置３０の記憶部に格納され、ネットワーク４０に接続可能な任意の装置が公開鍵サーバ装置３０の記憶部に格納された公開鍵ｙ等を取得可能な状態とすることを意味する。署名検証装置２０は、このような公開鍵ｙを通信部２０ｂによって公開鍵サーバ装置３０から受信し、記憶部２０ａに格納する。
【００３７】
［署名生成処理］
次に、第１実施形態の署名生成処理について説明する。
図６は、第１実施形態の署名生成処理を説明するためのフローチャートである。以下、図６に従って本形態の署名生成処理を説明する。
まず、署名生成装置１０（図３）の入力部１０ｄに、メッセージｍ∈｛０，１｝Ｎ＋Ｍとリカバリメッセージのビット長Ｍ≧１とが入力される（ステップＳ１１）。入力されたこれらの情報は、それぞれ記憶部１０ａに格納される。
【００３８】
次に、メッセージ分割部１０ｅが、記憶部１０ａからメッセージｍ∈｛０，１｝Ｎ＋Ｍとリカバリメッセージのビット長Ｍ≧１とを読み込む。メッセージ分割部１０ｅは、これらの情報を用い、
メッセージｍ∈｛０，１｝Ｎ＋Ｍを、ビット長Ｍのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍ  と、ビット長Ｎ（Ｎ≧０）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとに分割する（ステップＳ１２）。例えば、メッセージｍ∈｛０，１｝Ｎ＋Ｍの上位Ｍビットをリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍとし、下位Ｎビットをクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとする。なお、分割法はこれに限定されず、メッセージｍ∈｛０，１｝Ｎ＋Ｍのどのビットをリカバリメッセージｍｒｅｃとし、どのビットをクリアメッセージｍｃｌｒ
とするかは、任意に設定できる。このように分割されたビット長Ｍのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍ  と、ビット長Ｎのクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとは、それぞれ記憶部１０ａに格納される。
【００３９】
次に、任意値生成部１０ｆが任意値ｋ∈Ｚｑを生成し、生成した任意値ｋを記憶部１０ａに格納する（ステップＳ１３）。なお、任意値ｋの生成は、例えば、擬似乱数をＺｑにマッピングすることにより行う。
次に、群演算部１０ｇが、記憶部１０ａから生成元ｇ∈Ｇと任意値ｋ∈Ｚｑとを読み込み、
R=gk∈G  …(4)
を算出し、当該演算結果Ｒ∈Ｇを記憶部１０ａに出力して格納する（ステップＳ１４）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（４）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｋ倍）する演算（ｋ・ｇ∈Ｅ）を意味し、演算結果Ｒは楕円曲線Ｅ上の点となる。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（４）の右辺は、ｇｋｍｏｄ ｐの演算を意味し、演算結果Ｒはスカラー値となる。
【００４０】
次に、ハッシュ演算部１０ｈが、記憶部１０ａから演算結果Ｒ∈Ｇとリカバリメッセージｍｒｅｃのビット長Ｍとビット長パラメータＬを読み込む。ハッシュ演算部１０ｈは、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビットに定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒとビット長Ｍとに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値
Π=H0(β)∈{0,1}L+M  …(5)
を記憶部１０ａに出力して格納する（ステップＳ１５）。なお、第１実施形態では、βは演算結果Ｒとビット長Ｍとのみに依存する値γ＝（Ｒ，Ｍ）である。また、本形態のβの構成方法に限定はないが、βの構成方法は後述する署名検証装置２０でのβ’の構成方法と同一とする。本形態のβの構成例としては以下のようなものがある。
【００４１】
巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合：
〔β−１〕楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値（例えば、点Ｒのｘ座標若しくはｙ座標、又は、点Ｒのｘ座標とｙ座標とのビット結合値）を上位ビットとし、Ｍを下位ビットとして結合した値をβとする。
〔β−２〕楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値を下位ビットとし、Ｍを上位ビットとして結合した値をβとする。
〔β−３〕所定の規則に従い、楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値とＭとの各ビットをそれぞれ離散的に配置して結合した値をβとする。
巡回群Ｇが有限体の乗法群であった場合：
〔β−４〕スカラー値である演算結果Ｒを上位ビットとし、Ｍを下位ビットとして結合した値をβとする。
〔β−５〕スカラー値である演算結果Ｒを下位ビットとし、Ｍを上位ビットとして結合した値をβとする。
〔β−６〕所定の規則に従い、スカラー値である演算結果ＲとＭとの各ビットをそれぞれ離散的に配置して結合した値をβとする。
【００４２】
［ステップＳ１５の処理の例］
図７は、ステップＳ１５の処理の例を説明するためのフローチャートである。
【００４３】
まず、リカバリメッセージのビット長Ｍとビット長パラメータＬとがハッシュ演算回数算出部１０ｈａに読み込まれる。ハッシュ演算回数算出部１０ｈａは、
emax=rounddown{(L+M)/length(H)}  …(5-1)
の演算を行ってｅｍａｘ
を一時メモリ１０ｔに格納する（ステップＳ１５ａ）。なお、rounddown｛＊｝は＊の小数点以下を切り捨てる演算を意味し、length（＊）は＊のビット長を意味し、Ｈは公知のハッシュ関数を意味する。なお、ハッシュ関数Ｈの具体例としては、ＳＨＡ−１（ビット長１６０ビット）やＭＤ５（ビット長１２８ビット）などを例示できる。例えば、Ｌ＋Ｍ＝５００であり、ハッシュ関数ＨがＳＨＡ−１〔length（Ｈ）＝１６０〕であるならば、ｅｍａｘ＝３である。
【００４４】
次に、制御部１０ｓは変数ｅに０を代入し、変数ｅを一時メモリ１０ｔに格納する（ステップＳ１５ｂ）。
次に、部分ハッシュ演算部１０ｈｂが、一時メモリ１０ｔから変数ｅを読み込み、記憶部１０ａからβ＝Ｒを読み込み、ハッシュ値
H(e,β)  …(5-2)
を算出して一時メモリ１０ｔに格納する（ステップＳ１５ｃ）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（５−２）は、楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値（例えば、点Ｒのｘ座標若しくはｙ座標、又は、点Ｒのｘ座標とｙ座標とのビット結合値）と変数ｅとのビット結合値にハッシュ関数Ｈを作用させる演算を意味する。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（５−２）は、スカラー値である演算結果Ｒと変数ｅとのビット結合値にハッシュ関数Ｈ０を作用させる演算を意味する。
【００４５】
次に、制御部１０ｓが、一時メモリ１０ｔからｅｍａｘと変数ｅとを読み込み、
e=emax  …(5-3)
を満たすか否かを判断する（ステップＳ１５ｄ）。ここで、式（５−３）を満たさなければ、制御部１０ｓはｅ＋１を新たなｅとし、新たなｅを一時メモリ１０ｔに格納した後（ステップＳ１５ｅ）、処理をステップＳ１５ｃに戻す。一方、式（５−３）を満たすのであれば、制御部１０ｓはビット結合部１０ｈｃに指示を与え、ビット結合部１０ｈｃは、一時メモリ１０ｔから各ハッシュ値H(0,R),H(1,R),H(2,R),…,H(emax,R)を読み込み、それらのビット結合値
HC(R)=H(0,R)|・・・|H(emax,R)  …(5-4) 
を算出して一時メモリ１０ｔに格納する（ステップＳ１５ｆ）。 
次に、ビット削除部１０ｈｄが、一時メモリ１０ｔから、ビット結合値ＨＣ（Ｒ）とリカバリメッセージのビット長Ｍとビット長パラメータＬとを読み込み、
Π=H0(R)=delete{length(HC(R))-length(L+M),HC(R)}  …(5-5)
を算出して記憶部１０ａに出力する（ステップＳ１５ｇ）。なお、delete｛δ，ε｝は、εのビットを先頭からδビットだけ削除する処理を意味する。すなわち、式（５−５）は、ＨＣ（Ｒ）の先頭ビットを削除して全体のビット長をＬ＋ＭとしたものをΠ＝Ｈ０（Ｒ）とする演算を意味する。
【００４６】
なお、ステップＳ１５の処理方法はこれに限定されない。例えば、ｅを用いるのではなく、ハッシュチェインによってハッシュ値のビット長を拡張する方法でもよい。この場合、式（５−４）のＨＣ（Ｒ）は、例えば、    
HC(R)=H(R)|H(H(R))|H(H(H(R)))|…|H(H(H…(R)…))
となる（［ステップＳ１５の処理の例］の説明終わり）。
ステップＳ１５の後、ビット結合部１０ｍが、記憶部１０ａから共有値ｈ∈｛０，１｝Ｌと、リカバリメッセージｍｒｅｃとを読み込む（ステップＳ１６）。ビット結合部１０ｍは、共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値
d=h|mrec∈{0,1}L+M  …(6)
を算出し、当該ビット結合値ｄを記憶部１０ａに出力して格納する（ステップＳ１７）。なお、「第１ビット位置」及び「第２ビット位置」をどのビット位置にするかについて特に限定はない。しかし、署名生成装置１０と署名検証装置２０との間では、「第１ビット位置」及び「第２ビット位置」をどのビット位置にするかの基準を同一にしなければならない。図９に「第１ビット位置」及び「第２ビット位置」の設定例を示す。
【００４７】
図９（ａ）の例は、連続した上位Ｌビットを「第１ビット位置」とし、連続した下位Ｍビットを「第２ビット位置」とした例である。図９（ｂ）の例は、連続した上位Ｍビットを「第２ビット位置」とし、連続した下位Ｌビットを「第１ビット位置」とした例である。また、図９（ｃ）の例は、Ｌ≧Ｍの場合の例であり、上位から奇数番目のビット（合計Ｍビット）の位置を「第２ビット位置」とし、その他のビット位置を「第１ビット位置」とした例である。
次に、排他的論理和演算部１０ｎが、記憶部１０ａからハッシュ値Πとビット結合値ｄとを読み込む。排他的論理和演算部１０ｎは、ハッシュ値Πとビット結合値ｄとの排他的論理和
r=Π(+)d∈{0,1}L+M  …(7)
を算出し（（＋）は排他的論理和演算子）、当該排他的論理和値ｒを記憶部１０ａに出力して格納する（ステップＳ１８）。
【００４８】
次に、ハッシュ演算部１０ｐが、記憶部１０ａから排他的論理和値ｒとクリアメッセージｍｃｌｒとビット長Ｍとを読み込む。ハッシュ演算部１０ｐは、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、排他的論理和値ｒとクリアメッセージｍｃｌｒとビット長Ｍとに依存して定まる値γに作用させ、その演算結果であるハッシュ値
t=H3(γ)∈Zq  …(8)
を記憶部１０ａに出力して格納する（ステップＳ１９）。なお、第１実施形態では、γは排他的論理和値ｒとクリアメッセージｍｃｌｒとビット長Ｍとのみに依存する値γ＝（ｒ，ｍｃｌｒ，Ｍ）である。本形態のγの構成方法に限定はないが、γの構成方法は後述する署名検証装置２０でのγ’の構成方法と同一とする。γの構成例としては以下のようなものがある。
【００４９】
〔γ−１〕最上位Ｌ＋Ｍビットをｒとし、その後に続くＮビットをｍｃｌｒとし、さらにその後に続くＬビットをＭとして結合した２Ｌ＋Ｍ＋Ｎビットの値をγとする。
〔γ−２〕最上位ＬビットをＭとし、その後に続くＬ＋Ｍビットをｒとし、さらにその後に続くＮビットをｍｃｌｒとして結合した２Ｌ＋Ｍ＋Ｎビットの値をγとする。
〔γ−３〕所定の規則に従い、Ｍやｒやｍｃｌｒのビットをそれぞれ離散的（例えば、Ｍを偶数番目のビットに離散的に配置する等）に結合したものをγとする。
次に、整数演算部１０ｑが、記憶部１０ａから任意値ｋとハッシュ値ｔと秘密鍵ｘとｑとを読み込む。整数演算部１０ｑは、
s=k-t・x∈Zq  …(9)
を算出し、当該演算結果ｓを記憶部１０ａに出力して格納する（ステップＳ２０）。
次に、通信部１０ｒに、排他的論理和値ｒと演算結果ｓとクリアメッセージｍｃｌｒとが読み込まれ、通信部１０ｒは、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとをネットワーク４０を通じて署名検証装置２０に送信する（ステップＳ２１）。
【００５０】
［署名検証処理］
次に、第１実施形態の署名検証処理について説明する。
図８は、第１実施形態の署名検証処理を説明するためのフローチャートである。以下、図８に従って本形態の署名検証処理を説明する。
まず、署名検証装置２０（図５）の通信部２０ｂが、署名σ’＝（ｒ’，ｓ’）とクリアメッセージｍｃｌｒ’とを受信し（「入力を受け付け」に相当）、これらを記憶部２０ａに格納する（ステップＳ４１）。なお、署名とリアメッセージとが正規なものであれば、σ’＝（ｒ’，ｓ’）＝σ＝（ｒ，ｓ）であり、ｍｃｌｒ’＝ｍｃｌｒであるが、ここでは、検証対象の署名をσ’＝（ｒ’，ｓ’）と表現し、検証対象のクリアメッセージをｍｃｌｒ’と表現する。
【００５１】
次に、ビット長抽出部２０ｃが、記憶部２０ａから、ビット長パラメータＬと署名σ’＝（ｒ’，ｓ’）のｒ’とを読み込む。ビット長抽出部２０ｃは、
M'=length(r')‐L  …(10)
により、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を算出し、記憶部２０ａに格納する（ステップＳ４２）。
次に、ハッシュ演算部２０ｄが、記憶部２０ａからｒ’とクリアメッセージをｍｃｌｒ’とｑとビット長Ｍ’とを読み込む。ハッシュ演算部２０ｄは、署名生成装置１０と同一のハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、ｒ’とｍｃｌｒ’とビット長Ｍ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値
t’=H3(γ’)  …(11)
を記憶部２０ａに出力して格納する（ステップＳ４３）。なお、γ’の構成方法は前述した署名生成装置１０でのγの構成方法と同一（ｒ＝ｒ’とし、ｍｃｌｒ＝ｍｃｌｒ’とした場合に同一）とする。
【００５２】
次に、群演算部２０ｅが、記憶部２０ａから、生成元ｇ∈Ｇと署名生成装置１０の公開鍵ｙ∈Ｇと署名σ’のｓ’とハッシュ値ｔ’とを読み込み、
R’=gs’・yt’∈G  …(12)
の演算を行い、その演算結果Ｒ’を記憶部２０ａに出力して格納する（ステップＳ４４）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（１２）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｓ’倍）し、公開鍵ｙ＝（ｙ１，ｙ２）を楕円スカラー倍（楕円ｔ’倍）し、それらの演算結果を楕円加算する演算（ｓ’・ｇ＋ｔ’・ｙ∈Ｅ）を意味し、演算結果Ｒ’は楕円曲線Ｅ上の点となる。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（１２）の右辺は、ｇｓ’・ｙｔ’ｍｏｄ ｐの演算を意味し、演算結果Ｒ’はスカラー値となる。
【００５３】
次に、ハッシュ演算部２０ｆが、記憶部２０ａから演算結果Ｒ’∈Ｇとリカバリメッセージｍｒｅｃ’のビット長Ｍ’とビット長パラメータＬを読み込む。ハッシュ演算部２０ｆは、署名生成装置１０と同じハッシュ関数Ｈ０を演算結果Ｒ’とビット長Ｍ’とに依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値
Π'=H0(β’)∈{0,1}L+M'  …(13)
を記憶部２０ａに出力して格納する（ステップＳ４５）。なお、β’の構成方法は、前述した署名生成装置１０でのβの構成方法と同一とし、また、Ｈ０（β'）の演算は、署名生成装置１０の場合のＨ０（β'）の演算と同一（β＝β'，Ｍ＝Ｍ’の場合に同一）とする。
【００５４】
次に、排他的論理和演算部２０ｇが、記憶部２０ａから、ハッシュ値Π’と署名σ’が有するｒ’とを読み込み、それらの排他的論理和
d’=Π’(+)r’∈{0,1}Ｌ＋Ｍ’  …(14)
を算出し、当該排他的論理和値ｄ’を記憶部２０ａに出力して格納する（ステップＳ４６）。
次に、ビット抽出部２０ｈが、記憶部２０ａから排他的論理和値ｄ’とリカバリメッセージｍｒｅｃ’のビット長Ｍ’とを読み込む。ビット抽出部２０ｈは、排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｍｒｅｃ’∈｛０，１｝Ｍ’とを抽出し、それらを記憶部２０ａに格納する（ステップＳ４７）。なお、「第１ビット位置」及び「第２ビット位置」は、署名生成装置１０の処理での「第１ビット位置」及び「第２ビット位置」と同一（ｄ＝ｄ’とした場合に同一）とする。
【００５５】
次に、比較部２０ｉが、記憶部２０ａから共有値ｈ∈｛０，１｝Ｌと値ｈ’とを読み込み（ステップＳ４８）、
h'=h   …(15)
を満たすか否かを判断する（ステップＳ４９）。
ここで、式（１５）を満たさない場合、比較部２０ｉは０（検証失敗）を記憶部２０ａに出力して格納し、出力部２０ｍは、記憶部２０ａから送られた０（検証失敗）を出力する（ステップＳ５０）。一方、式（１５）を満たす場合、比較部２０ｉは１（検証成功）を記憶部２０ａに出力して格納し、出力部２０ｍは、記憶部２０ａから送られた１（検証成功）を出力し（ステップＳ５１）、さらにリカバリメッセージｍｒｅｃ’を出力する（ステップＳ５２）。
【００５６】
〔第２実施形態〕
次に、第２実施形態について説明する。第２実施形態は、第２の本発明に係る実施形態である。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
＜全体構成＞
署名生成装置１０が署名生成装置１１０となり、署名検証装置２０が署名検証装置１２０となる以外は、第１実施形態と同じである。
＜署名生成装置１１０の構成＞
［ハードウェア構成］
図２に示した署名生成装置１０のハードウェア構成と同様である。
［ハードウェアとプログラムとの協働］
第１実施形態と同様、本形態の署名生成装置１１０も図２に示したようなコンピュータに所定のプログラムが読み込まれることにより構成される。
図１０は、ＣＰＵにプログラムが読み込まれることにより構成される第２実施形態の署名生成装置１１０の機能構成を例示したブロック図である。なお、図１０における矢印はデータの流れを示すが、一時メモリ１０ｔや制御部１０ｓに入出力されるデータの流れは省略してある。また、図１０において第１実施形態と共通する部分には図３と同じ符号を付した。
【００５７】
図１０に示すように、本形態の署名生成装置１１０は、記憶部１０ａと、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、入力部１０ｄと、メッセージ分割部１１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部１１０ｈ，１１０ｐと、ビット結合部１０ｍと、排他的論理和演算部１０ｎと、整数演算部１０ｑと、通信部１０ｒと、制御部１０ｓと、一時メモリ１０ｔとを有する。なお、メッセージ分割部１１０ｅとハッシュ演算部１１０ｈ，１１０ｐとは、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。
【００５８】
＜署名検証装置１２０の構成＞
次に、署名検証装置１２０の構成を説明する。
［ハードウェア構成］
図２に示した署名生成装置１０のハードウェア構成と同様である。
［ハードウェアとプログラムとの協働］
署名検証装置１２０も図２に示したようなコンピュータに所定のプログラムが読み込まれることにより構成される。図１１は、このように構成される第２実施形態の署名検証装置１２０の機能構成を例示したブロック図である。なお、図１１における矢印はデータの流れを示すが、一時メモリ２０ｐや制御部２０ｎに入出力されるデータの流れは省略してある。また、図１１において第１実施形態と共通する部分には図５と同じ符号を付した。
図１１に示すように、本形態の署名検証装置１２０は、記憶部２０ａと、通信部２０ｂと、ビット長抽出部１２０ｃと、ハッシュ演算部１２０ｄ，１２０ｆと、群演算部２０ｅと、排他的論理和演算部２０ｇと、ビット抽出部２０ｈと、比較部２０ｉと、出力部２０ｍと、制御部２０ｎと、一時メモリ２０ｐとを有する。なお、ビット長抽出部１２０ｃとハッシュ演算部１２０ｄ，１２０ｆとは、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。
【００５９】
＜処理＞
次に、本形態の処理について説明する。
［前処理］
第１実施形態と同様である。
［鍵生成処理］
第１実施形態と同様である。
［署名生成処理］
次に、第１実施形態の署名生成処理について説明する。
図１２は、第２実施形態の署名生成処理を説明するためのフローチャートである。以下、図１２に従って本形態の署名生成処理を説明する。
まず、署名生成装置１１０（図１０）の入力部１０ｄに、メッセージｍ∈｛０，１｝Ｎ＋Ｍとリカバリメッセージのビット長Ｍ≧１とが入力される（ステップＳ１１１）。入力されたこれらの情報は、それぞれ記憶部１０ａに格納される。
【００６０】
次に、メッセージ分割部１１０ｅが、記憶部１０ａからメッセージｍ∈｛０，１｝Ｎ＋Ｍとリカバリメッセージのビット長Ｍ≧１とを読み込む。メッセージ分割部１１０ｅは、これらの情報を用い、
メッセージｍ∈｛０，１｝Ｎ＋Ｍを、ビット長Ｍのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍ  と、ビット長Ｎ（Ｎ≧０）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとに分割し、さらにクリアメッセージｍｃｌｒ∈｛０，１｝Ｎのビット長Ｎを抽出する（ステップＳ１１２）。なお、ビット分割の手法は第１実施形態と同様である。このように分割されたビット長Ｍのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍ  と、ビット長Ｎのクリアメッセージｍｃｌｒ∈｛０，１｝Ｎと、クリアメッセージｍｃｌｒ∈｛０，１｝Ｎのビット長Ｎとは、それぞれ記憶部１０ａに格納される。
次に、第１実施形態と同じく、任意値生成部１０ｆが任意値ｋ∈Ｚｑを生成し、生成した任意値ｋを記憶部１０ａに格納し（ステップＳ１１３）。群演算部１０ｇが、記憶部１０ａから生成元ｇ∈Ｇと任意値ｋ∈Ｚｑとを読み込み、式（４）に従ってＲを算出し、当該演算結果Ｒ∈Ｇを記憶部１０ａに出力して格納する（ステップＳ１１４）。
【００６１】
次に、ハッシュ演算部１１０ｈが、記憶部１０ａから演算結果Ｒ∈Ｇとリカバリメッセージｍｒｅｃのビット長Ｍとクリアメッセージｍｃｌｒのビット長Ｎとビット長パラメータＬを読み込む。ハッシュ演算部１１０ｈは、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビットに定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒとビット長Ｎとに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値
Π=H0(β)∈{0,1}L+M    …(16)
を記憶部１０ａに出力して格納する（ステップＳ１１５）。なお、第２実施形態では、βは演算結果Ｒとビット長Ｎとのみに依存する値γ＝（Ｒ，Ｎ）である。また、本形態のβの構成方法に限定はないが、βの構成方法は後述する署名検証装置１２０でのβ’の構成方法と同一とする。本形態のβの構成例としては以下のようなものがある。
巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合：
〔β−１〕楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値（例えば、点Ｒのｘ座標若しくはｙ座標、又は、点Ｒのｘ座標とｙ座標とのビット結合値）を上位ビットとし、Ｎを下位ビットとして結合した値をβとする。
〔β−２〕楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値を下位ビットとし、Ｎを上位ビットとして結合した値をβとする。
〔β−３〕所定の規則に従い、楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値とＮとの各ビットをそれぞれ離散的に配置して結合した値をβとする。
巡回群Ｇが有限体の乗法群であった場合：
〔β−４〕スカラー値である演算結果Ｒを上位ビットとし、Ｎを下位ビットとして結合した値をβとする。
〔β−５〕スカラー値である演算結果Ｒを下位ビットとし、Ｎを上位ビットとして結合した値をβとする。
〔β−６〕所定の規則に従い、スカラー値である演算結果ＲとＮとの各ビットをそれぞれ離散的に配置して結合した値をβとする。
【００６２】
ステップＳ１１５の後、第１実施形態のステップＳ１６〜Ｓ１８と同様な処理が行われる（ステップＳ１１６〜Ｓ１１８）。その後、ハッシュ演算部１１０ｐが、記憶部１０ａから排他的論理和値ｒとクリアメッセージｍｃｌｒとビット長Ｎとを読み込む。ハッシュ演算部１１０ｐは、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、排他的論理和値ｒとクリアメッセージｍｃｌｒとビット長Ｎとに依存して定まる値γに作用させ、その演算結果であるハッシュ値
t=H3(γ)∈Zq  …(17)
を記憶部１０ａに出力して格納する（ステップＳ１１９）。なお、第２実施形態では、γは排他的論理和値ｒとクリアメッセージｍｃｌｒとビット長Ｎとのみに依存する値γ＝（ｒ，ｍｃｌｒ，Ｎ）である。本形態のγの構成方法に限定はないが、γの構成方法は後述する署名検証装置１２０でのγ’の構成方法と同一とする。本形態のγの構成例としては以下のようなものがある。
〔γ−１〕最上位Ｌ＋Ｍビットをｒとし、その後に続くＮビットをｍｃｌｒとし、さらにその後に続くＬビットをＮとして結合した２Ｌ＋Ｍ＋Ｎビットの値をγとする。
〔γ−２〕最上位ＬビットをＮとし、その後に続くＬ＋Ｍビットをｒとし、さらにその後に続くＮビットをｍｃｌｒとして結合した２Ｌ＋Ｍ＋Ｎビットの値をγとする。
〔γ−３〕所定の規則に従い、Ｎやｒやｍｃｌｒのビットをそれぞれ離散的（例えば、Ｎを偶数番目のビットに離散的に配置する等）に結合したものをγとする。
次に、第１実施形態と同様、整数演算部１０ｑが、式（９）に従ってｓを算出し（ステップＳ１２０）、通信部１０ｒに、排他的論理和値ｒと演算結果ｓとクリアメッセージｍｃｌｒとが読み込まれ、通信部１０ｒが、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとをネットワーク４０を通じて署名検証装置１２０に送信する（ステップＳ１２１）。
【００６３】
［署名検証処理］
次に、第２実施形態の署名検証処理について説明する。
【００６４】
図１３は、第２実施形態の署名検証処理を説明するためのフローチャートである。以下、図１３に従って本形態の署名検証処理を説明する。
まず、署名検証装置１２０（図１１）の通信部２０ｂが、署名σ’＝（ｒ’，ｓ’）とクリアメッセージｍｃｌｒ’とを受信し（「入力を受け付け」に相当）、これらを記憶部２０ａに格納する（ステップＳ１４１）。なお、署名とリアメッセージとが正規なものであれば、σ’＝（ｒ’，ｓ’）＝σ＝（ｒ，ｓ）であり、ｍｃｌｒ’＝ｍｃｌｒであるが、ここでは、検証対象の署名をσ’＝（ｒ’，ｓ’）と表現し、検証対象のクリアメッセージをｍｃｌｒ’と表現する。
次に、ビット長抽出部１２０ｃが、記憶部２０ａから、ビット長パラメータＬと署名σ’＝（ｒ’，ｓ’）のｒ’とクリアメッセージをｍｃｌｒ’とを読み込み、式（１０）に従ってリカバリメッセージｍｒｅｃ’のビット長Ｍ’を算出し、さらに、クリアメッセージをｍｃｌｒ’のビット長
N'=|mclr'| …(18)
を算出し、これらを記憶部２０ａに格納する（ステップＳ１４２）。
【００６５】
次に、ハッシュ演算部１２０ｄが、記憶部２０ａからｒ’とクリアメッセージをｍｃｌｒ’とｑとビット長Ｎ’とを読み込む。ハッシュ演算部１２０ｄは、署名生成装置１１０と同一のハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、ｒ’とｍｃｌｒ’とビット長Ｎ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値
t’=H3(γ’)  …(19)
を記憶部２０ａに出力して格納する（ステップＳ１４３）。なお、γ’の構成方法は前述した署名生成装置１１０でのγの構成方法と同一（ｒ＝ｒ’とし、ｍｃｌｒ＝ｍｃｌｒ’とした場合に同一）とする。
次に、群演算部２０ｅが、記憶部２０ａから、生成元ｇ∈Ｇと署名生成装置１０の公開鍵ｙ∈Ｇと署名σ’のｓ’とハッシュ値ｔ’とを読み込み、第１実施形態と同様、式（１２）の演算を行い、その演算結果Ｒ’を記憶部２０ａに出力して格納する（ステップＳ１４４）。
【００６６】
次に、ハッシュ演算部１２０ｆが、記憶部２０ａから演算結果Ｒ’∈Ｇとリカバリメッセージｍｒｅｃ’のビット長Ｍ’とクリアメッセージをｍｃｌｒ’のビット長Ｎ’とビット長パラメータＬを読み込む。ハッシュ演算部１２０ｆは、署名生成装置１１０と同じハッシュ関数Ｈ０を演算結果Ｒ’とビット長Ｍ’とに依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値
Π'=H0(β’)∈{0,1}L+M'  …(20)
を記憶部２０ａに出力して格納する（ステップＳ１４５）。なお、β’の構成方法は、前述した署名生成装置１１０でのβの構成方法と同一とし、また、Ｈ０（β'）の演算は、署名生成装置１１０の場合のＨ０（β'）の演算と同一（β＝β'，Ｍ＝Ｍ’の場合に同一）とする。
その後、第１実施形態のステップＳ４６〜Ｓ５２と同じ処理が実行され（１４６〜Ｓ１５２）、署名検証が行われる。
【００６７】
〔第３実施形態〕
次に、第３実施形態について説明する。第３実施形態は、第３の本発明に係る実施形態である。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
＜全体構成＞
署名生成装置１０が署名生成装置２１０となり、署名検証装置２０が署名検証装置２２０となる以外は、第１実施形態と同じである。
【００６８】
＜署名生成装置２１０の構成＞
［ハードウェア構成］
図２に示した署名生成装置１０のハードウェア構成と同様である。
［ハードウェアとプログラムとの協働］
第１実施形態と同様、本形態の署名生成装置２１０も図２に示したようなコンピュータに所定のプログラムが読み込まれることにより構成される。
図１４は、ＣＰＵにプログラムが読み込まれることにより構成される第３実施形態の署名生成装置２１０の機能構成を例示したブロック図である。なお、図１４における矢印はデータの流れを示すが、一時メモリ１０ｔや制御部１０ｓに入出力されるデータの流れは省略してある。
【００６９】
図１４に示すように、本形態の署名生成装置２１０は、記憶部１０ａと、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、入力部１０ｄと、メッセージ分割部１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部２１０ｈ，２１０ｉ，２１０ｐと、ビット結合部１０ｍと、排他的論理和演算部１０ｎと、整数演算部１０ｑと、通信部１０ｒと、制御部１０ｓと、一時メモリ１０ｔとを有する。なお、ハッシュ演算部２１０ｈの機能構成は、前述したハッシュ演算部１０ｈの機能構成と同様である。なお、ハッシュ演算部２１０ｈ，２１０ｉ，２１０ｐは、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名生成装置２１０の機能をコンピュータに実行させるためのプログラムに相当する。
【００７０】
＜署名検証装置２２０の構成＞
次に、署名検証装置２２０の構成を説明する。
［ハードウェア構成］
図２に示した署名生成装置１０のハードウェア構成と同様である。
［ハードウェアとプログラムとの協働］
署名検証装置２２０も図２に示したようなコンピュータに所定のプログラムが読み込まれることにより構成される。図１５は、このように構成される第３実施形態の署名検証装置２２０の機能構成を例示したブロック図である。なお、図１５における矢印はデータの流れを示すが、一時メモリ２０ｐや制御部２０ｎに入出力されるデータの流れは省略してある。
図１５に示すように、本形態の署名検証装置２２０は、記憶部２０ａと、通信部２０ｂと、ビット長抽出部２０ｃと、ハッシュ演算部２２０ｄ，２２０ｆ，２２０ｋと、群演算部２０ｅと、排他的論理和演算部２０ｇと、ビット抽出部２０ｈと、比較部２２０ｉと、出力部２０ｍと、制御部２０ｎと、一時メモリ２０ｐとを有する。
【００７１】
なお、ハッシュ演算部２２０ｄ，２２０ｆ，２２０ｋは、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名検証装置２２０の機能をコンピュータに実行させるためのプログラムに相当する。
【００７２】
＜処理＞
次に、本形態の処理について説明する。
［前処理］
まず、署名システム１で使用する位数ｑの離散対数問題の求解が困難な巡回群Ｇとその生成元ｇ∈Ｇとを決定する。このような巡回群Ｇとしては、例えば、楕円曲線上の有理点のなす群や有限体の乗法群などを用いることができる。なお、安全性の面から位数ｑは素数であることが望ましいが、ｑの素因数分解が困難であるならｑは素数でなくてもかまわない。また、署名システム１で使用するビット長パラメータＬ∈Ｚ＞0（０より大きな整数）を決定する。
さらに、後述するリカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビットに定まる出力が可変長のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを決定する。なお、このようなハッシュ関数の演算方法については後述する。
また、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌと、また、入力値に対してＺｑ（ｑを法とする完全剰余系）の元を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑとを決定する。ハッシュ関数Ｈ１は、ハッシュ関数Ｈ０と同様に構成でき、ハッシュ関数Ｈ３は、ＳＨＡ−１等のハッシュ値に対し、ｑを法とした剰余演算を行うことで構成できる。
【００７３】
以上のように決定された巡回群Ｇや各ハッシュ関数Ｈ０，Ｈ１，Ｈ３を特定する情報は、例えば、署名生成装置２１０や署名検証装置２２０を構成する各プログラムに書き込まれ、署名生成装置２１０や署名検証装置２２０は、決定された巡回群Ｇでの演算や、各ハッシュ関数Ｈ０，Ｈ１，Ｈ３の演算が可能になるものとする。また、ビット長パラメータＬ∈Ｚ＞0や位数ｑや生成元ｇ∈Ｇは、署名生成装置２１０の記憶部１０ａと署名検証装置２２０の記憶部２０ａに格納される。
【００７４】
［鍵生成処理］
次に、署名生成装置２１０が行う鍵生成処理について説明する。
まず、署名生成装置２１０の秘密鍵生成部１０ｂが任意の秘密鍵ｘ∈Ｚｑを生成する。なお、この秘密鍵ｘの生成は、擬似乱数をＺｑにマッピングして行ってもよいし、署名生成者によって任意に決定された値を元に行ってもよい。生成された秘密鍵ｘは、署名生成装置２１０の記憶部１０ａに安全に格納される。すなわち、署名生成装置２１０の外部の装置は、記憶部１０ａから秘密鍵ｘを取得することができない。
次に、署名生成装置２１０の公開鍵生成部１０ｃが、記憶部１０ａから秘密鍵ｘと巡回群Ｇの生成元ｇ∈Ｇとを読み込み、巡回群Ｇで定義された演算
y=gx∈G  …(21)
を行って秘密鍵ｘに対応する公開鍵ｙ∈Ｇを生成し、記憶部１０ａに格納する。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（２１）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｘ倍）する演算（ｘ・ｇ∈Ｅ）を意味し、公開鍵ｙは楕円曲線Ｅ上の点となる。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（２１）の右辺は、ｇｘｍｏｄ ｐ（ただし、ｐ＝２ｑ＋１）の演算を意味し、公開鍵ｙはスカラー値となる。生成された公開鍵ｙは、通信部１０ｒからネットワーク４０を通じて公開鍵サーバ装置３０に送信され、公開鍵サーバ装置３０は、送信された公開鍵ｙを例えば公開鍵証明書とともに公開する。なお、公開鍵ｙ等の公開とは、公開鍵ｙ等が公開鍵サーバ装置３０の記憶部に格納され、ネットワーク４０に接続可能な任意の装置が公開鍵サーバ装置３０の記憶部に格納された公開鍵ｙ等を取得可能な状態とすることを意味する。署名検証装置２２０は、このような公開鍵ｙを通信部２０ｂによって公開鍵サーバ装置３０から受信し、記憶部２０ａに格納する。
【００７５】
［署名生成処理］
次に、第３実施形態の署名生成処理について説明する。
図１６は、第３実施形態の署名生成処理を説明するためのフローチャートである。以下、図１６に従って本形態の署名生成処理を説明する。
まず、署名生成装置２１０（図１４）の入力部１０ｄに、メッセージｍ∈｛０，１｝Ｎ＋Ｍとリカバリメッセージのビット長Ｍ≧１とが入力される（ステップＳ２１１）。入力されたこれらの情報は、それぞれ記憶部１０ａに格納される。
次に、メッセージ分割部１０ｅが、記憶部１０ａからメッセージｍ∈｛０，１｝Ｎ＋Ｍとリカバリメッセージのビット長Ｍ≧１とを読み込む。メッセージ分割部１０ｅは、これらの情報を用い、
メッセージｍ∈｛０，１｝Ｎ＋Ｍを、ビット長Ｍのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍ  と、ビット長Ｎ（Ｎ≧０）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとに分割する（ステップＳ２１２）。例えば、メッセージｍ∈｛０，１｝Ｎ＋Ｍの上位Ｍビットをリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍとし、下位Ｎビットをクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとする。なお、分割法はこれに限定されず、メッセージｍ∈｛０，１｝Ｎ＋Ｍのどのビットをリカバリメッセージｍｒｅｃとし、どのビットをクリアメッセージｍｃｌｒとするかは、任意に設定できる。このように分割されたビット長Ｍのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍ  と、ビット長Ｎのクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとは、それぞれ記憶部１０ａに格納される。
【００７６】
次に、任意値生成部１０ｆが任意値ｋ∈Ｚｑを生成し、生成した任意値ｋを記憶部１０ａに格納する（ステップＳ２１３）。なお、任意値ｋの生成は、例えば、擬似乱数をＺｑにマッピングすることにより行う。
次に、群演算部１０ｇが、記憶部１０ａから生成元ｇ∈Ｇと任意値ｋ∈Ｚｑとを読み込み、
R=gk∈G  …(22)
を算出し、当該演算結果Ｒ∈Ｇを記憶部１０ａに出力して格納する（ステップＳ２１４）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（２２）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｋ倍）する演算（ｋ・ｇ∈Ｅ）を意味し、演算結果Ｒは楕円曲線Ｅ上の点となる。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（２２）の右辺は、ｇｋｍｏｄ ｐの演算を意味し、演算結果Ｒはスカラー値となる。
次に、ハッシュ演算部２１０ｈが、記憶部１０ａから演算結果Ｒ∈Ｇとリカバリメッセージのビット長Ｍとビット長パラメータＬを読み込む。ハッシュ演算部２１０ｈは、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビットに定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒに依存して定まる値β（本形態ではβ＝Ｒ）に作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値
Π=H0(β)∈{0,1}L+M  …(23)
を記憶部１０ａに出力して格納する（ステップＳ２１５）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（２３）の右辺は、楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値（例えば、点Ｒのｘ座標若しくはｙ座標、又は、点Ｒのｘ座標とｙ座標とのビット結合値）にハッシュ関数Ｈ０を作用させる演算を意味する。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（２３）の右辺は、スカラー値である演算結果Ｒにハッシュ関数Ｈ０を作用させる演算を意味する。ハッシュ関数Ｈ０を作用させる演算の具体的な処理方法は、例えば、第１実施形態の図７と同様である。
【００７７】
ステップＳ２１５の後、ハッシュ演算部２１０ｉが、記憶部１０ａからリカバリメッセージｍｒｅｃとビット長パラメータＬとを読み込む。ハッシュ演算部２１０ｉは、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、リカバリメッセージｍｒｅｃに依存して定まる値α（本形態ではα＝ｍｒｅｃ）に作用させ、その演算結果であるＬビットのハッシュ値
h=H1(α)∈{0,1}L  …(24)
を記憶部１０ａに出力して格納する（ステップＳ２１６）。
次に、ビット結合部１０ｍが、記憶部１０ａからハッシュ値ｈ∈｛０，１｝Ｌとリカバリメッセージｍｒｅｃとを読み込む。ビット結合部１０ｍは、ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値
d=h|mrec∈{0,1}L+M  …(25)
を算出し、当該ビット結合値ｄを記憶部１０ａに出力して格納する（ステップＳ２１７）。なお、「第１ビット位置」及び「第２ビット位置」をどのビット位置にするかについて特に限定はない。しかし、署名生成装置２１０と署名検証装置２２０との間では、「第１ビット位置」及び「第２ビット位置」をどのビット位置にするかの基準を同一にしなければならない。「第１ビット位置」及び「第２ビット位置」の設定例は、例えば図９に示した通りである。
【００７８】
次に、排他的論理和演算部１０ｎが、記憶部１０ａからハッシュ値Πとビット結合値ｄとを読み込む。排他的論理和演算部１０ｎは、ハッシュ値Πとビット結合値ｄとの排他的論理和
r=Π(+)d∈{0,1}L+M  …(26)
を算出し（（＋）は排他的論理和演算子）、当該排他的論理和値ｒを記憶部１０ａに出力して格納する（ステップＳ２１８）。
次に、ハッシュ演算部２１０ｐが、記憶部１０ａから排他的論理和値ｒとクリアメッセージｍｃｌｒとを読み込む。ハッシュ演算部２１０ｐは、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、排他的論理和値ｒとクリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値
t=H3(γ)∈Zq  …(27)
を記憶部１０ａに出力して格納する（ステップＳ２１９）。なお、第３実施形態では、γは排他的論理和値ｒとクリアメッセージｍｃｌｒとのみに依存する値γ＝（ｒ，ｍｃｌｒ）である。本形態のγの構成方法に限定はないが、γの構成方法は後述する署名検証装置２２０でのγ’の構成方法と同一とする。γの構成例としては以下のようなものがある。
〔γ−１〕ｒを上位Ｌ＋Ｍビットとし、ｍｃｌｒを下位Ｎビットとして結合したＬ＋Ｍ＋Ｎビットの値をγとする。
〔γ−２〕ｒを下位Ｌ＋Ｍビットとし、ｍｃｌｒを上位Ｎビットとして結合したＬ＋Ｍ＋Ｎビットの値をγとする。
〔γ−３〕ｍｃｌｒを上位から奇数番目のビット（合計Ｎビット）とし、ｒをその他のＬ＋Ｍビットとして結合したＬ＋Ｍ＋Ｎビットの値をγとする。
次に、整数演算部１０ｑが、記憶部１０ａから任意値ｋとハッシュ値ｔと秘密鍵ｘとｑとを読み込む。整数演算部１０ｑは、
s=k-t・x∈Zq  …(28)
を算出し、当該演算結果ｓを記憶部１０ａに出力して格納する（ステップＳ２２０）。
次に、通信部１０ｒに、排他的論理和値ｒと演算結果ｓとクリアメッセージｍｃｌｒとが読み込まれ、通信部１０ｒは、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとをネットワーク４０を通じて署名検証装置２２０に送信する（ステップＳ２２１）。
【００７９】
［署名検証処理］
次に、第３実施形態の署名検証処理について説明する。
図１７は、第３実施形態の署名検証処理を説明するためのフローチャートである。以下、図１７に従って本形態の署名検証処理を説明する。
まず、署名検証装置２２０（図１５）の通信部２０ｂが、署名σ’＝（ｒ’，ｓ’）とクリアメッセージｍｃｌｒ’とを受信し（「入力を受け付け」に相当）、これらを記憶部２０ａに格納する（ステップＳ２４１）。なお、署名とリアメッセージとが正規なものであれば、σ’＝（ｒ’，ｓ’）＝σ＝（ｒ，ｓ）であり、ｍｃｌｒ’＝ｍｃｌｒであるが、ここでは、検証対象の署名をσ’＝（ｒ’，ｓ’）と表現し、検証対象のクリアメッセージをｍｃｌｒ’と表現する。
次に、ビット長抽出部２０ｃが、記憶部２０ａから、ビット長パラメータＬと署名σ’＝（ｒ’，ｓ’）のｒ’とを読み込む。ビット長抽出部２０ｃは、
M'=length(r')‐L  …(29)
により、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を算出し、記憶部２０ａに格納する（ステップＳ２４２）。
【００８０】
次に、ハッシュ演算部２２０ｄが、記憶部２０ａからｒ’とクリアメッセージをｍｃｌｒ’とｑとを読み込む。ハッシュ演算部２２０ｄは、署名生成装置２１０と同一のハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、ｒ’とｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値
t’=H3(γ’)  …(30)
を記憶部２０ａに出力して格納する（ステップＳ２４３）。なお、γ’の構成方法は前述した署名生成装置２１０でのγの構成方法と同一（ｒ＝ｒ’とし、ｍｃｌｒ＝ｍｃｌｒ’とした場合に同一）とする。
次に、群演算部２０ｅが、記憶部２０ａから、生成元ｇ∈Ｇと署名生成装置２１０の公開鍵ｙ∈Ｇと署名σ’のｓ’とハッシュ値ｔ’とを読み込み、
R’=gs’・yt’∈G  …(31)
の演算を行い、その演算結果Ｒ’を記憶部２０ａに出力して格納する（ステップＳ２４４）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（３１）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｓ’倍）し、公開鍵ｙ＝（ｙ１，ｙ２）を楕円スカラー倍（楕円ｔ’倍）し、それらの演算結果を楕円加算する演算（ｓ’・ｇ＋ｔ’・ｙ∈Ｅ）を意味し、演算結果Ｒ’は楕円曲線Ｅ上の点となる。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（３１）の右辺は、ｇｓ’・ｙｔ’ｍｏｄ ｐの演算を意味し、演算結果Ｒ’はスカラー値となる。
【００８１】
次に、ハッシュ演算部２２０ｆが、記憶部２０ａから演算結果Ｒ’∈Ｇとリカバリメッセージｍｒｅｃ’のビット長Ｍ’とビット長パラメータＬを読み込む。ハッシュ演算部２２０ｆは、署名生成装置２１０と同じハッシュ関数Ｈ０を演算結果Ｒ’に依存して定まる値β’（この例ではβ’＝Ｒ’）に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値
Π'=H0(β’)∈{0,1}L+M'  …(32)
を記憶部２０ａに出力して格納する（ステップＳ２４５）。なお、Ｈ０（β'）の演算は、署名生成装置２１０の場合のＨ０（β）の演算と同一（β＝β’，Ｍ＝Ｍ’の場合に同一）とする。
次に、排他的論理和演算部２０ｇが、記憶部２０ａから、ハッシュ値Π’と署名σ’が有するｒ’とを読み込み、それらの排他的論理和
d’=Π’(+)r’∈{0,1}Ｌ＋Ｍ’  …(33)
を算出し、当該排他的論理和値ｄ’を記憶部２０ａに出力して格納する（ステップＳ２４６）。
【００８２】
次に、ビット抽出部２０ｈが、記憶部２０ａから排他的論理和値ｄ’とリカバリメッセージｍｒｅｃ’のビット長Ｍ’とを読み込む。ビット抽出部２０ｈは、排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｍｒｅｃ’∈｛０，１｝Ｍ’とを抽出し、それらを記憶部２０ａに格納する（ステップＳ２４７）。なお、「第１ビット位置」及び「第２ビット位置」は、署名生成装置２１０の処理での「第１ビット位置」及び「第２ビット位置」と同一（ｄ＝ｄ’とした場合に同一）とする。
次に、ハッシュ演算部２２０ｋが、記憶部２０ａからリカバリメッセージｍｒｅｃ’を読み込む。ハッシュ演算部２２０ｋは、署名生成装置２１０と同一のハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、リカバリメッセージｍｒｅｃ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値
H1(α’)∈{0,1}L  …(34)
を記憶部２０ａに出力して格納する（ステップＳ２４８）。なお、α’の構成方法は前述した署名生成装置２１０でのαの構成方法と同一（ｍｒｅｃ＝ｍｒｅｃ’とした場合に同一）とする。
【００８３】
次に、比較部２０ｉが、記憶部２０ａからハッシュ値Ｈ１（α’）と値ｈ’とを読み込み、
h'=H1(α’)   …(35)
を満たすか否かを判断する（ステップＳ２４９）。
ここで、式（３５）を満たさない場合、比較部２０ｉは０（検証失敗）を記憶部２０ａに出力して格納し、出力部２０ｍは、記憶部２０ａから送られた０（検証失敗）を出力する（ステップＳ２５０）。一方、式（３５）を満たす場合、比較部２０ｉは１（検証成功）を記憶部２０ａに出力して格納し、出力部２０ｍは、記憶部２０ａから送られた１（検証成功）を出力し（ステップＳ２５１）、さらにリカバリメッセージｍｒｅｃ’を出力する（ステップＳ２５２）。
【００８４】
〔第４実施形態〕
次に、第４実施形態について説明する。第４実施形態は、第４の本発明に係る実施形態である。
第３実施形態では、リカバリメッセージｍｒｅｃに依存して定まる値をαとし、リカバリメッセージｍｒｅｃ’に依存して定まる値をα’とした。第４実施形態では、クリアメッセージｍｃｌｒに依存して定まる値をαとし、クリアメッセージｍｃｌｒ’に依存して定まる値をα’とする。以下では、第１，３実施形態との相違点を中心に説明する。
＜全体構成＞
署名生成装置１０が署名生成装置３１０となり、署名検証装置２０が署名検証装置３２０となる以外は、第１実施形態と同じである。
【００８５】
＜署名生成装置３１０の構成＞
［ハードウェア構成］
図２に示した署名生成装置１０のハードウェア構成と同様である。
［ハードウェアとプログラムとの協働］
第１実施形態と同様、本形態の署名生成装置３１０も図２に示したようなコンピュータに所定のプログラムが読み込まれることにより構成される。
図１８は、ＣＰＵにプログラムが読み込まれることにより構成される第４実施形態の署名生成装置３１０の機能構成を例示したブロック図である。
図１８に示すように、本形態の署名生成装置３１０は、記憶部１０ａと、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、入力部１０ｄと、メッセージ分割部１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部２１０ｈ，３１０ｉ，２１０ｐと、ビット結合部１０ｍと、排他的論理和演算部１０ｎと、整数演算部１０ｑと、通信部１０ｒと、制御部１０ｓと、一時メモリ１０ｔとを有する。なお、ハッシュ演算部３１０ｉは、その処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。
【００８６】
＜署名検証装置３２０の構成＞
次に、署名検証装置３２０の構成を説明する。
［ハードウェア構成］
図２に示した署名生成装置１０のハードウェア構成と同様である。
［ハードウェアとプログラムとの協働］
署名検証装置３２０も図２に示したようなコンピュータに所定のプログラムが読み込まれることにより構成される。図１９は、このように構成される第４実施形態の署名検証装置３２０の機能構成を例示したブロック図である。
図１９に示すように、本形態の署名検証装置３２０は、記憶部２０ａと、通信部２０ｂと、ビット長抽出部２０ｃと、ハッシュ演算部２２０ｄ，２２０ｆ，３２０ｋと、群演算部２０ｅと、排他的論理和演算部２０ｇと、ビット抽出部２０ｈと、比較部２２０ｉと、出力部２０ｍと、制御部２０ｎと、一時メモリ２０ｐとを有する。なお、ハッシュ演算部３２０ｋは、その処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。
【００８７】
＜処理＞
次に、本形態の処理について説明する。
［前処理］
第３実施形態と同じである。
［鍵生成処理］
第３実施形態と同じである。
［署名生成処理］
次に、第４実施形態の署名生成処理について説明する。
図２０は、第４実施形態の署名生成処理を説明するためのフローチャートである。以下、図２０に従って本形態の署名生成処理を説明する。
まず、署名生成装置３１０（図１８）が、第３実施形態のステップＳ２１１〜Ｓ２１５と同様の処理を実行する（ステップＳ３１１〜Ｓ３１５）。
ステップＳ３１５の後、ハッシュ演算部３１０ｉが、記憶部１０ａからクリアメッセージｍｃｌｒとビット長パラメータＬとを読み込む。ハッシュ演算部３１０ｉは、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、クリアメッセージｍｃｌｒに依存して定まる値α（本形態ではα＝ｍｃｌｒ）に作用させ、その演算結果であるＬビットのハッシュ値
h=H1(α)∈{0,1}L  …(36)
を記憶部１０ａに出力して格納する（ステップＳ３１６）。
その後、署名生成装置３１０は、第３実施形態のステップＳ２１７〜Ｓ２２１と同様な処理を実行する（ステップＳ３１７〜Ｓ３２１）。
【００８８】
［署名検証処理］
次に、第４実施形態の署名検証処理について説明する。
図２１は、第４実施形態の署名検証処理を説明するためのフローチャートである。以下、図２１に従って本形態の署名検証処理を説明する。
まず、署名検証装置３２０（図１９）が、第３実施形態のステップＳ２４１〜Ｓ２４７と同様な処理を実行する（ステップＳ３４１〜Ｓ３４７）。
その後、ハッシュ演算部３２０ｋが、記憶部２０ａからクリアメッセージｍｃｌｒ’を読み込む。ハッシュ演算部３２０ｋは、署名生成装置３１０と同一のハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、クリアメッセージｍｃｌｒ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値
H1(α’)∈{0,1}L  …(37)
を記憶部２０ａに出力して格納する（ステップＳ４４８）。なお、α’の構成方法は前述した署名生成装置３１０でのαの構成方法と同一（ｍｒｅｃ＝ｍｒｅｃ’とした場合に同一）とする。
その後、署名検証装置３２０は、第３実施形態のステップＳ２４９〜Ｓ２５２と同様な処理を実行して署名検証を行う（ステップＳ３４９〜Ｓ３５２）。
【００８９】
〔変形例〕
なお、本発明は上述の各実施形態に限定されるものではない。以下に各実施形態の変形例を示す。
第１実施形態では、βをＲとＭとに依存して定まる値（Ｒ，Ｍ）とし、β’をＲ’とＭ’とに依存して定まる値（Ｒ’，Ｍ’）とし、γをｒとｍｃｌｒとＭとに依存して定まる値（ｒ，ｍｃｌｒ，Ｍ）とし、γ’をｒ’とｍｃｌｒ’とＭ’とに依存して定まる値（ｒ’，ｍｃｌｒ’，Ｍ’）とした。しかし、第１実施形態の変形として、β，γの一方（β’，γ’の一方）のみがＭ（Ｍ’）に依存して定まる構成であってもよい。
また、第２実施形態では、βをＲとＮとに依存して定まる値（Ｒ，Ｎ）とし、β’をＲ’とＮ’とに依存して定まる値（Ｒ’，Ｎ’）とし、γをｒとｍｃｌｒとＮとに依存して定まる値（ｒ，ｍｃｌｒ，Ｎ）とし、γ’をｒ’とｍｃｌｒ’とＮ’とに依存して定まる値（ｒ’，ｍｃｌｒ’，Ｎ’）とした。しかし、第２実施形態の変形として、β，γの一方（β’，γ’の一方）のみがＮ（Ｎ’）に依存して定まる構成であってもよい。
【００９０】
また、第１，２実施形態の変形として、βとβ’とがさらに共通する付加情報に依存して定まる値であってもよく、γとγ’とがさらに共通する付加情報に依存して定まる値であってもよい。なお「付加情報」としては、リカバリメッセージのビット長や、クリアメッセージや、クリアメッセージのビット長や、公開鍵ｙや、群Ｇを特定するためのパラメータ、或いは、それらの少なくとも一部のビット結合値などを例示できる。これにより、署名検証精度をより向上させることができる。特に、付加情報として群Ｇを特定するためのパラメータを用いた場合には、不正な群（例えば、離散対数問題が容易であって群演算部での演算結果が正規の巡回群Ｇでの演算結果と同一となる群）を用いて生成された不正な署名が検証に合格してしまうことを防止できる。
また、第３実施形態では、α＝ｍｒｅｃとし、α’＝ｍｒｅｃ’とした。しかし、αをΠとｍｒｅｃとのみに依存する値（Π，ｍｒｅｃ）とし、α’をΠ’とｍｒｅｃ’とのみに依存する値（Π’，ｍｒｅｃ’）としてもよい。その他、αをｍｒｅｃと「付加情報」とに依存する値とし、α’をｍｒｅｃ’と「付加情報」とに依存する値としてもよい。
また、第４実施形態では、α＝ｍｃｌｒとし、α’＝ｍｃｌｒ’とした。しかし、αをΠとｍｃｌｒとのみに依存する値（Π，ｍｃｌｒ）とし、α’をΠ’とｍｃｌｒ’とのみに依存する値（Π’，ｍｃｌｒ’）としてもよい。その他、αをｍｃｌｒと「付加情報」とに依存する値とし、α’をｍｃｌｒ’と「付加情報」とに依存する値としてもよい。
【００９１】
また、第３，４実施形態では、β＝Ｒとし、β’＝Ｒ’とした。しかし、βをＲとリカバリメッセージｍｒｅｃのビット長Ｍとのみに依存する情報（Ｒ，Ｍ）とし、β’をＲ’とリカバリメッセージｍｒｅｃ’のビット長Ｍ’とのみに依存する情報（Ｒ’，Ｍ’）としてもよい。また、βをＲとクリアメッセージｍｃｌｒのビット長Ｎとのみに依存する情報（Ｒ，Ｎ）とし、β’をＲ’とクリアメッセージｍｃｌｒ’のビット長Ｎ’とのみに依存する情報（Ｒ’，Ｎ’）としてもよい。その他、βをＲと「付加情報」とに依存する値とし、β’をＲ’と「付加情報」とに依存する値としてもよい。
また、第３，４実施形態では、γをｒとｍｃｌｒとのみに依存して定まる値（ｒ，ｍｃｌｒ）とし、γ’をｒ’とｍｃｌｒ’とのみに依存して定まる値（ｒ’，ｍｃｌｒ’）とした。しかし、γをｒとｍｃｌｒとＭとのみに依存して定まる値（ｒ，ｍｃｌｒ，Ｍ）とし、γ’をｒ’とｍｃｌｒ’ とＭ’とのみに依存して定まる値（ｒ’，ｍｃｌｒ’ ，Ｍ’）としてもよい。γをｒとｍｃｌｒとＮとのみに依存して定まる値（ｒ，ｍｃｌｒ，Ｎ）とし、γ’をｒ’とｍｃｌｒ’ とＮ’とのみに依存して定まる値（ｒ’，ｍｃｌｒ’ ，Ｎ’）としてもよい。その他、γをｒとｍｃｌｒと「付加情報」とに依存して定まる値とし、γ’をｒ’とｍｃｌｒ’ と「付加情報」とに依存して定まる値としてもよい。
【００９２】
また、各実施形態では、署名生成装置１０〜３１０が鍵生成を行ったが、別の装置が鍵生成を行ってもよい。また、各実施形態では、公開鍵サーバ装置３０が公開鍵ｙを公開したが署名生成装置１０〜３１０が署名検証装置２０〜３２０に公開鍵ｙを送信する構成であってもよい。また、各処理におけるＺｑ（ｑを法とする完全剰余系）をＺ（整数）に置換した構成であってもよい。
また、第３，４実施形態では、署名検証装置２２０，３２０が、署名σ’が具備するｒ’のビット長とビット長パラメータＬとからリカバリメッセージのビット長を算出したが、署名生成装置２１０，３１０が署名検証装置２２０，３２０にリカバリメッセージのビット長を送信する構成であってもよい。
また、上記各実施形態では、リカバリメッセージのビット長Ｍを可変とし、署名生成装置１０〜３１０の入力部１０ｄにリカバリメッセージのビット長Ｍを入力する構成であった。しかし、リカバリメッセージのビット長Ｍを固定にしてもよい。この場合、署名生成装置１０〜３１０と署名検証装置２０〜３２０との間で、ビット長Ｍを共有する構成であってもよい。
また、ハッシュ関数とは、あるデータに対し、そのデータを代表する値を算出する関数を意味する。本発明では、ＳＨＡ−１やＭＤ５等のみならず、例えば、ＤＥＳやＣａｍｅｌｌｉａなどの共通鍵暗号関数に共通鍵を代入したものをハッシュ関数として用いることもできる。
【００９３】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００９４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態のプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
また、各形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００９５】
本発明は、電子署名を用いる様々な用途に適用可能である。
【図面の簡単な説明】
【００９６】
【図１】図１は、第１実施形態の署名システムの全体構成を示した概念図である。
【図２】図２は、第１実施形態の署名生成装置のハードウェア構成を例示したブロック図である。
【図３】図３は、第１実施形態の署名生成装置の機能構成を例示したブロック図である。
【図４】図４は、第１実施形態のハッシュ演算部の機能構成の詳細を示した図である。
【図５】図５は、第１実施形態の署名検証装置の機能構成を例示したブロック図である。
【図６】図６は、第１実施形態の署名生成処理を説明するためのフローチャートである。
【図７】図７は、ステップＳ１５の処理の例を説明するためのフローチャートである。
【図８】図８は、第１実施形態の署名検証処理を説明するためのフローチャートである。
【図９】図９（ａ）（ｂ）（ｃ）は「第１ビット位置」及び「第２ビット位置」の設定例を示した図である。
【図１０】図１０は、第２実施形態の署名生成装置１の機能構成を例示したブロック図である。
【図１１】図１１は、第２実施形態の署名検証装置の機能構成を例示したブロック図である。
【図１２】図１２は、第２実施形態の署名生成処理を説明するためのフローチャートである。
【図１３】図１３は、第２実施形態の署名検証処理を説明するためのフローチャートである。
【図１４】図１４は、第３実施形態の署名生成装置の機能構成を例示したブロック図である。
【図１５】図１５は、第３実施形態の署名検証装置の機能構成を例示したブロック図である。
【図１６】図１６は、第３実施形態の署名生成処理を説明するためのフローチャートである。
【図１７】図１７は、第３実施形態の署名検証処理を説明するためのフローチャートである。
【図１８】図１８は、第４実施形態の署名生成装置の機能構成を例示したブロック図である。
【図１９】図１９は、第４実施形態の署名検証装置の機能構成を例示したブロック図である。
【図２０】図２０は、第４実施形態の署名生成処理を説明するためのフローチャートである。
【図２１】図２１は、第４実施形態の署名検証処理を説明するためのフローチャートである。
【符号の説明】
【００９７】
１  署名システム
１０〜３１０  署名生成装置
２０〜３２０  署名検証装置
【図１】
2008113315.tif 000003
【図２】
2008113315.tif 000004
【図３】
2008113315.tif 000005
【図４】
2008113315.tif 000006
【図５】
2008113315.tif 000007
【図６】
2008113315.tif 000008
【図７】
2008113315.tif 000009
【図８】
2008113315.tif 000010
【図９】
2008113315.tif 000011
【図１０】
2008113315.tif 000012
【図１１】
2008113315.tif 000013
【図１２】
2008113315.tif 000014
【図１３】
2008113315.tif 000015
【図１４】
2008113315.tif 000016
【図１５】
2008113315.tif 000017
【図１６】
2008113315.tif 000018
【図１７】
2008113315.tif 000019
【図１８】
2008113315.tif 000020
【図１９】
2008113315.tif 000021
【図２０】
2008113315.tif 000022
【図２１】
2008113315.tif 000023