二次分圓域冪代數範數大小的期望

讓 $ \mathcal R $ 是二分圓域的冪的整數環。那是， $ \mathcal R = \mathbb Z[x] /\langle x^{2^k}+1\rangle $ 對於某個整數 $ k $ . 我們表示 $ \mathcal R / q \mathcal R $ 經過 $ \mathcal R_q $ . 這是 ring-LWE 眾所周知的設置。

我認為對於隨機選擇的元素 $ a \in \mathcal R_q $ ，據我所知，代數範數 $ N(a) $ 近似於 $ q^n $ . （但我對此也沒有任何參考。）因此，我另外猜測由生成的反循環矩陣的行列式 $ \phi(a) $ ， 在哪裡 $ \phi(a) $ 是一個係數嵌入 $ \mathcal R $ 至 $ \mathbb Z^n $ , 也接近 $ q^n $ 以不可忽略的機率。

但是，我找不到任何關於親密關係的參考。您能否給我任何參考或該陳述是否正確的答案？

公平警告

1. 我的代數數論有點生疏，而且
2. 這只會將您的問題簡化為（標準）問題，即顯示隨機理想格的最短向量的下限。

回想一下某個數域中的理想格 $ K $ 是一個格子，其形式為 $ L = I\mathcal{O}_K $ , 即是一個理想 $ I $ 在整數環中 $ K $ . 理想格，作為格，滿足 Minkowski 的第一界，即（在維 $ n $ ) $ \lambda_1(L) \leq \sqrt{n} \sqrt[n]{\det L} $ .

現在，給定一個理想晶格 $ I\mathcal{O}_K $ ，注意到 $ |N(I)| = |\mathcal{O}_K / I| = \left|\frac{\det I}{\det \mathcal{O}_K}\right| $ ，我們明白了 $$ \lambda_1(I\mathcal{O}_K) \leq \sqrt{n}\sqrt[n]{\det I}\implies \frac{\lambda_1(I\mathcal{O}_K)}{\sqrt{n}\sqrt[n]{\det \mathcal{O}_K}} \leq \sqrt[n]{N(I)}. $$

這將您的問題減少到表明，對於平均理想 $ I $ （或者也許是原則理想 $ (a) $ ), $ \lambda_1(I\mathcal{O}_K) $ 很大。我知道有很好的參考證明存在 $ I $ 這樣 $ \lambda_1(I\mathcal{O}_K) $ 很大（即第 4 節）。一個典型的討論參考，平均整數格有 $ \lambda_1(\mathcal{L}(A)) $ 大是這個還是這個。我還將簡要地（直接）證明 $ \lambda_1(\mathcal{L}(A)) $ 平均大（對於均勻 $ A $ ）。參考文獻中的那些使用了相當強大的工具，即像 Siegal 的積分公式之類的東西。希望直接證明將顯示在理想情況下事情在哪裡崩潰。

讓 $ \mathcal{B}n(c) $ 最多是一個半徑為整數向量的（以零為中心的）球 $ c $ . 讓 $ \mathcal{L}(A) $ 是由矩陣生成的格子 $ A $ ，我們將假設它是均勻隨機的。然後，我們有 $$ \begin{align*} \Pr_A[\lambda_1(\mathcal{L}(A)) > c] &= 1 - \Pr_A[\lambda_1(\mathcal{L}(A)) \leq c]\ & 1 - \Pr_A[\mathcal{L}(A) \cap \mathcal{B}(c) = {0}]\ &\geq 1 - |\mathcal{B}(c)\setminus{0}| \max{z\in\mathcal{B}(c)\setminus{0}}\Pr_A[z \in\mathcal{L}(A)]. \end{align*} $$ 我們現在所做的就是重新安排事情，並應用聯合約束。剩下的就是

1. 估計 $ |\mathcal{B}(c)\setminus{0}| $ ， 和
2. 計算 $ \Pr_A[z \in\mathcal{L}(A)] $ .

第一個是標準（數學）計算，參見權利要求 8.2。第二個也是標準的（至少對於整數格）—一個有 $$ \max_{z\neq 0}\Pr_A[z \in\mathcal{L}(A)] = \frac{|\mathcal{L}(A)\setminus {0}|}{|\mathbb{Z}^n/q\mathbb{Z}^n\setminus{0}|} = \frac{q^n-1}{\det \mathcal{L}(A) - 1}. $$ 對於整數格，計算起來很簡單 $ \det \mathcal{L}(A) $ （例如見這個）。但這（大致）是我們在理想情況下試圖降低的界限，即我們減少了下限 $ N(a) $ 到下界 $ \lambda_1(a\mathcal{O}_K) $ 到下界 $ \det a\mathcal{O}_K \approx N(a)\dots $

引用自：https://crypto.stackexchange.com/questions/102338