Lattice-Crypto
關於 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 的格的高斯啟發式算法。這不取決於輸入基的範數。