Introduction
Closest Vector Problem (CVP) 是 Shortest Vector Problem (SVP) 的一種變化，本來 SVP 是問離原點最近的格點在哪裡，CVP 則是問距離某個給定點最近的格點在哪裡。注意到 SVP 並不是 CVP 的特例，因為如果你問離原點最近的格點在哪裡，答案一定是原點。
為了統一符號，格點的基底是 \(n\) 個 \(n\) 維向量 \(b_1, b_2, \cdots, b_n\)，然後我們想要找格點 \(A = \sum a_ib_i\) 使得它離 \(Y(y_1, y_2, \cdots, y_n)\) 越近越好。解決這個問題毫不意外得靠強大的 LLL 演算法，以下介紹兩種簡單的方式。
Embedded Method
首先我們要先估計最短的向量大概有多長，令這個長度為 \(M\)，那我們考慮
\[\begin{pmatrix} & & b_1 & & & 0\\ & & b_2 & & & 0\\ & & \vdots & & &\\ & & b_n & & & 0\\ y_1 & y_2 & \cdots & y_{n-1} & y_n & M\\ \end{pmatrix}\]
其中一個好的格點會是 \(\begin{pmatrix}(Y-A) & M\end{pmatrix}\)，長度大約是 \(\sqrt{2}M\)。可以注意到如果 \(M\) 越大，那演算法越有可能不選最後一列，也就是說演算法直接變成計算 \(\{b_i\}\) 的 SVP，反過來 \(M\) 越小，演算法可能把最後一列乘上稍微大一點的係數，而這個係數只要不是 \(\pm 1\) 就不是我們要的答案。所以這個演算法比較適合用在 \(\{b_i\}\) 的 SVP 答案比 \(M\) 還要大的狀況。
Babai Rounding Technique
這個作法想法十分簡單，我們直接考慮以下方程式的解
\(\begin{pmatrix} x_1 & x_2 & \cdots & x_n \end{pmatrix} \begin{pmatrix} && b_1 && \\ && b_2 && \\ && \vdots && \\ && b_n && \end{pmatrix}= \begin{pmatrix} y_1 & y_2 & \cdots & y_n \end{pmatrix}\)
換句話說 \(Y = \sum x_ib_i\)。那我們直接選擇 \(a_i = \lfloor x_i\rceil\)，也就是四捨五入 \(x_i\)。這個做法不一定能找到很好的解，但是如果我們不使用 \(\{b_i\}\)，而是使用 LLL-reduced 的基底 \(\{b_i^{*}\}\) 的話，就可以確保找到的解和最佳解只差 exponential constant factor。
Hidden Number Problem
最後舉一個 CTF 中會用到 CVP 的例子 Hidden Number Problem (HNP)。給定 \(\{x_i\}\), \(\{y_i\}\), \(p\)，我們想要找 \(\alpha\) 使得對於所有 \(i\)， \(\alpha x_i\) 模 \(p\) 底下很接近 \(y_i\)，也就是說有個上界 \(B\) 滿足
\[\forall i,\,|(\alpha x_i - y_i)\,\%\,p| < B\]
我們會發現這個問題可以被轉換成 CVP：考慮以下格點
\[\begin{pmatrix} p & & &\\ & p & &\\ & & \ddots&\\ & & & p\\ x_1 & x_2 & \cdots & x_n & \frac{B}{p} \end{pmatrix}\]
最後一列乘上 \(\alpha\)，然後其他列消去 \(p\) 的倍數會形成一個很接近 \(\{y_i\}\) 的向量。如果用 embedded method 做的話，通常取 \(M = B\)。雖然把 \(x_i\) 列乘上 \(p\)，\(y_i\) 列乘上 \(0\)會得到一個很小的向量 \(\begin{pmatrix} 0 & 0 & \cdots & B & 0 \end{pmatrix}\)，但這個向量和我們要的向量幾乎垂直，所以答案很有可能藏在第二小的向量裡面。