關於 LLL 和 BKZ 能力的格約簡問題

我一直在閱讀如何估計 SIS 實例的硬度？並關注它的一些消息來源，我想確認一些事情。

LLL 算法在多項式時間內執行，但不能產生任意小的基，因此在大多數基於格的方案中與密碼分析不太相關。那是對的嗎？

BKZ 算法呼叫 SVP（最短向量問題）oracle 多項式的次數，它產生的基範數​​的下界與 SVP oracle 操作的塊大小成反比，而與輸入基的範數無關; 它使用的 SVP 預言機在時間上與塊大小成指數關係。那是對的嗎？

是的，如果您使用篩選在 BKZ 中實例化 SVP 預言機，那麼時間和記憶體的成本是指數級的。（如果您使用列舉實例化它，那麼成本是 $ k^{1/8,k + o(k)} $ ）。輸出向量的範數預計為 $ \delta_k^{d-1} \cdot \operatorname{Vol}(\Lambda)^{1/d} $ 和 $ \delta_k \approx GH(k)^{1/(k-1)} $ . 這裡 $ \operatorname{Vol}(\Lambda) $ 是晶格的體積，並且 $ GH(k) \approx \sqrt{k/(2\pi e)} $ 是體積為 1 的格的高斯啟發式算法。這不取決於輸入基的範數。

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