Lattice-based public key cryptosystem
NTRUEncrypt 公開鍵暗号システムは 、 NTRU 暗号化アルゴリズム とも呼ばれ 、 RSA および 楕円曲線暗号 (ECC)に代わる NTRU 格子ベースの暗号であり、格子内の 最短ベクトル問題 に基づいています( 量子コンピュータ を使用して解読できることは知られていません )。
これは、切断 多項式環 内の特定の多項式を、非常に小さな係数を持つ2つの多項式の商に因数 分解する ことが困難であると想定されていることに依拠しています。この暗号システムの解読は、特定の 格子 における 格子縮約 というアルゴリズムの問題と強く関連していますが、同等ではありません。公開されている攻撃を阻止するには、パラメータを慎重に選択する必要があります。
暗号化と復号化はどちらも単純な多項式乗算のみを使用するため、RSA、 ElGamal 、 楕円曲線暗号 といった他の非対称暗号化方式と比較して非常に高速です。しかしながら、NTRUEncryptは、実用化段階では、まだ同等の量の暗号解析が行われていません。
関連するアルゴリズムとして、 NTRUSign デジタル署名 アルゴリズムがあります。
具体的には、NTRU 演算は畳み込み乗算を含む切り捨て多項式環内のオブジェクトに基づいており 、環内のすべての多項式は 整数 係数 と最大 N -1 の次数を持ちます。 R = Z [ X ] / ( X N − 1 ) {\displaystyle \ R=\mathbb {Z} [X]/(X^{N}-1)}
a = a 0 + a 1 X + a 2 X 2 + ⋯ + a N − 2 X N − 2 + a N − 1 X N − 1 {\displaystyle {\textbf {a}}=a_{0}+a_{1}X+a_{2}X^{2}+\cdots +a_{N-2}X^{N-2}+a_{N-1}X^{N-1}} この環において、多項式に を乗じると、多項式の係数が 回転 するという効果があります。 したがって、 を固定した に対して の形の写像は、 の非零係数の 数と同じ数の の係数に依存する新しい多項式を生成します 。 X N = 1 {\displaystyle X^{N}=1} X {\displaystyle X} f ↦ f g {\displaystyle f\mapsto fg} g ∈ R {\displaystyle g\in R} f g {\displaystyle fg} f {\displaystyle f} g {\displaystyle g}
NTRU には 3 つの整数パラメータ ( N 、 p 、 q ) があり、 N は多項式の次数境界、 p は小係数、 qは大係数と呼ばれます。 N は 素数 、 qは常に p より (はるかに) 大きく 、 p と qは 互いに素で ある と仮定します 。 平文メッセージは p を 法とする多項式です が、 暗号文メッセージは q を法とする多項式です。 具体的には、暗号文は平文メッセージとランダムに選択された公開鍵の倍数で構成されますが、公開鍵自体は小係数 p の倍数と見なすことができ 、秘密鍵の所有者は暗号文から平文を抽出できます。
歴史 NTRUEncrypt公開鍵暗号システムは比較的新しい暗号システムです。このシステムの最初のバージョンは、単にNTRUと呼ばれ、1996年頃に3人の数学者（ ジェフリー・ホフスタイン 、 ジル・ピファー 、 ジョセフ・H・シルバーマン ）によって開発されました。1996年、これらの数学者はダニエル・リーマンと共にNTRU Cryptosystems, Inc.を設立し、この暗号システムに関する特許 [1] （現在は失効）を取得しました。
過去10年間、人々は暗号システムの改良に取り組んできました。暗号システムが初めて発表されて以来、システムのパフォーマンスとセキュリティの両方を向上させるためにいくつかの変更が行われました。パフォーマンスの向上の大部分は、処理の高速化に重点が置かれていました。 [ 詳細な説明が必要 ] 2005年まで、NTRUEncryptの復号失敗を説明する文献が見つかりました。 [ 引用が 必要 ] セキュリティに関しては、NTRUEncryptの最初のバージョン以降、現在[ 具体的に ] 知られているすべての攻撃に対して安全と思われる[ 説明が必要 ]新しいパラメータが導入され 、 計算 能力 も 適度 に 向上 し まし た。 [ 説明 が必要 ]
現在、このシステムは、格子ベース公開鍵暗号（ IEEE P1363.1 ）の仕様に基づき、IEEE P1363規格に完全に準拠しています 。NTRUEncrypt公開鍵暗号システムは、その高速性（ベンチマーク結果についてはhttp://bench.cr.yp.toを参照）とメモリ使用量の少なさ（下記参照） [ 疑わしい – 議論の余地あり ]により、モバイルデバイスや スマートカード などのアプリケーションで利用可能です 。2011年4月、NTRUEncryptは金融サービス業界での使用を目的としたX9.98規格として承認されました。 [2]
公開鍵生成 アリスからボブに秘密のメッセージを送信するには、公開鍵と秘密鍵を生成する必要があります。公開鍵はアリスとボブの両方が知っており、秘密鍵はボブのみが知っています。鍵のペアを生成するには、 次数が最大で係数が {-1,0,1} である 2 つの多項式 f と g が必要です。これらは、 R を法とする多項式の留数クラスの表現と考えることができます 。この多項式は、 逆元 modulo q および modulo p ( ユークリッド互除法 ) が存在するという追加要件も満たす必要があり、これは 、および が成立する必要があることを意味します。そのため、選択した f が逆元でない場合、ボブは戻って別の f を試す必要があります。 N − 1 {\displaystyle \ N-1} X N − 1 {\displaystyle \ X^{N}-1} f ∈ L f {\displaystyle {\textbf {f}}\in L_{f}} f ⋅ f p = 1 ( mod p ) {\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}} f ⋅ f q = 1 ( mod q ) {\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}}
f と （および） は ボブの秘密鍵である。公開鍵 h は、以下の量を計算することで生成される
。 f p {\displaystyle \ \mathbf {f} _{p}} g {\displaystyle \mathbf {g} }
h = p f q ⋅ g ( mod q ) . {\displaystyle {\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {q}}.} 例 ：この例では、パラメータ（ N 、 p 、 q ）は N = 11、 p = 3、 q = 32となり、多項式 f と g の次数は10以下となります。システムパラメータ（ N 、 p 、 q ）は誰もが知っています。多項式はランダムに選択されるため、次のように表されるとします。
f = − 1 + X + X 2 − X 4 + X 6 + X 9 − X 10 {\displaystyle {\textbf {f}}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}} g = − 1 + X 2 + X 3 + X 5 − X 8 − X 10 {\displaystyle {\textbf {g}}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}} ユークリッドの互除法を用いて、それぞれ pを法とする f の逆関数 と q を法とする逆関数を計算する。
f p = 1 + 2 X + 2 X 3 + 2 X 4 + X 5 + 2 X 7 + X 8 + 2 X 9 ( mod 3 ) {\displaystyle {\textbf {f}}_{p}=1+2X+2X^{3}+2X^{4}+X^{5}+2X^{7}+X^{8}+2X^{9}{\pmod {3}}} f q = 5 + 9 X + 6 X 2 + 16 X 3 + 4 X 4 + 15 X 5 + 16 X 6 + 22 X 7 + 20 X 8 + 18 X 9 + 30 X 10 ( mod 32 ) {\displaystyle {\textbf {f}}_{q}=5+9X+6X^{2}+16X^{3}+4X^{4}+15X^{5}+16X^{6}+22X^{7}+20X^{8}+18X^{9}+30X^{10}{\pmod {32}}} これはアリスとボブの両方に知られている公開鍵 h を作成し、積を計算する。
h = p f q ⋅ g ( mod 32 ) = 8 − 7 X − 10 X 2 − 12 X 3 + 12 X 4 − 8 X 5 + 15 X 6 − 13 X 7 + 12 X 8 − 13 X 9 + 16 X 10 ( mod 32 ) {\displaystyle {\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {32}}=8-7X-10X^{2}-12X^{3}+12X^{4}-8X^{5}+15X^{6}-13X^{7}+12X^{8}-13X^{9}+16X^{10}{\pmod {32}}}
暗号化 アリスはボブに秘密のメッセージを送りたいと考え、メッセージを係数が の多項式 m の形で表現します 。現代の暗号化アプリケーションでは、メッセージ多項式は2進数または3進数表現に変換できます。メッセージ多項式を作成した後、アリスは メッセージを隠蔽するために、小さな係数（{-1,0,1}の集合に限定されない）を持つ
多項式 rをランダムに選択します。 [ − p / 2 , p / 2 ] {\displaystyle [-p/2,p/2]}
ボブの公開鍵 h を使って暗号化されたメッセージ e が計算されます。
e = r ⋅ h + m ( mod q ) {\displaystyle {\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {q}}} この暗号文にはアリスのメッセージが隠されており、ボブに安全に送信できます。
例 : アリスが多項式で表せるメッセージを送信したいとします。
m = − 1 + X 3 − X 4 − X 8 + X 9 + X 10 {\displaystyle {\textbf {m}}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}} そしてランダムに選ばれた「ブラインド値」は次のように表される。
r = − 1 + X 2 + X 3 + X 4 − X 5 − X 7 {\displaystyle {\textbf {r}}=-1+X^{2}+X^{3}+X^{4}-X^{5}-X^{7}} ボブへの暗号化されたメッセージを表す 暗号文 eは次のようになります。
e = r ⋅ h + m ( mod 32 ) = 14 + 11 X + 26 X 2 + 24 X 3 + 14 X 4 + 16 X 5 + 30 X 6 + 7 X 7 + 25 X 8 + 6 X 9 + 19 X 10 ( mod 32 ) {\displaystyle {\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {32}}=14+11X+26X^{2}+24X^{3}+14X^{4}+16X^{5}+30X^{6}+7X^{7}+25X^{8}+6X^{9}+19X^{10}{\pmod {32}}}
復号化 r を知っている人なら誰でも、 e - rh を評価することで メッセージ mを 計算できます。したがって、 rはアリスによって漏洩されるべきではありません。公開されている情報に加えて、ボブは自身の秘密鍵も知っています。彼が m を取得する方法は次のとおりです 。まず、暗号化されたメッセージ e と秘密鍵 fの一部を掛け合わせます。
a = f ⋅ e ( mod q ) {\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}} 多項式を書き直すと、この方程式は実際には次の計算を表します。
a = f ⋅ e ( mod q ) {\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}} a = f ⋅ ( r ⋅ h + m ) ( mod q ) {\displaystyle {\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}){\pmod {q}}} a = f ⋅ ( r ⋅ p f q ⋅ g + m ) ( mod q ) {\displaystyle {\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot p{\textbf {f}}_{q}\cdot {\textbf {g}}+{\textbf {m}}){\pmod {q}}} a = p r ⋅ g + f ⋅ m ( mod q ) {\displaystyle {\textbf {a}}=p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}{\pmod {q}}} a の係数を 0から q – 1の間で選ぶ代わりに、係数は区間[- q /2, q /2]内で選ばれます。これは、アリスがメッセージ m の座標を区間[- p /2, p /2]内で選ぶため、元のメッセージが正しく復元されないのを防ぐためです 。これは、 多項式 r 、 g 、 f 、 m 、 および 素数 pの係数が q に比べて小さいため、 のすべての係数が すでに区間[- q /2, q /2]内にあることを意味します。これは、 を 法として縮小する際にすべての係数が変更されず、元のメッセージが正しく復元される可能性が
ある ことを意味します。 p r ⋅ g + f ⋅ m {\displaystyle \ p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}}
次のステップは、 p を法とした a を計算することです。
b = a ( mod p ) = f ⋅ m ( mod p ) {\displaystyle {\textbf {b}}={\textbf {a}}{\pmod {p}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}} なぜなら 。 p r ⋅ g ( mod p ) = 0 {\displaystyle \ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0}
b を知っている ボブは、秘密鍵のもう一方の部分を使って 、 b と ( f p ) {\displaystyle \ \left({\textbf {f}}_{p}\right)} f p {\displaystyle \ {\textbf {f}}_{p}}
c = f p ⋅ b = f p ⋅ f ⋅ m ( mod p ) {\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}} c = m ( mod p ) {\displaystyle {\textbf {c}}={\textbf {m}}{\pmod {p}}} このプロパティ は に必須であったためです 。 f ⋅ f p = 1 ( mod p ) {\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}} f p {\displaystyle \ {\textbf {f}}_{p}}
例 :アリスからボブへの 暗号化されたメッセージ eは多項式 fで乗算されます
a = f ⋅ e ( mod 32 ) = 3 − 7 X − 10 X 2 − 11 X 3 + 10 X 4 + 7 X 5 + 6 X 6 + 7 X 7 + 5 X 8 − 3 X 9 − 7 X 10 ( mod 32 ) , {\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {32}}=3-7X-10X^{2}-11X^{3}+10X^{4}+7X^{5}+6X^{6}+7X^{7}+5X^{8}-3X^{9}-7X^{10}{\pmod {32}},} ここでボブは、元のメッセージが正しく復元されないことを防ぐために、多項式a の係数に区間 [0, q – 1]ではなく区間[- q /2, q /2]を使用します。
p を法とする a の 係数を小さくすると、
b = a ( mod 3 ) = − X − X 2 + X 3 + X 4 + X 5 + X 7 − X 8 − X 10 ( mod 3 ) {\displaystyle {\textbf {b}}={\textbf {a}}{\pmod {3}}=-X-X^{2}+X^{3}+X^{4}+X^{5}+X^{7}-X^{8}-X^{10}{\pmod {3}}} これは と等しい 。 b = f ⋅ m ( mod 3 ) {\displaystyle \ {\textbf {b}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}}
最後のステップでは、その結果をボブの秘密鍵と掛け合わせて元のメッセージ m を得る。 f p {\displaystyle \ {\textbf {f}}_{p}}
c = f p ⋅ b = f p ⋅ f ⋅ m ( mod 3 ) = m ( mod 3 ) {\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}={\textbf {m}}{\pmod {3}}} c = − 1 + X 3 − X 4 − X 8 + X 9 + X 10 {\displaystyle {\textbf {c}}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}} それはまさにアリスがボブに送ったオリジナルのメッセージです。
攻撃 NTRU の提案以来、NTRUEncrypt 公開鍵暗号システムに対する攻撃がいくつか導入されています。ほとんどの攻撃は、メッセージ m を復元するだけでなく、秘密鍵 f を見つけて完全に解読することに重点が置かれています。 f に 非ゼロの係数がほとんどないことがわかっている場合、イヴは f のすべての値を試すことで ブルート フォース攻撃を成功させることができます。イヴが f´ が秘密鍵 かどうか知りたい場合は、単に を計算します 。係数が小さければ、それは秘密鍵 fである可能性があり、イヴは自分で暗号化したメッセージを復号化することで f´ が秘密鍵かどうかをテストできます。イヴは g の値を試して、 に小さな値があるかどうかをテストすること もできます 。 f ′ ⋅ h ( mod q ) {\displaystyle \ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}} g ′ ⋅ h − 1 ( mod q ) {\displaystyle \ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}}
より強力な中間者攻撃 を仕掛けることが可能です 。この攻撃は探索時間を平方根分短縮できます。この攻撃は、 という性質に基づいています 。 f ⋅ h = p g ( mod q ) {\displaystyle \ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}}
イヴは、条件を満たす条件 と 条件を満たす条件 を見つけたい。 f 1 {\displaystyle \ {\textbf {f}}_{1}} f 2 {\displaystyle \ {\textbf {f}}_{2}} f = f 1 + f 2 {\displaystyle \ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}}
( f 1 + f 2 ) ⋅ h = g ( mod q ) {\displaystyle \left({\textbf {f}}_{1}+{\textbf {f}}_{2}\right)\cdot {\textbf {h}}={\textbf {g}}{\pmod {q}}} f 1 ⋅ h = g − f 2 ⋅ h ( mod q ) {\displaystyle {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}} f に d 個の 1 と N - d 個の 0 がある 場合、Eve は 、長さが両方とも d /2である （つまり、 f の最小係数 と 最大係数 をカバーする）可能性のあるすべて のと を作成します。次に、 すべての を計算し 、最初の k 個の座標に基づいてそれらをビンに並べます。その後、すべての を計算し 、最初の k 個の座標だけでなく、最初の k 個の座標に 1 を加えた場合の結果に基づいてビンに並べます。次に、 と の両方を含むビンをチェックし 、 特性が 成り立つかどうかを確認します。 f 1 {\displaystyle \ {\textbf {f}}_{1}} f 2 {\displaystyle \ {\textbf {f}}_{2}} 1 2 N {\displaystyle \ {\frac {1}{2}}N} f 1 {\displaystyle \ {\textbf {f}}_{1}} 1 2 N {\displaystyle \ {\frac {1}{2}}N} f 2 {\displaystyle \ {\textbf {f}}_{2}} f 1 ⋅ h ( mod q ) {\displaystyle {\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}} f 1 {\displaystyle \ {\textbf {f}}_{1}} − f 2 ⋅ h ( mod q ) {\displaystyle \ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}} f 1 {\displaystyle \ {\textbf {f}}_{1}} f 2 {\displaystyle \ {\textbf {f}}_{2}} f 1 ⋅ h = g − f 2 ⋅ h ( mod q ) {\displaystyle \ {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}}
格子縮約攻撃は、NTRUEncryptを解読する最もよく知られた、そして最も実用的な方法の一つです。ある意味では、RSAにおける係数の因数分解に似ています。格子縮約攻撃に最もよく使われるアルゴリズムは、 Lenstra-Lenstra-Lovászアルゴリズム です。公開鍵 hには f と g の両方が含まれているため、 h からそれらを取得しようと試みることができます 。しかし、NTRUEncryptのパラメータが十分に安全に選択されている場合、秘密鍵を見つけるのは非常に困難です。格子縮約攻撃は、格子の次元が大きくなり、最短ベクトルが長くなるにつれて困難になります。
選択 暗号文攻撃もまた、秘密鍵 f を復元することで暗号文を完全に破る手法です 。この攻撃では、イヴは暗号文から自身のメッセージを取得し、それによって秘密鍵を入手しようとします。この攻撃では、イヴはボブと一切やり取りしません。
仕組み ：
まずイヴは、 かつと なる 暗号文を作成します 。イヴが e を解読する手順を書き留めると（f がわからないため、実際に値を計算することはありません）、 が見つかります 。 e = c h + c {\displaystyle \ {\textbf {e}}=c{\textbf {h}}+c} c = 0 ( mod p ) , c < q 2 {\displaystyle \ c=0{\pmod {p}},c<{\frac {q}{2}}} 2 c > q 2 {\displaystyle \ 2c>{\frac {q}{2}}} a = f ⋅ e ( mod q ) {\displaystyle \ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}
a = f ( c h + c ) ( mod q ) {\displaystyle {\textbf {a}}={\textbf {f}}\left(c{\textbf {h}}+c\right){\pmod {q}}} a = c g + c f ( mod q ) {\displaystyle {\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}{\pmod {q}}} a = c g + c f − q K {\displaystyle {\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}-qK} その ような K = ∑ k i x i {\displaystyle \ K=\sum k_{i}x^{i}}
k i = { 1 if the i t h coefficient of f and g is 1 , − 1 if the i t h coefficient of f and g is − 1 , 0 otherwise. {\displaystyle k_{i}={\begin{cases}1&{\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ 1,\\-1&{\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ -1,\\0&{\text{otherwise.}}\end{cases}}} 例 ：
f = − 1 + X + X 2 − X 4 + X 6 + X 9 − X 10 {\displaystyle {\textbf {f}}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}} g = − 1 + X 2 + X 3 + X 5 − X 8 − X 10 {\displaystyle {\textbf {g}}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}} すると K は になります 。 K = − 1 + X 2 − X 10 {\displaystyle \ K=-1+X^{2}-X^{10}}
p を法とする a の係数を減らすと、 実際には の係数も減ります 。 を掛け合わせると 、イヴは次の式を得ます。 c g + c f − q K ( mod p ) {\displaystyle \ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}} f p {\displaystyle \ {\textbf {f}}_{p}}
m = c f p ⋅ g + c f p ⋅ f − q f p ⋅ K ( mod p ) {\displaystyle {\textbf {m}}=c{\textbf {f}}_{p}\cdot {\textbf {g}}+c{\textbf {f}}_{p}\cdot {\textbf {f}}-q{\textbf {f}}_{p}\cdot K{\pmod {p}}} m = c h + c − q f p ⋅ K ( mod p ) {\displaystyle {\textbf {m}}=c{\textbf {h}}+c-q{\textbf {f}}_{p}\cdot K{\pmod {p}}} cはp の倍数として選択されたため 、 mは 次のように書ける。
m = − q f p ⋅ K ( mod p ) {\displaystyle {\textbf {m}}=-q{\textbf {f}}_{p}\cdot K{\pmod {p}}} つまり、 。 f = − q K ⋅ m − 1 ( mod p ) {\displaystyle \ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}}
ここで、 f と g が 同じ因数で等しい係数をほとんど持たない 場合、 K には非ゼロの係数がほとんどなく、したがって K は小さくなります。攻撃者は K の異なる値を試すことで f を復元できます 。
NTRUEncrypt に従ってメッセージを暗号化および復号化することにより、攻撃者は関数 f が正しい秘密鍵であるかどうかを確認できます。
最新の推奨パラメータ（下記参照）を使用することで、NTRUEncrypt公開鍵暗号システムはほとんどの攻撃に対して安全です。しかしながら、パフォーマンスとセキュリティの間で依然として葛藤が続いています。速度を低下させずにセキュリティを向上させることは困難であり、その逆もまた同様です。
アルゴリズムの有効性を損なうことなくプロセスを高速化する 1 つの方法は、秘密鍵 f に何らかの変更を加えることです。まず、 となるように f を 構築します。ここで F は小さな多項式 (つまり、係数 {-1,0, 1}) です。 このように f を構築することにより、 fは p を法として逆数になります 。実際 、 となるため、ボブは実際に逆数を計算する必要がなく、復号化の 2 番目の手順を実行する必要がありません。したがって、このように f を 構築すると時間が大幅に節約されますが、見つけやすくなるだけで 、 f を復元するのは依然として困難であるため、NTRUEncrypt のセキュリティには影響しません。この場合、 pによる乗算のため、 f の係数は -1、0、または 1 以外になります。 ただし、ボブは p を乗じて公開鍵 h を 生成し、後で暗号文を p を 法として簡約するため、暗号化方法には影響しません。 f = 1 + p F {\displaystyle \ {\textbf {f}}=1+p{\textbf {F}}} f − 1 = 1 ( mod p ) {\displaystyle \ {\textbf {f}}^{-1}=1{\pmod {p}}} f p {\displaystyle \ {\textbf {f}}_{p}}
第二に、 fは 複数の多項式の積として表すことができ、その多項式には多くの零係数が含まれます。これにより、計算回数が少なくなります。
2020年のNTRU NIST提出 [3] によれば、以下のパラメータは安全であると考えられている。
表1: パラメータ 北 q p 128ビットのセキュリティマージン（NTRU-HPS） 509 2048 3 192 ビットのセキュリティ マージン (NTRU-HPS) 677 2048 3 256ビットのセキュリティマージン（NTRU-HPS） 821 4096 3 256ビットのセキュリティマージン（NTRU-HRSS） 701 8192 3
参考文献 ^ 「米国特許6081597 – 公開鍵暗号システムの方法および装置」 – Google Patents 経由。 ^ 「Security InnovationのNTRUEncryptがデータ保護のX9標準に採用」（プレスリリース）。2011年4月11日。 ^ "NIST-PQ-Submission-NTRU-20201016.tar.gz". Jaulmes, E.、Joux, A. NTRUに対する選択暗号文攻撃。コンピュータサイエンス講義ノート、第1880巻。暗号技術の進歩に関する第20回国際暗号学会議議事録。pp. 20–35、2000年。 Jeffrey Hoffstein、Jill Pipher、Joseph H. Silverman. NTRU: リングベースの公開鍵暗号システム。Algorithmic Number Theory (ANTS III)、オレゴン州ポートランド、1998年6月、JP Buhler (編)、Lecture Notes in Computer Science 1423、Springer-Verlag、ベルリン、1998年、267-288ページ。 Howgrave-Graham, N.、Silverman, JH、および Whyte, W.、「NTRU 秘密キーに対する Meet-In-The-Middle 攻撃」 J. Hoffstein, J. Silverman. NTRUの最適化. 公開鍵暗号と計算数論（ワルシャワ、2000年9月11日～15日）, DeGruyter, 近日掲載予定. AC Atici、L. Batina、J. Fan、I. Verbauwhede。パーベイシブセキュリティのためのNTRUの低コスト実装。
外部リンク NTRU技術ウェブサイト 2018年7月2日アーカイブ Wayback Machine IEEE P1363ホームページ セキュリティイノベーション（NTRU Cryptosystems, Inc. を買収） NTRUEncrypt のオープンソース BSD ライセンス実装 NTRUEncrypt のオープンソース GPL v2 ライセンス NTRUEncryptベースの鍵交換を使用したオープンソースIPsecソリューションstrongSwan - NTRUを利用した暗号スイートを提供する組み込みSSL/TLSライブラリ（wolfSSL）
![{\displaystyle \R=\mathbb {Z} [X]/(X^{N}-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27dda5f6511ef49ca7d8715fd148feee4ac9eb97)
![{\displaystyle [-p/2,p/2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9cb2a2098f92c967015c51c263433a2da301b32b)
