(57)【要約】【課題】  ディジタル署名及びユーザ識別を実行する方法、システム及び装置。【解決手段】  署名者の秘密鍵は、ＮＴＲＵ格子の短く生成する基底であり、署名者の公開鍵は、同一格子のはるかに長く生成する基底である。ディジタル文書に対する署名は、この格子の、下記の３つの重要な特性を有するベクトルである。−署名は、署名されるディジタル文書に付加される。−署名によって、格子について一般的な最近接ベクトル問題を解く能力が実証される。−一般ＮＴＲＵ格子のプライベートベクトルが、まず、格子の完全な短い基底を構成するために使用される。したがって、ＲＥは、署名と、基礎になるＮＴＲＵ格子の最近接ベクトル問題の間の直接のリンクである。
2005515659.tif 000002
【特許請求の範囲】
【請求項１】
ディジタル文書Ｄに署名し、検証する方法であって、
環Ｒ、Ｒのイデアルｑ及びハッシュ関数を選択するステップと、
前記環Ｒの要素ｆ及びｇを生成し、ｑを法とする剰余系で前記環Ｒのｆの逆元ｆ−１を生成するステップと、
ｇ及びｆ−１を用いて導出することができる積に等しいｈを含む公開鍵を生成するステップと、
ｆ及びｇから導出される秘密鍵を作るステップと、
前記ディジタル文書Ｄに前記ハッシュ関数を適用することによってメッセージ・ダイジェストｍを生成するステップと、
前記秘密鍵を使用して前記メッセージ・ダイジェストｍにディジタル署名することによってディジタル署名ｓを生成するステップと、
前記ディジタル文書Ｄ及び前記公開鍵を用いて、１つ又は複数の特定の条件を検証することによって前記ディジタル署名ｓを検証するステップとを含む方法。
【請求項２】
前記ディジタル署名ｓの特定の条件は、ｓから導出される量が、前記メッセージ・ダイジェストｍから導出される量と、特定の関係を満足することである、請求項１に記載の方法。
【請求項３】
前記ディジタル署名ｓの特定の条件は、ｑを法とする剰余系での、前記ディジタル署名ｓと前記公開鍵ｈとの積から導出される前記環Ｒの要素ｔが、前記メッセージ・ダイジェストｍから導出される量と、特定の条件関係を満足することである、請求項１に記載の方法。
【請求項４】
Ｒの追加の要素Ｆ及びＧは、前記秘密鍵から導出することができ、要素Ｄ＝ｆ＊Ｇ−ｇ＊Ｆは前記イデアルｑであり、商ｑ／（Ｄ）が、小さい有限集合である、請求項１に記載の方法。
【請求項５】
Ｒの要素Ｂ及びｂを、前記要素ｆ、ｇ、Ｆ、Ｇ及び前記メッセージ・ダイジェストｍから導出することができ、前記ディジタル署名ｓは、式ｓ＝ｆ＊Ｂ−Ｆ＊ｂ  （ｍｏｄ  ｑ）によって導出することができる、請求項４に記載の方法。
【請求項６】
前記特定の条件が、ｍ＝（ｍ１、ｍ２）、かつ、Ｂが（ｍ１＊Ｇ−ｍ２＊Ｆ）／Ｄから導出できること、という条件を含む、請求項５に記載の方法。
【請求項７】
前記特定の条件が、ｍ＝（ｍ１、ｍ２）、かつ、ｂが（−ｇ＊ｍ１＋ｆ＊ｍ２）／Ｄから導出できること、という条件を含む、請求項５に記載の方法。
【請求項８】
ディジタル文書Ｄに署名し、検証する方法であって、
ハッシュ関数を選択するステップと、
整数ｑを選択するステップと、
多項式ｆ及びｇを生成するステップと、
ｆ−１＊ｆ＝１  （ｍｏｄ  ｑ）である、逆ｆ−１を決定するステップと、
ｈ＝ｆ−１＊ｇ  （ｍｏｄ  ｑ）である、ｈを含む公開鍵を作るステップと、
ｆ及びｇを含む秘密鍵を作るステップと、
前記ハッシュ関数を前記ディジタル文書Ｄに適用することによってメッセージ・ダイジェストｍを作るステップと、
前記秘密鍵を使用して前記メッセージ・ダイジェストｍにディジタル署名することによってディジタル署名ｓを作るステップと、
前記ハッシュ関数、前記公開鍵ｈ、前記ディジタル署名ｓ及び前記整数ｑを用いて、１つ又は複数の特定の条件を検証することによって、前記ディジタル文書Ｄの前記ディジタル署名を検証するステップとを含む方法。
【請求項９】
前記メッセージ・ダイジェストｍが、２つの多項式ｍ１及びｍ２を含む、請求項８に記載の方法。
【請求項１０】
単多項式Ｍ（Ｘ）が選択され、多項式の乗算は、まず普通の多項式の乗算を実行し、次にその結果をＭ（Ｘ）で割り、剰余だけを残すことによって達成される、請求項８に記載の方法。
【請求項１１】
非０整数Ｎが選択され、多項式の乗算は、Ｎを法とする剰余系で、指数を縮小することによって達成される、請求項８に記載の方法。
【請求項１２】
前記秘密鍵が、多項式Ｆ及びＧを含み、Ｆ及びＧは、１つ又は複数の特定の条件を満足する、請求項９に記載の方法。
【請求項１３】
前記特定の条件は、ｆ＊Ｇ−ｇ＊Ｆ＝ｑという条件を含む、請求項１２に記載の方法。
【請求項１４】
前記特定の条件は、Ｆ及びＧが有界係数を有するという条件を含む、請求項１２に記載の方法。
【請求項１５】
前記署名ｓが、
ｓ＝ｆ＊Ｂ＋Ｆ＊ｂ  （ｍｏｄ  ｑ）
として作られ、Ｂ及びｂが、１つ又は複数の特定の条件を満足する、請求項１２に記載の方法。
【請求項１６】
前記特定の条件は、Ｂが（ｍ１＊Ｇ−ｍ２＊Ｆ）／ｑから導出できるという条件を含む、請求項１５に記載の方法。
【請求項１７】
前記特定の条件は、ｂが（−ｇ＊ｍ１＋ｆ＊ｍ２）／ｑから導出できるという条件を含む、請求項１５に記載の方法。
【請求項１８】
前記検証は、多項式ｓ、ｔ、ｍ１、ｍ２が、１つ又は複数の特定の条件を満たすという、特定の条件を含み、ｔは、ｑを法とする剰余系で、前記ディジタル署名ｓと前記公開鍵ｈの積である、請求項９に記載の方法。
【請求項１９】
前記多項式ｓ、ｔ、ｍ１、ｍ２の特定の条件は、Ｒ２で距離を測定する特定の方法に関して（ｓ、ｔ）が（ｍ１、ｍ２）に近いという条件である、請求項１８に記載の方法。
【請求項２０】
前記距離を測定する特定の方法は、多項式の係数のベクトルに対する距離関数である、請求項１９に記載の方法。
【請求項２１】
前記多項式ｆ及びｇは、有界係数を有するように制約される、請求項８に記載の方法。
【請求項２２】
前記多項式ｆ、ｇ、Ｆ及びＧは、有界係数を有するように制約される、請求項１２に記載の方法。
【請求項２３】
前記多項式ｍ１は、０多項式である、請求項９に記載の方法。
【請求項２４】
前記多項式ｍ２は、０多項式である、請求項９に記載の方法。
【請求項２５】
前記ディジタル署名が、ユーザによってある位置で作られ、前記ある位置から他の位置に送信され、前記他の位置でユーザによって検証される、請求項８に記載の方法。
【請求項２６】
第２ユーザによって、第１ユーザの身元を認証する方法であって、前記第２ユーザから前記第１ユーザへのチャレンジ通信、前記第１ユーザから前記第２ユーザへのレスポンス通信、および、前記第２ユーザによる検証を含み、
環Ｒ、Ｒのイデアルｑ及びハッシュ関数を選択するステップと、
前記環Ｒの要素ｆ及びｇを生成し、ｑを法とする剰余系で前記環Ｒのｆの逆元ｆ−１を生成するステップと、
ｇ及びｆ−１を用いて導出することができる積に等しいｈを含む公開鍵を生成するステップと、
ｆ及びｇから導出される秘密鍵を生成するステップと、
前記第２ユーザによってチャレンジ通信Ｃを生成するステップと、
前記チャレンジ通信Ｃに前記ハッシュ関数を適用することによってチャレンジ・ダイジェストｍを生成するステップと、
前記秘密鍵を使用して前記チャレンジ・ダイジェストｍにディジタル署名することによってレスポンス通信ｓを生成するステップと、
ハッシュ関数、前記レスポンス通信ｓ、チャレンジ通信Ｃ及び前記公開鍵を用いて、１つ又は複数の特定の条件を検証することによって、前記レスポンス通信ｓを検証するステップとを含む方法。
【請求項２７】
前記レスポンス通信ｓの特定の条件は、ｓから導出される量が、前記チャレンジ・ダイジェストｍから導出される量と、特定の関係を満足することである、請求項２６に記載の方法。
【請求項２８】
前記レスポンス通信ｓの特定の条件は、ｑを法とする剰余系での、前記レスポンス通信ｓと前記公開鍵ｈとの積から導出される前記環Ｒの要素ｔが、前記チャレンジ・ダイジェストｍから導出される量と、特定の条件関係を満足することである、請求項２６に記載の方法。
【請求項２９】
Ｒの追加の要素Ｆ及びＧは、前記秘密鍵から導出することができ、要素Ｄ＝ｆ＊Ｇ−ｇ＊Ｆは前記イデアルｑであり、商ｑ／（Ｄ）が、小さい有限集合である、請求項２６に記載の方法。
【請求項３０】
Ｒの要素Ｂ及びｂを、前記要素ｆ、ｇ、Ｆ、Ｇ及び前記チャレンジ・ダイジェストｍから導出することができ、前記レスポンス通信ｓは、式ｓ＝ｆ＊Ｂ−Ｆ＊ｂ  （ｍｏｄ  ｑ）によって導出することができる、請求項２９に記載の方法。
【請求項３１】
前記特定の条件が、ｍ＝（ｍ１、ｍ２）、かつ、Ｂが（ｍ１＊Ｇ−ｍ２＊Ｆ）／Ｄから導出できること、という条件を含む、請求項３０に記載の方法。
【請求項３２】
前記特定の条件が、ｍ＝（ｍ１、ｍ２）、かつ、ｂが（−ｇ＊ｍ１＋ｆ＊ｍ２）／Ｄから導出できること、という条件を含む、請求項３０に記載の方法。
【請求項３３】
第２ユーザによって第１ユーザの身元を認証する方法であって、前記第２ユーザから前記第１ユーザへのチャレンジ通信、前記第１ユーザから前記第２ユーザへのレスポンス通信、および、前記第２ユーザによる検証を含み、
ハッシュ関数を選択するステップと、
整数ｑを選択するステップと、
多項式ｆ及びｇを生成するステップと、
ｆ−１＊ｆ＝１  （ｍｏｄ  ｑ）である、逆ｆ−１を決定するステップと、
ｈ＝ｆ−１＊ｇ  （ｍｏｄ  ｑ）である、ｈを含む公開鍵を作るステップと、
ｆ及びｇを含む秘密鍵を作るステップと、
前記第２ユーザによって、前記環ＲのチャレンジＣの選択を含むチャレンジ通信を生成するステップと、
前記第１ユーザによって、前記環Ｒのレスポンスｓの計算を含む、レスポンス通信を生成するステップであって、ｓは、前記ハッシュ関数を前記チャレンジＣに適用することによって導出されるチャレンジ・ダイジェストｍと、ｆとによって導出されるステップと、
前記第２ユーザによって、前記チャレンジＣ、前記ハッシュ関数、前記公開鍵ｈ、前記レスポンスｓ及び前記整数ｑを用いて、１つ又は複数の特定の条件の検証を含む検証を実行するステップとを含む方法。
【請求項３４】
前記チャレンジ・ダイジェストｍが、２つの多項式ｍ１及びｍ２を含む、請求項３３に記載の方法。
【請求項３５】
単多項式Ｍ（Ｘ）が選択され、多項式の乗算は、まず普通の多項式の乗算を実行し、次にその結果をＭ（Ｘ）で割り、剰余だけを残すことによって達成される、請求項３３に記載の方法。
【請求項３６】
非０整数Ｎが選択され、多項式の乗算は、Ｎを法とする剰余系で、指数を縮小することによって達成される、請求項３３に記載の方法。
【請求項３７】
前記秘密鍵が、多項式Ｆ及びＧを含み、Ｆ及びＧが、１つ又は複数の特定の条件を満足する、請求項３４に記載の方法。
【請求項３８】
前記特定の条件は、ｆ＊Ｇ−ｇ＊Ｆ＝ｑという条件を含む、請求項３７に記載の方法。
【請求項３９】
前記特定の条件は、Ｆ及びＧが有界係数を有するという条件を含む、請求項３７に記載の方法。
【請求項４０】
前記レスポンスｓが、
ｓ＝ｆ＊Ｂ＋Ｆ＊ｂ  （ｍｏｄ  ｑ）
として作られ、Ｂ及びｂが、１つ又は複数の特定の条件を満足する、請求項３７に記載の方法。
【請求項４１】
前記特定の条件は、Ｂが（ｍ１＊Ｇ−ｍ２＊Ｆ）／ｑから導出できるという条件を含む、請求項４０に記載の方法。
【請求項４２】
前記特定の条件は、ｂが（−ｇ＊ｍ１＋ｆ＊ｍ２）／ｑから導出できるという条件を含む、請求項４０に記載の方法。
【請求項４３】
前記検証は、多項式ｓ、ｔ、ｍ１、ｍ２が、１つ又は複数の特定の条件を満たすという、特定の条件を含み、ｔは、ｑを法とする剰余系で、前記レスポンスｓと前記公開鍵ｈの積である、請求項３４に記載の方法。
【請求項４４】
前記多項式ｓ、ｔ、ｍ１、ｍ２の特定の条件は、Ｒ２で距離を測定する特定の方法に関して（ｓ、ｔ）が（ｍ１、ｍ２）に近いという条件である、請求項４３に記載の方法。
【請求項４５】
前記距離を測定する特定の方法は、多項式の係数のベクトルに対する距離関数である、請求項４４に記載の方法。
【請求項４６】
前記多項式ｆ及びｇは、有界係数を有するように制約される、請求項３３に記載の方法。
【請求項４７】
前記多項式ｆ、ｇ、Ｆ及びＧは、有界係数を有するように制約される、請求項３７に記載の方法。
【請求項４８】
前記多項式ｍ１は、０多項式である、請求項３４に記載の方法。
【請求項４９】
前記多項式ｍ２は、０多項式である、請求項３４に記載の方法。
【請求項５０】
前記レスポンスが、ユーザによってある位置で作られ、前記ある位置から他の位置に送信され、前記他の位置でユーザによって検証される、請求項３３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・ネットワーク又は他のタイプの通信システムを介する安全な通信及び文書識別に関し、具体的には、環（ｒｉｎｇ）及びイデアル（ｉｄｅａｌ）に基づく安全なユーザ識別及びディジタル署名の技法に関する。本発明は、「スマート・カード」や他の媒体等といったカードと、ユーザ端末間との通信への応用も有する。
【背景技術】
【０００２】
コンピュータ・ネットワーク又は他の通信システムにおいて、所与のユーザが、１又は複数の他のシステムユーザと通信する前に、ユーザ識別技法により、ユーザの身元を証明することで、データ・セキュリティが提供される。他のシステムユーザは、これにより、実際にその所与のユーザと通信していることが保証される。ユーザとは、システム内の個々のコンピュータ又は他のタイプの端末を表す。チャレンジ−レスポンス（ｃｈａｌｌｅｎｇｅ−ｒｅｓｐｏｎｓｅ）タイプの通常のユーザ識別処理は、証明者（Ｐｒｏｖｅｒ）として参照されるシステムユーザが、検証者（Ｖｅｒｉｆｉｅｒ）として参照される別のシステムユーザから、チャレンジの形のある情報を受信することで開始される。証明者は、チャレンジ及び証明者の秘密鍵を使用して、レスポンスを生成し、このレスポンスは検証者に送信される。検証者は、チャレンジ、レスポンス及び公開鍵を使用して、レスポンスが正当な証明者によって生成されたことを検証する。証明者と検証者の間で渡される情報は、暗号技法に従って生成され、これによって、盗聴者又は他の攻撃者が、識別処理に干渉できないことが保証される。
【０００３】
証明者が１方向ハッシュ関数を使用し、検証者からのチャレンジをシミュレートすることで、チャレンジ−レスポンス・ユーザ識別技法を、ディジタル署名技法に変換できることは公知である。そのようなディジタル署名技法では、証明者は、メッセージに１方向ハッシュ関数を適用して、シミュレートされたチャレンジを生成する。証明者は、シミュレートされたチャレンジ及び秘密鍵を使用して、ディジタル署名を生成し、このディジタル署名を、メッセージと共に検証者に送信する。検証者は、同一の１方向ハッシュ関数をメッセージに適用して、シミュレートされたチャレンジを再生し、このチャレンジと公開鍵を使用して、ディジタル署名を検証する。
【０００４】
あるタイプのユーザ識別技法は、有限体の乗法群又は有限体において定義される楕円曲線上の点の群での指数関数の１方向特性に基づく。この技法は、特許文献１及び非特許文献1に記載されている。この技法は、証明者が、群の固定の基底値ｇを、ランダムに選択するｋでべき乗し、これを検証者に送信することを含む。非特許文献１の例では、ランダムに選択され、ｐ−１はｑで割り切れる、２つの素数ｐ及びｑが使用され、ｑ  ｍｏｄ  ｐのオーダの数ｇを選択する。数ｐ、ｑ及びｇは、すべてのユーザが利用可能である。証明者の秘密鍵は、ｘ  ｍｏｄ  ｑであり、証明者の公開鍵ｙは、ｇ−ｘ  ｍｏｄ  ｐである。証明者は、ランダムな０以外の数ｚ  ｍｏｄ  ｑを選択することにより識別処理を開始する。証明者は、量ｇｚ  ｍｏｄ  ｐを計算し、これをコミットメントとして検証者に送信する。検証者は、整数の集合｛１、２、…、２ｔ｝から乱数ｗを選択するが、ここで、ｔは、アプリケーションに依存するセキュリティ数であり、上で引用した文献では７２が選択される。検証者は、チャレンジとしてｗを証明者に送信する。証明者は、レスポンスとして量ｕ＝量ｚ＋ｘｗ  ｍｏｄ  ｑを計算し、検証者に送信する。検証者は、ｇｚがｐを法として量ｇｕｙｗと一致している場合、安全に識別されたものとして証明者を受け入れる。
【０００５】
もう１つのタイプのユーザ識別技法は、２つの大きい素数の積の素因数分解が困難であることに基づく。このタイプのユーザ識別技法が、非特許文献２に記載されている。この技法では、証明者が、ランダムに選択した引数ｇをｂ  ｍｏｄ  ｎ乗し、検証者に送信することを含む。非特許文献２の例では、ランダムに選択される２つの素数ｐ及びｑ、ｐとｑの積として生成される数ｎ並びにやはりランダムに選択される大きい素数ｂが使用される。数ｎ及びｂは、すべてのユーザが利用可能である。証明者の秘密鍵は、ｘ  ｍｏｄ  ｎであり、証明者の公開鍵ｙは、ｘ−ｂ  ｍｏｄ  ｎである。証明者は、法ｎの非０数の集合から数ｇをランダムに選択することによって識別処理を開始する。証明者は、量ｇｂ  ｍｏｄ  ｎを計算し、コミットメントとして検証者に送信する。検証者は、法ｂの非０数の集合から数ｃを選択し、チャレンジとしてｃを証明者に送信する。証明者は、レスポンスとして数ｈ＝量ｇｘｃ  ｍｏｄ  ｎを計算し、検証者に送信する。検証者は、ｇｂが、ｎを法とする剰余系でｈｂｙｃと一致している場合に、安全に識別されたものとして証明者を受け入れる。
【０００６】
もう１つのタイプのユーザ識別技法は、法ｑの特定の値の集合から、小さい係数を有する多項式を見つけることの困難さに基づく。このタイプのユーザ識別技法が、非特許文献３に記載されている。この技法では、証明者が、小さい係数を有する多項式を選択し、集合Ｓの値ｂに関してＸ＝ｂでの法ｑの値を公開することを含む。証明者は、小さい係数を有するコミットメント多項式を選択し、Ｓのｂに関するＸ＝ｂでの値を検証者に送信する。検証者は、チャレンジとして小さい多項式を選択し、証明者に送信する。証明者は、レスポンスとして、さまざまな他の多項式から形成される多項式を計算し、検証者に送信する。検証者は、レスポンス多項式が、小さい係数を有し、Ｓのすべての値ｂに関してＸ＝ｂで正しい値を有する場合に、安全に識別されたものとして証明者を受け入れる。
【０００７】
もう１つのタイプのユーザ識別技法は、格子のうちで近いベクトルを見つけることの困難さに基づく。このタイプの識別技法が、非特許文献４に記載されている。この方法では、格子のほぼ直交する基底が、秘密鍵として選択され、同一格子の直交しない基底が、公開鍵として公表される。検証者は、チャレンジとしてランダムなベクトルを（セキュア・ハッシュ関数を介して）選択する。証明者は、よいほぼ直交する基底を使用して、チャレンジ・ベクトルに近い格子ベクトルを見つけ、この格子ベクトルを検証者に送信する。検証者は、レスポンス・ベクトルが格子に含まれ、チャレンジ・ベクトルに十分に近い場合に、安全に識別されたものとして証明者を受け入れる。非特許文献４の方法では、公開鍵が、ランダムに選択された格子の完全な基底であり、したがって、Ｎ次元の格子についてＮ２ビットのオーダのサイズを有する。公開鍵のサイズが大きいので、この方法は、多くの応用例について非実用的である。
【０００８】
やはり格子で近いベクトルを見つけることの困難さに基づくユーザ識別技法のもう１つのタイプが、非特許文献５に記載されている。この方法では、格子が、畳み込みモジュール構造（ｃｏｎｖｏｌｕｔｉｏｎ  ｍｏｄｕｌａｒ  ｓｔｒｕｃｔｕｒｅ）を有し、これによって、公開鍵（すなわち、格子）を、Ｎ＊ｌｏｇ（Ｎ）ビットオーダサイズの単一ベクトルを使用して記述できるようになる。しかし、この方法では、補助的な素数を使用して格子点にチャレンジを付加しており、これによってセキュリティが低下する。
【０００９】
【特許文献１】米国特許第４９９５０８２号明細書
【非特許文献１】C.P.Schnorr著、”Efficient Identification and Signatures for Smart Cards”、 G.Brassard編、Advances in Cryptology−Crypto ‘89、“Lecture Notes in Computer Science  435、Springer-Verlag、1990年、P239-252
【非特許文献２】L.C.Guillou、J.J.Quisquater著、”A Practical Zero−Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory”、C.G.Gunther編、Advances in Cryptology−Eurocrypt ‘88、Lecture Notes in Computer Science 330、Springer-Verlag、１９８８年、P123-128
【非特許文献３】Jeffrey Hoffstein、Daniel Lieman、Joseph H.Silverman著、”Polynomial Rings and Efficient Public Key Authentication”、Proceeding of the International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC ’99)、M. Blum及びC.H.Lee編、City University of Hong Kong Press
【非特許文献４】Goldreich、S.Goldwasser、S.Halevi著、”Public-key cryptography from lattice reduction problems”、Proceedings of CRYPTO’97、Lecture Notes in Computer Science 1294、Springer-Verlag、1997年
【非特許文献５】J.Hoffstein、 J.Pipher、J.H.Silverman著、”NSS： An NTRU Lattice-Based Signature Scheme”、Advances in Cryptology-Eurocrypt ‘01、Lecture Notes in Computer Science、Springer-Verlag、2001年
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上で説明した非特許文献1〜５の技法は、多くの応用例で許容可能な性能を提供することができるが、上記及び他の従来技術の技法より高い計算効率と、セキュリティとを提供できる改善された技法の必要性がある。
【課題を解決するための手段】
【００１１】
本発明は、ユーザ識別、ディジタル署名及び他の安全な通信機能を実行する方法、システム及び装置を提供する。鍵が、大きな集合のベクトルから、本質的にランダムに選択され、鍵長は、同程度のセキュリティ・レベルをもつ、他の一般的な識別及びディジタル署名の鍵長と同程度である。本発明の署名技法及び検証技法によって、以前の技術に対する計算効率、鍵サイズ、フットプリント及び／又は処理要件の実質的な改善が提供される。
【００１２】
本発明による識別／ディジタル署名の実施形態の署名技法では、環の乗算と、その環のイデアルｑを法とする剰余系での縮小の混合システムが使用され、検証技法では、その有効性が初等確率論に依存する、要素の積の特殊な特性が使用される。本識別／ディジタル署名方式の安全性は、ｑを法とする縮小の反復及び特殊な特性を有する積の形成の困難さに由来する。多項式の商環を使用する、本識別／ディジタル署名方式の実施形態では、セキュリティが、ほとんどの格子について、最短のベクトルよりもほんの少し長いベクトルを見つけることが非常に難しいことと、ランダムに選択された非格子ベクトルに非常に近い格子ベクトルを見つけることも難しいという経験的に観察された事実にも基づく。
【００１３】
本発明の特徴の一つに従い、証明者として参照されるシステムユーザの１人が、環Ｒの秘密鍵要素ｆ及びｇを作成し、環Ｒの関連する公開鍵要素ｈを作成し、ｈを公開する、安全なユーザ識別技法が提供される。検証者として参照される、他のシステムユーザが、ランダムなチャレンジ・ビット列Ｃを選択し、ハッシュ関数をＣに適用して、環Ｒでのチャレンジ要素（ｍ１、ｍ２）＝Ｈａｓｈ（Ｃ）を生成する。検証者は、ｍ１及びｍ２を証明者に送信する。証明者は、秘密鍵（ｆ、ｇ）、要素ｍ１及び要素ｍ２を使用してレスポンス要素ｓを生成する。証明者は、レスポンス要素ｓを検証者に送信する。検証者は、要素ｓ及び公開鍵要素ｈを使用して、要素ｔ＝ｈ＊ｓ  ｍｏｄ  ｑを生成する。検証者は、環Ｒでの特定の距離関数に関して、要素の対（ｓ、ｔ）が要素の対（ｍ１、ｍ２）に十分に近いことを検査する。この条件が満足される場合に、検証者は、証明者の身元を受け入れる。検証者は、証明者によって送信されるデータの認証又は他の安全な通信機能のために、上記の証明者の安全な識別のための比較を使用することができる。
【００１４】
本発明の他の特徴に従うことで、ディジタル署名技法が提供される。証明者は、ディジタル文書Ｍにハッシュ関数を適用して、環Ｒでのチャレンジ要素（ｍ１、ｍ２）＝Ｈａｓｈ（Ｍ）を生成する。証明者は、ｍ１、ｍ２、ｆ及びｇを使用して、署名要素ｓを生成する。証明者は、ディジタル文書Ｍ及び署名ｓを公開する。検証者は、要素ｓ及び公開鍵要素ｈを使用して、要素ｔ＝ｈ＊ｓ  ｍｏｄ  ｑを生成する。検証者は、要素の対（ｓ、ｔ）が、環Ｒの特定の測定距離関数に関して要素の対（ｍ１、ｍ２）＝Ｈａｓｈ（Ｍ）に十分に近いことを検査する。この条件が満足される場合に、検証者は、メッセージＭに対する証明者の署名を受け入れる。
【００１５】
本発明のさらなる特徴及び長所は、以下、図面を用いた詳細な説明により明らかにする。
【発明を実施するための最良の形態】
【００１６】
図１は、本発明の実施形態の実施に用いるシステムのブロック図である。２つのプロセッサベースのサブシステム１０５及び１５５が、例えば、電話又はインターネット通信チャネルのような、任意の有線又は無線の通信チャネルといった、安全でないチャネル５０を介して通信している。サブシステム１０５は、プロセッサ１１０を有し、サブシステム１５５はは、プロセッサ１６０を有する。説明される形でプログラムされる時に、プロセッサ１１０及び１６０と、それに関連する回路は、本発明の実施形態を実施し、本発明の方法の実施形態を実践する。プロセッサ１１０及び１６０は、それぞれ、例えば電子ディジタル・プロセッサ又はマイクロプロセッサといった、適当なプロセッサとすることができる。電子的、光学的又は他の手段によって、本明細書に記載の機能を実行することができる、あらゆる汎用若しくは特殊目的のプロセッサ又は他の機械若しくは回路を使用することが可能である。プロセッサは、例えば、Ｉｎｔｅｌ社のＰｅｎｔｉｕｍ（登録商標）プロセッサとすることができる。サブシステム１０５は、典型的には、メモリ１２３、クロック＆タイミング回路１２１、入出力機能１１８、モニタ１２５とを有し、これらのすべてを、普通のタイプのものとすることができる。入力には、符号１０３で表されるキーボード入力を含めることができる。通信は、トランシーバ１３５を介し、トランシーバ１３５は、通信信号のための、モデム又は適当なデバイスからなる。
【００１７】
この例示的実施形態において、サブシステム１５５は、サブシステム１０５に類似する構成とすることができる。プロセッサ１６０は、関連する入出力回路１６４、メモリ１６８、クロック＆タイミング回路１７３及びモニタ１７６とを有する。入力に、キーボード１５５が含まれる。サブシステム１５５の外部世界との通信は、トランシーバ１６２を介し、トランシーバ１６２は、同様に、通信信号のための、モデム又は適当なデバイスからなる。
【００１８】
本発明によるユーザ識別技法及びディジタル署名技法は、乗算及び環のイデアルを法とする縮小に基づく。本発明の典型的な実施形態は、環に対する制約付き多項式の乗算及びイデアルを法とする縮小に基づく。典型的な環Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）は、多項式ＸＮ−１によって生成されるイデアルを法とし、整数係数を有する多項式の環であり、Ｒの典型的なイデアルは、整数ｑによって生成されるイデアルであり、Ｒの典型的な商は、多項式ＸＮ−１によって生成されるイデアルを法とする有限環Ｚ／ｑＺに含まれる係数を有する多項式の環Ｒ／ｑＲ＝（Ｚ／ｑＺ）［Ｘ］／（ＸＮ−１）である。
【００１９】
この識別技法及びディジタル署名技法では、環Ｒの乗算規則を利用する。Ｒの多項式Ａ（Ｘ）＝Ａ０＋Ａ１Ｘ＋…＋ＡＮ−１ＸＮ−１及びＲの多項式Ｂ（Ｘ）＝Ｂ０＋Ｂ１Ｘ＋…＋ＢＮ−１ＸＮ−１に対し、典型的な積は、
Ｃ（Ｘ）＝Ａ（Ｘ）＊Ｂ（Ｘ）＝Ｃ０＋Ｃ１Ｘ＋…＋ＣＮ−１ＸＮ−１
で与えられ、ここで、Ｃ０、…、ＣＮ−１は、
Ｃｉ＝Ａ０Ｂｉ＋Ａ１Ｂｉ−１＋…＋ＡｉＢ０＋Ａｉ＋１ＢＮ−１＋Ａｉ＋２ＢＮ−２＋…＋ＡＮ−１Ｂｉ＋１
で与えられる。この典型的な積は、畳込積（ｃｏｎｖｏｌｕｔｉｏｎ  ｐｒｏｄｕｃｔ）として知られている。残りの説明において、多項式の積に関するすべての言及は、上で説明したＲでの典型的な乗算を指すものとする。また、上で説明した乗算規則は、本発明の要件ではなく、代替実施形態では、他のタイプの環において、他のタイプの乗算規則を使用することもできる。
【００２０】
環Ｒの典型的な積は、ｈ（Ｘ）＝ｆ−１（Ｘ）＊ｇ（Ｘ）であり、ここで、ｆ（Ｘ）は、制約付き多項式の集合Ｒｆから選択され、ｇ（Ｘ）は、制約付き多項式の集合Ｒｇから選択され、Ｒでのｆ−１（Ｘ）は、Ｒ／ｑＲでのｆ（Ｘ）の逆関数である。制約付き多項式Ｒｆの典型的な集合は、有界の係数を有するＲの多項式の集合、より具体的には、指定された数の１を有する２進多項式の集合である。制約付き多項式Ｒｇの典型的な集合は、有界の係数を有するＲの多項式の集合、より具体的には、指定された数の１を有する２進多項式の集合である。２つの制約付き多項式Ｒｆでのｆ（Ｘ）及びＲｇでのｇ（Ｘ）が与えられれば、環Ｒ／ｑＲでの逆関数ｆ−１（Ｘ）を見つけ、Ｒでの積ｈ（Ｘ）＝ｆ−１（Ｘ）＊ｇ（Ｘ）を見つけることは、比較的簡単である。しかし、制約付き多項式の集合から、適切に選択された制約により、この処理を逆転し、ｆ−１（Ｘ）＊ｇ（Ｘ）がｈ（Ｘ）と等しくなるようなＲｆのｆ（Ｘ）及びＲｇのｇ（Ｘ）を判定することを極端に難しくすることができる。典型的な選択は、ｑ＝１２８、Ｎ＝２５１であり、Ｒｆは７３個の１及び１７８個の０を有する２進多項式の集合であり、Ｒｇは７１個の１及び１８０個の０を有する２進多項式の集合である。当業者は、ｈ（Ｘ）だけを与えられた時に、ｆ（Ｘ）とｇ（Ｘ）、又は、他の同等の対を回復することとが不可能な他の選択も簡単に導出することが可能である。以下で詳細に説明するように、これによって、効率的なユーザ識別及びディジタル署名の実施に使用するのに特によく適した１方向関数がもたらされる。
【００２１】
本発明による典型的な識別技法では、中央当局によって確立され、すべてのユーザに利用可能とされる複数のシステムパラメータが使用される。これらのシステムパラメータには、上述した数Ｎ及びｑが含まれる。システムパラメータには、適切な有界係数多項式の集合Ｒｆ、Ｒｇ、Ｒ２の要素間の距離を測定する式及び検証処理中に使用される数ＮｏｒｍＢｏｕｎｄが含まれる。図２に、公開鍵／秘密鍵対の作成フローを示す。ステップ２０２でパラメータを確立した後に、証明者は、ステップ２０４で、秘密の多項式、Ｒｆのｆ（Ｘ）及びＲｇのｇ（Ｘ）を選択する。証明者は、ステップ２０６で、環Ｒ／ｑＲのｆ（Ｘ）の逆関数ｆ−１（Ｘ）を計算する。証明者の秘密鍵には、２つの多項式ｆ（Ｘ）及びｇ（Ｘ）が含まれる。ステップ２０８で、効率を改善するために、証明者は、有界のサイズを有し、以下の式
ｆ（Ｘ）＊Ｇ（Ｘ）−ｇ（Ｘ）＊Ｆ（Ｘ）＝ｑ
を満足する、Ｒの２つの追加多項式Ｆ（Ｘ）及びＧ（Ｘ）を事前に計算することができる。証明者の公開鍵は、多項式ｈ（Ｘ）＝ｆ−１（Ｘ）＊ｇ（Ｘ）である。証明者は、ステップ２１０で公開鍵を公開する。
【００２２】
図３に、典型的な識別処理を示す。検証者は、ステップ３０２で、チャレンジＣを生成し、証明者に送信することによって、チャレンジ・フェーズを開始する。証明者は、ステップ３０４で、チャレンジＣにハッシュ関数を適用してＲの多項式ｍ１（Ｘ）及びｍ２（Ｘ）を形成することによって、レスポンス・フェーズを開始する。証明者は、秘密鍵多項式を使用して、レスポンス多項式ｓ（Ｘ）を計算し、その結果、（ｓ、ｔ）が、（ｍ１、ｍ２）に近くなるようにする。ここで、ｔ（Ｘ）は、Ｒ／ｑＲでｔ（Ｘ）＝ｈ（Ｘ）＊ｓ（Ｘ）である。レスポンス多項式の計算は、下記のステップ
・Ｑ［Ｘ］／（ＸＮ−１）で、Ｂ＝（ｍ１＊Ｇ−ｍ２＊Ｆ）／ｑ及びｂ＝（−ｍ１＊ｇ＋ｍ２＊ｆ）／ｑを計算する。
・Ｂ及びｂの係数を、最も近い整数に丸める。したがって、Ｂ及びｂは、Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）に含まれる。
・ｓ＝ｆ＊Ｂ＋Ｆ＊ｂ  （ｍｏｄ  ｑ）を計算する。
により実行される。
【００２３】
証明者は、ｓ（Ｘ）を検証者に送信する。検証者は、ステップ３０６で、Ｃにハッシュ関数を適用して多項式ｍ１（Ｘ）及びｍ２（Ｘ）を形成することによって、検証フェーズを開始する。検証者は、Ｒ／ｑＲの多項式ｔ（Ｘ）＝ｈ（Ｘ）＊ｓ（Ｘ）を計算する。検証者は、（ｓ、ｔ）から（ｍ１、ｍ２）への距離がＮｏｒｍＢｏｕｎｄより小さいことをテストする。証明者によって送信されたレスポンス多項式ｓ（Ｘ）がこのテストに合格する場合に、検証者は、正当なものとして証明者を受け入れる。
【００２４】
本発明の識別方法による実施形態について、現在の条件の下で、実用的な暗号による安全な識別／ディジタル署名方法を提供する動作パラメータ例を以下に示す。
【００２５】
Ｎ＝２５１、ｑ＝１２８、ＮｏｒｍＢｏｕｎｄ＝３５０、
Ｒｆ＝｛７３個の１及び１４８個の０を有する２進多項式｝
Ｒｇ＝｛７１個の１及び１５０個の０を有する２進多項式｝
距離は、センタリングされたユークリッド・ノルムによって測定される。当業者は、さまざまな安全性のレベルで実用的な暗号による安全な識別／ディジタル署名方法を提供する他の選択肢を簡単に導出するであろう。
【００２６】
「チャレンジ／レスポンス／検証」のステップを含むすべての認証方法は、ディジタル署名方法に変えることができる。基本的な発想は、ハッシュ関数（下記参照）を使用して、署名されるディジタル文書からチャレンジを作成することである。図４に、典型的なディジタル署名処理を示す。ディジタル署名を始めるステップは、下記の通りである。
【００２７】
鍵作成（ディジタル署名）
署名者が、識別方法と同じ、秘密署名鍵（ｆ（Ｘ）、ｇ（Ｘ）、Ｆ（Ｘ）、Ｇ（Ｘ））及び公開検証鍵ｈ（Ｘ）を作成する。
【００２８】
署名ステップ１．チャレンジ・ステップ（ディジタル署名）
署名者が、ステップ４０４で、署名されるディジタル文書Ｄにハッシュ関数Ｈ（下記参照）を適用して、チャレンジ多項式ｍ１（Ｘ）及びｍ２（Ｘ）を作る。
【００２９】
書名ステップ２．レスポンス・ステップ（ディジタル署名）
これは、識別方法と同一である。署名者が、秘密鍵多項式を使用して署名多項式ｓ（Ｘ）を計算し、その結果、（ｓ、ｔ）が（ｍ１、ｍ２）に近くなるようにする。ここで、Ｒ／ｑＲでｔ（Ｘ）＝ｈ（Ｘ）＊ｓ（Ｘ）である。署名者は、ディジタル文書及び署名からなる対（Ｄ、ｓ（Ｘ））を公開する。
【００３０】
検証ステップ（ディジタル署名）
検証者が、ステップ４０６で、ディジタル文書Ｄにハッシュ関数Ｈを適用して、多項式ｍ１（Ｘ）及びｍ２（Ｘ）を作る。検証処理は、識別方法と同一である。検証者は、Ｒ／ｑＲの多項式ｔ（Ｘ）＝ｈ（Ｘ）＊ｓ（Ｘ）を計算する。検証者は、（ｓ、ｔ）から（ｍ１、ｍ２）への距離がＮｏｒｍＢｏｕｎｄより小さいことをテストする。ｓ（Ｘ）がこのテストに合格する場合に、検証者は、文書Ｄのディジタル署名を受け入れる。
【００３１】
本発明の典型的な実施形態のさらなる詳細が、所望のセキュリティ・レベルを得るための典型的なパラメータ選択方法、及び、本発明の効率的な実施の典型的な方法と共に、付録Ａに記載されている。付録Ａ、表題「付録Ａ、ＮＴＲＵＳＩＧＮ：ＮＴＲＵ格子を使用するディジタル署名」が、本明細書に組み込まれ、本明細書の一部を形成する。
【００３２】
当該技術分野で周知のハッシュ関数が、本明細書で使用される。ハッシュ関数の目的は、任意の量のデータを入力とし、入力から出力を正確に予測することが非常に難しい形で小さい量のデータ（通常は８０ビットから１６０ビットの間）を作ることである。例えば、正確に同一の出力を作る、２つの入力組を見つけることが、極端に困難でなければならない。ハッシュ関数は、当技術分野で周知の、データのより長いストリームを作る形でも使用される。より長いデータのストリームを作るためにハッシュ関数を使用する典型的な方法は、当技術分野でカウンタ・モードとして公知であり、入力データが、カウンタに連結され、カウンタが増分されるたびに繰り返してハッシュ化される。ハッシュ関数は、暗号及びコンピュータ・サイエンスの他の領域でさまざまな目的で使用される。
【００３３】
よいハッシュ関数を作ることは、重要な問題である。ＳＨＡ１やＭＤ５等の典型的なハッシュ関数は、入力のチャンクをとり、部分に分割し、前記部分に単純な論理演算（例えば、論理和、論理積、シフト）を行うことで進行する。これは、一般に、複数回行われる。例えば、ＳＨＡ１では、５１２ビットのデータをとり、８０ラウンドの分割及び再組合せを行い、１６０ビットをユーザに返す。この処理は、より長いメッセージについては繰り返し行われる。
【００３４】
本発明のユーザ識別技法及びディジタル署名技法によって、従来技術の技法と同等のセキュリティ・レベルで、計算効率が大きく改善されると同時に、証明者及び検証者によって保管されなければならない情報の量を減らすことができる。上で説明した技法が、例示的であり、本発明を、図示した実施形態の特定のグループに制限するものではない。請求項の範囲内の代替実施形態は、当業者には容易に理解可能である。
【００３５】
付録Ａ、ＮＴＲＵＳＩＧＮ：ＮＴＲＵ格子を使用するディジタル署名
ＪＥＦＦＲＥＹ  ＨＯＦＦＳＴＥＩＮ、ＮＩＣＫ  ＨＯＷＧＲＡＶＥ−ＧＲＡＨＡＭ、ＪＩＬＬ  ＰＩＰＨＥＲ、ＪＯＳＥＰＨ  Ｈ．ＳＩＬＶＥＲＭＡＮ、ＷＩＬＬＩＡＭ  ＷＨＹＴＥ
【００３６】
序（１９９１  Ｍａｔｈｅｍａｔｉｃｓ  Ｓｕｂｊｅｃｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ。Ｐｒｉｍａｒｙ：９４Ａ６０；Ｓｅｃｏｎｄａｒｙ：１１Ｔ７１。キーワード及び句、ディジタル署名、公開鍵認証、ＮＴＲＵ、ＮＴＲＵＳＩＧＮ、ＮＴＲＵＥＮＣＲＹＰＴ、格子ベースの暗号、最近接ベクトル）。
【００３７】
安全な公開鍵による認証及びディジタル署名は、電子通信、商取引及びセキュリティにますます重要になってきている。これらは、強力なデスクトップ・コンピュータだけではなく、スマート・カード、セル・フォン及びＲＦＩＤトークン等、メモリ及び処理能力を厳しく制限されたデバイスでも必要である。公開鍵認証及びディジタル署名の重要性は、問題の理論的態様及び実用的態様の両方に捧げられた大量の文献（例えば、文献［１、５、９、１０、１７、２０、２３、２５、２６、２７］参照）によって十分に実証されている。
【００３８】
ＣＲＹＰＴＯ’９６で、ＮＴＲＵと呼ばれる、非常に効率的な新しい公開鍵暗号システムが導入された（詳細は［６］参照）。ＮＴＲＵは、畳み込みモジュール格子又はＮＴＲＵ格子と呼ばれる、あるクラスの格子について、短い及び／又は近いベクトルを見つけることが数学的に困難であるという問題を基礎としている。この論文で、筆者は、ＮＴＲＵで用いられたのと同じ格子についての、同じ困難な問題を基礎とする、ＮＴＲＵＳＩＧＮと呼ぶ相補的な高速認証及びディジタル署名方式を提示している。以下では、元のＮＴＲＵ公開鍵暗号化／復号化アルゴリズムを、ＮＴＲＵＥＮＣＲＹＰＴと呼ぶ。
【００３９】
ＮＴＲＵＳＩＧＮの核になる発想は、以下の通りである。署名者の秘密鍵は、ＮＴＲＵ格子の短く生成する基底であり、署名者の公開鍵は、同一格子のはるかに長く生成する基底である（これが、短く生成するベクトルのみを有するＮＴＲＵＥＮＣＲＹＰＴと異なる点である）。ディジタル文書の署名は、下記の２つの重要な特性を有する、格子内のベクトルである。
【００４０】
・署名は、署名されるディジタル文書に付加される。
・署名は、その格子内の一般的に最近接ベクトル問題を解く能力を実証する。
【００４１】
ＮＴＲＵＳＩＧＮが、この２つの特性を達成する様子を、以下に短く要約する。
【００４２】
鍵生成：秘密鍵は、（ｆ、ｇ）と表される短い２Ｎ次元のベクトルを含む。公開鍵は、ＮＴＲＵ格子ＬｈＮＴを特定する、大きいＮ次元ベクトルｈである。すなわち、ｈは、普通のＮＴＲＵ畳み込み合同ｈ≡ｆ−１＊ｇ  （ｍｏｄ  ｑ）により、ｆ及びｇから生成される。秘密鍵は、（ｆ、ｇ）と（Ｆ、Ｇ）が、完全なＮＴＲＵ格子ＬｈＮＴを生成するように選択された相補的な短いベクトル（Ｆ、Ｇ）も含む。
【００４３】
署名：署名されるディジタル文書はハッシュ化され、ｑを法とするランダム・ベクトル（ｍ１、ｍ２）が生成される。署名者は、（秘密の）短く生成するベクトルを用い、（ｍ１、ｍ２）に最も近い格子ベクトル（ｓ、ｔ）を見つける。
【００４４】
検証：検証者は、公開鍵ｈを使用して、（ｓ、ｔ）が、実際に格子ＬｈＮＴに含まれることを検証し、（ｓ、ｔ）が適度に（ｍ１、ｍ２）に近いことを検証する。
【００４５】
注１。ＮＳＳと呼ばれ、同様にＮＴＲＵ格子に基づく、初期のディジタル署名方法が、Ｅｕｒｏｃｒｙｐｔ  ２００１［７］で提示された。多数の暗号学者が、ＮＳＳ署名と基礎としている困難な格子問題間の不完全なリンクに起因する、ＮＳＳの弱さを見つけた。詳細についてはセクション８を参照されたい。これらの問題は、ＮＴＲＵＳＩＧＮで解決されている。というのは、ＮＴＲＵＳＩＧＮ署名と、基礎としているＮＴＲＵ格子の（近似）最近接ベクトル問題の間に直接で率直なリンクがあるからである。
【００４６】
注２。ＮＴＲＵＳＩＧＮが基づいている原理は、非常に単純である。署名者は、ＮＴＲＵ格子の短い基底ベクトルについて秘密の知識を有する。メッセージ・ダイジェストから生じる空間内の任意の点を与えられて、署名者は、この知識を使用して、メッセージ点に近いＮＴＲＵ格子内の点を見つける。署名者は、最近接ベクトル問題（ＣＰＶ）へのこの近似解を、署名として示す。この基本的な発想は、［４］でＧｏｌｄｒｅｉｃｈ、Ｇｏｌｄｗａｓｓｅｒ及びＨａｌｖｅｉによって既に提案されている。
【００４７】
この論文での基本的な進歩は、ＣＶＰベースの署名に関するＮＴＲＵ格子の使用である。ＮＴＲＵ格子の周期性によって、１つか２つのベクトルだけで公開鍵を指定できるようになり、実用的な鍵サイズのＮＴＲＵＥＮＣＲＹＰＴ及びＮＴＲＵＳＩＧＮの安全な実例を可能にするのは、この特性である。したがって、次元ｎの格子について、ＧＧＨ提案［４］は、サイズＯ（ｎ２）ビットの鍵を必要とするが、ＮＴＲＵＥＮＣＲＹＰＴ及びＮＴＲＵＳＩＧＮでは、サイズＯ（ｎ  ｌｏｇ  ｎ）ビットの鍵が使用される。実用的なレベルでは、これは、ＧＧＨのセキュア版が、１０５ビットから１０６ビット間の鍵を必要とする（［１９］参照）が、ＮＴＲＵＥＮＣＲＹＰＴ及びＮＴＲＵＳＩＧＮによって、２０００ビット未満の鍵を用いてＲＳＡ  １０２４ビット・セキュリティが達成されることを意味する。したがって、ＮＴＲＵＥＮＣＲＹＰＴ及びＮＴＲＵＳＩＧＮでは、ＲＳＡ及びＥＣＣを超える程度の速度及びフットプリントの利点を達成しながら、ＲＳＡサイズの鍵が使用される。
【００４８】
ＣＶＰベースの署名のためのＮＴＲＵ格子の使用は、完全に直接ではない。ＧＧＨ方式に関して、署名者は、秘密鍵として短いベクトルの任意の基底を選択することができる。ＮＴＲＵ格子について、第１の短いベクトル（ｆ、ｇ）、公開パラメータＮ及びｑにより、完全に格子ＬｈＮＴが決定され、その結果、署名者は、格子の半分の短い基底だけを有する。したがって、署名者は、既知の短いベクトル（ｆ、ｇ）を使用して、（ｆ、ｇ）と一緒にＬｈＮＴを生成する相補的な短いベクトル（Ｆ、Ｇ）を見つける必要がある。適当な（Ｆ、Ｇ）の効率的な構成は、重要な作業であり、この理論的アルゴリズム及び実用的アルゴリズムを、セクション５で説明する。
【００４９】
署名の偽造によって、ＮＴＲＵ格子のクラスに関して高次元で（近似）最近接ベクトル問題を解く能力が暗示されることを示す。有効な署名の任意長のトランスクリプトに含まれる情報も分析し、署名作成に使用される包括的な方法により、この方向からの攻撃の実現可能性が劇的に減ることを示す。
【００５０】
セクション１で、ＮＴＲＵＳＩＧＮの非常に短い説明から始める。この論文の残り（最後のセクションを除く）では、この最初のセクションで説明する署名方式の説明、拡充、及び正当化を提供する。
【００５１】
したがって、この論文の本体は、セクション２の、ＮＴＲＵＥＮＣＲＹＰＴ及びＮＴＲＵＳＩＧＮによって使用される畳み込みモジュール格子と困難な格子問題の概要から始まる。セクション３では、鍵作成処理の新しい態様を示し、ＮＴＲＵＳＩＧＮの署名プロトコル及び検証プロトコルを示す。また、ＲＳＡ  １０２４と同等レベルのセキュリティのための特定のパラメータ選択を示す。セクション４では、公開鍵から、直接、有効なＮＴＲＵＳＩＧＮ署名を作成する問題が、古典的な最近接ベクトル問題にどのように緊密に結び付けられるかを説明する。セクション５では、鍵作成の説明を完成させ、秘密ベクトル（ｆ、ｇ）の知識を与えられて、ＮＴＲＵ格子の完全な短い基底を見つける方法を説明する。セクション６では、長いトランスクリプトの分析から、攻撃者が最小限の情報しか与えられないことを示す。セクション７では、ＮＴＲＵＳＩＧＮをさらに効率的なＮＳＳと称する署名方式にする方法を説明し、基礎となるＣＶＰへのＮＴＲＵＳＩＧＮ署名の直接リンクとの補助的な合同（ある弱さにつながる）を介するアド・ホックな文書エンコーディング方法と対比する。
【００５２】
１．ＮＴＲＵＳＩＧＮの短い概要
ＮＴＲＵＳＩＧＮを短く説明する。さらなる詳細は、この論文の残りのセクションで示す。すべての多項式積がＸＮ−１を法とする。
【００５３】
公開パラメータ：次元パラメータＮ、法ｑ、鍵サイズ・パラメータｄｆ及びｄｇ並びに検証限度パラメータＮｏｒｍＢｏｕｎｄを選択する。
【００５４】
鍵生成：ｄｆ個の１を有する２進多項式ｆ及びｄｇ個の１を有する２進多項式ｇを選択する。公開鍵ｈ≡ｆ−１＊ｇ  （ｍｏｄ  ｑ）を計算する。ｆ＊Ｇ−ｇ＊Ｆ＝ｑを満足する小さい多項式（Ｆ、Ｇ）を計算する。
【００５５】
署名：ディジタル文書Ｄをハッシュ化して、ランダム・ベクトル（ｍ１、ｍ２）  ｍｏｄ  ｑを作成する。
【００５６】
Ｇ＊ｍ１−Ｆ＊ｍ２＝Ａ＋ｑ＊Ｂ
−ｇ＊ｍ１＋ｆ＊ｍ２＝ａ＋ｑ＊ｂ
のＢ及びｂを計算する。ここで、Ａ及びａは、−ｑ／２とｑ／２の間の係数を有する。Ｄに対する署名は、
ｓ≡ｆ＊Ｂ＋Ｆ＊ｂ  （ｍｏｄ  ｑ）
によって与えられる多項式ｓである。
【００５７】
検証：ディジタル文書Ｄをハッシュ化して、（ｍ１、ｍ２）を再作成する。ｔ≡ｓ＊ｈ  （ｍｏｄ  ｑ）を計算する。
【００５８】
‖ｓ−ｍ１‖２＋‖ｔ−ｍ２‖２≦ＮｏｒｍＢｏｕｎｄ２
であることを検証する。
【００５９】
提案されるパラメータ：下記のパラメータは、ＲＳＡ  １０２４によって提供されるものと同等の強さのセキュリティを提供する、すなわち、１０１２ＭＩＰＳ−年より大きな解読時間の有すると推定される。
【００６０】
Ｎ＝２５１、ｑ＝１２８、ｄｆ＝７３、ｄｇ＝７１、ＮｏｒｍＢｏｕｎｄ＝３１０
【００６１】
２．ＮＴＲＵ格子及び関連するベクトル問題
ＮＴＲＵ公開鍵暗号システム（ＮＴＲＵＥＮＣＲＹＰＴ）及び関連するＮＴＲＵ署名方式（ＮＴＲＵＳＩＧＮ）では、２つの公開パラメータＮ及びｑが使用される。通常の選択は、（Ｎ、ｑ）＝（２５１、１２８）と（Ｎ、ｑ）＝（５０３、２５６）である。基本的な演算は、畳み込み多項式の環で行われる。
【００６２】
Ｒ＝＜Ｚ＞［Ｘ］／（ＸＮ−１）
多項式ａ（Ｘ）＝ａ０＋ａ１Ｘ＋…＋ａＮ−１ＸＮ−１∈Ｒは、座標（ａ０、ａ１、…、ａＮ−１）∈＜Ｚ＞Ｎのベクトルによって識別される。Ｒの２つの多項式の積は、単純にその対応するベクトルの畳み込み積であることに留意する。
【００６３】
要素ａ∈＜Ｚ＞［Ｘ］／（ＸＮ−１）のサイズを測定する明白な方法は、ベクトル係数のユークリッド・ノルム（Σａｉ）１／２によるものである。しかし、環Ｒ及びその副格子を扱う時に［６、７］、下記の形で定義されるセンタリングされたノルムを扱う方がよい。μａ＝（１／Ｎ）Σａｉが、多項式ａ（Ｘ）∈Ｒの係数の平均値を表すものとする。ａのセンタリングされたノルム‖ａ‖は、
【００６４】
【数１】
2005515659.tif 000003
によって定義される。ランダムに選択される多項式ａ及びｂについて、ノルムは、準乗算的である。
【００６５】
‖ａ＊ｂ‖＝‖ａ‖−‖ｂ‖
【００６６】
Ｒの要素のｎ組を検討する時に、これらを同一の値を中心としてセンタリングしなければならない理由はない。一般に、ａ、ｂ、…、ｃ∈Ｒのｎ組（ａ、ｂ、…、ｃ）のセンタリングされたノルムは、次式によって定義される。
【００６７】
‖（ａ、ｂ、…、ｃ）‖２＝‖ａ‖２＋‖ｂ‖２＋…＋‖ｃ‖２    （２）
注３。センタリングされたノルムが、単に、係数のベクトルを（１、１、…、１１）に直交する空間に射影した後のユークリッド・ノルムであることに留意する。センタリングされたノルムを使用することが最善である理由は、攻撃者が、必ずセンタリングされたベクトルから開始し、したがって、センタリングされないノルムを使用することによって得られるものがないからである。数学的には、センタリングされたノルムの縮小は、分解
【００６８】
【数２】
2005515659.tif 000004
によって反映される。これによって、本質的に、攻撃者が、第２の因数で作業できるようになる。この分解によって、Ｎを素数にしなければならず、あるいは少なくとも小さい素数の因数を有してはならないことが重要である理由も示される。というのは、Ｎが因数分解される場合に、＜Ｚ＞［Ｘ］／（ＸＮ−１）のさらなる分解があるからである。この観測は、Ｎが多数の因数を有する時のＮＴＲＵ格子に対するＧｅｎｔｒｙの攻撃［２］の下にある。
【００６９】
多項式
ｈ（Ｘ）＝ｈ０＋ｈ１Ｘ＋ｈ２Ｘ２＋…＋ｈＮ−１ＸＮ−１∈Ｒ
に関連する畳み込みモジュール格子Ｌｈは、
ｖ（Ｘ）＝ｈ（Ｘ）＊ｕ（Ｘ）  （ｍｏｄ  ｑ）
を満足するベクトルの集合（ｕ、ｖ）∈Ｒ×Ｒ≡＜Ｚ＞２Ｎである。Ｌｈが、行列
【００７０】
【数３】
2005515659.tif 000005
の行によって生成されることは簡単にわかる。畳み込みモジュール格子は、（ｕ、ｖ）∈Ｌｈの場合に、
（Ｘｉ＊ｕ、Ｘｉ＊ｖ）∈Ｌｈ  総ての０≦ｉ＜Ｎについて
なので、回転不変性を有する。回転のそれぞれ（Ｘｉ＊ｕ、Ｘｉ＊ｖ）が、（ｕ、ｖ）と同一の（センタリングされた）ノルムを有することに留意する。（ｕ、ｖ）及びそのすべての回転によって生成されるＬｈの部分格子又は（ｕ、ｖ）によって生成されるＲ２のＲサブモジュールを、Ｒ＊（ｕ、ｖ）と書く。
【００７１】
Ｍｉｃｃｉａｎｃｉｏ［１８］は、Ｌｈの行列が、エルミート標準形（Ｈｅｒｍｉｔｅ  Ｎｏｒｍａｌ  Ｆｏｒｍ）で与えられることを観察した。すべての行列を、多項式時間でエルミート標準形にすることができるので、Ｌｈの行列が、Ｌｈ内の短いベクトルに関する最小限の可能な量の情報を伝えるといえる。
【００７２】
多項式ｈが、
ｈ≡ｆ−１＊ｇ  （ｍｏｄ  ｑ）
の形の分解を有する場合に、小さい係数（小さいの正確な定義については下を参照）を有する多項式ｆ及びｇについて、Ｌｈが、ＮＴＲＵ格子であると言い、これをＬｈＮＴと表す。
【００７３】
目標は、ＮＴＲＵ公開鍵暗号システム及びＮＴＲＵ署名方式を、ＬｈＮＴの格子問題に直接に関連させることである。これを行うために、下記の定義及び前提を設ける。
【００７４】
（１）セキュリティ・パラメータＮ及びｑは、
ｑ＝Ｏ（Ｎ）
によって関連する。実際には、一般に、１／３Ｎ≦ｑ≦２／３Ｎとする。
【００７５】
（２）小さい多項式は、係数がＯ（１）である、すなわち、係数がＮと独立の限度を有する多項式である。小さい多項式ａ（Ｘ）の（センタリングされた）ノルムは、次式を満足する。
【００７６】
‖ａ‖＝Ｏ（√Ｎ）
注４。ガウシアン・ヒューリスティック（Ｇａｕｓｓｉａｎ  ｈｅｕｒｉｓｔｉｃ）によって、「ランダム」格子の特性を予測する方法が提供される。このヒューリスティックに関して、以下の作業で有用ないくつかの発言を行う。詳細については［６］又は［７］を参照のこと。
【００７７】
（１）ガウシアン・ヒューリスティックでは、「ランダム」格子Ｌ（高次元の）の最短ベクトルが、約
λＧａｕｓｓ（Ｌ）＝√（ｄｉｍ（Ｌ）／２πｅ）・Ｄｅｔ（Ｌ）１／ｄｉｍ（Ｌ）
のサイズを有すると予測する。同様に、Ｌの最近接ベクトル問題は、そのサイズが約λＧａｕｓｓ（Ｌ）の解を有する。
【００７８】
（２）一般の畳み込みモジュール格子Ｌｈは、次元２Ｎ及び行列式ｑＮを有し、したがって、可能な最短ベクトル及び最近接ベクトルは、約
λＧａｕｓｓ（Ｌｈ）＝√（Ｎｑ／πｅ）＝Ｏ（Ｎ）    （３）
のサイズを有する。Ｌｈに、長さｑ＝Ｏ（Ｎ）のＮ個の線形に独立のベクトルが含まれる、すなわち、その行列の下側Ｎ行にベクトルが含まれる。これらの「ｑベクトル」の小さい線形の組み合わせだけが、Ｌｎの長さＯ（Ｎ）の明白なベクトルである。
【００７９】
（３）（ｕ、ｖ）∈Ｌｈの場合に、ｑを法とするｕ及びｖの座標を縮小することによって得られるベクトルは、Ｌｈに含まれる。したがって、Ｌｈに長さＯ（ｑ√（Ｎ））＝Ｏ（Ｎ３／２）の多数のベクトルが含まれる。さらに、所与のベクトルへの距離が多くともＯ（Ｎ３／２）であるベクトルをＬｈで見つけるのは簡単である。
【００８０】
（４）ＮＴＲＵ格子ＬｈＮＴでは、多項式ｈが、小さい多項式ｆ及びｇに関してｈ≡ｆ−１＊ｇ  ｍｏｄ  ｑの形であり、したがって、ＬｈＮＴに短いベクトル（ｆ、ｇ）が含まれる。より一般的には、すべての回転（Ｘｉ＊ｆ、Ｘｉ＊ｇ）が、長さＯ（√Ｎ）を有するＬｈＮＴの短いベクトルである。ガウシアン・ヒューリスティックに基づけば、これらの秘密の短いベクトルは、おそらくは、それがまたぐ部分空間Ｒ＊（ｆ、ｇ）内のどのベクトルよりもＯ（√Ｎ）だけ小さい。
【００８１】
定義１。ＬｈＮＴがＮＴＲＵ格子であるものとする。ＮＴＲＵ格子鍵問題は、ＬｈＮＴで長さＯ（√Ｎ）のベクトルを見つけることである。
【００８２】
注５。ＮＴＲＵ格子ＬｈＮＴに、長さＯ（√Ｎ）のベクトルによって生成される部分空間Ｒ＊（ｆ、ｇ）が含まれ、したがって、ＮＴＲＵ格子鍵問題は、必ず解を有する。ガウシアン・ヒューリスティックによって、部分空間Ｒ＊（ｆ、ｇ）から線形に独立のＬｈＮＴの最短ベクトルが、長さＯ（Ｎ）を有することが予測される。したがって、ＮＴＲＵ格子鍵問題のすべての解が、短い乗算（ｕ＊ｆ、ｕ＊ｇ）によって、すなわち、ｕ∈Ｒａとしてサイズ‖ｕ‖＝Ｏ（１）の多項式によって与えられる。
【００８３】
３．ＮＴＲＵＳＩＧＮ：鍵作成、署名及び検証
このセクションでは、ＮＴＲＵＳＩＧＮ鍵生成と、ＮＴＲＵＳＩＧＮの署名及び検証プロトコルを説明する。次のセクションで、ＮＴＲＵＳＩＧＮ署名によって近似ＣＶＰが解かれる理由を説明する。
【００８４】
３．１．鍵生成。  ＮＴＲＵＥＮＣＲＹＰＴ公開鍵／秘密鍵対で、秘密鍵は、小さい係数を有し、‖ｆ‖＝‖ｇ‖＝Ｏ（√Ｎ）を満足する２つの多項式ｆ及びｇからなり、公開鍵は、合同
ｈ≡ｆ−１＊ｇ  （ｍｏｄ  ｑ）
によって定義される多項式ｈである［６］。
【００８５】
ＮＴＲＵＳＩＧＮの秘密鍵／公開鍵対は、正確に同一の形で作成される。鍵作成者は、（ｆ、ｇ）を選択し、ｈ≡ｆ−１＊ｇ  （ｍｏｄ  ｑ）を形成する。しかし、鍵作成者は、秘密鍵の一部として、
ｆ＊Ｇ−ｇ＊Ｆ＝ｑ、かつ  ‖Ｆ‖、‖Ｇ‖＝Ｏ（Ｎ）
を満足する２つの追加の多項式Ｆ及びＧも計算する。（ｆ、ｇ）及び（Ｆ、Ｇ）の回転によって、Ｌｈの基底が形成されることに留意されたい。これについてはセクション５の補助定理２を参照のこと。
【００８６】
セクション５では、所与の（ｆ、ｇ）に関する（Ｆ、Ｇ）対の効率的な計算の方法を説明する。正確に言えば、ｆ及びｇが、所与の定数ｃについて、
‖ｆ‖≒ｃ√Ｎ  かつ  ‖ｇ‖≒ｃ√Ｎ    （４）
を満足するように選択される場合に、
‖Ｆ‖≒‖Ｇ‖≒ｃＮ／（√１２）    （５）
を満足する関連する（Ｆ、Ｇ）を見つけることが可能である。当座は、署名者が自分の裁量でそのような（Ｆ、Ｇ）対を有すると仮定する。
【００８７】
３．２．署名。  ディジタル文書Ｄに署名するために、署名者は、まず、Ｄをハッシュ化して、ｑを法とする２つのランダムな多項式ｍ１及びｍ２からなるメッセージ・ダイジェストｍ＝（ｍ１、ｍ２）を作る。Ｄに対する署名は、ｍに非常に近いベクトル（ｓ、ｔ）∈ＬｈＮＴである。署名者は、自分の短い基底ベクトルの＜Ｑ＞線形組合せとして（ｍ１、ｍ２）を表し、係数を最も近い整数に丸めることによって、（ｓ、ｔ）を見つける。格子の「よい基底」を使用してＣＶＰを近似的に解くこの標準的な方法は、暗号学での使用に関して、既に［４］で提案されている。
【００８８】
アルゴリズム的には、ＮＴＲＵ格子のこの手順を、次のように記述することができる。
【００８９】
・式
Ｇ＊ｍ１−Ｆ＊ｍ２＝Ａ＋ｑ＊Ｂ
−ｇ＊ｍ１＋ｆ＊ｍ２＝ａ＋ｑ＊ｂ      （６）
によって、多項式ａ、ｂ、Ａ、Ｂ∈＜Ｚ＞［Ｘ］／（ＸＮ−１）を計算する。ここで、ａ及びＡは、−ｑ／２とｑ／２の間の係数を有するように選択される。
【００９０】
・多項式ｓ及びｔを、
ｓ≡ｆ＊Ｂ＋Ｆ＊ｂ  （ｍｏｄ  ｑ）
ｔ≡ｇ＊Ｂ＋Ｇ＊ｂ  （ｍｏｄ  ｑ）      （７）
として計算する。多項式ｓは、公開鍵ｈに関するディジタル文書Ｄに対する署名である。
【００９１】
注６。実際には、署名の作成にはｂ及びＢだけが必要であり、ｓだけが、署名を形成するのに必要である。
【００９２】
（ｓ、ｔ）＝Ｂ＊（ｆ、ｇ）＋ｂ＊（Ｆ、Ｇ）  （ｍｏｄ  ｑ）
と書くことができるので、（ｓ、ｔ）が、ＮＴＲＵ格子ＬｈＮＴに含まれることも観察される。
【００９３】
注７。有理数の係数を有する多項式Ｐ（Ｘ）∈＜Ｑ＞［Ｘ］に関して、表記［Ｐ］を使用して、Ｐの各係数を最も近い整数に丸めることによって得られる多項式を表す。すると、署名処理全体を、次の行列の式によって要約することができ、次式は、ＣＶＰの近似解を見つける標準的な方法で短い基底｛（ｆ、ｇ）、（Ｆ、Ｇ）｝を使用していることを示す。
【００９４】
【数４】
2005515659.tif 000006
３．３．検証。  ｓが、メッセージ・ダイジェストｍ＝（ｍ１、ｍ２）及び公開鍵ｈの推定のＮＴＲＵＳＩＧＮ署名であるものとする。この署名は、署名者が、メッセージ・ダイジェスト・ベクトルｍに十分に近いＬｈＮＴの格子点を知っていることが実証される場合に有効である。したがって、検証は、下記の２つのステップからなる。
【００９５】
・多項式
ｔ≡ｈ＊ｓ  （ｍｏｄ  ｑ）
を計算する（定義により、（ｓ、ｔ）が格子ＬｈＮＴの点であることに留意）。
【００９６】
・（ｓ、ｔ）から（ｍ１、ｍ２）への（センタリングされた）距離を計算し、それが事前に指定された値ＮｏｒｍＢｏｕｎｄより小さいことを検証する。言い換えると、
‖（ｓ−ｍ１、ｔ−ｍ２）‖≦ＮｏｒｍＢｏｕｎｄ    （９）
であることを検査する。
【００９７】
３．４．検証が動作する理由。  有効な署名によって、署名者が、メッセージ・ダイジェスト・ベクトルｍからＮｏｒｍＢｏｕｎｄ以内の格子点を知っていることが実証される。明らかに、ＮｏｒｍＢｏｕｎｄを小さく設定するほど、偽造者が、秘密鍵の知識なしでこの問題を解くことが難しくなる。したがって、署名者によって有効な署名を効率的に生成できるようにしながら、限度ＮｏｒｍＢｏｕｎｄをどれほど小さく設定できるかを分析することが重要である。
【００９８】
（６）及び（７）から（又は（８）を使用して）、
【００９９】
【数５】
2005515659.tif 000007
を計算することができる。ａ及びＡの係数が、−ｑ／２とｑ／２の間であり、したがって、
ｍ１−ｓ＝ε１＊ｆ＋ε２＊Ｆ、かつ、ｍ２−ｔ＝ε１＊ｇ＋ε２＊Ｇ      （１０）
であることが想起される。ここで、ε１＝Ａ／ｑ及びε２＝ａ／ｑは、係数が−１／２と１／２の間である多項式である。
【０１００】
ｍ１及びｍ２は、すべてのｍｏｄ  ｑ多項式にまたがって変化するので、Ａがすべてのｍｏｄ  ｑ多項式にまたがって均一に変化することを検査するのは簡単であり、したがって、事実上、ε１の係数を、区間（−１／２、１／２）に均一に分布する独立のランダム変数として扱うことができる。したがって、平均して、‖ε１‖≒√（Ｎ／１２）が得られる。類似する注が、ａ及びε２にも適用され、したがって、‖ε２‖≒√（Ｎ／１２）が得られる（注１３参照）。
【０１０１】
次に、‖ε１‖≒‖ε２‖≒√（Ｎ／１２）及びノルムの準乗算性を使用して、（ｓ、ｔ）から（ｍ１、ｍ２）への距離
【０１０２】
【数６】
2005515659.tif 000008
を推定することができる。
【０１０３】
３．５．ＮＴＲＵＳＩＧＮのサンプル・パラメータ・セット。  後続のセクションからわかるように、下記のパラメータ・セットは、破るのに少なくともＲＳＡ  １０２４ビット鍵と同様の労力すなわち、約１０１２ＭＩＰＳ−年を要すると思われる。
【０１０４】
（Ｎ、ｑ、ｃ）＝（２５１、１２８、０．４５）    （１２）
ここで、ｃは、式（４）及び（５）によって定義される。実際には、ｆ及びｇを、ｆが７３個の１及び１７８個の０を有し、ｇが７１個の１及び１８０個の０を有する２進多項式として選択する（ｆ（１）及びｇ（１）が比較的素であることが必要であり、さもなければ、（ｆ、ｇ）をＬｈＮＴの基底全体に拡張することができない）。
【０１０５】
パラメータ（１２）によって、（１１）の右辺で４６６０１≒２１５．８７２の限度が作られる。これは、期待される距離の平均値である。したがって、（９）のノルム限度、例えばＮｏｒｍＢｏｕｎｄ＝２５０を満足する署名を見つけることは、完全に実現可能である。
【０１０６】
しかし、実際には、そのような厳密なノルム限度を設定する必要はない。格子縮小又は他の偽造方法によって、ノルムが４００を大きく下回る署名を作成できないことがわかるので、ＮｏｒｍＢｏｕｎｄ＝３１０という設定によって、安全なディジタル署名方式が与えられると思われる。正確に言うと、このノルム限度を用いると、ＮＴＲＵＳＩＧＮに対する最強の攻撃は、公開鍵から秘密鍵を回復する直接格子攻撃である。この攻撃は、長年にわたって完全に研究されている。というのは、これが、公開鍵からのＮＴＲＵＥＮＣＲＹＰＴ秘密鍵の回復と同一になるからである。
【０１０７】
３．６．プロトタイプ・タイミング結果。  ８００ＭＨｚのＰｅｎｔｉｕｍ（登録商標）ＩＩＩプロセッサ上で走る、Ｃでコンパイルされた、署名、検証及び鍵生成アルゴリズムが機能するプロトタイプ実施形態を作った。上で説明したパラメータ、Ｎ＝２５１、ｑ＝１２８、ｄｆ＝７３及びｄｇ＝７１を用いて、このプログラムは、毎秒約２０００個の文書に署名することができ、毎秒約３０００個の文書を検証することができる。まだ完全には最適化されていない鍵生成は、１つの鍵を生成するのに、反復係数Ｂ＝５０００（注１１参照）を用いて約１．５秒を要し、この時間の大半は、ノルム‖（Ｆ、Ｇ）‖≒４５のベクトル（Ｆ、Ｇ）を計算するのに使用された。鍵生成アルゴリズムの実行時間は、大幅に短縮できると期待される。
【０１０８】
４．ＮＴＲＵＳＩＧＮ及び近似最近接ベクトル問題
ＮＴＲＵＳＩＧＮ署名を偽造するためには、偽造者が、メッセージ・ダイジェスト点に十分に近い格子点を作ることができなければならない、すなわち、偽造者は、ＮＴＲＵ格子の近似ＣＶＰ問題を解かなければならないことが明白である。このセクションでは、公開鍵から直接にメッセージの署名を作ることの難しさを検討する。すなわち、ｆ及びｇの知識なしで、有効な署名のトランスクリプトの使用可能性もなしで、（９）を満足する対（ｓ、ｔ）∈ＬｈＮＴを作ることの難しさを検討する。したがって、所与の近似限度内でこれらの格子でＣＶＰを解くことがどれほど難しいかを調べる。この問題を解く既知の手法は、下記だけである。
（Ａ）近い格子点を突き止める格子縮小技法。
（Ｂ）網羅探索すなわち、格子点を推測し、それが近いことを期待するか、近い点を推測し、それが格子点であることを期待すること。
（Ｃ）（Ａ）及び（Ｂ）の組み合わせ。
【０１０９】
４．１．格子縮小を使用するＮＴＲＵＳＩＧＮ攻撃。  格子縮小を使用する明白な形は、ＬｈＮＴで非常に短い非０ベクトルを見つけることを試みることである。というのは、（ｆ、ｇ）及びその回転が、おそらくは最短のそのようなベクトルになるからである。パラメータ選択（１２）を用いると、この問題は、同一のパラメータを有するＮＴＲＵＥＮＣＲＹＰＴ公開鍵を破る問題と同等になる。経験から、パラメータ（１２）に関して、推定される解読時間は、１０１２ＭＩＰＳ年を超える。
【０１１０】
格子縮小を使用するもう１つの形は、有効な署名（ｓ、ｔ）を直接に突き止めることを試みることである。この問題は、明らかに、最近接ベクトル問題（ａｐｐｒ−ＣＶＰ）の近似になる。というのは、署名（ｓ、ｔ）が、ハッシュ関数を介してディジタル文書から生成された非格子点に近い格子点になる必要があるからである。一般に、「適度にランダムな」格子について、ａｐｐｒ−ＣＶＰの難しさは、格子の次元及びランダムに選択された点から格子の再も近い点までの期待される距離によって測定される。ガウシアン・ヒューリスティック（３）によって、空間内の点からＬｈＮＴ内の点までの期待される距離は、√（Ｎｑ／πｅ）になると示される。したがって、潜在的な偽造者は、空間内のランダムな点を提示され、所与の点までの距離が多くとも、ＬｈＮＴの実際に最も近い点までの期待される距離の
【０１１１】
【数７】
2005515659.tif 000009
倍であるＬｈＮＴの点を突き止めなければならない。
【０１１２】
（１２）に記載の特定のパラメータについて、ガウス値は、√（Ｎｑ／πｅ）≒６１．３である。したがって、ＮｏｒｍＢｏｕｎｄ＝３１０をセットすることは、偽造者が、期待される最短距離の５．０６倍以内の点を見つける必要があることを意味し、ＮｏｒｍＢｏｕｎｄ＝２２５の場合には、この比率が３．６７に下がる。広範な実験から、この近似最近接ベクトル問題を解くことは、この比が１に近づくにつれて困難になることが示されている。具体的に言うと、提案されたパラメータ（１２）について、この近似ＣＶＰを解くことは、比が、ＮｏｒｍＢｏｕｎｄ＝４８５に対応する７．９１ほどの大きさであっても、公開鍵を破る（すなわち、（ｆ、ｇ）を直接に見つける）ことより難しい。
【０１１３】
注８。重要な問題は、畳み込みモジュール格子の（近似）最短ベクトル問題及び（近似）最近接ベクトル問題が、より一般的なクラスの格子と同じ程度に難しいか否かである。これは、確かに、興味深い問題である。一般的な格子の最短ベクトル又は最近接ベクトルを近似する原理的な方法として、ＬＬＬアルゴリズム［１５］と、その一般化及び機能強化である［１２、１３、１４、２１、２２、２４］等がある。現在の状況は、標準的なＬＬＬ型格子縮小アルゴリズムより、かなりよく作用する、畳み込みモジュール格子用の特別なアルゴリズムがない（この領域の研究については［１６］参照）ことであり、格子縮小アルゴリズムの畳み込みモジュール格子への作用は、一般的な格子への作用より、よくはないと考えられる。
【０１１４】
４．２．網羅探索を使用するＮＴＲＵＳＩＧＮへの攻撃。  ＮＴＲＵＳＩＧＮ署名を偽造するのに網羅探索を使用することの難しさを分析するために、まず、空間内でランダムに選択される整数点がＬｈに含まれる確率が、ｑ−Ｎにすぎないことを観察した。畳み込みモジュール格子Ｌｈでａｐｐｒ−ＣＶＰを解き、したがってＮＴＲＵＳＩＧＮ署名を偽造する試みのより効率的な方法は、Ｃｒａｉｇ  Ｇｅｎｔｒｙ、Ｊａｋｏｂ  Ｊｏｎｓｓｏｎ及びＪａｃｑｕｅｓ  Ｓｔｅｒｎ（［３］参照）によって独立に言及された。彼らは、攻撃者が、所望の値を有するようにｓ及びｔの係数の半分を事前に選択し、残りのＮ個の係数について
ｔ≡ｈ＊ｓ  （ｍｏｄ  ｑ）
を解くことができることを観察した。これによって、格子Ｌｈの点（ｓ、ｔ）が作られ、その座標の半分が、攻撃者によって自由に選択される。もちろん、他のＮ個の座標は、一般にランダムで均一に分布するｑの剰余である。
【０１１５】
したがって、攻撃者は、格子点（ｓ、ｔ）を簡単に作成することができ、その結果、差（ｍ１、ｍ２）−（ｓ、ｔ）の座標の半分が消え、残りの半分は、独立で均一に分布するｑの剰余である。したがって、この手法の成功の確率は、区間［−ｑ／２、ｑ／２］からランダムに均一に選択されるＮ個の整数の二乗和が、ＮｏｒｍＢｏｕｎｄ２未満になる確率である。この確率の正確な推定値を得ることは、驚くほど難しいが、下記の基本的な上界が、この目的には十分である。
【０１１６】
命題１。Ｑが、実数の有限の集合であり、ｑ＝＃Ｑであり、Ｘ１、…、ＸＮが、Ｑで均一に分布する独立のランダム変数であり、Ｙ＝√（Ｘ１２＋…＋ＸＮ２）であるものとする。すべてのＡ＞０及びすべてのｌ＞０について、
【０１１７】
【数８】
2005515659.tif 000010
特に
【０１１８】
【数９】
2005515659.tif 000011
である。
【０１１９】
証明。集合Ｑから選択された座標を有する球‖ｘ‖≦Ａの点の数を推定する。したがって、
【０１２０】
【数１０】
2005515659.tif 000012
である。
【０１２１】
【表１】
2005515659.tif 000013
【０１２２】
【表２】
2005515659.tif 000014
ｘの座標は、集合Ｑで独立に均一に選択されるので、
【０１２３】
【数１１】
2005515659.tif 000015
である。これによって、命題の第１部分の証明が終わる。
【０１２４】
第２の推定値は、ｔ＝Ｎ／２Ａ２とすることによって、第１の推定値から得られる。
【０１２５】
この命題に、下記のパラメータを適用する。
【０１２６】
Ｎ＝２５１、ｑ＝１２８、Ｑ＝｛−６４、−６３、…、６３｝
その結果を、表１に示す。この表を調べると、３８０程度として選択されたＮｏｒｍＢｏｕｎｄであっても、この方法による成功の確率を無視できることは明らかである。
【０１２７】
注９。命題１で示した分析は、近似にすぎない。というのは、センタリングされたノルムではなく、標準ノルムが使用されたからである。しかし、これによって生じる差はわずかである。というのは、大多数のランダムなｍｏｄ  ｑベクトルについて、係数の平均値が非常に小さいからである。厳密な数学的分析は、かなり複雑であり、したがって、下記の実験を使用して例を示す。Ｎ＝２５１及びｑ＝１２８の１００００個のランダムなｍｏｄ  ｑベクトルを計算し、各ベクトルについて、標準ノルム及びセンタリングされたノルムを計算した。表２には、わずかな相違だけが示されている。命題１は、上界であり、この上界が必要な値よりはるかに小さくなるようにパラメータを選択したので、標準ノルムの代わりにセンタリングされたノルムを使用することの小さい影響は、このセキュリティ推定に影響しない。
【０１２８】
注１０。実際に、古典的なθ関数の関数式を適用して、命題１の上界をわずかに改善することができる。
【０１２９】
【数１２】
2005515659.tif 000016
【０１３０】
【表３】
2005515659.tif 000017
４．３．格子縮小と網羅探索の組み合わせによるＮＴＲＵＳＩＧＮへの攻撃。  ２つの方法を組み合わせる可能性が残されている。したがって、偽造者は、Ｎ個より多少少ない座標を事前に選択し、より低次元の格子に格子縮小技法を使用して、残りの座標を見つけることができる。したがって、偽造者が０≦α≦１のある選択について、ｓ及びｔのαＮ個の座標を事前に選択すると仮定する。偽造者は、（２−α）Ｎ次元の格子及び行列式ｑＮ（１＋α）に対して格子縮小技法を使用して、残りの（１−α）Ｎ個の座標をできるだけ小さくする。α＝０が、純粋な格子縮小に対応し、α＝１が、純粋な網羅探索に対応することに留意する。αが増えるにつれて、基本的な比（（１３）参照）
【０１３１】
【数１３】
2005515659.tif 000018
が小さくなり、これが１未満になる時に、ガウシアン・ヒューリスティックから、解が存在する可能性が非常に低いことがわかる。表３に、ＮｏｒｍＢｏｕｎｄのさまざまな値に対する、αの最大の許容可能な値と、対応する格子次元を示す。例えば、ＮｏｒｍＢｏｕｎｄ＝３１０によって、α＝０．３８３５の値が得られるが、これは、４０５次元の格子に対応する。したがって、格子縮小攻撃によって、４０５次元未満（５０２からの低下）に減らすことは期待できない。さらに、次元が４０５に向かって減らされる時に、次元の削減から得られる利益は、少なくとも部分的に、ガウス比の減少に起因して少なくなる。
【０１３２】
５．ＮＴＲＵＳＩＧＮ鍵の作成
このセクションでは、署名アルゴリズムに必要な鍵を生成する方法すなわち、その回転がＮＴＲＵ格子の基底を形成する２つのベクトルを見つける方法を示す。そのようなベクトルを見つける複数の方法のうち、１つだけを説明することに留意することが重要である。この処理をできる限り効率的にすることが、現在の研究課題である。
【０１３３】
以下では、環＜Ｚ＞［Ｘ］又は＜Ｚ＞［Ｘ］／（ＸＮ−１）の要素を有する２×２行列を検討するが、このどちらの環を使用するかは、文脈から明らかである。そのような行列の行列式は、＜Ｚ＞［Ｘ］又は＜Ｚ＞［Ｘ］／（ＸＮ−１）の要素である。目的は、行列の所与の上の行をとり、行列式がｑと等しくなる下の行を見つけることである。
【０１３４】
この目標を達成するために、２つの多項式ｆ及びｇを与えられたと仮定する。例えば、ｆ及びｇは、それぞれｄｆ個及びｄｇ個の１と等しい係数を有し、残りの係数が０である２進多項式とすることができる。Ｆ１、Ｇ１∈＜Ｚ＞［Ｘ］は、行列
【０１３５】
【数１４】
2005515659.tif 000019
が＜Ｚ＞［Ｘ］／（ＸＮ−１）でユニモジュラーになる、すなわち、
ｄｅｔ（Ｍ１）＝ｆ＊Ｇ１−ｇ＊Ｆ１≡１  （ｍｏｄ  ＸＮ−１）    （１５）
終結式を使用して、そのようなＦ１、Ｇ１を見つけるが、これが、Ｆ１及びＧ１を見つける唯一の方法ではなく、最も効率的な方法でもないことには留意する。
【０１３６】
標準的な方法を使用することにより開始して、
ｆ＊ｖ＋ｋ１＊（ＸＮ−１）＝Ｒｆ、    （１６）
ｇ＊ｕ＋ｋ２＊（ＸＮ−１）＝Ｒｇ、    （１７）
を満足する多項式ｕ、ｖ∈＜Ｚ＞［Ｘ］を見つける。ここで、Ｒｆは、（ｆ、ＸＮ−１）の（整数）終結式、Ｒｇは、（ｇ、ＸＮ−１）の（整数）終結式である。終結式Ｒｆ及びＲｇが互いに素であると仮定し、（整数）拡張ユークリッド・アルゴリズムを適用して、
αＲｆ＋βＲｇ＝１
を満足する整数α及びβを得る。これらの関係を組み合わせることによって、式
（αｖ）＊ｆ＋（βｕ）＊ｇ＝１  （ｍｏｄ  ＸＮ−１）
が得られる。したがって、ｇｃｄ（Ｒｆ、Ｒｇ）＝１である限り、多項式Ｆ１＝−βｕ及びＧ１＝αｖが見つかっており、その結果、（１４）によって定義される行列Ｍ１によって、ユニモジュラー条件（１５）が満足される。
【０１３７】
終結式が互いに素でない場合には、異なるｆ及びｇを選択することができる。ｆ及びｇの初期テストをすばやく実行して、その終結式が互いに素でない可能性が高いかどうかを調べることも可能である。重要な観察の１つが、ｆ（１）によってＲｆが割り切れ、ｇ（１）によってＲｇが割り切れ、したがって、ｇｃｄ（Ｒｆ、Ｒｇ）＝１の必要条件が、
ｇｃｄ（ｆ（１）、ｇ（１））＝１
になることである。また、Ｎが素数であり、ｐが、ｐ≡１  （ｍｏｄ  Ｎ）を満足する素数である場合に、
【０１３８】
【数１５】
2005515659.tif 000020
であることが観察された。具体的に言うと、ｐ＝２Ｎ＋１が素数である場合に、Ｒｆ及びＲｇのそれぞれが、ｐによって割り切られる可能性が約３９．３％であり、したがって、計算の残りを進める前に、これらの少なくとも１つが２Ｎ＋１によって割り切れないことを検査する価値がある可能性がある。
【０１３９】
ユニモジュラー行列（１４）を得たならば、必要な行列式を得ることはささいな問題である。というのは、第２行に定数をかけることができるからである。したがって、行列式ｑを有する行列を作るために、
Ｆｑ＝ｑＦ１  かつ  Ｇｑ＝ｑＧ１
とし、行列
【０１４０】
【数１６】
2005515659.tif 000021
を形成する。したがって、
ｄｅｔ（Ｍｑ）＝ｆ＊Ｇｑ−ｇ＊Ｆｑ＝ｑ    （１９）
になる。
【０１４１】
命題２。（１８）によって定義される行列Ｍｑの行によって、ｈに関連するＮＴＲＵ格子Ｌｈが生成される、すなわち、これによって、行列
【０１４２】
【数１７】
2005515659.tif 000022
の行と同一の格子が生成される。ここで、通常通り、＜Ｚ＞［Ｘ］／（ＸＮ−１）でｈ＝ｆ−１＊ｇ  （ｍｏｄ  ｑ）である。
【０１４３】
証明。変換行列Ｈ＝Ｍ’Ｍｑ−１が行列式１を有し、Ｈが＜Ｚ＞［Ｘ］／（ＸＮ−１）の項目を有することを示せば十分である。ｄｅｔ（Ｍｑ）＝ｄｅｔ（Ｍ’）＝ｑであることがわかっているので、ｄｅｔ（Ｈ）＝１である。次に、
【０１４４】
【数１８】
2005515659.tif 000023
を計算する。構成によってｆ＊ｈ≡ｇ  （ｍｏｄ  ｑ）なので、この最後の行列が、＜Ｚ＞［Ｘ］／（ＸＮ−１）の項目を有することは明らかである。したがって、Ｈは、ユニモジュラー変換行列であり、したがって、Ｍｑ及びＭ’の行によって、同一の格子が生成される。
【０１４５】
行列Ｍｑの行によって、ＮＴＲＵ格子Ｌｈが生成されるが、これらは、近いベクトルを直接に見つけるのに有用ではない。というのは、終結式の構成が、係数が非常に大きい多項式Ｆｑ及びＧｑにつながるからである。センタリングされたノルムを減らす（２）ことによって、（Ｆｑ、Ｇｑ）を小さくする。
【０１４６】
Ｍｑの第２行のノルムを減らす鍵は、第１行の倍数だけこれを変更できることを観察することである。というのは、これによって、その行によって生成される格子が変化しないからである。多項式ｆ及びｇは、既に非常に小さく、これらのセンタリングされた回転は、互いに適度に直交し、したがって、この縮小も非常によく働く（この処理を、部分的によい基底を用いるａｐｐｒ−ＣＶＰの解と見なすことができる）。
【０１４７】
この縮小が機能することを説明し、その有効性を測定するために、前の終結式の計算（１６、１７）からの情報を再利用する。Ｍｑの第１列から始める。Ｆｑからｆの倍数ｋ＊ｆを引いて、これを小さくしたい。ａｐｐｒ−ＣＶＰを解く「逆技法」は、ｋ≒Ｆｑ＊ｆ−１をとることであり、ここで、ｆ−１は、＜Ｑ＞［Ｘ］／（ＸＮ−１）のｆの逆関数である。終結式の関係（１６）を使用すると、
ｆ−１＝ｕ／Ｒｆ∈＜Ｑ＞［Ｘ］／（ＸＮ−１）
であることがわかる。したがって、ｋ＝［ｕ／Ｒｆ］とする。すなわち、ｋ∈Ｚ［Ｘ］／（ＸＮ−１）は、ｕ／Ｒｆを最も近い整数に丸めることによって得られる。ｋのこの選択を用いて、Ｆ＝Ｆｑ−ｋ＊ｆとする。このＦは、
Ｆ＝Ｆｑ−ｋ＊ｆ＝Ｆｑ−［Ｆｑ＊ｆ−１］＊ｆ＝（Ｆｑ＊ｆ−１−［Ｆｑ＊ｆ−１］）＊ｆ＝εｆ＊ｆ
を満足する。ここで、εｆは、区間［−１／２、１／２］内の係数を有する。さらに、εｆの係数は、この区間に多少均一に独立に分布するので、平均して‖εｆ‖＝√（Ｎ／１２）が得られる。したがって、
‖Ｆ‖≒‖εｆ‖・‖ｆ‖≒‖ｆ‖√（Ｎ／１２）
である。
【０１４８】
これによって、Ｍｑの左下の要素を小さくすることができるが、右下の要素についても同じことを同時に行いたい。言い換えると、小さい結果を得るためにＧｑからｇの倍数を引きたい。問題は、ＦｑをＦｑ−ｋ＊ｆに置換する場合に、ＧｑをＣｑ−ｋ＊ｇに置換する必要があり、同一のｋを使用しなければならないことである。その一方で、Ｇｑに使用される「正しい」ｋが、ｋ≒Ｇｑ＊ｇ−１であることがわかっている。つまり、Ｆｑに正しいｋと、Ｇｑに正しいｋはほぼ等しい。これが正しい理由を調べるために、関係（１９）をｆ＊ｇで割ると、
Ｇｑ／ｇ＝Ｆｑ／ｆ＋ｑ／（ｆ＊ｇ）
が得られる。したがって、Ｇｑ＊ｇ−１とＦｑ＊ｆ−１の間の差は、約
【０１４９】
【数１９】
2005515659.tif 000024
のサイズを有する。パラメータの実用的な組（１２）について、この量は、２．４９と等しく、これは、平均して、Ｇｑ＊ｇ−１及びＦｑ＊ｆ−１の係数が、０．１５７だけ異なることを意味する。このセクションの結果を組み合わせて、下記の結果が証明された。
【０１５０】
命題３。通常通りにｆ、ｇ∈＜Ｚ＞［Ｘ］／（ＸＮ−１）であり、ｈ＝ｆ−１＊ｇ  （ｍｏｄ  ｑ）であるものとする。Ｆｑ、Ｇｑ∈＜Ｚ＞［Ｘ］／（ＸＮ−１）が、
ｆ＊Ｇｑ−ｇ＊Ｆｑ＝ｑ
を満足するものとする。
【０１５１】
【数２０】
2005515659.tif 000025
とすると、行列
【０１５２】
【数２１】
2005515659.tif 000026
の行によって、ＮＴＲＵ格子Ｌｈが生成され、Ｆ及びＧは、ノルム
‖Ｆ‖≒‖ｆ‖√（Ｎ／１２）、‖Ｇ‖≒‖ｇ‖√（Ｎ／１２）
を有する。
【０１５３】
注１１。秘密の基底のサイズによって、近似ＣＶＰをどれほどよく解けるかが決定される。この理由から、実際には、（Ｆ、Ｇ）から（ｆ、ｇ）の倍数をさらに引いて、ノルムを減らすことを試みることが有用である。したがって、ｉ＝０、１、２、…、Ｂについて、ベクトル
（Ｆ、Ｇ）−Ｘｉ＊（ｆ、ｇ）
が（Ｆ、Ｇ）より小さいことをテストすることによって、縮小の最後のステージ実行する。そうである場合には、より小さいベクトルによって（Ｆ、Ｇ）を置換し、継続する。Ｂ＞Ｎの場合であっても改善が見つかる可能性があることには留意する。というのは、ｉの後続の値によって修正が行われる場合に、前に使用されたｉの値によってノルムを減らすことができるからである。
【０１５４】
注１２。終結式計算によって、より大きいベクトル（Ｆ、Ｇ）が作られる。（２０）で与えられる式を使用して（Ｆ、Ｇ）を修正することによって、このベクトルをはるかに小さくしてきた。これは、ＦとＧを別々に扱うことに対応する。実際には、これらを一緒に扱うことによってより小さい結果を得ることができるが、これは、多少の追加の終結式計算を必要とする。導出を省略し、単に、ｋの望ましい値が、
【０１５５】
【数２２】
2005515659.tif 000027
であることを示す。
【０１５６】
【数２３】
2005515659.tif 000028
【０１５７】
６．トランスクリプト分析
このセクションでは、各署名されたメッセージから攻撃者が得る情報を分析する。署名ベクトルとメッセージ・ダイジェスト・ベクトルの差が、多くともＮｏｒｍＢｏｕｎｄのノルムの短いベクトルである。署名ベクトルは、格子ベクトルであるが、メッセージ・ダイジェスト・ベクトルは、＜Ｚ＞２Ｎ  ｍｏｄ  ｑのランダムな点である。トランスクリプトを、差分（ｍ１、ｍ２）−（ｓ、ｔ）のリストと見なすが、この差分のそれぞれは、短いベクトルである。
【０１５８】
（１）メッセージ・ダイジェストは、ランダム・オラクルとして振る舞うハッシュ関数を使用して作成されると仮定しているので、能動的な攻撃者（選択されたメッセージの署名を求める攻撃者）は、受動的な攻撃者（署名されたメッセージのトランスクリプトを分析するのみの攻撃者）以上の情報を得ない。
【０１５９】
（２）署名差分ベクトルが、半径ＮｏｒｍＢｏｕｎｄの球面に（又は球内に）均一に分布する場合に、トランスクリプトから、ａｐｐｒ−ＣＶＰを解くのに有用な情報は作られない。
【０１６０】
第２のポイントは、非常に強い言明であり、多少の正当化を必要とする。本質的に、攻撃者自身がこの形のトランスクリプトを作成することができるのは事実である。攻撃者は、ランダムな格子点ａ１、ａ２、…を選択し、長さがＮｏｒｍＢｏｕｎｄと等しい（またはそれより小さい）ランダムなベクトルｒ１、ｒ２、…を選択し、自分のトランスクリプトとして、「メッセージ・ダイジェスト」ａ１＋ｒ１、ａ２＋ｒ２、…に対する「署名」ａ１、ａ２、…をとる。したがって、仮定（２）の下で、トランスクリプトを使用してａｐｐｒ−ＣＶＰを解く効率的なアルゴリズムが存在する場合に、トランスクリプトを必要としないａｐｐｒ−ＣＶＰを解く効率的なアルゴリズムが存在する（これは真でないと思われる）。
【０１６１】
上の２つの点を考慮に入れることは、攻撃者が利用を試みることができるトランスクリプト情報だけが、署名の差が半径ＮｏｒｍＢｏｕｎｄの球面上（または球体内）にランダムに分布しないという事実に起因することを意味する。
【０１６２】
セクション３．４で注記したように、よい基底（ｆ、ｇ）及び（Ｆ、Ｇ）を使用してａｐｐｒ−ＣＶＰを解くのに使用される方法は、式
【０１６３】
【数２４】
2005515659.tif 000029
につながる。ここで、Ａ及びａは、−ｑ／２とｑ／２の間で選択される座標を有するｍｏｄ  ｑベクトルである。正確には、これらは、合同
Ａ≡Ｇ＊ｍ１−Ｆ＊ｍ２  （ｍｏｄ  ｑ）
ａ≡−ｇ＊ｍ１＋ｆ＊ｍ２  （ｍｏｄ  ｑ）    （２２）
によって決定される。（２２）から、ｍ１及びｍ２が、すべてのｍｏｄ  ｑベクトルにまたがって変化するので、Ａの値が、すべてのｍｏｄ  ｑベクトルにまたがって均一に変化し、ａも同様であることは明らかである。
【０１６４】
注１３。ａとＡが互いに独立であることは、真でない。実際に、
ｆ＊Ａ≡−Ｆ＊ａ  （ｍｏｄ  ｑ）    （２３）
であることを検査するのは簡単である。したがって、所与の（ｆ、Ｆ）について、ａによってＡが決定され、逆も同様であることがわかる。これはセキュリティ問題ではない。というのは、合同（２３）が、単に、（２１）のｍ１−ｓの式が整数の係数を有することの言い換えにすぎないからである。
【０１６５】
第１の座標ｍ１−ｓに集中することができる。というのは、第２の座標が、第１座標並びに公知の情報ｈ及びｍによって決定されるからである。したがって、トランスクリプトから攻撃者に漏らされる情報は、正確に（Ａ／ｑ）＊ｆ＋（ａ／ｑ）＊Ｆ（ｑの剰余に縮小されない）であり、ここで、Ａ及びａの係数は、関係（２３）の対象になるランダムなｍｏｄ  ｑ多項式である。
【０１６６】
十分に多くの署名があれば、攻撃者が、（ｆ、ｇ）及び（Ｆ、Ｇ）（及びその回転）がまたがる平行六面体を再構成できる可能性が高いが、これは、長さがＮの指数のトランスクリプトを使用しなければ実現可能でないと思われる（最低限でも、＜Ｒ＞２Ｎの各象限で少なくとも１つの署名を有する必要があり、したがってＯ（２２Ｎ）個の署名が必要である）。
【０１６７】
（ｆ、ｇ）及び（Ｆ、Ｇ）がまたがる平行六面体内でランダムに選択された点のリストから攻撃者が演繹できる情報の量を正確に解くことは、興味深い問題である。攻撃者が、計算的に実現可能な時間のうちに有用な情報を演繹することができる可能性は、非常に低いと思われる。これは、進行中の研究の分野である。
【０１６８】
７．最適化及び機能強化
このセクションでは、ＮＴＲＵＳＩＧＮをさらに効率的にするのに使用することができるさまざまな方法を説明する。これらの方法の一部は、セキュリティの考慮点を有し、したがって、特定の応用例で使用する前に、注意して分析しなければならない。
【０１６９】
７．１．メッセージ・ダイジェストの短縮。  （ｍ１、ｍ２）の形のメッセージ・ダイジェストを使用するのではなく、（０、ｍ）の形のメッセージ・ダイジェストを使用する方が効率的であることわかっている。このセクションでは、そのような変更がセキュリティに対する悪影響を及ぼさず、実際には好ましい可能性があることを示す、ＮＴＲＵ格子の基底の特性を説明する。
【０１７０】
したがって、（０、ｍ）の形のメッセージ・ダイジェストに対する署名のトランスクリプトが、任意の点に対する署名（ｍ１、ｍ２）より多くの情報が漏らすか否かを調べる。鍵となる観察は、（ｓ、ｔ）が点（ｍ１、ｍ２）に対するＮＴＲＵＳＩＧＮ署名である場合に、格子点（ｘ、ｙ）に関して、格子点（ｓ＋ｘ、ｔ＋ｙ）が、点（ｍ１＋ｘ、ｍ２＋ｙ）に対する署名であることに留意することである。
【０１７１】
（ｘ、ｙ）＝−（ｍ１、ｍ１＊ｈ  ｍｏｄ  ｑ）
をとると、すべての署名を、（０、ｍ）の形のメッセージ・ダイジェストに対する署名に変換できることがわかる。したがって、（０、ｍ）の形のメッセージ・ダイジェストに署名することによって、（ｍ１、ｍ２）の形の一般的なメッセージ・ダイジェストに署名することより多くの情報が攻撃者に提供されることはない。
【０１７２】
対（ｍ１、ｍ２）の空間は、サイズｑ２Ｎを有するが、署名だけを決定する対（ａ、Ａ）の対応する空間あｈ、注１３で説明したようにサイズｑＮを有する。（０、ｍ）の形のメッセージ・ダイジェストを使用することは、メッセージ・ダイジェストが、所与の基底（ｆ、ｇ、Ｆ、Ｇ）を使用して作成される署名と、１対１対応関係にあることを意味する。
【０１７３】
７．２．メッセージ・ダイジェスト及び鍵の積の形。  最初のＮＴＲＵ公開鍵暗号システムについて、一部の多項式（例えば、ｍ、ｆ、ｇ）が複数のまばらな２進多項式の積になるようにすることによって、かなりの効率の利得を達成することができる（［１１、８］参照）。そのような手法によって、検索する空間が明らかに減るが、正しく実施される場合に、攻撃者に他の利益は与えられないと考えられる。もちろん、検索する空間は、中間一致（ｍｅｅｔ−ｉｎ−ｔｈｅ−ｍｉｄｄｌｅ）攻撃をくじくのに十分に大きくなるように設計しなければならない。
【０１７４】
類似する形で、ある多項式が積になるようにすることによってＮＴＲＵＳＩＧＮの効率を高めることが可能である。例えば、ｆ、ｇ及び／又はｍが、まばらな２進多項式の積になるようにすることができる。
【０１７５】
７．３．ｍｏｄ  ｑ縮小を用いるセンタリングされたノルムの計算。  「小さい」ｍｏｄ  ｑベクトルのセンタリングされたノルムを計算する時には、ベクトルを正しくセンタリングすることが重要である。したがって、例えば、検証者は、ｔ  ｍｏｄ  ｑだけを知り、真のｔの中心（すなわち、ｍｏｄ  ｑに縮小されないｔの真の値）がｑ／２又は−ｑ／２に近い場合には、センタリングされたノルムは、ｍｏｄ  ｑに縮小される前にｔの係数がシフトされなければ、正しくなくなる。これを行う２つの形がある。非効率的な形は、ｔのシフトのすべてを調べ、それぞれｑを法として縮小し、どれが最小のノルムを与えるかを検査することである。よりよい手法は、ｔの係数として現れない、ｑを法とする連続する値の最長の列を見つけ、この列の中央が−ｑ／２になるようにｔをシフトすることである。第３の手法は、Ｘ＝１でのさまざまな多項式の値を知っているという事実を使用して、センタリング値のあるべき場所を演繹することである。この第３の手法は、暗号化解除処理中にＮＴＲＵＥｎｃｒｙｐｔによって使用される手法である。
【０１７６】
７．４．転置格子の使用。  セクション７．２の積最適化を使用する場合に、セクション５で説明した鍵生成アルゴリズムの単純な修正によって、さらなる最適化を可能にすることができる。この発想は、行列式ｑの行列の転置行列を使用することである。長所は、積の構造を有するようにｆ及びｇを選択できることであるが、Ｆｑ及びＧｑが積になることを強制することはできない。最終的に、エルミート標準形の公開鍵ｈ及び普通のＮＴＲＵ格子Ｌｈになることに留意する。
【０１７７】
以前の構成では、１つの非常に短いベクトル（ｆ、ｇ）及び１つの適度に短いベクトル（Ｆ、Ｇ）からなる基底になった。この新しい転置構成では、基底（ｆ、Ｆ）及び（ｇ、Ｇ）が得られ、この２つの基底ベクトルは、ほぼ同じサイズであるが、第１座標が短く、第２座標が長い。そのような基底を与えられれば、２つの半分の寄与が等しくなるようにノルムに重みを付けることが自然である。
【０１７８】
この新しい格子のセキュリティを調べるさらなる研究が行われる必要があるが、これを使用することには明らかな効率の利益がある。ａｐｐｒ−ＣＶＰは、「長方形」基底よりも「正方形」基底を用いてよりよく解くことができるので、セキュリティの長所もある可能性がある。
【０１７９】
８．ＮＳＳの発達史
このセクションでは、ＮＳＳと呼ばれる、ＮＴＲＵ格子に基づく、初期のディジタル署名方法の歴史を簡単に再検討する。これを行うのは、欠陥のあるディジタル文書に署名を添付する方法が、どのようにＮＳＳの深刻な弱点につながったかを示し、基礎となるａｐｐｒ−ＣＶＰへのＮＴＲＵＳＩＧＮ署名の直接的なリンクにより、ＮＴＲＵＳＩＧＮがＮＳＳからどのように区別され、以前の方式の弱点から解放されたかを説明するためである。
【０１８０】
Ｅｕｒｏｃｒｙｐｔ  ２００１で説明された［７］ＮＳＳエンコーディング方法は、小さい素数ｐの剰余の補助合同条件の使用を介して、ディジタル文書が署名に直接に組み込まれた。Ｇｅｎｔｒｙ、Ｊｏｎｓｓｏｎ及びＳｔｅｒｎ（［３］参照）によって、独立に、このエンコーディング方法の弱点が、秘密鍵の知識なしで直接に署名を偽造するのに使用できることが発見された。それと同時に、Ｓｚｙｄｌｏ（同じく［３］参照）は、有効な署名の長いトランスクリプトから鍵を回復できるようになる、合同条件を利用するもう１つの方法を見つけた。
【０１８１】
この弱さの源は、ＮＳＳ法の、ＮＴＲＵ格子の（近似）最近接ベクトル問題への不完全なリンクであった。正確に言うと、署名は、下記の意味での最近接ベクトル問題への解を示した。空間内の点が、メッセージ・ダイジェストに関連付けられ、メッセージ・ダイジェスト点に適度に近いＮＴＲＵ格子内の点が、秘密鍵（その格子内の短いベクトル）の知識を使用して、構成された。有効な署名として受け入れられるために、格子点は、メッセージ・ダイジェスト点に十分に近いことが必要であり、その座標は、補助素数ｐを法とするある統計的特性を満足しなければならなかった。
【０１８２】
［７］で、指定された距離は、格子縮小法による偽造を不可能にするのに十分に小さかったが、異なる手法による偽造を不可能にするのに十分に小さくはなかった。Ｇｅｎｔｒｙ、Ｊｏｎｓｓｏｎ及びＳｔｅｒｎによるこの手法は、ｍｏｄ  ｐ統計条件を迂回することにも成功した。さらに、Ｓｚｙｄｌｏは、署名点を作成する特定の方法によって、ある周波数分布の分析によって署名の長いトランスクリプトから秘密鍵情報を抽出できるようになることに注目した。
【０１８３】
［７］のプレゼンテーションで、その著者は、エンコーディング技法に対する単純な修正によって、これらの方向からの攻撃の可能性がどれほど除去されるかを説明した。具体的に言うと、署名点とメッセージ・ダイジェスト点の間の関係は、最近接ベクトル問題にはるかに密に結び付けられ、効果的に直接偽造の可能性が除去された。しかし、多少アド・ホックな方法を使用して、必要なｍｏｄ  ｐ統計特性を満足する署名点が偽造された。
【０１８４】
Ｃｒｙｐｔｏ  ’０１のランプ・セッションで、Ｇｅｎｔｒｙ及びＳｚｙｄｌｏは、修正されたＮＳＳ法によって作られる有効な署名のトランスクリプトから、効果的に鍵サイズを半分に切り詰めるのに十分な情報が漏らされることを実証した論文を提示した。彼らは、漏らされる情報を潜在的に使用して多項式時間で完全な鍵を回復する方法も説明した。この方法では、ＮＳＳ署名ベクトルがメッセージ・ダイジェスト及び秘密鍵から構成される特定の方法の弱さが利用された。ＮＳＳの秘密鍵ｆ及び公開鍵ｈに、特殊な形が課せられ、これによって、（近似）ＣＶＰをすばやく効率的に解くことができるようになった。しかし、これは、署名が積ｆ＊ｗに密に関連することを意味した。Ｇｅｎｔｒｙ及びＳｚｙｄｌｏは、署名からのｆ＊ｗ及び関連する積ｆ＊ｆの発見に成功し、この２つの積の知識によって、多項式時間でｆを回復するのに十分な情報が得られた。
【０１８５】
ＮＳＳが基づく原理は、非常に単純であった。署名者は、ＮＴＲＵ格子内の短いベクトルの秘密の知識を有する。メッセージ・ダイジェストから生じる空間内の任意の点を与えられて、署名者は、この知識を使用して、ＮＴＲＵ格子内でメッセージ点に近い点を見つける。署名者は、この近似ＣＶＰに対する解を、自分の署名として示す（ＧＧＨ方式［４］と比較のこと）。
【０１８６】
ＮＳＳの弱さは、署名者が、ＮＴＲＵ格子ＬｈＮＴの短いベクトルの完全な基底を所有しないという事実から生じた。署名者は、その代わりに、１つの短い２Ｎ次元ベクトル（ｆ、ｇ）の知識を所有し、このベクトルの回転が、格子の半分にまたがった。署名者の知識は部分的なものにすぎないので、署名者は、特定の構成による近似ＣＶＰに対するどちらかといえば弱い解を作製した。この構成の一般的でない性質によって、前に説明した扉が攻撃者に開かれた。
【０１８７】
ＮＳＳとは対照的に、ＮＴＲＵＳＩＧＮでの署名と基礎になるａｐｐｒ−ＣＶＰの間のリンクは、明瞭直接である。まず一般的なＮＴＲＵ格子の秘密（ｆ、ｇ）ベクトルを使用して、格子の完全な短い基底を構成する。次に、メッセージ・ダイジェストを、２Ｎ次元空間内の任意の点に写像する。署名は、メッセージ・ダイジェスト点に非常に近い格子点であり、包括的な形で、ＮＴＲＵ格子の短いベクトルの完全な基底を使用して発見される。したがって、署名によって、ＮＴＲＵ格子の一般（近似）最近接ベクトル問題に対する直接の非常に鋭い回答が提供される。実行される追加テストはなく、検証される補助ｍｏｄ  ｐ条件はない。検証は、単純に、署名点がＮＴＲＵ格子内にあることと、それがメッセージ・ダイジェスト点から要求される半径の中にあることの検査からなる。
【０１８８】
参考文献
[1] E.F.Brickell and K.S.McCurley, “Interactive Identification and Digital Signature”, AT&T Technical Journal, 1991年11/12月, P73-86
[2] C.Gentry, “Key recovery and message attacks on NTRU-composite”, Advances in Cryptology-Eurocrypt ’01, Lecture Notes in Computer Science, Springer-Verlag, 2001年
[3] Craig Gentry, Jakob Jonsson, Jacques Stern, Michael Szydlo, “Cryptanalysis of the NTRU Signature Scheme(NSS) from Eurocrypt 2001”, Advances in Cryptology-Asiacrypt `01, Lecture Notes in Computer Science, Springer-Verlag, 2001年
[4] O.Goldreich, S.Coldwasser, S.Halvei, “Public-key cryptography from lattice reduction problems” In Proc.CRYPTO’97, Lecture Notes in Computer Science 1294, Springer-Verlag, 1997年, P112-131
[5] L.C.Guillou and J.-J.Quisquater, “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory”, Advances in Cryptology-Eurocrypt ’88, Lecture Notes in Computer Science 330, Springer-Verlag, 1988年, P123-128
[6] J.Hoffstein, J.Pipher, J.H.Silverman, “NTRU: A new high speed public key cryptosystem”, in Algorithmic Number Theory (ANTS III), Portland, OR., Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998年, P267-288
[7] J.Hoffstein, J.Pipher, J.H.Silverman, “NSS: An NTRU Lattice-based Signature Scheme”, Advances in Cryptology-Eurocrypt ’01, Lecture Notes in Computer Science, Springer-Verlag, 2001年
[8] J.Hoffstein, J.Pipher, J.H.Silverman, “Enhanced Encoding and Verification Methods for the NTRU Signature Scheme”, NTRU Technical Note #017, 2001年5月, www.ntru.com
[9] J.Hoffstein, D.Lieman, J.H.Silverman, “Polynomial Rings and Efficient Public Key Authentication”, in Proceeding of the International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC’99), Hong Kong, (M.Blum and C.H.Lee編), City University of Hong Kong Press.
[10] J.Hoffstein, J.H.Silverman, “Polynomial Rings and Efficient Public Key Authentication II”, in Proceeding of a Conference on Cryptography and Number Theory (CCNT’99), (I.Shparlinski編), Birkhauser
[11] J.Hoffstein, J.H.Silverman, “Optimizations for NTRU”, Public-Key Cryptography and Computational Number Theory, Warsaw, 2000年9月11-15日
[12] H.Koy, C.-P.Schnorr, “Segment LLL-Reduction of Lattice Bases”, Cryptography and Lattice Conference-Proceedings of CaLC’01, J.Silverman編, Lecture Notes in Computer Science, Springer-Verlag, 2001年3月, P67-80
[13] H.Koy, C.-P.Schnorr, “Segment LLL-Reduction with Floating Point Orthogonalization”, Cryptography and Lattice Conference-Proceedings of CaLC’01, J.Silverman編, Lecture Notes in Computer Science, Springer-Verlag, 2001年3月, P81-96
[14]J.Lagarias, H.W.Lenstra Jr, C.P.Schnorr, “Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice”, Combinatorica 10, 1990年, P333-348
[15] A.K.Lenstra, H.W.Lenstra Jr, L.Lovasz, “Factoring polynominals with rational coefficients”, Mathematische Ann.261, 1982年, P513-534
[16] A.May, J.H.Silverman, “Dimension reduction methods for convolution modular lattices”, Cryptography and Lattice Conference-Proceedings of CaLC’01, J.Silverman編, Lecture Notes in Computer Science, Springer-Verlag, 2001年3月, P110-125
[17] A.J.Menezes, P.C. van Oorschot, S.A.Vamstone, “Handbook of Applied Cryptography”, CRC Press, 1996年
[18] D.Micciancio, “Improving lattice based cryptosystems using Hermite normal form”, Cryptography and Lattice Conference-Proceedings of CaLC’01, J.Silverman編, Lecture Notes in Computer Science, Springer-Verlag, 2001年3月, P126-145
[19] P.Nguyen, “Cryptanalysis of the Goldreich-Goldwasser-Halvei Cryptosystem from Crypto’97”, Advances in Cryptology-Proceedings of CRYPTO’99, M.Wiener編, Lecture Notes in Computer Science, Springer-Verlag, 1999年8月15-19日
[20] T.Okamoto, “Provably secure and practical identification schemes and corresponding signature schemes”, Advances in Cryptology-Crypto’92, Lecture Notes in Computer Science 740, E.F.Brickell編, Springer-Verlag, 1993年, P31-53
[21] C.-P.Schnorr, “A hierarchy of polynomial time lattice basis reduction algorithms”, Theoretical Computer Science 53, 1987年, P201-224
[22] C.-P.Schnorr, “A more efficient algorithm for lattice basis reduction”, J.Algorithms 9, 1988年, P47-62
[23] C.-P.Schnorr, “Efficient identification and signature for smart cards”, Advances in Cryptology-Crypto’89, Lecture Notes in Computer Science 435, G.Brassard編, Springer-Verlag, 1990年, P239-251
[24] C.-P.Schnorr, M.Euchner, “Lattice basis reduction : improved practical algorithms and solving subset sum problems”, Math Programming 66, No.2, Ser.A, 1994年, P181-199
[25] J.Stern, “A new identification schemes with key of short size”, Advances in Cryptology-Crypto’93, Lecture Notes in Computer Science 773, D.Stinson編, Springer-Verlag, 1994年, P13-21
[26] J.Stern, “Designing identification schemes with key of short size”, Advances in Cryptology-Crypto’94, Lecture Notes in Computer Science 839, Y.G.Desmedt編, Springer-Verlag, 1994年, P164-173
[27] D.stinson, “Cryptography: Theory and Practice”, CRC Press, 1997年
【図面の簡単な説明】
【０１８９】
【図１】本発明の実施形態の実施に用いるシステムのブロック図である。
【図２】本発明の典型的な実施形態による鍵作成技法を示すフロー図である。
【図３】本発明の典型的な実施形態によるユーザ識別技法を示すフロー図である。
【図４】本発明の典型的な実施形態によるディジタル署名技法を示すフロー図である。
【符号の説明】
【０１９０】
５０  チャネル
１０３  キーボード
１０５、１５５  サブシステム
１１０、１６０  プロセッサ
１１８  入出力機能
１２１、１７３  クロック＆タイミング回路
１２３、１６８  メモリ
１２５、１７６  モニタ
１３５、１６２  トランシーバ
【図１】
2005515659.tif 000030
【図２】
2005515659.tif 000031
【図３】
2005515659.tif 000032
【図４】
2005515659.tif 000033
【国際調査報告】
2005515659.tif 000034
2005515659.tif 000035