膨脹係數
似乎有一個數量，通常表示 $ \gamma $ , 這樣 $ l_2 $ 兩個多項式乘積的範數可以寫成範數的乘積，最多乘以 $ \gamma $ .
例如，如果 $ f $ 和 $ g $ 是兩個多項式，我們有 $ |fg|\leq\gamma\cdot|f||g| $ . 例如，參見本文的第 2 節。我可以找到向量方面的因子資訊，但我不理解多項式方面的資訊。
這個數量是從哪裡來的？我們知道什麼結果？如何計算不同的環，甚至模組？
我鼓勵您閱讀Generalized Compact Knapsacks are Collision Resistant的第 3.1 節，它是第一次定義的。您的問題的答案是：
我可以找到向量方面的因子資訊，但我不理解多項式方面的資訊。
定義規範的“擴展因子”方式背後的想法 $ R = \mathbb{Z}[x]/(f(x)) $ 是使用所謂的“係數嵌入” $ \sigma : R \to\mathbb{R}^{\deg f} $ ，然後簡單地取內向量的（標準）範數 $ \mathbb{R}^{\deg f} $ . 係數嵌入需要一些輸入 $ r(x) $ , 減少它 mod $ f(x) $ 獲得一個獨特的代表 $ r(x) $ 內 $ \mathbb{Z}[x] + \langle f(x)\rangle $ （是學位的唯一代表 $ < \deg f $ )，然後讀取這個唯一代表的係數作為向量。也就是說，您正在使用的規範被定義為“ $ r(x) $ 多項式”和“ $ \vec r $ 向量”故意非常小。
這個數量是從哪裡來的？
它本質上是定義的，因為所需的關係 $ \lVert g(x)h(x)\rVert \not\leq \lVert g(x)\rVert\lVert h(x)\rVert $ 不成立，在哪裡 $ \lVert\cdot\rVert $ 是誘導上的規範 $ R $ 通過係數嵌入。可以定義擴展因子，使得該不等式的近似版本成立，即 $ \lVert g(x)h(x)\rVert \leq \gamma \lVert g(x)\rVert\lVert h(x)\rVert $ . 如果您將此視為定義它的目標，那麼應該相對清楚地了解為什麼擴展因子採用它所做的精確定義。
至於為什麼我們希望這樣的表達式成立，您應該將其視為類似於三角不等式的“乘法”版本。本質上，當使用某個代數結構上的範數時，如果你的範數“尊重”你的代數結構，事情會更好。對於環，這意味著範數是次可加的（也稱為滿足三角不等式）和次乘的（表示滿足 $ \lVert g(x)h(x)\rVert \leq \lVert g(x)\rVert \lVert h(x)\rVert $ )，或者甚至只是“大約”這樣（說是“軟糖因素” $ \gamma $ ).
我們知道什麼結果？
有一些限制它的一般結果（在連結的論文中討論），但許多作者不再使用它，因為有一種“更好”的方式來定義規範 $ \mathbb{Z}[x]/(f(x)) $ 這直接導致了子乘法構造，而無需引入“軟糖因子”（這本質上是擴展因子正在做的事情）。有關詳細資訊，請參閱Piekert 的調查A Decade of Lattice Cryptography的第 4.3.3 節。使用擴展因子定義的範數通常稱為係數嵌入，預設情況下是次乘的範數通常稱為 Minkowski 或 Canonical 嵌入。
請注意，除了分析表達式之外，Canonical 嵌入還有其他優點 — 它對應於在多個點上評估多項式，即“傅立葉變換”類型的操作。雖然計算此表示的效率低於僅從某些多項式中讀取係數，但一旦您計算了它，您就會獲得某些計算優勢（更快的乘法算法）。
如何計算不同的環，甚至模組？
它是針對該論文中的一些範例進行計算的，但在大多數情況下，我認為答案是“不是”。如果您想使用它，它已經計算了許多“常見”環（包括一些一般結果 — 參見論文），但許多作者只是使用 Minkowski 嵌入，它規避了強制特定規範的問題是次乘法。
請注意，諸如擴展因子之類的東西可能會出現在其他“格子加密相鄰”區域中。例如，在最近的這篇論文中，作者需要為格密碼學的“大整數”版本定義/分析類似的數量（請參閱這篇論文以了解呼叫它的動機）。當然，這也可能表明分析中使用了“錯誤的規範”，如果人們能找到“正確的規範”，他們就不需要定義擴展因子（可以說這就是發生的事情）關於規範 $ \mathbb{Z}[x]/(f(x)) $ ）。時間會證明一切。