JP4620669B2 - 署名生成装置、署名検証装置、それらの方法、および集積回路 - Google Patents

Description

本発明は、情報セキュリティ技術としての暗号技術に関し、特に、ディジタル署名に基づく処理を行う署名生成装置および署名検証装置に関する。

受信装置から送信装置へデータを送信する際の送信者の特定及びデータの改ざんを防止するための技術として、公開鍵暗号の一種であるディジタル署名方式がある。

このディジタル署名方式では、送信装置が、送信したいデータに対し、送信装置の秘密鍵を用いて署名データを作成し、送信したいデータと共に署名データを受信装置へ送信する。受信装置は、送信装置の公開鍵を用いて署名データを検証し、改ざんされているか否かを判定する（例えば、非特許文献１参照）。なお、公開鍵から秘密鍵の値は計算困難である。

最近、高速処理が可能な公開鍵暗号として、ＮＴＲＵ（エヌティーアールユー・クリプトシステムズ・インコーポレーテッドの登録商標）暗号が提案された（例えば、非特許文献２参照）。このＮＴＲＵ暗号は、ある法の下でべき乗剰余演算を行うＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）暗号や楕円曲線上の点のスカラ倍演算を行う楕円曲線暗号に比べ、高速に演算可能な多項式演算により暗号化と復号化を行う。したがって、ＮＴＲＵ暗号は、従来の公開鍵暗号よりも高速に処理することが可能で、ソフトウェアの処理でも実用的な時間で処理可能である。

つまり、公開鍵暗号にＮＴＲＵ暗号を用いた暗号通信システムでは、従来の公開鍵暗号を用いた暗号通信システムよりも、送信装置及び受信装置の処理が高速に行えるという利点がある。

ところで、上記非特許文献２で提案された方式は、データを暗号化する守秘暗号方式であったが、その後、ＮＴＲＵ暗号のディジタル署名方式が提案された（例えば、非特許文献３参照）。このようなディジタル署名方式は、解読法の出現などで、その方式が幾度か変更された。

以下では、ＮＴＲＵＳｉｇｎと呼ばれるディジタル署名方式（以下、ＮＴＲＵＳｉｇｎ署名方式という）について簡単に説明する（例えば、特許文献１および非特許文献４参照）。

＜ＮＴＲＵＳｉｇｎ署名方式＞
（１）ＮＴＲＵＳｉｇｎ署名方式のパラメータ
ＮＴＲＵＳｉｇｎ署名方式では、非負整数のパラメータである、Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄが使用される。以下に、これらのパラメータの意味を説明する。

（ｉ）パラメータＮ
ＮＴＲＵＳｉｇｎ署名方式は、多項式の演算により署名生成及び署名検証を行うディジタル署名方式である。ＮＴＲＵＳｉｇｎ署名方式で扱う多項式の次数は、上記パラメータＮにより決まる。

ＮＴＲＵＳｉｇｎ署名方式で扱う多項式は、上記パラメータＮに対し、Ｎ−１次以下の整数係数多項式であり、例えばＮ＝５のとき、Ｘ＾４＋Ｘ＾３＋１等の多項式である。ここで、「Ｘ＾ａ」はＸのａ乗を意味する。また、公開鍵ｈおよび署名ｓはいずれも、Ｎ−１次以下の多項式として表現される。また、秘密鍵は４つのＮ−１次以下の多項式対（ｆ，ｇ，Ｆ，Ｇ）である。すなわち、ｆ，ｇ，Ｆ，ＧはいずれもＮ−１次以下の多項式である。なお、以下では、４つの多項式からなる組（ｆ，ｇ，Ｆ，Ｇ）を、２つの対（ｆ，ｇ），（Ｆ，Ｇ）のさらなる対と捉えて、｛（ｆ，ｇ），（Ｆ，Ｇ）｝と表記する場合もある。

そして、多項式演算は、上記パラメータＮに対し、Ｘ＾Ｎ＝１という関係式を用いて、演算結果が常にＮ−１次以下の多項式になるように演算される。例えば、Ｎ＝５の場合、多項式Ｘ＾４＋Ｘ＾２＋１と多項式Ｘ＾３＋Ｘの積は、多項式と多項式の積を×、整数と多項式の積（あるいは整数と整数の積）を・とすると、Ｘ＾５＝１という関係から、
（Ｘ＾４＋Ｘ＾２＋１）×（Ｘ＾３＋Ｘ）
＝Ｘ＾７＋２・Ｘ＾５＋２・Ｘ＾３＋Ｘ
＝Ｘ＾２・１＋２・１＋２・Ｘ＾３＋Ｘ
＝２・Ｘ＾３＋Ｘ＾２＋Ｘ＋２
というように、常にＮ−１次以下の多項式になるように演算される。

なお、ＮＴＲＵＳｉｇｎ署名方式では、Ｎ−１次の多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）はベクトル（ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１））と同一視される。ここで、ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１）は多項式ａの係数であり、整数である。

（ｉｉ）パラメータｑ
ＮＴＲＵＳｉｇｎ署名方式では、２以上の整数であるパラメータｑを用いる。ＮＴＲＵＳｉｇｎ署名方式で出現する多項式の係数は、ｑを法とした剰余を取る。

（ｉｉｉ）パラメータｄｆ，ｄｇ
ＮＴＲＵＳｉｇｎ署名方式で扱う秘密鍵の一部である多項式ｆ及び、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇの選び方は、それぞれパラメータｄｆ，ｄｇにより決まる。

まず、多項式ｆは、ｄｆ個の係数が１であり、かつ他の係数は０となるように選ばれる。すなわち、多項式ｆは、Ｎ−１次以下の多項式であり、０次（定数項）からＮ−１次まで、Ｎ個の係数があるが、このＮ個の係数のうち、ｄｆ個の係数が１であり、かつ（Ｎ−ｄｆ）個の係数が０となるように選ばれる。そして、多項式ｇは、ｄｇ個の係数が１であり、かつ他の係数は０となるように選ばれる。

（ｉｖ）パラメータＮｏｒｍｂｏｕｎｄ
ＮＴＲＵＳｉｇｎ署名方式では、署名ｓから作られる２・Ｎ次元のベクトルとメッセージデータ（以下、単にメッセージという）のハッシュ値である２・Ｎ次元のベクトルとの距離を計算し、この距離により署名ｓが正しい署名であるかを判定する。Ｎｏｒｍｂｏｕｎｄは、この判定の際に使用されるしきい値である。すなわち、上記距離がＮｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しい署名として受理され、Ｎｏｒｍｂｏｕｎｄ以上であれば、正しくない署名として拒否される。なお、非特許文献４には、ＮＴＲＵＳｉｇｎ署名方式のパラメータの例として、（Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄ）＝（２５１，１２８，７３，７１，３１０）の例が挙げられている。

（２）メッセージのハッシュ値、ノルム及びベクトル間の距離
ＮＴＲＵＳｉｇｎ署名方式では、メッセージのハッシュ値に対する署名を作成する。メッセージのハッシュ値は、Ｎ次の多項式の対であり、２・Ｎ次元のベクトルと同一視される。なお、メッセージからハッシュ値を求めるハッシュ関数については、非特許文献１が詳しい。

ＮＴＲＵＳｉｇｎ署名方式では、署名検証にベクトル間の距離を用い、このような距離の算出にノルム（Ｃｅｎｔｅｒｅｄノルム）を用いる。以下、ノルムおよびベクトル間の距離の定義を示す。

多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）のノルム｜｜ａ｜｜を以下のように定義する。

｜｜ａ｜｜＝ｓｑｒｔ（（ａ＿０−μ）＾２＋（ａ＿１−μ）＾２＋…＋（ａ＿（Ｎ−１）−μ）＾２）
μ＝（１／Ｎ）・（ａ＿０＋ａ＿１＋ａ＿２＋…＋ａ＿（Ｎ−１））
ここで、ｓｑｒｔ（ｘ）はｘの平方根を示す。

多項式ａ，ｂの対（ａ，ｂ）のノルム｜｜（ａ，ｂ）｜｜を以下のように定義する。

｜｜（ａ，ｂ）｜｜＝ｓｑｒｔ（｜｜ａ｜｜＾２＋｜｜ｂ｜｜＾２）
多項式ａ，ｂの対（ａ，ｂ）とｃ，ｄの対（ｃ，ｄ）との距離（ベクトル間の距離）は、｜｜（ｃ−ａ，ｄ−ｂ）｜｜で定義される。

（３）ＮＴＲＵＳｉｇｎ署名方式の鍵生成
ＮＴＲＵＳｉｇｎ署名方式では、上述したように、パラメータｄｆ，ｄｇを用いてランダムに多項式ｆ，多項式ｇを生成する。そして非特許文献４に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ ｑ）
により、多項式ｈを生成する。さらに、以下の式を満たすようなノルムが小さい多項式Ｆ，Ｇを求める。

ｆ×Ｇ−ｇ×Ｆ＝ｑ
ここで、秘密鍵を｛（ｆ，ｇ），（Ｆ，Ｇ）｝、公開鍵をｈとする。秘密鍵は、署名を生成するための鍵であり、署名生成鍵とも呼ばれる。また、公開鍵は、署名を検証するための鍵であり、署名検証鍵とも呼ばれる。

また、ｘ＝ｙ（ｍｏｄ ｑ）は、多項式ｙの第ｉ次の係数を、剰余が０からｑ−１の範囲に収まるように法ｑで割ったときの剰余を、多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、多項式ｙの各係数を、０から（ｑ−１）の範囲に収まるように（ｍｏｄ ｑ）演算した多項式を、多項式ｘとする演算である。

（４）ＮＴＲＵＳｉｇｎ署名方式の署名生成
ＮＴＲＵＳｉｇｎ署名方式の署名生成では、署名対象であるメッセージｍの署名ｓを計算する。まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を計算する。

この２・Ｎ次元のベクトル（ｍ１，ｍ２）と秘密鍵｛（ｆ，ｇ），（Ｆ，Ｇ）｝を用いて、以下の式を満たす多項式ａ，ｂ，Ａ，Ｂを計算する。

Ｇ×ｍ１−Ｆ×ｍ２＝Ａ＋ｑ×Ｂ
−ｇ×ｍ１＋ｆ×ｍ２＝ａ＋ｑ×ｂ
ここで、Ａ，ａの係数は〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を取ったものとする。すなわち、法ｑで割ったときの剰余が〈ｑ／２〉からｑ−１である場合は、ｑ減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。

次に以下の式より、多項式ｓ，ｔを計算し、多項式ｓを署名として出力する。

ｓ＝ｆ×Ｂ＋Ｆ×ｂ （ｍｏｄ ｑ）
ｔ＝ｇ×Ｂ＋Ｇ×ｂ （ｍｏｄ ｑ）

図１は、署名ｓの生成方法を説明するための説明図である。

ＮＴＲＵＳｉｇｎ署名方式では、秘密鍵行列｛（ｆ，ｇ），（Ｆ，Ｇ）｝により張られる２・Ｎ次元格子上において、メッセージｍに対するハッシュ値Ｈ（ｍ）＝（ｍ１，ｍ２）の最近接格子点Ｐが、上述の式ｓ＝ｆ×Ｂ＋Ｆ×ｂ （ｍｏｄ ｑ）およびｔ＝ｇ×Ｂ＋Ｇ×ｂ （ｍｏｄ ｑ）により導出される。つまり、（ｍ１，ｍ２）に最も近い格子点が、最近接格子点Ｐとして見つけ出される。そして、その最近接格子点Ｐを示す署名ベクトル（ｓ，ｔ）のうち、多項式ｓだけが署名として扱われる。

（５）ＮＴＲＵＳｉｇｎ署名方式の署名検証
ＮＴＲＵＳｉｇｎ署名方式の署名検証では、署名ｓが署名対象であるメッセージｍの正しい署名であるか否かを検証する。まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）を計算する。

公開鍵ｈを用いて、以下の式より、多項式ｔを計算する。

ｔ＝ｓ×ｈ （ｍｏｄ ｑ）
２・Ｎ次元ベクトル（ｓ，ｔ）と（ｍ１，ｍ２）の距離を求め、Ｎｏｒｍｂｏｕｎｄ未満であるかをチェックする。Ｎｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しいと判定してその署名ｓを受理する。Ｎｏｒｍｂｏｕｎｄ以上であれば、署名ｓが不正と判定してその署名ｓを拒否する。

図２は、署名ｓの検証方法を説明するための説明図である。

ＮＴＲＵＳｉｇｎ署名方式では、署名ｓと公開鍵ｈとを用いた上述の式ｔ＝ｓ×ｈ （ｍｏｄ ｑ）により、公開鍵行列｛（１，ｈ），（０，ｑ）｝により張られる２・Ｎ次元格子上における格子点Ｐ（ｓ，ｔ）が導出される。ここで、このような２・Ｎ次元格子上において、メッセージｍに対するハッシュ値Ｈ（ｍ）＝（ｍ１，ｍ２）が、格子点Ｐ（ｓ，ｔ）を中心とする半径＝Ｎｏｒｍｂｏｕｎｄの超球内にあるか否かが判定される。超球内にあれば、署名ｓは正しいと判定されて受理され、超球内になければ、署名ｓは不正と判定されて拒否される。

ここで、上述のＮＴＲＵＳｉｇｎ署名方式では、正しい署名ｓであっても、署名検証時に「不正」と判定される場合（署名検証エラー）が存在する。

Ｎを２としたときの署名検証エラーの例を以下に示す。以下では、ｓとｍ１の距離に着目する。ｑ＝１２８、ｍ１＝（１，１２７）、ｓ＝（−３，１２４）とする。このとき、ｓ ｍｏｄ ｑ＝（１２５，１２４）となる。ｍ１−ｓ＝（４，３）であり、ｍ１とｓの距離は｜｜ｍ１−ｓ｜｜＝ｓｑｒｔ（（４−３．５）＾２＋（３−３．５）＾２）＝ｓｑｒｔ（０．５）である。しかし、ｍ１−（ｓ ｍｏｄ ｑ）＝（−１２４，３）であるため、ｍ１と（ｓ ｍｏｄ ｑ）の距離は｜｜ｍ１−（ｓ ｍｏｄ ｑ）｜｜＝ｓｑｒｔ（（−１２４−（−６０．５））＾２＋（３−（−６０．５））＾２）＝ｓｑｒｔ（８０６４．５）となり、その距離が大きくなってしまう。Ｎｏｒｍｂｏｕｎｄが小さい場合は、ｓに対して、ｑを法とした剰余を取ることにより、距離が大きくなり、正しい署名であってもその署名を不正と判定してしまい、不適切な署名検証エラーが発生する。

そこで、上述の不適切な署名検証エラーの発生を防ぐ方法が提案されている（例えば、非特許文献５参照）。具体的には、まず、署名検証時に、ｓ ｍｏｄ ｑに対し、ノルムが０となるベクトル（α，…，α）（すべての要素がαのベクトル）を加算して、ｑを法とした剰余を取ることにより、多項式ｓ’＝（ｓ ｍｏｄ ｑ）＋（α，…，α） ｍｏｄ ｑを計算する。次に、ｓ’と公開鍵ｈを用いてｔ’＝ｓ×ｈ （ｍｏｄ ｑ）を計算し、２・Ｎ次元ベクトル（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離を求め、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かをチェックする。すなわち、αに１からｑ−１の値を代入して、１からｑ−１のそれぞれの場合の距離を求め、それらの距離がＮｏｒｍｂｏｕｎｄ未満であるか否かをチェックする。その結果、何れかの距離がＮｏｒｍｂｏｕｎｄ未満であれば、署名ｓが正しいと判定してその署名ｓを受理する。一方、１からｑ−１のすべてのαの値に対する距離がＮｏｒｍｂｏｕｎｄ未満でなければ、署名ｓが不正であると判定して署名ｓを拒否する。

ここで、上述のような例の場合、ｓ ｍｏｄ ｑ＝（１２５，１２４）に対し、α＝３として（α，α）を加算すると、ｓ’＝（ｓ ｍｏｄ ｑ）＋（α，α）＝（１２５，１２４）＋（３，３）＝（１２８，１２７）＝（０，１２７） ｍｏｄ ｑとなる。このとき、ｍ１とｓ’の距離は、｜｜ｍ１−ｓ’｜｜＝｜｜（１，０）｜｜＝ｓｑｒｔ（（１−０．５）＾２＋（０−０．５）＾２）＝ｓｑｒｔ（０．５）となり、ｍ１とｓ’の距離は、ｍ１とｓの距離と同じになる。したがって、このような場合は、正しく署名が生成されていれば署名検証時に正しいと判定されるため、不適切な署名検証エラーを防ぐことが可能になる。
国際公開第０３／０５０９９８号パンフレット 岡本龍明、山本博資、「現代暗号」、産業図書（１９９７年） Ｊ．Ｈｏｆｆｓｔｅｉｎ， Ｊ．Ｐｉｐｈｅｒ， ａｎｄ Ｊ．Ｈ． Ｓｉｌｖｅｒｍａｎ， "ＮＴＲＵ： Ａ ｒｉｎｇ ｂａｓｅｄ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍ"， Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， １４２３， ｐｐ．２６７−２８８， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， １９９８． Ｊ．Ｈｏｆｆｓｔｅｉｎ， Ｊ．Ｐｉｐｈｅｒ ａｎｄ Ｊ．Ｓｉｌｖｅｒｍａｎ， "ＮＳＳ： Ａｎ ＮＴＲＵ Ｌａｔｔｉｃｅ−Ｂａｓｅｄ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ，" Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｐｌｏｇｙ−Ｅｕｒｏｃｒｙｐｔ ’０１， ＬＮＣＳ， Ｖｏｌ．２０４５， ｐｐ．１２３−１３７， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， ２００１． Ｊ．Ｈｏｆｆｓｔｅｉｎ， Ｎ．Ｇｒａｈａｍ， Ｊ．Ｐｉｐｈｅｒ， Ｊ．Ｓｉｌｖｅｒｍａｎ ａｎｄ Ｗ．Ｗｈｙｔｅ， "ＮＴＲＵＳｉｇｎ： Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅｓ Ｕｓｉｎｇ ｔｈｅ ＮＴＲＵ Ｌａｔｔｉｃｅ，" ＣＴ−ＲＳＡ’０３， ＬＮＣＳ， Ｖｏｌ．２６１２， ｐｐ．１２２−１４０， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， ２００３． "Ｅｆｆｉｃｉｅｎｔ Ｅｍｂｅｄｄｅｄ Ｓｅｃｕｒｉｔｙ Ｓｔａｎｄａｒｄｓ （ＥＥＳＳ） ＥＥＳＳ ＃１： Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ Ａｓｐｅｃｔｓ ｏｆ ＮＴＲＵＥｎｃｒｙｐｔ ａｎｄ ＮＴＲＵＳｉｇｎ"， Ｖｅｒ２．０， Ｊｕｎｅ ２０ｔｈ， ２００３．

しかしながら、上記非特許文献５の方法であっても、不適切な署名検証エラーが発生してしまうという問題がある。

上記非特許文献５の方法では、以下の場合に、不適切な署名検証エラーを発生させてしまう。

例えば、ｑ＝１２８、ｍ１＝（−２，１２７），ｓ＝（０，１２９）とする。このとき、ｓ ｍｏｄ ｑ＝（０，１）となる。ｍ１−ｓ＝（−２，−２）であり，ｍ１とｓの距離は｜｜ｍ１−ｓ｜｜＝ｓｑｒｔ（（−２−（−２））＾２＋（−２−（−２））＾２）＝０である。しかし、ｍ１−（ｓ ｍｏｄ ｑ）＝（−２，１２６）であるため、ｍ１とｓ ｍｏｄ ｑの距離は｜｜ｍ１−（ｓ ｍｏｄ ｑ）｜｜＝ｓｑｒｔ（（−２−６２）＾２＋（１２６−６２）＾２）＝ｓｑｒｔ（８１９２）となり、距離が大きくなってしまう。ここで、上記非特許文献５の方法を試みる。しかし、多項式ｓの要素の最大値１２９と最小値０の差は１２９であり、ｑ＝１２８を超えるため、上記非特許文献５の方法では、多項式ｓに対して（α，α）を加算した後、その加算結果に対して、ｑを法とする剰余を取っても、要素の最大値と最小値の差が１２９となるような多項式ｓ’を求めることができない。

したがって、上記のように多項式ｓの要素の最大値と最小値の差がｑを超える場合は、多項式ｓに対して法をｑとする剰余を取る（ｓ ｍｏｄ ｑを行う）ことにより、情報が欠落してしまうため、不適切な署名検証エラーが発生してしまう。

そこで、本発明は、かかる問題に鑑みてなされたものであって、不適切な署名検証エラーの発生を確実に防ぐことが可能な署名生成装置および署名検証装置を提供することを目的とする。

上記目的を達成するために、本発明に係る署名生成装置は、メッセージデータに対する署名データを、署名方式に従って生成する署名生成装置であって、前記署名方式は、加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、前記署名生成装置は、前記メッセージデータに対する、前記環Ｒの元ｓ，ｔからなる署名ベクトルを、前記秘密鍵を用いて算出する署名ベクトル生成手段と、前記元ｓを特定し得る前記環Ｒの第１の元と、前記元ｔをｑで割ったときの商である前記環Ｒの第２の元とを示す前記署名データを生成する署名データ生成手段とを備えることを特徴とする。例えば、前記第１の元は、前記元ｓをｑで割ったときの商である前記環Ｒの元ｓｈと、前記元ｓをｑで割ったときの余りである前記環Ｒの元ｓｌとからなる。

これにより、署名データは、元ｓを特定し得る第１の元と、元ｔをｑで割ったときの商である第２の元とを示すため、その署名データおよびメッセージデータを取得した署名検証装置は、その署名データにより示される第１の元を用いて、署名ベクトルの一部である元ｓを正しく復元することができる。例えば、第１の元が、元ｓをｑで割ったときの商および余りである元ｓｈ，ｓｌからなる場合には、署名検証装置は、その元ｓｈにｑを乗算して前記元ｓｌを加算することにより、元ｓを正しく復元することができる。さらに、署名検証装置は、その署名データの示す第２の元にｑを乗算した結果を用いて、署名ベクトルの一部である元ｔを正しく復元することができる。例えば、上述の元ｓｌと元ｈとの積の法をｑとする剰余に、第２の元とｑとの積を加算することにより、元ｔを正しく復元することができる。このように、本発明では、署名ベクトルである元ｓ，ｔに対して（ｍｏｄ ｑ）の演算を行うことなく、その元ｓ，ｔを署名検証装置側で正しく復元できるような署名データを生成するため、従来例のような不適切な署名検証エラーの発生を確実に防ぐことができる。つまり、元ｓの各要素における最大値と最小値の差がｑを超えるような場合であっても、元ｓの情報を欠落させてしまうことなく、その元ｓに基づいて正しい署名検証を署名検証装置に行わせることができる。

また、前記署名生成装置は、さらに、前記メッセージデータに対してハッシュ関数を適用することにより、前記環Ｒの元ｍ１および元ｍ２を生成するハッシュ値生成手段を備え、前記署名データ生成手段は、前記元ｓと前記元ｍ１との差を前記第１の元として生成することを特徴としてもよい。

これにより、第１の元が元ｓと元ｍ１との差であるため、署名データおよびメッセージデータを取得した署名検証装置は、その署名データにより示される第１の元を用いて、署名ベクトルの一部である元ｓを正しく復元することができる。即ち、署名検証装置は、メッセージデータに対してハッシュ関数を適用することにより元ｍ１を生成し、第１の元にその元ｍ１を加算することにより、元ｓを正しく復元することができる。また、第１の元は、元ｓと元ｍ１との差であるため、上述のように第１の元が元ｓｌ，ｓｈからなる場合と比べて、第１の元の情報量、つまり署名データの情報量を削減することができる。さらに、署名検証装置は、その元ｓと元ｈとの積の法をｑとする剰余に、第２の元とｑとの積を加算することにより、署名ベクトルの一部である元ｔを正しく復元することができる。

また、前記署名ベクトル生成手段は、前記元ｍ１と前記元ｓとのそれぞれのｉ番目の要素（ｉは１からＮの何れかの整数）が同じ値となるように、前記元ｓを算出することを特徴としてもよい。例えば、前記署名ベクトル生成手段は、ノルムが０である前記環Ｒの元の加算または減算を行うことにより、前記元ｓを算出する。

これにより、ノルムが０である元の加算または減算を行って、元ｓのｉ番目の要素が元ｍ１のｉ番目の要素と等しくなるように、元ｓが算出されるため、第１の元のｉ番目の要素が０となって他の各要素の値も０に近づけることができ、第１の元の情報量、つまり署名データの情報量をさらに削減することができる。また、ノルムが０である元の加算または減算により、元ｓのｉ番目の要素の値の調整を行っているため、一度算出した元ｓのノルムを変化させることなく上述のような調整を行うことができ、その調整を行う上で、署名ベクトルと、元ｍ１，ｍ２からなるハッシュ値ベクトルとの距離を一定に保つことができる。

また、本発明に係る署名検証装置は、メッセージデータに対する署名データを、署名方式に従って検証する署名検証装置であって、前記署名方式は、加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、前記署名検証装置は、前記メッセージデータに対して前記秘密鍵を用いて算出された、前記環Ｒの元ｓ，ｔからなる署名ベクトルのうち、前記元ｓを、前記署名データの示す前記環Ｒの第１の元を用いて復元するとともに、前記元ｔを、前記署名データの示す前記環Ｒの第２の元にｑを乗算した結果を用いて復元する署名ベクトル生成手段と、前記署名ベクトルを検証する検証手段とを備えることを特徴とする。例えば、前記第１の元は、前記元ｓをｑで割ったときの商である前記環Ｒの元ｓｈと、前記元ｓをｑで割ったときの余りである前記環Ｒの元ｓｌとからなり、前記第２の元は、前記元ｔをｑで割ったときの商であり、前記署名ベクトル生成手段は、前記元ｓｈにｑを乗算して前記元ｓｌを加算することにより、前記元ｓを復元し、前記元ｓｌと前記元ｈとの積の法をｑとする剰余に、前記第２の元とｑとの積を加算することにより、前記元ｔを復元することを特徴とする。

これにより、署名データは、元ｓを特定し得る第１の元と、元ｔをｑで割ったときの商である第２の元とを示すため、その署名データおよびメッセージデータを取得した署名検証装置は、その署名データにより示される第１の元を用いて、署名ベクトルの一部である元ｓを正しく復元することができる。例えば、第１の元が、元ｓをｑで割ったときの商および余りである元ｓｈ，ｓｌからなる場合には、署名検証装置は、その元ｓｈにｑを乗算して前記元ｓｌを加算することにより、元ｓを正しく復元することができる。さらに、署名検証装置は、その署名データの示す第２の元にｑを乗算した結果を用いて、署名ベクトルの一部である元ｔを正しく復元することができる。例えば、上述の元ｓｌと元ｈとの積の法をｑとする剰余に、第２の元とｑとの積を加算することにより、元ｔを正しく復元することができる。

また、前記署名検証装置は、さらに、前記メッセージデータに対してハッシュ関数を適用することにより、前記環Ｒの元ｍ１および元ｍ２を生成するハッシュ値生成手段を備え、前記第１の元は、前記元ｓと前記元ｍ１との差である前記環Ｒの元ｓｌからなり、前記第２の元は、前記元ｔをｑで割ったときの商であり、前記署名ベクトル生成手段は、前記元ｓｌに前記元ｍ１を加算することにより、前記元ｓを復元し、前記元ｓと元ｈとの積の法をｑとする剰余に、前記第２の元とｑとの積を加算することにより、前記元ｔを復元することを特徴としてもよい。

これにより、第１の元が元ｓと元ｍ１との差であるため、署名データおよびメッセージデータを取得した署名検証装置は、その署名データにより示される第１の元を用いて、署名ベクトルの一部である元ｓを正しく復元することができる。即ち、署名検証装置は、メッセージデータに対してハッシュ関数を適用することにより元ｍ１を生成し、第１の元にその元ｍ１を加算することにより、元ｓを正しく復元することができる。さらに、署名検証装置は、その元ｓと元ｈとの積の法をｑとする剰余に、第２の元とｑとの積を加算することにより、署名ベクトルの一部である元ｔを正しく復元することができる。

なお、本発明は、このような署名生成装置および署名検証装置として実現することができるだけでなく、その方法やプログラム、そのプログラムを格納する記憶媒体、集積回路としても実現することができる。

本発明の署名生成装置および署名検証装置は、不適切な署名検証エラーの発生を確実に防ぐことができるという作用効果を奏し、その価値は大きい。

（実施の形態１）
本発明の実施の形態１における改良ＮＴＲＵＳｉｇｎ署名方式１は、従来のＮＴＲＵＳｉｇｎ署名方式を改良した署名方式であって、不適切な署名検証エラーの発生を確実に防ぐことが可能なように署名を生成して検証するものである。

以下、本実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式１について詳細に説明する。

＜改良ＮＴＲＵＳｉｇｎ署名方式１＞
（１）改良ＮＴＲＵＳｉｇｎ署名方式１のパラメータ
改良ＮＴＲＵＳｉｇｎ署名方式１では、非負整数のパラメータ、Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄが使用される。これらのパラメータの定義は、従来のＮＴＲＵＳｉｇｎ署名方式と同様である。以下に、これらのパラメータの意味を説明する。

（ｉ）パラメータＮ
改良ＮＴＲＵＳｉｇｎ署名方式１は、多項式の演算により署名生成及び署名検証を行うディジタル署名方式である。改良ＮＴＲＵＳｉｇｎ署名方式１で扱う多項式の次数は、上記パラメータＮにより決まる。

改良ＮＴＲＵＳｉｇｎ署名方式１で扱う多項式は、上記パラメータＮに対し、Ｎ−１次以下の整数係数多項式であり、例えばＮ＝５のとき、Ｘ＾４＋Ｘ＾３＋１等の多項式である。ここで、「Ｘ＾ａ」はＸのａ乗を意味する。また、公開鍵ｈ、および署名ベクトルの一部である多項式ｓはいずれも、Ｎ−１次以下の多項式として表現される。また、秘密鍵は４つのＮ−１次以下の多項式対｛ｆ，ｇ，Ｆ，Ｇ｝である。すなわち、ｆ，ｇ，Ｆ，ＧはいずれもＮ−１次以下の多項式である。なお、以下では、４つの多項式からなる組（ｆ，ｇ，Ｆ，Ｇ）を、２つの対（ｆ，ｇ），（Ｆ，Ｇ）のさらなる対と捉えて、｛（ｆ，ｇ），（Ｆ，Ｇ）｝と表記する場合もある。

そして、多項式演算は、上記パラメータＮに対し、Ｘ＾Ｎ＝１という関係式を用いて、演算結果が常にＮ−１次以下の多項式になるように演算される。例えば、Ｎ＝５の場合、多項式Ｘ＾４＋Ｘ＾２＋１と多項式Ｘ＾３＋Ｘの積は、多項式と多項式の積を×、整数と多項式の積（あるいは整数と整数の積）を・とすると、Ｘ＾５＝１という関係から、
（Ｘ＾４＋Ｘ＾２＋１）×（Ｘ＾３＋Ｘ）
＝Ｘ＾７＋２・Ｘ＾５＋２・Ｘ＾３＋Ｘ
＝Ｘ＾２・１＋２・１＋２・Ｘ＾３＋Ｘ
＝２・Ｘ＾３＋Ｘ＾２＋Ｘ＋２
というように、常にＮ−１次以下の多項式になるように演算される。

なお、改良ＮＴＲＵＳｉｇｎ署名方式１においても、Ｎ−１次の多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）はベクトル（ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１））と同一視される。ここで、ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１）は多項式ａの係数であり、整数である。

（ｉｉ）パラメータｑ
改良ＮＴＲＵＳｉｇｎ署名方式１では、２以上の整数であるパラメータｑを用いる。改良ＮＴＲＵＳｉｇｎ署名方式１で出現する多項式の係数は、ｑを法とした剰余を取る。

（ｉｉｉ）パラメータｄｆ，ｄｇ
改良ＮＴＲＵＳｉｇｎ署名方式１で扱う秘密鍵の一部である多項式ｆ及び、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇの選び方は、それぞれパラメータｄｆ，ｄｇにより決まる。

まず、多項式ｆは、ｄｆ個の係数が１であり、かつ他の係数は０となるように選ばれる。すなわち、多項式ｆは、Ｎ−１次以下の多項式であり、０次（定数項）からＮ−１次まで、Ｎ個の係数があるが、このＮ個の係数のうち、ｄｆ個の係数が１であり、かつ（Ｎ−ｄｆ）個の係数が０となるように選ばれる。そして、多項式ｇは、ｄｇ個の係数が１であり、かつ他の係数は０となるように選ばれる。

（ｉｖ）パラメータＮｏｒｍｂｏｕｎｄ
改良ＮＴＲＵＳｉｇｎ署名方式１では、多項式ｓ，ｔから成る２・Ｎ次元のベクトル（署名ベクトル）とメッセージデータ（以下、単にメッセージという）のハッシュ値である２・Ｎ次元のベクトルの距離を計算し、この距離により署名が正しいか否かを判定する。Ｎｏｒｍｂｏｕｎｄは、この判定の際に使用するしきい値である。すなわち、上記距離がＮｏｒｍｂｏｕｎｄ未満であれば、署名が正しいとして受理され、Ｎｏｒｍｂｏｕｎｄ以上であれば、正しくない署名として拒否される。なお、非特許文献４には、ＮＴＲＵＳｉｇｎ署名方式のパラメータの例として、（Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄ）＝（２５１，１２８，７３，７１，３１０）の例が挙げられている。改良ＮＴＲＵＳｉｇｎ署名方式１においても、同様のパラメータ例を使用してもよい。

（２）メッセージのハッシュ値、ノルム及びベクトル間の距離
改良ＮＴＲＵＳｉｇｎ署名方式１においても、メッセージのハッシュ値に対する署名を作成する。メッセージのハッシュ値は、Ｎ次の多項式の対であり、２・Ｎ次元のベクトルと同一視される。なお、メッセージからハッシュ値を求めるハッシュ関数については、非特許文献１が詳しい。

改良ＮＴＲＵＳｉｇｎ署名方式１では、従来のＮＴＲＵＳｉｇｎ署名方式と同様、署名検証にベクトル間の距離を用い、このような距離の算出にノルム（Ｃｅｎｔｅｒｅｄノルム）を用いる。以下、ノルムおよびベクトル間の距離の定義を示す。

多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）のノルム｜｜ａ｜｜を以下のように定義する。

｜｜ａ｜｜＝ｓｑｒｔ（（ａ＿０−μ）＾２＋（ａ＿１−μ）＾２＋…＋（ａ＿（Ｎ−１）−μ）＾２）
μ＝（１／Ｎ）・（ａ＿０＋ａ＿１＋ａ＿２＋…＋ａ＿（Ｎ−１））
ここで、ｓｑｒｔ（ｘ）はｘの平方根を示す。

多項式ａ，ｂの対（ａ，ｂ）のノルム｜｜（ａ，ｂ）｜｜を以下のように定義する。

｜｜（ａ，ｂ）｜｜＝ｓｑｒｔ（｜｜ａ｜｜＾２＋｜｜ｂ｜｜＾２）
多項式ａ，ｂの対（ａ，ｂ）とｃ，ｄの対（ｃ，ｄ）との距離（ベクトル間の距離）は、｜｜（ｃ−ａ，ｄ−ｂ）｜｜で定義される。

（３）改良ＮＴＲＵＳｉｇｎ署名方式１の鍵生成
改良ＮＴＲＵＳｉｇｎ署名方式１では、ＮＴＲＵＳｉｇｎ署名方式と同様の方法で鍵生成を行う。まず、上述したように、パラメータｄｆ，ｄｇを用いてランダムに多項式ｆ，多項式ｇを生成する。そして非特許文献４に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ ｑ）
により、多項式ｈを生成する。さらに、以下の式を満たすようなノルムが小さい多項式Ｆ，Ｇを求める。

ｆ×Ｇ−ｇ×Ｆ＝ｑ
ここで、秘密鍵を｛（ｆ，ｇ），（Ｆ，Ｇ）｝、公開鍵をｈとする。秘密鍵は、署名を生成するための鍵であり、署名生成鍵とも呼ばれる。また、公開鍵は、署名を検証するための鍵であり、署名検証鍵とも呼ばれる。

また、ｘ＝ｙ（ｍｏｄ ｑ）は、多項式ｙの第ｉ次の係数を、剰余が０からｑ−１の範囲に収まるように法ｑで割ったときの剰余を、多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、多項式ｙの各係数を、０から（ｑ−１）の範囲に収まるように（ｍｏｄ ｑ）演算した多項式を、多項式ｘとする演算である。

（４）改良ＮＴＲＵＳｉｇｎ署名方式１の署名生成
改良ＮＴＲＵＳｉｇｎ署名方式１の署名生成では、署名対象であるメッセージｍの署名ｓｌ，ｓｈ，ｔｈを計算する。

まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を計算する。

この２・Ｎ次元のベクトル（ｍ１，ｍ２）と秘密鍵｛（ｆ，ｇ），（Ｆ，Ｇ）｝を用いて、以下の（式１）および（式２）を満たす多項式ａ，ｂ，Ａ，Ｂを計算する。

Ｇ×ｍ１−Ｆ×ｍ２＝Ａ＋ｑ×Ｂ ・・・（式１）
−ｇ×ｍ１＋ｆ×ｍ２＝ａ＋ｑ×ｂ ・・・（式２）
ここで、Ａ，ａの係数は〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を取ったものとする。すなわち、法ｑで割ったときの剰余が〈ｑ／２〉からｑ−１である場合は、ｑ減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。

次に以下の（式３）および（式４）より、多項式ｓ，ｔを計算する。

ｓ＝ｆ×Ｂ＋Ｆ×ｂ ・・・（式３）
ｔ＝ｇ×Ｂ＋Ｇ×ｂ ・・・（式４）
ここで、本実施の形態では、多項式ｓ，ｔに対して、法ｑの剰余を取ることなく、ｓ＝ｓｌ＋ｓｈ×ｑおよびｔ＝ｔｌ＋ｔｈ×ｑを満たす多項式ｓｌ，ｓｈ，ｔｈを算出する。なお、多項式ｓｌ，ｔｌの各係数（各要素）を、ｑ以下の非負整数とする。即ち、多項式ｓｌ，ｓｈは多項式ｓをｑで割ったときの余り及び商となっており、多項式ｔｌ,ｔｈは多項式ｔをｑで割ったときの余り及び商となっている。そして、本実施の形態では、多項式ｓｌ，ｓｈ，ｔｈを署名として扱う。

（５）改良ＮＴＲＵＳｉｇｎ署名方式１の署名検証
まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）を計算する。そして、公開鍵ｈを用いて、以下の（式６）より、多項式ｔｌを計算する。

ｔｌ＝ｓｌ×ｈ （ｍｏｄ ｑ） ・・・（式６）
さらに、ｓ＝ｓｌ＋ｓｈ×ｑおよびｔ＝ｔｌ＋ｔｈ×ｑを用いて、多項式ｓ，ｔを算出する。つまり、署名である多項式ｓｌ，ｓｈ，ｔｈと公開鍵ｈとを用いて、多項式ｓ，ｔが算出される。そして、２・Ｎ次元ベクトル（ｓ，ｔ）と（ｍ１，ｍ２）の距離を求め、その距離がＮｏｒｍｂｏｕｎｄ未満であるかをチェックする。Ｎｏｒｍｂｏｕｎｄ未満であれば、上記署名が正しいと判定してその署名を受理する。Ｎｏｒｍｂｏｕｎｄ以上であれば、上記署名が不正と判定してその署名を拒否する。

図３は、本実施の形態におけるディジタル署名システム１００の構成を示すブロック図である。

このディジタル署名システム１００は、上述の改良ＮＴＲＵＳｉｇｎ署名方式１を用いて署名を生成して検証するものであって、署名生成装置１１０と、署名検証装置１２０と、通信路１３０とから構成される。

署名生成装置１１０は、改良ＮＴＲＵＳｉｇｎ署名方式１により、入力されたメッセージｍに対する署名データＳ（多項式ｓｌ，ｓｈ，ｔｈを示すデータ）などを含む署名データセットＳＳを生成し、その署名データセットＳＳを署名検証装置１２０へ通信路１３０を介して送信する。また、このような署名生成装置１１０は、送信部１１１と、秘密鍵格納部１１２と、公開鍵証明書格納部１１３と、署名生成部１１４と、署名データセット生成部１１５とを備える。

署名検証装置１２０は、通信路１３０を介して署名生成装置１１０から、署名データセットＳＳを受信し、改良ＮＴＲＵＳｉｇｎ署名方式１により、その署名データセットＳＳに含まれる署名データＳを検証する。また、このような署名検証装置１２０は、受信部１２１と、ＣＡ公開鍵格納部１２２と、署名データセット格納部１２３と、署名検証部１２４とを備える。

以下、本実施の形態における署名生成装置１１０について詳細に説明する。

署名生成装置１１０の送信部１１１は、署名データセットＳＳを、通信路１３０を介して署名検証装置１２０へ送信する。

秘密鍵格納部１１２は、メッセージｍに対する多項式ｓを生成するための秘密鍵ＫＳを格納している。秘密鍵ＫＳは予め与えられているものとする。

公開鍵証明書格納部１１３は、上述の多項式ｈにより示される公開鍵ＫＰ（公開鍵ｈ）の公開鍵証明書ＣＰを格納する。公開鍵証明書ＣＰは、公開鍵ＫＰと、認証局ＣＡによる公開鍵ＫＰの署名データＳＰとからなる。この署名データＳＰも、改良ＮＴＲＵＳｉｇｎ署名方式１を使用して生成されている。また、公開鍵証明書ＣＰは予め与えられているものとする。なお、公開鍵証明書ＣＰは、公開鍵ＫＰと署名データＳＰ以外の他のデータを含んでいてもよい。例えば、ユーザの識別子や公開鍵証明書ＣＰの期限などを含んでもよい。

署名生成部１１４は、秘密鍵格納部１１２に格納されている秘密鍵ＫＳを用いて、メッセージｍに対する多項式ｓ，ｔを生成し、さらに、その多項式ｓ，ｔを復元して検証するための署名データＳ（多項式ｓｌ，ｓｈ，ｔｈ）を生成する。

図４は、本実施の形態における署名生成部１１４の構成を示すブロック図である。

署名生成部１１４は、ハッシュ値生成部１１４１と、署名ベクトル生成部１１４２と、署名データ生成部１１４３とを備える。

ハッシュ値生成部１１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を算出する。

署名ベクトル生成部１１４２は、秘密鍵ＫＳとハッシュ値Ｈを用いて、上記（式１）〜（式４）により、多項式ｓ，ｔを生成する。つまり、署名ベクトル生成部１１４２は、秘密鍵行列｛（ｆ，ｇ），（Ｆ，Ｇ）｝により張られる２・Ｎ次元格子上において、メッセージｍに対するハッシュ値Ｈ（ｍ）＝（ｍ１，ｍ２）の最近接格子点Ｐを示す署名ベクトル（ｓ，ｔ）を算出する。

署名データ生成部１１４３は、署名ベクトル生成部１１４２で生成された多項式ｓ，ｔを用いて、ｓ＝ｓｌ＋ｓｈ×ｑおよびｔ＝ｔｌ＋ｔｈ×ｑを満たす、多項式ｓｌ，ｓｈ，ｔｈを算出し、その多項式ｓｌ，ｓｈ，ｔｈを示す署名データＳを生成する。

図５は、署名生成部１１４の動作を示すフローチャートである。

まず、署名生成部１１４のハッシュ値生成部１１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）を算出する（ステップＳ１００）。

次に、署名生成部１１４の署名ベクトル生成部１１４２は、上記（式１）および（式２）を満たす多項式ａ，ｂ，Ａ，Ｂを算出する（ステップＳ１０２）。さらに、署名ベクトル生成部１１４２は、上記（式３）および（式４）により、多項式ｓ，ｔを算出する（ステップＳ１０４）。

そして、署名生成部１１４の署名データ生成部１１４３は、多項式ｓ，ｔを用いて、ｓ＝ｓｌ＋ｓｈ×ｑおよびｔ＝ｔｌ＋ｔｈ×ｑを満たす、多項式ｓｌ，ｓｈ，ｔｈを算出し、その多項式ｓｌ，ｓｈ，ｔｈを示す署名データＳを生成する（ステップＳ１０６）。

図６は、署名生成装置１１０の全体的な動作を示すフローチャートである。

署名生成装置１１０の署名生成部１１４は、秘密鍵格納部１１２に格納されている秘密鍵ＫＳを用いて、メッセージｍに対する多項式ｓ，ｔを生成するとともに、その多項式ｓ，ｔに基づいて署名データＳ（多項式ｓｌ，ｓｈ，ｔｈを示すデータ）を生成する（ステップＳ１２０）。

次に、署名生成装置１１０の署名データセット生成部１１５は、メッセージｍと、署名データＳと、公開鍵証明書格納部１１３に格納されている公開鍵証明書ＣＰとからなる署名データセットＳＳを生成する（ステップＳ１２２）。

そして、署名生成装置１１０の送信部１１１は、通信路１３０を介して署名データセットＳＳを署名検証装置１２０へ送信する（ステップＳ１２４）。

以下、本実施の形態における署名検証装置１２０について詳細に説明する。

署名検証装置１２０の受信部１２１は、署名生成装置１１０から送信された署名データセットＳＳを、通信路１３０を介して受信する。

ＣＡ公開鍵格納部１２２は、署名データセットＳＳに含まれる公開鍵証明書ＣＰを検証するための認証局ＣＡの公開鍵ＫＣＰを格納する。

署名データセット格納部１２３は、受信部１２１で受信された署名データセットＳＳを格納する。

署名検証部１２４は、署名データセットＳＳに含まれる署名データＳと、公開鍵証明書ＣＰに含まれる署名データＳＰとを検証する。

図７は、本実施の形態における署名検証部１２４の構成を示すブロック図である。

署名検証部１２４は、ハッシュ値生成部１２４１と、署名ベクトル生成部１２４３と、距離判定部１２４４とを備える。

ハッシュ値生成部１２４１は、署名対象データであるメッセージｍおよび公開鍵ＫＰのそれぞれのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する。

署名ベクトル生成部１２４３は、署名データＳおよび署名データＳＰのそれぞれに対して、多項式ｓ，ｔを算出する。即ち、署名ベクトル生成部１２４３は、署名データによって示される多項式ｓｌ，ｓｈをｓ＝ｓｌ＋ｓｈ×ｑに代入することで、多項式ｓを算出する。さらに、署名ベクトル生成部１２４３は、署名データによって示される多項式ｓｌと、多項式ｈ（公開鍵ＫＰまたは公開鍵ＫＣＰにより示される多項式）とを、上記（式６）に代入することにより多項式ｔｌを算出し、その多項式ｔｌと、署名データによって示される多項式ｔｈとを、ｔ＝ｔｌ＋ｔｈ×ｑに代入することにより、多項式ｔを算出する。

これにより、署名ベクトル生成部１２４３は、署名データＳおよび署名データＳＰのそれぞれに対して、２・Ｎ次元ベクトル（ｓ，ｔ）を署名ベクトルＳＶとして生成する。

距離判定部１２４４は、メッセージｍおよび署名データＳと、公開鍵ＫＰおよび署名データＳＰとのそれぞれに対して、ハッシュ値Ｈと署名ベクトルＳＶの距離を計算し、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する。即ち、メッセージｍおよび署名データＳに対する、ハッシュ値と署名ベクトルＳＶの距離がＮｏｒｍｂｏｕｎｄ未満であれば、距離判定部１２４４は、署名データＳが正しいと判定してその署名データＳを受理する。一方、Ｎｏｒｍｂｏｕｎｄ以上であれば、距離判定部１２４４は、署名データＳが不正と判定してその署名データＳを拒否する。また、公開鍵ＫＰおよび署名データＳＰに対する、ハッシュ値と署名ベクトルＳＶの距離がＮｏｒｍｂｏｕｎｄ未満であれば、距離判定部１２４４は、署名データＳＰが正しいと判定してその署名データＳＰを受理する。一方、Ｎｏｒｍｂｏｕｎｄ以上であれば、距離判定部１２４４は、署名データＳＰが不正と判定してその署名データＳＰを拒否する。

図８は、署名検証部１２４の動作を示すフローチャートである。

署名検証部１２４は、公開鍵ＫＰを用い、メッセージｍおよび署名データＳに対して図８に示す動作を行うことにより、その署名データＳを検証する。なお、署名検証部１２４は、署名データＳの検証を行う前に、公開鍵ＫＣＰを用い、公開鍵ＫＰおよび署名データＳＰに対して図８に示す動作を行うことにより、その署名データＳＰを検証している。

以下、署名検証部１２４が署名データＳを検証する具体的な動作について、図８を参照して説明する。

まず、署名検証部１２４のハッシュ値生成部１２４１は、署名データＳに対応するメッセージｍのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する（ステップＳ１４０）。

次に、署名ベクトル生成部１２４３は、署名データＳにより示される多項式ｓｌと、公開鍵ＫＰにより示される多項式ｈとを上記（式６）に代入することにより、多項式ｔｌを算出する（ステップＳ１４２）。

さらに、署名ベクトル生成部１２４３は、署名データＳにより示される多項式ｓｌ，ｓｈ，ｔｈと、ステップＳ１４２で算出された多項式ｔｌとを、ｓ＝ｓｌ＋ｓｈ×ｑおよびｔ＝ｔｌ＋ｔｈ×ｑに代入することにより、多項式ｓ，ｔを算出する（ステップＳ１４４）。このとき、署名ベクトル生成部１２４３は、署名データＳに対して、２・Ｎ次元ベクトル（ｓ，ｔ）を署名ベクトルＳＶとして生成する。

距離判定部１２４４は、ステップＳ１４０で算出されたハッシュ値Ｈ＝（ｍ１，ｍ２）と、ステップＳ１４４で生成された署名ベクトルＳＶとの距離を算出する（ステップＳ１４６）。そして、距離判定部１２４４は、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する（ステップＳ１４８）。距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満であると判定したときには（ステップＳ１４８のＹ）、署名データＳが正しいと判断してその署名データＳを受理する（ステップＳ１５０）。一方、距離判定部１２４４は、Ｎｏｒｍｂｏｕｎｄ未満でないと判定したときには（ステップＳ１４８のＮ）、署名データＳが不正であると判断してその署名データＳを拒否する（ステップＳ１５２）。

図９は、署名検証装置１２０の全体的な動作を示すフローチャートである。

まず、署名検証装置１２０の受信部１２１は、署名生成装置１１０から通信路１３０を介して署名データセットＳＳを受信し、その署名データセットＳＳを署名データセット格納部１２３に格納する（ステップＳ１７０）。

署名検証部１２４は、署名データセットＳＳの中の公開鍵証明書ＣＰに含まれる公開鍵ＫＰとその署名データＳＰに対し、署名データＳＰが公開鍵ＫＰの正しい署名であるか否かを、ＣＡ公開鍵格納部１２２に格納されている認証局ＣＡの公開鍵ＫＣＰを用いて検証する。つまり、署名検証部１２４は、署名データＳＰが正しい署名であるか否かを判別する（ステップＳ１７２）。ここで、署名検証部１２４は、正しい署名でないと判別したときには（ステップＳ１７２のＮ）、その署名データＳＰを拒否する（ステップＳ１７４）。

一方、署名検証部１２４は、ステップＳ１７２で署名データＳＰが正しい署名であると判別したときには（ステップＳ１７２のＹ）、その署名データＳＰを受理する。さらに、署名検証部１２４は、署名データセットＳＳの中のメッセージｍとその署名データＳに対し、署名データＳがメッセージｍの正しい署名であるか否かを、公開鍵ＫＰを用いて検証する。つまり、署名検証部１２４は、署名データＳが正しい署名であるか否かを判別する（ステップＳ１７６）。

ここで、署名検証部１２４は、正しい署名でないと判別したときには（ステップＳ１７６のＮ）、その署名データＳを拒否し（ステップＳ１７４）、正しい署名であると判別したときには（ステップＳ１７６のＹ）、その署名データＳを受理する（ステップＳ１７８）。即ち、ステップＳ１７８では、署名検証部１２４は、署名データセットＳＳが正当な署名を受けたデータであると認識する。

このように本実施の形態では、署名生成装置１１０において、公開鍵を用いたときに、署名ベクトル（ｓ，ｔ）を復元できるような多項式ｓｌ，ｓｈ，ｔｈを署名データに含めている。したがって、そのような署名データおよびメッセージを取得した署名検証装置１２０は、その署名データから署名ベクトル（ｓ，ｔ）を正しく復元することができ、その署名ベクトル（ｓ，ｔ）を用いて署名検証を行うことができる。例えば、署名検証装置１２０は、署名データに含まれる多項式ｓｈにｑを乗算して多項式ｓｌを加算することにより、署名ベクトルの一部である多項式ｓを正しく復元することができる。さらに、署名検証装置１２０は、署名データに含まれる多項式ｓｌと公開鍵（多項式ｈ）との積の法をｑとする剰余に、多項式ｔｈとｑとの積を加算することにより、署名ベクトルの一部である多項式ｔを正しく復元することができる。このように、本発明では、署名ベクトル（ｓ，ｔ）に対して（ｍｏｄ ｑ）の演算を行うことなく、その署名ベクトル（ｓ，ｔ）を署名検証装置１２０側で正しく復元できるような署名データを生成するため、（ｍｏｄ ｑ）の演算による情報の欠落を防ぎ、従来例のような不適切な署名検証エラーの発生を確実に防ぐことができる。したがって、署名ベクトル（ｓ，ｔ）の各要素における最大値と最小値との差がｑを超える場合においても、署名検証時に署名ベクトル（ｓ，ｔ）を正しく復元することができる。

（実施の形態２）
本発明の実施の形態２における改良ＮＴＲＵＳｉｇｎ署名方式２は、従来のＮＴＲＵＳｉｇｎ署名方式を改良した署名方式であって、実施の形態１と同様、不適切な署名検証エラーの発生を確実に防ぐことが可能なように署名を生成して検証するものである。さらに、本実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式２では、実施の形態１と比べて、署名データの情報量を抑えることができる。

以下、本実施の形態における改良ＮＴＲＵＳｉｇｎ署名方式２について詳細に説明する。

＜改良ＮＴＲＵＳｉｇｎ署名方式２＞
（１）改良ＮＴＲＵＳｉｇｎ署名方式２のパラメータ
改良ＮＴＲＵＳｉｇｎ署名方式２では、非負整数のパラメータ、Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄが使用される。これらのパラメータの定義は、従来のＮＴＲＵＳｉｇｎ署名方式と同様である。以下に、これらのパラメータの意味を説明する。

（ｉ）パラメータＮ
改良ＮＴＲＵＳｉｇｎ署名方式２は、多項式の演算により署名生成及び署名検証を行うディジタル署名方式である。改良ＮＴＲＵＳｉｇｎ署名方式２で扱う多項式の次数は、上記パラメータＮにより決まる。

改良ＮＴＲＵＳｉｇｎ署名方式２で扱う多項式は、上記パラメータＮに対し、Ｎ−１次以下の整数係数多項式であり、例えばＮ＝５のとき、Ｘ＾４＋Ｘ＾３＋１等の多項式である。ここで、「Ｘ＾ａ」はＸのａ乗を意味する。また、公開鍵ｈ、および署名ベクトルの一部である多項式ｓはいずれも、Ｎ−１次以下の多項式として表現される。また、秘密鍵は４つのＮ−１次以下の多項式対｛ｆ，ｇ，Ｆ，Ｇ｝である。すなわち、ｆ，ｇ，Ｆ，ＧはいずれもＮ−１次以下の多項式である。なお、以下では、４つの多項式からなる組（ｆ，ｇ，Ｆ，Ｇ）を、２つの対（ｆ，ｇ），（Ｆ，Ｇ）のさらなる対と捉えて、｛（ｆ，ｇ），（Ｆ，Ｇ）｝と表記する場合もある。

そして、多項式演算は、上記パラメータＮに対し、Ｘ＾Ｎ＝１という関係式を用いて、演算結果が常にＮ−１次以下の多項式になるように演算される。例えば、Ｎ＝５の場合、多項式Ｘ＾４＋Ｘ＾２＋１と多項式Ｘ＾３＋Ｘの積は、多項式と多項式の積を×、整数と多項式の積（あるいは整数と整数の積）を・とすると、Ｘ＾５＝１という関係から、
（Ｘ＾４＋Ｘ＾２＋１）×（Ｘ＾３＋Ｘ）
＝Ｘ＾７＋２・Ｘ＾５＋２・Ｘ＾３＋Ｘ
＝Ｘ＾２・１＋２・１＋２・Ｘ＾３＋Ｘ
＝２・Ｘ＾３＋Ｘ＾２＋Ｘ＋２
というように、常にＮ−１次以下の多項式になるように演算される。

なお、改良ＮＴＲＵＳｉｇｎ署名方式２においても、Ｎ−１次の多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）はベクトル（ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１））と同一視される。ここで、ａ＿０，ａ＿１，ａ＿２，…，ａ＿（Ｎ−１）は多項式ａの係数であり、整数である。

（ｉｉ）パラメータｑ
改良ＮＴＲＵＳｉｇｎ署名方式２では、２以上の整数であるパラメータｑを用いる。改良ＮＴＲＵＳｉｇｎ署名方式２で出現する多項式の係数は、ｑを法とした剰余を取る。

（ｉｉｉ）パラメータｄｆ，ｄｇ
改良ＮＴＲＵＳｉｇｎ署名方式２で扱う秘密鍵の一部である多項式ｆ及び、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇの選び方は、それぞれパラメータｄｆ，ｄｇにより決まる。

まず、多項式ｆは、ｄｆ個の係数が１であり、かつ他の係数は０となるように選ばれる。すなわち、多項式ｆは、Ｎ−１次以下の多項式であり、０次（定数項）からＮ−１次まで、Ｎ個の係数があるが、このＮ個の係数のうち、ｄｆ個の係数が１であり、かつ（Ｎ−ｄｆ）個の係数が０となるように選ばれる。そして、多項式ｇは、ｄｇ個の係数が１であり、かつ他の係数は０となるように選ばれる。

（ｉｖ）パラメータＮｏｒｍｂｏｕｎｄ
改良ＮＴＲＵＳｉｇｎ署名方式２では、多項式ｓ，ｔから成る２・Ｎ次元のベクトル（署名ベクトル）とメッセージデータ（以下、単にメッセージという）のハッシュ値である２・Ｎ次元のベクトルの距離を計算し、この距離により署名が正しいか否かを判定する。Ｎｏｒｍｂｏｕｎｄは、この判定の際に使用するしきい値である。すなわち、上記距離がＮｏｒｍｂｏｕｎｄ未満であれば、署名が正しいとして受理され、Ｎｏｒｍｂｏｕｎｄ以上であれば、正しくない署名として拒否される。なお、非特許文献４には、ＮＴＲＵＳｉｇｎ署名方式のパラメータの例として、（Ｎ，ｑ，ｄｆ，ｄｇ，Ｎｏｒｍｂｏｕｎｄ）＝（２５１，１２８，７３，７１，３１０）の例が挙げられている。改良ＮＴＲＵＳｉｇｎ署名方式２においても、同様のパラメータ例を使用してもよい。

（２）メッセージのハッシュ値、ノルム及びベクトル間の距離
改良ＮＴＲＵＳｉｇｎ署名方式２においても、メッセージのハッシュ値に対する署名を作成する。メッセージのハッシュ値は、Ｎ次の多項式の対であり、２・Ｎ次元のベクトルと同一視される。なお、メッセージからハッシュ値を求めるハッシュ関数については、非特許文献１が詳しい。

改良ＮＴＲＵＳｉｇｎ署名方式２では、従来のＮＴＲＵＳｉｇｎ署名方式と同様、署名検証にベクトル間の距離を用い、このような距離の算出にノルム（Ｃｅｎｔｅｒｅｄノルム）を用いる。以下、ノルムおよびベクトル間の距離の定義を示す。

多項式ａ＝ａ＿０＋ａ＿１・Ｘ＋ａ＿２・Ｘ＾２＋…＋ａ＿（Ｎ−１）・Ｘ＾（Ｎ−１）のノルム｜｜ａ｜｜を以下のように定義する。

｜｜ａ｜｜＝ｓｑｒｔ（（ａ＿０−μ）＾２＋（ａ＿１−μ）＾２＋…＋（ａ＿（Ｎ−１）−μ）＾２）
μ＝（１／Ｎ）・（ａ＿０＋ａ＿１＋ａ＿２＋…＋ａ＿（Ｎ−１））
ここで、ｓｑｒｔ（ｘ）はｘの平方根を示す。

多項式ａ，ｂの対（ａ，ｂ）のノルム｜｜（ａ，ｂ）｜｜を以下のように定義する。

｜｜（ａ，ｂ）｜｜＝ｓｑｒｔ（｜｜ａ｜｜＾２＋｜｜ｂ｜｜＾２）
多項式ａ，ｂの対（ａ，ｂ）とｃ，ｄの対（ｃ，ｄ）との距離（ベクトル間の距離）は、｜｜（ｃ−ａ，ｄ−ｂ）｜｜で定義される。

（３）改良ＮＴＲＵＳｉｇｎ署名方式２の鍵生成
改良ＮＴＲＵＳｉｇｎ署名方式２では、ＮＴＲＵＳｉｇｎ署名方式と同様の方法で鍵生成を行う。まず、上述したように、パラメータｄｆ，ｄｇを用いてランダムに多項式ｆ，多項式ｇを生成する。そして非特許文献４に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ ｑ）
により、多項式ｈを生成する。さらに、以下の式を満たすようなノルムが小さい多項式Ｆ，Ｇを求める。

ｆ×Ｇ−ｇ×Ｆ＝ｑ
ここで、秘密鍵を｛（ｆ，ｇ），（Ｆ，Ｇ）｝、公開鍵をｈとする。秘密鍵は、署名を生成するための鍵であり、署名生成鍵とも呼ばれる。また、公開鍵は、署名を検証するための鍵であり、署名検証鍵とも呼ばれる。

また、ｘ＝ｙ（ｍｏｄ ｑ）は、多項式ｙの第ｉ次の係数を、剰余が０からｑ−１の範囲に収まるように法ｑで割ったときの剰余を、多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、多項式ｙの各係数を、０から（ｑ−１）の範囲に収まるように（ｍｏｄ ｑ）演算した多項式を、多項式ｘとする演算である。

（４）改良ＮＴＲＵＳｉｇｎ署名方式２の署名生成
改良ＮＴＲＵＳｉｇｎ署名方式２の署名生成では、署名対象であるメッセージｍの署名ｓｌ’，ｔｈ’を計算する。

まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を計算する。

この２・Ｎ次元のベクトル（ｍ１，ｍ２）と秘密鍵｛（ｆ，ｇ），（Ｆ，Ｇ）｝を用いて、以下の（式１１）および（式１２）を満たす多項式ａ，ｂ，Ａ，Ｂを計算する。

Ｇ×ｍ１−Ｆ×ｍ２＝Ａ＋ｑ×Ｂ ・・・（式１１）
−ｇ×ｍ１＋ｆ×ｍ２＝ａ＋ｑ×ｂ ・・・（式１２）
ここで、Ａ，ａの係数は〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を取ったものとする。すなわち、法ｑで割ったときの剰余が〈ｑ／２〉からｑ−１である場合は、ｑ減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。

次に以下の（式１３）および（式１４）より、多項式ｓ，ｔを計算する。

ｓ＝ｆ×Ｂ＋Ｆ×ｂ ・・・（式１３）
ｔ＝ｇ×Ｂ＋Ｇ×ｂ ・・・（式１４）
ここで、本実施の形態では、多項式ｓ，ｔに対して、法ｑの剰余を取ることなく、この多項式ｓ，ｔに基づく多項式ｓ’，ｔ’を算出する。

即ち、多項式ｓをｓ＝ｓ＿０＋ｓ＿１・Ｘ＋ｓ＿２・Ｘ＾２＋…＋ｓ＿（Ｎ−１）・Ｘ＾（Ｎ−１）とし、多項式ｔをｔ＝ｔ＿０＋ｔ＿１・Ｘ＋ｔ＿２・Ｘ＾２＋…＋ｔ＿（Ｎ−１）・Ｘ＾（Ｎ−１）とし、多項式ｖ０をすべての係数が１の多項式とする。この場合、以下の（式１５）および（式１６）により、多項式ｓ’および多項式ｔ’を算出する。

ｓ’＝ｓ−（ｓ＿０−ｍ１＿０）×ｖ０
＝ｍ１＿０＋（ｓ＿１−ｓ＿０＋ｍ１＿０）・Ｘ
＋（ｓ＿２−ｓ＿０＋ｍ１＿０）・Ｘ＾２
＋…
＋（ｓ＿（Ｎ−１）−ｓ＿０＋ｍ１＿０）・Ｘ＾（Ｎ−１） ・・・（式１５）
ｔ’＝ｔ−（ｈｓ ×（ｓ＿０−ｍ１＿０） ｍｏｄ ｑ）×ｖ０
＝（ｔ＿０−（ｈｓ×（ｓ＿０−ｍ１＿０） ｍｏｄ ｑ））
＋（ｔ＿１−（ｈｓ×（ｓ＿０−ｍ１＿０） ｍｏｄ ｑ））・Ｘ
＋（ｔ＿２−（ｈｓ×（ｓ＿０−ｍ１＿０） ｍｏｄ ｑ））・Ｘ＾２
＋…
＋（ｔ＿（Ｎ−１）−（ｈｓ×（ｓ＿０−ｍ１＿０） ｍｏｄ ｑ））・Ｘ＾（Ｎ−１） ・・・（式１６）
なお、上記（式１５）および（式１６）において、ｍ１＿０は多項式ｍ１の０次の項（１番目の項）の係数であり、ｈｓは公開鍵である多項式ｈのすべての係数の和である。

さらに、ｓ’−ｍ１＝ｓｌ’およびｔ’＝ｔｌ’＋ｔｈ’×ｑを満たす多項式ｓｌ’，ｔｈ’を算出する。ここで、多項式ｔｌ’の全ての係数（要素）はｑ未満の非負整数である。そして、本実施の形態では、多項式ｓｌ’，ｔｈ’を署名として扱う。

つまり、本実施の形態では、多項式ｓ’と多項式ｍ１との距離が近いため、署名となる多項式ｓｌ’の情報量を削減することができる。

また、本実施の形態では、ノルムが０であるベクトルの加算または減算を行って、多項式ｓ’の１番目の要素が多項式ｍ１の１番目の要素と等しくなるように、多項式ｓ’が算出される。したがって、署名となる多項式ｓｌ’の１番目の要素が０となって他の各要素の値も０に近づけることができ、多項式ｓｌ’の情報量、つまり署名データの情報量をさらに削減することができる。また、ノルムが０であるベクトルの加算または減算により、多項式ｓ’の１番目の要素の値の調整を行っているため、一度算出した多項式ｓのノルムを変化させることなく上述のような調整を行うことができ、その調整を行う上で、（ｓ，ｔ）と（ｍ１，ｍ２）の距離と、（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離とを一定に保つことができる。

（５）改良ＮＴＲＵＳｉｇｎ署名方式２の署名検証
まず、メッセージｍに対するハッシュ値である２・Ｎ次元のベクトル（ｍ１，ｍ２）を計算する。さらに、ｓ’＝ｓｌ’＋ｍ１により多項式ｓ’を算出する。そして、公開鍵ｈを用いて、以下の（式１７）により、多項式ｔｌ’を算出する。

ｔｌ’＝ｓ’×ｈ （ｍｏｄ ｑ） ・・・（式１７）
また、署名である多項式ｔｈ’と、（式１７）により算出されたｔｌ’とを、ｔ’＝ｔｌ’＋ｔｈ’×ｑに代入することにより、多項式ｔ’を算出する。

そして、２・Ｎ次元ベクトル（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離を求め、その距離がＮｏｒｍｂｏｕｎｄ未満であるかをチェックする。Ｎｏｒｍｂｏｕｎｄ未満であれば、上記署名が正しいと判定してその署名を受理する。Ｎｏｒｍｂｏｕｎｄ以上であれば、上記署名が不正と判定してその署名を拒否する。

（６）改良ＮＴＲＵＳｉｇｎ署名方式２の動作検証
まず、（ｓ，ｔ）と（ｍ１，ｍ２）の距離と、（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離とが等しいことを示す。（式１５）により、ｓ−ｓ’＝（ｓ＿０−ｍ１＿０）×ｖ０の関係が成立し、（式１６）により、ｔ−ｔ’＝（ｈｓ×（ｓ＿０−ｍ１＿０） ｍｏｄ ｑ）×ｖ０の関係が成立する。したがって、｜｜ｓ−ｓ’｜｜＝（ｓ＿０−ｍ１＿０）・｜｜ｖ０｜｜および｜｜ｔ−ｔ’｜｜＝（ｈｓ×（ｓ＿０−ｍ１＿０） ｍｏｄ ｑ）・｜｜ｖ０｜｜の関係が成立する。ここで、｜｜ｖ０｜｜＝０であるため、｜｜ｓ−ｓ’｜｜＝０および｜｜ｔ−ｔ’｜｜＝０となり、｜｜ｍ１−ｓ｜｜＝｜｜ｍ１−ｓ’｜｜および｜｜ｍ２−ｔ｜｜＝｜｜ｍ２−ｔ’｜｜となる。したがって、（ｓ，ｔ）と（ｍ１，ｍ２）の距離と、（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離とは等しい。

次に、ｓ’×ｈ （ｍｏｄ ｑ）がｔｌ’となることを示す。ｓ’＝ｓ−（ｓ＿０−ｍ１＿０）×ｖ０より、以下の関係が成立する。

ｓ’×ｈ＝ｓ×ｈ−（ｓ＿０−ｍ１＿０）×ｖ０×ｈ
ここで、多項式ｖ０の係数はすべて１であるため、ｖ０×ｈ＝ｈｓ＋ｈｓ・Ｘ＋ｈｓ・Ｘ＾２＋…＋ｈｓ・Ｘ＾（Ｎ−１） ｍｏｄ Ｘ＾Ｎ−１となる。

したがって、以下の関係が成立する。

ｓ’×ｈ＝ｓ×ｈ−（ｓ＿０−ｍ１＿０）×（ｈｓ，ｈｓ，…，ｈｓ）
＝ｔ−（ｈｓ×（ｓ＿０−ｍ１＿０））×ｖ０ ｍｏｄ ｑ
＝ｔ’ ｍｏｄ ｑ＝ｔｌ’
その結果、上記（式１６）により多項式ｔ’を算出して、ｔ’＝ｔｌ’＋ｔｈ’×ｑを満たす多項式ｔｈ’を多項式ｓｌ’と合わせて署名としておけば、上記（式１７）、ｓ’＝ｓｌ’＋ｍ１およびｔ’＝ｔｌ’＋ｔｈ’×ｑから、２・Ｎ次元ベクトル（ｓ’、ｔ’）を算出することができる。そして、（ｓ，ｔ）と（ｍ１，ｍ２）の距離と、（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離とが等しいため、（ｓ’，ｔ’）と（ｍ１，ｍ２）の距離に基づいて署名を正しく検証することができる。

図１０は、本実施の形態におけるディジタル署名システム２００の構成を示すブロック図である。

このディジタル署名システム２００は、上述の改良ＮＴＲＵＳｉｇｎ署名方式２を用いて署名を生成して検証するものであって、署名生成装置２１０と、署名検証装置２２０と、通信路２３０とから構成される。

署名生成装置２１０は、改良ＮＴＲＵＳｉｇｎ署名方式２により、入力されたメッセージｍに対する署名データＳ（多項式ｓｌ’，ｔｈ’を示すデータ）などを含む署名データセットＳＳを生成し、その署名データセットＳＳを署名検証装置２２０へ通信路２３０を介して送信する。また、このような署名生成装置２１０は、送信部２１１と、秘密鍵格納部２１２と、公開鍵証明書格納部２１３と、署名生成部２１４と、署名データセット生成部２１５とを備える。

署名検証装置２２０は、通信路２３０を介して署名生成装置２１０から、署名データセットＳＳを受信し、改良ＮＴＲＵＳｉｇｎ署名方式２により、その署名データセットＳＳに含まれる署名データＳを検証する。また、このような署名検証装置２２０は、受信部２２１と、ＣＡ公開鍵格納部２２２と、署名データセット格納部２２３と、署名検証部２２４とを備える。

以下、本実施の形態における署名生成装置２１０について詳細に説明する。

署名生成装置２１０の送信部２１１は、署名データセットＳＳを、通信路２３０を介して署名検証装置２２０へ送信する。

秘密鍵格納部２１２は、メッセージｍに対する多項式ｓを生成するための秘密鍵ＫＳを格納している。秘密鍵ＫＳは予め与えられているものとする。

公開鍵証明書格納部２１３は、上述の多項式ｈにより示される公開鍵ＫＰ（公開鍵ｈ）の公開鍵証明書ＣＰを格納する。公開鍵証明書ＣＰは、公開鍵ＫＰと、認証局ＣＡによる公開鍵ＫＰの署名データＳＰとからなる。この署名データＳＰも、改良ＮＴＲＵＳｉｇｎ署名方式２を使用して生成されている。また、公開鍵証明書ＣＰは予め与えられているものとする。なお、公開鍵証明書ＣＰは、公開鍵ＫＰと署名データＳＰ以外の他のデータを含んでいてもよい。例えば、ユーザの識別子や公開鍵証明書ＣＰの期限などを含んでもよい。

署名生成部２１４は、秘密鍵格納部２１２に格納されている秘密鍵ＫＳを用いて、メッセージｍに対する多項式ｓ，ｔを生成し、さらに、その多項式ｓ，ｔと同等の多項式ｓ’，ｔ’を復元して検証するための署名データＳ（多項式ｓｌ’，ｔｈ’）を生成する。

図１１は、本実施の形態における署名生成部２１４の構成を示すブロック図である。

署名生成部２１４は、ハッシュ値生成部２１４１と、署名ベクトル生成部２１４２と、署名データ生成部２１４３とを備える。

ハッシュ値生成部２１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）（ｍ１及びｍ２はＮ次多項式）を算出する。

署名ベクトル生成部２１４２は、秘密鍵ＫＳとハッシュ値Ｈを用いて、上記（式１１）〜（式１４）により、多項式ｓ，ｔを生成する。さらに、本実施の形態における署名ベクトル生成部２１４２は、実施の形態１の署名ベクトル生成部１１４２と異なり、生成された多項式ｓ，ｔを用いて、上記（式１５）および（式１６）により、多項式ｓ’，ｔ’を算出する。つまり、署名ベクトル生成部２１４２は、秘密鍵行列｛（ｆ，ｇ），（Ｆ，Ｇ）｝により張られる２・Ｎ次元格子上において、メッセージｍに対するハッシュ値Ｈ（ｍ）＝（ｍ１，ｍ２）の最近接格子点Ｐを示す署名ベクトル（ｓ’，ｔ’）を算出する。

署名データ生成部２１４３は、実施の形態１の署名データ生成部１１４３と異なり、署名ベクトル生成部２１４２で算出された多項式ｓ’，ｔ’を用い、ｓ’−ｍ１＝ｓｌ’およびｔ’＝ｔｌ’＋ｔｈ’×ｑを満たす多項式ｓｌ’，ｔｈ’を算出し、その多項式ｓｌ’，ｔｈ’を示す署名データＳを生成する。

図１２は、署名生成部２１４の動作を示すフローチャートである。

まず、署名生成部２１４のハッシュ値生成部２１４１は、メッセージｍに対するハッシュ値Ｈを示す２・Ｎ次元のベクトル（ｍ１，ｍ２）を算出する（ステップＳ２００）。

次に、署名生成部２１４の署名ベクトル生成部２１４２は、上記（式１１）および（式１２）を満たす多項式ａ，ｂ，Ａ，Ｂを算出する（ステップＳ２０２）。さらに、署名ベクトル生成部２１４２は、上記（式１３）および（式１４）により、多項式ｓ，ｔを算出する（ステップＳ２０４）。そして、署名ベクトル生成部２１４２は、多項式ｓ，ｔを用いて、上記（式１５）および（式１６）により、多項式ｓ’，ｔ’を算出する（ステップＳ２０６）。

署名生成部２１４の署名データ生成部２１４３は、ｓ’−ｍ１＝ｓｌ’およびｔ’＝ｔｌ’＋ｔｈ’×ｑを満たす多項式ｓｌ’，ｔｈ’を算出し、その多項式ｓｌ’，ｔｈ’を示す署名データＳを生成する（ステップＳ２０８）。

ここで、本実施の形態における署名生成装置２１０の全体的な動作について、実施の形態１の図６に示すフローチャートを参照して説明する。

署名生成装置２１０の署名生成部２１４は、秘密鍵格納部２１２に格納されている秘密鍵ＫＳを用いて、メッセージｍに対する多項式ｓ，ｔを生成するとともに、その多項式ｓ，ｔに基づいて署名データＳ（多項式ｓｌ’，ｔｈ’を示すデータ）を生成する（ステップＳ１２０）。

次に、署名生成装置２１０の署名データセット生成部２１５は、メッセージｍと、署名データＳと、公開鍵証明書格納部２１３に格納されている公開鍵証明書ＣＰとからなる署名データセットＳＳを生成する（ステップＳ１２２）。

そして、署名生成装置２１０の送信部２１１は、通信路２３０を介して署名データセットＳＳを署名検証装置２２０へ送信する（ステップＳ１２４）。

以下、本実施の形態における署名検証装置２２０について詳細に説明する。

署名検証装置２２０の受信部２２１は、署名生成装置２１０から送信された署名データセットＳＳを、通信路２３０を介して受信する。

ＣＡ公開鍵格納部２２２は、署名データセットＳＳに含まれる公開鍵証明書ＣＰを検証するための認証局ＣＡの公開鍵ＫＣＰを格納する。

署名データセット格納部２２３は、受信部２２１で受信された署名データセットＳＳを格納する。

署名検証部２２４は、署名データセットＳＳに含まれる署名データＳと、公開鍵証明書ＣＰに含まれる署名データＳＰとを検証する。

図１３は、本実施の形態における署名検証部２２４の構成を示すブロック図である。

署名検証部２２４は、ハッシュ値生成部２２４１と、署名ベクトル生成部２２４３と、距離判定部２２４４とを備える。

ハッシュ値生成部２２４１は、署名対象データであるメッセージｍおよび公開鍵ＫＰのそれぞれのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する。

署名ベクトル生成部２２４３は、実施の形態１の署名ベクトル生成部１２４３と異なり、署名データＳおよび署名データＳＰのそれぞれに対して、多項式ｓ’，ｔ’を算出する。即ち、署名ベクトル生成部２２４３は、署名データによって示される多項式ｓｌ’をｓ’＝ｓｌ’＋ｍ１に代入することで、多項式ｓ’を算出する。さらに、署名ベクトル生成部２２４３は、算出された多項式ｓ’と、多項式ｈ（公開鍵ＫＰまたは公開鍵ＫＣＰにより示される多項式）とを、上記（式１７）に代入することにより、多項式ｔｌ’を算出する。そして、署名ベクトル生成部２２４３は、署名データによって示される多項式ｔｈ’と多項式ｔｌ’とを、ｔ’＝ｔｌ’＋ｔｈ’×ｑに代入することにより、多項式ｔ’を算出する。

これにより、署名ベクトル生成部２２４３は、署名データＳおよび署名データＳＰのそれぞれに対して、２・Ｎ次元ベクトル（ｓ’，ｔ’）を署名ベクトルＳＶとして生成する。

距離判定部２２４４は、メッセージｍおよび署名データＳと、公開鍵ＫＰおよび署名データＳＰとのそれぞれに対して、ハッシュ値Ｈと署名ベクトルＳＶの距離を計算し、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する。即ち、メッセージｍおよび署名データＳに対する、ハッシュ値と署名ベクトルＳＶの距離がＮｏｒｍｂｏｕｎｄ未満であれば、距離判定部２２４４は、署名データＳが正しいと判定してその署名データＳを受理する。一方、Ｎｏｒｍｂｏｕｎｄ以上であれば、距離判定部２２４４は、署名データＳが不正と判定してその署名データＳを拒否する。また、公開鍵ＫＰおよび署名データＳＰに対する、ハッシュ値と署名ベクトルＳＶの距離がＮｏｒｍｂｏｕｎｄ未満であれば、距離判定部２２４４は、署名データＳＰが正しいと判定してその署名データＳＰを受理する。一方、Ｎｏｒｍｂｏｕｎｄ以上であれば、距離判定部２２４４は、署名データＳＰが不正と判定してその署名データＳＰを拒否する。

図１４は、署名検証部２２４の動作を示すフローチャートである。

署名検証部２２４は、公開鍵ＫＰを用い、メッセージｍおよび署名データＳに対して図１４に示す動作を行うことにより、その署名データＳを検証する。なお、署名検証部２２４は、署名データＳの検証を行う前に、公開鍵ＫＣＰを用い、公開鍵ＫＰおよび署名データＳＰに対して図１４に示す動作を行うことにより、その署名データＳＰを検証している。

以下、署名検証部２２４が署名データＳを検証する具体的な動作について、図１４を参照して説明する。

まず、署名検証部２２４のハッシュ値生成部２２４１は、署名データＳに対応するメッセージｍのハッシュ値Ｈ（＝（ｍ１，ｍ２））を算出する（ステップＳ２４０）。

次に、署名ベクトル生成部２２４３は、署名データＳにより示される多項式ｓｌ’をｓ’＝ｓｌ’＋ｍ１に代入することで、多項式ｓ’を算出する（ステップＳ２４２）。さらに、署名ベクトル生成部２２４３は、算出された多項式ｓ’と、公開鍵ＫＰにより示される多項式ｈとを、上記（式１７）に代入することにより、多項式ｔｌ’を算出する（ステップＳ２４４）。そして、署名ベクトル生成部２２４３は、署名データＳによって示される多項式ｔｈ’と多項式ｔｌ’とを、ｔ’＝ｔｌ’＋ｔｈ’×ｑに代入することにより、多項式ｔ’を算出する（ステップＳ２４６）。このとき、署名ベクトル生成部２２４３は、署名データＳに対して、２・Ｎ次元ベクトル（ｓ’，ｔ’）を署名ベクトルＳＶとして生成する。

距離判定部２２４４は、ステップＳ２４０で算出されたハッシュ値Ｈ＝（ｍ１，ｍ２）と、ステップＳ２４６で生成された署名ベクトルＳＶとの距離を算出する（ステップＳ２４８）。そして、距離判定部２２４４は、その距離がＮｏｒｍｂｏｕｎｄ未満であるか否かを判定する（ステップＳ２５０）。距離判定部２２４４は、Ｎｏｒｍｂｏｕｎｄ未満であると判定したときには（ステップＳ２５０のＹ）、署名データＳが正しいと判断してその署名データＳを受理する（ステップＳ２５２）。一方、距離判定部２２４４は、Ｎｏｒｍｂｏｕｎｄ未満でないと判定したときには（ステップＳ２５０のＮ）、署名データＳが不正であると判断してその署名データＳを拒否する（ステップＳ２５４）。

ここで、本実施の形態における署名検証装置２２０の全体的な動作について、実施の形態１の図９に示すフローチャートを参照して説明する。

まず、署名検証装置２２０の受信部２２１は、署名生成装置２１０から通信路２３０を介して署名データセットＳＳを受信し、その署名データセットＳＳを署名データセット格納部２２３に格納する（ステップＳ１７０）。

署名検証部２２４は、署名データセットＳＳの中の公開鍵証明書ＣＰに含まれる公開鍵ＫＰとその署名データＳＰに対し、署名データＳＰが公開鍵ＫＰの正しい署名であるか否かを、ＣＡ公開鍵格納部２２２に格納されている認証局ＣＡの公開鍵ＫＣＰを用いて検証する。つまり、署名検証部２２４は、署名データＳＰが正しい署名であるか否かを判別する（ステップＳ１７２）。ここで、署名検証部２２４は、正しい署名でないと判別したときには（ステップＳ１７２のＮ）、その署名データＳＰを拒否する（ステップＳ１７４）。

一方、署名検証部２２４は、ステップＳ１７２で署名データＳＰが正しい署名であると判別したときには（ステップＳ１７２のＹ）、その署名データＳＰを受理する。さらに、署名検証部２２４は、署名データセットＳＳの中のメッセージｍとその署名データＳに対し、署名データＳがメッセージｍの正しい署名であるか否かを、公開鍵ＫＰを用いて検証する。つまり、署名検証部２２４は、署名データＳが正しい署名であるか否かを判別する（ステップＳ１７６）。

ここで、署名検証部２２４は、正しい署名でないと判別したときには（ステップＳ１７６のＮ）、その署名データＳを拒否し（ステップＳ１７４）、正しい署名であると判別したときには（ステップＳ１７６のＹ）、その署名データＳを受理する（ステップＳ１７８）。即ち、ステップＳ１７８では、署名検証部２２４は、署名データセットＳＳが正当な署名を受けたデータであると認識する。

このように本実施の形態では、署名生成装置２１０において、公開鍵を用いたときに、署名ベクトル（ｓ’，ｔ’）を復元できるような多項式ｓｌ’＝ｓ’−ｍ１，ｔｈ’を署名データに含めている。したがって、そのような署名データおよびメッセージを取得した署名検証装置２２０は、その署名データから署名ベクトル（ｓ’，ｔ’）を正しく復元することができ、その署名ベクトル（ｓ’，ｔ’）を用いて署名検証を行うことができる。例えば、署名検証装置２２０は、メッセージｍに対してハッシュ関数を適用することによりハッシュ値である（ｍ１，ｍ２）を生成し、多項式ｓｌ’にその多項式ｍ１を加算することにより、多項式ｓ’を正しく復元することができる。さらに、署名検証装置２２０は、その多項式ｓ’と公開鍵（多項式ｈ）との積の法をｑとする剰余に、多項式ｔｈ’とｑとの積を加算することにより、署名ベクトルの一部である多項式ｔ’を正しく復元することができる。このように、本発明では、署名ベクトルである署名ベクトル（ｓ’，ｔ’）に対して（ｍｏｄ ｑ）の演算を行うことなく、その署名ベクトル（ｓ’，ｔ’）を署名検証装置２２０側で正しく復元できるような署名データを生成するため、（ｍｏｄ ｑ）の演算による情報の欠落を防ぎ、従来例のような不適切な署名検証エラーの発生を確実に防ぐことができる。したがって、署名ベクトル（ｓ’，ｔ’）の各要素における最大値と最小値との差がｑを超える場合においても、署名検証時に署名ベクトル（ｓ’，ｔ’）を正しく復元することができる。

また、本実施の形態では、署名データとして多項式ｓ’と多項式ｍ１の差（多項式ｓｌ’）を送信している。多項式ｓ’と多項式ｍ１の距離は短く、また、多項式ｓ’の１番目の要素は多項式ｍ１の１番目の要素と等しいため、多項式ｓｌ’（＝ｓ’−ｍ１）は各要素が小さくなり、多項式ｓ’をそのまま送信するより送信データ量を削減することができる。

以上、本発明について上記実施の形態１および２を用いて説明したが、これらは、本発明の一例であり、本発明はこのような実施の形態に何ら限定されるものではない。つまり、本発明は、本発明の本質を逸脱しない範囲において種々なる態様で実施し得るものである。例えば、以下のような場合も本発明に含まれる。

（１） 実施の形態１において、多項式ｓの代わりに、ノルムが０であるベクトルを多項式ｓに加算して生成された多項式ｓａ（ｓａ＝ｓ＋（α，α，…，α））を使用してもよい。ここで、αは１からｑ−１のいずれかの整数であり、（α，α，…，α）はすべての要素がαであるベクトル、つまりノルムが０のベクトルである。この場合、ｓａ＝ｓｌ＋ｓｈ×ｑおよびｔ＝ｔｌ＋ｔｈ×ｑを満たす多項式ｓｌ，ｓｈ，ｔｈが署名として扱われる。

（２） 実施の形態２において、ノルムが０のベクトルを多項式ｓに加算することにより、多項式ｓ’と多項式ｍ１とにおける第１要素（０次の項の係数）を等しくしたが、他の要素、つまり第２要素から第Ｎ要素の何れかの要素を等しくしてもよい。例えば、多項式ｓ’と多項式ｍ１とにおける第３要素（２次の項の係数）が等しくなるように、ノルムが０のベクトルを多項式ｓに加算する。

（３） 実施の形態２において、署名データの一部として、ｓ’とｍ１の差であるｓｌ’＝ｓ’−ｍ１を送信しているが、ｓｌ”＝ｓ’−ｍ１＋（β，β，…，β）により算出されるｓｌ”とβを、ｓｌ’の代わりに、署名データの一部として送信してもよい。ここで、（β，β，…，β）はすべての要素がβであるベクトルである。

（４） 上記実施の形態１および２における署名生成装置および署名検証装置は、具体的には、マイクロプロセッサ、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、ハードディスクユニット、ディスプレイユニット、キーボード、およびマウスなどから構成されるコンピュータシステムである。前記ＲＡＭまたはハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、署名生成装置および署名検証装置は、その機能を達成する。ここでコンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。

（５） 上記実施の形態１および２における署名生成装置および署名検証装置を構成する構成要素の一部または全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ Ｓｃａｌｅ Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、システムＬＳＩは、その機能を達成する。

（６） 上記実施の形態１および２における署名生成装置および署名検証装置を構成する構成要素の一部または全部は、署名生成装置または署名検証装置に脱着可能なＩＣ（Integrated Circuit）カード、または単体のモジュールから構成されているとしてもよい。前記ＩＣカードまたは前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。前記ＩＣカードまたは前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムにしたがって動作することにより、前記ＩＣカードまたは前記モジュールは、その機能を達成する。このＩＣカードまたはこのモジュールは、耐タンパ性を有するとしてもよい。

（７） 本発明は、上記実施の形態１および２のディジタル署名システムにおけるそのシステムや装置として実現されるだけでなく、処理方法としても実現できる。また、この処理方法による動作をコンピュータに実行させるコンピュータプログラムとして実現してもよく、前記コンピュータプログラムからなるディジタル信号として実現してもよい。

（８） また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、ＭＯ（Magneto-Optical disk）、ＤＶＤ（Digital Versatile Disk）、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ Ｄｉｓｃ）、半導体メモリなどに記録したものとして実現してもよい。また、これらの記録媒体に記録されている前記ディジタル信号として実現してもよい。

（９） また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を、電気通信回線、無線または有線通信回線、インターネットを代表とするネットワーク、もしくはデータ放送等を経由して伝送するものとして実現してもよい。

（１０） また、本発明は、マイクロプロセッサとメモリを備えたコンピュータシステムとして実現しても良い。この場合には、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムにしたがって動作する。

（１１） また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を前記記録媒体に記録して移送することにより、または前記コンピュータプログラムまたは前記ディジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実現してもよい。

（１２） また、本発明は、上記実施の形態１および２をそれぞれ組み合わせて実現してもよい。

本発明の署名生成装置および署名検証装置は、不適切な署名検証エラーの発生を確実に防ぐことができるという効果を奏し、例えば、ディジタル署名システムなどに適用することができる。

図１は、署名の生成方法を説明するための説明図である。 図２は、署名の検証方法を説明するための説明図である。 図３は、本発明の実施の形態１におけるディジタル署名システムの構成を示すブロック図である。 図４は、本発明の実施の形態１における署名生成部の構成を示すブロック図である。 図５は、本発明の実施の形態１における署名生成部の動作を示すフローチャートである。 図６は、本発明の実施の形態１における署名生成装置の全体的な動作を示すフローチャートである。 図７は、本発明の実施の形態１における署名検証部の構成を示すブロック図である。 図８は、本発明の実施の形態１における署名検証部の動作を示すフローチャートである。 図９は、本発明の実施の形態１における署名検証装置の全体的な動作を示すフローチャートである。 図１０は、本発明の実施の形態２におけるディジタル署名システムの構成を示すブロック図である。 図１１は、本発明の実施の形態２における署名生成部の構成を示すブロック図である。 図１２は、本発明の実施の形態２における署名生成部の動作を示すフローチャートである。 図１３は、本発明の実施の形態２における署名検証部の構成を示すブロック図である。 図１４は、本発明の実施の形態２における署名検証部の動作を示すフローチャートである。

符号の説明

１００ ディジタル署名システム
１１０ 署名生成装置
１１１ 送信部
１１２ 秘密鍵格納部
１１３ 公開鍵証明書格納部
１１４ 署名生成部
１１５ 署名データセット生成部
１２０ 署名検証装置
１２１ 受信部
１２２ ＣＡ公開鍵格納部
１２３ 署名データセット格納部
１２４ 署名検証部
１３０ 通信路
１１４１ ハッシュ値生成部
１１４２ 署名ベクトル生成部
１１４３ 署名データ生成部
１２４１ ハッシュ値生成部
１２４３ 署名ベクトル生成部
１２４４ 距離判定部

Claims (14)

1. メッセージデータに対する署名データを、署名方式に従って生成する署名生成装置であって、
   前記署名方式は、
   加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
   前記署名生成装置は、
   前記メッセージデータに対する、前記環Ｒの元ｓ，ｔからなる署名ベクトルを、前記秘密鍵を用いて算出する署名ベクトル生成手段と、
   前記元ｓを特定し得る前記環Ｒの第１の元と、前記元ｔをｑで割ったときの商である前記環Ｒの第２の元とを示す前記署名データを生成する署名データ生成手段と
   を備えることを特徴とする署名生成装置。
2. 前記第１の元は、前記元ｓをｑで割ったときの商である前記環Ｒの元ｓｈと、前記元ｓをｑで割ったときの余りである前記環Ｒの元ｓｌとからなる
   ことを特徴とする請求項１記載の署名生成装置。
3. 前記署名生成装置は、さらに、
   前記メッセージデータに対してハッシュ関数を適用することにより、前記環Ｒの元ｍ１および元ｍ２を生成するハッシュ値生成手段を備え、
   前記署名データ生成手段は、
   前記元ｓと前記元ｍ１との差を前記第１の元として生成する
   ことを特徴とする請求項１記載の署名生成装置。
4. 前記署名ベクトル生成手段は、
   前記元ｍ１と前記元ｓとのそれぞれのｉ番目の要素（ｉは１からＮの何れかの整数）が同じ値となるように、前記元ｓを算出する
   ことを特徴とする請求項３記載の署名生成装置。
5. 前記署名ベクトル生成手段は、
   ノルムが０である前記環Ｒの元の加算または減算を行うことにより、前記元ｓを算出する
   ことを特徴とする請求項４記載の署名生成装置。
6. 前記署名ベクトル生成手段は、
   前記第１の元に含まれる各要素の値が０に近づくように前記元ｓを算出する
   ことを特徴とする請求項３記載の署名生成装置。
7. メッセージデータに対する署名データを、署名方式に従って検証する署名検証装置であって、
   前記署名方式は、
   加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
   前記署名検証装置は、
   前記メッセージデータに対して前記秘密鍵を用いて算出された、前記環Ｒの元ｓ，ｔからなる署名ベクトルのうち、前記元ｓを、前記署名データの示す前記環Ｒの第１の元を用いて復元するとともに、前記元ｔを、前記署名データの示す前記環Ｒの第２の元にｑを乗算した結果を用いて復元する署名ベクトル生成手段と、
   前記署名ベクトルを検証する検証手段と
   を備えることを特徴とする署名検証装置。
8. 前記第１の元は、前記元ｓをｑで割ったときの商である前記環Ｒの元ｓｈと、前記元ｓをｑで割ったときの余りである前記環Ｒの元ｓｌとからなり、前記第２の元は、前記元ｔをｑで割ったときの商であり、
   前記署名ベクトル生成手段は、
   前記元ｓｈにｑを乗算して前記元ｓｌを加算することにより、前記元ｓを復元し、
   前記元ｓｌと前記元ｈとの積の法をｑとする剰余に、前記第２の元とｑとの積を加算することにより、前記元ｔを復元する
   ことを特徴とする請求項７記載の署名検証装置。
9. 前記署名検証装置は、さらに、
   前記メッセージデータに対してハッシュ関数を適用することにより、前記環Ｒの元ｍ１および元ｍ２を生成するハッシュ値生成手段を備え、
   前記第１の元は、前記元ｓと前記元ｍ１との差である前記環Ｒの元ｓｌからなり、前記第２の元は、前記元ｔをｑで割ったときの商であり、
   前記署名ベクトル生成手段は、
   前記元ｓｌに前記元ｍ１を加算することにより、前記元ｓを復元し、
   前記元ｓと元ｈとの積の法をｑとする剰余に、前記第２の元とｑとの積を加算することにより、前記元ｔを復元する
   ことを特徴とする請求項７記載の署名検証装置。
10. 前記署名検証装置は、さらに、
    前記メッセージデータに対してハッシュ関数を適用することにより、前記環Ｒの元ｍ１および元ｍ２を生成するハッシュ値生成手段を備え、
    前記検証手段は、
    前記署名ベクトルと、前記元ｍ１および元ｍ２からなるハッシュ値ベクトルとの距離を、予め定められた距離と比較することにより、前記署名ベクトルを検証する
    ことを特徴とする請求項７記載の署名検証装置。
11. 署名生成装置がメッセージデータに対する署名データを、署名方式に従って生成する署名生成方法であって、
    前記署名方式は、
    加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
    前記署名生成装置は、署名ベクトル生成手段と署名データ生成手段とを備え、
    前記署名生成方法は、
    前記署名生成ステップを含み、
    前記署名生成ステップは、
    前記署名ベクトル生成手段が、前記メッセージデータに対する、前記環Ｒの元ｓ，ｔからなる署名ベクトルを、前記秘密鍵を用いて算出する署名ベクトル生成ステップと、
    前記署名データ生成手段が、前記元ｓを特定し得る前記環Ｒの第１の元と、前記元ｔをｑで割ったときの商である前記環Ｒの第２の元とを示す前記署名データを生成する署名データ生成ステップと
    を含むことを特徴とする署名生成方法。
12. 署名検証装置がメッセージデータに対する署名データを、署名方式に従って検証する署名検証方法であって、
    前記署名方式は、
    加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
    前記署名検証装置は、署名ベクトル生成手段と検証手段とを備え、
    前記署名検証方法は、
    前記署名検証ステップを含み、
    前記署名検証ステップは、
    前記署名ベクトル生成手段が、前記メッセージデータに対して前記秘密鍵を用いて算出された、前記環Ｒの元ｓ，ｔからなる署名ベクトルのうち、前記元ｓを、前記署名データの示す前記環Ｒの第１の元を用いて復元するとともに、前記元ｔを、前記署名データの示す前記環Ｒの第２の元にｑを乗算した結果を用いて復元する署名ベクトル生成ステップと、
    前記検証手段が前記署名ベクトルを検証する検証ステップと
    を含むことを特徴とする署名検証方法。
13. メッセージデータに対する署名データを、署名方式に従って生成する集積回路であって、
    前記署名方式は、
    加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
    前記集積回路は、
    前記メッセージデータに対する、前記環Ｒの元ｓ，ｔからなる署名ベクトルを、前記秘密鍵を用いて算出する署名ベクトル生成手段と、
    前記元ｓを特定し得る前記環Ｒの第１の元と、前記元ｔをｑで割ったときの商である前記環Ｒの第２の元とを示す前記署名データを生成する署名データ生成手段と
    を備えることを特徴とする集積回路。
14. メッセージデータに対する署名データを、署名方式に従って検証する集積回路であって、
    前記署名方式は、
    加算、減算、乗算、および元の大きさを示すノルムが定義されたＮ次元配列の集合である環Ｒと、正整数ｑとに対し、前記環Ｒの元ｆ，ｇおよび、ｆ（ｍｏｄ ｑ）の逆数である元Ｆｑを生成し（ここでｆ（ｍｏｄ ｑ）は、ｆをｑで割った余りを示す。）、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、ｆ×Ｇ−ｇ×Ｆ＝ｑを満たす元Ｆ，Ｇを生成し（ここで×は環Ｒの乗算を示す。）、前記４つの元ｆ，ｇ，Ｆ，Ｇからなる組｛ｆ，ｇ，Ｆ，Ｇ｝を秘密鍵として生成する鍵生成ステップと、前記メッセージデータに対する、前記環Ｒの元である前記署名データを、前記秘密鍵を用いて生成する署名生成ステップと、前記公開鍵を用いて前記署名データを検証する署名検証ステップとを含み、
    前記集積回路は、
    前記メッセージデータに対して前記秘密鍵を用いて算出された、前記環Ｒの元ｓ，ｔからなる署名ベクトルのうち、前記元ｓを、前記署名データの示す前記環Ｒの第１の元を用いて復元するとともに、前記元ｔを、前記署名データの示す前記環Ｒの第２の元にｑを乗算した結果を用いて復元する署名ベクトル生成手段と、
    前記署名ベクトルを検証する検証手段と
    を備えることを特徴とする集積回路。

Images