ring-LWE 中多項式之間的最小距離
讓 $ R_q=\mathbb{Z}_q[x]/\langle f(x)\rangle $ 在哪裡 $ f(x)=x^n+1 $ ，就像在環 LWE 問題中一樣。
讓 $ a(x) $ 均勻地隨機選擇 $ R_q $ .
問題：是否有任何定理可以限制以下形式的任何兩個多項式之間的距離 $ a(x)s_1(s) $ 和 $ a(x)s_2(x) $ ?
換句話說，什麼是價值 $ d $ 這樣$$ ||a(x)s_1(x)-a(x)s_2(x)||\geq d $$除非機率可忽略不計，對於任何兩個多項式 $ s_1(x),s_2(x)\in R_q $ 和在哪裡 $ ||\cdot|| $ 是平常的 $ L_2 $ 規範？
我假設 $ n $ 是一種力量 $ 2 $ 然後 $ q $ 是一個大於 $ n $ . 我正在丟棄瑣碎的案例 $ s_1 = s_2 $ .
如果你考慮一切 $ \mod q $ ，那麼它很可能超過了 $ a $ 存在 $ s_1 \neq s_2 $ 這樣 $ |a s_1 - a s_2| = \sqrt{n} $ . 的確， $ a $ 是可逆的 $ R_q $ 機率約為 $ 1 - n/q $ . 拿 $ s_2 = s_1 - a^{-1} $ ，那麼你有 $ a s_1 - a s_2 = 1 \mod q $ 和嵌入範數 $ 1 $ 是 $ \sqrt{n} $ .
如果你不考慮這個 $ \mod q $ , 即你在 $ R=\mathbb Z[x]/⟨f(x)⟩ $ ，那麼您正是在要求最小距離 $ \lambda_1(\mathfrak I) $ 理想格的 $ \mathfrak I $ 由產生 $ a $ . 對於這樣一個理想的晶格，我們可以相當精確地估計這個最小距離。一個簡單的下界是 $ \lambda_1(\mathfrak I) \geq \Delta_K^{1/2n} \cdot N(a)^{1/n} $ ， 在哪裡 $ N $ 表示的代數範數 $ a $ （即所有嵌入的乘積），以及 $ \Delta_K $ 是場的判別式 $ K = \mathbb Q(x)/(x^n+1) $ . 原因是最小向量 $ x $ 必須產生一個子理想 $ \mathfrak I $ ， 所以 $ N(x) \geq N(a) $ ， 和 $ |x|^n \geq \Delta_K^{1/2} N(x) $ . Minkowski 定理也給出了一個上限。