Ring-Lwe
Ring LWE：如何從“均勻分佈”中選擇秘密？
Ring-LWE的密鑰生成算法如下。有一個戒指 $ R_p =Z_p[x]/(x^n + 1) $ . 然後選擇一個均勻隨機的 $ a $ 從 $ R_p $ . 挑選 $ s $ 從適當的分佈。挑選 $ e $ 從誤差分佈（通常是一個恆定大小的高斯分佈）。計算 $ b = as + e $ . 揭示 $ (a, b) $ 作為公鑰和 $ s $ 是秘鑰。
我一直在閱讀同態加密標準。它說 $ s $ 可以從 $ R_p $ . 這怎麼可能？例如，如果（誠然不安全的）選擇 $ n=1 $ 被選中，然後對於任何值 $ a $ , $ b $ 和 $ e $ 有一些價值 $ s $ 滿足方程。更嚴重的是，例如， LPR 方案假設 $ (re - se_1 + e_2) $ 很小以便解密正確。怎麼可能小 $ s $ 均勻地隨機選擇 $ R_p $ ?
你是對的，基本上所有方案都要求秘密在具體意義上很小。雖然我對標準不是很熟悉，但我相信有問題的表格是由 Albrecht 等人的 LWE Estimator 生成的。其文件的這一頁說明了他們支持的各種秘密分發。我希望“統一”對應於“有界統一”，但我不確定哪個特定邊界用於生成該表。
我們先來想想普通的LWE。選擇秘密有兩種方式，一種是對秘密沒有限制；另一種方法是選擇一個簡短的秘密。Applebaum、Cash、Peikert、Sahai證明後者依然穩健。換句話說，秘密可以從多項式環或有界分佈中均勻選擇，具體取決於應用。對於 Ring-LWE 也是如此。