【手続補正書】
【提出日】平成21年2月10日(2009.2.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、少なくとも上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し（（＋）は排他的論理和演算子）、当該排他的論理和値ｒを出力する排他的論理和演算部と、
出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第３ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する署名出力部と、を有し、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値である、
ことを特徴とする署名生成装置。
【請求項２】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、少なくとも上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し（（＋）は排他的論理和演算子）、当該排他的論理和値ｒを出力する排他的論理和演算部と、
出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第３ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する署名出力部と、を有し、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値である、
ことを特徴とする署名生成装置。
【請求項３】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、少なくとも上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、少なくとも上記リカバリメッセージｍｒｅｃに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する第２ハッシュ演算部と、
上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し（（＋）は排他的論理和演算子）、当該排他的論理和値ｒを出力する排他的論理和演算部と、
出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第３ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項４】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、少なくとも上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、少なくとも上記クリアメッセージｍｃｌｒに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する第２ハッシュ演算部と、
上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力する排他的論理和演算部と、
出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第３ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項５】
請求項３又は４に記載の署名生成装置であって、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値である、
ことを特徴とする署名生成装置。
【請求項６】
請求項３又は４に記載の署名生成装置であって、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値である、
ことを特徴とする署名生成装置。
【請求項７】
署名検証する署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’との入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを格納する第２記憶部と、
上記署名σ’のｒ’のビット長から値Ｌ（Ｌは署名生成装置と共有される正の整数）を減じた値Ｍ’を、上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’として抽出するビット長抽出部と、
上記ビット長Ｍ’を格納する第３記憶部と、
整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
出力ビット長がＬ＋Ｍ’ビットのハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、少なくとも上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する排他的論理和演算部と、
署名生成装置との共有値ｈ∈｛０，１｝Ｌと、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力する比較部と、を有し、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値である、
ことを特徴とする署名検証装置。
【請求項８】
署名検証する署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’との入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを格納する第２記憶部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を格納する第３記憶部と、
上記クリアメッセージｍｃｌｒ’のビット長Ｎ’を格納する第４記憶部と、
整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、少なくとも上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する排他的論理和演算部と、
署名生成装置との共有値ｈ∈｛０，１｝Ｌと、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力する比較部と、を有し、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値である、
ことを特徴とする署名検証装置。
【請求項９】
署名検証する署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’との入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを格納する第２記憶部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を格納する第３記憶部と、
整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、少なくとも上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する排他的論理和演算部と、
出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、少なくとも上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｍｒｅｃ’∈｛０，１｝Ｍ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する第３ハッシュ演算部と、
上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する比較部と、
を有することを特徴とする署名検証装置。
【請求項１０】
署名検証する署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’との入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを格納する第２記憶部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を格納する第３記憶部と、
整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、少なくとも上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する排他的論理和演算部と、
出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、少なくとも上記クリアメッセージｍｃｌｒ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する第３ハッシュ演算部と、
上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する比較部と、
を有することを特徴とする署名検証装置。
【請求項１１】
請求項９又は１０に記載の署名検証装置であって、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値である、
ことを特徴とする署名検証装置。
【請求項１２】
請求項９又は１０に記載の署名検証装置であって、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値である、
ことを特徴とする署名検証装置。
【請求項１３】
署名生成を行う署名生成方法であって、
整数の秘密鍵ｘを第１記憶部に格納するステップと、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納するステップと、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、少なくとも上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
ビット結合部が、署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が、署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力するステップと、を有し、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃのビット長Ｍに依存して決まる値である、
ことを特徴とする署名生成方法。
【請求項１４】
署名生成を行う署名生成方法であって、
整数の秘密鍵ｘを第１記憶部に格納するステップと、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納するステップと、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、少なくとも上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
ビット結合部が、署名検証装置との共有値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が、署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力するステップと、を有し、
上記値β及び上記値γの少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒのビット長Ｎに依存して決まる値である、
ことを特徴とする署名生成方法。
【請求項１５】
署名生成を行う署名生成方法であって、
整数の秘密鍵ｘを第１記憶部に格納するステップと、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納するステップと、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、少なくとも上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、少なくとも上記リカバリメッセージｍｒｅｃに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力するステップと、
ビット結合部が、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が、署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１６】
署名生成を行う署名生成方法であって、
整数の秘密鍵ｘを第１記憶部に格納するステップと、
Ｍビット（Ｍ≧１）のリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２記憶部に格納するステップと、
Ｎビット（Ｎ≧１）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを第３記憶部に格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、少なくとも上記演算結果Ｒに依存して定まる値βに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（β）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、少なくとも上記クリアメッセージｍｃｌｒに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力するステップと、
ビット結合部が、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｍｒｅｃ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第３ハッシュ演算部が、出力値が整数のハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記排他的論理和値ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が、署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１７】
署名検証する署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とが署名入力部に入力されるステップと、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを第２記憶部に格納するステップと、
ビット長抽出部が、上記署名σ’のｒ’のビット長から値Ｌ（Ｌは署名生成装置と共有される正の整数）を減じた値Ｍ’を、上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’として抽出するステップと、
上記ビット長Ｍ’を第３記憶部に格納するステップと、
第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビットのハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、少なくとも上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
排他的論理和演算部が、上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
比較部が、署名生成装置との共有値ｈ∈｛０，１｝Ｌと、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力するステップと、を有し、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に依存して決まる値である、
ことを特徴とする署名検証方法。
【請求項１８】
署名検証する署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とが署名入力部に入力されるステップと、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを第２記憶部に格納するステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納するステップと、
上記クリアメッセージｍｃｌｒ’のビット長Ｎ’を第４記憶部に格納するステップと、
第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、少なくとも上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
排他的論理和演算部が、上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
比較部が、署名生成装置との共有値ｈ∈｛０，１｝Ｌと、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとを比較し、ｈ’＝ｈであることを条件に、検証が成功である旨の情報を出力するステップと、を有し、
上記値β’及び上記値γ’の少なくとも一方の値は、
さらに、上記クリアメッセージｍｃｌｒ’のビット長Ｎ’に依存して決まる値である、
ことを特徴とする署名検証方法。
【請求項１９】
署名検証する署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とが署名入力部に入力されるステップと、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを第２記憶部に格納するステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納するステップと、
第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、少なくとも上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
排他的論理和演算部が、上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
第３ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、少なくとも上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｍｒｅｃ’∈｛０，１｝Ｍ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力するステップと、
比較部が、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力するステップと、
を有することを特徴とする署名検証方法。
【請求項２０】
署名検証する署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とが署名入力部に入力されるステップと、
上記署名σ’＝（ｒ’，ｓ’）と上記クリアメッセージｍｃｌｒ’とを第２記憶部に格納するステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納するステップと、
第１ハッシュ演算部が、整数のハッシュ値を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、少なくとも上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、少なくとも上記演算結果Ｒ’に依存して定まる値β’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（β’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
排他的論理和演算部が、上記ハッシュ値Π’と、上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
第３ハッシュ演算部が、出力ビット長がＬビットのハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、少なくとも上記クリアメッセージｍｃｌｒ’に依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力するステップと、
比較部が、上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力するステップと、
を有することを特徴とする署名検証方法。
【請求項２１】
請求項１から６の何れかに記載の署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項２２】
請求項７から１２の何れかに記載の署名検証装置としてコンピュータを機能させるためのプログラム。