(57)【要約】【課題】様々なビット長のメッセージに柔軟に対応可能なメッセージ復元署名技術を提供する。【解決手段】ｘを署名生成装置の秘密鍵とし、mrec∈{0,1}Mをリカバリメッセージとし、ｋを任意値とし、ｇを位数ｑの巡回群Ｇの生成元とし、Ｒをgk∈Ｇとし、Ｈ０を出力可変長のハッシュ関数H0:{0,1}*→{0,1}L+Mとし、Ｈ１をハッシュ関数H1:{0,1}*→{0,1}Lとし、Ｈ２を出力可変長のハッシュ関数H2:{0,1}*→{0,1}Mとし、Ｈ３をハッシュ関数H3:{0,1}*→Zqとし、t=H3(γ)とし、s=k-t・x∈Zとし、r=H0(R)(+)(H1(mrec)|(mrec(+)H2(H1(mrec))))とし〔(+)は排他的論理和演算子〕、署名をσ=(r,s)とする。【選択図】図６
2008136193.tif 000002
【特許請求の範囲】
【請求項１】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビットのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを上記演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを出力する第１ハッシュ演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Πとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する第２ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記ハッシュ値Πと上記ハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを出力する第３ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを出力する第１排他的論理和演算部と、
上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するビット結合部と、
上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力する第２排他的論理和演算部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記排他的論理和値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第４ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）を出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項２】
署名生成を行う署名生成装置であって、
整数の秘密鍵ｘを格納する第１記憶部と、
Ｍビットのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納する第２記憶部と、
整数の任意値ｋを生成する任意値生成部と、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する群演算部と、   
入力値に対してＬビット（Ｌは署名検証装置と共有される正の整数）のハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する第２ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記演算結果Ｒと上記ハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを出力する第３ハッシュ演算部と、
上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを出力する第１排他的論理和演算部と、
上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｒ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｒを出力するビット結合部と、 
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記ビット結合値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する第４ハッシュ演算部と、
ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力する整数演算部と、
署名σ＝（ｒ，ｓ）を出力する署名出力部と、
を有することを特徴とする署名生成装置。
【請求項３】
請求項１又は２に記載の署名生成装置であって、
Ｎビットのクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを格納する第３記憶部をさらに有し、
上記第４ハッシュ演算部は、
上記ハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記ｒと上記クリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力し、
上記署名出力部は、
上記署名σ＝（ｒ，ｓ）と上記クリアメッセージｍｃｌｒとを出力する、
ことを特徴とする署名生成装置。
【請求項４】
請求項１に記載の署名生成装置であって、
上記Ｒ＝ｇｋ∈Ｇは、楕円曲線上の点ｇの楕円スカラー倍（ｋ倍）演算であり、
上記ハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを上記演算結果Ｒに作用させる演算は、楕円曲線上の点である上記演算結果Ｒを一義的又は限定的に特定する値に、上記ハッシュ関数Ｈ０を作用させる演算である、
ことを特徴とする署名生成装置。
【請求項５】
請求項２に記載の署名生成装置であって、
上記Ｒ＝ｇｋ∈Ｇは、楕円曲線上の点ｇの楕円スカラー倍（ｋ倍）演算である、
ことを特徴とする署名生成装置。
【請求項６】
請求項１又は２に記載の署名生成装置であって、
上記Ｒ＝ｇｋ∈Ｇは、ｇｘ ｍｏｄ ｐ（ただし、ｇは２以上の整数，ｐ＝２ｑ＋１）の演算である、
ことを特徴とする署名生成装置。
【請求項７】
署名検証を行う署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）の入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）を格納する第２記憶部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を格納する第３記憶部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、
上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を上記演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を出力する第２ハッシュ演算部と、
上記ハッシュ値Π’と上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する第１排他的論理和演算部と、
上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記ハッシュ値Π’と上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を出力する第３ハッシュ演算部と、
上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として出力する第２排他的論理和演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Π’と上記第２排他的論理和演算部で算出された上記リカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する第４ハッシュ演算部と、
上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する比較部と、
を有することを特徴とする署名検証装置。
【請求項８】
署名検証を行う署名検証装置であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚに対応する公開鍵ｙ＝ｇｘ∈Ｇを格納する第１記憶部と、
署名σ’＝（ｒ’，ｓ’）の入力を受け付ける署名入力部と、
上記署名σ’＝（ｒ’，ｓ’）を格納する第２記憶部と、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を格納する第３記憶部と、
入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する第１ハッシュ演算部と、
Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する群演算部と、  
上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記演算結果Ｒ’とｒ’の第１ビット位置のＬビット（Ｌは署名生成装置と共有される正の整数）の値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を出力する第３ハッシュ演算部と、
上記ｒ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として出力する第２排他的論理和演算部と、
入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒ’と上記第２排他的論理和演算部で算出された上記リカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する第４ハッシュ演算部と、
上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する比較部と、
を有することを特徴とする署名検証装置。
【請求項９】
請求項７又は８に記載の署名検証装置であって、
上記署名入力部は、
上記署名σ’と上記署名σ’に対応するクリアメッセージｍｃｌｒ’との入力を受け付け、
当該署名検証装置は、
上記クリアメッセージｍｃｌｒ’を格納する第４記憶部を有し、
上記第１ハッシュ演算部は、
上記ハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’と上記クリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する、
ことを特徴とする署名検証装置。
【請求項１０】
請求項７に記載の署名検証装置であって、
上記公開鍵ｙ＝ｇｘ∈Ｇは、楕円曲線上の点ｇの楕円スカラー倍（ｋ倍）点であり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、楕円曲線上の点ｇを楕円スカラー倍（楕円ｓ’倍）し、上記公開鍵ｙを楕円スカラー倍（楕円ｔ’倍）し、それらの演算結果を楕円加算する演算であり、
上記ハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を上記演算結果Ｒ’に作用させる演算は、楕円曲線Ｅ上の点である上記演算結果Ｒ’を一義的又は限定的に特定する値に、上記ハッシュ関数Ｈ０を作用させる演算である、
ことを特徴とする署名検証装置。
【請求項１１】
請求項８に記載の署名検証装置であって、
上記公開鍵ｙ＝ｇｘ∈Ｇは、楕円曲線上の点ｇの楕円スカラー倍（ｋ倍）点であり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、楕円曲線上の点ｇを楕円スカラー倍（楕円ｓ’倍）し、上記公開鍵ｙを楕円スカラー倍（楕円ｔ’倍）し、それらの演算結果を楕円加算する演算である、
ことを特徴とする署名検証装置。
【請求項１２】
請求項７又は８に記載の署名検証装置であって、
上記公開鍵ｙ＝ｇｘ∈Ｇは、ｇｘ ｍｏｄ ｐ（ただし、ｇは２以上の整数，ｐ＝２ｑ＋１）であり、
上記Ｒ’＝ｇｓ’・ｙｔ’∈Ｇは、ｇｓ’・ｙｔ’ ｍｏｄ ｐの演算をである、
ことを特徴とする署名検証装置。
【請求項１３】
署名生成装置の署名生成方法であって、
第１記憶部に整数の秘密鍵ｘを格納するステップと、
第２記憶部にＭビットのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、
第１ハッシュ演算部が、上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、上記演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを出力するステップと、
第２ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Πとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力するステップと、
第３ハッシュ演算部が、上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記ハッシュ値Πと上記ハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを出力するステップと、
第１排他的論理和演算部が、上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを出力するステップと、
ビット結合部が、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力するステップと、
第２排他的論理和演算部が、上記ハッシュ値Πと上記ビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力するステップと、
第４ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記排他的論理和値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が署名σ＝（ｒ，ｓ）を出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１４】
署名生成装置の署名生成方法であって、
第１記憶部に整数の秘密鍵ｘを格納するステップと、
第２記憶部にＭビットのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを格納するステップと、
任意値生成部が、整数の任意値ｋを生成するステップと、
群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力するステップと、   
第２ハッシュ演算部が、入力値に対してＬビット（Ｌは署名検証装置と共有される正の整数）のハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力するステップと、
第３ハッシュ演算部が、上記リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、上記演算結果Ｒと上記ハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを出力するステップと、
第１排他的論理和演算部が、上記リカバリメッセージｍｒｅｃと上記ハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを出力するステップと、
ビット結合部が、上記ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、上記排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｒ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｒを出力するステップと、
第４ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚ（整数）を、上記ビット結合値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力するステップと、
整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力するステップと、
署名出力部が署名σ＝（ｒ，ｓ）を出力するステップと、
を有することを特徴とする署名生成方法。
【請求項１５】
署名検証装置の署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚ（整数）に対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名入力部が、署名σ’＝（ｒ’，ｓ’）の入力を受け付けるステップと、
第２記憶部に上記署名σ’＝（ｒ’，ｓ’）を格納するステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納するステップと、
第１ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、
第２ハッシュ演算部が、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは署名生成装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、上記演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を出力するステップと、
第１排他的論理和演算部が、上記ハッシュ値Π’と上記署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力するステップと、
第３ハッシュ演算部が、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記ハッシュ値Π’と上記排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を出力するステップと、
第２排他的論理和演算部が、上記排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として出力するステップと、
第４ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記ハッシュ値Π’と上記第２排他的論理和演算部で算出された上記リカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力するステップと、
比較部が、上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力するステップと、
を有することを特徴とする署名検証方法。
【請求項１６】
署名検証装置の署名検証方法であって、
位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合における、署名生成装置の秘密鍵ｘ∈Ｚ（整数）に対応する公開鍵ｙ＝ｇｘ∈Ｇを第１記憶部に格納するステップと、
署名入力部が、署名σ’＝（ｒ’，ｓ’）の入力を受け付けるステップと、
第２記憶部に上記署名σ’＝（ｒ’，ｓ’）を格納するステップと、
上記署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を第３記憶部に格納するステップと、
第１ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、上記署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚ（整数）を出力するステップと、
群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力するステップと、  
第３ハッシュ演算部が、上記リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、上記演算結果Ｒ’と上記ｒ’の第１ビット位置のＬビット（Ｌは署名生成装置と共有される正の整数）の値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を出力するステップと、
第２排他的論理和演算部が、上記ｒ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’と上記ハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として出力するステップと、
第４ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、上記演算結果Ｒ’と上記第２排他的論理和演算部で算出された上記リカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力するステップと、
比較部が、上記Ｌビットの値ｈ’と上記ハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力するステップと、
を有することを特徴とする署名検証方法。
【請求項１７】
請求項１又は２に記載の署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項１８】
請求項７又は８に記載の署名検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に、署名からメッセージが復元できるメッセージ復元署名に関する。
【背景技術】
【０００２】
メッセージ復元署名の従来技術として非特許文献１に示すものがある。この方式は、ランダムオラクルモデルで安全性が証明される方式である。以下にこの方式の概要を示す。
【０００３】
この方式では、
メッセージｍ∈｛０，１｝ｋ１
関数Ｆ１：｛０，１｝ｋ２→｛０，１｝ｋ１
関数Ｆ２：｛０，１｝ｋ１→｛０，１｝ｋ２
関数Ｈ：｛０，１｝ｋ１＋ｋ２→｛０，１｝ｋ
Ｅ：有限体Ｆｑ上で定義された楕円曲線
ｐ：楕円曲線Ｅ上の点Ｒに対して楕円スカラー倍値ｐ・Ｒ＝Ｏ（Ｏは無限遠点）を満たす素数
Ｇ１：楕円曲線Ｅ上の位数ｐの部分集合の点
ｗ∈Ｚ／ｐＺ
秘密鍵：ｘ∈Ｚ／ｐＺ
公開鍵：（Ｆｑ，Ｅ，Ｇ１，Ｙ）（Ｙ＝−ｘ・Ｇ１（∈Ｅ））
とする。なお、｛０，１｝δは、２進δ桁のビットデータを示し、｛０，１｝δ→｛０，１｝εは、２進δ桁のビットデータから２進ε桁のビットデータへの写像である関数を示す。
【０００４】
＜署名生成＞
署名生成は以下のように行う。ただし、Ｒｘは点Ｒ∈Ｅのｘ座標を示し、（＋）は排他的論理和演算子を示す。
m’=F1(m)｜(F2(F1(m))(+)m) …(1)
R=(w・G1)x
r=R(+)m’ …(2)
c=H(r)
z=w+c・x mod p
署名σ=(r,z)
【０００５】
＜署名検証＞
署名検証は以下のように行う。ただし、［ｍ’］ｋ１はｍ’の先頭ｋ１ビットを示し、［ｍ’］ｋ２はｍ’の残りのｋ２ビットを示す。
m’=r(+)(z・G1+H(r)・Y)x
m=[m’]k2(+)F2([m’]k1)
[m’]k1=F1(m)であれば検証合格
【非特許文献１】Masayuki Abe, Tatsuaki Okamoto, "A Signature Scheme with Message Recovery as Secure as Discrete Logarithm," ASIACRYPT 1999, pp.378-389
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、非特許文献１の方式では、式（１）の（Ｆ２（Ｆ１（ｍ））や式（２）のＲのビット長が固定長であり、メッセージｍのビット長も固定長としなければならない。
【０００７】
このため、メッセージｍの長さが固定長より短い場合であっても、それに併せて署名σの一部分ｒのビット長を短くすることができず、非効率である。また、メッセージｍのビット長が固定長よりも長い場合には、式（１）にメッセージｍの一部分しか代入することができず、メッセージｍの全てのビットを対象としたメッセージ復元署名を構成できない。
【０００８】
本発明はこのような点に鑑みてなされたものであり、様々なビット長のメッセージに柔軟に対応可能なメッセージ復元署名技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明では上記課題を解決するために、署名生成装置が以下のように署名生成を行う。
まず、署名生成装置の記憶部に整数の秘密鍵ｘが格納され、さらに、Ｍビットのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍが格納される。ここで、リカバリメッセージｍｒｅｃが、署名対象の少なくとも一部となる。そして、署名生成装置の任意値生成部が、整数の任意値ｋを生成し、群演算部が、位数ｑの巡回群をＧとし、当該巡回群Ｇの生成元をｇとした場合におけるＲ＝ｇｋ∈Ｇを算出し、当該演算結果Ｒを出力する。なお、「ｇｋ∈Ｇ」とは、巡回群Ｇをなす演算をｇについてｋ回実行することを意味する（詳細は後述）。次に、署名生成装置の第１ハッシュ演算部が、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビット（Ｌは署名検証装置と共有される正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを、演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値Π＝Ｈ０（Ｒ）∈｛０，１｝Ｌ＋Ｍを出力する。なお、「関数εをδに作用させる」とは、「δ又はδを特定するための値を関数εに代入する」ことを意味する。次に、署名生成装置の第２ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、ハッシュ値Πとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値ｈ＝Ｈ１（α）∈｛０，１｝Ｌを出力する。また、署名生成装置の第３ハッシュ演算部が、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、ハッシュ値Πとハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値ｕ＝Ｈ２（β）∈｛０，１｝Ｍを出力する。さらに、署名生成装置の第１排他的論理和演算部が、リカバリメッセージｍｒｅｃとハッシュ値ｕとの排他的論理和ｗ＝ｍｒｅｃ（＋）ｕ∈｛０，１｝Ｍ（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを出力する。またビット結合部が、ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値ｄ＝ｈ｜ｗ∈｛０，１｝Ｌ＋Ｍを算出し、当該ビット結合値ｄを出力する。なお、第１ビット位置は必ずしも連続したＬビットの位置である必要はなく、離散的に配置された合計Ｌビットの位置でもよい。同様に、第２ビット位置も必ずしも連続したＭビットの位置である必要はなく、離散的に配置された合計Ｍビットの位置でもよい。ただし、「第１ビット位置」及び「第２ビット位置」がどのビット位置であるかについては、署名生成装置と署名検証装置とで統一しておく。次に、署名生成装置の第２排他的論理和演算部が、ハッシュ値Πとビット結合値ｄとの排他的論理和ｒ＝Π（＋）ｄ∈｛０，１｝Ｌ＋Ｍを算出し、当該排他的論理和値ｒを出力する。また署名生成装置の第４ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、排他的論理和値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力する。そして、整数演算部が、ｓ＝ｋ−ｔ・ｘ∈Ｚを算出し、当該演算結果ｓを出力し、署���出力部が署名σ＝（ｒ，ｓ）を出力する。
【００１０】
本発明の署名検証装置は、このように生成された署名を、以下のように検証する。なお、署名検証装置が受け取る署名をσ’＝（ｒ’，ｓ’）と表現する。
【００１１】
まず、署名検証装置の記憶部に署名生成装置の公開鍵ｙ＝ｇｘ∈Ｇを格納する。そして、署名検証装置の署名入力部に署名σ’＝（ｒ’，ｓ’）が入力され、その署名σ’＝（ｒ’，ｓ’）は記憶部に格納される。また、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を記憶部に格納する。なお、署名検証装置がビット長Ｍ’の値を取得する方法については後述する。そして、署名検証装置の第１ハッシュ演算部が、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、署名σ’が有するｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する。さらに、署名検証装置の群演算部が、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い、その演算結果Ｒ’を出力する。なお、「ｇｓ’・ｙｔ’∈Ｇ」とは、巡回群Ｇをなす演算をｇについてｓ’回施し、当該演算をｙについてｔ’回施し、それらの各演算結果に対して当該演算を施す演算を意味する（詳細は後述）。次に、署名検証装置の第２ハッシュ演算部が、リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＬ＋Ｍ’ビット（Ｌは正の整数）に定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍ’を、演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値Π’＝Ｈ０（Ｒ’）∈｛０，１｝Ｌ＋Ｍ’を出力する。さらに、署名検証装置の第１排他的論理和演算部が、ハッシュ値Πと署名σ’が有するｒ’との排他的論理和ｄ’＝Π’（＋）ｒ’∈｛０，１｝Ｌ＋Ｍ’を算出し、当該排他的論理和値ｄ’を出力する。また、署名検証装置の第３ハッシュ演算部が、リカバリメッセージｍｒｅｃ’のビット長Ｍ’に応じて出力ビット長がＭ’ビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍ’を、ハッシュ値Π’と排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値ｕ’＝Ｈ２（β’）∈｛０，１｝Ｍ’を出力する。また、第２排他的論理和演算部が、排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’とハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として出力する。さらに、第４ハッシュ演算部が、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、ハッシュ値Π’と第２排他的論理和演算部で算出されたリカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを出力する。そして、比較部が、Ｌビットの値ｈ’とハッシュ値Ｈ１（α’）とを比較し、ｈ’＝Ｈ１（α’）であることを条件に、検証が成功である旨の情報を出力する。
【００１２】
なお、「Πとｍｒｅｃとに依存して定まる値α」には、値αがΠとｍｒｅｃとのみに依存する場合のみならず、値αがΠとｍｒｅｃと他の情報とに依存する場合も含まれる。また、「Πとｈとに依存して定まる値β」には、値βがΠとｈとのみに依存する場合のみならず、値βがΠとｈと他の情報とに依存する場合も含まれ、「ｒに依存して定まる値γ」には、値γがｒのみに依存する場合のみならず、値γがｒと他の情報とに依存する場合も含まれる。同様に、「Π’とｍｒｅｃ’とに依存して定まる値α’」には、値α’がΠ’とｍｒｅｃとのみに依存する場合のみならず、値α’がΠ’とｍｒｅｃ’と他の情報とに依存する場合も含まれ、「Π’とｈ’とに依存して定まる値β’」には、値β’がΠ’とｈ’とのみに依存する場合のみならず、値β’がΠ’とｈ’と他の情報とに依存する場合も含まれ、「ｒ’に依存して定まる値γ’」には、値γ’がｒ’のみに依存する場合のみならず、値γ’がｒ’と他の情報とに依存する場合も含まれる。
【００１３】
ただし、署名生成装置で用いる値α，β，γのビット構成と、署名検証装置で用いる値α’，β’，γ’のビット構成とが、それぞれ同一である必要がある。例えば、署名生成装置において、Πを上位Ｌ＋Ｍビットとし、ｍｒｅｃを下位Ｍビットとして結合したＬ＋２Ｍビットの値をαとする場合、署名検証装置においても、Π’を上位Ｌ＋Ｍ’ビットとし、ｍｒｅｃ’を下位Ｍ’ビットとしたＬ＋２Ｍ’ビットの値をα’としなければならない（詳細は後述）。
【００１４】
ここで本発明では、リカバリメッセージのビット長に従って出力ビット長が変化するハッシュ関数Ｈ０，Ｈ２を用い、処理方法を工夫することにより、リカバリメッセージのビット長が変化しても、各排他的論理和演算の対象となる２つの被演算子のビット長を常に同一とできる。これにより、リカバリメッセージのビット長が短い場合には、それに併せて各演算過程での演算ビット数や署名σを構成するｒのビット数を短くでき、効率的な署名方式が実現できる。同時に、リカバリメッセージのビット長が長くなっても、リカバリメッセージｍｒｅｃの全てのビットを対象としたメッセージ復元署名が生成できる。
【００１５】
また、本発明では、署名生成装置で算出されたハッシュ値ｈ，ｕと署名検証装置で算出されたハッシュ値ｈ’，ｕ’とがそれぞれ整合性を持たないと署名検証が成功とならないため、ハッシュ値ｈとハッシュ値ｈ’との整合性のみで署名検証を行う場合より高い安全性を保証できる。
【００１６】
なお、本発明では、従来構成と異なり、メッセージの全てのビットを対象としたメッセージ復元署名を構成することもできる（ｍ＝ｍｒｅｃの場合）。しかし、メッセージｍの全てのビットをメッセージ復元署名の対象としない構成であってもよい。この場合、メッセージ復元署名の対象とするＭビットのリカバリメッセージｍｒｅｃと、メッセージ復元署名ではない通常の署名の対象とするＮビットのクリアメッセージｍｃｌｒとが署名対象となる。この場合、上述した本発明において、さらに、署名生成装置が、Ｎビットのクリアメッセージｍｃｌｒ∈｛０，１｝Ｎを記憶部に格納し、署名生成装置の第４ハッシュ演算部が、ハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、排他的論理和値ｒとクリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値ｔ＝Ｈ３（γ）∈Ｚを出力し、署名生成装置の署名出力部が、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとを出力する。署名検証装置には署名σ’とクリアメッセージｍｃｌｒ’とが入力され、署名検証装置はこれらを格納する。署名検証装置の第１ハッシュ演算部は、ハッシュ関数Ｈ３：｛０，１｝＊→Ｚを、署名σ’が有するｒ’とクリアメッセージｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値ｔ’＝Ｈ３（γ’）∈Ｚを出力する。
【００１７】
これにより、メッセージの全てのビットをメッセージ復元署名の対象とする必要のない場合にまで、メッセージの全ビットをメッセージ復元署名の対象とし、各演算過程における演算ビット数が長くなってしまうことを回避できる。即ち、様々なビット長のメッセージ及び様々な用途に対し、柔軟に対応可能なメッセージ復元署名が実現できる。
【発明の効果】
【００１８】
本発明では、様々なビット長のメッセージに柔軟に対応可能なメッセージ復元署名を実現できる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
【００２０】
〔第１実施形態〕
まず、本発明の第１実施形態について説明する。
【００２１】
＜全体構成＞
図１は、第１実施形態の署名システム１の全体構成を示した概念図である。
図１に示すように、本形態の署名システム１は、署名生成を行う署名生成装置１０と、署名検証を行う署名検証装置２０と、署名生成装置１０の効果鍵を公開する公開鍵サーバ装置３０とを有し、相互にネットワーク４０を通じて通信可能に接続される。なお、署名生成装置１０、署名検証装置２０及び公開鍵サーバ装置３０は、それぞれ、公知のコンピュータに所定のプログラムが読み込まれることにより構成される装置である。
【００２２】
＜署名生成装置１０の構成＞
次に、署名生成装置１０の構成を説明する。
【００２３】
［ハードウェア構成］
図２は、第１実施形態における署名生成装置１０のハードウェア構成を例示したブロック図である。
図２に例示するように、この例の署名生成装置１０は、ＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６、バス１７及び通信部１８を有している。
【００２４】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、この例の入力部１２は、データが入力される入力ポート、キーボード、マウス等であり、出力部１３は、データを出力する出力ポート、外部記録媒体へのデータ記憶装置、印刷装置、ディスプレイなどである。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、各種プログラムを格納したプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、例えば、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが書き込まれるプログラム領域１６ａ及び各種データが書き込まれるデータ領域１６ｂを有している。また、通信部１８は、ネットワークカードなどである。また、この例のバス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５、ＲＡＭ１６及び通信部１８を、データのやり取りが可能なように接続する。
【００２５】
［ハードウェアとプログラムとの協働］
ＣＰＵ１１（図２）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されているプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。なお、各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。
【００２６】
図３は、ＣＰＵ１１にプログラムが読み込まれることにより構成される第１実施形態における署名生成装置１０の機能構成を例示したブロック図である。なお、図３における矢印はデータの流れを示すが、一時メモリ１０ｔや制御部１０ｓに入出力されるデータの流れは省略してある。
図３に示すように、本形態の署名生成装置１０は、記憶部１０ａと、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、入力部１０ｄと、メッセージ分割部１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部１０ｈ，１０ｉ，１０ｊ，１０ｐと、排他的論理和演算部１０ｋ，１０ｎと、ビット結合部１０ｍと、整数演算部１０ｑと、通信部１０ｒと、制御部１０ｓと、一時メモリ１０ｔとを有する。
【００２７】
また、図４（ａ）は、ハッシュ演算部１０ｈの機能構成の詳細を示した図であり、図４（ｂ）は、ハッシュ演算部１０ｊの機能構成の詳細を示した図である。図４に示すように、ハッシュ演算部１０ｈは、ハッシュ回数演算部１０ｈａと、部分ハッシュ演算部１０ｈｂと、ビット結合部１０ｈｃと、ビット削除部１０ｈｄとを有する。また、ハッシュ演算部１０ｊは、ハッシュ回数演算部１０ｊａと、部分ハッシュ演算部１０ｊｂと、ビット結合部１０ｊｃと、ビット削除部１０ｊｄとを有する。
【００２８】
なお、記憶部１０ａと一時メモリ１０ｔとは、例えば、図２に記載したレジスタ１１ｃ、補助記憶装置１４、ＲＡＭ１６、或いはこれらを結合した記憶領域に相当する。また、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、メッセージ分割部１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部１０ｈ，１０ｉ，１０ｊ，１０ｐと、排他的論理和演算部１０ｋ，１０ｎと、ビット結合部１０ｍと、整数演算部１０ｑと、制御部１０ｓとは、それぞれの処理を実現するためのプログラムがＣＰＵ１１に読み込まれることにより構成されるものである。また、入力部１０ｄは、所定のプログラムが読み込まれたＣＰＵ１１の制御のもと駆動する入力部１２であり、通信部１０ｒは、所定のプログラムが読み込まれたＣＰＵ１１の制御のもと駆動する通信部１８である。また、署名生成装置１０は、制御部１０ｓの制御のもと各処理を実行する。さらに、特に明示しない限り、演算過程の各データは逐一一時メモリ１０ｔに読み書きされる。
【００２９】
また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名生成装置１０の機能をコンピュータに実行させるためのプログラムに相当する。
【００３０】
＜署名検証装置２０の構成＞
次に、署名検証装置２０の構成を説明する。
【００３１】
［ハードウェア構成］
図２に示した署名生成装置１０のハードウェア構成と同様である。
【００３２】
［ハードウェアとプログラムとの協働］
署名検証装置２０も図２に示したようなコンピュータに所定のプログラムが読み込まれることにより構成される。図５は、このように構成される第１実施形態の署名検証装置２０の機能構成を例示したブロック図である。なお、図５における矢印はデータの流れを示すが、一時メモリ２０ｎや制御部２０ｐに入出力されるデータの流れは省略してある。
【００３３】
図５に示すように、本形態の署名検証装置２０は、記憶部２０ａと、通信部２０ｂと、ビット長抽出部２０ｃと、ハッシュ演算部２０ｄ，２０ｆ，２０ｉ，２０ｋと、群演算部２０ｅと、排他的論理和演算部２０ｇと、ビット抽出部２０ｈと、排他的論理和演算部２０ｊと、比較部２０ｌと、出力部２０ｍと、制御部２０ｎと、一時メモリ２０ｐとを有する。
【００３４】
なお、記憶部２０ａと一時メモリ２０ｐとは、例えば、コンピュータが具備するレジスタ、補助記憶装置、ＲＡＭ、或いはこれらを結合した記憶領域に相当する。また、ビット長抽出部２０ｃと、ハッシュ演算部２０ｄ，２０ｆ，２０ｉ，２０ｋと、群演算部２０ｅと、排他的論理和演算部２０ｇと、ビット抽出部２０ｈと、排他的論理和演算部２０ｊと、比較部２０ｌと、制御部２０ｎとは、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。また、出力部２０ｍと通信部２０ｂは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動する。また、署名検証装置２０は、制御部２０ｎの制御のもと各処理を実行する。さらに、特に明示しない限り、演算過程の各データは逐一一時メモリ２０ｐに読み書きされる。
【００３５】
また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名検証装置２０の機能をコンピュータに実行させるためのプログラムに相当する。
【００３６】
＜処理＞
次に、本形態の処理について説明する。
【００３７】
［前処理］
まず、署名システム１で使用する位数ｑの離散対数問題の求解が困難な巡回群Ｇとその生成元ｇ∈Ｇとを決定する。このような巡回群Ｇとしては、例えば、楕円曲線上の有理点のなす群や有限体の乗法群などを用いることができる。なお、楕円曲線上の有理点のなす群を用いる場合、生成元ｇは楕円曲線上の点ｇ＝（ｇ１，ｇ２）であり、有限体の乗法群を用いる場合、生成元ｇは２以上の整数である。また、楕円曲線上の有理点のなす群をコンピュータ上で実現するための具体的方法には様々なもの（例えば、「N. Koblitz. Elliptic Curve Cryptosystems. Math. Comp., Vol. 48, No. 17, pp. 203-209, 1987.」「Victor S. Miller. Use of Elliptic Curves in Cryptography. In Advances in Cryptology - CRYPTO ’85, Vol. 218 of Lecture Notes in Computer Science, pp. 417-426. Springer, 1986.」）が存在し、実際、楕円曲線上の有理点のなす群で構成され、コンピュータ上で実装可能な様々な暗号方式が存在する。また、安全性の面から位数ｑは素数であることが望ましいが、ｑの素因数分解が困難であるならｑは素数でなくてもかまわない。また、署名システム１で使用するビット長パラメータＬ∈Ｚ＞0（０より大きな整数）を決定する。
【００３８】
さらに、後述するリカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビットに定まる出力が可変長のハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを決定し、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まる出力が可変長のハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを決定する。なお、これらのハッシュ関数の処理方法については後述する。
【００３９】
また、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌと、また、入力値に対してＺｑ（ｑを法とする完全剰余系）の元を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑとを決定する。ハッシュ関数Ｈ１は、ハッシュ関数Ｈ０やハッシュ関数Ｈ２と同様に構成でき、ハッシュ関数Ｈ３は、ＳＨＡ−１等のハッシュ値に対し、ｑを法とした剰余演算を行うことで構成できる。
【００４０】
以上のように決定された巡回群Ｇや各ハッシュ関数Ｈ０〜Ｈ３を特定する情報は、例えば、署名生成装置１０や署名検証装置２０を構成する各プログラムに書き込まれ、署名生成装置１０や署名検証装置２０は、決定された巡回群Ｇでの演算や、各ハッシュ関数Ｈ０〜Ｈ３の演算が可能になるものとする。また、ビット長パラメータＬ∈Ｚ＞0や位数ｑや生成元ｇ∈Ｇは、署名生成装置１０の記憶部１０ａと署名検証装置２０の記憶部２０ａに格納される。
【００４１】
［鍵生成処理］
次に、署名生成装置１０が行う鍵生成処理について説明する。
まず、署名生成装置１０の秘密鍵生成部１０ｂが任意の秘密鍵ｘ∈Ｚｑを生成する。なお、この秘密鍵ｘの生成は、擬似乱数をＺｑにマッピングして行ってもよいし、署名生成者によって任意に決定された値を元に行ってもよい。生成された秘密鍵ｘは、署名生成装置１０の記憶部１０ａに安全に格納される。すなわち、署名生成装置１０の外部の装置は、記憶部１０ａから秘密鍵ｘを取得することができない。
【００４２】
次に、署名生成装置１０の公開鍵生成部１０ｃが、記憶部１０ａから秘密鍵ｘと巡回群Ｇの生成元ｇ∈Ｇとを読み込み、巡回群Ｇで定義された演算
y=gx∈G  …(3)
を行って秘密鍵ｘに対応する公開鍵ｙ∈Ｇを生成し、記憶部１０ａに格納する。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（３）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｘ倍）する演算（ｘ・ｇ∈Ｅ）を意味し、公開鍵ｙは楕円曲線Ｅ上の点となる。なお、楕円スカラー倍演算をコンピュータ上で実行する具体的な方法としては、二進展開法、移動窓法等の公知の演算方法を例示できる（例えば、参考文献１“イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、鈴木治郎＝訳、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0”等参照）。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（３）の右辺は、ｇｘｍｏｄ ｐ（ただし、ｇは２以上の整数、ｐ＝２ｑ＋１）の演算を意味し、公開鍵ｙはスカラー値となる。生成された公開鍵ｙは、通信部１０ｒからネットワーク４０を通じて公開鍵サーバ装置３０に送信され、公開鍵サーバ装置３０は、送信された公開鍵ｙを例えば公開鍵証明書とともに公開する。なお、公開鍵ｙ等の公開とは、公開鍵ｙ等が公開鍵サーバ装置３０の記憶部に格納され、ネットワーク４０に接続可能な任意の装置が公開鍵サーバ装置３０の記憶部に格納された公開鍵ｙ等を取得可能な状態とすることを意味する。署名検証装置２０は、このような公開鍵ｙを通信部２０ｂによって公開鍵サーバ装置３０から受信し、記憶部２０ａに格納する。
【００４３】
［署名生成処理］
次に、第１実施形態の署名生成処理について説明する。
図６は、第１実施形態の署名生成処理を説明するためのフローチャートである。以下、図６に従って本形態の署名生成処理を説明する。
【００４４】
まず、署名生成装置１０（図３）の入力部１０ｄに、メッセージｍ∈｛０，１｝Ｎ＋Ｍとリカバリメッセージのビット長Ｍ≧１とが入力される（ステップＳ１１）。入力されたこれらの情報は、それぞれ記憶部１０ａに格納される。
【００４５】
次に、メッセージ分割部１０ｅが、記憶部１０ａからメッセージｍ∈｛０，１｝Ｎ＋Ｍとリカバリメッセージのビット長Ｍ≧１とを読み込む。メッセージ分割部１０ｅは、これらの情報を用い、
メッセージｍ∈｛０，１｝Ｎ＋Ｍを、ビット長Ｍのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍ  と、ビット長Ｎ（Ｎ≧０）のクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとに分割する（ステップＳ１２）。例えば、メッセージｍ∈｛０，１｝Ｎ＋Ｍの上位Ｍビットをリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍとし、下位Ｎビットをクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとする。なお、分割法はこれに限定されず、メッセージｍ∈｛０，１｝Ｎ＋Ｍのどのビットをリカバリメッセージｍｒｅｃとし、どのビットをクリアメッセージｍｃｌｒ
とするかは、任意に設定できる。このように分割されたビット長Ｍのリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍ  と、ビット長Ｎのクリアメッセージｍｃｌｒ∈｛０，１｝Ｎとは、それぞれ記憶部１０ａに格納される。
【００４６】
次に、任意値生成部１０ｆが任意値ｋ∈Ｚｑを生成し、生成した任意値ｋを記憶部１０ａに格納する（ステップＳ１３）。なお、任意値ｋの生成は、例えば、擬似乱数をＺｑにマッピングすることにより行う。
【００４７】
次に、群演算部１０ｇが、記憶部１０ａから生成元ｇ∈Ｇと任意値ｋ∈Ｚｑとを読み込み、
R=gk∈G  …(4)
を算出し、当該演算結果Ｒ∈Ｇを記憶部１０ａに出力して格納する（ステップＳ１４）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（４）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｋ倍）する演算（ｋ・ｇ∈Ｅ）を意味し、演算結果Ｒは楕円曲線Ｅ上の点となる。なお、楕円スカラー倍演算をコンピュータ上で実行する具体的な方法としては、二進展開法、移動窓法等の公知の演算方法を例示できる。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（４）の右辺は、ｇｋｍｏｄ ｐの演算を意味し、演算結果Ｒはスカラー値となる。
【００４８】
次に、ハッシュ演算部１０ｈが、記憶部１０ａから演算結果Ｒ∈Ｇとリカバリメッセージのビット長Ｍとビット長パラメータＬを読み込む。ハッシュ演算部１０ｈは、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＬ＋Ｍビットに定まるハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを演算結果Ｒに作用させ、その演算結果であるＬ＋Ｍビットのハッシュ値
Π=H0(R)∈{0,1}L+M  …(5)
を記憶部１０ａに出力して格納する（ステップＳ１５）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（５）の右辺は、楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値（例えば、点Ｒのｘ座標若しくはｙ座標、又は、点Ｒのｘ座標とｙ座標とのビット結合値）にハッシュ関数Ｈ０を作用させる演算を意味する。すなわち、この場合の「ハッシュ関数Ｈ０を演算結果Ｒに作用させる」とは、ハッシュ関数Ｈ０を、楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値に作用させることを意味する。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（５）の右辺は、スカラー値である演算結果Ｒにハッシュ関数Ｈ０を作用させる演算を意味する。
【００４９】
［ステップＳ１５の処理の例］
図７（ａ）は、ステップＳ１５の処理の例を説明するためのフローチャートである。
【００５０】
まず、リカバリメッセージのビット長Ｍとビット長パラメータＬとがハッシュ演算回数算出部１０ｈａに読み込まれる。ハッシュ演算回数算出部１０ｈａは、
emax=rounddown{(L+M)/length(H)}  …(5-1)
の演算を行ってｅｍａｘ
を一時メモリ１０ｔに格納する（ステップＳ１５ａ）。なお、rounddown｛＊｝は＊の小数点以下を切り捨てる演算を意味し、length（＊）は＊のビット長を意味し、Ｈは公知のハッシュ関数を意味する。なお、ハッシュ関数Ｈの具体例としては、ＳＨＡ−１（ビット長１６０ビット）やＭＤ５（ビット長１２８ビット）などを例示できる。例えば、Ｌ＋Ｍ＝５００であり、ハッシュ関数ＨがＳＨＡ−１〔length（Ｈ）＝１６０〕であるならば、ｅｍａｘ＝３である。
【００５１】
次に、制御部１０ｓは変数ｅに０を代入し、変数ｅを一時メモリ１０ｔに格納する（ステップＳ１５ｂ）。
【００５２】
次に、部分ハッシュ演算部１０ｈｂが、一時メモリ１０ｔから変数ｅを読み込み、記憶部１０ａから演算結果Ｒを読み込み、ハッシュ値
H(e,R)  …(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)…))
となる（［ステップＳ１５の処理の例］の説明終わり）。
【００５６】
ステップＳ１５の後、ハッシュ演算部１０ｉが、記憶部１０ａからハッシュ値Πとリカバリメッセージｍｒｅｃとビット長パラメータＬとを読み込む。ハッシュ演算部１０ｉは、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、ハッシュ値Πとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ、その演算結果であるＬビットのハッシュ値
h=H1(α)∈{0,1}L  …(6)
を記憶部１０ａに出力して格納する（ステップＳ１６）。なお、第１実施形態では、αはハッシュ値Πとリカバリメッセージｍｒｅｃとのみに依存する値α＝（Π，ｍｒｅｃ）である。なお、本形態のαの構成方法に限定はないが、αの構成方法は後述する署名検証装置２０でのα’（後述）の構成方法と同一とする。αの構成例としては以下のようなものがある。
【００５７】
〔α−１〕Πを上位Ｌ＋Ｍビットとし、ｍｒｅｃを下位Ｍビットとして結合したＬ＋２Ｍビットの値をαとする。
〔α−２〕Πを下位Ｌ＋Ｍビットとし、ｍｒｅｃを上位Ｍビットとして結合したＬ＋２Ｍビットの値をαとする。
〔α−３〕ｍｒｅｃを上位から奇数番目のビット（合計Ｍビット）とし、Πをその他のＬ＋Ｍビットとして結合したＬ＋２Ｍビットの値をαとする。
【００５８】
次に、ハッシュ演算部１０ｊが、記憶部１０ａからハッシュ値Πとハッシュ値ｈとリカバリメッセージのビット長Ｍとを読み込む。ハッシュ演算部１０ｊは、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、ハッシュ値Πとハッシュ値ｈとに依存して定まる値βに作用させ、その演算結果であるＭビットのハッシュ値
u=H2(β)∈{0,1}M  …(7)
を記憶部１０ａに出力して格納する（ステップＳ１７）。なお、第１実施形態では、βはハッシュ値Πとハッシュ値ｈとのみに依存する値β＝（Π，ｈ）である。本形態のβの構成方法に限定はないが、βの構成方法は後述する署名検証装置２０でのβ’（後述）の構成方法と同一とする。βの構成例としては以下のようなものがある。
【００５９】
〔β−１〕Πを上位Ｌ＋Ｍビットとし、ｈを下位Ｌビットとして結合した２Ｌ＋Ｍビットの値をβとする。
〔β−２〕Πを下位Ｌ＋Ｍビットとし、ｈを上位Ｌビットとして結合した２Ｌ＋Ｍビットの値をβとする。
〔β−３〕ｈを上位から奇数番目のビット（合計Ｌビット）とし、Πをその他のＬ＋Ｍビットとして結合した２Ｌ＋Ｍビットの値をβとする。
【００６０】
［ステップＳ１７の処理の例］
図７（ｂ）は、ステップＳ１７の処理の例を説明するためのフローチャートである。
まず、リカバリメッセージのビット長Ｍがハッシュ演算回数算出部１０ｊａに読み込まれる。ハッシュ演算回数算出部１０ｊａは、
emax=rounddown{M/length(H)}  …(7-1)
の演算を行ってｅｍａｘ
を一時メモリ１０ｔに格納する（ステップＳ１７ａ）。
【００６１】
次に、制御部１０ｓは変数ｅに０を代入し、変数ｅを一時メモリ１０ｔに格納する（ステップＳ１７ｂ）。
次に、部分ハッシュ演算部１０ｊｂが、一時メモリ１０ｔから変数ｅを読み込み、記憶部１０ａからハッシュ値Π，ｈを読み込み、ハッシュ値
H(e,β),β=(Π,h)  …(7-2)
を算出して一時メモリ１０ｔに格納する（ステップＳ１７ｃ）。
【００６２】
次に、制御部１０ｓが、一時メモリ１０ｔからｅｍａｘと変数ｅとを読み込み、
e=emax  …(7-3)
を満たすか否かを判断する（ステップＳ１７ｄ）。ここで、式（７−３）を満たさないのであれば、制御部１０ｓはｅ＋１を新たなｅとし、新たなｅを一時メモリ１０ｔに格納した後（ステップＳ１７ｅ）、処理をステップＳ１７ｃに戻す。一方、式（７−３）を満たすのであれば、制御部１０ｓはビット結合部１０ｊｃに指示を与え、ビット結合部１０ｊｃは、一時メモリ１０ｔから各ハッシュ値Ｈ（０，β），Ｈ（１，β），Ｈ（２，β），…，Ｈ（ｅｍａｘ，β）を読み込み、それらのビット結合値
HC(β)=H(0,β)|・・・|H(emax,β)  …(7-4) 
を算出して一時メモリ１０ｔに格納する（ステップＳ１７ｆ）。 
【００６３】
次に、ビット削除部１０ｊｄが、一時メモリ１０ｔから、ビット結合値ＨＣ（β）とリカバリメッセージのビット長Ｍを読み込み、
Π=H0(β)=delete{length(HC(β))-length(M),HC(β)｝  …(7-5)
を算出して記憶部１０ａに出力する（ステップＳ１７ｇ）。
【００６４】
なお、ステップＳ１７の処理方法はこれに限定されない。例えば、ｅを用いるのではなく、ハッシュチェインによってハッシュ値のビット長を拡張する方法でもよい（［ステップＳ１７の詳細処理の例］の説明終わり）。
【００６５】
ステップＳ１７の後、排他的論理和演算部１０ｋが、記憶部１０ａからリカバリメッセージｍｒｅｃとハッシュ値ｕとを読み込む。排他的論理和演算部１０ｋは、リカバリメッセージｍｒｅｃとハッシュ値ｕとの排他的論理和
w=mrec(+)u∈{0,1}M  …(8)
（（＋）は排他的論理和演算子）を算出し、当該排他的論理和値ｗを記憶部１０ａに出力して格納する（ステップＳ１８）。
【００６６】
次に、ビット結合部１０ｍが、記憶部１０ａからハッシュ値ｈ∈｛０，１｝Ｌと排他的論理和値ｗ∈｛０，１｝Ｍとを読み込む。ビット結合部１０ｍは、ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値
d=h|w∈{0,1}L+M  …(9)
を算出し、当該ビット結合値ｄを記憶部１０ａに出力して格納する（ステップＳ１９）。なお、「第１ビット位置」及び「第２ビット位置」をどのビット位置にするかについて特に限定はない。しかし、署名生成装置１０と署名検証装置２０との間では、「第１ビット位置」及び「第２ビット位置」をどのビット位置にするかの基準を同一にしなければならない。図９に「第１ビット位置」及び「第２ビット位置」の設定例を示す。
【００６７】
図９（ａ）の例は、連続した上位Ｌビットを「第１ビット位置」とし、連続した下位Ｍビットを「第２ビット位置」とした例である。図９（ｂ）の例は、連続した上位Ｍビットを「第２ビット位置」とし、連続した下位Ｌビットを「第１ビット位置」とした例である。また、図９（ｃ）の例は、Ｌ≧Ｍの場合の例であり、上位から奇数番目のビット（合計Ｍビット）の位置を「第２ビット位置」とし、その他のビット位置を「第１ビット位置」とした例である。
【００６８】
次に、排他的論理和演算部１０ｎが、記憶部１０ａからハッシュ値Πとビット結合値ｄとを読み込む。排他的論理和演算部１０ｎは、ハッシュ値Πとビット結合値ｄとの排他的論理和
r=Π(+)d∈{0,1}L+M  …(10)
を算出し、当該排他的論理和値ｒを記憶部１０ａに出力して格納する（ステップＳ２０）。
【００６９】
次に、ハッシュ演算部１０ｐが、記憶部１０ａから排他的論理和値ｒとクリアメッセージｍｃｌｒとを読み込む。ハッシュ演算部１０ｐは、入力値に対して整数を出力するハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、排他的論理和値ｒとクリアメッセージｍｃｌｒとに依存して定まる値γに作用させ、その演算結果であるハッシュ値
t=H3(γ)∈Zq  …(11)
を記憶部１０ａに出力して格納する（ステップＳ２１）。なお、第１実施形態では、γは排他的論理和値ｒとクリアメッセージｍｃｌｒとのみに依存する値γ＝（ｒ，ｍｃｌｒ）である。本形態のγの構成方法に限定はないが、γの構成方法は後述する署名検証装置２０でのγ’（後述）の構成方法と同一とする。γの構成例としては以下のようなものがある。
【００７０】
〔γ−１〕ｒを上位Ｌ＋Ｍビットとし、ｍｃｌｒを下位Ｎビットとして結合したＬ＋Ｍ＋Ｎビットの値をγとする。
〔γ−２〕ｒを下位Ｌ＋Ｍビットとし、ｍｃｌｒを上位Ｎビットとして結合したＬ＋Ｍ＋Ｎビットの値をγとする。
〔γ−３〕ｍｃｌｒを上位から奇数番目のビット（合計Ｎビット）とし、ｒをその他のＬ＋Ｍビットとして結合したＬ＋Ｍ＋Ｎビットの値をγとする。
【００７１】
次に、整数演算部１０ｑが、記憶部１０ａから任意値ｋとハッシュ値ｔと秘密鍵ｘとｑとを読み込む。整数演算部１０ｑは、
s=k-t・x∈Zq  …(12)
を算出し、当該演算結果ｓを記憶部１０ａに出力して格納する（ステップＳ２２）。
【００７２】
次に、通信部１０ｒに、排他的論理和値ｒと演算結果ｓとクリアメッセージｍｃｌｒとが読み込まれ、通信部１０ｒは、署名σ＝（ｒ，ｓ）とクリアメッセージｍｃｌｒとをネットワーク４０を通じて署名検証装置２０に送信する（ステップＳ２３）。
【００７３】
［署名検証処理］
次に、第１実施形態の署名検証処理について説明する。
図８は、第１実施形態の署名検証処理を説明するためのフローチャートである。以下、図８に従って本形態の署名検証処理を説明する。
【００７４】
まず、署名検証装置２０（図５）の通信部２０ｂが、署名σ’＝（ｒ’，ｓ’）とクリアメッセージｍｃｌｒ’とを受信し（「入力を受け付け」に相当）、これらを記憶部２０ａに格納する（ステップＳ４１）。なお、署名とリアメッセージとが正規なものであれば、σ’＝（ｒ’，ｓ’）＝σ＝（ｒ，ｓ）であり、ｍｃｌｒ’＝ｍｃｌｒであるが、ここでは、検証対象の署名をσ’＝（ｒ’，ｓ’）と表現し、検証対象のクリアメッセージをｍｃｌｒ’と表現する。
【００７５】
次に、ビット長抽出部２０ｃが、記憶部２０ａから、ビット長パラメータＬと署名σ’＝（ｒ’，ｓ’）のｒ’とを読み込む。ビット長抽出部２０ｃは、
M'=length(r')‐L  …(13)
により、署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を算出し、記憶部２０ａに格納する（ステップＳ４２）。
【００７６】
次に、ハッシュ演算部２０ｄが、記憶部２０ａからｒ’とクリアメッセージをｍｃｌｒ’とｑとを読み込む。ハッシュ演算部２０ｄは、署名生成装置１０と同一のハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、ｒ’とｍｃｌｒ’とに依存して定まる値γ’に作用させ、その演算結果であるハッシュ値
t’=H3(γ’)  …(14)
を記憶部２０ａに出力して格納する（ステップＳ４３）。なお、γ’の構成方法は前述した署名生成装置１０でのγの構成方法と同一（ｒ＝ｒ’とし、ｍｃｌｒ＝ｍｃｌｒ’とした場合に同一）とする。
【００７７】
次に、群演算部２０ｅが、記憶部２０ａから、生成元ｇ∈Ｇと署名生成装置１０の公開鍵ｙ∈Ｇと署名σ’のｓ’とハッシュ値ｔ’とを読み込み、
R’=gs’・yt’∈G  …(15)
の演算を行い、その演算結果Ｒ’を記憶部２０ａに出力して格納する（ステップＳ４４）。なお、例えば、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群であった場合、式（１５）の右辺は、楕円曲線Ｅ上の点である生成元ｇ＝（ｇ１，ｇ２）を楕円スカラー倍（楕円ｓ’倍）し、公開鍵ｙ＝（ｙ１，ｙ２）を楕円スカラー倍（楕円ｔ’倍）し、それらの演算結果を楕円加算する演算（ｓ’・ｇ＋ｔ’・ｙ∈Ｅ）を意味し、演算結果Ｒ’は楕円曲線Ｅ上の点となる。なお、楕円スカラー倍演算をＣＰＵ上で実行する具体的な方法としては、二進展開法、移動窓法等の公知の演算方法を例示できる。また、例えば、巡回群Ｇが有限体の乗法群であった場合、式（１５）の右辺は、ｇｓ’・ｙｔ’ｍｏｄ ｐの演算を意味し、演算結果Ｒ’はスカラー値となる。
【００７８】
次に、ハッシュ演算部２０ｆが、記憶部２０ａから演算結果Ｒ’∈Ｇとリカバリメッセージｍｒｅｃ’のビット長Ｍ’とビット長パラメータＬを読み込む。ハッシュ演算部２０ｆは、署名生成装置１０と同じハッシュ関数Ｈ０：｛０，１｝＊→｛０，１｝Ｌ＋Ｍを演算結果Ｒ’に作用させ、その演算結果であるＬ＋Ｍ’ビットのハッシュ値
Π'=H0(R')∈{0,1}L+M'  …(16)
を記憶部２０ａに出力して格納する（ステップＳ４５）。なお、Ｈ０（Ｒ’）の演算は、署名生成装置１０の場合と同一（Ｒ＝Ｒ’の場合に同一）とする。
【００７９】
次に、排他的論理和演算部２０ｇが、記憶部２０ａから、ハッシュ値Π’と署名σ’が有するｒ’とを読み込み、それらの排他的論理和
d’=Π’(+)r’∈{0,1}Ｌ＋Ｍ’  …(17)
を算出し、当該排他的論理和値ｄ’を記憶部２０ａに出力して格納する（ステップＳ４６）。
【００８０】
次に、ビット抽出部２０ｈが、記憶部２０ａから排他的論理和値ｄ’とリカバリメッセージｍｒｅｃ’のビット長Ｍ’とを読み込む。ビット抽出部２０ｈは、排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’とを抽出し、それらを記憶部２０ａに格納する（ステップＳ４７）。なお、「第１ビット位置」及び「第２ビット位置」は、署名生成装置１０の処理での「第１ビット位置」及び「第２ビット位置」と同一（ｄ＝ｄ’とした場合に同一）とする。
【００８１】
次に、ハッシュ演算部２０ｉが、記憶部２０ａからハッシュ値Π’とｈ’とリカバリメッセージｍｒｅｃ’のビット長Ｍ’とを読み込む。ハッシュ演算部２０ｉは、署名生成装置１０と同一のハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、ハッシュ値Π’と値ｈ’とに依存して定まる値β’に作用させ、その演算結果であるＭ’ビットのハッシュ値
u'=H2(β')∈{0,1}M'  …(18)
を記憶部２０ａに出力して格納する（ステップＳ４８）。なお、β'の構成方法は前述した署名生成装置１０でのβの構成方法と同一（Π＝Π’とし、ｈ＝ｈ’とした場合に同一）とする。
【００８２】
排他的論理和演算部２０ｊが、記憶部２０ａから値ｗ’∈｛０，１｝Ｍ’とハッシュ値ｕ’とを読み込む。排他的論理和演算部２０ｊは、値ｗ’とハッシュ値ｕ’との排他的論理和
mrec’=w’(+)u’∈{0,1}M  …(19)
を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として記憶部２０ａに出力して格納する（ステップＳ４９）。
【００８３】
次に、ハッシュ演算部２０ｋが、記憶部２０ａからハッシュ値Π’とリカバリメッセージｍｒｅｃ’とを読み込む。ハッシュ演算部２０ｋは、署名生成装置１０と同一のハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、ハッシュ値Π’とリカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値
H1(α’)∈{0,1}L  …(20)
を記憶部２０ａに出力して格納する（ステップＳ５０）。なお、α’の構成方法は前述した署名生成装置１０でのαの構成方法と同一（Π＝Π’とし、ｍｒｅｃ＝ｍｒｅｃ’とした場合に同一）とする。
【００８４】
次に、比較部２０ｌが、記憶部２０ａからハッシュ値Ｈ１（α’）と値ｈ’とを読み込み、
h'=H1(α’)   …(21)
を満たすか否かを判断する（ステップＳ５１）。
【００８５】
ここで、式（２１）を満たさない場合、比較部２０ｌは０（検証失敗）を記憶部２０ａに出力して格納し、出力部２０ｍは、記憶部２０ａから送られた０（検証失敗）を出力する（ステップＳ５２）。一方、式（２１）を満たす場合、比較部２０ｌは１（検証成功）を記憶部２０ａに出力して格納し、出力部２０ｍは、記憶部２０ａから送られた１（検証成功）を出力し（ステップＳ５３）、さらにリカバリメッセージｍｒｅｃ’を出力する（ステップＳ５４）。
【００８６】
〔第２実施形態〕
次に、本発明の第２実施形態について説明する。第２実施形態ではクリアメッセージを用いない。この点が第１実施形態との相違点である。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【００８７】
＜全体構成＞
第１実施形態の署名システム１の署名生成装置１０が署名生成装置１１０に置換され、署名検証装置２０が署名検証装置１２０に置換された構成である。
【００８８】
＜署名生成装置１１０の構成＞
次に、署名生成装置１１０の構成を説明する。
【００８９】
［ハードウェア構成］
第１実施形態の署名生成装置１０と同じである。
【００９０】
［ハードウェアとプログラムとの協働］
署名生成装置１１０もコンピュータに所定のプログラムが読み込まれることにより構成される。
図１０は、このように構成される第２実施形態における署名生成装置１１０の機能構成を例示したブロック図である。なお、署名生成装置１１０において署名生成装置１０と共通する部分には図３と同じ符号を付して説明を簡略化する。
図１０に示すように、本形態の署名生成装置１１０は、記憶部１０ａと、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、入力部１１０ｄと、ビット長抽出部１１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部１０ｈ，１０ｉ，１０ｊ，１１０ｐと、排他的論理和演算部１０ｋ，１０ｎと、ビット結合部１０ｍと、整数演算部１０ｑと、通信部１１０ｒと、制御部１０ｓと、一時メモリ１０ｔとを有する。
【００９１】
なお、ビット長抽出部１１０ｅとハッシュ演算部１１０ｐは、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。また、入力部１１０ｄは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動し、通信部１１０ｒは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動する。
【００９２】
また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名生成装置１１０の機能をコンピュータに実行させるためのプログラムに相当する。
【００９３】
＜署名検証装置１２０の構成＞
次に、署名検証装置１２０の構成を説明する。
【００９４】
［ハードウェア構成］
第１実施形態の署名検証装置２０と同じである。
【００９５】
［ハードウェアとプログラムとの協働］
署名検証装置１２０もコンピュータに所定のプログラムが読み込まれることにより構成される。図１１は、このように構成される第２実施形態の署名検証装置１２０の機能構成を例示したブロック図である。
図１１に示すように、本形態の署名検証装置１２０は、記憶部２０ａと、通信部１２０ｂと、ビット長抽出部２０ｃと、ハッシュ演算部１２０ｄ，２０ｆ，２０ｉ，２０ｋと、群演算部２０ｅと、排他的論理和演算部２０ｇと、ビット抽出部２０ｈと、排他的論理和演算部２０ｊと、比較部２０ｌと、出力部２０ｍと、制御部２０ｎと、一時メモリ２０ｐとを有する。
【００９６】
なお、ハッシュ演算部１２０ｄは、処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。また、通信部１２０ｂは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動する。また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名検証装置１２０の機能をコンピュータに実行させるためのプログラムに相当する。
【００９７】
＜処理＞
次に、本形態の処理について説明する。
【００９８】
［前処理・鍵生成処理］
第１実施形態と同じである。
【００９９】
［署名生成処理］
次に、第２実施形態の署名生成処理について説明する。
図１２は、第２実施形態の署名生成処理を説明するためのフローチャートである。以下、図１２に従って本形態の署名生成処理を説明する。
【０１００】
まず、署名生成装置１１０（図１０）の入力部１１０ｄに、リカバリメッセージｍｒｅｃ∈｛０，１｝Ｍが入力される（ステップＳ１１１）。入力されたリカバリメッセージｍｒｅｃは、記憶部１０ａに格納される。なお、第２実施形態ではｍ＝ｍｒｅｃである。
次に、ビット長抽出部１１０ｅが、記憶部１０ａからリカバリメッセージｍｒｅｃ∈｛０，１｝Ｍを読み込み、そのビット長Ｍを抽出して記憶部１０ａに格納する（ステップＳ１１２）。
【０１０１】
その後、署名生成装置１１０において第１実施形態のステップＳ１３〜Ｓ２０と同じ処理（ステップＳ１１３〜Ｓ１２０）が実行された後、ハッシュ演算部１１０ｐが、記憶部１０ａから排他的論理和値ｒを読み込む。ハッシュ演算部１１０ｐは、第１実施形態と同じハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、排他的論理和値ｒに依存して定まる値γに作用させ、その演算結果であるハッシュ値
t=H3(γ)∈Zq  …(22)
を記憶部１０ａに出力して格納する（ステップＳ１２１）。なお、第２実施形態では、γは排他的論理和値ｒのみに依存する値γ＝（ｒ）である。本形態のγの構成方法に限定はないが、γの構成方法は後述する署名検証装置１２０でのγ’（後述）の構成方法と同一とする。
【０１０２】
次に、整数演算部１０ｑが、記憶部１０ａから任意値ｋとハッシュ値ｔと秘密鍵ｘとｑとを読み込み、前述の式（１２）によってｓを算出し、当該演算結果ｓを記憶部１０ａに出力して格納する（ステップＳ１２２）。
次に、通信部１１０ｒに、排他的論理和値ｒと演算結果ｓが読み込まれ、通信部１０ｒは、署名σ＝（ｒ，ｓ）をネットワーク４０を通じて署名検証装置１２０に送信する（ステップＳ１２３）。
【０１０３】
［署名検証処理］
次に、第２実施形態の署名検証処理について説明する。
【０１０４】
図１３は、第２実施形態の署名検証処理を説明するためのフローチャートである。以下、図１３に従って本形態の署名検証処理を説明する。
【０１０５】
まず、署名検証装置１２０（図１１）の通信部１２０ｂが、署名σ’＝（ｒ’，ｓ’）を受信し（「入力を受け付け」に相当）、これらを記憶部２０ａに格納する（ステップＳ１４１）。
【０１０６】
次に、ビット長抽出部２０ｃが、記憶部２０ａから、ビット長パラメータＬと署名σ’＝（ｒ’，ｓ’）のｒ’とを読み込み、前述の式（１３）によって署名σ’に対応するリカバリメッセージｍｒｅｃ’のビット長Ｍ’を算出し、記憶部２０ａに格納する（ステップＳ１４２）。
【０１０７】
次に、ハッシュ演算部１２０ｄが、記憶部２０ａからｒ’とｑとを読み込む。ハッシュ演算部１２０ｄは、署名生成装置１１０と同一のハッシュ関数Ｈ３：｛０，１｝＊→Ｚｑを、ｒ’に依存して定まる値γ’に作用させ、その演算結果であるハッシュ値
t’=H3(γ’)  …(23)
を記憶部２０ａに出力して格納する（ステップＳ１４３）。なお、γ’の構成方法は前述した署名生成装置１１０でのγの構成方法と同一（ｒ＝ｒ’とした場合に同一）とする。
【０１０８】
その後、第１実施形態のステップＳ４４〜Ｓ５４と同じ処理によって署名検証を行う（ステップＳ１４４〜Ｓ１５４）。
【０１０９】
〔第３実施形態〕
次に、本発明の第３実施形態について説明する。本形態は第１実施形態の変形例であり、署名σ＝（ｒ，ｓ）を構成するｒを簡略化した例である。すなわち、第１実施形態においてr=H0(R)(+)H1(H0(R), mrec)|mrec(+)H2(H0(R),H1(H0(R),mrec))としていたのに対し、第３実施形態ではr=H1(R, mrec)|mrec(+) H2(R, H1(R, mrec))とする。これにより演算量を削減できる。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【０１１０】
＜全体構成＞
第１実施形態の署名システム１の署名生成装置１０が署名生成装置２１０に置換され、署名検証装置２０が署名検証装置２２０に置換された構成である。
【０１１１】
＜署名生成装置２１０の構成＞
次に、署名生成装置２１０の構成を説明する。
【０１１２】
［ハードウェア構成］
第１実施形態の署名生成装置１０と同じである。
【０１１３】
［ハードウェアとプログラムとの協働］
署名生成装置２１０もコンピュータに所定のプログラムが読み込まれることにより構成される。
図１４は、このように構成される第３実施形態における署名生成装置２１０の機能構成を例示したブロック図である。なお、署名生成装置２１０において署名生成装置１０と共通する部分には図３と同じ符号を付して説明を簡略化する。
図１４に示すように、本形態の署名生成装置２１０は、記憶部１０ａと、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、入力部１０ｄと、メッセージ分割部１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部２１０ｉ，２１０ｊ，２１０ｐと、排他的論理和演算部１０ｋと、ビット結合部２１０ｍと、整数演算部１０ｑと、通信部１０ｒと、制御部１０ｓと、一時メモリ１０ｔとを有する。
【０１１４】
なお、ハッシュ演算部２１０ｉ，２１０ｊ，２１０ｐとビット結合部２１０ｍとは、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。
また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名生成装置２１０の機能をコンピュータに実行させるためのプログラムに相当する。
【０１１５】
＜署名検証装置２２０の構成＞
次に、署名検証装置２２０の構成を説明する。
【０１１６】
［ハードウェア構成］
第１実施形態の署名検証装置２０と同じである。
【０１１７】
［ハードウェアとプログラムとの協働］
署名検証装置２２０もコンピュータに所定のプログラムが読み込まれることにより構成される。図１１は、このように構成される第２実施形態の署名検証装置１２０の機能構成を例示したブロック図である。
図１５に示すように、本形態の署名検証装置２２０は、記憶部２０ａと、通信部２０ｂと、ビット長抽出部２０ｃと、ハッシュ演算部２０ｄ，２２０ｉ，２２０ｋと、群演算部２０ｅと、ビット抽出部２０ｈと、排他的論理和演算部２０ｊと、比較部２０ｌと、出力部２０ｍと、制御部２０ｎと、一時メモリ２０ｐとを有する。
【０１１８】
なお、ハッシュ演算部２２０ｉ，２２０ｋと比較部２０ｌは、処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成されるものである。また、上記のプログラムは単体でその機能を実現できるものでもよいし、当該プログラムがさらに他のライブラリ（記載していない）を読み出して各機能を実現するものでもよい。すなわち、各プログラムの少なくとも一部が、署名検証装置１２０の機能をコンピュータに実行させるためのプログラムに相当する。
【０１１９】
＜処理＞
次に、本形態の処理について説明する。
【０１２０】
［前処理］
ハッシュ関数Ｈ０が設定されない点が第１実施形態との相違点である。
【０１２１】
［鍵生成処理］
第１実施形態と同じである。
【０１２２】
［署名生成処理］
次に、第３実施形態の署名生成処理について説明する。
【０１２３】
図１６は、第３実施形態の署名生成処理を説明するためのフローチャートである。以下、第１実施形態との相違点を中心に説明する。
まず、署名生成装置２１０が、第１実施形態のステップＳ１１〜Ｓ１４と同じ処理を実行する（ステップＳ２１１〜Ｓ２１４）。次に、ハッシュ演算部１０ｉが、記憶部１０ａからステップＳ１１４の演算結果Ｒとリカバリメッセージｍｒｅｃとビット長パラメータＬとを読み込む。ハッシュ演算部１０ｉは、入力値に対してＬビットのハッシュ値を出力するハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、演算結果Ｒとリカバリメッセージｍｒｅｃとに依存して定まる値αに作用させ（式（６））、その演算結果であるＬビットのハッシュ値ｈを記憶部１０ａに出力して格納する（ステップＳ２１５）。なお、第３実施形態では、αは演算結果Ｒ∈Ｇとリカバリメッセージｍｒｅｃとのみに依存する値α＝（Ｒ，ｍｒｅｃ）である。なお、巡回群Ｇが有限体の乗法群であった場合、本形態のαの構成は、ΠがＲに置換される点を除き、第１実施形態と同様である。また、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群である場合、本形態のαの構成は、Πが、楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値（例えば、点Ｒのｘ座標若しくはｙ座標、又は、点Ｒのｘ座標とｙ座標とのビット結合値）に置換される点を除き、第１実施形態と同様である。
【０１２４】
次に、ハッシュ演算部２１０ｊが、記憶部１０ａから演算結果Ｒとハッシュ値ｈとリカバリメッセージのビット長Ｍとを読み込む。ハッシュ演算部２１０ｊは、リカバリメッセージｍｒｅｃのビット長Ｍに応じて出力ビット長がＭビットに定まるハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、演算結果Ｒとハッシュ値ｈとに依存して定まる値βに作用させ（式（７））、その演算結果であるＭビットのハッシュ値ｕを記憶部１０ａに出力して格納する（ステップＳ２１６）。なお、第３実施形態では、βは演算結果Ｒとハッシュ値ｈとのみに依存する値β＝（Ｒ，ｈ）である。なお、巡回群Ｇが有限体の乗法群であった場合、本形態のβの構成は、ΠがＲに置換される点を除き、第１実施形態と同様である。また、巡回群Ｇが楕円曲線Ｅ上の有理点のなす群である場合、本形態のβの構成は、Πが、楕円曲線Ｅ上の点である演算結果Ｒを一義的又は限定的に特定できる値（例えば、点Ｒのｘ座標若しくはｙ座標、又は、点Ｒのｘ座標とｙ座標とのビット結合値）に置換される点を除き、第１実施形態と同様である。
【０１２５】
次に、排他的論理和演算部１０ｋが、記憶部１０ａからリカバリメッセージｍｒｅｃとハッシュ値ｕとを読み込む。排他的論理和演算部１０ｋは、リカバリメッセージｍｒｅｃとハッシュ値ｕとの排他的論理和ｗ（式（８））を算出し、当該排他的論理和値ｗを記憶部１０ａに出力して格納する（ステップＳ２１７）。
【０１２６】
次に、ビット結合部２１０ｍが、記憶部１０ａからハッシュ値ｈ∈｛０，１｝Ｌと排他的論理和値ｗ∈｛０，１｝Ｍとを読み込む。ビット結合部２１０ｍは、ハッシュ値ｈ∈｛０，１｝Ｌを第１ビット位置に配置し、排他的論理和値ｗ∈｛０，１｝Ｍを第２ビット位置に配置したＬ＋Ｍビットのビット結合値
r=h|w∈{0,1}L+M  …(24)
を算出し、当該ビット結合値ｒを記憶部１０ａに出力して格納する（ステップＳ２１８）。「第１ビット位置」及び「第２ビット位置」をどのビット位置にするかについては第１実施形態と同様である。
その後、第１実施形態のステップＳ２１〜Ｓ２３と同じ処理が実行される（ステップＳ２１９〜Ｓ２２１）。
【０１２７】
［署名検証処理］
次に、第３実施形態の署名検証処理について説明する。
図１７は、第１実施形態の署名検証処理を説明するためのフローチャートである。以下、第１実施形態との相違点を中心に説明する。
【０１２８】
まず、署名検証装置２２０が、第１実施形態のステップＳ４１〜Ｓ４４と同じ処理を実行する（ステップＳ２４１〜Ｓ２４４）。
【０１２９】
次に、ビット抽出部２２０ｈが、記憶部２０ａから署名σ’＝（ｒ’，ｓ’）のｒ’とリカバリメッセージｍｒｅｃ’のビット長Ｍ’とを読み込む。ビット抽出部２２０ｈは、ｒ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌと、ｒ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍ’とを抽出し、それらを記憶部２０ａに格納する（ステップＳ２４５）。なお、「第１ビット位置」及び「第２ビット位置」は、署名生成装置２１０の処理での「第１ビット位置」及び「第２ビット位置」と同一（ｄ＝ｄ’とした場合に同一）とする。
【０１３０】
次に、ハッシュ演算部２２０ｉが、記憶部２０ａからステップＳ２４４での演算結果Ｒ’とｈ’とリカバリメッセージｍｒｅｃ’のビット長Ｍ’とを読み込む。ハッシュ演算部２０ｉは、署名生成装置２１０と同一のハッシュ関数Ｈ２：｛０，１｝＊→｛０，１｝Ｍを、演算結果Ｒ’と値ｈ’とに依存して定まる値β’に作用させ（式（１８））、その演算結果であるＭ’ビットのハッシュ値ｕ’を記憶部２０ａに出力して格納する（ステップＳ２４６）。なお、β’の構成方法は署名生成装置２１０でのβの構成方法と同一（Π＝Π’とし、ｈ＝ｈ’とした場合に同一）とする。
【０１３１】
次に、排他的論理和演算部２０ｊが、記憶部２０ａから値ｗ’∈｛０，１｝Ｍ’とハッシュ値ｕ’とを読み込む。排他的論理和演算部２０ｊは、値ｗ’とハッシュ値ｕ’との排他的論理和を算出し（式（１０））、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍ’として記憶部２０ａに出力して格納する（ステップＳ２４７）。
【０１３２】
次に、ハッシュ演算部２２０ｋが、記憶部２０ａから演算結果Ｒ’とリカバリメッセージｍｒｅｃ’とを読み込む。ハッシュ演算部２２０ｋは、署名生成装置２１０と同一のハッシュ関数Ｈ１：｛０，１｝＊→｛０，１｝Ｌを、演算結果Ｒ’とリカバリメッセージｍｒｅｃ’とに依存して定まる値α’に作用させ、その演算結果であるＬビットのハッシュ値（式（２０））を記憶部２０ａに出力して格納する（ステップＳ２４８）。なお、α’の構成方法は署名生成装置２１０でのαの構成方法と同一（Π＝Π’とし、ｍｒｅｃ＝ｍｒｅｃ’とした場合に同一）とする。
【０１３３】
その後、第１実施形態のステップＳ５１〜Ｓ５４と同じ処理が実行される（ステップＳ２４９〜Ｓ２５２）。
【０１３４】
〔第４実施形態〕
次に、本発明の第４実施形態について説明する。本形態は第３実施形態の変形例である。第４実施形態ではクリアメッセージを用いない。この点が第３実施形態との相違点である。以下では、第１〜３実施形態との相違点を中心に説明し、第１〜３実施形態と共通する事項については説明を省略する。
【０１３５】
＜全体構成＞
第１実施形態の署名システム１の署名生成装置１０が署名生成装置３１０に置換され、署名検証装置２０が署名検証装置３２０に置換された構成である。
【０１３６】
＜署名生成装置３１０の構成＞
次に、署名生成装置３１０の構成を説明する。
【０１３７】
［ハードウェア構成］
第１実施形態の署名生成装置１０と同じである。
【０１３８】
［ハードウェアとプログラムとの協働］
署名生成装置３１０もコンピュータに所定のプログラムが読み込まれることにより構成される。
図１８は、このように構成される第４実施形態における署名生成装置３１０の機能構成を例示したブロック図である。なお、署名生成装置４１０において署名生成装置１０，１１０，２１０と共通する部分には図３，図１０，図１４と同じ符号を付して説明を簡略化する。
図１８に示すように、本形態の署名生成装置３１０は、記憶部１０ａと、秘密鍵生成部１０ｂと、公開鍵生成部１０ｃと、入力部１１０ｄと、ビット長抽出部１１０ｅと、任意値生成部１０ｆと、群演算部１０ｇと、ハッシュ演算部２１０ｉ，２１０ｊ，１１０ｐと、排他的論理和演算部１０ｋと、ビット結合部２１０ｍと、整数演算部１０ｑと、通信部１１０ｒと、制御部１０ｓと、一時メモリ１０ｔとを有する。
【０１３９】
＜署名検証装置３２０の構成＞
次に、署名検証装置３２０の構成を説明する。
【０１４０】
［ハードウェア構成］
第１実施形態の署名検証装置２０と同じである。
【０１４１】
［ハードウェアとプログラムとの協働］
署名検証装置３２０もコンピュータに所定のプログラムが読み込まれることにより構成される。図１９は、このように構成される第２実施形態の署名検証装置１２０の機能構成を例示したブロック図である。なお、署名検証装置３２０において署名検証装置２０，１２０，２２０と共通する部分には図５，図１１，図１５と同じ符号を付して説明を簡略化する。
図１９に示すように、本形態の署名検証装置３２０は、記憶部２０ａと、通信部１２０ｂと、ビット長抽出部２０ｃと、ハッシュ演算部１２０ｄ，２２０ｉ，２２０ｋと、群演算部２０ｅと、ビット抽出部２２０ｈと、排他的論理和演算部２０ｊと、比較部２０ｌと、出力部２０ｍと、制御部２０ｎと、一時メモリ２０ｐとを有する。
【０１４２】
＜処理＞
次に、本形態の処理について説明する。
【０１４３】
［前処理・鍵生成処理］
第１実施形態と同じである。
【０１４４】
［署名生成処理］
次に、第４実施形態の署名生成処理について説明する。
図２０は、第４実施形態の署名生成処理を説明するためのフローチャートである。以下、図２０に従って本形態の署名生成処理を説明する。
まず、署名生成装置３１０が、第２実施形態のステップＳ１１１〜Ｓ１１４と同じ処理を実行し（ステップＳ３１１〜Ｓ３１４）、次に、第３実施形態のステップＳ２１５〜Ｓ２１８と同じ処理を実行する（ステップＳ３１５〜Ｓ３１８）。次に、署名生成装置３１０が、第２実施形態のステップＳ１２１〜１２３と同じ処理を実行する（ステップＳ３１９〜Ｓ３２１）。
【０１４５】
［署名検証処理］
次に、第４実施形態の署名検証処理について説明する。
図２１は、第４実施形態の署名検証処理を説明するためのフローチャートである。以下、図２１に従って本形態の署名検証処理を説明する。
まず、署名検証装置３２０が、第２実施形態のステップＳ１４１〜Ｓ１４４と同じ処理を実行し（ステップＳ３４１〜Ｓ３４４）、次に、第３実施形態のステップＳ２４５〜２５２と同じ処理を実行する（ステップＳ３４５〜Ｓ３５２）。
【０１４６】
〔署名検証となる理由〕
次に、署名検証装置２０，１２０，２２０，３２０の処理が署名検証となる理由について説明する。
【０１４７】
＜第１，２実施形態について＞
署名検証装置２０，１２０では、署名σ’＝（ｒ’，ｓ’）を用い、ｒ’に依存して定まる値γ’に対してハッシュ値ｔ’＝Ｈ３（γ’）を演算し（式（１４）（２３））、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行い（式（１５））、ハッシュ値Π’＝Ｈ０（Ｒ’）の演算を行っている（式（１６））。署名σ’が正規なものであればｒ’＝ｒ及びｓ’＝ｓ（ｓ＝ｋ−ｔ・ｘ∈Ｚ）を満たすため、γ’＝γを満たし、ｔ’＝Ｈ３（γ’）＝Ｈ３（γ）＝ｔを満たし、ｙ＝ｇｘ∈Ｇを満たすため、Ｒ’＝ｇｓ’・ｙｔ’＝ｇｓ・ｙｔ＝ｇｋ−ｔ・ｘ・ｇｔ・ｘ＝ｇｋ∈Ｇとなる。そのため、Π’＝Ｈ０（Ｒ’）＝Ｈ０（ｇｋ）＝Πとなる。
【０１４８】
また、署名検証装置２０，１２０では、排他的論理和値ｄ’＝Π’（＋）ｒ’を求めているが（式（１７））、署名σ’が正規なものであればｒ’＝ｒを満たし、ｒ＝Π（＋）ｄを満たし、Π’＝Πを満たすため、ｄ’＝ｄを満たす。さらに、署名検証装置２０，１２０では、ハッシュ値Π’と排他的論理和値ｄ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’のハッシュ値ｕ’＝Ｈ２（β’）を求めているが（式（１８））、署名σ’が正規なものであればｄ’＝ｄを満たすため、ｈ’＝ｈを満たし、さらにΠ’＝Πを満たすため、β’＝βを満たし、ｕ’＝ｕを満たす。
【０１４９】
さらに、署名検証装置２０，１２０では、排他的論理和値ｄ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍとハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍとしているが（式（１９））、署名σ’が正規なものであればｕ’＝ｕ、Ｍ’＝Ｍ及びｄ’＝ｄを満たす。この場合、ｗ’＝ｗも満たすため、ｍｒｅｃ’＝ｗ’（＋）ｕ’＝ｗ（＋）ｕ＝ｍｒｅｃ（＋）ｕ（＋）ｕ＝ｍｒｅｃを満たす。
【０１５０】
その後、署名検証装置２０，１２０では、ハッシュ値Π’とリカバリメッセージｍｒｅｃ’とに依存して定まる値α’にハッシュ値Ｈ１を作用させたハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを求めている（式（２０））。署名σ’が正規なものであればΠ’＝Π，ｍｒｅｃ’＝ｍｒｅｃ，α’＝α，ｈ’＝ｈを満たし、署名生成装置ではｈ＝Ｈ１（α）としていたため、ｈ’＝Ｈ１（α’）も満たす。つまり、署名σ’が正規なものであればｈ’＝Ｈ１（α’）を満たすことがいえる。
【０１５１】
一方、巡回群Ｇでの離散対数問題の求解が困難であると仮定すると、秘密鍵ｘを知らない第三者は公開鍵ｙ＝ｇｘ∈Ｇから秘密鍵ｘを知ることができず、上記の検証に合格する署名σ’＝（ｒ’，ｓ’）を生成することができない。よって、上記の検証に合格する署名σ’＝（ｒ’，ｓ’）が秘密鍵ｘを知る者が正規に生成した署名であるといえる。
【０１５２】
＜第３，４実施形態について＞
署名検証装置２２０，３２０では、署名σ’＝（ｒ’，ｓ’）を用い、ｒ’に依存して定まる値γ’に対してハッシュ値ｔ’＝Ｈ３（γ’）を演算し、Ｒ’＝ｇｓ’・ｙｔ’∈Ｇの演算を行っている。署名σ’が正規なものであればｒ’＝ｒ及びｓ’＝ｓ（ｓ＝ｋ−ｔ・ｘ∈Ｚ）を満たすため、γ’＝γを満たし、ｔ’＝Ｈ３（γ’）＝Ｈ３（γ）＝ｔを満たし、ｙ＝ｇｘ∈Ｇを満たすため、Ｒ’＝ｇｓ’・ｙｔ’＝ｇｓ・ｙｔ＝ｇｋ−ｔ・ｘ・ｇｔ・ｘ＝ｇｋ＝Ｒとなる。
【０１５３】
また、署名検証装置２２０，３２０では、演算結果Ｒ’と署名σ’のｒ’の第１ビット位置のＬビットの値ｈ’∈｛０，１｝Ｌとに依存して定まる値β’のハッシュ値ｕ’＝Ｈ２（β’）を求めているが、署名σ’が正規なものであればｒ’＝ｒを満たすため、ｈ’＝ｈを満たし、さらにＲ’＝Ｒを満たすため、β’＝βを満たし、ｕ’＝ｕを満たす。        
【０１５４】
さらに、署名検証装置２２０，３２０では、署名σ’のｒ’の第２ビット位置のＭ’ビットの値ｗ’∈｛０，１｝Ｍとハッシュ値ｕ’との排他的論理和ｗ’（＋）ｕ’を算出し、その演算結果をリカバリメッセージｍｒｅｃ’∈｛０，１｝Ｍとしているが）、署名σ’が正規なものであればｕ’＝ｕ、Ｍ’＝Ｍ及びｒ’＝ｒを満たす。この場合、ｗ’＝ｗも満たすため、ｍｒｅｃ’＝ｗ’（＋）ｕ’＝ｗ（＋）ｕ＝ｍｒｅｃ（＋）ｕ（＋）ｕ＝ｍｒｅｃを満たす。
【０１５５】
その後、署名検証装置２２０，３２０では、演算結果Ｒ’とリカバリメッセージｍｒｅｃ’とに依存して定まる値α’にハッシュ値Ｈ１を作用させたハッシュ値Ｈ１（α’）∈｛０，１｝Ｌを求めている。署名σ’が正規なものであればＲ’＝Ｒ，ｍｒｅｃ’＝ｍｒｅｃ，α’＝α，ｈ’＝ｈを満たし、署名生成装置ではｈ＝Ｈ１（α）としていたため、ｈ’＝Ｈ１（α’）も満たす。つまり、署名σ’が正規なものであればｈ’＝Ｈ１（α’）を満たすことがいえる。
【０１５６】
一方、巡回群Ｇでの離散対数問題の求解が困難であると仮定すると、秘密鍵ｘを知らない第三者は公開鍵ｙ＝ｇｘ∈Ｇから秘密鍵ｘを知ることができず、上記の検証に合格する署名σ’＝（ｒ’，ｓ’）を生成することができない。よって、上記の検証に合格する署名σ’＝（ｒ’，ｓ’）が秘密鍵ｘを知る者が正規に生成した署名であるといえる。
【０１５７】
〔変形例〕
本発明は上述の各実施の形態に限定されるものではない。例えば、第１，２実施形態では、αをΠとｍｒｅｃとのみに依存する値とし、α’をΠ’とｍｒｅｃ’とのみに依存する値とした。しかし、αをΠとｍｒｅｃと第三情報とに依存する値とし、α’をΠ’とｍｒｅｃ’と第三情報とに依存する値としてもよい。なお、第三情報としては、クリアメッセージｍｃｌｒや公開鍵ｙや群Ｇを特定するためのパラメータなどを例示できる。βとβ’及びγとγ’についても同様である。これにより、署名検証精度をより向上させることができる。特に、第三情報として群Ｇを特定するためのパラメータを用いた場合には、不正な群（例えば、離散対数問題が容易であって群演算部２０ｅでの演算結果が正規の巡回群Ｇでの演算結果と同一となる群）を用いて生成された不正な署名が検証に合格してしまうことを防止できる。
【０１５８】
同様に、第３，４実施形態では、αをＲとｍｒｅｃとのみに依存する値とし、α’をＲ’とｍｒｅｃ’とのみに依存する値とした。しかし、αをＲとｍｒｅｃと第三情報とに依存する値とし、α’をＲ’とｍｒｅｃ’と第三情報とに依存する値としてもよい。βとβ’及びγとγ’についても同様である。
【０１５９】
また、各実施形態では、署名生成装置１０，１１０，２１０，３１０が鍵生成を行ったが、別の装置が鍵生成を行ってもよい。また、各実施形態では、公開鍵サーバ装置３０が公開鍵ｙを公開したが署名生成装置１０，１１０，２１０，３１０が署名検証装置２０，１２０，２２０，３２０に公開鍵ｙを送信する構成であってもよい。また、各処理におけるＺｑ（ｑを法とする完全剰余系）をＺ（整数）に置換した構成であってもよい。
【０１６０】
また、各実施形態では、署名検証装置２０，１２０，２２０，３２０が、署名σ’が具備するｒ’のビット長とビット長パラメータＬとからリカバリメッセージのビット長を算出したが、署名生成装置１０，１１０，２１０，３１０が署名検証装置２０，１２０，２２０，３２０にリカバリメッセージのビット長を送信する構成であってもよい。
【０１６１】
また、本発明における「ハッシュ関数」とは、あるデータに対し、そのデータを代表する値を算出する関数を意味する。本発明では、ＳＨＡ−１やＭＤ５等のみならず、例えば、ＤＥＳやＣａｍｅｌｌｉａなどの共通鍵暗号関数に共通鍵を代入したものをハッシュ関数として用いることもできる。
【０１６２】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１６３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１６４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１６７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１６８】
本発明は、電子署名を用いる様々な用途に適用可能である。
【図面の簡単な説明】
【０１６９】
【図１】図１は、第１実施形態の署名システムの全体構成を示した概念図である。
【図２】図２は、第１実施形態における署名生成装置のハードウェア構成を例示したブロック図である。
【図３】図３は、第１実施形態における署名生成装置の機能構成を例示したブロック図である。
【図４】図４（ａ）は、ハッシュ演算部の機能構成の詳細を示した図であり、図４（ｂ）は、ハッシュ演算部の機能構成の詳細を示した図である。
【図５】図５は、第１実施形態の署名検証装置の機能構成を例示したブロック図である。
【図６】図６は、第１実施形態の署名生成処理を説明するためのフローチャートである。
【図７】図７（ａ）は、ステップＳ１５の処理の例を説明するためのフローチャートであり、図７（ｂ）は、ステップＳ１７の処理の例を説明するためのフローチャートである。
【図８】図８は、第１実施形態の署名検証処理を説明するためのフローチャートである。
【図９】図９（ａ）（ｂ）（ｃ）は「第１ビット位置」及び「第２ビット位置」の設定例を示した図である。
【図１０】図１０は、第２実施形態における署名生成装置の機能構成を例示したブロック図である。
【図１１】図１１は、第２実施形態の署名検証装置の機能構成を例示したブロック図である。
【図１２】図１２は、第２実施形態の署名生成処理を説明するためのフローチャートである。
【図１３】図１３は、第２実施形態の署名検証処理を説明するためのフローチャートである。
【図１４】図１４は、第３実施形態における署名生成装置の機能構成を例示したブロック図である。
【図１５】図１５は、第３実施形態の署名検証装置の機能構成を例示したブロック図である。
【図１６】図１６は、第３実施形態の署名生成処理を説明するためのフローチャートである。
【図１７】図１７は、第３実施形態の署名検証処理を説明するためのフローチャートである。
【図１８】図１８は、第４実施形態における署名生成装置の機能構成を例示したブロック図である。
【図１９】図１９は、第４実施形態の署名検証装置の機能構成を例示したブロック図である。
【図２０】図２０は、第４実施形態の署名生成処理を説明するためのフローチャートである。
【図２１】図２１は、第４実施形態の署名検証処理を説明するためのフローチャートである。
【符号の説明】
【０１７０】
１  署名システム
１０，１１０，２１０，３１０  署名生成装置
２０，１２０，２２０，３２０  署名検証装置
【図１】
2008136193.tif 000003
【図２】
2008136193.tif 000004
【図３】
2008136193.tif 000005
【図４】
2008136193.tif 000006
【図５】
2008136193.tif 000007
【図６】
2008136193.tif 000008
【図７】
2008136193.tif 000009
【図８】
2008136193.tif 000010
【図９】
2008136193.tif 000011
【図１０】
2008136193.tif 000012
【図１１】
2008136193.tif 000013
【図１２】
2008136193.tif 000014
【図１３】
2008136193.tif 000015
【図１４】
2008136193.tif 000016
【図１５】
2008136193.tif 000017
【図１６】
2008136193.tif 000018
【図１７】
2008136193.tif 000019
【図１８】
2008136193.tif 000020
【図１９】
2008136193.tif 000021
【図２０】
2008136193.tif 000022
【図２１】
2008136193.tif 000023