Peikert 對 R-LWE 的攻擊框架：“reduction modulo q”是什麼意思？
我正在讀佩克特的論文$$ Pei16 $$關於 R-LWE 問題的安全實例化。在3.1節中，作者給出了一個新的攻擊框架，使用“reduction modulo an Ideal divisor ” $ \mathfrak{q} $ 模數的 $ qR $ “。我對代數數論有點陌生，所以我不理解這個框架，尤其是以下部分：
“讓 $ \mathfrak{q} ⊆ R $ 成為理想的除數 $ qR $ , 有範數 $ N(\mathfrak{q}) := |R/\mathfrak{q}| $ ， 然後讓 $ ψ $ 是一個連續的誤差分佈 $ K_\mathbb{R} $ . 給定 Ring-LWE 樣本 $ (a_i, b_i = s · a_i + e_i) \in R_q × K_\mathbb{R}/qR $ 在哪裡 $ a_i ← R_q $ 和 $ e_i ← ψ $ ，我們可以減少它們模 $ \mathfrak{q} $ 獲取樣品 $ (a’_i = a_i \mod \mathfrak{q} , b’i = b_i \mod \mathfrak{q}) \in R/{\mathfrak{q}} × K\mathbb{R}/\mathfrak{q} $ "
什麼“減模 $ \mathfrak{q} $ “是什麼意思？誰能幫我澄清一下？舉個例子就完美了。
回想一下，任何理想 $ I $ 的 $ R $ 特別是一個加法子群 $ R $ ，並且商 $ R/I $ 是陪集的集合 $ a + I = {a + i : i \in I} $ 對於每個 $ a \in R $ . 兩個陪襯 $ a+I, b+I $ 相等當且當 $ a-b \in I $ . 發送的地圖 $ a \in R $ 至 $ a + I \in R/I $ 被稱為“減少模 $ I $ ”，而且經常寫成“ $ a \bmod I $ 。”商 $ R/I $ 是通過誘導環操作從 $ R $ 本身： $ (a+I) + (b+I) = (a+b) + I $ 和類似的乘法。
現在假設我們有一些理想的除數 $ J $ 的 $ I $ ， IE， $ J \supseteq I $ . “自然”或“還原”模式 $ J $ “同態從 $ R/I $ 至 $ R/J $ 只是發送 $ a+I $ 至 $ a+J $ . 這是很好定義的，因為如果 $ a+I = b+I $ ， 然後 $ a+J=b+J $ 因為 $ a - b \in I \subseteq J $ . （您可以輕鬆檢查這既是加法同態又是乘法同態。）
在目前的情況下，我們有 $ I=qR $ 和一個理想的除數 $ J = \mathfrak{q} \supseteq I $ . 對於 Ring-LWE 樣本 $ (a_i, b_i = s \cdot a_i + e_i) $ ，我們應該查看 $ a_i \in R/qR $ 作為陪襯 $ a_i + qR $ . 減少它模 $ \mathfrak{q} $ 只是意味著將它發送到陪襯 $ a’_i = a_i + \mathfrak{q} \in R/\mathfrak{q} $ . 同樣，我們發送陪集 $ b_i + qR $ 到陪護
$$ \begin{equation} b’_i = b_i + \mathfrak{q} = (s \cdot a_i + e_i) + \mathfrak{q} = (s \cdot a’_i + e_i) + \mathfrak{q}. \end{equation} $$ 請注意，最後一個等式成立，因為 $ s \in R $ , $ \mathfrak{q} $ 是一個理想，並且 $ (a_i - a’_i) = \mathfrak{q} $ ， 所以 $ s \cdot (a_i - a’_i) \subseteq \mathfrak{q} $ . 這一切的結果是我們可以改造“mod $ qR $ " Ring-LWE 樣本 $ (a_i, b_i) $ 進入“模組 $ \mathfrak{q} $ “樣本 $ (a’_i, b’_i) $ . 但是，正如論文指出的那樣，如果誤差分佈 $ \psi $ 是非常“平滑”的模數 $ \mathfrak{q} $ —即，如果 $ e + \mathfrak{q} $ 非常接近制服 $ e \gets \psi $ —那么生成的樣本是無用的： $ (a’_i, b’_i) $ 只是統一的垃圾，並且（理論上的資訊）不可能恢復任何關於 $ s $ 從中。