猜測 RLWE Search-to-Decision 中的秘密

在On Ideal Lattices and Learning with Errors over Rings中，作者通過猜測 RLWE 秘密證明了搜尋到決策的減少 $ s $ ，並使用猜測從 $ \mathfrak{q}{i} $ - $ \mathrm{LWE}{q, \Psi} \text { to } \mathrm{DecLWE}{q, \Psi}^{i} $ （引理 5.9）。他們對猜測的性質隻字未提， $ g $ ，儘管他們確實繼續考慮是否 $ g\equiv s $ 反對 $ \mathfrak{q}{i} $ 或者 $ g \not\equiv s $ 反對 $ \mathfrak{q}{i} $ . 我的問題是：我們可以假設什麼是真實的 $ g $ ? 關於它的分佈，我們能說些什麼？關於其他行為模 $ \mathfrak{q}{i} $ ，還是在擂台上？或者它只能作為一個環元素而沒有更多的結構嗎？

“猜測”是列舉所有可能值的一部分 $ s\bmod \mathfrak{q}_iR^\vee $ . 減少基本上有兩個部分：

1. 一種判斷猜測是否正確的方法（ $ \mathsf{WDLWE}_{q, \Psi}^i $ 甲骨文）
2. 要嘗試的值的小空間（作為值 $ s\bmod \mathfrak{q}_i R^\vee $ 在 $ R_q^\vee/\mathfrak{q}_iR_q^\vee $ ，從論文的上下文來看，它似乎有大小 $ N(\mathfrak{q}_i) = q = \mathsf{poly}(n) $ ).

然後，您列舉所有可能的猜測，並返回驗證正確的猜測。這是一個確定性的過程（儘管您可以自由選擇特定的順序來列舉事物）。

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