Lattice-Crypto
格中的apprSVP
近似最短向量問題(apprSVP) 是一個問題，其中，給定基礎和近似因子 $ \gamma $ （維度的函式 $ n $ )，必須找到一個向量 $ v $ 屬於格子 $ L $ 這樣它的範數小於 $ \gamma $ 乘以格子中最短向量的長度 $ L $ .
但是即使最短向量的長度也很難找到，那麼在定義apprSVP時我們應該用什麼值代替最短向量的長度呢？
正如您所寫，SVP 的算法 $ _\gamma $ 必須輸出一個非零格向量 $ v \in L $ 這樣 $ | v | \leq \gamma \cdot \lambda_1(L) $ ， 在哪裡 $ \lambda_1(L) $ 表示的最小距離 $ L $ . 確實，我們沒有有效的算法來驗證候選人 $ v $ 滿足這個條件，因為 $ \lambda_1(L) $ 似乎很難計算。但這並不意味著需要更改定義： $ \lambda_1(L) $ 是一個定義明確的量，只要算法總是輸出一些 $ v $ 滿足條件，算法正確。
例如，一次可以證明LLL 算法找到一個非零 $ v \in L $ 這樣 $ | v | \leq 2^{n/2} \cdot \lambda_1(L) $ ， 在哪裡 $ n $ 是維度。即使 LLL 不計算，這仍然成立 $ \lambda_1(L) $ 確切地。