對偶在 RLWE 中的意義
在代數數域中，理想 $ I $ 在整數環中 $ \mathcal{O}K $ 有雙 $ I^\vee = {x\in\mathcal{O}K\text{ : }T{K/\mathbb{Q}}(xy)\in\mathbb{Z}\text{ for all }y\in I} $ ， 在哪裡 $ T{K/\mathbb{Q}}(\cdot) $ 是場跡。一個格子 $ \mathcal{L} $ 在 $ \mathbb{R}^n $ 有雙 $ \mathcal{L}^\ast = {x\in\mathbb{R}^n\text{ : }\langle x,y\rangle\in\mathbb{Z}\text{ for all }y\in\mathcal{L}} $ ， 在哪裡 $ \langle\cdot,\cdot \rangle $ 是內積。從RLWE 論文的第 14 頁開始，其中 $ \sigma $ 是規範嵌入和 $ \mathcal{L}\subset K $ :
不難看出，在canonical embedding下， $ \mathcal{L}^{\vee} $ 嵌入為對偶晶格的複共軛，即 $ \sigma\left(\mathcal{L}^{\vee}\right)=\overline{\sigma(\mathcal{L})^{*}} $ . 這是因為 $ \operatorname{Tr}(x y)=\sum_{i} \sigma_{i}(x) \sigma_{i}(y)=\langle\sigma(x), \overline{\sigma(y)}\rangle $ .
我的問題是：為什麼雙重理想 $ I^\vee $ 在 RLWE 中使用？是因為原始 LWE 論文的引理 3.14 的證明中存在量子傅里葉變換嗎？還是說RLWE的引理 4.7 （從 BDD 減少到 RLWE）是正確的？還是因為別的什麼原因？
請注意，對於 RLWE 的安全性，您並不嚴格需要雙重理想，如果您不使用它，您只會降低效率。請參閱代數結構 LWE 第 4 頁，對此進行了重新訪問以獲取一些評論。它確實出現在“對偶上的有界距離解碼 -> 原始上的離散高斯採樣 -> 對偶上的 BDD -> $ \dots $ “ 減少鏈，這是最壞情況減少平均情況的關鍵。粗略地說，引理 3.14 是這些步驟之一（使用量子傅里葉變換來表明對偶上的 BDD 意味著原始上的 DGS），並且引理 4.7 是另一個。這兩個步驟都涉及從格上的某個問題到對偶上的問題，但是，正如我最初所說，可以（稍後）通過從 Dual-RLWE 減少到 Primal-RLWE 將其從 RLWE 中刪除，以擴大誤差大小為代價。