NTRUE暗号化

NTRUEncrypt公開鍵暗号システムは、 NTRU 暗号化アルゴリズムとも呼ばれ、RSAおよび楕円曲線暗号(ECC)に代わるNTRU格子ベースの暗号システムであり、格子内の最短ベクトル問題に基づいています(量子コンピュータを使用して解読できないことは知られています)。

これは、切断された多項式環の特定の多項式を、非常に小さな係数を持つ 2 つの多項式の商に因数分解することが困難であると想定されることに依存しています。暗号システムの解読は、特定の格子における格子縮小のアルゴリズムの問​​題と強く関連していますが、同等ではありません。公開されている攻撃を阻止するには、パラメータを慎重に選択する必要があります。

暗号化と復号化の両方で単純な多項式の乗算のみを使用するため、これらの操作は、RSA、ElGamal、楕円曲線暗号などの他の非対称暗号化方式と比較して非常に高速です。ただし、NTRUEncrypt は、展開された形式で同等の量の暗号分析をまだ受けていません。

関連するアルゴリズムとして、NTRUSign デジタル署名アルゴリズムがあります。

具体的には、NTRU 演算は畳み込み乗算を伴う切り捨て多項式環内のオブジェクトに基づいており、環内のすべての多項式は整数係数を持ち、次数は最大N -1 です。 ${\displaystyle \ R=\mathbb {Z} [X]/(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}}$

この環では、多項式に を掛けると多項式の係数が回転する効果があります。したがって、を固定した場合のの形式の写像は、内の非ゼロ係数と同じ数の からの係数にすべての係数が依存する新しい多項式を生成します。 ${\displaystyle X^{N}=1}$${\displaystyle X}$ ${\displaystyle f\mapsto fg}$${\displaystyle g\in R}$${\displaystyle fg}$${\displaystyle f}$${\displaystyle g}$

NTRU には 3 つの整数パラメータ ( N、p、q ) があり、Nは多項式の次数境界、pは小係数、q は大係数と呼ばれます。 Nは素数、q は常にpより (はるかに) 大きく、pとq は互いに素であると仮定します。平文メッセージはp を法とする多項式ですが、暗号文メッセージはqを法とする多項式です。 具体的には、暗号文は平文メッセージとランダムに選択された公開鍵の倍数で構成されますが、公開鍵自体は小係数pの倍数と見なすことができ、秘密鍵の所有者は暗号文から平文を抽出できます。

NTRUEncrypt公開鍵暗号システムは比較的新しい暗号システムです。このシステムの最初のバージョンは単にNTRUと呼ばれ、1996年頃に3人の数学者（Jeffrey Hoffstein、Jill Pipher、Joseph H. Silverman ）によって開発されました。1996年にこれらの数学者はDaniel Liemanとともに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 を試す必要があります。 ${\displaystyle \N-1}$${\displaystyle \X^{N}-1}$${\displaystyle {\textbf {f}}\in L_{f}}$${\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}}$${\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}}$

fと（および）はボブの秘密鍵です。公開鍵hは、次の量を計算し生成されます。 ${\displaystyle \\mathbf {f}_{p}}$${\displaystyle g}$

${\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 ) は誰もが知っています。多項式はランダムに選択されるため、次のように表されるとします。

${\displaystyle {\textbf {f}}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}}$

${\displaystyle {\textbf {g}}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}}$

ユークリッドの互除法を用いて、それぞれ pを法とするfの逆数とqを法とするfの逆数が計算される。

${\displaystyle {\textbf {f}}_{p}=1+2X+2X^{3}+2X^{4}+X^{5}+2X^{7}+X^{8}+2X^{9}{\pmod {3}}}$

${\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を作成し、積を計算する。

${\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 をランダムに選択します。${\displaystyle [-p/2,p/2]}$

ボブの公開鍵hを使用して暗号化されたメッセージeが計算されます。

${\displaystyle {\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {q}}}$

この暗号文はアリスのメッセージを隠し、ボブに安全に送信できます。

例: アリスが多項式で表せるメッセージを送信したいとします。

${\displaystyle {\textbf {m}}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}}$

そしてランダムに選ばれた「盲検値」は次のように表される。

${\displaystyle {\textbf {r}}=-1+X^{2}+X^{3}+X^{4}-X^{5}-X^{7}}$

ボブへの暗号化されたメッセージを表す 暗号文eは次のようになります。

${\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の一部を掛け合わせます。

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}$

多項式を書き直すと、この方程式は実際には次の計算を表します。

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}$

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}){\pmod {q}}}$

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot p{\textbf {f}}_{q}\cdot {\textbf {g}}+{\textbf {m}}){\pmod {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] 内にあることを意味します。これは、 qを法として縮小する間、すべての係数が変更されず、元のメッセージが正しく復元される可能性があること を意味します。${\displaystyle \ p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}}$

次のステップは、 pを法としてaを計算することです。

${\displaystyle {\textbf {b}}={\textbf {a}}{\pmod {p}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}}$

なぜなら。 ${\displaystyle \ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0}$

bを知っているボブは、秘密鍵のもう一方の部分を使って、bと${\displaystyle \ \left({\textbf {f}}_{p}\right)}$${\displaystyle \ {\textbf {f}}_{p}}$

${\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}}$

${\displaystyle {\textbf {c}}={\textbf {m}}{\pmod {p}}}$

なぜなら、そのプロパティはに必要だったからです。 ${\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}}$${\displaystyle \ {\textbf {f}}_{p}}$

例: アリスからボブへの暗号化されたメッセージeは多項式fで乗算されます。

${\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の係数を小さくすると、

${\displaystyle {\textbf {b}}={\textbf {a}}{\pmod {3}}=-X-X^{2}+X^{3}+X^{4}+X^{5}+X^{7}-X^{8}-X^{10}{\pmod {3}}}$

これは に等しい。 ${\displaystyle \ {\textbf {b}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}}$

最後のステップでは、その結果をボブの秘密鍵から乗算して、元のメッセージmを生成します。${\displaystyle \ {\textbf {f}}_{p}}$

${\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}={\textbf {m}}{\pmod {3}}}$

${\displaystyle {\textbf {c}}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}}$

それはまさにアリスがボブに送った元のメッセージです。

NTRU の提案以来、NTRUEncrypt 公開鍵暗号システムに対する攻撃がいくつか導入されています。ほとんどの攻撃は、メッセージm を復元するだけでなく、秘密鍵f を見つけて完全に解読することに重点が置かれています。f に非ゼロの係数がほとんどないことがわかっている場合、Eve はfのすべての値を試すことでブルート フォース攻撃を成功させることができます。Eve がf´が秘密鍵であるかどうかを知りたい場合は、 を計算するだけです。係数が小さければ秘密鍵fである可能性があり、Eve は自分で暗号化したメッセージを復号化することで、 f´が秘密鍵かどうかをテストできます。Eve はgの値を試して、 に小さな値があるかどうかをテストすること もできます。 ${\displaystyle \ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}}$${\displaystyle \ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}}$

より強力なmeet-in-the-middle 攻撃を仕掛けることが可能です。この攻撃では、検索時間を平方根分短縮できます。この攻撃は、 という特性に基づいています。 ${\displaystyle \ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}}$

イブは、およびが成り立つような性質を持つもの を見つけたい 。${\displaystyle \ {\textbf {f}}_{1}}$${\displaystyle \ {\textbf {f}}_{2}}$${\displaystyle \ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}}$

${\displaystyle \left({\textbf {f}}_{1}+{\textbf {f}}_{2}\right)\cdot {\textbf {h}}={\textbf {g}}{\pmod {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 は、両方とも長さ (つまり、 f の最小の係数と最大の係数をカバー) があり、1 が d /2 個ある可能性のあるとをすべて作成します。次に、すべてについて を計算し、最初の k 個の座標に基づいてそれらをビンに並べます。その後、すべてについて を計算し、最初の k 個の座標だけでなく、最初の k 個の座標に 1 を加えた場合に何が起こるかに基づいてビンに並べます。次に、と の両方を含むビンをチェックして、プロパティが保持されるかどうかを確認します。 ${\displaystyle \ {\textbf {f}}_{1}}$${\displaystyle \ {\textbf {f}}_{2}}$${\displaystyle \ {\frac {1}{2}}N}$${\displaystyle \ {\textbf {f}}_{1}}$${\displaystyle \ {\frac {1}{2}}N}$${\displaystyle \ {\textbf {f}}_{2}}$${\displaystyle {\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}}$${\displaystyle \ {\textbf {f}}_{1}}$${\displaystyle \ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}}$${\displaystyle \ {\textbf {f}}_{1}}$${\displaystyle \ {\textbf {f}}_{2}}$${\displaystyle \ {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}}$

格子縮小攻撃は、NTRUEncrypt を破るための最もよく知られた、最も実用的な方法の 1 つです。ある意味では、RSA の係数の因数分解に似ています。格子縮小攻撃に最もよく使用されるアルゴリズムは、Lenstra-Lenstra-Lovász アルゴリズムです。公開鍵hにはfとg の両方が含まれているため、 hからこれらを取得できます。ただし、NTRUEncrypt パラメータが十分に安全に選択されている場合、秘密鍵を見つけるのは非常に困難です。格子縮小攻撃は、格子の次元が大きくなり、最短ベクトルが長くなると難しくなります。

選択暗号文攻撃も、秘密鍵fを復元し、完全な破綻をもたらす方法です。この攻撃では、イブは暗号文から自分のメッセージを取得し、秘密鍵を取得しようとします。この攻撃では、イブはボブと一切やり取りしません。

仕組み：

まず、イブは次のような暗号文を作成します。 イブが e を解読する手順を書き留めると (f がわからないため、実際に値を計算せずに)、次のようになります。 ${\displaystyle \ {\textbf {e}}=c{\textbf {h}}+c}$${\displaystyle \ c=0{\pmod {p}},c<{\frac {q}{2}}}$${\displaystyle \ 2c>{\frac {q}{2}}}$${\displaystyle \ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}$

${\displaystyle {\textbf {a}}={\textbf {f}}\left(c{\textbf {h}}+c\right){\pmod {q}}}$

${\displaystyle {\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}{\pmod {q}}}$

${\displaystyle {\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}-qK}$

その ような ${\displaystyle \ K=\sum k_{i}x^{i}}$

${\displaystyle k_{i}={\begin{cases}1\ \ \qquad {\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ 1\\-1\qquad {\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ -1\\0\ \ \qquad {\text{Otherwise}}\end{cases}}}$

例：

${\displaystyle {\textbf {f}}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}}$

${\displaystyle {\textbf {g}}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}}$

するとKはになります。 ${\displaystyle \ K=-1+X^{2}-X^{10}}$

p を法としてaの係数を減らすと、実際には の係数が減ります。 を乗算すると、Eve は次の式を得ます。 ${\displaystyle \ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}}$${\displaystyle \ {\textbf {f}}_{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}}}$

${\displaystyle {\textbf {m}}=c{\textbf {h}}+c-q{\textbf {f}}_{p}\cdot K{\pmod {p}}}$

cはpの倍数として選択されたため、mは次のように表される。

${\displaystyle {\textbf {m}}=-q{\textbf {f}}_{p}\cdot K{\pmod {p}}}$

つまり、. ${\displaystyle \ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}}$

ここで、 fとgが同じ因数で同じ係数をほとんど持たない場合、 Kにはゼロ以外の係数がほとんどなく、したがって小さくなります。Kの異なる値を試すことで、攻撃者はf を復元できます。

NTRUEncrypt に従ってメッセージを暗号化および復号化することにより、攻撃者は関数fが正しい秘密鍵であるかどうかを確認できます。

最新の推奨パラメータ (下記参照) を使用すると、NTRUEncrypt 公開鍵暗号システムはほとんどの攻撃に対して安全です。ただし、パフォーマンスとセキュリティの間では依然として葛藤が続いています。速度を落とさずにセキュリティを向上させることは困難であり、その逆も同様です。

アルゴリズムの有効性を損なうことなくプロセスを高速化する 1 つの方法は、秘密鍵fにいくつか変更を加えることです。まず、となるようにf を構築します。ここで、 F は小さな多項式 (つまり、係数 {-1,0, 1}) です。このようにf を構築することにより、 f はp を法として可逆に なります。実際、 となるため、ボブは実際に逆を計算する必要がなく、復号化の 2 番目の手順を実行する必要もありません。したがって、このようにf を構築すると多くの時間が節約されますが、NTRUEncrypt のセキュリティには影響しません。なぜなら、 f は見つけやすくなるだけで、復元するのは依然として困難だからです。この場合、pによる乗算のため、 fの係数は -1、0、または 1 以外になります。しかし、ボブはpを乗じて公開鍵h を生成し、後で暗号文をp を法として減算するため、暗号化方法には影響しません。 ${\displaystyle \ {\textbf {f}}=1+p{\textbf {F}}}$${\displaystyle \ {\textbf {f}}^{-1}=1{\pmod {p}}}$${\displaystyle \ {\textbf {f}}_{p}}$

2 番目に、f は複数の多項式の積として表すことができ、多項式には多くのゼロ係数があります。この方法により、実行する必要がある計算が少なくなります。

2020年のNTRU NIST提出^[3]によれば、以下のパラメータは安全であると考えられています。

• 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 技術ウェブサイト
• IEEE P1363 ホームページ
• セキュリティイノベーション（NTRU Cryptosystems, Inc. を買収）
• NTRUEncrypt のオープンソース BSD ライセンス実装
• NTRUEncrypt のオープンソース GPL v2 ライセンス
• NTRUEncrypt ベースの鍵交換を使用した strongSwan オープンソース IPsec ソリューション
• - NTRU を利用した暗号スイートを提供する組み込み SSL/TLS ライブラリ (wolfSSL)