【手続補正書】
【提出日】平成22年2月17日(2010.2.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
署名生成を行う署名生成装置であって、
整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとした場合における、
整数の任意値ｋを選択する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得る群演算部と、
入力値に対してＬビット（Ｌは署名検証装置と共有される正の整数）のハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得る第２ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記演算結果Ｒと上記ハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得る第３ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和をｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）とし、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｒ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｒを得るビット結合部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記ビット結合値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得る第４ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得る整数演算部と、
署名σ＝（ｒ，ｓ）を出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項２】
署名生成を行う署名生成装置であって、
整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとした場合における、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得る群演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを上記演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを得る第１ハッシュ演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Πとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得る第２ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記ハッシュ値Πと上記ハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得る第３ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを得る第１排他的論理和演算部と、
上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを得るビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを得る第２排他的論理和演算部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記排他的論理和値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得る第４ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得る整数演算部と、
署名σ＝（ｒ，ｓ）を出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項３】
請求項１又は２に記載の署名生成装置であって、
Ｎビットのクリアメッセージをｍｃｌｒ∈｛０，１｝Ｎとし、
上記第４ハッシュ演算部は、
上記ハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得、
上記署名出力部は、
上記署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する、
ことを特徴とする署名生成装置。
【請求項４】
請求項２に記載の署名生成装置であって、
上記Ｒ＝ｇｋ∈Ｇは、楕円曲線上の点ｇの楕円スカラー倍（ｋ倍）演算であり、
上記ハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを上記演算結果Ｒに作用させる演算は、楕円曲線上の点である上記演算結果Ｒを一義的又は限定的に特定する値に、上記ハッシュ関数Ｈ０を作用させる演算である、
ことを特徴とする署名生成装置。
【請求項５】
請求項１に記載の署名生成装置であって、
上記Ｒ＝ｇｋ∈Ｇは、楕円曲線上の点ｇの楕円スカラー倍（ｋ倍）演算である、
ことを特徴とする署名生成装置。
【請求項６】
請求項１又は２に記載の署名生成装置であって、
上記Ｒ＝ｇｋ∈Ｇは、ｇｘｍｏｄ ｐ（ただし、ｇは２以上の整数，ｐ＝２ｑ＋１）の演算である、
ことを特徴とする署名生成装置。
【請求項７】
署名検証を行う署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとし、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵をｙ＝ｇｘ∈Ｇとした場合における、
署名σ’＝（ｒ’，ｓ’）の入力を受け付ける署名入力部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを得る第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得る群演算部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記演算結果Ｒ’とｒ’の第１ビット位置のＬビット（Ｌは署名生成装置と共有される正の整数）の値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得る第３ハッシュ演算部と、
上記ｒ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として得る第２排他的論理和演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒ’と上記リカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得る第４ハッシュ演算部と、
上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較する比較部と、
を有することを特徴とする署名検証装置。
【請求項８】
署名検証を行う署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとし、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵をｙ＝ｇｘ∈Ｇとし、
署名σ’＝（ｒ’，ｓ’）の入力を受け付ける署名入力部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを得る第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得る群演算部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を上記演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を得る第２ハッシュ演算部と、
上記ハッシュ値Π’と上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を得る第１排他的論理和演算部と、
上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記ハッシュ値Π’と上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得る第３ハッシュ演算部と、
上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’とする第２排他的論理和演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Π’と上記第２排他的論理和演算部で算出された上記リカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得る第４ハッシュ演算部と、
上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較する比較部と、
を有することを特徴とする署名検証装置。
【請求項９】
請求項７又は８に記載の署名検証装置であって、
上記署名入力部は、
上記署名σ’と上記署名σ’に対応するクリアメッセージｍｃｌｒ’との入力を受け付け、
上記第１ハッシュ演算部は、
上記ハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを得る、
ことを特徴とする署名検証装置。
【請求項１０】
請求項８に記載の署名検証装置であって、
上記公開鍵ｙ＝ｇｘ∈Ｇは、楕円曲線上の点ｇの楕円スカラー倍（ｋ倍）点であり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、楕円曲線上の点ｇを楕円スカラー倍（楕円ｓ’倍）し、上記公開鍵ｙを楕円スカラー倍（楕円ｔ’倍）し、それらの演算結果を楕円加算する演算であり、
上記ハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を上記演算結果Ｒ’に作用させる演算は、楕円曲線Ｅ上の点である上記演算結果Ｒ’を一義的又は限定的に特定する値に、上記ハッシュ関数Ｈ０を作用させる演算である、
ことを特徴とする署名検証装置。
【請求項１１】
請求項７に記載の署名検証装置であって、
上記公開鍵ｙ＝ｇｘ∈Ｇは、楕円曲線上の点ｇの楕円スカラー倍（ｋ倍）点であり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、楕円曲線上の点ｇを楕円スカラー倍（楕円ｓ’倍）し、上記公開鍵ｙを楕円スカラー倍（楕円ｔ’倍）し、それらの演算結果を楕円加算する演算である、
ことを特徴とする署名検証装置。
【請求項１２】
請求項７又は８に記載の署名検証装置であって、
上記公開鍵ｙ＝ｇｘ∈Ｇは、ｇｘｍｏｄ ｐ（ただし、ｇは２以上の整数，ｐ＝２ｑ＋１）であり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、ｇｓ’・ｙｔ’ｍｏｄ ｐの演算である、
ことを特徴とする署名検証装置。
【請求項１３】
署名生成装置の署名生成方法であって、
整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとした場合における、
整数の任意値ｋを選択するステップと、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得るステップと、
入力値に対してＬビット（Ｌは署名検証装置と共有される正の整数）のハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得るステップと、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記演算結果Ｒと上記ハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得るステップと、
上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和をｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）とし、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｒ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｒを得るステップと、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記ビット結合値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得るステップと、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得るステップと、
署名σ＝（ｒ，ｓ）を出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１４】
署名生成装置の署名生成方法であって、
整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとした場合における、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得るステップと、
第１ハッシュ演算部が、上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを得るステップと、
第２ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Πとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得るステップと、
第３ハッシュ演算部が、上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記ハッシュ値Πと上記ハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得るステップと、
第１排他的論理和演算部が、上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを得るステップと、
ビット結合部が、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを得るステップと、
第２排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを得るステップと、
第４ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記排他的論理和値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得るステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得るステップと、
署名出力部が署名σ＝（ｒ，ｓ）を出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１５】
署名検証装置の署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとし、署名生成装置の秘密鍵ｘ∈Ｚ（整数）に対応する公開鍵をｙ＝ｇｘ∈Ｇをとした場合における、
署名σ’＝（ｒ’，ｓ’）の入力を受け付けるステップと、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚ（整数）を得るステップと、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得るステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記演算結果Ｒ’と上記ｒ’の第１ビット位置のＬビット（Ｌは署名生成装置と共有される正の整数）の値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得るステップと、
上記ｒ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として得るステップと、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒ’と上記リカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得るステップと、
上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較するステップと、
を有することを特徴とする署名検証方法。
【請求項１６】
署名検証装置の署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとし、署名生成装置の秘密鍵ｘ∈Ｚ（整数）に対応する公開鍵をｙ＝ｇｘ∈Ｇとした場合における、
署名入力部が、署名σ’＝（ｒ’，ｓ’）の入力を受け付けるステップと、
第１ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得るステップと、
第２ハッシュ演算部が、上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を得るステップと、
第１排他的論理和演算部が、上記ハッシュ値Π’と上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を得るステップと、
第３ハッシュ演算部が、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記ハッシュ値Π’と上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得るステップと、
第２排他的論理和演算部が、上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’とするステップと、
第４ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Π’と上記第２排他的論理和演算部で算出された上記リカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得るステップと、
比較部が、上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較するステップと、
を有することを特徴とする署名検証方法。
【請求項１７】
請求項１又は２に記載の署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項１８】
請求項７又は８に記載の署名検証装置としてコンピュータを機能させるためのプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
この方式では、
メッセージｍ∈｛０，１｝ｋ２
関数Ｆ１：｛０，１｝ｋ２→｛０，１｝ｋ１
関数Ｆ２：｛０，１｝ｋ１→｛０，１｝ｋ２
関数Ｈ：｛０，１｝ｋ１＋ｋ２→｛０，１｝ｋ
Ｅ：有限体Ｆｑ上で定義された楕円曲線
ｐ：楕円曲線Ｅ上の点Ｒに対して楕円スカラー倍値ｐ・Ｒ＝Ｏ（Ｏは無限遠点）を満たす素数
Ｇ１：楕円曲線Ｅ上の位数ｐの部分集合の点
ｗ∈Ｚ／ｐＺ
秘密鍵：ｘ∈Ｚ／ｐＺ
公開鍵：（Ｆｑ，Ｅ，Ｇ１，Ｙ）（Ｙ＝−ｘ・Ｇ１（∈Ｅ））
とする。なお、｛０，１｝δは、２進δ桁のビットデータを示し、｛０，１｝δ→｛０，１｝εは、２進δ桁のビットデータから２進ε桁のビットデータへの写像である関数を示す。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
＜署名生成＞
署名生成は以下のように行う。ただし、Ｒｘは点Ｒ∈Ｅのｘ座標を示し、（＋）は排他的論理和演算子を示す。
m’=F1(m)｜(F2(F1(m))(+)m) …(1)
Rx=(w・G1)x
r=Rx(+)m’ …(2)
c=H(r)
z=w+c・x mod p
署名σ=(r,z)
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
しかし、非特許文献１の方式では、式（１）の（Ｆ２（Ｆ１（ｍ））や式（２）のＲｘのビット長が固定長であり、メッセージｍのビット長も固定長としなければならない。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
請求項２及び１４の発明では上記課題を解決するために、以下のように署名生成を行う。
まず、整数の秘密鍵をｘとし、Ｍビットのリカバリメッセージをｍｒｅｃ∈｛０，１｝Ｍとする。ここで、リカバリメッセージｍｒｅｃが、署名対象の少なくとも一部となる。そして、署名生成装置の任意値生成部が、整数の任意値ｋを生成し、群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを得る。なお、「ｇｋ∈Ｇ」とは、巡回群Ｇをなす演算をｇについてｋ回実行することを意味する（詳細は後述）。次に、署名生成装置の第１ハッシュ演算部が、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを得る。なお、「関数εをδに作用させる」とは、「δ又はδを特定するための値を関数εに代入する」ことを意味する。次に、署名生成装置の第２ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、ハッシュ値Πとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを得る。また、署名生成装置の第３ハッシュ演算部が、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、ハッシュ値Πとハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを得る。さらに、署名生成装置の第１排他的論理和演算部が、リカバリメッセージｍｒｅｃとハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを得る。またビット結合部が、ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを得る。なお、第１ビット位置は必ずしも連続したＬビットの位置である必要はなく、離散的に配置された合計Ｌビットの位置でもよい。同様に、第２ビット位置も必ずしも連続したＭビットの位置である必要はなく、離散的に配置された合計Ｍビットの位置でもよい。ただし、「第１ビット位置」及び「第２ビット位置」がどのビット位置であるかについては、署名生成装置と署名検証装置とで統一しておく。次に、署名生成装置の第２排他的論理和演算部が、ハッシュ値Πとビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを得る。また署名生成装置の第４ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、排他的論理和値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを得る。そして、整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを得、署名出力部が署名σ＝（ｒ，ｓ）を出力する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
請求項８及び１６の発明では、このように生成された署名を、以下のように検証する。なお、署名検証装置が受け取る署名をσ’＝（ｒ’，ｓ’）と表現する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
署名生成装置の公開鍵をｙ＝ｇｘ∈Ｇとする。そして、署名検証装置の署名入力部に署名σ’＝（ｒ’，ｓ’）が入力される。また、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’とする。なお、署名検証装置がビット長Ｍ’の値を取得する方法については後述する。そして、署名検証装置の第１ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを得る。さらに、署名検証装置の群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を得る。なお、「ｇｓ’・ｙｔ’∈Ｇ」とは、巡回群Ｇをなす演算をｇについてｓ’回施し、当該演算をｙについてｔ’回施し、それらの各演算結果に対して当該演算を施す演算を意味する（詳細は後述）。次に、署名検証装置の第２ハッシュ演算部が、リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を得る。さらに、署名検証装置の第１排他的論理和演算部が、ハッシュ値Πと署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を得る。また、署名検証装置の第３ハッシュ演算部が、リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、ハッシュ値Π’と排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を得る。また、第２排他的論理和演算部が、排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’とハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として得る。さらに、第４ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、ハッシュ値Π’と第２排他的論理和演算部で算出されたリカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを得る。そして、比較部が、Ｌビットの値ｈ’とハッシュ値Ｈ１（α’）とを比較する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
また、請求項１，７，１３及び１５の発明でも上記課題を解決できる。
ここで本発明では、リカバリメッセージのビット長に従って出力ビット長が変化するハッシュ関数を用い、処理方法を工夫することにより、リカバリメッセージのビット長が変化しても、各排他的論理和演算の対象となる２つの被演算子のビット長を常に同一とできる。これにより、リカバリメッセージのビット長が短い場合には、それに併せて各演算過程での演算ビット数や署名σを構成するｒのビット数を短くでき、効率的な署名方式が実現できる。同時に、リカバリメッセージのビット長が長くなっても、リカバリメッセージｍｒｅｃの全てのビットを対象としたメッセージ復元署名が生成できる。