為什麼在求解 CVP 時最近平面算法的基數會減少

在 Babai 最近平面算法（求解 CVP 的近似版本）中，給定基作為輸入的第一步是找到約簡基（使用 LLL 約簡算法）。為什麼減少的基礎用於進一步的步驟？

簡短回答：如果基礎沒有減少，那麼與目標與實際最近向量之間的距離相比，目標與輸出之間的距離無法保證。通過 LLL 減少基礎，您可以限制該距離，因此 Babai 的最近平面算法將 CVP 求解到某個近似值。

看一下八佰最近平面算法的第二步，其中 $ t $ 指目標向量。

$ b \leftarrow t $

為了 $ i = n $ 做1

$ \quad b \leftarrow b - c_i b_i $ 在哪裡 $ c_i = \lceil \langle b, \tilde b_i \rangle / \langle \tilde b_i, \tilde b_i \rangle \rfloor $

結束

輸出 $ t-b $

其中波浪號表示基的 Gram-Schmidt 正交化。本質上，它尋找接近目標向量的基向量的整數組合。

現在，如果 $ t \in $ 跨度 $ (B) $ ，你可以看到你可以限制輸出和之間的距離 $ t $ 由總和 $ \langle \tilde b_i, \tilde b_i \rangle $ . LLL 為我們提供了這些值的界限。對於任意基礎，這些規範可能非常大，這意味著第二步可能非常非常偏離。

在這種情況下 $ t \notin $ 跨度 $ (B) $ ，您可以對的投影使用類似的論點 $ t $ 跨度 $ (B) $ .

有關如何使用基的 LLL 屬性來證明算法正確性的詳細資訊，請參閱本講座。

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