【手続補正書】
【提出日】平成22年11月30日(2010.11.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
署名生成を行う署名生成装置であって、
整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとした場合における、
整数の任意値ｋを選択する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得る群演算部と、
入力値に対してＬビット（Ｌは署名検証装置と共有される正の整数）のハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒとリカバリメッセージｍｒｅｃとに対応する値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得る第２ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記演算結果Ｒと上記ハッシュ値ｈとに対応する値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得る第３ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和をｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）とし、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｒ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｒを得るビット結合部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記ビット結合値ｒに対応する値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得る第４ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得る整数演算部と、
署名σ＝（ｒ，ｓ）を出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項２】
署名生成を行う署名生成装置であって、
整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとした場合における、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得る群演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを上記演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを得る第１ハッシュ演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Πとリカバリメッセージｍｒｅｃとに対応する値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得る第２ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記ハッシュ値Πと上記ハッシュ値ｈとに対応する値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得る第３ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを得る第１排他的論理和演算部と、
上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを得るビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを得る第２排他的論理和演算部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記排他的論理和値ｒに対応する値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得る第４ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得る整数演算部と、
署名σ＝（ｒ，ｓ）を出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項３】
請求項１又は２に記載の署名生成装置であって、
Ｎビットのクリアメッセージをｍｃｌｒ∈｛０，１｝Ｎとし、
上記第４ハッシュ演算部は、
上記ハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記ｒと上記クリアメッセージｍｃｌｒとに対応する値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得、
上記署名出力部は、
上記署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する、
ことを特徴とする署名生成装置。
【請求項４】
請求項２に記載の署名生成装置であって、
上記巡回群Ｇの生成元は、楕円曲線Ｅ上の点であり、
上記Ｒ＝ｇｋ∈Ｇは、上記楕円曲線Ｅ上の点ｋ・ｇ∈Ｅであり、
上記ハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを上記演算結果Ｒに作用させる演算は、楕円曲線上の点である上記演算結果Ｒを一義的又は限定的に特定する値に、上記ハッシュ関数Ｈ０を作用させる演算である、
ことを特徴とする署名生成装置。
【請求項５】
請求項１に記載の署名生成装置であって、
上記巡回群Ｇの生成元は、楕円曲線Ｅ上の点であり、
上記Ｒ＝ｇｋ∈Ｇは、上記楕円曲線Ｅ上の点ｋ・ｇ∈Ｅである、
ことを特徴とする署名生成装置。
【請求項６】
請求項１又は２に記載の署名生成装置であって、
上記Ｒ＝ｇｋ∈Ｇは、ｇｘｍｏｄ ｐ（ただし、ｇは２以上の整数，ｐ＝２ｑ＋１）である、
ことを特徴とする署名生成装置。
【請求項７】
署名検証を行う署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとし、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵をｙ＝ｇｘ∈Ｇとした場合における、
署名σ’＝（ｒ’，ｓ’）の入力を受け付ける署名入力部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記署名σ’が有するｒ’に対応する値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを得る第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得る群演算部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記演算結果Ｒ’とｒ’の第１ビット位置のＬビット（Ｌは署名生成装置と共有される正の整数）の値ｈ’∈｛０，１｝Ｌとに対応する値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得る第３ハッシュ演算部と、
上記ｒ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として得る第２排他的論理和演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒ’と上記リカバリメッセージｍｒｅｃ’とに対応する値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得る第４ハッシュ演算部と、
上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較する比較部と、
を有することを特徴とする署名検証装置。
【請求項８】
署名検証を行う署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとし、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵をｙ＝ｇｘ∈Ｇとし、
署名σ’＝（ｒ’，ｓ’）の入力を受け付ける署名入力部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記署名σ’が有するｒ’に対応する値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを得る第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得る群演算部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を上記演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を得る第２ハッシュ演算部と、
上記ハッシュ値Π’と上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を得る第１排他的論理和演算部と、
上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記ハッシュ値Π’と上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに対応する値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得る第３ハッシュ演算部と、
上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’とする第２排他的論理和演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Π’と上記第２排他的論理和演算部で算出された上記リカバリメッセージｍｒｅｃ’とに対応する値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得る第４ハッシュ演算部と、
上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較する比較部と、
を有することを特徴とする署名検証装置。
【請求項９】
請求項７又は８に記載の署名検証装置であって、
上記署名入力部は、
上記署名σ’と上記署名σ’に対応するクリアメッセージｍｃｌｒ’との入力を受け付け、
上記第１ハッシュ演算部は、
上記ハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに対応する値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを得る、
ことを特徴とする署名検証装置。
【請求項１０】
請求項８に記載の署名検証装置であって、
上記巡回群Ｇの生成元は、楕円曲線Ｅ上の点であり、
上記公開鍵ｙ＝ｇｘ∈Ｇは、上記楕円曲線Ｅ上の点ｋ・ｇ∈Ｅであり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、上記楕円曲線Ｅ上の点ｓ’・ｇ＋ｔ’・ｙ∈Ｅであり、
上記ハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を上記演算結果Ｒ’に作用させる演算は、楕円曲線Ｅ上の点である上記演算結果Ｒ’を一義的又は限定的に特定する値に、上記ハッシュ関数Ｈ０を作用させる演算である、
ことを特徴とする署名検証装置。
【請求項１１】
請求項７に記載の署名検証装置であって、
上記巡回群Ｇの生成元は、楕円曲線Ｅ上の点であり、
上記公開鍵ｙ＝ｇｘ∈Ｇは、上記楕円曲線Ｅ上の点ｋ・ｇ∈Ｅであり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、上記楕円曲線Ｅ上の点ｓ’・ｇ＋ｔ’・ｙ∈Ｅである、
ことを特徴とする署名検証装置。
【請求項１２】
請求項７又は８に記載の署名検証装置であって、
上記公開鍵ｙ＝ｇｘ∈Ｇは、ｇｘｍｏｄ ｐ（ただし、ｇは２以上の整数，ｐ＝２ｑ＋１）であり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、ｇｓ’・ｙｔ’ｍｏｄ ｐである、
ことを特徴とする署名検証装置。
【請求項１３】
署名生成装置の署名生成方法であって、
整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとした場合における、
整数の任意値ｋを選択するステップと、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得るステップと、
入力値に対してＬビット（Ｌは署名検証装置と共有される正の整数）のハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒとリカバリメッセージｍｒｅｃとに対応する値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得るステップと、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記演算結果Ｒと上記ハッシュ値ｈとに対応する値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得るステップと、
上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和をｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）とし、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｒ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｒを得るステップと、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記ビット結合値ｒに対応する値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得るステップと、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得るステップと、
署名σ＝（ｒ，ｓ）を出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１４】
署名生成装置の署名生成方法であって、
整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとした場合における、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得るステップと、
第１ハッシュ演算部が、上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを得るステップと、
第２ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Πとリカバリメッセージｍｒｅｃとに対応する値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得るステップと、
第３ハッシュ演算部が、上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記ハッシュ値Πと上記ハッシュ値ｈとに対応する値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得るステップと、
第１排他的論理和演算部が、上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを得るステップと、
ビット結合部が、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを得るステップと、
第２排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを得るステップと、
第４ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記排他的論理和値ｒに対応する値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得るステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得るステップと、
署名出力部が署名σ＝（ｒ，ｓ）を出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１５】
署名検証装置の署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとし、署名生成装置の秘密鍵ｘ∈Ｚ（整数）に対応する公開鍵をｙ＝ｇｘ∈Ｇをとした場合における、
署名σ’＝（ｒ’，ｓ’）の入力を受け付けるステップと、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’に対応する値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚ（整数）を得るステップと、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得るステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記演算結果Ｒ’と上記ｒ’の第１ビット位置のＬビット（Ｌは署名生成装置と共有される正の整数）の値ｈ’∈｛０，１｝Ｌとに対応する値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得るステップと、
上記ｒ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として得るステップと、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒ’と上記リカバリメッセージｍｒｅｃ’とに対応する値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得るステップと、
上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較するステップと、
を有することを特徴とする署名検証方法。
【請求項１６】
署名検証装置の署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとし、署名生成装置の秘密鍵ｘ∈Ｚ（整数）に対応する公開鍵をｙ＝ｇｘ∈Ｇとした場合における、
署名入力部が、署名σ’＝（ｒ’，ｓ’）の入力を受け付けるステップと、
第１ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’に対応する値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得るステップと、
第２ハッシュ演算部が、上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を得るステップと、
第１排他的論理和演算部が、上記ハッシュ値Π’と上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を得るステップと、
第３ハッシュ演算部が、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記ハッシュ値Π’と上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに対応する値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得るステップと、
第２排他的論理和演算部が、上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’とするステップと、
第４ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Π’と上記第２排他的論理和演算部で算出された上記リカバリメッセージｍｒｅｃ’とに対応する値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得るステップと、
比較部が、上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較するステップと、
を有することを特徴とする署名検証方法。
【請求項１７】
請求項１又は２に記載の署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項１８】
請求項７又は８に記載の署名検証装置としてコンピュータを機能させるためのプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
請求項２及び１４の発明では上記課題を解決するために、以下のように署名生成を行う。
まず、整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとする。ここで、リカバリメッセージｍｒｅｃが、署名対象の少なくとも一部となる。そして、署名生成装置の任意値生成部が、整数の任意値ｋを生成し、群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得る。なお、「ｇｋ∈Ｇ」とは、巡回群Ｇをなす演算をｇについてｋ回実行することを意味する（詳細は後述）。次に、署名生成装置の第１ハッシュ演算部が、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを得る。なお、「関数εをδに作用させる」とは、「δ又はδを特定するための値を関数εに代入する」ことを意味する。次に、署名生成装置の第２ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、ハッシュ値Πとリカバリメッセージｍｒｅｃとに対応する値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得る。また、署名生成装置の第３ハッシュ演算部が、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、ハッシュ値Πとハッシュ値ｈとに対応する値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得る。さらに、署名生成装置の第１排他的論理和演算部が、リカバリメッセージｍｒｅｃとハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを得る。またビット結合部が、ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを得る。なお、第１ビット位置は必ずしも連続したＬビットの位置である必要はなく、離散的に配置された合計Ｌビットの位置でもよい。同様に、第２ビット位置も必ずしも連続したＭビットの位置である必要はなく、離散的に配置された合計Ｍビットの位置でもよい。ただし、「第１ビット位置」及び「第２ビット位置」がどのビット位置であるかについては、署名生成装置と署名検証装置とで統一しておく。次に、署名生成装置の第２排他的論理和演算部が、ハッシュ値Πとビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを得る。また署名生成装置の第４ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、排他的論理和値ｒに対応する値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得る。そして、整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得、署名出力部が署名σ＝（ｒ，ｓ）を出力する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
署名生成装置の公開鍵をｙ＝ｇｘ∈Ｇとする。そして、署名検証装置の署名入力部に署名σ’＝（ｒ’，ｓ’）が入力される。また、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’とする。なお、署名検証装置がビット長Ｍ’の値を取得する方法については後述する。そして、署名検証装置の第１ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、署名σ’が有するｒ’に対応する値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを得る。さらに、署名検証装置の群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得る。なお、「ｇｓ’・ｙｔ’∈Ｇ」とは、巡回群Ｇをなす演算をｇについてｓ’回施し、当該演算をｙについてｔ’回施し、それらの各演算結果に対して当該演算を施す演算を意味する（詳細は後述）。次に、署名検証装置の第２ハッシュ演算部が、リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を得る。さらに、署名検証装置の第１排他的論理和演算部が、ハッシュ値Πと署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を得る。また、署名検証装置の第３ハッシュ演算部が、リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、ハッシュ値Π’と排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに対応する値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得る。また、第２排他的論理和演算部が、排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’とハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として得る。さらに、第４ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、ハッシュ値Π’と第２排他的論理和演算部で算出されたリカバリメッセージｍｒｅｃ’とに対応する値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得る。そして、比較部が、Ｌビットの値ｈ’とハッシュ値Ｈ１（α’）とを比較する。