(57)【要約】メッセージのデジタル署名を生成し検証するめの方法及びシステムが提供されている。デジタル署名は、デジタル署名多項式を含んでいる。環Ｒ（１０２）の互いに素な二つのイデアルｐ及びｑが選択される。秘密鍵及び第二イデアルｑが、公開鍵の生成に用いられる。一つ以上のメッセージ多項式が、署名されるべきメッセージに基づいて生成される。デジタル署名多項式は、メッセージ多項式の少なくとも一つと、秘密鍵多項式の少なくとも一つと、イデアルｐ及びｑのうち少なくとも一つとを用いて、未規約化状態のデジタル署名多項式が環Ｒの秘密鍵多項式の倍数でないというように、生成される（１１０）。署名は、続いて、少なくとも一つのメッセージ多項式と少なくとも一つのデジタル署名多項式との間の偏差（deviation）が予め定められた偏差（deviation）の閾値より小さいことを確認することにより、検証される（１１６）。
2004526387.tif 000002
【特許請求の範囲】
【請求項１】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
環Ｒの互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択する工程と、
前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成する工程と、
前記メッセージに基づいて一つ以上のメッセージ多項式を生成する工程と、
前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
を用いて、未規約化状態での前記デジタル署名多項式が前記環Ｒの前記秘密鍵多項式の倍数ではないというように、生成する工程と、
前記デジタル署名を、少なくとも、前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差閾値よりも小さいことを確認することにより、検証する工程と、
を備えた方法。
【請求項２】
前記環Ｒは、Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）であって、Ｎは１より大きい整数である
ことを特徴とする請求項１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３】
前記予め定められた偏差閾値は、Ｎ／５以下である
ことを特徴とする請求項２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４】
前記予め定められた偏差閾値は、ゼロに等しい
ことを特徴とする請求項１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項５】
前記メッセージ多項式は、前記メッセージに一つ以上のハッシュ関数を施すことにより生成される
ことを特徴とする請求項１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項６】
前記デジタル署名多項式の生成は、更に、
（ｄ）一つ以上のランダム秘密多項式
を用いることを含む
ことを特徴とする請求項１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項７】
ワンタイム秘密鍵を選択する工程を更に備えると共に、
前記デジタル署名多項式の生成は、更に、
（ｄ）前記ワンタイム秘密鍵
を用いることを含む
ことを特徴とする請求項１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項８】
前記検証は、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを確認する工程を更に有する
ことを特徴とする請求項１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項９】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
環Ｒの互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択する工程と、
前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成する工程と、
前記メッセージに基づいて一つ以上のメッセージ多項式を生成する工程と、
前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
を用いて生成する工程と、
前記デジタル署名を、少なくとも、前記デジタル署名多項式の少なくとも一つと関連付けられたノルムが予め定められたノルム閾値よりも小さいことを確認することにより、検証する工程と、
を備えた方法。
【請求項１０】
前記環Ｒは、Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）であって、Ｎは１より大きい整数である
ことを特徴とする請求項９に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１１】
前記デジタル署名多項式の少なくとも一つと関連付けられたノルムは、少なくとも一つのデジタル署名多項式のノルムである
ことを特徴とする請求項１０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１２】
前記メッセージ多項式の一つを前記デジタル署名多項式の一つから差し引くことにより微分多項式を計算する工程を更に備えると共に、
前記少なくとも一つのデジタル署名多項式に関連付けられたノルムは、前記微分多項式のノルムである
ことを特徴とする請求項１０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１３】
前記ノルムは、ユークリッドノルムであり、
前記予め定められたノルム閾値は、Ｎのオーダーである
ことを特徴とする請求項１０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１４】
前記メッセージ多項式は、前記メッセージに一つ以上のハッシュ関数を施すことにより生成される
ことを特徴とする請求項９に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１５】
前記デジタル署名多項式の生成は、更に、
（ｄ）一つ以上のランダム秘密多項式
を用いることを含む
ことを特徴とする請求項９に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１６】
ワンタイム秘密鍵を選択する工程を更に備えると共に、
前記デジタル署名多項式の生成は、更に、
（ｄ）前記ワンタイム秘密鍵
を用いることを含む
ことを特徴とする請求項９に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１７】
前記検証は、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを確認する工程を更に有する
ことを特徴とする請求項９に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１８】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
環Ｒのイデアルｐ及びｑを選択する工程と、
前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択する工程と、
前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成する工程と、
前記メッセージに基づいて一つ以上のメッセージ多項式を生成する工程と、
補助的な多重利用秘密情報を選択する工程と、
前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
（ｄ）前記補助的な多重利用秘密情報
を用いて生成する工程と、
前記デジタル署名を、少なくとも、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを確認することにより、検証する工程と、
を備えた方法。
【請求項１９】
前記環Ｒは、Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）であって、Ｎは１より大きい整数である
ことを特徴とする請求項１８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２０】
前記補助的な多重利用秘密情報は、前記環Ｒの一つ以上の補助的な秘密鍵多項式を含む
ことを特徴とする請求項１８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２１】
前記デジタル署名多項式の生成は、
前記デジタル署名多項式への二次の平均化攻撃（averaging attack）が前記補助的な秘密鍵多項式に依存した値に収束するというように、前記補助的な秘密鍵多項式を用いて一つ以上の前記デジタル署名多項式を調整する工程
を更に有することを特徴とする請求項２０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２２】
前記デジタル署名多項式の検証は、
前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が、予め定められた偏差閾値よりも小さいことを確認する工程
を更に有することを特徴とする請求項１８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２３】
前記デジタル署名多項式の検証は、
前記デジタル署名多項式の少なくとも一つのノルムが予め定められたノルム閾値よりも小さいことを確認する工程
を更に有することを特徴とする請求項１８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２４】
前記メッセージ多項式は、前記メッセージに一つ以上のハッシュ関数を施すことにより生成される
ことを特徴とする請求項１８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２５】
前記デジタル署名多項式の生成は、更に、
（ｅ）一つ以上のランダム秘密多項式
を用いることを含む
ことを特徴とする請求項１８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２６】
ワンタイム秘密鍵を選択する工程を更に備えると共に、
前記デジタル署名多項式の生成は、更に、
（ｅ）前記ワンタイム秘密鍵
を用いることを含む
ことを特徴とする請求項１８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２７】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は二つのデジタル署名多項式ｕ及びｖを含んでおり、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵を選択する工程と、
【数１】
2004526387.tif 000023
を計算する工程と、
前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成する工程と、
第一中間秘密多項式ｓ及び第二中間秘密多項式ｔを、ｓ＊ｈ＝ｔであるように、また、ｓ及びｔがｐを法として実質的に一致するように、選択する工程と、
第三の中間秘密多項式ａを、前記メッセージ多項式ｍの一つと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように、選択する工程と、
前記第一デジタル署名多項式ｕ＝ｓ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算する工程と、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算する工程と、
前記デジタル署名を、少なくとも、前記メッセージ多項式ｍの一つ以上と前記第一デジタル署名多項式ｕとの間の第一偏差（deviation）が予め定められた偏差閾値よりも小さいことと、前記メッセージ多項式ｍの一つ以上と前記第二デジタル署名多項式ｖとの間の第二偏差（deviation）が予め定められた偏差閾値よりも小さいことと、を確認することにより、検証する工程と、
を備えた方法。
【請求項２８】
前記秘密鍵多項式ｆ及びｇは、各々、ｐを法として前記環Ｒの多項式ｋと一致しており、
前記秘密鍵多項式ｆ及びｇの各々は、
【数２】
2004526387.tif 000024
のオーダーのユークリッドノルムを有している
ことを特徴とする請求項２７に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２９】
前記環Ｒのランダム多項式ｒを選択する工程を更に備えると共に、
第一中間秘密多項式ｓの選択は、ｓ＝ｐｒ＊（１−ｈ）−１（ｍｏｄ  ｑ）の計算を含み、
第二中間秘密多項式ｔの選択は、ｔ＝ｓ＊ｈ（ｍｏｄ  ｑ）の計算を含み、
第三中間秘密多項式ａの選択は、ａ＝ｆｐ−１＊（ｍ−ｓ）（ｍｏｄ  ｐ）の計算を含んでいる
ことを特徴とする請求項２７に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３０】
前記ランダム多項式ｒは、Ｎまたはより小さいオーダーのユークリッドノルムを有する
ことを特徴とする請求項２９に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３１】
前記予め定められた偏差閾値は、Ｎ／８以下である
ことを特徴とする請求項２９に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３２】
前記デジタル署名の検証は、ｕ＊ｈ＝ｖ（ｍｏｄ  ｑ）であることを確認する工程を更に有する
ことを特徴とする請求項２７に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３３】
前記メッセージ多項式ｍは、一つ以上の安全なハッシュ関数Ｈ（ｍ）を用いて生成される
ことを特徴とする請求項２７に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３４】
前記ランダム多項式ｒは、ｒ（１）＝０というように選択される
ことを特徴とする請求項２７に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３５】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は二つのデジタル署名多項式ｕ及びｖを含んでおり、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵を選択する工程と、
【数３】
2004526387.tif 000025
を計算する工程と、
前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成する工程と、
ランダム多項式ｒを選択する工程と、
第一中間多項式ｔ＝ｒ＊ｈ（ｍｏｄ  ｑ）を計算する工程と、
第二中間多項式ａを、
【数４】
2004526387.tif 000026
のオーダーのユークリッドノルムを有して、メッセージ多項式ｍと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択する工程と、
前記第一デジタル署名多項式ｕ＝ｒ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算する工程と、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算する工程と、
前記デジタル署名を、少なくとも、前記第一デジタル署名多項式ｕのユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二デジタル署名多項式ｖとの間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証する工程と、
を備えた方法。
【請求項３６】
前記秘密鍵多項式ｆ及びｇの各々は、
【数５】
2004526387.tif 000027
のオーダーのユークリッドノルムを有する
ことを特徴とする請求項３５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３７】
前記ランダム多項式ｒは、Ｎまたはより小さいオーダーのユークリッドノルムを有する
ことを特徴とする請求項３５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３８】
第二中間多項式ａの選択は、
【数６】
2004526387.tif 000028
を計算することを含む
ことを特徴とする請求項３５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３９】
前記予め定められた偏差閾値は、Ｎ／１２以下である
ことを特徴とする請求項３８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４０】
前記デジタル署名の検証は、ｕ＊ｈ＝ｖ（ｍｏｄ  ｑ）であることを確認すること
を更に含む
ことを特徴とする請求項３５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４１】
前記メッセージ多項式ｍは、一つ以上の安全なハッシュ関数Ｈ（ｍ）を用いて生成される
ことを特徴とする請求項３５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４２】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は四つのデジタル署名多項式ｕ１、ｖ１、ｕ２及びｖ２を含んでおり、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択する工程と、
【数７】
2004526387.tif 000029
を計算する工程と、
前記環Ｒのワンタイム秘密鍵多項式ｅを含むワンタイム秘密鍵を選択する工程と、
ワンタイム公開鍵多項式ｈ１及びｈ２の一つのペアを、ｈ１＝ｆ−１＊ｅ（ｍｏｄ  ｑ）及びｈ２＝ｇ−１＊ｅ（ｍｏｄ  ｑ）のように生成する工程と、
第一ランダム多項式ｒ１を選択する工程と、
第一中間多項式ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）を計算する工程と、
第二中間多項式ａ１を、ａ１のユークリッドノルムが
【数８】
2004526387.tif 000030
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択する工程と、
前記第一デジタル署名多項式ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）を計算する工程と、
前記第二デジタル署名多項式ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）を計算する工程と、
第二ランダム多項式ｒ２を選択する工程と、
第三中間多項式ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）を計算する工程と、
第二中間多項式ａ１を、ａ２のユークリッドノルムが
【数９】
2004526387.tif 000031
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択する工程と、
前記第三デジタル署名多項式ｕ２＝ｒ２＋ａ２＊ｇ（ｍｏｄ  ｑ）を計算する工程と、
前記第四デジタル署名多項式ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）を計算する工程と、
前記デジタル署名を、少なくとも、前記第一及び第三のデジタル署名多項式ｕ１及びｕ２の各々のユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二及び第四のデジタル署名多項式ｖ１及びｖ２の各々との間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証する工程と、
を備えた方法。
【請求項４３】
前記秘密鍵多項式ｆ及びｇの各々は、
【数１０】
2004526387.tif 000032
のオーダーのユークリッドノルムを有する
ことを特徴とする請求項４２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４４】
前記ランダム多項式ｒ１及びｒ２は、各々、Ｎまたはより小さいオーダーのユークリッドノルムを有する
ことを特徴とする請求項４２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４５】
第二中間多項式ａ１の選択は、
【数１１】
2004526387.tif 000033
を計算することを含み、
第四中間多項式ａ２の選択は、
【数１２】
2004526387.tif 000034
を計算することを含む
ことを特徴とする請求項４２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４６】
前記予め定められた偏差閾値は、Ｎ／１２以下である
ことを特徴とする請求項４５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４７】
ワンタイム秘密鍵多項式ｅを含むワンタイム秘密鍵の選択は、ｅの第一係数ｅ０をｑ／２ｐのオーダーとなるよう選択することを更に含む
ことを特徴とする請求項４２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４８】
前記予め定められた偏差閾値は、Ｎ／１００以下である
ことを特徴とする請求項４７に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４９】
前記予め定められた偏差閾値は、ゼロである
ことを特徴とする請求項４７に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項５０】
前記第一ランダム多項式ｒ１及び前記第二ランダム多項式ｒ１の選択は、ｒ１及びｒ２を計算するための一つ以上の補助的な多重利用秘密多項式を用いることを更に含む
ことを特徴とする請求項４２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項５１】
第一ランダム多項式ｒ１の選択は、ａ１’が第一のランダムな短い多項式でありｆ’が第一の補助的な多重利用秘密多項式であるとして、ｒ１＝ａ１’＊ｆ’を計算する工程を更に含み、
第二ランダム多項式ｒ２の選択は、ａ２’が第二のランダムな短い多項式でありｇ’が第二の補助的な多重利用多項式であるとして、ｒ２＝ａ２’＊ｇ’を計算する工程を更に含む
ことを特徴とする請求項５０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項５２】
第一ランダム多項式ｒ１の選択は、ａ１’及びａ１’’が第一及び第二のランダムな短い多項式でありｆ’及びｆ’’が第一及び第二の補助的な多重利用秘密多項式であるとして、ｒ１＝ａ１’＊ｆ’＋ａ１’’＊ｆ’’を計算する工程を更に含み、
第二ランダム多項式ｒ２の選択は、ａ２’及びａ２’’が第三及び第四のランダムな短い多項式でありｇ’及びｇ’’が第三及び第四の補助的な多重利用秘密多項式であるとして、ｒ２＝ａ２’＊ｇ’ ＋ａ２’’＊ｇ’’を計算する工程を更に含む
ことを特徴とする請求項５０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項５３】
前記デジタル署名を検証する工程は、
【数１３】
2004526387.tif 000035
であることを確認する工程を更に含んでいる
ことを特徴とする請求項４２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項５４】
前記メッセージ多項式ｍは、一つ以上の安全なハッシュ関数Ｈ（ｍ）を用いて生成される
ことを特徴とする請求項４２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項５５】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つとを用いて未規約化状態での前記デジタル署名多項式が前記環Ｒ上の前記秘密鍵多項式の倍数ではないというように前記デジタル署名多項式を生成するように、及び、前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差閾値よりも小さいことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置。
【請求項５６】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つとを用いて前記デジタル署名多項式を生成するように、及び、前記デジタル署名多項式の少なくとも一つのノルムが予め定められたノルム閾値よりも小さいことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置。
【請求項５７】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、前記秘密鍵と関連しない補助的な多重利用秘密情報と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つと補助的な多重利用秘密情報とを用いて前記デジタル署名多項式を生成するように、及び、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置。
【発明の詳細な説明】
【関連する出願】
【０００１】
出願人は、米国特許法第１１９条（ｅ）に基づき、２００１年５月４日出願された米国仮特許出願第６０／２８８，８４１号の優先権を主張するものであり、当該仮特許出願は引用によって本願に組み込まれる。
【発明の背景】
【０００２】
本発明は、一般に、暗号法、及び、コンピュータネットワークを介したまたは他のタイプのシステムならびに装置を介した安全な（秘密保護の）通信、に関しており、より特別には、環ベースの多項式代数を用いたデジタル署名の生成及び検証に関している。
【０００３】
デジタル署名は、安全な通信において、認証、データ保護及び否認防止を含む、様々な機能を果たしている。典型的には、デジタル署名は、送信すべきメッセージの内容と、署名者のＩＤと、の両方に施される。公開鍵暗号システムにおいて、デジタル署名は、典型的には、署名者のみに知られる秘密鍵と、署名すべきメッセージと、を用いて生成される。誰にでも知られ得る公開鍵は、続いて、当該署名を検証するために用いられる。
【０００４】
デジタル署名は、署名されたメッセージの受領者が、前記署名者が前記秘密鍵を保有していることを確信するというように、検証可能でなければならない。例えば、メッセージの受領者は、署名者のデジタル署名が真正であることを検証するために、署名者の公開鍵を用いることが可能でなければならない。加えて、デジタル署名の偽造は、実行不能でなければならない。最後に、署名者の秘密鍵を危機にさらすことを避けるために、デジタル署名は秘密鍵に関する有用な情報を漏洩してはならない。
【０００５】
デジタル署名を生成し検証するための様々な手法及びシステムが知られており、コンピュータネットワークや他の通信システム、例えば携帯電話ネットワーク、の中で利用されてきた。高速で効率的な署名の生成及び検証を提供するデジタル署名スキームの設計は、特別に強調されてきた。例えば、ＮＴＲＵ署名スキーム（「ＮＳＳ」）と呼ばれるデジタル署名スキームが、ＮＴＲＵ公開鍵暗号システムと関連して提案された。ＮＳＳは、J. Hoffstein, J. Pipher, J.H. Silverman著の「NSS: The NTRU Signature Scheme」（PROC. OF EUROCRYPT ’01, LNCS, 第2045巻, 211乃至228頁, Springer-Verlag, 2001年）に記述された。多項式代数に基づいて、ＮＳＳは、相当に短く容易に生成される鍵を用いており、高速で、かつ、メモリー要求が少ない。
【０００６】
ＮＳＳは、一つの秘密鍵と署名されるべきメッセージとを用いた署名の生成に関連している。秘密鍵、メッセージ及び署名は、それぞれ、一つ以上の多項式として表される。署名生成の過程の間、署名多項式の係数群は、ｐまたはｑを法として規約化される。ここで、前記ｐ及び前記ｑは固定の整数である。ある署名が生成されると、署名多項式とメッセージ多項式との偏差（deviation）を割り出すことにより、当該署名は部分的に検証され得る。二つの多項式ａとｂとの偏差（deviation）は、ｐを法とした、ａ（ｍｏｄ  ｑ）とｂ（ｍｏｄ  ｑ）とで異なる係数の数、として定義される。ＮＳＳは、署名の生成をより効率的に行うために、及び、署名が秘密鍵についての有用な情報を漏洩するであろう可能性を減少させるために、署名多項式とメッセージ多項式との間にある程度の偏差（deviation）を見込むように設計されている。例えば、各多項式が２５１個の係数を有するとき（Ｎ＝２５１）、ＮＳＳは、１多項式あたり５５と８７との間の係数の署名の偏差（deviation）を許容する。従って、ＮＳＳにおける真正な署名は、元となるメッセージから３分のＮより多く偏差（deviate）し得る。
【０００７】
偏差（deviation）の高い許容性のために、ＮＳＳは、深刻なセキュリティの欠陥を含んでいる。多数の暗号解析が、ＮＳＳ署名は署名の係数の確率的操作により比較的容易に偽造され得るということを、実証してきた。例えば、一度の攻撃で、多項式（Ｎ＝２５１）あたりたった５６の係数の偏差（deviation）しか有さない偽造が、署名者の秘密鍵の知識無くして、生成された。加えて、これらの解析は、高い割合の偏差（deviation）にもかかわらず、ＮＳＳ署名はそれでもなお攻撃者が署名者の秘密鍵を入手することを可能とするのに十分に有用な情報を漏洩することを証明した。そのような解析の一つの結果は、C. Gentry, J. Jonsson, J. Stern, M. Szydlo著の「Cryptanalysis of the NTRU Signature Scheme(NSS) from Eurocrypt 2001」（PROC. OF ASIACRYPT’01, LNCS, 第2248号, 1乃至20頁, Springer-Verlag, 2001年）において公開されている。C. Gentry, M. Szydlo著の「Cryptanalysis of the Revised NTRU Signature Scheme」（ADVANCES IN CRYPTOLOGY-Eurocrypt’02, LECTURE NOTES IN COMPUTER SCIENCE, Springer-Verlag, 2002年）もまた、参照されたい。両文献の内容は、引用によって本願に組み込まれ、本願中以下「ＮＳＳ暗号解析文献」という。
【０００８】
結果的に、高速で、効率的でかつ安全なデジタル署名システムへの要求は残存している。従って、本発明の目的は、攻撃者がデジタル署名の偽造を生成することが不可能な、高速で、効率的でかつ安全なデジタル署名システムを提供することである。署名者の秘密鍵についての有用な情報を漏洩しないデジタル署名の生成を可能とすることもまた、本発明の目的である。
【好適な実施の形態の簡単な要約】
【０００９】
本発明によれば、高速で、効率的でかつ安全なデジタル署名の生成及び検証を可能にし、署名の偽造を不可能にし、また、署名者の秘密鍵についての有用な情報を漏洩しない署名を提供する、というデジタル署名の方法及びシステムが記述される。
【００１０】
本発明の一つの特徴によれば、メッセージのデジタル署名を生成して検証する方法が提供されている。前記デジタル署名は、一つ以上のデジタル署名多項式を含んでいる。環Ｒの二つの互いに素なイデアルｐ及びｑが選択される。秘密鍵は、前記環Ｒの一つ以上の秘密鍵多項式を含むように選択される。公開鍵は、前記秘密鍵及び前記第二イデアルｑを用いて生成される。前記メッセージを用いて、一つ以上のメッセージ多項式が生成される。デジタル署名は、続いて、少なくとも以下の要素：（ａ）前記メッセージ多項式の少なくとも一つ（前記メッセージ多項式群の中の少なくとも一つの多項式）、（ｂ）前記秘密鍵多項式の少なくとも一つ（前記秘密鍵多項式群の中の少なくとも一つの多項式）、及び、（ｃ）前記イデアルｐ及びｑの少なくとも一つ、を用いて、未規約化状態での前記デジタル署名多項式が前記環Ｒ上の前記秘密鍵多項式の倍数ではないというように、生成される。前記デジタル署名は続いて、少なくとも、前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差（deviation）の閾値よりも小さいことを確認することにより、検証され得る。
【００１１】
本発明の別の特徴によれば、あるいは、前述の検証プロセスとの組み合わせによれば、前記デジタル署名はまた、少なくとも、前記デジタル署名多項式の少なくとも一つのノルムが予め定められたノルム閾値よりも小さいことを確認することにより、検証され得る。
【００１２】
本発明の別の特徴によれば、メッセージのデジタル署名を生成して検証する方法が提供されている。前記デジタル署名は、一つ以上のデジタル署名多項式を含んでいる。環Ｒの二つの互いに素なイデアルｐ及びｑが、選択される。秘密鍵は、前記環Ｒの一つ以上の秘密鍵多項式を含むように選択される。公開鍵は、前記秘密鍵及び前記第二イデアルｑを用いて生成される。補助的な多重利用秘密情報が、選択される。前記メッセージを用いて、一つ以上のメッセージ多項式が生成される。デジタル署名は、続いて、少なくとも以下の要素：（ａ）前記メッセージ多項式の少なくとも一つ、（ｂ）前記秘密鍵多項式の少なくとも一つ、（ｃ）前記イデアルｐ及びｑの少なくとも一つ、及び、（ｄ）前記補助的な多重利用秘密情報、を用いて生成される。前記デジタル署名は続いて、少なくとも、前記デジタル署名多項式及び前記公開鍵が予め定められた関係を満たすことを確認することにより、検証され得る。
【００１３】
本発明の別の実施の形態によれば、メッセージｍのデジタル署名を生成して検証する方法が提供されている。ここで、前記デジタル署名は、二つのデジタル署名多項式ｕ及びｖを含んでいる。環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の二つの互いに素なイデアルｐ及びｑが、選択される。ここで、Ｎは１より大きい整数である。秘密鍵が、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含むように選択される。公開鍵ｈが、
【数１】
2004526387.tif 000003
として計算される。第一及び第二中間秘密多項式ｓ及びｔが、ｓ＊ｈ＝ｔであるように、また、ｓ及びｔがｐを法として実質的に一致するように、選択される。第三の中間秘密多項式ａは、メッセージ多項式の一つｍと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように、選択される。第一デジタル署名多項式ｕは、続いて、ｕ＝ｓ＋ａ＊ｆ（ｍｏｄ  ｑ）として計算され、第二デジタル署名多項式ｖは、ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）として計算される。最後に、デジタル署名は、ｍとｕとの間の偏差（deviation）が予め定められた偏差（deviation）の閾値よりも小さいことと、ｍとｖとの間の偏差（deviation）もまた予め定められた偏差（deviation）の閾値よりも小さいことと、を確認することにより検証される。
【００１４】
本発明の別の実施の形態によれば、メッセージｍのデジタル署名を生成して検証する別の方法が提供されている。ここで、前記デジタル署名は、二つのデジタル署名多項式ｕ及びｖを含んでいる。環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の二つのイデアルｐ及びｑが、選択される。秘密鍵が、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含むように選択される。公開鍵ｈが、
【数２】
2004526387.tif 000004
として計算される。ランダム多項式ｒが選択されて、第一中間多項式ｔは、ｔ＝ｒ＊ｈ（ｍｏｄ  ｑ）として計算される。第二の中間多項式ａは、ａが
【数３】
2004526387.tif 000005
のオーダーのユークリッドノルムを有して、メッセージ多項式ｍと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように、選択される。第一デジタル署名多項式ｕは、続いて、ｕ＝ｒ＋ａ＊ｆ（ｍｏｄ  ｑ）として計算され、第二デジタル署名多項式ｖは、ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）として計算される。最後に、デジタル署名は、第一デジタル署名多項式ｕに関連付けられたユークリッドノルムがＮのオーダーであることと、メッセージｍと第二デジタル署名多項式ｖとの間の偏差（deviation）が予め定められた偏差（deviation）の閾値よりも小さいことと、を確認することにより検証される。
【００１５】
本発明の別の実施の形態によれば、メッセージｍのデジタル署名を生成して検証する方法が提供されている。ここで、前記デジタル署名は、四つのデジタル署名多項式ｕ１、ｖ１、ｕ２及びｖ２を含んでいる。環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の二つのイデアルｐ及びｑが、選択される。秘密鍵が、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含むように選択される。公開鍵ｈが、
【数４】
2004526387.tif 000006
として計算される。ワンタイム秘密鍵ｅが、前記環Ｒのワンタイム秘密鍵多項式ｅを含むように選択される。二つのワンタイム公開鍵多項式ｈ１及びｈ２が、ｈ１＝ｆ−１＊ｅ（ｍｏｄ  ｑ）及びｈ２＝ｇ−１＊ｅ（ｍｏｄ  ｑ）として生成される。第一ランダム多項式ｒ１が、続いて選択される。次に、第一中間多項式ｔ１が、ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）として計算され、第二中間多項式ａ１が、ａ１のユークリッドノルムが
【数５】
2004526387.tif 000007
のオーダーであってメッセージ多項式の一つ（メッセージ多項式群のうちの一つの多項式）ｍと量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化する、というように選択される。第一デジタル署名多項式ｕ１は、続いて、ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）として計算され、第二デジタル署名多項式ｖ１は、ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）として計算される。第二ランダム多項式ｒ２がまた選択されて、第三中間多項式ｔ２が、ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）として計算され、第四中間多項式ａ２が、ａ２のユークリッドノルムが
【数６】
2004526387.tif 000008
のオーダーであってメッセージ多項式の一つｍと量  ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化する、というように選択される。第三デジタル署名多項式ｕ２は、続いて、ｕ２＝ｒ２＋ａ２＊ｇ（ｍｏｄ  ｑ）として計算され、第四デジタル署名多項式ｖ２は、ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）として計算される。最後に、デジタル署名は、少なくとも、第一及び第三デジタル署名多項式ｕ１及びｕ２の各々のユークリッドノルムがＮのオーダーであることと、メッセージｍと第二及び第四デジタル署名多項式ｖ１及びｖ２の各々との間の偏差（deviation）が予め定められた偏差（deviation）の閾値よりも小さいことと、を確認することにより検証される。
【００１６】
本発明の別の実施の形態によれば、メッセージのデジタル署名を生成して検証するための装置が提供されている。ここで、前記デジタル署名は、一つ以上のデジタル署名多項式を含んでいる。前記装置は、環Ｒのイデアルｐ及びｑと、環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーを含んでいる。前記装置はまた、前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つとイデアルｐ及びｑの少なくとも一つとを用いて未規約化状態でのデジタル署名多項式が環Ｒ上の前記秘密鍵多項式の倍数ではないというようにデジタル署名多項式を生成するように、及び、前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差（deviation）の閾値よりも小さいことを少なくとも確認することによりデジタル署名を検証するように、機能し得るプロセッサーを含んでいる。
【００１７】
本発明の別の実施の形態によれば、メッセージのデジタル署名を生成して検証するための装置が提供されている。ここで、前記デジタル署名は、一つ以上のデジタル署名多項式を含んでいる。前記装置は、環Ｒのイデアルｐ及びｑと、環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーを含んでいる。前記装置はまた、前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つとイデアルｐ及びｑの少なくとも一つとを用いてデジタル署名多項式を生成するように、及び、前記デジタル署名多項式の少なくとも一つのノルムが予め定められたノルム閾値よりも小さいことを少なくとも確認することによりデジタル署名を検証するように、機能し得るプロセッサーを含んでいる。
【００１８】
本発明の別の実施の形態によれば、メッセージのデジタル署名を生成して検証するための装置が提供されている。ここで、前記デジタル署名は、一つ以上のデジタル署名多項式を含んでいる。前記装置は、環Ｒのイデアルｐ及びｑと、環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、補助的な多重利用の秘密情報と、を記憶するためのメモリーを含んでいる。前記装置はまた、前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つとイデアルｐ及びｑの少なくとも一つと補助的な多重利用秘密情報とを用いてデジタル署名多項式を生成するように、及び、前記デジタル署名多項式と前記公開鍵との間の偏差（deviation）が予め定められた関係を満たすことを少なくとも確認することによりデジタル署名を検証するように、機能し得るプロセッサーを含んでいる。
【００１９】
引き続いての本発明の好適な実施の形態の記述は、添付の図面を参照している。
【００２０】
図１は、本発明の一つの現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【００２１】
図２は、本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【００２２】
図３は、本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【００２３】
図４は、本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【００２４】
図５は、本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【００２５】
図６は、本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証するためのシステムを表すブロック図を示している。
【好適な実施の形態の詳細な説明】
【００２６】
添付の図面を参照して、図１は、本発明の一つの現時点での好適な実施の形態に係る、デジタル署名を生成し検証する方法を示すフロー図を示している。デジタル署名の生成における第一ステップ１０２は、環Ｒのイデアルｐ及びｑの選択である。好適には、ｐを法とした全ての操作は（−ｐ／２，ｐ／２］の範囲で実施され、ｑを法とした全ての操作は（−ｑ／２，ｑ／２］の範囲で実施される。一つの好適な環ＲはＺ［Ｘ］／（ＸＮ−１）である。ここで、Ｚは整数環であり、Ｎは１より大きい整数である。ステップ１０４において、秘密暗号鍵が選択される。前記秘密鍵は、前記環Ｒの一つ以上の多項式を含んでいる。好適には、前記秘密鍵は、前記環Ｒの二つの多項式ｆ及びｇを含んでいる。前記秘密鍵多項式は、また、行ベクトルとしても記述され得る：
【数７】
2004526387.tif 000009
【００２７】
パラメータＮ、ｐ及びｑは、公知である。好適には、ｐ及びｑは、互いに素な整数で、Ｎ／３＜ｑ＜２Ｎ／３  かつ  ｐ＜＜ｑ  である。例えば、（Ｎ，ｐ，ｑ）＝（２５１，３，１２８）が、公開パラメータ値の一つの好適な選択である。付加的な公開パラメータは、ＳｆとＳｇ（秘密鍵ｆ及びｇとして許容し得る多項式の空間）及びＳｒ（署名手続きの間に署名者が使用する中間多項式の空間）を含んでいる。これらの空間は、関連する多項式を（一様分布により選ばれたＺｑＮからのランダムベクトルと比べて）比較的短いユークリッド長を持つベクトルへと制約するよう設計されている。例えば、
【数８】
2004526387.tif 000010
のオーダーのユークリッドノルムを有する多項式を短いといい、Ｎのオーダーのユークリッドノルムを有する多項式をやや短いという。従って、二つの短い多項式の重畳（convolution）は、典型的には一つのやや短い多項式を生成する。好適には、短い及びやや短い多項式が、前記空間Ｓｆ、Ｓｇ及びＳｒに含まれている。
【００２８】
本発明の様々な実施の形態において使用され得る秘密鍵には、三つのタイプがある。第一の鍵のタイプ（これを鍵タイプＡとする）によれば、ｆ及びｇの両方が短い多項式である。第二の鍵のタイプ（これを鍵タイプＢとする）によれば、ｆ及びｇの両方が短い多項式であり、ある多項式ｋに対してｆ≡ｇ≡ｋ（ｍｏｄ  ｐ）である（即ち、ｆ、ｇ及びｋの係数群がｐを法として一致している）。第三の鍵のタイプは、ワンタイム秘密鍵ｅに主として用いられ、これを鍵タイプＣとする。鍵タイプＣによれば、ｅは短い多項式であるが、係数ｅ０はやや大きい（例えば、ｑ／２ｐ）。
【００２９】
前記秘密鍵の選択の後、ステップ１０６において公開鍵が生成される。好適には、公開鍵は、一つ以上の公開鍵多項式を含んでいる。例えば、秘密鍵が多項式ｆ及びｇを含んでいる場合、適切な公開鍵多項式ｈは、次の式を用いて生成され得る：
【数９】
2004526387.tif 000011
式２の多項式
【数１０】
2004526387.tif 000012
は、Ｒｑ＝Ｚｑ［Ｘ］／（ＸＮ−１）における多項式ｆの逆元を示す。「＊」は、Ｚ［Ｘ］／（ＸＮ−１）における、標準的な重畳（convolution）または多項式の積、を示す。
【数１１】
2004526387.tif 000013
一つ一つの署名のために新たな秘密鍵及び公開鍵を生成する必要はない。むしろ、秘密鍵が侵害されないかぎり、同一の秘密鍵及び公開鍵が多数のデジタル署名を生成し検証するために繰り返し用いられ得る。従って、秘密鍵多項式ｆ及びｇ、並びに公開鍵多項式ｈは、多重利用鍵であるといい得る。
【００３０】
選択的に、ステップ１０８において、補助的な多重利用秘密情報が選択される。補助的な多重利用秘密情報は、環Ｒの一つ以上の補助的な秘密多項式を含み得て、秘密鍵を補助するが、それ自身は秘密鍵に直接的に関係していない。前記補助的な多重利用秘密情報は、デジタル署名の生成において、当該署名が秘密鍵に関する有用な情報を漏洩するのを防ぐために利用され得る。このことは、秘密鍵に関する有用な情報を漏洩する署名の脆弱性を利用した二次の平均化攻撃（averaging attack）に対する防御を提供する。
【００３１】
ＮＳＳ署名に対する平均化攻撃（averaging attack）の使用は、ＮＳＳ暗号解析文献に記述されている。端的には、平均化攻撃（averaging attack）は、秘密鍵を、当該秘密鍵で署名された多数のデジタル署名の収束を解析することにより決定する。秘密鍵自身以外のデジタル署名の生成に用いられる要素は、ランダム又は公知であるであるため、同一の秘密鍵を用いて生成された一連の署名は当該秘密鍵に関連した値へと収束する。例えば、前記公知の要素はある公知の平均値へと収束し、前記ランダムの要素は多数の署名のサンプルにより予測可能となる。一連のデジタル署名多項式をそれらの逆多項式で乗算することにより、前記公知の平均値を取り除き得て、ｆ＊ｆｒｅｖを分離し得る。ｆ＊ｆｒｅｖは、当該秘密鍵に直接関係する情報を提供する。このようなタイプの、ある特定の秘密鍵を用いて作られた署名の複写（transcript）の解析により、秘密鍵についての情報を抽出し得て、究極的には、当該秘密鍵そのものを判定（決定）し得る。
【００３２】
本発明は、このようなタイプの平均化攻撃（averaging attack）への多重の防御を提供する。例えば、一つの防御は、ある一連の署名の収束値を操作することにより平均化攻撃（averaging attack）を欺くことに関連している。例えば、短いまたはやや短い多項式ｒが、ある固定の短いｆ’に対して、ｒ＝ａ’＊ｆ’というようにランダムに生成され得る。前記ベクトルｆ’は、秘密鍵の補完としての補助的な多重利用秘密情報であるが、秘密鍵又は公開鍵のいずれとも関連する必要が無く、好適には関連しない。従って、ある攻撃者が例えばｒ＋ａ＊ｆの形式の署名多項式の複写（transcript）に平均化攻撃（averaging attack）を実行した場合、当該攻撃者は、有用な値ｆ＊ｆｒｅｖではなく、ｆ＊ｆｒｅｖ＋ｆ’＊ｆ’ｒｅｖに関連する無用な値のみを復元し得る。
【００３３】
本発明による平均化攻撃（averaging attack）に対する防御のためのもう一つの方法は、適当な時間内で平均化攻撃（averaging attack）が収束しないようにすることである。例えば、ある中間秘密多項式
【数１２】
2004526387.tif 000014
が計算され得る。ここで、ｄは、もう一つのランダムで非常に短い多項式である。ｄ多項式は、ｆ＊ｆｒｅｖの収束を遅延させるノイズとしての役割を果たす。しかしながら、このような態様でのｄ多項式の使用は、関連するデジタル署名多項式により多くの偏差（deviation）をもたらす。従って、本アプローチは、好適には、以下により完全に記述されるように、偏差（deviation）の制約よりもユークリッドノルムの制約を用いてテストされる署名多項式に対して使用される。
【００３４】
図１に示した方法に戻って、一つ以上のメッセージ多項式がステップ１１０で生成される。本ステップは、メッセージ依存であって、新規のデジタル署名毎に繰り返されなければならない。好適には、メッセージ多項式は環Ｒ上にあり、このことは、秘密鍵及び公開鍵の多項式と関連したメッセージ多項式の便宜的な操作を可能とする。メッセージ多項式は、一つ以上のハッシュ関数を用いる公知の方法により生成され得る。
【００３５】
一つのワンタイム秘密鍵が、ステップ１１２において選択され得る。多重利用の秘密鍵と異なり、当該ワンタイム秘密鍵は、ただ一つの署名を生成するために用いられる。次の署名の生成には、新たなワンタイム秘密鍵が選択される。ワンタイム秘密鍵の選択は任意であるが、以下により完全に記述されるように、特に平均化攻撃（averaging attack）に関連して、デジタル署名のセキュリティを向上するために用いられ得る。
【００３６】
デジタル署名の生成は、ステップ１１４において実施される。好適には、デジタル署名は、メッセージ多項式及び秘密鍵多項式に基づき生成される一つ以上のデジタル署名多項式を含んでいる。デジタル署名は、選択的には、メッセージ多項式及び秘密鍵多項式に加えて、補助的な多重利用秘密情報及び／またはワンタイム秘密鍵を用いて生成され得る。
【００３７】
デジタル署名が生成されると、署名者は前記デジタル署名を伴ったメッセージを意図された受領者へと伝送する。当該受領者は、ステップ１１６において、前記デジタル署名を検証し得る。当該検証は、メッセージ、デジタル署名及び公開鍵の間の、一つ以上のタイプの比較を含み得る。ここで、前記公開鍵は、好適には、検証者に知られている。例えば、検証者は、デジタル署名多項式と公開鍵多項式との間において、予め定められた関係を確認し得る。加えて、検証者は、デジタル署名多項式とメッセージ多項式との間の偏差（deviation）が予め定められた偏差閾値と比べて小さいまたは等しいことを確認し得る。ａ，ｂ∈Ｚｑ［Ｘ］／（ＸＮ−１）に対して、ａとｂとの間の偏差（deviation）は次のように示される：
Ｄｅｖ（ａ，ｂ）＝＃｛ｉ：ｆｉ≠ｇｉ（ｍｏｄ  ｐ）｝    （４）
検証者は、また、一つ以上のデジタル署名多項式のノルムが、予め定められたノルム閾値と比べて小さいまたは等しいことを確認し得る。様々なノルム、例えばＬ１ノルム、Ｌ２（またはユークリッド）ノルムまたはより高次元のＬｐノルムのいずれかを含む、がデジタル署名多項式を制約するために使用され得る。便宜性のためには、ユークリッドノルムが好ましい。
【００３８】
ある署名を検証する過程で、検証者は、一般に、これらの比較のタイプのうち、二つの組み合わせまたは三つ全てを使用する。例えば、前記署名は、一般に、デジタル署名と公開鍵との間の予め定められた関係を確認すべきである。この第一のテストに加えて、前記検証者は、一般に、デジタル署名多項式に関して少なくとももう一つの別の比較（即ち、偏差（deviation）の制約及び／またはノルムの制約）を確認すべきである。本発明の様々な署名生成及び検証の手続きが、続いて、図２乃至図５に関連してより詳細に記述される。
【００３９】
図２は、本発明の他の一つの現時点での好適な実施の形態に係る、デジタル署名を生成し検証する方法を示すフロー図を示している。ステップ２０２において、一つの秘密鍵が選択される。好適には、前記秘密鍵は、鍵タイプＢであって、環Ｒの二つの短い多項式ｆ及びｇを含んでいる。ここで、ある多項式ｋについてｆ≡ｇ≡ｋ（ｍｏｄ  ｐ）である。前記秘密鍵に基づいて、一つの公開鍵が、ステップ２０４において生成される。前記公開鍵は、好適には、式２に従って計算される公開鍵多項式ｈを含んでいる。
【００４０】
一つ以上のメッセージ多項式ｍが、続いて、署名されるべきメッセージに基づいて、ステップ２０６において生成される。例えば、あるメッセージ多項式ｍは、好適には、あるハッシュ関数Ｈ（ｍ）を用いて計算される。ここで、Ｈは、安全なハッシュ関数（セキュアハッシュ関数）である。あるいは、前記メッセージ多項式は、二つの別々のハッシュ、Ｈ１（ｍ）及びＨ２（ｍ）、を含み得る。また、前記ハッシュ関数にランダム性が加えられ得る。例えば、あるメッセージ多項式が、Ｈ（ｍ，ｃ）として計算され得る。ここで、ｃは、署名の一部となるランダム値である。
【００４１】
選択的に、ステップ２０８において、一つのランダム秘密多項式ｒが、空間Ｓｒからｒ（１）＝０というように選択される。ｒをｒ（１）＝０というように選択することは必須ではないが、以下に説明する理由により好ましい。好適には、ｒはまた、短いまたはやや短い多項式であるべきである。ステップ２０８において一つのランダム秘密鍵ｒが選択された場合、続いてステップ２１０において、第一の中間秘密多項式ｓが次の式に従って計算される：
ｓ＝ｐｒ＊（１−ｈ）−１（ｍｏｄ  ｑ）    （５）
効率のため、パラメータ  （１−ｈ）−１  は、事前に計算されてｓ’として記憶され得る。ステップ２１２において、第二の中間秘密多項式ｔが次の式に従って計算される：
ｔ＝ｓ＊ｈ（ｍｏｄ  ｑ）    （６）
一般に、ｓ及びｔは、ｓ＊ｈ＝ｔであるように、かつ、ｓ及びｔがｐを法として実質的に一致するように、選択されるべきである。これは、式８及び式９で計算されるデジタル署名多項式ｕ及びｖの間の適正な公開鍵の関係を保持して、メッセージ多項式ｍとデジタル署名多項式ｕ及びｖとの間の偏差（deviation）の数を最小化するのを補助する。式５及び式６は、ｓとｔとの間の適正な関係を実現する一つの好適な方法を提供する。
【００４２】
第三の中間秘密多項式ａが、ステップ２１４において、次の式に従って計算される：
【数１３】
2004526387.tif 000015
一般に、第三の中間多項式ａは、ａが小さい多項式であって、かつ、メッセージ多項式ｍとデジタル署名多項式ｕ及び式９において計算されるｖとの間の偏差（deviation）を最小化するというように、選択されるべきである。式７は、ある適切な第三の中間多項式ａを計算する一つの好適な方法を提供する。
【００４３】
三つの中間秘密多項式ｓ、ｔ及びａの計算は、メッセージ多項式ｍからできるだけ少ない偏差（deviation）を生成するように意図されている。ｒ（１）＝０というようなランダム秘密多項式ｒの選択は、前述のように、ｓと  ｔ＝ｓ＊ｈ（ｍｏｄ  ｑ）＝ｓ−ｐｒ（ｍｏｄ  ｑ）  とがほぼ同じように偏差（deviate）する（即ち、ｓ及びｔが同一の係数の位置において偏差（deviate）している）ことを保証する。ｓ及びｔが同じように偏差（deviate）するならば、それらの偏差（deviation）は、式７に従って計算される中間秘密多項式ａを用いて直列的に修正され得る。
【００４４】
三つの中間秘密多項式が与えられると、第一のデジタル署名多項式ｕが、ステップ２１６において、次の式に従って生成される：
ｕ＝ｓ＋ａ＊ｆ（ｍｏｄ  ｑ）    （８）
第二のデジタル署名多項式ｖが、続いて、ステップ２１８において、次の式に従って生成される：
ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）    （９）
多項式のペア（ｕ，ｖ）が、当該メッセージの署名である。デジタル署名多項式ｕ及びｖの生成における秘密中間多項式ｓ及びｔの付加は、本発明がＮＳＳにおいて見られたセキュリティの欠陥の一つを克服する態様の一つである。これは、ＮＳＳ署名が単純にｑを法として規約化された秘密鍵多項式の積：（ｓ，ｔ）＝（ｆ＊ｗ，ｇ＊ｗ）（ｍｏｄ  ｑ）  であるからである。ここで、ｗは、ある短い乗数多項式である。結果として、ＮＳＳ署名は、ＮＳＳ暗号解析文献においてより詳細に記述されているように、攻撃者が秘密鍵ｆ及びｇを知ることを許容する成功的な攻撃にさらされてきた。署名多項式ｕ及びｖへ秘密中間多項式ｓ及びｔを付加することにより、本発明の本実施の形態は、ｕ及びｖが、未規約化状態（即ち、ｑを法とした規約化の前）において、環Ｒ上の秘密鍵多項式の積ではないことを、保証している。換言すれば、ｕ及びｖは、環Ｒｑ上で秘密鍵多項式ｆ及びｇにより除算されたとき、それぞれ、やや短いまたはより大きい多項式を生じる。本発明の他の実施の形態は、中間秘密多項式を同じ態様で用いる。
【００４５】
ｍまたはＨ（ｍ）の代わりに二つのハッシュＨ１（ｍ）及びＨ２（ｍ）が署名を生成するために用いられる場合、式５における項ｐｒは、Ｈ１（ｍ）−Ｈ２（ｍ）（ｍｏｄ  ｐ）  と一致する短いまたはやや短いランダム秘密多項式ｒに置換されるべきであって、ａは、式７の次の修正版に従って計算されるべきである：
【数１４】
2004526387.tif 000016
【００４６】
前述のようにデジタル署名を生成した後、前記署名者は、前記メッセージ、前記メッセージ多項式ｍ並びに前記デジタル署名多項式ｕ及びｖの一つまたは両方を、意図された受領者へと伝送する。前記受領検証者は、続いて、ステップ２２０において、少なくとも二つの比較を実施することにより、前記デジタル署名を検証し得る。集合的に、前記二つの比較を条件Ａという。第一の比較において、前記検証者は、前記デジタル署名多項式と前記署名者の公開鍵とが予め定められた関係  ｖ＝ｕ＊ｈ（ｍｏｄ  ｑ）  を満たすことを確認する。あるいは、前記署名者が前記デジタル署名多項式のうち一つのみ、例えばｕ、を伝送した場合、前記検証者は他のデジタル署名多項式ｖを前述の予め定められた関係に従って計算し得る。この代替の方法は、一般に本発明の様々な実施の形態に適応されるが、伝送されるデジタル署名のサイズを削減することによって伝送効率を向上させる。いずれの場合にも、前記検証者は、条件Ａを完全に満たすべく第二の比較を実施することを要求される。
【００４７】
第二の比較において、前記検証者は、前記メッセージ多項式ｍと第一及び第二のデジタル署名多項式ｕ及びｖの各々との間の偏差（deviation）が、予め定められた偏差閾値よりも小さいことを確認する。二つの異なるハッシュＨ１（ｍ）及びＨ２（ｍ）が署名多項式を生成するために用いられる場合、ｕはＨ１（ｍ）からの偏差（deviation）のために調査されるべきであり、ｖはＨ２（ｍ）からの偏差（deviation）のために調査されるべきである。例えば多項式あたりＮ／５の係数（即ち、Ｎ＝２５１に対して約５０の偏差（deviation））という偏差閾値、が、前述のようにＮＳＳ署名を偽造するのに成功していた偽造攻撃の可能性を顕著に削減するために、選択され得る。比較の両方が満たされた場合、前記検証者は、署名が真正であると判断する。
【００４８】
セキュリティを更に向上するために、前記偏差閾値は、更に低く設定され得る。実験結果は、本発明のこの特別な実施の形態が、Ｎ／８未満の偏差（deviation）（即ち、Ｎ＝２５１に対して３１未満の偏差（deviation））のデジタル署名を、署名者の秘密鍵に関する有用な情報を漏洩することなく、確実に生成可能であることを示している。本発明の他の実施の形態は、前記偏差閾値の更なる低減を考慮する。そのような他の実施の形態の一つが、図３に関連して記述される。
【００４９】
図３は、本発明の他の一つの現時点での好適な実施の形態に係る、デジタル署名を生成し検証する方法を示すフロー図を示している。ステップ３０２において、一つの秘密鍵が選択される。好適には、前記秘密鍵は、鍵タイプＡであって、二つの短い多項式ｆ及びｇを含んでいる。鍵タイプＡの多項式は、鍵タイプＢの多項式よりも短く（即ち、ユークリッドノルムがより小さく）なり得ることに留意されたい。これは、鍵タイプＢの多項式が、互いに等しくあってはならず、かつ同時に、ｐを法として一致していなければならない、からである。結果として、鍵タイプＢの秘密鍵多項式の一つは、必然的に、より大きい大きさの係数を有さなくてはならない。このことは、鍵タイプＡの多項式には要求されない。鍵タイプＡのより短い秘密鍵多項式は、従って、ｑを法とした規約化によってより少ない影響を受けて、故に、鍵タイプＡの多項式から生成されたデジタル署名多項式は、結局、メッセージ多項式との間により少ない偏差（deviation）を有する。
【００５０】
ステップ３０４において、一つの公開鍵が生成される。前述の実施の形態のように、前記公開鍵は、好適には、式２によって計算される公開鍵多項式ｈを含んでいる。一つ以上のメッセージ多項式ｍが、続いて、ステップ３０６において署名されるべきメッセージに基づいて生成される。例えば、前述のように、メッセージ多項式ｍは、好適には、ハッシュ関数Ｈ（ｍ）を用いて計算される。あるいは、前記メッセージ多項式は、二つの別々のハッシュＨ１（ｍ）及びＨ２（ｍ）を含み得る。更に、前記ハッシュ関数にはランダム性が付加され得る。例えば、メッセージ多項式ｍは、Ｈ（ｍ，ｃ）として計算され得る。ここで、ｃは、当該署名の一部となるランダム値である。
【００５１】
ステップ３０８において、一つのランダム秘密多項式ｒが空間Ｓｒから選択される。好適には、前記多項式ｒは短いまたはやや短い。ステップ３１０において、第一の中間秘密多項式ｔは次の式に従って計算される：
ｔ＝ｒ＊ｈ（ｍｏｄ  ｑ）    （１１）
【００５２】
ステップ３１２において、第二の中間秘密多項式ａが、続いて、次の式に従って計算される：
【数１５】
2004526387.tif 000017
後述される検証条件と一致して、第二の中間秘密多項式ａは、短くあるように計算され、二つの中間秘密多項式ｔ及びａの計算は、式１４に従って計算される第二のデジタル署名多項式ｖとメッセージ多項式ｍとの間の偏差（deviation）を可能な限り小さくするように意図されている。
【００５３】
前記二つの中間秘密多項式が与えられると、第一のデジタル署名多項式ｕが、ステップ３１４において次の式に従って生成される：
ｕ＝ｒ＋ａ＊ｆ（ｍｏｄ  ｑ）    （１３）
第二のデジタル署名多項式ｖは、続いて、ステップ３１６において次の式に従って生成される：
ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）    （１４）
前記多項式のペア（ｕ，ｖ）が、前記メッセージの署名である。前記署名を生成するために、二つのハッシュＨ１（ｍ）及びＨ２（ｍ）がｍの代わりに用いられた場合、ａは、式１２の次の修正版に従って計算されるべきである：
【数１６】
2004526387.tif 000018
【００５４】
前述のようにデジタル署名を生成した後、前記署名者は、前記メッセージ、前記メッセージ多項式ｍ並びに前記デジタル署名多項式ｕ及びｖを意図された受領者へと伝送する。前記受領検証者は、続いて、ステップ３１８において、三つの比較を実施することにより、前記デジタル署名を検証し得る。集合的に、前記三つの比較を条件Ｂという。第一に、前記検証者は、前記デジタル署名多項式と前記署名者の公開鍵とが予め定められた関係  ｖ＝ｕ＊ｈ（ｍｏｄ  ｑ）  を満たすことを確認する。第二に、前記検証者は、前記第一のデジタル署名多項式ｕがやや短いということを確認する。第三に、前記検証者は、前記メッセージ多項式ｍと第二のデジタル署名多項式ｖとの間の偏差（deviation）が、予め定められた偏差閾値よりも小さいことを確認する。三つの比較の各々が満たされた場合、前記検証者は、署名が真正であると判断する。
【００５５】
二つの異なるハッシュＨ１（ｍ）及びＨ２（ｍ）が署名多項式を生成するために用いられる場合、ｖはＨ２（ｍ）からの偏差（deviation）のために調査されるべきであり、ｕについてのユークリッドノルムの制約が、微分多項式  ｄ＝ｕ−Ｈ１（ｍ）  がやや短いことを確認することにより、調査されるべきである。
【００５６】
本実施の形態によると、第二のデジタル署名多項式ｖのみが、メッセージ多項式ｍに対する偏差（deviation）の条件を満たさなければならない、ということに留意されたい。これは、第一のデジタル署名多項式ｕが、単独で、ｕがやや短いことを要求する第二の比較によって制約されているからである。このように、条件Ｂは条件Ａと比較して、その偏差閾値が局所的基準であることから、より厳密な基準のセットである。それは、攻撃者に多数の係数位置を無視することを許容する。前記ユークリッドノルム閾値は、反対に、大局的基準であり、それは全ての係数によって強く影響される。
【００５７】
前述の実施の形態のように、例えば多項式あたりＮ／５の係数（即ち、Ｎ＝２５１に対して約５０の偏差（deviation））という偏差閾値が、前述のようにＮＳＳ署名を偽造するのに成功していた偽造攻撃の可能性を顕著に削減するために、選択され得る。セキュリティを更に向上するために、前記偏差閾値は、更に低く設定され得る。実験結果は、本発明のこの特別な実施の形態が、Ｎ／１２以下の偏差（deviation）（即ち、Ｎ＝２５１に対して２０以下の偏差（deviation））のデジタル署名を、署名者の秘密鍵に関する有用な情報を漏洩することなく、確実に生成可能であることを示している。図４を参照して記述される次の実施の形態は、同様に、安全な署名を実現することが可能である。
【００５８】
図４は、本発明の他の一つの現時点での好適な実施の形態に係る、デジタル署名を生成し検証する方法を示すフロー図を示している。ステップ４０２において、一つの秘密鍵が選択される。前述の実施の形態と同様に、好適には、前記秘密鍵は、鍵タイプＡであって、二つの短い多項式ｆ及びｇを含んでいる。一つのワンタイム秘密鍵多項式ｅが、続いて、ステップ４０４において生成される。ｆ、ｇ及びｅを与えられると、ワンタイム公開鍵多項式ｈ１及びｈ２の一つのペアが、好適には、ステップ４０６において次の式に従って生成される：
ｈ１＝ｆ−１＊ｅ（ｍｏｄ  ｑ）    （１６）
ｈ２＝ｇ−１＊ｅ（ｍｏｄ  ｑ）    （１７）
あるいは、ｈ１及びｈ２は、次の式に従って生成され得る：
ｈ１＝ｅ−１＊ｆ（ｍｏｄ  ｑ）    （１８）
ｈ２＝ｅ−１＊ｇ（ｍｏｄ  ｑ）    （１９）
式１８及び式１９は、ｈ１及びｈ２の適切な多項式を算出するが、途中でワンタイム秘密鍵の逆元ｅ−１（ｍｏｄ  ｑ）の計算を要求する。加えて、式１８及び式１９の利用は、後述の式２１乃至式２３及び式２５乃至式２７と同様のｅ、ｆ及びｇの代入を要求する。
【００５９】
本実施の形態による署名の生成に使用される前記ワンタイム公開鍵多項式ｈ１及びｈ２は、各々の新たな署名ごとに異なるが、前記署名の検証に用いられる多重利用の公開鍵多項式ｈは同一なままである。
【００６０】
一つ以上のメッセージ多項式ｍが、続いて、ステップ４０８において署名されるべきメッセージに基づいて生成される。例えば、前述のように、メッセージ多項式ｍは、好適には、一つのハッシュ関数Ｈ（ｍ）を用いて計算される。ここで、Ｈは、安全なハッシュ関数（セキュアハッシュ関数）である。あるいは、前記メッセージ多項式は、二つの別々のハッシュ、Ｈ１（ｍ）及びＨ２（ｍ）、を含み得る。また、前記ハッシュ関数にランダム性が加えられ得る。例えば、あるメッセージ多項式ｍが、Ｈ（ｍ，ｃ）として計算され得る。ここで、ｃは、署名の一部となるランダム値である。
【００６１】
ステップ４１０において、第一のランダム秘密多項式ｒ１が空間Ｓｒから選択される。好適には、多項式ｒ１は、短いかまたはやや短い。ステップ４１２において、第一の中間秘密多項式ｔ１が、次の式に従って計算される：
ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）    （２０）
続いて、ステップ４１４において、第二の中間秘密多項式ａ１が、次の式に従って計算される：
【数１７】
2004526387.tif 000019
【００６２】
初めの二つの中間秘密多項式を与えられると、第一のデジタル署名多項式ｕ１が、ステップ４１６において、次の式に従って生成される：
ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）    （２２）
第二のデジタル署名多項式ｖ１が、続いて、ステップ４１８において、次の式に従って生成される：
ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）    （２３）
【００６３】
ステップ４２０において、第二のランダム秘密多項式ｒ２が空間Ｓｒから選択される。好適には、多項式ｒ２は、短いかまたはやや短い。ステップ４２２において、第三の中間秘密多項式ｔ２が、次の式に従って計算される：
ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）    （２４）
ステップ４２４において、第四の中間秘密多項式ａ２が、次の式に従って計算される：
【数１８】
2004526387.tif 000020
前述四個の中間秘密多項式ｔ１、ｔ２、ａ１及びａ２の計算は、メッセージ多項式ｍからできるだけ少ない偏差（deviation）を生成するように意図されている。
【００６４】
第三及び第四の中間秘密多項式を与えられると、第三のデジタル署名多項式ｕ２が、ステップ４２６において、次の式に従って生成される：
ｕ２＝ｒ２＋ａ２＊ｇ（ｍｏｄ  ｑ）    （２６）
第四のデジタル署名多項式ｖ２が、続いて、ステップ４２８において、次の式に従って生成される：
ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）    （２７）
集合的に、四つのデジタル署名多項式（ｕ１，ｕ２，ｖ１，ｖ２）が当該メッセージの署名を構成する。
【００６５】
前述のようにデジタル署名を生成した後、前記署名者は、前記メッセージ、前記メッセージ多項式ｍ並びに前記デジタル署名多項式ｕ１、ｕ２、ｖ１及びｖ２を意図された受領者へと伝送する。前記受領検証者は、続いて、ステップ４３０において、前述の実施の形態において記述された３つの条件Ｂの比較の修正版を実施することにより、前記デジタル署名を検証し得る。第一に、前記検証者は、前記デジタル署名多項式と前記署名者の多重利用の公開鍵とが予め定められた関係
【数１９】
2004526387.tif 000021
を満たすことを確認する。第二に、前記検証者は、前記第一及び第三のデジタル署名多項式ｕ１及びｕ２の各々がやや短いということを確認する。第三に、前記検証者は、前記メッセージ多項式ｍと第二及び第四のデジタル署名多項式ｖ１及びｖ２の各々との間の偏差（deviation）が、予め定められた偏差閾値よりも小さいことを確認する。二つの異なるハッシュＨ１（ｍ）及びＨ２（ｍ）が署名多項式を生成するために用いられる場合、ｖ１はＨ１（ｍ）からの偏差（deviation）を調査されるべきであり、ｖ２はＨ２（ｍ）からの偏差（deviation）を調査されるべきである。前記の三つの比較の各々が満たされた場合、前記検証者は、署名が真正であると判断する。
【００６６】
本実施の形態によると、第二及び第四のデジタル署名多項式ｖ１及びｖ２のみが、メッセージ多項式ｍとの間の偏差（deviation）のために比較される必要がある、ということに留意されたい。これは、前述の実施の形態と同様に、第一及び第三のデジタル署名多項式ｕ１及びｕ２が、単独で、第二の比較によって制約されているからである。前記第二の比較は、より厳密なユークリッドノルム閾値であって、ｕ１及びｕ２の両方がやや短いことを要求する。加えて、本実施の形態におけるワンタイム秘密鍵の利用は、前記デジタル署名を平均化攻撃（averaging attack）から防御する。前記平均化攻撃は、ＮＳＳ署名の秘密鍵を明かすのに利用されてきた。前記ワンタイム秘密鍵は、平均化攻撃（averaging attack）を未然に防ぐように設計されている。前記ｖ多項式はワンタイム（一度限り利用の）秘密鍵のみに関連していることから、これらの多項式に関する平均化攻撃（averaging attack）は、有用な暗号解析情報を何も明かさない。平均化攻撃（averaging attack）は、必然的に、前記ｕ多項式の暗号解析に限定される。
【００６７】
前記ｕ多項式への平均化攻撃（averaging attack）に対する更なる防御のために、デジタル署名多項式の生成において、補助的な多重利用秘密多項式ｆ’及びｇ’が含まれ得る。特に、ｒ１はｒ１＝ａ１’＊ｆ’として計算され得て、ｒ２はｒ２＝ａ２’＊ｇ’として計算され得る。前述のように、補助的な多重利用秘密多項式ｆ’及びｇ’の利用は、デジタル署名多項式の複写（transcript）の収束値を操作し、平均化攻撃（averaging attack）を用いて秘密鍵多項式ｆ及びｇに関する有用な情報を取得することを顕著に困難にする。更なる防御の手段として、一つより多い補助的な多重利用秘密多項式が、各々のデジタル署名多項式を生成するために使用され得る。例えば、ｒ１はｒ１＝ａ１’＊ｆ’＋ａ１’’＊ｆ’’として計算され得て、ｒ２はｒ２＝ａ２’＊ｇ’＋ａ２’’＊ｇ’’として計算され得る。
【００６８】
偏差（deviation）の制約に関して、前述の実施の形態のように、例えば多項式あたりＮ／５の係数（即ち、Ｎ＝２５１に対して約５０の偏差（deviation））という閾値が、前述のようにＮＳＳ署名を偽造するのに成功していた偽造攻撃の可能性を顕著に削減するために、選択され得る。セキュリティを更に向上するために、前記偏差閾値は、更に低く設定され得る。実験結果は、前述の実施の形態と同様に、本発明のこの実施の形態が、Ｎ／１２以下の偏差（deviation）（即ち、Ｎ＝２５１に対して２０以下の偏差（deviation））のデジタル署名を、署名者の秘密鍵に関する有用な情報を漏洩することなく、確実に生成可能であることを示している。図５を参照して記述される次の実施の形態は、許容可能な偏差（deviation）の数を更に削減することにより、更に高い程度の安全性を提供する。
【００６９】
図５は、本発明の他の一つの現時点での好適な実施の形態に係る、デジタル署名を生成し検証する方法を示すフロー図を示している。ステップ５０２において、一つの秘密鍵が選択される。前述の実施の形態と同様に、好適には、前記秘密鍵は、鍵タイプＡであって、二つの短い多項式ｆ及びｇを含んでいる。好適には鍵タイプＣの一つのワンタイム秘密鍵多項式ｅが、続いて、好適には第一の係数ｅ０がやや大きい（例えば、ｑ／２ｐ）というように、ステップ５０４において生成される。ｆ、ｇ及びｅを与えられると、公開鍵多項式ｈ１及びｈ２の一つのペアが、好適には、ステップ５０６において、式１６及び式１７に従って生成される。一方、ｈ１及びｈ２はまた、式１８及び式１９に従っても生成され得る。
【００７０】
前述の実施の形態に関連して記述されたように、署名の生成に使用されるワンタイム公開鍵多項式ｈ１及びｈ２は各々の新たな署名ごとに異なるが、前記署名の検証に用いられる多重利用の公開鍵多項式ｈは同一なままである。
【００７１】
一つ以上のメッセージ多項式ｍが、続いて、ステップ５０８において署名されるべきメッセージに基づいて生成される。例えば、前述のように、メッセージ多項式ｍは、好適には、一つのハッシュ関数Ｈ（ｍ）を用いて計算される。ここで、Ｈは、安全なハッシュ関数（セキュアハッシュ関数）である。あるいは、前記メッセージ多項式は、二つの別々のハッシュＨ１（ｍ）及びＨ２（ｍ）を含み得る。更に、前記ハッシュ関数にはランダム性が付加され得る。例えば、あるメッセージ多項式ｍは、Ｈ（ｍ，ｃ）として計算され得る。ここで、ｃは、当該署名の一部となるランダム値である。
【００７２】
ステップ５１０において、第一のランダム秘密多項式ｒ１が空間Ｓｒから選択される。好適には、前記多項式ｒ１は短いまたはやや短い。ステップ５１２において、第一の中間秘密多項式ｔ１が次の式に従って計算される：
ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）    （２８）
ステップ５１４において、第二の中間秘密多項式ａ１が、短くあるべきであるが、量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  のメッセージｍからの偏差（deviation）が少ないまたはない、というように選択される。より具体的には、ａ１の係数群は、式３０を用いて後記のように計算されるｖ１がｐを法としてのメッセージ多項式ｍからの偏差（deviation）を少なく有するまたは全く有しない、というように選択される。加えて、ワンタイム秘密鍵ｅのやや大きい係数ｅ０は、量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  の係数群が区間  （−ｑ／２，ｑ／２）  の中心に近い、というように選択され得る。このことは、これらの係数群がｑを法とした操作において規約化されることを防ぐことを助け、それによって更に、ｐを法とした偏差（deviation）の可能性も低減する。
【００７３】
初めの二つの中間秘密多項式ｔ１及びａ１を与えられると、第一のデジタル署名多項式ｕ１が、ステップ５１６において、次の式に従って生成される：
ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）    （２９）
第二のデジタル署名多項式ｖ１が、続いて、ステップ５１８において、次の式に従って生成される：
ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）    （３０）
【００７４】
ステップ５２０において、第二のランダム秘密多項式ｒ２が空間Ｓｒから選択される。好適には、多項式ｒ２は、短いかまたはやや短い。続いてステップ５２２において、第三の中間秘密多項式ｔ２が、次の式に従って計算される：
ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）    （３１）
ステップ５２４において、第四の中間秘密多項式ａ２が、短くあるべきであるが、量  ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）  のメッセージｍからの偏差（deviation）が少ないまたはない、というように選択される。これは、ステップ５１４においてａ１に関連して記述されたものと同様の態様で達成される。多項式ａ１及びａ２並びに係数ｅ０の値の選択において、第二及び第四のデジタル署名多項式ｖ１及びｖ２の偏差（deviation）を防ぐことに主眼が置かれる。ｕ１及びｕ２がやや短いことを保証するためにａ１及びａ２は短い多項式であらなければならないが、ｕ１及びｕ２の検証の制約はそれらのｍからの偏差（deviation）よりむしろそれらのユークリッドノルムに依存するため、ｕ１またはｕ２の偏差を防ぐ必要性はない。このことは、多項式ｖ１及びｖ２の係数の極めて正確な操作を見込み、ｖ１及びｖ２の偏差を効果的に防ぐことを可能とする。
【００７５】
第三及び第四の中間秘密多項式を与えられると、第三のデジタル署名多項式ｕ２が、ステップ５２６において、次の式に従って生成される：
ｕ２＝ｒ２＋ａ２＊ｆ（ｍｏｄ  ｑ）    （３２）
第四のデジタル署名多項式ｖ２が、続いて、ステップ５２８において、次の式に従って生成される：
ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）    （３３）
集合的に、四つのデジタル署名多項式（ｕ１，ｕ２，ｖ１，ｖ２）が当該メッセージの署名を構成する。
【００７６】
前述のようにデジタル署名を生成した後、前記署名者は、前記メッセージ、前記メッセージ多項式ｍ並びに前記デジタル署名多項式ｕ１、ｕ２、ｖ１及びｖ２を意図された受領者へと伝送する。前記受領検証者は、続いて、ステップ５３０において、前述の実施の形態において用いられたものと同一の３つの修正された条件Ｂの比較を実施することにより、前記デジタル署名を検証し得る。第一に、前記検証者は、前記デジタル署名多項式と前記署名者の多重利用の公開鍵とが予め定められた関係
【数２０】
2004526387.tif 000022
を満たすことを確認する。第二に、前記検証者は、前記第一及び第三のデジタル署名多項式ｕ１及びｕ２の各々がやや短いということを確認する。第三に、前記検証者は、前記メッセージｍと第二及び第四のデジタル署名多項式ｖ１及びｖ２の各々との間の偏差（deviation）が、予め定められた偏差閾値よりも小さいことを確認する。三つの比較の全てが満たされた場合、前記検証者は、署名が真正であると判断する。
【００７７】
本実施の形態によると、第二及び第四のデジタル署名多項式ｖ１及びｖ２のみが、メッセージとの間の偏差（deviation）のために比較される必要がある、ということに留意されたい。これは、前述の実施の形態と同様に、第一及び第三のデジタル署名多項式ｕ１及びｕ２が、単独で、第二の比較によって制約されているからである。前記第二の比較は、より厳密なユークリッドノルム閾値であって、ｕ１及びｕ２の両方がやや短いことを要求する。加えて、本実施の形態におけるワンタイム秘密鍵ｅの利用は、前述の実施の形態に関連してより完全に記述されたように、それを平均化攻撃（averaging attack）から防御する。
【００７８】
平均化攻撃（averaging attack）に対する更なる防御のために、前述の実施の形態と同様に、デジタル署名多項式の生成において、補助的な多重利用秘密多項式ｆ’及びｇ’が含まれ得る。特に、ｒ１はｒ１＝ａ１’＊ｆ’として計算され得て、ｒ２はｒ２＝ａ２’＊ｇ’として計算され得る。前述のように、補助的な多重利用秘密多項式ｆ’及びｇ’の利用は、デジタル署名多項式の複写（transcript）の収束値を操作し、平均化攻撃（averaging attack）を用いて秘密鍵多項式ｆ及びｇに関する有用な情報を取得することを顕著に困難にする。更なる防御の手段として、一つより多い補助的な多重利用秘密多項式が、各々のデジタル署名多項式を生成するために使用され得る。例えば、ｒ１はｒ１＝ａ１’＊ｆ’＋ａ１’’＊ｆ’’として計算され得て、ｒ２はｒ２＝ａ２’＊ｇ’＋ａ２’’＊ｇ’’として計算され得る。
【００７９】
前述の実施の形態と同様に、例えば多項式あたりＮ／５の係数（即ち、Ｎ＝２５１に対して約５０の偏差（deviation））という偏差閾値が、前述のようにＮＳＳ署名を偽造するのに成功していた偽造攻撃の可能性を顕著に削減するために、選択され得る。セキュリティを更に向上するために、前記偏差閾値は、更に低く設定され得る。多項式ａ１及びａ２並びに係数ｅ０の正確な制御が可能であることに大きく起因して、実験結果は、本発明のこの実施の形態が、Ｎ／１００以下の偏差（deviation）（即ち、Ｎ＝２５１に対して２以下の偏差（deviation））のデジタル署名を、署名者の秘密鍵に関する有用な情報を漏洩することなく、確実に生成可能であることを示している。実際に、本実施の形態において注意深くａ１、ａ２及びｅ０を選択することによって、署名者は、全く偏差（deviation）のないデジタル署名を、それでもなお秘密鍵に関する有用な情報を漏洩することなく、確実に生成し得る。
【００８０】
本発明によるデジタル署名を生成し検証する様々な方法が記述されてきた。これらの方法を本発明の別の実施の形態に従って実践するためのシステムが、図６に関連して記述される。このシステムは、複数の利用者６０２、６０４、６０６、６０８を含んでいる。前記利用者の各々は、署名者及び／または検証者の役割を果たし得る。各々の利用者は、メモリー６１２と双方向に通信するプロセッサー６１０を含んでいる。前記プロセッサー６１０は、前述の手続きを実施するために、また、別の利用者へ伝送すべき情報を生成するために、適切なプログラムコードを実行する。適切なプログラムコードは、公知の方法によって作成され得る。メモリー６１２は、プログラムコードのみでなく、中間結果や、デジタル署名の生成及び検証の手続きの実施の間に使用される他の情報を記憶する。
【００８１】
通信ネットワーク６２０が提供され、利用者は当該通信ネットワーク上で通信し得る。通信ネットワーク６２０は、例えば、適切な通信ネットワークを提供する、ＬＡＮコンピュータネットワーク、ＷＡＮコンピュータネットワーク及び／または携帯電話ネットワークを含む、様々な一般的な形態であり得る。
【００８２】
本発明によると、利用者６０２は、デジタル署名を生成し通信ネットワーク６２０を介して利用者６０８へと伝送し得る。利用者６０８は、続いて、利用者６０２の署名を前述の手続きに従って検証し得る。利用者６０４及び利用者６０６は、通信ネットワーク６２０を介して同様の態様で通信し得る。加えて、利用者６０４及び利用者６０６は、図６に示されるように適切な直接の通信リンクを介してお互いに直接的に通信し得る。
【００８３】
信頼される認証局６３０が、様々な利用者６０２、６０４、６０６、６０８と関連付けられた公開鍵を記憶及び分配するために設けられる。例えば、利用者６０８からの署名を検証する前に、利用者６０２は、前述の検証手続きにおいて使用される利用者６０８の公開鍵のコピーを提供することを、認証局６３０へ要求し得る。
【００８４】
本発明は、特に好適な実施の形態及び例図に関連して詳細に記述されてきたが、本発明の趣旨及び範囲内において変形や修正が行われ得ることが理解される。
【図面の簡単な説明】
【００８５】
【図１】本発明の一つの現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【図２】本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【図３】本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【図４】本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【図５】本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証する方法を示すフロー図を示している。
【図６】本発明の別の現時点での好適な実施の形態に係るデジタル署名を生成し検証するためのシステムを表すブロック図を示している。
【図１】
2004526387.tif 000036
【図２】
2004526387.tif 000037
【図３】
2004526387.tif 000038
【図４】
2004526387.tif 000039
【図５】
2004526387.tif 000040
【図６】
2004526387.tif 000041
【国際公開パンフレット】
2004526387.tif 000042
2004526387.tif 000043
2004526387.tif 000044
2004526387.tif 000045
2004526387.tif 000046
2004526387.tif 000047
2004526387.tif 000048
2004526387.tif 000049
2004526387.tif 000050
2004526387.tif 000051
2004526387.tif 000052
2004526387.tif 000053
2004526387.tif 000054
2004526387.tif 000055
2004526387.tif 000056
2004526387.tif 000057
2004526387.tif 000058
2004526387.tif 000059
2004526387.tif 000060
2004526387.tif 000061
2004526387.tif 000062
2004526387.tif 000063
2004526387.tif 000064
2004526387.tif 000065
2004526387.tif 000066
2004526387.tif 000067
2004526387.tif 000068
2004526387.tif 000069
2004526387.tif 000070
2004526387.tif 000071
2004526387.tif 000072
2004526387.tif 000073
2004526387.tif 000074
2004526387.tif 000075
2004526387.tif 000076
2004526387.tif 000077
2004526387.tif 000078
2004526387.tif 000079
2004526387.tif 000080
2004526387.tif 000081
2004526387.tif 000082
2004526387.tif 000083
2004526387.tif 000084
2004526387.tif 000085
2004526387.tif 000086
2004526387.tif 000087
2004526387.tif 000088
2004526387.tif 000089
2004526387.tif 000090
2004526387.tif 000091
2004526387.tif 000092
2004526387.tif 000093
2004526387.tif 000094
2004526387.tif 000095
【国際調査報告】
2004526387.tif 000096
2004526387.tif 000097