NTRU格攻擊中參數q的意義
在NTRU(N,p,q,d)中，通常選擇N為素數，q為2的冪。為什麼如果我增加參數q，找到可以解密的密鑰或偽密鑰的機率消息要高得多？
例如，N=127, q=256 會給我一次不成功的格攻擊，但 N=127, q=2^16 會給我一次成功的格攻擊
基本上，密鑰的範數不依賴於 $ q $ ，而格子的第二個最小值的範數確實如此，所以，當你增加 $ q $ ，你增加了晶格的第一個和第二個最小值之間的差距，這使得問題更容易。
例如，如果密鑰由兩度組成- $ (N-1) $ 多項式 $ f $ 和 $ g $ 係數在 $ {-1, 0, 1} $ ，那麼我們有 $ ||(f, g)|| < 2N $ .
格子的一個基礎 $ L $ 我們在攻擊中使用的是 $$ \begin{pmatrix} I_N & H \ 0 & q\cdot I_N \end{pmatrix} \in \mathbb{Z}^{2N\times 2N} $$ 所以，很明顯 $ \det(L) = q^N $ 和 $ \dim(L) = 2N $ . 然後，通過高斯啟發式，我們期望的短向量 $ L $ 有範數接近 $ \sqrt{N}(\det(L))^{1/\dim(L)} = \sqrt{Nq} $ .
因為 $ (f, g) \in L $ 和 $ ||(f, g)|| $ 小於高斯啟發式預測的值，則存在“差距” $ L $ ，也就是說，我們期望 $ \lambda_1(L) = ||(f, g)|| $ 和 $ \lambda_2(L) \approx \sqrt{Nq} $ .
現在，粗略地說，如果我們恢復的向量比第二個最短的向量短，那麼它必須是第一個最短的向量。因此，當我們執行格基約簡時，如果我們恢復一個小於 $ \sqrt{Nq} $ ，它已經是（的短倍數） $ (f, g) $ 我們贏了。