大號3大號3L^3格羅弗搜尋 NTRU 變體
我正在閱讀韋恩·帕特森 (Wayne Patterson) 撰寫的關於密碼學的文章，偶然發現 $ L^3 $ 算法，它減少整數格相對於它們的基數。我還在NIST CFP A8上讀到過，基於 Grover 算法的攻擊實際上並不可行。已經有研究涵蓋了NTRU 變體的群環中的漏洞，另外的研究表明近似最近的向量在多項式時間內返回近似最短的向量。
Wayne Patterson 的“電腦科學家和數學家的數學密碼學”第 70 頁指出：“由 Lenstra、Lenstra 和 Lovasz 開發（並證明可以在多項式時間內執行）的中心算法是約簡基算法。該算法從任何基開始 $ \beta_{i} $ 用於整數格，並最終計算上一節意義上的簡化基。”然後第 72 頁展示瞭如何在針對背包的 Shamir 攻擊中應用 LLL 算法。
再次引用 Patterson 的話，“這兩個定理（6.1 和 6.2）一起給出了一個關於約簡基的向量必須與整個晶格中最短（非零）向量有多接近的估計。” pg。70.
我的問題：為什麼將 NTRU 變體的 LLL 縮減和組結構編碼為 Grover 搜尋中的搜尋空間以返回會破壞 NTRU 方案的輸出是不可行的？這與 NTRU Variants 連結文章中第 4.2 節中的 Coppersmith 和 Shamir 晶格攻擊一致。
這似乎與 Oracle 訪問基於 Goldreich 等人的相關研究的子程序一致。
換一種說法，我們是否可以肯定地知道，如果補充 Grover 搜尋，LLL 減少和格攻擊不會變得更強？
目前，晶格文獻中（至少）有一篇關於使用 Grover 搜尋加速晶格基減少的論文：A Faster Lattice Reduction Method Using Quantum Search。間接地，對格基約簡的子程序也有一些理論上的改進，例如通過量子搜尋加速求解精確 SVP。
但在實踐中，目前在高維中最快的方法可能是 BKZ，使用帶有極端修剪的格列舉作為精確的 SVP 子程序。對於這種方法的組合，我不相信任何人曾經提出過基於 Grover 搜尋的顯著加速，因為這兩種方法都不涉及對長長的預定義列表進行直接搜尋。
備註 1：Grover 搜尋通常會降低解決難題的時間複雜度 $ T $ （經典地）至少到 $ \sqrt{T} $ （數量）。和 $ T $ 在晶格維度上以指數方式縮放，這意味著我們需要將晶格維度最多增加一個因子 $ 2 $ 維護安全。通常，執行時的此類改進不被視為方案的“中斷”。
備註 2：密碼學的所有安全估計都只是：估計。沒有證據表明沒有（經典或量子）算法可以快速解決我們現在認為難以解決的問題。我們只是不知道解決這些問題的任何快速方法。所以我們不能確定密碼學是安全的，無論是經典的還是量子的。