同一個私鑰的多個 NTRU 公鑰？
NTRU公鑰本質上是通過乘以多項式的逆來生成的 $ f $ 由多項式 $ g $ . 多項式 $ f $ 是私鑰； $ g $ 被丟棄。
我的問題是：為同一個私鑰分發多個公鑰是否不安全，即使用相同的私鑰 $ f $ 但不同 $ g $ 的？
根據目前的知識，為同一個私鑰分發多個公鑰（具有獨立的分子） $ f $ 不是不安全的，只要參數被適當地實例化。在具體的安全性上有一些小的損失，但沒有什麼比得上有效的攻擊了。
僅用於一個公鑰的標準 NTRU 格 $ h $ 是
$$ \begin{equation} L_h = { (u,v) : u \cdot h = v \pmod{q} }, \end{equation} $$和 $ (f,g) \in L_h $ 是一個格向量，相對於高斯啟發式對“隨機”的預測，“異常短” $ 2n $ 具有相同行列式的維晶格 $ q^n $ 作為 $ L_h $ . 從本質上講，這個間隙控制了使用格減少找到密鑰的難度（較小的間隙意味著更難破解）。 有多個公鑰 $ h_i = g_i \cdot f^{-1} \pmod{q} $ 共享私鑰 $ f $ ，我們可以定義一個相似的格子
$$ \begin{equation} L = { (u, v_1, \ldots, v_t) : u \cdot h_i = v_i \pmod{q} }. \end{equation} $$ 這個 $ (t+1)n $ -維晶格具有行列式 $ q^{tn} $ ，所以高斯啟發式預測的最小距離為 $ \approx q^{t/(t+1)} $ ， 然而 $ (f,g_1, g_2, \ldots, g_t) $ 是一個“異常短”的晶格向量 $ L $ . 間隙通常比單密鑰情況下的要大，這使得找到密鑰更加容易。但只要差距不是很大（例如，多項式 $ n $ ) 並且維度足夠大，像 LLL/BKZ 這樣的算法將無法在任何可行的時間內找到密鑰。 另一個原因是，非正式地，從一個公鑰 $ h $ 我們可以生成許多公鑰 $ h_i $ 具有相同的密鑰，乘以 $ h $ 通過隨機小 $ g_i $ . 生成的公鑰不會像“真”密鑰那樣分發，它們也不會是獨立的，但這至少給出了一些直覺，為什麼很難從許多公鑰中找到秘密密鑰。
值得注意的是，這裡與 LWE 非常相似，可以得到無限數量的帶有秘密向量的雜訊隨機內積，並且此類樣本的數量對硬度沒有重大影響（儘管它確實有一些） .