NTRU涉及哪些操作？
我讀過基於格的算法涉及矩陣向量產品。這是NTRU算法的情況嗎？
當我閱讀 NTRU 算法的細節時，我看到了多項式的產品。矩陣向量產品在哪裡？
幾乎所有具有一定實用性能的基於格的方案都使用所有格子集中的格子。這些格子有額外的結構，可以用多項式來描述。這樣做的最大優勢在於，一方面晶格描述的大小遠小於任意晶格，另一方面可以使用快速傅里葉變換 (FFT) 進行乘法運算。如果您想了解更多關於理想格子或“環設置”/環-LWE 的Google。
應該注意的另一點是，這些性能方面的進步是由這些晶格提供的額外結構引起的。目前，我們不知道任何可以利用這種額外結構來實際破壞方案的攻擊（至少對於所提出的格類）。然而，這是一個正在進行的研究的主題，並且眾所周知，對於某些空間情況（如果以錯誤的方式選擇這些子集）方案會變得不安全（參見例如https://eprint.iacr.org/2015/176。 .pdf )。
一些基於 Lattice 的 Crypto 的工作方式是通過創建一個私有基礎，使用短正交向量來簡化計算。公共基由 HNF 組成，被稱為“Bad-basis”，具有非正交向量，這使得破壞系統變得困難：
NTRU-encrypt（它的一個版本）的工作原理如下：
**私鑰：**給定參數 $ q $ 兩個短向量 $ (f,g) $ 選擇使用循環轉換創建私鑰 $ T $ . 他們一起創建了帶有基礎的私有 q-ary lattice $ (T\cdot f,T\cdot g) $ . 格是卷積模格，它是在下閉合的 q-ary 格 $ T: <x,y> \mapsto <Tx,Ty> $
公鑰： $ T $ 和 $ f,g $ 必須滿足 $ T\cdot f $ 是一致的 $ I $ mod p 其中 p 是另一個系統參數（在我在底部發布的連結中描述； $ f,g $ 必須滿足一些要求）和 $ T\cdot g $ 是一致的 $ O $ 零矩陣。公鑰完全由 $ h=[T\cdot f]^{-1} g $ (mod q) 和公共矩陣 $ H $ 是 $ [(I,T\cdot f)^t;(O,q.I)^t] $ 在哪裡 $ ; $ 表示列分隔。明文是 $ (-r,m) $ 在哪裡 $ r $ 是一個隨機向量：
加密： $ [(-r,m)^t] $ 模型 H $ = $ （減少到） $ (m+[T\cdot h]r) $ （模 q）。矩陣結果的頂部只是 $ O $ ，在連結中再次解釋。
**解密：**是 $ [T\cdot f]c $ 模 q = $ [T\cdot f]m+[T\cdot g]r $ 模p $ = I.m+O.r=m $
所有這些都來自一本關於後量子加密的好書，位於 NTRU 加密部分。SVP 是陷阱門，因為找到短向量揭示了私有短基。FFT 還用於一些基於 Lattice 的壓縮函式中，這些函式使用 FFT 來加速矩陣乘法（其中一個是下面的連結以非常巧妙的方式做到了）
正如 mephisto 提到的，Learning-with Errors 是另一個基於 Lattice 的系統，具有提供實際安全證明的好處，我相信 NTRU 加密沒有。此外，如 mephisto 所提到的，某些結構化格（理想格）也用於加速計算和記憶體。如您所見，公共基礎實際上僅由 $ h $ . LWE 基於通過矩陣乘法和擾動選擇的格向量來區分均勻選擇的格向量。我相信連結解釋了改進的 NTRUencrypt 版本。由於格是基於多項式理想的，因此多項式乘法與矩陣向量乘積密切相關。在後量子提議中，它似乎創建了簡單的密碼系統，但不一定是最安全的。