NTRU：歴史、設計、セキュリティ

NTRUは1996年にHoffstein、Pipher、Silvermanによって発明され、現在も安全と考えられているポスト量子公開鍵システムの中でも最古のものの1つです。数論的な困難性に依存するRSAやECCとは異なり、NTRUの安全性は、多項式環から構成される特定の格子上で短いベクトルを見つける難しさに基づいています。NTRUは商用化され、ポスト量子暗号が普及する前から複数のセキュリティ製品に導入されていました。

NTRUは、切断多項式環Z[X]/(X^N - 1)で動作します。ここでNは素数です。この環の多項式の次数は高々N-1であり、乗算は巡回します（畳み込み）。環の選択と、小さな係数を持つ多項式の構造は、NTRUの効率性と安全性の両方において中心的な役割を果たします。

鍵生成では、係数が{-1, 0, 1}に含まれる2つの小さな多項式fとgを選びます。多項式fは、p（小さな素数で、通常は3）とq（より大きな素数で、通常は2048）の両方を法として可逆でなければなりません。公開鍵はh = f_q^{-1} * g mod qです。ここでf_qはqを法とするfの逆元です。秘密鍵はペア（f, g）です。

係数が小さいメッセージ多項式mを暗号化するため、送信者はランダムな小さいブラインディング多項式rを選び、c = r * h + m mod qを計算します。暗号文cは同じ環の多項式です。ランダムなrにより、同じメッセージを暗号化しても同一に見えることがなくなり、セマンティックセキュリティが実現されます。

復号ではa = f * c mod qを計算し、係数を範囲(-q/2, q/2]に選びます。次にa mod pによってf_p * m mod pが復元され、fp = f^{-1} mod pを乗算することでmが得られます。小さな誤差構造により、f * cの係数は十分小さくなるため、mod qとmod pの演算が正しく連携し、ノイズによる復号失敗なしにメッセージを復元できます。

現代のNTRUには、標準化された2つのパラメータファミリーがあります。NTRU-HPS（Hoffstein-Pipher-Silverman）とNTRU-HRSS（Hulsing-Rijneveld-Schanck-Schwabe）です。NTRU-HPSは三値メッセージ多項式を使用し、NTRU-HRSSは復号失敗率を下げるためにランダム化エンコーディングを使用します。どちらもNIST PQCラウンド3の最終候補となり、128、192、256ビットの安全性を目標とするパラメータセットが用意されています。

適切にパラメータ設定されたNTRUに対する多項式時間攻撃は、現在知られていません。最良の攻撃は、NTRU格子上で短いベクトルを見つける問題に帰着します。これは近似SVP問題の一例です。NTRU格子には特定の構造（巡回ブロック）があり、ランダム格子よりもわずかに攻撃しやすいため、この構造を考慮した安全性マージンを持つようにパラメータが選ばれます。

NTRUはNTRU Cryptosystems Inc.（後のSecurity Innovation）によって広範に特許化されました。元の特許は1996年と1998年に出願されました。この特許保護により、20年間にわたって広範な採用とオープンソース実装が妨げられました。NTRUの中核特許は2017年頃に失効し、その後オープンな実装が急速に増加して、NTRUはNIST PQC標準化競争に参加しました。

NTRUは、Kyber、Classic McEliece、SABERとともに、NIST PQC競争のラウンド3最終候補となりました。NISTは最終的に、より単純な安全性分析と明快な設計を理由として、Kyber（ML-KEM）を主要なKEM標準に選定しました。NTRUは標準化されませんでしたが、依然として有力な代替方式であり、その分析は格子の安全性に関する理解の向上に貢献しました。

Bernstein、Chuengsatiansup、Lange、van Vredendaalによって開発されたNTRUPrimeは、環構造X^N - 1を意図的に取り除き、素数次数の多項式X^N - X - 1に置き換えています。これにより、巡回環構造に起因する潜在的な弱点が排除されます。この弱点は、一部の暗号解析研究者によって悪用される可能性があると考えられていました。NTRUPrimeもNIST PQCの次点候補となりました。

NTRUはLWEベース方式より先に登場し、RegevによるLWEの帰着のような、形式的な最悪時困難性の帰着を持ちません。一方で、同等の安全性レベルで比較すると、NTRUは多くのLWE方式よりも鍵生成が高速で、暗号文のサイズも小さくなります。その代償は、帰着証明ではなく、数十年にわたる暗号解析の経験に依存する、より形式性の低い安全性の基盤です。

NTRUは、多項式環の算術に基づく先駆的な格子ベース暗号システムです。鍵生成では小さな多項式fとgを使用し、公開鍵はh = f^{-1}*g mod qです。暗号化ではランダムなブラインディングを使用し、復号ではfの小さな係数構造を利用します。NTRUには形式的な最悪時帰着はありませんが、数十年にわたる暗号解析に耐えてきました。特許は2017年に失効し、NIST PQCラウンド3の最終候補となりました。