RLWE 中的最近向量問題
我對格子問題最近向量問題 (CVP) 的多項式形式感興趣，或者換句話說，CVP 是否可以“轉移”到 Ring-LWE。
我對這個問題的想法是 CVP 的多項式形式如下所示：
讓 $ R = \mathbb{Z}[X]/\Phi_M(X) $ 及其殘留物 $ R_q = \mathbb{Z}_q[X]/\Phi_M(X) $ 在哪裡 $ q $ 是一個模數並且 $ \Phi_M(X) $ 一個分圓多項式 $ M $ 是 2 的冪。那麼多項式 CVP 問題將是： $ h(x) $ 是具有固定非整數係數的多項式，我們希望找到最接近的多項式 $ u(x) \in R_q = \mathbb{Z}_q[X]/\Phi_M(X) $ 至 $ h(x) $
到目前為止我所擁有的東西非常模糊，所以我想知道是否有人熟悉更準確的定義。（我無法通過線上研究找到一些東西。）
先感謝您
CVP 是一般格的問題。RLWE 是 LWE 對理想格的特化，是所有（一般）格的子集。所以已經可以在環設置中定義一個完全合理的CVP版本——將CVP的定義從一般格特化到理想格。
這就是人們在文學中所做的事情。例如，在基於最壞情況格問題的一般數域中顯示 RLWE 的偽隨機性的論文中，RLWE 與兩個問題有關，即 K-DGS 和 K-SIVP。這些問題在第 9 頁（含蓄地）定義，在
2.2 節中定義的所有格上的計算問題都可以通過將它們限制為數域中的（分數）理想格來專門化 $ K $ . 我們通過在它們前面加上前綴來引用這些專門的問題 $ K $ ，例如， $ K\mathsf{-GDP}{\mathcal{I},r} $ , $ K\mathsf{-DGS}{\gamma} $ ， ETC。
當然，您可以直接在理想晶格上自由定義自己的 CVP 變體。我還不清楚它是否相當於 $ K\mathsf{-CVP} $ , 即 CVP 對分數理想格的特化 $ K $ . 我立即看到的主要問題（作為僅對代數數論有過了解的人，記錄在案）是
- 目前尚不清楚您的定義中的“最接近”是什麼意思。通常，這是通過將“接近”定義為“在規範嵌入中的歐幾里德規範中”或類似的東西來定義的。通過不固定嵌入（係數/規範），您可能意味著兩個非常不同的事情，例如類似於“帶錯誤的多項式學習”問題或 RLWE。對於兩個分圓的力量來說，事情大多是等價的，但準確地說，它仍然是一個好習慣。
- 我不清楚 $ R_q $ 是一個殘差場 $ R $ ? 環的殘差場 $ R $ 通常意味著 $ R / \mathfrak{m} $ 為了 $ \mathfrak{m} $ 一個最大的理想。您的 $ R $ 是真的 $ R / (q) $ ， 和 $ (q) $ 不必是最大的（如 $ q $ 不必是素數，無論是在您的定義中，還是對於 RLWE 來說都很難）。
- 同樣，尚不清楚這意味著什麼 $ h(x) $ 具有非整數係數。如果您修復一些嵌入選擇，這是另一件會更清楚的事情 $ \phi: R \to k^n $ （為了 $ k\in{\mathbb{R}, \mathbb{C}}) $ ，然後讓 $ h\in k^n $ .