【手続補正書】
【提出日】平成17年2月21日(2005.2.21)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
環Ｒの互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択する工程と、
前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成する工程と、
前記メッセージに基づいて一つ以上のメッセージ多項式を生成する工程と、
前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
を用いて、未規約化状態での前記デジタル署名多項式が前記環Ｒの前記秘密鍵多項式の倍数ではないというように、生成する工程と、
前記デジタル署名を、少なくとも、前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差閾値よりも小さいことを確認することにより、検証する工程と、
を備えた方法。
【請求項２】
前記環Ｒは、Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）であって、Ｎは１より大きい整数であり、
前記予め定められた偏差閾値は、Ｎ／５以下である
ことを特徴とする請求項１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３】
前記予め定められた偏差閾値は、ゼロに等しい
ことを特徴とする請求項１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
環Ｒの互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択する工程と、
前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成する工程と、
前記メッセージに基づいて一つ以上のメッセージ多項式を生成する工程と、
前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
を用いて生成する工程と、
前記デジタル署名を、少なくとも、前記デジタル署名多項式の少なくとも一つと関連付けられたノルムが予め定められたノルム閾値よりも小さいことを確認することにより、検証する工程と、
を備えた方法。
【請求項５】
前記デジタル署名多項式の少なくとも一つと関連付けられたノルムは、少なくとも一つのデジタル署名多項式のノルムである
ことを特徴とする請求項４に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項６】
前記メッセージ多項式の一つを前記デジタル署名多項式の一つから差し引くことにより微分多項式を計算する工程を更に備えると共に、
前記少なくとも一つのデジタル署名多項式に関連付けられたノルムは、前記微分多項式のノルムである
ことを特徴とする請求項４に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項７】
前記ノルムは、ユークリッドノルムであり、
前記予め定められたノルム閾値は、Ｎのオーダーである
ことを特徴とする請求項４に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項８】
前記デジタル署名多項式の生成は、更に、
（ｄ）一つ以上のランダム秘密多項式
を用いることを含む
ことを特徴とする請求項１または４に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項９】
ワンタイム秘密鍵を選択する工程を更に備えると共に、
前記デジタル署名多項式の生成は、更に、
（ｄ）前記ワンタイム秘密鍵
を用いることを含む
ことを特徴とする請求項１または４に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１０】
前記検証は、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを確認する工程を更に有する
ことを特徴とする請求項１または４に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１１】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
環Ｒのイデアルｐ及びｑを選択する工程と、
前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択する工程と、
前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成する工程と、
前記メッセージに基づいて一つ以上のメッセージ多項式を生成する工程と、
補助的な多重利用秘密情報を選択する工程と、
前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
（ｄ）前記補助的な多重利用秘密情報
を用いて生成する工程と、
前記デジタル署名を、少なくとも、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを確認することにより、検証する工程と、
を備えた方法。
【請求項１２】
前記環Ｒは、Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）であって、Ｎは１より大きい整数である
ことを特徴とする請求項１、４または１１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１３】
前記補助的な多重利用秘密情報は、前記環Ｒの一つ以上の補助的な秘密鍵多項式を含む
ことを特徴とする請求項１１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１４】
前記デジタル署名多項式の生成は、
前記デジタル署名多項式への二次の平均化攻撃（averaging attack）が前記補助的な秘密鍵多項式に依存した値に収束するというように、前記補助的な秘密鍵多項式を用いて一つ以上の前記デジタル署名多項式を調整する工程
を更に有することを特徴とする請求項１３に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１５】
前記デジタル署名多項式の検証は、
前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が、予め定められた偏差閾値よりも小さいことを確認する工程
を更に有することを特徴とする請求項１１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１６】
前記デジタル署名多項式の検証は、
前記デジタル署名多項式の少なくとも一つのノルムが予め定められたノルム閾値よりも小さいことを確認する工程
を更に有することを特徴とする請求項１１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１７】
前記メッセージ多項式は、前記メッセージに一つ以上のハッシュ関数を施すことにより生成される
ことを特徴とする請求項１、４または１１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１８】
前記デジタル署名多項式の生成は、更に、
（ｅ）一つ以上のランダム秘密多項式
を用いることを含む
ことを特徴とする請求項１１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項１９】
ワンタイム秘密鍵を選択する工程を更に備えると共に、
前記デジタル署名多項式の生成は、更に、
（ｅ）前記ワンタイム秘密鍵
を用いることを含む
ことを特徴とする請求項１１に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２０】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は二つのデジタル署名多項式ｕ及びｖを含んでおり、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵を選択する工程と、
【数１】
2004526387.tif 000001
を計算する工程と、
前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成する工程と、
第一中間秘密多項式ｓ及び第二中間秘密多項式ｔを、ｓ＊ｈ＝ｔであるように、また、ｓ及びｔがｐを法として実質的に一致するように、選択する工程と、
第三の中間秘密多項式ａを、前記メッセージ多項式ｍの一つと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように、選択する工程と、
前記第一デジタル署名多項式ｕ＝ｓ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算する工程と、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算する工程と、
前記デジタル署名を、少なくとも、前記メッセージ多項式ｍの一つ以上と前記第一デジタル署名多項式ｕとの間の第一偏差（deviation）が予め定められた偏差閾値よりも小さいことと、前記メッセージ多項式ｍの一つ以上と前記第二デジタル署名多項式ｖとの間の第二偏差（deviation）が予め定められた偏差閾値よりも小さいことと、を確認することにより、検証する工程と、
を備えた方法。
【請求項２１】
前記秘密鍵多項式ｆ及びｇは、各々、ｐを法として前記環Ｒの多項式ｋと一致しており、
前記秘密鍵多項式ｆ及びｇの各々は、
【数２】
2004526387.tif 000002
のオーダーのユークリッドノルムを有している
ことを特徴とする請求項２０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２２】
前記環Ｒのランダム多項式ｒを選択する工程を更に備えると共に、
第一中間秘密多項式ｓの選択は、ｓ＝ｐｒ＊（１−ｈ）−１（ｍｏｄ  ｑ）の計算を含み、
第二中間秘密多項式ｔの選択は、ｔ＝ｓ＊ｈ（ｍｏｄ  ｑ）の計算を含み、
第三中間秘密多項式ａの選択は、ａ＝ｆｐ−１＊（ｍ−ｓ）（ｍｏｄ  ｐ）の計算を含んでいる
ことを特徴とする請求項２０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２３】
前記予め定められた偏差閾値は、Ｎ／８以下である
ことを特徴とする請求項２２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２４】
前記ランダム多項式ｒは、ｒ（１）＝０というように選択される
ことを特徴とする請求項２０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２５】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は二つのデジタル署名多項式ｕ及びｖを含んでおり、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵を選択する工程と、
【数３】
2004526387.tif 000003
を計算する工程と、
前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成する工程と、
ランダム多項式ｒを選択する工程と、
第一中間多項式ｔ＝ｒ＊ｈ（ｍｏｄ  ｑ）を計算する工程と、
第二中間多項式ａを、
【数４】
2004526387.tif 000004
のオーダーのユークリッドノルムを有して、メッセージ多項式ｍと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択する工程と、
前記第一デジタル署名多項式ｕ＝ｒ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算する工程と、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算する工程と、
前記デジタル署名を、少なくとも、前記第一デジタル署名多項式ｕのユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二デジタル署名多項式ｖとの間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証する工程と、
を備えた方法。
【請求項２６】
前記ランダム多項式ｒは、Ｎまたはより小さいオーダーのユークリッドノルムを有する
ことを特徴とする請求項２２または２５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２７】
第二中間多項式ａの選択は、
【数５】
2004526387.tif 000005
を計算することを含む
ことを特徴とする請求項２５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２８】
前記予め定められた偏差閾値は、Ｎ／１２以下である
ことを特徴とする請求項２７に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項２９】
前記デジタル署名の検証は、ｕ＊ｈ＝ｖ（ｍｏｄ  ｑ）であることを確認すること
を更に含む
ことを特徴とする請求項２０または２５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３０】
メッセージのデジタル署名を生成して検証する方法であって、前記デジタル署名は四つのデジタル署名多項式ｕ１、ｖ１、ｕ２及びｖ２を含んでおり、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択する工程と、
前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵を選択する工程と、
【数６】
2004526387.tif 000006
を計算する工程と、
前記環Ｒのワンタイム秘密鍵多項式ｅを含むワンタイム秘密鍵を選択する工程と、
ワンタイム公開鍵多項式ｈ１及びｈ２の一つのペアを、ｈ１＝ｆ−１＊ｅ（ｍｏｄ  ｑ）及びｈ２＝ｇ−１＊ｅ（ｍｏｄ  ｑ）のように生成する工程と、
第一ランダム多項式ｒ１を選択する工程と、
第一中間多項式ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）を計算する工程と、
第二中間多項式ａ１を、ａ１のユークリッドノルムが
【数７】
2004526387.tif 000007
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択する工程と、
前記第一デジタル署名多項式ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）を計算する工程と、
前記第二デジタル署名多項式ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）を計算する工程と、
第二ランダム多項式ｒ２を選択する工程と、
第三中間多項式ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）を計算する工程と、
第四中間多項式ａ２を、ａ２のユークリッドノルムが
【数８】
2004526387.tif 000008
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択する工程と、
前記第三デジタル署名多項式ｕ２＝ｒ２＋ａ２＊ｇ（ｍｏｄ  ｑ）を計算する工程と、
前記第四デジタル署名多項式ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）を計算する工程と、
前記デジタル署名を、少なくとも、前記第一及び第三のデジタル署名多項式ｕ１及びｕ２の各々のユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二及び第四のデジタル署名多項式ｖ１及びｖ２の各々との間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証する工程と、
を備えた方法。
【請求項３１】
前記秘密鍵多項式ｆ及びｇの各々は、
【数９】
2004526387.tif 000009
のオーダーのユークリッドノルムを有する
ことを特徴とする請求項２５または３０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３２】
前記ランダム多項式ｒ１及びｒ２は、各々、Ｎまたはより小さいオーダーのユークリッドノルムを有する
ことを特徴とする請求項３０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３３】
第二中間多項式ａ１の選択は、
【数１０】
2004526387.tif 000010
を計算することを含み、
第四中間多項式ａ２の選択は、
【数１１】
2004526387.tif 000011
を計算することを含む
ことを特徴とする請求項３０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３４】
前記予め定められた偏差閾値は、Ｎ／１２以下である
ことを特徴とする請求項３３に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３５】
ワンタイム秘密鍵多項式ｅを含むワンタイム秘密鍵の選択は、ｅの第一係数ｅ０をｑ／２ｐのオーダーとなるよう選択することを更に含む
ことを特徴とする請求項３０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３６】
前記予め定められた偏差閾値は、Ｎ／１００以下である
ことを特徴とする請求項３５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３７】
前記予め定められた偏差閾値は、ゼロである
ことを特徴とする請求項３５に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３８】
前記第一ランダム多項式ｒ１及び前記第二ランダム多項式ｒ２の選択は、ｒ１及びｒ２を計算するための一つ以上の補助的な多重利用秘密多項式を用いることを更に含む
ことを特徴とする請求項３０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項３９】
第一ランダム多項式ｒ１の選択は、ａ１’が第一のランダムな短い多項式でありｆ’が第一の補助的な多重利用秘密多項式であるとして、ｒ１＝ａ１’＊ｆ’を計算する工程を更に含み、
第二ランダム多項式ｒ２の選択は、ａ２’が第二のランダムな短い多項式でありｇ’が第二の補助的な多重利用多項式であるとして、ｒ２＝ａ２’＊ｇ’を計算する工程を更に含む
ことを特徴とする請求項３８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４０】
第一ランダム多項式ｒ１の選択は、ａ１’及びａ１’’が第一及び第二のランダムな短い多項式でありｆ’及びｆ’’が第一及び第二の補助的な多重利用秘密多項式であるとして、ｒ１＝ａ１’＊ｆ’＋ａ１’’＊ｆ’’を計算する工程を更に含み、
第二ランダム多項式ｒ２の選択は、ａ２’及びａ２’’が第三及び第四のランダムな短い多項式でありｇ’及びｇ’’が第三及び第四の補助的な多重利用秘密多項式であるとして、ｒ２＝ａ２’＊ｇ’ ＋ａ２’’＊ｇ’’を計算する工程を更に含む
ことを特徴とする請求項３８に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４１】
前記デジタル署名を検証する工程は、
【数１２】
2004526387.tif 000012
であることを確認する工程を更に含んでいる
ことを特徴とする請求項４２に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４２】
前記メッセージ多項式ｍは、一つ以上の安全なハッシュ関数Ｈ（ｍ）を用いて生成される
ことを特徴とする請求項２０、２５または３０に記載のメッセージのデジタル署名を生成して検証する方法。
【請求項４３】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つとを用いて未規約化状態での前記デジタル署名多項式が前記環Ｒ上の前記秘密鍵多項式の倍数ではないというように前記デジタル署名多項式を生成するように、及び、前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差閾値よりも小さいことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置。
【請求項４４】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つとを用いて前記デジタル署名多項式を生成するように、及び、前記デジタル署名多項式の少なくとも一つのノルムが予め定められたノルム閾値よりも小さいことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置。
【請求項４５】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、前記秘密鍵と関連しない補助的な多重利用秘密情報と、前記秘密鍵及び前記第二イデアルｑを用いて生成される公開鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つと補助的な多重利用秘密情報とを用いて前記デジタル署名多項式を生成するように、及び、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置。
【請求項４６】
メッセージのデジタル署名を生成するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つとを用いて未規約化状態での前記デジタル署名多項式が前記環Ｒ上の前記秘密鍵多項式の倍数ではないというように前記デジタル署名多項式を生成するように機能し得るプロセッサーと、
を備えた装置。
【請求項４７】
メッセージのデジタル署名を生成するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つとを用いて前記デジタル署名多項式を生成するように機能し得るプロセッサーと、
を備えた装置。
【請求項４８】
メッセージのデジタル署名を生成するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、前記秘密鍵と関連しない補助的な多重利用秘密情報と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つと補助的な多重利用秘密情報とを用いて前記デジタル署名多項式を生成するように機能し得るプロセッサーと、
を備えた装置。
【請求項４９】
メッセージのデジタル署名を検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差閾値よりも小さいことを少なくとも確認することにより前記デジタル署名を検証するように機能し得るプロセッサーを備えた装置。
【請求項５０】
メッセージのデジタル署名を検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
前記デジタル署名多項式の少なくとも一つのノルムが予め定められたノルム閾値よりも小さいことを少なくとも確認することにより前記デジタル署名を検証するように機能し得るプロセッサーを備えた装置。
【請求項５１】
メッセージのデジタル署名を検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑのうちの第二イデアルｑと前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵とを用いて生成される公開鍵を記憶するためのメモリーと、
前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを少なくとも確認することにより前記デジタル署名を検証するように機能し得るプロセッサーと、
を備えた装置。
【請求項５２】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、二つのデジタル署名多項式ｕ及びｖを含むことを特徴としており、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、を記憶するためのメモリーと、
【数１３】
2004526387.tif 000013
を計算し、
前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成し、
第一中間秘密多項式ｓ及び第二中間秘密多項式ｔを、ｓ＊ｈ＝ｔであるように、また、ｓ及びｔがｐを法として実質的に一致するように、選択し、
第三の中間秘密多項式ａを、前記メッセージ多項式ｍの一つと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように、選択し、
前記第一デジタル署名多項式ｕ＝ｓ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算し、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算し、
前記デジタル署名を、少なくとも、前記メッセージ多項式ｍの一つ以上と前記第一デジタル署名多項式ｕとの間の第一偏差（deviation）が予め定められた偏差閾値よりも小さいことと、前記メッセージ多項式ｍの一つ以上と前記第二デジタル署名多項式ｖとの間の第二偏差（deviation）が予め定められた偏差閾値よりも小さいことと、を確認することにより、検証するように、機能し得るプロセッサーと、
を備えた装置。
【請求項５３】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、二つのデジタル署名多項式ｕ及びｖを含むことを特徴としており、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、を記憶するためのメモリーと、
【数１４】
2004526387.tif 000014
を計算し、
前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成し、
ランダム多項式ｒを選択し、
第一中間多項式ｔ＝ｒ＊ｈ（ｍｏｄ  ｑ）を計算し、
第二中間多項式ａを、
【数１５】
2004526387.tif 000015
のオーダーのユークリッドノルムを有して、メッセージ多項式ｍと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択し、
前記第一デジタル署名多項式ｕ＝ｒ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算し、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算し、
前記デジタル署名を、少なくとも、前記第一デジタル署名多項式ｕのユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二デジタル署名多項式ｖとの間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証するように、機能し得るプロセッサーと、
を備えた装置。
【請求項５４】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、四つのデジタル署名多項式ｕ１、ｖ１、ｕ２及びｖ２を含むことを特徴としており、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、を記憶するためのメモリーと、
【数１６】
2004526387.tif 000016
を計算し、
前記環Ｒのワンタイム秘密鍵多項式ｅを含むワンタイム秘密鍵を選択し、
ワンタイム公開鍵多項式ｈ１及びｈ２の一つのペアを、ｈ１＝ｆ−１＊ｅ（ｍｏｄ  ｑ）及びｈ２＝ｇ−１＊ｅ（ｍｏｄ  ｑ）のように生成し、
第一ランダム多項式ｒ１を選択し、
第一中間多項式ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）を計算し、
第二中間多項式ａ１を、ａ１のユークリッドノルムが
【数１７】
2004526387.tif 000017
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択し、
前記第一デジタル署名多項式ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）を計算し、
前記第二デジタル署名多項式ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）を計算し、
第二ランダム多項式ｒ２を選択し、
第三中間多項式ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）を計算し、
第四中間多項式ａ２を、ａ２のユークリッドノルムが
【数１８】
2004526387.tif 000018
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択し、
前記第三デジタル署名多項式ｕ２＝ｒ２＋ａ２＊ｇ（ｍｏｄ  ｑ）を計算し、
前記第四デジタル署名多項式ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）を計算し、
前記デジタル署名を、少なくとも、前記第一及び第三のデジタル署名多項式ｕ１及びｕ２の各々のユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二及び第四のデジタル署名多項式ｖ１及びｖ２の各々との間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証するように、機能し得るプロセッサーと、
を備えた装置。
【請求項５５】
メッセージのデジタル署名を生成するための装置であって、
前記デジタル署名は、二つのデジタル署名多項式ｕ及びｖを含むことを特徴としており、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、を記憶するためのメモリーと、
【数１９】
2004526387.tif 000019
を計算し、
前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成し、
第一中間秘密多項式ｓ及び第二中間秘密多項式ｔを、ｓ＊ｈ＝ｔであるように、また、ｓ及びｔがｐを法として実質的に一致するように、選択し、
第三の中間秘密多項式ａを、前記メッセージ多項式ｍの一つと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように、選択し、
前記第一デジタル署名多項式ｕ＝ｓ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算し、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算するように、機能し得るプロセッサーと、
を備えた装置。
【請求項５６】
メッセージのデジタル署名を生成するための装置であって、
前記デジタル署名は、二つのデジタル署名多項式ｕ及びｖを含むことを特徴としており、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、を記憶するためのメモリーと、
【数２０】
2004526387.tif 000020
を計算し、
前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成し、
ランダム多項式ｒを選択し、
第一中間多項式ｔ＝ｒ＊ｈ（ｍｏｄ  ｑ）を計算し、
第二中間多項式ａを、
【数２１】
2004526387.tif 000021
のオーダーのユークリッドノルムを有して、メッセージ多項式ｍと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択し、
前記第一デジタル署名多項式ｕ＝ｒ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算し、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算するように、機能し得るプロセッサーと、
を備えた装置。
【請求項５７】
メッセージのデジタル署名を生成するための装置であって、
前記デジタル署名は、四つのデジタル署名多項式ｕ１、ｖ１、ｕ２及びｖ２を含むことを特徴としており、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、を記憶するためのメモリーと、
【数２２】
2004526387.tif 000022
を計算し、
前記環Ｒのワンタイム秘密鍵多項式ｅを含むワンタイム秘密鍵を選択し、
ワンタイム公開鍵多項式ｈ１及びｈ２の一つのペアを、ｈ１＝ｆ−１＊ｅ（ｍｏｄ  ｑ）及びｈ２＝ｇ−１＊ｅ（ｍｏｄ  ｑ）のように生成し、
第一ランダム多項式ｒ１を選択し、
第一中間多項式ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）を計算し、
第二中間多項式ａ１を、ａ１のユークリッドノルムが
【数２３】
2004526387.tif 000023
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択し、
前記第一デジタル署名多項式ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）を計算し、
前記第二デジタル署名多項式ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）を計算し、
第二ランダム多項式ｒ２を選択し、
第三中間多項式ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）を計算し、
第四中間多項式ａ２を、ａ２のユークリッドノルムが
【数２４】
2004526387.tif 000024
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択し、
前記第三デジタル署名多項式ｕ２＝ｒ２＋ａ２＊ｇ（ｍｏｄ  ｑ）を計算し、
前記第四デジタル署名多項式ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）を計算するように、機能し得るプロセッサーと、
を備えた装置。
【請求項５８】
メッセージのデジタル署名を検証するための装置であって、
前記デジタル署名は、二つのデジタル署名多項式ｕ及びｖを含み、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、から計算される
【数２５】
2004526387.tif 000025
に対して、第一中間秘密多項式ｓ及び第二中間秘密多項式ｔが、ｓ＊ｈ＝ｔであるように、また、ｓ及びｔがｐを法として実質的に一致するように、選択されており、
前記メッセージを用いて一つ以上のメッセージ多項式ｍが生成されており、
第三の中間秘密多項式ａが、前記メッセージ多項式ｍの一つと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択されており
前記第一デジタル署名多項式ｕ＝ｓ＋ａ＊ｆ（ｍｏｄ  ｑ）が計算され、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）が計算されていることを特徴としており、
前記デジタル署名を、少なくとも、前記メッセージ多項式ｍの一つ以上と前記第一デジタル署名多項式ｕとの間の第一偏差（deviation）が予め定められた偏差閾値よりも小さいことと、前記メッセージ多項式ｍの一つ以上と前記第二デジタル署名多項式ｖとの間の第二偏差（deviation）が予め定められた偏差閾値よりも小さいことと、を確認することにより、検証するように、機能し得るプロセッサーを備えた装置。
【請求項５９】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、二つのデジタル署名多項式ｕ及びｖを含み、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、から計算される
【数２６】
2004526387.tif 000026
に対して、第一中間多項式ｔ＝ｒ＊ｈ（ｍｏｄ  ｑ）が計算され、
前記メッセージを用いて一つ以上のメッセージ多項式ｍが生成されており、
ランダム多項式ｒが選択され、
第二中間多項式ａが、
【数２７】
2004526387.tif 000027
のオーダーのユークリッドノルムを有して、メッセージ多項式ｍと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択されており、
前記第一デジタル署名多項式ｕ＝ｒ＋ａ＊ｆ（ｍｏｄ  ｑ）が計算され、
前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）が計算されていることを特徴としており、
前記デジタル署名を、少なくとも、前記第一デジタル署名多項式ｕのユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二デジタル署名多項式ｖとの間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証するように、機能し得るプロセッサーを備えた装置。
【請求項６０】
メッセージのデジタル署名を検証するための装置であって、
前記デジタル署名は、四つのデジタル署名多項式ｕ１、ｖ１、ｕ２及びｖ２を含み、
Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑと、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵と、に基づいて
【数２８】
2004526387.tif 000028
が計算され、
前記環Ｒのワンタイム秘密鍵多項式ｅを含むワンタイム秘密鍵が選択され、
ワンタイム公開鍵多項式ｈ１及びｈ２の一つのペアが、ｈ１＝ｆ−１＊ｅ（ｍｏｄ  ｑ）及びｈ２＝ｇ−１＊ｅ（ｍｏｄ  ｑ）のように生成され、
第一ランダム多項式ｒ１が選択され、
第一中間多項式ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）が計算され、
第二中間多項式ａ１を、ａ１のユークリッドノルムが
【数２９】
2004526387.tif 000029
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択され、
前記第一デジタル署名多項式ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）が計算され、
前記第二デジタル署名多項式ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）が計算され、
第二ランダム多項式ｒ２が選択され、
第三中間多項式ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）が計算され、
第四中間多項式ａ２を、ａ２のユークリッドノルムが
【数３０】
2004526387.tif 000030
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択され、
前記第三デジタル署名多項式ｕ２＝ｒ２＋ａ２＊ｇ（ｍｏｄ  ｑ）が計算され、
前記第四デジタル署名多項式ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）が計算されていることを特徴としており、
前記デジタル署名を、少なくとも、前記第一及び第三のデジタル署名多項式ｕ１及びｕ２の各々のユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二及び第四のデジタル署名多項式ｖ１及びｖ２の各々との間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証するように、機能し得るプロセッサーを備えた装置。
【請求項６１】
少なくとも１台のプロセッサーに実行されて、請求項４３乃至６０のいずれかに記載の装置を実現させるプログラム。
【請求項６２】
通信装置にメッセージのデジタル署名を生成させて検証させる方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
第１通信装置に、環Ｒの互いに素なイデアルｐ及びｑを選択させる工程と、
第１通信装置に、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択させる工程と、
第１通信装置に、前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成させる工程と、
第１通信装置に、前記メッセージに基づいて一つ以上のメッセージ多項式を生成させる工程と、
第１通信装置に、前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
を用いて、未規約化状態での前記デジタル署名多項式が前記環Ｒの前記秘密鍵多項式の倍数ではないというように、生成させる工程と、
第２通信装置に、前記デジタル署名を、少なくとも、前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差閾値よりも小さいことを確認することにより、検証させる工程と、
を備えた方法。
【請求項６３】
通信装置にメッセージのデジタル署名を生成させて検証させる方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
第１通信装置に、環Ｒの互いに素なイデアルｐ及びｑを選択させる工程と、
第１通信装置に、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択させる工程と、
第１通信装置に、前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成させる工程と、
第１通信装置に、前記メッセージに基づいて一つ以上のメッセージ多項式を生成させる工程と、
第１通信装置に、前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
を用いて生成させる工程と、
第２通信装置に、前記デジタル署名を、少なくとも、前記デジタル署名多項式の少なくとも一つと関連付けられたノルムが予め定められたノルム閾値よりも小さいことを確認することにより、検証させる工程と、
を備えた方法。
【請求項６４】
通信装置にメッセージのデジタル署名を生成させて検証させる方法であって、前記デジタル署名は一つ以上のデジタル署名多項式を含んでおり、
第１通信装置に、環Ｒのイデアルｐ及びｑを選択させる工程と、
第１通信装置に、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵を選択させる工程と、
第１通信装置に、前記秘密鍵及び前記第二イデアルｑを用いて公開鍵を生成させる工程と、
第１通信装置に、前記メッセージに基づいて一つ以上のメッセージ多項式を生成させる工程と、
第１通信装置に、補助的な多重利用秘密情報を選択させる工程と、
第１通信装置に、前記デジタル署名多項式を、少なくとも以下の要素
（ａ）前記メッセージ多項式の少なくとも一つ
（ｂ）前記秘密鍵多項式の少なくとも一つ
（ｃ）前記イデアルｐ及びｑの少なくとも一つ
（ｄ）前記補助的な多重利用秘密情報
を用いて生成させる工程と、
第２通信装置に、前記デジタル署名を、少なくとも、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを確認することにより、検証させる工程と、
を備えた方法。
【請求項６５】
通信装置にメッセージのデジタル署名を生成させて検証させる方法であって、前記デジタル署名は二つのデジタル署名多項式ｕ及びｖを含んでおり、
第１通信装置に、Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択させる工程と、
第１通信装置に、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵を選択させる工程と、
【数３１】
2004526387.tif 000031
を第１通信装置に計算させる工程と、
第１通信装置に、前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成させる工程と、
第１通信装置に、第一中間秘密多項式ｓ及び第二中間秘密多項式ｔを、ｓ＊ｈ＝ｔであるように、また、ｓ及びｔがｐを法として実質的に一致するように、選択させる工程と、
第１通信装置に、第三の中間秘密多項式ａを、前記メッセージ多項式ｍの一つと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように、選択させる工程と、
第１通信装置に、前記第一デジタル署名多項式ｕ＝ｓ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算させる工程と、
第１通信装置に、前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算させる工程と、
第２通信装置に、前記デジタル署名を、少なくとも、前記メッセージ多項式ｍの一つ以上と前記第一デジタル署名多項式ｕとの間の第一偏差（deviation）が予め定められた偏差閾値よりも小さいことと、前記メッセージ多項式ｍの一つ以上と前記第二デジタル署名多項式ｖとの間の第二偏差（deviation）が予め定められた偏差閾値よりも小さいことと、を確認することにより、検証させる工程と、
を備えた方法。
【請求項６６】
通信装置にメッセージのデジタル署名を生成させて検証させる方法であって、前記デジタル署名は二つのデジタル署名多項式ｕ及びｖを含んでおり、
第１通信装置に、Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択させる工程と、
第１通信装置に、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵を選択させる工程と、
【数３２】
2004526387.tif 000032
を第１通信装置に計算させる工程と、
第１通信装置に、前記メッセージを用いて一つ以上のメッセージ多項式ｍを生成させる工程と、
第１通信装置に、ランダム多項式ｒを選択させる工程と、
第１通信装置に、第一中間多項式ｔ＝ｒ＊ｈ（ｍｏｄ  ｑ）を計算させる工程と、
第１通信装置に、第二中間多項式ａを、
【数３３】
2004526387.tif 000033
のオーダーのユークリッドノルムを有して、メッセージ多項式ｍと量  ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択させる工程と、
第１通信装置に、前記第一デジタル署名多項式ｕ＝ｒ＋ａ＊ｆ（ｍｏｄ  ｑ）を計算させる工程と、
第１通信装置に、前記第二デジタル署名多項式ｖ＝ｔ＋ａ＊ｇ（ｍｏｄ  ｑ）を計算させる工程と、
第２通信装置に、前記デジタル署名を、少なくとも、前記第一デジタル署名多項式ｕのユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二デジタル署名多項式ｖとの間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証させる工程と、
を備えた方法。
【請求項６７】
通信装置にメッセージのデジタル署名を生成させて検証する方法であって、前記デジタル署名は四つのデジタル署名多項式ｕ１、ｖ１、ｕ２及びｖ２を含んでおり、
第１通信装置に、Ｎが１より大きい整数であるとして、環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）の互いに素なイデアルｐ及びｑを選択させる工程と、
第１通信装置に、前記環Ｒの二つの秘密鍵多項式ｆ及びｇを含む秘密鍵を選択させる工程と、
【数３４】
2004526387.tif 000034
を第１通信装置に計算させる工程と、
第１通信装置に、前記環Ｒのワンタイム秘密鍵多項式ｅを含むワンタイム秘密鍵を選択させる工程と、
第１通信装置に、ワンタイム公開鍵多項式ｈ１及びｈ２の一つのペアを、ｈ１＝ｆ−１＊ｅ（ｍｏｄ  ｑ）及びｈ２＝ｇ−１＊ｅ（ｍｏｄ  ｑ）のように生成させる工程と、
第１通信装置に、第一ランダム多項式ｒ１を選択させる工程と、
第１通信装置に、第一中間多項式ｔ１＝ｒ１＊ｈ１（ｍｏｄ  ｑ）を計算させる工程と、
第１通信装置に、第二中間多項式ａ１を、ａ１のユークリッドノルムが
【数３５】
2004526387.tif 000035
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択させる工程と、
第１通信装置に、前記第一デジタル署名多項式ｕ１＝ｒ１＋ａ１＊ｆ（ｍｏｄ  ｑ）を計算させる工程と、
第１通信装置に、前記第二デジタル署名多項式ｖ１＝ｔ１＋ａ１＊ｅ（ｍｏｄ  ｑ）を計算させる工程と、
第１通信装置に、第二ランダム多項式ｒ２を選択させる工程と、
第１通信装置に、第三中間多項式ｔ２＝ｒ２＊ｈ２（ｍｏｄ  ｑ）を計算させる工程と、
第１通信装置に、第四中間多項式ａ２を、ａ２のユークリッドノルムが
【数３６】
2004526387.tif 000036
のオーダーであって、メッセージ多項式ｍの一つと量  ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）  との間の偏差（deviation）の数を最小化するように選択させる工程と、
第１通信装置に、前記第三デジタル署名多項式ｕ２＝ｒ２＋ａ２＊ｇ（ｍｏｄ  ｑ）を計算させる工程と、
第１通信装置に、前記第四デジタル署名多項式ｖ２＝ｔ２＋ａ２＊ｅ（ｍｏｄ  ｑ）を計算させる工程と、
第２通信装置に、前記デジタル署名を、少なくとも、前記第一及び第三のデジタル署名多項式ｕ１及びｕ２の各々のユークリッドノルムがＮのオーダーであることと、前記メッセージｍと前記第二及び第四のデジタル署名多項式ｖ１及びｖ２の各々との間の偏差（deviation）が予め定められた偏差閾値以下であることと、を確認することにより検証させる工程と、
を備えた方法。
【請求項６８】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つとを用いて未規約化状態での前記デジタル署名多項式が前記環Ｒ上の前記秘密鍵多項式の倍数ではないというように前記デジタル署名多項式を生成するように、及び、前記メッセージ多項式の少なくとも一つと前記デジタル署名多項式の少なくとも一つとの間の偏差（deviation）が予め定められた偏差閾値よりも小さいことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置の２以上と、
前記２以上の装置を通信可能にする通信ネットワークと、
を備えた通信ネットワークシステム。
【請求項６９】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つとを用いて前記デジタル署名多項式を生成するように、及び、前記デジタル署名多項式の少なくとも一つのノルムが予め定められたノルム閾値よりも小さいことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置の２以上と、
前記２以上の装置を通信可能にする通信ネットワークと、
を備えた通信ネットワークシステム。
【請求項７０】
メッセージのデジタル署名を生成して検証するための装置であって、
前記デジタル署名は、一つ以上のデジタル署名多項式を含むことを特徴としており、
環Ｒのイデアルｐ及びｑと、前記環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、前記秘密鍵と関連しない補助的な多重利用秘密情報と、前記秘密鍵及び前記第二イデアルｑを用いて生成される公開鍵と、を記憶するためのメモリーと、
前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つと前記イデアルｐ及びｑの少なくとも一つと補助的な多重利用秘密情報とを用いて前記デジタル署名多項式を生成するように、及び、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを少なくとも確認することにより前記デジタル署名を検証するように、機能し得るプロセッサーと、
を備えた装置の２以上と、
前記２以上の装置を通信可能にする通信ネットワークと、
を備えた通信ネットワークシステム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
本発明の別の実施の形態によれば、メッセージのデジタル署名を生成して検証するための装置が提供されている。ここで、前記デジタル署名は、一つ以上のデジタル署名多項式を含んでいる。前記装置は、環Ｒのイデアルｐ及びｑと、環Ｒの一つ以上の秘密鍵多項式を含む秘密鍵と、補助的な多重利用の秘密情報と、前記秘密鍵及び前記第二イデアルｑを用いて生成される公開鍵と、を記憶するためのメモリーを含んでいる。前記装置はまた、前記メッセージに基づいた一つ以上のメッセージ多項式を生成するように、前記メッセージ多項式の少なくとも一つと前記秘密鍵多項式の少なくとも一つとイデアルｐ及びｑの少なくとも一つと補助的な多重利用秘密情報とを用いてデジタル署名多項式を生成するように、及び、前記デジタル署名多項式と前記公開鍵とが予め定められた関係を満たすことを少なくとも確認することによりデジタル署名を検証するように、機能し得るプロセッサーを含んでいる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
デジタル署名が生成されると、署名者は前記デジタル署名を伴ったメッセージを意図された受領者へと伝送する。当該受領者は、ステップ１１６において、前記デジタル署名を検証し得る。当該検証は、メッセージ、デジタル署名及び公開鍵の間の、一つ以上のタイプの比較を含み得る。ここで、前記公開鍵は、好適には、検証者に知られている。例えば、検証者は、デジタル署名多項式と公開鍵多項式との間において、予め定められた関係を確認し得る。加えて、検証者は、デジタル署名多項式とメッセージ多項式との間の偏差（deviation）が予め定められた偏差閾値と比べて小さいまたは等しいことを確認し得る。ａ，ｂ∈Ｚｑ［Ｘ］／（ＸＮ−１）に対して、ａとｂとの間の偏差（deviation）は次のように示される：
Ｄｅｖ（ａ，ｂ）＝＃｛ｉ：ａｉ≠ｂｉ（ｍｏｄ  ｐ）｝    （４）
検証者は、また、一つ以上のデジタル署名多項式のノルムが、予め定められたノルム閾値と比べて小さいまたは等しいことを確認し得る。様々なノルム、例えばＬ１ノルム、Ｌ２（またはユークリッド）ノルムまたはより高次元のＬｐノルムのいずれかを含む、がデジタル署名多項式を制約するために使用され得る。便宜性のためには、ユークリッドノルムが好ましい。