(57)【要約】ノルム０ベクトル偽造攻撃を防ぐことが可能な署名生成装置および署名検証装置を提供する。  署名生成装置（１１０）は、メッセージ（ｍ）に対する署名データ（Ｓ）を、秘密鍵格納部（１１２）に格納されている秘密鍵を用いて生成し、その署名データ（Ｓ）のノルムが変化することなく、署名データ（Ｓ）に含まれるＮ個の要素のうち一つ目の要素が０となるように、その署名データ（Ｓ）の形式を変換する署名生成部（１１４）を備える。署名検証装置（１２０）は、署名データ（Ｓ）に含まれるＮ個の要素のうち一つ目の要素が０であるか否かを判定し、０でないと判定したときには、署名データ（Ｓ）を不正なものとして扱う署名検証部（１２４）を備える。
2006114948.tif 000002
【特許請求の範囲】
【請求項１】
署名方式を用いてメッセージデータに対する署名データを生成する署名生成装置であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記署名生成装置は、
前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成手段と、
前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換手段と
を備えることを特徴とする署名生成装置。
【請求項２】
前記署名変換手段は、前記対象要素が０からｑ−１の何れかの整数となるように、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項３】
前記署名変換手段は、前記対象要素が０となるように、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項４】
前記署名生成装置は、さらに、
前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成するハッシュ値生成手段を備え、
前記署名変換手段は、
前記対象要素が、前記ハッシュ値を示す２つのＮ次元配列に含まれる２・Ｎ個（ここで・は整数の乗算を示す。）の要素のうち何れか１つの値となるように、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項５】
前記署名変換手段は、
前記署名データにより示される多項式の０次の項に対応する要素が予め定められた値となるように、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項６】
前記署名変換手段は、
ノルムが０のベクトルであるノルム０ベクトルを前記署名データから減算することにより、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項７】
前記署名変換手段は、
全て同じ値の要素からなるＮ次元配列として構成される前記ノルム０ベクトルを前記署名データから減算する
ことを特徴とする請求項６記載の署名生成装置。
【請求項８】
前記署名生成装置は、さらに、
前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成し、前記Ｎ次元配列ごとに、当該Ｎ次元配列のノルムが変化することなく、当該Ｎ次元配列に含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記各Ｎ次元配列の形式を変換するハッシュ値生成手段を備え、
前記署名生成手段は、
前記組｛ｆ，ｇ，Ｆ，Ｇ｝のそれぞれの元の形式が、当該元に含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように整えられている前記秘密鍵と、前記ハッシュ値生成手段により形式が変換されたハッシュ値とを用いて前記署名データを生成する
ことを特徴とする請求項１記載の署名生成装置。
【請求項９】
署名方式を用いてメッセージデータに対する署名データを検証する署名検証装置であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記署名検証装置は、
前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定手段と、
前記環Ｒの元である前記署名データを、前記公開鍵を用いて検証する署名検証手段と
を備えることを特徴とする署名検証装置。
【請求項１０】
前記署名形式判定手段は、前記対象要素が、０からｑ−１の複数の整数の中から予め選択された１つの整数であるか否かを判定する
ことを特徴とする請求項９記載の署名検証装置。
【請求項１１】
前記署名形式判定手段は、前記対象要素が０であるか否かを判定する
ことを特徴とする請求項９記載の署名検証装置。
【請求項１２】
前記署名生成装置は、さらに、
前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成するハッシュ値生成手段を備え、
前記署名形式判定手段は、
前記対象要素の値が、前記ハッシュ値を示す２つのＮ次元配列に含まれる２・Ｎ個（ここで・は整数の乗算を示す。）の要素のうち何れか１つの値であるか否かを判定する
ことを特徴とする請求項９記載の署名検証装置。
【請求項１３】
前記署名形式判定手段は、
前記署名データにより示される多項式の０次の項に対応する要素が予め定められた値であるか否かを判定する
ことを特徴とする請求項９記載の署名検証装置。
【請求項１４】
前記署名検証手段は、
前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成し、前記Ｎ次元配列ごとに、当該Ｎ次元配列のノルムが変化することなく、当該Ｎ次元配列の要素のうち何れか１つの対象要素が予め定められた値となるように、前記各Ｎ次元配列の形式を変換するハッシュ値生成手段と、
前記元ｈに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように形式が整えられている前記公開鍵と、前記署名データとの積を前記環Ｒの元ｔとして算出し、前記元ｔのノルムが変化することなく、前記元ｔに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記元ｔの形式を変換することにより、形式が変換された前記元ｔと署名データとからなる署名ベクトルを生成する署名ベクトル生成手段と、
前記署名ベクトル生成手段により生成された署名ベクトルと、前記ハッシュ値生成手段により形式が変換されたハッシュ値との距離に基づいて、前記署名データを検証する距離判定手段とを備える
ことを特徴とする請求項９記載の署名検証装置。
【請求項１５】
署名方式を用いてメッセージデータに対する署名データを生成する署名生成方法であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記署名生成方法は、
前記署名生成ステップと、
前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換ステップと
を含むことを特徴とする署名生成方法。
【請求項１６】
署名方式を用いてメッセージデータに対する署名データを検証する署名検証方法であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記署名検証方法は、
前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定手段と、
前記署名検証ステップと
を含むことを特徴とする署名検証方法。
【請求項１７】
署名方式を用いてメッセージデータに対する署名データを生成するためのプログラムであって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記プログラムは、
前記署名生成ステップと、
前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換ステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項１８】
署名方式を用いてメッセージデータに対する署名データを検証するためのプログラムであって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記プログラムは、
前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定ステップと、
前記署名検証ステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項１９】
署名方式を用いてメッセージデータに対する署名データを生成する集積回路であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記集積回路は、
前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成手段と、
前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換手段と
を備えることを特徴とする集積回路。
【請求項２０】
署名方式を用いてメッセージデータに対する署名データを検証する集積回路であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記集積回路は、
前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定手段と、
前記環Ｒの元である前記署名データを、前記公開鍵を用いて検証する署名検証手段と
を備えることを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、情報セキュリティ技術としての暗号技術に関し、特に、ディジタル署名に基づく処理を行う署名生成装置および署名検証装置に関する。
【背景技術】
【０００２】  受信装置から送信装置へデータを送信する際の送信者の特定及びデータの改ざんを防止するための技術として、公開鍵暗号の一種であるディジタル署名方式がある。【０００３】  このディジタル署名方式では、送信装置が、送信したいデータに対し、送信装置の秘密鍵を用いて署名データを作成し、送信したいデータと共に署名データを受信装置へ送信する。受信装置は、送信装置の公開鍵を用いて署名データを検証し、改ざんされているか否かを判定する（例えば、非特許文献１参照）。なお、公開鍵から秘密鍵の値は計算困難である。【０００４】  最近、高速処理が可能な公開鍵暗号として、ＮＴＲＵ（エヌティーアールユー・クリプトシステムズ・インコーポレーテッドの登録商標）暗号が提案された（例えば、非特許文献２参照）。このＮＴＲＵ暗号は、ある法の下でべき乗剰余演算を行うＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）暗号や楕円曲線上の点のスカラ倍演算を行う楕円曲線暗号に比べ、高速に演算可能な多項式演算により暗号化と復号化を行う。したがって、ＮＴＲＵ暗号は、従来の公開鍵暗号よりも高速に処理することが可能で、ソフトウェアの処理でも実用的な時間で処理可能である。【０００５】  つまり、公開鍵暗号にＮＴＲＵ暗号を用いた暗号通信システムでは、従来の公開鍵暗号を用いた暗号通信システムよりも、送信装置及び受信装置の処理が高速に行えるという利点がある。【０００６】  ところで、上記非特許文献２で提案された方式は、データを暗号化する守秘暗号方式であったが、その後、ＮＴＲＵ暗号のディジタル署名方式が提案された（例えば、非特許文献３参照）。このようなディジタル署名方式は、解読法の出現などで、その方式が幾度か変更された。【０００７】  以下では、ＮＴＲＵＳｉｇｎと呼ばれるディジタル署名方式（以下、ＮＴＲＵＳｉｇｎ署名方式という）について簡単に説明する（例えば、特許文献１および非特許文献４参照）。【０００８】  ＜ＮＴＲＵＳｉｇｎ署名方式＞
（１）ＮＴＲＵＳｉｇｎ署名方式のパラメータ
ＮＴＲＵＳｉｇｎ署名方式では、非負整数のパラメータである、Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄが使用される。以下に、これらのパラメータの意味を説明する。【０００９】  （ｉ）パラメータＮ
ＮＴＲＵＳｉｇｎ署名方式は、多項式の演算により署名生成及び署名検証を行うディジタル署名方式である。ＮＴＲＵＳｉｇｎ署名方式で扱う多項式の次数は、上記パラメータＮにより決まる。【００１０】  ＮＴＲＵＳｉｇｎ署名方式で扱う多項式は、上記パラメータＮに対し、Ｎ−１次以下の整数係数多項式であり、例えばＮ＝５のとき、Ｘ＾４＋Ｘ＾３＋１等の多項式である。ここで、「Ｘ＾ａ」はＸのａ乗を意味する。また、公開鍵ｈおよび署名ｓはいずれも、Ｎ−１次以下の多項式として表現される。また、秘密鍵は４つのＮ−１次以下の多項式対（ｆ，ｇ，Ｆ，Ｇ）である。すなわち、ｆ，ｇ，Ｆ，ＧはいずれもＮ−１次以下の多項式である。なお、以下では、４つの多項式からなる組（ｆ，ｇ，Ｆ，Ｇ）を、２つの対（ｆ，ｇ），（Ｆ，Ｇ）のさらなる対と捉えて、｛（ｆ，ｇ），（Ｆ，Ｇ）｝と表記する場合もある。【００１１】  そして、多項式演算は、上記パラメータＮに対し、Ｘ＾Ｎ＝１という関係式を用いて、演算結果が常にＮ−１次以下の多項式になるように演算される。例えば、Ｎ＝５の場合、多項式Ｘ＾４＋Ｘ＾２＋１と多項式Ｘ＾３＋Ｘの積は、多項式と多項式の積を×、整数と多項式の積（あるいは整数と整数の積）を・とすると、Ｘ＾５＝１という関係から、
（Ｘ＾４＋Ｘ＾２＋１）×（Ｘ＾３＋Ｘ）
＝Ｘ＾７＋２・Ｘ＾５＋２・Ｘ＾３＋Ｘ
＝Ｘ＾２・１＋２・１＋２・Ｘ＾３＋Ｘ
＝２・Ｘ＾３＋Ｘ＾２＋Ｘ＋２
というように、常にＮ−１次以下の多項式になるように演算される。【００１２】  なお、ＮＴＲＵＳｉｇｎ署名方式では、Ｎ−１次の多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）はベクトル（ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１））と同一視される。ここで、ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１）は多項式ａの係数であり、整数である。【００１３】  （ｉｉ）パラメータｑ
ＮＴＲＵＳｉｇｎ署名方式では、２以上の整数であるパラメータｑを用いる。ＮＴＲＵＳｉｇｎ署名方式で出現する多項式の係数は、ｑを法とした剰余を取る。【００１４】  （ｉｉｉ）パラメータｄｆ，ｄｇ
ＮＴＲＵＳｉｇｎ署名方式で扱う秘密鍵の一部である多項式ｆ及び、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇの選び方は、それぞれパラメータｄｆ，ｄｇにより決まる。【００１５】  まず、多項式ｆは、ｄｆ個の係数が１であり、かつ他の係数は０となるように選ばれる。すなわち、多項式ｆは、Ｎ−１次以下の多項式であり、０次（定数項）からＮ−１次まで、Ｎ個の係数があるが、このＮ個の係数のうち、ｄｆ個の係数が１であり、かつ（Ｎ−ｄｆ）個の係数が０となるように選ばれる。そして、多項式ｇは、ｄｇ個の係数が１であり、かつ他の係数は０となるように選ばれる。【００１６】  （ｉｖ）パラメータＮｏｒｍｂｏｕｎｄ
ＮＴＲＵＳｉｇｎ署名方式では、署名ｓから作られる２・Ｎ次元のベクトルとメッセージデータ（以下、単にメッセージという）のハッシュ値である２・Ｎ次元のベクトルとの距離を計算し、この距離により署名ｓが正しい署名であるかを判定する。Ｎｏｒｍｂｏｕｎｄは、この判定の際に使用されるしきい値である。すなわち、上記距離がＮｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しい署名として受理され、Ｎｏｒｍｂｏｕｎｄ以上であれば、正しくない署名として拒否される。なお、非特許文献４には、ＮＴＲＵＳｉｇｎ署名方式のパラメータの例として、（Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄ）＝（２５１，１２８，７３，７１，３１０）の例が挙げられている。【００１７】  （２）メッセージのハッシュ値、ノルム及びベクトル間の距離
ＮＴＲＵＳｉｇｎ署名方式では、メッセージのハッシュ値に対する署名を作成する。メッセージのハッシュ値は、Ｎ次の多項式の対であり、２・Ｎ次元のベクトルと同一視される。なお、メッセージからハッシュ値を求めるハッシュ関数については、非特許文献１が詳しい。【００１８】  ＮＴＲＵＳｉｇｎ署名方式では、署名検証にベクトル間の距離を用い、このような距離の算出にノルム（Ｃｅｎｔｅｒｅｄノルム）を用いる。以下、ノルムおよびベクトル間の距離の定義を示す。【００１９】  多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）のノルム｜｜ａ｜｜を以下のように定義する。【００２０】    ｜｜ａ｜｜＝ｓｑｒｔ（（ａ＿０−μ）＾２＋（ａ＿１−μ）＾２＋…＋（ａ＿（Ｎ−１）−μ）＾２）
μ＝（１／Ｎ）・（ａ＿０＋ａ＿１＋ａ＿２＋…＋ａ＿（Ｎ−１））
ここで、ｓｑｒｔ（ｘ）はｘの平方根を示す。【００２１】  多項式ａ，ｂの対（ａ，ｂ）のノルム｜｜（ａ，ｂ）｜｜を以下のように定義する。【００２２】    ｜｜（ａ，ｂ）｜｜＝ｓｑｒｔ（｜｜ａ｜｜＾２＋｜｜ｂ｜｜＾２）
多項式ａ，ｂの対（ａ，ｂ）とｃ，ｄの対（ｃ，ｄ）との距離（ベクトル間の距離）は、｜｜（ｃ−ａ，ｄ−ｂ）｜｜で定義される。【００２３】  （３）ＮＴＲＵＳｉｇｎ署名方式の鍵生成
ＮＴＲＵＳｉｇｎ署名方式では、上述したように、パラメータｄｆ，ｄｇを用いてランダムに多項式ｆ，多項式ｇを生成する。そして非特許文献４に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈを生成する。さらに、以下の式を満たすようなノルムが小さい多項式Ｆ，Ｇを求める。【００２４】    ｆ×Ｇ−ｇ×Ｆ＝ｑ
ここで、秘密鍵を｛（ｆ，ｇ），（Ｆ，Ｇ）｝、公開鍵をｈとする。秘密鍵は、署名を生成するための鍵であり、署名生成鍵とも呼ばれる。また、公開鍵は、署名を検証するための鍵であり、署名検証鍵とも呼ばれる。【００２５】  また、ｘ＝ｙ（ｍｏｄ  ｑ）は、多項式ｙの第ｉ次の係数を、剰余が０からｑ−１の範囲に収まるように法ｑで割ったときの剰余を、多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、多項式ｙの各係数を、０から（ｑ−１）の範囲に収まるように（ｍｏｄ  ｑ）演算した多項式を、多項式ｘとする演算である。【００２６】  （４）ＮＴＲＵＳｉｇｎ署名方式の署名生成
ＮＴＲＵＳｉｇｎ署名方式の署名生成では、署名対象であるメッセージｍの署名ｓを計算する。まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を計算する。【００２７】  この２・Ｎ次元のベクトル（ｍ１，ｍ２）と秘密鍵｛（ｆ，ｇ），（Ｆ，Ｇ）｝を用いて、以下の式を満たす多項式ａ，ｂ，Ａ，Ｂを計算する。【００２８】    Ｇ×ｍ１−Ｆ×ｍ２＝Ａ＋ｑ×Ｂ
−ｇ×ｍ１＋ｆ×ｍ２＝ａ＋ｑ×ｂ
ここで、Ａ，ａの係数は〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を取ったものとする。すなわち、法ｑで割ったときの剰余が〈ｑ／２〉からｑ−１である場合は、ｑ減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。【００２９】  次に以下の式より、多項式ｓ，ｔを計算し、多項式ｓを署名として出力する。【００３０】    ｓ＝ｆ×Ｂ＋Ｆ×ｂ（ｍｏｄ  ｑ）
ｔ＝ｇ×Ｂ＋Ｇ×ｂ（ｍｏｄ  ｑ）
図１は、署名ｓの生成方法を説明するための説明図である。【００３１】  ＮＴＲＵＳｉｇｎ署名方式では、秘密鍵行列｛（ｆ，ｇ），（Ｆ，Ｇ）｝により張られる２・Ｎ次元格子上において、メッセージｍに対するハッシュ値Ｈ（ｍ）＝（ｍ１，ｍ２）の最近接格子点Ｐが、上述の式ｓ＝ｆ×Ｂ＋Ｆ×ｂ（ｍｏｄ  ｑ）およびｔ＝ｇ×Ｂ＋Ｇ×ｂ（ｍｏｄ  ｑ）により導出される。つまり、（ｍ１，ｍ２）に最も近い格子点が、最近接格子点Ｐとして見つけ出される。そして、その最近接格子点Ｐを示す署名ベクトル（ｓ，ｔ）のうち、多項式ｓだけが署名として扱われる。【００３２】  （５）ＮＴＲＵＳｉｇｎ署名方式の署名検証
ＮＴＲＵＳｉｇｎ署名方式の署名検証では、署名ｓが署名対象であるメッセージｍの正しい署名であるか否かを検証する。まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）を計算する。【００３３】  公開鍵ｈを用いて、以下の式より、多項式ｔを計算する。【００３４】    ｔ＝ｓ×ｈ（ｍｏｄ  ｑ）
２・Ｎ次元ベクトル（ｓ，ｔ）と（ｍ１，ｍ２）の距離を求め、Ｎｏｒｍｂｏｕｎｄ未満であるかをチェックする。Ｎｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しいと判定してその署名ｓを受理する。Ｎｏｒｍｂｏｕｎｄ以上であれば、署名ｓが不正と判定してその署名ｓを拒否する。【００３５】  図２は、署名ｓの検証方法を説明するための説明図である。【００３６】  ＮＴＲＵＳｉｇｎ署名方式では、署名ｓと公開鍵ｈとを用いた上述の式ｔ＝ｓ×ｈ（ｍｏｄ  ｑ）により、公開鍵行列｛（１，ｈ），（０，ｑ）｝により張られる２・Ｎ次元格子上における格子点Ｐ（ｓ，ｔ）が導出される。ここで、このような２・Ｎ次元格子上において、メッセージｍに対するハッシュ値Ｈ（ｍ）＝（ｍ１，ｍ２）が、格子点Ｐ（ｓ，ｔ）を中心とする半径＝Ｎｏｒｍｂｏｕｎｄの超球内にあるか否かが判定される。超球内にあれば、署名ｓは正しいと判定されて受理され、超球内になければ、署名ｓは不正と判定されて拒否される。
【特許文献１】国際公開第０３／０５０９９８号パンフレット
【非特許文献１】岡本龍明、山本博資、「現代暗号」、産業図書（１９９７年）
【非特許文献２】Ｊ．Ｈｏｆｆｓｔｅｉｎ，Ｊ．Ｐｉｐｈｅｒ，ａｎｄ  Ｊ．Ｈ．Ｓｉｌｖｅｒｍａｎ，“ＮＴＲＵ：Ａ  ｒｉｎｇ  ｂａｓｅｄ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ”，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，１４２３，ｐｐ．２６７−２８８，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９８．
【非特許文献３】Ｊ．Ｈｏｆｆｓｔｅｉｎ，Ｊ．Ｐｉｐｈｅｒ  ａｎｄ  Ｊ．Ｓｉｌｖｅｒｍａｎ，“ＮＳＳ：Ａｎ  ＮＴＲＵ  Ｌａｔｔｉｃｅ−Ｂａｓｅｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ，”Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｐｌｏｇｙ−Ｅｕｒｏｃｒｙｐｔ  ’０１，ＬＮＣＳ，Ｖｏｌ．２０４５，ｐｐ．１２３−１３７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００１
【非特許文献４】Ｊ．Ｈｏｆｆｓｔｅｉｎ，Ｎ．Ｇｒａｈａｍ，Ｊ．Ｐｉｐｈｅｒ，Ｊ．Ｓｉｌｖｅｒｍａｎ  ａｎｄ  Ｗ．Ｗｈｙｔｅ，“ＮＴＲＵＳｉｇｎ：Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  Ｕｓｉｎｇ  ｔｈｅ  ＮＴＲＵ  Ｌａｔｔｉｃｅ，”ＣＴ−ＲＳＡ’０３，ＬＮＣＳ，Ｖｏｌ．２６１２，ｐｐ．１２２−１４０，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００３
【非特許文献５】Ｓ．Ｍｉｎ，Ｇ．Ｙａｍａｍｏｔｏ  ａｎｄ  Ｋ．Ｋｉｍ，“Ｏｎ  ｔｈｅ  ｓｅｃｕｒｉｔｙ  ｏｆ  ＮＴＲＵＳｉｇｎ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅ”，ＳＣＩＳ２００４
【発明の開示】
【発明が解決しようとする課題】
【００３７】  しかしながら、上記特許文献１および非特許文献４のＮＴＲＵＳｉｇｎ署名方式では、署名を偽造することができるという問題がある。【００３８】  即ち、上記従来のＮＴＲＵＳｉｇｎ署名方式では、正規の署名ｓにノルム０ベクトルが加算されても、そのノルム０ベクトルが加算された署名ｓも正しい署名として検証される可能性がある。【００３９】  ノルム０ベクトルは、ノルムが０となるベクトルであって、例えば、全ての要素が１のベクトルがノルム０ベクトルである。【００４０】  すべての要素が１のベクトルｖ０＝（１，１，…，１）のノルムは、ノルムの定義より、
｜｜ｖ０｜｜＝ｓｑｒｔ（（１−μ）＾２＋（１−μ）＾２＋…＋（１−μ）＾２）
である。【００４１】    ここで、μ＝（１／Ｎ）・（１＋１＋１＋…＋１）＝１であるため、
｜｜ｖ０｜｜＝ｓｑｒｔ（（１−１）＾２＋（１−１）＾２＋…＋（１−１）＾２）＝０となる。【００４２】  つまり、署名ｓにノルム０ベクトルｖ０を加算して生成される偽造署名（ｓ＋ｖ０）のノルムは、署名ｓのノルムと等しいため、（ｓ＋ｖ０，ｔ）と（ｍ１，ｍ２）の距離は、（ｓ，ｔ）と（ｍ１，ｍ２）の距離と等しい。その結果、その偽造署名（ｓ＋ｖ０）が署名検証時に正しい署名として検証される。以下、このようなノルム０ベクトルの加算による署名ｓに対する攻撃を、「ノルム０ベクトル偽造攻撃」と呼ぶ。なお、このような攻撃については、非特許文献５で指摘されている。【００４３】  そこで、本発明は、かかる問題に鑑みてなされたものであって、ノルム０ベクトル偽造攻撃を防ぐことが可能な署名生成装置および署名検証装置を提供することを目的とする。
【課題を解決するための手段】
【００４４】  上記目的を達成するために、本発明に係る署名生成装置は、署名方式を用いてメッセージデータに対する署名データを生成する署名生成装置であって、前記署名方式は、加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、前記署名生成装置は、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成手段と、前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換手段とを備えることを特徴とする。【００４５】  これにより、ＮＴＲＵＳｉｇｎ署名方式により生成された署名データの形式は、そのノルムが変化することなく、対象要素が予め定められた値となる形式に変換されるため、その署名データおよびメッセージデータを取得した署名検証装置は、その署名データに対して、ＮＴＲＵＳｉｇｎ署名方式による署名検証を行うことができるとともに、その署名データの形式に基づいて、ノルム０ベクトル偽造攻撃が試みられたか否かを容易に判定することができる。例えば、署名データに含まれるＮ個の要素のうち一つ目の要素が０となるように、その署名データの形式が変換される場合、その署名データにノルム０ベクトル偽造攻撃が試みられると、その対象要素は０と異なる値になる。したがって、署名検証装置は、その署名データの一つ目の要素が０であるか否かを判別するだけで、ノルム０ベクトル偽造攻撃を簡単に防ぐことができる。その結果、ディジタル署名の安全性を高めることができる。【００４６】  また、前記署名生成装置は、さらに、前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成し、前記Ｎ次元配列ごとに、当該Ｎ次元配列のノルムが変化することなく、当該Ｎ次元配列に含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記各Ｎ次元配列の形式を変換するハッシュ値生成手段を備え、前記署名生成手段は、前記組｛ｆ，ｇ，Ｆ，Ｇ｝のそれぞれの元の形式が、当該元に含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように整えられている前記秘密鍵と、前記ハッシュ値生成手段により形式が変換されたハッシュ値とを用いて前記署名データを生成することを特徴としてもよい。【００４７】  これにより、ハッシュ値を示す２つのＮ次元配列と、秘密鍵を示す４つの元ｆ，ｇ，Ｆ，Ｇとはそれぞれ、それらに含まれる対象要素が予め定められた値になっているため、これらに対してノルム０ベクトルが加算されても、その加算行為を容易に検出することができ、ディジタル署名の安全性を確実に高めることができる。【００４８】  また、本発明に係る署名検証装置は、署名方式を用いてメッセージデータに対する署名データを検証する署名検証装置であって、前記署名方式は、加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、前記署名検証装置は、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定手段と、前記環Ｒの元である前記署名データを、前記公開鍵を用いて検証する署名検証手段とを備えることを特徴とする。【００４９】  例えば、ＮＴＲＵＳｉｇｎ署名方式により生成された署名データのノルムが変化することなく、対象要素が予め定められた値となるように、その署名データの形式が変換されている場合には、署名検証装置は、その署名データに対して、ＮＴＲＵＳｉｇｎ署名方式による署名検証を行うことができるとともに、その署名データの形式に基づいて、ノルム０ベクトル偽造攻撃が試みられたか否かを容易に判定することができる。例えば、署名データに含まれるＮ個の要素のうち一つ目の要素が０となるように、その署名データの形式が変換されている場合、その署名データにノルム０ベクトル偽造攻撃が試みられると、その対象要素は０と異なる値になる。したがって、署名検証装置は、その署名データの一つ目の要素が０であるか否かを判別するだけで、ノルム０ベクトル偽造攻撃を簡単に防ぐことができる。その結果、ディジタル署名の安全性を高めることができる。【００５０】  また、前記署名検証手段は、前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成し、前記Ｎ次元配列ごとに、当該Ｎ次元配列のノルムが変化することなく、当該Ｎ次元配列の要素のうち何れか１つの対象要素が予め定められた値となるように、前記各Ｎ次元配列の形式を変換するハッシュ値生成手段と、前記元ｈに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように形式が整えられている前記公開鍵と、前記署名データとの積を前記環Ｒの元ｔとして算出し、前記元ｔのノルムが変化することなく、前記元ｔに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記元ｔの形式を変換することにより、形式が��換された前記元ｔと署名データとからなる署名ベクトルを生成する署名ベクトル生成手段と、前記署名ベクトル生成手段により生成された署名ベクトルと、前記ハッシュ値生成手段により形式が変換されたハッシュ値との距離に基づいて、前記署名データを検証する距離判定手段とを備えることを特徴としてもよい。【００５１】  これにより、ハッシュ値を示す２つのＮ次元配列と、公開鍵を示す元ｈと、元ｔとはそれぞれ、それらに含まれる対象要素が予め定められた値になっているため、これらに対してノルム０ベクトルが加算されても、その加算行為を容易に検出することができ、ディジタル署名の安全性を確実に高めることができる。【００５２】  なお、本発明は、このような署名生成装置および署名検証装置として実現することができるだけでなく、その方法やプログラム、そのプログラムを格納する記憶媒体、集積回路としても実現することができる。
【発明の効果】
【００５３】  本発明の署名生成装置および署名検証装置は、ノルム０ベクトル偽造攻撃を防ぐことができるという作用効果を奏し、その価値は大きい。
【図面の簡単な説明】
【００５４】
【図１】図１は、署名の生成方法を説明するための説明図である。
【図２】図２は、署名の検証方法を説明するための説明図である。
【図３】図３は、本発明の実施の形態におけるディジタル署名システムの構成を示すブロック図である。
【図４】図４は、本発明の実施の形態における署名生成部の構成を示すブロック図である。
【図５】図５は、本発明の実施の形態における署名生成部の動作を示すフローチャートである。
【図６】図６は、本発明の実施の形態における署名生成装置の全体的な動作を示すフローチャートである。
【図７】図７は、本発明の実施の形態における署名検証部の構成を示すブロック図である。
【図８】図８は、本発明の実施の形態における署名検証部の動作を示すフローチャートである。
【図９】図９は、本発明の実施の形態における署名検証装置の全体的な動作を示すフローチャートである。
【図１０】図１０は、本発明の実施の形態における変形例１の署名生成部の動作を示すフローチャートである。
【図１１】図１１は、本発明の実施の形態における変形例１の署名検証部の動作を示すフローチャートである。
【図１２】図１２は、本発明の実施の形態における変形例２の署名生成部の動作を示すフローチャートである。
【図１３】図１３は、本発明の実施の形態における変形例２の署名検証部の動作を示すフローチャートである。
【符号の説明】
【００５５】  １００    ディジタル署名システム
１１０    署名生成装置
１１１    送信部
１１２    秘密鍵格納部
１１３    公開鍵証明書格納部
１１４    署名生成部
１１５    署名データセット生成部
１２０    署名検証装置
１２１    受信部
１２２    ＣＡ公開鍵格納部
１２３    署名データセット格納部
１２４    署名検証部
１３０    通信路
１１４１  ハッシュ値生成部
１１４２  署名ベクトル生成部
１１４３  署名変換部
１２４１  ハッシュ値生成部
１２４２  署名形式判定部
１２４３  署名ベクトル生成部
１２４４  距離判定部
【発明を実施するための最良の形態】
【００５６】  （実施の形態）
本発明の実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式は、従来のＮＴＲＵＳｉｇｎ署名方式を改良した署名方式であって、ノルム０ベクトル偽造攻撃を防ぐことが可能なように署名を生成して検証するものである。【００５７】  以下、本実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式について詳細に説明する。【００５８】  ＜改良ＮＴＲＵＳｉｇｎ署名方式＞
（１）改良ＮＴＲＵＳｉｇｎ署名方式のパラメータ
改良ＮＴＲＵＳｉｇｎ署名方式では、非負整数のパラメータ、Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄが使用される。これらのパラメータの定義は、従来のＮＴＲＵＳｉｇｎ署名方式と同様である。以下に、これらのパラメータの意味を説明する。【００５９】  （ｉ）パラメータＮ
改良ＮＴＲＵＳｉｇｎ署名方式は、多項式の演算により署名生成及び署名検証を行うディジタル署名方式である。改良ＮＴＲＵＳｉｇｎ署名方式で扱う多項式の次数は、上記パラメータＮにより決まる。【００６０】  改良ＮＴＲＵＳｉｇｎ署名方式で扱う多項式は、上記パラメータＮに対し、Ｎ−１次以下の整数係数多項式であり、例えばＮ＝５のとき、Ｘ＾４＋Ｘ＾３＋１等の多項式である。ここで、「Ｘ＾ａ」はＸのａ乗を意味する。また、公開鍵ｈおよび署名ｓはいずれも、Ｎ−１次以下の多項式として表現される。また、秘密鍵は４つのＮ−１次以下の多項式対｛ｆ，ｇ，Ｆ，Ｇ｝である。すなわち、ｆ，ｇ，Ｆ，ＧはいずれもＮ−１次以下の多項式である。なお、以下では、４つの多項式からなる組（ｆ，ｇ，Ｆ，Ｇ）を、２つの対（ｆ，ｇ），（Ｆ，Ｇ）のさらなる対と捉えて、｛（ｆ，ｇ），（Ｆ，Ｇ）｝と表記する場合もある。【００６１】  そして、多項式演算は、上記パラメータＮに対し、Ｘ＾Ｎ＝１という関係式を用いて、演算結果が常にＮ−１次以下の多項式になるように演算される。例えば、Ｎ＝５の場合、多項式Ｘ＾４＋Ｘ＾２＋１と多項式Ｘ＾３＋Ｘの積は、多項式と多項式の積を×、整数と多項式の積（あるいは整数と整数の積）を・とすると、Ｘ＾５＝１という関係から、
（Ｘ＾４＋Ｘ＾２＋１）×（Ｘ＾３＋Ｘ）
＝Ｘ＾７＋２・Ｘ＾５＋２・Ｘ＾３＋Ｘ
＝Ｘ＾２・１＋２・１＋２・Ｘ＾３＋Ｘ
＝２・Ｘ＾３＋Ｘ＾２＋Ｘ＋２
というように、常にＮ−１次以下の多項式になるように演算される。【００６２】  なお、改良ＮＴＲＵＳｉｇｎ署名方式においても、Ｎ−１次の多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）はベクトル（ａ＿０，ａ＿１，ａ＿２，…，ａ＿Ｎ−１））と同一視される。ここで、ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１）は多項式ａの係数であり、整数である。【００６３】  （ｉｉ）パラメータｑ
改良ＮＴＲＵＳｉｇｎ署名方式では、２以上の整数であるパラメータｑを用いる。改良ＮＴＲＵＳｉｇｎ署名方式で出現する多項式の係数は、ｑを法とした剰余を取る。【００６４】  （ｉｉｉ）パラメータｄｆ，ｄｇ
改良ＮＴＲＵＳｉｇｎ署名方式で扱う秘密鍵の一部である多項式ｆ及び、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇの選び方は、それぞれパラメータｄｆ，ｄｇにより決まる。【００６５】  まず、多項式ｆは、ｄｆ個の係数が１であり、かつ他の係数は０となるように選ばれる。すなわち、多項式ｆは、Ｎ−１次以下の多項式であり、０次（定数項）からＮ−１次まで、Ｎ個の係数があるが、このＮ個の係数のうち、ｄｆ個の係数が１であり、かつ（Ｎ−ｄｆ）個の係数が０となるように選ばれる。そして、多項式ｇは、ｄｇ個の係数が１であり、かつ他の係数は０となるように選ばれる。【００６６】  （ｉｖ）パラメータＮｏｒｍｂｏｕｎｄ
改良ＮＴＲＵＳｉｇｎ署名方式では、後述するが署名ｓから作られる２・Ｎ次元のベクトルとメッセージデータ（以下、単にメッセージという）のハッシュ値である２・Ｎ次元のベクトルの距離を計算し、この距離により署名ｓが正しい署名であるかを判定する。Ｎｏｒｍｂｏｕｎｄは、この判定の際に使用するしきい値である。すなわち、上記距離がＮｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しい署名として受理され、Ｎｏｒｍｂｏｕｎｄ以上であれば、正しくない署名として拒否される。なお、非特許文献４には、ＮＴＲＵＳｉｇｎ署名方式のパラメータの例として、（Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄ）＝（２５１，１２８，７３，７１，３１０）の例が挙げられている。改良ＮＴＲＵＳｉｇｎ署名方式においても、同様のパラメータ例を使用してもよい。【００６７】  （２）メッセージのハッシュ値、ノルム及びベクトル間の距離
改良ＮＴＲＵＳｉｇｎ署名方式においても、メッセージのハッシュ値に対する署名を作成する。メッセージのハッシュ値は、Ｎ次の多項式の対であり、２・Ｎ次元のベクトルと同一視される。なお、メッセージからハッシュ値を求めるハッシュ関数については、非特許文献１が詳しい。【００６８】  改良ＮＴＲＵＳｉｇｎ署名方式では、従来のＮＴＲＵＳｉｇｎ署名方式と同様、署名検証にベクトル間の距離を用い、このような距離の算出にノルム（Ｃｅｎｔｅｒｅｄノルム）を用いる。以下、ノルムおよびベクトル間の距離の定義を示す。【００６９】  多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）のノルム｜｜ａ｜｜を以下のように定義する。【００７０】    ｜｜ａ｜｜＝ｓｑｒｔ（（ａ＿０−μ）＾２＋（ａ＿１−μ）＾２＋…＋（ａ＿（Ｎ−１）−μ）＾２）
μ＝（１／Ｎ）・（ａ＿０＋ａ＿１＋ａ＿２＋…＋ａ＿（Ｎ−１））
ここで、ｓｑｒｔ（ｘ）はｘの平方根を示す。【００７１】  多項式ａ，ｂの対（ａ，ｂ）のノルム｜｜（ａ，ｂ）｜｜を以下のように定義する。【００７２】    ｜｜（ａ，ｂ）｜｜＝ｓｑｒｔ（｜｜ａ｜｜＾２＋｜｜ｂ｜｜＾２）
多項式ａ，ｂの対（ａ，ｂ）とｃ，ｄの対（ｃ，ｄ）との距離（ベクトル間の距離）は、｜｜（ｃ−ａ，ｄ−ｂ）｜｜で定義される。【００７３】  （３）改良ＮＴＲＵＳｉｇｎ署名方式の鍵生成
改良ＮＴＲＵＳｉｇｎ署名方式では、ＮＴＲＵＳｉｇｎ署名方式と同様の方法で鍵生成を行う。まず、上述したように、パラメータｄｆ，ｄｇを用いてランダムに多項式ｆ，多項式ｇを生成する。そして非特許文献４に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈを生成する。さらに、以下の式を満たすようなノルムが小さい多項式Ｆ，Ｇを求める。【００７４】    ｆ×Ｇ−ｇ×Ｆ＝ｑ
ここで、秘密鍵を｛（ｆ，ｇ），（Ｆ，Ｇ）｝、公開鍵をｈとする。秘密鍵は、署名を生成するための鍵であり、署名生成鍵とも呼ばれる。また、公開鍵は、署名を検証するための鍵であり、署名検証鍵とも呼ばれる。【００７５】  また、ｘ＝ｙ（ｍｏｄ  ｑ）は、多項式ｙの第ｉ次の係数を、剰余が０からｑ−１の範囲に収まるように法ｑで割ったときの剰余を、多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、多項式ｙの各係数を、０から（ｑ−１）の範囲に収まるように（ｍｏｄ  ｑ）演算した多項式を、多項式ｘとする演算である。【００７６】  （４）改良ＮＴＲＵＳｉｇｎ署名方式の署名生成
改良ＮＴＲＵＳｉｇｎ署名方式の署名生成では、署名対象であるメッセージｍの署名ｓを計算する。【００７７】  まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を計算する。【００７８】  この２・Ｎ次元のベクトル（ｍ１，ｍ２）と秘密鍵｛（ｆ，ｇ），（Ｆ，Ｇ）｝を用いて、以下の（式１）および（式２）を満たす多項式ａ，ｂ，Ａ，Ｂを計算する。【００７９】    Ｇ×ｍ１−Ｆ×ｍ２＝Ａ＋ｑ×Ｂ    ・・・（式１）
−ｇ×ｍ１＋ｆ×ｍ２＝ａ＋ｑ×ｂ  ・・・（式２）
ここで、Ａ，ａの係数は〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を取ったものとする。すなわち、法ｑで割ったときの剰余が〈ｑ／２〉からｑ−１である場合は、ｑ減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。【００８０】  次に以下の（式３）および（式４）より、多項式ｓ，ｔを計算する。【００８１】    ｓ＝ｆ×Ｂ＋Ｆ×ｂ（ｍｏｄ  ｑ）・・・（式３）
ｔ＝ｇ×Ｂ＋Ｇ×ｂ（ｍｏｄ  ｑ）・・・（式４）
本発明の実施の形態では、さらに、ｓ＝ｓ＿０＋ｓ＿１・Ｘ＋ｓ＿２・Ｘ＾２＋…＋ｓ＿（Ｎ−１）・Ｘ＾（Ｎ−１）とするときに、その多項式ｓと、ノルム０ベクトル（１，１，…，１）に対応する多項式ｖ０とを用いて、以下の（式５）に示すように、署名ｓ’を算出する。【００８２】    ｓ’＝ｓ−ｓ＿０×ｖ０
＝０＋（ｓ＿１−ｓ＿０）・Ｘ＋（ｓ＿２−ｓ＿０）・Ｘ＾２
＋…＋（ｓ＿（Ｎ−１）−ｓ＿０）・Ｘ＾（Ｎ−１）・・・（式５）
すなわち、本実施の形態では、多項式ｓの一つ目の要素（０次の項の係数）を０とするように、多項式ｓからノルム０ベクトルを減算し、その減算結果である多項式ｓ’を署名とする。【００８３】  言い換えれば、本実施の形態では、多項式ｓのノルムが変化することなく、その多項式ｓに含まれるＮ個の要素のうち一つ目の要素が０となるように、その多項式ｓの形式を変換し、その結果、多項式ｓ’を生成する。【００８４】  （５）改良ＮＴＲＵＳｉｇｎ署名方式の署名検証
改良ＮＴＲＵＳｉｇｎ署名方式の署名検証では、署名ｓ’が署名対象であるメッセージｍの正しい署名であるか否かを検証する。【００８５】  具体的に、まず、署名ｓ’の一つ目の要素（０次の項の係数）が０であるか否かをチェックする。一つ目の要素が０でなければ、署名ｓ’が不正であると判定してその署名ｓ’を拒否する。つまり、このようなチェックによって、ノルム０ベクトル偽造攻撃を防ぐことができる。【００８６】  一方、一つ目の要素が０であれば、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）を計算する。そして、公開鍵ｈを用いて、以下の（式６）より、多項式ｔ’を計算する。【００８７】    ｔ’＝ｓ’×ｈ（ｍｏｄ  ｑ）・・・（式６）
２・Ｎ次元ベクトル（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離を求め、Ｎｏｒｍｂｏｕｎｄ未満であるかをチェックする。Ｎｏｒｍｂｏｕｎｄ未満であれば、署名ｓ’が正しいと判定してその署名ｓ’を受理する。Ｎｏｒｍｂｏｕｎｄ以上であれば、署名ｓ’が不正と判定してその署名ｓ’を拒否する。なお、２・Ｎ次元ベクトルの距離がＮｏｒｍｂｏｕｎｄ未満であるか否かのチェックを行った後に、署名ｓ’の一つ目の要素が０であるか否かのチェックを行ってもよい。【００８８】  図３は、本発明の実施の形態におけるディジタル署名システム１００の構成を示すブロック図である。【００８９】  このディジタル署名システム１００は、上述の改良ＮＴＲＵＳｉｇｎ署名方式を用いて署名を生成して検証するものであって、署名生成装置１１０と、署名検証装置１２０と、通信路１３０とから構成される。【００９０】  署名生成装置１１０は、改良ＮＴＲＵＳｉｇｎ署名方式により、入力されたメッセージｍに対する署名ｓ’などを含む署名データセットＳＳを生成し、その署名データセットＳＳを署名検証装置１２０へ通信路１３０を介して送信する。また、このような署名生成装置１１０は、送信部１１１と、秘密鍵格納部１１２と、公開鍵証明書格納部１１３と、署名生成部１１４と、署名データセット生成部１１５とを備える。【００９１】  署名検証装置１２０は、通信路１３０を介して署名生成装置１１０から、署名データセットＳＳを受信し、改良ＮＴＲＵＳｉｇｎ署名方式により、その署名データセットＳＳに含まれる署名ｓ’などを検証する。また、このような署名検証装置１２０は、受信部１２１と、ＣＡ公開鍵格納部１２２と、署名データセット格納部１２３と、署名検証部１２４とを備える。【００９２】  以下、本実施の形態における署名生成装置１１０について詳細に説明する。【００９３】  署名生成装置１１０の送信部１１１は、署名データセットＳＳを、通信路１３０を介して署名検証装置１２０へ送信する。【００９４】  秘密鍵格納部１１２は、メッセージｍに対する署名ｓ’を生成するための秘密鍵ＫＳを格納している。秘密鍵ＫＳは予め与えられているものとする。【００９５】  公開鍵証明書格納部１１３は、上述の多項式ｈにより示される公開鍵ＫＰ（公開鍵ｈ）の公開鍵証明書ＣＰを格納する。公開鍵証明書ＣＰは、公開鍵ＫＰと、認証局ＣＡによる公開鍵ＫＰの署名を示す署名データＳＰとからなる。この署名データＳＰも、改良ＮＴＲＵＳｉｇｎ署名方式を使用して生成されている。また、公開鍵証明書ＣＰは予め与えられているものとする。なお、公開鍵証明書ＣＰは、公開鍵ＫＰと署名データＳＰ以外の他のデータを含んでいてもよい。例えば、ユーザの識別子や公開鍵証明書ＣＰの期限などを含んでもよい。【００９６】  署名生成部１１４は、秘密鍵格納部１１２に格納されている秘密鍵ＫＳを用いて、メッセージｍに対する署名ｓ’を示す署名データＳを生成する。【００９７】  図４は、本実施の形態における署名生成部１１４の構成を示すブロック図である。【００９８】  署名生成部１１４は、ハッシュ値生成部１１４１と、署名ベクトル生成部１１４２と、署名変換部１１４３とを備える。【００９９】  ハッシュ値生成部１１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を算出する。【０１００】  署名ベクトル生成部１１４２は、秘密鍵ＫＳとハッシュ値Ｈを用いて、上記（式１）〜（式４）により、多項式Ｓを生成する。【０１０１】  署名変換部１１４３は、署名ベクトル生成部１１４２で生成された多項式ｓを用いて、上記（式５）により、多項式ｓ’を生成する。即ち、多項式ｓがｓ＝ｓ＿０＋ｓ＿１・Ｘ＋ｓ＿２・Ｘ＾２＋…＋ｓ＿（Ｎ−１）・Ｘ＾（Ｎ−１）によって示される場合、署名変換部１１４３は、その多項式ｓと、ノルム０ベクトルであるｖ０＝（１，１，…，１）とを用いて、ｓ’＝０＋（ｓ＿１−ｓ＿０）・Ｘ＋（ｓ＿２−ｓ＿０）・Ｘ＾２＋…＋（ｓ＿（Ｎ−１）−ｓ＿０）・Ｘ＾（Ｎ−１）を算出する。【０１０２】  つまり、本実施の形態における署名変換部１１４３は、多項式ｓの一つ目の要素（０次の項の係数）を０とするよう、多項式ｓからノルム０ベクトルを減算し、その減算結果である多項式ｓ’を署名つまり署名データＳとして生成する。【０１０３】  言い換えれば、署名変換部１１４３は、多項式ｓのノルムが変化することなく、その多項式ｓに含まれるＮ個の要素のうち一つ目の要素が０となるように、その多項式ｓの形式を変換し、その結果、多項式ｓ’を署名として生成する。【０１０４】  署名データセット生成部１１５は、メッセージｍと、メッセージｍの署名データＳと、公開鍵証明書ＣＰとからなる署名データセットＳＳを生成する。【０１０５】  図５は、署名生成部１１４の動作を示すフローチャートである。【０１０６】  まず、署名生成部１１４のハッシュ値生成部１１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）を算出する（ステップＳ１００）。【０１０７】  次に、署名生成部１１４の署名ベクトル生成部１１４２は、上記（式１）および（式２）を満たす多項式ａ，ｂ，Ａ，Ｂを算出する（ステップＳ１０２）。さらに、署名ベクトル生成部１１４２は、上記（式３）により、多項式ｓを算出する（ステップＳ１０４）。【０１０８】  そして、署名生成部１１４の署名変換部１１４３は、上記（式５）により、その多項式ｓからノルム０ベクトルを減算して、一つ目の要素（０次の項の係数）が０である多項式ｓ’を署名つまり署名データＳとして生成する（ステップＳ１０６）。【０１０９】  図６は、署名生成装置１１０の全体的な動作を示すフローチャートである。【０１１０】  署名生成装置１１０の署名生成部１１４は、秘密鍵格納部１１２に格納されている秘密鍵ＫＳを用いて、メッセージｍに対する署名データＳを生成する（ステップＳ１２０）。【０１１１】  次に、署名生成装置１１０の署名データセット生成部１１５は、メッセージｍと、署名データＳと、公開鍵証明書格納部１１３に格納されている公開鍵証明書ＣＰとからなる署名データセットＳＳを生成する（ステップＳ１２２）。【０１１２】  そして、署名生成装置１１０の送信部１１１は、通信路１３０を介して署名データセットＳＳを署名検証装置１２０へ送信する（ステップＳ１２４）。【０１１３】  以下、本実施の形態における署名検証装置１２０について詳細に説明する。【０１１４】  署名検証装置１２０の受信部１２１は、署名生成装置１１０から送信された署名データセットＳＳを、通信路１３０を介して受信する。【０１１５】  ＣＡ公開鍵格納部１２２は、署名データセットＳＳに含まれる公開鍵証明書ＣＰを検証するための認証局ＣＡの公開鍵ＫＣＰを格納する。【０１１６】  署名データセット格納部１２３は、受信部１２１で受信された署名データセットＳＳを格納する。【０１１７】  署名検証部１２４は、署名データセットＳＳに含まれる署名データＳと、公開鍵証明書ＣＰに含まれる署名データＳＰとを検証する。【０１１８】  図７は、本実施の形態における署名検証部１２４の構成を示すブロック図である。【０１１９】  署名検証部１２４は、ハッシュ値生成部１２４１と、署名形式判定部１２４２と、署名ベクトル生成部１２４３と、距離判定部１２４４とを備える。【０１２０】  ハッシュ値生成部１２４１は、署名対象データであるメッセージｍおよび公開鍵ＫＰのそれぞれのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する。【０１２１】  署名形式判定部１２４２は、改良ＮＴＲＵＳｉｇｎ署名方式の検証対象である署名データＳおよび署名データＳＰのそれぞれの一つ目の要素が０であるか否かを判定する。ここで、署名形式判定部１２４２は、署名データＳおよび署名データＳＰの少なくとも一方における一つ目の要素が０であると判定したときには、受信部１２１で受信された署名データセットＳＳに対してノルム０ベクトル偽造攻撃が試みられたと判断する。つまり、署名形式判定部１２４２は、署名データセットＳＳに対して偽造が行われたと判断する。したがって、本実施の形態では、このような判定を行うことにより、ノルム０ベクトル偽造攻撃を防ぐことができる。【０１２２】  署名ベクトル生成部１２４３は、署名データＳおよび署名データＳＰのそれぞれにより示される多項式ｓ’と、公開鍵ＫＰまたは公開鍵ＫＣＰにより示される多項式ｈとを用いて、上記（式６）により、多項式ｔ’を算出する。つまり、署名ベクトル生成部１２４３は、ｔ’＝ｓ’×ｈ（ｍｏｄ  ｑ）により、署名データＳおよび署名データＳＰのそれぞれに対する多項式ｔ’を計算する。【０１２３】  さらに、署名ベクトル生成部１２４３は、署名データＳおよび署名データＳＰのそれぞれに対して、２・Ｎ次元ベクトル（ｓ’，ｔ’）を署名ベクトルＳＶとして生成する。【０１２４】  距離判定部１２４４は、メッセージｍおよび署名データＳと、公開鍵ＫＰおよび署名データＳＰとのそれぞれに対して、ハッシュ値Ｈと署名ベクトルＳＶの距離を計算し、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する。即ち、メッセージｍおよび署名データＳに対する、ハッシュ値と署名ベクトルＳＶの距離がＮｏｒｍｂｏｕｎｄ未満であれば、距離判定部１２４４は、署名データＳが正しいと判定してその署名データＳを受理する。一方、Ｎｏｒｍｂｏｕｎｄ以上であれば、距離判定部１２４４は、署名データＳが不正と判定してその署名データＳを拒否する。また、公開鍵ＫＰおよび署名データＳＰに対する、ハッシュ値と署名ベクトルＳＶの距離がＮｏｒｍｂｏｕｎｄ未満であれば、距離判定部１２４４は、署名データＳＰが正しいと判定してその署名データＳＰを受理する。一方、Ｎｏｒｍｂｏｕｎｄ以上であれば、距離判定部１２４４は、署名データＳＰが不正と判定してその署名データＳＰを拒否する。【０１２５】  図８は、署名検証部１２４の動作を示すフローチャートである。【０１２６】  署名検証部１２４は、公開鍵ＫＰを用い、メッセージｍおよび署名データＳに対して図８に示す動作を行うことにより、その署名データＳを検証する。なお、署名検証部１２４は、署名データＳの検証を行う前に、公開鍵ＫＣＰを用い、公開鍵ＫＰおよび署名データＳＰに対して図８に示す動作を行うことにより、その署名データＳＰを検証している。【０１２７】  以下、署名検証部１２４が署名データＳを検証する具体的な動作について、図８を参照して説明する。【０１２８】  署名検証部１２４の署名形式判定部１２４２は、まず、署名データＳにより示される多項式ｓ’の一つ目の要素（０次の項の係数）が０であるか否かを判定する（ステップＳ１４０）。ここで、署名形式判定部１２４２は、０でないと判定した場合は（ステップＳ１４０のＮ）、署名データＳが不正であるとしてその署名データＳを拒否する（ステップＳ１４２）。一方、署名形式判定部１２４２によって０であると判定された場合は（ステップＳ１４０のＹ）、ハッシュ値生成部１２４１は、その署名データＳに対応するメッセージｍのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する（ステップＳ１４４）。【０１２９】  次に、署名ベクトル生成部１２４３は、署名データＳにより示される多項式ｓ’と、公開鍵ＫＰにより示される多項式ｈとを用いて、上記（式６）により、多項式ｔ’を算出する（ステップＳ１４６）。このとき、署名ベクトル生成部１２４３は、署名データＳに対して、２・Ｎ次元ベクトル（ｓ’，ｔ’）を署名ベクトルＳＶとして生成する。【０１３０】  距離判定部１２４４は、ステップＳ１４４で算出されたハッシュ値Ｈ（＝（ｍ１，ｍ２）と、ステップＳ１４６で生成された署名ベクトルＳＶとの距離を算出する（ステップＳ１４８）。そして、距離判定部１２４４は、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する（ステップＳ１５０）。距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満であると判定したときには（ステップＳ１５０のＹ）、署名データＳが正しいと判断してその署名データＳを受理する（ステップＳ１５２）。一方、距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満でないと判定したときには（ステップＳ１５０のＮ）、署名データＳが不正であると判断してその署名データＳを拒否する（ステップＳ１４２）。【０１３１】  図９は、署名検証装置１２０の全体的な動作を示すフローチャートである。【０１３２】  まず、署名検証装置１２０の受信部１２１は、署名生成装置１１０から通信路１３０を介して署名データセットＳＳを受信し、その署名データセットＳＳを署名データセット格納部１２３に格納する（ステップＳ１７０）。【０１３３】  署名検証部１２４は、署名データセットＳＳの中の公開鍵証明書ＣＰに含まれる公開鍵ＫＰとその署名データＳＰに対し、署名データＳＰが公開鍵ＫＰの正しい署名であるか否かを、ＣＡ公開鍵格納部１２２に格納されている認証局ＣＡの公開鍵ＫＣＰを用いて検証する。つまり、署名検証部１２４は、署名データＳＰが正しい署名であるか否かを判別する（ステップＳ１７２）。ここで、署名検証部１２４は、正しい署名でないと判別したときには（ステップＳ１７２のＮ）、その署名データＳＰを拒否する（ステップＳ１７４）。【０１３４】  一方、署名検証部１２４は、ステップＳ１７２で署名データＳＰが正しい署名であると判別したときには（ステップＳ１７２のＹ）、その署名データＳＰを受理し、さらに、署名データセットＳＳの中のメッセージｍとその署名データＳに対し、署名データＳがメッセージｍの正しい署名であるか否かを、公開鍵ＫＰを用いて検証する。つまり、署名検証部１２４は、署名データＳが正しい署名であるか否かを判別する（ステップＳ１７６）。【０１３５】  ここで、署名検証部１２４は、正しい署名でないと判別したときには（ステップＳ１７６のＮ）、その署名データＳを拒否し（ステップＳ１７４）、正しい署名であると判別したときには（ステップＳ１７６のＹ）、その署名データＳを受理する（ステップＳ１７８）。即ち、ステップＳ１７８では、署名検証部１２４は、署名データセットＳＳが正当な署名を受けたデータであると認識する。【０１３６】  このように、本実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式で処理を行なうディジタル署名システム１００では、上記（式５）に示すように、多項式ｓのノルムを変化させることなく、その多項式ｓの形式を変換し、その変換結果である、一つ目の要素が０となる形式の多項式ｓ’を署名として扱う。そして、このディジタル署名システム１００では、多項式を示す署名データに対して検証を行うときには、その多項式の一つ目の要素が０であるか否かを判定することで、その署名データに対するノルム０ベクトル偽造攻撃を防ぐことができる。【０１３７】  つまり、本実施の形態では、署名検証装置１２０は、署名として扱われる多項式が上述のような形式であるか否かを判別し、上述のような形式でなければ、その多項式を不正な署名として扱う。【０１３８】  例えば、署名生成装置１１０は、一つ目の要素が０となる多項式ｓ’＝０＋ｓ＿１・Ｘ＋ｓ＿２・Ｘ＾２＋…＋ｓ＿（Ｎ−１）・Ｘ＾（Ｎ−１）を署名として生成する。この多項式ｓ’に対してノルム０ベクトルｖ０（１，１，…，１）が加算されると、加算された多項式ｓａは、ｓａ＝ｓ’＋ｖ０＝１＋（ｓ＿１＋１）・Ｘ＋（ｓ＿２＋１）・Ｘ＾２＋…＋（ｓ＿（Ｎ−１）＋１）・Ｘ＾（Ｎ−１）となる。つまり、多項式ｓａの一つ目の要素は０でなく、多項式のｓａの形式は上述のような形式とはならない。そこで、署名検証装置１２０は、多項式ｓａの形式が上述のような形式でないため、その多項式ｓａを不正な署名として扱う。【０１３９】  つまり、従来では、署名として扱われる多項式にノルム０ベクトルが加算されると、その多項式のノルムと、ノルム０ベクトルが加算された多項式のノルムとは等しいため、ノルム０ベクトルが加算された多項式も正当な署名として扱われてしまう。即ち、従来では、ノルム０ベクトル偽造攻撃を受ける。しかし、本実施の形態では、上述のように、署名生成時に、署名として扱われる多項式の形式を予め定められた形式に変換し、署名検証時には、検証対象の多項式の形式がその予め定められた形式であるか否かを判別する。これにより、署名生成時に生成された多項式のノルムと、検証対象の多項式のノルムとが等しくても、その検証対象の多項式が、ノルム０ベクトルが加算された不正な署名であるか否かを容易に判別することができる。【０１４０】  言い換えれば、本実施の形態では、従来の２・Ｎ次元ベクトル（ｓ，ｔ）と（ｍ１，ｍ２）との距離が等しくなるような複数の多項式ｓを、予め規定されたフォーマットの１つの多項式でまとめて表し、そのフォーマットの多項式を署名として扱っている。例えば、ｓ’、ｓ’＋（１，１，…，１）、ｓ’＋（２，２，…，２）、ｓ’＋（３，３，…，３）、…をそれぞれ多項式ｓとしたとき、各多項式ｓに対して算出される、２・Ｎ次元ベクトル（ｓ，ｔ）と（ｍ１，ｍ２）との距離はそれぞれ等しくなる。したがって、本実施の形態では、ｓ’、ｓ’＋（１，１，…，１）、ｓ’＋（２，２，…，２）、ｓ’＋（３，３，…，３）、…を、例えば、一つ目の要素が０であるフォーマットの多項式ｓ’でまとめて表し、その多項式ｓ’を署名として扱う。そして、多項式ｓ’に対してノルム０ベクトルが加算されたｓ’＋（２，２，…，２）やｓ’＋（３，３，…，３）などの多項式に対する上記距離と多項式ｓ’に対する上記距離とは等しい。しかし、これらの多項式のフォーマットは多項式ｓ’のフォーマットとは異なるため、これらの多項式は不正な署名であると判断される。【０１４１】  このように、本実施の形態におけるディジタル署名システム１００では、ノルム０ベクトル偽造攻撃は成功せず、安全である。【０１４２】  （変形例１）
ここで、上記実施の形態における第１の変形例について説明する。【０１４３】  上記実施の形態では、一つ目の要素が０である多項式ｓ’を署名として扱ったが、本変形例では、最後の要素（Ｎ−１次の項の係数）が０である多項式ｓ’を署名として扱う。つまり、上記実施の形態において署名として扱われる多項式の形式は、一つ目の要素が０となる形式であったが、本変形例において署名として扱われる多項式の形式は、最後の要素が０となる形式である。【０１４４】  具体的に、本変形例に係る署名生成部１１４の署名変換部１１４３は、多項式ｓと上記（式５）によって、多項式ｓ’を算出することなく、以下の（式７）によって、多項式ｓ’を算出する。【０１４５】    ｓ’＝ｓ（ｍｏｄ  Ｌ）・・・（式７）
なお、Ｌ＝Ｘ＾（Ｎ−１）＋Ｘ＾（Ｎ−２）＋…＋Ｘ＋１とする。【０１４６】  図１０は、本変形例に係る署名生成部１１４の動作を示すフローチャートである。【０１４７】  まず、署名生成部１１４のハッシュ値生成部１１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）を算出する（ステップＳ１９０）。【０１４８】  次に、署名生成部１１４の署名ベクトル生成部１１４２は、上記（式１）および（式２）を満たす多項式ａ，ｂ，Ａ，Ｂを算出する（ステップＳ１９２）。さらに、署名ベクトル生成部１１４２は、上記（式３）により、多項式ｓを算出する（ステップＳ１９４）。【０１４９】  そして、署名生成部１１４の署名変換部１１４３は、上記（式７）により、その多項式ｓのＬ（＝Ｘ＾（Ｎ−１）＋Ｘ＾（Ｎ−２）＋…＋Ｘ＋１）を法とする剰余を算出し、最後の要素（Ｎ−１次の項の係数）が０である多項式ｓ’を署名つまり署名データＳとして生成する（ステップＳ１９６）。【０１５０】  図１１は、本変形例に係る署名検証部１２４の動作を示すフローチャートである。【０１５１】  署名検証部１２４は、公開鍵ＫＰを用い、メッセージｍおよび署名データＳに対して図１１に示す動作を行うことにより、その署名データＳを検証する。なお、署名検証部１２４は、署名データＳの検証を行う前に、公開鍵ＫＣＰを用い、公開鍵ＫＰおよび署名データＳＰに対して図１１に示す動作を行うことにより、その署名データＳＰを検証している。【０１５２】  以下、署名検証部１２４が署名データＳを検証する具体的な動作について、図１１を参照して説明する。【０１５３】  署名検証部１２４の署名形式判定部１２４２は、まず、署名データＳにより示される多項式ｓ’の最後の要素（Ｎ−１次の項の係数）が０であるか否かを判定する（ステップＳ２１０）。ここで、署名形式判定部１２４２は、０でないと判定した場合は（ステップＳ２１０のＮ）、署名データＳが不正であるとしてその署名データＳを拒否する（ステップＳ２１２）。一方、署名形式判定部１２４２によって０であると判定された場合は（ステップＳ２１０のＹ）、ハッシュ値生成部１２４１は、その署名データＳに対応するメッセージｍのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する（ステップＳ２１４）。【０１５４】  次に、署名ベクトル生成部１２４３は、署名データＳにより示される多項式ｓ’と、公開鍵ＫＰにより示される多項式ｈとを用いて、上記（式６）により、多項式ｔ’を算出する（ステップＳ２１６）。このとき、署名ベクトル生成部１２４３は、署名データＳに対して、２・Ｎ次元ベクトル（ｓ’，ｔ’）を署名ベクトルＳＶとして生成する。【０１５５】  距離判定部１２４４は、ステップＳ２１４で算出されたハッシュ値Ｈ（＝（ｍ１，ｍ２））と、ステップＳ２１６で生成された署名ベクトルＳＶとの距離を算出する（ステップＳ２１８）。そして、距離判定部１２４４は、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する（ステップＳ２２０）。距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満であると判定したときには（ステップＳ２２０のＹ）、署名データＳが正しいと判断してその署名データＳを受理する（ステップＳ２２２）。一方���距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満でないと判定したときには（ステップＳ２２０のＮ）、署名データＳが不正であると判断してその署名データＳを拒否する（ステップＳ２１２）。【０１５６】  このように、本変形例では、上記（式７）に示すように、多項式ｓのノルムを変化させることなく、その多項式ｓの形式を変換し、その変換結果である、最後の要素が０となる形式の多項式ｓ’を署名として扱う。そして、このディジタル署名システム１００では、多項式を示す署名データに対して検証を行うときには、その多項式の最後の要素が０であるか否かを判定することで、その署名データに対するノルム０ベクトル偽造攻撃を防ぐことができる。【０１５７】  （変形例２）
ここで、上記実施の形態における第２の変形例について説明する。【０１５８】  本変形例では、変形例１と同様、多項式ｓの形式を、その多項式のノルムを変化させることなく、最後の要素（Ｎ−１次の項の係数）が０となるように変換するとともに、メッセージｍに対するハッシュ値、および署名と公開鍵との積のそれぞれの形式も、それぞれのノルムを変化させることなく、最後の要素（Ｎ−１次の項の係数）が０となるように変換する。【０１５９】  また、本変形例に係るディジタル署名システム１００では、多項式対｛ｆ，ｇ，Ｆ，Ｇ｝の代わりに多項式対｛ｆ”，ｇ”，Ｆ”，Ｇ”｝を秘密鍵とし、多項式ｈの代わりに多項式ｈ”を公開鍵ＫＰとして用いることで、署名生成および署名検証を行う。ここで、Ｌ＝Ｘ＾（Ｎ−１）＋Ｘ＾（Ｎ−２）＋…＋Ｘ＋１とすると、ｆ”，ｇ”，Ｆ”，Ｇ”およびｈ”は以下の式により示される。【０１６０】  ｆ”＝ｆ（ｍｏｄ  Ｌ）、ｇ”＝ｇ（ｍｏｄ  Ｌ）、Ｆ”＝Ｆ（ｍｏｄ  Ｌ）、Ｇ”＝Ｇ（ｍｏｄ  Ｌ）、ｈ”＝ｈ（ｍｏｄ  Ｌ）
つまり、本変形例で扱われる秘密鍵の４つの多項式はそれぞれ、最後の要素（Ｎ−１次の項の係数）が０となるような形式に整えられており、本変形例で扱われる公開鍵を示す多項式も、最後の要素（Ｎ−１次の項の係数）が０となるような形式に整えられている。なお、多項式ｆ，ｇ，Ｆ，Ｇのそれぞれのノルムは、多項式ｆ”，ｇ”，Ｆ”，Ｇ”のそれぞれのノルムと等しく、多項式ｈのノルムは多項式ｈ”のノルムと等しい。【０１６１】  図１２は、本変形例に係る署名生成部１１４の動作を示すフローチャートである。【０１６２】  まず、署名生成部１１４のハッシュ値生成部１１４１は、メッセージｍのハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）を算出する（ステップＳ２３０）。さらに、ハッシュ値生成部１１４１は、（ｍ１”，ｍ２”）を、ｍ１”＝ｍ１（ｍｏｄ  Ｌ）およびｍ２”＝ｍ２（ｍｏｄ  Ｌ）により算出する（ステップＳ２３２）。つまり、ハッシュ値生成部１１４１は、２・Ｎ次元のベクトル（ｍ１，ｍ２）の各多項式の形式を、それらの多項式のノルムを変化させることなく、最後の要素（Ｎ−１次の項の係数）が０となるように変換することで、ベクトル（ｍ１”，ｍ２”）を生成する。【０１６３】  次に、署名生成部１１４の署名ベクトル生成部１１４２は、以下の（式８）および（式９）を満たす多項式ａ”，ｂ”，Ａ”，Ｂ”を算出する（ステップＳ２３４）。【０１６４】    Ｇ”×ｍ１”−Ｆ”×ｍ２”＝Ａ”＋ｑ×Ｂ”    ・・・（式８）
−ｇ”×ｍ１”＋ｆ”×ｍ２”＝ａ”＋ｑ×ｂ”  ・・・（式９）
さらに、署名ベクトル生成部１１４２は、以下の（式１０）により、多項式ｓを算出する（ステップＳ２３６）。【０１６５】    ｓ＝ｆ”×Ｂ”＋Ｆ”×ｂ”（ｍｏｄ  ｑ）・・・（式１０）
そして、署名生成部１１４の署名変換部１１４３は、以下の（式１１）により、その多項式ｓのＬ（＝Ｘ＾（Ｎ−１）＋Ｘ＾（Ｎ−２）＋…＋Ｘ＋１）を法とする剰余を算出し、最後の要素（Ｎ−１次の項の係数）が０である多項式ｓ”を署名つまり署名データＳとして生成する（ステップＳ２３８）。【０１６６】    ｓ”＝ｓ（ｍｏｄ  Ｌ）・・・（式１１）
図１３は、本変形例に係る署名検証部１２４の動作を示すフローチャートである。【０１６７】  署名検証部１２４は、公開鍵ＫＰを用い、メッセージｍおよび署名データＳに対して図１３に示す動作を行うことにより、その署名データＳを検証する。なお、署名検証部１２４は、署名データＳの検証を行う前に、公開鍵ＫＣＰを用い、公開鍵ＫＰおよび署名データＳＰに対して図１３に示す動作を行うことにより、その署名データＳＰを検証している。【０１６８】  以下、署名検証部１２４が署名データＳを検証する具体的な動作について、図１３を参照して説明する。【０１６９】  署名検証部１２４の署名形式判定部１２４２は、まず、署名データＳにより示される多項式ｓ”の最後の要素（Ｎ−１次の項の係数）が０であるか否かを判定する（ステップＳ２６０）。ここで、署名形式判定部１２４２は、０でないと判定した場合は（ステップＳ２６０のＮ）、署名データＳが不正であるとしてその署名データＳを拒否する（ステップＳ２６２）。一方、署名形式判定部１２４２によって０であると判定された場合は（ステップＳ２６０のＹ）、ハッシュ値生成部１２４１は、その署名データＳに対応するメッセージｍのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する（ステップＳ２６４）。さらに、ハッシュ値生成部１２４１は、（ｍ１”，ｍ２”）を、ｍ１”＝ｍ１（ｍｏｄ  Ｌ）およびｍ２”＝ｍ２（ｍｏｄ  Ｌ）により算出する（ステップＳ２６６）。【０１７０】  次に、署名ベクトル生成部１２４３は、署名データＳにより示される多項式ｓ”と、公開鍵ＫＰにより示される多項式ｈ”とを用いて、以下の（式１２）により、多項式ｔ”を算出する（ステップＳ２６８）。【０１７１】    ｔ”＝ｓ”×ｈ”（ｍｏｄ  Ｌ）・・・（式１２）
また、このとき、署名ベクトル生成部１２４３は、署名データＳに対して、２・Ｎ次元ベクトル（ｓ”，ｔ”）を署名ベクトルＳＶとして生成する。【０１７２】  距離判定部１２４４は、ステップＳ２６６で算出されたハッシュ値Ｈ（＝（ｍ１”，ｍ２”））と、ステップＳ２１６で生成された署名ベクトルＳＶとの距離を算出する（ステップＳ２７０）。そして、距離判定部１２４４は、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する（ステップＳ２７２）。距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満であると判定したときには（ステップＳ２７２のＹ）、署名データＳが正しいと判断してその署名データＳを受理する（ステップＳ２７４）。一方、距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満でないと判定したときには（ステップＳ２７２のＮ）、署名データＳが不正であると判断してその署名データＳを拒否する（ステップＳ２６２）。【０１７３】  このように、本変形例では、署名として扱われる多項式ｓ”だけでなく、秘密鍵の４つの多項式ｆ”，ｇ”，Ｆ”，Ｇ”、公開鍵を示す多項式ｈ”、メッセージｍのハッシュ値（ｍ１”，ｍ２”）、および署名ｓ”と公開鍵ｈ”との積ｔ”のそれぞれの形式も、最後の要素（Ｎ−１次の項の係数）が０となるような形式に整えられている。これにより、多項式ｓ”，ｆ”，ｇ”，Ｆ”，Ｇ”，ｈ”，ｍ１”，ｍ２”，ｔ”のそれぞれに対する安全性を高めることができる。【０１７４】  また、ｓ”，ｆ”，ｇ”，Ｆ”，Ｇ”，ｈ”，ｍ１”，ｍ２”，ｔ”のそれぞれは、最後の要素が０に固定されているため、最後の要素を格納せず、０〜Ｎ−２次の項のみを格納してもよい。これにより、格納に要するサイズを削減することができる。【０１７５】  なお、本変形例では、多項式対｛ｆ”，ｇ”，Ｆ”，Ｇ”｝からなる秘密鍵を秘密鍵格納部１１２に予め格納しておいたが、多項式対｛ｆ，ｇ，Ｆ，Ｇ｝からなる秘密鍵を秘密鍵格納部１１２に予め格納しておいてもよい。同様に、本変形例では、多項式ｈ”により示される公開鍵ＫＰを、公開鍵証明書格納部１１３に予め格納しておいたが、多項式ｈにより示される公開鍵ＫＰを、公開鍵証明書格納部１１３に予め格納しておいてもよい。この場合には、署名生成部１１４は、秘密鍵格納部１１２に格納されている多項式対｛ｆ，ｇ，Ｆ，Ｇ｝を多項式対｛ｆ”，ｇ”，Ｆ”，Ｇ”｝に変換し、その多項式対｛ｆ”，ｇ”，Ｆ”，Ｇ”｝を用いて署名ｓ”を生成する。また、署名データセット生成部１１５は、公開鍵証明書格納部１１３に格納されている公開鍵ＫＰを示す多項式ｈを多項式ｈ”に変換し、その多項式ｈ”により示される公開鍵ＫＰを署名データセットＳＳに含める。【０１７６】  以上、本発明について上記実施の形態および変形例を用いて説明したが、これらは、本発明の一例であり、本発明はこのような実施の形態および変形例に何ら限定されるものではない。つまり、本発明は、本発明の本質を逸脱しない範囲において種々なる態様で実施し得るものである。例えば、以下のような場合も本発明に含まれる。【０１７７】  （１）上記実施の形態および変形例では、署名生成時に、多項式ｓ’の一つ目の要素（０次の項の係数）または最後の要素（Ｎ−１次の項の係数）を０とし、署名検証時に、その要素が０であるかを検証しているが、この要素以外の要素を０としてもよい。例えば、ｉ番目（ｉは２からＮ−１のいずれかの整数）の要素を０としてもよい。また、その要素を「０」ではなく、ｊ（ｊは１からｑ−１のいずれかの整数）としてもよい。また、その要素を、多項式ｍ１に含まれる何れかの要素と等しくなるようにしてもよい。例えば、署名生成時に、多項式ｓ’の一つ目の要素を、多項式ｍ１の一つ目の要素と等しくなるようにし、署名検証時に、多項式ｓ’の一つ目の要素が、多項式ｍ１の一つ目の要素と等しいかを検証してもよい。【０１７８】  （２）上記実施の形態および変形例における署名生成装置１１０および署名検証装置１２０は、具体的には、マイクロプロセッサ、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ハードディスクユニット、ディスプレイユニット、キーボード、およびマウスなどから構成されるコンピュータシステムである。前記ＲＡＭまたはハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、署名生成装置１１０および署名検証装置１２０は、その機能を達成する。ここでコンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。【０１７９】  （３）上記実施の形態および変形例における署名生成装置１１０および署名検証装置１２０を構成する構成要素の一部または全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、システムＬＳＩは、その機能を達成する。【０１８０】  （４）上記実施の形態および変形例における署名生成装置１１０および署名検証装置１２０を構成する構成要素の一部または全部は、署名生成装置１１０または署名検証装置１２０に脱着可能なＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）カード、または単体のモジュールから構成されているとしてもよい。前記ＩＣカードまたは前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。前記ＩＣカードまたは前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムにしたがって動作することにより、前記ＩＣカードまたは前記モジュールは、その機能を達成する。このＩＣカードまたはこのモジュールは、耐タンパ性を有するとしてもよい。【０１８１】  （５）本発明は、上記実施の形態および変形例におけるディジタル署名システム１００におけるそのシステムや装置として実現されるだけでなく、処理方法としても実現できる。また、この��理方法による動作をコンピュータに実行させるコンピュータプログラムとして実現してもよく、前記コンピュータプログラムからなるディジタル信号として実現してもよい。【０１８２】  （６）また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｏｒｙ）、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなどに記録したものとして実現してもよい。また、これらの記録媒体に記録されている前記ディジタル信号として実現してもよい。【０１８３】  （７）また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を、電気通信回線、無線または有線通信回線、インターネットを代表とするネットワーク、もしくはデータ放送等を経由して伝送するものとして実現してもよい。【０１８４】  （８）また、本発明は、マイクロプロセッサとメモリを備えたコンピュータシステムとして実現しても良い。この場合には、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムにしたがって動作する。【０１８５】  （９）また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を前記記録媒体に記録して移送することにより、または前記コンピュータプログラムまたは前記ディジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実現してもよい。【０１８６】  （１０）また、本発明は、上記実施の形態および変形例をそれぞれ組み合わせて実現してもよい。
【産業上の利用可能性】
【０１８７】  本発明の署名生成装置および署名検証装置は、ＮＴＲＵＳｉｇｎ署名方式等におけるノルム０ベクトル偽造攻撃を防ぐことができるという効果を奏し、例えば、ディジタル署名システムなどに適用することができる。
【図１】
2006114948.tif 000003
【図２】
2006114948.tif 000004
【図３】
2006114948.tif 000005
【図４】
2006114948.tif 000006
【図５】
2006114948.tif 000007
【図６】
2006114948.tif 000008
【図７】
2006114948.tif 000009
【図８】
2006114948.tif 000010
【図９】
2006114948.tif 000011
【図１０】
2006114948.tif 000012
【図１１】
2006114948.tif 000013
【図１２】
2006114948.tif 000014
【図１３】
2006114948.tif 000015
【手続補正書】
【提出日】平成18年12月21日(2006.12.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
署名方式を用いてメッセージデータに対する署名データを生成する署名生成装置であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記署名生成装置は、
前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成手段と、
前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換手段と
を備えることを特徴とする署名生成装置。
【請求項２】
前記署名変換手段は、前記対象要素が０からｑ−１の何れかの整数となるように、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項３】
前記署名変換手段は、前記対象要素が０となるように、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項４】
前記署名生成装置は、さらに、
前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成するハッシュ値生成手段を備え、
前記署名変換手段は、
前記対象要素が、前記ハッシュ値を示す２つのＮ次元配列に含まれる２・Ｎ個（ここで・は整数の乗算を示す。）の要素のうち何れか１つの値となるように、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項５】
前記署名変換手段は、
前記署名データにより示される多項式の０次の項に対応する要素が予め定められた値となるように、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項６】
前記署名変換手段は、
ノルムが０のベクトルであるノルム０ベクトルを前記署名データから減算することにより、前記署名データの形式を変換する
ことを特徴とする請求項１記載の署名生成装置。
【請求項７】
前記署名変換手段は、
全て同じ値の要素からなるＮ次元配列として構成される前記ノルム０ベクトルを前記署名データから減算する
ことを特徴とする請求項６記載の署名生成装置。
【請求項８】
前記署名生成装置は、さらに、
前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成し、前記Ｎ次元配列ごとに、当該Ｎ次元配列のノルムが変化することなく、当該Ｎ次元配列に含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記各Ｎ次元配列の形式を変換するハッシュ値生成手段を備え、
前記署名生成手段は、
前記組｛ｆ，ｇ，Ｆ，Ｇ｝のそれぞれの元の形式が、当該元に含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように整えられている前記秘密鍵と、前記ハッシュ値生成手段により形式が変換されたハッシュ値とを用いて前記署名データを生成する
ことを特徴とする請求項１記載の署名生成装置。
【請求項９】
署名方式を用いてメッセージデータに対する署名データを検証する署名検証装置であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記署名検証装置は、
前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定手段と、
前記環Ｒの元である前記署名データを、前記公開鍵を用いて検証する署名検証手段と
を備えることを特徴とする署名検証装置。
【請求項１０】
前記署名形式判定手段は、前記対象要素が、０からｑ−１の複数の整数の中から予め選択された１つの整数であるか否かを判定する
ことを特徴とする請求項９記載の署名検証装置。
【請求項１１】
前記署名形式判定手段は、前記対象要素が０であるか否かを判定する
ことを特徴とする請求項９記載の署名検証装置。
【請求項１２】
前記署名生成装置は、さらに、
前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成するハッシュ値生成手段を備え、
前記署名形式判定手段は、
前記対象要素の値が、前記ハッシュ値を示す２つのＮ次元配列に含まれる２・Ｎ個（ここで・は整数の乗算を示す。）の要素のうち何れか１つの値であるか否かを判定する
ことを特徴とする請求項９記載の署名検証装置。
【請求項１３】
前記署名形式判定手段は、
前記署名データにより示される多項式の０次の項に対応する要素が予め定められた値であるか否かを判定する
ことを特徴とする請求項９記載の署名検証装置。
【請求項１４】
前記署名検証手段は、
前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成し、前記Ｎ次元配列ごとに、当該Ｎ次元配列のノルムが変化することなく、当該Ｎ次元配列の要素のうち何れか１つの対象要素が予め定められた値となるように、前記各Ｎ次元配列の形式を変換するハッシュ値生成手段と、
前記元ｈに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように形式が整えられている前記公開鍵と、前記署名データとの積を前記環Ｒの元ｔとして算出し、前記元ｔのノルムが変化することなく、前記元ｔに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記元ｔの形式を変換することにより、形式が変換された前記元ｔと署名データとからなる署名ベクトルを生成する署名ベクトル生成手段と、
前記署名ベクトル生成手段により生成された署名ベクトルと、前記ハッシュ値生成手段により形式が変換されたハッシュ値との距離に基づいて、前記署名データを検証する距離判定手段とを備える
ことを特徴とする請求項９記載の署名検証装置。
【請求項１５】
署名方式を用いてメッセージデータに対する署名データを生成する署名生成方法であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記署名生成方法は、
前記署名生成ステップと、
前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換ステップと
を含むことを特徴とする署名生成方法。
【請求項１６】
署名方式を用いてメッセージデータに対する署名データを検証する署名検証方法であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記署名検証方法は、
前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定手段と、
前記署名検証ステップと
を含むことを特徴とする署名検証方法。
【請求項１７】
署名方式を用いてメッセージデータに対する署名データを生成するためのプログラムであって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記プログラムは、
前記署名生成ステップと、
前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換ステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項１８】
署名方式を用いてメッセージデータに対する署名データを検証するためのプログラムであって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記プログラムは、
前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定ステップと、
前記署名検証ステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項１９】
署名方式を用いてメッセージデータに対する署名データを生成する集積回路であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記集積回路は、
前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成手段と、
前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換手段と
を備えることを特徴とする集積回路。
【請求項２０】
署名方式を用いてメッセージデータに対する署名データを検証する集積回路であって、
前記署名方式は、
加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
前記集積回路は、
前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定手段と、
前記環Ｒの元である前記署名データを、前記公開鍵を用いて検証する署名検証手段と
を備えることを特徴とする集積回路。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術としての暗号技術に関し、特に、ディジタル署名に基づく処理を行う署名生成装置および署名検証装置に関する。
【背景技術】
【０００２】
受信装置から送信装置へデータを送信する際の送信者の特定及びデータの改ざんを防止するための技術として、公開鍵暗号の一種であるディジタル署名方式がある。
【０００３】
このディジタル署名方式では、送信装置が、送信したいデータに対し、送信装置の秘密鍵を用いて署名データを作成し、送信したいデータと共に署名データを受信装置へ送信する。受信装置は、送信装置の公開鍵を用いて署名データを検証し、改ざんされているか否かを判定する（例えば、非特許文献１参照）。なお、公開鍵から秘密鍵の値は計算困難である。
【０００４】
最近、高速処理が可能な公開鍵暗号として、ＮＴＲＵ（エヌティーアールユー・クリプトシステムズ・インコーポレーテッドの登録商標）暗号が提案された（例えば、非特許文献２参照）。このＮＴＲＵ暗号は、ある法の下でべき乗剰余演算を行うＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）暗号や楕円曲線上の点のスカラ倍演算を行う楕円曲線暗号に比べ、高速に演算可能な多項式演算により暗号化と復号化を行う。したがって、ＮＴＲＵ暗号は、従来の公開鍵暗号よりも高速に処理することが可能で、ソフトウェアの処理でも実用的な時間で処理可能である。
【０００５】
つまり、公開鍵暗号にＮＴＲＵ暗号を用いた暗号通信システムでは、従来の公開鍵暗号を用いた暗号通信システムよりも、送信装置及び受信装置の処理が高速に行えるという利点がある。
【０００６】
ところで、上記非特許文献２で提案された方式は、データを暗号化する守秘暗号方式であったが、その後、ＮＴＲＵ暗号のディジタル署名方式が提案された（例えば、非特許文献３参照）。このようなディジタル署名方式は、解読法の出現などで、その方式が幾度か変更された。
【０００７】
以下では、ＮＴＲＵＳｉｇｎと呼ばれるディジタル署名方式（以下、ＮＴＲＵＳｉｇｎ署名方式という）について簡単に説明する（例えば、特許文献１および非特許文献４参照）。
【０００８】
＜ＮＴＲＵＳｉｇｎ署名方式＞
（１）ＮＴＲＵＳｉｇｎ署名方式のパラメータ
ＮＴＲＵＳｉｇｎ署名方式では、非負整数のパラメータである、Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄが使用される。以下に、これらのパラメータの意味を説明する。
【０００９】
（ｉ）パラメータＮ
ＮＴＲＵＳｉｇｎ署名方式は、多項式の演算により署名生成及び署名検証を行うディジタル署名方式である。ＮＴＲＵＳｉｇｎ署名方式で扱う多項式の次数は、上記パラメータＮにより決まる。
【００１０】
ＮＴＲＵＳｉｇｎ署名方式で扱う多項式は、上記パラメータＮに対し、Ｎ−１次以下の整数係数多項式であり、例えばＮ＝５のとき、Ｘ＾４＋Ｘ＾３＋１等の多項式である。ここで、「Ｘ＾ａ」はＸのａ乗を意味する。また、公開鍵ｈおよび署名ｓはいずれも、Ｎ−１次以下の多項式として表現される。また、秘密鍵は４つのＮ−１次以下の多項式対（ｆ，ｇ，Ｆ，Ｇ）である。すなわち、ｆ，ｇ，Ｆ，ＧはいずれもＮ−１次以下の多項式である。なお、以下では、４つの多項式からなる組（ｆ，ｇ，Ｆ，Ｇ）を、２つの対（ｆ，ｇ），（Ｆ，Ｇ）のさらなる対と捉えて、｛（ｆ，ｇ），（Ｆ，Ｇ）｝と表記する場合もある。
【００１１】
そして、多項式演算は、上記パラメータＮに対し、Ｘ＾Ｎ＝１という関係式を用いて、演算結果が常にＮ−１次以下の多項式になるように演算される。例えば、Ｎ＝５の場合、多項式Ｘ＾４＋Ｘ＾２＋１と多項式Ｘ＾３＋Ｘの積は、多項式と多項式の積を×、整数と多項式の積（あるいは整数と整数の積）を・とすると、Ｘ＾５＝１という関係から、
（Ｘ＾４＋Ｘ＾２＋１）×（Ｘ＾３＋Ｘ）
＝Ｘ＾７＋２・Ｘ＾５＋２・Ｘ＾３＋Ｘ
＝Ｘ＾２・１＋２・１＋２・Ｘ＾３＋Ｘ
＝２・Ｘ＾３＋Ｘ＾２＋Ｘ＋２
というように、常にＮ−１次以下の多項式になるように演算される。
【００１２】
なお、ＮＴＲＵＳｉｇｎ署名方式では、Ｎ−１次の多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）はベクトル（ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１））と同一視される。ここで、ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１）は多項式ａの係数であり、整数である。
【００１３】
（ｉｉ）パラメータｑ
ＮＴＲＵＳｉｇｎ署名方式では、２以上の整数であるパラメータｑを用いる。ＮＴＲＵＳｉｇｎ署名方式で出現する多項式の係数は、ｑを法とした剰余を取る。
【００１４】
（ｉｉｉ）パラメータｄｆ，ｄｇ
ＮＴＲＵＳｉｇｎ署名方式で扱う秘密鍵の一部である多項式ｆ及び、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇの選び方は、それぞれパラメータｄｆ，ｄｇにより決まる。
【００１５】
まず、多項式ｆは、ｄｆ個の係数が１であり、かつ他の係数は０となるように選ばれる。すなわち、多項式ｆは、Ｎ−１次以下の多項式であり、０次（定数項）からＮ−１次まで、Ｎ個の係数があるが、このＮ個の係数のうち、ｄｆ個の係数が１であり、かつ（Ｎ−ｄｆ）個の係数が０となるように選ばれる。そして、多項式ｇは、ｄｇ個の係数が１であり、かつ他の係数は０となるように選ばれる。
【００１６】
（ｉｖ）パラメータＮｏｒｍｂｏｕｎｄ
ＮＴＲＵＳｉｇｎ署名方式では、署名ｓから作られる２・Ｎ次元のベクトルとメッセージデータ（以下、単にメッセージという）のハッシュ値である２・Ｎ次元のベクトルとの距離を計算し、この距離により署名ｓが正しい署名であるかを判定する。Ｎｏｒｍｂｏｕｎｄは、この判定の際に使用されるしきい値である。すなわち、上記距離がＮｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しい署名として受理され、Ｎｏｒｍｂｏｕｎｄ以上であれば、正しくない署名として拒否される。なお、非特許文献４には、ＮＴＲＵＳｉｇｎ署名方式のパラメータの例として、（Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄ）＝（２５１，１２８，７３，７１，３１０）の例が挙げられている。
【００１７】
（２）メッセージのハッシュ値、ノルム及びベクトル間の距離
ＮＴＲＵＳｉｇｎ署名方式では、メッセージのハッシュ値に対する署名を作成する。メッセージのハッシュ値は、Ｎ次の多項式の対であり、２・Ｎ次元のベクトルと同一視される。なお、メッセージからハッシュ値を求めるハッシュ関数については、非特許文献１が詳しい。
【００１８】
ＮＴＲＵＳｉｇｎ署名方式では、署名検証にベクトル間の距離を用い、このような距離の算出にノルム（Ｃｅｎｔｅｒｅｄノルム）を用いる。以下、ノルムおよびベクトル間の距離の定義を示す。
【００１９】
多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）のノルム｜｜ａ｜｜を以下のように定義する。
【００２０】
｜｜ａ｜｜＝ｓｑｒｔ（（ａ＿０−μ）＾２＋（ａ＿１−μ）＾２＋…＋（ａ＿（Ｎ−１）−μ）＾２）
μ＝（１／Ｎ）・（ａ＿０＋ａ＿１＋ａ＿２＋…＋ａ＿（Ｎ−１））
ここで、ｓｑｒｔ（ｘ）はｘの平方根を示す。
【００２１】
多項式ａ，ｂの対（ａ，ｂ）のノルム｜｜（ａ，ｂ）｜｜を以下のように定義する。
【００２２】
｜｜（ａ，ｂ）｜｜＝ｓｑｒｔ（｜｜ａ｜｜＾２＋｜｜ｂ｜｜＾２）
多項式ａ，ｂの対（ａ，ｂ）とｃ，ｄの対（ｃ，ｄ）との距離（ベクトル間の距離）は、｜｜（ｃ−ａ，ｄ−ｂ）｜｜で定義される。
【００２３】
（３）ＮＴＲＵＳｉｇｎ署名方式の鍵生成
ＮＴＲＵＳｉｇｎ署名方式では、上述したように、パラメータｄｆ，ｄｇを用いてランダムに多項式ｆ，多項式ｇを生成する。そして非特許文献４に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈを生成する。さらに、以下の式を満たすようなノルムが小さい多項式Ｆ，Ｇを求める。
【００２４】
ｆ×Ｇ−ｇ×Ｆ＝ｑ
ここで、秘密鍵を｛（ｆ，ｇ），（Ｆ，Ｇ）｝、公開鍵をｈとする。秘密鍵は、署名を生成するための鍵であり、署名生成鍵とも呼ばれる。また、公開鍵は、署名を検証するための鍵であり、署名検証鍵とも呼ばれる。
【００２５】
また、ｘ＝ｙ（ｍｏｄ  ｑ）は、多項式ｙの第ｉ次の係数を、剰余が０からｑ−１の範囲に収まるように法ｑで割ったときの剰余を、多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、多項式ｙの各係数を、０から（ｑ−１）の範囲に収まるように（ｍｏｄ  ｑ）演算した多項式を、多項式ｘとする演算である。
【００２６】
（４）ＮＴＲＵＳｉｇｎ署名方式の署名生成
ＮＴＲＵＳｉｇｎ署名方式の署名生成では、署名対象であるメッセージｍの署名ｓを計算する。まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を計算する。
【００２７】
この２・Ｎ次元のベクトル（ｍ１，ｍ２）と秘密鍵｛（ｆ，ｇ），（Ｆ，Ｇ）｝を用いて、以下の式を満たす多項式ａ，ｂ，Ａ，Ｂを計算する。
【００２８】
Ｇ×ｍ１−Ｆ×ｍ２＝Ａ＋ｑ×Ｂ
−ｇ×ｍ１＋ｆ×ｍ２＝ａ＋ｑ×ｂ
ここで、Ａ，ａの係数は〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を取ったものとする。すなわち、法ｑで割ったときの剰余が〈ｑ／２〉からｑ−１である場合は、ｑ減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。
【００２９】
次に以下の式より、多項式ｓ，ｔを計算し、多項式ｓを署名として出力する。
【００３０】
ｓ＝ｆ×Ｂ＋Ｆ×ｂ  （ｍｏｄ  ｑ）
ｔ＝ｇ×Ｂ＋Ｇ×ｂ  （ｍｏｄ  ｑ）
図１は、署名ｓの生成方法を説明するための説明図である。
【００３１】
ＮＴＲＵＳｉｇｎ署名方式では、秘密鍵行列｛（ｆ，ｇ），（Ｆ，Ｇ）｝により張られる２・Ｎ次元格子上において、メッセージｍに対するハッシュ値Ｈ（ｍ）＝（ｍ１，ｍ２）の最近接格子点Ｐが、上述の式ｓ＝ｆ×Ｂ＋Ｆ×ｂ  （ｍｏｄ  ｑ）およびｔ＝ｇ×Ｂ＋Ｇ×ｂ  （ｍｏｄ  ｑ）により導出される。つまり、（ｍ１，ｍ２）に最も近い格子点が、最近接格子点Ｐとして見つけ出される。そして、その最近接格子点Ｐを示す署名ベクトル（ｓ，ｔ）のうち、多項式ｓだけが署名として扱われる。
【００３２】
（５）ＮＴＲＵＳｉｇｎ署名方式の署名検証
ＮＴＲＵＳｉｇｎ署名方式の署名検証では、署名ｓが署名対象であるメッセージｍの正しい署名であるか否かを検証する。まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）を計算する。
【００３３】
公開鍵ｈを用いて、以下の式より、多項式ｔを計算する。
【００３４】
ｔ＝ｓ×ｈ  （ｍｏｄ  ｑ）
２・Ｎ次元ベクトル（ｓ，ｔ）と（ｍ１，ｍ２）の距離を求め、Ｎｏｒｍｂｏｕｎｄ未満であるかをチェックする。Ｎｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しいと判定してその署名ｓを受理する。Ｎｏｒｍｂｏｕｎｄ以上であれば、署名ｓが不正と判定してその署名ｓを拒否する。
【００３５】
図２は、署名ｓの検証方法を説明するための説明図である。
【００３６】
ＮＴＲＵＳｉｇｎ署名方式では、署名ｓと公開鍵ｈとを用いた上述の式ｔ＝ｓ×ｈ  （ｍｏｄ  ｑ）により、公開鍵行列｛（１，ｈ），（０，ｑ）｝により張られる２・Ｎ次元格子上における格子点Ｐ（ｓ，ｔ）が導出される。ここで、このような２・Ｎ次元格子上において、メッセージｍに対するハッシュ値Ｈ（ｍ）＝（ｍ１，ｍ２）が、格子点Ｐ（ｓ，ｔ）を中心とする半径＝Ｎｏｒｍｂｏｕｎｄの超球内にあるか否かが判定される。超球内にあれば、署名ｓは正しいと判定されて受理され、超球内になければ、署名ｓは不正と判定されて拒否される。
【特許文献１】国際公開第０３／０５０９９８号パンフレット
【非特許文献１】岡本龍明、山本博資、「現代暗号」、産業図書（１９９７年）
【非特許文献２】Ｊ．Ｈｏｆｆｓｔｅｉｎ，  Ｊ．Ｐｉｐｈｅｒ，  ａｎｄ  Ｊ．Ｈ．  Ｓｉｌｖｅｒｍａｎ，  “ＮＴＲＵ：  Ａ  ｒｉｎｇ  ｂａｓｅｄ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ”，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  １４２３，  ｐｐ．２６７−２８８，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９８．
【非特許文献３】Ｊ．Ｈｏｆｆｓｔｅｉｎ，  Ｊ．Ｐｉｐｈｅｒ  ａｎｄ  Ｊ．Ｓｉｌｖｅｒｍａｎ，  “ＮＳＳ：  Ａｎ  ＮＴＲＵ  Ｌａｔｔｉｃｅ−Ｂａｓｅｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ，”  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｐｌｏｇｙ−Ｅｕｒｏｃｒｙｐｔ  ’０１，  ＬＮＣＳ，  Ｖｏｌ．２０４５，  ｐｐ．１２３−１３７，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ２００１．
【非特許文献４】Ｊ．Ｈｏｆｆｓｔｅｉｎ，  Ｎ．Ｇｒａｈａｍ，  Ｊ．Ｐｉｐｈｅｒ，  Ｊ．Ｓｉｌｖｅｒｍａｎ  ａｎｄ  Ｗ．Ｗｈｙｔｅ，  “ＮＴＲＵＳｉｇｎ：  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  Ｕｓｉｎｇ  ｔｈｅ  ＮＴＲＵ  Ｌａｔｔｉｃｅ，”  ＣＴ−ＲＳＡ’０３，  ＬＮＣＳ，  Ｖｏｌ．２６１２，  ｐｐ．１２２−１４０，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ２００３．
【非特許文献５】Ｓ．  Ｍｉｎ，  Ｇ．  Ｙａｍａｍｏｔｏ  ａｎｄ  Ｋ．  Ｋｉｍ，  “Ｏｎ  ｔｈｅ  ｓｅｃｕｒｉｔｙ  ｏｆ  ＮＴＲＵＳｉｇｎ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅ”，  ＳＣＩＳ２００４．
【発明の開示】
【発明が解決しようとする課題】
【００３７】
しかしながら、上記特許文献１および非特許文献４のＮＴＲＵＳｉｇｎ署名方式では、署名を偽造することができるという問題がある。
【００３８】
即ち、上記従来のＮＴＲＵＳｉｇｎ署名方式では、正規の署名ｓにノルム０ベクトルが加算されても、そのノルム０ベクトルが加算された署名ｓも正しい署名として検証される可能性がある。
【００３９】
ノルム０ベクトルは、ノルムが０となるベクトルであって、例えば、全ての要素が１のベクトルがノルム０ベクトルである。
【００４０】
すべての要素が１のベクトルｖ０＝（１，１，…，１）のノルムは、ノルムの定義より、
｜｜ｖ０｜｜＝ｓｑｒｔ（（１−μ）＾２＋（１−μ）＾２＋…＋（１−μ）＾２）
である。
【００４１】
ここで、μ＝（１／Ｎ）・（１＋１＋１＋…＋１）＝１であるため、
｜｜ｖ０｜｜＝ｓｑｒｔ（（１−１）＾２＋（１−１）＾２＋…＋（１−１）＾２）＝０となる。
【００４２】
つまり、署名ｓにノルム０ベクトルｖ０を加算して生成される偽造署名（ｓ＋ｖ０）のノルムは、署名ｓのノルムと等しいため、（ｓ＋ｖ０，ｔ）と（ｍ１，ｍ２）の距離は、（ｓ，ｔ）と（ｍ１，ｍ２）の距離と等しい。その結果、その偽造署名（ｓ＋ｖ０）が署名検証時に正しい署名として検証される。以下、このようなノルム０ベクトルの加算による署名ｓに対する攻撃を、「ノルム０ベクトル偽造攻撃」と呼ぶ。なお、このような攻撃については、非特許文献５で指摘されている。
【００４３】
そこで、本発明は、かかる問題に鑑みてなされたものであって、ノルム０ベクトル偽造攻撃を防ぐことが可能な署名生成装置および署名検証装置を提供することを目的とする。
【課題を解決するための手段】
【００４４】
上記目的を達成するために、本発明に係る署名生成装置は、署名方式を用いてメッセージデータに対する署名データを生成する署名生成装置であって、前記署名方式は、加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、前記署名生成装置は、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成手段と、前記署名データのノルムが変化することなく、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記署名データの形式を変換する署名変換手段とを備えることを特徴とする。
【００４５】
これにより、ＮＴＲＵＳｉｇｎ署名方式により生成された署名データの形式は、そのノルムが変化することなく、対象要素が予め定められた値となる形式に変換されるため、その署名データおよびメッセージデータを取得した署名検証装置は、その署名データに対して、ＮＴＲＵＳｉｇｎ署名方式による署名検証を行うことができるとともに、その署名データの形式に基づいて、ノルム０ベクトル偽造攻撃が試みられたか否かを容易に判定することができる。例えば、署名データに含まれるＮ個の要素のうち一つ目の要素が０となるように、その署名データの形式が変換される場合、その署名データにノルム０ベクトル偽造攻撃が試みられると、その対象要素は０と異なる値になる。したがって、署名検証装置は、その署名データの一つ目の要素が０であるか否かを判別するだけで、ノルム０ベクトル偽造攻撃を簡単に防ぐことができる。その結果、ディジタル署名の安全性を高めることができる。
【００４６】
また、前記署名生成装置は、さらに、前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成し、前記Ｎ次元配列ごとに、当該Ｎ次元配列のノルムが変化することなく、当該Ｎ次元配列に含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記各Ｎ次元配列の形式を変換するハッシュ値生成手段を備え、前記署名生成手段は、前記組｛ｆ，ｇ，Ｆ，Ｇ｝のそれぞれの元の形式が、当該元に含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように整えられている前記秘密鍵と、前記ハッシュ値生成手段により形式が変換されたハッシュ値とを用いて前記署名データを生成することを特徴としてもよい。
【００４７】
これにより、ハッシュ値を示す２つのＮ次元配列と、秘密鍵を示す４つの元ｆ，ｇ，Ｆ，Ｇとはそれぞれ、それらに含まれる対象要素が予め定められた値になっているため、これらに対してノルム０ベクトルが加算されても、その加算行為を容易に検出することができ、ディジタル署名の安全性を確実に高めることができる。
【００４８】
また、本発明に係る署名検証装置は、署名方式を用いてメッセージデータに対する署名データを検証する署名検証装置であって、前記署名方式は、加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ  ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、前記署名検証装置は、前記署名データに含まれるＮ個の要素のうち何れか１つの対象要素が、予め定められた値であるか否かを判定し、予め定められた値でないと判定したときには、前記署名データを不正なものとして扱う署名形式判定手段と、前記環Ｒの元である前記署名データを、前記公開鍵を用いて検証する署名検証手段とを備えることを特徴とする。
【００４９】
例えば、ＮＴＲＵＳｉｇｎ署名方式により生成された署名データのノルムが変化することなく、対象要素が予め定められた値となるように、その署名データの形式が変換されている場合には、署名検証装置は、その署名データに対して、ＮＴＲＵＳｉｇｎ署名方式による署名検証を行うことができるとともに、その署名データの形式に基づいて、ノルム０ベクトル偽造攻撃が試みられたか否かを容易に判定することができる。例えば、署名データに含まれるＮ個の要素のうち一つ目の要素が０となるように、その署名データの形式が変換されている場合、その署名データにノルム０ベクトル偽造攻撃が試みられると、その対象要素は０と異なる値になる。したがって、署名検証装置は、その署名データの一つ目の要素が０であるか否かを判別するだけで、ノルム０ベクトル偽造攻撃を簡単に防ぐことができる。その結果、ディジタル署名の安全性を高めることができる。
【００５０】
また、前記署名検証手段は、前記メッセージデータに対するハッシュ値を示す２つのＮ次元配列を生成し、前記Ｎ次元配列ごとに、当該Ｎ次元配列のノルムが変化することなく、当該Ｎ次元配列の要素のうち何れか１つの対象要素が予め定められた値となるように、前記各Ｎ次元配列の形式を変換するハッシュ値生成手段と、前記元ｈに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように形式が整えられている前記公開鍵と、前記署名データとの積を前記環Ｒの元ｔとして算出し、前記元ｔのノルムが変化することなく、前記元ｔに含まれるＮ個の要素のうち何れか１つの対象要素が予め定められた値となるように、前記元ｔの形式を変換することにより、形式が変換された前記元ｔと署名データとからなる署名ベクトルを生成する署名ベクトル生成手段と、前記署名ベクトル生成手段により生成された署名ベクトルと、前記ハッシュ値生成手段により形式が変換されたハッシュ値との距離に基づいて、前記署名データを検証する距離判定手段とを備えることを特徴としてもよい。
【００５１】
これにより、ハッシュ値を示す２つのＮ次元配列と、公開鍵を示す元ｈと、元ｔとはそれぞれ、それらに含まれる対象要素が予め定められた値になっているため、これらに対してノルム０ベクトルが加算されても、その加算行為を容易に検出することができ、ディジタル署名の安全性を確実に高めることができる。
【００５２】
なお、本発明は、このような署名生成装置および署名検証装置として実現することができるだけでなく、その方法やプログラム、そのプログラムを格納する記憶媒体、集積回路としても実現することができる。
【発明の効果】
【００５３】
本発明の署名生成装置および署名検証装置は、ノルム０ベクトル偽造攻撃を防ぐことができるという作用効果を奏し、その価値は大きい。
【発明を実施するための最良の形態】
【００５４】
（実施の形態）
本発明の実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式は、従来のＮＴＲＵＳｉｇｎ署名方式を改良した署名方式であって、ノルム０ベクトル偽造攻撃を防ぐことが可能なように署名を生成して検証するものである。
【００５５】
以下、本実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式について詳細に説明する。
【００５６】
＜改良ＮＴＲＵＳｉｇｎ署名方式＞
（１）改良ＮＴＲＵＳｉｇｎ署名方式のパラメータ
改良ＮＴＲＵＳｉｇｎ署名方式では、非負整数のパラメータ、Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄが使用される。これらのパラメータの定義は、従来のＮＴＲＵＳｉｇｎ署名方式と同様である。以下に、これらのパラメータの意味を説明する。
【００５７】
（ｉ）パラメータＮ
改良ＮＴＲＵＳｉｇｎ署名方式は、多項式の演算により署名生成及び署名検証を行うディジタル署名方式である。改良ＮＴＲＵＳｉｇｎ署名方式で扱う多項式の次数は、上記パラメータＮにより決まる。
【００５８】
改良ＮＴＲＵＳｉｇｎ署名方式で扱う多項式は、上記パラメータＮに対し、Ｎ−１次以下の整数係数多項式であり、例えばＮ＝５のとき、Ｘ＾４＋Ｘ＾３＋１等の多項式である。ここで、「Ｘ＾ａ」はＸのａ乗を意味する。また、公開鍵ｈおよび署名ｓはいずれも、Ｎ−１次以下の多項式として表現される。また、秘密鍵は４つのＮ−１次以下の多項式対｛ｆ，ｇ，Ｆ，Ｇ｝である。すなわち、ｆ，ｇ，Ｆ，ＧはいずれもＮ−１次以下の多項式である。なお、以下では、４つの多項式からなる組（ｆ，ｇ，Ｆ，Ｇ）を、２つの対（ｆ，ｇ），（Ｆ，Ｇ）のさらなる対と捉えて、｛（ｆ，ｇ），（Ｆ，Ｇ）｝と表記する場合もある。
【００５９】
そして、多項式演算は、上記パラメータＮに対し、Ｘ＾Ｎ＝１という関係式を用いて、演算結果が常にＮ−１次以下の多項式になるように演算される。例えば、Ｎ＝５の場合、多項式Ｘ＾４＋Ｘ＾２＋１と多項式Ｘ＾３＋Ｘの積は、多項式と多項式の積を×、整数と多項式の積（あるいは整数と整数の積）を・とすると、Ｘ＾５＝１という関係から、
（Ｘ＾４＋Ｘ＾２＋１）×（Ｘ＾３＋Ｘ）
＝Ｘ＾７＋２・Ｘ＾５＋２・Ｘ＾３＋Ｘ
＝Ｘ＾２・１＋２・１＋２・Ｘ＾３＋Ｘ
＝２・Ｘ＾３＋Ｘ＾２＋Ｘ＋２
というように、常にＮ−１次以下の多項式になるように演算される。
【００６０】
なお、改良ＮＴＲＵＳｉｇｎ署名方式においても、Ｎ−１次の多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）はベクトル（ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１））と同一視される。ここで、ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１）は多項式ａの係数であり、整数である。
【００６１】
（ｉｉ）パラメータｑ
改良ＮＴＲＵＳｉｇｎ署名方式では、２以上の整数であるパラメータｑを用いる。改良ＮＴＲＵＳｉｇｎ署名方式で出現する多項式の係数は、ｑを法とした剰余を取る。
【００６２】
（ｉｉｉ）パラメータｄｆ，ｄｇ
改良ＮＴＲＵＳｉｇｎ署名方式で扱う秘密鍵の一部である多項式ｆ及び、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇの選び方は、それぞれパラメータｄｆ，ｄｇにより決まる。
【００６３】
まず、多項式ｆは、ｄｆ個の係数が１であり、かつ他の係数は０となるように選ばれる。すなわち、多項式ｆは、Ｎ−１次以下の多項式であり、０次（定数項）からＮ−１次まで、Ｎ個の係数があるが、このＮ個の係数のうち、ｄｆ個の係数が１であり、かつ（Ｎ−ｄｆ）個の係数が０となるように選ばれる。そして、多項式ｇは、ｄｇ個の係数が１であり、かつ他の係数は０となるように選ばれる。
【００６４】
（ｉｖ）パラメータＮｏｒｍｂｏｕｎｄ
改良ＮＴＲＵＳｉｇｎ署名方式では、後述するが署名ｓから作られる２・Ｎ次元のベクトルとメッセージデータ（以下、単にメッセージという）のハッシュ値である２・Ｎ次元のベクトルの距離を計算し、この距離により署名ｓが正しい署名であるかを判定する。Ｎｏｒｍｂｏｕｎｄは、この判定の際に使用するしきい値である。すなわち、上記距離がＮｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しい署名として受理され、Ｎｏｒｍｂｏｕｎｄ以上であれば、正しくない署名として拒否される。なお、非特許文献４には、ＮＴＲＵＳｉｇｎ署名方式のパラメータの例として、（Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄ）＝（２５１，１２８，７３，７１，３１０）の例が挙げられている。改良ＮＴＲＵＳｉｇｎ署名方式においても、同様のパラメータ例を使用してもよい。
【００６５】
（２）メッセージのハッシュ値、ノルム及びベクトル間の距離
改良ＮＴＲＵＳｉｇｎ署名方式においても、メッセージのハッシュ値に対する署名を作成する。メッセージのハッシュ値は、Ｎ次の多項式の対であり、２・Ｎ次元のベクトルと同一視される。なお、メッセージからハッシュ値を求めるハッシュ関数については、非特許文献１が詳しい。
【００６６】
改良ＮＴＲＵＳｉｇｎ署名方式では、従来のＮＴＲＵＳｉｇｎ署名方式と同様、署名検証にベクトル間の距離を用い、このような距離の算出にノルム（Ｃｅｎｔｅｒｅｄノルム）を用いる。以下、ノルムおよびベクトル間の距離の定義を示す。
【００６７】
多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）のノルム｜｜ａ｜｜を以下のように定義する。
【００６８】
｜｜ａ｜｜＝ｓｑｒｔ（（ａ＿０−μ）＾２＋（ａ＿１−μ）＾２＋…＋（ａ＿（Ｎ−１）−μ）＾２）
μ＝（１／Ｎ）・（ａ＿０＋ａ＿１＋ａ＿２＋…＋ａ＿（Ｎ−１））
ここで、ｓｑｒｔ（ｘ）はｘの平方根を示す。
【００６９】
多項式ａ，ｂの対（ａ，ｂ）のノルム｜｜（ａ，ｂ）｜｜を以下のように定義する。
【００７０】
｜｜（ａ，ｂ）｜｜＝ｓｑｒｔ（｜｜ａ｜｜＾２＋｜｜ｂ｜｜＾２）
多項式ａ，ｂの対（ａ，ｂ）とｃ，ｄの対（ｃ，ｄ）との距離（ベクトル間の距離）は、｜｜（ｃ−ａ，ｄ−ｂ）｜｜で定義される。
【００７１】
（３）改良ＮＴＲＵＳｉｇｎ署名方式の鍵生成
改良ＮＴＲＵＳｉｇｎ署名方式では、ＮＴＲＵＳｉｇｎ署名方式と同様の方法で鍵生成を行う。まず、上述したように、パラメータｄｆ，ｄｇを用いてランダムに多項式ｆ，多項式ｇを生成する。そして非特許文献４に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈを生成する。さらに、以下の式を満たすようなノルムが小さい多項式Ｆ，Ｇを求める。
【００７２】
ｆ×Ｇ−ｇ×Ｆ＝ｑ
ここで、秘密鍵を｛（ｆ，ｇ），（Ｆ，Ｇ）｝、公開鍵をｈとする。秘密鍵は、署名を生成するための鍵であり、署名生成鍵とも呼ばれる。また、公開鍵は、署名を検証するための鍵であり、署名検証鍵とも呼ばれる。
【００７３】
また、ｘ＝ｙ（ｍｏｄ  ｑ）は、多項式ｙの第ｉ次の係数を、剰余が０からｑ−１の範囲に収まるように法ｑで割ったときの剰余を、多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、多項式ｙの各係数を、０から（ｑ−１）の範囲に収まるように（ｍｏｄ  ｑ）演算した多項式を、多項式ｘとする演算である。
【００７４】
（４）改良ＮＴＲＵＳｉｇｎ署名方式の署名生成
改良ＮＴＲＵＳｉｇｎ署名方式の署名生成では、署名対象であるメッセージｍの署名ｓを計算する。
【００７５】
まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を計算する。
【００７６】
この２・Ｎ次元のベクトル（ｍ１，ｍ２）と秘密鍵｛（ｆ，ｇ），（Ｆ，Ｇ）｝を用いて、以下の（式１）および（式２）を満たす多項式ａ，ｂ，Ａ，Ｂを計算する。
【００７７】
Ｇ×ｍ１−Ｆ×ｍ２＝Ａ＋ｑ×Ｂ    ・・・（式１）
−ｇ×ｍ１＋ｆ×ｍ２＝ａ＋ｑ×ｂ  ・・・（式２）
ここで、Ａ，ａの係数は〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を取ったものとする。すなわち、法ｑで割ったときの剰余が〈ｑ／２〉からｑ−１である場合は、ｑ減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。
【００７８】
次に以下の（式３）および（式４）より、多項式ｓ，ｔを計算する。
【００７９】
ｓ＝ｆ×Ｂ＋Ｆ×ｂ  （ｍｏｄ  ｑ）  ・・・（式３）
ｔ＝ｇ×Ｂ＋Ｇ×ｂ  （ｍｏｄ  ｑ）  ・・・（式４）
本発明の実施の形態では、さらに、ｓ＝ｓ＿０＋ｓ＿１・Ｘ＋ｓ＿２・Ｘ＾２＋…＋ｓ＿（Ｎ−１）・Ｘ＾（Ｎ−１）とするときに、その多項式ｓと、ノルム０ベクトル（１，１，…，１）に対応する多項式ｖ０とを用いて、以下の（式５）に示すように、署名ｓ’を算出する。
【００８０】
ｓ’＝ｓ−ｓ＿０×ｖ０
＝０＋（ｓ＿１−ｓ＿０）・Ｘ＋（ｓ＿２−ｓ＿０）・Ｘ＾２
＋…＋（ｓ＿（Ｎ−１）−ｓ＿０）・Ｘ＾（Ｎ−１）  ・・・（式５）
すなわち、本実施の形態では、多項式ｓの一つ目の要素（０次の項の係数）を０とするように、多項式ｓからノルム０ベクトルを減算し、その減算結果である多項式ｓ’を署名とする。
【００８１】
言い換えれば、本実施の形態では、多項式ｓのノルムが変化することなく、その多項式ｓに含まれるＮ個の要素のうち一つ目の要素が０となるように、その多項式ｓの形式を変換し、その結果、多項式ｓ’を生成する。
【００８２】
（５）改良ＮＴＲＵＳｉｇｎ署名方式の署名検証
改良ＮＴＲＵＳｉｇｎ署名方式の署名検証では、署名ｓ’が署名対象であるメッセージｍの正しい署名であるか否かを検証する。
【００８３】
具体的に、まず、署名ｓ’の一つ目の要素（０次の項の係数）が０であるか否かをチェックする。一つ目の要素が０でなければ、署名ｓ’が不正であると判定してその署名ｓ’を拒否する。つまり、このようなチェックによって、ノルム０ベクトル偽造攻撃を防ぐことができる。
【００８４】
一方、一つ目の要素が０であれば、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）を計算する。そして、公開鍵ｈを用いて、以下の（式６）より、多項式ｔ’を計算する。
【００８５】
ｔ’＝ｓ’×ｈ  （ｍｏｄ  ｑ）  ・・・（式６）
２・Ｎ次元ベクトル（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離を求め、Ｎｏｒｍｂｏｕｎｄ未満であるかをチェックする。Ｎｏｒｍｂｏｕｎｄ未満であれば、署名ｓ’が正しいと判定してその署名ｓ’を受理する。Ｎｏｒｍｂｏｕｎｄ以上であれば、署名ｓ’が不正と判定してその署名ｓ’を拒否する。なお、２・Ｎ次元ベクトルの距離がＮｏｒｍｂｏｕｎｄ未満であるか否かのチェックを行った後に、署名ｓ’の一つ目の要素が０であるか否かのチェックを行ってもよい。
【００８６】
図３は、本発明の実施の形態におけるディジタル署名システム１００の構成を示すブロック図である。
【００８７】
このディジタル署名システム１００は、上述の改良ＮＴＲＵＳｉｇｎ署名方式を用いて署名を生成して検証するものであって、署名生成装置１１０と、署名検証装置１２０と、通信路１３０とから構成される。
【００８８】
署名生成装置１１０は、改良ＮＴＲＵＳｉｇｎ署名方式により、入力されたメッセージｍに対する署名ｓ’などを含む署名データセットＳＳを生成し、その署名データセットＳＳを署名検証装置１２０へ通信路１３０を介して送信する。また、このような署名生成装置１１０は、送信部１１１と、秘密鍵格納部１１２と、公開鍵証明書格納部１１３と、署名生成部１１４と、署名データセット生成部１１５とを備える。
【００８９】
署名検証装置１２０は、通信路１３０を介して署名生成装置１１０から、署名データセットＳＳを受信し、改良ＮＴＲＵＳｉｇｎ署名方式により、その署名データセットＳＳに含まれる署名ｓ’などを検証する。また、このような署名検証装置１２０は、受信部１２１と、ＣＡ公開鍵格納部１２２と、署名データセット格納部１２３と、署名検証部１２４とを備える。
【００９０】
以下、本実施の形態における署名生成装置１１０について詳細に説明する。
【００９１】
署名生成装置１１０の送信部１１１は、署名データセットＳＳを、通信路１３０を介して署名検証装置１２０へ送信する。
【００９２】
秘密鍵格納部１１２は、メッセージｍに対する署名ｓ’を生成するための秘密鍵ＫＳを格納している。秘密鍵ＫＳは予め与えられているものとする。
【００９３】
公開鍵証明書格納部１１３は、上述の多項式ｈにより示される公開鍵ＫＰ（公開鍵ｈ）の公開鍵証明書ＣＰを格納する。公開鍵証明書ＣＰは、公開鍵ＫＰと、認証局ＣＡによる公開鍵ＫＰの署名を示す署名データＳＰとからなる。この署名データＳＰも、改良ＮＴＲＵＳｉｇｎ署名方式を使用して生成されている。また、公開鍵証明書ＣＰは予め与えられているものとする。なお、公開鍵証明書ＣＰは、公開鍵ＫＰと署名データＳＰ以外の他のデータを含んでいてもよい。例えば、ユーザの識別子や公開鍵証明書ＣＰの期限などを含んでもよい。
【００９４】
署名生成部１１４は、秘密鍵格納部１１２に格納されている秘密鍵ＫＳを用いて、メッセージｍに対する署名ｓ’を示す署名データＳを生成する。
【００９５】
図４は、本実施の形態における署名生成部１１４の構成を示すブロック図である。
【００９６】
署名生成部１１４は、ハッシュ値生成部１１４１と、署名ベクトル生成部１１４２と、署名変換部１１４３とを備える。
【００９７】
ハッシュ値生成部１１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を算出する。
【００９８】
署名ベクトル生成部１１４２は、秘密鍵ＫＳとハッシュ値Ｈを用いて、上記（式１）〜（式４）により、多項式ｓを生成する。
【００９９】
署名変換部１１４３は、署名ベクトル生成部１１４２で生成された多項式ｓを用いて、上記（式５）により、多項式ｓ’を生成する。即ち、多項式ｓがｓ＝ｓ＿０＋ｓ＿１・Ｘ＋ｓ＿２・Ｘ＾２＋…＋ｓ＿（Ｎ−１）・Ｘ＾（Ｎ−１）によって示される場合、署名変換部１１４３は、その多項式ｓと、ノルム０ベクトルであるｖ０＝（１，１，…，１）とを用いて、ｓ’＝０＋（ｓ＿１−ｓ＿０）・Ｘ＋（ｓ＿２−ｓ＿０）・Ｘ＾２＋…＋（ｓ＿（Ｎ−１）−ｓ＿０）・Ｘ＾（Ｎ−１）を算出する。
【０１００】
つまり、本実施の形態における署名変換部１１４３は、多項式ｓの一つ目の要素（０次の項の係数）を０とするよう、多項式ｓからノルム０ベクトルを減算し、その減算結果である多項式ｓ’を署名つまり署名データＳとして生成する。
【０１０１】
言い換えれば、署名変換部１１４３は、多項式ｓのノルムが変化することなく、その多項式ｓに含まれるＮ個の要素のうち一つ目の要素が０となるように、その多項式ｓの形式を変換し、その結果、多項式ｓ’を署名として生成する。
【０１０２】
署名データセット生成部１１５は、メッセージｍと、メッセージｍの署名データＳと、公開鍵証明書ＣＰとからなる署名データセットＳＳを生成する。
【０１０３】
図５は、署名生成部１１４の動作を示すフローチャートである。
【０１０４】
まず、署名生成部１１４のハッシュ値生成部１１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）を算出する（ステップＳ１００）。
【０１０５】
次に、署名生成部１１４の署名ベクトル生成部１１４２は、上記（式１）および（式２）を満たす多項式ａ，ｂ，Ａ，Ｂを算出する（ステップＳ１０２）。さらに、署名ベクトル生成部１１４２は、上記（式３）により、多項式ｓを算出する（ステップＳ１０４）。
【０１０６】
そして、署名生成部１１４の署名変換部１１４３は、上記（式５）により、その多項式ｓからノルム０ベクトルを減算して、一つ目の要素（０次の項の係数）が０である多項式ｓ’を署名つまり署名データＳとして生成する（ステップＳ１０６）。
【０１０７】
図６は、署名生成装置１１０の全体的な動作を示すフローチャートである。
【０１０８】
署名生成装置１１０の署名生成部１１４は、秘密鍵格納部１１２に格納されている秘密鍵ＫＳを用いて、メッセージｍに対する署名データＳを生成する（ステップＳ１２０）。
【０１０９】
次に、署名生成装置１１０の署名データセット生成部１１５は、メッセージｍと、署名データＳと、公開鍵証明書格納部１１３に格納されている公開鍵証明書ＣＰとからなる署名データセットＳＳを生成する（ステップＳ１２２）。
【０１１０】
そして、署名生成装置１１０の送信部１１１は、通信路１３０を介して署名データセットＳＳを署名検証装置１２０へ送信する（ステップＳ１２４）。
【０１１１】
以下、本実施の形態における署名検証装置１２０について詳細に説明する。
【０１１２】
署名検証装置１２０の受信部１２１は、署名生成装置１１０から送信された署名データセットＳＳを、通信路１３０を介して受信する。
【０１１３】
ＣＡ公開鍵格納部１２２は、署名データセットＳＳに含まれる公開鍵証明書ＣＰを検証するための認証局ＣＡの公開鍵ＫＣＰを格納する。
【０１１４】
署名データセット格納部１２３は、受信部１２１で受信された署名データセットＳＳを格納する。
【０１１５】
署名検証部１２４は、署名データセットＳＳに含まれる署名データＳと、公開鍵証明書ＣＰに含まれる署名データＳＰとを検証する。
【０１１６】
図７は、本実施の形態における署名検証部１２４の構成を示すブロック図である。
【０１１７】
署名検証部１２４は、ハッシュ値生成部１２４１と、署名形式判定部１２４２と、署名ベクトル生成部１２４３と、距離判定部１２４４とを備える。
【０１１８】
ハッシュ値生成部１２４１は、署名対象データであるメッセージｍおよび公開鍵ＫＰのそれぞれのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する。
【０１１９】
署名形式判定部１２４２は、改良ＮＴＲＵＳｉｇｎ署名方式の検証対象である署名データＳおよび署名データＳＰのそれぞれの一つ目の要素が０であるか否かを判定する。ここで、署名形式判定部１２４２は、署名データＳおよび署名データＳＰの少なくとも一方における一つ目の要素が０であると判定したときには、受信部１２１で受信された署名データセットＳＳに対してノルム０ベクトル偽造攻撃が試みられたと判断する。つまり、署名形式判定部１２４２は、署名データセットＳＳに対して偽造が行われたと判断する。したがって、本実施の形態では、このような判定を行うことにより、ノルム０ベクトル偽造攻撃を防ぐことができる。
【０１２０】
署名ベクトル生成部１２４３は、署名データＳおよび署名データＳＰのそれぞれにより示される多項式ｓ’と、公開鍵ＫＰまたは公開鍵ＫＣＰにより示される多項式ｈとを用いて、上記（式６）により、多項式ｔ’を算出する。つまり、署名ベクトル生成部１２４３は、ｔ’＝ｓ’×ｈ  （ｍｏｄ  ｑ）により、署名データＳおよび署名データＳＰのそれぞれに対する多項式ｔ’を計算する。
【０１２１】
さらに、署名ベクトル生成部１２４３は、署名データＳおよび署名データＳＰのそれぞれに対して、２・Ｎ次元ベクトル（ｓ’，ｔ’）を署名ベクトルＳＶとして生成する。
【０１２２】
距離判定部１２４４は、メッセージｍおよび署名データＳと、公開鍵ＫＰおよび署名データＳＰとのそれぞれに対して、ハッシュ値Ｈと署名ベクトルＳＶの距離を計算し、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する。即ち、メッセージｍおよび署名データＳに対する、ハッシュ値と署名ベクトルＳＶの距離がＮｏｒｍｂｏｕｎｄ未満であれば、距離判定部１２４４は、署名データＳが正しいと判定してその署名データＳを受理する。一方、Ｎｏｒｍｂｏｕｎｄ以上であれば、距離判定部１２４４は、署名データＳが不正と判定してその署名データＳを拒否する。また、公開鍵ＫＰおよび署名データＳＰに対する、ハッシュ値と署名ベクトルＳＶの距離がＮｏｒｍｂｏｕｎｄ未満であれば、距離判定部１２４４は、署名データＳＰが正しいと判定してその署名データＳＰを受理する。一方、Ｎｏｒｍｂｏｕｎｄ以上であれば、距離判定部１２４４は、署名データＳＰが不正と判定してその署名データＳＰを拒否する。
【０１２３】
図８は、署名検証部１２４の動作を示すフローチャートである。
【０１２４】
署名検証部１２４は、公開鍵ＫＰを用い、メッセージｍおよび署名データＳに対して図８に示す動作を行うことにより、その署名データＳを検証する。なお、署名検証部１２４は、署名データＳの検証を行う前に、公開鍵ＫＣＰを用い、公開鍵ＫＰおよび署名データＳＰに対して図８に示す動作を行うことにより、その署名データＳＰを検証している。
【０１２５】
以下、署名検証部１２４が署名データＳを検証する具体的な動作について、図８を参照して説明する。
【０１２６】
署名検証部１２４の署名形式判定部１２４２は、まず、署名データＳにより示される多項式ｓ’の一つ目の要素（０次の項の係数）が０であるか否かを判定する（ステップＳ１４０）。ここで、署名形式判定部１２４２は、０でないと判定した場合は（ステップＳ１４０のＮ）、署名データＳが不正であるとしてその署名データＳを拒否する（ステップＳ１４２）。一方、署名形式判定部１２４２によって０であると判定された場合は（ステップＳ１４０のＹ）、ハッシュ値生成部１２４１は、その署名データＳに対応するメッセージｍのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する（ステップＳ１４４）。
【０１２７】
次に、署名ベクトル生成部１２４３は、署名データＳにより示される多項式ｓ’と、公開鍵ＫＰにより示される多項式ｈとを用いて、上記（式６）により、多項式ｔ’を算出する（ステップＳ１４６）。このとき、署名ベクトル生成部１２４３は、署名データＳに対して、２・Ｎ次元ベクトル（ｓ’，ｔ’）を署名ベクトルＳＶとして生成する。
【０１２８】
距離判定部１２４４は、ステップＳ１４４で算出されたハッシュ値Ｈ＝（ｍ１，ｍ２）と、ステップＳ１４６で生成された署名ベクトルＳＶとの距離を算出する（ステップＳ１４８）。そして、距離判定部１２４４は、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する（ステップＳ１５０）。距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満であると判定したときには（ステップＳ１５０のＹ）、署名データＳが正しいと判断してその署名データＳを受理する（ステップＳ１５２）。一方、距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満でないと判定したときには（ステップＳ１５０のＮ）、署名データＳが不正であると判断してその署名データＳを拒否する（ステップＳ１４２）。
【０１２９】
図９は、署名検証装置１２０の全体的な動作を示すフローチャートである。
【０１３０】
まず、署名検証装置１２０の受信部１２１は、署名生成装置１１０から通信路１３０を介して署名データセットＳＳを受信し、その署名データセットＳＳを署名データセット格納部１２３に格納する（ステップＳ１７０）。
【０１３１】
署名検証部１２４は、署名データセットＳＳの中の公開鍵証明書ＣＰに含まれる公開鍵ＫＰとその署名データＳＰに対し、署名データＳＰが公開鍵ＫＰの正しい署名であるか否かを、ＣＡ公開鍵格納部１２２に格納されている認証局ＣＡの公開鍵ＫＣＰを用いて検証する。つまり、署名検証部１２４は、署名データＳＰが正しい署名であるか否かを判別する（ステップＳ１７２）。ここで、署名検証部１２４は、正しい署名でないと判別したときには（ステップＳ１７２のＮ）、その署名データＳＰを拒否する（ステップＳ１７４）。
【０１３２】
一方、署名検証部１２４は、ステップＳ１７２で署名データＳＰが正しい署名であると判別したときには（ステップＳ１７２のＹ）、その署名データＳＰを受理し、さらに、署名データセットＳＳの中のメッセージｍとその署名データＳに対し、署名データＳがメッセージｍの正しい署名であるか否かを、公開鍵ＫＰを用いて検証する。つまり、署名検証部１２４は、署名データＳが正しい署名であるか否かを判別する（ステップＳ１７６）。
【０１３３】
ここで、署名検証部１２４は、正しい署名でないと判別したときには（ステップＳ１７６のＮ）、その署名データＳを拒否し（ステップＳ１７４）、正しい署名であると判別したときには（ステップＳ１７６のＹ）、その署名データＳを受理する（ステップＳ１７８）。即ち、ステップＳ１７８では、署名検証部１２４は、署名データセットＳＳが正当な署名を受けたデータであると認識する。
【０１３４】
このように、本実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式で処理を行なうディジタル署名システム１００では、上記（式５）に示すように、多項式ｓのノルムを変化させることなく、その多項式ｓの形式を変換し、その変換結果である、一つ目の要素が０となる形式の多項式ｓ’を署名として扱う。そして、このディジタル署名システム１００では、多項式を示す署名データに対して検証を行うときには、その多項式の一つ目の要素が０であるか否かを判定することで、その署名データに対するノルム０ベクトル偽造攻撃を防ぐことができる。
【０１３５】
つまり、本実施の形態では、署名検証装置１２０は、署名として扱われる多項式が上述のような形式であるか否かを判別し、上述のような形式でなければ、その多項式を不正な署名として扱う。
【０１３６】
例えば、署名生成装置１１０は、一つ目の要素が０となる多項式ｓ’＝０＋ｓ＿１・Ｘ＋ｓ＿２・Ｘ＾２＋…＋ｓ＿（Ｎ−１）・Ｘ＾（Ｎ−１）を署名として生成する。この多項式ｓ’に対してノルム０ベクトルｖ０（１，１，…，１）が加算されると、加算された多項式ｓａは、ｓａ＝ｓ’＋ｖ０＝１＋（ｓ＿１＋１）・Ｘ＋（ｓ＿２＋１）・Ｘ＾２＋…＋（ｓ＿（Ｎ−１）＋１）・Ｘ＾（Ｎ−１）となる。つまり、多項式ｓａの一つ目の要素は０でなく、多項式のｓａの形式は上述のような形式とはならない。そこで、署名検証装置１２０は、多項式ｓａの形式が上述のような形式でないため、その多項式ｓａを不正な署名として扱う。
【０１３７】
つまり、従来では、署名として扱われる多項式にノルム０ベクトルが加算されると、その多項式のノルムと、ノルム０ベクトルが加算された多項式のノルムとは等しいため、ノルム０ベクトルが加算された多項式も正当な署名として扱われてしまう。即ち、従来では、ノルム０ベクトル偽造攻撃を受ける。しかし、本実施の形態では、上述のように、署名生成時に、署名として扱われる多項式の形式を予め定められた形式に変換し、署名検証時には、検証対象の多項式の形式がその予め定められた形式であるか否かを判別する。これにより、署名生成時に生成された多項式のノルムと、検証対象の多項式のノルムとが等しくても、その検証対象の多項式が、ノルム０ベクトルが加算された不正な署名であるか否かを容易に判別することができる。
【０１３８】
言い換えれば、本実施の形態では、従来の２・Ｎ次元ベクトル（ｓ，ｔ）と（ｍ１，ｍ２）との距離が等しくなるような複数の多項式ｓを、予め規定されたフォーマットの１つの多項式でまとめて表し、そのフォーマットの多項式を署名として扱っている。例えば、ｓ’、ｓ’＋（１，１，…，１）、ｓ’＋（２，２，…，２）、ｓ’＋（３，３，…，３）、…をそれぞれ多項式ｓとしたとき、各多項式ｓに対して算出される、２・Ｎ次元ベクトル（ｓ，ｔ）と（ｍ１，ｍ２）との距離はそれぞれ等しくなる。したがって、本実施の形態では、ｓ’、ｓ’＋（１，１，…，１）、ｓ’＋（２，２，…，２）、ｓ’＋（３，３，…，３）、…を、例えば、一つ目の要素が０であるフォーマットの多項式ｓ’でまとめて表し、その多項式ｓ’を署名として扱う。そして、多項式ｓ’に対してノルム０ベクトルが加算されたｓ’＋（２，２，…，２）やｓ’＋（３，３，…，３）などの多項式に対する上記距離と多項式ｓ’に対する上記距離とは等しい。しかし、これらの多項式のフォーマットは多項式ｓ’のフォーマットとは異なるため、これらの多項式は不正な署名であると判断される。
【０１３９】
このように、本実施の形態におけるディジタル署名システム１００では、ノルム０ベクトル偽造攻撃は成功せず、安全である。
【０１４０】
（変形例１）
ここで、上記実施の形態における第１の変形例について説明する。
【０１４１】
上記実施の形態では、一つ目の要素が０である多項式ｓ’を署名として扱ったが、本変形例では、最後の要素（Ｎ−１次の項の係数）が０である多項式ｓ’を署名として扱う。つまり、上記実施の形態において署名として扱われる多項式の形式は、一つ目の要素が０となる形式であったが、本変形例において署名として扱われる多項式の形式は、最後の要素が０となる形式である。
【０１４２】
具体的に、本変形例に係る署名生成部１１４の署名変換部１１４３は、多項式ｓと上記（式５）によって、多項式ｓ’を算出することなく、以下の（式７）によって、多項式ｓ’を算出する。
【０１４３】
ｓ’＝ｓ（ｍｏｄ  Ｌ）  ・・・（式７）
なお、Ｌ＝Ｘ＾（Ｎ−１）＋Ｘ＾（Ｎ−２）＋…＋Ｘ＋１とする。
【０１４４】
図１０は、本変形例に係る署名生成部１１４の動作を示すフローチャートである。
【０１４５】
まず、署名生成部１１４のハッシュ値生成部１１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）を算出する（ステップＳ１９０）。
【０１４６】
次に、署名生成部１１４の署名ベクトル生成部１１４２は、上記（式１）および（式２）を満たす多項式ａ，ｂ，Ａ，Ｂを算出する（ステップＳ１９２）。さらに、署名ベクトル生成部１１４２は、上記（式３）により、多項式ｓを算出する（ステップＳ１９４）。
【０１４７】
そして、署名生成部１１４の署名変換部１１４３は、上記（式７）により、その多項式ｓのＬ（＝Ｘ＾（Ｎ−１）＋Ｘ＾（Ｎ−２）＋…＋Ｘ＋１）を法とする剰余を算出し、最後の要素（Ｎ−１次の項の係数）が０である多項式ｓ’を署名つまり署名データＳとして生成する（ステップＳ１９６）。
【０１４８】
図１１は、本変形例に係る署名検証部１２４の動作を示すフローチャートである。
【０１４９】
署名検証部１２４は、公開鍵ＫＰを用い、メッセージｍおよび署名データＳに対して図１１に示す動作を行うことにより、その署名データＳを検証する。なお、署名検証部１２４は、署名データＳの検証を行う前に、公開鍵ＫＣＰを用い、公開鍵ＫＰおよび署名データＳＰに対して図１１に示す動作を行うことにより、その署名データＳＰを検証している。
【０１５０】
以下、署名検証部１２４が署名データＳを検証する具体的な動作について、図１１を参照して説明する。
【０１５１】
署名検証部１２４の署名形式判定部１２４２は、まず、署名データＳにより示される多項式ｓ’の最後の要素（Ｎ−１次の項の係数）が０であるか否かを判定する（ステップＳ２１０）。ここで、署名形式判定部１２４２は、０でないと判定した場合は（ステップＳ２１０のＮ）、署名データＳが不正であるとしてその署名データＳを拒否する（ステップＳ２１２）。一方、署名形式判定部１２４２によって０であると判定された場合は（ステップＳ２１０のＹ）、ハッシュ値生成部１２４１は、その署名データＳに対応するメッセージｍのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する（ステップＳ２１４）。
【０１５２】
次に、署名ベクトル生成部１２４３は、署名データＳにより示される多項式ｓ’と、公開鍵ＫＰにより示される多項式ｈとを用いて、上記（式６）により、多項式ｔ’を算出する（ステップＳ２１６）。このとき、署名ベクトル生成部１２４３は、署名データＳに対して、２・Ｎ次元ベクトル（ｓ’，ｔ’）を署名ベクトルＳＶとして生成する。
【０１５３】
距離判定部１２４４は、ステップＳ２１４で算出されたハッシュ値Ｈ（＝（ｍ１，ｍ２））と、ステップＳ２１６で生成された署名ベクトルＳＶとの距離を算出する（ステップＳ２１８）。そして、距離判定部１２４４は、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する（ステップＳ２２０）。距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満であると判定したときには（ステップＳ２２０のＹ）、署名データＳが正しいと判断してその署名データＳを受理する（ステップＳ２２２）。一方、距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満でないと判定したときには（ステップＳ２２０のＮ）、署名データＳが不正であると判断してその署名データＳを拒否する（ステップＳ２１２）。
【０１５４】
このように、本変形例では、上記（式７）に示すように、多項式ｓのノルムを変化させることなく、その多項式ｓの形式を変換し、その変換結果である、最後の要素が０となる形式の多項式ｓ’を署名として扱う。そして、このディジタル署名システム１００では、多項式を示す署名データに対して検証を行うときには、その多項式の最後の要素が０であるか否かを判定することで、その署名データに対するノルム０ベクトル偽造攻撃を防ぐことができる。
【０１５５】
（変形例２）
ここで、上記実施の形態における第２の変形例について説明する。
【０１５６】
本変形例では、変形例１と同様、多項式ｓの形式を、その多項式のノルムを変化させることなく、最後の要素（Ｎ−１次の項の係数）が０となるように変換するとともに、メッセージｍに対するハッシュ値、および署名と公開鍵との積のそれぞれの形式も、それぞれのノルムを変化させることなく、最後の要素（Ｎ−１次の項の係数）が０となるように変換する。
【０１５７】
また、本変形例に係るディジタル署名システム１００では、多項式対｛ｆ，ｇ，Ｆ，Ｇ｝の代わりに多項式対｛ｆ”，ｇ”，Ｆ”，Ｇ”｝を秘密鍵とし、多項式ｈの代わりに多項式ｈ”を公開鍵ＫＰとして用いることで、署名生成および署名検証を行う。ここで、Ｌ＝Ｘ＾（Ｎ−１）＋Ｘ＾（Ｎ−２）＋…＋Ｘ＋１とすると、ｆ”，ｇ”，Ｆ”，Ｇ”およびｈ”は以下の式により示される。
【０１５８】
ｆ”＝ｆ（ｍｏｄ  Ｌ）、ｇ”＝ｇ（ｍｏｄ  Ｌ）、Ｆ”＝Ｆ（ｍｏｄ  Ｌ）、Ｇ”＝Ｇ（ｍｏｄ  Ｌ）、ｈ”＝ｈ（ｍｏｄ  Ｌ）
つまり、本変形例で扱われる秘密鍵の４つの多項式はそれぞれ、最後の要素（Ｎ−１次の項の係数）が０となるような形式に整えられており、本変形例で扱われる公開鍵を示す多項式も、最後の要素（Ｎ−１次の項の係数）が０となるような形式に整えられている。なお、多項式ｆ，ｇ，Ｆ，Ｇのそれぞれのノルムは、多項式ｆ”，ｇ”，Ｆ”，Ｇ”のそれぞれのノルムと等しく、多項式ｈのノルムは多項式ｈ”のノルムと等しい。
【０１５９】
図１２は、本変形例に係る署名生成部１１４の動作を示すフローチャートである。
【０１６０】
まず、署名生成部１１４のハッシュ値生成部１１４１は、メッセージｍのハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）を算出する（ステップＳ２３０）。さらに、ハッシュ値生成部１１４１は、（ｍ１”，ｍ２”）を、ｍ１”＝ｍ１  （ｍｏｄ  Ｌ）およびｍ２”＝ｍ２  （ｍｏｄ  Ｌ）により算出する（ステップＳ２３２）。つまり、ハッシュ値生成部１１４１は、２・Ｎ次元のベクトル（ｍ１，ｍ２）の各多項式の形式を、それらの多項式のノルムを変化させることなく、最後の要素（Ｎ−１次の項の係数）が０となるように変換することで、ベクトル（ｍ１”，ｍ２”）を生成する。
【０１６１】
次に、署名生成部１１４の署名ベクトル生成部１１４２は、以下の（式８）および（式９）を満たす多項式ａ”，ｂ”，Ａ”，Ｂ”を算出する（ステップＳ２３４）。
【０１６２】
Ｇ”×ｍ１”−Ｆ”×ｍ２”＝Ａ”＋ｑ×Ｂ”    ・・・（式８）
−ｇ”×ｍ１”＋ｆ”×ｍ２”＝ａ”＋ｑ×ｂ”  ・・・（式９）
さらに、署名ベクトル生成部１１４２は、以下の（式１０）により、多項式ｓを算出する（ステップＳ２３６）。
【０１６３】
ｓ＝ｆ”×Ｂ”＋Ｆ”×ｂ”  （ｍｏｄ  ｑ）  ・・・（式１０）
そして、署名生成部１１４の署名変換部１１４３は、以下の（式１１）により、その多項式ｓのＬ（＝Ｘ＾（Ｎ−１）＋Ｘ＾（Ｎ−２）＋…＋Ｘ＋１）を法とする剰余を算出し、最後の要素（Ｎ−１次の項の係数）が０である多項式ｓ”を署名つまり署名データＳとして生成する（ステップＳ２３８）。
【０１６４】
ｓ”＝ｓ（ｍｏｄ  Ｌ）  ・・・（式１１）
図１３は、本変形例に係る署名検証部１２４の動作を示すフローチャートである。
【０１６５】
署名検証部１２４は、公開鍵ＫＰを用い、メッセージｍおよび署名データＳに対して図１３に示す動作を行うことにより、その署名データＳを検証する。なお、署名検証部１２４は、署名データＳの検証を行う前に、公開鍵ＫＣＰを用い、公開鍵ＫＰおよび署名データＳＰに対して図１３に示す動作を行うことにより、その署名データＳＰを検証している。
【０１６６】
以下、署名検証部１２４が署名データＳを検証する具体的な動作について、図１３を参照して説明する。
【０１６７】
署名検証部１２４の署名形式判定部１２４２は、まず、署名データＳにより示される多項式ｓ”の最後の要素（Ｎ−１次の項の係数）が０であるか否かを判定する（ステップＳ２６０）。ここで、署名形式判定部１２４２は、０でないと判定した場合は（ステップＳ２６０のＮ）、署名データＳが不正であるとしてその署名データＳを拒否する（ステップＳ２６２）。一方、署名形式判定部１２４２によって０であると判定された場合は（ステップＳ２６０のＹ）、ハッシュ値生成部１２４１は、その署名データＳに対応するメッセージｍのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する（ステップＳ２６４）。さらに、ハッシュ値生成部１２４１は、（ｍ１”，ｍ２”）を、ｍ１”＝ｍ１  （ｍｏｄ  Ｌ）およびｍ２”＝ｍ２  （ｍｏｄ  Ｌ）により算出する（ステップＳ２６６）。
【０１６８】
次に、署名ベクトル生成部１２４３は、署名データＳにより示される多項式ｓ”と、公開鍵ＫＰにより示される多項式ｈ”とを用いて、以下の（式１２）により、多項式ｔ”を算出する（ステップＳ２６８）。
【０１６９】
ｔ”＝ｓ”×ｈ”（ｍｏｄ  Ｌ）  ・・・（式１２）
また、このとき、署名ベクトル生成部１２４３は、署名データＳに対して、２・Ｎ次元ベクトル（ｓ”，ｔ”）を署名ベクトルＳＶとして生成する。
【０１７０】
距離判定部１２４４は、ステップＳ２６６で算出されたハッシュ値Ｈ（＝（ｍ１”，ｍ２”））と、ステップＳ２１６で生成された署名ベクトルＳＶとの距離を算出する（ステップＳ２７０）。そして、距離判定部１２４４は、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する（ステップＳ２７２）。距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満であると判定したときには（ステップＳ２７２のＹ）、署名データＳが正しいと判断してその署名データＳを受理する（ステップＳ２７４）。一方、距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満でないと判定したときには（ステップＳ２７２のＮ）、署名データＳが不正であると判断してその署名データＳを拒否する（ステップＳ２６２）。
【０１７１】
このように、本変形例では、署名として扱われる多項式ｓ”だけでなく、秘密鍵の４つの多項式ｆ”，ｇ”，Ｆ”，Ｇ”、公開鍵を示す多項式ｈ”、メッセージｍのハッシュ値（ｍ１”，ｍ２”）、および署名ｓ”と公開鍵ｈ”との積ｔ”のそれぞれの形式も、最後の要素（Ｎ−１次の項の係数）が０となるような形式に整えられている。これにより、多項式ｓ”，ｆ”，ｇ”，Ｆ”，Ｇ”，ｈ”，ｍ１”，ｍ２”，ｔ”のそれぞれに対する安全性を高めることができる。
【０１７２】
また、ｓ”，ｆ”，ｇ”，Ｆ”，Ｇ”，ｈ”，ｍ１”，ｍ２”，ｔ”のそれぞれは、最後の要素が０に固定されているため、最後の要素を格納せず、０〜Ｎ−２次の項のみを格納してもよい。これにより、格納に要するサイズを削減することができる。
【０１７３】
なお、本変形例では、多項式対｛ｆ”，ｇ”，Ｆ”，Ｇ”｝からなる秘密鍵を秘密鍵格納部１１２に予め格納しておいたが、多項式対｛ｆ，ｇ，Ｆ，Ｇ｝からなる秘密鍵を秘密鍵格納部１１２に予め格納しておいてもよい。同様に、本変形例では、多項式ｈ”により示される公開鍵ＫＰを、公開鍵証明書格納部１１３に予め格納しておいたが、多項式ｈにより示される公開鍵ＫＰを、公開鍵証明書格納部１１３に予め格納しておいてもよい。この場合には、署名生成部１１４は、秘密鍵格納部１１２に格納されている多項式対｛ｆ，ｇ，Ｆ，Ｇ｝を多項式対｛ｆ”，ｇ”，Ｆ”，Ｇ”｝に変換し、その多項式対｛ｆ”，ｇ”，Ｆ”，Ｇ”｝を用いて署名ｓ”を生成する。また、署名データセット生成部１１５は、公開鍵証明書格納部１１３に格納されている公開鍵ＫＰを示す多項式ｈを多項式ｈ”に変換し、その多項式ｈ”により示される公開鍵ＫＰを署名データセットＳＳに含める。
【０１７４】
以上、本発明について上記実施の形態および変形例を用いて説明したが、これらは、本発明の一例であり、本発明はこのような実施の形態および変形例に何ら限定されるものではない。つまり、本発明は、本発明の本質を逸脱しない範囲において種々なる態様で実施し得るものである。例えば、以下のような場合も本発明に含まれる。
【０１７５】
（１）  上記実施の形態および変形例では、署名生成時に、多項式ｓ’の一つ目の要素（０次の項の係数）または最後の要素（Ｎ−１次の項の係数）を０とし、署名検証時に、その要素が０であるかを検証しているが、この要素以外の要素を０としてもよい。例えば、ｉ番目（ｉは２からＮ−１のいずれかの整数）の要素を０としてもよい。また、その要素を「０」ではなく、ｊ（ｊは１からｑ−１のいずれかの整数）としてもよい。また、その要素を、多項式ｍ１に含まれる何れかの要素と等しくなるようにしてもよい。例えば、署名生成時に、多項式ｓ’の一つ目の要素を、多項式ｍ１の一つ目の要素と等しくなるようにし、署名検証時に、多項式ｓ’の一つ目の要素が、多項式ｍ１の一つ目の要素と等しいかを検証してもよい。
【０１７６】
（２）  上記実施の形態および変形例における署名生成装置１１０および署名検証装置１２０は、具体的には、マイクロプロセッサ、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、ハードディスクユニット、ディスプレイユニット、キーボード、およびマウスなどから構成されるコンピュータシステムである。前記ＲＡＭまたはハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、署名生成装置１１０および署名検証装置１２０は、その機能を達成する。ここでコンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。
【０１７７】
（３）  上記実施の形態および変形例における署名生成装置１１０および署名検証装置１２０を構成する構成要素の一部または全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、システムＬＳＩは、その機能を達成する。
【０１７８】
（４）  上記実施の形態および変形例における署名生成装置１１０および署名検証装置１２０を構成する構成要素の一部または全部は、署名生成装置１１０または署名検証装置１２０に脱着可能なＩＣ（Integrated Circuit）カード、または単体のモジュールから構成されているとしてもよい。前記ＩＣカードまたは前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。前記ＩＣカードまたは前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムにしたがって動作することにより、前記ＩＣカードまたは前記モジュールは、その機能を達成する。このＩＣカードまたはこのモジュールは、耐タンパ性を有するとしてもよい。
【０１７９】
（５）  本発明は、上記実施の形態および変形例におけるディジタル署名システム１００におけるそのシステムや装置として実現されるだけでなく、処理方法としても実現できる。また、この処理方法による動作をコンピュータに実行させるコンピュータプログラムとして実現してもよく、前記コンピュータプログラムからなるディジタル信号として実現してもよい。
【０１８０】
（６）  また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、ＭＯ（Magneto-Optical disk）、ＤＶＤ（Digital Versatile Disk）、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなどに記録したものとして実現してもよい。また、これらの記録媒体に記録されている前記ディジタル信号として実現してもよい。
【０１８１】
（７）  また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を、電気通信回線、無線または有線通信回線、インターネットを代表とするネットワーク、もしくはデータ放送等を経由して伝送するものとして実現してもよい。
【０１８２】
（８）  また、本発明は、マイクロプロセッサとメモリを備えたコンピュータシステムとして実現しても良い。この場合には、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムにしたがって動作する。
【０１８３】
（９）  また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を前記記録媒体に記録して移送することにより、または前記コンピュータプログラムまたは前記ディジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実現してもよい。
【０１８４】
（１０）  また、本発明は、上記実施の形態および変形例をそれぞれ組み合わせて実現してもよい。
【産業上の利用可能性】
【０１８５】
本発明の署名生成装置および署名検証装置は、ＮＴＲＵＳｉｇｎ署名方式等におけるノルム０ベクトル偽造攻撃を防ぐことができるという効果を奏し、例えば、ディジタル署名システムなどに適用することができる。
【図面の簡単な説明】
【０１８６】
【図１】図１は、署名の生成方法を説明するための説明図である。
【図２】図２は、署名の検証方法を説明するための説明図である。
【図３】図３は、本発明の実施の形態におけるディジタル署名システムの構成を示すブロック図である。
【図４】図４は、本発明の実施の形態における署名生成部の構成を示すブロック図である。
【図５】図５は、本発明の実施の形態における署名生成部の動作を示すフローチャートである。
【図６】図６は、本発明の実施の形態における署名生成装置の全体的な動作を示すフローチャートである。
【図７】図７は、本発明の実施の形態における署名検証部の構成を示すブロック図である。
【図８】図８は、本発明の実施の形態における署名検証部の動作を示すフローチャートである。
【図９】図９は、本発明の実施の形態における署名検証装置の全体的な動作を示すフローチャートである。
【図１０】図１０は、本発明の実施の形態における変形例１の署名生成部の動作を示すフローチャートである。
【図１１】図１１は、本発明の実施の形態における変形例１の署名検証部の動作を示すフローチャートである。
【図１２】図１２は、本発明の実施の形態における変形例２の署名生成部の動作を示すフローチャートである。
【図１３】図１３は、本発明の実施の形態における変形例２の署名検証部の動作を示すフローチャートである。
【符号の説明】
【０１８７】
１００    ディジタル署名システム
１１０    署名生成装置
１１１    送信部
１１２    秘密鍵格納部
１１３    公開鍵証明書格納部
１１４    署名生成部
１１５    署名データセット生成部
１２０    署名検証装置
１２１    受信部
１２２    ＣＡ公開鍵格納部
１２３    署名データセット格納部
１２４    署名検証部
１３０    通信路
１１４１  ハッシュ値生成部
１１４２  署名ベクトル生成部
１１４３  署名変換部
１２４１  ハッシュ値生成部
１２４２  署名形式判定部
１２４３  署名ベクトル生成部
１２４４  距離判定部
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2006114948.tif 000016
【図２】
2006114948.tif 000017
【図３】
2006114948.tif 000018
【図４】
2006114948.tif 000019
【図５】
2006114948.tif 000020
【図６】
2006114948.tif 000021
【図７】
2006114948.tif 000022
【図８】
2006114948.tif 000023
【図９】
2006114948.tif 000024
【図１０】
2006114948.tif 000025
【図１１】
2006114948.tif 000026
【図１２】
2006114948.tif 000027
【図１３】
2006114948.tif 000028
【国際調査報告】
2006114948.tif 000029
2006114948.tif 000030
2006114948.tif 000031
2006114948.tif 000032
2006114948.tif 000033
2006114948.tif 000034